Tar implementation

Question

I am writing a tar implementation for education purposes and I started with reading from a tar file and printing the file content.

I use recursion for getting the next tar header and googled "When to use recursion?" Landed on this post where Peter Burns said:

There is a technique that language implementers can use called tail call optimization which can eliminate some classes of stack overflow. Put succinctly: if a function's return expression is simply the result of a function call, then you don't need to add a new level onto the stack, you can reuse the current one for the function being called. Regrettably, few imperative language-implementations have tail-call optimization built in.

Did he explicitly mean language implementers or can this be used by me too then?

As I was told to add the complete code so I will add what I got for now. It's not much because this is my first time working with a standardized format and I first want to be a able to read every header and get the offsets right, as tar pads content to next bigger blocksize.

It only works for tar file containing files only. I will implement all other kind of types if I understand more.

For now as already asked. Is the tar_getNextHeader() function badly designed regarding tail recursion and the quote above?

And I would like to improve my naming skills for structures, definitions because I think some structure and definitions are not nicely named.

Also if you see something I can do better or should not do/use, let me know.

tar.h:

#ifndef _TAR_H    // BEGIN INCLUDE GUARD
#define _TAR_H

/*********************************************************************************************************/
/*                                              DEPENDANICIES                                            */
/*********************************************************************************************************/

#include <stdio.h>

/*********************************************************************************************************/
/*                                               DEFINITIONS                                             */
/*********************************************************************************************************/

typedef struct tar tar;

/*********************************************************************************************************/
/*                                           FUNCTION DEFINITIONS                                        */
/*********************************************************************************************************/

tar* tar_load(const char *filename);
void tar_print(tar *tar);

#endif

tar.c:

/*********************************************************************************************************/
/*                                              DEPENDANICIES                                            */
/*********************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "tar.h"
#include "tar_internal.h"

/*********************************************************************************************************/
/*                                               DEFINITIONS                                             */
/*********************************************************************************************************/



/*********************************************************************************************************/
/*                                           FUNCTION DEFINITIONS                                        */
/*********************************************************************************************************/

/**
 * @brief Loads a tar file and parses/allocates included headers
 * NOTE: check for errno after calling
 * 
 * @param path path to tar file
 * @retval tar* on success
 * @retval NULL on failure 
 */
tar* tar_load(const char *path)
{
    struct stat fi;
    if(stat(path, &fi) != 0) {
        return NULL;
    }

    tar *tar = malloc(sizeof *tar);
    if(tar == NULL) {
        return NULL;
    }

    tar->size = fi.st_size;
    tar->filename = path;

    tar->fd = open(path, O_RDONLY);
    if(tar->fd == -1) {
        free(tar);
        return NULL;
    }

    tar->files = tar_getNextHeader(tar);

    return tar;
}

/**
 * @brief Prints file content (for testing purposes)
 * 
 * @param tar 
 */
void tar_print(tar *tar)
{
    lseek(tar->fd, 0, SEEK_SET);

    tar_entry *current = tar->files;

    while(current) {
        lseek(tar->fd, current->offset, SEEK_SET);
        char buffer[512];
        if(read(tar->fd, buffer, current->size) == 0) {
            printf("EOF\n");
            return;
        }

        printf("File: %s\n", current->header.filename);
        printf("Content:\n%s\n\n", buffer);

        current = current->next;
    }

}

tar_internal.h:

#ifndef _TAR_INTERNAL_H    // BEGIN INCLUDE GUARD
#define _TAR_INTERNAL_H

/*********************************************************************************************************/
/*                                              DEPENDANICIES                                            */
/*********************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include <errno.h>

#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <dirent.h>


/*********************************************************************************************************/
/*                                               DEFINITIONS                                             */
/*********************************************************************************************************/


#define NORMAL_FILE '0'
#define HARD_LINK '1'
#define SYMBOLIC_LINK '2'
#define CHARACTER_SPECIAL '3'
#define BLOCK_SPECIAL '4'
#define DIRECTORY '5'
#define FIFO '6'
#define CONTIGUOUS_FILE '7'
#define GLOBAL_EXTENDET_HEADER 'g'
#define EXTENDED_HEADER 'x'


/*

*/
#define TAR_BLOCKSIZE 512
#define USTAR "ustar"


typedef struct tar_header {
    union {
        struct {
            char filename[100];
            char mode[8];
            char uid[8];
            char gid[8];
            char size[12];
            char mtime[12];
            char chksum[8];
            char type;
            char link_filename[100];
            char magic[6];
            char version[2];
            char owner[32];
            char group[32];
            char devicemajor[8];
            char deviceminor[8];
            char prefix[155];
        };
        char padding[TAR_BLOCKSIZE];
    };
} tar_header;

