X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/45755c62629ed5663b73b6ac3f22618c7ec087f8..5964efeaa53eb62b51b814b67ff413f0593a03a0:/examples/msg/chord/chord.c diff --git a/examples/msg/chord/chord.c b/examples/msg/chord/chord.c index 54919e0a6c..2bfaa484ec 100644 --- a/examples/msg/chord/chord.c +++ b/examples/msg/chord/chord.c @@ -9,6 +9,10 @@ #include "msg/msg.h" #include "xbt/log.h" #include "xbt/asserts.h" +#include "mc/modelchecker.h" +#include "mc/mc.h" +#include "xbt/xbt_os_time.h" + XBT_LOG_NEW_DEFAULT_CATEGORY(msg_chord, "Messages specific for this msg example"); @@ -25,6 +29,8 @@ static int periodic_fix_fingers_delay = 120; static int periodic_check_predecessor_delay = 120; static int periodic_lookup_delay = 10; +extern long int smx_total_comms; + /** * Finger element. */ @@ -44,7 +50,6 @@ typedef struct node { char pred_mailbox[MAILBOX_NAME_SIZE]; // predecessor's mailbox name int next_finger_to_fix; // index of the next finger to fix in fix_fingers() msg_comm_t comm_receive; // current communication to receive - xbt_dynar_t comms; // current communications being sent double last_change_date; // last time I changed a finger or my predecessor } s_node_t, *node_t; @@ -77,10 +82,11 @@ static int *powers2; // utility functions static void chord_initialize(void); +static void chord_exit(void); static int normalize(int id); static int is_in_interval(int id, int start, int end); static void get_mailbox(int host_id, char* mailbox); -static void task_data_destroy(task_data_t task_data); +static void task_free(void* task); static void print_finger_table(node_t node); static void set_finger(node_t node, int finger_index, int id); static void set_predecessor(node_t node, int predecessor_id); @@ -119,7 +125,12 @@ static void chord_initialize(void) pow = pow << 1; } nb_keys = pow; - DEBUG1("Sets nb_keys to %d", nb_keys); + XBT_DEBUG("Sets nb_keys to %d", nb_keys); +} + +static void chord_exit(void) +{ + xbt_free(powers2); } /** @@ -129,18 +140,12 @@ static void chord_initialize(void) */ static int normalize(int id) { - // make sure id >= 0 - while (id < 0) { - id += nb_keys; - } - // make sure id < nb_keys - id = id % nb_keys; - - return id; + // like id % nb_keys, but works with negatives numbers (and faster) + return id & (nb_keys - 1); } /** - * \brief Returns whether a id belongs to the interval [start, end]. + * \brief Returns whether an id belongs to the interval [start, end]. * * The parameters are noramlized to make sure they are between 0 and nb_keys - 1). * 1 belongs to [62, 3] @@ -185,12 +190,14 @@ static void get_mailbox(int node_id, char* mailbox) } /** - * \brief Frees the memory used by some task data. - * \param task_data the task data to destroy + * \brief Frees the memory used by a task. + * \param task the MSG task to destroy */ -static void task_data_destroy(task_data_t task_data) +static void task_free(void* task) { - xbt_free(task_data); + // TODO add a parameter data_free_function to MSG_task_create? + xbt_free(MSG_task_get_data(task)); + MSG_task_destroy(task); } /** @@ -201,12 +208,12 @@ static void print_finger_table(node_t node) { if (XBT_LOG_ISENABLED(msg_chord, xbt_log_priority_verbose)) { int i; - VERB0("My finger table:"); - VERB0("Start | Succ "); + XBT_VERB("My finger table:"); + XBT_VERB("Start | Succ "); for (i = 0; i < nb_bits; i++) { - VERB2(" %3d | %3d ", (node->id + powers2[i]) % nb_keys, node->fingers[i].id); + XBT_VERB(" %3d | %3d ", (node->id + powers2[i]) % nb_keys, node->fingers[i].id); } - VERB1("Predecessor: %d", node->pred_id); + XBT_VERB("Predecessor: %d", node->pred_id); } } @@ -222,7 +229,7 @@ static void set_finger(node_t node, int finger_index, int id) node->fingers[finger_index].id = id; get_mailbox(id, node->fingers[finger_index].mailbox); node->last_change_date = MSG_get_clock(); - DEBUG2("My new finger #%d is %d", finger_index, id); + XBT_DEBUG("My new finger #%d is %d", finger_index, id); } } @@ -241,7 +248,7 @@ static void set_predecessor(node_t node, int predecessor_id) } node->last_change_date = MSG_get_clock(); - DEBUG1("My new predecessor is %d", predecessor_id); + XBT_DEBUG("My new predecessor is %d", predecessor_id); } } @@ -254,12 +261,16 @@ static void set_predecessor(node_t node, int predecessor_id) */ int node(int argc, char *argv[]) { + /* Reduce the run size for the MC */ + if(MC_IS_ENABLED){ + periodic_stabilize_delay = 8; + periodic_fix_fingers_delay = 8; + periodic_check_predecessor_delay = 8; + } + double init_time = MSG_get_clock(); - /*m_task_t task = NULL;*/ m_task_t task_received = NULL; - msg_comm_t comm_send = NULL; int i; - int index; int join_success = 0; double deadline; double next_stabilize_date = init_time + periodic_stabilize_delay; @@ -267,14 +278,13 @@ int node(int argc, char *argv[]) double next_check_predecessor_date = init_time + periodic_check_predecessor_delay; double next_lookup_date = init_time + periodic_lookup_delay; - xbt_assert0(argc == 3 || argc == 5, "Wrong number of arguments for this node"); + xbt_assert(argc == 3 || argc == 5, "Wrong number of arguments for this node"); // initialize my node s_node_t node = {0}; node.id = atoi(argv[1]); get_mailbox(node.id, node.mailbox); node.next_finger_to_fix = 0; - node.comms = xbt_dynar_new(sizeof(msg_comm_t), NULL); node.fingers = xbt_new0(s_finger_t, nb_bits); node.last_change_date = init_time; @@ -295,10 +305,10 @@ int node(int argc, char *argv[]) /* // sleep before starting - DEBUG1("Let's sleep during %f", sleep_time); + XBT_DEBUG("Let's sleep during %f", sleep_time); MSG_process_sleep(sleep_time); */ - DEBUG0("Hey! Let's join the system."); + XBT_DEBUG("Hey! Let's join the system."); join_success = join(&node, known_id); } @@ -338,13 +348,16 @@ int node(int argc, char *argv[]) MSG_process_sleep(5); } } - else { + + if (node.comm_receive && MSG_comm_test(node.comm_receive)) { + // a transfer has occured MSG_error_t status = MSG_comm_get_status(node.comm_receive); if (status != MSG_OK) { - DEBUG0("Failed to receive a task. Nevermind."); + XBT_DEBUG("Failed to receive a task. Nevermind."); + MSG_comm_destroy(node.comm_receive); node.comm_receive = NULL; } else { @@ -354,35 +367,18 @@ int node(int argc, char *argv[]) handle_task(&node, task_received); } } - - // see if some communications are finished - while ((index = MSG_comm_testany(node.comms)) != -1) { - comm_send = xbt_dynar_get_as(node.comms, index, msg_comm_t); - MSG_error_t status = MSG_comm_get_status(comm_send); - xbt_dynar_remove_at(node.comms, index, &comm_send); - DEBUG3("Communication %p is finished with status %d, dynar size is now %lu", - comm_send, status, xbt_dynar_length(node.comms)); - MSG_comm_destroy(comm_send); - } } - // clean unfinished comms sent - /* unsigned int cursor; - xbt_dynar_foreach(node.comms, cursor, comm_send) { - task = MSG_comm_get_task(comm_send); - MSG_task_cancel(task); - task_data_destroy(MSG_task_get_data(task)); - MSG_task_destroy(task); - MSG_comm_destroy(comm_send); - // FIXME: the task is actually not destroyed because MSG thinks that the other side (whose process is dead) is still using it - }*/ + if (node.comm_receive) { + MSG_comm_destroy(node.comm_receive); + node.comm_receive = NULL; + } // leave the ring leave(&node); } // stop the simulation - xbt_dynar_free(&node.comms); xbt_free(node.fingers); return 0; } @@ -395,65 +391,59 @@ int node(int argc, char *argv[]) */ static void handle_task(node_t node, m_task_t task) { - DEBUG1("Handling task %p", task); - msg_comm_t comm = NULL; - char* mailbox = NULL; + XBT_DEBUG("Handling task %p", task); + char mailbox[MAILBOX_NAME_SIZE]; task_data_t task_data = (task_data_t) MSG_task_get_data(task); e_task_type_t type = task_data->type; switch (type) { case TASK_FIND_SUCCESSOR: - DEBUG2("Receiving a 'Find Successor' request from %s for id %d", + XBT_DEBUG("Receiving a 'Find Successor' request from %s for id %d", task_data->issuer_host_name, task_data->request_id); // is my successor the successor? if (is_in_interval(task_data->request_id, node->id + 1, node->fingers[0].id)) { task_data->type = TASK_FIND_SUCCESSOR_ANSWER; task_data->answer_id = node->fingers[0].id; - DEBUG3("Sending back a 'Find Successor Answer' to %s: the successor of %d is %d", + XBT_DEBUG("Sending back a 'Find Successor Answer' to %s (mailbox %s): the successor of %d is %d", task_data->issuer_host_name, + task_data->answer_to, task_data->request_id, task_data->answer_id); - comm = MSG_task_isend(task, task_data->answer_to); - xbt_dynar_push(node->comms, &comm); + MSG_task_dsend(task, task_data->answer_to, task_free); } else { // otherwise, forward the request to the closest preceding finger in my table int closest = closest_preceding_node(node, task_data->request_id); - DEBUG2("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d", + XBT_DEBUG("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d", task_data->request_id, closest); get_mailbox(closest, mailbox); - comm = MSG_task_isend(task, mailbox); - xbt_dynar_push(node->comms, &comm); - xbt_free(mailbox); + MSG_task_dsend(task, mailbox, task_free); } break; case TASK_GET_PREDECESSOR: - DEBUG1("Receiving a 'Get Predecessor' request from %s", task_data->issuer_host_name); + XBT_DEBUG("Receiving a 'Get Predecessor' request from %s", task_data->issuer_host_name); task_data->type = TASK_GET_PREDECESSOR_ANSWER; task_data->answer_id = node->pred_id; - DEBUG3("Sending back a 'Get Predecessor Answer' to %s via mailbox '%s': my predecessor is %d", + XBT_DEBUG("Sending back a 'Get Predecessor Answer' to %s via mailbox '%s': my predecessor is %d", task_data->issuer_host_name, task_data->answer_to, task_data->answer_id); - comm = MSG_task_isend(task, task_data->answer_to); - xbt_dynar_push(node->comms, &comm); + MSG_task_dsend(task, task_data->answer_to, task_free); break; case TASK_NOTIFY: // someone is telling me that he may be my new predecessor - DEBUG1("Receiving a 'Notify' request from %s", task_data->issuer_host_name); + XBT_DEBUG("Receiving a 'Notify' request from %s", task_data->issuer_host_name); notify(node, task_data->request_id); - task_data_destroy(task_data); - MSG_task_destroy(task); + task_free(task); break; case TASK_PREDECESSOR_LEAVING: // my predecessor is about to quit - DEBUG1("Receiving a 'Predecessor Leaving' message from %s", task_data->issuer_host_name); + XBT_DEBUG("Receiving a 'Predecessor Leaving' message from %s", task_data->issuer_host_name); // modify my predecessor set_predecessor(node, task_data->request_id); - task_data_destroy(task_data); - MSG_task_destroy(task); + task_free(task); /*TODO : >> notify my new predecessor >> send a notify_predecessors !! @@ -462,11 +452,10 @@ static void handle_task(node_t node, m_task_t task) { case TASK_SUCCESSOR_LEAVING: // my successor is about to quit - DEBUG1("Receiving a 'Successor Leaving' message from %s", task_data->issuer_host_name); + XBT_DEBUG("Receiving a 'Successor Leaving' message from %s", task_data->issuer_host_name); // modify my successor FIXME : this should be implicit ? set_finger(node, 0, task_data->request_id); - task_data_destroy(task_data); - MSG_task_destroy(task); + task_free(task); /* TODO >> notify my new successor >> update my table & predecessors table */ @@ -474,7 +463,8 @@ static void handle_task(node_t node, m_task_t task) { case TASK_FIND_SUCCESSOR_ANSWER: case TASK_GET_PREDECESSOR_ANSWER: - DEBUG2("Ignoring unexpected task of type %d (%p)", type, task); + XBT_DEBUG("Ignoring unexpected task of type %d (%p)", type, task); + task_free(task); break; } } @@ -485,7 +475,7 @@ static void handle_task(node_t node, m_task_t task) { */ static void create(node_t node) { - DEBUG0("Create a new Chord ring..."); + XBT_DEBUG("Create a new Chord ring..."); set_predecessor(node, -1); // -1 means that I have no predecessor print_finger_table(node); } @@ -499,12 +489,19 @@ static void create(node_t node) */ static int join(node_t node, int known_id) { - INFO2("Joining the ring with id %d, knowing node %d", node->id, known_id); + XBT_INFO("Joining the ring with id %d, knowing node %d", node->id, known_id); set_predecessor(node, -1); // no predecessor (yet) + /* + int i; + for (i = 0; i < nb_bits; i++) { + set_finger(node, i, known_id); + } + */ + int successor_id = remote_find_successor(node, known_id, node->id); if (successor_id == -1) { - INFO0("Cannot join the ring."); + XBT_INFO("Cannot join the ring."); } else { set_finger(node, 0, successor_id); @@ -520,7 +517,7 @@ static int join(node_t node, int known_id) */ static void leave(node_t node) { - DEBUG0("Well Guys! I Think it's time for me to quit ;)"); + XBT_DEBUG("Well Guys! I Think it's time for me to quit ;)"); quit_notify(node, 1); // notify to my successor ( >>> 1 ); quit_notify(node, -1); // notify my predecessor ( >>> -1); // TODO ... @@ -546,7 +543,7 @@ static void quit_notify(node_t node, int to) const char* to_mailbox = NULL; if (to == 1) { // notify my successor to_mailbox = node->fingers[0].mailbox; - INFO2("Telling my Successor %d about my departure via mailbox %s", + XBT_INFO("Telling my Successor %d about my departure via mailbox %s", node->fingers[0].id, to_mailbox); req_data->type = TASK_PREDECESSOR_LEAVING; } @@ -557,7 +554,7 @@ static void quit_notify(node_t node, int to) } to_mailbox = node->pred_mailbox; - INFO2("Telling my Predecessor %d about my departure via mailbox %s", + XBT_INFO("Telling my Predecessor %d about my departure via mailbox %s", node->pred_id, to_mailbox); req_data->type = TASK_SUCCESSOR_LEAVING; } @@ -607,19 +604,18 @@ static int remote_find_successor(node_t node, int ask_to, int id) // send a "Find Successor" request to ask_to_id m_task_t task_sent = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, req_data); - DEBUG3("Sending a 'Find Successor' request (task %p) to %d for id %d", task_sent, ask_to, id); + XBT_DEBUG("Sending a 'Find Successor' request (task %p) to %d for id %d", task_sent, ask_to, id); MSG_error_t res = MSG_task_send_with_timeout(task_sent, mailbox, timeout); if (res != MSG_OK) { - DEBUG3("Failed to send the 'Find Successor' request (task %p) to %d for id %d", + XBT_DEBUG("Failed to send the 'Find Successor' request (task %p) to %d for id %d", task_sent, ask_to, id); - MSG_task_destroy(task_sent); - task_data_destroy(req_data); + task_free(task_sent); } else { // receive the answer - DEBUG3("Sent a 'Find Successor' request (task %p) to %d for key %d, waiting for the answer", + XBT_DEBUG("Sent a 'Find Successor' request (task %p) to %d for key %d, waiting for the answer", task_sent, ask_to, id); do { @@ -631,32 +627,38 @@ static int remote_find_successor(node_t node, int ask_to, int id) res = MSG_comm_wait(node->comm_receive, timeout); if (res != MSG_OK) { - DEBUG2("Failed to receive the answer to my 'Find Successor' request (task %p): %d", + XBT_DEBUG("Failed to receive the answer to my 'Find Successor' request (task %p): %d", task_sent, res); stop = 1; - //MSG_comm_destroy(node->comm_receive); + MSG_comm_destroy(node->comm_receive); + node->comm_receive = NULL; } else { m_task_t task_received = MSG_comm_get_task(node->comm_receive); - DEBUG1("Received a task (%p)", task_received); + XBT_DEBUG("Received a task (%p)", task_received); task_data_t ans_data = MSG_task_get_data(task_received); + if (MC_IS_ENABLED) { + MC_assert(task_received == task_sent); + } + if (task_received != task_sent) { // this is not the expected answer + MSG_comm_destroy(node->comm_receive); + node->comm_receive = NULL; handle_task(node, task_received); } else { // this is our answer - DEBUG4("Received the answer to my 'Find Successor' request for id %d (task %p): the successor of key %d is %d", + XBT_DEBUG("Received the answer to my 'Find Successor' request for id %d (task %p): the successor of key %d is %d", ans_data->request_id, task_received, id, ans_data->answer_id); successor = ans_data->answer_id; stop = 1; - MSG_task_destroy(task_received); - task_data_destroy(req_data); + MSG_comm_destroy(node->comm_receive); + node->comm_receive = NULL; + task_free(task_received); } } - MSG_comm_destroy(node->comm_receive); - node->comm_receive = NULL; } while (!stop); } @@ -682,20 +684,19 @@ static int remote_get_predecessor(node_t node, int ask_to) req_data->issuer_host_name = MSG_host_get_name(MSG_host_self()); // send a "Get Predecessor" request to ask_to_id - DEBUG1("Sending a 'Get Predecessor' request to %d", ask_to); + XBT_DEBUG("Sending a 'Get Predecessor' request to %d", ask_to); m_task_t task_sent = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, req_data); MSG_error_t res = MSG_task_send_with_timeout(task_sent, mailbox, timeout); if (res != MSG_OK) { - DEBUG2("Failed to send the 'Get Predecessor' request (task %p) to %d", + XBT_DEBUG("Failed to send the 'Get Predecessor' request (task %p) to %d", task_sent, ask_to); - MSG_task_destroy(task_sent); - task_data_destroy(req_data); + task_free(task_sent); } else { // receive the answer - DEBUG3("Sent 'Get Predecessor' request (task %p) to %d, waiting for the answer on my mailbox '%s'", + XBT_DEBUG("Sent 'Get Predecessor' request (task %p) to %d, waiting for the answer on my mailbox '%s'", task_sent, ask_to, req_data->answer_to); do { @@ -707,29 +708,35 @@ static int remote_get_predecessor(node_t node, int ask_to) res = MSG_comm_wait(node->comm_receive, timeout); if (res != MSG_OK) { - DEBUG2("Failed to receive the answer to my 'Get Predecessor' request (task %p): %d", + XBT_DEBUG("Failed to receive the answer to my 'Get Predecessor' request (task %p): %d", task_sent, res); stop = 1; - //MSG_comm_destroy(node->comm_receive); + MSG_comm_destroy(node->comm_receive); + node->comm_receive = NULL; } else { m_task_t task_received = MSG_comm_get_task(node->comm_receive); task_data_t ans_data = MSG_task_get_data(task_received); + if (MC_IS_ENABLED) { + MC_assert(task_received == task_sent); + } + if (task_received != task_sent) { + MSG_comm_destroy(node->comm_receive); + node->comm_receive = NULL; handle_task(node, task_received); } else { - DEBUG3("Received the answer to my 'Get Predecessor' request (task %p): the predecessor of node %d is %d", + XBT_DEBUG("Received the answer to my 'Get Predecessor' request (task %p): the predecessor of node %d is %d", task_received, ask_to, ans_data->answer_id); predecessor_id = ans_data->answer_id; stop = 1; - MSG_task_destroy(task_received); - task_data_destroy(req_data); + MSG_comm_destroy(node->comm_receive); + node->comm_receive = NULL; + task_free(task_received); } } - MSG_comm_destroy(node->comm_receive); - node->comm_receive = NULL; } while (!stop); } @@ -761,7 +768,7 @@ int closest_preceding_node(node_t node, int id) */ static void stabilize(node_t node) { - DEBUG0("Stabilizing node"); + XBT_DEBUG("Stabilizing node"); // get the predecessor of my immediate successor int candidate_id; @@ -797,7 +804,7 @@ static void notify(node_t node, int predecessor_candidate_id) { print_finger_table(node); } else { - DEBUG1("I don't have to change my predecessor to %d", predecessor_candidate_id); + XBT_DEBUG("I don't have to change my predecessor to %d", predecessor_candidate_id); } } @@ -816,11 +823,10 @@ static void remote_notify(node_t node, int notify_id, int predecessor_candidate_ // send a "Notify" request to notify_id m_task_t task = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, req_data); - DEBUG2("Sending a 'Notify' request (task %p) to %d", task, notify_id); + XBT_DEBUG("Sending a 'Notify' request (task %p) to %d", task, notify_id); char mailbox[MAILBOX_NAME_SIZE]; get_mailbox(notify_id, mailbox); - msg_comm_t comm = MSG_task_isend(task, mailbox); - xbt_dynar_push(node->comms, &comm); + MSG_task_dsend(task, mailbox, task_free); } /** @@ -830,7 +836,7 @@ static void remote_notify(node_t node, int notify_id, int predecessor_candidate_ */ static void fix_fingers(node_t node) { - DEBUG0("Fixing fingers"); + XBT_DEBUG("Fixing fingers"); int i = node->next_finger_to_fix; int id = find_successor(node, node->id + powers2[i]); if (id != -1) { @@ -850,7 +856,7 @@ static void fix_fingers(node_t node) { */ static void check_predecessor(node_t node) { - DEBUG0("Checking whether my predecessor is alive"); + XBT_DEBUG("Checking whether my predecessor is alive"); // TODO } @@ -861,7 +867,7 @@ static void check_predecessor(node_t node) static void random_lookup(node_t node) { int id = 1337; // TODO pick a pseudorandom id - DEBUG1("Making a lookup request for id %d", id); + XBT_DEBUG("Making a lookup request for id %d", id); find_successor(node, id); } @@ -884,17 +890,17 @@ int main(int argc, char *argv[]) int length = strlen("-nb_bits="); if (!strncmp(options[0], "-nb_bits=", length) && strlen(options[0]) > length) { nb_bits = atoi(options[0] + length); - DEBUG1("Set nb_bits to %d", nb_bits); + XBT_DEBUG("Set nb_bits to %d", nb_bits); } else { length = strlen("-timeout="); if (!strncmp(options[0], "-timeout=", length) && strlen(options[0]) > length) { timeout = atoi(options[0] + length); - DEBUG1("Set timeout to %d", timeout); + XBT_DEBUG("Set timeout to %d", timeout); } else { - xbt_assert1(0, "Invalid chord option '%s'", options[0]); + xbt_die("Invalid chord option '%s'", options[0]); } } options++; @@ -912,9 +918,11 @@ int main(int argc, char *argv[]) MSG_launch_application(application_file); MSG_error_t res = MSG_main(); - INFO1("Simulation time: %g", MSG_get_clock()); + XBT_CRITICAL("Messages created: %ld", smx_total_comms); + XBT_INFO("Simulated time: %g", MSG_get_clock()); MSG_clean(); + chord_exit(); if (res == MSG_OK) return 0;