path: root/src/VBox/Runtime/generic/semxroads-generic.cpp

/* $Id: semxroads-generic.cpp $ */
/** @file
 * IPRT Testcase - RTSemXRoads, generic implementation.
 */

/*
 * Copyright (C) 2009-2019 Oracle Corporation
 *
 * This file is part of VirtualBox Open Source Edition (OSE), as
 * available from http://www.virtualbox.org. This file is free software;
 * you can redistribute it and/or modify it under the terms of the GNU
 * General Public License (GPL) as published by the Free Software
 * Foundation, in version 2 as it comes in the "COPYING" file of the
 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
 *
 * The contents of this file may alternatively be used under the terms
 * of the Common Development and Distribution License Version 1.0
 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
 * VirtualBox OSE distribution, in which case the provisions of the
 * CDDL are applicable instead of those of the GPL.
 *
 * You may elect to license modified versions of this file under the
 * terms and conditions of either the GPL or the CDDL or both.
 */


/*********************************************************************************************************************************
*   Header Files                                                                                                                 *
*********************************************************************************************************************************/
#define RTASSERT_QUIET
#include <iprt/semaphore.h>
#include "internal/iprt.h"

#include <iprt/asm.h>
#include <iprt/assert.h>
#include <iprt/err.h>
#include <iprt/mem.h>
#include <iprt/thread.h>

#include "internal/magics.h"


/*********************************************************************************************************************************
*   Structures and Typedefs                                                                                                      *
*********************************************************************************************************************************/
typedef struct RTSEMXROADSINTERNAL
{
    /** Magic value (RTSEMXROADS_MAGIC).  */
    uint32_t volatile   u32Magic;
    uint32_t            u32Padding; /**< alignment padding.*/
    /* The state variable.
     * All accesses are atomic and it bits are defined like this:
     *      Bits 0..14  - cNorthSouth.
     *      Bit 15      - Unused.
     *      Bits 16..31 - cEastWest.
     *      Bit 31      - fDirection; 0=NS, 1=EW.
     *      Bits 32..46 - cWaitingNS
     *      Bit 47      - Unused.
     *      Bits 48..62 - cWaitingEW
     *      Bit 63      - Unused.
     */
    uint64_t volatile   u64State;
    /** Per-direction data. */
    struct
    {
        /** What the north/south bound threads are blocking on when waiting for
         * east/west traffic to stop. */
        RTSEMEVENTMULTI     hEvt;
        /** Indicates whether the semaphore needs resetting. */
        bool volatile       fNeedReset;
    } aDirs[2];
} RTSEMXROADSINTERNAL;


/*********************************************************************************************************************************
*   Defined Constants And Macros                                                                                                 *
*********************************************************************************************************************************/
#define RTSEMXROADS_CNT_BITS            15
#define RTSEMXROADS_CNT_MASK            UINT64_C(0x00007fff)

#define RTSEMXROADS_CNT_NS_SHIFT        0
#define RTSEMXROADS_CNT_NS_MASK         (RTSEMXROADS_CNT_MASK << RTSEMXROADS_CNT_NS_SHIFT)
#define RTSEMXROADS_CNT_EW_SHIFT        16
#define RTSEMXROADS_CNT_EW_MASK         (RTSEMXROADS_CNT_MASK << RTSEMXROADS_CNT_EW_SHIFT)
#define RTSEMXROADS_DIR_SHIFT           31
#define RTSEMXROADS_DIR_MASK            RT_BIT_64(RTSEMXROADS_DIR_SHIFT)

#define RTSEMXROADS_WAIT_CNT_NS_SHIFT   32
#define RTSEMXROADS_WAIT_CNT_NS_MASK    (RTSEMXROADS_CNT_MASK << RTSEMXROADS_WAIT_CNT_NS_SHIFT)
#define RTSEMXROADS_WAIT_CNT_EW_SHIFT   48
#define RTSEMXROADS_WAIT_CNT_EW_MASK    (RTSEMXROADS_CNT_MASK << RTSEMXROADS_WAIT_CNT_EW_SHIFT)


#if 0 /* debugging aid */
static uint32_t volatile g_iHist = 0;
static struct
{
    void *tsc;
    RTTHREAD hThread;
    uint32_t line;
    bool fDir;
    void *u64State;
    void *u64OldState;
    bool fNeedResetNS;
    bool fNeedResetEW;
    const char *psz;
} g_aHist[256];

