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