1 //===- Waymarking.h - Array waymarking algorithm ----------------*- 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 // Utility to backtrace an array's head, from a pointer into it. For the
10 // backtrace to work, we use "Waymarks", which are special tags embedded into
11 // the array's elements.
12 //
13 // A Tag of n-bits (in size) is composed as follows:
14 //
15 // bits: |   n-1   |             n-2 ... 0              |
16 //       .---------.------------------------------------.
17 //       |Stop Mask|(2^(n-1))-ary numeric system - digit|
18 //       '---------'------------------------------------'
19 //
20 // Backtracing is done as follows:
21 // Walk back (starting from a given pointer to an element into the array), until
22 // a tag with a "Stop Mask" is reached. Then start calculating the "Offset" from
23 // the array's head, by picking up digits along the way, until another stop is
24 // reached. The "Offset" is then subtracted from the current pointer, and the
25 // result is the array's head.
26 // A special case - if we first encounter a Tag with a Stop and a zero digit,
27 // then this is already the head.
28 //
29 // For example:
30 // In case of 2 bits:
31 //
32 // Tags:
33 // x0 - binary digit 0
34 // x1 - binary digit 1
35 // 1x - stop and calculate (s)
36 //
37 // Array:
38 //         .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
39 // head -> |s0 |s1 | 0 |s1 | 0 | 0 |s1 | 1 | 1 |s1 | 0 | 1 | 0 |s1 | 0 | 1 |
40 //         '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'
41 //             |-1 |-2     |-4         |-7         |-10            |-14
42 //          <_ |   |       |           |           |               |
43 //          <_____ |       |           |           |               |
44 //          <_____________ |           |           |               |
45 //          <_________________________ |           |               |
46 //          <_____________________________________ |               |
47 //          <_____________________________________________________ |
48 //
49 //
50 // In case of 3 bits:
51 //
52 // Tags:
53 // x00 - quaternary digit 0
54 // x01 - quaternary digit 1
55 // x10 - quaternary digit 2
56 // x11 - quaternary digit 3
57 // 1xy - stop and calculate (s)
58 //
59 // Array:
60 //         .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
61 // head -> |s0 |s1 |s2 |s3 | 0 |s1 | 2 |s1 | 0 |s2 | 2 |s2 | 0 |s3 | 2 |s3 |
62 //         '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'
63 //             |-1 |-2 |-3 |-4     |-6     |-8     |-10    |-12    |-14    |-16
64 //          <_ |   |   |   |       |       |       |       |       |       |
65 //          <_____ |   |   |       |       |       |       |       |       |
66 //          <_________ |   |       |       |       |       |       |       |
67 //          <_____________ |       |       |       |       |       |       |
68 //          <_____________________ |       |       |       |       |       |
69 //          <_____________________________ |       |       |       |       |
70 //          <_____________________________________ |       |       |       |
71 //          <_____________________________________________ |       |       |
72 //          <_____________________________________________________ |       |
73 //          <_____________________________________________________________ |
74 //
75 //
76 // The API introduce 2 functions:
77 // 1. fillWaymarks
78 // 2. followWaymarks
79 //
80 // Example:
81 //   int N = 10;
82 //   int M = 5;
83 //   int **A = new int *[N + M];   // Define the array.
84 //   for (int I = 0; I < N + M; ++I)
85 //     A[I] = new int(I);
86 //
87 //   fillWaymarks(A, A + N);       // Set the waymarks for the first N elements
88 //                                 // of the array.
89 //                                 // Note that it must be done AFTER we fill
90 //                                 // the array's elements.
91 //
92 //   ...                           // Elements which are not in the range
93 //                                 // [A, A+N) will not be marked, and we won't
94 //                                 // be able to call followWaymarks on them.
95 //
96 //   ...                           // Elements which will be changed after the
97 //                                 // call to fillWaymarks, will have to be
98 //                                 // retagged.
99 //
100 //   fillWaymarks(A + N, A + N + M, N); // Set the waymarks of the remaining M
101 //                                      // elements.
102 //   ...
103 //   int **It = A + N + 1;
104 //   int **B = followWaymarks(It); // Find the head of the array containing It.
105 //   assert(B == A);
106 //
107 //===----------------------------------------------------------------------===//
108 
109 #ifndef LLVM_ADT_WAYMARKING_H
110 #define LLVM_ADT_WAYMARKING_H
111 
112 #include "llvm/ADT/STLExtras.h"
113 #include "llvm/Support/PointerLikeTypeTraits.h"
114 
115 namespace llvm {
116 
117 namespace detail {
118 
119 template <unsigned NumBits> struct WaymarkingTraits {
120   enum : unsigned {
121     // The number of bits of a Waymarking Tag.
122     NUM_BITS = NumBits,
123 
124     // A Tag is composed from a Mark and a Stop mask.
125     MARK_SIZE = NUM_BITS - 1,
126     STOP_MASK = (1 << MARK_SIZE),
127     MARK_MASK = (STOP_MASK - 1),
128     TAG_MASK = (MARK_MASK | STOP_MASK),
129 
130     // The number of pre-computed tags (for fast fill).
131     NUM_STATIC_TAGS = 32
132   };
133 
134 private:
135   // Add a new tag, calculated from Count and Stop, to the Vals pack, while
136   // continuing recursively to decrease Len down to 0.
137   template <unsigned Len, bool Stop, unsigned Count, uint8_t... Vals>
138   struct AddTag;
139 
140   // Delegate to the specialized AddTag according to the need of a Stop mask.
141   template <unsigned Len, unsigned Count, uint8_t... Vals> struct GenTag {
142     typedef
143         typename AddTag<Len, (Count <= MARK_MASK), Count, Vals...>::Xdata Xdata;
144   };
145 
146   // Start adding tags while calculating the next Count, which is actually the
147   // number of already calculated tags (equivalent to the position in the
148   // array).
149   template <unsigned Len, uint8_t... Vals> struct GenOffset {
150     typedef typename GenTag<Len, sizeof...(Vals), Vals...>::Xdata Xdata;
151   };
152 
153   // Add the tag and remove it from Count.
154   template <unsigned Len, unsigned Count, uint8_t... Vals>
155   struct AddTag<Len, false, Count, Vals...> {
156     typedef typename GenTag<Len - 1, (Count >> MARK_SIZE), Vals...,
157                             Count & MARK_MASK>::Xdata Xdata;
158   };
159 
160   // We have reached the end of this Count, so start with a new Count.
161   template <unsigned Len, unsigned Count, uint8_t... Vals>
162   struct AddTag<Len, true, Count, Vals...> {
163     typedef typename GenOffset<Len - 1, Vals...,
164                                (Count & MARK_MASK) | STOP_MASK>::Xdata Xdata;
165   };
166 
167   template <unsigned Count, uint8_t... Vals> struct TagsData {
168     // The remaining number for calculating the next tag, following the last one
169     // in Values.
170     static const unsigned Remain = Count;
171 
172     // The array of ordered pre-computed Tags.
173     static const uint8_t Values[sizeof...(Vals)];
174   };
175 
176   // Specialize the case when Len equals 0, as the recursion stop condition.
177   template <unsigned Count, uint8_t... Vals>
178   struct AddTag<0, false, Count, Vals...> {
179     typedef TagsData<Count, Vals...> Xdata;
180   };
181 
182   template <unsigned Count, uint8_t... Vals>
183   struct AddTag<0, true, Count, Vals...> {
184     typedef TagsData<Count, Vals...> Xdata;
185   };
186 
187 public:
188   typedef typename GenOffset<NUM_STATIC_TAGS>::Xdata Tags;
189 };
190 
191 template <unsigned NumBits>
192 template <unsigned Count, uint8_t... Vals>
193 const uint8_t WaymarkingTraits<NumBits>::TagsData<
194     Count, Vals...>::Values[sizeof...(Vals)] = {Vals...};
195 
196 } // end namespace detail
197 
198 /// This class is responsible for tagging (and retrieving the tag of) a given
199 /// element of type T.
200 template <class T, class WTraits = detail::WaymarkingTraits<
201                        PointerLikeTypeTraits<T>::NumLowBitsAvailable>>
202 struct Waymarker {
203   using Traits = WTraits;
204   static void setWaymark(T &N, unsigned Tag) { N.setWaymark(Tag); }
205   static unsigned getWaymark(const T &N) { return N.getWaymark(); }
206 };
207 
208 template <class T, class WTraits> struct Waymarker<T *, WTraits> {
209   using Traits = WTraits;
210   static void setWaymark(T *&N, unsigned Tag) {
211     reinterpret_cast<uintptr_t &>(N) |= static_cast<uintptr_t>(Tag);
212   }
213   static unsigned getWaymark(const T *N) {
214     return static_cast<unsigned>(reinterpret_cast<uintptr_t>(N)) &
215            Traits::TAG_MASK;
216   }
217 };
218 
219 /// Sets up the waymarking algorithm's tags for a given range [Begin, End).
220 ///
221 /// \param Begin The beginning of the range to mark with tags (inclusive).
222 /// \param End The ending of the range to mark with tags (exclusive).
223 /// \param Offset The position in the supposed tags array from which to start
224 /// marking the given range.
225 template <class TIter, class Marker = Waymarker<
226                            typename std::iterator_traits<TIter>::value_type>>
227 void fillWaymarks(TIter Begin, TIter End, size_t Offset = 0) {
228   if (Begin == End)
229     return;
230 
231   size_t Count = Marker::Traits::Tags::Remain;
232   if (Offset <= Marker::Traits::NUM_STATIC_TAGS) {
233     // Start by filling the pre-calculated tags, starting from the given offset.
234     while (Offset != Marker::Traits::NUM_STATIC_TAGS) {
235       Marker::setWaymark(*Begin, Marker::Traits::Tags::Values[Offset]);
236 
237       ++Offset;
238       ++Begin;
239 
240       if (Begin == End)
241         return;
242     }
243   } else {
244     // The given offset is larger than the number of pre-computed tags, so we
245     // must do it the hard way.
246     // Calculate the next remaining Count, as if we have filled the tags up to
247     // the given offset.
248     size_t Off = Marker::Traits::NUM_STATIC_TAGS;
249     do {
250       ++Off;
251 
252       unsigned Tag = Count & Marker::Traits::MARK_MASK;
253 
254       // If the count can fit into the tag, then the counting must stop.
255       if (Count <= Marker::Traits::MARK_MASK) {
256         Tag |= Marker::Traits::STOP_MASK;
257         Count = Off;
258       } else
259         Count >>= Marker::Traits::MARK_SIZE;
260     } while (Off != Offset);
261   }
262 
263   // By now, we have the matching remaining Count for the current offset.
264   do {
265     ++Offset;
266 
267     unsigned Tag = Count & Marker::Traits::MARK_MASK;
268 
269     // If the count can fit into the tag, then the counting must stop.
270     if (Count <= Marker::Traits::MARK_MASK) {
271       Tag |= Marker::Traits::STOP_MASK;
272       Count = Offset;
273     } else
274       Count >>= Marker::Traits::MARK_SIZE;
275 
276     Marker::setWaymark(*Begin, Tag);
277     ++Begin;
278   } while (Begin != End);
279 }
280 
281 /// Sets up the waymarking algorithm's tags for a given range.
282 ///
283 /// \param Range The range to mark with tags.
284 /// \param Offset The position in the supposed tags array from which to start
285 /// marking the given range.
286 template <typename R, class Marker = Waymarker<typename std::remove_reference<
287                           decltype(*std::begin(std::declval<R &>()))>::type>>
288 void fillWaymarks(R &&Range, size_t Offset = 0) {
289   return fillWaymarks<decltype(std::begin(std::declval<R &>())), Marker>(
290       adl_begin(Range), adl_end(Range), Offset);
291 }
292 
293 /// Retrieves the element marked with tag of only STOP_MASK, by following the
294 /// waymarks. This is the first element in a range passed to a previous call to
295 /// \c fillWaymarks with \c Offset 0.
296 ///
297 /// For the trivial usage of calling \c fillWaymarks(Array), and \I is an
298 /// iterator inside \c Array, this function retrieves the head of \c Array, by
299 /// following the waymarks.
300 ///
301 /// \param I The iterator into an array which was marked by the waymarking tags
302 /// (by a previous call to \c fillWaymarks).
303 template <class TIter, class Marker = Waymarker<
304                            typename std::iterator_traits<TIter>::value_type>>
305 TIter followWaymarks(TIter I) {
306   unsigned Tag;
307   do
308     Tag = Marker::getWaymark(*I--);
309   while (!(Tag & Marker::Traits::STOP_MASK));
310 
311   // Special case for the first Use.
312   if (Tag != Marker::Traits::STOP_MASK) {
313     ptrdiff_t Offset = Tag & Marker::Traits::MARK_MASK;
314     while (!((Tag = Marker::getWaymark(*I)) & Marker::Traits::STOP_MASK)) {
315       Offset = (Offset << Marker::Traits::MARK_SIZE) + Tag;
316       --I;
317     }
318     I -= Offset;
319   }
320   return ++I;
321 }
322 
323 } // end namespace llvm
324 
325 #endif // LLVM_ADT_WAYMARKING_H
326