Memory Safety in Rust : A Safer C Implementation

main.c

#include "vec.h"

int main(void) {
  Vec* vec = vec_new();
  //vec is a pointer to a struct of an unknown type
  //so the compiler will not allow bugs 6 and 7 to occur.
  vec_push(vec, 107);
  vec_push(vec, 110);
  vec_free(vec);
}

vec.c

#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include <limits.h>
#include "vec.h"

// Vec is short for "vector", a common term for a resizable array.
// For simplicity, our vector type can only hold ints.
struct vec{
    size_t mark;     // Used to detect invalid objects
    int *data;       // Pointer to our array on the heap
    size_t length;   // How many elements are in our array
    size_t capacity; // How many elements our array can hold
};

static const size_t kVecMark = 0xfeedfacefeedfaceUL;
static const size_t kVecMarkFreed = 0xdeadbeefdeadbeefUL;
static const size_t kInitialCapacity = 16;
static const size_t kFreedCapacity = 13;

Vec *vec_new(void) {
    Vec *vec = calloc(1, sizeof(*vec));
    int *data = calloc(kInitialCapacity, sizeof(int));
    if (!vec) {
        return NULL;
    }
    if (!data) {
        free(vec);
        return NULL;
    }
    vec->data = data;
    vec->length = 0;
    vec->capacity = kInitialCapacity;
    vec->mark = kVecMark;
    return vec;
}

static bool check_nonnull_vec(Vec *vec)
{
    uintptr_t const value = (uintptr_t)vec;
    //malloc and calloc must return memory that is
    //aligned properly for all standard types.
    bool const valid_alignment = (value & 7) == 0;
    if (!valid_alignment) {
        return false;
    }
    
    if (vec->mark != kVecMark) {
        return false;
    }
    if (vec->data == NULL) {
        return false;
    }
    bool const over_initial = vec->capacity >= kInitialCapacity;
    if (!over_initial) {
        return false;
    }
    bool const valid_capacity = vec->capacity >= vec->length;
    if (!valid_capacity) {
        return false;
    }
    return true;
}

static bool check_vec_push_argument(Vec *vec)
{
    if (!vec) {
        return false;
    }
    size_t const max_capacity = SIZE_MAX;
    bool const can_add_capacity = vec->capacity < max_capacity;
    if (!can_add_capacity) {
        return false;
    }
    return check_nonnull_vec(vec);
}

void vec_push(Vec* vec, int n) {
    if (!check_vec_push_argument(vec)) {
        goto failure;
    }

    if (vec->length == vec->capacity) {
        size_t const new_capacity = vec->capacity * 2;
        if (new_capacity < vec->capacity) {
            goto failure;
        }

        //let cap = vec->capacity
        //(cap * 2) * sizeof(int) == cap * (sizeof(int) * 2)
        //Using the RHS instead of the LHS allows calloc
        //to detect overflow if a compiler removes
        //the previous check. Some compilers have
        //an option to make unsigned overflow undefined.
        int* new_data = (int*) calloc(vec->capacity, sizeof(int) * 2);

        if (!new_data) {
            goto failure;
        }
        
        for (size_t i = 0; i < vec->length; ++i) {
            new_data[i] = vec->data[i];
        }

        free(vec->data);
        
        vec->data = new_data;
        vec->capacity = new_capacity;
    }
    
    vec->data[vec->length] = n;
    ++vec->length;
    return;
failure:
    exit(EXIT_FAILURE);
}

void vec_free(Vec* vec) {
    if (!vec) {
        return;
    }
    
    if (!check_nonnull_vec(vec)) {
        exit(EXIT_FAILURE);
    }
    
    free(vec->data);
    vec->data = NULL;
    vec->mark = kVecMarkFreed;
    vec->capacity = kFreedCapacity;
    free(vec);
}

vec.h

#ifndef VEC_H
#define VEC_H
typedef struct vec Vec;
//public API of Vec which hides the internals
Vec* vec_new(void);
void vec_push(Vec* vec, int n);
void vec_free(Vec* vec);

#endif