SimGrid  3.13
Versatile Simulation of Distributed Systems
dht-chord.c File Reference
#include "simgrid/msg.h"
#include "simgrid/modelchecker.h"
#include <xbt/RngStream.h>
#include "src/mc/mc_replay.h"

Classes

struct  s_finger
 
struct  s_node
 
struct  s_task_data
 

Macros

#define COMM_SIZE   10
 
#define COMP_SIZE   0
 
#define MAILBOX_NAME_SIZE   10
 

Typedefs

typedef struct s_finger s_finger_t
 
typedef struct s_fingerfinger_t
 
typedef struct s_node s_node_t
 
typedef struct s_nodenode_t
 
typedef struct s_task_data s_task_data_t
 
typedef struct s_task_datatask_data_t
 

Enumerations

enum  e_task_type_t {
  TASK_FIND_SUCCESSOR, TASK_FIND_SUCCESSOR_ANSWER, TASK_GET_PREDECESSOR, TASK_GET_PREDECESSOR_ANSWER,
  TASK_NOTIFY, TASK_SUCCESSOR_LEAVING, TASK_PREDECESSOR_LEAVING, TASK_PREDECESSOR_ALIVE,
  TASK_PREDECESSOR_ALIVE_ANSWER
}
 

Functions

 XBT_LOG_NEW_DEFAULT_CATEGORY (msg_chord,"Messages specific for this msg example")
 
static void chord_exit (void)
 
static int normalize (int id)
 Turns an id into an equivalent id in [0, nb_keys). More...
 
static int is_in_interval (int id, int start, int end)
 Returns whether an id belongs to the interval [start, end]. More...
 
static void get_mailbox (int node_id, char *mailbox)
 Gets the mailbox name of a host given its chord id. More...
 
static void task_free (void *task)
 Frees the memory used by a task. More...
 
static void print_finger_table (node_t node)
 Displays the finger table of a node. More...
 
static void set_finger (node_t node, int finger_index, int id)
 Sets a finger of the current node. More...
 
static void set_predecessor (node_t node, int predecessor_id)
 Sets the predecessor of the current node. More...
 
static int node (int argc, char *argv[])
 Node Function Arguments: More...
 
static void handle_task (node_t node, msg_task_t task)
 This function is called when the current node receives a task. More...
 
static void create (node_t node)
 Initializes the current node as the first one of the system. More...
 
static int join (node_t node, int known_id)
 Makes the current node join the ring, knowing the id of a node already in the ring. More...
 
static void leave (node_t node)
 Makes the current node quit the system. More...
 
static int find_successor (node_t node, int id)
 Makes the current node find the successor node of an id. More...
 
static int remote_find_successor (node_t node, int ask_to, int id)
 Asks another node the successor node of an id. More...
 
static int remote_get_predecessor (node_t node, int ask_to)
 Asks another node its predecessor. More...
 
static int closest_preceding_node (node_t node, int id)
 Returns the closest preceding finger of an id with respect to the finger table of the current node. More...
 
static void stabilize (node_t node)
 This function is called periodically. More...
 
static void notify (node_t node, int predecessor_candidate_id)
 Notifies the current node that its predecessor may have changed. More...
 
static void remote_notify (node_t node, int notify_id, int predecessor_candidate_id)
 Notifies a remote node that its predecessor may have changed. More...
 
static void fix_fingers (node_t node)
 This function is called periodically. More...
 
static void check_predecessor (node_t node)
 This function is called periodically. More...
 
static void random_lookup (node_t node)
 Performs a find successor request to a random id. More...
 
static void quit_notify (node_t node)
 Notifies the successor and the predecessor of the current node of the departure. More...
 
static void chord_initialize (void)
 
int main (int argc, char *argv[])
 

Variables

static int nb_bits = 24
 
static int nb_keys = 0
 
static int timeout = 50
 
static int max_simulation_time = 1000
 
static int periodic_stabilize_delay = 20
 
static int periodic_fix_fingers_delay = 120
 
static int periodic_check_predecessor_delay = 120
 
static int periodic_lookup_delay = 10
 
static const double sleep_delay = 4.9999
 
static int * powers2
 
static xbt_dynar_t host_list
 

Macro Definition Documentation

#define COMM_SIZE   10
#define COMP_SIZE   0
#define MAILBOX_NAME_SIZE   10

Typedef Documentation

typedef struct s_finger s_finger_t
typedef struct s_finger * finger_t
typedef struct s_node s_node_t
typedef struct s_node * node_t
typedef struct s_task_data s_task_data_t
typedef struct s_task_data * task_data_t

Enumeration Type Documentation

Enumerator
TASK_FIND_SUCCESSOR 
TASK_FIND_SUCCESSOR_ANSWER 
TASK_GET_PREDECESSOR 
TASK_GET_PREDECESSOR_ANSWER 
TASK_NOTIFY 
TASK_SUCCESSOR_LEAVING 
TASK_PREDECESSOR_LEAVING 
TASK_PREDECESSOR_ALIVE 
TASK_PREDECESSOR_ALIVE_ANSWER 

