timers, pointers to functions and type safety

There's a bunch of related issues, some kernel, some gcc,
thus the Cc from hell on that one.

First of all, in theory the timers in kernel are done that way:
* they have callback of type void (*)(unsigned long)
* they have data to be passed to it - of type unsigned long
* callback is called by the code that even in theory has no
chance whatsoever of inlining the call.
* one of the constraints on the targets we can port the kernel
on is that unsigned long must be uintptr_t.

The last one means that we can pass any pointers to these suckers; just cast to unsigned long and cast back in the callback.

While that is safe (modulo the portability constraint that affects much more code than just timers), it ends up very inconvenient and leads to lousy type safety.

The thing is, absolute majority of callbacks really want a pointer to some object. There is a handful of cases where we really want a genuine number - not a pointer cast to unsigned long, not an index in array, etc. They certainly can be dealt with. Nearly a thousand of other instances definitely want pointers.

Another observation is that quite a few places are playing fast and loose with function pointers. Some are just too lazy and cast void (*)(void) to void (*)(unsigned long). These, IMO, should stop wanking and grow an unused argument. Not worth the ugliness... However, there are other cases, including very interesting

	timer->function = (void (*)(unsigned long))func;
	timer->data = (unsigned long)p;

with func actually being void (void *) and p being void *.

Now, _that_ is definitely not a valid C. Worse, it doesn't take much to come up with realistic architecture that would have different calling conventions for those. Just assume that
* there are two groups of registers (A and D)
* base address for memory access must be in some A register
* both A and D registers can be used for arithmetics
* ABI is such that functions with few arguments have them passed
via A and D registers, with pointers going via A and numbers via D. Realistic enough? I wouldn't be surprised if such beasts actually existed - embedded processors influenced by m68k are not particulary rare and picking such ABI would make sense for them.

Note that this kind of casts is not just in some obscure code; e.g. rpc_init_task() does just that.

And that's where it gets interesting. It would be very nice to get to the following situation:
* callbacks are void (*)(void *)
* data is void *
* instances can take void * or pointer to object type
* a macro SETUP_TIMER(timer, func, data) sets callback and data
and checks if func(data) would be valid.

It would be remove a lot of cruft and definitely improve the type safety of the entire thing. It's not hard to do; all it takes [warning: non portable C ahead] is

	typeof(*data) *p = data;
	timer->function = (void (*)(void *))func;
	timer->data = (void *)p;
	(void)(0 && (func(p),0));

Again, that's not a portable C, even leaving aside the use of typeof. Casts between the incompatible function types are undefined behaviour; rationale is that we might have different calling conventions for those. However, here we are at much safer ground; calling conventions are not likely to change if you replace a pointer to object with void *. It's still possible in theory, but let's face it, we would have far worse problems if it ever came to porting to such targets.

Note that here we have absolutely no possibility of eventual call ever being inlined, no matter what kind of analysis compiler might be doing. Call happens when kernel/timer.c gets to structure while trawling the lists and it simply has no way to tell which callback might be there (as the matter of fact, callback can and often does come from a module).

IOW, "gcc would ICE if it ever inlined it" kind of arguments (i.e. what had triggered gcc refusing to do direct call via such cast) doesn't apply here. Question to gcc folks: can we expect no problems with the approach above, provided that calling conventions are the same for passing void * and pointers to objects? No versions (including current 4.3 snapshots) create any problems here...

BTW, similar trick would be very useful for workqueues - there we already have void * as argument, but extra type safety would be nice to have.

Now, there's another question: how do we get there? Or, at least, from current void (*)(unsigned long) to void (*)(void *)...

"A fscking huge patch flipping everything at once" is obviously not an answer; too much PITA merging and impossible to review. There is a tempting possibility to do that gradually, with all intermediates still in working state, provided that on all platforms currently supported by the kernel unsigned long and void * are indeed passed the same way (again, only for current kernel targets and existing gcc versions). Namely, we could
* introduce SETUP_TIMER variant with cast to void (*)(unsigned long)
* switch to its use, converting callback instances to take pointers
at the same time. That would be done in reasonably sized groups.
* once it's over, flip ->function to void (*)(void *), ->data to
void * and update SETUP_TIMER accordingly; deal with remaining few instances of ->function.
That way we at least get that sucker chopped into reasonable pieces and do not introduce broken intermediate trees. Evil casts to void (*)(unsigned long) will be gone by the end of the series, so they are not there to stay - just a way to avoid too bad breakage in the middle of series. Of course, that strategy only works if all currently supported targets *do* allow that kind of casts; if there are any counterexamples, it's back to the drawing board and we'd better fix sunrpc ASAP - it does pull that sort of trick.

