1 /* $Id: npool.c,v 1.69 2003/07/10 21:05:03 royce Exp $
3 * COPYRIGHT: See COPYING in the top level directory
4 * PROJECT: ReactOS kernel
5 * FILE: ntoskrnl/mm/npool.c
6 * PURPOSE: Implements the kernel memory pool
7 * PROGRAMMER: David Welch (welch@cwcom.net)
10 * 10/06/98: Bug fixes by Iwan Fatahi (i_fatahi@hotmail.com)
11 * in take_block (if current bigger than required)
12 * in remove_from_used_list
14 * 23/08/98: Fixes from Robert Bergkvist (fragdance@hotmail.com)
17 /* INCLUDES ****************************************************************/
19 #include <ddk/ntddk.h>
20 #include <internal/mm.h>
21 #include <internal/ntoskrnl.h>
22 #include <internal/pool.h>
25 #include <internal/debug.h>
27 /* Enable strict checking of the nonpaged pool on every allocation */
28 //#define ENABLE_VALIDATE_POOL
30 /* Enable tracking of statistics about the tagged blocks in the pool */
31 #define TAG_STATISTICS_TRACKING
34 * Put each block in its own range of pages and position the block at the
35 * end of the range so any accesses beyond the end of block are to invalid
38 //#define WHOLE_PAGE_ALLOCATIONS
40 #ifdef ENABLE_VALIDATE_POOL
41 #define VALIDATE_POOL validate_kernel_pool()
47 #define POOL_TRACE(args...) do { DbgPrint(args); } while(0);
49 #define POOL_TRACE(args...)
52 /* avl types ****************************************************************/
55 * This declarations should be moved into a separate header file.
60 struct _NODE
* link
[2];
65 /* TYPES *******************************************************************/
67 #define BLOCK_HDR_USED_MAGIC (0xdeadbeef)
68 #define BLOCK_HDR_FREE_MAGIC (0xceadbeef)
71 * fields present at the start of a block (this is for internal use only)
73 typedef struct _BLOCK_HDR
78 LIST_ENTRY AddressList
;
79 LIST_ENTRY TagListEntry
;
87 ExAllocateWholePageBlock(ULONG Size
);
89 ExFreeWholePageBlock(PVOID Addr
);
91 /* GLOBALS *****************************************************************/
93 extern PVOID MiNonPagedPoolStart
;
94 extern ULONG MiNonPagedPoolLength
;
95 static ULONG MiCurrentNonPagedPoolLength
= 0;
98 * Head of the list of free blocks
100 static PNODE FreeBlockListRoot
= NULL
;
103 * Head of the list of in use block
105 static LIST_ENTRY UsedBlockListHead
;
107 static LIST_ENTRY AddressListHead
;
109 #ifndef WHOLE_PAGE_ALLOCATIONS
111 * Count of free blocks
113 static ULONG EiNrFreeBlocks
= 0;
116 * Count of used blocks
118 static ULONG EiNrUsedBlocks
= 0;
122 * Lock that protects the non-paged pool data structures
124 static KSPIN_LOCK MmNpoolLock
;
127 * Total memory used for free nonpaged pool blocks
129 ULONG EiFreeNonPagedPool
= 0;
132 * Total memory used for nonpaged pool blocks
134 ULONG EiUsedNonPagedPool
= 0;
137 * Allocate a range of memory in the nonpaged pool
140 MiAllocNonPagedPoolRegion(unsigned int nr_pages
);
143 MiFreeNonPagedPoolRegion(PVOID Addr
, ULONG Count
, BOOLEAN Free
);
145 #ifdef TAG_STATISTICS_TRACKING
146 #define TAG_HASH_TABLE_SIZE (1024)
147 static LIST_ENTRY tag_hash_table
[TAG_HASH_TABLE_SIZE
];
148 #endif /* TAG_STATISTICS_TRACKING */
150 /* avl helper functions ****************************************************/
152 void DumpFreeBlockNode(PNODE p
)
154 static int count
= 0;
161 DumpFreeBlockNode(p
->link
[0]);
162 blk
= CONTAINING_RECORD(p
, BLOCK_HDR
, Node
);
163 DbgPrint("%08x %8d (%d)\n", blk
, blk
->Size
, count
);
164 DumpFreeBlockNode(p
->link
[1]);
169 void DumpFreeBlockTree(void)
171 DbgPrint("--- Begin tree ------------------\n");
172 DbgPrint("%08x\n", CONTAINING_RECORD(FreeBlockListRoot
, BLOCK_HDR
, Node
));
173 DumpFreeBlockNode(FreeBlockListRoot
);
174 DbgPrint("--- End tree --------------------\n");
177 int compare_node(PNODE p1
, PNODE p2
)
179 BLOCK_HDR
* blk1
= CONTAINING_RECORD(p1
, BLOCK_HDR
, Node
);
180 BLOCK_HDR
* blk2
= CONTAINING_RECORD(p2
, BLOCK_HDR
, Node
);
182 if (blk1
->Size
== blk2
->Size
)
195 if (blk1
->Size
< blk2
->Size
)
199 if (blk1
->Size
> blk2
->Size
)
208 int compare_value(PVOID value
, PNODE p
)
210 BLOCK_HDR
* blk
= CONTAINING_RECORD(p
, BLOCK_HDR
, Node
);
211 ULONG v
= *(PULONG
)value
;
224 /* avl functions **********************************************************/
227 * The avl functions should be moved into a separate file.
230 /* The avl_insert and avl_remove are based on libavl (library for manipulation of binary trees). */
232 void avl_insert (PNODE
* root
, PNODE n
, int (*compare
)(PNODE
, PNODE
))
234 PNODE y
; /* Top node to update balance factor, and parent. */
235 PNODE p
, q
; /* Iterator, and parent. */
236 PNODE w
; /* New root of rebalanced subtree. */
237 int dir
; /* Direction to descend. */
239 n
->link
[0] = n
->link
[1] = n
->parent
= NULL
;
243 for (q
= NULL
, p
= *root
; p
!= NULL
; q
= p
, p
= p
->link
[dir
])
245 dir
= compare(n
, p
) > 0;
267 for (p
= n
; p
!= y
; p
= q
)
270 dir
= q
->link
[0] != p
;
281 if (y
->balance
== -2)
283 PNODE x
= y
->link
[0];
284 if (x
->balance
== -1)
287 y
->link
[0] = x
->link
[1];
289 x
->balance
= y
->balance
= 0;
290 x
->parent
= y
->parent
;
292 if (y
->link
[0] != NULL
)
294 y
->link
[0]->parent
= y
;
299 assert (x
->balance
== +1);
301 x
->link
[1] = w
->link
[0];
303 y
->link
[0] = w
->link
[1];
305 if (w
->balance
== -1)
310 else if (w
->balance
== 0)
312 x
->balance
= y
->balance
= 0;
314 else /* |w->pavl_balance == +1| */
320 w
->parent
= y
->parent
;
321 x
->parent
= y
->parent
= w
;
322 if (x
->link
[1] != NULL
)
324 x
->link
[1]->parent
= x
;
326 if (y
->link
[0] != NULL
)
328 y
->link
[0]->parent
= y
;
332 else if (y
->balance
== +2)
334 PNODE x
= y
->link
[1];
335 if (x
->balance
== +1)
338 y
->link
[1] = x
->link
[0];
340 x
->balance
= y
->balance
= 0;
341 x
->parent
= y
->parent
;
343 if (y
->link
[1] != NULL
)
345 y
->link
[1]->parent
= y
;
350 assert (x
->balance
== -1);
352 x
->link
[0] = w
->link
[1];
354 y
->link
[1] = w
->link
[0];
361 else if (w
->balance
== 0)
363 x
->balance
= y
->balance
= 0;
365 else /* |w->pavl_balance == -1| */
371 w
->parent
= y
->parent
;
372 x
->parent
= y
->parent
= w
;
373 if (x
->link
[0] != NULL
)
375 x
->link
[0]->parent
= x
;
377 if (y
->link
[1] != NULL
)
379 y
->link
[1]->parent
= y
;
387 if (w
->parent
!= NULL
)
389 w
->parent
->link
[y
!= w
->parent
->link
[0]] = w
;
399 void avl_remove (PNODE
*root
, PNODE item
, int (*compare
)(PNODE
, PNODE
))
401 PNODE p
; /* Traverses tree to find node to delete. */
402 PNODE q
; /* Parent of |p|. */
403 int dir
; /* Side of |q| on which |p| is linked. */
405 if (root
== NULL
|| *root
== NULL
)
419 dir
= compare(p
, q
) > 0;
422 if (p
->link
[1] == NULL
)
424 q
->link
[dir
] = p
->link
[0];
425 if (q
->link
[dir
] != NULL
)
427 q
->link
[dir
]->parent
= p
->parent
;
432 PNODE r
= p
->link
[1];
433 if (r
->link
[0] == NULL
)
435 r
->link
[0] = p
->link
[0];
437 r
->parent
= p
->parent
;
438 if (r
->link
[0] != NULL
)
440 r
->link
[0]->parent
= r
;
442 r
->balance
= p
->balance
;
448 PNODE s
= r
->link
[0];
449 while (s
->link
[0] != NULL
)
454 r
->link
[0] = s
->link
[1];
455 s
->link
[0] = p
->link
[0];
456 s
->link
[1] = p
->link
[1];
458 if (s
->link
[0] != NULL
)
460 s
->link
[0]->parent
= s
;
462 s
->link
[1]->parent
= s
;
463 s
->parent
= p
->parent
;
464 if (r
->link
[0] != NULL
)
466 r
->link
[0]->parent
= r
;
468 s
->balance
= p
->balance
;
474 item
->link
[0] = item
->link
[1] = item
->parent
= NULL
;
477 while (q
!= (PNODE
) root
)
481 if (y
->parent
!= NULL
)
492 dir
= q
->link
[0] != y
;
494 if (y
->balance
== +1)
498 else if (y
->balance
== +2)
500 PNODE x
= y
->link
[1];
501 if (x
->balance
== -1)
505 assert (x
->balance
== -1);
507 x
->link
[0] = w
->link
[1];
509 y
->link
[1] = w
->link
[0];
511 if (w
->balance
== +1)
516 else if (w
->balance
== 0)
518 x
->balance
= y
->balance
= 0;
520 else /* |w->pavl_balance == -1| */
526 w
->parent
= y
->parent
;
527 x
->parent
= y
->parent
= w
;
528 if (x
->link
[0] != NULL
)
530 x
->link
[0]->parent
= x
;
532 if (y
->link
[1] != NULL
)
534 y
->link
[1]->parent
= y
;
540 y
->link
[1] = x
->link
[0];
542 x
->parent
= y
->parent
;
544 if (y
->link
[1] != NULL
)
546 y
->link
[1]->parent
= y
;
557 x
->balance
= y
->balance
= 0;
565 dir
= q
->link
[0] != y
;
567 if (y
->balance
== -1)
571 else if (y
->balance
== -2)
573 PNODE x
= y
->link
[0];
574 if (x
->balance
== +1)
577 assert (x
->balance
== +1);
579 x
->link
[1] = w
->link
[0];
581 y
->link
[0] = w
->link
[1];
583 if (w
->balance
== -1)
588 else if (w
->balance
== 0)
590 x
->balance
= y
->balance
= 0;
592 else /* |w->pavl_balance == +1| */
598 w
->parent
= y
->parent
;
599 x
->parent
= y
->parent
= w
;
600 if (x
->link
[1] != NULL
)
602 x
->link
[1]->parent
= x
;
604 if (y
->link
[0] != NULL
)
606 y
->link
[0]->parent
= y
;
612 y
->link
[0] = x
->link
[1];
614 x
->parent
= y
->parent
;
616 if (y
->link
[0] != NULL
)
618 y
->link
[0]->parent
= y
;
629 x
->balance
= y
->balance
= 0;
639 PNODE
avl_get_next(PNODE root
, PNODE p
)
654 while (q
&& q
->link
[1] == p
)
670 PNODE
avl_find_equal_or_greater(PNODE root
, ULONG size
, int (compare
)(PVOID
, PNODE
))
676 for (p
= root
; p
!= NULL
;)
678 cmp
= compare((PVOID
)&size
, p
);
692 cmp
= compare((PVOID
)&size
, p
->link
[0]);
705 /* non paged pool functions ************************************************/
707 #ifdef TAG_STATISTICS_TRACKING
709 MiRemoveFromTagHashTable(BLOCK_HDR
* block
)
711 * Remove a block from the tag hash table
719 RemoveEntryList(&block
->TagListEntry
);
723 MiAddToTagHashTable(BLOCK_HDR
* block
)
725 * Add a block to the tag hash table
735 hash
= block
->Tag
% TAG_HASH_TABLE_SIZE
;
737 InsertHeadList(&tag_hash_table
[hash
], &block
->TagListEntry
);
739 #endif /* TAG_STATISTICS_TRACKING */
742 MiInitializeNonPagedPool(VOID
)
744 #ifdef TAG_STATISTICS_TRACKING
746 for (i
= 0; i
< TAG_HASH_TABLE_SIZE
; i
++)
748 InitializeListHead(&tag_hash_table
[i
]);
751 MiCurrentNonPagedPoolLength
= 0;
752 KeInitializeSpinLock(&MmNpoolLock
);
753 InitializeListHead(&UsedBlockListHead
);
754 InitializeListHead(&AddressListHead
);
755 FreeBlockListRoot
= NULL
;
758 #ifdef TAG_STATISTICS_TRACKING
760 MiDumpTagStats(ULONG CurrentTag
, ULONG CurrentNrBlocks
, ULONG CurrentSize
)
764 c1
= (CurrentTag
>> 24) & 0xFF;
765 c2
= (CurrentTag
>> 16) & 0xFF;
766 c3
= (CurrentTag
>> 8) & 0xFF;
767 c4
= CurrentTag
& 0xFF;
769 if (isprint(c1
) && isprint(c2
) && isprint(c3
) && isprint(c4
))
771 DbgPrint("Tag %x (%c%c%c%c) Blocks %d Total Size %d Average Size %d\n",
772 CurrentTag
, c4
, c3
, c2
, c1
, CurrentNrBlocks
,
773 CurrentSize
, CurrentSize
/ CurrentNrBlocks
);
777 DbgPrint("Tag %x Blocks %d Total Size %d Average Size %d\n",
778 CurrentTag
, CurrentNrBlocks
, CurrentSize
,
779 CurrentSize
/ CurrentNrBlocks
);
782 #endif /* TAG_STATISTICS_TRACKING */
785 MiDebugDumpNonPagedPoolStats(BOOLEAN NewOnly
)
787 #ifdef TAG_STATISTICS_TRACKING
791 ULONG CurrentNrBlocks
;
795 LIST_ENTRY tmpListHead
;
796 PLIST_ENTRY current_entry
;
798 DbgPrint("******* Dumping non paging pool stats ******\n");
801 for (i
= 0; i
< TAG_HASH_TABLE_SIZE
; i
++)
803 InitializeListHead(&tmpListHead
);
805 while (!IsListEmpty(&tag_hash_table
[i
]))
809 current_entry
= tag_hash_table
[i
].Flink
;
810 while (current_entry
!= &tag_hash_table
[i
])
812 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, TagListEntry
);
813 current_entry
= current_entry
->Flink
;
816 CurrentTag
= current
->Tag
;
820 if (current
->Tag
== CurrentTag
)
822 RemoveEntryList(¤t
->TagListEntry
);
823 InsertHeadList(&tmpListHead
, ¤t
->TagListEntry
);
824 if (!NewOnly
|| !current
->Dumped
)
828 CurrentSize
+= current
->Size
;
829 TotalSize
+= current
->Size
;
830 current
->Dumped
= TRUE
;
834 if (CurrentTag
!= 0 && CurrentNrBlocks
!= 0)
836 MiDumpTagStats(CurrentTag
, CurrentNrBlocks
, CurrentSize
);
839 if (!IsListEmpty(&tmpListHead
))
841 tag_hash_table
[i
].Flink
= tmpListHead
.Flink
;
842 tag_hash_table
[i
].Flink
->Blink
= &tag_hash_table
[i
];
843 tag_hash_table
[i
].Blink
= tmpListHead
.Blink
;
844 tag_hash_table
[i
].Blink
->Flink
= &tag_hash_table
[i
];
847 if (TotalBlocks
!= 0)
849 DbgPrint("TotalBlocks %d TotalSize %d AverageSize %d\n",
850 TotalBlocks
, TotalSize
, TotalSize
/ TotalBlocks
);
854 DbgPrint("TotalBlocks %d TotalSize %d\n",
855 TotalBlocks
, TotalSize
);
857 DbgPrint("Freeblocks %d TotalFreeSize %d AverageFreeSize %d\n",
858 EiNrFreeBlocks
, EiFreeNonPagedPool
, EiNrFreeBlocks
? EiFreeNonPagedPool
/ EiNrFreeBlocks
: 0);
859 DbgPrint("***************** Dump Complete ***************\n");
860 #endif /* TAG_STATISTICS_TRACKING */
864 MiDebugDumpNonPagedPool(BOOLEAN NewOnly
)
867 PLIST_ENTRY current_entry
;
870 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
872 DbgPrint("******* Dumping non paging pool contents ******\n");
873 current_entry
= UsedBlockListHead
.Flink
;
874 while (current_entry
!= &UsedBlockListHead
)
876 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, ListEntry
);
877 if (!NewOnly
|| !current
->Dumped
)
881 c1
= (current
->Tag
>> 24) & 0xFF;
882 c2
= (current
->Tag
>> 16) & 0xFF;
883 c3
= (current
->Tag
>> 8) & 0xFF;
884 c4
= current
->Tag
& 0xFF;
886 if (isprint(c1
) && isprint(c2
) && isprint(c3
) && isprint(c4
))
888 DbgPrint("Size 0x%x Tag 0x%x (%c%c%c%c) Allocator 0x%x\n",
889 current
->Size
, current
->Tag
, c4
, c3
, c2
, c1
,
894 DbgPrint("Size 0x%x Tag 0x%x Allocator 0x%x\n",
895 current
->Size
, current
->Tag
, current
->Caller
);
897 current
->Dumped
= TRUE
;
899 current_entry
= current_entry
->Flink
;
901 DbgPrint("***************** Dump Complete ***************\n");
902 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
905 #ifndef WHOLE_PAGE_ALLOCATIONS
907 #ifdef ENABLE_VALIDATE_POOL
908 static void validate_free_list(void)
910 * FUNCTION: Validate the integrity of the list of free blocks
914 PLIST_ENTRY current_entry
;
915 unsigned int blocks_seen
=0;
917 current_entry
= MiFreeBlockListHead
.Flink
;
918 while (current_entry
!= &MiFreeBlockListHead
)
922 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, ListEntry
);
923 base_addr
= (PVOID
)current
;
925 if (current
->Magic
!= BLOCK_HDR_FREE_MAGIC
)
927 DbgPrint("Bad block magic (probable pool corruption) at %x\n",
929 KeBugCheck(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
932 if (base_addr
< MiNonPagedPoolStart
||
933 MiNonPagedPoolStart
+ current
->Size
> MiNonPagedPoolStart
+ MiCurrentNonPagedPoolLength
)
935 DbgPrint("Block %x found outside pool area\n",current
);
936 DbgPrint("Size %d\n",current
->Size
);
937 DbgPrint("Limits are %x %x\n",MiNonPagedPoolStart
,
938 MiNonPagedPoolStart
+MiCurrentNonPagedPoolLength
);
939 KeBugCheck(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
942 if (blocks_seen
> MiNrFreeBlocks
)
944 DbgPrint("Too many blocks on free list\n");
945 KeBugCheck(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
947 if (current
->ListEntry
.Flink
!= &MiFreeBlockListHead
&&
948 current
->ListEntry
.Flink
->Blink
!= ¤t
->ListEntry
)
950 DbgPrint("%s:%d:Break in list (current %x next %x "
951 "current->next->previous %x)\n",
952 __FILE__
,__LINE__
,current
, current
->ListEntry
.Flink
,
953 current
->ListEntry
.Flink
->Blink
);
954 KeBugCheck(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
957 current_entry
= current_entry
->Flink
;
961 static void validate_used_list(void)
963 * FUNCTION: Validate the integrity of the list of used blocks
967 PLIST_ENTRY current_entry
;
968 unsigned int blocks_seen
=0;
970 current_entry
= UsedBlockListHead
.Flink
;
971 while (current_entry
!= &UsedBlockListHead
)
975 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, ListEntry
);
976 base_addr
= (PVOID
)current
;
978 if (current
->Magic
!= BLOCK_HDR_USED_MAGIC
)
980 DbgPrint("Bad block magic (probable pool corruption) at %x\n",
982 KeBugCheck(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
984 if (base_addr
< MiNonPagedPoolStart
||
985 (base_addr
+current
->Size
) >
986 MiNonPagedPoolStart
+MiCurrentNonPagedPoolLength
)
988 DbgPrint("Block %x found outside pool area\n",current
);
992 if (blocks_seen
> EiNrUsedBlocks
)
994 DbgPrint("Too many blocks on used list\n");
997 if (current
->ListEntry
.Flink
!= &UsedBlockListHead
&&
998 current
->ListEntry
.Flink
->Blink
!= ¤t
->ListEntry
)
1000 DbgPrint("Break in list (current %x next %x)\n",
1001 current
, current
->ListEntry
.Flink
);
1005 current_entry
= current_entry
->Flink
;
1009 static void check_duplicates(BLOCK_HDR
* blk
)
1011 * FUNCTION: Check a block has no duplicates
1013 * blk = block to check
1014 * NOTE: Bug checks if duplicates are found
1017 unsigned int base
= (int)blk
;
1018 unsigned int last
= ((int)blk
) + +sizeof(BLOCK_HDR
) + blk
->Size
;
1020 PLIST_ENTRY current_entry
;
1022 current_entry
= MiFreeBlockListHead
.Flink
;
1023 while (current_entry
!= &MiFreeBlockListHead
)
1025 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, ListEntry
);
1027 if (current
->Magic
!= BLOCK_HDR_FREE_MAGIC
)
1029 DbgPrint("Bad block magic (probable pool corruption) at %x\n",
1031 KeBugCheck(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1034 if ( (int)current
> base
&& (int)current
< last
)
1036 DbgPrint("intersecting blocks on list\n");
1039 if ( (int)current
< base
&&
1040 ((int)current
+ current
->Size
+ sizeof(BLOCK_HDR
))
1043 DbgPrint("intersecting blocks on list\n");
1047 current_entry
= current_entry
->Flink
;
1050 current_entry
= UsedBlockListHead
.Flink
;
1051 while (current_entry
!= &UsedBlockListHead
)
1053 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, ListEntry
);
1055 if ( (int)current
> base
&& (int)current
< last
)
1057 DbgPrint("intersecting blocks on list\n");
1060 if ( (int)current
< base
&&
1061 ((int)current
+ current
->Size
+ sizeof(BLOCK_HDR
))
1064 DbgPrint("intersecting blocks on list\n");
1068 current_entry
= current_entry
->Flink
;
1073 static void validate_kernel_pool(void)
1075 * FUNCTION: Checks the integrity of the kernel memory heap
1079 PLIST_ENTRY current_entry
;
1081 validate_free_list();
1082 validate_used_list();
1084 current_entry
= MiFreeBlockListHead
.Flink
;
1085 while (current_entry
!= &MiFreeBlockListHead
)
1087 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, ListEntry
);
1088 check_duplicates(current
);
1089 current_entry
= current_entry
->Flink
;
1091 current_entry
= UsedBlockListHead
.Flink
;
1092 while (current_entry
!= &UsedBlockListHead
)
1094 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, ListEntry
);
1095 check_duplicates(current
);
1096 current_entry
= current_entry
->Flink
;
1103 free_pages(BLOCK_HDR
* blk
)
1110 end
= (ULONG
)blk
+ sizeof(BLOCK_HDR
) + blk
->Size
;
1113 * If the block doesn't contain a whole page then there is nothing to do
1115 if (PAGE_ROUND_UP(start
) >= PAGE_ROUND_DOWN(end
))
1122 static void remove_from_used_list(BLOCK_HDR
* current
)
1124 RemoveEntryList(¤t
->ListEntry
);
1125 EiUsedNonPagedPool
-= current
->Size
;
1129 static void remove_from_free_list(BLOCK_HDR
* current
)
1131 DPRINT("remove_from_free_list %d\n", current
->Size
);
1133 avl_remove(&FreeBlockListRoot
, ¤t
->Node
, compare_node
);
1135 EiFreeNonPagedPool
-= current
->Size
;
1137 DPRINT("remove_from_free_list done\n");
1139 DumpFreeBlockTree();
1144 add_to_free_list(BLOCK_HDR
* blk
)
1146 * FUNCTION: add the block to the free list (internal)
1151 DPRINT("add_to_free_list (%d)\n", blk
->Size
);
1155 if (blk
->AddressList
.Blink
!= &AddressListHead
)
1157 current
= CONTAINING_RECORD(blk
->AddressList
.Blink
, BLOCK_HDR
, AddressList
);
1158 if (current
->Magic
== BLOCK_HDR_FREE_MAGIC
&&
1159 (PVOID
)current
+ current
->Size
+ sizeof(BLOCK_HDR
) == (PVOID
)blk
)
1162 remove_from_free_list(current
);
1163 RemoveEntryList(&blk
->AddressList
);
1164 current
->Size
= current
->Size
+ sizeof(BLOCK_HDR
) + blk
->Size
;
1165 current
->Magic
= BLOCK_HDR_USED_MAGIC
;
1166 memset(blk
, 0xcc, sizeof(BLOCK_HDR
));
1171 if (blk
->AddressList
.Flink
!= &AddressListHead
)
1173 current
= CONTAINING_RECORD(blk
->AddressList
.Flink
, BLOCK_HDR
, AddressList
);
1174 if (current
->Magic
== BLOCK_HDR_FREE_MAGIC
&&
1175 (PVOID
)blk
+ blk
->Size
+ sizeof(BLOCK_HDR
) == (PVOID
)current
)
1178 remove_from_free_list(current
);
1179 RemoveEntryList(¤t
->AddressList
);
1180 blk
->Size
= blk
->Size
+ sizeof(BLOCK_HDR
) + current
->Size
;
1181 memset(current
, 0xcc, sizeof(BLOCK_HDR
));
1185 DPRINT("%d\n", blk
->Size
);
1186 blk
->Magic
= BLOCK_HDR_FREE_MAGIC
;
1187 EiFreeNonPagedPool
+= blk
->Size
;
1188 avl_insert(&FreeBlockListRoot
, &blk
->Node
, compare_node
);
1190 DPRINT("add_to_free_list done\n");
1192 DumpFreeBlockTree();
1196 static void add_to_used_list(BLOCK_HDR
* blk
)
1198 * FUNCTION: add the block to the used list (internal)
1201 InsertHeadList(&UsedBlockListHead
, &blk
->ListEntry
);
1202 EiUsedNonPagedPool
+= blk
->Size
;
1206 inline static void* block_to_address(BLOCK_HDR
* blk
)
1208 * FUNCTION: Translate a block header address to the corresponding block
1209 * address (internal)
1212 return ( (void *) ((int)blk
+ sizeof(BLOCK_HDR
)) );
1215 inline static BLOCK_HDR
* address_to_block(void* addr
)
1217 return (BLOCK_HDR
*)
1218 ( ((int)addr
) - sizeof(BLOCK_HDR
) );
1221 static BLOCK_HDR
* lookup_block(unsigned int size
)
1224 BLOCK_HDR
* best
= NULL
;
1226 PVOID block
, block_boundary
;
1229 DPRINT("lookup_block %d\n", size
);
1231 if (size
< PAGE_SIZE
)
1233 p
= avl_find_equal_or_greater(FreeBlockListRoot
, size
, compare_value
);
1236 best
= CONTAINING_RECORD(p
, BLOCK_HDR
, Node
);
1241 p
= avl_find_equal_or_greater(FreeBlockListRoot
, size
, compare_value
);
1245 current
= CONTAINING_RECORD(p
, BLOCK_HDR
, Node
);
1246 block
= block_to_address(current
);
1247 block_boundary
= (PVOID
)PAGE_ROUND_UP((ULONG
)block
);
1248 new_size
= (ULONG
)block_boundary
- (ULONG
)block
+ size
;
1249 if (new_size
!= size
&& (ULONG
)block_boundary
- (ULONG
)block
< sizeof(BLOCK_HDR
))
1251 new_size
+= PAGE_SIZE
;
1253 if (current
->Size
>= new_size
&&
1254 (best
== NULL
|| current
->Size
< best
->Size
))
1258 if (best
&& current
->Size
>= size
+ PAGE_SIZE
+ 2 * sizeof(BLOCK_HDR
))
1262 p
= avl_get_next(FreeBlockListRoot
, p
);
1266 DPRINT("lookup_block done %d\n", best
? best
->Size
: 0);
1270 static void* take_block(BLOCK_HDR
* current
, unsigned int size
,
1271 ULONG Tag
, PVOID Caller
)
1273 * FUNCTION: Allocate a used block of least 'size' from the specified
1275 * RETURNS: The address of the created memory block
1279 BOOL Removed
= FALSE
;
1281 DPRINT("take_block\n");
1283 if (size
>= PAGE_SIZE
)
1285 blk
= address_to_block((PVOID
)PAGE_ROUND_UP(block_to_address (current
)));
1288 if ((ULONG
)blk
- (ULONG
)current
< sizeof(BLOCK_HDR
))
1290 (ULONG
)blk
+= PAGE_SIZE
;
1292 assert((ULONG
)blk
- (ULONG
)current
+ size
<= current
->Size
&& (ULONG
)blk
- (ULONG
)current
>= sizeof(BLOCK_HDR
));
1294 memset(blk
, 0, sizeof(BLOCK_HDR
));
1295 blk
->Magic
= BLOCK_HDR_USED_MAGIC
;
1296 blk
->Size
= current
->Size
- ((ULONG
)blk
- (ULONG
)current
);
1297 remove_from_free_list(current
);
1298 current
->Size
-= (blk
->Size
+ sizeof(BLOCK_HDR
));
1299 blk
->AddressList
.Flink
= current
->AddressList
.Flink
;
1300 blk
->AddressList
.Flink
->Blink
= &blk
->AddressList
;
1301 blk
->AddressList
.Blink
= ¤t
->AddressList
;
1302 current
->AddressList
.Flink
= &blk
->AddressList
;
1303 add_to_free_list(current
);
1308 if (Removed
== FALSE
)
1310 remove_from_free_list(current
);
1314 * If the block is much bigger than required then split it and
1315 * return a pointer to the allocated section. If the difference
1316 * between the sizes is marginal it makes no sense to have the
1319 if (current
->Size
> size
+ sizeof(BLOCK_HDR
))
1321 BLOCK_HDR
* free_blk
;
1324 * Replace the bigger block with a smaller block in the
1325 * same position in the list
1327 free_blk
= (BLOCK_HDR
*)(((int)current
)
1328 + sizeof(BLOCK_HDR
) + size
);
1330 free_blk
->Size
= current
->Size
- (sizeof(BLOCK_HDR
) + size
);
1332 free_blk
->AddressList
.Flink
= current
->AddressList
.Flink
;
1333 free_blk
->AddressList
.Flink
->Blink
= &free_blk
->AddressList
;
1334 free_blk
->AddressList
.Blink
= ¤t
->AddressList
;
1335 current
->AddressList
.Flink
= &free_blk
->AddressList
;
1336 current
->Magic
= BLOCK_HDR_USED_MAGIC
;
1337 free_blk
->Magic
= BLOCK_HDR_FREE_MAGIC
;
1338 add_to_free_list(free_blk
);
1339 add_to_used_list(current
);
1341 current
->Caller
= Caller
;
1342 current
->Dumped
= FALSE
;
1343 #ifdef TAG_STATISTICS_TRACKING
1344 MiAddToTagHashTable(current
);
1345 #endif /* TAG_STATISTICS_TRACKING */
1347 return(block_to_address(current
));
1351 * Otherwise allocate the whole block
1354 current
->Magic
= BLOCK_HDR_USED_MAGIC
;
1356 current
->Caller
= Caller
;
1357 current
->Dumped
= FALSE
;
1358 add_to_used_list(current
);
1359 #ifdef TAG_STATISTICS_TRACKING
1360 MiAddToTagHashTable(current
);
1361 #endif /* TAG_STATISTICS_TRACKING */
1364 return(block_to_address(current
));
1367 static void* grow_kernel_pool(unsigned int size
, ULONG Tag
, PVOID Caller
)
1369 * FUNCTION: Grow the executive heap to accomodate a block of at least 'size'
1373 ULONG nr_pages
= PAGE_ROUND_UP(size
+ sizeof(BLOCK_HDR
)) / PAGE_SIZE
;
1375 BLOCK_HDR
* blk
=NULL
;
1381 PLIST_ENTRY current_entry
;
1383 if (size
>= PAGE_SIZE
)
1388 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1389 start
= (ULONG
)MiNonPagedPoolStart
+ MiCurrentNonPagedPoolLength
;
1390 if (MiCurrentNonPagedPoolLength
+ nr_pages
* PAGE_SIZE
> MiNonPagedPoolLength
)
1392 DbgPrint("CRITICAL: Out of non-paged pool space\n");
1395 MiCurrentNonPagedPoolLength
+= nr_pages
* PAGE_SIZE
;
1396 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1398 DPRINT("growing heap for block size %d, ",size
);
1399 DPRINT("start %x\n",start
);
1401 for (i
=0;i
<nr_pages
;i
++)
1403 PHYSICAL_ADDRESS Page
;
1404 /* FIXME: Check whether we can really wait here. */
1405 Status
= MmRequestPageMemoryConsumer(MC_NPPOOL
, TRUE
, &Page
);
1406 if (!NT_SUCCESS(Status
))
1411 Status
= MmCreateVirtualMapping(NULL
,
1412 (PVOID
)(start
+ (i
*PAGE_SIZE
)),
1413 PAGE_READWRITE
|PAGE_SYSTEM
,
1416 if (!NT_SUCCESS(Status
))
1418 DbgPrint("Unable to create virtual mapping\n");
1423 blk
= (struct _BLOCK_HDR
*)start
;
1424 memset(blk
, 0, sizeof(BLOCK_HDR
));
1425 blk
->Size
= (nr_pages
* PAGE_SIZE
) - sizeof(BLOCK_HDR
);
1426 memset(block_to_address(blk
), 0xcc, blk
->Size
);
1428 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1429 current_entry
= AddressListHead
.Blink
;
1430 while (current_entry
!= &AddressListHead
)
1432 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, AddressList
);
1433 if ((PVOID
)current
+ current
->Size
< (PVOID
)blk
)
1435 InsertHeadList(current_entry
, &blk
->AddressList
);
1438 current_entry
= current_entry
->Blink
;
1440 if (current_entry
== &AddressListHead
)
1442 InsertHeadList(&AddressListHead
, &blk
->AddressList
);
1444 blk
->Magic
= BLOCK_HDR_FREE_MAGIC
;
1445 add_to_free_list(blk
);
1446 blk
= lookup_block(size
);
1449 block
= take_block(blk
, size
, Tag
, Caller
);
1452 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1456 #endif /* not WHOLE_PAGE_ALLOCATIONS */
1461 VOID STDCALL
ExFreeNonPagedPool (PVOID block
)
1463 * FUNCTION: Releases previously allocated memory
1465 * block = block to free
1468 #ifdef WHOLE_PAGE_ALLOCATIONS /* WHOLE_PAGE_ALLOCATIONS */
1476 DPRINT("freeing block %x\n",blk
);
1478 POOL_TRACE("ExFreePool(block %x), size %d, caller %x\n",block
,blk
->size
,
1479 ((PULONG
)&block
)[-1]);
1481 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1483 ExFreeWholePageBlock(block
);
1484 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1486 #else /* not WHOLE_PAGE_ALLOCATIONS */
1488 BLOCK_HDR
* blk
=address_to_block(block
);
1496 DPRINT("freeing block %x\n",blk
);
1498 POOL_TRACE("ExFreePool(block %x), size %d, caller %x\n",block
,blk
->size
,
1499 ((PULONG
)&block
)[-1]);
1501 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1505 if (blk
->Magic
!= BLOCK_HDR_USED_MAGIC
)
1507 if (blk
->Magic
== BLOCK_HDR_FREE_MAGIC
)
1509 DbgPrint("ExFreePool of already freed address %x\n", block
);
1513 DbgPrint("ExFreePool of non-allocated address %x (magic %x)\n",
1520 memset(block
, 0xcc, blk
->Size
);
1522 #ifdef TAG_STATISTICS_TRACKING
1523 MiRemoveFromTagHashTable(blk
);
1524 #endif /* TAG_STATISTICS_TRACKING */
1525 remove_from_used_list(blk
);
1528 blk
->TagListEntry
.Flink
= blk
->TagListEntry
.Blink
= NULL
;
1529 blk
->Magic
= BLOCK_HDR_FREE_MAGIC
;
1530 add_to_free_list(blk
);
1532 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1534 #endif /* WHOLE_PAGE_ALLOCATIONS */
1541 ExAllocateNonPagedPoolWithTag(ULONG Type
, ULONG Size
, ULONG Tag
, PVOID Caller
)
1543 #ifdef WHOLE_PAGE_ALLOCATIONS
1547 POOL_TRACE("ExAllocatePool(NumberOfBytes %d) caller %x ",
1550 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1553 * accomodate this useful idiom
1557 POOL_TRACE("= NULL\n");
1558 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1562 block
= ExAllocateWholePageBlock(Size
);
1563 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1566 #else /* not WHOLE_PAGE_ALLOCATIONS */
1568 BLOCK_HDR
* best
= NULL
;
1571 POOL_TRACE("ExAllocatePool(NumberOfBytes %d) caller %x ",
1574 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1579 /* after some allocations print the npaged pool stats */
1580 #ifdef TAG_STATISTICS_TRACKING
1582 static ULONG counter
= 0;
1583 if (counter
++ % 100000 == 0)
1585 MiDebugDumpNonPagedPoolStats(FALSE
);
1591 * accomodate this useful idiom
1595 POOL_TRACE("= NULL\n");
1596 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1599 /* Make the size dword alligned, this makes the block dword alligned */
1600 Size
= ROUND_UP(Size
, 4);
1602 * Look for an already created block of sufficent size
1604 best
= lookup_block(Size
);
1607 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1608 block
= grow_kernel_pool(Size
, Tag
, Caller
);
1611 DPRINT1("%d\n", Size
);
1612 DumpFreeBlockTree();
1614 assert(block
!= NULL
);
1615 memset(block
,0,Size
);
1619 block
=take_block(best
, Size
, Tag
, Caller
);
1621 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1622 memset(block
,0,Size
);
1625 #endif /* WHOLE_PAGE_ALLOCATIONS */
1628 #ifdef WHOLE_PAGE_ALLOCATIONS
1634 ExAllocateWholePageBlock(ULONG UserSize
)
1637 PHYSICAL_ADDRESS Page
;
1642 Size
= sizeof(ULONG
) + UserSize
;
1643 NrPages
= ROUND_UP(Size
, PAGE_SIZE
) / PAGE_SIZE
;
1645 Address
= MiAllocNonPagedPoolRegion(NrPages
+ 1);
1647 for (i
= 0; i
< NrPages
; i
++)
1649 Page
= MmAllocPage(MC_NPPOOL
, 0);
1650 if (Page
.QuadPart
== 0LL)
1654 MmCreateVirtualMapping(NULL
,
1655 Address
+ (i
* PAGE_SIZE
),
1656 PAGE_READWRITE
| PAGE_SYSTEM
,
1661 *((PULONG
)((ULONG
)Address
+ (NrPages
* PAGE_SIZE
) - Size
)) = NrPages
;
1662 return((PVOID
)((ULONG
)Address
+ (NrPages
* PAGE_SIZE
) - UserSize
));
1669 ExFreeWholePageBlock(PVOID Addr
)
1673 if (Addr
< MiNonPagedPoolStart
||
1674 Addr
>= (MiNonPagedPoolStart
+ MiCurrentNonPagedPoolLength
))
1676 DbgPrint("Block %x found outside pool area\n", Addr
);
1679 NrPages
= *(PULONG
)((ULONG
)Addr
- sizeof(ULONG
));
1680 MiFreeNonPagedPoolRegion((PVOID
)PAGE_ROUND_DOWN((ULONG
)Addr
), NrPages
, TRUE
);
1683 #endif /* WHOLE_PAGE_ALLOCATIONS */