39 Arrays

39.1 What an array is — when there are many of the same thing#

Before the syntax, let us see why arrays have to exist.

Say we handle the exam scores of a class of thirty students. With what we have learned so far, we would need thirty variables.

int score1, score2, score3, /* … */ score30;

To get the average we would have to write score1 + score2 + … + score30 out by hand. Loops (chapter 33) do not help — score1 and score2 are variables that merely have different names and have nothing to do with each other, so there is no way to say “the i-th score”. A thirty-first student means changing the code, and finding “student 17′s score” from a number typed by the user is impossible.

What we need is a way to use one name with a number attached. Mathematics already does this. We write a sequence as ${𝑎}_0,{𝑎}_1,{𝑎}_2,\dots$, and “${𝑎}_{𝑖}$” picks a different term depending on $𝑖$. There is one name, $𝑎$, and the subscript $𝑖$ decides which term it means. C’s array is exactly that.

int score[30];                /* thirty ints --- one name, score */
score[16] = 87;               /* the 17th student (numbering starts at 0) */
for (int i = 0; i < 30; i++)  /* we can say "the i-th", so a loop works */
    total += score[i];

C calls the number in the brackets a subscript, after the subscript of mathematics. What an array gives us comes down to three things.

We should also know from the start what C’s arrays do not give. The rest of this chapter and the next two build on this list.

• An array does not carry its own length. It loses it the moment it is passed to a function (“decay”, below).
• Nobody checks that the number is in range. score[30] and score[-1] compile and run. The result is “Accidents with arrays”, near the end of this chapter.
• Once fixed, the size does not change. Growing it at run time needs the dynamic allocation of chapter 46.

39.2 The rigorous definition — how the standard writes an array#

Now the same thing in the standard’s words. An array is defined as one of the type categories.

“ An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. The element type shall be complete whenever the array type is specified. Array types are characterized by their element type and by the number of elements in the array. An array type is said to be derived from its element type, and if its element type is T, the array type is sometimes called “array of T”.¹ ”

Unpack it phrase by phrase and most facts about arrays fall out of it.

“The count is part of the type” looks like a small line, but it comes back again and again. sizeof telling us the size of the whole array, &a + 1 jumping over the whole array (chapter 41), and the count vanishing in a function parameter all turn on this one fact.

This book asked the compilers what happens when the definition’s “nonempty” is broken. Both call an array of zero elements an extension.

gcc:   warning: ISO C forbids zero-size array ‘z’ [-Wpedantic]
clang: warning: zero size arrays are an extension [-Wzero-length-array]

39.3 Declaration and initialisation#

How to read int a[5]; is covered in detail in chapter 69, but for now this is enough — the name a is “an array of five int”. The size in the brackets must be an integer constant expression whose value is known at compile time, and it must be greater than zero. (With a variable, it becomes the variable length array we meet later.)

#include <stdio.h>

int main(void)
{
    int a[5] = {3, 1, 4, 1, 5};
    int sum = 0;

    for (int i = 0; i < 5; i += 1) {
        sum += a[i];
    }
    printf("sum: %d\n", sum);

    printf("a[2] = %d, *(a + 2) = %d\n", a[2], *(a + 2));

    int *p = a;                 /* the array name decays to the address of the first element */
    printf("sizeof a = %zu, sizeof p = %zu\n", sizeof a, sizeof p);
    return 0;
}

sum: 14
a[2] = 4, *(a + 2) = 4
sizeof a = 20, sizeof p = 8

int a[5] = {3, 1, 4, 1, 5}; — type, name, slot count, and brace initialisation. Access is a[i] and numbering starts at 0 (the first element is a[0], the last a[4]). Why count from 0 was already answered by the opening exchange — a[i] really means “the place $𝑖$ slots away from the start”, so the first element is zero slots away.

Initialisation comes in several forms, each with its own rule in the standard. One demo gathers them.

#include <stdio.h>

#define COUNT(a) (sizeof (a) / sizeof (a)[0])   /* real arrays only */

static void show(const char *label, const int *v, size_t n)
{
    printf("%-22s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d", v[i]);
    printf("   (%zu elements)\n", n);
}

static int counter[3];          /* static storage: 0 without an initializer */

