Converting between different file systems in place is an interesting technical problem.
Let's say you have a disk that is formatted with filesystem S (for "Source"), and you want it change it to filesystem D (for "Destination").
Let's assume for now that S is not encrypted. Let's also assume that we have a fair amount of scratch storage available somewhere not on the disk we are trying to convert. (I'll address removing this requirement later).
One approach is to make something that given a list of files, including metadata, and a blank disk, can create a D filesystem on that disk and then copies the files to it.
You also need something that given a file on S can give you a list of the block numbers that hold that file's data.
That's an S to D copier, not an S to D in place converter, but it is useful for testing your understanding of D. Once you are confident that you know how D works, you can then make a new version of your D copier.
The new version doesn't actually write anything out to the blank disk. Instead, it writes instructions for making the disk out to a file in scratch space. For blocks that would hold metadata (e.g., inode blocks on Unix filesystem), it records in the scratch space what their content would be and where they would go on D.
For blocks that would hold file data, you write into the scratch area the list of where that data resides on S, and where that data would go on D.
What you end up with, then, in the scratch space is essentially a set of block by block instructions for copying S to a blank disk and ending up with a D filesystem, where instructions are either "copy block X from S to block Y of D" or "Fill block Y of D with the following literal data".
So to do an in place conversion, just follow those instructions, but with S and D the same, right?
NO!!!!! That would likely totally trash things, because it is quite possible that a source block in one instruction may have already been overwritten as a destination in an earlier instruction.
What you first need is something that goes through the whole list of block copy/fill instructions and figures out an order they can be done in that is safe.
It is possible that there is no such order. In that case, you also need some free space that can used for temporary storage. Given some free space you can always find an order for the block copy/fill that works.
The free space can either be on another device, or if S is not full you can find and use its free space.
Anyway, once you do all this, you end up with a simple list of data move/fill steps that will convert S to D in place. You just have to figure out how to actually execute them. The tricky case is when S is your system disk so you cannot un-mount it. Your OS might get very unhappy if you start converting it in place, and you also have to worry that it might write things to it in the middle of the conversion that could corrupt it.
Probably best would be to do the conversion booted from something like a Linux live CD.
I said earlier that you needed some separate scratch space to store the information for the new filesystem. If there is free space on S you can probably use that.
This comment is getting long, so I'm going to cut it off here. In a reply to it I'll toss in a couple of implementation tricks that can be useful, especially if D is a proprietary filesystem that you do not have a complete spec for and so cannot make your thing that figures out where to write D metadata and file data.
If you do not have a good spec for D, a kludge is to make a virtual disk driver. Make a blank D volume on that virtual disk. Then you can copy everything from S to D, except you replace the actual data for each file with blocks of the form: <signature> <block # on S> <some constant fill pattern>.
For each block written that does NOT match that pattern, your virtual disk driver actually does save the data somewhere. For blocks that do match that pattern, it just records what block on S they came from.
From the information gathered by the virtual disk driver you have enough information to construct a D file system from the S filesystem.
If you do not have an operating system that understand both S and D (common in dual boot scenarios), you can still do the above, but first you have to have a step where from the OS that understands S you run something that makes a pseudo dump of S. For example, a modified version of tar. This modified tar would act like normal tar, except instead of copying the actual file data, it would just make a list of disk blocks.
Then you switch to the OS that understands D, and you can use your virtual disk driver and the output from the modified tar to make the virtual D filesystem and gather the necessary information.
Note that this only has a chance if D does not care about the actual contents of files. If D does care, for example maybe it stores a checksum of the file in the metadata, then we are screwed because we do not have the original data in this scenario. Whether or not this can be worked around depends on just how much we know about D.
When you are ready to do the actual conversion, you face the question of where to run it. If S is not your boot volume, you might be able to get away with dismounting it and doing the conversion under your normal operating system.
When we were playing around with something like the above in the late '90s (part of a project considering making a PartitionMagic competitor, although we didn't get much past the experimenting stage before management decided the market was too small, PartitionMagic was too dominant in it, and their patent was scary and so cancelled the project) we were leaning toward using a Linux live CD (for everything, not just the actual copying).
You probably want the code that actually goes through the block copy/fill list and executes it to have some sort of fault tolerance that allows it to pick up where it left off if something interrupts it such as a power failure.
- directory blocks that describe the directory structure and, for each file, where to find this data on disk.
- data blocks that contain actual file data.
- free space.
Chances are you don’t need to touch the data blocks, and you have the free space as scratch space. All you have to do is to write a new set of directory blocks for the new disk format, and then delete the set of old directory blocks. If the on-disk format is flexible enough w.r.t. the location of directory and data blocks and you’re somewhat lucky, you can mostly write the new set of directory blocks in existing free space on the source disk.
That would lead to an intermediate state where the source disk still has the old format, but has one extra file that contains most of the new directory structure.
The final, risky part then is fairly small: overwrite the disk’s root blocks so that the system sees the disk as having the new file format with the new directory structure.
If the disk formats use different disk blocks as first starting points, you can even have a disk that can be used in either format (IIRC, that was possible with FAT and HFS. FAT has its master directory block in sector 0, HFS has it in sector 2)
It's possible to upgrade an ext4 filesystem to btrfs, and it's done the way you're describing. The end result is a btrfs filesystem containing the same file hierarchy, with a bonus: an additional raw file whose content is a disk image of the ext4 filesystem (pointing to the same blocks as the files), which allows a rollback.
Yeah, that would be a good approach if you have enough free space.
You could also have a preprocessing step where you rearrange files on the source disk so that the free space is arranged optimally for holding the directory structure for the new filesystem.
Speaking of rearranging files...another fun technical problem is doing a (mostly) portable disk defragmenter. Given one filesystem/OS dependent function,
block_addr * blocks_for_file(char * pathname)
which given a file returns a list of the addresses of the disk block addresses of the blocks that contain the file, and a filesystem/os dependent function that can set the metadata (ownership, permissions, etc) for one file to be the same as another file, you can write a defragmenter where everything else just uses portable functions, such as C stdio. It won't be quite as good as a defragmenter that knows filesystem internals and does low level writing directly to the disk, because the (mostly) portable defragmenter cannot easily move directory blocks around in a predictable way. Still, you can get most files defragmented.
You can first build a map from files to disk blocks with the blocks_for_file function. You can also map the free space by filling the free space with files and using blocks_for_file to map those. When filling the free space to map it, you should fill it with many one block files rather than a few large files, for reasons that will soon become apparent.
Then suppose you want to move fragmented file X to blocks B, B+1, B+2, ..., B+N-1, where N is the size of X in blocks. First you find all files that overlap [B, B+N-1]. For each file Y that you need to move out of the way you do as follows (remember, earlier we filled up all the free space with small files, so right now the disk is full):
1. Delete just enough of our free space filler files to free up enough space for Y.
2. Copy Y to Y.new, including copying ownership and permissions.
3. Delete Y.
4. Rename Y.new to Y
5. Fill up the space that was freed in step #3 with one block files.
After you have done this with each file that overlapped [B, B+N-1], all of those files now reside in the original free space, and [B, B+N-1] is covered with small files you created. You can now delete those files, leaving the disk with just enough free space to let you make a copy of X, which will end up in that free space and be consecutive. You can then delete the original X, and fill the newly free space with more one block files, and we are back where we started, but with X defragmented.
Repeat for every other file you need to defragment.
What I like about this approach is that you defragmenter doesn't have to know anything about how the underlying filesystem works.
Going the other way, defragmenting when you do know intimate details of the filesystem, there is also a very cool albeit probably impractical approach to defragmenting.
First, you figure out where everything currently is and where the free space is.
Then, you have to peek at the filesystem's in-memory data structures to find all the state that it keeps at runtime concerning allocation.
You need to know enough, and grab enough runtime data, that you can do all of the following:
1. Accurately predict where a file copy operation will place the new file,
2. Accurately predict how that will change the internal state,
3. Accurately predict how file deletion will change the internal state.
These all have to be good enough that given the state of the filesystem (on disk and in memory), you can look at proposed series of copies and deletes, and correctly predict what the final layout of the disk will be.
When you can do that, you can in theory then write a defragmenter that looks at the state of the disk and the in-memory state, decides how it would like the disk to be arranged, and then writes out a shell script that accomplishes that entirely with a long list of cp, rm, chown, and chmod commands (or the equivalent if you are not on a Unix or Unix-like system).
That portable defragmenter probably could run into problems because writing a single block file can take more than one block on disk (the file system may need extra directory block(s)). Instead of deleting the files, setting them to zero length might work better.
”and then writes out a shell script that accomplishes that”
You better use a different device for that.
Firstly, you don’t know how long that script will be, and its length will affect what commands to use.
Secondly, if you just make it long enough up front, it may occupy space that, at the end of its run, must store other data.
Here’s another even more impractical idea: if all you know is that your disk does first fit, can you write a program that, after whatever amount of disk I/O, defragments a drive? I think you can (ignoring blocks used to store directory information)
Kind of tangentially, the defragmenter stuff reminds me of another interesting thing you can do given low level information about layout and access. I'm not sure how much of the following is still applicable on modern filesystems and hardware. It was pretty effective back at the end of the 20th century and early 21st century.
Consider a program like Photoshop or a web browser. If you watch the I/O it does while starting there are a lot of cases where it opens some file, reads a few k, then goes and reads from a bunch of other files, and eventually comes back and reads more from that first sale.
It often happens that the data it reads from that first file is actually consecutive on the disk, but because it read it in two separate reads separated by many reads from other files it has to do a seek when it comes back for that second part.
This typically happens for many different files during a launch. Font files, dynamic libraries, and databases, for example.
If you make a record the I/O sequences during many launches of a given program you also find that they are mostly the same. There might be a few differences due to it making temp files, or due to differences in the documents you are opening on each launch, but there is also a lot of commonality.
At this point you can get clever. Make something that can tweak the I/O requests made during application launch. When a program starts launching, your tweak thingy can check to see if you have a log of a previous launch. If you do it can load that and then for each I/O during the launch it can predict if data beyond the extent of that particular read is also going to be needed. If so, it can add another read to grab that data, reading it into a temp buffer somewhere.
That might seem pointless, because the launching program is still going to come back and try to do a read from that same part of the file later. Yes, it will...but now the data from your early read might still be in the system's file cache, saving a seek.
I'm simplifying a bit. What you would do in practice is analyze the logs of the prior launches, identify which requests caused seeks, and then taking into account the size of the system's file cache and whatever you know about how the system cache works, figure out which reads should be extended and which should not be (because they don't incur extra seeks, or because their data won't hang around in the cache long enough).
Basically, you are preloading the cache based on your knowledge of what I/Os will be upcoming.
On Windows 98 doing this could knock something like 30% of the launch time for Microsoft Office programs, Netscape Navigator, and Photoshop.
I was curious once if this would work on Linux, probably around 2000 or so. I made some logs of Netscape launching by simply using strace to record all the opens and reads that occurred during a few launches.
I then identified several small files that had multiple reads during launch separated by reads of other files, and then make a shell script that just did something like this:
where file_1, ..., file_N were some of the files that had multiple interleaved reads during launch. I made no attempt to just read the parts that were needed (which could have been done with dd) as I just wanted a quick test to see if there was a hint that things could be sped up.
Launching netscape via my shell script turned out to be something like 10-15% faster than normal, if I recall correctly. I was surprised at how well it worked considering that doing it this way (do all the cache preloading up front) should result in fewer cache hits than the "preload the cache for each file the first time that file is accessed during launch" method.
Let's say you have a disk that is formatted with filesystem S (for "Source"), and you want it change it to filesystem D (for "Destination").
Let's assume for now that S is not encrypted. Let's also assume that we have a fair amount of scratch storage available somewhere not on the disk we are trying to convert. (I'll address removing this requirement later).
One approach is to make something that given a list of files, including metadata, and a blank disk, can create a D filesystem on that disk and then copies the files to it.
You also need something that given a file on S can give you a list of the block numbers that hold that file's data.
That's an S to D copier, not an S to D in place converter, but it is useful for testing your understanding of D. Once you are confident that you know how D works, you can then make a new version of your D copier.
The new version doesn't actually write anything out to the blank disk. Instead, it writes instructions for making the disk out to a file in scratch space. For blocks that would hold metadata (e.g., inode blocks on Unix filesystem), it records in the scratch space what their content would be and where they would go on D.
For blocks that would hold file data, you write into the scratch area the list of where that data resides on S, and where that data would go on D.
What you end up with, then, in the scratch space is essentially a set of block by block instructions for copying S to a blank disk and ending up with a D filesystem, where instructions are either "copy block X from S to block Y of D" or "Fill block Y of D with the following literal data".
So to do an in place conversion, just follow those instructions, but with S and D the same, right?
NO!!!!! That would likely totally trash things, because it is quite possible that a source block in one instruction may have already been overwritten as a destination in an earlier instruction.
What you first need is something that goes through the whole list of block copy/fill instructions and figures out an order they can be done in that is safe.
It is possible that there is no such order. In that case, you also need some free space that can used for temporary storage. Given some free space you can always find an order for the block copy/fill that works.
The free space can either be on another device, or if S is not full you can find and use its free space.
Anyway, once you do all this, you end up with a simple list of data move/fill steps that will convert S to D in place. You just have to figure out how to actually execute them. The tricky case is when S is your system disk so you cannot un-mount it. Your OS might get very unhappy if you start converting it in place, and you also have to worry that it might write things to it in the middle of the conversion that could corrupt it.
Probably best would be to do the conversion booted from something like a Linux live CD.
I said earlier that you needed some separate scratch space to store the information for the new filesystem. If there is free space on S you can probably use that.
This comment is getting long, so I'm going to cut it off here. In a reply to it I'll toss in a couple of implementation tricks that can be useful, especially if D is a proprietary filesystem that you do not have a complete spec for and so cannot make your thing that figures out where to write D metadata and file data.