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 #define COMM_SIZE 10
  18 #define COMP_SIZE 0
  19
  20 /**
  21  * Finger element.
  22  */
  23 typedef struct finger {
  24   int id;
  25   char* mailbox;
  26 } s_finger_t, *finger_t;
  27
  28 /**
  29  * Node data.
  30  */
  31 typedef struct node {
  32   int id;                                 // my id
  33   char* mailbox;                          // my usual mailbox name
  34   s_finger_t fingers[NB_BITS];            // finger table (fingers[0] is my successor)
  35   int pred_id;                            // predecessor id
  36   char* pred_mailbox;                     // predecessor's mailbox name
  37   int next_finger_to_fix;                 // index of the next finger to fix in fix_fingers()
  38   msg_comm_t comm_receive;                // current communication to receive
  39   xbt_dynar_t comms;                      // current communications being sent
  40 } s_node_t, *node_t;
  41
  42 /**
  43  * Task data
  44  */
  45 typedef struct task_data {
  46   int request_id;
  47   int request_finger;
  48   int answer_id;
  49   const char* answer_to;
  50   const char* issuer_host_name; // used for logging
  51   int successor_id;                             // used when quitting
  52   int pred_id;                                  // used when quitting
  53   // FIXME: remove successor_id and pred_id, request_id is enough
  54 } s_task_data_t, *task_data_t;
  55
  56 static int powers2[NB_BITS];
  57
  58 // utility functions
  59 static void chord_initialize(void);
  60 static int normalize(int id);
  61 static int is_in_interval(int id, int start, int end);
  62 static char* get_mailbox(int host_id);
  63 static void print_finger_table(node_t node);
  64 static void set_finger(node_t node, int finger_index, int id);
  65 static void set_predecessor(node_t node, int predecessor_id);
  66
  67 // process functions
  68 static int node(int argc, char *argv[]);
  69 static void handle_task(node_t node, m_task_t task);
  70
  71 // Chord core
  72 static void create(node_t node);
  73 static void join(node_t node, int known_id);
  74 static void leave(node_t node);
  75 static int find_successor(node_t node, int id);
  76 static int remote_find_successor(node_t node, int ask_to_id, int id);
  77 static int remote_get_predecessor(node_t node, int ask_to_id);
  78 static int closest_preceding_node(node_t node, int id);
  79 static void stabilize(node_t node);
  80 static void notify(node_t node, int predecessor_candidate_id);
  81 static void remote_notify(node_t node, int notify_to, int predecessor_candidate_id);
  82 static void fix_fingers(node_t node);
  83 static void check_predecessor(node_t node);
  84 static void quit_notify(node_t node, int to);
  85
  86 static void chord_initialize(void)
  87 {
  88   // compute the powers of 2 once for all
  89   int pow = 1;
  90   int i;
  91   for (i = 0; i < NB_BITS; i++) {
  92     powers2[i] = pow;
  93     pow = pow << 1;
  94   }
  95 }
  96
  97 /**
  98  * \brief Turns an id into an equivalent id in [0, NB_KEYS[
  99  * \param id an id
 100  * \return the corresponding normalized id
 101  */
 102 static int normalize(int id)
 103 {
 104   // make sure id >= 0
 105   while (id < 0) {
 106     id += NB_KEYS;
 107   }
 108   // make sure id < NB_KEYS
 109   id = id % NB_KEYS;
 110
 111   return id;
 112 }
 113
 114 /**
 115  * \brief Returns whether a id belongs to the interval [start, end].
 116  *
 117  * The parameters are noramlized to make sure they are between 0 and CHORD_NB_KEYS - 1).
 118  * 1 belongs to [62, 3]
 119  * 1 does not belong to [3, 62]
 120  * 63 belongs to [62, 3]
 121  * 63 does not belong to [3, 62]
 122  * 24 belongs to [21, 29]
 123  * 24 does not belong to [29, 21]
 124  *
 125  * \param id id to check
 126  * \param start lower bound
 127  * \param end upper bound
 128  * \return a non-zero value if id in in [start, end]
 129  */
 130 static int is_in_interval(int id, int start, int end)
 131 {
 132   id = normalize(id);
 133   start = normalize(start);
 134   end = normalize(end);
 135
 136   // make sure end >= start and id >= start
 137   if (end < start) {
 138     end += NB_KEYS;
 139   }
 140
 141   if (id < start) {
 142     id += NB_KEYS;
 143   }
 144
 145   return id <= end;
 146 }
 147
 148 /**
 149  * \brief Gets the mailbox name of a host given its chord id.
 150  * \param node_id id of a node
 151  * \return the name of its mailbox
 152  * FIXME: free the memory
 153  */
 154 static char* get_mailbox(int node_id)
 155 {
 156   return bprintf("mailbox%d", node_id);
 157 }
 158
 159 /**
 160  * \brief Displays the finger table of a node.
 161  * \param node a node
 162  */
 163 static void print_finger_table(node_t node)
 164 {
 165   int i;
 166   int pow = 1;
 167   INFO0("My finger table:");
 168   INFO0("Start | Succ ");
 169   for (i = 0; i < NB_BITS; i++) {
 170     INFO2(" %3d  | %3d ", (node->id + pow) % NB_KEYS, node->fingers[i].id);
 171     pow = pow << 1;
 172   }
 173   INFO1("Predecessor: %d", node->pred_id);
 174 }
 175
 176 /**
 177  * \brief Sets a finger of the current node.
 178  * \param node the current node
 179  * \param finger_index index of the finger to set (0 to NB_BITS - 1)
 180  * \param id the id to set for this finger
 181  */
 182 static void set_finger(node_t node, int finger_index, int id)
 183 {
 184   node->fingers[finger_index].id = id;
 185   xbt_free(node->fingers[finger_index].mailbox);
 186   node->fingers[finger_index].mailbox = get_mailbox(id);
 187   INFO2("My new finger #%d is %d", finger_index, id);
 188 }
 189
 190 /**
 191  * \brief Sets the predecessor of the current node.
 192  * \param node the current node
 193  * \param id the id to predecessor, or -1 to unset the predecessor
 194  */
 195 static void set_predecessor(node_t node, int predecessor_id)
 196 {
 197   node->pred_id = predecessor_id;
 198   xbt_free(node->pred_mailbox);
 199
 200   if (predecessor_id != -1) {
 201     node->pred_mailbox = get_mailbox(predecessor_id);
 202   }
 203
 204   INFO1("My new predecessor is %d", predecessor_id);
 205 }
 206
 207 /**
 208  * \brief Node Function
 209  * Arguments:
 210  * - my id
 211  * - the id of a guy I know in the system (except for the first node)
 212  * - the time to sleep before I join (except for the first node)
 213  */
 214 int node(int argc, char *argv[])
 215 {
 216   double init_time = MSG_get_clock();
 217   m_task_t task = NULL;
 218   msg_comm_t comm_send = NULL;
 219   int i;
 220   double deadline;
 221   double next_stabilize_date = init_time + 10;
 222   double next_fix_fingers_date = init_time + 10;
 223   double next_check_predecessor_date = init_time + 10;
 224
 225   xbt_assert0(argc == 3 || argc == 5, "Wrong number of arguments for this node");
 226
 227   // initialize my node
 228   s_node_t node = {0};
 229   node.id = atoi(argv[1]);
 230   node.mailbox = get_mailbox(node.id);
 231   node.next_finger_to_fix = 0;
 232   node.comms = xbt_dynar_new(sizeof(msg_comm_t), NULL);
 233
 234   for (i = 0; i < NB_BITS; i++) {
 235     set_finger(&node, i, node.id);
 236   }
 237
 238   if (argc == 3) { // first ring
 239     deadline = atof(argv[2]);
 240     create(&node);
 241   }
 242   else {
 243     int known_id = atoi(argv[2]);
 244     double sleep_time = atof(argv[3]);
 245     deadline = atof(argv[4]);
 246
 247     // sleep before starting
 248     INFO1("Let's sleep during %f", sleep_time);
 249     MSG_process_sleep(sleep_time);
 250     INFO0("Hey! Let's join the system.");
 251
 252     join(&node, known_id);
 253   }
 254
 255   while (MSG_get_clock() < init_time + deadline) {
 256
 257     // see if some communications are finished
 258     int index;
 259     while ((index = MSG_comm_testany(node.comms)) != -1) {
 260       comm_send = xbt_dynar_get_as(node.comms, index, msg_comm_t);
 261       xbt_dynar_remove_at(node.comms, index, &comm_send);
 262       DEBUG3("Communication %p is finished with status %d, dynar size is now %lu",
 263             comm_send, MSG_comm_get_status(comm_send), xbt_dynar_length(node.comms));
 264       MSG_comm_destroy(comm_send);
 265     }
 266
 267     if (node.comm_receive == NULL) {
 268       task = NULL;
 269       node.comm_receive = MSG_task_irecv(&task, node.mailbox);
 270       // FIXME: do not make MSG_task_irecv() calls from several functions
 271     }
 272
 273     if (!MSG_comm_test(node.comm_receive)) {
 274
 275       // no task was received: make some periodic calls
 276       if (MSG_get_clock() >= next_stabilize_date) {
 277         stabilize(&node);
 278         next_stabilize_date = MSG_get_clock() + 10;
 279       }
 280       else if (MSG_get_clock() >= next_fix_fingers_date) {
 281         fix_fingers(&node);
 282         next_fix_fingers_date = MSG_get_clock() + 10;
 283       }
 284       else if (MSG_get_clock() >= next_check_predecessor_date) {
 285         check_predecessor(&node);
 286         next_check_predecessor_date = MSG_get_clock() + 10;
 287       }
 288       else {
 289         // nothing to do: sleep for a while
 290         MSG_process_sleep(1);
 291       }
 292     }
 293     else {
 294       // a transfer has occured
 295
 296       MSG_error_t status = MSG_comm_get_status(node.comm_receive);
 297       MSG_comm_destroy(node.comm_receive);
 298       node.comm_receive = NULL;
 299
 300       if (status != MSG_OK) {
 301         INFO0("Failed to receive a task. Nevermind.");
 302       }
 303       else {
 304         // the task was successfully received
 305         handle_task(&node, task);
 306       }
 307     }
 308   }
 309
 310   // leave the ring and stop the simulation
 311   leave(&node);
 312   xbt_dynar_free(&node.comms);
 313   xbt_free(node.mailbox);
 314   xbt_free(node.pred_mailbox);
 315   for (i = 0; i < NB_BITS - 1; i++) {
 316     xbt_free(node.fingers[i].mailbox);
 317   }
 318   return 0;
 319 }
 320
 321 /**
 322  * \brief This function is called when the current node receives a task.
 323  * \param node the current node
 324  * \param task the task to handle
 325  */
 326 static void handle_task(node_t node, m_task_t task) {
 327
 328   msg_comm_t comm = NULL;
 329   char* mailbox = NULL;
 330   const char* task_name = MSG_task_get_name(task);
 331   task_data_t task_data = (task_data_t) MSG_task_get_data(task);
 332
 333   if (!strcmp(task_name, "Find Successor")) {
 334     INFO2("Receiving a 'Find Successor' request from %s for id %d",
 335         task_data->issuer_host_name, task_data->request_id);
 336     // is my successor the successor?
 337     if (is_in_interval(task_data->request_id, node->id + 1, node->fingers[0].id)) {
 338       task_data->answer_id = node->fingers[0].id;
 339       MSG_task_set_name(task, "Find Successor Answer");
 340       comm = MSG_task_isend(task, task_data->answer_to);
 341       xbt_dynar_push(node->comms, &comm);
 342       INFO3("Sending back a 'Find Successor Answer' to %s: the successor of %d is %d",
 343             task_data->issuer_host_name,
 344             task_data->request_id, task_data->answer_id);
 345     }
 346     else {
 347       // otherwise, forward the request to the closest preceding finger in my table
 348       int closest = closest_preceding_node(node, task_data->request_id);
 349       INFO2("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d",
 350           task_data->request_id, closest);
 351       mailbox = get_mailbox(closest);
 352       comm = MSG_task_isend(task, mailbox);
 353       xbt_dynar_push(node->comms, &comm);
 354       xbt_free(mailbox);
 355     }
 356   }
 357
 358   else if (!strcmp(task_name, "Get Predecessor")) {
 359     INFO1("Receiving a 'Get Predecessor' request from %s", task_data->issuer_host_name);
 360     task_data->answer_id = node->pred_id;
 361     MSG_task_set_name(task, "Get Predecessor Answer");
 362     comm = MSG_task_isend(task, task_data->answer_to);
 363     xbt_dynar_push(node->comms, &comm);
 364     INFO3("Sending back a 'Get Predecessor Answer' to %s via mailbox '%s': my predecessor is %d",
 365           task_data->issuer_host_name,
 366           task_data->answer_to, task_data->answer_id);
 367   }
 368
 369   else if (!strcmp(task_name, "Notify")) {
 370     // someone is telling me that he may be my new predecessor
 371     INFO1("Receiving a 'Notify' request from %s", task_data->issuer_host_name);
 372     notify(node, task_data->request_id);
 373   }
 374
 375   else if (!strcmp(task_name, "Predecessor Leaving")) {
 376     // my predecessor is about to quit
 377     INFO1("Receiving a 'Predecessor Leaving' message from %s", task_data->issuer_host_name);
 378     // modify my predecessor
 379     set_predecessor(node, task_data->pred_id);
 380     /*TODO :
 381     >> notify my new predecessor
 382     >> send a notify_predecessors !!
 383      */
 384   }
 385
 386   else if (!strcmp(task_name, "Successor Leaving")) {
 387     // my successor is about to quit
 388     INFO1("Receiving a 'Successor Leaving' message from %s", task_data->issuer_host_name);
 389     // modify my successor FIXME : this should be implicit ?
 390     set_finger(node, 0, task_data->successor_id);
 391     /* TODO
 392     >> notify my new successor
 393     >> update my table & predecessors table */
 394   }
 395 }
 396
 397 /**
 398  * \brief Initializes the current node as the first one of the system.
 399  * \param node the current node
 400  */
 401 static void create(node_t node)
 402 {
 403   INFO0("Create a new Chord ring...");
 404   set_predecessor(node, -1); // -1 means that I have no predecessor
 405   print_finger_table(node);
 406 }
 407
 408 /**
 409  * \brief Makes the current node join the ring, knowing the id of a node
 410  * already in the ring
 411  * \param node the current node
 412  * \param known_id id of a node already in the ring
 413  */
 414 static void join(node_t node, int known_id)
 415 {
 416   INFO2("Joining the ring with id %d, knowing node %d", node->id, known_id);
 417   set_predecessor(node, -1); // no predecessor (yet)
 418
 419   int successor_id;
 420   do {
 421     successor_id = remote_find_successor(node, known_id, node->id);
 422     if (successor_id == -1) {
 423       INFO0("I really want to join the ring. Let's try again.");
 424     }
 425   } while (successor_id == -1);
 426
 427   set_finger(node, 0, successor_id);
 428   print_finger_table(node);
 429 }
 430
 431 /**
 432  * \brief Makes the current node quit the system
 433  * \param node the current node
 434  */
 435 static void leave(node_t node)
 436 {
 437   INFO0("Well Guys! I Think it's time for me to quit ;)");
 438   quit_notify(node, 1);  // notify to my successor ( >>> 1 );
 439   quit_notify(node, -1); // notify my predecessor  ( >>> -1);
 440   // TODO ...
 441 }
 442
 443 /*
 444  * \brief Notifies the successor or the predecessor of the current node
 445  * of the departure
 446  * \param node the current node
 447  * \param to 1 to notify the successor, -1 to notify the predecessor
 448  * FIXME: notify both nodes with only one call
 449  */
 450 static void quit_notify(node_t node, int to)
 451 {
 452   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 453   req_data->request_id = node->id;
 454   req_data->successor_id = node->fingers[0].id;
 455   req_data->pred_id = node->pred_id;
 456   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 457   const char *task_name = NULL;
 458   const char* to_mailbox = NULL;
 459   if (to == 1)    // notify my successor
 460   {
 461     to_mailbox = node->fingers[0].mailbox;
 462     INFO2("Telling my Successor %d about my departure via mailbox %s",
 463           node->fingers[0].id, to_mailbox);
 464     task_name = "Predecessor Leaving";
 465
 466   }
 467   else if (to == -1)    // notify my predecessor
 468   {
 469     if (node->pred_id == -1) {
 470       return;
 471     }
 472
 473     to_mailbox = node->pred_mailbox;
 474     INFO2("Telling my Predecessor %d about my departure via mailbox %s",
 475           node->pred_id, to_mailbox);
 476     task_name = "Predecessor Leaving";
 477
 478   }
 479   m_task_t task = MSG_task_create(task_name, COMP_SIZE, COMM_SIZE, req_data);
 480   //char* mailbox = get_mailbox(to_mailbox);
 481   msg_comm_t comm = MSG_task_isend(task, to_mailbox);
 482   xbt_dynar_push(node->comms, &comm);
 483 }
 484
 485 /**
 486  * \brief Makes the current node find the successor node of an id.
 487  * \param node the current node
 488  * \param id the id to find
 489  * \return the id of the successor node, or -1 if the request failed
 490  */
 491 static int find_successor(node_t node, int id)
 492 {
 493   // is my successor the successor?
 494   if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
 495     return node->fingers[0].id;
 496   }
 497
 498   // otherwise, ask the closest preceding finger in my table
 499   int closest = closest_preceding_node(node, id);
 500   return remote_find_successor(node, closest, id);
 501 }
 502
 503 /**
 504  * \brief Asks another node the successor node of an id.
 505  * \param node the current node
 506  * \param ask_to the node to ask to
 507  * \param id the id to find
 508  * \return the id of the successor node, or -1 if the request failed
 509  */
 510 static int remote_find_successor(node_t node, int ask_to, int id)
 511 {
 512   int successor = -1;
 513   int received_answer = 0;
 514   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 515   req_data->request_id = id;
 516   req_data->answer_to =  node->mailbox;
 517   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 518
 519   // send a "Find Successor" request to ask_to_id
 520   INFO2("Sending a 'Find Successor' request to %d for key %d", ask_to, id);
 521   m_task_t task = MSG_task_create("Find Successor", COMP_SIZE, COMM_SIZE, req_data);
 522   MSG_error_t res = MSG_task_send_with_timeout(task, get_mailbox(ask_to), 200);
 523
 524   if (res == MSG_OK) {
 525
 526     // receive the answer
 527     INFO2("Sent a 'Find Successor' request to %d for key %d, waiting for the answer", ask_to, id);
 528
 529     do {
 530       if (node->comm_receive == NULL) {
 531         task = NULL;
 532         node->comm_receive = MSG_task_irecv(&task, node->mailbox);
 533       }
 534
 535       res = MSG_comm_wait(node->comm_receive, 50);
 536
 537       if (res != MSG_OK) {
 538         INFO1("Failed to receive the answer: %d", res);
 539       }
 540       else {
 541         task = MSG_comm_get_task(node->comm_receive);
 542         INFO1("Received a task '%s'", MSG_task_get_name(task));
 543
 544         if (strcmp(MSG_task_get_name(task), "Find Successor Answer")) {
 545           handle_task(node, task);
 546         }
 547         else {
 548           task_data_t ans_data = MSG_task_get_data(task);
 549           successor = ans_data->answer_id;
 550           received_answer = 1;
 551           INFO2("This is the answer to my 'Find Successor' request: the successor of key %d is %d", id, successor);
 552         }
 553         MSG_comm_destroy(node->comm_receive);
 554         node->comm_receive = NULL;
 555 //        MSG_task_destroy(task);
 556       }
 557     } while (!received_answer);
 558   }
 559
 560   return successor;
 561 }
 562
 563 /**
 564  * \brief Asks another node its predecessor.
 565  * \param node the current node
 566  * \param ask_to the node to ask to
 567  * \return the id of its predecessor node, or -1 if the request failed
 568  * (or if the node does not know its predecessor)
 569  */
 570 static int remote_get_predecessor(node_t node, int ask_to)
 571 {
 572   int predecessor_id = -1;
 573   int received_answer = 0;
 574   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 575   req_data->answer_to = node->mailbox;
 576   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 577
 578   // send a "Get Predecessor" request to ask_to_id
 579   INFO1("Sending a 'Get Predecessor' request to %d", ask_to);
 580   m_task_t task = MSG_task_create("Get Predecessor", COMP_SIZE, COMM_SIZE, req_data);
 581   MSG_error_t res = MSG_task_send_with_timeout(task, get_mailbox(ask_to), 200);
 582
 583   if (res == MSG_OK) {
 584
 585     // receive the answer
 586     INFO2("Sent 'Get Predecessor' request to %d, waiting for the answer on my mailbox '%s'", ask_to, req_data->answer_to);
 587
 588     do {
 589       if (node->comm_receive == NULL) { // FIXME simplify this
 590         task = NULL;
 591         node->comm_receive = MSG_task_irecv(&task, node->mailbox);
 592       }
 593
 594       res = MSG_comm_wait(node->comm_receive, 50);
 595
 596       if (res != MSG_OK) {
 597         INFO1("Failed to receive the answer: %d", res);
 598       }
 599       else {
 600         task = MSG_comm_get_task(node->comm_receive);
 601         INFO1("Received a task '%s'", MSG_task_get_name(task));
 602
 603         if (strcmp(MSG_task_get_name(task), "Get Predecessor Answer")) {
 604           handle_task(node, task);
 605         }
 606         else {
 607           task_data_t ans_data = MSG_task_get_data(task);
 608           predecessor_id = ans_data->answer_id;
 609           received_answer = 1;
 610           INFO2("This is the answer to my 'Get Predecessor' request: the predecessor of node %d is %d", ask_to, predecessor_id);
 611         }
 612         MSG_comm_destroy(node->comm_receive);
 613         node->comm_receive = NULL;
 614 //        MSG_task_destroy(task);
 615       }
 616     } while (!received_answer);
 617   }
 618
 619   return predecessor_id;
 620 }
 621
 622 /**
 623  * \brief Returns the closest preceding finger of an id
 624  * with respect to the finger table of the current node.
 625  * \param node the current node
 626  * \param id the id to find
 627  * \return the closest preceding finger of that id
 628  */
 629 int closest_preceding_node(node_t node, int id)
 630 {
 631   int i;
 632   for (i = NB_BITS - 1; i >= 0; i--) {
 633     if (is_in_interval(node->fingers[i].id, node->id + 1, id - 1)) {
 634       return node->fingers[i].id;
 635     }
 636   }
 637   return node->id;
 638 }
 639
 640 /**
 641  * \brief This function is called periodically. It checks the immediate
 642  * successor of the current node.
 643  * \param node the current node
 644  */
 645 static void stabilize(node_t node)
 646 {
 647   INFO0("Stabilizing node");
 648
 649   // get the predecessor of my immediate successor
 650   int candidate_id;
 651   int successor_id = node->fingers[0].id;
 652   if (successor_id != node->id) {
 653     candidate_id = remote_get_predecessor(node, successor_id);
 654   }
 655   else {
 656     candidate_id = node->pred_id;
 657   }
 658
 659   // this node is a candidate to become my new successor
 660   if (candidate_id != -1
 661       && is_in_interval(candidate_id, node->id + 1, successor_id - 1)) {
 662     set_finger(node, 0, candidate_id);
 663   }
 664   if (successor_id != node->id) {
 665     remote_notify(node, successor_id, node->id);
 666   }
 667 }
 668
 669 /**
 670  * \brief Notifies the current node that its predecessor may have changed.
 671  * \param node the current node
 672  * \param candidate_id the possible new predecessor
 673  */
 674 static void notify(node_t node, int predecessor_candidate_id) {
 675
 676   if (node->pred_id == -1
 677     || is_in_interval(predecessor_candidate_id, node->pred_id + 1, node->id - 1)) {
 678
 679     set_predecessor(node, predecessor_candidate_id);
 680     print_finger_table(node);
 681   }
 682   else {
 683     INFO1("I don't have to change my predecessor to %d", predecessor_candidate_id);
 684   }
 685 }
 686
 687 /**
 688  * \brief Notifies a remote node that its predecessor may have changed.
 689  * \param node the current node
 690  * \param notify_id id of the node to notify
 691  * \param candidate_id the possible new predecessor
 692  */
 693 static void remote_notify(node_t node, int notify_id, int predecessor_candidate_id) {
 694
 695   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 696   req_data->request_id = predecessor_candidate_id;
 697   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 698
 699   // send a "Notify" request to notify_id
 700   INFO1("Sending a 'Notify' request to %d", notify_id);
 701   m_task_t task = MSG_task_create("Notify", COMP_SIZE, COMM_SIZE, req_data);
 702   char* mailbox = get_mailbox(notify_id);
 703   msg_comm_t comm = MSG_task_isend(task, mailbox);
 704   xbt_dynar_push(node->comms, &comm);
 705   xbt_free(mailbox);
 706 }
 707
 708 /**
 709  * \brief This function is called periodically.
 710  * It refreshes the finger table of the current node.
 711  * \param node the current node
 712  */
 713 static void fix_fingers(node_t node) {
 714
 715   INFO0("Fixing fingers");
 716   int i = node->next_finger_to_fix;
 717   int id = find_successor(node, node->id + powers2[i]);
 718   if (id != -1) {
 719
 720     if (id != node->fingers[i].id) {
 721       set_finger(node, i, id);
 722       print_finger_table(node);
 723     }
 724     node->next_finger_to_fix = (i + 1) % NB_BITS;
 725   }
 726 }
 727
 728 /**
 729  * \brief This function is called periodically.
 730  * It checks whether the predecessor has failed
 731  * \param node the current node
 732  */
 733 static void check_predecessor(node_t node)
 734 {
 735   INFO0("Checking whether my predecessor is alive");
 736   // TODO
 737 }
 738
 739 /**
 740  * \brief Main function.
 741  */
 742 int main(int argc, char *argv[])
 743 {
 744   if (argc < 3) {
 745     printf("Usage: %s platform_file deployment_file\n", argv[0]);
 746     printf("example: %s ../msg_platform.xml chord.xml\n", argv[0]);
 747     exit(1);
 748   }
 749
 750   const char* platform_file = argv[1];
 751   const char* application_file = argv[2];
 752
 753   chord_initialize();
 754
 755   MSG_global_init(&argc, argv);
 756   MSG_set_channel_number(0);
 757   MSG_create_environment(platform_file);
 758
 759   MSG_function_register("node", node);
 760   MSG_launch_application(application_file);
 761
 762   MSG_error_t res = MSG_main();
 763   INFO1("Simulation time: %g", MSG_get_clock());
 764
 765   MSG_clean();
 766
 767   if (res == MSG_OK)
 768     return 0;
 769   else
 770     return 1;
 771 }