File System β Easy Exam Guide Unit u03 (Files + Directories). Every idea is explained in simple words and linked to how the exam asks it. π΄ = comes a lot Β· π‘ = comes sometimes Β· βͺ = rare.
Written in simple (B1) English. Read it from top to bottom before the exam.
0How "files" come in the exam
The file system is one of the easiest topics to get points. It is usually 1 or 2 multiple-choice questions, about 2β2.5 points each. You only need to remember facts and do a little simple math. There are just six kinds of questions. This guide makes each one easy.
| The question you will see | Where it comes from in u03 | Section |
|---|---|---|
| π΄ A row of 0/1 blocks β "which sentences are true?" (allocation, fit, fragmentation) | Directories slides β allocation | Β§5 |
| π΄ ASCII / Unicode / UTF-8 / binary true-false | Files slides β encoding | Β§1 |
π΄ A list of ln/rm/echo/cat commands β what is the content, size, link count? | Directories slides β links | Β§4 |
π΄ open/read/write/close true-false | Files slides β POSIX I/O | Β§2 |
π‘ opendir/readdir and stat/lstat/fstat behaviour | Directories slides β calls | Β§7 |
π‘ Read an ls -l line (permissions, size, link count) | Directories slides β UNIX FS | Β§8 |
1Files and character encoding π΄ comes a lot
What a file really is
A file is just a line of bytes. The Linux kernel does not know if a file is "text" or "binary". This difference is only in how you read the bytes, not in the file itself.
Text (ASCII) files
- ASCII is the old standard. It uses 7 bits, so 128 characters (32 are control codes, 96 you can print). "Extended ASCII" uses 8 bits, so 256 characters.
- Text is made of lines. A new line is LF (10) on UNIX/Linux/macOS, but CR+LF (13+10) on Windows. The exam likes this small difference.
Unicode and UTF-8
- Unicode is a big set of characters (more than 110,000). It is not an encoding. UTF-8, UTF-16, UTF-32 are ways to encode Unicode. So "Unicode = UTF-8" is false.
- Unicode contains ASCII. The first 128 Unicode characters are the same as ASCII.
- UTF-8 uses 1 to 4 bytes (variable length) and it works with ASCII. A pure ASCII file looks the same in UTF-8. UTF-16 uses 2 or 4 bytes, so it does not work with ASCII. UTF-32 always uses 4 bytes.
Binary files
- Binary files can use any byte. They hold images, programs, and compressed data. A person cannot read them easily, and a text editor can break them.
- The same binary file can look different on two computers (because of byte order / hardware). So binary files are not very portable.
- A number in ASCII and the same number in binary are not the same bytes, and not the same size. Example:
231as text is 3 bytes (the characters '2','3','1'). As a binaryintit is 4 bytes with a different pattern. Binary is often smaller for numbers, but not always. - Serialization means changing a struct into bytes so you can save it or send it. Unicode (16-bit) serialization makes a bigger file than ASCII (8-bit) for the same data.
- UTF-8 has variable length and works with ASCII.
- Unicode contains ASCII (it is a superset).
- Binary files are not easy to read and can change on a different computer.
- A Unicode text file can be bigger than the same text in ASCII.
- If you read a UTF-8 file as ASCII, you see strange characters.
- "ASCII has all modern languages." No β only ~128 characters.
- "Unicode is always 32 bits" / "all Unicode fits in 2 bytes." No β the length changes.
- "ASCII is variable length." No β it is fixed length.
- "Unicode and UTF-8 are the same." No β set vs encoding.
- "A number in ASCII and binary has the same bytes." No.
2Reading and writing files β two libraries π΄ comes a lot
In C there are two ways to read and write files. The exam tests the difference between them.
| ISO C library (with buffer) | POSIX system calls (no buffer) | |
|---|---|---|
| Handle | FILE * (a stream) | an int file descriptor (fd) |
| Buffer | Yes (but stderr has no buffer; use fflush) | No β every call goes to the system |
| Open/close | fopen, fclose | open, close |
| Read/write | fgetc/fputc, fgets/fputs, fscanf/fprintf, fread/fwrite | read, write, lseek |
| Standard files | stdin/stdout/stderr | 0=stdin, 1=stdout, 2=stderr |
The five system calls β this is what the exam asks
All UNIX file work uses five calls: open, read, write, lseek, close.
open() β the "how many parameters" trap
int open(const char *path, int flags); // 2 parameters int open(const char *path, int flags, mode_t mode); // 3 parameters, when you create a file
open()can take 2 or 3 parameters. You use the 3rd one (mode) only when you create a new file (withO_CREAT), to set its permissions. So "open takes exactly 2" is false, and "open takes exactly 3" is also false.- You must pick one:
O_RDONLY/O_WRONLY/O_RDWR. Extra flags:O_CREAT,O_EXCL,O_TRUNC,O_APPEND,O_SYNC. - Permission bits:
S_IRUSR/S_IWUSR/S_IXUSR(user), theβ¦GRPones (group), theβ¦OTHones (others). The real result is also changed by theumask. - It returns the fd, or
-1if there is an error.
read() and write() β the "what it returns" trap
int read (int fd, void *buf, size_t nbytes); int write(int fd, void *buf, size_t nbytes);
- They work on plain bytes β text, characters, a struct, anything. They are the same for a file, the screen, or a pipe.
read()returns the number of BYTES it read (0means end of file,-1means error). It does not return a number of "objects" likefread(), and not a number of "bits". This is the most common trap.write()writes to a system buffer, not always straight to the disk (unless you useO_SYNC).- Good fact to know:
printf()useswrite()inside.
lseek() and close()
off_t lseek(int fd, off_t offset, int whence); // whence: SEEK_SET / SEEK_CUR / SEEK_END int close(int fd);
lseekmoves the read/write position. If you move past the end and write, you make a hole (it reads back as zeros).- Files close by themselves when the program ends.
- "open() takes exactly 2 / exactly 3 parameters." It can take 2 or 3 (both phrasings are false).
- "read() returns the number of objects / bits." It returns bytes.
- "A cyclic-graph file system does not allow sharing." Graphs are made to allow sharing.
3Types of directories & the idea of links π‘ helps you understand Β§4
A directory is a node in a tree that keeps information about its files. We use directories for three reasons: speed, names, and grouping. The slides show how directories grew over time. You mainly need the last two types:
| Type | Idea | Problem |
|---|---|---|
| One level | all files in one directory | names must be different; no multi-user |
| Two levels | one directory for each user | you need a path; no grouping |
| Tree | directories inside directories (current dir, paths) | cannot share one file under two names |
| Acyclic graph | you can share: one file has many names/paths, using links | you must be careful when you delete β soft vs hard links |
| Cyclic graph | cycles are allowed | danger of infinite loops; usually you cannot link a directory |
A link is a reference to a file that already exists. When you share a file, there are two ways to delete it β and these two ways are the two link types in Β§4:
- delete now, when one name goes away β you can have a broken (dangling) link β this is a soft (symbolic) link;
- delete only when the last name goes away. A counter in the i-node counts the names β this is a hard link.
4Hard links and soft links π΄ ~3/13 exams β always a command trace
This is the most "tricky" file question. You follow a list of ln/rm/echo/cat commands and you say what the content, size, and link count are. Learn the model below and it becomes easy points.
The simple model
In UNIX, a directory is a table: it maps a name β an i-node number. The real data and information of the file live in the i-node. The i-node has a counter of names (link count).
| Hard link ln f1 f2 | Soft / symbolic link ln -s f1 f2 | |
|---|---|---|
| What it is | a second name for the same i-node | a small new file. Its data is the path of the target |
| Same content? | Yes β same i-node, same data. Change one name β both change | No β it only points by the path name |
| Counter | +1 for each hard link. Data is deleted only when the counter is 0 | does not change the target's counter |
| Size | same as the file | = length of the path text (e.g. "f1" β 2 bytes) |
| If you delete the target | data still lives, through the other hard links | the link is now broken β cat gives an error |
| Rules | you cannot hard-link a directory, or link across file systems | you can link a directory and cross file systems |
echo -n "hello_world" > f1 # f1: inode A, data "hello_world", count 1 ln f1 f2 # f2 β inode A, count 2 ln f1 f3 # f3 β inode A, count 3 β (not 2! this is the trap) ln -s f1 f4 # f4: NEW inode, soft link, data = "f1" (size 2) rm f1 # delete the NAME f1; inode A count β 2 (f2,f3 still here) echo "hello" > f4 # f4 points to path "f1" β it MAKES f1 again (new inode) echo "_world" >> f2 # add to inode A β now "hello_world_world"Result: f2 and f3 have the same content "hello_world_world"; the size of f4 is 2 bytes; after the two
ln commands the counter was 3; f1 exists again (made by the soft link); the hard-link count of f2 is 2.- Hard links share one i-node and one content; if you add text with one name, all names change.
ln f1 f2; ln f1 f3makes the counter 3 (the "= 2" option is a trap when a 3rd link exists).- A soft link's size = length of the path; it breaks when the target is deleted (the first
catgives an error), but writing through it can make the target again. - You cannot make a hard link to a directory.
5How files are placed on the disk (allocation) π΄ the most common FS question β ~5/13
You get the disk as a row of blocks (free = 0, full = 1). You must say which sentences are true. To do this, you think about three placement methods and three "fit" algorithms. Learn this part well and you own the topic.
The three placement methods
| Method | How it saves a file | Directory keeps | Fragmentation | Access |
|---|---|---|---|---|
| Contiguous | in blocks next to each other | start block + length | external (gaps) + internal (last block not full) | line by line and direct |
| Linked (and FAT) | blocks anywhere; each block points to the next | pointer to the first (and last) block | no external; but each block needs a pointer | only line by line is fast |
| Indexed (i-node) | blocks anywhere; all pointers are in one index block | pointer to the index block | no external; but the index block costs space | line by line and direct |
- FAT is a kind of linked method. It moves the pointers out of the blocks into one big table (the File Allocation Table). It needs two reads per block (table + data). If you lose the table, you lose everything.
- Contiguous: the biggest file = the longest run of free blocks. Linked/indexed: the biggest file = all free blocks (indexed: minus 1 block for the index).
The three "fit" algorithms β for contiguous placement
| Algorithm | It chooses⦠|
|---|---|
| First-fit | the first gap that is big enough (start from the left) |
| Best-fit | the smallest gap that still fits (less waste) |
| Worst-fit | the biggest gap (leaves a big free part) |
When you place many files in order, these three can give different results (one works, another fails). That is the whole point of the question.
Fragmentation math
- Internal fragmentation of one file =
(blocks used Γ block size) β file size. Hereblocks used = round up (file size / block size). It is always less than one block. - External fragmentation = free space in small gaps that you cannot use. Only contiguous placement has it.
- Write the index number over each bit. Find the runs of 0 (free) and their lengths.
- "Can a file of size S fit in contiguous?" β you need one run β₯
round up (S / block size). - "Can it fit in linked/indexed?" β just compare
round up (S / block size)with the total free blocks (indexed: minus 1 for the index). - For a fit-algorithm list β place each file in order, and remove the blocks you use.
- For internal fragmentation β blocks Γ block size β file size.
round up (2.9) = 3 blocks. It fits only if there is a run of 3 free blocks. "Indexed, 17 free blocks" β biggest file = 16 MB (1 block is the index).- "Contiguous has internal but not external fragmentation." It has both.
- "Indexed cannot save a file bigger than the longest run." Wrong β indexed uses blocks anywhere.
- Mixing best-fit and first-fit on a list of files β do the steps, do not guess.
- Forgetting the index block when you count indexed space.
6The UNIX i-node & free space π‘ base for Β§4βΒ§5
The i-node
UNIX/Linux uses indexed placement with a combined plan. Each file has an i-node. The i-node keeps information (mode, 2 owners, 3 times, size, block count) and 15 block pointers:
| Pointers | Type | What it reaches |
|---|---|---|
| 1β12 | direct | the first 12 data blocks (small files) |
| 13 | single indirect | a block of pointers β data |
| 14 | double indirect | a block of pointers β blocks of pointers β data |
| 15 | triple indirect | three levels of pointers |
So small files are fast (direct), but very big files are still possible (indirect). If one block holds k pointers (k = block size / pointer size), the biggest file β (12 + k + kΒ² + kΒ³) Γ block size.
Free-space management
The system remembers free blocks with a bitmap: one bit for each block (free or full). This bitmap is exactly the row of 0/1 that you see in the allocation questions.
The link count of a directory
A directory is also a file with hard links, so its link count follows a rule: an empty directory has count 2 (its name + its own . entry). It gets +1 for each sub-directory (each child has a .. that points back).
7Directory & information system calls π‘ ~2/13 exams
File information: stat / lstat / fstat
int stat (const char *path, struct stat *sb); // follows the soft link to the target int lstat(const char *path, struct stat *sb); // information about the LINK itself int fstat(int fd, struct stat *sb); // by an open file descriptor
- All three return an int (0 or β1) and they fill a
struct statthat you give them. (The exam key once says they "return a pointer to struct stat" β but remember the real form.) lstatgives information about the soft link itself, not about the target. This is the key difference.statandfstatgive the same information for a normal file (one by path, one by fd).struct statfields:st_mode(type + permissions),st_ino(i-node number),st_dev,st_size, β¦- Type macros on
st_mode:S_ISREG,S_ISDIR,S_ISLNK,S_ISCHR,S_ISBLK,S_ISFIFO,S_ISSOCK.
List a directory: opendir / readdir / closedir
DIR *opendir (const char *path); // returns a DIR* stream, or NULL struct dirent *readdir (DIR *dp); // ONE entry each call; NULL at the end or on error int closedir(DIR *dp);
opendirreturns aDIR*(not astruct dirent*).readdirgives one entry each time you call it. You call it again and again until it returnsNULL.NULLmeans the end OR an error (not "only when the directory is empty").struct direnthas the i-node number (d_ino) and the name (d_name).
Move and create
char *getcwd(char *buf, int size); // the current directory int chdir (const char *path); int mkdir (const char *path, mode_t mode); int rmdir (const char *path); // only if the directory is EMPTY
FALSE traps: "
readdir returns all entries as a list", "readdir returns NULL only when empty", "opendir returns a struct dirent*", "lstat gives information about the target", "these calls can list a directory" (only opendir/readdir can).8How to read an ls -l line π‘ sometimes
Read the fields from left to right:
-rwxr-xr-- 1 user3 user3 9876 Feb 8 12:36 script.sh βββ¬βββ¬βββ¬β β β β β β β β β β β β owner group size time name β β β β others: r-- (the "1" is the link count ββ above) β β ββββ group: r-x β βββββββ owner: rwx βββββββββ type: - file, d directory, l soft link
- Three permission groups: owner / group / others, each with
rwx. On a file,xmeans "you can run it". On a directory,xmeans "you can enter it". - The number after the permissions is the hard-link count (a trap calls it "number of soft links").
- The size field is in bytes.
drwxr-xr-x, the sentence "the directory is executable by all users" was marked false, even though others have x. Think of x on a directory as "can enter", and do not trust the key 100% here.9Modern file systems βͺ rare β just read fast
| FS | Notes |
|---|---|
| FAT (12/16/32), exFAT | the linked/FAT family. FAT32 = 32-bit clusters; exFAT for USB/flash; VFAT adds long names. Simple, portable, no journaling. |
| NTFS | the Windows standard. Big sizes, journaling, encryption. Linux/macOS read it with drivers. |
| Ext / Ext2 / Ext3 / Ext4 | the Linux family. Ext2 = no journaling; Ext3 added journaling; Ext4 = bigger sizes + faster, still compatible. |
Journaling (NTFS, Ext3/4) writes changes like small transactions, so the file system can repair itself after a crash. That is all you need here.
10One-page trap sheet
Encoding
- Unicode contains ASCII Β· UTF-8 = 1β4 bytes & works with ASCII Β· UTF-16 does NOT work with ASCII.
- "Unicode = UTF-8" β Β· "ASCII variable length" β Β· "Unicode always 32-bit / 2-byte" β.
- Binary: not easy to read, can change on another computer; a number in ASCII vs binary has different bytes and size.
System calls
open()takes 2 or 3 parameters β "exactly 2" β and "exactly 3" β.read()returns BYTES (not objects, not bits). read/write are the same for file/screen/pipe.printfuseswrite.lstat= the link itself;opendirβDIR*;readdirβ onedirenteach call, NULL = end OR error.
Links
- Hard link = same i-node (same content, counter +1); soft link = a file with a path inside (size = path length, can break).
ln f1 f2; ln f1 f3β counter 3. You cannot hard-link a directory. Writing through a soft link can make the target again.
Allocation
- Contiguous = both internal + external fragmentation; biggest file = longest free run; needs first/best/worst-fit.
- Linked = no external fragmentation, pointer cost; FAT puts the pointers in one table.
- Indexed = no external fragmentation; biggest file = total free β 1 index block; UNIX i-node = 12 direct + single/double/triple indirect.
- Internal fragmentation = round up(S/B)Β·B β S, always less than one block. Directories have i-nodes too.