summaryrefslogtreecommitdiffstats
path: root/mozglue/baseprofiler/public/ProfileChunkedBufferDetail.h
blob: 75e461cd40dfd6b919b103622d033be6ad9cb39d (plain)
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef ProfileChunkedBufferDetail_h
#define ProfileChunkedBufferDetail_h

#include "mozilla/Assertions.h"
#include "mozilla/Likely.h"
#include "mozilla/ProfileBufferChunk.h"
#include "mozilla/ProfileBufferEntrySerialization.h"

namespace mozilla::profiler::detail {

// Internal accessor pointing at a position inside a chunk.
// It can handle two groups of chunks (typically the extant chunks stored in
// the store manager, and the current chunk).
// The main operations are:
// - ReadEntrySize() to read an entry size, 0 means failure.
// - operator+=(Length) to skip a number of bytes.
// - EntryReader() creates an entry reader at the current position for a given
//   size (it may fail with an empty reader), and skips the entry.
// Note that there is no "past-the-end" position -- as soon as InChunkPointer
// reaches the end, it becomes effectively null.
class InChunkPointer {
 public:
  using Byte = ProfileBufferChunk::Byte;
  using Length = ProfileBufferChunk::Length;

  // Nullptr-like InChunkPointer, may be used as end iterator.
  InChunkPointer()
      : mChunk(nullptr), mNextChunkGroup(nullptr), mOffsetInChunk(0) {}

  // InChunkPointer over one or two chunk groups, pointing at the given
  // block index (if still in range).
  // This constructor should only be used with *trusted* block index values!
  InChunkPointer(const ProfileBufferChunk* aChunk,
                 const ProfileBufferChunk* aNextChunkGroup,
                 ProfileBufferBlockIndex aBlockIndex)
      : mChunk(aChunk), mNextChunkGroup(aNextChunkGroup) {
    if (mChunk) {
      mOffsetInChunk = mChunk->OffsetFirstBlock();
      Adjust();
    } else if (mNextChunkGroup) {
      mChunk = mNextChunkGroup;
      mNextChunkGroup = nullptr;
      mOffsetInChunk = mChunk->OffsetFirstBlock();
      Adjust();
    } else {
      mOffsetInChunk = 0;
    }

    // Try to advance to given position.
    if (!AdvanceToGlobalRangePosition(aBlockIndex)) {
      // Block does not exist anymore (or block doesn't look valid), reset the
      // in-chunk pointer.
      mChunk = nullptr;
      mNextChunkGroup = nullptr;
    }
  }

  // InChunkPointer over one or two chunk groups, will start at the first
  // block (if any). This may be slow, so avoid using it too much.
  InChunkPointer(const ProfileBufferChunk* aChunk,
                 const ProfileBufferChunk* aNextChunkGroup,
                 ProfileBufferIndex aIndex = ProfileBufferIndex(0))
      : mChunk(aChunk), mNextChunkGroup(aNextChunkGroup) {
    if (mChunk) {
      mOffsetInChunk = mChunk->OffsetFirstBlock();
      Adjust();
    } else if (mNextChunkGroup) {
      mChunk = mNextChunkGroup;
      mNextChunkGroup = nullptr;
      mOffsetInChunk = mChunk->OffsetFirstBlock();
      Adjust();
    } else {
      mOffsetInChunk = 0;
    }

    // Try to advance to given position.
    if (!AdvanceToGlobalRangePosition(aIndex)) {
      // Block does not exist anymore, reset the in-chunk pointer.
      mChunk = nullptr;
      mNextChunkGroup = nullptr;
    }
  }

  // Compute the current position in the global range.
  // 0 if null (including if we're reached the end).
  [[nodiscard]] ProfileBufferIndex GlobalRangePosition() const {
    if (IsNull()) {
      return 0;
    }
    return mChunk->RangeStart() + mOffsetInChunk;
  }

