[B.A.T.M.A.N.] performance patches

List overview All Threads
Download

newer

older

[B.A.T.M.A.N.] batman-adv crash on...

Re: [B.A.T.M.A.N.] patch "staging:...

Marek Lindner

17 Nov 2010 17 Nov '10

1:26 a.m.

Hi,

after running a series of tests I noticed that batman-adv introduces a 10-20% performance overhead (depending on various factors) compared standard routing. I could identify the orig_hash locking as the main bottleneck as code all over the module requires to hold the lock causing a serious slowdown. During the last days I worked on a set of patches meant to increase the performance by replacing the orig_hash lock with rcu-locking and reference counting.

At the moment these patches are highly experimental because they fundamentally alter main data structures batman-adv possesses since it was first released. It is very likely that they will crash your system and/or introduce other funny behavior. However, feedback is highly appreciated due to the complex nature of the changes.

Known issues: * bonding / alternating candidates are not secured by refcounting (see find_router() * bcast_own / bcast_own_sum need protection, especially in orig_hash_add_if() / orig_hash_del_if() * NULL pointer dereference when an orig_node gets purged

Cheers, Marek

Show replies by date

Marek Lindner

17 Nov 17 Nov

1:26 a.m.

New subject: [B.A.T.M.A.N.] [PATCH 1/8] batman-adv: protect neighbor nodes with reference counters

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

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

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

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

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

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

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

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

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

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

-- 1.7.2.3

Linus Lüssing

20 Nov 20 Nov

6:27 p.m.

New subject: [B.A.T.M.A.N.] [PATCH 1/8] batman-adv: protect neighbor nodes with reference counters

Hi Marek,

...

@@ -108,7 +110,12 @@ static void update_route(struct bat_priv *bat_priv, orig_node->router->addr); }
neigh_node_tmp = orig_node->router; orig_node->router = neigh_node;

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

I guess you meant "kref_put(&neigh_node_tmp,... instead of neigh_node (without tmp) here, as neigh_node_tmp won't be used anymore, not neigh_node, right? Otherwise it also does not seem to make sense to first increase the refcount and then decreasing it right again after the additional check.

Marek Lindner

8:04 p.m.

New subject: [B.A.T.M.A.N.] [PATCH 1/8] batman-adv: protect neighbor nodes with reference counters

On Saturday 20 November 2010 19:27:01 Linus Lüssing wrote:

...

I guess you meant "kref_put(&neigh_node_tmp,... instead of neigh_node (without tmp) here, as neigh_node_tmp won't be used anymore, not neigh_node, right? Otherwise it also does not seem to make sense to first increase the refcount and then decreasing it right again after the additional check.

Yes, you are right. I'll fix that.

Thanks, Marek

Marek Lindner

17 Nov 17 Nov

1:26 a.m.

New subject: [B.A.T.M.A.N.] [PATCH 2/8] batman-adv: convert neighbor list to hlist

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

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

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

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

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

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

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

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

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

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

*best_neigh_node = NULL;

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

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

neigh_purged = true; - list_del(list_pos); + + hlist_del(&neigh_node->list); kref_put(&neigh_node->refcount, neigh_node_free_ref); } else { if ((*best_neigh_node == NULL) || @@ -328,6 +328,7 @@ void purge_orig_ref(struct bat_priv *bat_priv) int orig_seq_print_text(struct seq_file *seq, void *offset) { HASHIT(hashit); + struct hlist_node *node; struct element_t *bucket; struct net_device *net_dev = (struct net_device *)seq->private; struct bat_priv *bat_priv = netdev_priv(net_dev); @@ -379,7 +380,8 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) orig_node->router->tq_avg, orig_node->router->addr, orig_node->router->if_incoming->net_dev->name);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- 1.7.2.3

Marek Lindner

1:26 a.m.

New subject: [B.A.T.M.A.N.] [PATCH 3/8] batman-adv: protect neighbor list with rcu locks

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- batman-adv/originator.c | 31 ++++++++++++++++++++++++++----- batman-adv/routing.c | 13 +++++++++++++ batman-adv/types.h | 2 ++ 3 files changed, 41 insertions(+), 5 deletions(-)

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

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

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

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

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

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

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

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

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

*best_neigh_node = NULL;

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

neigh_purged = true;

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

@@ -380,11 +399,13 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) orig_node->router->tq_avg, orig_node->router->addr, orig_node->router->if_incoming->net_dev->name);

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

seq_printf(seq, "\n"); batman_count++; diff --git a/batman-adv/routing.c b/batman-adv/routing.c index c4ab00b..34df9c1 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -146,6 +146,7 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, unsigned char total_count;

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

@@ -154,6 +155,7 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, (tmp_neigh_node->if_incoming == if_incoming)) neigh_node = tmp_neigh_node; } + rcu_read_unlock();

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

@@ -175,6 +178,7 @@ static int is_bidirectional_neigh(struct orig_node *orig_node, (tmp_neigh_node->if_incoming == if_incoming)) neigh_node = tmp_neigh_node; } + rcu_read_unlock();

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

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

if (!neigh_node) { struct orig_node *orig_tmp; @@ -403,6 +409,7 @@ static char count_real_packets(struct ethhdr *ethhdr, &orig_node->batman_seqno_reset)) return -1;

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

@@ -424,6 +431,7 @@ static char count_real_packets(struct ethhdr *ethhdr, tmp_neigh_node->real_packet_count = bit_packet_count(tmp_neigh_node->real_bits); } + rcu_read_unlock();

