dhcpcd-discuss

Hi Roy -
To generate these routes I used FRRouting (https://frrouting.org).
The code can be found here: https://github.com/frrouting/frr.git .
Documentation to build on NetBSD is here:
http://docs.frrouting.org/projects/dev-guide/en/latest/building-frr-for-netbsd7.html
.  Essentially I used a new utility daemon to generate the routes via
cli: http://docs.frrouting.org/en/latest/sharp.html .  This can be a
bit complicated to setup, if you are interested in setting it up and
run into issues feel free to reach out to me, I'll get you any help
you may need here.

On to your questions about dhcpcd: I did see the rbtree()
functionality when I went searching for a replacement, but it is not
immediately available on linux..  I knew the rb_tree code would drop
right in as that we use it in our project.  Personally I don't have a
dog in this fight( hence the question in the original email ).  If you
want to use something else please do so, no skin off my back.  You'll
just need to point me at it if you want me to do the work :)

Size of original data structures:
(gdb) p sizeof(struct dhcpcd_ctx)
$1 = 600
(gdb) p sizeof(struct rt)
$2 = 160
(gdb)

1 million routes with original dhcpcd is ~19mb of main memory

Size w/ rb_tree:
(gdb) p sizeof(struct dhcpcd_ctx)
$1 = 904
(gdb) p sizeof(struct rt)
$2 = 176(gdb)

With 1 million routes with my code it's ~180mb of main memory.  This
implies I've introduced a memory leak, Looks like I'll need to look at
it this evening to see if I can figure out where I've gone wrong.  As
that an extra 16 bytes of memory per `struct rt` shouldn't be causing
this many problems.

donald

On Sun, Mar 3, 2019 at 7:12 AM Roy Marples <roy@xxxxxxxxxxxx> wrote:
>
> 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