নিজের malloc বানানো — memory allocator-এর ভেতরে

১ · malloc জাদু নয় — একটি সাধারণ C কোড

পর্ব ২০-এ আপনি malloc আর free ব্যবহার করতে শিখেছেন। চাইলেন, জায়গা পেলেন; কাজ শেষে ফেরত দিলেন। কিন্তু একটি প্রশ্ন তখন খোলা রেখে এসেছিলাম — malloc-এর ভেতরে আসলে কী ঘটে?

malloc কোনো বিশেষ হার্ডওয়্যার বা অপারেটিং সিস্টেমের গোপন কৌশল নয়। এটি কারও লেখা সাধারণ C কোড। Linux-এ এটি থাকে glibc-এর ভেতরে। কোডটি অপারেটিং সিস্টেমের কাছ থেকে একবারে একটি বড় মেমরির এলাকা নেয়, তারপর সেটিকে টুকরো টুকরো করে আপনার প্রোগ্রামকে দেয়। এই কোডের নাম allocator.

এই ছোট গল্পেই allocator-এর চারটি মূল কাজ লুকিয়ে আছে:

এই পর্বে আমরা নিজেই একটি ছোট allocator বানাব। উদ্দেশ্য glibc-এর সাথে পাল্লা দেওয়া নয়। উদ্দেশ্য তিনটি জিনিস হাড়ে হাড়ে বোঝা: pointer আসলে byte-এর হিসাব ছাড়া কিছু নয়; alignment কেন বাধ্যতামূলক; আর use-after-free বা double free কেন এত ভয়ংকর — কারণ এগুলো allocator-এর নিজের খাতাই নষ্ট করে দেয়।

২ · মেমরি আসে কোথা থেকে — brk, sbrk আর mmap

Allocator নিজে মেমরি তৈরি করতে পারে না; তাকেও কারও কাছে চাইতে হয়। সেই “কেউ” হলো অপারেটিং সিস্টেমের kernel, আর চাওয়ার উপায় system call. পর্ব ২০-এর ভাবনার প্রশ্নে সংক্ষেপে দেখেছিলেন — allocator পাইকারি দরে বড় টুকরো কেনে, খুচরা বেচে। এবার পাইকারি বাজারটি একটু কাছ থেকে দেখি।

একটি গুরুত্বপূর্ণ সূক্ষ্মতা আছে। mmap বা brk সফল হলেই আসল RAM পাওয়া যায় না। Kernel শুধু virtual memory-র ঠিকানা বরাদ্দ করে। আপনি প্রথমবার কোনো page ছুঁলে একটি page fault হয়, তখন kernel আসল RAM-এর একটি ফ্রেম জুড়ে দেয়। System call আর page fault — দুটিরই খরচ আছে, তাই সব allocator OS-এর কাছে কম যেতে আর হাতে থাকা মেমরি বারবার ব্যবহার করতে চায়।

mmap-এর আরও অনেক রূপ (ফাইলকে মেমরির মতো পড়া, প্রসেসের মধ্যে মেমরি ভাগ করা) আসবে পর্ব ৫১-এ। এই পর্বে আমাদের ডেমো allocator কোনো system call ডাকবে না। সে কাজ করবে একটি static array-র ওপর:

static _Alignas(max_align_t) size_t heap[1024 / sizeof(size_t)];   /* আমাদের ১ KB-র “OS” */

কেন? এটি যেকোনো OS-এ একইভাবে চলে, আর ফলাফল প্রতিবার হুবহু এক — আমরা কাঁচা ঠিকানা না ছাপিয়ে array-র শুরু থেকে কত byte দূরে (offset), সেটি ছাপাব। তা ছাড়া allocator-এর আসল বুদ্ধি মেমরি আনায় নয়, ভাগ করায়।

৩ · দুটি নিয়ম — alignment আর block header

নিয়ম ১: সবচেয়ে কড়া alignment

