You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
788 lines
26 KiB
788 lines
26 KiB
/*++
|
|
|
|
Copyright (c) 1999-2000 Microsoft Corporation
|
|
|
|
Module Name:
|
|
|
|
fsbpool.c
|
|
|
|
Abstract:
|
|
|
|
This file contains the implementation of fixed-size block pool.
|
|
|
|
Author:
|
|
|
|
Shaun Cox (shaunco) 10-Dec-1999
|
|
|
|
--*/
|
|
|
|
#include "precomp.h"
|
|
#include <align.h> // Macros: ROUND_UP_POINTER, POINTER_IS_ALIGNED
|
|
|
|
#define FSB_SCAVENGE_PERIOD_IN_SECONDS 30
|
|
#define FSB_MINIMUM_PAGE_LIFETIME_IN_SECONDS 20
|
|
|
|
#if defined (_WIN64)
|
|
#define APPROX_L2_CACHE_LINE_SIZE 128
|
|
#define BLOCK_TYPE SLIST_HEADER
|
|
#else
|
|
#define APPROX_L2_CACHE_LINE_SIZE 64
|
|
#define BLOCK_TYPE PVOID
|
|
#endif
|
|
|
|
|
|
// The following structures are used in the single allocation that
|
|
// a pool handle points to.
|
|
// PoolHandle ---> [FSB_POOL_HEADER + FSB_CPU_POOL_HEADER for cpu 0 +
|
|
// FSB_CPU_POOL_HEADER for cpu 1 + ...
|
|
// FSB_CPU_POOL_HEADER for cpu N]
|
|
//
|
|
|
|
// FSB_POOL_HEADER is the data common to all CPUs for a given pool.
|
|
//
|
|
typedef struct _FSB_POOL_HEADER
|
|
{
|
|
// cache-line -----
|
|
struct _FSB_POOL_HEADER_BASE
|
|
{
|
|
ULONG Tag;
|
|
USHORT CallerBlockSize; // caller's requested block size
|
|
USHORT AlignedBlockSize; // ALIGN_UP(CallerBlockSize, PVOID)
|
|
USHORT BlocksPerPage;
|
|
USHORT FreeBlockLinkOffset;
|
|
NDIS_BLOCK_INITIALIZER BuildFunction;
|
|
PVOID Allocation;
|
|
KSPIN_LOCK Interlock;
|
|
};
|
|
UCHAR Alignment[APPROX_L2_CACHE_LINE_SIZE
|
|
- (sizeof(struct _FSB_POOL_HEADER_BASE) % APPROX_L2_CACHE_LINE_SIZE)];
|
|
} FSB_POOL_HEADER, *PFSB_POOL_HEADER;
|
|
|
|
C_ASSERT(sizeof(FSB_POOL_HEADER) % APPROX_L2_CACHE_LINE_SIZE == 0);
|
|
|
|
|
|
// FSB_CPU_POOL_HEADER is the data specific to a CPU for a given pool.
|
|
//
|
|
typedef struct _FSB_CPU_POOL_HEADER
|
|
{
|
|
// cache-line -----
|
|
struct _FSB_CPU_POOL_HEADER_BASE
|
|
{
|
|
// The doubly-linked list of pages that make up this processor's pool.
|
|
// These pages have one or more free blocks available.
|
|
//
|
|
LIST_ENTRY PageList;
|
|
|
|
// The doubly-linked list of pages that are fully in use. This list
|
|
// is separate from the above list so that we do not spend time walking
|
|
// a very long list during FsbAllocate when many pages are fully used.
|
|
//
|
|
LIST_ENTRY UsedPageList;
|
|
|
|
// The next scheduled time (in units of KeQueryTickCount()) for
|
|
// scavenging this pool. The next scavenge will happen no earlier
|
|
// than this.
|
|
//
|
|
LARGE_INTEGER NextScavengeTick;
|
|
|
|
// The number of the processor that owns this pool.
|
|
//
|
|
ULONG OwnerCpu;
|
|
|
|
ULONG TotalBlocksAllocated;
|
|
ULONG TotalBlocksFreed;
|
|
ULONG PeakBlocksInUse;
|
|
ULONG TotalPagesAllocated;
|
|
ULONG TotalPagesFreed;
|
|
ULONG PeakPagesInUse;
|
|
};
|
|
UCHAR Alignment[APPROX_L2_CACHE_LINE_SIZE
|
|
- (sizeof(struct _FSB_CPU_POOL_HEADER_BASE) % APPROX_L2_CACHE_LINE_SIZE)];
|
|
} FSB_CPU_POOL_HEADER, *PFSB_CPU_POOL_HEADER;
|
|
|
|
C_ASSERT(sizeof(FSB_CPU_POOL_HEADER) % APPROX_L2_CACHE_LINE_SIZE == 0);
|
|
|
|
|
|
|
|
// FSB_PAGE_HEADER is the data at the beginning of each allocated pool page
|
|
// that describes the current state of the blocks on the page.
|
|
//
|
|
typedef struct _FSB_PAGE_HEADER
|
|
{
|
|
// cache-line -----
|
|
// Back pointer to the owning cpu pool.
|
|
//
|
|
PFSB_CPU_POOL_HEADER Pool;
|
|
|
|
// Linkage entry for the list of pages managed by the cpu pool.
|
|
//
|
|
LIST_ENTRY PageLink;
|
|
|
|
// Number of blocks built so far on this page. Blocks are built on
|
|
// demand. When this number reaches Pool->BlocksPerPage, all blocks on
|
|
// this page have been built.
|
|
//
|
|
USHORT BlocksBuilt;
|
|
|
|
// Boolean indicator of whether or not this page is on the cpu pool's
|
|
// used-page list. This is checked during FsbFree to see if the page
|
|
// should be moved back to the normal page list.
|
|
// (it is a USHORT, instead of BOOLEAN, for proper padding)
|
|
//
|
|
USHORT OnUsedPageList;
|
|
|
|
// List of free blocks on this page.
|
|
//
|
|
SLIST_HEADER FreeList;
|
|
|
|
// The value of KeQueryTickCount (normalized to units of seconds)
|
|
// which represents the time after which this page can be freed back
|
|
// to the system's pool. This time is only used once the depth of
|
|
// FreeList is Pool->BlocksPerPage. (i.e. this time is only used if
|
|
// the page is completely unused.)
|
|
//
|
|
LARGE_INTEGER LastUsedTick;
|
|
|
|
} FSB_PAGE_HEADER, *PFSB_PAGE_HEADER;
|
|
|
|
// Get a pointer to the overall pool given a pointer to one of
|
|
// the per-processor pools within it.
|
|
//
|
|
__inline
|
|
PFSB_POOL_HEADER
|
|
PoolFromCpuPool(
|
|
IN PFSB_CPU_POOL_HEADER CpuPool
|
|
)
|
|
{
|
|
return (PFSB_POOL_HEADER)(CpuPool - CpuPool->OwnerCpu) - 1;
|
|
}
|
|
|
|
|
|
__inline
|
|
VOID
|
|
ConvertSecondsToTicks(
|
|
IN ULONG Seconds,
|
|
OUT PLARGE_INTEGER Ticks
|
|
)
|
|
{
|
|
// If the following assert fires, you need to cast Seconds below to
|
|
// ULONGLONG so that 64 bit multiplication and division are used.
|
|
// The current code assumes less than 430 seconds so that the
|
|
// 32 multiplication below won't overflow.
|
|
//
|
|
ASSERT(Seconds < 430);
|
|
|
|
Ticks->HighPart = 0;
|
|
Ticks->LowPart = (Seconds * 10*1000*1000) / KeQueryTimeIncrement();
|
|
}
|
|
|
|
// Build the next block on the specified pool page.
|
|
// This can only be called if not all of the blocks have been built yet.
|
|
//
|
|
PUCHAR
|
|
FsbpBuildNextBlock(
|
|
IN const FSB_POOL_HEADER* Pool,
|
|
IN OUT PFSB_PAGE_HEADER Page
|
|
)
|
|
{
|
|
PUCHAR Block;
|
|
|
|
ASSERT(Page->BlocksBuilt < Pool->BlocksPerPage);
|
|
ASSERT((PAGE_SIZE - sizeof(FSB_PAGE_HEADER)) / Pool->AlignedBlockSize
|
|
== Pool->BlocksPerPage);
|
|
ASSERT(Pool->CallerBlockSize <= Pool->AlignedBlockSize);
|
|
|
|
Block = (PUCHAR)(Page + 1) + (Page->BlocksBuilt * Pool->AlignedBlockSize);
|
|
ASSERT(PAGE_ALIGN(Block) == Page);
|
|
|
|
if (Pool->BuildFunction) {
|
|
Pool->BuildFunction(Block, Pool->CallerBlockSize);
|
|
}
|
|
|
|
Page->BlocksBuilt++;
|
|
|
|
return Block;
|
|
}
|
|
|
|
// Allocate a new pool page and insert it at the head of the specified
|
|
// CPU pool. Build the first block on the new page and return a pointer
|
|
// to it.
|
|
//
|
|
PUCHAR
|
|
FsbpAllocateNewPageAndBuildOneBlock(
|
|
IN const FSB_POOL_HEADER* Pool,
|
|
IN PFSB_CPU_POOL_HEADER CpuPool
|
|
)
|
|
{
|
|
PFSB_PAGE_HEADER Page;
|
|
PUCHAR Block = NULL;
|
|
ULONG PagesInUse;
|
|
|
|
ASSERT(Pool);
|
|
|
|
Page = ExAllocatePoolWithTag(NonPagedPool, PAGE_SIZE, Pool->Tag);
|
|
if (Page)
|
|
{
|
|
ASSERT(Page == PAGE_ALIGN(Page));
|
|
|
|
RtlZeroMemory(Page, sizeof(FSB_PAGE_HEADER));
|
|
Page->Pool = CpuPool;
|
|
ExInitializeSListHead(&Page->FreeList);
|
|
|
|
// Insert the page at the head of the cpu's pool.
|
|
//
|
|
InsertHeadList(&CpuPool->PageList, &Page->PageLink);
|
|
CpuPool->TotalPagesAllocated++;
|
|
|
|
// Update the pool's statistics.
|
|
//
|
|
PagesInUse = CpuPool->TotalPagesAllocated - CpuPool->TotalPagesFreed;
|
|
if (PagesInUse > CpuPool->PeakPagesInUse)
|
|
{
|
|
CpuPool->PeakPagesInUse = PagesInUse;
|
|
}
|
|
|
|
Block = FsbpBuildNextBlock(Pool, Page);
|
|
ASSERT(Block);
|
|
}
|
|
|
|
return Block;
|
|
}
|
|
|
|
// Free the specified pool page back to the system's pool.
|
|
//
|
|
VOID
|
|
FsbpFreePage(
|
|
IN PFSB_CPU_POOL_HEADER CpuPool,
|
|
IN PFSB_PAGE_HEADER Page
|
|
)
|
|
{
|
|
ASSERT(Page == PAGE_ALIGN(Page));
|
|
ASSERT(Page->Pool == CpuPool);
|
|
|
|
ExFreePool(Page);
|
|
CpuPool->TotalPagesFreed++;
|
|
|
|
ASSERT(CpuPool->TotalPagesFreed <= CpuPool->TotalPagesAllocated);
|
|
}
|
|
|
|
// Free the specified pool page list back to the system's pool.
|
|
//
|
|
VOID
|
|
FsbpFreeList(
|
|
IN PFSB_CPU_POOL_HEADER CpuPool,
|
|
IN PLIST_ENTRY Head
|
|
)
|
|
{
|
|
PFSB_POOL_HEADER Pool;
|
|
PFSB_PAGE_HEADER Page;
|
|
PLIST_ENTRY Scan;
|
|
PLIST_ENTRY Next;
|
|
BOOLEAN UsedPageList;
|
|
|
|
Pool = PoolFromCpuPool(CpuPool);
|
|
UsedPageList = (Head == &CpuPool->UsedPageList);
|
|
|
|
for (Scan = Head->Flink; Scan != Head; Scan = Next)
|
|
{
|
|
Page = CONTAINING_RECORD(Scan, FSB_PAGE_HEADER, PageLink);
|
|
ASSERT(Page == PAGE_ALIGN(Page));
|
|
ASSERT(CpuPool == Page->Pool);
|
|
ASSERT(UsedPageList ? Page->OnUsedPageList : !Page->OnUsedPageList);
|
|
|
|
ASSERT(Page->BlocksBuilt <= Pool->BlocksPerPage);
|
|
ASSERT(Page->BlocksBuilt == ExQueryDepthSList(&Page->FreeList));
|
|
|
|
// Step to the next link before we free this page.
|
|
//
|
|
Next = Scan->Flink;
|
|
|
|
RemoveEntryList(Scan);
|
|
FsbpFreePage(CpuPool, Page);
|
|
}
|
|
}
|
|
|
|
// Reclaim the memory consumed by completely unused pool pages belonging
|
|
// to the specified per-processor pool.
|
|
//
|
|
// Caller IRQL: [DISPATCH_LEVEL]
|
|
//
|
|
VOID
|
|
FsbpScavengePool(
|
|
IN OUT PFSB_CPU_POOL_HEADER CpuPool
|
|
)
|
|
{
|
|
PFSB_POOL_HEADER Pool;
|
|
PFSB_PAGE_HEADER Page;
|
|
PLIST_ENTRY Scan;
|
|
PLIST_ENTRY Next;
|
|
LARGE_INTEGER Ticks;
|
|
LARGE_INTEGER TicksDelta;
|
|
|
|
// We must not only be at DISPATCH_LEVEL (or higher), we must also
|
|
// be called on the processor that owns the specified pool.
|
|
//
|
|
ASSERT(KeGetCurrentIrql() >= DISPATCH_LEVEL);
|
|
ASSERT((ULONG)KeGetCurrentProcessorNumber() == CpuPool->OwnerCpu);
|
|
|
|
Pool = PoolFromCpuPool(CpuPool);
|
|
|
|
KeQueryTickCount(&Ticks);
|
|
|
|
// Compute the next tick value which represents the earliest time
|
|
// that we will scavenge this pool again.
|
|
//
|
|
ConvertSecondsToTicks(FSB_SCAVENGE_PERIOD_IN_SECONDS, &TicksDelta);
|
|
CpuPool->NextScavengeTick.QuadPart = Ticks.QuadPart + TicksDelta.QuadPart;
|
|
|
|
// Compute the tick value which represents the last point at which
|
|
// its okay to free a page.
|
|
//
|
|
ConvertSecondsToTicks(FSB_MINIMUM_PAGE_LIFETIME_IN_SECONDS, &TicksDelta);
|
|
Ticks.QuadPart = Ticks.QuadPart - TicksDelta.QuadPart;
|
|
|
|
for (Scan = CpuPool->PageList.Flink;
|
|
Scan != &CpuPool->PageList;
|
|
Scan = Next)
|
|
{
|
|
Page = CONTAINING_RECORD(Scan, FSB_PAGE_HEADER, PageLink);
|
|
ASSERT(Page == PAGE_ALIGN(Page));
|
|
ASSERT(CpuPool == Page->Pool);
|
|
ASSERT(!Page->OnUsedPageList);
|
|
|
|
// Step to the next link before we possibly unlink this page.
|
|
//
|
|
Next = Scan->Flink;
|
|
|
|
if ((Pool->BlocksPerPage == ExQueryDepthSList(&Page->FreeList)) &&
|
|
(Ticks.QuadPart > Page->LastUsedTick.QuadPart))
|
|
{
|
|
RemoveEntryList(Scan);
|
|
|
|
FsbpFreePage(CpuPool, Page);
|
|
}
|
|
}
|
|
|
|
// Scan the used pages to see if they can be moved back to the normal
|
|
// list. This can happen if too many frees by non-owning processors
|
|
// are done. In that case, the pages get orphaned on the used-page
|
|
// list after all of their blocks have been freed to the page. Un-orphan
|
|
// them here.
|
|
//
|
|
for (Scan = CpuPool->UsedPageList.Flink;
|
|
Scan != &CpuPool->UsedPageList;
|
|
Scan = Next)
|
|
{
|
|
Page = CONTAINING_RECORD(Scan, FSB_PAGE_HEADER, PageLink);
|
|
ASSERT(Page == PAGE_ALIGN(Page));
|
|
ASSERT(CpuPool == Page->Pool);
|
|
ASSERT(Page->OnUsedPageList);
|
|
|
|
// Step to the next link before we possibly unlink this page.
|
|
Next = Scan->Flink;
|
|
|
|
if (0 != ExQueryDepthSList(&Page->FreeList))
|
|
{
|
|
RemoveEntryList(Scan);
|
|
Page->OnUsedPageList = FALSE;
|
|
InsertTailList(&CpuPool->PageList, Scan);
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
// Creates a pool of fixed-size blocks built over non-paged pool. Each
|
|
// block is BlockSize bytes long. If NULL is not returned,
|
|
// FsbDestroyPool should be called at a later time to reclaim the
|
|
// resources used by the pool.
|
|
//
|
|
// Arguments:
|
|
// BlockSize - The size, in bytes, of each block.
|
|
// FreeBlockLinkOffset - The offset, in bytes, from the beginning of a block
|
|
// that represenets a pointer-sized storage location that the pool can
|
|
// use to chain free blocks together. Most often this will be zero
|
|
// (meaning use the first pointer-size bytes of the block.)
|
|
// Tag - The pool tag to be used internally for calls to
|
|
// ExAllocatePoolWithTag. This allows callers to track
|
|
// memory consumption for different pools.
|
|
// BuildFunction - An optional pointer to a function which initializes
|
|
// blocks when they are first allocated by the pool. This allows the
|
|
// caller to perform custom, on-demand initialization of each block.
|
|
//
|
|
// Returns the handle used to identify the pool.
|
|
//
|
|
// Caller IRQL: [PASSIVE_LEVEL, DISPATCH_LEVEL]
|
|
//
|
|
HANDLE
|
|
FsbCreatePool(
|
|
IN USHORT BlockSize,
|
|
IN USHORT FreeBlockLinkOffset,
|
|
IN ULONG Tag,
|
|
IN NDIS_BLOCK_INITIALIZER BuildFunction OPTIONAL
|
|
)
|
|
{
|
|
SIZE_T Size;
|
|
PVOID Allocation;
|
|
PFSB_POOL_HEADER Pool = NULL;
|
|
PFSB_CPU_POOL_HEADER CpuPool;
|
|
CCHAR NumberCpus = KeNumberProcessors;
|
|
CCHAR i;
|
|
|
|
// We are going to ensure that all blocks returned by FsbAllocate are
|
|
// properly aligned (4-byte on x86 and 16-byte on 64-bit), but we also
|
|
// need to make sure that users are giving us a free block link offset
|
|
// that is a multiple of the base alignment, to ensure proper alignment
|
|
// for the free block SLIST operations.
|
|
//
|
|
ASSERT(FreeBlockLinkOffset % sizeof(BLOCK_TYPE) == 0);
|
|
|
|
// We need at least a pointer size worth of space to manage free
|
|
// blocks and we don't impose any per-block overhead, so we borrow it
|
|
// from the block itself.
|
|
//
|
|
ASSERT(BlockSize >= FreeBlockLinkOffset + sizeof(BLOCK_TYPE));
|
|
|
|
// This implementation shouldn't be used if we are not going to get more
|
|
// than about 8 blocks per page. Blocks bigger than this should probably
|
|
// be allocated with multiple pages at a time.
|
|
//
|
|
ASSERT(BlockSize < PAGE_SIZE / 8);
|
|
|
|
// Compute the size of our pool header allocation.
|
|
// Add padding to ensure that the pool header can begin on a cache line.
|
|
//
|
|
Size = sizeof(FSB_POOL_HEADER) + (sizeof(FSB_CPU_POOL_HEADER) * NumberCpus)
|
|
+ (APPROX_L2_CACHE_LINE_SIZE - MEMORY_ALLOCATION_ALIGNMENT);
|
|
|
|
// Allocate the pool header.
|
|
//
|
|
Allocation = ExAllocatePoolWithTag(NonPagedPool, Size, ' bsF');
|
|
|
|
if (Allocation)
|
|
{
|
|
ASSERT(POINTER_IS_ALIGNED(Allocation, MEMORY_ALLOCATION_ALIGNMENT));
|
|
RtlZeroMemory(Allocation, Size);
|
|
|
|
Pool = ROUND_UP_POINTER(Allocation, APPROX_L2_CACHE_LINE_SIZE);
|
|
|
|
// Initialize the pool header fields.
|
|
//
|
|
Pool->Tag = Tag;
|
|
Pool->CallerBlockSize = BlockSize;
|
|
Pool->AlignedBlockSize = (USHORT)ALIGN_UP(BlockSize, BLOCK_TYPE);
|
|
Pool->BlocksPerPage = (PAGE_SIZE - sizeof(FSB_PAGE_HEADER))
|
|
/ Pool->AlignedBlockSize;
|
|
Pool->FreeBlockLinkOffset = FreeBlockLinkOffset;
|
|
Pool->BuildFunction = BuildFunction;
|
|
Pool->Allocation = Allocation;
|
|
KeInitializeSpinLock(&Pool->Interlock);
|
|
|
|
// Initialize the per-cpu pool headers.
|
|
//
|
|
CpuPool = (PFSB_CPU_POOL_HEADER)(Pool + 1);
|
|
|
|
for (i = 0; i < NumberCpus; i++)
|
|
{
|
|
InitializeListHead(&CpuPool[i].PageList);
|
|
InitializeListHead(&CpuPool[i].UsedPageList);
|
|
CpuPool[i].OwnerCpu = i;
|
|
}
|
|
}
|
|
|
|
return Pool;
|
|
}
|
|
|
|
// Destroys a pool of fixed-size blocks previously created by a call to
|
|
// FsbCreatePool.
|
|
//
|
|
// Arguments:
|
|
// PoolHandle - Handle which identifies the pool being destroyed.
|
|
//
|
|
// Caller IRQL: [PASSIVE_LEVEL, DISPATCH_LEVEL]
|
|
//
|
|
VOID
|
|
FsbDestroyPool(
|
|
IN HANDLE PoolHandle
|
|
)
|
|
{
|
|
PFSB_POOL_HEADER Pool;
|
|
PFSB_CPU_POOL_HEADER CpuPool;
|
|
CCHAR NumberCpus = KeNumberProcessors;
|
|
CCHAR i;
|
|
|
|
Pool = (PFSB_POOL_HEADER)PoolHandle;
|
|
if (!Pool)
|
|
{
|
|
return;
|
|
}
|
|
|
|
for (i = 0, CpuPool = (PFSB_CPU_POOL_HEADER)(Pool + 1);
|
|
i < NumberCpus;
|
|
i++, CpuPool++)
|
|
{
|
|
ASSERT(CpuPool->OwnerCpu == (ULONG)i);
|
|
|
|
FsbpFreeList(CpuPool, &CpuPool->PageList);
|
|
FsbpFreeList(CpuPool, &CpuPool->UsedPageList);
|
|
|
|
ASSERT(CpuPool->TotalPagesAllocated == CpuPool->TotalPagesFreed);
|
|
ASSERT(CpuPool->TotalBlocksAllocated == CpuPool->TotalBlocksFreed);
|
|
}
|
|
|
|
ASSERT(Pool ==
|
|
ROUND_UP_POINTER(Pool->Allocation, APPROX_L2_CACHE_LINE_SIZE));
|
|
ExFreePool(Pool->Allocation);
|
|
}
|
|
|
|
// Returns a pointer to a block allocated from a pool. NULL is returned if
|
|
// the request could not be granted. The returned pointer is guaranteed to
|
|
// have 8 byte alignment.
|
|
//
|
|
// Arguments:
|
|
// PoolHandle - Handle which identifies the pool being allocated from.
|
|
//
|
|
// Caller IRQL: [PASSIVE_LEVEL, DISPATCH_LEVEL]
|
|
//
|
|
PUCHAR
|
|
FsbAllocate(
|
|
IN HANDLE PoolHandle
|
|
)
|
|
{
|
|
PFSB_POOL_HEADER Pool;
|
|
PFSB_CPU_POOL_HEADER CpuPool;
|
|
PFSB_PAGE_HEADER Page;
|
|
PSLIST_ENTRY BlockLink;
|
|
PUCHAR Block = NULL;
|
|
KIRQL OldIrql;
|
|
ULONG Cpu;
|
|
LARGE_INTEGER Ticks;
|
|
|
|
ASSERT(PoolHandle);
|
|
|
|
Pool = (PFSB_POOL_HEADER)PoolHandle;
|
|
|
|
// Raise IRQL before saving the processor number since there is chance
|
|
// it could have changed if we saved it while at passive.
|
|
//
|
|
OldIrql = KeRaiseIrqlToDpcLevel();
|
|
|
|
Cpu = KeGetCurrentProcessorNumber();
|
|
CpuPool = (PFSB_CPU_POOL_HEADER)(Pool + 1) + Cpu;
|
|
|
|
// See if the minimum time has passed since we last scavenged
|
|
// the pool. If it has, we'll scavenge again. Normally, scavenging
|
|
// should only be performed when we free. However, for the case when
|
|
// the caller constantly frees on a non-owning processor, we'll
|
|
// take this chance to do the scavenging.
|
|
//
|
|
KeQueryTickCount(&Ticks);
|
|
if (Ticks.QuadPart > CpuPool->NextScavengeTick.QuadPart)
|
|
{
|
|
FsbpScavengePool(CpuPool);
|
|
}
|
|
|
|
if (!IsListEmpty(&CpuPool->PageList))
|
|
{
|
|
Page = CONTAINING_RECORD(CpuPool->PageList.Flink, FSB_PAGE_HEADER, PageLink);
|
|
ASSERT(Page == PAGE_ALIGN(Page));
|
|
ASSERT(CpuPool == Page->Pool);
|
|
ASSERT(!Page->OnUsedPageList);
|
|
|
|
BlockLink = ExInterlockedPopEntrySList(&Page->FreeList, &Pool->Interlock);
|
|
if (BlockLink)
|
|
{
|
|
Block = (PUCHAR)BlockLink - Pool->FreeBlockLinkOffset;
|
|
}
|
|
else
|
|
{
|
|
// If there were no blocks on this page's free list, it had better
|
|
// mean we haven't yet built all of the blocks on the page.
|
|
// (Otherwise, what is a fully used page doing on the page list
|
|
// and not on the used-page list?)
|
|
//
|
|
ASSERT(Page->BlocksBuilt < Pool->BlocksPerPage);
|
|
|
|
Block = FsbpBuildNextBlock(Pool, Page);
|
|
ASSERT(Block);
|
|
}
|
|
|
|
// Got a block. Now check to see if it was the last one on a fully
|
|
// built page. If so, move the page to the used-page list.
|
|
//
|
|
if ((0 == ExQueryDepthSList(&Page->FreeList)) &&
|
|
(Page->BlocksBuilt == Pool->BlocksPerPage))
|
|
{
|
|
PLIST_ENTRY PageLink;
|
|
PageLink = RemoveHeadList(&CpuPool->PageList);
|
|
InsertTailList(&CpuPool->UsedPageList, PageLink);
|
|
Page->OnUsedPageList = TRUE;
|
|
|
|
ASSERT(Page == CONTAINING_RECORD(PageLink, FSB_PAGE_HEADER, PageLink));
|
|
}
|
|
|
|
ASSERT(Block);
|
|
goto GotABlock;
|
|
}
|
|
else
|
|
{
|
|
// The page list is empty so we have to allocate and add a new page.
|
|
//
|
|
Block = FsbpAllocateNewPageAndBuildOneBlock(Pool, CpuPool);
|
|
}
|
|
|
|
// If we are returning an block, update the statistics.
|
|
//
|
|
if (Block)
|
|
{
|
|
ULONG BlocksInUse;
|
|
GotABlock:
|
|
|
|
CpuPool->TotalBlocksAllocated++;
|
|
|
|
BlocksInUse = CpuPool->TotalBlocksAllocated - CpuPool->TotalBlocksFreed;
|
|
if (BlocksInUse > CpuPool->PeakBlocksInUse)
|
|
{
|
|
CpuPool->PeakBlocksInUse = BlocksInUse;
|
|
}
|
|
|
|
// Don't give anyone ideas about where this might point. I don't
|
|
// want anyone trashing my pool because they thought this field
|
|
// was valid for some reason.
|
|
//
|
|
((PSINGLE_LIST_ENTRY)((PUCHAR)Block + Pool->FreeBlockLinkOffset))->Next = NULL;
|
|
}
|
|
|
|
KeLowerIrql(OldIrql);
|
|
|
|
return Block;
|
|
}
|
|
|
|
// Free a block back to the pool from which it was allocated.
|
|
//
|
|
// Arguments:
|
|
// Block - A block returned from a prior call to FsbAllocate.
|
|
//
|
|
// Caller IRQL: [PASSIVE_LEVEL, DISPATCH_LEVEL]
|
|
//
|
|
VOID
|
|
FsbFree(
|
|
IN PUCHAR Block
|
|
)
|
|
{
|
|
PFSB_PAGE_HEADER Page;
|
|
PFSB_CPU_POOL_HEADER CpuPool;
|
|
PFSB_POOL_HEADER Pool;
|
|
LARGE_INTEGER Ticks;
|
|
LOGICAL PageIsOnUsedPageList;
|
|
LOGICAL Scavenge = FALSE;
|
|
|
|
ASSERT(Block);
|
|
|
|
// Get the address of the page that this block lives on. This is where
|
|
// our page header is stored.
|
|
//
|
|
Page = PAGE_ALIGN(Block);
|
|
|
|
// Follow the back pointer in the page header to locate the owning
|
|
// cpu's pool.
|
|
//
|
|
CpuPool = Page->Pool;
|
|
|
|
// Locate the pool header.
|
|
//
|
|
Pool = PoolFromCpuPool(CpuPool);
|
|
|
|
// See if the minimum time has passed since we last scavenged
|
|
// the pool. If it has, we'll scavenge again.
|
|
//
|
|
KeQueryTickCount(&Ticks);
|
|
if (Ticks.QuadPart > CpuPool->NextScavengeTick.QuadPart)
|
|
{
|
|
Scavenge = TRUE;
|
|
}
|
|
|
|
// Note the tick that this page was last used. If this is the last block
|
|
// to be returned to this page, this sets the minimum time that this page
|
|
// will continue to live unless it gets re-used.
|
|
//
|
|
Page->LastUsedTick.QuadPart = Ticks.QuadPart;
|
|
|
|
// If this page is on the used-page list, we'll put it back on the normal
|
|
// page list (only after pushing the block back on the page's free list)
|
|
// if, after raising IRQL, we are on the processor that owns this
|
|
// pool.
|
|
//
|
|
PageIsOnUsedPageList = Page->OnUsedPageList;
|
|
|
|
|
|
InterlockedIncrement((PLONG)&CpuPool->TotalBlocksFreed);
|
|
|
|
// Now return the block to the page's free list.
|
|
//
|
|
ExInterlockedPushEntrySList(
|
|
&Page->FreeList,
|
|
(PSLIST_ENTRY)((PUCHAR)Block + Pool->FreeBlockLinkOffset),
|
|
&Pool->Interlock);
|
|
|
|
//
|
|
// Warning: Now that the block is back on the page, one cannot *reliably*
|
|
// dereference anything through 'Page' anymore. It may have just been
|
|
// scavenged by its owning processor and subsequently freed. This is a
|
|
// particularly rare condition given that MINIMUM_PAGE_LIFETIME_IN_SECONDS
|
|
// is 20s, so we choose to live with it. The alternative would be to walk
|
|
// the UsedPageList whenever PageIsOnUsedPageList is true, making the
|
|
// FsbFree operation potentially expensive. We saved off the value of
|
|
// Page->OnUsedPageList before returning the block so we would not risk
|
|
// touching Page to get this value only to find that it was false.
|
|
//
|
|
|
|
// If we need to move the page from the used-page list to the normal
|
|
// page list, or if we need to scavenge, we need to be at DISPATCH_LEVEL
|
|
// and be executing on the processor that owns this pool.
|
|
// Find out if the CPU we are executing on right now owns this pool.
|
|
// Note that if we are running at PASSIVE_LEVEL, the current CPU may
|
|
// change over the duration of this function call, so this value is
|
|
// not absolute over the life of the function.
|
|
//
|
|
if ((PageIsOnUsedPageList || Scavenge) &&
|
|
((ULONG)KeGetCurrentProcessorNumber() == CpuPool->OwnerCpu))
|
|
{
|
|
KIRQL OldIrql;
|
|
|
|
OldIrql = KeRaiseIrqlToDpcLevel();
|
|
|
|
// Now that we are at DISPATCH_LEVEL, perform the work if we are still
|
|
// executing on the processor that owns the pool.
|
|
//
|
|
if ((ULONG)KeGetCurrentProcessorNumber() == CpuPool->OwnerCpu)
|
|
{
|
|
// If the page is still on the used-page list (meaning another
|
|
// FsbFree didn't just sneak by) and still has a free block (for
|
|
// instance, an FsbAllocate might sneak in on its owning processor,
|
|
// scavenge the page, and allocate the block we just freed; thereby
|
|
// putting it back on the used-page list), then put the page on the
|
|
// normal list. Very important to do this after (not before)
|
|
// returning the block to the free list because FsbAllocate expects
|
|
// blocks to be available from pages on the page list.
|
|
//
|
|
if (PageIsOnUsedPageList &&
|
|
Page->OnUsedPageList &&
|
|
(0 != ExQueryDepthSList(&Page->FreeList)))
|
|
{
|
|
RemoveEntryList(&Page->PageLink);
|
|
Page->OnUsedPageList = FALSE;
|
|
InsertTailList(&CpuPool->PageList, &Page->PageLink);
|
|
}
|
|
|
|
// Perform the scavenge if we previously noted we needed to do so.
|
|
//
|
|
if (Scavenge)
|
|
{
|
|
FsbpScavengePool(CpuPool);
|
|
}
|
|
}
|
|
|
|
KeLowerIrql(OldIrql);
|
|
}
|
|
}
|
|
|