1 /* Copyright (c) 2006-2017. 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. */
8 import org.simgrid.msg.Msg;
9 import org.simgrid.msg.Comm;
10 import org.simgrid.msg.Host;
11 import org.simgrid.msg.Task;
12 import org.simgrid.msg.Process;
13 import org.simgrid.msg.MsgException;
14 import org.simgrid.msg.TimeoutException;
15 public class Node extends Process {
17 protected String mailbox;
19 protected String predMailbox;
20 protected int nextFingerToFix;
21 protected Comm commReceive;
22 ///Last time I changed a finger or my predecessor
23 protected double lastChangeDate;
24 private int[] fingers;
26 public Node(Host host, String name, String[] args) {
27 super(host,name,args);
31 public void main(String[] args) throws MsgException {
32 if (args.length != 2 && args.length != 4) {
33 Msg.info("You need to provide 2 or 4 arguments.");
36 double initTime = Msg.getClock();
41 double nextStabilizeDate = initTime + Common.PERIODIC_STABILIZE_DELAY;
42 double nextFixFingersDate = initTime + Common.PERIODIC_FIX_FINGERS_DELAY;
43 double nextCheckPredecessorDate = initTime + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
44 double nextLookupDate = initTime + Common.PERIODIC_LOOKUP_DELAY;
47 id = Integer.parseInt(args[0]);
49 fingers = new int[Common.NB_BITS];
50 for (i = 0; i < Common.NB_BITS; i++) {
56 if (args.length == 2) {
57 deadline = Integer.parseInt(args[1]);
61 int knownId = Integer.parseInt(args[1]);
62 deadline = Integer.parseInt(args[3]);
63 Msg.debug("Hey! Let's join the system with the id " + id + ".");
65 joinSuccess = join(knownId);
68 double currentClock = Msg.getClock();
69 while (currentClock < (initTime + deadline) && currentClock < Common.MAX_SIMULATION_TIME) {
70 if (commReceive == null) {
71 commReceive = Task.irecv(this.mailbox);
74 if (!commReceive.test()) {
75 if (currentClock >= nextStabilizeDate) {
77 nextStabilizeDate = Msg.getClock() + Common.PERIODIC_STABILIZE_DELAY;
78 } else if (currentClock >= nextFixFingersDate) {
80 nextFixFingersDate = Msg.getClock() + Common.PERIODIC_FIX_FINGERS_DELAY;
81 } else if (currentClock >= nextCheckPredecessorDate) {
82 this.checkPredecessor();
83 nextCheckPredecessorDate = Msg.getClock() + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
84 } else if (currentClock >= nextLookupDate) {
86 nextLookupDate = Msg.getClock() + Common.PERIODIC_LOOKUP_DELAY;
90 currentClock = Msg.getClock();
92 handleTask(commReceive.getTask());
93 currentClock = Msg.getClock();
98 currentClock = Msg.getClock();
103 if (commReceive != null) {
107 Msg.info("I couldn't join the ring");
111 private void handleTask(Task task) {
112 if (task instanceof FindSuccessorTask) {
113 FindSuccessorTask fTask = (FindSuccessorTask)task;
114 Msg.debug("Receiving a 'Find Successor' request from " + fTask.getIssuerHostName() + " for id " +
115 fTask.getRequestId());
116 // is my successor the successor?
117 if (isInInterval(fTask.getRequestId(), this.id + 1, fingers[0])) {
118 Msg.debug("Send the request to " + fTask.getAnswerTo() + " with answer " + fingers[0]);
119 FindSuccessorAnswerTask answer = new FindSuccessorAnswerTask(getHost().getName(), mailbox, fingers[0]);
120 answer.dsend(fTask.getAnswerTo());
122 // otherwise, forward the request to the closest preceding finger in my table
123 int closest = closestPrecedingNode(fTask.getRequestId());
124 Msg.debug("Forward the request to " + closest);
125 fTask.dsend(Integer.toString(closest));
127 } else if (task instanceof GetPredecessorTask) {
128 GetPredecessorTask gTask = (GetPredecessorTask)(task);
129 Msg.debug("Receiving a 'Get Predecessor' request from " + gTask.getIssuerHostName());
130 GetPredecessorAnswerTask answer = new GetPredecessorAnswerTask(getHost().getName(), mailbox, predId);
131 answer.dsend(gTask.getAnswerTo());
132 } else if (task instanceof NotifyTask) {
133 NotifyTask nTask = (NotifyTask)task;
134 notify(nTask.getRequestId());
136 Msg.debug("Ignoring unexpected task of type:" + task);
140 private void leave() {
141 Msg.debug("Well Guys! I Think it's time for me to quit ;)");
142 // TODO: Notify my successor and predecessor.
145 /** @brief Initializes the current node as the first one of the system */
146 private void create() {
147 Msg.debug("Create a new Chord ring...");
151 // Makes the current node join the ring, knowing the id of a node already in the ring
152 private boolean join(int knownId) {
153 Msg.info("Joining the ring with id " + this.id + " knowing node " + knownId);
155 int successorId = remoteFindSuccessor(knownId, this.id);
156 if (successorId == -1) {
157 Msg.info("Cannot join the ring.");
159 setFinger(0, successorId);
161 return successorId != -1;
164 private void setPredecessor(int predecessorId) {
165 if (predecessorId != predId) {
166 predId = predecessorId;
167 if (predecessorId != -1) {
168 predMailbox = Integer.toString(predId);
170 lastChangeDate = Msg.getClock();
175 * @brief Asks another node its predecessor.
176 * @param askTo the node to ask to
177 * @return the id of its predecessor node, or -1 if the request failed(or if the node does not know its predecessor)
179 private int remoteGetPredecessor(int askTo) {
180 int predecessorId = -1;
181 boolean stop = false;
182 Msg.debug("Sending a 'Get Predecessor' request to " + askTo);
183 String mailboxTo = Integer.toString(askTo);
184 GetPredecessorTask sendTask = new GetPredecessorTask(getHost().getName(), this.mailbox);
186 sendTask.send(mailboxTo, Common.TIMEOUT);
189 if (commReceive == null) {
190 commReceive = Task.irecv(this.mailbox);
192 commReceive.waitCompletion(Common.TIMEOUT);
193 Task taskReceived = commReceive.getTask();
194 if (taskReceived instanceof GetPredecessorAnswerTask) {
195 predecessorId = ((GetPredecessorAnswerTask) taskReceived).getAnswerId();
198 handleTask(taskReceived);
203 catch (MsgException e) {
207 catch (MsgException e) {
208 Msg.debug("Failed to send the Get Predecessor request");
210 return predecessorId;
214 * @brief Makes the current node find the successor node of an id.
215 * @param node the current node
216 * @param id the id to find
217 * @return the id of the successor node, or -1 if the request failed
219 private int findSuccessor(int id) {
220 if (isInInterval(id, this.id + 1, fingers[0])) {
224 int closest = this.closestPrecedingNode(id);
225 return remoteFindSuccessor(closest, id);
228 // Asks another node the successor node of an id.
229 private int remoteFindSuccessor(int askTo, int id) {
231 boolean stop = false;
232 String askToMailbox = Integer.toString(askTo);
233 Task sendTask = new FindSuccessorTask(getHost().getName(), this.mailbox, id);
234 Msg.debug("Sending a 'Find Successor' request to " + askToMailbox + " for id " + id);
236 sendTask.send(askToMailbox, Common.TIMEOUT);
238 if (commReceive == null) {
239 commReceive = Task.irecv(this.mailbox);
242 commReceive.waitCompletion(Common.TIMEOUT);
243 Task task = commReceive.getTask();
244 if (task instanceof FindSuccessorAnswerTask) {
245 //TODO: Check if this this our answer.
246 FindSuccessorAnswerTask fTask = (FindSuccessorAnswerTask) task;
248 successor = fTask.getAnswerId();
254 catch (TimeoutException e) {
260 catch (TimeoutException e) {
261 Msg.debug("Failed to send the 'Find Successor' request");
263 catch (MsgException e) {
264 Msg.debug("Failed to receive Find Successor");
270 // This function is called periodically. It checks the immediate successor of the current node.
271 private void stabilize() {
272 Msg.debug("Stabilizing node");
274 int successorId = fingers[0];
275 if (successorId != this.id){
276 candidateId = remoteGetPredecessor(successorId);
278 candidateId = predId;
280 //This node is a candidate to become my new successor
281 if (candidateId != -1 && isInInterval(candidateId, this.id + 1, successorId - 1)) {
282 setFinger(0, candidateId);
284 if (successorId != this.id) {
285 remoteNotify(successorId, this.id);
290 * @brief Notifies the current node that its predecessor may have changed.
291 * @param candidate_id the possible new predecessor
293 private void notify(int predecessorCandidateId) {
294 if (predId == -1 || isInInterval(predecessorCandidateId, predId + 1, this.id - 1 )) {
295 setPredecessor(predecessorCandidateId);
300 * @brief Notifies a remote node that its predecessor may have changed.
301 * @param notify_id id of the node to notify
302 * @param candidate_id the possible new predecessor
304 private void remoteNotify(int notifyId, int predecessorCandidateId) {
305 Msg.debug("Sending a 'Notify' request to " + notifyId);
306 Task sentTask = new NotifyTask(getHost().getName(), this.mailbox, predecessorCandidateId);
307 sentTask.dsend(Integer.toString(notifyId));
310 // This function is called periodically.
311 // It refreshes the finger table of the current node.
312 private void fixFingers() {
313 Msg.debug("Fixing fingers");
314 int i = this.nextFingerToFix;
315 int successorId = this.findSuccessor(this.id + (int)Math.pow(2,i)); //FIXME: SLOW
316 if (successorId != -1) {
317 if (successorId != fingers[i]) {
318 setFinger(i, successorId);
320 nextFingerToFix = (i + 1) % Common.NB_BITS;
324 // This function is called periodically.
325 // It checks whether the predecessor has failed
326 private void checkPredecessor() {
330 // Performs a find successor request to a random id.
331 private void randomLookup() {
333 //Msg.info("Making a lookup request for id " + dest);
338 * @brief Returns the closest preceding finger of an id with respect to the finger table of the current node.
339 * @param id the id to find
340 * @return the closest preceding finger of that id
342 private int closestPrecedingNode(int id) {
343 for (int i = Common.NB_BITS - 1; i >= 0; i--) {
344 if (isInInterval(fingers[i], this.id + 1, id - 1)) {
352 * @brief Returns whether an id belongs to the interval [start, end].
354 * The parameters are noramlized to make sure they are between 0 and nb_keys - 1).
355 * 1 belongs to [62, 3]
356 * 1 does not belong to [3, 62]
357 * 63 belongs to [62, 3]
358 * 63 does not belong to [3, 62]
359 * 24 belongs to [21, 29]
360 * 24 does not belong to [29, 21]
362 * @param id id to check
363 * @param start lower bound
364 * @param end upper bound
365 * @return a non-zero value if id in in [start, end]
367 private static boolean isInInterval(int id, int start, int end) {
368 int normId = normalize(id);
369 int normStart = normalize(start);
370 int normEnd = normalize(end);
372 // make sure end >= start and id >= start
373 if (normEnd < normStart) {
374 normEnd += Common.NB_KEYS;
376 if (normId < normStart) {
377 normId += Common.NB_KEYS;
379 return (normId <= normEnd);
383 * @brief Turns an id into an equivalent id in [0, nb_keys).
385 * @return the corresponding normalized id
387 private static int normalize(int id) {
388 return id & (Common.NB_KEYS - 1);
392 * @brief Sets a finger of the current node.
393 * @param finger_index index of the finger to set (0 to nb_bits - 1)
394 * @param id the id to set for this finger
396 private void setFinger(int fingerIndex, int id) {
397 if (id != fingers[fingerIndex]) {
398 fingers[fingerIndex] = id;
399 lastChangeDate = Msg.getClock();