]> git.baikalelectronics.ru Git - kernel.git/commit
rhashtable: Add nested tables
authorHerbert Xu <herbert@gondor.apana.org.au>
Sat, 11 Feb 2017 11:26:47 +0000 (19:26 +0800)
committerDavid S. Miller <davem@davemloft.net>
Fri, 17 Feb 2017 17:28:35 +0000 (12:28 -0500)
commitffe942e0f32bca6d953ab2f173cc3c7fb0f0064f
tree0a6a08124301510af4c6f6926efc9ae7afd8c03f
parente77ddc48def1d0f7a1c0014450e47d40f9f560d2
rhashtable: Add nested tables

This patch adds code that handles GFP_ATOMIC kmalloc failure on
insertion.  As we cannot use vmalloc, we solve it by making our
hash table nested.  That is, we allocate single pages at each level
and reach our desired table size by nesting them.

When a nested table is created, only a single page is allocated
at the top-level.  Lower levels are allocated on demand during
insertion.  Therefore for each insertion to succeed, only two
(non-consecutive) pages are needed.

After a nested table is created, a rehash will be scheduled in
order to switch to a vmalloced table as soon as possible.  Also,
the rehash code will never rehash into a nested table.  If we
detect a nested table during a rehash, the rehash will be aborted
and a new rehash will be scheduled.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
Signed-off-by: David S. Miller <davem@davemloft.net>
include/linux/rhashtable.h
lib/rhashtable.c