2022q1 Homework3 (quiz4)

contributed by <yaohwang99 >

quiz4

Problem 1

$\lceil {\log }_{2}x\rceil$ = number of bits needed to store

$x-1$, for example,

${\log }_{2}8=3,8-1=7={111}_2$,

$\lceil {\log }_{2}9\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

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

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

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;

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;                                  \
    })