📂
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
  • Allocate a disk block
  • Free a disk block
  • Both allocation and free must be called inside a transaction

Was this helpful?

  1. File System

Block Allocator

Xv6’s block allocator maintains a free bitmap on disk, with on bit per block.

Allocate a disk block

Find the first available block, mark as in-use.

#define BSIZE 1024 // block size
// Block containing inode I
#define IBLOCK(I, sb)     ((i) / IPB + sb.inodestart)

// Bitmap bits per block
#define BPB           (BSIZE*8)

// Block of free map containing bit for block b
#define BBLOCK(b, sb) ((b)/BPB + sb.bmapstart)

Note: sb is superblock. struct superblock sb;

static uint
balloc(uint dev)
{
  int b, bi, m;
  struct buf *bp;

  bp = 0;
  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);
  }
  panic("balloc: out of blocks");
}

The outer loop reads each block of bitmap bits. The inner loop checks all BPB bits in a single bitmap block.

Free a disk block

Find it and mark the bit as 0.

static void
bfree(int dev, uint b)
{
  struct buf *bp;
  int bi, m;

  bp = bread(dev, BBLOCK(b, sb));
  bi = b % BPB;
  m = 1 << (bi % 8);
  if((bp->data[bi/8] & m) == 0)
    panic(“freeing free block”);
  bp->data[bi/8] &= ~m;
  log_write(bp);
  brelse(bp);
}

Both allocation and free must be called inside a transaction

PreviousInode ContentNextDesign a log system for crash recovery

Last updated 5 years ago

Was this helpful?