Arrays, Strings & Pointer Arithmetic

An array in C is the simplest possible data structure: a contiguous block of identically-sized objects in memory, laid out one after another with no gaps, no headers, no hidden metadata. When you write int arr[5];, the compiler allocates exactly 5 * sizeof(int) bytes. On a platform where int is 4 bytes, that is 20 consecutive bytes.

If the first element lives at address 0x1000, the elements live at: arr[0] → 0x1000, arr[1] → 0x1004, arr[2] → 0x1008, and so on. The address of element i is always base_address + i * sizeof(element).

This is not a coincidence — it is the defining property of an array. It means that subscript access is O(1) and requires only a single multiply-add-load sequence (which modern CPUs execute in one or two cycles). It also means the hardware prefetcher loves arrays, because access patterns are stride-regular.

The compiler knows all of this at compile time when the array size is fixed. It can sometimes eliminate the multiply entirely by converting arr[i] into a series of known offsets, or by using scaled addressing modes like [base + index*4] in x86 assembly.

#include <stdio.h>

int main(void) {
    int arr[5] = {10, 20, 30, 40, 50};

    /* Print the address and value of each element */
    for (int i = 0; i < 5; i++) {
        printf("arr[%d] at %p = %d\n", i, (void *)&arr[i], arr[i]);
    }

    /* Confirm: the gap between addresses is sizeof(int) */
    printf("Gap: %td bytes\n", (char *)&arr[1] - (char *)&arr[0]);
    return 0;
}

Here is the rule that unlocks everything else in this module:

In almost every context, the name of an array decays (is implicitly converted) to a pointer to its first element.

So if you have int arr[5], then in an expression context, arr becomes (int *)&arr[0] — a pointer of type int * pointing at the first element.

When does decay NOT happen?

1. When arr is the operand of sizeof: sizeof(arr) gives the full array size, not the pointer size.
2. When arr is the operand of the address-of operator &: &arr gives a pointer of type int (*)[5] — a pointer to the whole array.
3. In a string literal initializer: char s[] = "hello" copies the string, it does not decay.

This is why passing an array to a function causes you to lose the size information: the function parameter int *p receives only the pointer to the first element, not a copy of the array. The function has no way to know the length. This is why C standard library functions that operate on arrays (like memcpy, memset, write) always take an explicit length argument.

The decay is just a reinterpretation, not a copy. The array data never moves. You just get a lightweight pointer value pointing into it.

This is also why arr == &arr[0] is true (same address, same bit pattern), but arr and &arr have different types (int * vs int (*)[5]), even though they hold the same numeric address. The type is where all the arithmetic semantics live.

#include <stdio.h>

void show_array(int *p, int n) {
    /* 'p' is a plain pointer; sizeof(p) is 8 on 64-bit, NOT 20 */
    printf("sizeof(p) inside function = %zu\n", sizeof(p));
    for (int i = 0; i < n; i++)
        printf("%d ", p[i]);
    printf("\n");
}

int main(void) {
    int arr[5] = {1, 2, 3, 4, 5};

    printf("sizeof(arr) in main = %zu\n", sizeof(arr));  /* 20 */

    /* arr decays to &arr[0] when passed to a function */
    show_array(arr, 5);

    /* These three print the same address but have different types */
    printf("%p\n", (void *)arr);       /* int *       */
    printf("%p\n", (void *)&arr[0]);   /* int *       */
    printf("%p\n", (void *)&arr);      /* int (*)[5]  -- same address! */

    return 0;
}

When you add an integer n to a pointer p of type T *, the result is a pointer that points n elements forward — not n bytes forward. The compiler multiplies n by sizeof(T) for you automatically.

Formally: if p holds address A, then p + n holds address A + n * sizeof(*p).

This means:

• For int *p (where sizeof(int) == 4): p + 1 advances by 4 bytes.
• For double *p (where sizeof(double) == 8): p + 1 advances by 8 bytes.
• For char *p (where sizeof(char) == 1): p + 1 advances by exactly 1 byte.

