This code isn't short, but can someone help me spot the bug/problem (D1, DMD)? I have tried to write clean & short code, to help spotting problems.

It produces an (no error line given):
Error: overlapping array copy

It's just a stack data structure (here for simplicity just for items of type int), made with a single linked list of blocks that become geometrically bigger.


import std.gc: malloc, hasNoPointers;

int min(int a, int b) {
    return a <= b ? a : b;
}


class IntStack {
    struct Block {
        int len;
        Block* next;
        int* data;
    }

    Block* list_head, list_tail;
    int total_len;
    int used_last_block; // how many items are used in the last (tail) block


    this() {
        this.list_head = block_alloc(4);
        this.list_tail = list_head;
    }


    ubyte* mem_alloc(int nbytes) {
        auto p  = cast(ubyte*)malloc(nbytes);
        if (p is null)
            throw new Error("not enough mem");
        hasNoPointers(p);
        return p;
    }


    Block* block_alloc(int nints) {
        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;
        return new_block;
    }


    final void opCatAssign(int x) {
        if (this.used_last_block == this.list_tail.len) {
            // then last block is full and we must create a new one
            this.used_last_block = 0;
            auto new_block = block_alloc(this.list_tail.len * 2);

            // append to the linked list
            this.list_tail.next = new_block;
            this.list_tail = new_block;
        }

        this.list_tail.data[this.used_last_block] = x;
        this.used_last_block++;
        this.total_len++;
    }


    int[] toarray() {
        if (!this.total_len)
            return null;

        int* result_ptr = cast(int*)mem_alloc(this.total_len * int.sizeof);
        int[] result = result_ptr[0 .. this.total_len];

        Block* aux_ptr = this.list_head;
        int pos;

        // Here: Error: overlapping array copy
        while (aux_ptr != null) {
            // in the last block copy only up to the total_len
            int ncopy = min(aux_ptr.len, this.total_len - pos);

            result[pos .. pos + ncopy] = aux_ptr.data[0 .. ncopy];
            pos += ncopy;
            aux_ptr = aux_ptr.next;
        }

        return result;
    }
}


void main() {
    auto st = new IntStack();

    for (int i; i < 70_000; i++)
        st ~= i;

    auto aux = st.toarray;
    aux = st.toarray;
}



---------------------

Note: in that code I haven't used variable-length structs, like the following idiom sometimes used in C, because it gives array bounds errors:


struct Block {
    int len;
    Block* next;
    int[1] data;
}
...
auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) * int.sizeof);


I presume that can't be done in D (I don't want to write code that works only in release mode).

Bye and thank you,
bearophile

I don't known what the error comes from in your code but I do know that it is a result of trying to copy from one slice to another that overlap. Someone has a copy function that works in this cases (look at cashew)

On Sat, 06 Sep 2008 21:17:31 +0400, BCS <ao@pathlink.com> wrote:

> I don't known what the error comes from in your code but I do know that it is a result of trying to copy from one slice to another that overlap. Someone has a copy function that works in this cases (look at cashew)
>
>

Not necessarily. I once wrote a code that was passing and returning some arrays, but never copying them. In some cases I was getting some weird array overlapping exception that disappeared after small refactoring. I am 100% sure it was a DMD bug.

On Sat, 06 Sep 2008 05:12:56 +0400, bearophile <bearophileHUGS@lycos.com> wrote:

> This code isn't short, but can someone help me spot the bug/problem (D1, DMD)?
> I have tried to write clean & short code, to help spotting problems.
>
> It produces an (no error line given):
> Error: overlapping array copy
>
> It's just a stack data structure (here for simplicity just for items of type int), made with a single linked list of blocks that become geometrically bigger.
>
>
> import std.gc: malloc, hasNoPointers;
>
> int min(int a, int b) {
>     return a <= b ? a : b;
> }
>
>
> class IntStack {
>     struct Block {
>         int len;
>         Block* next;
>         int* data;
>     }
>
>     Block* list_head, list_tail;
>     int total_len;
>     int used_last_block; // how many items are used in the last (tail) block
>
>
>     this() {
>         this.list_head = block_alloc(4);
>         this.list_tail = list_head;
>     }
>
>
>     ubyte* mem_alloc(int nbytes) {
>         auto p  = cast(ubyte*)malloc(nbytes);
>         if (p is null)
>             throw new Error("not enough mem");
>         hasNoPointers(p);
>         return p;
>     }
>
>
>     Block* block_alloc(int nints) {
>         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;
>         return new_block;
>     }
>
>
>     final void opCatAssign(int x) {
>         if (this.used_last_block == this.list_tail.len) {
>             // then last block is full and we must create a new one
>             this.used_last_block = 0;
>             auto new_block = block_alloc(this.list_tail.len * 2);
>
>             // append to the linked list
>             this.list_tail.next = new_block;
>             this.list_tail = new_block;
>         }
>
>         this.list_tail.data[this.used_last_block] = x;
>         this.used_last_block++;
>         this.total_len++;
>     }
>
>
>     int[] toarray() {
>         if (!this.total_len)
>             return null;
>
>         int* result_ptr = cast(int*)mem_alloc(this.total_len * int.sizeof);
>         int[] result = result_ptr[0 .. this.total_len];
>
>         Block* aux_ptr = this.list_head;
>         int pos;
>
>         // Here: Error: overlapping array copy
>         while (aux_ptr != null) {
>             // in the last block copy only up to the total_len
>             int ncopy = min(aux_ptr.len, this.total_len - pos);
>            result[pos .. pos + ncopy] = aux_ptr.data[0 .. ncopy];
>             pos += ncopy;
>             aux_ptr = aux_ptr.next;
>         }
>
>         return result;
>     }
> }
>
>
> void main() {
>     auto st = new IntStack();
>
>     for (int i; i < 70_000; i++)
>         st ~= i;
>
>     auto aux = st.toarray;
>     aux = st.toarray;
> }
>
>
>
> ---------------------
>
> Note: in that code I haven't used variable-length structs, like the following idiom sometimes used in C, because it gives array bounds errors:
>
>
> struct Block {
>     int len;
>     Block* next;
>     int[1] data;
> }
> ...
> auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) * int.sizeof);
>
>
> I presume that can't be done in D (I don't want to write code that works only in release mode).
>
> Bye and thank you,
> bearophile

Just started digging your case. This behaviour is 100% repeatable with DMD1.028 but never takes place with DMD1.029+ (Windows).

On Sat, 06 Sep 2008 23:09:56 +0400, Denis Koroskin <2korden@gmail.com> wrote:

