Line data Source code
1 : // Copyright (c) 2019 Made to Order Software Corp. All Rights Reserved
2 : //
3 : // https://snapwebsites.org/project/snapdatabase
4 : // contact@m2osw.com
5 : //
6 : // This program is free software; you can redistribute it and/or modify
7 : // it under the terms of the GNU General Public License as published by
8 : // the Free Software Foundation; either version 2 of the License, or
9 : // (at your option) any later version.
10 : //
11 : // This program is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 : //
16 : // You should have received a copy of the GNU General Public License along
17 : // with this program; if not, write to the Free Software Foundation, Inc.,
18 : // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19 :
20 :
21 : /** \file
22 : * \brief The virtual buffer implementation.
23 : *
24 : * The virtual buffer allows us to access data which is not defined in one
25 : * straight memory buffer but instead scattered between blocks and memory
26 : * buffers (when the amount of data increases we allocate temporary memory
27 : * buffers until we flush the data to file).
28 : */
29 :
30 : // self
31 : //
32 : #include "snapdatabase/data/virtual_buffer.h"
33 :
34 : #include "snapdatabase/exception.h"
35 :
36 :
37 : // C++ lib
38 : //
39 : #include <iomanip>
40 : #include <iostream>
41 :
42 :
43 : // last include
44 : //
45 : #include <snapdev/poison.h>
46 :
47 :
48 :
49 : namespace snapdatabase
50 : {
51 :
52 :
53 :
54 19 : virtual_buffer::vbuf_t::vbuf_t()
55 : {
56 19 : }
57 :
58 :
59 3 : virtual_buffer::vbuf_t::vbuf_t(block::pointer_t b, std::uint64_t offset, std::uint64_t size)
60 : : f_block(b)
61 : , f_offset(offset)
62 3 : , f_size(size)
63 : {
64 3 : }
65 :
66 :
67 :
68 9 : virtual_buffer::virtual_buffer()
69 : {
70 9 : }
71 :
72 :
73 3 : virtual_buffer::virtual_buffer(block::pointer_t b, std::uint64_t offset, std::uint64_t size)
74 : {
75 3 : add_buffer(b, offset, size);
76 3 : }
77 :
78 :
79 3 : void virtual_buffer::add_buffer(block::pointer_t b, std::uint64_t offset, std::uint64_t size)
80 : {
81 3 : if(f_modified)
82 : {
83 : throw snapdatabase_logic_error(
84 : "Virtual buffer was already modified, you can't add"
85 0 : " another buffer until you commit this virtual buffer.");
86 : }
87 :
88 6 : vbuf_t const append(b, offset, size);
89 3 : f_buffers.push_back(append);
90 :
91 3 : f_total_size += size;
92 3 : }
93 :
94 :
95 0 : bool virtual_buffer::modified() const
96 : {
97 0 : return f_modified;
98 : }
99 :
100 :
101 56 : std::size_t virtual_buffer::count_buffers() const
102 : {
103 56 : return f_buffers.size();
104 : }
105 :
106 :
107 66 : std::uint64_t virtual_buffer::size() const
108 : {
109 66 : return f_total_size;
110 : }
111 :
112 :
113 2213 : bool virtual_buffer::is_data_available(std::uint64_t offset, std::uint64_t size) const
114 : {
115 2213 : return offset + size <= f_total_size;
116 : }
117 :
118 :
119 2105 : int virtual_buffer::pread(void * buf, std::uint64_t size, std::uint64_t offset, bool full) const
120 : {
121 2105 : if(size == 0)
122 : {
123 0 : return 0;
124 : }
125 :
126 2105 : if(full
127 2105 : && !is_data_available(offset, size))
128 : {
129 : throw invalid_size(
130 : "Not enough data to read from virtual buffer. Requested to read "
131 0 : + std::to_string(size)
132 0 : + " bytes at "
133 0 : + std::to_string(offset)
134 0 : + ", when the buffer is "
135 0 : + std::to_string(f_total_size)
136 0 : + " bytes total (missing: "
137 0 : + std::to_string((offset + size) - f_total_size)
138 0 : + " bytes).");
139 : }
140 :
141 2105 : std::uint64_t bytes_read(0);
142 2216 : for(auto const & b : f_buffers)
143 : {
144 2216 : if(offset >= b.f_size)
145 : {
146 101 : offset -= b.f_size;
147 : }
148 : else
149 : {
150 2115 : auto sz(size);
151 2115 : if(sz > b.f_size - offset)
152 : {
153 10 : sz = b.f_size - offset;
154 : }
155 2115 : if(b.f_block != nullptr)
156 : {
157 9 : memcpy(buf, b.f_block->data() + b.f_offset + offset, sz);
158 : }
159 : else
160 : {
161 2106 : memcpy(buf, b.f_data.data() + offset, sz);
162 : }
163 2115 : size -= sz;
164 2115 : bytes_read += sz;
165 :
166 2115 : if(size == 0)
167 : {
168 2105 : return bytes_read;
169 : }
170 :
171 10 : buf = reinterpret_cast<char *>(buf) + sz;
172 :
173 10 : offset = 0;
174 : }
175 : }
176 :
177 0 : return bytes_read;
178 : }
179 :
180 :
181 189 : int virtual_buffer::pwrite(void const * buf, std::uint64_t size, std::uint64_t offset, bool allow_growth)
182 : {
183 189 : if(size == 0)
184 : {
185 62 : return 0;
186 : }
187 :
188 254 : if(!allow_growth
189 127 : && !is_data_available(offset, size))
190 : {
191 : throw invalid_size(
192 : "Not enough space to write to virtual buffer. Requested to write "
193 0 : + std::to_string(size)
194 0 : + " bytes at "
195 0 : + std::to_string(offset)
196 0 : + ", when the buffer is "
197 0 : + std::to_string(f_total_size)
198 0 : + " bytes only.");
199 : }
200 :
201 127 : std::uint8_t const * in(reinterpret_cast<std::uint8_t const *>(buf));
202 127 : std::uint64_t bytes_written(0);
203 :
204 127 : auto check_modified = [&]()
205 : {
206 127 : if(!f_modified && bytes_written != 0)
207 : {
208 11 : f_modified = true;
209 : }
210 254 : };
211 :
212 602 : for(auto & b : f_buffers)
213 : {
214 583 : if(offset >= b.f_size)
215 : {
216 472 : offset -= b.f_size;
217 : }
218 : else
219 : {
220 111 : auto sz(size);
221 111 : if(sz > b.f_size - offset)
222 : {
223 3 : sz = b.f_size - offset;
224 : }
225 111 : if(b.f_block != nullptr)
226 : {
227 6 : memcpy(b.f_block->data() + offset, in, sz);
228 : }
229 : else
230 : {
231 105 : memcpy(b.f_data.data() + offset, in, sz);
232 : }
233 111 : size -= sz;
234 111 : bytes_written += sz;
235 :
236 111 : if(size == 0)
237 : {
238 108 : check_modified();
239 108 : return bytes_written;
240 : }
241 :
242 3 : in += sz;
243 :
244 3 : offset = 0;
245 : }
246 : }
247 :
248 : // this can happen if the caller calls us with an empty buffer
249 : //
250 19 : if(size == 0)
251 : {
252 0 : check_modified();
253 0 : return bytes_written;
254 : }
255 :
256 38 : if(!f_buffers.empty()
257 19 : && f_buffers.back().f_block == nullptr)
258 : {
259 10 : std::uint64_t const available(f_buffers.back().f_data.capacity() - f_buffers.back().f_size);
260 10 : if(available > 0)
261 : {
262 5 : auto const sz(std::min(available, size));
263 5 : f_buffers.back().f_data.resize(f_buffers.back().f_size + sz);
264 5 : memcpy(f_buffers.back().f_data.data() + f_buffers.back().f_size, in, sz);
265 5 : size -= sz;
266 5 : bytes_written += sz;
267 5 : f_buffers.back().f_size += sz;
268 5 : f_total_size += sz;
269 :
270 5 : if(size == 0)
271 : {
272 0 : check_modified();
273 0 : return bytes_written;
274 : }
275 :
276 5 : in += sz;
277 : }
278 : }
279 :
280 : // TBD: we may want to allocate multiple buffers of 4Kb instead of
281 : // a buffer large enough for this data? At the same time, we
282 : // can't save exactly 4Kb of data in the blocks anyway...
283 : //
284 : // however, we could probably use a form of binary search to
285 : // reduce the number iterations; however, after _many_ insertions
286 : // it is likely that such a search would not be working very well
287 : // and either way we'd need to update offsets though the entire
288 : // list of items
289 : //
290 : // on the other hand maybe we could use a larger buffer such
291 : // as 64Kb at once to avoid too many allocations total
292 : // (or use a hint / user settings / stats / ...)
293 : //
294 38 : vbuf_t append;
295 19 : append.f_data.reserve((size + 4095) & -4096);
296 19 : append.f_data.resize(size);
297 19 : append.f_size = size;
298 :
299 19 : memcpy(append.f_data.data(), in, size);
300 :
301 19 : f_buffers.push_back(append);
302 :
303 19 : bytes_written += size;
304 19 : f_total_size += size;
305 :
306 19 : check_modified();
307 19 : return bytes_written;
308 : }
309 :
310 :
311 29 : int virtual_buffer::pinsert(void const * buf, std::uint64_t size, std::uint64_t offset)
312 : {
313 : // avoid an insert if possible
314 : //
315 29 : if(size == 0)
316 : {
317 0 : return 0;
318 : }
319 :
320 29 : if(offset >= f_total_size)
321 : {
322 10 : return pwrite(buf, size, offset, true);
323 : }
324 :
325 19 : std::uint8_t const * in(reinterpret_cast<std::uint8_t const *>(buf));
326 :
327 : // insert has to happen... search the buffer where it will happen
328 : //
329 132 : for(auto b(f_buffers.begin()); b != f_buffers.end(); ++b)
330 : {
331 132 : if(offset >= b->f_size)
332 : {
333 113 : offset -= b->f_size;
334 : }
335 : else
336 : {
337 19 : if(b->f_block != nullptr)
338 : {
339 : // if inserting within a block, we have to break the block
340 : // in two
341 : {
342 0 : vbuf_t append;
343 0 : append.f_block = b->f_block;
344 0 : append.f_size = b->f_size - offset;
345 0 : append.f_offset = b->f_offset + offset;
346 0 : f_buffers.insert(b + 1, append);
347 : }
348 :
349 0 : b->f_size = offset;
350 :
351 : {
352 0 : vbuf_t append;
353 0 : append.f_size = size;
354 0 : memcpy(append.f_data.data(), in, size);
355 0 : f_buffers.insert(b + 1, append);
356 : }
357 : }
358 : else
359 : {
360 19 : b->f_data.insert(b->f_data.begin() + offset, in, in + size);
361 19 : b->f_size += size;
362 : }
363 19 : f_total_size += size;
364 19 : f_modified = true;
365 19 : return size;
366 : }
367 : }
368 :
369 0 : if(offset == 0)
370 : {
371 : // append at the end
372 : //
373 0 : if(!f_buffers.empty()
374 0 : && f_buffers.back().f_block == nullptr)
375 : {
376 0 : f_buffers.back().f_data.insert(f_buffers.back().f_data.end(), in, in + size);
377 : }
378 : else
379 : {
380 0 : vbuf_t append;
381 0 : append.f_size = size;
382 0 : memcpy(append.f_data.data(), in, size);
383 0 : f_buffers.push_back(append);
384 : }
385 0 : f_total_size += size;
386 0 : f_modified = true;
387 0 : return size;
388 : }
389 :
390 : throw snapdatabase_logic_error(
391 : "Reached the end of the pinsert() function. Offset should be 0, it is "
392 0 : + std::to_string(offset)
393 0 : + " instead, which should never happen.");
394 : }
395 :
396 :
397 0 : int virtual_buffer::perase(std::uint64_t size, std::uint64_t offset)
398 : {
399 0 : if(size == 0)
400 : {
401 0 : return 0;
402 : }
403 :
404 0 : if(offset >= f_total_size)
405 : {
406 0 : return 0;
407 : }
408 :
409 : // clamp the amount of data we can erase
410 : //
411 0 : if(size > f_total_size - offset)
412 : {
413 0 : size = f_total_size - offset;
414 : }
415 :
416 : // since we are going to erase/add some buffers (eventually)
417 : // we need to use our own iterator
418 : //
419 0 : std::uint64_t bytes_erased(0);
420 0 : for(auto it(f_buffers.begin()); it != f_buffers.end() && size > 0; )
421 : {
422 0 : auto next(it + 1);
423 0 : if(offset >= it->f_size)
424 : {
425 0 : offset -= it->f_size;
426 : }
427 : else
428 : {
429 0 : if(size >= it->f_size)
430 : {
431 0 : if(offset == 0)
432 : {
433 : // remove this entry entirely
434 : //
435 0 : size -= it->f_size;
436 0 : f_total_size -= it->f_size;
437 0 : bytes_erased += it->f_size;
438 0 : f_buffers.erase(it);
439 : }
440 : else
441 : {
442 : // remove end of this block
443 : //
444 0 : std::uint64_t const sz(it->f_size - offset);
445 0 : it->f_size = offset;
446 0 : f_total_size -= sz;
447 0 : size -= sz;
448 0 : bytes_erased += sz;
449 0 : offset = 0;
450 : }
451 : }
452 : else
453 : {
454 0 : if(offset == 0)
455 : {
456 : // remove the start of this block
457 : //
458 0 : if(it->f_block != nullptr)
459 : {
460 0 : it->f_offset += size;
461 : }
462 : else
463 : {
464 0 : it->f_data.erase(it->f_data.begin(), it->f_data.begin() + size);
465 : }
466 0 : it->f_size -= size;
467 : }
468 : else
469 : {
470 : // remove data from the middle of the block
471 : //
472 0 : if(it->f_block != nullptr)
473 : {
474 0 : if(offset + size >= it->f_size)
475 : {
476 0 : it->f_offset += offset;
477 0 : it->f_size -= size;
478 : }
479 : else
480 : {
481 0 : vbuf_t append;
482 0 : append.f_block = it->f_block;
483 0 : append.f_size = it->f_size - size - offset;
484 0 : append.f_offset = it->f_offset + size + offset;
485 0 : f_buffers.insert(it, append);
486 :
487 0 : it->f_size = offset;
488 : }
489 : }
490 : else
491 : {
492 0 : it->f_data.erase(it->f_data.begin() + offset, it->f_data.begin() + offset + size);
493 0 : it->f_size -= size;
494 : }
495 : }
496 0 : f_total_size -= size;
497 0 : bytes_erased += size;
498 0 : f_modified = bytes_erased != 0;
499 0 : return bytes_erased;
500 : }
501 : }
502 0 : it = next;
503 : }
504 :
505 0 : f_modified = bytes_erased != 0;
506 0 : return bytes_erased;
507 : }
508 :
509 :
510 :
511 0 : std::ostream & operator << (std::ostream & out, virtual_buffer const & v)
512 : {
513 : // using a separate stringstream makes it more multi-threading impervious
514 : // (because flags are not shared well otherwise)
515 : //
516 0 : std::stringstream ss;
517 :
518 0 : ss << std::hex << std::setfill('0');
519 :
520 0 : char const * newline("");
521 0 : std::uint64_t sz(v.size());
522 0 : for(snapdatabase::reference_t p(0); p < sz; ++p)
523 : {
524 0 : if(p % 16 == 0)
525 : {
526 0 : if(sz > 65536)
527 : {
528 0 : ss << newline << std::setw(8) << p << ": ";
529 : }
530 : else
531 : {
532 0 : ss << newline << std::setw(4) << p << ": ";
533 : }
534 0 : newline = "\n";
535 : }
536 :
537 : char c;
538 0 : if(v.pread(&c, 1, p) != 1)
539 : {
540 0 : throw io_error("Expected to read 1 more byte from virtual buffer.");
541 : }
542 :
543 0 : ss << " " << std::setw(2) << static_cast<int>(c);
544 : }
545 0 : ss << std::endl;
546 0 : return out << ss.str();
547 : }
548 :
549 :
550 :
551 6 : } // namespace snapdatabase
552 : // vim: ts=4 sw=4 et
|
