bpf: fix struct htab_elem layout
PATCH 1/2 bpf: fix struct htab_elem layout
From: Alexei Starovoitov <[email protected]>
commit 9f691549f76d488a0c74397b3e51e943865ea01f upstream.
when htab_elem is removed from the bucket list the htab_elem.hash_node.next field should not be overridden too early otherwise we have a tiny race window between lookup and delete.
The bug was discovered by manual code analysis and reproducible only with explicit udelay() in lookup_elem_raw().
--- kernel/bpf/hashtab.c | 28 ++++++++++++++++++++++------ 1 file changed, 22 insertions(+), 6 deletions(-)
kernel/bpf/hashtab.c +22 -6
@@ -41,8 +41,13 @@ enum extra_elem_state {struct htab_elem {union {struct hlist_node hash_node; -struct bpf_htab *htab; -struct pcpu_freelist_node fnode; +struct { +void *padding; +union { +struct bpf_htab *htab; +struct pcpu_freelist_node fnode; + }; + }; };union {struct rcu_head rcu;
@@ -114,8 +119,10 @@ static int prealloc_elems_and_freelist(struct bpf_htab *htab)if (err) goto free_elems; -pcpu_freelist_populate (&htab->freelist, htab->elems, htab->elem_size, - htab->map.max_entries); +pcpu_freelist_populate (&htab->freelist, + htab->elems + offsetof(struct htab_elem , fnode), + htab->elem_size, htab->map.max_entries); +return 0 ; free_elems:
@@ -148,6 +155,11 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)int err, i;u64 cost; +BUILD_BUG_ON (offsetof(struct htab_elem , htab) != + offsetof(struct htab_elem, hash_node.pprev)); + BUILD_BUG_ON(offsetof(struct htab_elem, fnode.next) != + offsetof(struct htab_elem, hash_node.pprev)); +if (attr->map_flags & ~BPF_F_NO_PREALLOC )/* reserved bits should not be used */ return ERR_PTR (-EINVAL );
@@ -429,9 +441,13 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,int err =0 ;if (prealloc) { - l_new = (struct htab_elem *)pcpu_freelist_pop (&htab->freelist); -if (!l_new) +struct pcpu_freelist_node *l; + + l =pcpu_freelist_pop (&htab->freelist); +if (!l) err = -E2BIG ; +else + l_new = container_of(l, struct htab_elem, fnode); }else {if (atomic_inc_return (&htab->count) > htab->map.max_entries) {atomic_dec (&htab->count);
Signature · 1 line
2.21.0.1020.gf2820cf01a-goog
PATCH 2/2 bpf: convert htab map to hlist_nulls
From: Alexei Starovoitov <[email protected]>
commit 4fe8435909fddc97b81472026aa954e06dd192a5 upstream.
when all map elements are pre-allocated one cpu can delete and reuse htab_elem while another cpu is still walking the hlist. In such case the lookup may miss the element. Convert hlist to hlist_nulls to avoid such scenario. When bucket lock is taken there is no need to take such precautions, so only convert map_lookup and map_get_next to nulls.
The race window is extremely small and only reproducible with explicit udelay() inside lookup_nulls_elem_raw()
Similar to hlist add hlist_nulls_for_each_entry_safe() and hlist_nulls_entry_safe() helpers.
--- include/linux/list_nulls.h | 5 +++ include/linux/rculist_nulls.h | 14 +++++++ kernel/bpf/hashtab.c | 71 +++++++++++++++++++++++------------ 3 files changed, 67 insertions(+), 23 deletions(-)
include/linux/list_nulls.h +5 -0
@@ -29,6 +29,11 @@ struct hlist_nulls_node { ((ptr)->first = (struct hlist_nulls_node *) NULLS_MARKER(nulls))#define hlist_nulls_entry (ptr, type, member) container_of(ptr,type,member) + +#define hlist_nulls_entry_safe (ptr, type, member) \ + ({ typeof(ptr) ____ptr = (ptr); \ + !is_a_nulls(____ptr) ? hlist_nulls_entry(____ptr, type, member) : NULL; \ + })/** * ptr_is_a_nulls - Test if a ptr is a nulls * @ptr: ptr to be tested
include/linux/rculist_nulls.h +14 -0
@@ -118,5 +118,19 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n, ({ tpos =hlist_nulls_entry (pos,typeof (*tpos), member);1 ; }); \ pos = rcu_dereference_raw(hlist_nulls_next_rcu(pos))) +/** +* hlist_nulls_for_each_entry_safe - +* iterate over list of given type safe against removal of list entry +* @tpos: the type * to use as a loop cursor. +* @pos: the &struct hlist_nulls_node to use as a loop cursor. +* @head: the head for your list. +* @member: the name of the hlist_nulls_node within the struct. +*/ +#define hlist_nulls_for_each_entry_safe (tpos, pos, head, member) \ + for (({barrier();}), \ + pos = rcu_dereference_raw(hlist_nulls_first_rcu(head)); \ + (!is_a_nulls(pos)) && \ + ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); \ + pos = rcu_dereference_raw(hlist_nulls_next_rcu(pos)); 1; });)#endif #endif
kernel/bpf/hashtab.c +48 -23
190 lines not on this page · raw message
Signature · 1 line
2.21.0.1020.gf2820cf01a-goog
Quoted 10 lines · Chenbo Feng
From: Alexei Starovoitov <[email protected]>
commit
9f691549f76d488a0c74397b3e51e943865ea01fupstream.when
htab_elemis removed from the bucket list the htab_elem.hash_node.next field should not be overridden too early otherwise we have a tiny race window between lookup and delete.
The bug was discovered by manual code analysis and reproducible only with explicitudelay()inlookup_elem_raw().
Quoted 6 lines
Fixes 6c9059817432 ("bpf: pre-allocate hash map elements")Reported-by Jonathan Perry <[email protected]>Signed-off-by Alexei Starovoitov <[email protected]>Acked-by Daniel Borkmann <[email protected]>Signed-off-by David S. Miller <[email protected]>Signed-off-by Chenbo Feng <[email protected]>
Queued both for 4.9, thank you.
--
Thanks,
Sasha