Pathological Erroneous Reclamation

[Eleanor Bartle]

The description of the generational collector given in the recent evolution paper implies that each step along the main promotion chain (NEW->SURVIVAL->OLD1->OLD) can point to the previous step, that is, OLD can point to OLD1 can point to SURVIVAL can point to NEW. Thus, OLD may transitively refer to NEW. However, OLD is not traversed, so if such a transitive reference is the only reference to NEW, then NEW will be collected at the next cycle despite being reachable from the root set.

I know this is a pathological case, but I find it hard to believe that such an erroneous collection is possible. So, where is the error in my understanding?

[Sainan]

I have no understanding of Lua's GC internals, but based on what you are saying, OLD is not *directly* pointing at NEW and instead pointing at OLD1, which itself points at SURVIVIAL, which itself points at NEW.

Given then that SURVIVIAL is the actual reference holder for NEW, we need not traverse OLD to keep NEW alive.

-- Sainan

[Roberto Ierusalimschy]

> I have no understanding of Lua's GC internals, but based on what you are saying, OLD is not *directly* pointing at NEW and instead pointing at OLD1, which itself points at SURVIVIAL, which itself points at NEW.
>
> Given then that SURVIVIAL is the actual reference holder for NEW, we need not traverse OLD to keep NEW alive.

More specifically, let us consider "*OLD* can point to *OLD1* can point
to *SURVIVAL* can point to *NEW*."

OLD is not traversed, so the fact that it points to OLD1 is ignored.
But OLD1 cannot be collected and it is traversed no matter what, so it
keeps SURVIVAL alive. Then SURVIVAL, being alive, keeps *NEW* alive.

OLD1 is the key ingredient here.

-- Roberto

[Eleanor Bartle]

So OLD1 is traversed even if not transitively from the root set? Is there a special list for OLD0 and OLD1, like the TOUCHED list?

--
You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/Hzv9UbN2PKA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/lua-l/20250429134916.GA1299365%40arraial.inf.puc-rio.br.

[Yan]

Here is my understanding from Lua 5.4.7 code. If there are any mistakes, please point them out.

For example you have a `G_OLD` and `black` table named `foo`, then setmetabletable for `foo`: `setmetabletable(foo, mt)`. mt is newly created. Then it triggers barrier.
in `luaC_barrier_`
  set `mt`'s age to `G_OLD0`, set `mt`'s color to `gray`. the `mt` is in `g-gray` linked list.
next minor collection comes:
in `youngcollection`
  in `atomic`
    `mt` is traversed. color is `black`.
  in `sweepgen`
    set `mt`’s age to `G_OLD1`.
  the objects which `mt` point to FROM `G_NEW` to `G_SURVIVAL`

next minor collection comes:
in `youngcollection`
  in `markold`
    set `mt`' age to `G_OLD`. if `mt` is black, then `reallymarkobject`. Make sure `mt` will be traversed in `atomic`
  in `atomic`
    `mt` is traversed. color is `black`.
  the objects which `mt` point to FROM `G_SURVIVAL` to `G_OLD1`.
 
You can read https://github.com/lua/lua/blob/master/lgc.h#L126.

[Eleanor Bartle]

I think that comment block has a mistake. It says OLD1 and TOUCHED2 are kept black, but they can point to SURVIVAL which are kept white -- an invariant violation.

--

You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/Hzv9UbN2PKA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/d5cea5f3-501d-4968-a678-d0c2e21b657bn%40googlegroups.com.

[Yan]

`G_OLD1` may still points to `G_SURVIVAL` (REMEMBER: `G_OLD1` don't point to `G_NEW`). So in `markold` function, invoke `reallymarkobject` to make sure the objects which `G_OLD1` points to will be traversed, after this traversing, there will be no young objects.
 
```c
/*
** Mark black 'OLD1' objects when starting a new young collection.
** Gray objects are already in some gray list, and so will be visited
** in the atomic step.
*/
static void markold (global_State *g, GCObject *from, GCObject *to) {
  GCObject *p;
  for (p = from; p != to; p = p->next) {
    if (getage(p) == G_OLD1) {
      lua_assert(!iswhite(p));
      changeage(p, G_OLD1, G_OLD);  /* now they are old */
      if (isblack(p))
        reallymarkobject(g, p);
    }
  }
}
```

` G_TOUCHED2 ` may still points to `G_SURVIVAL`. When it becomes `G_TOUCHED2`, it is still in the `g->grayagain`. Next gc cycle, make sure the objects `G_TOUCHED2` points to will be traversed, after this traversing, there will be no young objects.

```
// in correctgraylist function
else if (getage(curr) == G_TOUCHED1) {  /* touched in this cycle? */
  lua_assert(isgray(curr));
  nw2black(curr);  /* make it black, for next barrier */
  changeage(curr, G_TOUCHED1, G_TOUCHED2);
  goto remain;  /* keep it in the list and go to next element */
}
```

Eleanor Bartle <essenc...@gmail.com> 于2025年5月15日周四 08:15写道：

[Eleanor Bartle]

Oh, I see, the colours are for barriers. That makes more sense.

So, OLD1 is changed to OLD at the beginning of a cycle, and TOUCHED1 to TOUCHED2 at the end; when do the other state transitions happen? Which ones are atomic, and which ones run interspersed with the mutator, if any?

Also, I noticed a WHITE1BIT in the code; what does that mean?

--

You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/Hzv9UbN2PKA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/lua-l/CACYGEmTfTUYpAjhRRtB4Fc3OYoMH6s3kyXaqioL9HgGLg7NaMQ%40mail.gmail.com.