Race condition in heap coalesce.

    Previously the heap coalesce function looked at the "free" flag
    on the next block to determine if two blocks could be merged
    together.  The coalesce function is ran with all cores synchronized
    so no one should be modifying the heap, but there is still a
    subtle race condition.

    A user task could be in the process of freeing a block, marking it
    "free" but not actually inserting it onto the queues yet.  The
    coalesce will combine this block together but then when the user
    task resumes it continues to try to insert it onto the queue.
    This causes both the larger merged block and the smaller block to
    be on a free queue and memory corruption when both blocks are used.

    This is resolved by having a new flag indicating that the block
    is known to be part of the "coalesce" group and using this in
    addition to the "free" flag.  Only blocks which are actually present
    on the free queues are considered to be part of the "coalesce"
    group.

Change-Id: If33d15d731d32e07e01104244ebc65daf2295878
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/4520
Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com>
Reviewed-by: Daniel M. Crowell <dcrowell@us.ibm.com>
Tested-by: Jenkins Server
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

2 files changed, 36 insertions, 31 deletions

diff --git a/src/include/kernel/heapmgr.H b/src/include/kernel/heapmgr.H
index 56652ea66..cee0517f0 100644
--- a/src/include/kernel/heapmgr.H
+++ b/src/include/kernel/heapmgr.H
@@ -1,25 +1,25 @@
-//  IBM_PROLOG_BEGIN_TAG
-//  This is an automatically generated prolog.
-//
-//  $Source: src/include/kernel/heapmgr.H $
-//
-//  IBM CONFIDENTIAL
-//
-//  COPYRIGHT International Business Machines Corp. 2010 - 2011
-//
-//  p1
-//
-//  Object Code Only (OCO) source materials
-//  Licensed Internal Code Source Materials
-//  IBM HostBoot Licensed Internal Code
-//
-//  The source code for this program is not published or other-
-//  wise divested of its trade secrets, irrespective of what has
-//  been deposited with the U.S. Copyright Office.
-//
-//  Origin: 30
-//
-//  IBM_PROLOG_END
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/kernel/heapmgr.H $                                */
+/*                                                                        */
+/* IBM CONFIDENTIAL                                                       */
+/*                                                                        */
+/* COPYRIGHT International Business Machines Corp. 2010,2013              */
+/*                                                                        */
+/* p1                                                                     */
+/*                                                                        */
+/* Object Code Only (OCO) source materials                                */
+/* Licensed Internal Code Source Materials                                */
+/* IBM HostBoot Licensed Internal Code                                    */
+/*                                                                        */
+/* The source code for this program is not published or otherwise         */
+/* divested of its trade secrets, irrespective of what has been           */
+/* deposited with the U.S. Copyright Office.                              */
+/*                                                                        */
+/* Origin: 30                                                             */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
 #ifndef __KERNEL_HEAPMGR_H
 #define __KERNEL_HEAPMGR_H
 
@@ -40,7 +40,7 @@ void kernel_execute_decrementer();
  * The small heap increases one page at a time as allocations are needed.
  * A 4k pages is initially divided into buckes of size 3728,336, and 32.
  * Pages can't be recovered once assinged to the small heap.</p>
- * 
+ *
  * <p>Anthing larger than 3720 goes into the large allocation heap.
  * Memory in the large allocation heap are assigned as integral pages.
  * When memory is released from the large allocation heap, it is returned
@@ -134,10 +134,11 @@ class HeapManager
         {
             struct
             {
-                bool    free:1;         //!< Is chunck free
-                uint64_t bucket:63;     //!< Which bucket this chunk belongs to
+                bool    free:1;         //!< Is chunk free
+                bool    coalesce:1;     //!< Is chunk being coalesced
+                uint64_t bucket:62;     //!< Which bucket this chunk belongs to
             } PACKED;
-            
+
             chunk_t* next;      //!< Next chunk (for unallocated chunks only)
         };
 
@@ -150,7 +151,7 @@ class HeapManager
             size_t page_count;  //!< Number of pages used
             big_chunk_t * next; //!< Next allocation
 
-            big_chunk_t(void * i_ptr, size_t i_pages) 
+            big_chunk_t(void * i_ptr, size_t i_pages)
                 : addr(i_ptr), page_count(i_pages), next(NULL) {}
         };
 
diff --git a/src/kernel/heapmgr.C b/src/kernel/heapmgr.C
index 5518a96f8..d2df127e9 100644
--- a/src/kernel/heapmgr.C
+++ b/src/kernel/heapmgr.C
@@ -330,7 +330,10 @@ void HeapManager::_coalesce()
         chunk = NULL;
         while(NULL != (chunk = first_chunk[bucket].pop()))
         {
+            kassert(chunk->free);
+
             chunk->next = head;
+            chunk->coalesce = true;
             head = chunk;
         }
     }
@@ -351,7 +354,7 @@ void HeapManager::_coalesce()
             {
                 // This chunk might already be combined with a chunk earlier
                 // in the loop.
-                if(!chunk->free)
+                if((!chunk->coalesce) || (!chunk->free))
                 {
                     break;
                 }
@@ -370,7 +373,7 @@ void HeapManager::_coalesce()
                 }
 
                 // Cannot merge if buddy is not free.
-                if (!buddy->free)
+                if ((!buddy->free) || (!buddy->coalesce))
                 {
                     break;
                 }
@@ -387,7 +390,7 @@ void HeapManager::_coalesce()
                 }
 
                 // Do merge.
-                buddy->free = false;
+                buddy->free = buddy->coalesce = false;
                 chunk->bucket = newBucket;
                 incrementChunk = false;
                 mergedChunks = true;
@@ -407,7 +410,7 @@ void HeapManager::_coalesce()
         chunk = head;
         while (NULL != chunk)
         {
-            if (chunk->free)
+            if ((chunk->free) && (chunk->coalesce))
             {
                 chunk_t* temp = chunk->next;
                 chunk->next = newHead;
@@ -434,6 +437,7 @@ void HeapManager::_coalesce()
     {
         chunk_t * temp = chunk->next;
 
+        chunk->coalesce = false;
         push_bucket(chunk,chunk->bucket);
 
         ++cv_free_chunks;