/* $OpenBSD: subr_extent.c,v 1.57 2015/08/28 00:03:53 deraadt Exp $ */ /* $NetBSD: subr_extent.c,v 1.7 1996/11/21 18:46:34 cgd Exp $ */ /*- * Copyright (c) 1996, 1998 The NetBSD Foundation, Inc. * All rights reserved. * * This code is derived from software contributed to The NetBSD Foundation * by Jason R. Thorpe and Matthias Drochner. * * 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. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. 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 FOUNDATION 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. */ /* * General purpose extent manager. */ #ifdef _KERNEL #include <sys/param.h> #include <sys/extent.h> #include <sys/malloc.h> #include <sys/systm.h> #include <sys/queue.h> #include <sys/pool.h> #include <ddb/db_output.h> #else /* * user-land definitions, so it can fit into a testing harness. */ #include <sys/param.h> #include <sys/extent.h> #include <sys/queue.h> #include <errno.h> #include <err.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #define malloc(s, t, flags) malloc(s) #define free(p, t, s) free(p) #define tsleep(chan, pri, str, timo) (EWOULDBLOCK) #define wakeup(chan) ((void)0) struct pool { size_t pr_size; }; #define pool_init(a, b, c, d, e, f, g) do { (a)->pr_size = (b); } while (0) #define pool_setipl(pp, ipl) /* nothing */ #define pool_get(pp, flags) malloc((pp)->pr_size, 0, 0) #define pool_put(pp, rp) free((rp), 0, 0) #define panic(...) do { warnx(__VA_ARGS__); abort(); } while (0) #endif #if defined(DIAGNOSTIC) || defined(DDB) void extent_print1(struct extent *, int (*)(const char *, ...) __attribute__((__format__(__kprintf__,1,2)))); #endif static void extent_insert_and_optimize(struct extent *, u_long, u_long, struct extent_region *, struct extent_region *); static struct extent_region *extent_alloc_region_descriptor(struct extent *, int); static void extent_free_region_descriptor(struct extent *, struct extent_region *); int extent_do_alloc(struct extent *, u_long, u_long, u_long, u_long, u_long, u_long, int, struct extent_region *, u_long *); /* * Shortcut to align to an arbitrary power-of-two boundary. */ static __inline__ u_long extent_align(u_long start, u_long align, u_long skew) { return ((((start - skew) + (align - 1)) & (-align)) + skew); } #if defined(DIAGNOSTIC) || defined(DDB) /* * Register the extent on a doubly linked list. * Should work, no? */ static LIST_HEAD(listhead, extent) ext_list; static void extent_register(struct extent *); static void extent_register(struct extent *ex) { #ifdef DIAGNOSTIC struct extent *ep; #endif static int initialized; if (!initialized){ LIST_INIT(&ext_list); initialized = 1; } #ifdef DIAGNOSTIC LIST_FOREACH(ep, &ext_list, ex_link) { if (ep == ex) panic("%s: already registered", __func__); } #endif /* Insert into list */ LIST_INSERT_HEAD(&ext_list, ex, ex_link); } #endif /* DIAGNOSTIC || DDB */ struct pool ex_region_pl; static void extent_pool_init(void) { static int inited; if (!inited) { pool_init(&ex_region_pl, sizeof(struct extent_region), 0, 0, 0, "extentpl", NULL); pool_setipl(&ex_region_pl, IPL_VM); inited = 1; } } #ifdef DDB /* * Print out all extents registered. This is used in * DDB show extents */ void extent_print_all(void) { struct extent *ep; LIST_FOREACH(ep, &ext_list, ex_link) { extent_print1(ep, db_printf); } } #endif /* * Allocate and initialize an extent map. */ struct extent * extent_create(char *name, u_long start, u_long end, int mtype, caddr_t storage, size_t storagesize, int flags) { struct extent *ex; caddr_t cp = storage; size_t sz = storagesize; struct extent_region *rp; int fixed_extent = (storage != NULL); #ifdef DIAGNOSTIC /* Check arguments. */ if (name == NULL) panic("%s: name == NULL", __func__); if (end < start) { printf("%s: extent `%s', start 0x%lx, end 0x%lx\n", __func__, name, start, end); panic("%s: end < start", __func__); } if (fixed_extent && (storagesize < sizeof(struct extent_fixed))) panic("%s: fixed extent, bad storagesize 0x%lx", __func__, (u_long)storagesize); if (fixed_extent == 0 && (storagesize != 0 || storage != NULL)) panic("%s: storage provided for non-fixed", __func__); #endif extent_pool_init(); /* Allocate extent descriptor. */ if (fixed_extent) { struct extent_fixed *fex; memset(storage, 0, storagesize); /* * Align all descriptors on "long" boundaries. */ fex = (struct extent_fixed *)cp; ex = (struct extent *)fex; cp += ALIGN(sizeof(struct extent_fixed)); sz -= ALIGN(sizeof(struct extent_fixed)); fex->fex_storage = storage; fex->fex_storagesize = storagesize; /* * In a fixed extent, we have to pre-allocate region * descriptors and place them in the extent's freelist. */ LIST_INIT(&fex->fex_freelist); while (sz >= ALIGN(sizeof(struct extent_region))) { rp = (struct extent_region *)cp; cp += ALIGN(sizeof(struct extent_region)); sz -= ALIGN(sizeof(struct extent_region)); LIST_INSERT_HEAD(&fex->fex_freelist, rp, er_link); } } else { ex = (struct extent *)malloc(sizeof(struct extent), mtype, (flags & EX_WAITOK) ? M_WAITOK : M_NOWAIT); if (ex == NULL) return (NULL); } /* Fill in the extent descriptor and return it to the caller. */ LIST_INIT(&ex->ex_regions); ex->ex_name = name; ex->ex_start = start; ex->ex_end = end; ex->ex_mtype = mtype; ex->ex_flags = 0; if (fixed_extent) ex->ex_flags |= EXF_FIXED; if (flags & EX_NOCOALESCE) ex->ex_flags |= EXF_NOCOALESCE; if (flags & EX_FILLED) { rp = extent_alloc_region_descriptor(ex, flags); if (rp == NULL) { if (!fixed_extent) free(ex, mtype, sizeof(struct extent)); return (NULL); } rp->er_start = start; rp->er_end = end; LIST_INSERT_HEAD(&ex->ex_regions, rp, er_link); } #if defined(DIAGNOSTIC) || defined(DDB) extent_register(ex); #endif return (ex); } /* * Destroy an extent map. */ void extent_destroy(struct extent *ex) { struct extent_region *rp, *orp; #ifdef DIAGNOSTIC /* Check arguments. */ if (ex == NULL) panic("%s: NULL extent", __func__); #endif /* Free all region descriptors in extent. */ for (rp = LIST_FIRST(&ex->ex_regions); rp != NULL; ) { orp = rp; rp = LIST_NEXT(rp, er_link); LIST_REMOVE(orp, er_link); extent_free_region_descriptor(ex, orp); } #if defined(DIAGNOSTIC) || defined(DDB) /* Remove from the list of all extents. */ LIST_REMOVE(ex, ex_link); #endif /* If we're not a fixed extent, free the extent descriptor itself. */ if ((ex->ex_flags & EXF_FIXED) == 0) free(ex, ex->ex_mtype, sizeof(*ex)); } /* * Insert a region descriptor into the sorted region list after the * entry "after" or at the head of the list (if "after" is NULL). * The region descriptor we insert is passed in "rp". We must * allocate the region descriptor before calling this function! * If we don't need the region descriptor, it will be freed here. */ static void extent_insert_and_optimize(struct extent *ex, u_long start, u_long size, struct extent_region *after, struct extent_region *rp) { struct extent_region *nextr; int appended = 0; if (after == NULL) { /* * We're the first in the region list. If there's * a region after us, attempt to coalesce to save * descriptor overhead. */ if (((ex->ex_flags & EXF_NOCOALESCE) == 0) && !LIST_EMPTY(&ex->ex_regions) && ((start + size) == LIST_FIRST(&ex->ex_regions)->er_start)) { /* * We can coalesce. Prepend us to the first region. */ LIST_FIRST(&ex->ex_regions)->er_start = start; extent_free_region_descriptor(ex, rp); return; } /* * Can't coalesce. Fill in the region descriptor * in, and insert us at the head of the region list. */ rp->er_start = start; rp->er_end = start + (size - 1); LIST_INSERT_HEAD(&ex->ex_regions, rp, er_link); return; } /* * If EXF_NOCOALESCE is set, coalescing is disallowed. */ if (ex->ex_flags & EXF_NOCOALESCE) goto cant_coalesce; /* * Attempt to coalesce with the region before us. */ if ((after->er_end + 1) == start) { /* * We can coalesce. Append ourselves and make * note of it. */ after->er_end = start + (size - 1); appended = 1; } /* * Attempt to coalesce with the region after us. */ if (LIST_NEXT(after, er_link) != NULL && ((start + size) == LIST_NEXT(after, er_link)->er_start)) { /* * We can coalesce. Note that if we appended ourselves * to the previous region, we exactly fit the gap, and * can free the "next" region descriptor. */ if (appended) { /* * Yup, we can free it up. */ after->er_end = LIST_NEXT(after, er_link)->er_end; nextr = LIST_NEXT(after, er_link); LIST_REMOVE(nextr, er_link); extent_free_region_descriptor(ex, nextr); } else { /* * Nope, just prepend us to the next region. */ LIST_NEXT(after, er_link)->er_start = start; } extent_free_region_descriptor(ex, rp); return; } /* * We weren't able to coalesce with the next region, but * we don't need to allocate a region descriptor if we * appended ourselves to the previous region. */ if (appended) { extent_free_region_descriptor(ex, rp); return; } cant_coalesce: /* * Fill in the region descriptor and insert ourselves * into the region list. */ rp->er_start = start; rp->er_end = start + (size - 1); LIST_INSERT_AFTER(after, rp, er_link); } /* * Allocate a specific region in an extent map. */ int extent_alloc_region(struct extent *ex, u_long start, u_long size, int flags) { struct extent_region *rp, *last, *myrp; u_long end = start + (size - 1); int error; #ifdef DIAGNOSTIC /* Check arguments. */ if (ex == NULL) panic("%s: NULL extent", __func__); if (size < 1) { printf("%s: extent `%s', size 0x%lx\n", __func__, ex->ex_name, size); panic("%s: bad size", __func__); } if (end < start) { printf("%s: extent `%s', start 0x%lx, size 0x%lx\n", __func__, ex->ex_name, start, size); panic("%s: overflow", __func__); } if ((flags & EX_CONFLICTOK) && (flags & EX_WAITSPACE)) panic("%s: EX_CONFLICTOK and EX_WAITSPACE " "are mutually exclusive", __func__); #endif /* * Make sure the requested region lies within the * extent. */ if ((start < ex->ex_start) || (end > ex->ex_end)) { #ifdef DIAGNOSTIC printf("%s: extent `%s' (0x%lx - 0x%lx)\n", __func__, ex->ex_name, ex->ex_start, ex->ex_end); printf("%s: start 0x%lx, end 0x%lx\n", __func__, start, end); panic("%s: region lies outside extent", __func__); #else return (EINVAL); #endif } /* * Allocate the region descriptor. It will be freed later * if we can coalesce with another region. */ myrp = extent_alloc_region_descriptor(ex, flags); if (myrp == NULL) { #ifdef DIAGNOSTIC printf( "%s: can't allocate region descriptor\n", __func__); #endif return (ENOMEM); } alloc_start: /* * Attempt to place ourselves in the desired area of the * extent. We save ourselves some work by keeping the list sorted. * In other words, if the start of the current region is greater * than the end of our region, we don't have to search any further. */ /* * Keep a pointer to the last region we looked at so * that we don't have to traverse the list again when * we insert ourselves. If "last" is NULL when we * finally insert ourselves, we go at the head of the * list. See extent_insert_and_optimize() for details. */ last = NULL; LIST_FOREACH(rp, &ex->ex_regions, er_link) { if (rp->er_start > end) { /* * We lie before this region and don't * conflict. */ break; } /* * The current region begins before we end. * Check for a conflict. */ if (rp->er_end >= start) { /* * We conflict. If we can (and want to) wait, * do so. */ if (flags & EX_WAITSPACE) { ex->ex_flags |= EXF_WANTED; error = tsleep(ex, PRIBIO | ((flags & EX_CATCH) ? PCATCH : 0), "extnt", 0); if (error) return (error); goto alloc_start; } /* * If we tolerate conflicts adjust things such * that all space in the requested region is * allocated. */ if (flags & EX_CONFLICTOK) { /* * There are four possibilities: * * 1. The current region overlaps with * the start of the requested region. * Adjust the requested region to * start at the end of the current * region and try again. * * 2. The current region falls * completely within the requested * region. Free the current region * and try again. * * 3. The current region overlaps with * the end of the requested region. * Adjust the requested region to * end at the start of the current * region and try again. * * 4. The requested region falls * completely within the current * region. We're done. */ if (rp->er_start <= start) { if (rp->er_end < ex->ex_end) { start = rp->er_end + 1; size = end - start + 1; goto alloc_start; } } else if (rp->er_end < end) { LIST_REMOVE(rp, er_link); extent_free_region_descriptor(ex, rp); goto alloc_start; } else if (rp->er_start < end) { if (rp->er_start > ex->ex_start) { end = rp->er_start - 1; size = end - start + 1; goto alloc_start; } } return (0); } extent_free_region_descriptor(ex, myrp); return (EAGAIN); } /* * We don't conflict, but this region lies before * us. Keep a pointer to this region, and keep * trying. */ last = rp; } /* * We don't conflict with any regions. "last" points * to the region we fall after, or is NULL if we belong * at the beginning of the region list. Insert ourselves. */ extent_insert_and_optimize(ex, start, size, last, myrp); return (0); } /* * Macro to check (x + y) <= z. This check is designed to fail * if an overflow occurs. */ #define LE_OV(x, y, z) ((((x) + (y)) >= (x)) && (((x) + (y)) <= (z))) /* * Allocate a region in an extent map subregion. * * If EX_FAST is specified, we return the first fit in the map. * Otherwise, we try to minimize fragmentation by finding the * smallest gap that will hold the request. * * The allocated region is aligned to "alignment", which must be * a power of 2. */ int extent_do_alloc(struct extent *ex, u_long substart, u_long subend, u_long size, u_long alignment, u_long skew, u_long boundary, int flags, struct extent_region *myrp, u_long *result) { struct extent_region *rp, *last, *bestlast; u_long newstart, newend, exend, beststart, bestovh, ovh; u_long dontcross; int error; #ifdef DIAGNOSTIC /* Check arguments. */ if (ex == NULL) panic("%s: NULL extent", __func__); if (myrp == NULL) panic("%s: NULL region descriptor", __func__); if (result == NULL) panic("%s: NULL result pointer", __func__); if ((substart < ex->ex_start) || (substart > ex->ex_end) || (subend > ex->ex_end) || (subend < ex->ex_start)) { printf("%s: extent `%s', ex_start 0x%lx, ex_end 0x%lx\n", __func__, ex->ex_name, ex->ex_start, ex->ex_end); printf("%s: substart 0x%lx, subend 0x%lx\n", __func__, substart, subend); panic("%s: bad subregion", __func__); } if ((size < 1) || ((size - 1) > (subend - substart))) { printf("%s: extent `%s', size 0x%lx\n", __func__, ex->ex_name, size); panic("%s: bad size", __func__); } if (alignment == 0) panic("%s: bad alignment", __func__); if (boundary && (boundary < size)) { printf("%s: extent `%s', size 0x%lx, boundary 0x%lx\n", __func__, ex->ex_name, size, boundary); panic("%s: bad boundary", __func__); } #endif alloc_start: /* * Keep a pointer to the last region we looked at so * that we don't have to traverse the list again when * we insert ourselves. If "last" is NULL when we * finally insert ourselves, we go at the head of the * list. See extent_insert_and_optimize() for details. */ last = NULL; /* * Keep track of size and location of the smallest * chunk we fit in. * * Since the extent can be as large as the numeric range * of the CPU (0 - 0xffffffff for 32-bit systems), the * best overhead value can be the maximum unsigned integer. * Thus, we initialize "bestovh" to 0, since we insert ourselves * into the region list immediately on an exact match (which * is the only case where "bestovh" would be set to 0). */ bestovh = 0; beststart = 0; bestlast = NULL; /* * Keep track of end of free region. This is either the end of extent * or the start of a region past the subend. */ exend = ex->ex_end; /* * For N allocated regions, we must make (N + 1) * checks for unallocated space. The first chunk we * check is the area from the beginning of the subregion * to the first allocated region after that point. */ newstart = extent_align(substart, alignment, skew); if (newstart < ex->ex_start) { #ifdef DIAGNOSTIC printf("%s: extent `%s' (0x%lx - 0x%lx), alignment 0x%lx\n", __func__, ex->ex_name, ex->ex_start, ex->ex_end, alignment); panic("%s: overflow after alignment", __func__); #else extent_free_region_descriptor(ex, myrp); return (EINVAL); #endif } /* * Find the first allocated region that begins on or after * the subregion start, advancing the "last" pointer along * the way. */ LIST_FOREACH(rp, &ex->ex_regions, er_link) { if (rp->er_start >= newstart) break; last = rp; } /* * Relocate the start of our candidate region to the end of * the last allocated region (if there was one overlapping * our subrange). */ if (last != NULL && last->er_end >= newstart) newstart = extent_align((last->er_end + 1), alignment, skew); for (; rp != NULL; rp = LIST_NEXT(rp, er_link)) { /* * If the region pasts the subend, bail out and see * if we fit against the subend. */ if (rp->er_start > subend) { exend = rp->er_start; break; } /* * Check the chunk before "rp". Note that our * comparison is safe from overflow conditions. */ if (LE_OV(newstart, size, rp->er_start)) { /* * Do a boundary check, if necessary. Note * that a region may *begin* on the boundary, * but it must end before the boundary. */ if (boundary) { newend = newstart + (size - 1); /* * Calculate the next boundary after the start * of this region. */ dontcross = extent_align(newstart+1, boundary, (flags & EX_BOUNDZERO) ? 0 : ex->ex_start) - 1; #if 0 printf("newstart=%lx newend=%lx ex_start=%lx ex_end=%lx boundary=%lx dontcross=%lx\n", newstart, newend, ex->ex_start, ex->ex_end, boundary, dontcross); #endif /* Check for overflow */ if (dontcross < ex->ex_start) dontcross = ex->ex_end; else if (newend > dontcross) { /* * Candidate region crosses boundary. * Throw away the leading part and see * if we still fit. */ newstart = dontcross + 1; newend = newstart + (size - 1); dontcross += boundary; if (!LE_OV(newstart, size, rp->er_start)) goto skip; } /* * If we run past the end of * the extent or the boundary * overflows, then the request * can't fit. */ if (newstart + size - 1 > ex->ex_end || dontcross < newstart) goto fail; } /* * We would fit into this space. Calculate * the overhead (wasted space). If we exactly * fit, or we're taking the first fit, insert * ourselves into the region list. */ ovh = rp->er_start - newstart - size; if ((flags & EX_FAST) || (ovh == 0)) goto found; /* * Don't exactly fit, but check to see * if we're better than any current choice. */ if ((bestovh == 0) || (ovh < bestovh)) { bestovh = ovh; beststart = newstart; bestlast = last; } } skip: /* * Skip past the current region and check again. */ newstart = extent_align((rp->er_end + 1), alignment, skew); if (newstart < rp->er_end) { /* * Overflow condition. Don't error out, since * we might have a chunk of space that we can * use. */ goto fail; } last = rp; } /* * The final check is from the current starting point to the * end of the subregion. If there were no allocated regions, * "newstart" is set to the beginning of the subregion, or * just past the end of the last allocated region, adjusted * for alignment in either case. */ if (LE_OV(newstart, (size - 1), subend)) { /* * Do a boundary check, if necessary. Note * that a region may *begin* on the boundary, * but it must end before the boundary. */ if (boundary) { newend = newstart + (size - 1); /* * Calculate the next boundary after the start * of this region. */ dontcross = extent_align(newstart+1, boundary, (flags & EX_BOUNDZERO) ? 0 : ex->ex_start) - 1; #if 0 printf("newstart=%lx newend=%lx ex_start=%lx ex_end=%lx boundary=%lx dontcross=%lx\n", newstart, newend, ex->ex_start, ex->ex_end, boundary, dontcross); #endif /* Check for overflow */ if (dontcross < ex->ex_start) dontcross = ex->ex_end; else if (newend > dontcross) { /* * Candidate region crosses boundary. * Throw away the leading part and see * if we still fit. */ newstart = dontcross + 1; newend = newstart + (size - 1); dontcross += boundary; if (!LE_OV(newstart, (size - 1), subend)) goto fail; } /* * If we run past the end of * the extent or the boundary * overflows, then the request * can't fit. */ if (newstart + size - 1 > ex->ex_end || dontcross < newstart) goto fail; } /* * We would fit into this space. Calculate * the overhead (wasted space). If we exactly * fit, or we're taking the first fit, insert * ourselves into the region list. */ ovh = exend - newstart - (size - 1); if ((flags & EX_FAST) || (ovh == 0)) goto found; /* * Don't exactly fit, but check to see * if we're better than any current choice. */ if ((bestovh == 0) || (ovh < bestovh)) { bestovh = ovh; beststart = newstart; bestlast = last; } } fail: /* * One of the following two conditions have * occurred: * * There is no chunk large enough to hold the request. * * If EX_FAST was not specified, there is not an * exact match for the request. * * Note that if we reach this point and EX_FAST is * set, then we know there is no space in the extent for * the request. */ if (((flags & EX_FAST) == 0) && (bestovh != 0)) { /* * We have a match that's "good enough". */ newstart = beststart; last = bestlast; goto found; } /* * No space currently available. Wait for it to free up, * if possible. */ if (flags & EX_WAITSPACE) { ex->ex_flags |= EXF_WANTED; error = tsleep(ex, PRIBIO | ((flags & EX_CATCH) ? PCATCH : 0), "extnt", 0); if (error) return (error); goto alloc_start; } extent_free_region_descriptor(ex, myrp); return (EAGAIN); found: /* * Insert ourselves into the region list. */ extent_insert_and_optimize(ex, newstart, size, last, myrp); *result = newstart; return (0); } int extent_alloc_subregion(struct extent *ex, u_long substart, u_long subend, u_long size, u_long alignment, u_long skew, u_long boundary, int flags, u_long *result) { struct extent_region *rp; /* * Allocate the region descriptor. It will be freed later * if we can coalesce with another region. */ rp = extent_alloc_region_descriptor(ex, flags); if (rp == NULL) { #ifdef DIAGNOSTIC printf("%s: can't allocate region descriptor\n", __func__); #endif return (ENOMEM); } return extent_do_alloc(ex, substart, subend, size, alignment, skew, boundary, flags, rp, result); } int extent_alloc_subregion_with_descr(struct extent *ex, u_long substart, u_long subend, u_long size, u_long alignment, u_long skew, u_long boundary, int flags, struct extent_region *rp, u_long *result) { #ifdef DIAGNOSTIC if ((ex->ex_flags & EXF_NOCOALESCE) == 0) panic("%s: EX_NOCOALESCE not set", __func__); #endif rp->er_flags = ER_DISCARD; return extent_do_alloc(ex, substart, subend, size, alignment, skew, boundary, flags, rp, result); } int extent_free(struct extent *ex, u_long start, u_long size, int flags) { struct extent_region *rp, *nrp = NULL; u_long end = start + (size - 1); int exflags; #ifdef DIAGNOSTIC /* Check arguments. */ if (ex == NULL) panic("%s: NULL extent", __func__); if ((start < ex->ex_start) || (end > ex->ex_end)) { extent_print(ex); printf("%s: extent `%s', start 0x%lx, size 0x%lx\n", __func__, ex->ex_name, start, size); panic("%s: extent `%s', region not within extent", __func__, ex->ex_name); } /* Check for an overflow. */ if (end < start) { extent_print(ex); printf("%s: extent `%s', start 0x%lx, size 0x%lx\n", __func__, ex->ex_name, start, size); panic("%s: overflow", __func__); } #endif /* * If we're allowing coalescing, we must allocate a region * descriptor now, since it might block. * * XXX Make a static, create-time flags word, so we don't * XXX have to lock to read it! */ exflags = ex->ex_flags; if ((exflags & EXF_NOCOALESCE) == 0) { /* Allocate a region descriptor. */ nrp = extent_alloc_region_descriptor(ex, flags); if (nrp == NULL) return (ENOMEM); } /* * Find region and deallocate. Several possibilities: * * 1. (start == er_start) && (end == er_end): * Free descriptor. * * 2. (start == er_start) && (end < er_end): * Adjust er_start. * * 3. (start > er_start) && (end == er_end): * Adjust er_end. * * 4. (start > er_start) && (end < er_end): * Fragment region. Requires descriptor alloc. * * Cases 2, 3, and 4 require that the EXF_NOCOALESCE flag * is not set. */ LIST_FOREACH(rp, &ex->ex_regions, er_link) { /* * Save ourselves some comparisons; does the current * region end before chunk to be freed begins? If so, * then we haven't found the appropriate region descriptor. */ if (rp->er_end < start) continue; /* * Save ourselves some traversal; does the current * region begin after the chunk to be freed ends? If so, * then we've already passed any possible region descriptors * that might have contained the chunk to be freed. */ if (rp->er_start > end) break; /* Case 1. */ if ((start == rp->er_start) && (end == rp->er_end)) { LIST_REMOVE(rp, er_link); extent_free_region_descriptor(ex, rp); goto done; } /* * The following cases all require that EXF_NOCOALESCE * is not set. */ if (ex->ex_flags & EXF_NOCOALESCE) continue; /* Case 2. */ if ((start == rp->er_start) && (end < rp->er_end)) { rp->er_start = (end + 1); goto done; } /* Case 3. */ if ((start > rp->er_start) && (end == rp->er_end)) { rp->er_end = (start - 1); goto done; } /* Case 4. */ if ((start > rp->er_start) && (end < rp->er_end)) { /* Fill in new descriptor. */ nrp->er_start = end + 1; nrp->er_end = rp->er_end; /* Adjust current descriptor. */ rp->er_end = start - 1; /* Insert new descriptor after current. */ LIST_INSERT_AFTER(rp, nrp, er_link); /* We used the new descriptor, so don't free it below */ nrp = NULL; goto done; } } /* Region not found, or request otherwise invalid. */ #if defined(DIAGNOSTIC) || defined(DDB) extent_print(ex); #endif printf("%s: start 0x%lx, end 0x%lx\n", __func__, start, end); panic("%s: region not found", __func__); done: if (nrp != NULL) extent_free_region_descriptor(ex, nrp); if (ex->ex_flags & EXF_WANTED) { ex->ex_flags &= ~EXF_WANTED; wakeup(ex); } return (0); } static struct extent_region * extent_alloc_region_descriptor(struct extent *ex, int flags) { struct extent_region *rp; if (ex->ex_flags & EXF_FIXED) { struct extent_fixed *fex = (struct extent_fixed *)ex; while (LIST_EMPTY(&fex->fex_freelist)) { if (flags & EX_MALLOCOK) goto alloc; if ((flags & EX_WAITOK) == 0) return (NULL); ex->ex_flags |= EXF_FLWANTED; if (tsleep(&fex->fex_freelist, PRIBIO | ((flags & EX_CATCH) ? PCATCH : 0), "extnt", 0)) return (NULL); } rp = LIST_FIRST(&fex->fex_freelist); LIST_REMOVE(rp, er_link); /* * Don't muck with flags after pulling it off the * freelist; it may be a dynamically allocated * region pointer that was kindly given to us, * and we need to preserve that information. */ return (rp); } alloc: rp = pool_get(&ex_region_pl, (flags & EX_WAITOK) ? PR_WAITOK : PR_NOWAIT); if (rp != NULL) rp->er_flags = ER_ALLOC; return (rp); } static void extent_free_region_descriptor(struct extent *ex, struct extent_region *rp) { if (rp->er_flags & ER_DISCARD) return; if (ex->ex_flags & EXF_FIXED) { struct extent_fixed *fex = (struct extent_fixed *)ex; /* * If someone's waiting for a region descriptor, * be nice and give them this one, rather than * just free'ing it back to the system. */ if (rp->er_flags & ER_ALLOC) { if (ex->ex_flags & EXF_FLWANTED) { /* Clear all but ER_ALLOC flag. */ rp->er_flags = ER_ALLOC; LIST_INSERT_HEAD(&fex->fex_freelist, rp, er_link); goto wake_em_up; } else { pool_put(&ex_region_pl, rp); } } else { /* Clear all flags. */ rp->er_flags = 0; LIST_INSERT_HEAD(&fex->fex_freelist, rp, er_link); } if (ex->ex_flags & EXF_FLWANTED) { wake_em_up: ex->ex_flags &= ~EXF_FLWANTED; wakeup(&fex->fex_freelist); } return; } /* * We know it's dynamically allocated if we get here. */ pool_put(&ex_region_pl, rp); } #if defined(DIAGNOSTIC) || defined(DDB) || !defined(_KERNEL) void extent_print(struct extent *ex) { extent_print1(ex, printf); } void extent_print1(struct extent *ex, int (*pr)(const char *, ...) __attribute__((__format__(__kprintf__,1,2)))) { struct extent_region *rp; if (ex == NULL) panic("%s: NULL extent", __func__); #ifdef _KERNEL (*pr)("extent `%s' (0x%lx - 0x%lx), flags=%b\n", ex->ex_name, ex->ex_start, ex->ex_end, ex->ex_flags, EXF_BITS); #else (*pr)("extent `%s' (0x%lx - 0x%lx), flags = 0x%x\n", ex->ex_name, ex->ex_start, ex->ex_end, ex->ex_flags); #endif LIST_FOREACH(rp, &ex->ex_regions, er_link) (*pr)(" 0x%lx - 0x%lx\n", rp->er_start, rp->er_end); } #endif