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 runtime
  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         Sema *prev;
  30         Sema *next;
  31 };
  32
  33 typedef struct SemaRoot SemaRoot;
  34 struct SemaRoot
  35 {
  36         Lock;
  37         Sema *head;
  38         Sema *tail;
  39         // Number of waiters. Read w/o the lock.
  40         uint32 volatile nwait;
  41 };
  42
  43 // Prime to not correlate with any user patterns.
  44 #define SEMTABLESZ 251
  45
  46 static union
  47 {
  48         SemaRoot;
  49         uint8 pad[CacheLineSize];
  50 } semtable[SEMTABLESZ];
  51
  52 static SemaRoot*
  53 semroot(uint32 volatile *addr)
  54 {
  55         return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
  56 }
  57
  58 static void
  59 semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s)
  60 {
  61         s->g = runtime_g();
  62         s->addr = addr;
  63         s->next = nil;
  64         s->prev = root->tail;
  65         if(root->tail)
  66                 root->tail->next = s;
  67         else
  68                 root->head = s;
  69         root->tail = s;
  70 }
  71
  72 static void
  73 semdequeue(SemaRoot *root, Sema *s)
  74 {
  75         if(s->next)
  76                 s->next->prev = s->prev;
  77         else
  78                 root->tail = s->prev;
  79         if(s->prev)
  80                 s->prev->next = s->next;
  81         else
  82                 root->head = s->next;
  83         s->prev = nil;
  84         s->next = nil;
  85 }
  86
  87 static int32
  88 cansemacquire(uint32 volatile *addr)
  89 {
  90         uint32 v;
  91
  92         while((v = runtime_atomicload(addr)) > 0)
  93                 if(runtime_cas(addr, v, v-1))
  94                         return 1;
  95         return 0;
  96 }
  97
  98 void
  99 runtime_semacquire(uint32 volatile *addr)
 100 {
 101         G *g;
 102         Sema s;
 103         SemaRoot *root;
 104
 105         // Easy case.
 106         if(cansemacquire(addr))
 107                 return;
 108
 109         // Harder case:
 110         //      increment waiter count
 111         //      try cansemacquire one more time, return if succeeded
 112         //      enqueue itself as a waiter
 113         //      sleep
 114         //      (waiter descriptor is dequeued by signaler)
 115         g = runtime_g();
 116         root = semroot(addr);
 117         for(;;) {
 118
 119                 runtime_lock(root);
 120                 // Add ourselves to nwait to disable "easy case" in semrelease.
 121                 runtime_xadd(&root->nwait, 1);
 122                 // Check cansemacquire to avoid missed wakeup.
 123                 if(cansemacquire(addr)) {
 124                         runtime_xadd(&root->nwait, -1);
 125                         runtime_unlock(root);
 126                         return;
 127                 }
 128                 // Any semrelease after the cansemacquire knows we're waiting
 129                 // (we set nwait above), so go to sleep.
 130                 semqueue(root, addr, &s);
 131                 g->status = Gwaiting;
 132                 g->waitreason = "semacquire";
 133                 runtime_unlock(root);
 134                 runtime_gosched();
 135                 if(cansemacquire(addr))
 136                         return;
 137         }
 138 }
 139
 140 void
 141 runtime_semrelease(uint32 volatile *addr)
 142 {
 143         Sema *s;
 144         SemaRoot *root;
 145
 146         root = semroot(addr);
 147         runtime_xadd(addr, 1);
 148
 149         // Easy case: no waiters?
 150         // This check must happen after the xadd, to avoid a missed wakeup
 151         // (see loop in semacquire).
 152         if(runtime_atomicload(&root->nwait) == 0)
 153                 return;
 154
 155         // Harder case: search for a waiter and wake it.
 156         runtime_lock(root);
 157         if(runtime_atomicload(&root->nwait) == 0) {
 158                 // The count is already consumed by another goroutine,
 159                 // so no need to wake up another goroutine.
 160                 runtime_unlock(root);
 161                 return;
 162         }
 163         for(s = root->head; s; s = s->next) {
 164                 if(s->addr == addr) {
 165                         runtime_xadd(&root->nwait, -1);
 166                         semdequeue(root, s);
 167                         break;
 168                 }
 169         }
 170         runtime_unlock(root);
 171         if(s)
 172                 runtime_ready(s->g);
 173 }
 174
 175 func Semacquire(addr *uint32) {
 176         runtime_semacquire(addr);
 177 }
 178
 179 func Semrelease(addr *uint32) {
 180         runtime_semrelease(addr);
 181 }