The identity arr[i] == *(arr + i) is not just a shorthand — it is the definition of the subscript operator in C. The compiler literally rewrites every arr[i] into *(arr + i). This has a fun consequence: arr[i] and i[arr] are technically identical expressions (since *(arr + i) == *(i + arr)). This is legal C, though please never write it in real code.

Pointer subtraction is the inverse: p2 - p1 (where both point into the same array) gives the number of elements between them, as a ptrdiff_t. The result is again scaled by element size.

Valid arithmetic is only defined when the result pointer points within the array or to one past the last element. Arithmetic that takes you outside this range is undefined behavior — the compiler is free to assume it never happens, which can lead to miscompilation.

The char * type is special: because sizeof(char) is always 1, char * arithmetic moves one byte at a time, making it useful for raw memory manipulation (and why memcpy takes void * but internally casts to char *).

#include <stdio.h>

int main(void) {
    int arr[] = {10, 20, 30, 40, 50};
    int *p = arr;      /* p points to arr[0] */

    printf("*p       = %d  (arr[0])\n", *p);
    printf("*(p+1)   = %d  (arr[1])\n", *(p + 1));
    printf("*(p+4)   = %d  (arr[4])\n", *(p + 4));

    /* Walk with pointer increment */
    int *end = arr + 5;   /* one past the last element -- valid address */
    for (int *q = arr; q < end; q++) {
        printf("%d ", *q);
    }
    printf("\n");

    /* Pointer difference */
    int *mid = &arr[2];
    printf("mid - arr = %td elements\n", mid - arr);   /* 2 */

    return 0;
}

A C string is not a type — it is a convention. A C string is any contiguous sequence of char values where the last byte is the null character '\0' (ASCII value 0). The null byte is the sentinel that tells string functions where the string ends.

When you write a string literal like "hello", the compiler creates an anonymous array of 6 char values: {'h', 'e', 'l', 'l', 'o', '\0'}. The trailing '\0' is added automatically. The size of the storage needed for a string of n printable characters is n + 1 bytes.

Two common ways to store strings:

1. Array form: char s[] = "hello"; — the compiler allocates a 6-byte array on the stack and copies the literal into it. The array is mutable.

2. Pointer form: const char *s = "hello"; — s is a pointer to the string literal, which lives in a read-only segment of the binary. Attempting to write through s is undefined behavior (and typically a segfault). Mark it const.

All standard library string functions (strlen, strcpy, strcat, strcmp, strchr, ...) rely on the null terminator. strlen(s) just walks forward byte by byte counting until it hits \0. If you forget the null terminator, these functions walk off the end of your buffer — that is a bug.

The null terminator is not optional. It is not added for you by strncpy in all cases (a famous trap). It is not present in fixed-width records. You must track it carefully.

Note: char buf[5] = "hello" is a subtle bug — it stores {'h','e','l','l','o'} with no room for '\0'. The compiler may warn, some compile silently. The result is not a valid C string.

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

int main(void) {
    /* Array form: mutable, on the stack */
    char s[] = "hello";
    s[0] = 'H';                    /* OK: modifying the copy */
    printf("%s\n", s);             /* Hello */
    printf("len = %zu\n", strlen(s));   /* 5, not 6 */
    printf("size = %zu\n", sizeof(s));  /* 6 (includes \0) */

    /* Pointer form: do NOT write through it */
    const char *lit = "world";     /* points to read-only memory */
    /* lit[0] = 'W'; -- undefined behavior, likely segfault */

    /* Manual null check / iteration */
    for (const char *p = s; *p != '\0'; p++) {
        printf("'%c' at %p\n", *p, (void *)p);
    }

    return 0;
}

A buffer overflow happens when you write (or read) past the end of an array. Because C does not do bounds checking — the language standard simply says going out of bounds is undefined behavior — the compiler and runtime will happily let you overwrite adjacent memory.

Consider a stack frame that looks like this in memory (growing downward):

