Yitao's Blog

Memory Order浅析（以LevelDB中的跳表为例）零、引言最近一直在看LevelDB， 里面的跳表的实现在某种意义上是LockFree的，利用CAS实现了更高效*以及高并发的内存数据结构。 具体的分析暂且不表，本文的目的在于解决一直没想明白的std::memory_order。当然也不仅限于c++中的概念，应该在别的语言也有类似的不同隔离程度的内存屏障原语。通过本文可以： 1. 了解多线程中的一致性模型 2. 加深对于内存一致性模型的理解，以及平时该咋用 3：最后会通过LevelDB中的Skiplist的实例来分析为啥代码这么写 一、理论部分一些简单的名词概念（狗都不看部分）放在开头单纯方便下文中有不懂的地方可以Look Up Program Order（程序次序） 对于单个线程上操作，对同一个对象，先写后读，如果其中没有别的写，则读必定能读到该次写入 这个定义看上去很trival，但是考虑到现代的CPU的乱序执行和编译器可能进行的指令重排，这一点其实对于程序的执行的正确性是最大的保证 Sequential Consistence(顺序一致性)这玩意的定义不同的地方有不同的 ...

Linux ext3fs crash recovery systemxv6 Design Defects Every block needs to be written twice(one for log and another for fs) Syscall needs wait for committing disk I/O is synchronized ext3 Journal Designext3 could track on multiple transactions’ status at one time to get more parallelism. Similar to xv6, ext3 has write-back block cache and maintains each transaction a transaction info, includes Every transaction has a sequence number Revised block number by this tnx handles On disk circular lo ...

File system on xv6File system features Abstraction Crash Safety Disk Layout Performance -> Because storage are slow File system structures1234567struct inode{ file_info; name; inode_num; link_count; open_fd_count;//File can only be deleted, if above two are 0}; 12345inode cache -> mostly for synchronization ↑logging ｜buffer cache ｜-------- ｜disk ...

Thread SwitchThis lecture talks about xv6’s mechanism of thread switching. Background knowledgeThread : one serial execution, it should have its own pc, registers and stack. The scheduling system focus on the interleave multiple threads. There are two main methods to get this done, the first is using multi-cores and the second is to switch. To deal with a computation-bound program which takes a long run to finish the job, the scheduling system uses timer interrupt to pre-empt the kernel then s ...

Lec10 Machinery about synchronizeToday’s lecture talks about some synchronize mechanism, from lock, condition to wait to give a clear concept of what these mechanisms really effect. Diagram about switchTo avoid deadlock and repeat processes while doing switch, kernel needs a right order to lock and unlock. We need to make sure no other locks during swtch. Assume we have just 1 CPU and once p1 switch with 1 lock to p2, if p2 also tring to acquire the lock-> deadlock And acquire() turns off ...

LocksThis lecture talks about locks, I believe many people already have the concept of locks. So I just skip the very beginning of the lecture. Basic lock guidelineA consecuative rule: 2 processes accessing a shared data structure.If one is a writer=> lock data structure is needed. Too strict: there is a style called lock-free programming. Isn’t all situation needed lock Too loose: Some situation are no shared memory but still need lock Some problems Deadlock When two process trying to ac ...

InterruptRISCV interrupt-related registersSIE – supervisor interrupt enabled register, 3 bits for software int, external int and timer int.SSTATUS – supervior status register, one bit to enable interrupts.SIP – supervisor interrupt pending registerSCAUSE – supervisor cause registerSTVEC – supervisor trap vector registerMDELEG – machine delegate register Use of PLICPLIC, platform-level interrupt controller, passes interrupt on to a CPU. It is the handler of interrupts, that distributes interrupts ...

Page FaultVirtual MemoryTwo advantages: Isolations: Because of the exist of satp, two different processes can’t visit other’s physical memory Memory Indirection: The mapping from va -> pa, provides us many interesting features like, page fault, demanding, lazy allocation… sbrk()Grow(or shrink) the heap from lower to higher place(or h -> l)Two allocations methods: Eager Allocation: Allocate the memory immediately once sbrk() is called. Lazy Allocation: Allocate the memory only when t ...

Lec6- Isolation and syscallSupervisor registers stap – Store the page table’s base address stvec – Store the address of trap program – trampolines, note that this address is mapped on user’s page table but without PTE_U which means the user can’t modify it. sepc – Store the address in the user mode when ecall happens sstrach – Store the address of trapframe which stores a frame useds to temporarily keep the user’s registers. Also used as swap “transfer station” register. See the usage of csrrw ...

NetworkingIn this lab, we will program on NIC driver to control packet receive and transmit process. Because the lab has a detailed description of how to do the lab, I’ll just put on our code and explain some key points in the lab. Code Part1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253inte1000_transmit(struct mbuf *m){ // // Your code here. // // the mbuf contains an ethernet frame; program it into // the TX descriptor ring so that th ...

Lab10 MmapIn this lab, we need to develop a weak mmap(void* addr, size_t length, int prot, int flags, int fd, off_t offset), which have no designated addr and prot and flags are also limited to READ, WRITE and both and SHARED and PRIVATE. Also, we have to implement munmap(void *addr, size_t length), which won’t punch a hole in the middle of a region. To make mmap fast return, we won’t allocate any physical pages for a mmap call, and instead, we just put the call into a vma slot contains its me ...

Lab7 LockMemory allocatorThis section is to make kalloc and kfree parallelly performed. The main idea is the free-list is shared among all CPUs so all CPUs need to serialize the allocation that we could improve this process by maintaining multiple freelist on different CPU. Threads need to steal freepage from other CPU’s if its freelist is null. Actually we could let process steal more pages to reduces the frequency of starve for freelist. But I just do the lazy programing and make process steal ...

Lab 5 Lazy AllocationIn this lab, we gonna implement lazy allocation which means delay the true memory allocation till we actually needs it. lazy sbrk()To start with, we should modify the sbrk() from eager allocation to lazy one.But we should note that the parameter n can be arbitary number, either + or - so once the number is positve do the lazy allocation, but if the number is negative, we should do the deallocation immediately. Lazy AllocationThe time to truely allocate a page, is when kernel ...

Lab6 COWCopy-on-write on xv6In this lab, we need to implement COW on xv6. The idea of the lab is quite straight forward but there are some subtle detailsneeds to be treated carefully. Main idea of the lab, is to lazily allocate the physical page to child process. This lab takes almost 15h to debug (what fk), so I will give a detailed description of how I code and hope to give a rather clear idea. Firstly, define some utils functions to manipulate refrence count table int get_ref(uint64 pa) // r ...

Lab3 pagetable In this lab, we will modify the pagetable, and finally be able to dereference pointers in the kernel mode. Lab1–Print page table In this lab, it’s much easier than later two lab that we just need to write a DFS recursive function to walk down the 3-level pagetable and print out the path. Check vm.c/freewalk() and dfs the pagetable, note the format of a virtual memory address.We should notice that different from intel’s pagetable, xv6 store the P ...