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 Database file implementation.
23 : *
24 : * Each table uses one or more files. Each file is handled by a dbfile
25 : * object and a corresponding set of blocks.
26 : */
27 :
28 : // self
29 : //
30 : #include "snapdatabase/block/block_free_space.h"
31 :
32 : #include "snapdatabase/block/block_data.h"
33 : #include "snapdatabase/block/block_header.h"
34 : #include "snapdatabase/data/dbfile.h"
35 : #include "snapdatabase/data/dbtype.h"
36 : #include "snapdatabase/database/table.h"
37 :
38 : // boost lib
39 : //
40 : #include <boost/preprocessor/stringize.hpp>
41 :
42 : // last include
43 : //
44 : #include <snapdev/poison.h>
45 :
46 :
47 :
48 : namespace snapdatabase
49 : {
50 :
51 :
52 :
53 :
54 : namespace detail
55 : {
56 :
57 : /** \brief The offset is in case the header of this block grows.
58 : *
59 : * Right now the header of this block is just the magic word. If for some
60 : * reasons we need to add more information, we want to easily be able to
61 : * adjust the offset.
62 : *
63 : * At this time, there is no need so it is zero.
64 : *
65 : * \note
66 : * It is zero because we do not support an offset at position 0 (because
67 : * a size of 0 cannot be allocated).
68 : */
69 : constexpr uint64_t FREE_SPACE_OFFSET = 0;
70 :
71 :
72 : /** \brief Avoid small allocation wasting space.
73 : *
74 : * This parameter is used in an attempt to avoid wasting too much space
75 : * when allocating a new block. Small blocks are likely to be allocated
76 : * anyway so we leave them behind and start using blocks having space
77 : * for `FREE_SPACE_JUMP` references.
78 : */
79 : constexpr uint64_t FREE_SPACE_JUMP = sizeof(reference_t) * 32;
80 :
81 :
82 :
83 : // we can use bits 0 to 7 for our free space flags
84 : //
85 : // bits 8 to 31 are used by the other blocks (mainly the DATA block,
86 : // maybe the BLOB too?) these other bits are defined in how header since
87 : // they need to be accessible from te outside
88 : //
89 : constexpr uint32_t FREE_SPACE_FLAG_ALLOCATED = 0x01;
90 :
91 : struct free_space_meta_t
92 : {
93 : uint32_t f_size = 0;
94 : uint32_t f_flags = 0;
95 : };
96 :
97 :
98 : static_assert(sizeof(free_space_meta_t) == sizeof(reference_t)
99 : , "the free_space_meta_t structure must be exactly equal to one reference_t in size");
100 :
101 :
102 : struct free_space_link_t
103 : {
104 : free_space_meta_t f_meta = free_space_meta_t();
105 : reference_t f_next = 0;
106 : reference_t f_previous = 0;
107 : };
108 :
109 :
110 : static_assert(sizeof(free_space_link_t) % sizeof(reference_t) == 0
111 : , "the free_soace_link_t structure must have a size which is a multiple of sizeof(reference_t)");
112 :
113 :
114 : constexpr uint32_t FREE_SPACE_SIZE_MULTIPLE = sizeof(reference_t) * 4;
115 :
116 : static_assert(FREE_SPACE_SIZE_MULTIPLE >= sizeof(free_space_link_t)
117 : , "FREE_SPACE_SIZE_MULTIPLE must be at least equal to sizeof(fre_space_link_t)");
118 :
119 :
120 :
121 :
122 :
123 : class block_free_space_impl
124 : {
125 : public:
126 : block_free_space_impl(block & b);
127 : block_free_space_impl(block_free_space_impl const & rhs) = delete;
128 :
129 : block_free_space_impl operator = (block_free_space_impl const & rhs) = delete;
130 :
131 : free_space_t get_free_space(uint32_t minimum_size);
132 : void release_space(reference_t offset);
133 :
134 : private:
135 : reference_t * get_free_space_pointer(uint32_t size);
136 : void link_space(reference_t link_offset, free_space_link_t * link);
137 : free_space_link_t * get_link(reference_t r);
138 : void unlink_space(free_space_link_t * link);
139 : uint32_t total_space_available_in_one_data_block();
140 :
141 : block & f_block;
142 : };
143 :
144 :
145 :
146 0 : block_free_space_impl::block_free_space_impl(block & b)
147 0 : : f_block(b)
148 : {
149 0 : }
150 :
151 :
152 0 : reference_t * block_free_space_impl::get_free_space_pointer(uint32_t size)
153 : {
154 0 : if(size == 0)
155 : {
156 0 : throw snapdatabase_logic_error("You cannot call get_free_space_pointer() with a size of 0.");
157 : }
158 :
159 0 : size += FREE_SPACE_SIZE_MULTIPLE - 1;
160 0 : size /= FREE_SPACE_SIZE_MULTIPLE;
161 :
162 0 : return reinterpret_cast<reference_t *>(f_block.data() + FREE_SPACE_OFFSET) + size;
163 : }
164 :
165 :
166 0 : void block_free_space_impl::link_space(reference_t link_offset, free_space_link_t * link)
167 : {
168 0 : reference_t * d(get_free_space_pointer(link->f_meta.f_size));
169 :
170 0 : link->f_meta.f_flags &= ~FREE_SPACE_FLAG_ALLOCATED;
171 0 : link->f_next = *d;
172 0 : link->f_previous = 0;
173 0 : *d = link_offset;
174 0 : }
175 :
176 :
177 0 : free_space_link_t * block_free_space_impl::get_link(reference_t r)
178 : {
179 0 : if(r == 0)
180 : {
181 0 : throw snapdatabase_logic_error("You cannot call get_link() with a reference of 0.");
182 : }
183 :
184 0 : block::pointer_t b(f_block.get_table()->get_block(r));
185 :
186 0 : return reinterpret_cast<free_space_link_t *>(b->data(r));
187 : }
188 :
189 :
190 0 : void block_free_space_impl::unlink_space(free_space_link_t * link)
191 : {
192 0 : if(link->f_previous != 0)
193 : {
194 0 : free_space_link_t * p(get_link(link->f_previous));
195 0 : p->f_next = link->f_next;
196 : }
197 : else
198 : {
199 : // this is a "first link" which means this pointer appears in the
200 : // free space array
201 : //
202 0 : reference_t * d(get_free_space_pointer(link->f_meta.f_size));
203 0 : *d = link->f_next;
204 : }
205 :
206 0 : if(link->f_next != 0)
207 : {
208 0 : free_space_link_t * n(get_link(link->f_next));
209 0 : n->f_previous = link->f_previous;
210 : }
211 :
212 : // this is not needed we're about to smash that data anyway and it is
213 : // safe (in case it did not get overwritten, it's not secret information)
214 : //
215 : //link->f_next = 0;
216 : //link->f_previous = 0;
217 0 : }
218 :
219 :
220 0 : uint32_t block_free_space_impl::total_space_available_in_one_data_block()
221 : {
222 : static uint32_t total_space(0);
223 :
224 0 : if(total_space == 0)
225 : {
226 0 : total_space = block_data::block_total_space(f_block.get_table());
227 0 : total_space -= total_space % sizeof(reference_t);
228 : }
229 :
230 0 : return total_space;
231 : }
232 :
233 :
234 0 : free_space_t block_free_space_impl::get_free_space(uint32_t minimum_size)
235 : {
236 : // we always keep the size & flags
237 : //
238 : // (i.e. we return the free space reference + sizeof(free_space_meta_t)
239 : // so we have to allocate that much more space; that's a loss of about
240 : // 4Mb/1,000,000 rows)
241 : //
242 0 : minimum_size += sizeof(free_space_meta_t);
243 :
244 : // make the size a multiple of free_space_link_t rounded up
245 : //
246 0 : minimum_size += sizeof(free_space_link_t) - 1;
247 0 : minimum_size -= minimum_size % sizeof(free_space_link_t);
248 :
249 0 : uint32_t const total_space(total_space_available_in_one_data_block());
250 0 : if(minimum_size > total_space)
251 : {
252 : throw snapdatabase_logic_error(
253 : "get_free_space() called with a minimum_size ("
254 0 : + std::to_string(minimum_size)
255 0 : + " > "
256 0 : + std::to_string(total_space)
257 0 : + ") larger than what can be allocated.");
258 : }
259 :
260 0 : free_space_t result;
261 0 : result.f_size = minimum_size;
262 :
263 0 : reference_t * d(get_free_space_pointer(minimum_size));
264 0 : result.f_reference = *d;
265 :
266 0 : if(result.f_reference != 0)
267 : {
268 : // we got an extact match! remove that space from the list
269 : //
270 0 : unlink_space(get_link(result.f_reference));
271 0 : result.f_reference += sizeof(free_space_meta_t);
272 0 : result.f_block = f_block.get_table()->get_block(result.f_reference);
273 0 : return result;
274 : }
275 :
276 : // if allocating a rather small space, jump to a larger one at once
277 : // which allows us to keep smaller free spaces intact instead of
278 : // breaking them into even smaller free spaces
279 : //
280 0 : if(minimum_size < FREE_SPACE_JUMP)
281 : {
282 0 : d = get_free_space_pointer(FREE_SPACE_JUMP);
283 : }
284 : else
285 : {
286 0 : ++d;
287 : }
288 :
289 : // the linked list is sizeof(free_space_link_t) which is why we divide
290 : // the get_page_size() by sizeof(free_space_link_t)
291 : //
292 : // TODO: adjust the maximum with the `DATA` header subtracted since
293 : // we cannot ever allocate an entire block; it may save us one
294 : // iteration on each allocation attempt?
295 : //
296 0 : reference_t * end(get_free_space_pointer(f_block.get_table()->get_page_size()));
297 :
298 : // search for a large free space and allocate the buffer you are
299 : // asking for
300 : //
301 0 : while(d < end)
302 : {
303 0 : result.f_reference = *reinterpret_cast<reference_t *>(d);
304 0 : if(result.f_reference != 0)
305 : {
306 0 : free_space_link_t * link(get_link(result.f_reference));
307 0 : unlink_space(link);
308 :
309 : // enough space to break free space in two?
310 : //
311 0 : uint32_t new_size(link->f_meta.f_size - minimum_size);
312 0 : if(new_size >= sizeof(free_space_meta_t))
313 : {
314 0 : data_t data(reinterpret_cast<data_t>(link));
315 0 : free_space_link_t * new_link(reinterpret_cast<free_space_link_t *>(data + minimum_size));
316 0 : new_link->f_meta.f_size = link->f_meta.f_size - minimum_size;
317 0 : link->f_meta.f_size = minimum_size;
318 0 : new_link->f_meta.f_flags = 0;
319 0 : link_space(result.f_reference + minimum_size, new_link);
320 : }
321 : else
322 : {
323 0 : result.f_size = link->f_meta.f_size;
324 : }
325 :
326 0 : link->f_meta.f_flags |= FREE_SPACE_FLAG_ALLOCATED;
327 :
328 0 : result.f_reference += sizeof(free_space_meta_t);
329 0 : result.f_block = f_block.get_table()->get_block(result.f_reference);
330 0 : return result;
331 : }
332 : }
333 :
334 : // no space available, we have to allocate a new `DATA` block
335 : //
336 : {
337 0 : block::pointer_t data_block(f_block.get_table()->allocate_new_block(dbtype_t::BLOCK_TYPE_DATA));
338 :
339 : // the following skips the header and aligns "start" to the next
340 : // sizeof(reference_t) boundary
341 : //
342 0 : reference_t start(f_block.get_table()->get_page_size() - total_space);
343 0 : result.f_reference = start;
344 0 : free_space_link_t * link(reinterpret_cast<free_space_link_t *>(data_block->data() + start));
345 0 : start += minimum_size;
346 0 : uint32_t const remaining_size(total_space - minimum_size);
347 0 : if(remaining_size >= sizeof(free_space_meta_t))
348 : {
349 0 : free_space_link_t * new_link(reinterpret_cast<free_space_link_t *>(data_block->data() + start));
350 0 : new_link->f_meta.f_size = remaining_size;
351 0 : new_link->f_meta.f_flags = 0;
352 0 : link_space(data_block->get_offset() + start, new_link);
353 :
354 0 : link->f_meta.f_size = total_space - remaining_size;
355 : }
356 : else
357 : {
358 0 : link->f_meta.f_size = total_space;
359 : }
360 :
361 0 : link->f_meta.f_flags = FREE_SPACE_FLAG_ALLOCATED;
362 :
363 0 : result.f_reference += sizeof(free_space_meta_t);
364 0 : result.f_block = f_block.get_table()->get_block(result.f_reference);
365 0 : return result;
366 : }
367 : }
368 :
369 :
370 0 : void block_free_space_impl::release_space(reference_t offset)
371 : {
372 0 : if(offset % sizeof(reference_t) != 0)
373 : {
374 : throw snapdatabase_logic_error(
375 : "release_space() called with an invalid offset ("
376 0 : + std::to_string(offset)
377 0 : + "); it must be a multiple of "
378 0 : + BOOST_PP_STRINGIZE(sizeof(reference_t))
379 0 : + ".");
380 : }
381 :
382 0 : offset -= sizeof(free_space_meta_t);
383 0 : block::pointer_t b(f_block.get_table()->get_block(offset));
384 0 : free_space_link_t * link(reinterpret_cast<free_space_link_t *>(b->data(offset)));
385 :
386 0 : if(f_block.get_table()->is_secure())
387 : {
388 : // keep reseting the data when releasing it
389 : //
390 0 : memset(reinterpret_cast<data_t>(link + 1), 0, link->f_meta.f_size - sizeof(link->f_meta));
391 : }
392 :
393 0 : uint32_t const next_pos(link->f_meta.f_size + offset % f_block.get_table()->get_page_size());
394 0 : uint32_t const total_space(total_space_available_in_one_data_block());
395 0 : if(next_pos + sizeof(free_space_link_t) < total_space)
396 : {
397 0 : free_space_link_t * next_link(reinterpret_cast<free_space_link_t *>(b->data(next_pos)));
398 0 : if((next_link->f_meta.f_flags & FREE_SPACE_FLAG_ALLOCATED) != 0)
399 : {
400 : // merge the next with this one
401 : //
402 0 : link->f_meta.f_size += next_link->f_meta.f_size;
403 0 : unlink_space(next_link);
404 : }
405 : }
406 :
407 0 : reference_t start(f_block.get_table()->get_page_size() - total_space);
408 0 : if((link - reinterpret_cast<free_space_link_t *>(0)) % f_block.get_table()->get_page_size() > start)
409 : {
410 0 : free_space_link_t * previous_link(reinterpret_cast<free_space_link_t *>(b->data(start)));
411 0 : for(reference_t o(start);;)
412 : {
413 : ;
414 0 : free_space_link_t * link_after(reinterpret_cast<free_space_link_t *>(reinterpret_cast<data_t>(previous_link) + previous_link->f_meta.f_size));
415 0 : if(link_after == link)
416 : {
417 0 : if((previous_link->f_meta.f_flags & FREE_SPACE_FLAG_ALLOCATED) == 0)
418 : {
419 0 : unlink_space(previous_link);
420 0 : previous_link->f_meta.f_size += link->f_meta.f_size;
421 0 : link_space(o, previous_link);
422 :
423 0 : link = previous_link;
424 : }
425 0 : break;
426 : }
427 0 : else if(link_after > link)
428 : {
429 0 : break;
430 : }
431 0 : o += previous_link->f_meta.f_size;
432 0 : previous_link = link_after;
433 0 : }
434 : }
435 :
436 : // for the previous we need to start searching from the beginning of the
437 : // block; the `DATA` is an array of
438 : //
439 :
440 0 : link_space(offset, link);
441 :
442 : // TODO: look into agglomerating multiple free spaces if immediately
443 : // possible; here are the 4 possible cases
444 : //
445 : // 1. nothing before, nothing after, done
446 : // 2. something before, enlarge previous block
447 : // 3. something after, enlarge & move next block
448 : // 4. something before and after, enlarge previous block, drop next block
449 : //
450 : // right now, though we do not have a good way of finding a
451 : // previous block; the next block, though, should be at this
452 : // block + size so that one is easy and the block header is
453 : // enough to find it in our FSPC table
454 0 : }
455 :
456 :
457 :
458 : } // detail namespace
459 :
460 :
461 :
462 : namespace
463 : {
464 :
465 :
466 :
467 : // 'FSPC'
468 : constexpr struct_description_t g_description[] =
469 : {
470 : define_description(
471 : FieldName("header")
472 : , FieldType(struct_type_t::STRUCT_TYPE_STRUCTURE)
473 : , FieldSubDescription(detail::g_block_header)
474 : ),
475 : // TBD: it may be useful to determine a minimum size larger than
476 : // sizeof(free_space_link_t) for some tables and use that to
477 : // make sure we don't break blocks to sizes smaller than that
478 : //define_description(
479 : // FieldName("minimum_size")
480 : // , FieldType(struct_type_t::STRUCT_TYPE_UINT32)
481 : //),
482 : // the following is an aligned array of references
483 : //define_description(
484 : // FieldName("free_space")
485 : // , FieldType(struct_type_t::STRUCT_TYPE_UINT128)
486 : //),
487 : end_descriptions()
488 : };
489 :
490 :
491 : constexpr descriptions_by_version_t const g_descriptions_by_version[] =
492 : {
493 : define_description_by_version(
494 : DescriptionVersion(0, 1),
495 : DescriptionDescription(g_description)
496 : ),
497 : end_descriptions_by_version()
498 : };
499 :
500 :
501 :
502 : }
503 : // no name namespace
504 :
505 :
506 :
507 :
508 0 : block_free_space::block_free_space(dbfile::pointer_t f, reference_t offset)
509 : : block(g_descriptions_by_version, f, offset)
510 0 : , f_impl(std::make_unique<detail::block_free_space_impl>(*this))
511 : {
512 0 : }
513 :
514 :
515 0 : block_free_space::~block_free_space()
516 : {
517 0 : }
518 :
519 :
520 0 : free_space_t block_free_space::get_free_space(uint32_t minimum_size)
521 : {
522 0 : return f_impl->get_free_space(minimum_size);
523 : }
524 :
525 :
526 0 : void block_free_space::release_space(reference_t offset)
527 : {
528 0 : return f_impl->release_space(offset);
529 : }
530 :
531 :
532 0 : bool block_free_space::get_flag(data_t ptr, uint32_t flag)
533 : {
534 0 : detail::free_space_meta_t * meta(reinterpret_cast<detail::free_space_meta_t *>(ptr) - 1);
535 0 : return (meta->f_flags & flag) != 0;
536 : }
537 :
538 :
539 0 : void block_free_space::set_flag(data_t ptr, uint32_t flag)
540 : {
541 0 : detail::free_space_meta_t * meta(reinterpret_cast<detail::free_space_meta_t *>(ptr) - 1);
542 0 : meta->f_flags |= flag;
543 0 : }
544 :
545 :
546 0 : void block_free_space::clear_flag(data_t ptr, uint32_t flag)
547 : {
548 0 : detail::free_space_meta_t * meta(reinterpret_cast<detail::free_space_meta_t *>(ptr) - 1);
549 0 : meta->f_flags &= ~flag;
550 0 : }
551 :
552 :
553 :
554 : } // namespace snapdatabase
555 : // vim: ts=4 sw=4 et
|