if (need_update) { bat_dbg(DBG_BATMAN, bat_priv, @@ -476,13 +484,17 @@ void update_bonding_candidates(struct bat_priv *bat_priv, * as "bonding partner" */

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

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

@@ -536,6 +548,7 @@ void update_bonding_candidates(struct bat_priv *bat_priv,

candidates++; } + rcu_read_unlock();

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

-- 1.7.2.3

Marek Lindner

1:26 a.m.

New subject: [B.A.T.M.A.N.] [PATCH 4/8] batman-adv: remove hash resize functions

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- batman-adv/hash.h | 38 -------------------------------------- batman-adv/originator.c | 14 +------------- batman-adv/translation-table.c | 32 ++------------------------------ 3 files changed, 3 insertions(+), 81 deletions(-)

diff --git a/batman-adv/hash.h b/batman-adv/hash.h index 0b61c6e..ab67dcf 100644 --- a/batman-adv/hash.h +++ b/batman-adv/hash.h @@ -181,44 +181,6 @@ static inline void *hash_find(struct hashtable_t *hash, return NULL; }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- 1.7.2.3

Marek Lindner

1:26 a.m.

New subject: [B.A.T.M.A.N.] [PATCH 5/8] batman-adv: protect each hash row with rcu locks

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- batman-adv/hash.c | 46 +++++++++++---- batman-adv/hash.h | 125 ++++++++++++++++++++++++++-------------- batman-adv/icmp_socket.c | 2 + batman-adv/originator.c | 2 + batman-adv/routing.c | 12 ++++ batman-adv/translation-table.c | 15 +++++ batman-adv/unicast.c | 7 ++- batman-adv/vis.c | 4 + 8 files changed, 157 insertions(+), 56 deletions(-)

diff --git a/batman-adv/hash.c b/batman-adv/hash.c index 8605e2f..e2266f6 100644 --- a/batman-adv/hash.c +++ b/batman-adv/hash.c @@ -29,13 +29,16 @@ static void hash_init(struct hashtable_t *hash)

hash->elements = 0;

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

/* free only the hashtable and the hash itself. */ void hash_destroy(struct hashtable_t *hash) { + kfree(hash->list_locks); kfree(hash->table); kfree(hash); } @@ -45,22 +48,35 @@ struct hashtable_t *hash_new(int size) { struct hashtable_t *hash;

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

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

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

+ hash->size = size; hash_init(hash); - return hash; + +free_table: + kfree(hash->table); +free_hash: + kfree(hash); + return NULL; +} + +void bucket_free_rcu(struct rcu_head *rcu) +{ + struct element_t *bucket; + + bucket = container_of(rcu, struct element_t, rcu); + kfree(bucket); }

/* remove bucket (this might be used in hash_iterate() if you already found the @@ -71,12 +87,18 @@ void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) { void *data_save; struct element_t *bucket; + spinlock_t *list_lock; + + list_lock = &hash->list_locks[hash_it_t->index];

bucket = hlist_entry(hash_it_t->walk, struct element_t, hlist); data_save = bucket->data;

- hlist_del(hash_it_t->walk); - kfree(bucket); + spin_lock_bh(list_lock); + hlist_del_rcu(hash_it_t->walk); + spin_unlock_bh(list_lock); + + call_rcu(&bucket->rcu, bucket_free_rcu); hash->elements--;

return data_save; diff --git a/batman-adv/hash.h b/batman-adv/hash.h index ab67dcf..3ebfe5a 100644 --- a/batman-adv/hash.h +++ b/batman-adv/hash.h @@ -43,6 +43,7 @@ typedef void (*hashdata_free_cb)(void *, void *); struct element_t { void *data; /* pointer to the data */ struct hlist_node hlist; /* bucket list pointer */ + struct rcu_head rcu; };

struct hash_it_t { @@ -52,7 +53,8 @@ struct hash_it_t { };

struct hashtable_t { - struct hlist_head *table; /* the hashtable itself, with the buckets */ + struct hlist_head *table; /* the hashtable itself with the buckets */ + spinlock_t *list_locks; /* spinlock for each hash list entry */ int elements; /* number of elements registered */ int size; /* size of hashtable */ }; @@ -69,6 +71,8 @@ void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t); /* 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. */ @@ -78,19 +82,22 @@ static inline void hash_delete(struct hashtable_t *hash, struct hlist_head *head; struct hlist_node *walk, *safe; struct element_t *bucket; + spinlock_t *list_lock; int i;

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

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

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

hash_destroy(hash); @@ -105,30 +112,40 @@ static inline int hash_add(struct hashtable_t *hash, struct hlist_head *head; struct hlist_node *walk, *safe; struct element_t *bucket; + spinlock_t *list_lock;

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

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

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

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

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

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

/* removes data from hash, if found. returns pointer do data on success, so you @@ -142,21 +159,29 @@ static inline void *hash_remove(struct hashtable_t *hash, struct hash_it_t hash_it_t; struct element_t *bucket; struct hlist_head *head; + void *bucket_data = NULL;

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

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

- return NULL; + return bucket_data; }

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

if (!hash) return NULL; @@ -172,50 +198,63 @@ static inline void *hash_find(struct hashtable_t *hash, index = choose(keydata , hash->size); head = &hash->table[index];

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

- return NULL; + return bucket_data; }

-/* iterate though the hash. First element is selected if an iterator +/** + * iterate though the hash. First element is selected if an iterator * initialized with HASHIT() is supplied as iter. Use the returned * (or supplied) iterator to access the elements until hash_iterate returns - * NULL. */ + * NULL. + * + * caller must lock with rcu_read_lock() / rcu_read_unlock() + **/ static inline struct hash_it_t *hash_iterate(struct hashtable_t *hash, struct hash_it_t *iter) { if (!hash) - return NULL; + goto out; + if (!iter) - return NULL; + goto out;

iter->walk = iter->safe;

/* we search for the next head with list entries */ - if (!iter->walk) { - while (iter->index < hash->size) { - if (hlist_empty(&hash->table[iter->index])) - iter->index++; - else { - iter->walk = hash->table[iter->index].first; - - /* search next time */ - ++iter->index; - break; - } + if (iter->walk) + goto iter_next; + + while (iter->index < hash->size) { + if (hlist_empty(&hash->table[iter->index])) { + iter->index++; + continue; } + + iter->walk = + rcu_dereference(hash->table[iter->index].first); + + /* search next time */ + ++iter->index; + break; }

/* return iter when we found bucket otherwise null */ if (!iter->walk) - return NULL; + goto out;

- iter->safe = iter->walk->next; +iter_next: + iter->safe = rcu_dereference(iter->walk->next); return iter; + +out: + return NULL; }

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

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

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

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

if (orig_node) return orig_node; diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 34df9c1..0b4ebfb 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -850,9 +850,11 @@ static int recv_my_icmp_packet(struct bat_priv *bat_priv, /* answer echo request (ping) */ /* get routing information */ spin_lock_bh(&bat_priv->orig_hash_lock); + rcu_read_lock(); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, choose_orig, icmp_packet->orig)); + rcu_read_unlock(); ret = NET_RX_DROP;

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

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

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

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

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

router = find_router(bat_priv, orig_node, recv_if);

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

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

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

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

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

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

if (hna_global_entry) _hna_global_del_orig(bat_priv, hna_global_entry, @@ -237,9 +241,12 @@ void hna_local_remove(struct bat_priv *bat_priv,

spin_lock_bh(&bat_priv->hna_lhash_lock);

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

@@ -311,9 +318,11 @@ void hna_global_add_orig(struct bat_priv *bat_priv, spin_lock_bh(&bat_priv->hna_ghash_lock);

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

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

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

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

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

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

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

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

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

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

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

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

if (old_info != NULL) { @@ -717,9 +719,11 @@ static void unicast_vis_packet(struct bat_priv *bat_priv,

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

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

-- 1.7.2.3

Marek Lindner

1:26 a.m.

New subject: [B.A.T.M.A.N.] [PATCH 6/8] batman-adv: protect originator nodes with reference counters

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

diff --git a/batman-adv/originator.c b/batman-adv/originator.c index 8847bdd..58c479d 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -103,12 +103,13 @@ struct neigh_node *create_neighbor(struct orig_node *orig_node, return neigh_node; }

-static void free_orig_node(void *data, void *arg) +void orig_node_free_ref(struct kref *refcount) { struct hlist_node *node, *node_tmp; struct neigh_node *neigh_node; - struct orig_node *orig_node = (struct orig_node *)data; - struct bat_priv *bat_priv = (struct bat_priv *)arg; + struct orig_node *orig_node; + + orig_node = container_of(refcount, struct orig_node, refcount);

spin_lock_bh(&orig_node->neigh_list_lock);

@@ -122,7 +123,8 @@ static void free_orig_node(void *data, void *arg) spin_unlock_bh(&orig_node->neigh_list_lock);

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

kfree(orig_node->bcast_own); kfree(orig_node->bcast_own_sum); @@ -131,13 +133,25 @@ static void free_orig_node(void *data, void *arg)

void originator_free(struct bat_priv *bat_priv) { + HASHIT(hashit); + struct element_t *bucket; + struct orig_node *orig_node; + if (!bat_priv->orig_hash) return;

cancel_delayed_work_sync(&bat_priv->orig_work);

spin_lock_bh(&bat_priv->orig_hash_lock); - hash_delete(bat_priv->orig_hash, free_orig_node, bat_priv); + + while (hash_iterate(bat_priv->orig_hash, &hashit)) { + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + orig_node = bucket->data; + + hash_remove_bucket(bat_priv->orig_hash, &hashit); + kref_put(&orig_node->refcount, orig_node_free_ref); + } + bat_priv->orig_hash = NULL; spin_unlock_bh(&bat_priv->orig_hash_lock); } @@ -156,8 +170,10 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) addr)); rcu_read_unlock();

- if (orig_node) + if (orig_node) { + kref_get(&orig_node->refcount); return orig_node; + }

bat_dbg(DBG_BATMAN, bat_priv, "Creating new originator: %pM\n", addr); @@ -168,7 +184,9 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr)

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

+ orig_node->bat_priv = bat_priv; memcpy(orig_node->orig, addr, ETH_ALEN); orig_node->router = NULL; orig_node->hna_buff = NULL; @@ -197,6 +215,8 @@ 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); @@ -302,7 +322,7 @@ static void _purge_orig(struct bat_priv *bat_priv) if (orig_node->gw_flags) gw_node_delete(bat_priv, orig_node); hash_remove_bucket(bat_priv->orig_hash, &hashit); - free_orig_node(orig_node, bat_priv); + kref_put(&orig_node->refcount, orig_node_free_ref); }

if (time_after(jiffies, (orig_node->last_frag_packet + diff --git a/batman-adv/originator.h b/batman-adv/originator.h index f3676fa..f5a6964 100644 --- a/batman-adv/originator.h +++ b/batman-adv/originator.h @@ -25,6 +25,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); 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, diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 0b4ebfb..1c2dee1 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -291,6 +291,8 @@ 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); if (!neigh_node) return; } else @@ -399,7 +401,7 @@ static char count_real_packets(struct ethhdr *ethhdr, int set_mark;

orig_node = get_orig_node(bat_priv, batman_packet->orig); - if (orig_node == NULL) + if (!orig_node) return 0;

seq_diff = batman_packet->seqno - orig_node->last_real_seqno; @@ -407,7 +409,7 @@ static char count_real_packets(struct ethhdr *ethhdr, /* signalize caller that the packet is to be dropped. */ if (window_protected(bat_priv, seq_diff, &orig_node->batman_seqno_reset)) - return -1; + goto err;

rcu_read_lock(); hlist_for_each_entry(tmp_neigh_node, node, @@ -440,7 +442,12 @@ static char count_real_packets(struct ethhdr *ethhdr, orig_node->last_real_seqno = batman_packet->seqno; }

+ kref_put(&orig_node->refcount, orig_node_free_ref); return is_duplicate; + +err: + kref_put(&orig_node->refcount, orig_node_free_ref); + return -1; }

/* copy primary address for bonding */ @@ -657,7 +664,6 @@ void receive_bat_packet(struct ethhdr *ethhdr, int offset;

orig_neigh_node = get_orig_node(bat_priv, ethhdr->h_source); - if (!orig_neigh_node) return;

@@ -678,6 +684,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); return; }

@@ -689,7 +696,7 @@ void receive_bat_packet(struct ethhdr *ethhdr, }

orig_node = get_orig_node(bat_priv, batman_packet->orig); - if (orig_node == NULL) + if (!orig_node) return;

is_duplicate = count_real_packets(ethhdr, batman_packet, if_incoming); @@ -698,13 +705,13 @@ void receive_bat_packet(struct ethhdr *ethhdr, bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: packet within seqno protection time " "(sender: %pM)\n", ethhdr->h_source); - return; + goto out; }

if (batman_packet->tq == 0) { bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: originator packet with tq equal 0\n"); - return; + goto out; }

/* avoid temporary routing loops */ @@ -718,7 +725,7 @@ void receive_bat_packet(struct ethhdr *ethhdr, bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: ignoring all rebroadcast packets that " "may make me loop (sender: %pM)\n", ethhdr->h_source); - return; + goto out; }

/* if sender is a direct neighbor the sender mac equals @@ -726,8 +733,8 @@ void receive_bat_packet(struct ethhdr *ethhdr, orig_neigh_node = (is_single_hop_neigh ? orig_node : get_orig_node(bat_priv, ethhdr->h_source)); - if (orig_neigh_node == NULL) - return; + if (!orig_neigh_node) + goto out_neigh;

/* drop packet if sender is not a direct neighbor and if we * don't route towards it */ @@ -735,7 +742,7 @@ void receive_bat_packet(struct ethhdr *ethhdr, (orig_neigh_node->router == NULL)) { bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: OGM via unknown neighbor!\n"); - return; + goto out_neigh; }

is_bidirectional = is_bidirectional_neigh(orig_node, orig_neigh_node, @@ -763,26 +770,32 @@ void receive_bat_packet(struct ethhdr *ethhdr,

bat_dbg(DBG_BATMAN, bat_priv, "Forwarding packet: " "rebroadcast neighbor packet with direct link flag\n"); - return; + goto out_neigh; }

/* multihop originator */ if (!is_bidirectional) { bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: not received via bidirectional link\n"); - return; + goto out_neigh; }

if (is_duplicate) { bat_dbg(DBG_BATMAN, bat_priv, "Drop packet: duplicate packet received\n"); - return; + goto out_neigh; }

bat_dbg(DBG_BATMAN, bat_priv, "Forwarding packet: rebroadcast originator packet\n"); schedule_forward_packet(orig_node, ethhdr, batman_packet, 0, hna_buff_len, if_incoming); + +out_neigh: + if (!is_single_hop_neigh) + kref_put(&orig_neigh_node->refcount, orig_node_free_ref); +out: + kref_put(&orig_node->refcount, orig_node_free_ref); }

int recv_bat_packet(struct sk_buff *skb, struct batman_if *batman_if) diff --git a/batman-adv/types.h b/batman-adv/types.h index 1d6365d..f4ce526 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -86,6 +86,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; + struct bat_priv *bat_priv; unsigned long last_frag_packet; struct { uint8_t candidates;

-- 1.7.2.3

Marek Lindner

1:26 a.m.

New subject: [B.A.T.M.A.N.] [PATCH 7/8] batman-adv: replace orig_hash hash_iterate() with individual functions

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- batman-adv/originator.c | 212 +++++++++++++++++++++++++++++++++-------------- batman-adv/routing.c | 32 ++++++-- batman-adv/vis.c | 157 ++++++++++++++++++++++------------ 3 files changed, 275 insertions(+), 126 deletions(-)

diff --git a/batman-adv/originator.c b/batman-adv/originator.c index 58c479d..d573a5b 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -133,26 +133,44 @@ void orig_node_free_ref(struct kref *refcount)

void originator_free(struct bat_priv *bat_priv) { - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk, *safe; + struct hlist_head *head; struct element_t *bucket; + spinlock_t *list_lock; struct orig_node *orig_node; + int i, ret;

- if (!bat_priv->orig_hash) + if (!hash) return;

cancel_delayed_work_sync(&bat_priv->orig_work);

spin_lock_bh(&bat_priv->orig_hash_lock); + bat_priv->orig_hash = NULL; + + for (i = 0; i < hash->size; i++) { + rcu_read_lock(); + ret = hlist_empty(&hash->table[i]); + rcu_read_unlock(); + + if (ret) + continue;

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

- hash_remove_bucket(bat_priv->orig_hash, &hashit); - kref_put(&orig_node->refcount, orig_node_free_ref); + spin_lock_bh(list_lock); + hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { + hlist_del_rcu(walk); + orig_node = bucket->data; + kref_put(&orig_node->refcount, orig_node_free_ref); + call_rcu(&bucket->rcu, bucket_free_rcu); + } + spin_unlock_bh(list_lock); }

- bat_priv->orig_hash = NULL; + hash_destroy(hash); spin_unlock_bh(&bat_priv->orig_hash_lock); }

@@ -307,27 +325,52 @@ static bool purge_orig_node(struct bat_priv *bat_priv,

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

spin_lock_bh(&bat_priv->orig_hash_lock);

/* for all origins... */ - while (hash_iterate(bat_priv->orig_hash, &hashit)) { - bucket = hlist_entry(hashit.walk, struct element_t, hlist); - orig_node = bucket->data; - - if (purge_orig_node(bat_priv, orig_node)) { - if (orig_node->gw_flags) - gw_node_delete(bat_priv, orig_node); - hash_remove_bucket(bat_priv->orig_hash, &hashit); - kref_put(&orig_node->refcount, orig_node_free_ref); - } + for (i = 0; i < hash->size; i++) { + rcu_read_lock(); + ret = hlist_empty(&hash->table[i]); + rcu_read_unlock(); + + if (ret) + continue;

- if (time_after(jiffies, (orig_node->last_frag_packet + + head = &hash->table[i]; + list_lock = &hash->list_locks[i]; + + spin_lock_bh(list_lock); + hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) { + orig_node = bucket->data; + + if (purge_orig_node(bat_priv, orig_node)) { + if (orig_node->gw_flags) + gw_node_delete(bat_priv, orig_node); + hlist_del_rcu(walk); + kref_put(&orig_node->refcount, + orig_node_free_ref); + call_rcu(&bucket->rcu, bucket_free_rcu); + hash->elements--; + continue; + } + + if (time_after(jiffies, (orig_node->last_frag_packet + msecs_to_jiffies(FRAG_TIMEOUT)))) - frag_list_free(&orig_node->frag_list); + frag_list_free(&orig_node->frag_list); + + } + spin_unlock_bh(list_lock); }

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -356,16 +399,18 @@ void purge_orig_ref(struct bat_priv *bat_priv)

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

if ((!bat_priv->primary_if) || (bat_priv->primary_if->if_status != IF_ACTIVE)) { @@ -389,36 +434,48 @@ int orig_seq_print_text(struct seq_file *seq, void *offset)

spin_lock_bh(&bat_priv->orig_hash_lock);

- if (!orig_node->router) + if (ret) continue;

- if (orig_node->router->tq_avg == 0) - continue; + head = &hash->table[i]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { + orig_node = bucket->data; + + if (!orig_node->router) + continue;

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

- seq_printf(seq, "%pM %4i.%03is (%3i) %pM [%10s]:", - orig_node->orig, last_seen_secs, last_seen_msecs, - orig_node->router->tq_avg, orig_node->router->addr, - orig_node->router->if_incoming->net_dev->name); - - rcu_read_lock(); - hlist_for_each_entry(neigh_node, node, - &orig_node->neigh_list, list) { - seq_printf(seq, " %pM (%3i)", neigh_node->addr, - neigh_node->tq_avg); + neigh_node = orig_node->router; + seq_printf(seq, "%pM %4i.%03is (%3i) %pM [%10s]:", + orig_node->orig, last_seen_secs, + last_seen_msecs, neigh_node->tq_avg, + neigh_node->addr, + neigh_node->if_incoming->net_dev->name); + + hlist_for_each_entry(neigh_node, node, + &orig_node->neigh_list, list) { + seq_printf(seq, " %pM (%3i)", neigh_node->addr, + neigh_node->tq_avg); + } + + seq_printf(seq, "\n"); + batman_count++; } rcu_read_unlock(); - - seq_printf(seq, "\n"); - batman_count++; }

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

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

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

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

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

err: + rcu_read_unlock(); spin_unlock_bh(&bat_priv->orig_hash_lock); return -ENOMEM; } @@ -541,25 +614,39 @@ free_own_sum: int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) { struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; + struct element_t *bucket; struct batman_if *batman_if_tmp; struct orig_node *orig_node; - HASHIT(hashit); - struct element_t *bucket; - int ret; + int i, ret;

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

- ret = orig_node_del_if(orig_node, max_if_num, - batman_if->if_num); + ret = orig_node_del_if(orig_node, max_if_num, + batman_if->if_num);

- if (ret == -1) - goto err; + if (ret == -1) + goto err; + } + rcu_read_unlock(); }

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

err: + rcu_read_unlock(); spin_unlock_bh(&bat_priv->orig_hash_lock); return -ENOMEM; } diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 1c2dee1..8dadd2a 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -39,21 +39,37 @@ void slide_own_bcast_window(struct batman_if *batman_if) { struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; TYPE_OF_WORD *word; + int ret, i;

spin_lock_bh(&bat_priv->orig_hash_lock);

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

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

spin_unlock_bh(&bat_priv->orig_hash_lock); diff --git a/batman-adv/vis.c b/batman-adv/vis.c index ff3fabf..69efdf4 100644 --- a/batman-adv/vis.c +++ b/batman-adv/vis.c @@ -513,24 +513,40 @@ end: static int find_best_vis_server(struct bat_priv *bat_priv, struct vis_info *info) { - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; - int best_tq = -1; + int best_tq = -1, i, ret;

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

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

@@ -551,14 +567,17 @@ static bool vis_packet_full(struct vis_info *info) static int generate_vis_packet(struct bat_priv *bat_priv) { HASHIT(hashit_local); - HASHIT(hashit_global); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; + struct neigh_node *neigh_node; struct vis_info *info = (struct vis_info *)bat_priv->my_vis_info; struct vis_packet *packet = (struct vis_packet *)info->skb_packet->data; struct vis_info_entry *entry; struct hna_local_entry *hna_local_entry; - int best_tq = -1; + int best_tq = -1, i, ret;

info->first_seen = jiffies; packet->vis_type = atomic_read(&bat_priv->vis_mode); @@ -579,37 +598,49 @@ static int generate_vis_packet(struct bat_priv *bat_priv) } }

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

- if (!orig_node->router) + if (ret) continue;

- if (!compare_orig(orig_node->router->addr, orig_node->orig)) - continue; + head = &hash->table[i];

- if (orig_node->router->if_incoming->if_status != IF_ACTIVE) - continue; + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { + orig_node = bucket->data; + neigh_node = orig_node->router;

- if (orig_node->router->tq_avg < 1) - continue; + if (!neigh_node) + continue;

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

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

spin_unlock_bh(&bat_priv->orig_hash_lock); @@ -664,45 +695,59 @@ static void purge_vis_packets(struct bat_priv *bat_priv) static void broadcast_vis_packet(struct bat_priv *bat_priv, struct vis_info *info) { - HASHIT(hashit); + struct hashtable_t *hash = bat_priv->orig_hash; + struct hlist_node *walk; + struct hlist_head *head; struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; struct sk_buff *skb; struct batman_if *batman_if; uint8_t dstaddr[ETH_ALEN]; + int i, ret;

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

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

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

- memcpy(packet->target_orig, orig_node->orig, ETH_ALEN); - batman_if = orig_node->router->if_incoming; - memcpy(dstaddr, orig_node->router->addr, ETH_ALEN); - spin_unlock_bh(&bat_priv->orig_hash_lock); + head = &hash->table[i];

- skb = skb_clone(info->skb_packet, GFP_ATOMIC); - if (skb) - send_skb_packet(skb, batman_if, dstaddr); + rcu_read_lock(); + hlist_for_each_entry_rcu(bucket, walk, head, hlist) { + orig_node = bucket->data;

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

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

spin_unlock_bh(&bat_priv->orig_hash_lock);

-- 1.7.2.3

Marek Lindner

1:26 a.m.

New subject: [B.A.T.M.A.N.] [PATCH 8/8] batman-adv: remove orig_hash spinlock

Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- batman-adv/icmp_socket.c | 35 +++--- batman-adv/main.c | 1 - batman-adv/originator.c | 21 --- batman-adv/routing.c | 312 ++++++++++++++++++++++++---------------------- batman-adv/types.h | 1 - batman-adv/unicast.c | 96 +++++++++------ batman-adv/vis.c | 58 +++++----- 7 files changed, 264 insertions(+), 260 deletions(-)

diff --git a/batman-adv/icmp_socket.c b/batman-adv/icmp_socket.c index a9a10ed..3598f2b 100644 --- a/batman-adv/icmp_socket.c +++ b/batman-adv/icmp_socket.c @@ -157,10 +157,9 @@ static ssize_t bat_socket_write(struct file *file, const char __user *buff, struct sk_buff *skb; struct icmp_packet_rr *icmp_packet;

- struct orig_node *orig_node; - struct batman_if *batman_if; + struct orig_node *orig_node = NULL; + struct neigh_node *neigh_node = NULL; size_t packet_len = sizeof(struct icmp_packet); - uint8_t dstaddr[ETH_ALEN];

if (len < sizeof(struct icmp_packet)) { bat_dbg(DBG_BATMAN, bat_priv, @@ -220,49 +219,51 @@ static ssize_t bat_socket_write(struct file *file, const char __user *buff, if (atomic_read(&bat_priv->mesh_state) != MESH_ACTIVE) goto dst_unreach;

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

if (!orig_node) goto unlock;

- if (!orig_node->router) - goto unlock; + kref_get(&orig_node->refcount); + neigh_node = orig_node->router;

- batman_if = orig_node->router->if_incoming; - memcpy(dstaddr, orig_node->router->addr, ETH_ALEN); + if (!neigh_node) + goto unlock;

- spin_unlock_bh(&bat_priv->orig_hash_lock); + kref_get(&neigh_node->refcount); + rcu_read_unlock();

- if (!batman_if) + if (!neigh_node->if_incoming) goto dst_unreach;

- if (batman_if->if_status != IF_ACTIVE) + if (neigh_node->if_incoming->if_status != IF_ACTIVE) goto dst_unreach;

memcpy(icmp_packet->orig, bat_priv->primary_if->net_dev->dev_addr, ETH_ALEN);

if (packet_len == sizeof(struct icmp_packet_rr)) - memcpy(icmp_packet->rr, batman_if->net_dev->dev_addr, ETH_ALEN); - - - send_skb_packet(skb, batman_if, dstaddr); + memcpy(icmp_packet->rr, + neigh_node->if_incoming->net_dev->dev_addr, ETH_ALEN);

+ send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); goto out;

unlock: - spin_unlock_bh(&bat_priv->orig_hash_lock); + rcu_read_unlock(); dst_unreach: icmp_packet->msg_type = DESTINATION_UNREACHABLE; bat_socket_add_packet(socket_client, icmp_packet, packet_len); free_skb: kfree_skb(skb); out: + if (neigh_node) + kref_put(&neigh_node->refcount, neigh_node_free_ref); + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); return len; }

diff --git a/batman-adv/main.c b/batman-adv/main.c index c91e635..8acbb57 100644 --- a/batman-adv/main.c +++ b/batman-adv/main.c @@ -80,7 +80,6 @@ int mesh_init(struct net_device *soft_iface) { struct bat_priv *bat_priv = netdev_priv(soft_iface);

- spin_lock_init(&bat_priv->orig_hash_lock); spin_lock_init(&bat_priv->forw_bat_list_lock); spin_lock_init(&bat_priv->forw_bcast_list_lock); spin_lock_init(&bat_priv->hna_lhash_lock); diff --git a/batman-adv/originator.c b/batman-adv/originator.c index d573a5b..923cc39 100644 --- a/batman-adv/originator.c +++ b/batman-adv/originator.c @@ -44,18 +44,15 @@ int originator_init(struct bat_priv *bat_priv) if (bat_priv->orig_hash) return 1;

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

if (!bat_priv->orig_hash) goto err;

- spin_unlock_bh(&bat_priv->orig_hash_lock); start_purge_timer(bat_priv); return 1;

err: - spin_unlock_bh(&bat_priv->orig_hash_lock); return 0; }

@@ -146,7 +143,6 @@ void originator_free(struct bat_priv *bat_priv)

cancel_delayed_work_sync(&bat_priv->orig_work);

- spin_lock_bh(&bat_priv->orig_hash_lock); bat_priv->orig_hash = NULL;

for (i = 0; i < hash->size; i++) { @@ -171,7 +167,6 @@ void originator_free(struct bat_priv *bat_priv) }

hash_destroy(hash); - spin_unlock_bh(&bat_priv->orig_hash_lock); }

/* this function finds or creates an originator entry for the given @@ -336,8 +331,6 @@ static void _purge_orig(struct bat_priv *bat_priv) if (!hash) return;

- spin_lock_bh(&bat_priv->orig_hash_lock); - /* for all origins... */ for (i = 0; i < hash->size; i++) { rcu_read_lock(); @@ -373,8 +366,6 @@ static void _purge_orig(struct bat_priv *bat_priv) spin_unlock_bh(list_lock); }

- spin_unlock_bh(&bat_priv->orig_hash_lock); - gw_node_purge(bat_priv); gw_election(bat_priv);

@@ -432,8 +423,6 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) "Originator", "last-seen", "#", TQ_MAX_VALUE, "Nexthop", "outgoingIF", "Potential nexthops");

- spin_lock_bh(&bat_priv->orig_hash_lock); - for (i = 0; i < hash->size; i++) { rcu_read_lock(); ret = hlist_empty(&hash->table[i]); @@ -478,8 +467,6 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) rcu_read_unlock(); }

- spin_unlock_bh(&bat_priv->orig_hash_lock); - if ((batman_count == 0)) seq_printf(seq, "No batman nodes in range ...\n");

@@ -528,8 +515,6 @@ int orig_hash_add_if(struct batman_if *batman_if, int max_if_num)

/* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ - spin_lock_bh(&bat_priv->orig_hash_lock); - for (i = 0; i < hash->size; i++) { rcu_read_lock(); ret = hlist_empty(&hash->table[i]); @@ -550,12 +535,10 @@ int orig_hash_add_if(struct batman_if *batman_if, int max_if_num) rcu_read_unlock(); }

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

err: rcu_read_unlock(); - spin_unlock_bh(&bat_priv->orig_hash_lock); return -ENOMEM; }

@@ -624,8 +607,6 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num)

/* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ - spin_lock_bh(&bat_priv->orig_hash_lock); - for (i = 0; i < hash->size; i++) { rcu_read_lock(); ret = hlist_empty(&hash->table[i]); @@ -667,11 +648,9 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) rcu_read_unlock();

batman_if->if_num = -1; - spin_unlock_bh(&bat_priv->orig_hash_lock); return 0;

err: rcu_read_unlock(); - spin_unlock_bh(&bat_priv->orig_hash_lock); return -ENOMEM; } diff --git a/batman-adv/routing.c b/batman-adv/routing.c index 8dadd2a..c50da08 100644 --- a/batman-adv/routing.c +++ b/batman-adv/routing.c @@ -47,8 +47,6 @@ void slide_own_bcast_window(struct batman_if *batman_if) TYPE_OF_WORD *word; int ret, i;

- spin_lock_bh(&bat_priv->orig_hash_lock); - for (i = 0; i < hash->size; i++) { rcu_read_lock(); ret = hlist_empty(&hash->table[i]); @@ -71,8 +69,6 @@ void slide_own_bcast_window(struct batman_if *batman_if) } rcu_read_unlock(); } - - spin_unlock_bh(&bat_priv->orig_hash_lock); }

static void update_HNA(struct bat_priv *bat_priv, struct orig_node *orig_node, @@ -816,7 +812,6 @@ out:

int recv_bat_packet(struct sk_buff *skb, struct batman_if *batman_if) { - struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); struct ethhdr *ethhdr;

/* drop packet if it has not necessary minimum size */ @@ -843,12 +838,10 @@ int recv_bat_packet(struct sk_buff *skb, struct batman_if *batman_if)

ethhdr = (struct ethhdr *)skb_mac_header(skb);

- spin_lock_bh(&bat_priv->orig_hash_lock); receive_aggr_bat_packet(ethhdr, skb->data, skb_headlen(skb), batman_if); - spin_unlock_bh(&bat_priv->orig_hash_lock);

kfree_skb(skb); return NET_RX_SUCCESS; @@ -857,12 +850,11 @@ int recv_bat_packet(struct sk_buff *skb, struct batman_if *batman_if) static int recv_my_icmp_packet(struct bat_priv *bat_priv, struct sk_buff *skb, size_t icmp_len) { - struct orig_node *orig_node; + struct orig_node *orig_node = NULL; + struct neigh_node *neigh_node = NULL; struct icmp_packet_rr *icmp_packet; struct ethhdr *ethhdr; - struct batman_if *batman_if; - int ret; - uint8_t dstaddr[ETH_ALEN]; + int ret = NET_RX_DROP;

icmp_packet = (struct icmp_packet_rr *)skb->data; ethhdr = (struct ethhdr *)skb_mac_header(skb); @@ -870,62 +862,65 @@ static int recv_my_icmp_packet(struct bat_priv *bat_priv, /* add data to device queue */ if (icmp_packet->msg_type != ECHO_REQUEST) { bat_socket_receive_packet(icmp_packet, icmp_len); - return NET_RX_DROP; + goto out; }

if (!bat_priv->primary_if) - return NET_RX_DROP; + goto out;

/* answer echo request (ping) */ /* get routing information */ - spin_lock_bh(&bat_priv->orig_hash_lock); rcu_read_lock(); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, choose_orig, icmp_packet->orig)); - rcu_read_unlock(); - ret = NET_RX_DROP; + if (!orig_node) + goto unlock;

- if ((orig_node != NULL) && - (orig_node->router != NULL)) { + kref_get(&orig_node->refcount); + neigh_node = orig_node->router;

- /* don't lock while sending the packets ... we therefore - * copy the required data before sending */ - batman_if = orig_node->router->if_incoming; - memcpy(dstaddr, orig_node->router->addr, ETH_ALEN); - spin_unlock_bh(&bat_priv->orig_hash_lock); + if (!neigh_node) + goto unlock;

- /* create a copy of the skb, if needed, to modify it. */ - if (skb_cow(skb, sizeof(struct ethhdr)) < 0) - return NET_RX_DROP; + kref_get(&neigh_node->refcount); + rcu_read_unlock();

- icmp_packet = (struct icmp_packet_rr *)skb->data; - ethhdr = (struct ethhdr *)skb_mac_header(skb); + /* create a copy of the skb, if needed, to modify it. */ + if (skb_cow(skb, sizeof(struct ethhdr)) < 0) + goto out;

- memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN); - memcpy(icmp_packet->orig, - bat_priv->primary_if->net_dev->dev_addr, ETH_ALEN); - icmp_packet->msg_type = ECHO_REPLY; - icmp_packet->ttl = TTL; + icmp_packet = (struct icmp_packet_rr *)skb->data; + ethhdr = (struct ethhdr *)skb_mac_header(skb);

- send_skb_packet(skb, batman_if, dstaddr); - ret = NET_RX_SUCCESS; + memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN); + memcpy(icmp_packet->orig, + bat_priv->primary_if->net_dev->dev_addr, ETH_ALEN); + icmp_packet->msg_type = ECHO_REPLY; + icmp_packet->ttl = TTL;

- } else - spin_unlock_bh(&bat_priv->orig_hash_lock); + send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); + ret = NET_RX_SUCCESS; + goto out;

+unlock: + rcu_read_unlock(); +out: + if (neigh_node) + kref_put(&neigh_node->refcount, neigh_node_free_ref); + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); return ret; }

static int recv_icmp_ttl_exceeded(struct bat_priv *bat_priv, struct sk_buff *skb, size_t icmp_len) { - struct orig_node *orig_node; + struct orig_node *orig_node = NULL; + struct neigh_node *neigh_node = NULL; struct icmp_packet *icmp_packet; struct ethhdr *ethhdr; - struct batman_if *batman_if; - int ret; - uint8_t dstaddr[ETH_ALEN]; + int ret = NET_RX_DROP;

icmp_packet = (struct icmp_packet *)skb->data; ethhdr = (struct ethhdr *)skb_mac_header(skb); @@ -935,49 +930,53 @@ static int recv_icmp_ttl_exceeded(struct bat_priv *bat_priv, pr_debug("Warning - can't forward icmp packet from %pM to " "%pM: ttl exceeded\n", icmp_packet->orig, icmp_packet->dst); - return NET_RX_DROP; + goto out; }

if (!bat_priv->primary_if) - return NET_RX_DROP; + goto out;

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

- if ((orig_node != NULL) && - (orig_node->router != NULL)) { + kref_get(&orig_node->refcount); + neigh_node = orig_node->router;

- /* create a copy of the skb, if needed, to modify it. */ - if (skb_cow(skb, sizeof(struct ethhdr)) < 0) - return NET_RX_DROP; + kref_get(&neigh_node->refcount); + rcu_read_unlock();

- icmp_packet = (struct icmp_packet *) skb->data; - ethhdr = (struct ethhdr *)skb_mac_header(skb); + /* create a copy of the skb, if needed, to modify it. */ + if (skb_cow(skb, sizeof(struct ethhdr)) < 0) + goto out;

- memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN); - memcpy(icmp_packet->orig, - bat_priv->primary_if->net_dev->dev_addr, ETH_ALEN); - icmp_packet->msg_type = TTL_EXCEEDED; - icmp_packet->ttl = TTL; + icmp_packet = (struct icmp_packet *)skb->data; + ethhdr = (struct ethhdr *)skb_mac_header(skb);

- } else - spin_unlock_bh(&bat_priv->orig_hash_lock); + send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); + ret = NET_RX_SUCCESS; + goto out;

+unlock: + rcu_read_unlock(); +out: + if (neigh_node) + kref_put(&neigh_node->refcount, neigh_node_free_ref); + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); return ret; }

@@ -987,11 +986,10 @@ int recv_icmp_packet(struct sk_buff *skb, struct batman_if *recv_if) struct bat_priv *bat_priv = netdev_priv(recv_if->soft_iface); struct icmp_packet_rr *icmp_packet; struct ethhdr *ethhdr; - struct orig_node *orig_node; - struct batman_if *batman_if; + struct orig_node *orig_node = NULL; + struct neigh_node *neigh_node = NULL; int hdr_size = sizeof(struct icmp_packet); - int ret; - uint8_t dstaddr[ETH_ALEN]; + int ret = NET_RX_DROP;

/** * we truncate all incoming icmp packets if they don't match our size @@ -1001,21 +999,21 @@ int recv_icmp_packet(struct sk_buff *skb, struct batman_if *recv_if)

/* drop packet if it has not necessary minimum size */ if (unlikely(!pskb_may_pull(skb, hdr_size))) - return NET_RX_DROP; + goto out;

ethhdr = (struct ethhdr *)skb_mac_header(skb);

/* packet with unicast indication but broadcast recipient */ if (is_bcast(ethhdr->h_dest)) - return NET_RX_DROP; + goto out;

/* packet with broadcast sender address */ if (is_bcast(ethhdr->h_source)) - return NET_RX_DROP; + goto out;

/* not for me */ if (!is_my_mac(ethhdr->h_dest)) - return NET_RX_DROP; + goto out;

icmp_packet = (struct icmp_packet_rr *)skb->data;

@@ -1035,42 +1033,45 @@ int recv_icmp_packet(struct sk_buff *skb, struct batman_if *recv_if) if (icmp_packet->ttl < 2) return recv_icmp_ttl_exceeded(bat_priv, skb, hdr_size);

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

- if ((orig_node != NULL) && - (orig_node->router != NULL)) { + kref_get(&orig_node->refcount); + neigh_node = orig_node->router;

- /* create a copy of the skb, if needed, to modify it. */ - if (skb_cow(skb, sizeof(struct ethhdr)) < 0) - return NET_RX_DROP; + kref_get(&neigh_node->refcount); + rcu_read_unlock();

- /* decrement ttl */ - icmp_packet->ttl--; + icmp_packet = (struct icmp_packet_rr *)skb->data; + ethhdr = (struct ethhdr *)skb_mac_header(skb);

- /* route it */ - send_skb_packet(skb, batman_if, dstaddr); - ret = NET_RX_SUCCESS; + /* decrement ttl */ + icmp_packet->ttl--;

- } else - spin_unlock_bh(&bat_priv->orig_hash_lock); + /* route it */ + send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); + ret = NET_RX_SUCCESS; + goto out;

+unlock: + rcu_read_unlock(); +out: + if (neigh_node) + kref_put(&neigh_node->refcount, neigh_node_free_ref); + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); return ret; }

@@ -1200,13 +1201,11 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if, int hdr_size) { struct bat_priv *bat_priv = netdev_priv(recv_if->soft_iface); - struct orig_node *orig_node; - struct neigh_node *router; - struct batman_if *batman_if; - uint8_t dstaddr[ETH_ALEN]; + struct orig_node *orig_node = NULL; + struct neigh_node *neigh_node = NULL; struct unicast_packet *unicast_packet; struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb); - int ret; + int ret = NET_RX_DROP; struct sk_buff *new_skb;

unicast_packet = (struct unicast_packet *)skb->data; @@ -1216,55 +1215,54 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if, pr_debug("Warning - can't forward unicast packet from %pM to " "%pM: ttl exceeded\n", ethhdr->h_source, unicast_packet->dest); - return NET_RX_DROP; + goto out; }

- router = find_router(bat_priv, orig_node, recv_if); - - if (!router) { - spin_unlock_bh(&bat_priv->orig_hash_lock); - return NET_RX_DROP; - } + if (!orig_node) + goto unlock;

- /* don't lock while sending the packets ... we therefore - * copy the required data before sending */ + kref_get(&orig_node->refcount); + neigh_node = find_router(bat_priv, orig_node, recv_if);

- batman_if = router->if_incoming; - memcpy(dstaddr, router->addr, ETH_ALEN); + if (!neigh_node) + goto unlock;

- spin_unlock_bh(&bat_priv->orig_hash_lock); + kref_get(&neigh_node->refcount); + rcu_read_unlock();

/* create a copy of the skb, if needed, to modify it. */ if (skb_cow(skb, sizeof(struct ethhdr)) < 0) - return NET_RX_DROP; + goto out;

unicast_packet = (struct unicast_packet *)skb->data;

if (unicast_packet->packet_type == BAT_UNICAST && atomic_read(&bat_priv->fragmentation) && - skb->len > batman_if->net_dev->mtu) - return frag_send_skb(skb, bat_priv, batman_if, - dstaddr); + skb->len > neigh_node->if_incoming->net_dev->mtu) { + ret = frag_send_skb(skb, bat_priv, + neigh_node->if_incoming, neigh_node->addr); + goto out; + }

