ReactOS  r74622
vadnode.c
Go to the documentation of this file.
1 /*
2  * PROJECT: ReactOS Kernel
3  * LICENSE: BSD - See COPYING.ARM in the top level directory
4  * FILE: ntoskrnl/mm/ARM3/vadnode.c
5  * PURPOSE: ARM Memory Manager VAD Node Algorithms
6  * PROGRAMMERS: ReactOS Portable Systems Group
7  * Timo Kreuzer (timo.kreuzer@reactos.org)
8  */
9 
10 /* INCLUDES *******************************************************************/
11 
12 #include <ntoskrnl.h>
13 #define NDEBUG
14 #include <debug.h>
15 
16 #define MODULE_INVOLVED_IN_ARM3
17 #include <mm/ARM3/miarm.h>
18 
19 /* Include Mm version of AVL support */
20 #include "miavl.h"
21 #include <sdk/lib/rtl/avlsupp.c>
22 
23 /* GLOBALS ********************************************************************/
24 
26 {
30 
34 
38 
42 };
43 
44 /* FUNCTIONS ******************************************************************/
45 
46 PMMVAD
47 NTAPI
49 {
50  PMMVAD FoundVad;
51  ULONG_PTR Vpn;
53  TABLE_SEARCH_RESULT SearchResult;
54 
55  /* Start with the the hint */
56  FoundVad = (PMMVAD)Table->NodeHint;
57  if (!FoundVad) return NULL;
58 
59  /* Check if this VPN is in the hint, if so, use it */
60  Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
61  if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
62 
63  /* VAD hint didn't work, go look for it */
64  SearchResult = RtlpFindAvlTableNodeOrParent(Table,
65  (PVOID)Vpn,
66  (PMMADDRESS_NODE*)&FoundVad);
67  if (SearchResult != TableFoundNode) return NULL;
68 
69  /* We found it, update the hint */
70  ASSERT(FoundVad != NULL);
71  ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
72  Table->NodeHint = FoundVad;
73  return FoundVad;
74 }
75 
77 NTAPI
79  IN ULONG_PTR EndVpn,
81  OUT PMMADDRESS_NODE *NodeOrParent)
82 {
83  PMMADDRESS_NODE ParentNode, CurrentNode;
84 
85  /* If the tree is empty, there is no conflict */
86  if (Table->NumberGenericTableElements == 0) return TableEmptyTree;
87 
88  /* Start looping from the root node */
89  CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
90  ASSERT(CurrentNode != NULL);
91  while (CurrentNode)
92  {
93  ParentNode = CurrentNode;
94 
95  /* This address comes after */
96  if (StartVpn > CurrentNode->EndingVpn)
97  {
98  /* Keep searching on the right */
99  CurrentNode = RtlRightChildAvl(CurrentNode);
100  }
101  else if (EndVpn < CurrentNode->StartingVpn)
102  {
103  /* This address ends before the node starts, search on the left */
104  CurrentNode = RtlLeftChildAvl(CurrentNode);
105  }
106  else
107  {
108  /* This address is part of this node, return it */
109  *NodeOrParent = ParentNode;
110  return TableFoundNode;
111  }
112  }
113 
114  /* There is no more child, save the current node as parent */
115  *NodeOrParent = ParentNode;
116  if (StartVpn > ParentNode->EndingVpn)
117  {
118  return TableInsertAsRight;
119  }
120  else
121  {
122  return TableInsertAsLeft;
123  }
124 }
125 
126 VOID
127 NTAPI
129  IN PMMADDRESS_NODE NewNode,
132 {
133  PMMVAD_LONG Vad;
134 
135  /* Insert it into the tree */
136  RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
137 
138  /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
139  Vad = (PMMVAD_LONG)NewNode;
140  if (Vad->u.VadFlags.Spare == 0)
141  {
144  SIZE_T Size;
145  PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
146  PVOID AllocatedBase = (PVOID)(Vad->StartingVpn << PAGE_SHIFT);
147 
148  Size = ((Vad->EndingVpn + 1) - Vad->StartingVpn) << PAGE_SHIFT;
149 
150  if (AllocatedBase == NULL)
151  {
152  AllocatedBase = (PVOID)(ULONG_PTR)1;
153  Size -= 1;
154  }
155 
156  Status = MmCreateMemoryArea(&Process->Vm,
158  &AllocatedBase,
159  Size,
161  &MemoryArea,
162  0,
163  PAGE_SIZE);
164  ASSERT(NT_SUCCESS(Status));
165 
166  /* Check if this is VM VAD */
167  if (Vad->ControlArea == NULL)
168  {
169  /* We store the reactos MEMORY_AREA here */
170  Vad->FirstPrototypePte = (PMMPTE)MemoryArea;
171  }
172  else
173  {
174  /* This is a section VAD. Store the MAREA here for now */
175  ASSERT(Vad->u4.Banked == (PVOID)0xDEADBABE);
176  Vad->u4.Banked = (PVOID)MemoryArea;
177  }
178  }
179 }
180 
181 VOID
182 NTAPI
184  IN PMM_AVL_TABLE VadRoot)
185 {
188 
189  /* Validate the VAD and set it as the current hint */
190  ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
191  VadRoot->NodeHint = Vad;
192 
193  /* Find the parent VAD and where this child should be inserted */
194  Result = RtlpFindAvlTableNodeOrParent(VadRoot, (PVOID)Vad->StartingVpn, &Parent);
195  ASSERT(Result != TableFoundNode);
196  ASSERT((Parent != NULL) || (Result == TableEmptyTree));
197 
198  /* Do the actual insert operation */
199  MiInsertNode(VadRoot, (PVOID)Vad, Parent, Result);
200 }
201 
202 NTSTATUS
203 NTAPI
205  _Inout_ PMMVAD Vad,
208  _In_ ULONG_PTR HighestAddress,
211 {
212  ULONG_PTR StartingAddress, EndingAddress;
214  PETHREAD CurrentThread;
217 
218  /* Align the view size to pages */
219  ViewSize = ALIGN_UP_BY(ViewSize, PAGE_SIZE);
220 
221  /* Get the current process */
222  CurrentProcess = PsGetCurrentProcess();
223 
224  /* Acquire the address creation lock and make sure the process is alive */
225  KeAcquireGuardedMutex(&CurrentProcess->AddressCreationLock);
226  if (CurrentProcess->VmDeleted)
227  {
228  KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
229  DPRINT1("The process is dying\n");
231  }
232 
233  /* Did the caller specify an address? */
234  if (*BaseAddress == 0)
235  {
236  /* Make sure HighestAddress is not too large */
237  HighestAddress = min(HighestAddress, (ULONG_PTR)MM_HIGHEST_VAD_ADDRESS);
238 
239  /* Which way should we search? */
240  if ((AllocationType & MEM_TOP_DOWN) || CurrentProcess->VmTopDown)
241  {
242  /* Find an address top-down */
243  Result = MiFindEmptyAddressRangeDownTree(ViewSize,
244  HighestAddress,
245  Alignment,
246  &CurrentProcess->VadRoot,
247  &StartingAddress,
248  &Parent);
249  }
250  else
251  {
252  /* Find an address bottom-up */
253  Result = MiFindEmptyAddressRangeInTree(ViewSize,
254  Alignment,
255  &CurrentProcess->VadRoot,
256  &Parent,
257  &StartingAddress);
258  }
259 
260  /* Get the ending address, which is the last piece we need for the VAD */
261  EndingAddress = StartingAddress + ViewSize - 1;
262 
263  /* Check if we found a suitable location */
264  if ((Result == TableFoundNode) || (EndingAddress > HighestAddress))
265  {
266  DPRINT1("Not enough free space to insert this VAD node!\n");
267  KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
268  return STATUS_NO_MEMORY;
269  }
270 
271  ASSERT(StartingAddress != 0);
272  ASSERT(StartingAddress < (ULONG_PTR)HighestAddress);
273  ASSERT(EndingAddress > StartingAddress);
274  }
275  else
276  {
277  /* Calculate the starting and ending address */
278  StartingAddress = ALIGN_DOWN_BY(*BaseAddress, Alignment);
279  EndingAddress = StartingAddress + ViewSize - 1;
280 
281  /* Make sure it doesn't conflict with an existing allocation */
282  Result = MiCheckForConflictingNode(StartingAddress >> PAGE_SHIFT,
283  EndingAddress >> PAGE_SHIFT,
284  &CurrentProcess->VadRoot,
285  &Parent);
286  if (Result == TableFoundNode)
287  {
288  DPRINT1("Given address conflicts with existing node\n");
289  KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
291  }
292  }
293 
294  /* Now set the VAD address */
295  Vad->StartingVpn = StartingAddress >> PAGE_SHIFT;
296  Vad->EndingVpn = EndingAddress >> PAGE_SHIFT;
297 
298  /* Check if we already need to charge for the pages */
299  if ((Vad->u.VadFlags.PrivateMemory && Vad->u.VadFlags.MemCommit) ||
300  (!Vad->u.VadFlags.PrivateMemory &&
301  (Vad->u.VadFlags.Protection & PAGE_WRITECOPY)))
302  {
303  /* Set the commit charge */
304  Vad->u.VadFlags.CommitCharge = ViewSize / PAGE_SIZE;
305  }
306 
307  /* Check if the VAD is to be secured */
308  if (Vad->u2.VadFlags2.OneSecured)
309  {
310  /* This *must* be a long VAD! */
311  ASSERT(Vad->u2.VadFlags2.LongVad);
312 
313  /* Yeah this is retarded, I didn't invent it! */
314  ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn = StartingAddress;
315  ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn = EndingAddress;
316  }
317 
318  /* Lock the working set */
319  CurrentThread = PsGetCurrentThread();
320  MiLockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
321 
322  /* Insert the VAD */
323  CurrentProcess->VadRoot.NodeHint = Vad;
324  MiInsertNode(&CurrentProcess->VadRoot, (PVOID)Vad, Parent, Result);
325 
326  /* Release the working set */
327  MiUnlockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
328 
329  /* Update the process' virtual size, and peak virtual size */
330  CurrentProcess->VirtualSize += ViewSize;
331  if (CurrentProcess->VirtualSize > CurrentProcess->PeakVirtualSize)
332  {
333  CurrentProcess->PeakVirtualSize = CurrentProcess->VirtualSize;
334  }
335 
336  /* Unlock the address space */
337  KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
338 
339  *BaseAddress = StartingAddress;
340  return STATUS_SUCCESS;
341 }
342 
343 VOID
344 NTAPI
346 {
349  ASSERT(Section->Address.EndingVpn >= Section->Address.StartingVpn);
350 
351  /* Find the parent VAD and where this child should be inserted */
352  Result = RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot, (PVOID)Section->Address.StartingVpn, &Parent);
353  ASSERT(Result != TableFoundNode);
354  ASSERT((Parent != NULL) || (Result == TableEmptyTree));
355  MiInsertNode(&MmSectionBasedRoot, &Section->Address, Parent, Result);
356 }
357 
358 VOID
359 NTAPI
362 {
363  PMMVAD_LONG Vad;
364 
365  /* Call the AVL code */
366  RtlpDeleteAvlTreeNode(Table, Node);
367 
368  /* Decrease element count */
369  Table->NumberGenericTableElements--;
370 
371  /* Check if this node was the hint */
372  if (Table->NodeHint == Node)
373  {
374  /* Get a new hint, unless we're empty now, in which case nothing */
375  if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
376  else Table->NodeHint = Table->BalancedRoot.RightChild;
377  }
378 
379  /* Free the node from ReactOS view as well */
380  Vad = (PMMVAD_LONG)Node;
381  if ((Table != &MmSectionBasedRoot) && (Vad->u.VadFlags.Spare == 0))
382  {
385 
386  /* Check if this is VM VAD */
387  if (Vad->ControlArea == NULL)
388  {
389  /* We store the ReactOS MEMORY_AREA here */
390  MemoryArea = (PMEMORY_AREA)Vad->FirstPrototypePte;
391  }
392  else
393  {
394  /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
395  MemoryArea = (PMEMORY_AREA)Vad->u4.Banked;
396  }
397 
398  /* Make sure one actually still exists */
399  if (MemoryArea)
400  {
401  /* Make sure we have not already freed it */
402  ASSERT(MemoryArea != (PVOID)0xDEADBAB1);
403 
404  /* Get the process */
405  Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
406 
407  /* We only create fake memory-areas for ARM3 VADs */
408  ASSERT(MemoryArea->Type == MEMORY_AREA_OWNED_BY_ARM3);
409  ASSERT(MemoryArea->Vad == NULL);
410 
411  /* Free it */
412  MmFreeMemoryArea(&Process->Vm, MemoryArea, NULL, NULL);
413 
414  /* Check if this is VM VAD */
415  if (Vad->ControlArea == NULL)
416  {
417  /* Delete the pointer to it */
418  Vad->FirstPrototypePte = (PVOID)0xDEADBAB1;
419  }
420  else
421  {
422  /* Delete the pointer to it */
423  Vad->u4.Banked = (PVOID)0xDEADBAB1;
424  }
425  }
426  }
427 }
428 
430 NTAPI
432 {
434 
435  /* Get the left child */
436  if (RtlLeftChildAvl(Node))
437  {
438  /* Get right-most child */
439  Node = RtlLeftChildAvl(Node);
440  while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
441  return Node;
442  }
443 
444  Parent = RtlParentAvl(Node);
445  ASSERT(Parent != NULL);
446  while (Parent != Node)
447  {
448  /* The parent should be a right child, return the real predecessor */
449  if (RtlIsRightChildAvl(Node))
450  {
451  /* Return it unless it's the root */
452  if (Parent == RtlParentAvl(Parent)) Parent = NULL;
453  return Parent;
454  }
455 
456  /* Keep lopping until we find our parent */
457  Node = Parent;
458  Parent = RtlParentAvl(Node);
459  }
460 
461  /* Nothing found */
462  return NULL;
463 }
464 
466 NTAPI
468 {
470 
471  /* Get the right child */
472  if (RtlRightChildAvl(Node))
473  {
474  /* Get left-most child */
475  Node = RtlRightChildAvl(Node);
476  while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
477  return Node;
478  }
479 
480  Parent = RtlParentAvl(Node);
481  ASSERT(Parent != NULL);
482  while (Parent != Node)
483  {
484  /* The parent should be a left child, return the real predecessor */
485  if (RtlIsLeftChildAvl(Node))
486  {
487  /* Return it */
488  return Parent;
489  }
490 
491  /* Keep lopping until we find our parent */
492  Node = Parent;
493  Parent = RtlParentAvl(Node);
494  }
495 
496  /* Nothing found */
497  return NULL;
498 }
499 
501 NTAPI
505  OUT PMMADDRESS_NODE *PreviousVad,
507 {
508  PMMADDRESS_NODE Node, PreviousNode;
509  ULONG_PTR PageCount, AlignmentVpn, LowVpn, HighestVpn;
510  ASSERT(Length != 0);
511 
512  /* Calculate page numbers for the length, alignment, and starting address */
513  PageCount = BYTES_TO_PAGES(Length);
514  AlignmentVpn = Alignment >> PAGE_SHIFT;
515  LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT, AlignmentVpn);
516 
517  /* Check for kernel mode table (memory areas) */
518  if (Table->Unused == 1)
519  {
520  LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn);
521  }
522 
523  /* Check if the table is empty */
524  if (Table->NumberGenericTableElements == 0)
525  {
526  /* Tree is empty, the candidate address is already the best one */
527  *Base = LowVpn << PAGE_SHIFT;
528  return TableEmptyTree;
529  }
530 
531  /* Otherwise, follow the leftmost child of the right root node's child */
532  Node = RtlRightChildAvl(&Table->BalancedRoot);
533  while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
534 
535  /* Start a search to find a gap */
536  PreviousNode = NULL;
537  while (Node != NULL)
538  {
539  /* Check if the gap below the current node is suitable */
540  if (Node->StartingVpn >= LowVpn + PageCount)
541  {
542  /* There is enough space to add our node */
543  *Base = LowVpn << PAGE_SHIFT;
544 
545  /* Can we use the current node as parent? */
546  if (RtlLeftChildAvl(Node) == NULL)
547  {
548  /* Node has no left child, so use it as parent */
549  *PreviousVad = Node;
550  return TableInsertAsLeft;
551  }
552  else
553  {
554  /* Node has a left child, this means that the previous node is
555  the right-most child of it's left child and can be used as
556  the parent. In case we use the space before the left-most
557  node, it's left child must be NULL. */
558  ASSERT(PreviousNode != NULL);
559  ASSERT(RtlRightChildAvl(PreviousNode) == NULL);
560  *PreviousVad = PreviousNode;
561  return TableInsertAsRight;
562  }
563  }
564 
565  /* The next candidate is above the current node */
566  if (Node->EndingVpn >= LowVpn)
567  LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
568 
569  /* Remember the current node and go to the next node */
570  PreviousNode = Node;
571  Node = MiGetNextNode(Node);
572  }
573 
574  /* We're up to the highest VAD, will this allocation fit above it? */
575  HighestVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) / PAGE_SIZE;
576 
577  /* Check for kernel mode table (memory areas) */
578  if (Table->Unused == 1)
579  {
580  HighestVpn = ALIGN_UP_BY((ULONG_PTR)(LONG_PTR)-1 >> PAGE_SHIFT, AlignmentVpn);
581  }
582 
583  if (HighestVpn >= LowVpn + PageCount)
584  {
585  /* Yes! Use this VAD to store the allocation */
586  *PreviousVad = PreviousNode;
587  *Base = LowVpn << PAGE_SHIFT;
588  return TableInsertAsRight;
589  }
590 
591  /* Nyet, there's no free address space for this allocation, so we'll fail */
592  return TableFoundNode;
593 }
594 
596 NTAPI
598  IN ULONG_PTR BoundaryAddress,
603 {
604  PMMADDRESS_NODE Node, OldNode, Child;
605  ULONG_PTR LowVpn, HighVpn, AlignmentVpn;
606  PFN_NUMBER PageCount;
607 
608  /* Sanity checks */
609  ASSERT(BoundaryAddress);
610  ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS));
611  ASSERT((Alignment & (PAGE_SIZE - 1)) == 0);
612 
613  /* Calculate page numbers for the length and alignment */
614  Length = ROUND_TO_PAGES(Length);
615  PageCount = Length >> PAGE_SHIFT;
616  AlignmentVpn = Alignment / PAGE_SIZE;
617 
618  /* Check for kernel mode table (memory areas) */
619  if (Table->Unused == 1)
620  {
621  LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn);
622  }
623  else
624  {
625  LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS, Alignment);
626  }
627 
628  /* Check if there is enough space below the boundary */
629  if ((LowVpn + Length) > (BoundaryAddress + 1))
630  {
631  return TableFoundNode;
632  }
633 
634  /* Check if the table is empty */
635  if (Table->NumberGenericTableElements == 0)
636  {
637  /* Tree is empty, the candidate address is already the best one */
638  *Base = ALIGN_DOWN_BY(BoundaryAddress + 1 - Length, Alignment);
639  return TableEmptyTree;
640  }
641 
642  /* Calculate the initial upper margin */
643  HighVpn = (BoundaryAddress + 1) >> PAGE_SHIFT;
644 
645  /* Starting from the root, follow the right children until we found a node
646  that ends above the boundary */
647  Node = RtlRightChildAvl(&Table->BalancedRoot);
648  while ((Node->EndingVpn < HighVpn) &&
649  ((Child = RtlRightChildAvl(Node)) != NULL)) Node = Child;
650 
651  /* Now loop the Vad nodes */
652  while (Node)
653  {
654  /* Calculate the lower margin */
655  LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
656 
657  /* Check if the current bounds are suitable */
658  if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
659  {
660  /* There is enough space to add our node */
661  LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, AlignmentVpn);
662  *Base = LowVpn << PAGE_SHIFT;
663 
664  /* Can we use the current node as parent? */
665  if (!RtlRightChildAvl(Node))
666  {
667  /* Node has no right child, so use it as parent */
668  *Parent = Node;
669  return TableInsertAsRight;
670  }
671  else
672  {
673  /* Node has a right child, the node we had before is the most
674  left grandchild of that right child, use it as parent. */
675  *Parent = OldNode;
676  return TableInsertAsLeft;
677  }
678  }
679 
680  /* Update the upper margin if necessary */
681  if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
682 
683  /* Remember the current node and go to the previous node */
684  OldNode = Node;
685  Node = MiGetPreviousNode(Node);
686  }
687 
688  /* Check if there's enough space before the lowest Vad */
689  LowVpn = ALIGN_UP_BY((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) / PAGE_SIZE;
690  if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
691  {
692  /* There is enough space to add our address */
693  LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, Alignment >> PAGE_SHIFT);
694  *Base = LowVpn << PAGE_SHIFT;
695  *Parent = OldNode;
696  return TableInsertAsLeft;
697  }
698 
699  /* No address space left at all */
700  *Base = 0;
701  *Parent = NULL;
702  return TableFoundNode;
703 }
704 
705 NTSTATUS
706 NTAPI
708  IN ULONG_PTR BoundaryAddress,
712 {
713  PMMADDRESS_NODE Node, LowestNode;
714  ULONG_PTR LowVpn, BestVpn;
715 
716  /* Sanity checks */
717  ASSERT(Table == &MmSectionBasedRoot);
718  ASSERT(BoundaryAddress);
719  ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
720 
721  /* Compute page length, make sure the boundary address is valid */
722  Length = ROUND_TO_PAGES(Length);
723  if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
724 
725  /* Check if the table is empty */
726  BestVpn = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment);
727  if (Table->NumberGenericTableElements == 0)
728  {
729  /* Tree is empty, the candidate address is already the best one */
730  *Base = BestVpn;
731  return STATUS_SUCCESS;
732  }
733 
734  /* Go to the right-most node which should be the biggest address */
735  Node = Table->BalancedRoot.RightChild;
736  while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
737 
738  /* Check if we can fit in here */
739  LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment);
740  if ((LowVpn < BoundaryAddress) && (Length <= (BoundaryAddress - LowVpn)))
741  {
742 #if (NTDDI_VERSION >= NTDDI_VISTA)
743  /* Return the address. */
744  *Base = BestVpn;
745 #else
746  /* Note: this is a compatibility hack that mimics a bug in the 2k3
747  kernel. It will can waste up to Alignment bytes of memory above
748  the allocation. This bug was fixed in Windows Vista */
749  *Base = ROUND_DOWN(BoundaryAddress - Length, Alignment);
750 #endif
751  return STATUS_SUCCESS;
752  }
753 
754  /* Now loop the Vad nodes */
755  do
756  {
757  /* Break out if we've reached the last node */
758  LowestNode = MiGetPreviousNode(Node);
759  if (!LowestNode) break;
760 
761  /* Check if this node could contain the requested address */
762  LowVpn = ROUND_UP(LowestNode->EndingVpn + 1, Alignment);
763  if ((LowestNode->EndingVpn < BestVpn) &&
764  (LowVpn < Node->StartingVpn) &&
765  (Length <= (Node->StartingVpn - LowVpn)))
766  {
767  /* Check if we need to take BoundaryAddress into account */
768  if (BoundaryAddress < Node->StartingVpn)
769  {
770  /* Return the optimal VPN address */
771  *Base = BestVpn;
772  return STATUS_SUCCESS;
773  }
774  else
775  {
776  /* The upper margin is given by the Node's starting address */
777  *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
778  return STATUS_SUCCESS;
779  }
780  }
781 
782  /* Move to the next node */
783  Node = LowestNode;
784  } while (TRUE);
785 
786  /* Check if there's enough space before the lowest Vad */
788  ((Node->StartingVpn - (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) >= Length))
789  {
790  /* Check if it fits in perfectly */
791  if (BoundaryAddress < Node->StartingVpn)
792  {
793  /* Return the optimal VPN address */
794  *Base = BestVpn;
795  return STATUS_SUCCESS;
796  }
797 
798  /* Return an aligned base address within this node */
799  *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
800  return STATUS_SUCCESS;
801  }
802 
803  /* No address space left at all */
804  return STATUS_NO_MEMORY;
805 }
806 
807 NTSTATUS
808 NTAPI
810  IN PVOID Base,
811  IN SIZE_T Size,
812  IN ULONG ProtectionMask)
813 {
814  ULONG_PTR StartAddress, EndAddress;
815 
816  /* Compute start and end address */
817  StartAddress = (ULONG_PTR)Base;
818  EndAddress = StartAddress + Size - 1;
819 
820  /* Are we deleting/unmapping, or changing? */
821  if (ProtectionMask < MM_DELETE_CHECK)
822  {
823  /* Changing... are we allowed to do so? */
824  if ((Vad->u.VadFlags.NoChange == 1) &&
825  (Vad->u2.VadFlags2.SecNoChange == 1) &&
826  (Vad->u.VadFlags.Protection != ProtectionMask))
827  {
828  /* Nope, bail out */
829  DPRINT1("Trying to mess with a no-change VAD!\n");
831  }
832  }
833  else
834  {
835  /* This is allowed */
836  ProtectionMask = 0;
837  }
838 
839  /* ARM3 doesn't support this yet */
840  ASSERT(Vad->u2.VadFlags2.MultipleSecured == 0);
841 
842  /* Is this a one-secured VAD, like a TEB or PEB? */
843  if (Vad->u2.VadFlags2.OneSecured)
844  {
845  /* Is this allocation being described by the VAD? */
846  if ((StartAddress <= ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn) &&
847  (EndAddress >= ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn))
848  {
849  /* Guard page? */
850  if (ProtectionMask & MM_DECOMMIT)
851  {
852  DPRINT1("Not allowed to change protection on guard page!\n");
854  }
855 
856  /* ARM3 doesn't have read-only VADs yet */
857  ASSERT(Vad->u2.VadFlags2.ReadOnly == 0);
858 
859  /* Check if read-write protections are allowed */
860  if (MmReadWrite[ProtectionMask] < MM_READ_WRITE_ALLOWED)
861  {
862  DPRINT1("Invalid protection mask for RW access!\n");
864  }
865  }
866  }
867 
868  /* All good, allow the change */
869  return STATUS_SUCCESS;
870 }
871 
872 /* EOF */
873 
DWORD *typedef PVOID
Definition: winlogon.h:52
ULONG_PTR EndingVpn
Definition: mmtypes.h:760
NTSTATUS NTAPI MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length, IN ULONG_PTR BoundaryAddress, IN ULONG_PTR Alignment, IN PMM_AVL_TABLE Table, OUT PULONG_PTR Base)
Definition: vadnode.c:707
#define MM_READ_ONLY_ALLOWED
Definition: miarm.h:231
#define STATUS_SUCCESS
Definition: contextmenu.cpp:55
FORCEINLINE VOID RtlpDeleteAvlTreeNode(IN PRTL_AVL_TABLE Table, IN PRTL_BALANCED_LINKS Node)
Definition: avlsupp.c:295
#define PAGE_SHIFT
Definition: env_spec_w32.h:45
#define IN
Definition: typedefs.h:39
MM_AVL_TABLE MmSectionBasedRoot
Definition: section.c:109
#define RtlIsRightChildAvl
Definition: miavl.h:48
ULONG ReadOnly
Definition: mmtypes.h:711
#define ROUND_UP(n, align)
Definition: eventvwr.h:31
ULONG Type
Definition: mm.h:214
struct _MEMORY_AREA * PMEMORY_AREA
PMMADDRESS_NODE NTAPI MiGetNextNode(IN PMMADDRESS_NODE Node)
Definition: vadnode.c:467
FORCEINLINE VOID MiUnlockProcessWorkingSetUnsafe(IN PEPROCESS Process, IN PETHREAD Thread)
Definition: miarm.h:1177
#define PsGetCurrentThread()
Definition: env_spec_w32.h:81
VOID FASTCALL KeAcquireGuardedMutex(IN PKGUARDED_MUTEX GuardedMutex)
Definition: gmutex.c:42
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel)?(CompletionRoutine!=NULL):TRUE)
#define MI_LOWEST_VAD_ADDRESS
Definition: miarm.h:9
SIZE_T PeakVirtualSize
Definition: pstypes.h:1204
#define MM_DECOMMIT
Definition: miarm.h:66
char CHAR
Definition: xmlstorage.h:175
MMVAD_FLAGS VadFlags
Definition: mmtypes.h:764
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT
_In_opt_ ULONG Base
Definition: rtlfuncs.h:2327
#define TRUE
Definition: numbers.c:17
#define RtlRightChildAvl
Definition: miavl.h:45
VOID NTAPI MiInsertBasedSection(IN PSECTION Section)
Definition: vadnode.c:345
union _MMVAD_LONG::@2134 u4
PCONTROL_AREA ControlArea
Definition: mmtypes.h:766
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical UINT32 ACPI_TABLE_HEADER *OutTableHeader ACPI_TABLE_HEADER **OutTable ACPI_HANDLE UINT32 ACPI_WALK_CALLBACK ACPI_WALK_CALLBACK void void **ReturnValue UINT32 ACPI_BUFFER *RetPathPtr ACPI_OBJECT_HANDLER void *Data ACPI_OBJECT_HANDLER void **Data ACPI_STRING ACPI_OBJECT_LIST ACPI_BUFFER *ReturnObjectBuffer ACPI_DEVICE_INFO **ReturnBuffer ACPI_HANDLE Parent
Definition: acpixf.h:717
_At_(*)(_In_ PWSK_CLIENT Client, _In_opt_ PUNICODE_STRING NodeName, _In_opt_ PUNICODE_STRING ServiceName, _In_opt_ ULONG NameSpace, _In_opt_ GUID *Provider, _In_opt_ PADDRINFOEXW Hints, _Outptr_ PADDRINFOEXW *Result, _In_opt_ PEPROCESS OwningProcess, _In_opt_ PETHREAD OwningThread, _Inout_ PIRP Irp Result)(Mem)) NTSTATUS(WSKAPI *PFN_WSK_GET_ADDRESS_INFO
Definition: wsk.h:426
union _MMVAD_LONG::@2131 u
FORCEINLINE VOID RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table, IN PRTL_BALANCED_LINKS NewNode, IN OUT PVOID NodeOrParent, IN OUT TABLE_SEARCH_RESULT SearchResult)
Definition: avlsupp.c:208
#define MM_NO_ACCESS_ALLOWED
Definition: miarm.h:232
#define MM_DELETE_CHECK
Definition: miarm.h:233
uint32_t ULONG_PTR
Definition: typedefs.h:64
TABLE_SEARCH_RESULT NTAPI MiFindEmptyAddressRangeDownTree(IN SIZE_T Length, IN ULONG_PTR BoundaryAddress, IN ULONG_PTR Alignment, IN PMM_AVL_TABLE Table, OUT PULONG_PTR Base, OUT PMMADDRESS_NODE *Parent)
Definition: vadnode.c:597
ULONG_PTR EndingVpn
Definition: mmtypes.h:731
TABLE_SEARCH_RESULT NTAPI MiCheckForConflictingNode(IN ULONG_PTR StartVpn, IN ULONG_PTR EndVpn, IN PMM_AVL_TABLE Table, OUT PMMADDRESS_NODE *NodeOrParent)
Definition: vadnode.c:78
ULONG PFN_NUMBER
Definition: ke.h:8
#define MEMORY_AREA_OWNED_BY_ARM3
Definition: mm.h:71
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
#define PsGetCurrentProcess
Definition: psfuncs.h:17
TABLE_SEARCH_RESULT NTAPI MiFindEmptyAddressRangeInTree(IN SIZE_T Length, IN ULONG_PTR Alignment, IN PMM_AVL_TABLE Table, OUT PMMADDRESS_NODE *PreviousVad, OUT PULONG_PTR Base)
Definition: vadnode.c:502
#define MM_READ_WRITE_ALLOWED
Definition: miarm.h:230
smooth NULL
Definition: ftsmooth.c:464
NTSTATUS NTAPI MiCheckSecuredVad(IN PMMVAD Vad, IN PVOID Base, IN SIZE_T Size, IN ULONG ProtectionMask)
Definition: vadnode.c:809
PVOID Banked
Definition: mmtypes.h:781
ULONG_PTR StartingVpn
Definition: mmtypes.h:730
ULONG_PTR StartingVpn
Definition: mmtypes.h:654
PVOID NodeHint
Definition: mmtypes.h:671
UINTN Size
Definition: acefiex.h:550
EX_PUSH_LOCK AddressCreationLock
Definition: pstypes.h:1222
ULONG_PTR EndingVpn
Definition: mmtypes.h:655
FORCEINLINE VOID MiLockProcessWorkingSetUnsafe(IN PEPROCESS Process, IN PETHREAD Thread)
Definition: miarm.h:1107
_In_ HANDLE _Outptr_result_bytebuffer_ ViewSize PVOID * BaseAddress
Definition: mmfuncs.h:404
ULONG VmDeleted
Definition: pstypes.h:1330
ULONG CurrentProcess
Definition: shell.c:125
ULONG VmTopDown
Definition: pstypes.h:1349
if(!(yy_init))
Definition: macro.lex.yy.c:704
struct _MMVAD_LONG * PMMVAD_LONG
NTSTATUS NTAPI MiInsertVadEx(_Inout_ PMMVAD Vad, _In_ ULONG_PTR *BaseAddress, _In_ SIZE_T ViewSize, _In_ ULONG_PTR HighestAddress, _In_ ULONG_PTR Alignment, _In_ ULONG AllocationType)
Definition: vadnode.c:204
struct _MMPTE * PMMPTE
ULONG_PTR StartingVpn
Definition: mmtypes.h:759
#define STATUS_PROCESS_IS_TERMINATING
Definition: ntstatus.h:488
#define MM_LOWEST_USER_ADDRESS
Definition: armddk.h:20
NTSTATUS NTAPI MmFreeMemoryArea(PMMSUPPORT AddressSpace, PMEMORY_AREA MemoryArea, PMM_FREE_PAGE_FUNC FreePage, PVOID FreePageContext)
Definition: marea.c:280
MMVAD_FLAGS2 VadFlags2
Definition: mmtypes.h:772
#define _Inout_
Definition: no_sal2.h:244
union _MMVAD_LONG::@2132 u2
NTSTATUS NTAPI MmCreateMemoryArea(PMMSUPPORT AddressSpace, ULONG Type, PVOID *BaseAddress, SIZE_T Length, ULONG Protection, PMEMORY_AREA *Result, ULONG AllocationFlags, ULONG AllocationGranularity)
Definition: marea.c:412
struct _MMADDRESS_NODE * RightChild
Definition: mmtypes.h:653
#define BYTES_TO_PAGES(Size)
VOID NTAPI MiInsertVad(IN PMMVAD Vad, IN PMM_AVL_TABLE VadRoot)
Definition: vadnode.c:183
VOID UINTN Length
Definition: acefiex.h:718
#define PAGE_SIZE
Definition: env_spec_w32.h:49
_In_ ULONG _In_ BOOLEAN _Must_inspect_result_ PVOID * VirtualAddress
Definition: ndis.h:3772
#define STATUS_INVALID_PAGE_PROTECTION
Definition: ntstatus.h:291
_In_ HANDLE _Outptr_result_bytebuffer_ ViewSize PVOID _In_ ULONG_PTR _In_ SIZE_T _Inout_opt_ PLARGE_INTEGER _Inout_ PSIZE_T _In_ SECTION_INHERIT _In_ ULONG AllocationType
Definition: mmfuncs.h:404
#define RtlIsLeftChildAvl
Definition: miavl.h:47
MMSUPPORT Vm
Definition: pstypes.h:1288
Status
Definition: gdiplustypes.h:24
FORCEINLINE TABLE_SEARCH_RESULT RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PRTL_BALANCED_LINKS *NodeOrParent)
Definition: avlsupp.c:32
#define ALIGN_DOWN_BY(size, align)
#define _In_
Definition: no_sal2.h:204
#define ROUND_DOWN(n, align)
Definition: eventvwr.h:30
ULONG_PTR SIZE_T
Definition: typedefs.h:79
#define NT_SUCCESS(StatCode)
Definition: cmd.c:149
LONG NTSTATUS
Definition: DriverTester.h:11
#define RtlLeftChildAvl
Definition: miavl.h:46
#define ROUND_TO_PAGES(Size)
#define STATUS_NO_MEMORY
Definition: ntstatus.h:246
VOID NTAPI MiInsertNode(IN PMM_AVL_TABLE Table, IN PMMADDRESS_NODE NewNode, IN PMMADDRESS_NODE Parent, IN TABLE_SEARCH_RESULT Result)
Definition: vadnode.c:128
__int3264 LONG_PTR
Definition: mstsclib_h.h:276
#define min(a, b)
Definition: monoChain.cc:55
#define PAGE_WRITECOPY
Definition: nt_native.h:1305
VOID FASTCALL KeReleaseGuardedMutex(IN OUT PKGUARDED_MUTEX GuardedMutex)
Definition: gmutex.c:53
#define DPRINT1
Definition: precomp.h:8
CHAR MmReadWrite[32]
Definition: vadnode.c:25
#define MM_HIGHEST_VAD_ADDRESS
Definition: mm.h:36
_Must_inspect_result_ _In_ PLARGE_INTEGER _In_ PLARGE_INTEGER _In_ ULONG _In_ PFILE_OBJECT _In_ PVOID Process
Definition: fsrtlfuncs.h:219
#define OUT
Definition: typedefs.h:40
ULONG_PTR Spare
Definition: mmtypes.h:698
_In_ HANDLE _Outptr_result_bytebuffer_ ViewSize PVOID _In_ ULONG_PTR _In_ SIZE_T _Inout_opt_ PLARGE_INTEGER _Inout_ PSIZE_T ViewSize
Definition: mmfuncs.h:404
PMMADDRESS_NODE NTAPI MiGetPreviousNode(IN PMMADDRESS_NODE Node)
Definition: vadnode.c:431
unsigned int ULONG
Definition: retypes.h:1
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
PMMPTE FirstPrototypePte
Definition: mmtypes.h:767
#define ULONG_PTR
Definition: config.h:101
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical UINT32 ACPI_TABLE_HEADER *OutTableHeader ACPI_TABLE_HEADER **OutTable ACPI_HANDLE UINT32 ACPI_WALK_CALLBACK ACPI_WALK_CALLBACK void void **ReturnValue UINT32 ACPI_BUFFER *RetPathPtr ACPI_OBJECT_HANDLER void *Data ACPI_OBJECT_HANDLER void **Data ACPI_STRING ACPI_OBJECT_LIST ACPI_BUFFER *ReturnObjectBuffer ACPI_DEVICE_INFO **ReturnBuffer ACPI_HANDLE ACPI_HANDLE Child
Definition: acpixf.h:717
uint32_t * PULONG_PTR
Definition: typedefs.h:64
#define ALIGN_UP_BY(size, align)
VOID NTAPI MiRemoveNode(IN PMMADDRESS_NODE Node, IN PMM_AVL_TABLE Table)
Definition: vadnode.c:360
static BYTE u3[]
Definition: msg.c:580
#define MEM_TOP_DOWN
Definition: nt_native.h:1321
SIZE_T VirtualSize
Definition: pstypes.h:1205
#define STATUS_CONFLICTING_ADDRESSES
Definition: ntstatus.h:247
MM_AVL_TABLE VadRoot
Definition: pstypes.h:1385
#define RtlParentAvl
Definition: miavl.h:44
struct _MEMORY_AREA * MemoryArea
Definition: newmm.h:65
PVOID Vad
Definition: mm.h:219
struct _MMVAD * PMMVAD
#define MmSystemRangeStart
Definition: mm.h:25
union gl_dlist_node Node
Definition: dlist.c:302
PMMVAD NTAPI MiLocateAddress(IN PVOID VirtualAddress)
Definition: vadnode.c:48
#define PAGE_READWRITE
Definition: nt_native.h:1304