kernel hashtable.h dynamic size of hash table

Question

I have written the module which uses < linux/hashtable.h > at the moment, it works perfectly fine, however I would like to change it from static hash table size to configurable one.

How should I change initialization from this:

DEFINE_HASHTABLE(my_hash_table, 10);

to dynamic one so I can pass the size of hash table when module is loaded as parameter

I have tried with struct hlist_head* my_hash_table and its corresponding kmallocs() but with no success and give me these errors:

include/linux/bug.h:33:45: error: negative width in bit-field ‘<anonymous>’
 #define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:-!!(e); }))
                                             ^

include/linux/hashtable.h:27:35: note: in definition of macro ‘hash_min’
  (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
                                   ^

include/linux/hashtable.h:23:25: note: in expansion of macro ‘ilog2’
 #define HASH_BITS(name) ilog2(HASH_SIZE(name))
                         ^

include/linux/compiler-gcc.h:44:28: note: in expansion of macro ‘BUILD_BUG_ON_ZERO’
 #define __must_be_array(a) BUILD_BUG_ON_ZERO(__same_type((a), &(a)[0]))
                            ^

include/linux/kernel.h:54:59: note: in expansion of macro ‘__must_be_array’
 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))
                                                           ^

include/linux/hashtable.h:22:26: note: in expansion of macro ‘ARRAY_SIZE’
 #define HASH_SIZE(name) (ARRAY_SIZE(name))
                          ^

include/linux/hashtable.h:23:31: note: in expansion of macro ‘HASH_SIZE’
 #define HASH_BITS(name) ilog2(HASH_SIZE(name))
                               ^

include/linux/hashtable.h:56:48: note: in expansion of macro ‘HASH_BITS’
  hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
                                                ^

HashTable.c:103:9: note: in expansion of macro ‘hash_add’
         hash_add(my_hash_table, &entry->entry, entry->hashed_key);

Why are you using `kmalloc()` ? If unsure read http://stackoverflow.com/questions/116343/what-is-the-difference-between-vmalloc-and-kmalloc — gollum, Feb 22 '16 at 17:20
yes, I am aware about vmalloc as well, however it is not a problem at the moment — Marek Waszkiewicz, Feb 22 '16 at 17:24
Did you look at http://lxr.free-electrons.com/source/include/linux/hashtable.h and http://lxr.free-electrons.com/source/include/linux/list.h and study the internals? What is your effort so far, where did you fail? — gollum, Feb 22 '16 at 17:50
Re-sizing a hash table is usually a bad idea. After you adjust the size, you'd have to recalculate all existing hash entries, It is not very efficient if you have a large table with many entries. Better idea would be to size the table smartly from the start. — Bing Bang, Feb 22 '16 at 17:53
@BingBang I think the OP does not want to dynamically resize the hash table but only initialize it dynamically with a specific size. — gollum, Feb 22 '16 at 18:08
@gollum, BigBang - yes I want to add hash table size as module's input parameter — Marek Waszkiewicz, Feb 22 '16 at 19:57

score 2 · Answer 1 · answered Feb 22 '16 at 20:04

2

The kernel already has support for "dynamic" hashtables. And it's called - relativistic hash tables. More information and explanation how it works/how to use it can be found in the following very good LWN articles: Part 1 and Part 2

answered Feb 22 '16 at 20:04

LordDoskias

3,121
3
30
44

I do not want to resize while module is loaded, I want to load the module with hash table size parameter, instead of compile time – Marek Waszkiewicz Feb 22 '16 at 20:06
In that case you need to understand that a hashtable is nothing more than an array of hlist_head, so what you should do is accept the hashtable size as an argument (preferably a power of 2). And then use kmalloc/kzalloc to allocate an array of the appropriate size. That is - forget about DEFINE_HASHTABLE. Instead you will have something like struct hlist_head *hash_table = kzalloc(sizeof(struct hlist_head) * NUM_OF_ELEMENTS, GFP_KERNEL); – LordDoskias Feb 22 '16 at 20:07
yes, thats what I did, see my output with errors from hashtable.h macros – Marek Waszkiewicz Feb 22 '16 at 20:09
Paste more of your code and not just the initialization otherwise we can't infer what you are trying to do and why it is giving these errors. – LordDoskias Feb 22 '16 at 20:11
Don't use kzalloc. Of course it would (currently) work but the internal fields should be handled as a black box. Better use the `INIT_HLIST_HEAD` macro. – gollum Feb 22 '16 at 20:22
kzalloc + __hash_init ought to do the job. However, there is crucial code missing from the question to give a full answer. I'm almost certain that the OP is using hash_init on the dynamically allocated hash table and that's where the errors are coming from. – LordDoskias Feb 22 '16 at 20:24

