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_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

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

enum e_task_type_t

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

id

an 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

id	id to check
start	lower bound
end	upper 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_id	id of a node
mailbox	pointer 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

task	the MSG task to destroy

static void print_finger_table ( node_t  node )

static

Displays the finger table of a node.

Parameters

node

a node

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

static

Sets a finger of the current node.

Parameters

node	the current node
finger_index	index of the finger to set (0 to nb_bits - 1)
id	the 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

node	the current node
id	the 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

node	the current node
task	the 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

node	the 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

node	the current node
known_id	id 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

node	the current node

static int find_successor ( node_t  node, int  id  )

static

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

Parameters

node	the current node
id	the 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

node	the current node
ask_to	the node to ask to
id	the 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

node	the current node
ask_to	the 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

node	the current node
id	the 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

node	the current node

static void notify ( node_t  node, int  predecessor_candidate_id  )

static

Notifies the current node that its predecessor may have changed.

Parameters

node	the current node
candidate_id	the 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

node	the current node
notify_id	id of the node to notify
candidate_id	the 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

node	the current node

static void check_predecessor ( node_t  node )

static

This function is called periodically.

It checks whether the predecessor has failed

Parameters

node	the current node

static void random_lookup ( node_t  node )

static

Performs a find successor request to a random id.

Parameters

node	the current node

static void quit_notify ( node_t  node )

static

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

Parameters

node	the 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