Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367/* * COPYRIGHT: See COPYING in the top level directory * PROJECT: ReactOS Runtime Library * PURPOSE: Slist Routines * FILE: lib/rtl/slist.c * PROGRAMERS: Stefan Ginsberg (stefan.ginsberg@reactos.org) * Timo Kreuzer (timo.kreuzer@reactos.org) */
/* INCLUDES *****************************************************************/
#include <rtl.h>
#define NDEBUG#include <debug.h>
#ifdef _WIN64BOOLEAN RtlpUse16ByteSLists = -1;#endif
/* FUNCTIONS ***************************************************************/
VOIDNTAPIRtlInitializeSListHead( _Out_ PSLIST_HEADER SListHead){#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 /* On amd64 we don't need to store anything */ SListHead->Region = 0;#endif /* _IA64_ */#endif /* _WIN64 */
SListHead->Alignment = 0;}
PSLIST_ENTRYNTAPIRtlFirstEntrySList( _In_ const SLIST_HEADER *SListHead){#if defined(_WIN64) /* Check if the header is initialized as 16 byte header */ if (SListHead->Header16.HeaderType) { return (PVOID)(SListHead->Region & ~0xFLL); } else { union { ULONG64 Region; struct { ULONG64 Reserved:4; ULONG64 NextEntry:39; ULONG64 Reserved2:21; } Bits; } Pointer;
#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 SListHead->Next.Next;#endif}
WORDNTAPIRtlQueryDepthSList( _In_ PSLIST_HEADER SListHead){#if defined(_WIN64) return (USHORT)(SListHead->Alignment & 0xffff);#else return SListHead->Depth;#endif}
PSLIST_ENTRYFASTCALLRtlInterlockedPushListSList( _Inout_ PSLIST_HEADER SListHead, _Inout_ __drv_aliasesMem PSLIST_ENTRY List, _Inout_ PSLIST_ENTRY ListEnd, _In_ ULONG Count){#ifdef _WIN64 SLIST_HEADER OldSListHead, NewSListHead; PSLIST_ENTRY FirstEntry;
ASSERT(((ULONG_PTR)SListHead & 0xF) == 0); ASSERT(((ULONG_PTR)List & 0xF) == 0);
if (RtlpUse16ByteSLists) { BOOLEAN exchanged;
do { /* Capture the current SListHead */ OldSListHead = *SListHead;
/* Link the last list entry */ FirstEntry = (PSLIST_ENTRY)(SListHead->Region & ~0xFLL); ListEnd->Next = FirstEntry;
/* Set up new SListHead */ NewSListHead = OldSListHead; NewSListHead.Header16.Depth += Count; NewSListHead.Header16.Sequence++; NewSListHead.Region = (ULONG64)List; NewSListHead.Header16.HeaderType = 1; NewSListHead.Header16.Init = 1;
/* Atomically exchange the SlistHead with the new one */ exchanged = _InterlockedCompareExchange128((PLONG64)SListHead, NewSListHead.Region, NewSListHead.Alignment, (PLONG64)&OldSListHead); } while (!exchanged);
return FirstEntry; } else { ULONG64 Compare;
/* ListHead and List must be in the same region */ ASSERT(((ULONG64)SListHead & 0xFFFFF80000000000ull) == ((ULONG64)List & 0xFFFFF80000000000ull));
/* Read the header */ OldSListHead = *SListHead;
do { /* Construct the address from the header bits and the list head pointer */ FirstEntry = (PSLIST_ENTRY)((OldSListHead.Header8.NextEntry << 4) | ((ULONG64)SListHead & 0xFFFFF80000000000ull));
/* Link the last list entry */ ListEnd->Next = FirstEntry;
/* Create a new header */ NewSListHead = OldSListHead; NewSListHead.Header8.NextEntry = (ULONG64)List >> 4; NewSListHead.Header8.Depth += Count; NewSListHead.Header8.Sequence++;
/* Try to exchange atomically */ Compare = OldSListHead.Alignment; OldSListHead.Alignment = InterlockedCompareExchange64((PLONG64)&SListHead->Alignment, NewSListHead.Alignment, Compare); } while (OldSListHead.Alignment != Compare);
/* Return the old first entry */ return FirstEntry; }#else 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_ENTRYNTAPIRtlInterlockedPushEntrySList( _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_ENTRYNTAPIRtlInterlockedPopEntrySList( _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_ENTRYNTAPIRtlInterlockedFlushSList( _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