X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb2%2Ffree.c;h=7ede24616efc78df4e16eda260ace518bbd88755;hp=5d1bd3c6d1360d7c2a1b3498a58e3d7443ec0d18;hb=40bab4d5df030f84a63d9c6cb1348d8f27442a0a;hpb=2491b65a6d10cd6ca1a3e05bf535eb0180047922 diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c index 5d1bd3c6..7ede2461 100644 --- a/ccan/tdb2/free.c +++ b/ccan/tdb2/free.c @@ -1,7 +1,7 @@ - /* + /* Trivial Database 2: free list/block handling Copyright (C) Rusty Russell 2010 - + This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either @@ -59,7 +59,7 @@ tdb_off_t next_ftable(struct tdb_context *tdb, tdb_off_t ftable) return tdb_read_off(tdb, ftable + offsetof(struct tdb_freetable,next)); } -int tdb_ftable_init(struct tdb_context *tdb) +enum TDB_ERROR tdb_ftable_init(struct tdb_context *tdb) { /* Use reservoir sampling algorithm to select a free list at random. */ unsigned int rnd, max = 0, count = 0; @@ -69,8 +69,9 @@ int tdb_ftable_init(struct tdb_context *tdb) tdb->ftable = 0; while (off) { - if (off == TDB_OFF_ERR) - return -1; + if (TDB_OFF_IS_ERR(off)) { + return off; + } rnd = random(); if (rnd >= max) { @@ -82,7 +83,7 @@ int tdb_ftable_init(struct tdb_context *tdb) off = next_ftable(tdb, off); count++; } - return 0; + return TDB_SUCCESS; } /* Offset of a given bucket. */ @@ -92,7 +93,7 @@ tdb_off_t bucket_off(tdb_off_t ftable_off, unsigned bucket) + bucket * sizeof(tdb_off_t); } -/* Returns free_buckets + 1, or list number to search. */ +/* Returns free_buckets + 1, or list number to search, or -ve error. */ static tdb_off_t find_free_head(struct tdb_context *tdb, tdb_off_t ftable_off, tdb_off_t bucket) @@ -103,11 +104,12 @@ static tdb_off_t find_free_head(struct tdb_context *tdb, } /* Remove from free bucket. */ -static int remove_from_list(struct tdb_context *tdb, - tdb_off_t b_off, tdb_off_t r_off, - const struct tdb_free_record *r) +static enum TDB_ERROR remove_from_list(struct tdb_context *tdb, + tdb_off_t b_off, tdb_off_t r_off, + const struct tdb_free_record *r) { tdb_off_t off; + enum TDB_ERROR ecode; /* Front of list? */ if (frec_prev(r) == 0) { @@ -116,47 +118,50 @@ static int remove_from_list(struct tdb_context *tdb, off = frec_prev(r) + offsetof(struct tdb_free_record, next); } -#ifdef DEBUG +#ifdef CCAN_TDB2_DEBUG if (tdb_read_off(tdb, off) != r_off) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_FATAL, - "remove_from_list: %llu bad prev in list %llu", - (long long)r_off, (long long)b_off); - return -1; + return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "remove_from_list:" + " %llu bad prev in list %llu", + (long long)r_off, (long long)b_off); } #endif /* r->prev->next = r->next */ - if (tdb_write_off(tdb, off, r->next)) { - return -1; + ecode = tdb_write_off(tdb, off, r->next); + if (ecode != TDB_SUCCESS) { + return ecode; } if (r->next != 0) { off = r->next + offsetof(struct tdb_free_record,magic_and_prev); /* r->next->prev = r->prev */ -#ifdef DEBUG +#ifdef CCAN_TDB2_DEBUG if (tdb_read_off(tdb, off) & TDB_OFF_MASK != r_off) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_FATAL, - "remove_from_list: %llu bad list %llu", - (long long)r_off, (long long)b_off); - return -1; + return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "remove_from_list:" + " %llu bad list %llu", + (long long)r_off, (long long)b_off); } #endif - if (tdb_write_off(tdb, off, r->magic_and_prev)) { - return -1; + ecode = tdb_write_off(tdb, off, r->magic_and_prev); + if (ecode != TDB_SUCCESS) { + return ecode; } } - return 0; + return TDB_SUCCESS; } /* Enqueue in this free bucket. */ -static int enqueue_in_free(struct tdb_context *tdb, - tdb_off_t b_off, - tdb_off_t off, - tdb_len_t len) +static enum TDB_ERROR enqueue_in_free(struct tdb_context *tdb, + tdb_off_t b_off, + tdb_off_t off, + tdb_len_t len) { struct tdb_free_record new; + enum TDB_ERROR ecode; uint64_t magic = (TDB_FREE_MAGIC << (64 - TDB_OFF_UPPER_STEAL)); /* We only need to set ftable_and_len; rest is set in enqueue_in_free */ @@ -167,55 +172,62 @@ static int enqueue_in_free(struct tdb_context *tdb, /* new->next = head. */ new.next = tdb_read_off(tdb, b_off); - if (new.next == TDB_OFF_ERR) - return -1; + if (TDB_OFF_IS_ERR(new.next)) { + return new.next; + } if (new.next) { -#ifdef DEBUG +#ifdef CCAN_TDB2_DEBUG if (tdb_read_off(tdb, new.next + offsetof(struct tdb_free_record, magic_and_prev)) != magic) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_FATAL, - "enqueue_in_free: %llu bad head" - " prev %llu", - (long long)new.next, (long long)b_off); - return -1; + return tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "enqueue_in_free: %llu bad head" + " prev %llu", + (long long)new.next, + (long long)b_off); } #endif /* next->prev = new. */ - if (tdb_write_off(tdb, new.next - + offsetof(struct tdb_free_record, - magic_and_prev), - off | magic) != 0) - return -1; + ecode = tdb_write_off(tdb, new.next + + offsetof(struct tdb_free_record, + magic_and_prev), + off | magic); + if (ecode != TDB_SUCCESS) { + return ecode; + } } /* head = new */ - if (tdb_write_off(tdb, b_off, off) != 0) - return -1; + ecode = tdb_write_off(tdb, b_off, off); + if (ecode != TDB_SUCCESS) { + return ecode; + } return tdb_write_convert(tdb, off, &new, sizeof(new)); } /* List need not be locked. */ -int add_free_record(struct tdb_context *tdb, - tdb_off_t off, tdb_len_t len_with_header) +enum TDB_ERROR add_free_record(struct tdb_context *tdb, + tdb_off_t off, tdb_len_t len_with_header) { tdb_off_t b_off; tdb_len_t len; - int ret; + enum TDB_ERROR ecode; assert(len_with_header >= sizeof(struct tdb_free_record)); len = len_with_header - sizeof(struct tdb_used_record); b_off = bucket_off(tdb->ftable_off, size_to_bucket(len)); - if (tdb_lock_free_bucket(tdb, b_off, TDB_LOCK_WAIT) != 0) - return -1; + ecode = tdb_lock_free_bucket(tdb, b_off, TDB_LOCK_WAIT); + if (ecode != TDB_SUCCESS) { + return ecode; + } - ret = enqueue_in_free(tdb, b_off, off, len); + ecode = enqueue_in_free(tdb, b_off, off, len); tdb_unlock_free_bucket(tdb, b_off); - return ret; + return ecode; } static size_t adjust_size(size_t keylen, size_t datalen) @@ -254,29 +266,37 @@ static tdb_off_t ftable_offset(struct tdb_context *tdb, unsigned int ftable) return tdb->ftable_off; off = first_ftable(tdb); - for (i = 0; i < ftable; i++) + for (i = 0; i < ftable; i++) { + if (TDB_OFF_IS_ERR(off)) { + break; + } off = next_ftable(tdb, off); + } return off; } /* Note: we unlock the current bucket if we coalesce or fail. */ -static int coalesce(struct tdb_context *tdb, - tdb_off_t off, tdb_off_t b_off, tdb_len_t data_len) +static tdb_bool_err coalesce(struct tdb_context *tdb, + tdb_off_t off, tdb_off_t b_off, + tdb_len_t data_len) { tdb_off_t end; struct tdb_free_record rec; + enum TDB_ERROR ecode; add_stat(tdb, alloc_coalesce_tried, 1); end = off + sizeof(struct tdb_used_record) + data_len; - while (end < tdb->map_size) { + while (end < tdb->file->map_size) { const struct tdb_free_record *r; tdb_off_t nb_off; unsigned ftable, bucket; r = tdb_access_read(tdb, end, sizeof(*r), true); - if (!r) + if (TDB_PTR_IS_ERR(r)) { + ecode = TDB_PTR_ERR(r); goto err; + } if (frec_magic(r) != TDB_FREE_MAGIC || frec_ftable(r) == TDB_FTABLE_NONE) { @@ -286,17 +306,25 @@ static int coalesce(struct tdb_context *tdb, ftable = frec_ftable(r); bucket = size_to_bucket(frec_len(r)); - nb_off = bucket_off(ftable_offset(tdb, ftable), bucket); + nb_off = ftable_offset(tdb, ftable); + if (TDB_OFF_IS_ERR(nb_off)) { + tdb_access_release(tdb, r); + ecode = nb_off; + goto err; + } + nb_off = bucket_off(nb_off, bucket); tdb_access_release(tdb, r); /* We may be violating lock order here, so best effort. */ - if (tdb_lock_free_bucket(tdb, nb_off, TDB_LOCK_NOWAIT) == -1) { + if (tdb_lock_free_bucket(tdb, nb_off, TDB_LOCK_NOWAIT) + != TDB_SUCCESS) { add_stat(tdb, alloc_coalesce_lockfail, 1); break; } /* Now we have lock, re-check. */ - if (tdb_read_convert(tdb, end, &rec, sizeof(rec))) { + ecode = tdb_read_convert(tdb, end, &rec, sizeof(rec)); + if (ecode != TDB_SUCCESS) { tdb_unlock_free_bucket(tdb, nb_off); goto err; } @@ -314,7 +342,8 @@ static int coalesce(struct tdb_context *tdb, break; } - if (remove_from_list(tdb, nb_off, end, &rec) == -1) { + ecode = remove_from_list(tdb, nb_off, end, &rec); + if (ecode != TDB_SUCCESS) { tdb_unlock_free_bucket(tdb, nb_off); goto err; } @@ -326,42 +355,50 @@ static int coalesce(struct tdb_context *tdb, /* Didn't find any adjacent free? */ if (end == off + sizeof(struct tdb_used_record) + data_len) - return 0; + return false; /* OK, expand initial record */ - if (tdb_read_convert(tdb, off, &rec, sizeof(rec))) + ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec)); + if (ecode != TDB_SUCCESS) { goto err; + } if (frec_len(&rec) != data_len) { - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_FATAL, - "coalesce: expected data len %zu not %zu", - (size_t)data_len, (size_t)frec_len(&rec)); + ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "coalesce: expected data len %zu not %zu", + (size_t)data_len, (size_t)frec_len(&rec)); goto err; } - if (remove_from_list(tdb, b_off, off, &rec) == -1) + ecode = remove_from_list(tdb, b_off, off, &rec); + if (ecode != TDB_SUCCESS) { goto err; + } /* We have to drop this to avoid deadlocks, so make sure record * doesn't get coalesced by someone else! */ rec.ftable_and_len = (TDB_FTABLE_NONE << (64 - TDB_OFF_UPPER_STEAL)) | (end - off - sizeof(struct tdb_used_record)); - if (tdb_write_off(tdb, off + offsetof(struct tdb_free_record, - ftable_and_len), - rec.ftable_and_len) != 0) + ecode = tdb_write_off(tdb, off + offsetof(struct tdb_free_record, + ftable_and_len), + rec.ftable_and_len); + if (ecode != TDB_SUCCESS) { goto err; + } add_stat(tdb, alloc_coalesce_succeeded, 1); tdb_unlock_free_bucket(tdb, b_off); - if (add_free_record(tdb, off, end - off) == -1) - return -1; - return 1; + ecode = add_free_record(tdb, off, end - off); + if (ecode != TDB_SUCCESS) { + return ecode; + } + return true; err: /* To unify error paths, we *always* unlock bucket on error. */ tdb_unlock_free_bucket(tdb, b_off); - return -1; + return ecode; } /* We need size bytes to put our key and data in. */ @@ -377,6 +414,7 @@ static tdb_off_t lock_and_alloc(struct tdb_context *tdb, struct tdb_free_record best = { 0 }; double multiplier; size_t size = adjust_size(keylen, datalen); + enum TDB_ERROR ecode; add_stat(tdb, allocs, 1); again: @@ -384,8 +422,9 @@ again: /* FIXME: Try non-blocking wait first, to measure contention. */ /* Lock this bucket. */ - if (tdb_lock_free_bucket(tdb, b_off, TDB_LOCK_WAIT) == -1) { - return TDB_OFF_ERR; + ecode = tdb_lock_free_bucket(tdb, b_off, TDB_LOCK_WAIT); + if (ecode != TDB_SUCCESS) { + return ecode; } best.ftable_and_len = -1ULL; @@ -400,23 +439,30 @@ again: /* Walk the list to see if any are large enough, getting less fussy * as we go. */ off = tdb_read_off(tdb, b_off); - if (unlikely(off == TDB_OFF_ERR)) + if (TDB_OFF_IS_ERR(off)) { + ecode = off; goto unlock_err; + } while (off) { const struct tdb_free_record *r; tdb_len_t len; tdb_off_t next; + int coal; r = tdb_access_read(tdb, off, sizeof(*r), true); - if (!r) + if (TDB_PTR_IS_ERR(r)) { + ecode = TDB_PTR_ERR(r); goto unlock_err; + } if (frec_magic(r) != TDB_FREE_MAGIC) { + ecode = tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_LOG_ERROR, + "lock_and_alloc:" + " %llu non-free 0x%llx", + (long long)off, + (long long)r->magic_and_prev); tdb_access_release(tdb, r); - tdb_logerr(tdb, TDB_ERR_CORRUPT, TDB_DEBUG_FATAL, - "lock_and_alloc: %llu non-free 0x%llx", - (long long)off, (long long)r->magic_and_prev); goto unlock_err; } @@ -437,14 +483,15 @@ again: tdb_access_release(tdb, r); /* Since we're going slow anyway, try coalescing here. */ - switch (coalesce(tdb, off, b_off, len)) { - case -1: - /* This has already unlocked on error. */ - return -1; - case 1: + coal = coalesce(tdb, off, b_off, len); + if (coal == 1) { /* This has unlocked list, restart. */ goto again; } + if (coal < 0) { + /* This has already unlocked on error. */ + return coal; + } off = next; } @@ -454,8 +501,10 @@ again: size_t leftover; /* We're happy with this size: take it. */ - if (remove_from_list(tdb, b_off, best_off, &best) != 0) + ecode = remove_from_list(tdb, b_off, best_off, &best); + if (ecode != TDB_SUCCESS) { goto unlock_err; + } leftover = record_leftover(keylen, datalen, want_extra, frec_len(&best)); @@ -463,22 +512,37 @@ again: assert(keylen + datalen + leftover <= frec_len(&best)); /* We need to mark non-free before we drop lock, otherwise * coalesce() could try to merge it! */ - if (set_header(tdb, &rec, magic, keylen, datalen, - frec_len(&best) - leftover, hashlow) != 0) + ecode = set_header(tdb, &rec, magic, keylen, datalen, + frec_len(&best) - leftover, hashlow); + if (ecode != TDB_SUCCESS) { goto unlock_err; + } - if (tdb_write_convert(tdb, best_off, &rec, sizeof(rec)) != 0) + ecode = tdb_write_convert(tdb, best_off, &rec, sizeof(rec)); + if (ecode != TDB_SUCCESS) { goto unlock_err; + } + + /* For futureproofing, we put a 0 in any unused space. */ + if (rec_extra_padding(&rec)) { + ecode = tdb->methods->twrite(tdb, best_off + sizeof(rec) + + keylen + datalen, "", 1); + if (ecode != TDB_SUCCESS) { + goto unlock_err; + } + } /* Bucket of leftover will be <= current bucket, so nested * locking is allowed. */ if (leftover) { add_stat(tdb, alloc_leftover, 1); - if (add_free_record(tdb, - best_off + sizeof(rec) - + frec_len(&best) - leftover, - leftover)) - best_off = TDB_OFF_ERR; + ecode = add_free_record(tdb, + best_off + sizeof(rec) + + frec_len(&best) - leftover, + leftover); + if (ecode != TDB_SUCCESS) { + best_off = ecode; + } } tdb_unlock_free_bucket(tdb, b_off); @@ -490,16 +554,16 @@ again: unlock_err: tdb_unlock_free_bucket(tdb, b_off); - return TDB_OFF_ERR; + return ecode; } -/* Get a free block from current free list, or 0 if none. */ +/* Get a free block from current free list, or 0 if none, -ve on error. */ static tdb_off_t get_free(struct tdb_context *tdb, size_t keylen, size_t datalen, bool want_extra, unsigned magic, unsigned hashlow) { tdb_off_t off, ftable_off; - unsigned start_b, b, ftable; + tdb_off_t start_b, b, ftable; bool wrapped = false; /* If they are growing, add 50% to get to higher bucket. */ @@ -520,8 +584,8 @@ static tdb_off_t get_free(struct tdb_context *tdb, off = lock_and_alloc(tdb, ftable_off, b, keylen, datalen, want_extra, magic, hashlow); - if (off == TDB_OFF_ERR) - return TDB_OFF_ERR; + if (TDB_OFF_IS_ERR(off)) + return off; if (off != 0) { if (b == start_b) add_stat(tdb, alloc_bucket_exact, 1); @@ -535,13 +599,23 @@ static tdb_off_t get_free(struct tdb_context *tdb, /* Didn't work. Try next bucket. */ } + if (TDB_OFF_IS_ERR(b)) { + return b; + } + /* Hmm, try next table. */ ftable_off = next_ftable(tdb, ftable_off); + if (TDB_OFF_IS_ERR(ftable_off)) { + return ftable_off; + } ftable++; if (ftable_off == 0) { wrapped = true; ftable_off = first_ftable(tdb); + if (TDB_OFF_IS_ERR(ftable_off)) { + return ftable_off; + } ftable = 0; } } @@ -549,10 +623,10 @@ static tdb_off_t get_free(struct tdb_context *tdb, return 0; } -int set_header(struct tdb_context *tdb, - struct tdb_used_record *rec, - unsigned magic, uint64_t keylen, uint64_t datalen, - uint64_t actuallen, unsigned hashlow) +enum TDB_ERROR set_header(struct tdb_context *tdb, + struct tdb_used_record *rec, + unsigned magic, uint64_t keylen, uint64_t datalen, + uint64_t actuallen, unsigned hashlow) { uint64_t keybits = (fls64(keylen) + 1) / 2; @@ -567,55 +641,57 @@ int set_header(struct tdb_context *tdb, if (rec_key_length(rec) != keylen || rec_data_length(rec) != datalen || rec_extra_padding(rec) != actuallen - (keylen + datalen)) { - tdb_logerr(tdb, TDB_ERR_IO, TDB_DEBUG_ERROR, - "Could not encode k=%llu,d=%llu,a=%llu", - (long long)keylen, (long long)datalen, - (long long)actuallen); - return -1; + return tdb_logerr(tdb, TDB_ERR_IO, TDB_LOG_ERROR, + "Could not encode k=%llu,d=%llu,a=%llu", + (long long)keylen, (long long)datalen, + (long long)actuallen); } - return 0; + return TDB_SUCCESS; } /* Expand the database. */ -static int tdb_expand(struct tdb_context *tdb, tdb_len_t size) +static enum TDB_ERROR tdb_expand(struct tdb_context *tdb, tdb_len_t size) { uint64_t old_size; tdb_len_t wanted; + enum TDB_ERROR ecode; /* We need room for the record header too. */ wanted = sizeof(struct tdb_used_record) + size; /* Need to hold a hash lock to expand DB: transactions rely on it. */ if (!(tdb->flags & TDB_NOLOCK) - && !tdb->allrecord_lock.count && !tdb_has_hash_locks(tdb)) { - tdb_logerr(tdb, TDB_ERR_LOCK, TDB_DEBUG_ERROR, - "tdb_expand: must hold lock during expand"); - return -1; + && !tdb->file->allrecord_lock.count && !tdb_has_hash_locks(tdb)) { + return tdb_logerr(tdb, TDB_ERR_LOCK, TDB_LOG_ERROR, + "tdb_expand: must hold lock during expand"); } /* always make room for at least 100 more records, and at least 25% more space. */ - if (size * TDB_EXTENSION_FACTOR > tdb->map_size / 4) + if (size * TDB_EXTENSION_FACTOR > tdb->file->map_size / 4) wanted = size * TDB_EXTENSION_FACTOR; else - wanted = tdb->map_size / 4; + wanted = tdb->file->map_size / 4; wanted = adjust_size(0, wanted); /* Only one person can expand file at a time. */ - if (tdb_lock_expand(tdb, F_WRLCK) != 0) - return -1; + ecode = tdb_lock_expand(tdb, F_WRLCK); + if (ecode != TDB_SUCCESS) { + return ecode; + } /* Someone else may have expanded the file, so retry. */ - old_size = tdb->map_size; - tdb->methods->oob(tdb, tdb->map_size + 1, true); - if (tdb->map_size != old_size) { + old_size = tdb->file->map_size; + tdb->methods->oob(tdb, tdb->file->map_size + 1, true); + if (tdb->file->map_size != old_size) { tdb_unlock_expand(tdb, F_WRLCK); - return 0; + return TDB_SUCCESS; } - if (tdb->methods->expand_file(tdb, wanted) == -1) { + ecode = tdb->methods->expand_file(tdb, wanted); + if (ecode != TDB_SUCCESS) { tdb_unlock_expand(tdb, F_WRLCK); - return -1; + return ecode; } /* We need to drop this lock before adding free record. */ @@ -635,12 +711,15 @@ tdb_off_t alloc(struct tdb_context *tdb, size_t keylen, size_t datalen, assert(!tdb->direct_access); for (;;) { + enum TDB_ERROR ecode; off = get_free(tdb, keylen, datalen, growing, magic, hash); if (likely(off != 0)) break; - if (tdb_expand(tdb, adjust_size(keylen, datalen))) - return TDB_OFF_ERR; + ecode = tdb_expand(tdb, adjust_size(keylen, datalen)); + if (ecode != TDB_SUCCESS) { + return ecode; + } } return off;