+/**
+ * cfs_hash bucket descriptor, it's normally in stack of caller
+ */
+typedef struct cfs_hash_bd {
+ cfs_hash_bucket_t *bd_bucket; /**< address of bucket */
+ unsigned int bd_offset; /**< offset in bucket */
+} cfs_hash_bd_t;
+
+#define CFS_HASH_NAME_LEN 16 /**< default name length */
+#define CFS_HASH_BIGNAME_LEN 64 /**< bigname for param tree */
+
+#define CFS_HASH_BKT_BITS 3 /**< default bits of bucket */
+#define CFS_HASH_BITS_MAX 30 /**< max bits of bucket */
+#define CFS_HASH_BITS_MIN CFS_HASH_BKT_BITS
+
+/**
+ * common hash attributes.
+ */
+enum cfs_hash_tag {
+ /**
+ * don't need any lock, caller will protect operations with it's
+ * own lock. With this flag:
+ * . CFS_HASH_NO_BKTLOCK, CFS_HASH_RW_BKTLOCK, CFS_HASH_SPIN_BKTLOCK
+ * will be ignored.
+ * . Some functions will be disabled with this flag, i.e:
+ * cfs_hash_for_each_empty, cfs_hash_rehash
+ */
+ CFS_HASH_NO_LOCK = 1 << 0,
+ /** no bucket lock, use one spinlock to protect the whole hash */
+ CFS_HASH_NO_BKTLOCK = 1 << 1,
+ /** rwlock to protect bucket */
+ CFS_HASH_RW_BKTLOCK = 1 << 2,
+ /** spinlcok to protect bucket */
+ CFS_HASH_SPIN_BKTLOCK = 1 << 3,
+ /** always add new item to tail */
+ CFS_HASH_ADD_TAIL = 1 << 4,
+ /** hash-table doesn't have refcount on item */
+ CFS_HASH_NO_ITEMREF = 1 << 5,
+ /** big name for param-tree */
+ CFS_HASH_BIGNAME = 1 << 6,
+ /** track global count */
+ CFS_HASH_COUNTER = 1 << 7,
+ /** rehash item by new key */
+ CFS_HASH_REHASH_KEY = 1 << 8,
+ /** Enable dynamic hash resizing */
+ CFS_HASH_REHASH = 1 << 9,
+ /** can shrink hash-size */
+ CFS_HASH_SHRINK = 1 << 10,
+ /** assert hash is empty on exit */
+ CFS_HASH_ASSERT_EMPTY = 1 << 11,
+ /** record hlist depth */
+ CFS_HASH_DEPTH = 1 << 12,
+ /**
+ * rehash is always scheduled in a different thread, so current
+ * change on hash table is non-blocking
+ */
+ CFS_HASH_NBLK_CHANGE = 1 << 13,
+ /** NB, we typed hs_flags as __u16, please change it
+ * if you need to extend >=16 flags */
+};
+
+/** most used attributes */
+#define CFS_HASH_DEFAULT (CFS_HASH_RW_BKTLOCK | \
+ CFS_HASH_COUNTER | CFS_HASH_REHASH)
+
+/**
+ * cfs_hash is a hash-table implementation for general purpose, it can support:
+ * . two refcount modes
+ * hash-table with & without refcount
+ * . four lock modes
+ * nolock, one-spinlock, rw-bucket-lock, spin-bucket-lock
+ * . general operations
+ * lookup, add(add_tail or add_head), delete
+ * . rehash
+ * grows or shrink
+ * . iteration
+ * locked iteration and unlocked iteration
+ * . bigname
+ * support long name hash
+ * . debug
+ * trace max searching depth
+ *
+ * Rehash:
+ * When the htable grows or shrinks, a separate task (cfs_hash_rehash_worker)
+ * is spawned to handle the rehash in the background, it's possible that other
+ * processes can concurrently perform additions, deletions, and lookups
+ * without being blocked on rehash completion, because rehash will release
+ * the global wrlock for each bucket.
+ *
+ * rehash and iteration can't run at the same time because it's too tricky
+ * to keep both of them safe and correct.
+ * As they are relatively rare operations, so:
+ * . if iteration is in progress while we try to launch rehash, then
+ * it just giveup, iterator will launch rehash at the end.
+ * . if rehash is in progress while we try to iterate the hash table,
+ * then we just wait (shouldn't be very long time), anyway, nobody
+ * should expect iteration of whole hash-table to be non-blocking.
+ *
+ * During rehashing, a (key,object) pair may be in one of two buckets,
+ * depending on whether the worker task has yet to transfer the object
+ * to its new location in the table. Lookups and deletions need to search both
+ * locations; additions must take care to only insert into the new bucket.
+ */