Hi,
In the context of bug 31230, I have a question about the if_marked
construct.
[DOC http://gcc.gnu.org/onlinedocs/gccint/GTY-Options.html]
if_marked ("expression")
Suppose you want some kinds of object to be unique, and so you
put them in a hash table. If garbage collection marks the hash table,
these objects will never be freed, even if the last other reference
to them goes away. GGC has special handling to deal with this: if you
use the if_marked option on a global hash table, GGC will call the
routine whose name is the parameter to the option on each hash table
entry. If the routine returns nonzero, the hash table entry will be
marked as usual. If the routine returns zero, the hash table entry
will be deleted.
The routine ggc_marked_p can be used to determine if an element has
been marked already; in fact, the usual case is to use if_marked
("ggc_marked_p").
[/DOC]
Suppose we have a tree for type A and a tree for type B called A and
B for short, with both A and B having entries in the type_hash_table
called EA and EB, and as complication that A references B.
Suppose also that we have the following function type_hash_marked_p()
as the if_marked function:
...
static int prop(const_tree type)
{
return type == A;
}
static int type_hash_marked_p (const void *p) {
const_tree const type = ((const struct type_hash *) p)->type;
return ggc_marked_p (type) || prop (type);
}
...
During ggc_mark_roots(), when A and B are not live, 2 scenarios can
happen:
I.
- A and B are not marked
- EA is visited, and since prop(A) holds, EA is marked, then A, then B
- EB is visited, an since B is marked, it is not deleted
II.
- A and B are not marked
- EB is visited, and since prop(B) does not hold, EB is deleted
- EA is visited, an since prop(A) holds, EA is marked, then A, then B
The problem is that depending on the order in which we visit the hash
table entries EB is either marked or deleted.
I see 2 possible approaches to make the behavior predictable:
1. prop() needs to be transitively closed, in other words, prop(A)
and A references B needs to imply prop(B)
2. the garbage collector needs to calculate the transitive closure of
prop(), before deleting any hash table entries.
Approach 1 seems error-prone to me, but that does seem to be the de-
facto choice right now.
Can somebody please comment?
Regards
Tom
