[B.A.T.M.A.N.] [PATCH] Removing the big batman lock

The orig_hash_lock locks big sections of the batman-adv code base, which might lead to unneccesary performance degradation at some points.

Therefore this patch moves the locking from the whole originator hash table to individual orig nodes, introducing a reference count based system to identify whether a node is still in use or can be free()d.

To summarize the changes: * when iterating, the hash is only locked while an item is picked from the hash. Access to the orig_nodes themselves is no longer protected by orig_hash_lock. * Each orig_node is referenced when it is used or referenced (e.g. as neighbor), and freed when there are no references left. This makes it neccesary to carefully reference and unreference nodes. * orig_nodes receive an individual spin lock to protect access to their data.

I did some testing, including loading, unloading, killing individual nodes etc, which seems to be clean so far. However there might be more race conditions introduced by this large patch, and i'm therefore requesting a careful review before committing.

Signed-off-by: Simon Wunderlich simon.wunderlich@s2003.tu-chemnitz.de ---

Index: batman-adv-kernelland/vis.c =================================================================== --- batman-adv-kernelland/vis.c (revision 1489) +++ batman-adv-kernelland/vis.c (working copy) @@ -26,6 +26,7 @@ #include "soft-interface.h" #include "hard-interface.h" #include "hash.h" +#include "originator.h" #include "compat.h"

struct hashtable_t *vis_hash; @@ -262,16 +263,16 @@

/* Walk the originators and find the VIS server with the best tq. Set the packet * address to its address and return the best_tq. - * - * Must be called with the originator hash locked */ + */ static int find_best_vis_server(struct vis_info *info) { struct hash_it_t *hashit = NULL; - struct orig_node *orig_node; + struct orig_node *orig_node = NULL; int best_tq = -1;

- while (NULL != (hashit = hash_iterate(orig_hash, hashit))) { - orig_node = hashit->bucket->data; + while (NULL != (orig_node = orig_hash_iterate(&hashit, orig_node))) { + + spin_lock(&orig_node->lock); if ((orig_node != NULL) && (orig_node->router != NULL) && (orig_node->flags & VIS_SERVER) && @@ -280,6 +281,7 @@ memcpy(info->packet.target_orig, orig_node->orig, ETH_ALEN); } + spin_unlock(&orig_node->lock); } return best_tq; } @@ -298,7 +300,7 @@ static int generate_vis_packet(void) { struct hash_it_t *hashit = NULL; - struct orig_node *orig_node; + struct orig_node *orig_node = NULL; struct vis_info *info = (struct vis_info *)my_vis_info; struct vis_info_entry *entry, *entry_array; struct hna_local_entry *hna_local_entry; @@ -307,7 +309,6 @@

info->first_seen = jiffies;

- spin_lock(&orig_hash_lock); memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN); info->packet.ttl = TTL; info->packet.seqno++; @@ -316,17 +317,17 @@ if (!is_vis_server_locked()) { best_tq = find_best_vis_server(info); if (best_tq < 0) { - spin_unlock(&orig_hash_lock); return -1; } } - hashit = NULL;

entry_array = (struct vis_info_entry *) ((char *)info + sizeof(struct vis_info));

- while (NULL != (hashit = hash_iterate(orig_hash, hashit))) { - orig_node = hashit->bucket->data; + while (NULL != (orig_node = orig_hash_iterate(&hashit, orig_node))) { + + spin_lock(&orig_node->lock); + if (orig_node->router != NULL && compare_orig(orig_node->router->addr, orig_node->orig) && orig_node->batman_if @@ -340,15 +341,16 @@ entry->quality = orig_node->router->tq_avg; info->packet.entries++;

+ /* TODO: this is is a possible memory leak, + * hashit should be freed somewhere. */ if (vis_packet_full(info)) { - spin_unlock(&orig_hash_lock); + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); return 0; } } }

- spin_unlock(&orig_hash_lock); - hashit = NULL; spin_lock_irqsave(&hna_local_hash_lock, flags); while (NULL != (hashit = hash_iterate(hna_local_hash, hashit))) { @@ -388,14 +390,12 @@ static void broadcast_vis_packet(struct vis_info *info, int packet_length) { struct hash_it_t *hashit = NULL; - struct orig_node *orig_node; + struct orig_node *orig_node = NULL;

- spin_lock(&orig_hash_lock); - /* send to all routers in range. */ - while (NULL != (hashit = hash_iterate(orig_hash, hashit))) { - orig_node = hashit->bucket->data; + while (NULL != (orig_node = orig_hash_iterate(&hashit, orig_node))) {

+ spin_lock(&orig_node->lock); /* if it's a vis server and reachable, send it. */ if (orig_node && (orig_node->flags & VIS_SERVER) && @@ -415,27 +415,28 @@ orig_node->batman_if, orig_node->router->addr); } + spin_unlock(&orig_node->lock); } memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN); - spin_unlock(&orig_hash_lock); }

static void unicast_vis_packet(struct vis_info *info, int packet_length) { struct orig_node *orig_node;

- spin_lock(&orig_hash_lock); - orig_node = ((struct orig_node *) - hash_find(orig_hash, info->packet.target_orig)); + orig_node = orig_find(info->packet.target_orig);

- if ((orig_node != NULL) && - (orig_node->batman_if != NULL) && - (orig_node->router != NULL)) { - send_raw_packet((unsigned char *) &info->packet, packet_length, + if (orig_node) { + spin_lock(&orig_node->lock); + if ((orig_node->batman_if != NULL) && + (orig_node->router != NULL)) { + send_raw_packet((unsigned char *) &info->packet, packet_length, orig_node->batman_if, orig_node->router->addr); + } + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); } - spin_unlock(&orig_hash_lock); }

/* only send one vis packet. called from send_vis_packets() */ Index: batman-adv-kernelland/Makefile.kbuild =================================================================== --- batman-adv-kernelland/Makefile.kbuild (revision 1489) +++ batman-adv-kernelland/Makefile.kbuild (working copy) @@ -25,7 +25,7 @@ -include $(TOPDIR)/Rules.make endif

-# EXTRA_CFLAGS += -DCONFIG_BATMAN_DEBUG +EXTRA_CFLAGS += -DCONFIG_BATMAN_DEBUG

ifneq ($(REVISION),) EXTRA_CFLAGS += -DREVISION_VERSION="r$(REVISION)" Index: batman-adv-kernelland/types.h =================================================================== --- batman-adv-kernelland/types.h (revision 1489) +++ batman-adv-kernelland/types.h (working copy) @@ -62,6 +62,8 @@ int16_t hna_buff_len; uint16_t last_real_seqno; /* last and best known squence number */ uint8_t last_ttl; /* ttl of last received packet */ + spinlock_t lock; + atomic_t refcnt; TYPE_OF_WORD bcast_bits[NUM_WORDS]; uint16_t last_bcast_seqno; /* last broadcast sequence number received by this host */ struct list_head neigh_list; Index: batman-adv-kernelland/translation-table.c =================================================================== --- batman-adv-kernelland/translation-table.c (revision 1489) +++ batman-adv-kernelland/translation-table.c (working copy) @@ -24,6 +24,7 @@ #include "soft-interface.h" #include "types.h" #include "hash.h" +#include "originator.h" #include "compat.h"

struct hashtable_t *hna_local_hash; @@ -257,6 +258,9 @@ return 1; }

+ +/* adds an HNA entry to the global address table. + * orig_node's spinlock should be hold from outside */ void hna_global_add_orig(struct orig_node *orig_node, unsigned char *hna_buff, int hna_buff_len) { @@ -299,7 +303,7 @@

}

- hna_global_entry->orig_node = orig_node; + hna_global_entry->orig_node = orig_reference(orig_node); spin_unlock_irqrestore(&hna_global_hash_lock, flags);

/* remove address from local hash if present */ @@ -391,6 +395,8 @@ hna_str, orig_str, message);

