2 /* Copyright (c) 2010. The SimGrid Team.
3 * All rights reserved. */
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. */
11 #include "xbt/asserts.h"
12 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_chord,
13 "Messages specific for this msg example");
21 typedef struct finger {
24 } s_finger_t, *finger_t;
32 s_finger_t fingers[NB_BITS]; // finger table (fingers[0] is my successor)
33 int pred_id; // predecessor id
35 xbt_dynar_t comms; // current communications to finish
41 typedef struct task_data {
45 const char* answer_to;
46 const char* issuer_host_name; // used for logging
47 int successor_id; // used when quitting
48 int pred_id; // used when quitting
49 } s_task_data_t, *task_data_t;
52 static int normalize(int id);
53 static int is_in_interval(int id, int start, int end);
54 static char* get_mailbox(int host_id);
55 static void print_finger_table(node_t node);
58 static int node(int argc, char *argv[]);
61 static void initialize_first_node(node_t node);
62 static void initialize_finger_table(node_t data, int known_id);
63 static void join(node_t node, int known_id);
64 static void leave(node_t node);
67 static int find_successor(node_t node, int id);
68 static int remote_find_successor(node_t node, int ask_to_id, int id);
69 static int find_predecessor(node_t node, int id);
70 static int remote_find_predecessor(node_t node, int ask_to_id, int id);
71 static int closest_preceding_finger(node_t node, int id);
72 static int remote_closest_preceding_finger(int ask_to_id, int id);
73 static void notify_predecessors(node_t node);
74 static void remote_move_keys(node_t node, int take_from_id);
75 static void update_finger_table(node_t node, int candidate_id, int finger_index);
76 static void remote_update_finger_table(node_t node, int ask_to_id, int candidate_id, int finger_index);
77 static void notify(node_t node, int predecessor_candidate_id);
78 static void remote_notify(node_t node, int notify_to, int predecessor_candidate_id);
79 static void stabilize(node_t node);
80 static void quit_notify(node_t node, int to);
83 * \brief Turns an id into an equivalent id in [0, NB_KEYS[
85 * \return the corresponding normalized id
87 static int normalize(int id) {
93 // make sure id < NB_KEYS
100 * \brief Returns whether a id belongs to the interval [start, end].
102 * The parameters are noramlized to make sure they are between 0 and CHORD_NB_KEYS - 1).
103 * 1 belongs to [62, 3]
104 * 1 does not belong to [3, 62]
105 * 63 belongs to [62, 3]
106 * 63 does not belong to [3, 62]
107 * 24 belongs to [21, 29]
108 * 24 does not belong to [29, 21]
110 * \param id id to check
111 * \param start lower bound
112 * \param end upper bound
113 * \return a non-zero value if id in in [start, end]
115 static int is_in_interval(int id, int start, int end) {
118 start = normalize(start);
119 end = normalize(end);
121 // make sure end >= start and id >= start
134 * \brief Gets the mailbox name of a host given its chord id.
135 * \param node_id id of a node
136 * \return the name of its mailbox
137 * FIXME: free the memory
139 static char* get_mailbox(int node_id) {
141 return bprintf("mailbox%d", node_id);
145 * \brief Displays the finger table of a node.
148 static void print_finger_table(node_t node) {
152 INFO0("My finger table:");
153 INFO0("Start | Succ ");
154 for (i = 0; i < NB_BITS; i++) {
155 INFO2(" %3d | %3d ", (node->id + pow) % NB_KEYS, node->fingers[i].id);
158 INFO1("Predecessor: %d", node->pred_id);
162 * \brief Node Function
165 * - the id of a guy I know in the system (except for the first node)
166 * - the time to sleep before I join (except for the first node)
168 int node(int argc, char *argv[])
170 double init_time = MSG_get_clock();
171 msg_comm_t comm = NULL;
176 xbt_assert0(argc == 3 || argc == 5, "Wrong number of arguments for this node");
178 // initialize my node
180 node.id = atoi(argv[1]);
181 node.mailbox = get_mailbox(node.id);
182 node.comms = xbt_dynar_new(sizeof(msg_comm_t), NULL);
185 if (argc == 3) { // first ring
186 initialize_first_node(&node);
187 deadline = atof(argv[2]);
190 int known_id = atoi(argv[2]);
191 double sleep_time = atof(argv[3]);
192 deadline = atof(argv[4]);
194 // sleep before starting
195 INFO1("Let's sleep >>%f", sleep_time);
196 MSG_process_sleep(sleep_time);
197 INFO0("Hey! Let's join the system.");
199 join(&node, known_id);
202 while ((MSG_get_clock( )- init_time) < deadline) {
206 xbt_dynar_foreach(node.comms, cursor, comm) {
207 if (MSG_comm_test(comm)) { // FIXME: try with MSG_comm_testany instead
208 xbt_dynar_cursor_rm(node.comms, &cursor);
209 MSG_comm_destroy(comm);
213 m_task_t task = NULL;
214 MSG_error_t res = MSG_task_receive_with_timeout(&task, node.mailbox,45); // FIXME >> find the right timeout !!
216 if(res == MSG_OK) // else check deadline condition and keep waiting for a task
220 const char* task_name = MSG_task_get_name(task);
221 task_data_t task_data = (task_data_t) MSG_task_get_data(task);
223 if (!strcmp(task_name, "Find Successor")) {
224 INFO2("Receiving a 'Find Successor' Request from %s for id %d", task_data->issuer_host_name, task_data->request_id);
225 // is my successor the successor?
226 if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) {
227 task_data->answer_id = node.fingers[0].id;
228 MSG_task_set_name(task, "Find Successor Answer");
229 INFO3("Sending back a 'Find Successor' Answer to %s: the successor of %d is %d", task_data->issuer_host_name, task_data->request_id, task_data->answer_id);
230 comm = MSG_task_isend(task, task_data->answer_to);
231 xbt_dynar_push(node.comms, &comm);
234 // otherwise, forward the request to the closest preceding finger in my table
235 int closest = closest_preceding_finger(&node, task_data->request_id);
236 INFO2("Forwarding 'Find Successor' request for id %d to my closest preceding finger %d", task_data->request_id, closest);
237 mailbox = get_mailbox(closest);
238 comm = MSG_task_isend(task, mailbox);
239 xbt_dynar_push(node.comms, &comm);
244 else if (!strcmp(task_name, "Find Predecessor")) {
245 INFO2("Receiving a 'Find Predecessor' Request from %s for id %d", task_data->issuer_host_name, task_data->request_id);
246 // am I the predecessor?
247 if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) {
248 task_data->answer_id = node.id;
249 MSG_task_set_name(task, "Find Predecessor Answer");
250 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);
251 comm = MSG_task_isend(task, task_data->answer_to);
252 xbt_dynar_push(node.comms, &comm);
255 // otherwise, forward the request to the closest preceding finger in my table
256 int closest = closest_preceding_finger(&node, task_data->request_id);
257 INFO2("Forwarding 'Find Predecessor' request for id %d to my closest preceding finger %d", task_data->request_id, closest);
258 mailbox = get_mailbox(closest);
259 comm = MSG_task_isend(task, mailbox);
260 xbt_dynar_push(node.comms, &comm);
265 else if (!strcmp(task_name, "Update Finger")) {
266 // someone is telling me that he may be my new finger
267 INFO1("Receiving an 'Update Finger' request from %s", task_data->issuer_host_name);
268 update_finger_table(&node, task_data->request_id, task_data->request_finger);
270 else if (!strcmp(task_name, "Notify")) {
271 // someone is telling me that he may be my new predecessor
272 INFO1("Receiving a 'Notify' request from %s", task_data->issuer_host_name);
273 notify(&node, task_data->request_id);
275 else if (!strcmp(task_name, "Predecessor Leaving")) {
276 // my predecessor is about quitting
277 INFO1("Receiving a 'quite notify' from %s", task_data->issuer_host_name);
278 // modify my predecessor
279 node.pred_id = task_data->pred_id;
280 node.pred_mailbox = get_mailbox(node.id);
282 >> notify my new predecessor
283 >> send a notify_predecessors !!
287 else if (!strcmp(task_name, "Successor Leaving")) {
288 // my successor is about quitting
289 INFO1("Receiving a 'quite notify' from %s", task_data->issuer_host_name);
290 // modify my successor FIXME : this should be implicit ?
291 node.fingers[0].id = task_data->successor_id;
292 node.fingers[0].mailbox = get_mailbox(node.fingers[0].id);
294 >> notify my new successor
295 >> update my table & predecessors table */
299 // leave the ring and quit simulation
301 xbt_dynar_free(&node.comms);
302 xbt_free(node.mailbox);
303 xbt_free(node.pred_mailbox);
304 for (i = 0; i < NB_BITS - 1; i++) {
305 xbt_free(node.fingers[i].mailbox);
310 * \brief Initializes the current node as the first one of the system.
311 * \param node the current node
313 static void initialize_first_node(node_t node)
315 INFO0("Create a new Chord ring...");
317 // I am my own successor and predecessor
319 for (i = 0; i < NB_BITS; i++) {
320 node->fingers[i].id = node->id;
321 node->fingers[i].mailbox = xbt_strdup(node->mailbox);
323 node->pred_id = node->id;
324 node->pred_mailbox = node->mailbox;
325 print_finger_table(node);
329 * \brief Makes the current node join the system, knowing the id of a node already in the system
330 * \param node the current node
331 * \param known_id id of a node already in the system
333 static void join(node_t node, int known_id)
335 initialize_finger_table(node, known_id); // determine my fingers, asking to known_id
336 remote_notify(node, node->fingers[0].id, node->id); // tell my successor that I'm his new predecessor
337 notify_predecessors(node); // tell others that I may have became their finger
338 remote_move_keys(node, node->fingers[0].id); // take some key-value pairs from my successor
342 * \brief Makes the current node quit the system
343 * \param node the current node
345 static void leave(node_t node)
347 INFO0("Well Guys! I Think it's time for me to quit ;)");
348 quit_notify(node,1); // notify to my successor ( >>> 1 );
349 quit_notify(node,-1); // notify my predecessor ( >>> -1);
353 * \brief Notify msg to tell my successor||predecessor about my departure
354 * \param node the current node
356 static void quit_notify(node_t node, int to)
358 task_data_t req_data = xbt_new0(s_task_data_t, 1);
359 req_data->request_id = node->id;
360 req_data->successor_id = node->fingers[0].id;
361 req_data->pred_id = node->pred_id;
362 req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
363 const char *task_name = NULL;
364 const char* to_mailbox;
365 if( to == 1) // notify my successor
367 to_mailbox = node->fingers[0].mailbox;
368 INFO1("Telling my Successor about my departure via mailbox %s", to_mailbox);
369 task_name = "Predecessor Leaving";
372 else if(to == -1) // notify my predecessor
374 to_mailbox = node->pred_mailbox;
375 INFO1("Telling my Predecessor about my departure via mailbox %s",to_mailbox);
376 task_name = "Predecessor Leaving";
378 m_task_t task = MSG_task_create(task_name, 1000, 5000, req_data);
379 //char* mailbox = get_mailbox(to_mailbox);
380 msg_comm_t comm = MSG_task_isend(task, to_mailbox);
381 xbt_dynar_push(node->comms, &comm);
385 * \brief Initializes my finger table, knowing the id of a node already in the system.
386 * \param node the current node
387 * \param known_id id of a node already in the system
389 static void initialize_finger_table(node_t node, int known_id)
391 int my_id = node->id;
395 INFO0("Initializing my finger table...");
397 // ask known_id who is my immediate successor
398 node->fingers[0].id = remote_find_successor(node, known_id, my_id + 1);
399 node->fingers[0].mailbox = get_mailbox(node->fingers[0].id);
401 // find all other fingers
402 for (i = 0; i < NB_BITS - 1; i++) {
404 pow = pow << 1; // equivalent to pow = pow * 2
405 if (is_in_interval(my_id + pow, my_id, node->fingers[i].id - 1)) {
406 // I already have the info for this finger
407 node->fingers[i + 1].id = node->fingers[i].id;
410 // I don't have the info, ask the only guy I know
411 node->fingers[i + 1].id = remote_find_successor(node, known_id, my_id + pow);
413 node->fingers[i + 1].mailbox = get_mailbox(node->fingers[i + 1].id);
416 node->pred_id = find_predecessor(node, node->id);
417 node->pred_mailbox = get_mailbox(node->pred_id);
419 INFO0("Finger table initialized!");
420 print_finger_table(node);
424 * \brief Notifies some nodes that the current node may have became their finger.
425 * \param node the current node, which has just joined the system
427 static void notify_predecessors(node_t node)
431 for (i = 0; i < NB_BITS; i++) {
432 // find the closest node whose finger #i can be me
433 pred_id = find_predecessor(node, node->id - pow + 1); // note: no "+1" in the article!
434 if (pred_id != node->id) {
435 remote_update_finger_table(node, pred_id, node->id, i);
437 pow = pow << 1; // pow = pow * 2
442 * \brief Tells the current node that a node may have became its new finger.
443 * \param node the current node
444 * \param candidate_id id of the node that may be a new finger of the current node
445 * \param finger_index index of the finger to update
447 static void update_finger_table(node_t node, int candidate_id, int finger_index)
451 for (i = 0; i < finger_index; i++) {
455 // if (is_in_interval(candidate_id, node->id + pow, node->fingers[finger_index].id - 1)) {
456 if (is_in_interval(candidate_id, node->id, node->fingers[finger_index].id - 1)) {
457 // INFO3("Candidate %d is between %d and %d!", candidate_id, node->id + pow, node->fingers[finger_index].id - 1);
458 // candidate_id is my new finger
459 xbt_free(node->fingers[finger_index].mailbox);
460 node->fingers[finger_index].id = candidate_id;
461 node->fingers[finger_index].mailbox = get_mailbox(candidate_id);
462 INFO2("My new finger #%d is %d", finger_index, candidate_id);
463 print_finger_table(node);
465 if (node->pred_id != node->id) { // FIXME: is this necessary?
466 // my predecessor may be concerned too
467 remote_update_finger_table(node, node->pred_id, candidate_id, finger_index);
473 * \brief Tells a remote node that a node may have became its new finger.
474 * \param ask_to_id id of the remote node to update
475 * \param candidate_id id of the node that may be a new finger of the remote node
476 * \param finger_index index of the finger to update
478 static void remote_update_finger_table(node_t node, int ask_to_id, int candidate_id, int finger_index)
480 task_data_t req_data = xbt_new0(s_task_data_t, 1);
481 req_data->request_id = candidate_id;
482 req_data->request_finger = finger_index;
483 req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
485 // send a "Update Finger" request to ask_to_id
486 INFO3("Sending an 'Update Finger' request to %d: his finger #%d may be %d now", ask_to_id, finger_index, candidate_id);
487 m_task_t task = MSG_task_create("Update Finger", 1000, 5000, req_data);
488 char* mailbox = get_mailbox(ask_to_id);
489 msg_comm_t comm = MSG_task_isend(task, mailbox);
490 xbt_dynar_push(node->comms, &comm);
495 * \brief Makes the current node find the successor node of an id.
496 * \param node the current node
497 * \param id the id to find
498 * \return the id of the successor node
500 static int find_successor(node_t node, int id)
502 // is my successor the successor?
503 if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
504 return node->fingers[0].id;
507 // otherwise, ask the closest preceding finger in my table
508 int closest = closest_preceding_finger(node, id);
509 return remote_find_successor(node, closest, id);
513 * \brief Asks another node the successor node of an id.
514 * \param node the current node
515 * \param ask_to the node to ask to
516 * \param id the id to find
517 * \return the id of the successor node
519 static int remote_find_successor(node_t node, int ask_to, int id)
521 s_task_data_t req_data;
522 char* mailbox = bprintf("%s Find Successor", node->mailbox);
523 req_data.request_id = id;
524 req_data.answer_to = mailbox;
525 req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
527 // send a "Find Successor" request to ask_to_id
528 INFO2("Sending a 'Find Successor' request to %d for key %d", ask_to, id);
529 m_task_t task = MSG_task_create("Find Successor", 1000, 5000, &req_data);
530 MSG_task_send(task, get_mailbox(ask_to));
532 // receive the answer
534 MSG_task_receive(&task, req_data.answer_to);
535 task_data_t ans_data;
536 ans_data = MSG_task_get_data(task);
537 int successor = ans_data->answer_id;
539 INFO2("Received the answer to my Find Successor request: the successor of key %d is %d", id, successor);
546 * \brief Makes the current node find the predecessor node of an id.
547 * \param node the current node
548 * \param id the id to find
549 * \return the id of the predecessor node
551 static int find_predecessor(node_t node, int id)
553 if (node->id == node->fingers[0].id) {
554 // I am the only node in the system
558 if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
561 int ask_to = closest_preceding_finger(node, id);
562 return remote_find_predecessor(node, ask_to, id);
566 * \brief Asks another node the predecessor node of an id.
567 * \param node the current node
568 * \param ask_to the node to ask to
569 * \param id the id to find
570 * \return the id of the predecessor node
572 static int remote_find_predecessor(node_t node, int ask_to, int id)
574 s_task_data_t req_data;
575 char* mailbox = bprintf("%s Find Predecessor", node->mailbox);
576 req_data.request_id = id;
577 req_data.answer_to = mailbox;
578 req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
580 // send a "Find Predecessor" request to ask_to
581 INFO2("Sending a 'Find Predecessor' request to %d for key %d", ask_to, id);
582 m_task_t task = MSG_task_create("Find Predecessor", 1000, 5000, &req_data);
583 MSG_task_send(task, get_mailbox(ask_to));
585 // receive the answer
587 MSG_task_receive(&task, req_data.answer_to);
588 task_data_t ans_data;
589 ans_data = MSG_task_get_data(task);
590 int predecessor = ans_data->answer_id;
592 INFO2("Received the answer to my 'Find Predecessor' request: the predecessor of key %d is %d", id, predecessor);
598 * \brief Returns the closest preceding finger of an id
599 * with respect to the finger table of the current node.
600 * \param node the current node
601 * \param id the id to find
602 * \return the closest preceding finger of that id
604 int closest_preceding_finger(node_t node, int id)
607 for (i = NB_BITS - 1; i >= 0; i--) {
608 if (is_in_interval(node->fingers[i].id, node->id + 1, id - 1)) {
609 return node->fingers[i].id;
616 * \brief This function is called periodically. It checks the immediate
617 * successor of the current node.
618 * \param node the current node
620 static void stabilize(node_t node) {
622 int x = find_predecessor(node, node->fingers[0].id);
623 if (is_in_interval(x, node->id + 1, node->fingers[0].id)) {
624 xbt_free(node->fingers[0].mailbox);
625 node->fingers[0].id = x;
626 node->fingers[0].mailbox = get_mailbox(x);
628 remote_notify(node, node->fingers[0].id, node->id);
632 * \brief Notifies the current node that its predecessor may have changed.
633 * \param node the current node
634 * \param candidate_id the possible new predecessor
636 static void notify(node_t node, int predecessor_candidate_id) {
638 if (node->pred_id == node->id
639 || is_in_interval(predecessor_candidate_id, node->pred_id, node->id)) {
641 node->pred_id = predecessor_candidate_id;
642 node->pred_mailbox = get_mailbox(predecessor_candidate_id);
644 INFO1("My new predecessor is %d", predecessor_candidate_id);
645 print_finger_table(node);
648 INFO1("I don't have to change my predecessor to %d", predecessor_candidate_id);
653 * \brief Notifies a remote node that its predecessor may have changed.
654 * \param node the current node
655 * \param notify_id id of the node to notify
656 * \param candidate_id the possible new predecessor
658 static void remote_notify(node_t node, int notify_id, int predecessor_candidate_id) {
660 task_data_t req_data = xbt_new0(s_task_data_t, 1);
661 req_data->request_id = predecessor_candidate_id;
662 req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
664 // send a "Notify" request to notify_id
665 INFO1("Sending a 'Notify' request to %d", notify_id);
666 m_task_t task = MSG_task_create("Notify", 1000, 5000, req_data);
667 char* mailbox = get_mailbox(notify_id);
668 msg_comm_t comm = MSG_task_isend(task, mailbox);
669 xbt_dynar_push(node->comms, &comm);
674 * \brief Asks a node to take some of its keys.
675 * \param node the current node, which has just joined the system
676 * \param take_from_id id of a node who may have keys to give to the current node
678 static void remote_move_keys(node_t node, int take_from_id) {
683 * \brief Main function.
685 int main(int argc, char *argv[])
688 printf("Usage: %s platform_file deployment_file\n", argv[0]);
689 printf("example: %s ../msg_platform.xml chord.xml\n", argv[0]);
693 MSG_global_init(&argc, argv);
695 const char* platform_file = argv[1];
696 const char* application_file = argv[2];
698 /* MSG_config("workstation/model","KCCFLN05"); */
699 MSG_set_channel_number(0);
700 MSG_create_environment(platform_file);
702 MSG_function_register("node", node);
703 MSG_launch_application(application_file);
705 MSG_error_t res = MSG_main();
706 INFO1("Simulation time: %g", MSG_get_clock());