Garbage Collection Breaks Next

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Garbage Collection Breaks Next

Xmilia Hermit

Hi,

I think there is either an error in the manual or a bug in the implementation regarding the next function.
The manual state for the lua function next:
"The behavior of next is undefined if, during the traversal, you assign any value to a non-existent field in the table. You may however modify existing fields. In particular, you may set existing fields to nil."
https://www.lua.org/manual/5.4/manual.html#pdf-next

However, in the following example during the traversal all elements are set to nil. This is allowed by the manual but it throws an error if the collectgarbage call isn't commented out.

function LoopAndEmpty(t)
    for k, v in pairs(t) do
        t[k] = nil
        coroutine.yield(k, v)
    end
end

local c = coroutine.create(LoopAndEmpty)
local t = {}
t["no" .. "ref1"] = 1
t["no" .. "ref2"] = 2
print(coroutine.resume(c, t))
collectgarbage("collect")
print(coroutine.resume(c))

The problem seems to be that the key "noref1" or "noref2" is white when the table t is travered and then in traversestrongtable in https://github.com/lua/lua/blob/master/lgc.c#L526 the key is cleared. This should not be the case since it could be marked later.

Regards,
Xmilia

Reply | Threaded
Open this post in threaded view
|

Re: Garbage Collection Breaks Next

Roberto Ierusalimschy
> I think there is either an error in the manual or a bug in the
> implementation regarding the next function.
> The manual state for the lua function next:
> "The behavior of next is undefined if, during the traversal, you assign any
> value to a non-existent field in the table. You may however modify existing
> fields. In particular, you may set existing fields to nil."
> https://www.lua.org/manual/5.4/manual.html#pdf-next
>
> However, in the following example during the traversal all elements are set
> to nil. This is allowed by the manual but it throws an error if the
> collectgarbage call isn't commented out.
>
> function LoopAndEmpty(t)
>     for k, v in pairs(t) do
>         t[k] = nil
>         coroutine.yield(k, v)
>     end
> end
>
> local c = coroutine.create(LoopAndEmpty)
> local t = {}
> t["no" .. "ref1"] = 1
> t["no" .. "ref2"] = 2
> print(coroutine.resume(c, t))
> collectgarbage("collect")
> print(coroutine.resume(c))
>
> The problem seems to be that the key "noref1" or "noref2" is white when the
> table t is travered and then in traversestrongtable in
> https://github.com/lua/lua/blob/master/lgc.c#L526 the key is cleared. This
> should not be the case since it could be marked later.

I guess you are right.

A curiosity: How did you realise that you had to use a coroutine in your
example? (I am still trying to produce the bug without coroutines, but
the key is always traversed before the table.)

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: Garbage Collection Breaks Next

Xmilia Hermit

>> I think there is either an error in the manual or a bug in the
>> implementation regarding the next function.
>> The manual state for the lua function next:
>> "The behavior of next is undefined if, during the traversal, you assign any
>> value to a non-existent field in the table. You may however modify existing
>> fields. In particular, you may set existing fields to nil."
>> https://www.lua.org/manual/5.4/manual.html#pdf-next
>>
>> However, in the following example during the traversal all elements are set
>> to nil. This is allowed by the manual but it throws an error if the
>> collectgarbage call isn't commented out.
>>
>> function LoopAndEmpty(t)
>>      for k, v in pairs(t) do
>>          t[k] = nil
>>          coroutine.yield(k, v)
>>      end
>> end
>>
>> local c = coroutine.create(LoopAndEmpty)
>> local t = {}
>> t["no" .. "ref1"] = 1
>> t["no" .. "ref2"] = 2
>> print(coroutine.resume(c, t))
>> collectgarbage("collect")
>> print(coroutine.resume(c))
>>
>> The problem seems to be that the key "noref1" or "noref2" is white when the
>> table t is travered and then in traversestrongtable in
>> https://github.com/lua/lua/blob/master/lgc.c#L526 the key is cleared. This
>> should not be the case since it could be marked later.
> I guess you are right.
>
> A curiosity: How did you realise that you had to use a coroutine in your
> example? (I am still trying to produce the bug without coroutines, but
> the key is always traversed before the table.)


The stack of the mainthread is traversed first. If the key is on this
stack, it will be marked before any table is traversed through the gray
stack. Therefore normal for in loops in the main thread will never see
this behaviour.

I had an example without coroutines too, but it doesn't use a pairs
loop. Instead it used a custom iterator and a table holding the key to
delay the visit of the key.

local state = {k = nil}

local iterator = function(t)
     local k, v = next(t, state.k)
     state.k = k
     if k ~= nil then
         t[k] = nil
     end
     return v
end

local t = {}
t["no" .. "ref1"] = 1
t["no" .. "ref2"] = 2

for v in iterator, t do
     print(v)
     collectgarbage("collect")
end

However, I didn't like this contrived example so I searched for other
ways to delay the traversel of the stack. Since coroutines also have a
stack they can be used to delay the marking of the key.

Regards,
Xmilia
Reply | Threaded
Open this post in threaded view
|

Re: Garbage Collection Breaks Next

Roberto Ierusalimschy
> However, I didn't like this contrived example so I searched for other ways
> to delay the traversel of the stack. Since coroutines also have a stack they
> can be used to delay the marking of the key.

That was clever :-)

-- Roberto
Reply | Threaded
Open this post in threaded view
|

Re: Garbage Collection Breaks Next

Xmilia Hermit
Seems like globals are traversed first, so using a global table this
problem can happen in the main thread.

t = {}
t["no" .. "ref1"] = 1
t["no" .. "ref2"] = 2

for k, v in pairs(t) do
     t[k] = nil
     print(k, v)
     collectgarbage("collect")
end

Regards,
Xmilia
Reply | Threaded
Open this post in threaded view
|

Re: Garbage Collection Breaks Next

Roberto Ierusalimschy
> Seems like globals are traversed first, so using a global table this problem
> can happen in the main thread.
>
> t = {}
> t["no" .. "ref1"] = 1
> t["no" .. "ref2"] = 2
>
> for k, v in pairs(t) do
>     t[k] = nil
>     print(k, v)
>     collectgarbage("collect")
> end

The coroutine-based version seems more stable. This example does not
seem to work (that is, does not "not work" :-) when inserted inside a
larger test file, with many other globals. I guess it depends on the
order that items are visited in the global table. Inside threads (using
local variables), the order is more predictable.

-- Roberto