Function Documentation

XBT_LOG_NEW_DEFAULT_CATEGORY ( msg_chord  ,
"Messages specific for this msg example"   
)
static void chord_exit ( void  )
static
static int normalize ( int  id)
static

Turns an id into an equivalent id in [0, nb_keys).

Parameters
idan id
Returns
the corresponding normalized id
static int is_in_interval ( int  id,
int  start,
int  end 
)
static

Returns whether an id belongs to the interval [start, end].

The parameters are noramlized 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]

Parameters
idid to check
startlower bound
endupper bound
Returns
a non-zero value if id in in [start, end]
static void get_mailbox ( int  node_id,
char *  mailbox 
)
static

Gets the mailbox name of a host given its chord id.

Parameters
node_idid of a node
mailboxpointer to where the mailbox name should be written (there must be enough space)
static void task_free ( void task)
static

Frees the memory used by a task.

Parameters
taskthe MSG task to destroy
static void print_finger_table ( node_t  node)
static

Displays the finger table of a node.

Parameters
nodea node
static void set_finger ( node_t  node,
int  finger_index,
int  id 
)
static

Sets a finger of the current node.

Parameters
nodethe current node
finger_indexindex of the finger to set (0 to nb_bits - 1)
idthe id to set for this finger
static void set_predecessor ( node_t  node,
int  predecessor_id 
)
static

Sets the predecessor of the current node.

Parameters
nodethe current node
idthe id to predecessor, or -1 to unset the predecessor
int node ( int  argc,
char *  argv[] 
)
static

Node Function Arguments:

  • my id
  • the id of a guy I know in the system (except for the first node)
  • the time to sleep before I join (except for the first node)
static void handle_task ( node_t  node,
msg_task_t  task 
)
static

This function is called when the current node receives a task.

Parameters
nodethe current node
taskthe task to handle (don't touch it then: it will be destroyed, reused or forwarded)
static void create ( node_t  node)
static

Initializes the current node as the first one of the system.

Parameters
nodethe current node
static int join ( node_t  node,
int  known_id 
)
static

Makes the current node join the ring, knowing the id of a node already in the ring.

Parameters
nodethe current node
known_idid of a node already in the ring
Returns
1 if the join operation succeeded, 0 otherwise
static void leave ( node_t  node)
static

Makes the current node quit the system.

Parameters
nodethe current node
static int find_successor ( node_t  node,
int  id 
)
static

Makes the current node find the successor node of an id.

Parameters
nodethe current node
idthe id to find
Returns
the id of the successor node, or -1 if the request failed
static int remote_find_successor ( node_t  node,
int  ask_to,
int  id 
)
static

Asks another node the successor node of an id.

Parameters
nodethe current node
ask_tothe node to ask to
idthe id to find
Returns
the id of the successor node, or -1 if the request failed
static int remote_get_predecessor ( node_t  node,
int  ask_to 
)
static

Asks another node its predecessor.

Parameters
nodethe current node
ask_tothe node to ask to
Returns
the id of its predecessor node, or -1 if the request failed (or if the node does not know its predecessor)
int closest_preceding_node ( node_t  node,
int  id 
)
static

Returns the closest preceding finger of an id with respect to the finger table of the current node.

Parameters
nodethe current node
idthe id to find
Returns
the closest preceding finger of that id
static void stabilize ( node_t  node)
static

This function is called periodically.

It checks the immediate successor of the current node.

Parameters
nodethe current node
static void notify ( node_t  node,
int  predecessor_candidate_id 
)
static

Notifies the current node that its predecessor may have changed.

Parameters
nodethe current node
candidate_idthe possible new predecessor
static void remote_notify ( node_t  node,
int  notify_id,
int  predecessor_candidate_id 
)
static

Notifies a remote node that its predecessor may have changed.

Parameters
nodethe current node
notify_idid of the node to notify
candidate_idthe possible new predecessor
static void fix_fingers ( node_t  node)
static

This function is called periodically.

It refreshes the finger table of the current node.

Parameters
nodethe current node
static void check_predecessor ( node_t  node)
static

This function is called periodically.

It checks whether the predecessor has failed

Parameters
nodethe current node
static void random_lookup ( node_t  node)
static

Performs a find successor request to a random id.

Parameters
nodethe current node
static void quit_notify ( node_t  node)
static

Notifies the successor and the predecessor of the current node of the departure.

Parameters
nodethe current node
static void chord_initialize ( void  )
static
int main ( int  argc,
char *  argv[] 
)

Variable Documentation

int nb_bits = 24
static
int nb_keys = 0
static
int timeout = 50
static
int max_simulation_time = 1000
static
int periodic_stabilize_delay = 20
static
int periodic_fix_fingers_delay = 120
static
int periodic_check_predecessor_delay = 120
static
int periodic_lookup_delay = 10
static
const double sleep_delay = 4.9999
static
int* powers2
static
xbt_dynar_t host_list
static