[B.A.T.M.A.N.] [PATCH] Sync hash implementation of batgat and batman-adv

The compare functions had a different interpretation of its return value and kmalloc can sleep inside batgat because we are running in user context of kernel. --- batman/linux/modules/gateway.c | 4 +- batman/linux/modules/gateway24.c | 4 +- batman/linux/modules/hash.c | 266 ++++++++++++++++++++------------------ batman/linux/modules/hash.h | 9 +- 4 files changed, 149 insertions(+), 134 deletions(-)

diff --git a/batman/linux/modules/gateway.c b/batman/linux/modules/gateway.c index 41d75b5..1f2dc24 100644 --- a/batman/linux/modules/gateway.c +++ b/batman/linux/modules/gateway.c @@ -713,12 +713,12 @@ static struct gw_client *get_ip_addr(struct sockaddr_in *client_addr) * the ip address is the first/second field in the struct */ int compare_wip(void *data1, void *data2) { - return ( memcmp( data1, data2, 4 ) ); + return ( !memcmp( data1, data2, 4 ) ); }

int compare_vip(void *data1, void *data2) { - return ( memcmp( data1 + 4, data2 + 4, 4 ) ); + return ( !memcmp( data1 + 4, data2 + 4, 4 ) ); }

/* hashfunction to choose an entry in a hash table of given size */ diff --git a/batman/linux/modules/gateway24.c b/batman/linux/modules/gateway24.c index dbd1f42..a8d58e6 100644 --- a/batman/linux/modules/gateway24.c +++ b/batman/linux/modules/gateway24.c @@ -693,12 +693,12 @@ static int kernel_recvmsg(struct socket *sock, struct msghdr *msg, struct iovec

int compare_wip(void *data1, void *data2) { - return ( memcmp( data1, data2, 4 ) ); + return ( !memcmp( data1, data2, 4 ) ); }

int compare_vip(void *data1, void *data2) { - return ( memcmp( data1 + 4, data2 + 4, 4 ) ); + return ( !memcmp( data1 + 4, data2 + 4, 4 ) ); }

int choose_wip(void *data, int32_t size) diff --git a/batman/linux/modules/hash.c b/batman/linux/modules/hash.c index ae009be..e88c6e0 100644 --- a/batman/linux/modules/hash.c +++ b/batman/linux/modules/hash.c @@ -1,6 +1,6 @@ -/* Copyright (C) 2006 B.A.T.M.A.N. contributors: +/* + * Copyright (C) 2006-2008 B.A.T.M.A.N. contributors: * Simon Wunderlich, Marek Lindner - * * This program is free software; you can redistribute it and/or * modify it under the terms of version 2 of the GNU General Public * License as published by the Free Software Foundation. @@ -17,294 +17,304 @@ * */

+ + + + #include <linux/string.h> /* strlen, strstr, strncmp ... */ #include <linux/slab.h> #include "hash.h"

+ /* clears the hash */ -void hash_init(struct hashtable_t *hash) { +void hash_init(struct hashtable_t *hash) +{ int i; - hash->elements=0; - for (i=0 ; i<hash->size ; i++) { + + hash->elements = 0; + + for (i = 0 ; i < hash->size; i++) 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 hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb) +{ struct element_t *bucket, *last_bucket; int i;

- for (i=0; i<hash->size; i++) { + for (i = 0; i < hash->size; i++) { + bucket = hash->table[i];

- bucket= hash->table[i]; while (bucket != NULL) { + if (free_cb != NULL) + free_cb(bucket->data);

- if (free_cb!=NULL) - free_cb( bucket->data ); - - last_bucket= bucket; - bucket= bucket->next; + 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) { - - kfree( hash->table ); - kfree( hash ); - +void hash_destroy(struct hashtable_t *hash) +{ + kfree(hash->table); + kfree(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) { +struct hash_it_t *hash_iterate(struct hashtable_t *hash, struct hash_it_t *iter_in) +{ struct hash_it_t *iter;

if (iter_in == NULL) { - iter= kmalloc(sizeof(struct hash_it_t), GFP_KERNEL); - iter->index = -1; + iter = kmalloc(sizeof(struct hash_it_t), GFP_KERNEL); + iter->index = -1; iter->bucket = NULL; iter->prev_bucket = NULL; - } else + } else { iter= iter_in; + }

/* sanity checks first (if our bucket got deleted in the last iteration): */ - if (iter->bucket!=NULL) { + 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 ) { + if ((*iter->first_bucket) != NULL) { iter->prev_bucket = NULL; - iter->bucket= (*iter->first_bucket); - iter->first_bucket = &hash->table[ iter->index ]; - return(iter); + 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. + } 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; - + * 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; + 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); + return iter; } } - /* if not returned yet, we've reached the last one on the index and have to search forward */

+ /* if not returned yet, we've reached the last one on the index and have to search forward */ iter->index++; - while ( iter->index < hash->size ) { /* go through the entries of the hash table */ - if ((hash->table[ iter->index ]) != NULL){ + /* 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); /* if this table entry is not null, return it */ - } else - iter->index++; /* else, go to the next */ + iter->bucket = hash->table[iter->index]; + iter->first_bucket = &hash->table[iter->index]; + return iter; + } else { + iter->index++; + } } + /* nothing to iterate over anymore */ kfree(iter); - return(NULL); + return NULL; }

- /* 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_compare_cb compare, hashdata_choose_cb choose) +{ struct hashtable_t *hash;

- hash= kmalloc( sizeof(struct hashtable_t) , GFP_KERNEL); - if ( hash == NULL ) /* could not allocate the hash control structure */ - return (NULL); + hash = kmalloc(sizeof(struct hashtable_t) , GFP_KERNEL); + + if (hash == NULL) + return NULL;

- hash->size= size; - hash->table= kmalloc( sizeof(struct element_t *) * size, GFP_KERNEL); - if ( hash->table == NULL ) { /* could not allocate the table */ + hash->size = size; + hash->table = kmalloc(sizeof(struct element_t *) * size, GFP_KERNEL); + + if (hash->table == NULL) { kfree(hash); - return(NULL); + return NULL; } + hash_init(hash); - hash->compare= compare; - hash->choose= choose; - return(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, void *data) +{ int index; struct element_t *bucket, *prev_bucket = NULL;

- index = hash->choose( data, hash->size ); + index = hash->choose(data, hash->size); bucket = hash->table[index];

- while ( bucket!=NULL ) { - if (0 == hash->compare( bucket->data, data )) - return(-1); + while (bucket != NULL) { + if (hash->compare(bucket->data, data)) + return -1;

prev_bucket = bucket; - bucket= bucket->next; + bucket = bucket->next; }

/* found the tail of the list, add new element */ - if (NULL == (bucket= kmalloc(sizeof(struct element_t),GFP_KERNEL))) - return(-1); /* debugMalloc failed */ + bucket = kmalloc(sizeof(struct element_t),GFP_KERNEL); + + if (bucket == NULL) + return -1;

- bucket->data= data; /* init the new bucket */ - bucket->next= NULL; + bucket->data = data; + bucket->next = NULL;

/* and link it */ - if ( prev_bucket == NULL ) { + if (prev_bucket == NULL) hash->table[index] = bucket; - } else { + else prev_bucket->next = bucket; - }

hash->elements++; - return(0); - + 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, void *keydata) { +void *hash_find(struct hashtable_t *hash, void *keydata) +{ int index; struct element_t *bucket;

- index = hash->choose( keydata , hash->size ); + index = hash->choose(keydata , hash->size); bucket = hash->table[index];

- while ( bucket!=NULL ) { - if (0 == hash->compare( bucket->data, keydata )) - return( bucket->data ); + while (bucket != NULL) { + if (hash->compare(bucket->data, keydata)) + return bucket->data;

- bucket= bucket->next; + bucket = bucket->next; }

- return(NULL); - + 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 fiddles with hash-internals. */ -void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) { +void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) +{ void *data_save;

- data_save = hash_it_t->bucket->data; /* save the pointer to the data */ + data_save = hash_it_t->bucket->data;

- if ( hash_it_t->prev_bucket != NULL ) { + 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 ) { + else if (hash_it_t->first_bucket != NULL) (*hash_it_t->first_bucket) = hash_it_t->bucket->next; - }

kfree(hash_it_t->bucket); - hash->elements--; - return( data_save );

+ 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, void *data) { +void *hash_remove(struct hashtable_t *hash, void *data) +{ struct hash_it_t hash_it_t;

- hash_it_t.index = hash->choose( data, hash->size ); + hash_it_t.index = hash->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 (0 == hash->compare( hash_it_t.bucket->data, data )) { + while (hash_it_t.bucket != NULL) { + if (hash->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) ); + 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); - + 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, int size) { +struct hashtable_t *hash_resize(struct hashtable_t *hash, int size) +{ struct hashtable_t *new_hash; struct element_t *bucket; int i;

/* initialize a new hash with the new size */ - if (NULL == (new_hash= hash_new(size, hash->compare, hash->choose))) - return(NULL); + new_hash = hash_new(size, hash->compare, hash->choose); + + if (new_hash == NULL) + return NULL;

/* copy the elements */ - for (i=0; i<hash->size; i++) { - bucket= hash->table[i]; + for (i = 0; i < hash->size; i++) { + bucket = hash->table[i]; + while (bucket != NULL) { - hash_add( new_hash, bucket->data ); - bucket= bucket->next; + hash_add(new_hash, bucket->data); + bucket = bucket->next; } } - hash_delete(hash, NULL); /* remove hash and eventual overflow buckets but not the content itself. */

- return( new_hash); + /* remove hash and eventual overflow buckets but not the content itself. */ + hash_delete(hash, NULL);

+ return new_hash; }

-/* print the hash table for debugging */ -void hash_debug(struct hashtable_t *hash) { +/* print the hash table for debugging +void hash_debug(struct hashtable_t *hash) +{ int i; struct element_t *bucket;

for (i=0; i<hash->size;i++) { - printk("[%d] ",i); + printf("[%d] ",i); bucket= hash->table[i];

while (bucket != NULL) { - printk("-> [%10p] ", bucket); + printf("-> [%10p] ", bucket); bucket= bucket->next; }

- printk("\n"); + printf("\n");

} - printk("\n"); + printf("\n"); } + */

diff --git a/batman/linux/modules/hash.h b/batman/linux/modules/hash.h index a87cdcb..a778f04 100644 --- a/batman/linux/modules/hash.h +++ b/batman/linux/modules/hash.h @@ -1,6 +1,6 @@ -/* Copyright (C) 2006 B.A.T.M.A.N. contributors: +/* + * Copyright (C) 2006-2008 B.A.T.M.A.N. contributors: * Simon Wunderlich, Marek Lindner - * * This program is free software; you can redistribute it and/or * modify it under the terms of version 2 of the GNU General Public * License as published by the Free Software Foundation. @@ -16,6 +16,11 @@ * 02110-1301, USA * */ + + + + + #ifndef _BATMAN_HASH_H #define _BATMAN_HASH_H