[simgrid.git] / examples / lua / chord / chord.lua

-- A SimGrid Lua implementation of the Chord DHT

require("simgrid")

nb_bits = 24
nb_keys = 2^nb_bits
comp_size = 0
comm_size = 10
timeout = 50
max_simulation_time = 1000
stabilize_delay = 20
fix_fingers_delay = 120
check_predecessor_delay = 120
lookup_delay = 10

-- current node (don't worry, globals are duplicated in each process)
my_node = {
  id = my_id,
  next_finger_to_fix = 1,
  fingers = {},
  predecessor = nil,
  comm_recv = nil
}

-- Main function of each Chord process
-- Arguments:
-- - my id
-- - the id of a guy I know in the system (except for the first node)
function node(...)

  -- TODO simplify the parameters
  local known_id
  local args = {...}
  my_node.id = tonumber(args[1])
  if #args == 4 then
    known_id = tonumber(args[2])
  end

  -- initialize the node
  for i = 1, nb_bits do
    my_node.fingers[i] = my_node.id
  end
  my_node.comm_recv = simgrid.task.irecv(my_node.id)

  -- join the ring
  local join_success = false
  if known_id == nil then
    -- first node
    create()
    join_success = true
  else
    join_success = join(known_id)
  end

  -- main loop
  if join_success then

    local now = simgrid.get_clock()
    local next_stabilize_date = now + stabilize_delay
    local next_fix_fingers_date = now + fix_fingers_delay
    local next_check_predecessor_date = now + check_predecessor_delay
    local next_lookup_date = now + lookup_delay

    local task, success

    while now < max_simulation_time do

      task, success = simgrid.comm.test(my_node.comm_recv)

      if task then
        -- I received a task: answer it
        my_node.comm_recv = simgrid.task.irecv(my_node.id)
        handle_task(task)
      elseif failed then
        -- the communication has failed: nevermind
        my_node.comm_recv = simgrid.task.irecv(my_node.id)
      else
        -- no task was received: do periodic calls
        if now >= next_stabilize_date then
          stabilize()
          next_stabilize_date = simgrid.get_clock() + stabilize_delay

        elseif now >= next_fix_fingers_date then
          fix_fingers()
          next_fix_fingers_date = simgrid.get_clock() + fix_fingers_delay

        elseif now >= next_check_predecessor_date then
          check_predecessor()
          next_check_predecessor_date = simgrid.get_clock() + check_predecessor_delay
        elseif now >= next_lookup_date then
          random_lookup()
          next_lookup_date = simgrid.get_clock() + lookup_delay

        else
          -- nothing to do: sleep for a while
          simgrid.process.sleep(5)
        end
      end
      now = simgrid.get_clock()
    end -- while

    -- leave the ring
    leave()
  end
end

-- Makes the current node leave the ring
function leave()

  simgrid.info("Leaving the ring")
  -- TODO: notify others
end

-- This function is called when the current node receives a task.
-- - task: the task received
function handle_task(task)

  local type = task.type

  if type == "find successor" then

    simgrid.info("Received a 'find successor' request from " .. task.answer_to ..
        " for id " .. task.request_id)

    -- is my successor the successor?
    if is_in_interval(task.request_id, my_node.id + 1, my_node.fingers[1]) then

      simgrid.info("Sending back a 'find successor answer' to " ..
          task.answer_to .. ": the successor of " .. task.request_id ..
          " is " .. my_node.fingers[1])

      local ans_task = simgrid.task.new("", comp_size, comm_size)
      ans_task.type = "find successor answer"
      ans_task.request_id = task.request_id
      ans_task.answer = my_node.fingers[1]
      ans_task:dsend(task.answer_to)
    else
      -- forward the request to the closest preceding finger in my table

      simgrid.info("Forwarding the 'find successor' request to my closest preceding finger")

      local next_task = simgrid.task.new("", comp_size, comm_size)
      next_task.type = "find successor"
      next_task.request_id = task.request_id
      next_task.answer_to = task.answer_to
      next_task:dsend(closest_preceding_node(next_task.request_id))
    end

  elseif type == "get predecessor" then
    local ans_task = simgrid.task.new("", comp_size, comm_size)
    ans_task.type = "get predecessor answer"
    ans_task.answer = my_node.predecessor
    ans_task:dsend(task.answer_to)

  elseif type == "notify" then
    -- someone is telling me that he may be my new predecessor
    notify(task.request_id)

  elseif type == "predecessor leaving" then
    -- TODO

  elseif type == "successor_leaving" then
    -- TODO

  elseif type == "find successor answer" then
    -- ignoring

  elseif type == "get predecessor answer" then
    -- ignoring

  else
    error("Unknown type of task received: " .. task.type)
  end
end

-- Returns whether an id belongs to the interval [a, b[.
-- The parameters are normalized to make sure they are between 0 and nb_keys - 1.
-- 1 belongs to [62, 3].
-- 1 does not belong to [3, 62].
-- 63 belongs to [62, 3].
-- 63 does not belong to [3, 62].
-- 24 belongs to [21, 29].
-- 24 does not belong to [29, 21].
function is_in_interval(id, a, b)

  -- normalize the parameters
  id = id % nb_bits
  a = a % nb_bits
  b = b % nb_bits
 
  -- make sure a <= b and a <= id
  if b < a then
    b = b + nb_keys
  end

  if id < a then
    id = id + nb_keys
  end

  return id <= b
end

-- Returns whether the current node is in the ring.
function has_joined()

  return my_node.fingers[1] ~= nil
end

-- Creates a new Chord ring.
function create()
  my_node.predecessor = nil
  my_node.fingers[1] = my_node.id
end

-- Attemps to join the Chord ring.
-- - known_id: id of a node already in the ring
-- - return value: true if the join was successful
function join(known_id)

  simgrid.info("Joining the ring with id " .. my_node.id .. ", knowing node " .. known_id)

  local successor = remote_find_successor(known_id, my_node.id)
  if successor == nil then
    simgrid.info("Cannot join the ring.")
    return false
  end

  my_node.predecessor = nil
  my_node.fingers[1] = successor
  return true
end

-- Returns the closest preceding finger of an id with respect to the finger
-- table of the current node.
-- - id: the id to find
-- - return value: the closest preceding finger of that id
function closest_preceding_node(id)

  for i = nb_bits, 1, -1 do
    if is_in_interval(my_node.fingers[i], my_node.id + 1, id - 1) then
      -- finger i is the first one before id
      return my_node.fingers[i]
    end
  end
end

-- Finds the successor of an id
-- id: the id to find
-- return value: the id of the successor, or nil if the request failed
function find_successor(id)

  if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
    -- my successor is the successor
    return my_node.fingers[1]
  end

  -- ask to the closest preceding finger in my table
  local ask_to = closest_preceding_node(id)
  return remote_find_successor(ask_to, id)
end

-- Asks a remote node the successor of an id.
-- ask_to: id of a remote node to ask to
-- id: the id to find
-- return value: the id of the successor, or nil if the request failed
function remote_find_successor(ask_to, id)

  local task = simgrid.task.new("", comp_size, comm_size)
  task.type = "find successor"
  task.request_id = id
  task.answer_to = my_node.id

  simgrid.info("Sending a 'find successor' request to " .. ask_to .. " for id " .. id)
  if task:send(ask_to, timeout) then
    -- request successfully sent: wait for an answer

    simgrid.info("Sent the 'find successor' request to " .. ask_to ..
        " for id " .. id .. ", waiting for the answer")

    while true do
      task = simgrid.comm.wait(my_node.comm_recv, timeout)
      my_node.comm_recv = simgrid.task.irecv(my_node.id)
    
      if not task then
        -- failed to receive the answer
        simgrid.info("Failed to receive the answer to my 'find successor' request")
        return nil
      else
        -- a task was received: is it the expected answer?
        if task.type ~= "find successor answer" or task.request_id ~= id then
          -- this is not our answer
          simgrid.info("Received another request of type " .. task.type)
          handle_task(task)
        else
          -- this is our answer
          simgrid.info("Received the answer to my 'find successor' request for id " ..
              id .. ": the successor is " .. task.answer)
          return task.answer
        end
      end
    end
  else
    simgrid.info("Failed to send the 'find successor' request to " .. ask_to ..
        " for id " .. id)
  end

  return successor
end

-- Asks a remote node its predecessor.
-- ask_to: id of a remote node to ask to
-- return value: the id of its predecessor, or nil if the request failed
function remote_get_predecessor(ask_to)

  local task = simgrid.task.new("", comp_size, comm_size)
  task.type = "get predecessor"
  task.answer_to = my_node.id

  if task:send(ask_to, timeout) then
    -- request successfully sent: wait for an answer
    while true do
      task = simgrid.comm.wait(my_node.comm_recv, timeout)
      my_node.comm_recv = simgrid.task.irecv(my_node.id)
    
      if not task then
        -- failed to receive the answer
        return nil
      else
        -- a task was received: is it the expected answer?
        if task.type ~= "get predecessor answer" then
          -- this is not our answer
          handle_task(task)
        else
          -- this is our answer
          -- FIXME make sure the message answers to this particular request
          return task.answer
        end
      end
    end
  end

  return successor
end

-- Checks the immediate successor of the current node.
function stabilize()

  local candidate
  local successor = my_node.fingers[1]
  if successor ~= my_node.id then
    candidate = remote_get_predecessor(successor)
  else
    candidate = my_node.predecessor
  end

  -- this node is a candidate to become my new successor
  if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor - 1) then
    my_node.fingers[1] = candidate
  end

  if successor ~= my_node.id then
    remote_notify(successor, my_node.id)
  end
end

-- Notifies the current node that its predecessor my have changed
-- - candidate_predecessor: the possible new predecessor
function notify(candidate_predecessor)

  if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
      my_node.predecessor + 1, my_node.id - 1) then
    my_node.predecessor = candidate_predecessor
  end
end

-- Notifies a remote node that its predecessor my have changed.
-- - notify_to
-- - candidate the possible new predecessor
function remote_notify(notify_to, candidate_predecessor)

  local task = simgrid.task.new("", comp_size, comm_size)
  task.type = "notify"
  task.request_id = candidate_predecessor
  task:dsend(notify_to)
end

-- Refreshes the finger table of the current node.
function fix_fingers()

  local i = my_node.next_finger_to_fix
  local id = find_successor(my_node.id + 2^i)
  if id ~= nil then
    if id ~= my_node.fingers[i] then
      my_node.fingers[i] = id
    end
    my_node.next_finger_to_fix = (i % nb_bits) + 1
  end
end

-- Checks whether the predecessor of the current node has failed.
function check_predecessor()
  -- TODO
end

-- Performs a find successor request to an arbitrary id.
function random_lookup()

  find_successor(1337)
end

simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
simgrid.application(arg[2] or "../../msg/chord/chord90.xml")
simgrid.run()