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.
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,
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).