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