ReactOS 0.4.15-dev-8102-g108db8f
slist.c
Go to the documentation of this file.
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
19#endif
20
21/* FUNCTIONS ***************************************************************/
22
23VOID
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);
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
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 {
64 struct {
66 ULONG64 NextEntry:39;
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
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
101 _Inout_ PSLIST_HEADER SListHead,
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
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. */
223
225NTAPI
227 _Inout_ PSLIST_HEADER SListHead,
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
260NTAPI
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 */
285
286 /* Wrapped in SEH, since OldHeader.Next.Next can already be freed */
288 {
289 NewHeader.Next = *OldHeader.Next.Next;
290 }
291 _SEH2_EXCEPT((SListHead->Next.Next != OldHeader.Next.Next) ?
293 {
294 /* We got an exception and the list head changed.
295 Restart the whole operation. */
297 goto restart;
298 }
299 _SEH2_END;
300
301 /* We are done */
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
319NTAPI
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
unsigned char BOOLEAN
void restart(int argc, const char *argv[])
Definition: cmds.c:2115
#define DPRINT1
Definition: precomp.h:8
__int64 * PLONG64
Definition: basetsd.h:183
@ Reserved2
Definition: bcd.h:202
#define __drv_aliasesMem
Definition: btrfs_drv.h:203
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define ULONG_PTR
Definition: config.h:101
#define _SEH2_END
Definition: filesup.c:22
#define _SEH2_TRY
Definition: filesup.c:19
unsigned short WORD
Definition: ntddk_ex.h:93
#define EXCEPTION_EXECUTE_HANDLER
Definition: excpt.h:85
#define EXCEPTION_CONTINUE_SEARCH
Definition: excpt.h:86
#define InterlockedCompareExchange64
Definition: interlocked.h:114
BOOLEAN RtlpUse16ByteSLists
#define ASSERT(a)
Definition: mode.c:44
unsigned __int64 ULONG64
Definition: imports.h:198
#define _Inout_
Definition: ms_sal.h:378
#define _Out_
Definition: ms_sal.h:345
#define _In_
Definition: ms_sal.h:308
DECLSPEC_NORETURN NTSYSAPI VOID NTAPI RtlRaiseStatus(_In_ NTSTATUS Status)
int Count
Definition: noreturn.cpp:7
#define FASTCALL
Definition: nt_native.h:50
__GNU_EXTENSION typedef __int64 * PLONGLONG
Definition: ntbasedef.h:382
#define STATUS_DATATYPE_MISALIGNMENT
Definition: ntstatus.h:183
unsigned short USHORT
Definition: pedump.c:61
#define _SEH2_EXCEPT(...)
Definition: pseh2_64.h:66
#define _WARN(msg)
Definition: debug.h:263
PSLIST_ENTRY NTAPI RtlInterlockedPushEntrySList(_Inout_ PSLIST_HEADER SListHead, _Inout_ __drv_aliasesMem PSLIST_ENTRY SListEntry)
Definition: slist.c:226
PSLIST_ENTRY FASTCALL RtlInterlockedPushListSList(_Inout_ PSLIST_HEADER SListHead, _Inout_ __drv_aliasesMem PSLIST_ENTRY List, _Inout_ PSLIST_ENTRY ListEnd, _In_ ULONG Count)
Definition: slist.c:100
PSLIST_ENTRY NTAPI RtlInterlockedFlushSList(_Inout_ PSLIST_HEADER SListHead)
Definition: slist.c:320
WORD NTAPI RtlQueryDepthSList(_In_ PSLIST_HEADER SListHead)
Definition: slist.c:88
VOID NTAPI RtlInitializeSListHead(_Out_ PSLIST_HEADER SListHead)
Definition: slist.c:25
BOOLEAN RtlpExpectSListFault
Definition: slist.c:222
PSLIST_ENTRY NTAPI RtlInterlockedPopEntrySList(_Inout_ PSLIST_HEADER SListHead)
Definition: slist.c:261
PSLIST_ENTRY NTAPI RtlFirstEntrySList(_In_ const SLIST_HEADER *SListHead)
Definition: slist.c:51
#define NTAPI
Definition: typedefs.h:36
uint32_t ULONG_PTR
Definition: typedefs.h:65
uint32_t ULONG
Definition: typedefs.h:59
uint64_t ULONGLONG
Definition: typedefs.h:67
ULONGLONG Alignment
Definition: rtltypes.h:139
USHORT Sequence
Definition: rtltypes.h:143
SLIST_ENTRY Next
Definition: rtltypes.h:141
USHORT Depth
Definition: rtltypes.h:142
_Must_inspect_result_ _In_ WDFCMRESLIST List
Definition: wdfresource.h:550
_Reserved_ PVOID Reserved
Definition: winddi.h:3974
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY ListEnd
Definition: exfuncs.h:1224
#define PSLIST_ENTRY
Definition: rtltypes.h:134