#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include "libwfg.h"
#include "queue.h"
Functions | |
void | wfg_init (wfg_t *wfg) |
Initializes the wait-for graph data structure. | |
int | wfg_add_wait_edge (wfg_t *wfg, pthread_t t_id, unsigned int r_id) |
Adds a "wait" edge to the wait-for graph. | |
int | wfg_add_hold_edge (wfg_t *wfg, pthread_t t_id, unsigned int r_id) |
Replaces a "wait" edge with a "hold" edge on a wait-for graph. | |
int | wfg_remove_edge (wfg_t *wfg, pthread_t t_id, unsigned int r_id) |
Removes an edge on the wait-for graph. | |
int | wfg_get_cycle (wfg_t *wfg, pthread_t **cycle) |
Returns the numebr of threads and the identifiers of each thread that is contained in a cycle on the wait-for graph. | |
void | wfg_print_graph (wfg_t *wfg) |
Prints all wait-for relations between threads in the wait-for graph. | |
void | wfg_destroy (wfg_t *wfg) |
Destroys the wait-for graph data structure. |
int wfg_add_hold_edge | ( | wfg_t * | wfg, | |
pthread_t | t_id, | |||
unsigned int | r_id | |||
) |
Replaces a "wait" edge with a "hold" edge on a wait-for graph.
This function replaces an edge directed from a thread to a resource (a "wait" edge) with an edge directed from the resource to the thread (a "hold" edge). If the thread does not contain a directed edge to the resource when this function is called, this function should fail. This function should also fail if the resource is already "held" by another thread.
wfg | The wait-for graph data structure. | |
t_id | A unique identifier to a thread. A caller to this function may want to use the thread ID used by the system, by using the pthread_self() function. | |
r_id | A unique identifier to a resource. |
int wfg_add_wait_edge | ( | wfg_t * | wfg, | |
pthread_t | t_id, | |||
unsigned int | r_id | |||
) |
Adds a "wait" edge to the wait-for graph.
This function adds a directed edge from a thread to a resource in the wait-for graph. If the thread is already waiting on any resource (including the resource) requested, this function should fail.
wfg | The wait-for graph data structure. | |
t_id | A unique identifier to a thread. A caller to this function may want to use the thread ID used by the system, by using the pthread_self() function. | |
r_id | A unique identifier to a resource. |
void wfg_destroy | ( | wfg_t * | wfg | ) |
Destroys the wait-for graph data structure.
This function must always be called last, after all other libwfg functions.
wfg | The wait-for graph data structure. |
int wfg_get_cycle | ( | wfg_t * | wfg, | |
pthread_t ** | cycle | |||
) |
Returns the numebr of threads and the identifiers of each thread that is contained in a cycle on the wait-for graph.
If the wait-for graph contains a cycle, this function allocates an array of unsigned ints equal to the size of the cycle, populates the array with the thread identifiers of the threads in the cycle, modifies the value of cycle
to point to this newly created array, and returns the length of the array.
For example, if a cycle exists such that: t(id=1) => r(id=100) => t(id=2) => r(id=101) => t(id=1) (cycle)
...the array will be of length two and contain the elements: [1, 2].
This function only returns a single cycle and may return the same cycle each time the function is called until the cycle has been removed. This function can return ANY cycle, but it must contain only threads in the cycle itself.
It is up to the user of this library to free the memory allocated by this function.
If no cycle exists, this function must not allocate any memory and will return 0.
wfg | The wait-for graph data structure. | |
cycle | A pointer to an (unsigned int *), used by the function to return the cycle in the wait-for graph if a cycle exists. |
void wfg_init | ( | wfg_t * | wfg | ) |
Initializes the wait-for graph data structure.
This function must always be called first, before any other libwfg functions.
wfg | The wait-for graph data structure. |
void wfg_print_graph | ( | wfg_t * | wfg | ) |
Prints all wait-for relations between threads in the wait-for graph.
In a wait-for graph, a thread is "waiting for" another thread if a thread has a "wait" edge on a resource that is being "held" by another process. This function prints all of the edges to stdout in a comma- seperated list in the following format: [thread]=>[thread], [thread]=>[thread]
If t(id=1) and t(id=2) are both waiting for r(id=100), but (r=100) is held by t(id=3), the printout should be: 1=>3, 2=>3
When printing out the wait-for relations:
wfg | The wait-for graph data structure. |
int wfg_remove_edge | ( | wfg_t * | wfg, | |
pthread_t | t_id, | |||
unsigned int | r_id | |||
) |
Removes an edge on the wait-for graph.
If any edge exists between the thread and resource, this function removes that edge (either a "hold" edge or a "wait" edge).
wfg | The wait-for graph data structure. | |
t_id | A unique identifier to a thread. A caller to this function may want to use the thread ID used by the system, by using the pthread_self() function. | |
r_id | A unique identifier to a resource. |