X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/c2f8851217b62c872f98ef5233d6c53318844e31..52ecb7077f76635393af439dc2e023485631f8e9:/examples/msg/chord/chord.c diff --git a/examples/msg/chord/chord.c b/examples/msg/chord/chord.c index 88987d7aa7..8f7b2f543a 100644 --- a/examples/msg/chord/chord.c +++ b/examples/msg/chord/chord.c @@ -9,21 +9,30 @@ #include "msg/msg.h" #include "xbt/log.h" #include "xbt/asserts.h" +#include "mc/modelchecker.h" +#include "mc/mc.h" XBT_LOG_NEW_DEFAULT_CATEGORY(msg_chord, "Messages specific for this msg example"); -#define NB_BITS 16 -#define NB_KEYS 65536 #define COMM_SIZE 10 #define COMP_SIZE 0 -#define TIMEOUT 50 +#define MAILBOX_NAME_SIZE 10 + +static int nb_bits = 24; +static int nb_keys = 0; +static int timeout = 50; +static int max_simulation_time = 1000; +static int periodic_stabilize_delay = 20; +static int periodic_fix_fingers_delay = 120; +static int periodic_check_predecessor_delay = 120; +static int periodic_lookup_delay = 10; /** * Finger element. */ typedef struct finger { int id; - char* mailbox; + char mailbox[MAILBOX_NAME_SIZE]; // string representation of the id } s_finger_t, *finger_t; /** @@ -31,13 +40,14 @@ typedef struct finger { */ typedef struct node { int id; // my id - char* mailbox; // my usual mailbox name - s_finger_t fingers[NB_BITS]; // finger table (fingers[0] is my successor) + char mailbox[MAILBOX_NAME_SIZE]; // my mailbox name (string representation of the id) + s_finger_t *fingers; // finger table, of size nb_bits (fingers[0] is my successor) int pred_id; // predecessor id - char* pred_mailbox; // predecessor's mailbox name + 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; /** @@ -61,17 +71,17 @@ typedef struct task_data { int request_id; // id paramater (used by some types of tasks) int request_finger; // finger parameter (used by some types of tasks) int answer_id; // answer (used by some types of tasks) - char* answer_to; // mailbox to send an answer to (or NULL) + char answer_to[MAILBOX_NAME_SIZE]; // mailbox to send an answer to (if any) const char* issuer_host_name; // used for logging } s_task_data_t, *task_data_t; -static int powers2[NB_BITS]; +static int *powers2; // utility functions static void chord_initialize(void); static int normalize(int id); static int is_in_interval(int id, int start, int end); -static char* get_mailbox(int host_id); +static void get_mailbox(int host_id, char* mailbox); static void task_data_destroy(task_data_t task_data); static void print_finger_table(node_t node); static void set_finger(node_t node, int finger_index, int id); @@ -94,6 +104,7 @@ static void notify(node_t node, int predecessor_candidate_id); static void remote_notify(node_t node, int notify_to, int predecessor_candidate_id); static void fix_fingers(node_t node); static void check_predecessor(node_t node); +static void random_lookup(node_t); static void quit_notify(node_t node, int to); /** @@ -102,35 +113,32 @@ static void quit_notify(node_t node, int to); static void chord_initialize(void) { // compute the powers of 2 once for all + powers2 = xbt_new(int, nb_bits); int pow = 1; int i; - for (i = 0; i < NB_BITS; i++) { + for (i = 0; i < nb_bits; i++) { powers2[i] = pow; pow = pow << 1; } + nb_keys = pow; + DEBUG1("Sets nb_keys to %d", nb_keys); } /** - * \brief Turns an id into an equivalent id in [0, NB_KEYS). + * \brief Turns an id into an equivalent id in [0, nb_keys). * \param id an id * \return the corresponding normalized id */ 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]. * - * The parameters are noramlized to make sure they are between 0 and CHORD_NB_KEYS - 1). + * The parameters are noramlized to make sure they are between 0 and nb_keys - 1). * 1 belongs to [62, 3] * 1 does not belong to [3, 62] * 63 belongs to [62, 3] @@ -151,11 +159,11 @@ static int is_in_interval(int id, int start, int end) // make sure end >= start and id >= start if (end < start) { - end += NB_KEYS; + end += nb_keys; } if (id < start) { - id += NB_KEYS; + id += nb_keys; } return id <= end; @@ -164,11 +172,12 @@ static int is_in_interval(int id, int start, int end) /** * \brief Gets the mailbox name of a host given its chord id. * \param node_id id of a node - * \return the name of its mailbox + * \param mailbox pointer to where the mailbox name should be written + * (there must be enough space) */ -static char* get_mailbox(int node_id) +static void get_mailbox(int node_id, char* mailbox) { - return bprintf("mailbox%d", node_id); + snprintf(mailbox, MAILBOX_NAME_SIZE - 1, "%d", node_id); } /** @@ -177,7 +186,6 @@ static char* get_mailbox(int node_id) */ static void task_data_destroy(task_data_t task_data) { - xbt_free(task_data->answer_to); xbt_free(task_data); } @@ -189,12 +197,10 @@ static void print_finger_table(node_t node) { if (XBT_LOG_ISENABLED(msg_chord, xbt_log_priority_verbose)) { int i; - int pow = 1; VERB0("My finger table:"); VERB0("Start | Succ "); - for (i = 0; i < NB_BITS; i++) { - VERB2(" %3d | %3d ", (node->id + pow) % NB_KEYS, node->fingers[i].id); - pow = pow << 1; + for (i = 0; i < nb_bits; i++) { + VERB2(" %3d | %3d ", (node->id + powers2[i]) % nb_keys, node->fingers[i].id); } VERB1("Predecessor: %d", node->pred_id); } @@ -203,15 +209,17 @@ static void print_finger_table(node_t node) /** * \brief Sets a finger of the current node. * \param node the current node - * \param finger_index index of the finger to set (0 to NB_BITS - 1) + * \param finger_index index of the finger to set (0 to nb_bits - 1) * \param id the id to set for this finger */ static void set_finger(node_t node, int finger_index, int id) { - node->fingers[finger_index].id = id; - xbt_free(node->fingers[finger_index].mailbox); - node->fingers[finger_index].mailbox = get_mailbox(id); - DEBUG2("My new finger #%d is %d", finger_index, id); + if (id != node->fingers[finger_index].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); + } } /** @@ -221,14 +229,16 @@ static void set_finger(node_t node, int finger_index, int id) */ static void set_predecessor(node_t node, int predecessor_id) { - node->pred_id = predecessor_id; - xbt_free(node->pred_mailbox); + if (predecessor_id != node->pred_id) { + node->pred_id = predecessor_id; - if (predecessor_id != -1) { - node->pred_mailbox = get_mailbox(predecessor_id); - } + if (predecessor_id != -1) { + get_mailbox(predecessor_id, node->pred_mailbox); + } + node->last_change_date = MSG_get_clock(); - DEBUG1("My new predecessor is %d", predecessor_id); + DEBUG1("My new predecessor is %d", predecessor_id); + } } /** @@ -240,28 +250,38 @@ 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 + 10; - double next_fix_fingers_date = init_time + 10; - double next_check_predecessor_date = init_time + 10; + double next_stabilize_date = init_time + periodic_stabilize_delay; + double next_fix_fingers_date = init_time + periodic_fix_fingers_delay; + 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"); // initialize my node s_node_t node = {0}; node.id = atoi(argv[1]); - node.mailbox = get_mailbox(node.id); + 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; - for (i = 0; i < NB_BITS; i++) { + for (i = 0; i < nb_bits; i++) { + node.fingers[i].id = -1; set_finger(&node, i, node.id); } @@ -272,19 +292,23 @@ int node(int argc, char *argv[]) } else { int known_id = atoi(argv[2]); - double sleep_time = atof(argv[3]); + //double sleep_time = atof(argv[3]); deadline = atof(argv[4]); + /* // sleep before starting DEBUG1("Let's sleep during %f", sleep_time); MSG_process_sleep(sleep_time); + */ DEBUG0("Hey! Let's join the system."); join_success = join(&node, known_id); } if (join_success) { - while (MSG_get_clock() < init_time + deadline) { + while (MSG_get_clock() < init_time + deadline +// && MSG_get_clock() < node.last_change_date + 1000 + && MSG_get_clock() < max_simulation_time) { if (node.comm_receive == NULL) { task_received = NULL; @@ -297,16 +321,20 @@ int node(int argc, char *argv[]) // no task was received: make some periodic calls if (MSG_get_clock() >= next_stabilize_date) { stabilize(&node); - next_stabilize_date = MSG_get_clock() + 10; + next_stabilize_date = MSG_get_clock() + periodic_stabilize_delay; } else if (MSG_get_clock() >= next_fix_fingers_date) { fix_fingers(&node); - next_fix_fingers_date = MSG_get_clock() + 10; + next_fix_fingers_date = MSG_get_clock() + periodic_fix_fingers_delay; } else if (MSG_get_clock() >= next_check_predecessor_date) { check_predecessor(&node); - next_check_predecessor_date = MSG_get_clock() + 10; + next_check_predecessor_date = MSG_get_clock() + periodic_check_predecessor_delay; } + else if (MSG_get_clock() >= next_lookup_date) { + random_lookup(&node); + next_lookup_date = MSG_get_clock() + periodic_lookup_delay; + } else { // nothing to do: sleep for a while MSG_process_sleep(5); @@ -336,20 +364,25 @@ int node(int argc, char *argv[]) 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)); + m_task_t task = MSG_comm_get_task(comm_send); MSG_comm_destroy(comm_send); + if (status != MSG_OK) { + task_data_destroy(MSG_task_get_data(task)); + MSG_task_destroy(task); + } } } // clean unfinished comms sent - unsigned int cursor; + /* unsigned int cursor; xbt_dynar_foreach(node.comms, cursor, comm_send) { - task = MSG_comm_get_task(comm_send); + m_task_t 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 - } + }*/ // leave the ring leave(&node); @@ -357,11 +390,7 @@ int node(int argc, char *argv[]) // stop the simulation xbt_dynar_free(&node.comms); - xbt_free(node.mailbox); - xbt_free(node.pred_mailbox); - for (i = 0; i < NB_BITS - 1; i++) { - xbt_free(node.fingers[i].mailbox); - } + xbt_free(node.fingers); return 0; } @@ -375,7 +404,7 @@ static void handle_task(node_t node, m_task_t task) { DEBUG1("Handling task %p", task); msg_comm_t comm = NULL; - char* mailbox = NULL; + 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; @@ -388,8 +417,9 @@ static void handle_task(node_t node, m_task_t task) { 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", + DEBUG4("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); @@ -399,10 +429,9 @@ static void handle_task(node_t node, m_task_t task) { 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", task_data->request_id, closest); - mailbox = get_mailbox(closest); + get_mailbox(closest, mailbox); comm = MSG_task_isend(task, mailbox); xbt_dynar_push(node->comms, &comm); - xbt_free(mailbox); } break; @@ -453,6 +482,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); + task_data_destroy(task_data); + MSG_task_destroy(task); break; } } @@ -575,17 +606,18 @@ static int remote_find_successor(node_t node, int ask_to, int id) { int successor = -1; int stop = 0; - char* mailbox = get_mailbox(ask_to); + char mailbox[MAILBOX_NAME_SIZE]; + get_mailbox(ask_to, mailbox); task_data_t req_data = xbt_new0(s_task_data_t, 1); req_data->type = TASK_FIND_SUCCESSOR; req_data->request_id = id; - req_data->answer_to = xbt_strdup(node->mailbox); + get_mailbox(node->id, req_data->answer_to); req_data->issuer_host_name = MSG_host_get_name(MSG_host_self()); // 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); - MSG_error_t res = MSG_task_send_with_timeout(task_sent, mailbox, TIMEOUT); + 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", @@ -605,21 +637,28 @@ static int remote_find_successor(node_t node, int ask_to, int id) node->comm_receive = MSG_task_irecv(&task_received, node->mailbox); } - res = MSG_comm_wait(node->comm_receive, TIMEOUT); + 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", 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); 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 { @@ -628,15 +667,15 @@ static int remote_find_successor(node_t node, int ask_to, int id) ans_data->request_id, task_received, id, ans_data->answer_id); successor = ans_data->answer_id; stop = 1; + MSG_comm_destroy(node->comm_receive); + node->comm_receive = NULL; MSG_task_destroy(task_received); task_data_destroy(req_data); } } - node->comm_receive = NULL; } while (!stop); } - xbt_free(mailbox); return successor; } @@ -651,16 +690,17 @@ static int remote_get_predecessor(node_t node, int ask_to) { int predecessor_id = -1; int stop = 0; - char* mailbox = get_mailbox(ask_to); + char mailbox[MAILBOX_NAME_SIZE]; + get_mailbox(ask_to, mailbox); task_data_t req_data = xbt_new0(s_task_data_t, 1); req_data->type = TASK_GET_PREDECESSOR; - req_data->answer_to = xbt_strdup(node->mailbox); + get_mailbox(node->id, req_data->answer_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); 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); + 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", @@ -680,19 +720,26 @@ static int remote_get_predecessor(node_t node, int ask_to) node->comm_receive = MSG_task_irecv(&task_received, node->mailbox); } - res = MSG_comm_wait(node->comm_receive, TIMEOUT); + 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", 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 { @@ -700,15 +747,15 @@ static int remote_get_predecessor(node_t node, int ask_to) task_received, ask_to, ans_data->answer_id); predecessor_id = ans_data->answer_id; stop = 1; + MSG_comm_destroy(node->comm_receive); + node->comm_receive = NULL; MSG_task_destroy(task_received); task_data_destroy(req_data); } } - node->comm_receive = NULL; } while (!stop); } - xbt_free(mailbox); return predecessor_id; } @@ -722,7 +769,7 @@ static int remote_get_predecessor(node_t node, int ask_to) int closest_preceding_node(node_t node, int id) { int i; - for (i = NB_BITS - 1; i >= 0; i--) { + for (i = nb_bits - 1; i >= 0; i--) { if (is_in_interval(node->fingers[i].id, node->id + 1, id - 1)) { return node->fingers[i].id; } @@ -789,15 +836,14 @@ static void remote_notify(node_t node, int notify_id, int predecessor_candidate_ req_data->type = TASK_NOTIFY; req_data->request_id = predecessor_candidate_id; req_data->issuer_host_name = MSG_host_get_name(MSG_host_self()); - req_data->answer_to = NULL; // 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); - char* mailbox = get_mailbox(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); - xbt_free(mailbox); } /** @@ -816,7 +862,7 @@ static void fix_fingers(node_t node) { set_finger(node, i, id); print_finger_table(node); } - node->next_finger_to_fix = (i + 1) % NB_BITS; + node->next_finger_to_fix = (i + 1) % nb_bits; } } @@ -831,23 +877,57 @@ static void check_predecessor(node_t node) // TODO } +/** + * \brief Performs a find successor request to a random id. + * \param node the current 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); + find_successor(node, id); +} + /** * \brief Main function. */ int main(int argc, char *argv[]) { if (argc < 3) { - printf("Usage: %s platform_file deployment_file\n", argv[0]); + printf("Usage: %s [-nb_bits=n] [-timeout=t] platform_file deployment_file\n", argv[0]); printf("example: %s ../msg_platform.xml chord.xml\n", argv[0]); exit(1); } - const char* platform_file = argv[1]; - const char* application_file = argv[2]; + MSG_global_init(&argc, argv); + + char **options = &argv[1]; + while (!strncmp(options[0], "-", 1)) { + + 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); + } + 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); + } + else { + xbt_assert1(0, "Invalid chord option '%s'", options[0]); + } + } + options++; + } + + const char* platform_file = options[0]; + const char* application_file = options[1]; chord_initialize(); - MSG_global_init(&argc, argv); MSG_set_channel_number(0); MSG_create_environment(platform_file);