reactos/ntoskrnl/mm/ppool.c

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