* [B.A.T.M.A.N.] Polishing of the hash implementation
@ 2010-10-09 12:16 Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 1/5] batman-adv: Remove hashdata_compare_cb from hash Sven Eckelmann
` (5 more replies)
0 siblings, 6 replies; 9+ messages in thread
From: Sven Eckelmann @ 2010-10-09 12:16 UTC (permalink / raw)
To: b.a.t.m.a.n
Hi,
David S. Miller wasn't amused[1] by our hash implementation. Instead he
proposed some changes we should make. I tried to implement most of them, but
don't think we should really manually inline every functionality currently
provided by the hash implementation. I would rather keep the heavily used
functions as compiler inlineable functions and do the rest using standard
kernel hlist_*.
Best regards,
Sven
[1] Message-Id: <20100924.134334.28812338.davem@davemloft.net>
Sven Eckelmann (5):
batman-adv: Remove hashdata_compare_cb from hash
batman-adv: Remove hashdata_choose_cb from hash
batman-adv: Move hash callback related function to header
batman-adv: Make hash_iterate inlineable
batman-adv: Rewrite hash using hlist_*
batman-adv/hash.c | 237 +--------------------------------------
batman-adv/hash.h | 220 ++++++++++++++++++++++++++++++++-----
batman-adv/icmp_socket.c | 2 +
batman-adv/main.c | 28 -----
batman-adv/main.h | 2 -
batman-adv/originator.c | 31 ++++--
batman-adv/originator.h | 28 +++++
batman-adv/routing.c | 22 +++-
batman-adv/send.c | 1 +
batman-adv/translation-table.c | 58 +++++++---
batman-adv/unicast.c | 6 +-
batman-adv/vis.c | 49 ++++++--
12 files changed, 347 insertions(+), 337 deletions(-)
^ permalink raw reply [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCH 1/5] batman-adv: Remove hashdata_compare_cb from hash
2010-10-09 12:16 [B.A.T.M.A.N.] Polishing of the hash implementation Sven Eckelmann
@ 2010-10-09 12:16 ` Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 2/5] batman-adv: Remove hashdata_choose_cb " Sven Eckelmann
` (4 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: Sven Eckelmann @ 2010-10-09 12:16 UTC (permalink / raw)
To: b.a.t.m.a.n
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@davemloft.net>
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
batman-adv/hash.c | 25 +++++++++++++------------
batman-adv/hash.h | 23 ++++++++++++-----------
batman-adv/icmp_socket.c | 2 ++
batman-adv/main.c | 7 -------
batman-adv/main.h | 1 -
batman-adv/originator.c | 9 +++++----
batman-adv/originator.h | 7 +++++++
batman-adv/routing.c | 15 ++++++++++-----
batman-adv/send.c | 1 +
batman-adv/translation-table.c | 39 ++++++++++++++++++++++++---------------
batman-adv/unicast.c | 5 ++++-
batman-adv/vis.c | 15 ++++++++++-----
12 files changed, 88 insertions(+), 61 deletions(-)
diff --git a/batman-adv/hash.c b/batman-adv/hash.c
index 8ef26eb..a4abe14 100644
--- a/batman-adv/hash.c
+++ b/batman-adv/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/batman-adv/hash.h b/batman-adv/hash.h
index 2c8e176..742277e 100644
--- a/batman-adv/hash.h
+++ b/batman-adv/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/batman-adv/icmp_socket.c b/batman-adv/icmp_socket.c
index aa64ff8..de70752 100644
--- a/batman-adv/icmp_socket.c
+++ b/batman-adv/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/batman-adv/main.c b/batman-adv/main.c
index 6ecee49..ecab8b8 100644
--- a/batman-adv/main.c
+++ b/batman-adv/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/batman-adv/main.h b/batman-adv/main.h
index cc42eb4..c09a9fd 100644
--- a/batman-adv/main.h
+++ b/batman-adv/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/batman-adv/originator.c b/batman-adv/originator.c
index a7b74f0..2d883cd 100644
--- a/batman-adv/originator.c
+++ b/batman-adv/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/batman-adv/originator.h b/batman-adv/originator.h
index a97c400..ed903dc 100644
--- a/batman-adv/originator.h
+++ b/batman-adv/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/batman-adv/routing.c b/batman-adv/routing.c
index 1377f01..e42616d 100644
--- a/batman-adv/routing.c
+++ b/batman-adv/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/batman-adv/send.c b/batman-adv/send.c
index 180e18b..7097ff0 100644
--- a/batman-adv/send.c
+++ b/batman-adv/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/batman-adv/translation-table.c b/batman-adv/translation-table.c
index 9cae140..fc9342b 100644
--- a/batman-adv/translation-table.c
+++ b/batman-adv/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;
@@ -64,7 +65,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) {
@@ -103,13 +104,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)
@@ -124,7 +125,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,
@@ -228,7 +230,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);
}
@@ -241,7 +244,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);
@@ -291,7 +294,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;
@@ -315,7 +318,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,
@@ -336,7 +340,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);
}
@@ -348,7 +353,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,
@@ -375,7 +381,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)
@@ -446,7 +452,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);
}
@@ -466,7 +473,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))
@@ -504,7 +512,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/batman-adv/unicast.c b/batman-adv/unicast.c
index bca69f6..4390b0e 100644
--- a/batman-adv/unicast.c
+++ b/batman-adv/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/batman-adv/vis.c b/batman-adv/vis.c
index ddfdcd8..ef4ea86 100644
--- a/batman-adv/vis.c
+++ b/batman-adv/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);
--
1.7.2.3
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCH 2/5] batman-adv: Remove hashdata_choose_cb from hash
2010-10-09 12:16 [B.A.T.M.A.N.] Polishing of the hash implementation Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 1/5] batman-adv: Remove hashdata_compare_cb from hash Sven Eckelmann
@ 2010-10-09 12:16 ` Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 3/5] batman-adv: Move hash callback related function to header Sven Eckelmann
` (3 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: Sven Eckelmann @ 2010-10-09 12:16 UTC (permalink / raw)
To: b.a.t.m.a.n
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@davemloft.net>
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
batman-adv/hash.c | 24 ++++++++++++------------
batman-adv/hash.h | 19 +++++++++++--------
batman-adv/icmp_socket.c | 2 +-
batman-adv/main.c | 21 ---------------------
batman-adv/main.h | 1 -
batman-adv/originator.c | 11 ++++++++---
batman-adv/originator.h | 21 +++++++++++++++++++++
batman-adv/routing.c | 13 +++++++------
batman-adv/translation-table.c | 31 ++++++++++++++++++-------------
batman-adv/unicast.c | 3 ++-
batman-adv/vis.c | 17 +++++++++++------
11 files changed, 91 insertions(+), 72 deletions(-)
diff --git a/batman-adv/hash.c b/batman-adv/hash.c
index a4abe14..6361a31 100644
--- a/batman-adv/hash.c
+++ b/batman-adv/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/batman-adv/hash.h b/batman-adv/hash.h
index 742277e..85ee12b 100644
--- a/batman-adv/hash.h
+++ b/batman-adv/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/batman-adv/icmp_socket.c b/batman-adv/icmp_socket.c
index de70752..b9201c5 100644
--- a/batman-adv/icmp_socket.c
+++ b/batman-adv/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/batman-adv/main.c b/batman-adv/main.c
index ecab8b8..9c14832 100644
--- a/batman-adv/main.c
+++ b/batman-adv/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/batman-adv/main.h b/batman-adv/main.h
index c09a9fd..05e4ac8 100644
--- a/batman-adv/main.h
+++ b/batman-adv/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/batman-adv/originator.c b/batman-adv/originator.c
index 2d883cd..0927119 100644
--- a/batman-adv/originator.c
+++ b/batman-adv/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/batman-adv/originator.h b/batman-adv/originator.h
index ed903dc..d474ceb 100644
--- a/batman-adv/originator.h
+++ b/batman-adv/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/batman-adv/routing.c b/batman-adv/routing.c
index e42616d..bdb8460 100644
--- a/batman-adv/routing.c
+++ b/batman-adv/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/batman-adv/translation-table.c b/batman-adv/translation-table.c
index fc9342b..20e1a74 100644
--- a/batman-adv/translation-table.c
+++ b/batman-adv/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;
@@ -65,7 +65,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) {
@@ -104,13 +105,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)
@@ -126,7 +129,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,
@@ -230,7 +233,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);
}
@@ -244,7 +247,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);
@@ -294,7 +298,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;
@@ -319,7 +323,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,
@@ -341,7 +345,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);
}
@@ -354,7 +358,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,
@@ -382,6 +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, compare_orig,
+ choose_orig,
bat_priv->hna_global_hash->size * 2);
if (!swaphash)
@@ -452,7 +457,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);
}
@@ -474,7 +479,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))
@@ -513,7 +518,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/batman-adv/unicast.c b/batman-adv/unicast.c
index 4390b0e..aca5119 100644
--- a/batman-adv/unicast.c
+++ b/batman-adv/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/batman-adv/vis.c b/batman-adv/vis.c
index ef4ea86..88402c9 100644
--- a/batman-adv/vis.c
+++ b/batman-adv/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");
--
1.7.2.3
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCH 3/5] batman-adv: Move hash callback related function to header
2010-10-09 12:16 [B.A.T.M.A.N.] Polishing of the hash implementation Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 1/5] batman-adv: Remove hashdata_compare_cb from hash Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 2/5] batman-adv: Remove hashdata_choose_cb " Sven Eckelmann
@ 2010-10-09 12:16 ` Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 4/5] batman-adv: Make hash_iterate inlineable Sven Eckelmann
` (2 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: Sven Eckelmann @ 2010-10-09 12:16 UTC (permalink / raw)
To: b.a.t.m.a.n
To enable inlining of the function pointers hashdata_choose_cb,
hashdata_choose_cb and hashdata_free_cb, also the hash functions which
uses them must be inlined by the called function.
This should increase the performance, but also increases the size of the
generated machine code slightly.
Reported-by: David S. Miller <davem@davemloft.net>
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
batman-adv/hash.c | 150 ----------------------------------------------------
batman-adv/hash.h | 152 ++++++++++++++++++++++++++++++++++++++++++++++++----
2 files changed, 140 insertions(+), 162 deletions(-)
diff --git a/batman-adv/hash.c b/batman-adv/hash.c
index 6361a31..7d04987 100644
--- a/batman-adv/hash.c
+++ b/batman-adv/hash.c
@@ -33,30 +33,6 @@ static void hash_init(struct hashtable_t *hash)
hash->table[i] = NULL;
}
-/* remove the hash structure. if hashdata_free_cb != NULL, this function will be
- * called to remove the elements inside of the hash. if you don't remove the
- * elements, memory might be leaked. */
-void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb, void *arg)
-{
- struct element_t *bucket, *last_bucket;
- int i;
-
- for (i = 0; i < hash->size; i++) {
- bucket = hash->table[i];
-
- while (bucket != NULL) {
- if (free_cb != NULL)
- free_cb(bucket->data, arg);
-
- last_bucket = bucket;
- bucket = bucket->next;
- kfree(last_bucket);
- }
- }
-
- hash_destroy(hash);
-}
-
/* free only the hashtable and the hash itself. */
void hash_destroy(struct hashtable_t *hash)
{
@@ -159,70 +135,6 @@ struct hashtable_t *hash_new(int size)
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,
- hashdata_choose_cb choose, void *data)
-{
- int index;
- struct element_t *bucket, *prev_bucket = NULL;
-
- if (!hash)
- return -1;
-
- index = choose(data, hash->size);
- bucket = hash->table[index];
-
- while (bucket != NULL) {
- if (compare(bucket->data, data))
- return -1;
-
- prev_bucket = bucket;
- bucket = bucket->next;
- }
-
- /* found the tail of the 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;
-
- hash->elements++;
- return 0;
-}
-
-/* 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,
- hashdata_choose_cb choose, void *keydata)
-{
- int index;
- struct element_t *bucket;
-
- if (!hash)
- return NULL;
-
- index = choose(keydata , hash->size);
- bucket = hash->table[index];
-
- while (bucket != NULL) {
- if (compare(bucket->data, keydata))
- return bucket->data;
-
- bucket = bucket->next;
- }
-
- return NULL;
-}
-
/* remove bucket (this might be used in hash_iterate() if you already found the
* bucket you want to delete and don't need the overhead to find it again with
* hash_remove(). But usually, you don't want to use this function, as it
@@ -243,65 +155,3 @@ void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t)
return data_save;
}
-
-/* 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,
- hashdata_choose_cb choose, void *data)
-{
- struct hash_it_t hash_it_t;
-
- 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);
- }
-
- hash_it_t.prev_bucket = hash_it_t.bucket;
- hash_it_t.bucket = hash_it_t.bucket->next;
- }
-
- return NULL;
-}
-
-/* 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,
- 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);
-
- if (new_hash == NULL)
- return NULL;
-
- /* copy the elements */
- for (i = 0; i < hash->size; i++) {
- bucket = hash->table[i];
-
- while (bucket != NULL) {
- hash_add(new_hash, compare, choose, bucket->data);
- bucket = bucket->next;
- }
- }
-
- /* remove hash and eventual overflow buckets but not the content
- * itself. */
- hash_delete(hash, NULL, NULL);
-
- return new_hash;
-}
diff --git a/batman-adv/hash.h b/batman-adv/hash.h
index 85ee12b..efc4c28 100644
--- a/batman-adv/hash.h
+++ b/batman-adv/hash.h
@@ -66,35 +66,163 @@ struct hashtable_t *hash_new(int size);
* fiddles with hash-internals. */
void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t);
+/* free only the hashtable and the hash itself. */
+void hash_destroy(struct hashtable_t *hash);
+
/* remove the hash structure. if hashdata_free_cb != NULL, this function will be
* called to remove the elements inside of the hash. if you don't remove the
* elements, memory might be leaked. */
-void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb, void *arg);
+static inline void hash_delete(struct hashtable_t *hash,
+ hashdata_free_cb free_cb, void *arg)
+{
+ struct element_t *bucket, *last_bucket;
+ int i;
-/* free only the hashtable and the hash itself. */
-void hash_destroy(struct hashtable_t *hash);
+ for (i = 0; i < hash->size; i++) {
+ bucket = hash->table[i];
+
+ while (bucket != NULL) {
+ if (free_cb != NULL)
+ free_cb(bucket->data, arg);
+
+ last_bucket = bucket;
+ bucket = bucket->next;
+ kfree(last_bucket);
+ }
+ }
+
+ hash_destroy(hash);
+}
/* adds data to the hashtable. returns 0 on success, -1 on error */
-int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare,
- hashdata_choose_cb choose, void *data);
+static inline 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;
+
+ if (!hash)
+ return -1;
+
+ index = choose(data, hash->size);
+ bucket = hash->table[index];
+
+ while (bucket != NULL) {
+ if (compare(bucket->data, data))
+ return -1;
+
+ prev_bucket = bucket;
+ bucket = bucket->next;
+ }
+
+ /* found the tail of the 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;
+
+ hash->elements++;
+ return 0;
+}
/* 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,
- hashdata_choose_cb choose, void *data);
+static inline void *hash_remove(struct hashtable_t *hash,
+ hashdata_compare_cb compare,
+ hashdata_choose_cb choose, void *data)
+{
+ struct hash_it_t hash_it_t;
+
+ 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);
+ }
+
+ hash_it_t.prev_bucket = hash_it_t.bucket;
+ hash_it_t.bucket = hash_it_t.bucket->next;
+ }
+
+ return NULL;
+}
/* 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,
- hashdata_choose_cb choose, void *keydata);
+static inline void *hash_find(struct hashtable_t *hash,
+ hashdata_compare_cb compare,
+ hashdata_choose_cb choose, void *keydata)
+{
+ int index;
+ struct element_t *bucket;
+
+ if (!hash)
+ return NULL;
+
+ index = choose(keydata , hash->size);
+ bucket = hash->table[index];
+
+ while (bucket != NULL) {
+ if (compare(bucket->data, keydata))
+ return bucket->data;
+
+ bucket = bucket->next;
+ }
+
+ return NULL;
+}
/* 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,
- hashdata_choose_cb choose, int size);
+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 element_t *bucket;
+ int i;
+
+ /* initialize a new hash with the new size */
+ new_hash = hash_new(size);
+
+ if (new_hash == NULL)
+ return NULL;
+
+ /* copy the elements */
+ for (i = 0; i < hash->size; i++) {
+ bucket = hash->table[i];
+
+ while (bucket != NULL) {
+ hash_add(new_hash, compare, choose, bucket->data);
+ bucket = bucket->next;
+ }
+ }
+
+ /* remove hash and eventual overflow buckets but not the content
+ * itself. */
+ hash_delete(hash, NULL, NULL);
+
+ return new_hash;
+}
/* 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. */
--
1.7.2.3
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCH 4/5] batman-adv: Make hash_iterate inlineable
2010-10-09 12:16 [B.A.T.M.A.N.] Polishing of the hash implementation Sven Eckelmann
` (2 preceding siblings ...)
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 3/5] batman-adv: Move hash callback related function to header Sven Eckelmann
@ 2010-10-09 12:16 ` Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 5/5] batman-adv: Rewrite hash using hlist_* Sven Eckelmann
2010-10-23 1:41 ` [B.A.T.M.A.N.] Polishing of the hash implementation Marek Lindner
5 siblings, 0 replies; 9+ messages in thread
From: Sven Eckelmann @ 2010-10-09 12:16 UTC (permalink / raw)
To: b.a.t.m.a.n
hash_iterate is next to the function pointers the most called function
related to hashes which benefits from inlining as it is uses in loops.
Reported-by: David S. Miller <davem@davemloft.net>
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
batman-adv/hash.c | 72 ---------------------------------------------------
batman-adv/hash.h | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++---
2 files changed, 70 insertions(+), 76 deletions(-)
diff --git a/batman-adv/hash.c b/batman-adv/hash.c
index 7d04987..bfe943c 100644
--- a/batman-adv/hash.c
+++ b/batman-adv/hash.c
@@ -40,78 +40,6 @@ void hash_destroy(struct hashtable_t *hash)
kfree(hash);
}
-/* iterate though the hash. First element is selected if an iterator
- * initialized with HASHIT() is supplied as iter. Use the returned
- * (or supplied) iterator to access the elements until hash_iterate returns
- * NULL. */
-
-struct hash_it_t *hash_iterate(struct hashtable_t *hash,
- struct hash_it_t *iter)
-{
- if (!hash)
- return NULL;
- 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;
- }
- }
-
- /* 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;
- }
- }
-
- /* 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++;
- }
- }
-
- /* nothing to iterate over anymore */
- return NULL;
-}
-
/* allocates and clears the hash */
struct hashtable_t *hash_new(int size)
{
diff --git a/batman-adv/hash.h b/batman-adv/hash.h
index efc4c28..a8e4dd1 100644
--- a/batman-adv/hash.h
+++ b/batman-adv/hash.h
@@ -224,9 +224,75 @@ static inline struct hashtable_t *hash_resize(struct hashtable_t *hash,
return new_hash;
}
-/* 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. */
-struct hash_it_t *hash_iterate(struct hashtable_t *hash,
- struct hash_it_t *iter_in);
+/* iterate though the hash. First element is selected if an iterator
+ * initialized with HASHIT() is supplied as iter. Use the returned
+ * (or supplied) iterator to access the elements until hash_iterate returns
+ * NULL. */
+static inline struct hash_it_t *hash_iterate(struct hashtable_t *hash,
+ struct hash_it_t *iter)
+{
+ if (!hash)
+ return NULL;
+ if (!iter)
+ return NULL;
+
+ /* 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;
+ }
+ }
+
+ /* 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;
+ }
+ }
+
+ /* 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++;
+ }
+ }
+
+ /* nothing to iterate over anymore */
+ return NULL;
+}
#endif /* _NET_BATMAN_ADV_HASH_H_ */
--
1.7.2.3
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCH 5/5] batman-adv: Rewrite hash using hlist_*
2010-10-09 12:16 [B.A.T.M.A.N.] Polishing of the hash implementation Sven Eckelmann
` (3 preceding siblings ...)
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 4/5] batman-adv: Make hash_iterate inlineable Sven Eckelmann
@ 2010-10-09 12:16 ` Sven Eckelmann
2010-10-09 12:32 ` [B.A.T.M.A.N.] [PATCHv2 " Sven Eckelmann
2010-10-23 1:41 ` [B.A.T.M.A.N.] Polishing of the hash implementation Marek Lindner
5 siblings, 1 reply; 9+ messages in thread
From: Sven Eckelmann @ 2010-10-09 12:16 UTC (permalink / raw)
To: b.a.t.m.a.n
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@davemloft.net>
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
batman-adv/hash.c | 14 ++--
batman-adv/hash.h | 172 ++++++++++++++++------------------------
batman-adv/originator.c | 17 +++-
batman-adv/routing.c | 4 +-
batman-adv/translation-table.c | 16 +++-
batman-adv/vis.c | 29 +++++--
6 files changed, 122 insertions(+), 130 deletions(-)
diff --git a/batman-adv/hash.c b/batman-adv/hash.c
index bfe943c..8605e2f 100644
--- a/batman-adv/hash.c
+++ b/batman-adv/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/batman-adv/hash.h b/batman-adv/hash.h
index a8e4dd1..d42cfd2 100644
--- a/batman-adv/hash.h
+++ b/batman-adv/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, .head = NULL }
/* callback to a compare function. should
* compare 2 element datas for their keys,
@@ -41,18 +42,18 @@ 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_head *head;
+ 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 +76,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 +103,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 +141,15 @@ 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;
hash_it_t.index = choose(data, hash->size);
- hash_it_t.bucket = hash->table[hash_it_t.index];
- hash_it_t.prev_bucket = NULL;
+ hash_it_t.head = &hash->table[hash_it_t.index];
- 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);
+ hlist_for_each(hash_it_t.walk, hash_it_t.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);
- }
-
- hash_it_t.prev_bucket = hash_it_t.bucket;
- hash_it_t.bucket = hash_it_t.bucket->next;
}
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;
@@ -198,8 +189,10 @@ static inline struct hashtable_t *hash_resize(struct hashtable_t *hash,
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 +202,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];
- while (bucket != NULL) {
- hash_add(new_hash, compare, choose, bucket->data);
- bucket = bucket->next;
+ hlist_for_each_safe(walk, safe, head) {
+ bucket = hlist_entry(walk, struct element_t, hlist);
+
+ new_index = choose(bucket->data, size);
+ new_head = &new_hash->table[new_index];
+
+ hlist_del(walk);
+ hlist_add_head(walk, new_head);
}
}
- /* remove hash and eventual overflow buckets but not the content
- * itself. */
- hash_delete(hash, NULL, NULL);
+ hash_destroy(hash);
return new_hash;
}
@@ -236,63 +232,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;
- }
+ iter->walk = iter->safe;
+
+ /* we search for the next head with list entries */
+ if (!iter->walk) {
+ while (iter->index < hash->size) {
+ if (hlist_empty(&hash->table[iter->index]))
+ iter->index++;
+ else {
+ iter->walk = hash->table[iter->index].first;
+
+ /* search next time */
+ ++iter->index;
+ break;
}
- } 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;
}
}
- /* 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;
- }
- }
-
- /* 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++;
- }
- }
+ /* return iter when we found bucket otherwise null */
+ if (!iter->walk)
+ return NULL;
- /* nothing to iterate over anymore */
- return NULL;
+ iter->safe = iter->walk->next;
+ return iter;
}
#endif /* _NET_BATMAN_ADV_HASH_H_ */
diff --git a/batman-adv/originator.c b/batman-adv/originator.c
index 0927119..67d9821 100644
--- a/batman-adv/originator.c
+++ b/batman-adv/originator.c
@@ -274,6 +274,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 +282,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 +324,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 +358,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 +433,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 +514,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 +522,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/batman-adv/routing.c b/batman-adv/routing.c
index bdb8460..797ccd1 100644
--- a/batman-adv/routing.c
+++ b/batman-adv/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/batman-adv/translation-table.c b/batman-adv/translation-table.c
index 20e1a74..66b7b08 100644
--- a/batman-adv/translation-table.c
+++ b/batman-adv/translation-table.c
@@ -142,6 +142,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;
@@ -153,7 +154,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++;
@@ -174,6 +176,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;
@@ -204,7 +207,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);
@@ -263,13 +267,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;
@@ -405,6 +411,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;
@@ -434,7 +441,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/batman-adv/vis.c b/batman-adv/vis.c
index 88402c9..9e41f81 100644
--- a/batman-adv/vis.c
+++ b/batman-adv/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))
--
1.7.2.3
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCHv2 5/5] batman-adv: Rewrite hash using hlist_*
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 5/5] batman-adv: Rewrite hash using hlist_* Sven Eckelmann
@ 2010-10-09 12:32 ` Sven Eckelmann
2010-10-10 14:26 ` [B.A.T.M.A.N.] [PATCHv3 " Sven Eckelmann
0 siblings, 1 reply; 9+ messages in thread
From: Sven Eckelmann @ 2010-10-09 12:32 UTC (permalink / raw)
To: b.a.t.m.a.n
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@davemloft.net>
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
Remove now unused hashdata_compare_cb from hash_resize
batman-adv/hash.c | 14 ++--
batman-adv/hash.h | 173 +++++++++++++++------------------------
batman-adv/originator.c | 20 +++--
batman-adv/routing.c | 4 +-
batman-adv/translation-table.c | 22 +++--
batman-adv/vis.c | 29 +++++--
6 files changed, 125 insertions(+), 137 deletions(-)
diff --git a/batman-adv/hash.c b/batman-adv/hash.c
index bfe943c..8605e2f 100644
--- a/batman-adv/hash.c
+++ b/batman-adv/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/batman-adv/hash.h b/batman-adv/hash.h
index a8e4dd1..cf43035 100644
--- a/batman-adv/hash.h
+++ b/batman-adv/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, .head = NULL }
/* callback to a compare function. should
* compare 2 element datas for their keys,
@@ -41,18 +42,18 @@ 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_head *head;
+ 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 +76,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 +103,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 +141,15 @@ 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;
hash_it_t.index = choose(data, hash->size);
- hash_it_t.bucket = hash->table[hash_it_t.index];
- hash_it_t.prev_bucket = NULL;
+ hash_it_t.head = &hash->table[hash_it_t.index];
- 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);
+ hlist_for_each(hash_it_t.walk, hash_it_t.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);
- }
-
- hash_it_t.prev_bucket = hash_it_t.bucket;
- hash_it_t.bucket = hash_it_t.bucket->next;
}
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];
- while (bucket != NULL) {
- hash_add(new_hash, compare, choose, bucket->data);
- bucket = bucket->next;
+ hlist_for_each_safe(walk, safe, head) {
+ bucket = hlist_entry(walk, struct element_t, hlist);
+
+ new_index = choose(bucket->data, size);
+ new_head = &new_hash->table[new_index];
+
+ hlist_del(walk);
+ hlist_add_head(walk, new_head);
}
}
- /* 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;
- }
+ iter->walk = iter->safe;
+
+ /* we search for the next head with list entries */
+ if (!iter->walk) {
+ while (iter->index < hash->size) {
+ if (hlist_empty(&hash->table[iter->index]))
+ iter->index++;
+ else {
+ iter->walk = hash->table[iter->index].first;
+
+ /* search next time */
+ ++iter->index;
+ break;
}
- } 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;
}
}
- /* 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;
- }
- }
-
- /* 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++;
- }
- }
+ /* return iter when we found bucket otherwise null */
+ if (!iter->walk)
+ return NULL;
- /* nothing to iterate over anymore */
- return NULL;
+ iter->safe = iter->walk->next;
+ return iter;
}
#endif /* _NET_BATMAN_ADV_HASH_H_ */
diff --git a/batman-adv/originator.c b/batman-adv/originator.c
index 0927119..8e7b15d 100644
--- a/batman-adv/originator.c
+++ b/batman-adv/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/batman-adv/routing.c b/batman-adv/routing.c
index bdb8460..797ccd1 100644
--- a/batman-adv/routing.c
+++ b/batman-adv/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/batman-adv/translation-table.c b/batman-adv/translation-table.c
index 20e1a74..de93c3d 100644
--- a/batman-adv/translation-table.c
+++ b/batman-adv/translation-table.c
@@ -112,8 +112,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)
@@ -142,6 +141,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;
@@ -153,7 +153,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++;
@@ -174,6 +175,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;
@@ -204,7 +206,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);
@@ -263,13 +266,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;
@@ -385,8 +390,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)
@@ -405,6 +409,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;
@@ -434,7 +439,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/batman-adv/vis.c b/batman-adv/vis.c
index 88402c9..9e41f81 100644
--- a/batman-adv/vis.c
+++ b/batman-adv/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))
--
1.7.2.3
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [B.A.T.M.A.N.] [PATCHv3 5/5] batman-adv: Rewrite hash using hlist_*
2010-10-09 12:32 ` [B.A.T.M.A.N.] [PATCHv2 " Sven Eckelmann
@ 2010-10-10 14:26 ` Sven Eckelmann
0 siblings, 0 replies; 9+ messages in thread
From: Sven Eckelmann @ 2010-10-10 14:26 UTC (permalink / raw)
To: b.a.t.m.a.n
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@davemloft.net>
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
* Remove now unused hashdata_compare_cb from hash_resize
* We can also remove head from the iter without loosing essential information
batman-adv/hash.c | 14 ++--
batman-adv/hash.h | 175 ++++++++++++++++------------------------
batman-adv/originator.c | 20 +++--
batman-adv/routing.c | 4 +-
batman-adv/translation-table.c | 22 +++--
batman-adv/vis.c | 29 +++++--
6 files changed, 126 insertions(+), 138 deletions(-)
diff --git a/batman-adv/hash.c b/batman-adv/hash.c
index bfe943c..8605e2f 100644
--- a/batman-adv/hash.c
+++ b/batman-adv/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/batman-adv/hash.h b/batman-adv/hash.h
index a8e4dd1..0b61c6e 100644
--- a/batman-adv/hash.h
+++ b/batman-adv/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/batman-adv/originator.c b/batman-adv/originator.c
index 0927119..8e7b15d 100644
--- a/batman-adv/originator.c
+++ b/batman-adv/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/batman-adv/routing.c b/batman-adv/routing.c
index bdb8460..797ccd1 100644
--- a/batman-adv/routing.c
+++ b/batman-adv/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/batman-adv/translation-table.c b/batman-adv/translation-table.c
index 20e1a74..de93c3d 100644
--- a/batman-adv/translation-table.c
+++ b/batman-adv/translation-table.c
@@ -112,8 +112,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)
@@ -142,6 +141,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;
@@ -153,7 +153,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++;
@@ -174,6 +175,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;
@@ -204,7 +206,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);
@@ -263,13 +266,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;
@@ -385,8 +390,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)
@@ -405,6 +409,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;
@@ -434,7 +439,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/batman-adv/vis.c b/batman-adv/vis.c
index 88402c9..9e41f81 100644
--- a/batman-adv/vis.c
+++ b/batman-adv/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))
--
1.7.2.3
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [B.A.T.M.A.N.] Polishing of the hash implementation
2010-10-09 12:16 [B.A.T.M.A.N.] Polishing of the hash implementation Sven Eckelmann
` (4 preceding siblings ...)
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 5/5] batman-adv: Rewrite hash using hlist_* Sven Eckelmann
@ 2010-10-23 1:41 ` Marek Lindner
5 siblings, 0 replies; 9+ messages in thread
From: Marek Lindner @ 2010-10-23 1:41 UTC (permalink / raw)
To: The list for a Better Approach To Mobile Ad-hoc Networking
On Saturday 09 October 2010 14:16:35 Sven Eckelmann wrote:
> David S. Miller wasn't amused[1] by our hash implementation. Instead he
> proposed some changes we should make. I tried to implement most of them,
> but don't think we should really manually inline every functionality
> currently provided by the hash implementation. I would rather keep the
> heavily used functions as compiler inlineable functions and do the rest
> using standard kernel hlist_*.
Applied in revision 1838-1842.
Thanks,
Marek
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2010-10-23 1:41 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-10-09 12:16 [B.A.T.M.A.N.] Polishing of the hash implementation Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 1/5] batman-adv: Remove hashdata_compare_cb from hash Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 2/5] batman-adv: Remove hashdata_choose_cb " Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 3/5] batman-adv: Move hash callback related function to header Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 4/5] batman-adv: Make hash_iterate inlineable Sven Eckelmann
2010-10-09 12:16 ` [B.A.T.M.A.N.] [PATCH 5/5] batman-adv: Rewrite hash using hlist_* Sven Eckelmann
2010-10-09 12:32 ` [B.A.T.M.A.N.] [PATCHv2 " Sven Eckelmann
2010-10-10 14:26 ` [B.A.T.M.A.N.] [PATCHv3 " Sven Eckelmann
2010-10-23 1:41 ` [B.A.T.M.A.N.] Polishing of the hash implementation Marek Lindner
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).