Re: object addresses in Lua

[Xingzhi Pan <vengeance.storm@...>]

Okay I've refreshed my memory about hashing and I got your points now.  Thanks.

So back to my original question about GC moving objects.  Besides
pointers used in hash tables, I‘m also concerned about pointers inside
the frames of the call stack.  That is, there can be an unknown number
of pointers inside current activation records that also need to be
replaced.  So when the moving GC runs, it has to somehow scan the call
stack and detect then replace those pointers.

Am I correct or I'm missing something?  If I'm right, I'm still vague
about how to scan the stack in some way.

Thanks again.

Harry

On Tue, May 31, 2011 at 1:32 AM, Robert G. Jakabosky
<bobby@sharedrealm.com> wrote:
> On Monday 30, Xingzhi Pan wrote:
>> Thanks for the detailed reply.  I have further questions inlined below.
>>
>> On Fri, May 27, 2011 at 11:44 AM, Robert G. Jakabosky
>>
>> <bobby@sharedrealm.com> wrote:
>> > On Thursday 26, Xingzhi Pan wrote:
>> >> Hi,
>> >>
>> >> We all know that tables, functions, threads, and (full) userdata are
>> >> objects in Lua.  I'm wondering how the addresses of such objects are
>> >> treated in the Lua runtime system.  In particular, I want to know how
>> >> hard it is (or possible at all) to modify the Lua VM so that these
>> >> addresses can change at runtime without breaking the execution of the
>> >> running Lua program.
>> >
>> > The pointer for some Lua values
>> > (lightuserdata,userdata,table,function,thread) are used in the hash
>> > value when they are used as keys in a table.  Either you will have to
>> > change how those values are hashed, or you will have to re-hash all
>> > values that you move.
>>
>> I don't quite understand "The pointer...are used in the hash value
>> when they are used as keys in a table”.  So you're saying for example
>> when a function is used as a key in a table, its pointer is used "in
>> the hash value"?  What does "in the hash value" mean here?
>
> "in the hash value" should have been "as the hash value".  Basically I was
> saying that the pointer is used to create the semi-unique hash value for
> complex Lua objects.  For string keys a hash function is used to convert the
> string's contents to a semi-unique hash value.
>
>> I suppose
>> this function, as a key, can be used to retrieve a value (e.g., a
>> string) from the table.  According to you, how is this value connected
>> to this function's pointer?
>
> The Lua code below shows how a function value is used as a key:
> local tab = {} -- some table
> tab[print] = "some value"
> print(tab[print]) -- print value store in previous line.
>
> Lua needs to be able to lookup that key in the internal hash part of the 'tab'
> table, to do that Lua needs to be able to hash the key (convert it to a semi-
> unique number) to find the first bucket where that value might be stored.  For
> values that are not a string/number/boolean Lua uses the pointer to that value
> as the hash when doing that lookup.
>
>> > One way to handle the rehashing is to replace the old GC value with a
>> > redirect/link value, which contains a pointer to the new location.  Then
>> > during garbage collection you can re-hash all link values to the new
>> > value.  I haven't read much on compacting GCs, so there might be a
>> > better way of handling this.
>>
>> Please define "rehashing".  It seems that you're saying adding another
>> level of indirection but I'm confused.
>
> Rehashing means to find all keys in all tables that used the old pointer (the
> old hash), which will need to be removed and then re-inserted using the new
> pointer (the new hash).
>
>
>> >> The motivation behind this question is that I'm playing with Lua's
>> >> incremental mark-and-sweep garbage collector and am wondering if it's
>> >> possible to replace it with a moving collector (e.g., a copying
>> >> collector).  This is a personal project aiming at learning GC and
>> >> having fun.
>> >
>> > You might want to start by classifying each allocation as
>> > movable/non-movable. Some allocations (node arrays in tables, the
>> > internal string table) can be moved/reallocated without having to do a
>> > lot of fix-ups.
>>
>> I guess I need to read more about ltable.c to understand how objects
>> are connected together in a Lua VM instance.  But thanks to you I
>> already at least realized that they are mainly interconnected via
>> tables.  A little pointers would be appreciated.
>
> Yes, I recommend that you understand what the code in ltable.c does.
>
> Vaughan McAlley, has provided more info about how hashtables work, which you
> will need to understand before you try to understand the hashing code in
> ltable.c.
>
> --
> Robert G. Jakabosky
>
>



-- 
Pan, Xingzhi
http://www.panxingzhi.net