if (unicast_packet->packet_type == BAT_UNICAST_FRAG && - 2 * skb->len - hdr_size <= batman_if->net_dev->mtu) { + 2 * skb->len - hdr_size <= neigh_node->if_incoming->net_dev->mtu) {

ret = frag_reassemble_skb(skb, bat_priv, &new_skb);

if (ret == NET_RX_DROP) - return NET_RX_DROP; + goto out;

/* packet was buffered for late merge */ - if (!new_skb) - return NET_RX_SUCCESS; + if (!new_skb) { + ret = NET_RX_SUCCESS; + goto out; + }

skb = new_skb; unicast_packet = (struct unicast_packet *)skb->data; @@ -1274,9 +1272,18 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if, unicast_packet->ttl--;

/* route it */ - send_skb_packet(skb, batman_if, dstaddr); + send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); + ret = NET_RX_SUCCESS; + goto out;

- return NET_RX_SUCCESS; +unlock: + rcu_read_unlock(); +out: + if (neigh_node) + kref_put(&neigh_node->refcount, neigh_node_free_ref); + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); + return ret; }

int recv_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if) @@ -1335,81 +1342,82 @@ int recv_ucast_frag_packet(struct sk_buff *skb, struct batman_if *recv_if) int recv_bcast_packet(struct sk_buff *skb, struct batman_if *recv_if) { struct bat_priv *bat_priv = netdev_priv(recv_if->soft_iface); - struct orig_node *orig_node; + struct orig_node *orig_node = NULL; struct bcast_packet *bcast_packet; struct ethhdr *ethhdr; int hdr_size = sizeof(struct bcast_packet); + int ret = NET_RX_DROP; int32_t seq_diff;

/* drop packet if it has not necessary minimum size */ if (unlikely(!pskb_may_pull(skb, hdr_size))) - return NET_RX_DROP; + goto out;

ethhdr = (struct ethhdr *)skb_mac_header(skb);

/* packet with broadcast indication but unicast recipient */ if (!is_bcast(ethhdr->h_dest)) - return NET_RX_DROP; + goto out;

/* packet with broadcast sender address */ if (is_bcast(ethhdr->h_source)) - return NET_RX_DROP; + goto out;

/* ignore broadcasts sent by myself */ if (is_my_mac(ethhdr->h_source)) - return NET_RX_DROP; + goto out;

bcast_packet = (struct bcast_packet *)skb->data;

/* ignore broadcasts originated by myself */ if (is_my_mac(bcast_packet->orig)) - return NET_RX_DROP; + goto out;

if (bcast_packet->ttl < 2) - return NET_RX_DROP; + goto out;

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

- if (orig_node == NULL) { - spin_unlock_bh(&bat_priv->orig_hash_lock); - return NET_RX_DROP; - } + if (!orig_node) + goto unlock; + + kref_get(&orig_node->refcount); + rcu_read_unlock();

/* check whether the packet is a duplicate */ - if (get_bit_status(orig_node->bcast_bits, - orig_node->last_bcast_seqno, - ntohl(bcast_packet->seqno))) { - spin_unlock_bh(&bat_priv->orig_hash_lock); - return NET_RX_DROP; - } + if (get_bit_status(orig_node->bcast_bits, orig_node->last_bcast_seqno, + ntohl(bcast_packet->seqno))) + goto out;

seq_diff = ntohl(bcast_packet->seqno) - orig_node->last_bcast_seqno;

/* check whether the packet is old and the host just restarted. */ if (window_protected(bat_priv, seq_diff, - &orig_node->bcast_seqno_reset)) { - spin_unlock_bh(&bat_priv->orig_hash_lock); - return NET_RX_DROP; - } + &orig_node->bcast_seqno_reset)) + goto out;

