LWN: Comments on "Linux kernel design patterns - part 1"

It's a comma operator.

alison — 2012-04-15T23:47:57+00:00

Posted Jun 11, 2009 0:56 UTC (Thu) by xoddam notes
"the infamous http://en.wikipedia.org/wiki/Comma_operator".

Humorously, I just had a look at the Wikipedia article. "Huh, I thought I understood the comma operator!" Copied the code in question out, compiled and tested it, and sure enough the latest revision to the article was erroneous. So yeah, I guess the Comma Operator causes some confusion!

-- Alison

One use for reference-count biases...

atiqure — 2011-12-23T05:30:26+00:00

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

Linux Kernel Design Patterns - Part 1

smitty_one_each — 2009-06-12T12:39:09+00:00

Luke Palmer, Dana:
http://lukepalmer.wordpress.com/2009/06/12/the-role-of-a-...

Linux Kernel Design Patterns - Part 1

intgr — 2009-06-12T12:05:50+00:00

> Sometimes I dream of a kernel written in a high-level programming language...
There are many such projects, including Inferno from Bell Labs, Singularity from Microsoft (!) and a whole lot of others.
It's an interesting research area because it completely throws away decades-old CPU memory protection, because typesafe virtual machines guarantee that you can't access anything you don't have a reference to.

Obviously none of these is usable as a desktop OS though.

Linux Kernel Design Patterns - Part 1

marcH — 2009-06-11T14:41:48+00:00

<troll>
Ha! Now I know why kernel development is an order of magnitude harder than developing user level applications. This is not just the intrinsic problem of most bugs crashing the whole system. This is also the problem that advanced software engineering concepts like code reuse are only starting to reach these shores!
</troll>

Just for fun: http://lwn.net/Articles/306843/

Sometimes I dream of a kernel written in a high-level programming language...

It's a comma operator.

xoddam — 2009-06-11T00:56:15+00:00

This is C. In C, we have many ways of camouflaging incorrect code, including the infamous http://en.wikipedia.org/wiki/Comma_operator.

Typo

intgr — 2009-06-10T20:32:50+00:00

3      if (atomic_dec_and_lock(&obj->refcnt), &subsystem_lock) {

Either we've got variable argument if statements now, or someone put the closing parenthese in the wrong place.

kref_get_not_zero()

neilbrown — 2009-06-09T20:42:15+00:00

Thanks for that reference.

I cannot comment on the code under the microscope in that thread as I am not familiar with it at all. However your observation that kref_get_not_zero() can be safe when used under a lock that excludes the object from being freed is one that I completely agree with. It is therefore tempting to call the function kref_get_locked() to match the inode_get_locked that already exists.

However it can be valid to use atomic_inc_not_zero() when not holding a lock, as in the example in a previous thread. In that case it is safe not because a lock is held, but because a secondary reference is held (s_count).

Either way, the complete pattern description for kref would need to spell out how and when to use kref_get_not_zero() (or whatever it gets called).

I must say that Greg's 'ick' in the reply to your linked post surprised me. kref_get_not_zero is (in my view) much less 'ick' than kref_set which is part of the current kref API (exercise: find all 3 places that use kref_set and replace them with calls to other parts of the api).

Unfortunate wording

jake — 2009-06-09T14:44:28+00:00

> Is there a missing "not"?

oops ... fixed now, thanks!

jake

Unfortunate wording

jreiser — 2009-06-09T14:21:34+00:00

Sadly, the kref package does make use of this primitive either. [in section The "kref" style at the end of paragraph three.]

Please correct this confusing usage. Is there a missing "not"?

kref_get_not_zero()

abatters — 2009-06-09T14:11:19+00:00

> Sadly, the kref package does make use of this primitive either.

Heh. I suggested introducing kref_get_not_zero() (based on atomic_inc_not_zero()) back in January, but got a lot of resistance. Better luck to the next guy.

http://marc.info/?l=linux-scsi&m=123196509202149&w=4

One use for reference-count biases...

PaulMcKenney — 2009-06-09T13:50:50+00:00

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

Linux Kernel Design Patterns - Part 1

neilbrown — 2009-06-09T12:15:07+00:00

Hi.

Thanks for your comments!

Your "furthermore" observation about locks is probably quite true. However I cannot see exactly how it is relevant. I'm not advocating adding any locks in there.

Your statement that placing the information in s_flags "does not work" is one that I don't agree with. Seeing I didn't include this among the exercises, I will give the reason here.

Let us hypothesise a flag SYS_FLAG_ACTIVE which is set at the same time that s_active is set to 0. This flag indicates that the entry is 'active' and it implies a counted reference on the sysfs_dirent. So instead of initialising s_active to 0, we initialise it to 1 (which is more in keeping with the kref pattern anyway).

In place of the (rather complex) loop in sysfs_get_active, we have the code

  if (test_bit(SYS_FLAG_ACTIVE, &sd->s_flags) 
      && atomic_inc_not_zero(&sd->s_active))
       return sd;
  else
       return NULL;

For me, that is easier to understand.

sysfs_deactivate then becomes

   sd->s_sibling = (void *)&wait;

   clear_bit(SYS_FLAG_ACTIVE, &sd->s_flags);

   if (! atomic_dec_and_test(&sd->s_active))
          wait_for_completion(&wait);

   sd->s_sibling = NULL;

Note that clearing the ACTIVE bit requires that we drop the reference that it implies. If that was the last reference we don't need to wait for any completion.

Finally sysfs_put_active becomes:

   if (atomic_dec_and_test(&sd->s_active)) {
         struct completion *cmpl = (void*)sd->s_sibling;
         complete(cmpl);
   }

A few moments thought shows that this now allows us to make sysfs_deactivate even simpler.

    sd->s_sibling = (void *)&wait;

    clear_bit(SYS_FLAG_ACTIVE, &sd->s_flags);
    sysfs_put_active(sd);
    wait_for_completion(&wait);

This calls "complete" and then "wait_for_completion" in the same thread, which is a bit unusual, but should work perfectly.

Providing support for atomic_inc_not_zero were added to kref (which I have already advocated), this would allow s_active to become a kref.

I believe the net result of these changes would be that the code is easier to understand, and hence harder to break at a later date. They do not change the functionality at all.

Linux Kernel Design Patterns - Part 1

ebiederm — 2009-06-09T10:24:37+00:00

Your statements seem reasonable but then I read the part about the reference counting in sysfs which I have actually worked with in detail and I stare in disbelief.

Placing the extra bit of information in s_flags does not work because that breaks the atomic nature of the current test.

Furthermore you have missed one of the most interesting bits about the reference counting in sysfs. Holding just about any lock when removing a sysfs file and by extention a kobject or struct device is a fun way to dead lock the kernel without lockdep having a clue.

One use for reference-count biases...

neilbrown — 2009-06-09T05:39:48+00:00

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

PaulMcKenney — 2009-06-09T04:36:44+00:00

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.