169 lines · c
1//===-- sanitizer_ring_buffer.h ---------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Simple ring buffer.10//11//===----------------------------------------------------------------------===//12#ifndef SANITIZER_RING_BUFFER_H13#define SANITIZER_RING_BUFFER_H14 15#include "sanitizer_common.h"16 17namespace __sanitizer {18// RingBuffer<T>: fixed-size ring buffer optimized for speed of push().19// T should be a POD type and sizeof(T) should be divisible by sizeof(void*).20// At creation, all elements are zero.21template<class T>22class RingBuffer {23 public:24 COMPILER_CHECK(sizeof(T) % sizeof(void *) == 0);25 static RingBuffer *New(uptr Size) {26 void *Ptr = MmapOrDie(SizeInBytes(Size), "RingBuffer");27 RingBuffer *RB = reinterpret_cast<RingBuffer*>(Ptr);28 uptr End = reinterpret_cast<uptr>(Ptr) + SizeInBytes(Size);29 RB->last_ = RB->next_ = reinterpret_cast<T*>(End - sizeof(T));30 return RB;31 }32 void Delete() {33 UnmapOrDie(this, SizeInBytes(size()));34 }35 uptr size() const {36 return last_ + 1 -37 reinterpret_cast<T *>(reinterpret_cast<uptr>(this) +38 2 * sizeof(T *));39 }40 41 static uptr SizeInBytes(uptr Size) {42 return Size * sizeof(T) + 2 * sizeof(T*);43 }44 45 uptr SizeInBytes() { return SizeInBytes(size()); }46 47 void push(T t) {48 *next_ = t;49 next_--;50 static_assert((sizeof(T) % sizeof(T *)) == 0,51 "The condition below works only if sizeof(T) is divisible by "52 "sizeof(T*).");53 if (next_ <= reinterpret_cast<T*>(&next_))54 next_ = last_;55 }56 57 T operator[](uptr Idx) const {58 CHECK_LT(Idx, size());59 sptr IdxNext = Idx + 1;60 if (IdxNext > last_ - next_)61 IdxNext -= size();62 return next_[IdxNext];63 }64 65 private:66 RingBuffer() {}67 ~RingBuffer() {}68 RingBuffer(const RingBuffer&) = delete;69 70 // Data layout:71 // LNDDDDDDDD72 // D: data elements.73 // L: last_, always points to the last data element.74 // N: next_, initially equals to last_, is decremented on every push,75 // wraps around if it's less or equal than its own address.76 T *last_;77 T *next_;78 T data_[1]; // flexible array.79};80 81// A ring buffer with externally provided storage that encodes its state in 882// bytes. Has significant constraints on size and alignment of storage.83// See a comment in hwasan/hwasan_thread_list.h for the motivation behind this.84#if SANITIZER_WORDSIZE == 6485template <class T>86class CompactRingBuffer {87 // Top byte of long_ stores the buffer size in pages.88 // Lower bytes store the address of the next buffer element.89 static constexpr int kPageSizeBits = 12;90 static constexpr int kSizeShift = 56;91 static constexpr int kSizeBits = 64 - kSizeShift;92 static constexpr uptr kNextMask = (1ULL << kSizeShift) - 1;93 94 uptr GetStorageSize() const { return (long_ >> kSizeShift) << kPageSizeBits; }95 96 static uptr SignExtend(uptr x) { return ((sptr)x) << kSizeBits >> kSizeBits; }97 98 void Init(void *storage, uptr size) {99 CHECK_EQ(sizeof(CompactRingBuffer<T>), sizeof(void *));100 CHECK(IsPowerOfTwo(size));101 CHECK_GE(size, 1 << kPageSizeBits);102 CHECK_LE(size, 128 << kPageSizeBits);103 CHECK_EQ(size % 4096, 0);104 CHECK_EQ(size % sizeof(T), 0);105 uptr st = (uptr)storage;106 CHECK_EQ(st % (size * 2), 0);107 CHECK_EQ(st, SignExtend(st & kNextMask));108 long_ = (st & kNextMask) | ((size >> kPageSizeBits) << kSizeShift);109 }110 111 void SetNext(const T *next) {112 long_ = (long_ & ~kNextMask) | ((uptr)next & kNextMask);113 }114 115 public:116 CompactRingBuffer(void *storage, uptr size) {117 Init(storage, size);118 }119 120 // A copy constructor of sorts.121 CompactRingBuffer(const CompactRingBuffer &other, void *storage) {122 uptr size = other.GetStorageSize();123 internal_memcpy(storage, other.StartOfStorage(), size);124 Init(storage, size);125 uptr Idx = other.Next() - (const T *)other.StartOfStorage();126 SetNext((const T *)storage + Idx);127 }128 129 T *Next() const { return (T *)(SignExtend(long_ & kNextMask)); }130 131 void *StartOfStorage() const {132 return (void *)((uptr)Next() & ~(GetStorageSize() - 1));133 }134 135 void *EndOfStorage() const {136 return (void *)((uptr)StartOfStorage() + GetStorageSize());137 }138 139 uptr size() const { return GetStorageSize() / sizeof(T); }140 141 void push(T t) {142 T *next = Next();143 *next = t;144 next++;145 next = (T *)((uptr)next & ~GetStorageSize());146 SetNext(next);147 }148 149 const T &operator[](uptr Idx) const {150 CHECK_LT(Idx, size());151 const T *Begin = (const T *)StartOfStorage();152 sptr StorageIdx = Next() - Begin;153 StorageIdx -= (sptr)(Idx + 1);154 if (StorageIdx < 0)155 StorageIdx += size();156 return Begin[StorageIdx];157 }158 159 public:160 ~CompactRingBuffer() {}161 CompactRingBuffer(const CompactRingBuffer &) = delete;162 163 uptr long_;164};165#endif166} // namespace __sanitizer167 168#endif // SANITIZER_RING_BUFFER_H169