1 /* $Id: npool.c,v 1.89 2004/08/15 16:39:08 chorns 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 ****************************************************************/
21 #include <internal/debug.h>
23 /* Enable strict checking of the nonpaged pool on every allocation */
24 /*#define ENABLE_VALIDATE_POOL*/
26 /* Enable tracking of statistics about the tagged blocks in the pool */
27 #define TAG_STATISTICS_TRACKING
30 * Put each block in its own range of pages and position the block at the
31 * end of the range so any accesses beyond the end of block are to invalid
34 /*#define WHOLE_PAGE_ALLOCATIONS*/
36 #ifdef ENABLE_VALIDATE_POOL
37 #define VALIDATE_POOL validate_kernel_pool()
43 #define POOL_TRACE(args...) do { DbgPrint(args); } while(0);
46 #define POOL_TRACE(args...)
52 /* avl types ****************************************************************/
55 * This declarations should be moved into a separate header file.
60 struct _NODE
* link
[2];
66 /* TYPES *******************************************************************/
68 #define BLOCK_HDR_USED_MAGIC (0xdeadbeef)
69 #define BLOCK_HDR_FREE_MAGIC (0xceadbeef)
72 * fields present at the start of a block (this is for internal use only)
74 typedef struct _BLOCK_HDR
78 struct _BLOCK_HDR
* previous
;
86 LIST_ENTRY TagListEntry
;
99 #define BLOCK_HDR_SIZE ROUND_UP(sizeof(BLOCK_HDR), MM_POOL_ALIGNMENT)
102 ExAllocateWholePageBlock(ULONG Size
);
104 ExFreeWholePageBlock(PVOID Addr
);
106 /* GLOBALS *****************************************************************/
108 extern PVOID MiNonPagedPoolStart
;
109 extern ULONG MiNonPagedPoolLength
;
112 * Head of the list of free blocks
114 static PNODE FreeBlockListRoot
= NULL
;
117 * Head of the list of in use block
119 static LIST_ENTRY UsedBlockListHead
;
121 static LIST_ENTRY AddressListHead
;
123 #ifndef WHOLE_PAGE_ALLOCATIONS
125 * Count of free blocks
127 static ULONG EiNrFreeBlocks
= 0;
130 * Count of used blocks
132 static ULONG EiNrUsedBlocks
= 0;
136 * Lock that protects the non-paged pool data structures
138 static KSPIN_LOCK MmNpoolLock
;
141 * Total memory used for free nonpaged pool blocks
143 ULONG EiFreeNonPagedPool
= 0;
146 * Total memory used for nonpaged pool blocks
148 ULONG EiUsedNonPagedPool
= 0;
150 /* Total quota for Non Paged Pool */
151 ULONG MmTotalNonPagedPoolQuota
= 0;
154 * Allocate a range of memory in the nonpaged pool
157 MiAllocNonPagedPoolRegion(unsigned int nr_pages
);
160 MiFreeNonPagedPoolRegion(PVOID Addr
, ULONG Count
, BOOLEAN Free
);
162 #ifdef TAG_STATISTICS_TRACKING
163 #define TAG_HASH_TABLE_SIZE (1024)
164 static LIST_ENTRY tag_hash_table
[TAG_HASH_TABLE_SIZE
];
165 #endif /* TAG_STATISTICS_TRACKING */
167 #ifdef WHOLE_PAGE_ALLOCATIONS
168 static RTL_BITMAP NonPagedPoolAllocMap
;
169 static ULONG NonPagedPoolAllocMapHint
;
170 static ULONG MiCurrentNonPagedPoolLength
= 0;
172 static PULONG MiNonPagedPoolAllocMap
;
173 static ULONG MiNonPagedPoolNrOfPages
;
174 #endif /* WHOLE_PAGE_ALLOCATIONS */
176 /* avl helper functions ****************************************************/
178 void DumpFreeBlockNode(PNODE p
)
180 static int count
= 0;
187 DumpFreeBlockNode(p
->link
[0]);
188 blk
= CONTAINING_RECORD(p
, BLOCK_HDR
, Free
.Node
);
189 DbgPrint("%08x %8d (%d)\n", blk
, blk
->Size
, count
);
190 DumpFreeBlockNode(p
->link
[1]);
195 void DumpFreeBlockTree(void)
197 DbgPrint("--- Begin tree ------------------\n");
198 DbgPrint("%08x\n", CONTAINING_RECORD(FreeBlockListRoot
, BLOCK_HDR
, Free
.Node
));
199 DumpFreeBlockNode(FreeBlockListRoot
);
200 DbgPrint("--- End tree --------------------\n");
203 int compare_node(PNODE p1
, PNODE p2
)
205 BLOCK_HDR
* blk1
= CONTAINING_RECORD(p1
, BLOCK_HDR
, Free
.Node
);
206 BLOCK_HDR
* blk2
= CONTAINING_RECORD(p2
, BLOCK_HDR
, Free
.Node
);
208 if (blk1
->Size
== blk2
->Size
)
221 if (blk1
->Size
< blk2
->Size
)
225 if (blk1
->Size
> blk2
->Size
)
234 int compare_value(PVOID value
, PNODE p
)
236 BLOCK_HDR
* blk
= CONTAINING_RECORD(p
, BLOCK_HDR
, Free
.Node
);
237 ULONG v
= *(PULONG
)value
;
250 /* avl functions **********************************************************/
253 * The avl functions should be moved into a separate file.
256 /* The avl_insert and avl_remove are based on libavl (library for manipulation of binary trees). */
258 void avl_insert (PNODE
* root
, PNODE n
, int (*compare
)(PNODE
, PNODE
))
260 PNODE y
; /* Top node to update balance factor, and parent. */
261 PNODE p
, q
; /* Iterator, and parent. */
262 PNODE w
; /* New root of rebalanced subtree. */
263 int dir
= 0; /* Direction to descend. */
265 n
->link
[0] = n
->link
[1] = n
->parent
= NULL
;
269 for (q
= NULL
, p
= *root
; p
!= NULL
; q
= p
, p
= p
->link
[dir
])
271 dir
= compare(n
, p
) > 0;
293 for (p
= n
; p
!= y
; p
= q
)
296 dir
= q
->link
[0] != p
;
307 if (y
->balance
== -2)
309 PNODE x
= y
->link
[0];
310 if (x
->balance
== -1)
313 y
->link
[0] = x
->link
[1];
315 x
->balance
= y
->balance
= 0;
316 x
->parent
= y
->parent
;
318 if (y
->link
[0] != NULL
)
320 y
->link
[0]->parent
= y
;
325 assert (x
->balance
== +1);
327 x
->link
[1] = w
->link
[0];
329 y
->link
[0] = w
->link
[1];
331 if (w
->balance
== -1)
336 else if (w
->balance
== 0)
338 x
->balance
= y
->balance
= 0;
340 else /* |w->pavl_balance == +1| */
346 w
->parent
= y
->parent
;
347 x
->parent
= y
->parent
= w
;
348 if (x
->link
[1] != NULL
)
350 x
->link
[1]->parent
= x
;
352 if (y
->link
[0] != NULL
)
354 y
->link
[0]->parent
= y
;
358 else if (y
->balance
== +2)
360 PNODE x
= y
->link
[1];
361 if (x
->balance
== +1)
364 y
->link
[1] = x
->link
[0];
366 x
->balance
= y
->balance
= 0;
367 x
->parent
= y
->parent
;
369 if (y
->link
[1] != NULL
)
371 y
->link
[1]->parent
= y
;
376 assert (x
->balance
== -1);
378 x
->link
[0] = w
->link
[1];
380 y
->link
[1] = w
->link
[0];
387 else if (w
->balance
== 0)
389 x
->balance
= y
->balance
= 0;
391 else /* |w->pavl_balance == -1| */
397 w
->parent
= y
->parent
;
398 x
->parent
= y
->parent
= w
;
399 if (x
->link
[0] != NULL
)
401 x
->link
[0]->parent
= x
;
403 if (y
->link
[1] != NULL
)
405 y
->link
[1]->parent
= y
;
413 if (w
->parent
!= NULL
)
415 w
->parent
->link
[y
!= w
->parent
->link
[0]] = w
;
425 void avl_remove (PNODE
*root
, PNODE item
, int (*compare
)(PNODE
, PNODE
))
427 PNODE p
; /* Traverses tree to find node to delete. */
428 PNODE q
; /* Parent of |p|. */
429 int dir
; /* Side of |q| on which |p| is linked. */
431 if (root
== NULL
|| *root
== NULL
)
445 dir
= compare(p
, q
) > 0;
448 if (p
->link
[1] == NULL
)
450 q
->link
[dir
] = p
->link
[0];
451 if (q
->link
[dir
] != NULL
)
453 q
->link
[dir
]->parent
= p
->parent
;
458 PNODE r
= p
->link
[1];
459 if (r
->link
[0] == NULL
)
461 r
->link
[0] = p
->link
[0];
463 r
->parent
= p
->parent
;
464 if (r
->link
[0] != NULL
)
466 r
->link
[0]->parent
= r
;
468 r
->balance
= p
->balance
;
474 PNODE s
= r
->link
[0];
475 while (s
->link
[0] != NULL
)
480 r
->link
[0] = s
->link
[1];
481 s
->link
[0] = p
->link
[0];
482 s
->link
[1] = p
->link
[1];
484 if (s
->link
[0] != NULL
)
486 s
->link
[0]->parent
= s
;
488 s
->link
[1]->parent
= s
;
489 s
->parent
= p
->parent
;
490 if (r
->link
[0] != NULL
)
492 r
->link
[0]->parent
= r
;
494 s
->balance
= p
->balance
;
500 item
->link
[0] = item
->link
[1] = item
->parent
= NULL
;
503 while (q
!= (PNODE
) root
)
507 if (y
->parent
!= NULL
)
518 dir
= q
->link
[0] != y
;
520 if (y
->balance
== +1)
524 else if (y
->balance
== +2)
526 PNODE x
= y
->link
[1];
527 if (x
->balance
== -1)
531 assert (x
->balance
== -1);
533 x
->link
[0] = w
->link
[1];
535 y
->link
[1] = w
->link
[0];
537 if (w
->balance
== +1)
542 else if (w
->balance
== 0)
544 x
->balance
= y
->balance
= 0;
546 else /* |w->pavl_balance == -1| */
552 w
->parent
= y
->parent
;
553 x
->parent
= y
->parent
= w
;
554 if (x
->link
[0] != NULL
)
556 x
->link
[0]->parent
= x
;
558 if (y
->link
[1] != NULL
)
560 y
->link
[1]->parent
= y
;
566 y
->link
[1] = x
->link
[0];
568 x
->parent
= y
->parent
;
570 if (y
->link
[1] != NULL
)
572 y
->link
[1]->parent
= y
;
583 x
->balance
= y
->balance
= 0;
591 dir
= q
->link
[0] != y
;
593 if (y
->balance
== -1)
597 else if (y
->balance
== -2)
599 PNODE x
= y
->link
[0];
600 if (x
->balance
== +1)
603 assert (x
->balance
== +1);
605 x
->link
[1] = w
->link
[0];
607 y
->link
[0] = w
->link
[1];
609 if (w
->balance
== -1)
614 else if (w
->balance
== 0)
616 x
->balance
= y
->balance
= 0;
618 else /* |w->pavl_balance == +1| */
624 w
->parent
= y
->parent
;
625 x
->parent
= y
->parent
= w
;
626 if (x
->link
[1] != NULL
)
628 x
->link
[1]->parent
= x
;
630 if (y
->link
[0] != NULL
)
632 y
->link
[0]->parent
= y
;
638 y
->link
[0] = x
->link
[1];
640 x
->parent
= y
->parent
;
642 if (y
->link
[0] != NULL
)
644 y
->link
[0]->parent
= y
;
655 x
->balance
= y
->balance
= 0;
665 PNODE _cdecl
avl_get_first(PNODE root
)
680 PNODE
avl_get_next(PNODE root
, PNODE p
)
695 while (q
&& q
->link
[1] == p
)
711 PNODE
avl_find_equal_or_greater(PNODE root
, ULONG size
, int (compare
)(PVOID
, PNODE
))
717 for (p
= root
; p
!= NULL
;)
719 cmp
= compare((PVOID
)&size
, p
);
733 cmp
= compare((PVOID
)&size
, p
->link
[0]);
746 /* non paged pool functions ************************************************/
748 #ifdef TAG_STATISTICS_TRACKING
750 MiRemoveFromTagHashTable(BLOCK_HDR
* block
)
752 * Remove a block from the tag hash table
755 if (block
->Used
.Tag
== 0)
760 RemoveEntryList(&block
->Used
.TagListEntry
);
764 MiAddToTagHashTable(BLOCK_HDR
* block
)
766 * Add a block to the tag hash table
771 if (block
->Used
.Tag
== 0)
776 hash
= block
->Used
.Tag
% TAG_HASH_TABLE_SIZE
;
778 InsertHeadList(&tag_hash_table
[hash
], &block
->Used
.TagListEntry
);
780 #endif /* TAG_STATISTICS_TRACKING */
782 #if defined(TAG_STATISTICS_TRACKING) && !defined(WHOLE_PAGE_ALLOCATIONS)
784 MiDumpTagStats(ULONG CurrentTag
, ULONG CurrentNrBlocks
, ULONG CurrentSize
)
788 c1
= (CHAR
)((CurrentTag
>> 24) & 0xFF);
789 c2
= (CHAR
)((CurrentTag
>> 16) & 0xFF);
790 c3
= (CHAR
)((CurrentTag
>> 8) & 0xFF);
791 c4
= (CHAR
)(CurrentTag
& 0xFF);
793 if (isprint(c1
) && isprint(c2
) && isprint(c3
) && isprint(c4
))
795 DbgPrint("Tag %x (%c%c%c%c) Blocks %d Total Size %d Average Size %d\n",
796 CurrentTag
, c4
, c3
, c2
, c1
, CurrentNrBlocks
,
797 CurrentSize
, CurrentSize
/ CurrentNrBlocks
);
801 DbgPrint("Tag %x Blocks %d Total Size %d Average Size %d\n",
802 CurrentTag
, CurrentNrBlocks
, CurrentSize
,
803 CurrentSize
/ CurrentNrBlocks
);
806 #endif /* defined(TAG_STATISTICS_TRACKING) && !defined(WHOLE_PAGE_ALLOCATIONS); */
809 MiDebugDumpNonPagedPoolStats(BOOLEAN NewOnly
)
811 #if defined(TAG_STATISTICS_TRACKING) && !defined(WHOLE_PAGE_ALLOCATIONS)
815 ULONG CurrentNrBlocks
= 0;
816 ULONG CurrentSize
= 0;
820 LIST_ENTRY tmpListHead
;
821 PLIST_ENTRY current_entry
;
823 DbgPrint("******* Dumping non paging pool stats ******\n");
826 for (i
= 0; i
< TAG_HASH_TABLE_SIZE
; i
++)
828 InitializeListHead(&tmpListHead
);
830 while (!IsListEmpty(&tag_hash_table
[i
]))
834 current_entry
= tag_hash_table
[i
].Flink
;
835 while (current_entry
!= &tag_hash_table
[i
])
837 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, Used
.TagListEntry
);
838 current_entry
= current_entry
->Flink
;
841 CurrentTag
= current
->Used
.Tag
;
845 if (current
->Used
.Tag
== CurrentTag
)
847 RemoveEntryList(¤t
->Used
.TagListEntry
);
848 InsertHeadList(&tmpListHead
, ¤t
->Used
.TagListEntry
);
849 if (!NewOnly
|| !current
->Used
.Dumped
)
853 CurrentSize
+= current
->Size
;
854 TotalSize
+= current
->Size
;
855 current
->Used
.Dumped
= TRUE
;
859 if (CurrentTag
!= 0 && CurrentNrBlocks
!= 0)
861 MiDumpTagStats(CurrentTag
, CurrentNrBlocks
, CurrentSize
);
864 if (!IsListEmpty(&tmpListHead
))
866 tag_hash_table
[i
].Flink
= tmpListHead
.Flink
;
867 tag_hash_table
[i
].Flink
->Blink
= &tag_hash_table
[i
];
868 tag_hash_table
[i
].Blink
= tmpListHead
.Blink
;
869 tag_hash_table
[i
].Blink
->Flink
= &tag_hash_table
[i
];
872 if (TotalBlocks
!= 0)
874 DbgPrint("TotalBlocks %d TotalSize %d AverageSize %d\n",
875 TotalBlocks
, TotalSize
, TotalSize
/ TotalBlocks
);
879 DbgPrint("TotalBlocks %d TotalSize %d\n",
880 TotalBlocks
, TotalSize
);
882 Size
= EiFreeNonPagedPool
- (MiNonPagedPoolLength
- MiNonPagedPoolNrOfPages
* PAGE_SIZE
);
883 DbgPrint("Freeblocks %d TotalFreeSize %d AverageFreeSize %d\n",
884 EiNrFreeBlocks
, Size
, EiNrFreeBlocks
? Size
/ EiNrFreeBlocks
: 0);
885 DbgPrint("***************** Dump Complete ***************\n");
886 #endif /* defined(TAG_STATISTICS_TRACKING) && !defined(WHOLE_PAGE_ALLOCATIONS) */
890 MiDebugDumpNonPagedPool(BOOLEAN NewOnly
)
892 #ifndef WHOLE_PAGE_ALLOCATIONS
894 PLIST_ENTRY current_entry
;
897 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
899 DbgPrint("******* Dumping non paging pool contents ******\n");
900 current_entry
= UsedBlockListHead
.Flink
;
901 while (current_entry
!= &UsedBlockListHead
)
903 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, Used
.ListEntry
);
904 if (!NewOnly
|| !current
->Used
.Dumped
)
908 c1
= (CHAR
)((current
->Used
.Tag
>> 24) & 0xFF);
909 c2
= (CHAR
)((current
->Used
.Tag
>> 16) & 0xFF);
910 c3
= (CHAR
)((current
->Used
.Tag
>> 8) & 0xFF);
911 c4
= (CHAR
)(current
->Used
.Tag
& 0xFF);
913 if (isprint(c1
) && isprint(c2
) && isprint(c3
) && isprint(c4
))
915 DbgPrint("Size 0x%x Tag 0x%x (%c%c%c%c) Allocator 0x%x\n",
916 current
->Size
, current
->Used
.Tag
, c4
, c3
, c2
, c1
,
917 current
->Used
.Caller
);
921 DbgPrint("Size 0x%x Tag 0x%x Allocator 0x%x\n",
922 current
->Size
, current
->Used
.Tag
, current
->Used
.Caller
);
924 current
->Used
.Dumped
= TRUE
;
926 current_entry
= current_entry
->Flink
;
928 DbgPrint("***************** Dump Complete ***************\n");
929 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
930 #endif /* not WHOLE_PAGE_ALLOCATIONS */
933 #ifndef WHOLE_PAGE_ALLOCATIONS
935 #ifdef ENABLE_VALIDATE_POOL
936 static void validate_free_list(void)
938 * FUNCTION: Validate the integrity of the list of free blocks
942 unsigned int blocks_seen
=0;
945 p
= avl_get_first(FreeBlockListRoot
);
951 current
= CONTAINING_RECORD(p
, BLOCK_HDR
, Free
.Node
);
952 base_addr
= (PVOID
)current
;
954 if (current
->Magic
!= BLOCK_HDR_FREE_MAGIC
)
956 DbgPrint("Bad block magic (probable pool corruption) at %x\n",
958 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
961 if (base_addr
< MiNonPagedPoolStart
||
962 base_addr
+ BLOCK_HDR_SIZE
+ current
->Size
> MiNonPagedPoolStart
+ MiNonPagedPoolLength
)
964 DbgPrint("Block %x found outside pool area\n",current
);
965 DbgPrint("Size %d\n",current
->Size
);
966 DbgPrint("Limits are %x %x\n",MiNonPagedPoolStart
,
967 MiNonPagedPoolStart
+MiNonPagedPoolLength
);
968 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
971 if (blocks_seen
> EiNrFreeBlocks
)
973 DbgPrint("Too many blocks on free list\n");
974 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
976 p
= avl_get_next(FreeBlockListRoot
, p
);
980 static void validate_used_list(void)
982 * FUNCTION: Validate the integrity of the list of used blocks
986 PLIST_ENTRY current_entry
;
987 unsigned int blocks_seen
=0;
989 current_entry
= UsedBlockListHead
.Flink
;
990 while (current_entry
!= &UsedBlockListHead
)
994 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, Used
.ListEntry
);
995 base_addr
= (PVOID
)current
;
997 if (current
->Magic
!= BLOCK_HDR_USED_MAGIC
)
999 DbgPrint("Bad block magic (probable pool corruption) at %x\n",
1001 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1003 if (base_addr
< MiNonPagedPoolStart
||
1004 (base_addr
+BLOCK_HDR_SIZE
+current
->Size
) >
1005 MiNonPagedPoolStart
+MiNonPagedPoolLength
)
1007 DbgPrint("Block %x found outside pool area\n",current
);
1008 DbgPrint("Size %d\n",current
->Size
);
1009 DbgPrint("Limits are %x %x\n",MiNonPagedPoolStart
,
1010 MiNonPagedPoolStart
+MiNonPagedPoolLength
);
1011 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1014 if (blocks_seen
> EiNrUsedBlocks
)
1016 DbgPrint("Too many blocks on used list\n");
1017 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1019 if (current
->Used
.ListEntry
.Flink
!= &UsedBlockListHead
&&
1020 current
->Used
.ListEntry
.Flink
->Blink
!= ¤t
->Used
.ListEntry
)
1022 DbgPrint("%s:%d:Break in list (current %x next %x "
1023 "current->next->previous %x)\n",
1024 __FILE__
,__LINE__
,current
, current
->Used
.ListEntry
.Flink
,
1025 current
->Used
.ListEntry
.Flink
->Blink
);
1026 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1029 current_entry
= current_entry
->Flink
;
1033 static void check_duplicates(BLOCK_HDR
* blk
)
1035 * FUNCTION: Check a block has no duplicates
1037 * blk = block to check
1038 * NOTE: Bug checks if duplicates are found
1041 char* base
= (char*)blk
;
1042 char* last
= ((char*)blk
) + BLOCK_HDR_SIZE
+ blk
->Size
;
1044 PLIST_ENTRY current_entry
;
1047 p
= avl_get_first(FreeBlockListRoot
);
1051 current
= CONTAINING_RECORD(p
, BLOCK_HDR
, Free
.Node
);
1053 if (current
->Magic
!= BLOCK_HDR_FREE_MAGIC
)
1055 DbgPrint("Bad block magic (probable pool corruption) at %x\n",
1057 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1060 if ( (char*)current
> base
&& (char*)current
< last
)
1062 DbgPrint("intersecting blocks on list\n");
1063 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1065 if ( (char*)current
< base
&&
1066 ((char*)current
+ current
->Size
+ BLOCK_HDR_SIZE
)
1069 DbgPrint("intersecting blocks on list\n");
1070 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1072 p
= avl_get_next(FreeBlockListRoot
, p
);
1075 current_entry
= UsedBlockListHead
.Flink
;
1076 while (current_entry
!= &UsedBlockListHead
)
1078 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, Used
.ListEntry
);
1080 if ( (char*)current
> base
&& (char*)current
< last
)
1082 DbgPrint("intersecting blocks on list\n");
1083 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1085 if ( (char*)current
< base
&&
1086 ((char*)current
+ current
->Size
+ BLOCK_HDR_SIZE
)
1089 DbgPrint("intersecting blocks on list\n");
1090 KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1093 current_entry
= current_entry
->Flink
;
1098 static void validate_kernel_pool(void)
1100 * FUNCTION: Checks the integrity of the kernel memory heap
1104 PLIST_ENTRY current_entry
;
1107 validate_free_list();
1108 validate_used_list();
1110 p
= avl_get_first(FreeBlockListRoot
);
1113 current
= CONTAINING_RECORD(p
, BLOCK_HDR
, Free
.Node
);
1114 check_duplicates(current
);
1115 p
= avl_get_next(FreeBlockListRoot
, p
);
1117 current_entry
= UsedBlockListHead
.Flink
;
1118 while (current_entry
!= &UsedBlockListHead
)
1120 current
= CONTAINING_RECORD(current_entry
, BLOCK_HDR
, Used
.ListEntry
);
1121 check_duplicates(current
);
1122 current_entry
= current_entry
->Flink
;
1129 free_pages(BLOCK_HDR
* blk
)
1136 end
= (ULONG
)blk
+ BLOCK_HDR_SIZE
+ blk
->Size
;
1139 * If the block doesn't contain a whole page then there is nothing to do
1141 if (PAGE_ROUND_UP(start
) >= PAGE_ROUND_DOWN(end
))
1148 static void remove_from_used_list(BLOCK_HDR
* current
)
1150 RemoveEntryList(¤t
->Used
.ListEntry
);
1151 EiUsedNonPagedPool
-= current
->Size
;
1155 static void remove_from_free_list(BLOCK_HDR
* current
)
1157 DPRINT("remove_from_free_list %d\n", current
->Size
);
1159 avl_remove(&FreeBlockListRoot
, ¤t
->Free
.Node
, compare_node
);
1161 EiFreeNonPagedPool
-= current
->Size
;
1163 DPRINT("remove_from_free_list done\n");
1166 DumpFreeBlockTree();
1171 add_to_free_list(BLOCK_HDR
* blk
)
1173 * FUNCTION: add the block to the free list (internal)
1177 BOOL UpdatePrevPtr
= FALSE
;
1179 DPRINT("add_to_free_list (%d)\n", blk
->Size
);
1183 current
= blk
->previous
;
1184 if (current
&& current
->Magic
== BLOCK_HDR_FREE_MAGIC
)
1186 remove_from_free_list(current
);
1187 current
->Size
= current
->Size
+ BLOCK_HDR_SIZE
+ blk
->Size
;
1188 current
->Magic
= BLOCK_HDR_USED_MAGIC
;
1189 memset(blk
, 0xcc, BLOCK_HDR_SIZE
);
1191 UpdatePrevPtr
= TRUE
;
1194 current
= (BLOCK_HDR
*)((char*)blk
+ BLOCK_HDR_SIZE
+ blk
->Size
);
1195 if ((char*)current
< (char*)MiNonPagedPoolStart
+ MiNonPagedPoolLength
&&
1196 current
->Magic
== BLOCK_HDR_FREE_MAGIC
)
1198 remove_from_free_list(current
);
1199 blk
->Size
+= BLOCK_HDR_SIZE
+ current
->Size
;
1200 memset(current
, 0xcc, BLOCK_HDR_SIZE
);
1201 UpdatePrevPtr
= TRUE
;
1202 current
= (BLOCK_HDR
*)((char*)blk
+ BLOCK_HDR_SIZE
+ blk
->Size
);
1204 if (UpdatePrevPtr
&&
1205 (char*)current
< (char*)MiNonPagedPoolStart
+ MiNonPagedPoolLength
)
1207 current
->previous
= blk
;
1209 DPRINT("%d\n", blk
->Size
);
1210 blk
->Magic
= BLOCK_HDR_FREE_MAGIC
;
1211 EiFreeNonPagedPool
+= blk
->Size
;
1212 avl_insert(&FreeBlockListRoot
, &blk
->Free
.Node
, compare_node
);
1214 DPRINT("add_to_free_list done\n");
1217 DumpFreeBlockTree();
1221 static void add_to_used_list(BLOCK_HDR
* blk
)
1223 * FUNCTION: add the block to the used list (internal)
1226 InsertHeadList(&UsedBlockListHead
, &blk
->Used
.ListEntry
);
1227 EiUsedNonPagedPool
+= blk
->Size
;
1231 inline static void* block_to_address(BLOCK_HDR
* blk
)
1233 * FUNCTION: Translate a block header address to the corresponding block
1234 * address (internal)
1237 return ( (void *) ((char*)blk
+ BLOCK_HDR_SIZE
));
1240 inline static BLOCK_HDR
* address_to_block(void* addr
)
1242 return (BLOCK_HDR
*)
1243 ( ((char*)addr
) - BLOCK_HDR_SIZE
);
1247 grow_block(BLOCK_HDR
* blk
, PVOID end
)
1251 ULONG StartIndex
, EndIndex
;
1254 StartIndex
= (ULONG
)((char*)(PVOID
)PAGE_ROUND_UP((ULONG
)((char*)blk
+ BLOCK_HDR_SIZE
)) - (char*)MiNonPagedPoolStart
) / PAGE_SIZE
;
1255 EndIndex
= (ULONG
)((char*)PAGE_ROUND_UP(end
) - (char*)MiNonPagedPoolStart
) / PAGE_SIZE
;
1258 for (i
= StartIndex
; i
< EndIndex
; i
++)
1260 if (!(MiNonPagedPoolAllocMap
[i
/ 32] & (1 << (i
% 32))))
1262 for (j
= i
+ 1; j
< EndIndex
&& j
- i
< 32; j
++)
1264 if (MiNonPagedPoolAllocMap
[j
/ 32] & (1 << (j
% 32)))
1269 for (k
= 0; k
< j
- i
; k
++)
1271 Status
= MmRequestPageMemoryConsumer(MC_NPPOOL
, FALSE
, &Page
[k
]);
1272 if (!NT_SUCCESS(Status
))
1274 for (i
= 0; i
< k
; i
++)
1276 MmReleasePageMemoryConsumer(MC_NPPOOL
, Page
[i
]);
1281 Status
= MmCreateVirtualMapping(NULL
,
1282 MiNonPagedPoolStart
+ i
* PAGE_SIZE
,
1283 PAGE_READWRITE
|PAGE_SYSTEM
,
1286 if (!NT_SUCCESS(Status
))
1288 for (i
= 0; i
< k
; i
++)
1290 MmReleasePageMemoryConsumer(MC_NPPOOL
, Page
[i
]);
1294 for (j
= i
; j
< k
+ i
; j
++)
1296 MiNonPagedPoolAllocMap
[j
/ 32] |= (1 << (j
% 32));
1298 MiNonPagedPoolNrOfPages
+= k
;
1305 static BLOCK_HDR
* get_block(unsigned int size
, unsigned long alignment
)
1307 BLOCK_HDR
*blk
, *current
, *previous
= NULL
, *next
= NULL
, *best
= NULL
;
1308 ULONG previous_size
= 0, current_size
, next_size
= 0, new_size
;
1310 PVOID addr
, aligned_addr
;
1313 DPRINT("get_block %d\n", size
);
1317 p
= avl_find_equal_or_greater(FreeBlockListRoot
, size
, compare_value
);
1320 best
= CONTAINING_RECORD(p
, BLOCK_HDR
, Free
.Node
);
1321 addr
= block_to_address(best
);
1326 p
= avl_find_equal_or_greater(FreeBlockListRoot
, size
, compare_value
);
1330 current
= CONTAINING_RECORD(p
, BLOCK_HDR
, Free
.Node
);
1331 addr
= block_to_address(current
);
1332 /* calculate first aligned address available within this block */
1333 aligned_addr
= MM_ROUND_UP(addr
, alignment
);
1334 /* check to see if this address is already aligned */
1335 if (addr
== aligned_addr
)
1337 if (current
->Size
>= size
&&
1338 (best
== NULL
|| current
->Size
< best
->Size
))
1345 /* make sure there's enough room to make a free block by the space skipped
1346 * from alignment. If not, calculate forward to the next alignment
1347 * and see if we allocate there...
1349 new_size
= (ULONG
)aligned_addr
- (ULONG
)addr
+ size
;
1350 if ((ULONG
)aligned_addr
- (ULONG
)addr
< BLOCK_HDR_SIZE
)
1352 /* not enough room for a free block header, add some more bytes */
1353 aligned_addr
= MM_ROUND_UP(block_to_address((BLOCK_HDR
*)((char*)current
+ BLOCK_HDR_SIZE
)), alignment
);
1354 new_size
= (ULONG
)aligned_addr
- (ULONG
)addr
+ size
;
1356 if (current
->Size
>= new_size
&&
1357 (best
== NULL
|| current
->Size
< best
->Size
))
1362 if (best
&& current
->Size
>= size
+ alignment
+ 2 * BLOCK_HDR_SIZE
)
1366 p
= avl_get_next(FreeBlockListRoot
, p
);
1372 * We didn't find anything suitable at all.
1380 current_size
= current
->Size
;
1384 addr
= block_to_address(current
);
1385 aligned_addr
= MM_ROUND_UP(addr
, alignment
);
1386 if (addr
!= aligned_addr
)
1388 blk
= address_to_block(aligned_addr
);
1389 if ((char*)blk
< (char*)current
+ BLOCK_HDR_SIZE
)
1391 aligned_addr
= MM_ROUND_UP(block_to_address((BLOCK_HDR
*)((char*)current
+ BLOCK_HDR_SIZE
)), alignment
);
1392 blk
= address_to_block(aligned_addr
);
1395 * if size-aligned, break off the preceding bytes into their own block...
1398 previous_size
= (ULONG
)blk
- (ULONG
)previous
- BLOCK_HDR_SIZE
;
1400 current_size
-= ((ULONG
)current
- (ULONG
)previous
);
1404 end
= (char*)current
+ BLOCK_HDR_SIZE
+ size
;
1406 if (current_size
>= size
+ BLOCK_HDR_SIZE
+ MM_POOL_ALIGNMENT
)
1408 /* create a new free block after our block, if the memory size is >= 4 byte for this block */
1409 next
= (BLOCK_HDR
*)((ULONG
)current
+ size
+ BLOCK_HDR_SIZE
);
1410 next_size
= current_size
- size
- BLOCK_HDR_SIZE
;
1411 current_size
= size
;
1412 end
= (char*)next
+ BLOCK_HDR_SIZE
;
1417 remove_from_free_list(previous
);
1418 if (!grow_block(previous
, end
))
1420 add_to_free_list(previous
);
1423 memset(current
, 0, BLOCK_HDR_SIZE
);
1424 current
->Size
= current_size
;
1425 current
->Magic
= BLOCK_HDR_USED_MAGIC
;
1426 current
->previous
= previous
;
1427 previous
->Size
= previous_size
;
1430 blk
= (BLOCK_HDR
*)((char*)current
+ BLOCK_HDR_SIZE
+ current
->Size
);
1431 if ((char*)blk
< (char*)MiNonPagedPoolStart
+ MiNonPagedPoolLength
)
1433 blk
->previous
= current
;
1437 add_to_free_list(previous
);
1441 remove_from_free_list(current
);
1443 if (!grow_block(current
, end
))
1445 add_to_free_list(current
);
1449 current
->Magic
= BLOCK_HDR_USED_MAGIC
;
1452 current
->Size
= current_size
;
1458 memset(next
, 0, BLOCK_HDR_SIZE
);
1460 next
->Size
= next_size
;
1461 next
->Magic
= BLOCK_HDR_FREE_MAGIC
;
1462 next
->previous
= current
;
1463 blk
= (BLOCK_HDR
*)((char*)next
+ BLOCK_HDR_SIZE
+ next
->Size
);
1464 if ((char*)blk
< (char*)MiNonPagedPoolStart
+ MiNonPagedPoolLength
)
1466 blk
->previous
= next
;
1468 add_to_free_list(next
);
1471 add_to_used_list(current
);
1476 #endif /* not WHOLE_PAGE_ALLOCATIONS */
1478 VOID STDCALL
ExFreeNonPagedPool (PVOID block
)
1480 * FUNCTION: Releases previously allocated memory
1482 * block = block to free
1485 #ifdef WHOLE_PAGE_ALLOCATIONS /* WHOLE_PAGE_ALLOCATIONS */
1493 DPRINT("freeing block %x\n",blk
);
1495 POOL_TRACE("ExFreePool(block %x), size %d, caller %x\n",block
,blk
->size
,
1496 ((PULONG
)&block
)[-1]);
1498 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1500 ExFreeWholePageBlock(block
);
1501 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1503 #else /* not WHOLE_PAGE_ALLOCATIONS */
1505 BLOCK_HDR
* blk
=address_to_block(block
);
1513 DPRINT("freeing block %x\n",blk
);
1515 POOL_TRACE("ExFreePool(block %x), size %d, caller %x\n",block
,blk
->Size
,
1516 ((PULONG
)&block
)[-1]);
1518 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1522 if (blk
->Magic
!= BLOCK_HDR_USED_MAGIC
)
1524 if (blk
->Magic
== BLOCK_HDR_FREE_MAGIC
)
1526 DbgPrint("ExFreePool of already freed address %x\n", block
);
1530 DbgPrint("ExFreePool of non-allocated address %x (magic %x)\n",
1537 memset(block
, 0xcc, blk
->Size
);
1538 #ifdef TAG_STATISTICS_TRACKING
1540 MiRemoveFromTagHashTable(blk
);
1543 remove_from_used_list(blk
);
1544 blk
->Magic
= BLOCK_HDR_FREE_MAGIC
;
1545 add_to_free_list(blk
);
1547 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1549 #endif /* WHOLE_PAGE_ALLOCATIONS */
1553 ExAllocateNonPagedPoolWithTag(ULONG Type
, ULONG Size
, ULONG Tag
, PVOID Caller
)
1555 #ifdef WHOLE_PAGE_ALLOCATIONS
1559 POOL_TRACE("ExAllocatePool(NumberOfBytes %d) caller %x ",
1562 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1565 * accomodate this useful idiom
1569 POOL_TRACE("= NULL\n");
1570 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1574 block
= ExAllocateWholePageBlock(Size
);
1575 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1578 DPRINT1("Trying to allocate %lu bytes from nonpaged pool - nothing suitable found, returning NULL\n",
1583 #else /* not WHOLE_PAGE_ALLOCATIONS */
1586 BLOCK_HDR
* best
= NULL
;
1590 POOL_TRACE("ExAllocatePool(NumberOfBytes %d) caller %x ",
1593 KeAcquireSpinLock(&MmNpoolLock
, &oldIrql
);
1598 /* after some allocations print the npaged pool stats */
1599 #ifdef TAG_STATISTICS_TRACKING
1602 static ULONG counter
= 0;
1603 if (counter
++ % 100000 == 0)
1605 MiDebugDumpNonPagedPoolStats(FALSE
);
1611 * accomodate this useful idiom
1615 POOL_TRACE("= NULL\n");
1616 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1619 /* Make the size dword alligned, this makes the block dword alligned */
1620 Size
= ROUND_UP(Size
, MM_POOL_ALIGNMENT
);
1622 if (Size
>= PAGE_SIZE
)
1624 alignment
= PAGE_SIZE
;
1626 else if (Type
== NonPagedPoolCacheAligned
||
1627 Type
== NonPagedPoolCacheAlignedMustS
)
1629 alignment
= MM_CACHE_LINE_SIZE
;
1636 best
= get_block(Size
, alignment
);
1639 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1640 DPRINT1("Trying to allocate %lu bytes from nonpaged pool - nothing suitable found, returning NULL\n",
1644 best
->Used
.Tag
= Tag
;
1645 best
->Used
.Caller
= Caller
;
1646 best
->Used
.Dumped
= FALSE
;
1647 best
->Used
.TagListEntry
.Flink
= best
->Used
.TagListEntry
.Blink
= NULL
;
1648 #ifdef TAG_STATISTICS_TRACKING
1650 MiAddToTagHashTable(best
);
1653 KeReleaseSpinLock(&MmNpoolLock
, oldIrql
);
1654 block
= block_to_address(best
);
1655 /* RtlZeroMemory(block, Size);*/
1657 #endif /* WHOLE_PAGE_ALLOCATIONS */
1660 #ifdef WHOLE_PAGE_ALLOCATIONS
1663 ExAllocateWholePageBlock(ULONG Size
)
1666 PHYSICAL_ADDRESS Page
;
1671 NrPages
= ROUND_UP(Size
, PAGE_SIZE
) / PAGE_SIZE
;
1673 Base
= RtlFindClearBitsAndSet(&NonPagedPoolAllocMap
, NrPages
+ 1, NonPagedPoolAllocMapHint
);
1674 if (Base
== 0xffffffff)
1676 DbgPrint("Out of non paged pool space.\n");
1679 if (NonPagedPoolAllocMapHint
== Base
)
1681 NonPagedPoolAllocMapHint
+= (NrPages
+ 1);
1683 Address
= MiNonPagedPoolStart
+ Base
* PAGE_SIZE
;
1685 for (i
= 0; i
< NrPages
; i
++)
1687 Page
= MmAllocPage(MC_NPPOOL
, 0);
1688 if (Page
.QuadPart
== 0LL)
1692 MmCreateVirtualMapping(NULL
,
1693 Address
+ (i
* PAGE_SIZE
),
1694 PAGE_READWRITE
| PAGE_SYSTEM
,
1699 MiCurrentNonPagedPoolLength
= max(MiCurrentNonPagedPoolLength
, (Base
+ NrPages
) * PAGE_SIZE
);
1700 Size
= (Size
+ 7) & ~7;
1701 return((PVOID
)((PUCHAR
)Address
+ (NrPages
* PAGE_SIZE
) - Size
));
1705 ExFreeWholePageBlock(PVOID Addr
)
1709 if (Addr
< MiNonPagedPoolStart
||
1710 Addr
>= (MiNonPagedPoolStart
+ MiCurrentNonPagedPoolLength
))
1712 DbgPrint("Block %x found outside pool area\n", Addr
);
1715 Base
= (Addr
- MiNonPagedPoolStart
) / PAGE_SIZE
;
1716 NonPagedPoolAllocMapHint
= min(NonPagedPoolAllocMapHint
, Base
);
1717 while (MmIsPagePresent(NULL
, Addr
))
1719 MmDeleteVirtualMapping(NULL
,
1724 RtlClearBits(&NonPagedPoolAllocMap
, Base
, 1);
1730 #endif /* WHOLE_PAGE_ALLOCATIONS */
1733 MiInitializeNonPagedPool(VOID
)
1739 #ifdef WHOLE_PAGE_ALLOCATIONS
1744 #ifdef TAG_STATISTICS_TRACKING
1746 for (i
= 0; i
< TAG_HASH_TABLE_SIZE
; i
++)
1748 InitializeListHead(&tag_hash_table
[i
]);
1751 KeInitializeSpinLock(&MmNpoolLock
);
1752 InitializeListHead(&UsedBlockListHead
);
1753 InitializeListHead(&AddressListHead
);
1754 FreeBlockListRoot
= NULL
;
1755 #ifdef WHOLE_PAGE_ALLOCATIONS
1757 NonPagedPoolAllocMapHint
= PAGE_ROUND_UP(MiNonPagedPoolLength
/ PAGE_SIZE
/ 8) / PAGE_SIZE
;
1758 MiCurrentNonPagedPoolLength
= NonPagedPoolAllocMapHint
* PAGE_SIZE
;
1759 Address
= MiNonPagedPoolStart
;
1760 for (i
= 0; i
< NonPagedPoolAllocMapHint
; i
++)
1762 Status
= MmRequestPageMemoryConsumer(MC_NPPOOL
, FALSE
, &Page
);
1763 if (!NT_SUCCESS(Status
))
1765 DbgPrint("Unable to allocate a page\n");
1768 Status
= MmCreateVirtualMapping(NULL
,
1770 PAGE_READWRITE
|PAGE_SYSTEM
,
1773 if (!NT_SUCCESS(Status
))
1775 DbgPrint("Unable to create virtual mapping\n");
1778 Address
+= PAGE_SIZE
;
1780 RtlInitializeBitMap(&NonPagedPoolAllocMap
, MiNonPagedPoolStart
, MM_NONPAGED_POOL_SIZE
/ PAGE_SIZE
);
1781 RtlClearAllBits(&NonPagedPoolAllocMap
);
1782 RtlSetBits(&NonPagedPoolAllocMap
, 0, NonPagedPoolAllocMapHint
);
1785 MiNonPagedPoolAllocMap
= block_to_address((BLOCK_HDR
*)MiNonPagedPoolStart
);
1786 MiNonPagedPoolNrOfPages
= PAGE_ROUND_UP(ROUND_UP(MiNonPagedPoolLength
/ PAGE_SIZE
, 32) / 8 + 2 * BLOCK_HDR_SIZE
);
1787 MiNonPagedPoolNrOfPages
/= PAGE_SIZE
;
1788 Address
= MiNonPagedPoolStart
;
1789 for (i
= 0; i
< MiNonPagedPoolNrOfPages
; i
++)
1791 Status
= MmRequestPageMemoryConsumer(MC_NPPOOL
, FALSE
, &Page
);
1792 if (!NT_SUCCESS(Status
))
1794 DbgPrint("Unable to allocate a page\n");
1797 Status
= MmCreateVirtualMapping(NULL
,
1799 PAGE_READWRITE
|PAGE_SYSTEM
,
1802 if (!NT_SUCCESS(Status
))
1804 DbgPrint("Unable to create virtual mapping\n");
1807 MiNonPagedPoolAllocMap
[i
/ 32] |= (1 << (i
% 32));
1808 Address
= (PVOID
)((ULONG_PTR
)Address
+ PAGE_SIZE
);
1810 /* the first block contains the non paged pool bitmap */
1811 blk
= (BLOCK_HDR
*)MiNonPagedPoolStart
;
1812 memset(blk
, 0, BLOCK_HDR_SIZE
);
1813 blk
->Magic
= BLOCK_HDR_USED_MAGIC
;
1814 blk
->Size
= ROUND_UP(MiNonPagedPoolLength
/ PAGE_SIZE
, 32) / 8;
1815 blk
->previous
= NULL
;
1816 blk
->Used
.Tag
= 0xffffffff;
1817 blk
->Used
.Caller
= 0;
1818 blk
->Used
.Dumped
= FALSE
;
1819 add_to_used_list(blk
);
1820 #ifdef TAG_STATISTICS_TRACKING
1822 MiAddToTagHashTable(blk
);
1824 /* the second block is the first free block */
1825 blk
= (BLOCK_HDR
*)((char*)blk
+ BLOCK_HDR_SIZE
+ blk
->Size
);
1826 memset(blk
, 0, BLOCK_HDR_SIZE
);
1827 memset((char*)blk
+ BLOCK_HDR_SIZE
, 0x0cc, MiNonPagedPoolNrOfPages
* PAGE_SIZE
- ((ULONG
)blk
+ BLOCK_HDR_SIZE
- (ULONG
)MiNonPagedPoolStart
));
1828 blk
->Magic
= BLOCK_HDR_FREE_MAGIC
;
1829 blk
->Size
= MiNonPagedPoolLength
- ((ULONG
)blk
+ BLOCK_HDR_SIZE
- (ULONG
)MiNonPagedPoolStart
);
1830 blk
->previous
= (BLOCK_HDR
*)MiNonPagedPoolStart
;
1831 add_to_free_list(blk
);
1837 MiAllocateSpecialPool (IN POOL_TYPE PoolType
,
1838 IN SIZE_T NumberOfBytes
,
1843 /* FIXME: Special Pools not Supported */
1844 DbgPrint("Special Pools not supported\n");