Introduction

Hello, and welcome back to CS631 "Advanced Programming in the UNIX Environment". In our last two video segments, we talked a lot about hard links, and we established that a hardlink is merely an entry in a directory. We also previously looked at the members of the struct stat, and noted that st_size represents the size of the file. So let's take a look at what this means for a directory.

File sizes

First, let's revisit what the 'size' for the other different types of files means: A fifo and a socket have a file size of '0', since they never contain any data. They are used as interprocess communications rendezvous points only; the kernel shuffles the data between the processes, and they never hit the disk. A regular file is easy: just count the bytes: three ascii characters and a carriage return. A symbolic link contains as its contents the path of the target, so in this case: slash wherever (no carriage return here) is nine. And for devices, ls doesn't even get a 'size' field, and instead shows us the device major and minor numbers.

Directory sizes

So let's take a look at directories now. To do that, we'll reuse the virtual disk we had previously added and start fresh with a new filesystem. We mount it under /mnt and chown it to our user. With nothing on this disk yet, we see that it is pretty much empty, with only a single 512 byte block being used. If we create a new directory on this disk, we see that the used block count increases -- we now have two 512 byte blocks in use. Looking at the output of 'ls', we see that directories appear to use 512 bytes: 'dir' at inode number 4832, which we created, has a size of 512 bytes, as do 'dot' and 'dot dot'. But wait: the disk shows that there are only two 512 byte blocks used, but here we count three - why is that? Well, take a look at the inode number of dot and dot dot: it's the same, meaning they are the same directory, and so we really only have two 512 byte blocks in use. But hold on. How can both 'dot' and 'dot dot' be the same? And what's even weirder, even though these two have the same inode number -- '2' -- , they have different owners and different link counts! So they are NOT the same directory, even though they have the same inode number. And this is because they exist on different devices -- remember, we mounted a new filesystem under /mnt. So we have data on disk /dev/wd1a under /mnt, where the root directory of _this_ filesystem has an inode number of '2', while the root directory of the filesystem mounted under / -- the root filesystem -- has an inode number of '2' as well. Hopefully this illustrates why we can't have hard links across filesystems and why a file is uniquely identified only by the combination of the device and the inode number. Oh, and one more weird thing: on the _root_ filesystem, both dot and dot dot in the root directory do point to the same inode. But that is the only instance of dot and dot dot pointing to the same directory, since only in the root do you not have a parent directory. Anyway, so let's get back to the directory size. An empty directory uses 512 bytes. Well, it's not really empty: it contains two entries, dot and dot dot, remember? So if we add a new file to this directory, it would stand to reason that the directory size would increase. Let's give it a try. Hmm, ok, so we created a third entry, but the directory size remains the same. Likewise if we add another file. But this isn't getting us anywhere like this. Let's try adding a few more files a bit quicker. Ok, here we add 40 files to the directory that already has two entries, so we have a total of 42 files. Why 42? Come on, you should know this! 42 is the answer to the big question about life, the universe, and everything! Anyway, let's see, how big is our directory now? Hmm, still 512 bytes. But all these files are zero length in size, maybe if we create a larger file? Let's make the file '3' 1 megabyte in size. 1 megabyte is larger than 512 bytes, so surely our directory size has got to increase now. ...and... it doesn't. Still 512 bytes. Ok, so maybe all directories are always 512 bytes in size? Let's just give it one more try and add a 43rd file. Oh, look at that! Now our directory is suddenly 1024 bytes in size! Can we add another 42 files? Looks like we can, and with 84 files, we are still within 1024 bytes. ...and if we add an 85th file, our directory increases again by 512 bytes to 1536 bytes. So perhaps every file in a directory takes roughly 12 bytes or so? Now 512 divided by 42 is not 12 even, but 12.19, but 43 times 12 equals 516, so we can only fit 42 files into a 512 byte directory (or 84 into a 1024 byte directory). Let's see what happens when we remove file number 85. Remember, that was the file that bumped the directory size from 1024 to 1536, so removing it should bring our directory size back down to... ... well, that didn't work. Our directory is still 1536 bytes in size. Let's remove a bunch of files more, to make sure. Here, now we only have 33 files left. That's fewer than 42, so should fit into a 512 byte directory. But... the directory remains 1536 bytes. In fact, even if we remove _all_ files in the directory, the size remains 1536 bytes. Ok. So it looks like: 1) directories can increase in size to accomodate more files than fit into it, but directories do not shrink in size when you remove the files 2) the file size does not affect the size of the directory the file is in 3) a directory entry takes up 12 bytes All the files we created so far had very short filenames. Even if file _size_ doesn't matter, wouldn't it make sense for the _filename length_ to make a difference? That is, would a directory entry that has a long filename also only require 12 bytes? Let's test this theory. Since our directory can't shrink, we nuke it and start fresh with a new 512 byte empty directory containing only dot and dot dot. Let's try to create a very long filename. Because we're lazy and don't want to have to type a really long filename ourselves, we use this little pipeline to generate a filename that's 1024 bytes long. Oh, huh, that filename is too long! As I mentioned in previous lectures, all things are finite. All resources are limited. So it makes sense that we can't just create an infinite-length filename, and it looks like our limit for a filename is less than 1024. So by trial and error, we determine that we can create a file with a name that's 255 characters long. That looks like so: And our directory size now is... 512 bytes. Let's create a second file with such a long filename. Then we have four directory entries: dot, dot dot, aaaa and bbbbb. And our directory size _now_ is... 1024. Which should make some sense: a directory entry must contain the filename, so if we have two filenames with 255 character filenames each, then we are already at 510 bytes, not accounting for 'dot' and 'dot dot' (which add at least three more bytes), and not accounting for the additional information a directory entry must provide: the inode mapped to the file. Ok, now removing these large files also doesn't shrink the directory, so that's consistent with the behaviour we saw earlier. But... _why_ doesn't the directory shrink?

