Too Busy For Words - the PaulWay Blog

Tue 9th Feb, 2010

File system sequences

I recently had the occasion to create a new filesystem on a partition:

mkfs -T largefile4 /dev/sdc1

This creates copies of the superblock on a bunch of sectors across the disk, which can be used for recovering the superblock of the disk should something tragic happen to the main one (such as overwriting the first megabyte of a disk by accident). A useful tip here is that one can do the same command with the '-n' option to see what sectors it would write the superblock to, without actually reformatting the partition, in order to then provide a copy of a superblock to fsck:

mkfs -n -T largefile4 /dev/sdc1

In my case, these copies were written to these offsets:

Superblock backups stored on blocks: 
	32768, 98304, 163840, 229376, 294912, 819200, 884736, 1605632, 2654208, 
	4096000, 7962624, 11239424, 20480000, 23887872, 71663616, 78675968, 
	102400000, 214990848

What determines these magic numbers? Well, you can see from 163840 and 819200 that they're multiples of 32768. If we work out the multiples of the beginning offset for each offset, we get:

98304 = 3 * 32768
163840 = 5 * 32768
229376 = 7 * 32768
294912 = 9 * 32768
819200 = 25 * 32768
884736 = 27 * 32768
1605632 = 49 * 32768
2654208 = 81 * 32768
4096000 = 125 * 32768
7962624 = 243 * 32768
11239424 = 343 * 32768
20480000 = 625 * 32768
23887872 = 729 * 32768
71663616 = 2187 * 32768
78675968 = 2401 * 32768
102400000 = 3125 * 32768
214990848 = 6561 * 32768

Hmm. 3, 5, 7, eh? Then 9, which is 3 squared; then 25, which is 5 squared. Interesting. The 27 throws us for a second before we realise that that's 3 cubed, and it comes between 5 squared and 7 squared. And, sure enough, there's 81 (3^4) and 125 (5^3) ... it seems to be the sequence of successive square, cubes, etc. of 3, 5 and 7. It's a sequence of successive powers.

Why? Well, the whole object here is to make sure that a copy of the superblock survives if some tragedy happens to the disk. There are two broad kinds of disaster scenario here - destroying a contiguous block of disk, and destroying multiples of a specific sector offset across the disk (e.g. 0, 10, 20, 30, 40...). For the first, we can see the successive powers method quickly generates fairly large numbers without leaving any obvious large gaps - the ratio of number N and number N+1 never goes higher than 3. For the second situation, you can fairly quickly see from number factor theory that multiples of N will increasingly rarely intersect with the successive powers series, and only when N is (a multiple of) 105 will it intersect all three sequences.

It's perhaps arguable here that drive technology has made some of this irrelevant - ATA block replacement changes the mapping between logical and physical block numbers - and in fact the types of disaster scenarios this scheme of superblock copies addresses aren't really reflected in real-world usage. For example, if you're striping blocks across two disks then all your superblock copies are going to start on one disk (even if they then get striped across the second disk) because the successive power series always generates odd numbers. But as a way of avoiding some of the more obvious failure modes, it makes a lot of sense.

Another little bit of trivia explained.

Last updated: | path: tech / ideas | permanent link to this entry


All posts licensed under the CC-BY-NC license. Author Paul Wayper.


Main index / tbfw/ - © 2004-2016 Paul Wayper
Valid HTML5 Valid CSS!