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 7package runtime 8#include "runtime.h" 9#include "arch.h" 10 11#if __SIZEOF_POINTER__ == 8 12// SPARC64 and Solaris on AMD64 uses all 64 bits of virtual addresses. 13// Use low-order three bits as ABA counter. 14// http://docs.oracle.com/cd/E19120-01/open.solaris/816-5138/6mba6ua5p/index.html 15# if defined(__sparc__) || (defined(__sun__) && defined(__amd64__)) 16static inline uint64 lfPack(LFNode *node, uintptr cnt) { 17 return ((uint64)(node)) | ((cnt)&7); 18} 19static inline LFNode* lfUnpack(uint64 val) { 20 return (LFNode*)(val&~7); 21} 22# else 23# if defined(__aarch64__) 24// Depending on the kernel options, pointers on arm64 can have up to 48 significant 25// bits (see https://www.kernel.org/doc/Documentation/arm64/memory.txt). 26# define PTR_BITS 48 27# else 28// Amd64 uses 48-bit virtual addresses, 47-th bit is used as kernel/user flag. 29// So we use 17msb of pointers as ABA counter. 30# define PTR_BITS 47 31# endif 32# define CNT_BITS (64 - PTR_BITS + 3) 33static inline uint64 lfPack(LFNode *node, uintptr cnt) { 34 return ((uint64)(node)<<(64-PTR_BITS)) | (cnt&(((1<<CNT_BITS)-1))); 35} 36static inline LFNode* lfUnpack(uint64 val) { 37 return (LFNode*)((val >> CNT_BITS) << 3); 38} 39# endif 40#else 41static inline uint64 lfPack(LFNode *node, uintptr cnt) { 42 return ((uint64)(uintptr)(node)<<32) | cnt; 43} 44static inline LFNode* lfUnpack(uint64 val) { 45 return (LFNode*)(uintptr)(val >> 32); 46} 47#endif 48 49void 50runtime_lfstackpush(uint64 *head, LFNode *node) 51{ 52 uint64 old, new; 53 54 if(node != lfUnpack(lfPack(node, 0))) { 55 runtime_printf("p=%p\n", node); 56 runtime_throw("runtime_lfstackpush: invalid pointer"); 57 } 58 59 node->pushcnt++; 60 new = lfPack(node, node->pushcnt); 61 for(;;) { 62 old = runtime_atomicload64(head); 63 node->next = lfUnpack(old); 64 if(runtime_cas64(head, old, new)) 65 break; 66 } 67} 68 69LFNode* 70runtime_lfstackpop(uint64 *head) 71{ 72 LFNode *node, *node2; 73 uint64 old, new; 74 75 for(;;) { 76 old = runtime_atomicload64(head); 77 if(old == 0) 78 return nil; 79 node = lfUnpack(old); 80 node2 = runtime_atomicloadp(&node->next); 81 new = 0; 82 if(node2 != nil) 83 new = lfPack(node2, node2->pushcnt); 84 if(runtime_cas64(head, old, new)) 85 return node; 86 } 87} 88 89func lfstackpush_go(head *uint64, node *LFNode) { 90 runtime_lfstackpush(head, node); 91} 92 93func lfstackpop_go(head *uint64) (node *LFNode) { 94 node = runtime_lfstackpop(head); 95} 96