One use for reference-count biases... [LWN.net]

One use for reference-count biases...

Posted Jun 9, 2009 4:36 UTC (Tue) by PaulMcKenney (subscriber, #9624)
Parent article: Linux kernel design patterns - part 1

One use for reference-count biases is where the reference count is modified often enough that it must be represented as a per-CPU variable, as can happen when the reference count represents the number of outstanding I/Os. However, unless the reference count tends to be much larger than the number of CPUs, you get no benefit from the per-CPU nature of the variable. Adding in a large bias, on the other hand, allows the counter to operate on a completely per-CPU basis under normal operating conditions.

This trick is useful in cases where it is only necessary to actually test the counter for zero-or-not in special situations, such as when attempting to remove or reconfigure the I/O device. When such a situation arises, one subtracts out the bias, and then runs inefficiently until the I/Os drain and the reference count goes to zero, at which point the device may be safely removed or reconfigured. The bias may be added back in to return to normal operating conditions.

A very specialized use of a reference count, perhaps, but one that has actually appeared in real code in past lives.

(Log in to post comments)

One use for reference-count biases...

Posted Jun 9, 2009 5:39 UTC (Tue) by neilbrown (subscriber, #359) [Link]

Yes, I wouldn't be surprised if reference counts that are spread across multiple per-cpu variables would have very different trade-offs and hence different Patterns to the more traditional kinds!

I'm having trouble picturing exactly how the counters you describe would work (and particularly exactly what happens when the per-cpu counter hits zero) but it seems possible that the "one bit of information" that I claim a bias stores would, in this case, be the bit "Someone cares about a precise total value" and that one bit could conceivably be stored in a read-mostly cache line that could be easily shared among multiple processors.

So the code might look like:

   if (dec_and_test(per_cpu_counter))
         if (__test_bit(flag_name, &flag_variable))
               do some costly cross-cpu thing;

Is there any chance that would achieve the same result?

It may well be a case where you don't want to pay the price of an extra bit though.

One use for reference-count biases...

Posted Jun 9, 2009 13:50 UTC (Tue) by PaulMcKenney (subscriber, #9624) [Link]

Hmmmm... I was thinking more in terms of something like the following:

preempt_disable(); if (per_cpu_counter > 0) per_cpu_counter++; else do some costly global-lock-and-variable thing preempt_enable();

But it has been a good ten years since I messed with this, so I should take another look at it.

In any case, I very much agree with your overall premise that higher-level primitives are a very great improvement over continually re-inventing the wheel, most especially for those wheels with a strong history of being re-invented badly!!!

One use for reference-count biases...

Posted Dec 23, 2011 5:30 UTC (Fri) by atiqure (guest, #81951) [Link]

hii.. i dnt know who r u but i need help... please tell me something about how to develop a kernel without using any source i just want to use programming language like c,c++,java and assembly language can i do that with these languages ..if yes then please tell me from where to start and how ...pls help it will be christmas gift for me from you ...