hash_remove(hna_global_hash, hna_global_entry->addr); + orig_unreference(hna_global_entry->orig_node); + kfree(hna_global_entry); }

@@ -452,5 +458,5 @@ if (hna_global_entry == NULL) return NULL;

- return hna_global_entry->orig_node; + return orig_reference(hna_global_entry->orig_node); } Index: batman-adv-kernelland/send.c =================================================================== --- batman-adv-kernelland/send.c (revision 1489) +++ batman-adv-kernelland/send.c (working copy) @@ -294,6 +294,7 @@ batman_packet->ttl--; memcpy(batman_packet->prev_sender, ethhdr->h_source, ETH_ALEN);

+ spin_lock(&orig_node->lock); /* rebroadcast tq of our best ranking neighbor to ensure the rebroadcast * of our best tq value */ if ((orig_node->router) && (orig_node->router->tq_avg != 0)) { @@ -308,6 +309,7 @@

tq_avg = orig_node->router->tq_avg; } + spin_unlock(&orig_node->lock);

/* apply hop penalty */ batman_packet->tq = hop_penalty(batman_packet->tq); Index: batman-adv-kernelland/device.c =================================================================== --- batman-adv-kernelland/device.c (revision 1489) +++ batman-adv-kernelland/device.c (working copy) @@ -24,6 +24,7 @@ #include "send.h" #include "types.h" #include "hash.h" +#include "originator.h"

#include "compat.h"

@@ -205,6 +206,7 @@ struct icmp_packet icmp_packet; struct orig_node *orig_node; struct batman_if *batman_if; + uint8_t router_addr[ETH_ALEN];

if (len < sizeof(struct icmp_packet)) { printk(KERN_DEBUG "batman-adv:Error - can't send packet from char device: invalid packet size\n"); @@ -239,15 +241,20 @@ if (atomic_read(&module_state) != MODULE_ACTIVE) goto dst_unreach;

- spin_lock(&orig_hash_lock); - orig_node = ((struct orig_node *)hash_find(orig_hash, icmp_packet.dst)); + orig_node = orig_find(icmp_packet.dst);

if (!orig_node) - goto unlock; + goto dst_unreach;

+ spin_lock(&orig_node->lock); + if (!orig_node->router) goto unlock;

+ memcpy(router_addr, + orig_node->router->addr, + ETH_ALEN); + batman_if = orig_node->batman_if;

if (!batman_if) @@ -257,15 +264,18 @@ batman_if->net_dev->dev_addr, ETH_ALEN);

