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 >:

Public Types
using	value_type = FramePtrType
	The type stored in the container.
using	const_value_type = typename detail::constify< FramePtrType >::type
	The const type stored in the container.
using	size_type = size_t
	The size type.
using	difference_type = ptrdiff_t
	The difference type.
using	reference = FramePtrType
	The reference type.
using	const_reference = const FramePtrType
	The const reference type.
using	pointer = FramePtrType *
	The pointer type.
using	const_pointer = const FramePtrType *
	The const pointer type.
using	const_iterator = iterator
	The const iterator type.
using	reverse_iterator = std::reverse_iterator< iterator >
	The reverse iterator type.
using	const_reverse_iterator = std::reverse_iterator< const_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	begin () const 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	end () const 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

FramePtrType

The 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) (+- 0x40`0000, 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

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::value_type = FramePtrType

inherited

The type stored in the container.

const_value_type

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::const_value_type = typename detail::constify<FramePtrType>::type

inherited

The const type stored in the container.

size_type

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::size_type = size_t

inherited

The size type.

difference_type

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::difference_type = ptrdiff_t

inherited

The difference type.

reference

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::reference = FramePtrType

inherited

The reference type.

const_reference

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::const_reference = const FramePtrType

inherited

The const reference type.

pointer

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::pointer = FramePtrType *

inherited

The pointer type.

const_pointer

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::const_pointer = const FramePtrType *

inherited

The const pointer type.

const_iterator

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::const_iterator = iterator

inherited

The const iterator type.

reverse_iterator

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::reverse_iterator = std::reverse_iterator<iterator>

inherited

The reverse iterator type.

const_reverse_iterator

template<class FramePtrType , size_t FrameTypeSize>

using quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::const_reverse_iterator = std::reverse_iterator<const_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.

        : base(storage)
    {
    }

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.

        : base(storage, nullptr)
    {
    }

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()

template<class FramePtrType , size_t FrameTypeSize>

bool quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::empty ( ) const

inlinenoexceptinherited

Returns true if the index is empty.

{ return _storage.empty(); }

size()

template<class FramePtrType , size_t FrameTypeSize>

size_type quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::size ( ) const

inlinenoexceptinherited

Returns the number of items in the backtrace.

{ return _count; }

max_size()

template<class FramePtrType , size_t FrameTypeSize>

size_type quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::max_size ( ) const

inlinenoexceptinherited

Returns the maximum number of items in the backtrace.

{ return _count; }

begin() [1/2]

template<class FramePtrType , size_t FrameTypeSize>

iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::begin ( )

inlinenoexceptinherited

Returns an iterator to the first item in the backtrace.

{ return iterator(this); }

begin() [2/2]

template<class FramePtrType , size_t FrameTypeSize>

const_iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::begin ( ) const

inlinenoexceptinherited

Returns an iterator to the first item in the backtrace.

{ return iterator(this); }

cbegin()

template<class FramePtrType , size_t FrameTypeSize>

const_iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::cbegin ( ) const

inlinenoexceptinherited

Returns an iterator to the first item in the backtrace.

{ return iterator(this); }

end() [1/2]

template<class FramePtrType , size_t FrameTypeSize>

iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::end ( )

inlinenoexceptinherited

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

{ return iterator(); }

end() [2/2]

template<class FramePtrType , size_t FrameTypeSize>

const_iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::end ( ) const

inlinenoexceptinherited

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

{ return iterator(); }

cend()

template<class FramePtrType , size_t FrameTypeSize>

const_iterator quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::cend ( ) const

inlinenoexceptinherited

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

{ return iterator(); }

operator[]()

template<class FramePtrType , size_t FrameTypeSize>

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

inlinenoexceptinherited

Returns the specified element, unchecked.

      {
        uintptr_type out = 0;
        size_t idx = 0;
        for(size_type n = 0; n <= i; n++)
        {
          if(!_decode(out, idx))
            return nullptr;
        }
        return reinterpret_cast<value_type>(out);
      }

at()

template<class FramePtrType , size_t FrameTypeSize>

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

inlineinherited

Returns the specified element, checked.

      {
        uintptr_type out = 0;
        size_t idx = 0;
        for(size_type n = 0; n <= i; n++)
        {
          if(!_decode(out, idx))
          {
            abort();  // out of range
          }
        }
        return reinterpret_cast<value_type>(out);
      }

swap()

template<class FramePtrType , size_t FrameTypeSize>

void quickcpplib::_xxx::packed_backtrace::impl::packed_backtrace< FramePtrType, FrameTypeSize >::swap ( packed_backtrace< FramePtrType, FrameTypeSize > &  o )

inlinenoexceptinherited

Swaps with another instance.

      {
        using std::swap;
        swap(_storage, o._storage);
        swap(_count, o._count);
      }

assign()

template<class FramePtrType , size_t FrameTypeSize>

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

inlinenoexceptinherited

Assigns a raw stack backtrace to the packed storage.

      {
        uintptr_type out = 0;
        size_t idx = 0;
        memset(_storage.data(), 0, _storage.size());
        _count = 0;
        for(const auto &_i : input)
        {
          size_t startidx = idx;
          uintptr_type i = reinterpret_cast<uintptr_type>(_i);
          uintptr_type delta = i & bits63_43;
          if((out & bits63_43) != delta)
          {
            if(idx > _storage.size() - 3)
              return;
            // std::cout << "For entry " << _i << " encoding bits 63-43: " << (void *) delta << std::endl;
            _storage[idx++] = 0xc0 | ((delta >> 59) & 0x3f);
            _storage[idx++] = (delta >> 51) & 0xff;
            _storage[idx++] = (delta >> 43) & 0xff;
            out &= bits42_0;
            out |= delta;
          }
          delta = i & bits42_21;
          if((out & bits42_21) != delta)
          {
            if(idx > _storage.size() - 3)
            {
              memset(_storage.data() + startidx, 0, idx - startidx);
              return;
            }
            // std::cout << "For entry " << _i << " encoding bits 42-21: " << (void *) delta << std::endl;
            _storage[idx++] = 0x80 | ((delta >> 37) & 0x3f);
            _storage[idx++] = (delta >> 29) & 0xff;
            _storage[idx++] = (delta >> 21) & 0xff;
            out &= bits63_43;
            out |= bit20;
            out |= delta;
          }
          if(i - out >= (1 << 13) && out - i >= (1 << 13))
          {
            if(idx > _storage.size() - 3)
            {
              memset(_storage.data() + startidx, 0, idx - startidx);
              return;
            }
            delta = static_cast<uintptr_type>(i - out);
            // std::cout << "For entry " << _i << " with diff " << (intptr_t) delta << " encoding three byte delta: " << (void *) delta << std::endl;
            _storage[idx++] = 0x40 | ((delta >> 16) & 0x3f);
            _storage[idx++] = (delta >> 8) & 0xff;
            _storage[idx++] = (delta >> 0) & 0xff;
            out = i;
          }
          else
          {
            if(idx > _storage.size() - 2)
            {
              memset(_storage.data() + startidx, 0, idx - startidx);
              return;
            }
            delta = static_cast<uintptr_type>(i - out);
            // std::cout << "For entry " << _i << " with diff " << (intptr_t) delta << " encoding two byte delta: " << (void *) delta << std::endl;
            _storage[idx++] = (delta >> 8) & 0x3f;
            _storage[idx++] = (delta >> 0) & 0xff;
            out = i;
          }
          _count++;
        }
      }

---

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

• include/quickcpplib/packed_backtrace.hpp