Understandable. I assume you are trying to get more type safety more for error checking than optimization, being that the kernel still defaults to -fno-strict-aliasing.

Is this true of the ports you guys support even if the object is a function pointer or a function?
(Though the first case may be insane. I can't think of a *good* reason you'd pass a pointer to a function pointer to a timer callback,).

Ah, well, here is where you are kinda wrong, but not for the reason you are probably thinking of.

Right, it doesn't know what it will *always* be, but it may add if's and inline *possible* target sites based on profile results.

Particularly since the profile will tell us which are *actually* called. This shouldn't matter however, we still shouldn't ICE if we inline it :)

Personally, as someone who works on the pointer and alias analysis, I'm much more worried about your casting of void (*)(void) to void (*)(unsigned long) breaking in the future than I am about the above.

I can't really see the above code breaking any more than what you have now, and it should in fact, break a lot less. However, the removal of the argument cast (IE void (*) (void) to void (*) unsigned long) maybe break eventually. As we get into intermodule analysis and figure out the conservative set of called functions for a random function pointer, the typical thing to do is to type filter the set so only those address taken functions with "compatible" signatures (for some very loose definition of compatible) are said to be callable by a given function pointer. I can't imagine the definition of compatible would include address taken functions with less arguments than the function pointer you are calling through. In this specific case, as you point out, it's pretty unlikely we'll ever be able to come up with a set without something telling us. But I figured i'd mention it in case this type of casting is prevalent elsewhere.

IOW, unless someone else can see a good reason, I see no reason for you guys not to switch.

--Dan

Indeed.

                                                ^^^^^^

Pointer to pointer to function should be OK - it's a pointer to normal object type and I would be very surprised if it differed from void *, modulo very creative reading of 6.3.2.3(1). I certainly wouldn't expect it to differ from e.g. pointer to pointer to struct, even on targets far odder than anything we might hope to port to.

Pointer to function might be worse, but that's excluded by the above - it's not a pointer to object type.

In any case, we don't do either anywhere and if the need ever arises we can simply put that pointer into whatever structure our timer_list is embedded into and pass the address of that structure (which is what we do in a lot of cases anyway).

IOW, it's worth checking in SETUP_TIMER, but it's not going to be a realistic PITA in any instance.

That one will be gone; it's pure laziness and IMO ~10 instances mostly in weird ancient cdrom drivers are not worth worrying about, especially since getting rid of such crap is a matter of minutes.

Umm... That type of casting worries me too, and not for timer-related reasons. We do it a lot in one place: fs/bad_inode.c. A bunch of methods with different arguments,
static int return_EIO(void)

{
        return -EIO;
}

and (void *)return_EIO used to initialize them. There's a couple of other places where minor turds like that are done, but that one is the most massive. That's bloody annoying when doing any global call graph analysis (sparse-based in my case, but I wouldn't expect gcc folks being any happier with it)...

And no, it certainly isn't good C for many reasons (any target where callee removes arguments from stack before returning control to caller and that one's toast, for starters).

This is where a very limited form of C++ templates would do nicely; you could define something like the following:

template <typename T>
static inline void setup_timer(struct timer_list *timer,

		void (*function)(T *), T *data)
{
	timer->function = (void (*)(void *))function;
	timer->data = (void *)data;
	init_timer(timer);
}

Any attempts to call it with mismatched "function" and "data" arguments would display an "Unable to find matching template" error from the compiler.

Unfortunately you can't get simple templated functions without opening the whole barrel of monkeys involved with C++ support; including an explosion of reserved words, a 400% or more increase in compilation time, a decrease in the efficiency of parts of the generated code, etc.

<crazy-talk>
Maybe it's time for Linux to fork GCC and morph C99 into a language whose design more fundamentally supports the kinds of type-checking and static verification that we keep adding to the kernel, including some of the things that sparse, lockdep, kmemleak, etc. do. </crazy-talk>

Cheers,
Kyle Moffett

Fortunately, you can get all checks done by gcc without involving C++ (or related flamewars). See original post for a way to do it in a macro and for fsck sake, leave [email protected] out of it.

Folks, please trim the Cc. My apologies for cross-posting in the first place, should've double-posted instead and manually forwarded relevant followups...

