andrestc.com

Following my read of “The Linux Programming Interface”, I came across the concept of “file with holes” or “sparse files”. Those are files that try to use the file system more effectively by preventing it from using disk space when sections of the file are empty. The disk storage is only actually used when needed. Sparse files are really useful for backup utilities, disk images, database snapshots etc.

One way to create a sparse file is by using truncate:

$ truncate -s 10M testfile

We can check the apparent size of the file with the following command:

$ du --apparent-size testfile
10240 testfile

As stated on the man page for du, the apparent size is not the actual disk usage; it may be larger due to holes in sparse files, fragmentation, indirect blocks etc.

Now, let’s check for the actual disk usage:

$ du -h testfile
0 testfile

Note: the apparent size and the real disk usage for the file you created have the same value, your filesystem does not support sparse files. The archlinux wiki has a nice article about sparse files.

After introducing the topic, the “The Linux Programming Interface” book has an exercise on building a copy of the cp command that is able to create sparse files when the original file was sparse. The entire code for my implementation can be found here.

The real cp shell command has an heuristic to detect and keep the sparsity of the original file on to the target file (we can disable it with the flag sparse=never). Our cp copycat is going to be really simple: we will skip any ‘\0’ byte (that is how the holes are represented when reading file) by using lseek on the destination file.

Copying a file with holes

Surprisingly, while reading past the end of file results on and EOF error, writing past that does not result on an error. To create “holes” in a file, in c, all we need to do is use the lseek syscall to go beyond the end of the file.

First, let’s create a file with some content, followed by a hole and then some more content. This can be accomplished with the following c code:

#include <fcntl.h>
#include "tlpi_hdr.h"
#include "error_functions.c"
#include "get_num.c"

int main(int argc, char *argv[])
{
    int outputFd, openFlags;
    mode_t filePerms;
    off_t offset;

    if (argc < 2 || strcmp(argv[1], "--help") == 0)
        usageErr("%s file <text> hole-length <text>\n", argv[0]);
    
    openFlags = O_CREAT | O_WRONLY | O_TRUNC;
    filePerms = S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP |
                S_IROTH | S_IWOTH; /* rw-rw-rw- */

    outputFd = open(argv[1], openFlags, filePerms);
    if (outputFd == -1)
        errExit("open");

    if (write(outputFd, &argv[2][0], strlen(&argv[2][0])) != strlen(&argv[2][0]))
        errExit("failed to write whole buffer");

    offset = getLong(&argv[3][0], GN_ANY_BASE, &argv[3][0]);

    if (lseek(outputFd, offset, SEEK_CUR) == -1)
        errExit("lseek");

    if (write(outputFd, &argv[4][0], strlen(&argv[4][0])) != strlen(&argv[4][0]))
        errExit("failed to write whole buffer");

    if (close(outputFd) == -1)
        errExit("close output");

    exit(EXIT_SUCCESS);
}

To use this script simply invoke:

$ ./hole testfile "begin" 100000 " end"

This will create a file, “testfile”, write “begin” right at the start, skip 100000 bytes and write “ end” at that offset.

My implementation of cp can be viewed here, but the interesting part is the following code:

int i, holes = 0;
while ((numRead = read(inputFd, buf, BUF_SIZE)) > 0) 
{
    if (keepHoles == 1) {
        for (i = 0; i < numRead; i++) {
            if (buf[i] == '\0') {
                holes++;
                continue;
            } else if (holes > 0) {
                lseek(outputFd, holes, SEEK_CUR);
                holes = 0;
            }
            if (write(outputFd, &buf[i], 1) != 1)
                fatal("couldnt write char to file");
        }
    } else {
        if (write(outputFd, buf, numRead) != numRead)
            fatal("couldn't write whole buffer to file");
    }
}

If we go for the naive approach (without the -k flag), just writing to the output file the exact bytes read from the original file, we will create a dense file. By passing the flag -k, we are able to keep the sparsity of the original file by using lseek(2) syscall to skip the bytes represented by \0.

Running our cp implementation on our test file results in the following results:

$ ./cp testfile testfileDense
$ ./cp -k testfile testfileSparse
$ du -h testfile testfileSparse testfileDense
8,0K testfile
8,0K testfileSparse
100K testfileDense

Great! By using lseek we successfully kept the same disk usage on our copy file!

This blog post is part of a series of posts that I intent to write while reading “The Linux Programming Interface” to make sure I’m actually learning something, as a way to practice and to share knowledge.