sys/sys/buf_ring.h

   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$
  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