[starvation] avoid quadratic complexity of lock acquire sequence
[starvation] avoid quadratic complexity of lock acquire sequence

Summary:
If we acquire n nested locks we end up with n critical pairs, and for each pair the held-locks component goes up linearly, thus total space/time is O(n^2).

If the sets of held-locks are constructed with maximal sharing (intuitively, if they derive from the same set by additions) then the total space/time is O(n logn).

To do this, we must avoid constructing a new set every time we ask what the currently held locks are.  Here we maintain (care is needed in the presence of recursive locks) that set across lock acquisitons and removals.

Reviewed By: skcho

Differential Revision: D17736252

fbshipit-source-id: 0f9b292c4

jvillard/infer,facebook/infer,jvillard/infer,jvillard/infer,jvillard/infer,facebook/infer,facebook/infer,facebook/infer,facebook/infer,facebook/infer,facebook/infer,jvillard/infer,jvillard/infer,jvillard/infer