Source/bmalloc/libpas/src/test/LockFreeReadPtrPtrHashtableTests.cpp

/*
 * Copyright (c) 2019-2020 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "TestHarness.h"
#include "pas_heap_lock.h"
#include "pas_lock.h"
#include "pas_lock_free_read_ptr_ptr_hashtable.h"
#include <thread>
#include <vector>
#include <map>

using namespace std;

namespace {

unsigned hashFunction(const void* key, void* arg)
{
    PAS_UNUSED_PARAM(arg);
    return pas_hash_ptr(key);
}

void testChaos(unsigned numHitReaderThreads,
               unsigned numMissReaderThreads,
               unsigned numWriterThreads,
               unsigned numAdditions)
{
    pas_lock_free_read_ptr_ptr_hashtable table;
    map<unsigned, unsigned> ourMap;
    pas_lock mapLock;
    vector<unsigned> ourList;
    pas_lock listLock;
    bool done;
    vector<thread> writerThreads;
    vector<thread> readerThreads;
    pas_lock stopLock;
    unsigned numThreadsStopped;

    table = PAS_LOCK_FREE_READ_PTR_PTR_HASHTABLE_INITIALIZER;
    done = false;

    mapLock = PAS_LOCK_INITIALIZER;
    listLock = PAS_LOCK_INITIALIZER;

    stopLock = PAS_LOCK_INITIALIZER;
    numThreadsStopped = 0;

    auto threadIsStopping =
        [&] () {
            pas_lock_lock(&stopLock);
            numThreadsStopped++;
            pas_lock_unlock(&stopLock);
        };
    
    auto writerThreadFunc =
        [&] () {
            for (unsigned count = numAdditions; count--;) {
                unsigned key;
                unsigned value;

                value = deterministicRandomNumber(UINT_MAX);

                pas_lock_lock(&mapLock);
                for (;;) {
                    key = deterministicRandomNumber(UINT_MAX);
                    if (!ourMap.count(key))
                        break;
                }
                ourMap[key] = value;
                pas_lock_unlock(&mapLock);

                pas_heap_lock_lock();
                pas_lock_free_read_ptr_ptr_hashtable_set(
                    &table,
                    hashFunction,
                    NULL,
                    reinterpret_cast<const void*>(static_cast<uintptr_t>(key)),
                    reinterpret_cast<const void*>(static_cast<uintptr_t>(value)),
                    pas_lock_free_read_ptr_ptr_hashtable_add_new);
                pas_heap_lock_unlock();

                pas_lock_lock(&listLock);
                ourList.push_back(key);
                pas_lock_unlock(&listLock);
            }
            threadIsStopping();
        };

    auto hitReaderThreadFunc =
        [&] () {
            while (!done) {
                unsigned key;

                pas_lock_lock(&listLock);
                if (ourList.empty()) {
                    pas_lock_unlock(&listLock);
                    continue;
                }
                key = ourList[deterministicRandomNumber(static_cast<unsigned>(ourList.size()))];
                pas_lock_unlock(&listLock);

                const void* result = pas_lock_free_read_ptr_ptr_hashtable_find(
                    &table, hashFunction, NULL,
                    reinterpret_cast<const void*>(static_cast<uintptr_t>(key)));

                pas_lock_lock(&mapLock);
                unsigned value = ourMap[key];
                CHECK_EQUAL(result, reinterpret_cast<const void*>(static_cast<uintptr_t>(value)));
                pas_lock_unlock(&mapLock);
            }
            threadIsStopping();
        };

    auto missReaderThreadFunc =
        [&] () {
            while (!done) {
                uint64_t key;

                key = static_cast<uint64_t>(deterministicRandomNumber(UINT_MAX)) +
                    static_cast<uint64_t>(UINT_MAX);

                const void* result = pas_lock_free_read_ptr_ptr_hashtable_find(
                    &table, hashFunction, NULL,
                    reinterpret_cast<const void*>(static_cast<uintptr_t>(key)));

                CHECK(!result);
            }
            threadIsStopping();
        };

    for (unsigned count = numHitReaderThreads; count--;)
        readerThreads.push_back(thread(hitReaderThreadFunc));
    for (unsigned count = numMissReaderThreads; count--;)
        readerThreads.push_back(thread(missReaderThreadFunc));

    for (unsigned count = numWriterThreads; count--;)
        writerThreads.push_back(thread(writerThreadFunc));

    for (thread& thread : writerThreads)
        thread.join();

    done = true;

    for (thread& thread : readerThreads)
        thread.join();

    CHECK_EQUAL(numThreadsStopped, readerThreads.size() + writerThreads.size());
}

} // anonymous namespace

void addLockFreeReadPtrPtrHashtableTests()
{
    ADD_TEST(testChaos(1, 1, 1, 2000000));
    ADD_TEST(testChaos(10, 10, 10, 200000));
}