ntoskrnl/config/cmboot.c

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         BSD - See COPYING.ARM in the top level directory
   4  * FILE:            ntoskrnl/config/cmboot.c
   5  * PURPOSE:         Configuration Manager - Boot Initialization
   6  * PROGRAMMERS:     ReactOS Portable Systems Group
   7  *                  Alex Ionescu (alex.ionescu@reactos.org)
   8  */
   9
  10 /* INCLUDES *******************************************************************/
  11
  12 #include "ntoskrnl.h"
  13 #define NDEBUG
  14 #include "debug.h"
  15
  16 /* FUNCTIONS ******************************************************************/
  17
  18 HCELL_INDEX
  19 NTAPI
  20 CmpFindControlSet(IN PHHIVE SystemHive,
  21                   IN HCELL_INDEX RootCell,
  22                   IN PUNICODE_STRING SelectKeyName,
  23                   OUT PBOOLEAN AutoSelect)
  24 {
  25     UNICODE_STRING KeyName;
  26     PCM_KEY_NODE Node;
  27     HCELL_INDEX SelectCell, AutoSelectCell, SelectValueCell, ControlSetCell;
  28     HCELL_INDEX CurrentValueCell;
  29     PCM_KEY_VALUE KeyValue;
  30     ULONG Length;
  31     PULONG ControlSetId;
  32     ANSI_STRING ControlSetAnsiName;
  33     CHAR Buffer[128];
  34     WCHAR WideBuffer[128];
  35     NTSTATUS Status;
  36     PULONG CurrentData;
  37
  38     /* Sanity check */
  39     ASSERT(SystemHive->ReleaseCellRoutine == NULL);
  40
  41     /* Get the Select subkey */
  42     RtlInitUnicodeString(&KeyName, L"select");
  43     Node = (PCM_KEY_NODE)HvGetCell(SystemHive, RootCell);
  44     if (!Node) return HCELL_NIL;
  45     SelectCell = CmpFindSubKeyByName(SystemHive, Node, &KeyName);
  46     if (SelectCell == HCELL_NIL) return SelectCell;
  47
  48     /* Get AutoSelect value */
  49     RtlInitUnicodeString(&KeyName, L"AutoSelect");
  50     Node = (PCM_KEY_NODE)HvGetCell(SystemHive, SelectCell);
  51     if (!Node) return HCELL_NIL;
  52     AutoSelectCell = CmpFindValueByName(SystemHive, Node, &KeyName);
  53     if (AutoSelectCell == HCELL_NIL)
  54     {
  55         /* Assume TRUE if the value is missing. */
  56         *AutoSelect = TRUE;
  57     }
  58     else
  59     {
  60         /* Read the value */
  61         KeyValue = (PCM_KEY_VALUE)HvGetCell(SystemHive, AutoSelectCell);
  62         if (KeyValue == NULL) return HCELL_NIL;
  63
  64         /* Convert it to a boolean */
  65         *AutoSelect = *(PBOOLEAN)CmpValueToData(SystemHive, KeyValue, &Length);
  66     }
  67
  68     /* Now find the control set being looked up */
  69     Node = (PCM_KEY_NODE)HvGetCell(SystemHive, SelectCell);
  70     if (!Node) return HCELL_NIL;
  71     SelectValueCell = CmpFindValueByName(SystemHive, Node, SelectKeyName);
  72     if (SelectValueCell == HCELL_NIL) return SelectValueCell;
  73
  74     /* Read the value (corresponding to the CCS ID) */
  75     KeyValue = (PCM_KEY_VALUE)HvGetCell(SystemHive, SelectValueCell);
  76     if (!KeyValue) return HCELL_NIL;
  77     if (KeyValue->Type != REG_DWORD) return HCELL_NIL;
  78     ControlSetId = (PULONG)CmpValueToData(SystemHive, KeyValue, &Length);
  79
  80     /* Now build an Ansi String for the CCS's Name */
  81     sprintf(Buffer, "ControlSet%03lu", *ControlSetId);
  82     ControlSetAnsiName.Length = (USHORT)strlen(Buffer);
  83     ControlSetAnsiName.MaximumLength = (USHORT)strlen(Buffer);
  84     ControlSetAnsiName.Buffer = Buffer;
  85
  86     /* And convert it to Unicode... */
  87     KeyName.MaximumLength = 256;
  88     KeyName.Buffer = WideBuffer;
  89     Status = RtlAnsiStringToUnicodeString(&KeyName,
  90                                           &ControlSetAnsiName,
  91                                           FALSE);
  92     if (!NT_SUCCESS(Status)) return HCELL_NIL;
  93
  94     /* Now open it */
  95     Node = (PCM_KEY_NODE)HvGetCell(SystemHive, RootCell);
  96     if (!Node) return HCELL_NIL;
  97     ControlSetCell = CmpFindSubKeyByName(SystemHive, Node, &KeyName);
  98     if (ControlSetCell == HCELL_NIL) return ControlSetCell;
  99
 100     /* Get the value of the "Current" CCS */
 101     RtlInitUnicodeString(&KeyName, L"Current");
 102     Node =  (PCM_KEY_NODE)HvGetCell(SystemHive, SelectCell);
 103     if (!Node) return HCELL_NIL;
 104     CurrentValueCell = CmpFindValueByName(SystemHive, Node, &KeyName);
 105
 106     /* Make sure it exists */
 107     if (CurrentValueCell != HCELL_NIL)
 108     {
 109         /* Get the current value and make sure its a ULONG */
 110         KeyValue = (PCM_KEY_VALUE)HvGetCell(SystemHive, CurrentValueCell);
 111         if (!KeyValue) return HCELL_NIL;
 112         if (KeyValue->Type == REG_DWORD)
 113         {
 114             /* Get the data and update it */
 115             CurrentData = (PULONG)CmpValueToData(SystemHive,
 116                                                  KeyValue,
 117                                                  &Length);
 118             if (!CurrentData) return HCELL_NIL;
 119             *CurrentData = *ControlSetId;
 120         }
 121     }
 122
 123     /* Return the CCS Cell */
 124     return ControlSetCell;
 125 }
 126
 127 ULONG
 128 NTAPI
 129 CmpFindTagIndex(IN PHHIVE Hive,
 130                 IN HCELL_INDEX TagCell,
 131                 IN HCELL_INDEX GroupOrderCell,
 132                 IN PUNICODE_STRING GroupName)
 133 {
 134     PCM_KEY_VALUE TagValue, Value;
 135     HCELL_INDEX OrderCell;
 136     PULONG TagOrder, DriverTag;
 137     ULONG CurrentTag, Length;
 138     PCM_KEY_NODE Node;
 139     BOOLEAN BufferAllocated;
 140     ASSERT(Hive->ReleaseCellRoutine == NULL);
 141
 142     /* Get the tag */
 143     Value = HvGetCell(Hive, TagCell);
 144     ASSERT(Value);
 145     DriverTag = (PULONG)CmpValueToData(Hive, Value, &Length);
 146     ASSERT(DriverTag);
 147
 148     /* Get the order array */
 149     Node = HvGetCell(Hive, GroupOrderCell);
 150     ASSERT(Node);
 151     OrderCell = CmpFindValueByName(Hive, Node, GroupName);
 152     if (OrderCell == HCELL_NIL) return -2;
 153
 154     /* And read it */
 155     TagValue = HvGetCell(Hive, OrderCell);
 156     CmpGetValueData(Hive, TagValue, &Length, (PVOID*)&TagOrder, &BufferAllocated, &OrderCell);
 157     ASSERT(TagOrder);
 158
 159     /* Parse each tag */
 160     for (CurrentTag = 1; CurrentTag <= TagOrder[0]; CurrentTag++)
 161     {
 162         /* Find a match */
 163         if (TagOrder[CurrentTag] == *DriverTag)
 164         {
 165             /* Found it -- return the tag */
 166             if (BufferAllocated) ExFreePool(TagOrder);
 167             return CurrentTag;
 168         }
 169     }
 170
 171     /* No matches, so assume next to last ordering */
 172     if (BufferAllocated) ExFreePool(TagOrder);
 173     return -2;
 174 }
 175
 176 BOOLEAN
 177 NTAPI
 178 CmpAddDriverToList(IN PHHIVE Hive,
 179                    IN HCELL_INDEX DriverCell,
 180                    IN HCELL_INDEX GroupOrderCell,
 181                    IN PUNICODE_STRING RegistryPath,
 182                    IN PLIST_ENTRY BootDriverListHead)
 183 {
 184     PBOOT_DRIVER_NODE DriverNode;
 185     PBOOT_DRIVER_LIST_ENTRY DriverEntry;
 186     PCM_KEY_NODE Node;
 187     ULONG NameLength, Length;
 188     HCELL_INDEX ValueCell, TagCell;
 189     PCM_KEY_VALUE Value;
 190     PUNICODE_STRING FileName, RegistryString;
 191     UNICODE_STRING UnicodeString;
 192     PULONG ErrorControl;
 193     PWCHAR Buffer;
 194     ASSERT(Hive->ReleaseCellRoutine == NULL);
 195
 196     /* Allocate a driver node and initialize it */
 197     DriverNode = CmpAllocate(sizeof(BOOT_DRIVER_NODE), FALSE, TAG_CM);
 198     if (!DriverNode) return FALSE;
 199     DriverEntry = &DriverNode->ListEntry;
 200     DriverEntry->RegistryPath.Buffer = NULL;
 201     DriverEntry->FilePath.Buffer = NULL;
 202
 203     /* Get the driver cell */
 204     Node = HvGetCell(Hive, DriverCell);
 205     ASSERT(Node);
 206
 207     /* Get the name from the cell */
 208     DriverNode->Name.Length = Node->Flags & KEY_COMP_NAME ?
 209                               CmpCompressedNameSize(Node->Name, Node->NameLength) :
 210                               Node->NameLength;
 211     DriverNode->Name.MaximumLength = DriverNode->Name.Length;
 212     NameLength = DriverNode->Name.Length;
 213
 214     /* Now allocate the buffer for it and copy the name */
 215     DriverNode->Name.Buffer = CmpAllocate(NameLength, FALSE, TAG_CM);
 216     if (!DriverNode->Name.Buffer) return FALSE;
 217     if (Node->Flags & KEY_COMP_NAME)
 218     {
 219         /* Compressed name */
 220         CmpCopyCompressedName(DriverNode->Name.Buffer,
 221                               DriverNode->Name.Length,
 222                               Node->Name,
 223                               Node->NameLength);
 224     }
 225     else
 226     {
 227         /* Normal name */
 228         RtlCopyMemory(DriverNode->Name.Buffer, Node->Name, Node->NameLength);
 229     }
 230
 231     /* Now find the image path */
 232     RtlInitUnicodeString(&UnicodeString, L"ImagePath");
 233     ValueCell = CmpFindValueByName(Hive, Node, &UnicodeString);
 234     if (ValueCell == HCELL_NIL)
 235     {
 236         /* Couldn't find it, so assume the drivers path */
 237         Length = sizeof(L"System32\\Drivers\\") + NameLength + sizeof(L".sys");
 238
 239         /* Allocate the path name */
 240         FileName = &DriverEntry->FilePath;
 241         FileName->Length = 0;
 242         FileName->MaximumLength = Length;
 243         FileName->Buffer = CmpAllocate(Length, FALSE,TAG_CM);
 244         if (!FileName->Buffer) return FALSE;
 245
 246         /* Write the path name */
 247         RtlAppendUnicodeToString(FileName, L"System32\\Drivers\\");
 248         RtlAppendUnicodeStringToString(FileName, &DriverNode->Name);
 249         RtlAppendUnicodeToString(FileName, L".sys");
 250     }
 251     else
 252     {
 253         /* Path name exists, so grab it */
 254         Value = HvGetCell(Hive, ValueCell);
 255         ASSERT(Value);
 256
 257         /* Allocate and setup the path name */
 258         FileName = &DriverEntry->FilePath;
 259         Buffer = (PWCHAR)CmpValueToData(Hive, Value, &Length);
 260         FileName->MaximumLength = FileName->Length = Length;
 261         FileName->Buffer = CmpAllocate(Length, FALSE, TAG_CM);
 262
 263         /* Transfer the data */
 264         if (!(FileName->Buffer) || !(Buffer)) return FALSE;
 265         RtlCopyMemory(FileName->Buffer, Buffer, Length);
 266     }
 267
 268     /* Now build the registry path */
 269     RegistryString = &DriverEntry->RegistryPath;
 270     RegistryString->Length = 0;
 271     RegistryString->MaximumLength = RegistryPath->Length + NameLength;
 272     RegistryString->Buffer = CmpAllocate(RegistryString->MaximumLength, FALSE, TAG_CM);
 273     if (!RegistryString->Buffer) return FALSE;
 274
 275     /* Add the driver name to it */
 276     RtlAppendUnicodeStringToString(RegistryString, RegistryPath);
 277     RtlAppendUnicodeStringToString(RegistryString, &DriverNode->Name);
 278
 279     /* The entry is done, add it */
 280     InsertHeadList(BootDriverListHead, &DriverEntry->Link);
 281
 282     /* Now find error control settings */
 283     RtlInitUnicodeString(&UnicodeString, L"ErrorControl");
 284     ValueCell = CmpFindValueByName(Hive, Node, &UnicodeString);
 285     if (ValueCell == HCELL_NIL)
 286     {
 287         /* Couldn't find it, so assume default */
 288         DriverNode->ErrorControl = NormalError;
 289     }
 290     else
 291     {
 292         /* Otherwise, read whatever the data says */
 293         Value = HvGetCell(Hive, ValueCell);
 294         ASSERT(Value);
 295         ErrorControl = (PULONG)CmpValueToData(Hive, Value, &Length);
 296         ASSERT(ErrorControl);
 297         DriverNode->ErrorControl = *ErrorControl;
 298     }
 299
 300     /* Next, get the group cell */
 301     RtlInitUnicodeString(&UnicodeString, L"group");
 302     ValueCell = CmpFindValueByName(Hive, Node, &UnicodeString);
 303     if (ValueCell == HCELL_NIL)
 304     {
 305         /* Couldn't find, so set an empty string */
 306         RtlInitEmptyUnicodeString(&DriverNode->Group, NULL, 0);
 307     }
 308     else
 309     {
 310         /* Found it, read the group value */
 311         Value = HvGetCell(Hive, ValueCell);
 312         ASSERT(Value);
 313
 314         /* Copy it into the node */
 315         DriverNode->Group.Buffer = (PWCHAR)CmpValueToData(Hive, Value, &Length);
 316         if (!DriverNode->Group.Buffer) return FALSE;
 317         DriverNode->Group.Length = Length - sizeof(UNICODE_NULL);
 318         DriverNode->Group.MaximumLength = DriverNode->Group.Length;
 319     }
 320
 321     /* Finally, find the tag */
 322     RtlInitUnicodeString(&UnicodeString, L"Tag");
 323     TagCell = CmpFindValueByName(Hive, Node, &UnicodeString);
 324     if (TagCell == HCELL_NIL)
 325     {
 326         /* No tag, so load last */
 327         DriverNode->Tag = -1;
 328     }
 329     else
 330     {
 331         /* Otherwise, decode it based on tag order */
 332         DriverNode->Tag = CmpFindTagIndex(Hive,
 333                                           TagCell,
 334                                           GroupOrderCell,
 335                                           &DriverNode->Group);
 336     }
 337
 338     /* All done! */
 339     return TRUE;
 340 }
 341
 342 BOOLEAN
 343 NTAPI
 344 CmpIsLoadType(IN PHHIVE Hive,
 345               IN HCELL_INDEX Cell,
 346               IN SERVICE_LOAD_TYPE LoadType)
 347 {
 348     PCM_KEY_NODE Node;
 349     HCELL_INDEX ValueCell;
 350     UNICODE_STRING ValueString = RTL_CONSTANT_STRING(L"Start");
 351     PCM_KEY_VALUE Value;
 352     ULONG Length;
 353     PLONG Data;
 354     ASSERT(Hive->ReleaseCellRoutine == NULL);
 355
 356     /* Open the start cell */
 357     Node = HvGetCell(Hive, Cell);
 358     ASSERT(Node);
 359     ValueCell = CmpFindValueByName(Hive, Node, &ValueString);
 360     if (ValueCell == HCELL_NIL) return FALSE;
 361
 362     /* Read the start value */
 363     Value = HvGetCell(Hive, ValueCell);
 364     ASSERT(Value);
 365     Data = (PLONG)CmpValueToData(Hive, Value, &Length);
 366     ASSERT(Data);
 367
 368     /* Return if the type matches */
 369     return (*Data == LoadType);
 370 }
 371
 372 BOOLEAN
 373 NTAPI
 374 CmpFindDrivers(IN PHHIVE Hive,
 375                IN HCELL_INDEX ControlSet,
 376                IN SERVICE_LOAD_TYPE LoadType,
 377                IN PWCHAR BootFileSystem OPTIONAL,
 378                IN PLIST_ENTRY DriverListHead)
 379 {
 380     HCELL_INDEX ServicesCell, ControlCell, GroupOrderCell, DriverCell;
 381     UNICODE_STRING Name;
 382     ULONG i;
 383     WCHAR Buffer[128];
 384     UNICODE_STRING UnicodeString, KeyPath;
 385     PBOOT_DRIVER_NODE FsNode;
 386     PCM_KEY_NODE ControlNode, ServicesNode, Node;
 387     ASSERT(Hive->ReleaseCellRoutine == NULL);
 388
 389     /* Open the control set key */
 390     ControlNode = HvGetCell(Hive, ControlSet);
 391     ASSERT(ControlNode);
 392
 393     /* Get services cell */
 394     RtlInitUnicodeString(&Name, L"Services");
 395     ServicesCell = CmpFindSubKeyByName(Hive, ControlNode, &Name);
 396     if (ServicesCell == HCELL_NIL) return FALSE;
 397
 398     /* Open services key */
 399     ServicesNode = HvGetCell(Hive, ServicesCell);
 400     ASSERT(ServicesNode);
 401
 402     /* Get control cell */
 403     RtlInitUnicodeString(&Name, L"Control");
 404     ControlCell = CmpFindSubKeyByName(Hive, ControlNode, &Name);
 405     if (ControlCell == HCELL_NIL) return FALSE;
 406
 407     /* Get the group order cell and read it */
 408     RtlInitUnicodeString(&Name, L"GroupOrderList");
 409     Node = HvGetCell(Hive, ControlCell);
 410     ASSERT(Node);
 411     GroupOrderCell = CmpFindSubKeyByName(Hive, Node, &Name);
 412     if (GroupOrderCell == HCELL_NIL) return FALSE;
 413
 414     /* Build the root registry path */
 415     RtlInitEmptyUnicodeString(&KeyPath, Buffer, sizeof(Buffer));
 416     RtlAppendUnicodeToString(&KeyPath, L"\\Registry\\Machine\\System\\CurrentControlSet\\Services\\");
 417
 418     /* Find the first subkey (ie: the first driver or service) */
 419     i = 0;
 420     DriverCell = CmpFindSubKeyByNumber(Hive, ServicesNode, i);
 421     while (DriverCell != HCELL_NIL)
 422     {
 423         /* Make sure it's a driver of this start type */
 424         if (CmpIsLoadType(Hive, DriverCell, LoadType))
 425         {
 426             /* Add it to the list */
 427             CmpAddDriverToList(Hive,
 428                                DriverCell,
 429                                GroupOrderCell,
 430                                &KeyPath,
 431                                DriverListHead);
 432
 433         }
 434
 435         /* Try the next subkey */
 436         DriverCell = CmpFindSubKeyByNumber(Hive, ServicesNode, ++i);
 437     }
 438
 439     /* Check if we have a boot file system */
 440     if (BootFileSystem)
 441     {
 442         /* Find it */
 443         RtlInitUnicodeString(&UnicodeString, BootFileSystem);
 444         DriverCell = CmpFindSubKeyByName(Hive, ServicesNode, &UnicodeString);
 445         if (DriverCell != HCELL_NIL)
 446         {
 447             /* Always add it to the list */
 448             CmpAddDriverToList(Hive,
 449                                DriverCell,
 450                                GroupOrderCell,
 451                                &KeyPath,
 452                                DriverListHead);
 453
 454             /* Mark it as critical so it always loads */
 455             FsNode = CONTAINING_RECORD(DriverListHead->Flink,
 456                                        BOOT_DRIVER_NODE,
 457                                        ListEntry.Link);
 458             FsNode->ErrorControl = SERVICE_ERROR_CRITICAL;
 459         }
 460     }
 461
 462     /* We're done! */
 463     return TRUE;
 464 }
 465
 466 BOOLEAN
 467 NTAPI
 468 CmpDoSort(IN PLIST_ENTRY DriverListHead,
 469           IN PUNICODE_STRING OrderList)
 470 {
 471     PWCHAR Current, End = NULL;
 472     PLIST_ENTRY NextEntry;
 473     UNICODE_STRING GroupName;
 474     PBOOT_DRIVER_NODE CurrentNode;
 475
 476     /* We're going from end to start, so get to the last group and keep going */
 477     Current = &OrderList->Buffer[OrderList->Length / sizeof(WCHAR)];
 478     while (Current > OrderList->Buffer)
 479     {
 480         /* Scan the current string */
 481         do
 482         {
 483             if (*Current == UNICODE_NULL) End = Current;
 484         } while ((*(--Current - 1) != UNICODE_NULL) && (Current != OrderList->Buffer));
 485
 486         /* This is our cleaned up string for this specific group */
 487         ASSERT(End != NULL);
 488         GroupName.Length = (End - Current) * sizeof(WCHAR);
 489         GroupName.MaximumLength = GroupName.Length;
 490         GroupName.Buffer = Current;
 491
 492         /* Now loop the driver list */
 493         NextEntry = DriverListHead->Flink;
 494         while (NextEntry != DriverListHead)
 495         {
 496             /* Get this node */
 497             CurrentNode = CONTAINING_RECORD(NextEntry,
 498                                             BOOT_DRIVER_NODE,
 499                                             ListEntry.Link);
 500
 501             /* Get the next entry now since we'll do a relink */
 502             NextEntry = CurrentNode->ListEntry.Link.Flink;
 503
 504             /* Is there a group name and does it match the current group? */
 505             if ((CurrentNode->Group.Buffer) &&
 506                 (RtlEqualUnicodeString(&GroupName, &CurrentNode->Group, TRUE)))
 507             {
 508                 /* Remove from this location and re-link in the new one */
 509                 RemoveEntryList(&CurrentNode->ListEntry.Link);
 510                 InsertHeadList(DriverListHead, &CurrentNode->ListEntry.Link);
 511             }
 512         }
 513
 514         /* Move on */
 515         Current--;
 516     }
 517
 518     /* All done */
 519     return TRUE;
 520 }
 521
 522 BOOLEAN
 523 NTAPI
 524 CmpSortDriverList(IN PHHIVE Hive,
 525                   IN HCELL_INDEX ControlSet,
 526                   IN PLIST_ENTRY DriverListHead)
 527 {
 528     HCELL_INDEX Controls, GroupOrder, ListCell;
 529     UNICODE_STRING Name, DependList;
 530     PCM_KEY_VALUE ListNode;
 531     ULONG Length;
 532     PCM_KEY_NODE Node;
 533     ASSERT(Hive->ReleaseCellRoutine == NULL);
 534
 535     /* Open the control key */
 536     Node = HvGetCell(Hive, ControlSet);
 537     ASSERT(Node);
 538     RtlInitUnicodeString(&Name, L"Control");
 539     Controls = CmpFindSubKeyByName(Hive, Node, &Name);
 540     if (Controls == HCELL_NIL) return FALSE;
 541
 542     /* Open the service group order */
 543     Node = HvGetCell(Hive, Controls);
 544     ASSERT(Node);
 545     RtlInitUnicodeString(&Name, L"ServiceGroupOrder");
 546     GroupOrder = CmpFindSubKeyByName(Hive, Node, &Name);
 547     if (GroupOrder == HCELL_NIL) return FALSE;
 548
 549     /* Open the list key */
 550     Node = HvGetCell(Hive, GroupOrder);
 551     ASSERT(Node);
 552     RtlInitUnicodeString(&Name, L"list");
 553     ListCell = CmpFindValueByName(Hive, Node, &Name);
 554     if (ListCell == HCELL_NIL) return FALSE;
 555
 556     /* Now read the actual list */
 557     ListNode = HvGetCell(Hive, ListCell);
 558     ASSERT(ListNode);
 559     if (ListNode->Type != REG_MULTI_SZ) return FALSE;
 560
 561     /* Copy it into a buffer */
 562     DependList.Buffer = (PWCHAR)CmpValueToData(Hive, ListNode, &Length);
 563     if (!DependList.Buffer) return FALSE;
 564     DependList.Length = DependList.MaximumLength = Length - sizeof(UNICODE_NULL);
 565
 566     /* And start the recurive sort algorithm */
 567     return CmpDoSort(DriverListHead, &DependList);
 568 }
 569
 570 BOOLEAN
 571 NTAPI
 572 CmpOrderGroup(IN PBOOT_DRIVER_NODE StartNode,
 573               IN PBOOT_DRIVER_NODE EndNode)
 574 {
 575     PBOOT_DRIVER_NODE CurrentNode, PreviousNode;
 576     PLIST_ENTRY ListEntry;
 577
 578     /* Base case, nothing to do */
 579     if (StartNode == EndNode) return TRUE;
 580
 581     /* Loop the nodes */
 582     CurrentNode = StartNode;
 583     do
 584     {
 585         /* Save this as the previous node */
 586         PreviousNode = CurrentNode;
 587
 588         /* And move to the next one */
 589         ListEntry = CurrentNode->ListEntry.Link.Flink;
 590         CurrentNode = CONTAINING_RECORD(ListEntry,
 591                                         BOOT_DRIVER_NODE,
 592                                         ListEntry.Link);
 593
 594         /* Check if the previous driver had a bigger tag */
 595         if (PreviousNode->Tag > CurrentNode->Tag)
 596         {
 597             /* Check if we need to update the tail */
 598             if (CurrentNode == EndNode)
 599             {
 600                 /* Update the tail */
 601                 ListEntry = CurrentNode->ListEntry.Link.Blink;
 602                 EndNode = CONTAINING_RECORD(ListEntry,
 603                                             BOOT_DRIVER_NODE,
 604                                             ListEntry.Link);
 605             }
 606
 607             /* Remove this driver since we need to move it */
 608             RemoveEntryList(&CurrentNode->ListEntry.Link);
 609
 610             /* Keep looping until we find a driver with a lower tag than ours */
 611             while ((PreviousNode->Tag > CurrentNode->Tag) && (PreviousNode != StartNode))
 612             {
 613                 /* We'll be re-inserted at this spot */
 614                 ListEntry = PreviousNode->ListEntry.Link.Blink;
 615                 PreviousNode = CONTAINING_RECORD(ListEntry,
 616                                                  BOOT_DRIVER_NODE,
 617                                                  ListEntry.Link);
 618             }
 619
 620             /* Do the insert in the new location */
 621             InsertTailList(&PreviousNode->ListEntry.Link, &CurrentNode->ListEntry.Link);
 622
 623             /* Update the head, if needed */
 624             if (PreviousNode == StartNode) StartNode = CurrentNode;
 625         }
 626     } while (CurrentNode != EndNode);
 627
 628     /* All done */
 629     return TRUE;
 630 }
 631
 632 BOOLEAN
 633 NTAPI
 634 CmpResolveDriverDependencies(IN PLIST_ENTRY DriverListHead)
 635 {
 636     PLIST_ENTRY NextEntry;
 637     PBOOT_DRIVER_NODE StartNode, EndNode, CurrentNode;
 638
 639     /* Loop the list */
 640     NextEntry = DriverListHead->Flink;
 641     while (NextEntry != DriverListHead)
 642     {
 643         /* Find the first entry */
 644         StartNode = CONTAINING_RECORD(NextEntry,
 645                                       BOOT_DRIVER_NODE,
 646                                       ListEntry.Link);
 647         do
 648         {
 649             /* Find the last entry */
 650             EndNode = CONTAINING_RECORD(NextEntry,
 651                                         BOOT_DRIVER_NODE,
 652                                         ListEntry.Link);
 653
 654             /* Get the next entry */
 655             NextEntry = NextEntry->Flink;
 656             CurrentNode = CONTAINING_RECORD(NextEntry,
 657                                             BOOT_DRIVER_NODE,
 658                                             ListEntry.Link);
 659
 660             /* If the next entry is back to the top, break out */
 661             if (NextEntry == DriverListHead) break;
 662
 663             /* Otherwise, check if this entry is equal */
 664             if (!RtlEqualUnicodeString(&StartNode->Group,
 665                                        &CurrentNode->Group,
 666                                        TRUE))
 667             {
 668                 /* It is, so we've detected a cycle, break out */
 669                 break;
 670             }
 671         } while (NextEntry != DriverListHead);
 672
 673         /* Now we have the correct start and end pointers, so do the sort */
 674         CmpOrderGroup(StartNode, EndNode);
 675     }
 676
 677     /* We're done */
 678     return TRUE;
 679 }
 680
 681 /* EOF */