Long-standing error in exception handling by pool_allocator (contains untested patch)

[Joachim Kuebart]

Hi all,

many HP/SGI-derived allocator classes return memory regions that overlap
previously allocated regions which have not been deallocated under low-memory
conditions. The following program shows the effect by providing a very
small heap:

      1 #include <exception>
      2 #include <iostream>
      3 #include <memory>
      4 #include <new>
      5 
      6 #define ALIGN 8
      7 #define NFREELISTS 16
      8 #define FREELIST_INIT 20
      9 #define CHUNK_EXCESS (40 - FREELIST_INIT)
     10 
     11 struct word {
     12     char c[ALIGN];
     13 };
     14 
     15 char heap[(FREELIST_INIT + CHUNK_EXCESS) * sizeof(word)];
     16 char *heap_pointer = heap;
     17 
     18 void *operator new(size_t n) throw(std::bad_alloc) {
     19     heap_pointer += n;
     20     if (heap_pointer - heap > sizeof(heap))
     21 	throw std::bad_alloc();
     22     return heap_pointer - n;
     23 }
     24 
     25 void operator delete(void *p) throw() {
     26 }
     27 
     28 int
     29 main()
     30 {
     31     std::allocator<word> alloc;
     32 
     33     for (int i = 0; i != FREELIST_INIT; i++)
     34 	alloc.allocate(1);
     35 
     36     alloc.allocate(NFREELISTS);
     37 
     38     try {
     39 	alloc.allocate(CHUNK_EXCESS - NFREELISTS + 1);
     40 	std::cout << "no exception, test terminated" << std::endl;
     41 	exit(1);
     42     } catch (std::bad_alloc) {
     43 	// a real application would release some temporary buffers...
     44     }
     45 
     46     word *p = alloc.allocate(CHUNK_EXCESS - NFREELISTS);
     47 
     48     try {
     49 	word *q = alloc.allocate(1);
     50 	std::cout << "allocator is inconsistent: p = " <<
     51 		p << ", q = " << q << std::endl;
     52     } catch (std::bad_alloc) {
     53 	std::cout << "allocator appears to work" << std::endl;
     54     }
     55 
     56     return 0;
     57 }

Here is an explanation of what is going on:

The four constants (lines 6-9) are the internal alignment of
__pool_alloc_base, the number of free_lists, the initial number of elements
on a fresh free_list and the excess elements allocated for a new chunk.
(NOTE: This is only true initially and grows with the total amount of
allocated memory).

struct word (line 11) is an example data type designed to agree with the
internal alignment of __pool_alloc_base. This is just to simplify
calculations, the symptom occurs with data types of all (small) sizes.

Our heap (line 15) is designed to provide enough room for the first request
by the allocator only. operator new() (line 18-23) returns memory from this
heap until it is exhausted. Then, it throws a std::bad_alloc exception.

Since our heap grows strictly upwards, operator delete() is not required to
do anything (line 25-26).

line 33-34: Allocator state: all free_lists empty, no chunk.

Upon our first request, the allocator will allocate a chunk of 40 words and
initialise the first free_list with FREELIST_INIT items. We fetch all items
from the free_list and a chunk of CHUNK_EXCESS words is left.

line 36: Allocator state: all free_lists empty, chunk of size CHUNK_EXCESS.

We request a large object of NFREELISTS words that gets taken from the chunk.
Thus, a chunk of only CHUNK_EXCESS - NFREELISTS (= 4) words is left to the
allocator.

line 38-44: Allocator state: all free_lists empty, chunk of size 4.

Here we request more than the words left in the allocator's chunk. The
allocator puts the rest of the chunk on the 4th free_list and attempts to
allocate a new chunk which throws an exception because our heap is too small.

The exception is not intercepted by the allocator and a broken allocator will
now get confused and think that the rest of the chunk just put on the 4th
free_list is still available.

line 46: Broken state: 1 item on 4th free_list, overlapping chunk of size 4.
     	 Good state:   1 item on 4th free_list, no chunk.

We request the 4 words on the free_list.

line 48-54: Broken state: free_lists empty, overlapping chunk of size 4.
     	    Good state:   free_lists empty, no chunk.

We request one more word. A good allocator will try to allocate more memory
and throw an exception. A bad allocator will return memory that overlaps with
our last request (in fact, the displayed pointer values are identical).

The reason this happens is historic: the allocator class used to call
malloc() the first time which doesn't throw an exception but returned NULL
and used a malloc_alloc allocator the second time. Thus, in the original
implementation, the allocator could not get inconsistent. But since the
call to malloc() has been replaced by a call to operator new() which throws
an exception instead of returning NULL, the problem exists.

The fix I suggest:

--- pool_allocator.cc.orig	2004-10-09 16:52:40.000000000 +0200
+++ pool_allocator.cc	2004-10-09 16:55:50.000000000 +0200
@@ -90,8 +90,11 @@
 	
 	size_t __bytes_to_get = (2 * __total_bytes
 				 + _M_round_up(_S_heap_size >> 4));
-	_S_start_free = static_cast<char*>(::operator new(__bytes_to_get));
-	if (_S_start_free == 0)
+	try
+	  {
+	    _S_start_free = static_cast<char*>(::operator new(__bytes_to_get));
+	  }
+	catch (...)
 	  {
 	    // Try to make do with what we have.  That can't hurt.  We
 	    // do not try smaller requests, since that tends to result
@@ -111,11 +114,9 @@
 		    // right free list.
 		  }
 	      }
-	    _S_end_free = 0;        // In case of exception.
-
-	    // This should either throw an exception or remedy the situation.
-	    // Thus we assume it succeeded.
-	    _S_start_free = static_cast<char*>(::operator new(__bytes_to_get));
+	    // what we have wasn't enough. Rethrow.
+	    _S_start_free = _S_end_free = 0;        // we have no chunk
+	    throw;
 	  }
 	_S_heap_size += __bytes_to_get;
 	_S_end_free = _S_start_free + __bytes_to_get;

Put the call to operator new() in a try block and put the code that used to
be run when malloc() returned NULL into the catch clause. Obviously, calling
operator new() a second time with the same size request is pointless, so it
is removed.

Any comments and ideas are most welcome! I have verified that this patch
removes the described problem. I have not regression tested the patch because
I do not have a current version of the library at hand. If requested I will
catch up on the regression tests as my time permits.

cu Jo

-- 
La perfection est atteinte non quand il ne reste rien à ajouter, mais quand
il ne reste rien à enlever.  (Antoine de Saint-Exupéry)