1 /* SPDX-License-Identifier: BSD-3-Clause */
2 /* Copyright(c) 2007-2022 Intel Corporation */
3 #ifndef LAC_LOCK_FREE_STACK_H_1
4 #define LAC_LOCK_FREE_STACK_H_1
5 #include "lac_mem_pools.h"
6 
7 typedef union {
8 	struct {
9 		uint64_t ctr : 16;
10 		uint64_t ptr : 48;
11 	};
12 	uint64_t atomic;
13 } pointer_t;
14 
15 typedef struct {
16 	volatile pointer_t top;
17 } lock_free_stack_t;
18 
19 static inline void *
20 PTR(const uintptr_t addr48)
21 {
22 #ifdef __x86_64__
23 	const int64_t addr64 = addr48 << 16;
24 
25 	/* Do arithmetic shift to restore kernel canonical address (if not NULL)
26 	 */
27 	return (void *)(addr64 >> 16);
28 #else
29 	return (void *)(addr48);
30 #endif
31 }
32 
33 static inline lac_mem_blk_t *
34 pop(lock_free_stack_t *stack)
35 {
36 	pointer_t old_top;
37 	pointer_t new_top;
38 	lac_mem_blk_t *next;
39 
40 	do {
41 		old_top.atomic = stack->top.atomic;
42 		next = PTR(old_top.ptr);
43 		if (NULL == next)
44 			return next;
45 
46 		new_top.ptr = (uintptr_t)next->pNext;
47 		new_top.ctr = old_top.ctr + 1;
48 	} while (!__sync_bool_compare_and_swap(&stack->top.atomic,
49 					       old_top.atomic,
50 					       new_top.atomic));
51 
52 	return next;
53 }
54 
55 static inline void
56 push(lock_free_stack_t *stack, lac_mem_blk_t *val)
57 {
58 	pointer_t new_top;
59 	pointer_t old_top;
60 
61 	do {
62 		old_top.atomic = stack->top.atomic;
63 		val->pNext = PTR(old_top.ptr);
64 		new_top.ptr = (uintptr_t)val;
65 		new_top.ctr = old_top.ctr + 1;
66 	} while (!__sync_bool_compare_and_swap(&stack->top.atomic,
67 					       old_top.atomic,
68 					       new_top.atomic));
69 }
70 
71 static inline lock_free_stack_t
72 _init_stack(void)
73 {
74 	lock_free_stack_t stack = { { { 0 } } };
75 	return stack;
76 }
77 
78 static inline lac_mem_blk_t *
79 top(lock_free_stack_t *stack)
80 {
81 	pointer_t old_top = stack->top;
82 	lac_mem_blk_t *next = PTR(old_top.ptr);
83 	return next;
84 }
85 
86 #endif
87