reactos/ntoskrnl/mm/npool.c

   1 /* $Id$
   2  *
   3  * COPYRIGHT:       See COPYING in the top level directory
   4  * PROJECT:         ReactOS kernel
   5  * FILE:            ntoskrnl/mm/npool.c
   6  * PURPOSE:         Implements the kernel memory pool
   7  *
   8  * PROGRAMMERS:     David Welch (welch@cwcom.net)
   9  *                  Iwan Fatahi (i_fatahi@hotmail.com)
  10  *                  Robert Bergkvist (fragdance@hotmail.com)
  11  *                  Hartmut Birr
  12  */
  13
  14 /* INCLUDES ****************************************************************/
  15
  16 #include <ntoskrnl.h>
  17 #define NDEBUG
  18 #include <internal/debug.h>
  19
  20 #ifdef ENABLE_VALIDATE_POOL
  21 #define VALIDATE_POOL validate_kernel_pool()
  22 #else
  23 #define VALIDATE_POOL
  24 #endif
  25
  26 #if 0
  27 #define POOL_TRACE(args...) do { DbgPrint(args); } while(0);
  28 #else
  29 #if defined(__GNUC__)
  30 #define POOL_TRACE(args...)
  31 #else
  32 #define POOL_TRACE
  33 #endif /* __GNUC__ */
  34 #endif
  35
  36 /* avl types ****************************************************************/
  37
  38 /* FIXME:
  39  *   This declarations should be moved into a separate header file.
  40  */
  41
  42 typedef struct _NODE
  43 {
  44    struct _NODE* link[2];
  45    struct _NODE* parent;
  46    signed char balance;
  47 }
  48 NODE, *PNODE;
  49
  50 /* TYPES *******************************************************************/
  51
  52 #define BLOCK_HDR_USED_MAGIC (0xdeadbeef)
  53 #define BLOCK_HDR_FREE_MAGIC (0xceadbeef)
  54
  55 /*
  56  * fields present at the start of a block (this is for internal use only)
  57  */
  58 typedef struct _HDR
  59 {
  60     ULONG Magic;
  61     ULONG Size;
  62     struct _HDR* previous;
  63 } HDR, *PHDR;
  64
  65 typedef struct _HDR_USED
  66 {
  67     HDR hdr;
  68     LIST_ENTRY ListEntry;
  69     ULONG Tag;
  70     PVOID Caller;
  71     LIST_ENTRY TagListEntry;
  72     BOOLEAN Dumped;
  73 } HDR_USED, *PHDR_USED;
  74
  75 typedef struct _HDR_FREE
  76 {
  77     HDR hdr;
  78     NODE Node;
  79 } HDR_FREE, *PHDR_FREE;
  80
  81 #define HDR_FREE_SIZE ROUND_UP(sizeof(HDR_FREE), MM_POOL_ALIGNMENT)
  82 #define HDR_USED_SIZE ROUND_UP(sizeof(HDR_USED), MM_POOL_ALIGNMENT)
  83
  84
  85 /* GLOBALS *****************************************************************/
  86
  87 extern PVOID MiNonPagedPoolStart;
  88 extern ULONG MiNonPagedPoolLength;
  89
  90 /*
  91  * Head of the list of free blocks
  92  */
  93 static PNODE FreeBlockListRoot = NULL;
  94
  95 /*
  96  * Head of the list of in use block
  97  */
  98 static LIST_ENTRY UsedBlockListHead;
  99
 100 static LIST_ENTRY AddressListHead;
 101
 102 /*
 103  * Count of free blocks
 104  */
 105 static ULONG EiNrFreeBlocks = 0;
 106
 107 /*
 108  * Count of used blocks
 109  */
 110 static ULONG EiNrUsedBlocks = 0;
 111
 112 /*
 113  * Lock that protects the non-paged pool data structures
 114  */
 115 static KSPIN_LOCK MmNpoolLock;
 116
 117 /*
 118  * Total memory used for free nonpaged pool blocks
 119  */
 120 ULONG EiFreeNonPagedPool = 0;
 121
 122 /*
 123  * Total memory used for nonpaged pool blocks
 124  */
 125 ULONG EiUsedNonPagedPool = 0;
 126
 127 /* Total quota for Non Paged Pool */
 128 ULONG MmTotalNonPagedPoolQuota = 0;
 129
 130 /*
 131  * Allocate a range of memory in the nonpaged pool
 132  */
 133 PVOID
 134 MiAllocNonPagedPoolRegion(unsigned int nr_pages);
 135
 136 VOID
 137 MiFreeNonPagedPoolRegion(PVOID Addr, ULONG Count, BOOLEAN Free);
 138
 139 #ifdef TAG_STATISTICS_TRACKING
 140 #define TAG_HASH_TABLE_SIZE       (1024)
 141 static LIST_ENTRY tag_hash_table[TAG_HASH_TABLE_SIZE];
 142 #endif /* TAG_STATISTICS_TRACKING */
 143
 144 static PULONG MiNonPagedPoolAllocMap;
 145 static ULONG MiNonPagedPoolNrOfPages;
 146
 147 /* avl helper functions ****************************************************/
 148
 149 void DumpFreeBlockNode(PNODE p)
 150 {
 151    static int count = 0;
 152    HDR_FREE* blk;
 153
 154    count++;
 155
 156    if (p)
 157    {
 158       DumpFreeBlockNode(p->link[0]);
 159       blk = CONTAINING_RECORD(p, HDR_FREE, Node);
 160       DbgPrint("%08x %8d (%d)\n", blk, blk->hdr.Size, count);
 161       DumpFreeBlockNode(p->link[1]);
 162    }
 163
 164    count--;
 165 }
 166 void DumpFreeBlockTree(void)
 167 {
 168    DbgPrint("--- Begin tree ------------------\n");
 169    DbgPrint("%08x\n", CONTAINING_RECORD(FreeBlockListRoot, HDR_FREE, Node));
 170    DumpFreeBlockNode(FreeBlockListRoot);
 171    DbgPrint("--- End tree --------------------\n");
 172 }
 173
 174 int compare_node(PNODE p1, PNODE p2)
 175 {
 176    HDR_FREE* blk1 = CONTAINING_RECORD(p1, HDR_FREE, Node);
 177    HDR_FREE* blk2 = CONTAINING_RECORD(p2, HDR_FREE, Node);
 178
 179    if (blk1->hdr.Size == blk2->hdr.Size)
 180    {
 181       if (blk1 < blk2)
 182       {
 183          return -1;
 184       }
 185       if (blk1 > blk2)
 186       {
 187          return 1;
 188       }
 189    }
 190    else
 191    {
 192       if (blk1->hdr.Size < blk2->hdr.Size)
 193       {
 194          return -1;
 195       }
 196       if (blk1->hdr.Size > blk2->hdr.Size)
 197       {
 198          return 1;
 199       }
 200    }
 201    return 0;
 202
 203 }
 204
 205 int compare_value(PVOID value, PNODE p)
 206 {
 207    HDR_FREE* blk = CONTAINING_RECORD(p, HDR_FREE, Node);
 208    ULONG v = *(PULONG)value;
 209
 210    if (v < blk->hdr.Size)
 211    {
 212       return -1;
 213    }
 214    if (v > blk->hdr.Size)
 215    {
 216       return 1;
 217    }
 218    return 0;
 219 }
 220
 221 /* avl functions **********************************************************/
 222
 223 /* FIXME:
 224  *   The avl functions should be moved into a separate file.
 225  */
 226
 227 /* The avl_insert and avl_remove are based on libavl (library for manipulation of binary trees). */
 228
 229 void avl_insert (PNODE * root, PNODE n, int (*compare)(PNODE, PNODE))
 230 {
 231    PNODE y;     /* Top node to update balance factor, and parent. */
 232    PNODE p, q;  /* Iterator, and parent. */
 233    PNODE w;     /* New root of rebalanced subtree. */
 234    int dir = 0; /* Direction to descend. */
 235
 236    n->link[0] = n->link[1] = n->parent = NULL;
 237    n->balance = 0;
 238
 239    y = *root;
 240    for (q = NULL, p = *root; p != NULL; q = p, p = p->link[dir])
 241    {
 242       dir = compare(n, p) > 0;
 243       if (p->balance != 0)
 244       {
 245          y = p;
 246       }
 247    }
 248
 249    n->parent = q;
 250    if (q != NULL)
 251    {
 252       q->link[dir] = n;
 253    }
 254    else
 255    {
 256       *root = n;
 257    }
 258
 259    if (*root == n)
 260    {
 261       return;
 262    }
 263
 264    for (p = n; p != y; p = q)
 265    {
 266       q = p->parent;
 267       dir = q->link[0] != p;
 268       if (dir == 0)
 269       {
 270          q->balance--;
 271       }
 272       else
 273       {
 274          q->balance++;
 275       }
 276    }
 277
 278    if (y->balance == -2)
 279    {
 280       PNODE x = y->link[0];
 281       if (x->balance == -1)
 282       {
 283          w = x;
 284          y->link[0] = x->link[1];
 285          x->link[1] = y;
 286          x->balance = y->balance = 0;
 287          x->parent = y->parent;
 288          y->parent = x;
 289          if (y->link[0] != NULL)
 290          {
 291             y->link[0]->parent = y;
 292          }
 293       }
 294       else
 295       {
 296          ASSERT(x->balance == +1);
 297          w = x->link[1];
 298          x->link[1] = w->link[0];
 299          w->link[0] = x;
 300          y->link[0] = w->link[1];
 301          w->link[1] = y;
 302          if (w->balance == -1)
 303          {
 304             x->balance = 0;
 305             y->balance = +1;
 306          }
 307          else if (w->balance == 0)
 308          {
 309             x->balance = y->balance = 0;
 310          }
 311          else /* |w->pavl_balance == +1| */
 312          {
 313             x->balance = -1;
 314             y->balance = 0;
 315          }
 316          w->balance = 0;
 317          w->parent = y->parent;
 318          x->parent = y->parent = w;
 319          if (x->link[1] != NULL)
 320          {
 321             x->link[1]->parent = x;
 322          }
 323          if (y->link[0] != NULL)
 324          {
 325             y->link[0]->parent = y;
 326          }
 327       }
 328    }
 329    else if (y->balance == +2)
 330    {
 331       PNODE x = y->link[1];
 332       if (x->balance == +1)
 333       {
 334          w = x;
 335          y->link[1] = x->link[0];
 336          x->link[0] = y;
 337          x->balance = y->balance = 0;
 338          x->parent = y->parent;
 339          y->parent = x;
 340          if (y->link[1] != NULL)
 341          {
 342             y->link[1]->parent = y;
 343          }
 344       }
 345       else
 346       {
 347          ASSERT(x->balance == -1);
 348          w = x->link[0];
 349          x->link[0] = w->link[1];
 350          w->link[1] = x;
 351          y->link[1] = w->link[0];
 352          w->link[0] = y;
 353          if (w->balance == 1)
 354          {
 355             x->balance = 0;
 356             y->balance = -1;
 357          }
 358          else if (w->balance == 0)
 359          {
 360             x->balance = y->balance = 0;
 361          }
 362          else /* |w->pavl_balance == -1| */
 363          {
 364             x->balance = +1;
 365             y->balance = 0;
 366          }
 367          w->balance = 0;
 368          w->parent = y->parent;
 369          x->parent = y->parent = w;
 370          if (x->link[0] != NULL)
 371          {
 372             x->link[0]->parent = x;
 373          }
 374          if (y->link[1] != NULL)
 375          {
 376             y->link[1]->parent = y;
 377          }
 378       }
 379    }
 380    else
 381    {
 382       return;
 383    }
 384    if (w->parent != NULL)
 385    {
 386       w->parent->link[y != w->parent->link[0]] = w;
 387    }
 388    else
 389    {
 390       *root = w;
 391    }
 392
 393    return;
 394 }
 395
 396 void avl_remove (PNODE *root, PNODE item, int (*compare)(PNODE, PNODE))
 397 {
 398    PNODE p;  /* Traverses tree to find node to delete. */
 399    PNODE q;  /* Parent of |p|. */
 400    int dir;  /* Side of |q| on which |p| is linked. */
 401
 402    if (root == NULL || *root == NULL)
 403    {
 404       return ;
 405    }
 406
 407    p = item;
 408    q = p->parent;
 409    if (q == NULL)
 410    {
 411       q = (PNODE) root;
 412       dir = 0;
 413    }
 414    else
 415    {
 416       dir = compare(p, q) > 0;
 417    }
 418
 419    if (p->link[1] == NULL)
 420    {
 421       q->link[dir] = p->link[0];
 422       if (q->link[dir] != NULL)
 423       {
 424          q->link[dir]->parent = p->parent;
 425       }
 426    }
 427    else
 428    {
 429       PNODE r = p->link[1];
 430       if (r->link[0] == NULL)
 431       {
 432          r->link[0] = p->link[0];
 433          q->link[dir] = r;
 434          r->parent = p->parent;
 435          if (r->link[0] != NULL)
 436          {
 437             r->link[0]->parent = r;
 438          }
 439          r->balance = p->balance;
 440          q = r;
 441          dir = 1;
 442       }
 443       else
 444       {
 445          PNODE s = r->link[0];
 446          while (s->link[0] != NULL)
 447          {
 448             s = s->link[0];
 449          }
 450          r = s->parent;
 451          r->link[0] = s->link[1];
 452          s->link[0] = p->link[0];
 453          s->link[1] = p->link[1];
 454          q->link[dir] = s;
 455          if (s->link[0] != NULL)
 456          {
 457             s->link[0]->parent = s;
 458          }
 459          s->link[1]->parent = s;
 460          s->parent = p->parent;
 461          if (r->link[0] != NULL)
 462          {
 463             r->link[0]->parent = r;
 464          }
 465          s->balance = p->balance;
 466          q = r;
 467          dir = 0;
 468       }
 469    }
 470
 471    item->link[0] = item->link[1] = item->parent = NULL;
 472    item->balance = 0;
 473
 474    while (q != (PNODE) root)
 475    {
 476       PNODE y = q;
 477
 478       if (y->parent != NULL)
 479       {
 480          q = y->parent;
 481       }
 482       else
 483       {
 484          q = (PNODE) root;
 485       }
 486
 487       if (dir == 0)
 488       {
 489          dir = q->link[0] != y;
 490          y->balance++;
 491          if (y->balance == +1)
 492          {
 493             break;
 494          }
 495          else if (y->balance == +2)
 496          {
 497             PNODE x = y->link[1];
 498             if (x->balance == -1)
 499             {
 500                PNODE w;
 501
 502                ASSERT(x->balance == -1);
 503                w = x->link[0];
 504                x->link[0] = w->link[1];
 505                w->link[1] = x;
 506                y->link[1] = w->link[0];
 507                w->link[0] = y;
 508                if (w->balance == +1)
 509                {
 510                   x->balance = 0;
 511                   y->balance = -1;
 512                }
 513                else if (w->balance == 0)
 514                {
 515                   x->balance = y->balance = 0;
 516                }
 517                else /* |w->pavl_balance == -1| */
 518                {
 519                   x->balance = +1;
 520                   y->balance = 0;
 521                }
 522                w->balance = 0;
 523                w->parent = y->parent;
 524                x->parent = y->parent = w;
 525                if (x->link[0] != NULL)
 526                {
 527                   x->link[0]->parent = x;
 528                }
 529                if (y->link[1] != NULL)
 530                {
 531                   y->link[1]->parent = y;
 532                }
 533                q->link[dir] = w;
 534             }
 535             else
 536             {
 537                y->link[1] = x->link[0];
 538                x->link[0] = y;
 539                x->parent = y->parent;
 540                y->parent = x;
 541                if (y->link[1] != NULL)
 542                {
 543                   y->link[1]->parent = y;
 544                }
 545                q->link[dir] = x;
 546                if (x->balance == 0)
 547                {
 548                   x->balance = -1;
 549                   y->balance = +1;
 550                   break;
 551                }
 552                else
 553                {
 554                   x->balance = y->balance = 0;
 555                   y = x;
 556                }
 557             }
 558          }
 559       }
 560       else
 561       {
 562          dir = q->link[0] != y;
 563          y->balance--;
 564          if (y->balance == -1)
 565          {
 566             break;
 567          }
 568          else if (y->balance == -2)
 569          {
 570             PNODE x = y->link[0];
 571             if (x->balance == +1)
 572             {
 573                PNODE w;
 574                ASSERT(x->balance == +1);
 575                w = x->link[1];
 576                x->link[1] = w->link[0];
 577                w->link[0] = x;
 578                y->link[0] = w->link[1];
 579                w->link[1] = y;
 580                if (w->balance == -1)
 581                {
 582                   x->balance = 0;
 583                   y->balance = +1;
 584                }
 585                else if (w->balance == 0)
 586                {
 587                   x->balance = y->balance = 0;
 588                }
 589                else /* |w->pavl_balance == +1| */
 590                {
 591                   x->balance = -1;
 592                   y->balance = 0;
 593                }
 594                w->balance = 0;
 595                w->parent = y->parent;
 596                x->parent = y->parent = w;
 597                if (x->link[1] != NULL)
 598                {
 599                   x->link[1]->parent = x;
 600                }
 601                if (y->link[0] != NULL)
 602                {
 603                   y->link[0]->parent = y;
 604                }
 605                q->link[dir] = w;
 606             }
 607             else
 608             {
 609                y->link[0] = x->link[1];
 610                x->link[1] = y;
 611                x->parent = y->parent;
 612                y->parent = x;
 613                if (y->link[0] != NULL)
 614                {
 615                   y->link[0]->parent = y;
 616                }
 617                q->link[dir] = x;
 618                if (x->balance == 0)
 619                {
 620                   x->balance = +1;
 621                   y->balance = -1;
 622                   break;
 623                }
 624                else
 625                {
 626                   x->balance = y->balance = 0;
 627                   y = x;
 628                }
 629             }
 630          }
 631       }
 632    }
 633
 634 }
 635
 636 PNODE _cdecl avl_get_first(PNODE root)
 637 {
 638    PNODE p;
 639    if (root == NULL)
 640    {
 641       return NULL;
 642    }
 643    p = root;
 644    while (p->link[0])
 645    {
 646       p = p->link[0];
 647    }
 648    return p;
 649 }
 650
 651 PNODE avl_get_next(PNODE root, PNODE p)
 652 {
 653    PNODE q;
 654    if (p->link[1])
 655    {
 656       p = p->link[1];
 657       while(p->link[0])
 658       {
 659          p = p->link[0];
 660       }
 661       return p;
 662    }
 663    else
 664    {
 665       q = p->parent;
 666       while (q && q->link[1] == p)
 667       {
 668          p = q;
 669          q = q->parent;
 670       }
 671       if (q == NULL)
 672       {
 673          return NULL;
 674       }
 675       else
 676       {
 677          return q;
 678       }
 679    }
 680 }
 681
 682 PNODE avl_find_equal_or_greater(PNODE root, ULONG size, int (compare)(PVOID, PNODE))
 683 {
 684    PNODE p;
 685    PNODE prev = NULL;
 686    int cmp;
 687
 688    for (p = root; p != NULL;)
 689    {
 690       cmp = compare((PVOID)&size, p);
 691       if (cmp < 0)
 692       {
 693          prev = p;
 694          p = p->link[0];
 695       }
 696       else if (cmp > 0)
 697       {
 698          p = p->link[1];
 699       }
 700       else
 701       {
 702          while (p->link[0])
 703          {
 704             cmp = compare((PVOID)&size, p->link[0]);
 705             if (cmp != 0)
 706             {
 707                break;
 708             }
 709             p = p->link[0];
 710          }
 711          return p;
 712       }
 713    }
 714    return prev;
 715 }
 716
 717 /* non paged pool functions ************************************************/
 718
 719 #ifdef TAG_STATISTICS_TRACKING
 720 VOID
 721 MiRemoveFromTagHashTable(HDR_USED* block)
 722 /*
 723  * Remove a block from the tag hash table
 724  */
 725 {
 726    if (block->Tag == 0)
 727    {
 728       return;
 729    }
 730    RemoveEntryList(&block->TagListEntry);
 731 }
 732
 733 VOID
 734 MiAddToTagHashTable(HDR_USED* block)
 735 /*
 736  * Add a block to the tag hash table
 737  */
 738 {
 739    ULONG hash;
 740
 741    if (block->Tag == 0)
 742    {
 743       return;
 744    }
 745
 746    hash = block->Tag % TAG_HASH_TABLE_SIZE;
 747
 748    InsertHeadList(&tag_hash_table[hash], &block->TagListEntry);
 749 }
 750 #endif /* TAG_STATISTICS_TRACKING */
 751
 752 #if defined(TAG_STATISTICS_TRACKING)
 753 VOID STATIC
 754 MiDumpTagStats(ULONG CurrentTag, ULONG CurrentNrBlocks, ULONG CurrentSize)
 755 {
 756    CHAR c1, c2, c3, c4;
 757
 758    c1 = (CHAR)((CurrentTag >> 24) & 0xFF);
 759    c2 = (CHAR)((CurrentTag >> 16) & 0xFF);
 760    c3 = (CHAR)((CurrentTag >> 8) & 0xFF);
 761    c4 = (CHAR)(CurrentTag & 0xFF);
 762
 763    if (isprint(c1) && isprint(c2) && isprint(c3) && isprint(c4))
 764    {
 765       DbgPrint("Tag %x (%c%c%c%c) Blocks %d Total Size %d Average Size %d\n",
 766                CurrentTag, c4, c3, c2, c1, CurrentNrBlocks,
 767                CurrentSize, CurrentSize / CurrentNrBlocks);
 768    }
 769    else
 770    {
 771       DbgPrint("Tag %x Blocks %d Total Size %d Average Size %d\n",
 772                CurrentTag, CurrentNrBlocks, CurrentSize,
 773                CurrentSize / CurrentNrBlocks);
 774    }
 775 }
 776 #endif /* defined(TAG_STATISTICS_TRACKING) */
 777
 778 VOID
 779 MiDebugDumpNonPagedPoolStats(BOOLEAN NewOnly)
 780 {
 781 #if defined(TAG_STATISTICS_TRACKING)
 782    ULONG i;
 783    HDR_USED* current;
 784    ULONG CurrentTag;
 785    ULONG CurrentNrBlocks = 0;
 786    ULONG CurrentSize = 0;
 787    ULONG TotalBlocks;
 788    ULONG TotalSize;
 789    ULONG Size;
 790    LIST_ENTRY tmpListHead;
 791    PLIST_ENTRY current_entry;
 792
 793    DbgPrint("******* Dumping non paging pool stats ******\n");
 794    TotalBlocks = 0;
 795    TotalSize = 0;
 796    for (i = 0; i < TAG_HASH_TABLE_SIZE; i++)
 797    {
 798       InitializeListHead(&tmpListHead);
 799
 800       while (!IsListEmpty(&tag_hash_table[i]))
 801       {
 802          CurrentTag = 0;
 803
 804          current_entry = tag_hash_table[i].Flink;
 805          while (current_entry != &tag_hash_table[i])
 806          {
 807             current = CONTAINING_RECORD(current_entry, HDR_USED, TagListEntry);
 808             current_entry = current_entry->Flink;
 809             if (CurrentTag == 0)
 810             {
 811                CurrentTag = current->Tag;
 812                CurrentNrBlocks = 0;
 813                CurrentSize = 0;
 814             }
 815             if (current->Tag == CurrentTag)
 816             {
 817                RemoveEntryList(&current->TagListEntry);
 818                InsertHeadList(&tmpListHead, &current->TagListEntry);
 819                if (!NewOnly || !current->Dumped)
 820                {
 821                   CurrentNrBlocks++;
 822                   TotalBlocks++;
 823                   CurrentSize += current->hdr.Size;
 824                   TotalSize += current->hdr.Size;
 825                   current->Dumped = TRUE;
 826                }
 827             }
 828          }
 829          if (CurrentTag != 0 && CurrentNrBlocks != 0)
 830          {
 831             MiDumpTagStats(CurrentTag, CurrentNrBlocks, CurrentSize);
 832          }
 833       }
 834       if (!IsListEmpty(&tmpListHead))
 835       {
 836          tag_hash_table[i].Flink = tmpListHead.Flink;
 837          tag_hash_table[i].Flink->Blink = &tag_hash_table[i];
 838          tag_hash_table[i].Blink = tmpListHead.Blink;
 839          tag_hash_table[i].Blink->Flink = &tag_hash_table[i];
 840       }
 841    }
 842    if (TotalBlocks != 0)
 843    {
 844       DbgPrint("TotalBlocks %d TotalSize %d AverageSize %d\n",
 845                TotalBlocks, TotalSize, TotalSize / TotalBlocks);
 846    }
 847    else
 848    {
 849       DbgPrint("TotalBlocks %d TotalSize %d\n",
 850                TotalBlocks, TotalSize);
 851    }
 852    Size = EiFreeNonPagedPool - (MiNonPagedPoolLength - MiNonPagedPoolNrOfPages * PAGE_SIZE);
 853    DbgPrint("Freeblocks %d TotalFreeSize %d AverageFreeSize %d\n",
 854             EiNrFreeBlocks, Size, EiNrFreeBlocks ? Size / EiNrFreeBlocks : 0);
 855    DbgPrint("***************** Dump Complete ***************\n");
 856 #endif /* defined(TAG_STATISTICS_TRACKING) */
 857 }
 858
 859 VOID
 860 MiDebugDumpNonPagedPool(BOOLEAN NewOnly)
 861 {
 862 #if defined(POOL_DEBUG_APIS)
 863    HDR_USED* current;
 864    PLIST_ENTRY current_entry;
 865    KIRQL oldIrql;
 866
 867    KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
 868
 869    DbgPrint("******* Dumping non paging pool contents ******\n");
 870    current_entry = UsedBlockListHead.Flink;
 871    while (current_entry != &UsedBlockListHead)
 872    {
 873       current = CONTAINING_RECORD(current_entry, HDR_USED, ListEntry);
 874       if (!NewOnly || !current->Dumped)
 875       {
 876          CHAR c1, c2, c3, c4;
 877
 878          c1 = (CHAR)((current->Tag >> 24) & 0xFF);
 879          c2 = (CHAR)((current->Tag >> 16) & 0xFF);
 880          c3 = (CHAR)((current->Tag >> 8) & 0xFF);
 881          c4 = (CHAR)(current->Tag & 0xFF);
 882
 883          if (isprint(c1) && isprint(c2) && isprint(c3) && isprint(c4))
 884          {
 885             DbgPrint("Size 0x%x Tag 0x%x (%c%c%c%c) Allocator 0x%x\n",
 886                      current->hdr.Size, current->Tag, c4, c3, c2, c1,
 887                      current->Caller);
 888          }
 889          else
 890          {
 891             DbgPrint("Size 0x%x Tag 0x%x Allocator 0x%x\n",
 892                      current->hdr.Size, current->Tag, current->Caller);
 893          }
 894          current->Dumped = TRUE;
 895       }
 896       current_entry = current_entry->Flink;
 897    }
 898    DbgPrint("***************** Dump Complete ***************\n");
 899    KeReleaseSpinLock(&MmNpoolLock, oldIrql);
 900 #endif
 901 }
 902
 903 #ifdef ENABLE_VALIDATE_POOL
 904 static void validate_free_list(void)
 905 /*
 906  * FUNCTION: Validate the integrity of the list of free blocks
 907  */
 908 {
 909    HDR_FREE* current;
 910    unsigned int blocks_seen=0;
 911    PNODE p;
 912
 913    p = avl_get_first(FreeBlockListRoot);
 914
 915    while(p)
 916    {
 917       PVOID base_addr;
 918
 919       current = CONTAINING_RECORD(p, HDR_FREE, Node);
 920       base_addr = (PVOID)current;
 921
 922       if (current->hdr.Magic != BLOCK_HDR_FREE_MAGIC)
 923       {
 924          DbgPrint("Bad block magic (probable pool corruption) at %x\n",
 925                   current);
 926          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
 927       }
 928
 929       if (base_addr < MiNonPagedPoolStart ||
 930             (ULONG_PTR)base_addr + current->hdr.Size > (ULONG_PTR)MiNonPagedPoolStart + MiNonPagedPoolLength)
 931       {
 932          DbgPrint("Block %x found outside pool area\n",current);
 933          DbgPrint("Size %d\n",current->hdr.Size);
 934          DbgPrint("Limits are %x %x\n",MiNonPagedPoolStart,
 935                   (ULONG_PTR)MiNonPagedPoolStart+MiNonPagedPoolLength);
 936          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
 937       }
 938       blocks_seen++;
 939       if (blocks_seen > EiNrFreeBlocks)
 940       {
 941          DbgPrint("Too many blocks on free list\n");
 942          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
 943       }
 944       p = avl_get_next(FreeBlockListRoot, p);
 945    }
 946 }
 947
 948 static void validate_used_list(void)
 949 /*
 950  * FUNCTION: Validate the integrity of the list of used blocks
 951  */
 952 {
 953    HDR_USED* current;
 954    PLIST_ENTRY current_entry;
 955    unsigned int blocks_seen=0;
 956
 957    current_entry = UsedBlockListHead.Flink;
 958    while (current_entry != &UsedBlockListHead)
 959    {
 960       PVOID base_addr;
 961
 962       current = CONTAINING_RECORD(current_entry, HDR_USED, ListEntry);
 963       base_addr = (PVOID)current;
 964
 965       if (current->hdr.Magic != BLOCK_HDR_USED_MAGIC)
 966       {
 967          DbgPrint("Bad block magic (probable pool corruption) at %x\n",
 968                   current);
 969          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
 970       }
 971       if (base_addr < MiNonPagedPoolStart ||
 972             ((ULONG_PTR)base_addr+current->hdr.Size) >
 973             (ULONG_PTR)MiNonPagedPoolStart+MiNonPagedPoolLength)
 974       {
 975          DbgPrint("Block %x found outside pool area\n",current);
 976          DbgPrint("Size %d\n",current->hdr.Size);
 977          DbgPrint("Limits are %x %x\n",MiNonPagedPoolStart,
 978                   (ULONG_PTR)MiNonPagedPoolStart+MiNonPagedPoolLength);
 979          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
 980       }
 981       blocks_seen++;
 982       if (blocks_seen > EiNrUsedBlocks)
 983       {
 984          DbgPrint("Too many blocks on used list\n");
 985          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
 986       }
 987       if (current->ListEntry.Flink != &UsedBlockListHead &&
 988             current->ListEntry.Flink->Blink != &current->ListEntry)
 989       {
 990          DbgPrint("%s:%d:Break in list (current %x next %x "
 991                   "current->next->previous %x)\n",
 992                   __FILE__,__LINE__,current, current->ListEntry.Flink,
 993                   current->ListEntry.Flink->Blink);
 994          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
 995       }
 996
 997       current_entry = current_entry->Flink;
 998    }
 999 }
