1 /* 2 * COPYRIGHT: See COPYING in the top level directory 3 * PROJECT: ReactOS Runtime Library 4 * PURPOSE: Slist Routines 5 * FILE: lib/rtl/slist.c 6 * PROGRAMERS: Stefan Ginsberg (stefan.ginsberg@reactos.org) 7 * Timo Kreuzer (timo.kreuzer@reactos.org) 8 */ 9 10 /* INCLUDES *****************************************************************/ 11 12 #include <rtl.h> 13 14 #define NDEBUG 15 #include <debug.h> 16 17 #ifdef _WIN64 18 BOOLEAN RtlpUse16ByteSLists = -1; 19 #endif 20 21 /* FUNCTIONS ***************************************************************/ 22 23 VOID 24 NTAPI 25 RtlInitializeSListHead( 26 _Out_ PSLIST_HEADER SListHead) 27 { 28 #if defined(_WIN64) 29 /* Make sure the header is 16 byte aligned */ 30 if (((ULONG_PTR)SListHead & 0xf) != 0) 31 { 32 DPRINT1("Unaligned SListHead: 0x%p\n", SListHead); 33 RtlRaiseStatus(STATUS_DATATYPE_MISALIGNMENT); 34 } 35 36 /* Initialize the Region member */ 37 #if defined(_IA64_) 38 /* On Itanium we store the region in the list head */ 39 SListHead->Region = (ULONG_PTR)SListHead & VRN_MASK; 40 #else 41 /* On amd64 we don't need to store anything */ 42 SListHead->Region = 0; 43 #endif /* _IA64_ */ 44 #endif /* _WIN64 */ 45 46 SListHead->Alignment = 0; 47 } 48 49 PSLIST_ENTRY 50 NTAPI 51 RtlFirstEntrySList( 52 _In_ const SLIST_HEADER *SListHead) 53 { 54 #if defined(_WIN64) 55 /* Check if the header is initialized as 16 byte header */ 56 if (SListHead->Header16.HeaderType) 57 { 58 return (PVOID)(SListHead->Region & ~0xFLL); 59 } 60 else 61 { 62 union { 63 ULONG64 Region; 64 struct { 65 ULONG64 Reserved:4; 66 ULONG64 NextEntry:39; 67 ULONG64 Reserved2:21; 68 } Bits; 69 } Pointer; 70 71 #if defined(_IA64_) 72 /* On Itanium we stored the region in the list head */ 73 Pointer.Region = SListHead->Region; 74 #else 75 /* On amd64 we just use the list head itself */ 76 Pointer.Region = (ULONG64)SListHead; 77 #endif 78 Pointer.Bits.NextEntry = SListHead->Header8.NextEntry; 79 return (PVOID)Pointer.Region; 80 } 81 #else 82 return SListHead->Next.Next; 83 #endif 84 } 85 86 WORD 87 NTAPI 88 RtlQueryDepthSList( 89 _In_ PSLIST_HEADER SListHead) 90 { 91 #if defined(_WIN64) 92 return (USHORT)(SListHead->Alignment & 0xffff); 93 #else 94 return SListHead->Depth; 95 #endif 96 } 97 98 PSLIST_ENTRY 99 FASTCALL 100 RtlInterlockedPushListSList( 101 _Inout_ PSLIST_HEADER SListHead, 102 _Inout_ __drv_aliasesMem PSLIST_ENTRY List, 103 _Inout_ PSLIST_ENTRY ListEnd, 104 _In_ ULONG Count) 105 { 106 #ifdef _WIN64 107 SLIST_HEADER OldSListHead, NewSListHead; 108 PSLIST_ENTRY FirstEntry; 109 110 ASSERT(((ULONG_PTR)SListHead & 0xF) == 0); 111 ASSERT(((ULONG_PTR)List & 0xF) == 0); 112 113 if (RtlpUse16ByteSLists) 114 { 115 BOOLEAN exchanged; 116 117 do 118 { 119 /* Capture the current SListHead */ 120 OldSListHead = *SListHead; 121 122 /* Link the last list entry */ 123 FirstEntry = (PSLIST_ENTRY)(SListHead->Region & ~0xFLL); 124 ListEnd->Next = FirstEntry; 125 126 /* Set up new SListHead */ 127 NewSListHead = OldSListHead; 128 NewSListHead.Header16.Depth += Count; 129 NewSListHead.Header16.Sequence++; 130 NewSListHead.Region = (ULONG64)List; 131 NewSListHead.Header16.HeaderType = 1; 132 NewSListHead.Header16.Init = 1; 133 134 /* Atomically exchange the SlistHead with the new one */ 135 exchanged = _InterlockedCompareExchange128((PULONG64)SListHead, 136 NewSListHead.Region, 137 NewSListHead.Alignment, 138 (PULONG64)&OldSListHead); 139 } while (!exchanged); 140 141 return FirstEntry; 142 } 143 else 144 { 145 ULONG64 Compare; 146 147 /* ListHead and List must be in the same region */ 148 ASSERT(((ULONG64)SListHead & 0xFFFFF80000000000ull) == 149 ((ULONG64)List & 0xFFFFF80000000000ull)); 150 151 /* Read the header */ 152 OldSListHead = *SListHead; 153 154 do 155 { 156 /* Construct the address from the header bits and the list head pointer */ 157 FirstEntry = (PSLIST_ENTRY)((OldSListHead.Header8.NextEntry << 4) | 158 ((ULONG64)SListHead & 0xFFFFF80000000000ull)); 159 160 /* Link the last list entry */ 161 ListEnd->Next = FirstEntry; 162 163 /* Create a new header */ 164 NewSListHead = OldSListHead; 165 NewSListHead.Header8.NextEntry = (ULONG64)List >> 4; 166 NewSListHead.Header8.Depth += Count; 167 NewSListHead.Header8.Sequence++; 168 169 /* Try to exchange atomically */ 170 Compare = OldSListHead.Alignment; 171 OldSListHead.Alignment = InterlockedCompareExchange64((PLONG64)&SListHead->Alignment, 172 NewSListHead.Alignment, 173 Compare); 174 } while (OldSListHead.Alignment != Compare); 175 176 /* Return the old first entry */ 177 return FirstEntry; 178 } 179 #else 180 SLIST_HEADER OldHeader, NewHeader; 181 ULONGLONG Compare; 182 183 /* Read the header */ 184 OldHeader = *SListHead; 185 186 do 187 { 188 /* Link the last list entry */ 189 ListEnd->Next = OldHeader.Next.Next; 190 191 /* Create a new header */ 192 NewHeader = OldHeader; 193 NewHeader.Next.Next = List; 194 NewHeader.Depth += Count; 195 NewHeader.Sequence++; 196 197 /* Try to exchange atomically */ 198 Compare = OldHeader.Alignment; 199 OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment, 200 NewHeader.Alignment, 201 Compare); 202 } 203 while (OldHeader.Alignment != Compare); 204 205 /* Return the old first entry */ 206 return OldHeader.Next.Next; 207 #endif /* _WIN64 */ 208 } 209 210 211 #if !defined(_M_IX86) && !defined(_M_AMD64) 212 213 _WARN("C based S-List functions can bugcheck, if not handled properly in kernel") 214 215 #ifdef _WIN64 216 #error "No generic S-List functions for WIN64!" 217 #endif 218 219 /* This variable must be used in kernel mode to prevent the system from 220 bugchecking on non-present kernel memory. If this variable is set to TRUE 221 an exception needs to be dispatched. */ 222 BOOLEAN RtlpExpectSListFault; 223 224 PSLIST_ENTRY 225 NTAPI 226 RtlInterlockedPushEntrySList( 227 _Inout_ PSLIST_HEADER SListHead, 228 _Inout_ __drv_aliasesMem PSLIST_ENTRY SListEntry) 229 { 230 SLIST_HEADER OldHeader, NewHeader; 231 ULONGLONG Compare; 232 233 /* Read the header */ 234 OldHeader = *SListHead; 235 236 do 237 { 238 /* Link the list entry */ 239 SListEntry->Next = OldHeader.Next.Next; 240 241 /* Create a new header */ 242 NewHeader = OldHeader; 243 NewHeader.Next.Next = SListEntry; 244 NewHeader.Depth++; 245 NewHeader.Sequence++; 246 247 /* Try to exchange atomically */ 248 Compare = OldHeader.Alignment; 249 OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment, 250 NewHeader.Alignment, 251 Compare); 252 } 253 while (OldHeader.Alignment != Compare); 254 255 /* Return the old first entry */ 256 return OldHeader.Next.Next; 257 } 258 259 PSLIST_ENTRY 260 NTAPI 261 RtlInterlockedPopEntrySList( 262 _Inout_ PSLIST_HEADER SListHead) 263 { 264 SLIST_HEADER OldHeader, NewHeader; 265 ULONGLONG Compare; 266 267 restart: 268 269 /* Read the header */ 270 OldHeader = *SListHead; 271 272 do 273 { 274 /* Check for empty list */ 275 if (OldHeader.Next.Next == NULL) 276 { 277 return NULL; 278 } 279 280 /* Create a new header */ 281 NewHeader = OldHeader; 282 283 /* HACK to let the kernel know that we are doing slist-magic */ 284 RtlpExpectSListFault = TRUE; 285 286 /* Wrapped in SEH, since OldHeader.Next.Next can already be freed */ 287 _SEH2_TRY 288 { 289 NewHeader.Next = *OldHeader.Next.Next; 290 } 291 _SEH2_EXCEPT((SListHead->Next.Next != OldHeader.Next.Next) ? 292 EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) 293 { 294 /* We got an exception and the list head changed. 295 Restart the whole operation. */ 296 RtlpExpectSListFault = FALSE; 297 goto restart; 298 } 299 _SEH2_END; 300 301 /* We are done */ 302 RtlpExpectSListFault = FALSE; 303 304 /* Adjust depth */ 305 NewHeader.Depth--; 306 307 /* Try to exchange atomically */ 308 Compare = OldHeader.Alignment; 309 OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)SListHead->Alignment, 310 NewHeader.Alignment, 311 Compare); 312 } 313 while (OldHeader.Alignment != Compare); 314 315 return OldHeader.Next.Next; 316 } 317 318 PSLIST_ENTRY 319 NTAPI 320 RtlInterlockedFlushSList( 321 _Inout_ PSLIST_HEADER SListHead) 322 { 323 SLIST_HEADER OldHeader, NewHeader; 324 ULONGLONG Compare; 325 326 /* Read the header */ 327 OldHeader = *SListHead; 328 329 do 330 { 331 /* Check for empty list */ 332 if (OldHeader.Next.Next == NULL) 333 { 334 return NULL; 335 } 336 337 /* Create a new header (keep the sequence number) */ 338 NewHeader = OldHeader; 339 NewHeader.Next.Next = NULL; 340 NewHeader.Depth = 0; 341 342 /* Try to exchange atomically */ 343 Compare = OldHeader.Alignment; 344 OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment, 345 NewHeader.Alignment, 346 Compare); 347 } 348 while (OldHeader.Alignment != Compare); 349 350 /* Return the old first entry */ 351 return OldHeader.Next.Next; 352 353 } 354 355 #ifdef _MSC_VER 356 #pragma comment(linker, "/alternatename:ExpInterlockedPopEntrySList=RtlInterlockedPopEntrySList") 357 #pragma comment(linker, "/alternatename:ExpInterlockedPushEntrySList=RtlInterlockedPushEntrySList") 358 #pragma comment(linker, "/alternatename:ExpInterlockedFlushSList=RtlInterlockedFlushSList") 359 #else 360 #pragma redefine_extname RtlInterlockedPopEntrySList ExpInterlockedPopEntrySList 361 #pragma redefine_extname RtlInterlockedPushEntrySList ExpInterlockedPushEntrySList 362 #pragma redefine_extname RtlInterlockedFlushSList ExpInterlockedFlushSList 363 #endif 364 365 #endif 366 367