ntoskrnl/mm/ppool.c

   1 /* $Id$
   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 PVOID STDCALL
  65 ExAllocatePagedPoolWithTag (IN  POOL_TYPE       PoolType,
  66                             IN  ULONG           NumberOfBytes,
  67                             IN  ULONG           Tag)
  68 {
  69   PMM_PPOOL_FREE_BLOCK_HEADER BestBlock;
  70   PMM_PPOOL_FREE_BLOCK_HEADER CurrentBlock;
  71   ULONG BlockSize;
  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;
  76   PVOID BlockAddress;
  77
  78   /*
  79    * Don't bother allocating anything for a zero-byte block.
  80    */
  81   if (NumberOfBytes == 0)
  82     {
  83       return(NULL);
  84     }
  85
  86   /*
  87    * Calculate the total number of bytes we will need.
  88    */
  89   BlockSize = NumberOfBytes + sizeof(MM_PPOOL_USED_BLOCK_HEADER);
  90   if (BlockSize < sizeof(MM_PPOOL_FREE_BLOCK_HEADER))
  91   {
  92     /* At least we need the size of the free block header. */
  93     BlockSize = sizeof(MM_PPOOL_FREE_BLOCK_HEADER);
  94   }
  95
  96   ExAcquireFastMutex(&MmPagedPoolLock);
  97
  98   /*
  99    * Find the best fitting block.
 100    */
 101   PreviousBlock = NULL;
 102   BestPreviousBlock = BestBlock = NULL;
 103   CurrentBlock = MmPagedPoolFirstFreeBlock;
 104   while (CurrentBlock != NULL)
 105     {
 106       if (CurrentBlock->Size >= BlockSize &&
 107           (BestBlock == NULL ||
 108            (BestBlock->Size - BlockSize) > (CurrentBlock->Size - BlockSize)))
 109         {
 110           BestPreviousBlock = PreviousBlock;
 111           BestBlock = CurrentBlock;
 112         }
 113
 114       PreviousBlock = CurrentBlock;
 115       CurrentBlock = CurrentBlock->NextFree;
 116     }
 117
 118   /*
 119    * We didn't find anything suitable at all.
 120    */
 121   if (BestBlock == NULL)
 122     {
 123       ExReleaseFastMutex(&MmPagedPoolLock);
 124       return(NULL);
 125     }
 126
 127   /*
 128    * Is there enough space to create a second block from the unused portion.
 129    */
 130   if ((BestBlock->Size - BlockSize) > sizeof(MM_PPOOL_FREE_BLOCK_HEADER))
 131     {
 132       ULONG NewSize = BestBlock->Size - BlockSize;
 133
 134       /*
 135        * Create the new free block.
 136        */
 137       NextBlock = (PMM_PPOOL_FREE_BLOCK_HEADER)((PVOID)BestBlock + BlockSize);
 138       NextBlock->Size = NewSize;
 139       NextBlock->NextFree = BestBlock->NextFree;
 140
 141       /*
 142        * Replace the old free block with it.
 143        */
 144       if (BestPreviousBlock == NULL)
 145         {
 146           MmPagedPoolFirstFreeBlock = NextBlock;
 147         }
 148       else
 149         {
 150           BestPreviousBlock->NextFree = NextBlock;
 151         }
 152
 153       /*
 154        * Create the new used block header.
 155        */
 156       NewBlock = (PMM_PPOOL_USED_BLOCK_HEADER)BestBlock;
 157       NewBlock->Size = BlockSize;
 158     }
 159   else
 160     {
 161       ULONG NewSize = BestBlock->Size;
 162
 163       /*
 164        * Remove the selected block from the list of free blocks.
 165        */
 166       if (BestPreviousBlock == NULL)
 167         {
 168           MmPagedPoolFirstFreeBlock = BestBlock->NextFree;
 169         }
 170       else
 171         {
 172           BestPreviousBlock->NextFree = BestBlock->NextFree;
 173         }
 174
 175       /*
 176        * Set up the header of the new block
 177        */
 178       NewBlock = (PMM_PPOOL_USED_BLOCK_HEADER)BestBlock;
 179       NewBlock->Size = NewSize;
 180     }
 181
 182   ExReleaseFastMutex(&MmPagedPoolLock);
 183
 184   BlockAddress = (PVOID)NewBlock + sizeof(MM_PPOOL_USED_BLOCK_HEADER);
 185
 186   memset(BlockAddress, 0, NumberOfBytes);
 187
 188   return(BlockAddress);
 189 }
 190
 191 VOID STDCALL
 192 ExFreePagedPool(IN PVOID Block)
 193 {
 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;
 202
 203   ExAcquireFastMutex(&MmPagedPoolLock);
 204
 205   /*
 206    * Begin setting up the newly freed block's header.
 207    */
 208   FreeBlock->Size = UsedSize;
 209
 210   /*
 211    * Find the blocks immediately before and after the newly freed block on the free list.
 212    */
 213   PreviousBlock = NULL;
 214   NextBlock = MmPagedPoolFirstFreeBlock;
 215   while (NextBlock != NULL && NextBlock < FreeBlock)
 216     {
 217       PreviousBlock = NextBlock;
 218       NextBlock = NextBlock->NextFree;
 219     }
 220
 221   /*
 222    * Insert the freed block on the free list.
 223    */
 224   if (PreviousBlock == NULL)
 225     {
 226       FreeBlock->NextFree = MmPagedPoolFirstFreeBlock;
 227       MmPagedPoolFirstFreeBlock = FreeBlock;
 228     }
 229   else
 230     {
 231       PreviousBlock->NextFree = FreeBlock;
 232       FreeBlock->NextFree = NextBlock;
 233     }
 234
 235   /*
 236    * If the next block is immediately adjacent to the newly freed one then
 237    * merge them.
 238    */
 239   if (NextBlock != NULL &&
 240       ((PVOID)FreeBlock + FreeBlock->Size) == (PVOID)NextBlock)
 241     {
 242       FreeBlock->Size = FreeBlock->Size + NextBlock->Size;
 243       FreeBlock->NextFree = NextBlock->NextFree;
 244       NextNextBlock = NextBlock->NextFree;
 245     }
 246   else
 247     {
 248       NextNextBlock = NextBlock;
 249     }
 250
 251   /*
 252    * If the previous block is adjacent to the newly freed one then
 253    * merge them.
 254    */
 255   if (PreviousBlock != NULL &&
 256       ((PVOID)PreviousBlock + PreviousBlock->Size) == (PVOID)FreeBlock)
 257     {
 258       PreviousBlock->Size = PreviousBlock->Size + FreeBlock->Size;
 259       PreviousBlock->NextFree = NextNextBlock;
 260     }
 261
 262   ExReleaseFastMutex(&MmPagedPoolLock);
 263 }
 264
 265 /* EOF */