The common hashtable implementation in the kernel uses bits of the hash to compute the final size of the hastable. Similar can be done for the partially locked, concurrent hashtables in batman-adv. The requirement of sizes with power two will allow better compiler optimization in the future.
Signed-off-by: Sven Eckelmann sven@narfation.org --- v3: - Rebased on master
bridge_loop_avoidance.c | 6 ++++-- distributed-arp-table.c | 2 +- main.h | 9 +++++++++ network-coding.c | 7 +++++-- originator.c | 2 +- translation-table.c | 8 ++++++-- 6 files changed, 26 insertions(+), 8 deletions(-)
diff --git a/bridge_loop_avoidance.c b/bridge_loop_avoidance.c index 6927589..c999d6b 100644 --- a/bridge_loop_avoidance.c +++ b/bridge_loop_avoidance.c @@ -1220,6 +1220,8 @@ int batadv_bla_init(struct batadv_priv *bat_priv) struct batadv_hard_iface *primary_if; uint16_t crc; unsigned long entrytime; + uint32_t hash_claim_size = 1u << BATADV_BLA_CLAIM_HASH_BITS; + uint32_t hash_backbone_size = 1u << BATADV_BLA_BACKBONE_HASH_BITS;
spin_lock_init(&bat_priv->bla.bcast_duplist_lock);
@@ -1246,8 +1248,8 @@ int batadv_bla_init(struct batadv_priv *bat_priv) if (bat_priv->bla.claim_hash) return 0;
- bat_priv->bla.claim_hash = batadv_hash_new(128); - bat_priv->bla.backbone_hash = batadv_hash_new(32); + bat_priv->bla.claim_hash = batadv_hash_new(hash_claim_size); + bat_priv->bla.backbone_hash = batadv_hash_new(hash_backbone_size);
if (!bat_priv->bla.claim_hash || !bat_priv->bla.backbone_hash) return -ENOMEM; diff --git a/distributed-arp-table.c b/distributed-arp-table.c index 107ad62..87ab637 100644 --- a/distributed-arp-table.c +++ b/distributed-arp-table.c @@ -725,7 +725,7 @@ int batadv_dat_init(struct batadv_priv *bat_priv) if (bat_priv->dat.hash) return 0;
- bat_priv->dat.hash = batadv_hash_new(1024); + bat_priv->dat.hash = batadv_hash_new(1u << BATADV_DAT_HASH_BITS);
if (!bat_priv->dat.hash) return -ENOMEM; diff --git a/main.h b/main.h index 4deacfd..26a20ae 100644 --- a/main.h +++ b/main.h @@ -154,6 +154,15 @@ enum batadv_uev_type { #define BATADV_DAT_CANDIDATE_NOT_FOUND 0 #define BATADV_DAT_CANDIDATE_ORIG 1
+#define BATADV_BLA_CLAIM_HASH_BITS 7 +#define BATADV_BLA_BACKBONE_HASH_BITS 5 +#define BATADV_NC_CODING_HASH_BITS 7 +#define BATADV_NC_DECODING_HASH_BITS 7 +#define BATADV_DAT_HASH_BITS 10 +#define BATADV_ORIG_HASH_BITS 10 +#define BATADV_TT_LOCAL_HASH_BITS 10 +#define BATADV_TT_GLOBAL_HASH_BITS 10 + /* Debug Messages */ #ifdef pr_fmt #undef pr_fmt diff --git a/network-coding.c b/network-coding.c index d128c3b..b70c34e 100644 --- a/network-coding.c +++ b/network-coding.c @@ -116,20 +116,23 @@ static void batadv_nc_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv, */ int batadv_nc_mesh_init(struct batadv_priv *bat_priv) { + uint32_t hash_coding_size = 1u << BATADV_NC_CODING_HASH_BITS; + uint32_t hash_decoding_size = 1u << BATADV_NC_DECODING_HASH_BITS; + bat_priv->nc.timestamp_fwd_flush = jiffies; bat_priv->nc.timestamp_sniffed_purge = jiffies;
if (bat_priv->nc.coding_hash || bat_priv->nc.decoding_hash) return 0;
- bat_priv->nc.coding_hash = batadv_hash_new(128); + bat_priv->nc.coding_hash = batadv_hash_new(hash_coding_size); if (!bat_priv->nc.coding_hash) goto err;
batadv_hash_set_lock_class(bat_priv->nc.coding_hash, &batadv_nc_coding_hash_lock_class_key);
- bat_priv->nc.decoding_hash = batadv_hash_new(128); + bat_priv->nc.decoding_hash = batadv_hash_new(hash_decoding_size); if (!bat_priv->nc.decoding_hash) goto err;
diff --git a/originator.c b/originator.c index 90e805a..34ca176 100644 --- a/originator.c +++ b/originator.c @@ -130,7 +130,7 @@ int batadv_originator_init(struct batadv_priv *bat_priv) if (bat_priv->orig_hash) return 0;
- bat_priv->orig_hash = batadv_hash_new(1024); + bat_priv->orig_hash = batadv_hash_new(1u << BATADV_ORIG_HASH_BITS);
if (!bat_priv->orig_hash) goto err; diff --git a/translation-table.c b/translation-table.c index b20812b..1562e26 100644 --- a/translation-table.c +++ b/translation-table.c @@ -460,10 +460,12 @@ static int batadv_tt_local_table_transmit_size(struct batadv_priv *bat_priv)
static int batadv_tt_local_init(struct batadv_priv *bat_priv) { + uint32_t hash_size = 1u << BATADV_TT_LOCAL_HASH_BITS; + if (bat_priv->tt.local_hash) return 0;
- bat_priv->tt.local_hash = batadv_hash_new(1024); + bat_priv->tt.local_hash = batadv_hash_new(hash_size);
if (!bat_priv->tt.local_hash) return -ENOMEM; @@ -1158,10 +1160,12 @@ static void batadv_tt_local_table_free(struct batadv_priv *bat_priv)
static int batadv_tt_global_init(struct batadv_priv *bat_priv) { + uint32_t hash_size = 1u << BATADV_TT_GLOBAL_HASH_BITS; + if (bat_priv->tt.global_hash) return 0;
- bat_priv->tt.global_hash = batadv_hash_new(1024); + bat_priv->tt.global_hash = batadv_hash_new(hash_size);
if (!bat_priv->tt.global_hash) return -ENOMEM;
The size of an hashtable is known by the user of the hash and doesn't have to be stored inside the batadv_hashtable structure. This is an intermediate step before the size information is extracted by the compiler instead of manually added by the code.
Signed-off-by: Sven Eckelmann sven@narfation.org --- v3: - Rebased on master
bat_iv_ogm.c | 8 ++++--- bridge_loop_avoidance.c | 32 +++++++++++++++----------- distributed-arp-table.c | 12 +++++----- hash.c | 11 +++++---- hash.h | 13 ++++++----- network-coding.c | 44 +++++++++++++++++++++++++----------- originator.c | 9 ++++---- originator.h | 2 +- translation-table.c | 60 ++++++++++++++++++++++++++++--------------------- 9 files changed, 116 insertions(+), 75 deletions(-)
diff --git a/bat_iv_ogm.c b/bat_iv_ogm.c index 554e0e0..7b30cd4 100644 --- a/bat_iv_ogm.c +++ b/bat_iv_ogm.c @@ -245,7 +245,9 @@ batadv_iv_ogm_orig_get(struct batadv_priv *bat_priv, const uint8_t *addr) if (!orig_node->bat_iv.bcast_own_sum) goto free_orig_node;
- hash_added = batadv_hash_add(bat_priv->orig_hash, batadv_compare_orig, + hash_added = batadv_hash_add(bat_priv->orig_hash, + 1u << BATADV_ORIG_HASH_BITS, + batadv_compare_orig, batadv_choose_orig, orig_node, &orig_node->hash_entry); if (hash_added != 0) @@ -871,7 +873,7 @@ batadv_iv_ogm_slide_own_bcast_window(struct batadv_hard_iface *hard_iface) uint8_t *w; int if_num;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1812,7 +1814,7 @@ static void batadv_iv_ogm_orig_print(struct batadv_priv *bat_priv, "Originator", "last-seen", "#", BATADV_TQ_MAX_VALUE, "Nexthop", "outgoingIF", "Potential nexthops");
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); diff --git a/bridge_loop_avoidance.c b/bridge_loop_avoidance.c index c999d6b..d19f7c2 100644 --- a/bridge_loop_avoidance.c +++ b/bridge_loop_avoidance.c @@ -142,7 +142,7 @@ static struct batadv_bla_claim if (!hash) return NULL;
- index = batadv_choose_claim(data, hash->size); + index = batadv_choose_claim(data, 1u << BATADV_BLA_CLAIM_HASH_BITS); head = &hash->table[index];
rcu_read_lock(); @@ -178,6 +178,7 @@ batadv_backbone_hash_find(struct batadv_priv *bat_priv, struct batadv_bla_backbone_gw search_entry, *backbone_gw; struct batadv_bla_backbone_gw *backbone_gw_tmp = NULL; int index; + uint32_t hash_size = 1u << BATADV_BLA_BACKBONE_HASH_BITS;
if (!hash) return NULL; @@ -185,7 +186,7 @@ batadv_backbone_hash_find(struct batadv_priv *bat_priv, ether_addr_copy(search_entry.orig, addr); search_entry.vid = vid;
- index = batadv_choose_backbone_gw(&search_entry, hash->size); + index = batadv_choose_backbone_gw(&search_entry, hash_size); head = &hash->table[index];
rcu_read_lock(); @@ -220,7 +221,7 @@ batadv_bla_del_backbone_claims(struct batadv_bla_backbone_gw *backbone_gw) if (!hash) return;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_CLAIM_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -393,6 +394,7 @@ batadv_bla_get_backbone_gw(struct batadv_priv *bat_priv, uint8_t *orig, atomic_set(&entry->refcount, 2);
hash_added = batadv_hash_add(bat_priv->bla.backbone_hash, + 1u << BATADV_BLA_BACKBONE_HASH_BITS, batadv_compare_backbone_gw, batadv_choose_backbone_gw, entry, &entry->hash_entry); @@ -472,7 +474,7 @@ static void batadv_bla_answer_request(struct batadv_priv *bat_priv, return;
hash = bat_priv->bla.claim_hash; - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_CLAIM_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -576,6 +578,7 @@ static void batadv_bla_add_claim(struct batadv_priv *bat_priv, "bla_add_claim(): adding new entry %pM, vid %d to hash ...\n", mac, BATADV_PRINT_VID(vid)); hash_added = batadv_hash_add(bat_priv->bla.claim_hash, + 1u << BATADV_BLA_CLAIM_HASH_BITS, batadv_compare_claim, batadv_choose_claim, claim, &claim->hash_entry); @@ -626,8 +629,9 @@ static void batadv_bla_del_claim(struct batadv_priv *bat_priv, batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla_del_claim(): %pM, vid %d\n", mac, BATADV_PRINT_VID(vid));
- batadv_hash_remove(bat_priv->bla.claim_hash, batadv_compare_claim, - batadv_choose_claim, claim); + batadv_hash_remove(bat_priv->bla.claim_hash, + 1u << BATADV_BLA_CLAIM_HASH_BITS, + batadv_compare_claim, batadv_choose_claim, claim); batadv_claim_free_ref(claim); /* reference from the hash is gone */
claim->backbone_gw->crc ^= crc16(0, claim->addr, ETH_ALEN); @@ -994,7 +998,7 @@ static void batadv_bla_purge_backbone_gw(struct batadv_priv *bat_priv, int now) if (!hash) return;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -1047,7 +1051,7 @@ static void batadv_bla_purge_claims(struct batadv_priv *bat_priv, if (!hash) return;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_CLAIM_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1110,7 +1114,7 @@ void batadv_bla_update_orig_address(struct batadv_priv *bat_priv, if (!hash) return;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1163,7 +1167,7 @@ static void batadv_bla_periodic_work(struct work_struct *work) if (!hash) goto out;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1255,8 +1259,10 @@ int batadv_bla_init(struct batadv_priv *bat_priv) return -ENOMEM;
batadv_hash_set_lock_class(bat_priv->bla.claim_hash, + 1u << BATADV_BLA_CLAIM_HASH_BITS, &batadv_claim_hash_lock_class_key); batadv_hash_set_lock_class(bat_priv->bla.backbone_hash, + 1u << BATADV_BLA_CLAIM_HASH_BITS, &batadv_backbone_hash_lock_class_key);
batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla hashes initialized\n"); @@ -1362,7 +1368,7 @@ bool batadv_bla_is_backbone_gw_orig(struct batadv_priv *bat_priv, uint8_t *orig, if (!hash) return false;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1642,7 +1648,7 @@ int batadv_bla_claim_table_seq_print_text(struct seq_file *seq, void *offset) ntohs(bat_priv->bla.claim_dest.group)); seq_printf(seq, " %-17s %-5s %-17s [o] (%-6s)\n", "Client", "VID", "Originator", "CRC"); - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_CLAIM_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1687,7 +1693,7 @@ int batadv_bla_backbone_table_seq_print_text(struct seq_file *seq, void *offset) ntohs(bat_priv->bla.claim_dest.group)); seq_printf(seq, " %-17s %-5s %-9s (%-6s)\n", "Originator", "VID", "last seen", "CRC"); - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); diff --git a/distributed-arp-table.c b/distributed-arp-table.c index 87ab637..a027e75 100644 --- a/distributed-arp-table.c +++ b/distributed-arp-table.c @@ -88,7 +88,7 @@ static void __batadv_dat_purge(struct batadv_priv *bat_priv, if (!bat_priv->dat.hash) return;
- for (i = 0; i < bat_priv->dat.hash->size; i++) { + for (i = 0; i < 1u << BATADV_DAT_HASH_BITS; i++) { head = &bat_priv->dat.hash->table[i]; list_lock = &bat_priv->dat.hash->list_locks[i];
@@ -254,7 +254,7 @@ batadv_dat_entry_hash_find(struct batadv_priv *bat_priv, __be32 ip, to_find.ip = ip; to_find.vid = vid;
- index = batadv_hash_dat(&to_find, hash->size); + index = batadv_hash_dat(&to_find, 1u << BATADV_DAT_HASH_BITS); head = &hash->table[index];
rcu_read_lock(); @@ -309,7 +309,9 @@ static void batadv_dat_entry_add(struct batadv_priv *bat_priv, __be32 ip, dat_entry->last_update = jiffies; atomic_set(&dat_entry->refcount, 2);
- hash_added = batadv_hash_add(bat_priv->dat.hash, batadv_compare_dat, + hash_added = batadv_hash_add(bat_priv->dat.hash, + 1u << BATADV_DAT_HASH_BITS, + batadv_compare_dat, batadv_hash_dat, dat_entry, &dat_entry->hash_entry);
@@ -492,7 +494,7 @@ static void batadv_choose_next_candidate(struct batadv_priv *bat_priv, /* iterate over the originator list and find the node with the closest * dat_address which has not been selected yet */ - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -778,7 +780,7 @@ int batadv_dat_cache_seq_print_text(struct seq_file *seq, void *offset) seq_printf(seq, " %-7s %-9s %4s %11s\n", "IPv4", "MAC", "VID", "last-seen");
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_DAT_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); diff --git a/hash.c b/hash.c index 7c1c630..8e8d934 100644 --- a/hash.c +++ b/hash.c @@ -19,11 +19,11 @@ #include "hash.h"
/* clears the hash */ -static void batadv_hash_init(struct batadv_hashtable *hash) +static void batadv_hash_init(struct batadv_hashtable *hash, uint32_t size) { uint32_t i;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < size; i++) { INIT_HLIST_HEAD(&hash->table[i]); spin_lock_init(&hash->list_locks[i]); } @@ -55,8 +55,7 @@ struct batadv_hashtable *batadv_hash_new(uint32_t size) if (!hash->list_locks) goto free_table;
- hash->size = size; - batadv_hash_init(hash); + batadv_hash_init(hash, size); return hash;
free_table: @@ -66,11 +65,11 @@ free_hash: return NULL; }
-void batadv_hash_set_lock_class(struct batadv_hashtable *hash, +void batadv_hash_set_lock_class(struct batadv_hashtable *hash, uint32_t size, struct lock_class_key *key) { uint32_t i;
- for (i = 0; i < hash->size; i++) + for (i = 0; i < size; i++) lockdep_set_class(&hash->list_locks[i], key); } diff --git a/hash.h b/hash.h index a1d0980..c88166b 100644 --- a/hash.h +++ b/hash.h @@ -36,14 +36,13 @@ typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *); struct batadv_hashtable { struct hlist_head *table; /* the hashtable itself with the buckets */ spinlock_t *list_locks; /* spinlock for each hash list entry */ - uint32_t size; /* size of hashtable */ };
/* allocates and clears the hash */ struct batadv_hashtable *batadv_hash_new(uint32_t size);
/* set class key for all locks */ -void batadv_hash_set_lock_class(struct batadv_hashtable *hash, +void batadv_hash_set_lock_class(struct batadv_hashtable *hash, uint32_t size, struct lock_class_key *key);
/* free only the hashtable and the hash itself. */ @@ -54,6 +53,7 @@ void batadv_hash_destroy(struct batadv_hashtable *hash); * elements, memory might be leaked. */ static inline void batadv_hash_delete(struct batadv_hashtable *hash, + uint32_t size, batadv_hashdata_free_cb free_cb, void *arg) { @@ -62,7 +62,7 @@ static inline void batadv_hash_delete(struct batadv_hashtable *hash, spinlock_t *list_lock; /* spinlock to protect write access */ uint32_t i;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < size; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -82,6 +82,7 @@ static inline void batadv_hash_delete(struct batadv_hashtable *hash, /** * batadv_hash_add - adds data to the hashtable * @hash: storage hash table + * @size: size of the hashtable * @compare: callback to determine if 2 hash elements are identical * @choose: callback calculating the hash index * @data: data passed to the aforementioned callbacks as argument @@ -91,6 +92,7 @@ static inline void batadv_hash_delete(struct batadv_hashtable *hash, * and -1 on error. */ static inline int batadv_hash_add(struct batadv_hashtable *hash, + uint32_t size, batadv_hashdata_compare_cb compare, batadv_hashdata_choose_cb choose, const void *data, @@ -105,7 +107,7 @@ static inline int batadv_hash_add(struct batadv_hashtable *hash, if (!hash) goto out;
- index = choose(data, hash->size); + index = choose(data, size); head = &hash->table[index]; list_lock = &hash->list_locks[index];
@@ -136,6 +138,7 @@ out: * comparing. */ static inline void *batadv_hash_remove(struct batadv_hashtable *hash, + uint32_t size, batadv_hashdata_compare_cb compare, batadv_hashdata_choose_cb choose, void *data) @@ -145,7 +148,7 @@ static inline void *batadv_hash_remove(struct batadv_hashtable *hash, struct hlist_head *head; void *data_save = NULL;
- index = choose(data, hash->size); + index = choose(data, size); head = &hash->table[index];
spin_lock_bh(&hash->list_locks[index]); diff --git a/network-coding.c b/network-coding.c index b70c34e..6f0ceb4 100644 --- a/network-coding.c +++ b/network-coding.c @@ -130,6 +130,7 @@ int batadv_nc_mesh_init(struct batadv_priv *bat_priv) goto err;
batadv_hash_set_lock_class(bat_priv->nc.coding_hash, + 1u << BATADV_NC_CODING_HASH_BITS, &batadv_nc_coding_hash_lock_class_key);
bat_priv->nc.decoding_hash = batadv_hash_new(hash_decoding_size); @@ -137,6 +138,7 @@ int batadv_nc_mesh_init(struct batadv_priv *bat_priv) goto err;
batadv_hash_set_lock_class(bat_priv->nc.decoding_hash, + 1u << BATADV_NC_DECODING_HASH_BITS, &batadv_nc_decoding_hash_lock_class_key);
INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker); @@ -361,7 +363,7 @@ static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv) return;
/* For each orig_node */ - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -377,6 +379,7 @@ static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv) * unused ones * @bat_priv: the bat priv with all the soft interface information * @hash: hash table containing the nc paths to check + * @hash_size: number of buckets in the hashtable * @to_purge: function in charge to decide whether an entry has to be purged or * not. This function takes the nc node as argument and has to return * a boolean value: true is the entry has to be deleted, false @@ -384,6 +387,7 @@ static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv) */ static void batadv_nc_purge_paths(struct batadv_priv *bat_priv, struct batadv_hashtable *hash, + uint32_t hash_size, bool (*to_purge)(struct batadv_priv *, struct batadv_nc_path *)) { @@ -393,7 +397,7 @@ static void batadv_nc_purge_paths(struct batadv_priv *bat_priv, spinlock_t *lock; /* Protects lists in hash */ uint32_t i;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < hash_size; i++) { head = &hash->table[i]; lock = &hash->list_locks[i];
@@ -493,12 +497,13 @@ static int batadv_nc_hash_compare(const struct hlist_node *node, /** * batadv_nc_hash_find - search for an existing nc path and return it * @hash: hash table containing the nc path + * @hash_size: number of buckets in the hashtable * @data: search key * * Returns the nc_path if found, NULL otherwise. */ static struct batadv_nc_path * -batadv_nc_hash_find(struct batadv_hashtable *hash, +batadv_nc_hash_find(struct batadv_hashtable *hash, uint32_t hash_size, void *data) { struct hlist_head *head; @@ -508,7 +513,7 @@ batadv_nc_hash_find(struct batadv_hashtable *hash, if (!hash) return NULL;
- index = batadv_nc_hash_choose(data, hash->size); + index = batadv_nc_hash_choose(data, hash_size); head = &hash->table[index];
rcu_read_lock(); @@ -618,13 +623,14 @@ static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv, * nc packets * @bat_priv: the bat priv with all the soft interface information * @hash: to be processed hash table + * @hash_size: number of buckets in the hashtable * @process_fn: Function called to process given nc packet. Should return true * to encourage this function to proceed with the next packet. * Otherwise the rest of the current queue is skipped. */ static void batadv_nc_process_nc_paths(struct batadv_priv *bat_priv, - struct batadv_hashtable *hash, + struct batadv_hashtable *hash, uint32_t hash_size, bool (*process_fn)(struct batadv_priv *, struct batadv_nc_path *, struct batadv_nc_packet *)) @@ -639,7 +645,7 @@ batadv_nc_process_nc_paths(struct batadv_priv *bat_priv, return;
/* Loop hash table bins */ - for (i = 0; i < hash->size; i++) { + for (i = 0; i < hash_size; i++) { head = &hash->table[i];
/* Loop coding paths */ @@ -676,14 +682,17 @@ static void batadv_nc_worker(struct work_struct *work)
batadv_nc_purge_orig_hash(bat_priv); batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, + 1u << BATADV_NC_CODING_HASH_BITS, batadv_nc_to_purge_nc_path_coding); batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, + 1u << BATADV_NC_DECODING_HASH_BITS, batadv_nc_to_purge_nc_path_decoding);
timeout = bat_priv->nc.max_fwd_delay;
if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) { batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash, + 1u << BATADV_NC_CODING_HASH_BITS, batadv_nc_fwd_flush); bat_priv->nc.timestamp_fwd_flush = jiffies; } @@ -691,6 +700,7 @@ static void batadv_nc_worker(struct work_struct *work) if (batadv_has_timed_out(bat_priv->nc.timestamp_sniffed_purge, bat_priv->nc.max_buffer_time)) { batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.decoding_hash, + 1u << BATADV_NC_DECODING_HASH_BITS, batadv_nc_sniffed_purge); bat_priv->nc.timestamp_sniffed_purge = jiffies; } @@ -903,6 +913,7 @@ out: * batadv_nc_get_path - get existing nc_path or allocate a new one * @bat_priv: the bat priv with all the soft interface information * @hash: hash table containing the nc path + * @hash_size: number of buckets in the hashtable * @src: ethernet source address - first half of the nc path search key * @dst: ethernet destination address - second half of the nc path search key * @@ -911,6 +922,7 @@ out: */ static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv, struct batadv_hashtable *hash, + uint32_t hash_size, uint8_t *src, uint8_t *dst) { @@ -920,7 +932,7 @@ static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv, batadv_nc_hash_key_gen(&nc_path_key, src, dst);
/* Search for existing nc_path */ - nc_path = batadv_nc_hash_find(hash, (void *)&nc_path_key); + nc_path = batadv_nc_hash_find(hash, hash_size, (void *)&nc_path_key);
if (nc_path) { /* Set timestamp to delay removal of nc_path */ @@ -947,7 +959,7 @@ static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv, nc_path->next_hop);
/* Add nc_path to hash table */ - hash_added = batadv_hash_add(hash, batadv_nc_hash_compare, + hash_added = batadv_hash_add(hash, hash_size, batadv_nc_hash_compare, batadv_nc_hash_choose, &nc_path_key, &nc_path->hash_entry);
@@ -1242,7 +1254,8 @@ batadv_nc_path_search(struct batadv_priv *bat_priv, /* Create almost path key */ batadv_nc_hash_key_gen(&nc_path_key, in_nc_node->addr, out_nc_node->addr); - idx = batadv_nc_hash_choose(&nc_path_key, hash->size); + idx = batadv_nc_hash_choose(&nc_path_key, + 1u << BATADV_NC_CODING_HASH_BITS);
/* Check for coding opportunities in this nc_path */ rcu_read_lock(); @@ -1490,6 +1503,7 @@ bool batadv_nc_skb_forward(struct sk_buff *skb, /* Find or create a nc_path for this src-dst pair */ nc_path = batadv_nc_get_path(bat_priv, bat_priv->nc.coding_hash, + 1u << BATADV_NC_CODING_HASH_BITS, ethhdr->h_source, neigh_node->addr);
@@ -1539,6 +1553,7 @@ void batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv, /* Find existing nc_path or create a new */ nc_path = batadv_nc_get_path(bat_priv, bat_priv->nc.decoding_hash, + 1u << BATADV_NC_DECODING_HASH_BITS, ethhdr->h_source, ethhdr->h_dest);
@@ -1721,7 +1736,8 @@ batadv_nc_find_decoding_packet(struct batadv_priv *bat_priv, }
batadv_nc_hash_key_gen(&nc_path_key, source, dest); - index = batadv_nc_hash_choose(&nc_path_key, hash->size); + index = batadv_nc_hash_choose(&nc_path_key, + 1u << BATADV_NC_DECODING_HASH_BITS);
/* Search for matching coding path */ rcu_read_lock(); @@ -1830,9 +1846,11 @@ void batadv_nc_mesh_free(struct batadv_priv *bat_priv) batadv_tvlv_handler_unregister(bat_priv, BATADV_TVLV_NC, 1); cancel_delayed_work_sync(&bat_priv->nc.work);
- batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL); + batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, + 1u << BATADV_NC_CODING_HASH_BITS, NULL); batadv_hash_destroy(bat_priv->nc.coding_hash); - batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, NULL); + batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, + 1u << BATADV_NC_DECODING_HASH_BITS, NULL); batadv_hash_destroy(bat_priv->nc.decoding_hash); }
@@ -1857,7 +1875,7 @@ int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset) goto out;
/* Traverse list of originators */ - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i];
/* For each orig_node in this bin */ diff --git a/originator.c b/originator.c index 34ca176..55baa3d 100644 --- a/originator.c +++ b/originator.c @@ -136,6 +136,7 @@ int batadv_originator_init(struct batadv_priv *bat_priv) goto err;
batadv_hash_set_lock_class(bat_priv->orig_hash, + 1u << BATADV_ORIG_HASH_BITS, &batadv_orig_hash_lock_class_key);
INIT_DELAYED_WORK(&bat_priv->orig_work, batadv_purge_orig); @@ -615,7 +616,7 @@ void batadv_originator_free(struct batadv_priv *bat_priv)
bat_priv->orig_hash = NULL;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -964,7 +965,7 @@ static void _batadv_purge_orig(struct batadv_priv *bat_priv) return;
/* for all origins... */ - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -1098,7 +1099,7 @@ int batadv_orig_hash_add_if(struct batadv_hard_iface *hard_iface, /* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1135,7 +1136,7 @@ int batadv_orig_hash_del_if(struct batadv_hard_iface *hard_iface, /* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ - for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); diff --git a/originator.h b/originator.h index a179c03..89b810d 100644 --- a/originator.h +++ b/originator.h @@ -92,7 +92,7 @@ batadv_orig_hash_find(struct batadv_priv *bat_priv, const void *data) if (!hash) return NULL;
- index = batadv_choose_orig(data, hash->size); + index = batadv_choose_orig(data, 1u << BATADV_ORIG_HASH_BITS); head = &hash->table[index];
rcu_read_lock(); diff --git a/translation-table.c b/translation-table.c index 1562e26..60be9c6 100644 --- a/translation-table.c +++ b/translation-table.c @@ -83,8 +83,8 @@ static inline uint32_t batadv_choose_tt(const void *data, uint32_t size) * found, NULL otherwise. */ static struct batadv_tt_common_entry * -batadv_tt_hash_find(struct batadv_hashtable *hash, const uint8_t *addr, - unsigned short vid) +batadv_tt_hash_find(struct batadv_hashtable *hash, uint32_t size, + const uint8_t *addr, unsigned short vid) { struct hlist_head *head; struct batadv_tt_common_entry to_search, *tt, *tt_tmp = NULL; @@ -96,7 +96,7 @@ batadv_tt_hash_find(struct batadv_hashtable *hash, const uint8_t *addr, ether_addr_copy(to_search.addr, addr); to_search.vid = vid;
- index = batadv_choose_tt(&to_search, hash->size); + index = batadv_choose_tt(&to_search, size); head = &hash->table[index];
rcu_read_lock(); @@ -134,8 +134,9 @@ batadv_tt_local_hash_find(struct batadv_priv *bat_priv, const uint8_t *addr, struct batadv_tt_common_entry *tt_common_entry; struct batadv_tt_local_entry *tt_local_entry = NULL;
- tt_common_entry = batadv_tt_hash_find(bat_priv->tt.local_hash, addr, - vid); + tt_common_entry = batadv_tt_hash_find(bat_priv->tt.local_hash, + 1u << BATADV_TT_LOCAL_HASH_BITS, + addr, vid); if (tt_common_entry) tt_local_entry = container_of(tt_common_entry, struct batadv_tt_local_entry, @@ -159,8 +160,9 @@ batadv_tt_global_hash_find(struct batadv_priv *bat_priv, const uint8_t *addr, struct batadv_tt_common_entry *tt_common_entry; struct batadv_tt_global_entry *tt_global_entry = NULL;
- tt_common_entry = batadv_tt_hash_find(bat_priv->tt.global_hash, addr, - vid); + tt_common_entry = batadv_tt_hash_find(bat_priv->tt.global_hash, + 1u << BATADV_TT_GLOBAL_HASH_BITS, + addr, vid); if (tt_common_entry) tt_global_entry = container_of(tt_common_entry, struct batadv_tt_global_entry, @@ -470,7 +472,7 @@ static int batadv_tt_local_init(struct batadv_priv *bat_priv) if (!bat_priv->tt.local_hash) return -ENOMEM;
- batadv_hash_set_lock_class(bat_priv->tt.local_hash, + batadv_hash_set_lock_class(bat_priv->tt.local_hash, hash_size, &batadv_tt_local_hash_lock_class_key);
return 0; @@ -485,7 +487,8 @@ static void batadv_tt_global_free(struct batadv_priv *bat_priv, tt_global->common.addr, BATADV_PRINT_VID(tt_global->common.vid), message);
- batadv_hash_remove(bat_priv->tt.global_hash, batadv_compare_tt, + batadv_hash_remove(bat_priv->tt.global_hash, + 1u << BATADV_TT_GLOBAL_HASH_BITS, batadv_compare_tt, batadv_choose_tt, &tt_global->common); batadv_tt_global_entry_free_ref(tt_global); } @@ -599,8 +602,10 @@ bool batadv_tt_local_add(struct net_device *soft_iface, const uint8_t *addr, is_multicast_ether_addr(addr)) tt_local->common.flags |= BATADV_TT_CLIENT_NOPURGE;
- hash_added = batadv_hash_add(bat_priv->tt.local_hash, batadv_compare_tt, - batadv_choose_tt, &tt_local->common, + hash_added = batadv_hash_add(bat_priv->tt.local_hash, + 1u << BATADV_TT_LOCAL_HASH_BITS, + batadv_compare_tt, batadv_choose_tt, + &tt_local->common, &tt_local->common.hash_entry);
if (unlikely(hash_added != 0)) { @@ -924,7 +929,7 @@ int batadv_tt_local_seq_print_text(struct seq_file *seq, void *offset) seq_printf(seq, " %-13s %s %-8s %-9s (%-10s)\n", "Client", "VID", "Flags", "Last seen", "CRC");
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1104,7 +1109,7 @@ static void batadv_tt_local_purge(struct batadv_priv *bat_priv, spinlock_t *list_lock; /* protects write access to the hash lists */ uint32_t i;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -1130,7 +1135,7 @@ static void batadv_tt_local_table_free(struct batadv_priv *bat_priv)
hash = bat_priv->tt.local_hash;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -1170,7 +1175,7 @@ static int batadv_tt_global_init(struct batadv_priv *bat_priv) if (!bat_priv->tt.global_hash) return -ENOMEM;
- batadv_hash_set_lock_class(bat_priv->tt.global_hash, + batadv_hash_set_lock_class(bat_priv->tt.global_hash, hash_size, &batadv_tt_global_hash_lock_class_key);
return 0; @@ -1348,6 +1353,7 @@ static bool batadv_tt_global_add(struct batadv_priv *bat_priv, spin_lock_init(&tt_global_entry->list_lock);
hash_added = batadv_hash_add(bat_priv->tt.global_hash, + 1u << BATADV_TT_GLOBAL_HASH_BITS, batadv_compare_tt, batadv_choose_tt, common, &common->hash_entry); @@ -1591,7 +1597,7 @@ int batadv_tt_global_seq_print_text(struct seq_file *seq, void *offset) "Client", "VID", "(TTVN)", "Originator", "(Curr TTVN)", "CRC", "Flags");
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -1813,7 +1819,7 @@ void batadv_tt_global_del_orig(struct batadv_priv *bat_priv, if (!hash) return;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -1879,7 +1885,7 @@ static void batadv_tt_global_purge(struct batadv_priv *bat_priv) struct batadv_tt_common_entry *tt_common; struct batadv_tt_global_entry *tt_global;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -1922,7 +1928,7 @@ static void batadv_tt_global_table_free(struct batadv_priv *bat_priv)
hash = bat_priv->tt.global_hash;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
@@ -2057,7 +2063,7 @@ static uint32_t batadv_tt_global_crc(struct batadv_priv *bat_priv, uint8_t flags; __be16 tmp_vid;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -2132,7 +2138,7 @@ static uint32_t batadv_tt_local_crc(struct batadv_priv *bat_priv, uint8_t flags; __be16 tmp_vid;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -2288,6 +2294,7 @@ static int batadv_tt_global_valid(const void *entry_ptr, * specified tt hash * @bat_priv: the bat priv with all the soft interface information * @hash: hash table containing the tt entries + * @hash_size: number of buckets in the hashtable * @tt_len: expected tvlv tt data buffer length in number of bytes * @tvlv_buff: pointer to the buffer to fill with the TT data * @valid_cb: function to filter tt change entries @@ -2295,7 +2302,8 @@ static int batadv_tt_global_valid(const void *entry_ptr, */ static void batadv_tt_tvlv_generate(struct batadv_priv *bat_priv, struct batadv_hashtable *hash, - void *tvlv_buff, uint16_t tt_len, + uint32_t hash_size, void *tvlv_buff, + uint16_t tt_len, int (*valid_cb)(const void *, const void *), void *cb_data) { @@ -2309,7 +2317,7 @@ static void batadv_tt_tvlv_generate(struct batadv_priv *bat_priv, tt_change = (struct batadv_tvlv_tt_change *)tvlv_buff;
rcu_read_lock(); - for (i = 0; i < hash->size; i++) { + for (i = 0; i < hash_size; i++) { head = &hash->table[i];
hlist_for_each_entry_rcu(tt_common_entry, @@ -2589,6 +2597,7 @@ static bool batadv_send_other_tt_response(struct batadv_priv *bat_priv,
/* fill the rest of the tvlv with the real TT entries */ batadv_tt_tvlv_generate(bat_priv, bat_priv->tt.global_hash, + 1u << BATADV_TT_GLOBAL_HASH_BITS, tt_change, tt_len, batadv_tt_global_valid, req_dst_orig_node); @@ -2718,6 +2727,7 @@ static bool batadv_send_my_tt_response(struct batadv_priv *bat_priv,
/* fill the rest of the tvlv with the real TT entries */ batadv_tt_tvlv_generate(bat_priv, bat_priv->tt.local_hash, + 1u << BATADV_TT_LOCAL_HASH_BITS, tt_change, tt_len, batadv_tt_local_valid, NULL); } @@ -3123,7 +3133,7 @@ static void batadv_tt_local_set_flags(struct batadv_priv *bat_priv, if (!hash) return;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { head = &hash->table[i];
rcu_read_lock(); @@ -3165,7 +3175,7 @@ static void batadv_tt_local_purge_pending_clients(struct batadv_priv *bat_priv) if (!hash) return;
- for (i = 0; i < hash->size; i++) { + for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { head = &hash->table[i]; list_lock = &hash->list_locks[i];
From: "sven@narfation.org" sven@narfation.org
It is unnecessary to allocate an extra memory region for hashtables and the corresponding locks. This brings the hashes used in batman-adv slightly in the direction of the common statically sized hash table implementation. More common hashtable functionality cannot be used batman-adv wide because the simple hashtable and rhashtable implementations don't provide bucket based locking.
A sideeffect of this change is the initialization of each array of locks for each hashtable with a different lock_class. This allows to correct nesting of write access to two different hashtables without triggering a lockdep warning.
Signed-off-by: Sven Eckelmann sven@narfation.org --- v3: - Rebased on master - combine hlist_head and spinlock_t in own mini structure
The only thing I don't like at the moment are these checks whether hash was initialized/not initialized. Right now they are just removed because this check doesn't make sense anymore.
Makefile.kbuild | 1 - bat_iv_ogm.c | 13 ++-- bridge_loop_avoidance.c | 139 +++++++++++++-------------------------- distributed-arp-table.c | 52 ++++----------- hash.c | 75 --------------------- hash.h | 87 ++++++++++++------------- network-coding.c | 134 ++++++++++++++------------------------ originator.c | 56 +++++----------- originator.h | 9 +-- translation-table.c | 168 ++++++++++++++++-------------------------------- types.h | 27 +++++--- 11 files changed, 249 insertions(+), 512 deletions(-) delete mode 100644 hash.c
diff --git a/Makefile.kbuild b/Makefile.kbuild index 6903703..6ee8b04 100644 --- a/Makefile.kbuild +++ b/Makefile.kbuild @@ -26,7 +26,6 @@ batman-adv-y += fragmentation.o batman-adv-y += gateway_client.o batman-adv-y += gateway_common.o batman-adv-y += hard-interface.o -batman-adv-y += hash.o batman-adv-y += icmp_socket.o batman-adv-y += main.o batman-adv-$(CONFIG_BATMAN_ADV_MCAST) += multicast.o diff --git a/bat_iv_ogm.c b/bat_iv_ogm.c index 7b30cd4..60bb3d7 100644 --- a/bat_iv_ogm.c +++ b/bat_iv_ogm.c @@ -246,7 +246,6 @@ batadv_iv_ogm_orig_get(struct batadv_priv *bat_priv, const uint8_t *addr) goto free_orig_node;
hash_added = batadv_hash_add(bat_priv->orig_hash, - 1u << BATADV_ORIG_HASH_BITS, batadv_compare_orig, batadv_choose_orig, orig_node, &orig_node->hash_entry); @@ -864,7 +863,7 @@ static void batadv_iv_ogm_slide_own_bcast_window(struct batadv_hard_iface *hard_iface) { struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct hlist_head *head; struct batadv_orig_node *orig_node; unsigned long *word; @@ -873,8 +872,8 @@ batadv_iv_ogm_slide_own_bcast_window(struct batadv_hard_iface *hard_iface) uint8_t *w; int if_num;
- for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(orig_node, head, hash_entry) { @@ -1801,7 +1800,7 @@ static void batadv_iv_ogm_orig_print(struct batadv_priv *bat_priv, struct batadv_hard_iface *if_outgoing) { struct batadv_neigh_node *neigh_node; - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; int last_seen_msecs, last_seen_secs; struct batadv_orig_node *orig_node; struct batadv_neigh_ifinfo *n_ifinfo; @@ -1814,8 +1813,8 @@ static void batadv_iv_ogm_orig_print(struct batadv_priv *bat_priv, "Originator", "last-seen", "#", BATADV_TQ_MAX_VALUE, "Nexthop", "outgoingIF", "Potential nexthops");
- for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(orig_node, head, hash_entry) { diff --git a/bridge_loop_avoidance.c b/bridge_loop_avoidance.c index d19f7c2..7ebedbc 100644 --- a/bridge_loop_avoidance.c +++ b/bridge_loop_avoidance.c @@ -133,17 +133,14 @@ static struct batadv_bla_claim *batadv_claim_hash_find(struct batadv_priv *bat_priv, struct batadv_bla_claim *data) { - struct batadv_hashtable *hash = bat_priv->bla.claim_hash; + struct batadv_bucket *hash = bat_priv->bla.claim_hash; struct hlist_head *head; struct batadv_bla_claim *claim; struct batadv_bla_claim *claim_tmp = NULL; int index;
- if (!hash) - return NULL; - - index = batadv_choose_claim(data, 1u << BATADV_BLA_CLAIM_HASH_BITS); - head = &hash->table[index]; + index = batadv_choose_claim(data, ARRAY_SIZE(bat_priv->bla.claim_hash)); + head = &hash[index].head;
rcu_read_lock(); hlist_for_each_entry_rcu(claim, head, hash_entry) { @@ -173,21 +170,18 @@ static struct batadv_bla_backbone_gw * batadv_backbone_hash_find(struct batadv_priv *bat_priv, uint8_t *addr, unsigned short vid) { - struct batadv_hashtable *hash = bat_priv->bla.backbone_hash; + struct batadv_bucket *hash = bat_priv->bla.backbone_hash; struct hlist_head *head; struct batadv_bla_backbone_gw search_entry, *backbone_gw; struct batadv_bla_backbone_gw *backbone_gw_tmp = NULL; int index; - uint32_t hash_size = 1u << BATADV_BLA_BACKBONE_HASH_BITS; - - if (!hash) - return NULL; + uint32_t hash_size = ARRAY_SIZE(bat_priv->bla.backbone_hash);
ether_addr_copy(search_entry.orig, addr); search_entry.vid = vid;
index = batadv_choose_backbone_gw(&search_entry, hash_size); - head = &hash->table[index]; + head = &hash[index].head;
rcu_read_lock(); hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) { @@ -210,20 +204,19 @@ batadv_backbone_hash_find(struct batadv_priv *bat_priv, static void batadv_bla_del_backbone_claims(struct batadv_bla_backbone_gw *backbone_gw) { - struct batadv_hashtable *hash; + struct batadv_priv *bat_priv = backbone_gw->bat_priv; + struct batadv_bucket *hash; struct hlist_node *node_tmp; struct hlist_head *head; struct batadv_bla_claim *claim; int i; spinlock_t *list_lock; /* protects write access to the hash lists */
- hash = backbone_gw->bat_priv->bla.claim_hash; - if (!hash) - return; + hash = bat_priv->bla.claim_hash;
- for (i = 0; i < 1u << BATADV_BLA_CLAIM_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.claim_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(claim, node_tmp, @@ -394,7 +387,6 @@ batadv_bla_get_backbone_gw(struct batadv_priv *bat_priv, uint8_t *orig, atomic_set(&entry->refcount, 2);
hash_added = batadv_hash_add(bat_priv->bla.backbone_hash, - 1u << BATADV_BLA_BACKBONE_HASH_BITS, batadv_compare_backbone_gw, batadv_choose_backbone_gw, entry, &entry->hash_entry); @@ -459,7 +451,7 @@ static void batadv_bla_answer_request(struct batadv_priv *bat_priv, unsigned short vid) { struct hlist_head *head; - struct batadv_hashtable *hash; + struct batadv_bucket *hash; struct batadv_bla_claim *claim; struct batadv_bla_backbone_gw *backbone_gw; int i; @@ -474,8 +466,8 @@ static void batadv_bla_answer_request(struct batadv_priv *bat_priv, return;
hash = bat_priv->bla.claim_hash; - for (i = 0; i < 1u << BATADV_BLA_CLAIM_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.claim_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(claim, head, hash_entry) { @@ -578,7 +570,6 @@ static void batadv_bla_add_claim(struct batadv_priv *bat_priv, "bla_add_claim(): adding new entry %pM, vid %d to hash ...\n", mac, BATADV_PRINT_VID(vid)); hash_added = batadv_hash_add(bat_priv->bla.claim_hash, - 1u << BATADV_BLA_CLAIM_HASH_BITS, batadv_compare_claim, batadv_choose_claim, claim, &claim->hash_entry); @@ -629,9 +620,8 @@ static void batadv_bla_del_claim(struct batadv_priv *bat_priv, batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla_del_claim(): %pM, vid %d\n", mac, BATADV_PRINT_VID(vid));
- batadv_hash_remove(bat_priv->bla.claim_hash, - 1u << BATADV_BLA_CLAIM_HASH_BITS, - batadv_compare_claim, batadv_choose_claim, claim); + batadv_hash_remove(bat_priv->bla.claim_hash, batadv_compare_claim, + batadv_choose_claim, claim); batadv_claim_free_ref(claim); /* reference from the hash is gone */
claim->backbone_gw->crc ^= crc16(0, claim->addr, ETH_ALEN); @@ -990,17 +980,15 @@ static void batadv_bla_purge_backbone_gw(struct batadv_priv *bat_priv, int now) struct batadv_bla_backbone_gw *backbone_gw; struct hlist_node *node_tmp; struct hlist_head *head; - struct batadv_hashtable *hash; + struct batadv_bucket *hash; spinlock_t *list_lock; /* protects write access to the hash lists */ int i;
hash = bat_priv->bla.backbone_hash; - if (!hash) - return;
- for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.backbone_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(backbone_gw, node_tmp, @@ -1044,15 +1032,13 @@ static void batadv_bla_purge_claims(struct batadv_priv *bat_priv, { struct batadv_bla_claim *claim; struct hlist_head *head; - struct batadv_hashtable *hash; + struct batadv_bucket *hash; int i;
hash = bat_priv->bla.claim_hash; - if (!hash) - return;
- for (i = 0; i < 1u << BATADV_BLA_CLAIM_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.claim_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(claim, head, hash_entry) { @@ -1092,7 +1078,7 @@ void batadv_bla_update_orig_address(struct batadv_priv *bat_priv, { struct batadv_bla_backbone_gw *backbone_gw; struct hlist_head *head; - struct batadv_hashtable *hash; + struct batadv_bucket *hash; __be16 group; int i;
@@ -1111,11 +1097,9 @@ void batadv_bla_update_orig_address(struct batadv_priv *bat_priv, }
hash = bat_priv->bla.backbone_hash; - if (!hash) - return;
- for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.backbone_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) { @@ -1146,7 +1130,7 @@ static void batadv_bla_periodic_work(struct work_struct *work) struct batadv_priv_bla *priv_bla; struct hlist_head *head; struct batadv_bla_backbone_gw *backbone_gw; - struct batadv_hashtable *hash; + struct batadv_bucket *hash; struct batadv_hard_iface *primary_if; int i;
@@ -1164,11 +1148,9 @@ static void batadv_bla_periodic_work(struct work_struct *work) goto out;
hash = bat_priv->bla.backbone_hash; - if (!hash) - goto out;
- for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.backbone_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) { @@ -1208,14 +1190,6 @@ out: msecs_to_jiffies(BATADV_BLA_PERIOD_LENGTH)); }
-/* The hash for claim and backbone hash receive the same key because they - * are getting initialized by hash_new with the same key. Reinitializing - * them with to different keys to allow nested locking without generating - * lockdep warnings - */ -static struct lock_class_key batadv_claim_hash_lock_class_key; -static struct lock_class_key batadv_backbone_hash_lock_class_key; - /* initialize all bla structures */ int batadv_bla_init(struct batadv_priv *bat_priv) { @@ -1224,8 +1198,6 @@ int batadv_bla_init(struct batadv_priv *bat_priv) struct batadv_hard_iface *primary_if; uint16_t crc; unsigned long entrytime; - uint32_t hash_claim_size = 1u << BATADV_BLA_CLAIM_HASH_BITS; - uint32_t hash_backbone_size = 1u << BATADV_BLA_BACKBONE_HASH_BITS;
spin_lock_init(&bat_priv->bla.bcast_duplist_lock);
@@ -1249,21 +1221,8 @@ int batadv_bla_init(struct batadv_priv *bat_priv) bat_priv->bla.bcast_duplist[i].entrytime = entrytime; bat_priv->bla.bcast_duplist_curr = 0;
- if (bat_priv->bla.claim_hash) - return 0; - - bat_priv->bla.claim_hash = batadv_hash_new(hash_claim_size); - bat_priv->bla.backbone_hash = batadv_hash_new(hash_backbone_size); - - if (!bat_priv->bla.claim_hash || !bat_priv->bla.backbone_hash) - return -ENOMEM; - - batadv_hash_set_lock_class(bat_priv->bla.claim_hash, - 1u << BATADV_BLA_CLAIM_HASH_BITS, - &batadv_claim_hash_lock_class_key); - batadv_hash_set_lock_class(bat_priv->bla.backbone_hash, - 1u << BATADV_BLA_CLAIM_HASH_BITS, - &batadv_backbone_hash_lock_class_key); + batadv_hash_init(bat_priv->bla.claim_hash); + batadv_hash_init(bat_priv->bla.backbone_hash);
batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla hashes initialized\n");
@@ -1357,7 +1316,7 @@ out: bool batadv_bla_is_backbone_gw_orig(struct batadv_priv *bat_priv, uint8_t *orig, unsigned short vid) { - struct batadv_hashtable *hash = bat_priv->bla.backbone_hash; + struct batadv_bucket *hash = bat_priv->bla.backbone_hash; struct hlist_head *head; struct batadv_bla_backbone_gw *backbone_gw; int i; @@ -1365,11 +1324,8 @@ bool batadv_bla_is_backbone_gw_orig(struct batadv_priv *bat_priv, uint8_t *orig, if (!atomic_read(&bat_priv->bridge_loop_avoidance)) return false;
- if (!hash) - return false; - - for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.backbone_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) { @@ -1428,16 +1384,9 @@ void batadv_bla_free(struct batadv_priv *bat_priv) cancel_delayed_work_sync(&bat_priv->bla.work); primary_if = batadv_primary_if_get_selected(bat_priv);
- if (bat_priv->bla.claim_hash) { - batadv_bla_purge_claims(bat_priv, primary_if, 1); - batadv_hash_destroy(bat_priv->bla.claim_hash); - bat_priv->bla.claim_hash = NULL; - } - if (bat_priv->bla.backbone_hash) { - batadv_bla_purge_backbone_gw(bat_priv, 1); - batadv_hash_destroy(bat_priv->bla.backbone_hash); - bat_priv->bla.backbone_hash = NULL; - } + batadv_bla_purge_claims(bat_priv, primary_if, 1); + batadv_bla_purge_backbone_gw(bat_priv, 1); + if (primary_if) batadv_hardif_free_ref(primary_if); } @@ -1629,7 +1578,7 @@ int batadv_bla_claim_table_seq_print_text(struct seq_file *seq, void *offset) { struct net_device *net_dev = (struct net_device *)seq->private; struct batadv_priv *bat_priv = netdev_priv(net_dev); - struct batadv_hashtable *hash = bat_priv->bla.claim_hash; + struct batadv_bucket *hash = bat_priv->bla.claim_hash; struct batadv_bla_claim *claim; struct batadv_hard_iface *primary_if; struct hlist_head *head; @@ -1648,8 +1597,8 @@ int batadv_bla_claim_table_seq_print_text(struct seq_file *seq, void *offset) ntohs(bat_priv->bla.claim_dest.group)); seq_printf(seq, " %-17s %-5s %-17s [o] (%-6s)\n", "Client", "VID", "Originator", "CRC"); - for (i = 0; i < 1u << BATADV_BLA_CLAIM_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.claim_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(claim, head, hash_entry) { @@ -1673,7 +1622,7 @@ int batadv_bla_backbone_table_seq_print_text(struct seq_file *seq, void *offset) { struct net_device *net_dev = (struct net_device *)seq->private; struct batadv_priv *bat_priv = netdev_priv(net_dev); - struct batadv_hashtable *hash = bat_priv->bla.backbone_hash; + struct batadv_bucket *hash = bat_priv->bla.backbone_hash; struct batadv_bla_backbone_gw *backbone_gw; struct batadv_hard_iface *primary_if; struct hlist_head *head; @@ -1693,8 +1642,8 @@ int batadv_bla_backbone_table_seq_print_text(struct seq_file *seq, void *offset) ntohs(bat_priv->bla.claim_dest.group)); seq_printf(seq, " %-17s %-5s %-9s (%-6s)\n", "Originator", "VID", "last seen", "CRC"); - for (i = 0; i < 1u << BATADV_BLA_BACKBONE_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->bla.backbone_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) { diff --git a/distributed-arp-table.c b/distributed-arp-table.c index a027e75..b40789a 100644 --- a/distributed-arp-table.c +++ b/distributed-arp-table.c @@ -85,12 +85,9 @@ static void __batadv_dat_purge(struct batadv_priv *bat_priv, struct hlist_head *head; uint32_t i;
- if (!bat_priv->dat.hash) - return; - - for (i = 0; i < 1u << BATADV_DAT_HASH_BITS; i++) { - head = &bat_priv->dat.hash->table[i]; - list_lock = &bat_priv->dat.hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->dat.hash); i++) { + head = &bat_priv->dat.hash[i].head; + list_lock = &bat_priv->dat.hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(dat_entry, node_tmp, head, @@ -245,17 +242,14 @@ batadv_dat_entry_hash_find(struct batadv_priv *bat_priv, __be32 ip, { struct hlist_head *head; struct batadv_dat_entry to_find, *dat_entry, *dat_entry_tmp = NULL; - struct batadv_hashtable *hash = bat_priv->dat.hash; + struct batadv_bucket *hash = bat_priv->dat.hash; uint32_t index;
- if (!hash) - return NULL; - to_find.ip = ip; to_find.vid = vid;
- index = batadv_hash_dat(&to_find, 1u << BATADV_DAT_HASH_BITS); - head = &hash->table[index]; + index = batadv_hash_dat(&to_find, ARRAY_SIZE(bat_priv->dat.hash)); + head = &hash[index].head;
rcu_read_lock(); hlist_for_each_entry_rcu(dat_entry, head, hash_entry) { @@ -309,9 +303,7 @@ static void batadv_dat_entry_add(struct batadv_priv *bat_priv, __be32 ip, dat_entry->last_update = jiffies; atomic_set(&dat_entry->refcount, 2);
- hash_added = batadv_hash_add(bat_priv->dat.hash, - 1u << BATADV_DAT_HASH_BITS, - batadv_compare_dat, + hash_added = batadv_hash_add(bat_priv->dat.hash, batadv_compare_dat, batadv_hash_dat, dat_entry, &dat_entry->hash_entry);
@@ -482,7 +474,7 @@ static void batadv_choose_next_candidate(struct batadv_priv *bat_priv, { batadv_dat_addr_t max = 0, tmp_max = 0; struct batadv_orig_node *orig_node, *max_orig_node = NULL; - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct hlist_head *head; int i;
@@ -494,8 +486,8 @@ static void batadv_choose_next_candidate(struct batadv_priv *bat_priv, /* iterate over the originator list and find the node with the closest * dat_address which has not been selected yet */ - for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(orig_node, head, hash_entry) { @@ -549,9 +541,6 @@ batadv_dat_select_candidates(struct batadv_priv *bat_priv, __be32 ip_dst) batadv_dat_addr_t last_max = BATADV_DAT_ADDR_MAX, ip_key; struct batadv_dat_candidate *res;
- if (!bat_priv->orig_hash) - return NULL; - res = kmalloc_array(BATADV_DAT_CANDIDATES_NUM, sizeof(*res), GFP_ATOMIC); if (!res) @@ -708,14 +697,7 @@ static void batadv_dat_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv, */ static void batadv_dat_hash_free(struct batadv_priv *bat_priv) { - if (!bat_priv->dat.hash) - return; - __batadv_dat_purge(bat_priv, NULL); - - batadv_hash_destroy(bat_priv->dat.hash); - - bat_priv->dat.hash = NULL; }
/** @@ -724,13 +706,7 @@ static void batadv_dat_hash_free(struct batadv_priv *bat_priv) */ int batadv_dat_init(struct batadv_priv *bat_priv) { - if (bat_priv->dat.hash) - return 0; - - bat_priv->dat.hash = batadv_hash_new(1u << BATADV_DAT_HASH_BITS); - - if (!bat_priv->dat.hash) - return -ENOMEM; + batadv_hash_init(bat_priv->dat.hash);
batadv_dat_start_timer(bat_priv);
@@ -764,7 +740,7 @@ int batadv_dat_cache_seq_print_text(struct seq_file *seq, void *offset) { struct net_device *net_dev = (struct net_device *)seq->private; struct batadv_priv *bat_priv = netdev_priv(net_dev); - struct batadv_hashtable *hash = bat_priv->dat.hash; + struct batadv_bucket *hash = bat_priv->dat.hash; struct batadv_dat_entry *dat_entry; struct batadv_hard_iface *primary_if; struct hlist_head *head; @@ -780,8 +756,8 @@ int batadv_dat_cache_seq_print_text(struct seq_file *seq, void *offset) seq_printf(seq, " %-7s %-9s %4s %11s\n", "IPv4", "MAC", "VID", "last-seen");
- for (i = 0; i < 1u << BATADV_DAT_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->dat.hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(dat_entry, head, hash_entry) { diff --git a/hash.c b/hash.c deleted file mode 100644 index 8e8d934..0000000 --- a/hash.c +++ /dev/null @@ -1,75 +0,0 @@ -/* Copyright (C) 2006-2014 B.A.T.M.A.N. contributors: - * - * Simon Wunderlich, Marek Lindner - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of version 2 of the GNU General Public - * License as published by the Free Software Foundation. - * - * This program 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 - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, see http://www.gnu.org/licenses/. - */ - -#include "main.h" -#include "hash.h" - -/* clears the hash */ -static void batadv_hash_init(struct batadv_hashtable *hash, uint32_t size) -{ - uint32_t i; - - for (i = 0; i < size; i++) { - INIT_HLIST_HEAD(&hash->table[i]); - spin_lock_init(&hash->list_locks[i]); - } -} - -/* free only the hashtable and the hash itself. */ -void batadv_hash_destroy(struct batadv_hashtable *hash) -{ - kfree(hash->list_locks); - kfree(hash->table); - kfree(hash); -} - -/* allocates and clears the hash */ -struct batadv_hashtable *batadv_hash_new(uint32_t size) -{ - struct batadv_hashtable *hash; - - hash = kmalloc(sizeof(*hash), GFP_ATOMIC); - if (!hash) - return NULL; - - hash->table = kmalloc_array(size, sizeof(*hash->table), GFP_ATOMIC); - if (!hash->table) - goto free_hash; - - hash->list_locks = kmalloc_array(size, sizeof(*hash->list_locks), - GFP_ATOMIC); - if (!hash->list_locks) - goto free_table; - - batadv_hash_init(hash, size); - return hash; - -free_table: - kfree(hash->table); -free_hash: - kfree(hash); - return NULL; -} - -void batadv_hash_set_lock_class(struct batadv_hashtable *hash, uint32_t size, - struct lock_class_key *key) -{ - uint32_t i; - - for (i = 0; i < size; i++) - lockdep_set_class(&hash->list_locks[i], key); -} diff --git a/hash.h b/hash.h index c88166b..d6a23bc 100644 --- a/hash.h +++ b/hash.h @@ -20,6 +20,15 @@
#include <linux/list.h>
+#define batadv_hash_init(hashtable) \ + do { \ + uint32_t _it; \ + for (_it = 0; _it < ARRAY_SIZE(hashtable); _it++) { \ + INIT_HLIST_HEAD(&hashtable[_it].head); \ + spin_lock_init(&hashtable[_it].lock); \ + } \ + } while (0) + /* callback to a compare function. should compare 2 element datas for their * keys, return 0 if same and not 0 if not same */ @@ -33,38 +42,26 @@ typedef int (*batadv_hashdata_compare_cb)(const struct hlist_node *, typedef uint32_t (*batadv_hashdata_choose_cb)(const void *, uint32_t); typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *);
-struct batadv_hashtable { - struct hlist_head *table; /* the hashtable itself with the buckets */ - spinlock_t *list_locks; /* spinlock for each hash list entry */ -}; - -/* allocates and clears the hash */ -struct batadv_hashtable *batadv_hash_new(uint32_t size); - -/* set class key for all locks */ -void batadv_hash_set_lock_class(struct batadv_hashtable *hash, uint32_t size, - struct lock_class_key *key); - -/* free only the hashtable and the hash itself. */ -void batadv_hash_destroy(struct batadv_hashtable *hash); - /* remove the hash structure. if hashdata_free_cb != NULL, this function will be * called to remove the elements inside of the hash. if you don't remove the * elements, memory might be leaked. */ -static inline void batadv_hash_delete(struct batadv_hashtable *hash, - uint32_t size, - batadv_hashdata_free_cb free_cb, - void *arg) +#define batadv_hash_delete(hash, free_cb, arg) \ + _batadv_hash_delete(hash, ARRAY_SIZE(hash), free_cb, arg) + +static inline void _batadv_hash_delete(struct batadv_bucket *hash, + uint32_t hash_size, + batadv_hashdata_free_cb free_cb, + void *arg) { struct hlist_head *head; struct hlist_node *node, *node_tmp; spinlock_t *list_lock; /* spinlock to protect write access */ uint32_t i;
- for (i = 0; i < size; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < hash_size; i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_safe(node, node_tmp, head) { @@ -75,14 +72,11 @@ static inline void batadv_hash_delete(struct batadv_hashtable *hash, } spin_unlock_bh(list_lock); } - - batadv_hash_destroy(hash); }
/** * batadv_hash_add - adds data to the hashtable * @hash: storage hash table - * @size: size of the hashtable * @compare: callback to determine if 2 hash elements are identical * @choose: callback calculating the hash index * @data: data passed to the aforementioned callbacks as argument @@ -91,12 +85,16 @@ static inline void batadv_hash_delete(struct batadv_hashtable *hash, * Returns 0 on success, 1 if the element already is in the hash * and -1 on error. */ -static inline int batadv_hash_add(struct batadv_hashtable *hash, - uint32_t size, - batadv_hashdata_compare_cb compare, - batadv_hashdata_choose_cb choose, - const void *data, - struct hlist_node *data_node) +#define batadv_hash_add(hash, compare, choose, data, data_node) \ + _batadv_hash_add(hash, ARRAY_SIZE(hash), compare, choose, data, \ + data_node) + +static inline int _batadv_hash_add(struct batadv_bucket *hash, + uint32_t hash_size, + batadv_hashdata_compare_cb compare, + batadv_hashdata_choose_cb choose, + const void *data, + struct hlist_node *data_node) { uint32_t index; int ret = -1; @@ -107,9 +105,9 @@ static inline int batadv_hash_add(struct batadv_hashtable *hash, if (!hash) goto out;
- index = choose(data, size); - head = &hash->table[index]; - list_lock = &hash->list_locks[index]; + index = choose(data, hash_size); + head = &hash[index].head; + list_lock = &hash[index].lock;
spin_lock_bh(list_lock);
@@ -137,21 +135,24 @@ out: * structure you use with just the key filled, we just need the key for * comparing. */ -static inline void *batadv_hash_remove(struct batadv_hashtable *hash, - uint32_t size, - batadv_hashdata_compare_cb compare, - batadv_hashdata_choose_cb choose, - void *data) +#define batadv_hash_remove(hash, compare, choose, data) \ + _batadv_hash_remove(hash, ARRAY_SIZE(hash), compare, choose, data) + +static inline void *_batadv_hash_remove(struct batadv_bucket *hash, + uint32_t hash_size, + batadv_hashdata_compare_cb compare, + batadv_hashdata_choose_cb choose, + void *data) { uint32_t index; struct hlist_node *node; struct hlist_head *head; void *data_save = NULL;
- index = choose(data, size); - head = &hash->table[index]; + index = choose(data, hash_size); + head = &hash[index].head;
- spin_lock_bh(&hash->list_locks[index]); + spin_lock_bh(&hash[index].lock); hlist_for_each(node, head) { if (!compare(node, data)) continue; @@ -160,7 +161,7 @@ static inline void *batadv_hash_remove(struct batadv_hashtable *hash, hlist_del_rcu(node); break; } - spin_unlock_bh(&hash->list_locks[index]); + spin_unlock_bh(&hash[index].lock);
return data_save; } diff --git a/network-coding.c b/network-coding.c index 6f0ceb4..cb0c7ab 100644 --- a/network-coding.c +++ b/network-coding.c @@ -25,9 +25,6 @@ #include "hard-interface.h" #include "routing.h"
-static struct lock_class_key batadv_nc_coding_hash_lock_class_key; -static struct lock_class_key batadv_nc_decoding_hash_lock_class_key; - static void batadv_nc_worker(struct work_struct *work); static int batadv_nc_recv_coded_packet(struct sk_buff *skb, struct batadv_hard_iface *recv_if); @@ -116,30 +113,12 @@ static void batadv_nc_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv, */ int batadv_nc_mesh_init(struct batadv_priv *bat_priv) { - uint32_t hash_coding_size = 1u << BATADV_NC_CODING_HASH_BITS; - uint32_t hash_decoding_size = 1u << BATADV_NC_DECODING_HASH_BITS;
bat_priv->nc.timestamp_fwd_flush = jiffies; bat_priv->nc.timestamp_sniffed_purge = jiffies;
- if (bat_priv->nc.coding_hash || bat_priv->nc.decoding_hash) - return 0; - - bat_priv->nc.coding_hash = batadv_hash_new(hash_coding_size); - if (!bat_priv->nc.coding_hash) - goto err; - - batadv_hash_set_lock_class(bat_priv->nc.coding_hash, - 1u << BATADV_NC_CODING_HASH_BITS, - &batadv_nc_coding_hash_lock_class_key); - - bat_priv->nc.decoding_hash = batadv_hash_new(hash_decoding_size); - if (!bat_priv->nc.decoding_hash) - goto err; - - batadv_hash_set_lock_class(bat_priv->nc.decoding_hash, - 1u << BATADV_NC_DECODING_HASH_BITS, - &batadv_nc_decoding_hash_lock_class_key); + batadv_hash_init(bat_priv->nc.coding_hash); + batadv_hash_init(bat_priv->nc.decoding_hash);
INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker); batadv_nc_start_timer(bat_priv); @@ -149,9 +128,6 @@ int batadv_nc_mesh_init(struct batadv_priv *bat_priv) BATADV_TVLV_HANDLER_OGM_CIFNOTFND); batadv_nc_tvlv_container_update(bat_priv); return 0; - -err: - return -ENOMEM; }
/** @@ -354,17 +330,14 @@ void batadv_nc_purge_orig(struct batadv_priv *bat_priv, */ static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv) { - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct hlist_head *head; struct batadv_orig_node *orig_node; uint32_t i;
- if (!hash) - return; - /* For each orig_node */ - for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(orig_node, head, hash_entry) @@ -374,8 +347,11 @@ static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv) } }
+#define batadv_nc_purge_paths(bat_priv, hash, to_purge) \ + _batadv_nc_purge_paths(bat_priv, hash, ARRAY_SIZE(hash), to_purge) + /** - * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove + * _batadv_nc_purge_paths - traverse all nc paths part of the hash and remove * unused ones * @bat_priv: the bat priv with all the soft interface information * @hash: hash table containing the nc paths to check @@ -385,11 +361,11 @@ static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv) * a boolean value: true is the entry has to be deleted, false * otherwise */ -static void batadv_nc_purge_paths(struct batadv_priv *bat_priv, - struct batadv_hashtable *hash, - uint32_t hash_size, - bool (*to_purge)(struct batadv_priv *, - struct batadv_nc_path *)) +static void _batadv_nc_purge_paths(struct batadv_priv *bat_priv, + struct batadv_bucket *hash, + uint32_t hash_size, + bool (*to_purge)(struct batadv_priv *, + struct batadv_nc_path *)) { struct hlist_head *head; struct hlist_node *node_tmp; @@ -398,8 +374,8 @@ static void batadv_nc_purge_paths(struct batadv_priv *bat_priv, uint32_t i;
for (i = 0; i < hash_size; i++) { - head = &hash->table[i]; - lock = &hash->list_locks[i]; + head = &hash[i].head; + lock = &hash[i].lock;
/* For each nc_path in this bin */ spin_lock_bh(lock); @@ -503,18 +479,15 @@ static int batadv_nc_hash_compare(const struct hlist_node *node, * Returns the nc_path if found, NULL otherwise. */ static struct batadv_nc_path * -batadv_nc_hash_find(struct batadv_hashtable *hash, uint32_t hash_size, +batadv_nc_hash_find(struct batadv_bucket *hash, uint32_t hash_size, void *data) { struct hlist_head *head; struct batadv_nc_path *nc_path, *nc_path_tmp = NULL; int index;
- if (!hash) - return NULL; - index = batadv_nc_hash_choose(data, hash_size); - head = &hash->table[index]; + head = &hash[index].head;
rcu_read_lock(); hlist_for_each_entry_rcu(nc_path, head, hash_entry) { @@ -618,9 +591,13 @@ static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv, return true; }
+#define batadv_nc_process_nc_paths(bat_priv, hash, process_fn) \ + _batadv_nc_process_nc_paths(bat_priv, hash, ARRAY_SIZE(hash), \ + process_fn) + /** - * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed out - * nc packets + * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed + * out nc packets * @bat_priv: the bat priv with all the soft interface information * @hash: to be processed hash table * @hash_size: number of buckets in the hashtable @@ -629,11 +606,11 @@ static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv, * Otherwise the rest of the current queue is skipped. */ static void -batadv_nc_process_nc_paths(struct batadv_priv *bat_priv, - struct batadv_hashtable *hash, uint32_t hash_size, - bool (*process_fn)(struct batadv_priv *, - struct batadv_nc_path *, - struct batadv_nc_packet *)) +_batadv_nc_process_nc_paths(struct batadv_priv *bat_priv, + struct batadv_bucket *hash, uint32_t hash_size, + bool (*process_fn)(struct batadv_priv *, + struct batadv_nc_path *, + struct batadv_nc_packet *)) { struct hlist_head *head; struct batadv_nc_packet *nc_packet, *nc_packet_tmp; @@ -641,12 +618,9 @@ batadv_nc_process_nc_paths(struct batadv_priv *bat_priv, bool ret; int i;
- if (!hash) - return; - /* Loop hash table bins */ for (i = 0; i < hash_size; i++) { - head = &hash->table[i]; + head = &hash[i].head;
/* Loop coding paths */ rcu_read_lock(); @@ -682,17 +656,14 @@ static void batadv_nc_worker(struct work_struct *work)
batadv_nc_purge_orig_hash(bat_priv); batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, - 1u << BATADV_NC_CODING_HASH_BITS, batadv_nc_to_purge_nc_path_coding); batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, - 1u << BATADV_NC_DECODING_HASH_BITS, batadv_nc_to_purge_nc_path_decoding);
timeout = bat_priv->nc.max_fwd_delay;
if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) { batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash, - 1u << BATADV_NC_CODING_HASH_BITS, batadv_nc_fwd_flush); bat_priv->nc.timestamp_fwd_flush = jiffies; } @@ -700,7 +671,6 @@ static void batadv_nc_worker(struct work_struct *work) if (batadv_has_timed_out(bat_priv->nc.timestamp_sniffed_purge, bat_priv->nc.max_buffer_time)) { batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.decoding_hash, - 1u << BATADV_NC_DECODING_HASH_BITS, batadv_nc_sniffed_purge); bat_priv->nc.timestamp_sniffed_purge = jiffies; } @@ -921,7 +891,7 @@ out: * on error. */ static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv, - struct batadv_hashtable *hash, + struct batadv_bucket *hash, uint32_t hash_size, uint8_t *src, uint8_t *dst) @@ -959,9 +929,9 @@ static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv, nc_path->next_hop);
/* Add nc_path to hash table */ - hash_added = batadv_hash_add(hash, hash_size, batadv_nc_hash_compare, - batadv_nc_hash_choose, &nc_path_key, - &nc_path->hash_entry); + hash_added = _batadv_hash_add(hash, hash_size, batadv_nc_hash_compare, + batadv_nc_hash_choose, &nc_path_key, + &nc_path->hash_entry);
if (hash_added < 0) { kfree(nc_path); @@ -1245,21 +1215,18 @@ batadv_nc_path_search(struct batadv_priv *bat_priv, struct batadv_nc_path *nc_path, nc_path_key; struct batadv_nc_packet *nc_packet_out = NULL; struct batadv_nc_packet *nc_packet, *nc_packet_tmp; - struct batadv_hashtable *hash = bat_priv->nc.coding_hash; + struct batadv_bucket *hash = bat_priv->nc.coding_hash; int idx;
- if (!hash) - return NULL; - /* Create almost path key */ batadv_nc_hash_key_gen(&nc_path_key, in_nc_node->addr, out_nc_node->addr); idx = batadv_nc_hash_choose(&nc_path_key, - 1u << BATADV_NC_CODING_HASH_BITS); + ARRAY_SIZE(bat_priv->nc.coding_hash));
/* Check for coding opportunities in this nc_path */ rcu_read_lock(); - hlist_for_each_entry_rcu(nc_path, &hash->table[idx], hash_entry) { + hlist_for_each_entry_rcu(nc_path, &hash[idx].head, hash_entry) { if (!batadv_compare_eth(nc_path->prev_hop, in_nc_node->addr)) continue;
@@ -1503,7 +1470,7 @@ bool batadv_nc_skb_forward(struct sk_buff *skb, /* Find or create a nc_path for this src-dst pair */ nc_path = batadv_nc_get_path(bat_priv, bat_priv->nc.coding_hash, - 1u << BATADV_NC_CODING_HASH_BITS, + ARRAY_SIZE(bat_priv->nc.coding_hash), ethhdr->h_source, neigh_node->addr);
@@ -1553,7 +1520,7 @@ void batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv, /* Find existing nc_path or create a new */ nc_path = batadv_nc_get_path(bat_priv, bat_priv->nc.decoding_hash, - 1u << BATADV_NC_DECODING_HASH_BITS, + ARRAY_SIZE(bat_priv->nc.decoding_hash), ethhdr->h_source, ethhdr->h_dest);
@@ -1715,16 +1682,13 @@ batadv_nc_find_decoding_packet(struct batadv_priv *bat_priv, struct ethhdr *ethhdr, struct batadv_coded_packet *coded) { - struct batadv_hashtable *hash = bat_priv->nc.decoding_hash; + struct batadv_bucket *hash = bat_priv->nc.decoding_hash; struct batadv_nc_packet *tmp_nc_packet, *nc_packet = NULL; struct batadv_nc_path *nc_path, nc_path_key; uint8_t *dest, *source; __be32 packet_id; int index;
- if (!hash) - return NULL; - /* Select the correct packet id based on the location of our mac-addr */ dest = ethhdr->h_source; if (!batadv_is_my_mac(bat_priv, coded->second_dest)) { @@ -1737,11 +1701,11 @@ batadv_nc_find_decoding_packet(struct batadv_priv *bat_priv,
batadv_nc_hash_key_gen(&nc_path_key, source, dest); index = batadv_nc_hash_choose(&nc_path_key, - 1u << BATADV_NC_DECODING_HASH_BITS); + ARRAY_SIZE(bat_priv->nc.decoding_hash));
/* Search for matching coding path */ rcu_read_lock(); - hlist_for_each_entry_rcu(nc_path, &hash->table[index], hash_entry) { + hlist_for_each_entry_rcu(nc_path, &hash[index].head, hash_entry) { /* Find matching nc_packet */ spin_lock_bh(&nc_path->packet_list_lock); list_for_each_entry(tmp_nc_packet, @@ -1846,12 +1810,8 @@ void batadv_nc_mesh_free(struct batadv_priv *bat_priv) batadv_tvlv_handler_unregister(bat_priv, BATADV_TVLV_NC, 1); cancel_delayed_work_sync(&bat_priv->nc.work);
- batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, - 1u << BATADV_NC_CODING_HASH_BITS, NULL); - batadv_hash_destroy(bat_priv->nc.coding_hash); - batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, - 1u << BATADV_NC_DECODING_HASH_BITS, NULL); - batadv_hash_destroy(bat_priv->nc.decoding_hash); + batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL); + batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, NULL); }
/** @@ -1863,7 +1823,7 @@ int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset) { struct net_device *net_dev = (struct net_device *)seq->private; struct batadv_priv *bat_priv = netdev_priv(net_dev); - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct batadv_hard_iface *primary_if; struct hlist_head *head; struct batadv_orig_node *orig_node; @@ -1875,8 +1835,8 @@ int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset) goto out;
/* Traverse list of originators */ - for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head;
/* For each orig_node in this bin */ rcu_read_lock(); diff --git a/originator.c b/originator.c index 55baa3d..22996ec 100644 --- a/originator.c +++ b/originator.c @@ -29,9 +29,6 @@ #include "fragmentation.h" #include "multicast.h"
-/* hash class keys */ -static struct lock_class_key batadv_orig_hash_lock_class_key; - static void batadv_purge_orig(struct work_struct *work);
/* returns 1 if they are the same originator */ @@ -127,17 +124,7 @@ void batadv_orig_node_vlan_free_ref(struct batadv_orig_node_vlan *orig_vlan)
int batadv_originator_init(struct batadv_priv *bat_priv) { - if (bat_priv->orig_hash) - return 0; - - bat_priv->orig_hash = batadv_hash_new(1u << BATADV_ORIG_HASH_BITS); - - if (!bat_priv->orig_hash) - goto err; - - batadv_hash_set_lock_class(bat_priv->orig_hash, - 1u << BATADV_ORIG_HASH_BITS, - &batadv_orig_hash_lock_class_key); + batadv_hash_init(bat_priv->orig_hash);
INIT_DELAYED_WORK(&bat_priv->orig_work, batadv_purge_orig); queue_delayed_work(batadv_event_workqueue, @@ -145,9 +132,6 @@ int batadv_originator_init(struct batadv_priv *bat_priv) msecs_to_jiffies(BATADV_ORIG_WORK_PERIOD));
return 0; - -err: - return -ENOMEM; }
/** @@ -602,23 +586,18 @@ void batadv_orig_node_free_ref_now(struct batadv_orig_node *orig_node)
void batadv_originator_free(struct batadv_priv *bat_priv) { - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct hlist_node *node_tmp; struct hlist_head *head; spinlock_t *list_lock; /* spinlock to protect write access */ struct batadv_orig_node *orig_node; uint32_t i;
- if (!hash) - return; - cancel_delayed_work_sync(&bat_priv->orig_work);
- bat_priv->orig_hash = NULL; - - for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(orig_node, node_tmp, @@ -628,8 +607,6 @@ void batadv_originator_free(struct batadv_priv *bat_priv) } spin_unlock_bh(list_lock); } - - batadv_hash_destroy(hash); }
/** @@ -954,20 +931,17 @@ static bool batadv_purge_orig_node(struct batadv_priv *bat_priv,
static void _batadv_purge_orig(struct batadv_priv *bat_priv) { - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct hlist_node *node_tmp; struct hlist_head *head; spinlock_t *list_lock; /* spinlock to protect write access */ struct batadv_orig_node *orig_node; uint32_t i;
- if (!hash) - return; - /* for all origins... */ - for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(orig_node, node_tmp, @@ -1090,7 +1064,7 @@ int batadv_orig_hash_add_if(struct batadv_hard_iface *hard_iface, { struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); struct batadv_algo_ops *bao = bat_priv->bat_algo_ops; - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct hlist_head *head; struct batadv_orig_node *orig_node; uint32_t i; @@ -1099,8 +1073,8 @@ int batadv_orig_hash_add_if(struct batadv_hard_iface *hard_iface, /* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ - for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(orig_node, head, hash_entry) { @@ -1125,7 +1099,7 @@ int batadv_orig_hash_del_if(struct batadv_hard_iface *hard_iface, int max_if_num) { struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct hlist_head *head; struct batadv_hard_iface *hard_iface_tmp; struct batadv_orig_node *orig_node; @@ -1136,8 +1110,8 @@ int batadv_orig_hash_del_if(struct batadv_hard_iface *hard_iface, /* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ - for (i = 0; i < 1u << BATADV_ORIG_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->orig_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(orig_node, head, hash_entry) { diff --git a/originator.h b/originator.h index 89b810d..e0eb8fc 100644 --- a/originator.h +++ b/originator.h @@ -84,16 +84,13 @@ static inline uint32_t batadv_choose_orig(const void *data, uint32_t size) static inline struct batadv_orig_node * batadv_orig_hash_find(struct batadv_priv *bat_priv, const void *data) { - struct batadv_hashtable *hash = bat_priv->orig_hash; + struct batadv_bucket *hash = bat_priv->orig_hash; struct hlist_head *head; struct batadv_orig_node *orig_node, *orig_node_tmp = NULL; int index;
- if (!hash) - return NULL; - - index = batadv_choose_orig(data, 1u << BATADV_ORIG_HASH_BITS); - head = &hash->table[index]; + index = batadv_choose_orig(data, ARRAY_SIZE(bat_priv->orig_hash)); + head = &hash[index].head;
rcu_read_lock(); hlist_for_each_entry_rcu(orig_node, head, hash_entry) { diff --git a/translation-table.c b/translation-table.c index 60be9c6..81a5793 100644 --- a/translation-table.c +++ b/translation-table.c @@ -28,10 +28,6 @@
#include <linux/crc32c.h>
-/* hash class keys */ -static struct lock_class_key batadv_tt_local_hash_lock_class_key; -static struct lock_class_key batadv_tt_global_hash_lock_class_key; - static void batadv_send_roam_adv(struct batadv_priv *bat_priv, uint8_t *client, unsigned short vid, struct batadv_orig_node *orig_node); @@ -73,8 +69,11 @@ static inline uint32_t batadv_choose_tt(const void *data, uint32_t size) return hash % size; }
+#define batadv_tt_hash_find(hash, addr, vid) \ + _batadv_tt_hash_find(hash, ARRAY_SIZE(hash), addr, vid) + /** - * batadv_tt_hash_find - look for a client in the given hash table + * _batadv_tt_hash_find - look for a client in the given hash table * @hash: the hash table to search * @addr: the mac address of the client to look for * @vid: VLAN identifier @@ -83,21 +82,18 @@ static inline uint32_t batadv_choose_tt(const void *data, uint32_t size) * found, NULL otherwise. */ static struct batadv_tt_common_entry * -batadv_tt_hash_find(struct batadv_hashtable *hash, uint32_t size, - const uint8_t *addr, unsigned short vid) +_batadv_tt_hash_find(struct batadv_bucket *hash, uint32_t size, + const uint8_t *addr, unsigned short vid) { struct hlist_head *head; struct batadv_tt_common_entry to_search, *tt, *tt_tmp = NULL; uint32_t index;
- if (!hash) - return NULL; - ether_addr_copy(to_search.addr, addr); to_search.vid = vid;
index = batadv_choose_tt(&to_search, size); - head = &hash->table[index]; + head = &hash[index].head;
rcu_read_lock(); hlist_for_each_entry_rcu(tt, head, hash_entry) { @@ -134,9 +130,8 @@ batadv_tt_local_hash_find(struct batadv_priv *bat_priv, const uint8_t *addr, struct batadv_tt_common_entry *tt_common_entry; struct batadv_tt_local_entry *tt_local_entry = NULL;
- tt_common_entry = batadv_tt_hash_find(bat_priv->tt.local_hash, - 1u << BATADV_TT_LOCAL_HASH_BITS, - addr, vid); + tt_common_entry = batadv_tt_hash_find(bat_priv->tt.local_hash, addr, + vid); if (tt_common_entry) tt_local_entry = container_of(tt_common_entry, struct batadv_tt_local_entry, @@ -160,9 +155,8 @@ batadv_tt_global_hash_find(struct batadv_priv *bat_priv, const uint8_t *addr, struct batadv_tt_common_entry *tt_common_entry; struct batadv_tt_global_entry *tt_global_entry = NULL;
- tt_common_entry = batadv_tt_hash_find(bat_priv->tt.global_hash, - 1u << BATADV_TT_GLOBAL_HASH_BITS, - addr, vid); + tt_common_entry = batadv_tt_hash_find(bat_priv->tt.global_hash, addr, + vid); if (tt_common_entry) tt_global_entry = container_of(tt_common_entry, struct batadv_tt_global_entry, @@ -462,18 +456,7 @@ static int batadv_tt_local_table_transmit_size(struct batadv_priv *bat_priv)
static int batadv_tt_local_init(struct batadv_priv *bat_priv) { - uint32_t hash_size = 1u << BATADV_TT_LOCAL_HASH_BITS; - - if (bat_priv->tt.local_hash) - return 0; - - bat_priv->tt.local_hash = batadv_hash_new(hash_size); - - if (!bat_priv->tt.local_hash) - return -ENOMEM; - - batadv_hash_set_lock_class(bat_priv->tt.local_hash, hash_size, - &batadv_tt_local_hash_lock_class_key); + batadv_hash_init(bat_priv->tt.local_hash);
return 0; } @@ -487,8 +470,7 @@ static void batadv_tt_global_free(struct batadv_priv *bat_priv, tt_global->common.addr, BATADV_PRINT_VID(tt_global->common.vid), message);
- batadv_hash_remove(bat_priv->tt.global_hash, - 1u << BATADV_TT_GLOBAL_HASH_BITS, batadv_compare_tt, + batadv_hash_remove(bat_priv->tt.global_hash, batadv_compare_tt, batadv_choose_tt, &tt_global->common); batadv_tt_global_entry_free_ref(tt_global); } @@ -603,7 +585,6 @@ bool batadv_tt_local_add(struct net_device *soft_iface, const uint8_t *addr, tt_local->common.flags |= BATADV_TT_CLIENT_NOPURGE;
hash_added = batadv_hash_add(bat_priv->tt.local_hash, - 1u << BATADV_TT_LOCAL_HASH_BITS, batadv_compare_tt, batadv_choose_tt, &tt_local->common, &tt_local->common.hash_entry); @@ -905,7 +886,7 @@ int batadv_tt_local_seq_print_text(struct seq_file *seq, void *offset) { struct net_device *net_dev = (struct net_device *)seq->private; struct batadv_priv *bat_priv = netdev_priv(net_dev); - struct batadv_hashtable *hash = bat_priv->tt.local_hash; + struct batadv_bucket *hash = bat_priv->tt.local_hash; struct batadv_tt_common_entry *tt_common_entry; struct batadv_tt_local_entry *tt_local; struct batadv_hard_iface *primary_if; @@ -929,8 +910,8 @@ int batadv_tt_local_seq_print_text(struct seq_file *seq, void *offset) seq_printf(seq, " %-13s %s %-8s %-9s (%-10s)\n", "Client", "VID", "Flags", "Last seen", "CRC");
- for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.local_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(tt_common_entry, @@ -1104,14 +1085,14 @@ static void batadv_tt_local_purge_list(struct batadv_priv *bat_priv, static void batadv_tt_local_purge(struct batadv_priv *bat_priv, int timeout) { - struct batadv_hashtable *hash = bat_priv->tt.local_hash; + struct batadv_bucket *hash = bat_priv->tt.local_hash; struct hlist_head *head; spinlock_t *list_lock; /* protects write access to the hash lists */ uint32_t i;
- for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.local_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); batadv_tt_local_purge_list(bat_priv, head, timeout); @@ -1121,7 +1102,7 @@ static void batadv_tt_local_purge(struct batadv_priv *bat_priv,
static void batadv_tt_local_table_free(struct batadv_priv *bat_priv) { - struct batadv_hashtable *hash; + struct batadv_bucket *hash; spinlock_t *list_lock; /* protects write access to the hash lists */ struct batadv_tt_common_entry *tt_common_entry; struct batadv_tt_local_entry *tt_local; @@ -1130,14 +1111,11 @@ static void batadv_tt_local_table_free(struct batadv_priv *bat_priv) struct hlist_head *head; uint32_t i;
- if (!bat_priv->tt.local_hash) - return; - hash = bat_priv->tt.local_hash;
- for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.local_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(tt_common_entry, node_tmp, @@ -1157,26 +1135,11 @@ static void batadv_tt_local_table_free(struct batadv_priv *bat_priv) } spin_unlock_bh(list_lock); } - - batadv_hash_destroy(hash); - - bat_priv->tt.local_hash = NULL; }
static int batadv_tt_global_init(struct batadv_priv *bat_priv) { - uint32_t hash_size = 1u << BATADV_TT_GLOBAL_HASH_BITS; - - if (bat_priv->tt.global_hash) - return 0; - - bat_priv->tt.global_hash = batadv_hash_new(hash_size); - - if (!bat_priv->tt.global_hash) - return -ENOMEM; - - batadv_hash_set_lock_class(bat_priv->tt.global_hash, hash_size, - &batadv_tt_global_hash_lock_class_key); + batadv_hash_init(bat_priv->tt.global_hash);
return 0; } @@ -1353,7 +1316,6 @@ static bool batadv_tt_global_add(struct batadv_priv *bat_priv, spin_lock_init(&tt_global_entry->list_lock);
hash_added = batadv_hash_add(bat_priv->tt.global_hash, - 1u << BATADV_TT_GLOBAL_HASH_BITS, batadv_compare_tt, batadv_choose_tt, common, &common->hash_entry); @@ -1579,7 +1541,7 @@ int batadv_tt_global_seq_print_text(struct seq_file *seq, void *offset) { struct net_device *net_dev = (struct net_device *)seq->private; struct batadv_priv *bat_priv = netdev_priv(net_dev); - struct batadv_hashtable *hash = bat_priv->tt.global_hash; + struct batadv_bucket *hash = bat_priv->tt.global_hash; struct batadv_tt_common_entry *tt_common_entry; struct batadv_tt_global_entry *tt_global; struct batadv_hard_iface *primary_if; @@ -1597,8 +1559,8 @@ int batadv_tt_global_seq_print_text(struct seq_file *seq, void *offset) "Client", "VID", "(TTVN)", "Originator", "(Curr TTVN)", "CRC", "Flags");
- for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.global_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(tt_common_entry, @@ -1810,18 +1772,15 @@ void batadv_tt_global_del_orig(struct batadv_priv *bat_priv, struct batadv_tt_global_entry *tt_global; struct batadv_tt_common_entry *tt_common_entry; uint32_t i; - struct batadv_hashtable *hash = bat_priv->tt.global_hash; + struct batadv_bucket *hash = bat_priv->tt.global_hash; struct hlist_node *safe; struct hlist_head *head; spinlock_t *list_lock; /* protects write access to the hash lists */ unsigned short vid;
- if (!hash) - return; - - for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.global_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(tt_common_entry, safe, @@ -1876,7 +1835,7 @@ static bool batadv_tt_global_to_purge(struct batadv_tt_global_entry *tt_global,
static void batadv_tt_global_purge(struct batadv_priv *bat_priv) { - struct batadv_hashtable *hash = bat_priv->tt.global_hash; + struct batadv_bucket *hash = bat_priv->tt.global_hash; struct hlist_head *head; struct hlist_node *node_tmp; spinlock_t *list_lock; /* protects write access to the hash lists */ @@ -1885,9 +1844,9 @@ static void batadv_tt_global_purge(struct batadv_priv *bat_priv) struct batadv_tt_common_entry *tt_common; struct batadv_tt_global_entry *tt_global;
- for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.global_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(tt_common, node_tmp, head, @@ -1915,7 +1874,7 @@ static void batadv_tt_global_purge(struct batadv_priv *bat_priv)
static void batadv_tt_global_table_free(struct batadv_priv *bat_priv) { - struct batadv_hashtable *hash; + struct batadv_bucket *hash; spinlock_t *list_lock; /* protects write access to the hash lists */ struct batadv_tt_common_entry *tt_common_entry; struct batadv_tt_global_entry *tt_global; @@ -1923,14 +1882,11 @@ static void batadv_tt_global_table_free(struct batadv_priv *bat_priv) struct hlist_head *head; uint32_t i;
- if (!bat_priv->tt.global_hash) - return; - hash = bat_priv->tt.global_hash;
- for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.global_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(tt_common_entry, node_tmp, @@ -1943,10 +1899,6 @@ static void batadv_tt_global_table_free(struct batadv_priv *bat_priv) } spin_unlock_bh(list_lock); } - - batadv_hash_destroy(hash); - - bat_priv->tt.global_hash = NULL; }
static bool @@ -2055,7 +2007,7 @@ static uint32_t batadv_tt_global_crc(struct batadv_priv *bat_priv, struct batadv_orig_node *orig_node, unsigned short vid) { - struct batadv_hashtable *hash = bat_priv->tt.global_hash; + struct batadv_bucket *hash = bat_priv->tt.global_hash; struct batadv_tt_common_entry *tt_common; struct batadv_tt_global_entry *tt_global; struct hlist_head *head; @@ -2063,8 +2015,8 @@ static uint32_t batadv_tt_global_crc(struct batadv_priv *bat_priv, uint8_t flags; __be16 tmp_vid;
- for (i = 0; i < 1u << BATADV_TT_GLOBAL_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.global_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(tt_common, head, hash_entry) { @@ -2131,15 +2083,15 @@ static uint32_t batadv_tt_global_crc(struct batadv_priv *bat_priv, static uint32_t batadv_tt_local_crc(struct batadv_priv *bat_priv, unsigned short vid) { - struct batadv_hashtable *hash = bat_priv->tt.local_hash; + struct batadv_bucket *hash = bat_priv->tt.local_hash; struct batadv_tt_common_entry *tt_common; struct hlist_head *head; uint32_t i, crc_tmp, crc = 0; uint8_t flags; __be16 tmp_vid;
- for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.local_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(tt_common, head, hash_entry) { @@ -2301,7 +2253,7 @@ static int batadv_tt_global_valid(const void *entry_ptr, * @cb_data: data passed to the filter function as argument */ static void batadv_tt_tvlv_generate(struct batadv_priv *bat_priv, - struct batadv_hashtable *hash, + struct batadv_bucket *hash, uint32_t hash_size, void *tvlv_buff, uint16_t tt_len, int (*valid_cb)(const void *, const void *), @@ -2318,7 +2270,7 @@ static void batadv_tt_tvlv_generate(struct batadv_priv *bat_priv,
rcu_read_lock(); for (i = 0; i < hash_size; i++) { - head = &hash->table[i]; + head = &hash[i].head;
hlist_for_each_entry_rcu(tt_common_entry, head, hash_entry) { @@ -2597,7 +2549,7 @@ static bool batadv_send_other_tt_response(struct batadv_priv *bat_priv,
/* fill the rest of the tvlv with the real TT entries */ batadv_tt_tvlv_generate(bat_priv, bat_priv->tt.global_hash, - 1u << BATADV_TT_GLOBAL_HASH_BITS, + ARRAY_SIZE(bat_priv->tt.global_hash), tt_change, tt_len, batadv_tt_global_valid, req_dst_orig_node); @@ -2727,7 +2679,7 @@ static bool batadv_send_my_tt_response(struct batadv_priv *bat_priv,
/* fill the rest of the tvlv with the real TT entries */ batadv_tt_tvlv_generate(bat_priv, bat_priv->tt.local_hash, - 1u << BATADV_TT_LOCAL_HASH_BITS, + ARRAY_SIZE(bat_priv->tt.local_hash), tt_change, tt_len, batadv_tt_local_valid, NULL); } @@ -3124,17 +3076,14 @@ void batadv_tt_free(struct batadv_priv *bat_priv) static void batadv_tt_local_set_flags(struct batadv_priv *bat_priv, uint16_t flags, bool enable, bool count) { - struct batadv_hashtable *hash = bat_priv->tt.local_hash; + struct batadv_bucket *hash = bat_priv->tt.local_hash; struct batadv_tt_common_entry *tt_common_entry; uint16_t changed_num = 0; struct hlist_head *head; uint32_t i;
- if (!hash) - return; - - for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { - head = &hash->table[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.local_hash); i++) { + head = &hash[i].head;
rcu_read_lock(); hlist_for_each_entry_rcu(tt_common_entry, @@ -3163,7 +3112,7 @@ static void batadv_tt_local_set_flags(struct batadv_priv *bat_priv, /* Purge out all the tt local entries marked with BATADV_TT_CLIENT_PENDING */ static void batadv_tt_local_purge_pending_clients(struct batadv_priv *bat_priv) { - struct batadv_hashtable *hash = bat_priv->tt.local_hash; + struct batadv_bucket *hash = bat_priv->tt.local_hash; struct batadv_tt_common_entry *tt_common; struct batadv_tt_local_entry *tt_local; struct batadv_softif_vlan *vlan; @@ -3172,12 +3121,9 @@ static void batadv_tt_local_purge_pending_clients(struct batadv_priv *bat_priv) spinlock_t *list_lock; /* protects write access to the hash lists */ uint32_t i;
- if (!hash) - return; - - for (i = 0; i < 1u << BATADV_TT_LOCAL_HASH_BITS; i++) { - head = &hash->table[i]; - list_lock = &hash->list_locks[i]; + for (i = 0; i < ARRAY_SIZE(bat_priv->tt.local_hash); i++) { + head = &hash[i].head; + list_lock = &hash[i].lock;
spin_lock_bh(list_lock); hlist_for_each_entry_safe(tt_common, node_tmp, head, diff --git a/types.h b/types.h index de09807..60fb1b5 100644 --- a/types.h +++ b/types.h @@ -35,6 +35,16 @@ #endif /* CONFIG_BATMAN_ADV_DAT */
/** + * struct batadv_bucket - bucket for concurrent, list based hashtable + * @head: pointer to the data of this bucket + * @lock: lock protecting writes to this bucket + */ +struct batadv_bucket { + struct hlist_head head; + spinlock_t lock; /* Protects head */ +}; + +/** * enum batadv_dhcp_recipient - dhcp destination * @BATADV_DHCP_NO: packet is not a dhcp message * @BATADV_DHCP_TO_SERVER: dhcp message is directed to a server @@ -517,8 +527,8 @@ struct batadv_priv_tt { atomic_t ogm_append_cnt; atomic_t local_changes; struct list_head changes_list; - struct batadv_hashtable *local_hash; - struct batadv_hashtable *global_hash; + struct batadv_bucket local_hash[1u << BATADV_TT_LOCAL_HASH_BITS]; + struct batadv_bucket global_hash[1u << BATADV_TT_GLOBAL_HASH_BITS]; struct list_head req_list; struct list_head roam_list; spinlock_t changes_list_lock; /* protects changes */ @@ -548,8 +558,8 @@ struct batadv_priv_tt { #ifdef CONFIG_BATMAN_ADV_BLA struct batadv_priv_bla { atomic_t num_requests; - struct batadv_hashtable *claim_hash; - struct batadv_hashtable *backbone_hash; + struct batadv_bucket claim_hash[1u << BATADV_BLA_CLAIM_HASH_BITS]; + struct batadv_bucket backbone_hash[1u << BATADV_BLA_BACKBONE_HASH_BITS]; struct batadv_bcast_duplist_entry bcast_duplist[BATADV_DUPLIST_SIZE]; int bcast_duplist_curr; /* protects bcast_duplist & bcast_duplist_curr */ @@ -613,12 +623,13 @@ struct batadv_priv_tvlv { * struct batadv_priv_dat - per mesh interface DAT private data * @addr: node DAT address * @hash: hashtable representing the local ARP cache + * @hash_lock: locks for each hashtable buckets * @work: work queue callback item for cache purging */ #ifdef CONFIG_BATMAN_ADV_DAT struct batadv_priv_dat { batadv_dat_addr_t addr; - struct batadv_hashtable *hash; + struct batadv_bucket hash[1u << BATADV_DAT_HASH_BITS]; struct delayed_work work; }; #endif @@ -681,8 +692,8 @@ struct batadv_priv_nc { u32 max_buffer_time; unsigned long timestamp_fwd_flush; unsigned long timestamp_sniffed_purge; - struct batadv_hashtable *coding_hash; - struct batadv_hashtable *decoding_hash; + struct batadv_bucket coding_hash[1u << BATADV_NC_CODING_HASH_BITS]; + struct batadv_bucket decoding_hash[1u << BATADV_NC_DECODING_HASH_BITS]; };
/** @@ -795,7 +806,7 @@ struct batadv_priv { struct dentry *debug_dir; struct hlist_head forw_bat_list; struct hlist_head forw_bcast_list; - struct batadv_hashtable *orig_hash; + struct batadv_bucket orig_hash[1u << BATADV_ORIG_HASH_BITS]; spinlock_t forw_bat_list_lock; /* protects forw_bat_list */ spinlock_t forw_bcast_list_lock; /* protects forw_bcast_list */ struct delayed_work orig_work;
b.a.t.m.a.n@lists.open-mesh.org
-
Sven Eckelmann