Logo AND Algorithmique Numérique Distribuée

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