commits October 2010

commits@lists.open-mesh.org

1 participants
59 discussions

batman-adv; branch, master, updated. v2010.1.0-206-g4983f2a

by postmaster＠open-mesh.org

The following commit has been merged in the master branch: commit 4983f2aa6bdefb7247023c31b13d7d38f2e97091 Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Sat Oct 23 01:42:14 2010 +0000 batman-adv: Rewrite hash using hlist_* The hash implementation is a complete implementation of a hash using buckets as hash entries and overflow buckets attached to them. The kernel already provides datastructures hlist_head and hlist_node which can be used to implement an hash using lists as hash buckets. So it is better to implement heavily used functionality on top of those instead of providing a full hash implementation. The rewrite changes the behavior of some functions slightly: * hash_add add elements to the front instead of the tail * hash_iterate doesn't provide pointer to access bucket->data directly, but it can be accessed using hlist_entry Reported-by: David S. Miller <davem(a)davemloft.net> Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> diff --git a/hash.c b/hash.c index bfe943c..8605e2f 100644 --- a/hash.c +++ b/hash.c @@ -30,7 +30,7 @@ static void hash_init(struct hashtable_t *hash) hash->elements = 0; for (i = 0 ; i < hash->size; i++) - hash->table[i] = NULL; + INIT_HLIST_HEAD(&hash->table[i]); } /* free only the hashtable and the hash itself. */ @@ -70,15 +70,13 @@ struct hashtable_t *hash_new(int size) void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) { void *data_save; + struct element_t *bucket; - data_save = hash_it_t->bucket->data; + bucket = hlist_entry(hash_it_t->walk, struct element_t, hlist); + data_save = bucket->data; - if (hash_it_t->prev_bucket != NULL) - hash_it_t->prev_bucket->next = hash_it_t->bucket->next; - else if (hash_it_t->first_bucket != NULL) - (*hash_it_t->first_bucket) = hash_it_t->bucket->next; - - kfree(hash_it_t->bucket); + hlist_del(hash_it_t->walk); + kfree(bucket); hash->elements--; return data_save; diff --git a/hash.h b/hash.h index a8e4dd1..0b61c6e 100644 --- a/hash.h +++ b/hash.h @@ -22,10 +22,11 @@ #ifndef _NET_BATMAN_ADV_HASH_H_ #define _NET_BATMAN_ADV_HASH_H_ +#include <linux/list.h> + #define HASHIT(name) struct hash_it_t name = { \ - .index = -1, .bucket = NULL, \ - .prev_bucket = NULL, \ - .first_bucket = NULL } + .index = 0, .walk = NULL, \ + .safe = NULL} /* callback to a compare function. should * compare 2 element datas for their keys, @@ -41,18 +42,17 @@ typedef void (*hashdata_free_cb)(void *, void *); struct element_t { void *data; /* pointer to the data */ - struct element_t *next; /* overflow bucket pointer */ + struct hlist_node hlist; /* bucket list pointer */ }; struct hash_it_t { - int index; - struct element_t *bucket; - struct element_t *prev_bucket; - struct element_t **first_bucket; + size_t index; + struct hlist_node *walk; + struct hlist_node *safe; }; struct hashtable_t { - struct element_t **table; /* the hashtable itself, with the buckets */ + struct hlist_head *table; /* the hashtable itself, with the buckets */ int elements; /* number of elements registered */ int size; /* size of hashtable */ }; @@ -75,19 +75,21 @@ void hash_destroy(struct hashtable_t *hash); static inline void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb, void *arg) { - struct element_t *bucket, *last_bucket; + struct hlist_head *head; + struct hlist_node *walk, *safe; + struct element_t *bucket; int i; for (i = 0; i < hash->size; i++) { - bucket = hash->table[i]; + head = &hash->table[i]; - while (bucket != NULL) { + hlist_for_each_safe(walk, safe, head) { + bucket = hlist_entry(walk, struct element_t, hlist); if (free_cb != NULL) free_cb(bucket->data, arg); - last_bucket = bucket; - bucket = bucket->next; - kfree(last_bucket); + hlist_del(walk); + kfree(bucket); } } @@ -100,36 +102,30 @@ static inline int hash_add(struct hashtable_t *hash, hashdata_choose_cb choose, void *data) { int index; - struct element_t *bucket, *prev_bucket = NULL; + struct hlist_head *head; + struct hlist_node *walk, *safe; + struct element_t *bucket; if (!hash) return -1; index = choose(data, hash->size); - bucket = hash->table[index]; + head = &hash->table[index]; - while (bucket != NULL) { + hlist_for_each_safe(walk, safe, head) { + bucket = hlist_entry(walk, struct element_t, hlist); if (compare(bucket->data, data)) return -1; - - prev_bucket = bucket; - bucket = bucket->next; } - /* found the tail of the list, add new element */ + /* no duplicate found in list, add new element */ bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC); if (bucket == NULL) return -1; bucket->data = data; - bucket->next = NULL; - - /* and link it */ - if (prev_bucket == NULL) - hash->table[index] = bucket; - else - prev_bucket->next = bucket; + hlist_add_head(&bucket->hlist, head); hash->elements++; return 0; @@ -144,22 +140,16 @@ static inline void *hash_remove(struct hashtable_t *hash, hashdata_choose_cb choose, void *data) { struct hash_it_t hash_it_t; + struct element_t *bucket; + struct hlist_head *head; hash_it_t.index = choose(data, hash->size); - hash_it_t.bucket = hash->table[hash_it_t.index]; - hash_it_t.prev_bucket = NULL; - - while (hash_it_t.bucket != NULL) { - if (compare(hash_it_t.bucket->data, data)) { - hash_it_t.first_bucket = - (hash_it_t.bucket == - hash->table[hash_it_t.index] ? - &hash->table[hash_it_t.index] : NULL); - return hash_remove_bucket(hash, &hash_it_t); - } + head = &hash->table[hash_it_t.index]; - hash_it_t.prev_bucket = hash_it_t.bucket; - hash_it_t.bucket = hash_it_t.bucket->next; + 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); } return NULL; @@ -172,19 +162,20 @@ static inline void *hash_find(struct hashtable_t *hash, hashdata_choose_cb choose, void *keydata) { int index; + struct hlist_head *head; + struct hlist_node *walk; struct element_t *bucket; if (!hash) return NULL; index = choose(keydata , hash->size); - bucket = hash->table[index]; + head = &hash->table[index]; - while (bucket != NULL) { + hlist_for_each(walk, head) { + bucket = hlist_entry(walk, struct element_t, hlist); if (compare(bucket->data, keydata)) return bucket->data; - - bucket = bucket->next; } return NULL; @@ -193,13 +184,14 @@ static inline void *hash_find(struct hashtable_t *hash, /* 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_compare_cb compare, 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; + int i, new_index; /* initialize a new hash with the new size */ new_hash = hash_new(size); @@ -209,17 +201,20 @@ static inline struct hashtable_t *hash_resize(struct hashtable_t *hash, /* copy the elements */ for (i = 0; i < hash->size; i++) { - bucket = hash->table[i]; + head = &hash->table[i]; + + hlist_for_each_safe(walk, safe, head) { + bucket = hlist_entry(walk, struct element_t, hlist); - while (bucket != NULL) { - hash_add(new_hash, compare, choose, bucket->data); - bucket = bucket->next; + new_index = choose(bucket->data, size); + new_head = &new_hash->table[new_index]; + + hlist_del(walk); + hlist_add_head(walk, new_head); } } - /* remove hash and eventual overflow buckets but not the content - * itself. */ - hash_delete(hash, NULL, NULL); + hash_destroy(hash); return new_hash; } @@ -236,63 +231,29 @@ static inline struct hash_it_t *hash_iterate(struct hashtable_t *hash, if (!iter) return NULL; - /* sanity checks first (if our bucket got deleted in the last - * iteration): */ - if (iter->bucket != NULL) { - if (iter->first_bucket != NULL) { - /* we're on the first element and it got removed after - * the last iteration. */ - if ((*iter->first_bucket) != iter->bucket) { - /* there are still other elements in the list */ - if ((*iter->first_bucket) != NULL) { - iter->prev_bucket = NULL; - iter->bucket = (*iter->first_bucket); - iter->first_bucket = - &hash->table[iter->index]; - return iter; - } else { - iter->bucket = NULL; - } - } - } else if (iter->prev_bucket != NULL) { - /* - * we're not on the first element, and the bucket got - * removed after the last iteration. the last bucket's - * next pointer is not pointing to our actual bucket - * anymore. select the next. - */ - if (iter->prev_bucket->next != iter->bucket) - iter->bucket = iter->prev_bucket; - } - } + iter->walk = iter->safe; - /* now as we are sane, select the next one if there is some */ - if (iter->bucket != NULL) { - if (iter->bucket->next != NULL) { - iter->prev_bucket = iter->bucket; - iter->bucket = iter->bucket->next; - iter->first_bucket = NULL; - return iter; - } - } + /* 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; - /* if not returned yet, we've reached the last one on the index and have - * to search forward */ - iter->index++; - /* go through the entries of the hash table */ - while (iter->index < hash->size) { - if ((hash->table[iter->index]) != NULL) { - iter->prev_bucket = NULL; - iter->bucket = hash->table[iter->index]; - iter->first_bucket = &hash->table[iter->index]; - return iter; - } else { - iter->index++; + /* search next time */ + ++iter->index; + break; + } } } - /* nothing to iterate over anymore */ - return NULL; + /* return iter when we found bucket otherwise null */ + if (!iter->walk) + return NULL; + + iter->safe = iter->walk->next; + return iter; } #endif /* _NET_BATMAN_ADV_HASH_H_ */ diff --git a/originator.c b/originator.c index d4da99c..afac4eb 100644 --- a/originator.c +++ b/originator.c @@ -177,8 +177,7 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) goto free_bcast_own_sum; if (bat_priv->orig_hash->elements * 4 > bat_priv->orig_hash->size) { - swaphash = hash_resize(bat_priv->orig_hash, compare_orig, - choose_orig, + swaphash = hash_resize(bat_priv->orig_hash,choose_orig, bat_priv->orig_hash->size * 2); if (!swaphash) @@ -274,6 +273,7 @@ static bool purge_orig_node(struct bat_priv *bat_priv, static void _purge_orig(struct bat_priv *bat_priv) { HASHIT(hashit); + struct element_t *bucket; struct orig_node *orig_node; unsigned long flags; @@ -281,7 +281,8 @@ static void _purge_orig(struct bat_priv *bat_priv) /* for all origins... */ while (hash_iterate(bat_priv->orig_hash, &hashit)) { - orig_node = hashit.bucket->data; + 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) @@ -322,6 +323,7 @@ void purge_orig_ref(struct bat_priv *bat_priv) int orig_seq_print_text(struct seq_file *seq, void *offset) { HASHIT(hashit); + struct element_t *bucket; struct net_device *net_dev = (struct net_device *)seq->private; struct bat_priv *bat_priv = netdev_priv(net_dev); struct orig_node *orig_node; @@ -355,8 +357,8 @@ int orig_seq_print_text(struct seq_file *seq, void *offset) spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); while (hash_iterate(bat_priv->orig_hash, &hashit)) { - - orig_node = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + orig_node = bucket->data; if (!orig_node->router) continue; @@ -430,13 +432,15 @@ int orig_hash_add_if(struct batman_if *batman_if, int max_if_num) struct orig_node *orig_node; unsigned long flags; HASHIT(hashit); + struct element_t *bucket; /* resize all orig nodes because orig_node->bcast_own(_sum) depend on * if_num */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); while (hash_iterate(bat_priv->orig_hash, &hashit)) { - orig_node = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + orig_node = bucket->data; if (orig_node_add_if(orig_node, max_if_num) == -1) goto err; @@ -509,6 +513,7 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) struct orig_node *orig_node; unsigned long flags; HASHIT(hashit); + struct element_t *bucket; int ret; /* resize all orig nodes because orig_node->bcast_own(_sum) depend on @@ -516,7 +521,8 @@ int orig_hash_del_if(struct batman_if *batman_if, int max_if_num) spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); while (hash_iterate(bat_priv->orig_hash, &hashit)) { - orig_node = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + orig_node = bucket->data; ret = orig_node_del_if(orig_node, max_if_num, batman_if->if_num); diff --git a/routing.c b/routing.c index 60f23ef..186428d 100644 --- a/routing.c +++ b/routing.c @@ -40,6 +40,7 @@ void slide_own_bcast_window(struct batman_if *batman_if) { struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); HASHIT(hashit); + struct element_t *bucket; struct orig_node *orig_node; TYPE_OF_WORD *word; unsigned long flags; @@ -47,7 +48,8 @@ void slide_own_bcast_window(struct batman_if *batman_if) spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); while (hash_iterate(bat_priv->orig_hash, &hashit)) { - orig_node = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + orig_node = bucket->data; word = &(orig_node->bcast_own[batman_if->if_num * NUM_WORDS]); bit_get_packet(bat_priv, word, 1, 0); diff --git a/translation-table.c b/translation-table.c index 1e7f583..f435718 100644 --- a/translation-table.c +++ b/translation-table.c @@ -117,8 +117,7 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) if (bat_priv->hna_local_hash->elements * 4 > bat_priv->hna_local_hash->size) { - swaphash = hash_resize(bat_priv->hna_local_hash, compare_orig, - choose_orig, + swaphash = hash_resize(bat_priv->hna_local_hash, choose_orig, bat_priv->hna_local_hash->size * 2); if (!swaphash) @@ -147,6 +146,7 @@ int hna_local_fill_buffer(struct bat_priv *bat_priv, unsigned char *buff, int buff_len) { struct hna_local_entry *hna_local_entry; + struct element_t *bucket; HASHIT(hashit); int i = 0; unsigned long flags; @@ -158,7 +158,8 @@ int hna_local_fill_buffer(struct bat_priv *bat_priv, if (buff_len < (i + 1) * ETH_ALEN) break; - hna_local_entry = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + hna_local_entry = bucket->data; memcpy(buff + (i * ETH_ALEN), hna_local_entry->addr, ETH_ALEN); i++; @@ -179,6 +180,7 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) struct hna_local_entry *hna_local_entry; HASHIT(hashit); HASHIT(hashit_count); + struct element_t *bucket; unsigned long flags; size_t buf_size, pos; char *buff; @@ -209,7 +211,8 @@ int hna_local_seq_print_text(struct seq_file *seq, void *offset) pos = 0; while (hash_iterate(bat_priv->hna_local_hash, &hashit)) { - hna_local_entry = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + hna_local_entry = bucket->data; pos += snprintf(buff + pos, 22, " * %pM\n", hna_local_entry->addr); @@ -268,13 +271,15 @@ static void hna_local_purge(struct work_struct *work) container_of(delayed_work, struct bat_priv, hna_work); struct hna_local_entry *hna_local_entry; HASHIT(hashit); + struct element_t *bucket; unsigned long flags; unsigned long timeout; spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); while (hash_iterate(bat_priv->hna_local_hash, &hashit)) { - hna_local_entry = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + hna_local_entry = bucket->data; timeout = hna_local_entry->last_seen + LOCAL_HNA_TIMEOUT * HZ; @@ -390,8 +395,7 @@ void hna_global_add_orig(struct bat_priv *bat_priv, if (bat_priv->hna_global_hash->elements * 4 > bat_priv->hna_global_hash->size) { - swaphash = hash_resize(bat_priv->hna_global_hash, compare_orig, - choose_orig, + swaphash = hash_resize(bat_priv->hna_global_hash, choose_orig, bat_priv->hna_global_hash->size * 2); if (!swaphash) @@ -410,6 +414,7 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset) struct hna_global_entry *hna_global_entry; HASHIT(hashit); HASHIT(hashit_count); + struct element_t *bucket; unsigned long flags; size_t buf_size, pos; char *buff; @@ -439,7 +444,8 @@ int hna_global_seq_print_text(struct seq_file *seq, void *offset) pos = 0; while (hash_iterate(bat_priv->hna_global_hash, &hashit)) { - hna_global_entry = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + hna_global_entry = bucket->data; pos += snprintf(buff + pos, 44, " * %pM via %pM\n", hna_global_entry->addr, diff --git a/vis.c b/vis.c index 88402c9..9e41f81 100644 --- a/vis.c +++ b/vis.c @@ -183,6 +183,7 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) { HASHIT(hashit); HASHIT(hashit_count); + struct element_t *bucket; struct vis_info *info; struct vis_packet *packet; struct vis_info_entry *entries; @@ -206,7 +207,9 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) /* Estimate length */ spin_lock_irqsave(&bat_priv->vis_hash_lock, flags); while (hash_iterate(bat_priv->vis_hash, &hashit_count)) { - info = hashit_count.bucket->data; + bucket = hlist_entry(hashit_count.walk, struct element_t, + hlist); + info = bucket->data; packet = (struct vis_packet *)info->skb_packet->data; entries = (struct vis_info_entry *) ((char *)packet + sizeof(struct vis_packet)); @@ -244,7 +247,8 @@ int vis_seq_print_text(struct seq_file *seq, void *offset) buff_pos = 0; while (hash_iterate(bat_priv->vis_hash, &hashit)) { - info = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + info = bucket->data; packet = (struct vis_packet *)info->skb_packet->data; entries = (struct vis_info_entry *) ((char *)packet + sizeof(struct vis_packet)); @@ -523,6 +527,7 @@ static int find_best_vis_server(struct bat_priv *bat_priv, struct vis_info *info) { HASHIT(hashit); + struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; int best_tq = -1; @@ -530,7 +535,8 @@ static int find_best_vis_server(struct bat_priv *bat_priv, packet = (struct vis_packet *)info->skb_packet->data; while (hash_iterate(bat_priv->orig_hash, &hashit)) { - orig_node = hashit.bucket->data; + 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)) { @@ -559,6 +565,7 @@ static int generate_vis_packet(struct bat_priv *bat_priv) { HASHIT(hashit_local); HASHIT(hashit_global); + struct element_t *bucket; struct orig_node *orig_node; struct vis_info *info = (struct vis_info *)bat_priv->my_vis_info; struct vis_packet *packet = (struct vis_packet *)info->skb_packet->data; @@ -588,7 +595,9 @@ static int generate_vis_packet(struct bat_priv *bat_priv) } while (hash_iterate(bat_priv->orig_hash, &hashit_global)) { - orig_node = hashit_global.bucket->data; + bucket = hlist_entry(hashit_global.walk, struct element_t, + hlist); + orig_node = bucket->data; if (!orig_node->router) continue; @@ -623,7 +632,9 @@ static int generate_vis_packet(struct bat_priv *bat_priv) spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); while (hash_iterate(bat_priv->hna_local_hash, &hashit_local)) { - hna_local_entry = hashit_local.bucket->data; + bucket = hlist_entry(hashit_local.walk, struct element_t, + hlist); + hna_local_entry = bucket->data; entry = (struct vis_info_entry *)skb_put(info->skb_packet, sizeof(*entry)); memset(entry->src, 0, ETH_ALEN); @@ -647,10 +658,12 @@ static int generate_vis_packet(struct bat_priv *bat_priv) static void purge_vis_packets(struct bat_priv *bat_priv) { HASHIT(hashit); + struct element_t *bucket; struct vis_info *info; while (hash_iterate(bat_priv->vis_hash, &hashit)) { - info = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + info = bucket->data; /* never purge own data. */ if (info == bat_priv->my_vis_info) @@ -669,6 +682,7 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, struct vis_info *info) { HASHIT(hashit); + struct element_t *bucket; struct orig_node *orig_node; struct vis_packet *packet; struct sk_buff *skb; @@ -682,7 +696,8 @@ static void broadcast_vis_packet(struct bat_priv *bat_priv, /* send to all routers in range. */ while (hash_iterate(bat_priv->orig_hash, &hashit)) { - orig_node = hashit.bucket->data; + bucket = hlist_entry(hashit.walk, struct element_t, hlist); + orig_node = bucket->data; /* if it's a vis server and reachable, send it. */ if ((!orig_node) || (!orig_node->router)) -- batman-adv

12 years, 5 months

batman-adv; branch, master, updated. v2010.1.0-206-g4983f2a

by postmaster＠open-mesh.org

The following commit has been merged in the master branch: commit e908addcc37608ff01448f008db272d7b8f414ac Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Sat Oct 23 01:42:09 2010 +0000 batman-adv: Remove hashdata_compare_cb from hash Function pointers cannot be inlined by a compiler and thus always has the overhead of an call. hashdata_compare_cb's are one of the most often called function pointers and its overhead must kept relative low. As first step, every function which uses this function pointer takes it as parameter instead of storing it inside the hash abstraction structure. This not generate any performance gain right now. The called functions must also be able to be inlined by the calling functions to enable inlining of the function pointer. Reported-by: David S. Miller <davem(a)davemloft.net> Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> diff --git a/hash.c b/hash.c index 8ef26eb..a4abe14 100644 --- a/hash.c +++ b/hash.c @@ -137,8 +137,7 @@ struct hash_it_t *hash_iterate(struct hashtable_t *hash, } /* allocates and clears the hash */ -struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, - hashdata_choose_cb choose) +struct hashtable_t *hash_new(int size, hashdata_choose_cb choose) { struct hashtable_t *hash; @@ -157,14 +156,13 @@ struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, hash_init(hash); - hash->compare = compare; hash->choose = choose; return hash; } /* adds data to the hashtable. returns 0 on success, -1 on error */ -int hash_add(struct hashtable_t *hash, void *data) +int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, void *data) { int index; struct element_t *bucket, *prev_bucket = NULL; @@ -176,7 +174,7 @@ int hash_add(struct hashtable_t *hash, void *data) bucket = hash->table[index]; while (bucket != NULL) { - if (hash->compare(bucket->data, data)) + if (compare(bucket->data, data)) return -1; prev_bucket = bucket; @@ -204,7 +202,8 @@ int hash_add(struct hashtable_t *hash, void *data) /* finds data, based on the key in keydata. returns the found data on success, * or NULL on error */ -void *hash_find(struct hashtable_t *hash, void *keydata) +void *hash_find(struct hashtable_t *hash, hashdata_compare_cb compare, + void *keydata) { int index; struct element_t *bucket; @@ -216,7 +215,7 @@ void *hash_find(struct hashtable_t *hash, void *keydata) bucket = hash->table[index]; while (bucket != NULL) { - if (hash->compare(bucket->data, keydata)) + if (compare(bucket->data, keydata)) return bucket->data; bucket = bucket->next; @@ -250,7 +249,8 @@ void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) * can remove the used structure yourself, or NULL on error . data could be the * structure you use with just the key filled, we just need the key for * comparing. */ -void *hash_remove(struct hashtable_t *hash, void *data) +void *hash_remove(struct hashtable_t *hash, hashdata_compare_cb compare, + void *data) { struct hash_it_t hash_it_t; @@ -259,7 +259,7 @@ void *hash_remove(struct hashtable_t *hash, void *data) hash_it_t.prev_bucket = NULL; while (hash_it_t.bucket != NULL) { - if (hash->compare(hash_it_t.bucket->data, data)) { + if (compare(hash_it_t.bucket->data, data)) { hash_it_t.first_bucket = (hash_it_t.bucket == hash->table[hash_it_t.index] ? @@ -276,14 +276,15 @@ void *hash_remove(struct hashtable_t *hash, void *data) /* resize the hash, returns the pointer to the new hash or NULL on * error. removes the old hash on success. */ -struct hashtable_t *hash_resize(struct hashtable_t *hash, int size) +struct hashtable_t *hash_resize(struct hashtable_t *hash, + hashdata_compare_cb compare, int size) { struct hashtable_t *new_hash; struct element_t *bucket; int i; /* initialize a new hash with the new size */ - new_hash = hash_new(size, hash->compare, hash->choose); + new_hash = hash_new(size, hash->choose); if (new_hash == NULL) return NULL; @@ -293,7 +294,7 @@ struct hashtable_t *hash_resize(struct hashtable_t *hash, int size) bucket = hash->table[i]; while (bucket != NULL) { - hash_add(new_hash, bucket->data); + hash_add(new_hash, compare, bucket->data); bucket = bucket->next; } } diff --git a/hash.h b/hash.h index 2c8e176..742277e 100644 --- a/hash.h +++ b/hash.h @@ -27,7 +27,10 @@ .prev_bucket = NULL, \ .first_bucket = NULL } - +/* callback to a compare function. should + * compare 2 element datas for their keys, + * return 0 if same and not 0 if not + * same */ typedef int (*hashdata_compare_cb)(void *, void *); typedef int (*hashdata_choose_cb)(void *, int); typedef void (*hashdata_free_cb)(void *, void *); @@ -48,18 +51,13 @@ struct hashtable_t { struct element_t **table; /* the hashtable itself, with the buckets */ int elements; /* number of elements registered */ int size; /* size of hashtable */ - hashdata_compare_cb compare;/* callback to a compare function. should - * compare 2 element datas for their keys, - * return 0 if same and not 0 if not - * same */ hashdata_choose_cb choose; /* the hashfunction, should return an index * based on the key in the data of the first * argument and the size the second */ }; /* allocates and clears the hash */ -struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, - hashdata_choose_cb choose); +struct hashtable_t *hash_new(int size, hashdata_choose_cb choose); /* remove bucket (this might be used in hash_iterate() if you already found the * bucket you want to delete and don't need the overhead to find it again with @@ -76,21 +74,24 @@ void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb, void *arg); void hash_destroy(struct hashtable_t *hash); /* adds data to the hashtable. returns 0 on success, -1 on error */ -int hash_add(struct hashtable_t *hash, void *data); +int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, void *data); /* removes data from hash, if found. returns pointer do data on success, so you * can remove the used structure yourself, or NULL on error . data could be the * structure you use with just the key filled, we just need the key for * comparing. */ -void *hash_remove(struct hashtable_t *hash, void *data); +void *hash_remove(struct hashtable_t *hash, hashdata_compare_cb compare, + void *data); /* finds data, based on the key in keydata. returns the found data on success, * or NULL on error */ -void *hash_find(struct hashtable_t *hash, void *keydata); +void *hash_find(struct hashtable_t *hash, hashdata_compare_cb compare, + void *keydata); /* resize the hash, returns the pointer to the new hash or NULL on * error. removes the old hash on success */ -struct hashtable_t *hash_resize(struct hashtable_t *hash, int size); +struct hashtable_t *hash_resize(struct hashtable_t *hash, + hashdata_compare_cb compare, int size); /* iterate though the hash. first element is selected with iter_in NULL. use * the returned iterator to access the elements until hash_it_t returns NULL. */ diff --git a/icmp_socket.c b/icmp_socket.c index aa64ff8..de70752 100644 --- a/icmp_socket.c +++ b/icmp_socket.c @@ -26,6 +26,7 @@ #include "send.h" #include "types.h" #include "hash.h" +#include "originator.h" #include "hard-interface.h" #include "compat.h" @@ -227,6 +228,7 @@ static ssize_t bat_socket_write(struct file *file, const char __user *buff, spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, + compare_orig, icmp_packet->dst)); if (!orig_node) diff --git a/main.c b/main.c index 6ecee49..ecab8b8 100644 --- a/main.c +++ b/main.c @@ -159,13 +159,6 @@ int addr_to_string(char *buff, uint8_t *addr) return sprintf(buff, "%pM", addr); } -/* returns 1 if they are the same originator */ - -int compare_orig(void *data1, void *data2) -{ - return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); -} - /* hashfunction to choose an entry in a hash table of given size */ /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */ int choose_orig(void *data, int32_t size) diff --git a/main.h b/main.h index cc42eb4..c09a9fd 100644 --- a/main.h +++ b/main.h @@ -139,7 +139,6 @@ void mesh_free(struct net_device *soft_iface); void inc_module_count(void); void dec_module_count(void); int addr_to_string(char *buff, uint8_t *addr); -int compare_orig(void *data1, void *data2); int choose_orig(void *data, int32_t size); int is_my_mac(uint8_t *addr); int is_bcast(uint8_t *addr); diff --git a/originator.c b/originator.c index 6868a2a..95ca7ae 100644 --- a/originator.c +++ b/originator.c @@ -47,7 +47,7 @@ int originator_init(struct bat_priv *bat_priv) return 1; spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); - bat_priv->orig_hash = hash_new(128, compare_orig, choose_orig); + bat_priv->orig_hash = hash_new(128, choose_orig); if (!bat_priv->orig_hash) goto err; @@ -131,7 +131,8 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) struct hashtable_t *swaphash; int size; - orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, addr)); + orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, + compare_orig, addr)); if (orig_node) return orig_node; @@ -168,11 +169,11 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) if (!orig_node->bcast_own_sum) goto free_bcast_own; - if (hash_add(bat_priv->orig_hash, orig_node) < 0) + if (hash_add(bat_priv->orig_hash, compare_orig, orig_node) < 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, + swaphash = hash_resize(bat_priv->orig_hash, compare_orig, bat_priv->orig_hash->size * 2); if (!swaphash) diff --git a/originator.h b/originator.h index a97c400..ed903dc 100644 --- a/originator.h +++ b/originator.h @@ -33,4 +33,11 @@ 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); + +/* returns 1 if they are the same originator */ +static inline int compare_orig(void *data1, void *data2) +{ + return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); +} + #endif /* _NET_BATMAN_ADV_ORIGINATOR_H_ */ diff --git a/routing.c b/routing.c index cc8b77f..f12d878 100644 --- a/routing.c +++ b/routing.c @@ -823,6 +823,7 @@ static int recv_my_icmp_packet(struct bat_priv *bat_priv, /* get routing information */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, + compare_orig, icmp_packet->orig)); ret = NET_RX_DROP; @@ -885,7 +886,8 @@ static int recv_icmp_ttl_exceeded(struct bat_priv *bat_priv, /* get routing information */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, icmp_packet->orig)); + hash_find(bat_priv->orig_hash, compare_orig, + icmp_packet->orig)); ret = NET_RX_DROP; if ((orig_node != NULL) && @@ -979,7 +981,8 @@ int recv_icmp_packet(struct sk_buff *skb, struct batman_if *recv_if) /* get routing information */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, icmp_packet->dst)); + hash_find(bat_priv->orig_hash, compare_orig, + icmp_packet->dst)); if ((orig_node != NULL) && (orig_node->router != NULL)) { @@ -1054,7 +1057,7 @@ struct neigh_node *find_router(struct orig_node *orig_node, router_orig->orig, ETH_ALEN) == 0) { primary_orig_node = router_orig; } else { - primary_orig_node = hash_find(bat_priv->orig_hash, + primary_orig_node = hash_find(bat_priv->orig_hash, compare_orig, router_orig->primary_addr); if (!primary_orig_node) @@ -1160,7 +1163,8 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if, /* get routing information */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, unicast_packet->dest)); + hash_find(bat_priv->orig_hash, compare_orig, + unicast_packet->dest)); router = find_router(orig_node, recv_if); @@ -1306,7 +1310,8 @@ int recv_bcast_packet(struct sk_buff *skb, struct batman_if *recv_if) spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, bcast_packet->orig)); + hash_find(bat_priv->orig_hash, compare_orig, + bcast_packet->orig)); if (orig_node == NULL) { spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); diff --git a/send.c b/send.c index 180e18b..7097ff0 100644 --- a/send.c +++ b/send.c @@ -29,6 +29,7 @@ #include "vis.h" #include "aggregation.h" #include "gateway_common.h" +#include "originator.h" #include "compat.h" diff --git a/translation-table.c b/translation-table.c index 0bb9f6f..a648c57 100644 --- a/translation-table.c +++ b/translation-table.c @@ -24,6 +24,7 @@ #include "soft-interface.h" #include "types.h" #include "hash.h" +#include "originator.h" #include "compat.h" static void hna_local_purge(struct work_struct *work); @@ -42,7 +43,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, compare_orig, choose_orig); + bat_priv->hna_local_hash = hash_new(128, choose_orig); if (!bat_priv->hna_local_hash) return 0; @@ -65,7 +66,7 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); hna_local_entry = ((struct hna_local_entry *)hash_find(bat_priv->hna_local_hash, - addr)); + compare_orig, addr)); spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); if (hna_local_entry) { @@ -108,13 +109,13 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); - hash_add(bat_priv->hna_local_hash, hna_local_entry); + hash_add(bat_priv->hna_local_hash, compare_orig, hna_local_entry); 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, + swaphash = hash_resize(bat_priv->hna_local_hash, compare_orig, bat_priv->hna_local_hash->size * 2); if (!swaphash) @@ -129,7 +130,8 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); hna_global_entry = ((struct hna_global_entry *) - hash_find(bat_priv->hna_global_hash, addr)); + hash_find(bat_priv->hna_global_hash, + compare_orig, addr)); if (hna_global_entry) _hna_global_del_orig(bat_priv, hna_global_entry, @@ -233,7 +235,8 @@ static void hna_local_del(struct bat_priv *bat_priv, bat_dbg(DBG_ROUTES, bat_priv, "Deleting local hna entry (%pM): %s\n", hna_local_entry->addr, message); - hash_remove(bat_priv->hna_local_hash, hna_local_entry->addr); + hash_remove(bat_priv->hna_local_hash, compare_orig, + hna_local_entry->addr); _hna_local_del(hna_local_entry, bat_priv); } @@ -246,7 +249,7 @@ void hna_local_remove(struct bat_priv *bat_priv, spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); hna_local_entry = (struct hna_local_entry *) - hash_find(bat_priv->hna_local_hash, addr); + hash_find(bat_priv->hna_local_hash, compare_orig, addr); if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, message); @@ -296,7 +299,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, compare_orig, choose_orig); + bat_priv->hna_global_hash = hash_new(128, choose_orig); if (!bat_priv->hna_global_hash) return 0; @@ -320,7 +323,8 @@ void hna_global_add_orig(struct bat_priv *bat_priv, hna_ptr = hna_buff + (hna_buff_count * ETH_ALEN); hna_global_entry = (struct hna_global_entry *) - hash_find(bat_priv->hna_global_hash, hna_ptr); + hash_find(bat_priv->hna_global_hash, compare_orig, + hna_ptr); if (!hna_global_entry) { spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, @@ -341,7 +345,8 @@ void hna_global_add_orig(struct bat_priv *bat_priv, hna_global_entry->addr, orig_node->orig); spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); - hash_add(bat_priv->hna_global_hash, hna_global_entry); + hash_add(bat_priv->hna_global_hash, compare_orig, + hna_global_entry); } @@ -353,7 +358,8 @@ void hna_global_add_orig(struct bat_priv *bat_priv, hna_ptr = hna_buff + (hna_buff_count * ETH_ALEN); hna_local_entry = (struct hna_local_entry *) - hash_find(bat_priv->hna_local_hash, hna_ptr); + hash_find(bat_priv->hna_local_hash, compare_orig, + hna_ptr); if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, @@ -380,7 +386,7 @@ void hna_global_add_orig(struct bat_priv *bat_priv, if (bat_priv->hna_global_hash->elements * 4 > bat_priv->hna_global_hash->size) { - swaphash = hash_resize(bat_priv->hna_global_hash, + swaphash = hash_resize(bat_priv->hna_global_hash, compare_orig, bat_priv->hna_global_hash->size * 2); if (!swaphash) @@ -451,7 +457,8 @@ static void _hna_global_del_orig(struct bat_priv *bat_priv, hna_global_entry->addr, hna_global_entry->orig_node->orig, message); - hash_remove(bat_priv->hna_global_hash, hna_global_entry->addr); + hash_remove(bat_priv->hna_global_hash, compare_orig, + hna_global_entry->addr); kfree(hna_global_entry); } @@ -471,7 +478,8 @@ 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); hna_global_entry = (struct hna_global_entry *) - hash_find(bat_priv->hna_global_hash, hna_ptr); + hash_find(bat_priv->hna_global_hash, compare_orig, + hna_ptr); if ((hna_global_entry) && (hna_global_entry->orig_node == orig_node)) @@ -509,7 +517,8 @@ struct orig_node *transtable_search(struct bat_priv *bat_priv, uint8_t *addr) spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); hna_global_entry = (struct hna_global_entry *) - hash_find(bat_priv->hna_global_hash, addr); + hash_find(bat_priv->hna_global_hash, + compare_orig, addr); spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, flags); if (!hna_global_entry) diff --git a/unicast.c b/unicast.c index 6ceaf87..7b3b4da 100644 --- a/unicast.c +++ b/unicast.c @@ -24,6 +24,7 @@ #include "send.h" #include "soft-interface.h" #include "gateway_client.h" +#include "originator.h" #include "hash.h" #include "translation-table.h" #include "routing.h" @@ -180,7 +181,8 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, *new_skb = NULL; spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, unicast_packet->orig)); + hash_find(bat_priv->orig_hash, compare_orig, + unicast_packet->orig)); if (!orig_node) { pr_debug("couldn't find originator in orig_hash\n"); @@ -287,6 +289,7 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv) orig_node = (struct orig_node *)gw_get_selected(bat_priv); else orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, + compare_orig, ethhdr->h_dest)); /* check for hna host */ diff --git a/vis.c b/vis.c index ddfdcd8..ef4ea86 100644 --- a/vis.c +++ b/vis.c @@ -26,6 +26,7 @@ #include "soft-interface.h" #include "hard-interface.h" #include "hash.h" +#include "originator.h" #include "compat.h" #define MAX_VIS_PACKET_SIZE 1000 @@ -371,7 +372,7 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, sizeof(struct vis_packet)); memcpy(search_packet->vis_orig, vis_packet->vis_orig, ETH_ALEN); - old_info = hash_find(bat_priv->vis_hash, &search_elem); + old_info = hash_find(bat_priv->vis_hash, vis_info_cmp, &search_elem); kfree_skb(search_elem.skb_packet); if (old_info != NULL) { @@ -388,7 +389,7 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, } } /* remove old entry */ - hash_remove(bat_priv->vis_hash, old_info); + hash_remove(bat_priv->vis_hash, vis_info_cmp, old_info); send_list_del(old_info); kref_put(&old_info->refcount, free_info); } @@ -429,7 +430,7 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, recv_list_add(bat_priv, &info->recv_list, packet->sender_orig); /* try to add it */ - if (hash_add(bat_priv->vis_hash, info) < 0) { + if (hash_add(bat_priv->vis_hash, vis_info_cmp, info) < 0) { /* did not work (for some reason) */ kref_put(&old_info->refcount, free_info); info = NULL; @@ -718,6 +719,7 @@ static void unicast_vis_packet(struct bat_priv *bat_priv, spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); packet = (struct vis_packet *)info->skb_packet->data; orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, + compare_orig, packet->target_orig)); if ((!orig_node) || (!orig_node->router)) @@ -802,13 +804,14 @@ int vis_init(struct bat_priv *bat_priv) { struct vis_packet *packet; unsigned long flags; + int hash_added; if (bat_priv->vis_hash) return 1; spin_lock_irqsave(&bat_priv->vis_hash_lock, flags); - bat_priv->vis_hash = hash_new(256, vis_info_cmp, vis_info_choose); + bat_priv->vis_hash = hash_new(256, vis_info_choose); if (!bat_priv->vis_hash) { pr_err("Can't initialize vis_hash\n"); goto err; @@ -847,7 +850,9 @@ int vis_init(struct bat_priv *bat_priv) INIT_LIST_HEAD(&bat_priv->vis_send_list); - if (hash_add(bat_priv->vis_hash, bat_priv->my_vis_info) < 0) { + hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, + bat_priv->my_vis_info); + if (hash_added < 0) { pr_err("Can't add own vis packet into hash\n"); /* not in hash, need to remove it manually. */ kref_put(&bat_priv->my_vis_info->refcount, free_info); -- batman-adv

