Bug 56654 - apr_skiplist sometimes corrupts
Summary: apr_skiplist sometimes corrupts
Status: NEW
Alias: None
Product: APR
Classification: Unclassified
Component: APR (show other bugs)
Version: HEAD
Hardware: All All
: P2 critical (vote)
Target Milestone: ---
Assignee: Apache Portable Runtime bugs mailinglist
URL:
Keywords:
Depends on:
Blocks: 56645
  Show dependency tree
 
Reported: 2014-06-21 06:14 UTC by Takashi Sato
Modified: 2014-06-23 05:37 UTC (History)
0 users



Attachments
Enable skiplist_print_struct for debug (1.16 KB, patch)
2014-06-21 06:17 UTC, Takashi Sato
Details | Diff
code to reproduce (906 bytes, text/plain)
2014-06-21 06:22 UTC, Takashi Sato
Details
output from the code (31738) (1.09 KB, text/plain)
2014-06-21 06:23 UTC, Takashi Sato
Details
patch for fix (499 bytes, patch)
2014-06-21 06:35 UTC, Takashi Sato
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Takashi Sato 2014-06-21 06:14:53 UTC
apr_skiplist sometimes corrupts.

apr_skiplist_insert uses apr_skiplist_alloc to allocate memory for apr_skiplistnode_t, but apr_skiplist_alloc sometimes returns uninitialized (un-memset-zeroed) one.
apr_skiplist have a memory recycle system, so apr_skiplist_alloc first tries to get memory from it, but apr_skiplist_alloc doesn't clear memory.
apr_skiplist_insert presume apr_skiplist_alloc returns zero cleared memory.

How to reproduce:

1. insert objects to skiplist many times (about 10?)
2. remove all objects from the skiplist
3. insert objects to skiplist many times again

then skiplist_print_struct shows like this:
Skiplist Structure (height: 3)
_(nil) 0xb3805e78 0xb3805f18 
_0xb3806080 
_0xb3806088 0xb3806088 
_0xb38060c0 

First line should contains NULL only, but it doesn't.
Comment 1 Takashi Sato 2014-06-21 06:17:14 UTC
Created attachment 31737 [details]
Enable skiplist_print_struct for debug

apr_skiplist.c has skiplist_print_struct but disabled.
This patch enables it.
Comment 2 Takashi Sato 2014-06-21 06:22:28 UTC
Created attachment 31738 [details]
code to reproduce

This code needs earlier patch (31737)
Comment 3 Takashi Sato 2014-06-21 06:23:43 UTC
Created attachment 31739 [details]
output from the code (31738)
Comment 4 Takashi Sato 2014-06-21 06:35:36 UTC
Created attachment 31740 [details]
patch for fix

fix for apr_skiplist_alloc
Comment 5 Eric Covener 2014-06-21 11:54:05 UTC
Just out of context in the diff it's clear we pcalloc/calloc new memory so +1.

I did just now look at the original (non-apr) skiplist, which always does malloc inline and either does memset or memcpy right after. We don't seem to have that memcpy equivalent path (I can't tell why) so it seems like we're never doing a throwaway memset+memcpy.  

Will commit shortly
Comment 6 Eric Covener 2014-06-21 11:58:17 UTC
(In reply to Eric Covener from comment #5)
> Just out of context in the diff it's clear we pcalloc/calloc new memory so
> +1.
> 
> I did just now look at the original (non-apr) skiplist, which always does
> malloc inline and either does memset or memcpy right after. We don't seem to
> have that memcpy equivalent path (I can't tell why) so it seems like we're
> never doing a throwaway memset+memcpy.  
> 
> Will commit shortly

Did you try your testcase w/ this #if 0 un-ifdeffed out?

static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
                                        apr_skiplist_compare comp, int replace)
{
    apr_skiplistnode *m, *p, *tmp, *ret = NULL, **stack;
    int nh = 1, ch, stacki;
    if (!sl->top) {
        sl->height = 1;
        sl->topend = sl->bottomend = sl->top = sl->bottom =
            (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
#if 0
        sl->top->next = (apr_skiplistnode *)NULL;
        sl->top->data = (apr_skiplistnode *)NULL;
        sl->top->prev = (apr_skiplistnode *)NULL;
        sl->top->up = (apr_skiplistnode *)NULL;
        sl->top->down = (apr_skiplistnode *)NULL;
        sl->top->nextindex = (apr_skiplistnode *)NULL;
        sl->top->previndex = (apr_skiplistnode *)NULL;
#endif
        sl->top->sl = sl;
    }

I wonder if there is even any point in skipping a memset call though.
Comment 7 Takashi Sato 2014-06-21 14:34:33 UTC
(In reply to Eric Covener from comment #6)
[cut]
> 
> Did you try your testcase w/ this #if 0 un-ifdeffed out?
> 
> static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
>                                         apr_skiplist_compare comp, int
> replace)
> {
>     apr_skiplistnode *m, *p, *tmp, *ret = NULL, **stack;
>     int nh = 1, ch, stacki;
>     if (!sl->top) {
>         sl->height = 1;
>         sl->topend = sl->bottomend = sl->top = sl->bottom =
>             (apr_skiplistnode *)apr_skiplist_alloc(sl,
> sizeof(apr_skiplistnode));
> #if 0
>         sl->top->next = (apr_skiplistnode *)NULL;
>         sl->top->data = (apr_skiplistnode *)NULL;
>         sl->top->prev = (apr_skiplistnode *)NULL;
>         sl->top->up = (apr_skiplistnode *)NULL;
>         sl->top->down = (apr_skiplistnode *)NULL;
>         sl->top->nextindex = (apr_skiplistnode *)NULL;
>         sl->top->previndex = (apr_skiplistnode *)NULL;
> #endif
>         sl->top->sl = sl;
>     }
> 
> I wonder if there is even any point in skipping a memset call though.

I just tried this, but doesn't remove the issue.
Then, I found another #if 0 block.
 
    for (; sl->height < nh; sl->height++) {
        sl->top->up =
            (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
        sl->top->up->down = sl->top;
        sl->top = sl->topend = sl->top->up;
#if 0
        sl->top->prev = sl->top->next = sl->top->nextindex =
            sl->top->previndex = sl->top->up = NULL;
        sl->top->data = NULL;
#endif
        sl->top->sl = sl;
    }

I removed this and ran my testcode, and seemed like things went well.
Comment 8 Eric Covener 2014-06-22 15:13:10 UTC
It turns out a very minor change to your testcase crashes w/o the patch, I got
lucky in adding just a few extra calls.

Committed APR test based on your sample program and the #if 0 fix (1604598) to
trunk.  Will backport later today.  Please check out trunk for feedback before
I backport
Comment 9 Takashi Sato 2014-06-23 05:37:28 UTC
(In reply to Eric Covener from comment #8)
[cut]
> Committed APR test based on your sample program and the #if 0 fix (1604598)
> to
> trunk.  Will backport later today.  Please check out trunk for feedback
> before
> I backport

I tried. I verified the issue was resolved.
The httpd event MPM + wstunnel Async with idle timeout works well too.