portable_defns.h

/*
Copyright (c) 2003, Keir Fraser All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

    * Redistributions of source code must retain the above copyright
    * notice, this list of conditions and the following disclaimer.
    * 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.  Neither the name of the Keir Fraser
    * nor the names of its contributors may be used to endorse or
    * promote products derived from this software without specific
    * prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"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 THE COPYRIGHT
OWNER 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.
*/

#ifndef __PORTABLE_DEFNS_H__
#define __PORTABLE_DEFNS_H__

#define MAX_THREADS 256 /* Nobody will ever have more! */

#if defined(SPARC)
#include "sparc_defns.h"
#elif defined(SOLARIS_X86_686)
#include "solaris_x86_defns.h"
#elif defined(SOLARIS_X86_AMD64)
#include "solaris_amd64_defns.h"
#elif defined(INTEL)
#include "intel_defns.h"
#elif defined(X86_64)
#include "amd64_defns.h"
#elif defined(PPC)
#include "ppc_defns.h"
#elif defined(IA64)
#include "ia64_defns.h"
#elif defined(MIPS)
#include "mips_defns.h"
#elif defined(ALPHA)
#include "alpha_defns.h"
#else
#error "A valid architecture has not been defined"
#endif

#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif

#ifndef MB_NEAR_CAS
#define RMB_NEAR_CAS() RMB()
#define WMB_NEAR_CAS() WMB()
#define MB_NEAR_CAS()  MB()
#endif

typedef unsigned long int_addr_t;

#define FALSE 0
#define TRUE  1

#define ADD_TO(_v,_x)                                                   \
do {                                                                    \
    unsigned long __val = (_v), __newval;                               \
    while ( (__newval = CASIO(&(_v),__val,__val+(_x))) != __val )       \
        __val = __newval;                                               \
} while ( 0 )

/* new 'returning' versions allow use of old value at the successful
 * CAS update (Matt).  This allows an atomic inc to know if it was, for
 * example, the operation which uniquely incremented _v from 0 to 1, and
 * all equivalent threshold assertions */

#define ADD_TO_RETURNING_OLD(_v,_x,_o) \
do {                                                                    \
    unsigned long __val = (_v), __newval;                               \
    while ( (__newval = CASIO(&(_v),__val,__val+(_x))) != __val )       \
        __val = __newval;                                               \
	_o = __val;															\
} while ( 0 )

#define SUB_FROM(_v,_x)                                                 \
do {                                                                    \
    unsigned long __val = (_v), __newval;                               \
    while ( (__newval = CASIO(&(_v),__val,__val-(_x))) != __val )       \
        __val = __newval;                                               \
} while ( 0 )

#define SUB_FROM_RETURNING_OLD(_v,_x,_o)                                \
do {                                                                    \
    unsigned long __val = (_v), __newval;                               \
    while ( (__newval = CASIO(&(_v),__val,__val-(_x))) != __val )       \
        __val = __newval;                                               \
	_o = __val;															\
} while ( 0 )

/* or conversely the new value */
#define ADD_TO_RETURNING_NEW(_v,_x,_n) \
do {                                                                    \
    unsigned long __val = (_v), __newval;                               \
    while ( (__newval = CASIO(&(_v),__val,__val+(_x))) != __val )       \
        __val = __newval;                                               \
	_n = __val+_x;															\
} while ( 0 )

#define SUB_FROM_RETURNING_NEW(_v,_x,_n)                                \
do {                                                                    \
    unsigned long __val = (_v), __newval;                               \
    while ( (__newval = CASIO(&(_v),__val,__val-(_x))) != __val )       \
        __val = __newval;                                               \
	_n = __val+_x;															\
} while ( 0 )

/*
 * Allow us to efficiently align and pad structures so that shared fields
 * don't cause contention on thread-local or read-only fields.
 */
#define CACHE_PAD(_n) char __pad ## _n [CACHE_LINE_SIZE]
#define ALIGNED_ALLOC(_s)                                       \
    ((void *)(((unsigned long)malloc((_s)+CACHE_LINE_SIZE*2) +  \
        CACHE_LINE_SIZE - 1) & ~(CACHE_LINE_SIZE-1)))

/*
 * Interval counting
 */

typedef unsigned int interval_t;
#define get_interval(_i)                                                 \
do {                                                                     \
    interval_t _ni = interval;                                           \
    do { _i = _ni; } while ( (_ni = CASIO(&interval, _i, _i+1)) != _i ); \
} while ( 0 )

/*
 * POINTER MARKING
 */