# define add_hist(ns, os, dir, what)  \
    do \
    { \
        uint32_t i = (ASMAtomicIncU32(&g_iHist) - 1) % RT_ELEMENTS(g_aHist);\
        g_aHist[i].line         = __LINE__; \
        g_aHist[i].u64OldState  = (void *)(os); \
        g_aHist[i].u64State     = (void *)(ns); \
        g_aHist[i].fDir         = (dir); \
        g_aHist[i].psz          = (what); \
        g_aHist[i].fNeedResetNS = pThis->aDirs[0].fNeedReset; \
        g_aHist[i].fNeedResetEW = pThis->aDirs[1].fNeedReset; \
        g_aHist[i].hThread      = RTThreadSelf(); \
        g_aHist[i].tsc          = (void *)ASMReadTSC(); \
    } while (0)

# undef DECL_FORCE_INLINE
# define DECL_FORCE_INLINE(type) static type
#else
# define add_hist(ns, os, dir, what)  do { } while (0)
#endif


RTDECL(int) RTSemXRoadsCreate(PRTSEMXROADS phXRoads)
{
    RTSEMXROADSINTERNAL *pThis = (RTSEMXROADSINTERNAL *)RTMemAlloc(sizeof(*pThis));
    if (!pThis)
        return VERR_NO_MEMORY;

    int rc = RTSemEventMultiCreate(&pThis->aDirs[0].hEvt);
    if (RT_SUCCESS(rc))
    {
        rc = RTSemEventMultiCreate(&pThis->aDirs[1].hEvt);
        if (RT_SUCCESS(rc))
        {
            pThis->u32Magic            = RTSEMXROADS_MAGIC;
            pThis->u32Padding          = 0;
            pThis->u64State            = 0;
            pThis->aDirs[0].fNeedReset = false;
            pThis->aDirs[1].fNeedReset = false;
            *phXRoads = pThis;
            return VINF_SUCCESS;
        }
        RTSemEventMultiDestroy(pThis->aDirs[0].hEvt);
    }
    return rc;
}


RTDECL(int) RTSemXRoadsDestroy(RTSEMXROADS hXRoads)
{
    /*
     * Validate input.
     */
    RTSEMXROADSINTERNAL *pThis = hXRoads;
    if (pThis == NIL_RTSEMXROADS)
        return VINF_SUCCESS;
    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);
    Assert(!(ASMAtomicReadU64(&pThis->u64State) & (RTSEMXROADS_CNT_NS_MASK | RTSEMXROADS_CNT_EW_MASK)));

    /*
     * Invalidate the object and free up the resources.
     */
    AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTSEMXROADS_MAGIC_DEAD, RTSEMXROADS_MAGIC), VERR_INVALID_HANDLE);

    RTSEMEVENTMULTI hEvt;
    ASMAtomicXchgHandle(&pThis->aDirs[0].hEvt, NIL_RTSEMEVENTMULTI, &hEvt);
    int rc = RTSemEventMultiDestroy(hEvt);
    AssertRC(rc);

    ASMAtomicXchgHandle(&pThis->aDirs[1].hEvt, NIL_RTSEMEVENTMULTI, &hEvt);
    rc = RTSemEventMultiDestroy(hEvt);
    AssertRC(rc);

    RTMemFree(pThis);
    return VINF_SUCCESS;
}


/**
 * Internal worker for RTSemXRoadsNSEnter and RTSemXRoadsEWEnter.
 *
 * @returns IPRT status code.
 * @param   pThis               The semaphore instance.
 * @param   fDir                The direction.
 * @param   uCountShift         The shift count for getting the count.
 * @param   fCountMask          The mask for getting the count.
 * @param   uWaitCountShift     The shift count for getting the wait count.
 * @param   fWaitCountMask      The mask for getting the wait count.
 */
DECL_FORCE_INLINE(int) rtSemXRoadsEnter(RTSEMXROADSINTERNAL *pThis, uint64_t fDir,
                                        uint64_t uCountShift, uint64_t fCountMask,
                                        uint64_t uWaitCountShift, uint64_t fWaitCountMask)
{
    uint64_t    u64OldState;
    uint64_t    u64State;

    u64State = ASMAtomicReadU64(&pThis->u64State);
    u64OldState = u64State;
    add_hist(u64State, u64OldState, fDir, "enter");

    for (;;)
    {
        if ((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT))
        {
            /* It flows in the right direction, try follow it before it changes. */
            uint64_t c = (u64State & fCountMask) >> uCountShift;
            c++;
            Assert(c < 8*_1K);
            u64State &= ~fCountMask;
            u64State |= c << uCountShift;
            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
            {
                add_hist(u64State, u64OldState, fDir, "enter-simple");
                break;
            }
        }
        else if ((u64State & (RTSEMXROADS_CNT_NS_MASK | RTSEMXROADS_CNT_EW_MASK)) == 0)
        {
            /* Wrong direction, but we're alone here and can simply try switch the direction. */
            u64State &= ~(RTSEMXROADS_CNT_NS_MASK | RTSEMXROADS_CNT_EW_MASK | RTSEMXROADS_DIR_MASK);
            u64State |= (UINT64_C(1) << uCountShift) | (fDir << RTSEMXROADS_DIR_SHIFT);
            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
            {
                Assert(!pThis->aDirs[fDir].fNeedReset);
                add_hist(u64State, u64OldState, fDir, "enter-switch");
                break;
            }
        }
        else
        {
            /* Add ourselves to the queue and wait for the direction to change. */
            uint64_t c = (u64State & fCountMask) >> uCountShift;
            c++;
            Assert(c < RTSEMXROADS_CNT_MASK / 2);

            uint64_t cWait = (u64State & fWaitCountMask) >> uWaitCountShift;
            cWait++;
            Assert(cWait <= c);
            Assert(cWait < RTSEMXROADS_CNT_MASK / 2);

            u64State &= ~(fCountMask | fWaitCountMask);
            u64State |= (c << uCountShift) | (cWait << uWaitCountShift);

            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
            {
                add_hist(u64State, u64OldState, fDir, "enter-wait");
                for (uint32_t iLoop = 0; ; iLoop++)
                {
                    int rc = RTSemEventMultiWait(pThis->aDirs[fDir].hEvt, RT_INDEFINITE_WAIT);
                    AssertRCReturn(rc, rc);

                    if (pThis->u32Magic != RTSEMXROADS_MAGIC)
                        return VERR_SEM_DESTROYED;

                    Assert(pThis->aDirs[fDir].fNeedReset);
                    u64State = ASMAtomicReadU64(&pThis->u64State);
                    add_hist(u64State, u64OldState, fDir, "enter-wakeup");
                    if ((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT))
                        break;
                    AssertMsg(iLoop < 1, ("%u\n", iLoop));
                }

                /* Decrement the wait count and maybe reset the semaphore (if we're last). */
                for (;;)
                {
                    u64OldState = u64State;

                    cWait = (u64State & fWaitCountMask) >> uWaitCountShift;
                    Assert(cWait > 0);
                    cWait--;
                    u64State &= ~fWaitCountMask;
                    u64State |= cWait << uWaitCountShift;

                    if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
                    {
                        if (cWait == 0)
                        {
                            if (ASMAtomicXchgBool(&pThis->aDirs[fDir].fNeedReset, false))
                            {
                                add_hist(u64State, u64OldState, fDir, fDir ? "enter-reset-EW" : "enter-reset-NS");
                                int rc = RTSemEventMultiReset(pThis->aDirs[fDir].hEvt);
                                AssertRCReturn(rc, rc);
                            }
                            else
                                add_hist(u64State, u64OldState, fDir, "enter-dec-no-need");
                        }
                        break;
                    }
                    u64State = ASMAtomicReadU64(&pThis->u64State);
                }
                break;
            }

            add_hist(u64State, u64OldState, fDir, "enter-wait-failed");
        }

        if (pThis->u32Magic != RTSEMXROADS_MAGIC)
            return VERR_SEM_DESTROYED;

        ASMNopPause();
        u64State = ASMAtomicReadU64(&pThis->u64State);
        u64OldState = u64State;
    }

    /* got it! */
    Assert((ASMAtomicReadU64(&pThis->u64State) & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT));
    return VINF_SUCCESS;
}


/**
 * Internal worker for RTSemXRoadsNSLeave and RTSemXRoadsEWLeave.
 *
 * @returns IPRT status code.
 * @param   pThis               The semaphore instance.
 * @param   fDir                The direction.
 * @param   uCountShift         The shift count for getting the count.
 * @param   fCountMask          The mask for getting the count.
 */
