* [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops
@ 2020-02-18 17:25 Brian Vazquez
2020-02-18 21:23 ` Yonghong Song
` (2 more replies)
0 siblings, 3 replies; 5+ messages in thread
From: Brian Vazquez @ 2020-02-18 17:25 UTC (permalink / raw)
To: Brian Vazquez, Brian Vazquez, Alexei Starovoitov,
Daniel Borkmann, David S . Miller
Cc: linux-kernel, netdev, bpf, Yonghong Song
Grabbing the spinlock for every bucket even if it's empty, was causing
significant perfomance cost when traversing htab maps that have only a
few entries. This patch addresses the issue by checking first the
bucket_cnt, if the bucket has some entries then we go and grab the
spinlock and proceed with the batching.
Tested with a htab of size 50K and different value of populated entries.
Before:
Benchmark Time(ns) CPU(ns)
---------------------------------------------
BM_DumpHashMap/1 2759655 2752033
BM_DumpHashMap/10 2933722 2930825
BM_DumpHashMap/200 3171680 3170265
BM_DumpHashMap/500 3639607 3635511
BM_DumpHashMap/1000 4369008 4364981
BM_DumpHashMap/5k 11171919 11134028
BM_DumpHashMap/20k 69150080 69033496
BM_DumpHashMap/39k 190501036 190226162
After:
Benchmark Time(ns) CPU(ns)
---------------------------------------------
BM_DumpHashMap/1 202707 200109
BM_DumpHashMap/10 213441 210569
BM_DumpHashMap/200 478641 472350
BM_DumpHashMap/500 980061 967102
BM_DumpHashMap/1000 1863835 1839575
BM_DumpHashMap/5k 8961836 8902540
BM_DumpHashMap/20k 69761497 69322756
BM_DumpHashMap/39k 187437830 186551111
Fixes: 057996380a42 ("bpf: Add batch ops to all htab bpf map")
Cc: Yonghong Song <yhs@fb.com>
Signed-off-by: Brian Vazquez <brianvv@google.com>
---
v1 -> v2: Skip hlist_nulls_for_each_entry_safe if lock is not held
kernel/bpf/hashtab.c | 22 +++++++++++++++++++++-
1 file changed, 21 insertions(+), 1 deletion(-)
diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 2d182c4ee9d99..ea3bf04a0a7b6 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -1260,6 +1260,7 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
struct hlist_nulls_head *head;
struct hlist_nulls_node *n;
unsigned long flags;
+ bool locked = false;
struct htab_elem *l;
struct bucket *b;
int ret = 0;
@@ -1319,15 +1320,25 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
dst_val = values;
b = &htab->buckets[batch];
head = &b->head;
- raw_spin_lock_irqsave(&b->lock, flags);
+ /* do not grab the lock unless need it (bucket_cnt > 0). */
+ if (locked)
+ raw_spin_lock_irqsave(&b->lock, flags);
bucket_cnt = 0;
hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
bucket_cnt++;
+ if (bucket_cnt && !locked) {
+ locked = true;
+ goto again_nocopy;
+ }
+
if (bucket_cnt > (max_count - total)) {
if (total == 0)
ret = -ENOSPC;
+ /* Note that since bucket_cnt > 0 here, it is implicit
+ * that the locked was grabbed, so release it.
+ */
raw_spin_unlock_irqrestore(&b->lock, flags);
rcu_read_unlock();
this_cpu_dec(bpf_prog_active);
@@ -1337,6 +1348,9 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
if (bucket_cnt > bucket_size) {
bucket_size = bucket_cnt;
+ /* Note that since bucket_cnt > 0 here, it is implicit
+ * that the locked was grabbed, so release it.
+ */
raw_spin_unlock_irqrestore(&b->lock, flags);
rcu_read_unlock();
this_cpu_dec(bpf_prog_active);
@@ -1346,6 +1360,10 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
goto alloc;
}
+ /* Next block is only safe to run if you have grabbed the lock */
+ if (!locked)
+ goto next_batch;
+
hlist_nulls_for_each_entry_safe(l, n, head, hash_node) {
memcpy(dst_key, l->key, key_size);
@@ -1380,6 +1398,8 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
}
raw_spin_unlock_irqrestore(&b->lock, flags);
+ locked = false;
+next_batch:
/* If we are not copying data, we can go to next bucket and avoid
* unlocking the rcu.
*/
--
2.25.0.265.gbab2e86ba0-goog
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops
2020-02-18 17:25 [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops Brian Vazquez
@ 2020-02-18 21:23 ` Yonghong Song
2020-02-19 23:12 ` Alexei Starovoitov
2020-02-20 2:25 ` kbuild test robot
2020-02-20 5:29 ` kbuild test robot
2 siblings, 1 reply; 5+ messages in thread
From: Yonghong Song @ 2020-02-18 21:23 UTC (permalink / raw)
To: Brian Vazquez, Brian Vazquez, Alexei Starovoitov,
Daniel Borkmann, David S . Miller
Cc: linux-kernel, netdev, bpf
On 2/18/20 9:25 AM, Brian Vazquez wrote:
> Grabbing the spinlock for every bucket even if it's empty, was causing
> significant perfomance cost when traversing htab maps that have only a
> few entries. This patch addresses the issue by checking first the
> bucket_cnt, if the bucket has some entries then we go and grab the
> spinlock and proceed with the batching.
>
> Tested with a htab of size 50K and different value of populated entries.
>
> Before:
> Benchmark Time(ns) CPU(ns)
> ---------------------------------------------
> BM_DumpHashMap/1 2759655 2752033
> BM_DumpHashMap/10 2933722 2930825
> BM_DumpHashMap/200 3171680 3170265
> BM_DumpHashMap/500 3639607 3635511
> BM_DumpHashMap/1000 4369008 4364981
> BM_DumpHashMap/5k 11171919 11134028
> BM_DumpHashMap/20k 69150080 69033496
> BM_DumpHashMap/39k 190501036 190226162
>
> After:
> Benchmark Time(ns) CPU(ns)
> ---------------------------------------------
> BM_DumpHashMap/1 202707 200109
> BM_DumpHashMap/10 213441 210569
> BM_DumpHashMap/200 478641 472350
> BM_DumpHashMap/500 980061 967102
> BM_DumpHashMap/1000 1863835 1839575
> BM_DumpHashMap/5k 8961836 8902540
> BM_DumpHashMap/20k 69761497 69322756
> BM_DumpHashMap/39k 187437830 186551111
>
> Fixes: 057996380a42 ("bpf: Add batch ops to all htab bpf map")
> Cc: Yonghong Song <yhs@fb.com>
> Signed-off-by: Brian Vazquez <brianvv@google.com>
Thanks for the fix.
Acked-by: Yonghong Song <yhs@fb.com>
> ---
> v1 -> v2: Skip hlist_nulls_for_each_entry_safe if lock is not held
>
> kernel/bpf/hashtab.c | 22 +++++++++++++++++++++-
> 1 file changed, 21 insertions(+), 1 deletion(-)
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops
2020-02-18 21:23 ` Yonghong Song
@ 2020-02-19 23:12 ` Alexei Starovoitov
0 siblings, 0 replies; 5+ messages in thread
From: Alexei Starovoitov @ 2020-02-19 23:12 UTC (permalink / raw)
To: Yonghong Song
Cc: Brian Vazquez, Brian Vazquez, Alexei Starovoitov,
Daniel Borkmann, David S . Miller, LKML, Network Development,
bpf
On Tue, Feb 18, 2020 at 1:23 PM Yonghong Song <yhs@fb.com> wrote:
>
>
>
> On 2/18/20 9:25 AM, Brian Vazquez wrote:
> > Grabbing the spinlock for every bucket even if it's empty, was causing
> > significant perfomance cost when traversing htab maps that have only a
> > few entries. This patch addresses the issue by checking first the
> > bucket_cnt, if the bucket has some entries then we go and grab the
> > spinlock and proceed with the batching.
> >
> > Tested with a htab of size 50K and different value of populated entries.
> >
> > Before:
> > Benchmark Time(ns) CPU(ns)
> > ---------------------------------------------
> > BM_DumpHashMap/1 2759655 2752033
> > BM_DumpHashMap/10 2933722 2930825
> > BM_DumpHashMap/200 3171680 3170265
> > BM_DumpHashMap/500 3639607 3635511
> > BM_DumpHashMap/1000 4369008 4364981
> > BM_DumpHashMap/5k 11171919 11134028
> > BM_DumpHashMap/20k 69150080 69033496
> > BM_DumpHashMap/39k 190501036 190226162
> >
> > After:
> > Benchmark Time(ns) CPU(ns)
> > ---------------------------------------------
> > BM_DumpHashMap/1 202707 200109
> > BM_DumpHashMap/10 213441 210569
> > BM_DumpHashMap/200 478641 472350
> > BM_DumpHashMap/500 980061 967102
> > BM_DumpHashMap/1000 1863835 1839575
> > BM_DumpHashMap/5k 8961836 8902540
> > BM_DumpHashMap/20k 69761497 69322756
> > BM_DumpHashMap/39k 187437830 186551111
> >
> > Fixes: 057996380a42 ("bpf: Add batch ops to all htab bpf map")
> > Cc: Yonghong Song <yhs@fb.com>
> > Signed-off-by: Brian Vazquez <brianvv@google.com>
>
> Thanks for the fix.
> Acked-by: Yonghong Song <yhs@fb.com>
Applied. Thanks
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops
2020-02-18 17:25 [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops Brian Vazquez
2020-02-18 21:23 ` Yonghong Song
@ 2020-02-20 2:25 ` kbuild test robot
2020-02-20 5:29 ` kbuild test robot
2 siblings, 0 replies; 5+ messages in thread
From: kbuild test robot @ 2020-02-20 2:25 UTC (permalink / raw)
To: kbuild-all
[-- Attachment #1: Type: text/plain, Size: 5055 bytes --]
Hi Brian,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on bpf/master]
[also build test WARNING on bpf-next/master v5.6-rc2 next-20200219]
[if your patch is applied to the wrong git tree, please drop us a note to help
improve the system. BTW, we also suggest to use '--base' option to specify the
base tree in git format-patch, please see https://stackoverflow.com/a/37406982]
url: https://github.com/0day-ci/linux/commits/Brian-Vazquez/bpf-Do-not-grab-the-bucket-spinlock-by-default-on-htab-batch-ops/20200220-073319
base: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf.git master
config: s390-defconfig (attached as .config)
compiler: s390-linux-gcc (GCC) 7.5.0
reproduce:
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
GCC_VERSION=7.5.0 make.cross ARCH=s390
If you fix the issue, kindly add following tag
Reported-by: kbuild test robot <lkp@intel.com>
Note: it may well be a FALSE warning. FWIW you are at least aware of it now.
http://gcc.gnu.org/wiki/Better_Uninitialized_Warnings
All warnings (new ones prefixed by >>):
In file included from include/linux/irqflags.h:16:0,
from arch/s390/include/asm/processor.h:41,
from arch/s390/include/asm/thread_info.h:27,
from include/linux/thread_info.h:38,
from arch/s390/include/asm/preempt.h:6,
from include/linux/preempt.h:78,
from include/linux/spinlock.h:51,
from include/linux/seqlock.h:36,
from include/linux/time.h:6,
from include/linux/ktime.h:24,
from include/linux/timer.h:6,
from include/linux/workqueue.h:9,
from include/linux/bpf.h:9,
from kernel//bpf/hashtab.c:5:
kernel//bpf/hashtab.c: In function '__htab_map_lookup_and_delete_batch':
>> arch/s390/include/asm/irqflags.h:64:12: warning: 'flags' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (flags & ARCH_IRQ_ENABLED)
^
kernel//bpf/hashtab.c:1262:16: note: 'flags' was declared here
unsigned long flags;
^~~~~
--
In file included from include/linux/irqflags.h:16:0,
from arch/s390/include/asm/processor.h:41,
from arch/s390/include/asm/thread_info.h:27,
from include/linux/thread_info.h:38,
from arch/s390/include/asm/preempt.h:6,
from include/linux/preempt.h:78,
from include/linux/spinlock.h:51,
from include/linux/seqlock.h:36,
from include/linux/time.h:6,
from include/linux/ktime.h:24,
from include/linux/timer.h:6,
from include/linux/workqueue.h:9,
from include/linux/bpf.h:9,
from kernel/bpf/hashtab.c:5:
kernel/bpf/hashtab.c: In function '__htab_map_lookup_and_delete_batch':
>> arch/s390/include/asm/irqflags.h:64:12: warning: 'flags' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (flags & ARCH_IRQ_ENABLED)
^
kernel/bpf/hashtab.c:1262:16: note: 'flags' was declared here
unsigned long flags;
^~~~~
vim +/flags +64 arch/s390/include/asm/irqflags.h
1f194a4c393103 include/asm-s390/irqflags.h Heiko Carstens 2006-07-03 59
204ee2c5643199 arch/s390/include/asm/irqflags.h Christian Borntraeger 2016-01-11 60 /* This only restores external and I/O interrupt state */
f433c4aec9999d arch/s390/include/asm/irqflags.h Steven Rostedt 2011-07-24 61 static inline notrace void arch_local_irq_restore(unsigned long flags)
df9ee29270c11d arch/s390/include/asm/irqflags.h David Howells 2010-10-07 62 {
204ee2c5643199 arch/s390/include/asm/irqflags.h Christian Borntraeger 2016-01-11 63 /* only disabled->disabled and disabled->enabled is valid */
204ee2c5643199 arch/s390/include/asm/irqflags.h Christian Borntraeger 2016-01-11 @64 if (flags & ARCH_IRQ_ENABLED)
204ee2c5643199 arch/s390/include/asm/irqflags.h Christian Borntraeger 2016-01-11 65 arch_local_irq_enable();
df9ee29270c11d arch/s390/include/asm/irqflags.h David Howells 2010-10-07 66 }
df9ee29270c11d arch/s390/include/asm/irqflags.h David Howells 2010-10-07 67
:::::: The code at line 64 was first introduced by commit
:::::: 204ee2c5643199a25181ec04ea645d00709c2a5a s390/irqflags: optimize irq restore
:::::: TO: Christian Borntraeger <borntraeger@de.ibm.com>
:::::: CC: Martin Schwidefsky <schwidefsky@de.ibm.com>
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
[-- Attachment #2: config.gz --]
[-- Type: application/gzip, Size: 19126 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops
2020-02-18 17:25 [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops Brian Vazquez
2020-02-18 21:23 ` Yonghong Song
2020-02-20 2:25 ` kbuild test robot
@ 2020-02-20 5:29 ` kbuild test robot
2 siblings, 0 replies; 5+ messages in thread
From: kbuild test robot @ 2020-02-20 5:29 UTC (permalink / raw)
To: kbuild-all
[-- Attachment #1: Type: text/plain, Size: 5522 bytes --]
Hi Brian,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on bpf/master]
[also build test WARNING on bpf-next/master v5.6-rc2 next-20200219]
[if your patch is applied to the wrong git tree, please drop us a note to help
improve the system. BTW, we also suggest to use '--base' option to specify the
base tree in git format-patch, please see https://stackoverflow.com/a/37406982]
url: https://github.com/0day-ci/linux/commits/Brian-Vazquez/bpf-Do-not-grab-the-bucket-spinlock-by-default-on-htab-batch-ops/20200220-073319
base: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf.git master
config: sh-randconfig-a001-20200219 (attached as .config)
compiler: sh4-linux-gcc (GCC) 7.5.0
reproduce:
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
GCC_VERSION=7.5.0 make.cross ARCH=sh
If you fix the issue, kindly add following tag
Reported-by: kbuild test robot <lkp@intel.com>
Note: it may well be a FALSE warning. FWIW you are at least aware of it now.
http://gcc.gnu.org/wiki/Better_Uninitialized_Warnings
All warnings (new ones prefixed by >>):
In file included from include/linux/spinlock.h:54:0,
from include/linux/seqlock.h:36,
from include/linux/time.h:6,
from include/linux/ktime.h:24,
from include/linux/timer.h:6,
from include/linux/workqueue.h:9,
from include/linux/bpf.h:9,
from kernel//bpf/hashtab.c:5:
kernel//bpf/hashtab.c: In function '__htab_map_lookup_and_delete_batch':
>> include/linux/irqflags.h:89:3: warning: 'flags' may be used uninitialized in this function [-Wmaybe-uninitialized]
arch_local_irq_restore(flags); \
^~~~~~~~~~~~~~~~~~~~~~
kernel//bpf/hashtab.c:1262:16: note: 'flags' was declared here
unsigned long flags;
^~~~~
--
In file included from include/linux/spinlock.h:54:0,
from include/linux/seqlock.h:36,
from include/linux/time.h:6,
from include/linux/ktime.h:24,
from include/linux/timer.h:6,
from include/linux/workqueue.h:9,
from include/linux/bpf.h:9,
from kernel/bpf/hashtab.c:5:
kernel/bpf/hashtab.c: In function '__htab_map_lookup_and_delete_batch':
>> include/linux/irqflags.h:89:3: warning: 'flags' may be used uninitialized in this function [-Wmaybe-uninitialized]
arch_local_irq_restore(flags); \
^~~~~~~~~~~~~~~~~~~~~~
kernel/bpf/hashtab.c:1262:16: note: 'flags' was declared here
unsigned long flags;
^~~~~
vim +/flags +89 include/linux/irqflags.h
81d68a96a39844 Steven Rostedt 2008-05-12 75
df9ee29270c11d David Howells 2010-10-07 76 /*
df9ee29270c11d David Howells 2010-10-07 77 * Wrap the arch provided IRQ routines to provide appropriate checks.
df9ee29270c11d David Howells 2010-10-07 78 */
df9ee29270c11d David Howells 2010-10-07 79 #define raw_local_irq_disable() arch_local_irq_disable()
df9ee29270c11d David Howells 2010-10-07 80 #define raw_local_irq_enable() arch_local_irq_enable()
df9ee29270c11d David Howells 2010-10-07 81 #define raw_local_irq_save(flags) \
df9ee29270c11d David Howells 2010-10-07 82 do { \
df9ee29270c11d David Howells 2010-10-07 83 typecheck(unsigned long, flags); \
df9ee29270c11d David Howells 2010-10-07 84 flags = arch_local_irq_save(); \
df9ee29270c11d David Howells 2010-10-07 85 } while (0)
df9ee29270c11d David Howells 2010-10-07 86 #define raw_local_irq_restore(flags) \
df9ee29270c11d David Howells 2010-10-07 87 do { \
df9ee29270c11d David Howells 2010-10-07 88 typecheck(unsigned long, flags); \
df9ee29270c11d David Howells 2010-10-07 @89 arch_local_irq_restore(flags); \
df9ee29270c11d David Howells 2010-10-07 90 } while (0)
df9ee29270c11d David Howells 2010-10-07 91 #define raw_local_save_flags(flags) \
df9ee29270c11d David Howells 2010-10-07 92 do { \
df9ee29270c11d David Howells 2010-10-07 93 typecheck(unsigned long, flags); \
df9ee29270c11d David Howells 2010-10-07 94 flags = arch_local_save_flags(); \
df9ee29270c11d David Howells 2010-10-07 95 } while (0)
df9ee29270c11d David Howells 2010-10-07 96 #define raw_irqs_disabled_flags(flags) \
df9ee29270c11d David Howells 2010-10-07 97 ({ \
df9ee29270c11d David Howells 2010-10-07 98 typecheck(unsigned long, flags); \
df9ee29270c11d David Howells 2010-10-07 99 arch_irqs_disabled_flags(flags); \
df9ee29270c11d David Howells 2010-10-07 100 })
df9ee29270c11d David Howells 2010-10-07 101 #define raw_irqs_disabled() (arch_irqs_disabled())
df9ee29270c11d David Howells 2010-10-07 102 #define raw_safe_halt() arch_safe_halt()
de30a2b355ea85 Ingo Molnar 2006-07-03 103
:::::: The code at line 89 was first introduced by commit
:::::: df9ee29270c11dba7d0fe0b83ce47a4d8e8d2101 Fix IRQ flag handling naming
:::::: TO: David Howells <dhowells@redhat.com>
:::::: CC: David Howells <dhowells@redhat.com>
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
[-- Attachment #2: config.gz --]
[-- Type: application/gzip, Size: 24775 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2020-02-20 5:29 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-02-18 17:25 [PATCH v2 bpf] bpf: Do not grab the bucket spinlock by default on htab batch ops Brian Vazquez
2020-02-18 21:23 ` Yonghong Song
2020-02-19 23:12 ` Alexei Starovoitov
2020-02-20 2:25 ` kbuild test robot
2020-02-20 5:29 ` kbuild test robot
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.