Programming, Software and Code

Fixed-Size Allocator: Now With Extra Working!

03 Sep 2009
legacy  —  GC  —  Parrot
A few days ago I toggled the flag to disable the fixed-size allocator. I was receiving too many bug reports that I wasn't able to debug adequately, and I heard that it wasn't working at all on Win32. So we shut it down in hopes that we could find a fix eventually. Well, today I found and committed the fix.

NotFound mentioned out of the blue today that the fixed-size allocator was working on Linux, both 32- and 64-bit flavors. This was news to me, last I had heard it was malfunctioning on those platforms. However this news was quickly confirmed by darbelo too, and then I did it myself. Worked perfectly. So I crossed my fingers and tried on Win32 as well: Nothing. Segfault during miniparrot and the build stopped. I don't have GDB on my windows machine (it's actually my work computer, so it's use is limited). I do have Visual Studio, but I've yet to find a real way to debug a program in VS that I didn't build in VS, especially if it's a native-code executable. In lieu of real debugging tools, I used the "printf" method to try and narrow down where and when the segfault was happening. Here's the function that was causing problems, can you spot the error?

PARROT_CANNOT_RETURN_NULL
PMC_Attribute_Pool *
Parrot_gc_get_attribute_pool(PARROT_INTERP, size_t attrib_size)
{
   ASSERT_ARGS(Parrot_gc_get_attribute_pool)
   Arenas * const arenas = interp->arena_base;
   PMC_Attribute_Pool ** pools = arenas->attrib_pools;
   const size_t size = (attrib_size < sizeof (void *))?(sizeof (void *)):(attrib_size);
   const size_t idx  = size - sizeof (void *);

   if (pools == NULL) {
       const size_t total_length = idx + GC_ATTRIB_POOLS_HEADROOM;
       const size_t total_size   = (total_length + 1) * sizeof (void *);
       /* Allocate more then we strictly need, hoping that we can reduce the
          number of resizes. 8 is just an arbitrary number */
       pools = (PMC_Attribute_Pool **)mem_internal_allocate(total_size);
       memset(pools, 0, total_size);
       arenas->attrib_pools = pools;
       arenas->num_attribs = total_length;
   }
   if (arenas->num_attribs <= idx) {
       const size_t total_length = idx + GC_ATTRIB_POOLS_HEADROOM;
       const size_t total_size   = total_length * sizeof (void *);
       const size_t current_size = arenas->num_attribs;
       const size_t diff         = total_length - current_size;

       pools = (PMC_Attribute_Pool **)mem_internal_realloc(pools, total_size);
       memset(pools + current_size, 0, diff * sizeof (void *));
       arenas->attrib_pools = pools;
       arenas->num_attribs = total_length;
   }
   if (pools[idx] == NULL)
       pools[idx] = Parrot_gc_create_attrib_pool(interp, size);
   return pools[idx];
}

We keep an array of pool structures ("pools"), where each index into that array represents the size of the object managed by that pool. The smallest object we can allocate is a single pointer, because we link objects together into a linked list, so we need at least enough space for one pointer to handle that. We also want indexing for the smallest items (sizeof(void*)) to start at slot zero in the pools array to save space. To get this effect, we first calculate the minimum necessary size of the object, and then we subtract the sizeof(void*) from that to give us the index into the pools array. This part works just swell.

We then have two large logic blocks. The first determines whether we have allocated any pools at all, and if not first allocates space for the pools array. The second block determines if we have too few slots allocated, in which case the array is resized to accommodate our incoming request. We then check to see if the current slot is null, and allocate a new pool in that slot if it is. Finally we return the pool in the given slot.

The problem, I soon found out, was that for some specific sizes we were returning bad pointers. See the problem yet? Let's zoom in a little:

const size_t total_length = idx + GC_ATTRIB_POOLS_HEADROOM;
const size_t total_size   = total_length * sizeof (void *);
/* Allocate more then we strictly need, hoping that we can reduce the
  number of resizes. 8 is just an arbitrary number */
pools = (PMC_Attribute_Pool **)mem_internal_allocate(total_size);
memset(pools, 0, total_size);
arenas->num_attribs = total_length;

This is part of the logic for allocating a fresh pools array. GC_ATTRIB_POOLS_HEADROOM is a buffering factor I added. It's #define'd to be 8, which means that when we do allocate we make space for 8 sizes more then we currently need. This prevents us from needing to resize the array if we need to allocate an object that is only a little bit bigger (and we know that we will almost always need to allocate something that's just a little bigger).

Taking the index (idx) of the slot, we calculate the size of the array, allocate it, then initialize it all to zero. Except we don't. In the first run through if idx is 0 then total_length is 8 and total_size is 64. This means we're allocating enough space for 8 pointers, not one pointer plus a headroom of 8 additional pointers. Because the idx is zero-based, my math here was off by one. To see it better, consider if GC_ATTRIB_POOLS_HEADROOM was omitted entirely. Then idx would be 0, total_length would be 0, and total_size would be 0. Try passing that to malloc and see how well it works for you.

So I changed the calculation for total_size to:

const size_t total_size   = (total_length + 1) * sizeof (void *);

And Parrot magically started building on Win32. A few more small cleanups and I committed r40962.

I still need to do some benchmarking though, I'll try to do that tonight. I hope that this will bring some measurable performance improvements to Parrot.

This entry was originally posted on Blogger and was automatically converted. There may be some broken links and other errors due to the conversion. Please let me know about any serious problems.