boot2

18-gc-deep-list.scm (2367B)

---

 ;; Mark-stack overflow stress: force the
 ;; `mark_push → mark_push_recurse → mark_value` tail-branch fallback.
 ;;
 ;; `mark_stack` holds 512 entries (see `:mark_stack` in lisp.M1).
 ;; Overflow requires a DFS frontier wider than 512 at some point during
 ;; the mark phase. The cleanest trigger is a single live vector with
 ;; >512 element slots: `mark_value_vector` pushes each slot in one burst,
 ;; so the stack fills in-place and every further push routes through
 ;; `mark_push_recurse`.
 ;;
 ;; (LISP-GC.md originally conjectured that a deep *list* would overflow;
 ;; inspection of the mark order shows it won't — `mark_value_pair`
 ;; pushes cdr first and car second, so the DFS immediately consumes
 ;; the car side and leaves at most one leftover cdr per level. A flat
 ;; list never exceeds stack depth ~2. A large vector does. Keep the
 ;; filename for continuity with the step-5 plan in LISP-GC.md.)
 ;;
 ;; Bug this test pinned down: on aarch64/riscv64, `mark_push_recurse`
 ;; originally did `CALL mark_value ; RET`. Those arches' native CALL
 ;; writes the return address to a link register rather than pushing it,
 ;; so the inner CALL clobbered the incoming LR and the outer RET
 ;; branched to itself. The routine now tail-branches via
 ;; `li_br &mark_value ; b`, which lets mark_value return directly to
 ;; mark_push's caller. This test exercises that path across all three
 ;; arches.
 ;;
 ;; Plan:
 ;; 1. Allocate a 490-slot global vector. The mark stack is 512 entries
 ;;    and root-walking has contributed a handful of pending pair
 ;;    children before the vector is popped, so pushing 490 more
 ;;    elements crosses the threshold mid-vector.
 ;; 2. Fill with distinct fixnums so a mis-swept vector corrupts the
 ;;    checksum.
 ;; 3. Churn the pair arena to force repeated GCs while the vector
 ;;    stays globally reachable — each GC re-marks the vector and
 ;;    re-hits the overflow path.
 ;; 4. Sum the vector. Expected: 0 + 1 + … + 489 = 490 * 489 / 2 = 119805.
 
 (define v (make-vector 490 0))
 
 (define fill
   (lambda (i)
     (if (= i 490)
         0
         (begin (vector-set! v i i) (fill (+ i 1))))))
 (fill 0)
 
 (define churn
   (lambda (n)
     (if (= n 0)
         0
         (begin (cons n n) (churn (- n 1))))))
 (churn 2000)
 
 (define sum
   (lambda (i acc)
     (if (= i 490)
         acc
         (sum (+ i 1) (+ acc (vector-ref v i))))))
 
 (sum 0 0)