Oh, I'm sorry I totally missed the CC of [email protected]. My point was just that while it _could_ be done with GCC and some ugly macros, a basic form of C++ templates usually produces much nicer and more descriptive error messages (leaving out all the reasons C++ isn't usable in the kernel for the sake of academic discussion). The template syntax is also a bit more descriptive than is the macro syntax for achieving the same thing.

Cheers,
Kyle Moffett

Another alternative might be to define an intermediate version of timer_list that avoids adding new macros, like

struct timer_list {
	struct list_head entry;

­ unsigned long expires;

­ void (*function)(union { unsigned long l; void *p; }

				 __attribute__((transparent_union)));
­	union {
		unsigned long data __deprecated;
		void *obj;
	};

­ struct tvec_t_base_s *base;
};

Unfortunately, this relies more on gcc specific behavior than we may want, and it makes it possible to abuse in new ways, like defining a function to take an unsigned long argument, but passing the data as void *obj.

	Arnd <><

I think the real solution should be

	void (*function)(struct timer_list *timer);

and hand the timer itself to the callback. Most of the timers are embedded into data structures anyway and for the rest we can easily build one.

There are ~ 500 files affected and this is in the range of cleanups we did recently at the end of the merge window already. I'd volunteer to hack this up and keep the patch up to date until the final merge. I have done that before and I'm not scared about it. The patches are a couple of lines per file and I do not agree that this is impossible to review.

tglx

Ewwwwwww....

Let's not. It means more cruft in callbacks for no good reason. And more cruft in code setting it up, while we are at it.

I'd rather see that as patch series, TYVM. And no, it won't be a couple of lines per file with your variant.

Anyway, I'm doing that series in my tree, will post when it's over...

What's the cruft ?

struct bla = container_of(timer, struct bla, timer); ???

Err, you remove the timer->data = (unsigned long) hackery. Why is this adding cruft ?

I looked deeper into it. We have following timer usage:

- timers which don't use data at all - no change except for the callback argument of the function.

- timers which point to the data structure which embedds them - only the callback has to get a container_of()

- static single instance timers, which use .data as local storage for some value. That can be done with a simple static variable near the timer and using that variable instead of .data

- some rather seldom multi instance timers, which need then to become a data structure.

It will. Just some random files:

 arch/alpha/kernel/srmcons.c             |    7 +++--
 arch/arm/mach-pxa/lubbock.c             |    7 +++--
 arch/i386/kernel/tsc.c                  |    2 -
 arch/i386/mach-voyager/voyager_thread.c |    2 -
 arch/ia64/kernel/mca.c                  |    8 +++---
 arch/ia64/kernel/salinfo.c              |    2 -
 arch/ia64/sn/kernel/mca.c               |    2 -
 arch/ia64/sn/kernel/xpc_channel.c       |    3 --
 arch/ia64/sn/kernel/xpc_main.c          |    5 +++-
 arch/mips/lasat/picvue_proc.c           |    2 -
 arch/mips/sgi-ip22/ip22-reset.c         |   17 +++++++------
 include/asm-ia64/sn/xpc.h               |    2 -

Same here :)

tglx

That's it, right there. Any idea how much we've bloated the kernel with sysfs, just by insisting that the struct device not be the first item in the struct? There's any number of 2- and 3- line functions calling each other, each adding and subtracting constants from the pointers passed to them. This was a huge mistake, IMO.

What a nonsense.

	foo->timer.data = foo;

is complete redundant information.

This is going to make a lot of data structures smaller, when the timer_list is embedded in the structure itself and for the lot, which ignores the timer callback argument anyway.

tglx

container_of => still lousy type safety. All over the sodding place.

Not less than timer->data, where timer data is void *

tglx

RTFPosting. It might be void *, but it's set via SETUP_TIMER which does type checks before casting to void *.

IOW, I don't want _any_ typecasts/container_of necessary in the code.

Sane variant is

void foo_timer(struct net_device *dev)

{
	...
}

	struct foo_dev *p = netdev_priv(dev);
	SETUP_TIMER(&p->timer, foo_timer, dev);

etc.

With warning generated if foo_timer(dev) would not be type safe. Without typecasts. Without container_of(). Without any bleeding cruft at all.

BTW, the same goes for tasklets and for work_struct. Separate series, obviously...

Hi,

You need some more magic macros to access/modify the data field. Your SETUP_TIMER macro only protects the simple cases, which are easy anyway, in this case I prefer the space savings container_of can give us.

