examples/deprecated/msg/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/msg.h"
   9
  10 #include <stdio.h> /* snprintf */
  11
  12 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_kademlia_node, "Messages specific for this msg 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
  22   node->id = node_id;
  23   node->table = routing_table_init(node_id);
  24   snprintf(node->mailbox, MAILBOX_NAME_SIZE - 1, "%u", node_id);
  25   node->find_node_failed = 0;
  26   node->find_node_success = 0;
  27
  28   node->task_received = NULL;
  29   node->receive_comm = NULL;
  30
  31   return node;
  32 }
  33
  34 /* @brief Node destructor  */
  35 void node_free(node_t node)
  36 {
  37   routing_table_free(node->table);
  38   xbt_free(node);
  39 }
  40
  41 /** @brief Updates/Puts the node id unsigned into our routing table
  42   * @param node Our node data
  43   * @param id The id of the node we need to add unsigned into our routing table
  44   */
  45 void node_routing_table_update(const_node_t node, unsigned int id)
  46 {
  47   const_routing_table_t table = node->table;
  48   //retrieval of the bucket in which the should be
  49   const_bucket_t bucket = routing_table_find_bucket(table, id);
  50
  51   //check if the id is already in the bucket.
  52   unsigned int id_pos = bucket_find_id(bucket, id);
  53
  54   if (id_pos == -1) {
  55     /* We check if the bucket is full or not. If it is, we evict old offline elements */
  56     if (xbt_dynar_length(bucket->nodes) < BUCKET_SIZE) {
  57       //TODO: this is not really very efficient. Maybe we should use something else than dynars ?
  58       xbt_dynar_unshift(bucket->nodes, &id);
  59       XBT_VERB("I'm adding to my routing table %08x", id);
  60     } else {
  61       /* TODO: we need to evict the old elements: that's why this function is in "node" instead of "routing table".
  62        * This is not implemented yet. */
  63     }
  64   } else {
  65     //We push to the front of the dynar the element.
  66     unsigned int element = xbt_dynar_get_as(bucket->nodes, id_pos, unsigned int);
  67     xbt_dynar_remove_at(bucket->nodes, id_pos, NULL);
  68     xbt_dynar_unshift(bucket->nodes, &element);
  69     XBT_VERB("I'm updating %08x", element);
  70   }
  71 }
  72
  73 /** @brief Finds the closest nodes to the node given.
  74   * @param node : our node
  75   * @param destination_id : the id of the guy we are trying to find
  76   */
  77 answer_t node_find_closest(const_node_t node, unsigned int destination_id)
  78 {
  79   int i;
  80   answer_t answer = answer_init(destination_id);
  81   /* We find the corresponding bucket for the id */
  82   const_bucket_t bucket = routing_table_find_bucket(node->table, destination_id);
  83   int bucket_id = bucket->id;
  84   xbt_assert((bucket_id <= IDENTIFIER_SIZE), "Bucket found has a wrong identifier");
  85   /* So, we copy the contents of the bucket unsigned into our result dynar */
  86   answer_add_bucket(bucket, answer);
  87
  88   /* However, if we don't have enough elements in our bucket, we NEED to include at least "BUCKET_SIZE" elements
  89    * (if, of course, we know at least "BUCKET_SIZE" elements. So we're going to look unsigned into the other buckets.
  90    */
  91   for (i = 1; answer->size < BUCKET_SIZE && ((bucket_id - i > 0) || (bucket_id + i < IDENTIFIER_SIZE)); i++) {
  92     /* We check the previous buckets */
  93     if (bucket_id - i >= 0) {
  94       const_bucket_t bucket_p = &node->table->buckets[bucket_id - i];
  95       answer_add_bucket(bucket_p, answer);
  96     }
  97     /* We check the next buckets */
  98     if (bucket_id + i <= IDENTIFIER_SIZE) {
  99       const_bucket_t bucket_n = &node->table->buckets[bucket_id + i];
 100       answer_add_bucket(bucket_n, answer);
 101     }
 102   }
 103   /* We sort the array by XOR distance */
 104   answer_sort(answer);
 105   /* We trim the array to have only BUCKET_SIZE or less elements */
 106   answer_trim(answer);
 107
 108   return answer;
 109 }
 110
 111 /**@brief Returns an identifier which is in a specific bucket of a routing table
 112  * @param id id of the routing table owner
 113  * @param prefix id of the bucket where we want that identifier to be
 114  */
 115 unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix)
 116 {
 117   if (prefix == 0) {
 118     return 0;
 119   } else {
 120     return (1U << ((unsigned int)(prefix - 1))) ^ id;
 121   }
 122 }
 123
 124 /** @brief Returns the prefix of an identifier.
 125   * The prefix is the id of the bucket in which the remote identifier xor our identifier should be stored.
 126   * @param id : big unsigned int id to test
 127   * @param nb_bits : key size
 128   */
 129 unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits)
 130 {
 131   unsigned int size = sizeof(unsigned int) * 8;
 132   for (unsigned int j = 0; j < size; j++) {
 133     if (((id >> (size - 1 - j)) & 0x1) != 0) {
 134       return nb_bits - (j);
 135     }
 136   }
 137   return 0;
 138 }
 139
 140 /** @brief Gets the mailbox name of a host given its identifier */
 141 void get_node_mailbox(unsigned int id, char *mailbox)
 142 {
 143   snprintf(mailbox, MAILBOX_NAME_SIZE - 1, "%u", id);
 144 }
 145
 146 /** Constructor, build a new contact information. */
 147 node_contact_t node_contact_new(unsigned int id, unsigned int distance)
 148 {
 149   node_contact_t contact = xbt_new(s_node_contact_t, 1);
 150
 151   contact->id = id;
 152   contact->distance = distance;
 153
 154   return contact;
 155 }
 156
 157 /** Builds a contact information from a contact information */
 158 node_contact_t node_contact_copy(const_node_contact_t node_contact)
 159 {
 160   node_contact_t contact = xbt_new(s_node_contact_t, 1);
 161
 162   contact->id = node_contact->id;
 163   contact->distance = node_contact->distance;
 164
 165   return contact;
 166 }
 167
 168 /** Destructor */
 169 void node_contact_free(node_contact_t contact)
 170 {
 171   xbt_free(contact);
 172 }