2022q1 Homework5 (quiz6)

contrubuted by <yaohwang99>

problem link

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;
}

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

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