Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Fix distcheck.
[simgrid.git] / examples / s4u / dht-chord / s4u-dht-chord-node.cpp
1 /* Copyright (c) 2010-2020. The SimGrid Team. All rights reserved.          */
2
3 /* This program is free software; you can redistribute it and/or modify it
4  * under the terms of the license (GNU LGPL) which comes with this package. */
5
6 #include "s4u-dht-chord.hpp"
7
8 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(s4u_chord);
9
10 /* Returns whether an id belongs to the interval [start, end].
11  *
12  * The parameters are normalized to make sure they are between 0 and nb_keys - 1).
13  * 1 belongs to [62, 3]
14  * 1 does not belong to [3, 62]
15  * 63 belongs to [62, 3]
16  * 63 does not belong to [3, 62]
17  * 24 belongs to [21, 29]
18  * 24 does not belong to [29, 21]
19  *
20  * @param id id to check
21  * @param start lower bound
22  * @param end upper bound
23  * @return true if id in in [start, end]
24  */
25 static bool is_in_interval(int id, int start, int end)
26 {
27   int i = id % nb_keys;
28   int s = start % nb_keys;
29   int e = end % nb_keys;
30
31   // make sure end >= start and id >= start
32   if (e < s) {
33     e += nb_keys;
34   }
35
36   if (i < s) {
37     i += nb_keys;
38   }
39
40   return i <= e;
41 }
42
43 void ChordMessage::destroy(void* message)
44 {
45   delete static_cast<ChordMessage*>(message);
46 }
47
48 /* Initializes the current node as the first one of the system */
49 Node::Node(std::vector<std::string> args)
50 {
51   xbt_assert(args.size() == 3 || args.size() == 5, "Wrong number of arguments for this node");
52
53   // initialize my node
54   id_                = std::stoi(args[1]);
55   XBT_DEBUG("Initialize node with id: %d", id_);
56   random.set_seed(id_);
57   mailbox_           = simgrid::s4u::Mailbox::by_name(std::to_string(id_));
58   next_finger_to_fix = 0;
59   fingers_.resize(nb_bits, id_);
60
61   if (args.size() == 3) { // first ring
62     deadline_   = std::stod(args[2]);
63     start_time_ = simgrid::s4u::Engine::get_clock();
64     XBT_DEBUG("Create a new Chord ring...");
65   } else {
66     known_id_   = std::stoi(args[2]);
67     start_time_ = std::stod(args[3]);
68     deadline_   = std::stod(args[4]);
69     XBT_DEBUG("Hey! Let's join the system in %f seconds (shall leave at time %f)", start_time_,
70               start_time_ + deadline_);
71   }
72 }
73
74 /* Makes the current node join the ring, knowing the id of a node already in the ring
75  *
76  * @param known_id id of a node already in the ring
77  * @return true if the join operation succeeded
78  *  */
79
80 void Node::join(int known_id)
81 {
82   XBT_INFO("Joining the ring with id %d, knowing node %d", id_, known_id);
83   setPredecessor(-1); // no predecessor (yet)
84
85   int successor_id = remoteFindSuccessor(known_id, id_);
86   if (successor_id == -1) {
87     XBT_INFO("Cannot join the ring.");
88   } else {
89     setFinger(0, successor_id);
90     printFingerTable();
91     joined = true;
92   }
93 }
94
95 /* Makes the current node quit the system */
96 void Node::leave()
97 {
98   XBT_INFO("Well Guys! I Think it's time for me to leave ;)");
99   notifyAndQuit();
100   joined = false;
101 }
102
103 /* Notifies the successor and the predecessor of the current node before leaving */
104 void Node::notifyAndQuit()
105 {
106   // send the PREDECESSOR_LEAVING to our successor
107   ChordMessage* pred_msg = new ChordMessage(PREDECESSOR_LEAVING);
108   pred_msg->request_id   = pred_id_;
109   pred_msg->answer_to    = mailbox_;
110
111   XBT_DEBUG("Sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
112   try {
113     simgrid::s4u::Mailbox::by_name(std::to_string(fingers_[0]))->put(pred_msg, 10, timeout);
114   } catch (const simgrid::TimeoutException&) {
115     XBT_DEBUG("Timeout expired when sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
116     delete pred_msg;
117   }
118
119   if (pred_id_ != -1 && pred_id_ != id_) {
120     // send the SUCCESSOR_LEAVING to our predecessor (only if I have one that is not me)
121     ChordMessage* succ_msg = new ChordMessage(SUCCESSOR_LEAVING);
122     succ_msg->request_id   = fingers_[0];
123     succ_msg->answer_to    = mailbox_;
124     XBT_DEBUG("Sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
125
126     try {
127       simgrid::s4u::Mailbox::by_name(std::to_string(pred_id_))->put(succ_msg, 10, timeout);
128     } catch (const simgrid::TimeoutException&) {
129       XBT_DEBUG("Timeout expired when sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
130       delete succ_msg;
131     }
132   }
133 }
134
135 /* Performs a find successor request to a random id */
136 void Node::randomLookup()
137 {
138   int res          = id_;
139   int random_index = random.uniform_int(0, nb_bits - 1);
140   int random_id    = fingers_[random_index];
141   XBT_DEBUG("Making a lookup request for id %d", random_id);
142   if (random_id != id_)
143     res = findSuccessor(random_id);
144   XBT_DEBUG("The successor of node %d is %d", random_id, res);
145 }
146
147 /* Sets a finger of the current node.
148  *
149  * @param node the current node
150  * @param finger_index index of the finger to set (0 to nb_bits - 1)
151  * @param id the id to set for this finger
152  */
153 void Node::setFinger(int finger_index, int id)
154 {
155   if (id != fingers_[finger_index]) {
156     fingers_[finger_index] = id;
157     XBT_VERB("My new finger #%d is %d", finger_index, id);
158   }
159 }
160
161 /* Sets the predecessor of the current node.
162  * @param id the id to predecessor, or -1 to unset the predecessor
163  */
164 void Node::setPredecessor(int predecessor_id)
165 {
166   if (predecessor_id != pred_id_) {
167     pred_id_ = predecessor_id;
168     XBT_VERB("My new predecessor is %d", predecessor_id);
169   }
170 }
171
172 /** refreshes the finger table of the current node (called periodically) */
173 void Node::fixFingers()
174 {
175   XBT_DEBUG("Fixing fingers");
176   int id = findSuccessor(id_ + (1U << next_finger_to_fix));
177   if (id != -1) {
178     if (id != fingers_[next_finger_to_fix]) {
179       setFinger(next_finger_to_fix, id);
180       printFingerTable();
181     }
182     next_finger_to_fix = (next_finger_to_fix + 1) % nb_bits;
183   }
184 }
185
186 /** Displays the finger table of a node. */
187 void Node::printFingerTable()
188 {
189   if (XBT_LOG_ISENABLED(s4u_chord, xbt_log_priority_verbose)) {
190     XBT_VERB("My finger table:");
191     XBT_VERB("Start | Succ");
192     for (int i = 0; i < nb_bits; i++) {
193       XBT_VERB(" %3u  | %3d", (id_ + (1U << i)) % nb_keys, fingers_[i]);
194     }
195
196     XBT_VERB("Predecessor: %d", pred_id_);
197   }
198 }
199
200 /* checks whether the predecessor has failed (called periodically) */
201 void Node::checkPredecessor()
202 {
203   XBT_DEBUG("Checking whether my predecessor is alive");
204   void* data = nullptr;
205   if (pred_id_ == -1)
206     return;
207
208   simgrid::s4u::Mailbox* mailbox        = simgrid::s4u::Mailbox::by_name(std::to_string(pred_id_));
209   simgrid::s4u::Mailbox* return_mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_is_alive");
210
211   ChordMessage* message = new ChordMessage(PREDECESSOR_ALIVE);
212   message->request_id   = pred_id_;
213   message->answer_to    = return_mailbox;
214
215   XBT_DEBUG("Sending a 'Predecessor Alive' request to my predecessor %d", pred_id_);
216   try {
217     mailbox->put(message, 10, timeout);
218   } catch (const simgrid::TimeoutException&) {
219     XBT_DEBUG("Failed to send the 'Predecessor Alive' request to %d", pred_id_);
220     delete message;
221     return;
222   }
223
224   // receive the answer
225   XBT_DEBUG("Sent 'Predecessor Alive' request to %d, waiting for the answer on my mailbox '%s'", pred_id_,
226             message->answer_to->get_cname());
227   simgrid::s4u::CommPtr comm = return_mailbox->get_async(&data);
228
229   try {
230     comm->wait_for(timeout);
231     XBT_DEBUG("Received the answer to my 'Predecessor Alive': my predecessor %d is alive", pred_id_);
232     delete static_cast<ChordMessage*>(data);
233   } catch (const simgrid::TimeoutException&) {
234     XBT_DEBUG("Failed to receive the answer to my 'Predecessor Alive' request");
235     pred_id_ = -1;
236   }
237 }
238
239 /* Asks its predecessor to a remote node
240  *
241  * @param ask_to the node to ask to
242  * @return the id of its predecessor node, or -1 if the request failed (or if the node does not know its predecessor)
243  */
244 int Node::remoteGetPredecessor(int ask_to)
245 {
246   int predecessor_id                      = -1;
247   void* data                              = nullptr;
248   simgrid::s4u::Mailbox* mailbox          = simgrid::s4u::Mailbox::by_name(std::to_string(ask_to));
249   simgrid::s4u::Mailbox* return_mailbox   = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_pred");
250
251   ChordMessage* message = new ChordMessage(GET_PREDECESSOR);
252   message->request_id   = id_;
253   message->answer_to    = return_mailbox;
254
255   // send a "Get Predecessor" request to ask_to_id
256   XBT_DEBUG("Sending a 'Get Predecessor' request to %d", ask_to);
257   try {
258     mailbox->put(message, 10, timeout);
259   } catch (const simgrid::TimeoutException&) {
260     XBT_DEBUG("Failed to send the 'Get Predecessor' request to %d", ask_to);
261     delete message;
262     return predecessor_id;
263   }
264
265   // receive the answer
266   XBT_DEBUG("Sent 'Get Predecessor' request to %d, waiting for the answer on my mailbox '%s'", ask_to,
267             message->answer_to->get_cname());
268   simgrid::s4u::CommPtr comm = return_mailbox->get_async(&data);
269
270   try {
271     comm->wait_for(timeout);
272     const ChordMessage* answer = static_cast<ChordMessage*>(data);
273     XBT_DEBUG("Received the answer to my 'Get Predecessor' request: the predecessor of node %d is %d", ask_to,
274               answer->answer_id);
275     predecessor_id = answer->answer_id;
276     delete answer;
277   } catch (const simgrid::TimeoutException&) {
278     XBT_DEBUG("Failed to receive the answer to my 'Get Predecessor' request");
279     delete static_cast<ChordMessage*>(data);
280   }
281
282   return predecessor_id;
283 }
284
285 /* Returns the closest preceding finger of an id with respect to the finger table of the current node.
286  *
287  * @param id the id to find
288  * @return the closest preceding finger of that id
289  */
290 int Node::closestPrecedingFinger(int id)
291 {
292   for (int i = nb_bits - 1; i >= 0; i--) {
293     if (is_in_interval(fingers_[i], id_ + 1, id - 1)) {
294       return fingers_[i];
295     }
296   }
297   return id_;
298 }
299
300 /* Makes the current node find the successor node of an id.
301  *
302  * @param id the id to find
303  * @return the id of the successor node, or -1 if the request failed
304  */
305 int Node::findSuccessor(int id)
306 {
307   // is my successor the successor?
308   if (is_in_interval(id, id_ + 1, fingers_[0])) {
309     return fingers_[0];
310   }
311
312   // otherwise, ask the closest preceding finger in my table
313   return remoteFindSuccessor(closestPrecedingFinger(id), id);
314 }
315
316 int Node::remoteFindSuccessor(int ask_to, int id)
317 {
318   int successor                           = -1;
319   ChordMessage* data                      = nullptr;
320   simgrid::s4u::Mailbox* mailbox          = simgrid::s4u::Mailbox::by_name(std::to_string(ask_to));
321   simgrid::s4u::Mailbox* return_mailbox   = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_succ");
322
323   ChordMessage* message = new ChordMessage(FIND_SUCCESSOR);
324   message->request_id   = id_;
325   message->answer_to    = return_mailbox;
326
327   // send a "Find Successor" request to ask_to_id
328   XBT_DEBUG("Sending a 'Find Successor' request to %d for id %d", ask_to, id);
329   try {
330     mailbox->put(message, 10, timeout);
331   } catch (const simgrid::TimeoutException&) {
332     XBT_DEBUG("Failed to send the 'Find Successor' request to %d for id %d", ask_to, id_);
333     delete message;
334     return successor;
335   }
336   // receive the answer
337   XBT_DEBUG("Sent a 'Find Successor' request to %d for key %d, waiting for the answer", ask_to, id);
338   simgrid::s4u::CommPtr comm = return_mailbox->get_async(reinterpret_cast<void**>(&data));
339
340   try {
341     comm->wait_for(timeout);
342     const ChordMessage* answer = data;
343     XBT_DEBUG("Received the answer to my 'Find Successor' request for id %d: the successor of key %d is %d",
344               answer->request_id, id_, answer->answer_id);
345     successor = answer->answer_id;
346     delete answer;
347   } catch (const simgrid::TimeoutException&) {
348     XBT_DEBUG("Failed to receive the answer to my 'Find Successor' request");
349     delete data;
350   }
351
352   return successor;
353 }
354
355 /* Notifies the current node that its predecessor may have changed. */
356 void Node::notify(int predecessor_candidate_id)
357 {
358   if (pred_id_ == -1 || is_in_interval(predecessor_candidate_id, pred_id_ + 1, id_ - 1)) {
359     setPredecessor(predecessor_candidate_id);
360     printFingerTable();
361   } else {
362     XBT_DEBUG("I don't have to change my predecessor to %d", predecessor_candidate_id);
363   }
364 }
365
366 /* Notifies a remote node that its predecessor may have changed. */
367 void Node::remoteNotify(int notify_id, int predecessor_candidate_id) const
368 {
369   ChordMessage* message = new ChordMessage(NOTIFY);
370   message->request_id   = predecessor_candidate_id;
371   message->answer_to    = nullptr;
372
373   // send a "Notify" request to notify_id
374   XBT_DEBUG("Sending a 'Notify' request to %d", notify_id);
375   simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(notify_id));
376   mailbox->put_init(message, 10)->detach(ChordMessage::destroy);
377 }
378
379 /* This function is called periodically. It checks the immediate successor of the current node. */
380 void Node::stabilize()
381 {
382   XBT_DEBUG("Stabilizing node");
383
384   // get the predecessor of my immediate successor
385   int candidate_id = pred_id_;
386   int successor_id = fingers_[0];
387   if (successor_id != id_)
388     candidate_id = remoteGetPredecessor(successor_id);
389
390   // this node is a candidate to become my new successor
391   if (candidate_id != -1 && is_in_interval(candidate_id, id_ + 1, successor_id - 1)) {
392     setFinger(0, candidate_id);
393   }
394   if (successor_id != id_) {
395     remoteNotify(successor_id, id_);
396   }
397 }
398
399 /* This function is called when a node receives a message.
400  *
401  * @param message the message to handle (don't touch it afterward: it will be destroyed, reused or forwarded)
402  */
403 void Node::handleMessage(ChordMessage* message)
404 {
405   switch (message->type) {
406   case FIND_SUCCESSOR:
407     XBT_DEBUG("Received a 'Find Successor' request from %s for id %d", message->issuer_host_name.c_str(),
408         message->request_id);
409     // is my successor the successor?
410     if (is_in_interval(message->request_id, id_ + 1, fingers_[0])) {
411       message->type = FIND_SUCCESSOR_ANSWER;
412       message->answer_id = fingers_[0];
413       XBT_DEBUG("Sending back a 'Find Successor Answer' to %s (mailbox %s): the successor of %d is %d",
414                 message->issuer_host_name.c_str(), message->answer_to->get_cname(), message->request_id,
415                 message->answer_id);
416       message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
417     } else {
418       // otherwise, forward the request to the closest preceding finger in my table
419       int closest = closestPrecedingFinger(message->request_id);
420       XBT_DEBUG("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d",
421           message->request_id, closest);
422       simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(closest));
423       mailbox->put_init(message, 10)->detach(ChordMessage::destroy);
424     }
425     break;
426
427   case GET_PREDECESSOR:
428     XBT_DEBUG("Receiving a 'Get Predecessor' request from %s", message->issuer_host_name.c_str());
429     message->type = GET_PREDECESSOR_ANSWER;
430     message->answer_id = pred_id_;
431     XBT_DEBUG("Sending back a 'Get Predecessor Answer' to %s via mailbox '%s': my predecessor is %d",
432               message->issuer_host_name.c_str(), message->answer_to->get_cname(), message->answer_id);
433     message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
434     break;
435
436   case NOTIFY:
437     // someone is telling me that he may be my new predecessor
438     XBT_DEBUG("Receiving a 'Notify' request from %s", message->issuer_host_name.c_str());
439     notify(message->request_id);
440     delete message;
441     break;
442
443   case PREDECESSOR_LEAVING:
444     // my predecessor is about to quit
445     XBT_DEBUG("Receiving a 'Predecessor Leaving' message from %s", message->issuer_host_name.c_str());
446     // modify my predecessor
447     setPredecessor(message->request_id);
448     delete message;
449     /*TODO :
450       >> notify my new predecessor
451       >> send a notify_predecessors !!
452      */
453     break;
454
455   case SUCCESSOR_LEAVING:
456     // my successor is about to quit
457     XBT_DEBUG("Receiving a 'Successor Leaving' message from %s", message->issuer_host_name.c_str());
458     // modify my successor FIXME : this should be implicit ?
459     setFinger(0, message->request_id);
460     delete message;
461     /* TODO
462        >> notify my new successor
463        >> update my table & predecessors table */
464     break;
465
466   case PREDECESSOR_ALIVE:
467     XBT_DEBUG("Receiving a 'Predecessor Alive' request from %s", message->issuer_host_name.c_str());
468     message->type = PREDECESSOR_ALIVE_ANSWER;
469     XBT_DEBUG("Sending back a 'Predecessor Alive Answer' to %s (mailbox %s)", message->issuer_host_name.c_str(),
470               message->answer_to->get_cname());
471     message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
472     break;
473
474   default:
475     XBT_DEBUG("Ignoring unexpected message: %d from %s", message->type, message->issuer_host_name.c_str());
476     delete message;
477   }
478 }
479
480 void Node::operator()()
481 {
482   simgrid::s4u::this_actor::sleep_for(start_time_);
483   if (known_id_ == -1) {
484     setPredecessor(-1); // -1 means that I have no predecessor
485     printFingerTable();
486     joined = true;
487   } else {
488     join(known_id_);
489   }
490
491   if (not joined)
492     return;
493   void* data                         = nullptr;
494   double now                         = simgrid::s4u::Engine::get_clock();
495   double next_stabilize_date         = start_time_ + PERIODIC_STABILIZE_DELAY;
496   double next_fix_fingers_date       = start_time_ + PERIODIC_FIX_FINGERS_DELAY;
497   double next_check_predecessor_date = start_time_ + PERIODIC_CHECK_PREDECESSOR_DELAY;
498   double next_lookup_date            = start_time_ + PERIODIC_LOOKUP_DELAY;
499   simgrid::s4u::CommPtr comm_receive = nullptr;
500   while (now < std::min(start_time_ + deadline_, MAX_SIMULATION_TIME)) {
501     if (comm_receive == nullptr)
502       comm_receive = mailbox_->get_async(&data);
503     bool comm_completed = true;
504     try {
505       if (not comm_receive->test())
506         comm_completed = false;
507     } catch (const simgrid::TimeoutException&) {
508       XBT_DEBUG("Caught a timeout, go ahead.");
509     }
510
511     if (comm_completed) {
512       if (data != nullptr) {
513         ChordMessage* message = static_cast<ChordMessage*>(data);
514         handleMessage(message);
515         data = nullptr;
516       }
517       comm_receive = nullptr;
518     } else {
519       // no task was received: make some periodic calls
520       if (now >= next_stabilize_date) {
521         stabilize();
522         next_stabilize_date = simgrid::s4u::Engine::get_clock() + PERIODIC_STABILIZE_DELAY;
523       } else if (now >= next_fix_fingers_date) {
524         fixFingers();
525         next_fix_fingers_date = simgrid::s4u::Engine::get_clock() + PERIODIC_FIX_FINGERS_DELAY;
526       } else if (now >= next_check_predecessor_date) {
527         checkPredecessor();
528         next_check_predecessor_date = simgrid::s4u::Engine::get_clock() + PERIODIC_CHECK_PREDECESSOR_DELAY;
529       } else if (now >= next_lookup_date) {
530         randomLookup();
531         next_lookup_date = simgrid::s4u::Engine::get_clock() + PERIODIC_LOOKUP_DELAY;
532       } else {
533         // nothing to do: sleep for a while
534         simgrid::s4u::this_actor::sleep_for(SLEEP_DELAY);
535       }
536     }
537
538     now = simgrid::s4u::Engine::get_clock();
539   }
540   if (comm_receive != nullptr) {
541     try {
542       if (comm_receive->test())
543         delete static_cast<ChordMessage*>(data);
544       else
545         comm_receive->cancel();
546     } catch (const simgrid::TimeoutException&) {
547       XBT_DEBUG("Caught a timeout for last message, nevermind.");
548     }
549   }
550   // leave the ring
551   leave();
552 }