CS644 week 2: File I/O, part 2

Last week

Link: /week1

Review

• Concepts: Kernelspace and userspace, syscalls, the filesystem
• Syscalls: os.open, os.read, os.write, os.lseek, os.close

Solutions

• Duplicating a file: week1/duplicate.py
• Reading line-by-line: week1/line_by_line.py
• Simultaneous read/write: week1/simultaneous.py

Files, directories, and links

Linux distinguishes between several types of files:

• Regular file: A sequence of bytes. (Linux doesn't distinguish between binary and text files.)
• Directory: A listing of other files (which of course may themselves be directories).
• Symbolic link: A file that "points" to another file. Most syscalls follow symlinks by default, so if I create a symlink dir1/a that points to dir2/b, then calling open("dir1/a") will have the same effect as calling open("dir2/b").
  • If the original file is removed, then the symlink will be left dangling.
  • It's possible to create symlink loops. Trying to open or manipulate a symlink in a loop will return the ELOOP error.
  • Create a symlink with os.symlink.
• Hard link: Another kind of filesystem link, with some major differences from symlinks:
  • Hard links can't be left dangling; the file contents will be kept alive until all links to it are removed.
  • The hard link and the original file are completely identical, and in fact there is no "original" – the two are indistinguishable.
  • Creating a hard link to a directory is a bad idea as it can create filesystem loops.
  • Create a hard link with os.link.

In fact, hard links aren't really a different type of file – all regular files are effectively hard links. But normally we don't call them hard links unless we've created a second link to an existing file.

Under the hood: inodes

Within the kernel, files are represented by a data structure called an inode. The inode holds metadata about the file, and the location of the file's content on disk. (See man 7 inode for details.)

A directory is just a mapping from path names to inodes. Two path names can point to the same inode (this is what a hard link is). Only when the last path pointing to an inode is removed, will the underlying file contents be marked for deletion.

Other things can hold on to references to inodes, too, such as running programs. When you call open, the kernel will keep the file alive until you call close, even if another program deletes it.

So, the filesystem effectively has a reference-counting garbage collector. To extend the analogy further: symbolic links are like weak references and hard links are like strong references.

Try this:

touch test.txt
# make a hard link
ln test.txt test2.txt
ls -i test*.txt

ls -i will print the same inode number for the two files.

File permissions

Linux has inherited the classic file permissions model from Unix. There are three permission bits, each of which has a different meaning for regular files versus directories:

• Read
  • Files: can read from file
  • Directories: can list directory contents
• Write
  • Files: can write to file
  • Directories: can create, delete, and move entries
• Execute
  • Files: can execute as program
  • Directories: can "traverse", i.e. access paths within the directory

Owners and groups

Every file has an owner and a group. The three permissions (read, write, execute) can be separately set for the owner, the group, and everyone else. We can write a file's permission as a nine-character string, such as rwxr-xr-x, where the first three bits are the owner's permissions, the next bits the group's, and the last bits everyone else's.

Octal notation

Instead of a nine-character string, we can represent permissions more concisely as a three-digit octal number, for example 755. To break it down:

• 755 in octal is 111 101 101 in binary.
• So this is equivalent to rwx r-x r-x.
• Another way to remember is that r = 4, w = 2, and x = 1, so 7 = 4 + 2 + 1 = rwx.

Exercise: Copying a file tree

Exercise: Write a function copytree(inpath, outpath) that recursively copies the directory inpath and all files and directories underneath it.

You will need to use os.listdir or os.scandir (what's the difference?) to enumerate the entries in a directory.

This Python API is analogous to but slightly different from the C APIs, opendir which opens the directory for enumeration and readdir which returns one entry at a time. These C APIs are in turn wrappers around the underlying syscall, getdents, whose man page says "These are not the interfaces you are interested in."

To create a new empty directory, use os.mkdir.

To copy the files themselves, you can reuse the duplicate function that you wrote last week.

Follow-up

• Add a dry_run parameter. If true, then instead of actually copying, print the number of bytes that would have been copied. (Hint: Use the os.stat syscall and the stat module.)
• Copying files by calling read and write in a loop is inefficient, because every byte needs to be copied twice: from kernelspace to userspace (read) and from userspace back to kernelspace (write). Use the os.sendfile syscall to copy in-kernel. How much faster is it?
• Write a mirrortree function that creates a "mirror" of the source directory by hard-linking every file to the corresponding location in the destination directory, e.g., dest/a.txt is a hard link to src/a.txt. How much faster is it?

Exercise: Deleting a file tree

Exercise: Write a function rmtree(inpath) that recursively removes a directory and all its children.

Be careful to only run this on a test directory!

• os.unlink removes a file.
• os.rmdir removes an empty directory.

Follow-up

• What does your rmtree implementation do if the directory contains a symlink? Is there a security vulnerability? How can you fix it?

Final project milestone

Modify your program to create the database file with permissions locked down to the file's owner. Change your on-disk format to use multiple files: you can have one file per key, or do something fancier like allowing keys to have multiple parts such as a.b.c and store all a.* keys in the same file. Add commands to list all keys and to delete a key from the database.

Bonus material

• Changing a file's permissions, owner, and group: os.chmod and os.chown
• os.fsync ensures that any pending writes are flushed to disk. os.write returning successfully does not mean that the bytes were actually written to disk – the kernel buffers data to be written and flushes periodically. If you have your own Linux virtual machine, write an example program showing this is true.
  • You can crash the computer by running the shell command echo c | sudo tee /proc/sysrq-trigger (this won't work on the class server as students do not have sudo access). Be careful: this command can corrupt data elsewhere on the filesystem! Only run it on a virtual machine you don't care about.
• os.rename is the syscall to rename or move a file. It has the special property that the replacement of the target file is atomic. Demonstrate the use of rename to atomically overwrite an existing file, avoiding the partial writes we observed in last week's in-class exercise.
• "What file permissions does mv need?" by Ian Fisher
• "Torn Write Detection and Protection" by Alex Miller
  • This article is about partial writes at the storage level, while I believe the partial writes we observed were at the page cache level (i.e., in memory). Still interesting!