apr_allocator Re: Event MPM: Spinning on cleanups?

[Brian Pane <br...@apache.org>]

On Dec 30, 2005, at 6:48 PM, Roy T. Fielding wrote:

> On Dec 30, 2005, at 5:51 PM, Brian Pane wrote:
>
>> I haven't been able to find the bug yet.  As a next step, I'll try  
>> using
>> valgrind on a build with pool debugging enabled.
>
> On entry to allocator_free, if
>
>    (node == node->next && node->index > current_free_index)
>
> is true, then the do { } while ((node = next) != NULL);
> will go into an infinite loop.  This is because
>
>         if (max_free_index != APR_ALLOCATOR_MAX_FREE_UNLIMITED
>             && index > current_free_index) {
>             node->next = freelist;
>             freelist = node;
>         }
>
> does not update current_free_index.  I don't know if that is the
> problem, but it may be the symptom.

After reading and instrumenting the apr_allocator code, I just found
that odd things happen when
   max_free_index  == APR_ALLOCATOR_MAX_FREE_UNLIMITED.

The doesn't appear to be the cause of the problem in the Event
MPM, but it's worth noting.

APR_ALLOCATOR_MAX_FREE_UNLIMITED is zero, and it's used
as the initial value for allocator->current_free_index.  The problem is
that when apr_allocator_free() stores a block in one of its free  
lists, it
subtracts that block's index (a value from 1 to 20) from
allocator->current_free_index.

Note that allocator->current_free_index is unsigned.  Thus, when
it starts out at 0, subsequent calls to apr_allocator_free() turn it  
into
a number slightly smaller than 2^32.  On the next call to
apr_allocator_alloc() that recycles a block from one of the free
lists, this bit of defensive code ends up returning the value of
allocator->current_free_index to zero:

             allocator->current_free_index += node->index;
             if (allocator->current_free_index > allocator- 
 >max_free_index)
                 allocator->current_free_index = allocator- 
 >max_free_index;

We probably should have a check in apr_allocator_free() to
make sure that we're not causing an unsigned int overflow in
allocator->current_free_index, e.g.,
+    if (index > current_tree_index) {
+         current_tree_index = 0;
+    }
+    else {
           current_free_index -= index;
+    }

In cases where max_free_index is not set to
APR_ALLOCATOR_MAX_FREE_UNLIMITED, all the
current_free_index logic appears to work in a sane
manner: the values of current_free_index and
max_free_index are basically base-2 logarithms
of the amount of space currently in the
allocator->free[] lists and of the max amount
of space that may be stored in these lists.

These variables really could use clearer names
and some descriptive comments, however.  They're
not really indices: even without the unsigned
int overflow problem, they can have values much
larger than MAX_INDEX.  Maybe it's just me, but
the naming made it very tough to figure out the
underlying powers-of-two trick.

I'll commit a patch when I have time, hopefully
in the next couple of days.

Brian