bye, Roman

Which is done bloody rarely. grep and you'll see... BTW, there are other reasons why passing struct timer_list * is wrong:
* direct calls of the timer callback
* callback being the same for two timers embedded into
different structs
* see a timer callback, decide it looks better as a tasklet.
What, need a different glue now?

Look, it's a delayed call. The less glue we need, the better - the rules are much simpler that way, so that alone means that we'll get fewer fsckups.

Hi,

Why should that be wrong?

That's done bloody rarely as well.

What's wrong with changing the prototype? If you don't do it, the compiler will complain about it anyway.

You have the glue in a different place, so what?
The other alternative has real _practical_ value in almost every case, which I very much prefer. What's wrong with that?

bye, Roman

Need to arrange a struct timer_list?

How about "not having to change it at all"?

Where?

Lack of any type safety whatsoever, magic boilerplates in callback instances, rules more complex than "your callback should take a pointer, don't cast anything, it's just a way to arrange for a delayed call, nothing magical needed"?

Hi,

How is that different from arranging some struct foo? Either you need a reference object anyway or a NULL pointer works in both cases.

If it were a common operation, this might have some value...

In SETUP_TIMER.

I admit the compile check in SETUP_TIMER() is clever, but this way all the magic is in this place and is it really worth it? You're only adding _one_ extra typecheck for mostly simple cases anyway.
The container_of() method is not new and is already well used in other places, it has real practical advantages, which would make the change actually worthwile.

bye, Roman

Hi!

Well, there are so many of these simple changes, that SETUP_TIMER() with its clever trick looks very useful.
Pavel

