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