svn commit: r189201 - in user/kmacy/releng_7_fast_net/sys: conf
kern sys
Kip Macy
kmacy at FreeBSD.org
Sat Feb 28 20:43:31 PST 2009
Author: kmacy
Date: Sun Mar 1 04:43:30 2009
New Revision: 189201
URL: http://svn.freebsd.org/changeset/base/189201
Log:
multiq step 2:
- buf_ring: add 'buf_ring', a generic lockless ring-buffer
Added:
user/kmacy/releng_7_fast_net/sys/kern/subr_bufring.c (contents, props changed)
user/kmacy/releng_7_fast_net/sys/sys/buf_ring.h (contents, props changed)
Modified:
user/kmacy/releng_7_fast_net/sys/conf/files
Modified: user/kmacy/releng_7_fast_net/sys/conf/files
==============================================================================
--- user/kmacy/releng_7_fast_net/sys/conf/files Sun Mar 1 04:39:56 2009 (r189200)
+++ user/kmacy/releng_7_fast_net/sys/conf/files Sun Mar 1 04:43:30 2009 (r189201)
@@ -1489,6 +1489,7 @@ kern/subr_acl_posix1e.c standard
kern/subr_autoconf.c standard
kern/subr_blist.c standard
kern/subr_bus.c standard
+kern/subr_bufring.c standard
kern/subr_clock.c standard
kern/subr_devstat.c standard
kern/subr_disk.c standard
Added: user/kmacy/releng_7_fast_net/sys/kern/subr_bufring.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ user/kmacy/releng_7_fast_net/sys/kern/subr_bufring.c Sun Mar 1 04:43:30 2009 (r189201)
@@ -0,0 +1,136 @@
+/**************************************************************************
+ *
+ * Copyright (c) 2007,2008 Kip Macy kmacy at freebsd.org
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ *
+ * 2. The name of Kip Macy nor the names of other
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ *
+ ***************************************************************************/
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <sys/ktr.h>
+#include <sys/buf_ring.h>
+
+
+struct buf_ring *
+buf_ring_alloc(int count, struct malloc_type *type, int flags, struct mtx *lock)
+{
+ struct buf_ring *br;
+
+ KASSERT(powerof2(count), ("buf ring must be size power of 2"));
+
+ br = malloc(sizeof(struct buf_ring) + count*sizeof(caddr_t),
+ type, flags|M_ZERO);
+ if (br == NULL)
+ return (NULL);
+#ifdef DEBUG_BUFRING
+ br->br_lock = lock;
+#endif
+ br->br_prod_size = br->br_cons_size = count;
+ br->br_prod_mask = br->br_cons_mask = count-1;
+ br->br_prod_head = br->br_cons_head = 0;
+ br->br_prod_tail = br->br_cons_tail = 0;
+
+ return (br);
+}
+
+void
+buf_ring_free(struct buf_ring *br, struct malloc_type *type)
+{
+ free(br, type);
+}
+/**************************************************************************
+ *
+ * Copyright (c) 2007,2008 Kip Macy kmacy at freebsd.org
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ *
+ * 2. The name of Kip Macy nor the names of other
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ *
+ ***************************************************************************/
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <sys/ktr.h>
+#include <sys/buf_ring.h>
+
+
+struct buf_ring *
+buf_ring_alloc(int count, struct malloc_type *type, int flags, struct mtx *lock)
+{
+ struct buf_ring *br;
+
+ KASSERT(powerof2(count), ("buf ring must be size power of 2"));
+
+ br = malloc(sizeof(struct buf_ring) + count*sizeof(caddr_t),
+ type, flags|M_ZERO);
+ if (br == NULL)
+ return (NULL);
+#ifdef DEBUG_BUFRING
+ br->br_lock = lock;
+#endif
+ br->br_prod_size = br->br_cons_size = count;
+ br->br_prod_mask = br->br_cons_mask = count-1;
+ br->br_prod_head = br->br_cons_head = 0;
+ br->br_prod_tail = br->br_cons_tail = 0;
+
+ return (br);
+}
+
+void
+buf_ring_free(struct buf_ring *br, struct malloc_type *type)
+{
+ free(br, type);
+}
Added: user/kmacy/releng_7_fast_net/sys/sys/buf_ring.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ user/kmacy/releng_7_fast_net/sys/sys/buf_ring.h Sun Mar 1 04:43:30 2009 (r189201)
@@ -0,0 +1,500 @@
+/**************************************************************************
+ *
+ * Copyright (c) 2007,2008 Kip Macy kmacy at freebsd.org
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ *
+ * 2. The name of Kip Macy nor the names of other
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ *
+ ***************************************************************************/
+
+#ifndef _SYS_BUF_RING_H_
+#define _SYS_BUF_RING_H_
+
+#include <machine/cpu.h>
+
+#if defined(INVARIANTS) && !defined(DEBUG_BUFRING)
+#define DEBUG_BUFRING 1
+#endif
+
+#ifdef DEBUG_BUFRING
+#include <sys/lock.h>
+#include <sys/mutex.h>
+#endif
+
+struct buf_ring {
+ volatile uint32_t br_prod_head;
+ volatile uint32_t br_prod_tail;
+ int br_prod_size;
+ int br_prod_mask;
+ /*
+ * Pad out to next L2 cache line
+ */
+ uint64_t _pad0[14];
+
+ volatile uint32_t br_cons_head;
+ volatile uint32_t br_cons_tail;
+ int br_cons_size;
+ int br_cons_mask;
+
+ /*
+ * Pad out to next L2 cache line
+ */
+ uint64_t _pad1[14];
+#ifdef DEBUG_BUFRING
+ struct mtx *br_lock;
+#endif
+ void *br_ring[0];
+};
+
+
+static __inline int
+buf_ring_enqueue(struct buf_ring *br, void *buf)
+{
+ uint32_t prod_head, prod_next;
+ uint32_t cons_tail;
+ int success;
+#ifdef DEBUG_BUFRING
+ int i;
+ for (i = br->br_cons_head; i != br->br_prod_head;
+ i = ((i + 1) & br->br_cons_mask))
+ if(br->br_ring[i] == buf)
+ panic("buf=%p already enqueue at %d prod=%d cons=%d",
+ buf, i, br->br_prod_tail, br->br_cons_tail);
+#endif
+ critical_enter();
+ do {
+ prod_head = br->br_prod_head;
+ cons_tail = br->br_cons_tail;
+
+ prod_next = (prod_head + 1) & br->br_prod_mask;
+
+ if (prod_next == cons_tail) {
+ critical_exit();
+ return (ENOSPC);
+ }
+
+ success = atomic_cmpset_int(&br->br_prod_head, prod_head,
+ prod_next);
+ } while (success == 0);
+#ifdef DEBUG_BUFRING
+ if (br->br_ring[prod_head] != NULL)
+ panic("dangling value in enqueue");
+#endif
+ br->br_ring[prod_head] = buf;
+ wmb();
+
+ /*
+ * If there are other enqueues in progress
+ * that preceeded us, we need to wait for them
+ * to complete
+ */
+ while (br->br_prod_tail != prod_head)
+ cpu_spinwait();
+ br->br_prod_tail = prod_next;
+ mb();
+ critical_exit();
+ return (0);
+}
+
+/*
+ * multi-consumer safe dequeue
+ *
+ */
+static __inline void *
+buf_ring_dequeue_mc(struct buf_ring *br)
+{
+ uint32_t cons_head, cons_next;
+ uint32_t prod_tail;
+ void *buf;
+ int success;
+
+ critical_enter();
+ do {
+ cons_head = br->br_cons_head;
+ prod_tail = br->br_prod_tail;
+
+ cons_next = (cons_head + 1) & br->br_cons_mask;
+
+ if (cons_head == prod_tail) {
+ critical_exit();
+ return (NULL);
+ }
+
+ success = atomic_cmpset_int(&br->br_cons_head, cons_head,
+ cons_next);
+ } while (success == 0);
+
+ buf = br->br_ring[cons_head];
+#ifdef DEBUG_BUFRING
+ br->br_ring[cons_head] = NULL;
+#endif
+ mb();
+
+ /*
+ * If there are other dequeues in progress
+ * that preceeded us, we need to wait for them
+ * to complete
+ */
+ while (br->br_cons_tail != cons_head)
+ cpu_spinwait();
+
+ br->br_cons_tail = cons_next;
+ mb();
+ critical_exit();
+
+ return (buf);
+}
+
+/*
+ * Single-Consumer dequeue for uses where dequeue
+ * is protected by a lock
+ */
+static __inline void *
+buf_ring_dequeue_sc(struct buf_ring *br)
+{
+ uint32_t cons_head, cons_next;
+ uint32_t prod_tail;
+ void *buf;
+
+ critical_enter();
+ cons_head = br->br_cons_head;
+ prod_tail = br->br_prod_tail;
+
+ cons_next = (cons_head + 1) & br->br_cons_mask;
+
+ if (cons_head == prod_tail) {
+ critical_exit();
+ return (NULL);
+ }
+
+ br->br_cons_head = cons_next;
+ buf = br->br_ring[cons_head];
+ mb();
+
+#ifdef DEBUG_BUFRING
+ br->br_ring[cons_head] = NULL;
+ if (!mtx_owned(br->br_lock))
+ panic("lock not held on single consumer dequeue");
+ if (br->br_cons_tail != cons_head)
+ panic("inconsistent list cons_tail=%d cons_head=%d",
+ br->br_cons_tail, cons_head);
+#endif
+ br->br_cons_tail = cons_next;
+ mb();
+ critical_exit();
+ return (buf);
+}
+
+static __inline void *
+buf_ring_peek(struct buf_ring *br)
+{
+
+#ifdef DEBUG_BUFRING
+ if ((br->br_lock != NULL) && !mtx_owned(br->br_lock))
+ panic("lock not held on single consumer dequeue");
+#endif
+ mb();
+ return (br->br_ring[br->br_cons_tail]);
+}
+
+static __inline int
+buf_ring_full(struct buf_ring *br)
+{
+
+ return (((br->br_prod_head + 1) & br->br_prod_mask) == br->br_cons_tail);
+}
+
+static __inline int
+buf_ring_empty(struct buf_ring *br)
+{
+
+ return (br->br_cons_head == br->br_prod_tail);
+}
+
+static __inline int
+buf_ring_count(struct buf_ring *br)
+{
+
+ return ((br->br_prod_size + br->br_prod_tail - br->br_cons_tail)
+ & br->br_prod_mask);
+}
+
+struct buf_ring *buf_ring_alloc(int count, struct malloc_type *type, int flags,
+ struct mtx *);
+void buf_ring_free(struct buf_ring *br, struct malloc_type *type);
+
+
+
+#endif
+/**************************************************************************
+ *
+ * Copyright (c) 2007,2008 Kip Macy kmacy at freebsd.org
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ *
+ * 2. The name of Kip Macy nor the names of other
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ *
+ ***************************************************************************/
+
+#ifndef _SYS_BUF_RING_H_
+#define _SYS_BUF_RING_H_
+
+#include <machine/cpu.h>
+
+#if defined(INVARIANTS) && !defined(DEBUG_BUFRING)
+#define DEBUG_BUFRING 1
+#endif
+
+#ifdef DEBUG_BUFRING
+#include <sys/lock.h>
+#include <sys/mutex.h>
+#endif
+
+struct buf_ring {
+ volatile uint32_t br_prod_head;
+ volatile uint32_t br_prod_tail;
+ int br_prod_size;
+ int br_prod_mask;
+ /*
+ * Pad out to next L2 cache line
+ */
+ uint64_t _pad0[14];
+
+ volatile uint32_t br_cons_head;
+ volatile uint32_t br_cons_tail;
+ int br_cons_size;
+ int br_cons_mask;
+
+ /*
+ * Pad out to next L2 cache line
+ */
+ uint64_t _pad1[14];
+#ifdef DEBUG_BUFRING
+ struct mtx *br_lock;
+#endif
+ void *br_ring[0];
+};
+
+
+static __inline int
+buf_ring_enqueue(struct buf_ring *br, void *buf)
+{
+ uint32_t prod_head, prod_next;
+ uint32_t cons_tail;
+ int success;
+#ifdef DEBUG_BUFRING
+ int i;
+ for (i = br->br_cons_head; i != br->br_prod_head;
+ i = ((i + 1) & br->br_cons_mask))
+ if(br->br_ring[i] == buf)
+ panic("buf=%p already enqueue at %d prod=%d cons=%d",
+ buf, i, br->br_prod_tail, br->br_cons_tail);
+#endif
+ critical_enter();
+ do {
+ prod_head = br->br_prod_head;
+ cons_tail = br->br_cons_tail;
+
+ prod_next = (prod_head + 1) & br->br_prod_mask;
+
+ if (prod_next == cons_tail) {
+ critical_exit();
+ return (ENOSPC);
+ }
+
+ success = atomic_cmpset_int(&br->br_prod_head, prod_head,
+ prod_next);
+ } while (success == 0);
+#ifdef DEBUG_BUFRING
+ if (br->br_ring[prod_head] != NULL)
+ panic("dangling value in enqueue");
+#endif
+ br->br_ring[prod_head] = buf;
+ wmb();
+
+ /*
+ * If there are other enqueues in progress
+ * that preceeded us, we need to wait for them
+ * to complete
+ */
+ while (br->br_prod_tail != prod_head)
+ cpu_spinwait();
+ br->br_prod_tail = prod_next;
+ mb();
+ critical_exit();
+ return (0);
+}
+
+/*
+ * multi-consumer safe dequeue
+ *
+ */
+static __inline void *
+buf_ring_dequeue_mc(struct buf_ring *br)
+{
+ uint32_t cons_head, cons_next;
+ uint32_t prod_tail;
+ void *buf;
+ int success;
+
+ critical_enter();
+ do {
+ cons_head = br->br_cons_head;
+ prod_tail = br->br_prod_tail;
+
+ cons_next = (cons_head + 1) & br->br_cons_mask;
+
+ if (cons_head == prod_tail) {
+ critical_exit();
+ return (NULL);
+ }
+
+ success = atomic_cmpset_int(&br->br_cons_head, cons_head,
+ cons_next);
+ } while (success == 0);
+
+ buf = br->br_ring[cons_head];
+#ifdef DEBUG_BUFRING
+ br->br_ring[cons_head] = NULL;
+#endif
+ mb();
+
+ /*
+ * If there are other dequeues in progress
+ * that preceeded us, we need to wait for them
+ * to complete
+ */
+ while (br->br_cons_tail != cons_head)
+ cpu_spinwait();
+
+ br->br_cons_tail = cons_next;
+ mb();
+ critical_exit();
+
+ return (buf);
+}
+
+/*
+ * Single-Consumer dequeue for uses where dequeue
+ * is protected by a lock
+ */
+static __inline void *
+buf_ring_dequeue_sc(struct buf_ring *br)
+{
+ uint32_t cons_head, cons_next;
+ uint32_t prod_tail;
+ void *buf;
+
+ critical_enter();
+ cons_head = br->br_cons_head;
+ prod_tail = br->br_prod_tail;
+
+ cons_next = (cons_head + 1) & br->br_cons_mask;
+
+ if (cons_head == prod_tail) {
+ critical_exit();
+ return (NULL);
+ }
+
+ br->br_cons_head = cons_next;
+ buf = br->br_ring[cons_head];
+ mb();
+
+#ifdef DEBUG_BUFRING
+ br->br_ring[cons_head] = NULL;
+ if (!mtx_owned(br->br_lock))
+ panic("lock not held on single consumer dequeue");
+ if (br->br_cons_tail != cons_head)
+ panic("inconsistent list cons_tail=%d cons_head=%d",
+ br->br_cons_tail, cons_head);
+#endif
+ br->br_cons_tail = cons_next;
+ mb();
+ critical_exit();
+ return (buf);
+}
+
+static __inline void *
+buf_ring_peek(struct buf_ring *br)
+{
+
+#ifdef DEBUG_BUFRING
+ if ((br->br_lock != NULL) && !mtx_owned(br->br_lock))
+ panic("lock not held on single consumer dequeue");
+#endif
+ mb();
+ return (br->br_ring[br->br_cons_tail]);
+}
+
+static __inline int
+buf_ring_full(struct buf_ring *br)
+{
+
+ return (((br->br_prod_head + 1) & br->br_prod_mask) == br->br_cons_tail);
+}
+
+static __inline int
+buf_ring_empty(struct buf_ring *br)
+{
+
+ return (br->br_cons_head == br->br_prod_tail);
+}
+
+static __inline int
+buf_ring_count(struct buf_ring *br)
+{
+
+ return ((br->br_prod_size + br->br_prod_tail - br->br_cons_tail)
+ & br->br_prod_mask);
+}
+
+struct buf_ring *buf_ring_alloc(int count, struct malloc_type *type, int flags,
+ struct mtx *);
+void buf_ring_free(struct buf_ring *br, struct malloc_type *type);
+
+
+
+#endif
More information about the svn-src-user
mailing list