Unhandled error in test dynamic-extent.impure.lisp/CONSERVATIVE-NESTED-DX

[Lutz Euler]

After adding a presumably unrelated patch to sbcl-1.1.8-23, on an x86 build under Linux/x86_64 the test mentioned in the summary fails as follows:

::: Running :CONSERVATIVE-NESTED-DX
::: UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX
    due to #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>"
             {B14A091}>:
        "The assertion (EQUALP (NESTED-BAD 42) (MAKE-NESTED-GOOD :BAR *BAR*))
Unhandled TYPE-ERROR: The value NIL is not of type SB-KERNEL:LAYOUT.
Backtrace for: #<SB-THREAD:THREAD "main thread" RUNNING {AC3EE41}>
0: (SB-PCL::CACHE-MISS-VALUES #<error printing object>)
1: (SB-PCL::CACHING-MISS #<error printing object>)
2: ((LABELS SB-IMPL::HANDLE-IT :IN SB-KERNEL:OUTPUT-OBJECT) #<SB-PRETTY:PRETTY-STREAM {B14AA99}>)
3: (PRIN1 #<error printing object>)
4: (SB-FORMAT::S-FORMAT-DIRECTIVE-INTERPRETER #<SB-PRETTY:PRETTY-STREAM {B14AA99}> #<~S> NIL #<unavailable argument> #<unavailable argument>)
5: (SB-FORMAT::INTERPRET-DIRECTIVE-LIST #<error printing object>)
6: ((LABELS SB-FORMAT::DO-LOOP :IN SB-FORMAT::{-FORMAT-DIRECTIVE-INTERPRETER) #<error printing object>)
7: (SB-FORMAT::{-FORMAT-DIRECTIVE-INTERPRETER #<error printing object>)
8: (SB-FORMAT::INTERPRET-DIRECTIVE-LIST #<error printing object>)
9: ((LABELS SB-FORMAT::DO-LOOP :IN SB-FORMAT::{-FORMAT-DIRECTIVE-INTERPRETER) #<error printing object>)
10: (SB-FORMAT::{-FORMAT-DIRECTIVE-INTERPRETER #<error printing object>)
11: (SB-FORMAT::INTERPRET-DIRECTIVE-LIST #<error printing object>)
12: (SB-FORMAT::[-FORMAT-DIRECTIVE-INTERPRETER #<error printing object>)
13: (SB-FORMAT::INTERPRET-DIRECTIVE-LIST #<error printing object>)
14: ((LABELS #:BODY-NAME-1217 :IN SB-FORMAT::INTERPRET-FORMAT-LOGICAL-BLOCK))
15: (SB-FORMAT::INTERPRET-FORMAT-LOGICAL-BLOCK #<error printing object>)
16: (SB-FORMAT::<-FORMAT-DIRECTIVE-INTERPRETER #<error printing object>)
17: (SB-FORMAT::INTERPRET-DIRECTIVE-LIST #<error printing object>)
18: (SB-FORMAT::%FORMAT #<error printing object>)
19: (FORMAT #<error printing object>)
20: ((LABELS SB-IMPL::HANDLE-IT :IN SB-KERNEL:OUTPUT-OBJECT) #<SB-PRETTY:PRETTY-STREAM {B14AA99}>)
21: (PRINC #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #<SB-PRETTY:PRETTY-STREAM {B14AA99}>)
22: (SB-FORMAT::A-FORMAT-DIRECTIVE-INTERPRETER #<SB-PRETTY:PRETTY-STREAM {B14AA99}> #<~A> ("\"") #<unavailable argument> #<unavailable argument>)
23: (SB-FORMAT::INTERPRET-DIRECTIVE-LIST #<SB-PRETTY:PRETTY-STREAM {B14AA99}> (#<~A> "\"") (:UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #1=#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #1#) (#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}>))
24: ((LABELS #:BODY-NAME-1217 :IN SB-FORMAT::INTERPRET-FORMAT-LOGICAL-BLOCK))
25: (SB-FORMAT::INTERPRET-FORMAT-LOGICAL-BLOCK #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {9118D51}> (:UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #1=#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #1#) (:UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #1=#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #1#) "" NIL (#<~A> " " #<~S> " " #<~:_> "due to " #<~S> ": " #<~4I> #<~:_> "\"" #<~A> "\"") "" T)
26: (SB-FORMAT::<-FORMAT-DIRECTIVE-INTERPRETER #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {9118D51}> #<~@<> (#<~A> " " #<~S> " " #<~:_> "due to " #<~S> ": " #<~4I> #<~:_> "\"" #<~A> "\"" #<~:>>) (:UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #1=#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #1#) #<unavailable argument>)
27: (SB-FORMAT::INTERPRET-DIRECTIVE-LIST #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {9118D51}> (#<~@<> #<~A> " " #<~S> " " #<~:_> "due to " #<~S> ": " #<~4I> #<~:_> "\"" #<~A> "\"" #<~:>>) (:UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #1=#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #1#) (:UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #1=#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #1#))
28: (SB-FORMAT::%FORMAT #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {9118D51}> "~@<~A ~S ~:_due to ~S: ~4I~:_\"~A\"~:>" (:UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #1=#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #1#) (:UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #1=#<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #1#))
29: (FORMAT #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {9118D51}> "~@<~A ~S ~:_due to ~S: ~4I~:_\"~A\"~:>" :UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}>)
30: (TEST-UTIL::LOG-MSG "~@<~A ~S ~:_due to ~S: ~4I~:_\"~A\"~:>" :UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}> #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}>)
31: (TEST-UTIL::FAIL-TEST :UNEXPECTED-FAILURE :CONSERVATIVE-NESTED-DX #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}>)
32: ((FLET #:LAMBDA0 :IN #:G759) #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}>)
33: (SIGNAL #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}>)
34: (ERROR #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~
                                    with ~:*~{~{~S = ~S~}~^, ~}.~]~:@>" {B14A091}>)
35: (SB-KERNEL:ASSERT-ERROR #<error printing object>)
36: ((LAMBDA NIL :IN "/home/lutz/lisp/sbcl/sbcl-x86/tests/dynamic-extent.impure.lisp"))
37: (SB-INT:SIMPLE-EVAL-IN-LEXENV (COND (T (LET ((#1=#:THREADS760 (SB-THREAD:LIST-ALL-THREADS)) (TEST-UTIL::*THREADS-TO-JOIN* NIL) (TEST-UTIL::*THREADS-TO-KILL* NIL)) (BLOCK #2=#:G759 (HANDLER-BIND ((ERROR (LAMBDA (ERROR) (IF (TEST-UTIL::EXPECTED-FAILURE-P NIL) (TEST-UTIL::FAIL-TEST :EXPECTED-FAILURE (QUOTE :CONSERVATIVE-NESTED-DX) ERROR) (TEST-UTIL::FAIL-TEST :UNEXPECTED-FAILURE (QUOTE :CONSERVATIVE-NESTED-DX) ERROR)) (RETURN-FROM #2#)))) (PROGN (TEST-UTIL::LOG-MSG "Running ~S" (QUOTE :CONSERVATIVE-NESTED-DX)) (ASSERT (EQUALP (NESTED-BAD 42) (MAKE-NESTED-GOOD :BAR *BAR*))) (ASSERT (EQUALP *BAR* (LIST (LIST (MAKE-NESTED-BAD :BAR (LIST 42)))))) (LET ((TEST-UTIL::ANY-LEFTOVER NIL)) (DOLIST (TEST-UTIL::THREAD TEST-UTIL::*THREADS-TO-JOIN*) (IGNORE-ERRORS (SB-THREAD:JOIN-THREAD TEST-UTIL::THREAD))) (DOLIST (TEST-UTIL::THREAD TEST-UTIL::*THREADS-TO-KILL*) (IGNORE-ERRORS (SB-THREAD:TERMINATE-THREAD TEST-UTIL::THREAD))) (SETF #1# (UNION (UNION TEST-UTIL::*THREADS-TO-KILL* TEST-UTIL::*THREADS-TO-JOIN*) #1#)) (DOLIST (TEST-UTIL::THREAD (SB-THREAD:LIST-ALL-THREADS)) (UNLESS (OR (NOT (SB-THREAD:THREAD-ALIVE-P TEST-UTIL::THREAD)) (EQL TEST-UTIL::THREAD SB-THREAD:*CURRENT-THREAD*) (MEMBER TEST-UTIL::THREAD #1#) (SB-THREAD:THREAD-EMPHEMERAL-P TEST-UTIL::THREAD)) (SETF TEST-UTIL::ANY-LEFTOVER TEST-UTIL::THREAD) (IGNORE-ERRORS (SB-THREAD:TERMINATE-THREAD TEST-UTIL::THREAD)))) (WHEN TEST-UTIL::ANY-LEFTOVER (TEST-UTIL::FAIL-TEST :LEFTOVER-THREAD (QUOTE :CONSERVATIVE-NESTED-DX) TEST-UTIL::ANY-LEFTOVER) (RETURN-FROM #2#))) (IF (TEST-UTIL::EXPECTED-FAILURE-P NIL) (TEST-UTIL::FAIL-TEST :UNEXPECTED-SUCCESS (QUOTE :CONSERVATIVE-NESTED-DX) NIL) (TEST-UTIL::LOG-MSG "Success ~S" (QUOTE :CONSERVATIVE-NESTED-DX))))))))) #<NULL-LEXENV>)
[I did not paste the rest of the backtrace]

[Lutz Euler (lutz-euler)]

Trying to debug this, I found a way to reliably reproduce the test failure with plain 1.1.8-23:
Build SBCL 1.1.8-23 under x86_64/Linux with "sh make.sh", start it, then paste the following parts of tests/dynamic-extent.impure.lisp into the REPL:

(setq sb-c::*check-consistency* t
      sb-ext:*stack-allocate-dynamic-extent* t)

(defmacro defun-with-dx (name arglist &body body)
  (let ((debug-name (sb-int:symbolicate name "-HIGH-DEBUG"))
        (default-name (sb-int:symbolicate name "-DEFAULT")))
    `(progn
       (defun ,debug-name ,arglist
         (declare (optimize debug))
         ,@body)
       (defun ,default-name ,arglist
        ,@body)
       (defun ,name (&rest args)
         (apply #',debug-name args)
         (apply #',default-name args)))))

(declaim (notinline opaque-identity))
(defun opaque-identity (x)
  x)

(defparameter *bar* nil)
(declaim (inline make-nested-bad make-nested-good))
(defstruct (nested (:constructor make-nested-bad (&key bar &aux (bar (setf *bar* bar))))
                   (:constructor make-nested-good (&key bar)))
  bar)

(defun-with-dx nested-good (y)
  (let ((x (list (list (make-nested-good :bar (list (list (make-nested-good :bar (list y)))))))))
    (declare (dynamic-extent x))
    (true x)))

(defun-with-dx nested-bad (y)
  (let ((x (list (list (make-nested-bad :bar (list (list (make-nested-bad :bar (list y)))))))))
    (declare (dynamic-extent x))
    (unless (equalp (caar x) (make-nested-good :bar *bar*))
      (error "got ~S, wanted ~S" (caar x) (make-nested-good :bar *bar*)))
    (caar x)))

(declaim (notinline true))
(defun true (x)
  (declare (ignore x))
  t)

Then evaluating

(values (nested-bad 42) (make-nested-good :bar *bar*))

gives here:

debugger invoked on a TYPE-ERROR in thread
#<THREAD "main thread" RUNNING {1002B138B3}>:
  The value MAKE-NESTED-GOOD is not of type SB-KERNEL:LAYOUT.

Type HELP for debugger help, or (SB-EXT:EXIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
  0: [ABORT] Exit debugger, returning to top level.

CORRUPTION WARNING in SBCL pid 5513(tid 140737353926432):
Memory fault at d (pc=0x1000e9dd7c, sp=0x7ffff6d46140)
The integrity of this image is possibly compromised.
Continuing with fingers crossed.
(SB-PCL::CACHE-MISS-VALUES #<error printing object>)
0]

[Lutz Euler (lutz-euler)]

We discussed this shortly in #sbcl on 2013-06-04, but came to no final conclusion yet.
It would be good if some dynamic-extent guru could look into this. Is the test simply broken?

[Nikodemus Siivola (nikodemus)]

First off: These days I think many of stack allocation tests should be written using SB-INTROSPECT:ALLOCATION-INFORMATION to check if objects of interest are actually on stack or not.

Anyways, it looks to me like a regression -- unless it was always broken and just worked accidentally before...

(I would like to take a moment to apologise for the horrible names and lacking comments there.)

As far as I remember, the MAKE-NESTED-GOOD is supposed to be OK for stack allocation, whereas the SETF in MAKE-NESTED-BAD should prevent stack allocation. (Or at least stack allocation of the part that escapes via the SETF.)

I'm betting that the incredibly bogus error is the result MAKE-NESTED-BAD stack-allocating when it should not.

Just to clarify the point a bit further: when DX is requested we try to stack allocate as much as the nested structure as we can. Prior to the change that introduced this test nested structure constructors didn't stack allocate anything except the innermost structure.

This is the commit in question:

Author: Nikodemus Siivola <email address hidden>
Date: Fri Dec 12 13:05:23 2008 +0000

    1.0.23.38: fix bug 430 (stack alloc by nested defstruct constructors)

     * Mark lambdas introduced by the compiler as such, so that
       LAMBDA-SYSTEM-LAMBDA-P returns true for them.

     * Allow USE-GOOD-FOR-DX-P to inspect COMBINATIONs with CLAMBDA
       functionals: if the return value of the function always originates
       from a known DX-capable combination, and the arguments of the
       original combination are used only by the DX-capable combination,
       consider the original combination good for DX.

     * Allow USE-GOOD-FOR-DX-P to inspect REFs to LAMBDA-VARs: if the var
       is bound by a system lambda, has no other refs, is never set, gets
       its value from a single-value combination, and the LVAR it gets its
       value from is good for DX ... then the REF is good for DX as well.

     * HANDLE-NESTED-DYNAMIC-EXTENT-LVARS handles REFs as well by
       recursing on the lvar the REF gets its value from.

The important bits, IIRC, in the commit are DX-COMBINATION-P, and COMBINATION-ARGS-FLOW-CLEANLY-P. The SETF should cause the latter to say "no, they don't flow cleanly, so not OK to extend DX to arguments".

I'd start by winding history back to 6fd5fc37c44cc49ff0cb587022df4c881683a111 (first appearance of ALLOCATION-INFORMATION) and write a test that checks if things are allocated on stack when supposed to, and on heap when supposed to.

If nested structure DX does the right thing at that point in history, then bisect using the new test between that point and today.

If it doesn't do the right thing even then, write/backport a similar test for 1.0.23.38 and see if it ever worked right.

If it didn't, trace those functions mentioned above and compile small functions and stare at IR1 until you go blind or achieve illumination.

[Nikodemus Siivola (nikodemus)]

I tell a lie. TRIVIAL-LAMBDA-VAR-REF-P is quite important as well.

               ;; the LAMBDA this var is bound by has only a single REF, going
               ;; to a combination

This is the bit that the SETF should catch. IIRC.

[Paul Khuong (pvk)]

Nikodemus Siivola wrote:
> Anyways, it looks to me like a regression -- unless it was always broken
> and just worked accidentally before...
>
> (I would like to take a moment to apologise for the horrible names and
> lacking comments there.)
>
> As far as I remember, the MAKE-NESTED-GOOD is supposed to be OK for
> stack allocation, whereas the SETF in MAKE-NESTED-BAD should prevent
> stack allocation. (Or at least stack allocation of the part that escapes
> via the SETF.)
>
> I'm betting that the incredibly bogus error is the result MAKE-NESTED-
> BAD stack-allocating when it should not.

I don't see how why the SETF should stop stack allocation of the NESTED
struct itself. In the test case

(defun-with-dx nested-bad (y)
   (let ((x (list (list (make-nested-bad :bar (list (list
(make-nested-bad :bar (list y)))))))))
     (declare (dynamic-extent x))
     (unless (equalp (caar x) (make-nested-good :bar *bar*))
       (error "got ~S, wanted ~S" (caar x) (make-nested-good :bar *bar*)))
     (caar x)))

(caar x) is a stack-allocatable instance of NESTED, and returning that
value to the caller is just broken. Is it meant to return (nested-bar
(caar x)) (after adjusting :conservative-nested-dx to recons a structure)?

[Alastair Bridgewater (alastair-bridgewater)]

The test case seems to have been fixed to copy the stack-allocated structure (fixing the memory access problem, at least) in commit debae3c18d31b5222be4d5de8dcb2601336e24a4, and this bug report predates the 2015 improvements to stack analysis (some of which dealt with DX allocation). AFAICT, running the test code on current SBCL only produces the memory fault, and that only when trying to make use of the result of NESTED-BAD (tested, by calling NESTED-BAD by itself, which bombed, and by calling NESTED-BAD wrapped in a GET-LISP-OBJ-ADDRESS form, which returned a stack-address-looking-integer).

Basically, unless we're prepared to rewrite the dynamic-extent tests to use SB-INTROSPECT:ALLOCATION-INFORMATION, this bug can probably be closed. And if we ARE prepared to do that rewrite (or wish to for whatever reason) then it should be a separate bug, and this bug can probably be closed.