# 2022q1 Homework5 (quiz6)
contrubuted by <`yaohwang99`>
> [problem link](https://hackmd.io/@sysprog/linux2022-quiz6)
## Problem 1
### Spin lock

typedef struct {
    volatile int lock;
    unsigned int locker;
} spin_t;

Set `lock` and `locker` to `0`

int spin_init(spin_t *l)
{
    volatile int out;
    volatile int *lck = &(l->lock);
    asm("movl $0x0,(%1);" : "=r"(out) : "r"(lck));
    l->locker = 0;
    return 0;
}

---
If `lock` is `0`, swap the value of `lock` with the address of itself, then return.
If `lock` is not `0`, then the value is the address of itself, swap with the address of itself until the value is changed by other thread calling `spin_release` to set `lck` to `0`.

int spin_acquire(spin_t *l)
{
    int out;
    volatile int *lck = &(l->lock);
    asm("whileloop:"
        "xchg %%al, (%1);"
        "test %%al,%%al;"
        "jne whileloop;"
        : "=r"(out)
        : "r"(lck));
    return 0;
}

The instuction `xchg` swaps `%al` with `(%rax)`, which means swap the last byte of `%rax` with `*lck`. where `%rax` stores the value of `lck`.

spin_acquire:
        pushq   %rbp
        movq    %rsp, %rbp
        movq    %rdi, -24(%rbp)
        movq    -24(%rbp), %rax
        movq    %rax, -8(%rbp)
        movq    -8(%rbp), %rax
whileloop:xchg %al, (%rax);test %al,%al;jne whileloop;
        movl    %eax, -12(%rbp)
        movl    $0, %eax
        popq    %rbp
        ret

---

static inline int spin_release(spin_t *l)
{
    int out;
    volatile int *lck = &(l->lock);
    asm("movl $0x0,(%1);" : "=r"(out) : "r"(lck));
    l->locker = 0;
    return 0;
}

:::warning
By my understanding, the lock works by swaping tha least significant byte of it's address, which is not 0x00.

I also don't understand why `locker` exists.
:::

---

### Mutex lock
Mutex lock is almost the same as spin lock except that it uses system call and [futex](https://man7.org/linux/man-pages/man2/futex.2.html) to sleep (line 12) until `FUTEX_WAKE` (line 28).

static __attribute__((noinline)) int mutex_acquire(mutex_t *m)
{
    volatile int out;
    volatile int *lck = &(m->lock);
    asm("mutexloop:"
        "mov $1, %%eax;"
        "xchg %%al, (%%rdi);"
        "test %%al,%%al;"
        "je end"
        : "=r"(out)
        : "r"(lck));
    syscall(SYS_futex, m, FUTEX_WAIT, 1, NULL, NULL, 0);
    asm("jmp mutexloop");
    asm("end:");
    return 0;
}

/**
 * @brief Release the lock object atomically and wake up waiting threads
 * @param lock Mutex Lock object
 */
static inline int mutex_release(mutex_t *m)
{
    volatile int out;
    volatile int *lck = &(m->lock);
    asm("movl $0x0,(%1);" : "=r"(out) : "r"(lck));
    m->locker = 0;
    syscall(SYS_futex, m, FUTEX_WAKE, 1, NULL, NULL, 0);
    return 0;
}

---

### Create thread

/**
 * @brief Create a One One mapped thread
 * @param t Reference to the thread
 * @param routine Function associated with the thread
 * @param arg Arguments to the routine
 */
int thread_create(thread_t *t, void *routine, void *arg)
{
    spin_acquire(&global_lock);
    static bool init_state = false;
    if (!t || !routine) {
        spin_release(&global_lock);
        return EINVAL;
    }
    if (!init_state) {
        init_state = true;
        init();
    }

    node_t *node = list_insert(&tid_list, 0);
    if (!node) {
        printf("Thread address not found\n");
        spin_release(&global_lock);
        return -1;
    }

    funcargs_t *fa = malloc(sizeof(funcargs_t));
    if (!fa) {
        printf("Malloc failed\n");
        spin_release(&global_lock);
        return -1;
    }

    fa->f = routine;
    fa->arg = arg;
    void *thread_stack = alloc_stack(STACK_SZ, GUARD_SZ);
    if (!thread_stack) {
        perror("thread create");
        spin_release(&global_lock);
        free(fa);
        return errno;
    }
    fa->stack = thread_stack;
    thread_t tid = clone(wrap, (char *) thread_stack + STACK_SZ + GUARD_SZ,
                         CLONE_FLAGS, fa, &(EXP1), NULL, &(EXP2));
    node->tid_copy = tid;
    node->fa = fa;

    if (tid == -1) {
        perror("thread create");
        free(thread_stack);
        spin_release(&global_lock);
        return errno;
    }
    *t = tid;
    spin_release(&global_lock);
    return 0;
}

At line17, `init()` will only be called by the first cloned thread because `static` variables will ony be initialized once.
### clone flag

#define CLONE_FLAGS                                                     \
    (CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD | \
     CLONE_SYSVSEM | CLONE_PARENT_SETTID | CLONE_CHILD_CLEARTID)

CLONE_VM: the calling process and the child process run in the same memory space.
CLONE_FS: the caller and the child process share the same filesystem information.
CLONE_FILES: the calling process and the child process share the same file descriptor table.
CLONE_SIGHAND: the calling process and the child process share the same table of signal handlers.
CLONE_THREAD: the child is placed in the same thread group as the calling process.
CLONE_SYSVSEM: the child and the calling process share a single list of System V semaphore adjustment (semadj) values (see semop(2)).

CLONE_CHILD_CLEARTID: Clear (zero) the child thread ID at the location pointed to by child_tid (clone()) or cl_args.child_tid (clone3()) in child memory when the child exits, and do a wakeup on the futex at that address. The address involved may be changed by the set_tid_address(2) system call. This is used by threading libraries.

CLONE_PARENT_SETTID: Store the child thread ID at the location pointed to by parent_tid (clone()) or cl_args.parent_tid (clone3()) in the parent's memory.

thread_create $\to$ wrap $\to$ routine

thread_t tid = clone(wrap, (char *) thread_stack + STACK_SZ + GUARD_SZ,
                         CLONE_FLAGS, fa, &(node->tid), NULL, &(node->tid));
    node->tid_copy = tid;

The above function will create a new thread with a new tid, where `tid`, `node->tid`, and `node->tid_copy` has the same value.
:::danger
Because the flag include `CLONE_CHILD_CLEARTID` and `CLONE_PARENT_SETTID`, the function should clear `node->tid` to 0 and set `node->tid` to `tid `and return `tid`.
:::

---
When there are multiple reader entering the critical section, `rwlock` is acquired by the first reader and released by the last reader, preventing dead lock.

static void f1(void)
{
    mutex_acquire(&lock);
    if (++n_readers == 1)
        mutex_acquire(&rwlock);
    mutex_release(&lock);
    safe_printf(&print_lock, "Reader process in\n");
    atomic_fetch_add(&n_readers_in, 1);
    mutex_acquire(&lock);
    if (--n_readers == 0)
        mutex_release(&rwlock);
    mutex_release(&lock);

    atomic_fetch_sub(&n_readers_in, 1);
    safe_printf(&print_lock, "Reader process out\n");
}

## Problem 2
KKKK: &prev->next
QQQQ: &map->bucket[]
ZZZZ: &prev->next