The tree class below keeps an optional reference to a node's parent. To break a strong reference cycle, I initially made that a weak reference. Upon seeing HeapObjectSideTableEntry at the top of my time profiles, I found a 2x performance improvement turning parent into an unowned pointer (mistakenly thinking that child nodes never outlive their parents). I then encounter a crash in Expr.__deallocating_deinit which I'm trying to see if I understand correctly. The crash occurs only when building optimized, and only with unowned parent. The crash does not occur using weak parent or unowned(unsafe) parent. Note that the sample code assigned to parent, but never uses it. Questions:
- Is the mere presence of an unowned reference to an object whose strong reference count has gone to zero a bug? i.e. Is this crash expected Swift behavior?
- Does making parent unowned(unsafe) actually fix the underlying bug here or does it just turn it into a silent memory corruption that will be much harder to track down? i.e. Is it safe to have an unowned(unsafe) reference to an object whose strong reference count has gone to zero without using it?
- Is my interpretation of what is happening here correct? Does the analysis below of the strong and unowned reference count look right?
- Is something else entirely here causing the crash?
The code below starts with a tree representing the sum of two vectors: [x, 1] + [y + 2, 1].
Running it unoptimized will add the vector components to produce [x + y + 2, 1 + 1].
Running it optimized will crash with
UnownedReferenceCrash(95477,0x1000d3d40) malloc: Non-aligned pointer 0x16fdff138 being freed
Here is what I think is happening.
- Initially, y+2 has a 1 strong reference as a child of the vector, and 2 unowned references from its child nodes y and 2.
- In
addVectors,a[0].add(onRight: b[0]).flatten(),b[0]creates a 2nd strong reference to y+2 - In
add(onRight:),(shallowCopy + term)creates a temporaryExprnode x+(y+2) - That adds a 3rd strong reference to y+2, and changes its parent to point to temporary
flatten()changes the temporary to x+y+2- that releases one of y+2's strong references since the temporary now directly points to its children
- that also removed both of the unowned references to y+2 since y and 2's parents are now the temporary
replace(with:)copies the contents of the temporary into the first term of the first vector- returning from
add(onRight:)releases the strong reference to y+2 from it's term parameter - returning from
add(onRight:)releases that temporary Expr which y+2's parent still points to - when addVector's
bgoes out of scope, that release the last thing to hold a strong reference to y+2 - y+2 deinits, while still holding an unowned reference to that temporary
import Foundation
final class Expr: CustomStringConvertible, ExpressibleByStringLiteral {
unowned var parent: Expr? = nil
var op: String
var args: [Expr] = [] { didSet { setArgParents() } }
func setArgParents() { for arg in args { arg.parent = self } }
subscript(index:Int) -> Expr { args[index] }
var count: Int { args.count }
init(_ op: String, _ args: [Expr]) {
self.op = op
self.args = args
setArgParents()
}
convenience init(stringLiteral s: String) { self.init(s) }
convenience init(_ op: String, _ args:Expr...) { self.init(op, args) }
var shallowCopy: Expr { Expr(op, args) }
var description: String { args.isEmpty ? "\(op)" : "\(op)(\(args.map{$0.description}.joined(separator: ",")))" }
func addVectors() {
let a = args[0], b = args[1]
args.remove(at: 1)
for j in 0 ..< a.count {
a[j].add(onRight: b[j]).flatten()
}
if count == 1 { replace(with: args[0]) }
}
@discardableResult func replace(with expr: Expr) -> Expr {
op = expr.op
args = expr.args
return self
}
@discardableResult func add(onRight term: Expr) -> Expr {
replace(with: (shallowCopy + term).flatten())
}
@discardableResult func flatten() -> Expr {
args = args.flatMap{ $0.op == op ? $0.args : [$0] }
return self
}
}
func + (_ x: Expr, _ y: Expr) -> Expr { Expr("+", x, y) }
func test() {
let expr = Expr("vector", "X", "1") + Expr("vector", "Y" + "2", "1")
print(expr)
expr.addVectors()
print(expr)
}
test()
One last note: if we change flatten as below to explicitly set parent to nil when it creates a dangling node, then the crash goes away, which I read as evidence for y+2's weak parent reference to the temporary being the source of the crash.
@discardableResult func flatten() -> Expr {
args = args.flatMap{ expr -> [Expr] in
if expr.op == op {
expr.parent = nil
return expr.args
}
else {
return [expr]
}
}
return self
}
If I understand the implementation correctly: when the strong reference count goes to zero, the object deinit is run, but if the unowned ref count is non-zero, the memory associated with the object is left as an unowned husk until the unowned ref count goes to zero allow the memory to be freed.
Is the temporary's memory being freed while the y+2 node still has an unowned reference to it?
Might temporary have been allocated on the stack in add(onRight:)?
Here is a thread giving more context, though I think I wrote everything relevant here. https://twitter.com/RonAvitzur/status/1463576340519473159
