1 krisbash 1.1 #include <stdlib.h>
  2              #include <malloc.h>
  3              #include "lock.h"
  4              #include "atomic.h"
  5              #include "sleep.h"
  6              #include "cpu.h"
  7              #include "memory.h"
  8              
  9              #define CPU_MASK_UNINITIALIZED -1
 10              #define CACHE_LINE_SIZE 128
 11              #define LATCHES_PER_LINE 16
 12              #define POOL_FULL_MASK 0xffff
 13              #define POOL_LINES (s_cpuMask + 1)
 14              #define POOL_SIZE (sizeof(CachedLock_Pool) + CACHE_LINE_SIZE * (POOL_LINES + 1))
 15              
 16              #define ALIGN(x, size) (((x) + (size) - 1) & -(size))
 17              
 18              /* Number of separate cache lines, minus 1, for easy masking. */
 19              static int s_cpuMask = CPU_MASK_UNINITIALIZED;
 20              static ptrdiff_t s_masterMask = 0;
 21              static Lock s_latchPoolLock = LOCK_INITIALIZER;
 22 krisbash 1.1 static CachedLock_Pool* s_currentPool = NULL;
 23              
 24              #ifdef PAL_64BIT
 25              # define MASTER_INCREMENT ((ptrdiff_t)1 << 32)
 26              #else
 27              # define MASTER_INCREMENT ((ptrdiff_t)1 << 16)
 28              #endif
 29              
 30              #define MASTER_MASK (MASTER_INCREMENT - 1)
 31              
 32              static CachedLock_Pool* Pool_New()
 33              {
 34                  CachedLock_Pool* pool;
 35                  ptrdiff_t buffer;
 36              
 37                  /* The pool and all the latch lines are one block. */
 38                  pool = (CachedLock_Pool*)PAL_Malloc(POOL_SIZE);
 39                  if (pool == NULL)
 40                      return NULL;
 41              
 42                  /* buffer contains an extra cache line for manual alignment. */
 43 krisbash 1.1     buffer = (ptrdiff_t)(pool + 1);
 44                  buffer = ALIGN(buffer, CACHE_LINE_SIZE);
 45              
 46                  pool->latches = (ptrdiff_t*)buffer;
 47                  pool->mask = 0;
 48              
 49                  return pool;
 50              }
 51              
 52              static void Pool_Delete(
 53                  _In_ CachedLock_Pool* self
 54              )
 55              {
 56                  PAL_Free(self);
 57              }
 58              
 59              static void ATEXIT_API ShutdownCachePool(void)
 60              {
 61                  if (s_currentPool)
 62                      Pool_Delete(s_currentPool);
 63                  s_currentPool = NULL;
 64 krisbash 1.1 }
 65              
 66              static void InitializeCachePool()
 67              {
 68                  int cpus = CPU_GetCount();
 69              
 70                  /* Round up to the next power of two. */
 71                  if (cpus <= 1)
 72                      cpus = 1;
 73                  else if (cpus <= 2)
 74                      cpus = 2;
 75                  else if (cpus <= 4)
 76                      cpus = 4;
 77                  else if (cpus <= 8)
 78                      cpus = 8;
 79              #ifdef PAL_64BIT
 80                  else if (cpus > 16)
 81                      cpus = 32;
 82              #endif
 83                  else
 84                      cpus = 16;
 85 krisbash 1.1 
 86                  /* Everyone needs to mask off higher bits in case CPU_GetCurrent ever
 87                   * returns a number higher than it did now, or in case there are more than
 88                   * 32 CPUs. */
 89                  s_cpuMask = cpus - 1;
 90                  s_masterMask = ((ptrdiff_t)1 << cpus) - 1;
 91                  PAL_Atexit(ShutdownCachePool);
 92              }
 93              
 94              _Return_type_success_(return == 0) int CachedLock_Init_Checked(
 95                  _Out_ CachedLock* self,
 96                  unsigned long flags,
 97                  NitsCallSite cs
 98              )
 99              {
100                  CachedLock_Pool* pool;
101                  int index;
102                  ReadWriteLock temp = READWRITELOCK_INITIALIZER;
103              
104                  /* One-time initialization. Doesn't matter if called several times. */
105                  if (s_cpuMask == CPU_MASK_UNINITIALIZED)
106 krisbash 1.1         InitializeCachePool();
107              
108                  if (flags & CACHEDLOCK_FLAG_SHARED)
109                  {
110                      Lock_Acquire(&s_latchPoolLock);
111              
112                      if (NitsShouldFault(cs, NitsAutomatic))
113                          return -1;
114              
115                      if (s_currentPool == NULL ||
116                          s_currentPool->mask == POOL_FULL_MASK)
117                      {
118                          /* The current pool is full. */
119                          s_currentPool = Pool_New();
120                          if (s_currentPool == NULL)
121                              return -1;
122                      }
123              
124                      /* Search the pool for a zero bit. */
125                      pool = s_currentPool;
126                      for (index = 0; index < POOL_LINES; index++)
127 krisbash 1.1             if ((pool->mask & ((ptrdiff_t)1 << index)) == 0)
128                              break;
129              
130                      /* Take ownership of this index. */
131                      pool->mask |= ((ptrdiff_t)1 << index);
132                      Lock_Release(&s_latchPoolLock);
133                  }
134                  else
135                  {
136                      pool = Pool_New();
137                      if (pool == NULL)
138                          return -1;
139                      pool->mask = 1;
140                      index = 0;
141                  }
142              
143                  self->pool = pool;
144                  self->latches = pool->latches + index;
145                  self->lock = temp;
146                  self->master = 0;
147              
148 krisbash 1.1     return 0;
149              }
150              
151              void CachedLock_Destroy(
152                  _Inout_ CachedLock* self
153              )
154              {
155                  CachedLock_Pool* pool = self->pool;
156                  ptrdiff_t index = self->latches - self->pool->latches;
157              
158                  Lock_Acquire(&s_latchPoolLock);
159              
160                  /* Release ownership of our bit. */
161                  pool->mask &= ~((ptrdiff_t)1 << index);
162              
163                  /* Determine if this pool has been orphaned. */
164                  if (pool->mask == 0 && pool != s_currentPool)
165                      Pool_Delete(pool);
166              
167                  Lock_Release(&s_latchPoolLock);
168              }
169 krisbash 1.1 
170              static void ClearCPU(
171                  _Inout_ CachedLock* self,
172                  _Inout_ ptrdiff_t* latch)
173              {
174                  ptrdiff_t index = (latch - self->latches) / LATCHES_PER_LINE;
175              
176                  /* There are exclusive threads acquiring.
177                   * Mark this latch as empty in the central shared mask. */
178                  ptrdiff_t result = Atomic_And(&self->master, ~((ptrdiff_t)1 << index));
179              
180                  if ((result & MASTER_MASK) == 0)
181                      CondLock_Broadcast((ptrdiff_t)self);
182              }
183              
184              static int TryAcquireRead(
185                  _Inout_ CachedLock* self,
186                  _Out_   void** token
187              )
188              {
189                  volatile ptrdiff_t* master = &self->master;
190 krisbash 1.1     ptrdiff_t* latch;
191                  int cpu;
192              
193                  cpu = CPU_GetCurrent() & s_cpuMask;
194                  latch = self->latches + LATCHES_PER_LINE * cpu;
195              
196                  if (*master != 0)
197                  {
198                      /* Exclusive threads are already here. Short-circuit. */
199                      *token = NULL;
200                      return 0;
201                  }
202              
203                  Atomic_Inc(latch);
204              
205                  if (*master != 0)
206                  {
207                      /* Exclusive threads might have missed our increment. */
208                      if (Atomic_Dec(latch) == 0)
209                          ClearCPU(self, latch);
210                      *token = NULL;
211 krisbash 1.1         return 0;
212                  }
213                  
214                  /* Exclusive threads cannot miss that we are here. */
215                  *token = latch;
216                  return 1;
217              }
218              
219              void CachedLock_AcquireRead(
220                  _Inout_ CachedLock* self,
221                  _Out_   void** token
222              )
223              {
224                  if (TryAcquireRead(self, token) != 0)
225                      return;
226              
227                  ReadWriteLock_AcquireRead(&self->lock);
228              }
229              
230              void CachedLock_AcquireWrite(
231                  _Inout_ CachedLock* self
232 krisbash 1.1 )
233              {
234                  ptrdiff_t oldState, state, swapState;
235                  ptrdiff_t oldMask, zeroMask, index;
236                  volatile ptrdiff_t* master = &self->master;
237              
238                  /* The order of steps here is important.
239                   *  1) Stop shared readers from racing through the latches.
240                   *  2) Scan the latches to find inactive ones.
241                   *  3) Get exclusive access to the central lock.
242                   *  4) Wait for existing shared readers in the latches to leave.
243                   *
244                   * Doing (3) before (1) lets readers race through the latches if the
245                   *   central lock is still held by a reader from previous contention.
246                   * Doing (3) before (2) leads to deadlock if there are no active latches
247                   *   and another writer gets the central lock first.
248                   * Doing (3) after (4) lets readers race through the central lock. */
249              
250                  for (;;)
251                  {
252                      oldState = PAL_PREFETCH(master);
253 krisbash 1.1 
254                      /* The first thread atomically sets s_masterMask. */
255                      if (oldState == 0)
256                          state = s_masterMask + MASTER_INCREMENT;
257                      else
258                          state = oldState + MASTER_INCREMENT;
259              
260                      swapState = Atomic_CompareAndSwap(master, oldState, state);
261                      if (swapState == oldState)
262                          break;
263                  }
264              
265                  /* Reader threads will now observe that master != 0. */
266              
267                  if (oldState == 0)
268                  {
269                      /* This is the thread that set s_masterMask. */
270                      zeroMask = 0;
271                      for (index = 0; index < POOL_LINES; index++)
272                      {
273                          /* Determine if all shared threads are gone. */
274 krisbash 1.1             if (self->latches[LATCHES_PER_LINE * index] == 0)
275                              zeroMask |= ((ptrdiff_t)1 << index);
276                      }
277              
278                      /* Determine if there are any CPUs with shared threads remaining.
279                       * Other exclusive threads could be waiting. */
280                      if ((Atomic_And(master, ~zeroMask) & MASTER_MASK) == 0)
281                          CondLock_Broadcast((ptrdiff_t)self);
282                  }
283              
284                  ReadWriteLock_AcquireWrite(&self->lock);
285              
286                  for (;;)
287                  {
288                      /* Wait for all the latches to empty. */
289                      oldMask = *master;
290                      if ((oldMask & MASTER_MASK) == 0)
291                          return;
292              
293                      CondLock_Wait((ptrdiff_t)self, master, oldMask, CONDLOCK_DEFAULT_SPINCOUNT);
294                  }
295 krisbash 1.1 }
296              
297              void CachedLock_ReleaseRead(
298                  _Inout_ CachedLock* self,
299                  _In_    void* token
300              )
301              {
302                  ptrdiff_t* latch = (ptrdiff_t*)token;
303                  ptrdiff_t state;
304              
305                  if (latch == NULL)
306                  {
307                      /* This thread acquired the central lock, not a latch. */
308                      ReadWriteLock_ReleaseRead(&self->lock);
309                      return;
310                  }
311              
312                  /* Decrement the same latch that got incremented before. */
313                  state = Atomic_Dec(latch);
314                  if (state == 0 && self->master != 0)
315                      ClearCPU(self, latch);
316 krisbash 1.1 }
317              
318              void CachedLock_ReleaseWrite(
319                  _Inout_ CachedLock* self
320              )
321              {
322                  ReadWriteLock_ReleaseWrite(&self->lock);
323              
324                  /* Revert the increment that happened during Acquire. */
325                  Atomic_Add(&self->master, -MASTER_INCREMENT);
326              }