system/kernel/heap.cpp

64 	area_id			area;
84 	heap_area *		area;
124 	heap_area *	areas; // sorted so that the desired area is always first
131 	area_id		area;
350 	heap_area *area = heap->all_areas;
351 	while (area) {
352 		kprintf("\tarea %p: area: %" B_PRId32 "; base: %p; size: %zu; page_count: "
353 			"%" B_PRIu32 "; free_pages: %p (%" B_PRIu32 " entr%s)\n", area,
354 			area->area, (void *)area->base, area->size, area->page_count,
355 			area->free_pages, area->free_page_count,
356 			area->free_page_count == 1 ? "y" : "ies");
357 		area = area->all_next;
459 		heap_area *area = heap->all_areas;
460 		while (area) {
461 			for (uint32 i = 0; i < area->page_count; i++) {
462 				heap_page *page = &area->page_table[i];
466 				addr_t base = area->base + i * heap->page_size;
498 					while (i + pageCount < area->page_count
499 						&& area->page_table[i + pageCount].in_use
500 						&& area->page_table[i + pageCount].bin_index
502 						&& area->page_table[i + pageCount].allocation_id
521 			area = area->all_next;
566 		heap_area *area = heap->all_areas;
567 		while (area) {
569 			for (uint32 i = 0; i < area->page_count; i++) {
570 				heap_page *page = &area->page_table[i];
574 				addr_t base = area->base + i * heap->page_size;
617 					while (i + pageCount < area->page_count
618 						&& area->page_table[i + pageCount].in_use
619 						&& area->page_table[i + pageCount].bin_index
621 						&& area->page_table[i + pageCount].allocation_id
649 			area = area->all_next;
703 	heap_area *area = heap->all_areas;
704 	while (area) {
706 		for (uint32 i = 0; i < area->page_count; i++) {
707 			heap_page *page = &area->page_table[i];
711 			addr_t base = area->base + i * heap->page_size;
745 				while (i + pageCount < area->page_count
746 					&& area->page_table[i + pageCount].in_use
747 					&& area->page_table[i + pageCount].bin_index
749 					&& area->page_table[i + pageCount].allocation_id
771 		area = area->all_next;
858 	heap_area *area = heap->all_areas;
859 	while (area != NULL) {
863 		heap_page *page = area->free_pages;
865 			if ((addr_t)page < (addr_t)&area->page_table[0]
866 				|| (addr_t)page >= (addr_t)&area->page_table[area->page_count])
869 			if (page->index >= area->page_count)
872 			if ((addr_t)&area->page_table[page->index] != (addr_t)page)
888 		if (area->free_page_count != freePageCount)
893 		for (uint32 i = 0; i < area->page_count; i++) {
894 			if (area->page_table[i].in_use)
899 		if (freePageCount + usedPageCount != area->page_count) {
901 				freePageCount, usedPageCount, area->page_count);
904 		area = area->all_next;
908 	area = heap->areas;
911 	while (area != NULL) {
912 		if (area->free_page_count < lastFreeCount)
913 			panic("size ordering of area list broken\n");
915 		if (area->prev != lastArea)
916 			panic("area list entry has invalid prev link\n");
918 		lastArea = area;
919 		lastFreeCount = area->free_page_count;
920 		area = area->next;
924 	area = heap->all_areas;
925 	while (area != NULL) {
926 		if (lastArea != NULL && lastArea->base < area->base)
929 		lastArea = area;
930 		area = area->all_next;
940 			area = heap->all_areas;
941 			while (area) {
942 				if (area == page->area)
944 				area = area->all_next;
947 			if (area == NULL) {
948 				panic("page area not present in area list\n");
953 			if ((addr_t)page < (addr_t)&area->page_table[0]
954 				|| (addr_t)page >= (addr_t)&area->page_table[area->page_count])
957 			if (page->index >= area->page_count)
960 			if ((addr_t)&area->page_table[page->index] != (addr_t)page)
982 			addr_t pageBase = area->base + page->index * heap->page_size;
1025 	heap_area *area = (heap_area *)base;
1026 	area->area = areaID;
1033 	area->page_table = (heap_page *)base;
1038 	area->base = ROUNDUP(base, B_PAGE_SIZE);
1039 	area->size = size & ~(B_PAGE_SIZE - 1);
1042 	pageCount = area->size / heap->page_size;
1043 	area->page_count = pageCount;
1046 	memset((void *)area->page_table, 0, pageTableSize);
1048 		area->page_table[i].area = area;
1049 		area->page_table[i].index = i;
1054 		area->page_table[i - 1].next = &area->page_table[i];
1055 		area->page_table[i].prev = &area->page_table[i - 1];
1057 	area->free_pages = &area->page_table[0];
1058 	area->free_page_count = pageCount;
1059 	area->page_table[0].prev = NULL;
1060 	area->next = NULL;
1065 		// it's the only (empty) area in that heap
1066 		area->prev = NULL;
1067 		heap->areas = area;
1069 		// link in this area as the last one as it is completely empty
1074 		lastArea->next = area;
1075 		area->prev = lastArea;
1078 	// insert this area in the all_areas list so it stays ordered by base
1079 	if (heap->all_areas == NULL || heap->all_areas->base < area->base) {
1080 		area->all_next = heap->all_areas;
1081 		heap->all_areas = area;
1084 		while (insert->all_next && insert->all_next->base > area->base)
1087 		area->all_next = insert->all_next;
1088 		insert->all_next = area;
1091 	heap->total_pages += area->page_count;
1092 	heap->total_free_pages += area->free_page_count;
1095 		// this later on deletable area is yet empty - the empty count will be
1096 		// decremented as soon as this area is used for the first time
1103 	dprintf("heap_add_area: area %" B_PRId32 " added to %s heap %p - usable "
1104 		"range %p - %p\n", area->area, heap->name, heap, (void *)area->base,
1105 		(void *)(area->base + area->size));
1110 heap_remove_area(heap_allocator *heap, heap_area *area)
1112 	if (area->free_page_count != area->page_count) {
1113 		panic("tried removing heap area that has still pages in use");
1117 	if (area->prev == NULL && area->next == NULL) {
1118 		panic("tried removing the last non-full heap area");
1122 	if (heap->areas == area)
1123 		heap->areas = area->next;
1124 	if (area->prev != NULL)
1125 		area->prev->next = area->next;
1126 	if (area->next != NULL)
1127 		area->next->prev = area->prev;
1129 	if (heap->all_areas == area)
1130 		heap->all_areas = area->all_next;
1134 			if (previous->all_next == area) {
1135 				previous->all_next = area->all_next;
1143 			panic("removing heap area that is not in all list");
1146 	heap->total_pages -= area->page_count;
1147 	heap->total_free_pages -= area->free_page_count;
1149 	dprintf("heap_remove_area: area %" B_PRId32 " with range %p - %p removed "
1150 		"from %s heap %p\n", area->area, (void *)area->base,
1151 		(void *)(area->base + area->size), heap->name, heap);
1167 		// use up the first part of the area
1209 	rw_lock_init(&heap->area_lock, "heap area rw lock");
1218 heap_free_pages_added(heap_allocator *heap, heap_area *area, uint32 pageCount)
1220 	area->free_page_count += pageCount;
1223 	if (area->free_page_count == pageCount) {
1224 		// we need to add ourselfs to the area list of the heap
1225 		area->prev = NULL;
1226 		area->next = heap->areas;
1227 		if (area->next)
1228 			area->next->prev = area;
1229 		heap->areas = area;
1231 		// we might need to move back in the area list
1232 		if (area->next && area->next->free_page_count < area->free_page_count) {
1234 			heap_area *insert = area->next;
1236 				&& insert->next->free_page_count < area->free_page_count)
1239 			if (area->prev)
1240 				area->prev->next = area->next;
1241 			if (area->next)
1242 				area->next->prev = area->prev;
1243 			if (heap->areas == area)
1244 				heap->areas = area->next;
1246 			area->prev = insert;
1247 			area->next = insert->next;
1248 			if (area->next)
1249 				area->next->prev = area;
1250 			insert->next = area;
1254 	if (area->free_page_count == area->page_count && area->area >= 0)
1260 heap_free_pages_removed(heap_allocator *heap, heap_area *area, uint32 pageCount)
1262 	if (area->free_page_count == area->page_count && area->area >= 0) {
1263 		// this area was completely empty
1267 	area->free_page_count -= pageCount;
1270 	if (area->free_page_count == 0) {
1271 		// the area is now full so we remove it from the area list
1272 		if (area->prev)
1273 			area->prev->next = area->next;
1274 		if (area->next)
1275 			area->next->prev = area->prev;
1276 		if (heap->areas == area)
1277 			heap->areas = area->next;
1278 		area->next = area->prev = NULL;
1280 		// we might need to move forward in the area list
1281 		if (area->prev && area->prev->free_page_count > area->free_page_count) {
1283 			heap_area *insert = area->prev;
1285 				&& insert->prev->free_page_count > area->free_page_count)
1288 			if (area->prev)
1289 				area->prev->next = area->next;
1290 			if (area->next)
1291 				area->next->prev = area->prev;
1293 			area->prev = insert->prev;
1294 			area->next = insert;
1295 			if (area->prev)
1296 				area->prev->next = area;
1298 				heap->areas = area;
1299 			insert->prev = area;
1336 	heap_area *area = heap->areas;
1337 	while (area) {
1338 		if (area->free_page_count < pageCount) {
1339 			area = area->next;
1345 		const uint32 lastValid = area->page_count - pageCount + 1;
1348 			firstValid = (ROUNDUP(area->base, alignment) - area->base)
1355 			if (area->page_table[i].in_use)
1361 				if (area->page_table[i + j].in_use) {
1373 			area = area->next;
1378 			heap_page *page = &area->page_table[i];
1382 			heap_unlink_page(page, &area->free_pages);
1389 		heap_free_pages_removed(heap, area, pageCount);
1390 		return &area->page_table[first];
1427 	addr_t address = firstPage->area->base + firstPage->index * heap->page_size;
1446 		heap_area *area = heap->areas;
1447 		if (area == NULL) {
1455 		page = area->free_pages;
1456 		area->free_pages = page->next;
1460 		heap_free_pages_removed(heap, area, 1);
1484 		address = (void *)(page->area->base + page->index * heap->page_size
1599 	heap_area *area = heap->all_areas;
1600 	while (area) {
1602 		// base at the top, we need only find the first area with a base
1604 		if (area->base <= (addr_t)address) {
1605 			if ((addr_t)address >= area->base + area->size) {
1611 			// this area contains the allocation, we're done searching
1615 		area = area->all_next;
1618 	if (area == NULL) {
1625 	heap_page *page = &area->page_table[((addr_t)address - area->base)
1663 		if (((addr_t)address - area->base - page->index
1680 			heap_link_page(page, &area->free_pages);
1681 			heap_free_pages_added(heap, area, 1);
1706 		uint32 maxPages = area->page_count - page->index;
1721 			heap_link_page(&page[i], &area->free_pages);
1725 		heap_free_pages_added(heap, area, pageCount);
1738 		area = heap->areas;
1739 		while (area != NULL && heap->empty_areas > 1) {
1740 			heap_area *next = area->next;
1741 			if (area->area >= 0
1742 				&& area->free_page_count == area->page_count
1743 				&& heap_remove_area(heap, area) == B_OK) {
1744 				areasToDelete[areasToDeleteIndex++] = area->area;
1748 			area = next;
1779 	heap_area *area = heap->all_areas;
1780 	while (area) {
1782 		// base at the top, we need only find the first area with a base
1785 		if (area->base <= (addr_t)address) {
1786 			if ((addr_t)address >= area->base + area->size) {
1792 			// this area contains the allocation, we're done searching
1796 		area = area->all_next;
1799 	if (area == NULL) {
1806 	heap_page *page = &area->page_table[((addr_t)address - area->base)
1826 		uint32 maxPages = area->page_count - page->index;
1948 		TRACE(("heap: couldn't allocate heap area \"%s\"\n", name));
1974 				dprintf("heap_grower: failed to create new grow heap area\n");
1987 					dprintf("heap_grower: failed to create new heap area\n");
2097 			"area");
2124 		panic("heap_init_post_area(): couldn't allocate VIP heap area");
2249 		area_id allocationArea = create_area("memalign area", &address,
2253 			dprintf("heap: failed to create area for huge allocation\n");
2259 		info->area = allocationArea;
2272 		TRACE(("heap: allocated area %ld for huge allocation of %lu bytes\n",
2383 	// or maybe it was a huge allocation using an area
2385 	area_id area = area_for(address);
2386 	if (area >= B_OK && get_area_info(area, &areaInfo) == B_OK) {
2390 		if (info->magic == kAreaAllocationMagic && info->area == area
2393 			delete_area(area);
2394 			TRACE(("free(): freed huge allocation by deleting area %ld\n",
2395 				area));
2436 	// or maybe it was a huge allocation using an area
2438 	area_id area = area_for(address);
2439 	if (area >= B_OK && get_area_info(area, &areaInfo) == B_OK) {
2443 		if (info->magic == kAreaAllocationMagic && info->area == area
2451 				TRACE(("realloc(): new size %ld fits in old area %ld with %ld "
2452 					"available\n", newSize, area, available));
2457 			// have to allocate/copy/free - TODO maybe resize the area instead?
2466 			delete_area(area);
2468 				"old area %ld\n", newAddress, newSize, area));