QuickCppLib 0.10
Eliminate all the tedious hassle when making state-of-the-art C++ 14 - 23 libraries!
Loading...
Searching...
No Matches
quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType > Class Template Reference

A space packed stack backtrace letting you store twice or more stack frames in the same space. More...

#include "packed_backtrace.hpp"

Inheritance diagram for quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType >:
quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, sizeof(void *)>

Public Types

using value_type
 The type stored in the container.
using const_value_type
 The const type stored in the container.
using size_type
 The size type.
using difference_type
 The difference type.
using reference
 The reference type.
using const_reference
 The const reference type.
using pointer
 The pointer type.
using const_pointer
 The const pointer type.
using const_iterator
 The const iterator type.
using reverse_iterator
 The reverse iterator type.
using const_reverse_iterator
 The const reverse iterator type.

Public Member Functions

 packed_backtrace (span::span< const char > storage)
 Construct a packed backtrace view, parsing the given byte storage.
 packed_backtrace (span::span< char > storage, std::nullptr_t)
 Construct a packed backtrace view, not parsing the given byte storage.
 packed_backtrace (const packed_backtrace &)=default
 Default copy constructor.
 packed_backtrace (packed_backtrace &&)=default
 Default move constructor.
packed_backtrace & operator= (const packed_backtrace &)=default
 Default copy assignment.
packed_backtrace & operator= (packed_backtrace &&)=default
 Default move assignment.
bool empty () const noexcept
 Returns true if the index is empty.
size_type size () const noexcept
 Returns the number of items in the backtrace.
size_type max_size () const noexcept
 Returns the maximum number of items in the backtrace.
iterator begin () noexcept
 Returns an iterator to the first item in the backtrace.
const_iterator cbegin () const noexcept
 Returns an iterator to the first item in the backtrace.
iterator end () noexcept
 Returns an iterator to the item after the last in the backtrace.
const_iterator cend () const noexcept
 Returns an iterator to the item after the last in the backtrace.
value_type operator[] (size_type i) const noexcept
 Returns the specified element, unchecked.
value_type at (size_type i) const
 Returns the specified element, checked.
void swap (packed_backtrace &o) noexcept
 Swaps with another instance.
void assign (span::span< const_value_type > input) noexcept
 Assigns a raw stack backtrace to the packed storage.

Detailed Description

template<class FramePtrType = void *>
class quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType >

A space packed stack backtrace letting you store twice or more stack frames in the same space.

Template Parameters
FramePtrTypeThe type each stack backtrace frame ought to be represented as.
Note
Use make_packed_backtrace() to create one of these from a raw backtrace. Construct an instance on a byte span to load in the packed data so you can parse it.

64 bit address stack backtraces tend to waste a lot of storage which can be a problem when storing lengthy backtraces. Most 64 bit architectures only use the first 43 bits of address space wasting 2.5 bytes per entry, plus stack backtraces tend to be within a few megabytes and even kilobytes from one another. Intelligently packing the bits based on this knowledge can double or more the number of items you can store for a given number of bytes with virtually no runtime overhead, unlike compression.

On 32 bit architectures this class simply stores the stack normally, but otherwise works the same.

Performance:

  • GCC 7.1 on x64 3.1Ghz Skylake: Can construct and read 106188139 packed stacktraces/sec
  • VS2017 on x64 3.1Ghz Skylake: Can construct and read 79755133 packed stacktraces/sec

The 64-bit coding scheme is quite straightforward:

  • Top bits are 11 when it's bits 63-43 of a 64 bit absolute address (3 bytes)
  • Top bits are 10 when it's bits 42-21 of a 64 bit absolute address (3 bytes)
    • Note that this resets bits 20-0 to 0x100000 (bit 20 set, bits 19-0 cleared)
  • Top bits are 01 when it's a 22 bit offset from previous (3 bytes) (+- 0x400000, 4Mb)
  • Top bits are 00 when it's a 14 bit offset from previous (2 bytes) (+- 0x4000, 16Kb)
  • Potential improvement: 12 to 18 items in 40 bytes instead of 5 items

Sample 1:

0000 07fe fd4e 10ac - 6 bytes
0000 07fe f48b ffc7 - 3 bytes
0000 07fe f48b ff70 - 2 bytes
0000 07fe f48b fe23 - 2 bytes
0000 07fe f48d 51d8 - 3 bytes
0000 07fe f499 5249 - 3 bytes
0000 07fe f48a ef28 - 3 bytes
0000 07fe f48a ecc9 - 2 bytes
0000 07fe f071 244c - 6 bytes
0000 07fe f071 11b5 - 2 bytes
0000 07ff 0015 0acf - 6 bytes
0000 07ff 0015 098c - 2 bytes (40 bytes, 12 items, usually 96 bytes, 58% reduction)

Sample 2:

0000003d06e34950 - 6 bytes
0000000000400bcd - 6 bytes
0000000000400bf5 - 2 bytes
0000003d06e1ffe0 - 6 bytes
00000000004009f9 - 6 bytes (26 bytes, 5 items, usually 40 bytes, 35% reduction)

Member Typedef Documentation

◆ value_type

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::value_type
inherited

The type stored in the container.

◆ const_value_type

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::const_value_type
inherited

The const type stored in the container.

◆ size_type

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::size_type
inherited

The size type.

◆ difference_type

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::difference_type
inherited

The difference type.

◆ reference

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::reference
inherited

The reference type.

◆ const_reference

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::const_reference
inherited

The const reference type.

◆ pointer

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::pointer
inherited

The pointer type.

◆ const_pointer

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::const_pointer
inherited

The const pointer type.

◆ const_iterator

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::const_iterator
inherited

The const iterator type.

◆ reverse_iterator

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::reverse_iterator
inherited

The reverse iterator type.

◆ const_reverse_iterator

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::const_reverse_iterator
inherited

The const reverse iterator type.

Constructor & Destructor Documentation

◆ packed_backtrace() [1/4]

template<class FramePtrType = void *>
quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType >::packed_backtrace ( span::span< const char > storage)
inlineexplicit

Construct a packed backtrace view, parsing the given byte storage.

556 : base(storage)
557 {
558 }
A space packed stack backtrace letting you store twice or more stack frames in the same space.
Definition packed_backtrace.hpp:550

◆ packed_backtrace() [2/4]

template<class FramePtrType = void *>
quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType >::packed_backtrace ( span::span< char > storage,
std::nullptr_t  )
inlineexplicit

Construct a packed backtrace view, not parsing the given byte storage.

561 : base(storage, nullptr)
562 {
563 }

◆ packed_backtrace() [3/4]

template<class FramePtrType = void *>
quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType >::packed_backtrace ( const packed_backtrace< FramePtrType > & )
default

Default copy constructor.

◆ packed_backtrace() [4/4]

template<class FramePtrType = void *>
quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType >::packed_backtrace ( packed_backtrace< FramePtrType > && )
default

Default move constructor.

Member Function Documentation

◆ operator=() [1/2]

template<class FramePtrType = void *>
packed_backtrace & quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType >::operator= ( const packed_backtrace< FramePtrType > & )
default

Default copy assignment.

◆ operator=() [2/2]

template<class FramePtrType = void *>
packed_backtrace & quickcpplib::_xxx::packed_backtrace::packed_backtrace< FramePtrType >::operator= ( packed_backtrace< FramePtrType > && )
default

Default move assignment.

◆ empty()

bool quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::empty ( ) const
inlinenoexceptinherited

Returns true if the index is empty.

371{ return _storage.empty(); }
bool empty() const noexcept
Returns true if the index is empty.
Definition packed_backtrace.hpp:371

◆ size()

size_type quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::size ( ) const
inlinenoexceptinherited

Returns the number of items in the backtrace.

373{ return _count; }

◆ max_size()

size_type quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::max_size ( ) const
inlinenoexceptinherited

Returns the maximum number of items in the backtrace.

375{ return _count; }

◆ begin()

iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::begin ( )
inlinenoexceptinherited

Returns an iterator to the first item in the backtrace.

377{ return iterator(this); }

◆ cbegin()

const_iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::cbegin ( ) const
inlinenoexceptinherited

Returns an iterator to the first item in the backtrace.

381{ return iterator(this); }

◆ end()

iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::end ( )
inlinenoexceptinherited

Returns an iterator to the item after the last in the backtrace.

383{ return iterator(); }

◆ cend()

const_iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::cend ( ) const
inlinenoexceptinherited

