Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[SR-5633] isKnownUniquelyReferenced(_:) should optionally consider weak/unowned references #48203

Open
lorentey opened this issue Aug 5, 2017 · 10 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. runtime The Swift Runtime standard library Area: Standard library umbrella

Comments

@lorentey
Copy link
Member

lorentey commented Aug 5, 2017

Previous ID SR-5633
Radar None
Original Reporter @lorentey
Type Bug
Environment

Apple Swift version 4.0 (swiftlang-900.0.54.11 clang-900.0.31)

Apple Swift version 4.0-dev (LLVM b5c7bf32a9, Clang 42fb83c55f, Swift 2e5817e)

Swift version 4.0-dev (LLVM 98499e0a26, Clang 337d432629, Swift cfb2a87)

Additional Detail from JIRA
Votes 0
Component/s Standard Library
Labels Bug, Runtime
Assignee None
Priority Medium

md5: 3577d4724b9c773e5b7535af4a2c2326

is duplicated by:

  • SR-8538 runtime: isKnownUniquelyReferenced should return false if there's any weak/unowned refs (or offer new function with those semantics)

Issue Description:

In Swift 4, the function isKnownUniquelyReferenced‌ returns false for any object that has (or previously had) a weak reference:

class Foo {}
var foo = Foo()
print(isKnownUniquelyReferenced(&foo)   // => true  (OK)
weak var bar: Foo? = foo
print(isKnownUniquelyReferenced(&foo)   // => false (Not OK)
bar = nil
print(isKnownUniquelyReferenced(&foo)   // => false (Extremely not OK)

This is a regression from Swift 3.1, where all three print statements printed true.

IsKnownUniquelyReferenced is documented to only count strong references; but even if for some reason it was changed to also count weak references, it should still report true in the third case, where the object only has a single outstanding reference left.

(That being said, a useful coding technique for COW-enabled tree collection types depends on the uniqueness checks ignoring weak/unowned refs, so ideally the Swift 3 behavior should stay.)

@lorentey
Copy link
Member Author

lorentey commented Aug 5, 2017

I submitted a possible fix in PR #11362.

@gparker42
Copy link
Mannequin

gparker42 mannequin commented Aug 16, 2017

Weak and unowned references can break algorithms depending on precisely what guarantees they need from uniquely-referenced. I expect something to change here in the future.

(For example, if your algorithm is "it's uniquely referenced therefore no other threads can interfere" then weak and unowned references can break your assumptions. Another thread can read a weak or unowned reference behind your back after the uniquely-referenced check.)

But this is fine for now.

@lorentey
Copy link
Member Author

In the tree-based CoW collection use case I have in mind, storage references aren't visible outside the collection implementation, so the use of weak/unowned references is strictly controlled. I use them in the representation of indices to speed up operations. (E.g., in red-black trees, storing a path of node references inside the index leads to an algorithmic improvement to index(after🙂. The path itself can use unowned(unsafe) references, but for index validation, I also need to include an unowned or weak reference to the root node, along with a mutation counter.)

Indices are special because their use generally† requires the running thread to already have a (strong) copy of the corresponding collection on hand – so a standalone weak ref stored in an index won't get read on its own, unless the weak root node ref in an index supplied to a collection method belongs to a completely different collection instance (in which case the index is invalid, and the resulting trap will nicely prevent any data race). The weak/unowned references in an index are used to speed up operations on a separate strong reference that the thread already has; they aren't used to create new strong references out of thin air.

† There are two exceptions: indices need to implement Comparable, and in the == and < operators, two indices need to be compared without the help of the collection. I've sometimes implemented this by reading their weak root references, which indeed leads to races if the (unique) collection is also being mutated by its separate owner thread. (Thanks for pointing this out!) Thankfully, this is solvable by loosening index validation in this case, and comparing offsets or some other direct value instead.

Obviously, all this is really subtle and fragile, perhaps even in the context of CoW implementations. However, the current behavior meshes really nicely with the collection model to allow this narrow use case to work, and it gives us considerable performance benefits for certain useful types of collections. If isUnique counted weak/unowned references, I think I'd need to use double indirection to save the technique. I don't yet know the performance impact of that, but I should probably look into it.

@gparker42
Copy link
Mannequin

gparker42 mannequin commented Aug 17, 2017

"Not visible outside the implementation" also applies to the stdlib's current uses such as the Array implementation. We'll definitely preserve this capability somewhere. Perhaps we'll deprecate the current function and add new functions that are more explicit about which references they're checking.

@lorentey
Copy link
Member Author

That sounds like an excellent change! 👍

@atrick
Copy link
Member

atrick commented Aug 15, 2018

Perhaps we'll deprecate the current function and add new functions that are more explicit about which references they're checking.

Good idea.

@gparker42 and @lorentey, this issue came up again with @weissi's realloc work. Should we have a runtime/stdlib radar for this and do something more sensible before the API is baked in?

@gparker42
Copy link
Mannequin

gparker42 mannequin commented Aug 15, 2018

We can repurpose <rdar://problem/27070378> Race: isUniquelyReferenced doesn't consider the weak refcount

@ole
Copy link
Contributor

ole commented Jul 22, 2020

I arrived here via a link posted by @belkadan in a forum thread.

For what it's worth, I can't reproduce the behavior in the ticket description anymore. In Swift 5.2 and a current 5.3 beta (on macOS, tested with and without -O), all 3 print statements print "true":

class Foo {}
var foo = Foo()
print(isKnownUniquelyReferenced(&foo))   // => true
weak var bar: Foo? = foo
print(isKnownUniquelyReferenced(&foo))   // => true
bar = nil
print(isKnownUniquelyReferenced(&foo))   // => true

Whether that means the ticket should be closed, I don't know.

@lorentey
Copy link
Member Author

The original issue was resolved in one of the Swift 4 releases! However, this item has pivoted into tracking the addition of new API that allows selecting the desired behavior, and we haven't done that yet.

Detecting outstanding unowned references may not be feasible to implement at this point, but I believe weak references are still detectable.

@ole
Copy link
Contributor

ole commented Jul 23, 2020

@lorentey OK, thanks.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. runtime The Swift Runtime standard library Area: Standard library umbrella
Projects
None yet
Development

No branches or pull requests

3 participants