/* mark broadcast in flood history, update window position * if required. */ if (bit_get_packet(bat_priv, orig_node->bcast_bits, seq_diff, 1)) orig_node->last_bcast_seqno = ntohl(bcast_packet->seqno);

- spin_unlock_bh(&bat_priv->orig_hash_lock); /* rebroadcast packet */ add_bcast_packet_to_list(bat_priv, skb);

/* broadcast for me */ interface_rx(recv_if->soft_iface, skb, recv_if, hdr_size); + ret = NET_RX_SUCCESS; + goto out;

- return NET_RX_SUCCESS; +unlock: + rcu_read_unlock(); +out: + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); + return ret; }

int recv_vis_packet(struct sk_buff *skb, struct batman_if *recv_if) diff --git a/batman-adv/types.h b/batman-adv/types.h index f4ce526..167781f 100644 --- a/batman-adv/types.h +++ b/batman-adv/types.h @@ -156,7 +156,6 @@ struct bat_priv { struct hashtable_t *hna_local_hash; struct hashtable_t *hna_global_hash; struct hashtable_t *vis_hash; - spinlock_t orig_hash_lock; /* protects orig_hash */ spinlock_t forw_bat_list_lock; /* protects forw_bat_list */ spinlock_t forw_bcast_list_lock; /* protects */ spinlock_t hna_lhash_lock; /* protects hna_local_hash */ diff --git a/batman-adv/unicast.c b/batman-adv/unicast.c index 9df1c40..fdfb9a2 100644 --- a/batman-adv/unicast.c +++ b/batman-adv/unicast.c @@ -178,17 +178,16 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, (struct unicast_frag_packet *)skb->data;

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

- if (!orig_node) { - pr_debug("couldn't find originator in orig_hash\n"); - goto out; - } + kref_get(&orig_node->refcount); + rcu_read_unlock();

orig_node->last_frag_packet = jiffies;

@@ -212,9 +211,14 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, /* if not, merge failed */ if (*new_skb) ret = NET_RX_SUCCESS; -out: - spin_unlock_bh(&bat_priv->orig_hash_lock);

+ goto out; + +unlock: + rcu_read_unlock(); +out: + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); return ret; }

@@ -277,47 +281,53 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv) struct ethhdr *ethhdr = (struct ethhdr *)skb->data; struct unicast_packet *unicast_packet; struct orig_node *orig_node; - struct batman_if *batman_if; - struct neigh_node *router; + struct neigh_node *neigh_node; int data_len = skb->len; - uint8_t dstaddr[6]; - - spin_lock_bh(&bat_priv->orig_hash_lock); + int ret = 1;

/* get routing information */ - if (is_bcast(ethhdr->h_dest) || is_mcast(ethhdr->h_dest)) + if (is_bcast(ethhdr->h_dest) || is_mcast(ethhdr->h_dest)) { orig_node = (struct orig_node *)gw_get_selected(bat_priv); - else { + if (!orig_node) + goto trans_search; + + kref_get(&orig_node->refcount); + goto find_router; + } else { rcu_read_lock(); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, choose_orig, ethhdr->h_dest)); - rcu_read_lock(); + if (!orig_node) { + rcu_read_unlock(); + goto trans_search; + } + + kref_get(&orig_node->refcount); + rcu_read_unlock(); + goto find_router; }

+trans_search: /* check for hna host */ - if (!orig_node) - orig_node = transtable_search(bat_priv, ethhdr->h_dest); + orig_node = transtable_search(bat_priv, ethhdr->h_dest);