+ spin_unlock(&orig_node->lock); + orig_unreference(orig_node); + send_raw_packet((unsigned char *)&icmp_packet, sizeof(struct icmp_packet), - batman_if, orig_node->router->addr); + batman_if, router_addr);

- spin_unlock(&orig_hash_lock); goto out;

unlock: - spin_unlock(&orig_hash_lock); + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); dst_unreach: icmp_packet.msg_type = DESTINATION_UNREACHABLE; bat_device_add_packet(device_client, &icmp_packet); Index: batman-adv-kernelland/proc.c =================================================================== --- batman-adv-kernelland/proc.c (revision 1489) +++ batman-adv-kernelland/proc.c (working copy) @@ -28,6 +28,7 @@ #include "hash.h" #include "vis.h" #include "compat.h" +#include "originator.h"

static uint8_t vis_format = DOT_DRAW;

@@ -187,7 +188,7 @@ static int proc_originators_read(struct seq_file *seq, void *offset) { struct hash_it_t *hashit = NULL; - struct orig_node *orig_node; + struct orig_node *orig_node = NULL; struct neigh_node *neigh_node; int batman_count = 0; char orig_str[ETH_STR_LEN], router_str[ETH_STR_LEN]; @@ -213,11 +214,10 @@ ((struct batman_if *)if_list.next)->addr_str);

rcu_read_unlock(); - spin_lock(&orig_hash_lock);

- while (NULL != (hashit = hash_iterate(orig_hash, hashit))) { + while (NULL != (orig_node = orig_hash_iterate(&hashit, orig_node))) {

- orig_node = hashit->bucket->data; + spin_lock(&orig_node->lock);

if (!orig_node->router) continue; @@ -241,11 +241,10 @@ }

seq_printf(seq, "\n"); + spin_unlock(&orig_node->lock);

}

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

Index: batman-adv-kernelland/soft-interface.c =================================================================== --- batman-adv-kernelland/soft-interface.c (revision 1489) +++ batman-adv-kernelland/soft-interface.c (working copy) @@ -26,6 +26,7 @@ #include "translation-table.h" #include "types.h" #include "hash.h" +#include "originator.h" #include <linux/ethtool.h> #include <linux/etherdevice.h> #include "compat.h" @@ -34,7 +35,6 @@ * broadcast storms */ static int32_t skb_packets; static int32_t skb_bad_packets; -static int32_t lock_dropped;

unsigned char mainIfAddr[ETH_ALEN]; static unsigned char mainIfAddr_default[ETH_ALEN]; @@ -205,60 +205,55 @@ /* unicast packet */ } else {

- /* simply spin_lock()ing can deadlock when the lock is already - * hold. */ - /* TODO: defer the work in a working queue instead of - * dropping */ - if (!spin_trylock(&orig_hash_lock)) { - lock_dropped++; - printk(KERN_WARNING "batman-adv:%d packets dropped because lock was hold\n", lock_dropped); - goto dropped; - } - /* get routing information */ - orig_node = ((struct orig_node *)hash_find(orig_hash, - ethhdr->h_dest)); + orig_node = orig_find(ethhdr->h_dest);

/* check for hna host */ if (!orig_node) orig_node = transtable_search(ethhdr->h_dest);

- if ((orig_node) && - (orig_node->batman_if) && - (orig_node->router)) { - if (my_skb_push(skb, sizeof(struct unicast_packet)) < 0) - goto unlock; + if (!orig_node) + goto dropped;

- unicast_packet = (struct unicast_packet *)skb->data; + spin_lock(&orig_node->lock);

- unicast_packet->version = COMPAT_VERSION; - /* batman packet type: unicast */ - unicast_packet->packet_type = BAT_UNICAST; - /* set unicast ttl */ - unicast_packet->ttl = TTL; - /* copy the destination for faster routing */ - memcpy(unicast_packet->dest, orig_node->orig, ETH_ALEN); + if (!((orig_node->batman_if) && + (orig_node->router))) + goto unlock;

- /* net_dev won't be available when not active */ - if (orig_node->batman_if->if_active != IF_ACTIVE) - goto unlock; + if (my_skb_push(skb, sizeof(struct unicast_packet)) < 0) + goto unlock;

- send_raw_packet(skb->data, skb->len, - orig_node->batman_if, - orig_node->router->addr); - } else { + unicast_packet = (struct unicast_packet *)skb->data; + + unicast_packet->version = COMPAT_VERSION; + /* batman packet type: unicast */ + unicast_packet->packet_type = BAT_UNICAST; + /* set unicast ttl */ + unicast_packet->ttl = TTL; + /* copy the destination for faster routing */ + memcpy(unicast_packet->dest, orig_node->orig, ETH_ALEN); + + /* net_dev won't be available when not active */ + if (orig_node->batman_if->if_active != IF_ACTIVE) goto unlock; - } + + send_raw_packet(skb->data, skb->len, + orig_node->batman_if, + orig_node->router->addr);

- spin_unlock(&orig_hash_lock); + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); }

priv->stats.tx_packets++; priv->stats.tx_bytes += data_len; goto end;

+ unlock: - spin_unlock(&orig_hash_lock); + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); dropped: priv->stats.tx_dropped++; end: Index: batman-adv-kernelland/hard-interface.c =================================================================== --- batman-adv-kernelland/hard-interface.c (revision 1489) +++ batman-adv-kernelland/hard-interface.c (working copy) @@ -26,6 +26,7 @@ #include "translation-table.h" #include "routing.h" #include "hash.h" +#include "originator.h" #include "compat.h"