int main(void)
{
    int full[5]    = {3, 1, 4, 1, 5};   /* all five slots written */
    int part[5]    = {3, 1};            /* the other three are 0 */
    int sized[]    = {2, 7, 1, 8};      /* size taken from the initializer */
    int marked[6]  = {[4] = 9, [1] = 2};/* designated initializers (C99) */
    int empty[4]   = {};                /* C23: empty braces, all zero */

    puts("[1] initializers");
    show("{3, 1, 4, 1, 5}", full, COUNT(full));
    show("{3, 1}", part, COUNT(part));
    show("[] = {2, 7, 1, 8}", sized, COUNT(sized));
    show("{[4] = 9, [1] = 2}", marked, COUNT(marked));
    show("{}", empty, COUNT(empty));
    show("static, no initializer", counter, COUNT(counter));

    puts("\n[2] the array type knows its size");
    printf("sizeof full    = %zu bytes\n", sizeof full);
    printf("sizeof full[0] = %zu bytes\n", sizeof full[0]);
    printf("COUNT(full)    = %zu\n", COUNT(full));

    puts("\n[3] no whole-array assignment: copy element by element");
    int copy[5];
    for (size_t i = 0; i < COUNT(full); i++)
        copy[i] = full[i];                  /* copy = full; is an error */
    show("copy of full", copy, COUNT(copy));

    puts("\n[4] the first element shares the array's address");
    printf("(void *)full == (void *)&full[0] : %d\n",
           (void *)full == (void *)&full[0]);
    return 0;
}

[1] initializers
{3, 1, 4, 1, 5}        3 1 4 1 5   (5 elements)
{3, 1}                 3 1 0 0 0   (5 elements)
[] = {2, 7, 1, 8}      2 7 1 8   (4 elements)
{[4] = 9, [1] = 2}     0 2 0 0 9 0   (6 elements)
{}                     0 0 0 0   (4 elements)
static, no initializer 0 0 0   (3 elements)

[2] the array type knows its size
sizeof full    = 20 bytes
sizeof full[0] = 4 bytes
COUNT(full)    = 5

[3] no whole-array assignment: copy element by element
copy of full           3 1 4 1 5   (5 elements)

[4] the first element shares the array's address
(void *)full == (void *)&full[0] : 1

The difference between the last two rows matters. Write just int a[4]; inside a function and those four slots hold whatever someone using that place before left behind. That is why the demo does not print a local array without an initializer — printing it is itself one kind of accident at the end of this chapter. Always initialise a local array. Where all zeros will do, = {} is enough.

There is also the form that initialises a character array with a string literal (char s[] = "hi";). Its rule comes with strings in chapter 43.

39.4 What arrays cannot do — assign, compare or return as a whole#

Here is the first wall people from other languages hit. A C array cannot be handled as a whole.

What the compilers actually say:

gcc:   error: assignment to expression with array type
clang: error: array type 'int[3]' is not assignable

gcc:   warning: comparison between two arrays [-Warray-compare]
clang: warning: array comparison always evaluates to false [-Wtautological-compare]

gcc:   error: ‘f’ declared as function returning an array
clang: error: function cannot return array type 'int[3]'

So how do we copy an array? Three ways. Move the elements one by one (the demo’s third group), move the bytes in one go with the library’s memcpy (chapter 80), or put the array inside a structure — a structure can be assigned as a whole, so the array inside is copied with it (chapter 47). To compare contents, compare element by element or use memcmp.

39.5 Counting elements and traversal#

An array’s element count lives in its type, so sizeof can get it out. Divide the whole size by the size of one element.

#define COUNT(a) (sizeof (a) / sizeof (a)[0])

The demo’s second group is that calculation — 20 bytes ÷ 4 bytes = 5. With this macro the size is written in one place (the declaration), and loops say i < COUNT(a). Changing the size means changing one place.

★ But use it only on real arrays. An array passed to a function is already a pointer, and the same expression gives a wrong value — this chapter’s parameter section and chapter 41 cover that accident. The draft of the next standard (C2y) has an operator _Countof that does this job.³ It cannot be applied to anything that is not an array, so the language closes off this macro’s trap.

The traversal idiom is this.

for (size_t i = 0; i < COUNT(a); i++)   /* from 0, up to "less than" count */
    use(a[i]);

All three parts mean something. Starting at 0 is because the first element is number 0, and ending with < (less than) is because the last element is number “count − 1”. Using size_t as the index type is because it is the type that holds sizes and counts (chapter 36). Get any one of the three wrong and you are on the way to the accidents at the end of this chapter.

39.6 Arrays and pointers — the truth about decay#

The latter part of the first demonstration (arr.c) is this chapter’s heart. Here we set out exactly the relationship that has caused the most confusion in C — arrays and pointers.

The rule: in most contexts an array’s name decays into “the address of its first element.” Put side by side what survives the decay and what is lost:

Figure 39.1 — The array a and its decayed &a[0] have the same address but different types — so how many elements there are disappears.

That is why int *p = a; is legal — a was read as the pointer value &a[0]. And the notation a[i] is itself sugar for *(a + i) — add an integer to a pointer and you get the address “$𝑖$ slots along, by that type’s size” (pointer arithmetic — chapter 38′s rules apply here), and dereferencing that is indexed access. The demonstration’s a[2] == *(a + 2) is the check.

39.7 There is no gap between one element and the next#

Before pointer arithmetic, one fact has to be nailed down. We just read a[i] as “the place $𝑖$ cells away from the start” — and that arithmetic only works if the cells are contiguous. They are, and not by convention: it is the standard’s definition itself, read at the start of this chapter. Its “contiguously allocated” is the basis.

Three things follow from “contiguously allocated”.

Here is where structs differ. A struct may have gaps between members (chapter 48), while an array has no gap between elements. So what happens to an array of structs? Since no gap is allowed between elements, the struct’s own size is rounded up with padding at the tail so that it is a multiple of its alignment. That story is told with a figure in chapter 48, once structs have been introduced.

39.8 Adding to a pointer is not ordinary addition#

We have just said that a[i] is *(a + i). Then what value, exactly, is a + 2? If it were “2 added to an address” it would be two bytes along; in fact it is two int slots along, that is eight bytes. Pointer arithmetic moves by multiplying by the size of the type pointed at.

Figure 39.2 — The distance +1 moves a pointer is the size of the type it points at.

Set down exactly, the rule is this.

★ And that table is all there is. There are exactly four shapes in which a pointer may take part in addition or subtraction; everything else is an error the compiler must diagnose. The standard nails it down as a constraint.

“ For addition, either both operands shall have arithmetic type, or one operand shall be a pointer to a complete object type and the other shall have integer type. …

For subtraction, one of the following shall hold: both operands have arithmetic type; both operands are pointers to qualified or unqualified versions of compatible complete object types; or the left operand is a pointer to a complete object type and the right operand has integer type. (§6.5.7) ”

★ Note the asymmetry between addition and subtraction. 5 + p is fine but 5 - p is not, because addition asks only that “one operand is a pointer” while subtraction says “the left operand is a pointer”. The meaning makes it clear: “five slots along from this address” makes sense; “five minus an address” does not.

This book asked the compiler and confirmed it. Each of the four forbidden shapes is refused like this.

The last two follow from the clause’s phrase “a pointer to a complete object type”. void is not a complete type (chapter 27), and a function type is not an object type. Neither qualifies for arithmetic — gcc and clang allow byte-sized arithmetic on them as an extension, but -pedantic-errors turns it into an error.

So adding an integer to a pointer is not “adding a number to a number that is an address” but counting in slots. Only on a char * is 1 one byte; on an int * it is four, on a struct point * it is one whole struct.

/* Pointer arithmetic moves in "slots", not in bytes. */
#include <stddef.h>
#include <stdio.h>

struct point { int x, y; };

int main(void)
{
    char          c[4];
    int           a[8] = {0, 10, 20, 30, 40, 50, 60, 70};
    double        d[4];
    struct point  s[4];

    /* ── (1) the same +1, a different distance moved ─────────────── */
    printf("type           sizeof   (p+1) - p in bytes\n");
    printf("char           %2zu       %td\n",
           sizeof c[0], (char *)(c + 1) - (char *)c);
    printf("int            %2zu       %td\n",
           sizeof a[0], (char *)(a + 1) - (char *)a);
    printf("double         %2zu       %td\n",
           sizeof d[0], (char *)(d + 1) - (char *)d);
    printf("struct point   %2zu       %td\n",
           sizeof s[0], (char *)(s + 1) - (char *)s);

    /* to move by bytes, cast to a character pointer */
    int *p = a;
    printf("\np + 1        points at %d\n", *(p + 1));
    printf("(char*)p + 1 is the second byte of a[0]\n");

    /* ── (2) pointer subtraction gives a count of elements ────────── */
    ptrdiff_t gap = &a[4] - &a[1];
    printf("\n&a[4] - &a[1]        = %td  (elements, not bytes)\n", gap);
    printf("counted in bytes     = %td\n",
           (char *)&a[4] - (char *)&a[1]);

    /* ── (3) the subscript is sugar over the arithmetic ───────────── */
    printf("\na[3] = %d, *(a + 3) = %d, *(3 + a) = %d, 3[a] = %d\n",
           a[3], *(a + 3), *(3 + a), 3[a]);

    /* ── (4) one past the end may be formed, but never followed ───── */
    int *end = a + 8;                 /* one-past-the-end — legal */
    printf("\nelements up to the one-past-the-end address: %td (never dereferenced)\n", end - a);

    int count = 0;
    for (int *q = a; q != end; q++)   /* the standard idiom: stop at != end */
        count += (*q != 0);
    printf("non-zero elements: %d\n", count);
    return 0;
}

