httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jim Jagielski <...@jaguNET.com>
Subject Re: svn commit: r1666619 - /httpd/httpd/trunk/server/mpm/motorz/motorz.c
Date Fri, 10 Apr 2015 13:26:16 GMT
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