ECE391- Computer System Engineering
University of Illinois at Urbana- Champaign
Fall 2021
Lecture 16 Filesystems
§ 1-302 RULES OF CONDUCT
• Students enrolling in the university assume an obligation to conduct themselves in a manner compatible with the university’s function as an educational institution and suitable to members of the academic community.
a. “…any verbal threat or physically threatening behavior that would cause a reasonable person to fear for their safety”
f. “Any conduct that substantially threatens or interferes with the maintenance of appropriate order and discipline in the operation of the university…”
https://studentcode.illinois.edu/article1/part3/1-302/
Syllabus Addendum
“Behavior that persistently or grossly interferes with classroom activities is considered disruptive behavior and may be subject to disciplinary action. Such behavior inhibits other students’ ability to learn and an instructor’s ability to teach. A student responsible for disruptive behavior may be required to leave class pending discussion and resolution of the problem and may be reported to the Office for Student Conflict Resolution for disciplinary action. “
Responding to Disruptive or Threatening Student Behavior: A Guide for Faculty and Staff
Stress management
• Avoid – Believe it or not, you can simply avoid a lot of stress. Plan ahead, rearrange your surroundings and reap the benefits of a lighter load.
• Take control of your surroundings
• Learn to say no.
• Ditch part of your list.
• Alter -One of the most helpful things you can do during times of stress is to take inventory, then attempt to change your situation for the better.
• Respectfully ask others to change their behavior.
• Communicate your feelings openly.
• Manage your time better.
• State limits in advance.
• Accept -Sometimes we may have no choice but to accept things the way they are. For those times try to:
• Talk with someone.
• Forgive.
• Practice positive self-talk.
• Learn from your mistakes.
• Adapt – Thinking you can’t cope is one of the greatest stressors. That’s why adapting — which often involves changing your standards or expectations — can be most helpful in dealing with stress.
• Adjust your standards.
• Practice thought-stopping.
• Reframe the issue.
• Adopt a mantra.
• Create an assets column.
• Look at the big picture.
https://www.mayoclinic.org/healthy-lifestyle/stress-management/in-depth/stress-relief/art-20044476
Stress management
• Avoid – Believe it or not, you can simply avoid a lot of stress. Plan ahead, rearrange your surroundings and reap the benefits of a lighter load.
• Take control of your surroundings
• Learn to say no.
• Ditch part of your list.
• Alter -One of the most helpful things you can do during times of stress is to take inventory, then attempt to change your situation for the better.
• Respectfully ask others to change their behavior.
• Communicate your feelings openly.
• Manage your time better.
• State limits in advance.
• Accept -Sometimes we may have no choice but to accept things the way they are. For those times try to:
• Talk with someone.
• Forgive.
• Practice positive self-talk.
• Learn from your mistakes.
• Adapt – Thinking you can’t cope is one of the greatest stressors. That’s why adapting — which often involves changing your standards or expectations — can be most helpful in dealing with stress.
• Adjust your standards.
• Practice thought-stopping.
• Reframe the issue.
• Adopt a mantra.
• Create an assets column.
• Look at the big picture.
https://www.mayoclinic.org/healthy-lifestyle/stress-management/in-depth/stress-relief/art-20044476
Quick Resources
• As always, if it is a true safety emergency, please call 911.
• The Counseling Center is open Monday through Friday, 8 a.m. to 5 p.m. and can be reached at 217- 333-3704.
• The Student Assistance Center can be reached at (217) 333-0050 or email
• Those needing mental health support after 5 p.m. and on weekends please contact the Crisis Line at 217-359-4141 (TTY: 217-352-4217) to speak with a counselor.
https://studentaffairs.illinois.edu/support-resources
Announcements
• MP2
• Final Checkpoint: 5:59PM on 10/12
• MP3
• Checkpoint 1: 5:59PM on Tuesday 10/19
• Teams scheduled be released by the end of Tuesday 10/12
• End of Thursday 10/14
Virtualization
• Virtualization is the process of creating a software- based, or virtual, representation of something, such as virtual applications, servers, [memory, cpu, ] storage and networks.
• How do we virtualize?
https://www.vmware.com/solutions/virtualization.html
Sharing
• Time sharing is a basic technique used by an OS to share a resource. By allowing the resource to be used for a little while by one entity, and then a little while by another, and so forth, the resource in question (e.g., the CPU, or a network link) can be shared by many.
• The counterpart of time sharing is space sharing, where a resource is divided (in space) among those who wish to use it.
• For example, disk space is naturally a spaceshared resource; once a block is assigned to a file, it is normally not assigned to another file until the user deletes the original file.
• What did we just share last lecture? How? What else might we virtualize?
https://pages.cs.wisc.edu/~remzi/OSTEP/
Goals
• By the end of this sequence you should understand:
• the role of a file system in an operating system
• user and applications view of the UNIX filesystem • the virtual file system interface
• how the ext2 operating system works
• The ECE 391 MP 1 filesystem
Acknowledgements
• M. J. Dominus
• http://perl.plover.com/classes/ext2fs/samples/slide001.html
• . Antonelli
• http://www-personal.umich.edu/~cja/
•
• http://www.cs.uiuc.edu/class/fa07/cs423/overheads.html
• Remzi H. Arpaci-Dusseau and . Arpaci-Dusseau • http://pages.cs.wisc.edu/~remzi/OSTEP/
• Understanding the Linux Kernel (ULK) • Chapter 12, 15, 16, 18
Filesystems
the role of a file system in an operating system
Generic Files and Filesystems
• Must store large amounts of information
• Must survive termination of process using the
information
• Must allow other processes to access the information
• OS abstracts from the physical properties of its storage device to define a logical storage unit, called file. Files are mapped by the OS onto physical devices.
Differing Perspectives on Design
System Software
• Block oriented
• Physical sector #s
• No protection among users of the system
• Data might be corrupted if machine crashes
Application Software
• Byte oriented
• Named files
• Users protected from each other
• Robust to machine failures
Systems Software Challenges
• Workloads
• Files grow and shrink in pieces • Little a priori knowledge
• Performance
• Overcoming disk, tape, SSD performance behavior
• Failure
Application workloads and system
software design
• How are files organized by applications?
• Unstructured data – User program decides meaning (most common)
• Records – Fixed length
• Indexed data – Tree or other structure of records with keys
• How do applications access files?
• Sequential: bytes read in order (most common)
• Random: read/write element out of middle of arrays
• File characteristics (measurements of UNIX and NT)
• Most files are small (about 8KB)
• Most of the disk is allocated to large files – (90% of data is in 10% of files
• Large files use up most of the disk space
• Large files account for most of the bytes transferred
• Bad news is we need everything to be efficient all the time
File System Design Considerations
• How will we organize the storage on the physical device (layout)?
• How do we create new storage for a file (allocation)?
• How do we keep track of what is used and free (tracking of free blocks)?
• How do we organize files (directories)?
Example designs: allocation
• Contiguous blocks?
• Linked-List of blocks?
• Linked-List of blocks + Table? • I-nodes?
Contiguous Allocation
• Simple: store 2 #ʼs • Efficient: 1 seek
• Random Access
• Must know file size • Fragmentation
Linked-List Allocation
• Index with address to first
• First word points to next
block
• Can grow files dynamically
• Random Access is slow
• Internal Fragmentation
• Incomplete block sizes
• Unreliable: what if you lose one Block in chain?
Linked-List + Table
Example file: 4, 7, 2, 10, 12
0
1
2
10
3
11
4
7
5
6
3
7
2
8
9
10
12
11
12
-1
13
14
15
• FAT in memory
• pointers stored in table
(block,next)
• next = -1 indicates eof
• Full block size available
• Random Access w/o disk
reference
• Directory can store 1 #
• FAT must be stored in memory!
• 20GBdisk
• 1KBblock
• 1 word per entry • =>80MB!
Indexed Allocation
• Associate each file with data structure: i-node
• table of fileʼs blocks
• Only need i-nodes in memory for open files
• set max # of open files
Example designs: tracking free blocks
• Must keep track of blocks that are free • List?
• Bitmap?
Free Block List
• Block Contents:
• entries of other block addresses that are free • last entry points to another block
• Pros/Cons:
• Can be large
• Can be stored on Free Blocks
• Can load one block into memory at a time
• 16 GB free, 1 KB blocks, 4 bytes per entry => 65,794 blocks
Free Bitmap
• 1 bit per block (1 = free, 0 not free)
• 16 GB free, 1 KB blocks, 1 bit per entry => 2,048 blocks
• Fixed in size
• Free list can be smaller if few free pages • Can have 1 block in memory at a time
Filesystems
A brief primer on user and application software perspectives in UNIX
UNIX File System
• UNIX File – a sequence of 0 or more bytes containing arbitrary information
• Meaning of the bits is entirely up to the fileʼs owner
• File Names
• up to 255 characters (BSD, System V,…) • Base name + extension
• A (regular) file is a linear array of bytes that can be read or written starting at any byte offset in the file
• The size of the file offset determines the absolute maximum size of any file
• E.g., 32b offset, 4,294,967,296B file
UNIX Filesystem Calls
UNIX Filesystem Concepts
• File names are stored in a file called a directory
• Directories may refer to other directories as well as
to files
• A hierarchy of these directories is called a filesystem
• Each filesystem tree (a connected graph with no cycles) has a single topmost root directory
• Hardware devices are represented as special files
• A UNIX mantra: everything is a file
Important Directories in most UNIX Systems
Absolute vs. relative path names
• A file is accessed using its path name
• Absolute path name
• /dir1/dir2/…/dirn/filename • /opt/moab/etc/moab.cfg
• Relative path name
• current-working-directory/filename • moab.cfg
• Every process maintains a notion of a current working directory
• Initialized at login from /etc/passwd home directory field • Changed via chdir() system call
Soft Links
• A symbolic link, also termed a soft link, is a special kind of file that points to another file, much like
a shortcut in Windows or a Macintosh alias.
• Unlike a hard link, a symbolic link does not contain the data in the target file. It simply points to another entry somewhere in the file system.
• Can soft link directories
• Now it’s a filesystem graph
• Can cross filesystem boundary
• Separate permissions for different links
• “Dangling softlink” if pointed-to file is deleted
https://kb.iu.edu/d/abbe
UNIX Filesystem Directory Calls
Filesystems
Virtual file systems
The UNIX Filesystem
• In the beginning, there were two • UNIXTM File System (1971)
• Berkeley Fast File System (1983)
• After that, things got complicated
http://en.wikipedia.org/wiki/Berkeley_Software_Distribution
Virtual File System
• The role of the VFS is:
• Keep track of available filesystem types.
• Associate (and disassociate) devices with instances of the appropriate filesystem.
• Do any reasonable generic processing for operations involving files.
• When filesystem-specific operations become necessary, vector them to the filesystem in charge of the file, directory, or data structure (i.e., inode) in question.
http://www.tldp.org/LDP/khg/HyperNews/get/fs/vfstour.html
ECE391- Computer System Engineering
University of Illinois at Urbana- Champaign
Fall 2021
Lecture 16 Filesystems (cont.)
What is an infraction of academic
integrity?
• Cheating – using or attempting to use unauthorized materials
• Plagiarism – representing the words, work, or ideas of another as your own
• Fabrication – the falsification or invention of any information, including citations
• Facilitating Infractions of Academic Integrity – helping or attempting to help another commit an infraction
• Bribes, Favors, and Threats – actions intended to affect a grade or evaluation
• Academic Interference – tampering, altering or destroying educational material or depriving someone else of access to that material
https://provost.illinois.edu/policies/policies/academic-integrity/students-quick-reference-guide-to-academic-integrity/
Announcements
• MP3
• Checkpoint 1: 5:59PM on Tuesday 10/19
• Teams scheduled be released by the end of Tuesday 10/12
• End of Thursday 10/14 • 10/13/2021 (yesterday)
• Exam 2
• 10/28/2021, 7-9 PM, ECEB 1002 • Conflicts by 10/22/2021
• No Class 10/28/2021
Filesystems
ext2fs
What’s ext2fs?
• It’s the Extended Filesystyem for Linux • (Version 2)
• I don’t know what became of version 1
• Very common
• Probably most of your Linux system disks are ext2fs
http://perl.plover.com/classes/ext2fs/samples/slide001.html
Where’s the Code?
• Where’s the Code
• Unix filesystems all have certain structures in
common
• Generic Unix FS internals
• Generic code is in /usr/src/linux/fs
• Also /usr/src/linux/include/linux/fs.h and elsewhere
• Differences in ext2
• ext2-specific code is in /usr/src/linux/fs/ext2 • Also /usr/src/linux/include/linux/ext2*.h
Overview of Unix Filesystem
Structure
• There are three important parts: • Superblock (only one of these)
• Inodes (one per file)
• Data blocks (the rest of the disk)
• The superblock represents the entire filesystem
• Each inode represents a single file
• These belong to the system—they have a fixed format • You cannot read or write them directly
• The data blocks belong to the user • That’s where the data is stored
• Typically, 8kb each
Overview of Unix Filesystem Structure
• ext2fs is a little different
• There are some other structures between the superblock
and the inodes
• There are bitmaps recording which blocks are in use and which inodes
• One bit per block or inode
• The disk is partitioned into ‘block groups’
• Each block group has a copy of the superblock and bitmaps, some of the inodes, and some data blocks
• That way if the superblock or bitmaps are destroyed they can be restored from a copy
• So the picture above shows a single block group instead of the entire disk
struct file_system_type {
const char *name;
int fs_flags;
struct super_block *(*get_sb)(struct file_system_type *,
int, char *, void *, struct vfsmount *); void (*kill_sb) (struct super_block *); struct module *owner;
struct file_system_type *next;
struct list_head fs_supers;
struct lock_class_key s_lock_key; struct lock_class_key s_umount_key;
};
Linux Virtual File System Objects
Superblocks
• The first block is the ‘superblock’
• Metainformation about the entire filesystem is
stored there
• What kind of filesystem is it?
• How many blocks are there? How many are free?
• (This must be stored somewhere, or else df would take forever)
• How big are the blocks?
• How many inodes are there? How many are free?
• Code for reading in the superblock is in super.c • (That’s /usr/src/linux/fs/super.c)
https://www.win.tue.nl/~aeb/linux/lk/lk-8.html
Linux Virtual File System Objects
struct super_block { dev_t s_dev;
unsigned long s_blocksize; struct file_system_type *s_type; struct super_operations *s_op; struct dentry *s_root;
…
}
struct super_operations {
struct inode *(*alloc_inode)(struct super_block *sb); void (*destroy_inode)(struct inode *);
void (*read_inode) (struct inode *);
void (*dirty_inode) (struct inode *);
void (*write_inode) (struct inode *, int);
void (*put_inode) (struct inode *);
void (*drop_inode) (struct inode *);
void (*delete_inode) (struct inode *);
void (*put_super) (struct super_block *);
void (*write_super) (struct super_block *);
int (*sync_fs)(struct super_block *sb, int wait); void (*write_super_lockfs) (struct super_block *); void (*unlockfs) (struct super_block *);
int (*statfs) (struct super_block *, struct statfs *);
int (*remount_fs) (struct super_block *, int *, char *); void (*clear_inode) (struct inode *);
void (*umount_begin) (struct super_block *);
int (*show_options)(struct seq_file *, struct vfsmount *);
};
Virtual File Systems
• Operations like read, mount, and so on are performed differently for different kinds of file systems
• The code for reading a ramdisk is very different than for reading a real disk
• The kernel deals with this by creating an abstraction layer
• Typically, the top layer will have a list of filesystem types
• Each filesystem type will have a virtual method table
• When you load in a kernel module:
• The module provides functions for the file system operations
• And it registers the method table in a global kernel data structure
• Usually a linked list
• There is a similar organization further down to handle different kinds of physical devices
Virtual File Systems
• To mount:
• Look up the file system type in the list
• Find the method table for this file system type
• Invoke the read_super method for this file system type
• Actually the method tables in file_system_type list have only this one method!
• That’s because you can’t do anything else until you’ve loaded the superblock anyway
• Once the superblock is read in, you can do more stuff
Superblocks
• Each time you mount a filesystem, the kernel builds a struct super_block
• This struct contains a method table of superblock operations
• The structs are linked into a list
• mount’s job is to build this struct and put it into the list
• Typical mount call:
• mount(“/dev/hdb2”, “/home”, “ext2”, …);
Inodes
• In some sense, the inode is the most interesting structure on the disk
• Morethananyothersinglestruct,theinodeiswhatmakesunixunix
• The inode represents a file
• iforindex
• The inodes are addressed starting with 1
• Eachinode’snumberisitsi-number
• The inode contains all the important information about the file: • Whoownsthefile?Whatarethepermissions?
• Isitaplainfile,oradirectory,orasymlink,orsomethingelse?
• Whenwasitlastmodified?Whenwasitlastaccessed?
• And,mostimportant:Whichdatablocksholditsdata?
• In fact, the only important property of a file that isn’t in the inode is the name!
struct inode {
unsigned long i_ino;
umode_t i_mode;
uid_t i_uid;
gid_t i_gid;
kdev_t i_rdev;
loff_t i_size;
struct timespec i_atime;
struct timespec i_ctime;
struct timespec i_mtime;
struct super_block *i_sb;
struct inode_operations *i_op; struct address_space *i_mapping; struct list_head i_dentry;
…
}
Linux Virtual File System Objects
Directories
• Why isn’t the name of a file in the inode?
• BecauseonaUnixsystem,afilecanbeknownbymorethanonename
• Forexample,/home/mjd/Mail/..,/home/mjd/.,and/home/mjdareall the same file
• It’s the directories that supply names, not the inodes
• Directories are stored as data block and referenced by an inode.
• A directory file is a linked list of directory entry structures.
• Each line is called a link. It has a name and an i-number • Hencethelinkandunlinksystemcalls
• The actual format of a link varies from version to version of Unix • Originally,eachlinkwasjust14bytesofnamefollowedby2bytesofi-
number
• ext2fs uses counted-length names instead of fixed-length names
https://www.nongnu.org/ext2-doc/ext2.html#linked-directory-entry-structure
Directories
• When you ask for a file by name, Unix looks in the directory to find the i-number
• From the i-number, it can get the inode; for example fs/ext2/inode.c:
• From the inode, the kernel can get the data in the file
• If the file is another directory, the data is links— more names and i-numbers
Directories
• For example, to open /home/mjd/.profile:
• / is always in inode 2 of the root filesystem (Unless the process has done chroot)
• Open inode 2, read in the data, look for home, get the i-number
• Open the inode for home, read in the data, look for mjd, get the i-number
• Open the inode for mjd, read in the data, look for .profile, get the i-number
• Open the inode for .profile, read in the data, build a struct inode
• The system file pointer table gets a pointer to this struct inode
• The process’s file descriptor table has a pointer to the file pointer
… more on these structures next lecture
Struct file {
struct dentry *f_dentry; struct vfsmount *f_vfsmnt; struct file_operations *f_op; mode_t f_mode;
loff_t f_pos;
struct fown_struct f_owner; unsigned int f_uid, f_gid; unsigned long f_version;
…
}
struct file_operations {
struct module *owner;
loff_t (*llseek) (struct file *, loff_t, int);
ssize_t (*read) (struct file *, char *, size_t, loff_t *);
ssize_t (*aio_read) (struct kiocb *, char *, size_t, loff_t);
ssize_t (*write) (struct file *, const char *, size_t, loff_t *);
ssize_t (*aio_write) (struct kiocb *, const char *, size_t, loff_t);
int (*readdir) (struct file *, void *, filldir_t);
unsigned int (*poll) (struct file *, struct poll_table_struct *);
int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);
int (*mmap) (struct file *, struct vm_area_struct *);
int (*open) (struct inode *, struct file *);
int (*flush) (struct file *);
int (*release) (struct inode *, struct file *);
int (*fsync) (struct file *, struct dentry *, int datasync);
int (*aio_fsync) (struct kiocb *, int datasync);
int (*fasync) (int, struct file *, int);
int (*lock) (struct file *, int, struct file_lock *);
ssize_t (*readv) (struct file *, const struct iovec *, unsigned long, loff_t *);
ssize_t (*writev) (struct file *, const struct iovec *, unsigned long, loff_t *);
ssize_t (*sendfile) (struct file *, loff_t *, size_t, read_actor_t, void *);
ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int);
unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
};
Linux Virtual File System Objects
Directories
• Since two directories can list the same i-number, a file can have two names
• Or maybe a file’s i-number is not listed anywhere
• Then the file is lost!
• fsck detects this and makes a new link under /lost+found
• To rename a file in the same directory, just change the name in the link
• No copying is necessary
• To move a file to a different directory, link it in the
new place and unlink the old name • No copying is necessary
Link Count
• One of the items in the inode is a link count • “How many links are there to this file?”
• When you unlink a file, the kernel decrements the link count
• If the link count is 0, the kernel frees up the data blocks
• Unless someone still has the file open
• In which case the data is freed only when the file is closed
• This means you can open a file and unlink it
• Andstillreaditandwriteit
• unlinkingdoesn’tremovethefile;itonlyremovesthename
struct dentry {
struct inode *d_inode;
struct dentry *d_parent;
struct qstr d_name;
struct super_block *d_sb;
struct dentry_operations *d_op; struct list_head d_subdirs;
…
}
struct dentry_operations {
int (*d_revalidate)(struct dentry *, int);
int (*d_hash) (struct dentry *, struct qstr *);
int (*d_compare) (struct dentry *, struct qstr *, struct qstr *); int (*d_delete)(struct dentry *);
void (*d_release)(struct dentry *);
void (*d_iput)(struct dentry *, struct inode *);
};
Linux Virtual File System Objects
Data Blocks
• The tail end of the inode records where the data is actually stored: /* include/linux/ext2_fs.h */
struct ext2_inode {
…
__u32 i_block[EXT2_N_BLOCKS];/* Pointers to blocks */ …
};
• Data blocks are addressed by with 32-bit numbers starting from 0 within each block group
• The inode has room for 15 block addresses (that’s EXT2_N_BLOCKS)
• Elements 0..11 store the addresses of the first 12 blocks in the file
• What if a file needs more than 12 blocks?
Data Blocks
• What if a file needs more than 12 blocks?
• Block 12 does not contain any file data itself
• Instead, it is stuffed full of addresses for more data blocks
• It’s called an indirect block
• This suffices for files up to 2060 blocks
• Block 13 is the double indirect block
• This suffices for files up to 2060 + 4194304 blocks = 34.376 Gb
• Block 14 is a triple indirect block
block size b
4 kB
2 kB
1 kB
direct
48 kB
24 kB
12 kB
indirect
4 MB
1 MB
256 kB
doubly ind.
4 GB
512 MB
64 MB
triply ind.
4 TB
256 GB
16 GB
Data Blocks
• The indirect block structure means that small files can be read quickly
• The block numbers are right in the inode
• Large files are still possible, however
• For symlinks, ext2fs dispenses with the block addresses entirely
• It uses the i_block area for the name of the linked-to file
• (Unless that name is larger than 60 bytes)
• (In which case it allocates blocks to hold the name and stores
the block addresses as usual)
• This makes the symlinks faster
• The kernel only needs to go to the disk once instead of twice
Filesystems
The ECE 391 MP 3 filesystem
MP3 File System
MP3 File System: example declaration of data structures
• Memory file system -> all data kept in memory
• boot block:
• int32_t dir_count;
• int32_t inode_count;
• int32_t data_count;
• int8_t reserved[52];
•
• dentry:
• int8_t filename[FILENAME_LEN];
• int32_t filetype;
• int32_t inode_num;
• int8_t reserved[24];
• inode:
• int32_t length;
• int32_t data_block_num [1023];
MP3 File System Utilities (used by the kernel)
read_dentry_by_name () {
< Scans through the directory entries in the “boot block” to find the file name > Call read_dentry_by_index() {
< Populates the dentry parameter -> file name, file type, inode number >
} }
You call read_dentry_by_name () in sys_open() system call < open a file; set up the file object -> inode, fops, flags, position >
MP3 File System Abstractions
• Each task can have up to 8 open files
• Open files are represented with a file array (in a Process Control Block; PCB)
• File array is indexed by a file descriptor
… More on these concepts next lecture