net: Alloc NAPI page frags from their own pool
Subsystems (10)
cover net: Alloc NAPI page frags from their own pool
This patch series implements a means of allocating page fragments without the need for the local_irq_save/restore in __netdev_alloc_frag. By doing this I am able to decrease packet processing time by 11ns per packet in my test environment.
---
Alexander Duyck (6):
net: Split netdev_alloc_frag into __alloc_page_frag and add __napi_alloc_frag
net: Pull out core bits of __netdev_alloc_skb and add __napi_alloc_skb ethernet/intel: Use napi_alloc_skb
cxgb: Use napi_alloc_skb instead of netdev_alloc_skb_ip_align ethernet/realtek: use napi_alloc_skb instead of netdev_alloc_skb_ip_align ethernet/broadcom: Use napi_alloc_skb instead of netdev_alloc_skb_ip_align
drivers/net/ethernet/broadcom/b44.c | 2 drivers/net/ethernet/broadcom/bcm63xx_enet.c | 2 drivers/net/ethernet/broadcom/bnx2x/bnx2x_cmn.c | 2 drivers/net/ethernet/chelsio/cxgb/sge.c | 11 + drivers/net/ethernet/intel/e1000/e1000_main.c | 2 drivers/net/ethernet/intel/e1000e/netdev.c | 2 drivers/net/ethernet/intel/fm10k/fm10k_main.c | 4 drivers/net/ethernet/intel/igb/igb_main.c | 3 drivers/net/ethernet/intel/ixgb/ixgb_main.c | 6 - drivers/net/ethernet/intel/ixgbe/ixgbe_main.c | 4 drivers/net/ethernet/realtek/8139cp.c | 2 drivers/net/ethernet/realtek/8139too.c | 2 drivers/net/ethernet/realtek/r8169.c | 2 include/linux/skbuff.h | 11 + net/core/dev.c | 2 net/core/skbuff.c | 191 +++++++++++++++++------ 16 files changed, 178 insertions(+), 70 deletions(-)
--
PATCH 1/6 net: Split netdev_alloc_frag into __alloc_page_frag and add __napi_alloc_frag
This patch splits the netdev_alloc_frag function up so that it can be used on one of two page frag pools instead of being fixed on the netdev_alloc_cache. By doing this we can add a NAPI specific function __napi_alloc_frag that accesses a pool that is only used from softirq context. The advantage to this is that we do not need to call local_irq_save/restore which can be a significant savings.
I also took the opportunity to refactor the core bits that were placed in __alloc_page_frag. First I updated the allocation to do either a 32K allocation or an order 0 page. This is based on the changes in commmit d9b2938aa where it was found that latencies could be reduced in case of failures. Then I also rewrote the logic to work from the end of the page to the start. By doing this the size value doesn't have to be used unless we have run out of space for page fragments. Finally I cleaned up the atomic bits so that we just do an atomic_sub_and_test and if that returns true then we set the page->_count via an atomic_set. This way we can remove the extra conditional for the atomic_read since it would have led to an atomic_inc in the case of success anyway.
--- include/linux/skbuff.h | 2 + net/core/skbuff.c | 117 ++++++++++++++++++++++++++++++++---------------- 2 files changed, 79 insertions(+), 40 deletions(-)
include/linux/skbuff.h +2 -0
@@ -2164,6 +2164,8 @@ static inline struct sk_buff *netdev_alloc_skb_ip_align(struct net_device *dev,return __netdev_alloc_skb_ip_align (dev, length,GFP_ATOMIC ); } +void *napi_alloc_frag (unsigned int fragsz); +/** * __dev_alloc_pages - allocate page for network Rx * @gfp_mask: allocation priority. Set __GFP_NOMEMALLOC if not for network Rx
net/core/skbuff.c +77 -40
142 lines not on this page · raw message
Re: [net-next PATCH 1/6] net: Split netdev_alloc_frag into __alloc_page_frag and add __napi_alloc_frag
Quoted 11 lines · Alexander Duyck
This patch splits the
netdev_alloc_fragfunction up so that it can be used on one of two page frag pools instead of being fixed on thenetdev_alloc_cache. By doing this we can add a NAPI specific function__napi_alloc_fragthat accesses a pool that is only used from softirq context. The advantage to this is that we do not need to call local_irq_save/restore which can be a significant savings.I also took the opportunity to refactor the core bits that were placed in
__alloc_page_frag. First I updated the allocation to do either a 32K allocation or an order 0 page. This is based on the changes in commmitd9b2938aawhere it was found that latencies could be reduced in case of
thanks for explaining that piece of it.
Quoted 4 lines
net/core/skbuff.c +4
-0+struct page *page =NULL ; +gfp_t gfp = gfp_mask; + +if (order) {
net/core/skbuff.c struct netdev_alloc_cache { · line 355
Quoted 10 lines
net/core/skbuff.c +6
-3+ gfp_mask |= __GFP_COMP | __GFP_NOWARN | __GFP_NORETRY; + page =alloc_pages_node (NUMA_NO_NODE , gfp_mask, order); + nc->frag.size =PAGE_SIZE << (page ? order :0 ); + } -local_irq_save (flags); - nc =this_cpu_ptr (&netdev_alloc_cache); -if (unlikely (!nc->frag.page)) { +if (unlikely (!page)) + page =alloc_pages_node (NUMA_NO_NODE , gfp,0 );
I'm guessing you're not combining this 'if' with above one to keep gfp untouched, so there is a 'warn' when it actually fails 2nd time. Tricky :)
Anyway looks good to me and I think I understand it enough to say:
Re: [net-next PATCH 1/6] net: Split netdev_alloc_frag into __alloc_page_frag and add __napi_alloc_frag
Quoted 29 lines · Alexei Starovoitov
Quoted 11 lines · Alexander Duyck
This patch splits the
netdev_alloc_fragfunction up so that it can be used on one of two page frag pools instead of being fixed on thenetdev_alloc_cache. By doing this we can add a NAPI specific function__napi_alloc_fragthat accesses a pool that is only used from softirq context. The advantage to this is that we do not need to call local_irq_save/restore which can be a significant savings.I also took the opportunity to refactor the core bits that were placed in
__alloc_page_frag. First I updated the allocation to do either a 32K allocation or an order 0 page. This is based on the changes in commmitd9b2938aawhere it was found that latencies could be reduced in case ofthanks for explaining that piece of it.
Quoted 4 lines
net/core/skbuff.c +4
-0+struct page *page =NULL ; +gfp_t gfp = gfp_mask; + +if (order) {net/core/skbuff.c struct netdev_alloc_cache { · line 355
Quoted 10 lines
net/core/skbuff.c +6
-3+ gfp_mask |= __GFP_COMP | __GFP_NOWARN | __GFP_NORETRY; + page =alloc_pages_node (NUMA_NO_NODE , gfp_mask, order); + nc->frag.size =PAGE_SIZE << (page ? order :0 ); + } -local_irq_save (flags); - nc =this_cpu_ptr (&netdev_alloc_cache); -if (unlikely (!nc->frag.page)) { +if (unlikely (!page)) + page =alloc_pages_node (NUMA_NO_NODE , gfp,0 );
Quoted 5 lines
I'm guessing you're not combining this 'if' with above one to keep gfp untouched, so there is a 'warn' when it actually fails 2nd time. Tricky :)
Anyway looks good to me and I think I understand it enough to say:
Thanks. Yes the compiler is smart enough to combine the frag.size and the second check into one if order is non-zero. The other trick here is if order is 0 then that whole block disappears and I don't have to touch frag.size or gfp at all and the code gets much simpler as the *page = NULL falls though and cancels out the 'if' as a compile time check.
- Alex
Re: [net-next PATCH 1/6] net: Split netdev_alloc_frag into __alloc_page_frag and add __napi_alloc_frag
In reply to Alexander DuyckQuoted 5 lines · Alexander Duyck
I also took the opportunity to refactor the core bits that were placed in
__alloc_page_frag. First I updated the allocation to do either a 32K allocation or an order 0 page. This is based on the changes in commmitd9b2938aawhere it was found that latencies could be reduced in case of failures.
GFP_KERNEL and GFP_ATOMIC allocation constraints are quite different.
I have no idea how expensive it is to attempt order-3, order-2, order-1 allocations with GFP_ATOMIC.
I did an interesting experiment on mlx4 driver, allocating the pages needed to store the fragments, using a small layer before the alloc_page() that is normally used :
- Attempt order-9 allocations, and use split_page() to give the individual pages.
Boost in performance is 10% on TCP bulk receive, because of less TLB misses.
With huge amount of memory these days, alloc_page() tend to give pages spread all over memory, with poor TLB locality.
With this strategy, a 1024 RX ring is backed by 2 huge pages only.
Re: [net-next PATCH 1/6] net: Split netdev_alloc_frag into __alloc_page_frag and add __napi_alloc_frag
Quoted 8 lines · Eric Dumazet
Quoted 5 lines · Alexander Duyck
I also took the opportunity to refactor the core bits that were placed in
__alloc_page_frag. First I updated the allocation to do either a 32K allocation or an order 0 page. This is based on the changes in commmitd9b2938aawhere it was found that latencies could be reduced in case of failures.
Quoted 4 lines
GFP_KERNELandGFP_ATOMICallocation constraints are quite different.I have no idea how expensive it is to attempt order-3, order-2, order-1 allocations with
GFP_ATOMIC.
The most likely case is the successful first allocation so I didn't see much point in trying to optimize for the failure cases. I personally prefer to see a fast failure rather than one that is dragged out over several failed allocation attempts. In addition I can get away with several optimization tricks that I cannot with the loop.
Quoted 7 lines
I did an interesting experiment on mlx4 driver, allocating the pages needed to store the fragments, using a small layer before the
alloc_page()that is normally used :- Attempt order-9 allocations, and use
split_page()to give the individual pages.
Quoted 7 lines
Boost in performance is 10% on TCP bulk receive, because of less TLB misses.
With huge amount of memory these days,
alloc_page()tend to give pages spread all over memory, with poor TLB locality.With this strategy, a 1024 RX ring is backed by 2 huge pages only.
That is an interesting idea. I wonder if there would be a similar benefit for small packets. If nothing else I might try a few experiments with ixgbe to see if I can take advantage of something similar.
- Alex
Re: [net-next PATCH 1/6] net: Split netdev_alloc_frag into __alloc_page_frag and add __napi_alloc_frag
Quoted 3 lines · Alexander Duyck
That is an interesting idea. I wonder if there would be a similar benefit for small packets. If nothing else I might try a few experiments with ixgbe to see if I can take advantage of something similar.
I was planning to submit a core infrastructure when net-next reopens, a simple layer to use instead of alloc_page(), and immediately usable in Intel drivers.
Re: [net-next PATCH 1/6] net: Split netdev_alloc_frag into __alloc_page_frag and add __napi_alloc_frag
Quoted 8 lines · Eric Dumazet
Quoted 3 lines · Alexander Duyck
That is an interesting idea. I wonder if there would be a similar benefit for small packets. If nothing else I might try a few experiments with ixgbe to see if I can take advantage of something similar.
I was planning to submit a core infrastructure when net-next reopens, a simple layer to use instead of
alloc_page(), and immediately usable in Intel drivers.
Sound good. I look forward to it.
PATCH 2/6 net: Pull out core bits of __netdev_alloc_skb and add __napi_alloc_skb
In reply to Alexander DuyckThis change pulls the core functionality out of __netdev_alloc_skb and places them in a new function named __alloc_rx_skb. The reason for doing this is to make these bits accessible to a new function __napi_alloc_skb. In addition __alloc_rx_skb now has a new flags value that is used to determine which page frag pool to allocate from. If the SKB_ALLOC_NAPI flag is set then the NAPI pool is used. The advantage of this is that we do not have to use local_irq_save/restore when accessing the NAPI pool from NAPI context.
In my test setup I saw at least 11ns of savings using the napi_alloc_skb function versus the netdev_alloc_skb function, most of this being due to the fact that we didn't have to call local_irq_save/restore.
The main use case for napi_alloc_skb would be for things such as copybreak or page fragment based receive paths where an skb is allocated after the data has been received instead of before.
--- include/linux/skbuff.h | 9 ++++++ net/core/dev.c | 2 + net/core/skbuff.c | 74 +++++++++++++++++++++++++++++++++++++++++++----- 3 files changed, 77 insertions(+), 8 deletions(-)
include/linux/skbuff.h +9 -0
@@ -151,6 +151,7 @@ struct net_device;struct scatterlist ;struct pipe_inode_info ;struct iov_iter ; +struct napi_struct ;#if defined(CONFIG_NF_CONNTRACK ) || defined(CONFIG_NF_CONNTRACK_MODULE ) struct nf_conntrack {
@@ -673,6 +674,7 @@ struct sk_buff {#define SKB_ALLOC_FCLONE 0x01#define SKB_ALLOC_RX 0x02 +#define SKB_ALLOC_NAPI 0x04/* Returns true if the skb was allocated from PFMEMALLOC reserves */ static inline bool skb_pfmemalloc (const struct sk_buff *skb)
@@ -2165,6 +2167,13 @@ static inline struct sk_buff *netdev_alloc_skb_ip_align(struct net_device *dev, }void *napi_alloc_frag (unsigned int fragsz); +struct sk_buff *__napi_alloc_skb (struct napi_struct *napi, +unsigned int length,gfp_t gfp_mask); +static inline struct sk_buff *napi_alloc_skb (struct napi_struct *napi, +unsigned int length) +{ +return __napi_alloc_skb (napi, length,GFP_ATOMIC ); +}/** * __dev_alloc_pages - allocate page for network Rx
net/core/dev.c +1 -1
@@ -4172,7 +4172,7 @@ struct sk_buff *napi_get_frags(struct napi_struct *napi)struct sk_buff *skb = napi->skb;if (!skb) { - skb =netdev_alloc_skb_ip_align (napi->dev,GRO_MAX_HEAD ); + skb =napi_alloc_skb (napi,GRO_MAX_HEAD ); napi->skb = skb; }return skb;
net/core/skbuff.c +67 -7
112 lines not on this page · raw message
PATCH 3/6 ethernet/intel: Use napi_alloc_skb
In reply to Alexander DuyckThis change replaces calls to netdev_alloc_skb_ip_align with napi_alloc_skb. The advantage of napi_alloc_skb is currently the fact that the page allocation doesn't make use of any irq disable calls.
There are few spots where I couldn't replace the calls as the buffer allocation routine is called as a part of init which is outside of the softirq context.
--- drivers/net/ethernet/intel/e1000/e1000_main.c | 2 +- drivers/net/ethernet/intel/e1000e/netdev.c | 2 +- drivers/net/ethernet/intel/fm10k/fm10k_main.c | 4 ++-- drivers/net/ethernet/intel/igb/igb_main.c | 3 +-- drivers/net/ethernet/intel/ixgb/ixgb_main.c | 6 +++--- drivers/net/ethernet/intel/ixgbe/ixgbe_main.c | 4 ++-- 6 files changed, 10 insertions(+), 11 deletions(-)
drivers/net/ethernet/intel/e1000/e1000_main.c +1 -1
@@ -4100,7 +4100,7 @@ static bool e1000_tbi_should_accept(struct e1000_adapter *adapter,static struct sk_buff *e1000_alloc_rx_skb (struct e1000_adapter *adapter,unsigned int bufsz) { -struct sk_buff *skb =netdev_alloc_skb_ip_align (adapter->netdev, bufsz); +struct sk_buff *skb =napi_alloc_skb (&adapter->napi, bufsz);if (unlikely (!skb)) adapter->alloc_rx_buff_failed++;
drivers/net/ethernet/intel/e1000e/netdev.c +1 -1
@@ -1016,7 +1016,7 @@ static bool e1000_clean_rx_irq(struct e1000_ring *rx_ring, int *work_done,*/ if (length < copybreak) {struct sk_buff *new_skb = -netdev_alloc_skb_ip_align (netdev, length); +napi_alloc_skb (&adapter->napi, length);if (new_skb) { skb_copy_to_linear_data_offset(new_skb, -NET_IP_ALIGN,
drivers/net/ethernet/intel/fm10k/fm10k_main.c +2 -2
@@ -308,8 +308,8 @@ static struct sk_buff *fm10k_fetch_rx_buffer(struct fm10k_ring *rx_ring,#endif /* allocate a skb to store the frags */ - skb =netdev_alloc_skb_ip_align (rx_ring->netdev, -FM10K_RX_HDR_LEN ); + skb =napi_alloc_skb (&rx_ring->q_vector->napi, +FM10K_RX_HDR_LEN );if (unlikely (!skb)) { rx_ring->rx_stats.alloc_failed++;return NULL ;
drivers/net/ethernet/intel/igb/igb_main.c +1 -2
@@ -6641,8 +6641,7 @@ static struct sk_buff *igb_fetch_rx_buffer(struct igb_ring *rx_ring,#endif /* allocate a skb to store the frags */ - skb =netdev_alloc_skb_ip_align (rx_ring->netdev, -IGB_RX_HDR_LEN ); + skb =napi_alloc_skb (&rx_ring->q_vector->napi,IGB_RX_HDR_LEN );if (unlikely (!skb)) { rx_ring->rx_stats.alloc_failed++;return NULL ;
drivers/net/ethernet/intel/ixgb/ixgb_main.c +3 -3
@@ -1963,7 +1963,7 @@ ixgb_rx_checksum(struct ixgb_adapter *adapter,* this should improve performance for small packets with large amounts * of reassembly being done in the stack */ -static void ixgb_check_copybreak (struct net_device *netdev, +static void ixgb_check_copybreak (struct napi_struct *napi,struct ixgb_buffer *buffer_info,u32 length,struct sk_buff **skb) {
@@ -1972,7 +1972,7 @@ static void ixgb_check_copybreak(struct net_device *netdev,if (length > copybreak)return ; - new_skb =netdev_alloc_skb_ip_align (netdev, length); + new_skb =napi_alloc_skb (napi, length);if (!new_skb)return ;
@@ -2064,7 +2064,7 @@ ixgb_clean_rx_irq(struct ixgb_adapter *adapter, int *work_done, int work_to_do) goto rxdesc_done; } -ixgb_check_copybreak (netdev, buffer_info, length, &skb); +ixgb_check_copybreak (&adapter->napi, buffer_info, length, &skb);/* Good Receive */ skb_put (skb, length);
drivers/net/ethernet/intel/ixgbe/ixgbe_main.c +2 -2
@@ -1909,8 +1909,8 @@ static struct sk_buff *ixgbe_fetch_rx_buffer(struct ixgbe_ring *rx_ring,#endif /* allocate a skb to store the frags */ - skb =netdev_alloc_skb_ip_align (rx_ring->netdev, -IXGBE_RX_HDR_SIZE ); + skb =napi_alloc_skb (&rx_ring->q_vector->napi, +IXGBE_RX_HDR_SIZE );if (unlikely (!skb)) { rx_ring->rx_stats.alloc_rx_buff_failed++;return NULL ;
Re: [net-next PATCH 3/6] ethernet/intel: Use napi_alloc_skb
Quoted 11 lines · Alexander Duyck
This change replaces calls to
netdev_alloc_skb_ip_alignwithnapi_alloc_skb. The advantage ofnapi_alloc_skbis currently the fact that
the page allocation doesn't make use of any irq disable calls.There are few spots where I couldn't replace the calls as the buffer allocation routine is called as a part of init which is outside of the softirq context.
Cc Jeff Kirsher <[email protected]>Signed-off-by Alexander Duyck <[email protected]>
Quoted 8 lines
--- drivers/net/ethernet/intel/e1000/e1000_main.c | 2 +- drivers/net/ethernet/intel/e1000e/netdev.c | 2 +- drivers/net/ethernet/intel/fm10k/fm10k_main.c | 4 ++-- drivers/net/ethernet/intel/igb/igb_main.c | 3 +-- drivers/net/ethernet/intel/ixgb/ixgb_main.c | 6 +++--- drivers/net/ethernet/intel/ixgbe/ixgbe_main.c | 4 ++-- 6 files changed, 10 insertions(+), 11 deletions(-)
PATCH 4/6 cxgb: Use napi_alloc_skb instead of netdev_alloc_skb_ip_align
In reply to Alexander DuyckIn order to use napi_alloc_skb I needed to pass a pointer to struct adapter instead of struct pci_dev. This allowed me to access &adapter->napi.
--- drivers/net/ethernet/chelsio/cxgb/sge.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-)
drivers/net/ethernet/chelsio/cxgb/sge.c +6 -5
@@ -1025,7 +1025,7 @@ MODULE_PARM_DESC(copybreak, "Receive copy threshold");/** * get_packet - return the next ingress packet buffer -* @pdev: the PCI device that received the packet +* @adapter: the adapter that received the packet * @fl: the SGE free list holding the packet * @len: the actual packet length, excluding any SGE padding *
@@ -1037,14 +1037,15 @@ MODULE_PARM_DESC(copybreak, "Receive copy threshold");* threshold and the packet is too big to copy, or (b) the packet should * be copied but there is no memory for the copy. */ -static inline struct sk_buff *get_packet (struct pci_dev *pdev, +static inline struct sk_buff *get_packet (struct adapter *adapter,struct freelQ *fl,unsigned int len) { -struct sk_buff *skb;const struct freelQ_ce *ce = &fl->centries[fl->cidx]; +struct pci_dev *pdev = adapter->pdev; +struct sk_buff *skb;if (len < copybreak) { - skb =netdev_alloc_skb_ip_align (NULL , len); + skb =napi_alloc_skb (&adapter->napi, len);if (!skb) goto use_orig_buf;
@@ -1357,7 +1358,7 @@ static void sge_rx(struct sge *sge, struct freelQ *fl, unsigned int len)struct sge_port_stats *st;struct net_device *dev; - skb =get_packet (adapter->pdev, fl, len - sge->rx_pkt_pad); + skb =get_packet (adapter, fl, len - sge->rx_pkt_pad);if (unlikely (!skb)) { sge->stats.rx_drops++;return ;
PATCH 5/6 ethernet/realtek: use napi_alloc_skb instead of netdev_alloc_skb_ip_align
In reply to Alexander DuyckThis replaces most of the calls to netdev_alloc_skb_ip_align in the Realtek drivers. The one instance I didn't replace in 8139cp.c is because it was called as a part of init and as such is not always accessed from the softirq context.
--- drivers/net/ethernet/realtek/8139cp.c | 2 +- drivers/net/ethernet/realtek/8139too.c | 2 +- drivers/net/ethernet/realtek/r8169.c | 2 +- 3 files changed, 3 insertions(+), 3 deletions(-)
drivers/net/ethernet/realtek/8139cp.c +1 -1
@@ -507,7 +507,7 @@ rx_status_loop:netif_dbg (cp, rx_status, dev,"rx slot %d status 0x%x len %d\n" , rx_tail, status, len); - new_skb =netdev_alloc_skb_ip_align (dev, buflen); + new_skb =napi_alloc_skb (napi, buflen);if (!new_skb) { dev->stats.rx_dropped++; goto rx_next;
drivers/net/ethernet/realtek/8139too.c +1 -1
@@ -2037,7 +2037,7 @@ keep_pkt:/* Malloc up new buffer, compatible with net-2e. */ /* Omit the four octet CRC from the length. */ - skb =netdev_alloc_skb_ip_align (dev, pkt_size); + skb =napi_alloc_skb (&tp->napi, pkt_size);if (likely (skb)) {#if RX_BUF_IDX ==3 wrap_copy (skb, rx_ring, ring_offset+4 , pkt_size);
drivers/net/ethernet/realtek/r8169.c +1 -1
@@ -7269,7 +7269,7 @@ static struct sk_buff *rtl8169_try_rx_copy(void *data, data =rtl8169_align (data);dma_sync_single_for_cpu (d, addr, pkt_size,DMA_FROM_DEVICE );prefetch (data); - skb =netdev_alloc_skb_ip_align (tp->dev, pkt_size); + skb =napi_alloc_skb (&tp->napi, pkt_size);if (skb)memcpy (skb->data, data, pkt_size);dma_sync_single_for_device (d, addr, pkt_size,DMA_FROM_DEVICE );
PATCH 6/6 ethernet/broadcom: Use napi_alloc_skb instead of netdev_alloc_skb_ip_align
In reply to Alexander DuyckThis patch replaces the calls to netdev_alloc_skb_ip_align in the copybreak paths.
--- drivers/net/ethernet/broadcom/b44.c | 2 +- drivers/net/ethernet/broadcom/bcm63xx_enet.c | 2 +- drivers/net/ethernet/broadcom/bnx2x/bnx2x_cmn.c | 2 +- 3 files changed, 3 insertions(+), 3 deletions(-)
drivers/net/ethernet/broadcom/b44.c +1 -1
@@ -836,7 +836,7 @@ static int b44_rx(struct b44 *bp, int budget)struct sk_buff *copy_skb;b44_recycle_rx (bp, cons, bp->rx_prod); - copy_skb =netdev_alloc_skb_ip_align (bp->dev, len); + copy_skb =napi_alloc_skb (&bp->napi, len);if (copy_skb ==NULL ) goto drop_it_no_recycle;
drivers/net/ethernet/broadcom/bcm63xx_enet.c +1 -1
@@ -385,7 +385,7 @@ static int bcm_enet_receive_queue(struct net_device *dev, int budget)if (len < copybreak) {struct sk_buff *nskb; - nskb =netdev_alloc_skb_ip_align (dev, len); + nskb =napi_alloc_skb (&priv->napi, len);if (!nskb) {/* forget packet, just rearm desc */ dev->stats.rx_dropped++;
drivers/net/ethernet/broadcom/bnx2x/bnx2x_cmn.c +1 -1
@@ -1015,7 +1015,7 @@ static int bnx2x_rx_int(struct bnx2x_fastpath *fp, int budget)*/ if ((bp->dev->mtu >ETH_MAX_PACKET_SIZE ) && (len <=RX_COPY_THRESH )) { - skb =netdev_alloc_skb_ip_align (bp->dev, len); + skb =napi_alloc_skb (&fp->napi, len);if (skb ==NULL ) {DP (NETIF_MSG_RX_ERR |NETIF_MSG_RX_STATUS ,"ERROR packet dropped because of alloc failure\n" );
RE: [net-next PATCH 6/6] ethernet/broadcom: Use napi_alloc_skb instead of netdev_alloc_skb_ip_align
From: Alexander Duyck
Quoted 2 lines
This patch replaces the calls to
netdev_alloc_skb_ip_alignin the copybreak paths.
Why?
You still want the IP header to be aligned and you also want the memcpy() to be copying aligned data.
I suspect this fails on both counts?
David
Quoted 56 lines
Cc Gary Zambrano <[email protected]>Cc Florian Fainelli <[email protected]>Cc Ariel Elior <[email protected]>Signed-off-by Alexander Duyck <[email protected]>--- drivers/net/ethernet/broadcom/b44.c | 2 +- drivers/net/ethernet/broadcom/bcm63xx_enet.c | 2 +- drivers/net/ethernet/broadcom/bnx2x/bnx2x_cmn.c | 2 +- 3 files changed, 3 insertions(+), 3 deletions(-)drivers/net/ethernet/broadcom/b44.c +1
-1@@ -836,7 +836,7 @@ static int b44_rx(struct b44 *bp, int budget)struct sk_buff *copy_skb;b44_recycle_rx (bp, cons, bp->rx_prod); - copy_skb =netdev_alloc_skb_ip_align (bp->dev, len); + copy_skb =napi_alloc_skb (&bp->napi, len);if (copy_skb ==NULL ) goto drop_it_no_recycle;drivers/net/ethernet/broadcom/bcm63xx_enet.c +1
-1@@ -385,7 +385,7 @@ static int bcm_enet_receive_queue(struct net_device *dev, int budget)if (len < copybreak) {struct sk_buff *nskb; - nskb =netdev_alloc_skb_ip_align (dev, len); + nskb =napi_alloc_skb (&priv->napi, len);if (!nskb) {/* forget packet, just rearm desc */ dev->stats.rx_dropped++;drivers/net/ethernet/broadcom/bnx2x/bnx2x_cmn.c +1
-2@@ -1015,7 +1015,7 @@ static int bnx2x_rx_int(struct bnx2x_fastpath *fp, int budget)*/ if ((bp->dev->mtu >ETH_MAX_PACKET_SIZE ) && (len <=RX_COPY_THRESH )) { - skb =netdev_alloc_skb_ip_align (bp->dev, len); + skb =napi_alloc_skb (&fp->napi, len);if (skb ==NULL ) {DP (NETIF_MSG_RX_ERR |NETIF_MSG_RX_STATUS ,"ERROR packet dropped because of alloc failure\n" ); --To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
RE: [net-next PATCH 6/6] ethernet/broadcom: Use napi_alloc_skb instead of netdev_alloc_skb_ip_align
From: David Laight
Quoted 10 lines
From: Alexander Duyck
Quoted 2 lines
This patch replaces the calls to
netdev_alloc_skb_ip_alignin the copybreak paths.Why?
You still want the IP header to be aligned and you also want the
memcpy()to be copying aligned data.I suspect this fails on both counts?
Or am I confused by the naming?
David
Quoted 24 lines
David
Quoted 22 lines
Cc Gary Zambrano <[email protected]>Cc Florian Fainelli <[email protected]>Cc Ariel Elior <[email protected]>Signed-off-by Alexander Duyck <[email protected]>--- drivers/net/ethernet/broadcom/b44.c | 2 +- drivers/net/ethernet/broadcom/bcm63xx_enet.c | 2 +- drivers/net/ethernet/broadcom/bnx2x/bnx2x_cmn.c | 2 +- 3 files changed, 3 insertions(+), 3 deletions(-)drivers/net/ethernet/broadcom/b44.c +1
-1@@ -836,7 +836,7 @@ static int b44_rx(struct b44 *bp, int budget)struct sk_buff *copy_skb;b44_recycle_rx (bp, cons, bp->rx_prod); - copy_skb =netdev_alloc_skb_ip_align (bp->dev, len); + copy_skb =napi_alloc_skb (&bp->napi, len);if (copy_skb ==NULL ) goto drop_it_no_recycle;
...
Re: [net-next PATCH 6/6] ethernet/broadcom: Use napi_alloc_skb instead of netdev_alloc_skb_ip_align
Quoted 6 lines · David Laight
From: David Laight
Quoted 5 lines
From: Alexander Duyck
Quoted 2 lines
This patch replaces the calls to
netdev_alloc_skb_ip_alignin the copybreak paths.Why?
Quoted 8 lines
Quoted 4 lines
You still want the IP header to be aligned and you also want the
memcpy()to be copying aligned data.I suspect this fails on both counts?
Or am I confused by the naming?
David
The bit you are missing is that napi_alloc_skb is always IP aligned. The general idea with napi_alloc_skb is that it is a cheaper way allocate frames that are about to be passed up the stack as a NAPI or GRO receive so the IP aligned part is a given.
- Alex
cover Faster than SLAB caching of SKBs with qmempool (backed by alf_queue)
In reply to Alexander DuyckThe network stack have some use-cases that puts some extreme demands on the memory allocator. One use-case, 10Gbit/s wirespeed at smallest packet size[1], requires handling a packet every 67.2 ns (nanosec).
Micro benchmarking[2] the SLUB allocator (with skb size 256bytes elements), show "fast-path" instant reuse only costs 19 ns, but a closer to network usage pattern show the cost rise to 45 ns.
This patchset introduce a quick mempool (qmempool), which when used in-front of the SKB (sk_buff) kmem_cache, saves 12 ns on "fast-path" drop in iptables "raw" table, but more importantly saves 40 ns with IP-forwarding, which were hitting the slower SLUB use-case.
One of the building blocks for achieving this speedup is a cmpxchg based Lock-Free queue that supports bulking, named alf_queue for Array-based Lock-Free queue. By bulking elements (pointers) from the queue, the cost of the cmpxchg (approx 8 ns) is amortized over several elements.
Patch1: alf_queue (Lock-Free queue)
Patch2: qmempool using alf_queue
Patch3: usage of qmempool for SKB caching
Notice, this patchset depend on introduction of napi_alloc_skb(), which is part of Alexander Duyck's work patchset [3].
Different correctness tests and micro benchmarks are avail via my github repo "prototype-kernel"[4], where the alf_queue and qmempool is also kept in sync with this patchset.
Links:
[1]: http://netoptimizer.blogspot.dk/2014/05/the-calculations-10gbits-wirespeed.html
[2]: https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/qmempool_bench.c
[3]: http://thread.gmane.org/gmane.linux.network/342347
[4]: https://github.com/netoptimizer/prototype-kernel
---
Jesper Dangaard Brouer (3):
net: use qmempool in-front of sk_buff kmem_cache
mm: qmempool - quick queue based memory pool
lib: adding an Array-based Lock-Free (ALF) queue
include/linux/alf_queue.h | 303 ++++++++++++++++++++++++++++++++++++++++++ include/linux/qmempool.h | 205 +++++++++++++++++++++++++++++ include/linux/skbuff.h | 4 - lib/Kconfig | 13 ++ lib/Makefile | 2 lib/alf_queue.c | 47 +++++++ mm/Kconfig | 12 ++ mm/Makefile | 1 mm/qmempool.c | 322 +++++++++++++++++++++++++++++++++++++++++++++ net/core/dev.c | 5 + net/core/skbuff.c | 43 +++++- 11 files changed, 950 insertions(+), 7 deletions(-) create mode 100644 include/linux/alf_queue.h create mode 100644 include/linux/qmempool.h create mode 100644 lib/alf_queue.c create mode 100644 mm/qmempool.c
Signature · 11 lines
Best regards, Jesper Dangaard Brouer MSc.CS, Sr. Network Kernel Developer at Red Hat Author of http://www.iptv-analyzer.org LinkedIn: http://www.linkedin.com/in/brouer -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 1/3 lib: adding an Array-based Lock-Free (ALF) queue
This Array-based Lock-Free (ALF) queue, is a very fast bounded Producer-Consumer queue, supporting bulking. The MPMC (Multi-Producer/Multi-Consumer) variant uses a locked cmpxchg, but the cost can be amorized by utilizing bulk enqueue/dequeue.
Results on x86_64 CPU E5-2695, for variants:
MPMC = Multi-Producer-Multi-Consumer
SPSC = Single-Producer-Single-Consumer
(none-bulking): per element cost MPMC and SPSC
MPMC -- SPSC
simple : 9.519 ns -- 1.282 ns
multi(step:128): 12.905 ns -- 2.240 ns
The majority of the cost is associated with the locked cmpxchg in the MPMC variant. Bulking helps amortize this cost:
(bulking) cost per element comparing MPMC -> SPSC:
MPMC -- SPSC
bulk2 : 5.849 ns -- 1.748 ns
bulk3 : 4.102 ns -- 1.531 ns
bulk4 : 3.281 ns -- 1.383 ns
bulk6 : 2.530 ns -- 1.238 ns
bulk8 : 2.125 ns -- 1.196 ns
bulk16: 1.552 ns -- 1.109 ns
Joint work with Hannes Frederic Sowa.
---
Correctness of memory barries on different arch's need to be evaluated.
The API might need some adjustments/discussions regarding:
1) the semantics of enq/deq when doing bulking, choosing what to do when e.g. a bulk enqueue cannot fit fully.
2) some better way to detect miss-use of API, e.g. using single-enqueue variant function call on a multi-enqueue variant data structure. Now no detection happens.
include/linux/alf_queue.h | 303 +++++++++++++++++++++++++++++++++++++++++++++ lib/Kconfig | 13 ++ lib/Makefile | 2 lib/alf_queue.c | 47 +++++++ 4 files changed, 365 insertions(+), 0 deletions(-) create mode 100644 include/linux/alf_queue.h create mode 100644 lib/alf_queue.c
include/linux/alf_queue.h new file +303 -0
@@ -0,0 +1,303 @@ +#ifndef _LINUX_ALF_QUEUE_H +#define _LINUX_ALF_QUEUE_H +/* linux/alf_queue.h +* +* ALF: Array-based Lock-Free queue +* +* Queue properties +* - Array based for cache-line optimization +* - Bounded by the array size +* - FIFO Producer/Consumer queue, no queue traversal supported +* - Very fast +* - Designed as a queue for pointers to objects +* - Bulk enqueue and dequeue support +* - Supports combinations of Multi and Single Producer/Consumer +* +* Copyright (C) 2014, Red Hat, Inc., +* by Jesper Dangaard Brouer and Hannes Frederic Sowa +* for licensing details see kernel-base/COPYING +*/ +#include <linux/compiler.h> +#include <linux/kernel.h> + +struct alf_actor { +u32 head; +u32 tail; +}; + +struct alf_queue { +u32 size; +u32 mask; +u32 flags; +struct alf_actor producer____cacheline_aligned_in_smp ; +struct alf_actor consumer____cacheline_aligned_in_smp ; +void *ring[0 ]____cacheline_aligned_in_smp ; +}; + +struct alf_queue *alf_queue_alloc (u32 size,gfp_t gfp); +void alf_queue_free (struct alf_queue *q); + +/* Helpers for LOAD and STORE of elements, have been split-out because: +* 1. They can be reused for both "Single" and "Multi" variants +* 2. Allow us to experiment with (pipeline) optimizations in this area. +*/ +static inline void +__helper_alf_enqueue_store (u32 p_head,struct alf_queue *q, +void **ptr,const u32 n) +{ +int i, index = p_head; + +for (i =0 ; i < n; i++, index++) + q->ring[index & q->mask] = ptr[i]; +} + +static inline void +__helper_alf_dequeue_load (u32 c_head,struct alf_queue *q, +void **ptr,const u32 elems) +{ +int i, index = c_head; + +for (i =0 ; i < elems; i++, index++) + ptr[i] = q->ring[index & q->mask]; +} + +/* Main Multi-Producer ENQUEUE +* +* Even-though current API have a "fixed" semantics of aborting if it +* cannot enqueue the full bulk size. Users of this API should check +* on the returned number of enqueue elements match, to verify enqueue +* was successful. This allow us to introduce a "variable" enqueue +* scheme later. +* +* Not preemption safe. Multiple CPUs can enqueue elements, but the +* same CPU is not allowed to be preempted and access the same +* queue. Due to how the tail is updated, this can result in a soft +* lock-up. (Same goes for alf_mc_dequeue). +*/ +static inline int +alf_mp_enqueue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{ +u32 p_head, p_next, c_tail, space; + +/* Reserve part of the array for enqueue STORE/WRITE */ +do { + p_head =ACCESS_ONCE (q->producer.head); + c_tail =ACCESS_ONCE (q->consumer.tail); + + space = q->size + c_tail - p_head; +if (n > space) +return 0 ; + + p_next = p_head + n; + } +while (unlikely (cmpxchg (&q->producer.head, p_head, p_next) != p_head)); + +/* STORE the elems into the queue array */ +__helper_alf_enqueue_store (p_head, q, ptr, n); +smp_wmb ();/* Write-Memory-Barrier matching dequeue LOADs */ + +/* Wait for other concurrent preceding enqueues not yet done, +* this part make us none-wait-free and could be problematic +* in case of congestion with many CPUs +*/ +while (unlikely (ACCESS_ONCE (q->producer.tail) != p_head)) +cpu_relax (); +/* Mark this enq done and avail for consumption */ +ACCESS_ONCE (q->producer.tail) = p_next; + +return n; +} + +/* Main Multi-Consumer DEQUEUE */ +static inline int +alf_mc_dequeue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{ +u32 c_head, c_next, p_tail, elems; + +/* Reserve part of the array for dequeue LOAD/READ */ +do { + c_head =ACCESS_ONCE (q->consumer.head); + p_tail =ACCESS_ONCE (q->producer.tail); + + elems = p_tail - c_head; + +if (elems ==0 ) +return 0 ; +else + elems =min (elems, n); + + c_next = c_head + elems; + } +while (unlikely (cmpxchg (&q->consumer.head, c_head, c_next) != c_head)); + +/* LOAD the elems from the queue array. +* We don't need a smb_rmb() Read-Memory-Barrier here because +* the above cmpxchg is an implied full Memory-Barrier. +*/ +__helper_alf_dequeue_load (c_head, q, ptr, elems); + +/* Archs with weak Memory Ordering need a memory barrier here. +* As the STORE to q->consumer.tail, must happen after the +* dequeue LOADs. Dequeue LOADs have a dependent STORE into +* ptr, thus a smp_wmb() is enough. Paired with enqueue +* implicit full-MB in cmpxchg. +*/ +smp_wmb (); + +/* Wait for other concurrent preceding dequeues not yet done */ +while (unlikely (ACCESS_ONCE (q->consumer.tail) != c_head)) +cpu_relax (); +/* Mark this deq done and avail for producers */ +ACCESS_ONCE (q->consumer.tail) = c_next; + +return elems; +} + +/* #define ASSERT_DEBUG_SPSC 1 */ +#ifndef ASSERT_DEBUG_SPSC +#define ASSERT (x) do { } while (0) +#else +#define ASSERT (x) \ + do { \ + if (unlikely(!(x))) { \ + pr_crit("Assertion failed %s:%d: \"%s\"\n", \ + __FILE__, __LINE__, #x); \ + BUG(); \ + } \ + } while (0) +#endif + +/* Main SINGLE Producer ENQUEUE +* caller MUST make sure preemption is disabled +*/ +static inline int +alf_sp_enqueue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{ +u32 p_head, p_next, c_tail, space; + +/* Reserve part of the array for enqueue STORE/WRITE */ + p_head = q->producer.head; +smp_rmb ();/* for consumer.tail write, making sure deq loads are done */ + c_tail =ACCESS_ONCE (q->consumer.tail); + + space = q->size + c_tail - p_head; +if (n > space) +return 0 ; + + p_next = p_head + n; +ASSERT (ACCESS_ONCE (q->producer.head) == p_head); + q->producer.head = p_next; + +/* STORE the elems into the queue array */ +__helper_alf_enqueue_store (p_head, q, ptr, n); +smp_wmb ();/* Write-Memory-Barrier matching dequeue LOADs */ + +/* Assert no other CPU (or same CPU via preemption) changed queue */ +ASSERT (ACCESS_ONCE (q->producer.tail) == p_head); + +/* Mark this enq done and avail for consumption */ +ACCESS_ONCE (q->producer.tail) = p_next; + +return n; +} + +/* Main SINGLE Consumer DEQUEUE +* caller MUST make sure preemption is disabled +*/ +static inline int +alf_sc_dequeue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{ +u32 c_head, c_next, p_tail, elems; + +/* Reserve part of the array for dequeue LOAD/READ */ + c_head = q->consumer.head; + p_tail =ACCESS_ONCE (q->producer.tail); + + elems = p_tail - c_head; + +if (elems ==0 ) +return 0 ; +else + elems =min (elems, n); + + c_next = c_head + elems; +ASSERT (ACCESS_ONCE (q->consumer.head) == c_head); + q->consumer.head = c_next; + +smp_rmb ();/* Read-Memory-Barrier matching enq STOREs */ +__helper_alf_dequeue_load (c_head, q, ptr, elems); + +/* Archs with weak Memory Ordering need a memory barrier here. +* As the STORE to q->consumer.tail, must happen after the +* dequeue LOADs. Dequeue LOADs have a dependent STORE into +* ptr, thus a smp_wmb() is enough. +*/ +smp_wmb (); + +/* Assert no other CPU (or same CPU via preemption) changed queue */ +ASSERT (ACCESS_ONCE (q->consumer.tail) == c_head); + +/* Mark this deq done and avail for producers */ +ACCESS_ONCE (q->consumer.tail) = c_next; + +return elems; +} + +static inline bool +alf_queue_empty (struct alf_queue *q) +{ +u32 c_tail =ACCESS_ONCE (q->consumer.tail); +u32 p_tail =ACCESS_ONCE (q->producer.tail); + +/* The empty (and initial state) is when consumer have reached +* up with producer. +* +* DOUBLE-CHECK: Should we use producer.head, as this indicate +* a producer is in-progress(?) +*/ +return c_tail == p_tail; +} + +static inline int +alf_queue_count (struct alf_queue *q) +{ +u32 c_head =ACCESS_ONCE (q->consumer.head); +u32 p_tail =ACCESS_ONCE (q->producer.tail); +u32 elems; + +/* Due to u32 arithmetic the values are implicitly +* masked/modulo 32-bit, thus saving one mask operation +*/ + elems = p_tail - c_head; +/* Thus, same as: +* elems = (p_tail - c_head) & q->mask; +*/ +return elems; +} + +static inline int +alf_queue_avail_space (struct alf_queue *q) +{ +u32 p_head =ACCESS_ONCE (q->producer.head); +u32 c_tail =ACCESS_ONCE (q->consumer.tail); +u32 space; + +/* The max avail space is q->size and +* the empty state is when (consumer == producer) +*/ + +/* Due to u32 arithmetic the values are implicitly +* masked/modulo 32-bit, thus saving one mask operation +*/ + space = q->size + c_tail - p_head; +/* Thus, same as: +* space = (q->size + c_tail - p_head) & q->mask; +*/ +return space; +} + +#endif /* _LINUX_ALF_QUEUE_H */
lib/Kconfig +13 -0
@@ -439,6 +439,19 @@ config NLATTR bool # +# ALF queue +# +config ALF_QUEUE + bool "ALF: Array-based Lock-Free (Producer-Consumer) queue" + default y + help + This Array-based Lock-Free (ALF) queue, is a very fast + bounded Producer-Consumer queue, supporting bulking. The + MPMC (Multi-Producer/Multi-Consumer) variant uses a locked + cmpxchg, but the cost can be amorized by utilizing bulk + enqueue/dequeue. + +# # Generic 64-bit atomic support is selected if needed # config GENERIC_ATOMIC64
lib/Makefile +2 -0
@@ -119,6 +119,8 @@ obj-$(CONFIG_DYNAMIC_DEBUG) += dynamic_debug.o obj-$(CONFIG_NLATTR) += nlattr.o +obj-$(CONFIG_ALF_QUEUE) += alf_queue.o + obj-$(CONFIG_LRU_CACHE) += lru_cache.o obj-$(CONFIG_DMA_API_DEBUG) += dma-debug.o
lib/alf_queue.c new file +47 -0
47 lines not on this page · raw message
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
David Miller
maintainerRe: [RFC PATCH 1/3] lib: adding an Array-based Lock-Free (ALF) queue
From: Jesper Dangaard Brouer <[email protected]>
Date: Wed, 10 Dec 2014 15:15:26 +0100
Quoted 4 lines
include/linux/alf_queue.h new file +4
-0+static inline int +alf_mp_enqueue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{
...
include/linux/alf_queue.h line 116
Quoted 5 lines
include/linux/alf_queue.h new file +5
-0+/* Main Multi-Consumer DEQUEUE */ +static inline int +alf_mc_dequeue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{
I would seriously consider not inlining these.
RFC PATCH 2/3 mm: qmempool - quick queue based memory pool
In reply to Jesper Dangaard BrouerA quick queue-based memory pool, that functions as a cache in-front of kmem_cache SLAB/SLUB allocators. Which allows faster than SLAB/SLUB reuse/caching of fixed size memory elements
The speed gain comes from, the shared storage, using a Lock-Free queue that supports bulk refilling elements (to a percpu cache) with a single cmpxchg. Thus, the (lock-prefixed) cmpxchg cost is amortize over the bulk size.
Qmempool cannot easily replace all kmem_cache usage, because it is restricted in which contexts is can be used in, as the Lock-Free queue is not preemption safe. E.g. only supports GFP_ATOMIC allocations from SLAB.
This version is optimized for usage from softirq context, and cannot be used from hardirq context. Usage from none-softirq requires usage of local_bh_{disable,enable}, which have a fairly high cost.
Performance micro benchmarks against SLUB. First test is fast-path reuse of same element. Second test is allocating 256 element before freeing elements again, this pattern comes from how NIC ring queue cleanups often run.
On CPU E5-2695, CONFIG_PREEMPT=y, showing cost of alloc+free:
SLUB - softirq - none-softirq
fastpath-reuse: 19.563 ns - 7.837 ns - 18.536 ns N(256)-pattern: 45.039 ns - 11.782 ns - 24.186 ns
A significant win for usage from softirq, and a smaller win for none-softirq which requires taking local_bh_{disable,enable}.
---
include/linux/qmempool.h | 205 +++++++++++++++++++++++++++++ mm/Kconfig | 12 ++ mm/Makefile | 1 mm/qmempool.c | 322 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 540 insertions(+), 0 deletions(-) create mode 100644 include/linux/qmempool.h create mode 100644 mm/qmempool.c
include/linux/qmempool.h new file +205 -0
@@ -0,0 +1,205 @@ +/* +* qmempool - a quick queue based mempool +* +* A quick queue-based memory pool, that functions as a cache in-front +* of kmem_cache SLAB/SLUB allocators. Which allows faster than +* SLAB/SLUB reuse/caching of fixed size memory elements +* +* The speed gain comes from, the shared storage, using a Lock-Free +* queue that supports bulk refilling elements (to a percpu cache) +* with a single cmpxchg. Thus, the lock-prefixed cmpxchg cost is +* amortize over the bulk size. +* +* The Lock-Free queue is based on an array (of pointer to elements). +* This make access more cache optimal, as e.g. on 64bit 8 pointers +* can be stored per cache-line (which is superior to a linked list +* approach). Only storing the pointers to elements, is also +* beneficial as we don't touch the elements data. +* +* Qmempool cannot easily replace all kmem_cache usage, because it is +* restricted in which contexts is can be used in, as the Lock-Free +* queue is not preemption safe. This version is optimized for usage +* from softirq context, and cannot be used from hardirq context. +* +* Only support GFP_ATOMIC allocations from SLAB. +* +* Copyright (C) 2014, Red Hat, Inc., Jesper Dangaard Brouer +* for licensing details see kernel-base/COPYING +*/ + +#ifndef _LINUX_QMEMPOOL_H +#define _LINUX_QMEMPOOL_H + +#include <linux/alf_queue.h> +#include <linux/prefetch.h> +#include <linux/hardirq.h> + +/* Bulking is an essential part of the performance gains as this +* amortize the cost of cmpxchg ops used when accessing sharedq +*/ +#define QMEMPOOL_BULK 16 +#define QMEMPOOL_REFILL_MULTIPLIER 2 + +struct qmempool_percpu { +struct alf_queue *localq; +}; + +struct qmempool { +/* The shared queue (sharedq) is a Multi-Producer-Multi-Consumer +* queue where access is protected by an atomic cmpxchg operation. +* The queue support bulk transfers, which amortize the cost +* of the atomic cmpxchg operation. +*/ +struct alf_queue *sharedq; + +/* Per CPU local "cache" queues for faster atomic free access. +* The local queues (localq) are Single-Producer-Single-Consumer +* queues as they are per CPU. +*/ +struct qmempool_percpu __percpu *percpu; + +/* Backed by some SLAB kmem_cache */ +struct kmem_cache *kmem; + +/* Setup */ +uint32_t prealloc; +gfp_t gfp_mask; +}; + +extern void qmempool_destroy (struct qmempool *pool); +extern struct qmempool *qmempool_create ( +uint32_t localq_sz,uint32_t sharedq_sz,uint32_t prealloc, +struct kmem_cache *kmem,gfp_t gfp_mask); + +extern void *__qmempool_alloc_from_sharedq ( +struct qmempool *pool,gfp_t gfp_mask,struct alf_queue *localq); +extern void __qmempool_free_to_sharedq (void *elem,struct qmempool *pool, +struct alf_queue *localq); + +/* The percpu variables (SPSC queues) needs preempt protection, and +* the shared MPMC queue also needs protection against the same CPU +* access the same queue. +* +* Specialize and optimize the qmempool to run from softirq. +* Don't allow qmempool to be used from interrupt context. +* +* IDEA: When used from softirq, take advantage of the protection +* softirq gives. A softirq will never preempt another softirq, +* running on the same CPU. The only event that can preempt a softirq +* is an interrupt handler (and perhaps we don't need to support +* calling qmempool from an interrupt). Another softirq, even the +* same one, can run on another CPU however, but these helpers are +* only protecting our percpu variables. +* +* Thus, our percpu variables are safe if current the CPU is the one +* serving the softirq (tested via in_serving_softirq()), like: +* +* if (!in_serving_softirq()) +* local_bh_disable(); +* +* This makes qmempool very fast, when accesses from softirq, but +* slower when accessed outside softirq. The other contexts need to +* disable bottom-halves "bh" via local_bh_{disable,enable} (which on +* have been measured add cost if 7.5ns on CPU E5-2695). +* +* MUST not be used from interrupt context, when relying on softirq usage. +*/ +static inline int __qmempool_preempt_disable (void ) +{ +int in_serving_softirq =in_serving_softirq (); + +if (!in_serving_softirq) +local_bh_disable (); + +return in_serving_softirq; +} + +static inline void __qmempool_preempt_enable (int in_serving_softirq) +{ +if (!in_serving_softirq) +local_bh_enable (); +} + +/* Elements - alloc and free functions are inlined here for +* performance reasons, as the per CPU lockless access should be as +* fast as possible. +*/ + +/* Main allocation function +* +* Caller must make sure this is called from a preemptive safe context +*/ +static inline void *main_qmempool_alloc (struct qmempool *pool,gfp_t gfp_mask) +{ +/* NUMA considerations, for now the numa node is not handles, +* this could be handled via e.g. numa_mem_id() +*/ +void *elem; +struct qmempool_percpu *cpu; +int num; + +/* 1. attempt get element from local per CPU queue */ + cpu =this_cpu_ptr (pool->percpu); + num =alf_sc_dequeue (cpu->localq, (void **)&elem,1 ); +if (num ==1 )/* Succes: alloc elem by deq from localq cpu cache */ +return elem; + +/* 2. attempt get element from shared queue. This involves +* refilling the localq for next round. Side-effect can be +* alloc from SLAB. +*/ + elem =__qmempool_alloc_from_sharedq (pool, gfp_mask, cpu->localq); +return elem; +} + +static inline void *__qmempool_alloc (struct qmempool *pool,gfp_t gfp_mask) +{ +void *elem; +int state; + + state =__qmempool_preempt_disable (); + elem =main_qmempool_alloc (pool, gfp_mask); +__qmempool_preempt_enable (state); +return elem; +} + +static inline void *__qmempool_alloc_softirq (struct qmempool *pool, +gfp_t gfp_mask) +{ +return main_qmempool_alloc (pool, gfp_mask); +} + +/* Main free function */ +static inline void __qmempool_free (struct qmempool *pool,void *elem) +{ +struct qmempool_percpu *cpu; +int num; +int state; + +/* NUMA considerations, how do we make sure to avoid caching +* elements from a different NUMA node. +*/ + state =__qmempool_preempt_disable (); + +/* 1. attempt to free/return element to local per CPU queue */ + cpu =this_cpu_ptr (pool->percpu); + num =alf_sp_enqueue (cpu->localq, &elem,1 ); +if (num ==1 )/* success: element free'ed by enqueue to localq */ + goto done; + +/* 2. localq cannot store more elements, need to return some +* from localq to sharedq, to make room. Side-effect can be +* free to SLAB. +*/ +__qmempool_free_to_sharedq (elem, pool, cpu->localq); + +done: +__qmempool_preempt_enable (state); +} + +/* API users can choose to use "__" prefixed versions for inlining */ +extern void *qmempool_alloc (struct qmempool *pool,gfp_t gfp_mask); +extern void *qmempool_alloc_softirq (struct qmempool *pool,gfp_t gfp_mask); +extern void qmempool_free (struct qmempool *pool,void *elem); + +#endif /* _LINUX_QMEMPOOL_H */
mm/Kconfig +12 -0
@@ -618,3 +618,15 @@ config MAX_STACK_SIZE_MB changed to a smaller value in which case that is used. A sane initial value is 80 MB. + +config QMEMPOOL + bool "Quick queue based mempool (qmempool)" + default y + select ALF_QUEUE + help + A mempool designed for faster than SLAB/kmem_cache + reuse/caching of fixed size memory elements. Works as a + caching layer in-front of existing kmem_cache SLABs. Speed + is achieved by _bulk_ refilling percpu local cache, from a + Lock-Free queue requiring a single (locked) cmpxchg per bulk + transfer, thus amortizing the cost of the cmpxchg.
mm/Makefile +1 -0
@@ -69,3 +69,4 @@ obj-$(CONFIG_ZSMALLOC) += zsmalloc.o obj-$(CONFIG_GENERIC_EARLY_IOREMAP) += early_ioremap.o obj-$(CONFIG_CMA) += cma.o obj-$(CONFIG_MEMORY_BALLOON) += balloon_compaction.o +obj-$(CONFIG_QMEMPOOL) += qmempool.o
mm/qmempool.c new file +322 -0
322 lines not on this page · raw message
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 3/3 net: use qmempool in-front of sk_buff kmem_cache
In reply to Jesper Dangaard BrouerThis patch uses qmempool for faster than SLAB caching of SKBs.
Only use this caching in connection with napi_alloc_skb() which runs in softirq context. This softirq context provides the needed protection for qmempool and the underlying alf_queue.
Current caching settings are max 32 elements per CPU, which is 8192 bytes given SKB is SLAB_HWCACHE_ALIGN'ed. The shared queue max limit is 1024 which corresponds to worst-case 263KB memory usage. Systems with a NR_CPUS <= 8 will get a smaller max shared queue.
Benchmarked on a E5-2695 12-cores (no-HT) with ixgbe. Baseline is Alex'es napi_alloc_skb patchset.
Single flow/CPU, early drop in iptables RAW table (fast path compare):
* baseline: 3,159,160 pps
* qmempool: 3,282,508 pps
- Diff to baseline: +123348 pps => -11.89 ns
IP-forward single flow/cpu (slower path compare):
* baseline: 1,137,284 pps
* qmempool: 1,191,856 pps
- Diff to baseline: +54572 pps => -40.26 ns
Some of the improvements also come from qmempool_{alloc,free} have smaller code size than kmem_cache_{alloc,free}, which helps reduce instruction-cache misses.
Also did some scaling tests, to stress qmempool sharedq allocs (which stress the alf_queue's concurrency).
IP-forward MULTI flow/cpu (12 CPUs E5-2695 no-HT, 12 HWQs):
* baseline: 11,946,666 pps
* qmempool: 11,988,042 pps
- Diff to baseline: +41376 pps => -0.29 ns
---
include/linux/skbuff.h | 4 +++- net/core/dev.c | 5 ++++- net/core/skbuff.c | 43 ++++++++++++++++++++++++++++++++++++++----- 3 files changed, 45 insertions(+), 7 deletions(-)
include/linux/skbuff.h +3 -1
@@ -152,6 +152,7 @@ struct scatterlist;struct pipe_inode_info ;struct iov_iter ;struct napi_struct ; +struct qmempool ;#if defined(CONFIG_NF_CONNTRACK ) || defined(CONFIG_NF_CONNTRACK_MODULE ) struct nf_conntrack {
@@ -557,8 +558,8 @@ struct sk_buff { fclone:2, peeked:1, head_frag:1, + qmempool:1, xmit_more:1; -/* one bit hole */ kmemcheck_bitfield_end (flags1);/* fields enclosed in headers_start/headers_end are copied
@@ -755,6 +756,7 @@ void skb_tx_error(struct sk_buff *skb);void consume_skb (struct sk_buff *skb);void __kfree_skb (struct sk_buff *skb);extern struct kmem_cache *skbuff_head_cache; +extern struct qmempool *skbuff_head_pool;void kfree_skb_partial (struct sk_buff *skb,bool head_stolen); bool skb_try_coalesce(struct sk_buff *to, struct sk_buff *from,
net/core/dev.c +4 -1
@@ -135,6 +135,7 @@#include <linux/if_macvlan.h> #include <linux/errqueue.h> #include <linux/hrtimer.h> +#include <linux/qmempool.h> #include "net-sysfs.h"
@@ -4125,7 +4126,9 @@ static gro_result_t napi_skb_finish(gro_result_t ret, struct sk_buff *skb)case GRO_MERGED_FREE :if (NAPI_GRO_CB (skb)->free ==NAPI_GRO_FREE_STOLEN_HEAD ) -kmem_cache_free (skbuff_head_cache, skb); + (skb->qmempool) ? +qmempool_free (skbuff_head_pool, skb) : +kmem_cache_free (skbuff_head_cache, skb);else __kfree_skb (skb);break ;
net/core/skbuff.c +38 -5
112 lines not on this page · raw message
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RE: [RFC PATCH 0/3] Faster than SLAB caching of SKBs with qmempool (backed by alf_queue)
In reply to Jesper Dangaard BrouerRnJvbTogSmVzcGVyIERhbmdhYXJkIEJyb3Vlcg0KPiBUaGUgbmV0d29yayBzdGFjayBoYXZlIHNv bWUgdXNlLWNhc2VzIHRoYXQgcHV0cyBzb21lIGV4dHJlbWUgZGVtYW5kcw0KPiBvbiB0aGUgbWVt b3J5IGFsbG9jYXRvci4gIE9uZSB1c2UtY2FzZSwgMTBHYml0L3Mgd2lyZXNwZWVkIGF0IHNtYWxs ZXN0DQo+IHBhY2tldCBzaXplWzFdLCByZXF1aXJlcyBoYW5kbGluZyBhIHBhY2tldCBldmVyeSA2 Ny4yIG5zIChuYW5vc2VjKS4NCj4gDQo+IE1pY3JvIGJlbmNobWFya2luZ1syXSB0aGUgU0xVQiBh bGxvY2F0b3IgKHdpdGggc2tiIHNpemUgMjU2Ynl0ZXMNCj4gZWxlbWVudHMpLCBzaG93ICJmYXN0 LXBhdGgiIGluc3RhbnQgcmV1c2Ugb25seSBjb3N0cyAxOSBucywgYnV0IGENCj4gY2xvc2VyIHRv IG5ldHdvcmsgdXNhZ2UgcGF0dGVybiBzaG93IHRoZSBjb3N0IHJpc2UgdG8gNDUgbnMuDQo+IA0K PiBUaGlzIHBhdGNoc2V0IGludHJvZHVjZSBhIHF1aWNrIG1lbXBvb2wgKHFtZW1wb29sKSwgd2hp Y2ggd2hlbiB1c2VkDQo+IGluLWZyb250IG9mIHRoZSBTS0IgKHNrX2J1ZmYpIGttZW1fY2FjaGUs IHNhdmVzIDEyIG5zIG9uICJmYXN0LXBhdGgiDQo+IGRyb3AgaW4gaXB0YWJsZXMgInJhdyIgdGFi bGUsIGJ1dCBtb3JlIGltcG9ydGFudGx5IHNhdmVzIDQwIG5zIHdpdGgNCj4gSVAtZm9yd2FyZGlu Zywgd2hpY2ggd2VyZSBoaXR0aW5nIHRoZSBzbG93ZXIgU0xVQiB1c2UtY2FzZS4NCj4gDQo+IA0K PiBPbmUgb2YgdGhlIGJ1aWxkaW5nIGJsb2NrcyBmb3IgYWNoaWV2aW5nIHRoaXMgc3BlZWR1cCBp cyBhIGNtcHhjaGcNCj4gYmFzZWQgTG9jay1GcmVlIHF1ZXVlIHRoYXQgc3VwcG9ydHMgYnVsa2lu ZywgbmFtZWQgYWxmX3F1ZXVlIGZvcg0KPiBBcnJheS1iYXNlZCBMb2NrLUZyZWUgcXVldWUuICBC eSBidWxraW5nIGVsZW1lbnRzIChwb2ludGVycykgZnJvbSB0aGUNCj4gcXVldWUsIHRoZSBjb3N0 IG9mIHRoZSBjbXB4Y2hnIChhcHByb3ggOCBucykgaXMgYW1vcnRpemVkIG92ZXIgc2V2ZXJhbA0K PiBlbGVtZW50cy4NCg0KSXQgc2VlbXMgdG8gbWUgdGhhdCB0aGVzZSBpbXByb3ZlbWVudHMgY291 bGQgYmUgYWRkZWQgdG8gdGhlDQp1bmRlcmx5aW5nIGFsbG9jYXRvciBpdHNlbGYuDQpOZXN0aW5n IGFsbG9jYXRvcnMgZG9lc24ndCByZWFsbHkgc2VlbSByaWdodCB0byBtZS4NCg0KCURhdmlkDQoN Cg==
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [RFC PATCH 0/3] Faster than SLAB caching of SKBs with qmempool (backed by alf_queue)
Quoted 21 lines · On Wed, 10 Dec 2014 14:22:22 +0000 David Laight <[email protected]> wrote:
From: Jesper Dangaard Brouer
Quoted 14 lines
The network stack have some use-cases that puts some extreme demands on the memory allocator. One use-case, 10Gbit/s wirespeed at smallest packet size[1], requires handling a packet every 67.2 ns (nanosec).
Micro benchmarking[2] the SLUB allocator (with skb size 256bytes elements), show "fast-path" instant reuse only costs 19 ns, but a closer to network usage pattern show the cost rise to 45 ns.
This patchset introduce a quick mempool (qmempool), which when used in-front of the SKB (
sk_buff)kmem_cache, saves 12 ns on "fast-path" drop in iptables "raw" table, but more importantly saves 40 ns with IP-forwarding, which were hitting the slower SLUB use-case.Quoted 5 lines
One of the building blocks for achieving this speedup is a cmpxchg based Lock-Free queue that supports bulking, named
alf_queuefor Array-based Lock-Free queue. By bulking elements (pointers) from the queue, the cost of the cmpxchg (approx 8 ns) is amortized over several elements.
Quoted 3 lines
It seems to me that these improvements could be added to the underlying allocator itself.
Nesting allocators doesn't really seem right to me.
Yes, I would very much like to see these ideas integrated into the underlying allocators (hence addressing the mm-list).
This patchset demonstrates that it is possible to do something faster than the existing SLUB allocator. Which the network stack have a need for.
Signature · 11 lines
Best regards, Jesper Dangaard Brouer MSc.CS, Sr. Network Kernel Developer at Red Hat Author of http://www.iptv-analyzer.org LinkedIn: http://www.linkedin.com/in/brouer -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [RFC PATCH 0/3] Faster than SLAB caching of SKBs with qmempool (backed by alf_queue)
In reply to Jesper Dangaard BrouerQuoted 1 line · Jesper Dangaard Brouer
Patch1:
alf_queue(Lock-Free queue)
For some reason that key patch is not in my linux-mm archives nor in my inbox.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [RFC PATCH 0/3] Faster than SLAB caching of SKBs with qmempool (backed by alf_queue)
Quoted 6 lines · On Wed, 10 Dec 2014 09:17:32 -0600 (CST) Christoph Lameter <[email protected]> wrote:
Quoted 1 line · Jesper Dangaard Brouer
Patch1:
alf_queue(Lock-Free queue)For some reason that key patch is not in my linux-mm archives nor in my inbox.
That is very strange! I did notice that it was somehow delayed in
showing up on gmane.org (http://thread.gmane.org/gmane.linux.network/342347/focus=126148)
and didn't show up on netdev either...
Inserting it below (hoping my email client does not screw it up):
[PATCH RFC] lib: adding an Array-based Lock-Free (ALF) queue
From: Jesper Dangaard Brouer <[email protected]>
This Array-based Lock-Free (ALF) queue, is a very fast bounded Producer-Consumer queue, supporting bulking. The MPMC (Multi-Producer/Multi-Consumer) variant uses a locked cmpxchg, but the cost can be amorized by utilizing bulk enqueue/dequeue.
Results on x86_64 CPU E5-2695, for variants:
MPMC = Multi-Producer-Multi-Consumer
SPSC = Single-Producer-Single-Consumer
(none-bulking): per element cost MPMC and SPSC
MPMC -- SPSC
simple : 9.519 ns -- 1.282 ns
multi(step:128): 12.905 ns -- 2.240 ns
The majority of the cost is associated with the locked cmpxchg in the MPMC variant. Bulking helps amortize this cost:
(bulking) cost per element comparing MPMC -> SPSC:
MPMC -- SPSC
bulk2 : 5.849 ns -- 1.748 ns
bulk3 : 4.102 ns -- 1.531 ns
bulk4 : 3.281 ns -- 1.383 ns
bulk6 : 2.530 ns -- 1.238 ns
bulk8 : 2.125 ns -- 1.196 ns
bulk16: 1.552 ns -- 1.109 ns
Joint work with Hannes Frederic Sowa.
----
Correctness of memory barries on different arch's need to be evaluated.
The API might need some adjustments/discussions regarding:
1) the semantics of enq/deq when doing bulking, choosing what to do when e.g. a bulk enqueue cannot fit fully.
2) some better way to detect miss-use of API, e.g. using single-enqueue variant function call on a multi-enqueue variant data structure. Now no detection happens.
---
include/linux/alf_queue.h | 303 +++++++++++++++++++++++++++++++++++++++++++++ lib/Kconfig | 13 ++ lib/Makefile | 2 lib/alf_queue.c | 47 +++++++ 4 files changed, 365 insertions(+), 0 deletions(-) create mode 100644 include/linux/alf_queue.h create mode 100644 lib/alf_queue.c
include/linux/alf_queue.h new file +303 -0
@@ -0,0 +1,303 @@ +#ifndef _LINUX_ALF_QUEUE_H +#define _LINUX_ALF_QUEUE_H +/* linux/alf_queue.h +* +* ALF: Array-based Lock-Free queue +* +* Queue properties +* - Array based for cache-line optimization +* - Bounded by the array size +* - FIFO Producer/Consumer queue, no queue traversal supported +* - Very fast +* - Designed as a queue for pointers to objects +* - Bulk enqueue and dequeue support +* - Supports combinations of Multi and Single Producer/Consumer +* +* Copyright (C) 2014, Red Hat, Inc., +* by Jesper Dangaard Brouer and Hannes Frederic Sowa +* for licensing details see kernel-base/COPYING +*/ +#include <linux/compiler.h> +#include <linux/kernel.h> + +struct alf_actor { +u32 head; +u32 tail; +}; + +struct alf_queue { +u32 size; +u32 mask; +u32 flags; +struct alf_actor producer____cacheline_aligned_in_smp ; +struct alf_actor consumer____cacheline_aligned_in_smp ; +void *ring[0 ]____cacheline_aligned_in_smp ; +}; + +struct alf_queue *alf_queue_alloc (u32 size,gfp_t gfp); +void alf_queue_free (struct alf_queue *q); + +/* Helpers for LOAD and STORE of elements, have been split-out because: +* 1. They can be reused for both "Single" and "Multi" variants +* 2. Allow us to experiment with (pipeline) optimizations in this area. +*/ +static inline void +__helper_alf_enqueue_store (u32 p_head,struct alf_queue *q, +void **ptr,const u32 n) +{ +int i, index = p_head; + +for (i =0 ; i < n; i++, index++) + q->ring[index & q->mask] = ptr[i]; +} + +static inline void +__helper_alf_dequeue_load (u32 c_head,struct alf_queue *q, +void **ptr,const u32 elems) +{ +int i, index = c_head; + +for (i =0 ; i < elems; i++, index++) + ptr[i] = q->ring[index & q->mask]; +} + +/* Main Multi-Producer ENQUEUE +* +* Even-though current API have a "fixed" semantics of aborting if it +* cannot enqueue the full bulk size. Users of this API should check +* on the returned number of enqueue elements match, to verify enqueue +* was successful. This allow us to introduce a "variable" enqueue +* scheme later. +* +* Not preemption safe. Multiple CPUs can enqueue elements, but the +* same CPU is not allowed to be preempted and access the same +* queue. Due to how the tail is updated, this can result in a soft +* lock-up. (Same goes for alf_mc_dequeue). +*/ +static inline int +alf_mp_enqueue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{ +u32 p_head, p_next, c_tail, space; + +/* Reserve part of the array for enqueue STORE/WRITE */ +do { + p_head =ACCESS_ONCE (q->producer.head); + c_tail =ACCESS_ONCE (q->consumer.tail); + + space = q->size + c_tail - p_head; +if (n > space) +return 0 ; + + p_next = p_head + n; + } +while (unlikely (cmpxchg (&q->producer.head, p_head, p_next) != p_head)); + +/* STORE the elems into the queue array */ +__helper_alf_enqueue_store (p_head, q, ptr, n); +smp_wmb ();/* Write-Memory-Barrier matching dequeue LOADs */ + +/* Wait for other concurrent preceding enqueues not yet done, +* this part make us none-wait-free and could be problematic +* in case of congestion with many CPUs +*/ +while (unlikely (ACCESS_ONCE (q->producer.tail) != p_head)) +cpu_relax (); +/* Mark this enq done and avail for consumption */ +ACCESS_ONCE (q->producer.tail) = p_next; + +return n; +} + +/* Main Multi-Consumer DEQUEUE */ +static inline int +alf_mc_dequeue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{ +u32 c_head, c_next, p_tail, elems; + +/* Reserve part of the array for dequeue LOAD/READ */ +do { + c_head =ACCESS_ONCE (q->consumer.head); + p_tail =ACCESS_ONCE (q->producer.tail); + + elems = p_tail - c_head; + +if (elems ==0 ) +return 0 ; +else + elems =min (elems, n); + + c_next = c_head + elems; + } +while (unlikely (cmpxchg (&q->consumer.head, c_head, c_next) != c_head)); + +/* LOAD the elems from the queue array. +* We don't need a smb_rmb() Read-Memory-Barrier here because +* the above cmpxchg is an implied full Memory-Barrier. +*/ +__helper_alf_dequeue_load (c_head, q, ptr, elems); + +/* Archs with weak Memory Ordering need a memory barrier here. +* As the STORE to q->consumer.tail, must happen after the +* dequeue LOADs. Dequeue LOADs have a dependent STORE into +* ptr, thus a smp_wmb() is enough. Paired with enqueue +* implicit full-MB in cmpxchg. +*/ +smp_wmb (); + +/* Wait for other concurrent preceding dequeues not yet done */ +while (unlikely (ACCESS_ONCE (q->consumer.tail) != c_head)) +cpu_relax (); +/* Mark this deq done and avail for producers */ +ACCESS_ONCE (q->consumer.tail) = c_next; + +return elems; +} + +/* #define ASSERT_DEBUG_SPSC 1 */ +#ifndef ASSERT_DEBUG_SPSC +#define ASSERT (x) do { } while (0) +#else +#define ASSERT (x) \ + do { \ + if (unlikely(!(x))) { \ + pr_crit("Assertion failed %s:%d: \"%s\"\n", \ + __FILE__, __LINE__, #x); \ + BUG(); \ + } \ + } while (0) +#endif + +/* Main SINGLE Producer ENQUEUE +* caller MUST make sure preemption is disabled +*/ +static inline int +alf_sp_enqueue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{ +u32 p_head, p_next, c_tail, space; + +/* Reserve part of the array for enqueue STORE/WRITE */ + p_head = q->producer.head; +smp_rmb ();/* for consumer.tail write, making sure deq loads are done */ + c_tail =ACCESS_ONCE (q->consumer.tail); + + space = q->size + c_tail - p_head; +if (n > space) +return 0 ; + + p_next = p_head + n; +ASSERT (ACCESS_ONCE (q->producer.head) == p_head); + q->producer.head = p_next; + +/* STORE the elems into the queue array */ +__helper_alf_enqueue_store (p_head, q, ptr, n); +smp_wmb ();/* Write-Memory-Barrier matching dequeue LOADs */ + +/* Assert no other CPU (or same CPU via preemption) changed queue */ +ASSERT (ACCESS_ONCE (q->producer.tail) == p_head); + +/* Mark this enq done and avail for consumption */ +ACCESS_ONCE (q->producer.tail) = p_next; + +return n; +} + +/* Main SINGLE Consumer DEQUEUE +* caller MUST make sure preemption is disabled +*/ +static inline int +alf_sc_dequeue(const u32 n; +struct alf_queue *q,void *ptr[n],const u32 n) +{ +u32 c_head, c_next, p_tail, elems; + +/* Reserve part of the array for dequeue LOAD/READ */ + c_head = q->consumer.head; + p_tail =ACCESS_ONCE (q->producer.tail); + + elems = p_tail - c_head; + +if (elems ==0 ) +return 0 ; +else + elems =min (elems, n); + + c_next = c_head + elems; +ASSERT (ACCESS_ONCE (q->consumer.head) == c_head); + q->consumer.head = c_next; + +smp_rmb ();/* Read-Memory-Barrier matching enq STOREs */ +__helper_alf_dequeue_load (c_head, q, ptr, elems); + +/* Archs with weak Memory Ordering need a memory barrier here. +* As the STORE to q->consumer.tail, must happen after the +* dequeue LOADs. Dequeue LOADs have a dependent STORE into +* ptr, thus a smp_wmb() is enough. +*/ +smp_wmb (); + +/* Assert no other CPU (or same CPU via preemption) changed queue */ +ASSERT (ACCESS_ONCE (q->consumer.tail) == c_head); + +/* Mark this deq done and avail for producers */ +ACCESS_ONCE (q->consumer.tail) = c_next; + +return elems; +} + +static inline bool +alf_queue_empty (struct alf_queue *q) +{ +u32 c_tail =ACCESS_ONCE (q->consumer.tail); +u32 p_tail =ACCESS_ONCE (q->producer.tail); + +/* The empty (and initial state) is when consumer have reached +* up with producer. +* +* DOUBLE-CHECK: Should we use producer.head, as this indicate +* a producer is in-progress(?) +*/ +return c_tail == p_tail; +} + +static inline int +alf_queue_count (struct alf_queue *q) +{ +u32 c_head =ACCESS_ONCE (q->consumer.head); +u32 p_tail =ACCESS_ONCE (q->producer.tail); +u32 elems; + +/* Due to u32 arithmetic the values are implicitly +* masked/modulo 32-bit, thus saving one mask operation +*/ + elems = p_tail - c_head; +/* Thus, same as: +* elems = (p_tail - c_head) & q->mask; +*/ +return elems; +} + +static inline int +alf_queue_avail_space (struct alf_queue *q) +{ +u32 p_head =ACCESS_ONCE (q->producer.head); +u32 c_tail =ACCESS_ONCE (q->consumer.tail); +u32 space; + +/* The max avail space is q->size and +* the empty state is when (consumer == producer) +*/ + +/* Due to u32 arithmetic the values are implicitly +* masked/modulo 32-bit, thus saving one mask operation +*/ + space = q->size + c_tail - p_head; +/* Thus, same as: +* space = (q->size + c_tail - p_head) & q->mask; +*/ +return space; +} + +#endif /* _LINUX_ALF_QUEUE_H */
lib/Kconfig +13 -0
@@ -439,6 +439,19 @@ config NLATTR bool # +# ALF queue +# +config ALF_QUEUE + bool "ALF: Array-based Lock-Free (Producer-Consumer) queue" + default y + help + This Array-based Lock-Free (ALF) queue, is a very fast + bounded Producer-Consumer queue, supporting bulking. The + MPMC (Multi-Producer/Multi-Consumer) variant uses a locked + cmpxchg, but the cost can be amorized by utilizing bulk + enqueue/dequeue. + +# # Generic 64-bit atomic support is selected if needed # config GENERIC_ATOMIC64
lib/Makefile +2 -0
@@ -119,6 +119,8 @@ obj-$(CONFIG_DYNAMIC_DEBUG) += dynamic_debug.o obj-$(CONFIG_NLATTR) += nlattr.o +obj-$(CONFIG_ALF_QUEUE) += alf_queue.o + obj-$(CONFIG_LRU_CACHE) += lru_cache.o obj-$(CONFIG_DMA_API_DEBUG) += dma-debug.o
lib/alf_queue.c new file +47 -0
47 lines not on this page · raw message
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [RFC PATCH 0/3] Faster than SLAB caching of SKBs with qmempool (backed by alf_queue)
Quoted 3 lines · Jesper Dangaard Brouer
That is very strange! I did notice that it was somehow delayed in
showing up on gmane.org (http://thread.gmane.org/gmane.linux.network/342347/focus=126148)
and didn't show up on netdev either...
It finally got through.
Re: [RFC PATCH 0/3] Faster than SLAB caching of SKBs with qmempool (backed by alf_queue)
In reply to Jesper Dangaard BrouerQuoted 5 lines · Jesper Dangaard Brouer
One of the building blocks for achieving this speedup is a cmpxchg based Lock-Free queue that supports bulking, named
alf_queuefor Array-based Lock-Free queue. By bulking elements (pointers) from the queue, the cost of the cmpxchg (approx 8 ns) is amortized over several elements.
This is a bit of an issue since the design of the SLUB allocator is such that you should pick up an object, apply some processing and then take the next one. The fetching of an object warms up the first cacheline and this is tied into the way free objects are linked in SLUB.
So a bulk fetch from SLUB will not that effective and cause the touching of many cachelines if we are dealing with just a few objects. If we are looking at whole slab pages with all objects then SLUB can be effective since we do not have to build up the linked pointer structure in each page. SLAB has a different architecture there and a bulk fetch there is possible without touching objects even for small sets since the freelist management is separate from the objects.
If you do this bulking then you will later access cache cold objects? Doesnt that negate the benefit that you gain? Or are these objects written to by hardware and therefore by necessity cache cold?
We could provide a faster bulk alloc/free function.
int kmem_cache_alloc_array(struct kmem_cache *s, gfp_t flags,
size_t objects, void **array)
and this could be optimized by each slab allocator to provide fast population of objects in that array. We then assume that the number of objects is in the hundreds or so right?
The corresponding free function
void kmem_cache_free_array(struct kmem_cache *s,
size_t objects, void **array)
I think the queue management of the array can be improved by using a similar technique as used the SLUB allocator using the cmpxchg_local. cmpxchg_local is much faster than a full cmpxchg and we are operating on per cpu structures anyways. So the overhead could still be reduced.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Re: [RFC PATCH 0/3] Faster than SLAB caching of SKBs with qmempool (backed by alf_queue)
Quoted 21 lines · On Wed, 10 Dec 2014 13:51:32 -0600 (CST) Christoph Lameter <[email protected]> wrote:
Quoted 5 lines · Jesper Dangaard Brouer
One of the building blocks for achieving this speedup is a cmpxchg based Lock-Free queue that supports bulking, named
alf_queuefor Array-based Lock-Free queue. By bulking elements (pointers) from the queue, the cost of the cmpxchg (approx 8 ns) is amortized over several elements.This is a bit of an issue since the design of the SLUB allocator is such that you should pick up an object, apply some processing and then take the next one. The fetching of an object warms up the first cacheline and this is tied into the way free objects are linked in SLUB.
So a bulk fetch from SLUB will not that effective and cause the touching of many cachelines if we are dealing with just a few objects. If we are looking at whole slab pages with all objects then SLUB can be effective since we do not have to build up the linked pointer structure in each page. SLAB has a different architecture there and a bulk fetch there is possible without touching objects even for small sets since the freelist management is separate from the objects.
Quoted 3 lines
If you do this bulking then you will later access cache cold objects? Doesnt that negate the benefit that you gain? Or are these objects written to by hardware and therefore by necessity cache cold?
Cache warmup is a concern, but perhaps it's the callers responsibility to prefetch for their use-case. For qmempool I do have patches that prefetch elems when going from the sharedq to the localq (per CPU), but I didn't see much gain, and I could prove my point (of being faster than slab) without it. And I would use/need the slab bulk interface to add elems to sharedq which I consider semi-cache cold.
Quoted 4 lines
We could provide a faster bulk alloc/free function.
int kmem_cache_alloc_array(struct
kmem_cache*s,gfp_tflags,
size_tobjects, void **array)
I like it :-)
Quoted 3 lines
and this could be optimized by each slab allocator to provide fast population of objects in that array. We then assume that the number of objects is in the hundreds or so right?
I'm already seeing a benefit with 16 packets alloc/free "bulking".
On RX we have a "budget" of 64 packets/descriptors (taken from the NIC RX ring) that need SKBs.
On TX packets are put into the TX ring, and later at TX completion the TX ring is cleaned up, as many as 256 (as e.g. in the ixgbe driver).
Scientific articles on userspace networking (like netmap) report that they need at least 8 packet bulking to see wirespeed 10G at 64 bytes.
Quoted 10 lines
The corresponding free function
void kmem_cache_free_array(struct
kmem_cache*s,
size_tobjects, void **array)I think the queue management of the array can be improved by using a similar technique as used the SLUB allocator using the
cmpxchg_local.cmpxchg_localis much faster than a full cmpxchg and we are operating on per cpu structures anyways. So the overhead could still be reduced.
I think you missed that the per cpu localq is already not using cmpxchg (it is a SPSC queue). The sharedq (MPMC queue) does need and use the locked cmpxchg.
Signature · 11 lines
Best regards, Jesper Dangaard Brouer MSc.CS, Sr. Network Kernel Developer at Red Hat Author of http://www.iptv-analyzer.org LinkedIn: http://www.linkedin.com/in/brouer -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
David Miller
maintainerFrom: Alexander Duyck <[email protected]>
Date: Tue, 09 Dec 2014 19:40:35 -0800
Quoted 4 lines
This patch series implements a means of allocating page fragments without the need for the local_irq_save/restore in
__netdev_alloc_frag. By doing this I am able to decrease packet processing time by 11ns per packet in my test environment.
Looks great, series applied, thanks Alex.