typedef struct tar_entry {
    struct tar_entry *next;
    const char *filename;
    off_t offset;
    size_t size;
    tar_header header;
} tar_entry;

typedef struct tar {
    const char *filename; // tar filename
    size_t size; // tar file size
    tar_entry *files; // linked list
    size_t fd;
} tar;

/*********************************************************************************************************/
/*                                           FUNCTION DEFINITIONS                                        */
/*********************************************************************************************************/

size_t RoundUpBlock(size_t size, size_t blksz);

/*********************************************************************************************************/
/*                                           TAR HEADER INTERFACE                                        */
/*********************************************************************************************************/
bool tar_header_isUstar(tar_header *header);
void tar_header_setEmpty(tar_header *header);
bool tar_header_isDirectory(tar_header *header);
bool tar_header_isRegFile(tar_header *header);
bool tar_header_isLongName(tar_header *header);
bool tar_header_isLongLink(tar_header *header);
size_t tar_header_getSize(tar_header *header);
void tar_header_getPath(tar_header *header, char *path_buf, size_t len);


/*********************************************************************************************************/
/*                                             TAR FILE INTERFACE                                        */
/*********************************************************************************************************/

tar_entry* tar_getNextHeader(tar *tar);
int tar_skipFileContent(tar *tar, size_t filesz);

#endif

tar_internal.c:

/*********************************************************************************************************/
/*                                              DEPENDANICIES                                            */
/*********************************************************************************************************/

#include "tar.h"
#include "tar_internal.h"

/*********************************************************************************************************/
/*                                               DEFINITIONS                                             */
/*********************************************************************************************************/



/*********************************************************************************************************/
/*                                           FUNCTION DEFINITIONS                                        */
/*********************************************************************************************************/

bool tar_header_isUstar(tar_header *header)
{
    return ( strncmp(header->magic, USTAR, sizeof(USTAR)-1) == 0 );
}

size_t RoundUpBlock(size_t size, size_t blksz)
{
    size_t result = size % blksz;
    if( result == size ) {
        return blksz;
    }
    else if( result == 0 ) {
        return result;
    }

    return (size / blksz + 1) * blksz;
}

void tar_header_setEmpty(tar_header *head)
{
    memset(head->padding, 0, TAR_BLOCKSIZE);
}

bool tar_header_isDirectory(tar_header *head)
{
    return head->type == DIRECTORY;
}

bool tar_header_isRegFile(tar_header *head)
{
    return head->type == NORMAL_FILE;
}

/*
 always check errno for error after this call
*/
size_t tar_header_getSize(tar_header *head)
{
    return strtoul(head->size, NULL, 8);
}


/**
 * @brief skips the file content inside file and jumps to the next header
 * 
 * @param tar tar*
 * @param filesz size of file of the current header
 * @retval -1 on failure
 * @retval current offset in file in bytes 
 */
int tar_skipFileContent(tar *tar, size_t filesz)
{
    off_t curpos = lseek(tar->fd, 0, SEEK_CUR);
    size_t roundup = RoundUpBlock(filesz, TAR_BLOCKSIZE);

    if(curpos == -1) {
        return -1;
    }

    if(curpos + roundup > tar->size) {
        printf("DEBUG: TAR OVERREAD!!!\n");
        return -1;
    }

    if(lseek(tar->fd, roundup, SEEK_CUR) == -1) {
        return -1;
    }

    return curpos;
}

/**
 * @brief Recusive call to fill the linked list of entries
 * NOTE: alway check errno for this call. if errno == 0, and NULL is returned then EOF is reached, otherwise an error occured
 * NOTE: this function checks for ustar magic string to skip 0-byte sequences at the end of file, it does not work for tar files using the old standard
 * @param tar 
 * @retval NULL on failure (EOF or error while read)
 * @retval tar_entry *
 */
tar_entry* tar_getNextHeader(tar *tar)
{
    tar_entry *entry = malloc(sizeof *entry);
    if(entry == NULL) {
       return NULL;
    }

    size_t ret = read(tar->fd, &entry->header, TAR_BLOCKSIZE);
    if(ret == 0 || ret == -1) {
       goto CLEANUP;
    }

    if(!tar_header_isUstar(&entry->header)) {
       goto CLEANUP;
    }

    entry->size = tar_header_getSize(&entry->header);
    if(errno) {
        perror("tar_getNextHeader()->tar_header_getSize()");
        goto CLEANUP;
    }

    entry->offset = tar_skipFileContent(tar, entry->size);
    if(entry->offset == -1) {
        goto CLEANUP;
    }

    entry->next = tar_getNextHeader(tar);
    if(errno) {
        perror("tar_getNextHeader()->tar_getNextHeader()");
        return NULL;
    }
    return entry;

    CLEANUP:
    free(entry);
    return NULL;
}

