Re: Can userdate have references to lua objects?

[RLake@...]

> You could use the registry of course, but that needs some care: the link
> between the userdata and the references it contains should be through a
> weak-keyed table, or the userdata is not going to be collected.

Well, that is all that lua_ref does. So it's more or less equivalent.

> Also, a recent discussion by Alex, Roberto and Rici on this list seems to
be
> related and worth studying (subject: GC order.)  (A, R & R: did I still
miss
> something here?)

W: I don't know if you missed anything. For what its worth, here is a
"summary":

The problem with both Lua-4-style refs and Lua-5-style weak-keyed tables is
cyclic references: if the userdata references form a dag (directed acyclic
graph), you're fine. That means that there are no circular references (so
you could actually have used reference counting, but let me say here that
reference counting is not the ideal form of garbage collection even if you
know you have no circular references.)

The problem in both cases is the same: a contingent link which the garbage
collector doesn't know about. In the case of Lua-4 references, this is
unsolvable; in the case of Lua 5 weak-tables, at least one solution exists
although it is not yet implemented.

Let me try to explain what I mean by "contingent link".

First, how garbage collection works: A garbage collector traces through all
objects trying to figure out which ones can be referenced by the program.
It starts with objects on the stack and objects available through global
mechanisms (like the globals table). (These objects are called the "root
set".) It then applies a simple rule: If reachable object A contains a
reference to object B, then it assumes that B is reachable, and adds it to
the list. It keeps doing that until no more objects can be found; then
anything that has not been found is unreachable (there is no way the
program can reference it) and is therefore garbage.

So we can say that a reference to A implies a reference to B; therefore, B
is "live" (or reachable) if A is reachable. Hence B's existence is
"contingent" on A's existence. The reference in A to B is a "contingent
link".

That is actually a conservative estimate of reachability, though. It may be
that although A contains a reference to B, it will never use it, and has no
mechanism to provide it to other objects. In that case, B is not really
reachable through A, even though A contains a reference to it. I'll call
this an "extraneous reference." Under some circumstances (described in
detail below), circular extraneous references can lead to memory leaks.

In many garbage collection systems, it is possible for the programmer to
mark an extraneous reference as "weak". Weak references are simply not
followed by the garbage collector. Weak references were originally proposed
as a way to solve the circularity problem in reference-counting, but it
turned out to not be a very good solution because the programmer ends up
doing too much fairly difficult analysis. As we'll see, weak references
don't actually solve the "conservative estimate of reachability problem"
either. (They do have other uses, though.)

Now, we could say that in the case where A contains a strong reference to
B, that is a "contingent link"; that is, B's existence is contingent on A's
existence. The weak reference, on the other hand, does not form a
contingency relationship; a weak reference to B implies that B's existence
is *not* contingent on A's existence.

Now let's consider the case of an opaque object (say a userdata) A which
has no mechanism for storing references. However, we still want to create
contingent links from A to B. These links *cannot appear in A itself*.
(Another application is "annotation": say that A is immutable, or that we
don't want to change it, but we want to "annotate" it with B in way that
the annotation will disappear once A does.)

Our first attempt to do this is for A to put the reference to B in a
"registry". This registry is a global object, so it is part of the root
set; everything in it is considered reachable. If there is some mechanism
to allow A to know when it is about to be collected (a "finalisation"
routine), A can delete the reference to B when at this point. In essence,
we use the registry to define external contingency relationships. However,
the garbage collector does not know that A has done this, so it does not
know about the contingency relationship. As a result, once A becomes
unreachable (but before it has been collected) the registry's reference to
B is extraneous.

Unfortunately this means that if A is reachable from B (that is, there are
circular references), then A will never be collected. B is "reachable" from
the root set; A is reachable from B; so A is reachable from the root set.
So A will never be collected, and will therefore never let go of B. We have
a memory leak, even though we're using a garbage collector and this was
precisely the sort of problem that garbage collectors were intended to
solve: dealing with circular references.

We cannot fix this by making the registry contain a weak reference to B. If
we do that, there is nothing which "holds onto" B, and it could disappear
before A does. The weak reference does not provide a contingent link.

So what is wrong here? The problem is that we have a contingency
relationship in mind, but the garbage collector doesn't know about it. The
garbage collector therefore has to either be too conservative (which leads
to memory leaks) or too liberal (which leads to disappearing objects).
Neither of these is satisfactory.

Moreover, the registry does not solve the annotation problem, because it
depends on our being to able to change the behaviour of A (giving it a
finaliser, for example.)

So in Lua 5, the Lua authors came up with the idea of weak-keyed tables.
This is, in my opinion, a brilliant idea: a weak-keyed table is, in effect,
the declaration of a contingent link from the key to the value. Once the
key is no longer reachable, the key-value pair in the table is deleted and
the value is no longer reachable (through that means, anyway).

BUT, and this is an important "but", although the contingency information
is there staring the garbage collector in the face, as it were, the current
Lua-5 garbage collector does not make use of the information. The garbage
collector, instead, treats the weak-key/strong-value pair as though it were
a traditional weak reference/strong reference pair. This means that the
key->value contingency information is not used; the value is instead
contingent on the table. In other words, the garbage collector is going to
make a conservative estimate of the reachability of objects in the
weak-keyed table; values which are associated with unreachable keys are
extraneous, and if one of them refers to its key (even indirectly, even
through another weak-table contingency), this will create a memory leak.

So you can use this solution *only* if you know that there are no circular
references, and we're back to square one, except that there is a (to date
unimplemented) mechanism for solving the problem: getting the garbage
collector to understand weak tables as a collection of contingent links.
The mechanism is easy enough to implement; the only problem is that it
might be slow, or might create extra space overhead. (Until we test it, we
cannot really know how slow it is -- I am slowly coming round to the
conclusion that it is not actually that slow; and maybe someone will come
up with a better algorithm.)

----

If all that seems a bit theoretical, here is a simple example of the
annotation problem.

Suppose that I have several large tables, which I want to share with
various subsystems. The problem is that most of the time the subsystem will
not need to change the table, but it it does I don't want the original
table to be altered.

Metamethods give me a simple solution to this problem: lazy copying.

-- make and return a lazy copy of a
function lazycopy(a)
  return setmetatable({}, {__index = a})
end

Now the new table actually contains only the differences from the original
table, but it effectively contains everything. (Another solution would be
to cache successful lookups in the new table, which might or might not be
faster, depending on the depth of lazy copying.)

Looking at this code, I realise that the table {__index = a} will be
created for every lazy copy, even though it is a constant immutable table.
So I decide to "memoise" it; that is, I will annotate a with it's lazycopy
metatable:

do
  -- make a weak-keyed table
  local metas = setmetatable({}, {__mode = "k"})

  function lazycopy(a)
    local meta = metas[a]
    if not meta then
      meta = {__index = a}
      metas[a] = meta
    end
    return setmetatable({}, meta)
  end
end

(I would normally do the memoisation in the __index metamethod of metas, by
the way, but I've written like this for clarity.)

This will lead to a memory leak under the current implementation of
weak-keyed tables. Each value of metas (which is treated as a strong
reference) contains a reference to the key. So it doesn't matter that the
key is weak: once the value is marked, the key will be "reachable" and so
will never get collected.

----

There is a workaround -- someone is bound to suggest this if I don't --: a
could be used *as* the metatable. So I would write the following:

function lazycopy(a)
  if not rawget(a, "__index") then a.__index = a end
  return setmetatable({}, a)
end

I think this is unpleasant on a couple of grounds:

First, I need to modify the source table for it to work. Second, really odd
things might start to happen if certain fields (like __newindex) are added
to the source table. Finally, it is not easily extended. (For example, how
do you set up a "lazy merge" of two tables?)

Rici