  // Move InChunkPointer forward to the block at the given global block
  // position, which is assumed to be valid exactly -- but it may be obsolete.
  // 0 stays where it is (if valid already).
  // MOZ_ASSERTs if the index is invalid.
  [[nodiscard]] bool AdvanceToGlobalRangePosition(
      ProfileBufferBlockIndex aBlockIndex) {
    if (IsNull()) {
      // Pointer is null already. (Not asserting because it's acceptable.)
      return false;
    }
    if (!aBlockIndex) {
      // Special null position, just stay where we are.
      return ShouldPointAtValidBlock();
    }
    if (aBlockIndex.ConvertToProfileBufferIndex() < GlobalRangePosition()) {
      // Past the requested position, stay where we are (assuming the current
      // position was valid).
      return ShouldPointAtValidBlock();
    }
    for (;;) {
      if (aBlockIndex.ConvertToProfileBufferIndex() <
          mChunk->RangeStart() + mChunk->OffsetPastLastBlock()) {
        // Target position is in this chunk's written space, move to it.
        mOffsetInChunk =
            aBlockIndex.ConvertToProfileBufferIndex() - mChunk->RangeStart();
        return ShouldPointAtValidBlock();
      }
      // Position is after this chunk, try next chunk.
      GoToNextChunk();
      if (IsNull()) {
        return false;
      }
      // Skip whatever block tail there is, we don't allow pointing in the
      // middle of a block.
      mOffsetInChunk = mChunk->OffsetFirstBlock();
      if (aBlockIndex.ConvertToProfileBufferIndex() < GlobalRangePosition()) {
        // Past the requested position, meaning that the given position was in-
        // between blocks -> Failure.
        MOZ_ASSERT(false, "AdvanceToGlobalRangePosition - In-between blocks");
        return false;
      }
    }
  }

  // Move InChunkPointer forward to the block at or after the given global
  // range position.
  // 0 stays where it is (if valid already).
  [[nodiscard]] bool AdvanceToGlobalRangePosition(
      ProfileBufferIndex aPosition) {
    if (aPosition == 0) {
      // Special position '0', just stay where we are.
      // Success if this position is already valid.
      return !IsNull();
    }
    for (;;) {
      ProfileBufferIndex currentPosition = GlobalRangePosition();
      if (currentPosition == 0) {
        // Pointer is null.
        return false;
      }
      if (aPosition <= currentPosition) {
        // At or past the requested position, stay where we are.
        return true;
      }
      if (aPosition < mChunk->RangeStart() + mChunk->OffsetPastLastBlock()) {
        // Target position is in this chunk's written space, move to it.
        for (;;) {
          // Skip the current block.
          mOffsetInChunk += ReadEntrySize();
          if (mOffsetInChunk >= mChunk->OffsetPastLastBlock()) {
            // Reached the end of the chunk, this can happen for the last
            // block, let's just continue to the next chunk.
            break;
          }
          if (aPosition <= mChunk->RangeStart() + mOffsetInChunk) {
            // We're at or after the position, return at this block position.
            return true;
          }
        }
      }
      // Position is after this chunk, try next chunk.
      GoToNextChunk();
      if (IsNull()) {
        return false;
      }
      // Skip whatever block tail there is, we don't allow pointing in the
      // middle of a block.
      mOffsetInChunk = mChunk->OffsetFirstBlock();
    }
  }

  [[nodiscard]] Byte ReadByte() {
    MOZ_ASSERT(!IsNull());
    MOZ_ASSERT(mOffsetInChunk < mChunk->OffsetPastLastBlock());
    Byte byte = mChunk->ByteAt(mOffsetInChunk);
    if (MOZ_UNLIKELY(++mOffsetInChunk == mChunk->OffsetPastLastBlock())) {
      Adjust();
    }
    return byte;
  }

