Deadlock when saving objects with circular references

[czgarrett]

I have two PFObject subclasses A and B. A has an array of pointers to B, and B has a pointer to A.

Sometimes my app will fire off two save operations for A in rapid succession, and this will result in a deadlock. Here's where the deadlock occurs when saving an instance of A that references two B instances:

On thread 1:

• A iterates through the remaining items to save in PFObject#_deepSaveAsyncChildrenOfObject:withCurrentUser:sessionToken:. Those remaining items are a collection in the order B,A,B. It encounters A in the enumeration and calls canBeSerializedAfterSaving:withCurrentUser:error
• A synchronizes on its lock in PFObject#canBeSerializedAfterSaving:withCurrentUser:error
• A enumerates through its keys, and eventually comes to its reference to B.
• In PFObject#canBeSerializedAsValue:afterSaving:error:, the object ID for B is accessed.
• B synchronizes with its lock when it access its state.
• So now we have synchronized locks on this thread in the order A,B

Meanwhile, on thread 2:

• A iterates through the remaining items to save in PFObject#_deepSaveAsyncChildrenOfObject:withCurrentUser:sessionToken:. Those remaining items are a collection in the order B,A,B. It encounters B in the enumeration and calls canBeSerializedAfterSaving:withCurrentUser:error
• B synchronizes on its lock in PFObject#canBeSerializedAfterSaving:withCurrentUser:error
• B enumerates through its keys, and eventually comes to its reference to A.
• In PFObject#canBeSerializedAsValue:afterSaving:error:, the object ID for A is accessed.
• A synchronizes with its lock when it access its state.
• So now we have synchronized locks on this thread in the order B,A

BAM! Classic deadlock
One thread has lock in the order A,B, and the other has locked in the order B,A

Two possible ideas for fixes:

1. Sort the collection of remaining objects in _deepSave...
2. Limit the synchronization scope in canBeSerializedAsValue:afterSaving:error:, perhaps by making a copy of the dictionary and then proceeding. It seems risky to be synchronizing that entire block of code there because it could be doing all kinds of recursive accesses that could result in this deadlock.

[czgarrett]

The following change fixed this issue for me:

OLD:

// Returns YES if this object can be serialized for saving.
// @param saved A set of objects that we can assume will have been saved.
// @param error The reason why it can't be serialized.
- (BOOL)canBeSerializedAfterSaving:(NSMutableArray *)saved withCurrentUser:(PFUser *)user error:(NSError **)error {
    @synchronized (lock) {
        // This method is only used for batching sets of objects for saveAll
        // and when saving children automatically. Since it's only used to
        // determine whether or not save should be called on them, it only
        // needs to examine their current values, so we use estimatedData.
        if (![[self class] canBeSerializedAsValue:_estimatedData.dictionaryRepresentation
                                      afterSaving:saved
                                            error:error]) {
            return NO;
        }

        if ([self isDataAvailableForKey:@"ACL"] &&
            [[self ACLWithoutCopying] hasUnresolvedUser] &&
            ![saved containsObject:user]) {
            if (error) {
                *error = [PFErrorUtilities errorWithCode:kPFErrorInvalidACL
                                                 message:@"User associated with ACL must be signed up."];
            }
            return NO;
        }

        return YES;
    }
}

NEW:

// Returns YES if this object can be serialized for saving.
// @param saved A set of objects that we can assume will have been saved.
// @param error The reason why it can't be serialized.
- (BOOL)canBeSerializedAfterSaving:(NSMutableArray *)saved withCurrentUser:(PFUser *)user error:(NSError **)error {
    NSDictionary *dictionaryRepresentationCopy;
    @synchronized (lock) {
        dictionaryRepresentationCopy = _estimatedData.dictionaryRepresentation; // This copies the dictionary representation
    }
    // This method is only used for batching sets of objects for saveAll
    // and when saving children automatically. Since it's only used to
    // determine whether or not save should be called on them, it only
    // needs to examine their current values, so we use estimatedData.
    if (![[self class] canBeSerializedAsValue: dictionaryRepresentationCopy
                                  afterSaving:saved
                                        error:error]) {
        return NO;
    }

    if ([self isDataAvailableForKey:@"ACL"] &&
        [[self ACLWithoutCopying] hasUnresolvedUser] &&
        ![saved containsObject:user]) {
        if (error) {
            *error = [PFErrorUtilities errorWithCode:kPFErrorInvalidACL
                                             message:@"User associated with ACL must be signed up."];
        }
        return NO;
    }

    return YES;
}

[czgarrett]

Also: I tried to follow the instructions for contributing, but when I forked the repo the master branch won't even compile. I was hoping to write a unit test and create a pull request but I'm not sure how to make that happen. I'm sure the master branch actually does compile, but the contributor instructions need more details for project newcomers to get started.

[richardjrossiii]

@czgarrett Did you do a submodule fetch? git submodule update --init --recursive. It's stated in the README under steps for 'compiling the SDK yourself'.

[richardjrossiii]

Awesome find! There's a ton of 'bad' code revolving around how we deal with locks in our SDK, thanks for fixing one of them.

Though I would recommend doing an explicit copy of dictionaryRepresentation - just in case it was a NSMutableDictionary at some point.

If you don't want to go through the trouble of creating a PR yourself, I can create a PR and credit you with the fix if you'd like. Otherwise, I'll assume you're working on a PR, and am looking forward to reviewing it shortly!

Also, related discussion from the past: #11

[czgarrett]

Sure I'll do a PR. I'd like to figure out the process because I have other ideas for enhancements as well.

Chris

On May 9, 2016, at 4:44 PM, Richard Ross [email protected] wrote:

Awesome find! There's a ton of 'bad' code revolving around how we deal with locks in our SDK, thanks for fixing one of them.

If you don't want to go through the trouble of creating a PR yourself, I can create a PR and credit you with the fix if you'd like. Otherwise, I'll assume you're working on a PR, and am looking forward to reviewing it shortly!

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub

[nlutsenko]

Let me or @richardjrossiii know if you need help with it.
Should be pretty straightforward and for this change not even required to write tests ;)

[mbrauwers]

Hi guys, thanks for your hard work
I'm also experiencing some deadlocks, specially on isDataAvailable.

Do you have an idea when this potential fix will be committed to the master branch?

Thanks

[czgarrett]

PR created. Let me know if I did it right - this is my first time doing a PR for a forked repo.

[gateway]

Any updates on this?

[ranhsd]

Hi, any update on this issue? I am using the latest version and i still experience this issue.

[czgarrett]

I submitted a PR last July and it was never approved. Due to this and other issues, and a general lack of progress on this SDK, I finally gave up using the local data store and wrote my own sync engine using core data. While it was a pretty large effort, it did pay off because I have a lot more control over how sync works in my app.

[flovilmart]

@czgarrett what PR was it?

[czgarrett]

This one (actually turns out it was May, not July): #931

[TomWFox]

It seems this has been fixed, could it be closed? - @parse-community/ios-osx