Fix compilation errors.

Correct bounds check, where one was added when it should have been subtracted.

In D37716#857745, @hselasky wrote:

I assume you test compile before committing. Looks good!

Change usages of _RB_LINK to reorder the three pointers in RB_ENTRY to match the order in stable/13.

Rewrite the rb_remove code for greater clarity. Add more to the comment before find_space updates start_gap, to make clear why a->size does not matter there.

Don't 'fix' the start_gap hint until the next find_space. If an insert or removal leaves it at the root of a subtree with no usable gaps, a climb-up on the next find_space will fix it.

Change how counting happens in loops.

Update after many iommu_gas.c changes.

Remove the tree changes that have been checked in.

With DIAGNOSTIC defined, verify that the user of RB_INSERT_{PREV,NEXT} is using it properly.

Resolve conflict with recent commit.

Add comments.

Offer an RB_NEXT compromise.

In D36743#834240, @asomers wrote:

In D36743#834236, @dougm wrote:

In D36743#834231, @asomers wrote:

It looks like your version will result in more sequential oid numbers. But I don't see how the old version could create a duplicate. Could you please explain?

After your change, when the first oid_number tried is found to be in use, you usually increment the oid_number and use it, assuming that it is not also in use. Before your change, when the first oid-number tried is found to be in use, the code usually incremented the old number and iterated, to check whether that number was in use, and kept doing so until it found a number not in use. So, you have introduced a bug, which I am trying to address, by making sure that the oid_number is not in use.

Oh, I see. I missed a goto retry. If you move that out of the if block then that would also fix the problem.

In D36743#834231, @asomers wrote:

It looks like your version will result in more sequential oid numbers. But I don't see how the old version could create a duplicate. Could you please explain?

Resolve conflict with updated tree.h comments.

Use RB_INSERT_NEXT and RB_INSERT_PREV in more places.

Use INSERT_NEXT, INSERT_PREV macros.

Define insert_next and insert_prev tree operations, and use them to update the iommu_gas_entries tree.

Update after rb augment patch. Make start_gap point to the predecessor of the first empty gap that is big enough to hold a minimum allocation (1 page + 2 guards).

Apply recommended style change.

Accept suggestions. Add comment explaining why the 'end' entry must be the first one inserted into the new tree.

Apply kib's manpage fix.

Man page fix will go into the committed change.