# linux2021: [25077667](https://github.com/25077667/)
###### tags: `linux2021-quiz`
> [GitHub](https://github.com/25077667/)
:::info
我對不起納稅人
有在努力，可是沒有辦法盡全力
:::
## $\alpha$
```c=
v >> (bits - c);
v << (bits - c);
```
可是不能用 bits
改寫為：
```c=
v >> ((-c) & (sizeof(v) << 3) - 1);
v << ((-c) & (sizeof(v) << 3) - 1);
```
雖然這如果是我，我會直接用 `__builtin_rotate`
### 舉出 Linux 核心原始程式碼裡頭 bit rotation 的案例並說明
[Inlines rotl_64](https://github.com/torvalds/linux/commit/c4597c4426265667c225140ffc84032aae6d937e)
說明：
### 上述 C 程式碼經過編譯器最佳化 (例如使用 gcc) 後，能否運用到這二個指令()呢？
設計以下實驗：
```c=
#include <stdint.h>
#define __DECLARE_ROTATE(bits, type) \
static inline type rotl##bits(const type v, int c) \
{ \
const int mask = (bits) - (1); \
c &= mask; \
\
return (v << c) | ((-c) & (sizeof(v) << 3) - 1); \
} \
\
static inline type rotr##bits(const type v, int c) \
{ \
const int mask = (bits) - (1); \
c &= mask; \
\
return (v >> c) | ((-c) & (sizeof(v) << 3) - 1); \
}
#define DECLARE_ROTATE(bits) __DECLARE_ROTATE(bits, uint##bits##_t)
DECLARE_ROTATE(64);
DECLARE_ROTATE(32);
DECLARE_ROTATE(16);
DECLARE_ROTATE(8);
int main(int argc, char *argv[])
{
int a = argc;
return rotl64(a, 2);
}
```
指令：
> cc -S rotl.c -O1
輸出：
```asm=
.file "rotl.c"
.text
.globl main
.type main, @function
main:
.LFB8:
.cfi_startproc
movslq %edi, %rax
salq $2, %rax
orq $62, %rax
ret
.cfi_endproc
.LFE8:
.size main, .-main
.ident "GCC: (Debian 10.2.1-6) 10.2.1 20210110"
.section .note.GNU-stack,"",@progbits
```
然後嘗試 32 版本：
```asm=
leal 0(,%rdi,4), %eax
orl $30, %eax
```
即使修過編譯器(前端)、組合語言(雖然是ARM)，還是覺得很神奇。
> 可能我什麼也沒有學會吧。
## $\beta$
提交答案之後，發現計算錯誤了。
應該是：
```c=
(sz + mask) & ~mask;
```
### 說明上述程式碼的運作原理
### 在 Linux 核心原始程式碼找出類似 align_up 的程式碼，並舉例說明其用法
[tools/testing/selftests/vm/pkey-helpers.h](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/tools/testing/selftests/vm/pkey-helpers.h)
[Use case](https://github.com/torvalds/linux/blob/35e43538af8fd2cb39d58caca1134a87db173f75/tools/testing/selftests/vm/protection_keys.c#L735)
> 寫完上面，發現計算錯誤，才寫下面延伸討論。發現 Linux 的 test driver 就有答案zzzz
> 好吧，誠實面對自己，現在學會了（
稍微看一下，居然是 [Memory Protection Keys](https://www.kernel.org/doc/Documentation/core-api/protection-keys.rst)
> Memory Protection Keys provides a mechanism for enforcing **page-based** protections, but without requiring modification of the page tables when an application changes protection domains. It works by dedicating 4 previously ignored bits in each page table entry to a "protection key", giving 16 possible keys.
然後產生大 pkey 效能開消極大，所以考慮記憶體對齊特性，就變得相當重要
## $\gamma$
`fork` CoW，所以梯形公式
高度 12
## $\delta$
I tried, but it sounds not the correct answer:
```c=
/* Add element to queue. The client is responsible for freeing elementsput into
* the queue afterwards. Returns Q_OK on success or Q_ERROR on failure.
*/
int con_push(con_queue_t *restrict queue, void *restrict new_element)
{
/* Prepare new node */
node_t *node = _con_node_init(new_element);
if (!node)
return Q_ERROR;
/* Add to queue with lock */
mtx_lock(queue->first_mutex);
mtx_lock(queue->last_mutex);
if (queue->first == queue->last) { // AAA
queue->first = node;
mtx_unlock(queue->first_mutex);
node->next = queue->last;
} else {
mtx_unlock(queue->first_mutex);
node->next = queue->last->next;
queue->last->next = node;
}
queue->last = node;
mtx_unlock(queue->last_mutex);
return Q_OK;
}
/* Retrieve element and remove it from the queue.
* Returns a pointer to the element previously pushed in or NULL of the queue is
* emtpy.
*/
void *con_pop(con_queue_t *queue)
{
mtx_lock(queue->first_mutex);
node_t *node = queue->first; /* Node to be removed */
node_t *new_header = queue->first->next; /* become the first in the queue */
/* Queue is empty */
if (!new_header) {
mtx_unlock(queue->first_mutex);
return NULL;
}
/* Queue not empty: retrieve data and rewire */
void *return_value = node->value; // BBB
mtx_lock(queue->last_mutex); // CCC
if (queue->first == queue->last)
queue->first = queue->last = new_header; // all is dummy
else
queue->first = new_header;
mtx_unlock(queue->last_mutex);
mtx_unlock(queue->first_mutex);
/* Free removed node and return */
free(node);
return return_value;
}
#include <assert.h>
#include <stdio.h>
#define N_PUSH_THREADS 4
#define N_POP_THREADS 4
#define NUM 1000000
```
I considered if the `dummy` node is the last or first node of this `con_queue`.
It looks like the only one choise: the `dummy` is the last node.
However, if it is the last node. Why we need to protect it?
If we do not protect the last node, I tried to protect the "truely" last node which was pushed.
I protects the "truely" last node, so it needs a lock...
然後我也發現，我這寫法有一個 bug。
但是尚不清楚問題是從何導致？
### bug:
"有時候" 會 dummy 會 leak。（就只有 dummy）
而既然是"有時候"，我懷疑是 race condition 造成。
但是沒有找出是如何造成的。
## $\epsilon$
Just calculate it.
```c=
x + 1; // XXX
```
* YYY:
I have no idea now.
## $\zeta$
After study the man page and the resources:
[Zero copy](https://hackmd.io/@sysprog/linux2020-zerocopy)
[fast-web-server](https://hackmd.io/@sysprog/fast-web-server)
```c=
[1] = {.fd = target_fd, .events = POLLIN, .revents = POLLHUP},
[0] = {.fd = cl_fd, .events = POLLIN, .revents = POLLHUP},
```
It can work.
Sign in with Wallet
Connect another wallet