# 2022q1 Homework5 (quiz5)
contributed by < [cantfindagoodname](https://github.com/cantfindagoodname) >
> [題目](https://hackmd.io/@sysprog/linux2022-quiz5)
## 測驗 1
### `generate_sieve()`
A bitmap is generate by the function `generate_sieve()` which prototype is :
```c
static void generate_sieve(int digits);
```
:::warning
`generate_sieve()` is not a deterministic function, in which the function has side effect that mutates a non-local variable (namely `psieve`) that is the bitmap that should be generated.
In my opinion, this is a (convenient but) bad practice as the side effect is no apparent without looking into the actual implementation of the function.
:::
The result of `generate_sieve()` is as followed :
:::info
```shell
$ lscpu | grep "Byte Order"
Byte Order: Little Endian
```
Note that the code is ran with Little Endian Byte Order.
:::
```shell
(gdb) # breakpoint set after generate_sieve(N_DIGITS) call
(gdb) x/4t psieve
0x7ffff7be6010: 10010001 00110100 01001011 10011011
```
From the first 32-bit value of `psieve`, we get a bit sequence
```text
10011011 01001011 00110100 10010001
```
Counting from the least significant bit, bit `1,2,3,5,6,8,9,11,14,15,18,20,21,23,26,29,30` is unset
From the documentation (in form of comments), we know that `psieve` is a bitmap in which bit `n` represents the odd number `2n+1`.
We then get the sequence `3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61` by applying $f(n)\rightarrow2n+1$, which is the first 18 prime number discluding 2.
:::spoiler Implementation of `generate_sieve()`
```c
static void generate_sieve(int digits)
{
ull max = 0;
for (int count = 0; count < digits; ++count)
max = max * 10 + 9;
max = isqrt(max);
half_max = max >> 1;
/* We need half the space as multiples of 2 can be omitted */
int bytes = (max >> 1) + (max & 0x1);
/* Calculate the actual number of bytes required */
bytes = (bytes >> 3) + (bytes & 0x1);
bytes = ALIGN(bytes, 16); /* Align-up to 16-byte */
psieve = realloc(psieve, bytes);
if (!psieve) {
printf("realloc() failed!\n");
exit(1);
}
memset(psieve, 0, bytes);
/* In psieve bit 0 -> 1, 1 -> 3, 2 -> 5, 3 -> 7 and so on... */
/* Set the 0th bit representing 1 to COMPOSITE
*/
psieve[0] |= COMPOSITE << (1 >> 1);
unsigned char mask = 0x7;
for (ull n = 3; n <= max; n += 2) {
if (((psieve[n >> 4] >> ((n >> 1) & mask)) & 0x1) == PRIME) {
for (ull mul = (n << 1); mul < max; mul += n) {
/* Skip the evens: there is no representation in psieve */
if (!(mul & 0x1))
continue;
/* Set offset of mul in psieve */
psieve[mul >> 4] |= COMPOSITE
<< ((mul >> 1) & mask); /* bit offset */
}
}
}
}
```
:::
The [implementation](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) is pretty straight forward.
As by definition a prime number must have only 2 factors (1 and itself), the algorithm marks numbers that have the prime number as factor as composite.
i.e. $\{c = np, \textrm{p is prime number},n \in \mathbb{W^+}\}$
The algorithm picks only $p$ that are less than $\sqrt{\textrm{MAX}}$, if $p > \sqrt{\textrm{MAX}}$, multiple of $p$ must have been marked as composite.
Let $c$ be a composite number, $c = ab$, $a$ and $b$ is prime, $n$ is the maximum number
$(a > \sqrt{n})\ \vee \ (b > \sqrt{n}) \rightarrow ab > n \Rightarrow c > n$
Hence, $a > \sqrt{n} \rightarrow b <\sqrt{n}$,
$c$ would be marked as composite by $b$ when the algorithm iterates to $a$
The actual assignment to `psieve` only marks the bits as composite, with few twists,
1. Even numbers are skipped
Any `x >> 1`, `x << 1` are the result of this.
2. `*psieve` is a byte which holds 8 numbers,
Any `psieve[x >> 4]`, `x & mask` are the result of this.
3. The result are represented as bitmap
`x & 0x1` is used to represent a bit.
### `is_prime()`
:::spoiler Implementation
```c
static bool isprime(const ull val)
{
if (!(val & 0x1)) /* Test for divisibility by 2 */
return false;
ull *pquadbits = (ull *) psieve;
ull next = 3; /* start at 7 (i.e. 3 * 2 + 1) */
for (ull quad = ~*pquadbits & ~0b111, prev = 0; prev <= half_max;
quad = ~*++pquadbits) {
if (!quad) {
prev += 64;
continue;
}
while (quad) {
ull i = __builtin_ctzll(quad);
next = prev + i;
if (!(val % ((next << 1) + 1)))
return false;
quad &= ~(1ULL << i);
}
prev += 64;
}
return true;
}
```
:::
## 測驗 2
Thread memory
```c
/* in main */
pthread_create(&tp, NULL, foo, NULL);
pthread_join(tp, NULL);
```
Look at system call for pthread creation.
```shell
$ gcc thread_create.c && strace ./a.out
$ # ...
$ clone
clone(child_stack=0x7ffff7d96fb0, flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, parent_tid=[25694], tls=0x7ffff7d97700, child_tidptr=0x7ffff7d979d0) = 25694
```
```shell
$ man 2 clone
```
> The stack for the child process is specified via cl_args.stack, which points to the lowest byte of the stack area, and cl_args.stack_size, which specifies the size of the stack in bytes. In the case where the CLONE_VM flag (see below) is specified, a stack must be explicitly allocated and specified. Otherwise, these two fields can be specified as NULL and 0, which causes the child to use the same stack area as the parent (in the child's own virtual address space).
> CLONE_VM (since Linux 2.0)
>
> If CLONE_VM is set, the calling process and the child process run in the same memory space. In particular, memory writes performed by the calling process or by the child process are also visible in the other process.
Thread created in the program shares their memory space bar stack segment (unless specified). `.BSS` (static / global variable) is shared among the threads.
`shared_config` and `config_dom` are shared among the threads
### Sol
`EXP4` : `list_remove(&dom->retired, ptr)`
`EXP5` : `list_remove(&dom->retired, ptr)`
### What the program does
The program would create threads to call `reader_thread` and `writer_thread`.
`writer_thread` will writes new value to the shared memory `shared_config`,
`reader_thread` will loads the value of `shared_config`.
Example result ( `N_READERS`, `NWRITERS` = 1 / `N_ITERS` = 5 ) :
```shell
read config : { 0x00000000, 0x00000000, 0x00000000 }
read config : { 0x00000000, 0x00000000, 0x00000000 }
read config : { 0x00000000, 0x00000000, 0x00000000 }
read config : { 0x00000000, 0x00000000, 0x00000000 }
read config : { 0x00000000, 0x00000000, 0x00000000 }
updating config : { 0x1aef5a3c, 0x5d7f376e, 0x5192f1dd }
updated config : { 0x1aef5a3c, 0x5d7f376e, 0x5192f1dd }
updating config : { 0x3631917a, 0x6a8090a3, 0x2f3ea8c9 }
updated config : { 0x3631917a, 0x6a8090a3, 0x2f3ea8c9 }
```
To make sure read config is working properly, place `reader` after `writer`,
Example result ( `N_READERS`, `NWRITERS` = 1 / `N_ITERS` = 5 ) :
```shell
updating config : { 0x6b8b4567, 0x327b23c6, 0x643c9869 }
updated config : { 0x6b8b4567, 0x327b23c6, 0x643c9869 }
updating config : { 0x66334873, 0x74b0dc51, 0x19495cff }
updated config : { 0x66334873, 0x74b0dc51, 0x19495cff }
read config : { 0x66334873, 0x74b0dc51, 0x19495cff }
read config : { 0x66334873, 0x74b0dc51, 0x19495cff }
read config : { 0x66334873, 0x74b0dc51, 0x19495cff }
read config : { 0x66334873, 0x74b0dc51, 0x19495cff }
read config : { 0x66334873, 0x74b0dc51, 0x19495cff }
```
### Structure of program
There are three user-defined types in the program.
`config_t` : a structure that encapsulates 3 unsigned integer, it makes the process of passing arguments / assigning value cleaner.
`domain_t` : a structure that contains 2 lists and a deallocator (to free `config_t` in the structure), the graphical representation is of the list are as shown below
When `reader` reads `config_t`, it insert a `uintptr_t` object into the hazard pointer list. (`load`)
When `reader` successfully reads `config_t`, it then remove the `uintptr_t` from the hazard pointer list. (`drop`)
`drop` has a gcc builtin `__builtin_unreachable`, where tell the compiler the code is infact, unreachable.
The programmer declares `list_remove()` never return false for `drop`.
```c
bool list_remove(hp_t **head, uintptr_t ptr)
{
hp_t *node;
const uintptr_t nullptr = 0;
LIST_ITER (head, node) {
uintptr_t expected = atomic_load(&node->ptr);
if (expected == ptr && atomic_cas(&node->ptr, &expected, &nullptr))
return true;
}
return false;
}
```
`list_remove()` would only return `false` if `LIST_ITER` doesn't find `ptr` in list `*head`, which is the hazard pointer list when called in `drop`.
There are only one possible scenario for this case.
Which is, `ptr` isn't in the list.
- `drop` is called right after `load`, from the comment, `safe_val` must have come from `load`.
- If a `writer` tries to overwrite the `safe_config`, as the pointer is still in the hazard pointer list, `cleanup_ptr` will either defer the deallocation and put the pointer into retired list, or spin until the reader are done (and hence, `ptr` must still be in the hazard pointer list, as `drop` has yet to called in this assumption).
When `writer` writes to `config_t`, it writes a random value to a local `config_t` buffer, then it update the `shared_config` by calling `swap`.
`swap` will deallocate the old `config_t` pointer right away if the pointer is not in the hazard pointer list (that is, not referenced by any readerthat is, not referenced by any reader).
If the pointer is in the hazard pointer list, `swap` will either spin until it is no longer in the list, or defer the deallocation by placing the pointer into the retire list.
If `swap` is called when another thread is calling `read`, the lockless pattern compare-and-swap in `load` will remove the hazard pointer (that failed loading value) then try to load again, Adding a new node to the hazard pointer list. And thus, eliminating the use-after-free scenario for reader_thread.
### Data Race
When there are multiple writers, Thread Sanitizer will gives a warning about data race.
The data race is caused by use-after-free in the writer thread.
```c
/* clean up in swap, writer is not protected by hazard pointer */
swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config, 0);
/* use after free (by other thread) */
print_config("updated config ", new_config);
```
In my opinion, this is more a design error than an implementation error.
One way to resolve data race is to use the existing hazard pointer API to protect the read of `new_config` which is equivalent to `shared_config` after `swap`
```c
list_insert_or_append(&config_dom->pointers, (uintptr_t) new_config);
swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
0);
print_config("updated config ", new_config);
list_remove(&config_dom->pointers, (uintptr_t) new_config);
if (list_contains(&config_dom->retired, (uintptr_t) new_config))
list_remove(&config_dom->retired, (uintptr_t) new_config);
```
However, I feel like this solution is not ideal for some reason :
```c
if (list_contains(&config_dom->retired, (uintptr_t) new_config))
list_remove(&config_dom->retired, (uintptr_t) new_config);
```
We would check if cancellation of `new_config` is deffered, this defeats the purpose of using `flag` to set mode.
Ideally (in my opinion), the code above to collect retire list should be replaced by the collector `cleanup` which are invoked periodically by interrupt (with `SIGALRM` or something similar).
```c
list_insert_or_append(&config_dom->pointers, (uintptr_t) new_config);
swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
0);
```
`new_config` would be placed into the hazard pointer list, which means `swap` will certainly be stopped by the list.
This would cause serious performance issue (espiacially when spinning) for writer to write data into the shared memory. And again, I feel like this is more a design issue than implementation issue of the program.
Sign in with Wallet
Connect another wallet