net: use cmpxchg instead of spinlock in ptr rings
Subsystems (2)
RFC PATCH 1/2 net: use cmpxchg instead of spinlock in ptr rings
(looks like my message didn't reach the netdev list, due to me sending from the wrong email, forwarded message again):
Quoted 17 lines · On Thu, 10 Nov 2016 20:44:08 -0800 John Fastabend <[email protected]>…
--- include/linux/ptr_ring_ll.h | 136 +++++++++++++++++++++++++++++++++++++++++++ include/linux/skb_array.h | 25 ++++++++ 2 files changed, 161 insertions(+) create mode 100644 include/linux/ptr_ring_ll.hinclude/linux/ptr_ring_ll.h new file +5
-0@@ -0,0 +1,136 @@ +/* +* Definitions for the 'struct ptr_ring_ll' datastructure. +* +* Author: +* John Fastabend <[email protected]>
[...]
Quoted 4 lines
+ *
+ * This is a limited-size FIFO maintaining pointers in FIFO order, with
+ * one CPU producing entries and another consuming entries from a FIFO.
+ * extended fromptr_ring_llto use cmpxchg over spin lock.
It sounds like this is Single Producer Single Consumer (SPSC) implementation, but your implementation actually is Multi Producer Multi Consumer (MPMC) capable.
The implementation looks a lot like my alf_queue[1] implementation:
[1] https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/include/linux/alf_queue.h
If the primary use-case is one CPU producing and another consuming, then the normal ptr_ring (skb_array) will actually be faster!
The reason is ptr_ring avoids bouncing a cache-line between the CPUs on every ring access. This is achieved by having the checks for full (__ptr_ring_full) and empty (__ptr_ring_empty) use the contents of the array (NULL value).
I actually implemented two micro-benchmarks to measure the difference
between skb_array[2] and alf_queue[3]:
[2] https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/lib/skb_array_parallel01.c
[3] https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/lib/alf_queue_parallel01.c
Quoted 5 lines
+ */
include/linux/ptr_ring_ll.h new file +4
-0+ +#ifndef _LINUX_PTR_RING_LL_H +#define _LINUX_PTR_RING_LL_H 1 +
[...]
include/linux/ptr_ring_ll.h
Quoted 13 lines
include/linux/ptr_ring_ll.h new file +13
-0+ +struct ptr_ring_ll { +u32 prod_size; +u32 prod_mask; +u32 prod_head; +u32 prod_tail; +u32 cons_size; +u32 cons_mask; +u32 cons_head; +u32 cons_tail; + +void **queue; +};
Your implementation doesn't even split the consumer and producer into different cachelines (which in practice doesn't help much due to how the empty/full checks are performed).
include/linux/ptr_ring_ll.h
Quoted 12 lines
include/linux/ptr_ring_ll.h new file +12
-0+ +/* Note: callers invoking this in a loop must use a compiler barrier, +* for example cpu_relax(). Callers must hold producer_lock. +*/ +static inline int __ptr_ring_ll_produce (struct ptr_ring_ll *r,void *ptr) +{ +u32 ret, head, tail, next, slots, mask; + + do { + head = READ_ONCE(r->prod_head); + mask = READ_ONCE(r->prod_mask); + tail = READ_ONCE(r->cons_tail);
Problem occur here, as the producer need to access/read the consumers tail, to determine if the queue is not already full (slots avail). Thus, the next "consumer-CPU" will see the cacheline in wrong state (Modified/Invalid or Shared).
Quoted 18 lines
include/linux/ptr_ring_ll.h new file +18
-0+ + slots = mask + tail - head; +if (slots <1 ) +return -ENOMEM ; + + next = head +1 ; + ret =cmpxchg (&r->prod_head, head, next); + }while (ret != head); + + r->queue[head & mask] = ptr; +smp_wmb (); + +while (r->prod_tail != head) +cpu_relax (); + + r->prod_tail = next; +return 0 ; +}
include/linux/ptr_ring_ll.h
Quoted 10 lines
include/linux/ptr_ring_ll.h new file +10
-0+ +static inline void *__ptr_ring_ll_consume (struct ptr_ring_ll *r) +{ +u32 ret, head, tail, next, slots, mask; +void *ptr; + + do { + head = READ_ONCE(r->cons_head); + mask = READ_ONCE(r->cons_mask); + tail = READ_ONCE(r->prod_tail);
Like wise the consumer is reading the producer tail (for the empty check).
Quoted 22 lines
include/linux/ptr_ring_ll.h new file +22
-0+ + slots = tail - head; +if (slots <1 ) +return ERR_PTR (-ENOMEM ); + + next = head +1 ; + ret =cmpxchg (&r->cons_head, head, next); + }while (ret != head); + + ptr = r->queue[head & mask]; +smp_rmb (); + +while (r->cons_tail != head) +cpu_relax (); + + r->cons_tail = next; +return ptr; +} + +static inline void **__ptr_ring_ll_init_queue_alloc (int size,gfp_t gfp) +{ +return kzalloc (ALIGN (size *sizeof (void *),SMP_CACHE_BYTES ), gfp);
include/linux/ptr_ring_ll.h
Quoted 10 lines
include/linux/ptr_ring_ll.h new file +10
-0+} + +static inline int ptr_ring_ll_init (struct ptr_ring_ll *r,int size,gfp_t gfp) +{ + r->queue =__ptr_ring_init_queue_alloc (size, gfp); +if (!r->queue) +return -ENOMEM ; + + r->prod_size = r->cons_size = size; + r->prod_mask = r->cons_mask = size -1 ;
Shouldn't we have some check like is_power_of_2(size), as this code looks like it depend on this.
Quoted 6 lines
include/linux/ptr_ring_ll.h new file +6
-0+ r->prod_tail = r->prod_head =0 ; + r->cons_tail = r->prod_tail =0 ; + +return 0 ; +} +
[...]
Quoted 5 lines
include/linux/ptr_ring_ll.h new file +1
-0+#endif /* _LINUX_PTR_RING_LL_H */ include/linux/skb_array.h +0
-0
[...]
Quoted 6 lines
include/linux/skb_array.h +5
-0+static inline int skb_array_ll_produce (struct skb_array_ll *a,struct sk_buff *skb) +{ +return __ptr_ring_ll_produce (&a->ring, skb); +} +
[...]
include/linux/skb_array.h
Quoted 6 lines
include/linux/skb_array.h +5
-0+static inline struct sk_buff *skb_array_ll_consume (struct skb_array_ll *a) +{ +return __ptr_ring_ll_consume (&a->ring); +} +
Note in the Multi Producer Multi Consumer (MPMC) use-case this type of queue can be faster than normal ptr_ring. And in patch2 you implement bulking, which is where the real benefit shows (in the MPMC case) for this kind of queue.
What I would really like to see is a lock-free (locked cmpxchg) queue implementation, what like ptr_ring use the array as empty/full check, and still (somehow) support bulking.
Signature · 5 lines
Best regards, Jesper Dangaard Brouer MSc.CS, Principal Kernel Engineer at Red Hat Author of http://www.iptv-analyzer.org LinkedIn: http://www.linkedin.com/in/brouer
Quoted 3 lines · Jesper Dangaard Brouer
What I would really like to see is a lock-free (locked cmpxchg) queue implementation, what like
ptr_ringuse the array as empty/full check, and still (somehow) support bulking.
I think lock-free is overrated for this use-case - we hold the lock for such a short amount of time.
I think what we want is just a simpler spinlock - one that's faster than qlock for use-cases that are unfair anyway, like this one where even if you get the lock in a fair way, FIFO might be full and you won't be able to queue.
Or find an API to add to FIFO in a fair way.
Signature · 1 line
MST
Quoted 24 lines · Jesper Dangaard Brouer
(looks like my message didn't reach the netdev list, due to me sending from the wrong email, forwarded message again):
Quoted 17 lines · On Thu, 10 Nov 2016 20:44:08 -0800 John Fastabend <[email protected]>…
--- include/linux/ptr_ring_ll.h | 136 +++++++++++++++++++++++++++++++++++++++++++ include/linux/skb_array.h | 25 ++++++++ 2 files changed, 161 insertions(+) create mode 100644 include/linux/ptr_ring_ll.hinclude/linux/ptr_ring_ll.h new file +5
-0@@ -0,0 +1,136 @@ +/* +* Definitions for the 'struct ptr_ring_ll' datastructure. +* +* Author: +* John Fastabend <[email protected]> [...]
Quoted 8 lines
Quoted 4 lines
+ *
+ * This is a limited-size FIFO maintaining pointers in FIFO order, with
+ * one CPU producing entries and another consuming entries from a FIFO.
+ * extended fromptr_ring_llto use cmpxchg over spin lock.It sounds like this is Single Producer Single Consumer (SPSC) implementation, but your implementation actually is Multi Producer Multi Consumer (MPMC) capable.
Correct qdisc requires a MPMC to handle all the OOO cases.
Quoted 4 lines
The implementation looks a lot like my alf_queue[1] implementation:
[1] https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/include/linux/alf_queue.h
Sure, I was using that implementation originally.
Quoted 8 lines
If the primary use-case is one CPU producing and another consuming, then the normal
ptr_ring(skb_array) will actually be faster!The reason is
ptr_ringavoids bouncing a cache-line between the CPUs on every ring access. This is achieved by having the checks for full (__ptr_ring_full) and empty (__ptr_ring_empty) use the contents of the array (NULL value).
Quoted 5 lines
I actually implemented two micro-benchmarks to measure the difference
between skb_array[2] and alf_queue[3]:
[2] https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/lib/skb_array_parallel01.c
[3] https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/lib/alf_queue_parallel01.c
But :) this doesn't jive with my experiments where this implementation was actually giving better numbers with pktgen over pfifo_fast even in the SPSC case. I'll rerun metrics later this week its possible there was some other issue causing the difference I guess.
As I noted in Michael's email though really I need to fix a bug in my qdisc code and submit it before I worry too much about this optimization.
Quoted 16 lines
Quoted 6 lines
+ */
include/linux/ptr_ring_ll.h new file +4
-0+ +#ifndef _LINUX_PTR_RING_LL_H +#define _LINUX_PTR_RING_LL_H 1 +[...]
Quoted 9 lines
include/linux/ptr_ring_ll.h new file +9
-0+ +struct ptr_ring_ll { +u32 prod_size; +u32 prod_mask; +u32 prod_head; +u32 prod_tail; +u32 cons_size; +u32 cons_mask; +u32 cons_head;
Quoted 8 lines
include/linux/ptr_ring_ll.h
Quoted 4 lines
include/linux/ptr_ring_ll.h new file +4
-0+u32 cons_tail; + +void **queue; +};Your implementation doesn't even split the consumer and producer into different cachelines (which in practice doesn't help much due to how the empty/full checks are performed).
Its was just a implementation to get the qdisc patches off the ground. I expected to follow up with patches to optimize the implementation.
[...]
Quoted 12 lines
include/linux/ptr_ring_ll.h
Quoted 8 lines
include/linux/ptr_ring_ll.h new file +8
-0+static inline int ptr_ring_ll_init (struct ptr_ring_ll *r,int size,gfp_t gfp) +{ + r->queue =__ptr_ring_init_queue_alloc (size, gfp); +if (!r->queue) +return -ENOMEM ; + + r->prod_size = r->cons_size = size; + r->prod_mask = r->cons_mask = size -1 ;Shouldn't we have some check like
is_power_of_2(size), as this code looks like it depend on this.
Sure it is required. I was just ensuring callers do it correctly.
Quoted 6 lines
Quoted 6 lines
include/linux/ptr_ring_ll.h new file +6
-0+ r->prod_tail = r->prod_head =0 ; + r->cons_tail = r->prod_tail =0 ; + +return 0 ; +} +
[...]
Quoted 12 lines
include/linux/ptr_ring_ll.h
Quoted 6 lines
include/linux/ptr_ring_ll.h new file +5
-0+static inline struct sk_buff *skb_array_ll_consume (struct skb_array_ll *a) +{ +return __ptr_ring_ll_consume (&a->ring); +} +Note in the Multi Producer Multi Consumer (MPMC) use-case this type of queue can be faster than normal
ptr_ring. And in patch2 you implement bulking, which is where the real benefit shows (in the MPMC case) for this kind of queue.
Quoted 4 lines
What I would really like to see is a lock-free (locked cmpxchg) queue implementation, what like
ptr_ringuse the array as empty/full check, and still (somehow) support bulking.
OK perhaps worth experimenting with after if I can _finally_ get the qdisc series in.
.John