- router = find_router(bat_priv, orig_node, NULL); +find_router: + rcu_read_lock(); + neigh_node = find_router(bat_priv, orig_node, NULL);

- if (!router) + if (!neigh_node) goto unlock;

- /* don't lock while sending the packets ... we therefore - * copy the required data before sending */ - - batman_if = router->if_incoming; - memcpy(dstaddr, router->addr, ETH_ALEN); - - spin_unlock_bh(&bat_priv->orig_hash_lock); + kref_get(&neigh_node->refcount); + rcu_read_unlock();

- if (batman_if->if_status != IF_ACTIVE) - goto dropped; + if (neigh_node->if_incoming->if_status != IF_ACTIVE) + goto out;

if (my_skb_head_push(skb, sizeof(struct unicast_packet)) < 0) - goto dropped; + goto out;

unicast_packet = (struct unicast_packet *)skb->data;

@@ -331,18 +341,26 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv)

if (atomic_read(&bat_priv->fragmentation) && data_len + sizeof(struct unicast_packet) > - batman_if->net_dev->mtu) { + neigh_node->if_incoming->net_dev->mtu) { /* send frag skb decreases ttl */ unicast_packet->ttl++; - return frag_send_skb(skb, bat_priv, batman_if, - dstaddr); + ret = frag_send_skb(skb, bat_priv, + neigh_node->if_incoming, neigh_node->addr); + goto out; } - send_skb_packet(skb, batman_if, dstaddr); - return 0; + + send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); + ret = 0; + goto out;

