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
RtlInitializeSListHead(_Out_ PSLIST_HEADER SListHead)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
RtlFirstEntrySList(_In_ const SLIST_HEADER * SListHead)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
RtlQueryDepthSList(_In_ PSLIST_HEADER SListHead)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
RtlInterlockedPushListSList(_Inout_ PSLIST_HEADER SListHead,_Inout_ __drv_aliasesMem PSLIST_ENTRY List,_Inout_ PSLIST_ENTRY ListEnd,_In_ ULONG Count)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((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. */
222 BOOLEAN RtlpExpectSListFault;
223
224 PSLIST_ENTRY
225 NTAPI
RtlInterlockedPushEntrySList(_Inout_ PSLIST_HEADER SListHead,_Inout_ __drv_aliasesMem PSLIST_ENTRY SListEntry)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
RtlInterlockedPopEntrySList(_Inout_ PSLIST_HEADER SListHead)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
RtlInterlockedFlushSList(_Inout_ PSLIST_HEADER SListHead)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