Home | History | Annotate | Line # | Download | only in kern
subr_extent.c revision 1.69.2.1
      1  1.69.2.1      yamt /*	$NetBSD: subr_extent.c,v 1.69.2.1 2007/12/10 12:56:09 yamt Exp $	*/
      2       1.1   thorpej 
      3       1.1   thorpej /*-
      4      1.66      yamt  * Copyright (c) 1996, 1998, 2007 The NetBSD Foundation, Inc.
      5       1.1   thorpej  * All rights reserved.
      6       1.1   thorpej  *
      7       1.1   thorpej  * This code is derived from software contributed to The NetBSD Foundation
      8       1.1   thorpej  * by Jason R. Thorpe and Matthias Drochner.
      9       1.1   thorpej  *
     10       1.1   thorpej  * Redistribution and use in source and binary forms, with or without
     11       1.1   thorpej  * modification, are permitted provided that the following conditions
     12       1.1   thorpej  * are met:
     13       1.1   thorpej  * 1. Redistributions of source code must retain the above copyright
     14       1.1   thorpej  *    notice, this list of conditions and the following disclaimer.
     15       1.1   thorpej  * 2. Redistributions in binary form must reproduce the above copyright
     16       1.1   thorpej  *    notice, this list of conditions and the following disclaimer in the
     17       1.1   thorpej  *    documentation and/or other materials provided with the distribution.
     18       1.1   thorpej  * 3. All advertising materials mentioning features or use of this software
     19       1.1   thorpej  *    must display the following acknowledgement:
     20      1.20  christos  *	This product includes software developed by the NetBSD
     21      1.20  christos  *	Foundation, Inc. and its contributors.
     22       1.1   thorpej  * 4. Neither the name of The NetBSD Foundation nor the names of its
     23       1.1   thorpej  *    contributors may be used to endorse or promote products derived
     24       1.1   thorpej  *    from this software without specific prior written permission.
     25       1.1   thorpej  *
     26       1.1   thorpej  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     27       1.1   thorpej  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     28       1.1   thorpej  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     29      1.10       jtc  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     30      1.10       jtc  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     31       1.1   thorpej  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     32       1.1   thorpej  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     33       1.1   thorpej  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     34       1.1   thorpej  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     35       1.1   thorpej  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     36       1.1   thorpej  * POSSIBILITY OF SUCH DAMAGE.
     37       1.1   thorpej  */
     38       1.1   thorpej 
     39       1.1   thorpej /*
     40       1.1   thorpej  * General purpose extent manager.
     41       1.1   thorpej  */
     42      1.44     lukem 
     43      1.44     lukem #include <sys/cdefs.h>
     44  1.69.2.1      yamt __KERNEL_RCSID(0, "$NetBSD: subr_extent.c,v 1.69.2.1 2007/12/10 12:56:09 yamt Exp $");
     45       1.1   thorpej 
     46       1.7       cgd #ifdef _KERNEL
     47      1.49    martin #include "opt_lockdebug.h"
     48      1.49    martin 
     49       1.1   thorpej #include <sys/param.h>
     50       1.1   thorpej #include <sys/extent.h>
     51       1.1   thorpej #include <sys/malloc.h>
     52  1.69.2.1      yamt #include <sys/kmem.h>
     53      1.14        pk #include <sys/pool.h>
     54       1.1   thorpej #include <sys/time.h>
     55       1.1   thorpej #include <sys/systm.h>
     56       1.1   thorpej #include <sys/proc.h>
     57      1.34       mrg 
     58      1.34       mrg #include <uvm/uvm_extern.h>
     59      1.29   thorpej 
     60  1.69.2.1      yamt #define	KMEM_IS_RUNNING		kmem_running_p()
     61      1.18        pk #elif defined(_EXTENT_TESTING)
     62       1.7       cgd /*
     63       1.7       cgd  * user-land definitions, so it can fit into a testing harness.
     64       1.7       cgd  */
     65       1.7       cgd #include <sys/param.h>
     66      1.18        pk #include <sys/pool.h>
     67       1.7       cgd #include <sys/extent.h>
     68      1.67        ad 
     69       1.7       cgd #include <errno.h>
     70       1.7       cgd #include <stdlib.h>
     71       1.7       cgd #include <stdio.h>
     72      1.28      ross #include <string.h>
     73       1.7       cgd 
     74      1.30     jhawk /*
     75      1.30     jhawk  * Use multi-line #defines to avoid screwing up the kernel tags file;
     76      1.30     jhawk  * without this, ctags produces a tags file where panic() shows up
     77      1.30     jhawk  * in subr_extent.c rather than subr_prf.c.
     78      1.30     jhawk  */
     79      1.30     jhawk #define	\
     80      1.30     jhawk malloc(s, t, flags)		malloc(s)
     81      1.30     jhawk #define	\
     82      1.30     jhawk free(p, t)			free(p)
     83      1.30     jhawk #define	\
     84      1.67        ad cv_wait_sig(cv, lock)		(EWOULDBLOCK)
     85      1.38  augustss #define	\
     86      1.41   thorpej pool_get(pool, flags)		malloc((pool)->pr_size,0,0)
     87      1.30     jhawk #define	\
     88      1.30     jhawk pool_put(pool, rp)		free(rp,0)
     89      1.30     jhawk #define	\
     90      1.30     jhawk panic(a)			printf(a)
     91      1.68        ad #define	mutex_init(a, b, c)
     92      1.68        ad #define	mutex_destroy(a)
     93      1.68        ad #define	mutex_enter(l)
     94      1.68        ad #define	mutex_exit(l)
     95      1.68        ad #define	cv_wait(cv, lock)
     96      1.68        ad #define	cv_broadcast(cv)
     97      1.68        ad #define	cv_init(a, b)
     98      1.68        ad #define	cv_destroy(a)
     99      1.29   thorpej #define	KMEM_IS_RUNNING			(1)
    100      1.68        ad #define	IPL_VM				(0)
    101      1.69        ad #define	MUTEX_DEFAULT			(0)
    102       1.7       cgd #endif
    103       1.1   thorpej 
    104      1.41   thorpej static struct pool expool;
    105      1.14        pk 
    106       1.1   thorpej /*
    107       1.6   thorpej  * Macro to align to an arbitrary power-of-two boundary.
    108       1.6   thorpej  */
    109      1.19        pk #define EXTENT_ALIGN(_start, _align, _skew)		\
    110      1.19        pk 	(((((_start) - (_skew)) + ((_align) - 1)) & (-(_align))) + (_skew))
    111       1.6   thorpej 
    112       1.6   thorpej /*
    113      1.15  sommerfe  * Create the extent_region pool.
    114      1.15  sommerfe  */
    115      1.67        ad void
    116      1.67        ad extent_init(void)
    117      1.15  sommerfe {
    118      1.41   thorpej 
    119      1.18        pk #if defined(_KERNEL)
    120      1.41   thorpej 	pool_init(&expool, sizeof(struct extent_region), 0, 0, 0,
    121      1.63        ad 	    "extent", NULL, IPL_VM);
    122      1.18        pk #else
    123      1.41   thorpej 	expool.pr_size = sizeof(struct extent_region);
    124      1.18        pk #endif
    125      1.15  sommerfe }
    126      1.15  sommerfe 
    127      1.15  sommerfe /*
    128      1.67        ad  * Allocate an extent region descriptor.  EXTENT MUST NOT BE LOCKED.
    129      1.67        ad  * We will handle any locking we may need.
    130      1.52   thorpej  */
    131      1.52   thorpej static struct extent_region *
    132      1.52   thorpej extent_alloc_region_descriptor(struct extent *ex, int flags)
    133      1.52   thorpej {
    134      1.52   thorpej 	struct extent_region *rp;
    135      1.67        ad 	int exflags, error;
    136      1.52   thorpej 
    137      1.52   thorpej 	/*
    138      1.52   thorpej 	 * If the kernel memory allocator is not yet running, we can't
    139      1.52   thorpej 	 * use it (obviously).
    140      1.52   thorpej 	 */
    141      1.52   thorpej 	if (KMEM_IS_RUNNING == 0)
    142      1.52   thorpej 		flags &= ~EX_MALLOCOK;
    143      1.52   thorpej 
    144      1.52   thorpej 	/*
    145      1.52   thorpej 	 * XXX Make a static, create-time flags word, so we don't
    146      1.52   thorpej 	 * XXX have to lock to read it!
    147      1.52   thorpej 	 */
    148      1.67        ad 	mutex_enter(&ex->ex_lock);
    149      1.52   thorpej 	exflags = ex->ex_flags;
    150      1.67        ad 	mutex_exit(&ex->ex_lock);
    151      1.52   thorpej 
    152      1.52   thorpej 	if (exflags & EXF_FIXED) {
    153      1.52   thorpej 		struct extent_fixed *fex = (struct extent_fixed *)ex;
    154      1.52   thorpej 
    155      1.67        ad 		mutex_enter(&ex->ex_lock);
    156      1.52   thorpej 		for (;;) {
    157      1.52   thorpej 			if ((rp = LIST_FIRST(&fex->fex_freelist)) != NULL) {
    158      1.52   thorpej 				/*
    159      1.52   thorpej 				 * Don't muck with flags after pulling it off
    160      1.52   thorpej 				 * the freelist; it may have been dynamically
    161      1.52   thorpej 				 * allocated, and kindly given to us.  We
    162      1.52   thorpej 				 * need to remember that information.
    163      1.52   thorpej 				 */
    164      1.52   thorpej 				LIST_REMOVE(rp, er_link);
    165      1.67        ad 				mutex_exit(&ex->ex_lock);
    166      1.52   thorpej 				return (rp);
    167      1.52   thorpej 			}
    168      1.52   thorpej 			if (flags & EX_MALLOCOK) {
    169      1.67        ad 				mutex_exit(&ex->ex_lock);
    170      1.52   thorpej 				goto alloc;
    171      1.52   thorpej 			}
    172      1.52   thorpej 			if ((flags & EX_WAITOK) == 0) {
    173      1.67        ad 				mutex_exit(&ex->ex_lock);
    174      1.52   thorpej 				return (NULL);
    175      1.52   thorpej 			}
    176      1.52   thorpej 			ex->ex_flags |= EXF_FLWANTED;
    177      1.67        ad 			if ((flags & EX_CATCH) != 0)
    178      1.67        ad 				error = cv_wait_sig(&ex->ex_cv, &ex->ex_lock);
    179      1.67        ad 			else {
    180      1.67        ad 				cv_wait(&ex->ex_cv, &ex->ex_lock);
    181      1.67        ad 				error = 0;
    182      1.67        ad 			}
    183      1.67        ad 			if (error != 0) {
    184      1.67        ad 				mutex_exit(&ex->ex_lock);
    185      1.52   thorpej 				return (NULL);
    186      1.67        ad 			}
    187      1.52   thorpej 		}
    188      1.52   thorpej 	}
    189      1.52   thorpej 
    190      1.52   thorpej  alloc:
    191      1.52   thorpej 	rp = pool_get(&expool, (flags & EX_WAITOK) ? PR_WAITOK : 0);
    192      1.52   thorpej 
    193      1.52   thorpej 	if (rp != NULL)
    194      1.52   thorpej 		rp->er_flags = ER_ALLOC;
    195      1.52   thorpej 
    196      1.52   thorpej 	return (rp);
    197      1.52   thorpej }
    198      1.52   thorpej 
    199      1.52   thorpej /*
    200      1.67        ad  * Free an extent region descriptor.  EXTENT _MUST_ BE LOCKED!
    201      1.52   thorpej  */
    202      1.52   thorpej static void
    203      1.52   thorpej extent_free_region_descriptor(struct extent *ex, struct extent_region *rp)
    204      1.52   thorpej {
    205      1.52   thorpej 
    206      1.52   thorpej 	if (ex->ex_flags & EXF_FIXED) {
    207      1.52   thorpej 		struct extent_fixed *fex = (struct extent_fixed *)ex;
    208      1.52   thorpej 
    209      1.52   thorpej 		/*
    210      1.52   thorpej 		 * If someone's waiting for a region descriptor,
    211      1.52   thorpej 		 * be nice and give them this one, rather than
    212      1.52   thorpej 		 * just free'ing it back to the system.
    213      1.52   thorpej 		 */
    214      1.52   thorpej 		if (rp->er_flags & ER_ALLOC) {
    215      1.52   thorpej 			if (ex->ex_flags & EXF_FLWANTED) {
    216      1.52   thorpej 				/* Clear all but ER_ALLOC flag. */
    217      1.52   thorpej 				rp->er_flags = ER_ALLOC;
    218      1.52   thorpej 				LIST_INSERT_HEAD(&fex->fex_freelist, rp,
    219      1.52   thorpej 				    er_link);
    220      1.52   thorpej 				goto wake_em_up;
    221      1.67        ad 			} else
    222      1.52   thorpej 				pool_put(&expool, rp);
    223      1.52   thorpej 		} else {
    224      1.52   thorpej 			/* Clear all flags. */
    225      1.52   thorpej 			rp->er_flags = 0;
    226      1.52   thorpej 			LIST_INSERT_HEAD(&fex->fex_freelist, rp, er_link);
    227      1.52   thorpej 		}
    228      1.52   thorpej 
    229      1.52   thorpej  wake_em_up:
    230      1.67        ad 		ex->ex_flags &= ~EXF_FLWANTED;
    231      1.67        ad 		cv_broadcast(&ex->ex_cv);
    232      1.52   thorpej 		return;
    233      1.52   thorpej 	}
    234      1.52   thorpej 
    235      1.52   thorpej 	/*
    236      1.52   thorpej 	 * We know it's dynamically allocated if we get here.
    237      1.52   thorpej 	 */
    238      1.52   thorpej 	pool_put(&expool, rp);
    239      1.52   thorpej }
    240      1.52   thorpej 
    241      1.52   thorpej /*
    242       1.1   thorpej  * Allocate and initialize an extent map.
    243       1.1   thorpej  */
    244       1.1   thorpej struct extent *
    245      1.52   thorpej extent_create(const char *name, u_long start, u_long end,
    246      1.62  christos     struct malloc_type *mtype, void *storage, size_t storagesize, int flags)
    247       1.1   thorpej {
    248       1.1   thorpej 	struct extent *ex;
    249      1.62  christos 	char *cp = storage;
    250       1.1   thorpej 	size_t sz = storagesize;
    251       1.1   thorpej 	struct extent_region *rp;
    252       1.1   thorpej 	int fixed_extent = (storage != NULL);
    253      1.67        ad 
    254      1.67        ad #ifndef _KERNEL
    255      1.67        ad 	extent_init();
    256      1.67        ad #endif
    257       1.1   thorpej 
    258       1.6   thorpej #ifdef DIAGNOSTIC
    259       1.1   thorpej 	/* Check arguments. */
    260       1.1   thorpej 	if (name == NULL)
    261       1.1   thorpej 		panic("extent_create: name == NULL");
    262       1.1   thorpej 	if (end < start) {
    263       1.5  christos 		printf("extent_create: extent `%s', start 0x%lx, end 0x%lx\n",
    264       1.1   thorpej 		    name, start, end);
    265       1.1   thorpej 		panic("extent_create: end < start");
    266       1.1   thorpej 	}
    267       1.1   thorpej 	if (fixed_extent && (storagesize < sizeof(struct extent_fixed)))
    268      1.22   thorpej 		panic("extent_create: fixed extent, bad storagesize 0x%lx",
    269      1.22   thorpej 		    (u_long)storagesize);
    270       1.6   thorpej 	if (fixed_extent == 0 && (storagesize != 0 || storage != NULL))
    271       1.6   thorpej 		panic("extent_create: storage provided for non-fixed");
    272       1.6   thorpej #endif
    273       1.1   thorpej 
    274       1.1   thorpej 	/* Allocate extent descriptor. */
    275       1.1   thorpej 	if (fixed_extent) {
    276       1.1   thorpej 		struct extent_fixed *fex;
    277       1.1   thorpej 
    278      1.16     perry 		memset(storage, 0, storagesize);
    279       1.1   thorpej 
    280       1.1   thorpej 		/*
    281       1.1   thorpej 		 * Align all descriptors on "long" boundaries.
    282       1.1   thorpej 		 */
    283       1.1   thorpej 		fex = (struct extent_fixed *)cp;
    284       1.1   thorpej 		ex = (struct extent *)fex;
    285       1.6   thorpej 		cp += ALIGN(sizeof(struct extent_fixed));
    286       1.6   thorpej 		sz -= ALIGN(sizeof(struct extent_fixed));
    287       1.1   thorpej 		fex->fex_storage = storage;
    288       1.1   thorpej 		fex->fex_storagesize = storagesize;
    289       1.1   thorpej 
    290       1.1   thorpej 		/*
    291       1.1   thorpej 		 * In a fixed extent, we have to pre-allocate region
    292       1.1   thorpej 		 * descriptors and place them in the extent's freelist.
    293       1.1   thorpej 		 */
    294       1.1   thorpej 		LIST_INIT(&fex->fex_freelist);
    295       1.6   thorpej 		while (sz >= ALIGN(sizeof(struct extent_region))) {
    296       1.1   thorpej 			rp = (struct extent_region *)cp;
    297       1.6   thorpej 			cp += ALIGN(sizeof(struct extent_region));
    298       1.6   thorpej 			sz -= ALIGN(sizeof(struct extent_region));
    299       1.1   thorpej 			LIST_INSERT_HEAD(&fex->fex_freelist, rp, er_link);
    300       1.1   thorpej 		}
    301       1.1   thorpej 	} else {
    302       1.1   thorpej 		ex = (struct extent *)malloc(sizeof(struct extent),
    303       1.1   thorpej 		    mtype, (flags & EX_WAITOK) ? M_WAITOK : M_NOWAIT);
    304       1.1   thorpej 		if (ex == NULL)
    305       1.1   thorpej 			return (NULL);
    306       1.1   thorpej 	}
    307       1.1   thorpej 
    308       1.1   thorpej 	/* Fill in the extent descriptor and return it to the caller. */
    309      1.69        ad 	mutex_init(&ex->ex_lock, MUTEX_DEFAULT, IPL_VM);
    310      1.67        ad 	cv_init(&ex->ex_cv, "extent");
    311       1.1   thorpej 	LIST_INIT(&ex->ex_regions);
    312       1.1   thorpej 	ex->ex_name = name;
    313       1.1   thorpej 	ex->ex_start = start;
    314       1.1   thorpej 	ex->ex_end = end;
    315       1.1   thorpej 	ex->ex_mtype = mtype;
    316       1.1   thorpej 	ex->ex_flags = 0;
    317       1.1   thorpej 	if (fixed_extent)
    318       1.1   thorpej 		ex->ex_flags |= EXF_FIXED;
    319       1.6   thorpej 	if (flags & EX_NOCOALESCE)
    320       1.6   thorpej 		ex->ex_flags |= EXF_NOCOALESCE;
    321       1.1   thorpej 	return (ex);
    322       1.1   thorpej }
    323       1.1   thorpej 
    324       1.1   thorpej /*
    325       1.1   thorpej  * Destroy an extent map.
    326      1.21       chs  * Since we're freeing the data, there can't be any references
    327      1.21       chs  * so we don't need any locking.
    328       1.1   thorpej  */
    329       1.1   thorpej void
    330      1.52   thorpej extent_destroy(struct extent *ex)
    331       1.1   thorpej {
    332       1.1   thorpej 	struct extent_region *rp, *orp;
    333       1.1   thorpej 
    334       1.6   thorpej #ifdef DIAGNOSTIC
    335       1.1   thorpej 	/* Check arguments. */
    336       1.1   thorpej 	if (ex == NULL)
    337       1.1   thorpej 		panic("extent_destroy: NULL extent");
    338       1.6   thorpej #endif
    339      1.12   thorpej 
    340       1.1   thorpej 	/* Free all region descriptors in extent. */
    341      1.47      matt 	for (rp = LIST_FIRST(&ex->ex_regions); rp != NULL; ) {
    342       1.1   thorpej 		orp = rp;
    343      1.47      matt 		rp = LIST_NEXT(rp, er_link);
    344       1.1   thorpej 		LIST_REMOVE(orp, er_link);
    345       1.1   thorpej 		extent_free_region_descriptor(ex, orp);
    346       1.1   thorpej 	}
    347       1.1   thorpej 
    348      1.67        ad 	cv_destroy(&ex->ex_cv);
    349      1.67        ad 	mutex_destroy(&ex->ex_lock);
    350      1.67        ad 
    351       1.1   thorpej 	/* If we're not a fixed extent, free the extent descriptor itself. */
    352       1.1   thorpej 	if ((ex->ex_flags & EXF_FIXED) == 0)
    353       1.6   thorpej 		free(ex, ex->ex_mtype);
    354       1.1   thorpej }
    355       1.1   thorpej 
    356       1.1   thorpej /*
    357       1.1   thorpej  * Insert a region descriptor into the sorted region list after the
    358       1.1   thorpej  * entry "after" or at the head of the list (if "after" is NULL).
    359       1.6   thorpej  * The region descriptor we insert is passed in "rp".  We must
    360       1.6   thorpej  * allocate the region descriptor before calling this function!
    361       1.6   thorpej  * If we don't need the region descriptor, it will be freed here.
    362       1.1   thorpej  */
    363       1.6   thorpej static void
    364      1.52   thorpej extent_insert_and_optimize(struct extent *ex, u_long start, u_long size,
    365      1.61      yamt     int flags, struct extent_region *after, struct extent_region *rp)
    366       1.1   thorpej {
    367       1.7       cgd 	struct extent_region *nextr;
    368       1.1   thorpej 	int appended = 0;
    369       1.1   thorpej 
    370       1.1   thorpej 	if (after == NULL) {
    371       1.1   thorpej 		/*
    372       1.1   thorpej 		 * We're the first in the region list.  If there's
    373       1.1   thorpej 		 * a region after us, attempt to coalesce to save
    374       1.1   thorpej 		 * descriptor overhead.
    375       1.1   thorpej 		 */
    376       1.6   thorpej 		if (((ex->ex_flags & EXF_NOCOALESCE) == 0) &&
    377      1.47      matt 		    (LIST_FIRST(&ex->ex_regions) != NULL) &&
    378      1.47      matt 		    ((start + size) == LIST_FIRST(&ex->ex_regions)->er_start)) {
    379       1.1   thorpej 			/*
    380       1.1   thorpej 			 * We can coalesce.  Prepend us to the first region.
    381       1.1   thorpej 			 */
    382      1.47      matt 			LIST_FIRST(&ex->ex_regions)->er_start = start;
    383       1.6   thorpej 			extent_free_region_descriptor(ex, rp);
    384       1.6   thorpej 			return;
    385       1.1   thorpej 		}
    386       1.1   thorpej 
    387       1.1   thorpej 		/*
    388       1.6   thorpej 		 * Can't coalesce.  Fill in the region descriptor
    389       1.1   thorpej 		 * in, and insert us at the head of the region list.
    390       1.1   thorpej 		 */
    391       1.1   thorpej 		rp->er_start = start;
    392       1.1   thorpej 		rp->er_end = start + (size - 1);
    393       1.1   thorpej 		LIST_INSERT_HEAD(&ex->ex_regions, rp, er_link);
    394       1.6   thorpej 		return;
    395       1.1   thorpej 	}
    396       1.1   thorpej 
    397       1.1   thorpej 	/*
    398       1.6   thorpej 	 * If EXF_NOCOALESCE is set, coalescing is disallowed.
    399       1.1   thorpej 	 */
    400       1.6   thorpej 	if (ex->ex_flags & EXF_NOCOALESCE)
    401       1.6   thorpej 		goto cant_coalesce;
    402       1.1   thorpej 
    403       1.1   thorpej 	/*
    404       1.1   thorpej 	 * Attempt to coalesce with the region before us.
    405       1.1   thorpej 	 */
    406       1.1   thorpej 	if ((after->er_end + 1) == start) {
    407       1.1   thorpej 		/*
    408       1.1   thorpej 		 * We can coalesce.  Append ourselves and make
    409       1.1   thorpej 		 * note of it.
    410       1.1   thorpej 		 */
    411       1.1   thorpej 		after->er_end = start + (size - 1);
    412       1.1   thorpej 		appended = 1;
    413       1.1   thorpej 	}
    414       1.1   thorpej 
    415       1.1   thorpej 	/*
    416       1.1   thorpej 	 * Attempt to coalesce with the region after us.
    417       1.1   thorpej 	 */
    418      1.47      matt 	if ((LIST_NEXT(after, er_link) != NULL) &&
    419      1.47      matt 	    ((start + size) == LIST_NEXT(after, er_link)->er_start)) {
    420       1.1   thorpej 		/*
    421       1.1   thorpej 		 * We can coalesce.  Note that if we appended ourselves
    422       1.1   thorpej 		 * to the previous region, we exactly fit the gap, and
    423       1.1   thorpej 		 * can free the "next" region descriptor.
    424       1.1   thorpej 		 */
    425       1.1   thorpej 		if (appended) {
    426       1.1   thorpej 			/*
    427       1.1   thorpej 			 * Yup, we can free it up.
    428       1.1   thorpej 			 */
    429      1.47      matt 			after->er_end = LIST_NEXT(after, er_link)->er_end;
    430      1.47      matt 			nextr = LIST_NEXT(after, er_link);
    431       1.7       cgd 			LIST_REMOVE(nextr, er_link);
    432       1.7       cgd 			extent_free_region_descriptor(ex, nextr);
    433       1.1   thorpej 		} else {
    434       1.1   thorpej 			/*
    435       1.1   thorpej 			 * Nope, just prepend us to the next region.
    436       1.1   thorpej 			 */
    437      1.47      matt 			LIST_NEXT(after, er_link)->er_start = start;
    438       1.1   thorpej 		}
    439       1.6   thorpej 
    440       1.6   thorpej 		extent_free_region_descriptor(ex, rp);
    441       1.6   thorpej 		return;
    442       1.1   thorpej 	}
    443       1.1   thorpej 
    444       1.1   thorpej 	/*
    445       1.1   thorpej 	 * We weren't able to coalesce with the next region, but
    446       1.1   thorpej 	 * we don't need to allocate a region descriptor if we
    447       1.1   thorpej 	 * appended ourselves to the previous region.
    448       1.1   thorpej 	 */
    449       1.6   thorpej 	if (appended) {
    450       1.6   thorpej 		extent_free_region_descriptor(ex, rp);
    451       1.6   thorpej 		return;
    452       1.6   thorpej 	}
    453       1.1   thorpej 
    454       1.6   thorpej  cant_coalesce:
    455       1.1   thorpej 
    456       1.1   thorpej 	/*
    457       1.6   thorpej 	 * Fill in the region descriptor and insert ourselves
    458       1.1   thorpej 	 * into the region list.
    459       1.1   thorpej 	 */
    460       1.1   thorpej 	rp->er_start = start;
    461       1.1   thorpej 	rp->er_end = start + (size - 1);
    462       1.1   thorpej 	LIST_INSERT_AFTER(after, rp, er_link);
    463       1.1   thorpej }
    464       1.1   thorpej 
    465       1.1   thorpej /*
    466       1.1   thorpej  * Allocate a specific region in an extent map.
    467       1.1   thorpej  */
    468       1.1   thorpej int
    469      1.52   thorpej extent_alloc_region(struct extent *ex, u_long start, u_long size, int flags)
    470       1.1   thorpej {
    471       1.6   thorpej 	struct extent_region *rp, *last, *myrp;
    472       1.1   thorpej 	u_long end = start + (size - 1);
    473       1.1   thorpej 	int error;
    474       1.1   thorpej 
    475       1.6   thorpej #ifdef DIAGNOSTIC
    476       1.1   thorpej 	/* Check arguments. */
    477       1.1   thorpej 	if (ex == NULL)
    478       1.1   thorpej 		panic("extent_alloc_region: NULL extent");
    479       1.1   thorpej 	if (size < 1) {
    480       1.5  christos 		printf("extent_alloc_region: extent `%s', size 0x%lx\n",
    481       1.1   thorpej 		    ex->ex_name, size);
    482       1.1   thorpej 		panic("extent_alloc_region: bad size");
    483       1.1   thorpej 	}
    484       1.1   thorpej 	if (end < start) {
    485       1.5  christos 		printf(
    486       1.1   thorpej 		 "extent_alloc_region: extent `%s', start 0x%lx, size 0x%lx\n",
    487       1.1   thorpej 		 ex->ex_name, start, size);
    488       1.1   thorpej 		panic("extent_alloc_region: overflow");
    489       1.1   thorpej 	}
    490       1.6   thorpej #endif
    491      1.42   thorpej #ifdef LOCKDEBUG
    492      1.42   thorpej 	if (flags & EX_WAITSPACE)
    493      1.59      yamt 		ASSERT_SLEEPABLE(NULL, "extent_alloc_region(EX_WAITSPACE)");
    494      1.42   thorpej #endif
    495       1.6   thorpej 
    496       1.1   thorpej 	/*
    497       1.1   thorpej 	 * Make sure the requested region lies within the
    498       1.1   thorpej 	 * extent.
    499      1.12   thorpej 	 *
    500      1.12   thorpej 	 * We don't lock to check the range, because those values
    501      1.12   thorpej 	 * are never modified, and if another thread deletes the
    502      1.12   thorpej 	 * extent, we're screwed anyway.
    503       1.1   thorpej 	 */
    504       1.1   thorpej 	if ((start < ex->ex_start) || (end > ex->ex_end)) {
    505       1.6   thorpej #ifdef DIAGNOSTIC
    506       1.5  christos 		printf("extent_alloc_region: extent `%s' (0x%lx - 0x%lx)\n",
    507       1.1   thorpej 		    ex->ex_name, ex->ex_start, ex->ex_end);
    508       1.5  christos 		printf("extent_alloc_region: start 0x%lx, end 0x%lx\n",
    509       1.1   thorpej 		    start, end);
    510       1.1   thorpej 		panic("extent_alloc_region: region lies outside extent");
    511       1.6   thorpej #else
    512       1.6   thorpej 		return (EINVAL);
    513       1.6   thorpej #endif
    514       1.6   thorpej 	}
    515       1.6   thorpej 
    516       1.6   thorpej 	/*
    517       1.6   thorpej 	 * Allocate the region descriptor.  It will be freed later
    518      1.12   thorpej 	 * if we can coalesce with another region.  Don't lock before
    519      1.12   thorpej 	 * here!  This could block.
    520       1.6   thorpej 	 */
    521       1.6   thorpej 	myrp = extent_alloc_region_descriptor(ex, flags);
    522       1.6   thorpej 	if (myrp == NULL) {
    523       1.6   thorpej #ifdef DIAGNOSTIC
    524       1.6   thorpej 		printf(
    525       1.6   thorpej 		    "extent_alloc_region: can't allocate region descriptor\n");
    526       1.6   thorpej #endif
    527       1.6   thorpej 		return (ENOMEM);
    528       1.1   thorpej 	}
    529       1.1   thorpej 
    530      1.67        ad 	mutex_enter(&ex->ex_lock);
    531       1.1   thorpej  alloc_start:
    532      1.12   thorpej 
    533       1.1   thorpej 	/*
    534       1.1   thorpej 	 * Attempt to place ourselves in the desired area of the
    535       1.1   thorpej 	 * extent.  We save ourselves some work by keeping the list sorted.
    536       1.1   thorpej 	 * In other words, if the start of the current region is greater
    537       1.1   thorpej 	 * than the end of our region, we don't have to search any further.
    538       1.1   thorpej 	 */
    539       1.1   thorpej 
    540       1.1   thorpej 	/*
    541       1.1   thorpej 	 * Keep a pointer to the last region we looked at so
    542       1.1   thorpej 	 * that we don't have to traverse the list again when
    543       1.1   thorpej 	 * we insert ourselves.  If "last" is NULL when we
    544       1.1   thorpej 	 * finally insert ourselves, we go at the head of the
    545       1.1   thorpej 	 * list.  See extent_insert_and_optimize() for details.
    546       1.1   thorpej 	 */
    547       1.1   thorpej 	last = NULL;
    548       1.1   thorpej 
    549      1.47      matt 	LIST_FOREACH(rp, &ex->ex_regions, er_link) {
    550       1.1   thorpej 		if (rp->er_start > end) {
    551       1.1   thorpej 			/*
    552       1.1   thorpej 			 * We lie before this region and don't
    553       1.1   thorpej 			 * conflict.
    554       1.1   thorpej 			 */
    555       1.9   thorpej 			break;
    556       1.1   thorpej 		}
    557       1.1   thorpej 
    558       1.1   thorpej 		/*
    559       1.1   thorpej 		 * The current region begins before we end.
    560       1.1   thorpej 		 * Check for a conflict.
    561       1.1   thorpej 		 */
    562       1.1   thorpej 		if (rp->er_end >= start) {
    563       1.1   thorpej 			/*
    564       1.6   thorpej 			 * We conflict.  If we can (and want to) wait,
    565       1.6   thorpej 			 * do so.
    566       1.1   thorpej 			 */
    567       1.6   thorpej 			if (flags & EX_WAITSPACE) {
    568      1.67        ad 				if ((flags & EX_CATCH) != 0)
    569      1.67        ad 					error = cv_wait_sig(&ex->ex_cv,
    570      1.67        ad 					    &ex->ex_lock);
    571      1.67        ad 				else {
    572      1.67        ad 					cv_wait(&ex->ex_cv, &ex->ex_lock);
    573      1.67        ad 					error = 0;
    574      1.67        ad 				}
    575      1.56       dsl 				if (error == 0)
    576      1.56       dsl 					goto alloc_start;
    577      1.67        ad 				mutex_exit(&ex->ex_lock);
    578      1.56       dsl 			} else {
    579      1.67        ad 				mutex_exit(&ex->ex_lock);
    580      1.56       dsl 				error = EAGAIN;
    581       1.1   thorpej 			}
    582       1.6   thorpej 			extent_free_region_descriptor(ex, myrp);
    583      1.56       dsl 			return error;
    584       1.1   thorpej 		}
    585       1.1   thorpej 		/*
    586       1.1   thorpej 		 * We don't conflict, but this region lies before
    587       1.1   thorpej 		 * us.  Keep a pointer to this region, and keep
    588       1.1   thorpej 		 * trying.
    589       1.1   thorpej 		 */
    590       1.1   thorpej 		last = rp;
    591       1.1   thorpej 	}
    592       1.1   thorpej 
    593       1.1   thorpej 	/*
    594       1.1   thorpej 	 * We don't conflict with any regions.  "last" points
    595       1.1   thorpej 	 * to the region we fall after, or is NULL if we belong
    596       1.1   thorpej 	 * at the beginning of the region list.  Insert ourselves.
    597       1.1   thorpej 	 */
    598       1.6   thorpej 	extent_insert_and_optimize(ex, start, size, flags, last, myrp);
    599      1.67        ad 	mutex_exit(&ex->ex_lock);
    600       1.6   thorpej 	return (0);
    601       1.1   thorpej }
    602       1.1   thorpej 
    603       1.1   thorpej /*
    604       1.1   thorpej  * Macro to check (x + y) <= z.  This check is designed to fail
    605       1.1   thorpej  * if an overflow occurs.
    606       1.1   thorpej  */
    607       1.1   thorpej #define LE_OV(x, y, z)	((((x) + (y)) >= (x)) && (((x) + (y)) <= (z)))
    608       1.1   thorpej 
    609       1.1   thorpej /*
    610       1.1   thorpej  * Allocate a region in an extent map subregion.
    611       1.1   thorpej  *
    612       1.1   thorpej  * If EX_FAST is specified, we return the first fit in the map.
    613       1.1   thorpej  * Otherwise, we try to minimize fragmentation by finding the
    614       1.1   thorpej  * smallest gap that will hold the request.
    615       1.1   thorpej  *
    616       1.1   thorpej  * The allocated region is aligned to "alignment", which must be
    617       1.1   thorpej  * a power of 2.
    618       1.1   thorpej  */
    619       1.1   thorpej int
    620      1.52   thorpej extent_alloc_subregion1(struct extent *ex, u_long substart, u_long subend,
    621      1.52   thorpej     u_long size, u_long alignment, u_long skew, u_long boundary,
    622      1.52   thorpej     int flags, u_long *result)
    623       1.1   thorpej {
    624       1.6   thorpej 	struct extent_region *rp, *myrp, *last, *bestlast;
    625      1.43     enami 	u_long newstart, newend, exend, beststart, bestovh, ovh;
    626      1.23   mycroft 	u_long dontcross;
    627       1.1   thorpej 	int error;
    628       1.1   thorpej 
    629       1.6   thorpej #ifdef DIAGNOSTIC
    630      1.12   thorpej 	/*
    631      1.12   thorpej 	 * Check arguments.
    632      1.12   thorpej 	 *
    633      1.12   thorpej 	 * We don't lock to check these, because these values
    634      1.12   thorpej 	 * are never modified, and if another thread deletes the
    635      1.12   thorpej 	 * extent, we're screwed anyway.
    636      1.12   thorpej 	 */
    637       1.1   thorpej 	if (ex == NULL)
    638       1.1   thorpej 		panic("extent_alloc_subregion: NULL extent");
    639       1.1   thorpej 	if (result == NULL)
    640       1.1   thorpej 		panic("extent_alloc_subregion: NULL result pointer");
    641       1.8   thorpej 	if ((substart < ex->ex_start) || (substart > ex->ex_end) ||
    642       1.8   thorpej 	    (subend > ex->ex_end) || (subend < ex->ex_start)) {
    643       1.5  christos   printf("extent_alloc_subregion: extent `%s', ex_start 0x%lx, ex_end 0x%lx\n",
    644       1.1   thorpej 		    ex->ex_name, ex->ex_start, ex->ex_end);
    645       1.5  christos 		printf("extent_alloc_subregion: substart 0x%lx, subend 0x%lx\n",
    646       1.1   thorpej 		    substart, subend);
    647       1.1   thorpej 		panic("extent_alloc_subregion: bad subregion");
    648       1.1   thorpej 	}
    649       1.8   thorpej 	if ((size < 1) || ((size - 1) > (subend - substart))) {
    650       1.5  christos 		printf("extent_alloc_subregion: extent `%s', size 0x%lx\n",
    651       1.1   thorpej 		    ex->ex_name, size);
    652       1.1   thorpej 		panic("extent_alloc_subregion: bad size");
    653       1.1   thorpej 	}
    654       1.1   thorpej 	if (alignment == 0)
    655       1.1   thorpej 		panic("extent_alloc_subregion: bad alignment");
    656       1.1   thorpej 	if (boundary && (boundary < size)) {
    657       1.5  christos 		printf(
    658      1.40    marcus 		    "extent_alloc_subregion: extent `%s', size 0x%lx, "
    659      1.40    marcus 		    "boundary 0x%lx\n", ex->ex_name, size, boundary);
    660       1.1   thorpej 		panic("extent_alloc_subregion: bad boundary");
    661       1.1   thorpej 	}
    662      1.42   thorpej #endif
    663      1.42   thorpej #ifdef LOCKDEBUG
    664      1.42   thorpej 	if (flags & EX_WAITSPACE)
    665      1.59      yamt 		ASSERT_SLEEPABLE(NULL, "extent_alloc_subregion1(EX_WAITSPACE)");
    666       1.6   thorpej #endif
    667       1.6   thorpej 
    668       1.6   thorpej 	/*
    669       1.6   thorpej 	 * Allocate the region descriptor.  It will be freed later
    670      1.12   thorpej 	 * if we can coalesce with another region.  Don't lock before
    671      1.12   thorpej 	 * here!  This could block.
    672       1.6   thorpej 	 */
    673       1.6   thorpej 	myrp = extent_alloc_region_descriptor(ex, flags);
    674       1.6   thorpej 	if (myrp == NULL) {
    675       1.6   thorpej #ifdef DIAGNOSTIC
    676       1.6   thorpej 		printf(
    677       1.6   thorpej 		 "extent_alloc_subregion: can't allocate region descriptor\n");
    678       1.6   thorpej #endif
    679       1.6   thorpej 		return (ENOMEM);
    680       1.6   thorpej 	}
    681       1.1   thorpej 
    682       1.1   thorpej  alloc_start:
    683      1.67        ad 	mutex_enter(&ex->ex_lock);
    684      1.12   thorpej 
    685       1.1   thorpej 	/*
    686       1.1   thorpej 	 * Keep a pointer to the last region we looked at so
    687       1.1   thorpej 	 * that we don't have to traverse the list again when
    688       1.1   thorpej 	 * we insert ourselves.  If "last" is NULL when we
    689       1.1   thorpej 	 * finally insert ourselves, we go at the head of the
    690       1.1   thorpej 	 * list.  See extent_insert_and_optimize() for deatails.
    691       1.1   thorpej 	 */
    692       1.1   thorpej 	last = NULL;
    693       1.1   thorpej 
    694       1.1   thorpej 	/*
    695       1.1   thorpej 	 * Keep track of size and location of the smallest
    696       1.1   thorpej 	 * chunk we fit in.
    697       1.1   thorpej 	 *
    698       1.1   thorpej 	 * Since the extent can be as large as the numeric range
    699       1.1   thorpej 	 * of the CPU (0 - 0xffffffff for 32-bit systems), the
    700       1.1   thorpej 	 * best overhead value can be the maximum unsigned integer.
    701       1.1   thorpej 	 * Thus, we initialize "bestovh" to 0, since we insert ourselves
    702       1.1   thorpej 	 * into the region list immediately on an exact match (which
    703       1.1   thorpej 	 * is the only case where "bestovh" would be set to 0).
    704       1.1   thorpej 	 */
    705       1.1   thorpej 	bestovh = 0;
    706       1.1   thorpej 	beststart = 0;
    707       1.1   thorpej 	bestlast = NULL;
    708       1.1   thorpej 
    709       1.1   thorpej 	/*
    710      1.43     enami 	 * Keep track of end of free region.  This is either the end of extent
    711      1.43     enami 	 * or the start of a region past the subend.
    712      1.43     enami 	 */
    713      1.43     enami 	exend = ex->ex_end;
    714      1.43     enami 
    715      1.43     enami 	/*
    716       1.1   thorpej 	 * For N allocated regions, we must make (N + 1)
    717       1.1   thorpej 	 * checks for unallocated space.  The first chunk we
    718       1.1   thorpej 	 * check is the area from the beginning of the subregion
    719       1.9   thorpej 	 * to the first allocated region after that point.
    720       1.1   thorpej 	 */
    721      1.19        pk 	newstart = EXTENT_ALIGN(substart, alignment, skew);
    722       1.1   thorpej 	if (newstart < ex->ex_start) {
    723       1.6   thorpej #ifdef DIAGNOSTIC
    724       1.5  christos 		printf(
    725       1.1   thorpej       "extent_alloc_subregion: extent `%s' (0x%lx - 0x%lx), alignment 0x%lx\n",
    726       1.1   thorpej 		 ex->ex_name, ex->ex_start, ex->ex_end, alignment);
    727      1.67        ad 		mutex_exit(&ex->ex_lock);
    728       1.1   thorpej 		panic("extent_alloc_subregion: overflow after alignment");
    729       1.6   thorpej #else
    730       1.6   thorpej 		extent_free_region_descriptor(ex, myrp);
    731      1.67        ad 		mutex_exit(&ex->ex_lock);
    732       1.6   thorpej 		return (EINVAL);
    733       1.6   thorpej #endif
    734       1.1   thorpej 	}
    735       1.1   thorpej 
    736       1.9   thorpej 	/*
    737       1.9   thorpej 	 * Find the first allocated region that begins on or after
    738       1.9   thorpej 	 * the subregion start, advancing the "last" pointer along
    739       1.9   thorpej 	 * the way.
    740       1.9   thorpej 	 */
    741      1.47      matt 	LIST_FOREACH(rp, &ex->ex_regions, er_link) {
    742       1.9   thorpej 		if (rp->er_start >= newstart)
    743       1.9   thorpej 			break;
    744       1.9   thorpej 		last = rp;
    745       1.9   thorpej 	}
    746      1.17        pk 
    747      1.17        pk 	/*
    748      1.25  drochner 	 * Relocate the start of our candidate region to the end of
    749      1.25  drochner 	 * the last allocated region (if there was one overlapping
    750      1.25  drochner 	 * our subrange).
    751      1.17        pk 	 */
    752      1.25  drochner 	if (last != NULL && last->er_end >= newstart)
    753      1.19        pk 		newstart = EXTENT_ALIGN((last->er_end + 1), alignment, skew);
    754       1.9   thorpej 
    755      1.47      matt 	for (; rp != NULL; rp = LIST_NEXT(rp, er_link)) {
    756       1.1   thorpej 		/*
    757      1.43     enami 		 * If the region pasts the subend, bail out and see
    758      1.43     enami 		 * if we fit against the subend.
    759      1.43     enami 		 */
    760      1.51    bouyer 		if (rp->er_start > subend) {
    761      1.43     enami 			exend = rp->er_start;
    762      1.43     enami 			break;
    763      1.43     enami 		}
    764      1.43     enami 
    765      1.43     enami 		/*
    766       1.1   thorpej 		 * Check the chunk before "rp".  Note that our
    767       1.1   thorpej 		 * comparison is safe from overflow conditions.
    768       1.1   thorpej 		 */
    769       1.1   thorpej 		if (LE_OV(newstart, size, rp->er_start)) {
    770       1.1   thorpej 			/*
    771       1.1   thorpej 			 * Do a boundary check, if necessary.  Note
    772       1.1   thorpej 			 * that a region may *begin* on the boundary,
    773       1.1   thorpej 			 * but it must end before the boundary.
    774       1.1   thorpej 			 */
    775       1.1   thorpej 			if (boundary) {
    776       1.1   thorpej 				newend = newstart + (size - 1);
    777       1.1   thorpej 
    778       1.1   thorpej 				/*
    779      1.23   mycroft 				 * Calculate the next boundary after the start
    780      1.23   mycroft 				 * of this region.
    781      1.23   mycroft 				 */
    782      1.50  junyoung 				dontcross = EXTENT_ALIGN(newstart+1, boundary,
    783      1.23   mycroft 				    (flags & EX_BOUNDZERO) ? 0 : ex->ex_start)
    784      1.23   mycroft 				    - 1;
    785      1.23   mycroft 
    786      1.24   mycroft #if 0
    787      1.33        pk 				printf("newstart=%lx newend=%lx ex_start=%lx ex_end=%lx boundary=%lx dontcross=%lx\n",
    788      1.24   mycroft 				    newstart, newend, ex->ex_start, ex->ex_end,
    789      1.24   mycroft 				    boundary, dontcross);
    790      1.24   mycroft #endif
    791      1.24   mycroft 
    792      1.32       mrg 				/* Check for overflow */
    793      1.32       mrg 				if (dontcross < ex->ex_start)
    794      1.32       mrg 					dontcross = ex->ex_end;
    795      1.32       mrg 				else if (newend > dontcross) {
    796      1.24   mycroft 					/*
    797      1.24   mycroft 					 * Candidate region crosses boundary.
    798      1.24   mycroft 					 * Throw away the leading part and see
    799      1.24   mycroft 					 * if we still fit.
    800      1.24   mycroft 					 */
    801      1.24   mycroft 					newstart = dontcross + 1;
    802      1.24   mycroft 					newend = newstart + (size - 1);
    803      1.24   mycroft 					dontcross += boundary;
    804      1.24   mycroft 					if (!LE_OV(newstart, size, rp->er_start))
    805      1.45    bouyer 						goto skip;
    806      1.24   mycroft 				}
    807      1.24   mycroft 
    808      1.23   mycroft 				/*
    809      1.23   mycroft 				 * If we run past the end of
    810      1.23   mycroft 				 * the extent or the boundary
    811      1.23   mycroft 				 * overflows, then the request
    812      1.23   mycroft 				 * can't fit.
    813       1.1   thorpej 				 */
    814      1.36       mrg 				if (newstart + size - 1 > ex->ex_end ||
    815      1.23   mycroft 				    dontcross < newstart)
    816      1.23   mycroft 					goto fail;
    817       1.1   thorpej 			}
    818       1.1   thorpej 
    819       1.1   thorpej 			/*
    820       1.1   thorpej 			 * We would fit into this space.  Calculate
    821       1.1   thorpej 			 * the overhead (wasted space).  If we exactly
    822       1.1   thorpej 			 * fit, or we're taking the first fit, insert
    823       1.1   thorpej 			 * ourselves into the region list.
    824       1.1   thorpej 			 */
    825       1.1   thorpej 			ovh = rp->er_start - newstart - size;
    826       1.1   thorpej 			if ((flags & EX_FAST) || (ovh == 0))
    827       1.1   thorpej 				goto found;
    828       1.1   thorpej 
    829       1.1   thorpej 			/*
    830       1.1   thorpej 			 * Don't exactly fit, but check to see
    831       1.1   thorpej 			 * if we're better than any current choice.
    832       1.1   thorpej 			 */
    833       1.1   thorpej 			if ((bestovh == 0) || (ovh < bestovh)) {
    834       1.1   thorpej 				bestovh = ovh;
    835       1.1   thorpej 				beststart = newstart;
    836       1.1   thorpej 				bestlast = last;
    837       1.1   thorpej 			}
    838       1.1   thorpej 		}
    839       1.1   thorpej 
    840      1.45    bouyer skip:
    841       1.1   thorpej 		/*
    842       1.1   thorpej 		 * Skip past the current region and check again.
    843       1.1   thorpej 		 */
    844      1.19        pk 		newstart = EXTENT_ALIGN((rp->er_end + 1), alignment, skew);
    845       1.1   thorpej 		if (newstart < rp->er_end) {
    846       1.1   thorpej 			/*
    847       1.1   thorpej 			 * Overflow condition.  Don't error out, since
    848       1.1   thorpej 			 * we might have a chunk of space that we can
    849       1.1   thorpej 			 * use.
    850       1.1   thorpej 			 */
    851       1.1   thorpej 			goto fail;
    852       1.1   thorpej 		}
    853      1.50  junyoung 
    854       1.1   thorpej 		last = rp;
    855       1.1   thorpej 	}
    856       1.1   thorpej 
    857       1.1   thorpej 	/*
    858       1.1   thorpej 	 * The final check is from the current starting point to the
    859       1.1   thorpej 	 * end of the subregion.  If there were no allocated regions,
    860       1.1   thorpej 	 * "newstart" is set to the beginning of the subregion, or
    861       1.1   thorpej 	 * just past the end of the last allocated region, adjusted
    862       1.1   thorpej 	 * for alignment in either case.
    863       1.1   thorpej 	 */
    864       1.1   thorpej 	if (LE_OV(newstart, (size - 1), subend)) {
    865      1.24   mycroft 		/*
    866      1.24   mycroft 		 * Do a boundary check, if necessary.  Note
    867      1.24   mycroft 		 * that a region may *begin* on the boundary,
    868      1.24   mycroft 		 * but it must end before the boundary.
    869      1.24   mycroft 		 */
    870      1.24   mycroft 		if (boundary) {
    871      1.24   mycroft 			newend = newstart + (size - 1);
    872      1.24   mycroft 
    873      1.24   mycroft 			/*
    874      1.24   mycroft 			 * Calculate the next boundary after the start
    875      1.24   mycroft 			 * of this region.
    876      1.24   mycroft 			 */
    877      1.50  junyoung 			dontcross = EXTENT_ALIGN(newstart+1, boundary,
    878      1.24   mycroft 			    (flags & EX_BOUNDZERO) ? 0 : ex->ex_start)
    879      1.24   mycroft 			    - 1;
    880      1.24   mycroft 
    881      1.24   mycroft #if 0
    882      1.33        pk 			printf("newstart=%lx newend=%lx ex_start=%lx ex_end=%lx boundary=%lx dontcross=%lx\n",
    883      1.24   mycroft 			    newstart, newend, ex->ex_start, ex->ex_end,
    884      1.24   mycroft 			    boundary, dontcross);
    885      1.24   mycroft #endif
    886      1.24   mycroft 
    887      1.32       mrg 			/* Check for overflow */
    888      1.32       mrg 			if (dontcross < ex->ex_start)
    889      1.32       mrg 				dontcross = ex->ex_end;
    890      1.32       mrg 			else if (newend > dontcross) {
    891      1.24   mycroft 				/*
    892      1.24   mycroft 				 * Candidate region crosses boundary.
    893      1.24   mycroft 				 * Throw away the leading part and see
    894      1.24   mycroft 				 * if we still fit.
    895      1.24   mycroft 				 */
    896      1.24   mycroft 				newstart = dontcross + 1;
    897      1.24   mycroft 				newend = newstart + (size - 1);
    898      1.24   mycroft 				dontcross += boundary;
    899      1.24   mycroft 				if (!LE_OV(newstart, (size - 1), subend))
    900      1.24   mycroft 					goto fail;
    901      1.24   mycroft 			}
    902      1.24   mycroft 
    903      1.24   mycroft 			/*
    904      1.24   mycroft 			 * If we run past the end of
    905      1.24   mycroft 			 * the extent or the boundary
    906      1.24   mycroft 			 * overflows, then the request
    907      1.24   mycroft 			 * can't fit.
    908      1.24   mycroft 			 */
    909      1.36       mrg 			if (newstart + size - 1 > ex->ex_end ||
    910      1.24   mycroft 			    dontcross < newstart)
    911      1.24   mycroft 				goto fail;
    912      1.24   mycroft 		}
    913      1.24   mycroft 
    914       1.1   thorpej 		/*
    915       1.1   thorpej 		 * We would fit into this space.  Calculate
    916       1.1   thorpej 		 * the overhead (wasted space).  If we exactly
    917       1.1   thorpej 		 * fit, or we're taking the first fit, insert
    918       1.1   thorpej 		 * ourselves into the region list.
    919       1.1   thorpej 		 */
    920      1.43     enami 		ovh = exend - newstart - (size - 1);
    921       1.1   thorpej 		if ((flags & EX_FAST) || (ovh == 0))
    922       1.1   thorpej 			goto found;
    923       1.1   thorpej 
    924       1.1   thorpej 		/*
    925       1.1   thorpej 		 * Don't exactly fit, but check to see
    926       1.1   thorpej 		 * if we're better than any current choice.
    927       1.1   thorpej 		 */
    928       1.1   thorpej 		if ((bestovh == 0) || (ovh < bestovh)) {
    929       1.1   thorpej 			bestovh = ovh;
    930       1.1   thorpej 			beststart = newstart;
    931       1.1   thorpej 			bestlast = last;
    932       1.1   thorpej 		}
    933       1.1   thorpej 	}
    934       1.1   thorpej 
    935       1.1   thorpej  fail:
    936       1.1   thorpej 	/*
    937       1.1   thorpej 	 * One of the following two conditions have
    938       1.1   thorpej 	 * occurred:
    939       1.1   thorpej 	 *
    940       1.1   thorpej 	 *	There is no chunk large enough to hold the request.
    941       1.1   thorpej 	 *
    942       1.1   thorpej 	 *	If EX_FAST was not specified, there is not an
    943       1.1   thorpej 	 *	exact match for the request.
    944       1.1   thorpej 	 *
    945       1.1   thorpej 	 * Note that if we reach this point and EX_FAST is
    946       1.1   thorpej 	 * set, then we know there is no space in the extent for
    947       1.1   thorpej 	 * the request.
    948       1.1   thorpej 	 */
    949       1.1   thorpej 	if (((flags & EX_FAST) == 0) && (bestovh != 0)) {
    950       1.1   thorpej 		/*
    951       1.1   thorpej 		 * We have a match that's "good enough".
    952       1.1   thorpej 		 */
    953       1.1   thorpej 		newstart = beststart;
    954       1.1   thorpej 		last = bestlast;
    955       1.1   thorpej 		goto found;
    956       1.1   thorpej 	}
    957       1.1   thorpej 
    958       1.1   thorpej 	/*
    959       1.1   thorpej 	 * No space currently available.  Wait for it to free up,
    960       1.1   thorpej 	 * if possible.
    961       1.1   thorpej 	 */
    962       1.6   thorpej 	if (flags & EX_WAITSPACE) {
    963      1.67        ad 		if ((flags & EX_CATCH) != 0) {
    964      1.67        ad 			error = cv_wait_sig(&ex->ex_cv, &ex->ex_lock);
    965      1.67        ad 		} else {
    966      1.67        ad 			cv_wait(&ex->ex_cv, &ex->ex_lock);
    967      1.67        ad 			error = 0;
    968      1.67        ad 		}
    969      1.56       dsl 		if (error == 0)
    970      1.56       dsl 			goto alloc_start;
    971      1.67        ad 		mutex_exit(&ex->ex_lock);
    972      1.56       dsl 	} else {
    973      1.67        ad 		mutex_exit(&ex->ex_lock);
    974      1.56       dsl 		error = EAGAIN;
    975       1.1   thorpej 	}
    976       1.1   thorpej 
    977       1.6   thorpej 	extent_free_region_descriptor(ex, myrp);
    978      1.56       dsl 	return error;
    979       1.1   thorpej 
    980       1.1   thorpej  found:
    981       1.1   thorpej 	/*
    982       1.1   thorpej 	 * Insert ourselves into the region list.
    983       1.1   thorpej 	 */
    984       1.6   thorpej 	extent_insert_and_optimize(ex, newstart, size, flags, last, myrp);
    985      1.67        ad 	mutex_exit(&ex->ex_lock);
    986       1.6   thorpej 	*result = newstart;
    987       1.6   thorpej 	return (0);
    988       1.1   thorpej }
    989       1.1   thorpej 
    990       1.1   thorpej int
    991      1.55   thorpej extent_alloc_subregion(struct extent *ex, u_long start, u_long end, u_long size,
    992      1.55   thorpej     u_long alignment, u_long boundary, int flags, u_long *result)
    993      1.55   thorpej {
    994      1.55   thorpej 
    995      1.55   thorpej 	return (extent_alloc_subregion1(ex, start, end, size, alignment,
    996      1.55   thorpej 					0, boundary, flags, result));
    997      1.55   thorpej }
    998      1.55   thorpej 
    999      1.55   thorpej int
   1000      1.55   thorpej extent_alloc(struct extent *ex, u_long size, u_long alignment, u_long boundary,
   1001      1.55   thorpej     int flags, u_long *result)
   1002      1.55   thorpej {
   1003      1.55   thorpej 
   1004      1.55   thorpej 	return (extent_alloc_subregion1(ex, ex->ex_start, ex->ex_end,
   1005      1.55   thorpej 					size, alignment, 0, boundary,
   1006      1.55   thorpej 					flags, result));
   1007      1.55   thorpej }
   1008      1.55   thorpej 
   1009      1.55   thorpej int
   1010      1.55   thorpej extent_alloc1(struct extent *ex, u_long size, u_long alignment, u_long skew,
   1011      1.55   thorpej     u_long boundary, int flags, u_long *result)
   1012      1.55   thorpej {
   1013      1.55   thorpej 
   1014      1.55   thorpej 	return (extent_alloc_subregion1(ex, ex->ex_start, ex->ex_end,
   1015      1.55   thorpej 					size, alignment, skew, boundary,
   1016      1.55   thorpej 					flags, result));
   1017      1.55   thorpej }
   1018      1.55   thorpej 
   1019      1.55   thorpej int
   1020      1.52   thorpej extent_free(struct extent *ex, u_long start, u_long size, int flags)
   1021       1.1   thorpej {
   1022      1.12   thorpej 	struct extent_region *rp, *nrp = NULL;
   1023       1.1   thorpej 	u_long end = start + (size - 1);
   1024      1.57  christos 	int coalesce;
   1025       1.1   thorpej 
   1026       1.6   thorpej #ifdef DIAGNOSTIC
   1027      1.12   thorpej 	/*
   1028      1.12   thorpej 	 * Check arguments.
   1029      1.12   thorpej 	 *
   1030      1.12   thorpej 	 * We don't lock to check these, because these values
   1031      1.12   thorpej 	 * are never modified, and if another thread deletes the
   1032      1.12   thorpej 	 * extent, we're screwed anyway.
   1033      1.12   thorpej 	 */
   1034       1.1   thorpej 	if (ex == NULL)
   1035       1.1   thorpej 		panic("extent_free: NULL extent");
   1036      1.51    bouyer 	if ((start < ex->ex_start) || (end > ex->ex_end)) {
   1037       1.1   thorpej 		extent_print(ex);
   1038       1.5  christos 		printf("extent_free: extent `%s', start 0x%lx, size 0x%lx\n",
   1039       1.1   thorpej 		    ex->ex_name, start, size);
   1040       1.1   thorpej 		panic("extent_free: extent `%s', region not within extent",
   1041       1.1   thorpej 		    ex->ex_name);
   1042       1.1   thorpej 	}
   1043       1.1   thorpej 	/* Check for an overflow. */
   1044       1.1   thorpej 	if (end < start) {
   1045       1.1   thorpej 		extent_print(ex);
   1046       1.5  christos 		printf("extent_free: extent `%s', start 0x%lx, size 0x%lx\n",
   1047       1.1   thorpej 		    ex->ex_name, start, size);
   1048       1.1   thorpej 		panic("extent_free: overflow");
   1049       1.1   thorpej 	}
   1050       1.6   thorpej #endif
   1051       1.1   thorpej 
   1052       1.1   thorpej 	/*
   1053      1.12   thorpej 	 * If we're allowing coalescing, we must allocate a region
   1054      1.12   thorpej 	 * descriptor now, since it might block.
   1055      1.12   thorpej 	 *
   1056      1.12   thorpej 	 * XXX Make a static, create-time flags word, so we don't
   1057      1.12   thorpej 	 * XXX have to lock to read it!
   1058      1.12   thorpej 	 */
   1059      1.67        ad 	mutex_enter(&ex->ex_lock);
   1060      1.57  christos 	coalesce = (ex->ex_flags & EXF_NOCOALESCE) == 0;
   1061      1.67        ad 	mutex_exit(&ex->ex_lock);
   1062      1.14        pk 
   1063      1.58  christos 	if (coalesce) {
   1064      1.12   thorpej 		/* Allocate a region descriptor. */
   1065      1.12   thorpej 		nrp = extent_alloc_region_descriptor(ex, flags);
   1066      1.12   thorpej 		if (nrp == NULL)
   1067      1.12   thorpej 			return (ENOMEM);
   1068      1.12   thorpej 	}
   1069      1.12   thorpej 
   1070      1.67        ad 	mutex_enter(&ex->ex_lock);
   1071      1.12   thorpej 
   1072      1.12   thorpej 	/*
   1073       1.1   thorpej 	 * Find region and deallocate.  Several possibilities:
   1074       1.1   thorpej 	 *
   1075       1.1   thorpej 	 *	1. (start == er_start) && (end == er_end):
   1076       1.1   thorpej 	 *	   Free descriptor.
   1077       1.1   thorpej 	 *
   1078       1.1   thorpej 	 *	2. (start == er_start) && (end < er_end):
   1079       1.1   thorpej 	 *	   Adjust er_start.
   1080       1.1   thorpej 	 *
   1081       1.1   thorpej 	 *	3. (start > er_start) && (end == er_end):
   1082       1.1   thorpej 	 *	   Adjust er_end.
   1083       1.1   thorpej 	 *
   1084       1.1   thorpej 	 *	4. (start > er_start) && (end < er_end):
   1085       1.1   thorpej 	 *	   Fragment region.  Requires descriptor alloc.
   1086       1.1   thorpej 	 *
   1087       1.6   thorpej 	 * Cases 2, 3, and 4 require that the EXF_NOCOALESCE flag
   1088       1.1   thorpej 	 * is not set.
   1089       1.1   thorpej 	 */
   1090      1.47      matt 	LIST_FOREACH(rp, &ex->ex_regions, er_link) {
   1091       1.1   thorpej 		/*
   1092       1.1   thorpej 		 * Save ourselves some comparisons; does the current
   1093       1.1   thorpej 		 * region end before chunk to be freed begins?  If so,
   1094       1.1   thorpej 		 * then we haven't found the appropriate region descriptor.
   1095       1.1   thorpej 		 */
   1096       1.1   thorpej 		if (rp->er_end < start)
   1097       1.1   thorpej 			continue;
   1098       1.1   thorpej 
   1099       1.1   thorpej 		/*
   1100       1.1   thorpej 		 * Save ourselves some traversal; does the current
   1101       1.1   thorpej 		 * region begin after the chunk to be freed ends?  If so,
   1102       1.1   thorpej 		 * then we've already passed any possible region descriptors
   1103       1.1   thorpej 		 * that might have contained the chunk to be freed.
   1104       1.1   thorpej 		 */
   1105       1.1   thorpej 		if (rp->er_start > end)
   1106       1.1   thorpej 			break;
   1107       1.1   thorpej 
   1108       1.1   thorpej 		/* Case 1. */
   1109       1.1   thorpej 		if ((start == rp->er_start) && (end == rp->er_end)) {
   1110       1.1   thorpej 			LIST_REMOVE(rp, er_link);
   1111       1.1   thorpej 			extent_free_region_descriptor(ex, rp);
   1112       1.1   thorpej 			goto done;
   1113       1.1   thorpej 		}
   1114       1.1   thorpej 
   1115       1.1   thorpej 		/*
   1116       1.6   thorpej 		 * The following cases all require that EXF_NOCOALESCE
   1117       1.1   thorpej 		 * is not set.
   1118       1.1   thorpej 		 */
   1119      1.57  christos 		if (!coalesce)
   1120       1.1   thorpej 			continue;
   1121       1.1   thorpej 
   1122       1.1   thorpej 		/* Case 2. */
   1123       1.1   thorpej 		if ((start == rp->er_start) && (end < rp->er_end)) {
   1124       1.1   thorpej 			rp->er_start = (end + 1);
   1125       1.1   thorpej 			goto done;
   1126       1.1   thorpej 		}
   1127       1.1   thorpej 
   1128       1.1   thorpej 		/* Case 3. */
   1129       1.1   thorpej 		if ((start > rp->er_start) && (end == rp->er_end)) {
   1130       1.1   thorpej 			rp->er_end = (start - 1);
   1131       1.1   thorpej 			goto done;
   1132       1.1   thorpej 		}
   1133       1.1   thorpej 
   1134       1.1   thorpej 		/* Case 4. */
   1135       1.1   thorpej 		if ((start > rp->er_start) && (end < rp->er_end)) {
   1136       1.1   thorpej 			/* Fill in new descriptor. */
   1137       1.1   thorpej 			nrp->er_start = end + 1;
   1138       1.1   thorpej 			nrp->er_end = rp->er_end;
   1139       1.1   thorpej 
   1140       1.1   thorpej 			/* Adjust current descriptor. */
   1141       1.1   thorpej 			rp->er_end = start - 1;
   1142       1.1   thorpej 
   1143      1.13        pk 			/* Insert new descriptor after current. */
   1144       1.1   thorpej 			LIST_INSERT_AFTER(rp, nrp, er_link);
   1145      1.13        pk 
   1146      1.13        pk 			/* We used the new descriptor, so don't free it below */
   1147      1.13        pk 			nrp = NULL;
   1148       1.1   thorpej 			goto done;
   1149       1.1   thorpej 		}
   1150       1.1   thorpej 	}
   1151       1.1   thorpej 
   1152       1.1   thorpej 	/* Region not found, or request otherwise invalid. */
   1153      1.67        ad 	mutex_exit(&ex->ex_lock);
   1154       1.1   thorpej 	extent_print(ex);
   1155       1.5  christos 	printf("extent_free: start 0x%lx, end 0x%lx\n", start, end);
   1156       1.1   thorpej 	panic("extent_free: region not found");
   1157       1.1   thorpej 
   1158       1.1   thorpej  done:
   1159      1.13        pk 	if (nrp != NULL)
   1160      1.13        pk 		extent_free_region_descriptor(ex, nrp);
   1161      1.67        ad 	cv_broadcast(&ex->ex_cv);
   1162      1.67        ad 	mutex_exit(&ex->ex_lock);
   1163       1.1   thorpej 	return (0);
   1164       1.1   thorpej }
   1165       1.1   thorpej 
   1166       1.1   thorpej void
   1167      1.52   thorpej extent_print(struct extent *ex)
   1168       1.1   thorpej {
   1169       1.1   thorpej 	struct extent_region *rp;
   1170       1.1   thorpej 
   1171       1.1   thorpej 	if (ex == NULL)
   1172       1.1   thorpej 		panic("extent_print: NULL extent");
   1173       1.1   thorpej 
   1174      1.67        ad 	mutex_enter(&ex->ex_lock);
   1175      1.12   thorpej 
   1176       1.5  christos 	printf("extent `%s' (0x%lx - 0x%lx), flags = 0x%x\n", ex->ex_name,
   1177       1.1   thorpej 	    ex->ex_start, ex->ex_end, ex->ex_flags);
   1178       1.1   thorpej 
   1179      1.47      matt 	LIST_FOREACH(rp, &ex->ex_regions, er_link)
   1180       1.5  christos 		printf("     0x%lx - 0x%lx\n", rp->er_start, rp->er_end);
   1181      1.12   thorpej 
   1182      1.67        ad 	mutex_exit(&ex->ex_lock);
   1183       1.1   thorpej }
   1184