2021-04-06 RZHuangJeff

tags: linux2021

Problem 1

static void run(char *c, int t)
{
    char *redir_stdin = NULL, *redir_stdout = NULL;
    int pipefds[2] = {0, 0}, outfd = 0;
    char *v[99] = {0};
    char **u = &v[98]; /* end of words */
    for (;;) {
        c--;
        if (is_delim(*c)) /* if NULL (start of string) or pipe: break */
            break;
        if (!is_special(*c)) {
            c++;    /* Copy word of regular chars into previous u */
            *c = 0; /* Terminate current token */
            while (!is_special(*--c)) /* Find the begining of token */
                ;
            *--u = c + 1; /* Add found token to arguments list */
        }
        if (is_redir(*c)) { /* If < or > */
            if (*c == '<')
                redir_stdin = *u;
            else
                redir_stdout = *u;
            if ((u - v) != 98)
                u++;
        }
    }

---

Problem 2

static void dequeue(queue_t *q, int *fd)
{
    node_t *old_head;
    pthread_mutex_lock(q->head_lock);
    /* Since there is a dummy node at the begining of queue,
     * we are acturally looking for node next to it.
     */
    node_t *dummy = q->head;
    
    /* Wait until signaled that queue is non_empty.
     * Need while loop in case a new thread manages to steal the queue
     * element after the waiting thread is signaled, but before it can
     * re-acquire head_lock.
     */
    while (!dummy->next)
        pthread_cond_wait(q->non_empty, q->head_lock);
    
    /* Pop the node next to dummy node, and update the next
     * of dummy node by the node next to popped one.
     */
    old_head = dummy->next;
    dummy->next = old_head->next;
    
    /* Locking on tail_lock is performed since we have to
     * modify size properly, which is updated in both
     * enqueue and dequeue.
     */
    pthread_mutex_lock(q->tail_lock);
    q->size--;
    
    /* Special case of popping, the tail of queue should be
     * set to dummy once the queue becomes empty.
     */
    if (q->tail == old_head)
        q->tail = dummy;
    pthread_mutex_unlock(q->tail_lock);

    /* Copy the file descripor stored in popped node to *fd. */
    *fd = old_head->fd;
        
    pthread_mutex_unlock(q->head_lock);
    free(old_head);
}

1. The purpose of greeter_routine is to accept incoming connections, accepted connections will be queued until a worker_routine, which aims to deal with the requests, is avaliable.
2. Since there are different locks protect enqueueing and dequeueing from data racing, we do not need to worry about several enqueueing/dequeueing overlaps with each other. The only situation we have to concern is overlapping between enqueueing and dequeueing. With requiring tail_lock while dequeueing, the fields that are modified both in enqueueing and dequeueing (size and tail) is protected in critical section.

Did you consider to add the statement q->size--?
jserv

---

Problem 3

#define ALIGN_FLOOR(val, align) \
    ((val / align + ((val % align) != 0)) * align)

static inline int ringbuffer_sp_do_enqueue(ringbuf_t *r,
                                           void *const *obj_table,
                                           const unsigned n)
{
    uint32_t mask = r->prod.mask;
    uint32_t prod_head = r->prod.head, cons_tail = r->cons.tail;
    /* The subtraction is done between two unsigned 32-bits value (the result
     * is always modulo 32 bits even if we have prod_head > cons_tail). So
     * @free_entries is always between 0 and size(ring) - 1.
     */
    uint32_t free_entries = mask + cons_tail - prod_head;

    /* check that we have enough room in ring */
    if ((n > free_entries))
        return -ENOBUFS;

    uint32_t prod_next = prod_head + n;
    r->prod.head = prod_next;

    /* write entries in ring */
    ENQUEUE_PTRS();
    __compiler_barrier();

    r->prod.tail = prod_next;

    /* if we exceed the watermark */
    if (cons_tail - prod_next > r->prod.watermark)
        return -EDQUOT;
        
    return 0;
}

2. To expend the implementation of ring buffer to fit SPMC and MPMC, we have to introduce atomic operations to make sure that every modification to the buffer is expected. The most important thing is to keep the range between different producers or different consumers is not overlapped, this is where the atomic operations take place. Before a producer or a consumer modifies or reads from the buffer, they have to update the index (prod_head and cons_head) first, by atomic_compare_exchange. Once they mark their working place successfully, they can modfiy and read from such place without worrying other producers or consumers.

The macro #define ALIGN_FLOOR(val, align) ((val / align + ((val % align) != 0)) * align) was not elegant. Improve it.
jserv

---

Problem 4

static bool execute_client_callback(bus_client_t *client, void *msg)
{
    /* Load the client with which we are attempting to communicate. */
    bus_client_t local_client;
    __atomic_load(client, &local_client, __ATOMIC_SEQ_CST);

    /* Loop until reference count isupdated or client becomes unregistered */
    while (local_client.registered) {
        /* The expected reference count is the current one + 1 */
        bus_client_t new_client = local_client;
        ++(new_client.refcnt);

        /* If CAS succeeds, the client had the expected reference count, and
         * we updated it successfully. If CAS fails, the client was updated
         * recently. The actual value is copied to local_client.
         */
        if (CAS(client, &local_client, &new_client)) {
            /* The callback function registered is invoked here. */
            new_client.callback(new_client.ctx, msg);
        
            /* Decreace the reference count client. */
            while (!CAS(client, &new_client, &local_client))
                ;
            return true;
        }
    }

    /* Client was not registered or got unregistered while we attempted to send
     * a message
     */
    return false;
}

1. With designing callback function in this way, the reciever no needs to poll waiting for certain conditions happend, since once a condition happends, the sender thread will deal with that condition with in its context.
2. To reduce affects between different callback functions, a thread pool with several workers could be launched at very beginning. Workers will be locked on specific processors by processor affinity and aims to deal with executing callback functions. Once a message is sent via message bus, the corresponding callback function of reciever is queued for an avaliable worker.