Merge branch 'master' of ssh://gnunet.org/gnunet

3 files changed, 100 insertions, 71 deletions

diff --git a/contrib/scripts/netjail/netjail_core.sh b/contrib/scripts/netjail/netjail_core.sh
index 1cdbca816..d070f7220 100755
--- a/contrib/scripts/netjail/netjail_core.sh
+++ b/contrib/scripts/netjail/netjail_core.sh
@@ -28,6 +28,23 @@ netjail_opt() {
         printf "%d" 0
 }
 
+netjail_opts() {
+        local OPT=$1
+        local DEF=$2
+        shift 2
+        
+        while [ $# -gt 0 ]; do
+                if [ "$1" = "$OPT" ]; then
+                        printf "$2"
+                        return
+                fi
+
+                shift 1
+        done
+        
+        printf "$DEF"
+}
+
 netjail_check() {
         local NODE_COUNT=$1
         local FD_COUNT=$(($(ls /proc/self/fd | wc -w) - 4))
diff --git a/contrib/scripts/netjail/netjail_setup_internet.sh b/contrib/scripts/netjail/netjail_setup_internet.sh
index de8ef8f15..6ae047274 100755
--- a/contrib/scripts/netjail/netjail_setup_internet.sh
+++ b/contrib/scripts/netjail/netjail_setup_internet.sh
@@ -9,15 +9,25 @@ export PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"
 LOCAL_M=$1
 GLOBAL_N=$2
 
-# TODO: globally known peer?
-
 shift 2
 
 netjail_check $(($LOCAL_M * $GLOBAL_N))
 
-# Starts optionally 'stunserver' on "92.68.150.$(($GLOBAL_N + 1))":
+# Starts optionally an amount of nodes without NAT starting with "92.68.151.1"
+KNOWN=$(netjail_opt '--known' $@)
+KNOWN_NUM=$(netjail_opts '--known' 0 $@)
+
+# Starts optionally 'stunserver' on "92.68.150.254":
 STUN=$(netjail_opt '--stun' $@)
 
+if [ $KNOWN -gt 0 ]; then
+        shift 2
+
+        KNOWN=$KNOWN_NUM
+        
+        netjail_check $(($LOCAL_M * $GLOBAL_N + $KNOWN))
+fi
+
 if [ $STUN -gt 0 ]; then
         netjail_check_bin stunserver
         
@@ -30,19 +40,27 @@ netjail_check_bin $1
 
 LOCAL_GROUP="192.168.15"
 GLOBAL_GROUP="92.68.150"
+KNOWN_GROUP="92.68.151"
 
 CLEANUP=0
-echo "Start [local: $LOCAL_GROUP.0/24, global: $GLOBAL_GROUP.0/24, stun: $STUN]"
+echo "Start [local: $LOCAL_GROUP.0/24, global: $GLOBAL_GROUP.0/16, stun: $STUN]"
 
 NETWORK_NET=$(netjail_print_name "n" $GLOBAL_N $LOCAL_M)
 
 netjail_bridge $NETWORK_NET
 
+for X in $(seq $KNOWN); do
+        KNOWN_NODE=$(netjail_print_name "K" $X)
+
+        netjail_node $KNOWN_NODE
+        netjail_node_link_bridge $KNOWN_NODE $NETWORK_NET "$KNOWN_GROUP.$X" 16
+done
+
 for N in $(seq $GLOBAL_N); do
         ROUTER=$(netjail_print_name "R" $N)
 
         netjail_node $ROUTER 
-        netjail_node_link_bridge $ROUTER $NETWORK_NET "$GLOBAL_GROUP.$N" 24
+        netjail_node_link_bridge $ROUTER $NETWORK_NET "$GLOBAL_GROUP.$N" 16
 
         ROUTER_NET=$(netjail_print_name "r" $N)
 
@@ -72,16 +90,27 @@ KILLING=""
 
 if [ $STUN -gt 0 ]; then
         netjail_node $STUN_NODE
-        netjail_node_link_bridge $STUN_NODE $NETWORK_NET "$GLOBAL_GROUP.254" 24
+        netjail_node_link_bridge $STUN_NODE $NETWORK_NET "$GLOBAL_GROUP.254" 16
 
         netjail_node_exec $STUN_NODE 0 1 stunserver &
         KILLING="$!"
 fi
 
+for X in $(seq $KNOWN); do
+        KNOWN_NODE=$(netjail_print_name "K" $X)
+        INDEX=$(($X - 1))
+        
+        FD_X=$(($INDEX * 2 + 3 + 0))
+        FD_Y=$(($INDEX * 2 + 3 + 1))
+
+        netjail_node_exec $KNOWN_NODE $FD_X $FD_Y $@ &
+        WAITING="$! $WAITING"
+done
+
 for N in $(seq $GLOBAL_N); do
         for M in $(seq $LOCAL_M); do
                 NODE=$(netjail_print_name "N" $N $M)
-                INDEX=$(($LOCAL_M * ($N - 1) + $M - 1))
+                INDEX=$(($LOCAL_M * ($N - 1) + $M - 1 + $KNOWN))
 
                 FD_X=$(($INDEX * 2 + 3 + 0))
                 FD_Y=$(($INDEX * 2 + 3 + 1))
@@ -99,6 +128,13 @@ cleanup() {
                 netjail_node_clear $STUN_NODE
         fi
 
+        for X in $(seq $KNOWN); do
+                KNOWN_NODE=$(netjail_print_name "K" $X)
+                
+                netjail_node_unlink_bridge $KNOWN_NODE $NETWORK_NET
+                netjail_node_clear $KNOWN_NODE
+        done
+
         for N in $(seq $GLOBAL_N); do
                 ROUTER_NET=$(netjail_print_name "r" $N)
 
diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c
index 88b0c5d92..2c30f0b68 100644
--- a/src/dht/gnunet-service-dht_neighbours.c
+++ b/src/dht/gnunet-service-dht_neighbours.c
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     Copyright (C) 2009-2017 GNUnet e.V.
+     Copyright (C) 2009-2017, 2021 GNUnet e.V.
 
      GNUnet is free software: you can redistribute it and/or modify it
      under the terms of the GNU Affero General Public License as published
@@ -877,63 +877,36 @@ get_forward_count (uint32_t hop_count,
 
 
 /**
- * Compute the distance between have and target as a 32-bit value.
+ * Compute the distance between have and target as a 64-bit value.
  * Differences in the lower bits must count stronger than differences
  * in the higher bits.
  *
  * @param target
  * @param have
+ * @param bucket up to which offset are @a target and @a have identical and thus those bits should not be considered
  * @return 0 if have==target, otherwise a number
  *           that is larger as the distance between
  *           the two hash codes increases
  */
-static unsigned int
+static uint64_t
 get_distance (const struct GNUNET_HashCode *target,
-              const struct GNUNET_HashCode *have)
+              const struct GNUNET_HashCode *have,
+              unsigned int bucket)
 {
-  unsigned int bucket;
-  unsigned int msb;
-  unsigned int lsb;
-  unsigned int i;
-
-  /* We have to represent the distance between two 2^9 (=512)-bit
-   * numbers as a 2^5 (=32)-bit number with "0" being used for the
-   * two numbers being identical; furthermore, we need to
-   * guarantee that a difference in the number of matching
-   * bits is always represented in the result.
-   *
-   * We use 2^32/2^9 numerical values to distinguish between
-   * hash codes that have the same LSB bit distance and
-   * use the highest 2^9 bits of the result to signify the
-   * number of (mis)matching LSB bits; if we have 0 matching
-   * and hence 512 mismatching LSB bits we return -1 (since
-   * 512 itself cannot be represented with 9 bits) *//* first, calculate the most significant 9 bits of our
-   * result, aka the number of LSBs */bucket = GNUNET_CRYPTO_hash_matching_bits (target,
-                                             have);
-  /* bucket is now a value between 0 and 512 */
-  if (bucket == 512)
-    return 0;                   /* perfect match */
-  if (bucket == 0)
-    return (unsigned int) -1;   /* LSB differs; use max (if we did the bit-shifting
-                                 * below, we'd end up with max+1 (overflow)) */
-
-  /* calculate the most significant bits of the final result */
-  msb = (512 - bucket) << (32 - 9);
-  /* calculate the 32-9 least significant bits of the final result by
-   * looking at the differences in the 32-9 bits following the
-   * mismatching bit at 'bucket' */
-  lsb = 0;
-  for (i = bucket + 1;
-       (i < sizeof(struct GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9);
+  uint64_t lsb = 0;
+  
+  for (unsigned int i = bucket + 1;
+       (i < sizeof(struct GNUNET_HashCode) * 8) &&
+       (i < bucket + 1 + 64);
        i++)
   {
     if (GNUNET_CRYPTO_hash_get_bit_rtl (target, i) !=
         GNUNET_CRYPTO_hash_get_bit_rtl (have, i))
-      lsb |= (1 << (bucket + 32 - 9 - i));      /* first bit set will be 10,
-                                                 * last bit set will be 31 -- if
-                                                 * i does not reach 512 first... */
+      lsb |= (1LLU << (bucket + 64 - i));      /* first bit set will be 1,
+                                             * last bit set will be 63 -- if
+                                             * i does not reach 512 first... */
   }
-  return msb | lsb;
+  return lsb;
 }
 
 
@@ -1013,33 +986,42 @@ select_peer (const struct GNUNET_HashCode *key,
   unsigned int count;
   unsigned int selected;
   struct PeerInfo *pos;
-  unsigned int dist;
-  unsigned int smallest_distance;
   struct PeerInfo *chosen;
 
   if (hops >= GDS_NSE_get ())
   {
     /* greedy selection (closest peer that is not in bloomfilter) */
-    smallest_distance = UINT_MAX;
+    unsigned int best_bucket = 0;
+    uint64_t best_in_bucket = UINT64_MAX;
+
     chosen = NULL;
     for (bc = 0; bc <= closest_bucket; bc++)
     {
       pos = k_buckets[bc].head;
       count = 0;
-      while ((pos != NULL) && (count < bucket_size))
+      while ( (pos != NULL) &&
+              (count < bucket_size) )
       {
-        if ((NULL == bloom) ||
-            (GNUNET_NO ==
-             GNUNET_CONTAINER_bloomfilter_test (bloom,
-                                                &pos->phash)))
+        unsigned int bucket;
+        uint64_t dist;
+        
+        bucket = GNUNET_CRYPTO_hash_matching_bits (key,
+                                                   &pos->phash);
+        dist = get_distance (key,
+                             &pos->phash,
+                             bucket);
+        if (bucket < best_bucket)
+          continue;
+        if (dist > best_in_bucket)
+          continue;
+        best_bucket = bucket;
+        best_in_bucket = dist;
+        if ( (NULL == bloom) ||
+             (GNUNET_NO ==
+              GNUNET_CONTAINER_bloomfilter_test (bloom,
+                                                 &pos->phash)) )
         {
-          dist = get_distance (key,
-                               &pos->phash);
-          if (dist < smallest_distance)
-          {
-            chosen = pos;
-            smallest_distance = dist;
-          }
+          chosen = pos;
         }
         else
         {
@@ -1052,13 +1034,7 @@ select_peer (const struct GNUNET_HashCode *key,
                                       "# Peers excluded from routing due to Bloomfilter"),
                                     1,
                                     GNUNET_NO);
-          dist = get_distance (key,
-                               &pos->phash);
-          if (dist < smallest_distance)
-          {
-            chosen = NULL;
-            smallest_distance = dist;
-          }
+          chosen = NULL;
         }
         count++;
         pos = pos->next;