#define MIN(x, y) ((x) < (y) ? (x) : (y)) @@ -317,8 +318,9 @@ { struct batman_if *batman_if; struct batman_packet *batman_packet; - struct orig_node *orig_node; + struct orig_node *orig_node = NULL; struct hash_it_t *hashit = NULL; + int ret;

batman_if = kmalloc(sizeof(struct batman_if), GFP_KERNEL);

@@ -375,18 +377,18 @@

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

- while (NULL != (hashit = hash_iterate(orig_hash, hashit))) { - orig_node = hashit->bucket->data; - if (resize_orig(orig_node, if_num) == -1) { - spin_unlock(&orig_hash_lock); - goto out; - } + ret = 0; + while (NULL != (orig_node = orig_hash_iterate(&hashit, orig_node))) { + ret |= resize_orig(orig_node, if_num); }

- spin_unlock(&orig_hash_lock); + if (ret) { + printk(KERN_ERR "batman-adv:Resizing originators for %s failed.\n", batman_if->dev); + goto out; + }

+ if (!hardif_is_interface_up(batman_if->dev)) printk(KERN_ERR "batman-adv:Not using interface %s (retrying later): interface not active\n", batman_if->dev); else Index: batman-adv-kernelland/originator.c =================================================================== --- batman-adv-kernelland/originator.c (revision 1489) +++ batman-adv-kernelland/originator.c (working copy) @@ -19,17 +19,86 @@ * */

-/* increase the reference counter for this originator */ - #include "main.h" +#include "hash.h" #include "originator.h" -#include "hash.h" #include "translation-table.h" #include "routing.h"

+DEFINE_SPINLOCK(orig_hash_lock); static DECLARE_DELAYED_WORK(purge_orig_wq, purge_orig);

+/* increase the reference counter for this originator */ + +struct orig_node *orig_reference(struct orig_node *orig_node) +{ + if (orig_node == NULL) { + printk(KERN_ERR "batman-adv: tried to reference a NULL orig\n"); + dump_stack(); + return NULL; + } else if (atomic_read(&orig_node->refcnt) < 1) { + printk(KERN_DEBUG "batman-adv: trying to access a vanished node with refcnt %d\n", atomic_read(&orig_node->refcnt)); + return NULL; + } else { + atomic_inc(&orig_node->refcnt); + + return orig_node; + } +} + +static void __free_orig_node(void *data) +{ + struct orig_node *orig_node = (struct orig_node *)data; + + hna_global_del_orig(orig_node, "__free_orig_node"); + + kfree(orig_node->bcast_own); + kfree(orig_node->bcast_own_sum); + kfree(orig_node); +} + + +/* decrease the reference counter for this originator */ +struct orig_node *orig_unreference(struct orig_node *orig_node) +{ + char orig_str[ETH_STR_LEN]; + + if (orig_node == NULL) { + printk(KERN_ERR "batman-adv: tried to reference a NULL orig\n"); + dump_stack(); + return NULL; + } else if (atomic_read(&orig_node->refcnt) < 1) { + printk(KERN_DEBUG "batman-adv: trying to access a vanished node with refcnt %d\n", atomic_read(&orig_node->refcnt)); + return NULL; + } else { + + if (atomic_dec_and_test(&orig_node->refcnt)) { + addr_to_string(orig_str, orig_node->orig); + bat_dbg(DBG_BATMAN,"%s:decreasing refcnt of orig %s to %d, time to free\n", __func__, orig_str, atomic_read(&orig_node->refcnt)); + __free_orig_node(orig_node); + } + return orig_node; + } +} + + +/* find an orig node and increase the reference counter */ + +struct orig_node *orig_find(char *mac) +{ + struct orig_node *orig_node; + + spin_lock(&orig_hash_lock); + orig_node = ((struct orig_node *)hash_find(orig_hash, mac)); + spin_unlock(&orig_hash_lock); + + if (orig_node) + orig_node = orig_reference(orig_node); + + return orig_node; +} + static void start_purge_timer(void) { queue_delayed_work(bat_event_workqueue, &purge_orig_wq, 1 * HZ); @@ -64,6 +133,7 @@

spin_lock(&orig_hash_lock); hash_delete(orig_hash, free_orig_node); + orig_hash = NULL; spin_unlock(&orig_hash_lock); } @@ -81,7 +151,7 @@ INIT_LIST_HEAD(&neigh_node->list);

memcpy(neigh_node->addr, neigh, ETH_ALEN); - neigh_node->orig_node = orig_neigh_node; + neigh_node->orig_node = orig_reference(orig_neigh_node); neigh_node->if_incoming = if_incoming;

list_add_tail(&neigh_node->list, &orig_node->neigh_list); @@ -90,39 +160,35 @@

void free_orig_node(void *data) { + struct orig_node *orig_node = (struct orig_node *) data; struct list_head *list_pos, *list_pos_tmp; struct neigh_node *neigh_node; - struct orig_node *orig_node = (struct orig_node *)data;

+ hna_global_del_orig(orig_node, "originator timeout"); + + spin_lock(&orig_node->lock); /* for all neighbours 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);

+ orig_unreference(neigh_node->orig_node); + list_del(list_pos); kfree(neigh_node); } + orig_node->router = NULL; + spin_unlock(&orig_node->lock);

- hna_global_del_orig(orig_node, "originator timed out"); - - kfree(orig_node->bcast_own); - kfree(orig_node->bcast_own_sum); - kfree(orig_node); + orig_unreference(orig_node); }

-/* this function finds or creates an originator entry for the given - * address if it does not exits */ -struct orig_node *get_orig_node(uint8_t *addr) +struct orig_node *orig_node_create(uint8_t *addr) { struct orig_node *orig_node; struct hashtable_t *swaphash; char orig_str[ETH_STR_LEN]; int size;

- orig_node = ((struct orig_node *)hash_find(orig_hash, addr)); - - if (orig_node != NULL) - return orig_node; - addr_to_string(orig_str, addr); bat_dbg(DBG_BATMAN, "Creating new originator: %s \n", orig_str);

@@ -131,9 +197,12 @@ INIT_LIST_HEAD(&orig_node->neigh_list);

memcpy(orig_node->orig, addr, ETH_ALEN); + + orig_node->lock = __SPIN_LOCK_UNLOCKED(device_client->lock); orig_node->router = NULL; orig_node->batman_if = NULL; orig_node->hna_buff = NULL; + atomic_set(&orig_node->refcnt, 1);

size = num_ifs * sizeof(TYPE_OF_WORD) * NUM_WORDS;

@@ -155,7 +224,24 @@ else orig_hash = swaphash; } + return orig_node; +}

+/* this function finds or creates an originator entry for the given + * address if it does not exits */ +struct orig_node *get_orig_node(uint8_t *addr) +{ + struct orig_node *orig_node; + + orig_node = orig_find(addr); + + if (orig_node) + return orig_node; + + orig_node = orig_node_create(addr); + if (orig_node) + orig_node = orig_reference(orig_node_create(addr)); + return orig_node; }

@@ -164,6 +250,7 @@ { struct list_head *list_pos, *list_pos_tmp; char neigh_str[ETH_STR_LEN]; + char orig_str[ETH_STR_LEN]; struct neigh_node *neigh_node; bool neigh_purged = false;

@@ -178,10 +265,14 @@ (neigh_node->last_valid + ((PURGE_TIMEOUT * HZ) / 1000)))) {

+ addr_to_string(orig_str, orig_node->orig); addr_to_string(neigh_str, neigh_node->addr); bat_dbg(DBG_BATMAN, "Neighbour timeout: originator %s, neighbour: %s, last_valid %lu\n", orig_str, neigh_str, (neigh_node->last_valid / HZ)); + neigh_purged = true; + if (neigh_node == orig_node->router) + orig_node->router = NULL;

- neigh_purged = true; + orig_unreference(neigh_node->orig_node); list_del(list_pos); kfree(neigh_node); } else { @@ -201,10 +292,10 @@

addr_to_string(orig_str, orig_node->orig);

+ spin_lock(&orig_node->lock); if (time_after(jiffies, (orig_node->last_valid + ((2 * PURGE_TIMEOUT * HZ) / 1000)))) { - bat_dbg(DBG_BATMAN, "Originator timeout: originator %s, last_valid %lu\n", orig_str, (orig_node->last_valid / HZ)); @@ -215,28 +306,48 @@ orig_node->hna_buff, orig_node->hna_buff_len); } + spin_unlock(&orig_node->lock); return false; }

