You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Yann Ylavic <yl...@gmail.com> on 2014/05/22 12:04:50 UTC
apr_skiplist (current) implementation wrt mpm_event (timers, keepalives?)
Hello,
while working on
https://issues.apache.org/bugzilla/show_bug.cgi?id=56226 for a
possible way to use vhost's KeepAliveTimeout with mpm_event (by using
a skiplist instead of the actual keepalive queue), I realized that
apr_skiplists do not accept multiple values per key (unlike apr_table
for example, or std::multimap).
AFAICT this is only an implementation choice, which could be changed
with something like :
Index: tables/apr_skiplist.c
===================================================================
--- tables/apr_skiplist.c (revision 1595631)
+++ tables/apr_skiplist.c (working copy)
@@ -406,11 +406,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
if (m->next) {
compared = comp(data, m->next->data);
}
- if (compared == 0) {
- free(stack); /* OK. was malloc'ed */
- return 0;
- }
- if ((m->next == NULL) || (compared < 0)) {
+ if (compared < 0) {
if (ch <= nh) {
/* push on stack */
stack[stacki++] = m;
(probably with a new apr_skiplist_set_multi() which would make it controlable).
The skiplist's key used for timers by mpm_event is the expiration time
(in microseconds), I think the issue is multiple timers created at the
same time (which may happen when different threads request a timer,
eg. with event_register_[timed|socket]_callback).
In that case, none but the first one will be inserted in the skiplist
(and hence known by listener).
Shouldn't skiplists accept multiple values for the same key by default?
For 56226, if we were to replace the actual keepalive queue with a
skiplist, the proposed patch suffers the same issue.
If however the current behaviour (and speed) of using the base
server's KeepaliveTimeout for all the vhosts is a choice, I think it
should at least be documented on the KeepAliveTimeout directive, as a
limitation for mpm_event.
Regards,
Yann.
Re: apr_skiplist (current) implementation wrt mpm_event (timers, keepalives?)
Posted by Paul Querna <pa...@querna.org>.
- I think it is good to fix this behavior, using only the global
keepalive timeout was definitely a choice I (?) made when doing it.
- Skiplists seem generally acceptable for storing this data.
Alternatively a BTree with in order iteration would be competitive..
but, meh, either will be fine.
- I'd love if we could seek ways to unify the timeout queues inside
the Event MPM. Right now we have:
* keepalive_q
* write_completion_q
* linger_q
* short_linger_q
Maybe making a single structure for all timeouts, with a baton / type
enum for any extra data or the function to call?
For example `write_completion_q` is mapped to global server TimeOut
directive.. so same bug as KeepAliveTimeOut.
Making just the keepalive queue a skiplist, and leaving the others...
seems less than optimal in my view.
- No comment on fixing APR Skiplists :)
On Thu, May 22, 2014 at 5:04 AM, Yann Ylavic <yl...@gmail.com> wrote:
> Hello,
>
> while working on
> https://issues.apache.org/bugzilla/show_bug.cgi?id=56226 for a
> possible way to use vhost's KeepAliveTimeout with mpm_event (by using
> a skiplist instead of the actual keepalive queue), I realized that
> apr_skiplists do not accept multiple values per key (unlike apr_table
> for example, or std::multimap).
>
> AFAICT this is only an implementation choice, which could be changed
> with something like :
> Index: tables/apr_skiplist.c
> ===================================================================
> --- tables/apr_skiplist.c (revision 1595631)
> +++ tables/apr_skiplist.c (working copy)
> @@ -406,11 +406,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
> if (m->next) {
> compared = comp(data, m->next->data);
> }
> - if (compared == 0) {
> - free(stack); /* OK. was malloc'ed */
> - return 0;
> - }
> - if ((m->next == NULL) || (compared < 0)) {
> + if (compared < 0) {
> if (ch <= nh) {
> /* push on stack */
> stack[stacki++] = m;
>
> (probably with a new apr_skiplist_set_multi() which would make it controlable).
>
> The skiplist's key used for timers by mpm_event is the expiration time
> (in microseconds), I think the issue is multiple timers created at the
> same time (which may happen when different threads request a timer,
> eg. with event_register_[timed|socket]_callback).
> In that case, none but the first one will be inserted in the skiplist
> (and hence known by listener).
>
> Shouldn't skiplists accept multiple values for the same key by default?
>
> For 56226, if we were to replace the actual keepalive queue with a
> skiplist, the proposed patch suffers the same issue.
> If however the current behaviour (and speed) of using the base
> server's KeepaliveTimeout for all the vhosts is a choice, I think it
> should at least be documented on the KeepAliveTimeout directive, as a
> limitation for mpm_event.
>
> Regards,
> Yann.
Re: apr_skiplist (current) implementation wrt mpm_event (timers, keepalives?)
Posted by Jim Jagielski <ji...@jaguNET.com>.
But that would change behavior, which we really shouldn't
do.
On May 27, 2014, at 11:01 AM, Yann Ylavic <yl...@gmail.com> wrote:
> On Tue, May 27, 2014 at 4:21 PM, Jim Jagielski <ji...@jagunet.com> wrote:
>> Check out r1597797
>>
>> If OK, we can backport to 1.6
>
> I would have preferred skiplist_insert() == skiplist_add(), since it
> seems to be needed by mpm_event (unless we require APR 1.6 for
> httpd-2.4.x).
> But I guess it's a (behaviour) change which is not acceptable in APR.
> Is there any other apr_skiplist user other than httpd though?
>
> Otherwise I find the "replace" name a bit misleading, the previous
> value seems to be preserved instead (the new one being ignored).
> However the replace implementation looks non trivial, it would require
> to replace the duplicated (stacked) entries as well (void *data =>
> void **data?)...
>
Re: apr_skiplist (current) implementation wrt mpm_event (timers, keepalives?)
Posted by Yann Ylavic <yl...@gmail.com>.
On Tue, May 27, 2014 at 4:21 PM, Jim Jagielski <ji...@jagunet.com> wrote:
> Check out r1597797
>
> If OK, we can backport to 1.6
I would have preferred skiplist_insert() == skiplist_add(), since it
seems to be needed by mpm_event (unless we require APR 1.6 for
httpd-2.4.x).
But I guess it's a (behaviour) change which is not acceptable in APR.
Is there any other apr_skiplist user other than httpd though?
Otherwise I find the "replace" name a bit misleading, the previous
value seems to be preserved instead (the new one being ignored).
However the replace implementation looks non trivial, it would require
to replace the duplicated (stacked) entries as well (void *data =>
void **data?)...
Re: apr_skiplist (current) implementation wrt mpm_event (timers, keepalives?)
Posted by Jim Jagielski <ji...@jaguNET.com>.
Check out r1597797
If OK, we can backport to 1.6
On May 27, 2014, at 9:52 AM, Jim Jagielski <ji...@jaguNET.com> wrote:
> Adding dev@apr
> On May 22, 2014, at 6:04 AM, Yann Ylavic <yl...@gmail.com> wrote:
>
>> Hello,
>>
>> while working on
>> https://issues.apache.org/bugzilla/show_bug.cgi?id=56226 for a
>> possible way to use vhost's KeepAliveTimeout with mpm_event (by using
>> a skiplist instead of the actual keepalive queue), I realized that
>> apr_skiplists do not accept multiple values per key (unlike apr_table
>> for example, or std::multimap).
>>
>> AFAICT this is only an implementation choice, which could be changed
>> with something like :
>> Index: tables/apr_skiplist.c
>> ===================================================================
>> --- tables/apr_skiplist.c (revision 1595631)
>> +++ tables/apr_skiplist.c (working copy)
>> @@ -406,11 +406,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
>> if (m->next) {
>> compared = comp(data, m->next->data);
>> }
>> - if (compared == 0) {
>> - free(stack); /* OK. was malloc'ed */
>> - return 0;
>> - }
>> - if ((m->next == NULL) || (compared < 0)) {
>> + if (compared < 0) {
>> if (ch <= nh) {
>> /* push on stack */
>> stack[stacki++] = m;
>>
>> (probably with a new apr_skiplist_set_multi() which would make it controlable).
>>
>
> +1 on extending skiplist for multi-values per key.
>
> Maybe have apr_skiplist_set for current insert behavior and
> apr_skiplist_add() for multi-value option... We can then
> deprecate _insert.
>
> Good for apr-1.6.
Re: apr_skiplist (current) implementation wrt mpm_event (timers, keepalives?)
Posted by Jim Jagielski <ji...@jaguNET.com>.
Adding dev@apr
On May 22, 2014, at 6:04 AM, Yann Ylavic <yl...@gmail.com> wrote:
> Hello,
>
> while working on
> https://issues.apache.org/bugzilla/show_bug.cgi?id=56226 for a
> possible way to use vhost's KeepAliveTimeout with mpm_event (by using
> a skiplist instead of the actual keepalive queue), I realized that
> apr_skiplists do not accept multiple values per key (unlike apr_table
> for example, or std::multimap).
>
> AFAICT this is only an implementation choice, which could be changed
> with something like :
> Index: tables/apr_skiplist.c
> ===================================================================
> --- tables/apr_skiplist.c (revision 1595631)
> +++ tables/apr_skiplist.c (working copy)
> @@ -406,11 +406,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
> if (m->next) {
> compared = comp(data, m->next->data);
> }
> - if (compared == 0) {
> - free(stack); /* OK. was malloc'ed */
> - return 0;
> - }
> - if ((m->next == NULL) || (compared < 0)) {
> + if (compared < 0) {
> if (ch <= nh) {
> /* push on stack */
> stack[stacki++] = m;
>
> (probably with a new apr_skiplist_set_multi() which would make it controlable).
>
+1 on extending skiplist for multi-values per key.
Maybe have apr_skiplist_set for current insert behavior and
apr_skiplist_add() for multi-value option... We can then
deprecate _insert.
Good for apr-1.6.
Re: apr_skiplist (current) implementation wrt mpm_event (timers, keepalives?)
Posted by Jim Jagielski <ji...@jaguNET.com>.
Adding dev@apr
On May 22, 2014, at 6:04 AM, Yann Ylavic <yl...@gmail.com> wrote:
> Hello,
>
> while working on
> https://issues.apache.org/bugzilla/show_bug.cgi?id=56226 for a
> possible way to use vhost's KeepAliveTimeout with mpm_event (by using
> a skiplist instead of the actual keepalive queue), I realized that
> apr_skiplists do not accept multiple values per key (unlike apr_table
> for example, or std::multimap).
>
> AFAICT this is only an implementation choice, which could be changed
> with something like :
> Index: tables/apr_skiplist.c
> ===================================================================
> --- tables/apr_skiplist.c (revision 1595631)
> +++ tables/apr_skiplist.c (working copy)
> @@ -406,11 +406,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
> if (m->next) {
> compared = comp(data, m->next->data);
> }
> - if (compared == 0) {
> - free(stack); /* OK. was malloc'ed */
> - return 0;
> - }
> - if ((m->next == NULL) || (compared < 0)) {
> + if (compared < 0) {
> if (ch <= nh) {
> /* push on stack */
> stack[stacki++] = m;
>
> (probably with a new apr_skiplist_set_multi() which would make it controlable).
>
+1 on extending skiplist for multi-values per key.
Maybe have apr_skiplist_set for current insert behavior and
apr_skiplist_add() for multi-value option... We can then
deprecate _insert.
Good for apr-1.6.