12 years, 5 months

batman-adv; branch, master, updated. v2010.1.0-206-g4983f2a

by postmaster＠open-mesh.org

The following commit has been merged in the master branch: commit f1f2009b633e9e722434c228ef3ffa9e4fba6403 Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Sat Oct 23 01:42:11 2010 +0000 batman-adv: Remove hashdata_choose_cb from hash Function pointers cannot be inlined by a compiler and thus always has the overhead of an call. hashdata_choose_cb's are one of the most often called function pointers and its overhead must kept relative low. As first step, every function which uses this function pointer takes it as parameter instead of storing it inside the hash abstraction structure. This not generate any performance gain right now. The called functions must also be able to be inlined by the calling functions to enable inlining of the function pointer. Reported-by: David S. Miller <davem(a)davemloft.net> Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> diff --git a/hash.c b/hash.c index a4abe14..6361a31 100644 --- a/hash.c +++ b/hash.c @@ -137,7 +137,7 @@ struct hash_it_t *hash_iterate(struct hashtable_t *hash, } /* allocates and clears the hash */ -struct hashtable_t *hash_new(int size, hashdata_choose_cb choose) +struct hashtable_t *hash_new(int size) { struct hashtable_t *hash; @@ -156,13 +156,12 @@ struct hashtable_t *hash_new(int size, hashdata_choose_cb choose) hash_init(hash); - hash->choose = choose; - return hash; } /* adds data to the hashtable. returns 0 on success, -1 on error */ -int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, void *data) +int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, + hashdata_choose_cb choose, void *data) { int index; struct element_t *bucket, *prev_bucket = NULL; @@ -170,7 +169,7 @@ int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, void *data) if (!hash) return -1; - index = hash->choose(data, hash->size); + index = choose(data, hash->size); bucket = hash->table[index]; while (bucket != NULL) { @@ -203,7 +202,7 @@ int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, void *data) /* finds data, based on the key in keydata. returns the found data on success, * or NULL on error */ void *hash_find(struct hashtable_t *hash, hashdata_compare_cb compare, - void *keydata) + hashdata_choose_cb choose, void *keydata) { int index; struct element_t *bucket; @@ -211,7 +210,7 @@ void *hash_find(struct hashtable_t *hash, hashdata_compare_cb compare, if (!hash) return NULL; - index = hash->choose(keydata , hash->size); + index = choose(keydata , hash->size); bucket = hash->table[index]; while (bucket != NULL) { @@ -250,11 +249,11 @@ void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) * structure you use with just the key filled, we just need the key for * comparing. */ void *hash_remove(struct hashtable_t *hash, hashdata_compare_cb compare, - void *data) + hashdata_choose_cb choose, void *data) { struct hash_it_t hash_it_t; - hash_it_t.index = hash->choose(data, hash->size); + hash_it_t.index = choose(data, hash->size); hash_it_t.bucket = hash->table[hash_it_t.index]; hash_it_t.prev_bucket = NULL; @@ -277,14 +276,15 @@ void *hash_remove(struct hashtable_t *hash, hashdata_compare_cb compare, /* resize the hash, returns the pointer to the new hash or NULL on * error. removes the old hash on success. */ struct hashtable_t *hash_resize(struct hashtable_t *hash, - hashdata_compare_cb compare, int size) + hashdata_compare_cb compare, + hashdata_choose_cb choose, int size) { struct hashtable_t *new_hash; struct element_t *bucket; int i; /* initialize a new hash with the new size */ - new_hash = hash_new(size, hash->choose); + new_hash = hash_new(size); if (new_hash == NULL) return NULL; @@ -294,7 +294,7 @@ struct hashtable_t *hash_resize(struct hashtable_t *hash, bucket = hash->table[i]; while (bucket != NULL) { - hash_add(new_hash, compare, bucket->data); + hash_add(new_hash, compare, choose, bucket->data); bucket = bucket->next; } } diff --git a/hash.h b/hash.h index 742277e..85ee12b 100644 --- a/hash.h +++ b/hash.h @@ -32,6 +32,10 @@ * return 0 if same and not 0 if not * same */ typedef int (*hashdata_compare_cb)(void *, void *); + +/* the hashfunction, should return an index + * based on the key in the data of the first + * argument and the size the second */ typedef int (*hashdata_choose_cb)(void *, int); typedef void (*hashdata_free_cb)(void *, void *); @@ -51,13 +55,10 @@ struct hashtable_t { struct element_t **table; /* the hashtable itself, with the buckets */ int elements; /* number of elements registered */ int size; /* size of hashtable */ - hashdata_choose_cb choose; /* the hashfunction, should return an index - * based on the key in the data of the first - * argument and the size the second */ }; /* allocates and clears the hash */ -struct hashtable_t *hash_new(int size, hashdata_choose_cb choose); +struct hashtable_t *hash_new(int size); /* remove bucket (this might be used in hash_iterate() if you already found the * bucket you want to delete and don't need the overhead to find it again with @@ -74,24 +75,26 @@ void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb, void *arg); void hash_destroy(struct hashtable_t *hash); /* adds data to the hashtable. returns 0 on success, -1 on error */ -int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, void *data); +int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, + hashdata_choose_cb choose, void *data); /* removes data from hash, if found. returns pointer do data on success, so you * can remove the used structure yourself, or NULL on error . data could be the * structure you use with just the key filled, we just need the key for * comparing. */ void *hash_remove(struct hashtable_t *hash, hashdata_compare_cb compare, - void *data); + hashdata_choose_cb choose, void *data); /* finds data, based on the key in keydata. returns the found data on success, * or NULL on error */ void *hash_find(struct hashtable_t *hash, hashdata_compare_cb compare, - void *keydata); + hashdata_choose_cb choose, void *keydata); /* resize the hash, returns the pointer to the new hash or NULL on * error. removes the old hash on success */ struct hashtable_t *hash_resize(struct hashtable_t *hash, - hashdata_compare_cb compare, int size); + hashdata_compare_cb compare, + hashdata_choose_cb choose, int size); /* iterate though the hash. first element is selected with iter_in NULL. use * the returned iterator to access the elements until hash_it_t returns NULL. */ diff --git a/icmp_socket.c b/icmp_socket.c index de70752..b9201c5 100644 --- a/icmp_socket.c +++ b/icmp_socket.c @@ -228,7 +228,7 @@ static ssize_t bat_socket_write(struct file *file, const char __user *buff, spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, - compare_orig, + compare_orig, choose_orig, icmp_packet->dst)); if (!orig_node) diff --git a/main.c b/main.c index ecab8b8..9c14832 100644 --- a/main.c +++ b/main.c @@ -159,27 +159,6 @@ int addr_to_string(char *buff, uint8_t *addr) return sprintf(buff, "%pM", addr); } -/* hashfunction to choose an entry in a hash table of given size */ -/* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */ -int choose_orig(void *data, int32_t size) -{ - unsigned char *key = data; - uint32_t hash = 0; - size_t i; - - for (i = 0; i < 6; i++) { - hash += key[i]; - hash += (hash << 10); - hash ^= (hash >> 6); - } - - hash += (hash << 3); - hash ^= (hash >> 11); - hash += (hash << 15); - - return hash % size; -} - int is_my_mac(uint8_t *addr) { struct batman_if *batman_if; diff --git a/main.h b/main.h index c09a9fd..05e4ac8 100644 --- a/main.h +++ b/main.h @@ -139,7 +139,6 @@ void mesh_free(struct net_device *soft_iface); void inc_module_count(void); void dec_module_count(void); int addr_to_string(char *buff, uint8_t *addr); -int choose_orig(void *data, int32_t size); int is_my_mac(uint8_t *addr); int is_bcast(uint8_t *addr); int is_mcast(uint8_t *addr); diff --git a/originator.c b/originator.c index 95ca7ae..d4da99c 100644 --- a/originator.c +++ b/originator.c @@ -47,7 +47,7 @@ int originator_init(struct bat_priv *bat_priv) return 1; spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); - bat_priv->orig_hash = hash_new(128, choose_orig); + bat_priv->orig_hash = hash_new(128); if (!bat_priv->orig_hash) goto err; @@ -130,9 +130,11 @@ 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; orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, - compare_orig, addr)); + compare_orig, choose_orig, + addr)); if (orig_node) return orig_node; @@ -169,11 +171,14 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) if (!orig_node->bcast_own_sum) goto free_bcast_own; - if (hash_add(bat_priv->orig_hash, compare_orig, orig_node) < 0) + hash_added = hash_add(bat_priv->orig_hash, compare_orig, choose_orig, + orig_node); + 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, compare_orig, + choose_orig, bat_priv->orig_hash->size * 2); if (!swaphash) diff --git a/originator.h b/originator.h index ed903dc..d474ceb 100644 --- a/originator.h +++ b/originator.h @@ -40,4 +40,25 @@ static inline int compare_orig(void *data1, void *data2) return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0); } +/* hashfunction to choose an entry in a hash table of given size */ +/* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */ +static inline int choose_orig(void *data, int32_t size) +{ + unsigned char *key = data; + uint32_t hash = 0; + size_t i; + + for (i = 0; i < 6; i++) { + hash += key[i]; + hash += (hash << 10); + hash ^= (hash >> 6); + } + + hash += (hash << 3); + hash ^= (hash >> 11); + hash += (hash << 15); + + return hash % size; +} + #endif /* _NET_BATMAN_ADV_ORIGINATOR_H_ */ diff --git a/routing.c b/routing.c index f12d878..60f23ef 100644 --- a/routing.c +++ b/routing.c @@ -823,7 +823,7 @@ static int recv_my_icmp_packet(struct bat_priv *bat_priv, /* get routing information */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, - compare_orig, + compare_orig, choose_orig, icmp_packet->orig)); ret = NET_RX_DROP; @@ -886,7 +886,7 @@ static int recv_icmp_ttl_exceeded(struct bat_priv *bat_priv, /* get routing information */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, + hash_find(bat_priv->orig_hash, compare_orig, choose_orig, icmp_packet->orig)); ret = NET_RX_DROP; @@ -981,7 +981,7 @@ int recv_icmp_packet(struct sk_buff *skb, struct batman_if *recv_if) /* get routing information */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, + hash_find(bat_priv->orig_hash, compare_orig, choose_orig, icmp_packet->dst)); if ((orig_node != NULL) && @@ -1058,7 +1058,8 @@ struct neigh_node *find_router(struct orig_node *orig_node, primary_orig_node = router_orig; } else { primary_orig_node = hash_find(bat_priv->orig_hash, compare_orig, - router_orig->primary_addr); + choose_orig, + router_orig->primary_addr); if (!primary_orig_node) return orig_node->router; @@ -1163,7 +1164,7 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if, /* get routing information */ spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, + hash_find(bat_priv->orig_hash, compare_orig, choose_orig, unicast_packet->dest)); router = find_router(orig_node, recv_if); @@ -1310,7 +1311,7 @@ int recv_bcast_packet(struct sk_buff *skb, struct batman_if *recv_if) spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, + hash_find(bat_priv->orig_hash, compare_orig, choose_orig, bcast_packet->orig)); if (orig_node == NULL) { diff --git a/translation-table.c b/translation-table.c index a648c57..1e7f583 100644 --- a/translation-table.c +++ b/translation-table.c @@ -43,7 +43,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, choose_orig); + bat_priv->hna_local_hash = hash_new(128); if (!bat_priv->hna_local_hash) return 0; @@ -66,7 +66,8 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); hna_local_entry = ((struct hna_local_entry *)hash_find(bat_priv->hna_local_hash, - compare_orig, addr)); + compare_orig, choose_orig, + addr)); spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); if (hna_local_entry) { @@ -109,13 +110,15 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); - hash_add(bat_priv->hna_local_hash, compare_orig, hna_local_entry); + hash_add(bat_priv->hna_local_hash, compare_orig, choose_orig, + hna_local_entry); 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, compare_orig, + choose_orig, bat_priv->hna_local_hash->size * 2); if (!swaphash) @@ -131,7 +134,7 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr) hna_global_entry = ((struct hna_global_entry *) hash_find(bat_priv->hna_global_hash, - compare_orig, addr)); + compare_orig, choose_orig, addr)); if (hna_global_entry) _hna_global_del_orig(bat_priv, hna_global_entry, @@ -235,7 +238,7 @@ static void hna_local_del(struct bat_priv *bat_priv, bat_dbg(DBG_ROUTES, bat_priv, "Deleting local hna entry (%pM): %s\n", hna_local_entry->addr, message); - hash_remove(bat_priv->hna_local_hash, compare_orig, + hash_remove(bat_priv->hna_local_hash, compare_orig, choose_orig, hna_local_entry->addr); _hna_local_del(hna_local_entry, bat_priv); } @@ -249,7 +252,8 @@ void hna_local_remove(struct bat_priv *bat_priv, spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); hna_local_entry = (struct hna_local_entry *) - hash_find(bat_priv->hna_local_hash, compare_orig, addr); + hash_find(bat_priv->hna_local_hash, compare_orig, choose_orig, + addr); if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, message); @@ -299,7 +303,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, choose_orig); + bat_priv->hna_global_hash = hash_new(128); if (!bat_priv->hna_global_hash) return 0; @@ -324,7 +328,7 @@ void hna_global_add_orig(struct bat_priv *bat_priv, hna_ptr = hna_buff + (hna_buff_count * ETH_ALEN); hna_global_entry = (struct hna_global_entry *) hash_find(bat_priv->hna_global_hash, compare_orig, - hna_ptr); + choose_orig, hna_ptr); if (!hna_global_entry) { spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, @@ -346,7 +350,7 @@ void hna_global_add_orig(struct bat_priv *bat_priv, spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); hash_add(bat_priv->hna_global_hash, compare_orig, - hna_global_entry); + choose_orig, hna_global_entry); } @@ -359,7 +363,7 @@ void hna_global_add_orig(struct bat_priv *bat_priv, hna_ptr = hna_buff + (hna_buff_count * ETH_ALEN); hna_local_entry = (struct hna_local_entry *) hash_find(bat_priv->hna_local_hash, compare_orig, - hna_ptr); + choose_orig, hna_ptr); if (hna_local_entry) hna_local_del(bat_priv, hna_local_entry, @@ -387,6 +391,7 @@ void hna_global_add_orig(struct bat_priv *bat_priv, if (bat_priv->hna_global_hash->elements * 4 > bat_priv->hna_global_hash->size) { swaphash = hash_resize(bat_priv->hna_global_hash, compare_orig, + choose_orig, bat_priv->hna_global_hash->size * 2); if (!swaphash) @@ -457,7 +462,7 @@ static void _hna_global_del_orig(struct bat_priv *bat_priv, hna_global_entry->addr, hna_global_entry->orig_node->orig, message); - hash_remove(bat_priv->hna_global_hash, compare_orig, + hash_remove(bat_priv->hna_global_hash, compare_orig, choose_orig, hna_global_entry->addr); kfree(hna_global_entry); } @@ -479,7 +484,7 @@ void hna_global_del_orig(struct bat_priv *bat_priv, hna_ptr = orig_node->hna_buff + (hna_buff_count * ETH_ALEN); hna_global_entry = (struct hna_global_entry *) hash_find(bat_priv->hna_global_hash, compare_orig, - hna_ptr); + choose_orig, hna_ptr); if ((hna_global_entry) && (hna_global_entry->orig_node == orig_node)) @@ -518,7 +523,7 @@ struct orig_node *transtable_search(struct bat_priv *bat_priv, uint8_t *addr) spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); hna_global_entry = (struct hna_global_entry *) hash_find(bat_priv->hna_global_hash, - compare_orig, addr); + compare_orig, choose_orig, addr); spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, flags); if (!hna_global_entry) diff --git a/unicast.c b/unicast.c index 7b3b4da..b82e9e3 100644 --- a/unicast.c +++ b/unicast.c @@ -181,7 +181,7 @@ int frag_reassemble_skb(struct sk_buff *skb, struct bat_priv *bat_priv, *new_skb = NULL; spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); orig_node = ((struct orig_node *) - hash_find(bat_priv->orig_hash, compare_orig, + hash_find(bat_priv->orig_hash, compare_orig, choose_orig, unicast_packet->orig)); if (!orig_node) { @@ -290,6 +290,7 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv) else orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, compare_orig, + choose_orig, ethhdr->h_dest)); /* check for hna host */ diff --git a/vis.c b/vis.c index ef4ea86..88402c9 100644 --- a/vis.c +++ b/vis.c @@ -358,6 +358,7 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, struct vis_packet *search_packet, *old_packet; struct vis_info search_elem; struct vis_packet *packet; + int hash_added; *is_new = 0; /* sanity check */ @@ -372,7 +373,8 @@ 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); - old_info = hash_find(bat_priv->vis_hash, vis_info_cmp, &search_elem); + old_info = hash_find(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, + &search_elem); kfree_skb(search_elem.skb_packet); if (old_info != NULL) { @@ -389,7 +391,8 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, } } /* remove old entry */ - hash_remove(bat_priv->vis_hash, vis_info_cmp, old_info); + hash_remove(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, + old_info); send_list_del(old_info); kref_put(&old_info->refcount, free_info); } @@ -430,7 +433,9 @@ static struct vis_info *add_packet(struct bat_priv *bat_priv, recv_list_add(bat_priv, &info->recv_list, packet->sender_orig); /* try to add it */ - if (hash_add(bat_priv->vis_hash, vis_info_cmp, info) < 0) { + hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, + info); + if (hash_added < 0) { /* did not work (for some reason) */ kref_put(&old_info->refcount, free_info); info = NULL; @@ -719,7 +724,7 @@ static void unicast_vis_packet(struct bat_priv *bat_priv, spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); packet = (struct vis_packet *)info->skb_packet->data; orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, - compare_orig, + compare_orig, choose_orig, packet->target_orig)); if ((!orig_node) || (!orig_node->router)) @@ -811,7 +816,7 @@ int vis_init(struct bat_priv *bat_priv) spin_lock_irqsave(&bat_priv->vis_hash_lock, flags); - bat_priv->vis_hash = hash_new(256, vis_info_choose); + bat_priv->vis_hash = hash_new(256); if (!bat_priv->vis_hash) { pr_err("Can't initialize vis_hash\n"); goto err; @@ -850,7 +855,7 @@ int vis_init(struct bat_priv *bat_priv) INIT_LIST_HEAD(&bat_priv->vis_send_list); - hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, + hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, bat_priv->my_vis_info); if (hash_added < 0) { pr_err("Can't add own vis packet into hash\n"); -- batman-adv

