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 ? 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
