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