tdb: fix tdb_check() on other-endian tdbs.
[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 /* Since we opened it, these shouldn't fail unless it's recent corruption. */
29 static bool tdb_check_header(struct tdb_context *tdb, tdb_off_t *recovery)
30 {
31         struct tdb_header hdr;
32
33         if (tdb->methods->tdb_read(tdb, 0, &hdr, sizeof(hdr), 0) == -1)
34                 return false;
35         if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0)
36                 goto corrupt;
37
38         CONVERT(hdr);
39         if (hdr.version != TDB_VERSION)
40                 goto corrupt;
41
42         if (hdr.hashcheck != hashcheck(tdb))
43                 goto corrupt;
44
45         if (hdr.hash_size == 0)
46                 goto corrupt;
47
48         if (hdr.hash_size != tdb->header.hash_size)
49                 goto corrupt;
50
51         if (hdr.recovery_start != 0 &&
52             hdr.recovery_start < TDB_DATA_START(tdb->header.hash_size))
53                 goto corrupt;
54
55         *recovery = hdr.recovery_start;
56         return true;
57
58 corrupt:
59         tdb->ecode = TDB_ERR_CORRUPT;
60         TDB_LOG((tdb, TDB_DEBUG_ERROR, "Header is corrupt\n"));
61         return false;
62 }
63
64 /* Generic record header check. */
65 static bool tdb_check_record(struct tdb_context *tdb,
66                              tdb_off_t off,
67                              const struct tdb_record *rec)
68 {
69         tdb_off_t tailer;
70
71         /* Check rec->next: 0 or points to record offset, aligned. */
72         if (rec->next > 0 && rec->next < TDB_DATA_START(tdb->header.hash_size)){
73                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
74                          "Record offset %d too small next %d\n",
75                          off, rec->next));
76                 goto corrupt;
77         }
78         if (rec->next + sizeof(*rec) < rec->next) {
79                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
80                          "Record offset %d too large next %d\n",
81                          off, rec->next));
82                 goto corrupt;
83         }
84         if ((rec->next % TDB_ALIGNMENT) != 0) {
85                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
86                          "Record offset %d misaligned next %d\n",
87                          off, rec->next));
88                 goto corrupt;
89         }
90         if (tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 0))
91                 goto corrupt;
92
93         /* Check rec_len: similar to rec->next, implies next record. */
94         if ((rec->rec_len % TDB_ALIGNMENT) != 0) {
95                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
96                          "Record offset %d misaligned length %d\n",
97                          off, rec->rec_len));
98                 goto corrupt;
99         }
100         /* Must fit tailer. */
101         if (rec->rec_len < sizeof(tailer)) {
102                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
103                          "Record offset %d too short length %d\n",
104                          off, rec->rec_len));
105                 goto corrupt;
106         }
107         /* OOB allows "right at the end" access, so this works for last rec. */
108         if (tdb->methods->tdb_oob(tdb, off+sizeof(*rec)+rec->rec_len, 0))
109                 goto corrupt;
110
111         /* Check tailer. */
112         if (tdb_ofs_read(tdb, off+sizeof(*rec)+rec->rec_len-sizeof(tailer),
113                          &tailer) == -1)
114                 goto corrupt;
115         if (tailer != sizeof(*rec) + rec->rec_len) {
116                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
117                          "Record offset %d invalid tailer\n", off));
118                 goto corrupt;
119         }
120
121         return true;
122
123 corrupt:
124         tdb->ecode = TDB_ERR_CORRUPT;
125         return false;
126 }
127
128 /* Grab some bytes: may copy if can't use mmap.
129    Caller has already done bounds check. */
130 static TDB_DATA get_bytes(struct tdb_context *tdb,
131                           tdb_off_t off, tdb_len_t len)
132 {
133         TDB_DATA d;
134
135         d.dsize = len;
136
137         if (tdb->transaction == NULL && tdb->map_ptr != NULL)
138                 d.dptr = (unsigned char *)tdb->map_ptr + off;
139         else
140                 d.dptr = tdb_alloc_read(tdb, off, d.dsize);
141         return d;
142 }
143
144 /* Frees data if we're not able to simply use mmap. */
145 static void put_bytes(struct tdb_context *tdb, TDB_DATA d)
146 {
147         if (tdb->transaction == NULL && tdb->map_ptr != NULL)
148                 return;
149         free(d.dptr);
150 }
151
152 /* We use the excellent Jenkins lookup3 hash; this is based on hash_word2.
153  * See: http://burtleburtle.net/bob/c/lookup3.c
154  */
155 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
156 static void hash(uint32_t key, uint32_t *pc, uint32_t *pb)
157 {
158         uint32_t a,b,c;
159
160         /* Set up the internal state */
161         a = b = c = 0xdeadbeef + *pc;
162         c += *pb;
163         a += key;
164         c ^= b; c -= rot(b,14);
165         a ^= c; a -= rot(c,11);
166         b ^= a; b -= rot(a,25);
167         c ^= b; c -= rot(b,16);
168         a ^= c; a -= rot(c,4);
169         b ^= a; b -= rot(a,14);
170         c ^= b; c -= rot(b,24);
171         *pc=c; *pb=b;
172 }
173
174 /*
175   We want to check that all free records are in the free list
176   (only once), and all free list entries are free records.  Similarly
177   for each hash chain of used records.
178
179   Doing that naively (without walking hash chains, since we want to be
180   linear) means keeping a list of records which have been seen in each
181   hash chain, and another of records pointed to (ie. next pointers
182   from records and the initial hash chain heads).  These two lists
183   should be equal.  This will take 8 bytes per record, and require
184   sorting at the end.
185
186   So instead, we record each offset in a bitmap such a way that
187   recording it twice will cancel out.  Since each offset should appear
188   exactly twice, the bitmap should be zero at the end.
189
190   The approach was inspired by Bloom Filters (see Wikipedia).  For
191   each value, we flip K bits in a bitmap of size N.  The number of
192   distinct arrangements is:
193
194         N! / (K! * (N-K)!)
195
196   Of course, not all arrangements are actually distinct, but testing
197   shows this formula to be close enough.
198
199   So, if K == 8 and N == 256, the probability of two things flipping the same
200   bits is 1 in 409,663,695,276,000.
201
202   Given that ldb uses a hash size of 10000, using 32 bytes per hash chain
203   (320k) seems reasonable.
204 */
205 #define NUM_HASHES 8
206 #define BITMAP_BITS 256
207
208 static void bit_flip(unsigned char bits[], unsigned int idx)
209 {
210         bits[idx / CHAR_BIT] ^= (1 << (idx % CHAR_BIT));
211 }
212
213 /* We record offsets in a bitmap for the particular chain it should be in.  */
214 static void record_offset(unsigned char bits[], tdb_off_t off)
215 {
216         uint32_t h1 = off, h2 = 0;
217         unsigned int i;
218
219         /* We get two good hash values out of jhash2, so we use both.  Then
220          * we keep going to produce further hash values. */
221         for (i = 0; i < NUM_HASHES / 2; i++) {
222                 hash(off, &h1, &h2);
223                 bit_flip(bits, h1 % BITMAP_BITS);
224                 bit_flip(bits, h2 % BITMAP_BITS);
225                 h2++;
226         }
227 }
228
229 /* Check that an in-use record is valid. */
230 static bool tdb_check_used_record(struct tdb_context *tdb,
231                                   tdb_off_t off,
232                                   const struct tdb_record *rec,
233                                   unsigned char **hashes,
234                                   int (*check)(TDB_DATA, TDB_DATA, void *),
235                                   void *private_data)
236 {
237         TDB_DATA key, data;
238
239         if (!tdb_check_record(tdb, off, rec))
240                 return false;
241
242         /* key + data + tailer must fit in record */
243         if (rec->key_len + rec->data_len + sizeof(tdb_off_t) > rec->rec_len) {
244                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
245                          "Record offset %d too short for contents\n", off));
246                 return false;
247         }
248
249         key = get_bytes(tdb, off + sizeof(*rec), rec->key_len);
250         if (!key.dptr)
251                 return false;
252
253         if (tdb->hash_fn(&key) != rec->full_hash) {
254                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
255                          "Record offset %d has incorrect hash\n", off));
256                 goto fail_put_key;
257         }
258
259         /* Mark this offset as a known value for this hash bucket. */
260         record_offset(hashes[BUCKET(rec->full_hash)+1], off);
261         /* And similarly if the next pointer is valid. */
262         if (rec->next)
263                 record_offset(hashes[BUCKET(rec->full_hash)+1], rec->next);
264
265         /* If they supply a check function and this record isn't dead,
266            get data and feed it. */
267         if (check && rec->magic != TDB_DEAD_MAGIC) {
268                 data = get_bytes(tdb, off + sizeof(*rec) + rec->key_len,
269                                  rec->data_len);
270                 if (!data.dptr)
271                         goto fail_put_key;
272
273                 if (check(key, data, private_data) == -1)
274                         goto fail_put_data;
275                 put_bytes(tdb, data);
276         }
277
278         put_bytes(tdb, key);
279         return true;
280
281 fail_put_data:
282         put_bytes(tdb, data);
283 fail_put_key:
284         put_bytes(tdb, key);
285         return false;
286 }
287
288 /* Check that an unused record is valid. */
289 static bool tdb_check_free_record(struct tdb_context *tdb,
290                                   tdb_off_t off,
291                                   const struct tdb_record *rec,
292                                   unsigned char **hashes)
293 {
294         if (!tdb_check_record(tdb, off, rec))
295                 return false;
296
297         /* Mark this offset as a known value for the free list. */
298         record_offset(hashes[0], off);
299         /* And similarly if the next pointer is valid. */
300         if (rec->next)
301                 record_offset(hashes[0], rec->next);
302         return true;
303 }
304
305 /* Slow, but should be very rare. */
306 static size_t dead_space(struct tdb_context *tdb, tdb_off_t off)
307 {
308         size_t len;
309
310         for (len = 0; off + len < tdb->map_size; len++) {
311                 char c;
312                 if (tdb->methods->tdb_read(tdb, off, &c, 1, 0))
313                         return 0;
314                 if (c != 0 && c != 0x42)
315                         break;
316         }
317         return len;
318 }
319
320 int tdb_check(struct tdb_context *tdb,
321               int (*check)(TDB_DATA key, TDB_DATA data, void *private_data),
322               void *private_data)
323 {
324         unsigned int h;
325         unsigned char **hashes;
326         tdb_off_t off, recovery_start;
327         struct tdb_record rec;
328         bool found_recovery = false;
329         tdb_len_t dead;
330         bool locked;
331
332         /* Read-only databases use no locking at all: it's best-effort.
333          * We may have a write lock already, so skip that case too. */
334         if (tdb->read_only || tdb->allrecord_lock.count != 0) {
335                 locked = false;
336         } else {
337                 if (tdb_lockall_read(tdb) == -1)
338                         return -1;
339                 locked = true;
340         }
341
342         /* Make sure we know true size of the underlying file. */
343         tdb->methods->tdb_oob(tdb, tdb->map_size + 1, 1);
344
345         /* Header must be OK: also gets us the recovery ptr, if any. */
346         if (!tdb_check_header(tdb, &recovery_start))
347                 goto unlock;
348
349         /* We should have the whole header, too. */
350         if (tdb->map_size < TDB_DATA_START(tdb->header.hash_size)) {
351                 tdb->ecode = TDB_ERR_CORRUPT;
352                 TDB_LOG((tdb, TDB_DEBUG_ERROR, "File too short for hashes\n"));
353                 goto unlock;
354         }
355
356         /* One big malloc: pointers then bit arrays. */
357         hashes = (unsigned char **)calloc(
358                         1, sizeof(hashes[0]) * (1+tdb->header.hash_size)
359                         + BITMAP_BITS / CHAR_BIT * (1+tdb->header.hash_size));
360         if (!hashes) {
361                 tdb->ecode = TDB_ERR_OOM;
362                 goto unlock;
363         }
364
365         /* Initialize pointers */
366         hashes[0] = (unsigned char *)(&hashes[1+tdb->header.hash_size]);
367         for (h = 1; h < 1+tdb->header.hash_size; h++)
368                 hashes[h] = hashes[h-1] + BITMAP_BITS / CHAR_BIT;
369
370         /* Freelist and hash headers are all in a row: read them. */
371         for (h = 0; h < 1+tdb->header.hash_size; h++) {
372                 if (tdb_ofs_read(tdb, FREELIST_TOP + h*sizeof(tdb_off_t),
373                                  &off) == -1)
374                         goto free;
375                 if (off)
376                         record_offset(hashes[h], off);
377         }
378
379         /* For each record, read it in and check it's ok. */
380         for (off = TDB_DATA_START(tdb->header.hash_size);
381              off < tdb->map_size;
382              off += sizeof(rec) + rec.rec_len) {
383                 if (tdb->methods->tdb_read(tdb, off, &rec, sizeof(rec),
384                                            DOCONV()) == -1)
385                         goto free;
386                 switch (rec.magic) {
387                 case TDB_MAGIC:
388                 case TDB_DEAD_MAGIC:
389                         if (!tdb_check_used_record(tdb, off, &rec, hashes,
390                                                    check, private_data))
391                                 goto free;
392                         break;
393                 case TDB_FREE_MAGIC:
394                         if (!tdb_check_free_record(tdb, off, &rec, hashes))
395                                 goto free;
396                         break;
397                 /* If we crash after ftruncate, we can get zeroes or fill. */
398                 case TDB_RECOVERY_INVALID_MAGIC:
399                 case 0x42424242:
400                         if (recovery_start == off) {
401                                 found_recovery = true;
402                                 break;
403                         }
404                         dead = dead_space(tdb, off);
405                         if (dead < sizeof(rec))
406                                 goto corrupt;
407
408                         TDB_LOG((tdb, TDB_DEBUG_ERROR,
409                                  "Dead space at %d-%d (of %u)\n",
410                                  off, off + dead, tdb->map_size));
411                         rec.rec_len = dead - sizeof(rec);
412                         break;
413                 case TDB_RECOVERY_MAGIC:
414                         if (recovery_start != off) {
415                                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
416                                          "Unexpected recovery record at offset %d\n",
417                                          off));
418                                 goto free;
419                         }
420                         found_recovery = true;
421                         break;
422                 default: ;
423                 corrupt:
424                         tdb->ecode = TDB_ERR_CORRUPT;
425                         TDB_LOG((tdb, TDB_DEBUG_ERROR,
426                                  "Bad magic 0x%x at offset %d\n",
427                                  rec.magic, off));
428                         goto free;
429                 }
430         }
431
432         /* Now, hashes should all be empty: each record exists and is referred
433          * to by one other. */
434         for (h = 0; h < 1+tdb->header.hash_size; h++) {
435                 unsigned int i;
436                 for (i = 0; i < BITMAP_BITS / CHAR_BIT; i++) {
437                         if (hashes[h][i] != 0) {
438                                 tdb->ecode = TDB_ERR_CORRUPT;
439                                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
440                                          "Hashes do not match records\n"));
441                                 goto free;
442                         }
443                 }
444         }
445
446         /* We must have found recovery area if there was one. */
447         if (recovery_start != 0 && !found_recovery) {
448                 TDB_LOG((tdb, TDB_DEBUG_ERROR,
449                          "Expected a recovery area at %u\n",
450                          recovery_start));
451                 goto free;
452         }
453
454         free(hashes);
455         if (locked) {
456                 tdb_unlockall_read(tdb);
457         }
458         return 0;
459
460 free:
461         free(hashes);
462 unlock:
463         if (locked) {
464                 tdb_unlockall_read(tdb);
465         }
466         return -1;
467 }