Branch data Line data Source code
1 : : /* chert_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 : : * 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 <xapian/error.h>
31 : :
32 : : #include "chert_btreebase.h"
33 : : #include "io_utils.h"
34 : : #include "omassert.h"
35 : : #include "pack.h"
36 : : #include "str.h"
37 : : #include "utils.h"
38 : :
39 : : #include <algorithm>
40 : : #include <climits>
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 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 : 33339 : ChertTable_base::ChertTable_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 : 33339 : bit_map(0)
89 : : {
90 : 33339 : }
91 : :
92 : 0 : ChertTable_base::ChertTable_base(const ChertTable_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 : 9113 : ChertTable_base::swap(ChertTable_base &other)
120 : : {
121 : 9113 : std::swap(revision, other.revision);
122 : 9113 : std::swap(block_size, other.block_size);
123 : 9113 : std::swap(root, other.root);
124 : 9113 : std::swap(level, other.level);
125 : 9113 : std::swap(bit_map_size, other.bit_map_size);
126 : 9113 : std::swap(item_count, other.item_count);
127 : 9113 : std::swap(last_block, other.last_block);
128 : 9113 : std::swap(have_fakeroot, other.have_fakeroot);
129 : 9113 : std::swap(sequential, other.sequential);
130 : 9113 : std::swap(bit_map_low, other.bit_map_low);
131 : 9113 : std::swap(bit_map0, other.bit_map0);
132 : 9113 : std::swap(bit_map, other.bit_map);
133 : 9113 : }
134 : :
135 : 33339 : ChertTable_base::~ChertTable_base()
136 : : {
137 [ + + ][ # # ]: 33339 : delete [] bit_map;
138 : 33339 : bit_map = 0;
139 [ + + ][ # # ]: 33339 : delete [] bit_map0;
140 : 33339 : bit_map0 = 0;
141 : 33339 : }
142 : :
143 : : /** Do most of the error handling from unpack_uint() */
144 : : static bool
145 : 161740 : do_unpack_uint(const char **start, const char *end,
146 : : uint4 *dest, string &err_msg,
147 : : const string &basename,
148 : : const char *varname)
149 : : {
150 : 161740 : bool result = unpack_uint(start, end, dest);
151 [ - + ]: 161740 : if (rare(!result)) {
152 : 0 : err_msg += "Unable to read ";
153 : 0 : err_msg += varname;
154 : 0 : err_msg += " from ";
155 : 0 : err_msg += basename;
156 : 0 : err_msg += '\n';
157 : : }
158 : 161740 : return result;
159 : : }
160 : :
161 : : static bool
162 : 16174 : do_unpack_uint(const char **start, const char *end,
163 : : chert_tablesize_t *dest, string &err_msg,
164 : : const string &basename,
165 : : const char *varname)
166 : : {
167 : 16174 : bool result = unpack_uint(start, end, dest);
168 [ - + ]: 16174 : if (rare(!result)) {
169 : 0 : err_msg += "Unable to read ";
170 : 0 : err_msg += varname;
171 : 0 : err_msg += " from ";
172 : 0 : err_msg += basename;
173 : 0 : err_msg += '\n';
174 : : }
175 : 16174 : return result;
176 : : }
177 : :
178 : : #define DO_UNPACK_UINT_ERRCHECK(start, end, var) \
179 : : do { \
180 : : if (!do_unpack_uint(start, end, &var, err_msg, basename, #var)) { \
181 : : return false; \
182 : : } \
183 : : } while(0)
184 : :
185 : : /* How much of the base file to read at the first go (in bytes).
186 : : * This must be big enough that the base file without bitmap
187 : : * will fit in to this size with no problem. Other than that
188 : : * it's fairly arbitrary, but shouldn't be big enough to cause
189 : : * serious memory problems!
190 : : */
191 : : #define REASONABLE_BASE_SIZE 1024
192 : :
193 : : bool
194 : 18695 : ChertTable_base::read(const string & name, char ch, bool read_bitmap,
195 : : string &err_msg)
196 : : {
197 : 18695 : string basename = name + "base" + ch;
198 : : #ifdef __WIN32__
199 : : int h = msvc_posix_open(basename.c_str(), O_RDONLY | O_BINARY);
200 : : #else
201 : 18695 : int h = open(basename.c_str(), O_RDONLY | O_BINARY);
202 : : #endif
203 : :
204 [ + + ]: 18695 : if (h == -1) {
205 : 2521 : err_msg += "Couldn't open " + basename + ": " + strerror(errno) + "\n";
206 : 2521 : return false;
207 : : }
208 : 16174 : fdcloser closefd(h);
209 : :
210 : : char buf[REASONABLE_BASE_SIZE];
211 : :
212 : 16174 : const char *start = buf;
213 : 16174 : const char *end = buf + io_read(h, buf, REASONABLE_BASE_SIZE, 0);
214 : :
215 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, revision);
216 : : uint4 format;
217 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, format);
218 [ - + ]: 16174 : if (format != CURR_FORMAT) {
219 : : err_msg += "Bad base file format " + str(format) + " in " +
220 : 0 : basename + "\n";
221 : 0 : return false;
222 : : }
223 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, block_size);
224 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, root);
225 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, level);
226 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, bit_map_size);
227 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, item_count);
228 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, last_block);
229 : : uint4 have_fakeroot_;
230 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, have_fakeroot_);
231 : 16174 : have_fakeroot = have_fakeroot_;
232 : :
233 : : uint4 sequential_;
234 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, sequential_);
235 : 16174 : sequential = sequential_;
236 : :
237 [ + + ][ - + ]: 16174 : if (have_fakeroot && !sequential) {
238 : 0 : sequential = true; // FIXME : work out why we need this...
239 : : /*
240 : : err_msg += "Corrupt base file, `" + basename + "':\n"
241 : : "sequential must be set whenever have_fakeroot is set.\n" +
242 : : "sequential=" + (sequential?"true":"false") +
243 : : ", have_fakeroot=" + (have_fakeroot?"true":"false") + "\n";
244 : : return false;
245 : : */
246 : : }
247 : :
248 : : uint4 revision2;
249 [ - + ]: 16174 : DO_UNPACK_UINT_ERRCHECK(&start, end, revision2);
250 [ - + ]: 16174 : if (revision != revision2) {
251 : : err_msg += "Revision number mismatch in " +
252 : : basename + ": " +
253 : 0 : str(revision) + " vs " + str(revision2) + "\n";
254 : 0 : return false;
255 : : }
256 : :
257 : : /* It's ok to delete a zero pointer */
258 [ + + ]: 16174 : delete [] bit_map0;
259 : 16174 : bit_map0 = 0;
260 [ + + ]: 16174 : delete [] bit_map;
261 : 16174 : bit_map = 0;
262 : :
263 [ + + ]: 16174 : if (!read_bitmap)
264 : 12978 : return true;
265 : :
266 : 3196 : bit_map0 = new byte[bit_map_size];
267 : 3196 : bit_map = new byte[bit_map_size];
268 : :
269 : 3196 : size_t n = end - start;
270 [ - + ]: 3196 : if (n < bit_map_size) {
271 : 0 : memcpy(bit_map0, start, n);
272 : : (void)io_read(h, reinterpret_cast<char *>(bit_map0) + n,
273 : 0 : bit_map_size - n, bit_map_size - n);
274 : 0 : n = 0;
275 : : } else {
276 : 3196 : memcpy(bit_map0, start, bit_map_size);
277 : 3196 : n -= bit_map_size;
278 [ + - ]: 3196 : if (n) memmove(buf, start + bit_map_size, n);
279 : : }
280 : 3196 : memcpy(bit_map, bit_map0, bit_map_size);
281 : :
282 : 3196 : start = buf;
283 : 3196 : end = buf + n;
284 : 3196 : end += io_read(h, buf + n, REASONABLE_BASE_SIZE - n, 0);
285 : :
286 : : uint4 revision3;
287 [ - + ]: 3196 : if (!unpack_uint(&start, end, &revision3)) {
288 : : err_msg += "Couldn't read revision3 from base file " +
289 : 0 : basename + "\n";
290 : 0 : return false;
291 : : }
292 : :
293 [ - + ]: 3196 : if (revision != revision3) {
294 : : err_msg += "Revision number mismatch in " +
295 : : basename + ": " +
296 : 0 : str(revision) + " vs " + str(revision3) + "\n";
297 : 0 : return false;
298 : : }
299 : :
300 [ - + ]: 3196 : if (start != end) {
301 : 0 : err_msg += "Junk at end of base file " + basename + "\n";
302 : 0 : return false;
303 : : }
304 : :
305 : 18695 : return true;
306 : : }
307 : :
308 : : void
309 : 3016 : ChertTable_base::write_to_file(const string &filename,
310 : : char base_letter,
311 : : const string &tablename,
312 : : int changes_fd,
313 : : const string * changes_tail)
314 : : {
315 : 3016 : calculate_last_block();
316 : :
317 : 3016 : string buf;
318 : 3016 : pack_uint(buf, revision);
319 : 3016 : pack_uint(buf, CURR_FORMAT);
320 : 3016 : pack_uint(buf, block_size);
321 : 3016 : pack_uint(buf, static_cast<uint4>(root));
322 : 3016 : pack_uint(buf, static_cast<uint4>(level));
323 : 3016 : pack_uint(buf, static_cast<uint4>(bit_map_size));
324 : 3016 : pack_uint(buf, item_count);
325 : 3016 : pack_uint(buf, static_cast<uint4>(last_block));
326 : 3016 : pack_uint(buf, have_fakeroot);
327 : 3016 : pack_uint(buf, sequential);
328 : 3016 : pack_uint(buf, revision); // REVISION2
329 [ + + ]: 3016 : if (bit_map_size > 0) {
330 : 1792 : buf.append(reinterpret_cast<const char *>(bit_map), bit_map_size);
331 : : }
332 : 3016 : pack_uint(buf, revision); // REVISION3
333 : :
334 : : #ifdef __WIN32__
335 : : int h = msvc_posix_open(filename.c_str(), O_WRONLY | O_CREAT | O_TRUNC | O_BINARY);
336 : : #else
337 : 3016 : int h = open(filename.c_str(), O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0666);
338 : : #endif
339 [ - + ]: 3016 : if (h < 0) {
340 : : string message = string("Couldn't open base ")
341 : 0 : + filename + " to write: " + strerror(errno);
342 : 0 : throw Xapian::DatabaseOpeningError(message);
343 : : }
344 : 3016 : fdcloser closefd(h);
345 : :
346 [ + + ]: 3016 : if (changes_fd >= 0) {
347 : 86 : string changes_buf;
348 : 86 : pack_uint(changes_buf, 1u); // Indicate the item is a base file.
349 : 86 : pack_string(changes_buf, tablename);
350 : 86 : changes_buf += base_letter; // The base file letter.
351 : 86 : pack_uint(changes_buf, buf.size());
352 : 86 : io_write(changes_fd, changes_buf.data(), changes_buf.size());
353 : 86 : io_write(changes_fd, buf.data(), buf.size());
354 [ + + ]: 86 : if (changes_tail != NULL) {
355 : 23 : io_write(changes_fd, changes_tail->data(), changes_tail->size());
356 : : // changes_tail is only specified for the final table, so sync.
357 : 23 : io_sync(changes_fd);
358 : 86 : }
359 : : }
360 : :
361 : 3016 : io_write(h, buf.data(), buf.size());
362 : 3016 : io_sync(h);
363 : 3016 : }
364 : :
365 : : /*
366 : : block_free_at_start(B, n) is true iff (if and only if) block n was free at
367 : : the start of the transaction on the B-tree.
368 : : */
369 : :
370 : : bool
371 : 303981 : ChertTable_base::block_free_at_start(uint4 n) const
372 : : {
373 : 303981 : size_t i = n / CHAR_BIT;
374 : 303981 : int bit = 0x1 << n % CHAR_BIT;
375 : 303981 : return (bit_map0[i] & bit) == 0;
376 : : }
377 : :
378 : : /* free_block(B, n) causes block n to be marked free in the bit map.
379 : : B->bit_map_low is the lowest byte in the bit map known to have a free bit
380 : : set. Searching starts from there when looking for a free block.
381 : : */
382 : :
383 : : void
384 : 1927 : ChertTable_base::free_block(uint4 n)
385 : : {
386 : 1927 : uint4 i = n / CHAR_BIT;
387 : 1927 : int bit = 0x1 << n % CHAR_BIT;
388 : 1927 : bit_map[i] &= ~ bit;
389 : :
390 [ + + ]: 1927 : if (bit_map_low > i)
391 [ + + ]: 494 : if ((bit_map0[i] & bit) == 0) /* free at start */
392 : 106 : bit_map_low = i;
393 : 1927 : }
394 : :
395 : : /* extend(B) increases the size of the two bit maps in an obvious way.
396 : : The bitmap file grows and shrinks as the DB file grows and shrinks in
397 : : internal usage. But the DB file itself does not reduce in size, no matter
398 : : how many blocks are freed.
399 : : */
400 : :
401 : : #define BIT_MAP_INC 1000
402 : : /* increase the bit map by this number of bytes if it overflows */
403 : :
404 : : void
405 : 2432 : ChertTable_base::extend_bit_map()
406 : : {
407 : 2432 : int n = bit_map_size + BIT_MAP_INC;
408 : 2432 : byte *new_bit_map0 = 0;
409 : 2432 : byte *new_bit_map = 0;
410 : :
411 : : try {
412 : 2432 : new_bit_map0 = new byte[n];
413 : 2432 : new_bit_map = new byte[n];
414 : :
415 : 2432 : memcpy(new_bit_map0, bit_map0, bit_map_size);
416 : 2432 : memset(new_bit_map0 + bit_map_size, 0, n - bit_map_size);
417 : :
418 : 2432 : memcpy(new_bit_map, bit_map, bit_map_size);
419 : 2432 : memset(new_bit_map + bit_map_size, 0, n - bit_map_size);
420 : 0 : } catch (...) {
421 [ # # ]: 0 : delete [] new_bit_map0;
422 [ # # ]: 0 : delete [] new_bit_map;
423 : 0 : throw;
424 : : }
425 [ + - ]: 2432 : delete [] bit_map0;
426 : 2432 : bit_map0 = new_bit_map0;
427 [ + - ]: 2432 : delete [] bit_map;
428 : 2432 : bit_map = new_bit_map;
429 : 2432 : bit_map_size = n;
430 : 2432 : }
431 : :
432 : : /* next_free_block(B) returns the number of the next available free block in
433 : : the bitmap, marking it as 'in use' before returning. More precisely, we get
434 : : a block that is both free now (in bit_map) and was free at the beginning of
435 : : the transaction on the B-tree (in bit_map0).
436 : :
437 : : Starting at bit_map_low we go up byte at a time until we find a byte with a
438 : : free (zero) bit, and then go up that byte bit at a time. If the bit map has
439 : : no free bits it is extended so that it will have.
440 : : */
441 : :
442 : : uint4
443 : 20938 : ChertTable_base::next_free_block()
444 : : {
445 : : uint4 i;
446 : : int x;
447 : 23612 : for (i = bit_map_low;; i++) {
448 [ + + ]: 23612 : if (i >= bit_map_size) {
449 : 2432 : extend_bit_map();
450 : : }
451 : 23612 : x = bit_map0[i] | bit_map[i];
452 [ + + ]: 23612 : if (x != UCHAR_MAX) break;
453 : : }
454 : 20938 : uint4 n = i * CHAR_BIT;
455 : 20938 : int d = 0x1;
456 [ + + ]: 83728 : while ((x & d) != 0) { d <<= 1; n++; }
457 : 20938 : bit_map[i] |= d; /* set as 'in use' */
458 : 20938 : bit_map_low = i;
459 [ + + ]: 20938 : if (n > last_block) {
460 : 17638 : last_block = n;
461 : : }
462 : 20938 : return n;
463 : : }
464 : :
465 : : bool
466 : 161 : ChertTable_base::find_changed_block(uint4 * n)
467 : : {
468 : : // Search for a block which was free at the start of the transaction, but
469 : : // isn't now.
470 [ + + ]: 246 : while ((*n) <= last_block) {
471 : 160 : size_t offset = (*n) / CHAR_BIT;
472 : 160 : int bit = 0x1 << (*n) % CHAR_BIT;
473 : :
474 [ + + ][ + + ]: 160 : if (((bit_map0[offset] & bit) == 0) && ((bit_map[offset] & bit) != 0)) {
475 : 75 : return true;
476 : : }
477 : 85 : ++(*n);
478 : : }
479 : :
480 : 161 : return false;
481 : : }
482 : :
483 : : bool
484 : 3 : ChertTable_base::block_free_now(uint4 n)
485 : : {
486 : 3 : uint4 i = n / CHAR_BIT;
487 : 3 : int bit = 0x1 << n % CHAR_BIT;
488 : 3 : return (bit_map[i] & bit) == 0;
489 : : }
490 : :
491 : : void
492 : 3102 : ChertTable_base::calculate_last_block()
493 : : {
494 [ + + ]: 3102 : if (bit_map_size == 0) {
495 : 1224 : last_block = 0;
496 : 1224 : return;
497 : : }
498 : 1878 : int i = bit_map_size - 1;
499 [ + + ][ + + ]: 1161720 : while (bit_map[i] == 0 && i > 0) {
[ + + ]
500 : 1159842 : i--;
501 : : }
502 : 1878 : bit_map_size = i + 1;
503 : :
504 : 1878 : int x = bit_map[i];
505 : :
506 : : /* Check for when there are no blocks */
507 [ + + ]: 1878 : if (x == 0) {
508 : 135 : last_block = 0;
509 : 135 : return;
510 : : }
511 : 1743 : uint4 n = (i + 1) * CHAR_BIT - 1;
512 : 1743 : int d = 0x1 << (CHAR_BIT - 1);
513 [ + + ]: 12344 : while ((x & d) == 0) { d >>= 1; n--; }
514 : :
515 : 3102 : last_block = n;
516 : : }
517 : :
518 : : bool
519 : 3 : ChertTable_base::is_empty() const
520 : : {
521 [ + + ]: 9 : for (uint4 i = 0; i < bit_map_size; i++) {
522 [ - + ]: 6 : if (bit_map[i] != 0) {
523 : 0 : return false;
524 : : }
525 : : }
526 : 3 : return true;
527 : : }
528 : :
529 : : void
530 : 135 : ChertTable_base::clear_bit_map()
531 : : {
532 : 135 : memset(bit_map, 0, bit_map_size);
533 : 135 : }
534 : :
535 : : // We've commited, so "bitmap at start" needs to be reset to the current bitmap.
536 : : void
537 : 1792 : ChertTable_base::commit()
538 : : {
539 : 1792 : memcpy(bit_map0, bit_map, bit_map_size);
540 : 1792 : bit_map_low = 0;
541 : 1792 : }
|
