httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Yann Ylavic <ylavic....@gmail.com>
Subject Re: svn commit: r1666619 - /httpd/httpd/trunk/server/mpm/motorz/motorz.c
Date Fri, 10 Apr 2015 20:24:40 GMT
Probably, but when we want to remove a timer associated to a
connection (on cleanup), we can't simply remove any duplicate instead
(that's a lifetime issue, we can't leave an about to be freed timer in
the skiplist).

Since, with APR's skiplists, it is the responsability of the compare
function to tell how to order elements, what is a duplicate, and
eventually what is an exact element one is looking for (and motorz
needs this, unlike event), I guess we have to hack all that there...

On Fri, Apr 10, 2015 at 3:26 PM, Jim Jagielski <jim@jagunet.com> wrote:
> Isn't the whole idea of skiplists that one does not need
> such hacks for the impl to do "the right thing"?
>
>> On Apr 9, 2015, at 7:11 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
>>
>> I think I'm done with twisting myself into knots for skiplist's
>> compare function :p
>>
>> One reliable/efficient way to remove a given timer from the skiplist
>> (while obviously still inserting by expiration time, in order) is to
>> add a unique identifier in the struct timer itself.
>> Each time a timer is inserted, let's give it a sequential number, and
>> use the following compare function:
>>
>> static int timer_comp(void *a, void *b)
>> {
>>    const motorz_timer_t * const t1 = a;
>>    const motorz_timer_t * const t2 = b;
>>    if (t1->expires < t2->expires) {
>>        return -1;
>>    }
>>    else if (t1->expires > t2->expires) {
>>        return +1;
>>    }
>>    else if (t1->num < t2->num) {
>>        return -1;
>>    }
>>    else if (t1->num > t2->num) {
>>        return +1;
>>    }
>>    else {
>>        return 0;
>>    }
>> }
>>
>> By using a 64bit num, we can create 1M timers/sec during more than
>> 500K years, which I guess should be enough :)
>>
>> So, how about the attached patch?
>>
>>
>> On Tue, Apr 7, 2015 at 11:48 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
>>> Maybe a reliable way to remove events would be to use the new
>>> functions from r1671957 (something like the example added to
>>> testskiplist.c in this commit)?
>>> This can't be backported to APR-1.5.x though, so if that's suitable we
>>> would have to copy the skiplist's code (back) to httpd (as discussed
>>> elsewhere)...
>>>
>>> On Mon, Mar 23, 2015 at 11:09 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
>>>> On Sat, Mar 14, 2015 at 1:09 AM,  <ylavic@apache.org> wrote:
>>>>> Author: ylavic
>>>>> Date: Sat Mar 14 00:09:32 2015
>>>>> New Revision: 1666619
>>>>>
>>>>> URL: http://svn.apache.org/r1666619
>>>>> Log:
>>>>> mpm_motorz: follow up to r1666482.
>>>>> We only need one compare function for add semantic with apr_skiplist_insert()
>>>>> and unique timers (pointers). It also works with apr_skiplist_remove()
and
>>>>> apr_skiplist_find().
>>>>>
>>>>> Modified:
>>>>>    httpd/httpd/trunk/server/mpm/motorz/motorz.c
>>>>>
>>>>> Modified: httpd/httpd/trunk/server/mpm/motorz/motorz.c
>>>>> URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/motorz/motorz.c?rev=1666619&r1=1666618&r2=1666619&view=diff
>>>>> ==============================================================================
>>>>> --- httpd/httpd/trunk/server/mpm/motorz/motorz.c (original)
>>>>> +++ httpd/httpd/trunk/server/mpm/motorz/motorz.c Sat Mar 14 00:09:32
2015
>>>>> @@ -64,21 +64,18 @@ static motorz_core_t *motorz_core_get()
>>>>>     return g_motorz_core;
>>>>> }
>>>>>
>>>>> -static int indexing_comp(void *a, void *b)
>>>>> +static int timer_comp(void *a, void *b)
>>>>> {
>>>>> -    apr_time_t t1 = (apr_time_t) (((motorz_timer_t *) a)->expires);
>>>>> -    apr_time_t t2 = (apr_time_t) (((motorz_timer_t *) b)->expires);
>>>>> -    AP_DEBUG_ASSERT(t1);
>>>>> -    AP_DEBUG_ASSERT(t2);
>>>>> -    return ((t1 < t2) ? -1 : 1);
>>>>> -}
>>>>> -
>>>>> -static int indexing_compk(void *ac, void *b)
>>>>> -{
>>>>> -    apr_time_t *t1 = (apr_time_t *) ac;
>>>>> -    apr_time_t t2 = (apr_time_t) (((motorz_timer_t *) b)->expires);
>>>>> -    AP_DEBUG_ASSERT(t2);
>>>>> -    return ((*t1 < t2) ? -1 : 1);
>>>>> +    if (a != b) {
>>>>> +        apr_time_t t1 = (apr_time_t) (((motorz_timer_t *) a)->expires);
>>>>> +        apr_time_t t2 = (apr_time_t) (((motorz_timer_t *) b)->expires);
>>>>> +        AP_DEBUG_ASSERT(t1);
>>>>> +        AP_DEBUG_ASSERT(t2);
>>>>> +        return ((t1 < t2) ? -1 : 1);
>>>>> +    }
>>>>> +    else {
>>>>> +        return 0;
>>>>> +    }
>>>>> }
>>>>
>>>> I expected this compare function to work with apr_skiplist_remove()
>>>> but actually it does not.
>>>> The goal was to match the given pointer only (and not any other
>>>> duplicate!), but by returning +1 when a != b && t1 == t2, we may
skip
>>>> timers inserted first should any duplicate be inserted later with a
>>>> higher eight.
>>>>
>>>> For example, the below is the gdb output (dump_dipklist) after 10
>>>> duplicates have been inserted, where each 2-tuple is the address of
>>>> the node (0x...,) containing the address of the element (,000000...):
>>>>
>>>> (gdb) dump_skiplist skiplist
>>>> skiplist@0x69aba0: size=10: height=3
>>>> (0x69b008,000000000000) (0x6ac3c0,000000000000) (0x6ac628,000000000000)
>>>> (0x69b048,00000069b000)
>>>> (0x6ac338,00000069b088)
>>>> (0x6ac380,0000006ac378) (0x6ac400,0000006ac378)
>>>> (0x6ac448,0000006ac440)
>>>> (0x6ac490,0000006ac488) (0x6ac4d0,0000006ac488)
>>>> (0x6ac518,0000006ac510)
>>>> (0x6ac560,0000006ac558)
>>>> (0x6ac5a8,0000006ac5a0) (0x6ac5e8,0000006ac5a0) (0x6ac668,0000006ac5a0)
>>>> (0x6ac6b0,0000006ac6a8) (0x6ac6f0,0000006ac6a8)
>>>> (0x6ac738,0000006ac730) (0x6ac778,0000006ac730)
>>>>
>>>> If e.g. we now try to remove the element (0x6ac448,0000006ac440),
>>>> starting at the top (0x6ac628,000000000000), we will jump directly
>>>> next to (0x6ac668,0000006ac5a0), then down (no next) to
>>>> (0x6ac5e8,0000006ac5a0), then next to (0x6ac6f0,0000006ac6a8), then
>>>> next to (0x6ac778,0000006ac730), then down (no next) to
>>>> (0x6ac738,0000006ac730), and finally (no next, no down) to NULL.
>>>> All the elements (all duplicates) between the top and
>>>> (0x6ac668,0000006ac5a0) have been skipped, hence we had no chance to
>>>> find (0x6ac448,0000006ac440), because at least one element was
>>>> inserted later (exactly 4 here) with a higher eight.
>>>>
>>>> This is not an issue about insert vs add semantic, with both functions
>>>> we still need a "reliable" compare function to remove the exact
>>>> (requested) timer, and I see no way to build one...
>>>>
>>>> Thoughts?
>> <skiplist_timer_comp.patch>
>

Mime
View raw message