User: Password:
Subscribe / Log in / New account

generic hashtable implementation

From:  Sasha Levin <>
Subject:  [RFC v3 0/7] generic hashtable implementation
Date:  Tue, 7 Aug 2012 02:45:09 +0200
Message-ID:  <>
Cc:,,,,,,,,,,,,,,, Sasha Levin <>
Archive-link:  Article

There are quite a few places in the kernel which implement a hashtable
in a very similar way. Instead of having implementations of a hashtable
all over the kernel, we can re-use the code.

This patch series introduces a very simple hashtable implementation, and
modifies three (random) modules to use it. I've limited it to 3 only
so that it would be easy to review and modify, and to show that even
at this number we already eliminate a big amount of duplicated code.

If this basic hashtable looks ok, future code will include:

 - RCU support
 - Self locking (list_bl?)
 - Converting more code to use the hashtable

Changes in V3:

 - Address review comments by Tejun Heo, Josh Triplett, Eric Beiderman,
   Mathieu Desnoyers, Eric Dumazet and Linus Torvalds.
 - Removed hash_get due to being too Gandalf.
 - Rewrote the user namespaces hash implementation.
 - Hashtable went back to being a simple array of buckets, but without any
   of the macro tricks to get the size automatically.
 - Optimize hasing if key is 32 bits long.

Changes in V2:

 - Address review comments by Tejun Heo, Josh Triplett and Eric Beiderman (Thanks all!).
 - Rebase on top of latest master.
 - Convert more places to use the hashtable. Hopefully it will trigger more reviews by
 touching more subsystems.

Sasha Levin (7):
  hashtable: introduce a small and naive hashtable
  user_ns: use new hashtable implementation
  mm,ksm: use new hashtable implementation
  workqueue: use new hashtable implementation
  mm/huge_memory: use new hashtable implementation
  tracepoint: use new hashtable implementation
  net,9p: use new hashtable implementation

 include/linux/hashtable.h |   82 +++++++++++++++++++++++++++++++++++++++++
 kernel/tracepoint.c       |   26 +++++--------
 kernel/user.c             |   35 ++++++++----------
 kernel/workqueue.c        |   89 +++++++++------------------------------------
 mm/huge_memory.c          |   56 +++++++---------------------
 mm/ksm.c                  |   31 +++++++---------
 net/9p/error.c            |   21 +++++------
 7 files changed, 162 insertions(+), 178 deletions(-)
 create mode 100644 include/linux/hashtable.h


To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to  For more info on Linux MM,
see: .
Don't email: <a href=mailto:""> </a>

Copyright © 2012, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds