Memory Allocation — malloc আসলে কী করে

আগে এটা বুঝি

গত লেসনের শেষ প্রশ্নটা ছিল — একটা প্রোগ্রামার malloc(100) ডাকলে সেই ১০০ byte কোথা থেকে আসে? এতদিন আমরা OS-এর দৃষ্টিকোণ থেকে memory দেখেছি — VMA, page table, page fault। কিন্তু malloc নিজে kernel-এর অংশ না; এটা glibc-র (বা jemalloc, tcmalloc-এর) একটা library function, যা userspace-এই একটা সম্পূর্ণ বই-রক্ষণ ব্যবস্থা চালায়, আর মাঝেমধ্যে — শুধু মাঝেমধ্যে — kernel-কে ডাকে নতুন virtual memory চাইতে।

malloc সম্ভবত আপনার লেখা প্রোগ্রামে সবচেয়ে বেশি-ডাকা function, আর প্রায়ই সবচেয়ে কম বোঝা। প্রতিটা কল কি একটা syscall? না — বেশিরভাগ কলই আগে থেকে বরাদ্দ করা একটা বড় অঞ্চলের একটা টুকরো ফেরত দেয়, কোনো kernel-এর দ্বারস্থ না হয়েই। free() করার পর সেই memory কি OS-কে ফেরত যায়? প্রায়ই না — আর এই “না”-টার একটা সুনির্দিষ্ট, structural কারণ আছে, যা এই লেসনের কেন্দ্রীয় বিষয়।

এই লেসনে আমরা দেখব malloc ঠিক কখন kernel-কে ডাকে (brk বনাম mmap), সেই কলের ভেতরে ptmalloc2 কী বই রাখে (chunk, bin, arena), আর কেন “memory ফেরত দেওয়া” — যেটা শুনতে সহজ মনে হয় — বাস্তবে allocator ডিজাইনের সবচেয়ে কঠিন সমস্যাগুলোর একটা।

মূল ধারণা

brk/sbrk বনাম mmap — malloc-এর দুইটা উৎস

একটা প্রসেসের address space-এ heap সাধারণত BSS segment-এর ঠিক পরে বসে, আর তার উপরের সীমাকে বলে program break। brk(addr) syscall সরাসরি এই সীমা একটা নির্দিষ্ট ঠিকানায় বসায়; sbrk(increment) — যা glibc আসলে ব্যবহার করে — একটা relative wrapper, বর্তমান break-কে increment দিয়ে বাড়ায় (বা ঋণাত্মক increment দিয়ে কমায়) আর পুরনো break-এর ঠিকানা ফেরত দেয়।

mmap(), গত লেসনগুলোয় যেমন দেখেছেন, address space-এর যেকোনো জায়গায় একটা স্বতন্ত্র, VMA-backed অঞ্চল তৈরি করে — heap-এর সাথে তার কোনো structural সম্পর্ক নেই।

glibc-র malloc দুইটাই ব্যবহার করে, আকার অনুযায়ী সিদ্ধান্ত নিয়ে:

	`brk`/`sbrk`-ভিত্তিক heap	সরাসরি `mmap`
কখন ব্যবহৃত	request < `MMAP_THRESHOLD` (ডিফল্ট ১২৮ KB)	request ≥ `MMAP_THRESHOLD`
গঠন	একটা একক, ক্রমবর্ধমান contiguous অঞ্চল	প্রতিটা allocation-এর নিজস্ব, স্বতন্ত্র mapping
ফেরত দেওয়া	শুধু সবচেয়ে-উপরের অংশ থেকে, আর তাও শর্তসাপেক্ষে (নিচে বিস্তারিত)	`free()`-এ সরাসরি `munmap()` — সম্পূর্ণ, নিঃশর্ত ফেরত
syscall overhead	একটা `sbrk()` অনেকগুলো allocation-কে পরিবেশন করে	প্রতিটা বড় allocation-এর নিজস্ব `mmap`/`munmap`
alignment/waste	কোনো বাধ্যতামূলক page-alignment না, কিন্তু chunk header overhead আছে	পুরো request page-এ round হয় — ছোট allocation-এর জন্য অপচয়ী

MMAP_THRESHOLD কেন ১২৮ KB-তে বসানো — এটা একটা trade-off-এর ভারসাম্য বিন্দু। ছোট allocation-এ mmap ব্যবহার করলে প্রতিটার জন্য একটা পূর্ণাঙ্গ syscall (কয়েক μs) আর page-table bookkeeping লাগত, যেখানে heap-ভিত্তিক allocation-এ সেই খরচ প্রায় শূন্য (শুধু bin থেকে একটা chunk বাছাই)। কিন্তু বড় allocation-এ heap ব্যবহার করলে সেই একটা বড় chunk heap-এর মাঝখানে বসে যেত, coalescing/fragmentation-কে জটিল করে তুলত, আর free()-এও সহজে ফেরত দেওয়া যেত না (নিচের fragmentation অংশে ঠিক এই সমস্যা)। mmap-এ বড় allocation স্বতন্ত্র, তাই free()-এ সরাসরি সম্পূর্ণ munmap() — কোনো fragmentation-ঝুঁকি ছাড়াই। glibc এই threshold dynamically adjust করে — যদি একটা mmap-করা chunk free() করার সময় দেখা যায় সেটা threshold-এর চেয়ে বড় ছিল, glibc ভবিষ্যতের threshold কিছুটা বাড়িয়ে দেয় (একটা heuristic, যাতে একই আকারের বারবার allocation mmap-এর overhead এড়াতে পারে)। mallopt(M_MMAP_THRESHOLD, ...) দিয়ে ম্যানুয়ালি নিয়ন্ত্রণও করা যায়।

ptmalloc2-র ভেতরের গঠন — chunk, bin, coalescing

glibc-র malloc বাস্তবায়ন (ptmalloc2, Wolfram Gloger-এর, Doug Lea-র মূল dlmalloc-এর একটা thread-aware সম্প্রসারণ) heap-কে ছোট ছোট chunk-এ ভাগ করে রাখে:

              ┌───────────────┐
              │  prev_size     │  ← আগের chunk free হলে তার আকার (coalescing-এ ব্যবহৃত)
              ├───────────────┤
              │  size + flags  │  ← এই chunk-এর আকার; নিচের ৩ বিট flag (PREV_INUSE ইত্যাদি)
              ├───────────────┤ ← malloc()-এর ফেরত দেওয়া pointer ঠিক এখানে
              │                │
              │   user data    │
              │                │
              └───────────────┘

একটা allocated chunk-এর গঠন — user pointer chunk-এর মাঝখান থেকে শুরু, header তার আগে।

size field-এর নিচের তিনটা বিট (যেহেতু chunk সবসময় ৮/১৬-বাইট সারিবদ্ধ, তাই ওই বিটগুলো এমনিতেই শূন্য থাকত) flag হিসেবে পুনর্ব্যবহার হয় — PREV_INUSE (আগের chunk বরাদ্দকৃত কিনা, তাই prev_size বৈধ কিনা), IS_MMAPPED (এই chunk আলাদা mmap-করা কিনা), NON_MAIN_ARENA (কোন arena-র অংশ)। ঠিক গত মডিউলে PTE-র নিচের বিট পুনর্ব্যবহারের (huge page-এর PS বিট) মতো একই কৌশল।

Free হওয়া chunk-গুলো আকার অনুযায়ী আলাদা bin-এ রাখা হয়, দ্রুত খোঁজার জন্য:

