Merging Files Without Disk Space

Kerry Miles

A coworker recently presented me with a challenge: how can two files be merged when there is not enough space for cat part2 >>part1; rm part2 and no other filesystem can accommodate cat part1 part2 >>/another_fs/whole? I have been faced with this dilemma more than once, most frequently while manipulating log files or data exports. Barring wizardly manipulation of the inodes and indirect blocks that track which filesystem blocks belong to the files, I thought there was no way — but this time a solution dawned upon me.

Sparse Files

The solution relies upon sparse files, a rarely mentioned feature of UNIX by which a file can have a “hole” that does not take space from the filesystem. For a demonstration of sparse files, run these commands (this example assumes your filesystem block size is 4 KB):

echo "This is block 1" >testfile
echo "This is block 6" | dd bs=4k seek=5 of=testfile
du -sk testfile
ls -l testfile

If you examine the contents of “testfile” (try od -Cv testfile), the holes appear as a series of nulls. Many administrators learn about sparse files the hard way: when they attempt to restore files and they no longer fit into the filesystem. Since most commands, including cp, mv (to a different filesystem), tar, and cpio do not preserve sparseness, true null-filled blocks will replace the holes in files, causing them to consume more space. GNU tar’s -S option preserves sparseness, as may other alternatives in your environment.

An Overview of the Utility

The merge.pl utility works by reading the last block in file1, then truncating file1 to relinquish that block’s space. It then seeks past the end of file2 and writes the block from file1, leaving a hole large enough to fit the rest of file1. For example, if file1 is 4 blocks and file2 is 6, the utility will write the content of block 4 from file1 into block 10 of file2, leaving a hole in place of blocks 7, 8, and 9. By reading and truncating blocks from the end of file1 and writing them into file2, the hole is filled. Back to the example, block 3 from file1 would be written into block 9 of file2, 2 into 8, and finally 1 into 7. When file1 is empty, the merge is complete and file1 is removed.

The Gory Details

The utility begins with the assignment of two constants: $fs_bs and $my_bs. $fs_bs should be set to your filesystem block size; $my_bs is the size of the blocks that merge.pl will migrate. To improve performance, $my_bs is larger than $fs_bs and is a multiple of $fs_bs.

If fewer than 3 blocks are free in the filesystem, the way that UNIX keeps track of a file’s blocks can present a problem. The two files may require more space when combined than when separate! Since the dawn of journaled filesystems when fsck came to be like the Maytag repair man, some administrators have been able to forget about inodes and indirect blocks. For these lucky ones, here is a brief refresher.

The inode table is a fixed size, and blocks belonging to a small file are tracked exclusively by “direct pointers” in an inode within this table. As a file grows, a block of free space is taken to hold a “single indirect block”, which stores more pointers to the file’s blocks. When the file has too many blocks for a single indirect block, another free block is taken for a “double indirect block”, which holds pointers to blocks that in turn hold pointers to the file’s blocks. Implementations of this scheme vary greatly. For instance, of the systems that I tested, AIX’s jfs holds up to 8 direct pointers in the inode; Solaris’s ufs and Linux’s ext2fs hold the more typical 12. AIX relocates the direct pointers to the first single indirect block; Solaris and Linux do not. Some filesystems allow even larger files by using triple indirect blocks, adding one layer more of indirection than double indirect blocks; others support larger files using more efficient methods that involve fewer indirect blocks (in which case the logic in num_indirect() will err on the safe side).

The worst-case scenario is if a file with no indirect blocks is merged with one on the verge of requiring a triple indirect block. This will require 3 free blocks: the triple indirect block, pointing to a new indirect block, pointing to a new block for file pointers. If such a situation arises and the space is not available, the merge will be incomplete. Therefore, merge.pl first calculates how many indirect blocks are needed for file1 and file2, and how many will be needed for the merged file. It then adjusts for the block that would be saved if the last block of file1 and file2 were only partially used and could fit in one block. Finally, if it determines that more space will be needed by the merged file, it issues a warning. The utility could be enhanced to check how much space is free, but this test would not be portable (the available Filesys::DiskFree Perl module currently only supports 4 UNIX variants).

merge.pl then begins the real work of migrating the data from file1 to file2. Two subroutines are called upon. The first, get_block, checks whether this is the first time it has been called. If so, it adjusts the initial block size such that subsequent reads from file1 will be aligned with the block size, for performance. It then sets $f1_size to the the soon-to-be size of file1, seeks to that byte offset, reads the block, and truncates file1 to the new size.

get_block returns a reference to an anonymous hash containing the data and the offset at which it was read, which is pushed onto the array @buffered. When $num_buf has been reached, the anonymous hash references in @buffered begin to be shifted off and passed to put_block. put_block simply seeks in file2 to $f2_size (the original size of file2) plus the offset saved in the hash and writes the data. When file1 is empty, put_block is passed the remaining buffered data, and file1 is unlinked.

Using merge.pl

I have tested merge.pl with an AIX jfs filesystem, a Solaris ufs filesystem, and a Linux ext2fs filesystem, but most UNIX filesystems support sparse files. Testing was performed with Perl version 5.005_03; any 5.x version should suffice. You must have read and write access to both files, the files should not be in use, and your file size limit (reported by ulimit -a) must accommodate the combined file size. Most importantly, you should have a backup of the files! Since file1 is truncated as each block is added to file2, the files will be corrupt if the process does not complete.

As explained in the previous section, the filesystem block size ($fs_bs) and the indirect block calculation in the num_indirect() subroutine are system dependent. Their purpose is to predict whether additional space will be required for indirect blocks when the files are merged, in which case a warning is displayed. Verify that $fs_bs and the calculation are correct for your filesystem, or have at least 3 filesystem blocks free to be safe.

Of course, test the utility on your system before relying on it. A simple way to build files of a specific size for testing is with /dev/zero, which provides an endless supply of nulls. For example, the following dd commands will build a 700 KB and an 800 KB test file:

dd if=/dev/zero bs=1k count=700 of=file1
dd if=/dev/zero bs=1k count=800 of=file2

The command to append file1 to file2 is:

merge.pl file1 file2

merge.pl -spaceok file1 file2

About the Author

Kerry Miles is a Senior Systems Administrator for a major North Carolina health insurance company and has 10 years of UNIX administration and development experience. He can be reached at: kgmiles@usa.net.