1232950Stheraven/* 2232950Stheraven * Copyright 2010-2012 PathScale, Inc. All rights reserved. 3232950Stheraven * 4232950Stheraven * Redistribution and use in source and binary forms, with or without 5232950Stheraven * modification, are permitted provided that the following conditions are met: 6232950Stheraven * 7232950Stheraven * 1. Redistributions of source code must retain the above copyright notice, 8232950Stheraven * this list of conditions and the following disclaimer. 9232950Stheraven * 10232950Stheraven * 2. Redistributions in binary form must reproduce the above copyright notice, 11232950Stheraven * this list of conditions and the following disclaimer in the documentation 12232950Stheraven * and/or other materials provided with the distribution. 13232950Stheraven * 14232950Stheraven * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS 15232950Stheraven * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 16232950Stheraven * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 17232950Stheraven * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 18232950Stheraven * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 19232950Stheraven * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 20232950Stheraven * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 21232950Stheraven * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 22232950Stheraven * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 23232950Stheraven * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 24232950Stheraven * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25232950Stheraven */ 26232950Stheraven 27227825Stheraven/** 28227825Stheraven * guard.cc: Functions for thread-safe static initialisation. 29227825Stheraven * 30227825Stheraven * Static values in C++ can be initialised lazily their first use. This file 31227825Stheraven * contains functions that are used to ensure that two threads attempting to 32227825Stheraven * initialize the same static do not call the constructor twice. This is 33227825Stheraven * important because constructors can have side effects, so calling the 34227825Stheraven * constructor twice may be very bad. 35227825Stheraven * 36227825Stheraven * Statics that require initialisation are protected by a 64-bit value. Any 37227825Stheraven * platform that can do 32-bit atomic test and set operations can use this 38227825Stheraven * value as a low-overhead lock. Because statics (in most sane code) are 39227825Stheraven * accessed far more times than they are initialised, this lock implementation 40227825Stheraven * is heavily optimised towards the case where the static has already been 41227825Stheraven * initialised. 42227825Stheraven */ 43227825Stheraven#include <stdint.h> 44253159Stheraven#include <stdlib.h> 45253159Stheraven#include <stdio.h> 46227825Stheraven#include <pthread.h> 47227972Stheraven#include <assert.h> 48253159Stheraven#include "atomic.h" 49227825Stheraven 50253159Stheraven// Older GCC doesn't define __LITTLE_ENDIAN__ 51253159Stheraven#ifndef __LITTLE_ENDIAN__ 52253159Stheraven // If __BYTE_ORDER__ is defined, use that instead 53253159Stheraven# ifdef __BYTE_ORDER__ 54253159Stheraven# if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ 55253159Stheraven# define __LITTLE_ENDIAN__ 56253159Stheraven# endif 57253159Stheraven // x86 and ARM are the most common little-endian CPUs, so let's have a 58253159Stheraven // special case for them (ARM is already special cased). Assume everything 59253159Stheraven // else is big endian. 60253159Stheraven# elif defined(__x86_64) || defined(__i386) 61253159Stheraven# define __LITTLE_ENDIAN__ 62253159Stheraven# endif 63253159Stheraven#endif 64253159Stheraven 65253159Stheraven 66253159Stheraven/* 67253159Stheraven * The least significant bit of the guard variable indicates that the object 68253159Stheraven * has been initialised, the most significant bit is used for a spinlock. 69253159Stheraven */ 70227972Stheraven#ifdef __arm__ 71227972Stheraven// ARM ABI - 32-bit guards. 72253159Stheraventypedef uint32_t guard_t; 73278724Sdimtypedef uint32_t guard_lock_t; 74278724Sdimstatic const uint32_t LOCKED = static_cast<guard_t>(1) << 31; 75253159Stheravenstatic const uint32_t INITIALISED = 1; 76278724Sdim#define LOCK_PART(guard) (guard) 77278724Sdim#define INIT_PART(guard) (guard) 78278724Sdim#elif defined(_LP64) 79253159Stheraventypedef uint64_t guard_t; 80278724Sdimtypedef uint64_t guard_lock_t; 81253159Stheraven# if defined(__LITTLE_ENDIAN__) 82278724Sdimstatic const guard_t LOCKED = static_cast<guard_t>(1) << 63; 83253159Stheravenstatic const guard_t INITIALISED = 1; 84253159Stheraven# else 85253159Stheravenstatic const guard_t LOCKED = 1; 86278724Sdimstatic const guard_t INITIALISED = static_cast<guard_t>(1) << 56; 87253159Stheraven# endif 88278724Sdim#define LOCK_PART(guard) (guard) 89278724Sdim#define INIT_PART(guard) (guard) 90278724Sdim#else 91278724Sdimtypedef uint32_t guard_lock_t; 92278724Sdim# if defined(__LITTLE_ENDIAN__) 93278724Sdimtypedef struct { 94278724Sdim uint32_t init_half; 95278724Sdim uint32_t lock_half; 96278724Sdim} guard_t; 97278724Sdimstatic const uint32_t LOCKED = static_cast<guard_lock_t>(1) << 31; 98278724Sdimstatic const uint32_t INITIALISED = 1; 99278724Sdim# else 100278724Sdimtypedef struct { 101278724Sdim uint32_t init_half; 102278724Sdim uint32_t lock_half; 103278724Sdim} guard_t; 104278724Sdim_Static_assert(sizeof(guard_t) == sizeof(uint64_t), ""); 105278724Sdimstatic const uint32_t LOCKED = 1; 106278724Sdimstatic const uint32_t INITIALISED = static_cast<guard_lock_t>(1) << 24; 107278724Sdim# endif 108278724Sdim#define LOCK_PART(guard) (&(guard)->lock_half) 109278724Sdim#define INIT_PART(guard) (&(guard)->init_half) 110253159Stheraven#endif 111278724Sdimstatic const guard_lock_t INITIAL = 0; 112227972Stheraven 113227825Stheraven/** 114227972Stheraven * Acquires a lock on a guard, returning 0 if the object has already been 115227972Stheraven * initialised, and 1 if it has not. If the object is already constructed then 116227972Stheraven * this function just needs to read a byte from memory and return. 117227972Stheraven */ 118253159Stheravenextern "C" int __cxa_guard_acquire(volatile guard_t *guard_object) 119227972Stheraven{ 120278724Sdim guard_lock_t old; 121253159Stheraven // Not an atomic read, doesn't establish a happens-before relationship, but 122253159Stheraven // if one is already established and we end up seeing an initialised state 123253159Stheraven // then it's a fast path, otherwise we'll do something more expensive than 124253159Stheraven // this test anyway... 125278724Sdim if (INITIALISED == *INIT_PART(guard_object)) 126278724Sdim return 0; 127253159Stheraven // Spin trying to do the initialisation 128278724Sdim for (;;) 129227972Stheraven { 130253159Stheraven // Loop trying to move the value of the guard from 0 (not 131253159Stheraven // locked, not initialised) to the locked-uninitialised 132253159Stheraven // position. 133278724Sdim old = __sync_val_compare_and_swap(LOCK_PART(guard_object), 134278724Sdim INITIAL, LOCKED); 135278724Sdim if (old == INITIAL) { 136278724Sdim // Lock obtained. If lock and init bit are 137278724Sdim // in separate words, check for init race. 138278724Sdim if (INIT_PART(guard_object) == LOCK_PART(guard_object)) 139253159Stheraven return 1; 140278724Sdim if (INITIALISED != *INIT_PART(guard_object)) 141278724Sdim return 1; 142278724Sdim 143278724Sdim // No need for a memory barrier here, 144278724Sdim // see first comment. 145278724Sdim *LOCK_PART(guard_object) = INITIAL; 146278724Sdim return 0; 147227972Stheraven } 148278724Sdim // If lock and init bit are in the same word, check again 149278724Sdim // if we are done. 150278724Sdim if (INIT_PART(guard_object) == LOCK_PART(guard_object) && 151278724Sdim old == INITIALISED) 152278724Sdim return 0; 153278724Sdim 154278724Sdim assert(old == LOCKED); 155278724Sdim // Another thread holds the lock. 156278724Sdim // If lock and init bit are in different words, check 157278724Sdim // if we are done before yielding and looping. 158278724Sdim if (INIT_PART(guard_object) != LOCK_PART(guard_object) && 159278724Sdim INITIALISED == *INIT_PART(guard_object)) 160278724Sdim return 0; 161278724Sdim sched_yield(); 162227972Stheraven } 163227972Stheraven} 164227972Stheraven 165227972Stheraven/** 166227972Stheraven * Releases the lock without marking the object as initialised. This function 167227972Stheraven * is called if initialising a static causes an exception to be thrown. 168227972Stheraven */ 169253159Stheravenextern "C" void __cxa_guard_abort(volatile guard_t *guard_object) 170227972Stheraven{ 171253159Stheraven __attribute__((unused)) 172278724Sdim bool reset = __sync_bool_compare_and_swap(LOCK_PART(guard_object), 173278724Sdim LOCKED, INITIAL); 174253159Stheraven assert(reset); 175227972Stheraven} 176227972Stheraven/** 177227972Stheraven * Releases the guard and marks the object as initialised. This function is 178227972Stheraven * called after successful initialisation of a static. 179227972Stheraven */ 180253159Stheravenextern "C" void __cxa_guard_release(volatile guard_t *guard_object) 181227972Stheraven{ 182278724Sdim guard_lock_t old; 183278724Sdim if (INIT_PART(guard_object) == LOCK_PART(guard_object)) 184278724Sdim old = LOCKED; 185278724Sdim else 186278724Sdim old = INITIAL; 187253159Stheraven __attribute__((unused)) 188278724Sdim bool reset = __sync_bool_compare_and_swap(INIT_PART(guard_object), 189278724Sdim old, INITIALISED); 190253159Stheraven assert(reset); 191278724Sdim if (INIT_PART(guard_object) != LOCK_PART(guard_object)) 192278724Sdim *LOCK_PART(guard_object) = INITIAL; 193227972Stheraven} 194