# 2022-04-04 yaohwang99
## Problem 1
1. Traverse the first few unaligned bytes (the address is not multiple of `LBLOCKSIZE`), return target if found.
```c
while (UNALIGNED(src)) {
if (!length--)
return NULL;
if (*src == d)
return (void *) src;
src++;
}
```
2. Treverse each block with a block size of `LBLOCKSIZE`, `break` if target is in the current block.
```c
while (length >= LBLOCKSIZE) {
/* XXXXX: Your implementation should appear here */
if (DETECT_CHAR(*asrc, mask)){
break;
}
asrc++;
length -= LBLOCKSIZE;
}
}
```
3. Iterate through each byte in the current block or the remaining bytes and return the target.
```c
while (length--) {
if (*src == d)
return (void *) src;
src++;
}
```
## Problem 2
From [What do each memory order mean?](https://stackoverflow.com/questions/12346487/what-do-each-memory-order-mean)
>acquire - no loads can be reordered wrt. the atomic load. I.e. if they are after the atomic load in the source code, they will happen after the atomic load too.
>
>release - no stores can be reordered wrt. the atomic store. I.e. if they are before the atomic store in the source code, they will happen before the atomic store too.
I believe that ==DDD is `idx++`==.
The purpose of `cond_reload` is to update local variable to the correct `tail` when idx is more than 1 loop behind.
If `idx` is not before `fresh`, then that means the`cond_reload` should not be called (I believe it is a fool-proof design) and we just try the next slot as usual.
```c
static inline ringidx_t cond_reload(ringidx_t idx, const ringidx_t *loc)
{
ringidx_t fresh = __atomic_load_n(loc, __ATOMIC_RELAXED);
if (before(idx, fresh)) { /* fresh is after idx, use this instead */
idx = fresh;
} else { /* Continue with next slot */
/* XXXXX */ DDD;
}
return idx;
}
```
==TTT is `&lfr->tail, __ATOMIC_ACQUIRE`== because we would like to update the local variable `tail` and we need the operation after the atomic load in the source code happen after the atomic load.
```c
static inline ringidx_t find_tail(lfring_t *lfr, ringidx_t head, ringidx_t tail)
{
if (lfr->flags & LFRING_FLAG_SP) /* single-producer enqueue */
return __atomic_load_n(&lfr->tail, __ATOMIC_ACQUIRE);
/* Multi-producer enqueue.
* Scan ring for new elements that have been written but not released.
*/
ringidx_t mask = lfr->mask;
ringidx_t size = /* XXXXX */ KKK;
while (before(tail, head + size) &&
__atomic_load_n(/* XXXXX */ TTT) ==
tail)
tail++;
tail = cond_update(&lfr->tail, tail);
return tail;
}
```
From [reference link](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html)
>Built-in Function: bool __atomic_compare_exchange_n (type *ptr, type *expected, type desired, bool weak, int success_memorder, int failure_memorder)
This built-in function implements an atomic compare and exchange operation. This compares the contents of *ptr with the contents of *expected. If equal, the operation is a read-modify-write operation that writes desired into *ptr. If they are not equal, the operation is a read and the current contents of *ptr are written into *expected. weak is true for weak compare_exchange, which may fail spuriously, and false for the strong variation, which never fails spuriously. Many targets only offer the strong variation and ignore the parameter. When in doubt, use the strong variation.
If desired is written into *ptr then true is returned and memory is affected according to the memory order specified by success_memorder. There are no restrictions on what memory order can be used here.
Otherwise, false is returned and memory is affected according to failure_memorder. This memory order cannot be __ATOMIC_RELEASE nor __ATOMIC_ACQ_REL. It also cannot be a stronger order than that specified by success_memorder.
`__atomic_compare_exchange_n` writes `HHH` into `lft->head `if `lfr->head == head`.
Therefore ==HHH is `head + actual`==.
```c
uint32_t lfring_dequeue(lfring_t *lfr,
void **restrict elems,
uint32_t n_elems,
uint32_t *index)
{
ringidx_t mask = lfr->mask;
intptr_t actual;
ringidx_t head = __atomic_load_n(&lfr->head, __ATOMIC_RELAXED);
ringidx_t tail = __atomic_load_n(&lfr->tail, __ATOMIC_ACQUIRE);
do { /* skipped */
} while (!__atomic_compare_exchange_n(
&lfr->head, &head, /* Updated on failure */
/* XXXXX */ HHH,
/* weak */ false, __ATOMIC_RELAXED, __ATOMIC_RELAXED));
*index = (uint32_t) head;
return (uint32_t) actual;
}
```
## Problem 3
[workqueue.h](https://github.com/torvalds/linux/blob/master/include/linux/workqueue.h) shows that function `f` will be linked with `delayed_work n`.
```c
#define __WORK_INITIALIZER(n, f) { \
.data = WORK_DATA_STATIC_INIT(), \
.entry = { &(n).entry, &(n).entry }, \
.func = (f), \
__WORK_INIT_LOCKDEP_MAP(#n, &(n)) \
}
#define __DELAYED_WORK_INITIALIZER(n, f, tflags) { \
.work = __WORK_INITIALIZER((n).work, (f)), \
.timer = __TIMER_INITIALIZER(delayed_work_timer_fn,\
(tflags) | TIMER_IRQSAFE), \
}
#define DECLARE_WORK(n, f) \
struct work_struct n = __WORK_INITIALIZER(n, f)
#define DECLARE_DELAYED_WORK(n, f) \
struct delayed_work n = __DELAYED_WORK_INITIALIZER(n, f, 0)
```
```c
static DECLARE_DELAYED_WORK(dont_trace_task, periodic_routine);
```
`dont_trace_task` is linked with `periodic_routine`, so `periodic_routine` will be scheduled and executed by CFS(Complety Fair Scheduler) after it is enqueued by `queue_delayed_work(wq, &dont_trace_task, JIFFIES_DELAY)`
To make the function continue to be scheduled, we enqueue again at the end of the function.
```c
static void periodic_routine(struct work_struct *ws)
{
if (likely(loaded))
check();
queue_delayed_work(wq, &dont_trace_task, JIFFIES_DELAY);
}
```
The global variable `loaded` is set to true and false at `dont_trace_exit` and `dont_trace_init` to avoid potential error.
```c
static int __init dont_trace_init(void)
{
wq = create_workqueue(DONT_TRACE_WQ_NAME);
queue_delayed_work(wq, &dont_trace_task, JIFFIES_DELAY);
loaded = true;
pr_info("Loaded!\n");
return 0;
}
```
```c
static void __exit dont_trace_exit(void)
{
loaded = false;
/* No new routines will be queued */
cancel_delayed_work(&dont_trace_task);
/* Wait for the completion of all routines */
flush_workqueue(wq);
destroy_workqueue(wq);
pr_info("Unloaded.\n");
}
```
Sign in with Wallet
Connect another wallet