[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[or-cvs] r10304: Add math functions to round values to the nearest power of 2 (in tor/trunk: . doc src/common src/or)



Author: nickm
Date: 2007-05-24 13:12:57 -0400 (Thu, 24 May 2007)
New Revision: 10304

Modified:
   tor/trunk/
   tor/trunk/doc/TODO
   tor/trunk/src/common/compat.h
   tor/trunk/src/common/mempool.c
   tor/trunk/src/common/util.c
   tor/trunk/src/common/util.h
   tor/trunk/src/or/test.c
Log:
 r12916@catbus:  nickm | 2007-05-24 12:43:45 -0400
 Add math functions to round values to the nearest power of 2.  Make mempools more careful about making sure that the size of their chunks is a little less than a power of 2, not a little more.



Property changes on: tor/trunk
___________________________________________________________________
 svk:merge ticket from /tor/trunk [r12916] on 8246c3cf-6607-4228-993b-4d95d33730f1

Modified: tor/trunk/doc/TODO
===================================================================
--- tor/trunk/doc/TODO	2007-05-24 17:12:54 UTC (rev 10303)
+++ tor/trunk/doc/TODO	2007-05-24 17:12:57 UTC (rev 10304)
@@ -83,6 +83,7 @@
         - Push/pull documents as appropriate.
         o Have clients know which authorities are v3 authorities, and what
           their keys are.
+          - While we're at it, let v3 authorities have fqdns lines.
       - Start caching consensus documents once authorities make them
       - Start downloading and using consensus documents once caches serve them
     . 104: Long and Short Router Descriptors (by Jun 1)

Modified: tor/trunk/src/common/compat.h
===================================================================
--- tor/trunk/src/common/compat.h	2007-05-24 17:12:54 UTC (rev 10303)
+++ tor/trunk/src/common/compat.h	2007-05-24 17:12:57 UTC (rev 10304)
@@ -96,6 +96,7 @@
 #if defined(__GNUC__) && __GNUC__ >= 3
 #define ATTR_NORETURN __attribute__((noreturn))
 #define ATTR_PURE __attribute__((pure))
+#define ATTR_CONST __attribute__((const))
 #define ATTR_MALLOC __attribute__((malloc))
 #define ATTR_NORETURN __attribute__((noreturn))
 #define ATTR_NONNULL(x) __attribute__((nonnull x))
@@ -108,6 +109,7 @@
 #else
 #define ATTR_NORETURN
 #define ATTR_PURE
+#define ATTR_CONST
 #define ATTR_MALLOC
 #define ATTR_NORETURN
 #define ATTR_NONNULL(x)

Modified: tor/trunk/src/common/mempool.c
===================================================================
--- tor/trunk/src/common/mempool.c	2007-05-24 17:12:54 UTC (rev 10303)
+++ tor/trunk/src/common/mempool.c	2007-05-24 17:12:57 UTC (rev 10304)
@@ -361,18 +361,24 @@
   /* Now we figure out how many items fit in each chunk.  We need to fit at
    * least 2 items per chunk. No chunk can be more than MAX_CHUNK bytes long,
    * or less than MIN_CHUNK. */
-  /* XXXX020 Try a bit harder here: we want to be a bit less than a power of
-     2, not a bit over. */
   if (chunk_capacity > MAX_CHUNK)
     chunk_capacity = MAX_CHUNK;
-  if (chunk_capacity < alloc_size * 2 + CHUNK_OVERHEAD)
-    chunk_capacity = alloc_size * 2 + CHUNK_OVERHEAD;
+  /* Try to be around a power of 2 in size, since that's what allocators like
+   * handing out. 512K-1 byte is a lot better than 512K+1 byte. */
+  chunk_capacity = (size_t) round_to_power_of_2(chunk_capacity);
+  while (chunk_capacity < alloc_size * 2 + CHUNK_OVERHEAD)
+    chunk_capacity *= 2;
   if (chunk_capacity < MIN_CHUNK)
     chunk_capacity = MIN_CHUNK;
 
   pool->new_chunk_capacity = (chunk_capacity-CHUNK_OVERHEAD) / alloc_size;
   pool->item_alloc_size = alloc_size;
 
+  log_debug(LD_MM, "Capacity is %lu, item size is %lu, alloc size is %lu",
+            (unsigned long)pool->new_chunk_capacity,
+            (unsigned long)pool->item_alloc_size,
+            (unsigned long)(pool->new_chunk_capacity*pool->item_alloc_size));
+
   return pool;
 }
 