void purge_orig(struct work_struct *work) { struct hash_it_t *hashit = NULL; - struct orig_node *orig_node; + struct orig_node *orig_node = NULL;

- spin_lock(&orig_hash_lock);

/* for all origins... */ - while (NULL != (hashit = hash_iterate(orig_hash, hashit))) { - orig_node = hashit->bucket->data; + while (NULL != (orig_node = orig_hash_iterate(&hashit, orig_node))) { + if (purge_orig_node(orig_node)) { hash_remove_bucket(orig_hash, hashit); free_orig_node(orig_node); } }

- spin_unlock(&orig_hash_lock); - start_purge_timer(); }

+/* iterates over the originator hash, automatically referencing acquired orig_nodes. + * It also unreferences the last node if it is given. + * + * The calling function does not have to handle the orig_hash locks as this function + * does it. */ +struct orig_node *orig_hash_iterate(struct hash_it_t **hashit, struct orig_node *orig_node) +{ + if (orig_node) + orig_unreference(orig_node); + + spin_lock(&orig_hash_lock); + + *hashit = hash_iterate(orig_hash, *hashit); + if (*hashit) + orig_node = orig_reference((*hashit)->bucket->data); + else + orig_node = NULL; + + spin_unlock(&orig_hash_lock); + + return orig_node; +} Index: batman-adv-kernelland/originator.h =================================================================== --- batman-adv-kernelland/originator.h (revision 1489) +++ batman-adv-kernelland/originator.h (working copy) @@ -19,6 +19,8 @@ * */

+extern spinlock_t orig_hash_lock; + int originator_init(void); void free_orig_node(void *data); void originator_free(void); @@ -28,4 +30,8 @@ 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 orig_node *orig_reference(struct orig_node *orig); +struct orig_node *orig_unreference(struct orig_node *orig); +struct orig_node *orig_find(char *mac); +struct orig_node *orig_hash_iterate(struct hash_it_t **hashit, struct orig_node *orig_node);

Index: batman-adv-kernelland/main.c =================================================================== --- batman-adv-kernelland/main.c (revision 1489) +++ batman-adv-kernelland/main.c (working copy) @@ -23,7 +23,6 @@ #include "proc.h" #include "routing.h" #include "send.h" -#include "originator.h" #include "soft-interface.h" #include "device.h" #include "translation-table.h" @@ -31,6 +30,7 @@ #include "types.h" #include "vis.h" #include "hash.h" +#include "originator.h" #include "compat.h"

struct list_head if_list; @@ -38,7 +38,6 @@ struct hlist_head forw_bcast_list; struct hashtable_t *orig_hash;

-DEFINE_SPINLOCK(orig_hash_lock); DEFINE_SPINLOCK(forw_bat_list_lock); DEFINE_SPINLOCK(forw_bcast_list_lock);

Index: batman-adv-kernelland/routing.c =================================================================== --- batman-adv-kernelland/routing.c (revision 1489) +++ batman-adv-kernelland/routing.c (working copy) @@ -38,24 +38,21 @@

static atomic_t data_ready_cond; atomic_t exit_cond; + void slide_own_bcast_window(struct batman_if *batman_if) { struct hash_it_t *hashit = NULL; - struct orig_node *orig_node; + struct orig_node *orig_node = NULL; TYPE_OF_WORD *word;

- spin_lock(&orig_hash_lock); + while (NULL != (orig_node = orig_hash_iterate(&hashit, orig_node))) {

- while (NULL != (hashit = hash_iterate(orig_hash, hashit))) { - orig_node = hashit->bucket->data; word = &(orig_node->bcast_own[batman_if->if_num * NUM_WORDS]);

bit_get_packet(word, 1, 0); orig_node->bcast_own_sum[batman_if->if_num] = bit_packet_count(word); } - - spin_unlock(&orig_hash_lock); }

static void update_HNA(struct orig_node *orig_node, @@ -131,6 +128,8 @@ update_HNA(orig_node, hna_buff, hna_buff_len); }

+/* TODO: rename and comment this function */ +/* TODO: review referencing here */ static int isBidirectionalNeigh(struct orig_node *orig_node, struct orig_node *orig_neigh_node, struct batman_packet *batman_packet, @@ -144,25 +143,29 @@ addr_to_string(neigh_str, orig_neigh_node->orig);

if (orig_node == orig_neigh_node) { + spin_lock(&orig_node->lock); list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {

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

if (neigh_node == NULL) neigh_node = create_neighbor(orig_node, - orig_neigh_node, - orig_neigh_node->orig, + orig_node, + orig_node->orig, if_incoming);

neigh_node->last_valid = jiffies; + spin_unlock(&orig_node->lock); } else { /* find packet count of corresponding one hop neighbor */ + spin_lock(&orig_neigh_node->lock); + list_for_each_entry(tmp_neigh_node, &orig_neigh_node->neigh_list, list) {

@@ -177,6 +180,7 @@ orig_neigh_node, orig_neigh_node->orig, if_incoming); + spin_unlock(&orig_neigh_node->lock); }

orig_node->last_valid = jiffies; @@ -239,6 +243,7 @@ unsigned char *hna_buff, int hna_buff_len, char is_duplicate) { + struct orig_node *source_orig_node; struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL; int tmp_hna_buff_len;

@@ -260,11 +265,13 @@ ring_buffer_avg(tmp_neigh_node->tq_recv); }

- if (neigh_node == NULL) + if (neigh_node == NULL) { + source_orig_node = get_orig_node(ethhdr->h_source); neigh_node = create_neighbor(orig_node, - get_orig_node(ethhdr->h_source), + source_orig_node, ethhdr->h_source, if_incoming); - else + orig_unreference(source_orig_node); + } else bat_dbg(DBG_BATMAN, "Updating existing last-hop neighbour of originator\n");

@@ -323,6 +330,7 @@ if (orig_node == NULL) return 0;

+ spin_lock(&orig_node->lock); list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {

if (!is_duplicate) @@ -346,10 +354,13 @@ orig_node->last_real_seqno, batman_packet->seqno); orig_node->last_real_seqno = batman_packet->seqno; } + spin_unlock(&orig_node->lock); + orig_unreference(orig_node);

return is_duplicate; }

+/* receive and handle one batman packet */ void receive_bat_packet(struct ethhdr *ethhdr, struct batman_packet *batman_packet, unsigned char *hna_buff, @@ -448,10 +459,13 @@ * come via the corresponding interface */ /* if received seqno equals last send seqno save new * seqno for bidirectional check */ + + spin_lock(&orig_neigh_node->lock); if (has_directlink_flag && compare_orig(if_incoming->net_dev->dev_addr, batman_packet->orig) && (batman_packet->seqno - if_incoming_seqno + 2 == 0)) { + offset = if_incoming->if_num * NUM_WORDS; word = &(orig_neigh_node->bcast_own[offset]); bit_mark(word, 0); @@ -459,6 +473,9 @@ bit_packet_count(word); }

+ spin_unlock(&orig_neigh_node->lock); + orig_unreference(orig_neigh_node); + bat_dbg(DBG_BATMAN, "Drop packet: originator packet from myself (via neighbour) \n"); return; } @@ -481,6 +498,8 @@ if (orig_node == NULL) return;

+ spin_lock(&orig_node->lock); + /* avoid temporary routing loops */ if ((orig_node->router) && (orig_node->router->orig_node->router) && @@ -489,36 +508,49 @@ !(compare_orig(batman_packet->orig, batman_packet->prev_sender)) && (compare_orig(orig_node->router->addr, orig_node->router->orig_node->router->addr))) { + bat_dbg(DBG_BATMAN, "Drop packet: ignoring all rebroadcast packets that may make me loop (sender: %s) \n", neigh_str); + + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); return; } + spin_unlock(&orig_node->lock);

