libuthread: A C repository from RyanMa1

Phase 1: Queue API
- To implement the queue, we decided to use a doubly linked list. This was to
  maintain the O(1) requirement for most operations. Using a linked list
  allowed for O(1) enqueueing and dequeueing that could be difficult with
  other data structures, and it matched the specifications perfectly.
  The queue structure contained a pointer to its first and last nodes as well
  as an int to track its length. The nodes of the queue contained a pointer
  to a thread (TCB) member as well as pointers to their next and previous
  nodes.
```
typedef struct node_t {
	void *value;
  struct node_t *next;
	struct node_t *prev;
} node_t;

struct queue {
	node_t *first;
	node_t *last;
    int length;
};
```
- To handle queue_create(), memory was simply allocated for the queue and if
  allocation failed, NULL was returned. Otherwise, the queue's nodes were
  initialized to NULL and its length to 0.
- For enqueue(), cases in which the queue or data were NULL, malloc erred, the
  queue was empty, or the queue contained one or more nodes were accounted
  for. Most of the queue implementation involved basic pointer manipulations
  such as the following.
```
	newNode->value = data;
    ...
    } else {
		// one or more items in queue
    	newNode->next = NULL;
	  newNode->prev = queue->last;
	    queue->last->next = newNode;
    	queue->last = newNode;
	}
	queue->length++;
    return 0;
}
```
- In order to satisfy the condition of queue_length being O(1) in time
  complexity, queue length was simply incremented every time a node was
  enqueued and returned in the queue_length() function.
- In the case of queue_delete(), the possibilities of the queue or data being
  NULL, the queue being empty, the data not being found, and the queue having
  contents to be deleted were handled. It compares the pointer addresses and
  deletes the appropriate node once the match is found.
- For queue_destroy(), a simple check was made to determine whether the queue
  was not NULL or had a length of 0. If that held true, the queue was freed.
- To take care of queue_iterate(), it was first determined whether the queue
  or function were NULL. If not, a pointer to the first node of the queue was
  instantiated to serve as the iterator through the queue. The iterator goes
  through each node, calling the function specified, and, depending on the
  return value of that function, receives the data or not.
- The implementation of queue_dequeue() was very similar to that of
  queue_enqueue(). However, the use of a double pointer allowed us to save
  the address to data.
- To test the queue, we created a test_queue.c file. This manipulated nodes
  in the queue. Each node consisted of two ints and two char pointers. Each
  queue function was tested using either assert statements, strcmp, or prints
  to stderr as shown below. Queue_iterate() was tested using the given code
  under the "Hints" heading of the project2.html page.
```
assert(queue_destroy(NULL) == -1);
assert(queue_enqueue(NULL, NULL) == -1);
myData data1 = {1, 2, "Sevilla", "Bayern"};
  myData data2 = {0, 3, "Juventus", "Real Madrid"};
...
queue_t testq = queue_create();
void *data = NULL;
assert(queue_dequeue(testq, &data) == -1); //must return -1 (empty)
assert(queue_enqueue(testq, match1) == 0); // must return 0 (success)
...
  if (strcmp(ret->homeTeam, "Juventus") || strcmp(ret->awayTeam, "Real Madrid")) {
	fprintf(stderr, "%s\n", "Incorrect item dequeued");
  ...
}
...
int len = queue_length(testq);
if (len != 6) {
	fprintf(stderr, "%s", "Incorrect queue length");
  ...
}
```
Phase 2: Uthread API
- To implement the TCB structure, we used six variables to keep track of the
  TID, context, stack pointer, state, return value, and the TID of the thread to
  be joined. The state was an integer with 0, 1, 2, and 3 signifying Running,
  Ready, Zombie, and Blocked states respectively.
```
typedef struct {
	uthread_t tid;
  uthread_ctx_t *context;
	void *stackPtr;
  int state; // 0-Running, 1-Ready, 2-Zombie, 3-Blocked
 	int ret; // return value
	int joinThd; // TID of the thread to be joined by (-1 if none)
} TCB;
```
- For ease of use in the subsequent functions specified, global variables the
  queue, TID, and a pointer to the current thread were declared. We also created
  a few utility functions as well. The function uthread_self() uses the global
  variable to easily identify the current thread's thread ID. The functions
  find_ready() and find_TCB() took advantage of the unique queue iteration
  mechanism we implemented in the first phase. When used with
  queue_iterate(), they will help locate the TCB based on a thread ID and the
  TCB of the first ready thread, respectively.
```
/* Global variables */
static queue_t queue = NULL;
static uthread_t TID = 1; // defined in uthread.h
static TCB *curr_TCB = NULL; // Ptr to current thread TCB
...
/* Find a TCB with state 1-Ready */
int find_ready(void *data, void *arg) {
	TCB *ptr = (TCB*)data;
  if (ptr->state == 1)
  	return 1;
	return 0;
}
```
- The uthread_create() function is in charge of creating a new thread using the
  context API and enqueuing it as a ready thread. The context API simplifies
  the task considerably. We initialize the variables and allocate space for
  the stack and the context. The actual initialization of the execution
  context of the thread is also done by the context API. The following code
  snippet shows this process.
