examples/msg/kademlia/node.c

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