/* if sender is a direct neighbor the sender mac equals * originator mac */ orig_neigh_node = (is_single_hop_neigh ? - orig_node : get_orig_node(ethhdr->h_source)); - if (orig_neigh_node == NULL) + orig_reference(orig_node) : get_orig_node(ethhdr->h_source)); + if (orig_neigh_node == NULL) { + orig_unreference(orig_node); return; + }

/* drop packet if sender is not a direct neighbor and if we * don't route towards it */ if (!is_single_hop_neigh && (orig_neigh_node->router == NULL)) { bat_dbg(DBG_BATMAN, "Drop packet: OGM via unknown neighbor!\n"); + + orig_unreference(orig_node); + orig_unreference(orig_neigh_node); return; }

is_bidirectional = isBidirectionalNeigh(orig_node, orig_neigh_node, batman_packet, if_incoming); + orig_unreference(orig_neigh_node);

/* update ranking if it is not a duplicate or has the same * seqno and similar ttl as the non-duplicate */ + spin_lock(&orig_node->lock); if (is_bidirectional && (!is_duplicate || ((orig_node->last_real_seqno == batman_packet->seqno) && (orig_node->last_ttl - 3 <= batman_packet->ttl)))) update_orig(orig_node, ethhdr, batman_packet, if_incoming, hna_buff, hna_buff_len, is_duplicate); + spin_unlock(&orig_node->lock);