Modified: tor/trunk/src/common/util.c
===================================================================
--- tor/trunk/src/common/util.c	2007-05-24 17:12:54 UTC (rev 10303)
+++ tor/trunk/src/common/util.c	2007-05-24 17:12:57 UTC (rev 10304)
@@ -214,6 +214,54 @@
 }
 
 /* =====
+ * Math
+ * ===== */
+
+/** Returns floor(log2(u64)).  If u64 is 0, (incorrectly) returns 0. */
+int
+tor_log2(uint64_t u64)
+{
+  int r = 0;
+  if (u64 >= (U64_LITERAL(1)<<32)) {
+    u64 >>= 32;
+    r = 32;
+  }
+  if (u64 >= (U64_LITERAL(1)<<16)) {
+    u64 >>= 16;
+    r += 16;
+  }
+  if (u64 >= (U64_LITERAL(1)<<8)) {
+    u64 >>= 8;
+    r += 8;
+  }
+  if (u64 >= (U64_LITERAL(1)<<4)) {
+    u64 >>= 4;
+    r += 4;
+  }
+  if (u64 >= (U64_LITERAL(1)<<2)) {
+    u64 >>= 2;
+    r += 2;
+  }
+  if (u64 >= (U64_LITERAL(1)<<1)) {
+    u64 >>= 1;
+    r += 1;
+  }
+  return r;
+}
+
+/** Return the power of 2 closest to <b>u64</b>. */
+uint64_t
+round_to_power_of_2(uint64_t u64)
+{
+  int lg2 = tor_log2(u64);
+  uint64_t low = U64_LITERAL(1) << lg2, high = U64_LITERAL(1) << (lg2+1);
+  if (high - u64 < u64 - low)
+    return high;
+  else
+    return low;
+}
+
+/* =====
  * String manipulation
  * ===== */
 

Modified: tor/trunk/src/common/util.h
===================================================================
--- tor/trunk/src/common/util.h	2007-05-24 17:12:54 UTC (rev 10303)
+++ tor/trunk/src/common/util.h	2007-05-24 17:12:57 UTC (rev 10304)
@@ -142,6 +142,10 @@
 /** Macro: true if two values have different boolean values. */
 #define bool_neq(a,b) (!(a)!=!(b))
 
+/* Math functions */
+int tor_log2(uint64_t u64) ATTR_CONST;
+uint64_t round_to_power_of_2(uint64_t u64);
+
 /* String manipulation */
 
 /** Allowable characters in a hexadecimal string. */

Modified: tor/trunk/src/or/test.c
===================================================================
--- tor/trunk/src/or/test.c	2007-05-24 17:12:54 UTC (rev 10303)
+++ tor/trunk/src/or/test.c	2007-05-24 17:12:57 UTC (rev 10304)
@@ -946,6 +946,26 @@
   tor_gettimeofday(&end);
   /* We might've timewarped a little. */
   test_assert(tv_udiff(&start, &end) >= -5000);
+
+  /* Test tor_log2(). */
+  test_eq(tor_log2(64), 6);
+  test_eq(tor_log2(65), 6);
+  test_eq(tor_log2(63), 5);
+  test_eq(tor_log2(1), 0);
+  test_eq(tor_log2(2), 1);
+  test_eq(tor_log2(3), 1);
+  test_eq(tor_log2(4), 2);
+  test_eq(tor_log2(5), 2);
+  test_eq(tor_log2(U64_LITERAL(40000000000000000)), 55);
+  test_eq(tor_log2(UINT64_MAX), 63);
+
+  /* Test round_to_power_of_2 */
+  test_eq(round_to_power_of_2(120), 128);
+  test_eq(round_to_power_of_2(128), 128);
+  test_eq(round_to_power_of_2(130), 128);
+  test_eq(round_to_power_of_2(U64_LITERAL(40000000000000000)),
+          U64_LITERAL(1)<<55);
+  test_eq(round_to_power_of_2(0), 2);
 }
 
 static void