From 537f47f346c959a536cb69815542bca5ba42c9f1 Mon Sep 17 00:00:00 2001 From: Matthew Dillon Date: Mon, 29 Mar 2004 16:22:23 +0000 Subject: [PATCH] Bring in a bunch of well tested MPIPE changes. Preallocate a minimum number of mpipe elements when it is initialized. Use an array to cache free MPIPE buffers nad remove the data structure overloading that was previously occuring on the buffer itself. Add a deconstructor. Separate the blocking and non-blocking allocation APIs into their own functions. The new code still needs Giant, but it's getting a lot closer to being lock free. --- sys/dev/disk/ata/ata-all.c | 8 +- sys/dev/disk/ata/ata-disk.c | 4 +- sys/dev/disk/ata/ata-dma.c | 12 +- sys/kern/kern_mpipe.c | 216 +++++++++++++++++++++++------------- sys/sys/mpipe.h | 54 +++++++-- 5 files changed, 196 insertions(+), 98 deletions(-) diff --git a/sys/dev/disk/ata/ata-all.c b/sys/dev/disk/ata/ata-all.c index e7350de507..a2257af2af 100644 --- a/sys/dev/disk/ata/ata-all.c +++ b/sys/dev/disk/ata/ata-all.c @@ -26,7 +26,7 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD: src/sys/dev/ata/ata-all.c,v 1.50.2.45 2003/03/12 14:47:12 sos Exp $ - * $DragonFly: src/sys/dev/disk/ata/ata-all.c,v 1.14 2004/03/15 01:10:42 dillon Exp $ + * $DragonFly: src/sys/dev/disk/ata/ata-all.c,v 1.15 2004/03/29 16:22:23 dillon Exp $ */ #include "opt_ata.h" @@ -167,8 +167,10 @@ ata_probe(device_t dev) TAILQ_INIT(&ch->ata_queue); TAILQ_INIT(&ch->atapi_queue); - mpipe_init(&ch->req_mpipe, M_ATA, sizeof(union ata_request), 4, ata_mpipe_size); - mpipe_init(&ch->dma_mpipe, M_DEVBUF, PAGE_SIZE, 4, ata_mpipe_size); + mpipe_init(&ch->req_mpipe, M_ATA, sizeof(union ata_request), + 4, ata_mpipe_size, 0, NULL); + mpipe_init(&ch->dma_mpipe, M_DEVBUF, PAGE_SIZE, + 4, ata_mpipe_size, MPF_NOZERO, NULL); return 0; diff --git a/sys/dev/disk/ata/ata-disk.c b/sys/dev/disk/ata/ata-disk.c index 0bc8873dda..45501de382 100644 --- a/sys/dev/disk/ata/ata-disk.c +++ b/sys/dev/disk/ata/ata-disk.c @@ -26,7 +26,7 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD: src/sys/dev/ata/ata-disk.c,v 1.60.2.24 2003/01/30 07:19:59 sos Exp $ - * $DragonFly: src/sys/dev/disk/ata/ata-disk.c,v 1.14 2004/03/15 01:10:42 dillon Exp $ + * $DragonFly: src/sys/dev/disk/ata/ata-disk.c,v 1.15 2004/03/29 16:22:23 dillon Exp $ */ #include "opt_ata.h" @@ -409,7 +409,7 @@ ad_start(struct ata_device *atadev) * is full, in which case the request will be picked up later when * ad_start() is called after another request completes. */ - request = mpipe_alloc(&atadev->channel->req_mpipe, M_NOWAIT|M_ZERO); + request = mpipe_alloc_nowait(&atadev->channel->req_mpipe); if (request == NULL) { ata_prtdev(atadev, "pipeline full allocating request in ad_start\n"); return; diff --git a/sys/dev/disk/ata/ata-dma.c b/sys/dev/disk/ata/ata-dma.c index 5ee46cb136..33c09e456e 100644 --- a/sys/dev/disk/ata/ata-dma.c +++ b/sys/dev/disk/ata/ata-dma.c @@ -26,7 +26,7 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD: src/sys/dev/ata/ata-dma.c,v 1.35.2.31 2003/05/07 16:46:11 jhb Exp $ - * $DragonFly: src/sys/dev/disk/ata/ata-dma.c,v 1.20 2004/03/09 21:39:59 joerg Exp $ + * $DragonFly: src/sys/dev/disk/ata/ata-dma.c,v 1.21 2004/03/29 16:22:23 dillon Exp $ */ #include @@ -73,11 +73,15 @@ ata_dmaalloc(struct ata_device *atadev, int flags) return(0); KKASSERT(ch->dma_mpipe.max_count != 0); - atadev->dmastate.dmatab = mpipe_alloc(&ch->dma_mpipe, flags); - KKASSERT(((uintptr_t)atadev->dmastate.dmatab & PAGE_MASK) == 0); + if (flags & M_RNOWAIT) + atadev->dmastate.dmatab = mpipe_alloc_nowait(&ch->dma_mpipe); + else + atadev->dmastate.dmatab = mpipe_alloc_waitok(&ch->dma_mpipe); - if (atadev->dmastate.dmatab != NULL) + if (atadev->dmastate.dmatab != NULL) { + KKASSERT(((uintptr_t)atadev->dmastate.dmatab & PAGE_MASK) == 0); return(0); + } return(ENOBUFS); } diff --git a/sys/kern/kern_mpipe.c b/sys/kern/kern_mpipe.c index b32bc68419..240ee4be0d 100644 --- a/sys/kern/kern_mpipe.c +++ b/sys/kern/kern_mpipe.c @@ -23,7 +23,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $DragonFly: src/sys/kern/kern_mpipe.c,v 1.4 2004/03/29 14:16:32 joerg Exp $ + * $DragonFly: src/sys/kern/kern_mpipe.c,v 1.5 2004/03/29 16:22:21 dillon Exp $ */ #include @@ -41,127 +41,189 @@ #define arysize(ary) (sizeof(ary)/sizeof((ary)[0])) -typedef struct mpipe_buf { - TAILQ_ENTRY(mpipe_buf) entry; -} *mpipe_buf_t; +static MALLOC_DEFINE(M_MPIPEARY, "MPipe Array", "Auxillary MPIPE structure"); /* * Initialize a malloc pipeline for the specified malloc type and allocation - * size, and immediately allocate nnow buffers and set the nominal maximum - * to nmax. + * size. Create an array to cache up to nom_count buffers and preallocate + * them. */ void mpipe_init(malloc_pipe_t mpipe, malloc_type_t type, int bytes, - int nnow, int nmax) + int nnom, int nmax, + int mpflags, void (*deconstruct)(struct malloc_pipe *, void *)) { - if (bytes < sizeof(struct mpipe_buf)) - bytes = sizeof(struct mpipe_buf); + int n; + + if (nnom < 1) + nnom = 1; + if (nmax < 0) + nmax = 0x7FFF0000; /* some very large number */ + if (nmax < nnom) + nmax = nnom; bzero(mpipe, sizeof(struct malloc_pipe)); - TAILQ_INIT(&mpipe->queue); mpipe->type = type; mpipe->bytes = bytes; + mpipe->mpflags = mpflags; + mpipe->deconstruct = deconstruct; + if ((mpflags & MPF_NOZERO) == 0) + mpipe->mflags |= M_ZERO; + mpipe->ary_count = nnom; mpipe->max_count = nmax; - if (nnow > 0) { - void *buf; + mpipe->array = malloc(nnom * sizeof(mpipe->array[0]), M_MPIPEARY, + M_WAITOK | M_ZERO); - buf = malloc(bytes, mpipe->type, M_WAITOK); - KKASSERT(buf != NULL); + while (mpipe->free_count < nnom) { + n = mpipe->free_count; + mpipe->array[n] = malloc(bytes, mpipe->type, M_WAITOK | mpipe->mflags); + ++mpipe->free_count; ++mpipe->total_count; - mpipe_free(mpipe, buf); - while (--nnow > 0) { - buf = malloc(bytes, mpipe->type, M_SYSNOWAIT); - if (buf == NULL) - break; - ++mpipe->total_count; - mpipe_free(mpipe, buf); - } } - if (mpipe->max_count < mpipe->total_count) - mpipe->max_count = mpipe->total_count; } void mpipe_done(malloc_pipe_t mpipe) { - struct mpipe_buf *buf; + void *buf; + int n; - KKASSERT(mpipe->free_count == mpipe->total_count); - while (mpipe->free_count) { - buf = TAILQ_FIRST(&mpipe->queue); + KKASSERT(mpipe->free_count == mpipe->total_count); /* no outstanding mem */ + while (--mpipe->free_count >= 0) { + n = mpipe->free_count; + buf = mpipe->array[n]; + mpipe->array[n] = NULL; KKASSERT(buf != NULL); - TAILQ_REMOVE(&mpipe->queue, buf, entry); - --mpipe->free_count; --mpipe->total_count; + if (mpipe->deconstruct) + mpipe->deconstruct(mpipe, buf); free(buf, mpipe->type); } - KKASSERT(TAILQ_EMPTY(&mpipe->queue)); } /* - * Allocate an entry. flags can be M_RNOWAIT which tells us not to block. - * Unlike a normal malloc, if we block in mpipe_alloc() no deadlock will occur - * because it will unblock the moment an existing in-use buffer is freed. + * Allocate an entry, nominally non-blocking. The allocation is guarenteed + * to return non-NULL up to the nominal count after which it may return NULL. + * Note that the implementation is defined to be allowed to block for short + * periods of time. Use mpipe_alloc_waitok() to guarentee the allocation. */ void * -mpipe_alloc(malloc_pipe_t mpipe, int flags) +mpipe_alloc_nowait(malloc_pipe_t mpipe) { - mpipe_buf_t buf; + void *buf; + int n; crit_enter(); - while (mpipe->free_count == 0) { - if (mpipe->total_count < mpipe->max_count) { + if ((n = mpipe->free_count) != 0) { + /* + * Use a free entry if it exists. + */ + --n; + buf = mpipe->array[n]; + mpipe->array[n] = NULL; /* sanity check, not absolutely needed */ + mpipe->free_count = n; + } else if (mpipe->total_count >= mpipe->max_count) { + /* + * Return NULL if we have hit our limit + */ + buf = NULL; + } else { + /* + * Otherwise try to malloc() non-blocking. + */ + buf = malloc(mpipe->bytes, mpipe->type, M_NOWAIT | mpipe->mflags); + if (buf) ++mpipe->total_count; - if ((buf = malloc(mpipe->bytes, mpipe->type, flags)) != NULL) { - crit_exit(); - return(buf); - } - --mpipe->total_count; - } else if (flags & M_RNOWAIT) { - crit_exit(); - return(NULL); - } else { + } + crit_exit(); + return(buf); +} + +/* + * Allocate an entry, block until the allocation succeeds. This may cause + * us to block waiting for a prior allocation to be freed. + */ +void * +mpipe_alloc_waitok(malloc_pipe_t mpipe) +{ + void *buf; + int n; + int mfailed; + + crit_enter(); + mfailed = 0; + for (;;) { + if ((n = mpipe->free_count) != 0) { + /* + * Use a free entry if it exists. + */ + --n; + buf = mpipe->array[n]; + mpipe->array[n] = NULL; + mpipe->free_count = n; + break; + } + if (mpipe->total_count >= mpipe->max_count || mfailed) { + /* + * Block if we have hit our limit + */ mpipe->pending = 1; - tsleep(mpipe, 0, "mpipe", 0); + tsleep(mpipe, 0, "mpipe1", 0); + continue; + } + /* + * Otherwise try to malloc() non-blocking. If that fails loop to + * recheck, and block instead of trying to malloc() again. + */ + buf = malloc(mpipe->bytes, mpipe->type, M_NOWAIT | mpipe->mflags); + if (buf) { + ++mpipe->total_count; + break; } + mfailed = 1; } - buf = TAILQ_FIRST(&mpipe->queue); - KKASSERT(buf != NULL); - TAILQ_REMOVE(&mpipe->queue, buf, entry); - --mpipe->free_count; crit_exit(); - if (flags & M_ZERO) - bzero(buf, mpipe->bytes); return(buf); } /* - * Free an entry, unblock any waiters. + * Free an entry, unblock any waiters. Allow NULL. */ void -mpipe_free(malloc_pipe_t mpipe, void *vbuf) +mpipe_free(malloc_pipe_t mpipe, void *buf) { - struct mpipe_buf *buf; - - if ((buf = vbuf) != NULL) { - crit_enter(); - if (mpipe->total_count > mpipe->max_count) { - --mpipe->total_count; - crit_exit(); - free(buf, mpipe->type); - } else { - TAILQ_INSERT_TAIL(&mpipe->queue, buf, entry); - ++mpipe->free_count; - crit_exit(); - if (mpipe->free_count >= (mpipe->total_count >> 2) + 1) { - if (mpipe->trigger) { - mpipe->trigger(mpipe->trigger_data); - } - if (mpipe->pending) { - mpipe->pending = 0; - wakeup(mpipe); - } - } + int n; + + if (buf == NULL) + return; + + crit_enter(); + if ((n = mpipe->free_count) < mpipe->ary_count) { + /* + * Free slot available in free array (LIFO) + */ + mpipe->array[n] = buf; + ++mpipe->free_count; + if ((mpipe->mpflags & (MPF_CACHEDATA|MPF_NOZERO)) == 0) + bzero(buf, mpipe->bytes); + crit_exit(); + + /* + * Wakeup anyone blocked in mpipe_alloc_*(). + */ + if (mpipe->pending) { + mpipe->pending = 0; + wakeup(mpipe); } + } else { + /* + * All the free slots are full, free the buffer directly. + */ + --mpipe->total_count; + KKASSERT(mpipe->total_count >= mpipe->free_count); + if (mpipe->deconstruct) + mpipe->deconstruct(mpipe, buf); + crit_exit(); + free(buf, mpipe->type); } } diff --git a/sys/sys/mpipe.h b/sys/sys/mpipe.h index 8ef70919ce..0071dd071e 100644 --- a/sys/sys/mpipe.h +++ b/sys/sys/mpipe.h @@ -23,7 +23,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $DragonFly: src/sys/sys/mpipe.h,v 1.1 2003/11/30 20:13:53 dillon Exp $ + * $DragonFly: src/sys/sys/mpipe.h,v 1.2 2004/03/29 16:22:22 dillon Exp $ */ #ifndef _SYS_MPIPE_H_ @@ -34,32 +34,62 @@ #endif /* - * Pipeline memory allocations. This implements a pipeline for allocations - * of a particular size. It is used in order to allow memory allocations - * to block while at the same time guarenteeing that no deadlocks will occur. + * Pipeline memory allocations with persistent store capabilities. This + * implements a pipeline for allocations of a particular size. It is used + * in order to allow memory allocations to block while at the same time + * guarenteeing that no deadlocks will occur. + * + * By default new allocations are zero'd out. + * + * MPF_NOZERO If specified the underlying buffers are not zero'd. + * Note this also means you have no way of knowing which + * buffers are coming from the cache and which are new + * allocations. + * + * MPF_CACHEDATA If specified the deconstructor will be called when + * the underlying buffer is free()'d, but the buffer may + * be reused many times before/if that happens. The + * buffer is NOT zero'd on reuse regardless of the + * MPF_NOZERO flag. + * + * If not specified and MPF_NOZERO is also not specified, + * then buffers reused from the cache will be zero'd as + * well as new allocations. + * + * Note that the deconstructor function may still be NULL + * if this flag is specified, meaning that you don't need + * notification when the cached contents is physically + * free()'d. */ struct mpipe_buf; struct malloc_pipe { - TAILQ_HEAD(, mpipe_buf) queue; malloc_type_t type; /* malloc bucket */ int bytes; /* allocation size */ + int mpflags; /* MPF_ flags */ + int mflags; /* M_ flags (used internally) */ int pending; /* there is a request pending */ - int free_count; /* entries in free list */ - int total_count; /* total free + outstanding */ - int max_count; /* maximum cache size */ - void (*trigger)(void *data); /* trigger function on free */ - void *trigger_data; + int free_count; /* entries in array[] */ + int total_count; /* total outstanding allocations incl free */ + int ary_count; /* guarenteed allocation count */ + int max_count; /* maximum count (M_NOWAIT used beyond nom) */ + void **array; /* array[ary_count] */ + void (*deconstruct)(struct malloc_pipe *, void *buf); }; +#define MPF_CACHEDATA 0x0001 /* cache old buffers (do not zero) */ +#define MPF_NOZERO 0x0002 /* do not zero-out new allocations */ + typedef struct malloc_pipe *malloc_pipe_t; #ifdef _KERNEL void mpipe_init(malloc_pipe_t mpipe, malloc_type_t type, - int bytes, int nnow, int nmax); + int bytes, int nnom, int nmax, + int mpflags, void (*deconstruct)(struct malloc_pipe *, void *)); void mpipe_done(malloc_pipe_t mpipe); -void *mpipe_alloc(malloc_pipe_t mpipe, int flags); +void *mpipe_alloc_waitok(malloc_pipe_t mpipe); +void *mpipe_alloc_nowait(malloc_pipe_t mpipe); void mpipe_free(malloc_pipe_t mpipe, void *vbuf); #endif -- 2.41.0