1 /* $Id: ppool.c,v 1.11 2002/09/08 10:23:36 chorns Exp $
3 * COPYRIGHT: See COPYING in the top level directory
4 * PROJECT: ReactOS kernel
5 * FILE: ntoskrnl/mm/ppool.c
6 * PURPOSE: Implements the paged pool
7 * PROGRAMMER: David Welch (welch@mcmail.com)
12 /* INCLUDES *****************************************************************/
14 #include <ddk/ntddk.h>
15 #include <internal/pool.h>
16 #include <internal/mm.h>
18 #include <internal/debug.h>
20 /* GLOBALS *******************************************************************/
22 typedef struct _MM_PPOOL_FREE_BLOCK_HEADER
25 struct _MM_PPOOL_FREE_BLOCK_HEADER
* NextFree
;
26 } MM_PPOOL_FREE_BLOCK_HEADER
, *PMM_PPOOL_FREE_BLOCK_HEADER
;
28 typedef struct _MM_PPOOL_USED_BLOCK_HEADER
31 } MM_PPOOL_USED_BLOCK_HEADER
, *PMM_PPOOL_USED_BLOCK_HEADER
;
33 PVOID MmPagedPoolBase
;
34 ULONG MmPagedPoolSize
;
35 static FAST_MUTEX MmPagedPoolLock
;
36 static PMM_PPOOL_FREE_BLOCK_HEADER MmPagedPoolFirstFreeBlock
;
38 /* FUNCTIONS *****************************************************************/
40 VOID
MmInitializePagedPool(VOID
)
42 MmPagedPoolFirstFreeBlock
= (PMM_PPOOL_FREE_BLOCK_HEADER
)MmPagedPoolBase
;
44 * We are still at a high IRQL level at this point so explicitly commit
45 * the first page of the paged pool before writing the first block header.
47 MmCommitPagedPoolAddress((PVOID
)MmPagedPoolFirstFreeBlock
);
48 MmPagedPoolFirstFreeBlock
->Size
= MmPagedPoolSize
;
49 MmPagedPoolFirstFreeBlock
->NextFree
= NULL
;
51 ExInitializeFastMutex(&MmPagedPoolLock
);
54 /**********************************************************************
56 * ExAllocatePagedPoolWithTag@12
65 ExAllocatePagedPoolWithTag (IN POOL_TYPE PoolType
,
66 IN ULONG NumberOfBytes
,
69 PMM_PPOOL_FREE_BLOCK_HEADER BestBlock
;
70 PMM_PPOOL_FREE_BLOCK_HEADER CurrentBlock
;
72 PMM_PPOOL_USED_BLOCK_HEADER NewBlock
;
73 PMM_PPOOL_FREE_BLOCK_HEADER NextBlock
;
74 PMM_PPOOL_FREE_BLOCK_HEADER PreviousBlock
;
75 PMM_PPOOL_FREE_BLOCK_HEADER BestPreviousBlock
;
79 * Don't bother allocating anything for a zero-byte block.
81 if (NumberOfBytes
== 0)
87 * Calculate the total number of bytes we will need.
89 BlockSize
= NumberOfBytes
+ sizeof(MM_PPOOL_USED_BLOCK_HEADER
);
90 if (BlockSize
< sizeof(MM_PPOOL_FREE_BLOCK_HEADER
))
92 /* At least we need the size of the free block header. */
93 BlockSize
= sizeof(MM_PPOOL_FREE_BLOCK_HEADER
);
96 ExAcquireFastMutex(&MmPagedPoolLock
);
99 * Find the best fitting block.
101 PreviousBlock
= NULL
;
102 BestPreviousBlock
= BestBlock
= NULL
;
103 CurrentBlock
= MmPagedPoolFirstFreeBlock
;
104 while (CurrentBlock
!= NULL
)
106 if (CurrentBlock
->Size
>= BlockSize
&&
107 (BestBlock
== NULL
||
108 (BestBlock
->Size
- BlockSize
) > (CurrentBlock
->Size
- BlockSize
)))
110 BestPreviousBlock
= PreviousBlock
;
111 BestBlock
= CurrentBlock
;
114 PreviousBlock
= CurrentBlock
;
115 CurrentBlock
= CurrentBlock
->NextFree
;
119 * We didn't find anything suitable at all.
121 if (BestBlock
== NULL
)
123 ExReleaseFastMutex(&MmPagedPoolLock
);
128 * Is there enough space to create a second block from the unused portion.
130 if ((BestBlock
->Size
- BlockSize
) > sizeof(MM_PPOOL_FREE_BLOCK_HEADER
))
132 ULONG NewSize
= BestBlock
->Size
- BlockSize
;
135 * Create the new free block.
137 NextBlock
= (PMM_PPOOL_FREE_BLOCK_HEADER
)((PVOID
)BestBlock
+ BlockSize
);
138 NextBlock
->Size
= NewSize
;
139 NextBlock
->NextFree
= BestBlock
->NextFree
;
142 * Replace the old free block with it.
144 if (BestPreviousBlock
== NULL
)
146 MmPagedPoolFirstFreeBlock
= NextBlock
;
150 BestPreviousBlock
->NextFree
= NextBlock
;
154 * Create the new used block header.
156 NewBlock
= (PMM_PPOOL_USED_BLOCK_HEADER
)BestBlock
;
157 NewBlock
->Size
= BlockSize
;
161 ULONG NewSize
= BestBlock
->Size
;
164 * Remove the selected block from the list of free blocks.
166 if (BestPreviousBlock
== NULL
)
168 MmPagedPoolFirstFreeBlock
= BestBlock
->NextFree
;
172 BestPreviousBlock
->NextFree
= BestBlock
->NextFree
;
176 * Set up the header of the new block
178 NewBlock
= (PMM_PPOOL_USED_BLOCK_HEADER
)BestBlock
;
179 NewBlock
->Size
= NewSize
;
182 ExReleaseFastMutex(&MmPagedPoolLock
);
184 BlockAddress
= (PVOID
)NewBlock
+ sizeof(MM_PPOOL_USED_BLOCK_HEADER
);
186 memset(BlockAddress
, 0, NumberOfBytes
);
188 return(BlockAddress
);
192 ExFreePagedPool(IN PVOID Block
)
194 PMM_PPOOL_FREE_BLOCK_HEADER PreviousBlock
;
195 PMM_PPOOL_USED_BLOCK_HEADER UsedBlock
=
196 (PMM_PPOOL_USED_BLOCK_HEADER
)(Block
- sizeof(MM_PPOOL_USED_BLOCK_HEADER
));
197 ULONG UsedSize
= UsedBlock
->Size
;
198 PMM_PPOOL_FREE_BLOCK_HEADER FreeBlock
=
199 (PMM_PPOOL_FREE_BLOCK_HEADER
)UsedBlock
;
200 PMM_PPOOL_FREE_BLOCK_HEADER NextBlock
;
201 PMM_PPOOL_FREE_BLOCK_HEADER NextNextBlock
;
203 ExAcquireFastMutex(&MmPagedPoolLock
);
206 * Begin setting up the newly freed block's header.
208 FreeBlock
->Size
= UsedSize
;
211 * Find the blocks immediately before and after the newly freed block on the free list.
213 PreviousBlock
= NULL
;
214 NextBlock
= MmPagedPoolFirstFreeBlock
;
215 while (NextBlock
!= NULL
&& NextBlock
< FreeBlock
)
217 PreviousBlock
= NextBlock
;
218 NextBlock
= NextBlock
->NextFree
;
222 * Insert the freed block on the free list.
224 if (PreviousBlock
== NULL
)
226 FreeBlock
->NextFree
= MmPagedPoolFirstFreeBlock
;
227 MmPagedPoolFirstFreeBlock
= FreeBlock
;
231 PreviousBlock
->NextFree
= FreeBlock
;
232 FreeBlock
->NextFree
= NextBlock
;
236 * If the next block is immediately adjacent to the newly freed one then
239 if (NextBlock
!= NULL
&&
240 ((PVOID
)FreeBlock
+ FreeBlock
->Size
) == (PVOID
)NextBlock
)
242 FreeBlock
->Size
= FreeBlock
->Size
+ NextBlock
->Size
;
243 FreeBlock
->NextFree
= NextBlock
->NextFree
;
244 NextNextBlock
= NextBlock
->NextFree
;
248 NextNextBlock
= NextBlock
;
252 * If the previous block is adjacent to the newly freed one then
255 if (PreviousBlock
!= NULL
&&
256 ((PVOID
)PreviousBlock
+ PreviousBlock
->Size
) == (PVOID
)FreeBlock
)
258 PreviousBlock
->Size
= PreviousBlock
->Size
+ FreeBlock
->Size
;
259 PreviousBlock
->NextFree
= NextNextBlock
;
262 ExReleaseFastMutex(&MmPagedPoolLock
);