From: Marek Lindner lindner_marek@yahoo.de

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- Removed hashtable_t::elements

batman-adv/hash.c | 3 --- batman-adv/hash.h | 40 ---------------------------------------- batman-adv/originator.c | 14 +------------- batman-adv/translation-table.c | 32 ++------------------------------ 4 files changed, 3 insertions(+), 86 deletions(-)

diff --git a/batman-adv/hash.c b/batman-adv/hash.c index 8605e2f..3dedb06 100644 --- a/batman-adv/hash.c +++ b/batman-adv/hash.c @@ -27,8 +27,6 @@ static void hash_init(struct hashtable_t *hash) { int i;

- hash->elements = 0; - for (i = 0 ; i < hash->size; i++) INIT_HLIST_HEAD(&hash->table[i]); } @@ -77,7 +75,6 @@ void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t)

hlist_del(hash_it_t->walk); kfree(bucket); - hash->elements--;

return data_save; } diff --git a/batman-adv/hash.h b/batman-adv/hash.h index 0b61c6e..16b23bf 100644 --- a/batman-adv/hash.h +++ b/batman-adv/hash.h @@ -53,7 +53,6 @@ struct hash_it_t {

struct hashtable_t { struct hlist_head *table; /* the hashtable itself, with the buckets */ - int elements; /* number of elements registered */ int size; /* size of hashtable */ };

@@ -127,7 +126,6 @@ static inline int hash_add(struct hashtable_t *hash, bucket->data = data; hlist_add_head(&bucket->hlist, head);

- hash->elements++; return 0; }

@@ -181,44 +179,6 @@ static inline void *hash_find(struct hashtable_t *hash, return NULL; }

-/* resize the hash, returns the pointer to the new hash or NULL on - * error. removes the old hash on success */ -static inline struct hashtable_t *hash_resize(struct hashtable_t *hash, - hashdata_choose_cb choose, - int size) -{ - struct hashtable_t *new_hash; - struct hlist_head *head, *new_head; - struct hlist_node *walk, *safe; - struct element_t *bucket; - int i, new_index; - - /* initialize a new hash with the new size */ - new_hash = hash_new(size); - - if (new_hash == NULL) - return NULL; - - /* copy the elements */ - for (i = 0; i < hash->size; i++) { - head = &hash->table[i]; - - hlist_for_each_safe(walk, safe, head) { - bucket = hlist_entry(walk, struct element_t, hlist); - - new_index = choose(bucket->data, size); - new_head = &new_hash->table[new_index]; - - hlist_del(walk); - hlist_add_head(walk, new_head); - } - } - - hash_destroy(hash); - - return new_hash; -} - /* iterate though the hash. First element is selected if an iterator * initialized with HASHIT() is supplied as iter. Use the returned * (or supplied) iterator to access the elements until hash_iterate returns diff --git a/batman-adv/originator.c b/batman-adv/originator.c index 89ec021..a5612e6 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -45,7 +45,7 @@ int originator_init(struct bat_priv *bat_priv) return 1;

spin_lock_bh(&bat_priv->orig_hash_lock); - bat_priv->orig_hash = hash_new(128); + bat_priv->orig_hash = hash_new(1024);

if (!bat_priv->orig_hash) goto err; @@ -124,7 +124,6 @@ void originator_free(struct bat_priv *bat_priv) struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) { struct orig_node *orig_node; - struct hashtable_t *swaphash; int size; int hash_added;

@@ -172,17 +171,6 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) if (hash_added < 0) goto free_bcast_own_sum;

- if (bat_priv->orig_hash->elements * 4 > bat_priv->orig_hash->size) { - swaphash = hash_resize(bat_priv->orig_hash, choose_orig, - bat_priv->orig_hash->size * 2); - - if (!swaphash) - bat_dbg(DBG_BATMAN, bat_priv, - "Couldn't resize orig hash table\n"); - else - bat_priv->orig_hash = swaphash; - } - return orig_node; free_bcast_own_sum: kfree(orig_node->bcast_own_sum); diff --git a/batman-adv/translation-table.c b/batman-adv/translation-table.c index 4b0a107..72448c9 100644 --- a/batman-adv/translation-table.c +++ b/batman-adv/translation-table.c @@ -42,7 +42,7 @@ int hna_local_init(struct bat_priv *bat_priv) if (bat_priv->hna_local_hash) return 1;

- bat_priv->hna_local_hash = hash_new(128); + bat_priv->hna_local_hash = hash_new(1024);

if (!bat_priv->hna_local_hash) return 0; @@ -58,7 +58,6 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) struct bat_priv *bat_priv = netdev_priv(soft_iface); struct hna_local_entry *hna_local_entry; struct hna_global_entry *hna_global_entry; - struct hashtable_t *swaphash; int required_bytes;

spin_lock_bh(&bat_priv->hna_lhash_lock); @@ -113,17 +112,6 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) bat_priv->num_local_hna++; atomic_set(&bat_priv->hna_local_changed, 1);

- if (bat_priv->hna_local_hash->elements * 4 > - bat_priv->hna_local_hash->size) { - swaphash = hash_resize(bat_priv->hna_local_hash, choose_orig, - bat_priv->hna_local_hash->size * 2); - - if (!swaphash) - pr_err("Couldn't resize local hna hash table\n"); - else - bat_priv->hna_local_hash = swaphash; - } - spin_unlock_bh(&bat_priv->hna_lhash_lock);

/* remove address from global hash if present */ @@ -302,7 +290,7 @@ int hna_global_init(struct bat_priv *bat_priv) if (bat_priv->hna_global_hash) return 1;

- bat_priv->hna_global_hash = hash_new(128); + bat_priv->hna_global_hash = hash_new(1024);

if (!bat_priv->hna_global_hash) return 0; @@ -316,7 +304,6 @@ void hna_global_add_orig(struct bat_priv *bat_priv, { struct hna_global_entry *hna_global_entry; struct hna_local_entry *hna_local_entry; - struct hashtable_t *swaphash; int hna_buff_count = 0; unsigned char *hna_ptr;

@@ -382,21 +369,6 @@ void hna_global_add_orig(struct bat_priv *bat_priv, orig_node->hna_buff_len = hna_buff_len; } } - - spin_lock_bh(&bat_priv->hna_ghash_lock); - - if (bat_priv->hna_global_hash->elements * 4 > - bat_priv->hna_global_hash->size) { - swaphash = hash_resize(bat_priv->hna_global_hash, choose_orig, - bat_priv->hna_global_hash->size * 2); - - if (!swaphash) - pr_err("Couldn't resize global hna hash table\n"); - else - bat_priv->hna_global_hash = swaphash; - } - - spin_unlock_bh(&bat_priv->hna_ghash_lock); }

int hna_global_seq_print_text(struct seq_file *seq, void *offset)

Signed-off-by: Sven Eckelmann sven.eckelmann@gmx.de --- Removed hash_iterate completely as promised to David. This should also help to create the later patches in a more cleaner way.

batman-adv/hash.c | 18 --- batman-adv/hash.h | 75 ++------- batman-adv/originator.c | 132 ++++++++++------ batman-adv/routing.c | 24 ++- batman-adv/translation-table.c | 110 +++++++++----- batman-adv/vis.c | 328 +++++++++++++++++++++++----------------- 6 files changed, 372 insertions(+), 315 deletions(-)

diff --git a/batman-adv/hash.c b/batman-adv/hash.c index 3dedb06..fec9bbd 100644 --- a/batman-adv/hash.c +++ b/batman-adv/hash.c @@ -60,21 +60,3 @@ struct hashtable_t *hash_new(int size)

return hash; } - -/* remove bucket (this might be used in hash_iterate() if you already found the - * bucket you want to delete and don't need the overhead to find it again with - * hash_remove(). But usually, you don't want to use this function, as it - * fiddles with hash-internals. */ -void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) -{ - void *data_save; - struct element_t *bucket; - - bucket = hlist_entry(hash_it_t->walk, struct element_t, hlist); - data_save = bucket->data; - - hlist_del(hash_it_t->walk); - kfree(bucket); - - return data_save; -} diff --git a/batman-adv/hash.h b/batman-adv/hash.h index 16b23bf..0801f9c 100644 --- a/batman-adv/hash.h +++ b/batman-adv/hash.h @@ -24,10 +24,6 @@

#include <linux/list.h>

-#define HASHIT(name) struct hash_it_t name = { \ - .index = 0, .walk = NULL, \ - .safe = NULL} - /* callback to a compare function. should * compare 2 element datas for their keys, * return 0 if same and not 0 if not @@ -45,12 +41,6 @@ struct element_t { struct hlist_node hlist; /* bucket list pointer */ };