পর্ব ২২-এ দেখেছেন, double সাধারণত ৮-এর গুণিতক ঠিকানায় বসতে চায়, আর struct-এর ভেতরে এজন্য padding বসে। malloc-এর সমস্যা আরও বড় — সে জানেই না আপনি block-এ কী রাখবেন। তাই C স্ট্যান্ডার্ড বলে, malloc-এর দেওয়া ঠিকানা এমন হতে হবে যাতে যেকোনো সাধারণ টাইপ সেখানে নিরাপদে বসতে পারে।

“সবচেয়ে কড়া alignment কত?” — এর উত্তর দিতে C11 একটি বিশেষ টাইপ এনেছে: max_align_t (<stddef.h>-এ)। _Alignof(max_align_t) বলে দেয় এই প্ল্যাটফর্মে সবচেয়ে বড় মৌলিক alignment কত। ৬৪-বিট Linux-এ (x86-64, GCC) এটি ১৬ — এই কোর্সের compiler-এ চালিয়ে আমরা নিশ্চিত হয়েছি। কারণ long double-এর মতো টাইপ ১৬ byte alignment চায়।

তাহলে কেউ ২৪ byte চাইলে আমরা আকারটিকে ১৬-এর পরের গুণিতকে গোল করব — ৩২. সূত্রটি ছোট, কিন্তু প্রায় সব allocator-এ পাবেন:

size_t rounded = (n + AL - 1) / AL * AL;   /* AL = 16: 24 → 32, 32 → 32, 1 → 16 */
/* AL দুইয়ের ঘাত হলে একই কাজ বিটে: (n + AL - 1) & ~(AL - 1) */

নিয়ম ২: প্রতিটি block-এর আগে header

এবার আকার মনে রাখার সমস্যা। সমাধানটি সুন্দর: allocator আপনাকে যে ঠিকানা দেয়, তার ঠিক আগে কয়েকটি byte নিজের জন্য রেখে দেয়। সেখানে লেখে block-এর আকার। আপনি free(p) ডাকলে সে p থেকে কয়েক byte পিছিয়ে header পড়ে নেয়। ব্যবহারকারী যে অংশটি পান, তার নাম payload.

আমাদের header-এর আকার রাখব ১৬ byte, যদিও আকার লিখতে লাগে মাত্র ৮ byte (একটি size_t). কেন? Header ১৬ byte হলে আর block-এর শুরু ১৬-এর গুণিতকে হলে payload-ও ১৬-এর গুণিতকে পড়বে — alignment-এর নিয়ম আপনাআপনি মানা হলো। বাস্তবের glibc আরও হিসাবি; সে বাড়তি জায়গা নষ্ট না করতে আরও চতুর বিন্যাস ব্যবহার করে।

Flag লুকানো — আকারের নিচের বিটে

Header-এ আরও একটি তথ্য লাগে: block-টি এখন ব্যবহার হচ্ছে, না খালি? এর জন্য আলাদা ঘর না বানিয়ে একটি পুরোনো কৌশল কাজে লাগানো হয়। সব block-এর আকার ১৬-এর গুণিতক — মানে বাইনারিতে আকারের নিচের চারটি বিট সবসময় 0. সেই অব্যবহৃত বিটের একটিতে “used” flag রেখে দিলেই হলো। পর্ব ৯-এর bit mask এখানে সরাসরি কাজে লাগে:

size_t h = 48 | 1;            /* আকার 48, used = 1  → h = 49 */
size_t size = h & ~(size_t)1; /* নিচের বিট মুছে আকার: 48 */
int used = h & 1;             /* শুধু নিচের বিট: 1 */

glibc-ও ঠিক এই ধারণা ব্যবহার করে — তার chunk-এর আকারের নিচের কয়েকটি বিটে কয়েকটি flag থাকে। আর বাস্তবের malloc আপনার চাওয়ার চেয়ে কিছুটা বেশি দেয়, সেটি চোখেও দেখা যায়। glibc-এর একটি নিজস্ব ফাংশন আছে, malloc_usable_size(p) — block-এ আসলে কত byte ব্যবহারযোগ্য, তা বলে। এই কোর্সের Linux compiler-এ চালালে পাওয়া যায়:

