examples/c/dht-kademlia/node.c

   1 /* Copyright (c) 2010-2020. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "node.h"
   7 #include "routing_table.h"
   8 #include "simgrid/comm.h"
   9
  10 #include <stdio.h> /* snprintf */
  11
  12 XBT_LOG_NEW_DEFAULT_CATEGORY(dht_kademlia_node, "Messages specific for this example");
  13
  14 /** @brief Initialization of a node
  15  * @param node_id the id of the node
  16  * @return the node created
  17  */
  18 node_t node_init(unsigned int node_id)
  19 {
  20   node_t node             = xbt_new(s_node_t, 1);
  21   node->id                = node_id;
  22   node->table             = routing_table_init(node_id);
  23   node->mailbox           = get_node_mailbox(node_id);
  24   node->find_node_failed  = 0;
  25   node->find_node_success = 0;
  26
  27   node->received_msg = NULL;
  28   node->receive_comm = NULL;
  29
  30   return node;
  31 }
  32
  33 /* @brief Node destructor  */
  34 void node_free(node_t node)
  35 {
  36   routing_table_free(node->table);
  37   xbt_free(node);
  38 }
  39
  40 /**
  41  * @brief Tries to join the network
  42  * @param node node data
  43  * @param id_known id of the node I know in the network.
  44  */
  45 unsigned int join(node_t node, unsigned int id_known)
  46 {
  47   unsigned int i;
  48   unsigned int got_answer = 0;
  49
  50   sg_mailbox_t mailbox = get_node_mailbox(node->id);
  51
  52   /* Add the guy we know to our routing table and ourselves. */
  53   routing_table_update(node, node->id);
  54   routing_table_update(node, id_known);
  55
  56   /* First step: Send a "FIND_NODE" request to the node we know */
  57   send_find_node(node, id_known, node->id);
  58   do {
  59     if (node->receive_comm == NULL)
  60       node->receive_comm = sg_mailbox_get_async(mailbox, &node->received_msg);
  61
  62     if (sg_comm_test(node->receive_comm)) {
  63       XBT_DEBUG("Received an answer from the node I know.");
  64       got_answer = 1;
  65       // retrieve the node list and ping them.
  66       const kademlia_message_t msg = (kademlia_message_t)(node->received_msg);
  67       const s_answer_t* node_list  = msg->answer;
  68       if (node_list != NULL) {
  69         node_contact_t contact;
  70         xbt_dynar_foreach (node_list->nodes, i, contact)
  71           routing_table_update(node, contact->id);
  72         node->received_msg = NULL;
  73       } else {
  74         handle_find_node(node, msg);
  75       }
  76       answer_free(msg->answer);
  77       free(msg);
  78       node->receive_comm = NULL;
  79     } else {
  80       sg_actor_sleep_for(1);
  81     }
  82   } while (got_answer == 0);
  83
  84   /* Second step: Send a FIND_NODE to a a random node in buckets */
  85   unsigned int bucket_id = routing_table_find_bucket(node->table, id_known)->id;
  86   xbt_assert(bucket_id <= IDENTIFIER_SIZE);
  87   for (i = 0; ((bucket_id > i) || (bucket_id + i) <= IDENTIFIER_SIZE) && i < JOIN_BUCKETS_QUERIES; i++) {
  88     if (bucket_id > i) {
  89       unsigned int id_in_bucket = get_id_in_prefix(node->id, bucket_id - i);
  90       find_node(node, id_in_bucket, 0);
  91     }
  92     if (bucket_id + i <= IDENTIFIER_SIZE) {
  93       unsigned int id_in_bucket = get_id_in_prefix(node->id, bucket_id + i);
  94       find_node(node, id_in_bucket, 0);
  95     }
  96   }
  97   return got_answer;
  98 }
  99
 100 /** @brief Send a "FIND_NODE" to a node
 101  * @param node sender node data
 102  * @param id node we are querying
 103  * @param destination node we are trying to find.
 104  */
 105 void send_find_node(const_node_t node, unsigned int id, unsigned int destination)
 106 {
 107   /* Gets the mailbox to send to */
 108   sg_mailbox_t mailbox = get_node_mailbox(id);
 109   /* Build the message */
 110   kademlia_message_t msg = new_message(node->id, destination, NULL, node->mailbox, sg_host_self_get_name());
 111   sg_comm_t comm         = sg_mailbox_put_init(mailbox, msg, COMM_SIZE);
 112   sg_comm_detach(comm, free_message);
 113   XBT_VERB("Asking %u for its closest nodes", id);
 114 }
 115
 116 /**
 117  * Sends to the best "KADEMLIA_ALPHA" nodes in the "node_list" array a "FIND_NODE" request, to ask them for their best
 118  * nodes
 119  */
 120 unsigned int send_find_node_to_best(const_node_t node, const_answer_t node_list)
 121 {
 122   unsigned int i           = 0;
 123   unsigned int j           = 0;
 124   unsigned int destination = node_list->destination_id;
 125   while (j < KADEMLIA_ALPHA && i < node_list->size) {
 126     /* We need to have at most "KADEMLIA_ALPHA" requests each time, according to the protocol */
 127     /* Gets the node we want to send the query to */
 128     const s_node_contact_t* node_to_query = xbt_dynar_get_as(node_list->nodes, i, node_contact_t);
 129     if (node_to_query->id != node->id) { /* No need to query ourselves */
 130       send_find_node(node, node_to_query->id, destination);
 131       j++;
 132     }
 133     i++;
 134   }
 135   return i;
 136 }
 137
 138 /** @brief Updates/Puts the node id unsigned into our routing table
 139  * @param node Our node data
 140  * @param id The id of the node we need to add unsigned into our routing table
 141  */
 142 void routing_table_update(const_node_t node, unsigned int id)
 143 {
 144   const_routing_table_t table = node->table;
 145   // retrieval of the bucket in which the should be
 146   const_bucket_t bucket = routing_table_find_bucket(table, id);
 147
 148   // check if the id is already in the bucket.
 149   unsigned int id_pos = bucket_find_id(bucket, id);
 150
 151   if (id_pos == -1) {
 152     /* We check if the bucket is full or not. If it is, we evict an old element */
 153     if (xbt_dynar_length(bucket->nodes) >= BUCKET_SIZE)
 154       xbt_dynar_pop(bucket->nodes, NULL);
 155
 156     xbt_dynar_unshift(bucket->nodes, &id);
 157     XBT_VERB("I'm adding to my routing table %08x", id);
 158   } else {
 159     // We push to the front of the dynar the element.
 160     unsigned int element = xbt_dynar_get_as(bucket->nodes, id_pos, unsigned int);
 161     xbt_dynar_remove_at(bucket->nodes, id_pos, NULL);
 162     xbt_dynar_unshift(bucket->nodes, &element);
 163     XBT_VERB("I'm updating %08x", element);
 164   }
 165 }
 166
 167 /** @brief Finds the closest nodes to the node given.
 168  * @param node : our node
 169  * @param destination_id : the id of the guy we are trying to find
 170  */
 171 answer_t find_closest(const_node_t node, unsigned int destination_id)
 172 {
 173   int i;
 174   answer_t answer = answer_init(destination_id);
 175   /* We find the corresponding bucket for the id */
 176   const_bucket_t bucket = routing_table_find_bucket(node->table, destination_id);
 177   int bucket_id         = bucket->id;
 178   xbt_assert((bucket_id <= IDENTIFIER_SIZE), "Bucket found has a wrong identifier");
 179   /* So, we copy the contents of the bucket unsigned into our result dynar */
 180   answer_add_bucket(bucket, answer);
 181
 182   /* However, if we don't have enough elements in our bucket, we NEED to include at least "BUCKET_SIZE" elements
 183    * (if, of course, we know at least "BUCKET_SIZE" elements. So we're going to look unsigned into the other buckets.
 184    */
 185   for (i = 1; answer->size < BUCKET_SIZE && ((bucket_id - i > 0) || (bucket_id + i < IDENTIFIER_SIZE)); i++) {
 186     /* We check the previous buckets */
 187     if (bucket_id - i >= 0) {
 188       const_bucket_t bucket_p = &node->table->buckets[bucket_id - i];
 189       answer_add_bucket(bucket_p, answer);
 190     }
 191     /* We check the next buckets */
 192     if (bucket_id + i <= IDENTIFIER_SIZE) {
 193       const_bucket_t bucket_n = &node->table->buckets[bucket_id + i];
 194       answer_add_bucket(bucket_n, answer);
 195     }
 196   }
 197   /* We sort the array by XOR distance */
 198   answer_sort(answer);
 199   /* We trim the array to have only BUCKET_SIZE or less elements */
 200   answer_trim(answer);
 201
 202   return answer;
 203 }
 204
 205 unsigned int find_node(node_t node, unsigned int id_to_find, unsigned int count_in_stats)
 206 {
 207   unsigned int i = 0;
 208   unsigned int queries;
 209   unsigned int answers;
 210   unsigned int destination_found = 0;
 211   unsigned int nodes_added       = 0;
 212   double global_timeout          = simgrid_get_clock() + FIND_NODE_GLOBAL_TIMEOUT;
 213   unsigned int steps             = 0;
 214
 215   /* First we build a list of who we already know */
 216   answer_t node_list = find_closest(node, id_to_find);
 217   xbt_assert((node_list != NULL), "node_list incorrect");
 218
 219   XBT_DEBUG("Doing a FIND_NODE on %08x", id_to_find);
 220
 221   /* Ask the nodes on our list if they   have information about the node we are trying to find */
 222   sg_mailbox_t mailbox = get_node_mailbox(node->id);
 223   do {
 224     answers        = 0;
 225     queries        = send_find_node_to_best(node, node_list);
 226     nodes_added    = 0;
 227     double timeout = simgrid_get_clock() + FIND_NODE_TIMEOUT;
 228     steps++;
 229     double time_beginreceive = simgrid_get_clock();
 230
 231     do {
 232       if (node->receive_comm == NULL)
 233         node->receive_comm = sg_mailbox_get_async(mailbox, &node->received_msg);
 234
 235       if (sg_comm_test(node->receive_comm)) {
 236         // Figure out if we received an answer or something else
 237         const kademlia_message_t msg = (kademlia_message_t)(node->received_msg);
 238
 239         // Check if what we have received is what we are looking for.
 240         if (msg->answer != NULL && msg->answer->destination_id == id_to_find) {
 241           // Handle the answer
 242           routing_table_update(node, msg->sender_id);
 243           node_contact_t contact;
 244           xbt_dynar_foreach (node_list->nodes, i, contact)
 245             routing_table_update(node, contact->id);
 246
 247           answers++;
 248
 249           nodes_added = answer_merge(node_list, msg->answer);
 250           XBT_DEBUG("Received an answer from %s (%s) with %lu nodes on it", sg_mailbox_get_name(msg->answer_to),
 251                     msg->issuer_host_name, xbt_dynar_length(msg->answer->nodes));
 252         } else {
 253           if (msg->answer != NULL) {
 254             routing_table_update(node, msg->sender_id);
 255             XBT_DEBUG("Received a wrong answer for a FIND_NODE");
 256           } else {
 257             handle_find_node(node, msg);
 258           }
 259           // Update the timeout if we didn't have our answer
 260           timeout += simgrid_get_clock() - time_beginreceive;
 261           time_beginreceive = simgrid_get_clock();
 262         }
 263         answer_free(msg->answer);
 264         free(msg);
 265         node->receive_comm = NULL;
 266       } else {
 267         sg_actor_sleep_for(1);
 268       }
 269     } while (simgrid_get_clock() < timeout && answers < queries);
 270     destination_found = answer_destination_found(node_list);
 271   } while (!destination_found && (nodes_added > 0 || answers == 0) && simgrid_get_clock() < global_timeout &&
 272            steps < MAX_STEPS);
 273   if (destination_found) {
 274     if (count_in_stats)
 275       node->find_node_success++;
 276     if (queries > 4)
 277       XBT_VERB("FIND_NODE on %08x success in %u steps", id_to_find, steps);
 278     routing_table_update(node, id_to_find);
 279   } else {
 280     if (count_in_stats) {
 281       node->find_node_failed++;
 282       XBT_VERB("%08x not found in %u steps", id_to_find, steps);
 283     }
 284   }
 285   answer_free(node_list);
 286   return destination_found;
 287 }
 288
 289 /** @brief Does a pseudo-random lookup for someone in the system
 290  * @param node caller node data
 291  */
 292 void random_lookup(node_t node)
 293 {
 294   unsigned int id_to_look = RANDOM_LOOKUP_NODE; // Totally random.
 295   /* TODO: Use some pseudorandom generator. */
 296   XBT_DEBUG("I'm doing a random lookup");
 297   find_node(node, id_to_look, 1);
 298 }
 299
 300 /** @brief Handles the answer to an incoming "find_node" message */
 301 void handle_find_node(const_node_t node, const_kademlia_message_t msg)
 302 {
 303   routing_table_update(node, msg->sender_id);
 304   XBT_VERB("Received a FIND_NODE from %s (%s), he's trying to find %08x", sg_mailbox_get_name(msg->answer_to),
 305            msg->issuer_host_name, msg->destination_id);
 306   // Building the msg to send
 307   kademlia_message_t answer = new_message(node->id, msg->destination_id, find_closest(node, msg->destination_id),
 308                                           node->mailbox, sg_host_self_get_name());
 309   // Sending the msg
 310   sg_comm_t comm = sg_mailbox_put_init(msg->answer_to, answer, COMM_SIZE);
 311   sg_comm_detach(comm, &free_message);
 312 }
 313
 314 /**@brief Returns an identifier which is in a specific bucket of a routing table
 315  * @param id id of the routing table owner
 316  * @param prefix id of the bucket where we want that identifier to be
 317  */
 318 unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix)
 319 {
 320   if (prefix == 0) {
 321     return 0;
 322   } else {
 323     return (1U << (prefix - 1)) ^ id;
 324   }
 325 }
 326
 327 /** @brief Returns the prefix of an identifier.
 328  * The prefix is the id of the bucket in which the remote identifier xor our identifier should be stored.
 329  * @param id : big unsigned int id to test
 330  * @param nb_bits : key size
 331  */
 332 unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits)
 333 {
 334   unsigned int size = sizeof(unsigned int) * 8;
 335   for (unsigned int j = 0; j < size; j++) {
 336     if (((id >> (size - 1 - j)) & 0x1) != 0) {
 337       return nb_bits - (j);
 338     }
 339   }
 340   return 0;
 341 }
 342
 343 /** @brief Gets the mailbox name of a host given its identifier */
 344 sg_mailbox_t get_node_mailbox(unsigned int id)
 345 {
 346   char mailbox_name[MAILBOX_NAME_SIZE];
 347   snprintf(mailbox_name, MAILBOX_NAME_SIZE - 1, "%u", id);
 348   return sg_mailbox_by_name(mailbox_name);
 349 }
 350
 351 /** Constructor, build a new contact information. */
 352 node_contact_t node_contact_new(unsigned int id, unsigned int distance)
 353 {
 354   node_contact_t contact = xbt_new(s_node_contact_t, 1);
 355
 356   contact->id       = id;
 357   contact->distance = distance;
 358
 359   return contact;
 360 }
 361
 362 /** Builds a contact information from a contact information */
 363 node_contact_t node_contact_copy(const_node_contact_t node_contact)
 364 {
 365   node_contact_t contact = xbt_new(s_node_contact_t, 1);
 366
 367   contact->id       = node_contact->id;
 368   contact->distance = node_contact->distance;
 369
 370   return contact;
 371 }
 372
 373 /** Destructor */
 374 void node_contact_free(node_contact_t contact)
 375 {
 376   xbt_free(contact);
 377 }