Memory leakage in Lisp
Drew McDermott
impossible, but in fact they do seem to occur. I have had the following
experience in more than one Lisp implementation: Memory space is
allocated and then never reclaimed by the garbage collector, even though
there is no way that I know of to get to the stuff that is supposedly
still in use.
My assumption is that there is in fact some sneaky path to the would-be
garbage that is keeping it alive. But I've thought of all the obvious
starting points for such a path (such as: global variables set up for
debugging purposes and then forgotten, pointers from *, **, or ***,
etc.). The question is: Are there any portable or nonportable tools for
finding such starting points? (I'm currently using Allegro 6.2, so a
tool that worked in that implementation would be fine, but the Allegro
GC documentation doesn't mention such a thing.)
-- Drew McDermott
Paul F. Dietz
> My assumption is that there is in fact some sneaky path to the would-be
> garbage that is keeping it alive. But I've thought of all the obvious
> starting points for such a path (such as: global variables set up for
> debugging purposes and then forgotten, pointers from *, **, or ***,
> etc.). The question is: Are there any portable or nonportable tools for
> finding such starting points? (I'm currently using Allegro 6.2, so a
> tool that worked in that implementation would be fine, but the Allegro
> GC documentation doesn't mention such a thing.)
You can have leaked roots on the stack. We also found that
Allegro CL has some memory where it stores the VALUES vector,
and that area can retain roots. Try calling a function like
(defun cleanse-values ()
(values nil nil nil nil nil nil nil nil nil nil))
(or something like that) to flush this vector.
I think the debugging package in Allegro can be used to access
the stack to look for roots.
Paul
Erik Naggum
| I know that garbage collection is supposed to make memory leaks
| impossible, but in fact they do seem to occur.
A memory leak is defined as memory that cannot be referenced, yet is not
reclaimed and available for re-use. Since the whole point with garbage
collection is to reclaim memory that cannot be referenced, and copying
garbage collectors have a really hard time copying memory that is not
actually referenced, something is clearly amiss here. Unless you think
there is a bug in the garbage collection algorithm, I think calling it a
"memory leak" is misleading.
I presume you are not talking about the memory that has been allocated
from the system and that is available to allocate from within the Common
Lisp system. You can ask Allegro CL to release such memory with the
function `system:resize-areasด.
| I have had the following experience in more than one Lisp implementation:
| Memory space is allocated and then never reclaimed by the garbage
| collector, even though there is no way that I know of to get to the stuff
| that is supposedly still in use.
How do you see the discrepancy? Is the output from `(room t)ด misleading?
--
Erik Naggum, Oslo, Norway
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
Gabe Garza
> I know that garbage collection is supposed to make memory leaks
> impossible, but in fact they do seem to occur. I have had the following
> experience in more than one Lisp implementation: Memory space is
> allocated and then never reclaimed by the garbage collector, even
> though there is no way that I know of to get to the stuff that is
> supposedly still in use.
This may not apply to your cases and you've probably eliminated
something like this as a possibility, but for the sake of
googlers... In LispWorks, this can appear to happen if you don't
collect generations 2 or 3, which is the default. You have to call
both HCL:COLLECT-GENERATION-2 and HCL:COLLECT-HIGHEST-GENERATION for
those two generations to be collected (although on the one application
were I needed to do this enabling these caused it to randomly crash
hard without warning. I ended up manually calling HCL:MARK-AND-SWEEP
every five minutes or so...)
Gabe Garza
Espen Vestre
> googlers... In LispWorks, this can appear to happen if you don't
> collect generations 2 or 3, which is the default. You have to call
> both HCL:COLLECT-GENERATION-2 and HCL:COLLECT-HIGHEST-GENERATION for
> those two generations to be collected (although on the one application
> were I needed to do this enabling these caused it to randomly crash
> hard without warning. I ended up manually calling HCL:MARK-AND-SWEEP
> every five minutes or so...)
I think occasionally calling mark-and-sweep is a much better idea than
using collect-generation-2 or collect-highest-generation. Every 5
minutes is extreme, though. If your application has a lot of short-but-
not-short-enough-lived objects, you may get them to live a little longer
by experimenting with the parameters that control the size of the
lower generations.
I have a server application that runs for weeks: It calls
(mark-and-sweep 2) every morning after some data from yesterday have
been discarded, and then once an hour it analyzes data allocation
and then calls (mark-and-sweep 2) if x MB of memory has been allocated
in gen. 2 since the last run. This results in a total of about 5
mark-and-sweeps per day, each of them lasts for about 300-1500 ms.
However, for some really difficult applications, your generation 2
may get fragmented over time, and you may need to compact it. In
those cases, it's probably wise to open an support case with Xanalys.
One last thing: If you experience lots of promotions to gen. 3, you're
probably hit by a bug that was fixed in LispWorks 4.2.7.
--
(espen)
Joe Marshall
> My assumption is that there is in fact some sneaky path to the
> would-be garbage that is keeping it alive. The question is: Are
> there any portable or nonportable tools for finding such starting
> points?
I wrote such a tool for Lucid Common Lisp back in 1989, but I don't
know if it still exists. The basic idea is this:
Consider the entire heap to be a directed graph where the edges are
pointers and the nodes are the manifest objects. For each edge, one
can compute how much storage would be freed if that edge were cut
(i.e., the total sum of the size of each nodes that is reachable only
via that edge). Call this the weight of the edge.
The weight of the edges that lead out of the value cells of symbols
give you some idea of how much storage is being retained by that
symbol.
If you take all the edges leading *into* a structure or class of a
particular type, and divide the total weight by the number of edges,
you get an `average size' for that type of structure. This is a
measure of how much storage is being retained by the structure and all
of its subcomponents rather than a simple measure of the size of the
top-level structure itself.
---
A client of Lucid was complaining about `memory leaks'. While it is
patently absurd for the GC to `leak' memory, they wanted an accounting
of where the memory was actually being used. I wrote the code
described above and analyzed the heap of a lisp that had been running
their code for a while. I discovered that the symbol *HISTORY* was
the sole pointer to a huge amount of storage, and that structures of
type HISTORY-OBJECT, although small in themselves (a few dozen bytes),
and small in number (a handful of them), each held several tens of
Kbytes that were reachable in no other way. The entire `leak' was
accounted for by these objects.
(room t) didn't help because it simply reported that there
were a few hundred bytes taken up by HISTORY-OBJECTs, rather than that
the bulk of the CONS cells and VECTORS were being pointed to by the
HISTORY objects.
The hard part of this analysis is determining the weight of an edge
and finding the large weights. Determining the weight of every edge
in the heap would require storage proportional to the size of the
heap, and it is difficult given a random object to determine how
much storage would be freed without simulating a full garbage
collection. However, the concept behind the analysis is easy enough.
If the code still exists, I'd like to hear about it. If not, it
shouldn't take too long to write a reasonably portable version.
William D Clinger
> I know that garbage collection is supposed to make memory leaks
> impossible, but in fact they do seem to occur.
Drew, most compilers introduce space leaks by leaving stale pointers
in stack frames, some garbage collectors (e.g. conservative or DOF
collectors) do not in fact guarantee that all unreachable storage will
eventually be reclaimed, and most generational garbage collectors
operate with considerable floating garbage as a matter of course.
If your memory leaks are detectable at top level, then the compiler
probably isn't at fault, and I would guess that you aren't forcing
a full garbage collection. How you force a full collection is very
implementation-dependent, and some systems don't provide any way to
do it.
These remarks are general; I know next to nothing about Allegro CL.
Will
Lois Wolf
"Drew McDermott" <drew.mc...@yale.edu> wrote in message
news:3DDABDFA...@yale.edu...
> I have had the following
> experience in more than one Lisp implementation: Memory space is
> allocated and then never reclaimed by the garbage collector, even though
> there is no way that I know of to get to the stuff that is supposedly
> still in use.
>
> My assumption is that there is in fact some sneaky path to the would-be
> garbage that is keeping it alive. But I've thought of all the obvious
> starting points for such a path (such as: global variables set up for
> debugging purposes and then forgotten, pointers from *, **, or ***,
> etc.). The question is: Are there any portable or nonportable tools for
> finding such starting points? (I'm currently using Allegro 6.2, so a
> tool that worked in that implementation would be fine, but the Allegro
> GC documentation doesn't mention such a thing.)
There are two tools in Allegro CL 6.2 to track down non-reclaimed
objects: excl::get-objects and excl::get-references. They are not
exported/documented because they are messy, in that use of the tools
changes the heap by creating arrays which reference other objects in
the heap.
Each of these tools is a heap-walker, and thus returns what we call
a heapwalker result vector. A heapwalker result-vector is an array
whose first element is a number N, and the next N elements are
results. The result-vector will almost always be larger than (1+ N),
because some slop is added to the required size in order to guard
against any additional items coming into existence between the first
and second passes of the heap-walk.
Now for the tools:
excl::get-objects accepts a code argument. The code is the type
number which appears in the left-hand column of a (room t) output, and
which is labeled "code". All objects of that type are placed into a
heapwalker result-vector and returned. So, for example, if you
say (excl::get-objects 96), it will return a result-vector which
contains all of the (simple-array t (*)) objects in the lisp heap.
(however, be aware that the result vector is itself a (simple-array t (*))
so a second call to the same function will include that old result
vector in the new results).
excl::get-references accepts one argument wich can be any lisp-object,
and returns a result-vector of all objects (except stack-groups)
which refer to that object in any of its slots. It is in a sense a
backward-chain-walker. This tool can help you to find what objects
are being pointed to and thus why they are not being gc'd.
Some rules of thumb to know about excl::get-references results:
- You should do a (gc t) before you start using this tool.
Heapwalkers don't care if an object is dead or not, so it may be that
you are grabbing objects from the heap which would have otherwise
been collected because it was dead.
- You should remember that *, **, and *** are assigned results
from previous invocations of excl::get-references, so it is likely
that one of them will be in the next result-vector.
- Since previous result-vectors now hold pointers to what you are
looking for, they tend to show up in newer result-vectors, so the
results tend to get pretty messy.
Fortunately, however, the heapwalker tends to walk from oldest to
newest, so the first objects in any result-vector will be the older
ones. The rule is only general for cons cells, however, so it should
be taken with a grain of salt.
So a typical run might look like this, in which we trace one of the
pointers to excl::*expire-days* back to the excl package:
CL-USER(2): (inspect (excl::get-objects 7))
A simple T vector (15738) @ #x30460532
0-> fixnum 15718 [#x0000f598]
1-> The symbol EXCL::*EXPIRE-DAYS*
2-> The symbol EXCL::FASL-CASEMODE-MISMATCH-ERROR
3-> The symbol :ADDRESS
4-> The symbol STRING-TO-NATIVE
5-> The symbol STRING-TO-OCTETS
6-> The symbol EXCL::FWRAP-HOOK
7-> The symbol EXCL::&
8-> The symbol EXCL::FREWRAP
9-> The symbol :DOUBLE
10-> The symbol :FLOAT
11-> The symbol :UNSIGNED-CHAR
12-> The symbol :UNSIGNED-SHORT
13-> The symbol :UNSIGNED-LONG
14-> The symbol :UNSIGNED-INT
15-> The symbol :CHAR
16-> The symbol :SHORT
17-> The symbol :LONG
18-> The symbol :INT
19-> The symbol EXCL::GET-BASIC-FUNCTION
20-> The symbol EXCL::*ENCAPSULATION-COUNT*
21-> The symbol SYS::INVALID-RT-FUNCTION
22-> The symbol EXCL::*FWRAP-HASH-TABLE*
23-> The symbol EXCL::FIXUP-HANDLER-LOC
24-> The symbol :CONVERT
...
15737-> The symbol NIL
[1i] CL-USER(3): :i 1
The symbol EXCL::*EXPIRE-DAYS* @ #x3000123f
which is an INTERNAL symbol in the EXCL package
0 type ---------> Bit field: #x07
1 flags --------> Bit field: #x41
2 hash ---------> Bit field: #xf7fa
3 value --------> The symbol NIL
4 package ------> The EXCL package
5 function -----> #<Function (unnamed) @ #x300021da>
6 name ---------> A simple-string (13) "*EXPIRE-DAYS*"
7 plist --------> (COMP::.GLOB-SYMBOL-EXT. ...), a proper list with 4
elements
[1i] CL-USER(4): (excl::get-references 'excl::*expire-days*)
#(9 (EXCL::*EXPIRE-DAYS* . 290) *
#((:EMPTY) (:EMPTY) EXCL::CONTINUABLE EXCL::CLEAN-DFUN-CONSTRUCTORS
EXCL::ENTRY-VEC- EXCL::EQL-NOT-EQ (:EMPTY) (:EMPTY) (:EMPTY) (:EMPTY)
...)
(EXCL::*EXPIRE-DAYS* NIL 805311039) (EXCL::*EXPIRE-DAYS*)
(EXCL::*EXPIRE-DAYS* T 805311039) (EXCL::*EXPIRE-DAYS*)
#(15718 EXCL::*EXPIRE-DAYS* EXCL::FASL-CASEMODE-MISMATCH-ERROR :ADDRESS
STRING-TO-NATIVE STRING-TO-OCTETS EXCL::FWRAP-HOOK EXCL::& EXCL::FREWRAP
:DOUBLE ...)
#S(...) ...)
[1i] CL-USER(5): (excl::get-references (aref * 3))
#(2 #<SYMBOL hash-table (sans values) with 5409 entries @ #x3002a80a>
#(9 (EXCL::*EXPIRE-DAYS* . 290) *
#((:EMPTY) (:EMPTY) EXCL::CONTINUABLE EXCL::CLEAN-DFUN-CONSTRUCTORS
EXCL::ENTRY-VEC- EXCL::EQL-NOT-EQ (:EMPTY) (:EMPTY) (:EMPTY) (:EMPTY)
...)
(EXCL::*EXPIRE-DAYS* NIL 805311039) (EXCL::*EXPIRE-DAYS*)
(EXCL::*EXPIRE-DAYS* T 805311039) (EXCL::*EXPIRE-DAYS*)
#(15718 EXCL::*EXPIRE-DAYS* EXCL::FASL-CASEMODE-MISMATCH-ERROR :ADDRESS
STRING-TO-NATIVE STRING-TO-OCTETS EXCL::FWRAP-HOOK EXCL::&
EXCL::FREWRAP
:DOUBLE ...)
#S(...) ...)
NIL NIL NIL NIL NIL NIL NIL ...)
[1i] CL-USER(6): (excl::get-references (aref * 1))
#(2 #<The EXCL package>
#(2 #<SYMBOL hash-table (sans values) with 5409 entries @ #x3002a80a>
#(9 (EXCL::*EXPIRE-DAYS* . 290) *
#((:EMPTY) (:EMPTY) EXCL::CONTINUABLE EXCL::CLEAN-DFUN-CONSTRUCTORS
EXCL::ENTRY-VEC- EXCL::EQL-NOT-EQ (:EMPTY) (:EMPTY) (:EMPTY)
(:EMPTY)
...)
(EXCL::*EXPIRE-DAYS* NIL 805311039) (EXCL::*EXPIRE-DAYS*)
(EXCL::*EXPIRE-DAYS* T 805311039) (EXCL::*EXPIRE-DAYS*)
#(15718 EXCL::*EXPIRE-DAYS* EXCL::FASL-CASEMODE-MISMATCH-ERROR
:ADDRESS
STRING-TO-NATIVE STRING-TO-OCTETS EXCL::FWRAP-HOOK EXCL::&
EXCL::FREWRAP :DOUBLE ...)
#S(...) ...)
NIL NIL NIL NIL NIL NIL NIL ...)
NIL NIL NIL NIL NIL NIL NIL ...)
[1i] CL-USER(7):
Eric Marsden
lw> There are two tools in Allegro CL 6.2 to track down
lw> non-reclaimed objects: excl::get-objects and
lw> excl::get-references. They are not exported/documented because
lw> they are messy, in that use of the tools changes the heap by
lw> creating arrays which reference other objects in the heap.
this is interesting information. There are similar functions in CMUCL
called VM::LIST-ALLOCATED-OBJECTS and VM::LIST-REFERENCING-OBJECTS,
which return lists instead of vectors. Each takes a first SPACE
argument indicating whether to scan dynamic space, static space or
read-only space.
The example below shows how to obtain a list all objects of type
double-float in read-only space, and a list of all strings of length
42 in read-only space:
,----
| USER> (vm::list-allocated-objects :read-only :type vm::double-float-type)
| (0.0d0 1.8446744073709553d+19 -1.8446744073709553d+19 -3.141592653589793d0
| 1.5707963267948966d0 -1.5707963267948966d0 3.141592653589793d0 -1.0d0 1.0d0
| -0.0d0 0.0d0 0.0d0 -0.0d0 0.0d0 0.0d0 1.0d0 177.61896501848597d0
| 2.147483648d+9 -2.1474836490000002d+9 1.1102230246251568d-16
| 5.551115123125784d-17 -2.2250738585072014d-308 -2.2250738585072014d-308
| 4.940656458412465d-324 -1.7976931348623157d+308 1.7976931348623157d+308
| -4.940656458412465d-324 1.1102230246251568d-16 5.551115123125784d-17
| -1.7976931348623157d+308 4.940656458412465d-324 -4.940656458412465d-324
| 1.7976931348623157d+308 2.2250738585072014d-308 2.2250738585072014d-308
| 5.368709110000001d+8 0.0d0 -5.36870912d+8 0.0d0 0.0d0 -0.0d0
| #.EXT:DOUBLE-FLOAT-NEGATIVE-INFINITY #.EXT:DOUBLE-FLOAT-NEGATIVE-INFINITY
| #.EXT:DOUBLE-FLOAT-POSITIVE-INFINITY 308.2547155599167d0 -307.6526555685887d0
| 1.0d+7 0.001d0 1.0d+16 0.1d0 1.0d0 -3.141592653589793d0 0.5d0 0.25d0 4.0d0
| 2.983336292480083d-154 1.5707963267948966d0 -1.5707963267948966d0
| 3.351951982485649d+153 3.0d0 1.2d0 0.7071067811865475d0 0.6931471805599453d0
| 3.141592653589793d0 10.0d0 0.3010299914836512d0 0.0d0 0.0d0 0.5d0
| #.EXT:DOUBLE-FLOAT-POSITIVE-INFINITY 2.0d0 4.450147717014402d-308 -1.0d0 0.0d0
| 1.0d0 #.EXT:DOUBLE-FLOAT-POSITIVE-INFINITY -1.0d0 0.0d0 1.0d0
| 5.368709110000001d+8 -5.36870912d+8)
| USER> (vm::list-allocated-objects :read-only :type vm::simple-string-type
| :test (lambda (obj) (= 42 (length obj))))
| ("DEFMETHOD WRAPPER-FETCHER (STANDARD-CLASS)"
| "(.pv-cell. .next-method-call. specializer)"
| "DEFUN GET-COMPLEX-INITIALIZATION-FUNCTIONS"
| "DEFMETHOD DOCUMENTATION (FUNCTION (EQL #))"
| [...]
| "Veritas aeterna, can't declare ~S special."
| "Can't declare ~S special, it is a keyword."
| "Trying to declare ~S special, which is ~A."
| "COMPILED-DEBUG-FUNCTION-COMPILER-DEBUG-FUN"
| "Too large to be represented as a ~S:~% ~S"
| "~D is too big; ~S only has ~D dimension~:P")
`----
and the example below shows how to find all references to a given object
in a given space:
,----
| USER> (vm::list-referencing-objects :static *print-case*)
| (common-lisp::*previous-case* *print-case* #<(simple-vector 4096) {28018817}>
| :downcase #<(simple-vector 2729) {28002767}>)
| USER> (vm::list-referencing-objects :static #\Nul)
| ((#\Null 8 sparc:simple-string-type) ("Nul" . #\Null) ("^@" . #\Null)
| ("Null" . #\Null))
`----
These functions can produce lots of output; you probably don't want to
have *PRINT-ARRAY* set. More information on the breakdown of types of
objets allocated and the space that they occupy is available by
calling (ROOM T).
lw> Each of these tools is a heap-walker, and thus returns what we call
lw> a heapwalker result vector. A heapwalker result-vector is an array
lw> whose first element is a number N, and the next N elements are
lw> results.
the CMUCL function VM::MAP-ALLOCATED-OBJECTS allows you to walk the
heap; it calls a user-provided function on each allocated object.
Examples of usage are available in the CMUCL source code, in the file
src/code/room.lisp.
--
Eric Marsden <URL:http://www.laas.fr/~emarsden/>