malloc(1):  usable=24
malloc(14): usable=24
malloc(27): usable=40
malloc(40): usable=40

১ byte চাইলেও ২৪ byte! কারণ glibc ৬৪-বিটে প্রতিটি chunk ন্যূনতম ৩২ byte রাখে, তার মধ্যে ৮ byte header. খেয়াল রাখবেন, malloc_usable_size শুধু glibc-এর (<malloc.h>), স্ট্যান্ডার্ড C-এর নয় — Windows বা Mac-এ এর নাম ও আচরণ আলাদা। আর বাড়তি byte-এ লেখা “বৈধ” মনে করে কোড লিখবেন না; চাওয়া মাপের বাইরে লেখা সবসময় ভুল।

৪ · First-fit allocator — খোঁজা আর ভাগ করা

সবচেয়ে সহজ কৌশল দিয়ে শুরু করি: first fit. Heap-এর শুরু থেকে একটি একটি block দেখো; প্রথম যে খালি block যথেষ্ট বড়, সেটিই দাও। যদি সেটি দরকারের চেয়ে অনেক বড় হয়, তাহলে ভেঙে দুই ভাগ করো — সামনের অংশ দাও, বাকিটা খালি রেখে দাও। এই ভাঙার নাম splitting.

নিচের heap-এ চারটি block আছে। সংখ্যাগুলো payload-এর আকার (byte); প্রতিটির আগে ১৬ byte header আছে, আর @-এর পরের সংখ্যা হলো header-এর offset. প্রথমে malloc(24), তারপর malloc(100) — “পরে” চেপে দেখুন allocator কী ভাবে:

request: malloc(24)

এবার এই ধারণাগুলো আসল কোডে। নিচের প্রোগ্রামে পুরো একটি allocator আছে — my_malloc, my_free, আর heap-এর অবস্থা ছাপার জন্য dump. কোডটি অন্য পর্বের চেয়ে লম্বা; ধীরে পড়ুন, তারপর চালান।

#include <stdio.h>
#include <stddef.h>
#define HEAP 1024
#define AL _Alignof(max_align_t)                 /* 16 on x86-64 Linux */
static _Alignas(max_align_t) size_t heap[HEAP / sizeof(size_t)];
#define H(off) heap[(off) / sizeof(size_t)]       /* header word at byte offset */
#define SIZE(off) (H(off) & ~(size_t)1)           /* low bit = used flag */
static void *my_malloc(size_t n) {
    if (n > HEAP) return NULL;
    size_t need = AL + (n + AL - 1) / AL * AL;      /* header + rounded payload */
    for (size_t off = 0; off < HEAP; off += SIZE(off)) {
        size_t sz = H(off);
        if ((sz & 1) || sz < need) continue;        /* used or too small: skip */
        if (sz - need >= 2 * AL) { H(off + need) = sz - need; sz = need; } /* split */
        H(off) = sz | 1;                            /* mark used */
        return (char *)heap + off + AL;             /* payload after header */
    }
    return NULL;
}
static void my_free(void *p) {
    size_t off = (size_t)((char *)p - (char *)heap) - AL;
    if (!(H(off) & 1)) { printf("double free at offset %zu!\n", off); return; }
    H(off) &= ~(size_t)1;                           /* clear used flag */
    for (off = 0; off < HEAP; off += SIZE(off))     /* coalesce free neighbours */
        while (!(H(off) & 1) && off + H(off) < HEAP && !(H(off + H(off)) & 1))
            H(off) += H(off + H(off));
}
static void dump(const char *tag) {
    printf("%-7s", tag);
    for (size_t off = 0; off < HEAP; off += SIZE(off))
        printf(" [%zu %s %zu]", off, (H(off) & 1) ? "used" : "free", SIZE(off));
    printf("\n");
}
int main(void) {
    H(0) = HEAP;                                    /* one big free block */
    char *a = my_malloc(20), *b = my_malloc(100), *c = my_malloc(10);
    dump("start");
    my_free(b); dump("free b");
    my_free(b);                                     /* double free on purpose */
    my_free(a); dump("free a");
    char *d = my_malloc(40); dump("d=40");
    my_free(c); my_free(d); dump("end");
}

