1 /* Copyright (c) 2010-2016. The SimGrid Team. All rights reserved. */
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. */
6 #include "s4u_dht-chord.hpp"
8 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(s4u_chord);
10 /* Returns whether an id belongs to the interval [start, end].
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]
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]
25 static int is_in_interval(int id, int start, int end)
28 int s = start % nb_keys;
29 int e = end % nb_keys;
31 // make sure end >= start and id >= start
43 /* Initializes the current node as the first one of the system */
44 Node::Node(std::vector<std::string> args)
46 xbt_assert(args.size() == 3 || args.size() == 5, "Wrong number of arguments for this node");
49 id_ = std::stoi(args[1]);
50 stream = simgrid::s4u::this_actor::host()->extension<HostChord>()->getStream();
51 mailbox_ = simgrid::s4u::Mailbox::byName(std::to_string(id_));
52 next_finger_to_fix = 0;
53 fingers_ = new int[nb_bits];
55 for (int i = 0; i < nb_bits; i++) {
59 if (args.size() == 3) { // first ring
60 deadline_ = std::stod(args[2]);
61 start_time_ = simgrid::s4u::Engine::getClock();
62 XBT_DEBUG("Create a new Chord ring...");
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_);
76 /* Makes the current node join the ring, knowing the id of a node already in the ring
78 * \param known_id id of a node already in the ring
79 * \return true if the join operation succeeded
82 void Node::join(int known_id)
84 XBT_INFO("Joining the ring with id %d, knowing node %d", id_, known_id);
85 setPredecessor(-1); // no predecessor (yet)
87 int successor_id = remoteFindSuccessor(known_id, id_);
88 if (successor_id == -1) {
89 XBT_INFO("Cannot join the ring.");
91 setFinger(0, successor_id);
97 /* Makes the current node quit the system */
100 XBT_INFO("Well Guys! I Think it's time for me to leave ;)");
105 /* Notifies the successor and the predecessor of the current node before leaving */
106 void Node::notifyAndQuit()
108 // send the PREDECESSOR_LEAVING to our successor
109 ChordMessage* pred_msg = new ChordMessage(PREDECESSOR_LEAVING);
110 pred_msg->request_id = pred_id_;
111 pred_msg->answer_to = mailbox_;
113 XBT_DEBUG("Sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
115 simgrid::s4u::this_actor::send(simgrid::s4u::Mailbox::byName(std::to_string(fingers_[0])), pred_msg, 10, timeout);
116 } catch (xbt_ex& e) {
117 if (e.category == timeout_error) {
118 XBT_DEBUG("Timeout expired when sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
123 // send the SUCCESSOR_LEAVING to our predecessor
124 ChordMessage* succ_msg = new ChordMessage(SUCCESSOR_LEAVING);
125 succ_msg->request_id = fingers_[0];
126 succ_msg->answer_to = mailbox_;
127 XBT_DEBUG("Sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
130 simgrid::s4u::this_actor::send(simgrid::s4u::Mailbox::byName(std::to_string(pred_id_)), succ_msg, 10, timeout);
131 } catch (xbt_ex& e) {
132 if (e.category == timeout_error) {
133 XBT_DEBUG("Timeout expired when sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
139 /* Performs a find successor request to a random id */
140 void Node::randomLookup()
143 int random_index = RngStream_RandInt(stream, 0, nb_bits - 1);
144 int random_id = fingers_[random_index];
145 XBT_DEBUG("Making a lookup request for id %d", random_id);
146 if (random_id != id_)
147 res = findSuccessor(random_id);
148 XBT_DEBUG("The successor of node %d is %d", random_id, res);
151 /* Sets a finger of the current node.
153 * \param node the current node
154 * \param finger_index index of the finger to set (0 to nb_bits - 1)
155 * \param id the id to set for this finger
157 void Node::setFinger(int finger_index, int id)
159 if (id != fingers_[finger_index]) {
160 fingers_[finger_index] = id;
161 XBT_VERB("My new finger #%d is %d", finger_index, id);
165 /* Sets the predecessor of the current node.
166 * \param id the id to predecessor, or -1 to unset the predecessor
168 void Node::setPredecessor(int predecessor_id)
170 if (predecessor_id != pred_id_) {
171 pred_id_ = predecessor_id;
172 XBT_VERB("My new predecessor is %d", predecessor_id);
176 /** refreshes the finger table of the current node (called periodically) */
177 void Node::fixFingers()
179 XBT_DEBUG("Fixing fingers");
180 int id = findSuccessor(id_ + powers2[next_finger_to_fix]);
182 if (id != fingers_[next_finger_to_fix]) {
183 setFinger(next_finger_to_fix, id);
186 next_finger_to_fix = (next_finger_to_fix + 1) % nb_bits;
190 /** Displays the finger table of a node. */
191 void Node::printFingerTable()
193 if (XBT_LOG_ISENABLED(s4u_chord, xbt_log_priority_verbose)) {
194 XBT_VERB("My finger table:");
195 XBT_VERB("Start | Succ");
196 for (int i = 0; i < nb_bits; i++) {
197 XBT_VERB(" %3d | %3d", (id_ + powers2[i]) % nb_keys, fingers_[i]);
200 XBT_VERB("Predecessor: %d", pred_id_);
204 /* checks whether the predecessor has failed (called periodically) */
205 void Node::checkPredecessor()
207 XBT_DEBUG("Checking whether my predecessor is alive");
208 void* data = nullptr;
212 simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(pred_id_));
213 simgrid::s4u::MailboxPtr return_mailbox = simgrid::s4u::Mailbox::byName(std::to_string(id_) + "_is_alive");
215 ChordMessage* message = new ChordMessage(PREDECESSOR_ALIVE);
216 message->request_id = pred_id_;
217 message->answer_to = return_mailbox;
219 XBT_DEBUG("Sending a 'Predecessor Alive' request to my predecessor %d", pred_id_);
221 simgrid::s4u::this_actor::send(mailbox, message, 10, timeout);
222 } catch (xbt_ex& e) {
223 if (e.category == timeout_error) {
224 XBT_DEBUG("Failed to send the 'Predecessor Alive' request to %d", pred_id_);
229 // receive the answer
230 XBT_DEBUG("Sent 'Predecessor Alive' request to %d, waiting for the answer on my mailbox '%s'", pred_id_,
231 message->answer_to->name());
232 simgrid::s4u::Comm& comm = simgrid::s4u::this_actor::irecv(return_mailbox, &data);
236 XBT_DEBUG("Received the answer to my 'Predecessor Alive': my predecessor %d is alive", pred_id_);
238 } catch (xbt_ex& e) {
239 if (e.category == timeout_error) {
240 XBT_DEBUG("Failed to receive the answer to my 'Predecessor Alive' request");
246 /* Asks its predecessor to a remote node
248 * \param ask_to the node to ask to
249 * \return the id of its predecessor node, or -1 if the request failed (or if the node does not know its predecessor)
251 int Node::remoteGetPredecessor(int ask_to)
253 int predecessor_id = -1;
254 void* data = nullptr;
255 simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(ask_to));
256 simgrid::s4u::MailboxPtr return_mailbox = simgrid::s4u::Mailbox::byName(std::to_string(id_) + "_pred");
258 ChordMessage* message = new ChordMessage(GET_PREDECESSOR);
259 message->request_id = id_;
260 message->answer_to = return_mailbox;
262 // send a "Get Predecessor" request to ask_to_id
263 XBT_DEBUG("Sending a 'Get Predecessor' request to %d", ask_to);
265 simgrid::s4u::this_actor::send(mailbox, message, 10, timeout);
266 } catch (xbt_ex& e) {
267 if (e.category == timeout_error) {
268 XBT_DEBUG("Failed to send the 'Get Predecessor' request to %d", ask_to);
270 return predecessor_id;
274 // receive the answer
275 XBT_DEBUG("Sent 'Get Predecessor' request to %d, waiting for the answer on my mailbox '%s'", ask_to,
276 message->answer_to->name());
277 simgrid::s4u::Comm& comm = simgrid::s4u::this_actor::irecv(return_mailbox, &data);
281 ChordMessage* answer = static_cast<ChordMessage*>(data);
282 XBT_DEBUG("Received the answer to my 'Get Predecessor' request: the predecessor of node %d is %d", ask_to,
284 predecessor_id = answer->answer_id;
286 } catch (xbt_ex& e) {
287 if (e.category == timeout_error) {
288 XBT_DEBUG("Failed to receive the answer to my 'Get Predecessor' request");
289 delete static_cast<ChordMessage*>(data);
293 return predecessor_id;
296 /* Returns the closest preceding finger of an id with respect to the finger table of the current node.
298 * \param id the id to find
299 * \return the closest preceding finger of that id
301 int Node::closestPrecedingFinger(int id)
303 for (int i = nb_bits - 1; i >= 0; i--) {
304 if (is_in_interval(fingers_[i], id_ + 1, id - 1)) {
311 /* Makes the current node find the successor node of an id.
313 * \param id the id to find
314 * \return the id of the successor node, or -1 if the request failed
316 int Node::findSuccessor(int id)
318 // is my successor the successor?
319 if (is_in_interval(id, id_ + 1, fingers_[0])) {
323 // otherwise, ask the closest preceding finger in my table
324 return remoteFindSuccessor(closestPrecedingFinger(id), id);
327 int Node::remoteFindSuccessor(int ask_to, int id)
330 void* data = nullptr;
331 simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(ask_to));
332 simgrid::s4u::MailboxPtr return_mailbox = simgrid::s4u::Mailbox::byName(std::to_string(id_) + "_succ");
334 ChordMessage* message = new ChordMessage(FIND_SUCCESSOR);
335 message->request_id = id_;
336 message->answer_to = return_mailbox;
338 // send a "Find Successor" request to ask_to_id
339 XBT_DEBUG("Sending a 'Find Successor' request to %d for id %d", ask_to, id);
341 simgrid::s4u::this_actor::send(mailbox, message, 10, timeout);
342 } catch (xbt_ex& e) {
343 if (e.category == timeout_error) {
344 XBT_DEBUG("Failed to send the 'Find Successor' request to %d for id %d", ask_to, id_);
349 // receive the answer
350 XBT_DEBUG("Sent a 'Find Successor' request to %d for key %d, waiting for the answer", ask_to, id);
351 simgrid::s4u::Comm& comm = simgrid::s4u::this_actor::irecv(return_mailbox, &data);
355 ChordMessage* answer = static_cast<ChordMessage*>(data);
356 XBT_DEBUG("Received the answer to my 'Find Successor' request for id %d: the successor of key %d is %d",
357 answer->request_id, id_, answer->answer_id);
358 successor = answer->answer_id;
360 } catch (xbt_ex& e) {
361 if (e.category == timeout_error) {
362 XBT_DEBUG("Failed to receive the answer to my 'Find Successor' request");
363 delete static_cast<ChordMessage*>(data);
369 /* Notifies the current node that its predecessor may have changed. */
370 void Node::notify(int predecessor_candidate_id)
372 if (pred_id_ == -1 || is_in_interval(predecessor_candidate_id, pred_id_ + 1, id_ - 1)) {
373 setPredecessor(predecessor_candidate_id);
376 XBT_DEBUG("I don't have to change my predecessor to %d", predecessor_candidate_id);
380 /* Notifies a remote node that its predecessor may have changed. */
381 void Node::remoteNotify(int notify_id, int predecessor_candidate_id)
383 ChordMessage* message = new ChordMessage(NOTIFY);
384 message->request_id = predecessor_candidate_id;
385 message->answer_to = nullptr;
387 // send a "Notify" request to notify_id
388 XBT_DEBUG("Sending a 'Notify' request to %d", notify_id);
389 simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(notify_id));
391 // TODO make it a dsend
392 simgrid::s4u::this_actor::isend(mailbox, message, 10);
393 } catch (xbt_ex& e) {
394 if (e.category == timeout_error) {
395 XBT_DEBUG("Send of 'Notify' failed due to an expired timeout on receiver side");
401 /* This function is called periodically. It checks the immediate successor of the current node. */
402 void Node::stabilize()
404 XBT_DEBUG("Stabilizing node");
406 // get the predecessor of my immediate successor
408 int successor_id = fingers_[0];
409 if (successor_id != id_) {
410 candidate_id = remoteGetPredecessor(successor_id);
412 candidate_id = pred_id_;
415 // this node is a candidate to become my new successor
416 if (candidate_id != -1 && is_in_interval(candidate_id, id_ + 1, successor_id - 1)) {
417 setFinger(0, candidate_id);
419 if (successor_id != id_) {
420 remoteNotify(successor_id, id_);
424 /* This function is called when a node receives a message.
426 * \param message the message to handle (don't touch it afterward: it will be destroyed, reused or forwarded)
428 void Node::handleMessage(ChordMessage* message)
430 switch (message->type) {
432 XBT_DEBUG("Received a 'Find Successor' request from %s for id %d", message->issuer_host_name.c_str(),
433 message->request_id);
434 // is my successor the successor?
435 if (is_in_interval(message->request_id, id_ + 1, fingers_[0])) {
436 message->type = FIND_SUCCESSOR_ANSWER;
437 message->answer_id = fingers_[0];
438 XBT_DEBUG("Sending back a 'Find Successor Answer' to %s (mailbox %s): the successor of %d is %d",
439 message->issuer_host_name.c_str(), message->answer_to->name(), message->request_id, message->answer_id);
440 // TODO Replace by dsend
442 simgrid::s4u::this_actor::isend(message->answer_to, message, 10);
444 if (e.category == timeout_error) {
445 XBT_DEBUG("Send of 'Find Successor Answer' failed due du an expired timeout on receiver side");
449 // otherwise, forward the request to the closest preceding finger in my table
450 int closest = closestPrecedingFinger(message->request_id);
451 XBT_DEBUG("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d",
452 message->request_id, closest);
453 simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(closest));
454 //TODO make it a dsend
456 simgrid::s4u::this_actor::isend(mailbox, message, 10);
457 } catch (xbt_ex& e) {
458 if (e.category == timeout_error) {
459 XBT_DEBUG("Forward of 'Find Successor' failed due du an expired timeout on receiver side");
465 case GET_PREDECESSOR:
466 XBT_DEBUG("Receiving a 'Get Predecessor' request from %s", message->issuer_host_name.c_str());
467 message->type = GET_PREDECESSOR_ANSWER;
468 message->answer_id = pred_id_;
469 XBT_DEBUG("Sending back a 'Get Predecessor Answer' to %s via mailbox '%s': my predecessor is %d",
470 message->issuer_host_name.c_str(), message->answer_to->name(), message->answer_id);
471 //TODO make it a dsend
473 simgrid::s4u::this_actor::isend(message->answer_to, message, 10);
474 } catch (xbt_ex& e) {
475 if (e.category == timeout_error) {
476 XBT_DEBUG("Send of 'Get Predecessor Answer' failed due du an expired timeout on receiver side");
482 // someone is telling me that he may be my new predecessor
483 XBT_DEBUG("Receiving a 'Notify' request from %s", message->issuer_host_name.c_str());
484 notify(message->request_id);
488 case PREDECESSOR_LEAVING:
489 // my predecessor is about to quit
490 XBT_DEBUG("Receiving a 'Predecessor Leaving' message from %s", message->issuer_host_name.c_str());
491 // modify my predecessor
492 setPredecessor(message->request_id);
495 >> notify my new predecessor
496 >> send a notify_predecessors !!
500 case SUCCESSOR_LEAVING:
501 // my successor is about to quit
502 XBT_DEBUG("Receiving a 'Successor Leaving' message from %s", message->issuer_host_name.c_str());
503 // modify my successor FIXME : this should be implicit ?
504 setFinger(0, message->request_id);
507 >> notify my new successor
508 >> update my table & predecessors table */
511 case PREDECESSOR_ALIVE:
512 XBT_DEBUG("Receiving a 'Predecessor Alive' request from %s", message->issuer_host_name.c_str());
513 message->type = PREDECESSOR_ALIVE_ANSWER;
514 XBT_DEBUG("Sending back a 'Predecessor Alive Answer' to %s (mailbox %s)",
515 message->issuer_host_name.c_str(), message->answer_to->name());
516 //TODO Make it a dsend
518 simgrid::s4u::this_actor::isend(message->answer_to, message, 10);
519 } catch (xbt_ex& e) {
520 if (e.category == timeout_error) {
521 XBT_DEBUG("Send of 'Predecessor Alive' failed due du an expired timeout on receiver side");
527 XBT_DEBUG("Ignoring unexpected message: %d from %s", message->type, message->issuer_host_name.c_str());