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