+++ /dev/null
- /*
- Trivial Database 2: hash 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
- version 3 of the License, or (at your option) any later version.
-
- This library is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public
- License along with this library; if not, see <http://www.gnu.org/licenses/>.
-*/
-#include "private.h"
-#include <ccan/hash/hash.h>
-
-/* Default hash function. */
-uint32_t ntdb_jenkins_hash(const void *key, size_t length, uint32_t seed,
- void *unused)
-{
- return hash_stable((const unsigned char *)key, length, seed);
-}
-
-uint32_t ntdb_hash(struct ntdb_context *ntdb, const void *ptr, size_t len)
-{
- return ntdb->hash_fn(ptr, len, ntdb->hash_seed, ntdb->hash_data);
-}
-
-static ntdb_bool_err key_matches(struct ntdb_context *ntdb,
- const struct ntdb_used_record *rec,
- ntdb_off_t off,
- const NTDB_DATA *key,
- const char **rptr)
-{
- ntdb_bool_err ret = false;
- const char *rkey;
-
- if (rec_key_length(rec) != key->dsize) {
- ntdb->stats.compare_wrong_keylen++;
- return ret;
- }
-
- rkey = ntdb_access_read(ntdb, off + sizeof(*rec),
- key->dsize + rec_data_length(rec), false);
- if (NTDB_PTR_IS_ERR(rkey)) {
- return (ntdb_bool_err)NTDB_PTR_ERR(rkey);
- }
- if (memcmp(rkey, key->dptr, key->dsize) == 0) {
- if (rptr) {
- *rptr = rkey;
- } else {
- ntdb_access_release(ntdb, rkey);
- }
- return true;
- }
- ntdb->stats.compare_wrong_keycmp++;
- ntdb_access_release(ntdb, rkey);
- return ret;
-}
-
-/* Does entry match? */
-static ntdb_bool_err match(struct ntdb_context *ntdb,
- uint32_t hash,
- const NTDB_DATA *key,
- ntdb_off_t val,
- struct ntdb_used_record *rec,
- const char **rptr)
-{
- ntdb_off_t off;
- enum NTDB_ERROR ecode;
-
- ntdb->stats.compares++;
-
- /* Top bits of offset == next bits of hash. */
- if (bits_from(hash, ntdb->hash_bits, NTDB_OFF_UPPER_STEAL)
- != bits_from(val, 64-NTDB_OFF_UPPER_STEAL, NTDB_OFF_UPPER_STEAL)) {
- ntdb->stats.compare_wrong_offsetbits++;
- return false;
- }
-
- off = val & NTDB_OFF_MASK;
- ecode = ntdb_read_convert(ntdb, off, rec, sizeof(*rec));
- if (ecode != NTDB_SUCCESS) {
- return (ntdb_bool_err)ecode;
- }
-
- return key_matches(ntdb, rec, off, key, rptr);
-}
-
-static bool is_chain(ntdb_off_t val)
-{
- return val & (1ULL << NTDB_OFF_CHAIN_BIT);
-}
-
-static ntdb_off_t hbucket_off(ntdb_off_t base, ntdb_len_t idx)
-{
- return base + sizeof(struct ntdb_used_record)
- + idx * sizeof(ntdb_off_t);
-}
-
-/* This is the core routine which searches the hashtable for an entry.
- * On error, no locks are held and -ve is returned.
- * Otherwise, hinfo is filled in.
- * If not found, the return value is 0.
- * If found, the return value is the offset, and *rec is the record. */
-ntdb_off_t find_and_lock(struct ntdb_context *ntdb,
- NTDB_DATA key,
- int ltype,
- struct hash_info *h,
- struct ntdb_used_record *rec,
- const char **rptr)
-{
- ntdb_off_t off, val;
- const ntdb_off_t *arr = NULL;
- ntdb_len_t i;
- bool found_empty;
- enum NTDB_ERROR ecode;
- struct ntdb_used_record chdr;
- ntdb_bool_err berr;
-
- h->h = ntdb_hash(ntdb, key.dptr, key.dsize);
-
- h->table = NTDB_HASH_OFFSET;
- h->table_size = 1 << ntdb->hash_bits;
- h->bucket = bits_from(h->h, 0, ntdb->hash_bits);
- h->old_val = 0;
-
- ecode = ntdb_lock_hash(ntdb, h->bucket, ltype);
- if (ecode != NTDB_SUCCESS) {
- return NTDB_ERR_TO_OFF(ecode);
- }
-
- off = hbucket_off(h->table, h->bucket);
- val = ntdb_read_off(ntdb, off);
- if (NTDB_OFF_IS_ERR(val)) {
- ecode = NTDB_OFF_TO_ERR(val);
- goto fail;
- }
-
- /* Directly in hash table? */
- if (!likely(is_chain(val))) {
- if (val) {
- berr = match(ntdb, h->h, &key, val, rec, rptr);
- if (berr < 0) {
- ecode = NTDB_OFF_TO_ERR(berr);
- goto fail;
- }
- if (berr) {
- return val & NTDB_OFF_MASK;
- }
- /* If you want to insert here, make a chain. */
- h->old_val = val;
- }
- return 0;
- }
-
- /* Nope? Iterate through chain. */
- h->table = val & NTDB_OFF_MASK;
-
- ecode = ntdb_read_convert(ntdb, h->table, &chdr, sizeof(chdr));
- if (ecode != NTDB_SUCCESS) {
- goto fail;
- }
-
- if (rec_magic(&chdr) != NTDB_CHAIN_MAGIC) {
- ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT,
- NTDB_LOG_ERROR,
- "find_and_lock:"
- " corrupt record %#x at %llu",
- rec_magic(&chdr), (long long)off);
- goto fail;
- }
-
- h->table_size = rec_data_length(&chdr) / sizeof(ntdb_off_t);
-
- arr = ntdb_access_read(ntdb, hbucket_off(h->table, 0),
- rec_data_length(&chdr), true);
- if (NTDB_PTR_IS_ERR(arr)) {
- ecode = NTDB_PTR_ERR(arr);
- goto fail;
- }
-
- found_empty = false;
- for (i = 0; i < h->table_size; i++) {
- if (arr[i] == 0) {
- if (!found_empty) {
- h->bucket = i;
- found_empty = true;
- }
- } else {
- berr = match(ntdb, h->h, &key, arr[i], rec, rptr);
- if (berr < 0) {
- ecode = NTDB_OFF_TO_ERR(berr);
- ntdb_access_release(ntdb, arr);
- goto fail;
- }
- if (berr) {
- /* We found it! */
- h->bucket = i;
- off = arr[i] & NTDB_OFF_MASK;
- ntdb_access_release(ntdb, arr);
- return off;
- }
- }
- }
- if (!found_empty) {
- /* Set to any non-zero value */
- h->old_val = 1;
- h->bucket = i;
- }
-
- ntdb_access_release(ntdb, arr);
- return 0;
-
-fail:
- ntdb_unlock_hash(ntdb, h->bucket, ltype);
- return NTDB_ERR_TO_OFF(ecode);
-}
-
-static ntdb_off_t encode_offset(const struct ntdb_context *ntdb,
- ntdb_off_t new_off, uint32_t hash)
-{
- ntdb_off_t extra;
-
- assert((new_off & (1ULL << NTDB_OFF_CHAIN_BIT)) == 0);
- assert((new_off >> (64 - NTDB_OFF_UPPER_STEAL)) == 0);
- /* We pack extra hash bits into the upper bits of the offset. */
- extra = bits_from(hash, ntdb->hash_bits, NTDB_OFF_UPPER_STEAL);
- extra <<= (64 - NTDB_OFF_UPPER_STEAL);
-
- return new_off | extra;
-}
-
-/* Simply overwrite the hash entry we found before. */
-enum NTDB_ERROR replace_in_hash(struct ntdb_context *ntdb,
- const struct hash_info *h,
- ntdb_off_t new_off)
-{
- return ntdb_write_off(ntdb, hbucket_off(h->table, h->bucket),
- encode_offset(ntdb, new_off, h->h));
-}
-
-enum NTDB_ERROR delete_from_hash(struct ntdb_context *ntdb,
- const struct hash_info *h)
-{
- return ntdb_write_off(ntdb, hbucket_off(h->table, h->bucket), 0);
-}
-
-
-enum NTDB_ERROR add_to_hash(struct ntdb_context *ntdb,
- const struct hash_info *h,
- ntdb_off_t new_off)
-{
- enum NTDB_ERROR ecode;
- ntdb_off_t chain;
- struct ntdb_used_record chdr;
- const ntdb_off_t *old;
- ntdb_off_t *new;
-
- /* We hit an empty bucket during search? That's where it goes. */
- if (!h->old_val) {
- return replace_in_hash(ntdb, h, new_off);
- }
-
- /* Full at top-level? Create a 2-element chain. */
- if (h->table == NTDB_HASH_OFFSET) {
- ntdb_off_t pair[2];
-
- /* One element is old value, the other is the new value. */
- pair[0] = h->old_val;
- pair[1] = encode_offset(ntdb, new_off, h->h);
-
- chain = alloc(ntdb, 0, sizeof(pair), NTDB_CHAIN_MAGIC, true);
- if (NTDB_OFF_IS_ERR(chain)) {
- return NTDB_OFF_TO_ERR(chain);
- }
- ecode = ntdb_write_convert(ntdb,
- chain
- + sizeof(struct ntdb_used_record),
- pair, sizeof(pair));
- if (ecode == NTDB_SUCCESS) {
- ecode = ntdb_write_off(ntdb,
- hbucket_off(h->table, h->bucket),
- chain
- | (1ULL << NTDB_OFF_CHAIN_BIT));
- }
- return ecode;
- }
-
- /* Full bucket. Expand. */
- ecode = ntdb_read_convert(ntdb, h->table, &chdr, sizeof(chdr));
- if (ecode != NTDB_SUCCESS) {
- return ecode;
- }
-
- if (rec_extra_padding(&chdr) >= sizeof(new_off)) {
- /* Expand in place. */
- uint64_t dlen = rec_data_length(&chdr);
-
- ecode = set_header(ntdb, &chdr, NTDB_CHAIN_MAGIC, 0,
- dlen + sizeof(new_off),
- dlen + rec_extra_padding(&chdr));
-
- if (ecode != NTDB_SUCCESS) {
- return ecode;
- }
- /* find_and_lock set up h to point to last bucket. */
- ecode = replace_in_hash(ntdb, h, new_off);
- if (ecode != NTDB_SUCCESS) {
- return ecode;
- }
- ecode = ntdb_write_convert(ntdb, h->table, &chdr, sizeof(chdr));
- if (ecode != NTDB_SUCCESS) {
- return ecode;
- }
- /* For futureproofing, we always make the first byte of padding
- * a zero. */
- if (rec_extra_padding(&chdr)) {
- ecode = ntdb->io->twrite(ntdb, h->table + sizeof(chdr)
- + dlen + sizeof(new_off),
- "", 1);
- }
- return ecode;
- }
-
- /* We need to reallocate the chain. */
- chain = alloc(ntdb, 0, (h->table_size + 1) * sizeof(ntdb_off_t),
- NTDB_CHAIN_MAGIC, true);
- if (NTDB_OFF_IS_ERR(chain)) {
- return NTDB_OFF_TO_ERR(chain);
- }
-
- /* Map both and copy across old buckets. */
- old = ntdb_access_read(ntdb, hbucket_off(h->table, 0),
- h->table_size*sizeof(ntdb_off_t), true);
- if (NTDB_PTR_IS_ERR(old)) {
- return NTDB_PTR_ERR(old);
- }
- new = ntdb_access_write(ntdb, hbucket_off(chain, 0),
- (h->table_size + 1)*sizeof(ntdb_off_t), true);
- if (NTDB_PTR_IS_ERR(new)) {
- ntdb_access_release(ntdb, old);
- return NTDB_PTR_ERR(new);
- }
-
- memcpy(new, old, h->bucket * sizeof(ntdb_off_t));
- new[h->bucket] = encode_offset(ntdb, new_off, h->h);
- ntdb_access_release(ntdb, old);
-
- ecode = ntdb_access_commit(ntdb, new);
- if (ecode != NTDB_SUCCESS) {
- return ecode;
- }
-
- /* Free the old chain. */
- ecode = add_free_record(ntdb, h->table,
- sizeof(struct ntdb_used_record)
- + rec_data_length(&chdr)
- + rec_extra_padding(&chdr),
- NTDB_LOCK_WAIT, true);
-
- /* Replace top-level to point to new chain */
- return ntdb_write_off(ntdb,
- hbucket_off(NTDB_HASH_OFFSET,
- bits_from(h->h, 0, ntdb->hash_bits)),
- chain | (1ULL << NTDB_OFF_CHAIN_BIT));
-}
-
-/* Traverse support: returns offset of record, or 0 or -ve error. */
-static ntdb_off_t iterate_chain(struct ntdb_context *ntdb,
- ntdb_off_t val,
- struct hash_info *h)
-{
- ntdb_off_t i;
- enum NTDB_ERROR ecode;
- struct ntdb_used_record chdr;
-
- /* First load up chain header. */
- h->table = val & NTDB_OFF_MASK;
- ecode = ntdb_read_convert(ntdb, h->table, &chdr, sizeof(chdr));
- if (ecode != NTDB_SUCCESS) {
- return ecode;
- }
-
- if (rec_magic(&chdr) != NTDB_CHAIN_MAGIC) {
- return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT,
- NTDB_LOG_ERROR,
- "get_table:"
- " corrupt record %#x at %llu",
- rec_magic(&chdr),
- (long long)h->table);
- }
-
- /* Chain length is implied by data length. */
- h->table_size = rec_data_length(&chdr) / sizeof(ntdb_off_t);
-
- i = ntdb_find_nonzero_off(ntdb, hbucket_off(h->table, 0), h->bucket,
- h->table_size);
- if (NTDB_OFF_IS_ERR(i)) {
- return i;
- }
-
- if (i != h->table_size) {
- /* Return to next bucket. */
- h->bucket = i + 1;
- val = ntdb_read_off(ntdb, hbucket_off(h->table, i));
- if (NTDB_OFF_IS_ERR(val)) {
- return val;
- }
- return val & NTDB_OFF_MASK;
- }
-
- /* Go back up to hash table. */
- h->table = NTDB_HASH_OFFSET;
- h->table_size = 1 << ntdb->hash_bits;
- h->bucket = bits_from(h->h, 0, ntdb->hash_bits) + 1;
- return 0;
-}
-
-/* Keeps hash locked unless returns 0 or error. */
-static ntdb_off_t lock_and_iterate_hash(struct ntdb_context *ntdb,
- struct hash_info *h)
-{
- ntdb_off_t val, i;
- enum NTDB_ERROR ecode;
-
- if (h->table != NTDB_HASH_OFFSET) {
- /* We're in a chain. */
- i = bits_from(h->h, 0, ntdb->hash_bits);
- ecode = ntdb_lock_hash(ntdb, i, F_RDLCK);
- if (ecode != NTDB_SUCCESS) {
- return NTDB_ERR_TO_OFF(ecode);
- }
-
- /* We dropped lock, bucket might have moved! */
- val = ntdb_read_off(ntdb, hbucket_off(NTDB_HASH_OFFSET, i));
- if (NTDB_OFF_IS_ERR(val)) {
- goto unlock;
- }
-
- /* We don't remove chains: there should still be one there! */
- if (!val || !is_chain(val)) {
- ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT,
- NTDB_LOG_ERROR,
- "iterate_hash:"
- " vanished hchain %llu at %llu",
- (long long)val,
- (long long)i);
- val = NTDB_ERR_TO_OFF(ecode);
- goto unlock;
- }
-
- /* Find next bucket in the chain. */
- val = iterate_chain(ntdb, val, h);
- if (NTDB_OFF_IS_ERR(val)) {
- goto unlock;
- }
- if (val != 0) {
- return val;
- }
- ntdb_unlock_hash(ntdb, i, F_RDLCK);
-
- /* OK, we've reset h back to top level. */
- }
-
- /* We do this unlocked, then re-check. */
- for (i = ntdb_find_nonzero_off(ntdb, hbucket_off(h->table, 0),
- h->bucket, h->table_size);
- i != h->table_size;
- i = ntdb_find_nonzero_off(ntdb, hbucket_off(h->table, 0),
- i+1, h->table_size)) {
- ecode = ntdb_lock_hash(ntdb, i, F_RDLCK);
- if (ecode != NTDB_SUCCESS) {
- return NTDB_ERR_TO_OFF(ecode);
- }
-
- val = ntdb_read_off(ntdb, hbucket_off(h->table, i));
- if (NTDB_OFF_IS_ERR(val)) {
- goto unlock;
- }
-
- /* Lost race, and it's empty? */
- if (!val) {
- ntdb->stats.traverse_val_vanished++;
- ntdb_unlock_hash(ntdb, i, F_RDLCK);
- continue;
- }
-
- if (!is_chain(val)) {
- /* So caller knows what lock to free. */
- h->h = i;
- /* Return to next bucket. */
- h->bucket = i + 1;
- val &= NTDB_OFF_MASK;
- return val;
- }
-
- /* Start at beginning of chain */
- h->bucket = 0;
- h->h = i;
-
- val = iterate_chain(ntdb, val, h);
- if (NTDB_OFF_IS_ERR(val)) {
- goto unlock;
- }
- if (val != 0) {
- return val;
- }
-
- /* Otherwise, bucket has been set to i+1 */
- ntdb_unlock_hash(ntdb, i, F_RDLCK);
- }
- return 0;
-
-unlock:
- ntdb_unlock_hash(ntdb, i, F_RDLCK);
- return val;
-}
-
-/* Return success if we find something, NTDB_ERR_NOEXIST if none. */
-enum NTDB_ERROR next_in_hash(struct ntdb_context *ntdb,
- struct hash_info *h,
- NTDB_DATA *kbuf, size_t *dlen)
-{
- ntdb_off_t off;
- struct ntdb_used_record rec;
- enum NTDB_ERROR ecode;
-
- off = lock_and_iterate_hash(ntdb, h);
-
- if (NTDB_OFF_IS_ERR(off)) {
- return NTDB_OFF_TO_ERR(off);
- } else if (off == 0) {
- return NTDB_ERR_NOEXIST;
- }
-
- /* The hash for this key is still locked. */
- ecode = ntdb_read_convert(ntdb, off, &rec, sizeof(rec));
- if (ecode != NTDB_SUCCESS) {
- goto unlock;
- }
- if (rec_magic(&rec) != NTDB_USED_MAGIC) {
- ecode = ntdb_logerr(ntdb, NTDB_ERR_CORRUPT,
- NTDB_LOG_ERROR,
- "next_in_hash:"
- " corrupt record at %llu",
- (long long)off);
- goto unlock;
- }
-
- kbuf->dsize = rec_key_length(&rec);
-
- /* They want data as well? */
- if (dlen) {
- *dlen = rec_data_length(&rec);
- kbuf->dptr = ntdb_alloc_read(ntdb, off + sizeof(rec),
- kbuf->dsize + *dlen);
- } else {
- kbuf->dptr = ntdb_alloc_read(ntdb, off + sizeof(rec),
- kbuf->dsize);
- }
- if (NTDB_PTR_IS_ERR(kbuf->dptr)) {
- ecode = NTDB_PTR_ERR(kbuf->dptr);
- goto unlock;
- }
- ecode = NTDB_SUCCESS;
-
-unlock:
- ntdb_unlock_hash(ntdb, bits_from(h->h, 0, ntdb->hash_bits), F_RDLCK);
- return ecode;
-
-}
-
-enum NTDB_ERROR first_in_hash(struct ntdb_context *ntdb,
- struct hash_info *h,
- NTDB_DATA *kbuf, size_t *dlen)
-{
- h->table = NTDB_HASH_OFFSET;
- h->table_size = 1 << ntdb->hash_bits;
- h->bucket = 0;
-
- return next_in_hash(ntdb, h, kbuf, dlen);
-}
-
-/* Even if the entry isn't in this hash bucket, you'd have to lock this
- * bucket to find it. */
-static enum NTDB_ERROR chainlock(struct ntdb_context *ntdb,
- const NTDB_DATA *key, int ltype)
-{
- uint32_t h = ntdb_hash(ntdb, key->dptr, key->dsize);
-
- return ntdb_lock_hash(ntdb, bits_from(h, 0, ntdb->hash_bits), ltype);
-}
-
-/* lock/unlock one hash chain. This is meant to be used to reduce
- contention - it cannot guarantee how many records will be locked */
-_PUBLIC_ enum NTDB_ERROR ntdb_chainlock(struct ntdb_context *ntdb, NTDB_DATA key)
-{
- return chainlock(ntdb, &key, F_WRLCK);
-}
-
-_PUBLIC_ void ntdb_chainunlock(struct ntdb_context *ntdb, NTDB_DATA key)
-{
- uint32_t h = ntdb_hash(ntdb, key.dptr, key.dsize);
-
- ntdb_unlock_hash(ntdb, bits_from(h, 0, ntdb->hash_bits), F_WRLCK);
-}
-
-_PUBLIC_ enum NTDB_ERROR ntdb_chainlock_read(struct ntdb_context *ntdb,
- NTDB_DATA key)
-{
- return chainlock(ntdb, &key, F_RDLCK);
-}
-
-_PUBLIC_ void ntdb_chainunlock_read(struct ntdb_context *ntdb, NTDB_DATA key)
-{
- uint32_t h = ntdb_hash(ntdb, key.dptr, key.dsize);
-
- ntdb_unlock_hash(ntdb, bits_from(h, 0, ntdb->hash_bits), F_RDLCK);
-}
git.samba.org / kai / samba-autobuild / .git / blobdiff