path: root/src/testhash.c

/**

Copyright (c) Scott Gasch

Module Name:

    testhash.c

Abstract:

    Test of the main hash table code.

Author:

    Scott Gasch ([email protected]) 19 Oct 2004

Revision History:

**/

#ifdef TEST
#include "chess.h"

extern UCHAR g_cDirty;

#define CONVERT_HASH_DEPTH_TO_SEARCH_DEPTH(x) \
    ASSERT(((x) & 0xffffff00) == 0); \
    (x) <<= 4

FLAG 
SanityCheckHashEntry(HASH_ENTRY *p)
/**

Routine description:

    Make sure a hash table entry looks valid.

Parameters:

    HASH_ENTRY *p

Return value:

    FLAG

**/
{
    ULONG uDepth;

    if (p->u64Sig == 0)
    {
        if ((p->mv.uMove != 0) ||
            (p->uDepth != 0) ||
            (p->bvFlags != 0) ||
            (p->iValue != 0))
        {
            ASSERT(FALSE);
            return(FALSE);
        }
    }
    else
    {
        uDepth = p->uDepth;
        CONVERT_HASH_DEPTH_TO_SEARCH_DEPTH(uDepth);
        if (!IS_VALID_DEPTH(uDepth))
        {
            ASSERT(FALSE);
            return(FALSE);
        }

        switch(p->bvFlags & HASH_FLAG_VALID_BOUNDS)
        {
            case HASH_FLAG_LOWER:
            case HASH_FLAG_UPPER:
                break;

            case HASH_FLAG_EXACT:
                if (p->mv.uMove == 0)
                {
                    ASSERT(FALSE);
                    return(FALSE);
                }
                break;

            default:
                ASSERT(FALSE);
                return(FALSE);
        }
    }
    return(TRUE);
}


FLAG
TestLocklessHashAlgebra(void)
/**

Routine description:

    Pure algebra test for the lockless-hash scheme (Hyatt/Crafty --
    see hash.c's module comment) -- no concurrency involved, just
    verifies the XOR round-trip and the self-detection property a
    concurrent writer's torn update relies on. Operates directly on
    bare HASH_ENTRY structs, nothing from the real hash table.

    Three things checked, each over many random (key, data) pairs:

      1. Round-trip: write u64Data, write u64Sig = key ^ u64Data,
         then verify (u64Sig ^ u64Data) == key. This is the whole
         scheme -- if this doesn't hold, nothing else about the
         lockless rewrite can be trusted.

      2. Torn-write detection: simulate two threads' writes
         interleaving (data from one, sig from the other) and confirm
         the un-corrupted key essentially never matches either real
         key -- the self-check that makes the scheme safe without a
         lock.

      3. The one documented, harmless exception: when the two
         "threads'" data words happen to be bit-identical, the torn
         read un-corrupts to the SAME key either real writer would
         have produced -- confirmed explicitly, not just allowed to
         slip through the random sampling in (2).

Parameters:

    void

Return value:

    FLAG

**/
{
    const ULONG uIterations = 200000;
    ULONG u;
    FLAG fRet = TRUE;
    UINT64 u64FalsePositives = 0;

    Trace("Testing lockless hash algebra...\n");

    for (u = 0; u < uIterations; u++)
    {
        UINT64 u64Key1 = (((UINT64)randomMT()) << 32) | randomMT();
        UINT64 u64Data1 = (((UINT64)randomMT()) << 32) | randomMT();
        UINT64 u64Key2 = (((UINT64)randomMT()) << 32) | randomMT();
        UINT64 u64Data2 = (((UINT64)randomMT()) << 32) | randomMT();
        UINT64 u64Sig1, u64Sig2;
        UINT64 u64TornKey;

        // 1. Plain round-trip, both "entries" independently.
        u64Sig1 = u64Key1 ^ u64Data1;
        u64Sig2 = u64Key2 ^ u64Data2;
        if (((u64Sig1 ^ u64Data1) != u64Key1) ||
            ((u64Sig2 ^ u64Data2) != u64Key2))
        {
            Trace("TestLocklessHashAlgebra: round-trip failed for "
                  "iteration %lu\n", u);
            fRet = FALSE;
        }

        // 2. Torn write: data from "writer 2", sig from "writer 1"
        // (as if a reader's two plain loads landed on either side of
        // a concurrent full update). Must not un-corrupt to either
        // writer's real key, UNLESS the two data words happen to
        // coincide (case 3, checked separately below) -- that's the
        // one case this random sampling could legitimately hit, so
        // it's explicitly excluded here rather than miscounted as a
        // false positive.
        u64TornKey = u64Sig1 ^ u64Data2;
        if (u64Data1 != u64Data2)
        {
            if ((u64TornKey == u64Key1) || (u64TornKey == u64Key2))
            {
                u64FalsePositives++;
            }
        }
        else if (u64TornKey != u64Key1)
        {
            // This is case 3 by construction (u64Data1 == u64Data2)
            // -- the torn read MUST un-corrupt to u64Key1 here (and,
            // since the data words are equal, u64Key1's own sig1 is
            // exactly what a from-scratch write of u64Key2 with this
            // same data would have produced too -- not checked
            // separately, same algebra).
            Trace("TestLocklessHashAlgebra: case-3 coincidence did not "
                  "verify at iteration %lu\n", u);
            fRet = FALSE;
        }
    }

    // u64FalsePositives should be *exactly* zero -- a torn (sig1,
    // data2) pair un-corrupting to a real key by pure chance (data1
    // != data2) would require a specific 64-bit XOR coincidence,
    // astronomically unlikely across 200k random trials. Any nonzero
    // count here across a large sample is a red flag that the
    // algebra isn't what this comment thinks it is, not expected
    // noise -- hence ASSERT(FALSE), not just a logged warning.
    if (0 != u64FalsePositives)
    {
        Trace("TestLocklessHashAlgebra: %" COMPILER_LONGLONG_UNSIGNED_FORMAT
              " torn-write false positive(s) out of %lu trials\n",
              u64FalsePositives, uIterations);
        ASSERT(FALSE);
        fRet = FALSE;
    }

    if (FALSE == fRet)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "TestLocklessHashAlgebra", NULL, NULL,
                  __FILE__, __LINE__);
    }
    return(fRet);
}