Bin	আকার-সীমা	গঠন	Coalesce হয়?
tcache (glibc ≥ ২.২৬)	ছোট আকার, প্রতি-thread ৬৪টা পর্যন্ত	per-thread, lock-free singly-linked list	না
fastbin	≤ ১৬০ byte (ডিফল্ট)	singly-linked, LIFO	না — গতির জন্য ইচ্ছাকৃতভাবে এড়ানো
smallbin	< ৫১২ byte, নির্দিষ্ট আকার প্রতি bin	doubly-linked, FIFO	হ্যাঁ
largebin	≥ ৫১২ byte, একটা range প্রতি bin	doubly-linked, আকার-ক্রমে sorted	হ্যাঁ
unsorted bin	যেকোনো আকার, সদ্য-free হওয়া chunk-এর সাময়িক অবস্থান	doubly-linked	পরবর্তী malloc-এ sort হয়ে সঠিক bin-এ যায়

একটা malloc(n) কল এই ক্রমে খোঁজে: tcache (দ্রুততম, কোনো lock লাগে না) → fastbin (n যদি ছোট হয়) → smallbin/unsorted bin → largebin → কোনোটাতেই না পেলে heap-এর একদম শেষের “wilderness” chunk থেকে split করে দেওয়া → সেটাও অপর্যাপ্ত হলে sbrk() দিয়ে heap বড় করা (বা threshold ছাড়ালে সরাসরি mmap)।

Coalescing — free() করার সময়, fastbin ছাড়া সব ক্ষেত্রে, ptmalloc2 পাশের chunk-গুলো (আগেরটা prev_size/PREV_INUSE দিয়ে, পরেরটা সরাসরি) free কিনা চেক করে, free হলে জোড়া লাগিয়ে একটা বড় chunk বানায়। এটাই external fragmentation কমানোর মূল হাতিয়ার — ছোট ছোট free hole একসাথে জোড়া লেগে বড় request পরিবেশন করতে সক্ষম হয়। fastbin-এ ইচ্ছাকৃতভাবে coalesce করা হয় না — গতি অগ্রাধিকার পায়, পরে malloc_consolidate() (largbin request বা free()-এর নির্দিষ্ট শর্তে ট্রিগার হয়) fastbin-এর chunk-গুলোকে একসাথে coalesce করে।

Arena — multi-threaded allocation-এ lock contention কমানো

একটা single global heap আর একটা single lock দিয়ে সব thread-কে পরিবেশন করলে ভারী multi-threaded workload-এ সেই lock-ই bottleneck হয়ে যায়। ptmalloc2 তাই একাধিক arena রাখে — প্রতিটা তার নিজস্ব heap অঞ্চল (main thread-এরটা brk-ভিত্তিক, বাকিগুলো mmap-করা sub-heap) আর নিজস্ব mutex নিয়ে। একটা নতুন thread প্রথম allocation-এ একটা arena-য় assign হয় (round-robin-এর কাছাকাছি একটা নীতিতে, বা lock-free arena-য় গেলে সেটাই ব্যবহার করে); একাধিক thread একই arena ভাগ করতে পারে যদি thread সংখ্যা arena সংখ্যার চেয়ে বেশি হয়।

Arena সংখ্যার একটা ডিফল্ট ঊর্ধ্বসীমা আছে — 64-bit সিস্টেমে 8 × ncpus (tunable M_ARENA_MAX/MALLOC_ARENA_MAX environment variable দিয়ে)। এই সীমা ইচ্ছাকৃত — আরও বেশি arena মানে কম contention, কিন্তু প্রতিটা arena নিজস্ব heap ধরে রাখে, তাই arena সংখ্যা বাড়া সরাসরি memory overhead বাড়ায়, বিশেষত যদি বিভিন্ন arena-য় memory ভারসাম্যহীনভাবে ব্যবহৃত হয় (একটা arena-য় বড় allocation, বাকিগুলো প্রায় খালি কিন্তু তাদের heap তবুও ধরে থাকে)।

Fragmentation — কেন free() করার পরেও RSS কমে না

দুই ধরনের অপচয়:

Internal fragmentation — প্রতিটা allocation-এর জন্য chunk header (৮-১৬ byte) আর alignment (৬৪-বিটে ন্যূনতম chunk ৩২ byte) মানে একটা ছোট request-এও বাস্তব ব্যবহৃত মেমরি চাওয়া আকারের চেয়ে বেশি।
External fragmentation — মোট free memory যথেষ্ট, কিন্তু ছোট ছোট টুকরোয় ছড়ানো, তাই একটা বড় contiguous request পরিবেশন করা যায় না।

এই দুইটাই পরিচিত সমস্যা। কিন্তু আসল, প্রায়ই ভুল-বোঝা প্রশ্নটা হলো — যদি একটা প্রোগ্রাম ১ GB allocate করে পুরোটাই আবার free() করে, তার RSS কি ১ GB কমে?

সাধারণত না, আর কারণটা geometric — brk-ভিত্তিক heap-কে ভাবুন একটা স্ট্যাকের মতো: sbrk() শুধু সবচেয়ে-উপরের সীমা বাড়াতে বা কমাতে পারে। যদি heap-এর মাঝখানে (নিচের দিকে) একটা chunk এখনো ব্যবহৃত থাকে, তার উপরের সব free chunk থাকা সত্ত্বেও heap-এর top নামানো যায় না — কারণ সেই মাঝের ব্যবহৃত chunk-টা এখনো সেখানেই বসে আছে, আর ptmalloc2 (glibc-র ডিফল্ট বাস্তবায়নে) কোনো compaction করে না — allocated object-কে সরিয়ে একসাথে জড়ো করার কোনো mechanism নেই (যা করতে হলে সব pointer আপডেট করতে হতো, যা C-তে transparent-ভাবে অসম্ভব, কারণ pointer-গুলো programmer-এর হাতে)।

একটা concrete দৃশ্য

১,০০০টা ছোট object allocate করুন ক্রমে। শেষ ১০টা বাদে সব free() করুন — কিন্তু সেই বেঁচে-থাকা ১০টা যদি এলোমেলোভাবে ছড়ানো থাকে (প্রথমটা, মাঝেরটা, শেষেরটা), heap-এর top সেই সবচেয়ে-উপরের বেঁচে-থাকা object-এর ঠিক পরেই আটকে থাকবে — নিচের ৯৯০টা free chunk থাকা সত্ত্বেও RSS-এর প্রায় পুরোটাই ধরে থাকবে। মাত্র ১০টা live object, তবু প্রায় ১,০০০টার সমান memory footprint।

glibc-র malloc_trim() (আর internal heuristic M_TRIM_THRESHOLD, ডিফল্ট ১২৮ KB) একটা আংশিক সমাধান — যদি heap-এর একদম উপরে একটা যথেষ্ট বড় contiguous free chunk থাকে, glibc স্বয়ংক্রিয়ভাবে (বা ম্যানুয়াল malloc_trim(0) কলে) sbrk()-কে ঋণাত্মক increment দিয়ে সেই অংশ OS-কে ফেরত দেয়। কিন্তু এটা শুধু সবচেয়ে উপরের free অংশের জন্য কাজ করে — মাঝখানের hole-গুলো কখনো OS-কে ফেরত যায় না, শুধু ভবিষ্যতের allocation-এর জন্য পুনর্ব্যবহৃত হয়।

mmap-করা বড় allocation-এর জন্য এই সমস্যা নেই — free() সরাসরি munmap() ডাকে, পুরো অংশ তাৎক্ষণিকভাবে, নিঃশর্তভাবে OS-কে ফেরত যায়। এটাই MMAP_THRESHOLD-এর আরেকটা কারণ — বড়, দীর্ঘ-জীবিত allocation-কে heap-এর fragmentation-প্রবণ জগৎ থেকে বাইরে রাখা।

jemalloc, tcmalloc, mimalloc — বিকল্প ডিজাইন

glibc-র ptmalloc2 একমাত্র allocator না। কয়েকটা বিকল্প ভিন্ন trade-off বেছে নিয়েছে:

Allocator	মূল উৎস	কেন্দ্রীয় ডিজাইন-ধারণা
ptmalloc2 (glibc default)	Wolfram Gloger, Doug Lea-র dlmalloc-ভিত্তিক	Arena + bin, coalescing, brk/mmap হাইব্রিড
jemalloc	Jason Evans, FreeBSD (২০০৬), এখন Facebook/Meta-র মূল allocator	Size-class-ভিত্তিক “run”/“extent” সংগঠন, প্রতিটা thread-এর নিজস্ব cache, fragmentation-কে সরাসরি design metric হিসেবে ট্র্যাক করে
tcmalloc	Google	প্রতিটা thread-এর একটা lock-free local free-list (common path-এ কোনো lock না), একটা central free-list overflow/underflow-এ
mimalloc	Microsoft	“free list sharding” — প্রতিটা page-এর নিজস্ব local আর “deferred” free list, cross-thread free lock-free

মূল পার্থক্যের জায়গা — thread-local caching-এর গভীরতা (ptmalloc2-র tcache তুলনামূলক নতুন সংযোজন, jemalloc/tcmalloc শুরু থেকেই এই নীতিতে ডিজাইন করা) আর fragmentation-বিরোধী কৌশল (jemalloc-এর size-class segregation ptmalloc2-র bin-ভিত্তিক পদ্ধতির চেয়ে আরও কঠোরভাবে একই-আকারের object-কে একসাথে রাখে, যা দীর্ঘ-চলা, ভিন্ন-ভিন্ন-আকারের allocation-mix workload-এ কম fragmentation দেয়)।

ভেতরে কী ঘটছে

একটা malloc(64) কল — bin থেকে bin, শেষে kernel পর্যন্ত

malloc(64) — tcache miss থেকে শুরু করে সবচেয়ে খারাপ ক্ষেত্রে sbrk() পর্যন্ত

malloc(64) ডাকা হলোglibc প্রথমে request-কে chunk-size-এ রূপান্তর করে — header + alignment মিলিয়ে বাস্তবে ৮০ byte-এর একটা chunk লাগবে
tcache চেক — এই thread-এর নিজস্ব cache-এ ৮০-byte bin-এ কিছু আছে?থাকলে সরাসরি pop করে ফেরত — কোনো lock, কোনো syscall, প্রায় ~২০-৩০ ns
miss — fastbin চেক (৮০ byte fastbin সীমার মধ্যে)fastbin-এও খালি ধরে নিচ্ছি এই ট্রেসে — পরের ধাপে যেতে হচ্ছে
smallbin / unsorted bin স্ক্যানarena lock নিতে হয় এখানে — এটাই multi-threaded contention-এর জায়গা। unsorted bin-এর chunk-গুলো sort করে সঠিক bin-এ সরানো হয়, পথে যদি ৬৪-byte fit পাওয়া যায় তাহলেই তাৎক্ষণিক ফেরত
কোনো bin-এ উপযুক্ত chunk নেই — top chunk (wilderness) থেকে splitheap-এর একদম শেষে একটা বড়, unassigned chunk থাকে; সেখান থেকে ৮০ byte কেটে বাকিটা top chunk হিসেবে রেখে দেওয়া হয়
top chunk-ও যথেষ্ট বড় না — sbrk() ডাকতে হলোএই একমাত্র ধাপে সত্যিকারের syscall — heap-কে সাধারণত একটা বড় increment (যেমন ১৩২ KB) দিয়ে বাড়ানো হয়, শুধু ৮০ byte-এর জন্য না, যাতে পরের অনেক allocation syscall ছাড়াই পরিবেশন করা যায়
নতুন heap অঞ্চল থেকে chunk কেটে ফেরতuser pointer এখন এই নতুন অঞ্চলে — কিন্তু মনে রাখুন, গত লেসনের demand paging অনুযায়ী এই ঠিকানার physical frame এখনো বরাদ্দ হয়নি, প্রথম touch-এ একটা page fault ঘটবে

লক্ষ করুন শেষ ধাপ — sbrk() নিজেই কোনো physical memory বরাদ্দ করে না, শুধু virtual address space-এর সীমা বাড়ায়। গত লেসনের ভাষায় বললে, এটা ঠিক mmap()-এর মতোই lazy — malloc-এর ফেরত দেওয়া pointer touch না করা পর্যন্ত কোনো frame আসে না। malloc() সফল হওয়া মানেই memory “বরাদ্দ” হয়ে গেছে না — শুধু ঠিকানা reserve হয়েছে, ঠিক যেমন গত দুই লেসনে mmap()-এর ক্ষেত্রে দেখেছেন।

উদাহরণ

১০,০০০টা ৩২-byte allocation — overhead-এর হিসাব

ধরুন একটা প্রোগ্রাম ১০,০০০টা malloc(32) কল করে, কোনো free() ছাড়াই (একটা arena, একটা thread ধরে নিচ্ছি, coalescing-এর প্রশ্নই আসছে না কারণ কিছুই free হচ্ছে না)।

ব্যবহারকারীর চাওয়া মোট memory:

$10{,}000 \times 32\,\text{byte} = 320{,}000\,\text{byte} \approx 312.5\,\text{KB}$

বাস্তব chunk আকার — ৬৪-বিট glibc-তে একটা chunk-এর ন্যূনতম আকার ৩২ byte, header (size field, ৮ byte, prev_size পরের chunk-এর অংশ হিসেবে গণ্য হয় যদি এই chunk in-use থাকে) আর ১৬-byte alignment মিলিয়ে একটা ৩২-byte request বাস্তবে দাঁড়ায় প্রায় ৪৮ byte chunk-এ (৮ byte header + ৩২ byte data + ৮ byte alignment padding, প্রকৃত সংখ্যা glibc সংস্করণভেদে সামান্য বদলাতে পারে):

$10{,}000 \times 48\,\text{byte} = 480{,}000\,\text{byte} \approx 468.75\,\text{KB}$

Overhead অনুপাত:

$\frac{480{,}000 - 320{,}000}{320{,}000} = \frac{160{,}000}{320{,}000} = 50\%$

শুধু chunk header/alignment-এই ৫০% অতিরিক্ত memory — এটাই internal fragmentation-এর সরাসরি সংখ্যাভিত্তিক প্রমাণ, ছোট, বহু-সংখ্যক allocation-এ। এই কারণেই game engine, database-এর মতো ছোট, homogeneous object-ভারী সিস্টেম প্রায়ই নিজস্ব pool allocator ব্যবহার করে (একই আকারের হাজার হাজার object-এর জন্য একটা মাত্র বড় mmap, কোনো per-object header ছাড়াই) — এই লেসনের misconception সেকশনে এই প্যাটার্নটা আরও স্পষ্ট হবে।

