ntoskrnl/ex/handle.c

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         GPL - See COPYING in the top level directory
   4  * FILE:            ntoskrnl/ex/handle.c
   5  * PURPOSE:         Generic Executive Handle Tables
   6  * PROGRAMMERS:     Alex Ionescu (alex.ionescu@reactos.org)
   7  *                  Thomas Weidenmueller <w3seek@reactos.com>
   8  */
   9
  10 /* INCLUDES ******************************************************************/
  11
  12 #include <ntoskrnl.h>
  13 #define NDEBUG
  14 #include <debug.h>
  15
  16 /* GLOBALS *******************************************************************/
  17
  18 LIST_ENTRY HandleTableListHead;
  19 EX_PUSH_LOCK HandleTableListLock;
  20 #define SizeOfHandle(x) (sizeof(HANDLE) * (x))
  21
  22 /* PRIVATE FUNCTIONS *********************************************************/
  23
  24 VOID
  25 NTAPI
  26 INIT_FUNCTION
  27 ExpInitializeHandleTables(VOID)
  28 {
  29     /* Initialize the list of handle tables and the lock */
  30     InitializeListHead(&HandleTableListHead);
  31     ExInitializePushLock(&HandleTableListLock);
  32 }
  33
  34 PHANDLE_TABLE_ENTRY
  35 NTAPI
  36 ExpLookupHandleTableEntry(IN PHANDLE_TABLE HandleTable,
  37                           IN EXHANDLE Handle)
  38 {
  39     ULONG TableLevel;
  40     ULONG_PTR TableBase;
  41     PHANDLE_TABLE_ENTRY HandleArray, Entry;
  42     PVOID *PointerArray;
  43
  44     /* Clear the tag bits */
  45     Handle.TagBits = 0;
  46
  47     /* Check if the handle is in the allocated range */
  48     if (Handle.Value >= HandleTable->NextHandleNeedingPool)
  49     {
  50         return NULL;
  51     }
  52
  53     /* Get the table code */
  54     TableBase = HandleTable->TableCode;
  55
  56     /* Extract the table level and actual table base */
  57     TableLevel = (ULONG)(TableBase & 3);
  58     TableBase &= ~3;
  59
  60     PointerArray = (PVOID*)TableBase;
  61     HandleArray = (PHANDLE_TABLE_ENTRY)TableBase;
  62
  63     /* Check what level we're running at */
  64     switch (TableLevel)
  65     {
  66         case 2:
  67
  68             /* Get the mid level pointer array */
  69             PointerArray = PointerArray[Handle.HighIndex];
  70
  71             /* Fall through */
  72         case 1:
  73
  74             /* Get the handle array */
  75             HandleArray = PointerArray[Handle.MidIndex];
  76
  77             /* Fall through */
  78         case 0:
  79
  80             /* Get the entry using the low index */
  81             Entry = &HandleArray[Handle.LowIndex];
  82
  83             /* All done */
  84             break;
  85
  86         default:
  87
  88             ASSERT(FALSE);
  89             Entry = NULL;
  90     }
  91
  92     /* Return the handle entry */
  93     return Entry;
  94 }
  95
  96 PVOID
  97 NTAPI
  98 ExpAllocateTablePagedPool(IN PEPROCESS Process OPTIONAL,
  99                           IN SIZE_T Size)
 100 {
 101     PVOID Buffer;
 102
 103     /* Do the allocation */
 104     Buffer = ExAllocatePoolWithTag(PagedPool, Size, TAG_OBJECT_TABLE);
 105     if (Buffer)
 106     {
 107         /* Clear the memory */
 108         RtlZeroMemory(Buffer, Size);
 109
 110         /* Check if we have a process to charge quota */
 111         if (Process)
 112         {
 113             /* FIXME: Charge quota */
 114         }
 115     }
 116
 117     /* Return the allocated memory */
 118     return Buffer;
 119 }
 120
 121 PVOID
 122 NTAPI
 123 ExpAllocateTablePagedPoolNoZero(IN PEPROCESS Process OPTIONAL,
 124                                 IN SIZE_T Size)
 125 {
 126     PVOID Buffer;
 127
 128     /* Do the allocation */
 129     Buffer = ExAllocatePoolWithTag(PagedPool, Size, TAG_OBJECT_TABLE);
 130     if (Buffer)
 131     {
 132         /* Check if we have a process to charge quota */
 133         if (Process)
 134         {
 135             /* FIXME: Charge quota */
 136         }
 137     }
 138
 139     /* Return the allocated memory */
 140     return Buffer;
 141 }
 142
 143 VOID
 144 NTAPI
 145 ExpFreeTablePagedPool(IN PEPROCESS Process OPTIONAL,
 146                       IN PVOID Buffer,
 147                       IN SIZE_T Size)
 148 {
 149     /* Free the buffer */
 150     ExFreePoolWithTag(Buffer, TAG_OBJECT_TABLE);
 151     if (Process)
 152     {
 153         /* FIXME: Release quota */
 154     }
 155 }
 156
 157 VOID
 158 NTAPI
 159 ExpFreeLowLevelTable(IN PEPROCESS Process,
 160                      IN PHANDLE_TABLE_ENTRY TableEntry)
 161 {
 162     /* Check if we have an entry */
 163     if (TableEntry[0].Object)
 164     {
 165         /* Free the entry */
 166         ExpFreeTablePagedPool(Process,
 167                               TableEntry[0].Object,
 168                               LOW_LEVEL_ENTRIES *
 169                               sizeof(HANDLE_TABLE_ENTRY_INFO));
 170     }
 171
 172     /* Free the table */
 173     ExpFreeTablePagedPool(Process, TableEntry, PAGE_SIZE);
 174 }
 175
 176 VOID
 177 NTAPI
 178 ExpFreeHandleTable(IN PHANDLE_TABLE HandleTable)
 179 {
 180     PEPROCESS Process = HandleTable->QuotaProcess;
 181     ULONG i, j;
 182     ULONG_PTR TableCode = HandleTable->TableCode;
 183     ULONG_PTR TableBase = TableCode & ~3;
 184     ULONG TableLevel = (ULONG)(TableCode & 3);
 185     PHANDLE_TABLE_ENTRY Level1, *Level2, **Level3;
 186     PAGED_CODE();
 187
 188     /* Check which level we're at */
 189     if (TableLevel == 0)
 190     {
 191         /* Select the first level table base and just free it */
 192         Level1 = (PVOID)TableBase;
 193         ExpFreeLowLevelTable(Process, Level1);
 194     }
 195     else if (TableLevel == 1)
 196     {
 197         /* Select the second level table base */
 198         Level2 = (PVOID)TableBase;
 199
 200         /* Loop each mid level entry */
 201         for (i = 0; i < MID_LEVEL_ENTRIES; i++)
 202         {
 203             /* Leave if we've reached the last entry */
 204             if (!Level2[i]) break;
 205
 206             /* Free the second level table */
 207             ExpFreeLowLevelTable(Process, Level2[i]);
 208         }
 209
 210         /* Free the second level table */
 211         ExpFreeTablePagedPool(Process, Level2, PAGE_SIZE);
 212     }
 213     else
 214     {
 215         /* Select the third level table base */
 216         Level3 = (PVOID)TableBase;
 217
 218         /* Loop each high level entry */
 219         for (i = 0; i < HIGH_LEVEL_ENTRIES; i++)
 220         {
 221             /* Leave if we've reached the last entry */
 222             if (!Level3[i]) break;
 223
 224             /* Loop each mid level entry */
 225             for (j = 0; j < MID_LEVEL_ENTRIES; j++)
 226             {
 227                 /* Leave if we've reached the last entry */
 228                 if (!Level3[i][j]) break;
 229
 230                 /* Free the second level table */
 231                 ExpFreeLowLevelTable(Process, Level3[i][j]);
 232             }
 233
 234             /* Free the third level table entry */
 235             ExpFreeTablePagedPool(Process, Level3[i], PAGE_SIZE);
 236         }
 237
 238         /* Free the third level table */
 239         ExpFreeTablePagedPool(Process,
 240                               Level3,
 241                               SizeOfHandle(HIGH_LEVEL_ENTRIES));
 242     }
 243
 244     /* Free the actual table and check if we need to release quota */
 245     ExFreePoolWithTag(HandleTable, TAG_OBJECT_TABLE);
 246     if (Process)
 247     {
 248         /* FIXME: TODO */
 249     }
 250 }
 251
 252 VOID
 253 NTAPI
 254 ExpFreeHandleTableEntry(IN PHANDLE_TABLE HandleTable,
 255                         IN EXHANDLE Handle,
 256                         IN PHANDLE_TABLE_ENTRY HandleTableEntry)
 257 {
 258     ULONG OldValue, NewValue, *Free;
 259     ULONG i;
 260     PAGED_CODE();
 261
 262     /* Sanity checks */
 263     ASSERT(HandleTableEntry->Object == NULL);
 264     ASSERT(HandleTableEntry == ExpLookupHandleTableEntry(HandleTable, Handle));
 265
 266     /* Decrement the handle count */
 267     InterlockedDecrement(&HandleTable->HandleCount);
 268
 269     /* Mark the handle as free */
 270     NewValue = (ULONG)Handle.Value & ~(SizeOfHandle(1) - 1);
 271
 272     /* Check if we're FIFO */
 273     if (!HandleTable->StrictFIFO)
 274     {
 275         /* Select a lock index */
 276         i = (NewValue >> 2) % 4;
 277
 278         /* Select which entry to use */
 279         Free = (HandleTable->HandleTableLock[i].Locked) ?
 280                 &HandleTable->FirstFree : &HandleTable->LastFree;
 281     }
 282     else
 283     {
 284         /* No need to worry about locking, take the last entry */
 285         Free = &HandleTable->LastFree;
 286     }
 287
 288     /* Start value change loop */
 289     for (;;)
 290     {
 291         /* Get the current value and write */
 292         OldValue = *Free;
 293         HandleTableEntry->NextFreeTableEntry = (ULONG)OldValue;
 294         if (InterlockedCompareExchange((PLONG) Free, NewValue, OldValue) == OldValue)
 295         {
 296             /* Break out, we're done. Make sure the handle value makes sense */
 297             ASSERT((OldValue & FREE_HANDLE_MASK) <
 298                    HandleTable->NextHandleNeedingPool);
 299             break;
 300         }
 301     }
 302 }
 303
 304 PHANDLE_TABLE
 305 NTAPI
 306 ExpAllocateHandleTable(IN PEPROCESS Process OPTIONAL,
 307                        IN BOOLEAN NewTable)
 308 {
 309     PHANDLE_TABLE HandleTable;
 310     PHANDLE_TABLE_ENTRY HandleTableTable, HandleEntry;
 311     ULONG i;
 312     PAGED_CODE();
 313
 314     /* Allocate the table */
 315     HandleTable = ExAllocatePoolWithTag(PagedPool,
 316                                         sizeof(HANDLE_TABLE),
 317                                         TAG_OBJECT_TABLE);
 318     if (!HandleTable) return NULL;
 319
 320     /* Check if we have a process */
 321     if (Process)
 322     {
 323         /* FIXME: Charge quota */
 324     }
 325
 326     /* Clear the table */
 327     RtlZeroMemory(HandleTable, sizeof(HANDLE_TABLE));
 328
 329     /* Now allocate the first level structures */
 330     HandleTableTable = ExpAllocateTablePagedPoolNoZero(Process, PAGE_SIZE);
 331     if (!HandleTableTable)
 332     {
 333         /* Failed, free the table */
 334         ExFreePoolWithTag(HandleTable, TAG_OBJECT_TABLE);
 335         return NULL;
 336     }
 337
 338     /* Write the pointer to our first level structures */
 339     HandleTable->TableCode = (ULONG_PTR)HandleTableTable;
 340
 341     /* Initialize the first entry */
 342     HandleEntry = &HandleTableTable[0];
 343     HandleEntry->NextFreeTableEntry = -2;
 344     HandleEntry->Value = 0;
 345
 346     /* Check if this is a new table */
 347     if (NewTable)
 348     {
 349         /* Go past the root entry */
 350         HandleEntry++;
 351
 352         /* Loop every low level entry */
 353         for (i = 1; i < (LOW_LEVEL_ENTRIES - 1); i++)
 354         {
 355             /* Set up the free data */
 356             HandleEntry->Value = 0;
 357             HandleEntry->NextFreeTableEntry = (i + 1) * SizeOfHandle(1);
 358
 359             /* Move to the next entry */
 360             HandleEntry++;
 361         }
 362
 363         /* Terminate the last entry */
 364         HandleEntry->Value = 0;
 365         HandleEntry->NextFreeTableEntry = 0;
 366         HandleTable->FirstFree = SizeOfHandle(1);
 367     }
 368
 369     /* Set the next handle needing pool after our allocated page from above */
 370     HandleTable->NextHandleNeedingPool = LOW_LEVEL_ENTRIES * SizeOfHandle(1);
 371
 372     /* Setup the rest of the handle table data */
 373     HandleTable->QuotaProcess = Process;
 374     HandleTable->UniqueProcessId = PsGetCurrentProcess()->UniqueProcessId;
 375     HandleTable->Flags = 0;
 376
 377     /* Loop all the handle table locks */
 378     for (i = 0; i < 4; i++)
 379     {
 380         /* Initialize the handle table lock */
 381         ExInitializePushLock(&HandleTable->HandleTableLock[i]);
 382     }
 383
 384     /* Initialize the contention event lock and return the lock */
 385     ExInitializePushLock(&HandleTable->HandleContentionEvent);
 386     return HandleTable;
 387 }
 388
 389 PHANDLE_TABLE_ENTRY
 390 NTAPI
 391 ExpAllocateLowLevelTable(IN PHANDLE_TABLE HandleTable,
 392                          IN BOOLEAN DoInit)
 393 {
 394     ULONG i, Base;
 395     PHANDLE_TABLE_ENTRY Low, HandleEntry;
 396
 397     /* Allocate the low level table */
 398     Low = ExpAllocateTablePagedPoolNoZero(HandleTable->QuotaProcess,
 399                                           PAGE_SIZE);
 400     if (!Low) return NULL;
 401
 402     /* Setup the initial entry */
 403     HandleEntry = &Low[0];
 404     HandleEntry->NextFreeTableEntry = -2;
 405     HandleEntry->Value = 0;
 406
 407     /* Check if we're initializing */
 408     if (DoInit)
 409     {
 410         /* Go to the next entry and the base entry */
 411         HandleEntry++;
 412         Base = HandleTable->NextHandleNeedingPool + SizeOfHandle(2);
 413
 414         /* Loop each entry */
 415         for (i = Base;
 416              i < Base + SizeOfHandle(LOW_LEVEL_ENTRIES - 2);
 417              i += SizeOfHandle(1))
 418         {
 419             /* Free this entry and move on to the next one */
 420             HandleEntry->NextFreeTableEntry = i;
 421             HandleEntry->Value = 0;
 422             HandleEntry++;
 423         }
 424
 425         /* Terminate the last entry */
 426         HandleEntry->NextFreeTableEntry = 0;
 427         HandleEntry->Value = 0;
 428     }
 429
 430     /* Return the low level table */
 431     return Low;
 432 }
 433
 434 PHANDLE_TABLE_ENTRY*
 435 NTAPI
 436 ExpAllocateMidLevelTable(IN PHANDLE_TABLE HandleTable,
 437                          IN BOOLEAN DoInit,
 438                          OUT PHANDLE_TABLE_ENTRY *LowTableEntry)
 439 {
 440     PHANDLE_TABLE_ENTRY *Mid, Low;
 441
 442     /* Allocate the mid level table */
 443     Mid = ExpAllocateTablePagedPool(HandleTable->QuotaProcess, PAGE_SIZE);
 444     if (!Mid) return NULL;
 445
 446     /* Allocate a new low level for it */
 447     Low = ExpAllocateLowLevelTable(HandleTable, DoInit);
 448     if (!Low)
 449     {
 450         /* We failed, free the mid table */
 451         ExpFreeTablePagedPool(HandleTable->QuotaProcess, Mid, PAGE_SIZE);
 452         return NULL;
 453     }
 454
 455     /* Link the tables and return the pointer */
 456     Mid[0] = Low;
 457     *LowTableEntry = Low;
 458     return Mid;
 459 }
 460
 461 BOOLEAN
 462 NTAPI
 463 ExpAllocateHandleTableEntrySlow(IN PHANDLE_TABLE HandleTable,
 464                                 IN BOOLEAN DoInit)
 465 {
 466     ULONG i, j, Index;
 467     PHANDLE_TABLE_ENTRY Low = NULL, *Mid, **High, *SecondLevel, **ThirdLevel;
 468     ULONG NewFree, FirstFree;
 469     PVOID Value;
 470     ULONG_PTR TableCode = HandleTable->TableCode;
 471     ULONG_PTR TableBase = TableCode & ~3;
 472     ULONG TableLevel = (ULONG)(TableCode & 3);
 473     PAGED_CODE();
 474
 475     /* Check how many levels we already have */
 476     if (TableLevel == 0)
 477     {
 478         /* Allocate a mid level, since we only have a low level */
 479         Mid = ExpAllocateMidLevelTable(HandleTable, DoInit, &Low);
 480         if (!Mid) return FALSE;
 481
 482         /* Link up the tables */
 483         Mid[1] = Mid[0];
 484         Mid[0] = (PVOID)TableBase;
 485
 486         /* Write the new level and attempt to change the table code */
 487         TableBase = ((ULONG_PTR)Mid) | 1;
 488         Value = InterlockedExchangePointer((PVOID*)&HandleTable->TableCode, (PVOID)TableBase);
 489     }
 490     else if (TableLevel == 1)
 491     {
 492         /* Setup the 2nd level table */
 493         SecondLevel = (PVOID)TableBase;
 494
 495         /* Get if the next index can fit in the table */
 496         i = HandleTable->NextHandleNeedingPool /
 497             SizeOfHandle(LOW_LEVEL_ENTRIES);
 498         if (i < MID_LEVEL_ENTRIES)
 499         {
 500             /* We need to allocate a new table */
 501             Low = ExpAllocateLowLevelTable(HandleTable, DoInit);
 502             if (!Low) return FALSE;
 503
 504             /* Update the table */
 505             Value = InterlockedExchangePointer((PVOID*)&SecondLevel[i], Low);
 506             ASSERT(Value == NULL);
 507         }
 508         else
 509         {
 510             /* We need a new high level table */
 511             High = ExpAllocateTablePagedPool(HandleTable->QuotaProcess,
 512                                              SizeOfHandle(HIGH_LEVEL_ENTRIES));
 513             if (!High) return FALSE;
 514
 515             /* Allocate a new mid level table as well */
 516             Mid = ExpAllocateMidLevelTable(HandleTable, DoInit, &Low);
 517             if (!Mid)
 518             {
 519                 /* We failed, free the high level table as well */
 520                 ExpFreeTablePagedPool(HandleTable->QuotaProcess,
 521                                       High,
 522                                       SizeOfHandle(HIGH_LEVEL_ENTRIES));
 523                 return FALSE;
 524             }
 525
 526             /* Link up the tables */
 527             High[0] = (PVOID)TableBase;
 528             High[1] = Mid;
 529
 530             /* Write the new table and change the table code */
 531             TableBase = ((ULONG_PTR)High) | 2;
 532             Value = InterlockedExchangePointer((PVOID*)&HandleTable->TableCode,
 533                                                (PVOID)TableBase);
 534         }
 535     }
 536     else if (TableLevel == 2)
 537     {
 538         /* Setup the 3rd level table */
 539         ThirdLevel = (PVOID)TableBase;
 540
 541         /* Get the index and check if it can fit */
 542         i = HandleTable->NextHandleNeedingPool / SizeOfHandle(MAX_MID_INDEX);
 543         if (i >= HIGH_LEVEL_ENTRIES) return FALSE;
 544
 545         /* Check if there's no mid-level table */
 546         if (!ThirdLevel[i])
 547         {
 548             /* Allocate a new mid level table */
 549             Mid = ExpAllocateMidLevelTable(HandleTable, DoInit, &Low);
 550             if (!Mid) return FALSE;
 551
 552             /* Update the table pointer */
 553             Value = InterlockedExchangePointer((PVOID*)&ThirdLevel[i], Mid);
 554             ASSERT(Value == NULL);
 555         }
 556         else
 557         {
 558             /* We have one, check at which index we should insert our entry */
 559             Index  = (HandleTable->NextHandleNeedingPool / SizeOfHandle(1)) -
 560                       i * MAX_MID_INDEX;
 561             j = Index / LOW_LEVEL_ENTRIES;
 562
 563             /* Allocate a new low level */
 564             Low = ExpAllocateLowLevelTable(HandleTable, DoInit);
 565             if (!Low) return FALSE;
 566
 567             /* Update the table pointer */
 568             Value = InterlockedExchangePointer((PVOID*)&ThirdLevel[i][j], Low);
 569             ASSERT(Value == NULL);
 570         }
 571     }
 572     else
 573     {
 574         /* Something is really broken */
 575         ASSERT(FALSE);
 576     }
 577
 578     /* Update the index of the next handle */
 579     Index = InterlockedExchangeAdd((PLONG) &HandleTable->NextHandleNeedingPool,
 580                                    SizeOfHandle(LOW_LEVEL_ENTRIES));
 581
 582     /* Check if need to initialize the table */
 583     if (DoInit)
 584     {
 585         /* Create a new index number */
 586         Index += SizeOfHandle(1);
 587
 588         /* Start free index change loop */
 589         for (;;)
 590         {
 591             /* Setup the first free index */
 592             FirstFree = HandleTable->FirstFree;
 593             Low[LOW_LEVEL_ENTRIES - 1].NextFreeTableEntry = FirstFree;
 594
 595             /* Change the index */
 596             NewFree = InterlockedCompareExchange((PLONG) &HandleTable->FirstFree,
 597                                                  Index,
 598                                                  FirstFree);
 599             if (NewFree == FirstFree) break;
 600         }
 601     }
 602
 603     /* All done */
 604     return TRUE;
 605 }
 606
 607 ULONG
 608 NTAPI
 609 ExpMoveFreeHandles(IN PHANDLE_TABLE HandleTable)
 610 {
 611     ULONG LastFree, i;
 612
 613     /* Clear the last free index */
 614     LastFree = InterlockedExchange((PLONG) &HandleTable->LastFree, 0);
 615
 616     /* Check if we had no index */
 617     if (!LastFree) return LastFree;
 618
 619     /* Acquire the locks we need */
 620     for (i = 1; i < 4; i++)
 621     {
 622         /* Acquire this lock exclusively */
 623         ExWaitOnPushLock(&HandleTable->HandleTableLock[i]);
 624     }
 625
 626     /* Check if we're not strict FIFO */
 627     if (!HandleTable->StrictFIFO)
 628     {
 629         /* Update the first free index */
 630         if (!InterlockedCompareExchange((PLONG) &HandleTable->FirstFree, LastFree, 0))
 631         {
 632             /* We're done, exit */
 633             return LastFree;
 634         }
 635     }
 636
 637     /* We are strict FIFO, we need to reverse the entries */
 638     ASSERT(FALSE);
 639     return LastFree;
 640 }
 641
 642 PHANDLE_TABLE_ENTRY
 643 NTAPI
 644 ExpAllocateHandleTableEntry(IN PHANDLE_TABLE HandleTable,
 645                             OUT PEXHANDLE NewHandle)
 646 {
 647     ULONG OldValue, NewValue, NewValue1;
 648     PHANDLE_TABLE_ENTRY Entry;
 649     EXHANDLE Handle;
 650     BOOLEAN Result;
 651     ULONG i;
 652
 653     /* Start allocation loop */
 654     for (;;)
 655     {
 656         /* Get the current link */
 657         OldValue = HandleTable->FirstFree;
 658         while (!OldValue)
 659         {
 660             /* No free entries remain, lock the handle table */
 661             KeEnterCriticalRegion();
 662             ExAcquirePushLockExclusive(&HandleTable->HandleTableLock[0]);
 663
 664             /* Check the value again */
 665             OldValue = HandleTable->FirstFree;
 666             if (OldValue)
 667             {
 668                 /* Another thread has already created a new level, bail out */
 669                 ExReleasePushLockExclusive(&HandleTable->HandleTableLock[0]);
 670                 KeLeaveCriticalRegion();
 671                 break;
 672             }
 673
 674             /* Now move any free handles */
 675             OldValue = ExpMoveFreeHandles(HandleTable);
 676             if (OldValue)
 677             {
 678                 /* Another thread has already moved them, bail out */
 679                 ExReleasePushLockExclusive(&HandleTable->HandleTableLock[0]);
 680                 KeLeaveCriticalRegion();
 681                 break;
 682             }
 683
 684             /* We're the first one through, so do the actual allocation */
 685             Result = ExpAllocateHandleTableEntrySlow(HandleTable, TRUE);
 686
 687             /* Unlock the table and get the value now */
 688             ExReleasePushLockExclusive(&HandleTable->HandleTableLock[0]);
 689             KeLeaveCriticalRegion();
 690             OldValue = HandleTable->FirstFree;
 691
 692             /* Check if allocation failed */
 693             if (!Result)
 694             {
 695                 /* Check if nobody else went through here */
 696                 if (!OldValue)
 697                 {
 698                     /* We're still the only thread around, so fail */
 699                     NewHandle->GenericHandleOverlay = NULL;
 700                     return NULL;
 701                 }
 702             }
 703         }
 704
 705         /* We made it, write the current value */
 706         Handle.Value = (OldValue & FREE_HANDLE_MASK);
 707
 708         /* Lookup the entry for this handle */
 709         Entry = ExpLookupHandleTableEntry(HandleTable, Handle);
 710
 711         /* Get an available lock and acquire it */
 712         i = ((OldValue & FREE_HANDLE_MASK) >> 2) % 4;
 713         KeEnterCriticalRegion();
 714         ExAcquirePushLockShared(&HandleTable->HandleTableLock[i]);
 715
 716         /* Check if the value changed after acquiring the lock */
 717         if (OldValue != *(volatile ULONG*)&HandleTable->FirstFree)
 718         {
 719             /* It did, so try again */
 720             ExReleasePushLockShared(&HandleTable->HandleTableLock[i]);
 721             KeLeaveCriticalRegion();
 722             continue;
 723         }
 724
 725         /* Now get the next value and do the compare */
 726         NewValue = *(volatile ULONG*)&Entry->NextFreeTableEntry;
 727         NewValue1 = InterlockedCompareExchange((PLONG) &HandleTable->FirstFree,
 728                                                NewValue,
 729                                                OldValue);
 730
 731         /* The change was done, so release the lock */
 732         ExReleasePushLockShared(&HandleTable->HandleTableLock[i]);
 733         KeLeaveCriticalRegion();
 734
 735         /* Check if the compare was successful */
 736         if (NewValue1 == OldValue)
 737         {
 738             /* Make sure that the new handle is in range, and break out */
 739             ASSERT((NewValue & FREE_HANDLE_MASK) <
 740                    HandleTable->NextHandleNeedingPool);
 741             break;
 742         }
 743         else
 744         {
 745             /* The compare failed, make sure we expected it */
 746             ASSERT((NewValue1 & FREE_HANDLE_MASK) !=
 747                    (OldValue & FREE_HANDLE_MASK));
 748         }
 749     }
 750
 751     /* Increase the number of handles */
 752     InterlockedIncrement(&HandleTable->HandleCount);
 753
 754     /* Return the handle and the entry */
 755     *NewHandle = Handle;
 756     return Entry;
 757 }
 758
 759 PHANDLE_TABLE
 760 NTAPI
 761 ExCreateHandleTable(IN PEPROCESS Process OPTIONAL)
 762 {
 763     PHANDLE_TABLE HandleTable;
 764     PAGED_CODE();
 765
 766     /* Allocate the handle table */
 767     HandleTable = ExpAllocateHandleTable(Process, TRUE);
 768     if (!HandleTable) return NULL;
 769
 770     /* Acquire the handle table lock */
 771     KeEnterCriticalRegion();
 772     ExAcquirePushLockExclusive(&HandleTableListLock);
 773
 774     /* Insert it into the list */
 775     InsertTailList(&HandleTableListHead, &HandleTable->HandleTableList);
 776
 777     /* Release the lock */
 778     ExReleasePushLockExclusive(&HandleTableListLock);
 779     KeLeaveCriticalRegion();
 780
 781     /* Return the handle table */
 782     return HandleTable;
 783 }
 784
 785 HANDLE
 786 NTAPI
 787 ExCreateHandle(IN PHANDLE_TABLE HandleTable,
 788                IN PHANDLE_TABLE_ENTRY HandleTableEntry)
 789 {
 790     EXHANDLE Handle;
 791     PHANDLE_TABLE_ENTRY NewEntry;
 792     PAGED_CODE();
 793
 794     /* Start with a clean handle */
 795     Handle.GenericHandleOverlay = NULL;
 796
 797     /* Allocate a new entry */
 798     NewEntry = ExpAllocateHandleTableEntry(HandleTable, &Handle);
 799     if (NewEntry)
 800     {
 801         /* Enter a critical region */
 802         KeEnterCriticalRegion();
 803
 804         /* Write the entry */
 805         *NewEntry = *HandleTableEntry;
 806
 807         /* Unlock it and leave the critical region */
 808         ExUnlockHandleTableEntry(HandleTable, NewEntry);
 809         KeLeaveCriticalRegion();
 810     }
 811
 812     /* Return the handle value */
 813     return Handle.GenericHandleOverlay;
 814 }
 815
 816 VOID
 817 NTAPI
 818 ExpBlockOnLockedHandleEntry(IN PHANDLE_TABLE HandleTable,
 819                             IN PHANDLE_TABLE_ENTRY HandleTableEntry)
 820 {
 821     LONG_PTR OldValue;
 822     EX_PUSH_LOCK_WAIT_BLOCK WaitBlock;
 823
 824     /* Block on the pushlock */
 825     ExBlockPushLock(&HandleTable->HandleContentionEvent, &WaitBlock);
 826
 827     /* Get the current value and check if it's been unlocked */
 828     OldValue = HandleTableEntry->Value;
 829     if (!(OldValue) || (OldValue & EXHANDLE_TABLE_ENTRY_LOCK_BIT))
 830     {
 831         /* Unblock the pushlock and return */
 832         ExfUnblockPushLock(&HandleTable->HandleContentionEvent, &WaitBlock);
 833     }
 834     else
 835     {
 836         /* Wait for it to be unblocked */
 837         ExWaitForUnblockPushLock(&HandleTable->HandleContentionEvent,
 838                                  &WaitBlock);
 839     }
 840 }
 841
 842 BOOLEAN
 843 NTAPI
 844 ExpLockHandleTableEntry(IN PHANDLE_TABLE HandleTable,
 845                         IN PHANDLE_TABLE_ENTRY HandleTableEntry)
 846 {
 847     LONG_PTR NewValue, OldValue;
 848
 849     /* Sanity check */
 850     ASSERT((KeGetCurrentThread()->CombinedApcDisable != 0) ||
 851            (KeGetCurrentIrql() == APC_LEVEL));
 852
 853     /* Start lock loop */
 854     for (;;)
 855     {
 856         /* Get the current value and check if it's locked */
 857         OldValue = *(volatile LONG_PTR *)&HandleTableEntry->Object;
 858         if (OldValue & EXHANDLE_TABLE_ENTRY_LOCK_BIT)
 859         {
 860             /* It's not locked, remove the lock bit to lock it */
 861             NewValue = OldValue & ~EXHANDLE_TABLE_ENTRY_LOCK_BIT;
 862             if (InterlockedCompareExchangePointer(&HandleTableEntry->Object,
 863                                                   (PVOID)NewValue,
 864                                                   (PVOID)OldValue) == (PVOID)OldValue)
 865             {
 866                 /* We locked it, get out */
 867                 return TRUE;
 868             }
 869         }
 870         else
 871         {
 872             /* We couldn't lock it, bail out if it's been freed */
 873             if (!OldValue) return FALSE;
 874         }
 875
 876         /* It's locked, wait for it to be unlocked */
 877         ExpBlockOnLockedHandleEntry(HandleTable, HandleTableEntry);
 878     }
 879 }
 880
 881 VOID
 882 NTAPI
 883 ExUnlockHandleTableEntry(IN PHANDLE_TABLE HandleTable,
 884                          IN PHANDLE_TABLE_ENTRY HandleTableEntry)
 885 {
 886     LONG_PTR OldValue;
 887     PAGED_CODE();
 888
 889     /* Sanity check */
 890     ASSERT((KeGetCurrentThread()->CombinedApcDisable != 0) ||
 891            (KeGetCurrentIrql() == APC_LEVEL));
 892
 893     /* Set the lock bit and make sure it wasn't earlier */
 894     OldValue = InterlockedOr((PLONG) &HandleTableEntry->Value,
 895                              EXHANDLE_TABLE_ENTRY_LOCK_BIT);
 896     ASSERT((OldValue & EXHANDLE_TABLE_ENTRY_LOCK_BIT) == 0);
 897
 898     /* Unblock any waiters */
 899     ExfUnblockPushLock(&HandleTable->HandleContentionEvent, NULL);
 900 }
 901
 902 VOID
 903 NTAPI
 904 ExRemoveHandleTable(IN PHANDLE_TABLE HandleTable)
 905 {
 906     PAGED_CODE();
 907
 908     /* Acquire the table lock */
 909     KeEnterCriticalRegion();
 910     ExAcquirePushLockExclusive(&HandleTableListLock);
 911
 912     /* Remove the table and reset the list */
 913     RemoveEntryList(&HandleTable->HandleTableList);
 914     InitializeListHead(&HandleTable->HandleTableList);
 915
 916     /* Release the lock */
 917     ExReleasePushLockExclusive(&HandleTableListLock);
 918     KeLeaveCriticalRegion();
 919 }
 920
 921 VOID
 922 NTAPI
 923 ExDestroyHandleTable(IN PHANDLE_TABLE HandleTable,
 924                      IN PVOID DestroyHandleProcedure OPTIONAL)
 925 {
 926     PAGED_CODE();
 927
 928     /* Remove the handle from the list */
 929     ExRemoveHandleTable(HandleTable);
 930
 931     /* Check if we have a destroy callback */
 932     if (DestroyHandleProcedure)
 933     {
 934         /* FIXME: */
 935         ASSERT(FALSE);
 936     }
 937
 938     /* Free the handle table */
 939     ExpFreeHandleTable(HandleTable);
 940 }
 941
 942 BOOLEAN
 943 NTAPI
 944 ExDestroyHandle(IN PHANDLE_TABLE HandleTable,
 945                 IN HANDLE Handle,
 946                 IN PHANDLE_TABLE_ENTRY HandleTableEntry OPTIONAL)
 947 {
 948     EXHANDLE ExHandle;
 949     PVOID Object;
 950     PAGED_CODE();
 951
 952     /* Setup the actual handle value */
 953     ExHandle.GenericHandleOverlay = Handle;
 954
 955     /* Enter a critical region and check if we have to lookup the handle */
 956     KeEnterCriticalRegion();
 957     if (!HandleTableEntry)
 958     {
 959         /* Lookup the entry */
 960         HandleTableEntry = ExpLookupHandleTableEntry(HandleTable, ExHandle);
 961
 962         /* Make sure that we found an entry, and that it's valid */
 963         if (!(HandleTableEntry) ||
 964             !(HandleTableEntry->Object) ||
 965             (HandleTableEntry->NextFreeTableEntry == -2))
 966         {
 967             /* Invalid handle, fail */
 968             KeLeaveCriticalRegion();
 969             return FALSE;
 970         }
 971
 972         /* Lock the entry */
 973         if (!ExpLockHandleTableEntry(HandleTable, HandleTableEntry))
 974         {
 975             /* Couldn't lock, fail */
 976             KeLeaveCriticalRegion();
 977             return FALSE;
 978         }
 979     }
 980     else
 981     {
 982         /* Make sure the handle is locked */
 983         ASSERT((HandleTableEntry->Value & EXHANDLE_TABLE_ENTRY_LOCK_BIT) == 0);
 984     }
 985
 986     /* Clear the handle */
 987     Object = InterlockedExchangePointer((PVOID*)&HandleTableEntry->Object, NULL);
 988
 989     /* Sanity checks */
 990     ASSERT(Object != NULL);
 991     ASSERT((((ULONG_PTR)Object) & EXHANDLE_TABLE_ENTRY_LOCK_BIT) == 0);
 992
 993     /* Unblock the pushlock */
 994     ExfUnblockPushLock(&HandleTable->HandleContentionEvent, NULL);
 995
 996     /* Free the actual entry */
 997     ExpFreeHandleTableEntry(HandleTable, ExHandle, HandleTableEntry);
 998
 999     /* If we got here, return success */
1000     KeLeaveCriticalRegion();
1001     return TRUE;
1002 }
1003
1004 PHANDLE_TABLE_ENTRY
1005 NTAPI
1006 ExMapHandleToPointer(IN PHANDLE_TABLE HandleTable,
1007                      IN HANDLE Handle)
1008 {
1009     EXHANDLE ExHandle;
1010     PHANDLE_TABLE_ENTRY HandleTableEntry;
1011     PAGED_CODE();
1012
1013     /* Set the handle value */
1014     ExHandle.GenericHandleOverlay = Handle;
1015
1016     /* Fail if we got an invalid index */
1017     if (!(ExHandle.Index & (LOW_LEVEL_ENTRIES - 1))) return NULL;
1018
1019     /* Do the lookup */
1020     HandleTableEntry = ExpLookupHandleTableEntry(HandleTable, ExHandle);
1021     if (!HandleTableEntry) return NULL;
1022
1023     /* Lock it */
1024     if (!ExpLockHandleTableEntry(HandleTable, HandleTableEntry)) return NULL;
1025
1026     /* Return the entry */
1027     return HandleTableEntry;
1028 }
1029
1030 PHANDLE_TABLE
1031 NTAPI
1032 ExDupHandleTable(IN PEPROCESS Process,
1033                  IN PHANDLE_TABLE HandleTable,
1034                  IN PEX_DUPLICATE_HANDLE_CALLBACK DupHandleProcedure,
1035                  IN ULONG_PTR Mask)
1036 {
1037     PHANDLE_TABLE NewTable;
1038     EXHANDLE Handle;
1039     PHANDLE_TABLE_ENTRY HandleTableEntry, NewEntry;
1040     BOOLEAN Failed = FALSE;
1041     PAGED_CODE();
1042
1043     /* Allocate the duplicated copy */
1044     NewTable = ExpAllocateHandleTable(Process, FALSE);
1045     if (!NewTable) return NULL;
1046
1047     /* Loop each entry */
1048     while (NewTable->NextHandleNeedingPool <
1049            HandleTable->NextHandleNeedingPool)
1050     {
1051         /* Insert it into the duplicated copy */
1052         if (!ExpAllocateHandleTableEntrySlow(NewTable, FALSE))
1053         {
1054             /* Insert failed, free the new copy and return */
1055             ExpFreeHandleTable(NewTable);
1056             return NULL;
1057         }
1058     }
1059
1060     /* Setup the initial handle table data */
1061     NewTable->HandleCount = 0;
1062     NewTable->ExtraInfoPages = 0;
1063     NewTable->FirstFree = 0;
1064
1065     /* Setup the first handle value  */
1066     Handle.Value = SizeOfHandle(1);
1067
1068     /* Enter a critical region and lookup the new entry */
1069     KeEnterCriticalRegion();
1070     while ((NewEntry = ExpLookupHandleTableEntry(NewTable, Handle)))
1071     {
1072         /* Lookup the old entry */
1073         HandleTableEntry = ExpLookupHandleTableEntry(HandleTable, Handle);
1074
1075         /* Loop each entry */
1076         do
1077         {
1078             /* Check if it doesn't match the audit mask */
1079             if (!(HandleTableEntry->Value & Mask))
1080             {
1081                 /* Free it since we won't use it */
1082                 Failed = TRUE;
1083             }
1084             else
1085             {
1086                 /* Lock the entry */
1087                 if (!ExpLockHandleTableEntry(HandleTable, HandleTableEntry))
1088                 {
1089                     /* Free it since we can't lock it, so we won't use it */
1090                     Failed = TRUE;
1091                 }
1092                 else
1093                 {
1094                     /* Copy the handle value */
1095                     *NewEntry = *HandleTableEntry;
1096
1097                     /* Call the duplicate callback */
1098                     if (DupHandleProcedure(Process,
1099                                            HandleTable,
1100                                            HandleTableEntry,
1101                                            NewEntry))
1102                     {
1103                         /* Clear failure flag */
1104                         Failed = FALSE;
1105
1106                         /* Lock the entry, increase the handle count */
1107                         NewEntry->Value |= EXHANDLE_TABLE_ENTRY_LOCK_BIT;
1108                         NewTable->HandleCount++;
1109                     }
1110                     else
1111                     {
1112                         /* Duplication callback refused, fail */
1113                         Failed = TRUE;
1114                     }
1115                 }
1116             }
1117
1118             /* Check if we failed earlier and need to free */
1119             if (Failed)
1120             {
1121                 /* Free this entry */
1122                 NewEntry->Object = NULL;
1123                 NewEntry->NextFreeTableEntry = NewTable->FirstFree;
1124                 NewTable->FirstFree = (ULONG)Handle.Value;
1125             }
1126
1127             /* Increase the handle value and move to the next entry */
1128             Handle.Value += SizeOfHandle(1);
1129             NewEntry++;
1130             HandleTableEntry++;
1131         } while (Handle.Value % SizeOfHandle(LOW_LEVEL_ENTRIES));
1132
1133         /* We're done, skip the last entry */
1134         Handle.Value += SizeOfHandle(1);
1135     }
1136
1137     /* Acquire the table lock and insert this new table into the list */
1138     ExAcquirePushLockExclusive(&HandleTableListLock);
1139     InsertTailList(&HandleTableListHead, &NewTable->HandleTableList);
1140     ExReleasePushLockExclusive(&HandleTableListLock);
1141
1142     /* Leave the critical region we entered previously and return the table */
1143     KeLeaveCriticalRegion();
1144     return NewTable;
1145 }
1146
1147 BOOLEAN
1148 NTAPI
1149 ExChangeHandle(IN PHANDLE_TABLE HandleTable,
1150                IN HANDLE Handle,
1151                IN PEX_CHANGE_HANDLE_CALLBACK ChangeRoutine,
1152                IN ULONG_PTR Context)
1153 {
1154     EXHANDLE ExHandle;
1155     PHANDLE_TABLE_ENTRY HandleTableEntry;
1156     BOOLEAN Result = FALSE;
1157     PAGED_CODE();
1158
1159     /* Set the handle value */
1160     ExHandle.GenericHandleOverlay = Handle;
1161
1162     /* Find the entry for this handle */
1163     HandleTableEntry = ExpLookupHandleTableEntry(HandleTable, ExHandle);
1164
1165     /* Make sure that we found an entry, and that it's valid */
1166     if (!(HandleTableEntry) ||
1167         !(HandleTableEntry->Object) ||
1168         (HandleTableEntry->NextFreeTableEntry == -2))
1169     {
1170         /* It isn't, fail */
1171         return FALSE;
1172     }
1173
1174     /* Enter a critical region */
1175     KeEnterCriticalRegion();
1176
1177     /* Try locking the handle entry */
1178     if (ExpLockHandleTableEntry(HandleTable, HandleTableEntry))
1179     {
1180         /* Call the change routine and unlock the entry */
1181         Result = ChangeRoutine(HandleTableEntry, Context);
1182         ExUnlockHandleTableEntry(HandleTable, HandleTableEntry);
1183     }
1184
1185     /* Leave the critical region and return the callback result */
1186     KeLeaveCriticalRegion();
1187     return Result;
1188 }
1189
1190 VOID
1191 NTAPI
1192 ExSweepHandleTable(IN PHANDLE_TABLE HandleTable,
1193                    IN PEX_SWEEP_HANDLE_CALLBACK EnumHandleProcedure,
1194                    IN PVOID Context)
1195 {
1196     EXHANDLE Handle;
1197     PHANDLE_TABLE_ENTRY HandleTableEntry;
1198     PAGED_CODE();
1199
1200     /* Set the initial value and loop the entries */
1201     Handle.Value = SizeOfHandle(1);
1202     while ((HandleTableEntry = ExpLookupHandleTableEntry(HandleTable, Handle)))
1203     {
1204         /* Loop each handle */
1205         do
1206         {
1207             /* Lock the entry */
1208             if (ExpLockHandleTableEntry(HandleTable, HandleTableEntry))
1209             {
1210                 /* Notify the callback routine */
1211                 EnumHandleProcedure(HandleTableEntry,
1212                                     Handle.GenericHandleOverlay,
1213                                     Context);
1214             }
1215
1216             /* Go to the next handle and entry */
1217             Handle.Value += SizeOfHandle(1);
1218             HandleTableEntry++;
1219         } while (Handle.Value % SizeOfHandle(LOW_LEVEL_ENTRIES));
1220
1221         /* Skip past the last entry */
1222         Handle.Value += SizeOfHandle(1);
1223     }
1224 }
1225
1226 /*
1227  * @implemented
1228  */
1229 BOOLEAN
1230 NTAPI
1231 ExEnumHandleTable(IN PHANDLE_TABLE HandleTable,
1232                   IN PEX_ENUM_HANDLE_CALLBACK EnumHandleProcedure,
1233                   IN OUT PVOID Context,
1234                   OUT PHANDLE EnumHandle OPTIONAL)
1235 {
1236     EXHANDLE Handle;
1237     PHANDLE_TABLE_ENTRY HandleTableEntry;
1238     BOOLEAN Result = FALSE;
1239     PAGED_CODE();
1240
1241     /* Enter a critical region */
1242     KeEnterCriticalRegion();
1243
1244     /* Set the initial value and loop the entries */
1245     Handle.Value = 0;
1246     while ((HandleTableEntry = ExpLookupHandleTableEntry(HandleTable, Handle)))
1247     {
1248         /* Validate the entry */
1249         if ((HandleTableEntry->Object) &&
1250             (HandleTableEntry->NextFreeTableEntry != -2))
1251         {
1252             /* Lock the entry */
1253             if (ExpLockHandleTableEntry(HandleTable, HandleTableEntry))
1254             {
1255                 /* Notify the callback routine */
1256                 Result = EnumHandleProcedure(HandleTableEntry,
1257                                              Handle.GenericHandleOverlay,
1258                                              Context);
1259
1260                 /* Unlock it */
1261                 ExUnlockHandleTableEntry(HandleTable, HandleTableEntry);
1262
1263                 /* Was this the one looked for? */
1264                 if (Result)
1265                 {
1266                     /* If so, return it if requested */
1267                     if (EnumHandle) *EnumHandle = Handle.GenericHandleOverlay;
1268                     break;
1269                 }
1270             }
1271         }
1272
1273         /* Go to the next entry */
1274         Handle.Value += SizeOfHandle(1);
1275     }
1276
1277     /* Leave the critical region and return callback result */
1278     KeLeaveCriticalRegion();
1279     return Result;
1280 }