segmentation fault

[Jon Hsu <jonhsu@xxxxxxxxxxxxx>]

I believe I've found a bug in the implementation of
RELATED_SEGMENTED_ARRAY. The following code snippets are taken from
cmplr_segmented_array.h. First, in Allocate(), a memory block of
new_size elements is allocated. new_size is equal to either block_size
or next_block_size. Next, in Update_Map, pairs are pushed onto the map
vector. The first entry in the pair is a pointer and the second is a
flag that indicates whether or not the pointer can be freed. Notice that
if the block is larger than block_size, it is broken up into multiple
pairs. Finally, in ~RELATED_SEGMENTED_ARRAY, every pointer in every pair
is freed if the flag indicates that it is ok.

Now, the problem comes when next_block_size is greater than block_size.
For example, if next_block_size=256 and block_size=128, then
new_size=256 and Update_Map() is called with a memory block of 256
elements. It creates two pairs from this block, one for each half of the
memory block, and sets the own_memory flag to TRUE for both pairs.
Finally, when the destructor is called, it tries to free both halves of
the block separately, which causes a segmentation fault.

Unfortunately, I cannot supply an example that demonstrates this
problem, although I believe a simple call to Reserve(2*block_size) would
do the trick. My suggestion is to change Update_Map() as indicated below
to only free the first entry when a block is larger than block_size.
However, you may have a better idea, or may know of other data
structures which might have similar problems.



template <class T, UINT block_size>
void
RELATED_SEGMENTED_ARRAY<T,block_size>::Allocate ()
{
    Is_True (size == max_size, ("Invalid internal state in segmented
array"));

    UINT new_size;

    if (next_block_size == 0)
        new_size = block_size;
    else {
        new_size = Round_up (next_block_size);
        next_block_size = 0;
    }

    block = (T *) MEM_POOL_Alloc (pool, new_size * sizeof(T));
    max_size += new_size;
    block_base = size;

    Update_Map (block, new_size, TRUE);
} // RELATED_SEGMENTED_ARRAY::Allocate

template <class T, UINT block_size>
inline void
RELATED_SEGMENTED_ARRAY<T,block_size>::Update_Map(T    *marker,
                                                  UINT  new_size,
                                                  BOOL  own_memory)
{
  do {
    map.push_back(std::pair<T*, BOOL>(marker, own_memory));
    new_size -= block_size;
    marker += block_size;
    own_memory = FALSE; // Only the first entry can be freed for a block
that
                        // is larger than block_size.
  } while (new_size);
} // RELATED_SEGMENTED_ARRAY<T,block_size>::Update_Map

  ~RELATED_SEGMENTED_ARRAY() {
    // Free memory from blocks. Map memory gets freed when the map
    // vector is destructed.
    for (std::vector<std::pair<T *, BOOL>, mempool_allocator<T *>
>::iterator
           entry = map.begin();
         entry != map.end();
         ++entry) {
      // entry->second <==> this map entry owns the block's memory.
      if (entry->second) {
        MEM_POOL_FREE(pool, entry->first);
      }
    }