User: Password:
|
|
Subscribe / Log in / New account

Linux kernel design patterns - part 2

Linux kernel design patterns - part 2

Posted Jun 13, 2009 11:19 UTC (Sat) by nix (subscriber, #2304)
Parent article: Linux kernel design patterns - part 2

I must say that while I've used the RB-tree 'provide a partial toolbox' in
my own code, it felt ugly, more like an indictment of the language I was
working in than anything else. I couldn't help but think that if C had a
half-decent macro expansion facility, like Lisp, or guaranteed function
cloning and cross-module inlining (Ada provides some of that), all this
nonsense would be unnecessary. You could either provide a search macro
that expanded into code that did the search, incorporating your comparator
into the code itself rather than calling it, or the compiler could detect
the frequent use of some comparator, clone the search function, and inline
the comparator into the clone (and possibly the clone into its caller).

So this is really a workaround for C being such an expressively
impoverished language, IMHO.


(Log in to post comments)

Linux kernel design patterns - part 2

Posted Jun 13, 2009 22:49 UTC (Sat) by jlokier (guest, #52227) [Link]

You can in fact do this in C with macros. For example I have a nice list-sorting macro which takes a comparison code fragment as argument, and expands to fast code to sort a list using that comparator. Tree search and hash tables can be done similarly.

I agree macros more like LISP would be much more versatile. This is an area where C++ does well too, with or without templates.

But you can do it in C if you're determined.

Linux kernel design patterns - part 2

Posted Jun 14, 2009 9:20 UTC (Sun) by nix (subscriber, #2304) [Link]

Yeah, I suppose you could do that. There'd be constraints on the form of
the fragment, though: basically it'd have to be an expression.

With the statement-expression extension you *might* be able to do
something more than one expression long, but you're really playing in
areas where that extension hasn't been tested by that point, so who knows
if it'll work. (Well, I suppose I could try it.)

Linux kernel design patterns - part 2

Posted Jun 15, 2009 15:17 UTC (Mon) by madscientist (subscriber, #16861) [Link]

If you're willing to write your code for GNU C only you can use the GCC extension allowing statements and declarations as expressions to make this much simpler. see section 5.1 "Statements and Declarations in Expressions" in the chapter "C Extensions" in the GCC manual.

This lets you have a much more complex "expressions"... at the expense of portability.

Linux kernel design patterns - lack of red/black tree search function

Posted Jun 20, 2009 19:47 UTC (Sat) by giraffedata (subscriber, #1954) [Link]

... or guaranteed function cloning and cross-module inlining ...

I don't think it's cross-moduleness or variable-argumentness that make the common search function slow. It's the function pointer.

Does gcc inline even a locally defined used-once function when you call it via a constant function pointer? Didn't used to.

Linux kernel design patterns - lack of red/black tree search function

Posted Jun 21, 2009 22:26 UTC (Sun) by nix (subscriber, #2304) [Link]

No, it doesn't, but a sufficiently clever compiler could. The key is the
cross-module inlining.

(Even there, you'd be in trouble if the function doing the call was in a
different shared library than the caller. I don't see any way to fix
that.)

Linux kernel design patterns - lack of red/black tree search function

Posted Jun 21, 2009 22:46 UTC (Sun) by giraffedata (subscriber, #1954) [Link]

The key is the cross-module inlining.

Why is that the key? The pointed-to function would be in the main .c file and the library function that takes the function pointer as its argument would be in an included .h file like all the other functions we like to have inlined.

Linux kernel design patterns - lack of red/black tree search function

Posted Jun 22, 2009 22:21 UTC (Mon) by nix (subscriber, #2304) [Link]

Yes: and if the compiler was sufficiently clever, and all the .c files in
the application were presented to it at once, it would recognise instances
of this function that were frequently called with a particular function
pointer and clone a variant of that function that had that function
inlined into it: said variant would then get used only by the particular
call site in question.

This is way beyond what, say, GCC can do now, but is not disallowed nor
impossible to implement.

Linux kernel design patterns - lack of red/black tree search function

Posted Aug 22, 2009 15:32 UTC (Sat) by quotemstr (subscriber, #45331) [Link]

-fwhole-program

Linux kernel design patterns - part 2

Posted Jun 16, 2009 0:03 UTC (Tue) by neilbrown (subscriber, #359) [Link]

I have a few reflections on this.

Firstly: it may well be that C is "expressively impoverished". Nevertheless, C is the language that Linux is written in, and that is not likely to change. So if we find ways to make best use of those constructs which C gives us, and document them as Patterns, we can work around some of the worse short comings while still keeping the result reasonably maintainable.

Secondly: if you look at cfq_rb_root in cfq-iosched.c, you will find an rbtree with an 'optimisation' that the left-most node is cached, as in that application it is often wanted. Implementing that requires making changes inside the 'add' routine. Keeping the implementation 'open' makes it easier to build that sort of enhancement.

Thirdly: it may well be that there is a "better" pattern available using macros or inlines or whatever. In writing the article I was not inventing patterns, but simply documenting them. If doing so helps people to see the weaknesses in the patterns and thus to improve the code by applying a better pattern, then we will have achieved something very worthwhile.

Thanks.

Linux kernel design patterns - part 2

Posted Jun 22, 2009 22:23 UTC (Mon) by nix (subscriber, #2304) [Link]

Oh, I agree with all of that. I wasn't saying that this was a *bad* thing:
obviously C is a pretty damn good language to write kernels in! (I wasn't
writing a kernel at the time.)


Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds