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