Sunday, 17 May 2015 00:00

Development: Java RE 7. Fixing finally the Registry bug!

Written by 

So in the previous Blogpost we were able to replicate the issue with a local testcase. Amazing! Now it's time to discover what's really going on, and hence create a fix! Let's fix once and for all this registry nightmare corruption!


Some background first...

First, in short words so you can follow me, the registry memory structure is divided into "leaves". When one "leaf" is full of data, another "leaf" is created.

So the memory structure when creating just a couple of registry keys would look like this:

----------------- Leaf1 -----------...-----
Child1 Child2 Child3 Child4 Child5


And when we reach the limit of the Leaf1 and we add one more child, we would have something like:

----------------- Leaf1 -----------...----------
Child1 Child2 Child3 Child4 Child5 ... Child4999

----------------- Leaf2 -----------...----------
Child5000



What Happens In ReactOS?

As you can see a new leaf has been created since there is no more storage in Leaf1.
The problem arises when the next child is added:

----------------- Leaf1 -----------...----------
Child1 Child2 Child3 Child4 Child5 ... Child4999

----------------- Leaf2 -----------...----------
Child5001 Child5000


And if we add one more:

----------------- Leaf1 -----------...----------
Child1 Child2 Child3 Child4 Child5 ... Child4999

----------------- Leaf2 -----------...----------
Child5002 Child5001 Child5000


Do you see what's going on? They're not properly sorted! Leaf2 should look like, instead:

----------------- Leaf2 -----------...----------
Child5000 Child5001 Child5002


ReactOS, when there is just one Leaf, uses the CmpFindSubKeyInLeaf api to find the Subkey. This API does not need the keys to be sorted at all in the Leaf1, since it compares one by one all the memory entries to retrieve the proper Subkey in the Leaf. Not too efficient, but well, it was working nicely.

The first test we created, the one which was adding and deleting just one key, obviously was not forcing the creation of a second Leaf, so the bug was not shown at all.

However, the second test was creating, first, 10.000 Childs (and hence forcing a new Leaf to be created) and afterwards deleting the entries. This wouldn't be an issue if CmpFindSubKeyInLeaf was still used to find the Subkey, let's say Child5002, since this API does not need keys to be sorted.


Then where is the bug?

The memory structure was looking like:

----------------- Leaf1 -----------...----------
Child1 Child2 Child3 Child4 Child5 ... Child4999

----------------- Leaf2 -----------...----------
Child5002 Child5001 Child5000


The issue with CmpFindSubKeyInLeaf is that it's obviously non-efficient at all. It can work if you have just one leaf, however if you have 10 Leaves, you would be wasting too much cycles just to find a Key since it compares each key one by one. Imagine going through 9997 Childs to discover that the subkey needed is in Child9998.

That's the reason ReactOS uses a different API when more than one leaf are present in memory: CmpCompareInIndex


The Awesome CmpCompareInIndex...

CmpCompareInIndex is used inside a binary-search algorithm. A binary-search algorithm needs by definition to have all the items in the leaves properly sorted.
This binary search algorithm begins using the last value of the Leafs to know in which Leaf it has to check for the value.

Imagine the case we are searching for "Child2000", our binary search algorithm checks that the ending values in Leaf1 is Child4999, so it then checks inside that leaf by splitting the range in half. Since the values are properly sorted, then, the "Child2000" is, after some iterations, properly found.

Now, imagine the case we are searching for "Child5001", well, it checks the Leaf1 ending value and discovers it is "Child4999", so the algorithm discards Leaf1 because Child5001 is a bigger value. Then it checks Leaf2 ending value to discover it is "Child5000" (Remember: bugged sorting!), so it does not find a "proper" place where to add/delete the new value. Or worse, it does: Corrupting the registry! Voila!

The Fix

The first fix created was to avoid using the CmpCompareInIndex, and using CmpFindSubKeyInLeaf instead, even if there was more than one leaf. This patch was created mainly as a workaround (it was not too efficient) until proper sorting were implemented, and also to find if our guess was correct or not.

Thankfully, the guess was correct and we were able to install JRE 7 without any issues!
Once we confirmed the bug, Zefklop committed a fix to sort the Childs correctly, since as you can see they were not so messed, and voila! he fixed the latest issue of the JRE 7 installer!

This one issue took too many hours, Devs and Testers to track it down.. but that has enhanced ReactOS stability as a whole.


Did I say this is the latest bug in JRE7 installer?

Nope. I lied.
There was one more annoying bug, but...it'll have to wait until next post... ;)


Víctor Martínez

Víctor Martínez is the current ReactOS PR Team coordinator focused in partnerships and win-win strategies. After funding his own strategy company, he has been working as an operations and strategy advisor for several companies based in Russia, USA, and Europe. When he is not transforming Weakness into Revenue Streams, he is messing and breaking ReactOS Code.

Leave a comment

Make sure you enter the (*) required information where indicated. HTML code is not allowed.