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