  // Read and skip a ULEB128-encoded size.
  // 0 means failure (0-byte entries are not allowed.)
  // Note that this doesn't guarantee that there are actually that many bytes
  // available to read! (EntryReader() below may gracefully fail.)
  [[nodiscard]] Length ReadEntrySize() {
    ULEB128Reader<Length> reader;
    if (IsNull()) {
      return 0;
    }
    for (;;) {
      const bool isComplete = reader.FeedByteIsComplete(ReadByte());
      if (MOZ_UNLIKELY(IsNull())) {
        // End of chunks, so there's no actual entry after this anyway.
        return 0;
      }
      if (MOZ_LIKELY(isComplete)) {
        if (MOZ_UNLIKELY(reader.Value() > mChunk->BufferBytes())) {
          // Don't allow entries larger than a chunk.
          return 0;
        }
        return reader.Value();
      }
    }
  }

  InChunkPointer& operator+=(Length aLength) {
    MOZ_ASSERT(!IsNull());
    mOffsetInChunk += aLength;
    Adjust();
    return *this;
  }

  [[nodiscard]] ProfileBufferEntryReader EntryReader(Length aLength) {
    if (IsNull() || aLength == 0) {
      return ProfileBufferEntryReader();
    }

    MOZ_ASSERT(mOffsetInChunk < mChunk->OffsetPastLastBlock());

    // We should be pointing at the entry, past the entry size.
    const ProfileBufferIndex entryIndex = GlobalRangePosition();
    // Verify that there's enough space before for the size (starting at index
    // 1 at least).
    MOZ_ASSERT(entryIndex >= 1u + ULEB128Size(aLength));

    const Length remaining = mChunk->OffsetPastLastBlock() - mOffsetInChunk;
    Span<const Byte> mem0 = mChunk->BufferSpan();
    mem0 = mem0.From(mOffsetInChunk);
    if (aLength <= remaining) {
      // Move to the end of this block, which could make this null if we have
      // reached the end of all buffers.
      *this += aLength;
      return ProfileBufferEntryReader(
          mem0.To(aLength),
          // Block starts before the entry size.
          ProfileBufferBlockIndex::CreateFromProfileBufferIndex(
              entryIndex - ULEB128Size(aLength)),
          // Block ends right after the entry (could be null for last entry).
          ProfileBufferBlockIndex::CreateFromProfileBufferIndex(
              GlobalRangePosition()));
    }

    // We need to go to the next chunk for the 2nd part of this block.
    GoToNextChunk();
    if (IsNull()) {
      return ProfileBufferEntryReader();
    }

    Span<const Byte> mem1 = mChunk->BufferSpan();
    const Length tail = aLength - remaining;
    MOZ_ASSERT(tail <= mChunk->BufferBytes());
    MOZ_ASSERT(tail == mChunk->OffsetFirstBlock());
    // We are in the correct chunk, move the offset to the end of the block.
    mOffsetInChunk = tail;
    // And adjust as needed, which could make this null if we have reached the
    // end of all buffers.
    Adjust();
    return ProfileBufferEntryReader(
        mem0, mem1.To(tail),
        // Block starts before the entry size.
        ProfileBufferBlockIndex::CreateFromProfileBufferIndex(
            entryIndex - ULEB128Size(aLength)),
        // Block ends right after the entry (could be null for last entry).
        ProfileBufferBlockIndex::CreateFromProfileBufferIndex(
            GlobalRangePosition()));
  }

  [[nodiscard]] bool IsNull() const { return !mChunk; }

  [[nodiscard]] bool operator==(const InChunkPointer& aOther) const {
    if (IsNull() || aOther.IsNull()) {
      return IsNull() && aOther.IsNull();
    }
    return mChunk == aOther.mChunk && mOffsetInChunk == aOther.mOffsetInChunk;
  }

  [[nodiscard]] bool operator!=(const InChunkPointer& aOther) const {
    return !(*this == aOther);
  }

  [[nodiscard]] Byte operator*() const {
    MOZ_ASSERT(!IsNull());
    MOZ_ASSERT(mOffsetInChunk < mChunk->OffsetPastLastBlock());
    return mChunk->ByteAt(mOffsetInChunk);
  }

