FreeBSD/Linux Kernel Cross Reference
sys/contrib/ck/include/spinlock/ticket.h

     /*
      * Copyright 2010-2015 Samy Al Bahra.
      * 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 THE AUTHOR 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 AUTHOR 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 CK_SPINLOCK_TICKET_H
    #define CK_SPINLOCK_TICKET_H
    
    #include <ck_backoff.h>
    #include <ck_cc.h>
    #include <ck_elide.h>
    #include <ck_md.h>
    #include <ck_pr.h>
    #include <ck_stdbool.h>
    
    #ifndef CK_F_SPINLOCK_TICKET
    #define CK_F_SPINLOCK_TICKET
    /*
     * If 16-bit or 32-bit increment is supported, implement support for
     * trylock functionality on availability of 32-bit or 64-bit fetch-and-add
     * and compare-and-swap. This code path is only applied to x86*.
     */
    #if defined(CK_MD_TSO) && (defined(__x86__) || defined(__x86_64__))
    #if defined(CK_F_PR_FAA_32) && defined(CK_F_PR_INC_16) && defined(CK_F_PR_CAS_32)
    #define CK_SPINLOCK_TICKET_TYPE         uint32_t
    #define CK_SPINLOCK_TICKET_TYPE_BASE    uint16_t
    #define CK_SPINLOCK_TICKET_INC(x)       ck_pr_inc_16(x)
    #define CK_SPINLOCK_TICKET_CAS(x, y, z) ck_pr_cas_32(x, y, z)
    #define CK_SPINLOCK_TICKET_FAA(x, y)    ck_pr_faa_32(x, y)
    #define CK_SPINLOCK_TICKET_LOAD(x)      ck_pr_load_32(x)
    #define CK_SPINLOCK_TICKET_INCREMENT    (0x00010000UL)
    #define CK_SPINLOCK_TICKET_MASK         (0xFFFFUL)
    #define CK_SPINLOCK_TICKET_SHIFT        (16)
    #elif defined(CK_F_PR_FAA_64) && defined(CK_F_PR_INC_32) && defined(CK_F_PR_CAS_64)
    #define CK_SPINLOCK_TICKET_TYPE         uint64_t
    #define CK_SPINLOCK_TICKET_TYPE_BASE    uint32_t
    #define CK_SPINLOCK_TICKET_INC(x)       ck_pr_inc_32(x)
    #define CK_SPINLOCK_TICKET_CAS(x, y, z) ck_pr_cas_64(x, y, z)
    #define CK_SPINLOCK_TICKET_FAA(x, y)    ck_pr_faa_64(x, y)
    #define CK_SPINLOCK_TICKET_LOAD(x)      ck_pr_load_64(x)
    #define CK_SPINLOCK_TICKET_INCREMENT    (0x0000000100000000ULL)
    #define CK_SPINLOCK_TICKET_MASK         (0xFFFFFFFFULL)
    #define CK_SPINLOCK_TICKET_SHIFT        (32)
    #endif
    #endif /* CK_MD_TSO */
    
    #if defined(CK_SPINLOCK_TICKET_TYPE)
    #define CK_F_SPINLOCK_TICKET_TRYLOCK
    
    struct ck_spinlock_ticket {
            CK_SPINLOCK_TICKET_TYPE value;
    };
    typedef struct ck_spinlock_ticket ck_spinlock_ticket_t;
    #define CK_SPINLOCK_TICKET_INITIALIZER { .value = 0 }
    
    CK_CC_INLINE static void
    ck_spinlock_ticket_init(struct ck_spinlock_ticket *ticket)
    {
    
            ticket->value = 0;
            ck_pr_barrier();
            return;
    }
    
    CK_CC_INLINE static bool
    ck_spinlock_ticket_locked(struct ck_spinlock_ticket *ticket)
    {
            CK_SPINLOCK_TICKET_TYPE request, position;
    
            request = CK_SPINLOCK_TICKET_LOAD(&ticket->value);
            position = request & CK_SPINLOCK_TICKET_MASK;
            request >>= CK_SPINLOCK_TICKET_SHIFT;
    
            ck_pr_fence_acquire();
            return request != position;
    }
    
    CK_CC_INLINE static void
   ck_spinlock_ticket_lock(struct ck_spinlock_ticket *ticket)
   {
           CK_SPINLOCK_TICKET_TYPE request, position;
   
           /* Get our ticket number and set next ticket number. */
           request = CK_SPINLOCK_TICKET_FAA(&ticket->value,
               CK_SPINLOCK_TICKET_INCREMENT);
   
           position = request & CK_SPINLOCK_TICKET_MASK;
           request >>= CK_SPINLOCK_TICKET_SHIFT;
   
           while (request != position) {
                   ck_pr_stall();
                   position = CK_SPINLOCK_TICKET_LOAD(&ticket->value) &
                       CK_SPINLOCK_TICKET_MASK;
           }
   
           ck_pr_fence_lock();
           return;
   }
   
   CK_CC_INLINE static void
   ck_spinlock_ticket_lock_pb(struct ck_spinlock_ticket *ticket, unsigned int c)
   {
           CK_SPINLOCK_TICKET_TYPE request, position;
           ck_backoff_t backoff;
   
           /* Get our ticket number and set next ticket number. */
           request = CK_SPINLOCK_TICKET_FAA(&ticket->value,
               CK_SPINLOCK_TICKET_INCREMENT);
   
           position = request & CK_SPINLOCK_TICKET_MASK;
           request >>= CK_SPINLOCK_TICKET_SHIFT;
   
           while (request != position) {
                   ck_pr_stall();
                   position = CK_SPINLOCK_TICKET_LOAD(&ticket->value) &
                       CK_SPINLOCK_TICKET_MASK;
   
                   backoff = (request - position) & CK_SPINLOCK_TICKET_MASK;
                   backoff <<= c;
                   ck_backoff_eb(&backoff);
           }
   
           ck_pr_fence_lock();
           return;
   }
   
   CK_CC_INLINE static bool
   ck_spinlock_ticket_trylock(struct ck_spinlock_ticket *ticket)
   {
           CK_SPINLOCK_TICKET_TYPE snapshot, request, position;
   
           snapshot = CK_SPINLOCK_TICKET_LOAD(&ticket->value);
           position = snapshot & CK_SPINLOCK_TICKET_MASK;
           request = snapshot >> CK_SPINLOCK_TICKET_SHIFT;
   
           if (position != request)
                   return false;
   
           if (CK_SPINLOCK_TICKET_CAS(&ticket->value,
               snapshot, snapshot + CK_SPINLOCK_TICKET_INCREMENT) == false) {
                   return false;
           }
   
           ck_pr_fence_lock();
           return true;
   }
   
   CK_CC_INLINE static void
   ck_spinlock_ticket_unlock(struct ck_spinlock_ticket *ticket)
   {
   
           ck_pr_fence_unlock();
           CK_SPINLOCK_TICKET_INC((CK_SPINLOCK_TICKET_TYPE_BASE *)(void *)&ticket->value);
           return;
   }
   
   #undef CK_SPINLOCK_TICKET_TYPE
   #undef CK_SPINLOCK_TICKET_TYPE_BASE
   #undef CK_SPINLOCK_TICKET_INC
   #undef CK_SPINLOCK_TICKET_FAA
   #undef CK_SPINLOCK_TICKET_LOAD
   #undef CK_SPINLOCK_TICKET_INCREMENT
   #undef CK_SPINLOCK_TICKET_MASK
   #undef CK_SPINLOCK_TICKET_SHIFT
   #else
   /*
    * MESI benefits from cacheline padding between next and current. This avoids
    * invalidation of current from the cache due to incoming lock requests.
    */
   struct ck_spinlock_ticket {
           unsigned int next;
           unsigned int position;
   };
   typedef struct ck_spinlock_ticket ck_spinlock_ticket_t;
   
   #define CK_SPINLOCK_TICKET_INITIALIZER {.next = 0, .position = 0}
   
   CK_CC_INLINE static void
   ck_spinlock_ticket_init(struct ck_spinlock_ticket *ticket)
   {
   
           ticket->next = 0;
           ticket->position = 0;
           ck_pr_barrier();
   
           return;
   }
   
   CK_CC_INLINE static bool
   ck_spinlock_ticket_locked(struct ck_spinlock_ticket *ticket)
   {
           bool r;
   
           r = ck_pr_load_uint(&ticket->position) !=
               ck_pr_load_uint(&ticket->next);
           ck_pr_fence_acquire();
           return r;
   }
   
   CK_CC_INLINE static void
   ck_spinlock_ticket_lock(struct ck_spinlock_ticket *ticket)
   {
           unsigned int request;
   
           /* Get our ticket number and set next ticket number. */
           request = ck_pr_faa_uint(&ticket->next, 1);
   
           /*
            * Busy-wait until our ticket number is current.
            * We can get away without a fence here assuming
            * our position counter does not overflow.
            */
           while (ck_pr_load_uint(&ticket->position) != request)
                   ck_pr_stall();
   
           ck_pr_fence_lock();
           return;
   }
   
   CK_CC_INLINE static void
   ck_spinlock_ticket_lock_pb(struct ck_spinlock_ticket *ticket, unsigned int c)
   {
           ck_backoff_t backoff;
           unsigned int request, position;
   
           request = ck_pr_faa_uint(&ticket->next, 1);
   
           for (;;) {
                   position = ck_pr_load_uint(&ticket->position);
                   if (position == request)
                           break;
   
                   backoff = request - position;
                   backoff <<= c;
   
                   /*
                    * Ideally, back-off from generating cache traffic for at least
                    * the amount of time necessary for the number of pending lock
                    * acquisition and relinquish operations (assuming an empty
                    * critical section).
                    */
                   ck_backoff_eb(&backoff);
           }
   
           ck_pr_fence_lock();
           return;
   }
   
   CK_CC_INLINE static void
   ck_spinlock_ticket_unlock(struct ck_spinlock_ticket *ticket)
   {
           unsigned int update;
   
           ck_pr_fence_unlock();
   
           /*
            * Update current ticket value so next lock request can proceed.
            * Overflow behavior is assumed to be roll-over, in which case,
            * it is only an issue if there are 2^32 pending lock requests.
            */
           update = ck_pr_load_uint(&ticket->position);
           ck_pr_store_uint(&ticket->position, update + 1);
           return;
   }
   #endif /* !CK_F_SPINLOCK_TICKET_TRYLOCK */
   
   CK_ELIDE_PROTOTYPE(ck_spinlock_ticket, ck_spinlock_ticket_t,
       ck_spinlock_ticket_locked, ck_spinlock_ticket_lock,
       ck_spinlock_ticket_locked, ck_spinlock_ticket_unlock)
   
   CK_ELIDE_TRYLOCK_PROTOTYPE(ck_spinlock_ticket, ck_spinlock_ticket_t,
       ck_spinlock_ticket_locked, ck_spinlock_ticket_trylock)
   
   #endif /* CK_F_SPINLOCK_TICKET */
   #endif /* CK_SPINLOCK_TICKET_H */

Cache object: b959552de994bef3974605a81b31da39