1000
1001 static void check_duplicates(HDR* blk)
1002 /*
1003  * FUNCTION: Check a block has no duplicates
1004  * ARGUMENTS:
1005  *           blk = block to check
1006  * NOTE: Bug checks if duplicates are found
1007  */
1008 {
1009    ULONG_PTR base = (ULONG_PTR)blk;
1010    ULONG_PTR last = (ULONG_PTR)blk + blk->Size;
1011    PLIST_ENTRY current_entry;
1012    PNODE p;
1013    HDR_FREE* free;
1014    HDR_USED* used;
1015
1016    p = avl_get_first(FreeBlockListRoot);
1017
1018    while (p)
1019    {
1020       free = CONTAINING_RECORD(p, HDR_FREE, Node);
1021       if (free->hdr.Magic != BLOCK_HDR_FREE_MAGIC)
1022       {
1023          DbgPrint("Bad block magic (probable pool corruption) at %x\n",
1024                   free);
1025          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1026       }
1027
1028       if ( (ULONG_PTR)free > base && (ULONG_PTR)free < last )
1029       {
1030          DbgPrint("intersecting blocks on list\n");
1031          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1032       }
1033       if  ( (ULONG_PTR)free < base &&
1034             ((ULONG_PTR)free + free->hdr.Size) > base )
1035       {
1036          DbgPrint("intersecting blocks on list\n");
1037          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1038       }
1039       p = avl_get_next(FreeBlockListRoot, p);
1040    }
1041
1042    current_entry = UsedBlockListHead.Flink;
1043    while (current_entry != &UsedBlockListHead)
1044    {
1045       used = CONTAINING_RECORD(current_entry, HDR_USED, ListEntry);
1046
1047       if ( (ULONG_PTR)used > base && (ULONG_PTR)used < last )
1048       {
1049          DbgPrint("intersecting blocks on list\n");
1050          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1051       }
1052       if  ( (ULONG_PTR)current < base &&
1053             ((ULONG_PTR)current + current->hdr.Size) > base )
1054       {
1055          DbgPrint("intersecting blocks on list\n");
1056          KEBUGCHECK(/*KBUG_POOL_FREE_LIST_CORRUPT*/0);
1057       }
1058
1059       current_entry = current_entry->Flink;
1060    }
1061
1062 }
1063
1064 static void validate_kernel_pool(void)
1065 /*
1066  * FUNCTION: Checks the integrity of the kernel memory heap
1067  */
1068 {
1069    HDR_FREE* free;
1070    HDR_USED* used;
1071    PLIST_ENTRY current_entry;
1072    PNODE p;
1073
1074    validate_free_list();
1075    validate_used_list();
1076
1077    p = avl_get_first(FreeBlockListRoot);
1078    while (p)
1079    {
1080       freet = CONTAINING_RECORD(p, HDR_FREE, Node);
1081       check_duplicates(&free->hdr);
1082       p = avl_get_next(FreeBlockListRoot, p);
1083    }
1084    current_entry = UsedBlockListHead.Flink;
1085    while (current_entry != &UsedBlockListHead)
1086    {
1087       used = CONTAINING_RECORD(current_entry, HDR_USED, ListEntry);
1088       check_duplicates(&used->hdr);
1089       current_entry = current_entry->Flink;
1090    }
1091 }
1092 #endif
1093
1094 #if 0
1095 STATIC VOID
1096 free_pages(HDR_FREE* blk)
1097 {
1098    ULONG start;
1099    ULONG end;
1100
1101    start = (ULONG_PTR)blk;
1102    end = (ULONG_PTR)blk + blk->hdr.Size;
1103
1104    /*
1105     * If the block doesn't contain a whole page then there is nothing to do
1106     */
1107    if (PAGE_ROUND_UP(start) >= PAGE_ROUND_DOWN(end))
1108    {
1109       return;
1110    }
1111 }
1112 #endif
1113
1114 static void remove_from_used_list(HDR_USED* current)
1115 {
1116    RemoveEntryList(&current->ListEntry);
1117    EiUsedNonPagedPool -= current->hdr.Size;
1118    EiNrUsedBlocks--;
1119 }
1120
1121 static void remove_from_free_list(HDR_FREE* current)
1122 {
1123    DPRINT("remove_from_free_list %d\n", current->hdr.Size);
1124
1125    avl_remove(&FreeBlockListRoot, &current->Node, compare_node);
1126
1127    EiFreeNonPagedPool -= current->hdr.Size;
1128    EiNrFreeBlocks--;
1129    DPRINT("remove_from_free_list done\n");
1130 #ifdef DUMP_AVL
1131
1132    DumpFreeBlockTree();
1133 #endif
1134 }
1135
1136 static void
1137 add_to_free_list(HDR_FREE* blk)
1138 /*
1139  * FUNCTION: add the block to the free list (internal)
1140  */
1141 {
1142    HDR_FREE* current;
1143    BOOL UpdatePrevPtr = FALSE;
1144
1145    DPRINT("add_to_free_list (%d)\n", blk->hdr.Size);
1146
1147    EiNrFreeBlocks++;
1148
1149    current = (HDR_FREE*)blk->hdr.previous;
1150    if (current && current->hdr.Magic == BLOCK_HDR_FREE_MAGIC)
1151    {
1152       remove_from_free_list(current);
1153       current->hdr.Size = current->hdr.Size + blk->hdr.Size;
1154       current->hdr.Magic = BLOCK_HDR_USED_MAGIC;
1155       memset(blk, 0xcc, HDR_USED_SIZE);
1156       blk = current;
1157       UpdatePrevPtr = TRUE;
1158    }
1159
1160    current = (HDR_FREE*)((ULONG_PTR)blk + blk->hdr.Size);
1161    if ((char*)current < (char*)MiNonPagedPoolStart + MiNonPagedPoolLength &&
1162          current->hdr.Magic == BLOCK_HDR_FREE_MAGIC)
1163    {
1164       remove_from_free_list(current);
1165       blk->hdr.Size += current->hdr.Size;
1166       memset(current, 0xcc, HDR_FREE_SIZE);
1167       UpdatePrevPtr = TRUE;
1168       current = (HDR_FREE*)((ULONG_PTR)blk + blk->hdr.Size);
1169    }
1170    if (UpdatePrevPtr &&
1171          (char*)current < (char*)MiNonPagedPoolStart + MiNonPagedPoolLength)
1172    {
1173       current->hdr.previous = &blk->hdr;
1174    }
1175    DPRINT("%d\n", blk->hdr.Size);
1176    blk->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
1177    EiFreeNonPagedPool += blk->hdr.Size;
1178    avl_insert(&FreeBlockListRoot, &blk->Node, compare_node);
1179    DPRINT("add_to_free_list done\n");
1180 #ifdef DUMP_AVL
1181
1182    DumpFreeBlockTree();
1183 #endif
1184 }
1185
1186 static void add_to_used_list(HDR_USED* blk)
1187 /*
1188  * FUNCTION: add the block to the used list (internal)
1189  */
1190 {
1191    InsertHeadList(&UsedBlockListHead, &blk->ListEntry);
1192    EiUsedNonPagedPool += blk->hdr.Size;
1193    EiNrUsedBlocks++;
1194 }
1195
1196
1197 static BOOLEAN
1198 grow_block(HDR_FREE* blk, PVOID end)
1199 {
1200    NTSTATUS Status;
1201    PFN_TYPE Page[32];
1202    ULONG_PTR StartIndex, EndIndex;
1203    ULONG i, j, k;
1204
1205    StartIndex = (ULONG_PTR)(PAGE_ROUND_UP((ULONG_PTR)blk + HDR_FREE_SIZE - (ULONG_PTR)MiNonPagedPoolStart)) / PAGE_SIZE;
1206    EndIndex = ((ULONG_PTR)PAGE_ROUND_UP(end) - (ULONG_PTR)MiNonPagedPoolStart) / PAGE_SIZE;
1207
1208
1209    for (i = StartIndex; i < EndIndex; i++)
1210    {
1211       if (!(MiNonPagedPoolAllocMap[i / 32] & (1 << (i % 32))))
1212       {
1213          for (j = i + 1; j < EndIndex && j - i < 32; j++)
1214          {
1215             if (MiNonPagedPoolAllocMap[j / 32] & (1 << (j % 32)))
1216             {
1217                break;
1218             }
1219          }
1220          for (k = 0; k < j - i; k++)
1221          {
1222             Status = MmRequestPageMemoryConsumer(MC_NPPOOL, FALSE, &Page[k]);
1223             if (!NT_SUCCESS(Status))
1224             {
1225                for (i = 0; i < k; i++)
1226                {
1227                  MmReleasePageMemoryConsumer(MC_NPPOOL, Page[i]);
1228                }
1229                return FALSE;
1230             }
1231          }
1232          Status = MmCreateVirtualMapping(NULL,
1233                                          (PVOID)((ULONG_PTR)MiNonPagedPoolStart + i * PAGE_SIZE),
1234                                          PAGE_READWRITE|PAGE_SYSTEM,
1235                                          Page,
1236                                          k);
1237          if (!NT_SUCCESS(Status))
1238          {
1239             for (i = 0; i < k; i++)
1240             {
1241               MmReleasePageMemoryConsumer(MC_NPPOOL, Page[i]);
1242             }
1243             return FALSE;
1244          }
1245          for (j = i; j < k + i; j++)
1246          {
1247             MiNonPagedPoolAllocMap[j / 32] |= (1 << (j % 32));
1248          }
1249          MiNonPagedPoolNrOfPages += k;
1250          i += k - 1;
1251       }
1252    }
1253    return TRUE;
1254 }
1255
1256 static HDR_USED* get_block(unsigned int size, unsigned long alignment)
1257 {
1258    HDR_FREE *blk, *current, *previous = NULL, *next = NULL, *best = NULL;
1259    ULONG previous_size = 0, current_size, next_size = 0, new_size;
1260    PVOID end;
1261    PVOID addr, aligned_addr, best_aligned_addr=NULL;
1262    PNODE p;
1263
1264    DPRINT("get_block %d\n", size);
1265
1266    p = avl_find_equal_or_greater(FreeBlockListRoot, size + HDR_USED_SIZE, compare_value);
1267    while (p)
1268    {
1269       current = CONTAINING_RECORD(p, HDR_FREE, Node);
1270       addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE);
1271       /* calculate first aligned address available within this block */
1272       aligned_addr = alignment > 0 ? MM_ROUND_UP(addr, alignment) : addr;
1273       if (size < PAGE_SIZE)
1274       {
1275          /* check that the block is in one page */
1276          if (PAGE_ROUND_DOWN(aligned_addr) != PAGE_ROUND_DOWN((ULONG_PTR)aligned_addr + size - 1))
1277          {
1278             aligned_addr = (PVOID)PAGE_ROUND_UP(aligned_addr);
1279          }
1280       }
1281       DPRINT("%x %x\n", addr, aligned_addr);
1282       if (aligned_addr != addr)
1283       {
1284          while((ULONG_PTR)aligned_addr - (ULONG_PTR)addr < HDR_FREE_SIZE)
1285          {
1286             if (alignment == 0)
1287             {
1288                aligned_addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE + HDR_FREE_SIZE);
1289             }
1290             else
1291             {
1292                aligned_addr = MM_ROUND_UP((PVOID)((ULONG_PTR)current + HDR_USED_SIZE + HDR_FREE_SIZE), alignment);
1293             }
1294             if (size < PAGE_SIZE)
1295             {
1296                /* check that the block is in one page */
1297                if (PAGE_ROUND_DOWN(aligned_addr) != PAGE_ROUND_DOWN((ULONG_PTR)aligned_addr + size - 1))
1298                {
1299                   aligned_addr = (PVOID)PAGE_ROUND_UP(aligned_addr);
1300                }
1301             }
1302          }
1303       }
1304       DPRINT("%x %x\n", addr, aligned_addr);
1305       new_size = (ULONG_PTR)aligned_addr - (ULONG_PTR)addr + size;
1306       if (current->hdr.Size >= new_size + HDR_USED_SIZE &&
1307           (best == NULL || current->hdr.Size < best->hdr.Size))
1308       {
1309          best = current;
1310          best_aligned_addr = aligned_addr;
1311          if (new_size <= size + 2 * HDR_FREE_SIZE)
1312          {
1313              break;
1314          }
1315       }
1316
1317       if (best)
1318       {
1319          if (size < PAGE_SIZE)
1320          {
1321             if (current->hdr.Size >= 2 * PAGE_SIZE + HDR_FREE_SIZE)
1322             {
1323                 break;
1324             }
1325          }
1326          else
1327          {
1328             if (current->hdr.Size >= size + alignment + HDR_FREE_SIZE)
1329             {
1330                 break;
1331             }
1332          }
1333       }
1334       p = avl_get_next(FreeBlockListRoot, p);
1335    }
1336    /*
1337     * We didn't find anything suitable at all.
1338     */
1339    if (best == NULL)
1340    {
1341       return NULL;
1342    }
1343
1344    DPRINT(":: blk %x blk->hdr.Size %d (%d) Size %d\n", best, best->hdr.Size, best->hdr.Size - HDR_USED_SIZE, size);
1345
1346    current = best;
1347    current_size = current->hdr.Size - HDR_USED_SIZE;
1348    addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE);
1349    if (addr != best_aligned_addr)
1350    {
1351       blk = (HDR_FREE*)((ULONG_PTR)best_aligned_addr - HDR_USED_SIZE);
1352       /*
1353        * if size-aligned, break off the preceding bytes into their own block...
1354        */
1355       previous = current;
1356       previous_size = (ULONG_PTR)blk - (ULONG_PTR)previous - HDR_FREE_SIZE;
1357       current = blk;
1358       current_size -= ((ULONG_PTR)current - (ULONG_PTR)previous);
1359    }
1360    end = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE + size);
1361
1362    if (current_size >= size + HDR_FREE_SIZE + MM_POOL_ALIGNMENT)
1363    {
1364       /* create a new free block after our block, if the memory size is >= 4 byte for this block */
1365       next = (HDR_FREE*)((ULONG_PTR)current + size + HDR_USED_SIZE);
1366       next_size = current_size - size - HDR_FREE_SIZE;
1367       current_size = size;
1368       end = (PVOID)((ULONG_PTR)next + HDR_FREE_SIZE);
1369    }
1370
1371    if (previous)
1372    {
1373       remove_from_free_list(previous);
1374       if (!grow_block(previous, end))
1375       {
1376          add_to_free_list(previous);
1377          return NULL;
1378       }
1379       memset(current, 0, HDR_USED_SIZE);
1380       current->hdr.Size = current_size + HDR_USED_SIZE;
1381       current->hdr.Magic = BLOCK_HDR_USED_MAGIC;
1382       current->hdr.previous = &previous->hdr;
1383       previous->hdr.Size = previous_size + HDR_FREE_SIZE;
1384       if (next == NULL)
1385       {
1386          blk = (HDR_FREE*)((ULONG_PTR)current + current->hdr.Size);
1387          if ((ULONG_PTR)blk < (ULONG_PTR)MiNonPagedPoolStart + MiNonPagedPoolLength)
1388          {
1389             blk->hdr.previous = &current->hdr;
1390          }
1391       }
1392
1393       add_to_free_list(previous);
1394    }
1395    else
1396    {
1397       remove_from_free_list(current);
1398
1399       if (!grow_block(current, end))
1400       {
1401          add_to_free_list(current);
1402          return NULL;
1403       }
1404       current->hdr.Magic = BLOCK_HDR_USED_MAGIC;
1405       if (next)
1406       {
1407          current->hdr.Size = current_size + HDR_USED_SIZE;
1408       }
1409    }
1410
1411    if (next)
1412    {
1413       memset(next, 0, HDR_FREE_SIZE);
1414       next->hdr.Size = next_size + HDR_FREE_SIZE;
1415       next->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
1416       next->hdr.previous = &current->hdr;
1417       blk = (HDR_FREE*)((ULONG_PTR)next + next->hdr.Size);
1418       if ((ULONG_PTR)blk < (ULONG_PTR)MiNonPagedPoolStart + MiNonPagedPoolLength)
1419       {
1420          blk->hdr.previous = &next->hdr;
1421       }
1422       add_to_free_list(next);
1423    }
1424
1425    add_to_used_list((HDR_USED*)current);
1426    VALIDATE_POOL;
1427
1428    if (size < PAGE_SIZE)
1429    {
1430        addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE);
1431        if (PAGE_ROUND_DOWN(addr) != PAGE_ROUND_DOWN((PVOID)((ULONG_PTR)addr + size - 1)))
1432        {
1433            DPRINT1("%x %x\n", addr, (ULONG_PTR)addr + size);
1434        }
1435        ASSERT (PAGE_ROUND_DOWN(addr) == PAGE_ROUND_DOWN((PVOID)((ULONG_PTR)addr + size - 1)));
1436    }
1437    if (alignment)
1438    {
1439        addr = (PVOID)((ULONG_PTR)current + HDR_USED_SIZE);
1440        ASSERT(MM_ROUND_UP(addr, alignment) == addr);
1441    }
1442    return (HDR_USED*)current;
1443 }
1444
1445 ULONG STDCALL
1446 ExRosQueryNonPagedPoolTag ( PVOID Addr )
1447 {
1448    HDR_USED* blk=(HDR_USED*)((ULONG_PTR)Addr - HDR_USED_SIZE);
1449    if (blk->hdr.Magic != BLOCK_HDR_USED_MAGIC)
1450       KEBUGCHECK(0);
1451
1452    return blk->Tag;
1453 }
1454
1455 VOID STDCALL ExFreeNonPagedPool (PVOID block)
1456 /*
1457  * FUNCTION: Releases previously allocated memory
1458  * ARGUMENTS:
1459  *        block = block to free
1460  */
1461 {
1462    HDR_USED* blk=(HDR_USED*)((ULONG_PTR)block - HDR_USED_SIZE);
1463    KIRQL oldIrql;
1464
1465    if (block == NULL)
1466    {
1467       return;
1468    }
1469
1470    DPRINT("freeing block %x\n",blk);
1471
1472    POOL_TRACE("ExFreePool(block %x), size %d, caller %x\n",block,blk->hdr.Size,
1473               block->Caller);
1474    KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
1475
1476    VALIDATE_POOL;
1477    if (blk->hdr.Magic != BLOCK_HDR_USED_MAGIC)
1478    {
1479       if (blk->hdr.Magic == BLOCK_HDR_FREE_MAGIC)
1480       {
1481          DbgPrint("ExFreePool of already freed address %x\n", block);
1482       }
1483       else
1484       {
1485          DbgPrint("ExFreePool of non-allocated address %x (magic %x)\n",
1486                   block, blk->hdr.Magic);
1487       }
1488       KEBUGCHECK(0);
1489       return;
1490    }
1491    memset(block, 0xcc, blk->hdr.Size - HDR_USED_SIZE);
1492 #ifdef TAG_STATISTICS_TRACKING
1493
1494    MiRemoveFromTagHashTable(blk);
1495 #endif
1496
1497    remove_from_used_list(blk);
1498    blk->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
1499    add_to_free_list((HDR_FREE*)blk);
1500    VALIDATE_POOL;
1501    KeReleaseSpinLock(&MmNpoolLock, oldIrql);
1502 }
1503
1504 PVOID STDCALL
1505 ExAllocateNonPagedPoolWithTag(POOL_TYPE Type, ULONG Size, ULONG Tag, PVOID Caller)
1506 {
1507    PVOID block;
1508    HDR_USED* best = NULL;
1509    KIRQL oldIrql;
1510    ULONG alignment;
1511
1512    POOL_TRACE("ExAllocatePool(NumberOfBytes %d) caller %x ",
1513               Size,Caller);
1514
1515    KeAcquireSpinLock(&MmNpoolLock, &oldIrql);
1516
1517    VALIDATE_POOL;
1518
1519 #if 0
1520    /* after some allocations print the npaged pool stats */
1521 #ifdef TAG_STATISTICS_TRACKING
1522
1523    {
1524       static ULONG counter = 0;
1525       if (counter++ % 100000 == 0)
1526       {
1527          MiDebugDumpNonPagedPoolStats(FALSE);
1528       }
1529    }
1530 #endif
1531 #endif
1532    /*
1533    * accomodate this useful idiom
1534    */
1535    if (Size == 0)
1536    {
1537       POOL_TRACE("= NULL\n");
1538       KeReleaseSpinLock(&MmNpoolLock, oldIrql);
1539       return(NULL);
1540    }
1541    /* Make the size dword alligned, this makes the block dword alligned */
1542    Size = ROUND_UP(Size, MM_POOL_ALIGNMENT);
1543
1544    if (Size >= PAGE_SIZE)
1545    {
1546       alignment = PAGE_SIZE;
1547    }
1548    else if (Type & CACHE_ALIGNED_POOL_MASK)
1549    {
1550       alignment = MM_CACHE_LINE_SIZE;
1551    }
1552    else
1553    {
1554       alignment = 0;
1555    }
1556
1557    best = get_block(Size, alignment);
1558    if (best == NULL)
1559    {
1560       KeReleaseSpinLock(&MmNpoolLock, oldIrql);
1561       DPRINT1("Trying to allocate %lu bytes from nonpaged pool - nothing suitable found, returning NULL\n",
1562               Size );
1563       return NULL;
1564    }
1565    best->Tag = Tag;
1566    best->Caller = Caller;
1567    best->Dumped = FALSE;
1568    best->TagListEntry.Flink = best->TagListEntry.Blink = NULL;
1569 #ifdef TAG_STATISTICS_TRACKING
1570
1571    MiAddToTagHashTable(best);
1572 #endif
1573
1574    KeReleaseSpinLock(&MmNpoolLock, oldIrql);
1575    block = (PVOID)((ULONG_PTR)best + HDR_USED_SIZE);
1576    /*   RtlZeroMemory(block, Size);*/
1577    return(block);
1578 }
1579
1580 VOID INIT_FUNCTION
1581 MiInitializeNonPagedPool(VOID)
1582 {
1583    NTSTATUS Status;
1584    PFN_TYPE Page;
1585    ULONG i;
1586    PVOID Address;
1587    HDR_USED* used;
1588    HDR_FREE* free;
1589 #ifdef TAG_STATISTICS_TRACKING
1590
1591    for (i = 0; i < TAG_HASH_TABLE_SIZE; i++)
1592    {
1593       InitializeListHead(&tag_hash_table[i]);
1594    }
1595 #endif
1596    KeInitializeSpinLock(&MmNpoolLock);
1597    InitializeListHead(&UsedBlockListHead);
1598    InitializeListHead(&AddressListHead);
1599    FreeBlockListRoot = NULL;
1600
1601    MiNonPagedPoolAllocMap = (PVOID)((ULONG_PTR)MiNonPagedPoolStart + PAGE_SIZE);
1602    MiNonPagedPoolNrOfPages = PAGE_ROUND_UP(ROUND_UP(MiNonPagedPoolLength / PAGE_SIZE, 32) / 8 + HDR_FREE_SIZE) + PAGE_SIZE;
1603    MiNonPagedPoolNrOfPages /= PAGE_SIZE;
1604    Address = MiNonPagedPoolStart;
1605
1606    for (i = 0; i < MiNonPagedPoolNrOfPages; i++)
1607    {
1608       Status = MmRequestPageMemoryConsumer(MC_NPPOOL, FALSE, &Page);
1609       if (!NT_SUCCESS(Status))
1610       {
1611          DbgPrint("Unable to allocate a page\n");
1612          KEBUGCHECK(0);
1613       }
1614
1615       Status = MmCreateVirtualMapping(NULL,
1616                                       Address,
1617                                       PAGE_READWRITE|PAGE_SYSTEM,
1618                                       &Page,
1619                                       1);
1620       if (!NT_SUCCESS(Status))
1621       {
1622          DbgPrint("Unable to create virtual mapping\n");
1623          KEBUGCHECK(0);
1624       }
1625       Address = (PVOID)((ULONG_PTR)Address + PAGE_SIZE);
1626    }
1627
1628    for (i = 0; i < MiNonPagedPoolNrOfPages; i++)
1629    {
1630       MiNonPagedPoolAllocMap[i / 32] |= (1 << (i % 32));
1631    }
1632
1633    /* the first block is free */
1634    free = (HDR_FREE*)MiNonPagedPoolStart;
1635    free->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
1636    free->hdr.Size = PAGE_SIZE - HDR_USED_SIZE;
1637    free->hdr.previous = NULL;
1638    memset((PVOID)((ULONG_PTR)free + HDR_FREE_SIZE), 0xcc, free->hdr.Size - HDR_FREE_SIZE);
1639    add_to_free_list(free);
1640
1641    /* the second block contains the non paged pool bitmap */
1642    used = (HDR_USED*)((ULONG_PTR)free + free->hdr.Size);
1643    used->hdr.Magic = BLOCK_HDR_USED_MAGIC;
1644    used->hdr.Size = ROUND_UP(MiNonPagedPoolLength / PAGE_SIZE, 32) / 8 + HDR_USED_SIZE;
1645    used->hdr.previous = &free->hdr;
1646    used->Tag = 0xffffffff;
1647    used->Caller = 0;
1648    used->Dumped = FALSE;
1649    add_to_used_list(used);
1650 #ifdef TAG_STATISTICS_TRACKING
1651    MiAddToTagHashTable(used);
1652 #endif
1653
1654    /* the third block is the free block after the bitmap */
1655    free = (HDR_FREE*)((ULONG_PTR)used + used->hdr.Size);
1656    free->hdr.Magic = BLOCK_HDR_FREE_MAGIC;
1657    free->hdr.Size = MiNonPagedPoolLength - ((ULONG_PTR)free - (ULONG_PTR)MiNonPagedPoolStart);
1658    free->hdr.previous = &used->hdr;
1659    memset((PVOID)((ULONG_PTR)free + HDR_FREE_SIZE), 0x0cc, (ULONG_PTR)Address - (ULONG_PTR)free - HDR_FREE_SIZE);
1660    add_to_free_list(free);
1661 }
1662
1663 PVOID
1664 STDCALL
1665 MiAllocateSpecialPool  (IN POOL_TYPE PoolType,
1666                         IN SIZE_T NumberOfBytes,
1667                         IN ULONG Tag,
1668                         IN ULONG Underrun
1669                         )
1670 {
1671     /* FIXME: Special Pools not Supported */
1672     DbgPrint("Special Pools not supported\n");
1673     return NULL;
1674 }
1675
1676 /* EOF */