huwcampbell.com
Reactos
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
18BOOLEAN RtlpUse16ByteSLists = -1;
19#endif
20
21/* FUNCTIONS ***************************************************************/
22
23VOID
24NTAPI
25RtlInitializeSListHead(
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
49PSLIST_ENTRY
50NTAPI
51RtlFirstEntrySList(
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
86WORD
87NTAPI
88RtlQueryDepthSList(
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
98PSLIST_ENTRY
99FASTCALL
100RtlInterlockedPushListSList(
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((PLONG64)SListHead,
136 NewSListHead.Region,
137 NewSListHead.Alignment,
138 (PLONG64)&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. */
222BOOLEAN RtlpExpectSListFault;
223
224PSLIST_ENTRY
225NTAPI
226RtlInterlockedPushEntrySList(
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
259PSLIST_ENTRY
260NTAPI
261RtlInterlockedPopEntrySList(
262 _Inout_ PSLIST_HEADER SListHead)
263{
264 SLIST_HEADER OldHeader, NewHeader;
265 ULONGLONG Compare;
266
267restart:
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
318PSLIST_ENTRY
319NTAPI
320RtlInterlockedFlushSList(
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