buf_ring.h

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*-
    2  * Copyright (c) 2007-2009 Kip Macy <kmacy@freebsd.org>
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  * 1. Redistributions of source code must retain the above copyright
    9  *    notice, this list of conditions and the following disclaimer.
   10  * 2. Redistributions in binary form must reproduce the above copyright
   11  *    notice, this list of conditions and the following disclaimer in the
   12  *    documentation and/or other materials provided with the distribution.
   13  *
   14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   24  * SUCH DAMAGE.
   25  *
   26  * $FreeBSD: releng/9.2/sys/sys/buf_ring.h 248287 2013-03-14 21:39:39Z jfv $
   27  *
   28  */
   29 
   30 #ifndef _SYS_BUF_RING_H_
   31 #define _SYS_BUF_RING_H_
   32 
   33 #include <machine/cpu.h>
   34 
   35 #if defined(INVARIANTS) && !defined(DEBUG_BUFRING)
   36 #define DEBUG_BUFRING 1
   37 #endif
   38 
   39 #ifdef DEBUG_BUFRING
   40 #include <sys/lock.h>
   41 #include <sys/mutex.h>
   42 #endif
   43 
   44 struct buf_ring {
   45         volatile uint32_t       br_prod_head;
   46         volatile uint32_t       br_prod_tail;   
   47         int                     br_prod_size;
   48         int                     br_prod_mask;
   49         uint64_t                br_drops;
   50         uint64_t                br_prod_bufs;
   51         /*
   52          * Pad out to next L2 cache line
   53          */
   54         uint64_t                _pad0[11];
   55 
   56         volatile uint32_t       br_cons_head;
   57         volatile uint32_t       br_cons_tail;
   58         int                     br_cons_size;
   59         int                     br_cons_mask;
   60         
   61         /*
   62          * Pad out to next L2 cache line
   63          */
   64         uint64_t                _pad1[14];
   65 #ifdef DEBUG_BUFRING
   66         struct mtx              *br_lock;
   67 #endif  
   68         void                    *br_ring[0];
   69 };
   70 
   71 /*
   72  * multi-producer safe lock-free ring buffer enqueue
   73  *
   74  */
   75 static __inline int
   76 buf_ring_enqueue(struct buf_ring *br, void *buf)
   77 {
   78         uint32_t prod_head, prod_next;
   79         uint32_t cons_tail;
   80         int success;
   81 #ifdef DEBUG_BUFRING
   82         int i;
   83         for (i = br->br_cons_head; i != br->br_prod_head;
   84              i = ((i + 1) & br->br_cons_mask))
   85                 if(br->br_ring[i] == buf)
   86                         panic("buf=%p already enqueue at %d prod=%d cons=%d",
   87                             buf, i, br->br_prod_tail, br->br_cons_tail);
   88 #endif  
   89         critical_enter();
   90         do {
   91                 prod_head = br->br_prod_head;
   92                 cons_tail = br->br_cons_tail;
   93 
   94                 prod_next = (prod_head + 1) & br->br_prod_mask;
   95                 
   96                 if (prod_next == cons_tail) {
   97                         br->br_drops++;
   98                         critical_exit();
   99                         return (ENOBUFS);
  100                 }
  101                 
  102                 success = atomic_cmpset_int(&br->br_prod_head, prod_head,
  103                     prod_next);
  104         } while (success == 0);
  105 #ifdef DEBUG_BUFRING
  106         if (br->br_ring[prod_head] != NULL)
  107                 panic("dangling value in enqueue");
  108 #endif  
  109         br->br_ring[prod_head] = buf;
  110         wmb();
  111 
  112         /*
  113          * If there are other enqueues in progress
  114          * that preceeded us, we need to wait for them
  115          * to complete 
  116          */   
  117         while (br->br_prod_tail != prod_head)
  118                 cpu_spinwait();
  119         br->br_prod_bufs++;
  120         br->br_prod_tail = prod_next;
  121         critical_exit();
  122         return (0);
  123 }
  124 
  125 /*
  126  * multi-consumer safe dequeue 
  127  *
  128  */
  129 static __inline void *
  130 buf_ring_dequeue_mc(struct buf_ring *br)
  131 {
  132         uint32_t cons_head, cons_next;
  133         uint32_t prod_tail;
  134         void *buf;
  135         int success;
  136 
  137         critical_enter();
  138         do {
  139                 cons_head = br->br_cons_head;
  140                 prod_tail = br->br_prod_tail;
  141 
  142                 cons_next = (cons_head + 1) & br->br_cons_mask;
  143                 
  144                 if (cons_head == prod_tail) {
  145                         critical_exit();
  146                         return (NULL);
  147                 }
  148                 
  149                 success = atomic_cmpset_int(&br->br_cons_head, cons_head,
  150                     cons_next);
  151         } while (success == 0);         
  152 
  153         buf = br->br_ring[cons_head];
  154 #ifdef DEBUG_BUFRING
  155         br->br_ring[cons_head] = NULL;
  156 #endif
  157         rmb();
  158         
  159         /*
  160          * If there are other dequeues in progress
  161          * that preceeded us, we need to wait for them
  162          * to complete 
  163          */   
  164         while (br->br_cons_tail != cons_head)
  165                 cpu_spinwait();
  166 
  167         br->br_cons_tail = cons_next;
  168         critical_exit();
  169 
  170         return (buf);
  171 }
  172 
  173 /*
  174  * single-consumer dequeue 
  175  * use where dequeue is protected by a lock
  176  * e.g. a network driver's tx queue lock
  177  */
  178 static __inline void *
  179 buf_ring_dequeue_sc(struct buf_ring *br)
  180 {
  181         uint32_t cons_head, cons_next, cons_next_next;
  182         uint32_t prod_tail;
  183         void *buf;
  184         
  185         cons_head = br->br_cons_head;
  186         prod_tail = br->br_prod_tail;
  187         
  188         cons_next = (cons_head + 1) & br->br_cons_mask;
  189         cons_next_next = (cons_head + 2) & br->br_cons_mask;
  190         
  191         if (cons_head == prod_tail) 
  192                 return (NULL);
  193 
  194 #ifdef PREFETCH_DEFINED 
  195         if (cons_next != prod_tail) {           
  196                 prefetch(br->br_ring[cons_next]);
  197                 if (cons_next_next != prod_tail) 
  198                         prefetch(br->br_ring[cons_next_next]);
  199         }
  200 #endif
  201         br->br_cons_head = cons_next;
  202         buf = br->br_ring[cons_head];
  203 
  204 #ifdef DEBUG_BUFRING
  205         br->br_ring[cons_head] = NULL;
  206         if (!mtx_owned(br->br_lock))
  207                 panic("lock not held on single consumer dequeue");
  208         if (br->br_cons_tail != cons_head)
  209                 panic("inconsistent list cons_tail=%d cons_head=%d",
  210                     br->br_cons_tail, cons_head);
  211 #endif
  212         br->br_cons_tail = cons_next;
  213         return (buf);
  214 }
  215 
  216 /*
  217  * single-consumer advance after a peek
  218  * use where it is protected by a lock
  219  * e.g. a network driver's tx queue lock
  220  */
  221 static __inline void
  222 buf_ring_advance_sc(struct buf_ring *br)
  223 {
  224         uint32_t cons_head, cons_next;
  225         uint32_t prod_tail;
  226         
  227         cons_head = br->br_cons_head;
  228         prod_tail = br->br_prod_tail;
  229         
  230         cons_next = (cons_head + 1) & br->br_cons_mask;
  231         if (cons_head == prod_tail) 
  232                 return;
  233         br->br_cons_head = cons_next;
  234 #ifdef DEBUG_BUFRING
  235         br->br_ring[cons_head] = NULL;
  236 #endif
  237         br->br_cons_tail = cons_next;
  238 }
  239 
  240 /*
  241  * Used to return a buffer (most likely already there)
  242  * to the top od the ring. The caller should *not*
  243  * have used any dequeue to pull it out of the ring
  244  * but instead should have used the peek() function.
  245  * This is normally used where the transmit queue
  246  * of a driver is full, and an mubf must be returned.
  247  * Most likely whats in the ring-buffer is what
  248  * is being put back (since it was not removed), but
  249  * sometimes the lower transmit function may have
  250  * done a pullup or other function that will have
  251  * changed it. As an optimzation we always put it
  252  * back (since jhb says the store is probably cheaper),
  253  * if we have to do a multi-queue version we will need
  254  * the compare and an atomic.
  255  */
  256 static __inline void
  257 buf_ring_putback_sc(struct buf_ring *br, void *new)
  258 {
  259         KASSERT(br->br_cons_head != br->br_prod_tail, 
  260                 ("Buf-Ring has none in putback")) ;
  261         br->br_ring[br->br_cons_head] = new;
  262 }
  263 
  264 /*
  265  * return a pointer to the first entry in the ring
  266  * without modifying it, or NULL if the ring is empty
  267  * race-prone if not protected by a lock
  268  */
  269 static __inline void *
  270 buf_ring_peek(struct buf_ring *br)
  271 {
  272 
  273 #ifdef DEBUG_BUFRING
  274         if ((br->br_lock != NULL) && !mtx_owned(br->br_lock))
  275                 panic("lock not held on single consumer dequeue");
  276 #endif  
  277         /*
  278          * I believe it is safe to not have a memory barrier
  279          * here because we control cons and tail is worst case
  280          * a lagging indicator so we worst case we might
  281          * return NULL immediately after a buffer has been enqueued
  282          */
  283         if (br->br_cons_head == br->br_prod_tail)
  284                 return (NULL);
  285         
  286         return (br->br_ring[br->br_cons_head]);
  287 }
  288 
  289 static __inline int
  290 buf_ring_full(struct buf_ring *br)
  291 {
  292 
  293         return (((br->br_prod_head + 1) & br->br_prod_mask) == br->br_cons_tail);
  294 }
  295 
  296 static __inline int
  297 buf_ring_empty(struct buf_ring *br)
  298 {
  299 
  300         return (br->br_cons_head == br->br_prod_tail);
  301 }
  302 
  303 static __inline int
  304 buf_ring_count(struct buf_ring *br)
  305 {
  306 
  307         return ((br->br_prod_size + br->br_prod_tail - br->br_cons_tail)
  308             & br->br_prod_mask);
  309 }
  310 
  311 struct buf_ring *buf_ring_alloc(int count, struct malloc_type *type, int flags,
  312     struct mtx *);
  313 void buf_ring_free(struct buf_ring *br, struct malloc_type *type);
  314 
  315 
  316 
  317 #endif
Cache object: b41b0f5f0caa7dc48d3b090ad7ea90d1
[ 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.
FreeBSD/Linux Kernel Cross Reference sys/sys/buf_ring.h

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