Re: [RFC]Routes are stored as a linked list

Roy Marples

Sun Mar 03 12:10:37 2019

Hi Donald

On 02/03/2019 14:31, Donald Sharp wrote:

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


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!


Re: [RFC]Routes are stored as a linked listDonald Sharp
[RFC]Routes are stored as a linked listDonald Sharp
Archive administrator: postmaster@marples.name