Lua garbage collection

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Lua garbage collection

Norman Ramsey-3
I was disappointed that the Lua SP&E paper didn't say much about Lua's 
garbage collection.  I would like to have my C code allocate objects
of type userdata that get managed by Lua's garbage collector, but from 
the documentation I can't figure out how to do that.  Is it possible?

Norman Ramsey

Reply | Threaded
Open this post in threaded view
|

Re: Lua garbage collection

Roberto Ierusalimschy
> I was disappointed that the Lua SP&E paper didn't say much about Lua's
> garbage collection.  I would like to have my C code allocate objects
> of type userdata that get managed by Lua's garbage collector, but from
> the documentation I can't figure out how to do that.  Is it possible?

Not now. Userdatas (void *) are considered values, like numbers, so they are 
not allocated and therefore not collected. This will change in the next
version (3.0; an alpha version is coming very soon). Userdata will handle
any binary data, not only pointers. They will be objects, not values, and
therefore will be collected (and there will be a "fallback" to signal this).

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Lua garbage collection

David Jeske
In reply to this post by Norman Ramsey-3
On Apr 13, [hidden email] (Norman Ramsey) wrote:
> I was disappointed that the Lua SP&E paper didn't say much about Lua's 
> garbage collection.  I would like to have my C code allocate objects
> of type userdata that get managed by Lua's garbage collector, but from 
> the documentation I can't figure out how to do that.  Is it possible?
> 
> Norman Ramsey

I was thinking about this last night, and you can do it. It requires a
little bit of trickery on the C side, but it's not too rough and you
get some other good things from doing it.

1) Use "indexed" userdata instead of just straight
   pointers. Keep a C array of the "real" userdata pointers
   and make the "Lua userdata" contain an index into this array.

2) Make the C array hold a NON-LOCKED ref to the "userdata" object.

3) periodically sweep the C array, dereferenceing each lua-ref, if any
of them don't dereference, then Lua has GCed the corresponding
userdata, and you can throw it out.

- Positive side effects:

  - Because you are storing your own userdata pointers, you can be 
    guaranteed that Lua dosn't pass in a pointer to something you
    deallocated.. (i.e. Lua just passes you an index which you 
    dereference)

  - You can type the userdata, or put whatever information you want
    with it. Combined with a userdata fallback, this could give you
    a general system for doing "frozen" userdata objects, it
    allows you to handle different "types" of userdata differently,
    and it lets you tell whether Lua passed you the right _kind_ of 
    userdata.

- Negative side effects:

  - The "sweep" step is not be terribly efficient. However, it's not
    too bad either, and you don't _have_ to do it that often because
    you'll find dead ones anytime you try to derefence their lua_Ref
    handles.

- Things to remember 

  - Every time Lua passes you some userdata, you have to look it up
    in the table.

  - Don't do any of the following: (if you want to, you have to
    come up with some system of valid "tags" for the userdata indicies)

     - don't do your own descruction of objects in the table. Remember, if
       you want to use Lua GC, let it GC for you. If you start 
       destroying your own objects in your userdata array, then Lua
       will end up holding duplicate indicies for what were supposed
       to be DIFFERENT pieces of userdata. If you let it do ALL GC
       for these objects, then you'll be guaranteed when something is
       removed from your table, Lua dosn't have an index to it anymore.

     - Don't pass Lua the userdata multiple times.  (???)

       I've been looking in the source to see if this is right. I
       don't know what Lua does for userdata pointers with GC. Does
       it consider different returned userdata with the same exact
       value "the same pointer" or "distinct pointers"?

       I would be happy if it considered it the same pointer and
       would do GC correctly based on this. However, if it dosn't
       then just follow the rule above, and you should be fine.
    

Here is an example "implementation", I am just writing this in email,
it's not compiled, so there will be mistakes. It's just included so
you can see what I'm thinking...

#define UD_REFS_INCREMENT 10
struct clua_userdata_struct {
	unsigned char filled;
	int lua_ref;
	void *real_pointer;
};

struct clua_userdata_keeper_struct {
	struct clua_userdata_struct *elements;
	int max_elements;
} clua_userdata = { NULL, 0 };

int grow_clua_userdata(struct clua_userdata_keeper_struct *keeper) {
	int newsize;
	struct clua_userdata_struct *temp;

	if (!keeper->elements) {
		// there is no array, so make one
		keeper->max_elements = UD_REFS_INCREMENT;
		keeper->elements = (struct clua_userdata_struct *)
			malloc(sizeof(struct clua_userdata_struct) *
				keeper->max_elements);
		if (!keeper->elements) {
			keeper->max_elements = 0;
			return 1; // failed
		}
	} else {
		newsize = keeper->max_elements + UD_REFS_INCREMENT;
		temp = realloc(keeper->elements, 
			sizeof(struct clua_userdata_struct) *
			newsize);
		if (!temp) {
			return 1; // realloc failed
		}
		keeper->max_elements = newsize;
		keeper->elements = temp;
	}

	return 0; // success!
}

long int findAvailableEntry(
	struct clua_userdata_keeper_struct *keeper) {
	int element_count = 0;

	while (element_count < keeper->max_elements) {
		if (!keeper->elements[element_count]->filled) {
			return element_count;
		}
		element_count++;
	}

	// there wasn't an empty one, grow it...
	if (!grow_clua_userdata(keeper)) {
		element_count = 0;
		while ((element_count < keeper->max_elements) 
			&& (keeper->elements[element_count]->filled)) {
			element_count++;
		}
		if (element_count < keeper->max_elements) {
			return (element_count); // we found one..
		} else {
			return (-1); // we didn't...
		}
	} else {
		return -1; // we can't add an entry
	}
}

int clua_pushuserdata(void *data_ptr) {
	long int temp_index = findAvailableEntry(clua_userdata);
	lua_Object lua_temp;

	if (temp_index < 0) {
		// we failed
		return -1;
	} else {
		temp->real_pointer = data_ptr;
		temp->filled = 1;
		lua_pushuserdata((void *)temp_index);
		temp->lua_ref = lua_ref(0);
		lua_temp = lua_getref(temp->lua_ref);
		lua_pushobject(lua_temp);
	}

}

void clua_sweepuserdata(struct clua_userdata_keeper_struct *keeper) {
    int index = 0;

    if (keeper->elements) {
        while (index < keeper->max_elements) {
            if (keeper->elements[index]->filled) {
                if (lua_getref(keeper->elements[index]->lua_ref) 
			== LUA_NOOBECT) {
                    keeper->elements[index]->filled = 0; // it's lost!
                }
            }
	    index++;
        }
    }
}


-- 
David Jeske (N9LCA)   +   [hidden email]   +   http://www.igcom.net/~jeske/

Reply | Threaded
Open this post in threaded view
|

Re: Lua garbage collection

Roberto Ierusalimschy
       I've been looking in the source to see if this is right. I
       don't know what Lua does for userdata pointers with GC. Does
       it consider different returned userdata with the same exact
       value "the same pointer" or "distinct pointers"?

       I would be happy if it considered it the same pointer and
       would do GC correctly based on this. However, if it dosn't
       then just follow the rule above, and you should be fine.

Then you may be happy :-) In Lua 3.0, userdatas with the same exact values
(and tags) are considered the same object, and are GC correctly. That is,
if you get a "gc" fallback for it you can be sure there are no more
instances of this value inside Lua. (Notice that, in 3.0, one can have gc
fallbacks for userdata too).

-- Roberto