This is the archived Fall 2013 version of the course. For the most recent version, see

Class 24: Storage

(Sorry, lost the ink from today's class. I hope the slides are clear without it.)

Action Items

Project Design and Progress reviews this week. Schedule is tight - please be ready to start on time, and prepare questions you have.

Storage Systems

Delay Lines

I do not imagine that many of the Turing lecturers who will follow me will be people who were acquainted with Alan Turing... Although a mathematician, Turing took quite an interest in the engineering side of computer design… Turing’s contribution to this discussion was to advocate the use of gin, which he said contained alcohol and water in just the right proportions... Sir Maurice Wilkes (1913-2010), Computers Then and Now (1967 Turing Award Lecture)

Why does it matter what you put in the delay line?

Kingston KVR16N11/4 4GB 2Rx8 512M x 64-Bit PC3-12800 newegg Datasheet

J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino (UVa BSCS 2004), Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten. Lest We Remember: Cold Boot Attacks on Encryption Keys. USENIX Security 2008.

Unix File System

An inode represents a file. It includes:

  • size (in bytes)
  • user ID, group ID, permissions
  • link count
  • diskmap

and many other properties (see fs.h).

stat (Unix command) provides information about an inode.

> stat -x class24.pptx
  File: "class24.pptx"
  Size: 5855495      FileType: Regular File
  Mode: (0644/-rw-r--r--)         Uid: (  501/    dave)  Gid: (   20/   staff)
Device: 1,2   Inode: 6706357    Links: 1
Access: Wed Nov 20 15:00:41 2013
Modify: Wed Nov 20 14:23:13 2013
Change: Wed Nov 20 14:23:13 2013

Why doesn't the inode include the filename?

What commands would make the value of Links become 2? Can it ever be 0?

Unix System 5 File System

Diskmap is 13 entries: 0-9 are direct pointers to disk blocks (each disk block is 1K bytes); 10 is a pointer to an indirect block (each entry points to a block); 11 is a pointer to a double indirect block (each entry points to an indirect block); 12 is a pointer to a triple indirect block (each entry points to a double indirect block).

What is the largest file that can be store using this system?

How would you test if your file system uses a similar structure?

df -i gives information about the device inodes:

> df -i
Filesystem    512-blocks      Used Available Capacity  iused    ifree %iused  Mounted on
/dev/disk0s2   975425848 503107888 471805960    52% 62952484 58975745   52%   /
devfs                369       369         0   100%      641        0  100%   /dev
map -hosts             0         0         0   100%        0        0  100%   /net
map auto_home          0         0         0   100%        0        0  100%   /home

Could I run out of inodes before I run out of storage space?

To explore your drive's inodes: tree --inodes

Improving Reliability

OpenZFS maczfs

It's for people who have Mac OS, who have any data, and who really like their data. Whether on a single-drive laptop or on a massive server, it'll store your petabytes with ragingly redundant RAID reliability, and it'll keep the bit-rotted bleeps and bloops out of your iTunes library.

Merkle Trees

When one block changes, how many hashes need to be updated?


David Patterson, Garth Gibson, and Randy Katz. A Case of Redundant Arrays of Inexpensive Disks (RAID) (SIGMOD 1988)

Modern Storage Systems

How should file systems be re-designed to account for SSDs and networked storage?


  • Challenges
  • Course Wrapup
  • Final Projects
  • Final Survey
  • Getting Started with Github
  • IRC
  • Problem Set 3 - Zhtta Server - Benchmarking
  • Project
  • Project Ideas
  • Problem Set 1 - zhttpto Web Server
  • Comments on PS1 Comments
  • Problem Set 1 Reference Solution
  • Problem Set 2 - The Good Auld Shell
  • Problem Set 3 - Zhtta Server
  • Page Removed
  • Schedule
  • Enrolling for Spring 2014
  • Syllabus
  • Using Materials
  • Using Rust for an Undergraduate OS Course
  • VirtualBox
  • Working on Github in cs4414