Imported Upstream version 4.8.1
[platform/upstream/gcc48.git] / 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 #define CNT_MASK (0ull-1)
19
20 #if __SIZEOF_POINTER__ == 8 && (defined(__sparc__) || (defined(__sun__) && defined(__amd64__)))
21 // SPARC64 and Solaris on AMD64 uses all 64 bits of virtual addresses.
22 // Use low-order three bits as ABA counter.
23 // http://docs.oracle.com/cd/E19120-01/open.solaris/816-5138/6mba6ua5p/index.html
24 #undef PTR_BITS
25 #undef CNT_MASK
26 #undef PTR_MASK
27 #define PTR_BITS 0
28 #define CNT_MASK 7
29 #define PTR_MASK ((0ull-1)<<3)
30 #endif
31
32 void
33 runtime_lfstackpush(uint64 *head, LFNode *node)
34 {
35         uint64 old, new;
36
37         if((uintptr)node != ((uintptr)node&PTR_MASK)) {
38                 runtime_printf("p=%p\n", node);
39                 runtime_throw("runtime_lfstackpush: invalid pointer");
40         }
41
42         node->pushcnt++;
43         new = (uint64)(uintptr)node|(((uint64)node->pushcnt&CNT_MASK)<<PTR_BITS);
44         old = runtime_atomicload64(head);
45         for(;;) {
46                 node->next = (LFNode*)(uintptr)(old&PTR_MASK);
47                 if(runtime_cas64(head, &old, new))
48                         break;
49         }
50 }
51
52 LFNode*
53 runtime_lfstackpop(uint64 *head)
54 {
55         LFNode *node, *node2;
56         uint64 old, new;
57
58         old = runtime_atomicload64(head);
59         for(;;) {
60                 if(old == 0)
61                         return nil;
62                 node = (LFNode*)(uintptr)(old&PTR_MASK);
63                 node2 = runtime_atomicloadp(&node->next);
64                 new = 0;
65                 if(node2 != nil)
66                         new = (uint64)(uintptr)node2|(((uint64)node2->pushcnt&CNT_MASK)<<PTR_BITS);
67                 if(runtime_cas64(head, &old, new))
68                         return node;
69         }
70 }
71
72 LFNode* runtime_lfstackpop2(uint64*)
73   __asm__ (GOSYM_PREFIX "runtime.lfstackpop2");
74
75 LFNode*
76 runtime_lfstackpop2(uint64 *head)
77 {
78         return runtime_lfstackpop(head);
79 }