libkern/gen/OSAtomicOperations.c

   1 /*
   2  * Copyright (c) 2000-2006 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #include <libkern/OSAtomic.h>
  30
  31 enum {
  32         false   = 0,
  33         true    = 1
  34 };
  35
  36 #ifndef NULL
  37 #define NULL ((void *)0)
  38 #endif
  39
  40 /*
  41  * atomic operations
  42  *      these are _the_ atomic operations, currently cast atop CompareAndSwap,
  43  *      which is implemented in assembler.      if we are worried about the cost of
  44  *      this layering (we shouldn't be), then all this stuff could be
  45  *      implemented in assembler, as it is in MacOS8/9
  46  *      (derived from SuperMario/NativeLibs/IO/DriverServices/Synchronization.s,
  47  *      which I wrote for NuKernel in a previous life with a different last name...)
  48  *
  49  * native Boolean       CompareAndSwap(UInt32 oldValue, UInt32 newValue, UInt32 * oldValuePtr);
  50  *
  51  * We've since implemented a few more of these -- OSAddAtomic, OSDequeueAtomic,
  52  * OSEnqueueAtomic etc -- in assembler, either for speed or correctness.  See also the
  53  * commpage atomic operations, and the platform specific versions.
  54  * Like standards, there are a lot of atomic ops to choose from!
  55  */
  56
  57 #ifndef __ppc__
  58
  59
  60 SInt32  OSIncrementAtomic(volatile SInt32 * value)
  61 {
  62         return OSAddAtomic(1, value);
  63 }
  64
  65 SInt32  OSDecrementAtomic(volatile SInt32 * value)
  66 {
  67         return OSAddAtomic(-1, value);
  68 }
  69
  70 #ifdef CMPXCHG8B
  71 void *  OSDequeueAtomic(void * volatile * inList, SInt32 inOffset)
  72 {
  73         /* The _pointer_ is volatile, not the listhead itself */
  74         void * volatile oldListHead;
  75         void * volatile newListHead;
  76
  77         do {
  78                 oldListHead = *inList;
  79                 if (oldListHead == NULL) {
  80                         break;
  81                 }
  82
  83                 newListHead = *(void * volatile *) (((char *) oldListHead) + inOffset);
  84         } while (! OSCompareAndSwap((UInt32)oldListHead,
  85                                         (UInt32)newListHead, (volatile UInt32 *)inList));
  86         return oldListHead;
  87 }
  88
  89 void    OSEnqueueAtomic(void * volatile * inList, void * inNewLink, SInt32 inOffset)
  90 {
  91         /* The _pointer_ is volatile, not the listhead itself */
  92         void * volatile oldListHead;
  93         void * volatile newListHead = inNewLink;
  94         void * volatile * newLinkNextPtr = (void * volatile *) (((char *) inNewLink) + inOffset);
  95
  96         do {
  97                 oldListHead = *inList;
  98                 *newLinkNextPtr = oldListHead;
  99         } while (! OSCompareAndSwap((UInt32)oldListHead, (UInt32)newListHead,
 100                                         (volatile UInt32 *)inList));
 101 }
 102 #endif /* CMPXCHG8B */
 103 #endif  /* !__ppc__ */
 104
 105 static UInt32   OSBitwiseAtomic(UInt32 and_mask, UInt32 or_mask, UInt32 xor_mask, volatile UInt32 * value)
 106 {
 107         UInt32  oldValue;
 108         UInt32  newValue;
 109
 110         do {
 111                 oldValue = *value;
 112                 newValue = ((oldValue & and_mask) | or_mask) ^ xor_mask;
 113         } while (! OSCompareAndSwap(oldValue, newValue, value));
 114
 115         return oldValue;
 116 }
 117
 118 UInt32  OSBitAndAtomic(UInt32 mask, volatile UInt32 * value)
 119 {
 120         return OSBitwiseAtomic(mask, 0, 0, value);
 121 }
 122
 123 UInt32  OSBitOrAtomic(UInt32 mask, volatile UInt32 * value)
 124 {
 125         return OSBitwiseAtomic((UInt32) -1, mask, 0, value);
 126 }
 127
 128 UInt32  OSBitXorAtomic(UInt32 mask, volatile UInt32 * value)
 129 {
 130         return OSBitwiseAtomic((UInt32) -1, 0, mask, value);
 131 }
 132
 133 static Boolean OSCompareAndSwap8(UInt8 oldValue8, UInt8 newValue8, volatile UInt8 * value8)
 134 {
 135         UInt32                          mask            = 0x000000ff;
 136         UInt32                          alignment       = ((UInt32) value8) & (sizeof(UInt32) - 1);
 137         UInt32                          shiftValues = (24 << 24) | (16 << 16) | (8 << 8);
 138         int                                     shift           = (UInt32) *(((UInt8 *) &shiftValues) + alignment);
 139         volatile UInt32 *       value32         = (volatile UInt32 *) (value8 - alignment);
 140         UInt32                          oldValue;
 141         UInt32                          newValue;
 142
 143         mask <<= shift;
 144
 145         oldValue = *value32;
 146         oldValue = (oldValue & ~mask) | (oldValue8 << shift);
 147         newValue = (oldValue & ~mask) | (newValue8 << shift);
 148
 149         return OSCompareAndSwap(oldValue, newValue, value32);
 150 }
 151
 152 static Boolean  OSTestAndSetClear(UInt32 bit, Boolean wantSet, volatile UInt8 * startAddress)
 153 {
 154         UInt8           mask = 1;
 155         UInt8           oldValue;
 156         UInt8           wantValue;
 157
 158         startAddress += (bit / 8);
 159         mask <<= (7 - (bit % 8));
 160         wantValue = wantSet ? mask : 0;
 161
 162         do {
 163                 oldValue = *startAddress;
 164                 if ((oldValue & mask) == wantValue) {
 165                         break;
 166                 }
 167         } while (! OSCompareAndSwap8(oldValue, (oldValue & ~mask) | wantValue, startAddress));
 168
 169         return (oldValue & mask) == wantValue;
 170 }
 171
 172 Boolean OSTestAndSet(UInt32 bit, volatile UInt8 * startAddress)
 173 {
 174         return OSTestAndSetClear(bit, true, startAddress);
 175 }
 176
 177 Boolean OSTestAndClear(UInt32 bit, volatile UInt8 * startAddress)
 178 {
 179         return OSTestAndSetClear(bit, false, startAddress);
 180 }
 181
 182 /*
 183  * silly unaligned versions
 184  */
 185
 186 SInt8   OSIncrementAtomic8(volatile SInt8 * value)
 187 {
 188         return OSAddAtomic8(1, value);
 189 }
 190
 191 SInt8   OSDecrementAtomic8(volatile SInt8 * value)
 192 {
 193         return OSAddAtomic8(-1, value);
 194 }
 195
 196 SInt8   OSAddAtomic8(SInt32 amount, volatile SInt8 * value)
 197 {
 198         SInt8   oldValue;
 199         SInt8   newValue;
 200
 201         do {
 202                 oldValue = *value;
 203                 newValue = oldValue + amount;
 204         } while (! OSCompareAndSwap8((UInt8) oldValue, (UInt8) newValue, (volatile UInt8 *) value));
 205
 206         return oldValue;
 207 }
 208
 209 static UInt8    OSBitwiseAtomic8(UInt32 and_mask, UInt32 or_mask, UInt32 xor_mask, volatile UInt8 * value)
 210 {
 211         UInt8   oldValue;
 212         UInt8   newValue;
 213
 214         do {
 215                 oldValue = *value;
 216                 newValue = ((oldValue & and_mask) | or_mask) ^ xor_mask;
 217         } while (! OSCompareAndSwap8(oldValue, newValue, value));
 218
 219         return oldValue;
 220 }
 221
 222 UInt8   OSBitAndAtomic8(UInt32 mask, volatile UInt8 * value)
 223 {
 224         return OSBitwiseAtomic8(mask, 0, 0, value);
 225 }
 226
 227 UInt8   OSBitOrAtomic8(UInt32 mask, volatile UInt8 * value)
 228 {
 229         return OSBitwiseAtomic8((UInt32) -1, mask, 0, value);
 230 }
 231
 232 UInt8   OSBitXorAtomic8(UInt32 mask, volatile UInt8 * value)
 233 {
 234         return OSBitwiseAtomic8((UInt32) -1, 0, mask, value);
 235 }
 236
 237 static Boolean OSCompareAndSwap16(UInt16 oldValue16, UInt16 newValue16, volatile UInt16 * value16)
 238 {
 239         UInt32                          mask            = 0x0000ffff;
 240         UInt32                          alignment       = ((UInt32) value16) & (sizeof(UInt32) - 1);
 241         UInt32                          shiftValues = (16 << 24) | (16 << 16);
 242         UInt32                          shift           = (UInt32) *(((UInt8 *) &shiftValues) + alignment);
 243         volatile UInt32 *       value32         = (volatile UInt32 *) (((UInt32) value16) - alignment);
 244         UInt32                          oldValue;
 245         UInt32                          newValue;
 246
 247         mask <<= shift;
 248
 249         oldValue = *value32;
 250         oldValue = (oldValue & ~mask) | (oldValue16 << shift);
 251         newValue = (oldValue & ~mask) | (newValue16 << shift);
 252
 253         return OSCompareAndSwap(oldValue, newValue, value32);
 254 }
 255
 256 SInt16  OSIncrementAtomic16(volatile SInt16 * value)
 257 {
 258         return OSAddAtomic16(1, value);
 259 }
 260
 261 SInt16  OSDecrementAtomic16(volatile SInt16 * value)
 262 {
 263         return OSAddAtomic16(-1, value);
 264 }
 265
 266 SInt16  OSAddAtomic16(SInt32 amount, volatile SInt16 * value)
 267 {
 268         SInt16  oldValue;
 269         SInt16  newValue;
 270
 271         do {
 272                 oldValue = *value;
 273                 newValue = oldValue + amount;
 274         } while (! OSCompareAndSwap16((UInt16) oldValue, (UInt16) newValue, (volatile UInt16 *) value));
 275
 276         return oldValue;
 277 }
 278
 279 static UInt16   OSBitwiseAtomic16(UInt32 and_mask, UInt32 or_mask, UInt32 xor_mask, volatile UInt16 * value)
 280 {
 281         UInt16  oldValue;
 282         UInt16  newValue;
 283
 284         do {
 285                 oldValue = *value;
 286                 newValue = ((oldValue & and_mask) | or_mask) ^ xor_mask;
 287         } while (! OSCompareAndSwap16(oldValue, newValue, value));
 288
 289         return oldValue;
 290 }
 291
 292 UInt16  OSBitAndAtomic16(UInt32 mask, volatile UInt16 * value)
 293 {
 294         return OSBitwiseAtomic16(mask, 0, 0, value);
 295 }
 296
 297 UInt16  OSBitOrAtomic16(UInt32 mask, volatile UInt16 * value)
 298 {
 299         return OSBitwiseAtomic16((UInt32) -1, mask, 0, value);
 300 }
 301
 302 UInt16  OSBitXorAtomic16(UInt32 mask, volatile UInt16 * value)
 303 {
 304         return OSBitwiseAtomic16((UInt32) -1, 0, mask, value);
 305 }
 306