Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
2b6efe9703d1dab0e581a495d92874eeba80c30f
[simgrid.git] / examples / msg / pastry / pastry.c
1 /* Copyright (c) 2013-2015. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 #include <math.h>
8 #include "simgrid/msg.h"
9
10  XBT_LOG_NEW_DEFAULT_CATEGORY(msg_pastry, "Messages specific for this msg example");
11
12 /***************************************
13  * PASTRY                              *
14  *                                     *
15  * TODO:                               *
16  *  - handle node departure            *
17  *  - handle objects on the network    *
18  *  - handle neighborood in the update *
19  *                                     *
20  ***************************************/
21
22 #define COMM_SIZE 10
23 #define COMP_SIZE 0
24 #define MAILBOX_NAME_SIZE 10
25
26 #define DOMAIN_SIZE 4
27 #define LEVELS_COUNT 8 // sizeof(int)*8/DOMAIN_SIZE
28 #define LEVEL_SIZE 16 // 2^DOMAIN_SIZE
29 #define NEIGHBORHOOD_SIZE 6
30 #define NAMESPACE_SIZE 6
31 #define MAILBOX_NAME_SIZE 10
32
33 static int nb_bits = 16;
34 static int timeout = 50;
35 static int max_simulation_time = 1000;
36
37 extern long int smx_total_comms;
38
39 typedef struct s_node {
40   int id;                                 //128bits generated random(2^128 -1)
41   int known_id;
42   char mailbox[MAILBOX_NAME_SIZE];        // my mailbox name (string representation of the id)
43   int namespace_set[NAMESPACE_SIZE];
44   int neighborhood_set[NEIGHBORHOOD_SIZE];
45   int routing_table[LEVELS_COUNT][LEVEL_SIZE];
46   int ready;
47   msg_comm_t comm_receive;                // current communication to receive
48   xbt_fifo_t pending_tasks;
49 } s_node_t, *node_t;
50
51 typedef struct s_state {
52   int id;
53   int namespace_set[NAMESPACE_SIZE];
54   int neighborhood_set[NEIGHBORHOOD_SIZE];
55   int routing_table[LEVELS_COUNT][LEVEL_SIZE];
56 } s_state_t, *state_t;
57
58 /** Types of tasks exchanged between nodes. */
59 typedef enum {
60   TASK_JOIN,
61   TASK_JOIN_REPLY,
62   TASK_JOIN_LAST_REPLY,
63   TASK_UPDATE
64 } e_task_type_t;
65
66 typedef struct s_task_data {
67   e_task_type_t type;                     // type of task
68   int sender_id;                          // id paramater (used by some types of tasks)
69   //int request_finger;                     // finger parameter (used by some types of tasks)
70   int answer_id;                          // answer (used by some types of tasks)
71   char answer_to[MAILBOX_NAME_SIZE];      // mailbox to send an answer to (if any)
72   //const char* issuer_host_name;           // used for logging
73   int steps;
74   state_t state;
75 } s_task_data_t, *task_data_t;
76
77
78 static void print_node(node_t node);
79 static void print_node_id(node_t node);
80 static void print_node_neighborood_set(node_t node);
81 static void print_node_routing_table(node_t node);
82 static void print_node_namespace_set(node_t node);
83 static state_t node_get_state(node_t node);
84 static void get_mailbox(int node_id, char* mailbox);
85 static int domain(int a, int level);
86 static int shl(int a, int b);
87 static int closest_in_namespace_set(node_t node, int dest);
88 static int routing_next(node_t node, int dest);
89 static void create(node_t node);
90 static int join(node_t node);
91
92 /**
93  * \brief Gets the mailbox name of a host given its chord id.
94  * \param node_id id of a node
95  * \param mailbox pointer to where the mailbox name should be written
96  * (there must be enough space)
97  */
98 static void get_mailbox(int node_id, char* mailbox)
99 {
100   snprintf(mailbox, MAILBOX_NAME_SIZE - 1, "%d", node_id);
101 }
102
103 /**
104  * Get the specific level of a node id
105  */
106 int domain_mask = 0;
107 static int domain(int a, int level) {
108   if (domain_mask == 0)
109     domain_mask = pow(2, DOMAIN_SIZE) - 1;
110   int shift = (LEVELS_COUNT-level-1)*DOMAIN_SIZE;
111   return (a >> shift) & domain_mask;
112 }
113
114 /**
115  * Get the shared domains between the two givens ids
116  */
117 static int shl(int a, int b) {
118   int l = 0;
119   while(l<LEVELS_COUNT && domain(a,l) == domain(b,l))
120     l++;
121   return l;
122 }
123
124 /*
125  * Get the closest id to the dest in the node namespace_set
126  */
127 static int closest_in_namespace_set(node_t node, int dest) {
128   int best_dist;
129   int res = -1;
130   if ((node->namespace_set[NAMESPACE_SIZE-1] <= dest) & (dest <= node->namespace_set[0])) {
131     best_dist = abs(node->id - dest);
132     res = node->id;
133     int i, dist;
134     for (i=0; i<NAMESPACE_SIZE; i++) {
135       if (node->namespace_set[i]!=-1) {
136   dist = abs(node->namespace_set[i] - dest);
137   if (dist<best_dist) {
138     best_dist = dist;
139           res = node->namespace_set[i];    
140   }
141       }
142     }
143   }
144   return res;
145 }
146
147 /*
148  * Find the next node to forward a meassage to
149  */
150 static int routing_next(node_t node, int dest) {
151   int closest = closest_in_namespace_set(node, dest);
152   int res = -1;
153   if (closest!=-1)
154     return closest;
155
156   int l = shl(node->id, dest);
157   res = node->routing_table[l][domain(dest, l)];
158   if (res!=-1)
159     return res;
160
161   //rare case
162   int dist = abs(node->id - dest);
163   int i,j;
164   for (i=l; i<LEVELS_COUNT; i++) {
165     for (j=0; j<LEVEL_SIZE; j++) {
166       res = node->routing_table[i][j];
167       if (res!=-1 && abs(res - dest)<dist)
168         return res;
169     }
170   }
171
172   for (i=0; i<NEIGHBORHOOD_SIZE; i++) {
173     res = node->neighborhood_set[i];
174     if (res!=-1 && shl(res, dest)>=l && abs(res - dest)<dist)
175         return res;
176   }
177
178   for (i=0; i<NAMESPACE_SIZE; i++) {
179     res = node->namespace_set[i];
180     if (res!=-1 && shl(res, dest)>=l && abs(res - dest)<dist)
181         return res;
182   }
183
184   return node->id;
185 }
186
187 /*
188  * Handle a given task
189  */
190 static void handle_task(node_t node, msg_task_t task) {
191   XBT_DEBUG("Handling task %p", task);
192   char mailbox[MAILBOX_NAME_SIZE];
193   int i, j, min, max, d;
194   msg_task_t task_sent;
195   task_data_t req_data;
196   task_data_t task_data = (task_data_t) MSG_task_get_data(task);
197   e_task_type_t type = task_data->type;
198   // If the node is not ready keep the task for later
199   if (node->ready != 0 && !(type==TASK_JOIN_LAST_REPLY || type==TASK_JOIN_REPLY)) {
200     XBT_DEBUG("Task pending %i", type);
201     xbt_fifo_push(node->pending_tasks, task);
202     return;
203   }
204   switch (type) {
205     /*
206      * Try to join the ring
207      */
208     case TASK_JOIN: {
209       int next = routing_next(node, task_data->answer_id);
210       XBT_DEBUG("Join request from %08x forwarding to %08x", task_data->answer_id, next);      
211       type = TASK_JOIN_LAST_REPLY;
212
213       req_data = xbt_new0(s_task_data_t,1);
214       req_data->answer_id = task_data->sender_id;
215       req_data->steps = task_data->steps + 1;
216       
217       // if next different from current node forward the join
218       if (next!=node->id) {
219         get_mailbox(next, mailbox);
220         task_data->sender_id = node->id;
221   task_data->steps++;
222         task_sent = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, task_data);
223         MSG_task_send_with_timeout(task_sent, mailbox, timeout);
224         type = TASK_JOIN_REPLY;
225       } 
226       
227       // send back the current node state to the joining node
228       req_data->type = type;
229       req_data->sender_id = node->id;
230       get_mailbox(node->id, req_data->answer_to);
231       req_data->state = node_get_state(node);
232       task_sent = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, req_data);
233       MSG_task_send_with_timeout(task_sent, task_data->answer_to, timeout);
234       break;
235     }
236     /*
237      * Join reply from all the node touched by the join
238      */
239     case TASK_JOIN_LAST_REPLY:
240       // if last node touched reply, copy its namespace set
241       // TODO: it's work only if the two nodes are side to side (is it really the case ?)
242       j = (task_data->sender_id < node->id) ? -1 : 0;
243       for (i=0; i<NAMESPACE_SIZE/2; i++) {
244         node->namespace_set[i] = task_data->state->namespace_set[i-j];
245         node->namespace_set[NAMESPACE_SIZE-1-i] = task_data->state->namespace_set[NAMESPACE_SIZE-1-i-j-1];
246       }
247       node->namespace_set[NAMESPACE_SIZE/2+j] = task_data->sender_id;
248       node->ready += task_data->steps + 1;
249     case TASK_JOIN_REPLY:
250       XBT_DEBUG("Joining Reply");
251
252       // if first node touched reply, copy its neighborood set
253       if (task_data->sender_id == node->known_id) {
254   node->neighborhood_set[0] = task_data->sender_id;
255         for (i=1; i<NEIGHBORHOOD_SIZE; i++)
256             node->neighborhood_set[i] = task_data->state->neighborhood_set[i-1]; 
257       }
258       
259       // copy the corresponding routing table levels
260       min = (node->id==task_data->answer_id) ? 0 : shl(node->id, task_data->answer_id);      
261       max = shl(node->id, task_data->sender_id)+1;
262       for (i=min;i<max;i++) {
263         d = domain(node->id, i); 
264         for (j=0; j<LEVEL_SIZE; j++)
265     if (d!=j)
266             node->routing_table[i][j] =  task_data->state->routing_table[i][j];
267       }
268
269       node->ready--;
270       // if the node is ready, do all the pending tasks and send update to known nodes
271       if (node->ready==0) {
272         XBT_DEBUG("Node %i is ready!!!", node->id);
273
274         while(xbt_fifo_size(node->pending_tasks))
275     handle_task(node, xbt_fifo_pop(node->pending_tasks));
276
277   for (i=0; i<NAMESPACE_SIZE; i++) {
278           j = node->namespace_set[i];
279           if (j!=-1) {
280             XBT_DEBUG("Send update to %i", j);
281             get_mailbox(j, mailbox);
282       
283       req_data = xbt_new0(s_task_data_t,1);
284             req_data->answer_id = node->id;
285             req_data->steps = 0;
286             req_data->type = TASK_UPDATE;
287             req_data->sender_id = node->id;
288             get_mailbox(node->id, req_data->answer_to);
289             req_data->state = node_get_state(node);
290             task_sent = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, req_data);
291             MSG_task_send_with_timeout(task_sent, mailbox, timeout);
292           }
293         }
294       }
295       break;
296       
297     /*
298      * Recieved an update of state
299      */
300     case TASK_UPDATE:
301       XBT_DEBUG("Task update %i !!!", node->id);
302
303       /* Update namespace ses */
304       printf("Task update from %i !!!\n", task_data->sender_id);
305       print_node_id(node);
306       print_node_namespace_set(node);
307       int curr_namespace_set[NAMESPACE_SIZE];
308       int task_namespace_set[NAMESPACE_SIZE+1];
309       
310       // Copy the current namedspace
311       // and the task state namespace with state->id in the middle
312       i=0;
313       for (; i<NAMESPACE_SIZE/2; i++){
314         curr_namespace_set[i] = node->namespace_set[i];
315   task_namespace_set[i] = task_data->state->namespace_set[i];
316       }
317       task_namespace_set[i] = task_data->state->id;
318       for (; i<NAMESPACE_SIZE; i++){
319         curr_namespace_set[i] = node->namespace_set[i];  
320   task_namespace_set[i+1] = task_data->state->namespace_set[i];  
321       }
322
323       // get the index of values before and after node->id in task_namespace
324       min = -1;
325       max = -1;
326       for (i=0; i<=NAMESPACE_SIZE; i++) {
327   j = task_namespace_set[i];
328         if (i<NAMESPACE_SIZE)
329     printf("%08x %08x | ", j, curr_namespace_set[i]);
330   if (j != -1 && j < node->id) min = i;
331   if (j != -1 && max == -1 && j > node->id) max = i;
332       }
333       printf("\n");
334
335       // add lower elements
336       j = NAMESPACE_SIZE/2-1;
337       for (i=NAMESPACE_SIZE/2-1; i>=0; i--) {
338   printf("i:%i, j:%i, min:%i, currj:%08x, taskmin:%08x\n", i, j, min, curr_namespace_set[j], task_namespace_set[min]);
339         if (min<0) {
340     node->namespace_set[i] = curr_namespace_set[j];
341     j--; 
342   } else if (curr_namespace_set[j] == task_namespace_set[min]) {
343     node->namespace_set[i] = curr_namespace_set[j];
344     j--; min--;
345   } else if (curr_namespace_set[j] > task_namespace_set[min]) {
346           node->namespace_set[i] = curr_namespace_set[j];
347     j--;
348   } else {
349           node->namespace_set[i] = task_namespace_set[min];
350     min--;
351   }
352       }
353
354       // add greater elements
355       j = NAMESPACE_SIZE/2;
356       for (i=NAMESPACE_SIZE/2; i<NAMESPACE_SIZE; i++) {
357   printf("i:%i, j:%i, max:%i, currj:%08x, taskmax:%08x\n", i, j, max, curr_namespace_set[j], task_namespace_set[max]);        
358         if (min<0 || max>=NAMESPACE_SIZE) {
359     node->namespace_set[i] = curr_namespace_set[j];
360     j++;
361   } else if (curr_namespace_set[j] == -1) {
362     node->namespace_set[i] = task_namespace_set[max];
363     max++;
364   } else if (curr_namespace_set[j] == task_namespace_set[max]) {
365     node->namespace_set[i] = curr_namespace_set[j];
366     j++; max++;
367   } else if (curr_namespace_set[j] < task_namespace_set[max]) {
368           node->namespace_set[i] = curr_namespace_set[j];
369     j++;
370   } else {
371           node->namespace_set[i] = task_namespace_set[max];
372     max++;
373   }
374       }
375       print_node_namespace_set(node);
376
377       /* Update routing table */
378       for (i=shl(node->id, task_data->state->id); i<LEVELS_COUNT; i++) {
379         for (j=0; j<LEVEL_SIZE; j++) {
380           if (node->routing_table[i][j]==-1 && task_data->state->routing_table[i][j]==-1)
381             node->routing_table[i][j] = task_data->state->routing_table[i][j];
382         }
383       }
384   }         
385 }
386
387 /**
388  * \brief Initializes the current node as the first one of the system.
389  * \param node the current node
390  */
391 static void create(node_t node){
392   node->ready = 0;
393   XBT_DEBUG("Create a new Pastry ring...");
394 }
395
396 /*
397  * Join the ring
398  */
399 static int join(node_t node){
400   task_data_t req_data = xbt_new0(s_task_data_t,1);
401   req_data->type = TASK_JOIN;
402   req_data->sender_id = node->id;
403   req_data->answer_id = node->id;
404   req_data->steps = 0;
405   get_mailbox(node->id, req_data->answer_to);
406
407   char mailbox[MAILBOX_NAME_SIZE];
408   get_mailbox(node->known_id, mailbox);
409
410   msg_task_t task_sent = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, req_data);
411   XBT_DEBUG("Trying to join Pastry ring... (with node %s)", mailbox);
412   MSG_task_send_with_timeout(task_sent, mailbox, timeout);
413
414   return 1;
415 }
416
417 /*
418  * Print the node infomation
419  */
420 static void print_node(node_t node) {
421   printf("Node:\n");
422   print_node_id(node);
423   print_node_neighborood_set(node);
424   print_node_routing_table(node);
425   print_node_namespace_set(node);
426 }
427
428 /*
429  * Print the node id
430  */
431 static void print_node_id(node_t node) {
432   int i;  
433   printf(" id: %i '%08x' ", node->id, node->id);
434   for (i=0;i<LEVELS_COUNT;i++)
435     printf(" %x", domain(node->id, i));
436   printf("\n");
437 }
438
439 /*
440  * Print the node neighborood set
441  */
442 static void print_node_neighborood_set(node_t node) {
443   int i;  
444   printf(" neighborood:\n");
445   for (i=0; i<NEIGHBORHOOD_SIZE; i++)
446     printf("  %08x\n", node->neighborhood_set[i]);
447 }
448
449 /*
450  * Print the routing table
451  */
452 static void print_node_routing_table(node_t node) {
453   int i,j;  
454   printf(" routing table:\n");
455   for (i=0; i<LEVELS_COUNT; i++){
456     printf("  ");
457     for (j=0; j<LEVEL_SIZE; j++)
458       printf("%08x ", node->routing_table[i][j]);
459     printf("\n");
460   }
461 }
462
463 /*
464  * Print the node namespace set
465  */
466 static void print_node_namespace_set(node_t node) {
467   int i;
468   printf(" namespace:\n");
469   for (i=0; i<NAMESPACE_SIZE; i++)
470     printf("  %08x\n", node->namespace_set[i]);
471   printf("\n");
472
473 }
474
475 /*
476  * Get the corresponding state of a node
477  */
478 static state_t node_get_state(node_t node) {
479   int i,j;  
480   state_t state = xbt_new0(s_state_t,1);
481   state->id = node->id;
482   for (i=0; i<NEIGHBORHOOD_SIZE; i++)
483     state->neighborhood_set[i] = node->neighborhood_set[i];
484
485   for (i=0; i<LEVELS_COUNT; i++)
486     for (j=0; j<LEVEL_SIZE; j++)
487       state->routing_table[i][j] = node->routing_table[i][j];
488
489   for (i=0; i<NAMESPACE_SIZE; i++)
490     state->namespace_set[i] = node->namespace_set[i];
491
492   return state;
493 }
494
495
496 /**
497  * \brief Node Function
498  * Arguments:
499  * - my id
500  * - the id of a guy I know in the system (except for the first node)
501  * - the time to sleep before I join (except for the first node)
502  * - the deadline time
503  */
504 static int node(int argc, char *argv[])
505 {
506   double init_time = MSG_get_clock();
507   msg_task_t task_received = NULL;  
508   int join_success = 0;  
509   double deadline;
510   xbt_assert(argc == 3 || argc == 5, "Wrong number of arguments for this node");
511   s_node_t node = {0};
512   node.id = xbt_str_parse_int(argv[1], "Invalid ID: %s");
513   node.known_id = -1;
514   node.ready = -1;
515   node.pending_tasks = xbt_fifo_new();
516   get_mailbox(node.id, node.mailbox);
517   XBT_DEBUG("New node with id %s (%08x)", node.mailbox, node.id);
518   
519   int i,j,d;
520   for (i=0; i<LEVELS_COUNT; i++){
521     d = domain(node.id, i);
522     for (j=0; j<LEVEL_SIZE; j++)
523       node.routing_table[i][j] = (d==j) ? node.id : -1;
524   }
525
526   for (i=0; i<NEIGHBORHOOD_SIZE; i++)
527     node.neighborhood_set[i] = -1;
528
529   for (i=0; i<NAMESPACE_SIZE; i++)
530     node.namespace_set[i] = -1;
531
532   if (argc == 3) { // first ring
533     XBT_DEBUG("Hey! Let's create the system.");
534     deadline = xbt_str_parse_double(argv[2], "Invalid deadline: %s");
535     create(&node);
536     join_success = 1;
537   }
538   else {
539     node.known_id = xbt_str_parse_int(argv[2], "Invalid known ID: %s");
540     double sleep_time = xbt_str_parse_double(argv[3], "Invalid sleep time: %s");
541     deadline = xbt_str_parse_double(argv[4], "Invalid deadline: %s");
542
543     // sleep before starting
544     XBT_DEBUG("Let's sleep during %f", sleep_time);
545     MSG_process_sleep(sleep_time);
546     XBT_DEBUG("Hey! Let's join the system.");
547
548     join_success = join(&node);
549   }
550
551   if (join_success) {
552     XBT_DEBUG("Waiting ….");
553
554     while (MSG_get_clock() < init_time + deadline
555 //      && MSG_get_clock() < node.last_change_date + 1000
556         && MSG_get_clock() < max_simulation_time) {
557       if (node.comm_receive == NULL) {
558         task_received = NULL;
559         node.comm_receive = MSG_task_irecv(&task_received, node.mailbox);
560         // FIXME: do not make MSG_task_irecv() calls from several functions
561       }
562       if (!MSG_comm_test(node.comm_receive)) {
563         MSG_process_sleep(5);
564       } else {
565         // a transfer has occurred
566
567         msg_error_t status = MSG_comm_get_status(node.comm_receive);
568
569         if (status != MSG_OK) {
570           XBT_DEBUG("Failed to receive a task. Nevermind.");
571           MSG_comm_destroy(node.comm_receive);
572           node.comm_receive = NULL;
573         }
574         else {
575           // the task was successfully received
576           MSG_comm_destroy(node.comm_receive);
577           node.comm_receive = NULL;
578           handle_task(&node, task_received);
579         }
580       }
581
582     }
583     print_node(&node);
584   }
585   return 1;
586 }
587
588 /*
589  * Node data.
590  */
591 /*typedef struct s_node {
592   int id;                                 // my id
593   char mailbox[MAILBOX_NAME_SIZE];        // my mailbox name (string representation of the id)
594   s_finger_t *fingers;                    // finger table, of size nb_bits (fingers[0] is my successor)
595   int pred_id;                            // predecessor id
596   char pred_mailbox[MAILBOX_NAME_SIZE];   // predecessor's mailbox name
597   int next_finger_to_fix;                 // index of the next finger to fix in fix_fingers()
598   msg_comm_t comm_receive;                // current communication to receive
599   double last_change_date;                // last time I changed a finger or my predecessor
600 } s_node_t, *node_t;*/
601
602 /**
603  * \brief Main function.
604  */
605 int main(int argc, char *argv[])
606 {
607   MSG_init(&argc, argv);
608   xbt_assert(argc > 2, 
609        "Usage: %s [-nb_bits=n] [-timeout=t] platform_file deployment_file\n"
610        "\tExample: %s ../msg_platform.xml pastry10.xml\n", 
611        argv[0], argv[0]);
612   
613   char **options = &argv[1];
614   while (!strncmp(options[0], "-", 1)) {
615
616     int length = strlen("-nb_bits=");
617     if (!strncmp(options[0], "-nb_bits=", length) && strlen(options[0]) > length) {
618       nb_bits = xbt_str_parse_int(options[0] + length, "Invalid nb_bits parameter: %s");
619       XBT_DEBUG("Set nb_bits to %d", nb_bits);
620     }
621     else {
622
623       length = strlen("-timeout=");
624       if (!strncmp(options[0], "-timeout=", length) && strlen(options[0]) > length) {
625         timeout = xbt_str_parse_int(options[0] + length, "Invalid timeout parameter: %s");
626         XBT_DEBUG("Set timeout to %d", timeout);
627       }
628       else {
629         xbt_die("Invalid chord option '%s'", options[0]);
630       }
631     }
632     options++;
633   }
634
635   const char* platform_file = options[0];
636   const char* application_file = options[1];
637
638   MSG_create_environment(platform_file);
639   
640   MSG_function_register("node", node);
641   MSG_launch_application(application_file);
642
643   msg_error_t res = MSG_main();
644   XBT_CRITICAL("Messages created: %ld", smx_total_comms);
645   XBT_INFO("Simulated time: %g", MSG_get_clock());
646
647   return res != MSG_OK;
648 }