src/once.c

   1 /*
   2  * Copyright (c) 2008-2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_APACHE_LICENSE_HEADER_START@
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  *
  18  * @APPLE_APACHE_LICENSE_HEADER_END@
  19  */
  20
  21 #include "internal.h"
  22
  23 #undef dispatch_once
  24 #undef dispatch_once_f
  25
  26
  27 struct _dispatch_once_waiter_s {
  28         volatile struct _dispatch_once_waiter_s *volatile dow_next;
  29         _dispatch_thread_semaphore_t dow_sema;
  30 };
  31
  32 #define DISPATCH_ONCE_DONE ((struct _dispatch_once_waiter_s *)~0l)
  33
  34 #ifdef __BLOCKS__
  35 void
  36 dispatch_once(dispatch_once_t *val, dispatch_block_t block)
  37 {
  38         dispatch_once_f(val, block, _dispatch_Block_invoke(block));
  39 }
  40 #endif
  41
  42 DISPATCH_NOINLINE
  43 void
  44 dispatch_once_f(dispatch_once_t *val, void *ctxt, dispatch_function_t func)
  45 {
  46         struct _dispatch_once_waiter_s * volatile *vval =
  47                         (struct _dispatch_once_waiter_s**)val;
  48         struct _dispatch_once_waiter_s dow = { NULL, 0 };
  49         struct _dispatch_once_waiter_s *tail, *tmp;
  50         _dispatch_thread_semaphore_t sema;
  51
  52         if (dispatch_atomic_cmpxchg(vval, NULL, &dow, acquire)) {
  53                 _dispatch_client_callout(ctxt, func);
  54
  55                 // The next barrier must be long and strong.
  56                 //
  57                 // The scenario: SMP systems with weakly ordered memory models
  58                 // and aggressive out-of-order instruction execution.
  59                 //
  60                 // The problem:
  61                 //
  62                 // The dispatch_once*() wrapper macro causes the callee's
  63                 // instruction stream to look like this (pseudo-RISC):
  64                 //
  65                 //      load r5, pred-addr
  66                 //      cmpi r5, -1
  67                 //      beq  1f
  68                 //      call dispatch_once*()
  69                 //      1f:
  70                 //      load r6, data-addr
  71                 //
  72                 // May be re-ordered like so:
  73                 //
  74                 //      load r6, data-addr
  75                 //      load r5, pred-addr
  76                 //      cmpi r5, -1
  77                 //      beq  1f
  78                 //      call dispatch_once*()
  79                 //      1f:
  80                 //
  81                 // Normally, a barrier on the read side is used to workaround
  82                 // the weakly ordered memory model. But barriers are expensive
  83                 // and we only need to synchronize once! After func(ctxt)
  84                 // completes, the predicate will be marked as "done" and the
  85                 // branch predictor will correctly skip the call to
  86                 // dispatch_once*().
  87                 //
  88                 // A far faster alternative solution: Defeat the speculative
  89                 // read-ahead of peer CPUs.
  90                 //
  91                 // Modern architectures will throw away speculative results
  92                 // once a branch mis-prediction occurs. Therefore, if we can
  93                 // ensure that the predicate is not marked as being complete
  94                 // until long after the last store by func(ctxt), then we have
  95                 // defeated the read-ahead of peer CPUs.
  96                 //
  97                 // In other words, the last "store" by func(ctxt) must complete
  98                 // and then N cycles must elapse before ~0l is stored to *val.
  99                 // The value of N is whatever is sufficient to defeat the
 100                 // read-ahead mechanism of peer CPUs.
 101                 //
 102                 // On some CPUs, the most fully synchronizing instruction might
 103                 // need to be issued.
 104
 105                 dispatch_atomic_maximally_synchronizing_barrier();
 106                 // above assumed to contain release barrier
 107                 tmp = dispatch_atomic_xchg(vval, DISPATCH_ONCE_DONE, relaxed);
 108                 tail = &dow;
 109                 while (tail != tmp) {
 110                         while (!tmp->dow_next) {
 111                                 dispatch_hardware_pause();
 112                         }
 113                         sema = tmp->dow_sema;
 114                         tmp = (struct _dispatch_once_waiter_s*)tmp->dow_next;
 115                         _dispatch_thread_semaphore_signal(sema);
 116                 }
 117         } else {
 118                 dow.dow_sema = _dispatch_get_thread_semaphore();
 119                 tmp = *vval;
 120                 for (;;) {
 121                         if (tmp == DISPATCH_ONCE_DONE) {
 122                                 break;
 123                         }
 124                         if (dispatch_atomic_cmpxchgvw(vval, tmp, &dow, &tmp, release)) {
 125                                 dow.dow_next = tmp;
 126                                 _dispatch_thread_semaphore_wait(dow.dow_sema);
 127                                 break;
 128                         }
 129                 }
 130                 _dispatch_put_thread_semaphore(dow.dow_sema);
 131         }
 132 }