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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Simple ring buffer.
10//
11//===----------------------------------------------------------------------===//
12#ifndef SANITIZER_RING_BUFFER_H
13#define SANITIZER_RING_BUFFER_H
14
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    // The condition below works only if sizeof(T) is divisible by sizeof(T*).
51    if (next_ <= reinterpret_cast<T*>(&next_))
52      next_ = last_;
53  }
54
55  T operator[](uptr Idx) const {
56    CHECK_LT(Idx, size());
57    sptr IdxNext = Idx + 1;
58    if (IdxNext > last_ - next_)
59      IdxNext -= size();
60    return next_[IdxNext];
61  }
62
63 private:
64  RingBuffer() {}
65  ~RingBuffer() {}
66  RingBuffer(const RingBuffer&) = delete;
67
68  // Data layout:
69  // LNDDDDDDDD
70  // D: data elements.
71  // L: last_, always points to the last data element.
72  // N: next_, initially equals to last_, is decremented on every push,
73  //    wraps around if it's less or equal than its own address.
74  T *last_;
75  T *next_;
76  T data_[1];  // flexible array.
77};
78
79// A ring buffer with externally provided storage that encodes its state in 8
80// bytes. Has significant constraints on size and alignment of storage.
81// See a comment in hwasan/hwasan_thread_list.h for the motivation behind this.
82#if SANITIZER_WORDSIZE == 64
83template <class T>
84class CompactRingBuffer {
85  // Top byte of long_ stores the buffer size in pages.
86  // Lower bytes store the address of the next buffer element.
87  static constexpr int kPageSizeBits = 12;
88  static constexpr int kSizeShift = 56;
89  static constexpr int kSizeBits = 64 - kSizeShift;
90  static constexpr uptr kNextMask = (1ULL << kSizeShift) - 1;
91
92  uptr GetStorageSize() const { return (long_ >> kSizeShift) << kPageSizeBits; }
93
94  static uptr SignExtend(uptr x) { return ((sptr)x) << kSizeBits >> kSizeBits; }
95
96  void Init(void *storage, uptr size) {
97    CHECK_EQ(sizeof(CompactRingBuffer<T>), sizeof(void *));
98    CHECK(IsPowerOfTwo(size));
99    CHECK_GE(size, 1 << kPageSizeBits);
100    CHECK_LE(size, 128 << kPageSizeBits);
101    CHECK_EQ(size % 4096, 0);
102    CHECK_EQ(size % sizeof(T), 0);
103    uptr st = (uptr)storage;
104    CHECK_EQ(st % (size * 2), 0);
105    CHECK_EQ(st, SignExtend(st & kNextMask));
106    long_ = (st & kNextMask) | ((size >> kPageSizeBits) << kSizeShift);
107  }
108
109  void SetNext(const T *next) {
110    long_ = (long_ & ~kNextMask) | ((uptr)next & kNextMask);
111  }
112
113 public:
114  CompactRingBuffer(void *storage, uptr size) {
115    Init(storage, size);
116  }
117
118  // A copy constructor of sorts.
119  CompactRingBuffer(const CompactRingBuffer &other, void *storage) {
120    uptr size = other.GetStorageSize();
121    internal_memcpy(storage, other.StartOfStorage(), size);
122    Init(storage, size);
123    uptr Idx = other.Next() - (const T *)other.StartOfStorage();
124    SetNext((const T *)storage + Idx);
125  }
126
127  T *Next() const { return (T *)(SignExtend(long_ & kNextMask)); }
128
129  void *StartOfStorage() const {
130    return (void *)((uptr)Next() & ~(GetStorageSize() - 1));
131  }
132
133  void *EndOfStorage() const {
134    return (void *)((uptr)StartOfStorage() + GetStorageSize());
135  }
136
137  uptr size() const { return GetStorageSize() / sizeof(T); }
138
139  void push(T t) {
140    T *next = Next();
141    *next = t;
142    next++;
143    next = (T *)((uptr)next & ~GetStorageSize());
144    SetNext(next);
145  }
146
147  const T &operator[](uptr Idx) const {
148    CHECK_LT(Idx, size());
149    const T *Begin = (const T *)StartOfStorage();
150    sptr StorageIdx = Next() - Begin;
151    StorageIdx -= (sptr)(Idx + 1);
152    if (StorageIdx < 0)
153      StorageIdx += size();
154    return Begin[StorageIdx];
155  }
156
157 public:
158  ~CompactRingBuffer() {}
159  CompactRingBuffer(const CompactRingBuffer &) = delete;
160
161  uptr long_;
162};
163#endif
164}  // namespace __sanitizer
165
166#endif  // SANITIZER_RING_BUFFER_H
167