# linux2021: ilkclord

> [quiz-link](https://hackmd.io/@sysprog/linux2021-summer-quiz)

## $\delta$ - 1
This program is a mpmc model , and the number of consumer and producer are set to be 4 .
The pop and push action are defined as
* `pop` : pop out the elements from the top of the linked list
* `push` : push an elements into the tail of the linked list

The program starts by
1 . Initialize the queue
2 . Creating the consumer and producer thread
3 . Start poping and pushing
4 . Send the kill signal to end the program
### Thread Safety
The program assures the safety of data by using a queue with two `mutex_lock`

typedef struct { /* Two lock queue */
    node_t *first, *last;
    mtx_t *first_mutex, *last_mutex;
} con_queue_t;

`first_mutex` : protect the `first`
`last_mutex` : protect the `last`

* **poping**
`con_pop` take use of `first` to do the pop action .It has to assure the `first` is only used by sigle thread at the same time , so it lock the block which needs to use `first`

    mtx_lock(queue->first_mutex);

    node_t *node = queue->first;             /* Node to be removed */
    node_t *new_header = queue->first->next; /* become the first in the queue */

    /* Queue is empty */
    if (!new_header) {
        mtx_unlock(queue->first_mutex);
        return NULL;
    }

    /* Queue not empty: retrieve data and rewire */
    void *return_value = node->value;
    queue->first = new_header;

    mtx_unlock(queue->first_mutex);

* **pushing**
`con_push` takes use of `last` to do the push , and it assures `last` in a similar way . To keep the safety , a `mutex_lock` is applied to lock the block that needs to use `last`.

    mtx_lock(queue->last_mutex);
    if(queue->last) queue->last->next = node ;
    queue->last = node;
    mtx_unlock(queue->last_mutex);

### Thread Funtion

#### push_thread

This thread push elements into the queue . The thread terminate when it has push the limited number of elments in .

int push_thread(void *queue_ptr)
{
    con_queue_t *queue = (con_queue_t *) queue_ptr;

    /* Push ints into queue */
    for (int i = 0; i < NUM; ++i) {
        int *pushed_value = malloc(sizeof(int));
        *pushed_value = i;
        if (con_push(queue, pushed_value) != Q_OK)
            printf("Error pushing element %i\n", i);
    }

    thrd_exit(0);
}

#### pop_thread
This thread keeps poping out the elements from the queue , and it also free the elements it popped out .The thread will terminate when it pops out the element with value -1 , which is a killed signal .

int pop_thread(void *queue_ptr)
{
    con_queue_t *queue = (con_queue_t *) queue_ptr;

    /* Read values from queue. Break loop on -1 */
    while (1) {
        int *popped_value = con_pop(queue);
        if (popped_value) {
            if (*popped_value == -1) {
                free(popped_value);
                break;
            }

            free(popped_value);
        }
    }

    thrd_exit(0);
}

### Flow Chart

* program

Digraph G{
    Initilaize->"create threads" ->pushing ->terminate ->"Send killing signal" ->End
    "create threads" ->popping->End


}

* queue

Digraph G{
    push->last
    first->"node1"->"node2"->"node3"->"..."-> last
    first->pop
    rankdir = LR

}

### Problem
After the testing , we find that thhere is possibility that the program will be stock in a loop , which is the while_loop in the `pop_thread` .

Browse the code , the problem may be in `cond_pop`

`cond_pop` :

void *con_pop(con_queue_t *queue)
{
    mtx_lock(queue->first_mutex);

    node_t *node = queue->first;             /* Node to be removed */
    node_t *new_header = queue->first->next; /* become the first in the queue */

    /* Queue is empty */
    if (!new_header) {
        mtx_unlock(queue->first_mutex);
        return NULL;
    }

    /* Queue not empty: retrieve data and rewire */
    void *return_value = node->value;
    queue->first = new_header;

    mtx_unlock(queue->first_mutex);

    /* Free removed node and return */
    free(node);
    return return_value;
}

In line 9 , the if gate block the empty queue , but it checks the `!new_header` instead of `!node` , this makes the queue will alwalys has at least 1 elements inside . For the last one data in the queue , it will never be popped out , so we can changed the the check condition to `!node` .

### Improvement
In line 9 , the if gate block the empty queue , but it checks the `!new_header` instead of `!node` , this makes the queue will alwalys has at least 1 elements inside .For the last one data in the queue , it will never be popped out .

I guess the reason for this design is to keep the connection between `first` and `last` .
#### Solution 1
Add one more condition to check if killing signal has received .

if (!new_header && *(int *)(node->value) != -1 ) {
        mtx_unlock(queue->first_mutex);
        return NULL;
}

#### Solution 2
We can changed the check condition to `!node` ,too .But there exists some bugs . I analyze the behavoirs of `first` and `last` .

Initialize of `last` and `first`

    node_t *dummy = _con_node_init(NULL);
    if (!dummy) {
        con_free(queue);
        return NULL;
    }

    queue->first = queue->last = dummy;

`first` and `last`points to a same node `dummy ` .In expected situation , `last` will grows the queue bigger and indicates the tail ,`first` pops out the elements and decrease the size of queue .

Consider the special case , the elements were all popped out ,so `first` and `last` points to `NULL` . This is a serious problem , since `first` and `last` no longer has connection between each other , the pop function can't pop the elements out .

Expected :

Digraph G{
first->list->last
rankdir = LR
}

Broken :

Digraph G{
first
list->last
rankdir = LR
}

I add the modificatoin below to reconnect `first` and `last` and assure the correctness .

* `con_push`
I use if_else to connect `first` and `last` when pushing into empty queue ,also assure the thread safety .

   if(queue->last != NULL) 
      queue->last->next = node ;//AAA
    else{
      mtx_lock(queue->first_mutex) ;
      queue->first = node ;
      mtx_unlock(queue->first_mutex) ;
    }

* `con_pop`
I switch the order below , to check the if `first` is `NULL` , and return `NULL` if statement is true .

    node_t *node = queue->first;             /* Node to be removed */
    if (!node) {
        mtx_unlock(queue->first_mutex);
        return NULL;
    }
    node_t *new_header = queue->first->next; /* become the first in the queue */

## $\delta$ - 2
To modify the program to a lock free program , I replace the `mutex_lock` by C11 atomic operation .
### C11 Atomic

The only two change is in `con_pop` and `con_push`

* `con_pop`

void *con_pop(con_queue_t *queue)
{

    node_t *node = atomic_load(&(queue->first)); 
    /*Empty queue*/
    if(!node->next && *(int *)(node->value)!= -1)
        return NULL ;

    
    /*test if the node we fetched isn't use by others
     * if isn't , modified it to next one
     * */
    if(!atomic_compare_exchange_strong(&(queue->first) , &node , node->next))
      return NULL ;

    
    void *return_value = node->value ;// BBB;
    /* Free removed node and return */
    free(node);
    return return_value;
}

We applied atomic operation by first fetching the value of `first` . Then we check if `first` has been modified before we record the `return_value` . If it has been modified , it is unsafe operation , we return `NULL`

* `con_push`

int con_push(con_queue_t *restrict queue, void *restrict new_element)
{
    /* Prepare new node */
    node_t *node = _con_node_init(new_element);
    if (!node)
        return Q_ERROR;
    
    while(1){
        node_t *tmp = atomic_load(&(queue->last)) ;
      
        if(atomic_compare_exchange_strong(&(queue->last) , &tmp , node)){
            atomic_store(&(tmp->next) , node) ;
            break ;
        }
    }
    return Q_OK;
}

We applied it in a similar way , but we let it try untill it successed . Because in the original `con_push` we return `Q_ERROR` only if the `malloc` failed , so we repeat this operation untill sucess .