38.2 Challis algorithm

The Challis algorithm is used for the information in the root block of the LSS which is updated during each check point.

Consider that we need to atomically write some data to a fixed check point location on disk. One approach is to duplicate the data in two different places and write them in strict alternation. Each mirrored copy (or division) begins and ends with a modification sequence number (MSN). This serves two purposes:

  1. On recovery, if the start and end MSNs of a division are different then it indicates that a crash occurred in the middle of writing that division, so it is corrupt and must be ignored. For extra confidence, it is also possible to compute a checksum such as a CRC and store this in each division.
  2. If both divisions are valid, then we pick the one with the largest MSN, since this is the most up to date.

This is called Challis' algorithm.

When writing a division it is vital that error codes are checked to be confident that the division is written correctly. Otherwise it is possible that both divisions become invalid, and that may be disastrous.

Representation of each division on disk

The following grammar defines the layout of a division on disk. 


    <uint32> = (little endian binary representation using 4 octets)
    <int32> =  (little endian binary representation using 4 octets)

    <crc32> = <uint32>
    <msn>   = <int32>
    <zero-padding>   = 0x00 *

    <division> = <crc32> <msn> <payload> <zero-padding> <msn>

Note that the representation is the same on all platforms (and involves little endian representation of integers).

It is assumed the total size of the division is statically defined, therefore zero padding of the payload may be required. The trailing MSN always occupies the last 4 octets of the division.

The 32 bit CRC is calculated on all the octets in the division apart from the first 4 octets.

Buffers in system memory

When the LSS root block is read into a buffer in system memory (in a similar manner to using fread), the buffer corresponds exactly to the bytes on disk. So on a big endian machine, the buffer in memory is using little endian format, just as in the file. For example this is the case for the recorded CRC and the leading and trailing MSNs.

This is the same when a buffer is prepared in memory, ready to be written to disk.

No longer using packed structures

Originally the implementation used data structures which exactly match the representation on disk. However that approach has the following disadvantages:

  • It requires #pragma pack(push,1) directives, and that raises questions about unaligned memory access on some architectures such as ARMv7.
  • The memory footprint is increased when the disk representation is greater than what is needed in memory - such as typically in the case where there are mirrored copies, and the copies may be padded with zeros
  • Even if unaligned memory access is supported by the hardware, there may be performance issues
  • We don't get the little endian versus big endian byte swapping for platform independent representations of ints and floats on disk. We want to allow LSS files to be written on one machine and read on another.

It is typically best to work with the native platform dependent representation in system memory and only use the platform independent representation in the buffers which are read/written from disk.

CRC

The CRC32 on each division is calculated on the buffer in memory which starts with the leading MSN (msn1) and ending with the trailing MSN (msn2). Note that the CRC is inclusive of the leading and trailing MSNs.

Having both the buffer in memory as well as platform dependent data structures representing the same information makes the design more complex to understand. It is better to only use a buffer when it is needed. This happens when:

  • Reading the rootblock - this involves a single 64kB read.
  • Writing the rootblock when the store is being created for the first time.
  • Writing the dynamic header just after the store is opened and just before it is closed, to indicate whether a graceful shutdown has occurred.
  • Write a Challis division during a check point

The two divisions are identified by an index which can be 0 or 1.

ChallisDivisionInfo

The following data structure holds information about a single division: 


struct ChallisDivisionInfo
{
    CRC32 file_crc = 0;     // The CRC recorded in the file
    CRC32 calc_crc = 0;     // The CRC calculated from the data in the file
    ModSeqNum msn1 = 0;     // The leading MSN
    ModSeqNum msn2 = 0;     // The trailing MSN
};

Consider that the LSS has just been opened and the 64kB root block has been read from disk into a buffer in memory. For a given division we can obtain a pointer to the start of the division in system memory.

The following method of ChallisDivisionInfo can be used to initialise all four members from a division loaded into a buffer in system memory. 


void ReadFromFile(const octet_t* pDivision, ssize_t divisionSize);

Writing to the LSS

The following methods of interface IRAS are relevant to writing the root block. Note unfortunately that this API implies synchronous I/O and memory copying. We won't be fixing that today! It is important to allocate the buffer with the provided allocation function. 


typedef int64 RASAddress;

struct IRAS
{
    // Allocate memory blocks that are suitable for Read() and Write() calls because they are aligned
    // on sector boundaries.
    virtual void* AllocateMemoryBlock(int size) = 0;
    virtual void FreeMemoryBlock(void* p) = 0;

    // Write a buffer to the store.  The size of the file will automatically grow if necessary
    // to include the given range.
    // Throws exceptions on error
    // Note that write caching is not employed.  The data is flushed synchronously by this function
    virtual void Write(const void* buffer, RASAddress offset, int numBytes) = 0;

    ...
};

