Re: Lua garbage collection

[jeske@... (David Jeske)]

On Apr 13, nr@cs.virginia.edu (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)   +   jeske@igcom.net   +   http://www.igcom.net/~jeske/