type           sizeof   (p+1) - p in bytes
char            1       1
int             4       4
double          8       8
struct point    8       8

p + 1        points at 10
(char*)p + 1 is the second byte of a[0]

&a[4] - &a[1]        = 3  (elements, not bytes)
counted in bytes     = 12

a[3] = 30, *(a + 3) = 30, *(3 + a) = 30, 3[a] = 30

elements up to the one-past-the-end address: 8 (never dereferenced)
non-zero elements: 7

The first block of output shows the whole rule. The same + 1 moves a different distance for each type, and the distance is exactly sizeof. So (char *)p + 1 and p + 1 point at different places — which is where the idiom of casting to a character pointer to move by bytes comes from (chapter 103′s views do this).

The second block is subtraction. &a[4] - &a[1] is 3, not 12 — pointer subtraction gives a count of elements, not of bytes. And that is why the result has type ptrdiff_t: subtracting a later pointer from an earlier one can be negative, so the type must be signed.

39.8.1 Three integer types that go with pointers — ptrdiff_t, intptr_t, uintptr_t#

Three integer types go with pointers. The names are close enough to mix up, but the three answer different questions.

★ The rule for telling them apart is simple.

ptrdiff_t is the result type of a subtraction. q - p has that type, and it is signed for the reason already seen: subtracting a later position from an earlier one gives a negative. Do not confuse it with size_t — “how many” is size_t, “how far apart” is ptrdiff_t (chapter 36). Even the conversions differ: %zu and %td.

intptr_t and uintptr_t have nothing to do with subtraction. All they promise is a round trip — “a valid void * put into this type and taken back compares equal to the original”. Nothing more. Doing arithmetic on the converted value and converting back is outside that promise, and chapter 38′s provenance applies.

ptrdiff_t d1 = q - p;                              /* in elements, inside the contract */
uintptr_t d2 = (uintptr_t)q - (uintptr_t)p;        /* in bytes, on the edge of it */

39.8.2 How far it may go — the contract of the arithmetic#

Chapter 38′s provenance applies to pointer arithmetic as it stands. Reduced to practical sentences:

“Outside the contract even when only formed” sounds strange, but it changes how loop conditions are written. p < a + n (or p != a + n) is safe because it only compares with the one-past-the-end address; p < a + n + 1 computes an address one further out and is outside the contract. p <= a + n will not do either — the body reads the one-past-the-end slot, and the p++ that follows forms a + n + 1. Sweeping backwards as for (p = a + n - 1; p >= a - 1; p--) is dangerous for the same reason — a - 1 is an address before the array, and it is outside the contract the moment it is computed.

for (int *p = a + n - 1; p >= a - 1; p--)   /* forms a - 1 — outside the contract */
    ...

for (size_t i = n; i-- > 0; )    /* stops when i is 0 — no address is formed */
    use(a[i]);

39.9 An array parameter is not an array#

There is one more rule in the position of a function parameter. Declare it as an array and the compiler turns it into a pointer. So the following three are completely identical declarations to the compiler.

void f(int *a);
void f(int a[]);
void f(int a[10]);   /* the 10 is documentation only; it is not checked */

For a multi-dimensional array only the outermost (leftmost) dimension is stripped. The inner dimensions remain part of the type.

void g(int m[3][4]);   /*  the real type is  int (*m)[4]  */
void h(int c[2][3][4]);/*  the real type is  int (*c)[3][4] */

There are three places where this fact becomes visible.

#include <stdio.h>

/* The three declarations are exactly the same thing to the compiler: all int *.
   (Applying sizeof directly to a parameter name makes gcc warn, so we take it
    into a local variable of the same type once and measure that.) */