12 years, 5 months

batman-adv; branch, master, updated. v2010.1.0-201-gd777073

by postmaster＠open-mesh.org

The following commit has been merged in the master branch: commit d777073eb0b7c373e8ffe26da2241f69bb373396 Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Thu Oct 21 15:50:08 2010 +0000 batman-adv: Remove space before tab in bat_sysfs.c Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> diff --git a/bat_sysfs.c b/bat_sysfs.c index dbb0208..5ea5c11 100644 --- a/bat_sysfs.c +++ b/bat_sysfs.c @@ -80,7 +80,7 @@ ssize_t store_##_name(struct kobject *kobj, struct attribute *attr, \ } #define BAT_ATTR_SHOW_UINT(_name) \ -ssize_t show_##_name(struct kobject *kobj, struct attribute *attr, \ +ssize_t show_##_name(struct kobject *kobj, struct attribute *attr, \ char *buff) \ { \ struct bat_priv *bat_priv = kobj_to_batpriv(kobj); \ -- batman-adv

12 years, 5 months

linux integration; annotated tag, v2.6.36, created. v2.6.36

by postmaster＠open-mesh.org

The annotated tag, v2.6.36 has been created at 25427f38d3b791d986812cb81c68df38e8249ef8 (tag) tagging f6f94e2ab1b33f0082ac22d71f66385a60d8157f (commit) replaces v2.6.36-rc8 tagged by Linus Torvalds on Wed Oct 20 13:31:18 2010 -0700 - Shortlog ------------------------------------------------------------ Linux 2.6.36 The latest and greatest, and totally bug-free. At least until 2.6.37 comes along and shoves it under a speeding train like some kind of a bully. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) iEYEABECAAYFAky/UcwACgkQF3YsRnbiHLvg/ACffKjAb1fD6fpqcHbSijHHpbP3 4SkAnR4xOy7iKhmfS50ZrVsOkFFTuBHG =JD3z -----END PGP SIGNATURE----- ----------------------------------------------------------------------- -- linux integration

