uthash in kernel

[e.emanuel...@gmail.com]

Hi, I am using uthash as hash table for my linux kernel module. I chose it because it does not have floating point (that natively are not supported by kernel). However, I have strange behavior when I unload the module (CPU stuck for 22s bug).
This is where I use the hashmap:

#include <linux/slab.h>
#include "uthash.h"

struct hash_item {
iid_t iid;
accepted *value;
UT_hash_handle hh;
};

struct mem_storage //db
{
iid_t trim_iid;
struct hash_item * record;
};

static struct mem_storage*
mem_storage_new(int acceptor_id)
{
struct mem_storage* s = kmalloc(sizeof(struct mem_storage), GFP_KERNEL);
[...]
s->record = NULL;
return s;
}

static int
mem_storage_get(void* handle, iid_t iid, accepted* out)
{
struct mem_storage* s = handle;
struct hash_item * h = NULL;
HASH_FIND_INT( s->record, &iid, h); // kernel panic say the error is here
if(h == NULL)
return 0;
[..]
return 1;
}

static int
mem_storage_put(void* handle, accepted* acc)
{
struct mem_storage* s = handle;
struct hash_item * a = NULL;

HASH_FIND_INT(s->record, &(acc->iid), a); // Panic also here if I comment the line in mem_storage_get
if (a==NULL) {
a = kmalloc(sizeof(struct hash_item), GFP_KERNEL);
}
[ fill a with values]
HASH_ADD_INT(s->record, iid, a);

return 0;
}
When I add the -DHASH_DEBUG=1 to the ccflags-y, I get this error:
HASH_ADD_KEYPTR_BYHASHVALUE: invalid hh_prev (null), actual ffff895c06e78670

Basically, it's like the module is stuck in an infinite loop.
Can you help me?

Thanks a lot.

[Arthur O'Dwyer]

On Wed, Aug 16, 2017 at 6:37 AM, <e.emanuel...@gmail.com> wrote:

Hi, I am using uthash as hash table for my linux kernel module. I chose it because it does not have floating point (that natively are not supported by kernel). However, I have strange behavior when I unload the module (CPU stuck for 22s bug).
This is where I use the hashmap:

[...] 

static int
mem_storage_put(void* handle, accepted* acc)
{
    struct mem_storage* s = handle;
    struct hash_item * a = NULL;

    HASH_FIND_INT(s->record, &(acc->iid), a);  // Panic also here if I comment the line in mem_storage_get
    if (a==NULL) {
        a = kmalloc(sizeof(struct hash_item), GFP_KERNEL);
    }
    [ fill a with values]
    HASH_ADD_INT(s->record, iid, a);

I believe this is the problem here.

If a==NULL above, then you kmalloc a new node and add it to the table with HASH_ADD_INT; this is fine.

If a!=NULL, though, then (unless you snipped a "return") you are trying to HASH_ADD_INT a node which already exists in the table. You can't add the same node twice! You might want to use HASH_REPLACE, or you might want to edit the fields of "a" directly in place in the case it already exists.

Also, if "sizeof(iid_t)" is not exactly "sizeof(int)", you'll have a bug. I weakly recommend using HASH_ADD() explicitly instead of the HASH_ADD_INT() convenience macro, just for clarity's sake.

HTH,

Arthur

[Ema Esp]

You're completely right!

I figured that the a!=NULL handling was not correct, but I could not imagine that also iid_t would create bugs.

Since I could not change the iid_t type (which is uint32_t), I created 2 new macros:

#define HASH_FIND_IID(head,findint,out)                                          \

   HASH_FIND(hh,head,findint,sizeof(iid_t),out)

#define HASH_ADD_IID(head,intfield,add)                                          \

   HASH_ADD(hh,head,intfield,sizeof(iid_t),add)

and substituted all the _INT with _IID.

I was wondering why you (and also the guide) say that it is not recommended to use HASH_ADD. Just as curiosity, can you explain it?

And tanks a lot!

Emanuele

[Ema Esp]

Ok, I realized sizeof(iid_t) == sizeof(int), so the fix was the wrong handling of a != NULL.

I am sorry, but since I am here, I wanted to ask you another question: now I have another problem, in another hashmap:

I insert a value and right after I want to find it,just to debug. However, it seems not to find it.

#include "uthash.h"

struct instance

{

iid_t iid;

[...]

UT_hash_handle hh;

};

struct learner

{

[...]

struct instance * instances;

};

struct learner*

learner_new(int acceptors)

{

struct learner * l = kmalloc(sizeof(struct learner), GFP_KERNEL);

[...]

l->instances = NULL;

return l;

}

static struct instance*

learner_get_instance(struct learner* l, iid_t iids)

{

struct instance * h = NULL;

        HASH_FIND_IID( l->instances, &iids, h); 

return h;

}

static struct instance*

learner_get_instance_or_create(struct learner* l, iid_t iids)

{

struct instance* inst = learner_get_instance(l, iids);

if (inst == NULL) {

printk(KERN_WARNING "Instance is null, creating new one");

inst = instance_new(l->acceptors);  // Creates and allocates a new instance with iid = 0

HASH_ADD_IID(l->instances, iid, inst);  // does not work! why?

struct instance * h = NULL;

HASH_FIND_IID( l->instances, &iids, h);

if(h == NULL){

printk(KERN_ERR "Instance is null, YOU HAVE A PROBLEM");  // it always goes here

}

}else{

printk(KERN_WARNING "Instance is NOT null");

}

return inst;

}

If I call 3 times the learner_get_instance_or_create() with the same learner and same iid, it prints 3 times:

Instance is null, creating new one

Instance is null, YOU HAVE A PROBLEM

Instance is null, creating new one

Instance is null, YOU HAVE A PROBLEM

Instance is null, creating new one

Instance is null, YOU HAVE A PROBLEM

Thanks a lot again,

Emanuele

[Arthur O'Dwyer]

After this line, I would insert:

printf("%p %d\n", inst, inst->iid);

HASH_ADD_IID(l->instances, iid, inst);  // does not work! why?

And here:

printf("%d", (int)HASH_COUNT(l->instances));

 

struct instance * h = NULL;

HASH_FIND_IID( l->instances, &iids, h);

And here:

printf("%p %d\n", h, iids);

Remember, when you're debugging, your goal is to discover what is happening, so that you can discover when it goes wrong, so that you can discover why it goes wrong. Step 1 is always to find out what is happening. In this case I have a guess, of course, but you need to learn how to debug your code on your own.

–Arthur

[Ema Esp]

Found the problem, thanks again.

Basically if the instance was not found, I was creating and adding a new instance of iid = 0, and then in the HASH_FIND_IID I was looking for instance with iid = 1.

The next time the function was called, with same iid = 1 and head, it was not finding it and creating a new instance of iid = 0.

I fixed it calling inst->iid = iids; before HASH_ADD_IID.

You're right about debugging, and thanks for giving me just tips and not the complete solution!

Emanuele