[RFC]Routes are stored as a linked list

Donald Sharp

Sat Mar 02 14:31:36 2019


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

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.



Attachment: 0001-Convert-TAILQ-to-RB_TREE.patch
Description: Binary data

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