1 /** @file 2 3 A brief file description 4 5 @section license License 6 7 Licensed to the Apache Software Foundation (ASF) under one 8 or more contributor license agreements. See the NOTICE file 9 distributed with this work for additional information 10 regarding copyright ownership. The ASF licenses this file 11 to you under the Apache License, Version 2.0 (the 12 "License"); you may not use this file except in compliance 13 with the License. You may obtain a copy of the License at 14 15 http://www.apache.org/licenses/LICENSE-2.0 16 17 Unless required by applicable law or agreed to in writing, software 18 distributed under the License is distributed on an "AS IS" BASIS, 19 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 20 See the License for the specific language governing permissions and 21 limitations under the License. 22 */ 23 24 #pragma once 25 26 /*********************************************************************** 27 28 Generic Queue Implementation (for pointer data types only) 29 30 Uses atomic memory operations to avoid blocking. 31 Intended as a replacement for llqueue. 32 33 34 ***********************************************************************/ 35 36 #include "tscore/ink_platform.h" 37 #include "tscore/ink_defs.h" 38 #include "tscore/ink_apidefs.h" 39 40 /* 41 For information on the structure of the x86_64 memory map: 42 43 http://en.wikipedia.org/wiki/X86-64#Linux 44 45 Essentially, in the current 48-bit implementations, the 46 top bit as well as the lower 47 bits are used, leaving 47 the upper-but one 16 bits free to be used for the version. 48 We will use the top-but-one 15 and sign extend when generating 49 the pointer was required by the standard. 50 */ 51 52 /* 53 #if defined(POSIX_THREAD) 54 #include <pthread.h> 55 #include <stdlib.h> 56 #endif 57 */ 58 59 #ifdef __cplusplus 60 extern "C" { 61 #endif /* __cplusplus */ 62 63 void ink_queue_load_64(void *dst, void *src); 64 65 #ifdef __x86_64__ 66 #define INK_QUEUE_LD64(dst, src) *((uint64_t *)&(dst)) = *((uint64_t *)&(src)) 67 #else 68 #define INK_QUEUE_LD64(dst, src) (ink_queue_load_64((void *)&(dst), (void *)&(src))) 69 #endif 70 71 #if TS_HAS_128BIT_CAS 72 #define INK_QUEUE_LD(dst, src) \ 73 do { \ 74 *(__int128_t *)&(dst) = __sync_val_compare_and_swap((__int128_t *)&(src), 0, 0); \ 75 } while (0) 76 #else 77 #define INK_QUEUE_LD(dst, src) INK_QUEUE_LD64(dst, src) 78 #endif 79 80 /* 81 * Generic Free List Manager 82 */ 83 // Warning: head_p is read and written in multiple threads without a 84 // lock, use INK_QUEUE_LD to read safely. 85 union head_p { head_p()86 head_p() : data(){}; 87 88 #if (defined(__i386__) || defined(__arm__) || defined(__mips__)) && (SIZEOF_VOIDP == 4) 89 typedef int32_t version_type; 90 typedef int64_t data_type; 91 #elif TS_HAS_128BIT_CAS 92 typedef int64_t version_type; 93 typedef __int128_t data_type; 94 #else 95 typedef int64_t version_type; 96 typedef int64_t data_type; 97 #endif 98 99 struct { 100 void *pointer; 101 version_type version; 102 } s; 103 104 data_type data; 105 }; 106 107 /* 108 * Why is version required? One scenario is described below 109 * Think of a list like this -> A -> C -> D 110 * and you are popping from the list 111 * Between the time you take the ptr(A) and swap the head pointer 112 * the list could start looking like this 113 * -> A -> B -> C -> D 114 * If the version check is not there, the list will look like 115 * -> C -> D after the pop, which will result in the loss of "B" 116 * 117 * For more information, see: https://en.wikipedia.org/wiki/ABA_problem . 118 * (Versioning is a case of the "tagged state reference" workaround.) 119 */ 120 #define ZERO_HEAD_P(_x) 121 122 #ifdef DEBUG 123 #define FROM_PTR(_x) (void *)(((uintptr_t)_x) + 1) 124 #define TO_PTR(_x) (void *)(((uintptr_t)_x) - 1) 125 #else 126 #define FROM_PTR(_x) ((void *)(_x)) 127 #define TO_PTR(_x) ((void *)(_x)) 128 #endif 129 130 #if (defined(__i386__) || defined(__arm__) || defined(__mips__)) && (SIZEOF_VOIDP == 4) 131 #define FREELIST_POINTER(_x) (_x).s.pointer 132 #define FREELIST_VERSION(_x) (_x).s.version 133 #define SET_FREELIST_POINTER_VERSION(_x, _p, _v) \ 134 (_x).s.pointer = _p; \ 135 (_x).s.version = _v 136 #elif TS_HAS_128BIT_CAS 137 #define FREELIST_POINTER(_x) (_x).s.pointer 138 #define FREELIST_VERSION(_x) (_x).s.version 139 #define SET_FREELIST_POINTER_VERSION(_x, _p, _v) \ 140 (_x).s.pointer = _p; \ 141 (_x).s.version = _v 142 #elif defined(__x86_64__) || defined(__ia64__) || defined(__powerpc64__) || defined(__aarch64__) || defined(__mips64) 143 /* Layout of FREELIST_POINTER 144 * 145 * 0 ~ 47 bits : 48 bits, Virtual Address (47 bits for AMD64 and 48 bits for AArch64) 146 * 48 ~ 62 bits : 15 bits, Freelist Version 147 * 63 bits : 1 bits, The type of Virtual Address (0 = user space, 1 = kernel space) 148 */ 149 /* Detect which shift is implemented by the simple expression ((~0 >> 1) < 0): 150 * 151 * If the shift is 'logical' the highest order bit of the left side of the comparison is 0 so the result is positive. 152 * If the shift is 'arithmetic' the highest order bit of the left side is 1 so the result is negative. 153 */ 154 #if ((~0 >> 1) < 0) 155 /* the shift is `arithmetic' */ 156 #define FREELIST_POINTER(_x) \ 157 ((void *)((((intptr_t)(_x).data) & 0x0000FFFFFFFFFFFFLL) | ((((intptr_t)(_x).data) >> 63) << 48))) // sign extend 158 #else 159 /* the shift is `logical' */ 160 #define FREELIST_POINTER(_x) \ 161 ((void *)((((intptr_t)(_x).data) & 0x0000FFFFFFFFFFFFLL) | (((~((((intptr_t)(_x).data) >> 63) - 1)) >> 48) << 48))) 162 #endif 163 164 #define FREELIST_VERSION(_x) ((((intptr_t)(_x).data) & 0x7FFF000000000000LL) >> 48) 165 #define SET_FREELIST_POINTER_VERSION(_x, _p, _v) (_x).data = ((((intptr_t)(_p)) & 0x8000FFFFFFFFFFFFLL) | (((_v)&0x7FFFLL) << 48)) 166 #else 167 #error "unsupported processor" 168 #endif 169 170 struct _InkFreeList { 171 head_p head; 172 const char *name; 173 uint32_t type_size, chunk_size, used, allocated, alignment; 174 uint32_t allocated_base, used_base; 175 int advice; 176 }; 177 178 typedef struct ink_freelist_ops InkFreeListOps; 179 typedef struct _InkFreeList InkFreeList; 180 181 const InkFreeListOps *ink_freelist_malloc_ops(); 182 const InkFreeListOps *ink_freelist_freelist_ops(); 183 void ink_freelist_init_ops(int nofl_class, int nofl_proxy); 184 185 /* 186 * alignment must be a power of 2 187 */ 188 InkFreeList *ink_freelist_create(const char *name, uint32_t type_size, uint32_t chunk_size, uint32_t alignment); 189 190 inkcoreapi void ink_freelist_init(InkFreeList **fl, const char *name, uint32_t type_size, uint32_t chunk_size, uint32_t alignment); 191 inkcoreapi void ink_freelist_madvise_init(InkFreeList **fl, const char *name, uint32_t type_size, uint32_t chunk_size, 192 uint32_t alignment, int advice); 193 inkcoreapi void *ink_freelist_new(InkFreeList *f); 194 inkcoreapi void ink_freelist_free(InkFreeList *f, void *item); 195 inkcoreapi void ink_freelist_free_bulk(InkFreeList *f, void *head, void *tail, size_t num_item); 196 void ink_freelists_dump(FILE *f); 197 void ink_freelists_dump_baselinerel(FILE *f); 198 void ink_freelists_snap_baseline(); 199 200 struct InkAtomicList { InkAtomicListInkAtomicList201 InkAtomicList() {} 202 head_p head{}; 203 const char *name = nullptr; 204 uint32_t offset = 0; 205 }; 206 207 #if !defined(INK_QUEUE_NT) 208 #define INK_ATOMICLIST_EMPTY(_x) (!(TO_PTR(FREELIST_POINTER((_x.head))))) 209 #else 210 /* ink_queue_nt.c doesn't do the FROM/TO pointer swizzling */ 211 #define INK_ATOMICLIST_EMPTY(_x) (!((FREELIST_POINTER((_x.head))))) 212 #endif 213 214 // WARNING: the "name" string is not copied, it has to be a statically-stored constant string. 215 // 216 inkcoreapi void ink_atomiclist_init(InkAtomicList *l, const char *name, uint32_t offset_to_next); 217 218 inkcoreapi void *ink_atomiclist_push(InkAtomicList *l, void *item); 219 void *ink_atomiclist_pop(InkAtomicList *l); 220 inkcoreapi void *ink_atomiclist_popall(InkAtomicList *l); 221 /* 222 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING 223 * only if only one thread is doing pops it is possible to have a "remove" 224 * which only that thread can use as well. 225 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING 226 */ 227 void *ink_atomiclist_remove(InkAtomicList *l, void *item); 228 229 #ifdef __cplusplus 230 } 231 #endif /* __cplusplus */ 232