Patch for a couple of stack inconsistency bugs
somewhat-functional-programmer <[email protected]> Wed, 29 May 2019 13:21:18 +0000
| Newsgroups | gmane.editors.j.devel |
|---|---|
| Message-ID | <G9NKI9FmeEEs3Ds5GvgWtDz9yQ_EtYBYXU7HFZyqVKet9XxuSDV7NjdY85oAJLuBeGMFgvTIWoREE_sZ7accIfcjhqZdq9afjqNtEMaTbZs=__35535.5981899024$1559136123$gmane$org@protonmail.com> |
Hello list,
Lately I have been starting to dive deeper into Common Lisp and have started to
use ABCL more than SBCL or CCL lately. It is a very impressive project.
I want to post a patch for review/comments and hopefully have it be worthwhile
to eventually include it in ABCL. The patch attempts to fix a couple of stack
inconsistency bugs in the compiler. I came across the stack inconsistency issue
in one of my projects and started to try to find the root cause of the problem
based on a nice minimal reproduction of the bug found in
https://github.com/armedbear/abcl/issues/69.
However, my particular bug was slightly different. It had to do with using a
return-from in the cleanup form of an unwind-protect. The following two forms
also result in a stack inconsistency problem (and are a more minimal
reproduction of the bug my code introduced):
(defun two-arg-fn (one two)
(format t "Two args: ~S and ~S~%" one two))
(let ((fn (compile nil '(lambda ()
(two-arg-fn
(block test-block
(unwind-protect
30
(return-from test-block 8)))
-1)))))
(funcall fn))
My patch handles both the github issue and the stack inconsistency in the form
above. It also fixes jvm::print-code to print string representations of values
from the constant pool which I found useful in debugging the output.
Anyhow, let me attempt to quickly summarize the stack inconsistency problem in
general:
- Certain common lisp control flow forms
(tagbody/go/unwind-protect/block/return-from/throw/catch) require the use
of JVM exceptions to implement in bytecode
- When the JVM throws an exception, the operand stack is cleared and the
exception is pushed onto the operand stack (see jvms8, 6.5/athrow, p378)
- Therefore, any form which pushes values onto the operand stack for
further use is confounded when these control flow forms are child
forms
- To properly handle these alternate control flows we need to save the
result of the control flow form to a local variable in the stack frame
(distinct from the operand stack, and not destroyed by an exception
(well at least not until the exception passes /out/ of the method)
and then reload for use by the parent form to push on the operand stack
Take the case of the ash function (from the github issue). Bytecode for ash is
emitted from jvm::p2-ash. It compiles its arguments to the operand stack, and is
therefore vulnerable to the problem discussed above. Other low level functions
(like + for example in p2-plus) use the following forms to overcome this issue:
jvm::with-operand-accumulation and jvm::compile-operand. These forms save the
results of "unsafe" forms (opstack unsafe) to "registers" (local variables in
the stack frame). This technique allows for these complicated control flow forms
to be a child form of + with no issues, but not the ash function (which does not
do this). See my patch for how I added these already present
with-operand-accumulation and compile-operand forms to ash so it is no longer
vulnerable to stack inconsistency bugs.
Generally, function calls in ABCL are not vulnerable to these stack
inconsistency bugs. Function arguments are processed in jvm::process-args, and
in this function, the opstack safety of child forms is checked, and values are
saved to "registers" when a form is known to be unsafe. My case (the return-from
in the cleanup form of an unwind-protect) simply wasn't properly being marked as
opstack unsafe. I modified jvm::p1-unwind-protect to mark all direct children of
the unwind-protect as opstack unsafe, which eliminated my problem. I believe
there may have been confusion here in the code (speculation of course on my
part) of 'protected' form referring to the form actually protected by the
unwind-protect (which is totally different than being unsafe or needing opstack
/protection/) (or I'm misinterpreting this function and potentially causing
additional bugs!).
The only other item in my patch is fixing how bytecode is printed for debugging.
Basically, most items in a class constant pool are referenced with a 2 byte
index, but one (ldc) uses a one byte index). This has been accounted for in the
new function jvm::constant-pool-index.
Let me know what you think, and again please review, there aren't many lines
changed but I am new to the internals of the project. I think I ran all tests
(ant abcl.test) but while the ant task completed successfully, my output
complained of a missing dependency and I'm not sure what actually ran.
-Mark
The attached patch was produced against b3cfee6617e0c2c380d8675f3383d81e7758f358
from https://github.com/easye/abcl (latest master branch).
[jvms8] https://docs.oracle.com/javase/specs/jvms/se8/jvms8.pdf
stack-inconsistency-fixes.patch
(text/x-patch, 11.4 KB)
diff --git a/src/org/armedbear/lisp/compiler-pass1.lisp b/src/org/armedbear/lisp/compiler-pass1.lisp
index a4069af2..35298de7 100644
--- a/src/org/armedbear/lisp/compiler-pass1.lisp
+++ b/src/org/armedbear/lisp/compiler-pass1.lisp
@@ -673,12 +673,27 @@ where each of the vars returned is a list with these elements:
;; need to copy the forms to create a second copy.
(let* ((block (make-unwind-protect-node))
(*block* block)
- ;; a bit of jumping through hoops...
- (unwinding-forms (p1-body (copy-tree (cddr form))))
- (unprotected-forms (p1-body (cddr form)))
+
+ ;; i believe this comment is misleading...
+ ;; - from an /opstack/ safety perspective, all forms (including cleanup) can have non-local returns
+ ;; original comment: (and unwinding-forms and unprotected-forms were above this line previously, meaning they
+ ;; did not fall under an unwind-protect /block/ and hence lead to stack inconsistency problems)
;; ... because only the protected form is
;; protected by the UNWIND-PROTECT block
(*blocks* (cons block *blocks*))
+
+ ;; this may be ok to have /above/ the blocks decl, since these should not be present inside the
+ ;; exception handler and are therefore opstack safe
+ ;; my little test case passes either way (whether this is here or above)
+ ;; /but/ if the protected-form is marked as opstack unsafe, this should be too
+ ;; why is the protected form marked opstack unsafe?
+ (unwinding-forms (p1-body (copy-tree (cddr form))))
+
+ ;; the unprotected-forms actually end up inside an exception handler and as such, /do/ need
+ ;; to be marked opstack unsafe (so this is now below the *blocks* decl)
+ ;; (this name is now misleading from an opstack safety perspective)
+ (unprotected-forms (p1-body (cddr form)))
+
(protected-form (p1 (cadr form))))
(setf (unwind-protect-form block)
`(unwind-protect ,protected-form
diff --git a/src/org/armedbear/lisp/compiler-pass2.lisp b/src/org/armedbear/lisp/compiler-pass2.lisp
index edb670bb..389325bb 100644
--- a/src/org/armedbear/lisp/compiler-pass2.lisp
+++ b/src/org/armedbear/lisp/compiler-pass2.lisp
@@ -4242,20 +4242,30 @@ given a specific common representation.")
(<= -31 constant-shift 31)
(fixnum-type-p type1)
(fixnum-type-p result-type))
- (compile-form arg1 'stack :int)
(cond ((plusp constant-shift)
- (compile-form arg2 'stack :int)
- (maybe-emit-clear-values arg1 arg2)
+ (with-operand-accumulation
+ ((compile-operand arg1 :int)
+ (compile-operand arg2 :int)
+ (maybe-emit-clear-values arg1 arg2)))
(emit 'ishl))
((minusp constant-shift)
(cond ((fixnump arg2)
- (emit-push-constant-int (- arg2)))
+ (with-operand-accumulation
+ ((compile-operand arg1 :int)
+ (accumulate-operand (representation)
+ (emit-push-constant-int (- arg2)))
+ (maybe-emit-clear-values arg1))))
(t
- (compile-form arg2 'stack :int)
- (emit 'ineg)))
+ (with-operand-accumulation
+ ((compile-operand arg1 :int)
+ (accumulate-operand (representation :unsafe-p t)
+ (compile-form arg2 'stack :int)
+ (emit 'ineg))
+ (maybe-emit-clear-values arg1 arg2)))))
(maybe-emit-clear-values arg1 arg2)
(emit 'ishr))
((zerop constant-shift)
+ (compile-form arg1 'stack :int)
(compile-form arg2 nil nil))) ; for effect
(convert-representation :int representation)
(emit-move-from-stack target representation))
@@ -4264,20 +4274,30 @@ given a specific common representation.")
(<= -63 constant-shift 63)
(java-long-type-p type1)
(java-long-type-p result-type))
- (compile-form arg1 'stack :long)
(cond ((plusp constant-shift)
- (compile-form arg2 'stack :int)
- (maybe-emit-clear-values arg1 arg2)
+ (with-operand-accumulation
+ ((compile-operand arg1 :long)
+ (compile-operand arg2 :int)
+ (maybe-emit-clear-values arg1 arg2)))
(emit 'lshl))
((minusp constant-shift)
(cond ((fixnump arg2)
- (emit-push-constant-int (- arg2)))
+ (with-operand-accumulation
+ ((compile-operand arg1 :long)
+ (with-operand-accumulation (representation)
+ (emit-push-constant-int (- arg2)))
+ (maybe-emit-clear-values arg1))))
(t
- (compile-form arg2 'stack :int)
- (emit 'ineg)))
+ (with-operand-accumulation
+ ((compile-operand arg1 :long)
+ (accumulate-operand (representation :unsafe-p t)
+ (compile-form arg2 'stack :int)
+ (emit 'ineg))
+ (maybe-emit-clear-values arg1 arg2)))))
(maybe-emit-clear-values arg1 arg2)
(emit 'lshr))
((zerop constant-shift)
+ (compile-form arg1 'stack :long)
(compile-form arg2 nil nil))) ; for effect
(convert-representation :long representation)
(emit-move-from-stack target representation))
@@ -4293,21 +4313,27 @@ given a specific common representation.")
(cond ((and low2 high2 (<= 0 low2 high2 63) ; Non-negative shift.
(java-long-type-p type1)
(java-long-type-p result-type))
- (compile-forms-and-maybe-emit-clear-values arg1 'stack :long
- arg2 'stack :int)
+ (with-operand-accumulation
+ ((compile-operand arg1 :long)
+ (compile-operand arg2 :int)
+ (maybe-emit-clear-values arg1 arg2)))
(emit 'lshl)
(convert-representation :long representation))
((and low2 high2 (<= -63 low2 high2 0) ; Negative shift.
(java-long-type-p type1)
(java-long-type-p result-type))
- (compile-forms-and-maybe-emit-clear-values arg1 'stack :long
- arg2 'stack :int)
+ (with-operand-accumulation
+ ((compile-operand arg1 :long)
+ (compile-operand arg2 :int)
+ (maybe-emit-clear-values arg1 arg2)))
(emit 'ineg)
(emit 'lshr)
(convert-representation :long representation))
(t
- (compile-forms-and-maybe-emit-clear-values arg1 'stack nil
- arg2 'stack :int)
+ (with-operand-accumulation
+ ((compile-operand arg1 nil)
+ (compile-operand arg2 :int)
+ (maybe-emit-clear-values arg1 arg2)))
(emit-invokevirtual +lisp-object+ "ash" '(:int) +lisp-object+)
(fix-boxing representation result-type)))
(emit-move-from-stack target representation))
diff --git a/src/org/armedbear/lisp/jvm-instructions.lisp b/src/org/armedbear/lisp/jvm-instructions.lisp
index e985d55c..8626ab97 100644
--- a/src/org/armedbear/lisp/jvm-instructions.lisp
+++ b/src/org/armedbear/lisp/jvm-instructions.lisp
@@ -502,31 +502,59 @@
(and instruction
(= (the fixnum (instruction-opcode (the instruction instruction))) 202)))
+(defun constant-pool-index (instruction)
+ "If an instruction references an item in the constant pool, return
+ the index, otherwise return nil."
+ ;; 1 byte index
+ ;; 18 ldc
+ ;;
+ ;; 2 byte index
+ ;; 178 getstatic
+ ;; 179 putstatic
+ ;; 180 getfield
+ ;; 181 putfield
+ ;; 182 invokevirtual
+ ;; 183 invokespecial
+ ;; 184 invokestatic
+ ;; 185 invokeinterface
+ ;; 187 new
+ ;; 192 checkcast
+ ;; 193 instanceof
+ (when instruction
+ (case (instruction-opcode instruction)
+ (18 (first (instruction-args instruction)))
+ ((19 20 178 179 180 181 182 183 184 185 187 192 193)
+ (logior
+ (ash (first (instruction-args instruction)) 8)
+ (second (instruction-args instruction)))))))
+
(defun format-instruction-args (instruction pool)
- (if (memql (instruction-opcode instruction) '(18 19 20
- 178 179 180 181 182 183 184 185
- 187
- 192 193))
- (let ((*print-readably* nil)
- (*print-escape* nil))
+ (let* ((*print-readably* nil)
+ (*print-escape* nil)
+ (pool-index (constant-pool-index instruction))
+ (entry (when pool-index
+ (find-pool-entry pool pool-index))))
+ (when entry
+ (return-from
+ format-instruction-args
(with-output-to-string (s)
(print-pool-constant pool
- (find-pool-entry pool
- (car (instruction-args instruction))) s
- :package "org/armedbear/lisp")))
- (when (instruction-args instruction)
- (format nil "~S" (instruction-args instruction)))))
+ entry
+ s
+ :package "org/armedbear/lisp")))))
+ (when (instruction-args instruction)
+ (format nil "~S" (instruction-args instruction))))
(defun print-code (code pool)
(declare (ignorable pool))
(dotimes (i (length code))
(let ((instruction (elt code i)))
- (format t "~3D ~A ~19T~A ~A ~A~%"
+ (format t "~3D ~A ~19T~A ~@[IStack: ~A~] ~@[IDepth: ~A~]~%"
i
(opcode-name (instruction-opcode instruction))
(or (format-instruction-args instruction pool) "")
- (or (instruction-stack instruction) "")
- (or (instruction-depth instruction) "")))))
+ (instruction-stack instruction)
+ (instruction-depth instruction)))))
(defun print-code2 (code pool)
(declare (ignorable pool))
@@ -858,6 +886,7 @@
(declaim (ftype (function (t) t) analyze-stack))
(defun analyze-stack (code exception-entry-points)
(declare (optimize speed))
+ ;;(print-code code *pool*)
(let* ((code-length (length code)))
(declare (type vector code))
(dotimes (i code-length)