Hardware Virtualization — VT-x, EPT আর CPU নিজেই কীভাবে Popek-Goldberg সমস্যা সমাধান করল

এই স্ক্রিপ্টটা হাত-দিয়ে-verify করা না, সত্যিই চালিয়ে যাচাই করা — নিচের কোড ব্লকের ঠিক পরের আউটপুট ব্লকটা এই স্ক্রিপ্ট চালিয়ে সরাসরি পাওয়া, কোনো সংখ্যা অনুমান করা না।

#!/usr/bin/env python3
"""
EPT (2D page walk) vs Shadow Paging (1D page walk) worst-case cost model.

Part 1: worst-case memory-access count for a full page-table walk.
Part 2: toy crossover point -- when does EPT's cheaper page-table-WRITE
        path start winning over its more expensive TLB-MISS path,
        compared against shadow paging's cheaper walk / expensive trap?
"""

def walk_accesses_native_or_shadow(levels):
    """
    Native page walk (or shadow-paging walk, which is structurally
    identical from the CPU's point of view -- the shadow table already
    stores host-physical addresses at every level).
    """
    return levels  # one memory access per level to fetch that level's PTE

def walk_accesses_nested(guest_levels, nested_levels):
    """
    Full 2D (nested/EPT) page walk.
    To fetch EACH of the guest's page-table entries, the CPU must first
    translate that entry's guest-physical address into a host-physical
    address -- a FULL nested_levels-deep EPT walk -- and then do the
    access itself (+1). It does this for every guest level, and then
    does one more full EPT walk to translate the final data page's GPA.
    """
    per_guest_level = nested_levels + 1   # EPT walk for this level's GPA, then read it
    return guest_levels * per_guest_level + nested_levels  # + final data-page EPT walk


shadow_walk = walk_accesses_native_or_shadow(4)
ept_walk = walk_accesses_nested(guest_levels=4, nested_levels=4)

print("=== Part 1: worst-case memory accesses per TLB-miss page walk ===")
print(f"Native / shadow-paging walk (4-level, single dimension): {shadow_walk} accesses")
print(f"EPT/NPT nested walk (4-level guest x 4-level EPT):       {ept_walk} accesses")
print(f"  breakdown: 4 guest levels x (4 EPT + 1 read) + 4 final EPT = "
      f"{4*(4+1)} + 4 = {4*(4+1)+4}")
print()

# ---------------------------------------------------------------------------
# Part 2: toy crossover model
# ---------------------------------------------------------------------------
# Per-instruction expected extra cost, relative to a hypothetical "free" MMU:
#
#   shadow_cost(instr) = write_freq    * COST_VMEXIT                (trap+fixup on guest PTE writes)
#                       + tlbmiss_freq * shadow_walk * COST_ACCESS  (cheap walk on a miss)
#
#   ept_cost(instr)    = tlbmiss_freq * ept_walk    * COST_ACCESS   (no write-trap at all,
#                                                                     but a much pricier walk)
#
# EPT wins (ept_cost < shadow_cost) exactly when:
#
#   tlbmiss_freq * (ept_walk - shadow_walk) * COST_ACCESS < write_freq * COST_VMEXIT
#
#   =>  write_freq / tlbmiss_freq  >  (ept_walk - shadow_walk) * COST_ACCESS / COST_VMEXIT
#
# i.e. there's a critical RATIO of (guest page-table writes) to (TLB misses)
# above which EPT is the better deal, and below which shadow paging wins.

COST_VMEXIT = 1500   # cycles for a VM-exit + emulate-the-write + VM-entry round trip
                      # (order-of-magnitude figure widely cited for VT-x/AMD-V; real
                      # hardware ranges roughly 1,000-3,000+ cycles depending on the
                      # exit reason and microarchitecture)
COST_ACCESS = 100    # cycles per page-walk memory access that misses the page-walk
                      # caches and must go to L2/L3 (an honest middle estimate --
                      # NOT a full DRAM miss, since page-walker caches usually catch
                      # the upper levels; treat this as illustrative, not measured)

delta_accesses = ept_walk - shadow_walk
critical_ratio = delta_accesses * COST_ACCESS / COST_VMEXIT

print("=== Part 2: toy crossover point ===")
print(f"COST_VMEXIT (assumed)          = {COST_VMEXIT} cycles")
print(f"COST_ACCESS (assumed)          = {COST_ACCESS} cycles")
print(f"extra walk accesses EPT adds   = {ept_walk} - {shadow_walk} = {delta_accesses}")
print(f"critical write_freq/tlbmiss_freq ratio = "
      f"{delta_accesses} * {COST_ACCESS} / {COST_VMEXIT} = {critical_ratio:.4f}")
print()
print("Reading: if a workload causes MORE than "
      f"{critical_ratio:.3f} guest page-table writes per TLB miss, "
      "EPT is cheaper.")
print("If it causes FEWER, shadow paging's cheaper walk wins out.\n")

print(f"{'write/tlbmiss ratio':>22} | {'shadow cost/instr':>18} | {'EPT cost/instr':>15} | winner")
print("-" * 78)

# fix tlbmiss_freq, vary write_freq to vary the ratio
tlbmiss_freq = 0.01  # 1 TLB miss per 100 instructions (toy, illustrative)
for ratio in [0.0, 0.5, 1.0, critical_ratio, 2.0, 5.0, 10.0]:
    write_freq = ratio * tlbmiss_freq
    shadow_cost = write_freq * COST_VMEXIT + tlbmiss_freq * shadow_walk * COST_ACCESS
    ept_cost = tlbmiss_freq * ept_walk * COST_ACCESS
    winner = "EPT" if ept_cost < shadow_cost else ("tie" if abs(ept_cost-shadow_cost) < 1e-9 else "shadow")
    print(f"{ratio:>22.4f} | {shadow_cost:>18.2f} | {ept_cost:>15.2f} | {winner}")

স্ক্রিপ্টটা সরাসরি চালানোর প্রকৃত (hand-verified, কোনো অংশ অনুমান করা না) আউটপুট:

=== Part 1: worst-case memory accesses per TLB-miss page walk ===
Native / shadow-paging walk (4-level, single dimension): 4 accesses
EPT/NPT nested walk (4-level guest x 4-level EPT):       24 accesses
  breakdown: 4 guest levels x (4 EPT + 1 read) + 4 final EPT = 20 + 4 = 24

=== Part 2: toy crossover point ===
COST_VMEXIT (assumed)          = 1500 cycles
COST_ACCESS (assumed)          = 100 cycles
extra walk accesses EPT adds   = 24 - 4 = 20
critical write_freq/tlbmiss_freq ratio = 20 * 100 / 1500 = 1.3333

Reading: if a workload causes MORE than 1.333 guest page-table writes per TLB miss, EPT is cheaper.
If it causes FEWER, shadow paging's cheaper walk wins out.

   write/tlbmiss ratio |  shadow cost/instr |  EPT cost/instr | winner
------------------------------------------------------------------------------
                0.0000 |               4.00 |           24.00 | shadow
                0.5000 |              11.50 |           24.00 | shadow
                1.0000 |              19.00 |           24.00 | shadow
                1.3333 |              24.00 |           24.00 | tie
                2.0000 |              34.00 |           24.00 | EPT
                5.0000 |              79.00 |           24.00 | EPT
               10.0000 |             154.00 |           24.00 | EPT

পড়ুয়া দৃষ্টিতে: যদি একটা workload প্রতি TLB miss-এ গড়ে ১.৩৩-টার বেশি guest page-table write ঘটায় (মানে page table সংশোধন খুবই ঘন ঘন — নতুন process তৈরি, ঘন ঘন mmap/munmap), EPT স্পষ্টভাবে জেতে। কিন্তু একটা workload যেখানে page table প্রায় স্থির (কম fork/mmap, বেশিরভাগ সময় শুধু data access) অথচ TLB miss অনেক বেশি (বড়, র‍্যান্ডম-অ্যাক্সেস ডেটাসেট, huge page ছাড়া) — সেখানে তাত্ত্বিকভাবে shadow paging-এর সরল ৪-স্তরের walk জিততে পারত। বাস্তবে অবশ্য আধুনিক CPU-র page-walk cache (উচ্চ-স্তরের EPT/guest entry ক্যাশ করে রাখে) এই ২৪-হপ worst case-কে অনেক কমিয়ে আনে গড়পড়তা ক্ষেত্রে — এই সিমুলেশনটা ইচ্ছাকৃতভাবে সরলীকৃত (walk cache নেই ধরে), একটা উপরের সীমা (upper bound) দেখানোর জন্য, বাস্তব গড় latency-র সঠিক পরিমাপ না। তা সত্ত্বেও, বাস্তব ইঞ্জিনিয়ারিং সিদ্ধান্ত (EPT সবসময় জেতে, একটা বিরল edge-case ছাড়া) এই toy মডেলের সাথেই সামঞ্জস্যপূর্ণ — কারণ বাস্তব workload-এ page-table write-এর ফ্রিকোয়েন্সি প্রায় সবসময় critical ratio-র চেয়ে বেশি থাকে।