reactos/ntoskrnl/mm/ppool.c

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