Stackmaxxing for a recursion world record

Objective

• Push a real (non–tail-call-optimized) call-stack depth as far as possible.
• The creator reached ~17.6 trillion nested invocations by maximizing per-frame density and relying on true return addresses visible to debuggers (no TCO).

High-level approach

• Present the process with an enormous virtual stack by mapping a huge file as the process stack (using mmap with MAP_FIXED). The file is implemented by a custom FUSE filesystem that exposes a very large (128 TB) file without storing it all on disk.
• Minimize each stack frame (hand-written assembly, careful ABI/register use, remove locals, avoid compiler alignment overhead).
• Reduce kernel bookkeeping (page-table) overhead by using madvise behavior and a kernel tweak to free page-table memory that isn’t needed.
• Switch CPU mode from 64-bit to 32-bit so return addresses shrink from 8 bytes to 4 bytes for additional density.

Key technical concepts and tools covered

• Stack frame basics: return address + locals/stack spills; typical ABI/compiler behavior (e.g., AMD64 uses registers when possible; compilers may insert 16-byte stack alignment).
• Tail-call optimization (TCO): compilers can eliminate calls; requirement here is real return addresses visible to a debugger.
• Virtual memory layout and limits:
  • 4-level page tables provide ≈128 TB user address space.
  • 5-level paging (on newer CPUs) allows ≈64 PB.
• Page-table overhead: mapping a huge virtual stack creates many page-table structures that can dominate memory usage (hundreds of GB).
• mmap (MAP_FIXED), /proc/maps, ulimit (stack size), madvise (freeing pages/page tables), and interactions with the kernel page cache and memory-mapped files.
• FUSE: used to present a gigantic file without storing all pages; the implementation mirrors a few pages and returns zeros elsewhere.
• Assembly and linker scripts: bootstrap/recursive code placed at low addresses (including near 0), made tiny and writable to reduce per-frame cost.
• 32-bit/64-bit mode switching: far-call into a 32-bit code segment to make return addresses 4 bytes long; far return to resume 64-bit.
• GDB pitfalls: inserting breakpoints (writing int3) can corrupt bootstrap code and crash long runs.

Implementation highlights / step-by-step techniques

1. Start small and measure:
   • Begin with a simple C recursion (e.g., triangular numbers) to observe per-frame stack usage.
   • Measure frame size via disassembly and memory dumps in a debugger.
2. Reduce frame size:
   • Pass accumulators in registers instead of locals.
   • Avoid constructs that force stack spills; use compiler flags to suppress tail-call elimination where necessary.
   • Move critical recursion into hand-written assembly and control layout with a linker script.
3. Provide a huge stack via mmap of a file:
   • Implement a minimal FUSE filesystem exporting the large “stack” file.
   • FUSE read callback: return mirror copies of the last page’s return-address pattern; return zeros for offsets before the current written region.
   • FUSE write callback: accept writes only at the last page (ignore others).
4. Reserve the user address space for the stack:
   • Use mmap with MAP_FIXED to place the stack across the desired virtual range. Note small caveats: some low addresses/pages are normally protected.
5. Free page-table overhead on the fly:
   • Use madvise (and, in the author’s case, a kernel commit/patch) to free page tables for virtual ranges no longer needed.
6. Increase frame density via 32-bit mode:
   • When the 64-bit stack reaches around 4 GB of depth, perform a far call into a 32-bit code segment so subsequent returns push 4-byte return addresses.
   • Map a normal 4 GB region for the 32-bit portion of the stack.
7. Bootstrap and exit:
   • Place bootstrap code at very low addresses (even at 0) via a linker script so frames grow into the FUSE-mapped region.
   • Exit through an outer wrapper that returns a sanity-checked small result.

Practical problems encountered and fixes

• Tail-call optimization turned recursion into a loop: fix by enforcing real calls (inspect disassembly and adjust compiler flags or use assembly).
• ABI alignment (16-byte) wasted per-frame bytes: avoid by using assembly and not invoking vector-aligned library calls.
• Page-table memory explosion when mapping 128 TB: addressed by using madvise and relying on/patching kernel behavior to free page-table structures.
• GDB breakpoints: writing int3 into bootstrap locations corrupts code and can crash very long runs — avoid modifying code pages in use or use breakpoints injected differently.
• Performance: FUSE is slow for record-breaking runs; a kernel-level backing would be far faster.

Quantitative results & platform notes

• Test machine: Intel system with 16 GB RAM and 500 GB disk. A simple unlimited-stack C test reached ~940 million recursions before applying the advanced techniques.
• Typical recursion limits:
  • Python default recursion limit ≈ 1,000 (can be raised, but interpreter crashes eventually).
  • JavaScript ≈ 50,000.
  • C ≈ 260,000 in ordinary builds.
• Page-table overhead: mapping a 128 TB user-space stack can consume on the order of hundreds of GB of page-table memory (author observed ~256 GB).
• Final achieved depth: ~17.592 trillion recursive invocations (transcript: 17,592,722,915,310) — the run completed and returned successfully in a later attempt.
• Future scaling: CPUs with 5-level paging (≈64 PB user space) could enable far larger depths (quadrillions of frames) if other limits are addressed.

Advice for breaking the record

• Shrink critical assembly code further (code-golf key sections) — each byte saved yields more recursion.
• Avoid FUSE for performance-critical record attempts; prefer a kernel-level filesystem or kernel support to back the huge stack.
• Use hardware supporting 5-level paging to increase the address space (64 PB).
• Consider OS-level changes: different user/kernel address-space splits or kernel support for huge user stacks would enable much larger results.
• Implement madvise-like page-table freeing cleanly in-kernel to avoid warnings and cross-process restrictions.

Caveats, safety and correctness notes

• This is an experimental proof-of-concept, not production-quality code. The FUSE filesystem mirrors pages and ignores most writes; it only supports the regular access pattern of the recursing program.
• The author modified kernel behavior (or applied patches) and used aggressive MAP_FIXED mapping; these operations are risky and can destabilize systems if misused.
• Debugging very long runs is tricky: breakpoints can corrupt bootstrap code and there are large, slow outputs to handle.

Main speakers / sources referenced

• The project creator / narrator (engineer who designed, implemented, and ran the experiment).
• Linux kernel internals (mmap, madvise, and page-table behavior); a specific recent commit from a ByteDance/TikTok developer was mentioned as enabling major progress.
• FUSE (user-space filesystem) used to expose the gigantic pseudo-file.
• Tools and languages referenced: gcc/assembler/linker, GDB, Python/JavaScript/C examples, procfs (/proc/*), mmap/munmap, MAP_FIXED.