[tor-commits] [tor/maint-0.2.2] Fix binary search on lists of 0 or 1 element.

[nickm@xxxxxxxxxxxxxx]

commit 8905789170269d29ad87530642ecc2a6a891219b
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
Date:   Tue Oct 23 17:12:37 2012 -0400

    Fix binary search on lists of 0 or 1 element.
    
    The implementation we added has a tendency to crash with lists of 0 or
    one element.  That can happen if we get a consensus vote, v2
    consensus, consensus, or geoip file with 0 or 1 element.  There's a
    DOS opportunity there that authorities could exploit against one
    another, and which an evil v2 authority could exploit against anything
    downloading v2 directory information..
    
    This fix is minimalistic: It just adds a special-case for 0- and
    1-element lists.  For 0.2.4 (the current alpha series) we'll want a
    better patch.
    
    This is bug 7191; it's a fix on 0.2.0.10-alpha.
---
 src/common/container.c |   23 ++++++++++++++++++++++-
 1 files changed, 22 insertions(+), 1 deletions(-)

diff --git a/src/common/container.c b/src/common/container.c
index 5f53222..c047562 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -572,7 +572,28 @@ smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
                       int (*compare)(const void *key, const void **member),
                       int *found_out)
 {
-  int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid;
+  const int len = smartlist_len(sl);
+  int hi, lo, cmp, mid;
+
+  if (len == 0) {
+    *found_out = 0;
+    return 0;
+  } else if (len == 1) {
+    cmp = compare(key, (const void **) &sl->list[0]);
+    if (cmp == 0) {
+      *found_out = 1;
+      return 0;
+    } else if (cmp < 0) {
+      *found_out = 0;
+      return 0;
+    } else {
+      *found_out = 0;
+      return 1;
+    }
+  }
+
+  hi = smartlist_len(sl) - 1;
+  lo = 0;
 
   while (lo <= hi) {
     mid = (lo + hi) / 2;



_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits