Process Hacker
handle.c
Go to the documentation of this file.
1 /*
2  * Process Hacker -
3  * handle table
4  *
5  * Copyright (C) 2010-2011 wj32
6  *
7  * This file is part of Process Hacker.
8  *
9  * Process Hacker is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * Process Hacker is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with Process Hacker. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #include <phbase.h>
24 #include <handlep.h>
25 
26 static PH_FREE_LIST PhHandleTableLevel0FreeList;
27 static PH_FREE_LIST PhHandleTableLevel1FreeList;
28 
30  VOID
31  )
32 {
34  &PhHandleTableLevel0FreeList,
36  64
37  );
39  &PhHandleTableLevel1FreeList,
40  sizeof(PPH_HANDLE_TABLE_ENTRY) * PH_HANDLE_TABLE_LEVEL_ENTRIES,
41  64
42  );
43 }
44 
46  VOID
47  )
48 {
49  PPH_HANDLE_TABLE handleTable;
50  ULONG i;
51 
52 #ifdef PH_HANDLE_TABLE_SAFE
53  handleTable = PhAllocateSafe(sizeof(PH_HANDLE_TABLE));
54 
55  if (!handleTable)
56  return NULL;
57 #else
58  handleTable = PhAllocate(sizeof(PH_HANDLE_TABLE));
59 #endif
60 
61  PhInitializeQueuedLock(&handleTable->Lock);
63 
64  handleTable->NextValue = 0;
65 
66  handleTable->Count = 0;
67  handleTable->TableValue = (ULONG_PTR)PhpCreateHandleTableLevel0(handleTable, TRUE);
68 
69 #ifdef PH_HANDLE_TABLE_SAFE
70  if (!handleTable->TableValue)
71  {
72  PhFree(handleTable);
73  return NULL;
74  }
75 #endif
76 
77  // We have now created the level 0 table.
78  // The free list can now be set up to point to handle 0, which
79  // points to the rest of the free list (1 -> 2 -> 3 -> ...).
80  // The next batch of handles that need to be created start at
81  // PH_HANDLE_TABLE_LEVEL_ENTRIES.
82 
83  handleTable->FreeValue = 0;
85 
86  handleTable->FreeValueAlt = PH_HANDLE_VALUE_INVALID; // no entries in alt. free list
87 
88  handleTable->Flags = 0;
89 
90  for (i = 0; i < PH_HANDLE_TABLE_LOCKS; i++)
91  PhInitializeQueuedLock(&handleTable->Locks[i]);
92 
93  return handleTable;
94 }
95 
97  _In_ _Post_invalid_ PPH_HANDLE_TABLE HandleTable
98  )
99 {
100  ULONG_PTR tableValue;
101  ULONG tableLevel;
102  PPH_HANDLE_TABLE_ENTRY table0;
103  PPH_HANDLE_TABLE_ENTRY *table1;
104  PPH_HANDLE_TABLE_ENTRY **table2;
105  ULONG i;
106  ULONG j;
107 
108  tableValue = HandleTable->TableValue;
109  tableLevel = tableValue & PH_HANDLE_TABLE_LEVEL_MASK;
110  tableValue -= tableLevel;
111 
112  switch (tableLevel)
113  {
114  case 0:
115  {
116  table0 = (PPH_HANDLE_TABLE_ENTRY)tableValue;
117 
118  PhpFreeHandleTableLevel0(table0);
119  }
120  break;
121  case 1:
122  {
123  table1 = (PPH_HANDLE_TABLE_ENTRY *)tableValue;
124 
125  for (i = 0; i < PH_HANDLE_TABLE_LEVEL_ENTRIES; i++)
126  {
127  if (!table1[i])
128  break;
129 
130  PhpFreeHandleTableLevel0(table1[i]);
131  }
132 
133  PhpFreeHandleTableLevel1(table1);
134  }
135  break;
136  case 2:
137  {
138  table2 = (PPH_HANDLE_TABLE_ENTRY **)tableValue;
139 
140  for (i = 0; i < PH_HANDLE_TABLE_LEVEL_ENTRIES; i++)
141  {
142  if (!table2[i])
143  break;
144 
145  for (j = 0; j < PH_HANDLE_TABLE_LEVEL_ENTRIES; j++)
146  {
147  if (!table2[i][j])
148  break;
149 
150  PhpFreeHandleTableLevel0(table2[i][j]);
151  }
152 
153  PhpFreeHandleTableLevel1(table2[i]);
154  }
155 
156  PhpFreeHandleTableLevel2(table2);
157  }
158  break;
159  default:
161  }
162 
163  PhFree(HandleTable);
164 }
165 
167  _Inout_ PPH_HANDLE_TABLE HandleTable,
168  _In_ PPH_HANDLE_TABLE_ENTRY HandleTableEntry
169  )
170 {
171  PH_QUEUED_WAIT_BLOCK waitBlock;
172  ULONG_PTR value;
173 
174  PhQueueWakeEvent(&HandleTable->HandleWakeEvent, &waitBlock);
175 
176  value = HandleTableEntry->Value;
177 
178  if (
181  )
182  {
183  // Entry is not in use or has been unlocked; cancel the wait.
184  PhSetWakeEvent(&HandleTable->HandleWakeEvent, &waitBlock);
185  }
186  else
187  {
188  PhWaitForWakeEvent(&HandleTable->HandleWakeEvent, &waitBlock, TRUE, NULL);
189  }
190 }
191 
193  _Inout_ PPH_HANDLE_TABLE HandleTable,
194  _Inout_ PPH_HANDLE_TABLE_ENTRY HandleTableEntry
195  )
196 {
197  ULONG_PTR value;
198 
199  while (TRUE)
200  {
201  value = HandleTableEntry->Value;
202 
204  return FALSE;
205 
206  if (value & PH_HANDLE_TABLE_ENTRY_LOCKED)
207  {
208  if ((ULONG_PTR)_InterlockedCompareExchangePointer(
209  (PVOID *)&HandleTableEntry->Value,
210  (PVOID)(value - PH_HANDLE_TABLE_ENTRY_LOCKED),
211  (PVOID)value
212  ) == value)
213  {
214  return TRUE;
215  }
216  }
217 
218  PhpBlockOnLockedHandleTableEntry(HandleTable, HandleTableEntry);
219  }
220 }
221 
223  _Inout_ PPH_HANDLE_TABLE HandleTable,
224  _Inout_ PPH_HANDLE_TABLE_ENTRY HandleTableEntry
225  )
226 {
227  _interlockedbittestandset(
228  (PLONG)&HandleTableEntry->Value,
230  );
231  PhSetWakeEvent(&HandleTable->HandleWakeEvent, NULL);
232 }
233 
235  _Inout_ PPH_HANDLE_TABLE HandleTable,
236  _In_ PPH_HANDLE_TABLE_ENTRY HandleTableEntry
237  )
238 {
240  ULONG handleValue;
241 
242  entry = PhpAllocateHandleTableEntry(HandleTable, &handleValue);
243 
244  if (!entry)
245  return NULL;
246 
247  // Copy the given handle table entry to the allocated entry.
248 
249  // All free entries have the Free type and have the (not) locked
250  // bit clear. There is no problem with setting the Type now;
251  // the entry is still locked, so they will block.
253  entry->TypeAndValue.Value = HandleTableEntry->TypeAndValue.Value;
254  entry->Value2 = HandleTableEntry->Value2;
255 
256  // Now we unlock this entry, waking anyone who was caught back
257  // there before we had finished setting up the entry.
258  PhUnlockHandleTableEntry(HandleTable, entry);
259 
260  return PhpEncodeHandle(handleValue);
261 }
262 
264  _Inout_ PPH_HANDLE_TABLE HandleTable,
265  _In_ HANDLE Handle,
266  _In_opt_ PPH_HANDLE_TABLE_ENTRY HandleTableEntry
267  )
268 {
269  ULONG handleValue;
270 
271  handleValue = PhpDecodeHandle(Handle);
272 
273  if (!HandleTableEntry)
274  {
275  HandleTableEntry = PhpLookupHandleTableEntry(HandleTable, handleValue);
276 
277  if (!HandleTableEntry)
278  return FALSE;
279 
280  if (!PhLockHandleTableEntry(HandleTable, HandleTableEntry))
281  return FALSE;
282  }
283 
285  (PVOID *)&HandleTableEntry->Value,
287  );
288 
289  // The handle table entry is now free; wake any waiters because they
290  // can't lock the entry now. Any future lock attempts will fail because
291  // the entry is marked as being free.
292  PhSetWakeEvent(&HandleTable->HandleWakeEvent, NULL);
293 
294  PhpFreeHandleTableEntry(HandleTable, handleValue, HandleTableEntry);
295 
296  return TRUE;
297 }
298 
300  _In_ PPH_HANDLE_TABLE HandleTable,
301  _In_ HANDLE Handle
302  )
303 {
305 
306  entry = PhpLookupHandleTableEntry(HandleTable, PhpDecodeHandle(Handle));
307 
308  if (!entry)
309  return NULL;
310 
311  if (!PhLockHandleTableEntry(HandleTable, entry))
312  return NULL;
313 
314  return entry;
315 }
316 
318  _In_ PPH_HANDLE_TABLE HandleTable,
319  _In_ PPH_ENUM_HANDLE_TABLE_CALLBACK Callback,
320  _In_opt_ PVOID Context
321  )
322 {
323  ULONG handleValue;
325  BOOLEAN cont;
326 
327  handleValue = 0;
328 
329  while (entry = PhpLookupHandleTableEntry(HandleTable, handleValue))
330  {
331  if (PhLockHandleTableEntry(HandleTable, entry))
332  {
333  cont = Callback(
334  HandleTable,
335  PhpEncodeHandle(handleValue),
336  entry,
337  Context
338  );
339  PhUnlockHandleTableEntry(HandleTable, entry);
340 
341  if (!cont)
342  break;
343  }
344 
345  handleValue++;
346  }
347 }
348 
350  _In_ PPH_HANDLE_TABLE HandleTable,
351  _In_ PPH_ENUM_HANDLE_TABLE_CALLBACK Callback,
352  _In_opt_ PVOID Context
353  )
354 {
355  ULONG handleValue;
357  BOOLEAN cont;
358 
359  handleValue = 0;
360 
361  while (entry = PhpLookupHandleTableEntry(HandleTable, handleValue))
362  {
363  if (entry->TypeAndValue.Type == PH_HANDLE_TABLE_ENTRY_IN_USE)
364  {
365  cont = Callback(
366  HandleTable,
367  PhpEncodeHandle(handleValue),
368  entry,
369  Context
370  );
371 
372  if (!cont)
373  break;
374  }
375 
376  handleValue++;
377  }
378 }
379 
381  _In_ PPH_HANDLE_TABLE HandleTable,
382  _In_ PH_HANDLE_TABLE_INFORMATION_CLASS InformationClass,
383  _Out_writes_bytes_opt_(BufferLength) PVOID Buffer,
384  _In_ ULONG BufferLength,
385  _Out_opt_ PULONG ReturnLength
386  )
387 {
388  NTSTATUS status = STATUS_SUCCESS;
389  ULONG returnLength;
390 
391  switch (InformationClass)
392  {
394  {
395  PPH_HANDLE_TABLE_BASIC_INFORMATION basicInfo = Buffer;
396 
397  if (BufferLength == sizeof(PH_HANDLE_TABLE_BASIC_INFORMATION))
398  {
399  basicInfo->Count = HandleTable->Count;
400  basicInfo->Flags = HandleTable->Flags;
401  basicInfo->TableLevel = HandleTable->TableValue & PH_HANDLE_TABLE_LEVEL_MASK;
402  }
403  else
404  {
405  status = STATUS_INFO_LENGTH_MISMATCH;
406  }
407 
408  returnLength = sizeof(PH_HANDLE_TABLE_BASIC_INFORMATION);
409  }
410  break;
412  {
413  PPH_HANDLE_TABLE_FLAGS_INFORMATION flagsInfo = Buffer;
414 
415  if (BufferLength == sizeof(PH_HANDLE_TABLE_FLAGS_INFORMATION))
416  {
417  flagsInfo->Flags = HandleTable->Flags;
418  }
419  else
420  {
421  status = STATUS_INFO_LENGTH_MISMATCH;
422  }
423 
424  returnLength = sizeof(PH_HANDLE_TABLE_FLAGS_INFORMATION);
425  }
426  break;
427  default:
428  status = STATUS_INVALID_INFO_CLASS;
429  returnLength = 0;
430  break;
431  }
432 
433  if (ReturnLength)
434  *ReturnLength = returnLength;
435 
436  return status;
437 }
438 
440  _Inout_ PPH_HANDLE_TABLE HandleTable,
441  _In_ PH_HANDLE_TABLE_INFORMATION_CLASS InformationClass,
442  _In_reads_bytes_(BufferLength) PVOID Buffer,
443  _In_ ULONG BufferLength
444  )
445 {
446  NTSTATUS status = STATUS_SUCCESS;
447 
448  switch (InformationClass)
449  {
451  {
452  PPH_HANDLE_TABLE_FLAGS_INFORMATION flagsInfo = Buffer;
453  ULONG flags;
454 
455  if (BufferLength == sizeof(PH_HANDLE_TABLE_FLAGS_INFORMATION))
456  {
457  flags = flagsInfo->Flags;
458 
459  if ((flags & PH_HANDLE_TABLE_VALID_FLAGS) == flags)
460  HandleTable->Flags = flags;
461  else
462  status = STATUS_INVALID_PARAMETER;
463  }
464  else
465  {
466  status = STATUS_INFO_LENGTH_MISMATCH;
467  }
468  }
469  break;
470  default:
471  status = STATUS_INVALID_INFO_CLASS;
472  }
473 
474  return status;
475 }
476 
478  _Inout_ PPH_HANDLE_TABLE HandleTable,
479  _Out_ PULONG HandleValue
480  )
481 {
483  ULONG freeValue;
484  ULONG lockIndex;
485  ULONG nextFreeValue;
486  ULONG oldFreeValue;
487  BOOLEAN result;
488 
489  while (TRUE)
490  {
491  freeValue = HandleTable->FreeValue;
492 
493  while (freeValue == PH_HANDLE_VALUE_INVALID)
494  {
495  PhAcquireQueuedLockExclusive(&HandleTable->Lock);
496 
497  // Check again to see if we have free handles.
498 
499  freeValue = HandleTable->FreeValue;
500 
501  if (freeValue != PH_HANDLE_VALUE_INVALID)
502  {
503  PhReleaseQueuedLockExclusive(&HandleTable->Lock);
504  break;
505  }
506 
507  // Move handles from the alt. free list to the main free list,
508  // and check again.
509 
510  freeValue = PhpMoveFreeHandleTableEntries(HandleTable);
511 
512  if (freeValue != PH_HANDLE_VALUE_INVALID)
513  {
514  PhReleaseQueuedLockExclusive(&HandleTable->Lock);
515  break;
516  }
517 
518  result = PhpAllocateMoreHandleTableEntries(HandleTable, TRUE);
519 
520  PhReleaseQueuedLockExclusive(&HandleTable->Lock);
521 
522  freeValue = HandleTable->FreeValue;
523 
524  // Note that PhpAllocateMoreHandleTableEntries only
525  // returns FALSE if it failed to allocate memory.
526  // Success does not guarantee a free handle to be
527  // allocated, as they may have been all used up (however
528  // unlikely) when we reach this point. Success simply
529  // means to retry the allocation using the fast path.
530 
531  if (!result && freeValue == PH_HANDLE_VALUE_INVALID)
532  return NULL;
533  }
534 
535  entry = PhpLookupHandleTableEntry(HandleTable, freeValue);
536  lockIndex = PH_HANDLE_TABLE_LOCK_INDEX(freeValue);
537 
538  // To avoid the ABA problem, we would ideally have one
539  // queued lock per handle table entry. That would make the
540  // overhead too large, so instead there is a fixed number of
541  // locks, indexed by the handle value (mod no. locks).
542 
543  // Possibilities at this point:
544  // 1. freeValue != A (our copy), but the other thread has freed
545  // A, so FreeValue = A. No ABA problem since freeValue != A.
546  // 2. freeValue != A, and FreeValue != A. No ABA problem.
547  // 3. freeValue = A, and the other thread has freed A, so
548  // FreeValue = A. No ABA problem since we haven't read
549  // NextFreeValue yet.
550  // 4. freeValue = A, and FreeValue != A. No problem if this
551  // stays the same later, as the CAS will take care of it.
552 
553  PhpLockHandleTableShared(HandleTable, lockIndex);
554 
555  if (HandleTable->FreeValue != freeValue)
556  {
557  PhpUnlockHandleTableShared(HandleTable, lockIndex);
558  continue;
559  }
560 
561  MemoryBarrier();
562 
563  nextFreeValue = entry->NextFreeValue;
564 
565  // Possibilities/non-possibilities at this point:
566  // 1. freeValue != A (our copy), but the other thread has freed
567  // A, so FreeValue = A. This is actually impossible since we
568  // have acquired the lock on A and the free code checks that
569  // and uses the alt. free list instead.
570  // 2. freeValue != A, and FreeValue != A. No ABA problem.
571  // 3. freeValue = A, and the other thread has freed A, so
572  // FreeValue = A. Impossible like above. This is *the* ABA
573  // problem which we have now prevented.
574  // 4. freeValue = A, and FreeValue != A. CAS will take care
575  // of it.
576 
577  oldFreeValue = _InterlockedCompareExchange(
578  &HandleTable->FreeValue,
579  nextFreeValue,
580  freeValue
581  );
582 
583  PhpUnlockHandleTableShared(HandleTable, lockIndex);
584 
585  if (oldFreeValue == freeValue)
586  break;
587  }
588 
589  _InterlockedIncrement((PLONG)&HandleTable->Count);
590 
591  *HandleValue = freeValue;
592 
593  return entry;
594 }
595 
597  _Inout_ PPH_HANDLE_TABLE HandleTable,
598  _In_ ULONG HandleValue,
599  _Inout_ PPH_HANDLE_TABLE_ENTRY HandleTableEntry
600  )
601 {
602  PULONG freeList;
603  ULONG flags;
604  ULONG oldValue;
605 
606  _InterlockedDecrement((PLONG)&HandleTable->Count);
607 
608  flags = HandleTable->Flags;
609 
610  // Choose the free list to use depending on whether someone
611  // is popping from the main free list (see
612  // PhpAllocateHandleTableEntry for details). We always use
613  // the alt. free list if strict FIFO is enabled.
614  if (!(flags & PH_HANDLE_TABLE_STRICT_FIFO) &&
616  &HandleTable->Locks[PH_HANDLE_TABLE_LOCK_INDEX(HandleValue)]))
617  {
618  freeList = &HandleTable->FreeValue;
619  }
620  else
621  {
622  freeList = &HandleTable->FreeValueAlt;
623  }
624 
625  while (TRUE)
626  {
627  oldValue = *freeList;
628  HandleTableEntry->NextFreeValue = oldValue;
629 
630  if (_InterlockedCompareExchange(
631  freeList,
632  HandleValue,
633  oldValue
634  ) == oldValue)
635  {
636  break;
637  }
638  }
639 }
640 
642  _In_ PPH_HANDLE_TABLE HandleTable,
643  _In_ BOOLEAN Initialize
644  )
645 {
646  ULONG_PTR tableValue;
647  ULONG tableLevel;
648  PPH_HANDLE_TABLE_ENTRY table0;
649  PPH_HANDLE_TABLE_ENTRY *table1;
650  PPH_HANDLE_TABLE_ENTRY **table2;
651  ULONG i;
652  ULONG j;
653  ULONG oldNextValue;
654  ULONG freeValue;
655 
656  // Get a pointer to the table, and its level.
657 
658  tableValue = HandleTable->TableValue;
659  tableLevel = tableValue & PH_HANDLE_TABLE_LEVEL_MASK;
660  tableValue -= tableLevel;
661 
662  switch (tableLevel)
663  {
664  case 0:
665  {
666  // Create a level 1 table.
667 
668  table1 = PhpCreateHandleTableLevel1(HandleTable);
669 
670 #ifdef PH_HANDLE_TABLE_SAFE
671  if (!table1)
672  return FALSE;
673 #endif
674 
675  // Create a new level 0 table and move the existing level into
676  // the new level 1 table.
677 
678  table0 = PhpCreateHandleTableLevel0(HandleTable, Initialize);
679 
680 #ifdef PH_HANDLE_TABLE_SAFE
681  if (!table0)
682  {
683  PhpFreeHandleTableLevel1(table1);
684  return FALSE;
685  }
686 #endif
687 
688  table1[0] = (PPH_HANDLE_TABLE_ENTRY)tableValue;
689  table1[1] = table0;
690 
691  tableValue = (ULONG_PTR)table1 | 1;
692  //_InterlockedExchangePointer((PVOID *)&HandleTable->TableValue, (PVOID)tableValue);
693  HandleTable->TableValue = tableValue;
694  }
695  break;
696  case 1:
697  {
698  table1 = (PPH_HANDLE_TABLE_ENTRY *)tableValue;
699 
700  // Determine whether we need to create a new level 0 table or
701  // create a level 2 table.
702 
703  i = HandleTable->NextValue / PH_HANDLE_TABLE_LEVEL_ENTRIES;
704 
706  {
707  table0 = PhpCreateHandleTableLevel0(HandleTable, TRUE);
708 
709 #ifdef PH_HANDLE_TABLE_SAFE
710  if (!table0)
711  return FALSE;
712 #endif
713 
714  //_InterlockedExchangePointer((PVOID *)&table1[i], table0);
715  table1[i] = table0;
716  }
717  else
718  {
719  // Create a level 2 table.
720 
721  table2 = PhpCreateHandleTableLevel2(HandleTable);
722 
723 #ifdef PH_HANDLE_TABLE_SAFE
724  if (!table2)
725  return FALSE;
726 #endif
727 
728  // Create a new level 1 table and move the existing level into
729  // the new level 2 table.
730 
731  table1 = PhpCreateHandleTableLevel1(HandleTable);
732 
733 #ifdef PH_HANDLE_TABLE_SAFE
734  if (!table1)
735  {
736  PhpFreeHandleTableLevel2(table2);
737  return FALSE;
738  }
739 #endif
740 
741  table0 = PhpCreateHandleTableLevel0(HandleTable, Initialize);
742 
743 #ifdef PH_HANDLE_TABLE_SAFE
744  if (!table0)
745  {
746  PhpFreeHandleTableLevel1(table1);
747  PhpFreeHandleTableLevel2(table2);
748  return FALSE;
749  }
750 #endif
751 
752  table1[0] = table0;
753 
754  table2[0] = (PPH_HANDLE_TABLE_ENTRY *)tableValue;
755  table2[1] = table1;
756 
757  tableValue = (ULONG_PTR)table2 | 2;
758  //_InterlockedExchangePointer((PVOID *)&HandleTable->TableValue, (PVOID)tableValue);
759  HandleTable->TableValue = tableValue;
760  }
761  }
762  break;
763  case 2:
764  {
765  table2 = (PPH_HANDLE_TABLE_ENTRY **)tableValue;
766 
767  i = HandleTable->NextValue /
769  // i contains an index into the level 2 table, of the containing
770  // level 1 table.
771 
772  // Check if we have exceeded the maximum number of handles.
773 
775  return FALSE;
776 
777  // Check if we should create a new level 0 table or a new level 2
778  // table.
779  if (table2[i])
780  {
781  table0 = PhpCreateHandleTableLevel0(HandleTable, Initialize);
782 
783 #ifdef PH_HANDLE_TABLE_SAFE
784  if (!table0)
785  return FALSE;
786 #endif
787 
788  // Same as j = HandleTable->NextValue % (no. entries * no. entries),
789  // but we already calculated i so just use it.
790  j = HandleTable->NextValue - i *
793  // j now contains an index into the level 1 table, of the containing
794  // level 0 table (the one which was created).
795 
796  //_InterlockedExchangePointer((PVOID *)&table2[i][j], table0);
797  table2[i][j] = table0;
798  }
799  else
800  {
801  table1 = PhpCreateHandleTableLevel1(HandleTable);
802 
803 #ifdef PH_HANDLE_TABLE_SAFE
804  if (!table1)
805  return FALSE;
806 #endif
807 
808  table0 = PhpCreateHandleTableLevel0(HandleTable, TRUE);
809 
810 #ifdef PH_HANDLE_TABLE_SAFE
811  if (!table0)
812  {
813  PhpFreeHandleTableLevel1(table1);
814  return FALSE;
815  }
816 #endif
817 
818  table1[0] = table0;
819 
820  //_InterlockedExchangePointer((PVOID *)&table2[i], table1);
821  table2[i] = table1;
822  }
823  }
824  break;
825  default:
827  }
828 
829  // In each of the cases above, we allocated one additional level 0 table.
830  oldNextValue = _InterlockedExchangeAdd(
831  (PLONG)&HandleTable->NextValue,
833  );
834 
835  if (Initialize)
836  {
837  // No ABA problem since these are new handles being pushed.
838 
839  while (TRUE)
840  {
841  freeValue = HandleTable->FreeValue;
842  table0[PH_HANDLE_TABLE_LEVEL_ENTRIES - 1].NextFreeValue = freeValue;
843 
844  if (_InterlockedCompareExchange(
845  &HandleTable->FreeValue,
846  oldNextValue,
847  freeValue
848  ) == freeValue)
849  {
850  break;
851  }
852  }
853  }
854 
855  return TRUE;
856 }
857 
859  _In_ PPH_HANDLE_TABLE HandleTable,
860  _In_ ULONG HandleValue
861  )
862 {
863  ULONG_PTR tableValue;
864  ULONG tableLevel;
865  PPH_HANDLE_TABLE_ENTRY table0;
866  PPH_HANDLE_TABLE_ENTRY *table1;
867  PPH_HANDLE_TABLE_ENTRY **table2;
869 
870  if (HandleValue >= HandleTable->NextValue)
871  return NULL;
872 
873  // Get a pointer to the table, and its level.
874 
875  tableValue = HandleTable->TableValue;
876  tableLevel = tableValue & PH_HANDLE_TABLE_LEVEL_MASK;
877  tableValue -= tableLevel;
878 
879  // No additional checking needed; aleady checked against
880  // NextValue.
881 
882  switch (tableLevel)
883  {
884  case 0:
885  {
886  table0 = (PPH_HANDLE_TABLE_ENTRY)tableValue;
887  entry = &table0[HandleValue];
888  }
889  break;
890  case 1:
891  {
892  table1 = (PPH_HANDLE_TABLE_ENTRY *)tableValue;
893  table0 = table1[PH_HANDLE_VALUE_LEVEL1_U(HandleValue)];
894  entry = &table0[PH_HANDLE_VALUE_LEVEL0(HandleValue)];
895  }
896  break;
897  case 2:
898  {
899  table2 = (PPH_HANDLE_TABLE_ENTRY **)tableValue;
900  table1 = table2[PH_HANDLE_VALUE_LEVEL2_U(HandleValue)];
901  table0 = table1[PH_HANDLE_VALUE_LEVEL1(HandleValue)];
902  entry = &table0[PH_HANDLE_VALUE_LEVEL0(HandleValue)];
903  }
904  break;
905  default:
907  }
908 
909  return entry;
910 }
911 
913  _Inout_ PPH_HANDLE_TABLE HandleTable
914  )
915 {
916  ULONG freeValueAlt;
917  ULONG flags;
918  ULONG i;
919  ULONG index;
920  ULONG nextIndex;
921  ULONG lastIndex;
923  PPH_HANDLE_TABLE_ENTRY firstEntry;
924  ULONG count;
925  ULONG freeValue;
926 
927  // Remove all entries from the alt. free list.
928  freeValueAlt = _InterlockedExchange(&HandleTable->FreeValueAlt, PH_HANDLE_VALUE_INVALID);
929 
930  if (freeValueAlt == PH_HANDLE_VALUE_INVALID)
931  {
932  // No handles on the alt. free list.
934  }
935 
936  // Avoid the ABA problem by testing all locks (see
937  // PhpAllocateHandleTableEntry for details). Unlike
938  // in PhpFreeHandleTableEntry we have no "alternative"
939  // list, so we must allow blocking.
940  for (i = 0; i < PH_HANDLE_TABLE_LOCKS; i++)
941  PhAcquireReleaseQueuedLockExclusive(&HandleTable->Locks[i]);
942 
943  flags = HandleTable->Flags;
944 
945  if (!(flags & PH_HANDLE_TABLE_STRICT_FIFO))
946  {
947  // Shortcut: if there are no entries in the main free list and
948  // we don't need to reverse the chain, just return.
949  if (_InterlockedCompareExchange(
950  &HandleTable->FreeValue,
951  freeValueAlt,
954  return freeValueAlt;
955  }
956 
957  // Reverse the chain (even if strict FIFO is off; we have to
958  // traverse the list to find the last entry, so we might as well
959  // reverse it along the way).
960 
961  index = freeValueAlt;
962  lastIndex = PH_HANDLE_VALUE_INVALID;
963  count = 0;
964 
965  while (TRUE)
966  {
967  entry = PhpLookupHandleTableEntry(HandleTable, index);
968  count++;
969 
970  if (lastIndex == PH_HANDLE_VALUE_INVALID)
971  firstEntry = entry;
972 
973  nextIndex = entry->NextFreeValue;
974  entry->NextFreeValue = lastIndex;
975  lastIndex = index;
976 
977  if (nextIndex == PH_HANDLE_VALUE_INVALID)
978  break;
979 
980  index = nextIndex;
981  }
982 
983  // Note that firstEntry actually contains the last free
984  // entry, since we reversed the list. Similarly
985  // index/lastIndex both contain the index of the first
986  // free entry.
987 
988  // Push the entries onto the free list.
989  while (TRUE)
990  {
991  freeValue = HandleTable->FreeValue;
992  firstEntry->NextFreeValue = freeValue;
993 
994  if (_InterlockedCompareExchange(
995  &HandleTable->FreeValue,
996  index,
997  freeValue
998  ) == freeValue)
999  break;
1000  }
1001 
1002  // Force expansion if we don't have enough free handles.
1003  if (
1004  (flags & PH_HANDLE_TABLE_STRICT_FIFO) &&
1006  )
1007  {
1008  index = PH_HANDLE_VALUE_INVALID;
1009  }
1010 
1011  return index;
1012 }
1013 
1015  _In_ PPH_HANDLE_TABLE HandleTable,
1016  _In_ BOOLEAN Initialize
1017  )
1018 {
1019  PPH_HANDLE_TABLE_ENTRY table;
1020  PPH_HANDLE_TABLE_ENTRY entry;
1021  ULONG baseValue;
1022  ULONG i;
1023 
1024 #ifdef PH_HANDLE_TABLE_SAFE
1025  __try
1026  {
1027  table = PhAllocateFromFreeList(&PhHandleTableLevel0FreeList);
1028  }
1029  __except (SIMPLE_EXCEPTION_FILTER(GetExceptionCode() == STATUS_NO_MEMORY))
1030  {
1031  return NULL;
1032  }
1033 #else
1034  table = PhAllocateFromFreeList(&PhHandleTableLevel0FreeList);
1035 #endif
1036 
1037  if (Initialize)
1038  {
1039  entry = &table[0];
1040  baseValue = HandleTable->NextValue;
1041 
1042  for (i = baseValue + 1; i < baseValue + PH_HANDLE_TABLE_LEVEL_ENTRIES; i++)
1043  {
1045  entry->NextFreeValue = i;
1046  entry++;
1047  }
1048 
1051  }
1052 
1053  return table;
1054 }
1055 
1057  _In_ PPH_HANDLE_TABLE_ENTRY Table
1058  )
1059 {
1060  PhFreeToFreeList(&PhHandleTableLevel0FreeList, Table);
1061 }
1062 
1064  _In_ PPH_HANDLE_TABLE HandleTable
1065  )
1066 {
1067  PPH_HANDLE_TABLE_ENTRY *table;
1068 
1069 #ifdef PH_HANDLE_TABLE_SAFE
1070  __try
1071  {
1072  table = PhAllocateFromFreeList(&PhHandleTableLevel1FreeList);
1073  }
1074  __except (SIMPLE_EXCEPTION_FILTER(GetExceptionCode() == STATUS_NO_MEMORY))
1075  {
1076  return NULL;
1077  }
1078 #else
1079  table = PhAllocateFromFreeList(&PhHandleTableLevel1FreeList);
1080 #endif
1081 
1082  memset(table, 0, sizeof(PPH_HANDLE_TABLE_ENTRY) * PH_HANDLE_TABLE_LEVEL_ENTRIES);
1083 
1084  return table;
1085 }
1086 
1088  _In_ PPH_HANDLE_TABLE_ENTRY *Table
1089  )
1090 {
1091  PhFreeToFreeList(&PhHandleTableLevel1FreeList, Table);
1092 }
1093 
1095  _In_ PPH_HANDLE_TABLE HandleTable
1096  )
1097 {
1098  PPH_HANDLE_TABLE_ENTRY **table;
1099 
1100 #ifdef PH_HANDLE_TABLE_SAFE
1102 
1103  if (!table)
1104  return NULL;
1105 #else
1106  table = PhAllocate(sizeof(PPH_HANDLE_TABLE_ENTRY *) * PH_HANDLE_TABLE_LEVEL_ENTRIES);
1107 #endif
1108 
1109  memset(table, 0, sizeof(PPH_HANDLE_TABLE_ENTRY *) * PH_HANDLE_TABLE_LEVEL_ENTRIES);
1110 
1111  return table;
1112 }
1113 
1115  _In_ PPH_HANDLE_TABLE_ENTRY **Table
1116  )
1117 {
1118  PhFree(Table);
1119 }