summaryrefslogtreecommitdiffstats
path: root/lib/rhashtable.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2014-12-11 14:27:06 -0800
committerLinus Torvalds <torvalds@linux-foundation.org>2014-12-11 14:27:06 -0800
commit70e71ca0af244f48a5dcf56dc435243792e3a495 (patch)
treef7d9c4c4d9a857a00043e9bf6aa2d6f533a34778 /lib/rhashtable.c
parentbae41e45b7400496b9bf0c70c6004419d9987819 (diff)
parent00c83b01d58068dfeb2e1351cca6fccf2a83fa8f (diff)
downloadop-kernel-dev-70e71ca0af244f48a5dcf56dc435243792e3a495.zip
op-kernel-dev-70e71ca0af244f48a5dcf56dc435243792e3a495.tar.gz
Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next
Pull networking updates from David Miller: 1) New offloading infrastructure and example 'rocker' driver for offloading of switching and routing to hardware. This work was done by a large group of dedicated individuals, not limited to: Scott Feldman, Jiri Pirko, Thomas Graf, John Fastabend, Jamal Hadi Salim, Andy Gospodarek, Florian Fainelli, Roopa Prabhu 2) Start making the networking operate on IOV iterators instead of modifying iov objects in-situ during transfers. Thanks to Al Viro and Herbert Xu. 3) A set of new netlink interfaces for the TIPC stack, from Richard Alpe. 4) Remove unnecessary looping during ipv6 routing lookups, from Martin KaFai Lau. 5) Add PAUSE frame generation support to gianfar driver, from Matei Pavaluca. 6) Allow for larger reordering levels in TCP, which are easily achievable in the real world right now, from Eric Dumazet. 7) Add a variable of napi_schedule that doesn't need to disable cpu interrupts, from Eric Dumazet. 8) Use a doubly linked list to optimize neigh_parms_release(), from Nicolas Dichtel. 9) Various enhancements to the kernel BPF verifier, and allow eBPF programs to actually be attached to sockets. From Alexei Starovoitov. 10) Support TSO/LSO in sunvnet driver, from David L Stevens. 11) Allow controlling ECN usage via routing metrics, from Florian Westphal. 12) Remote checksum offload, from Tom Herbert. 13) Add split-header receive, BQL, and xmit_more support to amd-xgbe driver, from Thomas Lendacky. 14) Add MPLS support to openvswitch, from Simon Horman. 15) Support wildcard tunnel endpoints in ipv6 tunnels, from Steffen Klassert. 16) Do gro flushes on a per-device basis using a timer, from Eric Dumazet. This tries to resolve the conflicting goals between the desired handling of bulk vs. RPC-like traffic. 17) Allow userspace to ask for the CPU upon what a packet was received/steered, via SO_INCOMING_CPU. From Eric Dumazet. 18) Limit GSO packets to half the current congestion window, from Eric Dumazet. 19) Add a generic helper so that all drivers set their RSS keys in a consistent way, from Eric Dumazet. 20) Add xmit_more support to enic driver, from Govindarajulu Varadarajan. 21) Add VLAN packet scheduler action, from Jiri Pirko. 22) Support configurable RSS hash functions via ethtool, from Eyal Perry. * git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next: (1820 commits) Fix race condition between vxlan_sock_add and vxlan_sock_release net/macb: fix compilation warning for print_hex_dump() called with skb->mac_header net/mlx4: Add support for A0 steering net/mlx4: Refactor QUERY_PORT net/mlx4_core: Add explicit error message when rule doesn't meet configuration net/mlx4: Add A0 hybrid steering net/mlx4: Add mlx4_bitmap zone allocator net/mlx4: Add a check if there are too many reserved QPs net/mlx4: Change QP allocation scheme net/mlx4_core: Use tasklet for user-space CQ completion events net/mlx4_core: Mask out host side virtualization features for guests net/mlx4_en: Set csum level for encapsulated packets be2net: Export tunnel offloads only when a VxLAN tunnel is created gianfar: Fix dma check map error when DMA_API_DEBUG is enabled cxgb4/csiostor: Don't use MASTER_MUST for fw_hello call net: fec: only enable mdio interrupt before phy device link up net: fec: clear all interrupt events to support i.MX6SX net: fec: reset fep link status in suspend function net: sock: fix access via invalid file descriptor net: introduce helper macro for_each_cmsghdr ...
Diffstat (limited to 'lib/rhashtable.c')
-rw-r--r--lib/rhashtable.c88
1 files changed, 51 insertions, 37 deletions
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 624a0b7..6c3c723 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -20,7 +20,7 @@
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <linux/mm.h>
-#include <linux/hash.h>
+#include <linux/jhash.h>
#include <linux/random.h>
#include <linux/rhashtable.h>
@@ -32,7 +32,7 @@
#ifdef CONFIG_PROVE_LOCKING
int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
{
- return ht->p.mutex_is_held();
+ return ht->p.mutex_is_held(ht->p.parent);
}
EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
#endif
@@ -107,13 +107,13 @@ static u32 head_hashfn(const struct rhashtable *ht,
return obj_hashfn(ht, rht_obj(ht, he), hsize);
}
-static struct bucket_table *bucket_table_alloc(size_t nbuckets, gfp_t flags)
+static struct bucket_table *bucket_table_alloc(size_t nbuckets)
{
struct bucket_table *tbl;
size_t size;
size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);
- tbl = kzalloc(size, flags);
+ tbl = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
if (tbl == NULL)
tbl = vzalloc(size);
@@ -200,7 +200,6 @@ static void hashtable_chain_unzip(const struct rhashtable *ht,
/**
* rhashtable_expand - Expand hash table while allowing concurrent lookups
* @ht: the hash table to expand
- * @flags: allocation flags
*
* A secondary bucket array is allocated and the hash entries are migrated
* while keeping them on both lists until the end of the RCU grace period.
@@ -211,7 +210,7 @@ static void hashtable_chain_unzip(const struct rhashtable *ht,
* The caller must ensure that no concurrent table mutations take place.
* It is however valid to have concurrent lookups if they are RCU protected.
*/
-int rhashtable_expand(struct rhashtable *ht, gfp_t flags)
+int rhashtable_expand(struct rhashtable *ht)
{
struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
struct rhash_head *he;
@@ -223,7 +222,7 @@ int rhashtable_expand(struct rhashtable *ht, gfp_t flags)
if (ht->p.max_shift && ht->shift >= ht->p.max_shift)
return 0;
- new_tbl = bucket_table_alloc(old_tbl->size * 2, flags);
+ new_tbl = bucket_table_alloc(old_tbl->size * 2);
if (new_tbl == NULL)
return -ENOMEM;
@@ -281,7 +280,6 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
/**
* rhashtable_shrink - Shrink hash table while allowing concurrent lookups
* @ht: the hash table to shrink
- * @flags: allocation flags
*
* This function may only be called in a context where it is safe to call
* synchronize_rcu(), e.g. not within a rcu_read_lock() section.
@@ -289,7 +287,7 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
* The caller must ensure that no concurrent table mutations take place.
* It is however valid to have concurrent lookups if they are RCU protected.
*/
-int rhashtable_shrink(struct rhashtable *ht, gfp_t flags)
+int rhashtable_shrink(struct rhashtable *ht)
{
struct bucket_table *ntbl, *tbl = rht_dereference(ht->tbl, ht);
struct rhash_head __rcu **pprev;
@@ -300,7 +298,7 @@ int rhashtable_shrink(struct rhashtable *ht, gfp_t flags)
if (ht->shift <= ht->p.min_shift)
return 0;
- ntbl = bucket_table_alloc(tbl->size / 2, flags);
+ ntbl = bucket_table_alloc(tbl->size / 2);
if (ntbl == NULL)
return -ENOMEM;
@@ -341,7 +339,6 @@ EXPORT_SYMBOL_GPL(rhashtable_shrink);
* rhashtable_insert - insert object into hash hash table
* @ht: hash table
* @obj: pointer to hash head inside object
- * @flags: allocation flags (table expansion)
*
* Will automatically grow the table via rhashtable_expand() if the the
* grow_decision function specified at rhashtable_init() returns true.
@@ -349,8 +346,7 @@ EXPORT_SYMBOL_GPL(rhashtable_shrink);
* The caller must ensure that no concurrent table mutations occur. It is
* however valid to have concurrent lookups if they are RCU protected.
*/
-void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
- gfp_t flags)
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
{
struct bucket_table *tbl = rht_dereference(ht->tbl, ht);
u32 hash;
@@ -363,7 +359,7 @@ void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
ht->nelems++;
if (ht->p.grow_decision && ht->p.grow_decision(ht, tbl->size))
- rhashtable_expand(ht, flags);
+ rhashtable_expand(ht);
}
EXPORT_SYMBOL_GPL(rhashtable_insert);
@@ -372,14 +368,13 @@ EXPORT_SYMBOL_GPL(rhashtable_insert);
* @ht: hash table
* @obj: pointer to hash head inside object
* @pprev: pointer to previous element
- * @flags: allocation flags (table expansion)
*
* Identical to rhashtable_remove() but caller is alreayd aware of the element
* in front of the element to be deleted. This is in particular useful for
* deletion when combined with walking or lookup.
*/
void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
- struct rhash_head __rcu **pprev, gfp_t flags)
+ struct rhash_head __rcu **pprev)
{
struct bucket_table *tbl = rht_dereference(ht->tbl, ht);
@@ -390,7 +385,7 @@ void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
if (ht->p.shrink_decision &&
ht->p.shrink_decision(ht, tbl->size))
- rhashtable_shrink(ht, flags);
+ rhashtable_shrink(ht);
}
EXPORT_SYMBOL_GPL(rhashtable_remove_pprev);
@@ -398,7 +393,6 @@ EXPORT_SYMBOL_GPL(rhashtable_remove_pprev);
* rhashtable_remove - remove object from hash table
* @ht: hash table
* @obj: pointer to hash head inside object
- * @flags: allocation flags (table expansion)
*
* Since the hash chain is single linked, the removal operation needs to
* walk the bucket chain upon removal. The removal operation is thus
@@ -410,8 +404,7 @@ EXPORT_SYMBOL_GPL(rhashtable_remove_pprev);
* The caller must ensure that no concurrent table mutations occur. It is
* however valid to have concurrent lookups if they are RCU protected.
*/
-bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj,
- gfp_t flags)
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
{
struct bucket_table *tbl = rht_dereference(ht->tbl, ht);
struct rhash_head __rcu **pprev;
@@ -429,7 +422,7 @@ bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj,
continue;
}
- rhashtable_remove_pprev(ht, he, pprev, flags);
+ rhashtable_remove_pprev(ht, he, pprev);
return true;
}
@@ -531,8 +524,10 @@ static size_t rounded_hashtable_size(struct rhashtable_params *params)
* .head_offset = offsetof(struct test_obj, node),
* .key_offset = offsetof(struct test_obj, key),
* .key_len = sizeof(int),
- * .hashfn = arch_fast_hash,
+ * .hashfn = jhash,
+ * #ifdef CONFIG_PROVE_LOCKING
* .mutex_is_held = &my_mutex_is_held,
+ * #endif
* };
*
* Configuration Example 2: Variable length keys
@@ -550,9 +545,11 @@ static size_t rounded_hashtable_size(struct rhashtable_params *params)
*
* struct rhashtable_params params = {
* .head_offset = offsetof(struct test_obj, node),
- * .hashfn = arch_fast_hash,
+ * .hashfn = jhash,
* .obj_hashfn = my_hash_fn,
+ * #ifdef CONFIG_PROVE_LOCKING
* .mutex_is_held = &my_mutex_is_held,
+ * #endif
* };
*/
int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
@@ -572,7 +569,7 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
if (params->nelem_hint)
size = rounded_hashtable_size(params);
- tbl = bucket_table_alloc(size, GFP_KERNEL);
+ tbl = bucket_table_alloc(size);
if (tbl == NULL)
return -ENOMEM;
@@ -613,10 +610,12 @@ EXPORT_SYMBOL_GPL(rhashtable_destroy);
#define TEST_PTR ((void *) 0xdeadbeef)
#define TEST_NEXPANDS 4
-static int test_mutex_is_held(void)
+#ifdef CONFIG_PROVE_LOCKING
+static int test_mutex_is_held(void *parent)
{
return 1;
}
+#endif
struct test_obj {
void *ptr;
@@ -654,15 +653,15 @@ static int __init test_rht_lookup(struct rhashtable *ht)
return 0;
}
-static void test_bucket_stats(struct rhashtable *ht,
- struct bucket_table *tbl,
- bool quiet)
+static void test_bucket_stats(struct rhashtable *ht, bool quiet)
{
- unsigned int cnt, i, total = 0;
+ unsigned int cnt, rcu_cnt, i, total = 0;
struct test_obj *obj;
+ struct bucket_table *tbl;
+ tbl = rht_dereference_rcu(ht->tbl, ht);
for (i = 0; i < tbl->size; i++) {
- cnt = 0;
+ rcu_cnt = cnt = 0;
if (!quiet)
pr_info(" [%#4x/%zu]", i, tbl->size);
@@ -674,6 +673,13 @@ static void test_bucket_stats(struct rhashtable *ht,
pr_cont(" [%p],", obj);
}
+ rht_for_each_entry_rcu(obj, tbl->buckets[i], node)
+ rcu_cnt++;
+
+ if (rcu_cnt != cnt)
+ pr_warn("Test failed: Chain count mismach %d != %d",
+ cnt, rcu_cnt);
+
if (!quiet)
pr_cont("\n [%#x] first element: %p, chain length: %u\n",
i, tbl->buckets[i], cnt);
@@ -681,6 +687,9 @@ static void test_bucket_stats(struct rhashtable *ht,
pr_info(" Traversal complete: counted=%u, nelems=%zu, entries=%d\n",
total, ht->nelems, TEST_ENTRIES);
+
+ if (total != ht->nelems || total != TEST_ENTRIES)
+ pr_warn("Test failed: Total count mismatch ^^^");
}
static int __init test_rhashtable(struct rhashtable *ht)
@@ -707,18 +716,17 @@ static int __init test_rhashtable(struct rhashtable *ht)
obj->ptr = TEST_PTR;
obj->value = i * 2;
- rhashtable_insert(ht, &obj->node, GFP_KERNEL);
+ rhashtable_insert(ht, &obj->node);
}
rcu_read_lock();
- tbl = rht_dereference_rcu(ht->tbl, ht);
- test_bucket_stats(ht, tbl, true);
+ test_bucket_stats(ht, true);
test_rht_lookup(ht);
rcu_read_unlock();
for (i = 0; i < TEST_NEXPANDS; i++) {
pr_info(" Table expansion iteration %u...\n", i);
- rhashtable_expand(ht, GFP_KERNEL);
+ rhashtable_expand(ht);
rcu_read_lock();
pr_info(" Verifying lookups...\n");
@@ -728,7 +736,7 @@ static int __init test_rhashtable(struct rhashtable *ht)
for (i = 0; i < TEST_NEXPANDS; i++) {
pr_info(" Table shrinkage iteration %u...\n", i);
- rhashtable_shrink(ht, GFP_KERNEL);
+ rhashtable_shrink(ht);
rcu_read_lock();
pr_info(" Verifying lookups...\n");
@@ -736,6 +744,10 @@ static int __init test_rhashtable(struct rhashtable *ht)
rcu_read_unlock();
}
+ rcu_read_lock();
+ test_bucket_stats(ht, true);
+ rcu_read_unlock();
+
pr_info(" Deleting %d keys\n", TEST_ENTRIES);
for (i = 0; i < TEST_ENTRIES; i++) {
u32 key = i * 2;
@@ -743,7 +755,7 @@ static int __init test_rhashtable(struct rhashtable *ht)
obj = rhashtable_lookup(ht, &key);
BUG_ON(!obj);
- rhashtable_remove(ht, &obj->node, GFP_KERNEL);
+ rhashtable_remove(ht, &obj->node);
kfree(obj);
}
@@ -766,8 +778,10 @@ static int __init test_rht_init(void)
.head_offset = offsetof(struct test_obj, node),
.key_offset = offsetof(struct test_obj, value),
.key_len = sizeof(int),
- .hashfn = arch_fast_hash,
+ .hashfn = jhash,
+#ifdef CONFIG_PROVE_LOCKING
.mutex_is_held = &test_mutex_is_held,
+#endif
.grow_decision = rht_grow_above_75,
.shrink_decision = rht_shrink_below_30,
};
OpenPOWER on IntegriCloud