unlock: - spin_unlock_bh(&bat_priv->orig_hash_lock); -dropped: - kfree_skb(skb); - return 1; + rcu_read_unlock(); +out: + if (neigh_node) + kref_put(&neigh_node->refcount, neigh_node_free_ref); + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); + if (ret == 1) + kfree_skb(skb); + return ret; } diff --git a/batman-adv/vis.c b/batman-adv/vis.c index 69efdf4..0d35497 100644 --- a/batman-adv/vis.c +++ b/batman-adv/vis.c @@ -582,7 +582,6 @@ static int generate_vis_packet(struct bat_priv *bat_priv) info->first_seen = jiffies; packet->vis_type = atomic_read(&bat_priv->vis_mode);

- spin_lock_bh(&bat_priv->orig_hash_lock); memcpy(packet->target_orig, broadcast_addr, ETH_ALEN); packet->ttl = TTL; packet->seqno = htonl(ntohl(packet->seqno) + 1); @@ -592,10 +591,8 @@ static int generate_vis_packet(struct bat_priv *bat_priv) if (packet->vis_type == VIS_TYPE_CLIENT_UPDATE) { best_tq = find_best_vis_server(bat_priv, info);

- if (best_tq < 0) { - spin_unlock_bh(&bat_priv->orig_hash_lock); + if (best_tq < 0) return -1; - } }