৫ · free আর coalescing — পাশের ফাঁকা জায়গা জোড়া দেওয়া

free-এর সবচেয়ে সহজ রূপ হলো শুধু flag মুছে দেওয়া। কিন্তু তাতে একটি নীরব সমস্যা তৈরি হয়। পাশাপাশি তিনটি ছোট খালি block থাকলে allocator সেগুলোকে তিনটি আলাদা ছোট জায়গা হিসেবেই দেখে — একটি বড় অনুরোধ এলে বলবে “জায়গা নেই”, অথচ জায়গা আছে! সমাধান: free করার সময় প্রতিবেশী খালি কি না দেখে জোড়া দেওয়া, যার নাম coalescing.

পরের প্রতিবেশী খুঁজে পাওয়া সহজ — নিজের header-এ আকার আছে, যোগ করলেই পরের header. কিন্তু আগের প্রতিবেশী? header শুধু সামনের দিকে পথ দেখায়। এর সমাধান দিয়েছিলেন Donald Knuth — boundary tag: প্রতিটি block-এর শেষেও আকারের একটি কপি রাখো (footer). তাহলে যেকোনো block-এর header-এর ঠিক আগের কয়েকটি byte পড়লেই আগের block-এর আকার ও অবস্থা জানা যায়। দুই দিকেই জোড়া দেওয়া যায় এক ধাপে, পুরো heap না ঘুরেই।

largest free block: 128

Double free ধরা — flag আর magic number

উপরের কোডে my_free আগে flag দেখে নেয় — flag আগে থেকেই 0 হলে বুঝে যায় এটি double free. আরও কড়া allocator header-এ একটি magic number রাখে — ধরুন used block-এ একটি নির্দিষ্ট বিশেষ সংখ্যা, free block-এ আরেকটি। free-এর সময় সংখ্যাটি না মিললে বোঝা যায়, হয় ঠিকানাটি কখনো malloc দেয়নি, নয়তো কেউ header-এর ওপর লিখে ফেলেছে।

৬ · Fragmentation — জায়গা আছে, তবু পাওয়া যায় না

Fragmentation দুই রকম, আর দুটির কারণ ও প্রতিকার আলাদা:

নিচের ডায়াগ্রামে external fragmentation-কে চোখের সামনে ঘটতে দেখুন। সরলতার জন্য এখানে header বাদ দিয়ে শুধু payload দেখানো হয়েছে:

used 256, free 0

কোন খালি block বেছে নেবেন — placement policy

খালি block বেছে নেওয়ার নিয়মকে বলে placement policy. তিনটি ক্লাসিক নিয়ম:

কোনটি “সেরা”, তার সর্বজনীন উত্তর নেই — নির্ভর করে প্রোগ্রাম কোন মাপের জিনিস কোন ক্রমে নেয় ও ছাড়ে, তার ওপর।

৭ · বাস্তব allocator কীভাবে দ্রুত হয় — size class, thread cache, realloc, calloc

মাপ অনুযায়ী আলাদা তালিকা

একটি লম্বা তালিকা ঘুরে মাপমতো block খোঁজা ধীর। বাস্তবের প্রায় সব বড় allocator তাই segregated free list ব্যবহার করে: মাপ অনুযায়ী আলাদা আলাদা free list. ১৬ byte-এর খালি block এক তালিকায়, ৩২-এর আরেকটিতে, ৪৮-এর আরেকটিতে… কেউ ৪০ চাইলে সরাসরি ৪৮-এর তালিকার মাথা থেকে একটি তুলে দাও — খোঁজাই লাগে না, কাজটি প্রায় O(1). এই নির্দিষ্ট মাপগুলোর নাম size class.

