sys/kern/subr_unit.c

223 check_unrhdr(struct unrhdr *uh, int line)
230 	y = uh->first;
232 	TAILQ_FOREACH(up, &uh->head, list) {
234 		if (up->ptr != uh && up->ptr != NULL) {
246 	KASSERT (y == uh->busy,
248 	    uh->busy, y, line));
249 	KASSERT (z == uh->alloc,
251 	    uh->alloc, z, line));
257 check_unrhdr(struct unrhdr *uh __unused, int line __unused)
271 new_unr(struct unrhdr *uh, void **p1, void **p2)
275 	uh->alloc++;
289 delete_unr(struct unrhdr *uh, void *ptr)
293 	uh->alloc--;
295 	TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
299 clean_unrhdrl(struct unrhdr *uh)
303 	mtx_assert(uh->mtx, MA_OWNED);
304 	while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
305 		TAILQ_REMOVE(&uh->ppfree, up, list);
306 		mtx_unlock(uh->mtx);
308 		mtx_lock(uh->mtx);
314 clean_unrhdr(struct unrhdr *uh)
317 	mtx_lock(uh->mtx);
318 	clean_unrhdrl(uh);
319 	mtx_unlock(uh->mtx);
323 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
329 		uh->mtx = mutex;
331 		uh->mtx = &unitmtx;
332 	TAILQ_INIT(&uh->head);
333 	TAILQ_INIT(&uh->ppfree);
334 	uh->low = low;
335 	uh->high = high;
336 	uh->first = 0;
337 	uh->last = 1 + (high - low);
338 	check_unrhdr(uh, __LINE__);
350 	struct unrhdr *uh;
352 	uh = Malloc(sizeof *uh);
353 	init_unrhdr(uh, low, high, mutex);
354 	return (uh);
358 delete_unrhdr(struct unrhdr *uh)
361 	check_unrhdr(uh, __LINE__);
362 	KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
363 	KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
364 	KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
366 	Free(uh);
370 is_bitmap(struct unrhdr *uh, struct unr *up)
372 	return (up->ptr != uh && up->ptr != NULL);
385 optimize_unr(struct unrhdr *uh)
397 	TAILQ_FOREACH(uf, &uh->head, list) {
401 		if (is_bitmap(uh, uf))
412 			if (is_bitmap(uh, up))
429 	if (!is_bitmap(uh, us)) {
431 		TAILQ_REMOVE(&uh->head, us, list);
433 		l = us->ptr == uh ? 1 : 0;
438 		if (!is_bitmap(uh, uf)) {
455 			delete_unr(uh, uf->ptr);
470 			TAILQ_REMOVE(&uh->head, uf, list);
471 			delete_unr(uh, uf);
472 		} else if (uf->ptr == uh) {
475 			TAILQ_REMOVE(&uh->head, uf, list);
476 			delete_unr(uh, uf);
485 			TAILQ_REMOVE(&uh->head, uf, list);
486 			delete_unr(uh, ubf);
487 			delete_unr(uh, uf);
498 collapse_unr(struct unrhdr *uh, struct unr *up)
504 	if (is_bitmap(uh, up)) {
507 			delete_unr(uh, up->ptr);
508 			up->ptr = uh;
510 			delete_unr(uh, up->ptr);
520 		TAILQ_REMOVE(&uh->head, up, list);
521 		delete_unr(uh, up);
530 			TAILQ_REMOVE(&uh->head, upp, list);
531 			delete_unr(uh, upp);
536 			TAILQ_REMOVE(&uh->head, upp, list);
537 			delete_unr(uh, upp);
542 	upp = TAILQ_FIRST(&uh->head);
543 	if (upp != NULL && upp->ptr == uh) {
544 		uh->first += upp->len;
545 		TAILQ_REMOVE(&uh->head, upp, list);
546 		delete_unr(uh, upp);
552 	upp = TAILQ_LAST(&uh->head, unrhd);
554 		uh->last += upp->len;
555 		TAILQ_REMOVE(&uh->head, upp, list);
556 		delete_unr(uh, upp);
562 	while (optimize_unr(uh))
570 alloc_unrl(struct unrhdr *uh)
577 	mtx_assert(uh->mtx, MA_OWNED);
578 	check_unrhdr(uh, __LINE__);
579 	x = uh->low + uh->first;
581 	up = TAILQ_FIRST(&uh->head);
586 	if (up == NULL && uh->last > 0) {
587 		uh->first++;
588 		uh->last--;
589 		uh->busy++;
600 	KASSERT(up->ptr != uh, ("UNR first element is allocated"));
603 		uh->first++;
612 	uh->busy++;
613 	collapse_unr(uh, up);
618 alloc_unr(struct unrhdr *uh)
622 	mtx_lock(uh->mtx);
623 	i = alloc_unrl(uh);
624 	clean_unrhdrl(uh);
625 	mtx_unlock(uh->mtx);
630 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
636 	mtx_assert(uh->mtx, MA_OWNED);
638 	if (item < uh->low + uh->first || item > uh->high)
641 	up = TAILQ_FIRST(&uh->head);
643 	if (up == NULL && item - uh->low == uh->first) {
644 		uh->first++;
645 		uh->last--;
646 		uh->busy++;
647 		check_unrhdr(uh, __LINE__);
651 	i = item - uh->low - uh->first;
654 		up = new_unr(uh, p1, p2);
657 		TAILQ_INSERT_TAIL(&uh->head, up, list);
658 		up = new_unr(uh, p1, p2);
659 		up->ptr = uh;
661 		TAILQ_INSERT_TAIL(&uh->head, up, list);
662 		uh->last = uh->high - uh->low - i;
663 		uh->busy++;
664 		check_unrhdr(uh, __LINE__);
668 		TAILQ_FOREACH(up, &uh->head, list) {
677 			up = new_unr(uh, p1, p2);
680 			TAILQ_INSERT_TAIL(&uh->head, up, list);
682 		up = new_unr(uh, p1, p2);
683 		up->ptr = uh;
685 		TAILQ_INSERT_TAIL(&uh->head, up, list);
689 	if (is_bitmap(uh, up)) {
696 	} else if (up->ptr == uh)
705 		upn = new_unr(uh, p1, p2);
708 		TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
713 		upn = new_unr(uh, p1, p2);
719 	up->ptr = uh;
722 	last = uh->high - uh->low - (item - uh->low);
723 	if (uh->last > last)
724 		uh->last = last;
725 	uh->busy++;
726 	collapse_unr(uh, up);
727 	check_unrhdr(uh, __LINE__);
732 alloc_unr_specific(struct unrhdr *uh, u_int item)
742 	mtx_lock(uh->mtx);
743 	i = alloc_unr_specificl(uh, item, &p1, &p2);
744 	mtx_unlock(uh->mtx);
760 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
766 	KASSERT(item >= uh->low && item <= uh->high,
768 	     item, uh->low, uh->high));
769 	check_unrhdr(uh, __LINE__);
770 	item -= uh->low;
771 	upp = TAILQ_FIRST(&uh->head);
775 	if (item + 1 == uh->first && upp == NULL) {
776 		uh->last++;
777 		uh->first--;
778 		uh->busy--;
779 		check_unrhdr(uh, __LINE__);
786 	if (item < uh->first) {
787 		up = new_unr(uh, p1, p2);
788 		up->ptr = uh;
789 		up->len = uh->first - item;
790 		TAILQ_INSERT_HEAD(&uh->head, up, list);
791 		uh->first -= up->len;
794 	item -= uh->first;
797 	TAILQ_FOREACH(up, &uh->head, list) {
804 	if (is_bitmap(uh, up)) {
810 		uh->busy--;
811 		collapse_unr(uh, up);
815 	KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
820 		uh->busy--;
821 		collapse_unr(uh, up);
830 		uh->busy--;
831 		collapse_unr(uh, up);
840 		uh->busy--;
841 		collapse_unr(uh, up);
848 		upp = new_unr(uh, p1, p2);
849 		upp->ptr = uh;
851 		TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
856 		upp = new_unr(uh, p1, p2);
858 		upp->ptr = uh;
863 	uh->busy--;
864 	collapse_unr(uh, up);
868 free_unr(struct unrhdr *uh, u_int item)
875 	mtx_lock(uh->mtx);
876 	free_unrl(uh, item, &p1, &p2);
877 	clean_unrhdrl(uh);
878 	mtx_unlock(uh->mtx);
896 print_unr(struct unrhdr *uh, struct unr *up)
904 	else if (up->ptr == uh)
920 print_unrhdr(struct unrhdr *uh)
927 	    uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
928 	x = uh->low + uh->first;
929 	TAILQ_FOREACH(up, &uh->head, list) {
931 		print_unr(uh, up);
932 		if (up->ptr == NULL || up->ptr == uh)
940 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
946 		free_unr(uh, i);
950 		j = alloc_unr(uh);
960 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
964 	j = alloc_unr_specific(uh, i);
968 		free_unr(uh, i);
984 	struct unrhdr *uh;
1017 	uh = new_unrhdr(0, count - 1, NULL);
1018 	print_unrhdr(uh);
1037 			test_alloc_unr(uh, i, a);
1039 			test_alloc_unr_specific(uh, i, a);
1042 			print_unrhdr(uh);
1043 		check_unrhdr(uh, __LINE__);
1049 				print_unrhdr(uh);
1051 			free_unr(uh, i);
1054 	print_unrhdr(uh);
1055 	delete_unrhdr(uh);