[RTL]
[reactos.git] / reactos / lib / rtl / slist.c
index fe96ab6..b7a357f 100644 (file)
@@ -4,6 +4,7 @@
  * PURPOSE:         Slist Routines
  * FILE:            lib/rtl/slist.c
  * PROGRAMERS:      Stefan Ginsberg (stefan__100__@hotmail.com)
+ *                  Timo Kreuzer (timo.kreuzer@reactos.org)
  */
 
 /* INCLUDES *****************************************************************/
 #define NDEBUG
 #include <debug.h>
 
+#ifdef _WIN64
+BOOLEAN RtlpUse16ByteSLists = -1;
+#endif
+
 /* FUNCTIONS ***************************************************************/
 
 VOID
 NTAPI
-RtlInitializeSListHead(IN PSLIST_HEADER ListHead)
+RtlInitializeSListHead(
+    _Out_ PSLIST_HEADER SListHead)
 {
-#ifdef _WIN64
-    ListHead->Alignment = 0;
-    ListHead->Region = 0;
-    ListHead->Header8.Init = 1;
-    // ListHead->Header8.HeaderType = 1; // FIXME: depending on cmpxchg16b support?
+#if defined(_WIN64)
+    /* Make sure the header is 16 byte aligned */
+    if (((ULONG_PTR)SListHead & 0xf) != 0)
+    {
+        DPRINT1("Unaligned SListHead: 0x%p\n", SListHead);
+        RtlRaiseStatus(STATUS_DATATYPE_MISALIGNMENT);
+    }
+
+    /* Initialize the Region member */
+#if defined(_IA64_)
+    /* On Itanium we store the region in the list head */
+    SListHead->Region = (ULONG_PTR)SListHead & VRN_MASK;
 #else
-    ListHead->Alignment = 0;
-#endif
+    /* On amd64 we don't need to store anything */
+    SListHead->Region = 0;
+#endif /* _IA64_ */
+#endif /* _WIN64 */
+
+    SListHead->Alignment = 0;
 }
 
 PSLIST_ENTRY
 NTAPI
-RtlFirstEntrySList(IN const SLIST_HEADER *ListHead)
+RtlFirstEntrySList(
+    _In_ const SLIST_HEADER *SListHead)
 {
-#ifdef _WIN64
-    if (ListHead->Header8.HeaderType)
+#if defined(_WIN64)
+    /* Check if the header is initialized as 16 byte header */
+    if (SListHead->Header16.HeaderType)
     {
-        return (PVOID)(ListHead->Region & ~0xF);
+        return (PVOID)(SListHead->Region & ~0xFLL);
     }
     else
     {
         union {
-            PVOID P;
+            ULONG64 Region;
             struct {
                 ULONG64 Reserved:4;
                 ULONG64 NextEntry:39;
@@ -49,23 +68,230 @@ RtlFirstEntrySList(IN const SLIST_HEADER *ListHead)
             } Bits;
         } Pointer;
 
-        Pointer.P = (PVOID)ListHead;
-        Pointer.Bits.NextEntry = ListHead->Header8.NextEntry;
-        return Pointer.P;
+#if defined(_IA64_)
+        /* On Itanium we stored the region in the list head */
+        Pointer.Region = SListHead->Region;;
+#else
+        /* On amd64 we just use the list head itself */
+        Pointer.Region = (ULONG64)SListHead;
+#endif
+        Pointer.Bits.NextEntry = SListHead->Header8.NextEntry;
+        return (PVOID)Pointer.Region;
     }
 #else
-    return ListHead->Next.Next;
+    return SListHead->Next.Next;
 #endif
 }
 
 WORD
 NTAPI
-RtlQueryDepthSList(IN PSLIST_HEADER ListHead)
+RtlQueryDepthSList(
+    _In_ PSLIST_HEADER SListHead)
+{
+#if defined(_WIN64)
+    return (USHORT)(SListHead->Alignment & 0xffff);
+#else
+    return SListHead->Depth;
+#endif
+}
+
+PSLIST_ENTRY
+FASTCALL
+RtlInterlockedPushListSList(
+    _Inout_ PSLIST_HEADER SListHead,
+    _Inout_ __drv_aliasesMem PSLIST_ENTRY List,
+    _Inout_ PSLIST_ENTRY ListEnd,
+    _In_ ULONG Count)
 {
 #ifdef _WIN64
-    return ListHead->Header8.HeaderType ?
-        (WORD)ListHead->Header16.Sequence : (WORD)ListHead->Header8.Sequence;
+    UNIMPLEMENTED;
+    DbgBreakPoint();
+    return NULL;
 #else
-    return ListHead->Depth;
+    SLIST_HEADER OldHeader, NewHeader;
+    ULONGLONG Compare;
+
+    /* Read the header */
+    OldHeader = *SListHead;
+
+    do
+    {
+        /* Link the last list entry */
+        ListEnd->Next = OldHeader.Next.Next;
+
+        /* Create a new header */
+        NewHeader = OldHeader;
+        NewHeader.Next.Next = List;
+        NewHeader.Depth += Count;
+        NewHeader.Sequence++;
+
+        /* Try to exchange atomically */
+        Compare = OldHeader.Alignment;
+        OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
+                                                           NewHeader.Alignment,
+                                                           Compare);
+    }
+    while (OldHeader.Alignment != Compare);
+
+    /* Return the old first entry */
+    return OldHeader.Next.Next;
+#endif /* _WIN64 */
+}
+
+
+#if !defined(_M_IX86) && !defined(_M_AMD64)
+
+_WARN("C based S-List functions can bugcheck, if not handled properly in kernel")
+
+#ifdef _WIN64
+#error "No generic S-List functions for WIN64!"
 #endif
