A bug in my code

Denis Koroskin 2korden at gmail.com
Sat Sep 6 12:23:26 PDT 2008


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

> On Sat, 06 Sep 2008 05:12:56 +0400, bearophile  
> <bearophileHUGS at 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.


More information about the Digitalmars-d-learn mailing list