  InChunkPointer& operator++() {
    MOZ_ASSERT(!IsNull());
    MOZ_ASSERT(mOffsetInChunk < mChunk->OffsetPastLastBlock());
    if (MOZ_UNLIKELY(++mOffsetInChunk == mChunk->OffsetPastLastBlock())) {
      mOffsetInChunk = 0;
      GoToNextChunk();
      Adjust();
    }
    return *this;
  }

 private:
  void GoToNextChunk() {
    MOZ_ASSERT(!IsNull());
    const ProfileBufferIndex expectedNextRangeStart =
        mChunk->RangeStart() + mChunk->BufferBytes();

    mChunk = mChunk->GetNext();
    if (!mChunk) {
      // Reached the end of the current chunk group, try the next one (which
      // may be null too, especially on the 2nd try).
      mChunk = mNextChunkGroup;
      mNextChunkGroup = nullptr;
    }

    if (mChunk && mChunk->RangeStart() == 0) {
      // Reached a chunk without a valid (non-null) range start, assume there
      // are only unused chunks from here on.
      mChunk = nullptr;
    }

    MOZ_ASSERT(!mChunk || mChunk->RangeStart() == expectedNextRangeStart,
               "We don't handle discontinuous buffers (yet)");
    // Non-DEBUG fallback: Stop reading past discontinuities.
    // (They should be rare, only happening on temporary OOMs.)
    // TODO: Handle discontinuities (by skipping over incomplete blocks).
    if (mChunk && mChunk->RangeStart() != expectedNextRangeStart) {
      mChunk = nullptr;
    }
  }

  // We want `InChunkPointer` to always point at a valid byte (or be null).
  // After some operations, `mOffsetInChunk` may point past the end of the
  // current `mChunk`, in which case we need to adjust our position to be inside
  // the appropriate chunk. E.g., if we're 10 bytes after the end of the current
  // chunk, we should end up at offset 10 in the next chunk.
  // Note that we may "fall off" the last chunk and make this `InChunkPointer`
  // effectively null.
  void Adjust() {
    while (mChunk && mOffsetInChunk >= mChunk->OffsetPastLastBlock()) {
      // TODO: Try to adjust offset between chunks relative to mRangeStart
      // differences. But we don't handle discontinuities yet.
      if (mOffsetInChunk < mChunk->BufferBytes()) {
        mOffsetInChunk -= mChunk->BufferBytes();
      } else {
        mOffsetInChunk -= mChunk->OffsetPastLastBlock();
      }
      GoToNextChunk();
    }
  }

  // Check if the current position is likely to point at a valid block.
  // (Size should be reasonable, and block should fully fit inside buffer.)
  // MOZ_ASSERTs on failure, to catch incorrect uses of block indices (which
  // should only point at valid blocks if still in range). Non-asserting build
  // fallback should still be handled.
  [[nodiscard]] bool ShouldPointAtValidBlock() const {
    if (IsNull()) {
      // Pointer is null, no blocks here.
      MOZ_ASSERT(false, "ShouldPointAtValidBlock - null pointer");
      return false;
    }
    // Use a copy, so we don't modify `*this`.
    InChunkPointer pointer = *this;
    // Try to read the entry size.
    Length entrySize = pointer.ReadEntrySize();
    if (entrySize == 0) {
      // Entry size of zero means we read 0 or a way-too-big value.
      MOZ_ASSERT(false, "ShouldPointAtValidBlock - invalid size");
      return false;
    }
    // See if the last byte of the entry is still inside the buffer.
    pointer += entrySize - 1;
    MOZ_ASSERT(!pointer.IsNull(),
               "ShouldPointAtValidBlock - past end of buffer");
    return !pointer.IsNull();
  }

  const ProfileBufferChunk* mChunk;
  const ProfileBufferChunk* mNextChunkGroup;
  Length mOffsetInChunk;
};

}  // namespace mozilla::profiler::detail

#endif  // ProfileChunkedBufferDetail_h