Re: Approximate structure-allocation limit problem improvement

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Mon, Dec 21, 2015 at 04:18:56PM +0100, Colin Pitrat wrote:
> In fact, my point is exactly that we don't want to compare against
> zero, we're just doing it to not underflow our counters ! That's why
> in the code of the "Approximate structure-allocation limit problem",
> sub_count handles 0 in a way that is symmetrical to the way add_count
> handles the allocation limit that we want to enforce.
> 
> The issue is that it raise the following question: what to do when
> both the thread counter (_ counter _) and the globalized counter (_
> global_count _) are too small to substract delta ? It necessarly means
> that some other thread counter is non-zero and the sum of all counters
> is greater than delta, as we know a structure of size delta is still
> allocated.
> 
> This issue is highlighted in the book in paragraph 5.3.3 Simple Limit
> Counter discussion, with the sentence "Similarly, sub_ count() can
> fail even when the aggregate value of the counter is nowhere near
> zero."
> 
> For example, just after program starts (all counters are 0): thread A
> allocates a structure of size 10. Counter of thread A is 10, global
> counter and counter of thread B are both 0. The structure ownership is
> passed to thread B that wants to deallocate it. But sub_count finds
> that thread B counter is 0 so it takes the slow path, checking global
> counter that is also 0. It therefore fails. What should the program do
> in this case ? Keep the structure and try to deallocate it later ?
> 
> My proposition is to add a global "deallocated_size". In the slow path
> of sub_count, if delta cannot be substracted then it is added to
> deallocated_size and sub_count always succeeds. On the next
> globalize_count, deallocated_size will be reduced as much as possible.
> 
> Are my explanation clearer (sorry if not !) ? Am I missing a flow with
> this proposal ?

This explanation is very clear, thank you!  I had forgotten that the
solution in the book checks for both zero and the limit.

I would welcome a patch containing code and text for a solution that
checks only the limit.  The current solution could then be placed in
the answer to a Quick Quiz that asked about checking for limits and
also checking for bugs due to underflow (which might happen due to
double free -- though to your point, there are better ways of checking
for double free).

							Thanx, Paul

> Regards,
> Colin
> 
> 2015-12-18 19:03 GMT+01:00 Paul E. McKenney <paulmck@linux.vnet.ibm.com>:
> > On Wed, Dec 16, 2015 at 02:21:45PM +0100, Colin Pitrat wrote:
> >> Hello,
> >>
> >> in chapter 5 (Counting), in the paragraph concerning "Approximate
> >> structure-allocation limit problem", it is said:
> >>
> >> "Similarly, sub_count() can fail even when the aggregate value of the
> >> counter is nowhere near zero. In many cases, this is unacceptable."
> >>
> >> In the case of the Quick Quiz 5.3 question, it's true that it's quite
> >> a problem if it means freeing the structure fails because the counter
> >> cannot be updated ! And freeing it without updating the counter means
> >> the counter shifts from reality.
> >>
> >> However, the very existence of the structure is a guarantee that the
> >> real (total) counter value cannot be 0 or less than delta, so couldn't
> >> we imagine to always succeed the sub_count operation by keeping a
> >> global negative offset ? In the slow path, after globalize_count, if
> >> the global count is lower than delta then we set it to 0 and we
> >> increment the negative offset by what remains.
> >>
> >> On the next slow path operation during a add_count, this negative
> >> offset can be removed (or reduced) by reducing the local counter of
> >> the thread by the same value.
> >>
> >> This improvement over the proposed solution make it an acceptable
> >> answer for the quick quiz 5.3 whereas it isn't without.
> >>
> >> What do you think ?
> >> Should I spend a bit of time writing a paragraph and a code sample about it ?
> >
> > I must confess that I have read this message a few times, and still don't
> > understand what you are getting at.  Part of my trouble is that I am
> > not sure why you are comparing against zero -- the structure-allocation
> > problem only needs to compare against the limit.  But you might mean
> > zero after offset, or you might be talking about some related problem.
> >
> > So perhaps a paragraph and sample code would help me understand the
> > problem you are looking at and your example solution.
> >
> >                                                         Thanx, Paul
> >
>