conntrackd: questions about the new alarm implementation

conntrackd: questions about the new alarm implementation

[Max Kellermann]

Hi Pablo,

I have had a look at your new alarm.c.  I have a few questions about
it:

- Please explain why you now have 2048 (!) alarm queues, where the
  correct one is determined by hashing the alarm struct.  I fail to
  imagine how this hashing might be useful.  I can only see that it
  makes the code more complex and 2048 times slower - except for
  add_alarm(), which becomes a little bit faster, but there are only
  few add_alarm() invocations compared with get_next_alarm_run() and
  do_alarm_run().

- __run() is again bugged regarding due alarms: when an alarm is due,
  all readied file descriptors are ignored (l 193).  This is
  automatically recovered in the next select() call, so you didn't
  notice it.  Why do you keep screwing up this piece of code over and
  over? ;-)

- why this overcomplicated new __run() prototype with an int pointer
  parameter?  Its returned value is never used.  Its input value is
  only used to set next_alarm to NULL - why not just pass NULL as
  next_alarm in the first place (my patches did exactly that)?  Why
  does __run() have a return value?

Max

Re: conntrackd: questions about the new alarm implementation

[Pablo Neira Ayuso]

Max Kellermann wrote:
> I have had a look at your new alarm.c.  I have a few questions about
> it:
> 
> - Please explain why you now have 2048 (!) alarm queues, where the
>   correct one is determined by hashing the alarm struct.  I fail to
>   imagine how this hashing might be useful.  I can only see that it
>   makes the code more complex and 2048 times slower - except for
>   add_alarm(), which becomes a little bit faster, but there are only
>   few add_alarm() invocations compared with get_next_alarm_run() and
>   do_alarm_run().

This assumption is true for stats and sync-ftfw. However, it's not for
the sync-alarm implementation. The previous approach sucks up CPU in
add_alarm() with 25000 connections. Current the benchmarks report
smoother results.

-- 
"Los honestos son inadaptados sociales" -- Les Luthiers

Re: conntrackd: questions about the new alarm implementation

[Max Kellermann]

On 2008/01/21 13:55, Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> Max Kellermann wrote:
> > I have had a look at your new alarm.c.  I have a few questions about
> > it:
> > 
> > - Please explain why you now have 2048 (!) alarm queues, where the
> >   correct one is determined by hashing the alarm struct.  I fail to
> >   imagine how this hashing might be useful.  I can only see that it
> >   makes the code more complex and 2048 times slower - except for
> >   add_alarm(), which becomes a little bit faster, but there are only
> >   few add_alarm() invocations compared with get_next_alarm_run() and
> >   do_alarm_run().
> 
> This assumption is true for stats and sync-ftfw. However, it's not for
> the sync-alarm implementation. The previous approach sucks up CPU in
> add_alarm() with 25000 connections. Current the benchmarks report
> smoother results.

I wasn't aware that the alarm library has to scale up to so many alarm
objects.  Of course, linear search in a linked list is slow in these
dimensions, but there *has* to be a better algorithm.  I will send a
patch as soon as I have time to think about that.

Max

Re: conntrackd: questions about the new alarm implementation

[Pablo Neira Ayuso]

Max Kellermann wrote:
> On 2008/01/21 13:55, Pablo Neira Ayuso <pablo@netfilter.org> wrote:
>> Max Kellermann wrote:
>>> I have had a look at your new alarm.c.  I have a few questions about
>>> it:
>>>
>>> - Please explain why you now have 2048 (!) alarm queues, where the
>>>   correct one is determined by hashing the alarm struct.  I fail to
>>>   imagine how this hashing might be useful.  I can only see that it
>>>   makes the code more complex and 2048 times slower - except for
>>>   add_alarm(), which becomes a little bit faster, but there are only
>>>   few add_alarm() invocations compared with get_next_alarm_run() and
>>>   do_alarm_run().
>> This assumption is true for stats and sync-ftfw. However, it's not for
>> the sync-alarm implementation. The previous approach sucks up CPU in
>> add_alarm() with 25000 connections. Current the benchmarks report
>> smoother results.
> 
> I wasn't aware that the alarm library has to scale up to so many alarm
> objects.  Of course, linear search in a linked list is slow in these
> dimensions, but there *has* to be a better algorithm. 

Sure. Current approach gives good results to my benchmarks and I can
make peace since it's not linear anymore ;).

> I will send a patch as soon as I have time to think about that.

Great. I bet that this will be a win for conntrackd.

-- 
"Los honestos son inadaptados sociales" -- Les Luthiers

Re: conntrackd: questions about the new alarm implementation

[Max Kellermann]

On 2008/01/21 14:18, Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> Sure. Current approach gives good results to my benchmarks and I can
> make peace since it's not linear anymore ;).

It's still linear.  add_alarm() is still O(n), or better: it is
O(n/2048) which is mathematically the same as O(n).  But you made
everything else O(n*2048) = O(n), which is why I dislike this
optimization - you optimized for one artificial test case, penalizing
the majority of conntrackd users who don't have 25.000 connections.

Max

Re: conntrackd: questions about the new alarm implementation

[Pablo Neira Ayuso]

Max Kellermann wrote:
> On 2008/01/21 14:18, Pablo Neira Ayuso <pablo@netfilter.org> wrote:
>> Sure. Current approach gives good results to my benchmarks and I can
>> make peace since it's not linear anymore ;).
> 
> It's still linear.  add_alarm() is still O(n), or better: it is
> O(n/2048) which is mathematically the same as O(n).  But you made
> everything else O(n*2048) = O(n), which is why I dislike this
> optimization - you optimized for one artificial test case, penalizing
> the majority of conntrackd users who don't have 25.000 connections.

Indeed, it's still linear, what I meant to say is that we keep n smaller
since now it depends on the number of alarms in the bucket. The
statistics users are not penalized since they never run alarms. This is
true for sync-ftfw users though which only use one alarm, probably we
can tune the alarm scheduler (ALARM_HASH_SIZE) depending on the
conntrackd working mode.

-- 
"Los honestos son inadaptados sociales" -- Les Luthiers