On Wed, Dec 21, 2016 at 7:46 PM, Daniel Campbell <z...@gentoo.org> wrote: > > How does a file take up less than a single FS block? An inode has to be > allocated _somewhere_, does it not? >
So, the details are going to be filesystem-specific, but typically inodes go into some kind of area of the disk reserved for metadata, so that many of them can be stored in a single disk block. They're also fixed-length so storing them in groups lets you address them as an array. Likewise for directory trees, allocation tracking, and so on. In ext4 inodes are 256 bytes by default. So, obviously you can fit 16 of those in a single 4k disk block. 60 of those bytes are used to map the inode to the extents on the disk that contain the file's data. If the data within the file takes up less than 60 bytes then ext4 will store the data inside the actual inode itself since the mapping isn't actually needed in that case. That saves a whole block. Other filesystems do things differently. I don't profess to be a general expert, but I have read a fair bit on btrfs. Btrfs allocates spaces in b+ tree nodes that contain fixed-length records on one side (which would store things like inodes and other metadata records), and a heap full of variable-length records on the other. The latter can be used to store the content of small files. I believe btrfs can also use metadata space to store small regions of files as well (such as if you have a file that is just a few bytes larger than the next block boundary, or when you overwrite 1 byte of a large file which in btrfs does not get done in-place). The optimization of storing small bits of data without using entire blocks is a pretty common one. Another common optimization is dealing with large blocks of zeros in files. If you write a gigabyte of zeros in most filesystems it will certainly not take a gigabyte of space, even if the filesystem does not otherwise use compression. And of course you have stuff that consumes nothing but inodes, like links and device nodes and such. It isn't surprising that these optimizations are widespread on unix-like filesystems since small files for configuration/etc are so common. Not only does it save a ton of space, but it also saves a seek when the file is read. Finally, I'll just comment that if you're interested in brushing up on data structures, the documentation for any of the modern filesystems is a great thing to read up on. Since disk seeks are incredibly expensive but disks are very large a great deal of thought goes into how the data gets stored. -- Rich
