This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

question about if_marked construct


In the context of bug 31230, I have a question about the if_marked construct.

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").

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:
- 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
- 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?


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]