/* is single hop (direct) neighbour */ if (is_single_hop_neigh) { @@ -528,6 +560,7 @@ 1, hna_buff_len, if_incoming);

bat_dbg(DBG_BATMAN, "Forwarding packet: rebroadcast neighbour packet with direct link flag\n"); + orig_unreference(orig_node); return; }

@@ -535,11 +568,13 @@ if (!is_bidirectional) { bat_dbg(DBG_BATMAN, "Drop packet: not received via bidirectional link\n"); + orig_unreference(orig_node); return; }

if (is_duplicate) { bat_dbg(DBG_BATMAN, "Drop packet: duplicate packet received\n"); + orig_unreference(orig_node); return; }

@@ -547,6 +582,7 @@ "Forwarding packet: rebroadcast originator packet\n"); schedule_forward_packet(orig_node, ethhdr, batman_packet, 0, hna_buff_len, if_incoming); + orig_unreference(orig_node); }

@@ -585,12 +621,10 @@ if (result < sizeof(struct ethhdr) + sizeof(struct batman_packet)) return;

- spin_lock(&orig_hash_lock); receive_aggr_bat_packet(ethhdr, packet_buff + sizeof(struct ethhdr), result - sizeof(struct ethhdr), batman_if); - spin_unlock(&orig_hash_lock); }

static void recv_my_icmp_packet(struct ethhdr *ethhdr, @@ -608,25 +642,28 @@

/* answer echo request (ping) */ /* get routing information */ - spin_lock(&orig_hash_lock); - orig_node = ((struct orig_node *)hash_find(orig_hash, - icmp_packet->orig)); + orig_node = orig_find(icmp_packet->orig);

- if ((orig_node != NULL) && - (orig_node->batman_if != NULL) && - (orig_node->router != NULL)) { - memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN); - memcpy(icmp_packet->orig, ethhdr->h_dest, ETH_ALEN); - icmp_packet->msg_type = ECHO_REPLY; - icmp_packet->ttl = TTL; + if (orig_node) { + spin_lock(&orig_node->lock);

- send_raw_packet(packet_buff + sizeof(struct ethhdr), - result - sizeof(struct ethhdr), - orig_node->batman_if, - orig_node->router->addr); + if ((orig_node->batman_if != NULL) && + (orig_node->router != NULL)) { + memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN); + memcpy(icmp_packet->orig, ethhdr->h_dest, ETH_ALEN); + icmp_packet->msg_type = ECHO_REPLY; + icmp_packet->ttl = TTL; + + send_raw_packet(packet_buff + sizeof(struct ethhdr), + result - sizeof(struct ethhdr), + orig_node->batman_if, + orig_node->router->addr); + } + + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); }

- spin_unlock(&orig_hash_lock); return; }

@@ -642,33 +679,32 @@ addr_to_string(src_str, icmp_packet->orig); addr_to_string(dst_str, icmp_packet->dst);

