A bug in my code

[Jarrett Billingsley]

On Sun, Sep 7, 2008 at 7:48 AM, bearophile <bearophileHUGS at lycos.com> wrote:
> Manfred_Nowak:
>> Sorrily it might be correct only at the surface. In the deeper grounds
>> your coding might be lead by some wrong assumptions on the semantics of
>> the interface to the GC.
>> You are setting the attribute of `hasNoPointers' for each and every
>> memory block you `malloc'. But this is not true, because with the
>> assignment above you are introducing a pointer into that area, without
>> calling `hasPointers'.
>> This means that on the nextrun of `FullCollect' close to no elements of
>> the list are referenced anymore: they all get collected, except `head'
>> and `tail' ofcourse.
>
> You are right, that's the bug, thank you very much. I am used with languages where you have no GC, and you do everything by yourself, and high-level languages with GC where the GC works by itself. In the D code like that you have to interact with the GC a bit more closely :-)
> If not already present somewhere, I think D newbies will enjoy a small tutorial on such GC usage.
>
> This is the line of code that creates a new Block, it calls hasNoPointers() internally:
> auto new_block = cast(Block*)mem_alloc(Block.sizeof);
>
> The best way to solve the bug is to allocate that struct normally:
> auto new_block = new Block;
> So the GC knows where the GC pointers are.
> (Later I have realized that for this problem an even better solution is to not use a linked list at all, and append the block structs into a growing dynamic array, where the structs now have just two fields: a len and a pointer to the block data).

..Or just, you know, arrays.  Since that's exactly what they are.

>
> But I'm trying to learn to use the GC, not just to debug this little experimental program. This is an alternative solution, that works, but I don't trust/like this much because I *think* the GC may scan all the struct fields for possible pointers, even the 'len' (an integer) one (if that idea of mine is wrong then please tell me):
> auto new_block = cast(Block*)mem_alloc(Block.sizeof);
> hasPointers(new_block);

You're right, the GC will scan all the members of each block, len
included, since it's imprecise and stupid.

However there's no way around this.  You _have_ pointers in your
Blocks.  If you tell the GC otherwise, you're lying to it, and it will
misbehave.

What you _can_ do, however, is allocate your Blocks with new, and then
allocate the data they point to with malloc.  Then just set the data
blocks to hasNoPointers, and leave the Blocks as they are.

>
> So I have tried this, I have written this assuming that addRoot() adds a single pointer to the GC collected pool, but this last solution doesn't work, I don't know why:
> auto new_block = cast(Block*)mem_alloc(Block.sizeof);
> new_block.data = cast(int*)mem_alloc(nints * int.sizeof);
> new_block.len = nints;
> new_block.next = null;
> addRoot(new_block.next);
> addRoot(new_block.data);

Adding roots is certainly possible but it's not very elegant.  It
means that that object will not be collected until you remove it as a
root manually.  You can very easily end up with a memory leak that
way.

The simplest implementation, though, is to use arrays, like you
thought earlier.  You don't need to muck with the GC really at all in
this case, other than to set the allocated arrays as having no
pointers.

class IntStack
{
	int[][] data;
	int[] last_data;
	size_t total_len;
	size_t used_last_block;

	this()
	{
		last_data = block_alloc(4);
	}

	int[] block_alloc(int nints)
	{
		auto d = new int[nints];
		hasNoPointers(d.ptr);
		data ~= d;
		return d;
	}

	final void opCatAssign(int x)
	{
		if(used_last_block == last_data.length)
		{
			used_last_block = 0;
			last_data = block_alloc(last_data.length * 2);
		}

		last_data[used_last_block] = x;
		used_last_block++;
		total_len++;
	}

	int[] toarray()
	{
		if(!total_len)
			return null;
			
		auto result = new int[total_len];
		size_t pos = 0;
		
		foreach(blk; data[0 .. $ - 1])
		{
			result[pos .. pos + blk.length] = blk[];
			pos += blk.length;
		}
		
		result[pos .. pos + used_last_block] = last_data[0 .. used_last_block];
		return result;
	}
}