# 2022q1 Homework5 (quiz6) contrubuted by <`yaohwang99`> > [problem link](https://hackmd.io/@sysprog/linux2022-quiz6) ## Problem 1 ### Spin lock ```c typedef struct { volatile int lock; unsigned int locker; } spin_t; ``` Set `lock` and `locker` to `0` ```c 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`. ```c 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 ``` --- ```c 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). ```c= 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 ```c= /** * @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 ```c #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 ```c 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. ```c= 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
Last changed by  
 
yaohwang99
222

Read more

[ESCA](https://eecheng87.github.io/ESCA/)

Tasks [x] Support Nginx v1.22.0 Benchmark tool: wrk wrk is an open source benchmark tool for http servers. eventLoop->apidata->epfd Each thread handles thread->connections number of connections, which is equal to cfg.connections / cfg.threads. thread->cs contains an array of connections with size of thread->connections, which contains a connected fd and other relevant information. Each thread contains one aeEventLoop with a setsize of 10 + cfg.connections * 3.

6/20/2022
2022q1 Homework6 (ktcp)

contributed by < yaohwang99 > homework description User level echo server Use socket(), bind() listen() to create socket and link to server address. accept() will block the process until connected to some client. Set the socket to non-blocking.

5/8/2022
2022q1 Homework5 (quiz8)

contributed by < yaohwang99 > Problem 2 typedef uintptr_t ringidx_t; struct element { void *ptr; uintptr_t idx; };

4/24/2022
2022q1 Homework5 (quiz5)

contributed by <yaohwang99> Problem link Problem 2 A successful call to pthread_create() stores the ID of the new thread in the buffer pointed to by readers + i, return 0 and starts execution by invoking reader_thread int main() { pthread_t readers[N_READERS], writers[N_WRITERS];

4/14/2022
Read more from yaohwang99
Published on HackMD