Threshold তুলনা: এই একই ৩২৫,০০০ byte যদি একটা একক malloc(320000) কল হতো, সেটা MMAP_THRESHOLD (১২৮ KB = ১৩১,০৭২ byte)-এর বেশি, তাই সরাসরি mmap()। সেই একটা allocation-এর overhead শুধু page-round-up (৩২০,০০০ byte → ৩২১,৫৩৬ byte, নিকটতম 4KB-এর গুণিতকে) — মাত্র ০.৫%, ১০,০০০টা ছোট chunk-এর ৫০%-এর তুলনায় ১০০ গুণ কম আনুপাতিক অপচয়।

নিজে চালিয়ে দেখুন

EXPERIMENT

strace দিয়ে brk বনাম mmap-এর সীমা সরাসরি দেখুন

Linux (strace ইনস্টল করা থাকতে হবে)· ১৫ মিনিট

/* alloc_probe.c — একটা কমান্ড-লাইন আর্গুমেন্ট আকারে malloc করে,
 * তাতে লিখে (compiler optimize-away না করে), তারপর free করে।
 *
 * বানান: gcc -O0 -o alloc_probe alloc_probe.c
 * চালান: ./alloc_probe <bytes>
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv) {
    size_t n = atol(argv[1]);
    void *p = malloc(n);
    memset(p, 0x42, n);
    printf("allocated %zu byte at %p\n", n, p);
    free(p);
    return 0;
}

gcc -O0 -o alloc_probe alloc_probe.c

# ১০০ KB — MMAP_THRESHOLD (১২৮ KB)-এর নিচে
strace -e trace=brk,mmap ./alloc_probe 102400 2>&1 | grep -E "brk|mmap"

# ২০০ KB — MMAP_THRESHOLD-এর উপরে
strace -e trace=brk,mmap ./alloc_probe 204800 2>&1 | grep -E "brk|mmap"

১০০ KB-এর typical আউটপুট:

brk(NULL)                              = 0x55a1e2b3d000
brk(0x55a1e2b5e000)                    = 0x55a1e2b5e000    ← heap বাড়ল, malloc(102400)-এর জন্য

কোনো নতুন mmap দেখা যায় না (glibc নিজে চালু হওয়ার সময় কিছু mmap করে, সেগুলো এখানে ফিল্টার করা — শুধু আমাদের allocation-সংক্রান্ত entry দেখানো হয়েছে) — পুরো request brk-বর্ধিত heap থেকেই মেটানো হলো।

২০০ KB-এর typical আউটপুট:

mmap(NULL, 208896, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f3c4a1b0000

এবার কোনো heap-বৃদ্ধিকারী brk নেই — সরাসরি একটা mmap, আকার ২০৮,৮৯৬ byte (২০০ KB request-কে page-এ round up করে, আর glibc-র নিজস্ব bookkeeping header যোগ করে)। free() করার সময় (দেখতে strace -e trace=munmap যোগ করুন) এই অঞ্চল সরাসরি munmap() হয়ে যাবে — brk-ভিত্তিক allocation যা পারে না।

এটা কী প্রমাণ করে

একই কোড, শুধু allocation-এর আকার বদলালে glibc সম্পূর্ণ ভিন্ন syscall পথ বেছে নেয় — MMAP_THRESHOLD একটা তাত্ত্বিক সংখ্যা না, সরাসরি পর্যবেক্ষণযোগ্য।

EXPERIMENT

free() করার পরেও RSS কমে না — সরাসরি পরিমাপ

Linux· ২০ মিনিট

/* rss_hole.c — ১০০০টা ১ MB chunk allocate করে, শুধু প্রথমটা রেখে
 * বাকি সব free() করে — কিন্তু প্রথমটা (heap-এর সবচেয়ে নিচে) বেঁচে
 * থাকায় heap-এর top নামানো যায় না।
 *
 * বানান: gcc -O0 -o rss_hole rss_hole.c
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

static long rss_kb(void) {
    FILE *f = fopen("/proc/self/status", "r");
    char line[256];
    long kb = -1;
    while (fgets(line, sizeof(line), f))
        if (sscanf(line, "VmRSS: %ld kB", &kb) == 1) break;
    fclose(f);
    return kb;
}

int main(void) {
    printf("শুরুতে RSS = %ld KB\n", rss_kb());

    void *keep = NULL;
    void *ptrs[1000];
    for (int i = 0; i < 1000; i++) {
        ptrs[i] = malloc(1024 * 1024);
        memset(ptrs[i], 1, 1024 * 1024);   /* touch করে frame আনা */
        if (i == 0) keep = ptrs[i];        /* heap-এর একদম নিচেরটা রাখব */
    }
    printf("১০০০ MB allocate + touch করার পর RSS = %ld KB\n", rss_kb());

    for (int i = 1; i < 1000; i++) free(ptrs[i]);  /* প্রথমটা বাদে সব free */
    printf("৯৯৯টা free()-এর পর RSS = %ld KB\n", rss_kb());

    malloc_trim(0);
    printf("malloc_trim(0)-এর পর RSS = %ld KB\n", rss_kb());

    free(keep);
    return 0;
}

Typical আউটপুট:

শুরুতে RSS = 1800 KB
১০০০ MB allocate + touch করার পর RSS = 1026344 KB
৯৯৯টা free()-এর পর RSS = 1025928 KB
malloc_trim(0)-এর পর RSS = 2216 KB

৯৯৯টা free()-এর পরেও RSS প্রায় অপরিবর্তিত (~১ GB) — কারণ keep (heap-এর একদম নিচের chunk) এখনো live, আর তার উপরের সব free chunk থাকা সত্ত্বেও heap-এর top নামানো যায় না (এই লেসনের concept সেকশনের “স্ট্যাক” যুক্তি)। malloc_trim(0) ডাকার পর RSS হঠাৎ কমে যায় — কিন্তু লক্ষ করুন, এটা কাজ করল শুধু কারণ পরীক্ষাটা এমনভাবে সাজানো যে সব free chunk আসলে একটা একক, বিশাল contiguous অঞ্চল তৈরি করেছিল ঠিক heap-এর টপে (keep-এর ঠিক উপরেই)। বাস্তব প্রোগ্রামে live object-গুলো এলোমেলোভাবে ছড়ানো থাকলে (এই লেসনের earlier callout-এর দৃশ্য), malloc_trim এতটা কার্যকর হয় না — মাঝখানের hole-গুলো কখনোই trim-এর নাগালে আসে না।

এটা কী প্রমাণ করে

brk-ভিত্তিক heap-এ মাঝখানের object বেঁচে থাকলে, বাকি সব free করা সত্ত্বেও RSS প্রায় অপরিবর্তিত থাকে — malloc_trim() শুধু আংশিক সাহায্য করে, শুধু heap-এর একদম উপরের অংশে।

নিজে বানান

BUILD IT

একটা ৪০-লাইনের bump allocator — brk বনাম mmap দুইটা পথই দেখানো

C · ●●●○○

ছোট allocation-এর জন্য একটা brk-ভিত্তিক bump region রাখুন — sbrk() দিয়ে একটা বড় প্রাথমিক chunk নিয়ে ভেতরে ভেতরে bump করুন
একটা THRESHOLD ধ্রুবক ঠিক করুন (এই ডেমোতে ৬৪ KB) — তার বেশি request সরাসরি mmap করুন, স্বতন্ত্র
free() রাখুন সম্পূর্ণ no-op ছোট allocation-এর জন্য, কিন্তু mmap-করা বড় allocation ঠিকই munmap() করুন — দুইটা পথের ভিন্ন আচরণ প্রদর্শনের জন্য এটাই যথেষ্ট
পুরো ফাইলে ~৪০ লাইনের বেশি না রাখার চেষ্টা করুন — এটা একটা শিক্ষামূলক টুল, উৎপাদন allocator না

/* bump.c — brk বনাম mmap সিদ্ধান্ত দেখানোর জন্য একটা সর্বনিম্ন allocator।
 * ছোট request bump-allocated একটা brk region থেকে (free() কিছুই করে
 * না), বড় request সরাসরি mmap (free() সেটা munmap করে দেয়)।
 *
 * এটা coalescing, bin, বা fragmentation-প্রতিরোধ কিছুই করে না —
 * সম্পূর্ণ, উৎপাদন-মানের allocator-এর জন্য দেখুন Memory Allocator
 * প্রজেক্ট (bump → free list → boundary tag → size class)।
 */
#define _GNU_SOURCE
#include <unistd.h>
#include <sys/mman.h>
#include <stddef.h>

#define THRESHOLD (64 * 1024)
#define REGION    (4 * 1024 * 1024)

static char *base, *cur, *end;

static void init(void) {
    base = sbrk(REGION);
    cur = base;
    end = base + REGION;
}

void *my_malloc(size_t n) {
    n = (n + 15) & ~15UL;                       /* ১৬-byte align */

    if (n >= THRESHOLD) {                        /* বড় — সরাসরি mmap */
        size_t total = n + 16;                   /* সামনে আকার লিখে রাখব */
        void *m = mmap(NULL, total, PROT_READ | PROT_WRITE,
                        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if (m == MAP_FAILED) return NULL;
        *(size_t *)m = total;                    /* free()-এ munmap-এর আকার লাগবে */
        return (char *)m + 16;
    }

    if (!base) init();                           /* ছোট — bump region থেকে */
    if (cur + n > end) return NULL;               /* এই ডেমো heap বাড়ায় না */
    void *p = cur;
    cur += n;
    return p;
}

void my_free(void *p) {
    if (!p) return;
    /* bump region-এর ভেতরে হলে কিছুই করি না — no-op, ঠিক আগের
     * লেসনের প্রজেক্টের প্রথম ধাপের bump allocator-এর মতোই */
    if ((char *)p < base || (char *)p >= end) {
        void *m = (char *)p - 16;
        munmap(m, *(size_t *)m);                  /* mmap-করা — সরাসরি ফেরত */
    }
}

gcc -O0 -o bump_test bump.c   # একটা ছোট main() যোগ করে my_malloc(100) আর my_malloc(200000) পরীক্ষা করুন
strace -e trace=brk,mmap,munmap ./bump_test

strace আউটপুটে দেখবেন — প্রথম my_malloc(100)-এর আগে একটাই brk (পুরো ৪ MB region-এর জন্য, init()-এ), তারপর যত ছোট allocation করুন না কেন, আর কোনো নতুন brk/mmap না (bump region-এর ভেতরেই মেটে)। কিন্তু my_malloc(200000) (THRESHOLD-এর উপরে) সাথে সাথে একটা নতুন mmap তৈরি করবে, আর সংশ্লিষ্ট my_free()-এ একটা munmap।

এটা কেন সম্পূর্ণ allocator না

এই ৪০ লাইনে কোনো free-list নেই — ছোট allocation-এর free() কিছুই করে না, ঠিক memory-allocator প্রজেক্টের একদম প্রথম ধাপের মতো। কোনো coalescing নেই, কোনো fragmentation-প্রতিরোধ নেই, bump region একবার শেষ হয়ে গেলে আর বাড়ে না। উদ্দেশ্য শুধু একটাই জিনিস স্পষ্ট দেখানো — brk বনাম mmap-এর সিদ্ধান্ত, আর দুইটা পথের free()-আচরণের পার্থক্য। একটা প্রকৃত, ব্যবহারযোগ্য allocator লিখতে — header, free list, first-fit/best-fit, boundary-tag coalescing, size class, আর LD_PRELOAD দিয়ে সত্যিকারের প্রোগ্রামে চালানো পর্যন্ত — সম্পূর্ণ Memory Allocator প্রজেক্ট দেখুন, যা ঠিক এই লেসনের ধারণাগুলোর উপর দাঁড়িয়ে ধাপে ধাপে একটা production-grade allocator পর্যন্ত নিয়ে যায়।

বাস্তব সিস্টেমে

Redis, MySQL — glibc থেকে jemalloc-এ স্থানান্তর। Redis ডিফল্টভাবে jemalloc ব্যবহার করে Linux-এ (glibc malloc না) — কারণ Redis-এর workload (বহু ছোট, ভিন্ন-ভিন্ন-আকারের key/value, ঘন ঘন allocate/free) ptmalloc2-তে উল্লেখযোগ্য fragmentation তৈরি করত। jemalloc-এর size-class segregation একই ধরনের object-কে একসাথে রেখে এই fragmentation উল্লেখযোগ্যভাবে কমায়। MySQL-ও (বিশেষত InnoDB-ভারী workload-এ) প্রায়ই jemalloc বা tcmalloc-এর সাথে deploy হয়, প্রকাশিত benchmark-এ ২০-৩০% কম memory footprint দেখানো হয়েছে একই workload-এ।

LD_PRELOAD দিয়ে allocator বদলানো — কোনো recompile ছাড়াই। যেহেতু malloc/free একটা standard, dynamically-linked interface, LD_PRELOAD=/usr/lib/libjemalloc.so ./myapp চালালে পুরো প্রোগ্রামের allocator বদলে যায়, কোনো কোড পরিবর্তন বা recompile ছাড়াই — ঠিক এই লেসনের প্রজেক্টের LD_PRELOAD পরীক্ষার মতোই কৌশল, শুধু উল্টো দিকে (নিজের allocator না, একটা প্রতিষ্ঠিত বিকল্প)।

Container memory limit আর MALLOC_ARENA_MAX-এর surprise। একটা container-এ cgroup memory limit বেঁধে দেওয়া থাকলেও, glibc-র arena প্রতিটা নিজস্ব heap ধরে রাখে — বহু-core মেশিনে অনেকগুলো thread চালানো একটা প্রোগ্রাম 8 × ncpus পর্যন্ত arena তৈরি করতে পারে, প্রতিটা কয়েক MB ধরে রেখে, প্রকৃত ব্যবহৃত memory-র চেয়ে RSS অনেক বেশি দেখাতে পারে। এটা এমন একটা পরিচিত সমস্যা যে অনেক production deployment (Kubernetes-এ java/ruby/python অ্যাপ, যেখানে ইন্টারপ্রেটার নিজেও থ্রেড চালায়) MALLOC_ARENA_MAX=1 বা 2 সেট করে দেয়, arena সংখ্যা সীমাবদ্ধ রাখতে — একটা concurrency বনাম memory-overhead trade-off যা এই লেসনের arena আলোচনার সরাসরি প্রয়োগ।

Chrome/V8-এর PartitionAlloc, Firefox-এর mozjemalloc। বড় browser project প্রায়ই নিজস্ব allocator লেখে বা জেমালোক-জাতীয় কিছু integrate করে, কারণ browser-এর allocation pattern (বহু ছোট, স্বল্পস্থায়ী DOM/JS object) glibc-র default-এর তুলনায় ভিন্ন optimize-করা allocator থেকে উল্লেখযোগ্য লাভ পায় — PartitionAlloc এমনকি security-হার্ডেনিং (type-segregated allocation, use-after-free mitigation) একসাথে করে।

যে ভুলগুলো সবাই করে

“free() করলে সেই memory সাথে সাথে OS-কে ফেরত যায়।”

সাধারণত না। এই লেসনের experiment সরাসরি দেখিয়েছে — brk-ভিত্তিক heap-এ free() শুধু chunk-টাকে একটা bin-এ রাখে, ভবিষ্যতের allocation-এর জন্য পুনর্ব্যবহারের জন্য; OS-কে ফেরত (RSS কমা) যায় শুধু তখনই যখন heap-এর একদম উপরের অংশ পুরোপুরি free হয়, malloc_trim-এর মাধ্যমে (স্বয়ংক্রিয় বা ম্যানুয়াল)। মাঝখানের hole কখনো ফেরত যায় না। ব্যতিক্রম — বড়, mmap-করা allocation (≥ ১২৮ KB), যেখানে free() সরাসরি munmap() ডাকে, তাৎক্ষণিক, নিঃশর্ত ফেরত।

“malloc-এর প্রতিটা কল একটা syscall — তাই বহু ছোট allocation স্বাভাবিকভাবেই ধীর।”

উল্টো — malloc-এর পুরো ডিজাইনের একটা কেন্দ্রীয় লক্ষ্য syscall যতটা সম্ভব এড়ানো। hood সেকশনের LayerTrace-এ দেখা গেছে — tcache/fastbin/smallbin hit-এ কোনো syscall লাগেই না, শুধু একটা linked-list pop, কয়েক ন্যানোসেকেন্ড। sbrk()/mmap() ডাকা হয় শুধু তখনই যখন কোনো bin-এই পর্যাপ্ত free chunk নেই — আর তখনও glibc একবারে অনেকখানি (যেমন heap-এ একটা বড় increment) চেয়ে নেয়, যাতে পরবর্তী শত শত allocation কোনো syscall ছাড়াই মেটে। ১০,০০০টা malloc(32) কলে বাস্তবে হয়তো মাত্র একটা বা দুইটা sbrk() ঘটে।

“সব malloc বাস্তবায়ন কার্যত একই রকম — allocator বদলানো শুধু একটা cosmetic পরিবর্তন।”

Realworld সেকশনের Redis/MySQL উদাহরণ এটা সরাসরি খণ্ডন করে। ptmalloc2, jemalloc, tcmalloc, mimalloc-এর মধ্যে fragmentation-প্রতিরোধ কৌশল, thread-local caching-এর গভীরতা, আর arena-সংগঠন উল্লেখযোগ্যভাবে ভিন্ন — একই workload-এ ২০-৩০% memory footprint পার্থক্য অস্বাভাবিক না, বিশেষত দীর্ঘ-চলা, বহু-থ্রেডেড, বিচিত্র-আকারের allocation-mix সার্ভিসে। allocator বেছে নেওয়া একটা প্রকৃত performance-engineering সিদ্ধান্ত, শুধু পছন্দের প্রশ্ন না।

“একটা প্রোগ্রামের memory footprint ক্রমাগত বাড়তে থাকলে সেটা নিশ্চয়ই একটা memory leak।”

Fragmentation আর leak সম্পূর্ণ ভিন্ন সমস্যা, যদিও উপসর্গ একই রকম দেখায় (RSS ক্রমাগত বাড়া)। Leak মানে memory যার প্রতি আর কোনো reachable pointer নেই — সেই memory চিরকাল অব্যবহারযোগ্য থেকে যায়। Fragmentation মানে memory এখনো ব্যবহারযোগ্য, শুধু এমনভাবে ছড়ানো (এই লেসনের earlier callout-এর “১০টা live object, ~১০০০-এর সমান footprint” দৃশ্য) যে নতুন বড় request পরিবেশন করা কঠিন হয়ে পড়ে। দুইটার নির্ণয়ের টুল আলাদা — leak-এর জন্য valgrind --leak-check/ASan-এর leak detector (reachability analysis), fragmentation-এর জন্য malloc_stats()/jemalloc-এর নিজস্ব profiling (jeprof), যা allocated বনাম resident বনাম fragmented memory আলাদা করে দেখায়।

বুঝেছেন কি না দেখুন

একটা প্রোগ্রাম পরপর malloc(50000), malloc(150000), malloc(100) ডাকে (ডিফল্ট ১২৮ KB MMAP_THRESHOLD ধরে নিন)। প্রতিটা কল কোন পথে (brk-heap বা mmap) মেটানো হবে, আর কেন?

প্রয়োগ

প্রতিটার আকার MMAP_THRESHOLD (১৩১,০৭২ byte = ১২৮ KB)-এর সাথে তুলনা করি:

Call	আকার	MMAP_THRESHOLD-এর তুলনায়	পথ
`malloc(50000)`	৫০,০০০ byte	কম	brk-heap
`malloc(150000)`	১৫০,০০০ byte	বেশি (১৩১,০৭২-এর চেয়ে)	সরাসরি mmap
`malloc(100)`	১০০ byte	কম, অনেক	brk-heap

প্রথম আর তৃতীয় কল ছোট bin/heap থেকে মেটে, brk-বর্ধিত heap-এর অংশ। দ্বিতীয়টা threshold ছাড়িয়ে গেছে, তাই একটা স্বতন্ত্র mmap() তৈরি হবে — এই allocation-এর নিজস্ব VMA থাকবে, heap-এর সাথে কোনো সম্পর্ক ছাড়াই। যদি এই তিনটার প্রতিটা পরে free() হয় — প্রথম আর তৃতীয়টা heap-এর bin-এ ফিরে যাবে (RSS প্রায় অপরিবর্তিত), কিন্তু দ্বিতীয়টা সরাসরি munmap() হয়ে যাবে (RSS তাৎক্ষণিক কমবে ~১৫০ KB)।

ptmalloc2 fastbin-এ ইচ্ছাকৃতভাবে coalescing করে না, যদিও এটা fragmentation বাড়ানোর ঝুঁকি রাখে। কেন এই ডিজাইন সিদ্ধান্ত যুক্তিসঙ্গত?

যুক্তি

Fastbin-এর উদ্দেশ্য একটাই — সবচেয়ে দ্রুত সম্ভব allocate/free path প্রদান করা, ছোট, ঘন ঘন ব্যবহৃত আকারের জন্য (যেমন একটা linked-list node বারবার allocate/free হওয়া একটা tight loop-এ)। Coalescing-এ পাশের chunk-এর PREV_INUSE/আকার চেক করা, সম্ভাব্য bin পরিবর্তন করা — এই সবকিছু অতিরিক্ত instruction, আর ছোট, high-frequency allocation-এ এই overhead সহজেই allocation নিজের খরচের চেয়ে বড় হয়ে যেতে পারে।

Trade-off:

	Coalesce করলে	Coalesce না করলে (fastbin-এর নীতি)
প্রতিটা free()-এর খরচ	বেশি (পাশের chunk চেক + সম্ভাব্য merge)	কম — শুধু linked-list push
Fragmentation ঝুঁকি	কম	সাময়িকভাবে বেশি

সমাধান — deferred coalescing। ptmalloc2 fastbin-এর chunk-গুলো coalesce না করে জমতে দেয়, কিন্তু যখনই একটা larger request আসে যা কোনো bin-এই সরাসরি মেটে না, বা free()-এর একটা নির্দিষ্ট শর্ত মেটে, malloc_consolidate() ট্রিগার হয় — এক ধাক্কায় সব fastbin chunk coalesce করে দেয়। এটা একটা classic amortized cost কৌশল — প্রতিটা individual free()-কে সস্তা রাখা, আর প্রকৃত fragmentation-প্রতিরোধের কাজ ব্যাচ করে, শুধু তখনই, যখন সত্যিই দরকার (বড় request না মেটায়)।

Level 6-এর সংযোগ: এই “প্রতিটা operation-কে সস্তা রাখো, ভারী কাজ ব্যাচ করে periodic-ভাবে করো” প্যাটার্নটা amortized analysis-এর একটা ক্লাসিক উদাহরণ — dynamic array-র resize, বা এই মডিউলের গত লেসনের TLB shootdown-এর batching-ও একই নীতির প্রয়োগ। Level 6-এর algorithms module amortized analysis-এর আনুষ্ঠানিক গাণিতিক কাঠামো (potential method) দেখাবে।

আপনি একটা ২৪-core সার্ভারে একটা ভারী multi-threaded সার্ভিস চালাচ্ছেন যেখানে প্রতিটা thread প্রচুর ছোট, স্বল্পস্থায়ী allocation করে। ডিফল্ট glibc arena সেটিং (8 × ncpus = ১৯২ পর্যন্ত arena) ব্যবহার করবেন, নাকি MALLOC_ARENA_MAX=1 দিয়ে একটা মাত্র arena-য় বেঁধে দেবেন? Trade-off বিশ্লেষণ করুন।

ডিজাইন

দুইটা চরম বিকল্পের মধ্যে trade-off:

অনেকগুলো arena (ডিফল্ট, ১৯২ পর্যন্ত):

সুবিধা — প্রতিটা thread বেশিরভাগ সময় নিজস্ব (বা কম-শেয়ার্ড) arena পায়, lock contention কম, বিশেষত ২৪ core সমান্তরালে allocate/free করলে একটা single global lock হতো bottleneck।

অসুবিধা — প্রতিটা arena নিজস্ব heap ধরে রাখে (নিজস্ব bin-এর chunk, নিজস্ব top-chunk, নিজস্ব fragmentation)। ১৯২টা arena পর্যন্ত মানে memory ভারসাম্যহীনভাবে ছড়িয়ে যেতে পারে — কিছু arena-য় ভারী ব্যবহার, বাকিগুলো প্রায় খালি কিন্তু heap তবু ধরে রাখা। মোট RSS একটা single-arena সংস্করণের চেয়ে উল্লেখযোগ্যভাবে বেশি হতে পারে, বিশেষত যদি thread সংখ্যা সময়ের সাথে ওঠানামা করে (নতুন thread নতুন arena claim করে, পুরনো arena খালি হয়েও memory ধরে রাখে)।

একটা arena (MALLOC_ARENA_MAX=1):

সুবিধা — সব thread একই heap ভাগ করে, memory ব্যবহার tightly-packed, কোনো per-arena বাড়তি overhead নেই।

অসুবিধা — একটা মাত্র mutex, তাই ২৪টা thread একসাথে allocate/free করলে সেই lock-এই সবাই সারিবদ্ধ হয়ে যায় — throughput সরাসরি সীমাবদ্ধ।

	Default (বহু arena)	`MALLOC_ARENA_MAX=1`
Lock contention	কম	বেশি — ২৪ thread একটা mutex-এ
Memory overhead	বেশি (per-arena bookkeeping, ভারসাম্যহীনতা)	কম
উপযুক্ত workload	Allocation-heavy, memory যথেষ্ট পাওয়া যায়	Memory-সীমিত (container limit), throughput কম critical

বাস্তবসম্মত সিদ্ধান্ত — মাঝামাঝি একটা মান। সম্পূর্ণ ১৯২ arena বা সম্পূর্ণ ১টা — কোনোটাই প্রায়ই সেরা না। MALLOC_ARENA_MAX=4 বা ৮-এর মতো একটা মাঝারি সংখ্যা প্রায়ই ভালো ভারসাম্য দেয় — যথেষ্ট arena যাতে contention গুরুতর না হয়, কিন্তু সীমাবদ্ধ যাতে memory overhead নিয়ন্ত্রণে থাকে। এটা প্রোফাইল করে ঠিক করার বিষয় (perf lock contention দিয়ে lock-wait time মাপা, আর /proc/[pid]/status-এর VmRSS আলাদা arena-count-এ তুলনা করা), অনুমান করার বিষয় না।

Level 11-এর সংযোগ: এই lock-contention-বনাম-memory-overhead trade-off ঠিক একই আকৃতির যেমনটা Level 11-এর performance module thread-pool sizing-এ দেখাবে — বেশি worker মানে কম queueing কিন্তু বেশি per-worker overhead, ঠিক এখানকার বেশি-arena-মানে-কম-contention-কিন্তু-বেশি-memory প্যাটার্নের সমান্তরাল।

একটা প্রোগ্রাম চালু হয়ে ১ GB anonymous memory allocate করে touch করে, তারপর ৯৯৯ MB free করে, শুধু heap-এর একদম নিচের ১ MB বেঁচে থাকে। malloc_trim(0) ডাকার পর প্রত্যাশিত RSS কত হবে, আর কেন এই ফলাফল “memory leak” না?

প্রয়োগ

এই লেসনের RSS experiment-এর ঠিক বিপরীত বিন্যাস — এখানে বেঁচে-থাকা object heap-এর একদম নিচে, উপরে না। এটা গুরুত্বপূর্ণ পার্থক্য তৈরি করে:

malloc_trim() শুধু heap-এর একদম উপরের অংশ trim করতে পারে (brk শুধু top সীমা সরাতে পারে, স্ট্যাকের মতো)। এখানে ৯৯৯ MB free হওয়া অংশটা পুরোটাই বেঁচে-থাকা ১ MB-এর উপরে — অর্থাৎ heap-এর একদম টপ থেকে নিচের ঠিক ১ MB পর্যন্ত পুরোটাই free আর contiguous।

প্রত্যাশিত ফলাফল: malloc_trim(0) এই পুরো contiguous free অংশ চিনতে পারবে আর sbrk()-কে ঋণাত্মক increment দিয়ে ডাকবে — RSS নেমে আসবে প্রায় বেঁচে-থাকা ১ MB-এর কাছাকাছি (কিছু glibc bookkeeping overhead-সহ, ~১-২ MB)।

$\text{RSS}_{\text{trim-এর পর}} \approx 1\text{-}2\,\text{MB}, \quad \text{না যে } \sim 1000\,\text{MB}$

কেন এটা এই লেসনের RSS-experiment-এর ফলাফলের বিপরীত: সেই experiment-এ বেঁচে-থাকা chunk ছিল heap-এর নিচে (প্রথম allocation), তাই তার উপরের সব free chunk trim করা গিয়েছিল — এখানেও একই যুক্তি, কিন্তু চিহ্নিত করার বিষয়টা হলো “কে সবচেয়ে নিচে বেঁচে আছে” সেটাই নির্ধারণ করে কতটা trim সম্ভব, “মোট কতটা free হয়েছে” সেটা না।

কেন এটা memory leak না: কোনো pointer হারিয়ে যায়নি — প্রোগ্রাম ইচ্ছাকৃতভাবে ৯৯৯টা allocation free() করেছে, আর বাকি ১টা এখনো একটা valid pointer দিয়ে ধরে রাখা আছে (misconception সেকশনের সংজ্ঞা অনুযায়ী)। RSS-এর সাময়িক উচ্চতা (trim-এর আগে) fragmentation-এর ফল, leak-এর না — আর এই উদাহরণেই দেখা গেল fragmentation সবসময় স্থায়ী না, বিন্যাসের উপর নির্ভর করে কখনো কখনো সম্পূর্ণ trim-ও সম্ভব।

একটা game engine প্রতি frame-এ (৬০ FPS-এ, প্রতি ~১৬.৬৭ ms-এ একবার) হাজার হাজার ছোট, একই-আকারের temporary object (particle, collision-pair) allocate আর সাথে সাথেই free করে। glibc-র সাধারণ malloc/free ব্যবহার করবেন, নাকি একটা কাস্টম pool allocator লিখবেন? যুক্তি দিন।

ডিজাইন

এই workload-এর তিনটা বৈশিষ্ট্য বিশেষভাবে প্রাসঙ্গিক — সব object একই আকারের, allocation আর free প্রায় একসাথে (একটা frame-এর মধ্যেই), আর frequency অত্যন্ত বেশি (প্রতি ১৬.৬৭ ms-এ হাজার হাজার বার)।

glibc malloc/free ব্যবহার করলে:

tcache/fastbin hit হলে প্রতিটা কল সস্তা (~২০-৩০ ns), কিন্তু তবুও প্রতিটাতে একটা function-call boundary, size-encoding/decoding, bin bookkeeping — এই লেসনের example সেকশনের হিসাব অনুযায়ী প্রতিটা ছোট object-এ chunk header-এর জন্য উল্লেখযোগ্য internal fragmentation (৩২ byte object → ৪৮ byte chunk, ৫০% overhead)।
যদি bin-এর মধ্যে exact-fit না মেলে (বিভিন্ন আকারের object মিশে থাকলে), fragmentation জমতে পারে ফ্রেম-থেকে-ফ্রেমে, যদিও প্রতিটা ফ্রেম শেষে সব free হয়ে যায় — তাও bin bookkeeping-এর ওঠা-নামা একটা measurable overhead।

কাস্টম pool allocator (একটা বড় পূর্ব-বরাদ্দকৃত array + একটা free-index stack):

একটা single, বড় mmap/malloc region, ফ্রেমের শুরুতেই তৈরি — কোনো per-object header, কোনো bin lookup।
Allocate = একটা array-index pop (স্ট্যাক থেকে), free = push — উভয়ই কয়েক cycle, কোনো branch-heavy bin-selection logic ছাড়াই।
আরও ভালো — যদি সব object এক frame-এ তৈরি আর ধ্বংস হয়, একটা “arena reset” (শুধু free-index-কে শুরুতে ফিরিয়ে দেওয়া, প্রতিটা object আলাদা free() না করে) সম্ভব — $O(1)$ পুরো ফ্রেমের সব object মুক্ত করা, $O(n)$ না।

	glibc malloc/free	কাস্টম pool + frame-reset
Per-allocation খরচ	~২০-৩০ ns (tcache hit) + header overhead	কয়েক ns, কোনো header না
Per-frame cleanup	$O(n)$ পৃথক free()	$O(1)$ reset
Fragmentation	সম্ভাব্য, bin-mismatch-এ	নেই — সব object সমান আকার, একটানা array

সিদ্ধান্ত: এই নির্দিষ্ট workload-এর জন্য (homogeneous, frame-scoped, উচ্চ-frequency), একটা কাস্টম pool/arena allocator প্রায় সবসময় জেতে — এটাই কারণ প্রায় সব production game engine (Unreal-এর TMemPool, নিজস্ব frame allocator) এই প্যাটার্ন ব্যবহার করে, সাধারণ malloc সরাসরি hot path-এ কখনো রাখে না। সাধারণ নীতি: allocator-এর সাধারণ-উদ্দেশ্য ডিজাইন (glibc, jemalloc) যেকোনো আকার আর jীবনকাল সামলাতে পারার জন্য কিছুটা overhead মেনে নেয় — যখন আপনার workload-এর গঠন (আকার, jীবনকাল) আগে থেকেই নির্দিষ্টভাবে জানা, একটা বিশেষায়িত allocator সেই জ্ঞান কাজে লাগিয়ে সাধারণ-উদ্দেশ্য allocator-কে হারাতে পারে — Memory Allocator প্রজেক্টের “নিজেকে চ্যালেঞ্জ করুন” অংশের thread-per-arena আর debugging feature-গুলোও এই একই “specialize when you know the pattern” নীতির উদাহরণ।

এরপর কী

পরের লেসন — Stack বনাম heap, একসাথে দেখা

এই লেসনে আমরা heap-এর ভেতরের জগৎ দেখেছি — chunk, bin, arena, brk বনাম mmap। কিন্তু একটা প্রোগ্রামের memory-র আরেকটা প্রধান অঞ্চল — stack — সম্পূর্ণ ভিন্ন নিয়মে চলে, যা আগেই assembly মডিউলে (assembly/stack-frames-and-function-calls) দেখেছেন কিন্তু OS-এর দৃষ্টিকোণ থেকে না।

পরের লেসনে আমরা stack আর heap পাশাপাশি রেখে তুলনা করব — কেন stack allocation “বিনামূল্যে” (শুধু একটা register decrement, এই লেসনের chunk-header/bin-lookup ওভারহেডের বিপরীত), stack-এর ~৮ MB ulimit -s সীমা আর guard page কীভাবে stack overflow-কে একটা নিয়ন্ত্রিত SIGSEGV-তে পরিণত করে, alloca/VLA-র বিপদ, আর thread stack-এর আকার কীভাবে ঠিক করা হয়। আর sigaltstack/SA_ONSTACK দিয়ে stack overflow-কেই catch করার একমাত্র উপায় — নিজের হাতে বানাব।

Memory Allocation — malloc আসলে কী করে

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

brk/sbrk বনাম mmap — malloc-এর দুইটা উৎস

ptmalloc2-র ভেতরের গঠন — chunk, bin, coalescing

Arena — multi-threaded allocation-এ lock contention কমানো

Fragmentation — কেন free() করার পরেও RSS কমে না

jemalloc, tcmalloc, mimalloc — বিকল্প ডিজাইন

ভেতরে কী ঘটছে

একটা malloc(64) কল — bin থেকে bin, শেষে kernel পর্যন্ত

উদাহরণ

১০,০০০টা ৩২-byte allocation — overhead-এর হিসাব

নিজে চালিয়ে দেখুন

strace দিয়ে brk বনাম mmap-এর সীমা সরাসরি দেখুন

free() করার পরেও RSS কমে না — সরাসরি পরিমাপ

নিজে বানান

একটা ৪০-লাইনের bump allocator — brk বনাম mmap দুইটা পথই দেখানো

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

পরের লেসন — Stack বনাম heap, একসাথে দেখা

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

brk/sbrk বনাম mmap — malloc-এর দুইটা উৎস

ptmalloc2-র ভেতরের গঠন — chunk, bin, coalescing

Arena — multi-threaded allocation-এ lock contention কমানো

Fragmentation — কেন free() করার পরেও RSS কমে না

jemalloc, tcmalloc, mimalloc — বিকল্প ডিজাইন

⚙ভেতরে কী ঘটছেUnder the hood

একটা malloc(64) কল — bin থেকে bin, শেষে kernel পর্যন্ত

▶উদাহরণExample

১০,০০০টা ৩২-byte allocation — overhead-এর হিসাব

⌘নিজে চালিয়ে দেখুনExperiment

strace দিয়ে brk বনাম mmap-এর সীমা সরাসরি দেখুন

free() করার পরেও RSS কমে না — সরাসরি পরিমাপ

⚒নিজে বানানBuild it yourself

একটা ৪০-লাইনের bump allocator — brk বনাম mmap দুইটা পথই দেখানো

◉বাস্তব সিস্টেমেReal-world usage

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

পরের লেসন — Stack বনাম heap, একসাথে দেখা

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী