-/* $Id: npool.c,v 1.73 2003/07/29 19:43:13 royce Exp $
+/* $Id$
*
- * COPYRIGHT: See COPYING in the top level directory
- * PROJECT: ReactOS kernel
- * FILE: ntoskrnl/mm/npool.c
- * PURPOSE: Implements the kernel memory pool
- * PROGRAMMER: David Welch (welch@cwcom.net)
- * UPDATE HISTORY:
- * 27/05/98: Created
- * 10/06/98: Bug fixes by Iwan Fatahi (i_fatahi@hotmail.com)
- * in take_block (if current bigger than required)
- * in remove_from_used_list
- * in ExFreePool
- * 23/08/98: Fixes from Robert Bergkvist (fragdance@hotmail.com)
+ * COPYRIGHT: See COPYING in the top level directory
+ * PROJECT: ReactOS kernel
+ * FILE: ntoskrnl/mm/npool.c
+ * PURPOSE: Implements the kernel memory pool
+ *
+ * PROGRAMMERS: David Welch (welch@cwcom.net)
+ * Iwan Fatahi (i_fatahi@hotmail.com)
+ * Robert Bergkvist (fragdance@hotmail.com)
+ * Hartmut Birr
*/
/* INCLUDES ****************************************************************/
-#include <ddk/ntddk.h>
-#include <internal/mm.h>
-#include <internal/ntoskrnl.h>
-#include <internal/pool.h>
-
+#include <ntoskrnl.h>
#define NDEBUG
#include <internal/debug.h>
-/* Enable strict checking of the nonpaged pool on every allocation */
-//#define ENABLE_VALIDATE_POOL
-
-/* Enable tracking of statistics about the tagged blocks in the pool */
-#define TAG_STATISTICS_TRACKING
-
-/*
- * Put each block in its own range of pages and position the block at the
- * end of the range so any accesses beyond the end of block are to invalid
- * memory locations.
- */
-//#define WHOLE_PAGE_ALLOCATIONS
-
#ifdef ENABLE_VALIDATE_POOL
#define VALIDATE_POOL validate_kernel_pool()
#else
#if 0
#define POOL_TRACE(args...) do { DbgPrint(args); } while(0);
#else
+#if defined(__GNUC__)
#define POOL_TRACE(args...)
+#else
+#define POOL_TRACE
+#endif /* __GNUC__ */
#endif
/* avl types ****************************************************************/
typedef struct _NODE
{
- struct _NODE* link[2];
- struct _NODE* parent;
- signed char balance;
-} NODE, *PNODE;
+ struct _NODE* link[2];
+ struct _NODE* parent;
+ signed char balance;
+}
+NODE, *PNODE;
/* TYPES *******************************************************************/
/*
* fields present at the start of a block (this is for internal use only)
*/
-typedef struct _BLOCK_HDR
+typedef struct _HDR
{
- ULONG Magic;
- ULONG Size;
- LIST_ENTRY ListEntry;
- LIST_ENTRY AddressList;
- LIST_ENTRY TagListEntry;
- NODE Node;
- ULONG Tag;
- PVOID Caller;
- BOOLEAN Dumped;
-} BLOCK_HDR;
-
-PVOID STDCALL
-ExAllocateWholePageBlock(ULONG Size);
-VOID STDCALL
-ExFreeWholePageBlock(PVOID Addr);
+ ULONG Magic;
+ ULONG Size;
+ struct _HDR* previous;
+} HDR, *PHDR;
+
+typedef struct _HDR_USED
+{
+ HDR hdr;
+ LIST_ENTRY ListEntry;
+ ULONG Tag;
+ PVOID Caller;
+ LIST_ENTRY TagListEntry;
+ BOOLEAN Dumped;
+} HDR_USED, *PHDR_USED;
+
+typedef struct _HDR_FREE
+{
+ HDR hdr;
+ NODE Node;
+} HDR_FREE, *PHDR_FREE;
+
+#define HDR_FREE_SIZE ROUND_UP(sizeof(HDR_FREE), MM_POOL_ALIGNMENT)
+#define HDR_USED_SIZE ROUND_UP(sizeof(HDR_USED), MM_POOL_ALIGNMENT)
+
/* GLOBALS *****************************************************************/
extern PVOID MiNonPagedPoolStart;
extern ULONG MiNonPagedPoolLength;
-static ULONG MiCurrentNonPagedPoolLength = 0;
/*
* Head of the list of free blocks
static LIST_ENTRY AddressListHead;
-#ifndef WHOLE_PAGE_ALLOCATIONS
/*
* Count of free blocks
*/
* Count of used blocks
*/
static ULONG EiNrUsedBlocks = 0;
-#endif
/*
* Lock that protects the non-paged pool data structures
*/
ULONG EiUsedNonPagedPool = 0;
+/* Total quota for Non Paged Pool */
+ULONG MmTotalNonPagedPoolQuota = 0;
+
/*
* Allocate a range of memory in the nonpaged pool
*/
static LIST_ENTRY tag_hash_table[TAG_HASH_TABLE_SIZE];
#endif /* TAG_STATISTICS_TRACKING */
+static PULONG MiNonPagedPoolAllocMap;
+static ULONG MiNonPagedPoolNrOfPages;
+
/* avl helper functions ****************************************************/
void DumpFreeBlockNode(PNODE p)
{
- static int count = 0;
- BLOCK_HDR* blk;
+ static int count = 0;
+ HDR_FREE* blk;
- count++;
+ count++;
- if (p)
- {
+ if (p)
+ {
DumpFreeBlockNode(p->link[0]);
- blk = CONTAINING_RECORD(p, BLOCK_HDR, Node);
- DbgPrint("%08x %8d (%d)\n", blk, blk->Size, count);
+ blk = CONTAINING_RECORD(p, HDR_FREE, Node);
+ DbgPrint("%08x %8d (%d)\n", blk, blk->hdr.Size, count);
DumpFreeBlockNode(p->link[1]);
- }
+ }
- count--;
+ count--;
}
void DumpFreeBlockTree(void)
{
- DbgPrint("--- Begin tree ------------------\n");
- DbgPrint("%08x\n", CONTAINING_RECORD(FreeBlockListRoot, BLOCK_HDR, Node));
- DumpFreeBlockNode(FreeBlockListRoot);
- DbgPrint("--- End tree --------------------\n");
+ DbgPrint("--- Begin tree ------------------\n");
+ DbgPrint("%08x\n", CONTAINING_RECORD(FreeBlockListRoot, HDR_FREE, Node));
+ DumpFreeBlockNode(FreeBlockListRoot);
+ DbgPrint("--- End tree --------------------\n");
}
int compare_node(PNODE p1, PNODE p2)
{
- BLOCK_HDR* blk1 = CONTAINING_RECORD(p1, BLOCK_HDR, Node);
- BLOCK_HDR* blk2 = CONTAINING_RECORD(p2, BLOCK_HDR, Node);
+ HDR_FREE* blk1 = CONTAINING_RECORD(p1, HDR_FREE, Node);
+ HDR_FREE* blk2 = CONTAINING_RECORD(p2, HDR_FREE, Node);
- if (blk1->Size == blk2->Size)
- {
+ if (blk1->hdr.Size == blk2->hdr.Size)
+ {
if (blk1 < blk2)
- {
- return -1;
- }
+ {
+ return -1;
+ }
if (blk1 > blk2)
- {
- return 1;
- }
- }
- else
- {
- if (blk1->Size < blk2->Size)
- {
- return -1;
- }
- if (blk1->Size > blk2->Size)
- {
- return 1;
- }
- }
- return 0;
+ {
+ return 1;
+ }
+ }
+ else
+ {
+ if (blk1->hdr.Size < blk2->hdr.Size)
+ {
+ return -1;
+ }
+ if (blk1->hdr.Size > blk2->hdr.Size)
+ {
+ return 1;
+ }
+ }
+ return 0;
}
int compare_value(PVOID value, PNODE p)
{
- BLOCK_HDR* blk = CONTAINING_RECORD(p, BLOCK_HDR, Node);
- ULONG v = *(PULONG)value;
+ HDR_FREE* blk = CONTAINING_RECORD(p, HDR_FREE, Node);
+ ULONG v = *(PULONG)value;
- if (v < blk->Size)
- {
+ if (v < blk->hdr.Size)
+ {
return -1;
- }
- if (v > blk->Size)
- {
+ }
+ if (v > blk->hdr.Size)
+ {
return 1;
- }
- return 0;
+ }
+ return 0;
}
/* avl functions **********************************************************/
void avl_insert (PNODE * root, PNODE n, int (*compare)(PNODE, PNODE))
{
- PNODE y; /* Top node to update balance factor, and parent. */
- PNODE p, q; /* Iterator, and parent. */
- PNODE w; /* New root of rebalanced subtree. */
- int dir; /* Direction to descend. */
+ PNODE y; /* Top node to update balance factor, and parent. */
+ PNODE p, q; /* Iterator, and parent. */
+ PNODE w; /* New root of rebalanced subtree. */
+ int dir = 0; /* Direction to descend. */
- n->link[0] = n->link[1] = n->parent = NULL;
- n->balance = 0;
+ n->link[0] = n->link[1] = n->parent = NULL;
+ n->balance = 0;
- y = *root;
- for (q = NULL, p = *root; p != NULL; q = p, p = p->link[dir])
- {
+ y = *root;
+ for (q = NULL, p = *root; p != NULL; q = p, p = p->link[dir])
+ {
dir = compare(n, p) > 0;
if (p->balance != 0)
- {
- y = p;
- }
- }
-
- n->parent = q;
- if (q != NULL)
- {
+ {
+ y = p;
+ }
+ }
+
+ n->parent = q;
+ if (q != NULL)
+ {
q->link[dir] = n;
- }
- else
- {
+ }
+ else
+ {
*root = n;
- }
+ }
- if (*root == n)
- {
+ if (*root == n)
+ {
return;
- }
+ }
- for (p = n; p != y; p = q)
- {
+ for (p = n; p != y; p = q)
+ {
q = p->parent;
dir = q->link[0] != p;
if (dir == 0)
- {
- q->balance--;
- }
+ {
+ q->balance--;
+ }
else
- {
- q->balance++;
- }
- }
+ {
+ q->balance++;
+ }
+ }
- if (y->balance == -2)
- {
+ if (y->balance == -2)
+ {
PNODE x = y->link[0];
if (x->balance == -1)
- {
- w = x;
- y->link[0] = x->link[1];
- x->link[1] = y;
- x->balance = y->balance = 0;
- x->parent = y->parent;
- y->parent = x;
- if (y->link[0] != NULL)
- {
- y->link[0]->parent = y;
- }
- }
+ {
+ w = x;
+ y->link[0] = x->link[1];
+ x->link[1] = y;
+ x->balance = y->balance = 0;
+ x->parent = y->parent;
+ y->parent = x;
+ if (y->link[0] != NULL)
+ {
+ y->link[0]->parent = y;
+ }
+ }
else
- {
- assert (x->balance == +1);
- w = x->link[1];
- x->link[1] = w->link[0];
- w->link[0] = x;
- y->link[0] = w->link[1];
- w->link[1] = y;
- if (w->balance == -1)
- {
- x->balance = 0;
- y->balance = +1;
- }
- else if (w->balance == 0)
- {
- x->balance = y->balance = 0;
- }
- else /* |w->pavl_balance == +1| */
- {
- x->balance = -1;
- y->balance = 0;
- }
- w->balance = 0;
- w->parent = y->parent;
- x->parent = y->parent = w;
- if (x->link[1] != NULL)
- {
- x->link[1]->parent = x;
- }
- if (y->link[0] != NULL)
- {
- y->link[0]->parent = y;
- }
- }
- }
- else if (y->balance == +2)
- {
+ {
+ ASSERT(x->balance == +1);
+ w = x->link[1];
+ x->link[1] = w->link[0];
+ w->link[0] = x;
+ y->link[0] = w->link[1];
+ w->link[1] = y;
+ if (w->balance == -1)
+ {
+ x->balance = 0;
+ y->balance = +1;
+ }
+ else if (w->balance == 0)
+ {
+ x->balance = y->balance = 0;
+ }
+ else /* |w->pavl_balance == +1| */
+ {
+ x->balance = -1;
+ y->balance = 0;
+ }
+ w->balance = 0;
+ w->parent = y->parent;
+ x->parent = y->parent = w;
+ if (x->link[1] != NULL)
+ {
+ x->link[1]->parent = x;
+ }
+ if (y->link[0] != NULL)
+ {
+ y->link[0]->parent = y;
+ }
+ }
+ }
+ else if (y->balance == +2)
+ {
PNODE x = y->link[1];
if (x->balance == +1)
- {
- w = x;
- y->link[1] = x->link[0];
- x->link[0] = y;
- x->balance = y->balance = 0;
- x->parent = y->parent;
- y->parent = x;
- if (y->link[1] != NULL)
- {
- y->link[1]->parent = y;
- }
- }
+ {
+ w = x;
+ y->link[1] = x->link[0];
+ x->link[0] = y;
+ x->balance = y->balance = 0;
+ x->parent = y->parent;
+ y->parent = x;
+ if (y->link[1] != NULL)
+ {
+ y->link[1]->parent = y;
+ }
+ }
else
- {
- assert (x->balance == -1);
- w = x->link[0];
- x->link[0] = w->link[1];
- w->link[1] = x;
- y->link[1] = w->link[0];
- w->link[0] = y;
- if (w->balance == 1)
- {
- x->balance = 0;
- y->balance = -1;
- }
- else if (w->balance == 0)
- {
- x->balance = y->balance = 0;
- }
- else /* |w->pavl_balance == -1| */
- {
- x->balance = +1;
- y->balance = 0;
- }
- w->balance = 0;
- w->parent = y->parent;
- x->parent = y->parent = w;
- if (x->link[0] != NULL)
- {
- x->link[0]->parent = x;
- }
- if (y->link[1] != NULL)
- {
- y->link[1]->parent = y;
- }
- }
- }
- else
- {
+ {
+ ASSERT(x->balance == -1);
+ w = x->link[0];
+ x->link[0] = w->link[1];
+ w->link[1] = x;
+ y->link[1] = w->link[0];
+ w->link[0] = y;
+ if (w->balance == 1)
+ {
+ x->balance = 0;
+ y->balance = -1;
+ }
+ else if (w->balance == 0)
+ {
+ x->balance = y->balance = 0;
+ }
+ else /* |w->pavl_balance == -1| */
+ {
+ x->balance = +1;
+ y->balance = 0;
+ }
+ w->balance = 0;
+ w->parent = y->parent;
+ x->parent = y->parent = w;
+ if (x->link[0] != NULL)
+ {
+ x->link[0]->parent = x;
+ }
+ if (y->link[1] != NULL)
+ {
+ y->link[1]->parent = y;
+ }
+ }
+ }
+ else
+ {
return;
- }
- if (w->parent != NULL)
- {
+ }
+ if (w->parent != NULL)
+ {
w->parent->link[y != w->parent->link[0]] = w;
- }
- else
- {
+ }
+ else
+ {
*root = w;
- }
+ }
- return;
+ return;
}
void avl_remove (PNODE *root, PNODE item, int (*compare)(PNODE, PNODE))
{
- PNODE p; /* Traverses tree to find node to delete. */
- PNODE q; /* Parent of |p|. */
- int dir; /* Side of |q| on which |p| is linked. */
+ PNODE p; /* Traverses tree to find node to delete. */
+ PNODE q; /* Parent of |p|. */
+ int dir; /* Side of |q| on which |p| is linked. */
- if (root == NULL || *root == NULL)
- {
+ if (root == NULL || *root == NULL)
+ {
return ;
- }
+ }
- p = item;
- q = p->parent;
- if (q == NULL)
- {
+ p = item;
+ q = p->parent;
+ if (q == NULL)
+ {
q = (PNODE) root;
dir = 0;
- }
- else
- {
+ }
+ else
+ {
dir = compare(p, q) > 0;
- }
+ }
- if (p->link[1] == NULL)
- {
+ if (p->link[1] == NULL)
+ {
q->link[dir] = p->link[0];
if (q->link[dir] != NULL)
- {
- q->link[dir]->parent = p->parent;
- }
- }
- else
- {
+ {
+ q->link[dir]->parent = p->parent;
+ }
+ }
+ else
+ {
PNODE r = p->link[1];
if (r->link[0] == NULL)
- {
- r->link[0] = p->link[0];
- q->link[dir] = r;
- r->parent = p->parent;
- if (r->link[0] != NULL)
- {
- r->link[0]->parent = r;
- }
- r->balance = p->balance;
- q = r;
- dir = 1;
- }
+ {
+ r->link[0] = p->link[0];
+ q->link[dir] = r;
+ r->parent = p->parent;
+ if (r->link[0] != NULL)
+ {
+ r->link[0]->parent = r;
+ }
+ r->balance = p->balance;
+ q = r;
+ dir = 1;
+ }
else
- {
- PNODE s = r->link[0];
- while (s->link[0] != NULL)
- {
- s = s->link[0];
- }
- r = s->parent;
- r->link[0] = s->link[1];
- s->link[0] = p->link[0];
- s->link[1] = p->link[1];
- q->link[dir] = s;
- if (s->link[0] != NULL)
- {
- s->link[0]->parent = s;
- }
- s->link[1]->parent = s;
- s->parent = p->parent;
- if (r->link[0] != NULL)
- {
- r->link[0]->parent = r;
- }
- s->balance = p->balance;
- q = r;
- dir = 0;
- }
- }
+ {
+ PNODE s = r->link[0];
+ while (s->link[0] != NULL)
+ {
+ s = s->link[0];
+ }
+ r = s->parent;
+ r->link[0] = s->link[1];
+ s->link[0] = p->link[0];
+ s->link[1] = p->link[1];
+ q->link[dir] = s;
+ if (s->link[0] != NULL)
+ {
+ s->link[0]->parent = s;
+ }
+ s->link[1]->parent = s;
+ s->parent = p->parent;
+ if (r->link[0] != NULL)
+ {
+ r->link[0]->parent = r;
+ }
+ s->balance = p->balance;
+ q = r;
+ dir = 0;
+ }
+ }
- item->link[0] = item->link[1] = item->parent = NULL;
- item->balance = 0;
+ item->link[0] = item->link[1] = item->parent = NULL;
+ item->balance = 0;
- while (q != (PNODE) root)
- {
+ while (q != (PNODE) root)
+ {
PNODE y = q;
if (y->parent != NULL)
- {
- q = y->parent;
- }
+ {
+ q = y->parent;
+ }
else
- {
- q = (PNODE) root;
- }
+ {
+ q = (PNODE) root;
+ }
if (dir == 0)
- {
- dir = q->link[0] != y;
- y->balance++;
- if (y->balance == +1)
- {
- break;
- }
- else if (y->balance == +2)
+ {
+ dir = q->link[0] != y;
+ y->balance++;
+ if (y->balance == +1)
+ {
+ break;
+ }
+ else if (y->balance == +2)
+ {
+ PNODE x = y->link[1];
+ if (x->balance == -1)
+ {
+ PNODE w;
+
+ ASSERT(x->balance == -1);
+ w = x->link[0];
+ x->link[0] = w->link[1];
+ w->link[1] = x;
+ y->link[1] = w->link[0];
+ w->link[0] = y;
+ if (w->balance == +1)
+ {
+ x->balance = 0;
+ y->balance = -1;
+ }
+ else if (w->balance == 0)
+ {
+ x->balance = y->balance = 0;
+ }
+ else /* |w->pavl_balance == -1| */
+ {
+ x->balance = +1;
+ y->balance = 0;
+ }
+ w->balance = 0;
+ w->parent = y->parent;
+ x->parent = y->parent = w;
+ if (x->link[0] != NULL)
+ {
+ x->link[0]->parent = x;
+ }
+ if (y->link[1] != NULL)
+ {
+ y->link[1]->parent = y;
+ }
+ q->link[dir] = w;
+ }
+ else
{
- PNODE x = y->link[1];
- if (x->balance == -1)
- {
- PNODE w;
-
- assert (x->balance == -1);
- w = x->link[0];
- x->link[0] = w->link[1];
- w->link[1] = x;
- y->link[1] = w->link[0];
- w->link[0] = y;
- if (w->balance == +1)
- {
- x->balance = 0;
- y->balance = -1;
- }
- else if (w->balance == 0)
- {
- x->balance = y->balance = 0;
- }
- else /* |w->pavl_balance == -1| */
- {
- x->balance = +1;
- y->balance = 0;
- }
- w->balance = 0;
- w->parent = y->parent;
- x->parent = y->parent = w;
- if (x->link[0] != NULL)
- {
- x->link[0]->parent = x;
- }
- if (y->link[1] != NULL)
- {
- y->link[1]->parent = y;
- }
- q->link[dir] = w;
- }
- else
- {
- y->link[1] = x->link[0];
- x->link[0] = y;
- x->parent = y->parent;
- y->parent = x;
- if (y->link[1] != NULL)
- {
- y->link[1]->parent = y;
- }
- q->link[dir] = x;
- if (x->balance == 0)
- {
- x->balance = -1;
- y->balance = +1;
- break;
- }
- else
- {
- x->balance = y->balance = 0;
- y = x;
- }
- }
+ y->link[1] = x->link[0];
+ x->link[0] = y;
+ x->parent = y->parent;
+ y->parent = x;
+ if (y->link[1] != NULL)
+ {
+ y->link[1]->parent = y;
+ }
+ q->link[dir] = x;
+ if (x->balance == 0)
+ {
+ x->balance = -1;
+ y->balance = +1;
+ break;
+ }
+ else
+ {
+ x->balance = y->balance = 0;
+ y = x;
+ }
}
- }
+ }
+ }
else
- {
- dir = q->link[0] != y;
- y->balance--;
- if (y->balance == -1)
- {
- break;
- }
- else if (y->balance == -2)
+ {
+ dir = q->link[0] != y;
+ y->balance--;
+ if (y->balance == -1)
+ {
+ break;
+ }
+ else if (y->balance == -2)
+ {
+ PNODE x = y->link[0];
+ if (x->balance == +1)
+ {
+ PNODE w;
+ ASSERT(x->balance == +1);
+ w = x->link[1];
+ x->link[1] = w->link[0];
+ w->link[0] = x;
+ y->link[0] = w->link[1];
+ w->link[1] = y;
+ if (w->balance == -1)
+ {
+ x->balance = 0;
+ y->balance = +1;
+ }
+ else if (w->balance == 0)
+ {
+ x->balance = y->balance = 0;
+ }
+ else /* |w->pavl_balance == +1| */
+ {
+ x->balance = -1;
+ y->balance = 0;
+ }
+ w->balance = 0;
+ w->parent = y->parent;
+ x->parent = y->parent = w;
+ if (x->link[1] != NULL)
+ {
+ x->link[1]->parent = x;
+ }
+ if (y->link[0] != NULL)
+ {
+ y->link[0]->parent = y;
+ }
+ q->link[dir] = w;
+ }
+ else
{
- PNODE x = y->link[0];
- if (x->balance == +1)
- {
- PNODE w;
- assert (x->balance == +1);
- w = x->link[1];
- x->link[1] = w->link[0];
- w->link[0] = x;
- y->link[0] = w->link[1];
- w->link[1] = y;
- if (w->balance == -1)
- {
- x->balance = 0;
- y->balance = +1;
- }
- else if (w->balance == 0)
- {
- x->balance = y->balance = 0;
- }
- else /* |w->pavl_balance == +1| */
- {
- x->balance = -1;
- y->balance = 0;
- }
- w->balance = 0;
- w->parent = y->parent;
- x->parent = y->parent = w;
- if (x->link[1] != NULL)
- {
- x->link[1]->parent = x;
- }
- if (y->link[0] != NULL)
- {
- y->link[0]->parent = y;
- }
- q->link[dir] = w;
- }
- else
- {
- y->link[0] = x->link[1];
- x->link[1] = y;
- x->parent = y->parent;
- y->parent = x;
- if (y->link[0] != NULL)
- {
- y->link[0]->parent = y;
- }
- q->link[dir] = x;
- if (x->balance == 0)
- {
- x->balance = +1;
- y->balance = -1;
- break;
- }
- else
- {
- x->balance = y->balance = 0;
- y = x;
- }
- }
+ y->link[0] = x->link[1];
+ x->link[1] = y;
+ x->parent = y->parent;
+ y->parent = x;
+ if (y->link[0] != NULL)
+ {
+ y->link[0]->parent = y;
+ }
+ q->link[dir] = x;
+ if (x->balance == 0)
+ {
+ x->balance = +1;
+ y->balance = -1;
+ break;
+ }
+ else
+ {
+ x->balance = y->balance = 0;
+ y = x;
+ }
}
- }
- }
+ }
+ }
+ }
+
+}
+PNODE _cdecl avl_get_first(PNODE root)
+{
+ PNODE p;
+ if (root == NULL)
+ {
+ return NULL;
+ }
+ p = root;
+ while (p->link[0])
+ {
+ p = p->link[0];
+ }
+ return p;
}
PNODE avl_get_next(PNODE root, PNODE p)
{
- PNODE q;
- if (p->link[1])
- {
+ PNODE q;
+ if (p->link[1])
+ {
p = p->link[1];
while(p->link[0])
- {
- p = p->link[0];
- }
+ {
+ p = p->link[0];
+ }
return p;
- }
- else
- {
+ }
+ else
+ {
q = p->parent;
while (q && q->link[1] == p)
- {
- p = q;
- q = q->parent;
- }
+ {
+ p = q;
+ q = q->parent;
+ }
if (q == NULL)
- {
- return NULL;
- }
+ {
+ return NULL;
+ }
else
- {
- return q;
- }
- }
+ {
+ return q;
+ }
+ }
}
PNODE avl_find_equal_or_greater(PNODE root, ULONG size, int (compare)(PVOID, PNODE))
{
- PNODE p;
- PNODE prev = NULL;
- int cmp;
+ PNODE p;
+ PNODE prev = NULL;
+ int cmp;
- for (p = root; p != NULL;)
- {
+ for (p = root; p != NULL;)
+ {
cmp = compare((PVOID)&size, p);
if (cmp < 0)
- {
- prev = p;
- p = p->link[0];
- }
+ {
+ prev = p;
+ p = p->link[0];
+ }
else if (cmp > 0)
- {
- p = p->link[1];
- }
+ {
+ p = p->link[1];
+ }
else
- {
- while (p->link[0])
- {
- cmp = compare((PVOID)&size, p->link[0]);
- if (cmp != 0)
- {
- break;
- }
- p = p->link[0];
- }
- return p;
- }
- }
- return prev;
+ {
+ while (p->link[0])
+ {
+ cmp = compare((PVOID)&size, p->link[0]);
+ if (cmp != 0)
+ {
+ break;
+ }
+ p = p->link[0];
+ }
+ return p;
+ }
+ }
+ return prev;
}
/* non paged pool functions ************************************************/
#ifdef TAG_STATISTICS_TRACKING
VOID
-MiRemoveFromTagHashTable(BLOCK_HDR* block)
- /*
- * Remove a block from the tag hash table
- */
+MiRemoveFromTagHashTable(HDR_USED* block)
+/*
+ * Remove a block from the tag hash table
+ */
{
- if (block->Tag == 0)
- {
+ if (block->Tag == 0)
+ {
return;
- }
-
- RemoveEntryList(&block->TagListEntry);
+ }
+ RemoveEntryList(&block->TagListEntry);
}
VOID
-MiAddToTagHashTable(BLOCK_HDR* block)
- /*
- * Add a block to the tag hash table
- */
+MiAddToTagHashTable(HDR_USED* block)
+/*
+ * Add a block to the tag hash table
+ */
{
- ULONG hash;
+ ULONG hash;
- if (block->Tag == 0)
- {
+ if (block->Tag == 0)
+ {
return;
- }
+ }
- hash = block->Tag % TAG_HASH_TABLE_SIZE;
+ hash = block->Tag % TAG_HASH_TABLE_SIZE;
- InsertHeadList(&tag_hash_table[hash], &block->TagListEntry);
+ InsertHeadList(&tag_hash_table[hash], &block->TagListEntry);
}
#endif /* TAG_STATISTICS_TRACKING */
-VOID
-MiInitializeNonPagedPool(VOID)
-{
-#ifdef TAG_STATISTICS_TRACKING
- ULONG i;
- for (i = 0; i < TAG_HASH_TABLE_SIZE; i++)
- {
- InitializeListHead(&tag_hash_table[i]);
- }
-#endif
- MiCurrentNonPagedPoolLength = 0;
- KeInitializeSpinLock(&MmNpoolLock);
- InitializeListHead(&UsedBlockListHead);
- InitializeListHead(&AddressListHead);
- FreeBlockListRoot = NULL;
-}
-
-#ifdef TAG_STATISTICS_TRACKING
+#if defined(TAG_STATISTICS_TRACKING)
VOID STATIC
MiDumpTagStats(ULONG CurrentTag, ULONG CurrentNrBlocks, ULONG CurrentSize)
{
- CHAR c1, c2, c3, c4;
-
- c1 = (CurrentTag >> 24) & 0xFF;
- c2 = (CurrentTag >> 16) & 0xFF;
- c3 = (CurrentTag >> 8) & 0xFF;
- c4 = CurrentTag & 0xFF;
-
- if (isprint(c1) && isprint(c2) && isprint(c3) && isprint(c4))
- {
+ CHAR c1, c2, c3, c4;
+
+ c1 = (CHAR)((CurrentTag >> 24) & 0xFF);
+ c2 = (CHAR)((CurrentTag >> 16) & 0xFF);
+ c3 = (CHAR)((CurrentTag >> 8) & 0xFF);
+ c4 = (CHAR)(CurrentTag & 0xFF);
+
+ if (isprint(c1) && isprint(c2) && isprint(c3) && isprint(c4))
+ {
DbgPrint("Tag %x (%c%c%c%c) Blocks %d Total Size %d Average Size %d\n",
- CurrentTag, c4, c3, c2, c1, CurrentNrBlocks,
- CurrentSize, CurrentSize / CurrentNrBlocks);
- }
- else
- {
+ CurrentTag, c4, c3, c2, c1, CurrentNrBlocks,
+ CurrentSize, CurrentSize / CurrentNrBlocks);
+ }
+ else
+ {
DbgPrint("Tag %x Blocks %d Total Size %d Average Size %d\n",
- CurrentTag, CurrentNrBlocks, CurrentSize,
- CurrentSize / CurrentNrBlocks);
- }
+ CurrentTag, CurrentNrBlocks, CurrentSize,
+ CurrentSize / CurrentNrBlocks);
+ }
}
-#endif /* TAG_STATISTICS_TRACKING */
+#endif /* defined(TAG_STATISTICS_TRACKING) */
VOID
MiDebugDumpNonPagedPoolStats(BOOLEAN NewOnly)
{
-#ifdef TAG_STATISTICS_TRACKING
- ULONG i;
- BLOCK_HDR* current;
- ULONG CurrentTag;
- ULONG CurrentNrBlocks;
- ULONG CurrentSize;
- ULONG TotalBlocks;
- ULONG TotalSize;
- LIST_ENTRY tmpListHead;
- PLIST_ENTRY current_entry;
-
- DbgPrint("******* Dumping non paging pool stats ******\n");
- TotalBlocks = 0;
- TotalSize = 0;
- for (i = 0; i < TAG_HASH_TABLE_SIZE; i++)
- {
+#if defined(TAG_STATISTICS_TRACKING)
+ ULONG i;
+ HDR_USED* current;
+ ULONG CurrentTag;
+ ULONG CurrentNrBlocks = 0;
+ ULONG CurrentSize = 0;
+ ULONG TotalBlocks;
+ ULONG TotalSize;
+ ULONG Size;
+ LIST_ENTRY tmpListHead;
+ PLIST_ENTRY current_entry;
+
+ DbgPrint("******* Dumping non paging pool stats ******\n");
+ TotalBlocks = 0;
+ TotalSize = 0;
+ for (i = 0; i < TAG_HASH_TABLE_SIZE; i++)
+ {
InitializeListHead(&tmpListHead);
while (!IsListEmpty(&tag_hash_table[i]))
- {
- CurrentTag = 0;
+ {
+ CurrentTag = 0;
- current_entry = tag_hash_table[i].Flink;
- while (current_entry != &tag_hash_table[i])
- {
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, TagListEntry);
- current_entry = current_entry->Flink;
- if (CurrentTag == 0)
- {
- CurrentTag = current->Tag;
- CurrentNrBlocks = 0;
- CurrentSize = 0;
- }
- if (current->Tag == CurrentTag)
- {
- RemoveEntryList(¤t->TagListEntry);
- InsertHeadList(&tmpListHead, ¤t->TagListEntry);
- if (!NewOnly || !current->Dumped)
- {
- CurrentNrBlocks++;
- TotalBlocks++;
- CurrentSize += current->Size;
- TotalSize += current->Size;
- current->Dumped = TRUE;
- }
- }
- }
- if (CurrentTag != 0 && CurrentNrBlocks != 0)
- {
- MiDumpTagStats(CurrentTag, CurrentNrBlocks, CurrentSize);
- }
- }
+ current_entry = tag_hash_table[i].Flink;
+ while (current_entry != &tag_hash_table[i])
+ {
+ current = CONTAINING_RECORD(current_entry, HDR_USED, TagListEntry);
+ current_entry = current_entry->Flink;
+ if (CurrentTag == 0)
+ {
+ CurrentTag = current->Tag;
+ CurrentNrBlocks = 0;
+ CurrentSize = 0;
+ }
+ if (current->Tag == CurrentTag)
+ {
+ RemoveEntryList(¤t->TagListEntry);
+ InsertHeadList(&tmpListHead, ¤t->TagListEntry);
+ if (!NewOnly || !current->Dumped)
+ {
+ CurrentNrBlocks++;
+ TotalBlocks++;
+ CurrentSize += current->hdr.Size;
+ TotalSize += current->hdr.Size;
+ current->Dumped = TRUE;
+ }
+ }
+ }
+ if (CurrentTag != 0 && CurrentNrBlocks != 0)
+ {
+ MiDumpTagStats(CurrentTag, CurrentNrBlocks, CurrentSize);
+ }
+ }
if (!IsListEmpty(&tmpListHead))
- {
- tag_hash_table[i].Flink = tmpListHead.Flink;
- tag_hash_table[i].Flink->Blink = &tag_hash_table[i];
- tag_hash_table[i].Blink = tmpListHead.Blink;
- tag_hash_table[i].Blink->Flink = &tag_hash_table[i];
- }
- }
- if (TotalBlocks != 0)
- {
+ {
+ tag_hash_table[i].Flink = tmpListHead.Flink;
+ tag_hash_table[i].Flink->Blink = &tag_hash_table[i];
+ tag_hash_table[i].Blink = tmpListHead.Blink;
+ tag_hash_table[i].Blink->Flink = &tag_hash_table[i];
+ }
+ }
+ if (TotalBlocks != 0)
+ {
DbgPrint("TotalBlocks %d TotalSize %d AverageSize %d\n",
- TotalBlocks, TotalSize, TotalSize / TotalBlocks);
- }
- else
- {
+ TotalBlocks, TotalSize, TotalSize / TotalBlocks);
+ }
+ else
+ {
DbgPrint("TotalBlocks %d TotalSize %d\n",
- TotalBlocks, TotalSize);
- }
- DbgPrint("Freeblocks %d TotalFreeSize %d AverageFreeSize %d\n",
- EiNrFreeBlocks, EiFreeNonPagedPool, EiNrFreeBlocks ? EiFreeNonPagedPool / EiNrFreeBlocks : 0);
- DbgPrint("***************** Dump Complete ***************\n");
-#endif /* TAG_STATISTICS_TRACKING */
+ TotalBlocks, TotalSize);
+ }
+ Size = EiFreeNonPagedPool - (MiNonPagedPoolLength - MiNonPagedPoolNrOfPages * PAGE_SIZE);
+ DbgPrint("Freeblocks %d TotalFreeSize %d AverageFreeSize %d\n",
+ EiNrFreeBlocks, Size, EiNrFreeBlocks ? Size / EiNrFreeBlocks : 0);
+ DbgPrint("***************** Dump Complete ***************\n");
+#endif /* defined(TAG_STATISTICS_TRACKING) */
}
VOID
MiDebugDumpNonPagedPool(BOOLEAN NewOnly)
{
- BLOCK_HDR* current;
+#if defined(POOL_DEBUG_APIS)
+ HDR_USED* current;
PLIST_ENTRY current_entry;
KIRQL oldIrql;
-
+
KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
DbgPrint("******* Dumping non paging pool contents ******\n");
current_entry = UsedBlockListHead.Flink;
while (current_entry != &UsedBlockListHead)
- {
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, ListEntry);
- if (!NewOnly || !current->Dumped)
- {
- CHAR c1, c2, c3, c4;
-
- c1 = (current->Tag >> 24) & 0xFF;
- c2 = (current->Tag >> 16) & 0xFF;
- c3 = (current->Tag >> 8) & 0xFF;
- c4 = current->Tag & 0xFF;
-
- if (isprint(c1) && isprint(c2) && isprint(c3) && isprint(c4))
- {
- DbgPrint("Size 0x%x Tag 0x%x (%c%c%c%c) Allocator 0x%x\n",
- current->Size, current->Tag, c4, c3, c2, c1,
- current->Caller);
- }
- else
- {
- DbgPrint("Size 0x%x Tag 0x%x Allocator 0x%x\n",
- current->Size, current->Tag, current->Caller);
- }
- current->Dumped = TRUE;
- }
- current_entry = current_entry->Flink;
- }
- DbgPrint("***************** Dump Complete ***************\n");
+ {
+ current = CONTAINING_RECORD(current_entry, HDR_USED, ListEntry);
+ if (!NewOnly || !current->Dumped)
+ {
+ CHAR c1, c2, c3, c4;
+
+ c1 = (CHAR)((current->Tag >> 24) & 0xFF);
+ c2 = (CHAR)((current->Tag >> 16) & 0xFF);
+ c3 = (CHAR)((current->Tag >> 8) & 0xFF);
+ c4 = (CHAR)(current->Tag & 0xFF);
+
+ if (isprint(c1) && isprint(c2) && isprint(c3) && isprint(c4))
+ {
+ DbgPrint("Size 0x%x Tag 0x%x (%c%c%c%c) Allocator 0x%x\n",
+ current->hdr.Size, current->Tag, c4, c3, c2, c1,
+ current->Caller);
+ }
+ else
+ {
+ DbgPrint("Size 0x%x Tag 0x%x Allocator 0x%x\n",
+ current->hdr.Size, current->Tag, current->Caller);
+ }
+ current->Dumped = TRUE;
+ }
+ current_entry = current_entry->Flink;
+ }
+ DbgPrint("***************** Dump Complete ***************\n");
KeReleaseSpinLock(&MmNpoolLock, oldIrql);
+#endif
}
-#ifndef WHOLE_PAGE_ALLOCATIONS
-
#ifdef ENABLE_VALIDATE_POOL
static void validate_free_list(void)
/*
* FUNCTION: Validate the integrity of the list of free blocks
*/
{
- BLOCK_HDR* current;
- PLIST_ENTRY current_entry;
- unsigned int blocks_seen=0;
-
- current_entry = MiFreeBlockListHead.Flink;
- while (current_entry != &MiFreeBlockListHead)
- {
- PVOID base_addr;
-
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, ListEntry);
- base_addr = (PVOID)current;
-
- if (current->Magic != BLOCK_HDR_FREE_MAGIC)
- {
- DbgPrint("Bad block magic (probable pool corruption) at %x\n",
- current);
- KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
- }
-
- if (base_addr < MiNonPagedPoolStart ||
- MiNonPagedPoolStart + current->Size > MiNonPagedPoolStart + MiCurrentNonPagedPoolLength)
- {
- DbgPrint("Block %x found outside pool area\n",current);
- DbgPrint("Size %d\n",current->Size);
- DbgPrint("Limits are %x %x\n",MiNonPagedPoolStart,
- MiNonPagedPoolStart+MiCurrentNonPagedPoolLength);
- KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
- }
- blocks_seen++;
- if (blocks_seen > MiNrFreeBlocks)
- {
- DbgPrint("Too many blocks on free list\n");
- KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
- }
- if (current->ListEntry.Flink != &MiFreeBlockListHead &&
- current->ListEntry.Flink->Blink != ¤t->ListEntry)
- {
- DbgPrint("%s:%d:Break in list (current %x next %x "
- "current->next->previous %x)\n",
- __FILE__,__LINE__,current, current->ListEntry.Flink,
- current->ListEntry.Flink->Blink);
- KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
- }
-
- current_entry = current_entry->Flink;
- }
+ HDR_FREE* current;
+ unsigned int blocks_seen=0;
+ PNODE p;
+
+ p = avl_get_first(FreeBlockListRoot);
+
+ while(p)
+ {
+ PVOID base_addr;
+
+ current = CONTAINING_RECORD(p, HDR_FREE, Node);
+ base_addr = (PVOID)current;
+
+ if (current->hdr.Magic != BLOCK_HDR_FREE_MAGIC)
+ {
+ DbgPrint("Bad block magic (probable pool corruption) at %x\n",
+ current);
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+
+ if (base_addr < MiNonPagedPoolStart ||
+ (ULONG_PTR)base_addr + current->hdr.Size > (ULONG_PTR)MiNonPagedPoolStart + MiNonPagedPoolLength)
+ {
+ DbgPrint("Block %x found outside pool area\n",current);
+ DbgPrint("Size %d\n",current->hdr.Size);
+ DbgPrint("Limits are %x %x\n",MiNonPagedPoolStart,
+ (ULONG_PTR)MiNonPagedPoolStart+MiNonPagedPoolLength);
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+ blocks_seen++;
+ if (blocks_seen > EiNrFreeBlocks)
+ {
+ DbgPrint("Too many blocks on free list\n");
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+ p = avl_get_next(FreeBlockListRoot, p);
+ }
}
static void validate_used_list(void)
* FUNCTION: Validate the integrity of the list of used blocks
*/
{
- BLOCK_HDR* current;
+ HDR_USED* current;
PLIST_ENTRY current_entry;
unsigned int blocks_seen=0;
-
+
current_entry = UsedBlockListHead.Flink;
while (current_entry != &UsedBlockListHead)
- {
- PVOID base_addr;
-
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, ListEntry);
- base_addr = (PVOID)current;
-
- if (current->Magic != BLOCK_HDR_USED_MAGIC)
- {
- DbgPrint("Bad block magic (probable pool corruption) at %x\n",
- current);
- KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
- }
- if (base_addr < MiNonPagedPoolStart ||
- (base_addr+current->Size) >
- MiNonPagedPoolStart+MiCurrentNonPagedPoolLength)
- {
- DbgPrint("Block %x found outside pool area\n",current);
- for(;;);
- }
- blocks_seen++;
- if (blocks_seen > EiNrUsedBlocks)
- {
- DbgPrint("Too many blocks on used list\n");
- for(;;);
- }
- if (current->ListEntry.Flink != &UsedBlockListHead &&
- current->ListEntry.Flink->Blink != ¤t->ListEntry)
- {
- DbgPrint("Break in list (current %x next %x)\n",
- current, current->ListEntry.Flink);
- for(;;);
- }
-
- current_entry = current_entry->Flink;
- }
+ {
+ PVOID base_addr;
+
+ current = CONTAINING_RECORD(current_entry, HDR_USED, ListEntry);
+ base_addr = (PVOID)current;
+
+ if (current->hdr.Magic != BLOCK_HDR_USED_MAGIC)
+ {
+ DbgPrint("Bad block magic (probable pool corruption) at %x\n",
+ current);
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+ if (base_addr < MiNonPagedPoolStart ||
+ ((ULONG_PTR)base_addr+current->hdr.Size) >
+ (ULONG_PTR)MiNonPagedPoolStart+MiNonPagedPoolLength)
+ {
+ DbgPrint("Block %x found outside pool area\n",current);
+ DbgPrint("Size %d\n",current->hdr.Size);
+ DbgPrint("Limits are %x %x\n",MiNonPagedPoolStart,
+ (ULONG_PTR)MiNonPagedPoolStart+MiNonPagedPoolLength);
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+ blocks_seen++;
+ if (blocks_seen > EiNrUsedBlocks)
+ {
+ DbgPrint("Too many blocks on used list\n");
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+ if (current->ListEntry.Flink != &UsedBlockListHead &&
+ current->ListEntry.Flink->Blink != ¤t->ListEntry)
+ {
+ DbgPrint("%s:%d:Break in list (current %x next %x "
+ "current->next->previous %x)\n",
+ __FILE__,__LINE__,current, current->ListEntry.Flink,
+ current->ListEntry.Flink->Blink);
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+
+ current_entry = current_entry->Flink;
+ }
}
-static void check_duplicates(BLOCK_HDR* blk)
+static void check_duplicates(HDR* blk)
/*
* FUNCTION: Check a block has no duplicates
* ARGUMENTS:
* NOTE: Bug checks if duplicates are found
*/
{
- char* base = (char*)blk;
- char* last = ((char*)blk) + +sizeof(BLOCK_HDR) + blk->Size;
- BLOCK_HDR* current;
+ ULONG_PTR base = (ULONG_PTR)blk;
+ ULONG_PTR last = (ULONG_PTR)blk + blk->Size;
PLIST_ENTRY current_entry;
-
- current_entry = MiFreeBlockListHead.Flink;
- while (current_entry != &MiFreeBlockListHead)
- {
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, ListEntry);
+ PNODE p;
+ HDR_FREE* free;
+ HDR_USED* used;
- if (current->Magic != BLOCK_HDR_FREE_MAGIC)
- {
- DbgPrint("Bad block magic (probable pool corruption) at %x\n",
- current);
- KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
- }
-
- if ( (char*)current > base && (char*)current < last )
- {
- DbgPrint("intersecting blocks on list\n");
- for(;;);
- }
- if ( (char*)current < base &&
- ((char*)current + current->Size + sizeof(BLOCK_HDR))
- > base )
- {
- DbgPrint("intersecting blocks on list\n");
- for(;;);
- }
+ p = avl_get_first(FreeBlockListRoot);
+
+ while (p)
+ {
+ free = CONTAINING_RECORD(p, HDR_FREE, Node);
+ if (free->hdr.Magic != BLOCK_HDR_FREE_MAGIC)
+ {
+ DbgPrint("Bad block magic (probable pool corruption) at %x\n",
+ free);
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
- current_entry = current_entry->Flink;
- }
+ if ( (ULONG_PTR)free > base && (ULONG_PTR)free < last )
+ {
+ DbgPrint("intersecting blocks on list\n");
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+ if ( (ULONG_PTR)free < base &&
+ ((ULONG_PTR)free + free->hdr.Size) > base )
+ {
+ DbgPrint("intersecting blocks on list\n");
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+ p = avl_get_next(FreeBlockListRoot, p);
+ }
current_entry = UsedBlockListHead.Flink;
while (current_entry != &UsedBlockListHead)
- {
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, ListEntry);
+ {
+ used = CONTAINING_RECORD(current_entry, HDR_USED, ListEntry);
+
+ if ( (ULONG_PTR)used > base && (ULONG_PTR)used < last )
+ {
+ DbgPrint("intersecting blocks on list\n");
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+ if ( (ULONG_PTR)used < base &&
+ ((ULONG_PTR)used + used->hdr.Size) > base )
+ {
+ DbgPrint("intersecting blocks on list\n");
+ KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
+ }
+
+ current_entry = current_entry->Flink;
+ }
- if ( (char*)current > base && (char*)current < last )
- {
- DbgPrint("intersecting blocks on list\n");
- for(;;);
- }
- if ( (char*)current < base &&
- ((char*)current + current->Size + sizeof(BLOCK_HDR))
- > base )
- {
- DbgPrint("intersecting blocks on list\n");
- for(;;);
- }
-
- current_entry = current_entry->Flink;
- }
-
}
static void validate_kernel_pool(void)
* FUNCTION: Checks the integrity of the kernel memory heap
*/
{
- BLOCK_HDR* current;
+ HDR_FREE* free;
+ HDR_USED* used;
PLIST_ENTRY current_entry;
-
+ PNODE p;
+
validate_free_list();
validate_used_list();
- current_entry = MiFreeBlockListHead.Flink;
- while (current_entry != &MiFreeBlockListHead)
- {
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, ListEntry);
- check_duplicates(current);
- current_entry = current_entry->Flink;
- }
+ p = avl_get_first(FreeBlockListRoot);
+ while (p)
+ {
+ free = CONTAINING_RECORD(p, HDR_FREE, Node);
+ check_duplicates(&free->hdr);
+ p = avl_get_next(FreeBlockListRoot, p);
+ }
current_entry = UsedBlockListHead.Flink;
while (current_entry != &UsedBlockListHead)
- {
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, ListEntry);
- check_duplicates(current);
- current_entry = current_entry->Flink;
- }
+ {
+ used = CONTAINING_RECORD(current_entry, HDR_USED, ListEntry);
+ check_duplicates(&used->hdr);
+ current_entry = current_entry->Flink;
+ }
}
#endif
#if 0
STATIC VOID
-free_pages(BLOCK_HDR* blk)
+free_pages(HDR_FREE* blk)
{
- ULONG start;
- ULONG end;
- ULONG i;
+ ULONG start;
+ ULONG end;
- start = (ULONG)blk;
- end = (ULONG)blk + sizeof(BLOCK_HDR) + blk->Size;
+ start = (ULONG_PTR)blk;
+ end = (ULONG_PTR)blk + blk->hdr.Size;
- /*
- * If the block doesn't contain a whole page then there is nothing to do
- */
- if (PAGE_ROUND_UP(start) >= PAGE_ROUND_DOWN(end))
- {
+ /*
+ * If the block doesn't contain a whole page then there is nothing to do
+ */
+ if (PAGE_ROUND_UP(start) >= PAGE_ROUND_DOWN(end))
+ {
return;
- }
+ }
}
#endif
-static void remove_from_used_list(BLOCK_HDR* current)
+static void remove_from_used_list(HDR_USED* current)
{
- RemoveEntryList(¤t->ListEntry);
- EiUsedNonPagedPool -= current->Size;
- EiNrUsedBlocks--;
+ RemoveEntryList(¤t->ListEntry);
+ EiUsedNonPagedPool -= current->hdr.Size;
+ EiNrUsedBlocks--;
}
-static void remove_from_free_list(BLOCK_HDR* current)
+static void remove_from_free_list(HDR_FREE* current)
{
- DPRINT("remove_from_free_list %d\n", current->Size);
+ DPRINT("remove_from_free_list %d\n", current->hdr.Size);
- avl_remove(&FreeBlockListRoot, ¤t->Node, compare_node);
+ avl_remove(&FreeBlockListRoot, ¤t->Node, compare_node);
- EiFreeNonPagedPool -= current->Size;
- EiNrFreeBlocks--;
- DPRINT("remove_from_free_list done\n");
+ EiFreeNonPagedPool -= current->hdr.Size;
+ EiNrFreeBlocks--;
+ DPRINT("remove_from_free_list done\n");
#ifdef DUMP_AVL
- DumpFreeBlockTree();
+
+ DumpFreeBlockTree();
#endif
}
-static void
-add_to_free_list(BLOCK_HDR* blk)
+static void
+add_to_free_list(HDR_FREE* blk)
/*
* FUNCTION: add the block to the free list (internal)
*/
{
- BLOCK_HDR* current;
-
- DPRINT("add_to_free_list (%d)\n", blk->Size);
-
- EiNrFreeBlocks++;
-
- if (blk->AddressList.Blink != &AddressListHead)
- {
- current = CONTAINING_RECORD(blk->AddressList.Blink, BLOCK_HDR, AddressList);
- if (current->Magic == BLOCK_HDR_FREE_MAGIC &&
- (PVOID)current + current->Size + sizeof(BLOCK_HDR) == (PVOID)blk)
- {
- CHECKPOINT;
- remove_from_free_list(current);
- RemoveEntryList(&blk->AddressList);
- current->Size = current->Size + sizeof(BLOCK_HDR) + blk->Size;
- current->Magic = BLOCK_HDR_USED_MAGIC;
- memset(blk, 0xcc, sizeof(BLOCK_HDR));
- blk = current;
- }
- }
-
- if (blk->AddressList.Flink != &AddressListHead)
- {
- current = CONTAINING_RECORD(blk->AddressList.Flink, BLOCK_HDR, AddressList);
- if (current->Magic == BLOCK_HDR_FREE_MAGIC &&
- (PVOID)blk + blk->Size + sizeof(BLOCK_HDR) == (PVOID)current)
- {
- CHECKPOINT;
- remove_from_free_list(current);
- RemoveEntryList(¤t->AddressList);
- blk->Size = blk->Size + sizeof(BLOCK_HDR) + current->Size;
- memset(current, 0xcc, sizeof(BLOCK_HDR));
- }
- }
-
- DPRINT("%d\n", blk->Size);
- blk->Magic = BLOCK_HDR_FREE_MAGIC;
- EiFreeNonPagedPool += blk->Size;
- avl_insert(&FreeBlockListRoot, &blk->Node, compare_node);
-
- DPRINT("add_to_free_list done\n");
+ HDR_FREE* current;
+ BOOL UpdatePrevPtr = FALSE;
+
+ DPRINT("add_to_free_list (%d)\n", blk->hdr.Size);
+
+ EiNrFreeBlocks++;
+
+ current = (HDR_FREE*)blk->hdr.previous;
+ if (current && current->hdr.Magic == BLOCK_HDR_FREE_MAGIC)
+ {
+ remove_from_free_list(current);
+ current->hdr.Size = current->hdr.Size + blk->hdr.Size;
+ current->hdr.Magic = BLOCK_HDR_USED_MAGIC;
+ memset(blk, 0xcc, HDR_USED_SIZE);
+ blk = current;
+ UpdatePrevPtr = TRUE;
+ }
+
+ current = (HDR_FREE*)((ULONG_PTR)blk + blk->hdr.Size);
+ if ((char*)current < (char*)MiNonPagedPoolStart + MiNonPagedPoolLength &&
+ current->hdr.Magic == BLOCK_HDR_FREE_MAGIC)
+ {
+ remove_from_free_list(current);
+ blk->hdr.Size += current->hdr.Size;
+ memset(current, 0xcc, HDR_FREE_SIZE);
+ UpdatePrevPtr = TRUE;
+ current = (HDR_FREE*)((ULONG_PTR)blk + blk->hdr.Size);
+ }
+ if (UpdatePrevPtr &&
+ (char*)current < (char*)MiNonPagedPoolStart + MiNonPagedPoolLength)
+ {
+ current->hdr.previous = &blk->hdr;
+ }
+ DPRINT("%d\n", blk->hdr.Size);
+ blk->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
+ EiFreeNonPagedPool += blk->hdr.Size;
+ avl_insert(&FreeBlockListRoot, &blk->Node, compare_node);
+ DPRINT("add_to_free_list done\n");
#ifdef DUMP_AVL
- DumpFreeBlockTree();
+
+ DumpFreeBlockTree();
#endif
}
-static void add_to_used_list(BLOCK_HDR* blk)
+static void add_to_used_list(HDR_USED* blk)
/*
* FUNCTION: add the block to the used list (internal)
*/
{
- InsertHeadList(&UsedBlockListHead, &blk->ListEntry);
- EiUsedNonPagedPool += blk->Size;
- EiNrUsedBlocks++;
-}
-
-inline static void* block_to_address(BLOCK_HDR* blk)
-/*
- * FUNCTION: Translate a block header address to the corresponding block
- * address (internal)
- */
-{
- return ( (void *) ((char*)blk + sizeof(BLOCK_HDR)) );
+ InsertHeadList(&UsedBlockListHead, &blk->ListEntry);
+ EiUsedNonPagedPool += blk->hdr.Size;
+ EiNrUsedBlocks++;
}
-inline static BLOCK_HDR* address_to_block(void* addr)
-{
- return (BLOCK_HDR *)
- ( ((char*)addr) - sizeof(BLOCK_HDR) );
-}
-static BLOCK_HDR* lookup_block(unsigned int size)
+static BOOLEAN
+grow_block(HDR_FREE* blk, PVOID end)
{
- BLOCK_HDR* current;
- BLOCK_HDR* best = NULL;
- ULONG new_size;
- PVOID block, block_boundary;
- PNODE p;
+ NTSTATUS Status;
+ PFN_TYPE Page[32];
+ ULONG_PTR StartIndex, EndIndex;
+ ULONG i, j, k;
- DPRINT("lookup_block %d\n", size);
+ StartIndex = (ULONG_PTR)(PAGE_ROUND_UP((ULONG_PTR)blk + HDR_FREE_SIZE - (ULONG_PTR)MiNonPagedPoolStart)) / PAGE_SIZE;
+ EndIndex = ((ULONG_PTR)PAGE_ROUND_UP(end) - (ULONG_PTR)MiNonPagedPoolStart) / PAGE_SIZE;
- if (size < PAGE_SIZE)
- {
- p = avl_find_equal_or_greater(FreeBlockListRoot, size, compare_value);
- if (p)
- {
- best = CONTAINING_RECORD(p, BLOCK_HDR, Node);
- }
- }
- else
- {
- p = avl_find_equal_or_greater(FreeBlockListRoot, size, compare_value);
- while(p)
- {
- current = CONTAINING_RECORD(p, BLOCK_HDR, Node);
- block = block_to_address(current);
- block_boundary = (PVOID)PAGE_ROUND_UP((ULONG)block);
- new_size = (ULONG)block_boundary - (ULONG)block + size;
- if (new_size != size && (ULONG)block_boundary - (ULONG)block < sizeof(BLOCK_HDR))
- {
- new_size += PAGE_SIZE;
- }
- if (current->Size >= new_size &&
- (best == NULL || current->Size < best->Size))
- {
- best = current;
- }
- if (best && current->Size >= size + PAGE_SIZE + 2 * sizeof(BLOCK_HDR))
- {
+ for (i = StartIndex; i < EndIndex; i++)
+ {
+ if (!(MiNonPagedPoolAllocMap[i / 32] & (1 << (i % 32))))
+ {
+ for (j = i + 1; j < EndIndex && j - i < 32; j++)
+ {
+ if (MiNonPagedPoolAllocMap[j / 32] & (1 << (j % 32)))
+ {
break;
- }
- p = avl_get_next(FreeBlockListRoot, p);
-
+ }
+ }
+ for (k = 0; k < j - i; k++)
+ {
+ Status = MmRequestPageMemoryConsumer(MC_NPPOOL, FALSE, &Page[k]);
+ if (!NT_SUCCESS(Status))
+ {
+ for (i = 0; i < k; i++)
+ {
+ MmReleasePageMemoryConsumer(MC_NPPOOL, Page[i]);
+ }
+ return FALSE;
+ }
}
- }
- DPRINT("lookup_block done %d\n", best ? best->Size : 0);
- return best;
+ Status = MmCreateVirtualMapping(NULL,
+ (PVOID)((ULONG_PTR)MiNonPagedPoolStart + i * PAGE_SIZE),
+ PAGE_READWRITE|PAGE_SYSTEM,
+ Page,
+ k);
+ if (!NT_SUCCESS(Status))
+ {
+ for (i = 0; i < k; i++)
+ {
+ MmReleasePageMemoryConsumer(MC_NPPOOL, Page[i]);
+ }
+ return FALSE;
+ }
+ for (j = i; j < k + i; j++)
+ {
+ MiNonPagedPoolAllocMap[j / 32] |= (1 << (j % 32));
+ }
+ MiNonPagedPoolNrOfPages += k;
+ i += k - 1;
+ }
+ }
+ return TRUE;
}
-static void* take_block(BLOCK_HDR* current, unsigned int size,
- ULONG Tag, PVOID Caller)
-/*
- * FUNCTION: Allocate a used block of least 'size' from the specified
- * free block
- * RETURNS: The address of the created memory block
- */
+static HDR_USED* get_block(unsigned int size, unsigned long alignment)
{
- BLOCK_HDR* blk;
- BOOL Removed = FALSE;
-
- DPRINT("take_block\n");
+ HDR_FREE *blk, *current, *previous = NULL, *next = NULL, *best = NULL;
+ ULONG previous_size = 0, current_size, next_size = 0, new_size;
+ PVOID end;
+ PVOID addr, aligned_addr, best_aligned_addr=NULL;
+ PNODE p;
+
+ DPRINT("get_block %d\n", size);
- if (size >= PAGE_SIZE)
+ p = avl_find_equal_or_greater(FreeBlockListRoot, size + HDR_USED_SIZE, compare_value);
+ while (p)
+ {
+ current = CONTAINING_RECORD(p, HDR_FREE, Node);
+ addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE);
+ /* calculate first aligned address available within this block */
+ aligned_addr = alignment > 0 ? MM_ROUND_UP(addr, alignment) : addr;
+ if (size < PAGE_SIZE)
{
- blk = address_to_block((PVOID)PAGE_ROUND_UP(block_to_address (current)));
- if (blk != current)
- {
- if ((ULONG)blk - (ULONG)current < sizeof(BLOCK_HDR))
- {
- (ULONG)blk += PAGE_SIZE;
- }
- assert((ULONG)blk - (ULONG)current + size <= current->Size && (ULONG)blk - (ULONG)current >= sizeof(BLOCK_HDR));
-
- memset(blk, 0, sizeof(BLOCK_HDR));
- blk->Magic = BLOCK_HDR_USED_MAGIC;
- blk->Size = current->Size - ((ULONG)blk - (ULONG)current);
- remove_from_free_list(current);
- current->Size -= (blk->Size + sizeof(BLOCK_HDR));
- blk->AddressList.Flink = current->AddressList.Flink;
- blk->AddressList.Flink->Blink = &blk->AddressList;
- blk->AddressList.Blink = ¤t->AddressList;
- current->AddressList.Flink = &blk->AddressList;
- add_to_free_list(current);
- Removed = TRUE;
- current = blk;
- }
+ /* check that the block is in one page */
+ if (PAGE_ROUND_DOWN(aligned_addr) != PAGE_ROUND_DOWN((ULONG_PTR)aligned_addr + size - 1))
+ {
+ aligned_addr = (PVOID)PAGE_ROUND_UP(aligned_addr);
+ }
}
- if (Removed == FALSE)
- {
- remove_from_free_list(current);
- }
-
- /*
- * If the block is much bigger than required then split it and
- * return a pointer to the allocated section. If the difference
- * between the sizes is marginal it makes no sense to have the
- * extra overhead
- */
- if (current->Size > size + sizeof(BLOCK_HDR))
- {
- BLOCK_HDR* free_blk;
-
- /*
- * Replace the bigger block with a smaller block in the
- * same position in the list
- */
- free_blk = (BLOCK_HDR *)(((char*)current)
- + sizeof(BLOCK_HDR) + size);
-
- free_blk->Size = current->Size - (sizeof(BLOCK_HDR) + size);
- current->Size=size;
- free_blk->AddressList.Flink = current->AddressList.Flink;
- free_blk->AddressList.Flink->Blink = &free_blk->AddressList;
- free_blk->AddressList.Blink = ¤t->AddressList;
- current->AddressList.Flink = &free_blk->AddressList;
- current->Magic = BLOCK_HDR_USED_MAGIC;
- free_blk->Magic = BLOCK_HDR_FREE_MAGIC;
- add_to_free_list(free_blk);
- add_to_used_list(current);
- current->Tag = Tag;
- current->Caller = Caller;
- current->Dumped = FALSE;
-#ifdef TAG_STATISTICS_TRACKING
- MiAddToTagHashTable(current);
-#endif /* TAG_STATISTICS_TRACKING */
- VALIDATE_POOL;
- return(block_to_address(current));
- }
-
+ DPRINT("%x %x\n", addr, aligned_addr);
+ if (aligned_addr != addr)
+ {
+ while((ULONG_PTR)aligned_addr - (ULONG_PTR)addr < HDR_FREE_SIZE)
+ {
+ if (alignment == 0)
+ {
+ aligned_addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE + HDR_FREE_SIZE);
+ }
+ else
+ {
+ aligned_addr = MM_ROUND_UP((PVOID)((ULONG_PTR)current + HDR_USED_SIZE + HDR_FREE_SIZE), alignment);
+ }
+ if (size < PAGE_SIZE)
+ {
+ /* check that the block is in one page */
+ if (PAGE_ROUND_DOWN(aligned_addr) != PAGE_ROUND_DOWN((ULONG_PTR)aligned_addr + size - 1))
+ {
+ aligned_addr = (PVOID)PAGE_ROUND_UP(aligned_addr);
+ }
+ }
+ }
+ }
+ DPRINT("%x %x\n", addr, aligned_addr);
+ new_size = (ULONG_PTR)aligned_addr - (ULONG_PTR)addr + size;
+ if (current->hdr.Size >= new_size + HDR_USED_SIZE &&
+ (best == NULL || current->hdr.Size < best->hdr.Size))
+ {
+ best = current;
+ best_aligned_addr = aligned_addr;
+ if (new_size <= size + 2 * HDR_FREE_SIZE)
+ {
+ break;
+ }
+ }
+
+ if (best)
+ {
+ if (size < PAGE_SIZE)
+ {
+ if (current->hdr.Size >= 2 * PAGE_SIZE + HDR_FREE_SIZE)
+ {
+ break;
+ }
+ }
+ else
+ {
+ if (current->hdr.Size >= size + alignment + HDR_FREE_SIZE)
+ {
+ break;
+ }
+ }
+ }
+ p = avl_get_next(FreeBlockListRoot, p);
+ }
/*
- * Otherwise allocate the whole block
+ * We didn't find anything suitable at all.
*/
+ if (best == NULL)
+ {
+ return NULL;
+ }
- current->Magic = BLOCK_HDR_USED_MAGIC;
- current->Tag = Tag;
- current->Caller = Caller;
- current->Dumped = FALSE;
- add_to_used_list(current);
-#ifdef TAG_STATISTICS_TRACKING
- MiAddToTagHashTable(current);
-#endif /* TAG_STATISTICS_TRACKING */
+ DPRINT(":: blk %x blk->hdr.Size %d (%d) Size %d\n", best, best->hdr.Size, best->hdr.Size - HDR_USED_SIZE, size);
- VALIDATE_POOL;
- return(block_to_address(current));
-}
+ current = best;
+ current_size = current->hdr.Size - HDR_USED_SIZE;
+ addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE);
+ if (addr != best_aligned_addr)
+ {
+ blk = (HDR_FREE*)((ULONG_PTR)best_aligned_addr - HDR_USED_SIZE);
+ /*
+ * if size-aligned, break off the preceding bytes into their own block...
+ */
+ previous = current;
+ previous_size = (ULONG_PTR)blk - (ULONG_PTR)previous - HDR_FREE_SIZE;
+ current = blk;
+ current_size -= ((ULONG_PTR)current - (ULONG_PTR)previous);
+ }
+ end = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE + size);
-static void* grow_kernel_pool(unsigned int size, ULONG Tag, PVOID Caller)
-/*
- * FUNCTION: Grow the executive heap to accomodate a block of at least 'size'
- * bytes
- */
-{
- ULONG nr_pages = PAGE_ROUND_UP(size + sizeof(BLOCK_HDR)) / PAGE_SIZE;
- ULONG start;
- BLOCK_HDR* blk=NULL;
- BLOCK_HDR* current;
- ULONG i;
- KIRQL oldIrql;
- NTSTATUS Status;
- PVOID block = NULL;
- PLIST_ENTRY current_entry;
+ if (current_size >= size + HDR_FREE_SIZE + MM_POOL_ALIGNMENT)
+ {
+ /* create a new free block after our block, if the memory size is >= 4 byte for this block */
+ next = (HDR_FREE*)((ULONG_PTR)current + size + HDR_USED_SIZE);
+ next_size = current_size - size - HDR_FREE_SIZE;
+ current_size = size;
+ end = (PVOID)((ULONG_PTR)next + HDR_FREE_SIZE);
+ }
- if (size >= PAGE_SIZE)
- {
- nr_pages ++;
- }
+ if (previous)
+ {
+ remove_from_free_list(previous);
+ if (!grow_block(previous, end))
+ {
+ add_to_free_list(previous);
+ return NULL;
+ }
+ memset(current, 0, HDR_USED_SIZE);
+ current->hdr.Size = current_size + HDR_USED_SIZE;
+ current->hdr.Magic = BLOCK_HDR_USED_MAGIC;
+ current->hdr.previous = &previous->hdr;
+ previous->hdr.Size = previous_size + HDR_FREE_SIZE;
+ if (next == NULL)
+ {
+ blk = (HDR_FREE*)((ULONG_PTR)current + current->hdr.Size);
+ if ((ULONG_PTR)blk < (ULONG_PTR)MiNonPagedPoolStart + MiNonPagedPoolLength)
+ {
+ blk->hdr.previous = ¤t->hdr;
+ }
+ }
- KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
- start = (ULONG)MiNonPagedPoolStart + MiCurrentNonPagedPoolLength;
- if (MiCurrentNonPagedPoolLength + nr_pages * PAGE_SIZE > MiNonPagedPoolLength)
- {
- DbgPrint("CRITICAL: Out of non-paged pool space\n");
- KEBUGCHECK(0);
- }
- MiCurrentNonPagedPoolLength += nr_pages * PAGE_SIZE;
- KeReleaseSpinLock(&MmNpoolLock, oldIrql);
+ add_to_free_list(previous);
+ }
+ else
+ {
+ remove_from_free_list(current);
- DPRINT("growing heap for block size %d, ",size);
- DPRINT("start %x\n",start);
-
- for (i=0;i<nr_pages;i++)
- {
- PHYSICAL_ADDRESS Page;
- /* FIXME: Check whether we can really wait here. */
- Status = MmRequestPageMemoryConsumer(MC_NPPOOL, TRUE, &Page);
- if (!NT_SUCCESS(Status))
- {
- KEBUGCHECK(0);
- return(NULL);
- }
- Status = MmCreateVirtualMapping(NULL,
- (PVOID)(start + (i*PAGE_SIZE)),
- PAGE_READWRITE|PAGE_SYSTEM,
- Page,
- TRUE);
- if (!NT_SUCCESS(Status))
- {
- DbgPrint("Unable to create virtual mapping\n");
- KEBUGCHECK(0);
- }
- }
-
- blk = (struct _BLOCK_HDR *)start;
- memset(blk, 0, sizeof(BLOCK_HDR));
- blk->Size = (nr_pages * PAGE_SIZE) - sizeof(BLOCK_HDR);
- memset(block_to_address(blk), 0xcc, blk->Size);
+ if (!grow_block(current, end))
+ {
+ add_to_free_list(current);
+ return NULL;
+ }
+ current->hdr.Magic = BLOCK_HDR_USED_MAGIC;
+ if (next)
+ {
+ current->hdr.Size = current_size + HDR_USED_SIZE;
+ }
+ }
- KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
- current_entry = AddressListHead.Blink;
- while (current_entry != &AddressListHead)
- {
- current = CONTAINING_RECORD(current_entry, BLOCK_HDR, AddressList);
- if ((PVOID)current + current->Size < (PVOID)blk)
- {
- InsertHeadList(current_entry, &blk->AddressList);
- break;
- }
- current_entry = current_entry->Blink;
- }
- if (current_entry == &AddressListHead)
- {
- InsertHeadList(&AddressListHead, &blk->AddressList);
- }
- blk->Magic = BLOCK_HDR_FREE_MAGIC;
- add_to_free_list(blk);
- blk = lookup_block(size);
- if (blk)
- {
- block = take_block(blk, size, Tag, Caller);
- VALIDATE_POOL;
- }
- KeReleaseSpinLock(&MmNpoolLock, oldIrql);
- return block;
+ if (next)
+ {
+ memset(next, 0, HDR_FREE_SIZE);
+ next->hdr.Size = next_size + HDR_FREE_SIZE;
+ next->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
+ next->hdr.previous = ¤t->hdr;
+ blk = (HDR_FREE*)((ULONG_PTR)next + next->hdr.Size);
+ if ((ULONG_PTR)blk < (ULONG_PTR)MiNonPagedPoolStart + MiNonPagedPoolLength)
+ {
+ blk->hdr.previous = &next->hdr;
+ }
+ add_to_free_list(next);
+ }
+
+ add_to_used_list((HDR_USED*)current);
+ VALIDATE_POOL;
+
+ if (size < PAGE_SIZE)
+ {
+ addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE);
+ if (PAGE_ROUND_DOWN(addr) != PAGE_ROUND_DOWN((PVOID)((ULONG_PTR)addr + size - 1)))
+ {
+ DPRINT1("%x %x\n", addr, (ULONG_PTR)addr + size);
+ }
+ ASSERT (PAGE_ROUND_DOWN(addr) == PAGE_ROUND_DOWN((PVOID)((ULONG_PTR)addr + size - 1)));
+ }
+ if (alignment)
+ {
+ addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE);
+ ASSERT(MM_ROUND_UP(addr, alignment) == addr);
+ }
+ return (HDR_USED*)current;
}
-#endif /* not WHOLE_PAGE_ALLOCATIONS */
+ULONG STDCALL
+ExRosQueryNonPagedPoolTag ( PVOID Addr )
+{
+ HDR_USED* blk=(HDR_USED*)((ULONG_PTR)Addr - HDR_USED_SIZE);
+ if (blk->hdr.Magic != BLOCK_HDR_USED_MAGIC)
+ KEBUGCHECK(0);
+
+ return blk->Tag;
+}
VOID STDCALL ExFreeNonPagedPool (PVOID block)
/*
* block = block to free
*/
{
-#ifdef WHOLE_PAGE_ALLOCATIONS /* WHOLE_PAGE_ALLOCATIONS */
+ HDR_USED* blk=(HDR_USED*)((ULONG_PTR)block - HDR_USED_SIZE);
KIRQL oldIrql;
if (block == NULL)
- {
- return;
- }
+ {
+ return;
+ }
DPRINT("freeing block %x\n",blk);
-
- POOL_TRACE("ExFreePool(block %x), size %d, caller %x\n",block,blk->size,
- ((PULONG)&block)[-1]);
-
- KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
-
- ExFreeWholePageBlock(block);
- KeReleaseSpinLock(&MmNpoolLock, oldIrql);
-
-#else /* not WHOLE_PAGE_ALLOCATIONS */
- BLOCK_HDR* blk=address_to_block(block);
- KIRQL oldIrql;
-
- if (block == NULL)
- {
- return;
- }
-
- DPRINT("freeing block %x\n",blk);
-
- POOL_TRACE("ExFreePool(block %x), size %d, caller %x\n",block,blk->size,
- ((PULONG)&block)[-1]);
-
+ POOL_TRACE("ExFreePool(block %x), size %d, caller %x\n",block,blk->hdr.Size,
+ block->Caller);
KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
VALIDATE_POOL;
-
- if (blk->Magic != BLOCK_HDR_USED_MAGIC)
- {
- if (blk->Magic == BLOCK_HDR_FREE_MAGIC)
- {
- DbgPrint("ExFreePool of already freed address %x\n", block);
- }
- else
- {
- DbgPrint("ExFreePool of non-allocated address %x (magic %x)\n",
- block, blk->Magic);
- }
- KEBUGCHECK(0);
- return;
- }
-
- memset(block, 0xcc, blk->Size);
-
+ if (blk->hdr.Magic != BLOCK_HDR_USED_MAGIC)
+ {
+ if (blk->hdr.Magic == BLOCK_HDR_FREE_MAGIC)
+ {
+ DbgPrint("ExFreePool of already freed address %x\n", block);
+ }
+ else
+ {
+ DbgPrint("ExFreePool of non-allocated address %x (magic %x)\n",
+ block, blk->hdr.Magic);
+ }
+ KEBUGCHECK(0);
+ return;
+ }
+ memset(block, 0xcc, blk->hdr.Size - HDR_USED_SIZE);
#ifdef TAG_STATISTICS_TRACKING
+
MiRemoveFromTagHashTable(blk);
-#endif /* TAG_STATISTICS_TRACKING */
+#endif
+
remove_from_used_list(blk);
- blk->Tag = 0;
- blk->Caller = NULL;
- blk->TagListEntry.Flink = blk->TagListEntry.Blink = NULL;
- blk->Magic = BLOCK_HDR_FREE_MAGIC;
- add_to_free_list(blk);
+ blk->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
+ add_to_free_list((HDR_FREE*)blk);
VALIDATE_POOL;
KeReleaseSpinLock(&MmNpoolLock, oldIrql);
-
-#endif /* WHOLE_PAGE_ALLOCATIONS */
}
-PVOID STDCALL
-ExAllocateNonPagedPoolWithTag(ULONG Type, ULONG Size, ULONG Tag, PVOID Caller)
+PVOID STDCALL
+ExAllocateNonPagedPoolWithTag(POOL_TYPE Type, ULONG Size, ULONG Tag, PVOID Caller)
{
-#ifdef WHOLE_PAGE_ALLOCATIONS
PVOID block;
+ HDR_USED* best = NULL;
KIRQL oldIrql;
-
- POOL_TRACE("ExAllocatePool(NumberOfBytes %d) caller %x ",
- Size,Caller);
-
- KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
-
- /*
- * accomodate this useful idiom
- */
- if (Size == 0)
- {
- POOL_TRACE("= NULL\n");
- KeReleaseSpinLock(&MmNpoolLock, oldIrql);
- return(NULL);
- }
-
- block = ExAllocateWholePageBlock(Size);
- KeReleaseSpinLock(&MmNpoolLock, oldIrql);
- return(block);
+ ULONG alignment;
-#else /* not WHOLE_PAGE_ALLOCATIONS */
- PVOID block;
- BLOCK_HDR* best = NULL;
- KIRQL oldIrql;
-
POOL_TRACE("ExAllocatePool(NumberOfBytes %d) caller %x ",
- Size,Caller);
-
+ Size,Caller);
+
KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
VALIDATE_POOL;
#if 0
/* after some allocations print the npaged pool stats */
#ifdef TAG_STATISTICS_TRACKING
+
{
- static ULONG counter = 0;
- if (counter++ % 100000 == 0)
- {
- MiDebugDumpNonPagedPoolStats(FALSE);
- }
+ static ULONG counter = 0;
+ if (counter++ % 100000 == 0)
+ {
+ MiDebugDumpNonPagedPoolStats(FALSE);
+ }
}
#endif
#endif
/*
- * accomodate this useful idiom
- */
+ * accomodate this useful idiom
+ */
if (Size == 0)
- {
- POOL_TRACE("= NULL\n");
- KeReleaseSpinLock(&MmNpoolLock, oldIrql);
- return(NULL);
- }
- /* Make the size dword alligned, this makes the block dword alligned */
- Size = ROUND_UP(Size, 4);
- /*
- * Look for an already created block of sufficent size
- */
- best = lookup_block(Size);
- if (best == NULL)
- {
- KeReleaseSpinLock(&MmNpoolLock, oldIrql);
- block = grow_kernel_pool(Size, Tag, Caller);
- if (block == NULL)
- {
- DPRINT1("%d\n", Size);
- DumpFreeBlockTree();
- }
- assert(block != NULL);
- memset(block,0,Size);
- }
+ {
+ POOL_TRACE("= NULL\n");
+ KeReleaseSpinLock(&MmNpoolLock, oldIrql);
+ return(NULL);
+ }
+ /* Make the size dword alligned, this makes the block dword alligned */
+ Size = ROUND_UP(Size, MM_POOL_ALIGNMENT);
+
+ if (Size >= PAGE_SIZE)
+ {
+ alignment = PAGE_SIZE;
+ }
+ else if (Type & CACHE_ALIGNED_POOL_MASK)
+ {
+ alignment = MM_CACHE_LINE_SIZE;
+ }
else
- {
- block=take_block(best, Size, Tag, Caller);
- VALIDATE_POOL;
- KeReleaseSpinLock(&MmNpoolLock, oldIrql);
- memset(block,0,Size);
- }
+ {
+ alignment = 0;
+ }
+
+ best = get_block(Size, alignment);
+ if (best == NULL)
+ {
+ KeReleaseSpinLock(&MmNpoolLock, oldIrql);
+ DPRINT1("Trying to allocate %lu bytes from nonpaged pool - nothing suitable found, returning NULL\n",
+ Size );
+ return NULL;
+ }
+ best->Tag = Tag;
+ best->Caller = Caller;
+ best->Dumped = FALSE;
+ best->TagListEntry.Flink = best->TagListEntry.Blink = NULL;
+#ifdef TAG_STATISTICS_TRACKING
+
+ MiAddToTagHashTable(best);
+#endif
+
+ KeReleaseSpinLock(&MmNpoolLock, oldIrql);
+ block = (PVOID)((ULONG_PTR)best + HDR_USED_SIZE);
+ /* RtlZeroMemory(block, Size);*/
return(block);
-#endif /* WHOLE_PAGE_ALLOCATIONS */
}
-#ifdef WHOLE_PAGE_ALLOCATIONS
-
-PVOID STDCALL
-ExAllocateWholePageBlock(ULONG UserSize)
+VOID INIT_FUNCTION
+MiInitializeNonPagedPool(VOID)
{
- PVOID Address;
- PHYSICAL_ADDRESS Page;
- ULONG i;
- ULONG Size;
- ULONG NrPages;
-
- Size = sizeof(ULONG) + UserSize;
- NrPages = ROUND_UP(Size, PAGE_SIZE) / PAGE_SIZE;
-
- Address = MiAllocNonPagedPoolRegion(NrPages + 1);
-
- for (i = 0; i < NrPages; i++)
- {
- Page = MmAllocPage(MC_NPPOOL, 0);
- if (Page.QuadPart == 0LL)
- {
- KEBUGCHECK(0);
- }
- MmCreateVirtualMapping(NULL,
- Address + (i * PAGE_SIZE),
- PAGE_READWRITE | PAGE_SYSTEM,
- Page,
- TRUE);
- }
-
- *((PULONG)((ULONG)Address + (NrPages * PAGE_SIZE) - Size)) = NrPages;
- return((PVOID)((ULONG)Address + (NrPages * PAGE_SIZE) - UserSize));
+ NTSTATUS Status;
+ PFN_TYPE Page;
+ ULONG i;
+ PVOID Address;
+ HDR_USED* used;
+ HDR_FREE* free;
+#ifdef TAG_STATISTICS_TRACKING
+
+ for (i = 0; i < TAG_HASH_TABLE_SIZE; i++)
+ {
+ InitializeListHead(&tag_hash_table[i]);
+ }
+#endif
+ KeInitializeSpinLock(&MmNpoolLock);
+ InitializeListHead(&UsedBlockListHead);
+ InitializeListHead(&AddressListHead);
+ FreeBlockListRoot = NULL;
+
+ MiNonPagedPoolAllocMap = (PVOID)((ULONG_PTR)MiNonPagedPoolStart + PAGE_SIZE);
+ MiNonPagedPoolNrOfPages = PAGE_ROUND_UP(ROUND_UP(MiNonPagedPoolLength / PAGE_SIZE, 32) / 8 + HDR_FREE_SIZE) + PAGE_SIZE;
+ MiNonPagedPoolNrOfPages /= PAGE_SIZE;
+ Address = MiNonPagedPoolStart;
+
+ for (i = 0; i < MiNonPagedPoolNrOfPages; i++)
+ {
+ Status = MmRequestPageMemoryConsumer(MC_NPPOOL, FALSE, &Page);
+ if (!NT_SUCCESS(Status))
+ {
+ DbgPrint("Unable to allocate a page\n");
+ KEBUGCHECK(0);
+ }
+
+ Status = MmCreateVirtualMapping(NULL,
+ Address,
+ PAGE_READWRITE|PAGE_SYSTEM,
+ &Page,
+ 1);
+ if (!NT_SUCCESS(Status))
+ {
+ DbgPrint("Unable to create virtual mapping\n");
+ KEBUGCHECK(0);
+ }
+ Address = (PVOID)((ULONG_PTR)Address + PAGE_SIZE);
+ }
+
+ for (i = 0; i < MiNonPagedPoolNrOfPages; i++)
+ {
+ MiNonPagedPoolAllocMap[i / 32] |= (1 << (i % 32));
+ }
+
+ /* the first block is free */
+ free = (HDR_FREE*)MiNonPagedPoolStart;
+ free->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
+ free->hdr.Size = PAGE_SIZE - HDR_USED_SIZE;
+ free->hdr.previous = NULL;
+ memset((PVOID)((ULONG_PTR)free + HDR_FREE_SIZE), 0xcc, free->hdr.Size - HDR_FREE_SIZE);
+ add_to_free_list(free);
+
+ /* the second block contains the non paged pool bitmap */
+ used = (HDR_USED*)((ULONG_PTR)free + free->hdr.Size);
+ used->hdr.Magic = BLOCK_HDR_USED_MAGIC;
+ used->hdr.Size = ROUND_UP(MiNonPagedPoolLength / PAGE_SIZE, 32) / 8 + HDR_USED_SIZE;
+ used->hdr.previous = &free->hdr;
+ used->Tag = 0xffffffff;
+ used->Caller = 0;
+ used->Dumped = FALSE;
+ add_to_used_list(used);
+#ifdef TAG_STATISTICS_TRACKING
+ MiAddToTagHashTable(used);
+#endif
+
+ /* the third block is the free block after the bitmap */
+ free = (HDR_FREE*)((ULONG_PTR)used + used->hdr.Size);
+ free->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
+ free->hdr.Size = MiNonPagedPoolLength - ((ULONG_PTR)free - (ULONG_PTR)MiNonPagedPoolStart);
+ free->hdr.previous = &used->hdr;
+ memset((PVOID)((ULONG_PTR)free + HDR_FREE_SIZE), 0x0cc, (ULONG_PTR)Address - (ULONG_PTR)free - HDR_FREE_SIZE);
+ add_to_free_list(free);
}
-VOID STDCALL
-ExFreeWholePageBlock(PVOID Addr)
+PVOID
+STDCALL
+MiAllocateSpecialPool (IN POOL_TYPE PoolType,
+ IN SIZE_T NumberOfBytes,
+ IN ULONG Tag,
+ IN ULONG Underrun
+ )
{
- ULONG NrPages;
-
- if (Addr < MiNonPagedPoolStart ||
- Addr >= (MiNonPagedPoolStart + MiCurrentNonPagedPoolLength))
- {
- DbgPrint("Block %x found outside pool area\n", Addr);
- KEBUGCHECK(0);
- }
- NrPages = *(PULONG)((ULONG)Addr - sizeof(ULONG));
- MiFreeNonPagedPoolRegion((PVOID)PAGE_ROUND_DOWN((ULONG)Addr), NrPages, TRUE);
+ /* FIXME: Special Pools not Supported */
+ DbgPrint("Special Pools not supported\n");
+ return NULL;
}
-#endif /* WHOLE_PAGE_ALLOCATIONS */
-
/* EOF */
projects / reactos.git / blobdiff