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@xxxxxxxxxxxxxxxxxx>: > > 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 > > > -- To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
