ReactOS  0.4.14-dev-342-gdc047f9
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 
23 VOID
24 NTAPI
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 
50 NTAPI
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 {
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
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,
104  _In_ ULONG Count)
105 {
106 #ifdef _WIN64
108  DbgBreakPoint();
109  return NULL;
110 #else
111  SLIST_HEADER OldHeader, NewHeader;
112  ULONGLONG Compare;
113 
114  /* Read the header */
115  OldHeader = *SListHead;
116 
117  do
118  {
119  /* Link the last list entry */
120  ListEnd->Next = OldHeader.Next.Next;
121 
122  /* Create a new header */
123  NewHeader = OldHeader;
124  NewHeader.Next.Next = List;
125  NewHeader.Depth += Count;
126  NewHeader.Sequence++;
127 
128  /* Try to exchange atomically */
129  Compare = OldHeader.Alignment;
130  OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
131  NewHeader.Alignment,
132  Compare);
133  }
134  while (OldHeader.Alignment != Compare);
135 
136  /* Return the old first entry */
137  return OldHeader.Next.Next;
138 #endif /* _WIN64 */
139 }
140 
141 
142 #if !defined(_M_IX86) && !defined(_M_AMD64)
143 
144 _WARN("C based S-List functions can bugcheck, if not handled properly in kernel")
145 
146 #ifdef _WIN64
147 #error "No generic S-List functions for WIN64!"
148 #endif
149 
150 /* This variable must be used in kernel mode to prevent the system from
151  bugchecking on non-present kernel memory. If this variable is set to TRUE
152  an exception needs to be dispatched. */
154 
156 NTAPI
158  _Inout_ PSLIST_HEADER SListHead,
160 {
161  SLIST_HEADER OldHeader, NewHeader;
162  ULONGLONG Compare;
163 
164  /* Read the header */
165  OldHeader = *SListHead;
166 
167  do
168  {
169  /* Link the list entry */
170  SListEntry->Next = OldHeader.Next.Next;
171 
172  /* Create a new header */
173  NewHeader = OldHeader;
174  NewHeader.Next.Next = SListEntry;
175  NewHeader.Depth++;
176  NewHeader.Sequence++;
177 
178  /* Try to exchange atomically */
179  Compare = OldHeader.Alignment;
180  OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
181  NewHeader.Alignment,
182  Compare);
183  }
184  while (OldHeader.Alignment != Compare);
185 
186  /* Return the old first entry */
187  return OldHeader.Next.Next;
188 }
189 
191 NTAPI
193  _Inout_ PSLIST_HEADER SListHead)
194 {
195  SLIST_HEADER OldHeader, NewHeader;
196  ULONGLONG Compare;
197 
198 restart:
199 
200  /* Read the header */
201  OldHeader = *SListHead;
202 
203  do
204  {
205  /* Check for empty list */
206  if (OldHeader.Next.Next == NULL)
207  {
208  return NULL;
209  }
210 
211  /* Create a new header */
212  NewHeader = OldHeader;
213 
214  /* HACK to let the kernel know that we are doing slist-magic */
216 
217  /* Wrapped in SEH, since OldHeader.Next.Next can already be freed */
218  _SEH2_TRY
219  {
220  NewHeader.Next = *OldHeader.Next.Next;
221  }
222  _SEH2_EXCEPT((SListHead->Next.Next != OldHeader.Next.Next) ?
224  {
225  /* We got an exception and the list head changed.
226  Restart the whole operation. */
228  goto restart;
229  }
230  _SEH2_END;
231 
232  /* We are done */
234 
235  /* Adjust depth */
236  NewHeader.Depth--;
237 
238  /* Try to exchange atomically */
239  Compare = OldHeader.Alignment;
240  OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)SListHead->Alignment,
241  NewHeader.Alignment,
242  Compare);
243  }
244  while (OldHeader.Alignment != Compare);
245 
246  return OldHeader.Next.Next;
247 }
248 
250 NTAPI
252  _Inout_ PSLIST_HEADER SListHead)
253 {
254  SLIST_HEADER OldHeader, NewHeader;
255  ULONGLONG Compare;
256 
257  /* Read the header */
258  OldHeader = *SListHead;
259 
260  do
261  {
262  /* Check for empty list */
263  if (OldHeader.Next.Next == NULL)
264  {
265  return NULL;
266  }
267 
268  /* Create a new header (keep the sequence number) */
269  NewHeader = OldHeader;
270  NewHeader.Next.Next = NULL;
271  NewHeader.Depth = 0;
272 
273  /* Try to exchange atomically */
274  Compare = OldHeader.Alignment;
275  OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
276  NewHeader.Alignment,
277  Compare);
278  }
279  while (OldHeader.Alignment != Compare);
280 
281  /* Return the old first entry */
282  return OldHeader.Next.Next;
283 
284 }
285 
286 #ifdef _MSC_VER
287 #pragma comment(linker, "/alternatename:ExpInterlockedPopEntrySList=RtlInterlockedPopEntrySList")
288 #pragma comment(linker, "/alternatename:ExpInterlockedPushEntrySList=RtlInterlockedPushEntrySList")
289 #pragma comment(linker, "/alternatename:ExpInterlockedFlushSList=RtlInterlockedFlushSList")
290 #else
291 #pragma redefine_extname RtlInterlockedPopEntrySList ExpInterlockedPopEntrySList
292 #pragma redefine_extname RtlInterlockedPushEntrySList ExpInterlockedPushEntrySList
293 #pragma redefine_extname RtlInterlockedFlushSList ExpInterlockedFlushSList
294 #endif
295 
296 #endif
297 
DECLSPEC_NORETURN NTSYSAPI VOID NTAPI RtlRaiseStatus(_In_ NTSTATUS Status)
PSLIST_ENTRY NTAPI RtlInterlockedPopEntrySList(_Inout_ PSLIST_HEADER SListHead)
Definition: slist.c:192
ULONGLONG Alignment
Definition: rtltypes.h:135
#define TRUE
Definition: types.h:120
#define LL
Definition: tui.h:85
#define InterlockedCompareExchange64
Definition: interlocked.h:114
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY ListEnd
Definition: exfuncs.h:1015
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY _In_ ULONG Count
Definition: exfuncs.h:1015
PSLIST_ENTRY NTAPI RtlInterlockedPushEntrySList(_Inout_ PSLIST_HEADER SListHead, _Inout_ __drv_aliasesMem PSLIST_ENTRY SListEntry)
Definition: slist.c:157
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
USHORT Sequence
Definition: rtltypes.h:139
void DbgBreakPoint()
Definition: mach.c:553
#define FASTCALL
Definition: nt_native.h:50
WORD NTAPI RtlQueryDepthSList(_In_ PSLIST_HEADER SListHead)
Definition: slist.c:88
_SEH2_TRY
Definition: create.c:4250
uint32_t ULONG_PTR
Definition: typedefs.h:63
__GNU_EXTENSION typedef __int64 * PLONGLONG
Definition: ntbasedef.h:389
#define EXCEPTION_CONTINUE_SEARCH
Definition: excpt.h:86
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
#define _WARN(msg)
Definition: debug.h:263
BOOLEAN RtlpExpectSListFault
Definition: slist.c:153
#define __drv_aliasesMem
Definition: btrfs_drv.h:189
#define EXCEPTION_EXECUTE_HANDLER
Definition: excpt.h:85
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
#define _Out_
Definition: no_sal2.h:323
_Reserved_ PVOID Reserved
Definition: winddi.h:3974
Definition: bcd.h:202
void restart(int argc, const char *argv[])
Definition: cmds.c:2115
SLIST_ENTRY Next
Definition: rtltypes.h:137
LIST_ENTRY List
Definition: psmgr.c:57
uint64_t ULONGLONG
Definition: typedefs.h:65
unsigned short WORD
Definition: ntddk_ex.h:93
PSLIST_ENTRY NTAPI RtlFirstEntrySList(_In_ const SLIST_HEADER *SListHead)
Definition: slist.c:51
#define PSLIST_ENTRY
Definition: rtltypes.h:130
#define _Inout_
Definition: no_sal2.h:244
unsigned __int64 ULONG64
Definition: imports.h:198
PSLIST_ENTRY NTAPI RtlInterlockedFlushSList(_Inout_ PSLIST_HEADER SListHead)
Definition: slist.c:251
#define _In_
Definition: no_sal2.h:204
_SEH2_END
Definition: create.c:4424
unsigned short USHORT
Definition: pedump.c:61
VOID NTAPI RtlInitializeSListHead(_Out_ PSLIST_HEADER SListHead)
Definition: slist.c:25
BOOLEAN RtlpUse16ByteSLists
#define DPRINT1
Definition: precomp.h:8
#define STATUS_DATATYPE_MISALIGNMENT
Definition: ntstatus.h:171
unsigned int ULONG
Definition: retypes.h:1
#define UNIMPLEMENTED
Definition: debug.h:114
#define ULONG_PTR
Definition: config.h:101
USHORT Depth
Definition: rtltypes.h:138
#define _SEH2_EXCEPT(...)
Definition: pseh2_64.h:6