1 krisbash 1.1 #include "lock.h"
  2              #include "atomic.h"
  3              #include "thread.h"
  4              #include "cpu.h"
  5              
  6              #if defined(PAL_64BIT)
  7              # define FIELD_SIZE 13
  8              # define FIELD_MAX 0x1fff
  9              # define FIELD_SIGN 0x1000
 10              # define SPIN_SIZE 8
 11              # define SPIN_MAX 0xff
 12              # define SPIN_SIGN 0x80
 13              #elif defined(PAL_32BIT)
 14              # define FIELD_SIZE 6
 15              # define FIELD_MAX 0x3f
 16              # define FIELD_SIGN 0x20
 17              # define SPIN_SIZE 4
 18              # define SPIN_MAX 0xf
 19              # define SPIN_SIGN 0x8
 20              #else
 21              # error "unknown pointer size"
 22 krisbash 1.1 #endif /* 32/64 bit */
 23              
 24              #define OWN_MAXSHARED (FIELD_MAX - 1)
 25              #define OWN_EXCLUSIVE FIELD_MAX
 26              #define CurrentTick() CPU_GetTimeStamp()
 27              
 28              #if defined(_MSC_VER)
 29              #pragma warning(disable:4214)
 30              #endif
 31              
 32              typedef struct _LockFields
 33              {
 34                  size_t owners : FIELD_SIZE;
 35                  size_t unfair : 4;
 36                  size_t spin   : SPIN_SIZE;
 37                  size_t entry  : FIELD_SIZE;
 38                  size_t writer : FIELD_SIZE;
 39                  size_t exit   : FIELD_SIZE;
 40              } LockFields;
 41              
 42              #define LockState(p)  ((ptrdiff_t*)p)
 43 krisbash 1.1 #define ReadLockState(p) PAL_PREFETCH((volatile ptrdiff_t*)(p))
 44              #define LockOwners(x) (((LockFields*)&x)->owners)
 45              #define LockUnfair(x) (((LockFields*)&x)->unfair)
 46              #define LockSpin(x)   (((LockFields*)&x)->spin)
 47              #define LockEntry(x)  (((LockFields*)&x)->entry)
 48              #define LockWriter(x) (((LockFields*)&x)->writer)
 49              #define LockExit(x)   (((LockFields*)&x)->exit)
 50              
 51              static int TryAcquireRead(
 52                  _Inout_ ReadWriteLock* self
 53              )
 54              {
 55                  volatile LockFields* lock = (LockFields*)self;
 56                  size_t oldState, state, swapState;
 57              
 58                  for(;;)
 59                  {
 60                      oldState = ReadLockState(lock);
 61                      state = oldState + 1;
 62              
 63                      /* Skipped when owners is the only active field
 64 krisbash 1.1          * and we did not try to add too many shared owners. */
 65                      if (state >= OWN_EXCLUSIVE)
 66                      {
 67                          /* Detect whether adding another shared owner is impossible. */
 68                          if (LockOwners(oldState) >= OWN_MAXSHARED)
 69                              return 0;
 70              
 71                          /* If writer == exit, no writers are waiting. */
 72                          if ((LockWriter(state) ^ LockExit(state)) != 0)
 73                          {
 74                              /* Writers are waiting. Acquiring would jump the queue. */
 75                              if (((CurrentTick() - LockUnfair(oldState)) & 14) != 0)
 76                                  return 0;
 77                          }
 78                      }
 79              
 80                      /* Ready to take shared ownership. */
 81                      swapState = Atomic_CompareAndSwap(LockState(lock), oldState, state);
 82                      if (swapState == oldState)
 83                          return 1;
 84                  }
 85 krisbash 1.1 }
 86              
 87              static int TryAcquireWrite(
 88                  _Inout_ ReadWriteLock* self
 89              )
 90              {
 91                  volatile LockFields* lock = (LockFields*)self;
 92                  size_t oldState, state, swapState;
 93              
 94                  for(;;)
 95                  {
 96                      oldState = ReadLockState(lock);
 97                      state = oldState | OWN_EXCLUSIVE;
 98              
 99                      /* Skipped when the lock is empty. */
100                      if (oldState != 0)
101                      {
102                          /* Detect whether there are existing owners. */
103                          if (LockOwners(oldState) != 0)
104                              return 0;
105              
106 krisbash 1.1             /* Someone must be waiting. Acquiring would jump the queue. */
107                          if (((CurrentTick() - LockUnfair(oldState)) & 14) != 0)
108                              return 0;
109                      }
110              
111                      /* Ready to take exclusive ownership. */
112                      swapState = Atomic_CompareAndSwap(LockState(lock), oldState, state);
113                      if (swapState == oldState)
114                          return 1;
115                  }
116              }
117              
118              static void QueueAcquireRead(
119                  _Inout_ ReadWriteLock* self
120              )
121              {
122                  volatile LockFields* lock = (LockFields*)self;
123                  size_t oldState, state, swapState, preQueuedState;
124                  size_t waitFor, diff, key, spinState, spinCount;
125              
126                  for (;;)
127 krisbash 1.1     {
128                      oldState = ReadLockState(lock);
129                      state = oldState;
130              
131                      /* If there is no queue, we are the first one to wait;
132                       * allow unfairness for the current timer tick. */
133                      if (state <= OWN_EXCLUSIVE)
134                          LockUnfair(state) = CurrentTick();
135              
136                      /* Insert a barrier every half revolution.
137                       * This stops writer arithmetic from wrapping. */
138                      if ((LockEntry(state) & ~FIELD_SIGN) == 0)
139                          LockWriter(state) = LockEntry(state);
140              
141                      if (++LockEntry(state) == LockExit(state))
142                      {
143                          /* The queue arithmetic will wrap if we continue. */
144                          Thread_Yield();
145                          continue;
146                      }
147              
148 krisbash 1.1         swapState = Atomic_CompareAndSwap(LockState(lock), oldState, state);
149                      if (swapState == oldState)
150                          break;
151                  }
152              
153                  /* This thread now has a place in the queue.
154                   * Threads behind us may be depending on us to wake them up. */
155              
156                  /* Wait for the most recent writer to enter the queue. */
157                  waitFor = LockWriter(state);
158                  key = (size_t)lock ^ waitFor;
159                  preQueuedState = oldState;
160                  spinState = LockSpin(oldState);
161              
162                  for (;;)
163                  {
164                      /* Avoid write prefetching since we expect to wait. */
165                      oldState = *(ptrdiff_t*)lock;
166              
167                      diff = LockExit(oldState) - waitFor;
168                      if ((diff & FIELD_SIGN) == 0)
169 krisbash 1.1         {
170                          /* The writer ahead of us in line already acquired.
171                           * Someone could have beat us unfairly.
172                           * Just wait for the current owner. */
173                          waitFor = LockExit(oldState);
174                          key = (size_t)lock ^ waitFor;
175                      }
176              
177                      if ((diff & FIELD_SIGN) != 0 || (LockOwners(oldState) == OWN_EXCLUSIVE))
178                      {
179                          /* The writer ahead of us still hasn't acquired,
180                           * or someone owns the lock exclusively right now. */
181                          if (((CurrentTick() - LockUnfair(oldState)) & 14) == 0 &&
182                              LockEntry(oldState) - LockExit(oldState) >= 2 &&
183                              LockEntry(oldState) == LockEntry(preQueuedState) + 1 &&
184                              (LockOwners(oldState) < OWN_MAXSHARED))
185                          {
186                              /* Under certain conditions, we can acquire immediately if we
187                               * are the last thread in line and undo joining the queue. */
188                              if (preQueuedState <= OWN_EXCLUSIVE)
189                                  state = LockOwners(oldState) + 1;
190 krisbash 1.1                 else
191                              {
192                                  state = oldState + 1;
193                                  LockEntry(state) = LockEntry(preQueuedState);
194                                  LockWriter(state) = LockWriter(preQueuedState);
195                              }
196              
197                              /* Atomically de-queue and acquire unfairly. */
198                              swapState = Atomic_CompareAndSwap(LockState(lock), oldState, state);
199                              if (swapState == oldState)
200                                  return;
201                              continue;
202                          }
203              
204                          /* spinState being low means spinning usually works.
205                           * Use a high count if it has been working recently. */
206                          spinCount = (spinState & SPIN_SIGN) ?
207                              CONDLOCK_LOW_SPINCOUNT :
208                              CONDLOCK_HIGH_SPINCOUNT;
209              
210                          /* Spin and/or block until something changes.
211 krisbash 1.1              * Adjust the spin field based on whether spinning worked. */
212                          if (CondLock_Wait(key, (ptrdiff_t*)lock, oldState, spinCount))
213                              spinState = (spinState > 2) ? (spinState - 2) : 0;
214                          else
215                              spinState = (spinState < SPIN_MAX) ? (spinState + 1) : spinState;
216                          continue;
217                      }
218                      
219                      if (LockOwners(oldState) == OWN_MAXSHARED)
220                      {
221                          /* The owner arithmetic will overflow if we continue. */
222                          Thread_Yield();
223                          continue;
224                      }
225              
226                      state = oldState + 1;
227              
228                      /* Bump the exit ticket number. We're leaving the queue. */
229                      LockExit(state)++;
230              
231                      /* Zero the top 4 fields if the queue is now empty. */
232 krisbash 1.1         if (LockExit(state) == LockEntry(state))
233                          state = LockOwners(state);
234                      else
235                      {
236                          /* Not empty, but we just acquired fairly.
237                           * Allow unfairness for a while. */
238                          LockUnfair(state) = CurrentTick();
239                          LockSpin(state) = spinState;
240                      }
241              
242                      /* Ready to take shared ownership. */
243                      swapState = Atomic_CompareAndSwap(LockState(lock), oldState, state);
244                      if (swapState == oldState)
245                          break;
246                  }
247              
248                  if ((LockExit(state) & ~FIELD_SIGN) == 0)
249                  {
250                      /* Wakes those waiting on the artificial barrier inserted each half
251                       * revolution (see above). */
252                      key = (size_t)lock ^ LockExit(state);
253 krisbash 1.1         CondLock_Broadcast(key);
254                  }
255              }
256              
257              static void QueueAcquireWrite(
258                  _Inout_ ReadWriteLock* self
259              )
260              {
261                  volatile LockFields* lock = (LockFields*)self;
262                  size_t oldState, state, swapState, preQueuedState;
263                  size_t waitFor, key, spinState, spinCount;
264              
265                  for (;;)
266                  {
267                      oldState = ReadLockState(lock);
268                      state = oldState;
269              
270                      /* If there is no queue, we are the first one to wait;
271                       * allow unfairness for the current timer tick. */
272                      if (state <= OWN_EXCLUSIVE)
273                          LockUnfair(state) = CurrentTick();
274 krisbash 1.1 
275                      /* Wait for the most recent thread to enter the queue. */
276                      waitFor = LockEntry(state);
277              
278                      if (++LockEntry(state) == LockExit(state))
279                      {
280                          /* The queue arithmetic will wrap if we continue. */
281                          Thread_Yield();
282                          continue;
283                      }
284              
285                      /* Make reader threads coming in wait for us. */
286                      LockWriter(state) = LockEntry(state);
287              
288                      swapState = Atomic_CompareAndSwap(LockState(lock), oldState, state);
289                      if (swapState == oldState)
290                          break;
291                  }
292              
293                  /* This thread now has a place in the queue.
294                   * Threads behind us may be depending on us to wake them up. */
295 krisbash 1.1 
296                  preQueuedState = oldState;
297                  key = (size_t)lock ^ waitFor;
298                  spinState = LockSpin(oldState);
299              
300                  for (;;)
301                  {
302                      /* Avoid write prefetching since we expect to wait. */
303                      oldState = *(ptrdiff_t*)lock;
304              
305                      if (LockExit(oldState) != waitFor || LockOwners(oldState) != 0)
306                      {
307                          /* The thread ahead of us still hasn't acquired,
308                           * or some reader or writer owns the lock right now. */
309                          if (((CurrentTick() - LockUnfair(oldState)) & 14) == 0 &&
310                              LockEntry(oldState) - LockExit(oldState) >= 2 &&
311                              LockEntry(oldState) == LockEntry(preQueuedState) + 1 &&
312                              LockOwners(oldState) == 0)
313                          {
314                              /* Under certain conditions, we can acquire immediately if we
315                               * are the last thread in line and undo joining the queue. */
316 krisbash 1.1                 if (preQueuedState <= OWN_EXCLUSIVE)
317                                  state = OWN_EXCLUSIVE;
318                              else
319                              {
320                                  state = oldState + OWN_EXCLUSIVE;
321                                  LockEntry(state) = LockEntry(preQueuedState);
322                                  LockWriter(state) = LockWriter(preQueuedState);
323                              }
324              
325                              /* Atomically de-queue and acquire unfairly. */
326                              swapState = Atomic_CompareAndSwap(LockState(lock), oldState, state);
327                              if (swapState == oldState)
328                                  return;
329                              continue;
330                          }
331              
332                          /* spinState being low means spinning usually works.
333                           * Use a high count if it has been working recently. */
334                          spinCount = (spinState & SPIN_SIGN) ?
335                              CONDLOCK_LOW_SPINCOUNT :
336                              CONDLOCK_HIGH_SPINCOUNT;
337 krisbash 1.1 
338                          /* Spin and/or block until something changes.
339                           * Adjust the spin field based on whether spinning worked. */
340                          if (CondLock_Wait(key, (ptrdiff_t*)lock, oldState, spinCount))
341                              spinState = (spinState > 2) ? (spinState - 2) : 0;
342                          else
343                              spinState = (spinState < SPIN_MAX) ? (spinState + 1) : spinState;
344                          continue;
345                      }
346              
347                      state = oldState + OWN_EXCLUSIVE;
348              
349                      /* Bump the exit ticket number. We're leaving the queue. */
350                      LockExit(state)++;
351              
352                      /* Zero the top 4 fields if the queue is now empty. */
353                      if (LockExit(state) == LockEntry(state))
354                          state = LockOwners(state);
355                      else
356                      {
357                          /* Not empty, but we just acquired fairly.
358 krisbash 1.1              * Allow unfairness for a while. */
359                          LockUnfair(state) = CurrentTick();
360                          LockSpin(state) = spinState;
361                      }
362              
363                      /* Ready to take exclusive ownership. */
364                      swapState = Atomic_CompareAndSwap(LockState(lock), oldState, state);
365                      if (swapState == oldState)
366                          return;
367                  }
368              }
369              
370              int ReadWriteLock_TryAcquireRead(
371                  _Inout_ ReadWriteLock* self
372              )
373              {
374                  return TryAcquireRead(self);
375              }
376              
377              void ReadWriteLock_AcquireRead(
378                  _Inout_ ReadWriteLock* self
379 krisbash 1.1 )
380              {
381                  if (TryAcquireRead(self) != 0)
382                      return;
383              
384                  QueueAcquireRead(self);
385              }
386              
387              int ReadWriteLock_TryAcquireWrite(
388                  _Inout_ ReadWriteLock* self
389              )
390              {
391                  return TryAcquireWrite(self);
392              }
393              
394              void ReadWriteLock_AcquireWrite(
395                  _Inout_ ReadWriteLock* self)
396              {
397                  if (TryAcquireWrite(self) != 0)
398                      return;
399              
400 krisbash 1.1     QueueAcquireWrite(self);
401              }
402              
403              void ReadWriteLock_ReleaseRead(
404                  _Inout_ ReadWriteLock* self)
405              {
406                  volatile LockFields* lock = (LockFields*)self;
407                  size_t state, key;
408              
409                  state = Atomic_Dec(LockState(lock));
410                  if (state >= OWN_EXCLUSIVE && LockOwners(state) == 0)
411                  {
412                      /* There is a queue.
413                       * Writers may be blocked waiting for us to leave. */
414                      key = (size_t)lock ^ LockExit(state);
415                      CondLock_Broadcast(key);
416              
417                      //if (((LockEntry(state) - LockExit(state)) & (FIELD_SIZE - 1)) == 2 &&
418                      if (LockEntry(state) - LockExit(state) >= 2 &&
419                          ((CurrentTick() - LockUnfair(state)) & 14) == 0)
420                      {
421 krisbash 1.1             /* Under certain conditions, encourage the last group of threads in
422                           * line to stop spinning and acquire unfairly. */
423                          if (LockEntry(state) == LockWriter(state))
424                              key = (size_t)lock ^ (LockEntry(state) - 1);
425                          else
426                              key = (size_t)lock ^ LockWriter(state);
427                          CondLock_BroadcastSpinners(key);
428                      }
429                  }
430              }
431              
432              void ReadWriteLock_ReleaseWrite(
433                  _Inout_ ReadWriteLock* self)
434              {
435                  volatile LockFields* lock = (LockFields*)self;
436                  size_t state, key;
437              
438                  state = Atomic_Add(LockState(lock), -OWN_EXCLUSIVE);
439                  if (state != 0)
440                  {
441                      /* There is a queue.
442 krisbash 1.1          * Threads may be blocked waiting for us to leave. */
443                      key = (size_t)lock ^ LockExit(state);
444                      CondLock_Broadcast(key);
445              
446                      //if (((LockEntry(state) - LockExit(state)) & (FIELD_SIZE - 1)) == 2 &&
447                      if (LockEntry(state) - LockExit(state) >= 2 &&
448                          ((CurrentTick() - LockUnfair(state)) & 14) == 0)
449                      {
450                          /* Under certain conditions, encourage the last group of threads in
451                           * line to stop spinning and acquire unfairly. */
452                          if (LockEntry(state) == LockWriter(state))
453                              key = (size_t)lock ^ (LockEntry(state) - 1);
454                          else
455                              key = (size_t)lock ^ LockWriter(state);
456                          CondLock_BroadcastSpinners(key);
457                      }
458                  }
459              }