void
AnalyzeFullHashTable(void)
/**

Routine description:

    Walk over the hash table and validate populated entries.

Parameters:

    void

Return value:

    void

**/
{
    ULONG uEntry;
    ULONG uNumEntries = g_uHashTableSizeBytes / sizeof(HASH_ENTRY);
    HASH_ENTRY *p;
    ULONG uEmpty = 0;
    ULONG uStale = 0;
    ULONG uUnique = 0;
    ULONG uCount = 0;
    ULONG u;
    double d;
    FLAG fUnique;

    for (uEntry = 0;
         uEntry < uNumEntries;
         uEntry++)
    {
        p = &(g_pHashTable[uEntry]);

        //
        // See if it's stale
        //
        if ((p->bvFlags & 0xF0) != g_cDirty)
        {
            uStale++;
        }

        //
        // Sanity checks
        //
        if (FALSE == SanityCheckHashEntry(p))
        {
            UtilPanic(TESTCASE_FAILURE,
                      NULL, "TestHash", NULL, NULL,
                      __FILE__, __LINE__);
        }

        //
        // See if it's empty
        //
        if (p->u64Sig == 0)
        {
            uEmpty++;
        }
        else
        {
            uCount++;

            //
            // See if it's unique
            //
            if (uEntry % NUM_HASH_ENTRIES_PER_LINE)
            {
                // Lockless hash (see hash.c's module comment): u64Sig
                // no longer holds the plain key, it holds (realKey ^
                // u64Data), so two entries for the SAME position don't
                // have equal raw .u64Sig unless their .u64Data also
                // happens to match -- un-corrupt each side before
                // comparing.
                fUnique = TRUE;
                u = uEntry - 1;
                do
                {
                    if ((p->u64Sig ^ p->u64Data) ==
                        (g_pHashTable[u].u64Sig ^ g_pHashTable[u].u64Data))
                    {
                        fUnique = FALSE;
                        break;
                    }
                    u--;
                }
                while(u % NUM_HASH_ENTRIES_PER_LINE);
            }
            else
            {
                fUnique = TRUE;
            }
            uUnique += fUnique;
        }
    }

    //
    // Show results
    //
    Trace("There are %u entries in the hash table.\n", uNumEntries);

    d = (double)uStale / (double)uNumEntries * 100.0;
    Trace("The hash table is %6.3f percent stale.\n", d);

    d = (double)uEmpty / (double)uNumEntries * 100.0;
    Trace("The hash table is %6.3f percent empty.\n", d);

    d = (double)uUnique / (double)uCount * 100.0;
    Trace("The hash table is %6.3f percent unique.\n", d);
}
#endif