rhashtable: Parallel atomic insert/deletion & deferred expansion
Subsystems (6)
Thomas Graf
maintainercover rhashtable: Parallel atomic insert/deletion & deferred expansion
This is still work in progress but I wanted to share this as soon as the direction where this is heading to becomes clear.
* Patch 1: Remove gfp_t awareness
* Patch 2: Enhance selftest to catch traversal miscount
* Patch 3: Nulls marker convertion
* Patch 4: Add spin_lock_bh_nested()
* Patch 5: Per bucket spinlock, deferred expansion/shrinking
Paul, Eric, John, Dave: Let me know how far off this is from what you had in mind.
Opens:
* I'm in particular interested in the feasibility of the side effect regarding recent insertion visibility in bucket traversals (see below). I think current users of rhashtable can live with it but it might be worth to offer a synchronous expansion alternative at some point.
If anybody has a better alternative I'm definitely interested to hear about it.
* Convert inet hashtable over to this and see if it is missing anything.
* Own worker thread as we might eventually sleep for multiple grace periods?
* Yes, some of the rcu_assign_pointer() can probably be replaced with RCU_INIT_POINTER().
Converts the single linked list to us a nulls marker. Reserves 4 bits to distinguish list membership. Stores a full 27 bit hash as the default marker. This allows the marker to stay valid even if the stable expands or shrinks.
Introduces an array of spinlocks to protect bucket mutations. The number of spinlocks per CPU is configurable and selected based on the hash of the bucket. This allows for parallel insertions and removals of entries which do not share a lock.
The patch also defers expansion and shrinking to a worker queue which allow insertion and removal from atomic context. Insertions and deletions may occur in parallel to it and are only held up briefly while the particular bucket is linked or unzipped.
Mutations of the bucket table pointer is protected by a new mutex taken during expansion and shrinking, read access to that pointer for insertion and deletion is RCU protected.
In the event of an expansion or shrinking, the new bucket table allocated is exposed as a so called future table right away. Lookups, deletions, and insertions will briefly use both tables. The future table becomes the main table after an RCU grace period and initial relinking was performed which guarantees that no new insertions occur on the old table and all entries can be found.
The side effect of this is that during that RCU grace period, a bucket traversal using any rht_for_each() variant on the main table will not see any insertions performed during the RCU grace period which would at that point land in the future table. The lookup will see them as it searches both tables if needed.
Thomas Graf (5):
rhashtable: Remove gfp_flags from insert and remove functions
rhashtable: Check for count misatch in selftest
rhashtable: Convert to nulls list
spinlock: Add spin_lock_bh_nested()
rhashtable: Per bucket locks & expansion/shrinking in work queue
include/linux/list_nulls.h | 3 +- include/linux/rhashtable.h | 241 +++++++++++------ include/linux/spinlock.h | 8 + include/linux/spinlock_api_smp.h | 2 + include/linux/spinlock_api_up.h | 1 + kernel/locking/spinlock.c | 8 + lib/rhashtable.c | 539 ++++++++++++++++++++++++++------------- net/netfilter/nft_hash.c | 69 ++--- net/netlink/af_netlink.c | 18 +- net/netlink/diag.c | 4 +- 10 files changed, 604 insertions(+), 289 deletions(-)
Signature · 1 line
1.9.3
Thomas Graf
maintainerPATCH 1/5 rhashtable: Remove gfp_flags from insert and remove functions
As the expansion/shrinking is moved to a worker thread, no allocations will be performed anymore.
--- include/linux/rhashtable.h | 10 +++++----- lib/rhashtable.c | 41 +++++++++++++++++------------------------ net/netfilter/nft_hash.c | 4 ++-- net/netlink/af_netlink.c | 4 ++-- 4 files changed, 26 insertions(+), 33 deletions(-)
include/linux/rhashtable.h +5 -5
@@ -96,16 +96,16 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);u32 rhashtable_hashfn (const struct rhashtable *ht,const void *key,u32 len);u32 rhashtable_obj_hashfn (const struct rhashtable *ht,void *ptr); -void rhashtable_insert (struct rhashtable *ht,struct rhash_head *node,gfp_t ); -bool rhashtable_remove (struct rhashtable *ht,struct rhash_head *node,gfp_t ); +void rhashtable_insert (struct rhashtable *ht,struct rhash_head *node); +bool rhashtable_remove (struct rhashtable *ht,struct rhash_head *node);void rhashtable_remove_pprev (struct rhashtable *ht,struct rhash_head *obj, -struct rhash_head __rcu **pprev,gfp_t flags); +struct rhash_head __rcu **pprev);bool rht_grow_above_75 (const struct rhashtable *ht,size_t new_size);bool rht_shrink_below_30 (const struct rhashtable *ht,size_t new_size); -int rhashtable_expand (struct rhashtable *ht,gfp_t flags); -int rhashtable_shrink (struct rhashtable *ht,gfp_t flags); +int rhashtable_expand (struct rhashtable *ht); +int rhashtable_shrink (struct rhashtable *ht);void *rhashtable_lookup (const struct rhashtable *ht,const void *key); void *rhashtable_lookup_compare(const struct rhashtable *ht, u32 hash,
lib/rhashtable.c +17 -24
172 lines not on this page · raw message
net/netfilter/nft_hash.c +2 -2
@@ -65,7 +65,7 @@ static int nft_hash_insert(const struct nft_set *set,if (set->flags &NFT_SET_MAP )nft_data_copy (he->data, &elem->data); -rhashtable_insert (priv, &he->node,GFP_KERNEL ); +rhashtable_insert (priv, &he->node);return 0 ; }
@@ -88,7 +88,7 @@ static void nft_hash_remove(const struct nft_set *set, pprev = elem->cookie; he =rht_dereference ((*pprev), priv); -rhashtable_remove_pprev (priv, he, pprev,GFP_KERNEL ); +rhashtable_remove_pprev (priv, he, pprev);synchronize_rcu ();kfree (he);
net/netlink/af_netlink.c +2 -2
@@ -1082,7 +1082,7 @@ static int netlink_insert(struct sock *sk, struct net *net, u32 portid)nlk_sk (sk)->portid = portid;sock_hold (sk); -rhashtable_insert (&table->hash, &nlk_sk (sk)->node,GFP_KERNEL ); +rhashtable_insert (&table->hash, &nlk_sk (sk)->node); err =0 ; err:mutex_unlock (&nl_sk_hash_lock);
@@ -1095,7 +1095,7 @@ static void netlink_remove(struct sock *sk)mutex_lock (&nl_sk_hash_lock); table = &nl_table[sk->sk_protocol]; -if (rhashtable_remove (&table->hash, &nlk_sk (sk)->node,GFP_KERNEL )) { +if (rhashtable_remove (&table->hash, &nlk_sk (sk)->node)) {WARN_ON (atomic_read (&sk->sk_refcnt) ==1 );__sock_put (sk); }
Signature · 1 line
1.9.3
Thomas Graf
maintainerPATCH 5/5 rhashtable: Per bucket locks & expansion/shrinking in work queue
In reply to Thomas GrafIntroduces an array of spinlocks to protect bucket mutations. The number of spinlocks per CPU is configurable and selected based on the hash of the bucket. This allows for parallel insertions and removals of entries which do not share a lock.
The patch also defers expansion and shrinking to a worker queue which allow insertion and removal from atomic context. Insertions and deletions may occur in parallel to it and are only held up briefly while the particular bucket is linked or unzipped.
Mutations of the bucket table pointer is protected by a new mutex, read access to that pointer for insertion and deletion is RCU protected.
In the event of an expansion or shrinking, the new bucket table allocated is exposed as a so called future table right away. Lookups, deletions, and insertions will briefly use both tables. The future table becomes the main table after an RCU grace period and initial relinking was performed which guarantees that no new insertions occur on the old table but all entries can be found.
The side effect of this is that during that RCU grace period, a bucket traversal using any rht_for_each() variant on the main table will not see any insertions performed during the RCU grace period which would at that point land in the future table. The lookup will see them as it searches both tables if needed.
--- include/linux/rhashtable.h | 42 +++-- lib/rhashtable.c | 375 +++++++++++++++++++++++++++++++-------------- net/netfilter/nft_hash.c | 59 +++---- net/netlink/af_netlink.c | 5 +- 4 files changed, 330 insertions(+), 151 deletions(-)
include/linux/rhashtable.h +33 -9
@@ -19,13 +19,23 @@#define _LINUX_RHASHTABLE_H#include <linux/list_nulls.h> +#include <linux/workqueue.h> struct rhash_head {struct rhash_head __rcu *next; }; +/** +* struct bucket_table - Table of hash buckets +* @size: Number of hash buckets +* @locks_mask: Mask to apply before accessing locks[] +* @locks: Array of spinlocks protecting individual buckets +* @buckets: size * hash buckets +*/ struct bucket_table {size_t size; +unsigned int locks_mask; +spinlock_t *locks;struct rhash_head __rcu *buckets[]; };
@@ -44,6 +54,7 @@ struct rhashtable;* @max_shift: Maximum number of shifts while expanding * @min_shift: Minimum number of shifts while shrinking * @nulls_base: Base value to generate nulls marker +* @locks_mul: Number of bucket locks to allocate per cpu (default: 128) * @hashfn: Function to hash key * @obj_hashfn: Function to hash object * @grow_decision: If defined, may return true if table should expand
@@ -59,6 +70,7 @@ struct rhashtable_params {size_t max_shift;size_t min_shift;int nulls_base; +size_t locks_mul;rht_hashfn_t hashfn;rht_obj_hashfn_t obj_hashfn; bool (*grow_decision)(const struct rhashtable *ht,
@@ -71,15 +83,23 @@ struct rhashtable_params {/** * struct rhashtable - Hash table handle * @tbl: Bucket table +* @future_tbl: Future table during expansion and shrinking * @nelems: Number of elements in table * @shift: Current size (1 << shift) * @p: Configuration parameters +* @run_work: Delayed work executing expansion/shrinking +* @mutex: Hold while expansion/shrinking takes places +* @being_destroyed: True if table is set to be destroyed */ struct rhashtable {struct bucket_table __rcu *tbl; +struct bucket_table __rcu *future_tbl;size_t nelems;size_t shift;struct rhashtable_params p; +struct delayed_work run_work; +struct mutex mutex; +bool being_destroyed; };static inline unsigned long rht_marker (const struct rhashtable *ht,u32 hash)
@@ -101,9 +121,16 @@ static inline unsigned long rht_get_nulls_value(const struct rhash_head *ptr) }#ifdef CONFIG_PROVE_LOCKING -int lockdep_rht_mutex_is_held (const struct rhashtable *ht); +int lockdep_rht_mutex_is_held (struct rhashtable *ht); +int rht_bucket_lock_is_held (const struct bucket_table *tbl,u32 hash);#else -static inline int lockdep_rht_mutex_is_held (const struct rhashtable *ht) +static inline int lockdep_rht_mutex_is_held (struct rhashtable *ht) +{ +return 1 ; +} + +static inline int lockdep_rht_bucket_is_held (const struct bucket_table *tbl, +u32 hash) {return 1 ; }
@@ -112,12 +139,9 @@ static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)int rhashtable_init (struct rhashtable *ht,struct rhashtable_params *params);u32 rhashtable_hashfn (const struct rhashtable *ht,const void *key,u32 len); -u32 rhashtable_obj_hashfn (const struct rhashtable *ht,void *ptr);void rhashtable_insert (struct rhashtable *ht,struct rhash_head *node);bool rhashtable_remove (struct rhashtable *ht,struct rhash_head *node); -void rhashtable_remove_pprev (struct rhashtable *ht,struct rhash_head *obj, -struct rhash_head __rcu **pprev);bool rht_grow_above_75 (const struct rhashtable *ht,size_t new_size);bool rht_shrink_below_30 (const struct rhashtable *ht,size_t new_size);
@@ -126,10 +150,10 @@ int rhashtable_expand(struct rhashtable *ht);int rhashtable_shrink (struct rhashtable *ht);void *rhashtable_lookup (const struct rhashtable *ht,const void *key); -void *rhashtable_lookup_compare (const struct rhashtable *ht,u32 hash, +void *rhashtable_lookup_compare (const struct rhashtable *ht,const void *key,bool (*compare)(void *,void *),void *arg); -void rhashtable_destroy (const struct rhashtable *ht); +void rhashtable_destroy (struct rhashtable *ht);#define rht_dereference (p, ht) \ rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
@@ -138,10 +162,10 @@ void rhashtable_destroy(const struct rhashtable *ht); rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))#define rht_dereference_bucket (p, tbl, hash) \ - rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht)) + rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))#define rht_dereference_bucket_rcu (p, tbl, hash) \ - rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht)) + rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))#define rht_entry (tpos, pos, member) \ ({ tpos = container_of(pos, typeof(*tpos), member); 1; })
lib/rhashtable.c +263 -112
664 lines not on this page · raw message
net/netfilter/nft_hash.c +33 -26
81 lines not on this page · raw message
net/netlink/af_netlink.c +1 -4
@@ -1015,11 +1015,8 @@ static struct sock *__netlink_lookup(struct netlink_table *table, u32 portid, .net = net, .portid = portid, }; -u32 hash; - hash =rhashtable_hashfn (&table->hash, &portid,sizeof (portid)); - -return rhashtable_lookup_compare (&table->hash, hash, +return rhashtable_lookup_compare (&table->hash, &portid, &netlink_compare, &arg); }
Signature · 1 line
1.9.3
Thomas Graf
maintainerPATCH 2/5 rhashtable: Check for count misatch in selftest
In reply to Thomas Graf--- lib/rhashtable.c | 19 ++++++++++++++----- 1 file changed, 14 insertions(+), 5 deletions(-)
lib/rhashtable.c +14 -5
@@ -648,15 +648,14 @@ 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,struct bucket_table *tbl, +bool quiet) { -unsigned int cnt, i, total =0 ; +unsigned int cnt, rcu_cnt, i, total =0 ;struct test_obj *obj;for (i =0 ; i < tbl->size; i++) { - cnt =0 ; + rcu_cnt = cnt =0 ;if (!quiet)pr_info (" [%#4x/%zu]" , i, tbl->size);
@@ -668,6 +667,13 @@ static void test_bucket_stats(struct rhashtable *ht,pr_cont (" [%p]," , obj); } +rht_for_each_rcu (pos, tbl, i) + 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);
@@ -675,6 +681,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)
Signature · 1 line
1.9.3
Thomas Graf
maintainerPATCH 3/5 rhashtable: Convert to nulls list
In reply to Thomas GrafIn order to allow wider usage of rhashtable, use a special nulls marker to terminate each chain. The reason for not using the existing nulls_list is that the pprev pointer usage would not be valid as entries can be linked in two different buckets at the same time.
--- include/linux/list_nulls.h | 3 +- include/linux/rhashtable.h | 195 +++++++++++++++++++++++++++++++-------------- lib/rhashtable.c | 158 ++++++++++++++++++++++-------------- net/netfilter/nft_hash.c | 12 ++- net/netlink/af_netlink.c | 9 ++- net/netlink/diag.c | 4 +- 6 files changed, 248 insertions(+), 133 deletions(-)
include/linux/list_nulls.h +2 -1
@@ -21,8 +21,9 @@ struct hlist_nulls_head {struct hlist_nulls_node {struct hlist_nulls_node *next, **pprev; }; +#define NULLS_MARKER (value) (1UL | (((long)value) << 1))#define INIT_HLIST_NULLS_HEAD (ptr, nulls) \ - ((ptr)->first = (struct hlist_nulls_node *) (1UL | (((long)nulls) << 1))) + ((ptr)->first = (struct hlist_nulls_node *) NULLS_MARKER(nulls))#define hlist_nulls_entry (ptr, type, member) container_of(ptr,type,member)/**
include/linux/rhashtable.h +133 -62
257 lines not on this page · raw message
lib/rhashtable.c +96 -62
328 lines not on this page · raw message
net/netfilter/nft_hash.c +8 -4
@@ -99,12 +99,13 @@ static int nft_hash_get(const struct nft_set *set, struct nft_set_elem *elem)const struct rhashtable *priv =nft_set_priv (set);const struct bucket_table *tbl =rht_dereference_rcu (priv->tbl, priv);struct rhash_head __rcu *const *pprev; +struct rhash_head *pos;struct nft_hash_elem *he;u32 h; h =rhashtable_hashfn (priv, &elem->key, set->klen); pprev = &tbl->buckets[h]; -rht_for_each_entry_rcu (he, tbl->buckets[h], node) { +rht_for_each_entry_rcu (he, pos, tbl, h, node) {if (nft_data_cmp (&he->key, &elem->key, set->klen)) { pprev = &he->node.next;continue ;
@@ -130,7 +131,9 @@ static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set, tbl =rht_dereference_rcu (priv->tbl, priv);for (i =0 ; i < tbl->size; i++) { -rht_for_each_entry_rcu (he, tbl->buckets[i], node) { +struct rhash_head *pos; + +rht_for_each_entry_rcu (he, pos, tbl, i, node) {if (iter->count < iter->skip) goto cont;
@@ -181,12 +184,13 @@ static void nft_hash_destroy(const struct nft_set *set) {const struct rhashtable *priv =nft_set_priv (set);const struct bucket_table *tbl; -struct nft_hash_elem *he, *next; +struct nft_hash_elem *he; +struct rhash_head *pos, *next;unsigned int i; tbl =rht_dereference (priv->tbl, priv);for (i =0 ; i < tbl->size; i++) -rht_for_each_entry_safe (he, next, tbl->buckets[i], priv, node) +rht_for_each_entry_safe (he, pos, next, tbl, i, node)nft_hash_elem_destroy (set, he);rhashtable_destroy (priv);
net/netlink/af_netlink.c +6 -3
@@ -2903,7 +2903,9 @@ static struct sock *netlink_seq_socket_idx(struct seq_file *seq, loff_t pos)const struct bucket_table *tbl =rht_dereference_rcu (ht->tbl, ht);for (j =0 ; j < tbl->size; j++) { -rht_for_each_entry_rcu (nlk, tbl->buckets[j], node) { +struct rhash_head *node; + +rht_for_each_entry_rcu (nlk, node, tbl, j, node) { s = (struct sock *)nlk;if (sock_net (s) !=seq_file_net (seq))
@@ -2929,6 +2931,7 @@ static void *netlink_seq_start(struct seq_file *seq, loff_t *pos)static void *netlink_seq_next (struct seq_file *seq,void *v,loff_t *pos) { +struct rhash_head *node;struct netlink_sock *nlk;struct nl_seq_iter *iter;struct net *net;
@@ -2943,7 +2946,7 @@ static void *netlink_seq_next(struct seq_file *seq, void *v, loff_t *pos) iter = seq->private; nlk = v; -rht_for_each_entry_rcu (nlk, nlk->node.next, node) +rht_for_each_entry_rcu_continue (nlk, node, nlk->node.next, node)if (net_eq (sock_net ((struct sock *)nlk), net))return nlk;
@@ -2955,7 +2958,7 @@ static void *netlink_seq_next(struct seq_file *seq, void *v, loff_t *pos)const struct bucket_table *tbl =rht_dereference_rcu (ht->tbl, ht);for (; j < tbl->size; j++) { -rht_for_each_entry_rcu (nlk, tbl->buckets[j], node) { +rht_for_each_entry_rcu (nlk, node, tbl, j, node) {if (net_eq (sock_net ((struct sock *)nlk), net)) { iter->link = i; iter->hash_idx = j;
net/netlink/diag.c +3 -1
@@ -113,7 +113,9 @@ static int __netlink_diag_dump(struct sk_buff *skb, struct netlink_callback *cb, req =nlmsg_data (cb->nlh);for (i =0 ; i < htbl->size; i++) { -rht_for_each_entry (nlsk, htbl->buckets[i], ht, node) { +struct rhash_head *node; + +rht_for_each_entry (nlsk, node, htbl, i, node) { sk = (struct sock *)nlsk;if (!net_eq (sock_net (sk), net))
Signature · 1 line
1.9.3
Thomas Graf
maintainerPATCH 4/5 spinlock: Add spin_lock_bh_nested()
In reply to Thomas Graf--- include/linux/spinlock.h | 8 ++++++++ include/linux/spinlock_api_smp.h | 2 ++ include/linux/spinlock_api_up.h | 1 + kernel/locking/spinlock.c | 8 ++++++++ 4 files changed, 19 insertions(+)
include/linux/spinlock.h +8 -0
@@ -190,6 +190,8 @@ static inline void do_raw_spin_unlock(raw_spinlock_t *lock) __releases(lock)#ifdef CONFIG_DEBUG_LOCK_ALLOC # define raw_spin_lock_nested (lock, subclass) \ _raw_spin_lock_nested(lock, subclass) +# define raw_spin_lock_bh_nested (lock, subclass) \ + _raw_spin_lock_bh_nested(lock, subclass)# define raw_spin_lock_nest_lock (lock, nest_lock) \ do { \
@@ -199,6 +201,7 @@ static inline void do_raw_spin_unlock(raw_spinlock_t *lock) __releases(lock)#else # define raw_spin_lock_nested (lock, subclass) _raw_spin_lock(lock)# define raw_spin_lock_nest_lock (lock, nest_lock) _raw_spin_lock(lock) +# define raw_spin_lock_bh_nested (lock, subclass) _raw_spin_lock_bh(lock)#endif #if defined(CONFIG_SMP ) || defined(CONFIG_DEBUG_SPINLOCK )
@@ -318,6 +321,11 @@ do { \raw_spin_lock_nested (spinlock_check (lock), subclass); \ } while (0) +#define spin_lock_bh_nested (lock, subclass) \ +do { \ + raw_spin_lock_bh_nested(spinlock_check(lock), subclass);\ +} while (0) +#define spin_lock_nest_lock (lock, nest_lock) \ do { \ raw_spin_lock_nest_lock(spinlock_check(lock), nest_lock); \
include/linux/spinlock_api_smp.h +2 -0
@@ -22,6 +22,8 @@ int in_lock_functions(unsigned long addr); void __lockfunc _raw_spin_lock(raw_spinlock_t *lock) __acquires(lock); void __lockfunc _raw_spin_lock_nested(raw_spinlock_t *lock, int subclass) __acquires(lock); +void __lockfunc _raw_spin_lock_bh_nested(raw_spinlock_t *lock, int subclass) + __acquires(lock); void __lockfunc _raw_spin_lock_nest_lock(raw_spinlock_t *lock, struct lockdep_map *map) __acquires(lock);
include/linux/spinlock_api_up.h +1 -0
@@ -57,6 +57,7 @@#define _raw_spin_lock (lock) __LOCK(lock)#define _raw_spin_lock_nested (lock, subclass) __LOCK(lock) +#define _raw_spin_lock_bh_nested (lock, subclass) __LOCK(lock)#define _raw_read_lock (lock) __LOCK(lock)#define _raw_write_lock (lock) __LOCK(lock)#define _raw_spin_lock_bh (lock) __LOCK_BH(lock)
kernel/locking/spinlock.c +8 -0
@@ -363,6 +363,14 @@ void __lockfunc _raw_spin_lock_nested(raw_spinlock_t *lock, int subclass) }EXPORT_SYMBOL (_raw_spin_lock_nested); +void __lockfunc _raw_spin_lock_bh_nested(raw_spinlock_t *lock, int subclass) +{ +__local_bh_disable_ip (_RET_IP_,SOFTIRQ_LOCK_OFFSET ); +spin_acquire (&lock->dep_map, subclass,0 , _RET_IP_); +LOCK_CONTENDED (lock, do_raw_spin_trylock, do_raw_spin_lock); +} +EXPORT_SYMBOL (_raw_spin_lock_bh_nested); +unsigned long __lockfunc _raw_spin_lock_irqsave_nested (raw_spinlock_t *lock,int subclass) {
Signature · 1 line
1.9.3
Re: [PATCH 1/5] rhashtable: Remove gfp_flags from insert and remove functions
In reply to Thomas GrafQuoted 3 lines · Thomas Graf
As the expansion/shrinking is moved to a worker thread, no allocations will be performed anymore.
You meant : no GFP_ATOMIC allocations ?
I would rephrase using something like :
Because hash resizes are potentially time consuming, they'll be performed in process context where GFP_KERNEL allocations are preferred.
Quoted 41 lines
Signed-off-by Thomas Graf <[email protected]>--- include/linux/rhashtable.h | 10 +++++----- lib/rhashtable.c | 41 +++++++++++++++++------------------------ net/netfilter/nft_hash.c | 4 ++-- net/netlink/af_netlink.c | 4 ++-- 4 files changed, 26 insertions(+), 33 deletions(-)include/linux/rhashtable.h +5
-5@@ -96,16 +96,16 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);u32 rhashtable_hashfn (const struct rhashtable *ht,const void *key,u32 len);u32 rhashtable_obj_hashfn (const struct rhashtable *ht,void *ptr); -void rhashtable_insert (struct rhashtable *ht,struct rhash_head *node,gfp_t ); -bool rhashtable_remove (struct rhashtable *ht,struct rhash_head *node,gfp_t ); +void rhashtable_insert (struct rhashtable *ht,struct rhash_head *node); +bool rhashtable_remove (struct rhashtable *ht,struct rhash_head *node);void rhashtable_remove_pprev (struct rhashtable *ht,struct rhash_head *obj, -struct rhash_head __rcu **pprev,gfp_t flags); +struct rhash_head __rcu **pprev);bool rht_grow_above_75 (const struct rhashtable *ht,size_t new_size);bool rht_shrink_below_30 (const struct rhashtable *ht,size_t new_size); -int rhashtable_expand (struct rhashtable *ht,gfp_t flags); -int rhashtable_shrink (struct rhashtable *ht,gfp_t flags); +int rhashtable_expand (struct rhashtable *ht); +int rhashtable_shrink (struct rhashtable *ht);void *rhashtable_lookup (const struct rhashtable *ht,const void *key); void *rhashtable_lookup_compare(const struct rhashtable *ht, u32 hash,lib/rhashtable.c +0
-0@@ -108,13 +108,13 @@ static u32 head_hashfn(const struct rhashtable *ht,return obj_hashfn (ht,rht_obj (ht, he), hsize); }
lib/rhashtable.c static u32 head_hashfn(const struct rhashtable *ht, · line 117
Quoted 10 lines
lib/rhashtable.c +2
-2-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 );
Add __GFP_NOWARN, as you fallback to vzalloc ?
lib/rhashtable.c static u32 head_hashfn(const struct rhashtable *ht, · line 119
Quoted 2 lines
lib/rhashtable.c +0
-0if (tbl ==NULL ) tbl =vzalloc (size);
btw, inet hash table uses alloc_large_system_hash() which spreads the pages on all available NUMA nodes :
# dmesg | grep "TCP established" [ 1.223046] TCP established hash table entries: 524288 (order: 10, 4194304 bytes) # grep alloc_large_system_hash /proc/vmallocinfo | grep pages=1024 0xffffc900181d6000-0xffffc900185d7000 4198400 alloc_large_system_hash+0x177/0x237 pages=1024 vmalloc vpages N0=512 N1=512 0xffffc900185d7000-0xffffc900189d8000 4198400 alloc_large_system_hash+0x177/0x237 pages=1024 vmalloc vpages N0=512 N1=512 0xffffc90028a01000-0xffffc90028e02000 4198400 alloc_large_system_hash+0x177/0x237 pages=1024 vmalloc vpages N0=512 N1=512
So we might keep in mind to keep this numa policy.
Rest of the patch looks fine to me, thanks.
Thomas Graf
maintainerRe: [PATCH 1/5] rhashtable: Remove gfp_flags from insert and remove functions
Quoted 11 lines · Eric Dumazet
Quoted 3 lines · Thomas Graf
As the expansion/shrinking is moved to a worker thread, no allocations will be performed anymore.
You meant : no
GFP_ATOMICallocations ?I would rephrase using something like :
Because hash resizes are potentially time consuming, they'll be performed in process context where
GFP_KERNELallocations are preferred.
I meant to say no allocations in insert/remove anymore but your wording is even clearer. I'll update it.
Quoted 4 lines
lib/rhashtable.c static u32 head_hashfn(const struct rhashtable *ht, · line 117
Quoted 2 lines
lib/rhashtable.c +1
-1- tbl =kzalloc (size, flags); + tbl =kzalloc (size,GFP_KERNEL );Add
__GFP_NOWARN, as you fallback to vzalloc ?
Good point.
Quoted 11 lines
btw, inet hash table uses
alloc_large_system_hash()which spreads the pages on all available NUMA nodes :# dmesg | grep "TCP established" [ 1.223046] TCP established hash table entries: 524288 (order: 10, 4194304 bytes) # grep alloc_large_system_hash /proc/vmallocinfo | grep pages=1024 0xffffc900181d6000-0xffffc900185d7000 4198400 alloc_large_system_hash+0x177/0x237 pages=1024 vmalloc vpages N0=512 N1=512 0xffffc900185d7000-0xffffc900189d8000 4198400 alloc_large_system_hash+0x177/0x237 pages=1024 vmalloc vpages N0=512 N1=512 0xffffc90028a01000-0xffffc90028e02000 4198400 alloc_large_system_hash+0x177/0x237 pages=1024 vmalloc vpages N0=512 N1=512So we might keep in mind to keep this numa policy.
Agreed. Will introduce this through a table parameter option when converting the inet hash table.
Re: [PATCH 1/5] rhashtable: Remove gfp_flags from insert and remove functions
Quoted 2 lines · Thomas Graf
Agreed. Will introduce this through a table parameter option when converting the inet hash table.
I am not sure you covered the /proc/net/tcp problem yet ? (or inet_diag)
Thomas Graf
maintainerRe: [PATCH 1/5] rhashtable: Remove gfp_flags from insert and remove functions
Quoted 6 lines · Eric Dumazet
Quoted 2 lines · Thomas Graf
Agreed. Will introduce this through a table parameter option when converting the inet hash table.
I am not sure you covered the
/proc/net/tcpproblem yet ? (orinet_diag)
I haven't digged through inet_diag in all detail yet but was planning to acquire ht->mutex to block expansions and then take bucket locks during bucket traverals as done now. I will do that next but wanted to get this out for comments in the meantime.
Re: [PATCH 5/5] rhashtable: Per bucket locks & expansion/shrinking in work queue
In reply to Thomas Graflib/rhashtable.c static u32 head_hashfn(const struct rhashtable *ht, · line 160
Quoted 12 lines · Thomas Graf
lib/rhashtable.c +12
-0+static int alloc_bucket_locks (struct rhashtable *ht,struct bucket_table *tbl) +{ +unsigned int i, size; +#if defined(CONFIG_PROVE_LOCKING ) +unsigned int nr_pcpus =2 ; +#else +unsigned int nr_pcpus =num_possible_cpus (); +#endif + + nr_pcpus = min_t(unsigned int, nr_pcpus, 32UL); + size = nr_pcpus * ht->p.locks_mul; +
You need to roundup to next power of two.
Quoted 17 lines
lib/rhashtable.c +17
-0+if (sizeof (spinlock_t) !=0 ) { +#ifdef CONFIG_NUMA +if (size *sizeof (spinlock_t) >PAGE_SIZE ) + tbl->locks =vmalloc (size *sizeof (spinlock_t)); + else +#endif + tbl->locks =kmalloc_array (size,sizeof (spinlock_t), +GFP_KERNEL ); +if (!tbl->locks) +return -ENOMEM ; +for (i =0 ; i < size; i++) +spin_lock_init (&tbl->locks[i]); + } + tbl->locks_mask = size -1 ; + +return 0 ; +}
Thomas Graf
maintainerRe: [PATCH 5/5] rhashtable: Per bucket locks & expansion/shrinking in work queue
Quoted 1 line · Eric Dumazet
You need to roundup to next power of two.
Fixed, thanks!
Re: [PATCH 1/5] rhashtable: Remove gfp_flags from insert and remove functions
In reply to Thomas GrafQuoted 16 lines · Thomas Graf
Quoted 11 lines · Eric Dumazet
Quoted 3 lines · Thomas Graf
As the expansion/shrinking is moved to a worker thread, no allocations will be performed anymore.
You meant : no
GFP_ATOMICallocations ?I would rephrase using something like :
Because hash resizes are potentially time consuming, they'll be performed in process context where
GFP_KERNELallocations are preferred.I meant to say no allocations in insert/remove anymore but your wording is even clearer. I'll update it.
Quoted 6 lines
Quoted 4 lines
lib/rhashtable.c static u32 head_hashfn(const struct rhashtable *ht, · line 117
Quoted 2 lines
lib/rhashtable.c +1
-1- tbl =kzalloc (size, flags); + tbl =kzalloc (size,GFP_KERNEL );Add
__GFP_NOWARN, as you fallback to vzalloc ?Good point.
It needs to be both __GFP_NOWARN and __GFP_NORETRY.
Otherwise the system will kick in the OOM killer before it falls back to vzalloc. Which I can't imagine anyone wanting.
Look at the history of alloc_fdmem in fs/file.c for the real world reasoning.
Eric