6eca5537372992a8e5a4c2a02aee5a9a6308ef43
[ccan] / ccan / tdb / check.c
1  /* 
2    Unix SMB/CIFS implementation.
3
4    trivial database library
5
6    Copyright (C) Rusty Russell             2009
7    
8      ** NOTE! The following LGPL license applies to the tdb
9      ** library. This does NOT imply that all of Samba is released
10      ** under the LGPL
11    
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.
16
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.
21
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/>.
24 */
25 #include "tdb_private.h"
26 #include <limits.h>
27
28 /*
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).
32
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
37   them).
38
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.
42 */
43 #define NUM_HASHES 128
44 #define BITMAP_BITS (512 * CHAR_BIT)
45
46 /* We use the excellent Jenkins lookup3 hash; this is based on hash_word2.
47  * See: http://burtleburtle.net/bob/c/lookup3.c
48  */
49 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
50
51 #define final(a,b,c) \
52 { \
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); \
60 }
61
62 static void hash(uint32_t key, uint32_t *pc, uint32_t *pb)
63 {
64         uint32_t a,b,c;
65
66         /* Set up the internal state */
67         a = b = c = 0xdeadbeef + *pc;
68         c += *pb;
69
70         a += key;
71         final(a,b,c);
72         *pc=c; *pb=b;
73 }
74
75 static void bit_flip(unsigned char bits[], unsigned int idx)
76 {
77         bits[idx / CHAR_BIT] ^= (1 << (idx % CHAR_BIT));
78 }
79
80 static void add_to_hash(unsigned char bits[], tdb_off_t off)
81 {
82         uint32_t h1 = off, h2 = 0;
83         unsigned int i;
84         for (i = 0; i < NUM_HASHES / 2; i++) {
85                 hash(off, &h1, &h2);
86                 bit_flip(bits, h1 % BITMAP_BITS);
87                 bit_flip(bits, h2 % BITMAP_BITS);
88                 h2++;
89         }
90 }
91
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)
94 {
95         struct tdb_header hdr;
96
97         if (tdb->methods->tdb_read(tdb, 0, &hdr, sizeof(hdr), DOCONV()) == -1)
98                 return false;
99         if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0)
100                 goto corrupt;
101
102         CONVERT(hdr);
103         if (hdr.version != TDB_VERSION)
104                 goto corrupt;
105
106         if (hdr.rwlocks != 0)
107                 goto corrupt;
108
109         if (hdr.hash_size == 0)
110                 goto corrupt;
111
112         if (hdr.hash_size != tdb->header.hash_size)
113                 goto corrupt;
114
115         if (hdr.recovery_start != 0 &&
116             hdr.recovery_start < TDB_DATA_START(tdb->header.hash_size))
117                 goto corrupt;
118
119         *recovery = hdr.recovery_start;
120         return true;
121
122 corrupt:
123         tdb->ecode = TDB_ERR_CORRUPT;
124         return false;
125 }
126
127 static bool tdb_check_record(struct tdb_context *tdb,
128                              tdb_off_t off,
129                              const struct list_struct *rec)
130 {
131         tdb_off_t tailer;
132
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))
135                 goto corrupt;
136         if (rec->next + sizeof(*rec) < rec->next)
137                 goto corrupt;
138         if ((rec->next % TDB_ALIGNMENT) != 0)
139                 goto corrupt;
140         if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 1))
141                 goto corrupt;
142
143         /* Check rec_len: similar to rec->next, implies next record. */
144         if ((rec->rec_len % TDB_ALIGNMENT) != 0)
145                 goto corrupt;
146         /* Must fit tailer. */
147         if (rec->rec_len < sizeof(tailer))
148                 goto corrupt;
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))
151                 goto corrupt;
152
153         /* Check tailer. */
154         if (tdb_ofs_read(tdb, off+sizeof(*rec)+rec->rec_len-sizeof(tailer),
155                          &tailer) == -1)
156                 goto corrupt;
157         if (tailer != sizeof(*rec) + rec->rec_len)
158                 goto corrupt;
159
160         return true;
161
162 corrupt:
163         tdb->ecode = TDB_ERR_CORRUPT;
164         return false;
165 }
166
167 static TDB_DATA get_data(struct tdb_context *tdb, tdb_off_t off, tdb_len_t len)
168 {
169         TDB_DATA d;
170
171         d.dsize = len;
172
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;
176         else
177                 d.dptr = tdb_alloc_read(tdb, off, d.dsize);
178         return d;
179 }
180
181 static void put_data(struct tdb_context *tdb, TDB_DATA d)
182 {
183         if (tdb->transaction == NULL && tdb->map_ptr != NULL)
184                 return;
185         free(d.dptr);
186 }
187
188 static bool tdb_check_used_record(struct tdb_context *tdb,
189                                   tdb_off_t off,
190                                   const struct list_struct *rec,
191                                   unsigned char **hashes,
192                                   int (*check)(TDB_DATA, TDB_DATA, void *),
193                                   void *private)
194 {
195         TDB_DATA key, data;
196
197         if (!tdb_check_record(tdb, off, rec))
198                 return false;
199
200         /* key + data + tailer must fit in record */
201         if (rec->key_len + rec->data_len + sizeof(tdb_off_t) > rec->rec_len)
202                 return false;
203
204         key = get_data(tdb, off + sizeof(*rec), rec->key_len);
205         if (!key.dptr)
206                 return false;
207
208         if (tdb->hash_fn(&key) != rec->full_hash)
209                 goto fail_put_key;
210
211         add_to_hash(hashes[BUCKET(rec->full_hash)+1], off);
212         if (rec->next)
213                 add_to_hash(hashes[BUCKET(rec->full_hash)+1], rec->next);
214
215         /* If they supply a check function, get data. */
216         if (check) {
217                 data = get_data(tdb, off + sizeof(*rec) + rec->key_len,
218                                 rec->data_len);
219                 if (!data.dptr)
220                         goto fail_put_key;
221
222                 if (check(key, data, private) == -1)
223                         goto fail_put_data;
224                 put_data(tdb, data);
225         }
226
227         put_data(tdb, key);
228         return true;
229
230 fail_put_data:
231         put_data(tdb, data);
232 fail_put_key:
233         put_data(tdb, key);
234         return false;
235 }
236
237 static bool tdb_check_free_record(struct tdb_context *tdb,
238                                   tdb_off_t off,
239                                   const struct list_struct *rec,
240                                   unsigned char **hashes)
241 {
242         if (!tdb_check_record(tdb, off, rec))
243                 return false;
244
245         add_to_hash(hashes[0], off);
246         if (rec->next)
247                 add_to_hash(hashes[0], rec->next);
248         return true;
249 }
250
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),
254               void *private)
255 {
256         unsigned int h;
257         unsigned char **hashes;
258         tdb_off_t off, recovery_start;
259         struct list_struct rec;
260         bool found_recovery = false;
261
262         if (tdb_lockall(tdb) == -1)
263                 return -1;
264
265         /* Make sure we know true size of the underlying file. */
266         tdb->methods->tdb_oob(tdb, tdb->map_size + 1, 1);
267
268         if (!tdb_check_header(tdb, &recovery_start))
269                 goto unlock;
270
271         if (tdb->map_size < TDB_DATA_START(tdb->header.hash_size)) {
272                 tdb->ecode = TDB_ERR_CORRUPT;
273                 goto unlock;
274         }
275
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));
279         if (!hashes) {
280                 tdb->ecode = TDB_ERR_OOM;
281                 goto unlock;
282         }
283
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;
288
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),
292                                  &off) == -1)
293                         goto free;
294                 if (off)
295                         add_to_hash(hashes[h], off);
296         }
297
298         for (off = TDB_DATA_START(tdb->header.hash_size);
299              off < tdb->map_size;
300              off += sizeof(rec) + rec.rec_len) {
301                 if (tdb->methods->tdb_read(tdb, off, &rec, sizeof(rec),
302                                            DOCONV()) == -1)
303                         goto free;
304                 switch (rec.magic) {
305                 case TDB_MAGIC:
306                 case TDB_DEAD_MAGIC:
307                         if (!tdb_check_used_record(tdb, off, &rec, hashes,
308                                                    check, private))
309                                 goto free;
310                         break;
311                 case TDB_FREE_MAGIC:
312                         if (!tdb_check_free_record(tdb, off, &rec, hashes))
313                                 goto free;
314                         break;
315                 case TDB_RECOVERY_MAGIC:
316                         if (recovery_start != off)
317                                 goto free;
318                         found_recovery = true;
319                         break;
320                 default:
321                         tdb->ecode = TDB_ERR_CORRUPT;
322                         goto free;
323                 }
324         }
325
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++) {
329                 unsigned int i;
330                 for (i = 0; i < BITMAP_BITS / CHAR_BIT; i++) {
331                         if (hashes[h][i] != 0) {
332                                 tdb->ecode = TDB_ERR_CORRUPT;
333                                 goto free;
334                         }
335                 }
336         }
337
338         /* We must have found recovery area. */
339         if (recovery_start != 0 && !found_recovery)
340                 goto free;
341
342         free(hashes);
343         tdb_unlockall(tdb);
344         return 0;
345
346 free:
347         free(hashes);
348 unlock:
349         tdb_unlockall(tdb);
350         return -1;
351 }
352
353                 
354
355         
356
357