reactos/ntoskrnl/mm/ppool.c

   1 /* $Id: ppool.c,v 1.12 2003/07/10 21:05:04 royce Exp $
   2  *
   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)
   8  * UPDATE HISTORY:
   9  *                  Created 22/05/98
  10  */
  11
  12 /* INCLUDES *****************************************************************/
  13
  14 #include <ddk/ntddk.h>
  15 #include <internal/pool.h>
  16 #include <internal/mm.h>
  17
  18 #include <internal/debug.h>
  19
  20 /* GLOBALS *******************************************************************/
  21
  22 typedef struct _MM_PPOOL_FREE_BLOCK_HEADER
  23 {
  24   ULONG Size;
  25   struct _MM_PPOOL_FREE_BLOCK_HEADER* NextFree;
  26 } MM_PPOOL_FREE_BLOCK_HEADER, *PMM_PPOOL_FREE_BLOCK_HEADER;
  27
  28 typedef struct _MM_PPOOL_USED_BLOCK_HEADER
  29 {
  30   ULONG Size;
  31 } MM_PPOOL_USED_BLOCK_HEADER, *PMM_PPOOL_USED_BLOCK_HEADER;
  32
  33 PVOID MmPagedPoolBase;
  34 ULONG MmPagedPoolSize;
  35 static FAST_MUTEX MmPagedPoolLock;
  36 static PMM_PPOOL_FREE_BLOCK_HEADER MmPagedPoolFirstFreeBlock;
  37
  38 /* FUNCTIONS *****************************************************************/
  39
  40 VOID MmInitializePagedPool(VOID)
  41 {
  42   MmPagedPoolFirstFreeBlock = (PMM_PPOOL_FREE_BLOCK_HEADER)MmPagedPoolBase;
  43   /*
  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.
  46    */
  47   MmCommitPagedPoolAddress((PVOID)MmPagedPoolFirstFreeBlock);
  48   MmPagedPoolFirstFreeBlock->Size = MmPagedPoolSize;
  49   MmPagedPoolFirstFreeBlock->NextFree = NULL;
  50
  51   ExInitializeFastMutex(&MmPagedPoolLock);
  52 }
  53
  54 /**********************************************************************
  55  * NAME                                                 INTERNAL
  56  *      ExAllocatePagedPoolWithTag@12
  57  *
  58  * DESCRIPTION
  59  *
  60  * ARGUMENTS
  61  *
  62  * RETURN VALUE
  63  *
  64  * @implemented
  65  */
  66 PVOID STDCALL
  67 ExAllocatePagedPoolWithTag (IN  POOL_TYPE       PoolType,
  68                             IN  ULONG           NumberOfBytes,
  69                             IN  ULONG           Tag)
  70 {
  71   PMM_PPOOL_FREE_BLOCK_HEADER BestBlock;
  72   PMM_PPOOL_FREE_BLOCK_HEADER CurrentBlock;
  73   ULONG BlockSize;
  74   PMM_PPOOL_USED_BLOCK_HEADER NewBlock;
  75   PMM_PPOOL_FREE_BLOCK_HEADER NextBlock;
  76   PMM_PPOOL_FREE_BLOCK_HEADER PreviousBlock;
  77   PMM_PPOOL_FREE_BLOCK_HEADER BestPreviousBlock;
  78   PVOID BlockAddress;
  79
  80   /*
  81    * Don't bother allocating anything for a zero-byte block.
  82    */
  83   if (NumberOfBytes == 0)
  84     {
  85       return(NULL);
  86     }
  87
  88   /*
  89    * Calculate the total number of bytes we will need.
  90    */
  91   BlockSize = NumberOfBytes + sizeof(MM_PPOOL_USED_BLOCK_HEADER);
  92   if (BlockSize < sizeof(MM_PPOOL_FREE_BLOCK_HEADER))
  93   {
  94     /* At least we need the size of the free block header. */
  95     BlockSize = sizeof(MM_PPOOL_FREE_BLOCK_HEADER);
  96   }
  97
  98   ExAcquireFastMutex(&MmPagedPoolLock);
  99
 100   /*
 101    * Find the best fitting block.
 102    */
 103   PreviousBlock = NULL;
 104   BestPreviousBlock = BestBlock = NULL;
 105   CurrentBlock = MmPagedPoolFirstFreeBlock;
 106   while (CurrentBlock != NULL)
 107     {
 108       if (CurrentBlock->Size >= BlockSize &&
 109           (BestBlock == NULL ||
 110            (BestBlock->Size - BlockSize) > (CurrentBlock->Size - BlockSize)))
 111         {
 112           BestPreviousBlock = PreviousBlock;
 113           BestBlock = CurrentBlock;
 114         }
 115
 116       PreviousBlock = CurrentBlock;
 117       CurrentBlock = CurrentBlock->NextFree;
 118     }
 119
 120   /*
 121    * We didn't find anything suitable at all.
 122    */
 123   if (BestBlock == NULL)
 124     {
 125       ExReleaseFastMutex(&MmPagedPoolLock);
 126       return(NULL);
 127     }
 128
 129   /*
 130    * Is there enough space to create a second block from the unused portion.
 131    */
 132   if ((BestBlock->Size - BlockSize) > sizeof(MM_PPOOL_FREE_BLOCK_HEADER))
 133     {
 134       ULONG NewSize = BestBlock->Size - BlockSize;
 135
 136       /*
 137        * Create the new free block.
 138        */
 139       NextBlock = (PMM_PPOOL_FREE_BLOCK_HEADER)((PVOID)BestBlock + BlockSize);
 140       NextBlock->Size = NewSize;
 141       NextBlock->NextFree = BestBlock->NextFree;
 142
 143       /*
 144        * Replace the old free block with it.
 145        */
 146       if (BestPreviousBlock == NULL)
 147         {
 148           MmPagedPoolFirstFreeBlock = NextBlock;
 149         }
 150       else
 151         {
 152           BestPreviousBlock->NextFree = NextBlock;
 153         }
 154
 155       /*
 156        * Create the new used block header.
 157        */
 158       NewBlock = (PMM_PPOOL_USED_BLOCK_HEADER)BestBlock;
 159       NewBlock->Size = BlockSize;
 160     }
 161   else
 162     {
 163       ULONG NewSize = BestBlock->Size;
 164
 165       /*
 166        * Remove the selected block from the list of free blocks.
 167        */
 168       if (BestPreviousBlock == NULL)
 169         {
 170           MmPagedPoolFirstFreeBlock = BestBlock->NextFree;
 171         }
 172       else
 173         {
 174           BestPreviousBlock->NextFree = BestBlock->NextFree;
 175         }
 176
 177       /*
 178        * Set up the header of the new block
 179        */
 180       NewBlock = (PMM_PPOOL_USED_BLOCK_HEADER)BestBlock;
 181       NewBlock->Size = NewSize;
 182     }
 183
 184   ExReleaseFastMutex(&MmPagedPoolLock);
 185
 186   BlockAddress = (PVOID)NewBlock + sizeof(MM_PPOOL_USED_BLOCK_HEADER);
 187
 188   memset(BlockAddress, 0, NumberOfBytes);
 189
 190   return(BlockAddress);
 191 }
 192
 193 /*
 194  * @implemented
 195  */
 196 VOID STDCALL
 197 ExFreePagedPool(IN PVOID Block)
 198 {
 199   PMM_PPOOL_FREE_BLOCK_HEADER PreviousBlock;
 200   PMM_PPOOL_USED_BLOCK_HEADER UsedBlock =
 201     (PMM_PPOOL_USED_BLOCK_HEADER)(Block - sizeof(MM_PPOOL_USED_BLOCK_HEADER));
 202   ULONG UsedSize = UsedBlock->Size;
 203   PMM_PPOOL_FREE_BLOCK_HEADER FreeBlock =
 204     (PMM_PPOOL_FREE_BLOCK_HEADER)UsedBlock;
 205   PMM_PPOOL_FREE_BLOCK_HEADER NextBlock;
 206   PMM_PPOOL_FREE_BLOCK_HEADER NextNextBlock;
 207
 208   ExAcquireFastMutex(&MmPagedPoolLock);
 209
 210   /*
 211    * Begin setting up the newly freed block's header.
 212    */
 213   FreeBlock->Size = UsedSize;
 214
 215   /*
 216    * Find the blocks immediately before and after the newly freed block on the free list.
 217    */
 218   PreviousBlock = NULL;
 219   NextBlock = MmPagedPoolFirstFreeBlock;
 220   while (NextBlock != NULL && NextBlock < FreeBlock)
 221     {
 222       PreviousBlock = NextBlock;
 223       NextBlock = NextBlock->NextFree;
 224     }
 225
 226   /*
 227    * Insert the freed block on the free list.
 228    */
 229   if (PreviousBlock == NULL)
 230     {
 231       FreeBlock->NextFree = MmPagedPoolFirstFreeBlock;
 232       MmPagedPoolFirstFreeBlock = FreeBlock;
 233     }
 234   else
 235     {
 236       PreviousBlock->NextFree = FreeBlock;
 237       FreeBlock->NextFree = NextBlock;
 238     }
 239
 240   /*
 241    * If the next block is immediately adjacent to the newly freed one then
 242    * merge them.
 243    */
 244   if (NextBlock != NULL &&
 245       ((PVOID)FreeBlock + FreeBlock->Size) == (PVOID)NextBlock)
 246     {
 247       FreeBlock->Size = FreeBlock->Size + NextBlock->Size;
 248       FreeBlock->NextFree = NextBlock->NextFree;
 249       NextNextBlock = NextBlock->NextFree;
 250     }
 251   else
 252     {
 253       NextNextBlock = NextBlock;
 254     }
 255
 256   /*
 257    * If the previous block is adjacent to the newly freed one then
 258    * merge them.
 259    */
 260   if (PreviousBlock != NULL &&
 261       ((PVOID)PreviousBlock + PreviousBlock->Size) == (PVOID)FreeBlock)
 262     {
 263       PreviousBlock->Size = PreviousBlock->Size + FreeBlock->Size;
 264       PreviousBlock->NextFree = NextNextBlock;
 265     }
 266
 267   ExReleaseFastMutex(&MmPagedPoolLock);
 268 }
 269
 270 /* EOF */