📂
build a OS
  • Learn OS with me
  • OS Interfaces
    • OS interfaces
    • I/O and File descriptors
    • Process and Memory
    • Pipes
    • File
  • OS Organization
    • OS Organization
    • Challenge yourself
  • Memory Management
    • XV6 Virtual Memory
    • Page Table
      • Part 1: How to translate address
      • Part 2: Create an Address Space
      • Part 3: How Page Table is used
      • Part 4: Page Fault and Swap
      • Part 5: How to operate on page tables
    • xv6 buddy allocator
      • How to display physical memory
    • Memory Management Walk Through
  • Traps and Interrupts
    • Trap Home Page
      • 系统调用的核心原理
    • What is trapframe
    • What is trampoline
    • Traps from kernel space
    • How fork() works
    • How system calls get into/out of the kernel
    • How exec() works
  • Scheduling
    • XV6 CPU Scheduling
    • How unix pipes work?
    • How does wait(), exit(), kill() work?
  • File System
    • Overview and Disk Layout
    • Buffer Cache
    • Design Inode Layer
    • Inode Content
    • Block Allocator
    • Design a log system for crash recovery
    • Directory Layer
    • Path names
    • File Descriptor Layer
    • FS System Calls
    • XV6 VS Real World
    • Make Xv6 File disk management system
    • Write FS simulator in python
    • How Redirect Shell command works
  • Concurrency
    • Spinlock
    • How linux select work
    • Hardware Support Locking
    • Exercise: Implement atomic counter
    • Locking in Xv6
    • Concurrency in Xv6
    • Exercise: Socket Programming with Event loop
  • Labs
    • Lab 1 Xv6 and Unix utilities
    • Lab 2 Shell
    • Lab 3 Buddy Allocator
    • Lab 4 Lazy
    • Lab 5 Copy-on-Write Fork for xv6
    • Lab 6 RISC-V assembly
    • Lab 6 Uthread: switching between threads
    • Lab 6 Alarm
    • Lab 7 Lock
    • Lab 8 File System: Large Files
    • Lab 8 File System: Symbolic links
    • Lab 9 mmap
    • Lab 10 Networking Part 1
    • Lab 10 Networking Part 2
  • Hardware, Device, Assembly
    • RISC-V assembly
    • Assembly: Access and Store information in Memory
    • Start xv6 and the first process
    • Why first user process loads another program?
    • What does kernel.ld do in XV6?
    • XV6 Device Driver
Powered by GitBook
On this page
  • The Problem
  • Your Task
  • High Level Explain
  • Implementation Details
  • Solution
  • Preliminaries
  • Change file metadata
  • Add features in bmap
  • 心得

Was this helpful?

  1. Labs

Lab 8 File System: Large Files

Increase the maximum size of an xv6 file.

PreviousLab 7 LockNextLab 8 File System: Symbolic links

Last updated 5 years ago

Was this helpful?

The Problem

Currently xv6 files are limited to 268 blocks, or 268*BSIZE bytes (BSIZE is 1024 in xv6). This limit comes from the fact that an xv6 inode contains 12 “direct” block numbers and one “singly-indirect” block number, which refers to a block that holds up to 256 more block numbers, for a total of 12+256=268 blocks.

Your Task

High Level Explain

Increase the maximum size of an xv6 file. You’ll change the xv6 file system code to support a "doubly-indirect” block in each inode, containing 256 addresses of singly-indirect blocks, each of which can contain up to 256 addresses of data blocks. The result will be that a file will be able to consist of up to 256*256+256+11 blocks (11 instead of 12, because we will sacrifice one of the direct block numbers for the double-indirect block).

Implementation Details

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.

Solution

Preliminaries

mkfs initializes the file system to have fewer than 2000 free data blocks, too few to show off the changes you’ll make. Modify kernel/param.h to change FSSIZE from 2000 to 200,000:

#define FSSIZE       200000  // size of file system in blocks

Rebuild mkfs so that is produces a bigger disk: $ rm mkfs/mkfs fs.img; make mkfs/mkfs

Change file metadata

Change NDIRECT from 12 to 11. In file.h, modify in-memory copy of an inode struct: Change size of addrs from NDIRECT+1 to NDIRECT+2.

Add features in bmap

bmap return the disk block address of the nth block in inode ip. If there is no such block, bmap allocates one.

in fs.h

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))

#define NDOUBLY_INDIRECT NINDIRECT*NINDIRECT
#define MAXFILE (NDIRECT + NINDIRECT + NDOUBLY_INDIRECT)

Improve bmap to support this double indirect: 1. Load double indirect block, allocating if necessary. 2. Load 2nd layer block. 3. Find disk block.

  bn -= NINDIRECT;

  if(bn < NDOUBLY_INDIRECT){
    // Load double indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT + 1]) == 0)
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;

    // load 2nd layer block.
    uint double_index = bn / NINDIRECT;
    if((addr = a[double_index]) == 0){
      a[double_index] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);

    // now find disk block.
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    uint pos = bn % NINDIRECT;
    if ((addr = a[pos]) == 0) {
      a[pos] = addr = balloc(ip->dev);
      log_write(bp);
    }

心得

画图是最好的解答之一,再把画出的设计图实现,就是编程。