- printk(KERN_WARNING "batman-adv:Warning - can't send packet from %s to %s: ttl exceeded\n", src_str, dst_str); - /* send TTL exceeded if packet is an echo request (traceroute) */ if (icmp_packet->msg_type != ECHO_REQUEST) return;

/* get routing information */ - spin_lock(&orig_hash_lock); - orig_node = ((struct orig_node *) - hash_find(orig_hash, icmp_packet->orig)); + orig_node = orig_find(icmp_packet->orig);

- if ((orig_node != NULL) && - (orig_node->batman_if != NULL) && - (orig_node->router != NULL)) { - memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN); - memcpy(icmp_packet->orig, ethhdr->h_dest, ETH_ALEN); - icmp_packet->msg_type = TTL_EXCEEDED; - icmp_packet->ttl = TTL; + if (orig_node) { + spin_lock(&orig_node->lock);

- send_raw_packet(packet_buff + sizeof(struct ethhdr), - result - sizeof(struct ethhdr), - orig_node->batman_if, - orig_node->router->addr); + if ((orig_node->batman_if != NULL) && + (orig_node->router != NULL)) { + memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN); + memcpy(icmp_packet->orig, ethhdr->h_dest, ETH_ALEN); + icmp_packet->msg_type = TTL_EXCEEDED; + icmp_packet->ttl = TTL;

+ send_raw_packet(packet_buff + sizeof(struct ethhdr), + result - sizeof(struct ethhdr), + orig_node->batman_if, + orig_node->router->addr); + } + + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); } - - spin_unlock(&orig_hash_lock); }

@@ -713,24 +749,27 @@ }

/* get routing information */ - spin_lock(&orig_hash_lock); - orig_node = ((struct orig_node *) - hash_find(orig_hash, icmp_packet->dst)); + orig_node = orig_find(icmp_packet->dst);

- if ((orig_node != NULL) && - (orig_node->batman_if != NULL) && - (orig_node->router != NULL)) { + if (orig_node) { + spin_lock(&orig_node->lock);

- /* decrement ttl */ - icmp_packet->ttl--; + if ((orig_node->batman_if != NULL) && + (orig_node->router != NULL)) {

- /* route it */ - send_raw_packet(packet_buff + sizeof(struct ethhdr), - result - sizeof(struct ethhdr), - orig_node->batman_if, - orig_node->router->addr); + /* decrement ttl */ + icmp_packet->ttl--; + + /* route it */ + send_raw_packet(packet_buff + sizeof(struct ethhdr), + result - sizeof(struct ethhdr), + orig_node->batman_if, + orig_node->router->addr); + } + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); + } - spin_unlock(&orig_hash_lock); }

static void recv_unicast_packet(struct ethhdr *ethhdr, @@ -781,23 +820,26 @@ }

/* get routing information */ - spin_lock(&orig_hash_lock); - orig_node = ((struct orig_node *) - hash_find(orig_hash, unicast_packet->dest)); + orig_node = orig_find(unicast_packet->dest);

- if ((orig_node != NULL) && - (orig_node->batman_if != NULL) && - (orig_node->router != NULL)) { - /* decrement ttl */ - unicast_packet->ttl--; + if (orig_node) { + spin_lock(&orig_node->lock);

- /* route it */ - send_raw_packet(packet_buff + sizeof(struct ethhdr), - result - sizeof(struct ethhdr), - orig_node->batman_if, - orig_node->router->addr); + if ((orig_node->batman_if != NULL) && + (orig_node->router != NULL)) { + /* decrement ttl */ + unicast_packet->ttl--; + + /* route it */ + send_raw_packet(packet_buff + sizeof(struct ethhdr), + result - sizeof(struct ethhdr), + orig_node->batman_if, + orig_node->router->addr); + } + + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); } - spin_unlock(&orig_hash_lock); }

@@ -833,20 +875,19 @@ if (is_my_mac(bcast_packet->orig)) return;

- spin_lock(&orig_hash_lock); - orig_node = ((struct orig_node *) - hash_find(orig_hash, bcast_packet->orig)); + orig_node = orig_find(bcast_packet->orig);

- if (orig_node == NULL) { - spin_unlock(&orig_hash_lock); + if (!orig_node) return; - }

+ spin_lock(&orig_node->lock); + /* check flood history */ if (get_bit_status(orig_node->bcast_bits, orig_node->last_bcast_seqno, ntohs(bcast_packet->seqno))) { - spin_unlock(&orig_hash_lock); + spin_unlock(&orig_node->lock); + orig_unreference(orig_node); return; }

@@ -856,7 +897,8 @@ orig_node->last_bcast_seqno, 1)) orig_node->last_bcast_seqno = ntohs(bcast_packet->seqno);

- spin_unlock(&orig_hash_lock); + spin_unlock(&orig_node->lock); + orig_unreference(orig_node);

/* broadcast for me */ interface_rx(soft_device, packet_buff + hdr_size, result - hdr_size); Index: batman-adv-kernelland/main.h =================================================================== --- batman-adv-kernelland/main.h (revision 1489) +++ batman-adv-kernelland/main.h (working copy) @@ -124,7 +124,6 @@ extern struct hlist_head forw_bcast_list; extern struct hashtable_t *orig_hash;

-extern spinlock_t orig_hash_lock; extern spinlock_t forw_bat_list_lock; extern spinlock_t forw_bcast_list_lock;