#define get_marked_ref(_p)      ((void *)(((unsigned long)(_p)) | 1))
#define get_unmarked_ref(_p)    ((void *)(((unsigned long)(_p)) & ~1))
#define is_marked_ref(_p)       (((unsigned long)(_p)) & 1)


/*
 * SUPPORT FOR WEAK ORDERING OF MEMORY ACCESSES
 */

#ifdef WEAK_MEM_ORDER

#define MAYBE_GARBAGE (0)

/* Read field @_f into variable @_x. */
#define READ_FIELD(_x,_f)                                       \
do {                                                            \
    (_x) = (_f);                                                \
    if ( (_x) == MAYBE_GARBAGE ) { RMB(); (_x) = (_f); }        \
 while ( 0 )

#define WEAK_DEP_ORDER_RMB() RMB()
#define WEAK_DEP_ORDER_WMB() WMB()
#define WEAK_DEP_ORDER_MB()  MB()

#else

/* Read field @_f into variable @_x. */
#define READ_FIELD(_x,_f) ((_x) = (_f))

#define WEAK_DEP_ORDER_RMB() ((void)0)
#define WEAK_DEP_ORDER_WMB() ((void)0)
#define WEAK_DEP_ORDER_MB()  ((void)0)

#endif

#if !defined(INTEL) && !defined(SOLARIS_X86_686) && !defined(SOLARIS_X86_AMD64) && !defined(X86_64)

/*
 * Strong LL/SC operations
 */

static inline _u32 strong_ll(_u64 *ptr, int p)
{
    _u64 val_read;
    _u64 new_val;
    _u64 flag;

    flag = (1LL << p);

    new_val = *ptr;
    do {
        val_read = new_val;
        new_val = val_read | flag;
    } while ( ((val_read & flag) == 0) &&
              ((new_val = CAS64O(ptr, val_read, new_val)) != val_read) );

    return (_u32) (val_read >> 32);
}
#endif /* !INTEL */


static inline int strong_vl(_u64 *ptr, int p)
{
    _u64 val_read;
    _u64 flag;

    flag = (1LL << p);
    val_read = *ptr;

    return (val_read & flag);
}

#if !defined(INTEL) && !defined(X86_64)
static inline int strong_sc(_u64 *ptr, int p, _u32 n)
{
    _u64 val_read;
    _u64 new_val;
    _u64 flag;

    flag = (1LL << p);
    val_read = *ptr;

    while ( (val_read & flag) != 0 )
    {
        new_val = (((_u64)n) << 32);

        if ( (new_val = CAS64O(ptr, val_read, new_val)) == val_read )
        {
            return 1;
        }

        val_read = new_val;
    }

    return 0;
}
#endif /* !INTEL */


static inline void s_store(_u64 *ptr, _u32 n)
{
    _u64 new_val;

    new_val = (((_u64)n) << 32);
    *ptr = new_val;
}

static inline _u32 s_load(_u64 *ptr)
{
    _u64 val_read;

    val_read = *ptr;
    return (val_read >> 32);
}


/*
 * MCS lock
 */

typedef struct qnode_t qnode_t;

struct qnode_t {
    qnode_t *next;
    int locked;
};

typedef struct {
    qnode_t *tail;
} mcs_lock_t;

static inline void mcs_init(mcs_lock_t *lock)
{
    lock->tail = NULL;
}

static inline void mcs_lock(mcs_lock_t *lock, qnode_t *qn)
{
    qnode_t *pred;

    qn->next = NULL;
    qn->locked = 1;
    WMB_NEAR_CAS();

    pred = FASPO(&lock->tail, qn);
    if ( pred != NULL )
    {
        pred->next = qn;
        while ( qn->locked ) RMB();
    }

    MB();
}

static inline void mcs_unlock(mcs_lock_t *lock, qnode_t *qn)
{
    qnode_t *t = qn->next;

    MB();

    if ( t == NULL )
    {
        if ( CASPO(&lock->tail, qn, NULL) == qn ) return;
        while ( (t = qn->next) == NULL ) RMB();
        WEAK_DEP_ORDER_MB();
    }

    t->locked = 0;
}


/*
 * MCS fair MRSW lock.
 */

typedef struct mrsw_qnode_st mrsw_qnode_t;

struct mrsw_qnode_st {
#define CLS_RD 0
#define CLS_WR 1
    int qclass;
#define ST_NOSUCC   0
#define ST_RDSUCC   1
#define ST_WRSUCC   2
#define ST_SUCCMASK 3
#define ST_BLOCKED  4
    int state;
    mrsw_qnode_t *next;
};

typedef struct {
    mrsw_qnode_t *tail;
    mrsw_qnode_t *next_writer;
    int reader_count;
} mrsw_lock_t;


#define CLEAR_BLOCKED(_qn) ADD_TO((_qn)->state, -ST_BLOCKED)

static inline void mrsw_init(mrsw_lock_t *lock)
{
    memset(lock, 0, sizeof(*lock));
}

static inline void rd_lock(mrsw_lock_t *lock, mrsw_qnode_t *qn)
{
    mrsw_qnode_t *pred, *next;

    qn->qclass = CLS_RD;
    qn->next  = NULL;
    qn->state = ST_NOSUCC | ST_BLOCKED;

    WMB_NEAR_CAS();

    pred = FASPO(&lock->tail, qn);

    if ( pred == NULL )
    {
        ADD_TO(lock->reader_count, 1);
        CLEAR_BLOCKED(qn);
    }
    else
    {
        if ( (pred->qclass == CLS_WR) ||
             (CASIO(&pred->state, ST_BLOCKED|ST_NOSUCC, ST_BLOCKED|ST_RDSUCC)
              == (ST_BLOCKED|ST_NOSUCC)) )
        {
            WEAK_DEP_ORDER_WMB();
            pred->next = qn;
            while ( (qn->state & ST_BLOCKED) ) RMB();
        }
        else
        {
            ADD_TO(lock->reader_count, 1);
            pred->next = qn;
            WEAK_DEP_ORDER_WMB();
            CLEAR_BLOCKED(qn);
        }
    }

    if ( qn->state == ST_RDSUCC )
    {
        while ( (next = qn->next) == NULL ) RMB();
        ADD_TO(lock->reader_count, 1);
        WEAK_DEP_ORDER_WMB();
        CLEAR_BLOCKED(next);
    }

    RMB();
}

static inline void rd_unlock(mrsw_lock_t *lock, mrsw_qnode_t *qn)
{
    mrsw_qnode_t *next = qn->next;
    int c, oc;

    RMB();

    if ( (next != NULL) || (CASPO(&lock->tail, qn, NULL) != qn) )
    {
        while ( (next = qn->next) == NULL ) RMB();
        if ( (qn->state & ST_SUCCMASK) == ST_WRSUCC )
        {
            lock->next_writer = next;
            WMB_NEAR_CAS(); /* set next_writer before dec'ing refcnt */
        }
    }

    /* Bounded to maximum # readers if no native atomic_decrement */
    c = lock->reader_count;
    while ( (oc = CASIO(&lock->reader_count, c, c-1)) != c ) c = oc;

    if ( c == 1 )
    {
        WEAK_DEP_ORDER_MB();
        if ( (next = lock->next_writer) != NULL )
        {
            RMB();
            if ( (lock->reader_count == 0) &&
                 (CASPO(&lock->next_writer, next, NULL) == next) )
            {
                WEAK_DEP_ORDER_WMB();
                CLEAR_BLOCKED(next);
            }
        }
    }
}

static inline void wr_lock(mrsw_lock_t *lock, mrsw_qnode_t *qn)
{
    mrsw_qnode_t *pred;
    int os, s;

    qn->qclass = CLS_WR;
    qn->next  = NULL;
    qn->state = ST_NOSUCC | ST_BLOCKED;

    WMB_NEAR_CAS();

    pred = FASPO(&lock->tail, qn);

    if ( pred == NULL )
    {
        WEAK_DEP_ORDER_WMB();
        lock->next_writer = qn;
        MB(); /* check reader_count after setting next_writer. */
        if ( (lock->reader_count == 0) &&
             (CASPO(&lock->next_writer, qn, NULL) == qn) )
        {
            CLEAR_BLOCKED(qn);
        }
    }
    else
    {
        s = pred->state;
        /* Bounded while loop: only one other remote update may occur. */
        while ( (os = CASIO(&pred->state, s, s | ST_WRSUCC)) != s ) s = os;
        WMB();
        pred->next = qn;
    }

    while ( (qn->state & ST_BLOCKED) ) RMB();

    MB();
}

static inline void wr_unlock(mrsw_lock_t *lock, mrsw_qnode_t *qn)
{
    mrsw_qnode_t *next = qn->next;

    MB();

    if ( (next != NULL) || (CASPO(&lock->tail, qn, NULL) != qn) )
    {
        while ( (next = qn->next) == NULL ) RMB();
        WEAK_DEP_ORDER_MB();
        if ( next->qclass == CLS_RD )
        {
            ADD_TO(lock->reader_count, 1);
            WMB();
        }
        CLEAR_BLOCKED(next);
    }
}

#ifdef __cplusplus
}
#endif

#endif /* __PORTABLE_DEFNS_H__ */