Answer 1

What’s the Deal Here

Tail recursion is an extremely useful pattern. You’d normally use it to transform a loop into an equivalent function that calls itself. All the state that carries over from one invocation of the loop to the next becaomes arguments to the function. It can also decompose a larger function into smaller ones that return calls to each other. It’s especially useful to implement state machines.

The code that gets generated—if this optimization is enabled—is just as optimized as a loop. In fact, most functional languages don’t allow you to write loops at all, and replace them entirely with this technique.

Tail-call optimization works for all tail calls, not only tail calls to the same function, but it’s especially efficient to make a tail call to the same function, because then you can re-use the exact same stack frame. On a machine-code level, you can replace a call instruction and all the other overhead of a function call with a jump instruction.

I personally use this method a lot because I’ve done a lot of functional programming, and because it greatly facilitates a style of coding that protects you from certain kinds of bugs. Specifically, all your state that carries over gets fed into your function as const parameters, and all exit points are either the final value or a tail call. The entire state of the next trip through the function can only be updated all at once, at the same time. You can’t forget to set any of it, and you can’t set any of it twice on the same iteration. (Or actually, you can shoot yourself in the foot that way, because this is C, but you have to really be explicit about it. It won’t happen by accident.)

It does have some disadvantages: if there’s a lot of state (and you can’t refactor into smaller pieces that need less of it), the tail calls can get cumbersome. And some of it might be tramp data, which most of the functions it passes through don’t even use, just pass to the next function in the chain.

All modern C compilers can do the necessary optimization, but some need to be told to do it. GCC needs one of the optimization flags -O2, -O3, -Os or -foptimize-sibling-calls.

Clang and ICX have an extension, __attribute__((musttail)), that tells the compiler that a call must get this optimization. I therefore often write, for compatibility:

#if __clang__ || __INTEL_LLVM_COMPILER 
#  define MUSTTAIL __attribute((musttail))
#else
#  define MUSTTAIL /**/
#endif

This lets me write my tail-recursive calls as MUSTTAIL return, which expands to use this extension on the compilers that support it, or just return on those that don’t. (Annoyingly, I can only use it here if I return a function call from a void function, which is technically not legal. This doesn’t become an issue in functional programming, because functions with only side effects do not exist.)

Refactoring

So, let’s take as an example tar-print, which contains a while loop, and could therefore be refactored to use tail recursion:

/**
 * @brief Prints file content (for testing purposes)
 * 
 * @param tar 
 */
void tar_print(tar *tar)
{
    lseek(tar->fd, 0, SEEK_SET);

    tar_entry *current = tar->files;

    while(current) {
        lseek(tar->fd, current->offset, SEEK_SET);
        char buffer[512];
        if(read(tar->fd, buffer, current->size) == 0) {
            printf("EOF\n");
            return;
        }

        printf("File: %s\n", current->header.filename);
        printf("Content:\n%s\n\n", buffer);

        current = current->next;
    }

}

But First

