|
From: Jeremy F. <je...@go...> - 2005-02-24 17:06:58
|
Julian Seward wrote:
>The existing scheme is at least simple, in that you can simply say
>that a block is leaked/potentially leaked if no pointer to it is
>found/only a pointer to its interior is found. And from the kind of
>questions that have arisen in the past, it already confuses users.
>
>
That's possible. But I think a lot of people (including me) are being
mislead into thinking "oh, its only a small leak, no need to worry". A
lot of the code I've pointed this at (which isn't very much yet) has had
a much larger leakage problem than previously reported.
>Once you get into cycle detection, we need to explain about root sets
>and chasing pointers from there. Could you circulate a proposed
>documentation update?
>
>
OK. Hm, there doesn't seem to be any description about what the existing
leak checker does.
>* Clique is the wrong terminology. My understanding is that a clique
> is a completely-connected set of nodes in an undirected graph: each
> node-pair in the clique has a connecting edge. What you mean is
> Strongly Connected Components (SCCs), which are always associated with
> finding cycles in directed graphs.
>
>
Hm, it is a directed graph, and it is just looking for all the nodes it
contains. It isn't trying to find SCCs. The algorithm is very simple:
for each Unreached block:
push it onto the mark stack
mark everything traced from it as being IndirectLeak
The "clique leader" is the block which is left Unreached, and it
contains a summary of the size of all the blocks it points to.
The only slightly tricky part is when, while marking, we encounter a
block which was previously considered to be the root of a lost graph; it
gets merged into the current graph.
>* How much extra storage will the SCC detector require in the
> worst case?
>
>
None. It just reuses the marker machinery. The marker uses 2 words per
allocated block, which is only allocated during leak checking.
>In short, chase from all register sources,
>including vector registers.
>
Fair enough. It should probably skip registers/parts of registers which
the tool says is not defined though.
J
|