Size class আরেকটি উপকার করে: একই মাপের জিনিস পাশাপাশি থাকে, তাই external fragmentation কমে। খুব বড় অনুরোধ (glibc-এ ডিফল্টে প্রায় ১২৮ KB-র বেশি) সাধারণত আলাদা পথে, সরাসরি mmap দিয়ে সামলানো হয়।

একাধিক thread — খাতা একটি, হাত অনেক

পর্ব ৫২-এ আপনি thread নিয়ে কাজ করবেন। তখন একটি নতুন সমস্যা দাঁড়ায়: আমাদের allocator-এর heap আর header-গুলো সব thread-এর মধ্যে ভাগ করা। দুটি thread একসাথে একই খালি block-কে “আমার” বানাতে গেলে data race — দুজনেই একই জায়গা পাবে, হিসাব ভেঙে যাবে। সহজতম সমাধান একটি mutex: যে malloc ডাকছে, সে তালা দিয়ে ঢুকবে। কিন্তু ৩২টি core-এর সার্ভারে সবাই একটি তালার সামনে লাইন দিলে (lock contention) গতি ভেঙে পড়ে।

বাস্তবের allocator-গুলো তাই কাজ ভাগ করে দেয়। glibc-এর ptmalloc একাধিক arena রাখে — আলাদা আলাদা heap, যার প্রতিটির নিজের তালা; বিভিন্ন thread বিভিন্ন arena ব্যবহার করে। ২০১৭ সালের glibc ২.২৬ থেকে প্রতিটি thread-এর একটি ছোট নিজস্ব ভান্ডারও আছে, tcache: সম্প্রতি ছাড়া কয়েকটি ছোট block সেখানে জমা থাকে, আর পরের malloc তালা ছাড়াই সেখান থেকে পায়। পর্ব ২০-এ যে মেসেজটি দেখেছিলেন — free(): double free detected in tcache 2 — সেটি এই tcache-এরই পাহারা।

অন্য বিখ্যাত allocator-গুলোও একই মূল ধারণায় দাঁড়িয়ে — thread-প্রতি বা core-প্রতি cache, তার পেছনে ভাগ করা কেন্দ্রীয় ভান্ডার, আর size class: jemalloc (FreeBSD থেকে আসা, Facebook-এ বহুল ব্যবহৃত), Google-এর tcmalloc (“thread-caching malloc”), আর Microsoft Research-এর mimalloc.

realloc-এর আসল চেহারা

realloc দেখতে একটি ফাংশন, কিন্তু ভেতরে তিনটি আলাদা পথ। নিজের allocator-এ লিখলে মোটামুটি এমন হবে:

void *my_realloc(void *p, size_t n) {
    if (p == NULL) return my_malloc(n);        /* NULL হলে সাধারণ malloc */
    size_t old = payload_size(p);              /* header থেকে পুরোনো আকার */
    if (n <= old) return p;                    /* ১. জায়গা আছে: একই ঠিকানা (চাইলে split) */
    if (grow_into_next_free_block(p, n))       /* ২. পাশের block খালি ও যথেষ্ট বড়: */
        return p;                              /*    জোড়া দিয়ে একই ঠিকানায় বাড়ানো */
    void *q = my_malloc(n);                    /* ৩. নতুন জায়গা, কপি, পুরোনো free */
    if (q == NULL) return NULL;                /*    ব্যর্থ হলে পুরোনো block অক্ষত! */
    memcpy(q, p, old);
    my_free(p);
    return q;
}

তিন নম্বর পথটিই পর্ব ২০-এর সেই সতর্কতার কারণ — ঠিকানা বদলে যেতে পারে, আর ব্যর্থ হলে পুরোনো block থেকে যায়। তাই p = realloc(p, n) লিখলে ব্যর্থতার সময় একমাত্র ঠিকানাটি হারিয়ে leak হয়; সবসময় একটি অস্থায়ী ভ্যারিয়েবলে নিন। আরেকটি সূক্ষ্মতা: realloc(p, 0)-এর আচরণ নিয়ে বিভিন্ন library বরাবর একমত ছিল না, আর C23 এটিকে সরাসরি undefined behavior বলে দিয়েছে — এমন ডাক এড়িয়ে চলুন।

