Practical File System Design

Contents1 Preface1.1 Acknowledgements 2 Introduction to the BeOS and BFS2.1 History Leading up to BFS 2.1.1 The 2.1.2 The 2.2 Design Goals 2.2.1 Design Constraints 2.3 Summary 3 What Is A File System?3.1 The Fundamentals 3.2 The Terminology 3.3 The Abstractions 3.3.1 Files 3.3.2 Directories 3.4 File System Operations 3.4.1 Initialization 3.4.2 Mounting 3.4.3 Unmount 3.4.4 Creating Files 3.4.5 Creating Directories 3.4.6 Lookup/Open 3.4.7 Write 3.4.8 Read 3.4.9 Delete 3.4.10 Rename 3.4.11 Read Meta-Data 3.4.12 Write Meta-Data 3.4.13 OpenDir 3.4.14 ReadDir 3.4.15 Summary 3.5 Extended File System Operations 3.5.1 Symbolic Links 3.5.2 Hard Links 3.5.3 Dynamic Links 3.5.4 MMap 3.5.5 Attributes 3.5.6 Indexing 3.5.7 Journaling/Logging 3.5.8 Guaranteed Bandwidth / Bandwidth Reservation 3.5.9 Access Control Lists 3.6 Summary 4 Other File Systems 4.1 BSD FFS 4.2 Linux ext2 4.3 Macintosh HFS 4.4 Irix XFS 4.5 Window's NT NTFS 4.5.1 The Master File Table and Files 4.5.2 File System Meta-Data 4.5.3 Directories 4.5.4 Journaling and the Log File Service 4.5.5 Data Compression 4.5.6 Summary 4.6 Summary 5 The Data Structures of BFS5.1 What is a disk? 5.2 How to Manage Disk Blocks 5.3 Allocation Groups 5.4 Block Runs 5.5 The Super-Block 5.6 The I-Node Structure 5.7 The Core of an I-Node: the Data Stream 5.8 Attributes 5.9 Directories 5.10 Indexing 5.11 Summary 6 Attributes and Indexing 6.1 Attributes 6.1.1 Example Uses of Attributes 6.1.2 Attribute API 6.1.3 Attribute Details 6.1.4 The Big Picture: Small Data Attributes and More 6.1.5 Attribute Summary 6.2 Indexing 6.2.1 What is an Index? 6.2.2 Data Structure Choices 6.2.3 B-Trees 6.2.4 B-Tree Variants 6.2.5 Hashing 6.2.6 Data Structure Summary 6.2.7 Connections: Indexing and the Rest of the File System 6.2.8 Automatic Indices 6.2.9 Other Attribute Indices 6.2.10 BFS B+Trees 6.2.11 The API 6.2.12 The Data Structure 6.2.13 Duplicates 6.2.14 Integration 6.3 Queries 6.3.1 Query Language 6.3.2 Parsing Queries 6.3.3 Read Query { The Real Work 6.3.4 String Queries and Regular Expression Matching 6.3.5 Additional Duties for Read Query 6.3.6 Live Queries 6.4 Summary 7 Allocation Policies 7.1 Where do you put things on disk? 7.2 What Are Allocation Policies? 7.2.1 Real Disks 7.2.2 What Can You Layout? 7.2.3 Types Of Access 7.2.4 Allocation Policies in BFS 7.3 Summary 8 Journaling 8.1 The Basics 8.2 How Does Journaling Work? 8.2.1 Types of Journaling 8.3 What is Journaled? 8.4 Beyond Journaling 8.5 What's The Cost? 8.6 The BFS Journaling Implementation 8.6.1 Writing to the Log 8.6.2 The End of a Transaction 8.6.3 Batching Transactions 8.7 What Are Transactions: Part 2 8.7.1 Create File/Directory 8.7.2 Delete 8.7.3 Rename 8.7.4 Changing A File Size 8.7.5 The Rest 8.8 Summary 9 The Disk Block Cache 9.1 Background 9.2 The Organization of a Buer Cache 9.2.1 Cache Reads 9.2.2 Cache Writes 9.3 Cache Optimizations 9.4 I/O and the Cache 9.4.1 Sizing the Cache 9.4.2 Journaling and the Cache 9.4.3 When Not To Use the Cache 9.5 Summary 10 File System Performance10.1 What is Performance? 10.2 What Are The Benchmarks? 10.2.1 Other Benchmarks 10.2.2 Dangers of Benchmarks 10.2.3 Running Benchmarks 10.3 Performance Numbers 10.3.1 Test Setup 10.3.2 Streaming I/O Benchmark 10.3.3 File Creation/Deletion Benchmark 10.3.4 The PostMark Benchmark 10.3.5 Analysis 10.4 Performance In BFS 10.4.1 File Creation 10.4.2 The Cache 10.4.3 Allocation Policies 10.4.4 The Duplicate Test 10.4.5 The Log Area 10.5 Summary 11 The VNode Layer 11.1 Background 11.2 Vnode Layer Concepts 11.2.1 Private Data 11.2.2 Cookies 11.2.3 Vnode Concepts Summary 11.3 Vnode Layer Support Routines 11.4 How It Really Works 11.4.1 In the Beginning11.4.2 Vnode Support Operations 11.4.3 Reading and Writing vnodes 11.4.4 Securing Vnodes 11.4.5 Directory Functions 11.4.6 Working with Files 11.4.7 Create, Delete, Rename 11.4.8 Attributes and Index Operations 11.5 The Node Monitor 11.5.1 Live Queries 11.6 Summary 12 User Level API 12.1 The POSIX API 12.1.1 The Attribute Functions 12.1.2 The Index Functions 12.1.3 The Query Functions 12.1.4 The Volume Functions 12.1.5 C Summary 12.2 The C++ API 12.2.1 The Class Hierarchy 12.2.2 The Concepts 12.2.3 The Entries 12.2.4 The BPath Object 12.2.5 The Node Object: BNode 12.2.6 BEntryList 12.2.7 BQuery 12.2.8 BStatable 12.2.9 BEntry 12.2.10 BNode 12.2.11 BDirectory 12.2.12 BSymLink 12.2.13 BDataIO/BPositionIO 12.2.14 BFile 12.2.15 Node Monitoring 12.3 Using the API 12.3.1 The Setup 12.3.2 Generating the Attributes 12.3.3 Issuing a Query 12.4 Summary 13 Testing 13.1 The Supporting Cast 13.2 Examples of Data Structure Verication 13.3 Debugging Tools 13.4 Data Structure Design for Debugging 13.5 Types of Tests 13.5.1 Synthetic Tests 13.5.2 Real World Tests 13.5.3 End User Testing 13.6 Testing Methodology 13.7 Summary A A File System Construction Kit A.1 Introduction A.2 Overview A.3 The Data Structures A.4 The API A.4.1 The Super-Block A.4.2 Block Allocation A.4.3 I-node Management A.4.4 Journaling A.4.5 Data Streams A.4.6 Directory Operations A.4.7 File Operations