1 /* Copyright (c) 2010-2020. 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 true if id in in [start, end]
25 static bool 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 void ChordMessage::destroy(void* message)
45 delete static_cast<ChordMessage*>(message);
48 /* Initializes the current node as the first one of the system */
49 Node::Node(std::vector<std::string> args)
51 xbt_assert(args.size() == 3 || args.size() == 5, "Wrong number of arguments for this node");
54 id_ = std::stoi(args[1]);
55 XBT_DEBUG("Initialize node with id: %d", id_);
57 mailbox_ = simgrid::s4u::Mailbox::by_name(std::to_string(id_));
58 next_finger_to_fix = 0;
59 fingers_.resize(nb_bits, id_);
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...");
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_);
74 /* Makes the current node join the ring, knowing the id of a node already in the ring
76 * @param known_id id of a node already in the ring
77 * @return true if the join operation succeeded
80 void Node::join(int known_id)
82 XBT_INFO("Joining the ring with id %d, knowing node %d", id_, known_id);
83 setPredecessor(-1); // no predecessor (yet)
85 int successor_id = remoteFindSuccessor(known_id, id_);
86 if (successor_id == -1) {
87 XBT_INFO("Cannot join the ring.");
89 setFinger(0, successor_id);
95 /* Makes the current node quit the system */
98 XBT_INFO("Well Guys! I Think it's time for me to leave ;)");
103 /* Notifies the successor and the predecessor of the current node before leaving */
104 void Node::notifyAndQuit()
106 // send the PREDECESSOR_LEAVING to our successor
107 auto* pred_msg = new ChordMessage(PREDECESSOR_LEAVING);
108 pred_msg->request_id = pred_id_;
109 pred_msg->answer_to = mailbox_;
111 XBT_DEBUG("Sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
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]);
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 auto* 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_);
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_);
135 /* Performs a find successor request to a random id */
136 void Node::randomLookup()
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);
147 /* Sets a finger of the current node.
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
153 void Node::setFinger(int finger_index, int id)
155 if (id != fingers_[finger_index]) {
156 fingers_[finger_index] = id;
157 XBT_VERB("My new finger #%d is %d", finger_index, id);
161 /* Sets the predecessor of the current node.
162 * @param id the id to predecessor, or -1 to unset the predecessor
164 void Node::setPredecessor(int predecessor_id)
166 if (predecessor_id != pred_id_) {
167 pred_id_ = predecessor_id;
168 XBT_VERB("My new predecessor is %d", predecessor_id);
172 /** refreshes the finger table of the current node (called periodically) */
173 void Node::fixFingers()
175 XBT_DEBUG("Fixing fingers");
176 int id = findSuccessor(id_ + (1U << next_finger_to_fix));
178 if (id != fingers_[next_finger_to_fix]) {
179 setFinger(next_finger_to_fix, id);
182 next_finger_to_fix = (next_finger_to_fix + 1) % nb_bits;
186 /** Displays the finger table of a node. */
187 void Node::printFingerTable()
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]);
196 XBT_VERB("Predecessor: %d", pred_id_);
200 /* checks whether the predecessor has failed (called periodically) */
201 void Node::checkPredecessor()
203 XBT_DEBUG("Checking whether my predecessor is alive");
204 void* data = nullptr;
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");
211 auto* message = new ChordMessage(PREDECESSOR_ALIVE);
212 message->request_id = pred_id_;
213 message->answer_to = return_mailbox;
215 XBT_DEBUG("Sending a 'Predecessor Alive' request to my predecessor %d", pred_id_);
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_);
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);
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");
239 /* Asks its predecessor to a remote node
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)
244 int Node::remoteGetPredecessor(int ask_to)
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");
251 auto* message = new ChordMessage(GET_PREDECESSOR);
252 message->request_id = id_;
253 message->answer_to = return_mailbox;
255 // send a "Get Predecessor" request to ask_to_id
256 XBT_DEBUG("Sending a 'Get Predecessor' request to %d", ask_to);
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);
262 return predecessor_id;
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);
271 comm->wait_for(timeout);
272 const auto* 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,
275 predecessor_id = answer->answer_id;
277 } catch (const simgrid::TimeoutException&) {
278 XBT_DEBUG("Failed to receive the answer to my 'Get Predecessor' request");
279 delete static_cast<ChordMessage*>(data);
282 return predecessor_id;
285 /* Returns the closest preceding finger of an id with respect to the finger table of the current node.
287 * @param id the id to find
288 * @return the closest preceding finger of that id
290 int Node::closestPrecedingFinger(int id)
292 for (int i = nb_bits - 1; i >= 0; i--) {
293 if (is_in_interval(fingers_[i], id_ + 1, id - 1)) {
300 /* Makes the current node find the successor node of an id.
302 * @param id the id to find
303 * @return the id of the successor node, or -1 if the request failed
305 int Node::findSuccessor(int id)
307 // is my successor the successor?
308 if (is_in_interval(id, id_ + 1, fingers_[0])) {
312 // otherwise, ask the closest preceding finger in my table
313 return remoteFindSuccessor(closestPrecedingFinger(id), id);
316 int Node::remoteFindSuccessor(int ask_to, int id)
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");
323 auto* message = new ChordMessage(FIND_SUCCESSOR);
324 message->request_id = id_;
325 message->answer_to = return_mailbox;
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);
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_);
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));
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;
347 } catch (const simgrid::TimeoutException&) {
348 XBT_DEBUG("Failed to receive the answer to my 'Find Successor' request");
355 /* Notifies the current node that its predecessor may have changed. */
356 void Node::notify(int predecessor_candidate_id)
358 if (pred_id_ == -1 || is_in_interval(predecessor_candidate_id, pred_id_ + 1, id_ - 1)) {
359 setPredecessor(predecessor_candidate_id);
362 XBT_DEBUG("I don't have to change my predecessor to %d", predecessor_candidate_id);
366 /* Notifies a remote node that its predecessor may have changed. */
367 void Node::remoteNotify(int notify_id, int predecessor_candidate_id) const
369 auto* message = new ChordMessage(NOTIFY);
370 message->request_id = predecessor_candidate_id;
371 message->answer_to = nullptr;
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);
379 /* This function is called periodically. It checks the immediate successor of the current node. */
380 void Node::stabilize()
382 XBT_DEBUG("Stabilizing node");
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);
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);
394 if (successor_id != id_) {
395 remoteNotify(successor_id, id_);
399 /* This function is called when a node receives a message.
401 * @param message the message to handle (don't touch it afterward: it will be destroyed, reused or forwarded)
403 void Node::handleMessage(ChordMessage* message)
405 switch (message->type) {
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,
416 message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
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);
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);
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);
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);
450 >> notify my new predecessor
451 >> send a notify_predecessors !!
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);
462 >> notify my new successor
463 >> update my table & predecessors table */
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);
475 XBT_DEBUG("Ignoring unexpected message: %d from %s", message->type, message->issuer_host_name.c_str());
480 void Node::operator()()
482 simgrid::s4u::this_actor::sleep_for(start_time_);
483 if (known_id_ == -1) {
484 setPredecessor(-1); // -1 means that I have no predecessor
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;
505 if (not comm_receive->test())
506 comm_completed = false;
507 } catch (const simgrid::TimeoutException&) {
508 XBT_DEBUG("Caught a timeout, go ahead.");
511 if (comm_completed) {
512 if (data != nullptr) {
513 auto* message = static_cast<ChordMessage*>(data);
514 handleMessage(message);
517 comm_receive = nullptr;
519 // no task was received: make some periodic calls
520 if (now >= next_stabilize_date) {
522 next_stabilize_date = simgrid::s4u::Engine::get_clock() + PERIODIC_STABILIZE_DELAY;
523 } else if (now >= next_fix_fingers_date) {
525 next_fix_fingers_date = simgrid::s4u::Engine::get_clock() + PERIODIC_FIX_FINGERS_DELAY;
526 } else if (now >= next_check_predecessor_date) {
528 next_check_predecessor_date = simgrid::s4u::Engine::get_clock() + PERIODIC_CHECK_PREDECESSOR_DELAY;
529 } else if (now >= next_lookup_date) {
531 next_lookup_date = simgrid::s4u::Engine::get_clock() + PERIODIC_LOOKUP_DELAY;
533 // nothing to do: sleep for a while
534 simgrid::s4u::this_actor::sleep_for(SLEEP_DELAY);
538 now = simgrid::s4u::Engine::get_clock();
540 if (comm_receive != nullptr) {
542 if (comm_receive->test())
543 delete static_cast<ChordMessage*>(data);
545 comm_receive->cancel();
546 } catch (const simgrid::TimeoutException&) {
547 XBT_DEBUG("Caught a timeout for last message, nevermind.");