xapian-core  1.4.19
glass_freelist.cc
Go to the documentation of this file.
1 
4 /* Copyright 2014,2015,2016 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 "glass_freelist.h"
25 
26 #include "glass_table.h"
27 #include "xapian/error.h"
28 
29 #include "omassert.h"
30 #include "wordaccess.h"
31 #include <cstring>
32 
33 #if !HAVE_DECL___BUILTIN_POPCOUNT
34 // Only include <intrin.h> if we have to as it can result in warnings about
35 // duplicate declarations of builtin functions under mingw.
36 # if HAVE_DECL___POPCNT || HAVE_DECL___POPCNT64
37 # include <intrin.h>
38 # endif
39 #endif
40 
41 using namespace std;
42 using namespace Glass;
43 
44 // Allow forcing the freelist to be shorter to tickle bugs.
45 // FIXME: Sort out a way we can set this dynamically while running the
46 // testsuite.
47 #ifdef GLASS_FREELIST_SIZE
48 # define FREELIST_END_ \
49  (8 + (GLASS_FREELIST_SIZE < 3 ? 3 : GLASS_FREELIST_SIZE) * 4)
50 # define FREELIST_END (FREELIST_END_ < 2048 ? FREELIST_END_ : 2048)
51 #else
52 # define FREELIST_END block_size
53 #endif
54 
61 const unsigned C_BASE = 8;
62 
64 const uint4 UNUSED = static_cast<uint4>(-1);
65 
66 void
67 GlassFreeList::read_block(const GlassTable * B, uint4 n, uint8_t * ptr)
68 {
69  B->read_block(n, ptr);
70  if (rare(GET_LEVEL(ptr) != LEVEL_FREELIST))
71  throw Xapian::DatabaseCorruptError("Freelist corrupt");
72 }
73 
74 void
75 GlassFreeList::write_block(const GlassTable * B, uint4 n, uint8_t * ptr,
76  uint4 rev)
77 {
78  SET_REVISION(ptr, rev);
79  aligned_write4(ptr + 4, 0);
81  B->write_block(n, ptr, flw_appending);
82 }
83 
84 uint4
86  uint4 * blk_to_free)
87 {
88  if (fl == fl_end) {
89  return first_unused_block++;
90  }
91 
92  if (p == 0) {
93  if (fl.n == UNUSED) {
94  throw Xapian::DatabaseCorruptError("Freelist pointer invalid");
95  }
96  // Actually read the current freelist block.
97  p = new uint8_t[block_size];
98  read_block(B, fl.n, p);
99  }
100 
101  // Either the freelist end is in this block, or this freelist block has a
102  // next pointer.
103  Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
104 
105  if (fl.c != FREELIST_END - 4) {
106  uint4 blk = aligned_read4(p + fl.c);
107  if (blk == UNUSED)
108  throw Xapian::DatabaseCorruptError("Ran off end of freelist (" + str(fl.n) + ", " + str(fl.c) + ")");
109  fl.c += 4;
110  return blk;
111  }
112 
113  // Delay handling marking old block as unused until after we've
114  // started a new one.
115  uint4 old_fl_blk = fl.n;
116 
117  fl.n = aligned_read4(p + fl.c);
118  if (fl.n == UNUSED) {
119  throw Xapian::DatabaseCorruptError("Freelist next pointer invalid");
120  }
121  // Allow for mini-header at start of freelist block.
122  fl.c = C_BASE;
123  read_block(B, fl.n, p);
124 
125  // Either the freelist end is in this block, or this freelist block has
126  // a next pointer.
127  Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
128 
129  if (blk_to_free) {
130  Assert(*blk_to_free == BLK_UNUSED);
131  *blk_to_free = old_fl_blk;
132  } else {
133  mark_block_unused(B, block_size, old_fl_blk);
134  }
135 
136  return get_block(B, block_size);
137 }
138 
139 uint4
140 GlassFreeList::walk(const GlassTable *B, uint4 block_size, bool inclusive)
141 {
142  if (fl == fl_end) {
143  // It's expected that the caller checks !empty() first.
144  return UNUSED;
145  }
146 
147  if (p == 0) {
148  if (fl.n == UNUSED) {
149  throw Xapian::DatabaseCorruptError("Freelist pointer invalid");
150  }
151  p = new uint8_t[block_size];
152  read_block(B, fl.n, p);
153  if (inclusive) {
154  Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
155  return fl.n;
156  }
157  }
158 
159  // Either the freelist end is in this block, or this freelist block has
160  // a next pointer.
161  Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
162 
163  if (fl.c != FREELIST_END - 4) {
164  uint4 blk = aligned_read4(p + fl.c);
165  fl.c += 4;
166  return blk;
167  }
168 
169  fl.n = aligned_read4(p + fl.c);
170  if (fl.n == UNUSED) {
171  throw Xapian::DatabaseCorruptError("Freelist next pointer invalid");
172  }
173  // Allow for mini-header at start of freelist block.
174  fl.c = C_BASE;
175  read_block(B, fl.n, p);
176 
177  // Either the freelist end is in this block, or this freelist block has
178  // a next pointer.
179  Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
180 
181  if (inclusive)
182  return fl.n;
183  return walk(B, block_size, inclusive);
184 }
185 
186 void
188 {
189  // If the current flw block is full, we need to call get_block(), and if
190  // the returned block is the last entry in its freelist block, that block
191  // needs to be marked as unused. The recursion this would create is
192  // problematic, so we instead note down that block and mark it as unused
193  // once we've processed the original request.
194  uint4 blk_to_free = BLK_UNUSED;
195 
196  if (!pw) {
197  pw = new uint8_t[block_size];
198  if (flw.c != 0) {
199  read_block(B, flw.n, pw);
200  flw_appending = true;
201  }
202  }
203  if (flw.c == 0) {
204  uint4 n = get_block(B, block_size, &blk_to_free);
205  flw.n = n;
206  flw.c = C_BASE;
207  if (fl.c == 0) {
208  fl = fl_end = flw;
209  }
210  flw_appending = (n == first_unused_block - 1);
212  } else if (flw.c == FREELIST_END - 4) {
213  // blk is free *after* the current revision gets released, so we can't
214  // just use blk as the next block in the freelist chain.
215  uint4 n = get_block(B, block_size, &blk_to_free);
216  aligned_write4(pw + flw.c, n);
217 #ifdef GLASS_FREELIST_SIZE
218  if (block_size != FREELIST_END) {
219  memset(pw + FREELIST_END, 0, block_size - FREELIST_END);
220  }
221 #endif
222  write_block(B, flw.n, pw, revision + 1);
223  if (p && flw.n == fl.n) {
224  // FIXME: share and refcount?
225  memcpy(p, pw, block_size);
226  Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
227  }
228  flw.n = n;
229  flw.c = C_BASE;
230  flw_appending = (n == first_unused_block - 1);
232  }
233 
234  aligned_write4(pw + flw.c, blk);
235  flw.c += 4;
236 
237  if (blk_to_free != BLK_UNUSED)
238  mark_block_unused(B, block_size, blk_to_free);
239 }
240 
241 void
243 {
244  if (pw && flw.c != 0) {
245  memset(pw + flw.c, 255, FREELIST_END - flw.c - 4);
246 #ifdef GLASS_FREELIST_SIZE
247  if (block_size != FREELIST_END) {
248  memset(pw + FREELIST_END, 0xaa, block_size - FREELIST_END);
249  }
250 #endif
251  write_block(B, flw.n, pw, revision);
252  if (p && flw.n == fl.n) {
253  // FIXME: share and refcount?
254  memcpy(p, pw, block_size);
255  Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
256  }
257  flw_appending = true;
258  fl_end = flw;
259  }
260 }
261 
263 {
264  const unsigned BITS_PER_ELT = sizeof(elt_type) * 8;
265  const elt_type ALL_BITS = static_cast<elt_type>(-1);
266  uint4 first_unused = fl.get_first_unused_block();
267  bitmap_size = (first_unused + BITS_PER_ELT - 1) / BITS_PER_ELT;
268  bitmap = new elt_type[bitmap_size];
269  std::fill_n(bitmap, bitmap_size - 1, ALL_BITS);
270  // Only set the bits in the final element of bitmap which correspond to
271  // blocks < first_unused.
272  uint4 remainder = first_unused & (BITS_PER_ELT - 1);
273  if (remainder)
274  bitmap[bitmap_size - 1] = (static_cast<elt_type>(1) << remainder) - 1;
275  else
276  bitmap[bitmap_size - 1] = ALL_BITS;
277 }
278 
279 uint4
281 {
282  const unsigned BITS_PER_ELT = sizeof(elt_type) * 8;
283  uint4 c = 0;
284  for (uint4 i = 0; i < bitmap_size; ++i) {
285  elt_type elt = bitmap[i];
286  if (usual(elt == 0))
287  continue;
288  if (c == 0 && p_first_bad_blk) {
289  uint4 first_bad_blk = i * BITS_PER_ELT;
290  if (false) {
291 #if HAVE_DECL___BUILTIN_CTZ
292  } else if (sizeof(elt_type) == sizeof(unsigned)) {
293  first_bad_blk += __builtin_ctz(elt);
294 #endif
295 #if HAVE_DECL___BUILTIN_CTZL
296  } else if (sizeof(elt_type) == sizeof(unsigned long)) {
297  first_bad_blk += __builtin_ctzl(elt);
298 #endif
299 #if HAVE_DECL___BUILTIN_CTZLL
300  } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
301  first_bad_blk += __builtin_ctzll(elt);
302 #endif
303  } else {
304  for (elt_type mask = 1; (elt & mask) == 0; mask <<= 1) {
305  ++first_bad_blk;
306  }
307  }
308  *p_first_bad_blk = first_bad_blk;
309  }
310 
311  // Count set bits in elt.
312  if (false) {
313 #if HAVE_DECL___BUILTIN_POPCOUNT
314  } else if (sizeof(elt_type) == sizeof(unsigned)) {
315  c += __builtin_popcount(elt);
316 #elif HAVE_DECL___POPCNT
317  } else if (sizeof(elt_type) == sizeof(unsigned)) {
318  c += static_cast<uint4>(__popcnt(elt));
319 #endif
320 #if HAVE_DECL___BUILTIN_POPCOUNTL
321  } else if (sizeof(elt_type) == sizeof(unsigned long)) {
322  c += __builtin_popcountl(elt);
323 #endif
324 #if HAVE_DECL___BUILTIN_POPCOUNTLL
325  } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
326  c += __builtin_popcountll(elt);
327 #elif HAVE_DECL___POPCNT64
328  } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
329  c += static_cast<uint4>(__popcnt64(elt));
330 #endif
331  } else {
332  do {
333  ++c;
334  elt &= elt - 1;
335  } while (elt);
336  }
337  }
338  return c;
339 }
#define Assert(COND)
Definition: omassert.h:122
uint4 walk(const GlassTable *B, uint4 block_size, bool inclusive)
void write_block(const GlassTable *B, uint4 n, uint8_t *p, uint4 rev)
Definition: unittest.cc:682
XAPIAN_REVISION_TYPE rev
Revision number of a database.
Definition: types.h:133
void commit(const GlassTable *B, uint4 block_size)
#define usual(COND)
Definition: config.h:544
Class managing a Btree table in a Glass database.
Definition: glass_table.h:430
GlassFreeListChecker(const GlassFreeListChecker &)
void mark_block_unused(const GlassTable *B, uint4 block_size, uint4 n)
#define FREELIST_END
#define BLK_UNUSED
Definition: chert_cursor.h:31
STL namespace.
int revision()
Report the revision of the library which the program is linked with.
Definition: xapian.h:142
void write_block(uint4 n, const uint8_t *p, bool appending=false) const
write_block(n, p, appending) writes block n in the DB file from address p.
Definition: glass_table.cc:191
#define rare(COND)
Definition: config.h:543
void aligned_write4(unsigned char *ptr, T value)
Definition: wordaccess.h:170
Hierarchy of classes which Xapian can throw as exceptions.
uint32_t uint4
Definition: internaltypes.h:32
functions for reading and writing different width words
Glass freelist.
void SET_LEVEL(uint8_t *b, int x)
Definition: chert_table.h:158
uint4 get_first_unused_block() const
int GET_LEVEL(const uint8_t *b)
Definition: chert_table.h:151
uint32_t aligned_read4(const unsigned char *ptr)
Definition: wordaccess.h:145
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.
void read_block(const GlassTable *B, uint4 n, uint8_t *p)
Btree implementation.
unsigned long elt_type
DatabaseCorruptError indicates database corruption was detected.
Definition: error.h:409
void read_block(uint4 n, uint8_t *p) const
read_block(n, p) reads block n of the DB file to address p.
Definition: glass_table.cc:160
const int LEVEL_FREELIST
Freelist blocks have their level set to LEVEL_FREELIST.
Definition: glass_table.h:136
Various assertion macros.
const uint4 UNUSED
Invalid freelist block value, so we can detect overreading bugs, etc.
void SET_REVISION(uint8_t *b, uint4 rev)
Definition: chert_table.h:157
uint4 get_block(const GlassTable *B, uint4 block_size, uint4 *blk_to_free=NULL)
const unsigned C_BASE
The first offset to use for storing free block info.