Process Hacker
filepool.c
Go to the documentation of this file.
1 /*
2  * Process Hacker -
3  * file-based allocator
4  *
5  * Copyright (C) 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 /*
24  * File pool allows blocks of storage to be allocated from a file. Each
25  * file looks like this:
26  *
27  * Segment 0 __________________________________________________________
28  * | | | | |
29  * | Block Header | File Header | Block Header | Segment Header |
30  * |______________|________________|______________|________________|
31  * | | | | |
32  * | Block Header | User Data | Block Header | User Data |
33  * |______________|________________|______________|________________|
34  * | | | | |
35  * | ... | ... | ... | ... |
36  * |______________|________________|______________|________________|
37  * Segment 1 __________________________________________________________
38  * | | | | |
39  * | Block Header | Segment Header | Block Header | User Data |
40  * |______________|________________|______________|________________|
41  * | | | | |
42  * | ... | ... | ... | ... |
43  * |______________|________________|______________|________________|
44  * Segment 2 __________________________________________________________
45  * | | | | |
46  * | ... | ... | ... | ... |
47  * |______________|________________|______________|________________|
48  *
49  * A file consists of a variable number of segments, with the segment
50  * size specified as a power of two. Each segment contains a fixed
51  * number of blocks, leading to a variable block size. Every
52  * allocation made by the user is an allocation of a certain number
53  * of blocks, with enough space for the block header. This is placed
54  * at the beginning of each allocation and contains the number of
55  * blocks in the allocation (a better name for it would be the
56  * allocation header).
57  *
58  * Block management in each segment is handled by a bitmap which is
59  * stored in the segment header at the beginning of each segment.
60  * The first segment (segment 0) is special with the file header
61  * being placed immediately after an initial block header. This is
62  * because the segment size is stored in the file header, and without
63  * it we cannot calculate the block size, which is used to locate
64  * everything else in the file.
65  *
66  * To speed up allocations a number of free lists are maintained
67  * which categorize each segment based on how many free blocks
68  * they have. This means we can avoid trying to allocate from
69  * every existing segment before finding out we have to allocate a
70  * new segment, or trying to allocate from segments without the
71  * required number of free blocks. The downside of this technique is
72  * that it doesn't account for fragmentation within the allocation
73  * bitmap.
74  *
75  * Each segment is mapped in separately, and each view is cached.
76  * Even after a view becomes inactive (has a reference count of 0)
77  * it remains mapped in until the maximum number of inactive views
78  * is reached.
79  */
80 
81 #include <ph.h>
82 #include <filepool.h>
83 #include <filepoolp.h>
84 
94  _Out_ PPH_FILE_POOL *Pool,
95  _In_ HANDLE FileHandle,
96  _In_ BOOLEAN ReadOnly,
97  _In_opt_ PPH_FILE_POOL_PARAMETERS Parameters
98  )
99 {
100  NTSTATUS status;
101  PPH_FILE_POOL pool;
102  LARGE_INTEGER fileSize;
103  PH_FILE_POOL_PARAMETERS localParameters;
104  BOOLEAN creating;
105  HANDLE sectionHandle;
106  PPH_FP_BLOCK_HEADER initialBlock;
107  PPH_FP_FILE_HEADER header;
108  ULONG i;
109 
110  if (Parameters)
111  {
112  PhpValidateFilePoolParameters(Parameters);
113  }
114  else
115  {
116  PhpSetDefaultFilePoolParameters(&localParameters);
117  Parameters = &localParameters;
118  }
119 
120  pool = PhAllocate(sizeof(PH_FILE_POOL));
121  memset(pool, 0, sizeof(PH_FILE_POOL));
122 
123  pool->FileHandle = FileHandle;
124  pool->ReadOnly = ReadOnly;
125 
126  if (!NT_SUCCESS(status = PhGetFileSize(FileHandle, &fileSize)))
127  goto CleanupExit;
128 
129  creating = FALSE;
130 
131  // If the file is smaller than the page size, assume we're creating a new file.
132  if (fileSize.QuadPart < PAGE_SIZE)
133  {
134  if (ReadOnly)
135  {
136  status = STATUS_BAD_FILE_TYPE;
137  goto CleanupExit;
138  }
139 
140  fileSize.QuadPart = PAGE_SIZE;
141 
142  if (!NT_SUCCESS(status = PhSetFileSize(FileHandle, &fileSize)))
143  goto CleanupExit;
144 
145  creating = TRUE;
146  }
147 
148  // Create a section.
149  status = NtCreateSection(
150  &sectionHandle,
151  SECTION_ALL_ACCESS,
152  NULL,
153  &fileSize,
154  !ReadOnly ? PAGE_READWRITE : PAGE_READONLY,
155  SEC_COMMIT,
156  FileHandle
157  );
158 
159  if (!NT_SUCCESS(status))
160  goto CleanupExit;
161 
162  pool->SectionHandle = sectionHandle;
163 
164  // Map in the first segment, set up initial parameters, then remap the
165  // first segment.
166 
167  if (!NT_SUCCESS(status = PhFppMapRange(pool, 0, PAGE_SIZE, &initialBlock)))
168  goto CleanupExit;
169 
170  header = (PPH_FP_FILE_HEADER)&initialBlock->Body;
171 
172  if (creating)
173  {
174  header->Magic = PH_FP_MAGIC;
175  header->SegmentShift = Parameters->SegmentShift;
176  header->SegmentCount = 1;
177 
178  for (i = 0; i < PH_FP_FREE_LIST_COUNT; i++)
179  header->FreeLists[i] = -1;
180  }
181  else
182  {
183  if (header->Magic != PH_FP_MAGIC)
184  {
185  PhFppUnmapRange(pool, initialBlock);
186  status = STATUS_BAD_FILE_TYPE;
187  goto CleanupExit;
188  }
189  }
190 
191  pool->SegmentShift = header->SegmentShift;
192  pool->SegmentSize = 1 << pool->SegmentShift;
193 
195  pool->BlockSize = 1 << pool->BlockShift;
196  pool->FileHeaderBlockSpan = (sizeof(PH_FP_FILE_HEADER) + pool->BlockSize - 1) >> pool->BlockShift;
197  pool->SegmentHeaderBlockSpan = (sizeof(PH_FP_SEGMENT_HEADER) + pool->BlockSize - 1) >> pool->BlockShift;
198 
199  // Unmap the first segment and remap with the new segment size.
200 
201  PhFppUnmapRange(pool, initialBlock);
202 
203  if (creating)
204  {
205  // Extend the section so it fits the entire first segment.
206  if (!NT_SUCCESS(status = PhFppExtendRange(pool, pool->SegmentSize)))
207  goto CleanupExit;
208  }
209 
210  // Runtime structure initialization
211 
213  pool->ByIndexSize = 32;
214  pool->ByIndexBuckets = PhAllocate(sizeof(PPH_FILE_POOL_VIEW) * pool->ByIndexSize);
215  memset(pool->ByIndexBuckets, 0, sizeof(PPH_FILE_POOL_VIEW) * pool->ByIndexSize);
217 
218  pool->MaximumInactiveViews = Parameters->MaximumInactiveViews;
220 
221  // File structure initialization
222 
225 
226  if (creating)
227  {
228  PPH_FP_BLOCK_HEADER segmentHeaderBlock;
229 
230  // Set up the first segment properly.
231 
233  segmentHeaderBlock = (PPH_FP_BLOCK_HEADER)((PCHAR)pool->FirstBlockOfFirstSegment + (pool->FileHeaderBlockSpan << pool->BlockShift));
234  PhFppInitializeSegment(pool, segmentHeaderBlock, pool->FileHeaderBlockSpan);
235 
236  pool->Header->FreeLists[1] = 0;
237  }
238 
239 CleanupExit:
240  if (NT_SUCCESS(status))
241  {
242  *Pool = pool;
243  }
244  else
245  {
246  // Don't close the file handle the user passed in.
247  pool->FileHandle = NULL;
248  PhDestroyFilePool(pool);
249  }
250 
251  return status;
252 }
253 
266  _Out_ PPH_FILE_POOL *Pool,
267  _In_ PWSTR FileName,
268  _In_ BOOLEAN ReadOnly,
269  _In_ ULONG ShareAccess,
270  _In_ ULONG CreateDisposition,
271  _In_opt_ PPH_FILE_POOL_PARAMETERS Parameters
272  )
273 {
274  NTSTATUS status;
275  PPH_FILE_POOL pool;
276  HANDLE fileHandle;
277  ULONG createStatus;
278 
279  if (!NT_SUCCESS(status = PhCreateFileWin32Ex(
280  &fileHandle,
281  FileName,
282  !ReadOnly ? (FILE_GENERIC_READ | FILE_GENERIC_WRITE | DELETE) : FILE_GENERIC_READ,
283  FILE_ATTRIBUTE_NORMAL,
284  ShareAccess,
285  CreateDisposition,
287  &createStatus
288  )))
289  {
290  return status;
291  }
292 
293  status = PhCreateFilePool(&pool, fileHandle, ReadOnly, Parameters);
294 
295  if (NT_SUCCESS(status))
296  {
297  *Pool = pool;
298  }
299  else
300  {
301  if (!ReadOnly && createStatus == FILE_CREATED)
302  {
303  FILE_DISPOSITION_INFORMATION dispositionInfo;
304  IO_STATUS_BLOCK isb;
305 
306  dispositionInfo.DeleteFile = TRUE;
307  NtSetInformationFile(fileHandle, &isb, &dispositionInfo, sizeof(FILE_DISPOSITION_INFORMATION), FileDispositionInformation);
308  }
309 
310  NtClose(fileHandle);
311  }
312 
313  return status;
314 }
315 
322  _In_ _Post_invalid_ PPH_FILE_POOL Pool
323  )
324 {
325  ULONG i;
326  PLIST_ENTRY head;
327  PLIST_ENTRY entry;
328  PPH_FILE_POOL_VIEW view;
329 
330  // Unmap all views.
331  for (i = 0; i < Pool->ByIndexSize; i++)
332  {
333  if (head = Pool->ByIndexBuckets[i])
334  {
335  entry = head;
336 
337  do
338  {
339  view = CONTAINING_RECORD(entry, PH_FILE_POOL_VIEW, ByIndexListEntry);
340  entry = entry->Flink;
341  PhFppUnmapRange(Pool, view->Base);
342  PhFreeToFreeList(&Pool->ViewFreeList, view);
343  } while (entry != head);
344  }
345  }
346 
347  if (Pool->ByIndexBuckets)
348  PhFree(Pool->ByIndexBuckets);
349 
350  PhDeleteFreeList(&Pool->ViewFreeList);
351 
352  if (Pool->SectionHandle)
353  NtClose(Pool->SectionHandle);
354  if (Pool->FileHandle)
355  NtClose(Pool->FileHandle);
356 
357  PhFree(Pool);
358 }
359 
367  _Inout_ PPH_FILE_POOL_PARAMETERS Parameters
368  )
369 {
370  NTSTATUS status = STATUS_SUCCESS;
371 
372  // 16 <= SegmentShift <= 28
373 
374  if (Parameters->SegmentShift < 16)
375  {
376  Parameters->SegmentShift = 16;
377  status = STATUS_SOME_NOT_MAPPED;
378  }
379 
380  if (Parameters->SegmentShift > 28)
381  {
382  Parameters->SegmentShift = 28;
383  status = STATUS_SOME_NOT_MAPPED;
384  }
385 
386  return status;
387 }
388 
396  _Out_ PPH_FILE_POOL_PARAMETERS Parameters
397  )
398 {
399  Parameters->SegmentShift = 18; // 256kB
400  Parameters->MaximumInactiveViews = 128;
401 }
402 
420  _Inout_ PPH_FILE_POOL Pool,
421  _In_ ULONG Size,
422  _Out_opt_ PULONG Rva
423  )
424 {
425  PPH_FP_BLOCK_HEADER blockHeader;
426  ULONG numberOfBlocks;
427  PPH_FP_BLOCK_HEADER firstBlock;
428  PPH_FP_SEGMENT_HEADER segmentHeader;
429  ULONG freeListIndex;
430  ULONG freeListLimit;
431  ULONG segmentIndex;
432  ULONG nextSegmentIndex;
433  ULONG newFreeListIndex;
434 
435  // Calculate the number of blocks needed for the allocation.
436  numberOfBlocks = (FIELD_OFFSET(PH_FP_BLOCK_HEADER, Body) + Size + Pool->BlockSize - 1) >> Pool->BlockShift;
437 
438  if (numberOfBlocks > PH_FP_BLOCK_COUNT - Pool->SegmentHeaderBlockSpan)
439  {
440  // TODO: Perform a large allocation.
441  return NULL;
442  }
443 
444  // Scan each applicable free list and try to allocate from those segments.
445 
446  freeListLimit = PhFppComputeFreeListIndex(Pool, numberOfBlocks);
447 
448  for (freeListIndex = 0; freeListIndex <= freeListLimit; freeListIndex++)
449  {
450  segmentIndex = Pool->Header->FreeLists[freeListIndex];
451 
452  while (segmentIndex != -1)
453  {
454  firstBlock = PhFppReferenceSegment(Pool, segmentIndex);
455 
456  if (!firstBlock)
457  return NULL;
458 
459  segmentHeader = PhFppGetHeaderSegment(Pool, firstBlock);
460  nextSegmentIndex = segmentHeader->FreeFlink;
461 
462  blockHeader = PhFppAllocateBlocks(Pool, firstBlock, segmentHeader, numberOfBlocks);
463 
464  if (blockHeader)
465  goto BlockAllocated;
466 
467  PhFppDereferenceSegment(Pool, segmentIndex);
468  segmentIndex = nextSegmentIndex;
469  }
470  }
471 
472  // No segments have the required number of contiguous free blocks. Allocate a new one.
473 
474  firstBlock = PhFppAllocateSegment(Pool, &segmentIndex);
475 
476  if (!firstBlock)
477  return NULL;
478 
479  freeListIndex = 0;
480  segmentHeader = PhFppGetHeaderSegment(Pool, firstBlock);
481  blockHeader = PhFppAllocateBlocks(Pool, firstBlock, segmentHeader, numberOfBlocks);
482 
483  if (!blockHeader)
484  {
485  PhFppDereferenceSegment(Pool, segmentIndex);
486  return NULL;
487  }
488 
489 BlockAllocated:
490 
491  // Compute the new free list index of the segment and move it to another free list if necessary.
492 
493  newFreeListIndex = PhFppComputeFreeListIndex(Pool, segmentHeader->FreeBlocks);
494 
495  if (newFreeListIndex != freeListIndex)
496  {
497  PhFppRemoveFreeList(Pool, freeListIndex, segmentIndex, segmentHeader);
498  PhFppInsertFreeList(Pool, newFreeListIndex, segmentIndex, segmentHeader);
499  }
500 
501  if (Rva)
502  {
503  *Rva = PhFppEncodeRva(Pool, segmentIndex, firstBlock, &blockHeader->Body);
504  }
505 
506  return &blockHeader->Body;
507 }
508 
518  _Inout_ PPH_FILE_POOL Pool,
519  _In_ ULONG SegmentIndex,
520  _In_ PPH_FP_BLOCK_HEADER FirstBlock,
521  _In_ PVOID Block
522  )
523 {
524  PPH_FP_SEGMENT_HEADER segmentHeader;
525  ULONG oldFreeListIndex;
526  ULONG newFreeListIndex;
527 
528  segmentHeader = PhFppGetHeaderSegment(Pool, FirstBlock);
529  oldFreeListIndex = PhFppComputeFreeListIndex(Pool, segmentHeader->FreeBlocks);
530  PhFppFreeBlocks(Pool, FirstBlock, segmentHeader, PhFppGetHeaderBlock(Pool, Block));
531  newFreeListIndex = PhFppComputeFreeListIndex(Pool, segmentHeader->FreeBlocks);
532 
533  // Move the segment into another free list if needed.
534  if (newFreeListIndex != oldFreeListIndex)
535  {
536  PhFppRemoveFreeList(Pool, oldFreeListIndex, SegmentIndex, segmentHeader);
537  PhFppInsertFreeList(Pool, newFreeListIndex, SegmentIndex, segmentHeader);
538  }
539 }
540 
550  _Inout_ PPH_FILE_POOL Pool,
551  _In_ PVOID Block
552  )
553 {
554  PPH_FILE_POOL_VIEW view;
555  PPH_FP_BLOCK_HEADER firstBlock;
556 
557  view = PhFppFindViewByBase(Pool, Block);
558 
559  if (!view)
560  PhRaiseStatus(STATUS_INVALID_PARAMETER_2);
561 
562  firstBlock = view->Base;
563  PhpFreeFilePool(Pool, view->SegmentIndex, firstBlock, Block);
564  PhFppDereferenceView(Pool, view);
565 }
566 
574  _Inout_ PPH_FILE_POOL Pool,
575  _In_ ULONG Rva
576  )
577 {
578  ULONG segmentIndex;
579  ULONG offset;
580  PPH_FP_BLOCK_HEADER firstBlock;
581 
582  offset = PhFppDecodeRva(Pool, Rva, &segmentIndex);
583 
584  if (offset == -1)
585  return FALSE;
586 
587  firstBlock = PhFppReferenceSegment(Pool, segmentIndex);
588 
589  if (!firstBlock)
590  return FALSE;
591 
592  PhpFreeFilePool(Pool, segmentIndex, firstBlock, (PCHAR)firstBlock + offset);
593  PhFppDereferenceSegment(Pool, segmentIndex);
594 
595  return TRUE;
596 }
597 
605  _Inout_ PPH_FILE_POOL Pool,
606  _In_ PVOID Address
607  )
608 {
609  PhFppReferenceSegmentByBase(Pool, Address);
610 }
611 
619  _Inout_ PPH_FILE_POOL Pool,
620  _In_ PVOID Address
621  )
622 {
623  PhFppDereferenceSegmentByBase(Pool, Address);
624 }
625 
634  _Inout_ PPH_FILE_POOL Pool,
635  _In_ ULONG Rva
636  )
637 {
638  ULONG segmentIndex;
639  ULONG offset;
640  PPH_FP_BLOCK_HEADER firstBlock;
641 
642  if (Rva == 0)
643  return NULL;
644 
645  offset = PhFppDecodeRva(Pool, Rva, &segmentIndex);
646 
647  if (offset == -1)
648  return NULL;
649 
650  firstBlock = PhFppReferenceSegment(Pool, segmentIndex);
651 
652  if (!firstBlock)
653  return NULL;
654 
655  return (PCHAR)firstBlock + offset;
656 }
657 
665  _Inout_ PPH_FILE_POOL Pool,
666  _In_ ULONG Rva
667  )
668 {
669  ULONG segmentIndex;
670  ULONG offset;
671 
672  offset = PhFppDecodeRva(Pool, Rva, &segmentIndex);
673 
674  if (offset == -1)
675  return FALSE;
676 
677  PhFppDereferenceSegment(Pool, segmentIndex);
678 
679  return TRUE;
680 }
681 
693  _In_ PPH_FILE_POOL Pool,
694  _In_ PVOID Address
695  )
696 {
697  PPH_FILE_POOL_VIEW view;
698 
699  if (!Address)
700  return 0;
701 
702  view = PhFppFindViewByBase(Pool, Address);
703 
704  if (!view)
705  PhRaiseStatus(STATUS_INVALID_PARAMETER_2);
706 
707  return PhFppEncodeRva(Pool, view->SegmentIndex, view->Base, Address);
708 }
709 
717  _In_ PPH_FILE_POOL Pool,
718  _Out_ PULONGLONG Context
719  )
720 {
721  *Context = Pool->Header->UserContext;
722 }
723 
731  _Inout_ PPH_FILE_POOL Pool,
732  _In_ PULONGLONG Context
733  )
734 {
735  Pool->Header->UserContext = *Context;
736 }
737 
745  _Inout_ PPH_FILE_POOL Pool,
746  _In_ ULONG NewSize
747  )
748 {
749  LARGE_INTEGER newSectionSize;
750 
751  newSectionSize.QuadPart = NewSize;
752 
753  return NtExtendSection(Pool->SectionHandle, &newSectionSize);
754 }
755 
764 NTSTATUS PhFppMapRange(
765  _Inout_ PPH_FILE_POOL Pool,
766  _In_ ULONG Offset,
767  _In_ ULONG Size,
768  _Out_ PVOID *Base
769  )
770 {
771  NTSTATUS status;
772  PVOID baseAddress;
773  LARGE_INTEGER sectionOffset;
774  SIZE_T viewSize;
775 
776  baseAddress = NULL;
777  sectionOffset.QuadPart = Offset;
778  viewSize = Size;
779 
780  status = NtMapViewOfSection(
781  Pool->SectionHandle,
782  NtCurrentProcess(),
783  &baseAddress,
784  0,
785  viewSize,
786  &sectionOffset,
787  &viewSize,
788  ViewShare,
789  0,
790  !Pool->ReadOnly ? PAGE_READWRITE : PAGE_READONLY
791  );
792 
793  if (NT_SUCCESS(status))
794  *Base = baseAddress;
795 
796  return status;
797 }
798 
806  _Inout_ PPH_FILE_POOL Pool,
807  _In_ PVOID Base
808  )
809 {
810  return NtUnmapViewOfSection(NtCurrentProcess(), Base);
811 }
812 
823  _Inout_ PPH_FILE_POOL Pool,
824  _Out_ PPH_FP_BLOCK_HEADER BlockOfSegmentHeader,
825  _In_ ULONG AdditionalBlocksUsed
826  )
827 {
828  PPH_FP_SEGMENT_HEADER segmentHeader;
829  RTL_BITMAP bitmap;
830 
831  BlockOfSegmentHeader->Span = Pool->SegmentHeaderBlockSpan;
832  segmentHeader = (PPH_FP_SEGMENT_HEADER)&BlockOfSegmentHeader->Body;
833 
834  RtlInitializeBitMap(&bitmap, segmentHeader->Bitmap, PH_FP_BLOCK_COUNT);
835  RtlSetBits(&bitmap, 0, Pool->SegmentHeaderBlockSpan + AdditionalBlocksUsed);
836  segmentHeader->FreeBlocks = PH_FP_BLOCK_COUNT - (Pool->SegmentHeaderBlockSpan + AdditionalBlocksUsed);
837  segmentHeader->FreeFlink = -1;
838  segmentHeader->FreeBlink = -1;
839 }
840 
851  _Inout_ PPH_FILE_POOL Pool,
852  _Out_ PULONG NewSegmentIndex
853  )
854 {
855  ULONG newSize;
856  ULONG segmentIndex;
857  PPH_FP_BLOCK_HEADER firstBlock;
858  PPH_FP_SEGMENT_HEADER segmentHeader;
859 
860  newSize = (Pool->Header->SegmentCount + 1) << Pool->SegmentShift;
861 
862  if (!NT_SUCCESS(PhFppExtendRange(Pool, newSize)))
863  return NULL;
864 
865  segmentIndex = Pool->Header->SegmentCount++;
866  firstBlock = PhFppReferenceSegment(Pool, segmentIndex);
867  PhFppInitializeSegment(Pool, firstBlock, 0);
868  segmentHeader = (PPH_FP_SEGMENT_HEADER)&firstBlock->Body;
869 
870  PhFppInsertFreeList(Pool, 0, segmentIndex, segmentHeader);
871 
872  *NewSegmentIndex = segmentIndex;
873 
874  return firstBlock;
875 }
876 
884  _Inout_ PPH_FILE_POOL Pool,
885  _In_ PPH_FP_BLOCK_HEADER FirstBlock
886  )
887 {
888  if (FirstBlock != Pool->FirstBlockOfFirstSegment)
889  {
890  return (PPH_FP_SEGMENT_HEADER)&FirstBlock->Body;
891  }
892  else
893  {
894  // In the first segment, the segment header is after the file header.
895  return (PPH_FP_SEGMENT_HEADER)&((PPH_FP_BLOCK_HEADER)((PCHAR)FirstBlock + (Pool->FileHeaderBlockSpan << Pool->BlockShift)))->Body;
896  }
897 }
898 
900  _Inout_ PPH_FILE_POOL Pool,
901  _Inout_ PPH_FILE_POOL_VIEW View
902  )
903 {
904  ULONG index;
905  PLIST_ENTRY head;
906 
907  index = View->SegmentIndex & (Pool->ByIndexSize - 1);
908  head = Pool->ByIndexBuckets[index];
909 
910  if (head)
911  {
912  InsertHeadList(head, &View->ByIndexListEntry);
913  }
914  else
915  {
916  InitializeListHead(&View->ByIndexListEntry);
917  Pool->ByIndexBuckets[index] = &View->ByIndexListEntry;
918  }
919 }
920 
922  _Inout_ PPH_FILE_POOL Pool,
923  _Inout_ PPH_FILE_POOL_VIEW View
924  )
925 {
926  ULONG index;
927  PLIST_ENTRY head;
928 
929  index = View->SegmentIndex & (Pool->ByIndexSize - 1);
930  head = Pool->ByIndexBuckets[index];
931  assert(head);
932 
933  // Unlink the entry from the chain.
934  RemoveEntryList(&View->ByIndexListEntry);
935 
936  if (&View->ByIndexListEntry == head)
937  {
938  // This entry is currently the chain head.
939 
940  // If this was the last entry in the chain, then indicate
941  // that the chain is empty.
942  // Otherwise, choose a new head.
943 
944  if (IsListEmpty(head))
945  Pool->ByIndexBuckets[index] = NULL;
946  else
947  Pool->ByIndexBuckets[index] = head->Flink;
948  }
949 }
950 
961  _Inout_ PPH_FILE_POOL Pool,
962  _In_ ULONG SegmentIndex
963  )
964 {
965  ULONG index;
966  PLIST_ENTRY head;
967  PLIST_ENTRY entry;
968  PPH_FILE_POOL_VIEW view;
969 
970  index = SegmentIndex & (Pool->ByIndexSize - 1);
971  head = Pool->ByIndexBuckets[index];
972 
973  if (!head)
974  return NULL;
975 
976  entry = head;
977 
978  do
979  {
980  view = CONTAINING_RECORD(entry, PH_FILE_POOL_VIEW, ByIndexListEntry);
981 
982  if (view->SegmentIndex == SegmentIndex)
983  return view;
984 
985  entry = entry->Flink;
986  } while (entry != head);
987 
988  return NULL;
989 }
990 
992  _In_ PPH_AVL_LINKS Links1,
993  _In_ PPH_AVL_LINKS Links2
994  )
995 {
996  PPH_FILE_POOL_VIEW view1 = CONTAINING_RECORD(Links1, PH_FILE_POOL_VIEW, ByBaseLinks);
997  PPH_FILE_POOL_VIEW view2 = CONTAINING_RECORD(Links2, PH_FILE_POOL_VIEW, ByBaseLinks);
998 
999  return uintptrcmp((ULONG_PTR)view1->Base, (ULONG_PTR)view2->Base);
1000 }
1001 
1003  _Inout_ PPH_FILE_POOL Pool,
1004  _Inout_ PPH_FILE_POOL_VIEW View
1005  )
1006 {
1007  PhAddElementAvlTree(&Pool->ByBaseSet, &View->ByBaseLinks);
1008 }
1009 
1011  _Inout_ PPH_FILE_POOL Pool,
1012  _Inout_ PPH_FILE_POOL_VIEW View
1013  )
1014 {
1015  PhRemoveElementAvlTree(&Pool->ByBaseSet, &View->ByBaseLinks);
1016 }
1017 
1028  _Inout_ PPH_FILE_POOL Pool,
1029  _In_ PVOID Base
1030  )
1031 {
1032  PPH_FILE_POOL_VIEW view;
1033  PPH_AVL_LINKS links;
1034  PH_FILE_POOL_VIEW lookupView;
1035  LONG result;
1036 
1037  // This is an approximate search to find the target view in which the specified address
1038  // lies.
1039 
1040  lookupView.Base = Base;
1041 
1042  links = PhFindElementAvlTree2(&Pool->ByBaseSet, &lookupView.ByBaseLinks, &result);
1043 
1044  if (!links)
1045  return NULL;
1046 
1047  if (result == 0)
1048  {
1049  return CONTAINING_RECORD(links, PH_FILE_POOL_VIEW, ByBaseLinks);
1050  }
1051  else if (result < 0)
1052  {
1053  // The base of the returned element is larger than our base. The preceding
1054  // element must be the target view, or the target view doesn't exist.
1055 
1056  links = PhPredecessorElementAvlTree(links);
1057 
1058  if (!links)
1059  return NULL;
1060  }
1061  else
1062  {
1063  // The base of the returned element is smaller than our base. This element
1064  // must be the target view, or the target view doesn't exist.
1065  }
1066 
1067  view = CONTAINING_RECORD(links, PH_FILE_POOL_VIEW, ByBaseLinks);
1068 
1069  if ((ULONG_PTR)Base >= (ULONG_PTR)view->Base && (ULONG_PTR)Base < (ULONG_PTR)view->Base + Pool->SegmentSize)
1070  return view;
1071 
1072  return NULL;
1073 }
1074 
1076  _Inout_ PPH_FILE_POOL Pool,
1077  _In_ ULONG SegmentIndex
1078  )
1079 {
1080  PPH_FILE_POOL_VIEW view;
1081  PVOID base;
1082 
1083  // Map in the segment.
1084  if (!NT_SUCCESS(PhFppMapRange(Pool, SegmentIndex << Pool->SegmentShift, Pool->SegmentSize, &base)))
1085  return NULL;
1086 
1087  // Create and add the view entry.
1088 
1089  view = PhAllocateFromFreeList(&Pool->ViewFreeList);
1090  memset(view, 0, sizeof(PH_FILE_POOL_VIEW));
1091 
1092  view->RefCount = 1;
1093  view->SegmentIndex = SegmentIndex;
1094  view->Base = base;
1095 
1096  PhFppAddViewByIndex(Pool, view);
1097  PhFppAddViewByBase(Pool, view);
1098 
1099  return view;
1100 }
1101 
1103  _Inout_ PPH_FILE_POOL Pool,
1104  _Inout_ PPH_FILE_POOL_VIEW View
1105  )
1106 {
1107  PhFppUnmapRange(Pool, View->Base);
1108  PhFppRemoveViewByIndex(Pool, View);
1109  PhFppRemoveViewByBase(Pool, View);
1110 
1111  PhFreeToFreeList(&Pool->ViewFreeList, View);
1112 }
1113 
1115  _Inout_ PPH_FILE_POOL Pool,
1116  _Inout_ PPH_FILE_POOL_VIEW View
1117  )
1118 {
1119  RemoveEntryList(&View->InactiveViewsListEntry);
1120  Pool->NumberOfInactiveViews--;
1121 }
1122 
1124  _Inout_ PPH_FILE_POOL Pool,
1125  _Inout_ PPH_FILE_POOL_VIEW View
1126  )
1127 {
1128  InsertHeadList(&Pool->InactiveViewsListHead, &View->InactiveViewsListEntry);
1129  Pool->NumberOfInactiveViews++;
1130 
1131  // If we have too many inactive views, destroy the least recent ones.
1132  while (Pool->NumberOfInactiveViews > Pool->MaximumInactiveViews)
1133  {
1134  PLIST_ENTRY lruEntry;
1135  PPH_FILE_POOL_VIEW lruView;
1136 
1137  lruEntry = RemoveTailList(&Pool->InactiveViewsListHead);
1138  Pool->NumberOfInactiveViews--;
1139 
1140  assert(lruEntry != &Pool->InactiveViewsListHead);
1141  lruView = CONTAINING_RECORD(lruEntry, PH_FILE_POOL_VIEW, InactiveViewsListEntry);
1142  PhFppDestroyView(Pool, lruView);
1143  }
1144 }
1145 
1147  _Inout_ PPH_FILE_POOL Pool,
1148  _Inout_ PPH_FILE_POOL_VIEW View
1149  )
1150 {
1151  if (View->RefCount == 0)
1152  {
1153  // The view is inactive, so make it active.
1154  PhFppActivateView(Pool, View);
1155  }
1156 
1157  View->RefCount++;
1158 }
1159 
1161  _Inout_ PPH_FILE_POOL Pool,
1162  _Inout_ PPH_FILE_POOL_VIEW View
1163  )
1164 {
1165  if (--View->RefCount == 0)
1166  {
1167  if (View->SegmentIndex == 0)
1168  PhRaiseStatus(STATUS_INTERNAL_ERROR);
1169 
1170  PhFppDeactivateView(Pool, View);
1171  }
1172 }
1173 
1175  _Inout_ PPH_FILE_POOL Pool,
1176  _In_ ULONG SegmentIndex
1177  )
1178 {
1179  PPH_FILE_POOL_VIEW view;
1180 
1181  // Validate parameters.
1182  if (SegmentIndex != 0 && SegmentIndex >= Pool->Header->SegmentCount)
1183  return NULL;
1184 
1185  // Try to get a cached view.
1186 
1187  view = PhFppFindViewByIndex(Pool, SegmentIndex);
1188 
1189  if (view)
1190  {
1191  PhFppReferenceView(Pool, view);
1192 
1193  return (PPH_FP_BLOCK_HEADER)view->Base;
1194  }
1195 
1196  // No cached view, so create one.
1197 
1198  view = PhFppCreateView(Pool, SegmentIndex);
1199 
1200  if (!view)
1201  return NULL;
1202 
1203  return (PPH_FP_BLOCK_HEADER)view->Base;
1204 }
1205 
1207  _Inout_ PPH_FILE_POOL Pool,
1208  _In_ ULONG SegmentIndex
1209  )
1210 {
1211  PPH_FILE_POOL_VIEW view;
1212 
1213  view = PhFppFindViewByIndex(Pool, SegmentIndex);
1214 
1215  if (!view)
1216  PhRaiseStatus(STATUS_INTERNAL_ERROR);
1217 
1218  PhFppDereferenceView(Pool, view);
1219 }
1220 
1222  _Inout_ PPH_FILE_POOL Pool,
1223  _In_ PVOID Base
1224  )
1225 {
1226  PPH_FILE_POOL_VIEW view;
1227 
1228  view = PhFppFindViewByBase(Pool, Base);
1229 
1230  if (!view)
1231  PhRaiseStatus(STATUS_INTERNAL_ERROR);
1232 
1233  PhFppReferenceView(Pool, view);
1234 }
1235 
1237  _Inout_ PPH_FILE_POOL Pool,
1238  _In_ PVOID Base
1239  )
1240 {
1241  PPH_FILE_POOL_VIEW view;
1242 
1243  view = PhFppFindViewByBase(Pool, Base);
1244 
1245  if (!view)
1246  PhRaiseStatus(STATUS_INTERNAL_ERROR);
1247 
1248  PhFppDereferenceView(Pool, view);
1249 }
1250 
1263  _Inout_ PPH_FILE_POOL Pool,
1264  _In_ PPH_FP_BLOCK_HEADER FirstBlock,
1265  _Inout_ PPH_FP_SEGMENT_HEADER SegmentHeader,
1266  _In_ ULONG NumberOfBlocks
1267  )
1268 {
1269  RTL_BITMAP bitmap;
1270  ULONG hintIndex;
1271  ULONG foundIndex;
1272  PPH_FP_BLOCK_HEADER blockHeader;
1273 
1274  if (FirstBlock != Pool->FirstBlockOfFirstSegment)
1275  hintIndex = Pool->SegmentHeaderBlockSpan;
1276  else
1277  hintIndex = Pool->SegmentHeaderBlockSpan + Pool->FileHeaderBlockSpan;
1278 
1279  RtlInitializeBitMap(&bitmap, SegmentHeader->Bitmap, PH_FP_BLOCK_COUNT);
1280 
1281  // Find a range of free blocks and mark them as in-use.
1282  foundIndex = RtlFindClearBitsAndSet(&bitmap, NumberOfBlocks, hintIndex);
1283 
1284  if (foundIndex == -1)
1285  {
1286  // No more space.
1287  return NULL;
1288  }
1289 
1290  SegmentHeader->FreeBlocks -= NumberOfBlocks;
1291 
1292  blockHeader = (PPH_FP_BLOCK_HEADER)((PCHAR)FirstBlock + (foundIndex << Pool->BlockShift));
1293  blockHeader->Flags = 0;
1294  blockHeader->Span = NumberOfBlocks;
1295 
1296  return blockHeader;
1297 }
1298 
1308  _Inout_ PPH_FILE_POOL Pool,
1309  _In_ PPH_FP_BLOCK_HEADER FirstBlock,
1310  _Inout_ PPH_FP_SEGMENT_HEADER SegmentHeader,
1311  _In_ PPH_FP_BLOCK_HEADER BlockHeader
1312  )
1313 {
1314  RTL_BITMAP bitmap;
1315  ULONG startIndex;
1316  ULONG blockSpan;
1317 
1318  RtlInitializeBitMap(&bitmap, SegmentHeader->Bitmap, PH_FP_BLOCK_COUNT);
1319 
1320  // Mark the blocks as free.
1321  startIndex = (ULONG)((PCHAR)BlockHeader - (PCHAR)FirstBlock) >> Pool->BlockShift;
1322  blockSpan = BlockHeader->Span;
1323  RtlClearBits(&bitmap, startIndex, blockSpan);
1324  SegmentHeader->FreeBlocks += blockSpan;
1325 }
1326 
1334  _In_ PPH_FILE_POOL Pool,
1335  _In_ ULONG NumberOfBlocks
1336  )
1337 {
1338  // Use a binary tree to speed up comparison.
1339 
1340  if (NumberOfBlocks >= PH_FP_BLOCK_COUNT / 64)
1341  {
1342  if (NumberOfBlocks >= PH_FP_BLOCK_COUNT / 2)
1343  {
1344  if (NumberOfBlocks >= PH_FP_BLOCK_COUNT - Pool->SegmentHeaderBlockSpan)
1345  return 0;
1346  else
1347  return 1;
1348  }
1349  else
1350  {
1351  if (NumberOfBlocks >= PH_FP_BLOCK_COUNT / 16)
1352  return 2;
1353  else
1354  return 3;
1355  }
1356  }
1357  else
1358  {
1359  if (NumberOfBlocks >= 4)
1360  {
1361  if (NumberOfBlocks >= PH_FP_BLOCK_COUNT / 256)
1362  return 4;
1363  else
1364  return 5;
1365  }
1366  else
1367  {
1368  if (NumberOfBlocks >= 1)
1369  return 6;
1370  else
1371  return 7;
1372  }
1373  }
1374 }
1375 
1385  _Inout_ PPH_FILE_POOL Pool,
1386  _In_ ULONG FreeListIndex,
1387  _In_ ULONG SegmentIndex,
1388  _In_ PPH_FP_SEGMENT_HEADER SegmentHeader
1389  )
1390 {
1391  ULONG oldSegmentIndex;
1392  PPH_FP_BLOCK_HEADER oldSegmentFirstBlock;
1393  PPH_FP_SEGMENT_HEADER oldSegmentHeader;
1394 
1395  oldSegmentIndex = Pool->Header->FreeLists[FreeListIndex];
1396 
1397  // Try to reference the segment before we commit any changes.
1398 
1399  if (oldSegmentIndex != -1)
1400  {
1401  oldSegmentFirstBlock = PhFppReferenceSegment(Pool, oldSegmentIndex);
1402 
1403  if (!oldSegmentFirstBlock)
1404  return FALSE;
1405  }
1406 
1407  // Insert the segment into the list.
1408 
1409  SegmentHeader->FreeBlink = -1;
1410  SegmentHeader->FreeFlink = oldSegmentIndex;
1411  Pool->Header->FreeLists[FreeListIndex] = SegmentIndex;
1412 
1413  if (oldSegmentIndex != -1)
1414  {
1415  oldSegmentHeader = PhFppGetHeaderSegment(Pool, oldSegmentFirstBlock);
1416  oldSegmentHeader->FreeBlink = SegmentIndex;
1417  PhFppDereferenceSegment(Pool, oldSegmentIndex);
1418  }
1419 
1420  return TRUE;
1421 }
1422 
1432  _Inout_ PPH_FILE_POOL Pool,
1433  _In_ ULONG FreeListIndex,
1434  _In_ ULONG SegmentIndex,
1435  _In_ PPH_FP_SEGMENT_HEADER SegmentHeader
1436  )
1437 {
1438  ULONG flinkSegmentIndex;
1439  PPH_FP_BLOCK_HEADER flinkSegmentFirstBlock;
1440  PPH_FP_SEGMENT_HEADER flinkSegmentHeader;
1441  ULONG blinkSegmentIndex;
1442  PPH_FP_BLOCK_HEADER blinkSegmentFirstBlock;
1443  PPH_FP_SEGMENT_HEADER blinkSegmentHeader;
1444 
1445  flinkSegmentIndex = SegmentHeader->FreeFlink;
1446  blinkSegmentIndex = SegmentHeader->FreeBlink;
1447 
1448  // Try to reference the segments before we commit any changes.
1449 
1450  if (flinkSegmentIndex != -1)
1451  {
1452  flinkSegmentFirstBlock = PhFppReferenceSegment(Pool, flinkSegmentIndex);
1453 
1454  if (!flinkSegmentFirstBlock)
1455  return FALSE;
1456  }
1457 
1458  if (blinkSegmentIndex != -1)
1459  {
1460  blinkSegmentFirstBlock = PhFppReferenceSegment(Pool, blinkSegmentIndex);
1461 
1462  if (!blinkSegmentFirstBlock)
1463  {
1464  if (flinkSegmentIndex != -1)
1465  PhFppDereferenceSegment(Pool, flinkSegmentIndex);
1466 
1467  return FALSE;
1468  }
1469  }
1470 
1471  // Unlink the segment from the list.
1472 
1473  if (flinkSegmentIndex != -1)
1474  {
1475  flinkSegmentHeader = PhFppGetHeaderSegment(Pool, flinkSegmentFirstBlock);
1476  flinkSegmentHeader->FreeBlink = blinkSegmentIndex;
1477  PhFppDereferenceSegment(Pool, flinkSegmentIndex);
1478  }
1479 
1480  if (blinkSegmentIndex != -1)
1481  {
1482  blinkSegmentHeader = PhFppGetHeaderSegment(Pool, blinkSegmentFirstBlock);
1483  blinkSegmentHeader->FreeFlink = flinkSegmentIndex;
1484  PhFppDereferenceSegment(Pool, blinkSegmentIndex);
1485  }
1486  else
1487  {
1488  // The segment was the list head; select a new one.
1489  Pool->Header->FreeLists[FreeListIndex] = flinkSegmentIndex;
1490  }
1491 
1492  return TRUE;
1493 }
1494 
1502  _In_ PPH_FILE_POOL Pool,
1503  _In_ PVOID Block
1504  )
1505 {
1506  return CONTAINING_RECORD(Block, PH_FP_BLOCK_HEADER, Body);
1507 }
1508 
1518  _In_ PPH_FILE_POOL Pool,
1519  _In_ ULONG SegmentIndex,
1520  _In_ PPH_FP_BLOCK_HEADER FirstBlock,
1521  _In_ PVOID Address
1522  )
1523 {
1524  return (SegmentIndex << Pool->SegmentShift) + (ULONG)((PCHAR)Address - (PCHAR)FirstBlock);
1525 }
1526 
1538  _In_ PPH_FILE_POOL Pool,
1539  _In_ ULONG Rva,
1540  _Out_ PULONG SegmentIndex
1541  )
1542 {
1543  ULONG segmentIndex;
1544 
1545  segmentIndex = Rva >> Pool->SegmentShift;
1546 
1547  if (segmentIndex >= Pool->Header->SegmentCount)
1548  return -1;
1549 
1550  *SegmentIndex = segmentIndex;
1551 
1552  return Rva & (Pool->SegmentSize - 1);
1553 }