+
+/* This variable must be used in kernel mode to prevent the system from
+   bugchecking on non-present kernel memory. If this variable is set to TRUE
+   an exception needs to be dispatched. */
+BOOLEAN RtlpExpectSListFault;
+
+PSLIST_ENTRY
+NTAPI
+RtlInterlockedPushEntrySList(
+    _Inout_ PSLIST_HEADER SListHead,
+    _Inout_ __drv_aliasesMem PSLIST_ENTRY SListEntry)
+{
+    SLIST_HEADER OldHeader, NewHeader;
+    ULONGLONG Compare;
+
+    /* Read the header */
+    OldHeader = *SListHead;
+
+    do
+    {
+        /* Link the list entry */
+        SListEntry->Next = OldHeader.Next.Next;
+
+        /* Create a new header */
+        NewHeader = OldHeader;
+        NewHeader.Next.Next = SListEntry;
+        NewHeader.Depth++;
+        NewHeader.Sequence++;
+
+        /* Try to exchange atomically */
+        Compare = OldHeader.Alignment;
+        OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
+                                                           NewHeader.Alignment,
+                                                           Compare);
+    }
+    while (OldHeader.Alignment != Compare);
+
+    /* Return the old first entry */
+    return OldHeader.Next.Next;
+}
+
+PSLIST_ENTRY
+NTAPI
+RtlInterlockedPopEntrySList(
+    _Inout_ PSLIST_HEADER SListHead)
+{
+    SLIST_HEADER OldHeader, NewHeader;
+    ULONGLONG Compare;
+
+restart:
+
+    /* Read the header */
+    OldHeader = *SListHead;
+
+    do
+    {
+        /* Check for empty list */
+        if (OldHeader.Next.Next == NULL)
+        {
+            return NULL;
+        }
+
+        /* Create a new header */
+        NewHeader = OldHeader;
+
+        /* HACK to let the kernel know that we are doing slist-magic */
+        RtlpExpectSListFault = TRUE;
+
+        /* Wrapped in SEH, since OldHeader.Next.Next can already be freed */
+        _SEH2_TRY
+        {
+            NewHeader.Next = *OldHeader.Next.Next;
+        }
+        _SEH2_EXCEPT((SListHead->Next.Next != OldHeader.Next.Next) ?
+                     EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH)
+        {
+            /* We got an exception and the list head changed.
+               Restart the whole operation. */
+            RtlpExpectSListFault = FALSE;
+            goto restart;
+        }
+        _SEH2_END;
+
+        /* We are done */
+        RtlpExpectSListFault = FALSE;
+
+        /* Adjust depth */
+        NewHeader.Depth--;
+
+        /* Try to exchange atomically */
+        Compare = OldHeader.Alignment;
+        OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)SListHead->Alignment,
+                                                           NewHeader.Alignment,
+                                                           Compare);
+    }
+    while (OldHeader.Alignment != Compare);
+
+    return OldHeader.Next.Next;
 }
+
+PSLIST_ENTRY
+NTAPI
+RtlInterlockedFlushSList(
+    _Inout_ PSLIST_HEADER SListHead)
+{
+    SLIST_HEADER OldHeader, NewHeader;
+    ULONGLONG Compare;
+
+    /* Read the header */
+    OldHeader = *SListHead;
+
+    do
+    {
+        /* Check for empty list */
+        if (OldHeader.Next.Next == NULL)
+        {
+            return NULL;
+        }
+
+        /* Create a new header (keep the sequence number) */
+        NewHeader = OldHeader;
+        NewHeader.Next.Next = NULL;
+        NewHeader.Depth = 0;
+
+        /* Try to exchange atomically */
+        Compare = OldHeader.Alignment;
+        OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
+                                                           NewHeader.Alignment,
+                                                           Compare);
+    }
+    while (OldHeader.Alignment != Compare);
+
+    /* Return the old first entry */
+    return OldHeader.Next.Next;
+
+}
+
+#ifdef _MSC_VER
+#pragma comment(linker, "/alternatename:ExpInterlockedPopEntrySList=RtlInterlockedPopEntrySList")
+#pragma comment(linker, "/alternatename:ExpInterlockedPushEntrySList=RtlInterlockedPushEntrySList")
+#pragma comment(linker, "/alternatename:ExpInterlockedFlushSList=RtlInterlockedFlushSList")
+#else
+#pragma redefine_extname RtlInterlockedPopEntrySList ExpInterlockedPopEntrySList
+#pragma redefine_extname RtlInterlockedPushEntrySList ExpInterlockedPushEntrySList
+#pragma redefine_extname RtlInterlockedFlushSList ExpInterlockedFlushSList
+#endif
+
+#endif
+