calloc আর গুণের overflow

calloc-এর মূল্য শুধু শূন্য দিয়ে ভরায় নয়। count * size গুণ করতে গেলে size_t-এর সীমা পেরিয়ে ছোট একটি সংখ্যা হয়ে যেতে পারে — তখন ছোট block দেওয়া হবে, আর ব্যবহারকারী বড় ভেবে লিখতে থাকবেন। ভালো calloc গুণ করার আগেই ভাগ করে যাচাই করে:

void *safe_calloc(size_t count, size_t size) {
    if (size != 0 && count > SIZE_MAX / size) return NULL;  /* গুণ করলে overflow হতো */
    void *p = malloc(count * size);
    if (p != NULL) memset(p, 0, count * size);
    return p;
}

এই কোর্সের Linux compiler-এ glibc-এর আসল calloc(SIZE_MAX / 2, 4) চালিয়ে দেখেছি — নিরাপদে NULL দেয়। আধুনিক বিকল্পও আছে: GCC/Clang-এর __builtin_mul_overflow, আর C23-এর <stdckdint.h>-এ ckd_mul — দুটিই checked arithmetic. OpenBSD এই একই চিন্তা থেকে reallocarray এনেছিল, যা পরে glibc-তেও এসেছে।

৮ · বিশেষ কাজের allocator — arena আর pool

সাধারণ malloc সবার জন্য বানানো। কিন্তু মেমরি ব্যবহারের ধরন জানা থাকলে অনেক সহজ, অনেক দ্রুত allocator বানানো যায়।

Arena (bump) allocator — সব একসাথে ছেড়ে দেওয়া

একটি দোকানের দিনের বিক্রির CSV ফাইল পড়ার কথা ভাবুন। প্রতিটি লাইনে দোকানের নাম আর টাকার অঙ্ক। প্রোগ্রামটি শত শত ছোট string বানাবে, হিসাব করবে, রিপোর্ট দেবে — তারপর সবকিছু একসাথে ফেলে দেবে। প্রতিটি string-এর জন্য আলাদা malloc আর আলাদা free অপ্রয়োজনীয় খরচ, আর একটি free ভুলে গেলেই leak.

Arena allocator এই ধরনের জন্য তৈরি। একটি বড় buffer আর একটি সংখ্যা — used, অর্থাৎ কতদূর ভরা হয়েছে। নতুন অনুরোধ এলে used-কে aligned জায়গায় গোল করো, সেখান থেকে দাও, used সামনে ঠেলে দাও (“bump”). কোনো header নেই, কোনো free list নেই, খোঁজাও নেই। আর ছেড়ে দেওয়ার সময় একটি লাইন: used = 0.

1void *arena_alloc(Arena *a, size_t n) {2    size_t start = round_up(a->used, 16);3    if (start > a->cap || n > a->cap - start) return NULL;4    a->used = start + n;5    return a->buf + start;6}7/* no arena_free(name) exists */8ar.used = 0;        /* reset */

এবার পুরো প্রোগ্রামটি — একটি ছোট CSV থেকে দোকানের নামগুলো arena-তে কপি করে মোট বিক্রি হিসাব করা হচ্ছে:

