Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

[PATCH] Staging: tidspbridge: Use hashtable implementation

3 views
Skip to first unread message

Ivaylo DImitrov

unread,
Dec 25, 2013, 12:40:01 PM12/25/13
to
From: Ivaylo Dimitrov <freema...@abv.bg>

Use upstream hashtable implementation instead of generic code

Signed-off-by: Ivaylo Dimitrov <freema...@abv.bg>
---
drivers/staging/tidspbridge/gen/gh.c | 141 +++++++-------------
drivers/staging/tidspbridge/include/dspbridge/gh.h | 6 +-
drivers/staging/tidspbridge/pmgr/dbll.c | 47 ++++---
3 files changed, 78 insertions(+), 116 deletions(-)

diff --git a/drivers/staging/tidspbridge/gen/gh.c b/drivers/staging/tidspbridge/gen/gh.c
index 25eaef7..41a0a4f 100644
--- a/drivers/staging/tidspbridge/gen/gh.c
+++ b/drivers/staging/tidspbridge/gen/gh.c
@@ -14,56 +14,46 @@
* WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*/

-#include <linux/types.h>
+#include <linux/err.h>
+#include <linux/hashtable.h>
+#include <linux/slab.h>

-#include <dspbridge/host_os.h>
-#include <dspbridge/gh.h>
-
-struct element {
- struct element *next;
+struct gh_node {
+ struct hlist_node hl;
u8 data[1];
};

+#define GH_HASH_ORDER 8
+
struct gh_t_hash_tab {
- u16 max_bucket;
- u16 val_size;
- struct element **buckets;
- u16(*hash) (void *, u16);
- bool(*match) (void *, void *);
- void (*delete) (void *);
+ u32 val_size;
+ DECLARE_HASHTABLE(hash_table, GH_HASH_ORDER);
+ u32 (*hash)(void *);
+ bool (*match)(void *, void *);
+ void (*delete)(void *);
};

-static void noop(void *p);
-
/*
* ======== gh_create ========
*/

-struct gh_t_hash_tab *gh_create(u16 max_bucket, u16 val_size,
- u16(*hash) (void *, u16), bool(*match) (void *,
- void *),
- void (*delete) (void *))
+struct gh_t_hash_tab *gh_create(u32 val_size,u32 (*hash)(void *),
+ bool (*match)(void *, void *),
+ void (*delete)(void *))
{
struct gh_t_hash_tab *hash_tab;
- u16 i;
+
hash_tab = kzalloc(sizeof(struct gh_t_hash_tab), GFP_KERNEL);
- if (hash_tab == NULL)
- return NULL;
- hash_tab->max_bucket = max_bucket;
+
+ if (!hash_tab)
+ return ERR_PTR(-ENOMEM);
+
+ hash_init(hash_tab->hash_table);
+
hash_tab->val_size = val_size;
hash_tab->hash = hash;
hash_tab->match = match;
- hash_tab->delete = delete == NULL ? noop : delete;
-
- hash_tab->buckets =
- kzalloc(sizeof(struct element *) * max_bucket, GFP_KERNEL);
- if (hash_tab->buckets == NULL) {
- gh_delete(hash_tab);
- return NULL;
- }
-
- for (i = 0; i < max_bucket; i++)
- hash_tab->buckets[i] = NULL;
+ hash_tab->delete = delete;

return hash_tab;
}
@@ -73,21 +63,16 @@ struct gh_t_hash_tab *gh_create(u16 max_bucket, u16 val_size,
*/
void gh_delete(struct gh_t_hash_tab *hash_tab)
{
- struct element *elem, *next;
- u16 i;
-
- if (hash_tab != NULL) {
- if (hash_tab->buckets != NULL) {
- for (i = 0; i < hash_tab->max_bucket; i++) {
- for (elem = hash_tab->buckets[i]; elem != NULL;
- elem = next) {
- next = elem->next;
- (*hash_tab->delete) (elem->data);
- kfree(elem);
- }
- }
-
- kfree(hash_tab->buckets);
+ struct gh_node *n;
+ struct hlist_node *tmp;
+ u32 i;
+
+ if (hash_tab) {
+ hash_for_each_safe(hash_tab->hash_table, i, tmp, n, hl) {
+ hash_del(&n->hl);
+ if(hash_tab->delete)
+ hash_tab->delete(n->data);
+ kfree(n);
}

kfree(hash_tab);
@@ -100,16 +85,14 @@ void gh_delete(struct gh_t_hash_tab *hash_tab)

void *gh_find(struct gh_t_hash_tab *hash_tab, void *key)
{
- struct element *elem;
-
- elem = hash_tab->buckets[(*hash_tab->hash) (key, hash_tab->max_bucket)];
+ struct gh_node *n;
+ u32 key_hash = hash_tab->hash(key);

- for (; elem; elem = elem->next) {
- if ((*hash_tab->match) (key, elem->data))
- return elem->data;
- }
+ hash_for_each_possible(hash_tab->hash_table, n, hl, key_hash)
+ if (hash_tab->match(key, n->data))
+ return n->data;

- return NULL;
+ return ERR_PTR(-ENODATA);
}

/*
@@ -118,36 +101,19 @@ void *gh_find(struct gh_t_hash_tab *hash_tab, void *key)

void *gh_insert(struct gh_t_hash_tab *hash_tab, void *key, void *value)
{
- struct element *elem;
- u16 i;
- char *src, *dst;
+ struct gh_node *n;

- elem = kzalloc(sizeof(struct element) - 1 + hash_tab->val_size,
+ n = kmalloc(sizeof(struct gh_node) - 1 + hash_tab->val_size,
GFP_KERNEL);
- if (elem != NULL) {

- dst = (char *)elem->data;
- src = (char *)value;
- for (i = 0; i < hash_tab->val_size; i++)
- *dst++ = *src++;
+ if(!n)
+ return ERR_PTR(-ENOMEM);

- i = (*hash_tab->hash) (key, hash_tab->max_bucket);
- elem->next = hash_tab->buckets[i];
- hash_tab->buckets[i] = elem;
+ INIT_HLIST_NODE(&n->hl);
+ hash_add(hash_tab->hash_table, &n->hl, hash_tab->hash(key));
+ memcpy(n->data, value, hash_tab->val_size);

- return elem->data;
- }
-
- return NULL;
-}
-
-/*
- * ======== noop ========
- */
-/* ARGSUSED */
-static void noop(void *p)
-{
- p = p; /* stifle compiler warning */
+ return n->data;
}

#ifdef CONFIG_TIDSPBRIDGE_BACKTRACE
@@ -162,16 +128,11 @@ static void noop(void *p)
void gh_iterate(struct gh_t_hash_tab *hash_tab,
void (*callback)(void *, void *), void *user_data)
{
- struct element *elem;
+ struct gh_node *n;
u32 i;

- if (hash_tab && hash_tab->buckets)
- for (i = 0; i < hash_tab->max_bucket; i++) {
- elem = hash_tab->buckets[i];
- while (elem) {
- callback(&elem->data, user_data);
- elem = elem->next;
- }
- }
+ if (hash_tab)
+ hash_for_each(hash_tab->hash_table, i, n, hl)
+ callback(&n->data, user_data);
}
#endif
diff --git a/drivers/staging/tidspbridge/include/dspbridge/gh.h b/drivers/staging/tidspbridge/include/dspbridge/gh.h
index da85079..6ce69f4 100644
--- a/drivers/staging/tidspbridge/include/dspbridge/gh.h
+++ b/drivers/staging/tidspbridge/include/dspbridge/gh.h
@@ -18,9 +18,9 @@
#define GH_
#include <dspbridge/host_os.h>

-extern struct gh_t_hash_tab *gh_create(u16 max_bucket, u16 val_size,
- u16(*hash) (void *, u16),
- bool(*match) (void *, void *),
+extern struct gh_t_hash_tab *gh_create(u32 val_size,
+ u32 (*hash)(void *),
+ bool (*match)(void *, void *),
void (*delete) (void *));
extern void gh_delete(struct gh_t_hash_tab *hash_tab);
extern void *gh_find(struct gh_t_hash_tab *hash_tab, void *key);
diff --git a/drivers/staging/tidspbridge/pmgr/dbll.c b/drivers/staging/tidspbridge/pmgr/dbll.c
index 41e88ab..234a433 100644
--- a/drivers/staging/tidspbridge/pmgr/dbll.c
+++ b/drivers/staging/tidspbridge/pmgr/dbll.c
@@ -33,9 +33,6 @@
#include <dspbridge/dbll.h>
#include <dspbridge/rmm.h>

-/* Number of buckets for symbol hash table */
-#define MAXBUCKETS 211
-
/* Max buffer length */
#define MAXEXPR 128

@@ -183,7 +180,7 @@ static int execute(struct dynamic_loader_initialize *this, ldr_addr start);
static void release(struct dynamic_loader_initialize *this);

/* symbol table hash functions */
-static u16 name_hash(void *key, u16 max_bucket);
+static u32 name_hash(void *key);
static bool name_match(void *key, void *sp);
static void sym_delete(void *value);

@@ -280,7 +277,7 @@ bool dbll_get_addr(struct dbll_library_obj *zl_lib, char *name,
bool status = false;

sym = (struct dbll_symbol *)gh_find(zl_lib->sym_tab, name);
- if (sym != NULL) {
+ if (!IS_ERR(sym)) {
*sym_val = &sym->value;
status = true;
}
@@ -322,7 +319,7 @@ bool dbll_get_c_addr(struct dbll_library_obj *zl_lib, char *name,
/* Check for C name, if not found */
sym = (struct dbll_symbol *)gh_find(zl_lib->sym_tab, cname);

- if (sym != NULL) {
+ if (!IS_ERR(sym)) {
*sym_val = &sym->value;
status = true;
}
@@ -416,12 +413,13 @@ int dbll_load(struct dbll_library_obj *lib, dbll_flags flags,
/* Create a hash table for symbols if not already created */
if (zl_lib->sym_tab == NULL) {
got_symbols = false;
- zl_lib->sym_tab = gh_create(MAXBUCKETS,
- sizeof(struct dbll_symbol),
+ zl_lib->sym_tab = gh_create(sizeof(struct dbll_symbol),
name_hash,
name_match, sym_delete);
- if (zl_lib->sym_tab == NULL)
- status = -ENOMEM;
+ if (IS_ERR(zl_lib->sym_tab)) {
+ status = PTR_ERR(zl_lib->sym_tab);
+ zl_lib->sym_tab = NULL;
+ }

}
/*
@@ -593,10 +591,11 @@ int dbll_open(struct dbll_tar_obj *target, char *file, dbll_flags flags,
goto func_cont;

zl_lib->sym_tab =
- gh_create(MAXBUCKETS, sizeof(struct dbll_symbol), name_hash,
- name_match, sym_delete);
- if (zl_lib->sym_tab == NULL) {
- status = -ENOMEM;
+ gh_create(sizeof(struct dbll_symbol), name_hash, name_match,
+ sym_delete);
+ if (IS_ERR(zl_lib->sym_tab)) {
+ status = PTR_ERR(zl_lib->sym_tab);
+ zl_lib->sym_tab = NULL;
} else {
/* Do a fake load to get symbols - set write func to no_op */
zl_lib->init.dl_init.writemem = no_op;
@@ -793,10 +792,9 @@ static int dof_open(struct dbll_library_obj *zl_lib)
/*
* ======== name_hash ========
*/
-static u16 name_hash(void *key, u16 max_bucket)
+static u32 name_hash(void *key)
{
- u16 ret;
- u16 hash;
+ u32 hash;
char *name = (char *)key;

hash = 0;
@@ -806,9 +804,7 @@ static u16 name_hash(void *key, u16 max_bucket)
hash ^= *name++;
}

- ret = hash % max_bucket;
-
- return ret;
+ return hash;
}

/*
@@ -937,7 +933,7 @@ static struct dynload_symbol *find_in_symbol_table(struct dynamic_loader_sym
*this, const char *name,
unsigned moduleid)
{
- struct dynload_symbol *ret_sym;
+ struct dynload_symbol *ret_sym = NULL;
struct ldr_symbol *ldr_sym = (struct ldr_symbol *)this;
struct dbll_library_obj *lib;
struct dbll_symbol *sym;
@@ -945,7 +941,9 @@ static struct dynload_symbol *find_in_symbol_table(struct dynamic_loader_sym
lib = ldr_sym->lib;
sym = (struct dbll_symbol *)gh_find(lib->sym_tab, (char *)name);

- ret_sym = (struct dynload_symbol *)&sym->value;
+ if (!IS_ERR(sym))
+ ret_sym = (struct dynload_symbol *)&sym->value;
+
return ret_sym;
}

@@ -991,8 +989,11 @@ static struct dynload_symbol *dbll_add_to_symbol_table(struct dynamic_loader_sym
sym_ptr =
(struct dbll_symbol *)gh_insert(lib->sym_tab, (void *)name,
(void *)&symbol);
- if (sym_ptr == NULL)
+ if (IS_ERR(sym_ptr))
+ {
kfree(symbol.name);
+ sym_ptr = NULL;
+ }

}
if (sym_ptr != NULL)
--
1.5.6.1

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majo...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Pavel Machek

unread,
Dec 27, 2013, 4:50:02 AM12/27/13
to
Hi!

> From: Ivaylo Dimitrov <freema...@abv.bg>
>
> Use upstream hashtable implementation instead of generic code
>
> Signed-off-by: Ivaylo Dimitrov <freema...@abv.bg>

> @@ -991,8 +989,11 @@ static struct dynload_symbol *dbll_add_to_symbol_table(struct dynamic_loader_sym
> sym_ptr =
> (struct dbll_symbol *)gh_insert(lib->sym_tab, (void *)name,
> (void *)&symbol);
> - if (sym_ptr == NULL)
> + if (IS_ERR(sym_ptr))
> + {

You want this { to go to the previous line. Otherwise looks good,

Reviewed-by: Pavel Machek <pa...@ucw.cz>

Thanks,

Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Ivaylo Dimitrov

unread,
Dec 27, 2013, 11:00:03 AM12/27/13
to
From: Ivaylo Dimitrov <freema...@abv.bg>

Use upstream hashtable implementation instead of generic code

Signed-off-by: Ivaylo Dimitrov <freema...@abv.bg>
---
drivers/staging/tidspbridge/gen/gh.c | 141 +++++++-------------
drivers/staging/tidspbridge/include/dspbridge/gh.h | 6 +-
drivers/staging/tidspbridge/pmgr/dbll.c | 46 +++---
3 files changed, 77 insertions(+), 116 deletions(-)
index 41e88ab..931d5be 100644
@@ -991,8 +989,10 @@ static struct dynload_symbol *dbll_add_to_symbol_table(struct dynamic_loader_sym
sym_ptr =
(struct dbll_symbol *)gh_insert(lib->sym_tab, (void *)name,
(void *)&symbol);
- if (sym_ptr == NULL)
+ if (IS_ERR(sym_ptr)) {
kfree(symbol.name);
+ sym_ptr = NULL;
+ }

}
if (sym_ptr != NULL)
--
1.5.6.1

Dan Carpenter

unread,
Jan 2, 2014, 8:50:01 AM1/2/14
to
Minor nits. Nothing major.

On Wed, Dec 25, 2013 at 07:29:52PM +0200, Ivaylo DImitrov wrote:
> From: Ivaylo Dimitrov <freema...@abv.bg>
>
> Use upstream hashtable implementation instead of generic code
>
> Signed-off-by: Ivaylo Dimitrov <freema...@abv.bg>

Send from the same email you are using to Sign so we can at least
verify that small thing.

> ---
> drivers/staging/tidspbridge/gen/gh.c | 141 +++++++-------------
> drivers/staging/tidspbridge/include/dspbridge/gh.h | 6 +-
> drivers/staging/tidspbridge/pmgr/dbll.c | 47 ++++---
> 3 files changed, 78 insertions(+), 116 deletions(-)
>
> diff --git a/drivers/staging/tidspbridge/gen/gh.c b/drivers/staging/tidspbridge/gen/gh.c
> index 25eaef7..41a0a4f 100644
> --- a/drivers/staging/tidspbridge/gen/gh.c
> +++ b/drivers/staging/tidspbridge/gen/gh.c
> @@ -14,56 +14,46 @@
> * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
> */
>
> -#include <linux/types.h>
> +#include <linux/err.h>
> +#include <linux/hashtable.h>
> +#include <linux/slab.h>
>
> -#include <dspbridge/host_os.h>
> -#include <dspbridge/gh.h>
> -
> -struct element {
> - struct element *next;
> +struct gh_node {
> + struct hlist_node hl;
> u8 data[1];

Use a zero size array here so that you can remove the " - 1" from
"sizeof(struct gh_node) - 1 + hash_tab->val_size". (Fix in later
patches).
Don't put a blank line here between the call and the error handling.
Use checkpatch.pl.

> + hash_tab->delete(n->data);
> + kfree(n);
> }
>
> kfree(hash_tab);
> @@ -100,16 +85,14 @@ void gh_delete(struct gh_t_hash_tab *hash_tab)
>
> void *gh_find(struct gh_t_hash_tab *hash_tab, void *key)
> {
> - struct element *elem;
> -
> - elem = hash_tab->buckets[(*hash_tab->hash) (key, hash_tab->max_bucket)];
> + struct gh_node *n;
> + u32 key_hash = hash_tab->hash(key);
>
> - for (; elem; elem = elem->next) {
> - if ((*hash_tab->match) (key, elem->data))
> - return elem->data;
> - }
> + hash_for_each_possible(hash_tab->hash_table, n, hl, key_hash)
> + if (hash_tab->match(key, n->data))
> + return n->data;

Multi-line indents get curly braces for readability.
Multi-line indents get curly braces. But it would be better to reverse
this anyway.

if (!hash_tab)
return;

hash_for_each(hash_tab->hash_table, i, n, hl)
Remove the unneeded casts... (in later patches).

> - if (sym != NULL) {
> + if (!IS_ERR(sym)) {
> *sym_val = &sym->value;
> status = true;
> }

When ever I see a !IS_ERR() then it weirds me out. In this case my
intuition is correct and this function is super uglier than necessary
because of all the stupid debug code. It should just be:

bool dbll_get_addr(struct dbll_library_obj *zl_lib, char *name,
struct dbll_sym_val **sym_val)
{
struct dbll_symbol *sym;

sym = gh_find(zl_lib->sym_tab, name);
if (IS_ERR(sym))
return false;

*sym_val = &sym->value;
return true;
Don't put a blank line between the function and the error handling. (In
this case it's actually "success handling", I suppose. :P).

> - ret_sym = (struct dynload_symbol *)&sym->value;
> + if (!IS_ERR(sym))
> + ret_sym = (struct dynload_symbol *)&sym->value;
> +
> return ret_sym;

Again, reverse the IS_ERR() check and return directly. Use the struct
pointer instead of the address of the first member.

sym = gh_find(lib->sym_tab, (char *)name);
if (IS_ERR(sym))
return NULL;

return (struct dbll_symbol *)sym;

That way is easier to read. gh_find() should accept const pointers btw,
we shouldn't have to cast away the const in each of the callers.

> }
>
> @@ -991,8 +989,11 @@ static struct dynload_symbol *dbll_add_to_symbol_table(struct dynamic_loader_sym
> sym_ptr =
> (struct dbll_symbol *)gh_insert(lib->sym_tab, (void *)name,
> (void *)&symbol);
> - if (sym_ptr == NULL)
> + if (IS_ERR(sym_ptr))
> + {
> kfree(symbol.name);
> + sym_ptr = NULL;
> + }

Checkpatch. Same issues as before for a later patch series.

regards,
dan carpenter

Dan Carpenter

unread,
Jan 2, 2014, 10:10:01 AM1/2/14
to
> + u32 val_size;
> + DECLARE_HASHTABLE(hash_table, GH_HASH_ORDER);
> + u32 (*hash)(void *);
> + bool (*match)(void *, void *);
> + void (*delete)(void *);

I forgot to say, put the parameter name in the declaration.

+ u32 (*hash)(void *key);
+ bool (*match)(void *key, void *result);
+ void (*delete)(void *key);

I have no idea if those names are correct.

regards,
dan carpenter

Ivaylo Dimitrov

unread,
Jan 5, 2014, 2:00:02 PM1/5/14
to
From: Ivaylo Dimitrov <freema...@abv.bg>

Use upstream hashtable implementation instead of generic code

Signed-off-by: Ivaylo Dimitrov <ivo.g.di...@gmail.com>
---
drivers/staging/tidspbridge/gen/gh.c | 148 ++++++++------------
drivers/staging/tidspbridge/include/dspbridge/gh.h | 12 +-
drivers/staging/tidspbridge/pmgr/dbll.c | 78 +++++------
3 files changed, 99 insertions(+), 139 deletions(-)

diff --git a/drivers/staging/tidspbridge/gen/gh.c b/drivers/staging/tidspbridge/gen/gh.c
index 25eaef7..936470c 100644
--- a/drivers/staging/tidspbridge/gen/gh.c
+++ b/drivers/staging/tidspbridge/gen/gh.c
@@ -14,56 +14,45 @@
* WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*/

-#include <linux/types.h>
+#include <linux/err.h>
+#include <linux/hashtable.h>
+#include <linux/slab.h>

-#include <dspbridge/host_os.h>
-#include <dspbridge/gh.h>
-
-struct element {
- struct element *next;
- u8 data[1];
+struct gh_node {
+ struct hlist_node hl;
+ u8 data[0];
};

+#define GH_HASH_ORDER 8
+
struct gh_t_hash_tab {
- u16 max_bucket;
- u16 val_size;
- struct element **buckets;
- u16(*hash) (void *, u16);
- bool(*match) (void *, void *);
- void (*delete) (void *);
+ u32 val_size;
+ DECLARE_HASHTABLE(hash_table, GH_HASH_ORDER);
+ u32 (*hash)(const void *key);
+ bool (*match)(const void *key, const void *value);
+ void (*delete)(void *key);
};

-static void noop(void *p);
-
/*
* ======== gh_create ========
*/

-struct gh_t_hash_tab *gh_create(u16 max_bucket, u16 val_size,
- u16(*hash) (void *, u16), bool(*match) (void *,
- void *),
- void (*delete) (void *))
+struct gh_t_hash_tab *gh_create(u32 val_size, u32 (*hash)(const void *),
+ bool (*match)(const void *, const void *),
+ void (*delete)(void *))
{
struct gh_t_hash_tab *hash_tab;
- u16 i;
+
hash_tab = kzalloc(sizeof(struct gh_t_hash_tab), GFP_KERNEL);
- if (hash_tab == NULL)
- return NULL;
- hash_tab->max_bucket = max_bucket;
+ if (!hash_tab)
+ return ERR_PTR(-ENOMEM);
+
+ hash_init(hash_tab->hash_table);
+
hash_tab->val_size = val_size;
hash_tab->hash = hash;
hash_tab->match = match;
- hash_tab->delete = delete == NULL ? noop : delete;
-
- hash_tab->buckets =
- kzalloc(sizeof(struct element *) * max_bucket, GFP_KERNEL);
- if (hash_tab->buckets == NULL) {
- gh_delete(hash_tab);
- return NULL;
- }
-
- for (i = 0; i < max_bucket; i++)
- hash_tab->buckets[i] = NULL;
+ hash_tab->delete = delete;

return hash_tab;
}
@@ -73,21 +62,16 @@ struct gh_t_hash_tab *gh_create(u16 max_bucket, u16 val_size,
+ hash_tab->delete(n->data);
+ kfree(n);
}

kfree(hash_tab);
@@ -98,56 +82,39 @@ void gh_delete(struct gh_t_hash_tab *hash_tab)
* ======== gh_find ========
*/

-void *gh_find(struct gh_t_hash_tab *hash_tab, void *key)
+void *gh_find(struct gh_t_hash_tab *hash_tab, const void *key)
{
- struct element *elem;
+ struct gh_node *n;
+ u32 key_hash = hash_tab->hash(key);

- elem = hash_tab->buckets[(*hash_tab->hash) (key, hash_tab->max_bucket)];
-
- for (; elem; elem = elem->next) {
- if ((*hash_tab->match) (key, elem->data))
- return elem->data;
+ hash_for_each_possible(hash_tab->hash_table, n, hl, key_hash) {
+ if (hash_tab->match(key, n->data))
+ return n->data;
}

- return NULL;
+ return ERR_PTR(-ENODATA);
}

/*
* ======== gh_insert ========
*/

-void *gh_insert(struct gh_t_hash_tab *hash_tab, void *key, void *value)
+void *gh_insert(struct gh_t_hash_tab *hash_tab, const void *key,
+ const void *value)
{
- struct element *elem;
- u16 i;
- char *src, *dst;
+ struct gh_node *n;

- elem = kzalloc(sizeof(struct element) - 1 + hash_tab->val_size,
+ n = kmalloc(sizeof(struct gh_node) + hash_tab->val_size,
GFP_KERNEL);
- if (elem != NULL) {
-
- dst = (char *)elem->data;
- src = (char *)value;
- for (i = 0; i < hash_tab->val_size; i++)
- *dst++ = *src++;

- i = (*hash_tab->hash) (key, hash_tab->max_bucket);
- elem->next = hash_tab->buckets[i];
- hash_tab->buckets[i] = elem;
+ if (!n)
+ return ERR_PTR(-ENOMEM);

- return elem->data;
- }
-
- return NULL;
-}
+ INIT_HLIST_NODE(&n->hl);
+ hash_add(hash_tab->hash_table, &n->hl, hash_tab->hash(key));
+ memcpy(n->data, value, hash_tab->val_size);

-/*
- * ======== noop ========
- */
-/* ARGSUSED */
-static void noop(void *p)
-{
- p = p; /* stifle compiler warning */
+ return n->data;
}

#ifdef CONFIG_TIDSPBRIDGE_BACKTRACE
@@ -162,16 +129,13 @@ static void noop(void *p)
void gh_iterate(struct gh_t_hash_tab *hash_tab,
void (*callback)(void *, void *), void *user_data)
{
- struct element *elem;
+ struct gh_node *n;
u32 i;

- if (hash_tab && hash_tab->buckets)
- for (i = 0; i < hash_tab->max_bucket; i++) {
- elem = hash_tab->buckets[i];
- while (elem) {
- callback(&elem->data, user_data);
- elem = elem->next;
- }
- }
+ if (!hash_tab)
+ return;
+
+ hash_for_each(hash_tab->hash_table, i, n, hl)
+ callback(&n->data, user_data);
}
#endif
diff --git a/drivers/staging/tidspbridge/include/dspbridge/gh.h b/drivers/staging/tidspbridge/include/dspbridge/gh.h
index da85079..e4303b4 100644
--- a/drivers/staging/tidspbridge/include/dspbridge/gh.h
+++ b/drivers/staging/tidspbridge/include/dspbridge/gh.h
@@ -18,13 +18,13 @@
#define GH_
#include <dspbridge/host_os.h>

-extern struct gh_t_hash_tab *gh_create(u16 max_bucket, u16 val_size,
- u16(*hash) (void *, u16),
- bool(*match) (void *, void *),
- void (*delete) (void *));
+extern struct gh_t_hash_tab *gh_create(u32 val_size,
+ u32 (*hash)(const void *), bool (*match)(const void *,
+ const void *), void (*delete) (void *));
extern void gh_delete(struct gh_t_hash_tab *hash_tab);
-extern void *gh_find(struct gh_t_hash_tab *hash_tab, void *key);
-extern void *gh_insert(struct gh_t_hash_tab *hash_tab, void *key, void *value);
+extern void *gh_find(struct gh_t_hash_tab *hash_tab, const void *key);
+extern void *gh_insert(struct gh_t_hash_tab *hash_tab, const void *key,
+ const void *value);
#ifdef CONFIG_TIDSPBRIDGE_BACKTRACE
void gh_iterate(struct gh_t_hash_tab *hash_tab,
void (*callback)(void *, void *), void *user_data);
diff --git a/drivers/staging/tidspbridge/pmgr/dbll.c b/drivers/staging/tidspbridge/pmgr/dbll.c
index 41e88ab..764dbe5 100644
--- a/drivers/staging/tidspbridge/pmgr/dbll.c
+++ b/drivers/staging/tidspbridge/pmgr/dbll.c
@@ -33,9 +33,6 @@
#include <dspbridge/dbll.h>
#include <dspbridge/rmm.h>

-/* Number of buckets for symbol hash table */
-#define MAXBUCKETS 211
-
/* Max buffer length */
#define MAXEXPR 128

@@ -183,8 +180,8 @@ static int execute(struct dynamic_loader_initialize *this, ldr_addr start);
static void release(struct dynamic_loader_initialize *this);

/* symbol table hash functions */
-static u16 name_hash(void *key, u16 max_bucket);
-static bool name_match(void *key, void *sp);
+static u32 name_hash(const void *key);
+static bool name_match(const void *key, const void *sp);
static void sym_delete(void *value);

/* Symbol Redefinition */
@@ -277,17 +274,16 @@ bool dbll_get_addr(struct dbll_library_obj *zl_lib, char *name,
struct dbll_sym_val **sym_val)
{
struct dbll_symbol *sym;
- bool status = false;

sym = (struct dbll_symbol *)gh_find(zl_lib->sym_tab, name);
- if (sym != NULL) {
- *sym_val = &sym->value;
- status = true;
- }
+ if (IS_ERR(sym))
+ return false;

- dev_dbg(bridge, "%s: lib: %p name: %s paddr: %p, status 0x%x\n",
- __func__, zl_lib, name, sym_val, status);
- return status;
+ *sym_val = &sym->value;
+
+ dev_dbg(bridge, "%s: lib: %p name: %s paddr: %p\n",
+ __func__, zl_lib, name, sym_val);
+ return true;
}

/*
@@ -312,7 +308,6 @@ bool dbll_get_c_addr(struct dbll_library_obj *zl_lib, char *name,
{
struct dbll_symbol *sym;
char cname[MAXEXPR + 1];
- bool status = false;

cname[0] = '_';

@@ -321,13 +316,12 @@ bool dbll_get_c_addr(struct dbll_library_obj *zl_lib, char *name,

/* Check for C name, if not found */
sym = (struct dbll_symbol *)gh_find(zl_lib->sym_tab, cname);
+ if (IS_ERR(sym))
+ return false;

- if (sym != NULL) {
- *sym_val = &sym->value;
- status = true;
- }
+ *sym_val = &sym->value;

- return status;
+ return true;
}

/*
@@ -416,12 +410,13 @@ int dbll_load(struct dbll_library_obj *lib, dbll_flags flags,
/* Create a hash table for symbols if not already created */
if (zl_lib->sym_tab == NULL) {
got_symbols = false;
- zl_lib->sym_tab = gh_create(MAXBUCKETS,
- sizeof(struct dbll_symbol),
+ zl_lib->sym_tab = gh_create(sizeof(struct dbll_symbol),
name_hash,
name_match, sym_delete);
- if (zl_lib->sym_tab == NULL)
- status = -ENOMEM;
+ if (IS_ERR(zl_lib->sym_tab)) {
+ status = PTR_ERR(zl_lib->sym_tab);
+ zl_lib->sym_tab = NULL;
+ }

}
/*
@@ -593,10 +588,11 @@ int dbll_open(struct dbll_tar_obj *target, char *file, dbll_flags flags,
goto func_cont;

zl_lib->sym_tab =
- gh_create(MAXBUCKETS, sizeof(struct dbll_symbol), name_hash,
- name_match, sym_delete);
- if (zl_lib->sym_tab == NULL) {
- status = -ENOMEM;
+ gh_create(sizeof(struct dbll_symbol), name_hash, name_match,
+ sym_delete);
+ if (IS_ERR(zl_lib->sym_tab)) {
+ status = PTR_ERR(zl_lib->sym_tab);
+ zl_lib->sym_tab = NULL;
} else {
/* Do a fake load to get symbols - set write func to no_op */
zl_lib->init.dl_init.writemem = no_op;
@@ -793,11 +789,10 @@ static int dof_open(struct dbll_library_obj *zl_lib)
/*
* ======== name_hash ========
*/
-static u16 name_hash(void *key, u16 max_bucket)
+static u32 name_hash(const void *key)
{
- u16 ret;
- u16 hash;
- char *name = (char *)key;
+ u32 hash;
+ const char *name = (const char *)key;

hash = 0;

@@ -806,19 +801,17 @@ static u16 name_hash(void *key, u16 max_bucket)
hash ^= *name++;
}

- ret = hash % max_bucket;
-
- return ret;
+ return hash;
}

/*
* ======== name_match ========
*/
-static bool name_match(void *key, void *sp)
+static bool name_match(const void *key, const void *sp)
{
if ((key != NULL) && (sp != NULL)) {
- if (strcmp((char *)key, ((struct dbll_symbol *)sp)->name) ==
- 0)
+ if (strcmp((const char *)key,
+ ((const struct dbll_symbol *)sp)->name) == 0)
return true;
}
return false;
@@ -937,7 +930,6 @@ static struct dynload_symbol *find_in_symbol_table(struct dynamic_loader_sym
*this, const char *name,
unsigned moduleid)
{
- struct dynload_symbol *ret_sym;
struct ldr_symbol *ldr_sym = (struct ldr_symbol *)this;
struct dbll_library_obj *lib;
struct dbll_symbol *sym;
@@ -945,8 +937,10 @@ static struct dynload_symbol *find_in_symbol_table(struct dynamic_loader_sym
lib = ldr_sym->lib;
sym = (struct dbll_symbol *)gh_find(lib->sym_tab, (char *)name);

- ret_sym = (struct dynload_symbol *)&sym->value;
- return ret_sym;
+ if (IS_ERR(sym))
+ return NULL;
+
+ return (struct dynload_symbol *)&sym->value;
}

/*
@@ -991,8 +985,10 @@ static struct dynload_symbol *dbll_add_to_symbol_table(struct dynamic_loader_sym
sym_ptr =
(struct dbll_symbol *)gh_insert(lib->sym_tab, (void *)name,
(void *)&symbol);
- if (sym_ptr == NULL)
+ if (IS_ERR(sym_ptr)) {
kfree(symbol.name);
+ sym_ptr = NULL;
+ }

}
if (sym_ptr != NULL)
--
1.5.6.1

Dan Carpenter

unread,
Jan 5, 2014, 2:50:02 PM1/5/14
to
Looks much nicer. I had a few tiny comments, but those could be
addressed in later patches. (There is a lot of work to be done on this
driver).

On Sun, Jan 05, 2014 at 08:58:12PM +0200, Ivaylo Dimitrov wrote:
> -static u16 name_hash(void *key, u16 max_bucket)
> +static u32 name_hash(const void *key)
> {
> - u16 ret;
> - u16 hash;
> - char *name = (char *)key;
> + u32 hash;
> + const char *name = (const char *)key;
^^^^^^^^^^^^^^

I can't compile this driver, but I'm pretty sure this cast is not
needed.

> -static bool name_match(void *key, void *sp)
> +static bool name_match(const void *key, const void *sp)
> {
> if ((key != NULL) && (sp != NULL)) {
> - if (strcmp((char *)key, ((struct dbll_symbol *)sp)->name) ==
> - 0)
> + if (strcmp((const char *)key,
> + ((const struct dbll_symbol *)sp)->name) == 0)
> return true;

Unneeded casting.

if (strcmp(key, ((struct dbll_symbol *)sp)->name) == 0)
return true;

regards,
dan carpenter

Dan Carpenter

unread,
Jan 5, 2014, 4:20:01 PM1/5/14
to
This is not really an issue with this patch, it's something from the
original code so it doesn't affect merging the patch.

On Sun, Jan 05, 2014 at 08:55:47PM +0200, Ivaylo Dimitrov wrote:
> >Again, reverse the IS_ERR() check and return directly. Use the struct
> >pointer instead of the address of the first member.
> >
> > sym = gh_find(lib->sym_tab, (char *)name);
> > if (IS_ERR(sym))
> > return NULL;
> >
> > return (struct dbll_symbol *)sym;
> >
> >That way is easier to read. gh_find() should accept const pointers btw,
> >we shouldn't have to cast away the const in each of the callers.
> I don't think it is a good idea to return the structdbll_symbol*
> here - the function return type is structdynload_symbol* not
> structdbll_symbol*.

Oops.

> And that will break if we exchange value and name members of
> structdbll_symbol.

It will break anyway if we do that. It's one of those things where you
can't worry too much about what crazy people might try to do later and
then no one reviews the code and no one tests it. If we start doing
that sort of thing we are screwed already so it's not worth worrying
about.

I feel like the types in this driver are not beautiful.

The names are not clear. Take "struct dbll_tar_obj" for example. I'm
not clear what "dbll_" means. I think the "d" stands for dynmic. What
information does the "_obj" add? It would be better to call it
"struct dbll_target".

"dbll_alloc" is a verb instead of a noun so it sounds like a function
not a struct.

But mostly there is too much nonsense casting throughout.
dbll_find_symbol() takes a struct dynamic_loader_sym pointer but we
immediatly cast it to struct ldr_symbol. The struct ldr_symbol is
defined as:

struct ldr_symbol {
struct dynamic_loader_sym dl_symbol;
struct dbll_library_obj *lib;
};

The reason it does this is because it was originally C++ code and it
was ported to C. I think we could move the "lib pointer to the end
of the "dynamic_loader_sym" struct. We could make it a "void *data".
That would remove a source of casting.

There is a lot of this kind of stuff going on:

struct dbll_library_obj *zl_lib = (struct dbll_library_obj *)lib;

"lib" is already a dbll_library_obj struct. And "lib" is a better name,
what does zl_lib mean? I think it's Hungarian notation which we don't
like. Sometimes it uses pzl_ and I think the "p" means pointer. Ugh.
Inside of functions then we don't need to prefix local variables. It's
only for global variables where you run into naming clashes.

Anyway... This driver needs a lot of fixing where data types are
concerned.

Ivaylo Dimitrov

unread,
Jan 5, 2014, 6:20:02 PM1/5/14
to
From: Ivaylo Dimitrov <freema...@abv.bg>

Use upstream hashtable implementation instead of generic code

Signed-off-by: Ivaylo Dimitrov <ivo.g.di...@gmail.com>
---
drivers/staging/tidspbridge/gen/gh.c | 148 ++++++++------------
drivers/staging/tidspbridge/include/dspbridge/gh.h | 12 +-
drivers/staging/tidspbridge/pmgr/dbll.c | 77 +++++------
3 files changed, 98 insertions(+), 139 deletions(-)
index 41e88ab..741979a 100644
--- a/drivers/staging/tidspbridge/pmgr/dbll.c
+++ b/drivers/staging/tidspbridge/pmgr/dbll.c
@@ -33,9 +33,6 @@
#include <dspbridge/dbll.h>
#include <dspbridge/rmm.h>

-/* Number of buckets for symbol hash table */
-#define MAXBUCKETS 211
-
/* Max buffer length */
#define MAXEXPR 128

@@ -183,8 +180,8 @@ static int execute(struct dynamic_loader_initialize *this, ldr_addr start);
static void release(struct dynamic_loader_initialize *this);

/* symbol table hash functions */
-static u16 name_hash(void *key, u16 max_bucket);
-static bool name_match(void *key, void *sp);
-static u16 name_hash(void *key, u16 max_bucket)
+static u32 name_hash(const void *key)
{
- u16 ret;
- u16 hash;
- char *name = (char *)key;
+ u32 hash;
+ const char *name = key;

hash = 0;

@@ -806,19 +801,16 @@ static u16 name_hash(void *key, u16 max_bucket)
hash ^= *name++;
}

- ret = hash % max_bucket;
-
- return ret;
+ return hash;
}

/*
* ======== name_match ========
*/
-static bool name_match(void *key, void *sp)
+static bool name_match(const void *key, const void *sp)
{
if ((key != NULL) && (sp != NULL)) {
- if (strcmp((char *)key, ((struct dbll_symbol *)sp)->name) ==
- 0)
+ if (strcmp(key, ((struct dbll_symbol *)sp)->name) == 0)
return true;
}
return false;
@@ -937,7 +929,6 @@ static struct dynload_symbol *find_in_symbol_table(struct dynamic_loader_sym
*this, const char *name,
unsigned moduleid)
{
- struct dynload_symbol *ret_sym;
struct ldr_symbol *ldr_sym = (struct ldr_symbol *)this;
struct dbll_library_obj *lib;
struct dbll_symbol *sym;
@@ -945,8 +936,10 @@ static struct dynload_symbol *find_in_symbol_table(struct dynamic_loader_sym
lib = ldr_sym->lib;
sym = (struct dbll_symbol *)gh_find(lib->sym_tab, (char *)name);

- ret_sym = (struct dynload_symbol *)&sym->value;
- return ret_sym;
+ if (IS_ERR(sym))
+ return NULL;
+
+ return (struct dynload_symbol *)&sym->value;
}

/*
@@ -991,8 +984,10 @@ static struct dynload_symbol *dbll_add_to_symbol_table(struct dynamic_loader_sym
sym_ptr =
(struct dbll_symbol *)gh_insert(lib->sym_tab, (void *)name,
(void *)&symbol);
- if (sym_ptr == NULL)
+ if (IS_ERR(sym_ptr)) {
kfree(symbol.name);
+ sym_ptr = NULL;
+ }

}
if (sym_ptr != NULL)
--
1.5.6.1

Ivaylo Dimitrov

unread,
Jan 5, 2014, 6:20:02 PM1/5/14
to
Yeah, both are not needed (I am thinking C++ most of the time and have
forgotten that C is much relaxed than C++ :) ). However, I will send a
new version which fixes that, IMO it is better to fix it while I am on it.

Thanks,
Ivo
0 new messages