# 2022q1 Homework3 (quiz4)
contributed by <`yaohwang99` >
> [quiz4](https://hackmd.io/@sysprog/linux2022-quiz4)

## Problem 1
$\lceil\log_2x\rceil$ = number of bits needed to store $x-1$, for example, $\log_28=3,\ 8-1=7=111_2$, $\lceil\log_29\rceil=4, \ 9-1=8=1000_2$
Therefore, `ceil_log2(uint32_t x)` is find last set for `x-1`.
1. Decrease x by 1.
2. Check if any of the 16 more significant bits are set, if so, increase r by 16 and shift x right 16.
3. Repeat step 2 for 8, 4, 2 bits.

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;
    x--;
    r = (x > 0xFFFF) << 4;
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (EXP1) + 1;       
}

After line 14, x has 2 bit left, we also need to update `r`. With the same approach, The code after line 14 is

    r |= shift;
    shift = (x > 0x1) << 0;
    x >>= shift;
    r |= shift;
    return r;

The above code can be reduced to `return (EXP1) + 1`, where ==EXP 1 is `r | shift | x >> 1`==.

---

## Problem 2
Similar to Problem 1, the following code uses `t` as mask and check if any of the `shift` less significant bit are set. If none, increase the return value `o` by `shift`.
==EXP2: `x & t`==
==EXP3: `o |= shift`==

#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)

#include <stddef.h>

static inline size_t ffs(unsigned long x)
{
    if (x == 0)
        return 0;

    size_t o = 1;
    unsigned long t = ~0UL;
    size_t shift = BITS_PER_LONG;

    shift >>= 1;
    t >>= shift;

    while (shift) {
        if ((EXP2) == 0) {
            x >>= shift;
            EXP3;
        }

        shift >>= 1;
        t >>= shift;
    }

    return o;
}

---

## Problem 3

struct foo_consumer {
    int (*handler)(struct foo_consumer *self, void *);
    struct foo_consumer *next;
};

struct foo {
    struct foo_consumer *consumers;
    unsigned long flags;
};

#include <stdbool.h>

/*
 * For foo @foo, delete the consumer @fc.
 * Return true if the @fc is deleted sfccessfully
 * or return false.
 */
static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
    struct foo_consumer **con;
    bool ret = false;

    for (con = &foo->consumers; *con; EXP4) {
        if (*con == fc) {
            *con = EXP5;
            ret = true;
            break;
        }
    }

    return ret;
}

At the start of `for` at line 23, `con` points to `foo->consumers`

digraph {
    compound = true
    rankdir = LR
    subgraph cluster0{
        label = "struct foo"
        style = filled
        color = gray90
        node0[label = "<consumers>consumers|flag" shape = record]
    }
    subgraph cluster1{
        label = "struct foo_consumer"
        style = filled
        color = gray90
        node1[label = "handler|<next>next" shape = record]
    }
    subgraph cluster2{
        label = "struct foo_consumer"
        style = filled
        color = gray90
        node2[label = "handler|<next>next" shape = record]
    }
    subgraph cluster3{
        label = "struct foo_consumer"
        style = filled
        color = gray90
        node3[label = "handler|<next>next" shape = record]
    }
    con[shape = plaintext]
    fc[shape = plaintext]
    con->node0:consumers
    fc->node2[lhead = cluster2]
    node0:consumers->node1[lhead = cluster1]
    node1:next->node2[lhead = cluster2]
    node2:next->node3[lhead = cluster3]
}

Then `con` traverse through the list untill `*con == fc`, therefore, ==EXP4 is `con = &(*con)->next`==.

digraph {
    compound = true
    rankdir = LR
    subgraph cluster0{
        label = "struct foo"
        style = filled
        color = gray90
        node0[label = "<consumers>consumers|flag" shape = record]
    }
    subgraph cluster1{
        label = "struct foo_consumer"
        style = filled
        color = gray90
        node1[label = "handler|<next>next" shape = record]
    }
    subgraph cluster2{
        label = "struct foo_consumer"
        style = filled
        color = gray90
        node2[label = "handler|<next>next" shape = record]
    }
    subgraph cluster3{
        label = "struct foo_consumer"
        style = filled
        color = gray90
        node3[label = "handler|<next>next" shape = record]
    }
    con[shape = plaintext]
    fc[shape = plaintext]
    con->node1:next[color = red]
    fc->node2[lhead = cluster2]
    node0:consumers->node1[lhead = cluster1]
    node1:next->node2[lhead = cluster2]
    node2:next->node3[lhead = cluster3]
}

Then remove `fc` from the list, ==EXP3: fc->next==

