ntoskrnl/ex/handle.c

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