#include <stdio.h>
#include <string.h>
#include <stddef.h>
typedef struct { unsigned char *buf; size_t cap, used; } Arena;
static void *arena_alloc(Arena *a, size_t n) {
    size_t al = _Alignof(max_align_t);
    size_t start = (a->used + al - 1) / al * al;            /* round up */
    if (start > a->cap || n > a->cap - start) return NULL;  /* no overflow */
    a->used = start + n;                                    /* just bump */
    return a->buf + start;
}
int main(void) {
    static _Alignas(max_align_t) unsigned char mem[256];
    Arena ar = { mem, sizeof mem, 0 };
    const char *p = "Rahim Store,1200\nKarim Tea Stall,350\nNadia Fashion,4100\n";
    long total = 0;
    while (*p) {
        size_t len = strcspn(p, ",");
        char *name = arena_alloc(&ar, len + 1);   /* many small strings */
        if (name == NULL) { printf("arena full\n"); break; }
        memcpy(name, p, len);
        name[len] = '\0';
        long amount = 0;
        sscanf(p + len + 1, "%ld", &amount);
        total += amount;
        printf("%-16s %5ld  offset %td\n", name, amount, (unsigned char *)name - mem);
        p += strcspn(p, "\n") + 1;
    }
    printf("total %ld, arena used %zu of %zu bytes\n", total, ar.used, ar.cap);
    ar.used = 0;                                  /* free everything at once */
    printf("after reset: used %zu\n", ar.used);
    return 0;
}

Pool allocator — একই মাপের অনেক জিনিস

পর্ব ৩৩-এর linked list-এর কথা মনে করুন। প্রতিটি node একই মাপের, আর node বারবার যোগ ও মোছা হয়। প্রতিটির জন্য সাধারণ malloc ডাকলে প্রতিবার header-এর খরচ, খোঁজার খরচ, আর node-গুলো heap-এর এদিক-ওদিক ছড়িয়ে পড়ে (cache miss বাড়ে)।

Pool allocator শুরুতেই একই মাপের অনেকগুলো ঘর (slot) বানিয়ে রাখে। খালি ঘরগুলো একটি free list-এ গাঁথা — আর সেই তালিকার next pointer থাকে খালি ঘরের নিজের ভেতরেই, কারণ ঘরটি তো এখন খালি! পর্ব ৩৩-এ “malloc-এর ভেতরের free list” প্রসঙ্গে ঠিক এই কৌশলের কথা বলেছিলাম:

struct Node { int value; struct Node *next; };
typedef union Slot { union Slot *next_free; struct Node node; } Slot;
static Slot slots[1000];
static Slot *free_head;

void pool_init(void) {
    for (int i = 0; i < 999; i++) slots[i].next_free = &slots[i + 1];
    slots[999].next_free = NULL;
    free_head = &slots[0];
}
struct Node *pool_alloc(void) {
    if (free_head == NULL) return NULL;      /* pool খালি */
    Slot *s = free_head;
    free_head = s->next_free;                /* তালিকার মাথা সরাও: O(1) */
    return &s->node;
}
void pool_free(struct Node *n) {
    Slot *s = (Slot *)n;                     /* union: একই ঠিকানা */
    s->next_free = free_head;                /* মাথায় ঢোকাও: O(1) */
    free_head = s;
}

union (পর্ব ২২) এখানে দারুণ কাজ করছে: একটি ঘর হয় খালি — তখন তার ভেতরে next_free; নয়তো ব্যবহৃত — তখন ভেতরে একটি Node. একসাথে দুটো কখনো নয়, তাই একই জায়গা ভাগ করা নিরাপদ। নেওয়া আর ছাড়া দুটোই দুই-তিনটি নির্দেশ, কোনো header নেই, internal fragmentation নেই, আর সব node এক টানা array-তে — cache-বান্ধব। Linux kernel-এর slab allocator একই চিন্তার বড় রূপ: প্রতিটি ঘন ঘন ব্যবহৃত kernel struct-এর জন্য আলাদা cache.

৯ · যখন allocator-এর খাতা নষ্ট হয় — heap-এর বাগ ভেতর থেকে

এখন আপনি জানেন প্রতিটি payload-এর ঠিক আগে ও পরে allocator-এর নিজের তথ্য — heap metadata — থাকে। পর্ব ২০-এর পাঁচটি বিপজ্জনক ভুল এবার ভেতর থেকে বোঝা যায়। এখানে উদ্দেশ্য প্রতিরক্ষা: বাগটি কীভাবে খাতা নষ্ট করে, আর কীভাবে ধরবেন।