12 years, 5 months

linux integration; tag, GregKH-20101018, created. v2.6.36-rc8-527-g4f5cbb3

by postmaster＠open-mesh.org

The tag, GregKH-20101018 has been created at 4f5cbb3ec93661322de87d9756e9a38c7708d268 (commit) - Shortlog ------------------------------------------------------------ commit 4f5cbb3ec93661322de87d9756e9a38c7708d268 Merge: 2cb7c23 cd07202 Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Tue Oct 19 02:47:17 2010 +0200 Merge commit 'v2.6.36-rc8' into linux Conflicts: drivers/staging/batman-adv/hard-interface.c ----------------------------------------------------------------------- -- linux integration

12 years, 5 months

linux integration; branch, linux, updated. v2.6.36-rc8-527-g4f5cbb3

by postmaster＠open-mesh.org

The following commit has been merged in the linux branch: commit 2cb7c23024a5b440b29498adc1f46d9c3aebe81c Merge: c47f2d31185ac7c53d5e495b0a7124602527f38d 050ada5d7cdcc7d68b630af6eb6c477011867ead Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Tue Oct 19 02:13:39 2010 +0200 Merge remote branch 'origin/next' into linux Conflicts: drivers/staging/batman-adv/Makefile.kbuild drivers/staging/batman-adv/bat_printk.c drivers/staging/batman-adv/compat.h drivers/staging/batman-adv/sysfs-class-net-mesh diff --combined drivers/staging/batman-adv/Makefile index 4b5c434,0000000..7892428 mode 100644,000000..100644 --- a/drivers/staging/batman-adv/Makefile +++ b/drivers/staging/batman-adv/Makefile @@@ -1,22 -1,0 +1,22 @@@ +# +# Copyright (C) 2007-2010 B.A.T.M.A.N. contributors: +# +# Marek Lindner, Simon Wunderlich +# +# This program is free software; you can redistribute it and/or +# modify it under the terms of version 2 of the GNU General Public +# License as published by the Free Software Foundation. +# +# This program is distributed in the hope that it will be useful, but +# WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +# 02110-1301, USA +# + +obj-$(CONFIG_BATMAN_ADV) += batman-adv.o - batman-adv-objs := main.o bat_debugfs.o bat_sysfs.o send.o routing.o soft-interface.o icmp_socket.o translation-table.o bitarray.o hash.o ring_buffer.o vis.o hard-interface.o aggregation.o originator.o unicast.o ++batman-adv-y := main.o bat_debugfs.o bat_sysfs.o send.o routing.o soft-interface.o icmp_socket.o translation-table.o bitarray.o hash.o ring_buffer.o vis.o hard-interface.o aggregation.o originator.o unicast.o diff --combined drivers/staging/batman-adv/aggregation.c index 46b9c2b,08624d4..08624d4 --- a/drivers/staging/batman-adv/aggregation.c +++ b/drivers/staging/batman-adv/aggregation.c @@@ -123,8 -123,14 +123,14 @@@ static void new_aggregated_packet(unsig return; } - forw_packet_aggr->skb = dev_alloc_skb(MAX_AGGREGATION_BYTES + - sizeof(struct ethhdr)); + if ((atomic_read(&bat_priv->aggregation_enabled)) && + (packet_len < MAX_AGGREGATION_BYTES)) + forw_packet_aggr->skb = dev_alloc_skb(MAX_AGGREGATION_BYTES + + sizeof(struct ethhdr)); + else + forw_packet_aggr->skb = dev_alloc_skb(packet_len + + sizeof(struct ethhdr)); + if (!forw_packet_aggr->skb) { if (!own_packet) atomic_inc(&bat_priv->batman_queue_left); @@@ -251,9 -257,7 +257,7 @@@ void receive_aggr_bat_packet(struct eth batman_packet = (struct batman_packet *)packet_buff; - while (aggregated_packet(buff_pos, packet_len, - batman_packet->num_hna)) { - + do { /* network to host order for our 32bit seqno, and the orig_interval. */ batman_packet->seqno = ntohl(batman_packet->seqno); @@@ -266,5 -270,6 +270,6 @@@ buff_pos += BAT_PACKET_LEN + hna_len(batman_packet); batman_packet = (struct batman_packet *) (packet_buff + buff_pos); - } + } while (aggregated_packet(buff_pos, packet_len, + batman_packet->num_hna)); } diff --combined drivers/staging/batman-adv/originator.c index c530df1,0000000..865211d mode 100644,000000..100644 --- a/drivers/staging/batman-adv/originator.c +++ b/drivers/staging/batman-adv/originator.c @@@ -1,537 -1,0 +1,537 @@@ +/* + * Copyright (C) 2009-2010 B.A.T.M.A.N. contributors: + * + * Marek Lindner, Simon Wunderlich + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +/* increase the reference counter for this originator */ + +#include "main.h" +#include "originator.h" +#include "hash.h" +#include "translation-table.h" +#include "routing.h" +#include "hard-interface.h" +#include "unicast.h" + +static void purge_orig(struct work_struct *work); + +static void start_purge_timer(struct bat_priv *bat_priv) +{ + INIT_DELAYED_WORK(&bat_priv->orig_work, purge_orig); + queue_delayed_work(bat_event_workqueue, &bat_priv->orig_work, 1 * HZ); +} + +int originator_init(struct bat_priv *bat_priv) +{ + unsigned long flags; + if (bat_priv->orig_hash) + return 1; + + spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); + bat_priv->orig_hash = hash_new(128, compare_orig, choose_orig); + + if (!bat_priv->orig_hash) + goto err; + + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); + start_purge_timer(bat_priv); + return 1; + +err: + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); + 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) +{ + struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface); + struct neigh_node *neigh_node; + + bat_dbg(DBG_BATMAN, bat_priv, + "Creating new last-hop neighbor of originator\n"); + + neigh_node = kzalloc(sizeof(struct neigh_node), GFP_ATOMIC); + if (!neigh_node) + return NULL; + + INIT_LIST_HEAD(&neigh_node->list); + + memcpy(neigh_node->addr, neigh, ETH_ALEN); + neigh_node->orig_node = orig_neigh_node; + neigh_node->if_incoming = if_incoming; + + list_add_tail(&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 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); + kfree(neigh_node); + } + + frag_list_free(&orig_node->frag_list); + hna_global_del_orig(bat_priv, orig_node, "originator timed out"); + + kfree(orig_node->bcast_own); + kfree(orig_node->bcast_own_sum); + kfree(orig_node); +} + +void originator_free(struct bat_priv *bat_priv) +{ + unsigned long flags; + + if (!bat_priv->orig_hash) + return; + + cancel_delayed_work_sync(&bat_priv->orig_work); + + spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); + hash_delete(bat_priv->orig_hash, free_orig_node, bat_priv); + bat_priv->orig_hash = NULL; + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); +} + +/* this function finds or creates an originator entry for the given + * address if it does not exits */ +struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr) +{ + struct orig_node *orig_node; + struct hashtable_t *swaphash; + int size; + + orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash, addr)); + + if (orig_node) + return orig_node; + + bat_dbg(DBG_BATMAN, bat_priv, + "Creating new originator: %pM\n", addr); + + orig_node = kzalloc(sizeof(struct orig_node), GFP_ATOMIC); + if (!orig_node) + return NULL; + + INIT_LIST_HEAD(&orig_node->neigh_list); + + memcpy(orig_node->orig, addr, ETH_ALEN); + orig_node->router = NULL; + orig_node->hna_buff = NULL; + orig_node->bcast_seqno_reset = jiffies - 1 + - msecs_to_jiffies(RESET_PROTECTION_MS); + orig_node->batman_seqno_reset = jiffies - 1 + - msecs_to_jiffies(RESET_PROTECTION_MS); + + size = bat_priv->num_ifaces * sizeof(TYPE_OF_WORD) * NUM_WORDS; + + orig_node->bcast_own = kzalloc(size, GFP_ATOMIC); + if (!orig_node->bcast_own) + goto free_orig_node; + + size = bat_priv->num_ifaces * sizeof(uint8_t); + orig_node->bcast_own_sum = kzalloc(size, GFP_ATOMIC); + + INIT_LIST_HEAD(&orig_node->frag_list); + orig_node->last_frag_packet = 0; + + if (!orig_node->bcast_own_sum) + goto free_bcast_own; + + if (hash_add(bat_priv->orig_hash, orig_node) < 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, + 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); +free_bcast_own: + kfree(orig_node->bcast_own); +free_orig_node: + kfree(orig_node); + return NULL; +} + +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 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); + + if ((time_after(jiffies, + neigh_node->last_valid + PURGE_TIMEOUT * HZ)) || + (neigh_node->if_incoming->if_status == IF_INACTIVE) || + (neigh_node->if_incoming->if_status == IF_TO_BE_REMOVED)) { + + if (neigh_node->if_incoming->if_status == + IF_TO_BE_REMOVED) + bat_dbg(DBG_BATMAN, bat_priv, + "neighbor purge: originator %pM, " + "neighbor: %pM, iface: %s\n", + orig_node->orig, neigh_node->addr, + neigh_node->if_incoming->net_dev->name); + else + bat_dbg(DBG_BATMAN, bat_priv, + "neighbor timeout: originator %pM, " + "neighbor: %pM, last_valid: %lu\n", + orig_node->orig, neigh_node->addr, + (neigh_node->last_valid / HZ)); + + neigh_purged = true; + list_del(list_pos); + kfree(neigh_node); + } else { + if ((*best_neigh_node == NULL) || + (neigh_node->tq_avg > (*best_neigh_node)->tq_avg)) + *best_neigh_node = neigh_node; + } + } + return neigh_purged; +} + +static bool purge_orig_node(struct bat_priv *bat_priv, + struct orig_node *orig_node) +{ + struct neigh_node *best_neigh_node; + + if (time_after(jiffies, + orig_node->last_valid + 2 * PURGE_TIMEOUT * HZ)) { + + bat_dbg(DBG_BATMAN, bat_priv, + "Originator timeout: originator %pM, last_valid %lu\n", + orig_node->orig, (orig_node->last_valid / HZ)); + return true; + } else { + if (purge_orig_neighbors(bat_priv, orig_node, + &best_neigh_node)) { + update_routes(bat_priv, orig_node, + best_neigh_node, + orig_node->hna_buff, + orig_node->hna_buff_len); + /* update bonding candidates, we could have lost + * some candidates. */ + update_bonding_candidates(bat_priv, orig_node); + } + } + + return false; +} + +static void _purge_orig(struct bat_priv *bat_priv) +{ + HASHIT(hashit); + struct orig_node *orig_node; + unsigned long flags; + + spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); + + /* for all origins... */ + while (hash_iterate(bat_priv->orig_hash, &hashit)) { + orig_node = hashit.bucket->data; + + if (purge_orig_node(bat_priv, orig_node)) { + hash_remove_bucket(bat_priv->orig_hash, &hashit); + free_orig_node(orig_node, bat_priv); + } + + if (time_after(jiffies, (orig_node->last_frag_packet + + msecs_to_jiffies(FRAG_TIMEOUT)))) + frag_list_free(&orig_node->frag_list); + } + + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); + +} + +static void purge_orig(struct work_struct *work) +{ + struct delayed_work *delayed_work = + container_of(work, struct delayed_work, work); + struct bat_priv *bat_priv = + container_of(delayed_work, struct bat_priv, orig_work); + + _purge_orig(bat_priv); + start_purge_timer(bat_priv); +} + +void purge_orig_ref(struct bat_priv *bat_priv) +{ + _purge_orig(bat_priv); +} + +int orig_seq_print_text(struct seq_file *seq, void *offset) +{ + HASHIT(hashit); + struct net_device *net_dev = (struct net_device *)seq->private; + struct bat_priv *bat_priv = netdev_priv(net_dev); + struct orig_node *orig_node; + struct neigh_node *neigh_node; + int batman_count = 0; + int last_seen_secs; + int last_seen_msecs; + unsigned long flags; + char orig_str[ETH_STR_LEN], router_str[ETH_STR_LEN]; + + if ((!bat_priv->primary_if) || + (bat_priv->primary_if->if_status != IF_ACTIVE)) { + if (!bat_priv->primary_if) + return seq_printf(seq, "BATMAN mesh %s disabled - " + "please specify interfaces to enable it\n", + net_dev->name); + + return seq_printf(seq, "BATMAN mesh %s " + "disabled - primary interface not active\n", + net_dev->name); + } + + seq_printf(seq, "[B.A.T.M.A.N. adv %s%s, MainIF/MAC: %s/%s (%s)]\n", + SOURCE_VERSION, REVISION_VERSION_STR, + bat_priv->primary_if->net_dev->name, + bat_priv->primary_if->addr_str, net_dev->name); + seq_printf(seq, " %-15s %s (%s/%i) %17s [%10s]: %20s ...\n", + "Originator", "last-seen", "#", TQ_MAX_VALUE, "Nexthop", + "outgoingIF", "Potential nexthops"); + + spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); + + while (hash_iterate(bat_priv->orig_hash, &hashit)) { + + orig_node = hashit.bucket->data; + + if (!orig_node->router) + continue; + + if (orig_node->router->tq_avg == 0) + continue; + + addr_to_string(orig_str, orig_node->orig); + addr_to_string(router_str, orig_node->router->addr); + last_seen_secs = jiffies_to_msecs(jiffies - + orig_node->last_valid) / 1000; + last_seen_msecs = jiffies_to_msecs(jiffies - + orig_node->last_valid) % 1000; + + seq_printf(seq, "%-17s %4i.%03is (%3i) %17s [%10s]:", + orig_str, last_seen_secs, last_seen_msecs, + orig_node->router->tq_avg, router_str, + orig_node->router->if_incoming->net_dev->name); + + list_for_each_entry(neigh_node, &orig_node->neigh_list, list) { + addr_to_string(orig_str, neigh_node->addr); + seq_printf(seq, " %17s (%3i)", orig_str, + neigh_node->tq_avg); + } + + seq_printf(seq, "\n"); + batman_count++; + } + + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); + + if ((batman_count == 0)) + seq_printf(seq, "No batman nodes in range ...\n"); + + return 0; +} + +static int orig_node_add_if(struct orig_node *orig_node, int max_if_num) +{ + void *data_ptr; + + data_ptr = kmalloc(max_if_num * sizeof(TYPE_OF_WORD) * NUM_WORDS, + GFP_ATOMIC); + if (!data_ptr) { + pr_err("Can't resize orig: out of memory\n"); + return -1; + } + + memcpy(data_ptr, orig_node->bcast_own, + (max_if_num - 1) * sizeof(TYPE_OF_WORD) * NUM_WORDS); + kfree(orig_node->bcast_own); + orig_node->bcast_own = data_ptr; + + data_ptr = kmalloc(max_if_num * sizeof(uint8_t), GFP_ATOMIC); + if (!data_ptr) { + pr_err("Can't resize orig: out of memory\n"); + return -1; + } + + memcpy(data_ptr, orig_node->bcast_own_sum, + (max_if_num - 1) * sizeof(uint8_t)); + kfree(orig_node->bcast_own_sum); + orig_node->bcast_own_sum = data_ptr; + + return 0; +} + +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; + unsigned long flags; + HASHIT(hashit); + + /* resize all orig nodes because orig_node->bcast_own(_sum) depend on + * if_num */ + spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); + + while (hash_iterate(bat_priv->orig_hash, &hashit)) { + orig_node = hashit.bucket->data; + + if (orig_node_add_if(orig_node, max_if_num) == -1) + goto err; + } + + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); + return 0; + +err: + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); + return -ENOMEM; +} + +static int orig_node_del_if(struct orig_node *orig_node, + int max_if_num, int del_if_num) +{ + void *data_ptr = NULL; + int chunk_size; + + /* last interface was removed */ + if (max_if_num == 0) + goto free_bcast_own; + + chunk_size = sizeof(TYPE_OF_WORD) * NUM_WORDS; + data_ptr = kmalloc(max_if_num * chunk_size, GFP_ATOMIC); + if (!data_ptr) { + pr_err("Can't resize orig: out of memory\n"); + return -1; + } + + /* copy first part */ + memcpy(data_ptr, orig_node->bcast_own, del_if_num * chunk_size); + + /* copy second part */ - memcpy(data_ptr, ++ memcpy(data_ptr + del_if_num * chunk_size, + orig_node->bcast_own + ((del_if_num + 1) * chunk_size), + (max_if_num - del_if_num) * chunk_size); + +free_bcast_own: + kfree(orig_node->bcast_own); + orig_node->bcast_own = data_ptr; + + if (max_if_num == 0) + goto free_own_sum; + + data_ptr = kmalloc(max_if_num * sizeof(uint8_t), GFP_ATOMIC); + if (!data_ptr) { + pr_err("Can't resize orig: out of memory\n"); + return -1; + } + + memcpy(data_ptr, orig_node->bcast_own_sum, + del_if_num * sizeof(uint8_t)); + - memcpy(data_ptr, ++ memcpy(data_ptr + del_if_num * sizeof(uint8_t), + orig_node->bcast_own_sum + ((del_if_num + 1) * sizeof(uint8_t)), + (max_if_num - del_if_num) * sizeof(uint8_t)); + +free_own_sum: + kfree(orig_node->bcast_own_sum); + orig_node->bcast_own_sum = data_ptr; + + return 0; +} + +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 batman_if *batman_if_tmp; + struct orig_node *orig_node; + unsigned long flags; + HASHIT(hashit); + int ret; + + /* resize all orig nodes because orig_node->bcast_own(_sum) depend on + * if_num */ + spin_lock_irqsave(&bat_priv->orig_hash_lock, flags); + + while (hash_iterate(bat_priv->orig_hash, &hashit)) { + orig_node = hashit.bucket->data; + + ret = orig_node_del_if(orig_node, max_if_num, + batman_if->if_num); + + if (ret == -1) + goto err; + } + + /* renumber remaining batman interfaces _inside_ of orig_hash_lock */ + rcu_read_lock(); + list_for_each_entry_rcu(batman_if_tmp, &if_list, list) { + if (batman_if_tmp->if_status == IF_NOT_IN_USE) + continue; + + if (batman_if == batman_if_tmp) + continue; + + if (batman_if->soft_iface != batman_if_tmp->soft_iface) + continue; + + if (batman_if_tmp->if_num > batman_if->if_num) + batman_if_tmp->if_num--; + } + rcu_read_unlock(); + + batman_if->if_num = -1; + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); + return 0; + +err: + spin_unlock_irqrestore(&bat_priv->orig_hash_lock, flags); + return -ENOMEM; +} diff --combined drivers/staging/batman-adv/send.c index 5d57ef5,0000000..9032861 mode 100644,000000..100644 --- a/drivers/staging/batman-adv/send.c +++ b/drivers/staging/batman-adv/send.c @@@ -1,577 -1,0 +1,580 @@@ +/* + * Copyright (C) 2007-2010 B.A.T.M.A.N. contributors: + * + * Marek Lindner, Simon Wunderlich + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#include "main.h" +#include "send.h" +#include "routing.h" +#include "translation-table.h" +#include "soft-interface.h" +#include "hard-interface.h" +#include "types.h" +#include "vis.h" +#include "aggregation.h" + + +static void send_outstanding_bcast_packet(struct work_struct *work); + +/* apply hop penalty for a normal link */ +static uint8_t hop_penalty(const uint8_t tq) +{ + return (tq * (TQ_MAX_VALUE - TQ_HOP_PENALTY)) / (TQ_MAX_VALUE); +} + +/* when do we schedule our own packet to be sent */ +static unsigned long own_send_time(struct bat_priv *bat_priv) +{ + return jiffies + msecs_to_jiffies( + atomic_read(&bat_priv->orig_interval) - + JITTER + (random32() % 2*JITTER)); +} + +/* when do we schedule a forwarded packet to be sent */ +static unsigned long forward_send_time(struct bat_priv *bat_priv) +{ + return jiffies + msecs_to_jiffies(random32() % (JITTER/2)); +} + +/* send out an already prepared packet to the given address via the + * specified batman interface */ +int send_skb_packet(struct sk_buff *skb, + struct batman_if *batman_if, + uint8_t *dst_addr) +{ + struct ethhdr *ethhdr; + + if (batman_if->if_status != IF_ACTIVE) + goto send_skb_err; + + if (unlikely(!batman_if->net_dev)) + goto send_skb_err; + + if (!(batman_if->net_dev->flags & IFF_UP)) { + pr_warning("Interface %s is not up - can't send packet via " + "that interface!\n", batman_if->net_dev->name); + goto send_skb_err; + } + + /* push to the ethernet header. */ + if (my_skb_head_push(skb, sizeof(struct ethhdr)) < 0) + goto send_skb_err; + + skb_reset_mac_header(skb); + + ethhdr = (struct ethhdr *) skb_mac_header(skb); + memcpy(ethhdr->h_source, batman_if->net_dev->dev_addr, ETH_ALEN); + memcpy(ethhdr->h_dest, dst_addr, ETH_ALEN); + ethhdr->h_proto = __constant_htons(ETH_P_BATMAN); + + skb_set_network_header(skb, ETH_HLEN); + skb->priority = TC_PRIO_CONTROL; + skb->protocol = __constant_htons(ETH_P_BATMAN); + + skb->dev = batman_if->net_dev; + + /* dev_queue_xmit() returns a negative result on error. However on + * congestion and traffic shaping, it drops and returns NET_XMIT_DROP + * (which is > 0). This will not be treated as an error. */ + + return dev_queue_xmit(skb); +send_skb_err: + kfree_skb(skb); + return NET_XMIT_DROP; +} + +/* Send a packet to a given interface */ +static void send_packet_to_if(struct forw_packet *forw_packet, + struct batman_if *batman_if) +{ + struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); + char *fwd_str; + uint8_t packet_num; + int16_t buff_pos; + struct batman_packet *batman_packet; + struct sk_buff *skb; + + if (batman_if->if_status != IF_ACTIVE) + return; + + packet_num = 0; + buff_pos = 0; + batman_packet = (struct batman_packet *)forw_packet->skb->data; + + /* adjust all flags and log packets */ + while (aggregated_packet(buff_pos, + forw_packet->packet_len, + batman_packet->num_hna)) { + + /* we might have aggregated direct link packets with an + * ordinary base packet */ + if ((forw_packet->direct_link_flags & (1 << packet_num)) && + (forw_packet->if_incoming == batman_if)) + batman_packet->flags |= DIRECTLINK; + else + batman_packet->flags &= ~DIRECTLINK; + + fwd_str = (packet_num > 0 ? "Forwarding" : (forw_packet->own ? + "Sending own" : + "Forwarding")); + bat_dbg(DBG_BATMAN, bat_priv, + "%s %spacket (originator %pM, seqno %d, TQ %d, TTL %d," + " IDF %s) on interface %s [%s]\n", + fwd_str, (packet_num > 0 ? "aggregated " : ""), + batman_packet->orig, ntohl(batman_packet->seqno), + batman_packet->tq, batman_packet->ttl, + (batman_packet->flags & DIRECTLINK ? + "on" : "off"), + batman_if->net_dev->name, batman_if->addr_str); + + buff_pos += sizeof(struct batman_packet) + + (batman_packet->num_hna * ETH_ALEN); + packet_num++; + batman_packet = (struct batman_packet *) + (forw_packet->skb->data + buff_pos); + } + + /* create clone because function is called more than once */ + skb = skb_clone(forw_packet->skb, GFP_ATOMIC); + if (skb) + send_skb_packet(skb, batman_if, broadcast_addr); +} + +/* send a batman packet */ +static void send_packet(struct forw_packet *forw_packet) +{ + struct batman_if *batman_if; - struct net_device *soft_iface = forw_packet->if_incoming->soft_iface; - struct bat_priv *bat_priv = netdev_priv(soft_iface); ++ struct net_device *soft_iface; ++ struct bat_priv *bat_priv; + struct batman_packet *batman_packet = + (struct batman_packet *)(forw_packet->skb->data); + unsigned char directlink = (batman_packet->flags & DIRECTLINK ? 1 : 0); + + if (!forw_packet->if_incoming) { + pr_err("Error - can't forward packet: incoming iface not " + "specified\n"); + return; + } + ++ soft_iface = forw_packet->if_incoming->soft_iface; ++ bat_priv = netdev_priv(soft_iface); ++ + if (forw_packet->if_incoming->if_status != IF_ACTIVE) + return; + + /* multihomed peer assumed */ + /* non-primary OGMs are only broadcasted on their interface */ + if ((directlink && (batman_packet->ttl == 1)) || + (forw_packet->own && (forw_packet->if_incoming->if_num > 0))) { + + /* FIXME: what about aggregated packets ? */ + bat_dbg(DBG_BATMAN, bat_priv, + "%s packet (originator %pM, seqno %d, TTL %d) " + "on interface %s [%s]\n", + (forw_packet->own ? "Sending own" : "Forwarding"), + batman_packet->orig, ntohl(batman_packet->seqno), + batman_packet->ttl, + forw_packet->if_incoming->net_dev->name, + forw_packet->if_incoming->addr_str); + + /* skb is only used once and than forw_packet is free'd */ + send_skb_packet(forw_packet->skb, forw_packet->if_incoming, + broadcast_addr); + forw_packet->skb = NULL; + + return; + } + + /* broadcast on every interface */ + rcu_read_lock(); + list_for_each_entry_rcu(batman_if, &if_list, list) { + if (batman_if->soft_iface != soft_iface) + continue; + + send_packet_to_if(forw_packet, batman_if); + } + rcu_read_unlock(); +} + +static void rebuild_batman_packet(struct bat_priv *bat_priv, + struct batman_if *batman_if) +{ + int new_len; + unsigned char *new_buff; + struct batman_packet *batman_packet; + + new_len = sizeof(struct batman_packet) + + (bat_priv->num_local_hna * ETH_ALEN); + new_buff = kmalloc(new_len, GFP_ATOMIC); + + /* keep old buffer if kmalloc should fail */ + if (new_buff) { + memcpy(new_buff, batman_if->packet_buff, + sizeof(struct batman_packet)); + batman_packet = (struct batman_packet *)new_buff; + + batman_packet->num_hna = hna_local_fill_buffer(bat_priv, + new_buff + sizeof(struct batman_packet), + new_len - sizeof(struct batman_packet)); + + kfree(batman_if->packet_buff); + batman_if->packet_buff = new_buff; + batman_if->packet_len = new_len; + } +} + +void schedule_own_packet(struct batman_if *batman_if) +{ + struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface); + unsigned long send_time; + struct batman_packet *batman_packet; + int vis_server; + + if ((batman_if->if_status == IF_NOT_IN_USE) || + (batman_if->if_status == IF_TO_BE_REMOVED)) + return; + + vis_server = atomic_read(&bat_priv->vis_mode); + + /** + * the interface gets activated here to avoid race conditions between + * the moment of activating the interface in + * hardif_activate_interface() where the originator mac is set and + * outdated packets (especially uninitialized mac addresses) in the + * packet queue + */ + if (batman_if->if_status == IF_TO_BE_ACTIVATED) + batman_if->if_status = IF_ACTIVE; + + /* if local hna has changed and interface is a primary interface */ + if ((atomic_read(&bat_priv->hna_local_changed)) && + (batman_if == bat_priv->primary_if)) + rebuild_batman_packet(bat_priv, batman_if); + + /** + * NOTE: packet_buff might just have been re-allocated in + * rebuild_batman_packet() + */ + batman_packet = (struct batman_packet *)batman_if->packet_buff; + + /* change sequence number to network order */ + batman_packet->seqno = + htonl((uint32_t)atomic_read(&batman_if->seqno)); + + if (vis_server == VIS_TYPE_SERVER_SYNC) + batman_packet->flags |= VIS_SERVER; + else + batman_packet->flags &= ~VIS_SERVER; + + atomic_inc(&batman_if->seqno); + + slide_own_bcast_window(batman_if); + send_time = own_send_time(bat_priv); + add_bat_packet_to_list(bat_priv, + batman_if->packet_buff, + batman_if->packet_len, + batman_if, 1, send_time); +} + +void schedule_forward_packet(struct orig_node *orig_node, + struct ethhdr *ethhdr, + struct batman_packet *batman_packet, + uint8_t directlink, int hna_buff_len, + struct batman_if *if_incoming) +{ + struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface); + unsigned char in_tq, in_ttl, tq_avg = 0; + unsigned long send_time; + + if (batman_packet->ttl <= 1) { + bat_dbg(DBG_BATMAN, bat_priv, "ttl exceeded\n"); + return; + } + + in_tq = batman_packet->tq; + in_ttl = batman_packet->ttl; + + batman_packet->ttl--; + memcpy(batman_packet->prev_sender, ethhdr->h_source, ETH_ALEN); + + /* 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)) { + + /* rebroadcast ogm of best ranking neighbor as is */ + if (!compare_orig(orig_node->router->addr, ethhdr->h_source)) { + batman_packet->tq = orig_node->router->tq_avg; + + if (orig_node->router->last_ttl) + batman_packet->ttl = orig_node->router->last_ttl + - 1; + } + + tq_avg = orig_node->router->tq_avg; + } + + /* apply hop penalty */ + batman_packet->tq = hop_penalty(batman_packet->tq); + + bat_dbg(DBG_BATMAN, bat_priv, + "Forwarding packet: tq_orig: %i, tq_avg: %i, " + "tq_forw: %i, ttl_orig: %i, ttl_forw: %i\n", + in_tq, tq_avg, batman_packet->tq, in_ttl - 1, + batman_packet->ttl); + + batman_packet->seqno = htonl(batman_packet->seqno); + + /* switch of primaries first hop flag when forwarding */ + batman_packet->flags &= ~PRIMARIES_FIRST_HOP; + if (directlink) + batman_packet->flags |= DIRECTLINK; + else + batman_packet->flags &= ~DIRECTLINK; + + send_time = forward_send_time(bat_priv); + add_bat_packet_to_list(bat_priv, + (unsigned char *)batman_packet, + sizeof(struct batman_packet) + hna_buff_len, + if_incoming, 0, send_time); +} + +static void forw_packet_free(struct forw_packet *forw_packet) +{ + if (forw_packet->skb) + kfree_skb(forw_packet->skb); + kfree(forw_packet); +} + +static void _add_bcast_packet_to_list(struct bat_priv *bat_priv, + struct forw_packet *forw_packet, + unsigned long send_time) +{ + unsigned long flags; + INIT_HLIST_NODE(&forw_packet->list); + + /* add new packet to packet list */ + spin_lock_irqsave(&bat_priv->forw_bcast_list_lock, flags); + hlist_add_head(&forw_packet->list, &bat_priv->forw_bcast_list); + spin_unlock_irqrestore(&bat_priv->forw_bcast_list_lock, flags); + + /* start timer for this packet */ + INIT_DELAYED_WORK(&forw_packet->delayed_work, + send_outstanding_bcast_packet); + queue_delayed_work(bat_event_workqueue, &forw_packet->delayed_work, + send_time); +} + +#define atomic_dec_not_zero(v) atomic_add_unless((v), -1, 0) +/* add a broadcast packet to the queue and setup timers. broadcast packets + * are sent multiple times to increase probability for beeing received. + * + * This function returns NETDEV_TX_OK on success and NETDEV_TX_BUSY on + * errors. + * + * The skb is not consumed, so the caller should make sure that the + * skb is freed. */ +int add_bcast_packet_to_list(struct bat_priv *bat_priv, struct sk_buff *skb) +{ + struct forw_packet *forw_packet; + struct bcast_packet *bcast_packet; + + if (!atomic_dec_not_zero(&bat_priv->bcast_queue_left)) { + bat_dbg(DBG_BATMAN, bat_priv, "bcast packet queue full\n"); + goto out; + } + + if (!bat_priv->primary_if) + goto out; + + forw_packet = kmalloc(sizeof(struct forw_packet), GFP_ATOMIC); + + if (!forw_packet) + goto out_and_inc; + + skb = skb_copy(skb, GFP_ATOMIC); + if (!skb) + goto packet_free; + + /* as we have a copy now, it is safe to decrease the TTL */ + bcast_packet = (struct bcast_packet *)skb->data; + bcast_packet->ttl--; + + skb_reset_mac_header(skb); + + forw_packet->skb = skb; + forw_packet->if_incoming = bat_priv->primary_if; + + /* how often did we send the bcast packet ? */ + forw_packet->num_packets = 0; + + _add_bcast_packet_to_list(bat_priv, forw_packet, 1); + return NETDEV_TX_OK; + +packet_free: + kfree(forw_packet); +out_and_inc: + atomic_inc(&bat_priv->bcast_queue_left); +out: + return NETDEV_TX_BUSY; +} + +static void send_outstanding_bcast_packet(struct work_struct *work) +{ + struct batman_if *batman_if; + struct delayed_work *delayed_work = + container_of(work, struct delayed_work, work); + struct forw_packet *forw_packet = + container_of(delayed_work, struct forw_packet, delayed_work); + unsigned long flags; + struct sk_buff *skb1; + struct net_device *soft_iface = forw_packet->if_incoming->soft_iface; + struct bat_priv *bat_priv = netdev_priv(soft_iface); + + spin_lock_irqsave(&bat_priv->forw_bcast_list_lock, flags); + hlist_del(&forw_packet->list); + spin_unlock_irqrestore(&bat_priv->forw_bcast_list_lock, flags); + + if (atomic_read(&bat_priv->mesh_state) == MESH_DEACTIVATING) + goto out; + + /* rebroadcast packet */ + rcu_read_lock(); + list_for_each_entry_rcu(batman_if, &if_list, list) { + if (batman_if->soft_iface != soft_iface) + continue; + + /* send a copy of the saved skb */ + skb1 = skb_clone(forw_packet->skb, GFP_ATOMIC); + if (skb1) + send_skb_packet(skb1, batman_if, broadcast_addr); + } + rcu_read_unlock(); + + forw_packet->num_packets++; + + /* if we still have some more bcasts to send */ + if (forw_packet->num_packets < 3) { + _add_bcast_packet_to_list(bat_priv, forw_packet, + ((5 * HZ) / 1000)); + return; + } + +out: + forw_packet_free(forw_packet); + atomic_inc(&bat_priv->bcast_queue_left); +} + +void send_outstanding_bat_packet(struct work_struct *work) +{ + struct delayed_work *delayed_work = + container_of(work, struct delayed_work, work); + struct forw_packet *forw_packet = + container_of(delayed_work, struct forw_packet, delayed_work); + unsigned long flags; + struct bat_priv *bat_priv; + + bat_priv = netdev_priv(forw_packet->if_incoming->soft_iface); + spin_lock_irqsave(&bat_priv->forw_bat_list_lock, flags); + hlist_del(&forw_packet->list); + spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags); + + if (atomic_read(&bat_priv->mesh_state) == MESH_DEACTIVATING) + goto out; + + send_packet(forw_packet); + + /** + * we have to have at least one packet in the queue + * to determine the queues wake up time unless we are + * shutting down + */ + if (forw_packet->own) + schedule_own_packet(forw_packet->if_incoming); + +out: + /* don't count own packet */ + if (!forw_packet->own) + atomic_inc(&bat_priv->batman_queue_left); + + forw_packet_free(forw_packet); +} + +void purge_outstanding_packets(struct bat_priv *bat_priv, + struct batman_if *batman_if) +{ + struct forw_packet *forw_packet; + struct hlist_node *tmp_node, *safe_tmp_node; + unsigned long flags; + + if (batman_if) + bat_dbg(DBG_BATMAN, bat_priv, + "purge_outstanding_packets(): %s\n", + batman_if->net_dev->name); + else + bat_dbg(DBG_BATMAN, bat_priv, + "purge_outstanding_packets()\n"); + + /* free bcast list */ + spin_lock_irqsave(&bat_priv->forw_bcast_list_lock, flags); + hlist_for_each_entry_safe(forw_packet, tmp_node, safe_tmp_node, + &bat_priv->forw_bcast_list, list) { + + /** + * if purge_outstanding_packets() was called with an argmument + * we delete only packets belonging to the given interface + */ + if ((batman_if) && + (forw_packet->if_incoming != batman_if)) + continue; + + spin_unlock_irqrestore(&bat_priv->forw_bcast_list_lock, flags); + + /** + * send_outstanding_bcast_packet() will lock the list to + * delete the item from the list + */ + cancel_delayed_work_sync(&forw_packet->delayed_work); + spin_lock_irqsave(&bat_priv->forw_bcast_list_lock, flags); + } + spin_unlock_irqrestore(&bat_priv->forw_bcast_list_lock, flags); + + /* free batman packet list */ + spin_lock_irqsave(&bat_priv->forw_bat_list_lock, flags); + hlist_for_each_entry_safe(forw_packet, tmp_node, safe_tmp_node, + &bat_priv->forw_bat_list, list) { + + /** + * if purge_outstanding_packets() was called with an argmument + * we delete only packets belonging to the given interface + */ + if ((batman_if) && + (forw_packet->if_incoming != batman_if)) + continue; + + spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags); + + /** + * send_outstanding_bat_packet() will lock the list to + * delete the item from the list + */ + cancel_delayed_work_sync(&forw_packet->delayed_work); + spin_lock_irqsave(&bat_priv->forw_bat_list_lock, flags); + } + spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags); +} diff --combined drivers/staging/batman-adv/sysfs-class-net-mesh index 5aa1912,b4cdb60..b4cdb60 --- a/drivers/staging/batman-adv/sysfs-class-net-mesh +++ b/drivers/staging/batman-adv/sysfs-class-net-mesh @@@ -14,6 -14,14 +14,14 @@@ Description mesh will be sent using multiple interfaces at the same time (if available). + What: /sys/class/net/<mesh_iface>/mesh/fragmentation + Date: October 2010 + Contact: Andreas Langer <an.langer(a)gmx.de> + Description: + Indicates whether the data traffic going through the + mesh will be fragmented or silently discarded if the + packet size exceeds the outgoing interface MTU. + What: /sys/class/net/<mesh_iface>/mesh/orig_interval Date: May 2010 Contact: Marek Lindner <lindner_marek(a)yahoo.de> diff --combined drivers/staging/batman-adv/translation-table.c index 12b2325,0000000..681ccbd mode 100644,000000..100644 --- a/drivers/staging/batman-adv/translation-table.c +++ b/drivers/staging/batman-adv/translation-table.c @@@ -1,513 -1,0 +1,518 @@@ +/* + * Copyright (C) 2007-2010 B.A.T.M.A.N. contributors: + * + * Marek Lindner, Simon Wunderlich + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#include "main.h" +#include "translation-table.h" +#include "soft-interface.h" +#include "types.h" +#include "hash.h" + +static void hna_local_purge(struct work_struct *work); +static void _hna_global_del_orig(struct bat_priv *bat_priv, + struct hna_global_entry *hna_global_entry, + char *message); + +static void hna_local_start_timer(struct bat_priv *bat_priv) +{ + INIT_DELAYED_WORK(&bat_priv->hna_work, hna_local_purge); + queue_delayed_work(bat_event_workqueue, &bat_priv->hna_work, 10 * HZ); +} + +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, compare_orig, choose_orig); + + if (!bat_priv->hna_local_hash) + return 0; + + atomic_set(&bat_priv->hna_local_changed, 0); + hna_local_start_timer(bat_priv); + + return 1; +} + +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; + unsigned long flags; ++ int required_bytes; + + spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); + hna_local_entry = + ((struct hna_local_entry *)hash_find(bat_priv->hna_local_hash, + addr)); + spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); + + if (hna_local_entry) { + hna_local_entry->last_seen = jiffies; + return; + } + + /* only announce as many hosts as possible in the batman-packet and + space in batman_packet->num_hna That also should give a limit to + MAC-flooding. */ - if ((bat_priv->num_local_hna + 1 > (ETH_DATA_LEN - BAT_PACKET_LEN) - / ETH_ALEN) || ++ required_bytes = (bat_priv->num_local_hna + 1) * ETH_ALEN; ++ required_bytes += BAT_PACKET_LEN; ++ ++ if ((required_bytes > ETH_DATA_LEN) || ++ (atomic_read(&bat_priv->aggregation_enabled) && ++ required_bytes > MAX_AGGREGATION_BYTES) || + (bat_priv->num_local_hna + 1 > 255)) { + bat_dbg(DBG_ROUTES, bat_priv, + "Can't add new local hna entry (%pM): " + "number of local hna entries exceeds packet size\n", + addr); + return; + } + + bat_dbg(DBG_ROUTES, bat_priv, + "Creating new local hna entry: %pM\n", addr); + + hna_local_entry = kmalloc(sizeof(struct hna_local_entry), GFP_ATOMIC); + if (!hna_local_entry) + return; + + memcpy(hna_local_entry->addr, addr, ETH_ALEN); + hna_local_entry->last_seen = jiffies; + + /* the batman interface mac address should never be purged */ + if (compare_orig(addr, soft_iface->dev_addr)) + hna_local_entry->never_purge = 1; + else + hna_local_entry->never_purge = 0; + + spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); + + hash_add(bat_priv->hna_local_hash, hna_local_entry); + 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, + 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_irqrestore(&bat_priv->hna_lhash_lock, flags); + + /* remove address from global hash if present */ + spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); + + hna_global_entry = ((struct hna_global_entry *) + hash_find(bat_priv->hna_global_hash, addr)); + + if (hna_global_entry) + _hna_global_del_orig(bat_priv, hna_global_entry, + "local hna received"); + + spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, flags); +} + +int hna_local_fill_buffer(struct bat_priv *bat_priv, + unsigned char *buff, int buff_len) +{ + struct hna_local_entry *hna_local_entry; + HASHIT(hashit); + int i = 0; + unsigned long flags; + + spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); + + while (hash_iterate(bat_priv->hna_local_hash, &hashit)) { + + if (buff_len < (i + 1) * ETH_ALEN) + break; + + hna_local_entry = hashit.bucket->data; + memcpy(buff + (i * ETH_ALEN), hna_local_entry->addr, ETH_ALEN); + + i++; + } + + /* if we did not get all new local hnas see you next time ;-) */ + if (i == bat_priv->num_local_hna) + atomic_set(&bat_priv->hna_local_changed, 0); + + spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); + return i; +} + +int hna_local_seq_print_text(struct seq_file *seq, void *offset) +{ + struct net_device *net_dev = (struct net_device *)seq->private; + struct bat_priv *bat_priv = netdev_priv(net_dev); + struct hna_local_entry *hna_local_entry; + HASHIT(hashit); + HASHIT(hashit_count); + unsigned long flags; + size_t buf_size, pos; + char *buff; + + if (!bat_priv->primary_if) { + return seq_printf(seq, "BATMAN mesh %s disabled - " + "please specify interfaces to enable it\n", + net_dev->name); + } + + seq_printf(seq, "Locally retrieved addresses (from %s) " + "announced via HNA:\n", + net_dev->name); + + spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); + + buf_size = 1; + /* Estimate length for: " * xx:xx:xx:xx:xx:xx\n" */ + while (hash_iterate(bat_priv->hna_local_hash, &hashit_count)) + buf_size += 21; + + buff = kmalloc(buf_size, GFP_ATOMIC); + if (!buff) { + spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); + return -ENOMEM; + } + buff[0] = '\0'; + pos = 0; + + while (hash_iterate(bat_priv->hna_local_hash, &hashit)) { + hna_local_entry = hashit.bucket->data; + + pos += snprintf(buff + pos, 22, " * %pM\n", + hna_local_entry->addr); + } + + spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); + + seq_printf(seq, "%s", buff); + kfree(buff); + return 0; +} + +static void _hna_local_del(void *data, void *arg) +{ + struct bat_priv *bat_priv = (struct bat_priv *)arg; + + kfree(data); + bat_priv->num_local_hna--; + atomic_set(&bat_priv->hna_local_changed, 1); +} + +static void hna_local_del(struct bat_priv *bat_priv, + struct hna_local_entry *hna_local_entry, + char *message) +{ + bat_dbg(DBG_ROUTES, bat_priv, "Deleting local hna entry (%pM): %s\n", + hna_local_entry->addr, message); + + hash_remove(bat_priv->hna_local_hash, hna_local_entry->addr); + _hna_local_del(hna_local_entry, bat_priv); +} + +void hna_local_remove(struct bat_priv *bat_priv, + uint8_t *addr, char *message) +{ + struct hna_local_entry *hna_local_entry; + unsigned long flags; + + spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); + + hna_local_entry = (struct hna_local_entry *) + hash_find(bat_priv->hna_local_hash, addr); + if (hna_local_entry) + hna_local_del(bat_priv, hna_local_entry, message); + + spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); +} + +static void hna_local_purge(struct work_struct *work) +{ + struct delayed_work *delayed_work = + container_of(work, struct delayed_work, work); + struct bat_priv *bat_priv = + container_of(delayed_work, struct bat_priv, hna_work); + struct hna_local_entry *hna_local_entry; + HASHIT(hashit); + unsigned long flags; + unsigned long timeout; + + spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); + + while (hash_iterate(bat_priv->hna_local_hash, &hashit)) { + hna_local_entry = hashit.bucket->data; + + timeout = hna_local_entry->last_seen + LOCAL_HNA_TIMEOUT * HZ; + + if ((!hna_local_entry->never_purge) && + time_after(jiffies, timeout)) + hna_local_del(bat_priv, hna_local_entry, + "address timed out"); + } + + spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); + hna_local_start_timer(bat_priv); +} + +void hna_local_free(struct bat_priv *bat_priv) +{ + if (!bat_priv->hna_local_hash) + return; + + cancel_delayed_work_sync(&bat_priv->hna_work); + hash_delete(bat_priv->hna_local_hash, _hna_local_del, bat_priv); + bat_priv->hna_local_hash = NULL; +} + +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, compare_orig, choose_orig); + + if (!bat_priv->hna_global_hash) + return 0; + + return 1; +} + +void hna_global_add_orig(struct bat_priv *bat_priv, + struct orig_node *orig_node, + unsigned char *hna_buff, int hna_buff_len) +{ + struct hna_global_entry *hna_global_entry; + struct hna_local_entry *hna_local_entry; + struct hashtable_t *swaphash; + int hna_buff_count = 0; + unsigned long flags; + unsigned char *hna_ptr; + + while ((hna_buff_count + 1) * ETH_ALEN <= hna_buff_len) { + spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); + + hna_ptr = hna_buff + (hna_buff_count * ETH_ALEN); + hna_global_entry = (struct hna_global_entry *) + hash_find(bat_priv->hna_global_hash, hna_ptr); + + if (!hna_global_entry) { + spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, + flags); + + hna_global_entry = + kmalloc(sizeof(struct hna_global_entry), + GFP_ATOMIC); + + if (!hna_global_entry) + break; + + memcpy(hna_global_entry->addr, hna_ptr, ETH_ALEN); + + bat_dbg(DBG_ROUTES, bat_priv, + "Creating new global hna entry: " + "%pM (via %pM)\n", + hna_global_entry->addr, orig_node->orig); + + spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); + hash_add(bat_priv->hna_global_hash, hna_global_entry); + + } + + hna_global_entry->orig_node = orig_node; + spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, flags); + + /* remove address from local hash if present */ + spin_lock_irqsave(&bat_priv->hna_lhash_lock, flags); + + hna_ptr = hna_buff + (hna_buff_count * ETH_ALEN); + hna_local_entry = (struct hna_local_entry *) + hash_find(bat_priv->hna_local_hash, hna_ptr); + + if (hna_local_entry) + hna_local_del(bat_priv, hna_local_entry, + "global hna received"); + + spin_unlock_irqrestore(&bat_priv->hna_lhash_lock, flags); + + hna_buff_count++; + } + + /* initialize, and overwrite if malloc succeeds */ + orig_node->hna_buff = NULL; + orig_node->hna_buff_len = 0; + + if (hna_buff_len > 0) { + orig_node->hna_buff = kmalloc(hna_buff_len, GFP_ATOMIC); + if (orig_node->hna_buff) { + memcpy(orig_node->hna_buff, hna_buff, hna_buff_len); + orig_node->hna_buff_len = hna_buff_len; + } + } + + spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); + + if (bat_priv->hna_global_hash->elements * 4 > + bat_priv->hna_global_hash->size) { + swaphash = hash_resize(bat_priv->hna_global_hash, + 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_irqrestore(&bat_priv->hna_ghash_lock, flags); +} + +int hna_global_seq_print_text(struct seq_file *seq, void *offset) +{ + struct net_device *net_dev = (struct net_device *)seq->private; + struct bat_priv *bat_priv = netdev_priv(net_dev); + struct hna_global_entry *hna_global_entry; + HASHIT(hashit); + HASHIT(hashit_count); + unsigned long flags; + size_t buf_size, pos; + char *buff; + + if (!bat_priv->primary_if) { + return seq_printf(seq, "BATMAN mesh %s disabled - " + "please specify interfaces to enable it\n", + net_dev->name); + } + + seq_printf(seq, "Globally announced HNAs received via the mesh %s\n", + net_dev->name); + + spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); + + buf_size = 1; + /* Estimate length for: " * xx:xx:xx:xx:xx:xx via xx:xx:xx:xx:xx:xx\n"*/ + while (hash_iterate(bat_priv->hna_global_hash, &hashit_count)) + buf_size += 43; + + buff = kmalloc(buf_size, GFP_ATOMIC); + if (!buff) { + spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, flags); + return -ENOMEM; + } + buff[0] = '\0'; + pos = 0; + + while (hash_iterate(bat_priv->hna_global_hash, &hashit)) { + hna_global_entry = hashit.bucket->data; + + pos += snprintf(buff + pos, 44, + " * %pM via %pM\n", hna_global_entry->addr, + hna_global_entry->orig_node->orig); + } + + spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, flags); + + seq_printf(seq, "%s", buff); + kfree(buff); + return 0; +} + +static void _hna_global_del_orig(struct bat_priv *bat_priv, + struct hna_global_entry *hna_global_entry, + char *message) +{ + bat_dbg(DBG_ROUTES, bat_priv, + "Deleting global hna entry %pM (via %pM): %s\n", + hna_global_entry->addr, hna_global_entry->orig_node->orig, + message); + + hash_remove(bat_priv->hna_global_hash, hna_global_entry->addr); + kfree(hna_global_entry); +} + +void hna_global_del_orig(struct bat_priv *bat_priv, + struct orig_node *orig_node, char *message) +{ + struct hna_global_entry *hna_global_entry; + int hna_buff_count = 0; + unsigned long flags; + unsigned char *hna_ptr; + + if (orig_node->hna_buff_len == 0) + return; + + spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); + + while ((hna_buff_count + 1) * ETH_ALEN <= orig_node->hna_buff_len) { + hna_ptr = orig_node->hna_buff + (hna_buff_count * ETH_ALEN); + hna_global_entry = (struct hna_global_entry *) + hash_find(bat_priv->hna_global_hash, hna_ptr); + + if ((hna_global_entry) && + (hna_global_entry->orig_node == orig_node)) + _hna_global_del_orig(bat_priv, hna_global_entry, + message); + + hna_buff_count++; + } + + spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, flags); + + orig_node->hna_buff_len = 0; + kfree(orig_node->hna_buff); + orig_node->hna_buff = NULL; +} + +static void hna_global_del(void *data, void *arg) +{ + kfree(data); +} + +void hna_global_free(struct bat_priv *bat_priv) +{ + if (!bat_priv->hna_global_hash) + return; + + hash_delete(bat_priv->hna_global_hash, hna_global_del, NULL); + bat_priv->hna_global_hash = NULL; +} + +struct orig_node *transtable_search(struct bat_priv *bat_priv, uint8_t *addr) +{ + struct hna_global_entry *hna_global_entry; + unsigned long flags; + + spin_lock_irqsave(&bat_priv->hna_ghash_lock, flags); + hna_global_entry = (struct hna_global_entry *) + hash_find(bat_priv->hna_global_hash, addr); + spin_unlock_irqrestore(&bat_priv->hna_ghash_lock, flags); + + if (!hna_global_entry) + return NULL; + + return hna_global_entry->orig_node; +} -- linux integration

