From 152943e8fe145f156e28ae9834b934a8e02471bc Mon Sep 17 00:00:00 2001 From: thiery Date: Thu, 9 Dec 2010 10:10:55 +0000 Subject: [PATCH] Working on Chord git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@9103 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- examples/msg/chord/chord.c | 692 ++++++++++++++++++++++------------- examples/msg/chord/chord.xml | 52 +-- 2 files changed, 445 insertions(+), 299 deletions(-) diff --git a/examples/msg/chord/chord.c b/examples/msg/chord/chord.c index 38728bdb13..e44aed8b85 100644 --- a/examples/msg/chord/chord.c +++ b/examples/msg/chord/chord.c @@ -5,269 +5,349 @@ * under the terms of the license (GNU LGPL) which comes with this package. */ #include -#include #include "msg/msg.h" -#include "xbt/sysdep.h" /* calloc, printf */ - -/* Create a log channel to have nice outputs. */ #include "xbt/log.h" #include "xbt/asserts.h" -XBT_LOG_NEW_DEFAULT_CATEGORY(msg_test, +XBT_LOG_NEW_DEFAULT_CATEGORY(msg_chord, "Messages specific for this msg example"); -#define KEY_BITS 6 -#define CHORD_NB_KEYS 64 -/* -* Finger Element -*/ -typedef struct{ - int id; - const char *host_name; - const char *mailbox; -} finger_elem; +#define NB_BITS 6 +#define NB_KEYS 64 -/* - * Node Data +/** + * Finger element. */ -typedef struct{ - int id; // my id - const char *host_name; //my host name - const char* mailbox; //my mailbox - int fingers_nb; // size of finger list - finger_elem* fingers; // finger list [ fingers[0] >> Successor - int next; //next finger to fix - int pred_id; // predecessor id - const char* pred_host_name; // predecessor host name - const char* pred_mailbox; // predecessor mailbox -}data_node; - -//global; +typedef struct finger { + int id; + const char* mailbox; +} s_finger_t, *finger_t; +/** + * Node data. + */ +typedef struct node { + int id; // my id + const char* mailbox; + s_finger_t fingers[NB_BITS]; // finger table (fingers[0] is my successor) + int pred_id; // predecessor id + const char* pred_mailbox; +} s_node_t, *node_t; + +/** + * Task data + */ +typedef struct task_data { + int request_id; + int request_finger; + int answer_id; + const char* answer_to; +} s_task_data_t, *task_data_t; + +// utility functions +static int normalize(int id); +static int is_in_interval(int id, int start, int end); +static char* get_mailbox(int host_id); + +// process functions static int node(int argc, char *argv[]); static int sender(int argc,char *argv[]); -static void find_successor_node(data_node *my_data, m_task_t join_task); -static int find_successor(data_node* my_data, int id); -static const char* find_closest_preceding(data_node* n_node, int id); //return a mailbox -static int get_successor_id(m_host_t); -static MSG_error_t test_all(const char *platform_file, - const char *application_file); -static void init_finger_table(data_node *data, int known_id); +// initialization +static void initialize_first_node(node_t node); +static void initialize_finger_table(node_t data, int known_id); +static void join(node_t node, int known_id); + +// Chord core +static int find_successor(node_t node, int id); +static int remote_find_successor(node_t node, int ask_to_id, int id); +static int find_predecessor(node_t node, int id); +static int remote_find_predecessor(node_t node, int ask_to_id, int id); +static int closest_preceding_finger(node_t node, int id); +static int remote_closest_preceding_finger(int ask_to_id, int id); +static void notify(node_t); +static void remote_move_keys(node_t node, int take_from_id); +static void update_finger_table(node_t node, int candidate_id, int finger_index); +static void remote_update_finger_table(int ask_to_id, int candidate_id, int finger_index); + +//static void find_successor_node(node_t my_data, m_task_t join_task); + +/** + * \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) { -static int is_in_interval(unsigned int id, unsigned int start, unsigned int end) { + // make sure id >= 0 + while (id < 0) { + id += NB_KEYS; + } + + // make sure id < NB_KEYS + id = id % NB_KEYS; - id = id % CHORD_NB_KEYS; - start = start % CHORD_NB_KEYS; - end = end % CHORD_NB_KEYS; + return id; +} - /* make sure end >= start and id >= start */ +/** + * \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). + * 1 belongs to [62, 3] + * 1 does not belong to [3, 62] + * 63 belongs to [62, 3] + * 63 does not belong to [3, 62] + * 24 belongs to [21, 29] + * 24 does not belong to [29, 21] + * + * \param id id to check + * \param start lower bound + * \param end upper bound + * \return a non-zero value if id in in [start, end] + */ +static int is_in_interval(int id, int start, int end) { + + id = normalize(id); + start = normalize(start); + end = normalize(end); + + // make sure end >= start and id >= start if (end < start) { - end += CHORD_NB_KEYS; + end += NB_KEYS; } if (id < start) { - id += CHORD_NB_KEYS; + id += NB_KEYS; } - return id < end; + return id <= end; } -/* - * Node Function +/** + * \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 + * FIXME: free the memory */ +static char* get_mailbox(int node_id) { -/* - - - - - - >argument value="time_to_sleep"/> - -*/ -static int cpt = 0; + return bprintf("mailbox%d", node_id); +} + +/** + * \brief Node Function + * Arguments: + * - my id + * - the id of a guy I know in the system (except for the first node) + * - the time to sleep before I join (except for the first node) + */ int node(int argc, char *argv[]) { - m_task_t recv_request = NULL; - int first = 1; - int joined = 0; - int res,create = 0; - if ( argc == 3) // if no known host are declared >>> first node >>> create chord ring - { - create = 1; - } + xbt_assert0(argc == 2 || argc == 4, "Wrong number of arguments for this node"); - //int id = atoi(argv[1]); - //int mailbox = atoi(argv[2]); - // init data node - data_node *data = xbt_new(data_node,1); - data->host_name = MSG_host_get_name(MSG_host_self()); - data->id = atoi(argv[1]); - data->mailbox = argv[2]; - data->fingers_nb = 1; - data->fingers = xbt_new(finger_elem,KEY_BITS); - data->fingers[0].host_name = data->host_name; - data->fingers[0].id = data->id; - data->fingers[0].mailbox = data->mailbox; - data->next = 0; - data->pred_host_name = NULL; - data->pred_id = -1; - data->pred_mailbox = NULL; + // initialize my node + s_node_t node = {0}; + node.id = atoi(argv[1]); + node.mailbox = get_mailbox(node.id); -/* - * Ring Point Entry Node + if (argc == 2) { // first ring + initialize_first_node(&node); + } + else { + int known_id = atoi(argv[2]); + double sleep_time = atof(argv[3]); + + // sleep before starting + INFO1("Let's sleep >>%f", sleep_time); + MSG_process_sleep(sleep_time); + INFO0("Hey! Let's join the system."); + + join(&node, known_id); + } + + while (1) { + + m_task_t task = NULL; + MSG_error_t res = MSG_task_receive(&task, node.mailbox); + + xbt_assert0(res == MSG_OK, "MSG_task_receive failed"); + + // get data + const char* task_name = MSG_task_get_name(task); + task_data_t task_data = (task_data_t) MSG_task_get_data(task); + + if (!strcmp(task_name, "Find Successor")) { + + // is my successor the successor? + if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) { + task_data->answer_id = node.fingers[0].id; + MSG_task_set_name(task, "Find Successor Answer"); + MSG_task_send(task, task_data->answer_to); + } + else { + // otherwise, forward the request to the closest preceding finger in my table + int closest = closest_preceding_finger(&node, task_data->request_id); + MSG_task_send(task, get_mailbox(closest)); + } + } + /* + else if (!strcmp(task_name, "Find Successor Answer")) { + + } + */ + else if (!strcmp(task_name, "Find Predecessor")) { + + // am I the predecessor? + if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) { + task_data->answer_id = node.id; + MSG_task_set_name(task, "Find Predecessor Answer"); + MSG_task_send(task, task_data->answer_to); + } + else { + // otherwise, forward the request to the closest preceding finger in my table + int closest = closest_preceding_finger(&node, task_data->request_id); + MSG_task_send(task, get_mailbox(closest)); + } + } + /* + else if (!strcmp(task_name, "Find Predecessor Answer")) { + + } + */ + else if (!strcmp(task_name, "Update Finger")) { + update_finger_table(&node, task_data->request_id, task_data->request_finger); + } + /* + else if (!strcmp(task_name, "Fix Fingers")) + { + int i; + for (i = KEY_BITS - 1 ; i >= 0; i--) + { + data->fingers[i] = find_finger_elem(data,(data->id)+pow(2,i-1)); + } + } + */ + } +} + +/** + * \brief Initializes the current node as the first one of the system. + * \param node the current node */ - if (create) // first ring - { - INFO0("Create new Chord Ring..."); - joined = 1; - cpt++; - //sucessor = n - data->fingers[0].host_name = data->host_name; - data->fingers[0].id = data->id; - data->fingers[0].mailbox = data->mailbox; - while(cpt < MSG_get_host_number()-1) //make condition!!! - { - recv_request = NULL; - res = MSG_task_receive(&(recv_request),data->mailbox); - xbt_assert0(res == MSG_OK, "MSG_receiev failed"); - if (!strcmp(MSG_task_get_name(recv_request), "Join Call")) - { - if(MSG_task_get_data(recv_request)==NULL) - { - WARN0("Receiving an Empty Data"); - } - data_node *recv_data = (data_node*)MSG_task_get_data(recv_request); - INFO1("Receiving a Join Call from %s",recv_data->host_name); - if (first) - { - // predecessor(recv_data) >>>> data - recv_data->pred_host_name = data->host_name; - recv_data->pred_id = data->id; - recv_data->pred_mailbox = data->mailbox; - data->fingers_nb = 1; - // successor(recv_data) >>> data - recv_data->fingers[0].id = data->id; - recv_data->fingers[0].host_name = data->host_name; - recv_data->fingers[0].mailbox = data->mailbox; - //successor(data) >>>> recv_data - data->fingers[data->fingers_nb - 1].host_name = recv_data->host_name; - data->fingers[data->fingers_nb - 1].id = recv_data->id; - data->fingers[data->fingers_nb - 1].mailbox = recv_data->mailbox; - INFO1("Sending back a Join Request to %s",recv_data->host_name); - MSG_task_set_name(recv_request,"Join Response"); - MSG_task_send(recv_request,recv_data->mailbox); - first = 0; - } - else{ - find_successor_node(data,recv_request); - } - - } - } - } -/* - * Joining Node +static void initialize_first_node(node_t node) +{ + INFO0("Create a new Chord ring..."); + + // I am my own successor and predecessor + int i; + for (i = 0; i < NB_BITS; i++) { + node->fingers[i].id = node->id; + node->fingers[i].mailbox = node->mailbox; + } + node->pred_id = node->id; + node->pred_mailbox = node->mailbox; +} + +/** + * \brief Makes the current node join the system, knowing the id of a node already in the system + * \param node the current node + * \param known_id id of a node already in the system */ - else if(!create) - { - //Sleep Before Starting - INFO1("Let's Sleep >>%i",atoi(argv[6])); - MSG_process_sleep(atoi(argv[5])); - INFO0("Hey! Let's Send a Join Request"); - //send a join task to the known host via its(known host) mailbox - const char* known_host_name = argv[3]; - const char* known_mailbox = argv[4]; - int known_id = atoi(argv[5]); - m_task_t join_request = MSG_task_create("Join Call",10000,2000,data); // define comp size and comm size (#define ...) - INFO2("Sending a join request to %s via mailbox %s",known_host_name,known_mailbox); - MSG_task_send(join_request,known_mailbox); - //wait for answer on my mailbox - while(cpt < MSG_get_host_number()-1) - { - recv_request = NULL; - int res = MSG_task_receive(&(recv_request),data->mailbox); - //check if it's the response for my request - xbt_assert0(res == MSG_OK, "MSG_receiev failed"); - // get data - data_node *recv_data = (data_node*)MSG_task_get_data(recv_request); - // Join Call Message - if(!strcmp(MSG_task_get_name(recv_request), "Join Call")) - { - - INFO1("Receiving Join Call From %s",recv_data->host_name); - if(!joined) - { - INFO1("Sorry %s... I'm not yet joined",recv_data->host_name); - //No Treatment - MSG_task_set_name(recv_request,"Join Failed"); - MSG_task_send(recv_request,recv_data->mailbox); - } - else - { - find_successor_node(data,recv_request); - } - - } - // Join Response - else if(!strcmp(MSG_task_get_name(recv_request), "Join Response")) - { - INFO0("Receiving Join Response!!!"); - INFO1("My successor is : %s",data->fingers[0].host_name); - INFO1("My Predecessor is : %s",data->pred_host_name); - cpt++; - joined = 1; - INFO1("My finger table size : %i",data->fingers_nb); - INFO0("***********************************************************************"); - - /* - MSG_task_set_name(recv_request,"Fix Fingers"); - - MSG_task_send(recv_request,data->pred_mailbox); - MSG_task_send(recv_request,data->fingers[0].mailbox); - */ - init_finger_table(data, known_id); - - //treatment - } - // Join Failure Message - else if(!strcmp(MSG_task_get_name(recv_request), "Join Failed")) - { - INFO0("My Join call has failed... let's Try Again"); - // send back - //MSG_task_send(join_request,known_mailbox); - // !!!!!!!!! YVes Jaques Always...???§§§§************************** - - } - else if(!strcmp(MSG_task_get_name(recv_request), "Fix Fingers")) - { - int i; - for(i = KEY_BITS -1 ; i>= 0;i--) - { - //data->fingers[i] = find_finger_elem(data,(data->id)+pow(2,i-1)); - } - } - } - } - return 0; +static void join(node_t node, int known_id) +{ + initialize_finger_table(node, known_id); // determine my fingers, asking to known_id + notify(node); // tell others that I may have became their finger + remote_move_keys(node, node->fingers[0].id); // take some key-value pairs from my sucessor } /* - * Initializes + * \brief Initializes my finger table, knowing the id of a node already in the system. + * \param node the current node + * \param known_id id of a node already in the system */ -void init_finger_table(data_node *node, int known_id) { +static void initialize_finger_table(node_t node, int known_id) +{ + int my_id = node->id; + int i; + int pow = 1; // 2^i // ask known_id who is my immediate successor -// data->fingers[0].id = remote_find_successor(known_id, data->id + 1); + node->fingers[0].id = remote_find_successor(node, known_id, my_id + 1); + node->fingers[0].mailbox = get_mailbox(node->fingers[0].id); + + // find all other fingers + for (i = 0; i < NB_BITS - 1; i++) { + + pow = pow << 1; // equivalent to pow = pow * 2 + if (is_in_interval(my_id + pow, my_id, node->fingers[i].id - 1)) { + // I already have the info for this finger + node->fingers[i + 1].id = node->fingers[i].id; + } + else { + // I don't have the info, ask the only guy I know + node->fingers[i + 1].id = remote_find_successor(node, known_id, my_id + pow); + } + node->fingers[i + 1].mailbox = get_mailbox(node->fingers[i + 1].id); + } } -/* - * +/** + * \brief Notifies some nodes that the current node may have became their finger. + * \param node the current node, which has just joined the system */ -void find_successor_node(data_node* n_data,m_task_t join_task) //use all data +static void notify(node_t node) +{ + int i, pred_id; + int pow = 1; + for (i = 0; i < NB_KEYS; i++) { + // find the closest node whose finger #i can be me + pred_id = find_predecessor(node, node->id - pow); + remote_update_finger_table(pred_id, node->id, i); + pow = pow << 1; // pow = pow * 2 + } +} + +/** + * \brief Tells the current node that a node may have became its new finger. + * \param node the current node + * \param candidate_id id of the node that may be a new finger of the current node + * \param finger_index index of the finger to update + */ +static void update_finger_table(node_t node, int candidate_id, int finger_index) +{ + if (is_in_interval(candidate_id, node->id, node->fingers[finger_index].id - 1)) { + + // candidate_id is my new finger + node->fingers[finger_index].id = candidate_id; + node->fingers[finger_index].mailbox = get_mailbox(candidate_id); + + // my predecessor may be concerned too + remote_update_finger_table(node->pred_id, candidate_id, finger_index); + } +} + +/** + * \brief Tells a remote node that a node may have became its new finger. + * \param ask_to_id id of the remote node to update + * \param candidate_id id of the node that may be a new finger of the remote node + * \param finger_index index of the finger to update + */ +static void remote_update_finger_table(int ask_to_id, int candidate_id, int finger_index) +{ + s_task_data_t req_data; + req_data.request_id = candidate_id; + req_data.request_finger = finger_index; + + // send a "Update Finger" request to ask_to_id + m_task_t task = MSG_task_create("Update Finger", 1000, 5000, &req_data); + MSG_task_send(task, get_mailbox(ask_to_id)); +} + +/* deprecated version where the remote host modifies the issuer's node data +static void find_successor_node(node_t n_data,m_task_t join_task) //use all data { //get recv data - data_node *recv_data = (data_node*)MSG_task_get_data(join_task); + node_t recv_data = (node_t)MSG_task_get_data(join_task); INFO3("recv_data->id : %i , n_data->id :%i , successor->id :%i",recv_data->id,n_data->id,n_data->fingers[0].id); //if ((recv_data->id >= n_data->id) && (recv_data->id <= n_data->fingers[0].id)) if (is_in_interval(recv_data->id,n_data->id,n_data->fingers[0].id)) @@ -299,69 +379,157 @@ void find_successor_node(data_node* n_data,m_task_t join_task) //use all data MSG_task_send(join_task,closest_preceding_mailbox); } } +*/ -const char* find_closest_preceding(data_node* n_node,int id) +/** + * \brief Makes the current node find the successor node of an id. + * \param node the current node + * \param id the id to find + * \return the id of the successor node + */ +static int find_successor(node_t node, int id) { - int i; - for(i = n_node->fingers_nb-1; i >= 0 ; i--) - { - if (n_node->fingers[i].id <= id) - return n_node->fingers[i].mailbox; - } + // is my successor the successor? + if (is_in_interval(id, node->id + 1, node->fingers[0].id)) { + return node->fingers[0].id; + } - return n_node->mailbox; // !!!!!!!!!!!!!! + // otherwise, ask the closest preceding finger in my table + int closest = closest_preceding_finger(node, id); + return remote_find_successor(node, closest, id); } -/* - * Fin successor id : used to fix finger list + +/** + * \brief Asks another node the successor node of an id. + * \param node the current node + * \param ask_to the node to ask to + * \param id the id to find + * \return the id of the successor node */ -static int find_successor(data_node* n_data, int id) +static int remote_find_successor(node_t node, int ask_to, int id) { - if (is_in_interval(id,n_data->id,n_data->fingers[0].id)) - return n_data->fingers[0].id; - else - return 0; - + s_task_data_t req_data; + req_data.request_id = id; + req_data.answer_to = node->mailbox; + + // send a "Find Successor" request to ask_to_id + m_task_t task = MSG_task_create("Find Successor", 1000, 5000, &req_data); + MSG_task_send(task, get_mailbox(ask_to)); + + // receive the answer + task = NULL; + MSG_task_receive(&task, node->mailbox); // FIXME: don't receive here other messages than the excepted one + task_data_t ans_data; + ans_data = MSG_task_get_data(task); + int successor = ans_data->answer_id; + + return successor; } - -/** Test function */ -MSG_error_t test_all(const char *platform_file, - const char *application_file) +/** + * \brief Makes the current node find the predecessor node of an id. + * \param node the current node + * \param id the id to find + * \return the id of the predecessor node + */ +static int find_predecessor(node_t node, int id) { - MSG_error_t res = MSG_OK; - - /* MSG_config("workstation/model","KCCFLN05"); */ - { /* Simulation setting */ - MSG_set_channel_number(0); - MSG_create_environment(platform_file); + if (node->id == node->fingers[0].id) { + // I am the only node in the system + return node->id; + } + if (is_in_interval(id, node->id + 1, node->fingers[0].id)) { + return node->id; } - { /* Application deployment */ - MSG_function_register("node",node); - MSG_launch_application(application_file); + int ask_to = closest_preceding_finger(node, id); + return remote_find_predecessor(node, ask_to, id); +} + +/** + * \brief Asks another node the predecessor node of an id. + * \param node the current node + * \param ask_to the node to ask to + * \param id the id to find + * \return the id of the predecessor node + */ +static int remote_find_predecessor(node_t node, int ask_to, int id) +{ + s_task_data_t req_data; + req_data.request_id = id; + req_data.answer_to = node->mailbox; + + // send a "Find Predecessor" request to ask_to + m_task_t task = MSG_task_create("Find Predecessor", 1000, 5000, &req_data); + MSG_task_send(task, get_mailbox(ask_to)); + + // receive the answer + task = NULL; + MSG_task_receive(&task, node->mailbox); // FIXME: don't receive here other messages than the excepted one + task_data_t ans_data; + ans_data = MSG_task_get_data(task); + int predecessor = ans_data->answer_id; + + return predecessor; +} + +/** + * \brief Returns the closest preceding finger of an id + * with respect to the finger table of the current node. + * \param node the current node + * \param id the id to find + * \return the closest preceding finger of that id + */ +int closest_preceding_finger(node_t node, int id) +{ + int 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; + } } - res = MSG_main(); - INFO1("Simulation time %g", MSG_get_clock()); + return node->id; +} - return res; -} /* end_of_test_all */ +/** + * \brief Asks a node to take some of its keys. + * \param node the current node, which has just joined the system + * \param take_from_id id of a node who may have keys to give to the current node + */ +static void remote_move_keys(node_t node, int take_from_id) { + // TODO +} -/** Main function */ +/** + * \brief Main function. + */ int main(int argc, char *argv[]) { - MSG_error_t res = MSG_OK; - - MSG_global_init(&argc, argv); if (argc < 3) { printf("Usage: %s platform_file deployment_file\n", argv[0]); - printf("example: %s msg_platform.xml msg_deployment.xml\n", argv[0]); + printf("example: %s ../msg_platform.xml chord.xml\n", argv[0]); exit(1); } - res = test_all(argv[1], argv[2]); + + MSG_global_init(&argc, argv); + + const char* platform_file = argv[1]; + const char* application_file = argv[2]; + + /* MSG_config("workstation/model","KCCFLN05"); */ + MSG_set_channel_number(0); + MSG_create_environment(platform_file); + + MSG_function_register("node", node); + MSG_launch_application(application_file); + + MSG_error_t res = MSG_main(); + INFO1("Simulation time: %g", MSG_get_clock()); + MSG_clean(); if (res == MSG_OK) return 0; else return 1; -} /* end_of_main */ +} diff --git a/examples/msg/chord/chord.xml b/examples/msg/chord/chord.xml index 5727b6b60a..18ffb265cd 100644 --- a/examples/msg/chord/chord.xml +++ b/examples/msg/chord/chord.xml @@ -3,72 +3,50 @@ - - - - + - + - - - - + - + - - - - + - + - - - - + - + - - - - + - + - - - - + - + - - - - + - + - - + -- 2.20.1