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