Exercises — Dynamic memory — malloc, calloc, realloc, free

Apply $\text{bytes}=n\times \text{sizeof(T)}$ term by term.

• a: sizeof(*a) = sizeof(int) = 4, so $10\times 4=40$ bytes.
• b: calloc(32, sizeof(char)) = $32\times 1=32$ bytes, and all set to zero.
• c: sizeof(*c) = sizeof(double) = 8, so $6\times 8=48$ bytes.

Note the contents: a and c are garbage (uninitialized), b is all zeros because it came from calloc.

1. malloc (fast, dirty memory)
2. calloc (cleared allocate)
3. realloc (resize, preserving contents)
4. free (return to the heap)

#include <stdlib.h>
 
double *d = malloc(n * sizeof(*d));   // 1. bytes = n * sizeof(double)
if (d == NULL) return 1;              // 2. malloc can fail -> must check
for (int i = 0; i < n; i++)           // 3. malloc gives garbage -> initialize
    d[i] = i / 2.0;
free(d);                              // 4. avoid a memory leak
d = NULL;                             // 5. avoid a dangling pointer

The two "safety steps" are the NULL check (step 2) and the d = NULL after free (step 5). Skipping step 2 risks dereferencing NULL; skipping step 5 leaves a dangling pointer that a later free(d) or d[0] would turn into undefined behavior.

int *freq = calloc(100, sizeof(*freq));
if (!freq) return 1;

calloc is correct because counters must start at zero — with malloc you'd have to add a memset or a loop. Total bytes: $100\times \text{sizeof(int)}=100\times 4=400$ bytes, all zeroed.

The bug is a use-after-free. After free(p), the three ints belong to the heap allocator again; p still holds the old address (its bits didn't change), so p[0] = 7 writes into memory the program no longer owns.

Failure mode: undefined behavior. The allocator may have already handed that block to another allocation, so your write silently corrupts someone else's data — or the allocator's own bookkeeping — producing a crash or a bug that surfaces far from here. Fix: free(p); p = NULL; — then p[0] = 7 becomes a clean NULL-dereference crash instead of silent corruption. A tool like Valgrind flags this instantly.

On failure, realloc returns NULL but leaves the old block untouched and still valid. The assignment overwrites v with NULL, so the address of the old (still-allocated) block is now lost forever — nobody holds it, so it can never be freed. That is a memory leak.

Fix — use a temporary, commit only on success:

int *tmp = realloc(v, cap * sizeof(*v));
if (!tmp) { free(v); return 1; }   // old v still valid -> free it, or keep it
v = tmp;                           // commit only when we know it worked

We grow only when len == cap (the buffer is exactly full), and each grow doubles cap.

Grows happen at len = 2, 4, 8, i.e. 3 grows, and cap goes 2 → 4 → 8 → 16. Final cap = 16.

When realloc moves the block, it must copy the old elements into the new one. The cost is dominated by those copies.

Doubling (1 → 2 → 4 → 8): grows copy 1 + 2 + 4 = 7 elements total (you copy the current contents each time you double). In general the sum $1+2+4+\cdots +n/2=n-1$, which is $O(n)$ — spread over $n$ pushes, that's $O(1)$ per push amortized.

Grow by +1 (1 → 2 → 3 → ... → 8): each of the 7 grows copies all current elements: $1+2+3+4+5+6+7=28$ copies. In general $1+2+\cdots +(n-1)=\frac{n(n-1)}{2}$, which is $O(n^2)$.

So doubling: 7 copies; +1 growth: 28 copies — and the gap widens fast as $n$ grows.

size_t overflow means count * 16 exceeds $2^{64}-1$ and wraps around modulo $2^{64}$. The product first exceeds the max when $16\times \text{count}\ge 2^{64}⟺\text{count}\ge \frac{2^{64}}{16}=2^{60}.$ So the smallest overflowing count is $2^{60}=1152921504606846976$. At that value, count * 16 = 2^{64}, which wraps to 0.

Danger: malloc(0) may return a tiny (or NULL) block, but the program thinks it has $2^{60}$ elements and writes far past the block — a classic heap buffer overflow, exploitable for code execution. This is why the multiplication must be validated before allocating.

(a) Whether calloc(count, size) detects overflow of count * size is implementation-defined. Glibc, musl, and most quality libcs do return NULL on overflow, but a conforming minimal implementation need not — so relying on it is non-portable.

(b) Portable check — verify the division inverts the multiplication:

void *safe_alloc(size_t count, size_t size) {
    if (size != 0 && count > SIZE_MAX / size)
        return NULL;                 // would overflow -> refuse
    return malloc(count * size);     // now provably safe
}

The test count > SIZE_MAX / size is true exactly when count * size would exceed SIZE_MAX. We guard size != 0 first because dividing by zero is undefined; if size == 0 there's nothing to overflow.

malloc = fast dirty bytes; calloc = zeroed bytes + the count × size split; realloc = grow/shrink preserving data (use a tmp!); free = give it back exactly once, then = NULL.

1. Check the return for NULL. 2. free exactly once, then set the pointer to NULL. 3. Use sizeof(*p) and a tmp variable for realloc.