DECL_FORCE_INLINE(int) rtSemXRoadsLeave(RTSEMXROADSINTERNAL *pThis, uint64_t fDir, uint64_t uCountShift, uint64_t fCountMask)
{
    for (;;)
    {
        uint64_t u64OldState;
        uint64_t u64State;
        uint64_t c;

        u64State = ASMAtomicReadU64(&pThis->u64State);
        u64OldState = u64State;

        /* The direction cannot change until we've left or we'll crash. */
        Assert((u64State & RTSEMXROADS_DIR_MASK) == (fDir << RTSEMXROADS_DIR_SHIFT));

        c = (u64State & fCountMask) >> uCountShift;
        Assert(c > 0);
        c--;

        if (    c > 0
            ||  (u64State & ((RTSEMXROADS_CNT_NS_MASK | RTSEMXROADS_CNT_EW_MASK) & ~fCountMask)) == 0)
        {
            /* We're not the last one across or there aren't any one waiting in the other direction.  */
            u64State &= ~fCountMask;
            u64State |= c << uCountShift;
            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
            {
                add_hist(u64State, u64OldState, fDir, "leave-simple");
                return VINF_SUCCESS;
            }
        }
        else
        {
            /* Reverse the direction and signal the threads in the other direction. */
            u64State &= ~(fCountMask | RTSEMXROADS_DIR_MASK);
            u64State |= (uint64_t)!fDir << RTSEMXROADS_DIR_SHIFT;
            if (ASMAtomicCmpXchgU64(&pThis->u64State, u64State, u64OldState))
            {
                add_hist(u64State, u64OldState, fDir, fDir ? "leave-signal-NS" : "leave-signal-EW");
                Assert(!pThis->aDirs[!fDir].fNeedReset);
                ASMAtomicWriteBool(&pThis->aDirs[!fDir].fNeedReset, true);
                int rc = RTSemEventMultiSignal(pThis->aDirs[!fDir].hEvt);
                AssertRC(rc);
                return VINF_SUCCESS;
            }
        }

        ASMNopPause();
        if (pThis->u32Magic != RTSEMXROADS_MAGIC)
            return VERR_SEM_DESTROYED;
    }
}


RTDECL(int) RTSemXRoadsNSEnter(RTSEMXROADS hXRoads)
{
    /*
     * Validate input.
     */
    RTSEMXROADSINTERNAL *pThis = hXRoads;
    if (pThis == NIL_RTSEMXROADS)
        return VINF_SUCCESS;
    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);

    return rtSemXRoadsEnter(pThis, 0, RTSEMXROADS_CNT_NS_SHIFT, RTSEMXROADS_CNT_NS_MASK, RTSEMXROADS_WAIT_CNT_NS_SHIFT, RTSEMXROADS_WAIT_CNT_NS_MASK);
}


RTDECL(int) RTSemXRoadsNSLeave(RTSEMXROADS hXRoads)
{
    /*
     * Validate input.
     */
    RTSEMXROADSINTERNAL *pThis = hXRoads;
    if (pThis == NIL_RTSEMXROADS)
        return VINF_SUCCESS;
    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);

    return rtSemXRoadsLeave(pThis, 0, RTSEMXROADS_CNT_NS_SHIFT, RTSEMXROADS_CNT_NS_MASK);
}


RTDECL(int) RTSemXRoadsEWEnter(RTSEMXROADS hXRoads)
{
    /*
     * Validate input.
     */
    RTSEMXROADSINTERNAL *pThis = hXRoads;
    if (pThis == NIL_RTSEMXROADS)
        return VINF_SUCCESS;
    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);

    return rtSemXRoadsEnter(pThis, 1, RTSEMXROADS_CNT_EW_SHIFT, RTSEMXROADS_CNT_EW_MASK, RTSEMXROADS_WAIT_CNT_EW_SHIFT, RTSEMXROADS_WAIT_CNT_EW_MASK);
}


RTDECL(int) RTSemXRoadsEWLeave(RTSEMXROADS hXRoads)
{
    /*
     * Validate input.
     */
    RTSEMXROADSINTERNAL *pThis = hXRoads;
    if (pThis == NIL_RTSEMXROADS)
        return VINF_SUCCESS;
    AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
    AssertReturn(pThis->u32Magic == RTSEMXROADS_MAGIC, VERR_INVALID_HANDLE);

    return rtSemXRoadsLeave(pThis, 1, RTSEMXROADS_CNT_EW_SHIFT, RTSEMXROADS_CNT_EW_MASK);
}