Re: object addresses in Lua

["Robert G. Jakabosky" <bobby@...>]

On Thursday 02, Xingzhi Pan wrote:
> 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

Yes there will be pointers to GC objects on the call stacks.

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

You can look at the current GC code to see how it walks the Lua stacks, global 
table & registry to mark all live references.

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


-- 
Robert G. Jakabosky