diff options
author | Dean Michael Berris <dberris@google.com> | 2017-10-03 06:15:34 +0000 |
---|---|---|
committer | Dean Michael Berris <dberris@google.com> | 2017-10-03 06:15:34 +0000 |
commit | ebffae6c671e3c5c914395212eea2ce3b5269312 (patch) | |
tree | eb0d213d26b768504ba088917db8e84f5ee67322 /lib/xray | |
parent | dad2946b51de3226184ca0aff641537f3e532857 (diff) |
[XRay][compiler-rt] Use a hand-written circular buffer in BufferQueue
Summary:
This change removes the dependency on using a std::deque<...> for the
storage of the buffers in the buffer queue. We instead implement a
fixed-size circular buffer that's resilient to exhaustion, and preserves
the semantics of the BufferQueue.
We're moving away from using std::deque<...> for two reasons:
- We want to remove dependencies on the STL for data structures.
- We want the data structure we use to not require re-allocation in
the normal course of operation.
The internal implementation of the buffer queue uses heap-allocated
arrays that are initialized once when the BufferQueue is created, and
re-uses slots in the buffer array as buffers are returned in order.
We also change the lock used in the implementation to a spinlock
instead of a blocking mutex. We reason that since the release operations
now take very little time in the critical section, that a spinlock would
be appropriate.
This change is related to D38073.
Reviewers: dblaikie, kpw, pelikan
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D38119
git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@314766 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/xray')
-rw-r--r-- | lib/xray/xray_buffer_queue.cc | 49 | ||||
-rw-r--r-- | lib/xray/xray_buffer_queue.h | 23 |
2 files changed, 51 insertions, 21 deletions
diff --git a/lib/xray/xray_buffer_queue.cc b/lib/xray/xray_buffer_queue.cc index 7ba755ac3..99175a025 100644 --- a/lib/xray/xray_buffer_queue.cc +++ b/lib/xray/xray_buffer_queue.cc @@ -16,6 +16,7 @@ #include "sanitizer_common/sanitizer_common.h" #include "sanitizer_common/sanitizer_libc.h" +#include <algorithm> #include <cstdlib> #include <tuple> @@ -23,18 +24,21 @@ using namespace __xray; using namespace __sanitizer; BufferQueue::BufferQueue(std::size_t B, std::size_t N, bool &Success) - : BufferSize(B), Buffers(N), Mutex(), OwnedBuffers(), Finalizing{0} { - for (auto &T : Buffers) { + : BufferSize(B), Buffers(new std::tuple<Buffer, bool>[N]()), + BufferCount(N), Finalizing{0}, OwnedBuffers(new void *[N]()), + Next(Buffers.get()), First(nullptr) { + for (size_t i = 0; i < N; ++i) { + auto &T = Buffers[i]; void *Tmp = malloc(BufferSize); if (Tmp == nullptr) { Success = false; return; } - auto &Buf = std::get<0>(T); + std::get<1>(T) = false; Buf.Buffer = Tmp; Buf.Size = B; - OwnedBuffers.emplace(Tmp); + OwnedBuffers[i] = Tmp; } Success = true; } @@ -42,27 +46,43 @@ BufferQueue::BufferQueue(std::size_t B, std::size_t N, bool &Success) BufferQueue::ErrorCode BufferQueue::getBuffer(Buffer &Buf) { if (__sanitizer::atomic_load(&Finalizing, __sanitizer::memory_order_acquire)) return ErrorCode::QueueFinalizing; - __sanitizer::BlockingMutexLock Guard(&Mutex); - if (Buffers.empty()) + __sanitizer::SpinMutexLock Guard(&Mutex); + + if (Next == First) return ErrorCode::NotEnoughMemory; - auto &T = Buffers.front(); + + auto &T = *Next; auto &B = std::get<0>(T); Buf = B; - B.Buffer = nullptr; - B.Size = 0; - Buffers.pop_front(); + + if (First == nullptr) + First = Next; + ++Next; + if (Next == (Buffers.get() + BufferCount)) + Next = Buffers.get(); + return ErrorCode::Ok; } BufferQueue::ErrorCode BufferQueue::releaseBuffer(Buffer &Buf) { - if (OwnedBuffers.count(Buf.Buffer) == 0) + // Blitz through the buffers array to find the buffer. + if (std::none_of(OwnedBuffers.get(), OwnedBuffers.get() + BufferCount, + [&Buf](void *P) { return P == Buf.Buffer; })) return ErrorCode::UnrecognizedBuffer; - __sanitizer::BlockingMutexLock Guard(&Mutex); + __sanitizer::SpinMutexLock Guard(&Mutex); + + // This points to a semantic bug, we really ought to not be releasing more + // buffers than we actually get. + if (First == nullptr || First == Next) + return ErrorCode::NotEnoughMemory; // Now that the buffer has been released, we mark it as "used". - Buffers.emplace(Buffers.end(), Buf, true /* used */); + *First = std::make_tuple(Buf, true); Buf.Buffer = nullptr; Buf.Size = 0; + ++First; + if (First == (Buffers.get() + BufferCount)) + First = Buffers.get(); return ErrorCode::Ok; } @@ -74,7 +94,8 @@ BufferQueue::ErrorCode BufferQueue::finalize() { } BufferQueue::~BufferQueue() { - for (auto &T : Buffers) { + for (auto I = Buffers.get(), E = Buffers.get() + BufferCount; I != E; ++I) { + auto &T = *I; auto &Buf = std::get<0>(T); free(Buf.Buffer); } diff --git a/lib/xray/xray_buffer_queue.h b/lib/xray/xray_buffer_queue.h index bd382a26c..1115b4722 100644 --- a/lib/xray/xray_buffer_queue.h +++ b/lib/xray/xray_buffer_queue.h @@ -17,8 +17,8 @@ #include "sanitizer_common/sanitizer_atomic.h" #include "sanitizer_common/sanitizer_mutex.h" -#include <deque> -#include <unordered_set> +#include <cstdint> +#include <memory> #include <utility> namespace __xray { @@ -36,15 +36,23 @@ public: }; private: + // Size of each individual Buffer. size_t BufferSize; // We use a bool to indicate whether the Buffer has been used in this // freelist implementation. - std::deque<std::tuple<Buffer, bool>> Buffers; - __sanitizer::BlockingMutex Mutex; - std::unordered_set<void *> OwnedBuffers; + std::unique_ptr<std::tuple<Buffer, bool>[]> Buffers; + size_t BufferCount; + + __sanitizer::SpinMutex Mutex; __sanitizer::atomic_uint8_t Finalizing; + // Sorted buffer pointers, making it quick to find buffers that we own. + std::unique_ptr<void *[]> OwnedBuffers; + + std::tuple<Buffer, bool> *Next; + std::tuple<Buffer, bool> *First; + public: enum class ErrorCode : unsigned { Ok, @@ -117,8 +125,9 @@ public: /// Buffer is marked 'used' (i.e. has been the result of getBuffer(...) and a /// releaseBuffer(...) operation). template <class F> void apply(F Fn) { - __sanitizer::BlockingMutexLock G(&Mutex); - for (const auto &T : Buffers) { + __sanitizer::SpinMutexLock G(&Mutex); + for (auto I = Buffers.get(), E = Buffers.get() + BufferCount; I != E; ++I) { + const auto &T = *I; if (std::get<1>(T)) Fn(std::get<0>(T)); } |