12 years, 5 months

batman-adv; branch, next, updated. v2010.1.0-48-g050ada5

by postmaster＠open-mesh.org

The following commit has been merged in the next branch: commit 8a621f0348ac734ae571735412c76f9383109da6 Author: Marek Lindner <lindner_marek(a)yahoo.de> Date: Mon Oct 18 09:12:29 2010 +0000 batman-adv: fix crash when new OGM is generated If aggregation is not enabled the local translation table can grow much bigger and expects to fill a full ethernet packet. Reported-by: Sam Yeung <sam.cwyeung(a)gmail.com> Signed-off-by: Marek Lindner <lindner_marek(a)yahoo.de> Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> diff --git a/aggregation.c b/aggregation.c index 46b9c2b..16b268e 100644 --- a/aggregation.c +++ b/aggregation.c @@ -123,8 +123,14 @@ static void new_aggregated_packet(unsigned char *packet_buff, int packet_len, return; } - forw_packet_aggr->skb = dev_alloc_skb(MAX_AGGREGATION_BYTES + - sizeof(struct ethhdr)); + if ((atomic_read(&bat_priv->aggregation_enabled)) && + (packet_len < MAX_AGGREGATION_BYTES)) + forw_packet_aggr->skb = dev_alloc_skb(MAX_AGGREGATION_BYTES + + sizeof(struct ethhdr)); + else + forw_packet_aggr->skb = dev_alloc_skb(packet_len + + sizeof(struct ethhdr)); + if (!forw_packet_aggr->skb) { if (!own_packet) atomic_inc(&bat_priv->batman_queue_left); -- batman-adv

12 years, 5 months

batman-adv; branch, next, updated. v2010.1.0-48-g050ada5

by postmaster＠open-mesh.org

The following commit has been merged in the next branch: commit 050ada5d7cdcc7d68b630af6eb6c477011867ead Author: Marek Lindner <lindner_marek(a)yahoo.de> Date: Mon Oct 18 09:12:30 2010 +0000 batman-adv: process OGMs bigger than MAX_AGGREGATION_BYTES Reported-by: Sam Yeung <sam.cwyeung(a)gmail.com> Signed-off-by: Marek Lindner <lindner_marek(a)yahoo.de> Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> diff --git a/aggregation.c b/aggregation.c index 16b268e..08624d4 100644 --- a/aggregation.c +++ b/aggregation.c @@ -257,9 +257,7 @@ void receive_aggr_bat_packet(struct ethhdr *ethhdr, unsigned char *packet_buff, batman_packet = (struct batman_packet *)packet_buff; - while (aggregated_packet(buff_pos, packet_len, - batman_packet->num_hna)) { - + do { /* network to host order for our 32bit seqno, and the orig_interval. */ batman_packet->seqno = ntohl(batman_packet->seqno); @@ -272,5 +270,6 @@ void receive_aggr_bat_packet(struct ethhdr *ethhdr, unsigned char *packet_buff, buff_pos += BAT_PACKET_LEN + hna_len(batman_packet); batman_packet = (struct batman_packet *) (packet_buff + buff_pos); - } + } while (aggregated_packet(buff_pos, packet_len, + batman_packet->num_hna)); } -- batman-adv

12 years, 5 months

batman-adv; branch, next, updated. v2010.1.0-48-g050ada5

by postmaster＠open-mesh.org

The following commit has been merged in the next branch: commit 2012426ba8c91726fb740a8a2bd4c49d07c265e2 Author: Marek Lindner <lindner_marek(a)yahoo.de> Date: Mon Oct 18 09:09:57 2010 +0000 batman-adv: document fragmentation sysfs API Signed-off-by: Marek Lindner <lindner_marek(a)yahoo.de> Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> diff --git a/sysfs-class-net-mesh b/sysfs-class-net-mesh index 5aa1912..b4cdb60 100644 --- a/sysfs-class-net-mesh +++ b/sysfs-class-net-mesh @@ -14,6 +14,14 @@ Description: mesh will be sent using multiple interfaces at the same time (if available). +What: /sys/class/net/<mesh_iface>/mesh/fragmentation +Date: October 2010 +Contact: Andreas Langer <an.langer(a)gmx.de> +Description: + Indicates whether the data traffic going through the + mesh will be fragmented or silently discarded if the + packet size exceeds the outgoing interface MTU. + What: /sys/class/net/<mesh_iface>/mesh/orig_interval Date: May 2010 Contact: Marek Lindner <lindner_marek(a)yahoo.de> -- batman-adv

12 years, 5 months

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

commits October 2010