Branch data Line data Source code
1 : : /* flint_btreebase.cc: Btree base file implementation
2 : : *
3 : : * Copyright 1999,2000,2001 BrightStation PLC
4 : : * Copyright 2002,2003,2004,2006,2008,2011 Olly Betts
5 : : * Copyright 2010 Richard Boulton
6 : : *
7 : : * This program is free software; you can redistribute it and/or
8 : : * modify it under the terms of the GNU General Public License as
9 : : * published by the Free Software Foundation; either version 2 of the
10 : : * License, or (at your option) any later version.
11 : : *
12 : : * This program is distributed in the hope that it will be useful,
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : * GNU General Public License for more details.
16 : : *
17 : : * You should have received a copy of the GNU General Public License
18 : : * along with this program; if not, write to the Free Software
19 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
20 : : * USA
21 : : */
22 : :
23 : : #include <config.h>
24 : :
25 : : #include "safeerrno.h"
26 : : #ifdef __WIN32__
27 : : # include "msvc_posix_wrapper.h"
28 : : #endif
29 : :
30 : : #include "flint_btreebase.h"
31 : : #include "flint_utils.h"
32 : : #include "io_utils.h"
33 : : #include "str.h"
34 : : #include "utils.h"
35 : : #include <xapian/error.h>
36 : : #include "omassert.h"
37 : :
38 : : #include <climits>
39 : :
40 : : #include <algorithm>
41 : : #include <cstring>
42 : :
43 : : using namespace std;
44 : :
45 : : /************ Base file parameters ************/
46 : :
47 : : /** This is the current description of the base file format:
48 : : *
49 : : * Numbers are (unless mentioned otherwise) stored in the variable
50 : : * length format used by F_pack_uint() - that is 7 bits at a time in
51 : : * a byte, starting with lower-order bits, and setting the high bit
52 : : * on all bytes before the last one.
53 : : *
54 : : * The format consists of a sequence of numbers in this order:
55 : : *
56 : : * REVISION
57 : : * FORMAT will be = CURR_FORMAT for the current format. If this value
58 : : * higher then it is a different format which we
59 : : * doesn't yet understand, so we bomb out. If it's lower,
60 : : * then it depends if we have backwards-compatibility code
61 : : * implemented (we don't for format versions < 5).
62 : : * BLOCK_SIZE
63 : : * ROOT
64 : : * LEVEL
65 : : * BIT_MAP_SIZE
66 : : * ITEM_COUNT
67 : : * LAST_BLOCK
68 : : * HAVE_FAKEROOT
69 : : * SEQUENTIAL
70 : : * REVISION2 A second copy of the revision number, for consistency checks.
71 : : * BITMAP The bitmap. This will be BIT_MAP_SIZE raw bytes.
72 : : * REVISION3 A third copy of the revision number, for consistency checks.
73 : : */
74 : : #define CURR_FORMAT 5U
75 : :
76 : 37830 : FlintTable_base::FlintTable_base()
77 : : : revision(0),
78 : : block_size(0),
79 : : root(0),
80 : : level(0),
81 : : bit_map_size(0),
82 : : item_count(0),
83 : : last_block(0),
84 : : have_fakeroot(false),
85 : : sequential(false),
86 : : bit_map_low(0),
87 : : bit_map0(0),
88 : 37830 : bit_map(0)
89 : : {
90 : 37830 : }
91 : :
92 : 0 : FlintTable_base::FlintTable_base(const FlintTable_base &other)
93 : : : revision(other.revision),
94 : : block_size(other.block_size),
95 : : root(other.root),
96 : : level(other.level),
97 : : bit_map_size(other.bit_map_size),
98 : : item_count(other.item_count),
99 : : last_block(other.last_block),
100 : : have_fakeroot(other.have_fakeroot),
101 : : sequential(other.sequential),
102 : : bit_map_low(other.bit_map_low),
103 : : bit_map0(0),
104 : 0 : bit_map(0)
105 : : {
106 : : try {
107 : 0 : bit_map0 = new byte[bit_map_size];
108 : 0 : bit_map = new byte[bit_map_size];
109 : :
110 : 0 : memcpy(bit_map0, other.bit_map0, bit_map_size);
111 : 0 : memcpy(bit_map, other.bit_map, bit_map_size);
112 : 0 : } catch (...) {
113 [ # # ][ # # ]: 0 : delete [] bit_map0;
114 [ # # ][ # # ]: 0 : delete [] bit_map;
115 : : }
116 : 0 : }
117 : :
118 : : void
119 : 10447 : FlintTable_base::swap(FlintTable_base &other)
120 : : {
121 : 10447 : std::swap(revision, other.revision);
122 : 10447 : std::swap(block_size, other.block_size);
123 : 10447 : std::swap(root, other.root);
124 : 10447 : std::swap(level, other.level);
125 : 10447 : std::swap(bit_map_size, other.bit_map_size);
126 : 10447 : std::swap(item_count, other.item_count);
127 : 10447 : std::swap(last_block, other.last_block);
128 : 10447 : std::swap(have_fakeroot, other.have_fakeroot);
129 : 10447 : std::swap(sequential, other.sequential);
130 : 10447 : std::swap(bit_map_low, other.bit_map_low);
131 : 10447 : std::swap(bit_map0, other.bit_map0);
132 : 10447 : std::swap(bit_map, other.bit_map);
133 : 10447 : }
134 : :
135 : 37830 : FlintTable_base::~FlintTable_base()
136 : : {
137 [ + + ][ # # ]: 37830 : delete [] bit_map;
138 : 37830 : bit_map = 0;
139 [ + + ][ # # ]: 37830 : delete [] bit_map0;
140 : 37830 : bit_map0 = 0;
141 : 37830 : }
142 : :
143 : : bool
144 : 207185 : FlintTable_base::do_unpack_uint(const char **start, const char *end,
145 : : uint4 *dest, string &err_msg,
146 : : const string &basename,
147 : : const char *varname)
148 : : {
149 : 207185 : bool result = F_unpack_uint(start, end, dest);
150 [ - + ]: 207185 : if (!result) {
151 : : err_msg += "Unable to read " + string(varname) + " from " +
152 : 0 : basename + "\n";
153 : : }
154 : 207185 : return result;
155 : : }
156 : :
157 : : #define DO_UNPACK_UINT_ERRCHECK(start, end, var) \
158 : : do { \
159 : : if (!do_unpack_uint(start, end, &var, err_msg, basename, #var)) { \
160 : : return false; \
161 : : } \
162 : : } while(0)
163 : :
164 : : /* How much of the base file to read at the first go (in bytes).
165 : : * This must be big enough that the base file without bitmap
166 : : * will fit in to this size with no problem. Other than that
167 : : * it's fairly arbitrary, but shouldn't be big enough to cause
168 : : * serious memory problems!
169 : : */
170 : : #define REASONABLE_BASE_SIZE 1024
171 : :
172 : : bool
173 : 21503 : FlintTable_base::read(const string & name, char ch, bool read_bitmap,
174 : : string &err_msg)
175 : : {
176 : 21503 : string basename = name + "base" + ch;
177 : : #ifdef __WIN32__
178 : : int h = msvc_posix_open(basename.c_str(), O_RDONLY | O_BINARY);
179 : : #else
180 : 21503 : int h = open(basename.c_str(), O_RDONLY | O_BINARY);
181 : : #endif
182 : :
183 [ + + ]: 21503 : if (h == -1) {
184 : 2668 : err_msg += "Couldn't open " + basename + ": " + strerror(errno) + "\n";
185 : 2668 : return false;
186 : : }
187 : 18835 : fdcloser closefd(h);
188 : :
189 : : char buf[REASONABLE_BASE_SIZE];
190 : :
191 : 18835 : const char *start = buf;
192 : 18835 : const char *end = buf + io_read(h, buf, REASONABLE_BASE_SIZE, 0);
193 : :
194 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, revision);
195 : : uint4 format;
196 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, format);
197 [ - + ]: 18835 : if (format != CURR_FORMAT) {
198 : : err_msg += "Bad base file format " + str(format) + " in " +
199 : 0 : basename + "\n";
200 : 0 : return false;
201 : : }
202 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, block_size);
203 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, root);
204 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, level);
205 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, bit_map_size);
206 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, item_count);
207 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, last_block);
208 : : uint4 have_fakeroot_;
209 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, have_fakeroot_);
210 : 18835 : have_fakeroot = have_fakeroot_;
211 : :
212 : : uint4 sequential_;
213 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, sequential_);
214 : 18835 : sequential = sequential_;
215 : :
216 [ + + ][ - + ]: 18835 : if (have_fakeroot && !sequential) {
217 : 0 : sequential = true; // FIXME : work out why we need this...
218 : : /*
219 : : err_msg += "Corrupt base file, `" + basename + "':\n"
220 : : "sequential must be set whenever have_fakeroot is set.\n" +
221 : : "sequential=" + (sequential?"true":"false") +
222 : : ", have_fakeroot=" + (have_fakeroot?"true":"false") + "\n";
223 : : return false;
224 : : */
225 : : }
226 : :
227 : : uint4 revision2;
228 [ - + ]: 18835 : DO_UNPACK_UINT_ERRCHECK(&start, end, revision2);
229 [ - + ]: 18835 : if (revision != revision2) {
230 : : err_msg += "Revision number mismatch in " +
231 : : basename + ": " +
232 : 0 : str(revision) + " vs " + str(revision2) + "\n";
233 : 0 : return false;
234 : : }
235 : :
236 : : /* It's ok to delete a zero pointer */
237 [ + + ]: 18835 : delete [] bit_map0;
238 : 18835 : bit_map0 = 0;
239 [ + + ]: 18835 : delete [] bit_map;
240 : 18835 : bit_map = 0;
241 : :
242 [ + + ]: 18835 : if (!read_bitmap)
243 : 15140 : return true;
244 : :
245 : 3695 : bit_map0 = new byte[bit_map_size];
246 : 3695 : bit_map = new byte[bit_map_size];
247 : :
248 : 3695 : size_t n = end - start;
249 [ - + ]: 3695 : if (n < bit_map_size) {
250 : 0 : memcpy(bit_map0, start, n);
251 : : (void)io_read(h, reinterpret_cast<char *>(bit_map0) + n,
252 : 0 : bit_map_size - n, bit_map_size - n);
253 : 0 : n = 0;
254 : : } else {
255 : 3695 : memcpy(bit_map0, start, bit_map_size);
256 : 3695 : n -= bit_map_size;
257 [ + - ]: 3695 : if (n) memmove(buf, start + bit_map_size, n);
258 : : }
259 : 3695 : memcpy(bit_map, bit_map0, bit_map_size);
260 : :
261 : 3695 : start = buf;
262 : 3695 : end = buf + n;
263 : 3695 : end += io_read(h, buf + n, REASONABLE_BASE_SIZE - n, 0);
264 : :
265 : : uint4 revision3;
266 [ - + ]: 3695 : if (!F_unpack_uint(&start, end, &revision3)) {
267 : : err_msg += "Couldn't read revision3 from base file " +
268 : 0 : basename + "\n";
269 : 0 : return false;
270 : : }
271 : :
272 [ - + ]: 3695 : if (revision != revision3) {
273 : : err_msg += "Revision number mismatch in " +
274 : : basename + ": " +
275 : 0 : str(revision) + " vs " + str(revision3) + "\n";
276 : 0 : return false;
277 : : }
278 : :
279 [ - + ]: 3695 : if (start != end) {
280 : 0 : err_msg += "Junk at end of base file " + basename + "\n";
281 : 0 : return false;
282 : : }
283 : :
284 : 21503 : return true;
285 : : }
286 : :
287 : : void
288 : 3526 : FlintTable_base::write_to_file(const string &filename,
289 : : char base_letter,
290 : : const string &tablename,
291 : : int changes_fd,
292 : : const string * changes_tail)
293 : : {
294 : 3526 : calculate_last_block();
295 : :
296 : 3526 : string buf;
297 : 3526 : buf += F_pack_uint(revision);
298 : 3526 : buf += F_pack_uint(CURR_FORMAT);
299 : 3526 : buf += F_pack_uint(block_size);
300 : 3526 : buf += F_pack_uint(static_cast<uint4>(root));
301 : 3526 : buf += F_pack_uint(static_cast<uint4>(level));
302 : 3526 : buf += F_pack_uint(static_cast<uint4>(bit_map_size));
303 : 3526 : buf += F_pack_uint(static_cast<uint4>(item_count));
304 : 3526 : buf += F_pack_uint(static_cast<uint4>(last_block));
305 : 3526 : buf += F_pack_uint(have_fakeroot);
306 : 3526 : buf += F_pack_uint(sequential);
307 : 3526 : buf += F_pack_uint(revision); // REVISION2
308 [ + + ]: 3526 : if (bit_map_size > 0) {
309 : 2133 : buf.append(reinterpret_cast<const char *>(bit_map), bit_map_size);
310 : : }
311 : 3526 : buf += F_pack_uint(revision); // REVISION3
312 : :
313 : : #ifdef __WIN32__
314 : : int h = msvc_posix_open(filename.c_str(), O_WRONLY | O_CREAT | O_TRUNC | O_BINARY);
315 : : #else
316 : 3526 : int h = open(filename.c_str(), O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0666);
317 : : #endif
318 [ - + ]: 3526 : if (h < 0) {
319 : : string message = string("Couldn't open base ")
320 : 0 : + filename + " to write: " + strerror(errno);
321 : 0 : throw Xapian::DatabaseOpeningError(message);
322 : : }
323 : 3526 : fdcloser closefd(h);
324 : :
325 [ + + ]: 3526 : if (changes_fd >= 0) {
326 : 50 : string changes_buf;
327 : 50 : changes_buf += F_pack_uint(1u); // Indicate the item is a base file.
328 : 50 : changes_buf += F_pack_string(tablename);
329 : 50 : changes_buf += base_letter; // The base file letter.
330 : 50 : changes_buf += F_pack_uint(buf.size());
331 : 50 : io_write(changes_fd, changes_buf.data(), changes_buf.size());
332 : 50 : io_write(changes_fd, buf.data(), buf.size());
333 [ + + ]: 50 : if (changes_tail != NULL) {
334 : 10 : io_write(changes_fd, changes_tail->data(), changes_tail->size());
335 : : // changes_tail is only specified for the final table, so sync.
336 : 10 : io_sync(changes_fd);
337 : 50 : }
338 : : }
339 : :
340 : 3526 : io_write(h, buf.data(), buf.size());
341 : 3526 : io_sync(h);
342 : 3526 : }
343 : :
344 : : /*
345 : : block_free_at_start(B, n) is true iff (if and only if) block n was free at
346 : : the start of the transaction on the B-tree.
347 : : */
348 : :
349 : : bool
350 : 55333 : FlintTable_base::block_free_at_start(uint4 n) const
351 : : {
352 : 55333 : size_t i = n / CHAR_BIT;
353 : 55333 : int bit = 0x1 << n % CHAR_BIT;
354 : 55333 : return (bit_map0[i] & bit) == 0;
355 : : }
356 : :
357 : : /* free_block(B, n) causes block n to be marked free in the bit map.
358 : : B->bit_map_low is the lowest byte in the bit map known to have a free bit
359 : : set. Searching starts from there when looking for a free block.
360 : : */
361 : :
362 : : void
363 : 2136 : FlintTable_base::free_block(uint4 n)
364 : : {
365 : 2136 : uint4 i = n / CHAR_BIT;
366 : 2136 : int bit = 0x1 << n % CHAR_BIT;
367 : 2136 : bit_map[i] &= ~ bit;
368 : :
369 [ + + ]: 2136 : if (bit_map_low > i)
370 [ + + ]: 450 : if ((bit_map0[i] & bit) == 0) /* free at start */
371 : 129 : bit_map_low = i;
372 : 2136 : }
373 : :
374 : : /* extend(B) increases the size of the two bit maps in an obvious way.
375 : : The bitmap file grows and shrinks as the DB file grows and shrinks in
376 : : internal usage. But the DB file itself does not reduce in size, no matter
377 : : how many blocks are freed.
378 : : */
379 : :
380 : : #define BIT_MAP_INC 1000
381 : : /* increase the bit map by this number of bytes if it overflows */
382 : :
383 : : void
384 : 2731 : FlintTable_base::extend_bit_map()
385 : : {
386 : 2731 : int n = bit_map_size + BIT_MAP_INC;
387 : 2731 : byte *new_bit_map0 = 0;
388 : 2731 : byte *new_bit_map = 0;
389 : :
390 : : try {
391 : 2731 : new_bit_map0 = new byte[n];
392 : 2731 : new_bit_map = new byte[n];
393 : :
394 : 2731 : memcpy(new_bit_map0, bit_map0, bit_map_size);
395 : 2731 : memset(new_bit_map0 + bit_map_size, 0, n - bit_map_size);
396 : :
397 : 2731 : memcpy(new_bit_map, bit_map, bit_map_size);
398 : 2731 : memset(new_bit_map + bit_map_size, 0, n - bit_map_size);
399 : 0 : } catch (...) {
400 [ # # ]: 0 : delete [] new_bit_map0;
401 [ # # ]: 0 : delete [] new_bit_map;
402 : 0 : throw;
403 : : }
404 [ + - ]: 2731 : delete [] bit_map0;
405 : 2731 : bit_map0 = new_bit_map0;
406 [ + - ]: 2731 : delete [] bit_map;
407 : 2731 : bit_map = new_bit_map;
408 : 2731 : bit_map_size = n;
409 : 2731 : }
410 : :
411 : : /* next_free_block(B) returns the number of the next available free block in
412 : : the bitmap, marking it as 'in use' before returning. More precisely, we get
413 : : a block that is both free now (in bit_map) and was free at the beginning of
414 : : the transaction on the B-tree (in bit_map0).
415 : :
416 : : Starting at bit_map_low we go up byte at a time until we find a byte with a
417 : : free (zero) bit, and then go up that byte bit at a time. If the bit map has
418 : : no free bits it is extended so that it will have.
419 : : */
420 : :
421 : : uint4
422 : 17120 : FlintTable_base::next_free_block()
423 : : {
424 : : uint4 i;
425 : : int x;
426 : 19398 : for (i = bit_map_low;; i++) {
427 [ + + ]: 19398 : if (i >= bit_map_size) {
428 : 2731 : extend_bit_map();
429 : : }
430 : 19398 : x = bit_map0[i] | bit_map[i];
431 [ + + ]: 19398 : if (x != UCHAR_MAX) break;
432 : : }
433 : 17120 : uint4 n = i * CHAR_BIT;
434 : 17120 : int d = 0x1;
435 [ + + ]: 64856 : while ((x & d) != 0) { d <<= 1; n++; }
436 : 17120 : bit_map[i] |= d; /* set as 'in use' */
437 : 17120 : bit_map_low = i;
438 [ + + ]: 17120 : if (n > last_block) {
439 : 13488 : last_block = n;
440 : : }
441 : 17120 : return n;
442 : : }
443 : :
444 : : bool
445 : 99 : FlintTable_base::find_changed_block(uint4 * n)
446 : : {
447 : : // Search for a block which was free at the start of the transaction, but
448 : : // isn't now.
449 [ + + ]: 124 : while ((*n) <= last_block) {
450 : 74 : size_t offset = (*n) / CHAR_BIT;
451 : 74 : int bit = 0x1 << (*n) % CHAR_BIT;
452 : :
453 [ + + ][ + - ]: 74 : if (((bit_map0[offset] & bit) == 0) && ((bit_map[offset] & bit) != 0)) {
454 : 49 : return true;
455 : : }
456 : 25 : ++(*n);
457 : : }
458 : :
459 : 99 : return false;
460 : : }
461 : :
462 : : bool
463 : 4 : FlintTable_base::block_free_now(uint4 n)
464 : : {
465 : 4 : uint4 i = n / CHAR_BIT;
466 : 4 : int bit = 0x1 << n % CHAR_BIT;
467 : 4 : return (bit_map[i] & bit) == 0;
468 : : }
469 : :
470 : : void
471 : 3576 : FlintTable_base::calculate_last_block()
472 : : {
473 [ + + ]: 3576 : if (bit_map_size == 0) {
474 : 1393 : last_block = 0;
475 : 1393 : return;
476 : : }
477 : 2183 : int i = bit_map_size - 1;
478 [ + + ][ + + ]: 1365367 : while (bit_map[i] == 0 && i > 0) {
[ + + ]
479 : 1363184 : i--;
480 : : }
481 : 2183 : bit_map_size = i + 1;
482 : :
483 : 2183 : int x = bit_map[i];
484 : :
485 : : /* Check for when there are no blocks */
486 [ + + ]: 2183 : if (x == 0) {
487 : 102 : last_block = 0;
488 : 102 : return;
489 : : }
490 : 2081 : uint4 n = (i + 1) * CHAR_BIT - 1;
491 : 2081 : int d = 0x1 << (CHAR_BIT - 1);
492 [ + + ]: 14838 : while ((x & d) == 0) { d >>= 1; n--; }
493 : :
494 : 3576 : last_block = n;
495 : : }
496 : :
497 : : bool
498 : 4 : FlintTable_base::is_empty() const
499 : : {
500 [ + + ]: 11 : for (uint4 i = 0; i < bit_map_size; i++) {
501 [ - + ]: 7 : if (bit_map[i] != 0) {
502 : 0 : return false;
503 : : }
504 : : }
505 : 4 : return true;
506 : : }
507 : :
508 : : void
509 : 102 : FlintTable_base::clear_bit_map()
510 : : {
511 : 102 : memset(bit_map, 0, bit_map_size);
512 : 102 : }
513 : :
514 : : // We've commited, so "bitmap at start" needs to be reset to the current bitmap.
515 : : void
516 : 2133 : FlintTable_base::commit()
517 : : {
518 : 2133 : memcpy(bit_map0, bit_map, bit_map_size);
519 : 2133 : bit_map_low = 0;
520 : 2133 : }
|
