reactos/ntoskrnl/mm/ppool.c

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