```
  //Create a user thread
TCB *newThd = malloc(sizeof(TCB));
newThd->tid = TID;
newThd->state = 1; 
newThd->joinThd = -1; // no thread to join to at the moment

newThd->context = malloc(sizeof(uthread_ctx_t));
newThd->stackPtr = uthread_ctx_alloc_stack();
if (uthread_ctx_init(newThd->context, newThd->stackPtr, func, arg) != 0)
  	return -1;

queue_enqueue(queue, newThd);
TID++; // TID for next thread
```
- In uthread_create(), when the queue is empty, our library recognizes that
  it is the first library call from the user. Therefore, we use a separate
  function initialize() to initalize the queue, the "main" thread, and the
  first user thread. This process is similar to a typical thread creation
  process described in uthread_create(). However, it is noteworthy that the
  "main" thread does not have to be initialized since it already has a stack.
  The preemption process, which we will describe in detail in Phase 4, also
  begins at the end of this function.
- For uthread_exit(), the running thread's state is changed to Zombie, its
  return value is collected, and queue_delete() is called to remove the
  thread from the queue. Its resources, however, are not freed here because
  they may be collected by the thread it is joining to. At the end of the
  function, we make sure to unblock the thread it is planning to join to, if
  present. (This part is implemented in Phase 3).
- In the function uthread_yield(), the current thread becomes ready unless it
  is blocked. This ensures that an unblocking of a thread can only be done
  when the child thread's execution exits. If the queue only contains one
  element ("main" thread) or if there is no more ready thread, we are done.
  Otherwise, we repeatedly enqueue and dequeue until we find the first ready
  thread. Once found, its state is switched to running and is placed at the
  end of the queue. We change the global variable for the current TCB
  accordingly and switch the context using a context API function.
- We used the given files to test this phase.

Phase 3: uthread_join()

The uthread_join() function was created with the child joining the calling
parent. It was first determined if the main thread could not be joined, if
the TID was the same as the calling thread's, if the TID could not be found
using queue_iterate(), and if the child was already being joined.

  TCB *child_thd = NULL;
  TCB *parent_thd = curr_TCB; // <=> calling thread
  uthread_t *childtid = &tid;

  // prelimiary checks & find child_thd based on tid
  if (tid == 0)
  	return -1; // main thread cannot be joined
  if (tid == uthread_self())
    	return -1; // tid is same as calling thd
  if (queue_iterate(queue, find_TCB, (void*)childtid, (void**)&child_thd) == 0) {
  	if (!child_thd)
  		return -1; // if tid cannot be found
  }
  if (child_thd->joinThd != -1)
  	return -1;  // if child is already being joined

Then, if the child was Ready or Running, the parent was blocked until the
child died. If the child was dead, then its return value was collected and
it was freed.

  while(1) {
  	if (child_thd->state == 0 || child_thd->state == 1) {
		// If child is active, block parent until child dies
  		parent_thd->state = 3; // block 
  		child_thd->joinThd = uthread_self();
		uthread_yield();

	} else if (child_thd->state == 2) {
		// Child now dead. Now collect and free
  		if (child_thd->ret)
  			*retval = child_thd->ret;
  		free(child_thd); 
  		break;
	}
  }

For testing, we created test_phase3.c. In this file, thread1 waits on
thread2 to terminate and collect its return value using uthread_join().

int thread2(void* arg) {
	sleep(3);
	printf("thread 2 execution: returning value 5\n");
	return 5;
}

int thread1(void* arg) {
	uthread_t tid;
	int retval;
	tid = uthread_create(thread2, NULL);
	uthread_join(tid, &retval);
	printf("thread 1 execution: waited and obtained return value %d from thread2\n", retval);
	return 0;
}
int main(void) {
	uthread_t tid;
	tid = uthread_create(thread1, NULL);
	uthread_join(tid, NULL);
	return 0;
}

Phase 4: Preemption
- The forth phase mainly involved standard implementations of timed alarms and
  their handler. The function setitimer() sets an emission of the signal
  SIGVTALRM a hundred times per second. The function sigaction() handles
  these signals by calling a handler that simply calls uthread_yield(). The
  functions preempt_{enable,disable} are also simple implementations of
  signal blocking, following the GNU manual. This mechanism ensures that no
  one thread will hoard all resources and prevent other threads from
  executing.
- Preemption begins at the end of the function initialize(), which sets up the
  "main" thread and the first user thread. To prevent preemption from causing
  inconsistent program behaviors, we strictly disabled it in the yield process
  and the exit process. On the other hand, by inserting the function
  preempt_enable() in the bootstrap function, we made sure that preemption is
  active during the execution of threads.
- We wrote a simple program called test_preempt.c to test this phase. Without
  preemption, this programs gets stuck in thread1's infinite loop, and thread2
  and thread3 are never executed. However, with preemption, although the
  program eventually gets trapped in the infinite loops, all two print
  statements from thread2 and thread3 are executed. This proves that threads
  are regularly being forced to yield due to our implementation of preemption.
```
int thread3(void* arg) {
	printf("thread3 execution\n");
	return 0;
 }
 int thread2(void* arg) {
	printf("thread2 pause starting..\n");
	while(1);
  	return 0;
 }
 int thread1(void* arg) {
	uthread_create(thread2, NULL);
	uthread_create(thread3, NULL);
	while(1);
  	return 0;
 }
 int main(void) {
	uthread_t tid;
	tid = uthread_create(thread1, NULL);
    uthread_join(tid, NULL);
  return 0;
 }
 ```
```

RyanMa1/libuthread

Phase 1: Queue API

Phase 2: Uthread API

Phase 3: uthread_join()

Phase 4: Preemption

Sources: