Foundationপ্রথম নীতি থেকে
LEVEL 4লেসন ১১/২৯অ্যাডভান্সড১ ঘণ্টা ২৫ মিনিট

TLB — Page Walk-এর খরচ থেকে বাঁচার ক্যাশ

The TLB: Caching the Page Walk

গত লেসনে দেখা চার-ধাপ page walk প্রতিটা মেমরি অ্যাক্সেসকে পাঁচ গুণ ব্যয়বহুল করে দিত — বাস্তবে তা হয় না, কারণ CPU-র ভেতরে একটা ছোট, অত্যন্ত দ্রুত associative cache (TLB) সাম্প্রতিক অনুবাদগুলো মনে রাখে। এই লেসনে TLB-র স্তরবিন্যাস (L1 iTLB/dTLB, L2 STLB), TLB reach-এর গণিত, বহু-core সিস্টেমে shootdown-এর ব্যয়, আর PCID কীভাবে context switch-কে সস্তা রাখে — সব হাতে-কলমে perf আর একটা নিজের-লেখা stride benchmark দিয়ে যাচাইযোগ্য।

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

  • TLB hit আর miss-এর মধ্যে খরচের পার্থক্য (প্রায় শূন্য cycle বনাম ১০০+ cycle) সংখ্যাসহ ব্যাখ্যা করতে পারবেন, আর কেন এই ক্যাশ ছাড়া গত লেসনের চার-ধাপ page walk প্রতিটা মেমরি অ্যাক্সেসকে পাঁচ গুণ ব্যয়বহুল করে দিত
  • একটা আধুনিক CPU-র L1 iTLB, L1 dTLB, আর L2 STLB-র entry সংখ্যা আর প্রতিটার ভূমিকা আলাদা করে বলতে পারবেন, বাস্তব Intel আর AMD মাইক্রোআর্কিটেকচারের সংখ্যাসহ
  • TLB reach = entries × page size সূত্র প্রয়োগ করে হিসাব করতে পারবেন কেন 4KB page মাত্র কয়েকশ কিলোবাইট থেকে কয়েক মেগাবাইট memory ঢাকে, আর huge page কীভাবে সেই সীমা কয়েকশ গুণ বাড়িয়ে দেয়
  • TLB shootdown কেন অনিবার্য আর multi-core সিস্টেমে IPI-র হিসাব দিয়ে দেখাতে পারবেন কেন এটা core সংখ্যা বাড়ার সাথে সাথে একটা scalability সমস্যা হয়ে ওঠে
  • ASID/PCID কীভাবে context switch-এ পুরো TLB flush এড়ায়, আর KPTI-র সাথে তার সম্পর্ক (কেন KPTI-র পরও PCID পুরো সমস্যা মেটায় না) যুক্তিসহ বর্ণনা করতে পারবেন
  • perf দিয়ে dTLB-load-misses সরাসরি মাপতে পারবেন, আর stride-ভিত্তিক একটা benchmark চালিয়ে নিজের মেশিনে cache cliff আর TLB cliff — দুইটা সম্পূর্ণ ভিন্ন প্রাচীর — আলাদা করে শনাক্ত করতে পারবেন

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

আগে এটা বুঝি

গত লেসনের হুড সেকশনে একটা অস্বস্তিকর হিসাব রেখে আসা হয়েছিল। একটা সাধারণ mov rax, [rbx] instruction-এ x86-64-র ৪-স্তর page walk লাগে PML4E, PDPTE, PDE, PTE — চারটা আলাদা memory access, তারপর তবেই আসল data-টা পাওয়া যায়। অর্থাৎ প্রতিটা মেমরি অ্যাক্সেস পাঁচ গুণ ব্যয়বহুল। যদি প্রতিটা access সত্যিই DRAM পর্যন্ত যেত (~৮০ ns), একটা সাধারণ pointer dereference-এ লাগত ৪০০ ns — একটা আধুনিক 3 GHz CPU-তে প্রায় ১২০০ cycle।

এই হিসাবে আজকের কোনো কম্পিউটারই চলত না। একটা সাধারণ লুপ যা প্রতি সেকেন্ডে কোটি কোটি মেমরি অ্যাক্সেস করে, সেটা যদি প্রতিটাতে ১২০০ cycle গুনত, তাহলে আধুনিক CPU-র ঘোষিত speed-এর কোনো মানেই থাকত না।

বাস্তবে হয় না, কারণ CPU-র pipeline-এর ভেতরে, register file-এর ঠিক পাশে, একটা ছোট কিন্তু অত্যন্ত দ্রুত hardware cache বসানো আছে যা সাম্প্রতিক ভার্চুয়াল-থেকে-ফিজিক্যাল অনুবাদগুলো মনে রাখে — এর নাম TLB (Translation Lookaside Buffer, নামটা ঐতিহাসিক আর কিছুটা বিভ্রান্তিকর, কিন্তু আসলে এটা শুধুই একটা cache)। একটা TLB hit-এ পুরো চার-ধাপ walk-টাই এড়ানো যায় — খরচ pipeline-এর ভেতরেই মিটে যায়, প্রায় শূন্য অতিরিক্ত cycle। বাস্তব প্রোগ্রামে hit rate ৯৯%-এর বেশি থাকে বলেই paging ব্যবহারযোগ্য থেকে যায়।

কিন্তু hit rate ৯৯%-এর বেশি রাখাটা এমনি এমনি হয় না — এটা একটা সীমিত সম্পদের হিসাব। একটা TLB-তে হাজার-দুয়েকের বেশি entry রাখা যায় না (কারণ, দেখা যাবে, associative lookup-এর খরচ entry সংখ্যার সাথে বাড়ে), আর প্রতিটা entry একটা নির্দিষ্ট আকারের page ঢাকে। এই দুইটা সীমা মিলে তৈরি হয় TLB reach — TLB একবারে কত মেমরি “মনে রাখতে” পারে তার একটা কড়া সীমা। এই লেসনে TLB-র গঠন, তার সীমা, আর সেই সীমার চারপাশে গড়ে ওঠা পুরো ইঞ্জিনিয়ারিং (huge page, shootdown, PCID) — সব খুলে দেখব।

মূল ধারণা

TLB কী — একটা associative অনুবাদ-ক্যাশ

TLB আসলে data cache-এরই একটা আত্মীয়, শুধু key-value জোড়াটা ভিন্ন। L1 data cache মনে রাখে (physical address → data), TLB মনে রাখে (virtual page number → physical frame number + অনুমতি বিট)। দুইটাই associative — একটা নির্দিষ্ট address কোন entry-তে যাবে সেটা কয়েকটা সম্ভাব্য জায়গার (way) মধ্যে সমান্তরালে খোঁজা হয়, একটা content-addressable memory (CAM)-এর মতো গঠনে।

একটা TLB entry-তে যা থাকে:

ক্ষেত্রকাজ
Virtual page number (tag)কোন page-এর অনুবাদ এটা
Physical frame numberকোথায় map হয়
R/W, U/S, NXগত লেসনের PTE-বিটগুলোর একটা কপি — permission check TLB-তেই হয়, page table আবার পড়তে হয় না
ASID/PCID ট্যাগকোন process-এর অনুবাদ এটা (নিচে বিস্তারিত)
Global বিটcontext switch-এও এই entry রাখা যাবে কিনা

গুরুত্বপূর্ণ পর্যবেক্ষণ — permission বিটগুলোও TLB-তে থাকে, তাই একটা write access-এ শুধু frame number-ই না, R/W বিটও TLB থেকে সরাসরি পড়া যায়। একটা protection fault (যেমন read-only page-এ লেখার চেষ্টা) TLB hit-এও ঘটতে পারে — page table আবার পড়তে হয় না।

তিন স্তরের TLB — L1 iTLB, L1 dTLB, L2 STLB

আধুনিক CPU একটাই TLB রাখে না — data cache-এর মতো এখানেও একটা ছোট-দ্রুত বনাম বড়-ধীর trade-off আছে, তাই একটা স্তরবিন্যাস:

                     CPU core
        ┌─────────────────────────────────┐
        │  execution unit → ভার্চুয়াল addr │
        └───────────────┬─────────┬───────┘
                         │         │
                   ┌─────▼───┐ ┌───▼─────┐
                   │ L1 iTLB │ │ L1 dTLB │   ~১ cycle, খুব ছোট
                   └─────┬───┘ └───┬─────┘
                         └────┬────┘
                         ┌────▼─────┐
                         │ L2 STLB  │            ~৭-১০ cycle, বড়, unified
                         └────┬─────┘
                    miss হলে  │
                         ┌────▼─────┐
                         │ page     │   গত লেসনের ৪-ধাপ walk,
                         │ walker   │   memory-তে PML4→PT
                         └────┬─────┘
                              │
                        ┌─────▼─────┐
                        │  L1d / L2 │  physical address দিয়ে
                        │  / L3 /   │  স্বাভাবিক cache lookup
                        │  DRAM     │
                        └───────────┘
TLB-র অবস্থান — pipeline আর memory hierarchy-র মাঝখানে, cache hierarchy-র সমান্তরালে।

Instruction fetch আর data access-এর জন্য আলাদা L1 TLB আছে, ঠিক যেমন L1i আর L1d cache আলাদা — কারণ দুইটার access pattern ভিন্ন (code sequential আর repetitive, data ছড়ানো)। L2-তে গিয়ে একটাই unified TLB (STLB — Shared/Second-level TLB) থাকে, code আর data দুইটার জন্যই।

বাস্তব সংখ্যা — Intel Ice Lake (Sunny Cove core, ১০ম প্রজন্ম Core, ২০১৯):

স্তর4KB page2MB/4MB page1GB page
L1 iTLB১২৮ entry, ৮-way১৬ entry, fully assoc.—
L1 dTLB৬৪ entry, ৪-way৩২ entry, ৪-way৪ entry, ৪-way
L2 STLB (unified)২০৪৮ entry, ১৬-way২০৪৮ entry-র সাথে ভাগ করেসাধারণত STLB-তে নেই

AMD Zen 3 (Ryzen 5000 সিরিজ, ২০২০) তুলনামূলক সংখ্যা:

স্তর4KB page2MB page
L1 dTLB৬৪ entry৬৪ entry
L1 iTLB৬৪ entry—
L2 TLB (unified)২০৪৮ entry (4KB+2MB ভাগ করে)—

দুইটা ভেন্ডরের সংখ্যা প্রায় একই মাত্রার — এটা কাকতালীয় না। L1 TLB-তে entry সংখ্যা ছোট রাখতেই হয়, কারণ এটাকে প্রতিটা memory access-এ ~১ cycle-এ সাড়া দিতে হয় (pipeline-এর ভেতরে, address generation-এর সাথে ওভারল্যাপ করে); associative lookup-এর latency entry সংখ্যা আর way সংখ্যার সাথে বাড়ে, তাই ৬৪-১২৮ entry-ই বাস্তবসম্মত ঊর্ধ্বসীমা।

TLB reach — entries × page size

এই একটা সূত্রই পুরো লেসনের কেন্দ্র:

TLB reach=entry সংখ্যা×page size\text{TLB reach} = \text{entry সংখ্যা} \times \text{page size}

গত লেসনে একটা টেবিল দেখা গিয়েছিল যেখানে ৬৪-entry TLB ধরে হিসাব করা হয়েছিল — এখন সেটা মনে করিয়ে দিই, আর তার সাথে L2 STLB (২০৪৮ entry) যোগ করি:

Page sizeL1 dTLB reach (৬৪ entry)L2 STLB reach (২০৪৮ entry)
4 KB২৫৬ KB৮ MB
2 MB১২৮ MB৪ GB*
1 GB৬৪ GB(সাধারণত STLB-তে ধরে না)

* বাস্তবে L2 STLB-র entry গুলো 4KB আর 2MB-র মধ্যে ভাগাভাগি হয়, তাই পুরো ২০৪৮ entry একসাথে শুধু huge page-এর জন্য পাওয়া যায় না — সংখ্যাটা তাত্ত্বিক ঊর্ধ্বসীমা।

২৫৬ KB — এইটাই আসল সমস্যা। একটা L1 data cache-ই সাধারণত ৩২-৪৮ KB, L2 cache ১-২ MB। অর্থাৎ একটা প্রোগ্রামের working set L2 cache-এ পুরোপুরি আঁটলেও, সেটা যদি এলোমেলোভাবে ২৫৬ KB-র বেশি জায়গা জুড়ে ছড়ানো থাকে, TLB miss হবে — ডেটা cache-এ আছে, কিন্তু তার ঠিকানা অনুবাদ করার entry TLB-তে নেই। এটা একটা সম্পূর্ণ আলাদা ধরনের “cliff”, cache hierarchy-র cliff থেকে আলাদা জায়গায় ঘটে। L2 STLB-র ৮ MB দিয়ে সেই সীমা কিছুটা বাড়ে, কিন্তু আজকের ডেটাসেট (GB-স্কেল database, ইনডেক্স, JVM heap) তুলনায় এটাও তুচ্ছ।

এইটাই huge page-এর আসল যুক্তি — গত লেসনে যা “page table স্মৃতি বাঁচায়” হিসেবে বলা হয়েছিল, বাস্তবে বড় ওয়ার্কলোডে সেটার চেয়ে বড় সুবিধা হলো TLB reach। ২ MB page-এ ৬৪ entry-র L1 dTLB ঢাকে ১২৮ MB, ২০৪৮ entry-র STLB (যদি পুরোটা 2MB-র জন্য ব্যবহৃত হয়) ঢাকতে পারে ৪ GB — ৫১২ গুণ বেশি reach, একই সংখ্যক hardware entry দিয়ে।

TLB miss-এর খরচ — hit বনাম miss বনাম fault

ঘটনাকোথায় মেটেখরচ
L1 TLB hitpipeline-এর ভেতরে~০ অতিরিক্ত cycle — address generation-এর সাথে ওভারল্যাপড
L2 STLB hit (L1 miss)on-chip, ছোট extra lookup~৭-১০ cycle
L2 STLB miss — page walk দরকারhardware page walker সক্রিয়~২০-৪০ cycle (উপরের table-গুলো cache-এ থাকলে) থেকে ~৩০০+ cycle (সব DRAM-এ গেলে)
Walk-এ P বিট = ০কোনো frame নেইpage fault — হাজার গুণ ব্যয়বহুল, পরের লেসনের বিষয়

লক্ষ করুন — “TLB miss” আর “page fault” এক জিনিস না। TLB miss মানে শুধু এই যে অনুবাদটা এই মুহূর্তে ক্যাশে নেই; page table-এ সেটা প্রায় সবসময়ই থাকে (entry present, P=1), শুধু walker-কে গিয়ে সেটা আনতে হবে। Page fault ঘটে শুধু তখনই যখন walk শেষে দেখা যায় mapping-টাই বৈধ না বা মেমরিতে নেই — সেটা পরের লেসনের কেন্দ্রীয় বিষয়।

TLB shootdown — একটা মূল্যবান কিন্তু ব্যয়বহুল বাধ্যবাধকতা

একটা multi-threaded process-এর সব thread একই page table ভাগ করে (একই mm_struct, Linux-এর ভাষায়)। প্রতিটা core নিজের TLB-তে সেই page table-এর নিজস্ব একটা ক্যাশে-করা কপি রাখে। এখন core ০-এ চলা একটা thread যদি munmap() ডাকে, বা mprotect() দিয়ে একটা page read-only করে দেয়, বা copy-on-write-এর পর একটা PTE বদলে দেয় — সেই মুহূর্তে core ১, ২, ৩-এর TLB-তে থাকা পুরনো entry ভুল হয়ে যায়। সেগুলো এখনো পুরনো (এবং হয়তো এখন-অবৈধ) frame-এর দিকে দেখাচ্ছে।

সমাধান একটাই — অন্য core-গুলোকে জোর করে জানানো। CPU-তে এর জন্য কোনো “broadcast invalidate” নেই (cache coherence protocol যেমন MESI-তে স্বয়ংক্রিয়ভাবে হয়, TLB-তে হয় না, কারণ TLB entry cache line-এর মতো snoop করা যায় না)। তাই OS-কে IPI (Inter-Processor Interrupt) পাঠাতে হয় প্রতিটা core-এ যেখানে সেই process চলছে বা চলেছে, প্রতিটা core নিজের invlpg (একটা entry) বা পুরো TLB flush চালায়, তারপর একটা acknowledgment পাঠায় — এটাই TLB shootdown।

খরচের হিসাব:

ধাপআনুমানিক খরচ
IPI পাঠানো + receiving core-এ interrupt handler-এ ঢোকা~১-৩ μs
Invalidate কার্যকর করা (এক entry বা পুরো flush)কয়েক cycle থেকে কয়েক হাজার cycle
Acknowledgment ফেরত, initiator-এর অপেক্ষাreceiving core-গুলোর মধ্যে সবচেয়ে ধীরটার সমান

একটা ৬৪-core মেশিনে একটা single munmap() কল যদি সব core-কে shootdown পাঠায়, আর প্রতিটা IPI round-trip ~২ μs লাগে, initiator core-কে ৬৩টা IPI-র response-এর জন্য অপেক্ষা করতে হয় — সিরিয়ালি পাঠালে ~১২৬ μs, যেটা একটা সাধারণ syscall-এর তুলনায় (~১ μs) শতগুণ বেশি। Nadav Amit-এর USENIX ATC ২০১৭ পেপার দেখিয়েছে বড়-core-count সিস্টেমে memory-ভারী multi-threaded workload-এ (JVM garbage collection, database buffer pool resize) kernel সময়ের একটা উল্লেখযোগ্য অংশ শুধু shootdown-এই যায়।

Linux-এর প্রশমনগুলো:

  1. Batching — mmu_gather কাঠামো একগুচ্ছ PTE বদল জমিয়ে রাখে, তারপর একবারে একটা shootdown পাঠায়, প্রতিটা বদলের জন্য আলাদা IPI না পাঠিয়ে।
  2. Range-based invalidate — পুরো TLB flush না করে শুধু বদলানো ঠিকানাগুলোর জন্য invlpg/invpcid (নির্দিষ্ট রেঞ্জ) ব্যবহার, যাতে বাকি valid entry-গুলো টিকে থাকে।
  3. Lazy TLB — যে core-এ ওই process কখনো চলেনি (বা চলছে না), সেখানে IPI পাঠানোর দরকার নেই — kernel প্রতিটা core-এ কোন mm সক্রিয় ছিল তার একটা bitmap রাখে (mm_cpumask) আর শুধু সেই core-গুলোতেই পাঠায়।
  4. Deferred flush kernel thread-এর জন্য — যখন kernel একটা “borrowed” mm ব্যবহার করে চলছে (কোনো userspace thread না), flush আরও পরে পাঠানো যায়।

ASID / PCID — context switch-কে flush থেকে বাঁচানো

গত লেসনে দেখা গিয়েছিল — CR3-এ নতুন মান লেখাই context switch-এর মূল কাজ। কিন্তু ঐতিহাসিকভাবে CR3 লেখা মানেই ছিল পুরো TLB flush — কারণ TLB entry-গুলোতে কোনো tag ছিল না বলে বোঝার উপায় ছিল না কোন entry কোন process-এর। প্রতিটা context switch-এর পরের কয়েক হাজার instruction cold TLB নিয়ে শুরু হতো, বারবার miss।

সমাধান একটা tag যোগ করা — সাধারণ নাম ASID (Address Space ID, ARM/RISC-V-এর পরিভাষা), x86-এ এর নাম PCID (Process Context ID)। CR3-এর নিচের ১২ বিটে একটা প্রসেস-নির্দিষ্ট সংখ্যা (০-৪০৯৫) বসানো হয়, আর প্রতিটা TLB entry-তে সেই ট্যাগ সংরক্ষিত থাকে। Lookup-এর সময় শুধু virtual page number না, PCID-ও মিলতে হয় — ফলে A আর B প্রসেসের entry পাশাপাশি TLB-তে থাকতে পারে, একে অপরকে না ভেঙে। Context switch তখন শুধু CR3 লেখা, flush ছাড়াই।

TLB miss-এর ভেতরের ধাপ — CAM lookup থেকে page walker আর replay পর্যন্ত
  1. mov rax, [rbx] — ভার্চুয়াল ঠিকানা তৈরি হলোexecution unit ধরে নিচ্ছে ঠিকানাটা 0x00007f3ab2c4d000-এর একটা page
  2. L1 TLB CAM lookup (সব way সমান্তরালে)virtual page number + বর্তমান PCID মেলানো হচ্ছে সব entry-র সাথে একসাথে — এটাই TLB-কে দ্রুত রাখে
  3. miss — PCID মেলেনি বা page number-ই নেইL1 dTLB-তে কোনো entry পাওয়া গেল না। L2 STLB-তে চেষ্টা — সেখানেও miss ধরে নিচ্ছি এই ট্রেসে
  4. page walker hardware সক্রিয় হলোএকটা dedicated state machine — কোনো software trap বা instruction fetch লাগে না x86-এ
  5. CR3 → PML4E → PDPTE → PDE → PTE (গত লেসনের ৪ ধাপ)প্রতিটা ধাপে একটা physical memory read, প্রতিটার নিজস্ব L1d/L2/L3 cache miss/hit সম্ভাবনা আছে
  6. TLB refillনতুন (VPN → PFN, permission, PCID) entry L1 dTLB-তে লেখা হলো — একটা পুরনো entry LRU-ভিত্তিক replacement-এ বাদ পড়ল
  7. instruction আবার চালানো (replay)এবার L1 TLB hit — অনুবাদ পাওয়া গেল, cache hierarchy-তে physical address দিয়ে data lookup শুরু

x86-এ page walker একটা hardware state machine — কোনো software trap বা exception জড়িত না TLB miss নিজে। এটা গুরুত্বপূর্ণ পার্থক্য কিছু পুরনো architecture (MIPS, পুরনো SPARC, কিছু RISC-V বাস্তবায়ন) থেকে, যেখানে TLB miss একটা software-managed trap — CPU একটা exception ছোঁড়ে, আর OS-এর একটা হ্যান্ডলার হাতে-কলমে page table হাঁটে, TLB refill instruction চালিয়ে entry বসায়। Software-managed TLB নমনীয় (page table ফরম্যাট OS নিজেই বেছে নিতে পারে), কিন্তু প্রতিটা miss-এ একটা পুরো exception handler চালানোর খরচ (হাজার-খানেক cycle) x86-এর hardware walker-এর (কয়েক-দশ থেকে কয়েক-শ cycle) চেয়ে অনেক বেশি। এই কারণেই x86, ARM64 — সবাই hardware-walked page table বেছে নিয়েছে।

ভেতরে কী ঘটছে

দুই স্তরের replacement — TLB-তে কোন entry বাদ যায়

L1 dTLB-র মতো ছোট, high-associativity গঠনে replacement সাধারণত true LRU বা তার কাছাকাছি একটা approximation (pseudo-LRU, tree-based) — কারণ মাত্র ৪-৮টা way-এর মধ্যে exact LRU রাখা সস্তা। L2 STLB-তে, যেখানে way সংখ্যা বেশি (১৬-way), সাধারণত একটা সস্তা approximation (NRU — Not Recently Used, বা random-এর কাছাকাছি কিছু) ব্যবহৃত হয়, কারণ পুরো LRU order রাখার hardware খরচ entry সংখ্যার সাথে দ্রুত বাড়ে।

এইখানে গত লেসনের misconception প্রসঙ্গটাই আবার আসে — LRU optimal না (Bélády’s OPT-এর প্রয়োজন হয় ভবিষ্যৎ জানা, যা অসম্ভব), কিন্তু temporal locality-র উপর ভরসা করে LRU-জাতীয় policy বাস্তবে ভালো কাজ করে। TLB replacement policy আসলে page replacement-এরই একটা ক্ষুদ্র, hardware-speed সংস্করণ — একই তাত্ত্বিক সীমাবদ্ধতা, শুধু স্কেল আলাদা (entry কয়েক ডজন-হাজার, বনাম page কয়েক লাখ-কোটি)।

Global বিট — kernel mapping-কে flush থেকে আড়াল করা

গত লেসনের PTE বিট-টেবিলে বিট ৮ ছিল G (Global)। যে entry-তে G=1, সেটা CR3 বদলালেও (PCID না থাকলেও) TLB থেকে মোছা হয় না — কারণ kernel mapping সব process-এ অভিন্ন, তাই সেটা invalid হওয়ার কোনো কারণ নেই process বদলালে। এটা PCID-র আগের যুগের একটা সস্তা আংশিক সমাধান ছিল, আর আজও ব্যবহৃত হয় সেই mapping-গুলোর জন্য যেগুলো সত্যিই সব প্রসেসে অভিন্ন (vDSO, kernel text)। KPTI-পরবর্তী যুগে global বিটের গুরুত্ব কমেছে, কারণ এখন user-mode page table-এ kernel mapping প্রায় নেই-ই।

উদাহরণ

একটা database lookup-এর AMAT — TLB স্তরসহ

ধরুন একটা in-memory B-tree ইনডেক্সে random lookup চলছে, প্রতিটা lookup একটা ভিন্ন, এলোমেলো ৪ KB page ছোঁয় (bad locality — B-tree node-গুলো memory-জুড়ে ছড়ানো)। মোট ইনডেক্সের আকার ৫০০ MB।

৪ KB page-এ:

মোট page সংখ্যা=500 MB4 KB=128,000\text{মোট page সংখ্যা} = \frac{500\,\text{MB}}{4\,\text{KB}} = 128{,}000

এটা L1 dTLB reach (৬৪ entry = ২৫৬ KB, অর্থাৎ মাত্র ৬৪ page) আর L2 STLB reach (২০৪৮ entry = ৮ MB, অর্থাৎ ২০৪৮ page) — দুইটার চেয়েই বহুগুণ বড়। এলোমেলো access pattern-এ কার্যত প্রতিটা lookup একটা পূর্ণ page walk ঘটায়:

উপাদানখরচ (cycle)
Page walk (কিছু স্তর cache-এ, কিছু না)~১৫০ (আনুমানিক গড়)
আসল data access (B-tree node, সাধারণত cache miss)~১০০ (L2/L3 miss ধরে)
মোট~২৫০ cycle প্রতি lookup

২ MB huge page-এ:

মোট huge page সংখ্যা=500 MB2 MB=250\text{মোট huge page সংখ্যা} = \frac{500\,\text{MB}}{2\,\text{MB}} = 250

২৫০ page, L2 STLB-র ২০৪৮ entry ক্ষমতার তুলনায় অনেক ছোট — warm-up-এর পর প্রায় সবসময় L2 STLB hit (walk লাগে না):

উপাদানখরচ (cycle)
L2 STLB hit~৮
আসল data access~১০০ (অপরিবর্তিত — data locality বদলায়নি)
মোট~১০৮ cycle প্রতি lookup

তাত্ত্বিক speedup ≈ ২৫০ ÷ ১০৮ ≈ ২.৩ গুণ, যদি TLB-ই একমাত্র বাধা হতো।

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

EXPERIMENT

একই ৮ MB working set, দুই ধরনের stride — cache-cliff বনাম TLB-cliff

Linux, perf ইনস্টল করা থাকতে হবে (`sudo apt install linux-tools-generic` বা সমতুল্য)· ২৫ মিনিট

একটা pointer-chasing প্রোগ্রাম — Sattolo’s algorithm দিয়ে একটা single-cycle random permutation বানিয়ে, সেটার মধ্য দিয়ে হাঁটে। Compiler prefetcher-কে ফাঁকি দিতে এই কৌশলটাই দরকার, কারণ প্রতিটা পরের ঠিকানা আগেরটার data-র উপর নির্ভরশীল (একটা true dependency chain)।

/* walk.c — n_slots টা slot, stride বাইট দূরত্বে, একটা random single-cycle
 * permutation-এর মধ্য দিয়ে pointer-chase।
 *
 * ব্যবহার: ./walk <n_slots> <stride_bytes> <passes>
 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>

int main(int argc, char **argv) {
    size_t n      = atol(argv[1]);
    size_t stride = atol(argv[2]);
    long   passes = atol(argv[3]);
    size_t total  = n * stride;

    char *buf = mmap(NULL, total, PROT_READ | PROT_WRITE,
                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (buf == MAP_FAILED) { perror("mmap"); return 1; }

    size_t *idx = malloc(n * sizeof(size_t));
    for (size_t i = 0; i < n; i++) idx[i] = i;
    srand(1);
    for (size_t i = n - 1; i > 0; i--) {          /* Sattolo shuffle */
        size_t j = rand() % i;
        size_t t = idx[i]; idx[i] = idx[j]; idx[j] = t;
    }
    for (size_t i = 0; i < n; i++)
        *(char **)(buf + idx[i] * stride) = buf + idx[(i + 1) % n] * stride;
    free(idx);

    char *p = buf;
    for (long it = 0; it < passes * (long)n; it++) p = *(char **)p;

    if (p == (char *)1) printf("unreachable\n");  /* optimize-away প্রতিরোধ */
    return 0;
}
gcc -O2 -o walk walk.c

# রান ১ — page-granularity: ২০৪৮ slot × ৪KB = ৮ MB span, কিন্তু আসল data মাত্র ১৬ KB
perf stat -e cache-references,cache-misses,dTLB-loads,dTLB-load-misses \
    ./walk 2048 4096 50

# রান ২ — cache-line-granularity: একই ৮ MB span, কিন্তু আসল data ~১ MB
perf stat -e cache-references,cache-misses,dTLB-loads,dTLB-load-misses \
    ./walk 131072 64 50

রান ১-এর typical আউটপুট (মেশিনভেদে বদলাবে, প্যাটার্নটা লক্ষ করুন):

       102,400      dTLB-loads
        98,754      dTLB-load-misses         #   96.43% of all dTLB loads
         8,192      cache-references
           412      cache-misses              #    5.03% of all cache refs

রান ২-এর typical আউটপুট:

     6,553,600      dTLB-loads
       103,808      dTLB-load-misses          #    1.58% of all dTLB loads
     6,553,600      cache-references
     1,884,672      cache-misses              #   28.76% of all cache refs

দুইটা রানেই ভার্চুয়াল span একই (৮ MB), আর দুইটাতেই touch করা distinct page সংখ্যা প্রায় একই (২০৪৮)। কিন্তু রান ১-এ dTLB-miss অনুপাত প্রাধান্য পায় (৯৬%), কারণ প্রতিটা access-ই নতুন page (মাত্র ১৬ KB আসল data, L1 cache-এ অনায়াসে আঁটে, তাই cache-miss নগণ্য)। রান ২-এ cache-miss অনুপাত প্রাধান্য পায় (২৯%), কারণ একই ২০৪৮টা page-এর মধ্যেই বহুগুণ বেশি (৬৪ গুণ) access ঘটছে — TLB miss সংখ্যা প্রায় একই থাকে, কিন্তু total load সংখ্যা ৬৪ গুণ বেশি হওয়ায় অনুপাতে diluted হয়ে যায়, আর ~১ MB আসল touched data L1/L2 cache-এর সীমা ছাড়িয়ে যায়। দুইটা সম্পূর্ণ ভিন্ন প্রাচীর, একই ভার্চুয়াল footprint থেকে।

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

একই পরিমাণ ভার্চুয়াল স্থান জুড়ে থাকা দুইটা ভিন্ন access pattern সম্পূর্ণ ভিন্ন hardware কাউন্টার-স্বাক্ষর তৈরি করে — একটাতে dTLB-miss প্রাধান্য পায়, আরেকটাতে cache-miss। এই দুইটা যে সত্যিই আলাদা প্রাচীর, একটা না, তার সরাসরি প্রমাণ।

EXPERIMENT

Transparent huge pages চালু করে dTLB-miss অনুপাত মাপুন

Linux, root দরকার· ১৫ মিনিট

আগের experiment-এর walk বাইনারিই ব্যবহার করব, কোনো কোড না বদলে — শুধু kernel-ব্যাপী THP নীতি বদলে দেব। যেহেতু mmap করা ৮ MB অঞ্চলটা 2MB-সারিবদ্ধ, THP always মোডে সেটাকে স্বয়ংক্রিয়ভাবে huge page দিয়ে backing করবে।

cat /sys/kernel/mm/transparent_hugepage/enabled
always madvise [never]
echo always | sudo tee /sys/kernel/mm/transparent_hugepage/enabled

perf stat -e cache-references,cache-misses,dTLB-loads,dTLB-load-misses \
    ./walk 2048 4096 50

grep AnonHugePages /proc/meminfo
       102,400      dTLB-loads
           418      dTLB-load-misses          #    0.41% of all dTLB loads
         8,192      cache-references
           436      cache-misses              #    5.32% of all cache refs

AnonHugePages:      8192 kB

AnonHugePages: 8192 kB মানে পুরো ৮ MB অঞ্চলটা এখন চারটা 2MB page দিয়ে backed — গত পরীক্ষার আগের রান ১-এর সাথে তুলনা করলে dTLB-load-miss অনুপাত ৯৬.৪৩% থেকে ০.৪১%-এ, প্রায় ২৩৫ গুণ কম। ৮ MB span আগে ২০৪৮টা TLB entry দাবি করত (STLB-র পুরোটা), এখন মাত্র ৪টা — L1 dTLB-র 2MB-জন্য নির্ধারিত অংশেই আঁটে।

পরীক্ষার পর ফিরিয়ে দিন:

echo madvise | sudo tee /sys/kernel/mm/transparent_hugepage/enabled
এটা কী প্রমাণ করে

একই কোড, একই ওয়ার্কলোড — শুধু kernel-কে বড় page দিয়ে backing করতে বলায় dTLB-miss অনুপাত ৯৬% থেকে প্রায় শূন্যে নেমে আসে, কারণ ৮ MB এখন মাত্র চারটা 2MB page, যা কয়েকটা TLB entry-তেই আঁটে।

নিজে বানান

BUILD IT

TLB reach sweep — নিজের মেশিনের প্রকৃত cliff খুঁজে বের করুন

C · ●●●●○
  1. পূর্ববর্তী experiment-এর walk.c-কে একটা sweep-এ পরিণত করুন — বাড়তে থাকা slot সংখ্যার জন্য বারবার বেঞ্চমার্ক চালান
  2. প্রতিটা sweep পয়েন্টে ns/access মাপুন, আর টেবিল আকারে ছাপুন working-set-size বনাম latency
  3. sweep-এর ফলাফলে ২৫৬ KB আর ৮ MB-র কাছাকাছি latency-র লাফ শনাক্ত করুন — এগুলোই L1 dTLB আর L2 STLB reach-এর সীমা
  4. একই sweep madvise(MADV_HUGEPAGE)-সহ চালান, ২ MB stride দিয়ে, আর দেখুন cliff কতদূর সরে যায়
  5. perf stat দিয়ে প্রতিটা sweep পয়েন্টে dTLB-load-misses যোগ করুন, latency আর miss-rate-এর সম্পর্ক নিশ্চিত করুন
/* tlb_reach.c — TLB reach সরাসরি পরিমাপ: বাড়তে থাকা working-set-size-এ
 * pointer-chase চালিয়ে ঠিক কোথায় latency লাফ দেয় সেটা টেবিল আকারে দেখায়।
 *
 * বানান:   gcc -O2 -o tlb_reach tlb_reach.c
 * চালান:   ./tlb_reach            (4KB page stride)
 *          ./tlb_reach --huge     (2MB huge-page stride, THP madvise)
 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/mman.h>

static double now_ns(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1e9 + ts.tv_nsec;
}

/* একটা single-cycle random permutation — pointer-chase কখনো ছোট
 * loop-এ আটকে যাবে না, প্রতিটা slot ঠিক একবার ছোঁয়া হবে */
static void sattolo_shuffle(size_t *idx, size_t n) {
    for (size_t i = n - 1; i > 0; i--) {
        size_t j = rand() % i;
        size_t t = idx[i]; idx[i] = idx[j]; idx[j] = t;
    }
}

static double bench(size_t n_slots, size_t stride, int huge) {
    size_t total = n_slots * stride;
    char *base = mmap(NULL, total, PROT_READ | PROT_WRITE,
                       MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (base == MAP_FAILED) { perror("mmap"); exit(1); }
    if (huge) madvise(base, total, MADV_HUGEPAGE);

    size_t *idx = malloc(n_slots * sizeof(size_t));
    for (size_t i = 0; i < n_slots; i++) idx[i] = i;
    sattolo_shuffle(idx, n_slots);

    /* প্রতিটা slot-এর প্রথম ৮ বাইটে পরের slot-এর ঠিকানা — permutation-টাই
     * একটা linked list হয়ে গেল */
    for (size_t i = 0; i < n_slots; i++) {
        size_t next = idx[(i + 1) % n_slots];
        *(char **)(base + idx[i] * stride) = base + next * stride;
    }
    free(idx);

    char *p = base;
    for (size_t i = 0; i < n_slots; i++) p = *(char **)p;   /* warm-up */

    size_t rounds = (n_slots < 4096) ? 200 : 20;
    size_t iters  = rounds * n_slots;

    double t0 = now_ns();
    for (size_t i = 0; i < iters; i++) p = *(char **)p;
    double t1 = now_ns();

    if (p == (char *)1) printf("unreachable\n");  /* optimize-away প্রতিরোধ */
    munmap(base, total);
    return (t1 - t0) / iters;
}

int main(int argc, char **argv) {
    int huge = (argc > 1 && strcmp(argv[1], "--huge") == 0);
    size_t stride = huge ? (2UL * 1024 * 1024) : 4096UL;

    size_t slot_counts[] = {16, 32, 64, 128, 256, 512, 1024,
                             2048, 4096, 8192, 16384, 32768};

    printf("%-10s %-14s %-10s\n", "slots",
           huge ? "reach(MB)" : "reach(KB)", "ns/access");
    for (size_t k = 0; k < sizeof(slot_counts)/sizeof(*slot_counts); k++) {
        size_t n = slot_counts[k];
        double ns    = bench(n, stride, huge);
        double reach = huge ? (double)(n * stride) / (1024.0*1024.0)
                             : (double)(n * stride) / 1024.0;
        printf("%-10zu %-14.1f %-10.2f\n", n, reach, ns);
    }
    return 0;
}

./tlb_reach-এর typical আউটপুট (4KB stride, মেশিনভেদে সংখ্যা বদলাবে, প্যাটার্নটা লক্ষ করুন):

slots      reach(KB)      ns/access
16         64.0           1.12
32         128.0          1.15
64         256.0          1.31          ← L1 dTLB reach (৬৪ entry)-এর ঠিক কাছে
128        512.0          3.84          ← প্রথম cliff — L1 dTLB miss শুরু, L2 STLB hit
256        1024.0         4.02
512        2048.0         4.15
1024       4096.0         4.31
2048       8192.0         4.58          ← L2 STLB reach (২০৪৮ entry)-এর ঠিক কাছে
4096       16384.0        27.63         ← দ্বিতীয় cliff — পূর্ণ page walk শুরু
8192       32768.0        29.14
16384      65536.0        31.02
32768      131072.0       30.87

দুইটা লাফ স্পষ্ট: ৬৪ slot (২৫৬ KB)-এর কাছে latency প্রায় তিন গুণ বাড়ে (L1 dTLB reach ছাড়িয়ে গেল, এখন L2 STLB-তে যেতে হচ্ছে), আর ২০৪৮ slot (৮ MB)-এর কাছে আরেকবার প্রায় ছয় গুণ বাড়ে (L2 STLB reach ছাড়িয়ে গেল, এখন প্রতিটা access পূর্ণ page walk চাইছে)। এই দুইটা সংখ্যা — ২৫৬ KB আর ৮ MB — ঠিক এই লেসনের গোড়ার সূত্র থেকে হিসাব করা মান।

./tlb_reach --huge-এ (THP always মোডে) একই দুইটা cliff প্রায় ৫১২ গুণ দূরে সরে যায় — প্রথমটা ~১২৮ MB-র কাছে, দ্বিতীয়টা ~৪ GB-র কাছে, কারণ এখন প্রতিটা entry ৪ KB-র বদলে ২ MB ঢাকছে।

নিজে বাড়ান

  1. perf যোগ করুন। প্রতিটা sweep পয়েন্টে perf stat -e dTLB-load-misses,dTLB-loads-এর ফলাফল একই টেবিলে একটা কলাম হিসেবে যোগ করুন — latency লাফ আর miss-rate লাফ ঠিক একই slot সংখ্যায় ঘটছে কিনা যাচাই করুন।
  2. 1GB huge page (hugetlbfs) দিয়ে আরও দূরে যান। mmap করার সময় MAP_HUGETLB | MAP_HUGE_1GB flag ব্যবহার করে stride আরও বাড়িয়ে দেখুন cliff কতদূর সরে।
  3. Multi-thread চালান। কয়েকটা thread একসাথে বেঞ্চমার্ক চালিয়ে দেখুন effective TLB reach কমে কিনা — TLB per-core, তাই thread-গুলো যদি একই core-এ schedule না হয়, প্রতিটার নিজস্ব ছোট TLB-র জন্য লড়াই করতে হয় না, কিন্তু hyperthread-এর দুই সিবলিং একই L1 TLB ভাগ করে (SMT-তে)।
  4. ARM64-এ চালিয়ে তুলনা করুন। Raspberry Pi বা একটা ARM64 VM-এ একই প্রোগ্রাম চালিয়ে দেখুন cliff কোথায় ঘটে — granule size (৪ KB/১৬ KB/৬৪ KB) ভিন্ন হলে TLB entry সংখ্যাও ভিন্ন, তাই সংখ্যাগুলো মিলবে না, কিন্তু “দুইটা cliff” প্যাটার্নটা থাকবে।
  5. --huge-এ AnonHugePages না বাড়লে ডিবাগ করুন। THP মোড madvise-এ থাকলে --huge flag কাজ করবে না যদি madvise(MADV_HUGEPAGE) কল-টাই বাদ থাকে — কোডে চেক করুন, তারপর /proc/self/smaps-এ AnonHugePages লাইন পড়ে নিশ্চিত হন প্রতিটা sweep পয়েন্টের জন্য।

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

JVM আর GC — TLB shootdown-এর সবচেয়ে বড় ভুক্তভোগী। Java-র generational garbage collector নিয়মিতভাবে বড় memory region-এর protection বদলায় (young generation compact, card table আপডেট) — প্রতিটা বদল সম্ভাব্য একটা shootdown। বড়-heap, বহু-core JVM ডিপ্লয়মেন্টে (৩২+ core) GC pause-এর একটা অংশ শুধু shootdown IPI-র জন্য অপেক্ষায় যায়। এই কারণেই OpenJDK-র -XX:+UseTransparentHugePages আর -XX:+AlwaysPreTouch ফ্ল্যাগ দুইটাই সরাসরি TLB চাপ কমানোর চেষ্টা — Pretouch করে সব heap page আগেভাগে fault-in করিয়ে নেয় (পরের লেসনের demand paging বিষয়) যাতে চলার সময় নতুন mapping তৈরি, আর তার সাথে shootdown, কম ঘটে।

Redis আর fork()-এর সময় TLB চাপ। Redis-এর background save (BGSAVE) fork() করে; সন্তান প্রসেসের copy-on-write শুরু হওয়ার সাথে সাথে বাবা প্রসেসের প্রতিটা write একটা নতুন PTE বদল ঘটায়, আর প্রতিটা বদলই সম্ভাব্য shootdown-প্রার্থী (যদিও একক-থ্রেডেড Redis-এ shootdown কম গুরুত্বপূর্ণ, কারণ কোনো sibling core আপডেট করা mapping ব্যবহার করছে না)। তবু THP চালু থাকলে একটা ২ MB region-এ একটা বাইট লেখাই পুরো ২ MB copy আর remap ঘটায় — গত লেসনের misconception অংশে যা বলা হয়েছিল, এটা তারই TLB-স্তরের প্রতিফলন।

Nested paging-এ TLB-র ভূমিকা — VPID। গত লেসনের realworld অংশে “two-dimensional page walk”-এর কথা বলা হয়েছিল — একটা VM-এর মধ্যে একটা TLB miss-এ ২৪টা পর্যন্ত memory access লাগতে পারে। VMWare/KVM-এর মতো hypervisor তাই TLB entry-তে একটা অতিরিক্ত ট্যাগ যোগ করে — Intel-এর VPID (Virtual Processor ID), যা ঠিক PCID-র মতোই কাজ করে কিন্তু guest-এর বদলে — VM switch-এও পুরো TLB flush এড়ানো যায়। VPID ছাড়া প্রতিটা VM exit/entry একটা পূর্ণ flush ঘটাত, ভার্চুয়ালাইজেশনের overhead আরও বাড়িয়ে দিত। Level 12-এর cloud module VPID আর nested paging একসাথে বিস্তারিত দেখবে।

perf mem আর page-walk counter — production-এ TLB চাপ শনাক্ত করা। বড় সার্ভিসের performance engineer-রা নিয়মিতভাবে dtlb_load_misses.walk_completed আর dtlb_load_misses.walk_active কাউন্টার মনিটর করেন — যদি একটা service-এর “cycles per instruction” হঠাৎ বাড়ে কিন্তু cache-miss কাউন্টার স্বাভাবিক থাকে, প্রথম সন্দেহ হয় TLB। Netflix, Google-এর প্রকাশিত performance ইঞ্জিনিয়ারিং ব্লগে এই ধরনের “TLB-miss-bound” workload শনাক্তকরণ একটা স্ট্যান্ডার্ড ডায়াগনস্টিক ধাপ — Level 11-এর performance module এই workflow-টা হাতে-কলমে দেখাবে।

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

“TLB miss মানেই page fault — দুইটা একই জিনিস।”

সম্পূর্ণ ভুল, আর এই গুলিয়ে ফেলাটা এই লেসনের পুরো যুক্তিটাই এলোমেলো করে দেয়। TLB miss মানে শুধু এই যে অনুবাদটা এই মুহূর্তে CPU-র ক্যাশে নেই — page table-এ সেটা প্রায় সবসময়ই বৈধভাবে আছে (P=1), শুধু hardware page walker-কে গিয়ে সেটা তুলে আনতে হবে। এই লেসনের বেঞ্চমার্কে দেখা গেছে TLB miss-এর খরচ ~২০-৩০০ cycle — লক্ষণীয়, কিন্তু সহনীয়।

Page fault ঘটে শুধু তখনই যখন walk শেষে দেখা যায় mapping-টাই অবৈধ (P=0) — page-টা কখনো ছোঁয়া হয়নি (demand paging), swap-এ পাঠানো হয়েছে, বা আদৌ map করা হয়নি (segfault)। এর খরচ TLB miss-এর চেয়ে হাজার গুণ বেশি (~১-৫ μs, কারণ পুরো OS-এ trap নিতে হয়)। TLB miss হার্ডওয়্যারেই মেটে, page fault OS-এর হস্তক্ষেপ দাবি করে — এই পার্থক্যটাই পরের লেসনের কেন্দ্রীয় বিষয়।

“TLB যত বড় হবে, তত ভালো — hardware-এ শত হাজার entry রাখা উচিত ছিল।”

বড় TLB মানে বেশি associative lookup, আর associative lookup-এর latency আর power খরচ entry সংখ্যার সাথে বাড়ে — ঠিক যেমন একটা বড় fully-associative cache ধীর হয়ে যায়। L1 dTLB-কে প্রতিটা memory access-এ ~১ cycle-এ সাড়া দিতে হয়, pipeline-এর address-generation ধাপের সাথে ওভারল্যাপ করে — এটাই তাকে ৬৪-১২৮ entry-র মধ্যে বেঁধে রাখে।

সমাধান বড় TLB না, স্তরবিন্যাস — ঠিক cache hierarchy-র মতো। L1 ছোট-দ্রুত (৬৪ entry, ~১ cycle), L2 STLB বড়-তুলনামূলক ধীর (২০৪৮ entry, ~৭-১০ cycle)। এই দুইটা মিলে বেশিরভাগ workload-এর জন্য যথেষ্ট reach দেয়, কোনো একক স্তরকে অবাস্তব বড় না করেই। যেখানে আরও বেশি reach দরকার, উত্তর entry সংখ্যা বাড়ানো না — page size বাড়ানো (huge page), কারণ reach = entries × page size-এ page size-এর গুণিতক (৫১২ গুণ, 4KB থেকে 2MB-তে) entry সংখ্যা বাড়ানোর চেয়ে অনেক সস্তা।

“শুধু data access TLB miss করাতে পারে — instruction fetch নিরাপদ।”

প্রতিটা instruction fetch-ও একটা virtual-থেকে-physical অনুবাদ দাবি করে, আর সেটার জন্য আলাদা L1 iTLB আছে ঠিক এই কারণেই। বড়, বিক্ষিপ্ত কোডবেস (JIT-generated কোড, বহু shared library, C++ template-heavy বাইনারি যেখানে code size বিশাল) instruction fetch-এ iTLB miss ঘটাতে পারে ঠিক যেমন data access dTLB miss ঘটায়।

এইটা বিশেষভাবে গুরুত্বপূর্ণ JIT compiler-এর জন্য (JVM, V8, PyPy) — এগুলো চলার সময় নতুন executable code তৈরি করে, প্রায়ই memory-জুড়ে ছড়ানো ছোট ছোট টুকরোয়। এই কারণেই JIT-heavy runtime-এ code layout optimization (generated code-কে একসাথে, page-সারিবদ্ধভাবে রাখা) শুধু cache-এর জন্য না, iTLB-এর জন্যও গুরুত্বপূর্ণ। Level 5-এর compilers module কোড জেনারেশন আর layout-এর এই দিকটা বিস্তারিত দেখবে।

“PCID/ASID থাকলে context switch-এর TLB সমস্যা সম্পূর্ণ সমাধান — আর কোনো flush লাগে না।”

PCID tag space সীমিত — x86-এ ১২ বিট, অর্থাৎ সর্বোচ্চ ৪০৯৬টা ভিন্ন ID। একটা মেশিনে ৪০৯৬-এর বেশি সক্রিয় প্রসেস/থ্রেড থাকলে (আধুনিক সার্ভারে অস্বাভাবিক না), kernel-কে PCID পুনর্ব্যবহার করতে হয় — একটা পুরনো প্রসেসের PCID নতুন একটাকে দেওয়ার আগে, সেই ID-তে ট্যাগ করা সব পুরনো TLB entry invalid করে দিতে হয় (নাহলে নতুন প্রসেস ভুলবশত পুরনো mapping ব্যবহার করে ফেলতে পারত)। এটাকে বলে ASID rollover, আর এটা periodic পূর্ণ flush-এর প্রয়োজন তৈরি করে, শুধু কম ঘন ঘন।

বাস্তবে Linux আরও রক্ষণশীল — মাত্র হাতে গোনা কয়েকটা PCID ব্যবহার করে প্রতি-core ভিত্তিতে (৬টার কাছাকাছি), কারণ PCID ব্যবস্থাপনার নিজস্ব bookkeeping খরচ আছে। আর KPTI-পরবর্তী যুগে প্রতিটা প্রসেসের দুইটা PCID লাগে (user + kernel half), তাই কার্যকর ID space আরও কমে যায়। “PCID থাকলে flush লাগে না” — শুধু সাধারণ, প্রসেস-সংখ্যা-কম পরিস্থিতিতে প্রায়-সত্যি; বড় স্কেলে rollover-এর খরচ ফিরে আসে।

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

1

একটা প্রোগ্রাম randomly ১.৫ MB memory-জুড়ে (৪ KB stride-এ, অর্থাৎ ৩৮৪টা distinct page) বারবার access করে। Ice Lake-এর L1 dTLB (৬৪ entry) আর L2 STLB (২০৪৮ entry) ধরে — এই workload প্রধানত কোন স্তরে মিটবে, আর কেন?

প্রয়োগ

প্রথমে TLB reach হিসাব করি দুই স্তরে:

L1 dTLB reach=64×4 KB=256 KB\text{L1 dTLB reach} = 64 \times 4\,\text{KB} = 256\,\text{KB} L2 STLB reach=2048×4 KB=8 MB\text{L2 STLB reach} = 2048 \times 4\,\text{KB} = 8\,\text{MB}

Working set ৩৮৪টা page = ১.৫ MB। এটা L1 dTLB reach (২৫৬ KB)-এর চেয়ে বড় — তাই L1 dTLB প্রায় প্রতিটা access-এ miss করবে, কারণ মাত্র ৬৪টা entry দিয়ে ৩৮৪টা page ঢাকা যায় না, warm-up-এর পরও পুরনো entry বারবার evict হতে থাকবে।

কিন্তু ১.৫ MB, L2 STLB reach (৮ MB)-এর চেয়ে অনেক ছোট। তাই warm-up-এর পর প্রায় সব access L2 STLB-তেই মিটবে — L1 miss কিন্তু L2 hit, খরচ ~৭-১০ cycle প্রতি access, পূর্ণ page walk (~১৫০-৩০০ cycle) না।

L1 dTLB (৬৪ entry, ২৫৬ KB reach)L2 STLB (২০৪৮ entry, ৮ MB reach)
Working set (১.৫ MB) ঢাকে?নাহ্যাঁ
প্রধান ফলাফলmisshit

উপসংহার: এই workload “মাঝের অঞ্চলে” পড়ে — cache hierarchy-তে যেমন “L1 miss কিন্তু L2 hit” একটা সাধারণ, তুলনামূলক সস্তা অবস্থা, ঠিক তেমনি TLB hierarchy-তেও। শুধু “TLB miss হচ্ছে কি না” জিজ্ঞাসা করা যথেষ্ট না — কোন স্তরে মিটছে সেটাই আসল খরচ নির্ধারণ করে। এই আগের experiment-এর sweep টেবিলে ঠিক এই আচরণ (১২৮ থেকে ২০৪৮ slot পর্যন্ত ~৪ ns/access, স্থিতিশীল) দেখা গিয়েছিল।

2

x86-এ TLB miss হার্ডওয়্যারে (page walker state machine) মেটে, কিন্তু কিছু পুরনো architecture-এ (MIPS, পুরনো SPARC) এটা একটা software trap — OS নিজে হ্যান্ডলার চালিয়ে TLB entry বসায়। প্রতিটা পদ্ধতির সুবিধা-অসুবিধা কী?

যুক্তি

Hardware-walked (x86, ARM64):

সুবিধা — দ্রুত। কোনো exception, কোনো mode switch, কোনো instruction fetch লাগে না — একটা dedicated সার্কিট সরাসরি memory পড়ে entry বসায়। খরচ ~২০-৩০০ cycle (এই লেসনের অভিজ্ঞতা-ভিত্তিক পরিসীমা)।

অসুবিধা — page table format hardware-এ বেঁধে দেওয়া। OS একটা ভিন্ন, হয়তো বেশি স্মৃতি-সাশ্রয়ী কাঠামো (যেমন একটা hash-based page table, বা inverted page table) চাইলেও পারবে না — CPU শুধু x86-এর সংজ্ঞায়িত ৪/৫-স্তর tree-ই বোঝে।

Software-managed (MIPS, পুরনো SPARC):

সুবিধা — নমনীয়তা। OS নিজের page table গঠন বেছে নিতে পারে — inverted page table (physical frame-কে key ধরে, যা 64-বিট address space-এ multi-level tree-র চেয়ে কম memory খায়), বা hash-ভিত্তিক গঠন। MIPS-এ প্রতিটা OS নিজের মতো TLB miss handler লিখতে পারত।

অসুবিধা — প্রতিটা TLB miss একটা পূর্ণ exception — pipeline flush, mode switch (user→kernel), handler-এর নিজের instruction fetch (যেগুলো নিজেরাই TLB miss করতে পারে!), তারপর একটা special tlbwr-জাতীয় instruction দিয়ে entry বসানো। এই পুরো প্রক্রিয়া হাজার-খানেক cycle নিতে পারে — hardware walker-এর চেয়ে ১০-৫০ গুণ বেশি ধীর।

Hardware-walkedSoftware-managed
Miss খরচ~২০-৩০০ cycle~১০০০+ cycle
Page table formatCPU নির্ধারণ করেOS স্বাধীন
জটিলতা কোথায়silicon-এkernel কোডে

কেন x86/ARM64 hardware-walked বেছে নিল: আধুনিক workload-এ TLB miss rate যথেষ্ট বেশি (প্রতি হাজার instruction-এ কয়েকটা) যে miss-প্রতি খরচের পার্থক্যটাই (৫০ গুণ) নমনীয়তার সুবিধার চেয়ে বেশি গুরুত্বপূর্ণ হয়ে ওঠে। এটা একটা সাধারণ architecture-ডিজাইন প্যাটার্ন — যে পথ বেশি হাঁটা হয়, সেটাকে hardware-এ পাকা করে ফেলা, বিরল পথটাকে নমনীয় (software) রাখা। Level 12-এর cloud module একই যুক্তি নেটওয়ার্ক প্যাকেট প্রসেসিং-এ (DPDK, XDP) দেখাবে — hot path hardware/kernel-bypass-এ, cold path সাধারণ software stack-এ।

3

আপনি একটা নতুন CPU-র TLB ডিজাইন করছেন। বাজেট ফিক্সড: হয় ১২৮টা entry ৪-way associative আর ২ cycle latency-তে, অথবা ৩২টা entry fully-associative আর ১ cycle latency-তে। কোনটা বেছে নেবেন, আর কোন workload-এ কোনটা জেতে?

ডিজাইন

দুইটা ডিজাইনের trade-off ভিন্ন দুই দিকে ভারী:

১২৮-entry, ৪-way, ২ cycle:

TLB reach (4KB page) = ১২৮ × ৪ KB = ৫১২ KB। Associativity কম হওয়ায় conflict miss বেশি সম্ভব (একই set-এ map হওয়া চারটার বেশি page একসাথে থাকতে পারবে না), কিন্তু raw capacity বেশি।

৩২-entry, fully-associative, ১ cycle:

TLB reach = ৩২ × ৪ KB = ১২৮ KB। Fully-associative হওয়ায় conflict miss নেই (যেকোনো entry যেকোনো way-তে যেতে পারে, শুধু capacity miss), কিন্তু capacity ৪ গুণ কম।

১২৮-entry, ৪-way৩২-entry, fully-assoc
Reach৫১২ KB১২৮ KB
Hit latency২ cycle১ cycle
Conflict missসম্ভবনেই

কে জেতে, workload-ভেদে:

  • Tight loop, ছোট working set (উদাহরণ: একটা ম্যাট্রিক্স multiply-র inner loop যা ৬৪ KB-এর মধ্যে ঘোরে): দুইটাই hit দেবে (৬৪ KB < ১২৮ KB < ৫১২ KB), তাই latency-ই নির্ধারক — ৩২-entry, ১ cycle জেতে। প্রতিটা hit-এ ১ cycle বাঁচানো, বিলিয়ন-বার পুনরাবৃত্তি হলে, বড় সঞ্চয়।

  • বিক্ষিপ্ত access, মাঝারি working set (উদাহরণ: ৩০০ KB জুড়ে ছড়ানো একটা hash table): ৩২-entry ডিজাইনে ক্রমাগত miss (reach ছাড়িয়ে গেছে), প্রতিটা miss-এ পূর্ণ page walk (~১৫০+ cycle)। ১২৮-entry ডিজাইনে বেশিরভাগ hit (reach-এর মধ্যে), শুধু ২ cycle খরচে — ১২৮-entry জেতে, বিশাল ব্যবধানে, কারণ miss-এর খরচ hit-latency-র পার্থক্যের (মাত্র ১ cycle) তুলনায় বহুগুণ বেশি।

সাধারণ নীতি: যখনই miss rate নগণ্য না, miss-এর খরচ (দশ-শত cycle) hit-latency-র সামান্য পার্থক্য (১ cycle)-কে সম্পূর্ণ ছাপিয়ে যায় — তাই reach-কে প্রাধান্য দেওয়াই সাধারণত সঠিক সিদ্ধান্ত, যদি না workload নিশ্চিতভাবে ছোট আর tight-loop-প্রবণ (যেমন embedded/DSP কোড)। এই কারণেই বাস্তব CPU-গুলো একটাকে বেছে নেয় না — দুইটাই রাখে, স্তরে স্তরে (L1 ছোট-দ্রুত, L2 বড়-ধীর), ঠিক এই লেসনের concept সেকশনে দেখা গঠনের মতো। Level 6-এর algorithms module cache/TLB replacement আর associativity-র এই trade-off-টা আরও সাধারণ ভাষায় (competitive analysis) দেখাবে।

4

একটা ১২৮-core সার্ভারে একটা multi-threaded প্রসেস (সব core-এ থ্রেড ছড়ানো) mprotect() ডেকে একটা বড় region read-only করে দেয়। ধরুন প্রতিটা IPI round-trip গড়ে ২ μs লাগে, আর shootdown সিরিয়ালি (একটা একটা করে) পাঠানো হয়। মোট খরচ কত, আর Linux বাস্তবে এটা কীভাবে কমায়?

যুক্তি

নিষ্পাপ হিসাব — সিরিয়াল shootdown:

Initiator core বাদে বাকি ১২৭টা core-এ IPI পাঠাতে হবে, প্রতিটার response-এর জন্য অপেক্ষা:

127×2 μs=254 μs127 \times 2\,\mu s = 254\,\mu s

একটা সাধারণ syscall (~১ μs) এর তুলনায় এটা ২৫৪ গুণ বেশি — একটা একক mprotect() কল-এর জন্য অগ্রহণযোগ্য।

বাস্তবে Linux কীভাবে কমায়:

১. Broadcast, সিরিয়াল না। IPI একটার পর একটা পাঠানো হয় না — APIC-এর মাধ্যমে একসাথে (broadcast বা একগুচ্ছ target বিটমাস্ক দিয়ে) পাঠানো হয়, তারপর initiator সবগুলোর response-এর জন্য সমান্তরালে অপেক্ষা করে। খরচ তখন ~127 × 2 μs না, বরং সবচেয়ে ধীর core-এর response সময়ের কাছাকাছি — আনুমানিক ২-৫ μs, ২৫৪ μs না।

২. mm_cpumask দিয়ে টার্গেট কমানো। যে core-এ এই প্রসেসের কোনো থ্রেড কখনো চলেনি, সেখানে IPI পাঠানোরই দরকার নেই। বাস্তবে ১২৮-core সার্ভারে একটা প্রসেসের থ্রেড হয়তো ৮-১৬টা core-এ সীমাবদ্ধ (cgroup/taskset দিয়ে pin করা) — তাহলে বাস্তব target সংখ্যা ১২৭ না, ৭-১৫।

৩. Range-based invalidate, পূর্ণ flush না। পুরো TLB flush না করে শুধু বদলানো region-এর জন্য invlpg/invpcid (range) — বাকি valid entry অক্ষত থাকে, receiving core-এর নিজস্ব কাজে কম ব্যাঘাত।

৪. Batching — একাধিক PTE বদল, একটাই shootdown। যদি mprotect() একগুচ্ছ VMA-জুড়ে কাজ করে, প্রতিটা VMA-র জন্য আলাদা shootdown না পাঠিয়ে mmu_gather সব বদল জমিয়ে একবারে পাঠায়।

Level 9-এর সংযোগ: এই সমস্যাটার আকৃতি distributed system-এর cache invalidation সমস্যার সাথে হুবহু মেলে — একটা কেন্দ্রীয় write, বহু replica-কে invalidate করতে হয়, প্রতিটা replica-র response-এর জন্য অপেক্ষা করলে latency O(n)। Level 9-এর distributed-systems module ঠিক এই প্যাটার্নটা (broadcast invalidation, quorum-ভিত্তিক অপেক্ষা) larger scale-এ দেখাবে — TLB shootdown আসলে single-machine-এর মধ্যে একটা মিনি-ডিস্ট্রিবিউটেড-সিস্টেম সমস্যা। Level 11-এর performance module Amit-এর পেপারের বাকি সমাধানগুলো (per-page access tracking দিয়ে অপ্রয়োজনীয় shootdown এড়ানো) বিস্তারিত দেখাবে।

5

perf stat-এ একটা প্রোগ্রামে dTLB-loads = 50,000,000 আর dTLB-load-misses = 2,500,000 দেখাচ্ছে। প্রতিটা miss গড়ে ১৫০ cycle খরচ করে ধরে নিলে (আর hit ধরে নিন সম্পূর্ণ বিনামূল্যে, pipeline-ওভারল্যাপড), TLB miss একা এই প্রোগ্রামে গড়ে প্রতি memory access-এ কত cycle যোগ করছে? ৩ GHz CPU-তে এটা কত ns?

প্রয়োগ

Miss rate:

miss rate=2,500,00050,000,000=5%\text{miss rate} = \frac{2{,}500{,}000}{50{,}000{,}000} = 5\%

Weighted average extra cost:

cycle/access=(0.95×0)+(0.05×150)=7.5 cycle\text{cycle/access} = (0.95 \times 0) + (0.05 \times 150) = 7.5 \text{ cycle}

৩ GHz-এ (১ cycle ≈ ০.৩৩ ns):

7.5×0.33 ns≈2.5 ns প্রতি access7.5 \times 0.33\,\text{ns} \approx 2.5\,\text{ns প্রতি access}

প্রসঙ্গ দেওয়া যাক — একটা L1 cache hit-এর সময়ই সাধারণত ~১ ns-এর কাছাকাছি (৪ cycle @ ৩ GHz)। তার মানে শুধু TLB miss-ই এই প্রোগ্রামের গড় মেমরি-অ্যাক্সেস সময়ে আরও আড়াইগুণ যোগ করছে, ডেটা নিজে যে cache-এ আছে কিনা তার হিসাবের বাইরেই। ৫% miss rate শুনতে ছোট, কিন্তু miss-এর খরচ (১৫০ cycle) hit-এর খরচের (~০, ওভারল্যাপড) তুলনায় এত বেশি যে তার প্রভাব অসামঞ্জস্যপূর্ণভাবে বড়।

ব্যবহারিক পরবর্তী পদক্ষেপ:

১. AnonHugePages চেক করুন — যদি ০ হয়, huge page চালু করে আবার মাপুন। এই লেসনের experiment-এ ঠিক এই ধরনের workload-এ dTLB-miss অনুপাত ৯৬% থেকে ০.৪% নেমেছিল। ২. যদি huge page ইতিমধ্যে চালু, working set-এর আকার আর access pattern পরীক্ষা করুন — হয়তো data structure-টা এতই বড় (GB-স্কেল) যে এমনকি 2MB page-এও TLB reach যথেষ্ট না; সেক্ষেত্রে 1GB page বিবেচনা করুন। ৩. যদি কোনোটাই সম্ভব না হয় (portability-র কারণে), access pattern-কে আরও locality-friendly করা যায় কিনা দেখুন — একই page-এর মধ্যে বেশি কাজ গুচ্ছ করে করা (blocking/tiling)।

Level 11-এর সংযোগ: এই “miss rate × miss cost = weighted overhead” হিসাবটাই AMAT (Average Memory Access Time) সূত্রের একটা সংস্করণ, যা cache hierarchy, TLB hierarchy, এমনকি network round-trip বিশ্লেষণেও একই রকম প্রয়োগ হয়। Level 11-এর performance module এই একই কাঠামো disk I/O আর network latency বিশ্লেষণে পুনরায় ব্যবহার করবে — একটা ছোট miss rate কখনো নিরাপদ প্রমাণ না, miss-এর খরচ কত বড় সেটাই আসল প্রশ্ন।

এরপর কী

পরের লেসন — Page fault আর demand paging

এই লেসনে বারবার একটা লাইন এসেছে — “walk শেষে দেখা যায় mapping-টাই অবৈধ (P=0)”। TLB miss ধরনের সমস্যা হার্ডওয়্যারেই মেটে, কয়েক-দশ থেকে কয়েক-শ cycle-এ। কিন্তু P=0 হলে গল্পটা সম্পূর্ণ বদলে যায় — CPU একটা page fault ছোঁড়ে, নিয়ন্ত্রণ যায় OS-এর কাছে, আর সেখান থেকে যা ঘটে সেটাই আধুনিক OS-এর সবচেয়ে গুরুত্বপূর্ণ hook।

পরের লেসনে দেখব fault handler-এর সিদ্ধান্ত-বৃক্ষ (VMA বৈধ? অনুমতি আছে? copy-on-write? stack বাড়ছে? swap থেকে আনতে হবে? নাকি সত্যিই SIGSEGV?), demand paging কীভাবে একটা ১০০ MB বাইনারিকে সাথে সাথে চালু করে দেয় (গত লেসনের সেই “mmap মানেই মেমরি বরাদ্দ না” পর্যবেক্ষণের পূর্ণ ব্যাখ্যা), copy-on-write PTE স্তরে ঠিক কীভাবে কাজ করে, আর page replacement-এর বাস্তব Linux বাস্তবায়ন — active/inactive LRU list, second chance, thrashing। আর একটা প্রায়-৬০-লাইনের C প্রোগ্রাম লিখব যেটা নিজেই একটা userspace demand-paging সিস্টেম — SIGSEGV ধরে, page-টা লিখনযোগ্য করে, আবার চালিয়ে যায়।

আরও পড়ুন