ptr_ring: linked list fallback

So pointer rings work fine, but they have a problem: make them too small and not enough entries fit. Make them too large and you start flushing your cache and running out of memory.

This is a new idea of mine: a ring backed by a linked list. Once you run out of ring entries, instead of a drop you fall back on a list with a common lock.

Should work well for the case where the ring is typically sized correctly, but will help address the fact that some user try to set e.g. tx queue length to 1000000.

In other words, the idea is that if a user sets a really huge TX queue length, we allocate a ptr_ring which is smaller, and use the backup linked list when necessary to provide the requested TX queue length legitimately.

My hope this will move us closer to direction where e.g. fw codel can use ptr rings without locking at all. The API is still very rough, and I really need to take a hard look at lock nesting.

Compiled only, sending for early feedback/flames.

Signed-off-by Michael S. Tsirkin <[email protected]>

---

changes from v1:
- added clarifications by DaveM in the commit log
- build fixes

  include/linux/ptr_ring.h | 64 +++++++++++++++++++++++++++++++++++++++++++++---
  1 file changed, 61 insertions(+), 3 deletions(-)

include/linux/ptr_ring.h +0 -0

index d72b2e7..8aa8882 100644

include/linux/ptr_ring.h +16 -3

+
  struct ptr_ring {
  	int producer ____cacheline_aligned_in_smp;
  	spinlock_t producer_lock;
  	int consumer_head ____cacheline_aligned_in_smp; /* next valid entry */
  	int consumer_tail; /* next entry to invalidate */
+	struct plist *consumer_list;
  	spinlock_t consumer_lock;
  	/* Shared consumer/producer data */
  	/* Read-only by both the producer and the consumer */

@@ -120,10 +127,40 @@ static inline int __ptr_ring_produce(struct ptr_ring *r, void *ptr)
  }
 
  /*
- * Note: resize (below) nests producer lock within consumer lock, so if you
- * consume in interrupt or BH context, you must disable interrupts/BH when
- * calling this.
+ * Note: resize API with the _fallback should be used when calling this.
   */
+static inline int ptr_ring_produce_fallback(struct ptr_ring *r, void *ptr)
+{
+	int ret;
+	unsigned long flags;
+	struct plist *p = ptr;
+
+	p->next = NULL;
+	p->last = p;
+
+	spin_lock_irqsave(&r->producer_lock, flags);
+	ret = __ptr_ring_produce(r, ptr);
+	if (ret) {
+		spin_lock(&r->consumer_lock);

include/linux/ptr_ring.h +30 -0

+		}
+		spin_unlock(&r->consumer_lock);
+	}
+
+	spin_unlock_irqrestore(&r->producer_lock, flags);
+
+	return ret;
+}
+
  static inline int ptr_ring_produce(struct ptr_ring *r, void *ptr)
  {
  	int ret;

@@ -135,6 +172,7 @@ static inline int ptr_ring_produce(struct ptr_ring *r, void *ptr)
  	return ret;
  }
 
+
  static inline int ptr_ring_produce_irq(struct ptr_ring *r, void *ptr)
  {
  	int ret;

@@ -359,6 +397,26 @@ static inline void *ptr_ring_consume_bh(struct ptr_ring *r)
  	return ptr;
  }
 
+static inline void *ptr_ring_consume_fallback(struct ptr_ring *r)
+{
+	unsigned long flags;
+	struct plist *ptr;
+
+	spin_lock_irqsave(&r->consumer_lock, flags);
+	if (r->consumer_list) {
+		ptr = r->consumer_list;
+		r->consumer_list = ptr->next;
+	} else {
+		ptr = __ptr_ring_consume(r);
+		if (ptr) {
+			r->consumer_list = ptr->next;
+		}
+	}
+	spin_unlock_irqrestore(&r->consumer_lock, flags);
+
+	return ptr;
+}
+
  static inline int ptr_ring_consume_batched(struct ptr_ring *r,
  					   void **array, int n)
  {

Quoted 33 lines · Michael S. Tsirkin

So pointer rings work fine, but they have a problem: make them too small and not enough entries fit. Make them too large and you start flushing your cache and running out of memory.

This is a new idea of mine: a ring backed by a linked list. Once you run out of ring entries, instead of a drop you fall back on a list with a common lock.

Should work well for the case where the ring is typically sized correctly, but will help address the fact that some user try to set e.g. tx queue length to 1000000.

In other words, the idea is that if a user sets a really huge TX queue length, we allocate a ptr_ring which is smaller, and use the backup linked list when necessary to provide the requested TX queue length legitimately.

My hope this will move us closer to direction where e.g. fw codel can use ptr rings without locking at all. The API is still very rough, and I really need to take a hard look at lock nesting.

Compiled only, sending for early feedback/flames.

Signed-off-by Michael S. Tsirkin <[email protected]>

---

changes from v1:
- added clarifications by DaveM in the commit log
- build fixes

  include/linux/ptr_ring.h | 64 +++++++++++++++++++++++++++++++++++++++++++++---
  1 file changed, 61 insertions(+), 3 deletions(-)

include/linux/ptr_ring.h line 37

Quoted 12 lines

include/linux/ptr_ring.h +5 -0

index d72b2e7..8aa8882 100644
@@ -31,11 +31,18 @@
  #include <asm/errno.h>
  #endif
+/* entries must start with the following structure */
+struct plist {
+	struct plist *next;
+	struct plist *last; /* only valid in the 1st entry */
+};

So I wonder whether or not it's better to do this in e.g skb_array implementation. Then it can use its own prev/next field.

Quoted 35 lines

include/linux/ptr_ring.h +20 -3

+
  struct ptr_ring {
  	int producer ____cacheline_aligned_in_smp;
  	spinlock_t producer_lock;
  	int consumer_head ____cacheline_aligned_in_smp; /* next valid entry */
  	int consumer_tail; /* next entry to invalidate */
+	struct plist *consumer_list;
  	spinlock_t consumer_lock;
  	/* Shared consumer/producer data */
  	/* Read-only by both the producer and the consumer */

@@ -120,10 +127,40 @@ static inline int __ptr_ring_produce(struct ptr_ring *r, void *ptr)
  }
  /*
- * Note: resize (below) nests producer lock within consumer lock, so if you
- * consume in interrupt or BH context, you must disable interrupts/BH when
- * calling this.
+ * Note: resize API with the _fallback should be used when calling this.
   */
+static inline int ptr_ring_produce_fallback(struct ptr_ring *r, void *ptr)
+{
+	int ret;
+	unsigned long flags;
+	struct plist *p = ptr;
+
+	p->next = NULL;
+	p->last = p;
+
+	spin_lock_irqsave(&r->producer_lock, flags);
+	ret = __ptr_ring_produce(r, ptr);
+	if (ret) {
+		spin_lock(&r->consumer_lock);
+		ret = __ptr_ring_produce(r, ptr);
+		if (ret) {
+			int producer = r->producer ? r->producer - 1 :
+				r->size - 1;

include/linux/ptr_ring.h static inline int __ptr_ring_produce(struct ptr_ring *r, void *ptr) · line 154

Quoted 6 lines

include/linux/ptr_ring.h +6 -0

+			struct plist *first = r->queue[producer];
+
+			BUG_ON(!first);
+
+			first->last->next = p;
+			first->last = p;

I believe we still need a limitation on the total size of the queue.

Thanks

Quoted 45 lines

include/linux/ptr_ring.h +30 -0

+		}
+		spin_unlock(&r->consumer_lock);
+	}
+
+	spin_unlock_irqrestore(&r->producer_lock, flags);
+
+	return ret;
+}
+
  static inline int ptr_ring_produce(struct ptr_ring *r, void *ptr)
  {
  	int ret;

@@ -135,6 +172,7 @@ static inline int ptr_ring_produce(struct ptr_ring *r, void *ptr)
  	return ret;
  }
+
  static inline int ptr_ring_produce_irq(struct ptr_ring *r, void *ptr)
  {
  	int ret;

@@ -359,6 +397,26 @@ static inline void *ptr_ring_consume_bh(struct ptr_ring *r)
  	return ptr;
  }
+static inline void *ptr_ring_consume_fallback(struct ptr_ring *r)
+{
+	unsigned long flags;
+	struct plist *ptr;
+
+	spin_lock_irqsave(&r->consumer_lock, flags);
+	if (r->consumer_list) {
+		ptr = r->consumer_list;
+		r->consumer_list = ptr->next;
+	} else {
+		ptr = __ptr_ring_consume(r);
+		if (ptr) {
+			r->consumer_list = ptr->next;
+		}
+	}
+	spin_unlock_irqrestore(&r->consumer_lock, flags);
+
+	return ptr;
+}
+
  static inline int ptr_ring_consume_batched(struct ptr_ring *r,
  					   void **array, int n)
  {

Quoted 34 lines · Jason Wang

Quoted 33 lines · Michael S. Tsirkin

So pointer rings work fine, but they have a problem: make them too small and not enough entries fit. Make them too large and you start flushing your cache and running out of memory.

This is a new idea of mine: a ring backed by a linked list. Once you run out of ring entries, instead of a drop you fall back on a list with a common lock.

Should work well for the case where the ring is typically sized correctly, but will help address the fact that some user try to set e.g. tx queue length to 1000000.

In other words, the idea is that if a user sets a really huge TX queue length, we allocate a ptr_ring which is smaller, and use the backup linked list when necessary to provide the requested TX queue length legitimately.

My hope this will move us closer to direction where e.g. fw codel can use ptr rings without locking at all. The API is still very rough, and I really need to take a hard look at lock nesting.

Compiled only, sending for early feedback/flames.

Signed-off-by Michael S. Tsirkin<[email protected]>

---

changes from v1:
- added clarifications by DaveM in the commit log
- build fixes

   include/linux/ptr_ring.h | 64 +++++++++++++++++++++++++++++++++++++++++++++---
   1 file changed, 61 insertions(+), 3 deletions(-)

Quoted 14 lines

include/linux/ptr_ring.h line 37

Quoted 12 lines

include/linux/ptr_ring.h +5 -0

index d72b2e7..8aa8882 100644
@@ -31,11 +31,18 @@
   #include <asm/errno.h>
   #endif
+/* entries must start with the following structure */
+struct plist {
+	struct plist *next;
+	struct plist *last; /* only valid in the 1st entry */
+};

So I wonder whether or not it's better to do this in e.g skb_array implementation. Then it can use its own prev/next field.

XDP uses ptr ring directly, doesn't it?

Quoted 49 lines · Michael S. Tsirkin

Quoted 48 lines · Jason Wang

Quoted 38 lines · Michael S. Tsirkin

So pointer rings work fine, but they have a problem: make them too small and not enough entries fit. Make them too large and you start flushing your cache and running out of memory.

This is a new idea of mine: a ring backed by a linked list. Once you run out of ring entries, instead of a drop you fall back on a list with a common lock.

Should work well for the case where the ring is typically sized correctly, but will help address the fact that some user try to set e.g. tx queue length to 1000000.

In other words, the idea is that if a user sets a really huge TX queue length, we allocate a ptr_ring which is smaller, and use the backup linked list when necessary to provide the requested TX queue length legitimately.

My hope this will move us closer to direction where e.g. fw codel can use ptr rings without locking at all. The API is still very rough, and I really need to take a hard look at lock nesting.

Compiled only, sending for early feedback/flames.

Signed-off-by Michael S. Tsirkin<[email protected]>

---

changes from v1:
- added clarifications by DaveM in the commit log
- build fixes

   include/linux/ptr_ring.h | 64 +++++++++++++++++++++++++++++++++++++++++++++---
   1 file changed, 61 insertions(+), 3 deletions(-)

include/linux/ptr_ring.h +0 -0

index d72b2e7..8aa8882 100644

include/linux/ptr_ring.h line 37

Quoted 7 lines

include/linux/ptr_ring.h +5 -0

@@ -31,11 +31,18 @@
   #include <asm/errno.h>
   #endif
+/* entries must start with the following structure */
+struct plist {
+	struct plist *next;
+	struct plist *last; /* only valid in the 1st entry */
+};

So I wonder whether or not it's better to do this in e.g skb_array implementation. Then it can use its own prev/next field.

Quoted 2 lines

XDP uses ptr ring directly, doesn't it?

Well I believe the main user for this is qdisc, which use skb array. And we can not use what implemented in this patch directly for sk_buff without some changes on the data structure.

For XDP, we need to embed plist in struct xdp_buff too,

so it looks to me
that the better approach is to have separated function for ptr ring and skb array.

Thanks

Quoted 51 lines · Jason Wang

Quoted 49 lines · Michael S. Tsirkin

Quoted 48 lines · Jason Wang

Quoted 38 lines · Michael S. Tsirkin

So pointer rings work fine, but they have a problem: make them too small and not enough entries fit. Make them too large and you start flushing your cache and running out of memory.

This is a new idea of mine: a ring backed by a linked list. Once you run out of ring entries, instead of a drop you fall back on a list with a common lock.

Should work well for the case where the ring is typically sized correctly, but will help address the fact that some user try to set e.g. tx queue length to 1000000.

In other words, the idea is that if a user sets a really huge TX queue length, we allocate a ptr_ring which is smaller, and use the backup linked list when necessary to provide the requested TX queue length legitimately.

My hope this will move us closer to direction where e.g. fw codel can use ptr rings without locking at all. The API is still very rough, and I really need to take a hard look at lock nesting.

Compiled only, sending for early feedback/flames.

Signed-off-by Michael S. Tsirkin<[email protected]>

---

changes from v1:
- added clarifications by DaveM in the commit log
- build fixes

    include/linux/ptr_ring.h | 64 +++++++++++++++++++++++++++++++++++++++++++++---
    1 file changed, 61 insertions(+), 3 deletions(-)

include/linux/ptr_ring.h +0 -0

index d72b2e7..8aa8882 100644

include/linux/ptr_ring.h line 37

Quoted 7 lines

include/linux/ptr_ring.h +5 -0

@@ -31,11 +31,18 @@
    #include <asm/errno.h>
    #endif
+/* entries must start with the following structure */
+struct plist {
+	struct plist *next;
+	struct plist *last; /* only valid in the 1st entry */
+};

So I wonder whether or not it's better to do this in e.g skb_array implementation. Then it can use its own prev/next field.

Quoted 5 lines

Quoted 2 lines

XDP uses ptr ring directly, doesn't it?

Well I believe the main user for this is qdisc, which use skb array. And we can not use what implemented in this patch directly for sk_buff without some changes on the data structure.

Why not? skb has next and prev pointers at 1st two fields:

struct sk_buff {
         union {
                 struct {
                         /* These two members must be first. */
                         struct sk_buff          *next;
                         struct sk_buff          *prev;

...
}

so it's just a question of casting to struct plist.

Or we can add plist to a union:

struct sk_buff {
         union {
                 struct {
                         /* These two members must be first. */
                         struct sk_buff          *next;
                         struct sk_buff          *prev;
                         
                         union {
                                 struct net_device       *dev;
                                 /* Some protocols might use this space to store information,
                                  * while device pointer would be NULL.
                                  * UDP receive path is one user.
                                  */
                                 unsigned long           dev_scratch;
                         };
                 };
                 struct rb_node  rbnode; /* used in netem & tcp stack */

Quoted 2 lines

For XDP, we need to embed plist in struct xdp_buff too,

Right - that's pretty straightforward, isn't it?

Quoted 5 lines

so it looks to me
that the better approach is to have separated function for ptr ring and skb array.

Thanks

Quoted 14 lines

Quoted 3 lines

Well I believe the main user for this is qdisc, which use skb array. And we can not use what implemented in this patch directly for sk_buff without some changes on the data structure.

Why not? skb has next and prev pointers at 1st two fields:

struct sk_buff {
         union {
                 struct {
                         /* These two members must be first. */ struct sk_buff          *next; struct sk_buff          *prev;
...
}

Quoted 1 line

so it's just a question of casting to struct plist.

Well, then the casting can only be done in skb_array implementation?

Quoted 16 lines · Jason Wang

Quoted 16 lines

Quoted 5 lines

Well I believe the main user for this is qdisc, which use skb array. And we
can not use what implemented in this patch directly for sk_buff without some
changes on the data structure.

Why not? skb has next and prev pointers at 1st two fields:

struct sk_buff {
         union {
                 struct {
                         /* These two members must be first. */ struct sk_buff          *next; struct sk_buff          *prev;
...
}

Quoted 3 lines

Quoted 1 line

so it's just a question of casting to struct plist.

Well, then the casting can only be done in skb_array implementation?

Ok, could be done in ptr ring. But still looks tricky, because of the different meaning of prev and last.

Thanks

Quoted 68 lines · Michael S. Tsirkin

Quoted 51 lines · Jason Wang

Quoted 49 lines · Michael S. Tsirkin

Quoted 48 lines · Jason Wang

Quoted 38 lines · Michael S. Tsirkin

So pointer rings work fine, but they have a problem: make them too small and not enough entries fit. Make them too large and you start flushing your cache and running out of memory.

This is a new idea of mine: a ring backed by a linked list. Once you run out of ring entries, instead of a drop you fall back on a list with a common lock.

Should work well for the case where the ring is typically sized correctly, but will help address the fact that some user try to set e.g. tx queue length to 1000000.

In other words, the idea is that if a user sets a really huge TX queue length, we allocate a ptr_ring which is smaller, and use the backup linked list when necessary to provide the requested TX queue length legitimately.

My hope this will move us closer to direction where e.g. fw codel can use ptr rings without locking at all. The API is still very rough, and I really need to take a hard look at lock nesting.

Compiled only, sending for early feedback/flames.

Signed-off-by Michael S. Tsirkin<[email protected]>

---

changes from v1:
- added clarifications by DaveM in the commit log
- build fixes

    include/linux/ptr_ring.h | 64 +++++++++++++++++++++++++++++++++++++++++++++---
    1 file changed, 61 insertions(+), 3 deletions(-)

include/linux/ptr_ring.h +0 -0

index d72b2e7..8aa8882 100644

include/linux/ptr_ring.h line 37

Quoted 7 lines

include/linux/ptr_ring.h +5 -0

@@ -31,11 +31,18 @@
    #include <asm/errno.h>
    #endif
+/* entries must start with the following structure */
+struct plist {
+	struct plist *next;
+	struct plist *last; /* only valid in the 1st entry */
+};

So I wonder whether or not it's better to do this in e.g skb_array implementation. Then it can use its own prev/next field.

Quoted 5 lines

Quoted 2 lines

XDP uses ptr ring directly, doesn't it?

Well I believe the main user for this is qdisc, which use skb array. And we can not use what implemented in this patch directly for sk_buff without some changes on the data structure.

Why not? skb has next and prev pointers at 1st two fields:

struct sk_buff {
         union {
                 struct {
                         /* These two members must be first. */
                         struct sk_buff          *next;
                         struct sk_buff          *prev;

...
}

Quoted 1 line

so it's just a question of casting to struct plist.

Well, then the casting can only be done in skb_array implementation?

Quoted 21 lines

Or we can add plist to a union:

struct sk_buff {
         union {
                 struct {
                         /* These two members must be first. */
                         struct sk_buff          *next;
                         struct sk_buff          *prev;
                         union {
                                 struct net_device       *dev;
                                 /* Some protocols might use this space to store information,
                                  * while device pointer would be NULL.
                                  * UDP receive path is one user.
                                  */
                                 unsigned long           dev_scratch;
                         };
                 };
                 struct rb_node  rbnode; /* used in netem & tcp stack */

Review

Quoted 2 lines

(quoted diff) +1 -0

+		struct plist plist; /* For use with ptr_ring */
         };

This look ok.

Quoted 1 line

Quoted 2 lines

Quoted 1 line

For XDP, we need to embed plist in struct xdp_buff too,

Right - that's pretty straightforward, isn't it?

Yes, it's not clear to me this is really needed for XDP consider the lock contention it brings.

Thanks

Quoted 5 lines

Quoted 5 lines

so it looks to me
that the better approach is to have separated function for ptr ring and skb array.

Thanks

Quoted 24 lines

Quoted 20 lines

Or we can add plist to a union:

struct sk_buff {
          union {
                  struct {
                          /* These two members must be first. */
                          struct sk_buff          *next;
                          struct sk_buff          *prev;
                          union {
                                  struct net_device       *dev;
                                  /* Some protocols might use this space to store information,
                                   * while device pointer would be NULL.
                                   * UDP receive path is one user.
                                   */
                                  unsigned long           dev_scratch;
                          };
                  };
                  struct rb_node  rbnode; /* used in netem & tcp stack */

Review

Quoted 2 lines

(quoted diff) +1 -0

+		struct plist plist; /* For use with ptr_ring */
          };

This look ok.

Quoted 6 lines

Quoted 2 lines

Quoted 1 line

For XDP, we need to embed plist in struct xdp_buff too,

Right - that's pretty straightforward, isn't it?

Yes, it's not clear to me this is really needed for XDP consider the lock contention it brings.

Thanks

The contention is only when the ring overflows into the list though.

Quoted 30 lines · Michael S. Tsirkin

Quoted 30 lines

Quoted 20 lines

Or we can add plist to a union:

struct sk_buff {
          union {
                  struct {
                          /* These two members must be first. */
                          struct sk_buff          *next;
                          struct sk_buff          *prev;
                          union {
                                  struct net_device       *dev;
                                  /* Some protocols might use this space to store information,
                                   * while device pointer would be NULL.
                                   * UDP receive path is one user.
                                   */
                                  unsigned long           dev_scratch;
                          };
                  };
                  struct rb_node  rbnode; /* used in netem & tcp stack */

Review

Quoted 2 lines

(quoted diff) +1 -0

+		struct plist plist; /* For use with ptr_ring */
          };

This look ok.

Quoted 2 lines

Quoted 1 line

For XDP, we need to embed plist in struct xdp_buff too,

Right - that's pretty straightforward, isn't it?

Yes, it's not clear to me this is really needed for XDP consider the lock contention it brings.

Thanks

Quoted 2 lines

The contention is only when the ring overflows into the list though.

Right, but there's usually a mismatch of speed between producer and consumer. In case of a fast producer, we may get this contention very frequently.

Thanks

Quoted 38 lines · Jason Wang

Quoted 24 lines · Michael S. Tsirkin

Quoted 24 lines

Quoted 20 lines

Or we can add plist to a union:

struct sk_buff {
           union {
                   struct {
                           /* These two members must be first. */
                           struct sk_buff          *next;
                           struct sk_buff          *prev;
                           union {
                                   struct net_device       *dev;
                                   /* Some protocols might use this space to store information,
                                    * while device pointer would be NULL.
                                    * UDP receive path is one user.
                                    */
                                   unsigned long           dev_scratch;
                           };
                   };
                   struct rb_node  rbnode; /* used in netem & tcp stack */

Review

Quoted 2 lines

(quoted diff) +1 -0

+		struct plist plist; /* For use with ptr_ring */
           };

This look ok.

Quoted 8 lines

Quoted 6 lines

Quoted 2 lines

Quoted 1 line

For XDP, we need to embed plist in struct xdp_buff too,

Right - that's pretty straightforward, isn't it?

Yes, it's not clear to me this is really needed for XDP consider the lock contention it brings.

Thanks

The contention is only when the ring overflows into the list though.

Right, but there's usually a mismatch of speed between producer and consumer. In case of a fast producer, we may get this contention very frequently.

Quoted 1 line

Thanks

This is not true in my experiments. In my experiments, ring size of 4k bytes is enough to see packet drops in single %s of cases.

To you have workloads where rings are full most of the time?

One other nice side effect of this patch is that instead of dropping packets quickly it slows down producer to match consumer speeds.

IOW, it can go either way in theory, we will need to test and see the effect.

Quoted 39 lines · Michael S. Tsirkin

Quoted 38 lines · Jason Wang

Quoted 24 lines · Michael S. Tsirkin

Quoted 24 lines

Quoted 20 lines

Or we can add plist to a union:

struct sk_buff {
           union {
                   struct {
                           /* These two members must be first. */
                           struct sk_buff          *next;
                           struct sk_buff          *prev;
                           union {
                                   struct net_device       *dev;
                                   /* Some protocols might use this space to store information,
                                    * while device pointer would be NULL.
                                    * UDP receive path is one user.
                                    */
                                   unsigned long           dev_scratch;
                           };
                   };
                   struct rb_node  rbnode; /* used in netem & tcp stack */

Review

Quoted 2 lines

(quoted diff) +1 -0

+		struct plist plist; /* For use with ptr_ring */
           };

This look ok.

Quoted 8 lines

Quoted 6 lines

Quoted 2 lines

Quoted 1 line

For XDP, we need to embed plist in struct xdp_buff too,

Right - that's pretty straightforward, isn't it?

Yes, it's not clear to me this is really needed for XDP consider the lock contention it brings.

Thanks

The contention is only when the ring overflows into the list though.

Right, but there's usually a mismatch of speed between producer and consumer. In case of a fast producer, we may get this contention very frequently.

Quoted 5 lines

Quoted 1 line

Thanks

This is not true in my experiments. In my experiments, ring size of 4k bytes is enough to see packet drops in single %s of cases.

To you have workloads where rings are full most of the time?

E.g using xdp_redirect to redirect packets from ixgbe to tap. In my test, ixgeb can produce ~8Mpps. But vhost can only consume ~3.5Mpps.

Quoted 3 lines

One other nice side effect of this patch is that instead of dropping packets quickly it slows down producer to match consumer speeds.

In some case, producer may not want to be slowed down, e.g in devmap which can redirect packets into several different interfaces.

Quoted 2 lines

IOW, it can go either way in theory, we will need to test and see the effect.

Yes.

Thanks

Quoted 41 lines · Jason Wang

Quoted 39 lines · Michael S. Tsirkin

Quoted 38 lines · Jason Wang

Quoted 24 lines · Michael S. Tsirkin

Quoted 24 lines

Quoted 20 lines

Or we can add plist to a union:

struct sk_buff {
            union {
                    struct {
                            /* These two members must be first. */
                            struct sk_buff          *next;
                            struct sk_buff          *prev;
                            union {
                                    struct net_device       *dev;
                                    /* Some protocols might use this space to store information,
                                     * while device pointer would be NULL.
                                     * UDP receive path is one user.
                                     */
                                    unsigned long           dev_scratch;
                            };
                    };
                    struct rb_node  rbnode; /* used in netem & tcp stack */

Review

Quoted 2 lines

(quoted diff) +1 -0

+		struct plist plist; /* For use with ptr_ring */
            };

This look ok.

Quoted 8 lines

Quoted 6 lines

Quoted 2 lines

Quoted 1 line

For XDP, we need to embed plist in struct xdp_buff too,

Right - that's pretty straightforward, isn't it?

Yes, it's not clear to me this is really needed for XDP consider the lock contention it brings.

Thanks

The contention is only when the ring overflows into the list though.

Right, but there's usually a mismatch of speed between producer and consumer. In case of a fast producer, we may get this contention very frequently.

Thanks

Quoted 6 lines

Quoted 4 lines

This is not true in my experiments. In my experiments, ring size of 4k bytes is enough to see packet drops in single %s of cases.

To you have workloads where rings are full most of the time?

E.g using xdp_redirect to redirect packets from ixgbe to tap. In my test, ixgeb can produce ~8Mpps. But vhost can only consume ~3.5Mpps.

Then you are better off just using a small ring and dropping packets early, right?

Quoted 9 lines

Quoted 2 lines

One other nice side effect of this patch is that instead of dropping packets quickly it slows down producer to match consumer speeds.

In some case, producer may not want to be slowed down, e.g in devmap which can redirect packets into several different interfaces.

Quoted 2 lines

IOW, it can go either way in theory, we will need to test and see the effect.

Yes.

Thanks

So pointer rings work fine, but they have a problem: make them too small and not enough entries fit. Make them too large and you start flushing your cache and running out of memory.

This is a new idea of mine: a ring backed by a linked list. Once you run out of ring entries, instead of a drop you fall back on a list with a common lock.

Should work well for the case where the ring is typically sized correctly, but will help address the fact that some user try to set e.g. tx queue length to 1000000.

In other words, the idea is that if a user sets a really huge TX queue length, we allocate a ptr_ring which is smaller, and use the backup linked list when necessary to provide the requested TX queue length legitimately.

My hope this will move us closer to direction where e.g. fw codel can use ptr rings without locking at all. The API is still very rough, and I really need to take a hard look at lock nesting.

Compiled only, sending for early feedback/flames.

Quoted 17 lines · Michael S. Tsirkin

So pointer rings work fine, but they have a problem: make them too small and not enough entries fit. Make them too large and you start flushing your cache and running out of memory.

This is a new idea of mine: a ring backed by a linked list. Once you run out of ring entries, instead of a drop you fall back on a list with a common lock.

Should work well for the case where the ring is typically sized correctly, but will help address the fact that some user try to set e.g. tx queue length to 1000000.

In other words, the idea is that if a user sets a really huge TX queue length, we allocate a ptr_ring which is smaller, and use the backup linked list when necessary to provide the requested TX queue length legitimately.

Quoted 5 lines

My hope this will move us closer to direction where e.g. fw codel can use ptr rings without locking at all. The API is still very rough, and I really need to take a hard look at lock nesting.

Compiled only, sending for early feedback/flames.

Okay I'll bite then ;)

High performance will be hit only if nothing is added in the (fallback) list.

Under stress, list operations will be the bottleneck, allowing XXXX items in the list, probably wasting cpu caches by always dequeue-ing cold objects.

Since systems need to be provisioned to cope with the stress, why trying to optimize the light load case, while we know CPU has plenty of cycles to use ?

If something uses ptr_ring and needs a list for the fallback, it might simply go back to the old-and-simple list stuff.

Note that this old-and-simple stuff can greatly be optimized with the use of two lists, as was shown in UDP stack lately, to decouple producer and consumer (batching effects)