Bug 16824 – std.experimental.allocator.dispose leaks memory for arrays of more than 1 dimension
Status
RESOLVED
Resolution
FIXED
Severity
normal
Priority
P1
Component
phobos
Product
D
Version
D2
Platform
x86_64
OS
Windows
Creation time
2016-11-28T21:53:00Z
Last change time
2017-03-22T12:21:40Z
Assigned to
razvan.nitu1305
Creator
atila.neves
Comments
Comment #0 by atila.neves — 2016-11-28T21:53:54Z
The program below throws an AssertError due to memory leaks when calling dispose with a 2D array. dispose works fine with a 1D array. The issue is there for all N-D arrays where N > 1 (it's easy to get a 3D one with string[][]). A simple fix is to check in the dispose for arrays whether or not the elements are also arrays and recurse.
The output for the program:
+ Allocated ptr 544880 of 16 bytes length
+ Allocated ptr 544640 of 24 bytes length
+ Allocated ptr 544EA0 of 24 bytes length
- Deallocate ptr 544880 of 16 bytes length
[email protected](42): Memory leak in TestAllocator. Allocations: [ByteRange(544640, 24), ByteRange(544EA0, 24)]
----------------
0x0040A501 in _d_assert_msg
0x00402388 in _Dmain at C:\Users\Atila\coding\d\experiments\allocator.d(55)
0x0040B337 in D2rt6dmain211_d_run_mainUiPPaPUAAaZiZ6runAllMFZ9__lambda1MFZv
0x0040B2FB in void rt.dmain2._d_run_main(int, char**, extern (C) int function(char[][])*).runAll()
0x0040B1FC in _d_run_main
0x00409F28 in main at C:\Users\Atila\coding\d\experiments\allocator.d(7)
0x0042804D in mainCRTStartup
0x75C838F4 in BaseThreadInitThunk
0x76F75DE3 in RtlUnicodeStringToInteger
0x76F75DAE in RtlUnicodeStringToInteger
The program:
import std.stdio;
struct TestAllocator {
import std.experimental.allocator.common: platformAlignment;
import std.experimental.allocator.mallocator: Mallocator;
alias allocator = Mallocator.instance;
private static struct ByteRange {
void* ptr;
size_t length;
}
private ByteRange[] _allocations;
enum uint alignment = platformAlignment;
void[] allocate(size_t numBytes) {
auto ret = allocator.allocate(numBytes);
writeln("+ Allocated ptr ", ret.ptr, " of ", ret.length, " bytes length");
_allocations ~= ByteRange(ret.ptr, ret.length);
return ret;
}
bool deallocate(void[] bytes) {
import std.algorithm: remove, canFind;
import std.conv: text;
writeln("- Deallocate ptr ", bytes.ptr, " of ", bytes.length, " bytes length");
bool pred(ByteRange other) { return other.ptr == bytes.ptr && other.length == bytes.length; }
assert(_allocations.canFind!pred,
text("Unknown deallocate byte range. Ptr: ", bytes.ptr, " length: ", bytes.length,
" allocations: ", _allocations));
_allocations = _allocations.remove!pred;
return allocator.deallocate(bytes);
}
~this() {
import std.conv: text;
assert(!_allocations.length, text("Memory leak in TestAllocator. Allocations: ", _allocations));
}
}
void main() {
import std.experimental.allocator: dispose, makeArray;
TestAllocator allocator;
auto ints2d = allocator.makeArray!(int[])(2);
foreach(ref ints1d; ints2d)
ints1d = allocator.makeArray!(int)(3);
allocator.dispose(ints2d);
}
Comment #1 by andrei — 2016-12-22T01:22:45Z
OK, so what we have here at the core is this:
auto ints2d = allocator.makeArray!(int[])(2);
foreach(ref ints1d; ints2d)
ints1d = allocator.makeArray!(int)(3);
What I see here by means of manual coding:
* Create an array of int[] using an allocator
* Create a bunch of arrays of int using the same allocator
This is again by means of manual coding. The individual arrays might have been created using a different allocator, or sliced from a larger buffer.
I don't think we should expect the top-level allocator to "know" (assume really) that everything was allocated with the same allocator.
Comment #2 by razvan.nitu1305 — 2016-12-22T12:41:01Z
(In reply to Andrei Alexandrescu from comment #1)
> OK, so what we have here at the core is this:
>
> auto ints2d = allocator.makeArray!(int[])(2);
> foreach(ref ints1d; ints2d)
> ints1d = allocator.makeArray!(int)(3);
>
> What I see here by means of manual coding:
>
> * Create an array of int[] using an allocator
> * Create a bunch of arrays of int using the same allocator
>
> This is again by means of manual coding. The individual arrays might have
> been created using a different allocator, or sliced from a larger buffer.
>
> I don't think we should expect the top-level allocator to "know" (assume
> really) that everything was allocated with the same allocator.
Thing would be great if we could test to see if the inner arrays were allocated
using the same allocator. If that is the case, then we can free the initial array
entirely, otherwise it's the user's job to do that. Unfortunately, I do not know
at this point if such a test is possible, but I will investigate further.
Comment #3 by andrei — 2016-12-22T13:29:40Z
The owns() method allows allocators to figure that out, but returns true for internal pointers as well, which means the following would not end well:
auto ints2d = allocator.makeArray!(int[])(2);
auto bulk = allocator.makeArray!(int[])(ints2d.length * 100);
foreach(i; 0 .. ints2d.length)
ints2s[i] = bulk[i * 100 .. (i + 1) * 100];
which is a customary way to save on allocations in multidimensional arrays.
@Atila, any good argument on how we can make this work? If not, I think we should close as invalid.
Comment #4 by andrei — 2016-12-22T13:30:32Z
(In reply to Andrei Alexandrescu from comment #3)
> The owns() method allows allocators to figure that out, but returns true for
> internal pointers as well, which means the following would not end well:
>
> auto ints2d = allocator.makeArray!(int[])(2);
> auto bulk = allocator.makeArray!(int[])(ints2d.length * 100);
> foreach(i; 0 .. ints2d.length)
> ints2s[i] = bulk[i * 100 .. (i + 1) * 100];
>
> which is a customary way to save on allocations in multidimensional arrays.
>
> @Atila, any good argument on how we can make this work? If not, I think we
> should close as invalid.
Corrected code:
auto ints2d = allocator.makeArray!(int[])(2);
auto bulk = allocator.makeArray!int(ints2d.length * 100);
foreach(i; 0 .. ints2d.length)
ints2s[i] = bulk[i * 100 .. (i + 1) * 100];
Comment #5 by atila.neves — 2016-12-23T11:03:12Z
I understand the arguments; but I still think there should be an easy, canonical way of allocating arrays of more than one dimension and be able to dispose of them without leaking memory. I didn't even know I _was_ leaking memory until I wrote that test allocator. And I only did _that_ because I'm paranoid.
Comment #6 by andrei — 2016-12-23T16:54:39Z
(In reply to Atila Neves from comment #5)
> I understand the arguments; but I still think there should be an easy,
> canonical way of allocating arrays of more than one dimension and be able to
> dispose of them without leaking memory. I didn't even know I _was_ leaking
> memory until I wrote that test allocator. And I only did _that_ because I'm
> paranoid.
It seems the right view is this:
* If you used a loop to allocate your multidimensional array, you're supposed to use a loop to deallocate your multidimensional array. The library can't guess what you did.
* If the library provides a means to dispose a multidimensional array in one shot under certain assumptions, the library must provide a means to create a multidimensional array in one shot such that those assumptions are fulfilled.
One way I see this moving forward is to provide the following functions:
* makeMultidimensional -> does the looparoo that Atila currently does by hand
* disposeMultidimensional -> does what Razvan does now in his PR, i.e. disposes the whole array ASSUMING it had been created by makeMultidimensional
(maybe later)
* makeCompactMultidimensional -> computes the appopriate sizes and allocates one hunk that is then sliced and diced to return the multidimensional array.
* disposeCompactMultidimensional -> disposes an array ASSUMING it had been created by makeCompactMultidimensional
Comment #7 by atila.neves — 2016-12-23T17:10:41Z
I think adding the extra functions is the way forward.
Comment #8 by andrei — 2016-12-23T17:16:36Z
worksforme
Atila you just volunteered to help @Razvan our grad student in case he needs assistance and review with *CompactMultidimensional, which may have subtleties related to alignment.