-struct hash_it_t { - size_t index; - struct hlist_node *walk; - struct hlist_node *safe; -}; - struct hashtable_t { struct hlist_head *table; /* the hashtable itself, with the buckets */ int size; /* size of hashtable */ @@ -59,11 +49,10 @@ struct hashtable_t { /* allocates and clears the hash */ struct hashtable_t *hash_new(int size);

-/* remove bucket (this might be used in hash_iterate() if you already found the - * bucket you want to delete and don't need the overhead to find it again with - * hash_remove(). But usually, you don't want to use this function, as it - * fiddles with hash-internals. */ -void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t); +/* remove element if you already found the element you want to delete and don't + * need the overhead to find it again with hash_remove(). But usually, you + * don't want to use this function, as it fiddles with hash-internals. */ +void *hash_remove_element(struct hashtable_t *hash, struct element_t *elem);

/* free only the hashtable and the hash itself. */ void hash_destroy(struct hashtable_t *hash); @@ -137,17 +126,22 @@ static inline void *hash_remove(struct hashtable_t *hash, hashdata_compare_cb compare, hashdata_choose_cb choose, void *data) { - struct hash_it_t hash_it_t; + size_t index; + struct hlist_node *walk; struct element_t *bucket; struct hlist_head *head; + void *data_save;

- hash_it_t.index = choose(data, hash->size); - head = &hash->table[hash_it_t.index]; + index = choose(data, hash->size); + head = &hash->table[index];

- hlist_for_each(hash_it_t.walk, head) { - bucket = hlist_entry(hash_it_t.walk, struct element_t, hlist); - if (compare(bucket->data, data)) - return hash_remove_bucket(hash, &hash_it_t); + hlist_for_each_entry(bucket, walk, head, hlist) { + if (compare(bucket->data, data)) { + data_save = bucket->data; + hlist_del(walk); + kfree(bucket); + return data_save; + } }

return NULL; @@ -179,41 +173,4 @@ static inline void *hash_find(struct hashtable_t *hash, return NULL; }

-/* iterate though the hash. First element is selected if an iterator - * initialized with HASHIT() is supplied as iter. Use the returned - * (or supplied) iterator to access the elements until hash_iterate returns - * NULL. */ -static inline struct hash_it_t *hash_iterate(struct hashtable_t *hash, - struct hash_it_t *iter) -{ - if (!hash) - return NULL; - if (!iter) - return NULL; - - iter->walk = iter->safe; - - /* we search for the next head with list entries */ - if (!iter->walk) { - while (iter->index < hash->size) { - if (hlist_empty(&hash->table[iter->index])) - iter->index++; - else { - iter->walk = hash->table[iter->index].first; - - /* search next time */ - ++iter->index; - break; - } - } - } - - /* return iter when we found bucket otherwise null */ - if (!iter->walk) - return NULL; - - iter->safe = iter->walk->next; - return iter; -} - #endif /* _NET_BATMAN_ADV_HASH_H_ */ diff --git a/batman-adv/originator.c b/batman-adv/originator.c index a5612e6..7b1fc52 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -256,27 +256,37 @@ static bool purge_orig_node(struct bat_priv *bat_priv,

static void _purge_orig(struct bat_priv *bat_priv) { - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk, *safe; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; + int i; + + if (!hash) + return;

spin_lock_bh(&bat_priv->orig_hash_lock);

/* for all origins... */ - while (hash_iterate(bat_priv->orig_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - orig_node = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- if (purge_orig_node(bat_priv, orig_node)) { - if (orig_node->gw_flags) - gw_node_delete(bat_priv, orig_node); - hash_remove_bucket(bat_priv->orig_hash, &hashit); - free_orig_node(orig_node, bat_priv); + hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { + orig_node = bucket->data; + + if (purge_orig_node(bat_priv, orig_node)) { + if (orig_node->gw_flags) + gw_node_delete(bat_priv, orig_node); + hlist_del(walk); + kfree(bucket); + free_orig_node(orig_node, bat_priv); + } + + if (time_after(jiffies, orig_node->last_frag_packet + + msecs_to_jiffies(FRAG_TIMEOUT))) + frag_list_free(&orig_node->frag_list); } - - if (time_after(jiffies, (orig_node->last_frag_packet + - msecs_to_jiffies(FRAG_TIMEOUT)))) - frag_list_free(&orig_node->frag_list); }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -305,15 +315,18 @@ void purge_orig_ref(struct bat_priv *bat_priv)

int orig_seq_print_text(struct seq_file *seq, void *offset) { - HASHIT(hashit); - struct element_t *bucket; struct net_device *net_dev = (struct net_device *)seq->private; struct bat_priv *bat_priv = netdev_priv(net_dev); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; + struct element_t *bucket; struct orig_node *orig_node; struct neigh_node *neigh_node; int batman_count = 0; int last_seen_secs; int last_seen_msecs; + int i;

if ((!bat_priv->primary_if) || (bat_priv->primary_if->if_status != IF_ACTIVE)) { @@ -337,33 +350,39 @@ int orig_seq_print_text(struct seq_file *seq, void *offset)

spin_lock_bh(&bat_priv->orig_hash_lock);

- while (hash_iterate(bat_priv->orig_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - orig_node = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- if (!orig_node->router) - continue; + hlist_for_each_entry(bucket, walk, head, hlist) { + orig_node = bucket->data;

- if (orig_node->router->tq_avg == 0) - continue; + if (!orig_node->router) + continue;

- last_seen_secs = jiffies_to_msecs(jiffies - + if (orig_node->router->tq_avg == 0) + continue; + + last_seen_secs = jiffies_to_msecs(jiffies - orig_node->last_valid) / 1000; - last_seen_msecs = jiffies_to_msecs(jiffies - + last_seen_msecs = jiffies_to_msecs(jiffies - orig_node->last_valid) % 1000;

- seq_printf(seq, "%pM %4i.%03is (%3i) %pM [%10s]:", - orig_node->orig, last_seen_secs, last_seen_msecs, - orig_node->router->tq_avg, orig_node->router->addr, - orig_node->router->if_incoming->net_dev->name); + neigh_node = orig_node->router; + seq_printf(seq, "%pM %4i.%03is (%3i) %pM [%10s]:", + orig_node->orig, last_seen_secs, + last_seen_msecs, neigh_node->tq_avg, + neigh_node->addr, + neigh_node->if_incoming->net_dev->name);

- list_for_each_entry(neigh_node, &orig_node->neigh_list, list) { - seq_printf(seq, " %pM (%3i)", neigh_node->addr, - neigh_node->tq_avg); + list_for_each_entry(neigh_node, &orig_node->neigh_list, + list) { + seq_printf(seq, " %pM (%3i)", neigh_node->addr, + neigh_node->tq_avg); + } + + seq_printf(seq, "\n"); + batman_count++; } - - seq_printf(seq, "\n"); - batman_count++; }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -407,20 +426,26 @@ static int orig_node_add_if(struct orig_node *orig_node, int max_if_num) int orig_hash_add_if(struct batman_if *batman_if, int max_if_num) { struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); - struct orig_node *orig_node; - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; + struct orig_node *orig_node; + int i;

/* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ spin_lock_bh(&bat_priv->orig_hash_lock);

- while (hash_iterate(bat_priv->orig_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - orig_node = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- if (orig_node_add_if(orig_node, max_if_num) == -1) - goto err; + hlist_for_each_entry(bucket, walk, head, hlist) { + orig_node = bucket->data; + + if (orig_node_add_if(orig_node, max_if_num) == -1) + goto err; + } }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -486,25 +511,30 @@ free_own_sum: int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) { struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; + struct element_t *bucket; struct batman_if *batman_if_tmp; struct orig_node *orig_node; - HASHIT(hashit); - struct element_t *bucket; - int ret; + int i, ret;

/* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ spin_lock_bh(&bat_priv->orig_hash_lock);

- while (hash_iterate(bat_priv->orig_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - orig_node = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- ret = orig_node_del_if(orig_node, max_if_num, - batman_if->if_num); + hlist_for_each_entry(bucket, walk, head, hlist) { + orig_node = bucket->data;

- if (ret == -1) - goto err; + ret = orig_node_del_if(orig_node, max_if_num, + batman_if->if_num); + + if (ret == -1) + goto err; + } }

/* renumber remaining batman interfaces _inside_ of orig_hash_lock */ diff --git a/batman-adv/routing.c b/batman-adv/routing.c index d8b0c5a..8cec99b 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -39,21 +39,29 @@ void slide_own_bcast_window(struct batman_if *batman_if) { struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; TYPE_OF_WORD *word; + int i; + size_t word_index;

spin_lock_bh(&bat_priv->orig_hash_lock);

- while (hash_iterate(bat_priv->orig_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - orig_node = bucket->data; - word = &(orig_node->bcast_own[batman_if->if_num * NUM_WORDS]); + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- bit_get_packet(bat_priv, word, 1, 0); - orig_node->bcast_own_sum[batman_if->if_num] = - bit_packet_count(word); + hlist_for_each_entry(bucket, walk, head, hlist) { + orig_node = bucket->data; + word_index = batman_if->if_num * NUM_WORDS; + word = &(orig_node->bcast_own[word_index]); + + bit_get_packet(bat_priv, word, 1, 0); + orig_node->bcast_own_sum[batman_if->if_num] = + bit_packet_count(word); + } }

spin_unlock_bh(&bat_priv->orig_hash_lock); diff --git a/batman-adv/translation-table.c b/batman-adv/translation-table.c index 72448c9..a19e16c 100644 --- a/batman-adv/translation-table.c +++ b/batman-adv/translation-table.c @@ -131,27 +131,34 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) int hna_local_fill_buffer(struct bat_priv *bat_priv, unsigned char *buff, int buff_len) { + struct hashtable_t *hash = bat_priv->hna_local_hash; struct hna_local_entry *hna_local_entry; struct element_t *bucket; - HASHIT(hashit); - int i = 0; + int i; + struct hlist_node *walk; + struct hlist_head *head; + int count = 0;

spin_lock_bh(&bat_priv->hna_lhash_lock);

- while (hash_iterate(bat_priv->hna_local_hash, &hashit)) { + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- if (buff_len < (i + 1) * ETH_ALEN) - break; + hlist_for_each_entry(bucket, walk, head, hlist) {

- bucket = hlist_entry(hashit.walk, struct element_t, hlist); - hna_local_entry = bucket->data; - memcpy(buff + (i * ETH_ALEN), hna_local_entry->addr, ETH_ALEN); + if (buff_len < (count + 1) * ETH_ALEN) + break;

- i++; + hna_local_entry = bucket->data; + memcpy(buff + (count * ETH_ALEN), hna_local_entry->addr, + ETH_ALEN); + + count++; + } }

/* if we did not get all new local hnas see you next time ;-) */ - if (i == bat_priv->num_local_hna) + if (count == bat_priv->num_local_hna) atomic_set(&bat_priv->hna_local_changed, 0);

spin_unlock_bh(&bat_priv->hna_lhash_lock); @@ -162,9 +169,11 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) { struct net_device *net_dev = (struct net_device *)seq->private; struct bat_priv *bat_priv = netdev_priv(net_dev); + struct hashtable_t *hash = bat_priv->hna_local_hash; struct hna_local_entry *hna_local_entry; - HASHIT(hashit); - HASHIT(hashit_count); + int i; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; size_t buf_size, pos; char *buff; @@ -183,8 +192,12 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset)

buf_size = 1; /* Estimate length for: " * xx:xx:xx:xx:xx:xx\n" */ - while (hash_iterate(bat_priv->hna_local_hash, &hashit_count)) - buf_size += 21; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i]; + + hlist_for_each(walk, head) + buf_size += 21; + }

buff = kmalloc(buf_size, GFP_ATOMIC); if (!buff) { @@ -194,12 +207,15 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) buff[0] = '\0'; pos = 0;

- while (hash_iterate(bat_priv->hna_local_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - hna_local_entry = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- pos += snprintf(buff + pos, 22, " * %pM\n", - hna_local_entry->addr); + hlist_for_each_entry(bucket, walk, head, hlist) { + hna_local_entry = bucket->data; + + pos += snprintf(buff + pos, 22, " * %pM\n", + hna_local_entry->addr); + } }

spin_unlock_bh(&bat_priv->hna_lhash_lock); @@ -240,6 +256,7 @@ void hna_local_remove(struct bat_priv *bat_priv, hna_local_entry = (struct hna_local_entry *) hash_find(bat_priv->hna_local_hash, compare_orig, choose_orig, addr); + if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, message);

@@ -252,23 +269,30 @@ static void hna_local_purge(struct work_struct *work) container_of(work, struct delayed_work, work); struct bat_priv *bat_priv = container_of(delayed_work, struct bat_priv, hna_work); + struct hashtable_t *hash = bat_priv->hna_local_hash; struct hna_local_entry *hna_local_entry; - HASHIT(hashit); + int i; + struct hlist_node *walk, *safe; + struct hlist_head *head; struct element_t *bucket; unsigned long timeout;

spin_lock_bh(&bat_priv->hna_lhash_lock);

- while (hash_iterate(bat_priv->hna_local_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - hna_local_entry = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- timeout = hna_local_entry->last_seen + LOCAL_HNA_TIMEOUT * HZ; + hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { + hna_local_entry = bucket->data;

- if ((!hna_local_entry->never_purge) && - time_after(jiffies, timeout)) - hna_local_del(bat_priv, hna_local_entry, - "address timed out"); + timeout = hna_local_entry->last_seen; + timeout += LOCAL_HNA_TIMEOUT * HZ; + + if ((!hna_local_entry->never_purge) && + time_after(jiffies, timeout)) + hna_local_del(bat_priv, hna_local_entry, + "address timed out"); + } }

spin_unlock_bh(&bat_priv->hna_lhash_lock); @@ -375,9 +399,11 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset) { struct net_device *net_dev = (struct net_device *)seq->private; struct bat_priv *bat_priv = netdev_priv(net_dev); + struct hashtable_t *hash = bat_priv->hna_global_hash; struct hna_global_entry *hna_global_entry; - HASHIT(hashit); - HASHIT(hashit_count); + int i; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; size_t buf_size, pos; char *buff; @@ -395,8 +421,12 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset)

buf_size = 1; /* Estimate length for: " * xx:xx:xx:xx:xx:xx via xx:xx:xx:xx:xx:xx\n"*/ - while (hash_iterate(bat_priv->hna_global_hash, &hashit_count)) - buf_size += 43; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i]; + + hlist_for_each(walk, head) + buf_size += 43; + }

buff = kmalloc(buf_size, GFP_ATOMIC); if (!buff) { @@ -406,13 +436,17 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset) buff[0] = '\0'; pos = 0;

- while (hash_iterate(bat_priv->hna_global_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - hna_global_entry = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- pos += snprintf(buff + pos, 44, - " * %pM via %pM\n", hna_global_entry->addr, - hna_global_entry->orig_node->orig); + hlist_for_each_entry(bucket, walk, head, hlist) { + hna_global_entry = bucket->data; + + pos += snprintf(buff + pos, 44, + " * %pM via %pM\n", + hna_global_entry->addr, + hna_global_entry->orig_node->orig); + } }

spin_unlock_bh(&bat_priv->hna_ghash_lock); diff --git a/batman-adv/vis.c b/batman-adv/vis.c index 957a086..d7f5b6b 100644 --- a/batman-adv/vis.c +++ b/batman-adv/vis.c @@ -174,21 +174,23 @@ static ssize_t vis_data_read_entry(char *buff, struct vis_info_entry *entry,

int vis_seq_print_text(struct seq_file *seq, void *offset) { - HASHIT(hashit); - HASHIT(hashit_count); + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct vis_info *info; struct vis_packet *packet; struct vis_info_entry *entries; struct net_device *net_dev = (struct net_device *)seq->private; struct bat_priv *bat_priv = netdev_priv(net_dev); + struct hashtable_t *hash = bat_priv->vis_hash; HLIST_HEAD(vis_if_list); struct if_list_entry *entry; struct hlist_node *pos, *n; - int i; + int i, j; int vis_server = atomic_read(&bat_priv->vis_mode); size_t buff_pos, buf_size; char *buff; + int compare;

if ((!bat_priv->primary_if) || (vis_server == VIS_TYPE_CLIENT_UPDATE)) @@ -197,35 +199,41 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) buf_size = 1; /* Estimate length */ spin_lock_bh(&bat_priv->vis_hash_lock); - while (hash_iterate(bat_priv->vis_hash, &hashit_count)) { - bucket = hlist_entry(hashit_count.walk, struct element_t, - hlist); - info = bucket->data; - packet = (struct vis_packet *)info->skb_packet->data; - entries = (struct vis_info_entry *) - ((char *)packet + sizeof(struct vis_packet)); + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- for (i = 0; i < packet->entries; i++) { - if (entries[i].quality == 0) - continue; - vis_data_insert_interface(entries[i].src, &vis_if_list, - compare_orig(entries[i].src, packet->vis_orig)); - } + hlist_for_each_entry(bucket, walk, head, hlist) { + info = bucket->data; + packet = (struct vis_packet *)info->skb_packet->data; + entries = (struct vis_info_entry *) + ((char *)packet + sizeof(struct vis_packet));

- hlist_for_each_entry(entry, pos, &vis_if_list, list) { - buf_size += 18 + 26 * packet->entries; + for (j = 0; j < packet->entries; j++) { + if (entries[j].quality == 0) + continue; + compare = + compare_orig(entries[j].src, packet->vis_orig); + vis_data_insert_interface(entries[j].src, + &vis_if_list, + compare); + }

- /* add primary/secondary records */ - if (compare_orig(entry->addr, packet->vis_orig)) - buf_size += - vis_data_count_prim_sec(&vis_if_list); + hlist_for_each_entry(entry, pos, &vis_if_list, list) { + buf_size += 18 + 26 * packet->entries;

- buf_size += 1; - } + /* add primary/secondary records */ + if (compare_orig(entry->addr, packet->vis_orig)) + buf_size += + vis_data_count_prim_sec(&vis_if_list);

- hlist_for_each_entry_safe(entry, pos, n, &vis_if_list, list) { - hlist_del(&entry->list); - kfree(entry); + buf_size += 1; + } + + hlist_for_each_entry_safe(entry, pos, n, &vis_if_list, + list) { + hlist_del(&entry->list); + kfree(entry); + } } }

@@ -237,42 +245,50 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) buff[0] = '\0'; buff_pos = 0;

- while (hash_iterate(bat_priv->vis_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - info = bucket->data; - packet = (struct vis_packet *)info->skb_packet->data; - entries = (struct vis_info_entry *) - ((char *)packet + sizeof(struct vis_packet)); + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- for (i = 0; i < packet->entries; i++) { - if (entries[i].quality == 0) - continue; - vis_data_insert_interface(entries[i].src, &vis_if_list, - compare_orig(entries[i].src, packet->vis_orig)); - } + hlist_for_each_entry(bucket, walk, head, hlist) { + info = bucket->data; + packet = (struct vis_packet *)info->skb_packet->data; + entries = (struct vis_info_entry *) + ((char *)packet + sizeof(struct vis_packet));

- hlist_for_each_entry(entry, pos, &vis_if_list, list) { - buff_pos += sprintf(buff + buff_pos, "%pM,", - entry->addr); + for (j = 0; j < packet->entries; j++) { + if (entries[j].quality == 0) + continue; + compare = + compare_orig(entries[j].src, packet->vis_orig); + vis_data_insert_interface(entries[j].src, + &vis_if_list, + compare); + }

- for (i = 0; i < packet->entries; i++) - buff_pos += vis_data_read_entry(buff + buff_pos, - &entries[i], - entry->addr, - entry->primary); + hlist_for_each_entry(entry, pos, &vis_if_list, list) { + buff_pos += sprintf(buff + buff_pos, "%pM,", + entry->addr);

- /* add primary/secondary records */ - if (compare_orig(entry->addr, packet->vis_orig)) - buff_pos += - vis_data_read_prim_sec(buff + buff_pos, - &vis_if_list); + for (i = 0; i < packet->entries; i++) + buff_pos += vis_data_read_entry( + buff + buff_pos, + &entries[i], + entry->addr, + entry->primary);

- buff_pos += sprintf(buff + buff_pos, "\n"); - } + /* add primary/secondary records */ + if (compare_orig(entry->addr, packet->vis_orig)) + buff_pos += + vis_data_read_prim_sec(buff + buff_pos, + &vis_if_list);

- hlist_for_each_entry_safe(entry, pos, n, &vis_if_list, list) { - hlist_del(&entry->list); - kfree(entry); + buff_pos += sprintf(buff + buff_pos, "\n"); + } + + hlist_for_each_entry_safe(entry, pos, n, &vis_if_list, + list) { + hlist_del(&entry->list); + kfree(entry); + } } }

@@ -511,24 +527,31 @@ end: static int find_best_vis_server(struct bat_priv *bat_priv, struct vis_info *info) { - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; - int best_tq = -1; + int best_tq = -1, i;

packet = (struct vis_packet *)info->skb_packet->data;

- while (hash_iterate(bat_priv->orig_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - orig_node = bucket->data; - if ((orig_node) && (orig_node->router) && - (orig_node->flags & VIS_SERVER) && - (orig_node->router->tq_avg > best_tq)) { - best_tq = orig_node->router->tq_avg; - memcpy(packet->target_orig, orig_node->orig, ETH_ALEN); + for (i = 0; i < hash->size; i++) { + head = &hash->table[i]; + + hlist_for_each_entry(bucket, walk, head, hlist) { + orig_node = bucket->data; + if ((orig_node) && (orig_node->router) && + (orig_node->flags & VIS_SERVER) && + (orig_node->router->tq_avg > best_tq)) { + best_tq = orig_node->router->tq_avg; + memcpy(packet->target_orig, orig_node->orig, + ETH_ALEN); + } } } + return best_tq; }

@@ -548,15 +571,17 @@ static bool vis_packet_full(struct vis_info *info) * returns 0 on success, -1 if no packet could be generated */ static int generate_vis_packet(struct bat_priv *bat_priv) { - HASHIT(hashit_local); - HASHIT(hashit_global); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; + struct neigh_node *neigh_node; struct vis_info *info = (struct vis_info *)bat_priv->my_vis_info; struct vis_packet *packet = (struct vis_packet *)info->skb_packet->data; struct vis_info_entry *entry; struct hna_local_entry *hna_local_entry; - int best_tq = -1; + int best_tq = -1, i;

info->first_seen = jiffies; packet->vis_type = atomic_read(&bat_priv->vis_mode); @@ -577,56 +602,64 @@ static int generate_vis_packet(struct bat_priv *bat_priv) } }

- while (hash_iterate(bat_priv->orig_hash, &hashit_global)) { - bucket = hlist_entry(hashit_global.walk, struct element_t, - hlist); - orig_node = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- if (!orig_node->router) - continue; + hlist_for_each_entry(bucket, walk, head, hlist) { + orig_node = bucket->data; + neigh_node = orig_node->router;

- if (!compare_orig(orig_node->router->addr, orig_node->orig)) - continue; + if (!neigh_node) + continue;

- if (orig_node->router->if_incoming->if_status != IF_ACTIVE) - continue; + if (!compare_orig(neigh_node->addr, orig_node->orig)) + continue;

- if (orig_node->router->tq_avg < 1) - continue; + if (neigh_node->if_incoming->if_status != IF_ACTIVE) + continue;

- /* fill one entry into buffer. */ - entry = (struct vis_info_entry *) - skb_put(info->skb_packet, sizeof(*entry)); - memcpy(entry->src, - orig_node->router->if_incoming->net_dev->dev_addr, - ETH_ALEN); - memcpy(entry->dest, orig_node->orig, ETH_ALEN); - entry->quality = orig_node->router->tq_avg; - packet->entries++; + if (neigh_node->tq_avg < 1) + continue;

- if (vis_packet_full(info)) { - spin_unlock_bh(&bat_priv->orig_hash_lock); - return 0; + /* fill one entry into buffer. */ + entry = (struct vis_info_entry *) + skb_put(info->skb_packet, sizeof(*entry)); + memcpy(entry->src, + neigh_node->if_incoming->net_dev->dev_addr, + ETH_ALEN); + memcpy(entry->dest, orig_node->orig, ETH_ALEN); + entry->quality = neigh_node->tq_avg; + packet->entries++; + + if (vis_packet_full(info)) { + spin_unlock_bh(&bat_priv->orig_hash_lock); + return 0; + } } }

spin_unlock_bh(&bat_priv->orig_hash_lock);

+ hash = bat_priv->hna_local_hash; + spin_lock_bh(&bat_priv->hna_lhash_lock); - while (hash_iterate(bat_priv->hna_local_hash, &hashit_local)) { - bucket = hlist_entry(hashit_local.walk, struct element_t, - hlist); - hna_local_entry = bucket->data; - entry = (struct vis_info_entry *)skb_put(info->skb_packet, - sizeof(*entry)); - memset(entry->src, 0, ETH_ALEN); - memcpy(entry->dest, hna_local_entry->addr, ETH_ALEN); - entry->quality = 0; /* 0 means HNA */ - packet->entries++; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- if (vis_packet_full(info)) { - spin_unlock_bh(&bat_priv->hna_lhash_lock); - return 0; + hlist_for_each_entry(bucket, walk, head, hlist) { + hna_local_entry = bucket->data; + entry = (struct vis_info_entry *) + skb_put(info->skb_packet, + sizeof(*entry)); + memset(entry->src, 0, ETH_ALEN); + memcpy(entry->dest, hna_local_entry->addr, ETH_ALEN); + entry->quality = 0; /* 0 means HNA */ + packet->entries++; + + if (vis_packet_full(info)) { + spin_unlock_bh(&bat_priv->hna_lhash_lock); + return 0; + } } }

@@ -638,23 +671,30 @@ static int generate_vis_packet(struct bat_priv *bat_priv) * held */ static void purge_vis_packets(struct bat_priv *bat_priv) { - HASHIT(hashit); + int i; + struct hashtable_t *hash = bat_priv->vis_hash; + struct hlist_node *walk, *safe; + struct hlist_head *head; struct element_t *bucket; struct vis_info *info;

- while (hash_iterate(bat_priv->vis_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - info = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- /* never purge own data. */ - if (info == bat_priv->my_vis_info) - continue; + hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { + info = bucket->data;

- if (time_after(jiffies, - info->first_seen + VIS_TIMEOUT * HZ)) { - hash_remove_bucket(bat_priv->vis_hash, &hashit); - send_list_del(info); - kref_put(&info->refcount, free_info); + /* never purge own data. */ + if (info == bat_priv->my_vis_info) + continue; + + if (time_after(jiffies, + info->first_seen + VIS_TIMEOUT * HZ)) { + hlist_del(walk); + kfree(bucket); + send_list_del(info); + kref_put(&info->refcount, free_info); + } } } } @@ -662,44 +702,50 @@ static void purge_vis_packets(struct bat_priv *bat_priv) static void broadcast_vis_packet(struct bat_priv *bat_priv, struct vis_info *info) { - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; struct sk_buff *skb; struct batman_if *batman_if; uint8_t dstaddr[ETH_ALEN]; + int i;

spin_lock_bh(&bat_priv->orig_hash_lock); packet = (struct vis_packet *)info->skb_packet->data;

/* send to all routers in range. */ - while (hash_iterate(bat_priv->orig_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - orig_node = bucket->data; + for (i = 0; i < hash->size; i++) { + head = &hash->table[i];

- /* if it's a vis server and reachable, send it. */ - if ((!orig_node) || (!orig_node->router)) - continue; - if (!(orig_node->flags & VIS_SERVER)) - continue; - /* don't send it if we already received the packet from - * this node. */ - if (recv_list_is_in(bat_priv, &info->recv_list, - orig_node->orig)) - continue; + hlist_for_each_entry(bucket, walk, head, hlist) { + orig_node = bucket->data;

- memcpy(packet->target_orig, orig_node->orig, ETH_ALEN); - batman_if = orig_node->router->if_incoming; - memcpy(dstaddr, orig_node->router->addr, ETH_ALEN); - spin_unlock_bh(&bat_priv->orig_hash_lock); + /* if it's a vis server and reachable, send it. */ + if ((!orig_node) || (!orig_node->router)) + continue; + if (!(orig_node->flags & VIS_SERVER)) + continue; + /* don't send it if we already received the packet from + * this node. */ + if (recv_list_is_in(bat_priv, &info->recv_list, + orig_node->orig)) + continue;

- skb = skb_clone(info->skb_packet, GFP_ATOMIC); - if (skb) - send_skb_packet(skb, batman_if, dstaddr); + memcpy(packet->target_orig, orig_node->orig, ETH_ALEN); + batman_if = orig_node->router->if_incoming; + memcpy(dstaddr, orig_node->router->addr, ETH_ALEN); + spin_unlock_bh(&bat_priv->orig_hash_lock);

- spin_lock_bh(&bat_priv->orig_hash_lock); + skb = skb_clone(info->skb_packet, GFP_ATOMIC); + if (skb) + send_skb_packet(skb, batman_if, dstaddr); + + spin_lock_bh(&bat_priv->orig_hash_lock); + }

}

From: Marek Lindner lindner_marek@yahoo.de

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- batman-adv/originator.c | 20 +++++++++++++++----- batman-adv/originator.h | 8 +++++--- batman-adv/routing.c | 7 +++++++ batman-adv/types.h | 1 + 4 files changed, 28 insertions(+), 8 deletions(-)

diff --git a/batman-adv/originator.c b/batman-adv/originator.c index 7b1fc52..cc778ea 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -59,9 +59,18 @@ err: return 0; }

-struct neigh_node * -create_neighbor(struct orig_node *orig_node, struct orig_node *orig_neigh_node, - uint8_t *neigh, struct batman_if *if_incoming) +void neigh_node_free_ref(struct kref *refcount) +{ + struct neigh_node *neigh_node; + + neigh_node = container_of(refcount, struct neigh_node, refcount); + kfree(neigh_node); +} + +struct neigh_node *create_neighbor(struct orig_node *orig_node, + struct orig_node *orig_neigh_node, + uint8_t *neigh, + struct batman_if *if_incoming) { struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface); struct neigh_node *neigh_node; @@ -78,6 +87,7 @@ create_neighbor(struct orig_node *orig_node, struct orig_node *orig_neigh_node, memcpy(neigh_node->addr, neigh, ETH_ALEN); neigh_node->orig_node = orig_neigh_node; neigh_node->if_incoming = if_incoming; + kref_init(&neigh_node->refcount);

list_add_tail(&neigh_node->list, &orig_node->neigh_list); return neigh_node; @@ -95,7 +105,7 @@ static void free_orig_node(void *data, void *arg) neigh_node = list_entry(list_pos, struct neigh_node, list);

list_del(list_pos); - kfree(neigh_node); + kref_put(&neigh_node->refcount, neigh_node_free_ref); }

frag_list_free(&orig_node->frag_list); @@ -216,7 +226,7 @@ static bool purge_orig_neighbors(struct bat_priv *bat_priv,

neigh_purged = true; list_del(list_pos); - kfree(neigh_node); + kref_put(&neigh_node->refcount, neigh_node_free_ref); } else { if ((*best_neigh_node == NULL) || (neigh_node->tq_avg > (*best_neigh_node)->tq_avg)) diff --git a/batman-adv/originator.h b/batman-adv/originator.h index d474ceb..f3676fa 100644 --- a/batman-adv/originator.h +++ b/batman-adv/originator.h @@ -26,9 +26,11 @@ int originator_init(struct bat_priv *bat_priv); void originator_free(struct bat_priv *bat_priv); void purge_orig_ref(struct bat_priv *bat_priv); struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr); -struct neigh_node * -create_neighbor(struct orig_node *orig_node, struct orig_node *orig_neigh_node, - uint8_t *neigh, struct batman_if *if_incoming); +struct neigh_node *create_neighbor(struct orig_node *orig_node, + struct orig_node *orig_neigh_node, + uint8_t *neigh, + struct batman_if *if_incoming); +void neigh_node_free_ref(struct kref *refcount); int orig_seq_print_text(struct seq_file *seq, void *offset); int orig_hash_add_if(struct batman_if *batman_if, int max_if_num); int orig_hash_del_if(struct batman_if *batman_if, int max_if_num); diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 8cec99b..014413e 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -90,6 +90,8 @@ static void update_route(struct bat_priv *bat_priv, struct neigh_node *neigh_node, unsigned char *hna_buff, int hna_buff_len) { + struct neigh_node *neigh_node_tmp; + /* route deleted */ if ((orig_node->router != NULL) && (neigh_node == NULL)) {

@@ -116,7 +118,12 @@ static void update_route(struct bat_priv *bat_priv, orig_node->router->addr); }

+ if (neigh_node) + kref_get(&neigh_node->refcount); + neigh_node_tmp = orig_node->router; orig_node->router = neigh_node; + if (neigh_node_tmp) + kref_put(&neigh_node_tmp->refcount, neigh_node_free_ref); }

diff --git a/batman-adv/types.h b/batman-adv/types.h index 1d00849..c1accbf 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -115,6 +115,7 @@ struct neigh_node { struct neigh_node *next_bond_candidate; unsigned long last_valid; TYPE_OF_WORD real_bits[NUM_WORDS]; + struct kref refcount; struct orig_node *orig_node; struct batman_if *if_incoming; };

From: Marek Lindner lindner_marek@yahoo.de

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- batman-adv/originator.c | 30 +++++++++++++++--------------- batman-adv/routing.c | 29 ++++++++++++++++++----------- batman-adv/types.h | 4 ++-- 3 files changed, 35 insertions(+), 28 deletions(-)

diff --git a/batman-adv/originator.c b/batman-adv/originator.c index cc778ea..1df73e3 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -82,29 +82,28 @@ struct neigh_node *create_neighbor(struct orig_node *orig_node, if (!neigh_node) return NULL;

- INIT_LIST_HEAD(&neigh_node->list); + INIT_HLIST_NODE(&neigh_node->list);

memcpy(neigh_node->addr, neigh, ETH_ALEN); neigh_node->orig_node = orig_neigh_node; neigh_node->if_incoming = if_incoming; kref_init(&neigh_node->refcount);

- list_add_tail(&neigh_node->list, &orig_node->neigh_list); + hlist_add_head(&neigh_node->list, &orig_node->neigh_list); return neigh_node; }

static void free_orig_node(void *data, void *arg) { - struct list_head *list_pos, *list_pos_tmp; + struct hlist_node *node, *node_tmp; struct neigh_node *neigh_node; struct orig_node *orig_node = (struct orig_node *)data; struct bat_priv *bat_priv = (struct bat_priv *)arg;

/* for all neighbors towards this originator ... */ - list_for_each_safe(list_pos, list_pos_tmp, &orig_node->neigh_list) { - neigh_node = list_entry(list_pos, struct neigh_node, list); - - list_del(list_pos); + hlist_for_each_entry_safe(neigh_node, node, node_tmp, + &orig_node->neigh_list, list) { + hlist_del(&neigh_node->list); kref_put(&neigh_node->refcount, neigh_node_free_ref); }

@@ -151,7 +150,7 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) if (!orig_node) return NULL;

- INIT_LIST_HEAD(&orig_node->neigh_list); + INIT_HLIST_HEAD(&orig_node->neigh_list);

memcpy(orig_node->orig, addr, ETH_ALEN); orig_node->router = NULL; @@ -195,15 +194,15 @@ static bool purge_orig_neighbors(struct bat_priv *bat_priv, struct orig_node *orig_node, struct neigh_node **best_neigh_node) { - struct list_head *list_pos, *list_pos_tmp; + struct hlist_node *node, *node_tmp; struct neigh_node *neigh_node; bool neigh_purged = false;

*best_neigh_node = NULL;

/* for all neighbors towards this originator ... */ - list_for_each_safe(list_pos, list_pos_tmp, &orig_node->neigh_list) { - neigh_node = list_entry(list_pos, struct neigh_node, list); + hlist_for_each_entry_safe(neigh_node, node, node_tmp, + &orig_node->neigh_list, list) {

if ((time_after(jiffies, neigh_node->last_valid + PURGE_TIMEOUT * HZ)) || @@ -225,7 +224,8 @@ static bool purge_orig_neighbors(struct bat_priv *bat_priv, (neigh_node->last_valid / HZ));

neigh_purged = true; - list_del(list_pos); + + hlist_del(&neigh_node->list); kref_put(&neigh_node->refcount, neigh_node_free_ref); } else { if ((*best_neigh_node == NULL) || @@ -328,7 +328,7 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) struct net_device *net_dev = (struct net_device *)seq->private; struct bat_priv *bat_priv = netdev_priv(net_dev); struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *walk, *node; struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; @@ -384,8 +384,8 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) neigh_node->addr, neigh_node->if_incoming->net_dev->name);

- list_for_each_entry(neigh_node, &orig_node->neigh_list, - list) { + hlist_for_each_entry(neigh_node, node, + &orig_node->neigh_list, list) { seq_printf(seq, " %pM (%3i)", neigh_node->addr, neigh_node->tq_avg); } diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 014413e..773c1ba 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -150,12 +150,12 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, { struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface); struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL; + struct hlist_node *node; unsigned char total_count;

if (orig_node == orig_neigh_node) { - list_for_each_entry(tmp_neigh_node, - &orig_node->neigh_list, - list) { + hlist_for_each_entry(tmp_neigh_node, node, + &orig_node->neigh_list, list) {

if (compare_orig(tmp_neigh_node->addr, orig_neigh_node->orig) && @@ -175,8 +175,8 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, neigh_node->last_valid = jiffies; } else { /* find packet count of corresponding one hop neighbor */ - list_for_each_entry(tmp_neigh_node, - &orig_neigh_node->neigh_list, list) { + hlist_for_each_entry(tmp_neigh_node, node, + &orig_neigh_node->neigh_list, list) {

if (compare_orig(tmp_neigh_node->addr, orig_neigh_node->orig) && @@ -261,12 +261,14 @@ static void update_orig(struct bat_priv *bat_priv, char is_duplicate) { struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL; + struct hlist_node *node; int tmp_hna_buff_len;

bat_dbg(DBG_BATMAN, bat_priv, "update_originator(): " "Searching and updating originator entry of received packet\n");

- list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) { + hlist_for_each_entry(tmp_neigh_node, node, + &orig_node->neigh_list, list) { if (compare_orig(tmp_neigh_node->addr, ethhdr->h_source) && (tmp_neigh_node->if_incoming == if_incoming)) { neigh_node = tmp_neigh_node; @@ -392,6 +394,7 @@ static char count_real_packets(struct ethhdr *ethhdr, struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface); struct orig_node *orig_node; struct neigh_node *tmp_neigh_node; + struct hlist_node *node; char is_duplicate = 0; int32_t seq_diff; int need_update = 0; @@ -408,7 +411,8 @@ static char count_real_packets(struct ethhdr *ethhdr, &orig_node->batman_seqno_reset)) return -1;

- list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) { + hlist_for_each_entry(tmp_neigh_node, node, + &orig_node->neigh_list, list) {

is_duplicate |= get_bit_status(tmp_neigh_node->real_bits, orig_node->last_real_seqno, @@ -460,6 +464,7 @@ void update_bonding_candidates(struct bat_priv *bat_priv, int candidates; int interference_candidate; int best_tq; + struct hlist_node *node, *node2; struct neigh_node *tmp_neigh_node, *tmp_neigh_node2; struct neigh_node *first_candidate, *last_candidate;

@@ -479,13 +484,15 @@ void update_bonding_candidates(struct bat_priv *bat_priv, * as "bonding partner" */

/* first, zero the list */ - list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) { + hlist_for_each_entry(tmp_neigh_node, node, + &orig_node->neigh_list, list) { tmp_neigh_node->next_bond_candidate = NULL; }

first_candidate = NULL; last_candidate = NULL; - list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) { + hlist_for_each_entry(tmp_neigh_node, node, + &orig_node->neigh_list, list) {

/* only consider if it has the same primary address ... */ if (memcmp(orig_node->orig, @@ -502,8 +509,8 @@ void update_bonding_candidates(struct bat_priv *bat_priv, * select this candidate because of possible interference. */

interference_candidate = 0; - list_for_each_entry(tmp_neigh_node2, - &orig_node->neigh_list, list) { + hlist_for_each_entry(tmp_neigh_node2, node2, + &orig_node->neigh_list, list) {

if (tmp_neigh_node2 == tmp_neigh_node) continue; diff --git a/batman-adv/types.h b/batman-adv/types.h index c1accbf..1ce91f6 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -83,7 +83,7 @@ struct orig_node { uint8_t last_ttl; TYPE_OF_WORD bcast_bits[NUM_WORDS]; uint32_t last_bcast_seqno; - struct list_head neigh_list; + struct hlist_head neigh_list; struct list_head frag_list; unsigned long last_frag_packet; struct { @@ -105,7 +105,7 @@ struct gw_node { * @last_valid: when last packet via this neighbor was received */ struct neigh_node { - struct list_head list; + struct hlist_node list; uint8_t addr[ETH_ALEN]; uint8_t real_packet_count; uint8_t tq_recv[TQ_GLOBAL_WINDOW_SIZE];

From: Marek Lindner lindner_marek@yahoo.de

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- Needed to add a lot of _rcu stuff here and I am sure many things are still wrong here.

batman-adv/originator.c | 35 ++++++++++++++++++++++++++++------- batman-adv/routing.c | 41 +++++++++++++++++++++++++++-------------- batman-adv/types.h | 2 ++ 3 files changed, 57 insertions(+), 21 deletions(-)

diff --git a/batman-adv/originator.c b/batman-adv/originator.c index 1df73e3..4d6d125 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -67,6 +67,14 @@ void neigh_node_free_ref(struct kref *refcount) kfree(neigh_node); }

+static void neigh_node_free_rcu(struct rcu_head *rcu) +{ + struct neigh_node *neigh_node; + + neigh_node = container_of(rcu, struct neigh_node, rcu); + kref_put(&neigh_node->refcount, neigh_node_free_ref); +} + struct neigh_node *create_neighbor(struct orig_node *orig_node, struct orig_node *orig_neigh_node, uint8_t *neigh, @@ -89,7 +97,9 @@ struct neigh_node *create_neighbor(struct orig_node *orig_node, neigh_node->if_incoming = if_incoming; kref_init(&neigh_node->refcount);

- hlist_add_head(&neigh_node->list, &orig_node->neigh_list); + spin_lock_bh(&orig_node->neigh_list_lock); + hlist_add_head_rcu(&neigh_node->list, &orig_node->neigh_list); + spin_unlock_bh(&orig_node->neigh_list_lock); return neigh_node; }

@@ -100,13 +110,17 @@ static void free_orig_node(void *data, void *arg) struct orig_node *orig_node = (struct orig_node *)data; struct bat_priv *bat_priv = (struct bat_priv *)arg;

+ spin_lock_bh(&orig_node->neigh_list_lock); + /* for all neighbors towards this originator ... */ hlist_for_each_entry_safe(neigh_node, node, node_tmp, &orig_node->neigh_list, list) { - hlist_del(&neigh_node->list); - kref_put(&neigh_node->refcount, neigh_node_free_ref); + hlist_del_rcu(&neigh_node->list); + call_rcu(&neigh_node->rcu, neigh_node_free_rcu); }

+ spin_unlock_bh(&orig_node->neigh_list_lock); + frag_list_free(&orig_node->frag_list); hna_global_del_orig(bat_priv, orig_node, "originator timed out");

@@ -151,6 +165,7 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) return NULL;

INIT_HLIST_HEAD(&orig_node->neigh_list); + spin_lock_init(&orig_node->neigh_list_lock);

memcpy(orig_node->orig, addr, ETH_ALEN); orig_node->router = NULL; @@ -200,6 +215,8 @@ static bool purge_orig_neighbors(struct bat_priv *bat_priv,

*best_neigh_node = NULL;

+ spin_lock_bh(&orig_node->neigh_list_lock); + /* for all neighbors towards this originator ... */ hlist_for_each_entry_safe(neigh_node, node, node_tmp, &orig_node->neigh_list, list) { @@ -225,14 +242,16 @@ static bool purge_orig_neighbors(struct bat_priv *bat_priv,

neigh_purged = true;

- hlist_del(&neigh_node->list); - kref_put(&neigh_node->refcount, neigh_node_free_ref); + hlist_del_rcu(&neigh_node->list); + call_rcu(&neigh_node->rcu, neigh_node_free_rcu); } else { if ((*best_neigh_node == NULL) || (neigh_node->tq_avg > (*best_neigh_node)->tq_avg)) *best_neigh_node = neigh_node; } } + + spin_unlock_bh(&orig_node->neigh_list_lock); return neigh_purged; }

@@ -384,11 +403,13 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) neigh_node->addr, neigh_node->if_incoming->net_dev->name);

- hlist_for_each_entry(neigh_node, node, - &orig_node->neigh_list, list) { + rcu_read_lock(); + hlist_for_each_entry_rcu(neigh_node, node, + &orig_node->neigh_list, list) { seq_printf(seq, " %pM (%3i)", neigh_node->addr, neigh_node->tq_avg); } + rcu_read_unlock();

seq_printf(seq, "\n"); batman_count++; diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 773c1ba..ae383d6 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -154,14 +154,16 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, unsigned char total_count;

if (orig_node == orig_neigh_node) { - hlist_for_each_entry(tmp_neigh_node, node, - &orig_node->neigh_list, list) { + rcu_read_lock(); + hlist_for_each_entry_rcu(tmp_neigh_node, node, + &orig_node->neigh_list, list) {

if (compare_orig(tmp_neigh_node->addr, orig_neigh_node->orig) && (tmp_neigh_node->if_incoming == if_incoming)) neigh_node = tmp_neigh_node; } + rcu_read_unlock();

if (!neigh_node) neigh_node = create_neighbor(orig_node, @@ -175,14 +177,16 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, neigh_node->last_valid = jiffies; } else { /* find packet count of corresponding one hop neighbor */ - hlist_for_each_entry(tmp_neigh_node, node, - &orig_neigh_node->neigh_list, list) { + rcu_read_lock(); + hlist_for_each_entry_rcu(tmp_neigh_node, node, + &orig_neigh_node->neigh_list, list) {

if (compare_orig(tmp_neigh_node->addr, orig_neigh_node->orig) && (tmp_neigh_node->if_incoming == if_incoming)) neigh_node = tmp_neigh_node; } + rcu_read_unlock();

if (!neigh_node) neigh_node = create_neighbor(orig_neigh_node, @@ -267,8 +271,9 @@ static void update_orig(struct bat_priv *bat_priv, bat_dbg(DBG_BATMAN, bat_priv, "update_originator(): " "Searching and updating originator entry of received packet\n");

- hlist_for_each_entry(tmp_neigh_node, node, - &orig_node->neigh_list, list) { + rcu_read_lock(); + hlist_for_each_entry_rcu(tmp_neigh_node, node, + &orig_node->neigh_list, list) { if (compare_orig(tmp_neigh_node->addr, ethhdr->h_source) && (tmp_neigh_node->if_incoming == if_incoming)) { neigh_node = tmp_neigh_node; @@ -283,6 +288,7 @@ static void update_orig(struct bat_priv *bat_priv, tmp_neigh_node->tq_avg = ring_buffer_avg(tmp_neigh_node->tq_recv); } + rcu_read_unlock();

if (!neigh_node) { struct orig_node *orig_tmp; @@ -411,8 +417,9 @@ static char count_real_packets(struct ethhdr *ethhdr, &orig_node->batman_seqno_reset)) return -1;

- hlist_for_each_entry(tmp_neigh_node, node, - &orig_node->neigh_list, list) { + rcu_read_lock(); + hlist_for_each_entry_rcu(tmp_neigh_node, node, + &orig_node->neigh_list, list) {

is_duplicate |= get_bit_status(tmp_neigh_node->real_bits, orig_node->last_real_seqno, @@ -432,6 +439,7 @@ static char count_real_packets(struct ethhdr *ethhdr, tmp_neigh_node->real_packet_count = bit_packet_count(tmp_neigh_node->real_bits); } + rcu_read_unlock();

if (need_update) { bat_dbg(DBG_BATMAN, bat_priv, @@ -484,15 +492,19 @@ void update_bonding_candidates(struct bat_priv *bat_priv, * as "bonding partner" */

/* first, zero the list */ - hlist_for_each_entry(tmp_neigh_node, node, - &orig_node->neigh_list, list) { + rcu_read_lock(); + hlist_for_each_entry_rcu(tmp_neigh_node, node, + &orig_node->neigh_list, list) { tmp_neigh_node->next_bond_candidate = NULL; } + rcu_read_unlock();

first_candidate = NULL; last_candidate = NULL; - hlist_for_each_entry(tmp_neigh_node, node, - &orig_node->neigh_list, list) { + + rcu_read_lock(); + hlist_for_each_entry_rcu(tmp_neigh_node, node, + &orig_node->neigh_list, list) {

/* only consider if it has the same primary address ... */ if (memcmp(orig_node->orig, @@ -509,8 +521,8 @@ void update_bonding_candidates(struct bat_priv *bat_priv, * select this candidate because of possible interference. */

interference_candidate = 0; - hlist_for_each_entry(tmp_neigh_node2, node2, - &orig_node->neigh_list, list) { + hlist_for_each_entry_rcu(tmp_neigh_node2, node2, + &orig_node->neigh_list, list) {

if (tmp_neigh_node2 == tmp_neigh_node) continue; @@ -544,6 +556,7 @@ void update_bonding_candidates(struct bat_priv *bat_priv,

candidates++; } + rcu_read_unlock();

if (candidates > 0) { first_candidate->next_bond_candidate = last_candidate; diff --git a/batman-adv/types.h b/batman-adv/types.h index 1ce91f6..1d6365d 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -85,6 +85,7 @@ struct orig_node { uint32_t last_bcast_seqno; struct hlist_head neigh_list; struct list_head frag_list; + spinlock_t neigh_list_lock; /* protects neighbor list */ unsigned long last_frag_packet; struct { uint8_t candidates; @@ -116,6 +117,7 @@ struct neigh_node { unsigned long last_valid; TYPE_OF_WORD real_bits[NUM_WORDS]; struct kref refcount; + struct rcu_head rcu; struct orig_node *orig_node; struct batman_if *if_incoming; };

From: Marek Lindner lindner_marek@yahoo.de

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- Could we move those '!= NULL' and ' == ' as an extra patch?

batman-adv/hash.c | 36 +++++++++++++----- batman-adv/hash.h | 77 ++++++++++++++++++++++++++------------- batman-adv/icmp_socket.c | 2 + batman-adv/originator.c | 27 ++++++++++---- batman-adv/routing.c | 16 ++++++++- batman-adv/translation-table.c | 14 +++++++ batman-adv/unicast.c | 7 +++- batman-adv/vis.c | 18 +++++++-- 8 files changed, 148 insertions(+), 49 deletions(-)

diff --git a/batman-adv/hash.c b/batman-adv/hash.c index fec9bbd..aaf3e0c 100644 --- a/batman-adv/hash.c +++ b/batman-adv/hash.c @@ -27,13 +27,16 @@ static void hash_init(struct hashtable_t *hash) { int i;

- for (i = 0 ; i < hash->size; i++) + for (i = 0 ; i < hash->size; i++) { INIT_HLIST_HEAD(&hash->table[i]); + spin_lock_init(&hash->list_locks[i]); + } }

/* free only the hashtable and the hash itself. */ void hash_destroy(struct hashtable_t *hash) { + kfree(hash->list_locks); kfree(hash->table); kfree(hash); } @@ -43,20 +46,33 @@ struct hashtable_t *hash_new(int size) { struct hashtable_t *hash;

- hash = kmalloc(sizeof(struct hashtable_t) , GFP_ATOMIC); - - if (hash == NULL) + hash = kmalloc(sizeof(struct hashtable_t), GFP_ATOMIC); + if (!hash) return NULL;

- hash->size = size; hash->table = kmalloc(sizeof(struct element_t *) * size, GFP_ATOMIC); + if (!hash->table) + goto free_hash;

- if (hash->table == NULL) { - kfree(hash); - return NULL; - } + hash->list_locks = kmalloc(sizeof(spinlock_t) * size, GFP_ATOMIC); + if (!hash->list_locks) + goto free_table;

+ hash->size = size; hash_init(hash); - return hash; + +free_table: + kfree(hash->table); +free_hash: + kfree(hash); + return NULL; +} + +void bucket_free_rcu(struct rcu_head *rcu) +{ + struct element_t *bucket; + + bucket = container_of(rcu, struct element_t, rcu); + kfree(bucket); } diff --git a/batman-adv/hash.h b/batman-adv/hash.h index 0801f9c..d47735c 100644 --- a/batman-adv/hash.h +++ b/batman-adv/hash.h @@ -39,10 +39,12 @@ typedef void (*hashdata_free_cb)(void *, void *); struct element_t { void *data; /* pointer to the data */ struct hlist_node hlist; /* bucket list pointer */ + struct rcu_head rcu; };

struct hashtable_t { - struct hlist_head *table; /* the hashtable itself, with the buckets */ + struct hlist_head *table; /* the hashtable itself with the buckets */ + spinlock_t *list_locks; /* spinlock for each hash list entry */ int size; /* size of hashtable */ };

@@ -57,6 +59,8 @@ void *hash_remove_element(struct hashtable_t *hash, struct element_t *elem); /* free only the hashtable and the hash itself. */ void hash_destroy(struct hashtable_t *hash);

+void bucket_free_rcu(struct rcu_head *rcu); + /* 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. */ @@ -66,19 +70,22 @@ static inline void hash_delete(struct hashtable_t *hash, struct hlist_head *head; struct hlist_node *walk, *safe; struct element_t *bucket; + spinlock_t *list_lock; int i;

for (i = 0; i < hash->size; i++) { head = &hash->table[i]; + list_lock = &hash->list_locks[i];

- hlist_for_each_safe(walk, safe, head) { - bucket = hlist_entry(walk, struct element_t, hlist); - if (free_cb != NULL) + spin_lock_bh(list_lock); + hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { + if (free_cb) free_cb(bucket->data, arg);

- hlist_del(walk); - kfree(bucket); + hlist_del_rcu(walk); + call_rcu(&bucket->rcu, bucket_free_rcu); } + spin_unlock_bh(list_lock); }

hash_destroy(hash); @@ -93,29 +100,39 @@ static inline int hash_add(struct hashtable_t *hash, struct hlist_head *head; struct hlist_node *walk, *safe; struct element_t *bucket; + spinlock_t *list_lock;

if (!hash) - return -1; + goto err;

index = choose(data, hash->size); head = &hash->table[index]; + list_lock = &hash->list_locks[index];

- hlist_for_each_safe(walk, safe, head) { - bucket = hlist_entry(walk, struct element_t, hlist); + rcu_read_lock(); + hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { if (compare(bucket->data, data)) - return -1; + goto err_unlock; } + rcu_read_unlock();

/* no duplicate found in list, add new element */ bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC); - - if (bucket == NULL) - return -1; + if (!bucket) + goto err;

bucket->data = data; - hlist_add_head(&bucket->hlist, head); + + spin_lock_bh(list_lock); + hlist_add_head_rcu(&bucket->hlist, head); + spin_unlock_bh(list_lock);

return 0; + +err_unlock: + rcu_read_unlock(); +err: + return -1; }

/* removes data from hash, if found. returns pointer do data on success, so you @@ -130,25 +147,31 @@ static inline void *hash_remove(struct hashtable_t *hash, struct hlist_node *walk; struct element_t *bucket; struct hlist_head *head; - void *data_save; + void *data_save = NULL;

index = choose(data, hash->size); head = &hash->table[index];

+ spin_lock_bh(&hash->list_locks[index]); hlist_for_each_entry(bucket, walk, head, hlist) { if (compare(bucket->data, data)) { data_save = bucket->data; - hlist_del(walk); - kfree(bucket); - return data_save; + hlist_del_rcu(walk); + call_rcu(&bucket->rcu, bucket_free_rcu); + break; } } + spin_unlock_bh(&hash->list_locks[index]);

- return NULL; + return data_save; }

-/* finds data, based on the key in keydata. returns the found data on success, - * or NULL on error */ +/** + * finds data, based on the key in keydata. returns the found data on success, + * or NULL on error + * + * caller must lock with rcu_read_lock() / rcu_read_unlock() + **/ static inline void *hash_find(struct hashtable_t *hash, hashdata_compare_cb compare, hashdata_choose_cb choose, void *keydata) @@ -157,6 +180,7 @@ static inline void *hash_find(struct hashtable_t *hash, struct hlist_head *head; struct hlist_node *walk; struct element_t *bucket; + void *bucket_data = NULL;

if (!hash) return NULL; @@ -164,13 +188,14 @@ static inline void *hash_find(struct hashtable_t *hash, index = choose(keydata , hash->size); head = &hash->table[index];

- hlist_for_each(walk, head) { - bucket = hlist_entry(walk, struct element_t, hlist); - if (compare(bucket->data, keydata)) - return bucket->data; + hlist_for_each_entry(bucket, walk, head, hlist) { + if (compare(bucket->data, keydata)) { + bucket_data = bucket->data; + break; + } }

- return NULL; + return bucket_data; }

#endif /* _NET_BATMAN_ADV_HASH_H_ */ diff --git a/batman-adv/icmp_socket.c b/batman-adv/icmp_socket.c index ecf6d7f..a9a10ed 100644 --- a/batman-adv/icmp_socket.c +++ b/batman-adv/icmp_socket.c @@ -221,9 +221,11 @@ static ssize_t bat_socket_write(struct file *file, const char __user *buff, goto dst_unreach;

spin_lock_bh(&bat_priv->orig_hash_lock); + rcu_read_lock(); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, choose_orig, icmp_packet->dst)); + rcu_read_unlock();

if (!orig_node) goto unlock; diff --git a/batman-adv/originator.c b/batman-adv/originator.c index 4d6d125..a43cda4 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -150,9 +150,11 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) int size; int hash_added;

+ rcu_read_lock(); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, choose_orig, addr)); + rcu_read_unlock();

if (orig_node) return orig_node; @@ -289,6 +291,7 @@ static void _purge_orig(struct bat_priv *bat_priv) struct hlist_node *walk, *safe; struct hlist_head *head; struct element_t *bucket; + spinlock_t *list_lock; struct orig_node *orig_node; int i;

@@ -300,22 +303,26 @@ static void _purge_orig(struct bat_priv *bat_priv) /* for all origins... */ for (i = 0; i < hash->size; i++) { head = &hash->table[i]; + list_lock = &hash->list_locks[i];

+ spin_lock_bh(list_lock); hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { orig_node = bucket->data;

if (purge_orig_node(bat_priv, orig_node)) { if (orig_node->gw_flags) gw_node_delete(bat_priv, orig_node); - hlist_del(walk); - kfree(bucket); + hlist_del_rcu(walk); + call_rcu(&bucket->rcu, bucket_free_rcu); free_orig_node(orig_node, bat_priv); + continue; }

if (time_after(jiffies, orig_node->last_frag_packet + msecs_to_jiffies(FRAG_TIMEOUT))) frag_list_free(&orig_node->frag_list); } + spin_unlock_bh(list_lock); }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -382,7 +389,8 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) for (i = 0; i < hash->size; i++) { head = &hash->table[i];

- hlist_for_each_entry(bucket, walk, head, hlist) { + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data;

if (!orig_node->router) @@ -403,17 +411,16 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) neigh_node->addr, neigh_node->if_incoming->net_dev->name);

- rcu_read_lock(); hlist_for_each_entry_rcu(neigh_node, node, &orig_node->neigh_list, list) { seq_printf(seq, " %pM (%3i)", neigh_node->addr, neigh_node->tq_avg); } - rcu_read_unlock();

seq_printf(seq, "\n"); batman_count++; } + rcu_read_unlock(); }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -471,18 +478,21 @@ int orig_hash_add_if(struct batman_if *batman_if, int max_if_num) for (i = 0; i < hash->size; i++) { head = &hash->table[i];

- hlist_for_each_entry(bucket, walk, head, hlist) { + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data;

if (orig_node_add_if(orig_node, max_if_num) == -1) goto err; } + rcu_read_unlock(); }

spin_unlock_bh(&bat_priv->orig_hash_lock); return 0;

err: + rcu_read_unlock(); spin_unlock_bh(&bat_priv->orig_hash_lock); return -ENOMEM; } @@ -557,7 +567,8 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) for (i = 0; i < hash->size; i++) { head = &hash->table[i];

- hlist_for_each_entry(bucket, walk, head, hlist) { + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data;

ret = orig_node_del_if(orig_node, max_if_num, @@ -566,6 +577,7 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) if (ret == -1) goto err; } + rcu_read_unlock(); }

/* renumber remaining batman interfaces _inside_ of orig_hash_lock */ @@ -590,6 +602,7 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) return 0;

err: + rcu_read_unlock(); spin_unlock_bh(&bat_priv->orig_hash_lock); return -ENOMEM; } diff --git a/batman-adv/routing.c b/batman-adv/routing.c index ae383d6..035f159 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -53,7 +53,8 @@ void slide_own_bcast_window(struct batman_if *batman_if) for (i = 0; i < hash->size; i++) { head = &hash->table[i];

- hlist_for_each_entry(bucket, walk, head, hlist) { + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data; word_index = batman_if->if_num * NUM_WORDS; word = &(orig_node->bcast_own[word_index]); @@ -62,6 +63,7 @@ void slide_own_bcast_window(struct batman_if *batman_if) orig_node->bcast_own_sum[batman_if->if_num] = bit_packet_count(word); } + rcu_read_unlock(); }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -858,9 +860,11 @@ static int recv_my_icmp_packet(struct bat_priv *bat_priv, /* answer echo request (ping) */ /* get routing information */ spin_lock_bh(&bat_priv->orig_hash_lock); + rcu_read_lock(); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, choose_orig, icmp_packet->orig)); + rcu_read_unlock(); ret = NET_RX_DROP;

if ((orig_node != NULL) && @@ -920,9 +924,11 @@ static int recv_icmp_ttl_exceeded(struct bat_priv *bat_priv,

/* get routing information */ spin_lock_bh(&bat_priv->orig_hash_lock); + rcu_read_lock(); orig_node = ((struct orig_node *) hash_find(bat_priv->orig_hash, compare_orig, choose_orig, icmp_packet->orig)); + rcu_read_unlock(); ret = NET_RX_DROP;

if ((orig_node != NULL) && @@ -1014,9 +1020,11 @@ int recv_icmp_packet(struct sk_buff *skb, struct batman_if *recv_if)

/* get routing information */ spin_lock_bh(&bat_priv->orig_hash_lock); + rcu_read_lock(); orig_node = ((struct orig_node *) hash_find(bat_priv->orig_hash, compare_orig, choose_orig, icmp_packet->dst)); + rcu_read_unlock();

if ((orig_node != NULL) && (orig_node->router != NULL)) { @@ -1087,9 +1095,11 @@ struct neigh_node *find_router(struct bat_priv *bat_priv, router_orig->orig, ETH_ALEN) == 0) { primary_orig_node = router_orig; } else { + rcu_read_lock(); primary_orig_node = hash_find(bat_priv->orig_hash, compare_orig, choose_orig, router_orig->primary_addr); + rcu_read_unlock();

if (!primary_orig_node) return orig_node->router; @@ -1192,9 +1202,11 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if,

/* get routing information */ spin_lock_bh(&bat_priv->orig_hash_lock); + rcu_read_lock(); orig_node = ((struct orig_node *) hash_find(bat_priv->orig_hash, compare_orig, choose_orig, unicast_packet->dest)); + rcu_read_unlock();

router = find_router(bat_priv, orig_node, recv_if);

@@ -1338,9 +1350,11 @@ int recv_bcast_packet(struct sk_buff *skb, struct batman_if *recv_if) return NET_RX_DROP;

spin_lock_bh(&bat_priv->orig_hash_lock); + rcu_read_lock(); orig_node = ((struct orig_node *) hash_find(bat_priv->orig_hash, compare_orig, choose_orig, bcast_packet->orig)); + rcu_read_unlock();

if (orig_node == NULL) { spin_unlock_bh(&bat_priv->orig_hash_lock); diff --git a/batman-adv/translation-table.c b/batman-adv/translation-table.c index a19e16c..6f6ee58 100644 --- a/batman-adv/translation-table.c +++ b/batman-adv/translation-table.c @@ -61,10 +61,12 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) int required_bytes;

spin_lock_bh(&bat_priv->hna_lhash_lock); + rcu_read_lock(); hna_local_entry = ((struct hna_local_entry *)hash_find(bat_priv->hna_local_hash, compare_orig, choose_orig, addr)); + rcu_read_unlock(); spin_unlock_bh(&bat_priv->hna_lhash_lock);

if (hna_local_entry) { @@ -117,9 +119,11 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) /* remove address from global hash if present */ spin_lock_bh(&bat_priv->hna_ghash_lock);

+ rcu_read_lock(); hna_global_entry = ((struct hna_global_entry *) hash_find(bat_priv->hna_global_hash, compare_orig, choose_orig, addr)); + rcu_read_unlock();

if (hna_global_entry) _hna_global_del_orig(bat_priv, hna_global_entry, @@ -253,9 +257,11 @@ void hna_local_remove(struct bat_priv *bat_priv,

spin_lock_bh(&bat_priv->hna_lhash_lock);

+ rcu_read_lock(); hna_local_entry = (struct hna_local_entry *) hash_find(bat_priv->hna_local_hash, compare_orig, choose_orig, addr); + rcu_read_unlock();

if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, message); @@ -335,9 +341,11 @@ void hna_global_add_orig(struct bat_priv *bat_priv, spin_lock_bh(&bat_priv->hna_ghash_lock);

hna_ptr = hna_buff + (hna_buff_count * ETH_ALEN); + rcu_read_lock(); hna_global_entry = (struct hna_global_entry *) hash_find(bat_priv->hna_global_hash, compare_orig, choose_orig, hna_ptr); + rcu_read_unlock();

if (!hna_global_entry) { spin_unlock_bh(&bat_priv->hna_ghash_lock); @@ -369,9 +377,11 @@ void hna_global_add_orig(struct bat_priv *bat_priv, spin_lock_bh(&bat_priv->hna_lhash_lock);

hna_ptr = hna_buff + (hna_buff_count * ETH_ALEN); + rcu_read_lock(); hna_local_entry = (struct hna_local_entry *) hash_find(bat_priv->hna_local_hash, compare_orig, choose_orig, hna_ptr); + rcu_read_unlock();

if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, @@ -484,9 +494,11 @@ void hna_global_del_orig(struct bat_priv *bat_priv,

while ((hna_buff_count + 1) * ETH_ALEN <= orig_node->hna_buff_len) { hna_ptr = orig_node->hna_buff + (hna_buff_count * ETH_ALEN); + rcu_read_lock(); hna_global_entry = (struct hna_global_entry *) hash_find(bat_priv->hna_global_hash, compare_orig, choose_orig, hna_ptr); + rcu_read_unlock();

if ((hna_global_entry) && (hna_global_entry->orig_node == orig_node)) @@ -522,9 +534,11 @@ struct orig_node *transtable_search(struct bat_priv *bat_priv, uint8_t *addr) struct hna_global_entry *hna_global_entry;

spin_lock_bh(&bat_priv->hna_ghash_lock); + rcu_read_lock(); hna_global_entry = (struct hna_global_entry *) hash_find(bat_priv->hna_global_hash, compare_orig, choose_orig, addr); + rcu_read_unlock(); spin_unlock_bh(&bat_priv->hna_ghash_lock);

if (!hna_global_entry) diff --git a/batman-adv/unicast.c b/batman-adv/unicast.c index dc2e28b..0b2ea82 100644 --- a/batman-adv/unicast.c +++ b/batman-adv/unicast.c @@ -179,9 +179,11 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv,

*new_skb = NULL; spin_lock_bh(&bat_priv->orig_hash_lock); + rcu_read_lock(); orig_node = ((struct orig_node *) hash_find(bat_priv->orig_hash, compare_orig, choose_orig, unicast_packet->orig)); + rcu_read_unlock();

if (!orig_node) { pr_debug("couldn't find originator in orig_hash\n"); @@ -285,11 +287,14 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv) /* get routing information */ if (is_multicast_ether_addr(ethhdr->h_dest)) orig_node = (struct orig_node *)gw_get_selected(bat_priv); - else + else { + rcu_read_lock(); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, choose_orig, ethhdr->h_dest)); + rcu_read_unlock(); + }

/* check for hna host */ if (!orig_node) diff --git a/batman-adv/vis.c b/batman-adv/vis.c index d7f5b6b..653673e 100644 --- a/batman-adv/vis.c +++ b/batman-adv/vis.c @@ -380,8 +380,10 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, sizeof(struct vis_packet));

memcpy(search_packet->vis_orig, vis_packet->vis_orig, ETH_ALEN); + rcu_read_lock(); old_info = hash_find(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, &search_elem); + rcu_read_unlock(); kfree_skb(search_elem.skb_packet);

if (old_info != NULL) { @@ -540,7 +542,8 @@ static int find_best_vis_server(struct bat_priv *bat_priv, for (i = 0; i < hash->size; i++) { head = &hash->table[i];

- hlist_for_each_entry(bucket, walk, head, hlist) { + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data; if ((orig_node) && (orig_node->router) && (orig_node->flags & VIS_SERVER) && @@ -550,6 +553,7 @@ static int find_best_vis_server(struct bat_priv *bat_priv, ETH_ALEN); } } + rcu_read_unlock(); }

return best_tq; @@ -605,7 +609,8 @@ static int generate_vis_packet(struct bat_priv *bat_priv) for (i = 0; i < hash->size; i++) { head = &hash->table[i];

- hlist_for_each_entry(bucket, walk, head, hlist) { + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data; neigh_node = orig_node->router;

@@ -632,10 +637,12 @@ static int generate_vis_packet(struct bat_priv *bat_priv) packet->entries++;

if (vis_packet_full(info)) { + rcu_read_unlock(); spin_unlock_bh(&bat_priv->orig_hash_lock); return 0; } } + rcu_read_unlock(); }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -721,7 +728,8 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, for (i = 0; i < hash->size; i++) { head = &hash->table[i];

- hlist_for_each_entry(bucket, walk, head, hlist) { + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data;

/* if it's a vis server and reachable, send it. */ @@ -746,7 +754,7 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv,

spin_lock_bh(&bat_priv->orig_hash_lock); } - + rcu_read_unlock(); }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -763,9 +771,11 @@ static void unicast_vis_packet(struct bat_priv *bat_priv,

spin_lock_bh(&bat_priv->orig_hash_lock); packet = (struct vis_packet *)info->skb_packet->data; + rcu_read_lock(); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, choose_orig, packet->target_orig)); + rcu_read_unlock();

if ((!orig_node) || (!orig_node->router)) goto out;

From: Marek Lindner lindner_marek@yahoo.de

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- batman-adv/originator.c | 11 +++++++++-- batman-adv/routing.c | 27 +++++++++++++++++++++++---- batman-adv/types.h | 1 + 3 files changed, 33 insertions(+), 6 deletions(-)

diff --git a/batman-adv/originator.c b/batman-adv/originator.c index fa34ea0..6a97879 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -195,6 +195,7 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) return NULL;

INIT_HLIST_HEAD(&orig_node->neigh_list); + spin_lock_init(&orig_node->ogm_cnt_lock); spin_lock_init(&orig_node->neigh_list_lock); kref_init(&orig_node->refcount);

@@ -502,7 +503,7 @@ int orig_hash_add_if(struct batman_if *batman_if, int max_if_num) struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; - int i; + int i, ret;

/* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ @@ -515,7 +516,11 @@ int orig_hash_add_if(struct batman_if *batman_if, int max_if_num) hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data;

- if (orig_node_add_if(orig_node, max_if_num) == -1) + spin_lock_bh(&orig_node->ogm_cnt_lock); + ret = orig_node_add_if(orig_node, max_if_num); + spin_unlock_bh(&orig_node->ogm_cnt_lock); + + if (ret == -1) goto err; } rcu_read_unlock(); @@ -604,8 +609,10 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data;

+ spin_lock_bh(&orig_node->ogm_cnt_lock); ret = orig_node_del_if(orig_node, max_if_num, batman_if->if_num); + spin_unlock_bh(&orig_node->ogm_cnt_lock);

if (ret == -1) goto err; diff --git a/batman-adv/routing.c b/batman-adv/routing.c index a9a30ff..aa3f21a 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -56,12 +56,14 @@ void slide_own_bcast_window(struct batman_if *batman_if) rcu_read_lock(); hlist_for_each_entry_rcu(bucket, walk, head, hlist) { orig_node = bucket->data; + spin_lock_bh(&orig_node->ogm_cnt_lock); word_index = batman_if->if_num * NUM_WORDS; word = &(orig_node->bcast_own[word_index]);

bit_get_packet(bat_priv, word, 1, 0); orig_node->bcast_own_sum[batman_if->if_num] = bit_packet_count(word); + spin_unlock_bh(&orig_node->ogm_cnt_lock); } rcu_read_unlock(); } @@ -267,8 +269,10 @@ static void update_orig(struct bat_priv *bat_priv, char is_duplicate) { struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL; + struct orig_node *orig_node_tmp; struct hlist_node *node; int tmp_hna_buff_len; + uint8_t bcast_own_sum_orig, bcast_own_sum_neigh;

bat_dbg(DBG_BATMAN, bat_priv, "update_originator(): " "Searching and updating originator entry of received packet\n"); @@ -338,10 +342,22 @@ static void update_orig(struct bat_priv *bat_priv, /* if the TQ is the same and the link not more symetric we * won't consider it either */ if ((orig_node->router) && - ((neigh_node->tq_avg == orig_node->router->tq_avg) && - (orig_node->router->orig_node->bcast_own_sum[if_incoming->if_num] - >= neigh_node->orig_node->bcast_own_sum[if_incoming->if_num]))) - goto update_hna; + (neigh_node->tq_avg == orig_node->router->tq_avg)) { + orig_node_tmp = orig_node->router->orig_node; + spin_lock_bh(&orig_node_tmp->ogm_cnt_lock); + bcast_own_sum_orig = + orig_node_tmp->bcast_own_sum[if_incoming->if_num]; + spin_unlock_bh(&orig_node_tmp->ogm_cnt_lock); + + orig_node_tmp = neigh_node->orig_node; + spin_lock_bh(&orig_node_tmp->ogm_cnt_lock); + bcast_own_sum_neigh = + orig_node_tmp->bcast_own_sum[if_incoming->if_num]; + spin_unlock_bh(&orig_node_tmp->ogm_cnt_lock); + + if (bcast_own_sum_orig >= bcast_own_sum_neigh) + goto update_hna; + }

update_routes(bat_priv, orig_node, neigh_node, hna_buff, tmp_hna_buff_len); @@ -686,10 +702,13 @@ void receive_bat_packet(struct ethhdr *ethhdr, batman_packet->orig) && (batman_packet->seqno - if_incoming_seqno + 2 == 0)) { offset = if_incoming->if_num * NUM_WORDS; + + spin_lock_bh(&orig_neigh_node->ogm_cnt_lock); word = &(orig_neigh_node->bcast_own[offset]); bit_mark(word, 0); orig_neigh_node->bcast_own_sum[if_incoming->if_num] = bit_packet_count(word); + spin_unlock_bh(&orig_neigh_node->ogm_cnt_lock); }

bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: " diff --git a/batman-adv/types.h b/batman-adv/types.h index f4ce526..de4efa0 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -89,6 +89,7 @@ struct orig_node { struct kref refcount; struct bat_priv *bat_priv; unsigned long last_frag_packet; + spinlock_t ogm_cnt_lock; /* protects ogm counter */ struct { uint8_t candidates; struct neigh_node *selected;