xapian-core  1.4.21
glass_check.cc
Go to the documentation of this file.
1 
4 /* Copyright 1999,2000,2001 BrightStation PLC
5  * Copyright 2002 Ananova Ltd
6  * Copyright 2002,2004,2005,2008,2009,2011,2012,2013,2014,2016 Olly Betts
7  * Copyright 2008 Lemur Consulting Ltd
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License as
11  * published by the Free Software Foundation; either version 2 of the
12  * License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
22  * USA
23  */
24 
25 #include <config.h>
26 
27 #include "glass_check.h"
28 #include "glass_version.h"
30 #include "xapian/constants.h"
31 
32 #include "autoptr.h"
33 #include <climits>
34 #include <cstring>
35 #include <ostream>
36 
37 using namespace Glass;
38 using namespace std;
39 
41 {
42  while (n--) out->put(' ');
43 }
44 
45 void GlassTableCheck::print_bytes(int n, const uint8_t * p) const
46 {
47  out->write(reinterpret_cast<const char *>(p), n);
48 }
49 
50 void GlassTableCheck::print_key(const uint8_t * p, int c, int j) const
51 {
52  if (j == 0) {
53  LeafItem item(p, c);
54  string key;
55  if (item.key().length() >= 0)
56  item.key().read(&key);
57  string escaped;
58  description_append(escaped, key);
59  *out << escaped;
60  int x = item.component_of();
61  *out << ' ' << x;
62  if (item.last_component()) {
63  *out << '/' << x;
64  }
65  } else {
66  BItem item(p, c);
67  string key;
68  if (item.key().length() >= 0)
69  item.key().read(&key);
70  string escaped;
71  description_append(escaped, key);
72  *out << escaped;
73  }
74 }
75 
76 void GlassTableCheck::print_tag(const uint8_t * p, int c, int j) const
77 {
78  if (j == 0) {
79  LeafItem item(p, c);
80  string tag;
81  item.append_chunk(&tag);
82  string escaped;
83  description_append(escaped, tag);
84  *out << ' ' << escaped;
85  } else {
86  BItem item(p, c);
87  *out << "--> [" << item.block_given_by() << ']';
88  }
89 }
90 
91 void GlassTableCheck::report_block_full(int m, int n, const uint8_t * p) const
92 {
93  int j = GET_LEVEL(p);
94  int dir_end = DIR_END(p);
95  *out << '\n';
96  print_spaces(m);
97  *out << "Block [" << n << "] level " << j << ", revision *" << REVISION(p)
98  << " items (" << (dir_end - DIR_START) / D2 << ") usage "
99  << block_usage(p) << "%:\n";
100  for (int c = DIR_START; c < dir_end; c += D2) {
101  print_spaces(m);
102  print_key(p, c, j);
103  *out << ' ';
104  print_tag(p, c, j);
105  *out << '\n';
106  }
107 }
108 
109 int GlassTableCheck::block_usage(const uint8_t * p) const
110 {
111  int space = block_size - DIR_END(p);
112  int free = TOTAL_FREE(p);
113  return (space - free) * 100 / space; /* a percentage */
114 }
115 
119 void GlassTableCheck::report_block(int m, int n, const uint8_t * p) const
120 {
121  int j = GET_LEVEL(p);
122  int dir_end = DIR_END(p);
123  int c;
124  print_spaces(m);
125  *out << "[" << n << "] *" << REVISION(p) << " ("
126  << (dir_end - DIR_START) / D2 << ") " << block_usage(p) << "% ";
127 
128  for (c = DIR_START; c < dir_end; c += D2) {
129  if (c >= DIR_START + 6 && c < dir_end - 6) {
130  if (c == DIR_START + 6) *out << "... ";
131  continue;
132  }
133 
134  print_key(p, c, j);
135  *out << ' ';
136  }
137  *out << endl;
138 }
139 
140 XAPIAN_NORETURN(static void failure(const char *msg, uint4 n, int c = 0));
141 static void
142 failure(const char *msg, uint4 n, int c)
143 {
144  string e = "Block ";
145  e += str(n);
146  if (c) {
147  e += " item ";
148  e += str((c - DIR_START) / D2);
149  }
150  e += ": ";
151  e += msg;
152  throw Xapian::DatabaseError(e);
153 }
154 
155 void
157  GlassFreeListChecker & flcheck)
158 {
159  const uint8_t * p = C_[j].get_p();
160  uint4 n = C_[j].get_n();
161  int c;
162  int significant_c = j == 0 ? DIR_START : DIR_START + D2;
163  /* the first key in an index block is dummy, remember */
164 
165  size_t max_free = MAX_FREE(p);
166  int dir_end = DIR_END(p);
167  int total_free = block_size - dir_end;
168 
169  if (!flcheck.mark_used(n))
170  failure("used more than once in the Btree", n);
171 
172  if (j != GET_LEVEL(p))
173  failure("wrong level", n);
174  // dir_end must be > DIR_START, fit within the block, and be odd.
175  if (dir_end <= DIR_START || dir_end > int(block_size) || (dir_end & 1) != 1)
176  failure("directory end pointer invalid", n);
177 
178  if (opts & Xapian::DBCHECK_SHORT_TREE)
179  report_block(3 * (level - j), n, p);
180 
181  if (opts & Xapian::DBCHECK_FULL_TREE)
182  report_block_full(3 * (level - j), n, p);
183 
184  if (j == 0) {
185  for (c = DIR_START; c < dir_end; c += D2) {
186  LeafItem item(p, c);
187  int o = item.get_address() - p;
188  if (o > int(block_size))
189  failure("item starts outside block", n, c);
190  if (o - dir_end < int(max_free))
191  failure("item overlaps directory", n, c);
192 
193  int kt_len = item.size();
194  if (o + kt_len > int(block_size))
195  failure("item ends outside block", n, c);
196  total_free -= kt_len;
197 
198  if (c > significant_c && compare(LeafItem(p, c - D2), item) >= 0)
199  failure("not in sorted order", n, c);
200  }
201  } else {
202  for (c = DIR_START; c < dir_end; c += D2) {
203  BItem item(p, c);
204  int o = item.get_address() - p;
205  if (o > int(block_size))
206  failure("item starts outside block", n, c);
207  if (o - dir_end < int(max_free))
208  failure("item overlaps directory", n, c);
209 
210  int kt_len = item.size();
211  if (o + kt_len > int(block_size))
212  failure("item ends outside block", n, c);
213  total_free -= kt_len;
214 
215  if (c > significant_c && compare(BItem(p, c - D2), item) >= 0)
216  failure("not in sorted order", n, c);
217  }
218  }
219  if (total_free != TOTAL_FREE(p))
220  failure("stored total free space value wrong", n);
221 
222  if (j == 0) return;
223  for (c = DIR_START; c < dir_end; c += D2) {
224  C_[j].c = c;
225  block_to_cursor(C_, j - 1, BItem(p, c).block_given_by());
226 
227  block_check(C_, j - 1, opts, flcheck);
228 
229  const uint8_t * q = C_[j - 1].get_p();
230  /* if j == 1, and c > DIR_START, the first key of level j - 1 must be
231  * >= the key of p, c: */
232 
233  if (j == 1 && c > DIR_START)
234  if (compare(LeafItem(q, DIR_START), BItem(p, c)) < 0)
235  failure("leaf key < left dividing key in level above", n, c);
236 
237  /* if j > 1, and c > DIR_START, the second key of level j - 1 must be
238  * >= the key of p, c: */
239 
240  if (j > 1 && c > DIR_START && DIR_END(q) > DIR_START + D2 &&
241  compare(BItem(q, DIR_START + D2), BItem(p, c)) < 0)
242  failure("key < left dividing key in level above", n, c);
243 
244  /* the last key of level j - 1 must be < the key of p, c + D2, if c +
245  * D2 < dir_end: */
246 
247  if (c + D2 < dir_end) {
248  if (j == 1) {
249  if (compare(LeafItem(q, DIR_END(q) - D2), BItem(p, c + D2)) >= 0)
250  failure("leaf key >= right dividing key in level above", n, c);
251  } else if (DIR_START + D2 < DIR_END(q)) {
252  if (compare(BItem(q, DIR_END(q) - D2), BItem(p, c + D2)) >= 0)
253  failure("key >= right dividing key in level above", n, c);
254  }
255  }
256 
257  if (REVISION(q) > REVISION(p))
258  failure("block has greater revision than parent", n);
259  }
260 }
261 
263 GlassTableCheck::check(const char * tablename, const string & path, int fd,
264  off_t offset_,
265  const GlassVersion & version_file, int opts,
266  ostream *out)
267 {
268  string filename(path);
269  filename += '/';
270  filename += tablename;
271  filename += '.';
272 
273  AutoPtr<GlassTableCheck> B(
274  fd < 0 ?
275  new GlassTableCheck(tablename, filename, false, out) :
276  new GlassTableCheck(tablename, fd, offset_, false, out));
277 
278  Glass::table_type tab_type;
279  if (strcmp(tablename, "postlist") == 0) {
280  tab_type = Glass::POSTLIST;
281  } else if (strcmp(tablename, "docdata") == 0) {
282  tab_type = Glass::DOCDATA;
283  } else if (strcmp(tablename, "termlist") == 0) {
284  tab_type = Glass::TERMLIST;
285  } else if (strcmp(tablename, "position") == 0) {
286  tab_type = Glass::POSITION;
287  } else if (strcmp(tablename, "spelling") == 0) {
288  tab_type = Glass::SPELLING;
289  } else if (strcmp(tablename, "synonym") == 0) {
290  tab_type = Glass::SYNONYM;
291  } else {
292  string e = "Unknown table: ";
293  e += tablename;
294  throw Xapian::DatabaseError(e);
295  }
296 
297  B->open(0, version_file.get_root(tab_type), version_file.get_revision());
298  Glass::Cursor * C = B->C;
299 
300  if (opts & Xapian::DBCHECK_SHOW_STATS) {
301  *out << "blocksize=" << B->block_size / 1024 << "K"
302  " items=" << B->item_count
303  << " firstunused=" << B->free_list.get_first_unused_block()
304  << " revision=" << B->revision_number
305  << " levels=" << B->level
306  << " root=";
307  if (B->faked_root_block)
308  *out << "(faked)";
309  else
310  *out << C[B->level].get_n();
311  *out << endl;
312  }
313 
314  if (B->faked_root_block) {
315  if (out && opts)
316  *out << "void ";
317  } else {
318  // We walk the Btree marking off the blocks which it uses, then walk
319  // the free list, marking the blocks which aren't used. Any blocks not
320  // marked have been leaked.
321  GlassFreeListChecker flcheck(B->free_list);
322  GlassFreeListChecker flcheck2(B->free_list);
323  B->block_check(C, B->level, opts, flcheck);
324 
325  if (opts & Xapian::DBCHECK_SHOW_FREELIST) {
326  *out << "Freelist:";
327  if (B->free_list.empty())
328  *out << " empty";
329  }
330  while (!B->free_list.empty()) {
331  uint4 n = B->free_list.walk(B.get(), B->block_size, true);
332  if (opts & Xapian::DBCHECK_SHOW_FREELIST)
333  *out << ' ' << n;
334  if (!flcheck2.mark_used(n)) {
335  if (opts & Xapian::DBCHECK_SHOW_FREELIST)
336  *out << endl;
337  failure("Same block is in freelist more than once", n);
338  }
339  if (!flcheck.mark_used(n)) {
340  if (opts & Xapian::DBCHECK_SHOW_FREELIST)
341  *out << endl;
342  failure("Used block also in freelist", n);
343  }
344  }
345  if (opts & Xapian::DBCHECK_SHOW_FREELIST)
346  *out << endl;
347 
348  uint4 first_bad;
349  uint4 count = flcheck.count_set_bits(&first_bad);
350  // Skip this check for a single file DB for now. FIXME
351  if (count && fd < 0) {
352  string e = str(count);
353  e += " unused block(s) missing from the free list, first is ";
354  e += str(first_bad);
355  throw Xapian::DatabaseError(e);
356  }
357  }
358  if (out && opts) *out << "B-tree checked okay" << endl;
359  return B.release();
360 }
361 
362 void GlassTableCheck::report_cursor(int N, const Glass::Cursor * C_) const
363 {
364  *out << N << ")\n";
365  for (int i = 0; i <= level; ++i)
366  *out << "p=" << C_[i].get_p() << ", "
367  "c=" << C_[i].c << ", "
368  "n=[" << C_[i].get_n() << "], "
369  "rewrite=" << C_[i].rewrite << endl;
370 }
const RootInfo & get_root(Glass::table_type tbl) const
bool mark_used(uint4 n)
GlassVersion class.
int component_of() const
Definition: glass_table.h:184
Definition: unittest.cc:682
table_type
Definition: glass_defs.h:46
int TOTAL_FREE(const uint8_t *b)
Definition: glass_table.h:113
uint4 REVISION(const uint8_t *b)
Definition: glass_table.h:110
Constants in the Xapian namespace.
The GlassVersion class manages the revision files.
Definition: glass_version.h:94
static const char * opts
STL namespace.
void print_tag(const uint8_t *p, int c, int j) const
Definition: glass_check.cc:76
void report_block(int m, int n, const uint8_t *p) const
GlassTableCheck::report_block(m, n, p) prints the block at p, block number n, indented by m spaces...
Definition: glass_check.cc:119
const int DBCHECK_SHOW_FREELIST
Show the bitmap for the B-tree.
Definition: constants.h:222
int size() const
SIZE in diagram above.
Definition: glass_table.h:178
void print_bytes(int n, const uint8_t *p) const
Definition: glass_check.cc:45
int MAX_FREE(const uint8_t *b)
Definition: glass_table.h:112
int compare(ITEM1 a, ITEM2 b)
Compare two items by their keys.
Definition: glass_table.h:935
static void failure(const char *msg, uint4 n, int c=0)
Definition: glass_check.cc:142
void read(std::string *key) const
Definition: glass_table.h:146
const int DBCHECK_FULL_TREE
Show a full display of the B-tree contents.
Definition: constants.h:216
void description_append(std::string &desc, const std::string &s)
Definition: unittest.cc:100
uint32_t uint4
Definition: internaltypes.h:32
int GET_LEVEL(const uint8_t *b)
Definition: glass_table.h:111
Btree checking.
int length() const
Definition: glass_table.h:149
string str(int value)
Convert int to std::string.
Definition: str.cc:90
uint4 count_set_bits(uint4 *p_first_bad_blk) const
Count how many bits are still set.
const int D2
Definition: glass_table.h:74
void report_cursor(int N, const Glass::Cursor *C_) const
Definition: glass_check.cc:362
bool last_component() const
Definition: glass_table.h:183
void report_block_full(int m, int n, const uint8_t *p) const
Definition: glass_check.cc:91
int DIR_END(const uint8_t *b)
Definition: glass_table.h:114
static GlassTableCheck * check(const char *tablename, const std::string &path, int fd, off_t offset_, const GlassVersion &version_file, int opts, std::ostream *out)
Definition: glass_check.cc:263
Append a string to an object description, escaping invalid UTF-8.
const int DIR_START
Definition: glass_table.h:115
int size() const
SIZE in diagram above.
Definition: glass_table.h:319
void block_check(Glass::Cursor *C_, int j, int opts, GlassFreeListChecker &flcheck)
Definition: glass_check.cc:156
Key key() const
Definition: glass_table.h:322
void append_chunk(std::string *tag) const
Definition: glass_table.h:189
int c
offset in the block&#39;s directory
Definition: glass_cursor.h:134
int block_usage(const uint8_t *p) const
Definition: glass_check.cc:109
void print_key(const uint8_t *p, int c, int j) const
Definition: glass_check.cc:50
void print_spaces(int n) const
Definition: glass_check.cc:40
T get_address() const
Definition: glass_table.h:317
const uint8_t * get_p() const
Get pointer to block.
Definition: glass_cursor.h:116
DatabaseError indicates some sort of database related error.
Definition: error.h:367
glass_revision_number_t get_revision() const
uint4 block_given_by() const
Get this item&#39;s tag as a block number (this block should not be at level 0).
Definition: glass_table.h:326
uint4 get_n() const
Get the block number.
Definition: glass_cursor.h:101
Wrapper around standard unique_ptr template.
const int DBCHECK_SHORT_TREE
Show a short-format display of the B-tree contents.
Definition: constants.h:210
bool rewrite
true if the block is not the same as on disk, and so needs rewriting
Definition: glass_cursor.h:137
#define C(X)
const int DBCHECK_SHOW_STATS
Show statistics for the B-tree.
Definition: constants.h:228