2 Unix SMB/CIFS implementation.
4 trivial database library
6 Copyright (C) Andrew Tridgell 1999-2005
7 Copyright (C) Paul `Rusty' Russell 2000
8 Copyright (C) Jeremy Allison 2000-2003
10 ** NOTE! The following LGPL license applies to the tdb
11 ** library. This does NOT imply that all of Samba is released
14 This library is free software; you can redistribute it and/or
15 modify it under the terms of the GNU Lesser General Public
16 License as published by the Free Software Foundation; either
17 version 3 of the License, or (at your option) any later version.
19 This library is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 Lesser General Public License for more details.
24 You should have received a copy of the GNU Lesser General Public
25 License along with this library; if not, see <http://www.gnu.org/licenses/>.
28 #include "tdb_private.h"
30 /* read a freelist record and check for simple errors */
31 int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct tdb_record *rec)
33 if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
36 if (rec->magic == TDB_MAGIC) {
37 /* this happens when a app is showdown while deleting a record - we should
38 not completely fail when this happens */
39 TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read non-free magic 0x%x at offset=%u - fixing\n",
41 rec->magic = TDB_FREE_MAGIC;
42 if (tdb_rec_write(tdb, off, rec) == -1)
46 if (rec->magic != TDB_FREE_MAGIC) {
47 /* Ensure ecode is set for log fn. */
48 tdb->ecode = TDB_ERR_CORRUPT;
49 TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read bad magic 0x%x at offset=%u\n",
53 if (tdb->methods->tdb_oob(tdb, rec->next, sizeof(*rec), 0) != 0)
58 /* update a record tailer (must hold allocation lock) */
59 static int update_tailer(struct tdb_context *tdb, tdb_off_t offset,
60 const struct tdb_record *rec)
64 /* Offset of tailer from record header */
65 totalsize = sizeof(*rec) + rec->rec_len;
66 return tdb_ofs_write(tdb, offset + totalsize - sizeof(tdb_off_t),
71 * Read the record directly on the left.
72 * Fail if there is no record on the left.
74 static int read_record_on_left(struct tdb_context *tdb, tdb_off_t rec_ptr,
76 struct tdb_record *left_r)
80 struct tdb_record left_rec;
83 left_ptr = rec_ptr - sizeof(tdb_off_t);
85 if (left_ptr <= TDB_DATA_START(tdb->hash_size)) {
86 /* no record on the left */
90 /* Read in tailer and jump back to header */
91 ret = tdb_ofs_read(tdb, left_ptr, &left_size);
93 TDB_LOG((tdb, TDB_DEBUG_FATAL,
94 "tdb_free: left offset read failed at %u\n", left_ptr));
98 /* it could be uninitialised data */
99 if (left_size == 0 || left_size == TDB_PAD_U32) {
103 if (left_size > rec_ptr) {
107 left_ptr = rec_ptr - left_size;
109 if (left_ptr < TDB_DATA_START(tdb->hash_size)) {
113 /* Now read in the left record */
114 ret = tdb->methods->tdb_read(tdb, left_ptr, &left_rec,
115 sizeof(left_rec), DOCONV());
117 TDB_LOG((tdb, TDB_DEBUG_FATAL,
118 "tdb_free: left read failed at %u (%u)\n",
119 left_ptr, left_size));
130 * Merge new freelist record with the direct left neighbour.
131 * This assumes that left_rec represents the record
132 * directly to the left of right_rec and that this is
135 static int merge_with_left_record(struct tdb_context *tdb,
137 struct tdb_record *left_rec,
138 struct tdb_record *right_rec)
142 left_rec->rec_len += sizeof(*right_rec) + right_rec->rec_len;
144 ret = tdb_rec_write(tdb, left_ptr, left_rec);
146 TDB_LOG((tdb, TDB_DEBUG_FATAL,
147 "merge_with_left_record: update_left failed at %u\n",
152 ret = update_tailer(tdb, left_ptr, left_rec);
154 TDB_LOG((tdb, TDB_DEBUG_FATAL,
155 "merge_with_left_record: update_tailer failed at %u\n",
164 * Check whether the record left of a given freelist record is
165 * also a freelist record, and if so, merge the two records.
169 * 0 if left was not a free record
170 * 1 if left was free and successfully merged.
172 * The current record is handed in with pointer and fully read record.
174 * The left record pointer and struct can be retrieved as result
177 static int check_merge_with_left_record(struct tdb_context *tdb,
179 struct tdb_record *rec,
181 struct tdb_record *lr)
184 struct tdb_record left_rec;
187 ret = read_record_on_left(tdb, rec_ptr, &left_ptr, &left_rec);
192 if (left_rec.magic != TDB_FREE_MAGIC) {
196 /* It's free - expand to include it. */
197 ret = merge_with_left_record(tdb, left_ptr, &left_rec, rec);
214 * Check whether the record left of a given freelist record is
215 * also a freelist record, and if so, merge the two records.
219 * 0 if left was not a free record
220 * 1 if left was free and successfully merged.
222 * In this variant, the input record is specified just as the pointer
223 * and is read from the database if needed.
225 * next_ptr will contain the original record's next pointer after
226 * successful merging (which will be lost after merging), so that
227 * the caller can update the last pointer.
229 static int check_merge_ptr_with_left_record(struct tdb_context *tdb,
234 struct tdb_record rec, left_rec;
237 ret = read_record_on_left(tdb, rec_ptr, &left_ptr, &left_rec);
242 if (left_rec.magic != TDB_FREE_MAGIC) {
246 /* It's free - expand to include it. */
248 ret = tdb->methods->tdb_read(tdb, rec_ptr, &rec,
249 sizeof(rec), DOCONV());
254 ret = merge_with_left_record(tdb, left_ptr, &left_rec, &rec);
259 if (next_ptr != NULL) {
260 *next_ptr = rec.next;
267 * Add an element into the freelist.
269 * We merge the new record into the left record if it is also a
270 * free record, but not with the right one. This makes the
271 * operation O(1) instead of O(n): merging with the right record
272 * requires a traverse of the freelist to find the previous
273 * record in the free list.
275 * This prevents db traverses from being O(n^2) after a lot of deletes.
277 int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec)
281 /* Allocation and tailer lock */
282 if (tdb_lock(tdb, -1, F_WRLCK) != 0)
285 /* set an initial tailer, so if we fail we don't leave a bogus record */
286 if (update_tailer(tdb, offset, rec) != 0) {
287 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed!\n"));
291 ret = check_merge_with_left_record(tdb, offset, rec, NULL, NULL);
300 /* Nothing to merge, prepend to free list */
302 rec->magic = TDB_FREE_MAGIC;
304 if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
305 tdb_rec_write(tdb, offset, rec) == -1 ||
306 tdb_ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
307 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free record write failed at offset=%u\n", offset));
312 /* And we're done. */
313 tdb_unlock(tdb, -1, F_WRLCK);
317 tdb_unlock(tdb, -1, F_WRLCK);
324 the core of tdb_allocate - called when we have decided which
325 free list entry to use
327 Note that we try to allocate by grabbing data from the end of an existing record,
328 not the beginning. This is so the left merge in a free is more likely to be
329 able to free up the record without fragmentation
331 static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb,
332 tdb_len_t length, tdb_off_t rec_ptr,
333 struct tdb_record *rec, tdb_off_t last_ptr)
335 #define MIN_REC_SIZE (sizeof(struct tdb_record) + sizeof(tdb_off_t) + 8)
337 if (rec->rec_len < length + MIN_REC_SIZE) {
338 /* we have to grab the whole record */
340 /* unlink it from the previous record */
341 if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) {
345 /* mark it not free */
346 rec->magic = TDB_MAGIC;
347 if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
353 /* we're going to just shorten the existing record */
354 rec->rec_len -= (length + sizeof(*rec));
355 if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
358 if (update_tailer(tdb, rec_ptr, rec) == -1) {
362 /* and setup the new record */
363 rec_ptr += sizeof(*rec) + rec->rec_len;
365 memset(rec, '\0', sizeof(*rec));
366 rec->rec_len = length;
367 rec->magic = TDB_MAGIC;
369 if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
373 if (update_tailer(tdb, rec_ptr, rec) == -1) {
380 /* allocate some space from the free list. The offset returned points
381 to a unconnected tdb_record within the database with room for at
382 least length bytes of total data
384 0 is returned if the space could not be allocated
386 static tdb_off_t tdb_allocate_from_freelist(
387 struct tdb_context *tdb, tdb_len_t length, struct tdb_record *rec)
389 tdb_off_t rec_ptr, last_ptr, newrec_ptr;
390 struct tdb_chainwalk_ctx chainwalk;
393 tdb_off_t rec_ptr, last_ptr;
396 float multiplier = 1.0;
397 bool merge_created_candidate;
399 /* over-allocate to reduce fragmentation */
402 /* Extra bytes required for tailer */
403 length += sizeof(tdb_off_t);
404 length = TDB_ALIGN(length, TDB_ALIGNMENT);
407 merge_created_candidate = false;
408 last_ptr = FREELIST_TOP;
410 /* read in the freelist top */
411 if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
415 tdb_chainwalk_init(&chainwalk, rec_ptr);
418 bestfit.last_ptr = 0;
422 this is a best fit allocation strategy. Originally we used
423 a first fit strategy, but it suffered from massive fragmentation
424 issues when faced with a slowly increasing record size.
429 struct tdb_record left_rec;
431 if (tdb_rec_free_read(tdb, rec_ptr, rec) == -1) {
435 ret = check_merge_with_left_record(tdb, rec_ptr, rec,
436 &left_ptr, &left_rec);
443 ret = tdb_ofs_write(tdb, last_ptr, &rec->next);
449 * We have merged the current record into the left
450 * neighbour. So our traverse of the freelist will
451 * skip it and consider the next record in the chain.
453 * But the enlarged left neighbour may be a candidate.
454 * If it is, we can not directly use it, though.
455 * The only thing we can do and have to do here is to
456 * update the current best fit size in the chain if the
457 * current best fit is the left record. (By that we may
458 * worsen the best fit we already had, bit this is not a
461 * If the current best fit is not the left record,
462 * all we can do is remember the fact that a merge
463 * created a new candidate so that we can trigger
464 * a second walk of the freelist if at the end of
465 * the first walk we have not found any fit.
466 * This way we can avoid expanding the database.
469 if (bestfit.rec_ptr == left_ptr) {
470 bestfit.rec_len = left_rec.rec_len;
473 if (left_rec.rec_len > length) {
474 merge_created_candidate = true;
482 if (rec->rec_len >= length) {
483 if (bestfit.rec_ptr == 0 ||
484 rec->rec_len < bestfit.rec_len) {
485 bestfit.rec_len = rec->rec_len;
486 bestfit.rec_ptr = rec_ptr;
487 bestfit.last_ptr = last_ptr;
491 /* move to the next record */
497 ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
503 /* if we've found a record that is big enough, then
504 stop searching if its also not too big. The
505 definition of 'too big' changes as we scan
507 if (bestfit.rec_len > 0 &&
508 bestfit.rec_len < length * multiplier) {
512 /* this multiplier means we only extremely rarely
513 search more than 50 or so records. At 50 records we
514 accept records up to 11 times larger than what we
519 if (bestfit.rec_ptr != 0) {
520 if (tdb_rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
524 newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr,
525 rec, bestfit.last_ptr);
529 if (merge_created_candidate) {
533 /* we didn't find enough space. See if we can expand the
534 database and if we can then try again */
535 if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
541 static bool tdb_alloc_dead(
542 struct tdb_context *tdb, int hash, tdb_len_t length,
543 tdb_off_t *rec_ptr, struct tdb_record *rec)
547 *rec_ptr = tdb_find_dead(tdb, hash, rec, length, &last_ptr);
552 * Unlink the record from the hash chain, it's about to be moved into
555 return (tdb_ofs_write(tdb, last_ptr, &rec->next) == 0);
558 static void tdb_purge_dead(struct tdb_context *tdb, uint32_t hash)
560 uint32_t max_dead_records = tdb->max_dead_records;
562 tdb->max_dead_records = 0;
564 tdb_trim_dead(tdb, hash);
566 tdb->max_dead_records = max_dead_records;
570 * Chain "hash" is assumed to be locked
573 tdb_off_t tdb_allocate(struct tdb_context *tdb, int hash, tdb_len_t length,
574 struct tdb_record *rec)
579 if (tdb->max_dead_records == 0) {
581 * No dead records to expect anywhere. Do the blocking
582 * freelist lock without trying to steal from others
584 goto blocking_freelist_allocate;
588 * The following loop tries to get the freelist lock nonblocking. If
589 * it gets the lock, allocate from there. If the freelist is busy,
590 * instead of waiting we try to steal dead records from other hash
593 * Be aware that we do nonblocking locks on the other hash chains as
594 * well and fail gracefully. This way we avoid deadlocks (we block two
595 * hash chains, something which is pretty bad normally)
598 for (i=0; i<tdb->hash_size; i++) {
602 list = BUCKET(hash+i);
604 if (tdb_lock_nonblock(tdb, list, F_WRLCK) == 0) {
607 got_dead = tdb_alloc_dead(tdb, list, length, &ret, rec);
608 tdb_unlock(tdb, list, F_WRLCK);
615 if (tdb_lock_nonblock(tdb, -1, F_WRLCK) == 0) {
617 * Under the freelist lock take the chance to give
618 * back our dead records.
620 tdb_purge_dead(tdb, hash);
622 ret = tdb_allocate_from_freelist(tdb, length, rec);
623 tdb_unlock(tdb, -1, F_WRLCK);
628 blocking_freelist_allocate:
630 if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
634 * Dead records can happen even if max_dead_records==0, they
635 * are older than the max_dead_records concept: They happen if
636 * tdb_delete happens concurrently with a traverse.
638 tdb_purge_dead(tdb, hash);
639 ret = tdb_allocate_from_freelist(tdb, length, rec);
640 tdb_unlock(tdb, -1, F_WRLCK);
645 * Merge adjacent records in the freelist.
647 static int tdb_freelist_merge_adjacent(struct tdb_context *tdb,
648 int *count_records, int *count_merged)
655 ret = tdb_lock(tdb, -1, F_RDLCK);
661 while (tdb_ofs_read(tdb, cur, &next) == 0 && next != 0) {
666 ret = check_merge_ptr_with_left_record(tdb, next, &next2);
673 * now let cur->next point to next2 instead of next
676 ret = tdb_ofs_write(tdb, cur, &next2);
688 if (count_records != NULL) {
689 *count_records = count;
692 if (count_merged != NULL) {
693 *count_merged = merged;
699 tdb_unlock(tdb, -1, F_RDLCK);
704 * return the size of the freelist - no merging done
706 static int tdb_freelist_size_no_merge(struct tdb_context *tdb)
711 if (tdb_lock(tdb, -1, F_RDLCK) == -1) {
716 while (tdb_ofs_read(tdb, ptr, &ptr) == 0 && ptr != 0) {
720 tdb_unlock(tdb, -1, F_RDLCK);
725 * return the size of the freelist - used to decide if we should repack
727 * As a side effect, adjacent records are merged unless the
728 * database is read-only, in order to reduce the fragmentation
731 _PUBLIC_ int tdb_freelist_size(struct tdb_context *tdb)
736 if (tdb->read_only) {
737 count = tdb_freelist_size_no_merge(tdb);
740 ret = tdb_freelist_merge_adjacent(tdb, &count, NULL);