dhcpcd-discuss

Hi Donald

On 02/03/2019 14:31, Donald Sharp wrote:
> Morning!
>
> I've been doing some performance data gathering for
> installation/removal of a large number of routes and noticed that
> dhcpcd was using a large amount of cpu when I did this.  After some
> quick investigation I noticed that dhcpcd uses a TAILQ for route
> storage.  I converted the TAILQ that was being used to a
> openbsd-tree.h RB_TREE and saw some fairly significant performance
> improvements when I installed and removed 1 million routes:
>
> Original Code:
>
> sharpd@janelle ~/s/debian> ps -ef | grep dhcpcd
> root     24802     1 66 13:42 ?        00:03:11 /usr/sbin/dhcpcd
> sharpd   24939 19416  0 13:47 pts/0    00:00:00 grep --color=auto dhcpcd
>
> With RB_TREE:
>
> sharpd@janelle ~/s/debian> ps -ef | grep dhcpcd
> root     24526     1 12 13:37 ?        00:00:29 /usr/sbin/dhcpcd
> sharpd   24626 19416  0 13:41 pts/0    00:00:00 grep --color=auto dhcpcd

That looks quite impressive.
Would you mind sharing the code you used to insert and remove these routes?

There is only one minor issue with the patch I've spotted from a cursory 
review - in rt_compare you don't need the HAVE_ROUTE_METRIC define.
Even when the OS doesn't support route metrics (ie evey OS other than 
Linux) we still prefer routes in metric order.
Other than that, it's just minor cosmetic issues which I can tart up as 
needed.

> At this point, I've run the modified dhcpcd but have done no real
> testing in that I'm not sure what to look for, nor am I aware of any
> project concerns about adding new data structures to the tree, or for
> that matter how this would really like to be handled and am seeking
> input on how to proceed.  I've attached the patch I've created so far
> for discussion purposes and yes I realize it is a bit of a hack to get
> it working at this point.
My only concern is what is best for dhcpcd.
My main dev platform is NetBSD and I'm also a NetBSD developer. So I 
tend to prefer to eat my own dog food, for better or worse.

In the tree(3) man page it states that these macros are deprecated and 
rbtree(3) should be used instead. rbtree is NetBSD specific in libc 
while tree(3) is only found on modern BSD - there is no linux equivalent 
either in muscl or glibc AFAIK.

Your patch takes OpenBSD code where they replaced the RB_ macros with 
the OpenBSD version of rbtree from NetBSD. The big difference AFAIK 
(aside from the actual implementation) is that the OpenBSD libc 
functions are not designed to be used directly whereas the NetBSD ones are.
NetBSD seems more powerful in this regards as to the tree setup with 
comparison functions.
Sadly, NetBSD lacks the SAFE macros of tree walking dhcpcd would need, 
but these are quite trivial to write so it's not that bad.

Lastly, the size of the binary is of some concern. How much larger does 
your patch grow dhcpcd?
Because rbtree is in NetBSD libc and some NetBSD boot targets that use 
dhcpcd are already size constrained, that seems like the better option 
to me.

This is quite important, because there could be servers with thousands 
of interfaces as well so an rbtree could be used here as well.

Regardless of how this turns, out many thanks for the work so far!

Roy