First stab at a choke algorithm for all peers. In previous versions choking

was done per torrent.

1 files changed, 110 insertions, 7 deletions

diff --git a/btpd/upload.c b/btpd/upload.c
index 42de2ac..4ce7b42 100644
--- a/btpd/upload.c
+++ b/btpd/upload.c
@@ -1,31 +1,134 @@
+#include <string.h>
 
 #include "btpd.h"
 
+#define CHOKE_INTERVAL (& (struct timeval) { 10, 0 })
+
 static struct event m_choke_timer;
 static unsigned m_npeers;
 static struct peer_tq m_peerq = BTPDQ_HEAD_INITIALIZER(m_peerq);
+static int m_max_downloaders = 4;
+
+struct peer_sort {
+    struct peer *p;
+    unsigned i;
+};
+
+static int
+rate_cmp(const void *arg1, const void *arg2)
+{
+    struct peer *p1 = (*(struct peer_sort **)arg1)->p;
+    struct peer *p2 = (*(struct peer_sort **)arg2)->p;
+    unsigned long rate1 = torrent_has_all(p1->tp) ? p1->rate_up : p1->rate_dwn;
+    unsigned long rate2 = torrent_has_all(p2->tp) ? p2->rate_up : p2->rate_dwn;
+    if (rate1 < rate2)
+        return -1;
+    else if (rate1 == rate2)
+        return 0;
+    else
+        return 1;
+}
 
 static void
 choke_do(void)
 {
-    struct peer *p;
-    BTPDQ_FOREACH(p, &m_peerq, ul_entry)
-        if (p->flags & PF_I_CHOKE)
-            peer_unchoke(p);
+    if (m_max_downloaders == -1) {
+        struct peer *p;
+        BTPDQ_FOREACH(p, &m_peerq, ul_entry)
+            if (p->flags & PF_I_CHOKE)
+                peer_unchoke(p);
+    } else if (m_max_downloaders == 0) {
+        struct peer *p;
+        BTPDQ_FOREACH(p, &m_peerq, ul_entry)
+            if ((p->flags & PF_I_CHOKE) == 0)
+                peer_choke(p);
+    } else if (m_npeers > 0) {
+        struct peer_sort worthy[m_npeers];
+        unsigned nworthy = 0;
+        unsigned i = 0;
+        unsigned found = 0;
+        struct peer *p;
+        int unchoked[m_npeers];
+
+        BTPDQ_FOREACH(p, &m_peerq, ul_entry) {
+            if (((torrent_has_all(p->tp) && p->rate_up > 0)
+                    || (!torrent_has_all(p->tp) && p->rate_dwn > 0))) {
+                worthy[nworthy].p = p;
+                worthy[nworthy].i = i;
+                nworthy++;
+            }
+            i++;
+        }
+        qsort(worthy, nworthy, sizeof(worthy[0]), rate_cmp);
+
+        bzero(unchoked, sizeof(unchoked));
+        for (i = nworthy - 1; i >= 0 && found < m_max_downloaders - 1; i--) {
+            if ((worthy[i].p->flags & PF_P_WANT) != 0)
+                found++;
+            if ((worthy[i].p->flags & PF_I_CHOKE) != 0)
+                peer_unchoke(p);
+            unchoked[worthy[i].i] = 1;
+        }
+
+        i = 0;
+        BTPDQ_FOREACH(p, &m_peerq, ul_entry) {
+            if (!unchoked[i]) {
+                if (found < m_max_downloaders) {
+                    if (p->flags & PF_P_WANT)
+                        found++;
+                    if (p->flags & PF_I_CHOKE)
+                        peer_unchoke(p);
+                } else {
+                    if ((p->flags & PF_I_CHOKE) == 0)
+                        peer_choke(p);
+                }
+            }
+            i++;
+        }
+    }
+}
+
+static void
+shuffle_optimists(void)
+{
+    for (unsigned i = 0; i < m_npeers; i++) {
+        struct peer *p = BTPDQ_FIRST(&m_peerq);
+        if ((p->flags & (PF_P_WANT|PF_I_CHOKE)) == (PF_P_WANT|PF_I_CHOKE)) {
+            break;
+        } else {
+            BTPDQ_REMOVE(&m_peerq, p, ul_entry);
+            BTPDQ_INSERT_TAIL(&m_peerq, p, ul_entry);
+        }
+    }
 }
 
 static void
 choke_cb(int sd, short type, void *arg)
 {
-    evtimer_add(&m_choke_timer, (& (struct timeval) { 10, 0}));
+    evtimer_add(&m_choke_timer, CHOKE_INTERVAL);
+    static int cb_count = 0;
+    cb_count++;
+    if (cb_count % 3 == 0)
+        shuffle_optimists();
     choke_do();
 }
 
 void
 ul_on_new_peer(struct peer *p)
 {
+    long where = rand_between(-2, m_npeers);
+    if (where < 1)
+        BTPDQ_INSERT_HEAD(&m_peerq, p, ul_entry);
+    else {
+        struct peer *it = BTPDQ_FIRST(&m_peerq);
+        where--;
+        while (where > 0) {
+            it = BTPDQ_NEXT(it, ul_entry);
+            where--;
+        }
+        BTPDQ_INSERT_AFTER(&m_peerq, it, p, ul_entry);
+    }
     m_npeers++;
-    BTPDQ_INSERT_HEAD(&m_peerq, p, ul_entry);
     choke_do();
 }
 
@@ -70,5 +173,5 @@ void
 ul_init(void)
 {
     evtimer_set(&m_choke_timer, choke_cb, NULL);
-    evtimer_add(&m_choke_timer, (& (struct timeval) { 10, 0 }));
+    evtimer_add(&m_choke_timer, CHOKE_INTERVAL);
 }