সবচেয়ে কষ্টের বিষয় হলো কারণ আর লক্ষণের মধ্যে দূরত্ব। আমাদের ছোট allocator-এ a-তে ৩২-এর জায়গায় ৪০ byte লিখলে b-এর header নষ্ট হবে, কোনো error ছাড়াই। Crash দেখা যাবে পরে my_free-এর ভেতরে — অথচ দোষ a-তে লেখা কোডের।

পাহারাদার — sanitizer, Valgrind আর hardened allocator

পর্ব ৩১-এ যে sanitizer আর Valgrind দেখেছেন, সেগুলো ঠিক এই সমস্যার জন্যই। AddressSanitizer প্রতিটি block-এর দুই পাশে নিষিদ্ধ এলাকা (redzone) রাখে আর free হওয়া block কিছুক্ষণ আটকে রাখে (quarantine) — তাই overflow বা use-after-free যে লাইনে ঘটে, সেখানেই ধরা পড়ে, পরের কোনো দুর্ঘটনায় নয়। Valgrind কোড না বদলেই প্রতিটি মেমরি-ব্যবহার পরীক্ষা করে।

gcc -g -fsanitize=address,undefined my_alloc_test.c -o t && ./t
valgrind --leak-check=full ./t

একটি সূক্ষ্ম কথা: ASan চেনে শুধু আসল malloc-এর block — আপনার static array-র ভেতরের ভুল সে সাধারণত দেখতে পায় না। তাই নিজের allocator-কে আলাদা করে test করুন: হাজার বার এলোমেলো malloc/free চালিয়ে প্রতিবার হিসাব মেলান (সব block-এর আকারের যোগফল = পুরো heap? পাশাপাশি দুটি খালি block নেই তো?)।

Production-এর জন্যও প্রতিরক্ষা আছে। Hardened allocator নিরাপত্তাকে গতির ওপরে রাখে: metadata-কে payload থেকে দূরে আলাদা জায়গায় রাখা, free list-এর pointer গোপন চাবি দিয়ে এনকোড করা, block-এর ঠিকানা এলোমেলো করা, double free কড়াভাবে ধরা। Android-এর Scudo, GrapheneOS-এর hardened_malloc, আর Chrome-এর PartitionAlloc এই ধারার উদাহরণ; glibc-ও তার free list-এ “safe-linking” নামে pointer এনকোড করার কৌশল যোগ করেছে। এগুলো বাগ দূর করে না — শুধু বাগকে হামলায় পরিণত করা কঠিন করে।

১০ · AI-এর যুগে — AI-এর লেখা allocator যাচাই

“একটা memory allocator লিখে দাও” — AI কয়েক সেকেন্ডে পরিষ্কার দেখতে কোড দেবে। কিন্তু allocator-এর ভুল ধরা পড়ে লাখ বার malloc/free-এর পরে, অন্য thread-এ, অন্য মাপে। নিচের ভুলগুলো AI-এর allocator-এ বারবার দেখা যায়:

AI-এর allocator হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি ফেরত ঠিকানা _Alignof(max_align_t)-এর গুণিতক — assert দিয়ে প্রমাণ করেছি
• সব free করার পরে heap আবার একটি বড় খালি block — কোনো byte হারায়নি
• 0, 1, heap-এর মাপ, আর SIZE_MAX-এর কাছাকাছি মাপ দিয়ে চালিয়েছি
• Double free আর ভুল ঠিকানা free করলে কী হয় — জেনে-বুঝে পরীক্ষা করেছি
• বহু-thread ব্যবহার হলে তালা বা thread-প্রতি cache আছে, আর ThreadSanitizer পরিষ্কার
• বাকি প্রোগ্রাম সাধারণ malloc দিয়ে ASan/Valgrind-এ পরিষ্কার — তারপরই নিজের allocator বসিয়েছি