# 2022q1 Homework4 (quiz4)
contributed by < [cantfindagoodname](https://github.com/cantfindagoodname) >
> [題目](https://hackmd.io/@sysprog/linux2022-quiz4)
Note :
// TODO - all `test 1 - 5` should be implemented in scheduler of Linux kernel, find them out
## 測驗 1
```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 (r | shift | x >> 1) + 1;
}
```
`EXP1` : `r | shift | (x > 1)` would be more suitable as the answer as it correspond to the earlier segment of code, however, the test restrict the use of parenthesis `(` and `)`, hence `>>` is used instead of `>`, as only the two most least significant bit of `x` would be set at `EXP1`.
We wish to find `ceil` of `log2`,
i.e. All value after power of 2 would round up, until it reaches the next power of 2
e.g. `lg 2 = 1`, `lg 3 = 1.58 => 2`
In other words, value before power of 2 would be same
Hence, the program would subtract by 1 at the start of the function.
`0b1000 - 1 = 0b0111`, base-2 log ( bits of information ) would be same until `0b0100`
When returning, add by 1 as it needs to round up.
As in how the base-2 logarithmetic is done, check [quiz3](https://hackmd.io/@cantfindagoodname/linux2022-quiz3#%E6%B8%AC%E9%A9%977)
### 延伸問題
There are no problem in `x = 0`, as `lg 0 = -inf (NaN)`.
The return value is `int` so it should represent the largest possible number returned by the function.
Where the problem lies though, is in `lg 1`, as `lg 1 = 0`, the result should not round up to 1.
However, as the return value would be `EXP1` + 1, and `EXP1` is of `uint32_t` type, the minimum value of the return value is `1`, hence `0` is not representable.
One solution is simply not add 1 when `x` is initially `1`
```c
return (r | shift | (x > 1)) + !!(t - 1); /* t is initial value of x */
```
---
## 測驗 2
```c
unsigned long t = ~0UL;
size_t shift = BITS_PER_LONG;
shift >>= 1;
t >>= shift;
```
`~0UL` would set a variable which length are long.
`shift >>= 1` would reduce the value by half, which it originally is `BITS_PER_LONG`, which means it is very likely that half of the unsigned long integer would be accessed.
`t` is unsigned, hence `t >> n` would logically shift right.
From this alone, we can deduce that `t` is bitmask, and `shift` is used to divides the value assessed by half, and the goal is to do binary split, then evaluate top and bottom half of value.
```c
while (shift) {
if ((x & t) == 0) {
x >>= shift;
o += shift;
}
shift >>= 1;
t >>= shift;
}
```
We know that `t` is bitmask, and `o` is return value, so they could be used as followed
`x & t`, `o += shift`, similar application to `o += shift` could be found in [quiz3](https://hackmd.io/@cantfindagoodname/linux2022-quiz3#%E6%B8%AC%E9%A9%977), where `ret += v` is done every time they are splitted.
`if ((x & t) == 0)` would check if the lower half has set bits, if not, `ffs` must be at the top half, hence the lower half of `x` is discarded, and `o += shift` indicates it is at current top half.
Then the program would narrow the mask to check again.
## 測驗 3
```c
static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
struct foo_consumer **con;
bool ret = false;
for (con = &foo->consumers; *con; con = &(*con)->next) {
if (*con == fc) {
*con = (*con)->next;
ret = true;
break;
}
}
return ret;
}
```
The for loop would iterate through each nodes of the list, similar to `foreach`
`con` is a pointer to pointer of a node, It just has to reach the next node, and does not need to know what the node actually is. I'd like to see `con` as "pointer to edge" of the list
After `EXP4`, `EXP4` : `&(*con)->next`
After `EXP5`, `EXP5` : `(*con)->next`
:::warning
:warning: Use Graphviz to represent the nodes rather than still images.
:notes: jserv
:::
### 延伸問題
#### 區分 foo 和 foo_consumer 的好處
```c
struct foo_consumer {
int (*handler)(struct foo_consumer *self, void *);
struct foo_consumer *next;
};
struct foo {
struct foo_consumer *consumers;
unsigned long flags;
};
```
The node list and structure are encapsulate seperately.
1. We can extend easily
```c
struct bar {
struct foo_consumer *consumers1;
struct foo_consumer *consumers2;
struct foo_consumer *consumers3;
unsigned long flags;
};
```
2. We can store metadata for the whole structure and nodes seperately
It would be waste of time / space and the code would be less readable when everything is stuffed into a single structure.
e.g.
```c
typedef struct __meta_t meta_t;
struct foo_consumer {
int (*handler)(struct foo_consumer *self, void *);
void (*op)(struct foo_consumer *self);
meta_t *metadata;
meta_t getmeta();
struct foo_consumer *next;
};
struct foo {
void (*destructor)(void *);
struct foo_consumer *getList(unsigned);
unsigned list_cnt;
unsigned flags;
unsigned *consumer_cnt;
struct foo_consumer *consumers[0];
};
```
3. We can also extend the program to do operations on the list or the whole data structure itself.
---
## 測驗 4
The program stores the current context to the data structure `struct task` (linked list, used as LIFO stack)
Then the program alternate between the tasks in the function pointer `registered_task[]` (assigned to `tasks`) with `setjmp`, `longjmp`
> The functions described on this page are used for performing "nonlocal gotos": transferring execution from one function to a predetermined location in another function. The setjmp() function dynamically establishes the target to which control will later be transferred, and longjmp() performs the transfer of execution.
`schedule()` will call `taskN()`, which would push its context into the `struct task` list, then it would go back to `schedule()` with `longjmp()`.
`EXP8` : `longjmp(sched,1)`
`EXP9` : `longjmp(sched,1)`
After all tasks are pushed into the `struct task` list, `task_join` is called to initiate `task_switch`
`task_join` is used to initiate `task_switch` and they both would switch to the first task ("top" of `struct task`), they will "pop" the task from the list,
`EXP6` : `list_del(&t->list)`
`EXP7` : `list_del(&t->list)`
There was a error in the program though, the program don't switches as much as the output shows. (Each switches would print `Task N:resume`)
```shell
Task 0: n = 2
Task 1: n = 3
Task 0: resume
Task 1: resume
Task 0: resume
Task 0: complete
Task 1: resume
Task 1: complete
$ # 2 + 3 = 5 but there are only 4 `resume`
```
When a automatic variable (function-local, non-static) that is not `volatile` is modified, said variable has undefined value.
> [Source](http://gcc.gnu.org/onlinedocs/gccint/Interface.html)
> If you use longjmp, beware of automatic variables. ISO C says that automatic variables that are not declared volatile have undefined values after a longjmp. And this is all GCC promises to do, because it is very difficult to restore register variables correctly, and one of GCC’s features is that it can put variables in registers without your asking it to.
I designed a experiment to check how `setjmp` works
```c
#include <stdio.h>
#include <setjmp.h>
static jmp_buf ctx, foo_ctx;
static int lock = 1;
void foo()
{
int i = 0;
setjmp(foo_ctx);
i = 99999;
if (!lock){
longjmp(ctx, 1);
}
}
void bar()
{
for (int i = 0;i < 50;++i) {
setjmp(ctx);
printf("%d\n", i);
if (lock-- > 0) {
longjmp(foo_ctx, 1);
}
}
}
int main()
{
foo();
bar();
return 0;
}
```
Output:
```shell
0
99999
```
One solution is to make the variable `i` in for loop of `taskN` global or non-static.
## 延伸問題
Segmentation Fault when applying optimizer flag
Sign in with Wallet
Connect another wallet