(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

I agree with Al, Matthew and Pavel. The current timer stuff is a pita and needs fixing, and it seems Al has come up with a good way to do it without adding additional crap into every single user of timers.

There *are* times when having the additional space for storing a pointer is cheaper (in terms of number of bytes) than code to calculate an offset, and those who have read the assembly code probably know this all too well.

Al - I look forward to your changes.

Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:

Hi,

What exactly is the pita here? Al only came up with some rather theoretical problems with no practical relevance.

In simple cases gcc can optimize this away, additionally it's offset by one less memory reference in the timer code, so the code executed per timer would be equal or often even less. Additionally less code is needed to initialize the timer.

I don't. The current API is maybe not perfect, but changing the API for no practical benefit would be an even bigger pita. I'd rather keep it as is.

bye, Roman

Lack of type-checking in timers is ugly.

Al is trying to add type-checking in pretty nice & straightforward manner. Please let him do it.
Pavel

(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Hi,

It's a matter of perspective, a bit more type checking would be nice, but breaking the API just for that is ugly as well. Unless there is a bad need for it, I don't think it's worth it...

bye, Roman

I do not think Al is breaking anything. He's adding that typechecking, old interface can still stay for a while.
Pavel

(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

All it generally takes is two instances of a timer_list struct that use one common handler function for the removal of the data member from the timer_list to be a win on pretty much every platform.

Consider: you replace:

	struct timer_list {
		void (*func)(unsigned long data);
		unsigned long data;
	};

	void handler(unsigned long data)
	{
		struct *foo = (struct foo *) data;
		...
	}

with:

	struct timer_list {
		void (*func)(struct timer_list *timer);
		unsigned long data;
	};

	void handler(struct timer_list *timer)
	{
		struct *foo = container_of(timer, struct foo, mytimer);
		...
	}

You are removing 4 or 8 bytes (an unsigned long) from each of two structures and replacing them with a single ADD/SUB instruction, usually with a small immediate value - which will be at most 4 bytes on most archs - and in some cases it'll cost less than that because the compiler can use REG+offset addressing and so avoid the adjustment entirely.

Another way to look at it is that timers aren't generally called all that often, but that a fair number of structures in the kernel contain timers - though maybe second or third hand. You can shrink all of these by one word per timer, and that makes an immediate effect.

Furthermore, I have patches to shrink work_struct by (a) removing the timer where it's not needed, (b) folding the single flag bit into one of the pointers, and (c) dropping the data member in favour of using container_of() in the handler.

In almost every case where a work_struct is used, the data argument is the address of the structure containing the work_struct, so (c) gains.

The three reductions reduce the size of work_struct by two-thirds. The new delayed_struct is only a reduction of one-sixth as it still carries a timer. However, if that timer can be shrunk by one-sixth by removing that data argument, then the delayed_struct can exhibit a one-quarter reduction instead.

David

I assume you wanted to delete "data" ?

Your premise is two timer_lists which use one common handler.

	struct foo {
		struct timer_list timer1;
		strucr timer_list timer2;
	};

would preclude using a common handler for both timers. You need two separate handlers, one which knows the offset of timer1 and the other the offset of timer2.

In this case, you are removing 2 * sizeof(unsigned long) from struct foo, but you're adding a two add/sub instructions to each handler, but worse than that, this would force two veneer handlers to call the common handler.

The point here is that we can all dream up cases where some particular way is a win or not. Whether it really _is_ a win depends on the uses in the kernel.

The only real way to find that out is to try it. Generate a patch. Build it. See what happens to the kernel code and data sizes.

I strongly suggest that we do that rather than speculating. 8) Words (and emails) are cheap but in the end are not really constructive.

Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:

Yes.

That's not what I was thinking of. I was thinking of something much simpler:

	struct foo {
		struct timer_list timer;
	};


	...
		struct foo *a = kmalloc(sizeof(struct foo), GFP_KERNEL);
		a->timer.fn = do_foo_timer;
	...
		struct foo *b = kmalloc(sizeof(struct foo), GFP_KERNEL);
		b->timer.fn = do_foo_timer;
	...
		struct foo *c = kmalloc(sizeof(struct foo), GFP_KERNEL);
		c->timer.fn = do_foo_timer;
	...
		struct foo *d = kmalloc(sizeof(struct foo), GFP_KERNEL);
		d->timer.fn = do_foo_timer;
	...

You've now got four copies of struct timer_list, but only one handler.

David

<re-insert last paragraph of my message until read, understood and actioned.>

Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:

I was merely correcting your assumption of what premise I was thinking of. You thought of something unnecessarily complex. I said nothing about what I thought of your last suggestion. Timer reduction patches are being worked on, though not by me.

David

That's entirely a matter of opinion. Which is _precisely_ why I made that particular statement which you don't appear to understand.

Let me make it again in a different way:

This is all mere hand waving. We can all dream up scenarios where something works better than something else. Until someone actually sits down and works it out it's just useless talk and random opinions, nothing more.

Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:

the question is: which is more important, the type safety of a container_of() [or type cast], which if we get it wrong produces a /very/ trivial crash that is trivial to fix - or embedded timers data structure size all around the kernel? I believe the latter is more important.

and we could have a runtime debugging option to tie the type of the structure to the timer list entry. For example by using __builtin_classify_type(), sizeof() and offsetof() to fingerprint timer structs at init_timer time, and then checking for that at container_of() time - or something like that. In fact, gcc should really give us a better way to categorize types than __builtin_classify_type(). We could probably improve the situation by having some global registry of types known to the kernel, via a huge switch() around __builtin_types_compatible_p().

Ingo

Indeed yes.

Using container_of() and ditching the data value, you generally have to have one extra instruction per timer handler, if that, but you are able to discard one instruction or more from __run_timers() and struct timer_list discards a word.

You will almost certainly have far more timer_list structs in the kernel than timer handler functions, therefore it's a space win, and possibly also a time win (if the reduction of __run_timers() is greater than the increase in the timer handler).

And that extra instruction in the timer handler is usually going to be an addition or subtraction of a small immediate value - which may be zero (in which case the insn is dropped) or which may be folded directly into memory access instruction offsets.

David

The hell it is. You get wrong fields of a big struct read and modified. Silently.

Besides, I can show you fsckloads of cases when we do *NOT* pass a pointer to struct the timer is embedded into. Some of them called directly (and no, the thing they get as argument doesn't point to anything that would contain a timer_list).

Guys, please, look at actual users of that stuff.

I've been and looked at every single user of work_struct in the kernel (at least, I think I have), and 99% of those just expect data to be the container of the work_struct or a data structure linked to it. I had to come up with a way to deal with cases where data is something from which you can't derive from the work_struct address, but I'm not sure how best to do that for timers.

I haven't, however, been and looked at timers, so I can't say what actually applies there.

David

yeah - i think you are right. I think we should go with your changes to incrase type safety for timer callbacks - and if someone wants to shrink size (which patches do not exist at the moment), that person can think about how to achieve that while still keeping type safety.

Ingo

Hi,

sysfs is a major bloat indeed, but that's not it.
If at all this generates smaller code, as only one pointer is needed instead of two.

bye, Roman