reactos/ntoskrnl/mm/ppool.c

   1 /* $Id: ppool.c,v 1.16 2003/08/04 08:26:19 hbirr 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 #define NDEBUG
  19 #include <internal/debug.h>
  20
  21 /* GLOBALS *******************************************************************/
  22
  23 /* Enable strict checking of the paged pool on every allocation */
  24 #define ENABLE_VALIDATE_POOL
  25
  26 #undef assert
  27 #define assert(x) if (!(x)) {DbgPrint("Assertion "#x" failed at %s:%d\n", __FILE__,__LINE__); KeBugCheck(0); }
  28 #define ASSERT_SIZE(n) assert ( (n) <= MmPagedPoolSize && (n) >= 0 )
  29 #define ASSERT_PTR(p) assert ( ((size_t)(p)) >= ((size_t)MmPagedPoolBase) && ((size_t)(p)) < ((size_t)(MmPagedPoolBase+MmPagedPoolSize)) )
  30
  31 // to disable buffer over/under-run detection, set the following macro to 0
  32 #define MM_PPOOL_BOUNDARY_BYTES 4
  33
  34 typedef struct _MM_PPOOL_FREE_BLOCK_HEADER
  35 {
  36   LONG Size;
  37   struct _MM_PPOOL_FREE_BLOCK_HEADER* NextFree;
  38 } MM_PPOOL_FREE_BLOCK_HEADER, *PMM_PPOOL_FREE_BLOCK_HEADER;
  39
  40 typedef struct _MM_PPOOL_USED_BLOCK_HEADER
  41 {
  42   LONG Size;
  43 #if MM_PPOOL_BOUNDARY_BYTES
  44   LONG UserSize; // how many bytes the user actually asked for...
  45 #endif//MM_PPOOL_BOUNDARY_BYTES
  46 } MM_PPOOL_USED_BLOCK_HEADER, *PMM_PPOOL_USED_BLOCK_HEADER;
  47
  48 PVOID MmPagedPoolBase;
  49 ULONG MmPagedPoolSize;
  50 static FAST_MUTEX MmPagedPoolLock;
  51 static PMM_PPOOL_FREE_BLOCK_HEADER MmPagedPoolFirstFreeBlock;
  52
  53 /* FUNCTIONS *****************************************************************/
  54
  55 inline static void* block_to_address ( PVOID blk )
  56 /*
  57  * FUNCTION: Translate a block header address to the corresponding block
  58  * address (internal)
  59  */
  60 {
  61   return ( (void *) ((char*)blk + sizeof(MM_PPOOL_USED_BLOCK_HEADER) + MM_PPOOL_BOUNDARY_BYTES) );
  62 }
  63
  64 inline static PMM_PPOOL_USED_BLOCK_HEADER address_to_block(PVOID addr)
  65 {
  66   return (PMM_PPOOL_USED_BLOCK_HEADER)
  67          ( ((char*)addr) - sizeof(MM_PPOOL_USED_BLOCK_HEADER) - MM_PPOOL_BOUNDARY_BYTES );
  68 }
  69
  70 VOID MmInitializePagedPool(VOID)
  71 {
  72   MmPagedPoolFirstFreeBlock = (PMM_PPOOL_FREE_BLOCK_HEADER)MmPagedPoolBase;
  73   /*
  74    * We are still at a high IRQL level at this point so explicitly commit
  75    * the first page of the paged pool before writing the first block header.
  76    */
  77   MmCommitPagedPoolAddress((PVOID)MmPagedPoolFirstFreeBlock);
  78   MmPagedPoolFirstFreeBlock->Size = MmPagedPoolSize;
  79   MmPagedPoolFirstFreeBlock->NextFree = NULL;
  80
  81   ExInitializeFastMutex(&MmPagedPoolLock);
  82 }
  83
  84 #ifdef ENABLE_VALIDATE_POOL
  85 static void VerifyPagedPool ( int line )
  86 {
  87   PMM_PPOOL_FREE_BLOCK_HEADER p = MmPagedPoolFirstFreeBlock;
  88   int count = 0;
  89   DPRINT ( "VerifyPagedPool(%i):\n", line );
  90   while ( p )
  91   {
  92     DPRINT ( "  0x%x: %lu bytes (next 0x%x)\n", p, p->Size, p->NextFree );
  93     ASSERT_PTR(p);
  94     ASSERT_SIZE(p->Size);
  95     count++;
  96     p = p->NextFree;
  97   }
  98   DPRINT ( "VerifyPagedPool(%i): (%lu blocks)\n", line, count );
  99 }
 100 #define VerifyPagedPool() VerifyPagedPool(__LINE__)
 101 #else
 102 #define VerifyPagedPool()
 103 #endif
 104
 105 /**********************************************************************
 106  * NAME                                                 INTERNAL
 107  *      ExAllocatePagedPoolWithTag@12
 108  *
 109  * DESCRIPTION
 110  *
 111  * ARGUMENTS
 112  *
 113  * RETURN VALUE
 114  */
 115 PVOID STDCALL
 116 ExAllocatePagedPoolWithTag (IN  POOL_TYPE       PoolType,
 117                             IN  ULONG           NumberOfBytes,
 118                             IN  ULONG           Tag)
 119 {
 120   PMM_PPOOL_FREE_BLOCK_HEADER BestBlock;
 121   PMM_PPOOL_FREE_BLOCK_HEADER CurrentBlock;
 122   ULONG BlockSize;
 123   PMM_PPOOL_USED_BLOCK_HEADER NewBlock;
 124   PMM_PPOOL_FREE_BLOCK_HEADER NextBlock;
 125   PMM_PPOOL_FREE_BLOCK_HEADER PreviousBlock;
 126   PMM_PPOOL_FREE_BLOCK_HEADER BestPreviousBlock;
 127   PVOID BlockAddress;
 128   ULONG Alignment;
 129
 130   /*
 131    * Don't bother allocating anything for a zero-byte block.
 132    */
 133   if (NumberOfBytes == 0)
 134     {
 135       return(NULL);
 136     }
 137
 138   DPRINT ( "ExAllocatePagedPoolWithTag(%i,%lu,%lu)\n", PoolType, NumberOfBytes, Tag );
 139   VerifyPagedPool();
 140
 141   if (NumberOfBytes >= PAGE_SIZE)
 142     {
 143       Alignment = PAGE_SIZE;
 144     }
 145   else if (PoolType == PagedPoolCacheAligned)
 146     {
 147       Alignment = MM_CACHE_LINE_SIZE;
 148     }
 149   else
 150     {
 151       Alignment = 0;
 152     }
 153
 154   /*
 155    * Calculate the total number of bytes we will need.
 156    */
 157   BlockSize = NumberOfBytes + sizeof(MM_PPOOL_USED_BLOCK_HEADER) + 2*MM_PPOOL_BOUNDARY_BYTES;
 158   if (BlockSize < sizeof(MM_PPOOL_FREE_BLOCK_HEADER))
 159   {
 160     /* At least we need the size of the free block header. */
 161     BlockSize = sizeof(MM_PPOOL_FREE_BLOCK_HEADER);
 162   }
 163
 164   ExAcquireFastMutex(&MmPagedPoolLock);
 165
 166   /*
 167    * Find the best-fitting block.
 168    */
 169   PreviousBlock = NULL;
 170   BestPreviousBlock = BestBlock = NULL;
 171   CurrentBlock = MmPagedPoolFirstFreeBlock;
 172   if ( Alignment > 0 )
 173     {
 174       PVOID BestAlignedAddr = NULL;
 175       while ( CurrentBlock != NULL )
 176         {
 177           PVOID Addr = block_to_address(CurrentBlock);
 178           PVOID CurrentBlockEnd = (PVOID)CurrentBlock + CurrentBlock->Size;
 179           /* calculate last size-aligned address available within this block */
 180           PVOID AlignedAddr = MM_ROUND_DOWN(CurrentBlockEnd-NumberOfBytes-MM_PPOOL_BOUNDARY_BYTES, Alignment);
 181           assert ( AlignedAddr+NumberOfBytes+MM_PPOOL_BOUNDARY_BYTES <= CurrentBlockEnd );
 182
 183           /* special case, this address is already size-aligned, and the right size */
 184           if ( Addr == AlignedAddr )
 185             {
 186               BestAlignedAddr = AlignedAddr;
 187               BestPreviousBlock = PreviousBlock;
 188               BestBlock = CurrentBlock;
 189               break;
 190             }
 191           else if ( Addr < (PVOID)address_to_block(AlignedAddr) )
 192             {
 193               /*
 194                * there's enough room to allocate our size-aligned memory out
 195                * of this block, see if it's a better choice than any previous
 196                * finds
 197                */
 198               if ( BestBlock == NULL || BestBlock->Size > CurrentBlock->Size )
 199                 {
 200                   BestAlignedAddr = AlignedAddr;
 201                   BestPreviousBlock = PreviousBlock;
 202                   BestBlock = CurrentBlock;
 203                 }
 204             }
 205
 206           PreviousBlock = CurrentBlock;
 207           CurrentBlock = CurrentBlock->NextFree;
 208         }
 209
 210       /*
 211        * we found a best block can/should we chop a few bytes off the beginning
 212        * into a separate memory block?
 213        */
 214       if ( BestBlock != NULL )
 215         {
 216           PVOID Addr = block_to_address(BestBlock);
 217           if ( BestAlignedAddr != Addr )
 218             {
 219               PMM_PPOOL_FREE_BLOCK_HEADER NewFreeBlock =
 220                 (PMM_PPOOL_FREE_BLOCK_HEADER)address_to_block(BestAlignedAddr);
 221               assert ( BestAlignedAddr > Addr );
 222               NewFreeBlock->Size = Addr + BestBlock->Size - BestAlignedAddr;
 223               ASSERT_SIZE(NewFreeBlock->Size);
 224               BestBlock->Size = (size_t)NewFreeBlock - (size_t)Addr;
 225               ASSERT_SIZE(BestBlock->Size);
 226
 227               DPRINT ( "breaking off preceding bytes into their own block...\n" );
 228               DPRINT ( "NewFreeBlock 0x%x Size %lu (Old Block's new size %lu) NextFree 0x%x\n",
 229                 NewFreeBlock, NewFreeBlock->Size, BestBlock->Size, BestBlock->NextFree );
 230
 231               /* insert the new block into the chain */
 232               NewFreeBlock->NextFree = BestBlock->NextFree;
 233               BestBlock->NextFree = NewFreeBlock;
 234
 235               /* we want the following code to use our size-aligned block */
 236               BestPreviousBlock = BestBlock;
 237               BestBlock = NewFreeBlock;
 238
 239               //VerifyPagedPool();
 240             }
 241         }
 242     }
 243   /*
 244    * non-size-aligned block search
 245    */
 246   else while ( CurrentBlock != NULL )
 247     {
 248       if (    CurrentBlock->Size >= BlockSize
 249            && ( BestBlock == NULL || BestBlock->Size > CurrentBlock->Size )
 250          )
 251         {
 252           BestPreviousBlock = PreviousBlock;
 253           BestBlock = CurrentBlock;
 254         }
 255
 256       PreviousBlock = CurrentBlock;
 257       CurrentBlock = CurrentBlock->NextFree;
 258     }
 259
 260   /*
 261    * We didn't find anything suitable at all.
 262    */
 263   if (BestBlock == NULL)
 264     {
 265       DPRINT("ExAllocatePagedPoolWithTag() - nothing suitable found, returning NULL\n" );
 266       ExReleaseFastMutex(&MmPagedPoolLock);
 267       return(NULL);
 268     }
 269
 270   DPRINT("BestBlock 0x%x NextFree 0x%x\n", BestBlock, BestBlock->NextFree );
 271
 272   //VerifyPagedPool();
 273
 274   /*
 275    * Is there enough space to create a second block from the unused portion.
 276    */
 277   if ( BestBlock->Size > BlockSize
 278     && (BestBlock->Size - BlockSize) > sizeof(MM_PPOOL_FREE_BLOCK_HEADER)
 279     )
 280     {
 281       ULONG NewSize = BestBlock->Size - BlockSize;
 282       ASSERT_SIZE ( NewSize );
 283
 284       //DPRINT("creating 2nd block from unused portion\n");
 285       DPRINT("BestBlock 0x%x Size 0x%x BlockSize 0x%x NewSize 0x%x\n",
 286         BestBlock, BestBlock->Size, BlockSize, NewSize );
 287
 288       /*
 289        * Create the new free block.
 290        */
 291       //DPRINT("creating the new free block");
 292       NextBlock = (PMM_PPOOL_FREE_BLOCK_HEADER)((char*)BestBlock + BlockSize);
 293       //DPRINT(".");
 294       NextBlock->Size = NewSize;
 295       ASSERT_SIZE ( NextBlock->Size );
 296       //DPRINT(".");
 297       NextBlock->NextFree = BestBlock->NextFree;
 298       //DPRINT(".\n");
 299
 300       /*
 301        * Replace the old free block with it.
 302        */
 303       //DPRINT("replacing old free block with it");
 304       if (BestPreviousBlock == NULL)
 305         {
 306           //DPRINT("(from beginning)");
 307           MmPagedPoolFirstFreeBlock = NextBlock;
 308         }
 309       else
 310         {
 311           //DPRINT("(from previous)");
 312           BestPreviousBlock->NextFree = NextBlock;
 313         }
 314       //DPRINT(".\n");
 315
 316       /*
 317        * Create the new used block header.
 318        */
 319       //DPRINT("create new used block header");
 320       NewBlock = (PMM_PPOOL_USED_BLOCK_HEADER)BestBlock;
 321       //DPRINT(".");
 322       NewBlock->Size = BlockSize;
 323       ASSERT_SIZE ( NewBlock->Size );
 324       //DPRINT(".\n");
 325     }
 326   else
 327     {
 328       ULONG NewSize = BestBlock->Size;
 329
 330       /*
 331        * Remove the selected block from the list of free blocks.
 332        */
 333       //DPRINT ( "Removing selected block from free block list\n" );
 334       if (BestPreviousBlock == NULL)
 335         {
 336           MmPagedPoolFirstFreeBlock = BestBlock->NextFree;
 337         }
 338       else
 339         {
 340           BestPreviousBlock->NextFree = BestBlock->NextFree;
 341         }
 342
 343       /*
 344        * Set up the header of the new block
 345        */
 346       NewBlock = (PMM_PPOOL_USED_BLOCK_HEADER)BestBlock;
 347       NewBlock->Size = NewSize;
 348       ASSERT_SIZE ( NewBlock->Size );
 349     }
 350
 351   VerifyPagedPool();
 352
 353   ExReleaseFastMutex(&MmPagedPoolLock);
 354
 355   BlockAddress = block_to_address ( NewBlock );
 356
 357   memset(BlockAddress, 0, NumberOfBytes);
 358
 359 #if MM_PPOOL_BOUNDARY_BYTES
 360   NewBlock->UserSize = NumberOfBytes;
 361   // write out buffer-overrun detection bytes
 362   {
 363     int i;
 364     PUCHAR Addr = (PUCHAR)BlockAddress;
 365     //DbgPrint ( "writing buffer-overrun detection bytes" );
 366     for ( i = 0; i < MM_PPOOL_BOUNDARY_BYTES; i++ )
 367     {
 368       //DbgPrint(".");
 369       *(Addr-i-1) = 0xCD;
 370       //DbgPrint("o");
 371       *(Addr+NewBlock->UserSize+i) = 0xCD;
 372     }
 373     //DbgPrint ( "done!\n" );
 374   }
 375 #endif//MM_PPOOL_BOUNDARY_BYTES
 376
 377   return(BlockAddress);
 378 }
 379
 380 VOID STDCALL
 381 ExFreePagedPool(IN PVOID Block)
 382 {
 383   PMM_PPOOL_FREE_BLOCK_HEADER PreviousBlock;
 384   PMM_PPOOL_USED_BLOCK_HEADER UsedBlock = address_to_block(Block);
 385   ULONG UsedSize = UsedBlock->Size;
 386   PMM_PPOOL_FREE_BLOCK_HEADER FreeBlock =
 387     (PMM_PPOOL_FREE_BLOCK_HEADER)UsedBlock;
 388   PMM_PPOOL_FREE_BLOCK_HEADER NextBlock;
 389   PMM_PPOOL_FREE_BLOCK_HEADER NextNextBlock;
 390
 391 #if MM_PPOOL_BOUNDARY_BYTES
 392   // write out buffer-overrun detection bytes
 393   {
 394     int i;
 395     PUCHAR Addr = (PUCHAR)Block;
 396     //DbgPrint ( "checking buffer-overrun detection bytes..." );
 397     for ( i = 0; i < MM_PPOOL_BOUNDARY_BYTES; i++ )
 398     {
 399       assert ( *(Addr-i-1) == 0xCD );
 400       assert ( *(Addr+UsedBlock->UserSize+i) == 0xCD );
 401     }
 402     //DbgPrint ( "done!\n" );
 403   }
 404 #endif//MM_PPOOL_BOUNDARY_BYTES
 405
 406   ExAcquireFastMutex(&MmPagedPoolLock);
 407
 408   /*
 409    * Begin setting up the newly freed block's header.
 410    */
 411   FreeBlock->Size = UsedSize;
 412   ASSERT_SIZE ( FreeBlock->Size );
 413
 414   /*
 415    * Find the blocks immediately before and after the newly freed block on the free list.
 416    */
 417   PreviousBlock = NULL;
 418   NextBlock = MmPagedPoolFirstFreeBlock;
 419   while (NextBlock != NULL && NextBlock < FreeBlock)
 420     {
 421       PreviousBlock = NextBlock;
 422       NextBlock = NextBlock->NextFree;
 423     }
 424
 425   /*
 426    * Insert the freed block on the free list.
 427    */
 428   if (PreviousBlock == NULL)
 429     {
 430       FreeBlock->NextFree = MmPagedPoolFirstFreeBlock;
 431       MmPagedPoolFirstFreeBlock = FreeBlock;
 432     }
 433   else
 434     {
 435       PreviousBlock->NextFree = FreeBlock;
 436       FreeBlock->NextFree = NextBlock;
 437     }
 438
 439   /*
 440    * If the next block is immediately adjacent to the newly freed one then
 441    * merge them.
 442    */
 443   if (NextBlock != NULL &&
 444       ((char*)FreeBlock + FreeBlock->Size) == (char*)NextBlock)
 445     {
 446       FreeBlock->Size = FreeBlock->Size + NextBlock->Size;
 447       ASSERT_SIZE ( FreeBlock->Size );
 448       FreeBlock->NextFree = NextBlock->NextFree;
 449       NextNextBlock = NextBlock->NextFree;
 450     }
 451   else
 452     {
 453       NextNextBlock = NextBlock;
 454     }
 455
 456   /*
 457    * If the previous block is adjacent to the newly freed one then
 458    * merge them.
 459    */
 460   if (PreviousBlock != NULL &&
 461       ((char*)PreviousBlock + PreviousBlock->Size) == (char*)FreeBlock)
 462     {
 463       PreviousBlock->Size = PreviousBlock->Size + FreeBlock->Size;
 464       ASSERT_SIZE ( PreviousBlock->Size );
 465       PreviousBlock->NextFree = NextNextBlock;
 466     }
 467
 468   VerifyPagedPool();
 469
 470   ExReleaseFastMutex(&MmPagedPoolLock);
 471 }
 472
 473 /* EOF */