static void by_ptr(int *a)     { int *p = a; printf("  int *a      : sizeof = %zu\n", sizeof p); }
static void by_arr(int a[])    { int *p = a; printf("  int a[]     : sizeof = %zu\n", sizeof p); }
static void by_size(int a[10]) { int *p = a; printf("  int a[10]   : sizeof = %zu\n", sizeof p); }

/* A parameter is just a pointer variable, so another address can be assigned to it */
static int second_of(int a[10])
{
    a = a + 1;          /* impossible for an array — an array name cannot be assigned to */
    return a[0];
}

/* Two dimensions: only the outermost (leftmost) dimension is stripped.
   int m[3][4]  ->  int (*m)[4] */
static void by_2d(int m[3][4])
{
    int (*p)[4] = m;    /* this is the parameter's real type */
    printf("  int m[3][4] : sizeof = %zu (a pointer), sizeof p[0] = %zu (one row)\n",
           sizeof p, sizeof p[0]);
    printf("                m[1][2] = %d\n", m[1][2]);
}

int main(void)
{
    int arr[10] = {0,1,2,3,4,5,6,7,8,9};
    int grid[3][4] = { {0,1,2,3}, {4,5,6,7}, {8,9,10,11} };

    printf("on the caller's side (real arrays):\n");
    printf("  int arr[10]    : sizeof = %zu\n", sizeof arr);
    printf("  int grid[3][4] : sizeof = %zu, sizeof grid[0] = %zu\n",
           sizeof grid, sizeof grid[0]);

    printf("inside the functions (all pointers):\n");
    by_ptr(arr);
    by_arr(arr);
    by_size(arr);
    by_2d(grid);

    printf("assigning to a parameter: second_of(arr) = %d\n", second_of(arr));
    printf("the original is untouched: arr[0] = %d\n", arr[0]);
    return 0;
}

on the caller's side (real arrays):
  int arr[10]    : sizeof = 40
  int grid[3][4] : sizeof = 48, sizeof grid[0] = 16
inside the functions (all pointers):
  int *a      : sizeof = 8
  int a[]     : sizeof = 8
  int a[10]   : sizeof = 8
  int m[3][4] : sizeof = 8 (a pointer), sizeof p[0] = 16 (one row)
                m[1][2] = 6
assigning to a parameter: second_of(arr) = 1
the original is untouched: arr[0] = 0

① The value of sizeof differs. On the caller’s side arr is a real array, so 40 bytes (ten ints), but inside the function it is 8 — the size of one pointer. So the idiom sizeof a / sizeof a[0] for counting elements does not work inside a function. The count must be received separately.

GCC does flag this mistake. Here is the diagnostic received when the example was first written.

error: ‘sizeof’ on array function parameter ‘a’ will return size of ‘int *’
       [-Werror=sizeof-array-argument]
note: declared here

② The parameter can be assigned to. An array’s name cannot appear on the left of an assignment, but a parameter is just a pointer variable, so a = a + 1 works. The example’s second_of does that — it moves the parameter along and reads a[0], yielding the original array’s second element — and the caller’s arr was not affected at all (exactly chapter 34′s copy-by-value rule).

③ A 2-D array parameter keeps only half its size information. sizeof p is 8 (a pointer) while sizeof p[0] is 16 — that is, the size of “one row” survives. It is because the inner dimension remains in the type, and that is what makes an access like m[1][2] compute correctly. Put the other way round, the size of the inner dimension must be written — int m[][] does not compile.

39.10 Arrays whose size is settled at run time — VLAs#

Every array so far had its size settled at compile time. C99 added one more — the VLA (variable-length array). A variable, not a constant, may be written in the size slot.

#include <stdio.h>

/* [static N]: the promise "an array of at least N elements comes here".
   It can be used only in an array declarator of a function parameter. */
static int sum3(const int a[static 3])
{
    return a[0] + a[1] + a[2];
}

/* A variable length array (VLA) as a parameter: take the size first, use it after */
static int sum_n(size_t n, const int a[n])
{
    int s = 0;
    for (size_t i = 0; i < n; i++) s += a[i];
    return s;
}

/* A two-dimensional VLA parameter — no computing indices by hand */
static int trace(size_t n, const int m[n][n])
{
    int s = 0;
    for (size_t i = 0; i < n; i++) s += m[i][i];
    return s;
}