Root block sections


    const int ROOT_BLOCK_STATIC_HEADER_SIZE = 1024;
    const int ROOT_BLOCK_DYNAMIC_HEADER_SIZE = 1024;
    const int ROOT_BLOCK_HEADER_SIZE = ROOT_BLOCK_STATIC_HEADER_SIZE + ROOT_BLOCK_DYNAMIC_HEADER_SIZE;

    const int ROOT_BLOCK_DIVISION_SIZE = 31 * 1024;

    // The root block consists of the header plus two divisions.  With the above values this is
    // 1k + 1k + 31K + 31k = 64k
    const int ROOT_BLOCK_SIZE = ROOT_BLOCK_HEADER_SIZE + (2 * ROOT_BLOCK_DIVISION_SIZE);

    root block =
    [
        static root header (1kB)
        dynamic root header (1kB)
        root block division 0 (31 kB)
        root block division 1 (31 kB)
    ]

The following function gets the offset into the file for the given division. 


// division must be 0 or 1.
inline ssize_t GetDivisionOffset(int division)
{
    cxAssert(division == 0 || division == 1);
    return ROOT_BLOCK_HEADER_SIZE + division * ROOT_BLOCK_DIVISION_SIZE;
}

Writing a new division

It is assumed the two divisions in the root block can be written independently, so writing the next division doesn't upset the previous valid division.

In order to write a new Challis division we need to know which division. This is determined by the least significant bit of the MSN.

With existing compile time settings the root block is 64kB, with a 2kB header. Division 0 is offset 2kB and division 1 is offset 33kB. 


// rootBlockBuffer is the pointer to 64kB buffer used for reading and writing the root block or parts thereof
void WriteDivision(IRAS& ras, int32 msn, octet_t* rootBlockBuffer)
{
    int division = (msn & 1);   // 0 or 1
    RASAddress divisionOffset = GetDivisionOffset(division);

    octet_t* buffer = rootBlockBuffer + divisionOffset;

    // Leave space for the CRC
    octet_t* start = buffer + sizeof(CRC32);

    OutputArchive ar(start);
    ar << msn;
    SerialisePayloadOfDivision(ar);
    ar << msn;
    cxAssert(ar-buffer == ROOT_BLOCK_DIVISION_SIZE);

    // Fill in the CRC
    Serialise(buffer, CalculateCRC32(start, ar-start));

    ras.Write(buffer, divisionOffset, ROOT_BLOCK_DIVISION_SIZE);
}

Validating a division

When the LSS is opened we need to check the two divisions to see whether they are valid. If neither is valid we are stuffed. If only one is valid then that is the one we pick. If both are valid we pick the one with the highest MSN.

We want a function which validates a given division, and either returns -1 if invalid, or else the MSN 


// rootBlockBuffer is the pointer to 64kB buffer used for reading the root block
int32 ValidateDivision(const octet_t* rootBlockBuffer, int division)
{
    cxAssert(division == 0 || division == 1);
    RASAddress divisionOffset = GetDivisionOffset(division);

    octet_t* buffer = rootBlockBuffer + divisionOffset;
    CRC32 crc;
    int32 msn1, msn2;
    InputArchive ar(buffer);
    ar >> crc >> msn1;
    ar.Skip( ROOT_BLOCK_DIVISION_SIZE - sizeof(CRC32) - 2*sizeof(MSN) );
    ar >> msn2;
    cxAssert(ar-buffer == ROOT_BLOCK_DIVISION_SIZE);

    if (msn1 < 0)
        return -1;  // Invalid MSN

    if (msn1 != msn2)
        return -1;  // Leading and trailing MSNs are unequal

    if (crc != CalculateCRC32(buffer + sizeof(CRC32), ROOT_BLOCK_DIVISION_SIZE - sizeof(CRC32)))
        return -1;  // Invalid because CRC is wrong

    return msn1;
}

References

Challis, M. F. "Database Consistency and Integrity in a Multi-User Environment", Databases: Improving Usability and Responsiveness, Academic Press, pp. 245-270, 1978.

Code


using ModSeqNum = int32;

void WriteChallisDivisionInfo(octet_t* pDivision, ssize_t divisionSize, ModSeqNum msn);

struct ChallisDivisionInfo
{
    bool IsValid() const { return msn1 >= 0 && msn1 == msn2 && file_crc == calc_crc; }
    void WriteDiagnosticInfo(xostream& os) const;
    void ReadFromFile(const octet_t* pDivision, ssize_t divisionSize);
    ModSeqNum GetMsn() const { return IsValid() ? msn1 : -1; }
    static constexpr ssize_t PayLoadSize(ssize_t divisionSize) { return divisionSize - sizeof(CRC32) - 2*sizeof(ModSeqNum); }
    static constexpr ssize_t PayLoadOffset() { return sizeof(CRC32) + sizeof(ModSeqNum); }

    CRC32 file_crc = 0;     // The CRC recorded in the file
    CRC32 calc_crc = 0;     // The CRC calculated from the data in the file
    ModSeqNum msn1 = 0;     // The leading MSN
    ModSeqNum msn2 = 0;     // The trailing MSN
};

struct ChallisDivisionPair
{
    void WriteDiagnosticInfo(xostream& os) const;

    // Returns MSN for the latest valid version, or -1 if neither version is valid
    // if useMostUpToDateDivision is false then try to return the second latest version
    ModSeqNum GetMSNOfLatestValidVersion(bool useMostUpToDateDivision) const;

    ChallisDivisionInfo divisions[2];
};