digraph {
    compound = true
    rankdir = LR
    subgraph cluster0{
        label = "foo"
        style = filled
        color = gray90
        node0[label = "<consumers>consumers|flag" shape = record]
    }
    subgraph cluster1{
        label = "foo_consumer"
        style = filled
        color = gray90
        node1[label = "handler|<next>next" shape = record]
    }
    subgraph cluster2{
        label = "foo_consumer"
        style = filled
        color = gray90
        node2[label = "handler|<next>next" shape = record]
    }
    subgraph cluster3{
        label = "foo_consumer"
        style = filled
        color = gray90
        node3[label = "handler|<next>next" shape = record]
    }
    con[shape = plaintext]
    fc[shape = plaintext]
    con->node1:next
    fc->node2[lhead = cluster2]
    node0:consumers->node1[lhead = cluster1]
    node1:next->node3[lhead = cluster3 color = red]
    node2:next->node3[lhead = cluster3]
}

## Problem 4
The structure stores the `env` value. `tasks` is function designator

struct task {
    jmp_buf env;
    struct list_head list;
};

static LIST_HEAD(tasklist);
static void (**tasks)(void *);
static int ntasks;
static jmp_buf sched;

digraph {
    compound = true
    rankdir = LR
    subgraph cluster0{
        label = "tasklist"
        style = filled
        color = gray90
        node0[shape = record label="<next>next|<prev>prev"]
    }
    subgraph cluster1{
        label = "task"
        style = filled
        color = gray90
        node1[shape = record label="env|<list>list"]
    }
    subgraph cluster2{
        label = "task"
        style = filled
        color = gray90
        node2[shape = record label="env|<list>list"]
    }
    subgraph cluster3{
        label = "task"
        style = filled
        color = gray90
        node3[shape = record label="env|<list>list"]
    }

    node0->node1:list[dir = both]
    node1:list->node2:list[dir = both]
    node2:list->node3:list[dir = both]
    node3:list->node0:prev[dir = both]
    
}

`task_add` inserts a new tast from tail and `task_switch` removes the first task in the list. Therefore, ==EXP6 is `list_del(&t->list)`==.
`task_join` goes through each task in the list and complete them, so ==EXP7 is `list_del(&t->list)`==.

static void task_add(struct list_head *tasklist, jmp_buf env)
{
    struct task *t = malloc(sizeof(*t));
    memcpy(t->env, env, sizeof(jmp_buf));
    INIT_LIST_HEAD(&t->list);
    list_add_tail(&t->list, tasklist);
}

static void task_switch(struct list_head *tasklist)
{
    jmp_buf env;

    if (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        EXP6;
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

static void task_join(struct list_head *tasklist)
{
    jmp_buf env;

    while (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        EXP7;
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

`longjmp(sched, 1)` will jump to `setjump(sched)` in `schedule`.

void schedule(void)
{
    static int i;

    srand(0xCAFEBABE ^ (uintptr_t) &schedule); /* Thanks to ASLR */

    setjmp(sched);

    while (ntasks-- > 0) {
        int n = rand() % 5;
        tasks[i++](&n);
        printf("Never reached\n");
    }

    task_join(&tasklist);
}

For each tast, the program prints `n` then add itself to `tasklist` then do EXP8.

/* A task yields control n times */

void task0(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 0: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        EXP8;
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: resume\n");
    }

    printf("Task 0: complete\n");
    longjmp(sched, 1);
}

From the output, we can see that the program jumps back to `schedule()` after n is printed, so ==EXP8 and EXP9 is `longjmp(sched, 1)`==

Task 0: n = 3
Task 1: n = 3
Task 0: resume
Task 1: resume
Task 0: resume
Task 0: complete
Task 1: resume
Task 1: complete

---

## Problem 5

#include <stdint.h>
#include <string.h>                       
#include <stdlib.h>

#define __READ_ONCE_SIZE                                  \
    ({                                                    \
        switch (size) {                                   \
        case 1:                                           \
            *(uint8_t *) res = *(volatile uint8_t *) p;   \
            break;                                        \
        case 2:                                           \
            *(uint16_t *) res = *(volatile uint16_t *) p; \
            break;                                        \
        case 4:                                           \
            *(uint32_t *) res = *(volatile uint32_t *) p; \
            break;                                        \
        case 8:                                           \
            *(uint64_t *) res = *(volatile uint64_t *) p; \
            break;                                        \
        default:                                          \
            memcpy((void *) res, (const void *) p, size); \
        }                                                 \
    })

static inline void __read_once_size(const volatile void *p, void *res, int size)
{
    __READ_ONCE_SIZE;
}

Here, we would like to implement READ_ONCE using the above macro.
The parameter `res` corresponds to the argument `__u.__c`.
The intuitve answer is let DECL0 be `void *__c`, however, case 1 (line 8) of the above macro indicates that we need `*res` to be 1 byte.
Therefore, ==DECL0 is `char __c[1]`==, where `__c` is a pointer to 1 byte memory.

#define READ_ONCE(x)                                \
    ({                                              \
        union {                                     \
            typeof(x) __val;                        \
            DECL0;                            \
        } __u;                                      \
        __read_once_size(&(x), __u.__c, sizeof(x)); \
        __u.__val;                                  \
    })