Okay, before we go any further, stop and think about this:

        char buffer[512];
        if(read(tar->fd, buffer, current->size) == 0) {

This looks like a buffer overrun to me. Always, always, always check for buffer overruns in C. And I mean it.

Are you absolutely, positively certain that current->size can never be greater than the size of buffer? No, because buffer is initialized with a literal that is not in sync with the code that manages these data structures! There is a #define TAR_BLOCKSIZE that looks like it might be relevant, but it isn’t used here. if you had a good reason to believe this was safe when you wrote it—and I don’t see any comment or explanation why that would be—this code has no way to tell what changes there might have been to the other module, nor does anyone maintaining it have anything warning them to come back here and update the size of this buffer, too.

So if you really, truly, are sure that this code will never overrun the buffer and break everything—if you know for a fact that it is perfectly safe—put your money where your mouth is and write

assert(current->size <= sizeof(buffer));

What reason is there not to? Your code is safe, right? There’s no bug here. So that assertion will always pass. Right?

Setting Things up

All right, with that out of the way, let’s take a look at the program. This code needs "tar_internal.h". Since you’re using the POSIX API, it’s a good idea to request a specific version of it before you include any headers, with

#define _POSIX_C_SOURCE 200809L
#define _XOPEN_SOURCE   700

Technically, setting both is redundant, but it protects you from anyone else setting either to a value you didn’t expect.

You don’t check any of your system calls for errors. That C even lets people away with this was a terrible idea. I’ll throw in the boilerplate I often use for all system calls that set errno:

void fatal_system_error_handler( const char* const msg,
                                 const int err,
                                 const char* sourcefile,
                                 const int line )
{
    fflush(stdout); // Don't cross the streams!
    fprintf( stderr,
             "%s (%s:%d): %s\n",
             msg,
             sourcefile,
             line,
             strerror(err) );
    exit(EXIT_FAILURE);
}

#define fatal_system_error(msg) \
    fatal_system_error_handler( (msg), errno, __FILE__, __LINE__ )

I also change the type of fd, apparently an open file descriptor, from size_t to int, because that’s how you’re using it.

Finally, I include all the headers needed for this to work.

Refactoring the Function Itself

There’s a bit of initialization, followed by the while loop. In another language, we’d put the initialization in a wrapper function and turn the loop into a nested helper function. In C, we don’t have nested functions, so the helper becomes a static function in the same file.

The while loop itself has three pieces of state it uses: a local buffer, a file descriptor tar->fd, and a pointer to current. The buffer doesn’t need to persist between invocations, so it can stay as a local. The other two become function parameters. Since they never need to be modified in the middle of an iteration, they can become const.

So the signature of the helper function replacing the while loop could be:

static void tar_print_helper( const int fd,
                              const tar_entry* const current );

The initialization does two things: lseek to an offset of 0, and intialize current. Since we’re only keeping a copy of the fd field of tar around, we initialize both of these pieces of state by calling tar_print_helper from our refactored function, creatively called tar_print2:

void tar_print2(const tar* const archive)
{
    lseek(archive->fd, 0, SEEK_SET);
    tar_print_helper(archive->fd, archive->files);
}

You’ll notice that the final line is a tail call, which is to say, the last thing the function does before it returns. It’s not tail-recursive, because it’s not calling itself (or a function with the same type of arguments as itself). Compilers often can inline function calls like that and optimize them the same way as tail-recursive calls. In practice, compilers sometimes do and sometimes don’t.

What does the helper, which replaces the loop, look like? Recall, the loop looks like this:

    while(current) {
        lseek(tar->fd, current->offset, SEEK_SET);
        char buffer[512];
        if(read(tar->fd, buffer, current->size) == 0) {
            printf("EOF\n");
            return;
        }

        printf("File: %s\n", current->header.filename);
        printf("Content:\n%s\n\n", buffer);

        current = current->next;
    }

The refactored version looks like this:

static void tar_print_helper( const int fd,
                              const tar_entry* const current )
{
    if (!current) {
        return;
    }

    if ( (off_t)-1 == lseek(fd, current->offset, SEEK_SET) ) {
        fatal_system_error("Error seeking to offset");
    }

    char buffer[512];
    assert(current->size <= sizeof(buffer));
    const ssize_t read_result = read(fd, buffer, current->size);

    if (read_result < 0) {
        fatal_system_error("Error reading from file descriptor in tar_entry");
    }

    if (read_result == 0) {
        printf("EOF\n");
        return;
    }

    printf("File: %s\n", current->header.filename);
    printf("Content:\n%s\n\n", buffer);

    MUSTTAIL return tar_print_helper(fd, current->next);
}

Aside from one significant change to the code inside—actually checking for errors—only two things change. The loop condition becomes a test at the start of the function. (A do ... while loop would have it at the end instead.) And the update of current becomes a new call to the helper, with the new value of current as the second parameter. Because fd never changes, we can call it with the same value every time, and the compiler should notice that it never changes and optimize away any code to set it again.

What Does This Compile to?

This varies greatly. Clang 16.0.0 does not realize it can perform the tail-call optimization unless I specifically give it the MUSTTAIL directive although, once I do, it also recognizes that the non-tail-recursive call to it can be optimized away to a jump too. So this extension can sometimes improve the code considerably, even for functions that don’t make tail-recursive calls themselves.

ICX 2022 is based on a slightly-older version of the Clang backend, and has the same bug. GCC cannot do tail-call optimization on this code at all. Changing the function to return an int makes no difference here.

The problem here turns out to be declaring buffer as a local variable inside the helper. If I declare the buffer once, in the wrapper, and pass around a pointer to it, all three compilers become able to optimize it.

static void  tar_print_helper( const int fd,
                             const tar_entry* const current,
                             char buffer[TAR_BLOCKSIZE] )
{
    if (!current) {
        return;
    }

    if ( (off_t)-1 == lseek(fd, current->offset, SEEK_SET) ) {
        fatal_system_error("Error seeking to offset");
    }

    assert(current->size <= TAR_BLOCKSIZE);
    const ssize_t read_result = read(fd, buffer, current->size);

    if (read_result < 0) {
        fatal_system_error("Error reading from file descriptor in tar_entry");
    }

    if (read_result == 0) {
        printf("EOF\n");
        return;
    }

    printf("File: %s\n", current->header.filename);
    printf("Content:\n%s\n\n", buffer);

    return tar_print_helper(fd, current->next, buffer);
}


void tar_print2(const tar* const archive)
{
    char buffer[TAR_BLOCKSIZE];

    lseek(archive->fd, 0, SEEK_SET);
    return tar_print_helper(archive->fd, archive->files, buffer);
}

Another Example

I’ve written several solutions here that use tail recursion. Here’s one you might like.

Update: Error Handling

I’ll answer your question from the comments here.

I plugged in a piece of existing code I had, as a quick way to handle error codes (from library calls that set errno only!) You make a valid point that you don’t want a library to crash the program. You’ve thought about how this code should handle errors and what its requirements are, which is great! (Although, then, should it be sending messages to standard output, behind the application’s back?)

Indeed, some C coding standards forbid ignoring any return value, unless you explicitly write void. Some other languages, such as Rust, enforce this explicitly through its type system. Functions that might fail return a type that represents either an error or a valid result, and to use it for anything, you must unwrap it, and handle every case somehow (even if it’s just a runtime panic).

But your functions don’t report any errors, either, or return any information. They just return void. So, if there should be code elsewhere to recover or shut down more gracefully, how is any other code supposed to find out about them?

One classic approach is to return an error code. If you do this, be careful that the code for error is not also a valid return value! You might need to use a wider type for this; in this example, read() (in modern versions of POSIX) returns a ssize_t, or signed size type, rather that an unsigned size_t. This is so positive values can indicate success and negative values an error. Negative int values for error are the most common convention, because that’s how Dennis Ritchie and Ken Thompson did it. If you take this approach, all the if blocks that call fatal_system_error() would instead return -errno; (POSIX error values are positive) or maybe something like return (errno > 0) ? -errno : UNKNOWN_ERROR; to be sure.

A variation on this is to define your own enum type that lists every possible error code. This has the advantage that the compiler, and your debugger, remember the name. Otherwise, you might have to look through a header file to see that -2 is -ENOENT, and means file-not-found (“No such directory entry”). It also means that if you handle errors in a switch block with no default: block, and someone later adds a new kind of error, the compiler will alert you that you are no longer handling every possible condition.

Another possible solution that I’ve implicitly referred to would be to keep an error code in a global variable. And the standard library still, for historical reasons, is stuck doing something that isn’t actually that any more but is mostly backwards-compatible with it. But that’s something that’s been abandoned. There are many problems with it, one of which is that it’s not thread-safe.

There’s another great option in C++ and many other languages: you can throw an exception. Whatever handler is currently active will catch it, and any resources allocated through RIIA will be properly released. The downside is that exceptions aren’t appropriate for a critical path, because catching one is slow. They’re designed for exceptional events that mean the program has to stop what it was doing anyway.

A final approach that’s often used in C is to return a success/error code and take a pointer to a destination buffer as an output parameter. This is not something you would frequently see used with tail recursion, though, since recursive solutions usually want to chain and compose their functions.

Answer 2

The recursion here is not tail recursion.

A tail-call is one where no further processing is needed between the called function's return and that of the calling function (this means that the current function can just be substituted with the called function instead of creating a new stack frame).

In C, that looks like

return other_function(/*...*/);

or (for a function returning no value)

other_function(/*...*/);
return;

Anything else is not tail recursion.

For example, this factorial function is not tail-recursive:

unsigned int fact(unsigned int n)
{
    if (!n) return 1;
    return n * fact(n-1);
}

A tail-recursive implementation looks like this:

static unsigned int fact_acc(unsigned int n, unsigned int accumulated)
{
    if (!n) return accumulated;
    return fact_acc(n-1, accumulated * n);
}

unsigned int fact(unsigned int n)
{
    return fact_acc(n, 1);
}

In any case, C doesn't mandate that tail-calls be optimised in this way: some compilers will save your stack and some won't (and here, different compilers could quite possibly be the same compiler program, but invoked with different arguments!).