DOLIST's detection of constant list arg can exhaust memory on circular lists
Affects | Status | Importance | Assigned to | Milestone | |
---|---|---|---|---|---|
SBCL |
Fix Released
|
Medium
|
Unassigned |
Bug Description
DOLIST uses LIST-MEMBERS so that it can insert into its expansion (THE (member <items>) loopvar).
But only a very specific case of circularity is detected. The general case is not:
* (sb-impl:
=>
Heap exhausted during garbage collection: 32 bytes available, 48 requested.
Gen StaPg UbSta LaSta LUbSt Boxed Unboxed LB LUB !move Alloc Waste Trig WP GCs Mem-age
0: 0 0 0 0 0 0 0 0 0 0 0 10737418 0 0 0.0000
1: 28980 0 0 0 13125 0 0 0 0 429658320 421680 268565578 0 1 1.4002
2: 32767 0 0 0 18324 3 0 0 16 600034640 504496 2000000 11571 0 0.6321
3: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
4: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
5: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
6: 0 0 0 0 1154 162 0 0 0 43122688 0 2000000 1123 0 0.0000
Total bytes allocated = 1072815648
Dynamic-
GC control variables:
*GC-INHIBIT* = true
*GC-PENDING* = in progress
fatal error encountered in SBCL pid 3135:
Heap exhausted, game over.
But this minimal example employs a circular list whose first three elements are not part of the cycle.
EVAL is used only to hide the const-ness from the compiler, proving that the code is otherwise fine.
The output varies randomly of course.
(let ((n 0))
(flet ((test-it (arg &aux (x (random 100)))
(< x 3)))
(dolist (item (eval ''(one two three . #1=(foo bar . #1#))))
(cond ((test-it item) (return 'yup))
=>
Iteration 1 : ONE 66
Iteration 2 : TWO 80
Iteration 3 : THREE 64
Iteration 4 : FOO 68
Iteration 5 : BAR 1
YUP
Maybe if LIST-WITH-LENGTH-P is false of the constant list we should not try so hard to insert a member type?
Changed in sbcl: | |
status: | New → Confirmed |
status: | Confirmed → In Progress |
importance: | Undecided → Medium |
assignee: | nobody → Paul Khuong (pvk) |
Changed in sbcl: | |
status: | In Progress → Fix Committed |
Changed in sbcl: | |
status: | Fix Committed → Fix Released |
Changed in sbcl: | |
assignee: | Paul Khuong (pvk) → nobody |
Fixed in
commit 678a5d0cd5bfccf 621e11147507471 c3f511595c
Author: Paul Khuong <email address hidden>
Date: Thu Jan 3 10:31:09 2013 -0500
Do not traverse long constant lists when expanding DOLIST
* Only gather type information on the list contents' if it's short
(at most 20 elements); otherwise, do not derive type information.
* Thanks to Douglas Katzman for the bug report (lp#1095488).