Returns an iterator to the item after the last in the backtrace.

387{ return iterator(); }

◆ operator[]()

value_type quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::operator[] ( size_type i) const
inlinenoexceptinherited

Returns the specified element, unchecked.

390 {
391 uintptr_type out = 0;
392 size_t idx = 0;
393 for(size_type n = 0; n <= i; n++)
394 {
395 if(!_decode(out, idx))
396 return nullptr;
397 }
398 return reinterpret_cast<value_type>(out);
399 }

◆ at()

value_type quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::at ( size_type i) const
inlineinherited

Returns the specified element, checked.

402 {
403 uintptr_type out = 0;
404 size_t idx = 0;
405 for(size_type n = 0; n <= i; n++)
406 {
407 if(!_decode(out, idx))
408 {
409 abort(); // out of range
410 }
411 }
412 return reinterpret_cast<value_type>(out);
413 }

◆ swap()

void quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::swap ( packed_backtrace< void *, sizeof(void *)> & o)
inlinenoexceptinherited

Swaps with another instance.

416 {
417 using std::swap;
418 swap(_storage, o._storage);
419 swap(_count, o._count);
420 }
void swap(packed_backtrace &o) noexcept
Definition packed_backtrace.hpp:415

◆ assign()

void quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< void *, FrameTypeSize >::assign ( span::span< const_value_type > input)
inlinenoexceptinherited

Assigns a raw stack backtrace to the packed storage.

424 {
425 uintptr_type out = 0;
426 size_t idx = 0;
427 memset(_storage.data(), 0, _storage.size());
428 _count = 0;
429 for(const auto &_i : input)
430 {
431 size_t startidx = idx;
432 uintptr_type i = reinterpret_cast<uintptr_type>(_i);
434 if((out & bits63_43) != delta)
435 {
436 if(idx > _storage.size() - 3)
437 return;
438 // std::cout << "For entry " << _i << " encoding bits 63-43: " << (void *) delta << std::endl;
439 _storage[idx++] = 0xc0 | ((delta >> 59) & 0x3f);
440 _storage[idx++] = (delta >> 51) & 0xff;
441 _storage[idx++] = (delta >> 43) & 0xff;
442 out &= bits42_0;
443 out |= delta;
444 }
445 delta = i & bits42_21;
446 if((out & bits42_21) != delta)
447 {
448 if(idx > _storage.size() - 3)
449 {
450 memset(_storage.data() + startidx, 0, idx - startidx);
451 return;
452 }
453 // std::cout << "For entry " << _i << " encoding bits 42-21: " << (void *) delta << std::endl;
454 _storage[idx++] = 0x80 | ((delta >> 37) & 0x3f);
455 _storage[idx++] = (delta >> 29) & 0xff;
456 _storage[idx++] = (delta >> 21) & 0xff;
457 out &= bits63_43;
458 out |= bit20;
459 out |= delta;
460 }
461 if(i - out >= (1 << 13) && out - i >= (1 << 13))
462 {
463 if(idx > _storage.size() - 3)
464 {
465 memset(_storage.data() + startidx, 0, idx - startidx);
466 return;
467 }
468 delta = static_cast<uintptr_type>(i - out);
469 // std::cout << "For entry " << _i << " with diff " << (intptr_t) delta << " encoding three byte delta: " << (void *) delta << std::endl;
470 _storage[idx++] = 0x40 | ((delta >> 16) & 0x3f);
471 _storage[idx++] = (delta >> 8) & 0xff;
472 _storage[idx++] = (delta >> 0) & 0xff;
473 out = i;
474 }
475 else
476 {
477 if(idx > _storage.size() - 2)
478 {
479 memset(_storage.data() + startidx, 0, idx - startidx);
480 return;
481 }
482 delta = static_cast<uintptr_type>(i - out);
483 // std::cout << "For entry " << _i << " with diff " << (intptr_t) delta << " encoding two byte delta: " << (void *) delta << std::endl;
484 _storage[idx++] = (delta >> 8) & 0x3f;
485 _storage[idx++] = (delta >> 0) & 0xff;
486 out = i;
487 }
488 _count++;
489 }
490 }
size_type size() const noexcept
Returns the number of items in the backtrace.
Definition packed_backtrace.hpp:373

The documentation for this class was generated from the following file: