Lines Matching +full:up +full:-
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
4 * Copyright (c) 2004 Poul-Henning Kamp
31 * These functions implement a mixed run-length/bitmap management of unit
36 * A return value of -1 signals that no more unit numbers are available.
51 * sleep so the free_unr() function does not come in a pre-locked variant.
131 #define UNR_NO_MTX ((void *)(uintptr_t)-1)
140 KASSERT(mp->state == 0, ("mutex already locked")); in mtx_lock()
141 mp->state = 1; in mtx_lock()
147 KASSERT(mp->state == 1, ("mutex not locked")); in mtx_unlock()
148 mp->state = 0; in mtx_unlock()
157 KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true")); in mtx_assert()
181 * - at the start of the allocator space, all elements in [low, low + first)
183 * - at the end of the allocator space, all elements in [high - last, high]
199 #define NBITS (NBBY * sizeof(((struct unrb *)NULL)->map))
202 is_bitmap(struct unrhdr *uh, struct unr *up) in is_bitmap() argument
204 return (up->ptr != uh && up->ptr != NULL); in is_bitmap()
212 bit_ffs(ub->map, len, &first_set); in ub_empty()
213 return (first_set == -1); in ub_empty()
222 bit_ffc(ub->map, len, &first_clear); in ub_full()
223 return (first_clear == -1); in ub_full()
227 * start: ipos = -1, upos = NULL;
228 * end: ipos = -1, upos = uh
243 iter->ipos = -1; in create_iter_unr()
244 iter->uh = uh; in create_iter_unr()
245 iter->upos = NULL; in create_iter_unr()
246 iter->upos_first_item = -1; in create_iter_unr()
253 struct unr *up; in next_iter_unrl() local
258 if (iter->ipos == -1) { in next_iter_unrl()
259 if (iter->upos == uh) in next_iter_unrl()
261 y = uh->low - 1; in next_iter_unrl()
262 if (uh->first == 0) { in next_iter_unrl()
263 up = TAILQ_FIRST(&uh->head); in next_iter_unrl()
264 if (up == NULL) { in next_iter_unrl()
265 iter->upos = uh; in next_iter_unrl()
268 iter->upos = up; in next_iter_unrl()
269 if (up->ptr == NULL) in next_iter_unrl()
270 iter->upos = NULL; in next_iter_unrl()
272 iter->upos_first_item = uh->low; in next_iter_unrl()
275 y = iter->ipos; in next_iter_unrl()
278 up = iter->upos; in next_iter_unrl()
281 if (up == NULL) { in next_iter_unrl()
282 if (y + 1 < uh->low + uh->first) { in next_iter_unrl()
283 iter->ipos = y + 1; in next_iter_unrl()
286 up = iter->upos = TAILQ_FIRST(&uh->head); in next_iter_unrl()
287 iter->upos_first_item = uh->low + uh->first; in next_iter_unrl()
291 if (y + 1 < iter->upos_first_item + up->len) { in next_iter_unrl()
292 if (up->ptr == uh) { in next_iter_unrl()
293 iter->ipos = y + 1; in next_iter_unrl()
295 } else if (is_bitmap(uh, up)) { in next_iter_unrl()
296 ub = up->ptr; in next_iter_unrl()
297 bit_ffs_at(&ub->map[0], in next_iter_unrl()
298 y + 1 - iter->upos_first_item, in next_iter_unrl()
299 up->len, &c); in next_iter_unrl()
300 if (c != -1) { in next_iter_unrl()
301 iter->ipos = iter->upos_first_item + c; in next_iter_unrl()
306 iter->upos_first_item += up->len; in next_iter_unrl()
307 y = iter->upos_first_item - 1; in next_iter_unrl()
308 up = iter->upos = TAILQ_NEXT((struct unr *)iter->upos, list); in next_iter_unrl()
309 if (iter->upos == NULL) { in next_iter_unrl()
310 iter->ipos = -1; in next_iter_unrl()
311 iter->upos = uh; in next_iter_unrl()
318 * returns -1 on end, otherwise the next element
327 uh = iter->uh; in next_iter_unr()
328 if (uh->mtx != NULL) in next_iter_unr()
329 mtx_lock(uh->mtx); in next_iter_unr()
331 if (uh->mtx != NULL) in next_iter_unr()
332 mtx_unlock(uh->mtx); in next_iter_unr()
333 return (iter->ipos); in next_iter_unr()
357 struct unr *up; in check_unrhdr() local
362 y = uh->first; in check_unrhdr()
364 TAILQ_FOREACH(up, &uh->head, list) { in check_unrhdr()
366 if (is_bitmap(uh, up)) { in check_unrhdr()
367 ub = up->ptr; in check_unrhdr()
368 KASSERT (up->len <= NBITS, in check_unrhdr()
370 up->len, NBITS, line)); in check_unrhdr()
373 bit_count(ub->map, 0, up->len, &w); in check_unrhdr()
375 } else if (up->ptr != NULL) in check_unrhdr()
376 y += up->len; in check_unrhdr()
378 KASSERT (y == uh->busy, in check_unrhdr()
380 uh->busy, y, line)); in check_unrhdr()
381 KASSERT (z == uh->alloc, in check_unrhdr()
383 uh->alloc, z, line)); in check_unrhdr()
406 uh->alloc++; in new_unr()
422 struct unr *up; in delete_unr() local
424 uh->alloc--; in delete_unr()
425 up = ptr; in delete_unr()
426 TAILQ_INSERT_TAIL(&uh->ppfree, up, list); in delete_unr()
432 struct unr *up; in clean_unrhdrl() local
434 if (uh->mtx != NULL) in clean_unrhdrl()
435 mtx_assert(uh->mtx, MA_OWNED); in clean_unrhdrl()
436 while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) { in clean_unrhdrl()
437 TAILQ_REMOVE(&uh->ppfree, up, list); in clean_unrhdrl()
438 if (uh->mtx != NULL) in clean_unrhdrl()
439 mtx_unlock(uh->mtx); in clean_unrhdrl()
440 Free(up); in clean_unrhdrl()
441 if (uh->mtx != NULL) in clean_unrhdrl()
442 mtx_lock(uh->mtx); in clean_unrhdrl()
451 if (uh->mtx != NULL) in clean_unrhdr()
452 mtx_lock(uh->mtx); in clean_unrhdr()
454 if (uh->mtx != NULL) in clean_unrhdr()
455 mtx_unlock(uh->mtx); in clean_unrhdr()
465 uh->mtx = NULL; in init_unrhdr()
467 uh->mtx = mutex; in init_unrhdr()
469 uh->mtx = &unitmtx; in init_unrhdr()
470 TAILQ_INIT(&uh->head); in init_unrhdr()
471 TAILQ_INIT(&uh->ppfree); in init_unrhdr()
472 uh->low = low; in init_unrhdr()
473 uh->high = high; in init_unrhdr()
474 uh->first = 0; in init_unrhdr()
475 uh->last = 1 + (high - low); in init_unrhdr()
476 uh->busy = 0; in init_unrhdr()
477 uh->alloc = 0; in init_unrhdr()
502 KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy)); in delete_unrhdr()
503 KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr")); in delete_unrhdr()
504 KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL, in delete_unrhdr()
512 struct unr *up, *uq; in clear_unrhdr() local
514 KASSERT(TAILQ_EMPTY(&uh->ppfree), in clear_unrhdr()
516 TAILQ_FOREACH_SAFE(up, &uh->head, list, uq) { in clear_unrhdr()
517 if (up->ptr != uh) { in clear_unrhdr()
518 Free(up->ptr); in clear_unrhdr()
520 Free(up); in clear_unrhdr()
522 uh->busy = 0; in clear_unrhdr()
523 uh->alloc = 0; in clear_unrhdr()
524 init_unrhdr(uh, uh->low, uh->high, uh->mtx); in clear_unrhdr()
541 struct unr *up, *uf, *us; in optimize_unr() local
551 TAILQ_FOREACH(uf, &uh->head, list) { in optimize_unr()
552 if (uf->len >= NBITS) in optimize_unr()
557 l = uf->len; in optimize_unr()
558 up = uf; in optimize_unr()
560 up = TAILQ_NEXT(up, list); in optimize_unr()
561 if (up == NULL) in optimize_unr()
563 if ((up->len + l) > NBITS) in optimize_unr()
566 if (is_bitmap(uh, up)) in optimize_unr()
568 l += up->len; in optimize_unr()
585 TAILQ_REMOVE(&uh->head, us, list); in optimize_unr()
586 a = us->len; in optimize_unr()
587 l = us->ptr == uh ? 1 : 0; in optimize_unr()
589 bit_nclear(ub->map, 0, NBITS - 1); in optimize_unr()
591 bit_nset(ub->map, 0, a); in optimize_unr()
593 if (uf->ptr == NULL) in optimize_unr()
594 bit_nclear(ub->map, a, a + uf->len - 1); in optimize_unr()
596 bit_nset(ub->map, a, a + uf->len - 1); in optimize_unr()
597 uf->ptr = ub; in optimize_unr()
598 uf->len += a; in optimize_unr()
601 ubf = uf->ptr; in optimize_unr()
602 for (l = 0; l < uf->len; l++, a++) { in optimize_unr()
603 if (bit_test(ubf->map, l)) in optimize_unr()
604 bit_set(ub->map, a); in optimize_unr()
606 bit_clear(ub->map, a); in optimize_unr()
608 uf->len = a; in optimize_unr()
609 delete_unr(uh, uf->ptr); in optimize_unr()
610 uf->ptr = ub; in optimize_unr()
614 ub = us->ptr; in optimize_unr()
619 if (uf->len + us->len > NBITS) in optimize_unr()
621 if (uf->ptr == NULL) { in optimize_unr()
622 bit_nclear(ub->map, us->len, us->len + uf->len - 1); in optimize_unr()
623 us->len += uf->len; in optimize_unr()
624 TAILQ_REMOVE(&uh->head, uf, list); in optimize_unr()
626 } else if (uf->ptr == uh) { in optimize_unr()
627 bit_nset(ub->map, us->len, us->len + uf->len - 1); in optimize_unr()
628 us->len += uf->len; in optimize_unr()
629 TAILQ_REMOVE(&uh->head, uf, list); in optimize_unr()
632 ubf = uf->ptr; in optimize_unr()
633 for (l = 0; l < uf->len; l++, us->len++) { in optimize_unr()
634 if (bit_test(ubf->map, l)) in optimize_unr()
635 bit_set(ub->map, us->len); in optimize_unr()
637 bit_clear(ub->map, us->len); in optimize_unr()
639 TAILQ_REMOVE(&uh->head, uf, list); in optimize_unr()
652 collapse_unr(struct unrhdr *uh, struct unr *up) in collapse_unr() argument
658 if (is_bitmap(uh, up)) { in collapse_unr()
659 ub = up->ptr; in collapse_unr()
660 if (ub_full(ub, up->len)) { in collapse_unr()
661 delete_unr(uh, up->ptr); in collapse_unr()
662 up->ptr = uh; in collapse_unr()
663 } else if (ub_empty(ub, up->len)) { in collapse_unr()
664 delete_unr(uh, up->ptr); in collapse_unr()
665 up->ptr = NULL; in collapse_unr()
670 if (up->len == 0) { in collapse_unr()
671 upp = TAILQ_PREV(up, unrhd, list); in collapse_unr()
673 upp = TAILQ_NEXT(up, list); in collapse_unr()
674 TAILQ_REMOVE(&uh->head, up, list); in collapse_unr()
675 delete_unr(uh, up); in collapse_unr()
676 up = upp; in collapse_unr()
679 /* If we have "hot-spot" still, merge with neighbor if possible */ in collapse_unr()
680 if (up != NULL) { in collapse_unr()
681 upp = TAILQ_PREV(up, unrhd, list); in collapse_unr()
682 if (upp != NULL && up->ptr == upp->ptr) { in collapse_unr()
683 up->len += upp->len; in collapse_unr()
684 TAILQ_REMOVE(&uh->head, upp, list); in collapse_unr()
687 upp = TAILQ_NEXT(up, list); in collapse_unr()
688 if (upp != NULL && up->ptr == upp->ptr) { in collapse_unr()
689 up->len += upp->len; in collapse_unr()
690 TAILQ_REMOVE(&uh->head, upp, list); in collapse_unr()
695 /* Merge into ->first if possible */ in collapse_unr()
696 upp = TAILQ_FIRST(&uh->head); in collapse_unr()
697 if (upp != NULL && upp->ptr == uh) { in collapse_unr()
698 uh->first += upp->len; in collapse_unr()
699 TAILQ_REMOVE(&uh->head, upp, list); in collapse_unr()
701 if (up == upp) in collapse_unr()
702 up = NULL; in collapse_unr()
705 /* Merge into ->last if possible */ in collapse_unr()
706 upp = TAILQ_LAST(&uh->head, unrhd); in collapse_unr()
707 if (upp != NULL && upp->ptr == NULL) { in collapse_unr()
708 uh->last += upp->len; in collapse_unr()
709 TAILQ_REMOVE(&uh->head, upp, list); in collapse_unr()
711 if (up == upp) in collapse_unr()
712 up = NULL; in collapse_unr()
726 struct unr *up; in alloc_unrl() local
731 if (uh->mtx != NULL) in alloc_unrl()
732 mtx_assert(uh->mtx, MA_OWNED); in alloc_unrl()
734 x = uh->low + uh->first; in alloc_unrl()
736 up = TAILQ_FIRST(&uh->head); in alloc_unrl()
741 if (up == NULL && uh->last > 0) { in alloc_unrl()
742 uh->first++; in alloc_unrl()
743 uh->last--; in alloc_unrl()
744 uh->busy++; in alloc_unrl()
752 if (up == NULL) in alloc_unrl()
753 return (-1); in alloc_unrl()
755 KASSERT(up->ptr != uh, ("UNR first element is allocated")); in alloc_unrl()
757 if (up->ptr == NULL) { /* free run */ in alloc_unrl()
758 uh->first++; in alloc_unrl()
759 up->len--; in alloc_unrl()
761 ub = up->ptr; in alloc_unrl()
762 bit_ffc(ub->map, up->len, &y); in alloc_unrl()
763 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap.")); in alloc_unrl()
764 bit_set(ub->map, y); in alloc_unrl()
767 uh->busy++; in alloc_unrl()
768 collapse_unr(uh, up); in alloc_unrl()
777 if (uh->mtx != NULL) in alloc_unr()
778 mtx_lock(uh->mtx); in alloc_unr()
781 if (uh->mtx != NULL) in alloc_unr()
782 mtx_unlock(uh->mtx); in alloc_unr()
789 struct unr *up, *upn; in alloc_unr_specificl() local
793 if (uh->mtx != NULL) in alloc_unr_specificl()
794 mtx_assert(uh->mtx, MA_OWNED); in alloc_unr_specificl()
796 if (item < uh->low + uh->first || item > uh->high) in alloc_unr_specificl()
797 return (-1); in alloc_unr_specificl()
799 up = TAILQ_FIRST(&uh->head); in alloc_unr_specificl()
801 if (up == NULL && item - uh->low == uh->first) { in alloc_unr_specificl()
802 uh->first++; in alloc_unr_specificl()
803 uh->last--; in alloc_unr_specificl()
804 uh->busy++; in alloc_unr_specificl()
809 i = item - uh->low - uh->first; in alloc_unr_specificl()
811 if (up == NULL) { in alloc_unr_specificl()
812 up = new_unr(uh, p1, p2); in alloc_unr_specificl()
813 up->ptr = NULL; in alloc_unr_specificl()
814 up->len = i; in alloc_unr_specificl()
815 TAILQ_INSERT_TAIL(&uh->head, up, list); in alloc_unr_specificl()
816 up = new_unr(uh, p1, p2); in alloc_unr_specificl()
817 up->ptr = uh; in alloc_unr_specificl()
818 up->len = 1; in alloc_unr_specificl()
819 TAILQ_INSERT_TAIL(&uh->head, up, list); in alloc_unr_specificl()
820 uh->last = uh->high - uh->low - i; in alloc_unr_specificl()
821 uh->busy++; in alloc_unr_specificl()
826 TAILQ_FOREACH(up, &uh->head, list) { in alloc_unr_specificl()
827 if (up->len > i) in alloc_unr_specificl()
829 i -= up->len; in alloc_unr_specificl()
833 if (up == NULL) { in alloc_unr_specificl()
835 up = new_unr(uh, p1, p2); in alloc_unr_specificl()
836 up->ptr = NULL; in alloc_unr_specificl()
837 up->len = i; in alloc_unr_specificl()
838 TAILQ_INSERT_TAIL(&uh->head, up, list); in alloc_unr_specificl()
840 up = new_unr(uh, p1, p2); in alloc_unr_specificl()
841 up->ptr = uh; in alloc_unr_specificl()
842 up->len = 1; in alloc_unr_specificl()
843 TAILQ_INSERT_TAIL(&uh->head, up, list); in alloc_unr_specificl()
847 if (is_bitmap(uh, up)) { in alloc_unr_specificl()
848 ub = up->ptr; in alloc_unr_specificl()
849 if (bit_test(ub->map, i) == 0) { in alloc_unr_specificl()
850 bit_set(ub->map, i); in alloc_unr_specificl()
853 return (-1); in alloc_unr_specificl()
854 } else if (up->ptr == uh) in alloc_unr_specificl()
855 return (-1); in alloc_unr_specificl()
857 KASSERT(up->ptr == NULL, in alloc_unr_specificl()
858 ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up)); in alloc_unr_specificl()
861 tl = up->len - (1 + i); in alloc_unr_specificl()
864 upn->ptr = NULL; in alloc_unr_specificl()
865 upn->len = tl; in alloc_unr_specificl()
866 TAILQ_INSERT_AFTER(&uh->head, up, upn, list); in alloc_unr_specificl()
872 upn->len = i; in alloc_unr_specificl()
873 upn->ptr = NULL; in alloc_unr_specificl()
874 TAILQ_INSERT_BEFORE(up, upn, list); in alloc_unr_specificl()
876 up->len = 1; in alloc_unr_specificl()
877 up->ptr = uh; in alloc_unr_specificl()
880 last = uh->high - uh->low - (item - uh->low); in alloc_unr_specificl()
881 if (uh->last > last) in alloc_unr_specificl()
882 uh->last = last; in alloc_unr_specificl()
883 uh->busy++; in alloc_unr_specificl()
884 collapse_unr(uh, up); in alloc_unr_specificl()
900 if (uh->mtx != NULL) in alloc_unr_specific()
901 mtx_lock(uh->mtx); in alloc_unr_specific()
903 if (uh->mtx != NULL) in alloc_unr_specific()
904 mtx_unlock(uh->mtx); in alloc_unr_specific()
922 struct unr *up, *upp, *upn; in free_unrl() local
926 KASSERT(item >= uh->low && item <= uh->high, in free_unrl()
928 item, uh->low, uh->high)); in free_unrl()
930 item -= uh->low; in free_unrl()
931 upp = TAILQ_FIRST(&uh->head); in free_unrl()
935 if (item + 1 == uh->first && upp == NULL) { in free_unrl()
936 uh->last++; in free_unrl()
937 uh->first--; in free_unrl()
938 uh->busy--; in free_unrl()
943 * Freeing in the ->first section. Create a run starting at the in free_unrl()
946 if (item < uh->first) { in free_unrl()
947 up = new_unr(uh, p1, p2); in free_unrl()
948 up->ptr = uh; in free_unrl()
949 up->len = uh->first - item; in free_unrl()
950 TAILQ_INSERT_HEAD(&uh->head, up, list); in free_unrl()
951 uh->first -= up->len; in free_unrl()
954 item -= uh->first; in free_unrl()
957 TAILQ_FOREACH(up, &uh->head, list) { in free_unrl()
958 if (up->len > item) in free_unrl()
960 item -= up->len; in free_unrl()
964 if (is_bitmap(uh, up)) { in free_unrl()
965 ub = up->ptr; in free_unrl()
967 KASSERT(bit_test(ub->map, item) != 0, in free_unrl()
969 bit_clear(ub->map, item); in free_unrl()
970 uh->busy--; in free_unrl()
971 collapse_unr(uh, up); in free_unrl()
975 KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item)); in free_unrl()
978 if (up->len == 1) { in free_unrl()
979 up->ptr = NULL; in free_unrl()
980 uh->busy--; in free_unrl()
981 collapse_unr(uh, up); in free_unrl()
986 upp = TAILQ_PREV(up, unrhd, list); in free_unrl()
987 if (item == 0 && upp != NULL && upp->ptr == NULL) { in free_unrl()
988 upp->len++; in free_unrl()
989 up->len--; in free_unrl()
990 uh->busy--; in free_unrl()
991 collapse_unr(uh, up); in free_unrl()
996 upn = TAILQ_NEXT(up, list); in free_unrl()
997 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) { in free_unrl()
998 upn->len++; in free_unrl()
999 up->len--; in free_unrl()
1000 uh->busy--; in free_unrl()
1001 collapse_unr(uh, up); in free_unrl()
1006 pl = up->len - (1 + item); in free_unrl()
1009 upp->ptr = uh; in free_unrl()
1010 upp->len = pl; in free_unrl()
1011 TAILQ_INSERT_AFTER(&uh->head, up, upp, list); in free_unrl()
1017 upp->len = item; in free_unrl()
1018 upp->ptr = uh; in free_unrl()
1019 TAILQ_INSERT_BEFORE(up, upp, list); in free_unrl()
1021 up->len = 1; in free_unrl()
1022 up->ptr = NULL; in free_unrl()
1023 uh->busy--; in free_unrl()
1024 collapse_unr(uh, up); in free_unrl()
1035 if (uh->mtx != NULL) in free_unr()
1036 mtx_lock(uh->mtx); in free_unr()
1039 if (uh->mtx != NULL) in free_unr()
1040 mtx_unlock(uh->mtx); in free_unr()
1061 print_unr(struct unrhdr *uh, struct unr *up) in print_unr() argument
1066 db_printf(" %p len = %5u ", up, up->len); in print_unr()
1067 if (up->ptr == NULL) in print_unr()
1069 else if (up->ptr == uh) in print_unr()
1072 ub = up->ptr; in print_unr()
1074 for (x = 0; x < up->len; x++) { in print_unr()
1075 if (bit_test(ub->map, x)) in print_unr()
1087 struct unr *up; in print_unrhdr() local
1092 uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc); in print_unrhdr()
1093 x = uh->low + uh->first; in print_unrhdr()
1094 TAILQ_FOREACH(up, &uh->head, list) { in print_unrhdr()
1096 print_unr(uh, up); in print_unrhdr()
1097 if (up->ptr == NULL || up->ptr == uh) in print_unrhdr()
1098 x += up->len; in print_unrhdr()
1121 iter, iter->uh, iter->ipos, iter->upos, iter->upos_first_item); in print_unrhdr_iter()
1157 if (j != -1) { in test_alloc_unr()
1171 if (j == -1) { in test_alloc_unr_specific()
1188 return (*(const int *)a - *(const int *)b); in test_iter_compar()
1244 while ((v = next_iter_unr(ihandle)) != -1) { in test_iter()
1267 printf("%s [-h] [-i] [-r REPETITIONS] [-v]\n", argv[0]); in usage()
1284 while ((ch = getopt(argc, argv, "hir:v")) != -1) { in main()
1313 uh = new_unrhdr(0, count - 1, NULL); in main()