examples/msg/chord/chord.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 <stdio.h>
   9 #include "msg/msg.h"
  10 #include "xbt/log.h"
  11 #include "xbt/asserts.h"
  12 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_chord,
  13                              "Messages specific for this msg example");
  14
  15 #define NB_BITS 6
  16 #define NB_KEYS 64
  17
  18 /**
  19  * Finger element.
  20  */
  21 typedef struct finger {
  22   int id;
  23   char* mailbox;
  24 } s_finger_t, *finger_t;
  25
  26 /**
  27  * Node data.
  28  */
  29 typedef struct node {
  30   int id;                                 // my id
  31   char* mailbox;                          // my usual mailbox name
  32   s_finger_t fingers[NB_BITS];            // finger table (fingers[0] is my successor)
  33   int pred_id;                            // predecessor id
  34   char* pred_mailbox;                     // predecessor's mailbox name
  35   int next_finger_to_fix;                 // index of the next finger to fix in fix_fingers()
  36   xbt_dynar_t comms;                      // current communications pending
  37 } s_node_t, *node_t;
  38
  39 /**
  40  * Task data
  41  */
  42 typedef struct task_data {
  43   int request_id;
  44   int request_finger;
  45   int answer_id;
  46   const char* answer_to;
  47   const char* issuer_host_name; // used for logging
  48   int successor_id;                             // used when quitting
  49   int pred_id;                                  // used when quitting
  50   // FIXME: remove successor_id and pred_id, request_id is enough
  51 } s_task_data_t, *task_data_t;
  52
  53 static int powers2[NB_BITS];
  54
  55 // utility functions
  56 static void chord_initialize(void);
  57 static int normalize(int id);
  58 static int is_in_interval(int id, int start, int end);
  59 static char* get_mailbox(int host_id);
  60 static void print_finger_table(node_t node);
  61 static void set_finger(node_t node, int finger_index, int id);
  62 static void set_predecessor(node_t node, int predecessor_id);
  63
  64 // process functions
  65 static int node(int argc, char *argv[]);
  66
  67 // Chord core
  68 static void create(node_t node);
  69 static void join(node_t node, int known_id);
  70 static void leave(node_t node);
  71 static int find_successor(node_t node, int id);
  72 static int remote_find_successor(node_t node, int ask_to_id, int id);
  73 static int remote_get_predecessor(node_t node, int ask_to_id);
  74 static int closest_preceding_node(node_t node, int id);
  75 static void stabilize(node_t node);
  76 static void notify(node_t node, int predecessor_candidate_id);
  77 static void remote_notify(node_t node, int notify_to, int predecessor_candidate_id);
  78 static void fix_fingers(node_t node);
  79 static void check_predecessor(node_t node);
  80 static void quit_notify(node_t node, int to);
  81
  82 // not implemented yet
  83 //static void remote_move_keys(node_t node, int take_from_id);
  84
  85 // deprecated
  86 /*
  87 static void bootstrap(node_t node, int known_id);
  88 static int find_predecessor(node_t node, int id);
  89 static int remote_find_predecessor(node_t node, int ask_to_id, int id);
  90 static int remote_closest_preceding_finger(int ask_to_id, int id);
  91 static void notify_predecessors(node_t node);
  92 static void initialize_finger_table(node_t data, int known_id);
  93 static void update_finger_table(node_t node, int candidate_id, int finger_index);
  94 static void remote_update_finger_table(node_t node, int ask_to_id, int candidate_id, int finger_index);
  95 static void notify_node_joined(node_t node, int new_node_id);
  96 static void remote_notify_node_joined(node_t node, int notify_id);
  97 */
  98
  99 static void chord_initialize(void)
 100 {
 101   // compute the powers of 2 once for all
 102   int pow = 1;
 103   int i;
 104   for (i = 0; i < NB_BITS; i++) {
 105     powers2[i] = pow;
 106     pow = pow << 1;
 107   }
 108 }
 109
 110 /**
 111  * \brief Turns an id into an equivalent id in [0, NB_KEYS[
 112  * \param id an id
 113  * \return the corresponding normalized id
 114  */
 115 static int normalize(int id)
 116 {
 117   // make sure id >= 0
 118   while (id < 0) {
 119     id += NB_KEYS;
 120   }
 121   // make sure id < NB_KEYS
 122   id = id % NB_KEYS;
 123
 124   return id;
 125 }
 126
 127 /**
 128  * \brief Returns whether a id belongs to the interval [start, end].
 129  *
 130  * The parameters are noramlized to make sure they are between 0 and CHORD_NB_KEYS - 1).
 131  * 1 belongs to [62, 3]
 132  * 1 does not belong to [3, 62]
 133  * 63 belongs to [62, 3]
 134  * 63 does not belong to [3, 62]
 135  * 24 belongs to [21, 29]
 136  * 24 does not belong to [29, 21]
 137  *
 138  * \param id id to check
 139  * \param start lower bound
 140  * \param end upper bound
 141  * \return a non-zero value if id in in [start, end]
 142  */
 143 static int is_in_interval(int id, int start, int end)
 144 {
 145   id = normalize(id);
 146   start = normalize(start);
 147   end = normalize(end);
 148
 149   // make sure end >= start and id >= start
 150   if (end < start) {
 151     end += NB_KEYS;
 152   }
 153
 154   if (id < start) {
 155     id += NB_KEYS;
 156   }
 157
 158   return id <= end;
 159 }
 160
 161 /**
 162  * \brief Gets the mailbox name of a host given its chord id.
 163  * \param node_id id of a node
 164  * \return the name of its mailbox
 165  * FIXME: free the memory
 166  */
 167 static char* get_mailbox(int node_id)
 168 {
 169   return bprintf("mailbox%d", node_id);
 170 }
 171
 172 /**
 173  * \brief Displays the finger table of a node.
 174  * \param node a node
 175  */
 176 static void print_finger_table(node_t node)
 177 {
 178   int i;
 179   int pow = 1;
 180   INFO0("My finger table:");
 181   INFO0("Start | Succ ");
 182   for (i = 0; i < NB_BITS; i++) {
 183     INFO2(" %3d  | %3d ", (node->id + pow) % NB_KEYS, node->fingers[i].id);
 184     pow = pow << 1;
 185   }
 186   INFO1("Predecessor: %d", node->pred_id);
 187 }
 188
 189 /**
 190  * \brief Sets a finger of the current node.
 191  * \param node the current node
 192  * \param finger_index index of the finger to set (0 to NB_BITS - 1)
 193  * \param id the id to set for this finger
 194  */
 195 static void set_finger(node_t node, int finger_index, int id)
 196 {
 197   node->fingers[finger_index].id = id;
 198   xbt_free(node->fingers[finger_index].mailbox);
 199   node->fingers[finger_index].mailbox = get_mailbox(id);
 200   INFO2("My new finger #%d is %d", finger_index, id);
 201 }
 202
 203 /**
 204  * \brief Sets the predecessor of the current node.
 205  * \param node the current node
 206  * \param id the id to predecessor, or -1 to unset the predecessor
 207  */
 208 static void set_predecessor(node_t node, int predecessor_id)
 209 {
 210   node->pred_id = predecessor_id;
 211   xbt_free(node->pred_mailbox);
 212
 213   if (predecessor_id != -1) {
 214     node->pred_mailbox = get_mailbox(predecessor_id);
 215   }
 216
 217   INFO1("My new predecessor is %d", predecessor_id);
 218 }
 219
 220 /**
 221  * \brief Node Function
 222  * Arguments:
 223  * - my id
 224  * - the id of a guy I know in the system (except for the first node)
 225  * - the time to sleep before I join (except for the first node)
 226  */
 227 int node(int argc, char *argv[])
 228 {
 229   double init_time = MSG_get_clock();
 230   m_task_t task = NULL;
 231   msg_comm_t comm_send = NULL;
 232   msg_comm_t comm_receive = NULL;
 233   int i;
 234   char* mailbox = NULL;
 235   double deadline;
 236   double next_stabilize_date = init_time + 10;
 237   double next_fix_fingers_date = init_time + 10;
 238   double next_check_predecessor_date = init_time + 10;
 239
 240   xbt_assert0(argc == 3 || argc == 5, "Wrong number of arguments for this node");
 241
 242   // initialize my node
 243   s_node_t node = {0};
 244   node.id = atoi(argv[1]);
 245   node.mailbox = get_mailbox(node.id);
 246   node.next_finger_to_fix = 0;
 247   node.comms = xbt_dynar_new(sizeof(msg_comm_t), NULL);
 248
 249   for (i = 0; i < NB_BITS; i++) {
 250     set_finger(&node, i, node.id);
 251   }
 252
 253   if (argc == 3) { // first ring
 254     deadline = atof(argv[2]);
 255     create(&node);
 256   }
 257   else {
 258     int known_id = atoi(argv[2]);
 259     double sleep_time = atof(argv[3]);
 260     deadline = atof(argv[4]);
 261
 262     // sleep before starting
 263     INFO1("Let's sleep during %f", sleep_time);
 264     MSG_process_sleep(sleep_time);
 265     INFO0("Hey! Let's join the system.");
 266
 267     join(&node, known_id);
 268   }
 269
 270   while (MSG_get_clock() < init_time + deadline) {
 271
 272     // see if some communications are finished
 273     int index;
 274     while ((index = MSG_comm_testany(node.comms)) != -1) {
 275       comm_send = xbt_dynar_get_as(node.comms, index, msg_comm_t);
 276       xbt_dynar_remove_at(node.comms, index, &comm_send);
 277       MSG_comm_destroy(comm_send);
 278     }
 279
 280     if (comm_receive == NULL) {
 281       task = NULL;
 282       comm_receive = MSG_task_irecv(&task, node.mailbox);
 283     }
 284
 285     if (!MSG_comm_test(comm_receive)) {
 286
 287       // no task was received: make some periodic calls
 288       if (MSG_get_clock() >= next_stabilize_date) {
 289         stabilize(&node);
 290         next_stabilize_date = MSG_get_clock() + 10;
 291       }
 292       else if (MSG_get_clock() >= next_fix_fingers_date) {
 293         fix_fingers(&node);
 294         next_fix_fingers_date = MSG_get_clock() + 10;
 295       }
 296       else if (MSG_get_clock() >= next_check_predecessor_date) {
 297         check_predecessor(&node);
 298         next_check_predecessor_date = MSG_get_clock() + 10;
 299       }
 300       else {
 301         // nothing to do: sleep for a while
 302         MSG_process_sleep(5);
 303       }
 304     }
 305     else {
 306       // a task was received
 307
 308       MSG_comm_destroy(comm_receive);
 309       comm_receive = NULL;
 310       const char* task_name = MSG_task_get_name(task);
 311       task_data_t task_data = (task_data_t) MSG_task_get_data(task);
 312
 313       if (!strcmp(task_name, "Find Successor")) {
 314         INFO2("Receiving a 'Find Successor' Request from %s for id %d",
 315               task_data->issuer_host_name, task_data->request_id);
 316         // is my successor the successor?
 317         if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) {
 318           task_data->answer_id = node.fingers[0].id;
 319           MSG_task_set_name(task, "Find Successor Answer");
 320           INFO3("Sending back a 'Find Successor Answer' to %s: the successor of %d is %d",
 321                 task_data->issuer_host_name, task_data->request_id, task_data->answer_id);
 322           comm_send = MSG_task_isend(task, task_data->answer_to);
 323           xbt_dynar_push(node.comms, &comm_send);
 324         }
 325         else {
 326           // otherwise, forward the request to the closest preceding finger in my table
 327           int closest = closest_preceding_node(&node, task_data->request_id);
 328           INFO2("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d",
 329                 task_data->request_id, closest);
 330           mailbox = get_mailbox(closest);
 331           comm_send = MSG_task_isend(task, mailbox);
 332           xbt_dynar_push(node.comms, &comm_send);
 333           xbt_free(mailbox);
 334         }
 335       }
 336
 337       else if (!strcmp(task_name, "Get Predecessor")) {
 338         INFO1("Receiving a 'Get Predecessor' Request from %s", task_data->issuer_host_name);
 339         task_data->answer_id = node.pred_id;
 340         MSG_task_set_name(task, "Get Predecessor Answer");
 341         INFO2("Sending back a 'Get Predecessor Answer' to %s: my predecessor is %d",
 342               task_data->issuer_host_name, task_data->answer_id);
 343         comm_send = MSG_task_isend(task, task_data->answer_to);
 344         xbt_dynar_push(node.comms, &comm_send);
 345       }
 346       /*
 347       else if (!strcmp(task_name, "Find Predecessor")) {
 348         INFO2("Receiving a 'Find Predecessor' Request from %s for id %d", task_data->issuer_host_name, task_data->request_id);
 349         // am I the predecessor?
 350         if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) {
 351           task_data->answer_id = node.id;
 352           MSG_task_set_name(task, "Find Predecessor Answer");
 353           INFO3("Sending back a 'Find Predecessor' Answer to %s: the predecessor of %d is %d", task_data->issuer_host_name, task_data->request_id, task_data->answer_id);
 354           comm = MSG_task_isend(task, task_data->answer_to);
 355           xbt_dynar_push(node.comms, &comm);
 356         }
 357         else {
 358           // otherwise, forward the request to the closest preceding finger in my table
 359           int closest = closest_preceding_node(&node, task_data->request_id);
 360           INFO2("Forwarding 'Find Predecessor' request for id %d to my closest preceding finger %d", task_data->request_id, closest);
 361           mailbox = get_mailbox(closest);
 362           comm = MSG_task_isend(task, mailbox);
 363           xbt_dynar_push(node.comms, &comm);
 364           xbt_free(mailbox);
 365         }
 366       }
 367       */
 368
 369       /*
 370       else if (!strcmp(task_name, "Notify Node Joined")) {
 371         // someone may be my new neighboor
 372         INFO1("Receiving a 'Notify Node Joine' request from %s", task_data->issuer_host_name);
 373         notify_node_joined(&node, task_data->request_id);
 374       }
 375       else if (!strcmp(task_name, "Update Finger")) {
 376         // someone is telling me that he may be my new finger
 377         INFO1("Receiving an 'Update Finger' request from %s", task_data->issuer_host_name);
 378         update_finger_table(&node, task_data->request_id, task_data->request_finger);
 379       }
 380       */
 381       else if (!strcmp(task_name, "Notify")) {
 382         // someone is telling me that he may be my new predecessor
 383         INFO1("Receiving a 'Notify' request from %s", task_data->issuer_host_name);
 384         notify(&node, task_data->request_id);
 385       }
 386       else if (!strcmp(task_name, "Predecessor Leaving")) {
 387         // my predecessor is about to quit
 388         INFO1("Receiving a 'Predecessor Leaving' message from %s", task_data->issuer_host_name);
 389         // modify my predecessor
 390         set_predecessor(&node, task_data->pred_id);
 391         /*TODO :
 392           >> notify my new predecessor
 393           >> send a notify_predecessors !!
 394          */
 395       }
 396       else if (!strcmp(task_name, "Successor Leaving")) {
 397         // my successor is about to quit
 398         INFO1("Receiving a 'Successor Leaving' message from %s", task_data->issuer_host_name);
 399         // modify my successor FIXME : this should be implicit ?
 400         set_finger(&node, 0, task_data->successor_id);
 401         /* TODO
 402           >> notify my new successor
 403           >> update my table & predecessors table */
 404       }
 405     }
 406   }
 407
 408   // leave the ring and stop the simulation
 409   leave(&node);
 410   xbt_dynar_free(&node.comms);
 411   xbt_free(node.mailbox);
 412   xbt_free(node.pred_mailbox);
 413   for (i = 0; i < NB_BITS - 1; i++) {
 414     xbt_free(node.fingers[i].mailbox);
 415   }
 416   return 0;
 417 }
 418
 419 /**
 420  * \brief Initializes the current node as the first one of the system.
 421  * \param node the current node
 422  */
 423 static void create(node_t node)
 424 {
 425   INFO0("Create a new Chord ring...");
 426   set_predecessor(node, -1); // -1 means that I have no predecessor
 427   print_finger_table(node);
 428 }
 429
 430 /**
 431  * \brief Makes the current node join the ring, knowing the id of a node
 432  * already in the ring
 433  * \param node the current node
 434  * \param known_id id of a node already in the ring
 435  */
 436 static void join(node_t node, int known_id)
 437 {
 438   INFO2("Joining the ring with id %d, knowing node %d", node->id, known_id);
 439   set_predecessor(node, -1); // no predecessor (yet)
 440
 441   int successor_id;
 442   do {
 443     successor_id = remote_find_successor(node, known_id, node->id);
 444     INFO0("My 'Find Successor' request has failed, let's try again");
 445   } while (successor_id == -1);
 446
 447   set_finger(node, 0, successor_id);
 448   print_finger_table(node);
 449 }
 450
 451 /**
 452  * \brief Notifies the current node that a node has just joined the network.
 453  * \param node the current node
 454  * \param new_node_id id of the new node in the network
 455  */
 456 /*
 457 static void notify_node_joined(node_t node, int new_node_id)
 458 {
 459   INFO1("A new node %d has joined the network, let's see if it is a neighboor", new_node_id);
 460   if (is_in_interval(new_node_id, node->id + 1, node->fingers[0].id - 1)) {
 461     // new_node_id is my new successor
 462     set_finger(node, 0, new_node_id);
 463     bootstrap(node, new_node_id);
 464   }
 465
 466   if (is_in_interval(new_node_id, node->pred_id + 1, node->id - 1)) {
 467     // new_node_id is my new predecessor
 468     set_predecessor(node, new_node_id);
 469     bootstrap(node, new_node_id);
 470   }
 471 }
 472 */
 473
 474 /**
 475  * \brief Notifies a remote node that the current node has just joined
 476  * the network.
 477  * \param node the current node
 478  * \param notify_id id of the remote node to notify
 479  */
 480 /*
 481 static void remote_notify_node_joined(node_t node, int notify_id)
 482 {
 483   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 484   req_data->request_id = node->id;
 485   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 486
 487   // send a "Notify" request to notify_id
 488   INFO2("Sending a 'Notify' request to %d because I have joined the network with id %d", notify_id, node->id);
 489   m_task_t task = MSG_task_create("Notify", 1000, 5000, req_data);
 490   char* mailbox = get_mailbox(notify_id);
 491   msg_comm_t comm = MSG_task_isend(task, mailbox);
 492   xbt_dynar_push(node->comms, &comm);
 493   xbt_free(mailbox);
 494 }
 495 */
 496
 497 /**
 498 * \brief Let the current node send queries to fill in its own finger table.
 499 * \param node the current node
 500 * \param ask_to_id id of a node to send queries to
 501 */
 502 /*
 503 static void bootstrap(node_t node, int ask_to_id)
 504 {
 505   INFO0("Filling my finger table");
 506   int i, pred_id, succ_id;
 507   int pow = 1;
 508
 509   for (i = 0; i < NB_BITS; i++)
 510   {
 511     pred_id = remote_find_successor(node, ask_to_id, pow);
 512     do {
 513       succ_id = pred_id;
 514       pred_id = remote_find_predecessor(node, pred_id, pred_id);
 515     } while (pred_id >= pow);
 516
 517     pow = pow << 1;
 518     set_finger(node, i, succ_id);
 519   }
 520 }
 521 */
 522
 523 /**
 524  * \brief Makes the current node quit the system
 525  * \param node the current node
 526  */
 527 static void leave(node_t node)
 528 {
 529   INFO0("Well Guys! I Think it's time for me to quit ;)");
 530   quit_notify(node, 1);  // notify to my successor ( >>> 1 );
 531   quit_notify(node, -1); // notify my predecessor  ( >>> -1);
 532   // TODO ...
 533 }
 534
 535 /*
 536  * \brief Notifies the successor or the predecessor of the current node
 537  * of the departure
 538  * \param node the current node
 539  * \param to 1 to notify the successor, -1 to notify the predecessor
 540  * FIXME: notify both nodes with only one call
 541  */
 542 static void quit_notify(node_t node, int to)
 543 {
 544   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 545   req_data->request_id = node->id;
 546   req_data->successor_id = node->fingers[0].id;
 547   req_data->pred_id = node->pred_id;
 548   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 549   const char *task_name = NULL;
 550   const char* to_mailbox = NULL;
 551   if (to == 1)    // notify my successor
 552   {
 553     to_mailbox = node->fingers[0].mailbox;
 554     INFO2("Telling my Successor %d about my departure via mailbox %s",
 555           node->fingers[0].id, to_mailbox);
 556     task_name = "Predecessor Leaving";
 557
 558   }
 559   else if (to == -1)    // notify my predecessor
 560   {
 561     if (node->pred_id == -1) {
 562       return;
 563     }
 564
 565     to_mailbox = node->pred_mailbox;
 566     INFO2("Telling my Predecessor %d about my departure via mailbox %s",
 567           node->pred_id, to_mailbox);
 568     task_name = "Predecessor Leaving";
 569
 570   }
 571   m_task_t task = MSG_task_create(task_name, 1000, 5000, req_data);
 572   //char* mailbox = get_mailbox(to_mailbox);
 573   msg_comm_t comm = MSG_task_isend(task, to_mailbox);
 574   xbt_dynar_push(node->comms, &comm);
 575 }
 576
 577 /*
 578  * \brief Initializes my finger table, knowing the id of a node already in the system.
 579  * \param node the current node
 580  * \param known_id id of a node already in the system
 581  */
 582 /*
 583 static void initialize_finger_table(node_t node, int known_id)
 584 {
 585   int my_id = node->id;
 586   int i;
 587   int pow = 1; // 2^i
 588
 589   INFO0("Initializing my finger table...");
 590
 591   // ask known_id who is my immediate successor
 592   node->fingers[0].id = remote_find_successor(node, known_id, my_id + 1);
 593   node->fingers[0].mailbox = get_mailbox(node->fingers[0].id);
 594
 595   // find all other fingers
 596   for (i = 0; i < NB_BITS - 1; i++) {
 597
 598     pow = pow << 1; // equivalent to pow = pow * 2
 599     if (is_in_interval(my_id + pow, my_id, node->fingers[i].id - 1)) {
 600       // I already have the info for this finger
 601       node->fingers[i + 1].id = node->fingers[i].id;
 602     }
 603     else {
 604       // I don't have the info, ask the only guy I know
 605       node->fingers[i + 1].id = remote_find_successor(node, known_id, my_id + pow);
 606     }
 607     node->fingers[i + 1].mailbox = get_mailbox(node->fingers[i + 1].id);
 608   }
 609
 610   node->pred_id = find_predecessor(node, node->id);
 611   node->pred_mailbox = get_mailbox(node->pred_id);
 612
 613   INFO0("Finger table initialized!");
 614   print_finger_table(node);
 615 }
 616 */
 617
 618 /**
 619  * \brief Notifies some nodes that the current node may have became their finger.
 620  * \param node the current node, which has just joined the system
 621  */
 622 /*
 623 static void notify_predecessors(node_t node)
 624 {
 625   int i, pred_id;
 626   int pow = 1;
 627   for (i = 0; i < NB_BITS; i++) {
 628     // find the closest node whose finger #i can be me
 629     pred_id = find_predecessor(node, node->id - pow + 1); // note: no "+1" in the article!
 630     if (pred_id != node->id) {
 631       remote_update_finger_table(node, pred_id, node->id, i);
 632     }
 633     pow = pow << 1; // pow = pow * 2
 634   }
 635 }
 636 */
 637
 638 /**
 639  * \brief Tells the current node that a node may have became its new finger.
 640  * \param node the current node
 641  * \param candidate_id id of the node that may be a new finger of the current node
 642  * \param finger_index index of the finger to update
 643  */
 644 /*
 645 static void update_finger_table(node_t node, int candidate_id, int finger_index)
 646 {
 647   int pow = 1;
 648   int i;
 649   for (i = 0; i < finger_index; i++) {
 650     pow = pow << 1;
 651   }
 652
 653   //  if (is_in_interval(candidate_id, node->id + pow, node->fingers[finger_index].id - 1)) {
 654   if (is_in_interval(candidate_id, node->id, node->fingers[finger_index].id - 1)) {
 655 //    INFO3("Candidate %d is between %d and %d!", candidate_id, node->id + pow, node->fingers[finger_index].id - 1);
 656     // candidate_id is my new finger
 657     set_finger(node, finger_index, candidate_id);
 658     print_finger_table(node);
 659
 660     if (node->pred_id != node->id) { // FIXME: is this necessary?
 661       // my predecessor may be concerned too
 662       remote_update_finger_table(node, node->pred_id, candidate_id, finger_index);
 663     }
 664   }
 665 }
 666 */
 667
 668 /**
 669  * \brief Tells a remote node that a node may have became its new finger.
 670  * \param ask_to_id id of the remote node to update
 671  * \param candidate_id id of the node that may be a new finger of the remote node
 672  * \param finger_index index of the finger to update
 673  */
 674 /*
 675 static void remote_update_finger_table(node_t node, int ask_to_id, int candidate_id, int finger_index)
 676 {
 677   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 678   req_data->request_id = candidate_id;
 679   req_data->request_finger = finger_index;
 680   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 681
 682   // send a "Update Finger" request to ask_to_id
 683   INFO3("Sending an 'Update Finger' request to %d: his finger #%d may be %d now", ask_to_id, finger_index, candidate_id);
 684   m_task_t task = MSG_task_create("Update Finger", 1000, 5000, req_data);
 685   char* mailbox = get_mailbox(ask_to_id);
 686   msg_comm_t comm = MSG_task_isend(task, mailbox);
 687   xbt_dynar_push(node->comms, &comm);
 688   xbt_free(mailbox);
 689 }
 690 */
 691
 692 /**
 693  * \brief Makes the current node find the successor node of an id.
 694  * \param node the current node
 695  * \param id the id to find
 696  * \return the id of the successor node, or -1 if the request failed
 697  */
 698 static int find_successor(node_t node, int id)
 699 {
 700   // is my successor the successor?
 701   if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
 702     return node->fingers[0].id;
 703   }
 704
 705   // otherwise, ask the closest preceding finger in my table
 706   int closest = closest_preceding_node(node, id);
 707   return remote_find_successor(node, closest, id);
 708 }
 709
 710 /**
 711  * \brief Asks another node the successor node of an id.
 712  * \param node the current node
 713  * \param ask_to the node to ask to
 714  * \param id the id to find
 715  * \return the id of the successor node, or -1 if the request failed
 716  */
 717 static int remote_find_successor(node_t node, int ask_to, int id)
 718 {
 719   int successor = -1;
 720   s_task_data_t req_data;
 721   char* mailbox = bprintf("%s Find Successor", node->mailbox);
 722   req_data.request_id = id;
 723   req_data.answer_to = mailbox;
 724   req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
 725
 726   // send a "Find Successor" request to ask_to_id
 727   INFO2("Sending a 'Find Successor' request to %d for key %d", ask_to, id);
 728   m_task_t task = MSG_task_create("Find Successor", 1000, 5000, &req_data);
 729   MSG_error_t res = MSG_task_send_with_timeout(task, get_mailbox(ask_to), 20);
 730   if (res == MSG_OK) {
 731
 732     // receive the answer
 733     task = NULL;
 734     res = MSG_task_receive_with_timeout(&task, req_data.answer_to, 20);
 735
 736     if (res == MSG_OK) {
 737
 738       task_data_t ans_data;
 739       ans_data = MSG_task_get_data(task);
 740       successor = ans_data->answer_id;
 741       INFO2("Received the answer to my 'Find Successor' request: the successor of key %d is %d", id, successor);
 742     }
 743   }
 744
 745   xbt_free(mailbox);
 746   return successor;
 747 }
 748
 749 /**
 750  * \brief Asks another node its predecessor.
 751  * \param node the current node
 752  * \param ask_to the node to ask to
 753  * \return the id of its predecessor node, or -1 if the request failed
 754  * (or if the node does not know its predecessor)
 755  */
 756 static int remote_get_predecessor(node_t node, int ask_to)
 757 {
 758   int predecessor_id = -1;
 759   s_task_data_t req_data;
 760   char* mailbox = bprintf("%s Get Predecessor", node->mailbox);
 761   req_data.answer_to = mailbox;
 762   req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
 763
 764   // send a "Get Predecessor" request to ask_to_id
 765   INFO1("Sending a 'Get Predecessor' request to %d", ask_to);
 766   m_task_t task = MSG_task_create("Get Predecessor", 1000, 5000, &req_data);
 767   MSG_error_t res = MSG_task_send_with_timeout(task, get_mailbox(ask_to), 20);
 768
 769   if (res == MSG_OK) {
 770
 771     // receive the answer
 772     task = NULL;
 773     res = MSG_task_receive_with_timeout(&task, req_data.answer_to, 20);
 774
 775     if (res == MSG_OK) {
 776
 777       task_data_t ans_data;
 778       ans_data = MSG_task_get_data(task);
 779       predecessor_id = ans_data->answer_id;
 780       INFO2("Received the answer to my 'Get Predecessor' request: the predecessor of node %d is %d", ask_to, predecessor_id);
 781     }
 782   }
 783
 784   xbt_free(mailbox);
 785   return predecessor_id;
 786 }
 787
 788 /**
 789  * \brief Makes the current node find the predecessor node of an id.
 790  * \param node the current node
 791  * \param id the id to find
 792  * \return the id of the predecessor node
 793  */
 794 /*
 795 static int find_predecessor(node_t node, int id)
 796 {
 797   if (node->id == node->fingers[0].id) {
 798     // I am the only node in the system
 799     return node->id;
 800   }
 801
 802   if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
 803     return node->id;
 804   }
 805   int ask_to = closest_preceding_node(node, id);
 806   return remote_find_predecessor(node, ask_to, id);
 807 }
 808 */
 809
 810 /**
 811  * \brief Asks another node the predecessor node of an id.
 812  * \param node the current node
 813  * \param ask_to the node to ask to
 814  * \param id the id to find
 815  * \return the id of the predecessor node
 816  */
 817 /*
 818 static int remote_find_predecessor(node_t node, int ask_to, int id)
 819 {
 820   s_task_data_t req_data;
 821   char* mailbox = bprintf("%s Find Predecessor", node->mailbox);
 822   req_data.request_id = id;
 823   req_data.answer_to = mailbox;
 824   req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
 825
 826   // send a "Find Predecessor" request to ask_to
 827   INFO2("Sending a 'Find Predecessor' request to %d for key %d", ask_to, id);
 828   m_task_t task = MSG_task_create("Find Predecessor", 1000, 5000, &req_data);
 829   MSG_task_send(task, get_mailbox(ask_to));
 830
 831   // receive the answer
 832   task = NULL;
 833   MSG_task_receive(&task, req_data.answer_to);
 834   task_data_t ans_data;
 835   ans_data = MSG_task_get_data(task);
 836   int predecessor = ans_data->answer_id;
 837   xbt_free(mailbox);
 838   INFO2("Received the answer to my 'Find Predecessor' request: the predecessor of key %d is %d", id, predecessor);
 839
 840   return predecessor;
 841 }
 842 */
 843
 844 /**
 845  * \brief Returns the closest preceding finger of an id
 846  * with respect to the finger table of the current node.
 847  * \param node the current node
 848  * \param id the id to find
 849  * \return the closest preceding finger of that id
 850  */
 851 int closest_preceding_node(node_t node, int id)
 852 {
 853   int i;
 854   for (i = NB_BITS - 1; i >= 0; i--) {
 855     if (is_in_interval(node->fingers[i].id, node->id + 1, id - 1)) {
 856       return node->fingers[i].id;
 857     }
 858   }
 859   return node->id;
 860 }
 861
 862 /**
 863  * \brief This function is called periodically. It checks the immediate
 864  * successor of the current node.
 865  * \param node the current node
 866  */
 867 static void stabilize(node_t node)
 868 {
 869   INFO0("Stabilizing node");
 870
 871   // get the predecessor of my immediate successor
 872   int candidate_id;
 873   int successor_id = node->fingers[0].id;
 874   if (successor_id != node->id) {
 875     candidate_id = remote_get_predecessor(node, successor_id);
 876   }
 877   else {
 878     candidate_id = node->pred_id;
 879   }
 880
 881   // this node is a candidate to become my new successor
 882   if (candidate_id != -1
 883       && is_in_interval(candidate_id, node->id + 1, successor_id - 1)) {
 884     set_finger(node, 0, candidate_id);
 885   }
 886   if (successor_id != node->id) {
 887     remote_notify(node, successor_id, node->id);
 888   }
 889 }
 890
 891 /**
 892  * \brief Notifies the current node that its predecessor may have changed.
 893  * \param node the current node
 894  * \param candidate_id the possible new predecessor
 895  */
 896 static void notify(node_t node, int predecessor_candidate_id) {
 897
 898   if (node->pred_id == -1
 899     || is_in_interval(predecessor_candidate_id, node->pred_id + 1, node->id - 1)) {
 900
 901     set_predecessor(node, predecessor_candidate_id);
 902     print_finger_table(node);
 903   }
 904   else {
 905     INFO1("I don't have to change my predecessor to %d", predecessor_candidate_id);
 906   }
 907 }
 908
 909 /**
 910  * \brief Notifies a remote node that its predecessor may have changed.
 911  * \param node the current node
 912  * \param notify_id id of the node to notify
 913  * \param candidate_id the possible new predecessor
 914  */
 915 static void remote_notify(node_t node, int notify_id, int predecessor_candidate_id) {
 916
 917   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 918   req_data->request_id = predecessor_candidate_id;
 919   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 920
 921   // send a "Notify" request to notify_id
 922   INFO1("Sending a 'Notify' request to %d", notify_id);
 923   m_task_t task = MSG_task_create("Notify", 1000, 5000, req_data);
 924   char* mailbox = get_mailbox(notify_id);
 925   msg_comm_t comm = MSG_task_isend(task, mailbox);
 926   xbt_dynar_push(node->comms, &comm);
 927   xbt_free(mailbox);
 928 }
 929
 930 /**
 931  * \brief This function is called periodically.
 932  * It refreshes the finger table of the current node.
 933  * \param node the current node
 934  */
 935 static void fix_fingers(node_t node) {
 936
 937   INFO0("Fixing fingers");
 938   int i = node->next_finger_to_fix;
 939   int id = find_successor(node, node->id + powers2[i]);
 940   if (id != -1) {
 941
 942     if (id != node->fingers[i].id) {
 943       set_finger(node, i, id);
 944       print_finger_table(node);
 945     }
 946     node->next_finger_to_fix = (i + 1) % NB_BITS;
 947   }
 948 }
 949
 950 /**
 951  * \brief This function is called periodically.
 952  * It checks whether the predecessor has failed
 953  * \param node the current node
 954  */
 955 static void check_predecessor(node_t node)
 956 {
 957   INFO0("Checking whether my predecessor is alive");
 958   // TODO
 959 }
 960
 961 /**
 962  * \brief Main function.
 963  */
 964 int main(int argc, char *argv[])
 965 {
 966   if (argc < 3) {
 967     printf("Usage: %s platform_file deployment_file\n", argv[0]);
 968     printf("example: %s ../msg_platform.xml chord.xml\n", argv[0]);
 969     exit(1);
 970   }
 971
 972   const char* platform_file = argv[1];
 973   const char* application_file = argv[2];
 974
 975   chord_initialize();
 976
 977   MSG_global_init(&argc, argv);
 978   MSG_set_channel_number(0);
 979   MSG_create_environment(platform_file);
 980
 981   MSG_function_register("node", node);
 982   MSG_launch_application(application_file);
 983
 984   MSG_error_t res = MSG_main();
 985   INFO1("Simulation time: %g", MSG_get_clock());
 986
 987   MSG_clean();
 988
 989   if (res == MSG_OK)
 990     return 0;
 991   else
 992     return 1;
 993 }