libgo/runtime/sema.goc

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Semaphore implementation exposed to Go.
   6 // Intended use is provide a sleep and wakeup
   7 // primitive that can be used in the contended case
   8 // of other synchronization primitives.
   9 // Thus it targets the same goal as Linux's futex,
  10 // but it has much simpler semantics.
  11 //
  12 // That is, don't think of these as semaphores.
  13 // Think of them as a way to implement sleep and wakeup
  14 // such that every sleep is paired with a single wakeup,
  15 // even if, due to races, the wakeup happens before the sleep.
  16 //
  17 // See Mullender and Cox, ``Semaphores in Plan 9,''
  18 // http://swtch.com/semaphore.pdf
  19
  20 package sync
  21 #include "runtime.h"
  22 #include "arch.h"
  23
  24 typedef struct Sema Sema;
  25 struct Sema
  26 {
  27         uint32 volatile*        addr;
  28         G*      g;
  29         int64   releasetime;
  30         Sema*   prev;
  31         Sema*   next;
  32 };
  33
  34 typedef struct SemaRoot SemaRoot;
  35 struct SemaRoot
  36 {
  37         Lock;
  38         Sema*   head;
  39         Sema*   tail;
  40         // Number of waiters. Read w/o the lock.
  41         uint32 volatile nwait;
  42 };
  43
  44 // Prime to not correlate with any user patterns.
  45 #define SEMTABLESZ 251
  46
  47 union semtable
  48 {
  49         SemaRoot;
  50         uint8 pad[CacheLineSize];
  51 };
  52 static union semtable semtable[SEMTABLESZ];
  53
  54 static SemaRoot*
  55 semroot(uint32 volatile *addr)
  56 {
  57         return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
  58 }
  59
  60 static void
  61 semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s)
  62 {
  63         s->g = runtime_g();
  64         s->addr = addr;
  65         s->next = nil;
  66         s->prev = root->tail;
  67         if(root->tail)
  68                 root->tail->next = s;
  69         else
  70                 root->head = s;
  71         root->tail = s;
  72 }
  73
  74 static void
  75 semdequeue(SemaRoot *root, Sema *s)
  76 {
  77         if(s->next)
  78                 s->next->prev = s->prev;
  79         else
  80                 root->tail = s->prev;
  81         if(s->prev)
  82                 s->prev->next = s->next;
  83         else
  84                 root->head = s->next;
  85         s->prev = nil;
  86         s->next = nil;
  87 }
  88
  89 static int32
  90 cansemacquire(uint32 volatile *addr)
  91 {
  92         uint32 v;
  93
  94         while((v = runtime_atomicload(addr)) > 0)
  95                 if(runtime_cas(addr, v, v-1))
  96                         return 1;
  97         return 0;
  98 }
  99
 100 static void
 101 semacquireimpl(uint32 volatile *addr, int32 profile)
 102 {
 103         Sema s; // Needs to be allocated on stack, otherwise garbage collector could deallocate it
 104         SemaRoot *root;
 105         int64 t0;
 106
 107         // Easy case.
 108         if(cansemacquire(addr))
 109                 return;
 110
 111         // Harder case:
 112         //      increment waiter count
 113         //      try cansemacquire one more time, return if succeeded
 114         //      enqueue itself as a waiter
 115         //      sleep
 116         //      (waiter descriptor is dequeued by signaler)
 117         root = semroot(addr);
 118         t0 = 0;
 119         s.releasetime = 0;
 120         if(profile && runtime_blockprofilerate > 0) {
 121                 t0 = runtime_cputicks();
 122                 s.releasetime = -1;
 123         }
 124         for(;;) {
 125
 126                 runtime_lock(root);
 127                 // Add ourselves to nwait to disable "easy case" in semrelease.
 128                 runtime_xadd(&root->nwait, 1);
 129                 // Check cansemacquire to avoid missed wakeup.
 130                 if(cansemacquire(addr)) {
 131                         runtime_xadd(&root->nwait, -1);
 132                         runtime_unlock(root);
 133                         return;
 134                 }
 135                 // Any semrelease after the cansemacquire knows we're waiting
 136                 // (we set nwait above), so go to sleep.
 137                 semqueue(root, addr, &s);
 138                 runtime_park(runtime_unlock, root, "semacquire");
 139                 if(cansemacquire(addr)) {
 140                         if(t0)
 141                                 runtime_blockevent(s.releasetime - t0, 3);
 142                         return;
 143                 }
 144         }
 145 }
 146
 147 void
 148 runtime_semacquire(uint32 volatile *addr)
 149 {
 150         semacquireimpl(addr, 0);
 151 }
 152
 153 void
 154 runtime_semrelease(uint32 volatile *addr)
 155 {
 156         Sema *s;
 157         SemaRoot *root;
 158
 159         root = semroot(addr);
 160         runtime_xadd(addr, 1);
 161
 162         // Easy case: no waiters?
 163         // This check must happen after the xadd, to avoid a missed wakeup
 164         // (see loop in semacquire).
 165         if(runtime_atomicload(&root->nwait) == 0)
 166                 return;
 167
 168         // Harder case: search for a waiter and wake it.
 169         runtime_lock(root);
 170         if(runtime_atomicload(&root->nwait) == 0) {
 171                 // The count is already consumed by another goroutine,
 172                 // so no need to wake up another goroutine.
 173                 runtime_unlock(root);
 174                 return;
 175         }
 176         for(s = root->head; s; s = s->next) {
 177                 if(s->addr == addr) {
 178                         runtime_xadd(&root->nwait, -1);
 179                         semdequeue(root, s);
 180                         break;
 181                 }
 182         }
 183         runtime_unlock(root);
 184         if(s) {
 185                 if(s->releasetime)
 186                         s->releasetime = runtime_cputicks();
 187                 runtime_ready(s->g);
 188         }
 189 }
 190
 191 func runtime_Semacquire(addr *uint32) {
 192         semacquireimpl(addr, 1);
 193 }
 194
 195 func runtime_Semrelease(addr *uint32) {
 196         runtime_semrelease(addr);
 197 }