int main(void)
{
    int fixed[3] = {1, 2, 3};
    printf("sum3        = %d\n", sum3(fixed));

    size_t n = 4;
    int local[n];                    /* a local VLA: its size is settled while running */
    for (size_t i = 0; i < n; i++) local[i] = (int)(i * i);

    printf("sizeof local = %zu bytes (= %zu ints)\n", sizeof local, sizeof local / sizeof local[0]);
    printf("sum_n       = %d\n", sum_n(n, local));

    int grid[3][3] = { {1,2,3}, {4,5,6}, {7,8,9} };
    printf("trace       = %d\n", trace(3, grid));
    return 0;
}

sum3        = 6
sizeof local = 16 bytes (= 4 ints)
sum_n       = 14
trace       = 15

There are two uses. The first is the VLA as a local variable (int local[n];), where an array whose size is settled at run time is allocated on the stack. That is also the only time sizeof is computed at run time — the example’s sizeof local returning 16 is the evidence. The second is the VLA as a parameter (const int a[n], const int m[n][n]), and this form is far more useful. Its value is greatest in two dimensions and above — you can write m[i][j] directly instead of computing m[i * n + j] by hand.

Local VLAs, however, are now generally not recommended in practice.

• Fail to control the size and the stack overflows. Use a number that came from input directly as a size and an attacker can bring down the stack, and there is no way to check for that collapse.
• There is no way to report failure. malloc at least returns null (chapter 46); a VLA simply collapses when there is no room.
• Its standing in the standard wavered too. Mandatory in C99, it became an optional feature in C11 (if __STDC_NO_VLA__ is defined, the implementation lacks it). MSVC does not support it.
• The Linux kernel removed VLAs from its entire codebase in 2018⁴ — predictability of stack usage and performance were the reasons.

So: use the VLA notation in parameters; avoid local VLAs. If you need an array whose size is settled at run time, chapter 46′s dynamic allocation is the proper method.

39.11 [static N] in a parameter — “at least this many will arrive”#

There is one more peculiar syntax used only in array parameters.

int sum3(const int a[static 3]);   /* a points at three or more elements */

Here static has nothing to do with storage duration (chapter 45). It means the contract “the pointer passed in this argument points at an array of at least N elements.” There are two benefits — the compiler may optimise on that premise (prefetching and the like), and it can warn about calls that pass null or a shorter array.

Two things to remember.

• The only place it may be written is an array declarator in a function parameter. It cannot go on a local variable or a struct member declaration. And for a multi-dimensional array it attaches only to the outermost dimension.
• Break the contract and you are outside it. sum3(nullptr) or passing a two-element array is undefined behaviour — meaning it is a promise, not a check.

39.11.1 [static 1] — writing “not null” into the declaration#

The most common form uses size 1.

void use(int a[static 1]);   /* a points at one valid object */

Saying “an array with at least one element” is the same as saying not a null pointer, and the object it points at is valid. Instead of a comment reading “do not pass null”, the promise sits in the declaration itself. That is why this spelling is used as the idiom for expressing non-nullness in a form a machine can read.

Tools really do read it. Here is what GCC 15 did while this book was being written.

static int sum1(int a[static 1]) { return a[0]; }
...
(void)sum1(NULL);

warning: argument 1 null where non-null expected [-Wnonnull]
note: in a call to function ‘sum1’ declared ‘nonnull’

“Declared nonnull” is the phrase that matters — the compiler treats [static 1] as a non-null attribute. With a size above 1 it looks at the length as well. Passing a two-element array to a const int a[static 3] parameter gets this:

warning: ‘sum3’ reading 12 bytes from a region of size 8 [-Wstringop-overread]

Still, it is a promise, not a check. No run-time test is inserted, and the compiler can only complain where it can see the problem — a literal null, an array of known size. Once the pointer has flowed through a few functions it usually says nothing at all. A call that breaks the promise is simply undefined behaviour.

39.11.2 A qualifier inside the same brackets qualifies the pointer#

The other thing that may go inside those brackets is a qualifier.

void f(int a[const 4]);      /* == void f(int *const a); */
void g(int a[restrict 4]);   /* == void g(int *restrict a); */

Here const attaches to the pointer itself, not to the elements it points at. It means a cannot be changed to point elsewhere inside the function; it does not mean a[0] is read-only. To protect the elements, the const goes outside the brackets, as in const int a[4].

static and a qualifier can be combined in the same brackets. The grammar allows both [static qualifiers N] and [qualifiers static N], so int a[const static 1] and int a[static const 1] are both valid — “points at one valid object, and the pointer itself cannot be reassigned.”