for (i = 0; i < hash->size; i++) { @@ -635,16 +632,12 @@ static int generate_vis_packet(struct bat_priv *bat_priv) entry->quality = neigh_node->tq_avg; packet->entries++;

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

- spin_unlock_bh(&bat_priv->orig_hash_lock); - spin_lock_bh(&bat_priv->hna_lhash_lock); while (hash_iterate(bat_priv->hna_local_hash, &hashit_local)) { bucket = hlist_entry(hashit_local.walk, struct element_t, @@ -665,6 +658,10 @@ static int generate_vis_packet(struct bat_priv *bat_priv)

spin_unlock_bh(&bat_priv->hna_lhash_lock); return 0; + +unlock: + rcu_read_unlock(); + return 0; }

/* free old vis packets. Must be called with this vis_hash_lock @@ -707,7 +704,6 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, int i, ret;

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

/* send to all routers in range. */ @@ -739,54 +735,58 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, memcpy(packet->target_orig, orig_node->orig, ETH_ALEN); batman_if = orig_node->router->if_incoming; memcpy(dstaddr, orig_node->router->addr, ETH_ALEN); - spin_unlock_bh(&bat_priv->orig_hash_lock);

skb = skb_clone(info->skb_packet, GFP_ATOMIC); if (skb) send_skb_packet(skb, batman_if, dstaddr);

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

static void unicast_vis_packet(struct bat_priv *bat_priv, struct vis_info *info) { struct orig_node *orig_node; + struct neigh_node *neigh_node = NULL; struct sk_buff *skb; struct vis_packet *packet; - struct batman_if *batman_if; - uint8_t dstaddr[ETH_ALEN];

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

- if ((!orig_node) || (!orig_node->router)) - goto out; + if (!orig_node) + goto unlock; + + kref_get(&orig_node->refcount); + neigh_node = orig_node->router; + + if (!neigh_node) + goto unlock;

skb = skb_clone(info->skb_packet, GFP_ATOMIC); if (skb) - send_skb_packet(skb, batman_if, dstaddr); + send_skb_packet(skb, neigh_node->if_incoming, + neigh_node->addr);

- return; + goto out;

+unlock: + rcu_read_unlock(); out: - spin_unlock_bh(&bat_priv->orig_hash_lock); + if (neigh_node) + kref_put(&neigh_node->refcount, neigh_node_free_ref); + if (orig_node) + kref_put(&orig_node->refcount, orig_node_free_ref); + return; }

/* only send one vis packet. called from send_vis_packets() */

-- 1.7.2.3

5118

Age (days ago)

5121

Last active (days ago)

b.a.t.m.a.n@lists.open-mesh.org

10 comments

2 participants

tags (0)

participants (2)

Linus Lüssing
Marek Lindner