libgo/runtime/lfstack.c

   1 // Copyright 2012 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 // Lock-free stack.
   6
   7 #include "runtime.h"
   8 #include "arch.h"
   9
  10 #if __SIZEOF_POINTER__ == 8
  11 // Amd64 uses 48-bit virtual addresses, 47-th bit is used as kernel/user flag.
  12 // So we use 17msb of pointers as ABA counter.
  13 # define PTR_BITS 47
  14 #else
  15 # define PTR_BITS 32
  16 #endif
  17 #define PTR_MASK ((1ull<<PTR_BITS)-1)
  18
  19 void
  20 runtime_lfstackpush(uint64 *head, LFNode *node)
  21 {
  22         uint64 old, new;
  23
  24         if((uintptr)node != ((uintptr)node&PTR_MASK)) {
  25                 runtime_printf("p=%p\n", node);
  26                 runtime_throw("runtime_lfstackpush: invalid pointer");
  27         }
  28
  29         node->pushcnt++;
  30         new = (uint64)(uintptr)node|(((uint64)node->pushcnt)<<PTR_BITS);
  31         old = runtime_atomicload64(head);
  32         for(;;) {
  33                 node->next = (LFNode*)(uintptr)(old&PTR_MASK);
  34                 if(runtime_cas64(head, &old, new))
  35                         break;
  36         }
  37 }
  38
  39 LFNode*
  40 runtime_lfstackpop(uint64 *head)
  41 {
  42         LFNode *node, *node2;
  43         uint64 old, new;
  44
  45         old = runtime_atomicload64(head);
  46         for(;;) {
  47                 if(old == 0)
  48                         return nil;
  49                 node = (LFNode*)(uintptr)(old&PTR_MASK);
  50                 node2 = runtime_atomicloadp(&node->next);
  51                 new = 0;
  52                 if(node2 != nil)
  53                         new = (uint64)(uintptr)node2|(((uint64)node2->pushcnt)<<PTR_BITS);
  54                 if(runtime_cas64(head, &old, new))
  55                         return node;
  56         }
  57 }
  58
  59 LFNode* runtime_lfstackpop2(uint64*)
  60   asm("runtime.lfstackpop2");
  61
  62 LFNode*
  63 runtime_lfstackpop2(uint64 *head)
  64 {
  65         return runtime_lfstackpop(head);
  66 }