Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

Sasha Levin
2012-08-24T19:46:57Z

On 08/23/2012 10:04 PM, Tejun Heo wrote:
> Hello, Sasha.
>
> On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote:
>>> I think the almost trivial nature of hlist hashtables makes this a bit
>>> tricky and I'm not very sure but having this combinatory explosion is
>>> a bit dazzling when the same functionality can be achieved by simply
>>> combining operations which are already defined and named considering
>>> hashtable. I'm not feeling too strong about this tho. What do others
>>> think?
>>
>> I'm thinking that this hashtable API will have 2 purposes: First, it would
>> prevent the excessive duplication of hashtable implementations all around the code.
>>
>> Second, it will allow more easily interchangeable hashtable implementations to
>> find their way into the kernel. There are several maintainers who would be happy
>> to see dynamically sized RCU hashtable, and I'm guessing that several more
>> variants could be added based on needs in specific modules.
>>
>> The second reason is why several things you've mentioned look the way they are:
>>
>> - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since
>> initialization for other hashtables may be more complicated than the static
>> initialization for this implementation, which means that any place that used
>> DEFINE_HASHTABLE() and didn't do hash_init() will be buggy.
>
> I think this is problematic. It looks exactly like other existing
> DEFINE macros yet what its semantics is different. I don't think
> that's a good idea.

I can switch that to be DECLARE_HASHTABLE() if the issue is semantics.

>> I'm actually tempted in hiding hlist completely from hashtable users, probably
>> by simply defining a hash_head/hash_node on top of the hlist_ counterparts.
>
> I think that it would be best to keep this one simple & obvious, which
> already has enough in-kernel users to justify its existence. There
> are significant benefits in being trivially understandable and
> expectable. If we want more advanced ones - say resizing, hybrid or
> what not, let's make that a separate one. No need to complicate the
> common straight-forward case for that.
>
> So, I think it would be best to keep this one as straight-forward and
> trivial as possible. Helper macros to help its users are fine but
> let's please not go for full encapsulation.

What if we cut off the dynamic allocated (but not resizable) hashtable out for
the moment, and focus on the most common statically allocated hashtable case?

The benefits would be:

- Getting rid of all the _size() macros, which will make the amount of helpers
here reasonable.
- Dynamically allocated hashtable can be easily added as a separate
implementation using the same API. We already have some of those in the kernel...
- When that's ready, I feel it's a shame to lose full encapsulation just due to
hash_hashed().

Thanks,
Sasha

>
> Thanks.
>