5 ms·
I think it is easier. Split your source disk in: - directory blocks that describe the directory structure and, for each file, where to find this data on disk.
by Someone 9y ago
I think it is easier. Split your source disk in:
- 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)
- glandium 9y agoIt'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.
- tzs 9y agoYeah, 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).
- tzs 9y agoKind 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: cp file_1 > /dev/null cp file_2 > /dev/null ... cp file_N > /dev/null exec /path/to/netscape $* 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.