39.12 The boundary — the life-or-death rule#

An array’s safety rule is one and admits no compromise — valid subscripts run from 0 to the slot count minus one. Reading or writing a[5] (in a five-slot array) is outside the contract, and that slot is someone else’s memory — perhaps a neighbouring variable, perhaps the ledger of a function call we will meet in chapter 45. Read it and you get rubbish; write it and someone else’s data is quietly broken — the buffer overrun has caused more accidents and security vulnerabilities than anything else in C’s history (the next sections of this chapter are the accidents that arrays alone explain; those that involve strings continue in chapters 43–44).

There is exactly one place the standard specially permits at the boundary — as foreshadowed in chapter 38, making the address of the slot one past the end (a + 5) is legal (as long as you do not follow it). The traversal idiom relies on that:

for (int *it = a; it != a + 5; it += 1) { /* use *it */ }

Why does C not check the boundary? A check “at least 0, less than the count?” on every subscript would weigh down the innermost loops, and above all the language does not know the count to ask about — an array loses its length the moment it crosses a function boundary (the parameter section above). So checking was left to the programmer and the tools. The next sections show what happens when that responsibility is neglected.

39.13 Accidents with arrays — security and memory problems#

The accidents that arrays alone can cause fall into five kinds. Each breaks something different.

★ All five compile, and usually run. That is why a program that was fine in testing collapses only on particular input. For each kind this book checked what the compilers and sanitizers (chapter 18) notice (gcc 14, clang 19, x86-64 Linux).

39.13.1 ① One past the end — a single <=#

The most common shape is one wrong end condition.

int a[5] = {3, 1, 4, 1, 5};
for (int i = 0; i <= 5; i++)   /* "less than or equal" --- reads a[5] */
    sum += a[i];

Its nickname is the fencepost error. A 10-metre fence with a post every metre has eleven posts, not ten — the number of slots and the number of boundaries differ by one. In an array the difference is “five elements” versus “boundaries 0 to 5”.

Compiled and run without instrumentation, this code printed 14 with no trouble at all. There happened to be a 0 at a[5]. The tools say this about the same code.

gcc -O2 -Wall:
  warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
  note: within this loop

gcc -fsanitize=address, run:
  ERROR: AddressSanitizer: stack-buffer-overflow on address …
  READ of size 4 at … thread T0
    #0 … in main …:7
    This frame has 1 object(s):
      [32, 52) 'a' (line 4) <== Memory access at offset 52 overflows this variable

Read ASan’s last line. a occupies bytes 32 up to (not including) 52 of the frame (20 bytes, five ints), and the access happened at byte 52 — exactly one slot beyond. The warning appeared only with optimisation on (-O1 or higher), and clang 19 gave no warning for this shape. That is why we do not rely on warnings, but pair the habit of writing the end condition as < count with ASan.

39.13.2 ② Write overflow — covering the neighbour#

Bytes written past the end do not vanish. They cover whatever else was there. A real overflow is outside the contract, so its result cannot be shown in a demo; instead this book built a model that splits one big array into two “variables”, an 8-byte name and a 4-byte permission flag. Every access in the model stays inside one array, so it is within the contract.

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

/* A real overflow is outside the contract and cannot be demonstrated.
   So one big array is split into two "variables": an 8-byte name and a
   4-byte permission flag. Every access below stays inside frame. */
enum { NAME = 8, FLAG = 4 };
static unsigned char frame[NAME + FLAG];

static int flag(void)
{
    int f;
    memcpy(&f, frame + NAME, sizeof f);
    return f;
}

/* copies all it is given, never asks the size --- like strcpy */
static void copy_unchecked(unsigned char *dst, const char *src)
{
    while (*src)
        *dst++ = (unsigned char)*src++;
}

/* copies with the capacity of the destination */
static size_t copy_checked(unsigned char *dst, size_t cap, const char *src)
{
    size_t n = 0;
    while (src[n] && n < cap) {
        dst[n] = (unsigned char)src[n];
        n++;
    }
    return n;
}

int main(void)
{
    puts("[1] a short name stays inside its 8 bytes");
    memset(frame, 0, sizeof frame);
    copy_unchecked(frame, "kim");
    printf("flag = %d\n", flag());

    puts("\n[2] a long name runs into the neighbour");
    memset(frame, 0, sizeof frame);
    copy_unchecked(frame, "abcdefgh\x01");
    printf("flag = %d   <- nobody wrote to flag on purpose\n", flag());

    puts("\n[3] the same input, copied with the capacity");
    memset(frame, 0, sizeof frame);
    size_t n = copy_checked(frame, NAME, "abcdefgh\x01");
    printf("copied %zu bytes, flag = %d\n", n, flag());
    return 0;
}