[  saved return address  ]  ← higher address
[  local variable 'auth' ]  ← 4 bytes above buf
[  char buf[8]           ]  ← 8 bytes

If you call gets(buf) (or any unchecked copy into buf) with input longer than 7 characters (plus null), the overflow overwrites auth, then the return address, and beyond. This is the classic stack smashing attack — and it is real. gets() was removed from C11 for exactly this reason.

The danger is proportional to what gets overwritten:

• Overwriting another local variable: logical bug, wrong output.
• Overwriting the saved frame pointer: corrupted stack unwind.
• Overwriting the return address: arbitrary code execution (classic exploit).
• Overwriting a function pointer: another code execution vector.

Why C lets this happen: C was designed for systems programming where bounds checking would be too expensive and too restrictive. The programmer is trusted to know their buffer sizes. This is a fundamental trade-off, not an oversight.

Modern mitigations (stack canaries, ASLR, non-executable stacks, CFI) make exploitation harder but not impossible. The kernel itself deploys all of these, and kernel security reviews explicitly look for buffer overflows.

Safe alternatives: fgets(buf, sizeof(buf), stdin), snprintf, strlcpy (BSD), or the length-aware functions in the kernel's own string library.

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

/* INTENTIONALLY VULNERABLE -- demonstration only, never use gets() */
void dangerous(void) {
    int auth = 0;
    char buf[8];

    printf("Enter name: ");
    /* gets() does NO bounds check. Input > 7 chars overflows. */
    /* gets(buf);  <-- do not compile and run this! */

    /* SAFE version: */
    if (fgets(buf, sizeof(buf), stdin) != NULL) {
        /* strip newline */
        buf[strcspn(buf, "\n")] = '\0';
    }

    if (auth) printf("Authenticated (this should never print!)\n");
    else      printf("Hello, %s\n", buf);
}

int main(void) { dangerous(); return 0; }

A 2D array in C is simply an array whose elements are themselves arrays. int m[3][4] is an array of 3 elements, each of which is an array of 4 ints. The total storage is 3 * 4 * sizeof(int) bytes, laid out completely flat in row-major order.

Row-major means row 0's elements come first, then row 1, then row 2:

m[0][0], m[0][1], m[0][2], m[0][3],
m[1][0], m[1][1], m[1][2], m[1][3],
m[2][0], m[2][1], m[2][2], m[2][3]

The address of m[i][j] is: base + (i * 4 + j) * sizeof(int). The compiler computes this for you from the declared dimensions.

Decay for 2D arrays: m decays to a pointer to its first row — a int (*)[4], a pointer to an array of 4 ints, not int **. This is different from a pointer to a pointer! Passing m to a function requires the function signature to declare the inner dimension: void foo(int m[][4], int rows) or equivalently void foo(int (*m)[4], int rows).

Cache performance matters here. Iterating with the last (column) index changing fastest (row-major traversal) is cache-friendly because adjacent elements are adjacent in memory. Swapping the loop order so the row index changes fastest (column-major traversal on a row-major array) causes a cache miss on almost every access — potentially a 10–100x slowdown for large matrices.

This is not academic: Linux kernel DMA scatter-gather table code, frame buffer operations, and many crypto routines care deeply about this distinction.

#include <stdio.h>

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

    /* Row-major traversal: cache-friendly */
    printf("Row-major traversal:\n");
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 4; j++)
            printf("%3d", m[i][j]);

    /* All elements are contiguous -- verify with pointer arithmetic */
    int *flat = &m[0][0];
    printf("\nFlat view: ");
    for (int k = 0; k < 12; k++)
        printf("%d ", flat[k]);

    /* Type of a decayed 2D array: pointer to row, NOT int ** */
    int (*row_ptr)[4] = m;   /* points to row 0 */
    printf("\nm[2][3] via row_ptr: %d\n", row_ptr[2][3]);  /* 12 */

    return 0;
}

These two declarations look similar but mean completely different things:

