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