[1] a short name stays inside its 8 bytes
flag = 0

[2] a long name runs into the neighbour
flag = 1   <- nobody wrote to flag on purpose

[3] the same input, copied with the capacity
copied 8 bytes, flag = 0

The second group is the point. A nine-byte name overflowed its 8-byte container and wrote 0x01 into the first byte of the permission flag, and flag, which nobody touched on purpose, became 1 (in little-endian order the first byte is the low end of the value — chapter 3). All a copy that never asks the length does is “write as much as it is given”; the size of the container is outside its view. Pass the size along, as in the third group, and the same input stays inside the container.

What lies right after an array in a real program is the compiler’s choice. For a local array it is other local variables, a canary the compiler planted (a value put there to notice an overflow), and further out the function’s return address. If that can be covered, an attacker decides where execution continues with nothing but input — we see that picture after learning the stack in chapter 45, and the history of the attack and its defences continues in chapter 44.

39.13.3 ③ Read overflow — memory that leaks out#

Overflowing a read breaks no data. So it hides longer. What is lost is not the integrity of the data but secrets — the values beyond the array go out with the output.

39.13.4 ④ Negative subscripts — half a check#

There is a shape that slips through even though there is a check.

int table[8];
void set(int i, int v)
{
    if (i < 8)          /* only the upper bound is checked */
        table[i] = v;
}

i is a signed integer, so when -1 comes in, -1 < 8 is true and it writes table[-1] — the 4 bytes just in front of the array. If the input is taken with something like atoi and passed straight on, it is a value an attacker can choose. This book ran it with -1.

gcc -fsanitize=address, run:      ok          <- caught nothing
gcc -fsanitize=bounds,  run:
  runtime error: index -1 out of bounds for type 'int [8]'

★ ASan missed it. ASan places poisoned memory (a redzone) after a global array and watches for a step on them, but the memory just in front of this array was other, ordinary memory without poison. It catches overflows to the back well, but misses an overflow to the front that lands in other ordinary memory. UBSan’s -fsanitize=bounds, on the other hand, knows the array’s type (int [8]) and compares the subscript directly, so it caught it. The two tools look at different things — which is why both stay on.

There are two cures. Check both sides (if (i >= 0 && i < 8)), or take the subscript as unsigned size_t. With the latter, -1 becomes a huge number and one i < 8 filters it out. The other traps at the spot where a signed value becomes an unsigned type were in chapter 30 — knowing where that conversion happens is the precondition.

39.13.5 ⑤ Uninitialised arrays — memory someone else used#

The initialisation table above said a local array without an initializer is indeterminate. Its slots still hold the bytes left by the function that used the same place before. Write that array to a file or send it over the network without filling it completely, and someone else’s values — sometimes pieces of a password or a key — go out with it. This is why such information leaks in the structures and arrays an operating-system kernel hands back to users are reported year after year.

We tested how much the compilers notice.

The last row is what happens in practice. When the filling function is in another file, the compiler cannot see what it fills. So the habit comes first — a local array starts with = {}. There is a safety net too. With gcc 12 and later and with clang, -ftrivial-auto-var-init=zero makes the compiler fill uninitialised local variables with zero. The Linux kernel lets this be switched on with one setting, to prevent such leaks altogether. But there is no guarantee that zero is the right value, so it is a device that hides bugs, not one that fixes them.

39.14 Layers of defence — what to switch on and what to make a habit#

No single measure stops all five kinds; it takes several layers. What one layer misses, the next one catches.

★ The higher the layer in the table, the cheaper; the lower, the later it catches. Compiler warnings and sanitizers see only the paths that testing went through, and the release-build safety nets stop an attack without fixing the bug. So the surest layer is the habit at the top — and turning that habit into a component is the work of this book’s Part XIII.

We can handle contiguous memory. Having learned decay you will be wondering whether an array and a pointer are ultimately the same thing; chapter 41 answers that question with rules — the whole picture forms only after multidimensional arrays. The next chapter stacks arrays — the case where the element is itself an array, that is, multidimensional arrays. What we learned here, “one step is one element”, applies unchanged; the element is just a whole row.