54 Dynamic B+Tree alignment

Alignment

Alignment rules are platform dependent. See The Lost Art of Structure Packing by Eric S. Raymond. However, most platforms follow the same notion of self-alignment - the data types short, int, long, float, double and pointers follow the rule that a variable of size N must be aligned on an N byte boundary.

Ceda/cxPersistStore/BPlusTree2.h appears to have an issue with allowing unaligned memory accesses, which can cause a SIGBUS signal to be raised on ARMv7.

Ceda/cxPersistStore/BPlusTree2.h defines ceda::pair<T1,T2> which is like std::pair except it is packed.

#pragma pack(push,1)
template <typename T1,typename T2>
struct pair
{
    T1 first;
    T2 second;
};
#pragma pack(pop)

This is asking for trouble on platforms like ARMv7.

Alignment property of a data type

The size of a data type is insufficient information to tell you how padding is applied when it is used in other structures. This is illustrated by the following code involving a std::pair<char,T> for various T where sizeof(T) is always 8, and yet the size of the pair varies:

struct F
{
    int a;
    int b;
};

template<typename T>
void ShowAlignment(const char* msg)
{
    using P = std::pair<char,T>;
    Tracer() << msg
             << " : size = " << sizeof(T)
             << " size of pair = " << sizeof(P)
             << " offset = " << offsetof(P,second) << "\n";
}

void CheckAlignment()
{
    using namespace ceda;
    ShowAlignment<std::array<int8 ,8>>("std::array<int8,8>");
    ShowAlignment<std::array<int16,4>>("std::array<int16,4>");
    ShowAlignment<std::array<int32,2>>("std::array<int32,2>");
    ShowAlignment<std::array<int64,1>>("std::array<int64,1>");
    ShowAlignment<std::array<F,1>>("std::array<F,1>");
}

The output on x64-windows platform is:

std::array<int8,8>  : size = 8   size of pair = 9    offset = 1
std::array<int16,4> : size = 8   size of pair = 10   offset = 2
std::array<int32,2> : size = 8   size of pair = 12   offset = 4
std::array<int64,1> : size = 8   size of pair = 16   offset = 8
std::array<F,1>     : size = 8   size of pair = 12   offset = 4

To model this, we need TypeOps to have an additional field called 'alignment'. The alignment of T equals the offset of T in std::pair<char,T>, and typical values are 1,2,4 or 8.

Layout calculation

Let types T1 and T2 have given sizes and alignments (provided by their TypeOps). We want to calculate the layout of std::pair<T1,T2>.

The following is assumed:

• The offset of the first member of type T1 is zero.
• The offset of the second member of type T2 equals the smallest integer o where both
  • o >= sizeof(T1)
  • o % alignment(T2) == 0
• The alignment of the pair is given by a = max( alignment(T1), alignment(T2) )
• The size of the pair is the smallest integer s satisfying both
  • s >= o + sizeof(T2)
  • s % a == 0

Let f(m,a) = (k==0) ? m : (m+a-k) where k = m % a

Then
    o = f( sizeof(T1), alignment(T2) )
    a = max( alignment(T1), alignment(T2) )
    s = f( o + sizeof(T2), a )