Implemented new fence syncs which replaces the old sync points.

gpu/command_buffer/service/sync_point_manager.cc

Index: gpu/command_buffer/service/sync_point_manager.cc
diff --git a/gpu/command_buffer/service/sync_point_manager.cc b/gpu/command_buffer/service/sync_point_manager.cc
index 039e494de8b1d4bd5ea3df100c89ec10cb508690..b35915a5e877b5dd889d0d3004522d3faa1dd63c 100644
--- a/gpu/command_buffer/service/sync_point_manager.cc
+++ b/gpu/command_buffer/service/sync_point_manager.cc
@@ -6,44 +6,241 @@
 
 #include <climits>
 
+#include "base/bind.h"
+#include "base/containers/hash_tables.h"
+#include "base/location.h"
 #include "base/logging.h"
 #include "base/rand_util.h"
 #include "base/sequence_checker.h"
+#include "base/single_thread_task_runner.h"
 
 namespace gpu {
 
 static const int kMaxSyncBase = INT_MAX;
 
-scoped_refptr<SyncPointClientState> SyncPointClientState::Create() {
-  return new SyncPointClientState;
+namespace {
+
+void RunOnThread(scoped_refptr<base::SingleThreadTaskRunner> task_runner,
+                 const base::Closure& callback) {
+  if (task_runner->BelongsToCurrentThread()) {
+    callback.Run();
+  } else {
+    task_runner->PostTask(FROM_HERE, callback);
+  }
+}
+
+}  // namespace
+
+scoped_refptr<SyncPointOrderData> SyncPointOrderData::Create() {
+  return new SyncPointOrderData;
 }
 
-uint32_t SyncPointClientState::GenerateUnprocessedOrderNumber(
+void SyncPointOrderData::Destroy() {
+  base::AutoLock auto_lock(order_fence_queue_lock_);
+  while (!order_fence_queue_.empty()) {
+    order_fence_queue_.pop();
+  }
+}
+
+uint32_t SyncPointOrderData::GenerateUnprocessedOrderNumber(
     SyncPointManager* sync_point_manager) {
   const uint32_t order_num = sync_point_manager->GenerateOrderNumber();
   base::subtle::Release_Store(&unprocessed_order_num_, order_num);
   return order_num;
 }
 
-SyncPointClientState::SyncPointClientState()
+void SyncPointOrderData::BeginProcessingOrderNumber(uint32_t order_num) {
+  DCHECK(processing_thread_checker_.CalledOnValidThread());
+  DCHECK_GE(order_num, current_order_num_);
+  current_order_num_ = order_num;
+}
+
+void SyncPointOrderData::FinishProcessingOrderNumber(uint32_t order_num) {
+  DCHECK(processing_thread_checker_.CalledOnValidThread());
+  DCHECK_EQ(current_order_num_, order_num);
+  DCHECK_GT(order_num, processed_order_num());
+
+  // Catch invalid waits which were waiting on fence syncs that do not exist.
+  // Release without the lock to avoid possible deadlocks.
+  std::vector<OrderFence> ensure_releases;
+  {
+    base::AutoLock auto_lock(order_fence_queue_lock_);
+    while (!order_fence_queue_.empty()) {
+      const OrderFence& order_fence = order_fence_queue_.top();
+      if (order_fence_queue_.top().order_num <= order_num) {
+        ensure_releases.push_back(order_fence);
+        order_fence_queue_.pop();
+        continue;
+      }
+      break;
+    }
+  }
+  for (OrderFence& order_fence : ensure_releases) {
+    order_fence.client_state->EnsureReleased(order_fence.fence_release);
+  }
+
+  base::subtle::Release_Store(&processed_order_num_, order_num);

[piman, 2015/09/30 22:50:23]

This should happen before we do the EnsureReleased, so that if the other client
tries to WaitForRelease on the same order, it will immediately call its
callback, instead of inserting an OrderFence, which would not be released until
later (if at all).

Actually, I believe modifying processed_order_num_ should happen under the lock,
otherwise there is a data race:
say thread 1 is in SyncPointClientState::WaitForRelease on l.140 (has the lock),
and thread 2 is in SyncPointOrderData::FinishProcessingOrderNumber on l.78
(doesn't have the lock). Thread 1 believe the order isn't passed, so it will add
the OrderFence. Thread 2 however is already done processing the order, but
hasn't updated processed_order_num_ yet.


So in the end, I don't think processed_order_num_ can simply be an atomic, it
also needs to be protected by the lock (at which point you can make it a
non-atomic simple variable).

You can probalby go through the same logic for unprocessed_order_num_ actually.
At the end of the day, you have an invariant: all the OrderFence in
order_fence_queue_ must have an order_num that is between processed_num_+1 and
unprocessed_order_num_ (inclusive). This invariant can only be consistent when
the lock is held.

[David Yen, 2015/09/30 23:55:18]

That is true, in that case even the release counts all need to be checked under
the lock. I have added a ValidateReleaseOrderNumber() function that does all of
this and replaces AddOrderFenceGuard().

+}
+
+SyncPointOrderData::OrderFence::OrderFence(
+    uint32_t order, uint64_t release, scoped_refptr<SyncPointClientState> state)
+  : order_num(order),
+    fence_release(release),
+    client_state(state) {
+}
+
+SyncPointOrderData::OrderFence::~OrderFence() {
+}
+
+SyncPointOrderData::SyncPointOrderData()
   : processed_order_num_(0),
     unprocessed_order_num_(0),
     current_order_num_(0) {
 }
 
+SyncPointOrderData::~SyncPointOrderData() {
+}
+
+void SyncPointOrderData::AddOrderFenceGuard(
+    uint32_t order_num, uint64_t fence_release,
+    scoped_refptr<SyncPointClientState> client_state) {
+  base::AutoLock auto_lock(order_fence_queue_lock_);
+  order_fence_queue_.push(OrderFence(order_num, fence_release, client_state));
+}
+
+SyncPointClientState::ReleaseCallback::ReleaseCallback(
+    uint64_t release, const base::Closure& callback)
+  : release_count(release),
+    callback_closure(callback) {
+}
+
+SyncPointClientState::ReleaseCallback::~ReleaseCallback() {
+}
+
+SyncPointClientState::SyncPointClientState(
+    scoped_refptr<SyncPointOrderData> order_data)
+  : order_data_(order_data),
+    fence_sync_release_(0) {
+}
+
 SyncPointClientState::~SyncPointClientState() {
 }
 
+bool SyncPointClientState::WaitForRelease(uint32_t wait_order_num,
+                                          uint64_t release,
+                                          const base::Closure& callback) {
+  // Lock must be held the whole time while we validate otherwise it could be
+  // released while we are checking.
+  {
+    base::AutoLock auto_lock(fence_sync_lock_);
+    if (release > fence_sync_release_) {
+      const uint32_t processed_num = order_data_->processed_order_num();
+      const uint32_t unprocessed_num = order_data_->unprocessed_order_num();
+
+      // Release should have a possible unprocessed order number lower
+      // than the wait order number.
+      if ((processed_num + 1) >= wait_order_num)

[piman, 2015/09/30 22:50:23]

I think this should be processed_num >= wait_order_num. If wait_order_num ==
processed_num+1, you would want to wait, not early exit.

[David Yen, 2015/09/30 23:55:18]

This is a bit tricky and I only found it after writing the unit test, but we
must have an unprocessed order number less than the wait order number so wait
order num has to be processed_num + 2. For example, if we processed up to 9 and
the wait order number is 10, the release can't exist.

[piman, 2015/10/01 01:00:23]

Ok, I think I convinced myself of why, but I think by going through that mental
process, I found an issue with the fact that we force-retire only in
FinishProcessingOrderNumber, after we reached or passed the waiting order num.

Say you have 2 clients and the following commands:

Client1:
[order 0] ...
[order 2] Release(1)
[order 5] Wait(2)

Client2:
[order 1] ...
[order 3] Wait(1)
[order 4] Release(2)
[order 6] ...

A valid execution order is [0 1 2 3 4 5 6], and that would work fine. However,
if Client1 doesn't Release(1) in [2], then when executing [3], Client2 will add
(Client2, [3], 1) to Client1's order_fence_queue_ (wait_order_num=[3],
client1.processed=0, client1.unprocessed=5), and unschedule. Client1 can
continue to [5] but because the fence 2 wasn't released, it will add itself to
Client2's order_fence_queue (wait_order_num=[5], client2.processed=1,
client2.unprocessed=6) and unschedule, never force-releasing 1 (and 2 won't be
force-released either).
-> deadlock.

The reason is that we really want to force-releasing 1 and unblock Client2 as
soon as Client1 goes beyond 3, that is, as soon as it starts processing [5], or
(if there was no [5]) as soon as it's out of things to do.


I think it would be useful to have a test for this case.

[David Yen, 2015/10/01 17:15:51]

Ah, that is a tricky case. I think we actually did think of this case when we
were discussing the different attacks. I added a unit test for this and verified
that it was failing, and also fixed it now.

+        return false;
+
+      // Release should have more unprocessed numbers if we are waiting.
+      if (unprocessed_num <= processed_num)
+        return false;
+
+      // Add the callback which will be called upon release.
+      release_callback_queue_.push(ReleaseCallback(release, callback));
+
+      // Validate by ensuring fence is released by the expected order number.
+      const uint32_t expected_order_num = std::min(unprocessed_num,
+                                                   wait_order_num);
+      order_data_->AddOrderFenceGuard(expected_order_num, release, this);
+      return true;
+    }
+  }
+
+  // Already released, run the callback now.
+  callback.Run();
+  return true;
+}
+
+void SyncPointClientState::ReleaseFenceSync(uint64_t release) {
+  // Call callbacks without the lock to avoid possible deadlocks.
+  std::vector<base::Closure> callback_list;
+  {
+    base::AutoLock auto_lock(fence_sync_lock_);
+    ReleaseFenceSyncLocked(release, &callback_list);
+  }
+
+  for (const base::Closure& closure : callback_list) {
+    closure.Run();
+  }
+}
+
+void SyncPointClientState::EnsureReleased(uint64_t release) {
+  // Call callbacks without the lock to avoid possible deadlocks.
+  std::vector<base::Closure> callback_list;
+  {
+    base::AutoLock auto_lock(fence_sync_lock_);
+    if (release <= fence_sync_release_)
+      return;
+
+    ReleaseFenceSyncLocked(release, &callback_list);
+  }
+
+  for (const base::Closure& closure : callback_list) {
+    closure.Run();
+  }
+}
+
+void SyncPointClientState::ReleaseFenceSyncLocked(
+    uint64_t release, std::vector<base::Closure>* callback_list) {
+  fence_sync_lock_.AssertAcquired();
+  DCHECK_GT(release, fence_sync_release_);
+
+  fence_sync_release_ = release;
+  while (!release_callback_queue_.empty() &&
+         release_callback_queue_.top().release_count <= release) {
+    callback_list->push_back(release_callback_queue_.top().callback_closure);
+    release_callback_queue_.pop();
+  }
+}
+
 SyncPointClient::~SyncPointClient() {
+  // Release all fences on destruction.
+  ReleaseFenceSync(UINT64_MAX);
+
   sync_point_manager_->DestroySyncPointClient(namespace_id_, client_id_);
 }
 
+bool SyncPointClient::Wait(scoped_refptr<SyncPointClientState> release_state,
+                           uint64_t release_count,
+                           const base::Closure& wait_complete_callback) {
+  const uint32_t wait_order_number =
+      client_state_->order_data()->current_order_num();
+  return release_state->WaitForRelease(wait_order_number,
+                                       release_count,
+                                       wait_complete_callback);
+}
+
+bool SyncPointClient::WaitNonThreadSafe(
+    scoped_refptr<SyncPointClientState> release_state,
+    uint64_t release_count,
+    scoped_refptr<base::SingleThreadTaskRunner> runner,
+    const base::Closure& wait_complete_callback) {
+  return Wait(release_state,
+              release_count,
+              base::Bind(&RunOnThread, runner, wait_complete_callback));
+}
+
+void SyncPointClient::ReleaseFenceSync(uint64_t release) {
+  client_state_->ReleaseFenceSync(release);
+}
+
 SyncPointClient::SyncPointClient(SyncPointManager* sync_point_manager,
-                                 scoped_refptr<SyncPointClientState> state,
+                                 scoped_refptr<SyncPointOrderData> order_data,
                                  CommandBufferNamespace namespace_id,
                                  uint64_t client_id)
   : sync_point_manager_(sync_point_manager),
-    client_state_(state),
+    client_state_(new SyncPointClientState(order_data)),
     namespace_id_(namespace_id),
     client_id_(client_id) {
 }
@@ -65,7 +262,7 @@ SyncPointManager::~SyncPointManager() {
 }
 
 scoped_ptr<SyncPointClient> SyncPointManager::CreateSyncPointClient(
-    scoped_refptr<SyncPointClientState> client_state,
+    scoped_refptr<SyncPointOrderData> order_data,
     CommandBufferNamespace namespace_id, uint64_t client_id) {
   DCHECK_GE(namespace_id, 0);
   DCHECK_LT(static_cast<size_t>(namespace_id), arraysize(client_maps_));
@@ -74,7 +271,7 @@ scoped_ptr<SyncPointClient> SyncPointManager::CreateSyncPointClient(
   ClientMap& client_map = client_maps_[namespace_id];
   std::pair<ClientMap::iterator, bool> result = client_map.insert(
       std::make_pair(client_id, new SyncPointClient(this,
-                                                    client_state,
+                                                    order_data,
                                                     namespace_id,
                                                     client_id)));
   DCHECK(result.second);