Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'noRngStream' into 'master'
[simgrid.git] / examples / s4u / dht-chord / s4u-dht-chord-node.cpp
1 /* Copyright (c) 2010-2019. 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 a non-zero value if id in in [start, end]
24  */
25 static int 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   mailbox_           = simgrid::s4u::Mailbox::by_name(std::to_string(id_));
56   next_finger_to_fix = 0;
57   fingers_.resize(nb_bits, id_);
58
59   if (args.size() == 3) { // first ring
60     deadline_   = std::stod(args[2]);
61     start_time_ = simgrid::s4u::Engine::get_clock();
62     XBT_DEBUG("Create a new Chord ring...");
63   } else {
64     known_id_   = std::stoi(args[2]);
65     start_time_ = std::stod(args[3]);
66     deadline_   = std::stod(args[4]);
67     XBT_DEBUG("Hey! Let's join the system in %f seconds (shall leave at time %f)", start_time_,
68               start_time_ + deadline_);
69   }
70 }
71
72 /* Makes the current node join the ring, knowing the id of a node already in the ring
73  *
74  * @param known_id id of a node already in the ring
75  * @return true if the join operation succeeded
76  *  */
77
78 void Node::join(int known_id)
79 {
80   XBT_INFO("Joining the ring with id %d, knowing node %d", id_, known_id);
81   setPredecessor(-1); // no predecessor (yet)
82
83   int successor_id = remoteFindSuccessor(known_id, id_);
84   if (successor_id == -1) {
85     XBT_INFO("Cannot join the ring.");
86   } else {
87     setFinger(0, successor_id);
88     printFingerTable();
89     joined = true;
90   }
91 }
92
93 /* Makes the current node quit the system */
94 void Node::leave()
95 {
96   XBT_INFO("Well Guys! I Think it's time for me to leave ;)");
97   notifyAndQuit();
98   joined = false;
99 }
100
101 /* Notifies the successor and the predecessor of the current node before leaving */
102 void Node::notifyAndQuit()
103 {
104   // send the PREDECESSOR_LEAVING to our successor
105   ChordMessage* pred_msg = new ChordMessage(PREDECESSOR_LEAVING);
106   pred_msg->request_id   = pred_id_;
107   pred_msg->answer_to    = mailbox_;
108
109   XBT_DEBUG("Sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
110   try {
111     simgrid::s4u::Mailbox::by_name(std::to_string(fingers_[0]))->put(pred_msg, 10, timeout);
112   } catch (const simgrid::TimeoutException&) {
113     XBT_DEBUG("Timeout expired when sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
114     delete pred_msg;
115   }
116
117   if (pred_id_ != -1 && pred_id_ != id_) {
118     // send the SUCCESSOR_LEAVING to our predecessor (only if I have one that is not me)
119     ChordMessage* succ_msg = new ChordMessage(SUCCESSOR_LEAVING);
120     succ_msg->request_id   = fingers_[0];
121     succ_msg->answer_to    = mailbox_;
122     XBT_DEBUG("Sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
123
124     try {
125       simgrid::s4u::Mailbox::by_name(std::to_string(pred_id_))->put(succ_msg, 10, timeout);
126     } catch (const simgrid::TimeoutException&) {
127       XBT_DEBUG("Timeout expired when sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
128       delete succ_msg;
129     }
130   }
131 }
132
133 /* Performs a find successor request to a random id */
134 void Node::randomLookup()
135 {
136   int res          = id_;
137   std::uniform_int_distribution<int> dist(0, nb_bits - 1);
138   int random_index = dist(generator);
139   int random_id    = fingers_[random_index];
140   XBT_DEBUG("Making a lookup request for id %d", random_id);
141   if (random_id != id_)
142     res = findSuccessor(random_id);
143   XBT_DEBUG("The successor of node %d is %d", random_id, res);
144 }
145
146 /* Sets a finger of the current node.
147  *
148  * @param node the current node
149  * @param finger_index index of the finger to set (0 to nb_bits - 1)
150  * @param id the id to set for this finger
151  */
152 void Node::setFinger(int finger_index, int id)
153 {
154   if (id != fingers_[finger_index]) {
155     fingers_[finger_index] = id;
156     XBT_VERB("My new finger #%d is %d", finger_index, id);
157   }
158 }
159
160 /* Sets the predecessor of the current node.
161  * @param id the id to predecessor, or -1 to unset the predecessor
162  */
163 void Node::setPredecessor(int predecessor_id)
164 {
165   if (predecessor_id != pred_id_) {
166     pred_id_ = predecessor_id;
167     XBT_VERB("My new predecessor is %d", predecessor_id);
168   }
169 }
170
171 /** refreshes the finger table of the current node (called periodically) */
172 void Node::fixFingers()
173 {
174   XBT_DEBUG("Fixing fingers");
175   int id = findSuccessor(id_ + (1U << next_finger_to_fix));
176   if (id != -1) {
177     if (id != fingers_[next_finger_to_fix]) {
178       setFinger(next_finger_to_fix, id);
179       printFingerTable();
180     }
181     next_finger_to_fix = (next_finger_to_fix + 1) % nb_bits;
182   }
183 }
184
185 /** Displays the finger table of a node. */
186 void Node::printFingerTable()
187 {
188   if (XBT_LOG_ISENABLED(s4u_chord, xbt_log_priority_verbose)) {
189     XBT_VERB("My finger table:");
190     XBT_VERB("Start | Succ");
191     for (int i = 0; i < nb_bits; i++) {
192       XBT_VERB(" %3u  | %3d", (id_ + (1U << i)) % nb_keys, fingers_[i]);
193     }
194
195     XBT_VERB("Predecessor: %d", pred_id_);
196   }
197 }
198
199 /* checks whether the predecessor has failed (called periodically) */
200 void Node::checkPredecessor()
201 {
202   XBT_DEBUG("Checking whether my predecessor is alive");
203   void* data = nullptr;
204   if (pred_id_ == -1)
205     return;
206
207   simgrid::s4u::Mailbox* mailbox        = simgrid::s4u::Mailbox::by_name(std::to_string(pred_id_));
208   simgrid::s4u::Mailbox* return_mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_is_alive");
209
210   ChordMessage* message = new ChordMessage(PREDECESSOR_ALIVE);
211   message->request_id   = pred_id_;
212   message->answer_to    = return_mailbox;
213
214   XBT_DEBUG("Sending a 'Predecessor Alive' request to my predecessor %d", pred_id_);
215   try {
216     mailbox->put(message, 10, timeout);
217   } catch (const simgrid::TimeoutException&) {
218     XBT_DEBUG("Failed to send the 'Predecessor Alive' request to %d", pred_id_);
219     delete message;
220     return;
221   }
222
223   // receive the answer
224   XBT_DEBUG("Sent 'Predecessor Alive' request to %d, waiting for the answer on my mailbox '%s'", pred_id_,
225             message->answer_to->get_cname());
226   simgrid::s4u::CommPtr comm = return_mailbox->get_async(&data);
227
228   try {
229     comm->wait_for(timeout);
230     XBT_DEBUG("Received the answer to my 'Predecessor Alive': my predecessor %d is alive", pred_id_);
231     delete static_cast<ChordMessage*>(data);
232   } catch (const simgrid::TimeoutException&) {
233     XBT_DEBUG("Failed to receive the answer to my 'Predecessor Alive' request");
234     pred_id_ = -1;
235   }
236 }
237
238 /* Asks its predecessor to a remote node
239  *
240  * @param ask_to the node to ask to
241  * @return the id of its predecessor node, or -1 if the request failed (or if the node does not know its predecessor)
242  */
243 int Node::remoteGetPredecessor(int ask_to)
244 {
245   int predecessor_id                      = -1;
246   void* data                              = nullptr;
247   simgrid::s4u::Mailbox* mailbox          = simgrid::s4u::Mailbox::by_name(std::to_string(ask_to));
248   simgrid::s4u::Mailbox* return_mailbox   = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_pred");
249
250   ChordMessage* message = new ChordMessage(GET_PREDECESSOR);
251   message->request_id   = id_;
252   message->answer_to    = return_mailbox;
253
254   // send a "Get Predecessor" request to ask_to_id
255   XBT_DEBUG("Sending a 'Get Predecessor' request to %d", ask_to);
256   try {
257     mailbox->put(message, 10, timeout);
258   } catch (const simgrid::TimeoutException&) {
259     XBT_DEBUG("Failed to send the 'Get Predecessor' request to %d", ask_to);
260     delete message;
261     return predecessor_id;
262   }
263
264   // receive the answer
265   XBT_DEBUG("Sent 'Get Predecessor' request to %d, waiting for the answer on my mailbox '%s'", ask_to,
266             message->answer_to->get_cname());
267   simgrid::s4u::CommPtr comm = return_mailbox->get_async(&data);
268
269   try {
270     comm->wait_for(timeout);
271     ChordMessage* answer = static_cast<ChordMessage*>(data);
272     XBT_DEBUG("Received the answer to my 'Get Predecessor' request: the predecessor of node %d is %d", ask_to,
273               answer->answer_id);
274     predecessor_id = answer->answer_id;
275     delete answer;
276   } catch (const simgrid::TimeoutException&) {
277     XBT_DEBUG("Failed to receive the answer to my 'Get Predecessor' request");
278     delete static_cast<ChordMessage*>(data);
279   }
280
281   return predecessor_id;
282 }
283
284 /* Returns the closest preceding finger of an id with respect to the finger table of the current node.
285  *
286  * @param id the id to find
287  * @return the closest preceding finger of that id
288  */
289 int Node::closestPrecedingFinger(int id)
290 {
291   for (int i = nb_bits - 1; i >= 0; i--) {
292     if (is_in_interval(fingers_[i], id_ + 1, id - 1)) {
293       return fingers_[i];
294     }
295   }
296   return id_;
297 }
298
299 /* Makes the current node find the successor node of an id.
300  *
301  * @param id the id to find
302  * @return the id of the successor node, or -1 if the request failed
303  */
304 int Node::findSuccessor(int id)
305 {
306   // is my successor the successor?
307   if (is_in_interval(id, id_ + 1, fingers_[0])) {
308     return fingers_[0];
309   }
310
311   // otherwise, ask the closest preceding finger in my table
312   return remoteFindSuccessor(closestPrecedingFinger(id), id);
313 }
314
315 int Node::remoteFindSuccessor(int ask_to, int id)
316 {
317   int successor                           = -1;
318   void* data                              = nullptr;
319   simgrid::s4u::Mailbox* mailbox          = simgrid::s4u::Mailbox::by_name(std::to_string(ask_to));
320   simgrid::s4u::Mailbox* return_mailbox   = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_succ");
321
322   ChordMessage* message = new ChordMessage(FIND_SUCCESSOR);
323   message->request_id   = id_;
324   message->answer_to    = return_mailbox;
325
326   // send a "Find Successor" request to ask_to_id
327   XBT_DEBUG("Sending a 'Find Successor' request to %d for id %d", ask_to, id);
328   try {
329     mailbox->put(message, 10, timeout);
330   } catch (const simgrid::TimeoutException&) {
331     XBT_DEBUG("Failed to send the 'Find Successor' request to %d for id %d", ask_to, id_);
332     delete message;
333     return successor;
334   }
335   // receive the answer
336   XBT_DEBUG("Sent a 'Find Successor' request to %d for key %d, waiting for the answer", ask_to, id);
337   simgrid::s4u::CommPtr comm = return_mailbox->get_async(&data);
338
339   try {
340     comm->wait_for(timeout);
341     ChordMessage* answer = static_cast<ChordMessage*>(data);
342     XBT_DEBUG("Received the answer to my 'Find Successor' request for id %d: the successor of key %d is %d",
343               answer->request_id, id_, answer->answer_id);
344     successor = answer->answer_id;
345     delete answer;
346   } catch (const simgrid::TimeoutException&) {
347     XBT_DEBUG("Failed to receive the answer to my 'Find Successor' request");
348     delete static_cast<ChordMessage*>(data);
349   }
350
351   return successor;
352 }
353
354 /* Notifies the current node that its predecessor may have changed. */
355 void Node::notify(int predecessor_candidate_id)
356 {
357   if (pred_id_ == -1 || is_in_interval(predecessor_candidate_id, pred_id_ + 1, id_ - 1)) {
358     setPredecessor(predecessor_candidate_id);
359     printFingerTable();
360   } else {
361     XBT_DEBUG("I don't have to change my predecessor to %d", predecessor_candidate_id);
362   }
363 }
364
365 /* Notifies a remote node that its predecessor may have changed. */
366 void Node::remoteNotify(int notify_id, int predecessor_candidate_id)
367 {
368   ChordMessage* message = new ChordMessage(NOTIFY);
369   message->request_id   = predecessor_candidate_id;
370   message->answer_to    = nullptr;
371
372   // send a "Notify" request to notify_id
373   XBT_DEBUG("Sending a 'Notify' request to %d", notify_id);
374   simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(notify_id));
375   mailbox->put_init(message, 10)->detach(ChordMessage::destroy);
376 }
377
378 /* This function is called periodically. It checks the immediate successor of the current node. */
379 void Node::stabilize()
380 {
381   XBT_DEBUG("Stabilizing node");
382
383   // get the predecessor of my immediate successor
384   int candidate_id = pred_id_;
385   int successor_id = fingers_[0];
386   if (successor_id != id_)
387     candidate_id = remoteGetPredecessor(successor_id);
388
389   // this node is a candidate to become my new successor
390   if (candidate_id != -1 && is_in_interval(candidate_id, id_ + 1, successor_id - 1)) {
391     setFinger(0, candidate_id);
392   }
393   if (successor_id != id_) {
394     remoteNotify(successor_id, id_);
395   }
396 }
397
398 /* This function is called when a node receives a message.
399  *
400  * @param message the message to handle (don't touch it afterward: it will be destroyed, reused or forwarded)
401  */
402 void Node::handleMessage(ChordMessage* message)
403 {
404   switch (message->type) {
405   case FIND_SUCCESSOR:
406     XBT_DEBUG("Received a 'Find Successor' request from %s for id %d", message->issuer_host_name.c_str(),
407         message->request_id);
408     // is my successor the successor?
409     if (is_in_interval(message->request_id, id_ + 1, fingers_[0])) {
410       message->type = FIND_SUCCESSOR_ANSWER;
411       message->answer_id = fingers_[0];
412       XBT_DEBUG("Sending back a 'Find Successor Answer' to %s (mailbox %s): the successor of %d is %d",
413                 message->issuer_host_name.c_str(), message->answer_to->get_cname(), message->request_id,
414                 message->answer_id);
415       message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
416     } else {
417       // otherwise, forward the request to the closest preceding finger in my table
418       int closest = closestPrecedingFinger(message->request_id);
419       XBT_DEBUG("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d",
420           message->request_id, closest);
421       simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(closest));
422       mailbox->put_init(message, 10)->detach(ChordMessage::destroy);
423     }
424     break;
425
426   case GET_PREDECESSOR:
427     XBT_DEBUG("Receiving a 'Get Predecessor' request from %s", message->issuer_host_name.c_str());
428     message->type = GET_PREDECESSOR_ANSWER;
429     message->answer_id = pred_id_;
430     XBT_DEBUG("Sending back a 'Get Predecessor Answer' to %s via mailbox '%s': my predecessor is %d",
431               message->issuer_host_name.c_str(), message->answer_to->get_cname(), message->answer_id);
432     message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
433     break;
434
435   case NOTIFY:
436     // someone is telling me that he may be my new predecessor
437     XBT_DEBUG("Receiving a 'Notify' request from %s", message->issuer_host_name.c_str());
438     notify(message->request_id);
439     delete message;
440     break;
441
442   case PREDECESSOR_LEAVING:
443     // my predecessor is about to quit
444     XBT_DEBUG("Receiving a 'Predecessor Leaving' message from %s", message->issuer_host_name.c_str());
445     // modify my predecessor
446     setPredecessor(message->request_id);
447     delete message;
448     /*TODO :
449       >> notify my new predecessor
450       >> send a notify_predecessors !!
451      */
452     break;
453
454   case SUCCESSOR_LEAVING:
455     // my successor is about to quit
456     XBT_DEBUG("Receiving a 'Successor Leaving' message from %s", message->issuer_host_name.c_str());
457     // modify my successor FIXME : this should be implicit ?
458     setFinger(0, message->request_id);
459     delete message;
460     /* TODO
461        >> notify my new successor
462        >> update my table & predecessors table */
463     break;
464
465   case PREDECESSOR_ALIVE:
466     XBT_DEBUG("Receiving a 'Predecessor Alive' request from %s", message->issuer_host_name.c_str());
467     message->type = PREDECESSOR_ALIVE_ANSWER;
468     XBT_DEBUG("Sending back a 'Predecessor Alive Answer' to %s (mailbox %s)", message->issuer_host_name.c_str(),
469               message->answer_to->get_cname());
470     message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
471     break;
472
473   default:
474     XBT_DEBUG("Ignoring unexpected message: %d from %s", message->type, message->issuer_host_name.c_str());
475     delete message;
476   }
477 }