int *a[5];      /* array of 5 pointers to int   */
int (*b)[5];    /* pointer to an array of 5 ints */

The first, int *a[5], is an array of pointers. a itself is an array of 5 elements, each element being a pointer to int. Those pointers can point to completely different locations in memory — they do not need to be contiguous. This is the model used for argv in main(int argc, char *argv[]): argv is a pointer to an array of char * pointers, each pointing to a separate null-terminated string in different memory locations.

The second, int (*b)[5], is a pointer to an array. b holds the address of a single array of 5 ints. When you do b++, the pointer advances by 5 * sizeof(int) bytes — it jumps to the next array of 5 ints. This is the type you get when a 2D array decays.

The char *argv[] vs char **argv puzzle: In a function parameter, char *argv[] and char **argv are exactly equivalent — both decay to char **. But char *a[5] as a local variable and char **p as a variable are not the same: the first has storage for 5 pointers, the second is just a pointer.

This distinction is crucial in the kernel. argv-style pointer arrays (ragged arrays) allow variable-length strings. 2D arrays (int (*)[N]) allow direct row-stride arithmetic. Confusing the two leads to type errors, miscompilation, or subtle memory bugs.

Use cdecl (the tool or website) to decode complex C declarations — it is a normal thing to do, even for experienced engineers.

#include <stdio.h>

int main(void) {
    /* Array of pointers: each pointer is independent */
    const char *words[] = {"alpha", "bravo", "charlie"};
    for (int i = 0; i < 3; i++)
        printf("%s\n", words[i]);

    /* Pointer to array: b points to a whole row at once */
    int grid[3][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
    int (*row)[4] = grid;   /* points to row 0 */
    row++;                  /* now points to row 1 (advances 16 bytes) */
    printf("row 1, col 2 = %d\n", (*row)[2]);  /* 7 */

    /* sizeof contrast */
    printf("sizeof(words)     = %zu\n", sizeof(words));    /* 3 * 8 = 24 on 64-bit */
    printf("sizeof(*grid)     = %zu\n", sizeof(*grid));    /* 4 * 4 = 16 */

    return 0;
}

Once you understand pointer arithmetic, you can appreciate one of the most elegant macros in the Linux kernel: container_of. It appears thousands of times in the kernel source and is the backbone of the linked list, work queue, and many other subsystems.

The problem it solves: you have a pointer to a member inside a struct, and you want a pointer to the enclosing struct. The technique is pure pointer arithmetic.

#define container_of(ptr, type, member) ({
    const typeof(((type *)0)->member) *__mptr = (ptr);  \
    (type *)((char *)__mptr - offsetof(type, member)); })

What it does:

1. offsetof(type, member) gives the byte offset of member within type.
2. Cast ptr to char * (so arithmetic is byte-granular).
3. Subtract the offset to get back to the start of the struct.
4. Cast to type *.

This is possible because struct layout is deterministic and defined by the compiler (with possible padding, but offsetof accounts for that exactly).

The kernel's generic doubly-linked list (include/linux/list.h) uses this to embed a struct list_head inside any struct, then use container_of to recover the outer struct. You never need a void *data field — the list node is part of the payload struct.

Understanding this macro requires mastering: struct layout, sizeof, offsetof, pointer casting, and byte arithmetic — everything this module builds toward.

#include <stdio.h>
#include <stddef.h>   /* offsetof */

/* Simplified container_of (without GNU typeof extension) */
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

struct task {
    int   pid;
    char  name[16];
    /* In the kernel, list_head would be embedded here */
    int   list_next;   /* simplified placeholder */
};

int main(void) {
    struct task t = {42, "init", 0};

    /* Suppose we only have a pointer to the 'name' field */
    char *name_ptr = t.name;

    /* Recover the enclosing struct */
    struct task *recovered = container_of(name_ptr, struct task, name);

    printf("pid = %d\n", recovered->pid);    /* 42 */
    printf("name = %s\n", recovered->name);  /* init */

    return 0;
}