sdk/lib/rtl/slist.c

   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     UNIMPLEMENTED;
 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. */
 153 BOOLEAN RtlpExpectSListFault;
 154
 155 PSLIST_ENTRY
 156 NTAPI
 157 RtlInterlockedPushEntrySList(
 158     _Inout_ PSLIST_HEADER SListHead,
 159     _Inout_ __drv_aliasesMem PSLIST_ENTRY SListEntry)
 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
 190 PSLIST_ENTRY
 191 NTAPI
 192 RtlInterlockedPopEntrySList(
 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 */
 215         RtlpExpectSListFault = TRUE;
 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) ?
 223                      EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH)
 224         {
 225             /* We got an exception and the list head changed.
 226                Restart the whole operation. */
 227             RtlpExpectSListFault = FALSE;
 228             goto restart;
 229         }
 230         _SEH2_END;
 231
 232         /* We are done */
 233         RtlpExpectSListFault = FALSE;
 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
 249 PSLIST_ENTRY
 250 NTAPI
 251 RtlInterlockedFlushSList(
 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