2 Trivial Database 2: free list/block handling
3 Copyright (C) Rusty Russell 2010
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 3 of the License, or (at your option) any later version.
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, see <http://www.gnu.org/licenses/>.
19 #include <ccan/likely/likely.h>
20 #include <ccan/asearch/asearch.h>
22 /* We keep an ordered array of offsets. */
23 static bool append(struct ntdb_context
*ntdb
,
24 ntdb_off_t
**arr
, size_t *num
, ntdb_off_t off
)
29 new = ntdb
->alloc_fn(ntdb
, sizeof(ntdb_off_t
), ntdb
->alloc_data
);
31 new = ntdb
->expand_fn(*arr
, (*num
+ 1) * sizeof(ntdb_off_t
),
41 static enum NTDB_ERROR
check_header(struct ntdb_context
*ntdb
, ntdb_off_t
*recovery
,
42 uint64_t *features
, size_t *num_capabilities
)
45 struct ntdb_header hdr
;
46 enum NTDB_ERROR ecode
;
49 ecode
= ntdb_read_convert(ntdb
, 0, &hdr
, sizeof(hdr
));
50 if (ecode
!= NTDB_SUCCESS
) {
53 /* magic food should not be converted, so convert back. */
54 ntdb_convert(ntdb
, hdr
.magic_food
, sizeof(hdr
.magic_food
));
56 hash_test
= NTDB_HASH_MAGIC
;
57 hash_test
= ntdb_hash(ntdb
, &hash_test
, sizeof(hash_test
));
58 if (hdr
.hash_test
!= hash_test
) {
59 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
60 "check: hash test %llu should be %llu",
61 (long long)hdr
.hash_test
,
62 (long long)hash_test
);
65 if (strcmp(hdr
.magic_food
, NTDB_MAGIC_FOOD
) != 0) {
66 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
67 "check: bad magic '%.*s'",
68 (unsigned)sizeof(hdr
.magic_food
),
72 /* Features which are used must be a subset of features offered. */
73 if (hdr
.features_used
& ~hdr
.features_offered
) {
74 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
75 "check: features used (0x%llx) which"
76 " are not offered (0x%llx)",
77 (long long)hdr
.features_used
,
78 (long long)hdr
.features_offered
);
81 *features
= hdr
.features_offered
;
82 *recovery
= hdr
.recovery
;
84 if (*recovery
< sizeof(hdr
)
85 || *recovery
> ntdb
->file
->map_size
) {
86 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
88 " invalid recovery offset %zu",
93 for (off
= hdr
.capabilities
; off
&& ecode
== NTDB_SUCCESS
; off
= next
) {
94 const struct ntdb_capability
*cap
;
97 cap
= ntdb_access_read(ntdb
, off
, sizeof(*cap
), true);
98 if (NTDB_PTR_IS_ERR(cap
)) {
99 return NTDB_PTR_ERR(cap
);
102 /* All capabilities are unknown. */
103 e
= unknown_capability(ntdb
, "ntdb_check", cap
->type
);
105 ntdb_access_release(ntdb
, cap
);
108 (*num_capabilities
)++;
111 /* Don't check reserved: they *can* be used later. */
115 static enum NTDB_ERROR
check_hash_tree(struct ntdb_context
*ntdb
,
116 ntdb_off_t off
, unsigned int group_bits
,
118 unsigned hprefix_bits
,
122 enum NTDB_ERROR (*check
)(NTDB_DATA
,
126 static enum NTDB_ERROR
check_hash_chain(struct ntdb_context
*ntdb
,
132 enum NTDB_ERROR (*check
)(NTDB_DATA
,
137 struct ntdb_used_record rec
;
138 enum NTDB_ERROR ecode
;
140 ecode
= ntdb_read_convert(ntdb
, off
, &rec
, sizeof(rec
));
141 if (ecode
!= NTDB_SUCCESS
) {
145 if (rec_magic(&rec
) != NTDB_CHAIN_MAGIC
) {
146 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
147 "ntdb_check: Bad hash chain magic %llu",
148 (long long)rec_magic(&rec
));
151 if (rec_data_length(&rec
) != sizeof(struct ntdb_chain
)) {
152 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
154 " Bad hash chain length %llu vs %zu",
155 (long long)rec_data_length(&rec
),
156 sizeof(struct ntdb_chain
));
158 if (rec_key_length(&rec
) != 0) {
159 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
160 "ntdb_check: Bad hash chain key length %llu",
161 (long long)rec_key_length(&rec
));
163 if (rec_hash(&rec
) != 0) {
164 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
165 "ntdb_check: Bad hash chain hash value %llu",
166 (long long)rec_hash(&rec
));
170 ecode
= check_hash_tree(ntdb
, off
, 0, hash
, 64,
171 used
, num_used
, num_found
, check
, data
);
172 if (ecode
!= NTDB_SUCCESS
) {
176 off
= ntdb_read_off(ntdb
, off
+ offsetof(struct ntdb_chain
, next
));
177 if (NTDB_OFF_IS_ERR(off
)) {
178 return NTDB_OFF_TO_ERR(off
);
183 return check_hash_chain(ntdb
, off
, hash
, used
, num_used
, num_found
,
187 static enum NTDB_ERROR
check_hash_record(struct ntdb_context
*ntdb
,
190 unsigned hprefix_bits
,
194 enum NTDB_ERROR (*check
)(NTDB_DATA
,
199 struct ntdb_used_record rec
;
200 enum NTDB_ERROR ecode
;
202 if (hprefix_bits
>= 64)
203 return check_hash_chain(ntdb
, off
, hprefix
, used
, num_used
,
204 num_found
, check
, data
);
206 ecode
= ntdb_read_convert(ntdb
, off
, &rec
, sizeof(rec
));
207 if (ecode
!= NTDB_SUCCESS
) {
211 if (rec_magic(&rec
) != NTDB_HTABLE_MAGIC
) {
212 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
213 "ntdb_check: Bad hash table magic %llu",
214 (long long)rec_magic(&rec
));
216 if (rec_data_length(&rec
)
217 != sizeof(ntdb_off_t
) << NTDB_SUBLEVEL_HASH_BITS
) {
218 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
220 " Bad hash table length %llu vs %llu",
221 (long long)rec_data_length(&rec
),
222 (long long)sizeof(ntdb_off_t
)
223 << NTDB_SUBLEVEL_HASH_BITS
);
225 if (rec_key_length(&rec
) != 0) {
226 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
227 "ntdb_check: Bad hash table key length %llu",
228 (long long)rec_key_length(&rec
));
230 if (rec_hash(&rec
) != 0) {
231 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
232 "ntdb_check: Bad hash table hash value %llu",
233 (long long)rec_hash(&rec
));
237 return check_hash_tree(ntdb
, off
,
238 NTDB_SUBLEVEL_HASH_BITS
-NTDB_HASH_GROUP_BITS
,
239 hprefix
, hprefix_bits
,
240 used
, num_used
, num_found
, check
, data
);
243 static int off_cmp(const ntdb_off_t
*a
, const ntdb_off_t
*b
)
245 /* Can overflow an int. */
251 static uint64_t get_bits(uint64_t h
, unsigned num
, unsigned *used
)
255 return (h
>> (64 - *used
)) & ((1U << num
) - 1);
258 static enum NTDB_ERROR
check_hash_tree(struct ntdb_context
*ntdb
,
259 ntdb_off_t off
, unsigned int group_bits
,
261 unsigned hprefix_bits
,
265 enum NTDB_ERROR (*check
)(NTDB_DATA
,
270 const ntdb_off_t
*hash
;
271 struct ntdb_used_record rec
;
272 enum NTDB_ERROR ecode
;
274 hash
= ntdb_access_read(ntdb
, off
,
276 << (group_bits
+ NTDB_HASH_GROUP_BITS
),
278 if (NTDB_PTR_IS_ERR(hash
)) {
279 return NTDB_PTR_ERR(hash
);
282 for (g
= 0; g
< (1 << group_bits
); g
++) {
283 const ntdb_off_t
*group
= hash
+ (g
<< NTDB_HASH_GROUP_BITS
);
284 for (b
= 0; b
< (1 << NTDB_HASH_GROUP_BITS
); b
++) {
285 unsigned int bucket
, i
, used_bits
;
291 off
= group
[b
] & NTDB_OFF_MASK
;
292 p
= asearch(&off
, used
, num_used
, off_cmp
);
294 ecode
= ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
296 "ntdb_check: Invalid offset"
301 /* Mark it invalid. */
305 if (hprefix_bits
== 64) {
306 /* Chained entries are unordered. */
307 if (is_subhash(group
[b
])) {
308 ecode
= NTDB_ERR_CORRUPT
;
309 ntdb_logerr(ntdb
, ecode
,
311 "ntdb_check: Invalid chain"
315 h
= hash_record(ntdb
, off
);
317 ecode
= NTDB_ERR_CORRUPT
;
318 ntdb_logerr(ntdb
, ecode
,
320 "check: bad hash chain"
327 ecode
= ntdb_read_convert(ntdb
, off
, &rec
,
329 if (ecode
!= NTDB_SUCCESS
) {
335 if (is_subhash(group
[b
])) {
338 << (group_bits
+ NTDB_HASH_GROUP_BITS
))
339 + g
* (1 << NTDB_HASH_GROUP_BITS
) + b
;
341 ecode
= check_hash_record(ntdb
,
342 group
[b
] & NTDB_OFF_MASK
,
346 + NTDB_HASH_GROUP_BITS
,
347 used
, num_used
, num_found
,
349 if (ecode
!= NTDB_SUCCESS
) {
356 /* Does it belong here at all? */
357 h
= hash_record(ntdb
, off
);
359 if (get_bits(h
, hprefix_bits
, &used_bits
) != hprefix
361 ecode
= ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
363 "check: bad hash placement"
370 /* Does it belong in this group? */
371 if (get_bits(h
, group_bits
, &used_bits
) != g
) {
372 ecode
= ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
374 "check: bad group %llu"
380 /* Are bucket bits correct? */
381 bucket
= group
[b
] & NTDB_OFF_HASH_GROUP_MASK
;
382 if (get_bits(h
, NTDB_HASH_GROUP_BITS
, &used_bits
)
384 used_bits
-= NTDB_HASH_GROUP_BITS
;
385 ecode
= ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
387 "check: bad bucket %u vs %u",
388 (unsigned)get_bits(h
,
389 NTDB_HASH_GROUP_BITS
,
395 /* There must not be any zero entries between
396 * the bucket it belongs in and this one! */
399 i
= (i
+ 1) % (1 << NTDB_HASH_GROUP_BITS
)) {
401 ecode
= NTDB_ERR_CORRUPT
;
402 ntdb_logerr(ntdb
, ecode
,
404 "check: bad group placement"
411 ecode
= ntdb_read_convert(ntdb
, off
, &rec
, sizeof(rec
));
412 if (ecode
!= NTDB_SUCCESS
) {
416 /* Bottom bits must match header. */
417 if ((h
& ((1 << 11)-1)) != rec_hash(&rec
)) {
418 ecode
= ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
420 "ntdb_check: Bad hash magic"
422 " (0x%llx vs 0x%llx)",
425 (long long)rec_hash(&rec
));
432 const unsigned char *kptr
;
434 kptr
= ntdb_access_read(ntdb
,
437 + rec_data_length(&rec
),
439 if (NTDB_PTR_IS_ERR(kptr
)) {
440 ecode
= NTDB_PTR_ERR(kptr
);
444 k
= ntdb_mkdata(kptr
, rec_key_length(&rec
));
445 d
= ntdb_mkdata(kptr
+ k
.dsize
,
446 rec_data_length(&rec
));
447 ecode
= check(k
, d
, data
);
448 ntdb_access_release(ntdb
, kptr
);
449 if (ecode
!= NTDB_SUCCESS
) {
455 ntdb_access_release(ntdb
, hash
);
459 ntdb_access_release(ntdb
, hash
);
463 static enum NTDB_ERROR
check_hash(struct ntdb_context
*ntdb
,
465 size_t num_used
, size_t num_other_used
,
466 enum NTDB_ERROR (*check
)(NTDB_DATA
, NTDB_DATA
, void *),
469 /* Free tables and capabilities also show up as used. */
470 size_t num_found
= num_other_used
;
471 enum NTDB_ERROR ecode
;
473 ecode
= check_hash_tree(ntdb
, offsetof(struct ntdb_header
, hashtable
),
474 NTDB_TOPLEVEL_HASH_BITS
-NTDB_HASH_GROUP_BITS
,
475 0, 0, used
, num_used
, &num_found
,
477 if (ecode
== NTDB_SUCCESS
) {
478 if (num_found
!= num_used
) {
479 ecode
= ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
480 "ntdb_check: Not all entries"
487 static enum NTDB_ERROR
check_free(struct ntdb_context
*ntdb
,
489 const struct ntdb_free_record
*frec
,
490 ntdb_off_t prev
, unsigned int ftable
,
493 enum NTDB_ERROR ecode
;
495 if (frec_magic(frec
) != NTDB_FREE_MAGIC
) {
496 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
497 "ntdb_check: offset %llu bad magic 0x%llx",
499 (long long)frec
->magic_and_prev
);
501 if (frec_ftable(frec
) != ftable
) {
502 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
503 "ntdb_check: offset %llu bad freetable %u",
504 (long long)off
, frec_ftable(frec
));
508 ecode
= ntdb
->io
->oob(ntdb
, off
,
510 + sizeof(struct ntdb_used_record
),
512 if (ecode
!= NTDB_SUCCESS
) {
515 if (size_to_bucket(frec_len(frec
)) != bucket
) {
516 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
517 "ntdb_check: offset %llu in wrong bucket"
520 bucket
, size_to_bucket(frec_len(frec
)));
522 if (prev
&& prev
!= frec_prev(frec
)) {
523 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
524 "ntdb_check: offset %llu bad prev"
527 (long long)prev
, (long long)frec_len(frec
));
532 static enum NTDB_ERROR
check_free_table(struct ntdb_context
*ntdb
,
533 ntdb_off_t ftable_off
,
539 struct ntdb_freetable ft
;
542 enum NTDB_ERROR ecode
;
544 ecode
= ntdb_read_convert(ntdb
, ftable_off
, &ft
, sizeof(ft
));
545 if (ecode
!= NTDB_SUCCESS
) {
549 if (rec_magic(&ft
.hdr
) != NTDB_FTABLE_MAGIC
550 || rec_key_length(&ft
.hdr
) != 0
551 || rec_data_length(&ft
.hdr
) != sizeof(ft
) - sizeof(ft
.hdr
)
552 || rec_hash(&ft
.hdr
) != 0) {
553 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
554 "ntdb_check: Invalid header on free table");
557 for (i
= 0; i
< NTDB_FREE_BUCKETS
; i
++) {
558 ntdb_off_t off
, prev
= 0, *p
, first
= 0;
559 struct ntdb_free_record f
;
561 h
= bucket_off(ftable_off
, i
);
562 for (off
= ntdb_read_off(ntdb
, h
); off
; off
= f
.next
) {
563 if (NTDB_OFF_IS_ERR(off
)) {
564 return NTDB_OFF_TO_ERR(off
);
567 off
&= NTDB_OFF_MASK
;
570 ecode
= ntdb_read_convert(ntdb
, off
, &f
, sizeof(f
));
571 if (ecode
!= NTDB_SUCCESS
) {
574 ecode
= check_free(ntdb
, off
, &f
, prev
, ftable_num
, i
);
575 if (ecode
!= NTDB_SUCCESS
) {
579 /* FIXME: Check hash bits */
580 p
= asearch(&off
, fr
, num_free
, off_cmp
);
582 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
584 "ntdb_check: Invalid offset"
585 " %llu in free table",
588 /* Mark it invalid. */
595 /* Now we can check first back pointer. */
596 ecode
= ntdb_read_convert(ntdb
, first
, &f
, sizeof(f
));
597 if (ecode
!= NTDB_SUCCESS
) {
600 ecode
= check_free(ntdb
, first
, &f
, prev
, ftable_num
, i
);
601 if (ecode
!= NTDB_SUCCESS
) {
609 /* Slow, but should be very rare. */
610 ntdb_off_t
dead_space(struct ntdb_context
*ntdb
, ntdb_off_t off
)
613 enum NTDB_ERROR ecode
;
615 for (len
= 0; off
+ len
< ntdb
->file
->map_size
; len
++) {
617 ecode
= ntdb
->io
->tread(ntdb
, off
, &c
, 1);
618 if (ecode
!= NTDB_SUCCESS
) {
619 return NTDB_ERR_TO_OFF(ecode
);
621 if (c
!= 0 && c
!= 0x43)
627 static enum NTDB_ERROR
check_linear(struct ntdb_context
*ntdb
,
628 ntdb_off_t
**used
, size_t *num_used
,
629 ntdb_off_t
**fr
, size_t *num_free
,
630 uint64_t features
, ntdb_off_t recovery
)
634 enum NTDB_ERROR ecode
;
635 bool found_recovery
= false;
637 for (off
= sizeof(struct ntdb_header
);
638 off
< ntdb
->file
->map_size
;
641 struct ntdb_used_record u
;
642 struct ntdb_free_record f
;
643 struct ntdb_recovery_record r
;
645 /* r is larger: only get that if we need to. */
646 ecode
= ntdb_read_convert(ntdb
, off
, &rec
, sizeof(rec
.f
));
647 if (ecode
!= NTDB_SUCCESS
) {
651 /* If we crash after ftruncate, we can get zeroes or fill. */
652 if (rec
.r
.magic
== NTDB_RECOVERY_INVALID_MAGIC
653 || rec
.r
.magic
== 0x4343434343434343ULL
) {
654 ecode
= ntdb_read_convert(ntdb
, off
, &rec
, sizeof(rec
.r
));
655 if (ecode
!= NTDB_SUCCESS
) {
658 if (recovery
== off
) {
659 found_recovery
= true;
660 len
= sizeof(rec
.r
) + rec
.r
.max_len
;
662 len
= dead_space(ntdb
, off
);
663 if (NTDB_OFF_IS_ERR(len
)) {
664 return NTDB_OFF_TO_ERR(len
);
666 if (len
< sizeof(rec
.r
)) {
667 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
669 "ntdb_check: invalid"
670 " dead space at %zu",
674 ntdb_logerr(ntdb
, NTDB_SUCCESS
, NTDB_LOG_WARNING
,
675 "Dead space at %zu-%zu (of %zu)",
676 (size_t)off
, (size_t)(off
+ len
),
677 (size_t)ntdb
->file
->map_size
);
679 } else if (rec
.r
.magic
== NTDB_RECOVERY_MAGIC
) {
680 ecode
= ntdb_read_convert(ntdb
, off
, &rec
, sizeof(rec
.r
));
681 if (ecode
!= NTDB_SUCCESS
) {
684 if (recovery
!= off
) {
685 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
687 "ntdb_check: unexpected"
688 " recovery record at offset"
692 if (rec
.r
.len
> rec
.r
.max_len
) {
693 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
695 "ntdb_check: invalid recovery"
699 if (rec
.r
.eof
> ntdb
->file
->map_size
) {
700 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
702 "ntdb_check: invalid old EOF"
703 " %zu", (size_t)rec
.r
.eof
);
705 found_recovery
= true;
706 len
= sizeof(rec
.r
) + rec
.r
.max_len
;
707 } else if (frec_magic(&rec
.f
) == NTDB_FREE_MAGIC
) {
708 len
= sizeof(rec
.u
) + frec_len(&rec
.f
);
709 if (off
+ len
> ntdb
->file
->map_size
) {
710 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
712 "ntdb_check: free overlength"
713 " %llu at offset %llu",
717 /* This record should be in free lists. */
718 if (frec_ftable(&rec
.f
) != NTDB_FTABLE_NONE
719 && !append(ntdb
, fr
, num_free
, off
)) {
720 return ntdb_logerr(ntdb
, NTDB_ERR_OOM
,
722 "ntdb_check: tracking %zu'th"
723 " free record.", *num_free
);
725 } else if (rec_magic(&rec
.u
) == NTDB_USED_MAGIC
726 || rec_magic(&rec
.u
) == NTDB_CHAIN_MAGIC
727 || rec_magic(&rec
.u
) == NTDB_HTABLE_MAGIC
728 || rec_magic(&rec
.u
) == NTDB_FTABLE_MAGIC
729 || rec_magic(&rec
.u
) == NTDB_CAP_MAGIC
) {
730 uint64_t klen
, dlen
, extra
;
732 /* This record is used! */
733 if (!append(ntdb
, used
, num_used
, off
)) {
734 return ntdb_logerr(ntdb
, NTDB_ERR_OOM
,
736 "ntdb_check: tracking %zu'th"
737 " used record.", *num_used
);
740 klen
= rec_key_length(&rec
.u
);
741 dlen
= rec_data_length(&rec
.u
);
742 extra
= rec_extra_padding(&rec
.u
);
744 len
= sizeof(rec
.u
) + klen
+ dlen
+ extra
;
745 if (off
+ len
> ntdb
->file
->map_size
) {
746 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
748 "ntdb_check: used overlength"
749 " %llu at offset %llu",
754 if (len
< sizeof(rec
.f
)) {
755 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
757 "ntdb_check: too short record"
763 /* Check that records have correct 0 at end (but may
765 if (extra
&& !features
766 && rec_magic(&rec
.u
) != NTDB_CAP_MAGIC
) {
769 p
= ntdb_access_read(ntdb
, off
+ sizeof(rec
.u
)
770 + klen
+ dlen
, 1, false);
771 if (NTDB_PTR_IS_ERR(p
))
772 return NTDB_PTR_ERR(p
);
774 ntdb_access_release(ntdb
, p
);
777 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
786 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
,
788 "ntdb_check: Bad magic 0x%llx"
790 (long long)rec_magic(&rec
.u
),
795 /* We must have found recovery area if there was one. */
796 if (recovery
!= 0 && !found_recovery
) {
797 return ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
798 "ntdb_check: expected a recovery area at %zu",
805 _PUBLIC_
enum NTDB_ERROR
ntdb_check_(struct ntdb_context
*ntdb
,
806 enum NTDB_ERROR (*check
)(NTDB_DATA
, NTDB_DATA
, void *),
809 ntdb_off_t
*fr
= NULL
, *used
= NULL
, ft
, recovery
;
810 size_t num_free
= 0, num_used
= 0, num_found
= 0, num_ftables
= 0,
811 num_capabilities
= 0;
813 enum NTDB_ERROR ecode
;
815 if (ntdb
->flags
& NTDB_CANT_CHECK
) {
816 return ntdb_logerr(ntdb
, NTDB_SUCCESS
, NTDB_LOG_WARNING
,
817 "ntdb_check: database has unknown capability,"
821 ecode
= ntdb_allrecord_lock(ntdb
, F_RDLCK
, NTDB_LOCK_WAIT
, false);
822 if (ecode
!= NTDB_SUCCESS
) {
826 ecode
= ntdb_lock_expand(ntdb
, F_RDLCK
);
827 if (ecode
!= NTDB_SUCCESS
) {
828 ntdb_allrecord_unlock(ntdb
, F_RDLCK
);
832 ecode
= check_header(ntdb
, &recovery
, &features
, &num_capabilities
);
833 if (ecode
!= NTDB_SUCCESS
)
836 /* First we do a linear scan, checking all records. */
837 ecode
= check_linear(ntdb
, &used
, &num_used
, &fr
, &num_free
, features
,
839 if (ecode
!= NTDB_SUCCESS
)
842 for (ft
= first_ftable(ntdb
); ft
; ft
= next_ftable(ntdb
, ft
)) {
843 if (NTDB_OFF_IS_ERR(ft
)) {
844 ecode
= NTDB_OFF_TO_ERR(ft
);
847 ecode
= check_free_table(ntdb
, ft
, num_ftables
, fr
, num_free
,
849 if (ecode
!= NTDB_SUCCESS
)
854 /* FIXME: Check key uniqueness? */
855 ecode
= check_hash(ntdb
, used
, num_used
, num_ftables
+ num_capabilities
,
857 if (ecode
!= NTDB_SUCCESS
)
860 if (num_found
!= num_free
) {
861 ecode
= ntdb_logerr(ntdb
, NTDB_ERR_CORRUPT
, NTDB_LOG_ERROR
,
862 "ntdb_check: Not all entries are in"
867 ntdb_allrecord_unlock(ntdb
, F_RDLCK
);
868 ntdb_unlock_expand(ntdb
, F_RDLCK
);
869 ntdb
->free_fn(fr
, ntdb
->alloc_data
);
870 ntdb
->free_fn(used
, ntdb
->alloc_data
);