Xv6 學習紀錄

課程影片連結： 6.S081 Fall 2020 Lecture 11: Thread Switching thread 的目標與手段 我們希望 multi-threading，是因為希望可以有多個 thread 去分享同一個 CPU，在 xv6 中，是以「過了一段時間換人使用」作為 thread switching 的依據。在這個目標之下，我們可以來思考以下幾件事情： 什麼是「(該換人 (thread) 使用 CPU) 的時間到了」 我們需要 save/restore 哪些關於 thread 的資訊 完整的流程該如何實做 1. 什麼是「(該換人 (thread) 使用 CPU) 的時間到了」? kernel/trap.c: usertrap(): void usertrap(void) { // [...] // give up the CPU if this is a timer interrupt. if(which_dev == 2) yield(); usertrapret(); } 在 usertrap() 中，如果是遇到 timer interrupt，則會進入到 yield()，進去之後會進入後續 thread switching 的處理 ...

Lab 連結：Lab: Multithreading Uthread: switching between threads (moderate) In this exercise you will design the context switch mechanism for a user-level threading system, and then implement it. To get you started, your xv6 has two files user/uthread.c and user/uthread_switch.S, and a rule in the Makefile to build a uthread program. uthread.c contains most of a user-level threading package, and code for three simple test threads. The threading package is missing some of the code to create a thread and to switch between threads. ...

課程影片連結： 6.S081 Fall 2020 Lecture 10: Multiprocessors and Locks Deadlock acquire(&l) acquire(&l) release(&l) Locks vs. Performance 越多 lock 雖然可能可以比較安全，但也會出現效能上的不佳 Case study UART kernel/uart.c struct spinlock uart_tx_lock; void uartputc(int c) { acquire(&uart_tx_lock); if(panicked){ for(;;) ; } while(uart_tx_w == uart_tx_r + UART_TX_BUF_SIZE){ // buffer is full. // wait for uartstart() to open up space in the buffer. sleep(&uart_tx_r, &uart_tx_lock); } uart_tx_buf[uart_tx_w % UART_TX_BUF_SIZE] = c; uart_tx_w += 1; uartstart(); release(&uart_tx_lock); } void uartintr(void) { // read and process incoming characters. while(1){ int c = uartgetc(); if(c == -1) break; consoleintr(c); } // send buffered characters. acquire(&uart_tx_lock); uartstart(); release(&uart_tx_lock); } Lock rules protect data structure Lock 的實做 broken lock void acquire(struct spinlock *lk) // does not work! { for(;;) { if(lk->locked == 0) { lk->locked = 1; break; } } } 這是一個錯誤的實做方法，因為可能有兩個 CPU 進入到 if (l->locked == 0) ...

kernel/kalloc.c data structure kmem 與 fun kmem 負責紀錄可使用的 pages，這些 pages 用一個 linked list 做紀錄 struct run { struct run *next; }; struct { struct spinlock lock; struct run *freelist; } kmem; 這個 Linked list run 是一個裡面就只有一個值，指向下一個可用的 page 的 address kalloc() 與 kfree() // Allocate one 4096-byte page of physical memory. // Returns a pointer that the kernel can use. // Returns 0 if the memory cannot be allocated. void * kalloc(void) { struct run *r; acquire(&kmem.lock); r = kmem.freelist; if(r) kmem.freelist = r->next; release(&kmem.lock); if(r) memset((char*)r, 5, PGSIZE); // fill with junk return (void*)r; } kalloc() 中，回傳 freelist 的 head，新的 head 變成 freelist->next Returns 0 if the memory cannot be allocated. 之所以這會成立，是因為在最一開始最一開始的時候，struct run *freelist; 被初始成 null (0)，kinit() 之前的這個唯一的 freelist 最後會變成 linked list 的結尾，這也是 kalloc() 之所以把記憶體用光之後會回傳 0 的原因 // Free the page of physical memory pointed at by pa, // which normally should have been returned by a // call to kalloc(). (The exception is when // initializing the allocator; see kinit above.) void kfree(void *pa) { struct run *r; if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP) panic("kfree"); // Fill with junk to catch dangling refs. memset(pa, 1, PGSIZE); r = (struct run*)pa; acquire(&kmem.lock); r->next = kmem.freelist; kmem.freelist = r; release(&kmem.lock); } pa 必須是一個 page 的開頭 kfree() 把這個不要的 pa 放到 freelist 的開頭 freelist 的初始化過程 kernel/main.c void main() { if(cpuid() == 0){ consoleinit(); printfinit(); printf("\n"); printf("xv6 kernel is booting\n"); printf("\n"); kinit(); // physical page allocator <- 這裡進入 kalloc.c kvminit(); // create kernel page table kvminithart(); // turn on paging procinit(); // process table trapinit(); // trap vectors trapinithart(); // install kernel trap vector plicinit(); // set up interrupt controller plicinithart(); // ask PLIC for device interrupts binit(); // buffer cache iinit(); // inode table fileinit(); // file table virtio_disk_init(); // emulated hard disk userinit(); // first user process __sync_synchronize(); started = 1; } else { while(started == 0) ; __sync_synchronize(); printf("hart %d starting\n", cpuid()); kvminithart(); // turn on paging trapinithart(); // install kernel trap vector plicinithart(); // ask PLIC for device interrupts } scheduler(); } kernel/kalloc.c: kinit() void kinit() { initlock(&kmem.lock, "kmem"); freerange(end, (void*)PHYSTOP); } 初始 kmem.lock 使用 freerange() 把可用的 page 都放到 freelist 中 kernel/kalloc.c: freerange() void freerange(void *pa_start, void *pa_end) { char *p; p = (char*)PGROUNDUP((uint64)pa_start); for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) kfree(p); } 這裡使用先前提到的 kfree() 一次一次的把可用 page 放到 freelist 的前方 ...

這篇主要是為了 lab locks 中的 “Buffer cache” 這一題，要我們先了解 bcache 的一些原理與應用，主要的參考資料是 xv6 book 8.1 ~ 8.3 與 bcache 相關的程式碼 kernel/main.c void main() { if(cpuid() == 0){ consoleinit(); printfinit(); printf("\n"); printf("xv6 kernel is booting\n"); printf("\n"); kinit(); // physical page allocator kvminit(); // create kernel page table kvminithart(); // turn on paging procinit(); // process table trapinit(); // trap vectors trapinithart(); // install kernel trap vector plicinit(); // set up interrupt controller plicinithart(); // ask PLIC for device interrupts binit(); // buffer cache <- 這裡進入 bcache 的初始化過程 iinit(); // inode table fileinit(); // file table virtio_disk_init(); // emulated hard disk userinit(); // first user process __sync_synchronize(); started = 1; } else { while(started == 0) ; __sync_synchronize(); printf("hart %d starting\n", cpuid()); kvminithart(); // turn on paging trapinithart(); // install kernel trap vector plicinithart(); // ask PLIC for device interrupts } scheduler(); } kernel/bio.c: binit() struct { struct spinlock lock; struct buf buf[NBUF]; // Linked list of all buffers, through prev/next. // Sorted by how recently the buffer was used. // head.next is most recent, head.prev is least. struct buf head; } bcache; void binit(void) { struct buf *b; initlock(&bcache.lock, "bcache"); // Create linked list of buffers bcache.head.prev = &bcache.head; bcache.head.next = &bcache.head; for(b = bcache.buf; b < bcache.buf+NBUF; b++){ b->next = bcache.head.next; b->prev = &bcache.head; initsleeplock(&b->lock, "buffer"); bcache.head.next->prev = b; bcache.head.next = b; } } 在 binit() 之後，就不會直接使用 bcache.buf 這個 array，而是使用由 head 開頭的這個環狀 linked-list bread() 與 bwrite() // Return a locked buf with the contents of the indicated block. struct buf* bread(uint dev, uint blockno) { struct buf *b; b = bget(dev, blockno); if(!b->valid) { virtio_disk_rw(b, 0); b->valid = 1; } return b; } 如果 bget() 可以拿到 buf 就直接回傳，如果不行，則使用 virtio_disk_rw() ...

Lab 連結：Lab: locks Memory allocator (moderate) Your job is to implement per-CPU freelists, and stealing when a CPU’s free list is empty. You must give all of your locks names that start with “kmem”. That is, you should call initlock for each of your locks, and pass a name that starts with “kmem”. Run kalloctest to see if your implementation has reduced lock contention. To check that it can still allocate all of memory, run usertests sbrkmuch. Your output will look similar to that shown below, with much-reduced contention in total on kmem locks, although the specific numbers will differ. Make sure all tests in usertests -q pass. make grade should say that the kalloctests pass. ...

// Init fs void fsinit(int dev) { readsb(dev, &sb); if(sb.magic != FSMAGIC) panic("invalid file system"); initlog(dev, &sb); } // Zero a block. static void bzero(int dev, int bno) { struct buf *bp; bp = bread(dev, bno); memset(bp->data, 0, BSIZE); log_write(bp); brelse(bp); } balloc() 與 bfree() // Blocks. // Allocate a zeroed disk block. // returns 0 if out of disk space. static uint balloc(uint dev) { int b, bi, m; struct buf *bp; bp = 0; // 掃過 super block for(b = 0; b < sb.size; b += BPB){ bp = bread(dev, BBLOCK(b, sb)); for(bi = 0; bi < BPB && b + bi < sb.size; bi++){ m = 1 << (bi % 8); if((bp->data[bi/8] & m) == 0){ // Is block free? bp->data[bi/8] |= m; // Mark block in use. log_write(bp); brelse(bp); bzero(dev, b + bi); return b + bi; } } brelse(bp); } printf("balloc: out of blocks\n"); return 0; } balloc() 是 block allocate 的意思 ...

課程連結：6.S081 Fall 2020 Lecture 14: File Systems 實際操作 在影片中 50:00 左右的地方開始有實際的操作 make clean make 先修改 kernel/bio.c: bwrite() // Write b's contents to disk. Must be locked. void bwrite(struct buf *b) { if(!holdingsleep(&b->lock)) panic("bwrite"); if (b->blockno >= 32) printf("write: %d\n", b->blockno); virtio_disk_rw(b, 1); }

Lab 連結：Lab: file system Large files (moderate) Modify bmap() so that it implements a doubly-indirect block, in addition to direct blocks and a singly-indirect block. You’ll have to have only 11 direct blocks, rather than 12, to make room for your new doubly-indirect block; you’re not allowed to change the size of an on-disk inode. The first 11 elements of ip->addrs[] should be direct blocks; the 12th should be a singly-indirect block (just like the current one); the 13th should be your new doubly-indirect block. You are done with this exercise when bigfile writes 65803 blocks and usertests runs successfully: ...

Lab 連結：Lab: mmap Lab: mmap (hard) The mmap and munmap system calls allow UNIX programs to exert detailed control over their address spaces. They can be used to share memory among processes, to map files into process address spaces, and as part of user-level page fault schemes such as the garbage-collection algorithms discussed in lecture. In this lab you’ll add mmap and munmap to xv6, focusing on memory-mapped files. 目前的理解會像是把 memory address map 到一個 file 中，可以有多個 process share 同一份資料的好處 ...