[PATCH] Use rbtree for looking up the client in rebound(8)

[Dimitris Papastamos]

Hi,

There was a comment in the code that indicated that it might be worth
investigating the use of trees.  I have not currently done any kind of
serious benchmarking on this but I am looking into it.

===================================================================
RCS file: /cvs/src/usr.sbin/rebound/rebound.c,v
retrieving revision 1.28
diff -u -p -r1.28 rebound.c
--- rebound.c   26 Oct 2015 12:24:48 -0000      1.28
+++ rebound.c   27 Oct 2015 17:02:36 -0000
@@ -19,6 +19,7 @@
 #include <arpa/inet.h>
 #include <netinet/in.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/event.h>
 #include <sys/time.h>
 #include <sys/signal.h>
@@ -83,11 +84,14 @@ struct request {
        socklen_t fromlen;
        struct timespec ts;
        TAILQ_ENTRY(request) fifo;
+       RB_ENTRY(request) reqnode;
        uint16_t clientid;
        uint16_t reqid;
        struct dnscache *cacheent;
 };
 static TAILQ_HEAD(, request) reqfifo;
+static RB_HEAD(reqtree, request) reqtree;
+RB_PROTOTYPE_STATIC(reqtree, request, reqnode, reqcmp)
 
 
 static void
@@ -144,6 +148,7 @@ freerequest(struct request *req)
        struct dnscache *ent;
 
        TAILQ_REMOVE(&reqfifo, req, fifo);
+       RB_REMOVE(reqtree, &reqtree, req);
        if (req->client != -1)
                close(req->client);
        if (req->s != -1)
@@ -164,6 +169,13 @@ freecacheent(struct dnscache *ent)
        free(ent);
 }
 
+static int
+reqcmp(struct request *r1, struct request *r2)
+{
+       return r1->s - r2->s;
+}
+RB_GENERATE_STATIC(reqtree, request, reqnode, reqcmp)
+
 static struct request *
 newrequest(int ud, struct sockaddr *remoteaddr)
 {
@@ -192,6 +204,7 @@ newrequest(int ud, struct sockaddr *remo
                return NULL;
 
        TAILQ_INSERT_TAIL(&reqfifo, req, fifo);
+       RB_INSERT(reqtree, &reqtree, req);
        req->ts = now;
        req->ts.tv_sec += 30;
 
@@ -298,6 +311,7 @@ newtcprequest(int ld, struct sockaddr *r
                return NULL;
 
        TAILQ_INSERT_TAIL(&reqfifo, req, fifo);
+       RB_INSERT(reqtree, &reqtree, req);
        req->ts = now;
        req->ts.tv_sec += 30;
 
@@ -358,7 +372,7 @@ launch(const char *confname, int ud, int
        struct sockaddr_storage remoteaddr;
        struct kevent chlist[2], kev[4];
        struct timespec ts, *timeout = NULL;
-       struct request *req;
+       struct request reqkey, *req;
        struct dnscache *ent;
        struct passwd *pwd;
        FILE *conf;
@@ -438,12 +452,8 @@ launch(const char *confname, int ud, int
                                        kevent(kq, chlist, 1, NULL, 0, NULL);
                                }
                        } else if (kev[i].filter == EVFILT_WRITE) {
-                               req = TAILQ_FIRST(&reqfifo);
-                               while (req) {
-                                       if (req->s == kev[i].ident)
-                                               break;
-                                       req = TAILQ_NEXT(req, fifo);
-                               }
+                               reqkey.s = kev[i].ident;
+                               req = RB_FIND(reqtree, &reqtree, &reqkey);
                                if (!req)
                                        logerr("lost request");
                                req = tcpphasetwo(req);
@@ -455,13 +465,8 @@ launch(const char *confname, int ud, int
                                        kevent(kq, chlist, 2, NULL, 0, NULL);
                                }
                        } else if (kev[i].filter == EVFILT_READ) {
-                               /* use a tree here? */
-                               req = TAILQ_FIRST(&reqfifo);
-                               while (req) {
-                                       if (req->s == kev[i].ident)
-                                               break;
-                                       req = TAILQ_NEXT(req, fifo);
-                               }
+                               reqkey.s = kev[i].ident;
+                               req = RB_FIND(reqtree, &reqtree, &reqkey);
                                if (!req)
                                        logerr("lost request");
                                if (req->client == -1)
@@ -547,6 +552,7 @@ main(int argc, char **argv)
        if (!debug)
                daemon(0, 0);
 
+       RB_INIT(&reqtree);
        TAILQ_INIT(&reqfifo);
        TAILQ_INIT(&cache);