> On Sat, 06 Sep 2008 05:12:56 +0400, bearophile <bearophileHUGS@lycos.com> wrote:
>
>> This code isn't short, but can someone help me spot the bug/problem (D1, DMD)?
>> I have tried to write clean & short code, to help spotting problems.
>>
>> It produces an (no error line given):
>> Error: overlapping array copy
>>
>> It's just a stack data structure (here for simplicity just for items of type int), made with a single linked list of blocks that become geometrically bigger.
>>
>>
>> import std.gc: malloc, hasNoPointers;
>>
>> int min(int a, int b) {
>>     return a <= b ? a : b;
>> }
>>
>>
>> class IntStack {
>>     struct Block {
>>         int len;
>>         Block* next;
>>         int* data;
>>     }
>>
>>     Block* list_head, list_tail;
>>     int total_len;
>>     int used_last_block; // how many items are used in the last (tail) block
>>
>>
>>     this() {
>>         this.list_head = block_alloc(4);
>>         this.list_tail = list_head;
>>     }
>>
>>
>>     ubyte* mem_alloc(int nbytes) {
>>         auto p  = cast(ubyte*)malloc(nbytes);
>>         if (p is null)
>>             throw new Error("not enough mem");
>>         hasNoPointers(p);
>>         return p;
>>     }
>>
>>
>>     Block* block_alloc(int nints) {
>>         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;
>>         return new_block;
>>     }
>>
>>
>>     final void opCatAssign(int x) {
>>         if (this.used_last_block == this.list_tail.len) {
>>             // then last block is full and we must create a new one
>>             this.used_last_block = 0;
>>             auto new_block = block_alloc(this.list_tail.len * 2);
>>
>>             // append to the linked list
>>             this.list_tail.next = new_block;
>>             this.list_tail = new_block;
>>         }
>>
>>         this.list_tail.data[this.used_last_block] = x;
>>         this.used_last_block++;
>>         this.total_len++;
>>     }
>>
>>
>>     int[] toarray() {
>>         if (!this.total_len)
>>             return null;
>>
>>         int* result_ptr = cast(int*)mem_alloc(this.total_len * int.sizeof);
>>         int[] result = result_ptr[0 .. this.total_len];
>>
>>         Block* aux_ptr = this.list_head;
>>         int pos;
>>
>>         // Here: Error: overlapping array copy
>>         while (aux_ptr != null) {
>>             // in the last block copy only up to the total_len
>>             int ncopy = min(aux_ptr.len, this.total_len - pos);
>>            result[pos .. pos + ncopy] = aux_ptr.data[0 .. ncopy];
>>             pos += ncopy;
>>             aux_ptr = aux_ptr.next;
>>         }
>>
>>         return result;
>>     }
>> }
>>
>>
>> void main() {
>>     auto st = new IntStack();
>>
>>     for (int i; i < 70_000; i++)
>>         st ~= i;
>>
>>     auto aux = st.toarray;
>>     aux = st.toarray;
>> }
>>
>>
>>
>> ---------------------
>>
>> Note: in that code I haven't used variable-length structs, like the following idiom sometimes used in C, because it gives array bounds errors:
>>
>>
>> struct Block {
>>     int len;
>>     Block* next;
>>     int[1] data;
>> }
>> ...
>> auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) * int.sizeof);
>>
>>
>> I presume that can't be done in D (I don't want to write code that works only in release mode).
>>
>> Bye and thank you,
>> bearophile
>
> Just started digging your case. This behaviour is 100% repeatable with DMD1.028 but never takes place with DMD1.029+ (Windows).

WTF? Changing nearly *anything* (like, decreasing loop counf from 70_000 to 65_000, putting logging of any kind or commenting out almost any line) makes problem disappear.

I think you should put the whole test program into bugzilla for Walter play with. Even though it *looks like* problem is gone in 1.029+ it might just be hidden and may arise under different circumstances.

bearophile wrote:

>             this.list_tail.next = new_block;
>             this.list_tail = new_block;
> 

What are you doing here?

-manfred

-- 
If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)

Manfred_Nowak Wrote:
> >             this.list_tail.next = new_block;
> >             this.list_tail = new_block;
> > 
> What are you doing here?

Let's see. This is a singly linked list, the list header that is the pointer to the oldest allocated block is (this doesn't change often):
this.list_head
The last block of the linked list is pointed by:
this.list_tail
Each block has a "next" pointer.

When the user wants to add an item to the data structure and the last block is full, I have to allocate a new block, that is pointed by:
new_block

So I allocate:
new_block = GC_malloc ...

Then I set the 'next' pointer of the last block of the list (that was null) to point the new block: this.list_tail.next = new_block;

Then I move the tail pointer to point to the newly allocate block:
this.list_tail = new_block;
So now the tail pointer correctly points to the last block.

Now I can reset to zero the number of the items in the last block: this.used_last_block = 0;

Then I can copy the new item in the correct position, that is 0 if the block is newly allocated: this.list_tail.data[this.used_last_block] = x;

Then I increment the number of items used in the last block, so next time I'll insert in the second space: this.used_last_block++;

Then I increment the total length of the data structure, to remember how much long it is: this.total_len++;

So that code looks correct to me.

Bye,
bearophile

bearophile wrote:
> > this.list_tail.next = new_block;
> So that code looks correct to me.

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 can see this by introducing a simple printout:
|   int ncopy = min(aux_ptr.len, this.total_len - pos);
|   writefln( ncopy);

which will printout the lines
|   4
|   69996
|   0
|   .....
for the second run of `st.toarray'.

-manfred
-- 
If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)

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


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


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

Bye and thank you,
bearophile

On Sun, Sep 7, 2008 at 7:48 AM, bearophile <bearophileHUGS@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;
	}
}