From 14a2721d2c87dc13f1ef66818c41cd0848dd52db Mon Sep 17 00:00:00 2001 From: Patrick Williams Date: Fri, 6 Jul 2012 15:40:43 -0500 Subject: Live-lock issues in memory allocator. * Debug tool for PageManager. * Support PageMgr allocations of non-2^k size. * Switch page-allocation to always be in kernel-mode. While investigating issue 44511, I noticed two problesm with the memory page allocator (PageManager). First, the allocator did not support allocations of pages which were not a power of 2, which would result in pages appearing to "leak". Second, in situations where a large allocation was requested and there was not a large chunk available, the allocation would enter a live-lock condition where coalescing would never occur. Switched the PageManager so that all allocations happen in kernel space. This allows us to force memory-release operations on the syscall path when we are out of memory and also put in place a task_yield call which will allow coalescing to eventually occur. Issue 44523 is suppose to fully resolve any of these live-lock paths. RTC: 44511 Change-Id: Ifefd5d0996ee6914e291c862fac0c7b76980717f Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/1330 Tested-by: Jenkins Server Reviewed-by: Daniel M. Crowell Reviewed-by: A. Patrick Williams III --- src/kernel/pagemgr.C | 179 ++++++++++++++++++++++++++------------------------- 1 file changed, 92 insertions(+), 87 deletions(-) (limited to 'src/kernel/pagemgr.C') diff --git a/src/kernel/pagemgr.C b/src/kernel/pagemgr.C index 3991ff920..60db55e12 100644 --- a/src/kernel/pagemgr.C +++ b/src/kernel/pagemgr.C @@ -29,10 +29,11 @@ #include #include #include -#include #include #include -#include +#include +#include +#include size_t PageManager::cv_coalesce_count = 0; size_t PageManager::cv_low_page_count = -1; @@ -47,14 +48,14 @@ void PageManagerCore::addMemory( size_t i_addr, size_t i_pageCount ) size_t page_length = BUCKETS-1; while(length > 0) { - while (length < (size_t)(1 << page_length)) + while (length < (size_t)(1 << page_length)) { - page_length--; + page_length--; } - iv_heap[page_length].push(page); - page = (page_t*)((uint64_t)page + (1 << page_length)*PAGESIZE); - length -= (1 << page_length); + iv_heap[page_length].push(page); + page = (page_t*)((uint64_t)page + (1 << page_length)*PAGESIZE); + length -= (1 << page_length); } __sync_add_and_fetch(&iv_available, i_pageCount); } @@ -63,8 +64,15 @@ void PageManagerCore::addMemory( size_t i_addr, size_t i_pageCount ) PageManagerCore::page_t * PageManagerCore::allocatePage( size_t i_pageCount ) { - size_t which_bucket = 0; - while (i_pageCount > (size_t)(1 << which_bucket)) which_bucket++; + size_t which_bucket = ((sizeof(size_t)*8 - 1) - + __builtin_clzl(i_pageCount)); + size_t bucket_size = ((size_t)1) << which_bucket; + + if (bucket_size != i_pageCount) + { + ++which_bucket; + bucket_size <<= 1; + } page_t* page = (page_t*)NULL; int retries = 0; @@ -77,7 +85,18 @@ PageManagerCore::page_t * PageManagerCore::allocatePage( size_t i_pageCount ) // Update statistics. if(page) { - __sync_sub_and_fetch(&iv_available, i_pageCount); + __sync_sub_and_fetch(&iv_available, bucket_size); + + // Buckets are 2^k in size so if i_pageCount is not 2^k we have some + // extra pages allocated. ie. the non-2^k portion of i_pageCount. + // Return that portion by freeing. + if (bucket_size != i_pageCount) + { + freePage(reinterpret_cast( + reinterpret_cast(page) + + (i_pageCount*PAGESIZE)), + bucket_size - i_pageCount); + } } return page; @@ -89,13 +108,24 @@ void PageManagerCore::freePage( void * i_page, size_t i_pageCount ) { if ((NULL == i_page) || (0 == i_pageCount)) return; - size_t which_bucket = 0; - while (i_pageCount > (size_t)(1 << which_bucket)) which_bucket++; + size_t which_bucket = ((sizeof(size_t)*8 - 1) - + __builtin_clzl(i_pageCount)); + size_t bucket_size = ((size_t)1) << which_bucket; push_bucket((page_t*)i_page, which_bucket); // Update statistics. - __sync_add_and_fetch(&iv_available, i_pageCount); + __sync_add_and_fetch(&iv_available, bucket_size); + + // Buckets are 2^k in size so if i_pageCount is not 2^k we have some + // spare pages to free. ie. the non-2^k portion of i_pageCount. + if (bucket_size != i_pageCount) + { + freePage(reinterpret_cast( + reinterpret_cast(i_page) + + (bucket_size*PAGESIZE)), + i_pageCount - bucket_size); + } return; } @@ -107,10 +137,34 @@ void PageManager::init() Singleton::instance(); } -void* PageManager::allocatePage(size_t n) +void* PageManager::allocatePage(size_t n, bool userspace) { - PageManager& pmgr = Singleton::instance(); - return pmgr._allocatePage(n); + void* page = NULL; + + // In non-kernel mode, make a system-call to allocate in kernel-mode. + if (!KernelMisc::in_kernel_mode()) + { + while (NULL == page) + { + page = _syscall1(Systemcalls::MM_ALLOC_PAGES, + reinterpret_cast(n)); + + // Didn't successfully allocate, so yield in hopes that memory + // will eventually free up (ex. VMM flushes). + if (NULL == page) + { + task_yield(); + } + } + } + else + { + // In kernel mode. Do a normal call to the PageManager. + PageManager& pmgr = Singleton::instance(); + page = pmgr._allocatePage(n, userspace); + } + + return page; } void PageManager::freePage(void* p, size_t n) @@ -140,8 +194,8 @@ PageManager::PageManager() // Display. printk("Initializing PageManager with %zd pages starting at %lx...", - length, - addr); + length, + addr); // Populate L3 cache lines. uint64_t* cache_line = reinterpret_cast(addr); @@ -172,62 +226,27 @@ PageManager::PageManager() printk("done\n"); } -void* PageManager::_allocatePage(size_t n) +void* PageManager::_allocatePage(size_t n, bool userspace) { - PageManagerCore::page_t* page = NULL; + PageManagerCore::page_t* page = iv_heap.allocatePage(n); - // Initiate a page cast out if low - if(_queryAvail() < 16 && queryKernelMode() == false) + // If the allocation came from kernel-space and normal allocation + // was unsuccessful, pull a page off the reserve heap. + if ((NULL == page) && (!userspace)) { - // Kernel mode might have Vmm mutex lock which would cause deadlock - // were VmmManager functions called to flush and cast out. - - // Only want one thread testing and flushing - if(__sync_bool_compare_and_swap(&(iv_lock),0,1)) - { - if(_queryAvail() < 5) - { - mm_flush_pages(VmmManager::CRITICAL); - } - else - { - mm_flush_pages(VmmManager::NORMAL); - } - iv_lock = 0; - } + printkd("PAGEMANAGER: kernel heap used\n"); + page = iv_heapKernel.allocatePage(n); } - while(page == NULL) - { - page = iv_heap.allocatePage(n); - - if(NULL == page) - { - if(queryKernelMode() == true) - { - printkd("PAGEMANAGER: kernel heap used\n"); - page = iv_heapKernel.allocatePage(n); - break; - } - else - { - //task yield and hope there is more memory available - //when execution continues - printkd("PAGEMANAGER: Task held off\n"); - task_yield(); - - //Possible Loop forever? or is there a break condition?? - } - } - } - - if (NULL == page) + // If still not successful, we're out of memory. Assert. + if ((NULL == page) && (!userspace)) { register task_t* t; asm volatile("mr %0, 13" : "=r"(t)); - printk("Insufficient memory for alloc of size %zd page on tid=%d!\n", n, t->tid); + printk("Insufficient memory for alloc %zd pages on tid=%d!\n", + n, t->tid); printk("Pages available=%ld\n",iv_pagesAvail); - while(1); + kassert(false); } // Update statistics. @@ -257,7 +276,6 @@ void PageManager::_freePage(void* p, size_t n) if(page) { iv_heapKernel.addMemory(reinterpret_cast(page), ks); - __sync_sub_and_fetch(&iv_pagesAvail, ks); } } @@ -273,14 +291,14 @@ PageManagerCore::page_t* PageManagerCore::pop_bucket(size_t i_n) if (NULL == p) { - // Couldn't allocate from the correct size bucket, so split up an - // item from the next sized bucket. - p = pop_bucket(i_n+1); - if (NULL != p) - { - push_bucket((page_t*) (((uint64_t)p) + (PAGESIZE * (1 << i_n))), - i_n); - } + // Couldn't allocate from the correct size bucket, so split up an + // item from the next sized bucket. + p = pop_bucket(i_n+1); + if (NULL != p) + { + push_bucket((page_t*) (((uint64_t)p) + (PAGESIZE * (1 << i_n))), + i_n); + } } return p; } @@ -304,9 +322,6 @@ void PageManager::_coalesce( void ) // Coalsesce adjacent free memory blocks void PageManagerCore::coalesce( void ) { - // TODO: Issue 44511 - Function appears to leak memory. - return; - // Look at all the "free buckets" and find blocks to merge // Since this is binary, all merges will be from the same free bucket // Each bucket is a stack of non-allocated memory blocks of the same size @@ -371,13 +386,3 @@ void PageManagerCore::coalesce( void ) printkd("PAGEMGR low page count %ld\n", PageManager::cv_low_page_count); } -bool PageManager::queryKernelMode() const -{ - uint64_t stack = 0; - asm volatile("mr %0, 1" : "=r"(stack)); - if(stack >= VMM_VADDR_STACK_SEGMENT && stack < VMM_VADDR_DEVICE_SEGMENT_FIRST) - { - return false; - } - return true; -} -- cgit v1.2.1