Memory Allocator

কেন এই প্রজেক্ট

malloc সম্ভবত আপনার লেখা সবচেয়ে বেশি-ব্যবহৃত function, আর সম্ভবত সবচেয়ে কম বোঝা। এটা কোথা থেকে memory পায়? কেন free করার পরেও প্রোগ্রামের RSS কমে না? কেন দুইটা প্রোগ্রাম একই allocation pattern-এ ভিন্ন গতিতে চলে?

Allocator লেখা একটা বিরল প্রজেক্ট যেখানে আপনি একটা নিরবচ্ছিন্ন space-time trade-off নিজের হাতে নিয়ন্ত্রণ করেন। প্রতিটা সিদ্ধান্ত — header কত বড়, কোন fit policy, কখন coalesce — সরাসরি মাপা যায়।

আর এটা এমন কোড যেখানে একটা bug মানে সাধারণ crash নয়, বরং অন্য কোথাও, অনেক পরে অদ্ভুত আচরণ। সেই debugging অভিজ্ঞতাটাই মূল্যবান।

Interface

void *my_malloc(size_t size);
void  my_free(void *ptr);
void *my_realloc(void *ptr, size_t size);
void *my_calloc(size_t n, size_t size);

ধাপে ধাপে

১. Arena আর bump allocator

#define ARENA_SIZE (64UL \<\< 20)      /* 64 MB */

static char *arena, *bump, *arena_end;

static void init(void) {
    arena = mmap(NULL, ARENA_SIZE, PROT_READ | PROT_WRITE,
                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    bump = arena;
    arena_end = arena + ARENA_SIZE;
}

void *my_malloc(size_t size) {
    size = (size + 15) & ~15UL;          /* ১৬-byte align */
    if (bump + size > arena_end) return NULL;
    void *p = bump;
    bump += size;
    return p;
}

void my_free(void *p) { (void)p; }       /* কিছুই না */

৩০ লাইনে একটা কাজ করা allocator। অবিশ্বাস্যভাবে দ্রুত — একটা যোগ আর একটা তুলনা। কিন্তু memory কখনো ফেরত আসে না।

লক্ষ্য করুন mmap ৬৪ MB চাইল কিন্তু RSS বাড়ল না — lazy allocation, যা আপনি page fault-এর লেসনে দেখেছেন।

২. Header আর free list

প্রতিটা block-এর আগে একটা header:

typedef struct block {
    size_t size;              /* নিচের bit গুলো flag-এর জন্য মুক্ত */
    struct block *next;       /* শুধু free block-এ ব্যবহৃত */
    struct block *prev;
} block_t;

চতুর কৌশল: size সবসময় ১৬-এর গুণিতক, তাই নিচের ৪ bit সবসময় শূন্য — সেখানে allocated flag রাখুন।

#define SIZE(b)      ((b)->size & ~0xFUL)
#define IS_ALLOC(b)  ((b)->size & 1)

Header-এর খরচ মনে রাখুন: প্রতি allocation-এ ৮–৩২ byte। ১৬-byte allocation-এ সেটা ১০০%+ overhead — এজন্যই size class দরকার।

৩. Coalescing আর boundary tag

free()-এর সময় পাশের block মুক্ত হলে জোড়া লাগান। ডান পাশে যাওয়া সহজ ((char*)b + SIZE(b)), কিন্তু বাঁ পাশে?

সমাধান — boundary tag: প্রতিটা block-এর শেষেও size লিখে রাখুন। তখন আগের block-এর footer পড়ে তার শুরু বের করা যায়।

┌────────┬──────────────┬────────┐
│ header │   payload    │ footer │
│  size  │              │  size  │
└────────┴──────────────┴────────┘

Knuth-এর এই কৌশলটা ১৯৬০-এর দশকের, আর আজও প্রতিটা allocator-এ আছে।

৪. Fit policy

Policy	খোঁজার খরচ	Fragmentation
First fit	দ্রুত	মাঝারি
Best fit	O(n)	কম, কিন্তু ছোট টুকরো বাড়ে
Worst fit	O(n)	খারাপ
Segregated	O(1)	ভালো

তিনটাই লিখুন আর মেপে দেখুন — অনুমান করবেন না।

পরিমাপ

/* প্রতিটা পরীক্ষার পর ছাপুন */
size_t total_requested;   /* ব্যবহারকারী যা চেয়েছে */
size_t total_arena_used;  /* আপনি arena থেকে যা নিয়েছেন */
double utilisation = (double)total_requested / total_arena_used;

Utilisation ০.৮-এর উপরে হলে ভালো। Throughput আলাদাভাবে মাপুন — ops/second।

তিনটা workload দিয়ে পরীক্ষা করুন:

1. অনেক ছোট allocation, কখনো free না — bump জিতবে
2. Random size, random free — coalescing-এর আসল পরীক্ষা
3. দুইটা আকার পর্যায়ক্রমে (ফ্র্যাগমেন্টেশন ফাঁদ) — এখানেই naive allocator ভেঙে পড়ে

LD_PRELOAD দিয়ে বাস্তব পরীক্ষা

gcc -shared -fPIC -o myalloc.so myalloc.c
LD_PRELOAD=./myalloc.so ls -la
LD_PRELOAD=./myalloc.so git status

আপনার allocator যদি একটা সত্যিকারের প্রোগ্রাম চালাতে পারে, সেটা একটা বাস্তব অর্জন। প্রথমবার প্রায় নিশ্চিতভাবে crash করবে — আর সেই debugging-টাই সবচেয়ে বেশি শেখাবে।

নিজেকে চ্যালেঞ্জ করুন

1. Thread safety — একটা global lock, তারপর per-thread arena (glibc-র arena ধারণা), আর contention মাপুন
2. mmap threshold — বড় allocation সরাসরি mmap, munmap-এ ফেরত
3. Debugging feature — double-free detection, canary দিয়ে buffer overflow ধরা (এটাই ASAN-এর সরলীকৃত রূপ)
4. MADV_DONTNEED দিয়ে মুক্ত page OS-কে ফেরত দিন আর RSS কমতে দেখুন
5. jemalloc আর mimalloc-এর সাথে তুলনা করুন একই benchmark-এ