From 589987f8218c9aa61d65f582a3b3e1bbd32bda81 Mon Sep 17 00:00:00 2001
From: Fredrik Tolf <fredrik@dolda2000.com>
Date: Tue, 1 Jan 2013 08:36:50 +0100
Subject: [PATCH] lib: Reimplemented mtio-epoll timeout checking as a bin-heap.

---
 lib/mtio-epoll.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 78 insertions(+), 16 deletions(-)

diff --git a/lib/mtio-epoll.c b/lib/mtio-epoll.c
index 72468e0..2a25992 100644
--- a/lib/mtio-epoll.c
+++ b/lib/mtio-epoll.c
@@ -38,13 +38,20 @@ struct blocker {
     struct blocker *n, *p, *n2, *p2;
     int fd, reg;
     int ev;
+    int thpos;
     time_t to;
     struct muth *th;
 };
 
+struct timeentry {
+    time_t to;
+    struct blocker *bl;
+};
+
 static int epfd = -1, fdln = 0;
 static int exitstatus;
 static struct blocker **fdlist;
+static typedbuf(struct timeentry) timeheap;
 
 static int regfd(struct blocker *bl)
 {
@@ -129,6 +136,65 @@ static void remfd(struct blocker *bl)
     bl->reg = 0;
 }
 
+static void thraise(struct timeentry ent, int n)
+{
+    int p;
+    
+    while(n > 0) {
+	p = (n - 1) >> 1;
+	if(timeheap.b[p].to <= ent.to)
+	    break;
+	timeheap.b[n] = timeheap.b[p];
+	timeheap.b[n].bl->thpos = n;
+	n = p;
+    }
+    timeheap.b[n] = ent;
+    ent.bl->thpos = n;
+}
+
+static void thlower(struct timeentry ent, int n)
+{
+    int c;
+    
+    while(1) {
+	c = (n << 1) + 1;
+	if(c >= timeheap.d)
+	    break;
+	if((c + 1 < timeheap.d) && (timeheap.b[c + 1].to < timeheap.b[c].to))
+	    c = c + 1;
+	if(timeheap.b[c].to > ent.to)
+	    break;
+	timeheap.b[n] = timeheap.b[c];
+	timeheap.b[n].bl->thpos = n;
+	n = c;
+    }
+    timeheap.b[n] = ent;
+    ent.bl->thpos = n;
+}
+
+static void addtimeout(struct blocker *bl, time_t to)
+{
+    sizebuf(timeheap, ++timeheap.d);
+    thraise((struct timeentry){.to = to, .bl = bl}, timeheap.d - 1);
+}
+
+static void deltimeout(struct blocker *bl)
+{
+    struct timeentry ent;
+    int n;
+    
+    if(bl->thpos == timeheap.d - 1) {
+	timeheap.d--;
+	return;
+    }
+    n = bl->thpos;
+    ent = timeheap.b[--timeheap.d];
+    if((n > 0) && (timeheap.b[(n - 1) >> 1].to > ent.to))
+	thraise(ent, n);
+    else
+	thlower(ent, n);
+}
+
 int block(int fd, int ev, time_t to)
 {
     struct blocker *bl;
@@ -137,8 +203,6 @@ int block(int fd, int ev, time_t to)
     omalloc(bl);
     bl->fd = fd;
     bl->ev = ev;
-    if(to > 0)
-	bl->to = time(NULL) + to;
     bl->th = current;
     if((epfd >= 0) && regfd(bl)) {
 	free(bl);
@@ -148,7 +212,11 @@ int block(int fd, int ev, time_t to)
     if(blockers)
 	blockers->p = bl;
     blockers = bl;
+    if(to > 0)
+	addtimeout(bl, bl->to = (time(NULL) + to));
     rv = yield();
+    if(bl->to > 0)
+	deltimeout(bl);
     if(bl->n)
 	bl->n->p = bl->p;
     if(bl->p)
@@ -165,27 +233,23 @@ int ioloop(void)
     struct blocker *bl, *nbl;
     struct epoll_event evr[16];
     int i, fd, nev, ev, toval;
-    time_t now, timeout;
+    time_t now;
     
     exitstatus = 0;
     epfd = epoll_create(128);
     fcntl(epfd, F_SETFD, FD_CLOEXEC);
+    bufinit(timeheap);
     for(bl = blockers; bl; bl = nbl) {
 	nbl = bl->n;
 	if(regfd(bl))
 	    resume(bl->th, -1);
     }
     while(blockers != NULL) {
-	timeout = 0;
-	for(bl = blockers; bl; bl = bl->n) {
-	    if((bl->to != 0) && ((timeout == 0) || (timeout > bl->to)))
-		timeout = bl->to;
-	}
 	now = time(NULL);
-	if(timeout == 0)
+	if(timeheap.d == 0)
 	    toval = -1;
-	else if(timeout > now)
-	    toval = (timeout - now) * 1000;
+	else if(timeheap.b[0].to > now)
+	    toval = (timeheap.b[0].to - now) * 1000;
 	else
 	    toval = 1000;
 	if(exitstatus)
@@ -216,14 +280,12 @@ int ioloop(void)
 	    }
 	}
 	now = time(NULL);
-	for(bl = blockers; bl; bl = nbl) {
-	    nbl = bl->n;
-	    if((bl->to != 0) && (bl->to <= now))
-		resume(bl->th, 0);
-	}
+	while((timeheap.d > 0) && (timeheap.b[0].to <= now))
+	    resume(timeheap.b[0].bl->th, 0);
     }
     for(bl = blockers; bl; bl = bl->n)
 	remfd(bl);
+    buffree(timeheap);
     close(epfd);
     epfd = -1;
     return(exitstatus);
-- 
2.11.0