score 0 · Answer 2 · answered Feb 22 '16 at 19:34

0

In order to change ...

DEFINE_HASHTABLE(my_hash_table, 10);

... to a dynamically allocated equivalent you would use something like this:

#define MY_HT_SZ 1024

struct hlist_head *my_hash_table;
int i;

my_hash_table = kmalloc(MY_HT_SZ * sizeof(struct hlist_head), GFP_KERNEL);

if (!my_hash_table)
    goto error_handler;

for (i = 0; i < MY_HT_SZ; i++)
    INIT_HLIST_HEAD(&my_hash_table[i]);

answered Feb 22 '16 at 19:34

gollum

2,472
1
18
21

I was trying it already, it is not working because of hashtable.h macros, see output – Marek Waszkiewicz Feb 22 '16 at 19:54
yes, as I said earlier already tried it, gives macro errors while hash_add, updated the question accordingly – Marek Waszkiewicz Feb 22 '16 at 20:02
These macros protect you from accessing elements outside of the array. You cannot use these macros because the size is not known if you allocate it dynamically. Do yourself a favor and research how `hlist_add_head` is used: http://lxr.free-electrons.com/ident?v=4.4;i=hlist_add_head – gollum Feb 22 '16 at 20:29
so you saying this macros which really are API for hash table are valid only for an array ? and not on dynamically allocated pointer to array ? – Marek Waszkiewicz Feb 22 '16 at 20:37
These are convenience macros for predefined hash tables. I've a certain feeling that you're missing some basics regarding hash tables. Maybe you should give some more info what you want to achieve. What is your data? Which hash function are you using? – gollum Feb 22 '16 at 20:45
It is not enough. There is a lot of MACRO uses HASH_BITS(hastable) MACRO. – legale Nov 21 '22 at 09:48

legale · Answer 3 · 2022-11-21T09:49:43.233

Same problem. I have solved this like that:

hashtable declaration.

    /* 
    * example: struct hlist_head tbl[1 << (bits)]; 
    * DECLARE_HASHTABLE(tbl, bits); 
    */
    //struct hlist_head tbl[1 << bits];

    struct hlist_head *tbl = malloc((1 << bits) * sizeof(struct hlist_head) );

Initialization.

    // Initialize the hashtable.
    //hash_init(tbl);

    __hash_init(tbl, 1 << bits);

Than i'have added all MACRO that uses HASH_BITS(hastable) HASH_SIZE(hashtable) with the same _bits version MACRO.

/**
 * hash_add - add an object to a hashtable
 * @hashtable: hashtable to add to
 * @node: the &struct hlist_node of the object to be added
 * @key: the key of the object to be added
 */
#define hash_add(hashtable, node, key)                      \
    hlist_add_head(node, &hashtable[hash_32(key, HASH_BITS(hashtable))])

#define hash_add_bits(hashtable, bits, node, key)                       \
    hlist_add_head(node, &hashtable[hash_32(key, bits)])

Same for others:

/**
 * hash_for_each - iterate over a hashtable
 * @name: hashtable to iterate
 * @bkt: integer to use as bucket loop cursor
 * @obj: the type * to use as a loop cursor for each entry
 * @member: the name of the hlist_node within the struct
 */
#define hash_for_each(name, bkt, obj, member)               \
    for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
            (bkt)++)\
        hlist_for_each_entry(obj, &name[bkt], member)

#define hash_for_each_bits(name, bits, bkt, obj, member)                \
    for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < (1 << bits);\
            (bkt)++)\
        hlist_for_each_entry(obj, &name[bkt], member)

You can take a look here: https://github.com/legale/hashtable-linux-kernel

kernel hashtable.h dynamic size of hash table

3 Answers3