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