1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* Copyright (C) B.A.T.M.A.N. contributors: 3 * 4 * Simon Wunderlich, Marek Lindner 5 */ 6 7 #ifndef _NET_BATMAN_ADV_HASH_H_ 8 #define _NET_BATMAN_ADV_HASH_H_ 9 10 #include "main.h" 11 12 #include <linux/atomic.h> 13 #include <linux/compiler.h> 14 #include <linux/list.h> 15 #include <linux/lockdep.h> 16 #include <linux/rculist.h> 17 #include <linux/spinlock.h> 18 #include <linux/stddef.h> 19 #include <linux/types.h> 20 21 /** 22 * typedef batadv_hashdata_compare_cb - hash element comparison callback 23 * @node: hlist node of the element currently stored in the bucket 24 * @key: opaque payload to compare @node's key against 25 * 26 * Compare hash element by its keys. 27 * 28 * Return: true if both elements are considered equal, false otherwise. 29 */ 30 typedef bool (*batadv_hashdata_compare_cb)(const struct hlist_node *node, 31 const void *key); 32 33 /** 34 * typedef batadv_hashdata_choose_cb - hash bucket selection callback 35 * @key: opaque payload whose key selects the bucket 36 * @size: number of buckets in the hash table 37 * 38 * Return: bucket index derived from the key in @key and the table @size. 39 */ 40 typedef u32 (*batadv_hashdata_choose_cb)(const void *key, u32 size); 41 42 /** 43 * typedef batadv_hashdata_free_cb - hash element free callback 44 * @node: hlist node of the element being removed 45 * @arg: opaque caller-supplied argument forwarded from the caller 46 * 47 * Release a previously inserted hash element. 48 */ 49 typedef void (*batadv_hashdata_free_cb)(struct hlist_node *node, void *arg); 50 51 /** 52 * struct batadv_hashtable - Wrapper of simple hlist based hashtable 53 */ 54 struct batadv_hashtable { 55 /** @table: the hashtable itself with the buckets */ 56 struct hlist_head *table; 57 58 /** @list_locks: spinlock for each hash list entry */ 59 spinlock_t *list_locks; 60 61 /** @size: size of hashtable */ 62 u32 size; 63 64 /** @generation: current (generation) sequence number */ 65 atomic_t generation; 66 }; 67 68 /* allocates and clears the hash */ 69 struct batadv_hashtable *batadv_hash_new(u32 size); 70 71 /* set class key for all locks */ 72 void batadv_hash_set_lock_class(struct batadv_hashtable *hash, 73 struct lock_class_key *key); 74 75 /* free only the hashtable and the hash itself. */ 76 void batadv_hash_destroy(struct batadv_hashtable *hash); 77 78 /** 79 * batadv_hash_add() - adds data to the hashtable 80 * @hash: storage hash table 81 * @compare: callback to determine if 2 hash elements are identical 82 * @choose: callback calculating the hash index 83 * @data: data passed to the aforementioned callbacks as argument 84 * @data_node: to be added element 85 * 86 * Return: 0 on success, 1 if the element already is in the hash 87 * and -1 on error. 88 */ 89 static inline int batadv_hash_add(struct batadv_hashtable *hash, 90 batadv_hashdata_compare_cb compare, 91 batadv_hashdata_choose_cb choose, 92 const void *data, 93 struct hlist_node *data_node) 94 { 95 spinlock_t *list_lock; /* spinlock to protect write access */ 96 struct hlist_head *head; 97 struct hlist_node *node; 98 int ret = -1; 99 u32 index; 100 101 if (!hash) 102 goto out; 103 104 index = choose(data, hash->size); 105 head = &hash->table[index]; 106 list_lock = &hash->list_locks[index]; 107 108 spin_lock_bh(list_lock); 109 110 hlist_for_each(node, head) { 111 if (!compare(node, data)) 112 continue; 113 114 ret = 1; 115 goto unlock; 116 } 117 118 /* no duplicate found in list, add new element */ 119 hlist_add_head_rcu(data_node, head); 120 atomic_inc(&hash->generation); 121 122 ret = 0; 123 124 unlock: 125 spin_unlock_bh(list_lock); 126 out: 127 return ret; 128 } 129 130 /** 131 * batadv_hash_remove() - Removes data from hash, if found 132 * @hash: hash table 133 * @compare: callback to determine if 2 hash elements are identical 134 * @choose: callback calculating the hash index 135 * @data: data passed to the aforementioned callbacks as argument 136 * 137 * data could be the structure you use with just the key filled, we just need 138 * the key for comparing. 139 * 140 * Return: returns pointer to data on success, so you can remove the used 141 * structure yourself, or NULL on error 142 */ 143 static inline void *batadv_hash_remove(struct batadv_hashtable *hash, 144 batadv_hashdata_compare_cb compare, 145 batadv_hashdata_choose_cb choose, 146 void *data) 147 { 148 struct hlist_node *node; 149 struct hlist_head *head; 150 void *data_save = NULL; 151 u32 index; 152 153 index = choose(data, hash->size); 154 head = &hash->table[index]; 155 156 spin_lock_bh(&hash->list_locks[index]); 157 hlist_for_each(node, head) { 158 if (!compare(node, data)) 159 continue; 160 161 data_save = node; 162 hlist_del_rcu(node); 163 atomic_inc(&hash->generation); 164 break; 165 } 166 spin_unlock_bh(&hash->list_locks[index]); 167 168 return data_save; 169 } 170 171 #endif /* _NET_BATMAN_ADV_HASH_H_ */ 172