Algorithm for organizing logical volumes in the Windows OS environment
The JavaScript code prototype surely outperforms the basic DISKPART.EXE system utility in solving the problem of streamlining logical volumes.
An algorithm is described whose implementation in JavaScript prototype code confidently ahead of the time required for solving the problem is the DISKPART.EXE system reference utility. The principles on which the algorithm is based are described. A possible explanation, but not proof, is given to why DISKPART.EXE is slower than JavaScript code. Contest results are given in various editions of Windows, including Windows 10 RTM TH1. Described as changes made in various editions of Windows 10 forced several times to rework the algorithm in order to increase its reliability, although at the cost of some loss of speed.
Logical volumes underlie any OS. As long as there are no logical volumes, the system simply has nowhere to place. Preparing a logical volume involves allocating space on a physical storage device (that is, creating a data volume, Storage # Volume, often not quite correctly referred to as a Partition, Partition), and then creating a file system within which the components of any OS reside. The following is an algorithm for solving the problem of ordering a logical volume in relation to Windows, but the full description of the algorithm hosted on GitHub is compared with other operating systems.
The basic algorithm described here is based on two principles:
')
1. The use of "natural sorting" on a unique, "genetic" property acquired by objects-children from objects-parents.
2. Calculation of the “address” of an object, carrier of detailed information about an object that is one level from the parent, based on the “genetic code” of the parent object.
Each object, one level from the parent, acquires a number of unique properties that distinguish it from other objects generated by the same parent, such as: date and time of birth, unique character identifier, unique numeric identifier, symbolic, generic name, technical characteristics related to the volume of stored data, etc.
In order to avoid collisions, if two devices with absolutely identical identifiers assigned by equipment manufacturers appear in the system, each such identifier when the device first appears in the system is tied with a “tag with a number”.
Manufacturers that produce hard drives, flash drives, DVD and CD drives of different subclasses (internal, external, virtual, read only, read and write, with a choice of storage media), Tape Drives, Floppy drives.
Manufacturers of equipment (Manufactures), endow their products with a unique, non-destructible and existing since the release for the lifetime, identifier. The identifier, called in the system "PnPDeviceID", is represented by a rather long text string, divided into subgroups by the symbol "&". The subgroups contain the name of the manufacturer, the name of the specific product, the version number, the class of the product, and more.
As soon as any of the storage devices was first recognized by a specific operating system, the corresponding device (with one exception) acquires another unique, substantially shorter and strictly formalized identifier called the GUID. The GUID is 42 ASCII characters of which 6 characters are service characters. In this connection, only 32 hex characters are immediately significant, immediately converted by the system into an 8-byte number, QWORD, according to a certain algorithm. These eight-byte numbers using the system hashing algorithm are further used for “direct access” to the corresponding objects and for the ordering of objects by creating enums.
An exception. At least one of the storage devices that is not assigned a GUID is the device class with the generic name “DVD-ROM”, served in the Windows environment of any editions and editions by the driver “cdrom”, HKLM \ SYSTEM \ CurrentControlClass \ Services \ cdrom \ Enum .
For such devices, the OS-assigned PnPDeviceID is the only device identifier in the system.
Windows does exactly the same thing as babysitters in maternity hospitals, tying a tag to a newborn's hand: the OS also assigns a tag with a number to the identifier from the manufacturer in case the OS has to recognize and assign another similar device to PnPDeviceID manufacturer. This "tag with the number" is assigned through the standard delimiter "&" last. Thus, it is guaranteed that there will never be two devices in the system with exactly the same PnPDeviceID.
PnPDeviceID is created absolutely for all data storage devices that were first recognized by the system. But for all devices other than “DVD-ROM”, as mentioned above, the system also creates a GUID. How, in this case, do the GUIDs differ for two devices with exactly the same identifiers from the manufacturer, where does the tag with the number in the GUID hang? The “tag with the number” is the last two hex characters of the first GUID field. A more detailed explanation will be given below when comparing the program reports in the environment 8.1 and Windows 10 RTM TH1.
For logical volumes:
Volume Serial Number, SerialNumber . Assigned to the OS absolutely all devices logical volumes, including even virtual "DVD-ROM". The serial number is represented by 8 hexadecimal characters. There are possible collisions in this field that cannot be eliminated, and the system does not attempt to do this, since there is no need for that. The serial number "00000000" is acquired by all logical volumes that have been fully encrypted (Encrypted) in one way or another, and the system cannot read the serial number of the volume until the volume is mounted with the decoding code. Thus, 8 zeros in the SerialNumber field of a logical volume confidently indicate that this volume is encrypted.
For storage devices:
Serial number of the device, SerialNumber . It is assigned by the device manufacturer. 8 hex characters. It is stored in the system even for devices, the only logical volume on which was encrypted in one way or another.
Signature drive, Signature . It is assigned by the device manufacturer. 8 hex characters.
All OSs block the display in the disk signature system if Gpt-formatted partitions are located on the disk. This is undoubtedly a system trick, which allows, without using low-level disk I / O operations, by the presence or absence of a disk signature, determine the Style (Format) of formatting partitions on the disk: Mbr / Gpt. Very elegantly, this is demonstrated in the disk properties stored in HKLM \ HARDWARE \ DESCRIPTION \ System \ MultifunctionAdapter \ 0 \ DiskController \ 0 \ DiskPeripheral, where the property "Identifier" = "9cb5ff90-00000000-A" is stored. 8 zeros, undoubtedly specially recorded by the OS in place of the real disk signature, indicate that the partitions on the disk have the Gpt formatting style.
A small JavaScript code, WhoIsFaster.js, sequentially launched for execution (WShell.Exec) command lines corresponding to the execution of EnumDevicesAndVolumes.wsf and DISKPART.EXE. During the execution of both programs, the lines that were output by the programs on StdOut were read and the lines read were buffered in order to measure the CPU execution time with the utmost precision. Measurements were made with an accuracy of milliseconds and seconds and milliseconds appear everywhere in the tables.
Unfortunately, these figures do not only reflect CPU time: EnumDevicesAndVolumes.wsf, after completing its main work and outputting all reports, created in the current directory also the input file used in the command line to launch DISKPART.EXE. So, the time spent on disk I / O should be added to the CPU time used by both programs. Since the write time on the disc is obviously longer than the read time, DISKPART.EXE has some advantage over this parameter.
Thinkpad R500, 2.4Gz, 8 Gb RAM, ATI Mobility Radeon HD 3400, 1650x1080, two internal drives. The first, main, four sections. The second, two sections.
Windows 7 Enterprise Evaluation. Installed only Total Commander and Free Javascript Editor. The same programs are installed in other systems.
Windows 8.1: MS Office 2013, Acronis True Image 2015, Acronis Disk Director 12, a pair of AOMEI programs for creating backups and for partition maintenance. Only those applications that list their own driver filters that create enumerations in HKLM \ SYSTEM \ CurrentControlSet \ Services are listed.
Windows 10: starting with Technical Preview Build 10049, when it became possible to update Windows 8.1 without losing the installed application programs and their settings, the current 8.1 version was updated. In the future, Windows 10 has undergone updates with all officially released assemblies, and therefore the composition of the application software in the 9600 and 10240 environments is completely the same.
Competitive results in the environments of all three editions of Windows are quite close. We can only note that in the Windows 10 environment, the speed of the prototype code is more affected by parallel-running browsers with a large number of open pages, MS Office 2013 Word, which automatically starts the synchronization service with OneDrive, than in previous editions. Therefore, the "competition" has always been held on an equal footing, immediately after the launch of Windows.
How can we explain the significantly lower speed of DISKPART.EXE in comparison with the interpreted code EnumDevicesAndVolumes.wsf in the Windows 8.1 environment? There is only one, unsubstantiated explanation. As already mentioned, for all storage devices and data volumes and logical volumes created on them, the system uses QWORD keys (8 bytes) to work with hash tables.
For the same purpose, the described algorithm uses only the Field Field 1 GUID, which is converted by the system into a QWORD. There is not enough knowledge and data to assess the dependence of the access speed to the system hash table, but it appears that this dependence is non-linear and, at best, inversely proportional to N * log (N), where N is the key length in bits or bytes. Thus, it is the short keys used by the described algorithm that can explain the lag of DISKPART.EXE.
Before the advent of Windows 10 RTM TH1 Build 10240, the competitive results in the environment of various assemblies only slightly differed from those in environment 8.1. However, in the build environment 10240, the key enumeration algorithm was fundamentally changed
HKU \ SID \ Software \ Microsoft \ Windows \ CurrentVersion \ Explorer \ MountPoints2 \ CPC \ Volume: if starting from 7601 and ending with 10166 “children went families,” that is, all logical volumes created on the same physical disk strictly followed one after another in ascending order of displacement from the beginning of the disk, then the “natural” ordering of logical volumes in which the volumes are listed strictly in the order of their mounting in the system was introduced for the first time in environment 10240. This change was supposed to speed up the system with logical volumes. DISKPART.EXE does not seem to use this enumeration yet and still pushes the devices serviced by the cdrom driver into the first rows.
Picture 1
It is this output of the information about logical volumes by the program DISKPART.EXE that was the “task to follow” and the creation of a fast solution algorithm. The pictures 2 and 3 below are one of the many reports created by EnumDevicesAndVolumes.wsf. These are the shortest reports created by EnumDevicesAndVolumes.wsf. Nevertheless, even this report contains more information than the above DISKPART report and does not contain meaningless information, as in the Status column: it is natural that all volumes are healthy, otherwise they would have to deal with their treatment, rather than competitions in solving the problem.
Figure 2
Figure 3
Figure 2 presents a brief report of EnumDevicesAndVolumes.wsf in the Windows 8.1 environment, and a very similar Figure 3 presents a similar report in the Windows 10 RTM TH1 environment. The difference is found only in the values ​​of the F1 fields: pay attention to “714ce4NN” and you will notice that only the last two characters provide DevGUID.F1 distinction for different Mbr-formatted disks, SD-card and partitions of the first of two Gpt-formatted VHDs. Moreover, different VolGUID.F1, corresponding to sections on Mbr-formatted disks, have the same format. But in Windows 10, where, as already mentioned, the VolumeGUID creation algorithms were changed, “714ce4NN” was assigned to only two volumes, one on the first disk, the System Reserved label and one on the second disk, the TOSH-MK1646GSX label. A more detailed analysis of the detection of “genetic kinship” of various GUIDs, the EnumDevicesAndVolumes.wsf JS script, presents in a specially crafted report created by the ShowResemblanse () method.
I will explain the use of “Windows Registry” instead of “System Registry” by the fact that in my view the Russian word “registry” is similar to “barn book” and calls it “flat file”, and not a hierarchical database, which is Windows Registry.
Why the “prototype code”? Initially, in imitation of DISKPART.EXE, it was planned to write the FAD code, “Fast And Dirty”, but life and Microsoft were first forced to remove the word Fast, and then I decided to make the code cleaner and more suitable for fast rewriting in C, C ++, C #. But still, the code remains a PROTOTYPE in the sense that it does not provide any functionality with respect to objects placed by the code in three collections.
In the second part, it is planned to describe the four steps of the algorithm, the first three of which strictly follow the two principles proclaimed at the beginning of this publication. Each of the first three steps begins with the reading of some enumeration, continues with the extraction of detailed properties from some “garbage can” and ends with the placement of detailed objects endowed with all the necessary properties in the corresponding collection.
However, those who wish can, without waiting for the second part, see and download EnumDevicesAndVolumes.wsf, WhoIsFaster.js by the link:
https://github.com/sysprg-46/EnumerateDevicesAndVolumesWin/tree/master
There are also full descriptions in Russian in the DOCX and PDF formats, as well as screenshots present “long” competitive cycles, 10-15 runs each in Windows 7, Windows 8.1 and Windows 10 environments.
An algorithm is described whose implementation in JavaScript prototype code confidently ahead of the time required for solving the problem is the DISKPART.EXE system reference utility. The principles on which the algorithm is based are described. A possible explanation, but not proof, is given to why DISKPART.EXE is slower than JavaScript code. Contest results are given in various editions of Windows, including Windows 10 RTM TH1. Described as changes made in various editions of Windows 10 forced several times to rework the algorithm in order to increase its reliability, although at the cost of some loss of speed.
Introduction
Logical volumes underlie any OS. As long as there are no logical volumes, the system simply has nowhere to place. Preparing a logical volume involves allocating space on a physical storage device (that is, creating a data volume, Storage # Volume, often not quite correctly referred to as a Partition, Partition), and then creating a file system within which the components of any OS reside. The following is an algorithm for solving the problem of ordering a logical volume in relation to Windows, but the full description of the algorithm hosted on GitHub is compared with other operating systems.
Principles on which the described algorithm is based
The basic algorithm described here is based on two principles:
')
1. The use of "natural sorting" on a unique, "genetic" property acquired by objects-children from objects-parents.
2. Calculation of the “address” of an object, carrier of detailed information about an object that is one level from the parent, based on the “genetic code” of the parent object.
Each object, one level from the parent, acquires a number of unique properties that distinguish it from other objects generated by the same parent, such as: date and time of birth, unique character identifier, unique numeric identifier, symbolic, generic name, technical characteristics related to the volume of stored data, etc.
In order to avoid collisions, if two devices with absolutely identical identifiers assigned by equipment manufacturers appear in the system, each such identifier when the device first appears in the system is tied with a “tag with a number”.
Identification of storage devices by equipment manufacturers and operating systems
Manufacturers that produce hard drives, flash drives, DVD and CD drives of different subclasses (internal, external, virtual, read only, read and write, with a choice of storage media), Tape Drives, Floppy drives.
Manufacturers of equipment (Manufactures), endow their products with a unique, non-destructible and existing since the release for the lifetime, identifier. The identifier, called in the system "PnPDeviceID", is represented by a rather long text string, divided into subgroups by the symbol "&". The subgroups contain the name of the manufacturer, the name of the specific product, the version number, the class of the product, and more.
As soon as any of the storage devices was first recognized by a specific operating system, the corresponding device (with one exception) acquires another unique, substantially shorter and strictly formalized identifier called the GUID. The GUID is 42 ASCII characters of which 6 characters are service characters. In this connection, only 32 hex characters are immediately significant, immediately converted by the system into an 8-byte number, QWORD, according to a certain algorithm. These eight-byte numbers using the system hashing algorithm are further used for “direct access” to the corresponding objects and for the ordering of objects by creating enums.
An exception. At least one of the storage devices that is not assigned a GUID is the device class with the generic name “DVD-ROM”, served in the Windows environment of any editions and editions by the driver “cdrom”, HKLM \ SYSTEM \ CurrentControlClass \ Services \ cdrom \ Enum .
For such devices, the OS-assigned PnPDeviceID is the only device identifier in the system.
Resolution of collisions in the Windows environment
Windows does exactly the same thing as babysitters in maternity hospitals, tying a tag to a newborn's hand: the OS also assigns a tag with a number to the identifier from the manufacturer in case the OS has to recognize and assign another similar device to PnPDeviceID manufacturer. This "tag with the number" is assigned through the standard delimiter "&" last. Thus, it is guaranteed that there will never be two devices in the system with exactly the same PnPDeviceID.
PnPDeviceID is created absolutely for all data storage devices that were first recognized by the system. But for all devices other than “DVD-ROM”, as mentioned above, the system also creates a GUID. How, in this case, do the GUIDs differ for two devices with exactly the same identifiers from the manufacturer, where does the tag with the number in the GUID hang? The “tag with the number” is the last two hex characters of the first GUID field. A more detailed explanation will be given below when comparing the program reports in the environment 8.1 and Windows 10 RTM TH1.
Additional unique properties of storage devices
For logical volumes:
Volume Serial Number, SerialNumber . Assigned to the OS absolutely all devices logical volumes, including even virtual "DVD-ROM". The serial number is represented by 8 hexadecimal characters. There are possible collisions in this field that cannot be eliminated, and the system does not attempt to do this, since there is no need for that. The serial number "00000000" is acquired by all logical volumes that have been fully encrypted (Encrypted) in one way or another, and the system cannot read the serial number of the volume until the volume is mounted with the decoding code. Thus, 8 zeros in the SerialNumber field of a logical volume confidently indicate that this volume is encrypted.
For storage devices:
Serial number of the device, SerialNumber . It is assigned by the device manufacturer. 8 hex characters. It is stored in the system even for devices, the only logical volume on which was encrypted in one way or another.
Signature drive, Signature . It is assigned by the device manufacturer. 8 hex characters.
All OSs block the display in the disk signature system if Gpt-formatted partitions are located on the disk. This is undoubtedly a system trick, which allows, without using low-level disk I / O operations, by the presence or absence of a disk signature, determine the Style (Format) of formatting partitions on the disk: Mbr / Gpt. Very elegantly, this is demonstrated in the disk properties stored in HKLM \ HARDWARE \ DESCRIPTION \ System \ MultifunctionAdapter \ 0 \ DiskController \ 0 \ DiskPeripheral, where the property "Identifier" = "9cb5ff90-00000000-A" is stored. 8 zeros, undoubtedly specially recorded by the OS in place of the real disk signature, indicate that the partitions on the disk have the Gpt formatting style.
Run results running on different versions of Windows
| Windows 10 RTM TH1 Build 10240 | ||
| N | EnumDevicesAndVolumes.wsf | DISKPART.EXE |
| one | 2.140 | 6.235 |
| 2 | 1.452 | 2.936 |
| 3 | 2.530 | 2.953 |
| four | 2.541 | 2.867 |
| five | 1.448 | 2.905 |
| Windows 8.1 Build 9600 | ||
| N | EnumDevicesAndVolumes.wsf | DISKPART.EXE |
| one | 1.243 | 5.274 |
| 2 | 1.222 | 2.558 |
| 3 | 1.218 | 1.289 |
| four | 1.200 | 1.379 |
| five | 1.379 | 1.425 |
| Windows 7 SP1 Build 7601 | ||
| N | EnumDevicesAndVolumes.wsf | DISKPART.EXE |
| one | 1.406 | 11.913 |
| 2 | 1.319 | 2.130 |
| 3 | 1.338 | 2.662 |
| four | 1.310 | 2.788 |
| five | 1.287 | 2.698 |
A small JavaScript code, WhoIsFaster.js, sequentially launched for execution (WShell.Exec) command lines corresponding to the execution of EnumDevicesAndVolumes.wsf and DISKPART.EXE. During the execution of both programs, the lines that were output by the programs on StdOut were read and the lines read were buffered in order to measure the CPU execution time with the utmost precision. Measurements were made with an accuracy of milliseconds and seconds and milliseconds appear everywhere in the tables.
Unfortunately, these figures do not only reflect CPU time: EnumDevicesAndVolumes.wsf, after completing its main work and outputting all reports, created in the current directory also the input file used in the command line to launch DISKPART.EXE. So, the time spent on disk I / O should be added to the CPU time used by both programs. Since the write time on the disc is obviously longer than the read time, DISKPART.EXE has some advantage over this parameter.
Hardware platform
Thinkpad R500, 2.4Gz, 8 Gb RAM, ATI Mobility Radeon HD 3400, 1650x1080, two internal drives. The first, main, four sections. The second, two sections.
Applications installed on different versions of Windows
Windows 7 Enterprise Evaluation. Installed only Total Commander and Free Javascript Editor. The same programs are installed in other systems.
Windows 8.1: MS Office 2013, Acronis True Image 2015, Acronis Disk Director 12, a pair of AOMEI programs for creating backups and for partition maintenance. Only those applications that list their own driver filters that create enumerations in HKLM \ SYSTEM \ CurrentControlSet \ Services are listed.
Windows 10: starting with Technical Preview Build 10049, when it became possible to update Windows 8.1 without losing the installed application programs and their settings, the current 8.1 version was updated. In the future, Windows 10 has undergone updates with all officially released assemblies, and therefore the composition of the application software in the 9600 and 10240 environments is completely the same.
Interpretation of results
Competitive results in the environments of all three editions of Windows are quite close. We can only note that in the Windows 10 environment, the speed of the prototype code is more affected by parallel-running browsers with a large number of open pages, MS Office 2013 Word, which automatically starts the synchronization service with OneDrive, than in previous editions. Therefore, the "competition" has always been held on an equal footing, immediately after the launch of Windows.
How can we explain the significantly lower speed of DISKPART.EXE in comparison with the interpreted code EnumDevicesAndVolumes.wsf in the Windows 8.1 environment? There is only one, unsubstantiated explanation. As already mentioned, for all storage devices and data volumes and logical volumes created on them, the system uses QWORD keys (8 bytes) to work with hash tables.
For the same purpose, the described algorithm uses only the Field Field 1 GUID, which is converted by the system into a QWORD. There is not enough knowledge and data to assess the dependence of the access speed to the system hash table, but it appears that this dependence is non-linear and, at best, inversely proportional to N * log (N), where N is the key length in bits or bytes. Thus, it is the short keys used by the described algorithm that can explain the lag of DISKPART.EXE.
Before the advent of Windows 10 RTM TH1 Build 10240, the competitive results in the environment of various assemblies only slightly differed from those in environment 8.1. However, in the build environment 10240, the key enumeration algorithm was fundamentally changed
HKU \ SID \ Software \ Microsoft \ Windows \ CurrentVersion \ Explorer \ MountPoints2 \ CPC \ Volume: if starting from 7601 and ending with 10166 “children went families,” that is, all logical volumes created on the same physical disk strictly followed one after another in ascending order of displacement from the beginning of the disk, then the “natural” ordering of logical volumes in which the volumes are listed strictly in the order of their mounting in the system was introduced for the first time in environment 10240. This change was supposed to speed up the system with logical volumes. DISKPART.EXE does not seem to use this enumeration yet and still pushes the devices serviced by the cdrom driver into the first rows.
Visual presentation of the results of solving the problem
Picture 1
It is this output of the information about logical volumes by the program DISKPART.EXE that was the “task to follow” and the creation of a fast solution algorithm. The pictures 2 and 3 below are one of the many reports created by EnumDevicesAndVolumes.wsf. These are the shortest reports created by EnumDevicesAndVolumes.wsf. Nevertheless, even this report contains more information than the above DISKPART report and does not contain meaningless information, as in the Status column: it is natural that all volumes are healthy, otherwise they would have to deal with their treatment, rather than competitions in solving the problem.
Figure 2
Figure 3
Figure 2 presents a brief report of EnumDevicesAndVolumes.wsf in the Windows 8.1 environment, and a very similar Figure 3 presents a similar report in the Windows 10 RTM TH1 environment. The difference is found only in the values ​​of the F1 fields: pay attention to “714ce4NN” and you will notice that only the last two characters provide DevGUID.F1 distinction for different Mbr-formatted disks, SD-card and partitions of the first of two Gpt-formatted VHDs. Moreover, different VolGUID.F1, corresponding to sections on Mbr-formatted disks, have the same format. But in Windows 10, where, as already mentioned, the VolumeGUID creation algorithms were changed, “714ce4NN” was assigned to only two volumes, one on the first disk, the System Reserved label and one on the second disk, the TOSH-MK1646GSX label. A more detailed analysis of the detection of “genetic kinship” of various GUIDs, the EnumDevicesAndVolumes.wsf JS script, presents in a specially crafted report created by the ShowResemblanse () method.
Concluding remarks to the first part of the publication
I will explain the use of “Windows Registry” instead of “System Registry” by the fact that in my view the Russian word “registry” is similar to “barn book” and calls it “flat file”, and not a hierarchical database, which is Windows Registry.
Why the “prototype code”? Initially, in imitation of DISKPART.EXE, it was planned to write the FAD code, “Fast And Dirty”, but life and Microsoft were first forced to remove the word Fast, and then I decided to make the code cleaner and more suitable for fast rewriting in C, C ++, C #. But still, the code remains a PROTOTYPE in the sense that it does not provide any functionality with respect to objects placed by the code in three collections.
In the second part, it is planned to describe the four steps of the algorithm, the first three of which strictly follow the two principles proclaimed at the beginning of this publication. Each of the first three steps begins with the reading of some enumeration, continues with the extraction of detailed properties from some “garbage can” and ends with the placement of detailed objects endowed with all the necessary properties in the corresponding collection.
However, those who wish can, without waiting for the second part, see and download EnumDevicesAndVolumes.wsf, WhoIsFaster.js by the link:
https://github.com/sysprg-46/EnumerateDevicesAndVolumesWin/tree/master
There are also full descriptions in Russian in the DOCX and PDF formats, as well as screenshots present “long” competitive cycles, 10-15 runs each in Windows 7, Windows 8.1 and Windows 10 environments.
Source: https://habr.com/ru/post/264019/
All Articles