# 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.
```c=
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
```c
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`==
```c
#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
```c=
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`
```graphviz
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`==.
```graphviz
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==
```graphviz
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
```c
struct task {
jmp_buf env;
struct list_head list;
};
static LIST_HEAD(tasklist);
static void (**tasks)(void *);
static int ntasks;
static jmp_buf sched;
```
```graphviz
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)`==.
```c
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`.
```c
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.
```c
/* 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
```c
#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.
```c
#define READ_ONCE(x) \
({ \
union { \
typeof(x) __val; \
DECL0; \
} __u; \
__read_once_size(&(x), __u.__c, sizeof(x)); \
__u.__val; \
})
```
Sign in with Wallet
Connect another wallet