examples/msg/kademlia/node.c

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