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

$\text{bytes}=n\times \text{sizeof(T)}$ ko har term par apply karo.

• a: sizeof(*a) = sizeof(int) = 4, toh $10\times 4=40$ bytes.
• b: calloc(32, sizeof(char)) = $32\times 1=32$ bytes, aur sab zero set hain.
• c: sizeof(*c) = sizeof(double) = 8, toh $6\times 8=48$ bytes.

Contents note karo: a aur c garbage hain (uninitialized), b all zeros hai kyunki woh calloc se aaya hai.

1. malloc (fast, dirty memory)
2. calloc (cleared allocate)
3. realloc (resize, contents preserve karte hue)
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 fail ho sakta hai -> check karna zaroori hai
for (int i = 0; i < n; i++)           // 3. malloc garbage deta hai -> initialize karo
    d[i] = i / 2.0;
free(d);                              // 4. memory leak avoid karo
d = NULL;                             // 5. dangling pointer avoid karo

Do "safety steps" hain NULL check (step 2) aur free ke baad d = NULL (step 5). Step 2 skip karne se NULL dereference ka risk hai; step 5 skip karne se ek dangling pointer rah jaata hai jise baad mein free(d) ya d[0] undefined behavior mein badal deta.

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

calloc correct hai kyunki counters zero se start hone chahiye — malloc ke saath tumhe memset ya loop add karna padta. Kul bytes: $100\times \text{sizeof(int)}=100\times 4=400$ bytes, sab zeroed.

Bug use-after-free hai. free(p) ke baad, teen ints heap allocator ke paas wapas chali gayi hain; p abhi bhi purana address hold karta hai (uske bits nahi badle), toh p[0] = 7 us memory mein likhta hai jis program ka ab ownership nahi hai.

Failure mode: undefined behavior. Allocator shayad already us block ko kisi doosre allocation ko de chuka ho, toh tumhari write kisi aur ke data ko — ya allocator ke apne bookkeeping ko — silently corrupt kar deti hai — ek crash ya ek bug produce karta hai jo bahut door surface karta hai. Fix: free(p); p = NULL; — tab p[0] = 7 silent corruption ki jagah ek clean NULL-dereference crash ban jaata hai. Valgrind jaisa tool isse instantly flag karta hai.

Failure par, realloc NULL return karta hai lekin old block ko untouched aur valid chhod deta hai. Assignment v ko NULL se overwrite kar deta hai, toh old (still-allocated) block ka address ab hamesha ke liye kho gaya — koi bhi use hold nahi karta, toh use kabhi free nahi kiya ja sakta. Woh memory leak hai.

Fix — ek temporary use karo, sirf success par commit karo:

int *tmp = realloc(v, cap * sizeof(*v));
if (!tmp) { free(v); return 1; }   // purana v abhi valid hai -> free karo, ya rakhho
v = tmp;                           // sirf tab commit karo jab pata ho ki kaam kiya

Hum sirf tab grow karte hain jab len == cap (buffer exactly full ho), aur har grow cap ko double karta hai.

Grows len = 2, 4, 8 par hoti hain, yani 3 grows, aur cap jaata hai 2 → 4 → 8 → 16. Final cap = 16.

Jab realloc block move karta hai, usse old elements ko nayi jagah copy karna padta hai. Cost in copies se dominate hoti hai.

Doubling (1 → 2 → 4 → 8): grows copy karte hain 1 + 2 + 4 = 7 elements total (har baar double karte waqt current contents copy hote hain). Generally sum $1+2+4+\cdots +n/2=n-1$ hota hai, jo $O(n)$ hai — $n$ pushes mein spread karo, toh per push $O(1)$ amortized.

+1 grow karo (1 → 2 → 3 → ... → 8): 7 grows mein se har ek saare current elements copy karta hai: $1+2+3+4+5+6+7=28$ copies. Generally $1+2+\cdots +(n-1)=\frac{n(n-1)}{2}$ hota hai, jo $O(n^2)$ hai.

Toh doubling: 7 copies; +1 growth: 28 copies — aur jaise jaise $n$ badhta hai yeh gap tezi se barhta hai.

size_t overflow ka matlab hai count * 16 $2^{64}-1$ se zyada ho jaata hai aur $2^{64}$ modulo wrap around ho jaata hai. Product pehli baar max exceed karta hai jab $16\times \text{count}\ge 2^{64}⟺\text{count}\ge \frac{2^{64}}{16}=2^{60}.$ Toh sabse chhota overflowing count $2^{60}=1152921504606846976$ hai. Us value par, count * 16 = 2^{64}, jo wrap hokar 0 ban jaata hai.

Danger: malloc(0) ek tiny (ya NULL) block return kar sakta hai, lekin program sochta hai ki uske paas $2^{60}$ elements hain aur block ke bahut door likhta hai — ek classic heap buffer overflow, code execution ke liye exploitable. Yahi wajah hai ki multiplication ko allocate karne se pehle validate karna zaroori hai.

(a) Kya calloc(count, size) count * size ka overflow detect karta hai yeh implementation-defined hai. Glibc, musl, aur zyaadatar quality libcs overflow par NULL return karte hain, lekin ek conforming minimal implementation ko nahi karna padta — toh iske par rely karna non-portable hai.

(b) Portable check — verify karo ki division multiplication ko invert karta hai:

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

Test count > SIZE_MAX / size exactly tab true hota hai jab count * size SIZE_MAX exceed karta. Hum pehle size != 0 guard karte hain kyunki zero se divide karna undefined hai; agar size == 0 ho toh overflow kuch bhi nahi kar sakta.

malloc = fast dirty bytes; calloc = zeroed bytes + count × size split; realloc = data preserve karte hue grow/shrink karo (ek tmp use karo!); free = exactly ek baar wapas do, phir = NULL.

1. Return ko NULL ke liye check karo. 2. Exactly ek baar free karo, phir pointer ko NULL set karo. 3. realloc ke liye sizeof(*p) aur ek tmp variable use karo.