Major Description
Due the investigations done to fix the JRE/JDK bug we've found the following statements:
1)The keys in the memory structure are not placed sorted, but they are placed in a descendent order.
2) So when a new entry is added,which forces a split, the entry is placed incorrectly in the wrong leaf.
The memory dump before inserting the entry which forces a split is:
***** Non splitted list *****
|
Parent -> 1 Items
|
--List[0] (0x8000c020) -> 1012 Items
|
----List[0][0] (0x80000180) = "Child1012"
|
----...
|
----List[0][1011] (0x8000b860) = "Child1"
|
Here we can see how the "ChildXXXX" are placed in memory in a descendent order in just one "leaf"(List[0])
The expected order should be:
***** Non splitted list *****
|
Parent -> 1 Items
|
--List[0] (0x8000c020) -> 1012 Items
|
----List[0][0] (0x80000180) = "Child1"
|
----...
|
----List[0][1011] (0x8000b860) = "Child1012"
|
This is the first bug.
Now, when the "Child1013" is created, we are forcing the split creating 2 leafs, Leaf1 being List[0] and Leaf2 being List[1]. The memory structure in ReactOS becomes as follows:
***** Splitted list *****
|
Parent -> 2 Lists(Leafs)
|
--List[0] (0x8000c020) -> 506 Items
|
----List[0][0] (0x80000180) = "Child1012"
|
----...
|
----List[0][505] (0x8000b860) = "Child0508"
|
|
|
--List[1] (0x8001a020) -> 508 Items
|
----List[1][0] (0x8000b800) = "Child0507"
|
----List[1][1] (0x800198c0) = "Child1013"
|
----List[1][2] (0x8000b7a0) = "Child0506"
|
----...
|
----List[1][507] (0x800001f0) = "Child0001"
|
As you can see, the List[0] goes downwards from Child1012 to Child0508, and the second leaf stores from "Child0507" to "Child001". The split is correctly done, however due to the previous bug we have wrongly "downwards" sorted the list
In the split, the entry is wrongly placed. Really it is following the correct logic as it places the "Child1013" entry AFTER the highest value in the 2nd leaf however,since the list is not correctly sorted, the highest value in the second leaf is not "Child1012" but "Child0507".
The expected sorted ordering is:
Parent -> 2 Lists(Leafs)
|
--List[0] (0x8000c020) -> 506 Items
|
----List[0][0] (0x800001f0) = "Child0001"
|
----List[0][0]
|
----...
|
----List[0][505] (0x8000b800) = "Child0507"
|
|
|
--List[1] (0x8001a020) -> 508 Items
|
----List[1][0] (0x8000b860) = "Child0508"
|
----...
|
----List[1][506] (0x80000180) = "Child1012"
|
----List[1][507] (0x800198c0) = "Child1013"
|
Basically, what it's failing is:
- Adding a entry thinking the list is already sorted when it is not. Hence it is incorrectly placed in the wrong leaf, and much worse, the Cmp....Index functions are prone to assert since they need a sorted list to work correctly otherwise the binary search wont work.