| 1 | /* SPDX-License-Identifier: GPL-2.0 */ |
|---|
| 2 | /* |
|---|
| 3 | * Resizable, Scalable, Concurrent Hash Table |
|---|
| 4 | * |
|---|
| 5 | * Simple structures that might be needed in include |
|---|
| 6 | * files. |
|---|
| 7 | */ |
|---|
| 8 | |
|---|
| 9 | #ifndef _LINUX_RHASHTABLE_TYPES_H |
|---|
| 10 | #define _LINUX_RHASHTABLE_TYPES_H |
|---|
| 11 | |
|---|
| 12 | #include <linux/alloc_tag.h> |
|---|
| 13 | #include <linux/atomic.h> |
|---|
| 14 | #include <linux/compiler.h> |
|---|
| 15 | #include <linux/mutex.h> |
|---|
| 16 | #include <linux/workqueue_types.h> |
|---|
| 17 | |
|---|
| 18 | struct rhash_head { |
|---|
| 19 | struct rhash_head __rcu *next; |
|---|
| 20 | }; |
|---|
| 21 | |
|---|
| 22 | struct rhlist_head { |
|---|
| 23 | struct rhash_head rhead; |
|---|
| 24 | struct rhlist_head __rcu *next; |
|---|
| 25 | }; |
|---|
| 26 | |
|---|
| 27 | struct bucket_table; |
|---|
| 28 | |
|---|
| 29 | /** |
|---|
| 30 | * struct rhashtable_compare_arg - Key for the function rhashtable_compare |
|---|
| 31 | * @ht: Hash table |
|---|
| 32 | * @key: Key to compare against |
|---|
| 33 | */ |
|---|
| 34 | struct rhashtable_compare_arg { |
|---|
| 35 | struct rhashtable *ht; |
|---|
| 36 | const void *key; |
|---|
| 37 | }; |
|---|
| 38 | |
|---|
| 39 | typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed); |
|---|
| 40 | typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed); |
|---|
| 41 | typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg, |
|---|
| 42 | const void *obj); |
|---|
| 43 | |
|---|
| 44 | /** |
|---|
| 45 | * struct rhashtable_params - Hash table construction parameters |
|---|
| 46 | * @nelem_hint: Hint on number of elements, should be 75% of desired size |
|---|
| 47 | * @key_len: Length of key |
|---|
| 48 | * @key_offset: Offset of key in struct to be hashed |
|---|
| 49 | * @head_offset: Offset of rhash_head in struct to be hashed |
|---|
| 50 | * @max_size: Maximum size while expanding |
|---|
| 51 | * @min_size: Minimum size while shrinking |
|---|
| 52 | * @automatic_shrinking: Enable automatic shrinking of tables |
|---|
| 53 | * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash) |
|---|
| 54 | * @obj_hashfn: Function to hash object |
|---|
| 55 | * @obj_cmpfn: Function to compare key with object |
|---|
| 56 | */ |
|---|
| 57 | struct rhashtable_params { |
|---|
| 58 | u16 nelem_hint; |
|---|
| 59 | u16 key_len; |
|---|
| 60 | u16 key_offset; |
|---|
| 61 | u16 head_offset; |
|---|
| 62 | unsigned int max_size; |
|---|
| 63 | u16 min_size; |
|---|
| 64 | bool automatic_shrinking; |
|---|
| 65 | rht_hashfn_t hashfn; |
|---|
| 66 | rht_obj_hashfn_t obj_hashfn; |
|---|
| 67 | rht_obj_cmpfn_t obj_cmpfn; |
|---|
| 68 | }; |
|---|
| 69 | |
|---|
| 70 | /** |
|---|
| 71 | * struct rhashtable - Hash table handle |
|---|
| 72 | * @tbl: Bucket table |
|---|
| 73 | * @key_len: Key length for hashfn |
|---|
| 74 | * @max_elems: Maximum number of elements in table |
|---|
| 75 | * @p: Configuration parameters |
|---|
| 76 | * @rhlist: True if this is an rhltable |
|---|
| 77 | * @run_work: Deferred worker to expand/shrink asynchronously |
|---|
| 78 | * @mutex: Mutex to protect current/future table swapping |
|---|
| 79 | * @lock: Spin lock to protect walker list |
|---|
| 80 | * @nelems: Number of elements in table |
|---|
| 81 | */ |
|---|
| 82 | struct rhashtable { |
|---|
| 83 | struct bucket_table __rcu *tbl; |
|---|
| 84 | unsigned int key_len; |
|---|
| 85 | unsigned int max_elems; |
|---|
| 86 | struct rhashtable_params p; |
|---|
| 87 | bool rhlist; |
|---|
| 88 | struct work_struct run_work; |
|---|
| 89 | struct mutex mutex; |
|---|
| 90 | spinlock_t lock; |
|---|
| 91 | atomic_t nelems; |
|---|
| 92 | #ifdef CONFIG_MEM_ALLOC_PROFILING |
|---|
| 93 | struct alloc_tag *alloc_tag; |
|---|
| 94 | #endif |
|---|
| 95 | }; |
|---|
| 96 | |
|---|
| 97 | /** |
|---|
| 98 | * struct rhltable - Hash table with duplicate objects in a list |
|---|
| 99 | * @ht: Underlying rhtable |
|---|
| 100 | */ |
|---|
| 101 | struct rhltable { |
|---|
| 102 | struct rhashtable ht; |
|---|
| 103 | }; |
|---|
| 104 | |
|---|
| 105 | /** |
|---|
| 106 | * struct rhashtable_walker - Hash table walker |
|---|
| 107 | * @list: List entry on list of walkers |
|---|
| 108 | * @tbl: The table that we were walking over |
|---|
| 109 | */ |
|---|
| 110 | struct rhashtable_walker { |
|---|
| 111 | struct list_head list; |
|---|
| 112 | struct bucket_table *tbl; |
|---|
| 113 | }; |
|---|
| 114 | |
|---|
| 115 | /** |
|---|
| 116 | * struct rhashtable_iter - Hash table iterator |
|---|
| 117 | * @ht: Table to iterate through |
|---|
| 118 | * @p: Current pointer |
|---|
| 119 | * @list: Current hash list pointer |
|---|
| 120 | * @walker: Associated rhashtable walker |
|---|
| 121 | * @slot: Current slot |
|---|
| 122 | * @skip: Number of entries to skip in slot |
|---|
| 123 | */ |
|---|
| 124 | struct rhashtable_iter { |
|---|
| 125 | struct rhashtable *ht; |
|---|
| 126 | struct rhash_head *p; |
|---|
| 127 | struct rhlist_head *list; |
|---|
| 128 | struct rhashtable_walker walker; |
|---|
| 129 | unsigned int slot; |
|---|
| 130 | unsigned int skip; |
|---|
| 131 | bool end_of_table; |
|---|
| 132 | }; |
|---|
| 133 | |
|---|
| 134 | int rhashtable_init_noprof(struct rhashtable *ht, |
|---|
| 135 | const struct rhashtable_params *params); |
|---|
| 136 | #define rhashtable_init(...) alloc_hooks(rhashtable_init_noprof(__VA_ARGS__)) |
|---|
| 137 | |
|---|
| 138 | int rhltable_init_noprof(struct rhltable *hlt, |
|---|
| 139 | const struct rhashtable_params *params); |
|---|
| 140 | #define rhltable_init(...) alloc_hooks(rhltable_init_noprof(__VA_ARGS__)) |
|---|
| 141 | |
|---|
| 142 | #endif /* _LINUX_RHASHTABLE_TYPES_H */ |
|---|
| 143 | |
|---|
