test: addrsup.c File Reference

01076 : 01077 01078 The function determines if any addresses between a given starting and 01079 ending address is contained within a virtual address descriptor. 01080 01081 Arguments: 01082 01083 StartVpn - Supplies the virtual address to locate a containing 01084 descriptor. 01085 01086 EndVpn - Supplies the virtual address to locate a containing 01087 descriptor. 01088 01089 Return Value: 01090 01091 Returns a pointer to the first conflicting virtual address descriptor 01092 if one is found, otherwise a NULL value is returned. 01093 01094 --*/ 01095 01096 { 01097 PMMADDRESS_NODE Node; 01098 01099 Node = Root; 01100 01101 for (;;) { 01102 01103 if (Node == (PMMADDRESS_NODE)NULL) { 01104 return (PMMADDRESS_NODE)NULL; 01105 } 01106 01107 if (StartVpn > Node->EndingVpn) { 01108 Node = Node->RightChild; 01109 01110 } else if (EndVpn < Node->StartingVpn) { 01111 Node = Node->LeftChild; 01112 01113 } else { 01114 01115 // 01116 // The starting address is less than or equal to the end VA 01117 // and the ending address is greater than or equal to the 01118 // start va. Return this node. 01119 // 01120 01121 return Node; 01122 } 01123 } 01124 }

01261 : 01262 01263 The function examines the virtual address descriptors to locate 01264 an unused range of the specified size and returns the starting 01265 address of the range. The function examines from the high 01266 addresses down and ensures that starting address is less than 01267 the specified address. 01268 01269 Arguments: 01270 01271 SizeOfRange - Supplies the size in bytes of the range to locate. 01272 01273 HighestAddressToEndAt - Supplies the virtual address that limits 01274 the value of the ending address. The ending 01275 address of the located range must be less 01276 than this address. 01277 01278 Alignment - Supplies the alignment for the address. Must be 01279 a power of 2 and greater than the page_size. 01280 01281 Root - Supplies the root of the tree to search through. 01282 01283 Return Value: 01284 01285 Returns the starting address of a suitable range. 01286 01287 --*/ 01288 01289 { 01290 PMMADDRESS_NODE Node; 01291 PMMADDRESS_NODE PreviousNode; 01292 ULONG_PTR AlignedEndingVa; 01293 PVOID OptimalStart; 01294 ULONG_PTR OptimalStartVpn; 01295 ULONG_PTR HighestVpn; 01296 ULONG_PTR AlignmentVpn; 01297 01298 SizeOfRange = MI_ROUND_TO_SIZE (SizeOfRange, PAGE_SIZE); 01299 01300 ASSERT (HighestAddressToEndAt != NULL); 01301 ASSERT (HighestAddressToEndAt <= (PVOID)((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1)); 01302 01303 HighestVpn = MI_VA_TO_VPN (HighestAddressToEndAt); 01304 01305 // 01306 // Locate the Node with the highest starting address. 01307 // 01308 01309 OptimalStart = (PVOID)(MI_ALIGN_TO_SIZE( 01310 (((ULONG_PTR)HighestAddressToEndAt + 1) - SizeOfRange), 01311 Alignment)); 01312 Node = Root; 01313 01314 if (Node == (PMMADDRESS_NODE)NULL) { 01315 01316 // 01317 // The tree is empty, any range is okay. 01318 // 01319 01320 return (PMMADDRESS_NODE)(OptimalStart); 01321 } 01322 01323 // 01324 // See if an empty slot exists to hold this range, locate the largest 01325 // element in the tree. 01326 // 01327 01328 while (Node->RightChild != (PMMADDRESS_NODE)NULL) { 01329 Node = Node->RightChild; 01330 } 01331 01332 // 01333 // Check to see if a range exists between the highest address VAD 01334 // and the highest address to end at. 01335 // 01336 01337 AlignedEndingVa = (ULONG_PTR)MI_ROUND_TO_SIZE ((ULONG_PTR)MI_VPN_TO_VA_ENDING (Node->EndingVpn), 01338 Alignment); 01339 01340 if (AlignedEndingVa < (ULONG_PTR)HighestAddressToEndAt) { 01341 01342 if ( SizeOfRange < ((ULONG_PTR)HighestAddressToEndAt - AlignedEndingVa)) { 01343 01344 return (PMMADDRESS_NODE)(MI_ALIGN_TO_SIZE( 01345 ((ULONG_PTR)HighestAddressToEndAt - SizeOfRange), 01346 Alignment)); 01347 } 01348 } 01349 01350 // 01351 // Walk the tree backwards looking for a fit. 01352 // 01353 01354 OptimalStartVpn = MI_VA_TO_VPN (OptimalStart); 01355 AlignmentVpn = MI_VA_TO_VPN (Alignment); 01356 01357 for (;;) { 01358 01359 PreviousNode = MiGetPreviousNode (Node); 01360 01361 if (PreviousNode != (PMMADDRESS_NODE)NULL) { 01362 01363 // 01364 // Is the ending Va below the top of the address to end at. 01365 // 01366 01367 if (PreviousNode->EndingVpn < OptimalStartVpn) { 01368 if ((SizeOfRange >> PAGE_SHIFT) <= 01369 ((ULONG_PTR)Node->StartingVpn - 01370 (ULONG_PTR)MI_ROUND_TO_SIZE(1 + PreviousNode->EndingVpn, 01371 AlignmentVpn))) { 01372 01373 // 01374 // See if the optimal start will fit between these 01375 // two VADs. 01376 // 01377 01378 if ((OptimalStartVpn > PreviousNode->EndingVpn) && 01379 (HighestVpn < Node->StartingVpn)) { 01380 return (PMMADDRESS_NODE)(OptimalStart); 01381 } 01382 01383 // 01384 // Check to ensure that the ending address aligned upwards 01385 // is not greater than the starting address. 01386 // 01387 01388 if ((ULONG_PTR)Node->StartingVpn > 01389 (ULONG_PTR)MI_ROUND_TO_SIZE(1 + PreviousNode->EndingVpn, 01390 AlignmentVpn)) { 01391 01392 return (PMMADDRESS_NODE)MI_ALIGN_TO_SIZE( 01393 (ULONG_PTR)MI_VPN_TO_VA (Node->StartingVpn) - SizeOfRange, 01394 Alignment); 01395 } 01396 } 01397 } 01398 } else { 01399 01400 // 01401 // No more descriptors, check to see if this fits into the remainder 01402 // of the address space. 01403 // 01404 01405 if (Node->StartingVpn > MI_VA_TO_VPN (MM_LOWEST_USER_ADDRESS)) { 01406 if ((SizeOfRange >> PAGE_SHIFT) <= 01407 ((ULONG_PTR)Node->StartingVpn - MI_VA_TO_VPN (MM_LOWEST_USER_ADDRESS))) { 01408 01409 // 01410 // See if the optimal start will fit between these 01411 // two VADs. 01412 // 01413 01414 if (HighestVpn < Node->StartingVpn) { 01415 return (PMMADDRESS_NODE)(OptimalStart); 01416 } 01417 01418 return (PMMADDRESS_NODE)MI_ALIGN_TO_SIZE( 01419 (ULONG_PTR)MI_VPN_TO_VA (Node->StartingVpn) - SizeOfRange, 01420 Alignment); 01421 } 01422 } else { 01423 ExRaiseStatus (STATUS_NO_MEMORY); 01424 } 01425 } 01426 Node = PreviousNode; 01427 } 01428 } #if DBG

01136 : 01137 01138 The function examines the virtual address descriptors to locate 01139 an unused range of the specified size and returns the starting 01140 address of the range. 01141 01142 Arguments: 01143 01144 SizeOfRange - Supplies the size in bytes of the range to locate. 01145 01146 Alignment - Supplies the alignment for the address. Must be 01147 a power of 2 and greater than the page_size. 01148 01149 Root - Supplies the root of the tree to search through. 01150 01151 PreviousVad - Supplies the Vad which is before this the found 01152 address range. 01153 01154 Return Value: 01155 01156 Returns the starting address of a suitable range. 01157 01158 --*/ 01159 01160 { 01161 PMMADDRESS_NODE Node; 01162 PMMADDRESS_NODE NextNode; 01163 ULONG_PTR AlignmentVpn; 01164 01165 AlignmentVpn = Alignment >> PAGE_SHIFT; 01166 01167 // 01168 // Locate the Node with the lowest starting address. 01169 // 01170 01171 SizeOfRange = (SizeOfRange + (PAGE_SIZE - 1)) >> PAGE_SHIFT; 01172 ASSERT (SizeOfRange != 0); 01173 01174 Node = Root; 01175 01176 if (Node == (PMMADDRESS_NODE)NULL) { 01177 return MM_LOWEST_USER_ADDRESS; 01178 } 01179 while (Node->LeftChild != (PMMADDRESS_NODE)NULL) { 01180 Node = Node->LeftChild; 01181 } 01182 01183 // 01184 // Check to see if a range exists between the lowest address VAD 01185 // and lowest user address. 01186 // 01187 01188 if (Node->StartingVpn > MI_VA_TO_VPN (MM_LOWEST_USER_ADDRESS)) { 01189 if ( SizeOfRange < 01190 (Node->StartingVpn - MI_VA_TO_VPN (MM_LOWEST_USER_ADDRESS))) { 01191 01192 *PreviousVad = NULL; 01193 return MM_LOWEST_USER_ADDRESS; 01194 } 01195 } 01196 01197 for (;;) { 01198 01199 NextNode = MiGetNextNode (Node); 01200 01201 if (NextNode != (PMMADDRESS_NODE)NULL) { 01202 01203 if (SizeOfRange <= 01204 ((ULONG_PTR)NextNode->StartingVpn - 01205 MI_ROUND_TO_SIZE(1 + Node->EndingVpn, 01206 AlignmentVpn))) { 01207 01208 // 01209 // Check to ensure that the ending address aligned upwards 01210 // is not greater than the starting address. 01211 // 01212 01213 if ((ULONG_PTR)NextNode->StartingVpn > 01214 MI_ROUND_TO_SIZE(1 + Node->EndingVpn, 01215 AlignmentVpn)) { 01216 01217 *PreviousVad = Node; 01218 return (PMMADDRESS_NODE)MI_ROUND_TO_SIZE( 01219 (ULONG_PTR)MI_VPN_TO_VA_ENDING(Node->EndingVpn), 01220 Alignment); 01221 } 01222 } 01223 01224 } else { 01225 01226 // 01227 // No more descriptors, check to see if this fits into the remainder 01228 // of the address space. 01229 // 01230 01231 if ((((ULONG_PTR)Node->EndingVpn + MI_VA_TO_VPN(X64K)) < 01232 MI_VA_TO_VPN (MM_HIGHEST_VAD_ADDRESS)) 01233 && 01234 (SizeOfRange <= 01235 ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS - 01236 (ULONG_PTR)MI_ROUND_TO_SIZE( 01237 (ULONG_PTR)MI_VPN_TO_VA(Node->EndingVpn), Alignment)))) { 01238 01239 *PreviousVad = Node; 01240 return (PMMADDRESS_NODE)MI_ROUND_TO_SIZE( 01241 (ULONG_PTR)MI_VPN_TO_VA_ENDING(Node->EndingVpn), 01242 Alignment); 01243 } else { 01244 ExRaiseStatus (STATUS_NO_MEMORY); 01245 } 01246 } 01247 Node = NextNode; 01248 } 01249 }

00430 : 00431 00432 This function locates the virtual address descriptor which contains 00433 the address range which logically is first within the address space. 00434 00435 Arguments: 00436 00437 None. 00438 00439 Return Value: 00440 00441 Returns a pointer to the virtual address descriptor containing the 00442 first address range, NULL if none. 00443 00444 --*/ 00445 00446 { 00447 PMMADDRESS_NODE First; 00448 00449 First = Root; 00450 00451 if (First == (PMMADDRESS_NODE)NULL) { 00452 return (PMMADDRESS_NODE)NULL; 00453 } 00454 00455 while (First->LeftChild != (PMMADDRESS_NODE)NULL) { 00456 First = First->LeftChild; 00457 } 00458 00459 return First; 00460 }

00303 : 00304 00305 This function locates the virtual address descriptor which contains 00306 the address range which logically follows the specified address range. 00307 00308 Arguments: 00309 00310 Node - Supplies a pointer to a virtual address descriptor. 00311 00312 Return Value: 00313 00314 Returns a pointer to the virtual address descriptor containing the 00315 next address range, NULL if none. 00316 00317 --*/ 00318 00319 { 00320 PMMADDRESS_NODE Next; 00321 PMMADDRESS_NODE Parent; 00322 PMMADDRESS_NODE Left; 00323 00324 Next = Node; 00325 00326 if (Next->RightChild == (PMMADDRESS_NODE)NULL) { 00327 00328 while ((Parent = Next->Parent) != (PMMADDRESS_NODE)NULL) { 00329 00330 // 00331 // Locate the first ancestor of this node of which this 00332 // node is the left child of and return that node as the 00333 // next element. 00334 // 00335 00336 if (Parent->LeftChild == Next) { 00337 return Parent; 00338 } 00339 00340 Next = Parent; 00341 00342 } 00343 00344 return (PMMADDRESS_NODE)NULL; 00345 } 00346 00347 // 00348 // A right child exists, locate the left most child of that right child. 00349 // 00350 00351 Next = Next->RightChild; 00352 00353 while ((Left = Next->LeftChild) != (PMMADDRESS_NODE)NULL) { 00354 Next = Left; 00355 } 00356 return Next; 00357 00358 }

00368 : 00369 00370 This function locates the virtual address descriptor which contains 00371 the address range which logically precedes the specified virtual 00372 address descriptor. 00373 00374 Arguments: 00375 00376 Node - Supplies a pointer to a virtual address descriptor. 00377 00378 Return Value: 00379 00380 Returns a pointer to the virtual address descriptor containing the 00381 next address range, NULL if none. 00382 00383 --*/ 00384 00385 { 00386 PMMADDRESS_NODE Previous; 00387 00388 Previous = Node; 00389 00390 if (Previous->LeftChild == (PMMADDRESS_NODE)NULL) { 00391 00392 00393 while (Previous->Parent != (PMMADDRESS_NODE)NULL) { 00394 00395 // 00396 // Locate the first ancestor of this node of which this 00397 // node is the right child of and return that node as the 00398 // Previous element. 00399 // 00400 00401 if (Previous->Parent->RightChild == Previous) { 00402 return Previous->Parent; 00403 } 00404 00405 Previous = Previous->Parent; 00406 00407 } 00408 return (PMMADDRESS_NODE)NULL; 00409 } 00410 00411 // 00412 // A left child exists, locate the right most child of that left child. 00413 // 00414 00415 Previous = Previous->LeftChild; 00416 while (Previous->RightChild != (PMMADDRESS_NODE)NULL) { 00417 Previous = Previous->RightChild; 00418 } 00419 return Previous; 00420 }

00471 : 00472 00473 This function inserts a virtual address descriptor into the tree and 00474 reorders the splay tree as appropriate. 00475 00476 Arguments: 00477 00478 Node - Supplies a pointer to a virtual address descriptor 00479 00480 00481 Return Value: 00482 00483 None. 00484 00485 --*/ 00486 00487 { 00488 ULONG Level = 0; 00489 PMMADDRESS_NODE Parent; 00490 00491 // 00492 // Initialize virtual address descriptor child links. 00493 // 00494 00495 Node->LeftChild = (PMMADDRESS_NODE)NULL; 00496 Node->RightChild = (PMMADDRESS_NODE)NULL; 00497 00498 // 00499 // If the tree is empty, then establish this virtual address descriptor 00500 // as the root of the tree. 00501 // Otherwise descend the tree to find the correct place to 00502 // insert the descriptor. 00503 // 00504 00505 Parent = *Root; 00506 if (!Parent) { 00507 *Root = Node; 00508 Node->Parent = (PMMADDRESS_NODE)NULL; 00509 } else { 00510 00511 for (;;) { 00512 00513 Level += 1; 00514 if (Level == 15) { 00515 MiReorderTree(Parent, Root); 00516 } 00517 00518 // 00519 // If the starting address for this virtual address descriptor 00520 // is less than the parent starting address, then 00521 // follow the left child link. Else follow the right child link. 00522 // 00523 00524 if (Node->StartingVpn < Parent->StartingVpn) { 00525 00526 // 00527 // Starting address of the virtual address descriptor is less 00528 // than the parent starting virtual address. 00529 // Follow left child link if not null. Otherwise 00530 // insert the descriptor as the left child of the parent and 00531 // reorder the tree. 00532 // 00533 00534 if (Parent->LeftChild) { 00535 Parent = Parent->LeftChild; 00536 } else { 00537 Parent->LeftChild = Node; 00538 Node->Parent = Parent; 00539 // MiReorderTree(Node, Root); 00540 break; 00541 } 00542 } else { 00543 00544 // 00545 // Starting address of the virtual address descriptor is greater 00546 // than the parent starting virtual address. 00547 // Follow right child link if not null. Otherwise 00548 // insert the descriptor as the right child of the parent and 00549 // reorder the tree. 00550 // 00551 00552 if (Parent->RightChild) { 00553 Parent = Parent->RightChild; 00554 } else { 00555 Parent->RightChild = Node; 00556 Node->Parent = Parent; 00557 // MiReorderTree(Node, Root); 00558 break; 00559 } 00560 } 00561 } 00562 } 00563 return; 00564 }

01008 : 01009 01010 The function locates the virtual address descriptor which describes 01011 a given address. 01012 01013 Arguments: 01014 01015 Vpn - Supplies the virtual page number to locate a descriptor 01016 for. 01017 01018 Return Value: 01019 01020 Returns a pointer to the virtual address descriptor which contains 01021 the supplied virtual address or NULL if none was located. 01022 01023 --*/ 01024 01025 { 01026 01027 PMMADDRESS_NODE Parent; 01028 ULONG Level = 0; 01029 01030 Parent = *Root; 01031 01032 for (;;) { 01033 01034 if (Parent == (PMMADDRESS_NODE)NULL) { 01035 return (PMMADDRESS_NODE)NULL; 01036 } 01037 01038 if (Level == 20) { 01039 01040 // 01041 // There are 20 nodes above this point, reorder the 01042 // tree with this node as the root. 01043 // 01044 01045 MiReorderTree(Parent, Root); 01046 } 01047 01048 if (Vpn < Parent->StartingVpn) { 01049 Parent = Parent->LeftChild; 01050 Level += 1; 01051 01052 } else if (Vpn > Parent->EndingVpn) { 01053 Parent = Parent->RightChild; 01054 Level += 1; 01055 01056 } else { 01057 01058 // 01059 // The address is within the start and end range. 01060 // 01061 01062 return Parent; 01063 } 01064 } 01065 }

00575 : 00576 00577 This function removes a virtual address descriptor from the tree and 00578 reorders the splay tree as appropriate. 00579 00580 Arguments: 00581 00582 Node - Supplies a pointer to a virtual address descriptor. 00583 00584 Return Value: 00585 00586 None. 00587 00588 --*/ 00589 00590 { 00591 00592 PMMADDRESS_NODE LeftChild; 00593 PMMADDRESS_NODE RightChild; 00594 PMMADDRESS_NODE SplayNode; 00595 00596 00597 LeftChild = Node->LeftChild; 00598 RightChild = Node->RightChild; 00599 00600 00601 // 00602 // If the Node is the root of the tree, then establish new root. Else 00603 // isolate splay case and perform splay tree transformation. 00604 // 00605 00606 if (Node == *Root) { 00607 00608 // 00609 // This Node is the root of the tree. There are four cases to 00610 // handle: 00611 // 00612 // 1. the descriptor has no children 00613 // 2. the descriptor has a left child but no right child 00614 // 3. the descriptor has a right child but no left child 00615 // 4. the descriptor has both a right child and a left child 00616 // 00617 00618 if (LeftChild) { 00619 if (RightChild) { 00620 00621 // 00622 // The descriptor has both a left child and a right child. 00623 // 00624 00625 if (LeftChild->RightChild) { 00626 00627 // 00628 // The left child has a right child. Make the right most 00629 // descendent of the right child of the left child the 00630 // new root of the tree. 00631 // 00632 // Pictorially: 00633 // 00634 // R R 00635 // | | 00636 // X Z 00637 // / \ / \ 00638 // A B -> A B 00639 // \ \ 00640 // . . 00641 // \ 00642 // Z 00643 // 00644 00645 SplayNode = LeftChild->RightChild; 00646 while (SplayNode->RightChild) { 00647 SplayNode = SplayNode->RightChild; 00648 } 00649 *Root = SplayNode; 00650 SplayNode->Parent->RightChild = SplayNode->LeftChild; 00651 if (SplayNode->LeftChild) { 00652 SplayNode->LeftChild->Parent = SplayNode->Parent; 00653 } 00654 SplayNode->Parent = (PMMADDRESS_NODE)NULL; 00655 LeftChild->Parent = SplayNode; 00656 RightChild->Parent = SplayNode; 00657 SplayNode->LeftChild = LeftChild; 00658 SplayNode->RightChild = RightChild; 00659 } else if (RightChild->LeftChild) { 00660 00661 // 00662 // The right child has a left child. Make the left most 00663 // descendent of the left child of the right child the 00664 // new root of the tree. 00665 // 00666 // Pictorially: 00667 // 00668 // R R 00669 // | | 00670 // X Z 00671 // / \ / \ 00672 // A B -> A B 00673 // / / 00674 // . . 00675 // / 00676 // Z 00677 // 00678 00679 SplayNode = RightChild->LeftChild; 00680 while (SplayNode->LeftChild) { 00681 SplayNode = SplayNode->LeftChild; 00682 } 00683 *Root = SplayNode; 00684 SplayNode->Parent->LeftChild = SplayNode->RightChild; 00685 if (SplayNode->RightChild) { 00686 SplayNode->RightChild->Parent = SplayNode->Parent; 00687 } 00688 SplayNode->Parent = (PMMADDRESS_NODE)NULL; 00689 LeftChild->Parent = SplayNode; 00690 RightChild->Parent = SplayNode; 00691 SplayNode->LeftChild = LeftChild; 00692 SplayNode->RightChild = RightChild; 00693 } else { 00694 00695 // 00696 // The left child of the descriptor does not have a right child, 00697 // and the right child of the descriptor does not have a left 00698 // child. Make the left child of the descriptor the new root of 00699 // the tree. 00700 // 00701 // Pictorially: 00702 // 00703 // R R 00704 // | | 00705 // X A 00706 // / \ / \ 00707 // A B -> . B 00708 // / / 00709 // . 00710 // 00711 00712 *Root = LeftChild; 00713 LeftChild->Parent = (PMMADDRESS_NODE)NULL; 00714 LeftChild->RightChild = RightChild; 00715 LeftChild->RightChild->Parent = LeftChild; 00716 } 00717 } else { 00718 00719 // 00720 // The descriptor has a left child, but does not have a right child. 00721 // Make the left child the new root of the tree. 00722 // 00723 // Pictorially: 00724 // 00725 // R R 00726 // | | 00727 // X -> A 00728 // / 00729 // A 00730 // 00731 00732 *Root = LeftChild; 00733 LeftChild->Parent = (PMMADDRESS_NODE)NULL; 00734 } 00735 } else if (RightChild) { 00736 00737 // 00738 // The descriptor has a right child, but does not have a left child. 00739 // Make the right child the new root of the tree. 00740 // 00741 // Pictorially: 00742 // 00743 // R R 00744 // | | 00745 // X -> A 00746 // \ 00747 // A 00748 // 00749 00750 *Root = RightChild; 00751 RightChild->Parent = (PMMADDRESS_NODE)NULL; 00752 while (RightChild->LeftChild) { 00753 RightChild = RightChild->LeftChild; 00754 } 00755 } else { 00756 00757 // 00758 // The descriptor has neither a left child nor a right child. The 00759 // tree will be empty after removing the descriptor. 00760 // 00761 // Pictorially: 00762 // 00763 // R R 00764 // | -> 00765 // X 00766 // 00767 00768 *Root = NULL; 00769 } 00770 } else if (LeftChild) { 00771 if (RightChild) { 00772 00773 // 00774 // The descriptor has both a left child and a right child. 00775 // 00776 00777 if (LeftChild->RightChild) { 00778 00779 // 00780 // The left child has a right child. Make the right most 00781 // descendent of the right child of the left child the new 00782 // root of the subtree. 00783 // 00784 // Pictorially: 00785 // 00786 // P P 00787 // / \ 00788 // X X 00789 // / \ / \ 00790 // A B or A B 00791 // \ \ 00792 // . . 00793 // \ \ 00794 // Z Z 00795 // 00796 // | 00797 // v 00798 // 00799 // P P 00800 // / \ 00801 // Z Z 00802 // / \ / \ 00803 // A B or A B 00804 // \ \ 00805 // . . 00806 // 00807 00808 SplayNode = LeftChild->RightChild; 00809 while (SplayNode->RightChild) { 00810 SplayNode = SplayNode->RightChild; 00811 } 00812 SplayNode->Parent->RightChild = SplayNode->LeftChild; 00813 if (SplayNode->LeftChild) { 00814 SplayNode->LeftChild->Parent = SplayNode->Parent; 00815 } 00816 SplayNode->Parent = Node->Parent; 00817 if (Node == Node->Parent->LeftChild) { 00818 Node->Parent->LeftChild = SplayNode; 00819 } else { 00820 Node->Parent->RightChild = SplayNode; 00821 } 00822 LeftChild->Parent = SplayNode; 00823 RightChild->Parent = SplayNode; 00824 SplayNode->LeftChild = LeftChild; 00825 SplayNode->RightChild = RightChild; 00826 } else if (RightChild->LeftChild) { 00827 00828 // 00829 // The right child has a left child. Make the left most 00830 // descendent of the left child of the right child the 00831 // new root of the subtree. 00832 // 00833 // Pictorially: 00834 // 00835 // P P 00836 // / \ 00837 // X X 00838 // / \ / \ 00839 // A B or A B 00840 // / / 00841 // . . 00842 // / / 00843 // Z Z 00844 // 00845 // | 00846 // v 00847 // 00848 // P P 00849 // / \ 00850 // Z Z 00851 // / \ / \ 00852 // A B or A B 00853 // / / 00854 // . . 00855 // 00856 00857 SplayNode = RightChild->LeftChild; 00858 while (SplayNode->LeftChild) { 00859 SplayNode = SplayNode->LeftChild; 00860 } 00861 SplayNode->Parent->LeftChild = SplayNode->RightChild; 00862 if (SplayNode->RightChild) { 00863 SplayNode->RightChild->Parent = SplayNode->Parent; 00864 } 00865 SplayNode->Parent = Node->Parent; 00866 if (Node == Node->Parent->LeftChild) { 00867 Node->Parent->LeftChild = SplayNode; 00868 } else { 00869 Node->Parent->RightChild = SplayNode; 00870 } 00871 LeftChild->Parent = SplayNode; 00872 RightChild->Parent = SplayNode; 00873 SplayNode->LeftChild = LeftChild; 00874 SplayNode->RightChild = RightChild; 00875 } else { 00876 00877 // 00878 // The left child of the descriptor does not have a right child, 00879 // and the right child of the descriptor does node have a left 00880 // child. Make the left child of the descriptor the new root of 00881 // the subtree. 00882 // 00883 // Pictorially: 00884 // 00885 // P P 00886 // / \ 00887 // X X 00888 // / \ / \ 00889 // A B or A B 00890 // / / 00891 // . . 00892 // 00893 // | 00894 // v 00895 // 00896 // P P 00897 // / \ 00898 // A A 00899 // / \ / \ 00900 // . B or . B 00901 // / / 00902 // 00903 00904 SplayNode = LeftChild; 00905 SplayNode->Parent = Node->Parent; 00906 if (Node == Node->Parent->LeftChild) { 00907 Node->Parent->LeftChild = SplayNode; 00908 } else { 00909 Node->Parent->RightChild = SplayNode; 00910 } 00911 SplayNode->RightChild = RightChild; 00912 RightChild->Parent = SplayNode; 00913 } 00914 } else { 00915 00916 // 00917 // The descriptor has a left child, but does not have a right child. 00918 // Make the left child the new root of the subtree. 00919 // 00920 // Pictorially: 00921 // 00922 // P P 00923 // / \ 00924 // X or X 00925 // / / 00926 // A A 00927 // 00928 // | 00929 // v 00930 // 00931 // P P 00932 // / \ 00933 // A A 00934 // 00935 00936 LeftChild->Parent = Node->Parent; 00937 if (Node == Node->Parent->LeftChild) { 00938 Node->Parent->LeftChild = LeftChild; 00939 } else { 00940 Node->Parent->RightChild = LeftChild; 00941 } 00942 } 00943 } else if (RightChild) { 00944 00945 // 00946 // descriptor has a right child, but does not have a left child. Make 00947 // the right child the new root of the subtree. 00948 // 00949 // Pictorially: 00950 // 00951 // P P 00952 // / \ 00953 // X or X 00954 // \ \ 00955 // A A 00956 // 00957 // | 00958 // v 00959 // 00960 // P P 00961 // / \ 00962 // A A 00963 // 00964 00965 RightChild->Parent = Node->Parent; 00966 if (Node == Node->Parent->LeftChild) { 00967 Node->Parent->LeftChild = RightChild; 00968 } else { 00969 Node->Parent->RightChild = RightChild; 00970 } 00971 } else { 00972 00973 // 00974 // The descriptor has neither a left child nor a right child. Delete 00975 // the descriptor from the tree and adjust its parent right or left 00976 // link. 00977 // 00978 // Pictorially: 00979 // 00980 // P P 00981 // / \ 00982 // X or X 00983 // 00984 // | 00985 // v 00986 // 00987 // P P 00988 // 00989 00990 if (Node == Node->Parent->LeftChild) { 00991 Node->Parent->LeftChild = (PMMADDRESS_NODE)NULL; 00992 } else { 00993 Node->Parent->RightChild = (PMMADDRESS_NODE)NULL; 00994 } 00995 } 00996 return; 00997 }

00052 : 00053 00054 This function reorders the Node tree by applying various splay functions 00055 to the tree. This is a local function that is called by the insert Node 00056 routine. 00057 00058 Arguments: 00059 00060 Node - Supplies a pointer to a virtual address descriptor. 00061 00062 Return Value: 00063 00064 None. 00065 00066 --*/ 00067 00068 { 00069 PMMADDRESS_NODE GrandParent; 00070 PMMADDRESS_NODE Parent; 00071 PMMADDRESS_NODE SplayNode; 00072 00073 // 00074 // Reorder Node tree to make it as balanced as possible with as little 00075 // work as possible. 00076 // 00077 00078 SplayNode = Node; 00079 00080 while (SplayNode != *Root) { 00081 00082 Parent = SplayNode->Parent; 00083 if (Parent == *Root) { 00084 00085 // 00086 // Splay node's parent is the root of the tree. Rotate the tree 00087 // left or right depending on whether the splay node is the left 00088 // of right child of its parent. 00089 // 00090 // Pictorially: 00091 // 00092 // Right Left 00093 // 00094 // P X P X 00095 // / \ / \ / \ / \ 00096 // X C -> A P C X -> P A 00097 // / \ / \ / \ / \ 00098 // A B B C B A C B 00099 // 00100 00101 *Root = SplayNode; 00102 SplayNode->Parent = (PMMADDRESS_NODE)NULL; 00103 Parent->Parent = SplayNode; 00104 if (SplayNode == Parent->LeftChild) { 00105 00106 // 00107 // Splay node is the left child of its parent. Rotate tree 00108 // right. 00109 // 00110 00111 Parent->LeftChild = SplayNode->RightChild; 00112 if (SplayNode->RightChild) { 00113 SplayNode->RightChild->Parent = Parent; 00114 } 00115 SplayNode->RightChild = Parent; 00116 } else { 00117 00118 // 00119 // Splay node is the right child of its parent. Rotate tree 00120 // left. 00121 // 00122 00123 Parent->RightChild = SplayNode->LeftChild; 00124 if (SplayNode->LeftChild) { 00125 SplayNode->LeftChild->Parent = Parent; 00126 } 00127 SplayNode->LeftChild = Parent; 00128 } 00129 break; 00130 } else { 00131 GrandParent = Parent->Parent; 00132 if ((SplayNode == Parent->LeftChild) && 00133 (Parent == GrandParent->LeftChild)) { 00134 00135 // 00136 // Both the splay node and the parent node are left children 00137 // of their parents. Rotate tree right and make the parent 00138 // the root of the new subtree. 00139 // 00140 // Pictorially: 00141 // 00142 // G P 00143 // / \ / \ 00144 // P D X G 00145 // / \ -> / \ / \ 00146 // X C A B C D 00147 // / \ 00148 // A B 00149 // 00150 00151 if (GrandParent == *Root) { 00152 *Root = Parent; 00153 Parent->Parent = (PMMADDRESS_NODE)NULL; 00154 } else { 00155 Parent->Parent = GrandParent->Parent; 00156 if (GrandParent == GrandParent->Parent->LeftChild) { 00157 GrandParent->Parent->LeftChild = Parent; 00158 } else { 00159 GrandParent->Parent->RightChild = Parent; 00160 } 00161 } 00162 GrandParent->LeftChild = Parent->RightChild; 00163 if (Parent->RightChild) { 00164 Parent->RightChild->Parent = GrandParent; 00165 } 00166 GrandParent->Parent = Parent; 00167 Parent->RightChild = GrandParent; 00168 SplayNode = Parent; 00169 } else if ((SplayNode == Parent->RightChild) && 00170 (Parent == GrandParent->RightChild)) { 00171 00172 // 00173 // Both the splay node and the parent node are right children 00174 // of their parents. Rotate tree left and make the parent 00175 // the root of the new subtree. 00176 // 00177 // Pictorially: 00178 // 00179 // G P 00180 // / \ / \ 00181 // D P G X 00182 // / \ -> / \ / \ 00183 // C X D C B A 00184 // / \ 00185 // A B 00186 // 00187 00188 if (GrandParent == *Root) { 00189 *Root = Parent; 00190 Parent->Parent = (PMMADDRESS_NODE)NULL; 00191 } else { 00192 Parent->Parent = GrandParent->Parent; 00193 if (GrandParent == GrandParent->Parent->LeftChild) { 00194 GrandParent->Parent->LeftChild = Parent; 00195 } else { 00196 GrandParent->Parent->RightChild = Parent; 00197 } 00198 } 00199 GrandParent->RightChild = Parent->LeftChild; 00200 if (Parent->LeftChild) { 00201 Parent->LeftChild->Parent = GrandParent; 00202 } 00203 GrandParent->Parent = Parent; 00204 Parent->LeftChild = GrandParent; 00205 SplayNode = Parent; 00206 } else if ((SplayNode == Parent->LeftChild) && 00207 (Parent == GrandParent->RightChild)) { 00208 00209 // 00210 // Splay node is the left child of its parent and parent is 00211 // the right child of its parent. Rotate tree left and make 00212 // splay node the root of the new subtree. 00213 // 00214 // Pictorially: 00215 // 00216 // G X 00217 // / \ / \ 00218 // A P G P 00219 // / \ -> / \ / \ 00220 // X D A B C D 00221 // / \ 00222 // B C 00223 // 00224 00225 if (GrandParent == *Root) { 00226 *Root = SplayNode; 00227 SplayNode->Parent = (PMMADDRESS_NODE)NULL; 00228 } else { 00229 SplayNode->Parent = GrandParent->Parent; 00230 if (GrandParent == GrandParent->Parent->LeftChild) { 00231 GrandParent->Parent->LeftChild = SplayNode; 00232 } else { 00233 GrandParent->Parent->RightChild = SplayNode; 00234 } 00235 } 00236 Parent->LeftChild = SplayNode->RightChild; 00237 if (SplayNode->RightChild) { 00238 SplayNode->RightChild->Parent = Parent; 00239 } 00240 GrandParent->RightChild = SplayNode->LeftChild; 00241 if (SplayNode->LeftChild) { 00242 SplayNode->LeftChild->Parent = GrandParent; 00243 } 00244 Parent->Parent = SplayNode; 00245 GrandParent->Parent = SplayNode; 00246 SplayNode->LeftChild = GrandParent; 00247 SplayNode->RightChild = Parent; 00248 } else { 00249 00250 // 00251 // Splay node is the right child of its parent and parent is 00252 // the left child of its parent. Rotate tree right and make 00253 // splay node the root of the new subtree. 00254 // 00255 // Pictorially: 00256 // 00257 // G X 00258 // / \ / \ 00259 // P A P G 00260 // / \ -> / \ / \ 00261 // D X D C B A 00262 // / \ 00263 // C B 00264 // 00265 00266 if (GrandParent == *Root) { 00267 *Root = SplayNode; 00268 SplayNode->Parent = (PMMADDRESS_NODE)NULL; 00269 } else { 00270 SplayNode->Parent = GrandParent->Parent; 00271 if (GrandParent == GrandParent->Parent->LeftChild) { 00272 GrandParent->Parent->LeftChild = SplayNode; 00273 } else { 00274 GrandParent->Parent->RightChild = SplayNode; 00275 } 00276 } 00277 Parent->RightChild = SplayNode->LeftChild; 00278 if (SplayNode->LeftChild) { 00279 SplayNode->LeftChild->Parent = Parent; 00280 } 00281 GrandParent->LeftChild = SplayNode->RightChild; 00282 if (SplayNode->RightChild) { 00283 SplayNode->RightChild->Parent = GrandParent; 00284 } 00285 Parent->Parent = SplayNode; 00286 GrandParent->Parent = SplayNode; 00287 SplayNode->LeftChild = Parent; 00288 SplayNode->RightChild = GrandParent; 00289 } 00290 } 00291 } 00292 return; 00293 }


Functions
VOID	MiReorderTree (IN PMMADDRESS_NODE Node, IN OUT PMMADDRESS_NODE *Root)
PMMADDRESS_NODE FASTCALL	MiGetNextNode (IN PMMADDRESS_NODE Node)
PMMADDRESS_NODE FASTCALL	MiGetPreviousNode (IN PMMADDRESS_NODE Node)
PMMADDRESS_NODE FASTCALL	MiGetFirstNode (IN PMMADDRESS_NODE Root)
VOID FASTCALL	MiInsertNode (IN PMMADDRESS_NODE Node, IN OUT PMMADDRESS_NODE *Root)
VOID FASTCALL	MiRemoveNode (IN PMMADDRESS_NODE Node, IN OUT PMMADDRESS_NODE *Root)
PMMADDRESS_NODE FASTCALL	MiLocateAddressInTree (IN ULONG_PTR Vpn, IN PMMADDRESS_NODE *Root)
PMMADDRESS_NODE	MiCheckForConflictingNode (IN ULONG_PTR StartVpn, IN ULONG_PTR EndVpn, IN PMMADDRESS_NODE Root)
PVOID	MiFindEmptyAddressRangeInTree (IN SIZE_T SizeOfRange, IN ULONG_PTR Alignment, IN PMMADDRESS_NODE Root, OUT PMMADDRESS_NODE *PreviousVad)
PVOID	MiFindEmptyAddressRangeDownTree (IN SIZE_T SizeOfRange, IN PVOID HighestAddressToEndAt, IN ULONG_PTR Alignment, IN PMMADDRESS_NODE Root)

addrsup.c File Reference

Functions

Function Documentation