Directory structures on disk

How does the filesystem actually organize the directory entries? To inspect that, we again start from scratch with a brand new filesystem on our disk. Ok, here we create three directory entries with variable length filenames, "file", "longer-filename", "third-file", and their inodes are shown as provided by our good friend 'ls'. Now, let's try to take a look at the internal structure of the directory. To do that, we're cheating a little bit here: We'll use the 'hexdump' utility to provide us with the hexadecimal representation of the bytes on disk. This works on this file system, but not all file systems let you read a directory; as we discussed in our last video segment, you normally should use the designated system calls. Anyway, what you see here, then, are the bytes on disk making up the directory, and you can see in it the filenames. Each directory entry is made up of: - 4 bytes for the inode in little-endian display We can use the bc(1) utility to easily convert numbers between different bases as shown here, so 25C0 in hex is 9664 in decimal. two bytes of directory entry length 0C hex is 12 decimal, meaning the _next_ directory entry will start at byte 13. And oh, look at that, here we have our 12 byte directory entry size that we determined earlier for shorter files! Let's keep an eye on the directory entry size here. one byte encoding the type of file with 4 representing a file of type directory one hex byte specifying the length of the filename And here, too, take note: the highest value a single hex byte can have is 'FF', which, in decimal, is 255 -- the maximum length of a filename that we observed earlier! So here, the first directory entry has a filename length of 1, and the next byte is exactly that filename: hex 2E is ascii '.' Now our filenames are padded on a four byte boundary, which then adds up nicely to the 12 bytes that the directory entry length told us this entry would be. So the second entry has inode number 2... ...is also 12 bytes long... ...is of type directory... ...has a filename length of 2, with the filename being 'dot dot', and the entry padded again to the 4-byte boundary. The third entry has inode number 9965... ...but is 16 bytes in length, not 12 ...is of type regular file... ...with a four byte length filename followed by NULL padding. The fourth entry has inode number 9966 is 24 bytes long is of type regular file and has a filename length of 15. The last entry has inode number 9967 but this entries length is 448 bytes! ... even though the filename length is only 10 bytes That is, the last entry spans the entire remainder of the directory. And with that, we're getting an idea of how the filesystem manages the directory: it uses the directory entry length to identify where the next directory entry begins; but if the filename length of the entry (plus padding) is shorter than the directory entry, then we have space to add a new entry at this point. Ok, let's roll with that for the time being. Now what happens when we remove a directory entry? Well, here we do just that, and then we inspect the directory again using hexdump(1). Note that even though we removed the directory entry, the filename is still there. In fact, all the bytes we had previously seen for 'longer-filename' are still in the exact same place. But I thought we removed the entry? And so we did. But removing a directory entry doesn't have to go and erase the data inside of the directory. All we need to do is update the previous directory entry's length to span the entry we just removed. So here, we see the directory entry length for 'file', which previously was 16, is now 40. The record was extended. Which is why our directory didn't shrink: The sum of the record lengths did not change. Instead, the record length of 'file' was increased, but with the NULL padding after the filename length, the data left in place is no longer used. Now what happens when we create a new file? Here, let's use a short filename -- 'shorty'. After we created 'shorty', the record length for 'file' shrunk again back to 16 bytes... ...and the newly created directory entry was added after 'file', overwriting the data that was previously used for 'longer-filename'. In fact, we can still see the remainder of 'longer-filename' left here, since 'shorty' is much shorter. And the directory entry length for 'shorty' is now 24 decimal. Again, the filename length prevents us from accidentally reading the garbage data left in place from the previous entry. When we remove 'shorty', the record length for 'file' jumps back up to 40 bytes, spanning 'shorty' and the older 'longer-filename'. So this worked out nicely, because 'shorty' did fit into the space that we had between 'file' and 'third-file'. Let's add another file, but one with a longer filename. As you see here, 'a-significantly-longer-name' doesn't fit in between 'name' and 'third-file', so the record length for 'file' remains unchanged. but the record length for 'third-file', which previously was 448 bytes, now shrunk to 20 bytes. and 'a-siginficantly-longer-name' is added at the end of the directory, with _its_ record length now spanning the remainder of the directory. Note that when we created this new file, we reused the inode number 9666: it was previously used for 'shorty', but now is used for 'a-significantly-longer-name'. This is a good reminder that while an inode does identify a file uniquely, you have no guarantee that a file by a given inode accessed at one time is the same when accessed another time, as inodes may be reused if they were previously unallocated. Ok, one more round: This time, we'll use really long filenames. Here, you see the 255 length filenames aaaa and bbbb. Since they didn't fit into the available space in between files, they were added. And since bbbbb bumps the total size over 512 bytes, the directory was extended to be 1024 bytes in size. Now if we remove aaaaa and then create a few shorter files, let's see where they end up: ccc fits into the slot of 'shorty' ddd fits right behind that one but eee does not fit right there, but we have a large hole here left from aaaaaa, so eee ends up right there with its record length being 392 bytes and ending where bbbbb begins. So in this way, we see why the directory does not shrink, and how it juggles the variable length directory entries.

Recap

Phew, that was some fine /toohexdump spelunking we did there, huh? Let's recap: For starters, directories are filesystem dependent, and different filesystems may implement them differently. On the Unix Filesystem (or the BSD variant, the Fast File System or FFS), they consist of a number of directory blocks, which for efficiency's sake are aligned on the physical blocksize of the disk. The size of a directory is independent of the sizes of the files in the directory, since it only contains the mapping of the filename to the inode, not the file data itself. But the directory size does depend on the length of the filenames in it, as we've seen and a directory may grow in size, but not shrink, due to the way it juggles the different entries of varying lengths. Now other filesystems may behave rather different, but perhaps you want to give it a try and find out how by running similar examples on, for example, the memory filesystem used on our reference VM for /tmp, on a macOS system or on the linux systems you have access to. When you do, pay attention to link count and size as you add / remove files; and see whether filename length changes directory entry size on those filesystems, too. But enough about directories - next time, we'll talk about a few system functions relating to file times, system identification and the like. Until then - thanks for watching! Cheers!