Potential bug (EXC_BAD_ACCESS) on dealloc after returning from function?

Hi all,

Context:

I am using Swift for the 2020 Advent of Code, specifically Day 23 (Day 23 - Advent of Code 2020). So, if you're participating and haven't finished this yet, there are spoilers.

Explanation:

I have a linked list -esque Node structure, with a value and a next pointer.

class Node<T> {
	public let value: T
	public var next: Node<T>?
	init(_ val: T, _ n: Node<T>?) {
		value = val
		next = n
	}
}

In one function call I do two things:

  1. Construct a Map of the value to the Node<Int> with 1 million values
  2. Construct a linked list of those 1 million values

I finally return two values from the linked list in the function as an [Int]. However, there is a short delay (when debugging in debug mode in Xcode), before I get an EXC_BAD_ACCESS.

The following are screenshots of the exception in action:

It looks like it's coming from the Node<Int> implicit deinit function.

The solution to this for me was to manually set the .next to nil for all of the values (lines 488-490 in the first screenshot). When doing this, the return is instantaneous and has no exception.

I'm on Xcode 12.3 on Big Sur, with Swift 5.3.2.

Conclusion:

First, I find it hilarious that I (potentially) found a bug in Swift through an Advent of Code problem. If I'm right, then I hope you all can have a good laugh too!

Second, what does everyone think? With the only change being to uncomment those lines to remove the problem, it seems like this might be a problem. Unless I'm missing something fundamental about how to use Swift. I'm guessing that ARC doesn't like 1-million-deep linked lists, perhaps?

If this is a bug, should I post it anywhere besides this forum?

I'm sure there's a way to reproduce it without all of my code. It will take ~30s to run in debug mode or ~9s in release mode to get to the point where the error occurs. As compiler bugs can be tricky, I didn't want to change anything and lose the error.

Links:

What you’re seeing here is a stack overflow. When your first node is deallocated, it decreases the reference count of the second node. Then that second node gets deallocated which decreases the ref count for the third, which does the same to the 4th, …, 1 millionth node.

This is all happening within one super large call stack which will for 1M nodes very likely blow through your stack. When it does that, the program crashes. You can see the number 232,845 in Xcode’s stack view (which hides some “internal” frames) and that number is the number of the stack frame. So you got to about a quarter of a million stack frames until you hit the end of the stack.

One of the buttons at the very bottom of Xcode’s stack view allows you to un-hide internal stack frames.

2 Likes

This looks like SR-5145: Letting a long linked list go out of scope can cause a stack-overflow with ARC.

Thanks for the information, @johannesweiss! That all makes a lot of sense, with the stack.

@ole, that looks exactly like it! This definitely seems like expected behavior.

If I knew about unhiding internal stack frames, then I definitely would have thought about the ref decrease chain. This is good to know knowledge.

Thanks, all!