1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2019 Intel Corporation 3 */ 4 5 #ifndef _RTE_STACK_LF_C11_H_ 6 #define _RTE_STACK_LF_C11_H_ 7 8 #include <rte_branch_prediction.h> 9 #include <rte_prefetch.h> 10 11 static __rte_always_inline unsigned int 12 __rte_stack_lf_count(struct rte_stack *s) 13 { 14 /* stack_lf_push() and stack_lf_pop() do not update the list's contents 15 * and stack_lf->len atomically, which can cause the list to appear 16 * shorter than it actually is if this function is called while other 17 * threads are modifying the list. 18 * 19 * However, given the inherently approximate nature of the get_count 20 * callback -- even if the list and its size were updated atomically, 21 * the size could change between when get_count executes and when the 22 * value is returned to the caller -- this is acceptable. 23 * 24 * The stack_lf->len updates are placed such that the list may appear to 25 * have fewer elements than it does, but will never appear to have more 26 * elements. If the mempool is near-empty to the point that this is a 27 * concern, the user should consider increasing the mempool size. 28 */ 29 return (unsigned int)__atomic_load_n(&s->stack_lf.used.len, 30 __ATOMIC_RELAXED); 31 } 32 33 static __rte_always_inline void 34 __rte_stack_lf_push_elems(struct rte_stack_lf_list *list, 35 struct rte_stack_lf_elem *first, 36 struct rte_stack_lf_elem *last, 37 unsigned int num) 38 { 39 struct rte_stack_lf_head old_head; 40 int success; 41 42 old_head = list->head; 43 44 do { 45 struct rte_stack_lf_head new_head; 46 47 /* Use an acquire fence to establish a synchronized-with 48 * relationship between the list->head load and store-release 49 * operations (as part of the rte_atomic128_cmp_exchange()). 50 */ 51 __atomic_thread_fence(__ATOMIC_ACQUIRE); 52 53 /* Swing the top pointer to the first element in the list and 54 * make the last element point to the old top. 55 */ 56 new_head.top = first; 57 new_head.cnt = old_head.cnt + 1; 58 59 last->next = old_head.top; 60 61 /* Use the release memmodel to ensure the writes to the LF LIFO 62 * elements are visible before the head pointer write. 63 */ 64 success = rte_atomic128_cmp_exchange( 65 (rte_int128_t *)&list->head, 66 (rte_int128_t *)&old_head, 67 (rte_int128_t *)&new_head, 68 1, __ATOMIC_RELEASE, 69 __ATOMIC_RELAXED); 70 } while (success == 0); 71 72 /* Ensure the stack modifications are not reordered with respect 73 * to the LIFO len update. 74 */ 75 __atomic_add_fetch(&list->len, num, __ATOMIC_RELEASE); 76 } 77 78 static __rte_always_inline struct rte_stack_lf_elem * 79 __rte_stack_lf_pop_elems(struct rte_stack_lf_list *list, 80 unsigned int num, 81 void **obj_table, 82 struct rte_stack_lf_elem **last) 83 { 84 struct rte_stack_lf_head old_head; 85 uint64_t len; 86 int success; 87 88 /* Reserve num elements, if available */ 89 len = __atomic_load_n(&list->len, __ATOMIC_ACQUIRE); 90 91 while (1) { 92 /* Does the list contain enough elements? */ 93 if (unlikely(len < num)) 94 return NULL; 95 96 /* len is updated on failure */ 97 if (__atomic_compare_exchange_n(&list->len, 98 &len, len - num, 99 0, __ATOMIC_ACQUIRE, 100 __ATOMIC_ACQUIRE)) 101 break; 102 } 103 104 /* If a torn read occurs, the CAS will fail and set old_head to the 105 * correct/latest value. 106 */ 107 old_head = list->head; 108 109 /* Pop num elements */ 110 do { 111 struct rte_stack_lf_head new_head; 112 struct rte_stack_lf_elem *tmp; 113 unsigned int i; 114 115 /* Use the acquire memmodel to ensure the reads to the LF LIFO 116 * elements are properly ordered with respect to the head 117 * pointer read. 118 */ 119 __atomic_thread_fence(__ATOMIC_ACQUIRE); 120 121 rte_prefetch0(old_head.top); 122 123 tmp = old_head.top; 124 125 /* Traverse the list to find the new head. A next pointer will 126 * either point to another element or NULL; if a thread 127 * encounters a pointer that has already been popped, the CAS 128 * will fail. 129 */ 130 for (i = 0; i < num && tmp != NULL; i++) { 131 rte_prefetch0(tmp->next); 132 if (obj_table) 133 obj_table[i] = tmp->data; 134 if (last) 135 *last = tmp; 136 tmp = tmp->next; 137 } 138 139 /* If NULL was encountered, the list was modified while 140 * traversing it. Retry. 141 */ 142 if (i != num) 143 continue; 144 145 new_head.top = tmp; 146 new_head.cnt = old_head.cnt + 1; 147 148 success = rte_atomic128_cmp_exchange( 149 (rte_int128_t *)&list->head, 150 (rte_int128_t *)&old_head, 151 (rte_int128_t *)&new_head, 152 1, __ATOMIC_RELEASE, 153 __ATOMIC_RELAXED); 154 } while (success == 0); 155 156 return old_head.top; 157 } 158 159 #endif /* _RTE_STACK_LF_C11_H_ */ 160