Re: [boost] [intrusive] Possible bug in bstree_algorithms.hpp

Subject: Re: [boost] [intrusive] Possible bug in bstree_algorithms.hpp
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2014-09-14 17:36:14

El 11/09/2014 22:56, Lars Hagström escribió:
> I've added more debugging to rbtree_best_fit.hpp in a fork of interprocess
> at github.com, DonOregano/interprocess.git
> Direct link to my patched file
> https://github.com/DonOregano/interprocess/blob/aba6893976f5be62eed0763c3036013fa3717694/include/boost/interprocess/mem_algo/rbtree_best_fit.hpp
>
> Anyway, among the additions are the checks that I think you wanted above,
> that shows that prev_block and next_block are always in the multiset, as
> per your email.
>
> I also added logs to every priv_allocate to check that the block that we're
> trying to deallocate has in fact been allocated (that it is not just some
> random block).
>
> I also print out m_prev_size and m_size, and they're not obviously
> corrupted by randomness, they contain 4s and 0s etc, not wierd numbers...
> That doesnt really prove anything, though...
>
> I also added a check to make sure that block is not in the multiset, which
> it is not.
>
>
> Just a couple of stupid questions: Are we certain that check() is correct?

No. It's new code and it might have bugs.

> And should the invariants hold midway through priv_deallocate? Just so that
> I've not inserted checks that are not meant to hold in that place and that
> this thing is a red herring?

I realized that once the size of a inserted block is modified tree 
invariants might be broken because imultiset is ordered by size. Tree 
invariants should be checked before the end of the function, after 
m_imultiset is fixed with erase+insert or replace, when tree invariants 
should have been restored. Maybe the code is confusing but the idea is 
to avoid removing (and rebalancing) the tree if it's not strictly 
needed. I guess code could be simplified to be more readable and 
maintainable (I've improved readability a bit in the last commits). 
Remove checks after size modification and add it at the end the function.

> Below is the output produced by my program, with the logs added, and even
> further down (sorry) is the stacktrace from the failed check() call.

Thanks. Please remove the checks between size modification and the end 
of the function and try again.

> *ugh*. What can we do to make this debugging easier? It feels a bit
> inefficient...
> I could set up a VM on for example Digital Ocean and get everything up and
> running, and give you the password and some instructions?

That would be quite efficient, yes ;-)

Best,

Ion