-
-#if 0 /* FIXME: Check other bits. */
- unsigned int bits, bitmask, hoffextra;
- /* Bottom three bits show how many extra hash bits. */
- bits = (off & ((1 << TDB_EXTRA_HASHBITS_NUM) - 1)) + 1;
- bitmask = (1 << bits)-1;
- hoffextra = ((off >> TDB_EXTRA_HASHBITS_NUM) & bitmask);
- uint64_t hextra = hash >> tdb->header.v.hash_bits;
- if ((hextra & bitmask) != hoffextra)
- return TDB_OFF_ERR;
- off &= ~...;
-#endif
-
- if (tdb_read_convert(tdb, off, rec, sizeof(*rec)) == -1)
- return TDB_OFF_ERR;
-
- /* FIXME: check extra bits in header! */
- keylen = rec_key_length(rec);
- if (keylen != key->dsize)
- return TDB_OFF_ERR;
-
- rkey = tdb_access_read(tdb, off + sizeof(*rec), keylen, false);
- if (!rkey)
- return TDB_OFF_ERR;
- if (memcmp(rkey, key->dptr, keylen) != 0)
- off = TDB_OFF_ERR;
- tdb_access_release(tdb, rkey);
- return off;
-}
-
-/* FIXME: Optimize? */
-static void unlock_lists(struct tdb_context *tdb,
- tdb_off_t list, tdb_len_t num,
- int ltype)
-{
- tdb_off_t i;
-
- for (i = list; i < list + num; i++)
- tdb_unlock_list(tdb, i, ltype);
-}
-
-/* FIXME: Optimize? */
-static int lock_lists(struct tdb_context *tdb,
- tdb_off_t list, tdb_len_t num,
- int ltype)
-{
- tdb_off_t i;
-
- for (i = list; i < list + num; i++) {
- if (tdb_lock_list(tdb, i, ltype, TDB_LOCK_WAIT) != 0) {
- unlock_lists(tdb, list, i - list, ltype);
- return -1;
- }
- }
- return 0;
-}
-
-/* We lock hashes up to the next empty offset. We already hold the
- * lock on the start bucket, but we may need to release and re-grab
- * it. If we fail, we hold no locks at all! */
-static tdb_len_t relock_hash_to_zero(struct tdb_context *tdb,
- tdb_off_t start, int ltype)
-{
- tdb_len_t num, len, pre_locks;
-
-again:
- num = 1ULL << tdb->header.v.hash_bits;
- len = tdb_find_zero_off(tdb, hash_off(tdb, start), num - start);
- if (unlikely(len == num - start)) {
- /* We hit the end of the hash range. Drop lock: we have
- to lock start of hash first. */
- tdb_unlock_list(tdb, start, ltype);
- /* Grab something, so header is stable. */
- if (tdb_lock_list(tdb, 0, ltype, TDB_LOCK_WAIT))
- return TDB_OFF_ERR;
- len = tdb_find_zero_off(tdb, hash_off(tdb, 0), num);
- if (lock_lists(tdb, 1, len, ltype) == -1) {
- tdb_unlock_list(tdb, 0, ltype);
- return TDB_OFF_ERR;
- }
- pre_locks = len;
- len = num - start;
- } else {
- /* We already have lock on start. */
- start++;
- pre_locks = 0;
- }
- if (unlikely(lock_lists(tdb, start, len, ltype) == -1)) {
- if (pre_locks)
- unlock_lists(tdb, 0, pre_locks, ltype);
- else
- tdb_unlock_list(tdb, start, ltype);
- return TDB_OFF_ERR;
- }
-
- /* Now, did we lose the race, and it's not zero any more? */
- if (unlikely(tdb_read_off(tdb, hash_off(tdb, pre_locks + len)) != 0)) {
- unlock_lists(tdb, 0, pre_locks, ltype);
- /* Leave the start locked, as expected. */
- unlock_lists(tdb, start + 1, len - 1, ltype);
- goto again;
- }
-
- return pre_locks + len;
-}
-
-/* FIXME: modify, don't rewrite! */
-static int update_rec_hdr(struct tdb_context *tdb,
- tdb_off_t off,
- tdb_len_t keylen,
- tdb_len_t datalen,
- struct tdb_used_record *rec,
- uint64_t h)
-{
- uint64_t room = rec_data_length(rec) + rec_extra_padding(rec);
-
- if (set_header(tdb, rec, keylen, datalen, room - datalen, h))
- return -1;
-
- return tdb_write_convert(tdb, off, rec, sizeof(*rec));
-}
-
-/* If we fail, others will try after us. */
-static void enlarge_hash(struct tdb_context *tdb)
-{
- tdb_off_t newoff, oldoff, i;
- tdb_len_t hlen;
- uint64_t h, num = 1ULL << tdb->header.v.hash_bits;
- struct tdb_used_record pad, *r;
-
- /* FIXME: We should do this without holding locks throughout. */
- if (tdb_allrecord_lock(tdb, F_WRLCK, TDB_LOCK_WAIT, false) == -1)
- return;
-
- /* Someone else enlarged for us? Nothing to do. */
- if ((1ULL << tdb->header.v.hash_bits) != num)
- goto unlock;
-
- /* Allocate our new array. */
- hlen = num * sizeof(tdb_off_t) * 2;
- newoff = alloc(tdb, 0, hlen, 0, false);
- if (unlikely(newoff == TDB_OFF_ERR))
- goto unlock;
- if (unlikely(newoff == 0)) {
- if (tdb_expand(tdb, 0, hlen, false) == -1)
- goto unlock;
- newoff = alloc(tdb, 0, hlen, 0, false);
- if (newoff == TDB_OFF_ERR || newoff == 0)
- goto unlock;
- }
- /* Step over record header! */
- newoff += sizeof(struct tdb_used_record);
-
- /* Starts all zero. */
- if (zero_out(tdb, newoff, hlen) == -1)
- goto unlock;
-
- /* FIXME: If the space before is empty, we know this is in its ideal
- * location. Or steal a bit from the pointer to avoid rehash. */
- for (i = tdb_find_nonzero_off(tdb, hash_off(tdb, 0), num);
- i < num;
- i += tdb_find_nonzero_off(tdb, hash_off(tdb, i), num - i)) {
- tdb_off_t off;
- off = tdb_read_off(tdb, hash_off(tdb, i));
- if (unlikely(off == TDB_OFF_ERR))
- goto unlock;
- if (unlikely(!off)) {
- tdb->ecode = TDB_ERR_CORRUPT;
- tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
- "find_bucket_and_lock: zero hash bucket!\n");
- goto unlock;
- }
- h = hash_record(tdb, off);
- /* FIXME: Encode extra hash bits! */
- if (tdb_write_off(tdb, newoff
- + (h & ((num * 2) - 1)) * sizeof(uint64_t),
- off) == -1)
- goto unlock;
- }
-
- /* Free up old hash. */
- oldoff = tdb->header.v.hash_off - sizeof(*r);
- r = tdb_get(tdb, oldoff, &pad, sizeof(*r));
- if (!r)
- goto unlock;
- add_free_record(tdb, oldoff,
- sizeof(*r)+rec_data_length(r)+rec_extra_padding(r));
-
- /* Now we write the modified header. */
- tdb->header.v.hash_bits++;
- tdb->header.v.hash_off = newoff;
- write_header(tdb);
-unlock:
- tdb_allrecord_unlock(tdb, F_WRLCK);
-}
-
-int tdb_store(struct tdb_context *tdb,
- struct tdb_data key, struct tdb_data dbuf, int flag)
-{
- tdb_off_t new_off, off, old_bucket, start, num_locks = 1;
- struct tdb_used_record rec;
- uint64_t h;
- bool growing = false;
-
- h = tdb_hash(tdb, key.dptr, key.dsize);
-
- /* FIXME: can we avoid locks for some fast paths? */
- start = tdb_lock_list(tdb, h, F_WRLCK, TDB_LOCK_WAIT);
- if (start == TDB_OFF_ERR)
- return -1;
-
- /* Fast path. */
- old_bucket = start;
- off = entry_matches(tdb, start, h, &key, &rec);
- if (unlikely(off == TDB_OFF_ERR)) {
- /* Slow path, need to grab more locks and search. */
- tdb_off_t i;
-
- /* Warning: this may drop the lock! Does that on error. */
- num_locks = relock_hash_to_zero(tdb, start, F_WRLCK);
- if (num_locks == TDB_OFF_ERR)
- return -1;
-
- for (i = start; i < start + num_locks; i++) {
- off = entry_matches(tdb, i, h, &key, &rec);
- /* Empty entry or we found it? */
- if (off == 0 || off != TDB_OFF_ERR) {
- old_bucket = i;
- break;
- }
- }
- if (i == start + num_locks)
- off = 0;