---
# System prepended metadata

title: 'linux2021: [25077667](https://github.com/25077667/)'
tags: [linux2021-quiz]

---

# 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.

![](https://i.imgur.com/OdZfp9s.png)
