The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/sys/buf_ring.h

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /**************************************************************************
    2  *
    3  * Copyright (c) 2007-2009 Kip Macy kmacy@freebsd.org
    4  * All rights reserved.
    5  *
    6  * Redistribution and use in source and binary forms, with or without
    7  * modification, are permitted provided that the following conditions are met:
    8  *
    9  * 1. Redistributions of source code must retain the above copyright notice,
   10  *    this list of conditions and the following disclaimer.
   11  *
   12  * 2. The name of Kip Macy nor the names of other
   13  *    contributors may be used to endorse or promote products derived from
   14  *    this software without specific prior written permission.
   15  *
   16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
   20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   26  * POSSIBILITY OF SUCH DAMAGE.
   27  *
   28  * $FreeBSD: releng/8.0/sys/sys/buf_ring.h 193848 2009-06-09 19:19:16Z kmacy $
   29  *
   30  ***************************************************************************/
   31 
   32 #ifndef _SYS_BUF_RING_H_
   33 #define _SYS_BUF_RING_H_
   34 
   35 #include <machine/cpu.h>
   36 
   37 #if defined(INVARIANTS) && !defined(DEBUG_BUFRING)
   38 #define DEBUG_BUFRING 1
   39 #endif
   40 
   41 #ifdef DEBUG_BUFRING
   42 #include <sys/lock.h>
   43 #include <sys/mutex.h>
   44 #endif
   45 
   46 struct buf_ring {
   47         volatile uint32_t       br_prod_head;
   48         volatile uint32_t       br_prod_tail;   
   49         int                     br_prod_size;
   50         int                     br_prod_mask;
   51         uint64_t                br_drops;
   52         uint64_t                br_prod_bufs;
   53         uint64_t                br_prod_bytes;
   54         /*
   55          * Pad out to next L2 cache line
   56          */
   57         uint64_t                _pad0[11];
   58 
   59         volatile uint32_t       br_cons_head;
   60         volatile uint32_t       br_cons_tail;
   61         int                     br_cons_size;
   62         int                     br_cons_mask;
   63         
   64         /*
   65          * Pad out to next L2 cache line
   66          */
   67         uint64_t                _pad1[14];
   68 #ifdef DEBUG_BUFRING
   69         struct mtx              *br_lock;
   70 #endif  
   71         void                    *br_ring[0];
   72 };
   73 
   74 /*
   75  * multi-producer safe lock-free ring buffer enqueue
   76  *
   77  */
   78 static __inline int
   79 buf_ring_enqueue_bytes(struct buf_ring *br, void *buf, int nbytes)
   80 {
   81         uint32_t prod_head, prod_next;
   82         uint32_t cons_tail;
   83         int success;
   84 #ifdef DEBUG_BUFRING
   85         int i;
   86         for (i = br->br_cons_head; i != br->br_prod_head;
   87              i = ((i + 1) & br->br_cons_mask))
   88                 if(br->br_ring[i] == buf)
   89                         panic("buf=%p already enqueue at %d prod=%d cons=%d",
   90                             buf, i, br->br_prod_tail, br->br_cons_tail);
   91 #endif  
   92         critical_enter();
   93         do {
   94                 prod_head = br->br_prod_head;
   95                 cons_tail = br->br_cons_tail;
   96 
   97                 prod_next = (prod_head + 1) & br->br_prod_mask;
   98                 
   99                 if (prod_next == cons_tail) {
  100                         critical_exit();
  101                         return (ENOBUFS);
  102                 }
  103                 
  104                 success = atomic_cmpset_int(&br->br_prod_head, prod_head,
  105                     prod_next);
  106         } while (success == 0);
  107 #ifdef DEBUG_BUFRING
  108         if (br->br_ring[prod_head] != NULL)
  109                 panic("dangling value in enqueue");
  110 #endif  
  111         br->br_ring[prod_head] = buf;
  112         wmb();
  113 
  114         /*
  115          * If there are other enqueues in progress
  116          * that preceeded us, we need to wait for them
  117          * to complete 
  118          */   
  119         while (br->br_prod_tail != prod_head)
  120                 cpu_spinwait();
  121         br->br_prod_bufs++;
  122         br->br_prod_bytes += nbytes;
  123         br->br_prod_tail = prod_next;
  124         critical_exit();
  125         return (0);
  126 }
  127 
  128 static __inline int
  129 buf_ring_enqueue(struct buf_ring *br, void *buf)
  130 {
  131 
  132         return (buf_ring_enqueue_bytes(br, buf, 0));
  133 }
  134 
  135 /*
  136  * multi-consumer safe dequeue 
  137  *
  138  */
  139 static __inline void *
  140 buf_ring_dequeue_mc(struct buf_ring *br)
  141 {
  142         uint32_t cons_head, cons_next;
  143         uint32_t prod_tail;
  144         void *buf;
  145         int success;
  146 
  147         critical_enter();
  148         do {
  149                 cons_head = br->br_cons_head;
  150                 prod_tail = br->br_prod_tail;
  151 
  152                 cons_next = (cons_head + 1) & br->br_cons_mask;
  153                 
  154                 if (cons_head == prod_tail) {
  155                         critical_exit();
  156                         return (NULL);
  157                 }
  158                 
  159                 success = atomic_cmpset_int(&br->br_cons_head, cons_head,
  160                     cons_next);
  161         } while (success == 0);         
  162 
  163         buf = br->br_ring[cons_head];
  164 #ifdef DEBUG_BUFRING
  165         br->br_ring[cons_head] = NULL;
  166 #endif
  167         rmb();
  168         
  169         /*
  170          * If there are other dequeues in progress
  171          * that preceeded us, we need to wait for them
  172          * to complete 
  173          */   
  174         while (br->br_cons_tail != cons_head)
  175                 cpu_spinwait();
  176 
  177         br->br_cons_tail = cons_next;
  178         critical_exit();
  179 
  180         return (buf);
  181 }
  182 
  183 /*
  184  * single-consumer dequeue 
  185  * use where dequeue is protected by a lock
  186  * e.g. a network driver's tx queue lock
  187  */
  188 static __inline void *
  189 buf_ring_dequeue_sc(struct buf_ring *br)
  190 {
  191         uint32_t cons_head, cons_next, cons_next_next;
  192         uint32_t prod_tail;
  193         void *buf;
  194         
  195         cons_head = br->br_cons_head;
  196         prod_tail = br->br_prod_tail;
  197         
  198         cons_next = (cons_head + 1) & br->br_cons_mask;
  199         cons_next_next = (cons_head + 2) & br->br_cons_mask;
  200         
  201         if (cons_head == prod_tail) 
  202                 return (NULL);
  203 
  204 #ifdef PREFETCH_DEFINED 
  205         if (cons_next != prod_tail) {           
  206                 prefetch(br->br_ring[cons_next]);
  207                 if (cons_next_next != prod_tail) 
  208                         prefetch(br->br_ring[cons_next_next]);
  209         }
  210 #endif
  211         br->br_cons_head = cons_next;
  212         buf = br->br_ring[cons_head];
  213 
  214 #ifdef DEBUG_BUFRING
  215         br->br_ring[cons_head] = NULL;
  216         if (!mtx_owned(br->br_lock))
  217                 panic("lock not held on single consumer dequeue");
  218         if (br->br_cons_tail != cons_head)
  219                 panic("inconsistent list cons_tail=%d cons_head=%d",
  220                     br->br_cons_tail, cons_head);
  221 #endif
  222         br->br_cons_tail = cons_next;
  223         return (buf);
  224 }
  225 
  226 /*
  227  * return a pointer to the first entry in the ring
  228  * without modifying it, or NULL if the ring is empty
  229  * race-prone if not protected by a lock
  230  */
  231 static __inline void *
  232 buf_ring_peek(struct buf_ring *br)
  233 {
  234 
  235 #ifdef DEBUG_BUFRING
  236         if ((br->br_lock != NULL) && !mtx_owned(br->br_lock))
  237                 panic("lock not held on single consumer dequeue");
  238 #endif  
  239         /*
  240          * I believe it is safe to not have a memory barrier
  241          * here because we control cons and tail is worst case
  242          * a lagging indicator so we worst case we might
  243          * return NULL immediately after a buffer has been enqueued
  244          */
  245         if (br->br_cons_head == br->br_prod_tail)
  246                 return (NULL);
  247         
  248         return (br->br_ring[br->br_cons_head]);
  249 }
  250 
  251 static __inline int
  252 buf_ring_full(struct buf_ring *br)
  253 {
  254 
  255         return (((br->br_prod_head + 1) & br->br_prod_mask) == br->br_cons_tail);
  256 }
  257 
  258 static __inline int
  259 buf_ring_empty(struct buf_ring *br)
  260 {
  261 
  262         return (br->br_cons_head == br->br_prod_tail);
  263 }
  264 
  265 static __inline int
  266 buf_ring_count(struct buf_ring *br)
  267 {
  268 
  269         return ((br->br_prod_size + br->br_prod_tail - br->br_cons_tail)
  270             & br->br_prod_mask);
  271 }
  272 
  273 struct buf_ring *buf_ring_alloc(int count, struct malloc_type *type, int flags,
  274     struct mtx *);
  275 void buf_ring_free(struct buf_ring *br, struct malloc_type *type);
  276 
  277 
  278 
  279 #endif

Cache object: c20cbf703921b13d074c34565e872717


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.