system/kernel/heap.cpp

103 	heap_page *	page_list; // sorted so that the desired page is always first
160 		B_PAGE_SIZE,				/* page size */
163 		8,							/* min count per page */
164 		16							/* max waste per page */
170 		B_PAGE_SIZE * 8,			/* page size */
173 		4,							/* min count per page */
174 		64							/* max waste per page */
180 		B_PAGE_SIZE * 16,			/* page size */
183 		1,							/* min count per page */
184 		256							/* max waste per page */
309 dump_page(heap_page *page)
312 	for (addr_t *temp = page->free_list; temp != NULL; temp = (addr_t *)*temp)
316 		"free_list %p (%" B_PRIu32 " entr%s)\n", page, page->bin_index,
317 		page->free_count, page->empty_index, page->free_list, count,
326 	for (heap_page *page = bin->page_list; page != NULL; page = page->next)
333 	for (heap_page *page = bin->page_list; page != NULL; page = page->next)
334 		dump_page(page);
462 				heap_page *page = &area->page_table[i];
463 				if (!page->in_use)
467 				if (page->bin_index < heap->bin_count) {
468 					// page is used by a small allocation bin
469 					uint32 elementCount = page->empty_index;
471 						= heap->bins[page->bin_index].element_size;
476 						for (addr_t *temp = page->free_list; temp != NULL;
496 					// page is used by a big allocation, find the page count
503 							== page->allocation_id)
570 				heap_page *page = &area->page_table[i];
571 				if (!page->in_use)
575 				if (page->bin_index < heap->bin_count) {
576 					// page is used by a small allocation bin
577 					uint32 elementCount = page->empty_index;
579 						= heap->bins[page->bin_index].element_size;
584 						for (addr_t *temp = page->free_list; temp != NULL;
615 					// page is used by a big allocation, find the page count
622 							== page->allocation_id)
707 			heap_page *page = &area->page_table[i];
708 			if (!page->in_use)
712 			if (page->bin_index < heap->bin_count) {
713 				// page is used by a small allocation bin
714 				uint32 elementCount = page->empty_index;
715 				size_t elementSize = heap->bins[page->bin_index].element_size;
719 					for (addr_t *temp = page->free_list; temp != NULL;
743 				// page is used by a big allocation, find the page count
750 						== page->allocation_id) {
863 		heap_page *page = area->free_pages;
864 		while (page) {
865 			if ((addr_t)page < (addr_t)&area->page_table[0]
866 				|| (addr_t)page >= (addr_t)&area->page_table[area->page_count])
867 				panic("free page is not part of the page table\n");
869 			if (page->index >= area->page_count)
870 				panic("free page has invalid index\n");
872 			if ((addr_t)&area->page_table[page->index] != (addr_t)page)
873 				panic("free page index does not lead to target page\n");
875 			if (page->prev != lastPage)
876 				panic("free page entry has invalid prev link\n");
878 			if (page->in_use)
879 				panic("free page marked as in use\n");
881 			lastPage = page;
882 			page = page->next;
889 			panic("free page count doesn't match free page list\n");
891 		// validate the page table
937 		heap_page *page = bin->page_list;
939 		while (page) {
942 				if (area == page->area)
948 				panic("page area not present in area list\n");
949 				page = page->next;
953 			if ((addr_t)page < (addr_t)&area->page_table[0]
954 				|| (addr_t)page >= (addr_t)&area->page_table[area->page_count])
955 				panic("used page is not part of the page table\n");
957 			if (page->index >= area->page_count)
958 				panic("used page has invalid index\n");
960 			if ((addr_t)&area->page_table[page->index] != (addr_t)page)
961 				panic("used page index does not lead to target page\n");
963 			if (page->prev != lastPage) {
964 				panic("used page entry has invalid prev link (%p vs %p bin "
965 					"%lu)\n", page->prev, lastPage, i);
968 			if (!page->in_use)
969 				panic("used page marked as not in use\n");
971 			if (page->bin_index != i) {
972 				panic("used page with bin index %u in page list of bin %lu\n",
973 					page->bin_index, i);
976 			if (page->free_count < lastFreeCount)
977 				panic("ordering of bin page list broken\n");
981 			addr_t *element = page->free_list;
982 			addr_t pageBase = area->base + page->index * heap->page_size;
986 					panic("free list entry out of page range\n");
996 			if (page->empty_index > slotCount) {
998 					page->empty_index, slotCount);
1001 			freeSlotsCount += (slotCount - page->empty_index);
1003 				panic("more free slots than fit into the page\n");
1005 			lastPage = page;
1006 			lastFreeCount = page->free_count;
1007 			page = page->next;
1037 	// the rest is now actually usable memory (rounded to the next page)
1041 	// now we know the real page count
1045 	// zero out the page table and fill in page indexes
1210 	mutex_init(&heap->page_lock, "heap page lock");
1306 heap_link_page(heap_page *page, heap_page **list)
1308 	page->prev = NULL;
1309 	page->next = *list;
1310 	if (page->next)
1311 		page->next->prev = page;
1312 	*list = page;
1317 heap_unlink_page(heap_page *page, heap_page **list)
1319 	if (page->prev)
1320 		page->prev->next = page->next;
1321 	if (page->next)
1322 		page->next->prev = page->prev;
1323 	if (list && *list == page) {
1324 		*list = page->next;
1325 		if (page->next)
1326 			page->next->prev = NULL;
1378 			heap_page *page = &area->page_table[i];
1379 			page->in_use = 1;
1380 			page->bin_index = heap->bin_count;
1382 			heap_unlink_page(page, &area->free_pages);
1384 			page->next = page->prev = NULL;
1385 			page->free_list = NULL;
1386 			page->allocation_id = (uint16)first;
1443 	heap_page *page = bin->page_list;
1444 	if (page == NULL) {
1455 		page = area->free_pages;
1456 		area->free_pages = page->next;
1457 		if (page->next)
1458 			page->next->prev = NULL;
1462 		if (page->in_use)
1463 			panic("got an in use page %p from the free pages list\n", page);
1464 		page->in_use = 1;
1468 		page->bin_index = binIndex;
1469 		page->free_count = bin->max_free_count;
1470 		page->empty_index = 0;
1471 		page->free_list = NULL;
1472 		page->next = page->prev = NULL;
1473 		bin->page_list = page;
1476 	// we have a page where we have a free slot
1478 	if (page->free_list) {
1480 		address = page->free_list;
1481 		page->free_list = (addr_t *)*page->free_list;
1483 		// the page hasn't been fully allocated so use the next empty_index
1484 		address = (void *)(page->area->base + page->index * heap->page_size
1485 			+ page->empty_index * bin->element_size);
1486 		page->empty_index++;
1489 	page->free_count--;
1490 	if (page->free_count == 0) {
1491 		// the page is now full so we remove it from the page_list
1492 		bin->page_list = page->next;
1493 		if (page->next)
1494 			page->next->prev = NULL;
1495 		page->next = page->prev = NULL;
1544 			// (page aligned) page has to be allocated anyway.
1625 	heap_page *page = &area->page_table[((addr_t)address - area->base)
1628 	TRACE(("free(): page %p: bin_index %d, free_count %d\n", page,
1629 		page->bin_index, page->free_count));
1631 	if (page->bin_index > heap->bin_count) {
1632 		panic("free(): page %p: invalid bin_index %d\n", page, page->bin_index);
1636 	if (page->bin_index < heap->bin_count) {
1638 		heap_bin *bin = &heap->bins[page->bin_index];
1643 			// on this page to make sure this address doesn't exist.
1645 			for (addr_t *temp = page->free_list; temp != NULL;
1648 					panic("free(): address %p already exists in page free "
1663 		if (((addr_t)address - area->base - page->index
1670 		// add the address to the page free list
1671 		*(addr_t *)address = (addr_t)page->free_list;
1672 		page->free_list = (addr_t *)address;
1673 		page->free_count++;
1675 		if (page->free_count == bin->max_free_count) {
1676 			// we are now empty, remove the page from the bin list
1678 			heap_unlink_page(page, &bin->page_list);
1679 			page->in_use = 0;
1680 			heap_link_page(page, &area->free_pages);
1682 		} else if (page->free_count == 1) {
1683 			// we need to add ourselfs to the page list of the bin
1684 			heap_link_page(page, &bin->page_list);
1687 			if (page->next && page->next->free_count < page->free_count) {
1689 				heap_page *insert = page->next;
1691 					&& insert->next->free_count < page->free_count)
1694 				heap_unlink_page(page, &bin->page_list);
1696 				page->prev = insert;
1697 				page->next = insert->next;
1698 				if (page->next)
1699 					page->next->prev = page;
1700 				insert->next = page;
1704 		// large allocation, just return the pages to the page free list
1705 		uint32 allocationID = page->allocation_id;
1706 		uint32 maxPages = area->page_count - page->index;
1712 			if (!page[i].in_use || page[i].bin_index != heap->bin_count
1713 				|| page[i].allocation_id != allocationID)
1716 			// this page still belongs to the same allocation
1717 			page[i].in_use = 0;
1718 			page[i].allocation_id = 0;
1721 			heap_link_page(&page[i], &area->free_pages);
1806 	heap_page *page = &area->page_table[((addr_t)address - area->base)
1808 	if (page->bin_index > heap->bin_count) {
1809 		panic("realloc(): page %p: invalid bin_index %d\n", page,
1810 			page->bin_index);
1817 	if (page->bin_index < heap->bin_count) {
1819 		heap_bin *bin = &heap->bins[page->bin_index];
1821 		if (page->bin_index > 0)
1822 			minSize = heap->bins[page->bin_index - 1].element_size + 1;
1825 		uint32 allocationID = page->allocation_id;
1826 		uint32 maxPages = area->page_count - page->index;
1831 			if (!page[i].in_use || page[i].bin_index != heap->bin_count
1832 				|| page[i].allocation_id != allocationID)
2113 		B_PAGE_SIZE,				/* page size */
2116 		8,							/* min count per page */
2117 		16							/* max waste per page */