All posts
A scene from a medieval illuminated manuscript depicting Adam and Eve getting cast out of paradise.
Adam and Eve segfault after trying to access trees[-1];

Bounds checking in C

Everyone knows that there are no checks guarding against overflow in C. Can we change that? Of course! But can we change that in a way that is easy to implement and not a pain to use? Well, read on to find out.

Coming from TypeScript as my previous main language I wasn't overly concerned about bounds checking when I started with C. Initially I believed the situation to be similar as both languages allow array access at arbitrary indices and both return incorrect values outside of bounds. C however allows an incorrect access to corrupt memory which can have disastrous consequences.

To remedy this problem in some other way than being very careful when doing index access I looked around to see how other people approach the problem. Mostly I found people just switching to other languages, but I do like C and I feel quite confident in the choice of this language. Fortunately I have found Nic Barker's "Tips for C Programming" video which outlines one possible approach to the problem.

In the video Nic suggests that for every array type in our program we write an accompanying getter function that does the bounds checking. Here's how this could look:

// From Nic's video, modified slightly
typedef struct {
  int32_t* items;
  int32_t length;
  int32_t capacity;
} Int32Array;

int32_t Int32Array_Get(Int32Array array, int32_t index) {
  if (index >= 0 && index < array.length) {
    return array.items[index];
  }
  // Set breakpoint and return
  return 0;
  // Or use a platform specific trap
  raise(SIGTRAP);
}

void IterateItems(Int32Array array) {
  // The <= error will be caught
  for (int32_t i = 0; i <= array.length; i++) {
    int32_t item = Int32Array_Get(array, i);
  }
}

When confronted with the necessity of writing this piece of code for every array type in his program Nic shrugs it off saying it's not a big deal and pointing towards the possibility of code generation as a remedy.

Having to do extra work for every array in the program is something I very much wanted to avoid. Writing boilerplate doesn't scare me that much - the real issue is in how this would interrupt my train of thought every time I wanted to use an array for anything.

One day, I had a big insight about this problem. What if we put the bounds checking inside the square brackets? Take a good look at this piece of code:

i32 value = array[/* here! */ i];

If we replace i with some expression that performs the bounds checking the entire semantics of the array access stay untouched! Obviously the result of this expression has to be i, so the easiest thing to do is to introduce a function that returns i (isz is a machine sized integer).

static inline isz bounds_check(isz idx, isz len) {
  ASSERT(idx >= 0 && idx < len, "Out of bounds access");
  return idx;
}

Now we can begin using it. Obviously the need to state the length explicitly (for now) is bothersome, but we enjoy all the same semantics without introducing a function per type:

// Works with C arrays
i32 array[10] = {0};
array[bounds_check(i, 10)] += 3;

// As well as custom ones
typedef My_Array { My_Struct* ptr; isz len; isz cap; } My_Array;
My_Array my_array = /* ... */;
MyStruct* s = &my_array.ptr[bounds_check(i, my_array.len)];

We can make this more ergonomic still if we introduce some helper macros:

// This one is a fan favorite
#define countof(x) (sizeof(x)/sizeof(x[0]))
// But now for the real deal
#define IDX_L(a, i, l) (a)[bounds_check((isz)(i), (isz)(l))]
#define IDX(a, i)      IDX_L((a).ptr, (i), (a).len)
#define IDX_C(a, i)    IDX_L((a), (i), countof(a))

// With those we re-work our examples
i32 array[10] = {0};
IDX_C(array, i) += 3;

typedef My_Array { My_Struct* ptr; isz len; isz cap; } My_Array;
My_Array my_array = /* ... */;
MyStruct* s = &IDX(my_array, i);

I have been using this bounds checking mechanism ever since and now you can too! There is really minimal downside to this approach as the overall character count is almost the same as before and the ergonomics are identical.