2 Unix SMB/CIFS implementation.
4 trivial database library
6 Copyright (C) Rusty Russell 2009
8 ** NOTE! The following LGPL license applies to the tdb
9 ** library. This does NOT imply that all of Samba is released
12 This library is free software; you can redistribute it and/or
13 modify it under the terms of the GNU Lesser General Public
14 License as published by the Free Software Foundation; either
15 version 3 of the License, or (at your option) any later version.
17 This library is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 Lesser General Public License for more details.
22 You should have received a copy of the GNU Lesser General Public
23 License along with this library; if not, see <http://www.gnu.org/licenses/>.
25 #include "tdb_private.h"
29 For each value, we flip F bits in a bitmap of size 2^B. So we can think
30 of this as a F*B bit hash (this isn't quite true due to hash collisions,
31 but it seems good enough for F << B).
33 Assume that we only have a single error; this is *not* the birthday
34 problem, since the question is: "does that error hash to the same as
35 the correct value", ie. a simple 1 in 2^F*B. The chances of detecting
36 multiple errors is even higher (since we only need to detect one of
39 Given that ldb uses a hash size of 10000, using 512 bytes per hash chain
40 (5M) seems reasonable. With 128 hashes, that's about 1 in a million chance
41 of missing a single linked list error.
43 #define NUM_HASHES 128
44 #define BITMAP_BITS (512 * CHAR_BIT)
46 /* We use the excellent Jenkins lookup3 hash; this is based on hash_word2.
47 * See: http://burtleburtle.net/bob/c/lookup3.c
49 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
51 #define final(a,b,c) \
53 c ^= b; c -= rot(b,14); \
54 a ^= c; a -= rot(c,11); \
55 b ^= a; b -= rot(a,25); \
56 c ^= b; c -= rot(b,16); \
57 a ^= c; a -= rot(c,4); \
58 b ^= a; b -= rot(a,14); \
59 c ^= b; c -= rot(b,24); \
62 static void hash(uint32_t key, uint32_t *pc, uint32_t *pb)
66 /* Set up the internal state */
67 a = b = c = 0xdeadbeef + *pc;
75 static void bit_flip(unsigned char bits[], unsigned int idx)
77 bits[idx / CHAR_BIT] ^= (1 << (idx % CHAR_BIT));
80 static void add_to_hash(unsigned char bits[], tdb_off_t off)
82 uint32_t h1 = off, h2 = 0;
84 for (i = 0; i < NUM_HASHES / 2; i++) {
86 bit_flip(bits, h1 % BITMAP_BITS);
87 bit_flip(bits, h2 % BITMAP_BITS);
92 /* Since we opened it, these shouldn't fail unless it's recent corruption. */
93 static bool tdb_check_header(struct tdb_context *tdb, tdb_off_t *recovery)
95 struct tdb_header hdr;
97 if (tdb->methods->tdb_read(tdb, 0, &hdr, sizeof(hdr), DOCONV()) == -1)
99 if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0)
103 if (hdr.version != TDB_VERSION)
106 if (hdr.rwlocks != 0)
109 if (hdr.hash_size == 0)
112 if (hdr.hash_size != tdb->header.hash_size)
115 if (hdr.recovery_start != 0 &&
116 hdr.recovery_start < TDB_DATA_START(tdb->header.hash_size))
119 *recovery = hdr.recovery_start;
123 tdb->ecode = TDB_ERR_CORRUPT;
127 static bool tdb_check_record(struct tdb_context *tdb,
129 const struct list_struct *rec)
133 /* Check rec->next: 0 or points to record offset, aligned. */
134 if (rec->next > 0 && rec->next < TDB_DATA_START(tdb->header.hash_size))
136 if (rec->next + sizeof(*rec) < rec->next)
138 if ((rec->next % TDB_ALIGNMENT) != 0)
140 if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 1))
143 /* Check rec_len: similar to rec->next, implies next record. */
144 if ((rec->rec_len % TDB_ALIGNMENT) != 0)
146 /* Must fit tailer. */
147 if (rec->rec_len < sizeof(tailer))
149 /* OOB allows "right at the end" access, so this works for last rec. */
150 if (tdb->methods->tdb_oob(tdb, off+sizeof(*rec)+rec->rec_len, 1))
154 if (tdb_ofs_read(tdb, off+sizeof(*rec)+rec->rec_len-sizeof(tailer),
157 if (tailer != sizeof(*rec) + rec->rec_len)
163 tdb->ecode = TDB_ERR_CORRUPT;
167 static TDB_DATA get_data(struct tdb_context *tdb, tdb_off_t off, tdb_len_t len)
173 /* We've already done bounds check here. */
174 if (tdb->transaction == NULL && tdb->map_ptr != NULL)
175 d.dptr = (unsigned char *)tdb->map_ptr + off;
177 d.dptr = tdb_alloc_read(tdb, off, d.dsize);
181 static void put_data(struct tdb_context *tdb, TDB_DATA d)
183 if (tdb->transaction == NULL && tdb->map_ptr != NULL)
188 static bool tdb_check_used_record(struct tdb_context *tdb,
190 const struct list_struct *rec,
191 unsigned char **hashes,
192 int (*check)(TDB_DATA, TDB_DATA, void *),
197 if (!tdb_check_record(tdb, off, rec))
200 /* key + data + tailer must fit in record */
201 if (rec->key_len + rec->data_len + sizeof(tdb_off_t) > rec->rec_len)
204 key = get_data(tdb, off + sizeof(*rec), rec->key_len);
208 if (tdb->hash_fn(&key) != rec->full_hash)
211 add_to_hash(hashes[BUCKET(rec->full_hash)+1], off);
213 add_to_hash(hashes[BUCKET(rec->full_hash)+1], rec->next);
215 /* If they supply a check function, get data. */
217 data = get_data(tdb, off + sizeof(*rec) + rec->key_len,
222 if (check(key, data, private) == -1)
237 static bool tdb_check_free_record(struct tdb_context *tdb,
239 const struct list_struct *rec,
240 unsigned char **hashes)
242 if (!tdb_check_record(tdb, off, rec))
245 add_to_hash(hashes[0], off);
247 add_to_hash(hashes[0], rec->next);
251 /* We do this via linear scan, even though it's not 100% accurate. */
252 int tdb_check(struct tdb_context *tdb,
253 int (*check)(TDB_DATA key, TDB_DATA data, void *private),
257 unsigned char **hashes;
258 tdb_off_t off, recovery_start;
259 struct list_struct rec;
260 bool found_recovery = false;
262 if (tdb_lockall(tdb) == -1)
265 /* Make sure we know true size of the underlying file. */
266 tdb->methods->tdb_oob(tdb, tdb->map_size + 1, 1);
268 if (!tdb_check_header(tdb, &recovery_start))
271 if (tdb->map_size < TDB_DATA_START(tdb->header.hash_size)) {
272 tdb->ecode = TDB_ERR_CORRUPT;
276 /* One big malloc: pointers then bit arrays. */
277 hashes = calloc(1, sizeof(hashes[0]) * (1+tdb->header.hash_size)
278 + BITMAP_BITS / CHAR_BIT * (1+tdb->header.hash_size));
280 tdb->ecode = TDB_ERR_OOM;
284 /* Initialize pointers */
285 hashes[0] = (unsigned char *)(&hashes[1+tdb->header.hash_size]);
286 for (h = 1; h < 1+tdb->header.hash_size; h++)
287 hashes[h] = hashes[h-1] + BITMAP_BITS / CHAR_BIT;
289 /* Freelist and hash headers are all in a row. */
290 for (h = 0; h < 1+tdb->header.hash_size; h++) {
291 if (tdb_ofs_read(tdb, FREELIST_TOP + h*sizeof(tdb_off_t),
295 add_to_hash(hashes[h], off);
298 for (off = TDB_DATA_START(tdb->header.hash_size);
300 off += sizeof(rec) + rec.rec_len) {
301 if (tdb->methods->tdb_read(tdb, off, &rec, sizeof(rec),
307 if (!tdb_check_used_record(tdb, off, &rec, hashes,
312 if (!tdb_check_free_record(tdb, off, &rec, hashes))
315 case TDB_RECOVERY_MAGIC:
316 if (recovery_start != off)
318 found_recovery = true;
321 tdb->ecode = TDB_ERR_CORRUPT;
326 /* Now, hashes should all be empty: each record exists and is referred
327 * to by one other. */
328 for (h = 0; h < 1+tdb->header.hash_size; h++) {
330 for (i = 0; i < BITMAP_BITS / CHAR_BIT; i++) {
331 if (hashes[h][i] != 0) {
332 tdb->ecode = TDB_ERR_CORRUPT;
338 /* We must have found recovery area. */
339 if (recovery_start != 0 && !found_recovery)