* [B.A.T.M.A.N.] reordered rcu (part II)
@ 2011-02-09 18:18 Marek Lindner
2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 1/2] batman-adv: separate ethernet comparing calls from hash functions Marek Lindner
` (4 more replies)
0 siblings, 5 replies; 9+ messages in thread
From: Marek Lindner @ 2011-02-09 18:18 UTC (permalink / raw)
To: b.a.t.m.a.n
Hi,
here comes the next batch of changes to make the code "rcu safe". It won't be
the last one but should make all follow-ups much easier.
Regards,
Marek
^ permalink raw reply [flat|nested] 9+ messages in thread* [B.A.T.M.A.N.] [PATCH 1/2] batman-adv: separate ethernet comparing calls from hash functions 2011-02-09 18:18 [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner @ 2011-02-09 18:19 ` Marek Lindner 2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 2/2] batman-adv: remove extra layer between hash and hash element - hash bucket Marek Lindner ` (3 subsequent siblings) 4 siblings, 0 replies; 9+ messages in thread From: Marek Lindner @ 2011-02-09 18:19 UTC (permalink / raw) To: b.a.t.m.a.n; +Cc: Marek Lindner Note: The function compare_ether_addr() provided by the Linux kernel requires aligned memory. Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> --- batman-adv/hard-interface.c | 2 +- batman-adv/main.c | 2 +- batman-adv/main.h | 10 +++++++ batman-adv/routing.c | 55 +++++++++++++++++++-------------------- batman-adv/send.c | 2 +- batman-adv/soft-interface.c | 2 +- batman-adv/translation-table.c | 2 +- batman-adv/vis.c | 18 ++++++------ 8 files changed, 51 insertions(+), 42 deletions(-) diff --git a/batman-adv/hard-interface.c b/batman-adv/hard-interface.c index 8982485..de9bd36 100644 --- a/batman-adv/hard-interface.c +++ b/batman-adv/hard-interface.c @@ -187,7 +187,7 @@ static void check_known_mac_addr(struct net_device *net_dev) if (batman_if->net_dev == net_dev) continue; - if (!compare_orig(batman_if->net_dev->dev_addr, + if (!compare_eth(batman_if->net_dev->dev_addr, net_dev->dev_addr)) continue; diff --git a/batman-adv/main.c b/batman-adv/main.c index 658ad5a..09c21f2 100644 --- a/batman-adv/main.c +++ b/batman-adv/main.c @@ -160,7 +160,7 @@ int is_my_mac(uint8_t *addr) if (batman_if->if_status != IF_ACTIVE) continue; - if (compare_orig(batman_if->net_dev->dev_addr, addr)) { + if (compare_eth(batman_if->net_dev->dev_addr, addr)) { rcu_read_unlock(); return 1; } diff --git a/batman-adv/main.h b/batman-adv/main.h index bd8470d..57f0d24 100644 --- a/batman-adv/main.h +++ b/batman-adv/main.h @@ -167,4 +167,14 @@ static inline void bat_dbg(char type __always_unused, pr_err("%s: " fmt, _netdev->name, ## arg); \ } while (0) +/** + * returns 1 if they are the same ethernet addr + * + * note: can't use compare_ether_addr() as it requires aligned memory + */ +static inline int compare_eth(void *data1, void *data2) +{ + return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); +} + #endif /* _NET_BATMAN_ADV_MAIN_H_ */ diff --git a/batman-adv/routing.c b/batman-adv/routing.c index a2b770a..892b463 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -159,8 +159,8 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, 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) && + if (compare_eth(tmp_neigh_node->addr, + orig_neigh_node->orig) && (tmp_neigh_node->if_incoming == if_incoming)) neigh_node = tmp_neigh_node; } @@ -188,8 +188,8 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, 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) && + if (compare_eth(tmp_neigh_node->addr, + orig_neigh_node->orig) && (tmp_neigh_node->if_incoming == if_incoming)) neigh_node = tmp_neigh_node; } @@ -300,8 +300,8 @@ static void bonding_candidate_add(struct orig_node *orig_node, spin_lock_bh(&orig_node->neigh_list_lock); /* only consider if it has the same primary address ... */ - if (!compare_orig(orig_node->orig, - neigh_node->orig_node->primary_addr)) + if (!compare_eth(orig_node->orig, + neigh_node->orig_node->primary_addr)) goto candidate_del; if (!orig_node->router) @@ -330,7 +330,7 @@ static void bonding_candidate_add(struct orig_node *orig_node, continue; if ((neigh_node->if_incoming == tmp_neigh_node->if_incoming) || - (compare_orig(neigh_node->addr, tmp_neigh_node->addr))) { + (compare_eth(neigh_node->addr, tmp_neigh_node->addr))) { interference_candidate = 1; break; } @@ -390,7 +390,7 @@ static void update_orig(struct bat_priv *bat_priv, 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) && + if (compare_eth(tmp_neigh_node->addr, ethhdr->h_source) && (tmp_neigh_node->if_incoming == if_incoming) && atomic_inc_not_zero(&tmp_neigh_node->refcount)) { if (neigh_node) @@ -575,7 +575,7 @@ static char count_real_packets(struct ethhdr *ethhdr, orig_node->last_real_seqno, batman_packet->seqno); - if (compare_orig(tmp_neigh_node->addr, ethhdr->h_source) && + if (compare_eth(tmp_neigh_node->addr, ethhdr->h_source) && (tmp_neigh_node->if_incoming == if_incoming)) set_mark = 1; else @@ -640,8 +640,8 @@ void receive_bat_packet(struct ethhdr *ethhdr, has_directlink_flag = (batman_packet->flags & DIRECTLINK ? 1 : 0); - is_single_hop_neigh = (compare_orig(ethhdr->h_source, - batman_packet->orig) ? 1 : 0); + is_single_hop_neigh = (compare_eth(ethhdr->h_source, + batman_packet->orig) ? 1 : 0); bat_dbg(DBG_BATMAN, bat_priv, "Received BATMAN packet via NB: %pM, IF: %s [%pM] " @@ -661,19 +661,19 @@ void receive_bat_packet(struct ethhdr *ethhdr, if (batman_if->soft_iface != if_incoming->soft_iface) continue; - if (compare_orig(ethhdr->h_source, - batman_if->net_dev->dev_addr)) + if (compare_eth(ethhdr->h_source, + batman_if->net_dev->dev_addr)) is_my_addr = 1; - if (compare_orig(batman_packet->orig, - batman_if->net_dev->dev_addr)) + if (compare_eth(batman_packet->orig, + batman_if->net_dev->dev_addr)) is_my_orig = 1; - if (compare_orig(batman_packet->prev_sender, - batman_if->net_dev->dev_addr)) + if (compare_eth(batman_packet->prev_sender, + batman_if->net_dev->dev_addr)) is_my_oldorig = 1; - if (compare_orig(ethhdr->h_source, broadcast_addr)) + if (compare_eth(ethhdr->h_source, broadcast_addr)) is_broadcast = 1; } rcu_read_unlock(); @@ -713,8 +713,8 @@ void receive_bat_packet(struct ethhdr *ethhdr, /* if received seqno equals last send seqno save new * seqno for bidirectional check */ if (has_directlink_flag && - compare_orig(if_incoming->net_dev->dev_addr, - batman_packet->orig) && + compare_eth(if_incoming->net_dev->dev_addr, + batman_packet->orig) && (batman_packet->seqno - if_incoming_seqno + 2 == 0)) { offset = if_incoming->if_num * NUM_WORDS; @@ -761,11 +761,11 @@ void receive_bat_packet(struct ethhdr *ethhdr, /* avoid temporary routing loops */ if ((orig_node->router) && (orig_node->router->orig_node->router) && - (compare_orig(orig_node->router->addr, - batman_packet->prev_sender)) && - !(compare_orig(batman_packet->orig, batman_packet->prev_sender)) && - (compare_orig(orig_node->router->addr, - orig_node->router->orig_node->router->addr))) { + (compare_eth(orig_node->router->addr, + batman_packet->prev_sender)) && + !(compare_eth(batman_packet->orig, batman_packet->prev_sender)) && + (compare_eth(orig_node->router->addr, + orig_node->router->orig_node->router->addr))) { bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: ignoring all rebroadcast packets that " "may make me loop (sender: %pM)\n", ethhdr->h_source); @@ -1146,14 +1146,13 @@ struct neigh_node *find_router(struct bat_priv *bat_priv, /* if we have something in the primary_addr, we can search * for a potential bonding candidate. */ - if (memcmp(router_orig->primary_addr, zero_mac, ETH_ALEN) == 0) + if (compare_eth(router_orig->primary_addr, zero_mac)) goto return_router; /* find the orig_node which has the primary interface. might * even be the same as our router_orig in many cases */ - if (memcmp(router_orig->primary_addr, - router_orig->orig, ETH_ALEN) == 0) { + if (compare_eth(router_orig->primary_addr, router_orig->orig)) { primary_orig_node = router_orig; } else { primary_orig_node = hash_find(bat_priv->orig_hash, compare_orig, diff --git a/batman-adv/send.c b/batman-adv/send.c index 8314276..f0232ad 100644 --- a/batman-adv/send.c +++ b/batman-adv/send.c @@ -326,7 +326,7 @@ void schedule_forward_packet(struct orig_node *orig_node, if ((orig_node->router) && (orig_node->router->tq_avg != 0)) { /* rebroadcast ogm of best ranking neighbor as is */ - if (!compare_orig(orig_node->router->addr, ethhdr->h_source)) { + if (!compare_eth(orig_node->router->addr, ethhdr->h_source)) { batman_packet->tq = orig_node->router->tq_avg; if (orig_node->router->last_ttl) diff --git a/batman-adv/soft-interface.c b/batman-adv/soft-interface.c index bd8b539..41f9f57 100644 --- a/batman-adv/soft-interface.c +++ b/batman-adv/soft-interface.c @@ -134,7 +134,7 @@ static struct softif_neigh *softif_neigh_get(struct bat_priv *bat_priv, rcu_read_lock(); hlist_for_each_entry_rcu(softif_neigh, node, &bat_priv->softif_neigh_list, list) { - if (memcmp(softif_neigh->addr, addr, ETH_ALEN) != 0) + if (!compare_eth(softif_neigh->addr, addr)) continue; if (softif_neigh->vid != vid) diff --git a/batman-adv/translation-table.c b/batman-adv/translation-table.c index 28a212a..b323c24 100644 --- a/batman-adv/translation-table.c +++ b/batman-adv/translation-table.c @@ -101,7 +101,7 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) hna_local_entry->last_seen = jiffies; /* the batman interface mac address should never be purged */ - if (compare_orig(addr, soft_iface->dev_addr)) + if (compare_eth(addr, soft_iface->dev_addr)) hna_local_entry->never_purge = 1; else hna_local_entry->never_purge = 0; diff --git a/batman-adv/vis.c b/batman-adv/vis.c index c1c3258..6435886 100644 --- a/batman-adv/vis.c +++ b/batman-adv/vis.c @@ -76,7 +76,7 @@ static int vis_info_cmp(void *data1, void *data2) d2 = data2; p1 = (struct vis_packet *)d1->skb_packet->data; p2 = (struct vis_packet *)d2->skb_packet->data; - return compare_orig(p1->vis_orig, p2->vis_orig); + return compare_eth(p1->vis_orig, p2->vis_orig); } /* hash function to choose an entry in a hash table of given size */ @@ -114,7 +114,7 @@ static void vis_data_insert_interface(const uint8_t *interface, struct hlist_node *pos; hlist_for_each_entry(entry, pos, if_list, list) { - if (compare_orig(entry->addr, (void *)interface)) + if (compare_eth(entry->addr, (void *)interface)) return; } @@ -166,7 +166,7 @@ static ssize_t vis_data_read_entry(char *buff, struct vis_info_entry *entry, /* maximal length: max(4+17+2, 3+17+1+3+2) == 26 */ if (primary && entry->quality == 0) return sprintf(buff, "HNA %pM, ", entry->dest); - else if (compare_orig(entry->src, src)) + else if (compare_eth(entry->src, src)) return sprintf(buff, "TQ %pM %d, ", entry->dest, entry->quality); @@ -213,7 +213,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) if (entries[j].quality == 0) continue; compare = - compare_orig(entries[j].src, packet->vis_orig); + compare_eth(entries[j].src, packet->vis_orig); vis_data_insert_interface(entries[j].src, &vis_if_list, compare); @@ -223,7 +223,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) buf_size += 18 + 26 * packet->entries; /* add primary/secondary records */ - if (compare_orig(entry->addr, packet->vis_orig)) + if (compare_eth(entry->addr, packet->vis_orig)) buf_size += vis_data_count_prim_sec(&vis_if_list); @@ -259,7 +259,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) if (entries[j].quality == 0) continue; compare = - compare_orig(entries[j].src, packet->vis_orig); + compare_eth(entries[j].src, packet->vis_orig); vis_data_insert_interface(entries[j].src, &vis_if_list, compare); @@ -277,7 +277,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) entry->primary); /* add primary/secondary records */ - if (compare_orig(entry->addr, packet->vis_orig)) + if (compare_eth(entry->addr, packet->vis_orig)) buff_pos += vis_data_read_prim_sec(buff + buff_pos, &vis_if_list); @@ -345,7 +345,7 @@ static int recv_list_is_in(struct bat_priv *bat_priv, spin_lock_bh(&bat_priv->vis_list_lock); list_for_each_entry(entry, recv_list, list) { - if (memcmp(entry->mac, mac, ETH_ALEN) == 0) { + if (compare_eth(entry->mac, mac)) { spin_unlock_bh(&bat_priv->vis_list_lock); return 1; } @@ -615,7 +615,7 @@ static int generate_vis_packet(struct bat_priv *bat_priv) if (!neigh_node) continue; - if (!compare_orig(neigh_node->addr, orig_node->orig)) + if (!compare_eth(neigh_node->addr, orig_node->orig)) continue; if (neigh_node->if_incoming->if_status != IF_ACTIVE) -- 1.7.2.3 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCH 2/2] batman-adv: remove extra layer between hash and hash element - hash bucket 2011-02-09 18:18 [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner 2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 1/2] batman-adv: separate ethernet comparing calls from hash functions Marek Lindner @ 2011-02-09 18:19 ` Marek Lindner 2011-02-10 13:03 ` Linus Lüssing 2011-02-13 21:36 ` [B.A.T.M.A.N.] [PATCHv2 2/4] " Marek Lindner 2011-02-13 21:39 ` [B.A.T.M.A.N.] [PATCH 3/4] batman-adv: Correct rcu refcounting for orig_node Marek Lindner ` (2 subsequent siblings) 4 siblings, 2 replies; 9+ messages in thread From: Marek Lindner @ 2011-02-09 18:19 UTC (permalink / raw) To: b.a.t.m.a.n; +Cc: Marek Lindner Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> --- batman-adv/compat.h | 8 ++ batman-adv/hash.c | 8 -- batman-adv/hash.h | 95 +++++-------------- batman-adv/icmp_socket.c | 5 +- batman-adv/originator.c | 71 ++++---------- batman-adv/originator.h | 34 +++++++- batman-adv/routing.c | 41 +++----- batman-adv/translation-table.c | 208 +++++++++++++++++++++++++-------------- batman-adv/types.h | 4 + batman-adv/unicast.c | 12 +-- batman-adv/vis.c | 102 +++++++++++--------- 11 files changed, 296 insertions(+), 292 deletions(-) diff --git a/batman-adv/compat.h b/batman-adv/compat.h index a76d0be..29a3203 100644 --- a/batman-adv/compat.h +++ b/batman-adv/compat.h @@ -270,4 +270,12 @@ int bat_seq_printf(struct seq_file *m, const char *f, ...); #endif /* < KERNEL_VERSION(2, 6, 33) */ +#define hlist_first_rcu(head) (*((struct hlist_node **)(&(head)->first))) +#define hlist_next_rcu(node) (*((struct hlist_node **)(&(node)->next))) + +#define __hlist_for_each_rcu(pos, head) \ + for (pos = rcu_dereference(hlist_first_rcu(head)); \ + pos && ({ prefetch(pos->next); 1; }); \ + pos = rcu_dereference(hlist_next_rcu(pos))) + #endif /* _NET_BATMAN_ADV_COMPAT_H_ */ diff --git a/batman-adv/hash.c b/batman-adv/hash.c index 0265366..c5213d8 100644 --- a/batman-adv/hash.c +++ b/batman-adv/hash.c @@ -68,11 +68,3 @@ 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 3c48c6b..434822b 100644 --- a/batman-adv/hash.h +++ b/batman-adv/hash.h @@ -28,19 +28,13 @@ * compare 2 element datas for their keys, * return 0 if same and not 0 if not * same */ -typedef int (*hashdata_compare_cb)(void *, void *); +typedef int (*hashdata_compare_cb)(struct hlist_node *, void *); /* the hashfunction, should return an index * based on the key in the data of the first * argument and the size the second */ typedef int (*hashdata_choose_cb)(void *, int); -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; -}; +typedef void (*hashdata_free_cb)(struct hlist_node *, void *); struct hashtable_t { struct hlist_head *table; /* the hashtable itself with the buckets */ @@ -54,8 +48,6 @@ struct hashtable_t *hash_new(int size); /* 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. */ @@ -63,8 +55,7 @@ static inline void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb, void *arg) { struct hlist_head *head; - struct hlist_node *walk, *safe; - struct element_t *bucket; + struct hlist_node *node, *node_tmp; spinlock_t *list_lock; /* spinlock to protect write access */ int i; @@ -73,12 +64,11 @@ static inline void hash_delete(struct hashtable_t *hash, list_lock = &hash->list_locks[i]; spin_lock_bh(list_lock); - hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { - if (free_cb) - free_cb(bucket->data, arg); + hlist_for_each_safe(node, node_tmp, head) { + hlist_del_rcu(node); - hlist_del_rcu(walk); - call_rcu(&bucket->rcu, bucket_free_rcu); + if (free_cb) + free_cb(node, arg); } spin_unlock_bh(list_lock); } @@ -89,12 +79,12 @@ static inline void hash_delete(struct hashtable_t *hash, /* adds data to the hashtable. returns 0 on success, -1 on error */ static inline int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, - hashdata_choose_cb choose, void *data) + hashdata_choose_cb choose, + void *data, struct hlist_node *data_node) { int index; struct hlist_head *head; - struct hlist_node *walk, *safe; - struct element_t *bucket; + struct hlist_node *node; spinlock_t *list_lock; /* spinlock to protect write access */ if (!hash) @@ -105,21 +95,17 @@ static inline int hash_add(struct hashtable_t *hash, list_lock = &hash->list_locks[index]; rcu_read_lock(); - hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { - if (compare(bucket->data, data)) - goto err_unlock; + __hlist_for_each_rcu(node, head) { + if (!compare(node, data)) + continue; + + goto err_unlock; } rcu_read_unlock(); /* no duplicate found in list, add new element */ - bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC); - if (!bucket) - goto err; - - bucket->data = data; - spin_lock_bh(list_lock); - hlist_add_head_rcu(&bucket->hlist, head); + hlist_add_head_rcu(data_node, head); spin_unlock_bh(list_lock); return 0; @@ -139,8 +125,7 @@ static inline void *hash_remove(struct hashtable_t *hash, hashdata_choose_cb choose, void *data) { size_t index; - struct hlist_node *walk; - struct element_t *bucket; + struct hlist_node *node; struct hlist_head *head; void *data_save = NULL; @@ -148,49 +133,17 @@ static inline void *hash_remove(struct hashtable_t *hash, 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_rcu(walk); - call_rcu(&bucket->rcu, bucket_free_rcu); - break; - } + hlist_for_each(node, head) { + if (!compare(node, data)) + continue; + + data_save = node; + hlist_del_rcu(node); + break; } spin_unlock_bh(&hash->list_locks[index]); return data_save; } -/** - * 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) -{ - int index; - struct hlist_head *head; - struct hlist_node *walk; - struct element_t *bucket; - void *bucket_data = NULL; - - if (!hash) - return NULL; - - index = choose(keydata , hash->size); - head = &hash->table[index]; - - hlist_for_each_entry(bucket, walk, head, hlist) { - if (compare(bucket->data, keydata)) { - bucket_data = bucket->data; - break; - } - } - - return bucket_data; -} - #endif /* _NET_BATMAN_ADV_HASH_H_ */ diff --git a/batman-adv/icmp_socket.c b/batman-adv/icmp_socket.c index 9f150bf..7159c81 100644 --- a/batman-adv/icmp_socket.c +++ b/batman-adv/icmp_socket.c @@ -219,14 +219,11 @@ static ssize_t bat_socket_write(struct file *file, const char __user *buff, goto dst_unreach; rcu_read_lock(); - orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, - compare_orig, choose_orig, - icmp_packet->dst)); + orig_node = orig_hash_find(bat_priv->orig_hash, icmp_packet->dst); if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) diff --git a/batman-adv/originator.c b/batman-adv/originator.c index bde9778..447781e 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -137,9 +137,8 @@ void orig_node_free_ref(struct kref *refcount) void originator_free(struct bat_priv *bat_priv) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk, *safe; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; spinlock_t *list_lock; /* spinlock to protect write access */ struct orig_node *orig_node; int i; @@ -156,11 +155,10 @@ void originator_free(struct bat_priv *bat_priv) 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; + hlist_for_each_entry_safe(orig_node, node, node_tmp, + head, hash_entry) { - hlist_del_rcu(walk); - call_rcu(&bucket->rcu, bucket_free_rcu); + hlist_del_rcu(node); kref_put(&orig_node->refcount, orig_node_free_ref); } spin_unlock_bh(list_lock); @@ -169,18 +167,6 @@ void originator_free(struct bat_priv *bat_priv) hash_destroy(hash); } -static void bucket_free_orig_rcu(struct rcu_head *rcu) -{ - struct element_t *bucket; - struct orig_node *orig_node; - - bucket = container_of(rcu, struct element_t, rcu); - orig_node = bucket->data; - - kref_put(&orig_node->refcount, orig_node_free_ref); - kfree(bucket); -} - /* this function finds or creates an originator entry for the given * address if it does not exits */ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) @@ -189,16 +175,9 @@ 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) { - kref_get(&orig_node->refcount); + orig_node = orig_hash_find(bat_priv->orig_hash, addr); + if (orig_node) return orig_node; - } bat_dbg(DBG_BATMAN, bat_priv, "Creating new originator: %pM\n", addr); @@ -240,8 +219,8 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) if (!orig_node->bcast_own_sum) goto free_bcast_own; - hash_added = hash_add(bat_priv->orig_hash, compare_orig, choose_orig, - orig_node); + hash_added = hash_add(bat_priv->orig_hash, compare_orig, + choose_orig, orig_node, &orig_node->hash_entry); if (hash_added < 0) goto free_bcast_own_sum; @@ -341,9 +320,8 @@ static bool purge_orig_node(struct bat_priv *bat_priv, static void _purge_orig(struct bat_priv *bat_priv) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk, *safe; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; spinlock_t *list_lock; /* spinlock to protect write access */ struct orig_node *orig_node; int i; @@ -357,14 +335,12 @@ static void _purge_orig(struct bat_priv *bat_priv) 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; - + hlist_for_each_entry_safe(orig_node, node, node_tmp, + head, hash_entry) { if (purge_orig_node(bat_priv, orig_node)) { if (orig_node->gw_flags) gw_node_delete(bat_priv, orig_node); - hlist_del_rcu(walk); - call_rcu(&bucket->rcu, bucket_free_orig_rcu); + hlist_del_rcu(node); continue; } @@ -402,9 +378,8 @@ 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, *node; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; struct neigh_node *neigh_node; int batman_count = 0; @@ -436,9 +411,7 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; - + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { if (!orig_node->router) continue; @@ -457,7 +430,7 @@ 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_rcu(neigh_node, node, + hlist_for_each_entry_rcu(neigh_node, node_tmp, &orig_node->neigh_list, list) { seq_printf(seq, " %pM (%3i)", neigh_node->addr, neigh_node->tq_avg); @@ -509,9 +482,8 @@ 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 hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; int i, ret; @@ -521,9 +493,7 @@ int orig_hash_add_if(struct batman_if *batman_if, int max_if_num) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; - + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { 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); @@ -597,9 +567,8 @@ 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_node *node; struct hlist_head *head; - struct element_t *bucket; struct batman_if *batman_if_tmp; struct orig_node *orig_node; int i, ret; @@ -610,9 +579,7 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; - + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { spin_lock_bh(&orig_node->ogm_cnt_lock); ret = orig_node_del_if(orig_node, max_if_num, batman_if->if_num); diff --git a/batman-adv/originator.h b/batman-adv/originator.h index 84d96e2..dc087fd 100644 --- a/batman-adv/originator.h +++ b/batman-adv/originator.h @@ -22,6 +22,8 @@ #ifndef _NET_BATMAN_ADV_ORIGINATOR_H_ #define _NET_BATMAN_ADV_ORIGINATOR_H_ +#include "hash.h" + 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); @@ -38,8 +40,10 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num); /* returns 1 if they are the same originator */ -static inline int compare_orig(void *data1, void *data2) +static inline int compare_orig(struct hlist_node *node, void *data2) { + void *data1 = container_of(node, struct orig_node, hash_entry); + return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); } @@ -64,4 +68,32 @@ static inline int choose_orig(void *data, int32_t size) return hash % size; } +static inline struct orig_node *orig_hash_find(struct hashtable_t *hash, + void *data) +{ + int index; + struct hlist_head *head; + struct hlist_node *node; + struct orig_node *orig_node, *orig_node_tmp = NULL; + + if (!hash) + return NULL; + + index = choose_orig(data, hash->size); + head = &hash->table[index]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { + if (!compare_eth(orig_node, data)) + continue; + + orig_node_tmp = orig_node; + kref_get(&orig_node_tmp->refcount); + break; + } + rcu_read_unlock(); + + return orig_node_tmp; +} + #endif /* _NET_BATMAN_ADV_ORIGINATOR_H_ */ diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 892b463..da882cd 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -39,9 +39,8 @@ void slide_own_bcast_window(struct batman_if *batman_if) { 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_node *node; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; unsigned long *word; int i; @@ -51,8 +50,7 @@ void slide_own_bcast_window(struct batman_if *batman_if) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { spin_lock_bh(&orig_node->ogm_cnt_lock); word_index = batman_if->if_num * NUM_WORDS; word = &(orig_node->bcast_own[word_index]); @@ -898,13 +896,11 @@ static int recv_my_icmp_packet(struct bat_priv *bat_priv, /* answer echo request (ping) */ /* get routing information */ rcu_read_lock(); - orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, - compare_orig, choose_orig, - icmp_packet->orig)); + orig_node = orig_hash_find(bat_priv->orig_hash, icmp_packet->orig); + if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) @@ -966,13 +962,11 @@ static int recv_icmp_ttl_exceeded(struct bat_priv *bat_priv, /* get routing information */ rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - icmp_packet->orig)); + orig_node = orig_hash_find(bat_priv->orig_hash, icmp_packet->orig); + if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) @@ -1066,13 +1060,11 @@ int recv_icmp_packet(struct sk_buff *skb, struct batman_if *recv_if) /* get routing information */ rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - icmp_packet->dst)); + orig_node = orig_hash_find(bat_priv->orig_hash, icmp_packet->dst); + if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) @@ -1155,11 +1147,12 @@ struct neigh_node *find_router(struct bat_priv *bat_priv, if (compare_eth(router_orig->primary_addr, router_orig->orig)) { primary_orig_node = router_orig; } else { - primary_orig_node = hash_find(bat_priv->orig_hash, compare_orig, - choose_orig, - router_orig->primary_addr); + primary_orig_node = orig_hash_find(bat_priv->orig_hash, + router_orig->primary_addr); if (!primary_orig_node) goto return_router; + + kref_put(&primary_orig_node->refcount, orig_node_free_ref); } /* with less than 2 candidates, we can't do any @@ -1302,14 +1295,11 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if, /* get routing information */ rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - unicast_packet->dest)); + orig_node = orig_hash_find(bat_priv->orig_hash, unicast_packet->dest); if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); rcu_read_unlock(); /* find_router() increases neigh_nodes refcount if found. */ @@ -1459,14 +1449,11 @@ int recv_bcast_packet(struct sk_buff *skb, struct batman_if *recv_if) goto out; rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - bcast_packet->orig)); + orig_node = orig_hash_find(bat_priv->orig_hash, bcast_packet->orig); if (!orig_node) goto rcu_unlock; - kref_get(&orig_node->refcount); rcu_read_unlock(); spin_lock_bh(&orig_node->bcast_seqno_lock); diff --git a/batman-adv/translation-table.c b/batman-adv/translation-table.c index b323c24..3a342e7 100644 --- a/batman-adv/translation-table.c +++ b/batman-adv/translation-table.c @@ -30,12 +30,83 @@ static void _hna_global_del_orig(struct bat_priv *bat_priv, struct hna_global_entry *hna_global_entry, char *message); +/* returns 1 if they are the same mac addr */ +static int compare_lhna(struct hlist_node *node, void *data2) +{ + void *data1 = container_of(node, struct hna_local_entry, hash_entry); + + return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); +} + +/* returns 1 if they are the same mac addr */ +static int compare_ghna(struct hlist_node *node, void *data2) +{ + void *data1 = container_of(node, struct hna_global_entry, hash_entry); + + return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); +} + static void hna_local_start_timer(struct bat_priv *bat_priv) { INIT_DELAYED_WORK(&bat_priv->hna_work, hna_local_purge); queue_delayed_work(bat_event_workqueue, &bat_priv->hna_work, 10 * HZ); } +static struct hna_local_entry *hna_local_hash_find(struct hashtable_t *hash, + void *data) +{ + int index; + struct hlist_head *head; + struct hlist_node *node; + struct hna_local_entry *hna_local_entry, *hna_local_entry_tmp = NULL; + + if (!hash) + return NULL; + + index = choose_orig(data, hash->size); + head = &hash->table[index]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(hna_local_entry, node, head, hash_entry) { + if (!compare_eth(hna_local_entry, data)) + continue; + + hna_local_entry_tmp = hna_local_entry; + break; + } + rcu_read_unlock(); + + return hna_local_entry_tmp; +} + +static struct hna_global_entry *hna_global_hash_find(struct hashtable_t *hash, + void *data) +{ + int index; + struct hlist_head *head; + struct hlist_node *node; + struct hna_global_entry *hna_global_entry; + struct hna_global_entry *hna_global_entry_tmp = NULL; + + if (!hash) + return NULL; + + index = choose_orig(data, hash->size); + head = &hash->table[index]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(hna_global_entry, node, head, hash_entry) { + if (!compare_eth(hna_global_entry, data)) + continue; + + hna_global_entry_tmp = hna_global_entry; + break; + } + rcu_read_unlock(); + + return hna_global_entry_tmp; +} + int hna_local_init(struct bat_priv *bat_priv) { if (bat_priv->hna_local_hash) @@ -60,12 +131,7 @@ 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(); + hna_local_entry = hna_local_hash_find(bat_priv->hna_local_hash, addr); spin_unlock_bh(&bat_priv->hna_lhash_lock); if (hna_local_entry) { @@ -108,8 +174,8 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) spin_lock_bh(&bat_priv->hna_lhash_lock); - hash_add(bat_priv->hna_local_hash, compare_orig, choose_orig, - hna_local_entry); + hash_add(bat_priv->hna_local_hash, compare_lhna, choose_orig, + hna_local_entry, &hna_local_entry->hash_entry); bat_priv->num_local_hna++; atomic_set(&bat_priv->hna_local_changed, 1); @@ -118,11 +184,7 @@ 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(); + hna_global_entry = hna_global_hash_find(bat_priv->hna_global_hash, addr); if (hna_global_entry) _hna_global_del_orig(bat_priv, hna_global_entry, @@ -136,28 +198,27 @@ int hna_local_fill_buffer(struct bat_priv *bat_priv, { struct hashtable_t *hash = bat_priv->hna_local_hash; struct hna_local_entry *hna_local_entry; - struct element_t *bucket; - int i; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - int count = 0; + int i, count = 0; spin_lock_bh(&bat_priv->hna_lhash_lock); 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(hna_local_entry, node, + head, hash_entry) { if (buff_len < (count + 1) * ETH_ALEN) break; - hna_local_entry = bucket->data; memcpy(buff + (count * ETH_ALEN), hna_local_entry->addr, ETH_ALEN); count++; } + rcu_read_unlock(); } /* if we did not get all new local hnas see you next time ;-) */ @@ -174,12 +235,11 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) 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; - int i; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; size_t buf_size, pos; char *buff; + int i; if (!bat_priv->primary_if) { return seq_printf(seq, "BATMAN mesh %s disabled - " @@ -198,8 +258,10 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each(walk, head) + rcu_read_lock(); + __hlist_for_each_rcu(node, head) buf_size += 21; + rcu_read_unlock(); } buff = kmalloc(buf_size, GFP_ATOMIC); @@ -207,18 +269,20 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) spin_unlock_bh(&bat_priv->hna_lhash_lock); return -ENOMEM; } + buff[0] = '\0'; pos = 0; for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each_entry(bucket, walk, head, hlist) { - hna_local_entry = bucket->data; - + rcu_read_lock(); + hlist_for_each_entry_rcu(hna_local_entry, node, + head, hash_entry) { pos += snprintf(buff + pos, 22, " * %pM\n", hna_local_entry->addr); } + rcu_read_unlock(); } spin_unlock_bh(&bat_priv->hna_lhash_lock); @@ -228,9 +292,10 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) return 0; } -static void _hna_local_del(void *data, void *arg) +static void _hna_local_del(struct hlist_node *node, void *arg) { struct bat_priv *bat_priv = (struct bat_priv *)arg; + void *data = container_of(node, struct hna_local_entry, hash_entry); kfree(data); bat_priv->num_local_hna--; @@ -244,9 +309,9 @@ static void hna_local_del(struct bat_priv *bat_priv, bat_dbg(DBG_ROUTES, bat_priv, "Deleting local hna entry (%pM): %s\n", hna_local_entry->addr, message); - hash_remove(bat_priv->hna_local_hash, compare_orig, choose_orig, + hash_remove(bat_priv->hna_local_hash, compare_lhna, choose_orig, hna_local_entry->addr); - _hna_local_del(hna_local_entry, bat_priv); + _hna_local_del(&hna_local_entry->hash_entry, bat_priv); } void hna_local_remove(struct bat_priv *bat_priv, @@ -256,11 +321,7 @@ 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(); + hna_local_entry = hna_local_hash_find(bat_priv->hna_local_hash, addr); if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, message); @@ -276,27 +337,29 @@ static void hna_local_purge(struct work_struct *work) 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; - int i; - struct hlist_node *walk, *safe; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; unsigned long timeout; + int i; spin_lock_bh(&bat_priv->hna_lhash_lock); for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { - hna_local_entry = bucket->data; + hlist_for_each_entry_safe(hna_local_entry, node, node_tmp, + head, hash_entry) { + if (hna_local_entry->never_purge) + continue; 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"); + if (time_before(jiffies, timeout)) + continue; + + hna_local_del(bat_priv, hna_local_entry, + "address timed out"); } } @@ -340,11 +403,9 @@ 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(); + hna_global_entry = + hna_global_hash_find(bat_priv->hna_global_hash, + hna_ptr); if (!hna_global_entry) { spin_unlock_bh(&bat_priv->hna_ghash_lock); @@ -364,8 +425,9 @@ void hna_global_add_orig(struct bat_priv *bat_priv, hna_global_entry->addr, orig_node->orig); spin_lock_bh(&bat_priv->hna_ghash_lock); - hash_add(bat_priv->hna_global_hash, compare_orig, - choose_orig, hna_global_entry); + hash_add(bat_priv->hna_global_hash, compare_ghna, + choose_orig, hna_global_entry, + &hna_global_entry->hash_entry); } @@ -376,11 +438,8 @@ 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(); + hna_local_entry = hna_local_hash_find(bat_priv->hna_local_hash, + hna_ptr); if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, @@ -410,12 +469,11 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset) 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; - int i; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; size_t buf_size, pos; char *buff; + int i; if (!bat_priv->primary_if) { return seq_printf(seq, "BATMAN mesh %s disabled - " @@ -433,8 +491,10 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset) for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each(walk, head) + rcu_read_lock(); + __hlist_for_each_rcu(node, head) buf_size += 43; + rcu_read_unlock(); } buff = kmalloc(buf_size, GFP_ATOMIC); @@ -448,14 +508,15 @@ int hna_global_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) { - hna_global_entry = bucket->data; - + rcu_read_lock(); + hlist_for_each_entry_rcu(hna_global_entry, node, + head, hash_entry) { pos += snprintf(buff + pos, 44, " * %pM via %pM\n", hna_global_entry->addr, hna_global_entry->orig_node->orig); } + rcu_read_unlock(); } spin_unlock_bh(&bat_priv->hna_ghash_lock); @@ -474,7 +535,7 @@ static void _hna_global_del_orig(struct bat_priv *bat_priv, hna_global_entry->addr, hna_global_entry->orig_node->orig, message); - hash_remove(bat_priv->hna_global_hash, compare_orig, choose_orig, + hash_remove(bat_priv->hna_global_hash, compare_ghna, choose_orig, hna_global_entry->addr); kfree(hna_global_entry); } @@ -493,11 +554,9 @@ 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(); + hna_global_entry = + hna_global_hash_find(bat_priv->hna_global_hash, + hna_ptr); if ((hna_global_entry) && (hna_global_entry->orig_node == orig_node)) @@ -514,8 +573,10 @@ void hna_global_del_orig(struct bat_priv *bat_priv, orig_node->hna_buff = NULL; } -static void hna_global_del(void *data, void *arg) +static void hna_global_del(struct hlist_node *node, void *arg) { + void *data = container_of(node, struct hna_global_entry, hash_entry); + kfree(data); } @@ -533,15 +594,12 @@ 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); + hna_global_entry = hna_global_hash_find(bat_priv->hna_global_hash, + addr); if (hna_global_entry) kref_get(&hna_global_entry->orig_node->refcount); - rcu_read_unlock(); spin_unlock_bh(&bat_priv->hna_ghash_lock); if (!hna_global_entry) diff --git a/batman-adv/types.h b/batman-adv/types.h index ee77d48..171b780 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -85,6 +85,7 @@ struct orig_node { struct list_head frag_list; spinlock_t neigh_list_lock; /* protects neighbor list */ struct kref refcount; + struct hlist_node hash_entry; struct bat_priv *bat_priv; unsigned long last_frag_packet; spinlock_t ogm_cnt_lock; /* protects: bcast_own, bcast_own_sum, @@ -193,11 +194,13 @@ struct hna_local_entry { uint8_t addr[ETH_ALEN]; unsigned long last_seen; char never_purge; + struct hlist_node hash_entry; }; struct hna_global_entry { uint8_t addr[ETH_ALEN]; struct orig_node *orig_node; + struct hlist_node hash_entry; }; /** @@ -247,6 +250,7 @@ struct vis_info { * from. we should not reply to them. */ struct list_head send_list; struct kref refcount; + struct hlist_node hash_entry; struct bat_priv *bat_priv; /* this packet might be part of the vis send queue. */ struct sk_buff *skb_packet; diff --git a/batman-adv/unicast.c b/batman-adv/unicast.c index ddd6852..c4616d2 100644 --- a/batman-adv/unicast.c +++ b/batman-adv/unicast.c @@ -184,15 +184,9 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, *new_skb = NULL; - rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - unicast_packet->orig)); + orig_node = orig_hash_find(bat_priv->orig_hash, unicast_packet->orig); if (!orig_node) - goto unlock; - - kref_get(&orig_node->refcount); - rcu_read_unlock(); + goto out; orig_node->last_frag_packet = jiffies; @@ -219,8 +213,6 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, goto out; -unlock: - rcu_read_unlock(); out: if (orig_node) kref_put(&orig_node->refcount, orig_node_free_ref); diff --git a/batman-adv/vis.c b/batman-adv/vis.c index 6435886..53aa836 100644 --- a/batman-adv/vis.c +++ b/batman-adv/vis.c @@ -68,11 +68,12 @@ static void free_info(struct kref *ref) } /* Compare two vis packets, used by the hashing algorithm */ -static int vis_info_cmp(void *data1, void *data2) +static int vis_info_cmp(struct hlist_node *node, void *data2) { struct vis_info *d1, *d2; struct vis_packet *p1, *p2; - d1 = data1; + + d1 = container_of(node, struct vis_info, hash_entry); d2 = data2; p1 = (struct vis_packet *)d1->skb_packet->data; p2 = (struct vis_packet *)d2->skb_packet->data; @@ -104,6 +105,33 @@ static int vis_info_choose(void *data, int size) return hash % size; } +static struct vis_info *vis_hash_find(struct hashtable_t *hash, + void *data) +{ + int index; + struct hlist_head *head; + struct hlist_node *node; + struct vis_info *vis_info, *vis_info_tmp = NULL; + + if (!hash) + return NULL; + + index = vis_info_choose(data, hash->size); + head = &hash->table[index]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(vis_info, node, head, hash_entry) { + if (!vis_info_cmp(node, data)) + continue; + + vis_info_tmp = vis_info; + break; + } + rcu_read_unlock(); + + return vis_info_tmp; +} + /* insert interface to the list of interfaces of one originator, if it * does not already exist in the list */ static void vis_data_insert_interface(const uint8_t *interface, @@ -175,9 +203,8 @@ 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) { - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; struct vis_info *info; struct vis_packet *packet; struct vis_info_entry *entries; @@ -203,8 +230,8 @@ int vis_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) { - info = bucket->data; + rcu_read_lock(); + hlist_for_each_entry_rcu(info, node, head, hash_entry) { packet = (struct vis_packet *)info->skb_packet->data; entries = (struct vis_info_entry *) ((char *)packet + sizeof(struct vis_packet)); @@ -236,6 +263,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) kfree(entry); } } + rcu_read_unlock(); } buff = kmalloc(buf_size, GFP_ATOMIC); @@ -249,8 +277,8 @@ int vis_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) { - info = bucket->data; + rcu_read_lock(); + hlist_for_each_entry_rcu(info, node, head, hash_entry) { packet = (struct vis_packet *)info->skb_packet->data; entries = (struct vis_info_entry *) ((char *)packet + sizeof(struct vis_packet)); @@ -291,6 +319,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) kfree(entry); } } + rcu_read_unlock(); } spin_unlock_bh(&bat_priv->vis_hash_lock); @@ -381,10 +410,7 @@ 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(); + old_info = vis_hash_find(bat_priv->vis_hash, &search_elem); kfree_skb(search_elem.skb_packet); if (old_info) { @@ -444,7 +470,7 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, /* try to add it */ hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, - info); + info, &info->hash_entry); if (hash_added < 0) { /* did not work (for some reason) */ kref_put(&info->refcount, free_info); @@ -531,9 +557,8 @@ static int find_best_vis_server(struct bat_priv *bat_priv, struct vis_info *info) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; int best_tq = -1, i; @@ -544,11 +569,10 @@ static int find_best_vis_server(struct bat_priv *bat_priv, head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { if ((orig_node) && (orig_node->router) && - (orig_node->flags & VIS_SERVER) && - (orig_node->router->tq_avg > best_tq)) { + (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); @@ -577,9 +601,8 @@ static bool vis_packet_full(struct vis_info *info) static int generate_vis_packet(struct bat_priv *bat_priv) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *node; 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; @@ -608,8 +631,7 @@ static int generate_vis_packet(struct bat_priv *bat_priv) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { neigh_node = orig_node->router; if (!neigh_node) @@ -646,8 +668,7 @@ 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) { - hna_local_entry = bucket->data; + hlist_for_each_entry(hna_local_entry, node, head, hash_entry) { entry = (struct vis_info_entry *) skb_put(info->skb_packet, sizeof(*entry)); @@ -677,25 +698,22 @@ static void purge_vis_packets(struct bat_priv *bat_priv) { int i; struct hashtable_t *hash = bat_priv->vis_hash; - struct hlist_node *walk, *safe; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; struct vis_info *info; for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { - info = bucket->data; - + hlist_for_each_entry_safe(info, node, node_tmp, + head, hash_entry) { /* 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); + hlist_del(node); send_list_del(info); kref_put(&info->refcount, free_info); } @@ -707,9 +725,8 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, struct vis_info *info) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; struct sk_buff *skb; @@ -725,9 +742,7 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; - + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { /* if it's a vis server and reachable, send it. */ if ((!orig_node) || (!orig_node->router)) continue; @@ -763,14 +778,11 @@ static void unicast_vis_packet(struct bat_priv *bat_priv, 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)); + orig_node = orig_hash_find(bat_priv->orig_hash, packet->target_orig); if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) @@ -909,7 +921,8 @@ int vis_init(struct bat_priv *bat_priv) INIT_LIST_HEAD(&bat_priv->vis_send_list); hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, - bat_priv->my_vis_info); + bat_priv->my_vis_info, + &bat_priv->my_vis_info->hash_entry); if (hash_added < 0) { pr_err("Can't add own vis packet into hash\n"); /* not in hash, need to remove it manually. */ @@ -931,10 +944,11 @@ err: } /* Decrease the reference count on a hash item info */ -static void free_info_ref(void *data, void *arg) +static void free_info_ref(struct hlist_node *node, void *arg) { - struct vis_info *info = data; + struct vis_info *info; + info = container_of(node, struct vis_info, hash_entry); send_list_del(info); kref_put(&info->refcount, free_info); } -- 1.7.2.3 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [B.A.T.M.A.N.] [PATCH 2/2] batman-adv: remove extra layer between hash and hash element - hash bucket 2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 2/2] batman-adv: remove extra layer between hash and hash element - hash bucket Marek Lindner @ 2011-02-10 13:03 ` Linus Lüssing 2011-02-10 13:36 ` Marek Lindner 2011-02-13 21:36 ` [B.A.T.M.A.N.] [PATCHv2 2/4] " Marek Lindner 1 sibling, 1 reply; 9+ messages in thread From: Linus Lüssing @ 2011-02-10 13:03 UTC (permalink / raw) To: The list for a Better Approach To Mobile Ad-hoc Networking > diff --git a/batman-adv/compat.h b/batman-adv/compat.h > index a76d0be..29a3203 100644 > --- a/batman-adv/compat.h > +++ b/batman-adv/compat.h > @@ -270,4 +270,12 @@ int bat_seq_printf(struct seq_file *m, const char *f, ...); > > #endif /* < KERNEL_VERSION(2, 6, 33) */ > > +#define hlist_first_rcu(head) (*((struct hlist_node **)(&(head)->first))) > +#define hlist_next_rcu(node) (*((struct hlist_node **)(&(node)->next))) > + > +#define __hlist_for_each_rcu(pos, head) \ > + for (pos = rcu_dereference(hlist_first_rcu(head)); \ > + pos && ({ prefetch(pos->next); 1; }); \ > + pos = rcu_dereference(hlist_next_rcu(pos))) > + > #endif /* _NET_BATMAN_ADV_COMPAT_H_ */ Isn't there a #define with < KERNEL_VERSION(2, 6, 37) missing? (Haven't checked much else about this patch yet) Cheers, Linus ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [B.A.T.M.A.N.] [PATCH 2/2] batman-adv: remove extra layer between hash and hash element - hash bucket 2011-02-10 13:03 ` Linus Lüssing @ 2011-02-10 13:36 ` Marek Lindner 0 siblings, 0 replies; 9+ messages in thread From: Marek Lindner @ 2011-02-10 13:36 UTC (permalink / raw) To: The list for a Better Approach To Mobile Ad-hoc Networking On Thursday 10 February 2011 14:03:03 Linus Lüssing wrote: > Isn't there a #define with < KERNEL_VERSION(2, 6, 37) missing? > (Haven't checked much else about this patch yet) Why would there be a need for .37 (this functionality came with .34) ? Nevertheless, you are right - it is missing here. Regards, Marek ^ permalink raw reply [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCHv2 2/4] batman-adv: remove extra layer between hash and hash element - hash bucket 2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 2/2] batman-adv: remove extra layer between hash and hash element - hash bucket Marek Lindner 2011-02-10 13:03 ` Linus Lüssing @ 2011-02-13 21:36 ` Marek Lindner 1 sibling, 0 replies; 9+ messages in thread From: Marek Lindner @ 2011-02-13 21:36 UTC (permalink / raw) To: b.a.t.m.a.n; +Cc: Marek Lindner Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> --- Rebase on trunk, checking kernel version in compat.h and minor hash_find() API change. batman-adv/compat.h | 12 +++ batman-adv/hash.c | 8 -- batman-adv/hash.h | 95 +++++-------------- batman-adv/icmp_socket.c | 5 +- batman-adv/originator.c | 71 ++++---------- batman-adv/originator.h | 35 +++++++- batman-adv/routing.c | 41 +++----- batman-adv/translation-table.c | 204 +++++++++++++++++++++++++--------------- batman-adv/types.h | 4 + batman-adv/unicast.c | 12 +-- batman-adv/vis.c | 103 ++++++++++++--------- 11 files changed, 298 insertions(+), 292 deletions(-) diff --git a/batman-adv/compat.h b/batman-adv/compat.h index 4e89049..0c5ad82 100644 --- a/batman-adv/compat.h +++ b/batman-adv/compat.h @@ -270,6 +270,18 @@ int bat_seq_printf(struct seq_file *m, const char *f, ...); #endif /* < KERNEL_VERSION(2, 6, 33) */ +#if LINUX_VERSION_CODE < KERNEL_VERSION(2, 6, 34) + +#define hlist_first_rcu(head) (*((struct hlist_node **)(&(head)->first))) +#define hlist_next_rcu(node) (*((struct hlist_node **)(&(node)->next))) + +#define __hlist_for_each_rcu(pos, head) \ + for (pos = rcu_dereference(hlist_first_rcu(head)); \ + pos && ({ prefetch(pos->next); 1; }); \ + pos = rcu_dereference(hlist_next_rcu(pos))) + +#endif /* < KERNEL_VERSION(2, 6, 34) */ + #if LINUX_VERSION_CODE < KERNEL_VERSION(2, 6, 36) #define __rcu diff --git a/batman-adv/hash.c b/batman-adv/hash.c index 0265366..c5213d8 100644 --- a/batman-adv/hash.c +++ b/batman-adv/hash.c @@ -68,11 +68,3 @@ 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 3c48c6b..434822b 100644 --- a/batman-adv/hash.h +++ b/batman-adv/hash.h @@ -28,19 +28,13 @@ * compare 2 element datas for their keys, * return 0 if same and not 0 if not * same */ -typedef int (*hashdata_compare_cb)(void *, void *); +typedef int (*hashdata_compare_cb)(struct hlist_node *, void *); /* the hashfunction, should return an index * based on the key in the data of the first * argument and the size the second */ typedef int (*hashdata_choose_cb)(void *, int); -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; -}; +typedef void (*hashdata_free_cb)(struct hlist_node *, void *); struct hashtable_t { struct hlist_head *table; /* the hashtable itself with the buckets */ @@ -54,8 +48,6 @@ struct hashtable_t *hash_new(int size); /* 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. */ @@ -63,8 +55,7 @@ static inline void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb, void *arg) { struct hlist_head *head; - struct hlist_node *walk, *safe; - struct element_t *bucket; + struct hlist_node *node, *node_tmp; spinlock_t *list_lock; /* spinlock to protect write access */ int i; @@ -73,12 +64,11 @@ static inline void hash_delete(struct hashtable_t *hash, list_lock = &hash->list_locks[i]; spin_lock_bh(list_lock); - hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { - if (free_cb) - free_cb(bucket->data, arg); + hlist_for_each_safe(node, node_tmp, head) { + hlist_del_rcu(node); - hlist_del_rcu(walk); - call_rcu(&bucket->rcu, bucket_free_rcu); + if (free_cb) + free_cb(node, arg); } spin_unlock_bh(list_lock); } @@ -89,12 +79,12 @@ static inline void hash_delete(struct hashtable_t *hash, /* adds data to the hashtable. returns 0 on success, -1 on error */ static inline int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, - hashdata_choose_cb choose, void *data) + hashdata_choose_cb choose, + void *data, struct hlist_node *data_node) { int index; struct hlist_head *head; - struct hlist_node *walk, *safe; - struct element_t *bucket; + struct hlist_node *node; spinlock_t *list_lock; /* spinlock to protect write access */ if (!hash) @@ -105,21 +95,17 @@ static inline int hash_add(struct hashtable_t *hash, list_lock = &hash->list_locks[index]; rcu_read_lock(); - hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { - if (compare(bucket->data, data)) - goto err_unlock; + __hlist_for_each_rcu(node, head) { + if (!compare(node, data)) + continue; + + goto err_unlock; } rcu_read_unlock(); /* no duplicate found in list, add new element */ - bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC); - if (!bucket) - goto err; - - bucket->data = data; - spin_lock_bh(list_lock); - hlist_add_head_rcu(&bucket->hlist, head); + hlist_add_head_rcu(data_node, head); spin_unlock_bh(list_lock); return 0; @@ -139,8 +125,7 @@ static inline void *hash_remove(struct hashtable_t *hash, hashdata_choose_cb choose, void *data) { size_t index; - struct hlist_node *walk; - struct element_t *bucket; + struct hlist_node *node; struct hlist_head *head; void *data_save = NULL; @@ -148,49 +133,17 @@ static inline void *hash_remove(struct hashtable_t *hash, 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_rcu(walk); - call_rcu(&bucket->rcu, bucket_free_rcu); - break; - } + hlist_for_each(node, head) { + if (!compare(node, data)) + continue; + + data_save = node; + hlist_del_rcu(node); + break; } spin_unlock_bh(&hash->list_locks[index]); return data_save; } -/** - * 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) -{ - int index; - struct hlist_head *head; - struct hlist_node *walk; - struct element_t *bucket; - void *bucket_data = NULL; - - if (!hash) - return NULL; - - index = choose(keydata , hash->size); - head = &hash->table[index]; - - hlist_for_each_entry(bucket, walk, head, hlist) { - if (compare(bucket->data, keydata)) { - bucket_data = bucket->data; - break; - } - } - - return bucket_data; -} - #endif /* _NET_BATMAN_ADV_HASH_H_ */ diff --git a/batman-adv/icmp_socket.c b/batman-adv/icmp_socket.c index 9f150bf..17792f3 100644 --- a/batman-adv/icmp_socket.c +++ b/batman-adv/icmp_socket.c @@ -219,14 +219,11 @@ static ssize_t bat_socket_write(struct file *file, const char __user *buff, goto dst_unreach; rcu_read_lock(); - orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, - compare_orig, choose_orig, - icmp_packet->dst)); + orig_node = orig_hash_find(bat_priv, icmp_packet->dst); if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) diff --git a/batman-adv/originator.c b/batman-adv/originator.c index bde9778..c9ba013 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -137,9 +137,8 @@ void orig_node_free_ref(struct kref *refcount) void originator_free(struct bat_priv *bat_priv) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk, *safe; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; spinlock_t *list_lock; /* spinlock to protect write access */ struct orig_node *orig_node; int i; @@ -156,11 +155,10 @@ void originator_free(struct bat_priv *bat_priv) 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; + hlist_for_each_entry_safe(orig_node, node, node_tmp, + head, hash_entry) { - hlist_del_rcu(walk); - call_rcu(&bucket->rcu, bucket_free_rcu); + hlist_del_rcu(node); kref_put(&orig_node->refcount, orig_node_free_ref); } spin_unlock_bh(list_lock); @@ -169,18 +167,6 @@ void originator_free(struct bat_priv *bat_priv) hash_destroy(hash); } -static void bucket_free_orig_rcu(struct rcu_head *rcu) -{ - struct element_t *bucket; - struct orig_node *orig_node; - - bucket = container_of(rcu, struct element_t, rcu); - orig_node = bucket->data; - - kref_put(&orig_node->refcount, orig_node_free_ref); - kfree(bucket); -} - /* this function finds or creates an originator entry for the given * address if it does not exits */ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) @@ -189,16 +175,9 @@ 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) { - kref_get(&orig_node->refcount); + orig_node = orig_hash_find(bat_priv, addr); + if (orig_node) return orig_node; - } bat_dbg(DBG_BATMAN, bat_priv, "Creating new originator: %pM\n", addr); @@ -240,8 +219,8 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) if (!orig_node->bcast_own_sum) goto free_bcast_own; - hash_added = hash_add(bat_priv->orig_hash, compare_orig, choose_orig, - orig_node); + hash_added = hash_add(bat_priv->orig_hash, compare_orig, + choose_orig, orig_node, &orig_node->hash_entry); if (hash_added < 0) goto free_bcast_own_sum; @@ -341,9 +320,8 @@ static bool purge_orig_node(struct bat_priv *bat_priv, static void _purge_orig(struct bat_priv *bat_priv) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk, *safe; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; spinlock_t *list_lock; /* spinlock to protect write access */ struct orig_node *orig_node; int i; @@ -357,14 +335,12 @@ static void _purge_orig(struct bat_priv *bat_priv) 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; - + hlist_for_each_entry_safe(orig_node, node, node_tmp, + head, hash_entry) { if (purge_orig_node(bat_priv, orig_node)) { if (orig_node->gw_flags) gw_node_delete(bat_priv, orig_node); - hlist_del_rcu(walk); - call_rcu(&bucket->rcu, bucket_free_orig_rcu); + hlist_del_rcu(node); continue; } @@ -402,9 +378,8 @@ 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, *node; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; struct neigh_node *neigh_node; int batman_count = 0; @@ -436,9 +411,7 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; - + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { if (!orig_node->router) continue; @@ -457,7 +430,7 @@ 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_rcu(neigh_node, node, + hlist_for_each_entry_rcu(neigh_node, node_tmp, &orig_node->neigh_list, list) { seq_printf(seq, " %pM (%3i)", neigh_node->addr, neigh_node->tq_avg); @@ -509,9 +482,8 @@ 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 hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; int i, ret; @@ -521,9 +493,7 @@ int orig_hash_add_if(struct batman_if *batman_if, int max_if_num) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; - + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { 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); @@ -597,9 +567,8 @@ 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_node *node; struct hlist_head *head; - struct element_t *bucket; struct batman_if *batman_if_tmp; struct orig_node *orig_node; int i, ret; @@ -610,9 +579,7 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; - + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { spin_lock_bh(&orig_node->ogm_cnt_lock); ret = orig_node_del_if(orig_node, max_if_num, batman_if->if_num); diff --git a/batman-adv/originator.h b/batman-adv/originator.h index 84d96e2..b4b9a09 100644 --- a/batman-adv/originator.h +++ b/batman-adv/originator.h @@ -22,6 +22,8 @@ #ifndef _NET_BATMAN_ADV_ORIGINATOR_H_ #define _NET_BATMAN_ADV_ORIGINATOR_H_ +#include "hash.h" + 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); @@ -38,8 +40,10 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num); /* returns 1 if they are the same originator */ -static inline int compare_orig(void *data1, void *data2) +static inline int compare_orig(struct hlist_node *node, void *data2) { + void *data1 = container_of(node, struct orig_node, hash_entry); + return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); } @@ -64,4 +68,33 @@ static inline int choose_orig(void *data, int32_t size) return hash % size; } +static inline struct orig_node *orig_hash_find(struct bat_priv *bat_priv, + void *data) +{ + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_head *head; + struct hlist_node *node; + struct orig_node *orig_node, *orig_node_tmp = NULL; + int index; + + if (!hash) + return NULL; + + index = choose_orig(data, hash->size); + head = &hash->table[index]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { + if (!compare_eth(orig_node, data)) + continue; + + orig_node_tmp = orig_node; + kref_get(&orig_node_tmp->refcount); + break; + } + rcu_read_unlock(); + + return orig_node_tmp; +} + #endif /* _NET_BATMAN_ADV_ORIGINATOR_H_ */ diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 892b463..d381cbc 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -39,9 +39,8 @@ void slide_own_bcast_window(struct batman_if *batman_if) { 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_node *node; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; unsigned long *word; int i; @@ -51,8 +50,7 @@ void slide_own_bcast_window(struct batman_if *batman_if) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { spin_lock_bh(&orig_node->ogm_cnt_lock); word_index = batman_if->if_num * NUM_WORDS; word = &(orig_node->bcast_own[word_index]); @@ -898,13 +896,11 @@ static int recv_my_icmp_packet(struct bat_priv *bat_priv, /* answer echo request (ping) */ /* get routing information */ rcu_read_lock(); - orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, - compare_orig, choose_orig, - icmp_packet->orig)); + orig_node = orig_hash_find(bat_priv, icmp_packet->orig); + if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) @@ -966,13 +962,11 @@ static int recv_icmp_ttl_exceeded(struct bat_priv *bat_priv, /* get routing information */ rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - icmp_packet->orig)); + orig_node = orig_hash_find(bat_priv, icmp_packet->orig); + if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) @@ -1066,13 +1060,11 @@ int recv_icmp_packet(struct sk_buff *skb, struct batman_if *recv_if) /* get routing information */ rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - icmp_packet->dst)); + orig_node = orig_hash_find(bat_priv, icmp_packet->dst); + if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) @@ -1155,11 +1147,12 @@ struct neigh_node *find_router(struct bat_priv *bat_priv, if (compare_eth(router_orig->primary_addr, router_orig->orig)) { primary_orig_node = router_orig; } else { - primary_orig_node = hash_find(bat_priv->orig_hash, compare_orig, - choose_orig, - router_orig->primary_addr); + primary_orig_node = orig_hash_find(bat_priv, + router_orig->primary_addr); if (!primary_orig_node) goto return_router; + + kref_put(&primary_orig_node->refcount, orig_node_free_ref); } /* with less than 2 candidates, we can't do any @@ -1302,14 +1295,11 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if, /* get routing information */ rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - unicast_packet->dest)); + orig_node = orig_hash_find(bat_priv, unicast_packet->dest); if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); rcu_read_unlock(); /* find_router() increases neigh_nodes refcount if found. */ @@ -1459,14 +1449,11 @@ int recv_bcast_packet(struct sk_buff *skb, struct batman_if *recv_if) goto out; rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - bcast_packet->orig)); + orig_node = orig_hash_find(bat_priv, bcast_packet->orig); if (!orig_node) goto rcu_unlock; - kref_get(&orig_node->refcount); rcu_read_unlock(); spin_lock_bh(&orig_node->bcast_seqno_lock); diff --git a/batman-adv/translation-table.c b/batman-adv/translation-table.c index b323c24..cd8a583 100644 --- a/batman-adv/translation-table.c +++ b/batman-adv/translation-table.c @@ -30,12 +30,85 @@ static void _hna_global_del_orig(struct bat_priv *bat_priv, struct hna_global_entry *hna_global_entry, char *message); +/* returns 1 if they are the same mac addr */ +static int compare_lhna(struct hlist_node *node, void *data2) +{ + void *data1 = container_of(node, struct hna_local_entry, hash_entry); + + return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); +} + +/* returns 1 if they are the same mac addr */ +static int compare_ghna(struct hlist_node *node, void *data2) +{ + void *data1 = container_of(node, struct hna_global_entry, hash_entry); + + return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); +} + static void hna_local_start_timer(struct bat_priv *bat_priv) { INIT_DELAYED_WORK(&bat_priv->hna_work, hna_local_purge); queue_delayed_work(bat_event_workqueue, &bat_priv->hna_work, 10 * HZ); } +static struct hna_local_entry *hna_local_hash_find(struct bat_priv *bat_priv, + void *data) +{ + struct hashtable_t *hash = bat_priv->hna_local_hash; + struct hlist_head *head; + struct hlist_node *node; + struct hna_local_entry *hna_local_entry, *hna_local_entry_tmp = NULL; + int index; + + if (!hash) + return NULL; + + index = choose_orig(data, hash->size); + head = &hash->table[index]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(hna_local_entry, node, head, hash_entry) { + if (!compare_eth(hna_local_entry, data)) + continue; + + hna_local_entry_tmp = hna_local_entry; + break; + } + rcu_read_unlock(); + + return hna_local_entry_tmp; +} + +static struct hna_global_entry *hna_global_hash_find(struct bat_priv *bat_priv, + void *data) +{ + struct hashtable_t *hash = bat_priv->hna_global_hash; + struct hlist_head *head; + struct hlist_node *node; + struct hna_global_entry *hna_global_entry; + struct hna_global_entry *hna_global_entry_tmp = NULL; + int index; + + if (!hash) + return NULL; + + index = choose_orig(data, hash->size); + head = &hash->table[index]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(hna_global_entry, node, head, hash_entry) { + if (!compare_eth(hna_global_entry, data)) + continue; + + hna_global_entry_tmp = hna_global_entry; + break; + } + rcu_read_unlock(); + + return hna_global_entry_tmp; +} + int hna_local_init(struct bat_priv *bat_priv) { if (bat_priv->hna_local_hash) @@ -60,12 +133,7 @@ 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(); + hna_local_entry = hna_local_hash_find(bat_priv, addr); spin_unlock_bh(&bat_priv->hna_lhash_lock); if (hna_local_entry) { @@ -108,8 +176,8 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) spin_lock_bh(&bat_priv->hna_lhash_lock); - hash_add(bat_priv->hna_local_hash, compare_orig, choose_orig, - hna_local_entry); + hash_add(bat_priv->hna_local_hash, compare_lhna, choose_orig, + hna_local_entry, &hna_local_entry->hash_entry); bat_priv->num_local_hna++; atomic_set(&bat_priv->hna_local_changed, 1); @@ -118,11 +186,7 @@ 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(); + hna_global_entry = hna_global_hash_find(bat_priv, addr); if (hna_global_entry) _hna_global_del_orig(bat_priv, hna_global_entry, @@ -136,28 +200,27 @@ int hna_local_fill_buffer(struct bat_priv *bat_priv, { struct hashtable_t *hash = bat_priv->hna_local_hash; struct hna_local_entry *hna_local_entry; - struct element_t *bucket; - int i; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - int count = 0; + int i, count = 0; spin_lock_bh(&bat_priv->hna_lhash_lock); 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(hna_local_entry, node, + head, hash_entry) { if (buff_len < (count + 1) * ETH_ALEN) break; - hna_local_entry = bucket->data; memcpy(buff + (count * ETH_ALEN), hna_local_entry->addr, ETH_ALEN); count++; } + rcu_read_unlock(); } /* if we did not get all new local hnas see you next time ;-) */ @@ -174,12 +237,11 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) 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; - int i; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; size_t buf_size, pos; char *buff; + int i; if (!bat_priv->primary_if) { return seq_printf(seq, "BATMAN mesh %s disabled - " @@ -198,8 +260,10 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each(walk, head) + rcu_read_lock(); + __hlist_for_each_rcu(node, head) buf_size += 21; + rcu_read_unlock(); } buff = kmalloc(buf_size, GFP_ATOMIC); @@ -207,18 +271,20 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) spin_unlock_bh(&bat_priv->hna_lhash_lock); return -ENOMEM; } + buff[0] = '\0'; pos = 0; for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each_entry(bucket, walk, head, hlist) { - hna_local_entry = bucket->data; - + rcu_read_lock(); + hlist_for_each_entry_rcu(hna_local_entry, node, + head, hash_entry) { pos += snprintf(buff + pos, 22, " * %pM\n", hna_local_entry->addr); } + rcu_read_unlock(); } spin_unlock_bh(&bat_priv->hna_lhash_lock); @@ -228,9 +294,10 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) return 0; } -static void _hna_local_del(void *data, void *arg) +static void _hna_local_del(struct hlist_node *node, void *arg) { struct bat_priv *bat_priv = (struct bat_priv *)arg; + void *data = container_of(node, struct hna_local_entry, hash_entry); kfree(data); bat_priv->num_local_hna--; @@ -244,9 +311,9 @@ static void hna_local_del(struct bat_priv *bat_priv, bat_dbg(DBG_ROUTES, bat_priv, "Deleting local hna entry (%pM): %s\n", hna_local_entry->addr, message); - hash_remove(bat_priv->hna_local_hash, compare_orig, choose_orig, + hash_remove(bat_priv->hna_local_hash, compare_lhna, choose_orig, hna_local_entry->addr); - _hna_local_del(hna_local_entry, bat_priv); + _hna_local_del(&hna_local_entry->hash_entry, bat_priv); } void hna_local_remove(struct bat_priv *bat_priv, @@ -256,11 +323,7 @@ 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(); + hna_local_entry = hna_local_hash_find(bat_priv, addr); if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, message); @@ -276,27 +339,29 @@ static void hna_local_purge(struct work_struct *work) 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; - int i; - struct hlist_node *walk, *safe; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; unsigned long timeout; + int i; spin_lock_bh(&bat_priv->hna_lhash_lock); for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { - hna_local_entry = bucket->data; + hlist_for_each_entry_safe(hna_local_entry, node, node_tmp, + head, hash_entry) { + if (hna_local_entry->never_purge) + continue; 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"); + if (time_before(jiffies, timeout)) + continue; + + hna_local_del(bat_priv, hna_local_entry, + "address timed out"); } } @@ -340,11 +405,7 @@ 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(); + hna_global_entry = hna_global_hash_find(bat_priv, hna_ptr); if (!hna_global_entry) { spin_unlock_bh(&bat_priv->hna_ghash_lock); @@ -364,8 +425,9 @@ void hna_global_add_orig(struct bat_priv *bat_priv, hna_global_entry->addr, orig_node->orig); spin_lock_bh(&bat_priv->hna_ghash_lock); - hash_add(bat_priv->hna_global_hash, compare_orig, - choose_orig, hna_global_entry); + hash_add(bat_priv->hna_global_hash, compare_ghna, + choose_orig, hna_global_entry, + &hna_global_entry->hash_entry); } @@ -376,11 +438,7 @@ 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(); + hna_local_entry = hna_local_hash_find(bat_priv, hna_ptr); if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, @@ -410,12 +468,11 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset) 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; - int i; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; size_t buf_size, pos; char *buff; + int i; if (!bat_priv->primary_if) { return seq_printf(seq, "BATMAN mesh %s disabled - " @@ -433,8 +490,10 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset) for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each(walk, head) + rcu_read_lock(); + __hlist_for_each_rcu(node, head) buf_size += 43; + rcu_read_unlock(); } buff = kmalloc(buf_size, GFP_ATOMIC); @@ -448,14 +507,15 @@ int hna_global_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) { - hna_global_entry = bucket->data; - + rcu_read_lock(); + hlist_for_each_entry_rcu(hna_global_entry, node, + head, hash_entry) { pos += snprintf(buff + pos, 44, " * %pM via %pM\n", hna_global_entry->addr, hna_global_entry->orig_node->orig); } + rcu_read_unlock(); } spin_unlock_bh(&bat_priv->hna_ghash_lock); @@ -474,7 +534,7 @@ static void _hna_global_del_orig(struct bat_priv *bat_priv, hna_global_entry->addr, hna_global_entry->orig_node->orig, message); - hash_remove(bat_priv->hna_global_hash, compare_orig, choose_orig, + hash_remove(bat_priv->hna_global_hash, compare_ghna, choose_orig, hna_global_entry->addr); kfree(hna_global_entry); } @@ -493,11 +553,7 @@ 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(); + hna_global_entry = hna_global_hash_find(bat_priv, hna_ptr); if ((hna_global_entry) && (hna_global_entry->orig_node == orig_node)) @@ -514,8 +570,10 @@ void hna_global_del_orig(struct bat_priv *bat_priv, orig_node->hna_buff = NULL; } -static void hna_global_del(void *data, void *arg) +static void hna_global_del(struct hlist_node *node, void *arg) { + void *data = container_of(node, struct hna_global_entry, hash_entry); + kfree(data); } @@ -533,15 +591,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); + hna_global_entry = hna_global_hash_find(bat_priv, addr); if (hna_global_entry) kref_get(&hna_global_entry->orig_node->refcount); - rcu_read_unlock(); spin_unlock_bh(&bat_priv->hna_ghash_lock); if (!hna_global_entry) diff --git a/batman-adv/types.h b/batman-adv/types.h index b6acb12..cc10843 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -85,6 +85,7 @@ struct orig_node { struct list_head frag_list; spinlock_t neigh_list_lock; /* protects neighbor list */ struct kref refcount; + struct hlist_node hash_entry; struct bat_priv *bat_priv; unsigned long last_frag_packet; spinlock_t ogm_cnt_lock; /* protects: bcast_own, bcast_own_sum, @@ -193,11 +194,13 @@ struct hna_local_entry { uint8_t addr[ETH_ALEN]; unsigned long last_seen; char never_purge; + struct hlist_node hash_entry; }; struct hna_global_entry { uint8_t addr[ETH_ALEN]; struct orig_node *orig_node; + struct hlist_node hash_entry; }; /** @@ -247,6 +250,7 @@ struct vis_info { * from. we should not reply to them. */ struct list_head send_list; struct kref refcount; + struct hlist_node hash_entry; struct bat_priv *bat_priv; /* this packet might be part of the vis send queue. */ struct sk_buff *skb_packet; diff --git a/batman-adv/unicast.c b/batman-adv/unicast.c index a7aacad..af81008 100644 --- a/batman-adv/unicast.c +++ b/batman-adv/unicast.c @@ -184,15 +184,9 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, *new_skb = NULL; - rcu_read_lock(); - orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, choose_orig, - unicast_packet->orig)); + orig_node = orig_hash_find(bat_priv, unicast_packet->orig); if (!orig_node) - goto unlock; - - kref_get(&orig_node->refcount); - rcu_read_unlock(); + goto out; orig_node->last_frag_packet = jiffies; @@ -219,8 +213,6 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, goto out; -unlock: - rcu_read_unlock(); out: if (orig_node) kref_put(&orig_node->refcount, orig_node_free_ref); diff --git a/batman-adv/vis.c b/batman-adv/vis.c index 6435886..2e8fc4d 100644 --- a/batman-adv/vis.c +++ b/batman-adv/vis.c @@ -68,11 +68,12 @@ static void free_info(struct kref *ref) } /* Compare two vis packets, used by the hashing algorithm */ -static int vis_info_cmp(void *data1, void *data2) +static int vis_info_cmp(struct hlist_node *node, void *data2) { struct vis_info *d1, *d2; struct vis_packet *p1, *p2; - d1 = data1; + + d1 = container_of(node, struct vis_info, hash_entry); d2 = data2; p1 = (struct vis_packet *)d1->skb_packet->data; p2 = (struct vis_packet *)d2->skb_packet->data; @@ -104,6 +105,34 @@ static int vis_info_choose(void *data, int size) return hash % size; } +static struct vis_info *vis_hash_find(struct bat_priv *bat_priv, + void *data) +{ + struct hashtable_t *hash = bat_priv->vis_hash; + struct hlist_head *head; + struct hlist_node *node; + struct vis_info *vis_info, *vis_info_tmp = NULL; + int index; + + if (!hash) + return NULL; + + index = vis_info_choose(data, hash->size); + head = &hash->table[index]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(vis_info, node, head, hash_entry) { + if (!vis_info_cmp(node, data)) + continue; + + vis_info_tmp = vis_info; + break; + } + rcu_read_unlock(); + + return vis_info_tmp; +} + /* insert interface to the list of interfaces of one originator, if it * does not already exist in the list */ static void vis_data_insert_interface(const uint8_t *interface, @@ -175,9 +204,8 @@ 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) { - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; struct vis_info *info; struct vis_packet *packet; struct vis_info_entry *entries; @@ -203,8 +231,8 @@ int vis_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) { - info = bucket->data; + rcu_read_lock(); + hlist_for_each_entry_rcu(info, node, head, hash_entry) { packet = (struct vis_packet *)info->skb_packet->data; entries = (struct vis_info_entry *) ((char *)packet + sizeof(struct vis_packet)); @@ -236,6 +264,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) kfree(entry); } } + rcu_read_unlock(); } buff = kmalloc(buf_size, GFP_ATOMIC); @@ -249,8 +278,8 @@ int vis_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) { - info = bucket->data; + rcu_read_lock(); + hlist_for_each_entry_rcu(info, node, head, hash_entry) { packet = (struct vis_packet *)info->skb_packet->data; entries = (struct vis_info_entry *) ((char *)packet + sizeof(struct vis_packet)); @@ -291,6 +320,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) kfree(entry); } } + rcu_read_unlock(); } spin_unlock_bh(&bat_priv->vis_hash_lock); @@ -381,10 +411,7 @@ 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(); + old_info = vis_hash_find(bat_priv, &search_elem); kfree_skb(search_elem.skb_packet); if (old_info) { @@ -444,7 +471,7 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, /* try to add it */ hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, - info); + info, &info->hash_entry); if (hash_added < 0) { /* did not work (for some reason) */ kref_put(&info->refcount, free_info); @@ -531,9 +558,8 @@ static int find_best_vis_server(struct bat_priv *bat_priv, struct vis_info *info) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; int best_tq = -1, i; @@ -544,11 +570,10 @@ static int find_best_vis_server(struct bat_priv *bat_priv, head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { if ((orig_node) && (orig_node->router) && - (orig_node->flags & VIS_SERVER) && - (orig_node->router->tq_avg > best_tq)) { + (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); @@ -577,9 +602,8 @@ static bool vis_packet_full(struct vis_info *info) static int generate_vis_packet(struct bat_priv *bat_priv) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *node; 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; @@ -608,8 +632,7 @@ static int generate_vis_packet(struct bat_priv *bat_priv) head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { neigh_node = orig_node->router; if (!neigh_node) @@ -646,8 +669,7 @@ 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) { - hna_local_entry = bucket->data; + hlist_for_each_entry(hna_local_entry, node, head, hash_entry) { entry = (struct vis_info_entry *) skb_put(info->skb_packet, sizeof(*entry)); @@ -677,25 +699,22 @@ static void purge_vis_packets(struct bat_priv *bat_priv) { int i; struct hashtable_t *hash = bat_priv->vis_hash; - struct hlist_node *walk, *safe; + struct hlist_node *node, *node_tmp; struct hlist_head *head; - struct element_t *bucket; struct vis_info *info; for (i = 0; i < hash->size; i++) { head = &hash->table[i]; - hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { - info = bucket->data; - + hlist_for_each_entry_safe(info, node, node_tmp, + head, hash_entry) { /* 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); + hlist_del(node); send_list_del(info); kref_put(&info->refcount, free_info); } @@ -707,9 +726,8 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, struct vis_info *info) { struct hashtable_t *hash = bat_priv->orig_hash; - struct hlist_node *walk; + struct hlist_node *node; struct hlist_head *head; - struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; struct sk_buff *skb; @@ -725,9 +743,7 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, head = &hash->table[i]; rcu_read_lock(); - hlist_for_each_entry_rcu(bucket, walk, head, hlist) { - orig_node = bucket->data; - + hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { /* if it's a vis server and reachable, send it. */ if ((!orig_node) || (!orig_node->router)) continue; @@ -763,14 +779,11 @@ static void unicast_vis_packet(struct bat_priv *bat_priv, 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)); + orig_node = orig_hash_find(bat_priv, packet->target_orig); if (!orig_node) goto unlock; - kref_get(&orig_node->refcount); neigh_node = orig_node->router; if (!neigh_node) @@ -909,7 +922,8 @@ int vis_init(struct bat_priv *bat_priv) INIT_LIST_HEAD(&bat_priv->vis_send_list); hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, - bat_priv->my_vis_info); + bat_priv->my_vis_info, + &bat_priv->my_vis_info->hash_entry); if (hash_added < 0) { pr_err("Can't add own vis packet into hash\n"); /* not in hash, need to remove it manually. */ @@ -931,10 +945,11 @@ err: } /* Decrease the reference count on a hash item info */ -static void free_info_ref(void *data, void *arg) +static void free_info_ref(struct hlist_node *node, void *arg) { - struct vis_info *info = data; + struct vis_info *info; + info = container_of(node, struct vis_info, hash_entry); send_list_del(info); kref_put(&info->refcount, free_info); } -- 1.7.2.3 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCH 3/4] batman-adv: Correct rcu refcounting for orig_node 2011-02-09 18:18 [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner 2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 1/2] batman-adv: separate ethernet comparing calls from hash functions Marek Lindner 2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 2/2] batman-adv: remove extra layer between hash and hash element - hash bucket Marek Lindner @ 2011-02-13 21:39 ` Marek Lindner 2011-02-13 21:40 ` [B.A.T.M.A.N.] [PATCH 4/4] batman-adv: increase refcount in create_neighbor to be consistent Marek Lindner 2011-02-18 12:26 ` [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner 4 siblings, 0 replies; 9+ messages in thread From: Marek Lindner @ 2011-02-13 21:39 UTC (permalink / raw) To: b.a.t.m.a.n; +Cc: Marek Lindner It might be possible that 2 threads access the same data in the same rcu grace period. The first thread calls call_rcu() to decrement the refcount and free the data while the second thread increases the refcount to use the data. To avoid this race condition all refcount operations have to be atomic. Reported-by: Sven Eckelmann <sven@narfation.org> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> --- batman-adv/gateway_client.c | 6 ++++-- batman-adv/icmp_socket.c | 2 +- batman-adv/originator.c | 18 ++++++++++++------ batman-adv/originator.h | 6 ++++-- batman-adv/routing.c | 22 +++++++++++----------- batman-adv/translation-table.c | 15 +++++++++------ batman-adv/types.h | 3 ++- batman-adv/unicast.c | 6 ++---- batman-adv/vis.c | 2 +- 9 files changed, 46 insertions(+), 34 deletions(-) diff --git a/batman-adv/gateway_client.c b/batman-adv/gateway_client.c index 3486854..ba6e4f2 100644 --- a/batman-adv/gateway_client.c +++ b/batman-adv/gateway_client.c @@ -53,9 +53,11 @@ void *gw_get_selected(struct bat_priv *bat_priv) goto out; orig_node = curr_gateway_tmp->orig_node; + if (!orig_node) + goto out; - if (orig_node) - kref_get(&orig_node->refcount); + if (!atomic_inc_not_zero(&orig_node->refcount)) + orig_node = NULL; out: rcu_read_unlock(); diff --git a/batman-adv/icmp_socket.c b/batman-adv/icmp_socket.c index 17792f3..34ce56c 100644 --- a/batman-adv/icmp_socket.c +++ b/batman-adv/icmp_socket.c @@ -263,7 +263,7 @@ out: if (neigh_node) neigh_node_free_ref(neigh_node); if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return len; } diff --git a/batman-adv/originator.c b/batman-adv/originator.c index c9ba013..f6be7a1 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -99,13 +99,13 @@ struct neigh_node *create_neighbor(struct orig_node *orig_node, return neigh_node; } -void orig_node_free_ref(struct kref *refcount) +static void orig_node_free_rcu(struct rcu_head *rcu) { struct hlist_node *node, *node_tmp; struct neigh_node *neigh_node, *tmp_neigh_node; struct orig_node *orig_node; - orig_node = container_of(refcount, struct orig_node, refcount); + orig_node = container_of(rcu, struct orig_node, rcu); spin_lock_bh(&orig_node->neigh_list_lock); @@ -134,6 +134,12 @@ void orig_node_free_ref(struct kref *refcount) kfree(orig_node); } +void orig_node_free_ref(struct orig_node *orig_node) +{ + if (atomic_dec_and_test(&orig_node->refcount)) + call_rcu(&orig_node->rcu, orig_node_free_rcu); +} + void originator_free(struct bat_priv *bat_priv) { struct hashtable_t *hash = bat_priv->orig_hash; @@ -159,7 +165,7 @@ void originator_free(struct bat_priv *bat_priv) head, hash_entry) { hlist_del_rcu(node); - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); } spin_unlock_bh(list_lock); } @@ -191,7 +197,9 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) spin_lock_init(&orig_node->ogm_cnt_lock); spin_lock_init(&orig_node->bcast_seqno_lock); spin_lock_init(&orig_node->neigh_list_lock); - kref_init(&orig_node->refcount); + + /* extra reference for return */ + atomic_set(&orig_node->refcount, 2); orig_node->bat_priv = bat_priv; memcpy(orig_node->orig, addr, ETH_ALEN); @@ -224,8 +232,6 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) if (hash_added < 0) goto free_bcast_own_sum; - /* extra reference for return */ - kref_get(&orig_node->refcount); return orig_node; free_bcast_own_sum: kfree(orig_node->bcast_own_sum); diff --git a/batman-adv/originator.h b/batman-adv/originator.h index b4b9a09..3d7a39d 100644 --- a/batman-adv/originator.h +++ b/batman-adv/originator.h @@ -27,7 +27,7 @@ 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); -void orig_node_free_ref(struct kref *refcount); +void orig_node_free_ref(struct orig_node *orig_node); 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, @@ -88,8 +88,10 @@ static inline struct orig_node *orig_hash_find(struct bat_priv *bat_priv, if (!compare_eth(orig_node, data)) continue; + if (!atomic_inc_not_zero(&orig_node->refcount)) + continue; + orig_node_tmp = orig_node; - kref_get(&orig_node_tmp->refcount); break; } rcu_read_unlock(); diff --git a/batman-adv/routing.c b/batman-adv/routing.c index d381cbc..dc24871 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -416,7 +416,7 @@ static void update_orig(struct bat_priv *bat_priv, neigh_node = create_neighbor(orig_node, orig_tmp, ethhdr->h_source, if_incoming); - kref_put(&orig_tmp->refcount, orig_node_free_ref); + orig_node_free_ref(orig_tmp); if (!neigh_node) goto unlock; @@ -600,7 +600,7 @@ static char count_real_packets(struct ethhdr *ethhdr, out: spin_unlock_bh(&orig_node->ogm_cnt_lock); - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return ret; } @@ -726,7 +726,7 @@ void receive_bat_packet(struct ethhdr *ethhdr, bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: " "originator packet from myself (via neighbor)\n"); - kref_put(&orig_neigh_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_neigh_node); return; } @@ -832,9 +832,9 @@ void receive_bat_packet(struct ethhdr *ethhdr, out_neigh: if ((orig_neigh_node) && (!is_single_hop_neigh)) - kref_put(&orig_neigh_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_neigh_node); out: - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); } int recv_bat_packet(struct sk_buff *skb, struct batman_if *batman_if) @@ -935,7 +935,7 @@ out: if (neigh_node) neigh_node_free_ref(neigh_node); if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return ret; } @@ -1001,7 +1001,7 @@ out: if (neigh_node) neigh_node_free_ref(neigh_node); if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return ret; } @@ -1097,7 +1097,7 @@ out: if (neigh_node) neigh_node_free_ref(neigh_node); if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return ret; } @@ -1152,7 +1152,7 @@ struct neigh_node *find_router(struct bat_priv *bat_priv, if (!primary_orig_node) goto return_router; - kref_put(&primary_orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(primary_orig_node); } /* with less than 2 candidates, we can't do any @@ -1354,7 +1354,7 @@ out: if (neigh_node) neigh_node_free_ref(neigh_node); if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return ret; } @@ -1492,7 +1492,7 @@ spin_unlock: spin_unlock_bh(&orig_node->bcast_seqno_lock); out: if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return ret; } diff --git a/batman-adv/translation-table.c b/batman-adv/translation-table.c index cd8a583..8d15b48 100644 --- a/batman-adv/translation-table.c +++ b/batman-adv/translation-table.c @@ -589,17 +589,20 @@ void hna_global_free(struct bat_priv *bat_priv) struct orig_node *transtable_search(struct bat_priv *bat_priv, uint8_t *addr) { struct hna_global_entry *hna_global_entry; + struct orig_node *orig_node = NULL; spin_lock_bh(&bat_priv->hna_ghash_lock); hna_global_entry = hna_global_hash_find(bat_priv, addr); - if (hna_global_entry) - kref_get(&hna_global_entry->orig_node->refcount); + if (!hna_global_entry) + goto out; - spin_unlock_bh(&bat_priv->hna_ghash_lock); + if (!atomic_inc_not_zero(&hna_global_entry->orig_node->refcount)) + goto out; - if (!hna_global_entry) - return NULL; + orig_node = hna_global_entry->orig_node; - return hna_global_entry->orig_node; +out: + spin_unlock_bh(&bat_priv->hna_ghash_lock); + return orig_node; } diff --git a/batman-adv/types.h b/batman-adv/types.h index cc10843..a9bf186 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -84,7 +84,8 @@ struct orig_node { struct hlist_head neigh_list; struct list_head frag_list; spinlock_t neigh_list_lock; /* protects neighbor list */ - struct kref refcount; + atomic_t refcount; + struct rcu_head rcu; struct hlist_node hash_entry; struct bat_priv *bat_priv; unsigned long last_frag_packet; diff --git a/batman-adv/unicast.c b/batman-adv/unicast.c index af81008..6bfb573 100644 --- a/batman-adv/unicast.c +++ b/batman-adv/unicast.c @@ -211,11 +211,9 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, if (*new_skb) ret = NET_RX_SUCCESS; - goto out; - out: if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return ret; } @@ -344,7 +342,7 @@ out: if (neigh_node) neigh_node_free_ref(neigh_node); if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); if (ret == 1) kfree_skb(skb); return ret; diff --git a/batman-adv/vis.c b/batman-adv/vis.c index 2e8fc4d..074feba 100644 --- a/batman-adv/vis.c +++ b/batman-adv/vis.c @@ -809,7 +809,7 @@ out: if (neigh_node) neigh_node_free_ref(neigh_node); if (orig_node) - kref_put(&orig_node->refcount, orig_node_free_ref); + orig_node_free_ref(orig_node); return; } -- 1.7.2.3 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCH 4/4] batman-adv: increase refcount in create_neighbor to be consistent 2011-02-09 18:18 [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner ` (2 preceding siblings ...) 2011-02-13 21:39 ` [B.A.T.M.A.N.] [PATCH 3/4] batman-adv: Correct rcu refcounting for orig_node Marek Lindner @ 2011-02-13 21:40 ` Marek Lindner 2011-02-18 12:26 ` [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner 4 siblings, 0 replies; 9+ messages in thread From: Marek Lindner @ 2011-02-13 21:40 UTC (permalink / raw) To: b.a.t.m.a.n; +Cc: Marek Lindner Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> --- batman-adv/originator.c | 4 ++- batman-adv/routing.c | 63 ++++++++++++++++++++-------------------------- 2 files changed, 30 insertions(+), 37 deletions(-) diff --git a/batman-adv/originator.c b/batman-adv/originator.c index f6be7a1..c2017b2 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -91,7 +91,9 @@ struct neigh_node *create_neighbor(struct orig_node *orig_node, memcpy(neigh_node->addr, neigh, ETH_ALEN); neigh_node->orig_node = orig_neigh_node; neigh_node->if_incoming = if_incoming; - atomic_set(&neigh_node->refcount, 1); + + /* extra reference for return */ + atomic_set(&neigh_node->refcount, 2); spin_lock_bh(&orig_node->neigh_list_lock); hlist_add_head_rcu(&neigh_node->list, &orig_node->neigh_list); diff --git a/batman-adv/routing.c b/batman-adv/routing.c index dc24871..3cfa2c7 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -146,7 +146,7 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, struct batman_if *if_incoming) { struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface); - struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL; + struct neigh_node *neigh_node = NULL, *tmp_neigh_node; struct hlist_node *node; unsigned char total_count; uint8_t orig_eq_count, neigh_rq_count, tq_own; @@ -157,27 +157,27 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, hlist_for_each_entry_rcu(tmp_neigh_node, node, &orig_node->neigh_list, list) { - if (compare_eth(tmp_neigh_node->addr, - orig_neigh_node->orig) && - (tmp_neigh_node->if_incoming == if_incoming)) - neigh_node = tmp_neigh_node; + if (!compare_eth(tmp_neigh_node->addr, + orig_neigh_node->orig)) + continue; + + if (tmp_neigh_node->if_incoming != if_incoming) + continue; + + if (!atomic_inc_not_zero(&tmp_neigh_node->refcount)) + continue; + + neigh_node = tmp_neigh_node; } + rcu_read_unlock(); if (!neigh_node) neigh_node = create_neighbor(orig_node, orig_neigh_node, orig_neigh_node->orig, if_incoming); - /* create_neighbor failed, return 0 */ if (!neigh_node) - goto unlock; - - if (!atomic_inc_not_zero(&neigh_node->refcount)) { - neigh_node = NULL; - goto unlock; - } - - rcu_read_unlock(); + goto out; neigh_node->last_valid = jiffies; } else { @@ -186,27 +186,27 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, hlist_for_each_entry_rcu(tmp_neigh_node, node, &orig_neigh_node->neigh_list, list) { - if (compare_eth(tmp_neigh_node->addr, - orig_neigh_node->orig) && - (tmp_neigh_node->if_incoming == if_incoming)) - neigh_node = tmp_neigh_node; + if (!compare_eth(tmp_neigh_node->addr, + orig_neigh_node->orig)) + continue; + + if (tmp_neigh_node->if_incoming != if_incoming) + continue; + + if (!atomic_inc_not_zero(&tmp_neigh_node->refcount)) + continue; + + neigh_node = tmp_neigh_node; } + rcu_read_unlock(); if (!neigh_node) neigh_node = create_neighbor(orig_neigh_node, orig_neigh_node, orig_neigh_node->orig, if_incoming); - /* create_neighbor failed, return 0 */ if (!neigh_node) - goto unlock; - - if (!atomic_inc_not_zero(&neigh_node->refcount)) { - neigh_node = NULL; - goto unlock; - } - - rcu_read_unlock(); + goto out; } orig_node->last_valid = jiffies; @@ -261,10 +261,6 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, if (batman_packet->tq >= TQ_TOTAL_BIDRECT_LIMIT) ret = 1; - goto out; - -unlock: - rcu_read_unlock(); out: if (neigh_node) neigh_node_free_ref(neigh_node); @@ -419,11 +415,6 @@ static void update_orig(struct bat_priv *bat_priv, orig_node_free_ref(orig_tmp); if (!neigh_node) goto unlock; - - if (!atomic_inc_not_zero(&neigh_node->refcount)) { - neigh_node = NULL; - goto unlock; - } } else bat_dbg(DBG_BATMAN, bat_priv, "Updating existing last-hop neighbor of originator\n"); -- 1.7.2.3 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [B.A.T.M.A.N.] reordered rcu (part II) 2011-02-09 18:18 [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner ` (3 preceding siblings ...) 2011-02-13 21:40 ` [B.A.T.M.A.N.] [PATCH 4/4] batman-adv: increase refcount in create_neighbor to be consistent Marek Lindner @ 2011-02-18 12:26 ` Marek Lindner 4 siblings, 0 replies; 9+ messages in thread From: Marek Lindner @ 2011-02-18 12:26 UTC (permalink / raw) To: The list for a Better Approach To Mobile Ad-hoc Networking On Wednesday 09 February 2011 19:18:41 Marek Lindner wrote: > here comes the next batch of changes to make the code "rcu safe". It won't > be the last one but should make all follow-ups much easier. Applied in revision 1947-1950. Regards, Marek ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2011-02-18 12:26 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-02-09 18:18 [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner 2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 1/2] batman-adv: separate ethernet comparing calls from hash functions Marek Lindner 2011-02-09 18:19 ` [B.A.T.M.A.N.] [PATCH 2/2] batman-adv: remove extra layer between hash and hash element - hash bucket Marek Lindner 2011-02-10 13:03 ` Linus Lüssing 2011-02-10 13:36 ` Marek Lindner 2011-02-13 21:36 ` [B.A.T.M.A.N.] [PATCHv2 2/4] " Marek Lindner 2011-02-13 21:39 ` [B.A.T.M.A.N.] [PATCH 3/4] batman-adv: Correct rcu refcounting for orig_node Marek Lindner 2011-02-13 21:40 ` [B.A.T.M.A.N.] [PATCH 4/4] batman-adv: increase refcount in create_neighbor to be consistent Marek Lindner 2011-02-18 12:26 ` [B.A.T.M.A.N.] reordered rcu (part II) Marek Lindner
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.