1 /* Copyright (c) 2010-2023. 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);
9 namespace sg4 = simgrid::s4u;
11 void ChordMessage::destroy(void* message)
13 delete static_cast<ChordMessage*>(message);
16 /* Returns whether an id belongs to the interval [start, end].
18 * The parameters are normalized to make sure they are between 0 and nb_keys_ - 1).
19 * 1 belongs to [62, 3]
20 * 1 does not belong to [3, 62]
21 * 63 belongs to [62, 3]
22 * 63 does not belong to [3, 62]
23 * 24 belongs to [21, 29]
24 * 24 does not belong to [29, 21]
26 * @param id id to check
27 * @param start lower bound
28 * @param end upper bound
29 * @return true if id in in [start, end]
31 bool Node::is_in_interval(int id, int start, int end)
33 int i = id % nb_keys_;
34 int s = start % nb_keys_;
35 int e = end % nb_keys_;
37 // make sure end >= start and id >= start
49 void Node::set_parameters(int nb_bits, int nb_keys, int timeout)
56 /* Initializes the current node as the first one of the system */
57 Node::Node(std::vector<std::string> args)
59 xbt_assert(args.size() == 3 || args.size() == 5, "Wrong number of arguments for this node");
62 id_ = std::stoi(args[1]);
63 XBT_DEBUG("Initialize node with id: %d", id_);
64 random_.set_seed(id_);
65 mailbox_ = sg4::Mailbox::by_name(std::to_string(id_));
66 next_finger_to_fix_ = 0;
67 fingers_.resize(nb_bits_, id_);
69 if (args.size() == 3) { // first ring
70 deadline_ = std::stod(args[2]);
71 start_time_ = sg4::Engine::get_clock();
72 XBT_DEBUG("Create a new Chord ring...");
74 known_id_ = std::stoi(args[2]);
75 start_time_ = std::stod(args[3]);
76 deadline_ = std::stod(args[4]);
77 XBT_DEBUG("Hey! Let's join the system in %f seconds (shall leave at time %f)", start_time_,
78 start_time_ + deadline_);
82 /* Makes the current node join the ring, knowing the id of a node already in the ring
84 * @param known_id id of a node already in the ring
85 * @return true if the join operation succeeded
88 void Node::join(int known_id)
90 XBT_INFO("Joining the ring with id %d, knowing node %d", id_, known_id);
91 setPredecessor(-1); // no predecessor (yet)
93 int successor_id = remoteFindSuccessor(known_id, id_);
94 if (successor_id == -1) {
95 XBT_INFO("Cannot join the ring.");
97 setFinger(0, successor_id);
103 /* Makes the current node quit the system */
106 XBT_INFO("Well Guys! I Think it's time for me to leave ;)");
111 /* Notifies the successor and the predecessor of the current node before leaving */
112 void Node::notifyAndQuit()
114 // send the PREDECESSOR_LEAVING to our successor
115 auto* pred_msg = new ChordMessage(MessageType::PREDECESSOR_LEAVING);
116 pred_msg->request_id = pred_id_;
117 pred_msg->answer_to = mailbox_;
119 XBT_DEBUG("Sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
121 sg4::Mailbox::by_name(std::to_string(fingers_[0]))->put(pred_msg, 10, timeout_);
122 } catch (const simgrid::TimeoutException&) {
123 XBT_DEBUG("Timeout expired when sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
127 if (pred_id_ != -1 && pred_id_ != id_) {
128 // send the SUCCESSOR_LEAVING to our predecessor (only if I have one that is not me)
129 auto* succ_msg = new ChordMessage(MessageType::SUCCESSOR_LEAVING);
130 succ_msg->request_id = fingers_[0];
131 succ_msg->answer_to = mailbox_;
132 XBT_DEBUG("Sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
135 sg4::Mailbox::by_name(std::to_string(pred_id_))->put(succ_msg, 10, timeout_);
136 } catch (const simgrid::TimeoutException&) {
137 XBT_DEBUG("Timeout expired when sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
143 /* Performs a find successor request to a random id */
144 void Node::randomLookup()
147 int random_index = random_.uniform_int(0, nb_bits_ - 1);
148 int random_id = fingers_[random_index];
149 XBT_DEBUG("Making a lookup request for id %d", random_id);
150 if (random_id != id_)
151 res = findSuccessor(random_id);
152 XBT_DEBUG("The successor of node %d is %d", random_id, res);
155 /* Sets a finger of the current node.
157 * @param node the current node
158 * @param finger_index index of the finger to set (0 to nb_bits_ - 1)
159 * @param id the id to set for this finger
161 void Node::setFinger(int finger_index, int id)
163 if (id != fingers_[finger_index]) {
164 fingers_[finger_index] = id;
165 XBT_VERB("My new finger #%d is %d", finger_index, id);
169 /* Sets the predecessor of the current node.
170 * @param id the id to predecessor, or -1 to unset the predecessor
172 void Node::setPredecessor(int predecessor_id)
174 if (predecessor_id != pred_id_) {
175 pred_id_ = predecessor_id;
176 XBT_VERB("My new predecessor is %d", predecessor_id);
180 /** refreshes the finger table of the current node (called periodically) */
181 void Node::fixFingers()
183 XBT_DEBUG("Fixing fingers");
184 int id = findSuccessor(id_ + (1U << next_finger_to_fix_));
186 if (id != fingers_[next_finger_to_fix_]) {
187 setFinger(next_finger_to_fix_, id);
190 next_finger_to_fix_ = (next_finger_to_fix_ + 1) % nb_bits_;
194 /** Displays the finger table of a node. */
195 void Node::printFingerTable()
197 if (XBT_LOG_ISENABLED(s4u_chord, xbt_log_priority_verbose)) {
198 XBT_VERB("My finger table:");
199 XBT_VERB("Start | Succ");
200 for (int i = 0; i < nb_bits_; i++) {
201 XBT_VERB(" %3u | %3d", (id_ + (1U << i)) % nb_keys_, fingers_[i]);
204 XBT_VERB("Predecessor: %d", pred_id_);
208 /* checks whether the predecessor has failed (called periodically) */
209 void Node::checkPredecessor()
211 XBT_DEBUG("Checking whether my predecessor is alive");
215 sg4::Mailbox* mailbox = sg4::Mailbox::by_name(std::to_string(pred_id_));
216 sg4::Mailbox* return_mailbox = sg4::Mailbox::by_name(std::to_string(id_) + "_is_alive");
218 auto* message = new ChordMessage(MessageType::PREDECESSOR_ALIVE);
219 message->request_id = pred_id_;
220 message->answer_to = return_mailbox;
222 XBT_DEBUG("Sending a 'Predecessor Alive' request to my predecessor %d", pred_id_);
224 mailbox->put(message, 10, timeout_);
225 } catch (const simgrid::TimeoutException&) {
226 XBT_DEBUG("Failed to send the 'Predecessor Alive' request to %d", pred_id_);
231 // receive the answer
232 XBT_DEBUG("Sent 'Predecessor Alive' request to %d, waiting for the answer on my mailbox '%s'", pred_id_,
233 message->answer_to->get_cname());
234 ChordMessage* answer = nullptr;
235 sg4::CommPtr comm = return_mailbox->get_async<ChordMessage>(&answer);
238 comm->wait_for(timeout_);
239 XBT_DEBUG("Received the answer to my 'Predecessor Alive': my predecessor %d is alive", pred_id_);
241 } catch (const simgrid::TimeoutException&) {
242 XBT_DEBUG("Failed to receive the answer to my 'Predecessor Alive' request");
247 /* Asks its predecessor to a remote node
249 * @param ask_to the node to ask to
250 * @return the id of its predecessor node, or -1 if the request failed (or if the node does not know its predecessor)
252 int Node::remoteGetPredecessor(int ask_to)
254 int predecessor_id = -1;
255 sg4::Mailbox* mailbox = sg4::Mailbox::by_name(std::to_string(ask_to));
256 sg4::Mailbox* return_mailbox = sg4::Mailbox::by_name(std::to_string(id_) + "_pred");
258 auto* message = new ChordMessage(MessageType::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 mailbox->put(message, 10, timeout_);
266 } catch (const simgrid::TimeoutException&) {
267 XBT_DEBUG("Failed to send the 'Get Predecessor' request to %d", ask_to);
269 return predecessor_id;
272 // receive the answer
273 XBT_DEBUG("Sent 'Get Predecessor' request to %d, waiting for the answer on my mailbox '%s'", ask_to,
274 message->answer_to->get_cname());
275 ChordMessage* answer = nullptr;
276 sg4::CommPtr comm = return_mailbox->get_async<ChordMessage>(&answer);
279 comm->wait_for(timeout_);
280 XBT_DEBUG("Received the answer to my 'Get Predecessor' request: the predecessor of node %d is %d", ask_to,
282 predecessor_id = answer->answer_id;
284 } catch (const simgrid::TimeoutException&) {
285 XBT_DEBUG("Failed to receive the answer to my 'Get Predecessor' request");
289 return predecessor_id;
292 /* Returns the closest preceding finger of an id with respect to the finger table of the current node.
294 * @param id the id to find
295 * @return the closest preceding finger of that id
297 int Node::closestPrecedingFinger(int id)
299 for (int i = nb_bits_ - 1; i >= 0; i--) {
300 if (is_in_interval(fingers_[i], id_ + 1, id - 1)) {
307 /* Makes the current node find the successor node of an id.
309 * @param id the id to find
310 * @return the id of the successor node, or -1 if the request failed
312 int Node::findSuccessor(int id)
314 // is my successor the successor?
315 if (is_in_interval(id, id_ + 1, fingers_[0])) {
319 // otherwise, ask the closest preceding finger in my table
320 return remoteFindSuccessor(closestPrecedingFinger(id), id);
323 int Node::remoteFindSuccessor(int ask_to, int id)
326 sg4::Mailbox* mailbox = sg4::Mailbox::by_name(std::to_string(ask_to));
327 sg4::Mailbox* return_mailbox = sg4::Mailbox::by_name(std::to_string(id_) + "_succ");
329 auto* message = new ChordMessage(MessageType::FIND_SUCCESSOR);
330 message->request_id = id_;
331 message->answer_to = return_mailbox;
333 // send a "Find Successor" request to ask_to_id
334 XBT_DEBUG("Sending a 'Find Successor' request to %d for id %d", ask_to, id);
336 mailbox->put(message, 10, timeout_);
337 } catch (const simgrid::TimeoutException&) {
338 XBT_DEBUG("Failed to send the 'Find Successor' request to %d for id %d", ask_to, id_);
342 // receive the answer
343 XBT_DEBUG("Sent a 'Find Successor' request to %d for key %d, waiting for the answer", ask_to, id);
344 ChordMessage* answer = nullptr;
345 sg4::CommPtr comm = return_mailbox->get_async<ChordMessage>(&answer);
348 comm->wait_for(timeout_);
349 XBT_DEBUG("Received the answer to my 'Find Successor' request for id %d: the successor of key %d is %d",
350 answer->request_id, id_, answer->answer_id);
351 successor = answer->answer_id;
353 } catch (const simgrid::TimeoutException&) {
354 XBT_DEBUG("Failed to receive the answer to my 'Find Successor' request");
361 /* Notifies the current node that its predecessor may have changed. */
362 void Node::notify(int predecessor_candidate_id)
364 if (pred_id_ == -1 || is_in_interval(predecessor_candidate_id, pred_id_ + 1, id_ - 1)) {
365 setPredecessor(predecessor_candidate_id);
368 XBT_DEBUG("I don't have to change my predecessor to %d", predecessor_candidate_id);
372 /* Notifies a remote node that its predecessor may have changed. */
373 void Node::remoteNotify(int notify_id, int predecessor_candidate_id) const
375 auto* message = new ChordMessage(MessageType::NOTIFY);
376 message->request_id = predecessor_candidate_id;
377 message->answer_to = nullptr;
379 // send a "Notify" request to notify_id
380 XBT_DEBUG("Sending a 'Notify' request to %d", notify_id);
381 sg4::Mailbox* mailbox = sg4::Mailbox::by_name(std::to_string(notify_id));
382 mailbox->put_init(message, 10)->detach(ChordMessage::destroy);
385 /* This function is called periodically. It checks the immediate successor of the current node. */
386 void Node::stabilize()
388 XBT_DEBUG("Stabilizing node");
390 // get the predecessor of my immediate successor
391 int candidate_id = pred_id_;
392 int successor_id = fingers_[0];
393 if (successor_id != id_)
394 candidate_id = remoteGetPredecessor(successor_id);
396 // this node is a candidate to become my new successor
397 if (candidate_id != -1 && is_in_interval(candidate_id, id_ + 1, successor_id - 1)) {
398 setFinger(0, candidate_id);
400 if (successor_id != id_) {
401 remoteNotify(successor_id, id_);
405 /* This function is called when a node receives a message.
407 * @param message the message to handle (don't touch it afterward: it will be destroyed, reused or forwarded)
409 void Node::handleMessage(ChordMessage* message)
411 switch (message->type) {
412 case MessageType::FIND_SUCCESSOR:
413 XBT_DEBUG("Received a 'Find Successor' request from %s for id %d", message->issuer_host_name.c_str(),
414 message->request_id);
415 // is my successor the successor?
416 if (is_in_interval(message->request_id, id_ + 1, fingers_[0])) {
417 message->type = MessageType::FIND_SUCCESSOR_ANSWER;
418 message->answer_id = fingers_[0];
419 XBT_DEBUG("Sending back a 'Find Successor Answer' to %s (mailbox %s): the successor of %d is %d",
420 message->issuer_host_name.c_str(), message->answer_to->get_cname(), message->request_id,
422 message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
424 // otherwise, forward the request to the closest preceding finger in my table
425 int closest = closestPrecedingFinger(message->request_id);
426 XBT_DEBUG("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d",
427 message->request_id, closest);
428 sg4::Mailbox* mailbox = sg4::Mailbox::by_name(std::to_string(closest));
429 mailbox->put_init(message, 10)->detach(ChordMessage::destroy);
433 case MessageType::GET_PREDECESSOR:
434 XBT_DEBUG("Receiving a 'Get Predecessor' request from %s", message->issuer_host_name.c_str());
435 message->type = MessageType::GET_PREDECESSOR_ANSWER;
436 message->answer_id = pred_id_;
437 XBT_DEBUG("Sending back a 'Get Predecessor Answer' to %s via mailbox '%s': my predecessor is %d",
438 message->issuer_host_name.c_str(), message->answer_to->get_cname(), message->answer_id);
439 message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
442 case MessageType::NOTIFY:
443 // someone is telling me that he may be my new predecessor
444 XBT_DEBUG("Receiving a 'Notify' request from %s", message->issuer_host_name.c_str());
445 notify(message->request_id);
449 case MessageType::PREDECESSOR_LEAVING:
450 // my predecessor is about to quit
451 XBT_DEBUG("Receiving a 'Predecessor Leaving' message from %s", message->issuer_host_name.c_str());
452 // modify my predecessor
453 setPredecessor(message->request_id);
456 >> notify my new predecessor
457 >> send a notify_predecessors !!
461 case MessageType::SUCCESSOR_LEAVING:
462 // my successor is about to quit
463 XBT_DEBUG("Receiving a 'Successor Leaving' message from %s", message->issuer_host_name.c_str());
464 // modify my successor FIXME : this should be implicit ?
465 setFinger(0, message->request_id);
468 >> notify my new successor
469 >> update my table & predecessors table */
472 case MessageType::PREDECESSOR_ALIVE:
473 XBT_DEBUG("Receiving a 'Predecessor Alive' request from %s", message->issuer_host_name.c_str());
474 message->type = MessageType::PREDECESSOR_ALIVE_ANSWER;
475 XBT_DEBUG("Sending back a 'Predecessor Alive Answer' to %s (mailbox %s)", message->issuer_host_name.c_str(),
476 message->answer_to->get_cname());
477 message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
481 XBT_DEBUG("Ignoring unexpected message: %d from %s", static_cast<int>(message->type),
482 message->issuer_host_name.c_str());
487 void Node::operator()()
489 sg4::this_actor::sleep_for(start_time_);
490 if (known_id_ == -1) {
491 setPredecessor(-1); // -1 means that I have no predecessor
500 ChordMessage* message = nullptr;
501 double now = sg4::Engine::get_clock();
502 double next_stabilize_date = start_time_ + PERIODIC_STABILIZE_DELAY;
503 double next_fix_fingers_date = start_time_ + PERIODIC_FIX_FINGERS_DELAY;
504 double next_check_predecessor_date = start_time_ + PERIODIC_CHECK_PREDECESSOR_DELAY;
505 double next_lookup_date = start_time_ + PERIODIC_LOOKUP_DELAY;
506 sg4::CommPtr comm_receive = nullptr;
507 while (now < std::min(start_time_ + deadline_, MAX_SIMULATION_TIME)) {
508 if (comm_receive == nullptr)
509 comm_receive = mailbox_->get_async<ChordMessage>(&message);
510 bool comm_completed = true;
512 if (not comm_receive->test())
513 comm_completed = false;
514 } catch (const simgrid::TimeoutException&) {
515 XBT_DEBUG("Caught a timeout, go ahead.");
518 if (comm_completed) {
519 if (message != nullptr) {
520 handleMessage(message);
523 comm_receive = nullptr;
525 // no task was received: make some periodic calls
526 if (now >= next_stabilize_date) {
528 next_stabilize_date = sg4::Engine::get_clock() + PERIODIC_STABILIZE_DELAY;
529 } else if (now >= next_fix_fingers_date) {
531 next_fix_fingers_date = sg4::Engine::get_clock() + PERIODIC_FIX_FINGERS_DELAY;
532 } else if (now >= next_check_predecessor_date) {
534 next_check_predecessor_date = sg4::Engine::get_clock() + PERIODIC_CHECK_PREDECESSOR_DELAY;
535 } else if (now >= next_lookup_date) {
537 next_lookup_date = sg4::Engine::get_clock() + PERIODIC_LOOKUP_DELAY;
539 // nothing to do: sleep for a while
540 sg4::this_actor::sleep_for(SLEEP_DELAY);
544 now = sg4::Engine::get_clock();
546 if (comm_receive != nullptr) {
548 if (comm_receive->test())
551 comm_receive->cancel();
552 } catch (const simgrid::TimeoutException&) {
553 XBT_DEBUG("Caught a timeout for last message, nevermind.");