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