VANHULLEBUS Yvan wrote:
> On Tue, Sep 16, 2008 at 11:19:25AM +0300, Timo Ters wrote:
>> The fundamental "problem" currently is that schedular() traverses
>> the full list of struct sched entries. This seems to be only to
>> remove the entries marked dead (as sched_add() makes sure that the
>> tree is sorted by execution time). Thus schedular() is O(n).
> The good news is that it still doesn't take so much CPU time for basic
> setups (a few remote sites, not so much IPSec SAs, and no errors at
> all), but it can start to consume some important amounts of CPU in
> some other setups (*lots* of peers, *lots* of IPSec SAs, and various
> configuration errors on some peers).
Yes, I'm afraid of bit similar here. Though it should not be too big
a problem. I'll probably start to get 100-150 peers sooner or later,
which would mean something like 300 scheduler entries or so, which
isn't too bad yet. But if it grows, it can become a problem at
>> I did similar schedular thingy in opennhrp. And it has schedular()
>> which is O(1), that is a constant time function (well, actually the
>> time varies based on how many entries expired and were executed, but
>> it does not do full traversal of the list). This is achieved by
>> sched_kill() doing the removal from the list, and taking care in
>> other places that the list entry references are not cached. So I'm
>> planning to do the same.
> Having a better schedular would be great. I planned to do that some
> time ago, but I realized that the changes I was about to commit just
> moved the CPU time from one place to another, so I discarded them.
> As long as your schedular is quite always at least as fast as the
> actual, it is ok for me.
The proposed change would be as fast with most operations. But
schedular() would be speeded up significantly (when there's lot of
schedule items in queue).
If inserting an entry becomes too slow, we might have to implement
binary heap or something similar which has O(lg n) running time for
node insertion and removal. I did this for another project of mine
that has thousands of scheduler entries with small intervals and a
lot of insertions.
>> But I also was thinking to embed "struct sched" where it was used,
>> instead of dynamically allocating it. Since mostly the schedule
>> pointer is always in schedule, so it'll reduce memory
>> allocations. That way we could also get rid of "void *param" and let
>> it point to "struct sched" instead, then the callback function could
>> deduce the pointer to context structure from that. Not allocating
>> dynamically also might help to avoid memory corruption bugs, such as
>> we had earlier with DPD timer, see commit from 2007-12-30. What
>> would you think about this change?
> This is quite another stuff....
> Removing the _stub() functions would be interesting, and avoiding
> memory corruptions is of course a good thing. Would you plan to do
> that for 0.8.x branch, or will you commit them to HEAD later ?
Well, we would not get rid of _stub() functions. Actually, currently
those could be removed as they do only a typecast. In the proposed
change we would definitely need _stub() functions as the pointer is
manipulated by an offset. The only useful advantage would be smaller
memory footprint (as struct sched.param would become obsolete).
Similar approach is used also in e.g. Linux kernel.
I was hoping to commit the phase1 rekeying and the scheduler changes
before branching 0.8.
The ph1 rekeying stuff should about done (just waiting feedback and
doing more testing), and the scheduler stuff is pretty fast written.
I expect to get a working patch ready today or by latest tomorrow