1 /* glass_check.cc: Btree checking
3 * Copyright 1999,2000,2001 BrightStation PLC
4 * Copyright 2002 Ananova Ltd
5 * Copyright 2002,2004,2005,2008,2009,2011,2012,2013,2014,2016 Olly Betts
6 * Copyright 2008 Lemur Consulting Ltd
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License as
10 * published by the Free Software Foundation; either version 2 of the
11 * License, or (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
26 #include "glass_check.h"
27 #include "glass_version.h"
28 #include "unicode/description_append.h"
29 #include "xapian/constants.h"
36 using namespace Glass
;
39 void GlassTableCheck::print_spaces(int n
) const
41 while (n
--) out
->put(' ');
44 void GlassTableCheck::print_bytes(int n
, const byte
* p
) const
46 out
->write(reinterpret_cast<const char *>(p
), n
);
49 void GlassTableCheck::print_key(const byte
* p
, int c
, int j
) const
54 if (item
.key().length() >= 0)
55 item
.key().read(&key
);
57 description_append(escaped
, key
);
59 int x
= item
.component_of();
61 if (item
.last_component()) {
67 if (item
.key().length() >= 0)
68 item
.key().read(&key
);
70 description_append(escaped
, key
);
75 void GlassTableCheck::print_tag(const byte
* p
, int c
, int j
) const
80 item
.append_chunk(&tag
);
82 description_append(escaped
, tag
);
83 *out
<< ' ' << escaped
;
86 *out
<< "--> [" << item
.block_given_by() << ']';
90 void GlassTableCheck::report_block_full(int m
, int n
, const byte
* p
) const
93 int dir_end
= DIR_END(p
);
96 *out
<< "Block [" << n
<< "] level " << j
<< ", revision *" << REVISION(p
)
97 << " items (" << (dir_end
- DIR_START
) / D2
<< ") usage "
98 << block_usage(p
) << "%:\n";
99 for (int c
= DIR_START
; c
< dir_end
; c
+= D2
) {
108 int GlassTableCheck::block_usage(const byte
* p
) const
110 int space
= block_size
- DIR_END(p
);
111 int free
= TOTAL_FREE(p
);
112 return (space
- free
) * 100 / space
; /* a percentage */
115 /** GlassTableCheck::report_block(m, n, p) prints the block at p, block number n,
116 * indented by m spaces.
118 void GlassTableCheck::report_block(int m
, int n
, const byte
* p
) const
120 int j
= GET_LEVEL(p
);
121 int dir_end
= DIR_END(p
);
124 *out
<< "[" << n
<< "] *" << REVISION(p
) << " ("
125 << (dir_end
- DIR_START
) / D2
<< ") " << block_usage(p
) << "% ";
127 for (c
= DIR_START
; c
< dir_end
; c
+= D2
) {
128 if (c
>= DIR_START
+ 6 && c
< dir_end
- 6) {
129 if (c
== DIR_START
+ 6) *out
<< "... ";
139 XAPIAN_NORETURN(static void failure(const char *msg
, uint4 n
, int c
= 0));
141 failure(const char *msg
, uint4 n
, int c
)
147 e
+= str((c
- DIR_START
) / D2
);
151 throw Xapian::DatabaseError(e
);
155 GlassTableCheck::block_check(Glass::Cursor
* C_
, int j
, int opts
,
156 GlassFreeListChecker
& flcheck
)
158 const byte
* p
= C_
[j
].get_p();
159 uint4 n
= C_
[j
].get_n();
161 int significant_c
= j
== 0 ? DIR_START
: DIR_START
+ D2
;
162 /* the first key in an index block is dummy, remember */
164 size_t max_free
= MAX_FREE(p
);
165 int dir_end
= DIR_END(p
);
166 int total_free
= block_size
- dir_end
;
168 if (!flcheck
.mark_used(n
))
169 failure("used more than once in the Btree", n
);
171 if (j
!= GET_LEVEL(p
))
172 failure("wrong level", n
);
173 // dir_end must be > DIR_START, fit within the block, and be odd.
174 if (dir_end
<= DIR_START
|| dir_end
> int(block_size
) || (dir_end
& 1) != 1)
175 failure("directory end pointer invalid", n
);
177 if (opts
& Xapian::DBCHECK_SHORT_TREE
)
178 report_block(3*(level
- j
), n
, p
);
180 if (opts
& Xapian::DBCHECK_FULL_TREE
)
181 report_block_full(3*(level
- j
), n
, p
);
184 for (c
= DIR_START
; c
< dir_end
; c
+= D2
) {
186 int o
= item
.get_address() - p
;
187 if (o
> int(block_size
))
188 failure("item starts outside block", n
, c
);
189 if (o
- dir_end
< int(max_free
))
190 failure("item overlaps directory", n
, c
);
192 int kt_len
= item
.size();
193 if (o
+ kt_len
> int(block_size
))
194 failure("item ends outside block", n
, c
);
195 total_free
-= kt_len
;
197 if (c
> significant_c
&& compare(LeafItem(p
, c
- D2
), item
) >= 0)
198 failure("not in sorted order", n
, c
);
201 for (c
= DIR_START
; c
< dir_end
; c
+= D2
) {
203 int o
= item
.get_address() - p
;
204 if (o
> int(block_size
))
205 failure("item starts outside block", n
, c
);
206 if (o
- dir_end
< int(max_free
))
207 failure("item overlaps directory", n
, c
);
209 int kt_len
= item
.size();
210 if (o
+ kt_len
> int(block_size
))
211 failure("item ends outside block", n
, c
);
212 total_free
-= kt_len
;
214 if (c
> significant_c
&& compare(BItem(p
, c
- D2
), item
) >= 0)
215 failure("not in sorted order", n
, c
);
218 if (total_free
!= TOTAL_FREE(p
))
219 failure("stored total free space value wrong", n
);
222 for (c
= DIR_START
; c
< dir_end
; c
+= D2
) {
224 block_to_cursor(C_
, j
- 1, BItem(p
, c
).block_given_by());
226 block_check(C_
, j
- 1, opts
, flcheck
);
228 const byte
* q
= C_
[j
- 1].get_p();
229 /* if j == 1, and c > DIR_START, the first key of level j - 1 must be
230 * >= the key of p, c: */
232 if (j
== 1 && c
> DIR_START
)
233 if (compare(LeafItem(q
, DIR_START
), BItem(p
, c
)) < 0)
234 failure("leaf key < left dividing key in level above", n
, c
);
236 /* if j > 1, and c > DIR_START, the second key of level j - 1 must be
237 * >= the key of p, c: */
239 if (j
> 1 && c
> DIR_START
&& DIR_END(q
) > DIR_START
+ D2
&&
240 compare(BItem(q
, DIR_START
+ D2
), BItem(p
, c
)) < 0)
241 failure("key < left dividing key in level above", n
, c
);
243 /* the last key of level j - 1 must be < the key of p, c + D2, if c +
246 if (c
+ D2
< dir_end
) {
248 if (compare(LeafItem(q
, DIR_END(q
) - D2
), BItem(p
, c
+ D2
)) >= 0)
249 failure("leaf key >= right dividing key in level above", n
, c
);
250 } else if (DIR_START
+ D2
< DIR_END(q
)) {
251 if (compare(BItem(q
, DIR_END(q
) - D2
), BItem(p
, c
+ D2
)) >= 0)
252 failure("key >= right dividing key in level above", n
, c
);
256 if (REVISION(q
) > REVISION(p
))
257 failure("block has greater revision than parent", n
);
262 GlassTableCheck::check(const char * tablename
, const string
& path
, int fd
,
264 const GlassVersion
& version_file
, int opts
,
267 string
filename(path
);
269 filename
+= tablename
;
272 AutoPtr
<GlassTableCheck
> B(
274 new GlassTableCheck(tablename
, filename
, false, out
) :
275 new GlassTableCheck(tablename
, fd
, offset_
, false, out
));
277 Glass::table_type tab_type
;
278 if (strcmp(tablename
, "postlist") == 0) {
279 tab_type
= Glass::POSTLIST
;
280 } else if (strcmp(tablename
, "docdata") == 0) {
281 tab_type
= Glass::DOCDATA
;
282 } else if (strcmp(tablename
, "termlist") == 0) {
283 tab_type
= Glass::TERMLIST
;
284 } else if (strcmp(tablename
, "position") == 0) {
285 tab_type
= Glass::POSITION
;
286 } else if (strcmp(tablename
, "spelling") == 0) {
287 tab_type
= Glass::SPELLING
;
288 } else if (strcmp(tablename
, "synonym") == 0) {
289 tab_type
= Glass::SYNONYM
;
291 string e
= "Unknown table: ";
293 throw Xapian::DatabaseError(e
);
296 B
->open(0, version_file
.get_root(tab_type
), version_file
.get_revision());
297 Glass::Cursor
* C
= B
->C
;
299 if (opts
& Xapian::DBCHECK_SHOW_STATS
) {
300 *out
<< "blocksize=" << B
->block_size
/ 1024 << "K"
301 " items=" << B
->item_count
302 << " firstunused=" << B
->free_list
.get_first_unused_block()
303 << " revision=" << B
->revision_number
304 << " levels=" << B
->level
306 if (B
->faked_root_block
)
309 *out
<< C
[B
->level
].get_n();
313 if (B
->faked_root_block
) {
317 // We walk the Btree marking off the blocks which it uses, then walk
318 // the free list, marking the blocks which aren't used. Any blocks not
319 // marked have been leaked.
320 GlassFreeListChecker
flcheck(B
->free_list
);
321 GlassFreeListChecker
flcheck2(B
->free_list
);
322 B
->block_check(C
, B
->level
, opts
, flcheck
);
324 if (opts
& Xapian::DBCHECK_SHOW_FREELIST
) {
326 if (B
->free_list
.empty())
329 while (!B
->free_list
.empty()) {
330 uint4 n
= B
->free_list
.walk(B
.get(), B
->block_size
, true);
331 if (opts
& Xapian::DBCHECK_SHOW_FREELIST
)
333 if (!flcheck2
.mark_used(n
)) {
334 if (opts
& Xapian::DBCHECK_SHOW_FREELIST
)
336 failure("Same block is in freelist more than once", n
);
338 if (!flcheck
.mark_used(n
)) {
339 if (opts
& Xapian::DBCHECK_SHOW_FREELIST
)
341 failure("Used block also in freelist", n
);
344 if (opts
& Xapian::DBCHECK_SHOW_FREELIST
)
348 uint4 count
= flcheck
.count_set_bits(&first_bad
);
349 // Skip this check for a single file DB for now. FIXME
350 if (count
&& fd
< 0) {
351 string e
= str(count
);
352 e
+= " unused block(s) missing from the free list, first is ";
354 throw Xapian::DatabaseError(e
);
357 if (opts
) *out
<< "B-tree checked okay" << endl
;
361 void GlassTableCheck::report_cursor(int N
, const Glass::Cursor
* C_
) const
364 for (int i
= 0; i
<= level
; i
++)
365 *out
<< "p=" << C_
[i
].get_p() << ", "
366 "c=" << C_
[i
].c
<< ", "
367 "n=[" << C_
[i
].get_n() << "], "
368 "rewrite=" << C_
[i
].rewrite
<< endl
;