sys/sys/buf_ring.h

   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$
  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         /*
  53          * Pad out to next L2 cache line
  54          */
  55         uint64_t                _pad0[13];
  56
  57         volatile uint32_t       br_cons_head;
  58         volatile uint32_t       br_cons_tail;
  59         int                     br_cons_size;
  60         int                     br_cons_mask;
  61
  62         /*
  63          * Pad out to next L2 cache line
  64          */
  65         uint64_t                _pad1[14];
  66 #ifdef DEBUG_BUFRING
  67         struct mtx              *br_lock;
  68 #endif
  69         void                    *br_ring[0];
  70 };
  71
  72 /*
  73  * multi-producer safe lock-free ring buffer enqueue
  74  *
  75  */
  76 static __inline int
  77 buf_ring_enqueue(struct buf_ring *br, void *buf)
  78 {
  79         uint32_t prod_head, prod_next;
  80         uint32_t cons_tail;
  81         int success;
  82 #ifdef DEBUG_BUFRING
  83         int i;
  84         for (i = br->br_cons_head; i != br->br_prod_head;
  85              i = ((i + 1) & br->br_cons_mask))
  86                 if(br->br_ring[i] == buf)
  87                         panic("buf=%p already enqueue at %d prod=%d cons=%d",
  88                             buf, i, br->br_prod_tail, br->br_cons_tail);
  89 #endif
  90         critical_enter();
  91         do {
  92                 prod_head = br->br_prod_head;
  93                 cons_tail = br->br_cons_tail;
  94
  95                 prod_next = (prod_head + 1) & br->br_prod_mask;
  96
  97                 if (prod_next == cons_tail) {
  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_tail = prod_next;
 120         mb();
 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         mb();
 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         mb();
 169         critical_exit();
 170
 171         return (buf);
 172 }
 173
 174 /*
 175  * single-consumer dequeue
 176  * use where dequeue is protected by a lock
 177  * e.g. a network driver's tx queue lock
 178  */
 179 static __inline void *
 180 buf_ring_dequeue_sc(struct buf_ring *br)
 181 {
 182         uint32_t cons_head, cons_next;
 183         uint32_t prod_tail;
 184         void *buf;
 185
 186         critical_enter();
 187         cons_head = br->br_cons_head;
 188         prod_tail = br->br_prod_tail;
 189
 190         cons_next = (cons_head + 1) & br->br_cons_mask;
 191
 192         if (cons_head == prod_tail) {
 193                 critical_exit();
 194                 return (NULL);
 195         }
 196
 197         br->br_cons_head = cons_next;
 198         buf = br->br_ring[cons_head];
 199         mb();
 200
 201 #ifdef DEBUG_BUFRING
 202         br->br_ring[cons_head] = NULL;
 203         if (!mtx_owned(br->br_lock))
 204                 panic("lock not held on single consumer dequeue");
 205         if (br->br_cons_tail != cons_head)
 206                 panic("inconsistent list cons_tail=%d cons_head=%d",
 207                     br->br_cons_tail, cons_head);
 208 #endif
 209         br->br_cons_tail = cons_next;
 210         mb();
 211         critical_exit();
 212         return (buf);
 213 }
 214
 215 /*
 216  * return a pointer to the first entry in the ring
 217  * without modifying it, or NULL if the ring is empty
 218  * race-prone if not protected by a lock
 219  */
 220 static __inline void *
 221 buf_ring_peek(struct buf_ring *br)
 222 {
 223
 224 #ifdef DEBUG_BUFRING
 225         if ((br->br_lock != NULL) && !mtx_owned(br->br_lock))
 226                 panic("lock not held on single consumer dequeue");
 227 #endif
 228         mb();
 229         if (br->br_cons_head == br->br_prod_tail)
 230                 return (NULL);
 231
 232         return (br->br_ring[br->br_cons_head]);
 233 }
 234
 235 static __inline int
 236 buf_ring_full(struct buf_ring *br)
 237 {
 238
 239         return (((br->br_prod_head + 1) & br->br_prod_mask) == br->br_cons_tail);
 240 }
 241
 242 static __inline int
 243 buf_ring_empty(struct buf_ring *br)
 244 {
 245
 246         return (br->br_cons_head == br->br_prod_tail);
 247 }
 248
 249 static __inline int
 250 buf_ring_count(struct buf_ring *br)
 251 {
 252
 253         return ((br->br_prod_size + br->br_prod_tail - br->br_cons_tail)
 254             & br->br_prod_mask);
 255 }
 256
 257 struct buf_ring *buf_ring_alloc(int count, struct malloc_type *type, int flags,
 258     struct mtx *);
 259 void buf_ring_free(struct buf_ring *br, struct malloc_type *type);
 260
 261
 262
 263 #endif