Memory leak / failure to garbage collect linked list #61036
Description
It appears that a linked list implementation for ROHD (https://github.com/intel/rohd) hardware simulations is running into some sort of memory leak or failure to garbage collect removed nodes.
The original symptom was in a large hardware simulation using ROHD (a big, long-running Dart program) hitting a heap exhausted message. For example, something like this:
Exhausted heap space, trying to allocate 300080 bytes.
Exhausted heap space, trying to allocate 176 bytes.
Unhandled exception:
Out of Memory
We used the DevTools memory profiler to try to identify the source and found it was a linked-list implementation (see below). We wrote a benchmark (see below) that reproduces a memory increase over time similar to what is seen in our large program.
There appears to be some unpredictability about when the memory increase happens. For example, sometimes garbage collection seems to work fine until we hit "pause" on the debugger and resume and then it stops cleaning.
We also noticed some strange inconsistencies. For example, we see 100 instances of the DummyElement in a snapshot:
But then we also see >100k instances in the memory profile:
We're not sure what we could do to clear memory that we're not pointing to anymore, and assumed garbage collection would clean up, hence we suspect a garbage collection bug in Dart may be to blame?
Reproduced on two systems:
- Windows 11 laptop with WSL 2 Ubuntu:
Dart SDK version: 3.8.1 (stable) (None) on "linux_x64" - In an Ubuntu docker container on a server machine:
Dart SDK version: 3.5.1 (stable) (None) on "linux_x64"
The full implementation is available here:
https://github.com/intel/rohd/blob/main/lib/src/collections/iterable_removable_queue.dart
However, a simplified version of the implementation with no dependencies is pasted below:
// Copyright (C) 2023 Intel Corporation
// SPDX-License-Identifier: BSD-3-Clause
//
// iterable_removable_queue.dart
// Definition for an optimized queue for signal propagation subscriptions and
// similar applications.
//
// 2023 April 21
// Author: Max Korbel <max.korbel@intel.com>
/// A queue that can be easily iterated through and remove items during
/// iteration.
class IterableRemovableQueue<T> {
/// The first item in this queue.
///
/// Null if the queue is empty.
_IterableRemovableElement<T>? _first;
/// The last item in this queue.
///
/// Null if the queue is empty.
_IterableRemovableElement<T>? _last;
/// Adds a new item to the end of the queue.
void add(T item) {
final newElement = _IterableRemovableElement<T>(item);
if (isEmpty) {
_first = newElement;
_last = _first;
} else {
_last!.next = newElement;
_last = newElement;
}
}
/// Indicates whether there are no items in the queue.
bool get isEmpty => _first == null;
/// Iterates through all items in the queue, removing any which are indicated
/// by [removeWhere], and performing [action] on the rest.
void iterate(
{void Function(T item)? action, bool Function(T item)? removeWhere}) {
if (isEmpty) {
return;
}
var element = _first;
_IterableRemovableElement<T>? previous;
while (element != null) {
if (removeWhere != null && removeWhere(element.item)) {
previous?.next = element.next;
if (element == _first) {
_first = element.next;
} else if (element == _last) {
_last = previous;
}
} else {
if (action != null) {
action(element.item);
}
previous = element;
}
element = element.next;
}
}
}
/// One element of a [IterableRemovableQueue].
class _IterableRemovableElement<T> {
/// The item being tracked by this element.
final T item;
/// The next element in the queue.
_IterableRemovableElement<T>? next;
/// Constructs an element containing [item].
_IterableRemovableElement(this.item);
}The following benchmark code was used to help diagnose the memory issues (depends on benchmark_harness and the queue implementation):
import 'package:benchmark_harness/benchmark_harness.dart';
import 'package:rohd/src/collections/iterable_removable_queue.dart';
class DummyElement {
final Set<String> someSet = {};
int value;
DummyElement(this.value) {
for (var i = 0; i < 100; i++) {
someSet.add('item_${value}_$i');
}
}
}
class IterableRemovableQueueBenchmark extends BenchmarkBase {
IterableRemovableQueueBenchmark() : super('IterableRemovableQueue');
late final IterableRemovableQueue<DummyElement> queue;
static const numElements = 100;
static const numIterations = 10000;
@override
void setup() {
queue = IterableRemovableQueue<DummyElement>();
for (var i = 0; i < numElements; i++) {
queue.add(DummyElement(i));
}
}
@override
void run() {
for (var iter = 0; iter < numIterations; iter++) {
for (var i = 0; i < numElements; i++) {
queue
..iterate(
action: (item) => item.value + 1,
removeWhere: (item) => item.value == i,
)
..add(DummyElement(i));
}
}
}
}
void main() {
IterableRemovableQueueBenchmark().report();
}