Skip to contentSkip to conversation

Btrfs for mainline

RFC PATCH In review Chris Mason 45 participants 367 messages Dec 31, 2008 – Jan 21, 2009 Page 2 of 2

Subsystems (8)
x86 VFS Kbuild Btrfs file system +4 more subsystems
lore
Share & tools
lore
#239 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 5 lines · Ingo Molnar
Quoted 2 lines · Linus Torvalds
Quoted 1 line · Ingo Molnar
Quoted 8 lines
Quoted 6 lines
Quoted 4 lines

Well, it's not totally meaningless. To begin with, defining 'inline' to mean 'always inline' is a Linux kernel definition. So we already changed the behavior - in the hope of getting it right most of the time and in the hope of thus improving the kernel.

Umm. No we didn't. We've never changed it. It was "always inline" back in

s/changed the behavior/overrode the behavior

The point is, as far as the kenrel has been concerned, "inline" has always meant the same thing. Not just for the last few weeks, but for the last 18 _years_. It's always meant "always inline".

Quoted 3 lines

But i'd definitely argue that the Linux kernel definition of 'inline' was always more consistent than GCC's. That was rather easy as well: it doesnt get any more clear-cut than 'always inline'.

Exactly. And I argue that we shouldn't change it.

If we have too many "inline"s, and if gcc inlines for us _anyway_, then the answer is not to change the meaning of "inline", but simply say "ok, we have too many inlines. Let's remove the ones we don't care about".

Quoted 3 lines

I think it is axiomatic that improving the kernel means changing it - sometimes that means changing deep details. (And if you see us ignoring complaints, let us know, it must not happen.)

And I'm agreeing with you.

What I'm _not_ agreeing with is how you want to change the semantics of something we've had for 18 years.

YOU are the one who want to make "inline" mean "maybe". I'm against it. I'm against it because it makes no sense. It's not what we've ever done.

Linus

#240 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 7 lines · Ingo Molnar

* Linus Torvalds <[email protected]> wrote:

- Headers could probably go back to 'extern inline' again. At not small expense - we just finished moving to 'static inline'. We'd need to guarantee a library instantiation for every header include file - this is an additional mechanism with additional introduction complexities and an ongoing maintenance cost.

Puzzled? What benefit is there to going back to extern inline in headers?

Harvey

#241 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 9 lines · Harvey Harrison
Quoted 5 lines · Ingo Molnar

- Headers could probably go back to 'extern inline' again. At not small expense - we just finished moving to 'static inline'. We'd need to guarantee a library instantiation for every header include file - this is an additional mechanism with additional introduction complexities and an ongoing maintenance cost.

Puzzled? What benefit is there to going back to extern inline in headers?

There's none. In fact, it's wrong, unless you _also_ have an extern definition (according to the "new" gcc rules as of back in the days).

Of course, as long as "inline" really means _always_ inline, it won't matter. So in that sense Ingo is right - we _could_. Which has no bearing on whether we _should_, of course.

In fact, the whole mess with "extern inline" is a perfect example of why a inlining hit should be called "may_inline" or "inline_hint" or something like that.

Because then it actually makes sense to have "extern may_inline" with one definition, and another definition for the non-inline version. And it's very clear what the deal is about, and why we literally have two versions of the same function.

But again, that's very much not a "let's use 'extern' instead of 'static'". It's a totally different issue.

Linus

[ A third reason to use "extern inline" is actually a really evil one: we
could do it for our unrelated issue with system call definitions on architectures that require the caller to sign-extend the arguments.

Since we don't control the callers of system calls, we can't do that, and architectures like s390 actually have potential security holes due to callers that don't "follow the rules". So there are different needs for trusted - in-kernel - system call users that we know do the sign extension correctly, and untrusted - user-mode callers that just call through the system call function table.

What we _could_ do is for the wrappers to use

	extern inline int sys_open(const char *pathname, int flags, mode_t mode)
	{
		return SYS_open(pathname, mode);
	}

which gives the C callers the right interface without any unnecessary wrapping, and then

	long WRAP_open(const char *pathname, long flags, long mode)
	{
		return SYS_open(pathname, flags, mode);
	}
	asm ("\t.globl sys_alias\n\t.set WRAP_open");

which is the one that gets linked from any asm code. So now asm code and C code gets two different functions, even though they use the same system call name - one with inline expansion, one with linker games.

Whee. The games we can play (and the odd reasons we must play them). ]

#242 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 8 lines · Linus Torvalds

There's none. In fact, it's wrong, unless you _also_ have an extern definition (according to the "new" gcc rules as of back in the days).

Of course, as long as "inline" really means _always_ inline, it won't matter. So in that sense Ingo is right - we _could_. Which has no bearing on whether we _should_, of course.

I was thinking about experimenting with this, to see what level of upside it might add. Ingo showed me numbers which indicate that a fairly significant fraction of the cases where removing inline helps is in .h files, which would require code movement to fix. Hence to see if it can be automated.

-hpa

Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.
#243 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 6 lines · H. Peter Anvin

I was thinking about experimenting with this, to see what level of upside it might add. Ingo showed me numbers which indicate that a fairly significant fraction of the cases where removing inline helps is in .h files, which would require code movement to fix. Hence to see if it can be automated.

We _definitely_ have too many inline functions in headers. They usually start out small, and then they grow. And even after they've grown big, it's usually not at all clear exactly where else they should go, so even when you realize that "that shouldn't be inlined", moving them and making them uninlined is not obvious.

And quite often, some of them go away - or at least shrink a lot - when some config option or other isn't set. So sometimes it's an inline because a certain class of people really want it inlined, simply because for _them_ it makes sense, but when you enable debugging or something, it absolutely explodes.

Linus

#244 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 7 lines · Linus Torvalds

And quite often, some of them go away - or at least shrink a lot - when some config option or other isn't set. So sometimes it's an inline because a certain class of people really want it inlined, simply because for _them_ it makes sense, but when you enable debugging or something, it absolutely explodes.

And this is really why getting static inline annotations right is really hard if not impossible in the general case (especially when considering the sheer number of architectures we compile on.) So making it possible for the compiler to do the right thing for at least this class of functions really does seem like a good idea.

-hpa

Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.
#245 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 14 lines · Linus Torvalds
Quoted 6 lines · H. Peter Anvin

I was thinking about experimenting with this, to see what level of upside it might add. Ingo showed me numbers which indicate that a fairly significant fraction of the cases where removing inline helps is in .h files, which would require code movement to fix. Hence to see if it can be automated.

We _definitely_ have too many inline functions in headers. They usually start out small, and then they grow. And even after they've grown big, it's usually not at all clear exactly where else they should go, so even when you realize that "that shouldn't be inlined", moving them and making them uninlined is not obvious.

Quoted 5 lines

And quite often, some of them go away - or at least shrink a lot - when some config option or other isn't set. So sometimes it's an inline because a certain class of people really want it inlined, simply because for _them_ it makes sense, but when you enable debugging or something, it absolutely explodes.

IMO it's all quite dynamic when it comes to inlining.

Beyond the .config variances (which alone is enough degrees of freedom to make this non-static, it at least is a complexity we can control in the kernel to a certain degree) it also depends on the platform, the CPU type, the compiler version - factors which we dont (and probably dont want to) control.

There's also the in-source variance of how many times an inline function is used within a .c file, and that factor is not easily tracked. If it's used once in a single .c file it should be inlined even if it's large. If it's used twice in a .c file it might be put out of line. Transition between those states is not obvious in all cases.

There's certainly clear-cut cases: the very small/constant ones that must be short and inlined in any environment, and the very large/complex ones that must not be inlined under any circumstance.

But there's a lot of shades of grey inbetween - and that's where the size wins come from. I'm not sure we can (or should) generally expect kernel coders to continuously maintain the 30,000+ inline attributes in the kernel that involve 100,000+ functions:

- Nothing breaks if it's there, nothing breaks if it's not there. It's a completely opaque, transparent entity that never pushes itself to the foreground of human attention.

- It's so easy to add an inline function call site to a .c file without noticing that it should not be inlined anymore.

- It's so easy to _remove_ a usage site from a .c file without noticing that something should be inlined. I.e. local changes will have an effect on the inline attribute _elsewhere_ - and this link is not obvious and not tooled when editing the code.

- The mapping from C statements to assembly can be non-obvious even to experienced developers. Data type details (signed/unsigned, width, etc.) can push an inline function over the (very hard to define) boundary.

I.e. IMO it's all very dynamic, it's opaque, it's not visualized and it's hard to track - so it's very fundamentally not for humans to maintain [except for the really clear-cut cases].

Add to that that in _theory_ the decision to inline or not is boringly mechanic and tools ought to be able to do a near-perfect job with it and just adopt to whatever environment the kernel is in at a given moment when it's built.

GCC limps along with its annoyingly mis-designed inlining heuristics, hopefully LLVC will become a real compiler that is aware of little details like instruction size and has a built-in assembler ...

So IMO all the basic psychological mechanics are missing from the picture that would result in really good, "self-maintained" inline attributes.

We can try to inject the requirement to have good inline attributes as an external rule, as a principle we want to see met - but we cannot expect it to be followed really in its current form, as it goes subtly against the human nature on various levels.

Ingo

#246 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 2 lines · Ingo Molnar

If it's used once in a single .c file it should be inlined even if it's large.

As Linus has pointed out, because of GCC not sharing stack among different inlined functions, the above is surprisingly not true.

In kernel it's a problem due to raw stack usage.

In userspace apps (where stack used is larger), inlining single-call functions could, paradoxically, run slower due to increased stack dcache pressure for some larger functions.

-- Jamie

#247 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 6 lines · Jamie Lokier
Quoted 2 lines · Ingo Molnar

If it's used once in a single .c file it should be inlined even if it's large.

As Linus has pointed out, because of GCC not sharing stack among different inlined functions, the above is surprisingly not true.

Yes, but note that this has no relevance to the specific case of
CONFIG_OPTIMIZE_INLINING: GCC can at most decide to inline _less_, not more. I.e. under CONFIG_OPTIMIZE_INLINING we can only end up having less stack sharing trouble.

Ingo

#248 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 6 lines

- Headers could probably go back to 'extern inline' again. At not small expense - we just finished moving to 'static inline'. We'd need to guarantee a library instantiation for every header include file - this is an additional mechanism with additional introduction complexities and an ongoing maintenance cost.

I thought the "static inline" in headers should be more of a "always inline". As Andrew Morton keeps yelling at me to use static inline instead of macros ;-)

I do not see the point in the functions in the headers needing to have their "inlines" removed.

Quoted 4 lines

- 'static inline' functions in .c files that are not used cause no build warnings - while if we change them to 'static', we get a 'defined but not used' warning. Hundreds of new warnings in the allyesconfig builds.

Perhaps that's a good thing to see what functions are unused in the source.

Quoted 6 lines

I know that because i just have removed all variants of 'inline' from all .c files of the kernel, it's a 3.5MB patch:

   3263 files changed, 12409 insertions(+), 12409 deletions(-)
Quoted 8 lines

x86 defconfig comparisons:

      text    filename
   6875817    vmlinux.always-inline                       (  0.000% )
   6838290    vmlinux.always-inline+remove-c-inlines      ( -0.548% )
   6794474    vmlinux.optimize-inlining                   ( -1.197% )

So the kernel's size improved by half a percent. Should i submit it?

Are there cases that are "must inline" in that patch? Also, what is the difference if you do vmlinux.optimize-remove-c-inlines? Is there a difference there?

-- Steve

#249 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 4 lines · Ingo Molnar

- 'static inline' functions in .c files that are not used cause no build warnings - while if we change them to 'static', we get a 'defined but not used' warning. Hundreds of new warnings in the allyesconfig builds.

Well, duh. Maybe they shouldn't be marked "inline", and maybe they should be marked with "__maybe_unused" instead.

I do not think it makes sense to use "inline" as a way to say "maybe I won't use this function".

Yes, it's true that "static inline" won't warn, but hey, as a way to avoid a warning it's a pretty bad one.

Linus

#250 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 31 lines · On Sat, 10 Jan 2009 02:01:25 +0100 Ingo Molnar <[email protected]> wrote:
Quoted 11 lines · Linus Torvalds
Quoted 2 lines · Ingo Molnar

may_inline/inline_hint is a longer, less known and uglier keyword.

Hey, your choice, should you decide to accept it, is to just get rid of them entirely.

You claim that we're back to square one, but that's simply the way things are. Either "inline" means something, or it doesn't. You argue for it meaning nothing. I argue for it meaning something.

Quoted 5 lines

If you want to argue for it meaning nothing, then REMOVE it, instead of breaking it.

It really is that simple. Remove the inlines you think are wrong. Instead of trying to change the meaning of them.

Well, it's not totally meaningless. To begin with, defining 'inline' to mean 'always inline' is a Linux kernel definition. So we already changed the behavior - in the hope of getting it right most of the time and in the hope of thus improving the kernel.

And now it appears that in our quest of improving the kernel we can further tweak that (already non-standard) meaning to a weak "inline if the compiler agrees too" hint. That gives us an even more compact kernel. It also moves the meaning of 'inline' closer to what the typical programmer expects it to be - for better or worse.

Quoted 5 lines

We could remove them completely, but there are a couple of practical problems with that:

- In this cycle alone, in the past ~2 weeks we added another 1300 inlines to the kernel.

Who "reviewed" all that?

Quoted 7 lines

Do we really want periodic postings of:

[PATCH 0/135] inline removal cleanups

... in the next 10 years? We have about 20% of all functions in the kernel marked with 'inline'. It is a _very_ strong habit. Is it worth fighting against it?

A side-effect of the inline fetish is that a lot of it goes into header files, thus requiring that those header files #include lots of other headers, thus leading to, well, the current mess.

#251 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 3 lines

A side-effect of the inline fetish is that a lot of it goes into header files, thus requiring that those header files #include lots of other headers, thus leading to, well, the current mess.

I personally also always found it annoying while grepping that part of the code is in a completely different directory. e.g. try to go through TCP code without jumping to .hs all the time.

Long term that problem will hopefully disappear, as gcc learns to do cross source file inlining (like a lot of other compilers already do)

-Andi

Signature · 1 line
[email protected]
#252 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 2 lines · Andi Kleen

Long term that problem will hopefully disappear, as gcc learns to do cross source file inlining (like a lot of other compilers already do)

We've already been able to get GCC doing this for the kernel, in fact (the --combine -fwhole-program stuff I was working on a while back).

It gives an interesting size reduction, especially in file systems and other places where we tend to have functions with a single call site... but in a different file.

Linus argues that we don't want that kind of inlining because it harms debuggability, but that isn't _always_ true. Sometimes you weren't going to get a backtrace if something goes wrong _anyway_. And even if the size reduction doesn't necessarily give a corresponding performance improvement, we might not care. In the embedded world, size does matter too. And the numbers are such that you can happily keep debuginfo for the shipped kernel builds and postprocess any backtraces you get. Just as we can for distros.

In general, I would much prefer being able to trust the compiler, rather than disabling its heuristics completely. We might not be able to trust it right now, but we should be working towards that state. Not just declaring that we know best, even though _sometimes_ we do.

I think we should:

- Unconditionally have 'inline' meaning 'always_inline'. If we say it, we should mean it.

- Resist the temptation to use -fno-inline-functions. Allow GCC to inline other things if it wants to.

- Reduce the number of unnecessary 'inline' markers, and have a policy that the use of 'inline' should be accompanied by either a GCC PR# or an explanation of why we couldn't reasonably have expected GCC to get this particular case right.

- Have a similar policy of PR# or explanation for 'uninline' too.

I don't think we should just give up on GCC ever getting it right. That way lies madness. As we've often found in the past.

Signature · 2 lines
David Woodhouse                            Open Source Technology Centre
[email protected]                              Intel Corporation
#253 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 5 lines · David Woodhouse

- Unconditionally have 'inline' meaning 'always_inline'. If we say it, we should mean it.

- Resist the temptation to use -fno-inline-functions. Allow GCC to inline other things if it wants to.

The proposal was to use -fno-inline-functions-called-once (but the resulting numbers were not promising)

We've never allowed gcc to inline any other functions not marked inline explicitely because that's not included in -O2.

Quoted 9 lines

- Reduce the number of unnecessary 'inline' markers, and have a policy that the use of 'inline' should be accompanied by either a GCC PR# or an explanation of why we couldn't reasonably have expected GCC to get this particular case right.

- Have a similar policy of PR# or explanation for 'uninline' too.

I don't think we should just give up on GCC ever getting it right. That way lies madness. As we've often found in the past.

It sounds like you're advocating to set -O3/-finline-functions
by default. Not sure that's a good idea.

-Andi

Signature · 1 line
[email protected]
#254 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 3 lines · Andi Kleen

The proposal was to use -fno-inline-functions-called-once (but the resulting numbers were not promising)

Well, the _optimal_ situation would be to not need it, because gcc does a good job without it. That implies trying to find a better balance between "worth it" and "causes problems".

Rigth now, it does sound like gcc simply doesn't try to balance AT ALL, or balances only when we add some very version-specific random options (ie the stack-usage one). And even those options don't actually make much sense - yes, they "balance" things, but they don't do it in a sensible manner.

For example: stack usage is undeniably a problem (we've hit it over and over again), but it's not about "stack must not be larger than X bytes".

If the call is done unconditionally, then inlining _one_ function will grow the static stack usage of the function we inline into, but it will _not_ grow the dynamic stack usage one whit - so deciding to not inline because of stack usage is pointless.

See? So "stop inlining when you hit a stack limit" IS THE WRONG THING TO DO TOO! Because it just means that the compiler continues to do bad inlining decisions until it hits some magical limit - but since the problem isn't the static stack size of any _single_ function, but the combined stack size of a dynamic chain of them, that's totally idiotic. You still grew the dynamic stack, and you have no way of knowing by how much - the limit on the static one simply has zero bearing what-so-ever on the dynamic one.

So no, "limit static stack usage" is not a good option, because it stops inlining when it doesn't matter (single unconditional call), and doesn't stop inlining when it might (lots of sequential calls, in a deep chain).

The other alternative is to let gcc do what it does, but

(a) remove lots of unnecessary 'inline's. And we should likely do this regardless of any "-fno-inline-functions-called-once" issues.

(b) add lots of 'noinline's to avoid all the cases where gcc screws up so badly that it's either a debugging disaster or an actual correctness issue.

The problem with (b) is that it's a lot of hard thinking, and debugging disasters always happen in code that you didn't realize would be a problem (because if you had, it simply wouldn't be the debugging issue it is).

Linus

#255 lore raw

gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 7 lines · Linus Torvalds
Quoted 3 lines · Andi Kleen

The proposal was to use -fno-inline-functions-called-once (but the resulting numbers were not promising)

Quoted 7 lines

Well, the _optimal_ situation would be to not need it, because gcc does a good job without it. That implies trying to find a better balance between "worth it" and "causes problems".

Rigth now, it does sound like gcc simply doesn't try to balance AT ALL, or balances only when we add some very version-specific random options (ie the stack-usage one).

The gcc 4.3 inliner takes stack growth into account by default (without any special options). I experimented a bit with it when that
was introduced and found the default thresholds are too large for the kernel and don't change the checkstack.pl picture much.

I asked back then and was told --param large-stack-frame is expected to be a reasonable stable --param (as much as these can be) and I did a patch to lower it, but I couldn't get myself to actually submit it [if you really want it I can send it].

But of course that only helps for gcc 4.3+, older gccs would need a different workaround.

On the other hand (my personal opinion, not shared by everyone) is that the ioctl switch stack issue is mostly only a problem with 4K stacks and in the rare cases when I still run 32bit kernels I never set that option because I consider it russian roulette (because there undoutedly dangerous dynamic stack growth cases that checkstack.pl doesn't flag)

Quoted 11 lines

And even those options don't actually make much
sense - yes, they "balance" things, but they don't do it in a sensible manner.

For example: stack usage is undeniably a problem (we've hit it over and over again), but it's not about "stack must not be larger than X bytes".

If the call is done unconditionally, then inlining _one_ function will grow the static stack usage of the function we inline into, but it will _not_ grow the dynamic stack usage one whit - so deciding to not inline because of stack usage is pointless.

Don't think the current inliner takes that into account from a quick look at the sources, although it probably could. Maybe Honza can comment.

But even if it did it could only do that for a single file, but if the function is in a different file gcc doesn't have the information (unless you run with David's --combine hack). This means the kernel developers have to do it anyways.

On the other hand I'm not sure it's that big a problem. Just someone should run make checkstack occasionally and add noinlines to large offenders.

-Andi

[keep quote for Honza's benefit]

Quoted 29 lines

See? So "stop inlining when you hit a stack limit" IS THE WRONG THING TO DO TOO! Because it just means that the compiler continues to do bad inlining decisions until it hits some magical limit - but since the problem isn't the static stack size of any _single_ function, but the combined stack size of a dynamic chain of them, that's totally idiotic. You still grew the dynamic stack, and you have no way of knowing by how much - the limit on the static one simply has zero bearing what-so-ever on the dynamic one.

So no, "limit static stack usage" is not a good option, because it stops inlining when it doesn't matter (single unconditional call), and doesn't stop inlining when it might (lots of sequential calls, in a deep chain).

The other alternative is to let gcc do what it does, but

(a) remove lots of unnecessary 'inline's. And we should likely do this regardless of any "-fno-inline-functions-called-once" issues.

(b) add lots of 'noinline's to avoid all the cases where gcc screws up so badly that it's either a debugging disaster or an actual correctness issue.

The problem with (b) is that it's a lot of hard thinking, and debugging disasters always happen in code that you didn't realize would be a problem (because if you had, it simply wouldn't be the debugging issue it is).

Linus

Signature · 1 line
[email protected]
#256 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 7 lines · Andi Kleen

On the other hand (my personal opinion, not shared by everyone) is that the ioctl switch stack issue is mostly only a problem with 4K stacks and in the rare cases when I still run 32bit kernels I never set that option because I consider it russian roulette (because there undoutedly dangerous dynamic stack growth cases that checkstack.pl doesn't flag)

Isn't the ioctl switch stack issue a separate GCC bug?

It was/is assigning assigning separate space for local variables which are mutually exclusive. So instead of the stack footprint of the function with the switch() being equal to the largest individual stack size of all the subfunctions, it's equal to the _sum_ of the stack sizes of the subfunctions. Even though it'll never use them all at the same time.

Without that bug, it would have been harmless to inline them all.

Signature · 2 lines
David Woodhouse                            Open Source Technology Centre
[email protected]                              Intel Corporation
#257 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 3 lines

Isn't the ioctl switch stack issue a separate GCC bug?

It was/is assigning assigning separate space for local variables which

Was -- i think that got fixed in gcc. But again only in newer versions.

Quoted 7 lines

are mutually exclusive. So instead of the stack footprint of the function with the switch() being equal to the largest individual stack size of all the subfunctions, it's equal to the _sum_ of the stack sizes of the subfunctions. Even though it'll never use them all at the same time.

Without that bug, it would have been harmless to inline them all.

True.

-Andi

Signature · 1 line
[email protected]
#258 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 2 lines · Andi Kleen

Was -- i think that got fixed in gcc. But again only in newer versions.

I doubt it. People have said that about a million times, it has never gotten fixed, and I've never seen any actual proof.

I think that what got fixed was that gcc now at least re-uses stack slots for temporary spills. But only for things that fit in registers - not if you actually had variables that are big enough to be of type MEM. And the latter is what tends to eat stack-space (ie structures etc on stack).

But hey, maybe it really did get fixed. But the last big stack user wasn't that long ago, and I saw it and I have a pretty recent gcc (gcc-4.3.2 right now, it could obviously have been slightly older back a few months ago).

Linus

#259 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 6 lines · Linus Torvalds
Quoted 2 lines · Andi Kleen

Was -- i think that got fixed in gcc. But again only in newer versions.

I doubt it. People have said that about a million times, it has never gotten fixed, and I've never seen any actual proof.

In fact, I just double-checked.

Try this:

	struct a {
		unsigned long array[200];
		int a;
	};

	struct b {
		int b;
		unsigned long array[200];
	};

	extern int fn3(int, void *);
	extern int fn4(int, void *);

	static inline __attribute__((always_inline)) int fn1(int flag)
	{
		struct a a;
		return fn3(flag, &a);
	}

	static inline __attribute__((always_inline)) int fn2(int flag)
	{
		struct b b;
		return fn4(flag, &b);
	}

	int fn(int flag)
	{
		if (flag & 1)
			return fn1(flag);
		return fn2(flag);
	}

(yeah, I made sure it would inline with "always_inline" just so that the issue wouldn't be hidden by any "avoid stack frames" flags).

Gcc creates a big stack frame that contains _both_ 'a' and 'b', and does not merge the allocations together even though they clearly have no overlap in usage. Both 'a' and 'b' get 201 long-words (1608 bytes) of stack, causing the inlined version to have 3kB+ of stack, even though the non-inlined one would never use more than half of it.

So please stop claiming this is fixed. It's not fixed, never has been, and quite frankly, probably never will be because the lifetime analysis is hard enough (ie once you inline and there is any complex usage, CSE etc will quite possibly mix up the lifetimes - the above is clearly not any _realistic_ example).

So even if the above trivial case could be fixed, I suspect a more complex real-life case would still keep the allocations separate. Because merging the allocations and re-using the same stack for both really is pretty non-trivial, and the best solution is to simply not inline.

(And yeah, the above is such an extreme case that gcc seems to realize that it makes no sense to inline because the stack frame is _so_ big. I don't know what the default stack frame limit is, but it's apparently smaller than 1.5kB ;)

Linus

#260 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 5 lines · Linus Torvalds
Quoted 2 lines · Linus Torvalds
Quoted 1 line · Andi Kleen
Quoted 7 lines
Quoted 4 lines
Quoted 1 line

Was -- i think that got fixed in gcc. But again only in newer versions.

I doubt it. People have said that about a million times, it has never gotten fixed, and I've never seen any actual proof.

In fact, I just double-checked.
Try this:

Hmm, I actually had tested it some time ago with my own program (supposed to emulate an ioctl)

extern void f5(char *);

static void f3(void)

{
	char y[100];
	f5(y);
}

static void f2(void)

{
	char x[100];
	f5(x);
}

int f(int cmd)

{
	switch (cmd) { 
	case 1: f3(); break;
	case 2: f2(); break;
	}
	return 1;
}

and with gcc 4.3.1 I get:

.globl f
.type f, @function
f:
.LFB4:

	subq	$120, %rsp			<---- not 200 bytes, stack gets reused; dunno where the 20 comes from
.LCFI0:
	cmpl	$1, %edi
	je	.L4
	cmpl	$2, %edi
	je	.L4
	movl	$1, %eax
	addq	$120, %rsp
	ret
	.p2align 4,,10
	.p2align 3
.L4:
	movq	%rsp, %rdi
	call	f5
	movl	$1, %eax
	addq	$120, %rsp
	ret

.LFE4:

so at least least for this case it works. Your case also doesn't work for me. So it looks like gcc didn't like something you did in your test program. Could be a pointer aliasing problem of some sort.

But yes it doesn't work as well as we hoped.

-Andi

#261 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Andi Kleen

so at least least for this case it works. Your case also doesn't work for me. So it looks like gcc didn't like something you did in your test program.

I very intentionally used _different_ types.

If you use the same type, gcc will apparenrly happily say "hey, I can combine two variables of the same type with different liveness into the same variable".

But that's not the interesting case.

Linus

#262 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 8 lines · Linus Torvalds
Quoted 4 lines · Andi Kleen

so at least least for this case it works. Your case also doesn't work for me. So it looks like gcc didn't like something you did in your test program.

Quoted 5 lines

I very intentionally used _different_ types.

If you use the same type, gcc will apparenrly happily say "hey, I can combine two variables of the same type with different liveness into the same variable".

Confirmed.

Quoted 1 line

But that's not the interesting case.

Weird. I wonder where this strange restriction comes from. It indeed makes this much less useful than it could be :/

-Andi

Signature · 1 line
[email protected]
#263 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Andi Kleen

Weird. I wonder where this strange restriction comes from. It indeed makes this much less useful than it could be :/

Most likely they're collapsing at too early of a stage.

-hpa

Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.
#264 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Andi Kleen
Quoted 12 lines · Andi Kleen
Quoted 10 lines · Linus Torvalds
Quoted 3 lines · Andi Kleen

so at least least for this case it works. Your case also doesn't work for me. So it looks like gcc didn't like something you did in your test program.

I very intentionally used _different_ types.

If you use the same type, gcc will apparenrly happily say "hey, I can combine two variables of the same type with different liveness into the same variable".

Quoted 5 lines

Confirmed.

Quoted 1 line

But that's not the interesting case.

Weird. I wonder where this strange restriction comes from.

Something at the back of my mind said "aliasing".

$ gcc linus.c -O2 -S ; grep subl linus.s
        subl    $1624, %esp
$ gcc linus.c -O2 -S -fno-strict-aliasing; grep subl linus.s
        subl    $824, %esp

That's with 4.3.2.

Bernd

Signature · 4 lines
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif
#265 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 9 lines · Bernd Schmidt

Something at the back of my mind said "aliasing".

$ gcc linus.c -O2 -S ; grep subl linus.s
        subl    $1624, %esp
$ gcc linus.c -O2 -S -fno-strict-aliasing; grep subl linus.s
        subl    $824, %esp

That's with 4.3.2.

Interesting.

Nonsensical, but interesting.

Since they have no overlap in lifetime, confusing this with aliasing is really really broken (if the functions _hadn't_ been inlined, you'd have gotten the same address for the two variables anyway! So anybody who thinks that they need different addresses because they are different types is really really fundmantally confused!).

But your numbers are unambiguous, and I can see the effect of that compiler flag myself.

The good news is that the kernel obviously already uses -fno-strict-aliasing for other reasonds, so we should see this effect already, _despite_ it making no sense. And the stack usage still causes problems.

Oh, and I see why. This test-case shows it clearly.

Note how the max stack usage _should_ be "struct b" + "struct c". Note how it isn't (it's "struct a" + "struct b/c").

So what seems to be going on is that gcc is able to do some per-slot sharing, but if you have one function with a single large entity, and another with a couple of different ones, gcc can't do any smart allocation.

Put another way: gcc doesn't create a "union of the set of different stack usages" (which would be optimal given a single frame, and generate the stack layout of just the maximum possible size), it creates a "set of unions of different stack usages" (which can be optimal in the trivial cases, but not nearly optimal in practical cases).

That explains the ioctl behavior - the structure use is usually pretty complicated (ie it's almost never about just _one_ large stack slot, but the ioctl cases tend to do random stuff with multiple slots).

So it doesn't add up to some horrible maximum of all sizes, but it also doesn't end up coalescing stack usage very well.

Linus
---

struct a {
	int a;
	unsigned long array[200];
};
struct b {
	int b;
	unsigned long array[100];
};
struct c {
	int c;
	unsigned long array[100];
};

extern int fn3(int, void *);
extern int fn4(int, void *);

static inline __attribute__ ((always_inline))
int fn1(int flag)

{
	struct a a;
	return fn3(flag, &a);
}

static inline __attribute__ ((always_inline))
int fn2(int flag)

{
	struct b b;
	struct c c;	
	return fn4(flag, &b) + fn4(flag, &c);
}

int fn(int flag)

{
	fn1(flag);
	if (flag & 1)
		return 0;
	return fn2(flag);
}
#266 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 7 lines · Linus Torvalds
Quoted 7 lines

Something at the back of my mind said "aliasing".

$ gcc linus.c -O2 -S ; grep subl linus.s
        subl    $1624, %esp
$ gcc linus.c -O2 -S -fno-strict-aliasing; grep subl linus.s
        subl    $824, %esp
Quoted 5 lines
Quoted 1 line

That's with 4.3.2.

Interesting.

Nonsensical, but interesting.

What I find nonsensical is that -fno-strict-aliasing generates better code here. Normally one would expect the compiler seeing more aliases with that option and then be more conservative regarding any sharing. But it seems to be the other way round here.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#267 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 11 lines · Andi Kleen
Quoted 10 lines · Linus Torvalds
Quoted 8 lines

Something at the back of my mind said "aliasing".

$ gcc linus.c -O2 -S ; grep subl linus.s
        subl    $1624, %esp
$ gcc linus.c -O2 -S -fno-strict-aliasing; grep subl linus.s
        subl    $824, %esp

That's with 4.3.2.

Interesting.

Quoted 7 lines
Quoted 1 line

Nonsensical, but interesting.

What I find nonsensical is that -fno-strict-aliasing generates better code here. Normally one would expect the compiler seeing more aliases with that option and then be more conservative regarding any sharing. But it seems to be the other way round here.

For this to be convolved with aliasing *AT ALL* indicates this is done incorrectly.

This is about storage allocation, not aliases. Storage allocation only depends on lifetime.

-hpa

#268 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 3 lines · H. Peter Anvin

This is about storage allocation, not aliases. Storage allocation only depends on lifetime.

Well, the thing is, code motion does extend life-times, and if you think you can move stores across each other (even when you can see that they alias statically) due to type-based alias decisions, that does essentially end up making what _used_ to be disjoint lifetimes now be potentially overlapping.

Linus

#269 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 8 lines · Linus Torvalds
Quoted 2 lines

This is about storage allocation, not aliases. Storage allocation only depends on lifetime.

Well, the thing is, code motion does extend life-times, and if you think you can move stores across each other (even when you can see that they alias statically) due to type-based alias decisions, that does essentially end up making what _used_ to be disjoint lifetimes now be potentially overlapping.

Sometimes code motion makes code faster and/or smaller but use more stack space. If you want to keep the stack use down, it blocks some other optimisations.

Register allocation is similar: code motion optimisations may use more registers due to overlapping lifetimes, which causes more register spills and changes the code. The two interact; it's not trivial to optimise fully.

-- Jamie

#270 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Jamie Lokier

Sometimes code motion makes code faster and/or smaller but use more stack space. If you want to keep the stack use down, it blocks some other optimisations.

Uhh. Yes. Compiling is an exercise in trade-offs.

That doesn't mean that you should try to find the STUPID trade-offs, though.

The thing is, there is no excuse for gcc's stupid alias analysis. Other compilers actually take advantage of things like the C standards type alias ambiguity by (a) realizing that it's insane as a general thing and
(b) limiting it to the real special cases, like assuming that pointers to floats and pointers to integers do not alias.

That, btw, is where the whole concept comes from. It should be passed off as an "unsafe FP optimization", where it actually makes sense, exactly like a lot of other unsafe FP optimizations.

Linus

#271 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to H. Peter Anvin
Quoted 3 lines · H. Peter Anvin

This is about storage allocation, not aliases. Storage allocation only depends on lifetime.

Well, the thing is, code motion does extend life-times, and if you think you can move stores across each other (even when you can see that they alias statically) due to type-based alias decisions, that does essentially end up making what _used_ to be disjoint lifetimes now be potentially overlapping.

Linus

#272 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Andi Kleen
Quoted 6 lines · Andi Kleen

What I find nonsensical is that -fno-strict-aliasing generates better code here. Normally one would expect the compiler seeing more aliases with that option and then be more conservative regarding any sharing. But it seems to be the other way round here.

No, that's not the surprising part. And in fact, now that you mention it, I can even tell you why gcc does what it does.

But you'll need some background to it:

Type-based aliasing is _stupid_. It's so incredibly stupid that it's not even funny. It's broken. And gcc took the broken notion, and made it more so by making it a "by-the-letter-of-the-law" thing that makes no sense.

What happens (well, maybe it's fixed, but this was _literally_ what gcc used to do) is that the type-based aliasing overrode everything else, so if two accesses were to different types (and not in a union, and none of the types were "char"), then gcc "knew" that they clearly could not alias, and could thus wildly re-order accesses.

That's INSANE. It's so incredibly insane that people who do that should just be put out of their misery before they can reproduce. But real gcc developers really thought that it makes sense, because the standard allows it, and it gives the compiler the maximal freedom - because it can now do things that are CLEARLY NONSENSICAL.

And to compiler people, being able to do things that are clearly nonsensical seems to often be seen as a really good thing, because it means that they no longer have to worry about whether the end result works or not - they just got permission to do stupid things in the name of optimization.

So gcc did. I know for a _fact_ that gcc would re-order write accesses that were clearly to (statically) the same address. Gcc would suddenly think that

	unsigned long a;

	a = 5;
	*(unsigned short *)&a = 4;

could be re-ordered to set it to 4 first (because clearly they don't alias
- by reading the standard), and then because now the assignment of 'a=5' was later, the assignment of 4 could be elided entirely! And if somebody complains that the compiler is insane, the compiler people would say "nyaah, nyaah, the standards people said we can do this", with absolutely no introspection to ask whether it made any SENSE.

Anyway, once you start doing stupid things like that, and once you start thinking that the standard makes more sense than a human being using his brain for 5 seconds, suddenly you end up in a situation where you can move stores around wildly, and it's all 'correct'.

Now, take my stupid example, and make "fn1()" do "a.a = 1" and make "fn2()" do "b.b = 2", and think about what a compiler that thinks it can re-order the two writes willy-nilly will do?

Right. It will say "ok, a.a and b.b can not alias EVEN IF THEY HAVE STATICALLY THE SAME ADDFRESS ON THE STACK", because they are in two different structres. So we can then re-order the accesses, and move the stores around.

Guess what happens if you have that kind of insane mentality, and you then try to make sure that they really don't alias, so you allocate extra stack space.

The fact is, Linux uses -fno-strict-aliasing for a damn good reason:
because the gcc notion of "strict aliasing" is one huge stinking pile of sh*t. Linux doesn't use that flag because Linux is playing fast and loose, it uses that flag because _not_ using that flag is insane.

Type-based aliasing is unacceptably stupid to begin with, and gcc took that stupidity to totally new heights by making it actually more important than even statically visible aliasing.

Linus

#273 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Andi Kleen
Quoted 6 lines · Andi Kleen

What I find nonsensical is that -fno-strict-aliasing generates better code here. Normally one would expect the compiler seeing more aliases with that option and then be more conservative regarding any sharing. But it seems to be the other way round here.

No, that's not the surprising part. And in fact, now that you mention it, I can even tell you why gcc does what it does.

But you'll need some background to it:

Type-based aliasing is _stupid_. It's so incredibly stupid that it's not even funny. It's broken. And gcc took the broken notion, and made it more so by making it a "by-the-letter-of-the-law" thing that makes no sense.

What happens (well, maybe it's fixed, but this was _literally_ what gcc used to do) is that the type-based aliasing overrode everything else, so if two accesses were to different types (and not in a union, and none of the types were "char"), then gcc "knew" that they clearly could not alias, and could thus wildly re-order accesses.

That's INSANE. It's so incredibly insane that people who do that should just be put out of their misery before they can reproduce. But real gcc developers really thought that it makes sense, because the standard allows it, and it gives the compiler the maximal freedom - because it can now do things that are CLEARLY NONSENSICAL.

And to compiler people, being able to do things that are clearly nonsensical seems to often be seen as a really good thing, because it means that they no longer have to worry about whether the end result works or not - they just got permission to do stupid things in the name of optimization.

So gcc did. I know for a _fact_ that gcc would re-order write accesses that were clearly to (statically) the same address. Gcc would suddenly think that

	unsigned long a;

	a = 5;
	*(unsigned short *)&a = 4;

could be re-ordered to set it to 4 first (because clearly they don't alias
- by reading the standard), and then because now the assignment of 'a=5' was later, the assignment of 4 could be elided entirely! And if somebody complains that the compiler is insane, the compiler people would say "nyaah, nyaah, the standards people said we can do this", with absolutely no introspection to ask whether it made any SENSE.

Anyway, once you start doing stupid things like that, and once you start thinking that the standard makes more sense than a human being using his brain for 5 seconds, suddenly you end up in a situation where you can move stores around wildly, and it's all 'correct'.

Now, take my stupid example, and make "fn1()" do "a.a = 1" and make "fn2()" do "b.b = 2", and think about what a compiler that thinks it can re-order the two writes willy-nilly will do?

Right. It will say "ok, a.a and b.b can not alias EVEN IF THEY HAVE STATICALLY THE SAME ADDFRESS ON THE STACK", because they are in two different structres. So we can then re-order the accesses, and move the stores around.

Guess what happens if you have that kind of insane mentality, and you then try to make sure that they really don't alias, so you allocate extra stack space.

The fact is, Linux uses -fno-strict-aliasing for a damn good reason:
because the gcc notion of "strict aliasing" is one huge stinking pile of sh*t. Linux doesn't use that flag because Linux is playing fast and loose, it uses that flag because _not_ using that flag is insane.

Type-based aliasing is unacceptably stupid to begin with, and gcc took that stupidity to totally new heights by making it actually more important than even statically visible aliasing.

Linus

#274 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Linus Torvalds

Type-based aliasing is unacceptably stupid to begin with, and gcc took that stupidity to totally new heights by making it actually more important than even statically visible aliasing.

Btw, there are good forms of type-based aliasing.

The 'restrict' keyword actually makes sense as a way to say "this pointer points to data that you cannot reach any other way". Of course, almost nobody uses it, and quite frankly, inlining can destroy that one too (a pointer that is restricted in the callEE is not necessarily restricted at all in the callER, and an inliner that doesn't track that subtle distinction will be very unhappy).

So compiler people usually don't much like 'restrict' - because it i very limited (you might even say restricted) in its meaning, and doesn't allow for nearly the same kind of wild optimizations than the insane standard C type-aliasing allows.

The best option, of course, is for a compiler to handle just _static_ alias information that it can prove (whether by use of 'restrict' or by actually doing some fancy real analysis of its own allocations), and letting the hardware do run-time dynamic alias analysis.

I suspect gcc people were a bit stressed out by Itanium support - it's an insane architecture that basically requires an insane compiler for reasonable performance, and I think the Itanium people ended up brain-washing a lot of people who might otherwise have been sane.

So maybe I should blame Intel. Or HP. Because they almost certainly were at least a _part_ reason for bad compiler decisions.

Linus

#275 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 1 line · Linus Torvalds

But you'll need some background to it:

You paint a somewhat one-sided picture bordering on FUD.

Quoted 1 line

Type-based aliasing is _stupid_.

Type-based aliasing is simply an application of the language definition, and depending on the compiled application and/or target architecture, it can be essential for performance.

It's _hard_ to tell whether two memory accesses can possibly conflict, and the ability to decide based on type makes a vast difference. This is not, as you suggest in another post, simply a mild inconvenience for the compiler that restricts scheduling a bit and forces the hardware sort it out at run-time. Too lazy to construct one myself, I googled for examples, and here's a trivial one that shows how it affects the ability of the compiler to eliminate memory references:

  typedef struct
  {
    short a, b, c;
  } Sample;

void test(int* values, Sample *uniform, int count) {
int i;

   for (i=0;i<count;i++)
   {
     values[i] += uniform->b;
   }
  }

Type-based aliasing is what allows you to eliminate a load from the loop. Most users probably expect this kind of optimization from their compiler, and it'll make a difference not just on Itanium.

I'll grant you that if you're writing a kernel or maybe a malloc library, you have reason to be unhappy about it. But that's what compiler switches are for: -fno-strict-aliasing allows you to write code in a superset of C.

Quoted 11 lines

So gcc did. I know for a _fact_ that gcc would re-order write accesses that were clearly to (statically) the same address. Gcc would suddenly think that

	unsigned long a;

	a = 5;
	*(unsigned short *)&a = 4;

could be re-ordered to set it to 4 first (because clearly they don't alias
- by reading the standard),

To be precise, what the standard says is that your example is not C, and therefore has no meaning. While this kind of thing does occur in the wild, it is infrequent, and the programs that used this kind of code have been fixed over the years.

gcc even warns about code such as the above with -Wall, which makes this even more of a non-issue.

linus2.c: In function 'foo':
linus2.c:6: warning: dereferencing type-punned pointer will break strict-aliasing rules

Quoted 5 lines

and then because now the assignment of 'a=5'
was later, the assignment of 4 could be elided entirely! And if somebody complains that the compiler is insane, the compiler people would say "nyaah, nyaah, the standards people said we can do this", with absolutely no introspection to ask whether it made any SENSE.

The thing is, yours is a trivial example, but try to think further: in the general case the compiler can't tell whether two accesses can go to the same address at runtime. If it could, we wouldn't be having this discussion; I'm pretty sure this question reduces to the halting problem. That's why the compiler must have a set of conservative rules that allow it to decide that two accesses definitely _can't_ conflict. For all standards conforming programs, type based aliasing is such a rule. You could add code to weaken it by also checking against the address, but since that cannot be a reliable test that catches all problematic cases, what would be the point?

So, in effect, if you're arguing that the compiler should detect the above case and override the type-based aliasing based on the known address, you're arguing that only subtle bugs in the application should be exposed, not the obvious ones. If you're arguing we should do away with type-based aliasing altogether, you're ignoring the fact that there are (a majority of) other users of gcc than the Linux kernel, they write standards-conforming C, and they tend to worry about performance of compiled code.

Quoted 4 lines

The fact is, Linux uses -fno-strict-aliasing for a damn good reason:
because the gcc notion of "strict aliasing" is one huge stinking pile of sh*t. Linux doesn't use that flag because Linux is playing fast and loose, it uses that flag because _not_ using that flag is insane.

Not using this flag works for pretty much all user space applications these days.

Quoted 3 lines

Type-based aliasing is unacceptably stupid to begin with, and gcc took that stupidity to totally new heights by making it actually more important than even statically visible aliasing.

gcc makes use of statically visible aliasing if it can use it to prove that two accesses can't conflict even if they have the same type, but it's vastly less powerful than type based analysis. Since it's impossible in general to decide that two accesses must conflict, trying to avoid transformations based on such an attempt is completely senseless. Trying to do so would have no effect for conforming C programs, and avoid only a subset of the problematic cases for other programs, so it's a waste of time.

So, to summarize: strict aliasing works for nearly every application these days, there's a compiler switch for the rest to turn it off, it can be a serious performance improvement, and the compiler warns about dangerous constructs. That makes the issue a little less black and white than "type based aliasing is stupid".

Bernd

Signature · 4 lines
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif
#276 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Bernd Schmidt

Too lazy to construct one myself, I googled for examples, and here's a trivial one that shows how it affects the ability of the compiler to eliminate memory references:

Do you really think this is realistic or even relevant?

The fact is

(a) most people use similar types, so your example of "short" vs "int" is actually not very common. Type-based alias analysis is wonderful for finding specific examples of something you can optimize, but it's not actually all that wonderful in general. It _particularly_ isn't wonderful once you start looking at the downsides.

When you're adding arrays of integers, you're usually adding integers. Not "short"s. The shorts may be a great example of a special case, but it's a special case!

(b) instructions with memory accesses aren't the problem - instructions that take cache misses are. Your example is an excellent example of that - eliding the simple load out of the loop makes just about absolutely _zero_ difference in any somewhat more realistic scenario, because that one isn't the one that is going to make any real difference anyway.

The thing is, the way to optimize for modern CPU's isn't to worry over-much about instruction scheduling. Yes, it matters for the broken ones, but it matters in the embedded world where you still find in-order CPU's, and there the size of code etc matters even more.

Quoted 4 lines

I'll grant you that if you're writing a kernel or maybe a malloc library, you have reason to be unhappy about it. But that's what compiler switches are for: -fno-strict-aliasing allows you to write code in a superset of C.

Oh, I'd use that flag regardless yes. But what you didn't seem to react to was that gcc - for no valid reason what-so-ever - actually trusts (or at least trusted: I haven't looked at that code for years) provably true static alias information _less_ than the idiotic weaker type-based one.

You make all this noise about how type-based alias analysis improves code, but then you can't seem to just look at the example I gave you. Type-based alias analysis didn't improve code. It just made things worse, for no actual gain. Moving those accesses to the stack around just causes worse behavior, and a bigger stack frame, which causes more cache misses.

[ Again, I do admit that kernel code is "different": we tend to have a
cold stack, in ways that many other code sequences do not have. System code tends to get a lot more I$ and D$ misses. Deep call-chains _will_ take cache misses on the stack, simply because the user will do things between system calls or page faults that almost guarantees that things are not in L1, and often not in L2 either.

Also, sadly, microbenchmarks often hide this, since they are often exactly the unrealistic kinds of back-to-back system calls that almost no real program ever has, since real programs actually _do_ something with the data. ]

My point is, you're making all these arguments and avoiding looking at the downsides of what you are arguing for.

So we use -Os - because it generally generates better (and simpler) code. We use -fno-strict-alias for the same reason.

Linus

#277 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

<comic relief>

Quoted 1 line · Linus Torvalds

code tends to get a lot more I$ and D$ misses. Deep call-chains _will_

I feel like an idiot that I never realized that "I$" meant "instruction cache" until now :-p

</comic relief>

-- Steve

#278 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Bernd Schmidt
Quoted 12 lines · Bernd Schmidt
Quoted 1 line · Linus Torvalds

But you'll need some background to it:

You paint a somewhat one-sided picture bordering on FUD.

Quoted 1 line

Type-based aliasing is _stupid_.

Type-based aliasing is simply an application of the language definition, and depending on the compiled application and/or target architecture, it can be essential for performance.
[...]

Quoted 5 lines

So, to summarize: strict aliasing works for nearly every application these days, there's a compiler switch for the rest to turn it off, it can be a serious performance improvement, and the compiler warns about dangerous constructs. That makes the issue a little less black and white than "type based aliasing is stupid".

i did some size measurements. Latest kernel, gcc 4.3.2, x86 defconfig, vmlinux built with strict-aliasing optimizations and without.

The image sizes are:

text data bss dec hex filename
6997984 1635900 1322376 9956260 97eba4 vmlinux.gcc.-fno-strict-aliasing 6985962 1635884 1322376 9944222 97bc9e vmlinux.gcc.strict-aliasing

that's 0.17% of a size win only.

The cost? More than _300_ new "type-punned" warnings during the kernel build (3000 altogether, including duplicates that trigger in multiple object files) - more than _1000_ new warnings (more than 10,000 total) in an allyesconfig build.

That is a _ton_ of effort for a ~0.1% category win. Often in historic code that has been working well and now got broken by gcc.

I think this feature has been over-sold while it under-performs. You also significantly weakened the utility of the C language for lowlevel hardware-conscious programming as a result (which is the strongest side of C by far).

Type based aliasing should at most have been an opt-in for code that cares, not a turned-on-by-default feature for everyone.

You already dismissed concerns in this thread by suggesting that Linux is just one of many projects, but that way you dismiss 1) the largest OSS project by linecount 2) one of the most performance-optimized pieces of OSS software in existence.

I.e. you dismiss what should have been GCC's strongest supporter, ally, test-field and early prototype tester. A lot of folks in the kernel look at the assembly level on a daily basis, they run the latest hardware and they see where GCC messes up. By dismissing Linux you cut yourself off from a lot of development power, you cut yourself off from a lot of enthusiasm and you miss out on a lot of dynamism that would naturally help GCC too.

I.e. almost by definition you cannot possibly be interested in writing the best compiler on the planet.

Ingo

#279 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 10 lines · Ingo Molnar
Quoted 4 lines · Bernd Schmidt
Quoted 1 line · Linus Torvalds

But you'll need some background to it:

You paint a somewhat one-sided picture bordering on FUD.

Type based aliasing should at most have been an opt-in for code that cares, not a turned-on-by-default feature for everyone.

I want to know what is the problem with the restrict keyword? I'm sure I've read Linus ranting about how bad it is in the past... it seems like a nice opt-in thing that can be used where the aliases are verified and the code is particularly performance critical...

#280 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Nick Piggin

I want to know what is the problem with the restrict keyword? I'm sure I've read Linus ranting about how bad it is in the past...

No, I don't think I've ranted about 'restrict'. I think it's a reasonable solution for performance-critical code, and unlike the whole type-aliasing model, it actually works for the _sane_ cases (ie doing some operation over two arrays of the same type, and letting the compiler know that it can access the arrays without fearing that writing to one would affect reading from the other).

The problem with 'restrict' is that almost nobody uses it, and it does obviously require programmer input rather than the compiler doing it automatically. But it should work well as a way to get Fortran-like performance from HPC workloads written in C - which is where most of the people are who really want the alias analysis.

Quoted 2 lines

it seems like a nice opt-in thing that can be used where the aliases are verified and the code is particularly performance critical...

Yes. I think we could use it in the kernel, although I'm not sure how many cases we would ever find where we really care.

Linus

#281 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 15 lines · Linus Torvalds
Quoted 4 lines · Nick Piggin

I want to know what is the problem with the restrict keyword? I'm sure I've read Linus ranting about how bad it is in the past...

No, I don't think I've ranted about 'restrict'. I think it's a reasonable solution for performance-critical code, and unlike the whole type-aliasing model, it actually works for the _sane_ cases (ie doing some operation over two arrays of the same type, and letting the compiler know that it can access the arrays without fearing that writing to one would affect reading from the other).

Quoted 5 lines

The problem with 'restrict' is that almost nobody uses it, and it does obviously require programmer input rather than the compiler doing it automatically. But it should work well as a way to get Fortran-like performance from HPC workloads written in C - which is where most of the people are who really want the alias analysis.

OK, that makes sense. I just had a vague feeling that you disliked it.

Quoted 5 lines
Quoted 2 lines

it seems like a nice opt-in thing that can be used where the aliases are verified and the code is particularly performance critical...

Yes. I think we could use it in the kernel, although I'm not sure how many cases we would ever find where we really care.

Yeah, we don't tend to do a lot of intensive data processing, so it is normally the cache misses that hurt most as you noted earlier.

Some places it might be appropriate, though. It might be nice if it can bring code size down too...

#282 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 11 lines · Nick Piggin
Quoted 5 lines
Quoted 2 lines

it seems like a nice opt-in thing that can be used where the aliases are verified and the code is particularly performance critical...

Yes. I think we could use it in the kernel, although I'm not sure how many cases we would ever find where we really care.

Yeah, we don't tend to do a lot of intensive data processing, so it is normally the cache misses that hurt most as you noted earlier.

Some places it might be appropriate, though. It might be nice if it can bring code size down too...

I checked, its size effects were miniscule [0.17%] on the x86 defconfig kernel and it seems to be a clear loss in total cost as there would be an ongoing maintenance cost of this weird new variant of C that language lawyers legislated out of thin air and which departs so significantly from time-tested C coding concepts and practices.

We'd have to work around aliasing warnings of the compiler again and again with no upside and in fact i'd argue that the resulting code is _less_ clean.

The lack of data processing complexity in the kernel is not a surprise:
the kernel is really just a conduit/abstractor between hw and apps, and rarely generates genuinely new information. (In fact it can be generally considered a broken system call concept if such data processing _has_ to be conducted somewhere in the kernel.)

( Notable exceptions would be the crypto code and the RAID5 [XOR checksum]
and RAID6 [polinomial checksums] code - but those tend to be seriously hand-optimized already, with the most critical bits written in assembly. )

Ingo

#283 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 12 lines · Ingo Molnar
Quoted 9 lines · Nick Piggin
Quoted 5 lines
Quoted 2 lines

it seems like a nice opt-in thing that can be used where the aliases are verified and the code is particularly performance critical...

Yes. I think we could use it in the kernel, although I'm not sure how many cases we would ever find where we really care.

Yeah, we don't tend to do a lot of intensive data processing, so it is normally the cache misses that hurt most as you noted earlier.

Quoted 6 lines
Quoted 2 lines

Some places it might be appropriate, though. It might be nice if it can bring code size down too...

I checked, its size effects were miniscule [0.17%] on the x86 defconfig kernel and it seems to be a clear loss in total cost as there would be an ongoing maintenance cost

They were talking about 'restrict', not strict-aliasing. Where it can be used, it's going to give you optimisations that strict-aliasing can't.

Signature · 2 lines
David Woodhouse                            Open Source Technology Centre
[email protected]                              Intel Corporation
#284 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 16 lines · David Woodhouse
Quoted 15 lines · Ingo Molnar
Quoted 11 lines · Nick Piggin
Quoted 5 lines
Quoted 2 lines

it seems like a nice opt-in thing that can be used where the aliases are verified and the code is particularly performance critical...

Yes. I think we could use it in the kernel, although I'm not sure how many cases we would ever find where we really care.

Yeah, we don't tend to do a lot of intensive data processing, so it is normally the cache misses that hurt most as you noted earlier.

Some places it might be appropriate, though. It might be nice if it can bring code size down too...

Quoted 6 lines
Quoted 3 lines

I checked, its size effects were miniscule [0.17%] on the x86 defconfig kernel and it seems to be a clear loss in total cost as there would be an ongoing maintenance cost

They were talking about 'restrict', not strict-aliasing. Where it can be used, it's going to give you optimisations that strict-aliasing can't.

the two are obviously related (just that the 'restrict' keyword can be used for same-type pointers so it gives even broader leeway) so i used the 0.17% figure i already had to give a ballpark figure about what such type of optimizations can bring us in general.

(Different-type pointer uses are a common pattern: we have a lot of places where we have pointers to structures with different types so strict-aliasing optimization opportunities apply quite broadly already.)

Ingo

#285 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Ingo Molnar

(Different-type pointer uses are a common pattern: we have a lot of places where we have pointers to structures with different types so strict-aliasing optimization opportunities apply quite broadly already.)

Yes and no.

It's true that the kernel in general uses mostly pointers through structures that can help the type-based thing.

However, the most common and important cases are actually the very same structures. In particular, things like <linux/list.h>. Same "struct list", often embedded into another case of the same struct.

And that's where "restrict" can actually help. It might be interesting to see, for example, if it makes any difference to add a "restrict" qualifier to the "new" pointer in __list_add(). That might give the compiler the ability to schedule the stores to next->prev and prev->next differently, and maybe it could matter?

It probably is not noticeable. The big reason for wanting to do alias analysis tends to not be thatt kind of code at all, but the cases where you can do much bigger simplifications, or on in-order machines where you really want to hoist things like FP loads early and FP stores late, and alias analysis (and here type-based is more reasonable) shows that the FP accesses cannot alias with the integer accesses around it.

In x86, I doubt _any_ amount of alias analysis makes a hug difference (as long as the compiler at least doesn't think that local variable spills can alias with anything else). Not enough registers, and generally pretty aggressively OoO (with alias analysis in hardware) makes for a much less sensitive platform.

Linus

#286 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 22 lines · Linus Torvalds
Quoted 5 lines · Ingo Molnar

(Different-type pointer uses are a common pattern: we have a lot of places where we have pointers to structures with different types so strict-aliasing optimization opportunities apply quite broadly already.)

Yes and no.

It's true that the kernel in general uses mostly pointers through structures that can help the type-based thing.

However, the most common and important cases are actually the very same structures. In particular, things like <linux/list.h>. Same "struct list", often embedded into another case of the same struct.

And that's where "restrict" can actually help. It might be interesting to see, for example, if it makes any difference to add a "restrict" qualifier to the "new" pointer in __list_add(). That might give the compiler the ability to schedule the stores to next->prev and prev->next differently, and maybe it could matter?

Quoted 6 lines

It probably is not noticeable. The big reason for wanting to do alias analysis tends to not be thatt kind of code at all, but the cases where you can do much bigger simplifications, or on in-order machines where you really want to hoist things like FP loads early and FP stores late, and alias analysis (and here type-based is more reasonable) shows that the FP accesses cannot alias with the integer accesses around it.

Hm, GCC uses __restrict__, right?

The patch below makes no difference at all on an x86 defconfig:

vmlinux:
text data bss dec hex filename
7253544 1641812 1324296 10219652 9bf084 vmlinux.before
7253544 1641812 1324296 10219652 9bf084 vmlinux.after

not a single instruction was changed:

--- vmlinux.before.asm
+++ vmlinux.after.asm
@@ -1,5 +1,5 @@

-vmlinux.before: file format elf64-x86-64
+vmlinux.after: file format elf64-x86-64

I'm wondering whether there's any internal tie-up between alias analysis and the __restrict__ keyword - so if we turn off aliasing optimizations the __restrict__ keyword's optimizations are turned off as well.

Nope, with aliasing optimizations turned back on there's still no change on the x86 defconfig:

text data bss dec hex filename
7240893 1641796 1324296 10206985 9bbf09 vmlinux.before
7240893 1641796 1324296 10206985 9bbf09 vmlinux.after

GCC 4.3.2. Maybe i missed something obvious?

Ingo

---
 include/linux/list.h |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/list.h +2 -2
Index: linux/include/linux/list.h
===================================================================
@@ -38,7 +38,7 @@ static inline void INIT_LIST_HEAD(struct
  * the prev/next entries already!
  */
 #ifndef CONFIG_DEBUG_LIST
-static inline void __list_add(struct list_head *new,
+static inline void __list_add(struct list_head * __restrict__ new,
 			      struct list_head *prev,
 			      struct list_head *next)
 {
@@ -48,7 +48,7 @@ static inline void __list_add(struct lis
 	prev->next = new;
 }
 #else
-extern void __list_add(struct list_head *new,
+extern void __list_add(struct list_head * __restrict__ new,
 			      struct list_head *prev,
 			      struct list_head *next);
 #endif
#287 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 5 lines · Ingo Molnar

Hm, GCC uses __restrict__, right?

I'm wondering whether there's any internal tie-up between alias analysis and the __restrict__ keyword - so if we turn off aliasing optimizations the __restrict__ keyword's optimizations are turned off as well.

Actually I suspect that "restrict" makes little difference for inlines or even statics, since gcc generally can do alias analysis fine there. However, in the presence of an intermodule function call, all alias analysis is off. This is presumably why type-based analysis is used at all ... to at least be able to a modicum of, say, loop invariant removal in the presence of a library call. This is also where "restrict" comes into play.

-hpa

#288 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 1 line

GCC 4.3.2. Maybe i missed something obvious?

The typical use case of restrict is to tell it that multiple given arrays are independent and then give the loop optimizer more freedom to handle expressions in the loop that accesses these arrays.

Since there are no loops in the list functions nothing changed.

Ok presumably there are some other optimizations which rely on that alias information too, but again the list_* stuff is probably too simple to trigger any of them.

-Andi

#289 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 7 lines · Andi Kleen
Quoted 1 line

GCC 4.3.2. Maybe i missed something obvious?

The typical use case of restrict is to tell it that multiple given arrays are independent and then give the loop optimizer more freedom to handle expressions in the loop that accesses these arrays.

Quoted 5 lines

Since there are no loops in the list functions nothing changed.

Ok presumably there are some other optimizations which rely on that alias information too, but again the list_* stuff is probably too simple to trigger any of them.

Any function that does several interleaved loads and stores through different pointers could have much more freedom to move loads early and stores late. Big OOOE CPUs won't care so much, but embedded and things (including in-order x86) are very important users of the kernel.

#290 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 10 lines · Nick Piggin
Quoted 9 lines · Andi Kleen
Quoted 1 line

GCC 4.3.2. Maybe i missed something obvious?

The typical use case of restrict is to tell it that multiple given arrays are independent and then give the loop optimizer more freedom to handle expressions in the loop that accesses these arrays.

Since there are no loops in the list functions nothing changed.

Quoted 7 lines
Quoted 3 lines

Ok presumably there are some other optimizations which rely on that alias information too, but again the list_* stuff is probably too simple to trigger any of them.

Any function that does several interleaved loads and stores through different pointers could have much more freedom to move loads early and stores late.

For once that would require more live registers. It's not a clear and obvious win. Especially not if you have only very little registers, like on 32bit x86.

Then it would typically increase code size.

Then x86s tend to have very very fast L1 caches and if something is not in L1 on reads then the cost of fetching something for a read dwarfs the few cycles you can typically get out of this.

And lastly even on a in order system stores can be typically queued without stalling, so it doesn't hurt to do them early.

Also at least x86 gcc normally doesn't do scheduling beyond basic blocks, so any if () shuts it up.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#291 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 19 lines · Andi Kleen
Quoted 10 lines · Nick Piggin
Quoted 9 lines · Andi Kleen
Quoted 1 line

GCC 4.3.2. Maybe i missed something obvious?

The typical use case of restrict is to tell it that multiple given arrays are independent and then give the loop optimizer more freedom to handle expressions in the loop that accesses these arrays.

Since there are no loops in the list functions nothing changed.

Quoted 7 lines
Quoted 3 lines

Ok presumably there are some other optimizations which rely on that alias information too, but again the list_* stuff is probably too simple to trigger any of them.

Any function that does several interleaved loads and stores through different pointers could have much more freedom to move loads early and stores late.

Quoted 5 lines

For once that would require more live registers. It's not a clear and obvious win. Especially not if you have only very little registers, like on 32bit x86.

Then it would typically increase code size.

The point is that the compiler is then free to do it. If things slow down after the compiler gets *more* information, then that is a problem with the compiler heuristics rather than the information we give it.

Quoted 4 lines

Then x86s tend to have very very fast L1 caches and if something is not in L1 on reads then the cost of fetching something for a read dwarfs the few cycles you can typically get out of this.

Well most architectures have L1 caches of several cycles. And L2 miss typically means going to L2 which in some cases the compiler is expected to attempt to cover as much as possible (eg in-order architectures).

If the caches are missed completely, then especially with an in-order architecture, you want to issue as many parallel loads as possible during the stall. If the compiler can't resolve aliases, then it simply won't be able to bring some of those loads forward.

Quoted 3 lines

And lastly even on a in order system stores can be typically queued without stalling, so it doesn't hurt to do them early.

Store queues are, what? On the order of tens of entries for big power hungry x86? I'd guess much smaller for low power in-order x86 and ARM etc. These can definitely fill up and stall, so you still want to get loads out early if possible.

Even a lot of OOOE CPUs I think won't have the best alias anaysis, so all else being equal, it wouldn't hurt them to move loads earlier.

Quoted 2 lines

Also at least x86 gcc normally doesn't do scheduling beyond basic blocks, so any if () shuts it up.

I don't think any of this is a reason not to use restrict, though. But... there are so many places we could add it to the kernel, and probably so few where it makes much difference. Maybe it should be able to help some critical core code, though.

#292 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines

The point is that the compiler is then free to do it. If things slow down after the compiler gets *more* information, then that is a problem with the compiler heuristics rather than the information we give it.

The point was the -Os disables it typically then. (not always, compiler heuristics are far from perfect)

Quoted 11 lines
Quoted 6 lines

Then x86s tend to have very very fast L1 caches and if something is not in L1 on reads then the cost of fetching something for a read dwarfs the few cycles you can typically get out of this.

Well most architectures have L1 caches of several cycles. And L2 miss typically means going to L2 which in some cases the compiler is expected to attempt to cover as much as possible (eg in-order architectures).

L2 cache is so much slower that scheduling a few instructions more doesn't help much.

Quoted 5 lines

stall, so you still want to get loads out early if possible.

Even a lot of OOOE CPUs I think won't have the best alias anaysis, so all else being equal, it wouldn't hurt them to move loads earlier.

Hmm, but if the load is nearby it won't matter if a store is in the middle, because the CPU will just execute over it.

The real big win is if you do some computation inbetween, but at least for typical list manipulation there isn't really any.

Quoted 7 lines
Quoted 2 lines

Also at least x86 gcc normally doesn't do scheduling beyond basic blocks, so any if () shuts it up.

I don't think any of this is a reason not to use restrict, though. But... there are so many places we could add it to the kernel, and probably so few where it makes much difference. Maybe it should be able to help some critical core code, though.

Frankly I think it would be another unlikely().

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#293 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 7 lines · Andi Kleen
Quoted 4 lines

The point is that the compiler is then free to do it. If things slow down after the compiler gets *more* information, then that is a problem with the compiler heuristics rather than the information we give it.

The point was the -Os disables it typically then. (not always, compiler heuristics are far from perfect)

That'd be just another gcc failing. If it can make the code faster without a size increase, then it should (of course if it has to start spilling registers etc. then that's a different matter, but we're not talking about only 32-bit x86 here).

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

Then x86s tend to have very very fast L1 caches and if something is not in L1 on reads then the cost of fetching something for a read dwarfs the few cycles you can typically get out of this.

Quoted 7 lines
Quoted 4 lines

Well most architectures have L1 caches of several cycles. And L2 miss typically means going to L2 which in some cases the compiler is expected to attempt to cover as much as possible (eg in-order architectures).

L2 cache is so much slower that scheduling a few instructions more doesn't help much.

I think on a lot of CPUs that is actually not the case. Including on Nehalem and Montecito CPUs where it is what, like under 15 cycles?

Even in cases where you have a high latency LLC or go to memory, you want to be able to start as many loads as possible before stalling. Especially for in-order architectures, but even OOOE can stall if it can't resolve store addresses early enough or speculate them.

Quoted 9 lines
Quoted 5 lines

stall, so you still want to get loads out early if possible.

Even a lot of OOOE CPUs I think won't have the best alias anaysis, so all else being equal, it wouldn't hurt them to move loads earlier.

Hmm, but if the load is nearby it won't matter if a store is in the middle, because the CPU will just execute over it.

If the address is not known or the store buffer fills up etc then it may not be able to. It could even be hundreds of instructions here too much for an OOOE processor window. We have a lot of huge functions (although granted they'll often contain barriers for other reasons like locks or function calls anyway).

Quoted 3 lines

The real big win is if you do some computation inbetween, but at least for typical list manipulation there isn't really any.

Well, I have a feeling that the MLP side of it could be more significant than ILP. But no data.

#294 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 1 line

The problem with 'restrict' is that almost nobody uses it, and it does

Also gcc traditionally didn't do a very good job using it (this might be better in the very latest versions). At least some of the 3.x often discarded this information.

Quoted 3 lines

automatically. But it should work well as a way to get Fortran-like performance from HPC workloads written in C - which is where most of the people are who really want the alias analysis.

It's more than just HPC -- a lot of code has critical loops.

Quoted 5 lines
Quoted 2 lines

it seems like a nice opt-in thing that can be used where the aliases are verified and the code is particularly performance critical...

Yes. I think we could use it in the kernel, although I'm not sure how many cases we would ever find where we really care.

Very little I suspect. Also the optimizations that gcc does with this often increase the code size. While that can be a win, with people judging gcc's output apparently *ONLY* on the code size as seen in this thread[1] it would obviously not compete well.

-Andi

[1] although there are compilers around that generate smaller code than gcc at its best.

Signature · 1 line
[email protected] -- Speaking for myself only.
#295 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 15 lines · Linus Torvalds
Quoted 4 lines · Nick Piggin

I want to know what is the problem with the restrict keyword? I'm sure I've read Linus ranting about how bad it is in the past...

No, I don't think I've ranted about 'restrict'. I think it's a reasonable solution for performance-critical code, and unlike the whole type-aliasing model, it actually works for the _sane_ cases (ie doing some operation over two arrays of the same type, and letting the compiler know that it can access the arrays without fearing that writing to one would affect reading from the other).

Quoted 5 lines

The problem with 'restrict' is that almost nobody uses it, and it does obviously require programmer input rather than the compiler doing it automatically. But it should work well as a way to get Fortran-like performance from HPC workloads written in C - which is where most of the people are who really want the alias analysis.

while working in my college thesis, a fortran HPC workload (10k lines of fortran), converted to C resulted in performance speedups. this was with gcc 3.4.
A simple f2c conversion + adaptations, resulted in a considerable speedup. (20% IIRC).
The conversion was not done by performance reasons, the extra performance was simply a unexpected, but quite nice outcome. Just to let you guys know, that even with gcc3.4, gcc of C code ran faster than gfortran of the equiv. fortran code.

... pushing the optimization engine further (-march tunning and -O3) resulted in bad data.
But I can't swear by the correctness of some of the computations with REAL's made in the original fortran code.

Quoted 13 lines
Quoted 3 lines

it seems like a nice opt-in thing that can be used where the aliases are verified and the code is particularly performance critical...

Yes. I think we could use it in the kernel, although I'm not sure how many cases we would ever find where we really care.

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 1 line
Miguel Sousa Filipe
#296 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 13 lines · Linus Torvalds
Quoted 8 lines · Bernd Schmidt

Something at the back of my mind said "aliasing".

$ gcc linus.c -O2 -S ; grep subl linus.s
        subl    $1624, %esp
$ gcc linus.c -O2 -S -fno-strict-aliasing; grep subl linus.s
        subl    $824, %esp

That's with 4.3.2.

Interesting.

Quoted 7 lines

Nonsensical, but interesting.

Since they have no overlap in lifetime, confusing this with aliasing is really really broken (if the functions _hadn't_ been inlined, you'd have gotten the same address for the two variables anyway! So anybody who thinks that they need different addresses because they are different types is really really fundmantally confused!).

I've never really looked at the stack slot sharing code. But I think it's not hard to see what's going on: "no overlap in lifetime" may be a temporary state. Let's say you have

{
variable_of_some_type a;
writes to a;
other stuff;
reads from a;
}
{
variable_of_some_other_type b;
writes to b;
other stuff;
reads from b;
}

At the point where the compiler generates RTL, stack space has to be allocated for variables A and B. At this point the lifetimes are non-overlapping. However, if the compiler chooses to put them into the same stack location, the RTL-based alias analysis will happily conclude (based on the differing types) that the reads from A and the writes to B can't possibly conflict, and some passes may end up reordering them. End result: overlapping lifetimes and overlapping stack slots. Oops.

Bernd

Signature · 4 lines
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif
#297 lore raw

Re: gcc inlining heuristics was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 6 lines · Bernd Schmidt

However, if the compiler chooses to put them into the same stack location, the RTL-based alias analysis will happily conclude (based on the differing types) that the reads from A and the writes to B can't possibly conflict, and some passes may end up reordering them. End
result: overlapping lifetimes and overlapping stack slots. Oops.

Yes, I came to the same conclusion.

Of course, I knew a-priori that the real bug was using type-based alais analysis to make (statically visible) aliasing decisions, but I realize that there are people who never understood things like that. Sadly, some of them worked on gcc.

Linus

#298 lore raw

Hard to debug kernel issues (was Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning)

In reply to David Woodhouse
Quoted 2 lines · David Woodhouse

Sometimes you weren't going to get a backtrace if something goes wrong _anyway_.

Case in point - we've been struggling with some of our SuperMicro based systems with AMD Barcelona B3 k10h CPUs *turning themselves off* when running various HPC applications.

Nothing in the kernel logs, nothing in the IPMI controller logs. It's just like someone has wandered in and held the power button down (and no, it's not that).

It's been driving us up the wall.

We'd assumed it was a hardware issue as it was happening with all sorts of kernels but today we tried 2.6.29-rc1 "just in case" and I've not been able to reproduce the crash (yet) on a node I can crash in about 30 seconds, and rebooting back into 2.6.28 makes it crash again.

If the test boxes are still alive tomorrow I might see if we can attempt some form of a reverse bisect to track down what commit fixed it (git doesn't seem to support that so we've going to have to invert the good/bad commands).

cheers,
Chris

Signature · 4 lines
 Chris Samuel  :  http://www.csamuel.org/  :  Melbourne, VIC

This email may come with a PGP signature as a file. Do not panic.
For more info see: http://en.wikipedia.org/wiki/OpenPGP
#299 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 7 lines · Ingo Molnar

- Headers could probably go back to 'extern inline' again. At not small expense - we just finished moving to 'static inline'. We'd need to guarantee a library instantiation for every header include file - this is an additional mechanism with additional introduction complexities and an ongoing maintenance cost.

I think I have a pretty clean idea for how to do this. I'm going to experiment with it over the next few days.

-hpa

Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.
#300 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 4 lines · Ingo Molnar

- Perhaps we could introduce a name for the first category: __must_inline? __should_inline? Not because it wouldnt mean 'always', but because it is 'always inline' for another reason than the correctless __always_inline.

I think you're thinking about this the wrong way.

"inline" is a pretty damn strong hint already.

If you want a weaker one, make it _weaker_ instead of trying to use superlatives like "super_inline" or "must_inline" or whatever.

So I'd suggest:

- keep "inline" as being a strong hint. In fact, I'd suggest it not be a hint at all - when we say "inline", we mean it. No ambiguity _anywhere_, and no need for idiotic "I really really REALLY mean it" versions.

- add a "maybe_inline" or "inline_hint" to mean that "ok, compiler, maybe this is worth inlining, but I'll leave the final choice to you".

That would get rid of the whole rationale for OPTIMIZE_INLINING=y, because at that point, it's no longer potentially a correctness issue. At that point, if we let gcc optimize things, it was a per-call-site conscious decision.

Linus

#301 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 7 lines · Linus Torvalds
Quoted 4 lines · Ingo Molnar

So, should we not remove CONFIG_OPTIMIZE_INLINING, then the correct one would be to mark it __always_inline [__asm_inline is senseless there], or the second patch below that changes the bit parameter to unsigned int.

Well, I certainly don't want to _remove_ the "inline" like your patch did.

hm, that was a bug that i noticed and fixed in the second, fuller version of the patch i sent - which converts all the 'int nr' instances in bitops.h to 'unsigned int nr'.

This is the only instance where the integer type of 'nr' matters in practice though, due to the modulo arithmetics. But for cleanliness reasons we want to do the full patch, to have a standard type signature for these bitop methods.

Quoted 2 lines

Other gcc versions will care. But I committed the pure "change to unsigned" part.

thanks! I'll clean up the rest - the second patch will now conflict (trivially). I also wanted to check the whole file more fully, there might be other details. [ So many files, so few nights ;-) ]

We also might need more __always_inline's here and in other places, to solve the nonsensical inlining problems that Chris's case showed for example, with earlier GCCs.

Another option would be to not trust earlier GCCs at all with this feature
- to only define inline to not-__always_inline only on latest 4.3.x GCC - the only one that seems to at least not mess up royally.

Thus CONFIG_OPTIMIZE_INLINING=y would have no effect on older GCCs. That would quarantine the problem (and the impact) sufficiently i think. And if future GCCs start messing up in this area we could zap the whole feature in a heartbeat.

( Although now that we have this feature this gives an incentive to
compiler folks to tune their inliner on to the Linux kernel - for a decade we never allowed them to do that. The kernel clearly has one of the trickiest (and ugliest) inlining smarts in headers - and we never really exposed compilers to those things, so i'm not surprised at all that they mess up in cases.

Unfortunately the version lifecycle of most compiler projects is measured in years, not in months like that of the kernel. There's many reasons for that - and not all of those reasons are strictly their fault. )

Ingo

#302 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 4 lines

I've done a finegrained size analysis today (see my other mail in this thread), and it turns out that on gcc 4.3.x the main (and pretty much only) inlining annotation that matters in arch/x86/include/asm/*.h is the onliner patch attached below, annotating constant_test_bit().

That's pretty cool.

Should definitely file a gcc bug report for that though so that they can fix gcc. Did you already do that or should I?

-Andi

#303 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Ingo Molnar
Quoted 1 line · Ingo Molnar

* Linus Torvalds <[email protected]> wrote:

<snip>

Quoted 7 lines
Quoted 3 lines

Ingo - I think we need to remove that crap again. Because gcc gets the inlining horribly horribly wrong. As usual.

Apparently it messes up with asm()s: it doesnt know the contents of the asm() and hence it over-estimates the size [based on string heuristics]
...

<snip>

Quoted 6 lines

That win is mixed in slowpath and fastpath as well.

I see three options:

- Disable CONFIG_OPTIMIZE_INLINING=y altogether (it's already default-off)

I'd like to see this, leave all the heuristics out of it, if I say inline, I don't mean _maybe_, I mean you'd better damn well inline it. On the other hand, alpha seems to be hand-disabling the inline means __always_inline in their arch headers, so if this option is kept, it should be enabled on alpha as that is the current state of play there and get rid of that arch-private bit.

Quoted 3 lines

- Change the asm() inline markers to something new like asm_inline, which defaults to __always_inline.

I'd suggest just making inline always mean __always_inline. And get to work removing inline from functions in C files. This is probably also the better choice to keep older gccs producing decent code.

Quoted 7 lines

- Just mark all asm() inline markers as __always_inline - realizing that these should never ever be out of line.

We might still try the second or third options, as i think we shouldnt go back into the business of managing the inline attributes of ~100,000 kernel functions.

Or just make it clear that inline shouldn't (unless for a very good reason) _ever_ be used in a .c file.

Cheers,

Harvey

#304 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 8 lines · Harvey Harrison
Quoted 4 lines

We might still try the second or third options, as i think we shouldnt go back into the business of managing the inline attributes of ~100,000 kernel functions.

Or just make it clear that inline shouldn't (unless for a very good reason) _ever_ be used in a .c file.

The question is if that would produce acceptable quality code. In theory it should, but I'm more than wondering if it really will.

It would be ideal, of course, as it would mean less typing. I guess we could try it out by disabling any "inline" in the current code that isn't "__always_inline"...

-hpa

Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.
#305 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 10 lines · H. Peter Anvin
Quoted 8 lines · Harvey Harrison
Quoted 4 lines

We might still try the second or third options, as i think we shouldnt go back into the business of managing the inline attributes of ~100,000 kernel functions.

Or just make it clear that inline shouldn't (unless for a very good reason) _ever_ be used in a .c file.

Quoted 7 lines

The question is if that would produce acceptable quality code. In theory it should, but I'm more than wondering if it really will.

It would be ideal, of course, as it would mean less typing. I guess we could try it out by disabling any "inline" in the current code that isn't "__always_inline"...

A lot of code was written assuming inline means __always_inline, I'd suggest keeping that assumption and working on removing inlines that aren't strictly necessary as there's no way to know what inlines meant 'try to inline' and what ones really should have been __always_inline.

Not that I feel _that_ strongly about it.

Cheers,

Harvey

#306 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 8 lines · Harvey Harrison

A lot of code was written assuming inline means __always_inline, I'd suggest keeping that assumption and working on removing inlines that aren't strictly necessary as there's no way to know what inlines meant 'try to inline' and what ones really should have been __always_inline.

Not that I feel _that_ strongly about it.

Actually, we have that reasonably well down by now. There seems to be a couple of minor tweaking still necessary, but I think we're 90-95% there already.

-hpa

Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.
#307 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to H. Peter Anvin
Quoted 6 lines · H. Peter Anvin
Quoted 5 lines · Harvey Harrison
Quoted 4 lines

We might still try the second or third options, as i think we shouldnt go back into the business of managing the inline attributes of ~100,000 kernel functions.

Quoted 6 lines
Quoted 3 lines

Or just make it clear that inline shouldn't (unless for a very good reason) _ever_ be used in a .c file.

The question is if that would produce acceptable quality code. In theory it should, but I'm more than wondering if it really will.

I actually often use noinline when developing code simply because it makes it easier to read oopses when gcc doesn't inline ever static (which it normally does if it only has a single caller). You know roughly where it crashed without having to decode the line number.

I believe others do that too, I notice it's all over btrfs for example.

-Andi

Signature · 1 line
[email protected]
#308 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Andi Kleen

I actually often use noinline when developing code simply because it makes it easier to read oopses when gcc doesn't inline ever static (which it normally does if it only has a single caller)

Yes. Gcc inlining is a total piece of sh*t.

Gcc doesn't inline enough when we ask it to, and inlines too damn aggressively when we don't. It seems to almost totally ignore the inline hint.

Oh, well. The best option tends to be

- mark things "noinline" just to make sure gcc doesn't screw up.

- make "inline" mean "must_inline".

- maybe add a new "maybe_inline" to be the "inline" hint that gcc uses.

because quite frankly, depending on gcc to do the right thing is not working out.

Linus

#309 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 5 lines · Linus Torvalds
Quoted 3 lines

I actually often use noinline when developing code simply because it makes it easier to read oopses when gcc doesn't inline ever static (which it normally does if it only has a single caller)

Yes. Gcc inlining is a total piece of sh*t.

The static inlining by default (unfortunately) saves a lot of text size.

For testing I built an x86-64 allyesconfig kernel with -fno-inline-functions-called-once (which disables the default static inlining), and it increased text size by ~4.1% (over 2MB for a allyesconfig kernel). So I think we have to keep that, dropping it would cost too much :/

-Andi

Signature · 1 line
[email protected]
#310 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Andi Kleen
Quoted 14 lines · On Fri, 9 Jan 2009 04:35:31 +0100 Andi Kleen <[email protected]> wrote:
Quoted 6 lines · H. Peter Anvin
Quoted 5 lines · Harvey Harrison
Quoted 4 lines

We might still try the second or third options, as i think we shouldnt go back into the business of managing the inline attributes of ~100,000 kernel functions.

Quoted 6 lines
Quoted 3 lines

Or just make it clear that inline shouldn't (unless for a very good reason) _ever_ be used in a .c file.

The question is if that would produce acceptable quality code. In theory it should, but I'm more than wondering if it really will.

Quoted 7 lines

I actually often use noinline when developing code simply because it makes it easier to read oopses when gcc doesn't inline ever static (which it normally does if it only has a single caller). You know roughly where it crashed without having to decode the line number.

I believe others do that too, I notice it's all over btrfs for example.

Plus there is the problem where

foo()

{
	char a[1000];
}

bar()

{
	char a[1000];
}

zot()

{
	foo();
	bar();
}

uses 2000 bytes of stack.

Fortunately scripts/checkstack.pl can find these.

If someone runs it.

With the right kconfig settings.

And with the right compiler version.

#311 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

Quoted 10 lines

foo()

{
	char a[1000];
}

bar()

{
	char a[1000];
}
Quoted 8 lines

zot()

{
	foo();
	bar();
}

uses 2000 bytes of stack.
And with the right compiler version.

I believe that's fixed in newer gcc versions.

For old gccs we might indeed need to add noinlines though.

-Andi

Signature · 1 line
[email protected]
#312 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Andi Kleen
Quoted 14 lines · Andi Kleen
Quoted 6 lines · H. Peter Anvin
Quoted 5 lines · Harvey Harrison
Quoted 4 lines

We might still try the second or third options, as i think we shouldnt go back into the business of managing the inline attributes of ~100,000 kernel functions.

Quoted 6 lines
Quoted 3 lines

Or just make it clear that inline shouldn't (unless for a very good reason) _ever_ be used in a .c file.

The question is if that would produce acceptable quality code. In theory it should, but I'm more than wondering if it really will.

Quoted 6 lines

I actually often use noinline when developing code simply because it makes it easier to read oopses when gcc doesn't inline ever static (which it normally does if it only has a single caller). You know roughly where it crashed without having to decode the line number.

I believe others do that too, I notice it's all over btrfs for example.

For btrfs it was mostly about stack size at first. I'd use checkstack.pl and then run through the big funcs and figure out how they got so huge. It was almost always because gcc was inlining something it shouldn't, so I started using it on most funcs.

-chris

maintainer
#313 lore raw

Re: [PATCH -v7][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 3 lines · Linus Torvalds

Ok, I've gone through -v7, and I'm sure you're all shocked to hear it, but I have no complaints.

*cheer*, except I guess we need to figure out what goes bad for Chris.

Quoted 2 lines

Except that you dropped all the good commit
commentary you had earlier ;)

Yeah, I've yet to add that back, will do.

Quoted 11 lines

The patch looks pretty good (except for the big "#if 0" block in mutex-debug.c that I hope gets fixed, but I can't even really claim that I can be bothered), the locking looks fine (ie no locking at all), and the numbers seem pretty convinving.

Oh, and I think the open-coded

	atomic_cmpxchg(count, 1, 0) == 1

could possibly just be replaced with a simple __mutex_fastpath_trylock(). I dunno.

__mutex_fastpath_trylock() isn't always that neat -- see include/asm-generic/mutex-xchg.h -- and its a NOP on DEBUG_MUTEXES.

Note how I used old_val for the list_empty() thing as well, we could possibly drop that extra condition though.

#314 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 8 lines · Linus Torvalds
Quoted 2 lines · Peter Zijlstra

Do we really have to re-do all that code every loop?

No, you're right, we can just look up the cpu once. Which makes Andrew's argument that "probe_kernel_address()" isn't in any hot path even more true.

Do you need to even do that if CONFIG_DEBUG_PAGEALLOC is unset? Something like:

#ifdef CONFIG_DEBUG_PAGEALLOC
                /*
                 * Need to access the cpu field knowing that
                 * DEBUG_PAGEALLOC could have unmapped it if
                 * the mutex owner just released it and exited.
                 */
                if (probe_kernel_address(&thread->cpu, cpu))
                        break;
#else
		cpu = thread->cpu;

#endif

Shaggy

Signature · 2 lines
David Kleikamp
IBM Linux Technology Center
#315 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

Quoted 2 lines · Dave Kleikamp

Do you need to even do that if CONFIG_DEBUG_PAGEALLOC is unset?

No.

Quoted 12 lines

Something like:

#ifdef CONFIG_DEBUG_PAGEALLOC
                /*
                 * Need to access the cpu field knowing that
                 * DEBUG_PAGEALLOC could have unmapped it if
                 * the mutex owner just released it and exited.
                 */
                if (probe_kernel_address(&thread->cpu, cpu))
                        break;
#else
		cpu = thread->cpu;
Quoted 1 line

#endif

yes. That would work fine.

Linus

#316 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

Quoted 20 lines · Linus Torvalds
Quoted 2 lines · Dave Kleikamp

Do you need to even do that if CONFIG_DEBUG_PAGEALLOC is unset?

No.

Quoted 12 lines

Something like:

#ifdef CONFIG_DEBUG_PAGEALLOC
                /*
                 * Need to access the cpu field knowing that
                 * DEBUG_PAGEALLOC could have unmapped it if
                 * the mutex owner just released it and exited.
                 */
                if (probe_kernel_address(&thread->cpu, cpu))
                        break;
#else
		cpu = thread->cpu;
Quoted 1 line

#endif

Quoted 1 line

yes. That would work fine.

What about memory hotplug as Ingo mentioned?

Should that be:

#if defined(CONFIG_DEBUG_PAGEALLOC) || defined(CONFIG_MEMORY_HOTPLUG)

??

-- Steve

#317 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Steven Rostedt

Should that be:

#if defined(CONFIG_DEBUG_PAGEALLOC) || defined(CONFIG_MEMORY_HOTPLUG)

Well, probably CONFIG_MEMORY_HOTREMOVE, no? And I'd actually suggest that unplugging should have a stop-machine if it doesn't already, just because it's such a special case - like module removal.

Linus

#318 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · On Wed, 7 Jan 2009 15:57:06 -0800 (PST) Linus Torvalds…
Quoted 1 line · Steven Rostedt
Quoted 8 lines
Quoted 3 lines

Should that be:

#if defined(CONFIG_DEBUG_PAGEALLOC) || defined(CONFIG_MEMORY_HOTPLUG)

Well, probably CONFIG_MEMORY_HOTREMOVE, no? And I'd actually suggest that unplugging should have a stop-machine if it doesn't already, just because it's such a special case - like module removal.

I looked memory hotplug code again, then..

1. stop_machine() is not used.
2. x86-64 code doesn't have "unmap physical memory from the kernel space". (because ia64, my (old) target machine, doesn't need it.) I'm not sure about powerpc.

I'd like to look into this for x86-64 when I can.

BTW, can I make a quiestion ?
==

			if (lock->owner != thread)
				break;

			/*
			 * Need to access the cpu field knowing that
			 * DEBUG_PAGEALLOC could have unmapped it if
			 * the mutex owner just released it and exited.
			 */
			if (__get_user(cpu, &thread->cpu))
				break;

==
"thread" can be obsolete while lock->owner == thread ? Isn't this depends on CONFIG_DEBUG_MUTEXES ?

Thanks,
-Kame

#319 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 7 lines · Linus Torvalds
Quoted 3 lines

Should that be:

#if defined(CONFIG_DEBUG_PAGEALLOC) || defined(CONFIG_MEMORY_HOTPLUG)

Well, probably CONFIG_MEMORY_HOTREMOVE, no? And I'd actually suggest that unplugging should have a stop-machine if it doesn't already, just because it's such a special case - like module removal.

I do not think stop-machine will help, unless that spinning is protected by preempt-disable. If the task gets preempted after grabbing the owner thread_info, and then stop-machine runs, the memory disappears, the task is scheduled back, accesses the owner thread_info and then page-fault.

-- Steve

#320 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

Quoted 6 lines · On Wed, 7 Jan 2009 21:33:31 -0500 (EST) Steven Rostedt <[email protected]>…
Quoted 4 lines · Linus Torvalds
Quoted 3 lines

Should that be:

#if defined(CONFIG_DEBUG_PAGEALLOC) || defined(CONFIG_MEMORY_HOTPLUG)

Quoted 9 lines
Quoted 3 lines

Well, probably CONFIG_MEMORY_HOTREMOVE, no? And I'd actually suggest that unplugging should have a stop-machine if it doesn't already, just because it's such a special case - like module removal.

I do not think stop-machine will help, unless that spinning is protected by preempt-disable. If the task gets preempted after grabbing the owner thread_info, and then stop-machine runs, the memory disappears, the task is scheduled back, accesses the owner thread_info and then page-fault.

How about recording "cpu" into mutex at locking explicitly ? too bad ?

-Kame

#321 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

In reply to Steven Rostedt
Quoted 5 lines

What about memory hotplug as Ingo mentioned?

Should that be:

#if defined(CONFIG_DEBUG_PAGEALLOC) || defined(CONFIG_MEMORY_HOTPLUG)

We expect memory hotunplug to only really work in movable zones (all others should at least have one kernel object somewhere that prevents unplug) and you can't have task structs in movable zones obviously

So it's probably a non issue in practice.

-Andi

Signature · 1 line
[email protected]
#322 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

Quoted 11 lines · Andi Kleen
Quoted 5 lines

What about memory hotplug as Ingo mentioned?

Should that be:

#if defined(CONFIG_DEBUG_PAGEALLOC) || defined(CONFIG_MEMORY_HOTPLUG)

We expect memory hotunplug to only really work in movable zones (all others should at least have one kernel object somewhere that prevents unplug) and you can't have task structs in movable zones obviously

So it's probably a non issue in practice.

Sure, it probably is a non issue, but I'm afraid that non issues of today might become issues of tomorrow. Where does it say that we can never put a task struct in a movable zone. Perhaps, we could someday have a CPU with memory local to it, and pinned tasks to that CPU in that memory. Then there can be cases where we remove the CPU and memory together.

Because of preemption in the mutex spin part, there's no guarantee that a the task in that removed memory will not be referenced again. Of course this thought is purely theoretical, but I like to solve bugs that might might happen tomorrow too. ;-)

-- Steve

#323 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

Quoted 3 lines

Sure, it probably is a non issue, but I'm afraid that non issues of today might become issues of tomorrow. Where does it say that we can never put a task struct in a movable zone.

Task structs are not movable, so they by definition do not belong in movable zones.

Quoted 2 lines

memory local to it, and pinned tasks to that CPU in that memory. Then there can be cases where we remove the CPU and memory together.

If you did that you would need to redesign so much of the kernel, changing the mutex code too would be the smallest of your worries.

-Andi

Signature · 1 line
[email protected]
#324 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 5 lines

But we can do that with __get_user(thread_info->cpu) (very unlikely page fault protection due to the possibility of CONFIG_DEBUG_PAGEALLOC) and then validating the cpu. It it's in range, we can use it and verify whether cpu_rq(cpu)->curr has that thread_info.

Quoted 7 lines

So we can do all that locklessly and optimistically, just going back and verifying the results later. This is why "thread_info" is actually a better thing to use than "task_struct" - we can look up the cpu in it with a simple dereference. We knew the pointer _used_ to be valid, so in any normal situation, it will never page fault (and if you have CONFIG_DEBUG_PAGEALLOC and hit a very unlucky race, then performance isn't your concern anyway: we just need to make the page fault be non-lethal ;)

The problem with probe_kernel_address() is that it does lots of operations around the access in the hot path (set_fs, pagefault_disable etc.), so i'm not sure that's a good idea.

Sure you can probably do better, but that would involve patching all architectures won't it? Ok I suppose you could make an ARCH_HAS_blabla white list, but that wouldn't be exactly pretty.

-Andi

#325 lore raw

Re: [PATCH -v5][RFC]: mutex: implement adaptive spinning

Quoted 13 lines · On Wed, 7 Jan 2009 22:37:40 +0100 Andi Kleen <[email protected]> wrote:
Quoted 5 lines

But we can do that with __get_user(thread_info->cpu) (very unlikely page fault protection due to the possibility of CONFIG_DEBUG_PAGEALLOC) and then validating the cpu. It it's in range, we can use it and verify whether cpu_rq(cpu)->curr has that thread_info.

Quoted 7 lines

So we can do all that locklessly and optimistically, just going back and verifying the results later. This is why "thread_info" is actually a better thing to use than "task_struct" - we can look up the cpu in it with a simple dereference. We knew the pointer _used_ to be valid, so in any normal situation, it will never page fault (and if you have CONFIG_DEBUG_PAGEALLOC and hit a very unlucky race, then performance isn't your concern anyway: we just need to make the page fault be non-lethal ;)

Quoted 3 lines

The problem with probe_kernel_address() is that it does lots of operations around the access in the hot path (set_fs, pagefault_disable etc.), so i'm not sure that's a good idea.

probe_kernel_address() isn't tooooo bad - a few reads and writes into the task_struct and thread_struct. And we're on the slow, contended path here anyway..

#326 lore raw

Re: [PATCH -v4][RFC]: mutex: implement adaptive spinning

In reply to Linus Torvalds
Quoted 8 lines · Linus Torvalds
Quoted 3 lines · Peter Zijlstra

Change mutex contention behaviour such that it will sometimes busy wait on acquisition - moving its behaviour closer to that of spinlocks.

Ok, this one looks _almost_ ok.

Quoted 8 lines

The only problem is that I think you've lost the UP case.

In UP, you shouldn't have the code to spin, and the "spin_or_schedule()" should fall back to just the schedule case.

It migth also be worthwhile to try to not set the owner, and re-organize that a bit (by making it a inline function that sets the owner only for CONFIG_SMP or lockdep/debug).

So far I haven't found any btrfs benchmarks where this is slower than mutexes without any spinning. But, it isn't quite as fast as the btrfs spin.

I'm using three different benchmarks, and they hammer on different things. All against btrfs and a single sata drive.

* dbench -t 30 50, which means run dbench 50 for 30 seconds. It is a
broad workload that hammers on lots of code, but it also tends to go faster when things are less fair. These numbers are stable across runs. Some IO is done at the very start of the run, but the bulk of the run is CPU bound in various btrfs btrees.

Plain mutex: dbench reports 240MB/s
Simple spin: dbench reports 560MB/s
Peter's v4: dbench reports 388MB/s

* 50 procs creating 10,000 files (4k each), one dir per proc. The result is 50 dirs and each dir has 10,000 files. This is mostly CPU bound for the procs, but pdflush and friends are doing lots of IO.

Plain mutex: avg: 115 files/s avg system time for each proc: 1.6s Simple spin: avg: 152 files/s avg system time for each proc: 2s Peter's v4: avg: 130 files/s avg system time for each proc: 2.9s

I would have expected Peter's patch to use less system time than my spin. If I change his patch to limit the spin to 512 iterations (same as my code), the system time goes back down to 1.7s, but the files/s doesn't improve.

* Parallel stat: the last benchmark is the most interesting, since it really hammers on the btree locking speed. I take the directory tree the file creation run (50 dirs, 10,000 files each) and have 50 procs running stat on all the files in parallel.

Before the run I clear the inode cache but leave the page cache. So, everything is hot in the btree but there are no inodes in cache.

Plain mutex: 9.488s real, 8.6 sys
Simple spin: 3.8s real 13.8s sys
Peter's v4: 7.9s real 8.5s sys

-chris

#327 lore raw

Re: [PATCH -v4][RFC]: mutex: implement adaptive spinning

Quoted 4 lines · Chris Mason

So far I haven't found any btrfs benchmarks where this is slower than mutexes without any spinning. But, it isn't quite as fast as the btrfs spin.

Quite frankly, from our history with ext3 and other filesystems, using a mutex in the filesystem is generally the wrong thing to do anyway.

Are you sure you can't just use a spinlock, and just release it over IO? The "have to do IO or extend the btree" case is usually pretty damn clear.

Because it really sounds like you're lock-limited, and you should just try to clean it up. A pure "just spinlock" in the hotpath is always going to be better.

Linus

#328 lore raw

Re: [PATCH -v4][RFC]: mutex: implement adaptive spinning

Quoted 10 lines · Linus Torvalds
Quoted 4 lines · Chris Mason

So far I haven't found any btrfs benchmarks where this is slower than mutexes without any spinning. But, it isn't quite as fast as the btrfs spin.

Quite frankly, from our history with ext3 and other filesystems, using a mutex in the filesystem is generally the wrong thing to do anyway.

Quoted 6 lines

Are you sure you can't just use a spinlock, and just release it over IO? The "have to do IO or extend the btree" case is usually pretty damn clear.

Because it really sounds like you're lock-limited, and you should just try to clean it up. A pure "just spinlock" in the hotpath is always going to be better.

There are definitely ways I can improve performance for contention in the hot btree nodes, and I think it would be a mistake to tune the generic adaptive locks just for my current code.

But, it isn't a bad test case to compare the spin with the new patch and with the plain mutex. If the adaptive code gets in, I think it would be best for me to drop the spin.

Either way there's more work to be done in the btrfs locking code.

-chris

#329 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Peter Zijlstra
Quoted 22 lines · Peter Zijlstra
kernel/sched.c +22 -0
+void mutex_spin_or_schedule(struct mutex_waiter *waiter, long state, unsigned long *flags)
+{
+	struct mutex *lock = waiter->lock;
+	struct task_struct *task = waiter->task;
+	struct task_struct *owner = lock->owner;
+	struct rq *rq;
+
+	if (!owner)
+		goto do_schedule;
+
+	rq = task_rq(owner);
+
+	if (rq->curr != owner) {
+do_schedule:
+		__set_task_state(task, state);
+		spin_unlock_mutex(&lock->wait_lock, *flags);
+		schedule();
+	} else {
+		spin_unlock_mutex(&lock->wait_lock, *flags);
+		for (;;) {
+			/* Stop spinning when there's a pending signal. */
+			if (signal_pending_state(state, task))

kernel/sched.c pick_next_task(struct rq *rq, struct tas · line 4636

Quoted 10 lines
kernel/sched.c +10 -0
+				break;
+
+			/* Owner changed, bail to revalidate state */
+			if (lock->owner != owner)
+				break;
+
+			/* Owner stopped running, bail to revalidate state */
+			if (rq->curr != owner)
+				break;
+

2 questions from my immature thought:

1) Do we need keep gcc from optimizing when we access lock->owner and rq->curr in the loop?

2) "if (rq->curr != owner)" need become smarter.
schedule()

   {
	select_next
	rq->curr = next;
	contex_swith

}
we also spin when owner is select_next-ing in schedule(). but select_next is not fast enough.

Lai.

maintainer
#330 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 36 lines · Lai Jiangshan
Quoted 22 lines · Peter Zijlstra
kernel/sched.c +22 -0
+void mutex_spin_or_schedule(struct mutex_waiter *waiter, long state, unsigned long *flags)
+{
+	struct mutex *lock = waiter->lock;
+	struct task_struct *task = waiter->task;
+	struct task_struct *owner = lock->owner;
+	struct rq *rq;
+
+	if (!owner)
+		goto do_schedule;
+
+	rq = task_rq(owner);
+
+	if (rq->curr != owner) {
+do_schedule:
+		__set_task_state(task, state);
+		spin_unlock_mutex(&lock->wait_lock, *flags);
+		schedule();
+	} else {
+		spin_unlock_mutex(&lock->wait_lock, *flags);
+		for (;;) {
+			/* Stop spinning when there's a pending signal. */
+			if (signal_pending_state(state, task))

kernel/sched.c pick_next_task(struct rq *rq, struct tas · line 4636

Quoted 10 lines
kernel/sched.c +10 -0
+				break;
+
+			/* Owner changed, bail to revalidate state */
+			if (lock->owner != owner)
+				break;
+
+			/* Owner stopped running, bail to revalidate state */
+			if (rq->curr != owner)
+				break;
+

2 questions from my immature thought:

Quoted 2 lines

1) Do we need keep gcc from optimizing when we access lock->owner and rq->curr in the loop?

cpu_relax() is a compiler barrier iirc.

Quoted 9 lines

2) "if (rq->curr != owner)" need become smarter.
schedule()

   {
	select_next
	rq->curr = next;
	contex_swith

}
we also spin when owner is select_next-ing in schedule(). but select_next is not fast enough.

I'm not sure what you're saying here..

#331 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 51 lines · Peter Zijlstra
Quoted 35 lines · Lai Jiangshan
Quoted 22 lines · Peter Zijlstra
kernel/sched.c +22 -0
+void mutex_spin_or_schedule(struct mutex_waiter *waiter, long state, unsigned long *flags)
+{
+	struct mutex *lock = waiter->lock;
+	struct task_struct *task = waiter->task;
+	struct task_struct *owner = lock->owner;
+	struct rq *rq;
+
+	if (!owner)
+		goto do_schedule;
+
+	rq = task_rq(owner);
+
+	if (rq->curr != owner) {
+do_schedule:
+		__set_task_state(task, state);
+		spin_unlock_mutex(&lock->wait_lock, *flags);
+		schedule();
+	} else {
+		spin_unlock_mutex(&lock->wait_lock, *flags);
+		for (;;) {
+			/* Stop spinning when there's a pending signal. */
+			if (signal_pending_state(state, task))

kernel/sched.c pick_next_task(struct rq *rq, struct tas · line 4636

Quoted 10 lines
kernel/sched.c +10 -0
+				break;
+
+			/* Owner changed, bail to revalidate state */
+			if (lock->owner != owner)
+				break;
+
+			/* Owner stopped running, bail to revalidate state */
+			if (rq->curr != owner)
+				break;
+

2 questions from my immature thought:

Quoted 2 lines

1) Do we need keep gcc from optimizing when we access lock->owner and rq->curr in the loop?

cpu_relax() is a compiler barrier iirc.

Quoted 9 lines

2) "if (rq->curr != owner)" need become smarter.
schedule()

   {
	select_next
	rq->curr = next;
	contex_swith

}
we also spin when owner is select_next-ing in schedule(). but select_next is not fast enough.

Quoted 3 lines

I'm not sure what you're saying here..

I means when mutex owner calls schedule(), current task is also spinning until rq->curr is changed.

I think such spin is not necessary, it is doing nothing but wasting time. And this spin period is not short, and when this spin period ended, rq->curr is changed too, current task has to sleep.

So I think current task should sleep earlier when it detects that mutex owner start schedule().

#332 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 2 lines · Lai Jiangshan

So I think current task should sleep earlier when it detects that mutex owner start schedule().

How do you propose it detects this?

Signature · 4 lines
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."
#333 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Peter Zijlstra
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Paul E. McKenney

Preemptable RCU needs to be faster. Got it -- and might have a way to do it by eliminating the irq disabling and cutting way back on the number of operations that must be performed. It would probably still be necessary to access the task structure.

Quoted 6 lines
Quoted 2 lines

Or is something other than the raw performance of rcu_read_lock() and rcu_read_unlock() at issue here?

With Linus' mutex_spin_or_schedule() function the whole - keeping owner's task_struct alive issue goes away,.. now if only the thing would boot...

Cool! And I can relate to the "if only the thing would boot" part. ;-)

Thanx, Paul

#334 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Ingo Molnar
Quoted 6 lines · Ingo Molnar

The thing i like most about Peter's patch (compared to most other adaptive spinning approaches i've seen, which all sucked as they included various ugly heuristics complicating the whole thing) is that it solves the "how long should we spin" question elegantly: we spin until the owner runs on a CPU.

The other way around, you mean: we spin until the owner is no longer holding a cpu.

I agree that it's better than the normal "spin for some random time" model, but I can't say I like the "return 0" cases where it just retries the whole loop if the semaphore was gotten by somebody else instead. Sounds like an easyish live-lock to me.

I also still strongly suspect that whatever lock actually needs this, should be seriously re-thought.

But apart from the "return 0" craziness I at least dont' _hate_ this patch. Do we have numbers? Do we know which locks this matters on?

Linus

#335 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 3 lines · Linus Torvalds

The other way around, you mean: we spin until the owner is no longer holding a cpu.

Btw, I hate the name of the helper function for that. "task_is_current()"? "current" means something totally different in the linux kernel: it means that the task is _this_ task.

So the only sensible implementation of "task_is_current(task)" is to just make it return "task == current", but that's obviously not what the function wants to do.

So it should be renamed. Something like "task_is_oncpu()" or whatever.

I realize that the scheduler internally has that whole "rq->curr" thing, but that's an internal scheduler thing, and should not be confused with the overall kernel model of "current".

Linus

#336 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 8 lines · Linus Torvalds

Btw, I hate the name of the helper function for that. "task_is_current()"? "current" means something totally different in the linux kernel: it means that the task is _this_ task.

So the only sensible implementation of "task_is_current(task)" is to just make it return "task == current", but that's obviously not what the function wants to do.

Quoted 5 lines

So it should be renamed. Something like "task_is_oncpu()" or whatever.

I realize that the scheduler internally has that whole "rq->curr" thing, but that's an internal scheduler thing, and should not be confused with the overall kernel model of "current".

I totally agree that we should change the name of that. I never thought about the confusion that it would cause to someone that is not working so heavy on the scheduler. Thanks for the perspective.

Sometimes us scheduler guys have our heads too much up the scheduler ass that all we see is scheduler crap ;-)

-- Steve

#337 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Linus Torvalds
Quoted 2 lines · Linus Torvalds

So it should be renamed. Something like "task_is_oncpu()" or whatever.

Another complaint, which is tangentially related in that it actually concerns "current".

Right now, if some process deadlocks on a mutex, we get hung process, but with a nice backtrace and hopefully other things (that don't need that lock) still continue to work.

But if I read it correctly, the adaptive spin code will instead just hang. Exactly because "task_is_current()" will also trigger for that case, and now you get an infinite loop, with the process spinning until it looses its own CPU, which obviously will never happen.

Yes, this is the behavior we get with spinlocks too, and yes, lock debugging will talk about it, but it's a regression. We've historically had a _lot_ more bad deadlocks on mutexes than we have had on spinlocks, exactly because mutexes can be held over much more complex code. So regressing on it and making it less debuggable is bad.

IOW, if we do this, then I think we need a

	BUG_ON(task == owner);

in the waiting slow-path. I realize the test already exists for the DEBUG case, but I think we just want it even for production kernels. Especially since we'd only ever need it in the slow-path.

Linus

#338 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 4 lines · Linus Torvalds

Right now, if some process deadlocks on a mutex, we get hung process, but with a nice backtrace and hopefully other things (that don't need that lock) still continue to work.

Clarification: the "nice backtrace" we only get with something like sysrq-W, of course. We don't get a backtrace _automatically_, but with an otherwise live machine, there's a better chance that people do get wchan or other info. IOW, it's at least a fairly debuggable situation.

Linus

#339 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 10 lines · Linus Torvalds
Quoted 4 lines · Linus Torvalds

Right now, if some process deadlocks on a mutex, we get hung process, but with a nice backtrace and hopefully other things (that don't need that lock) still continue to work.

Clarification: the "nice backtrace" we only get with something like sysrq-W, of course. We don't get a backtrace _automatically_, but with an otherwise live machine, there's a better chance that people do get wchan or other info. IOW, it's at least a fairly debuggable situation.

btw., the softlockup watchdog detects non-progressing uninterruptible tasks (regardless of whether they locked up due to mutexes or any other reason).

This does occasionally help in debugging deadlocks:

http://marc.info/?l=linux-mm&m=122889587725061&w=2

but it would indeed be also good to have the most common self-deadlock case checked unconditionally in the mutex slowpath.

Ingo

#340 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Linus Torvalds
Quoted 22 lines · Linus Torvalds
Quoted 2 lines · Linus Torvalds

So it should be renamed. Something like "task_is_oncpu()" or whatever.

Another complaint, which is tangentially related in that it actually concerns "current".

Right now, if some process deadlocks on a mutex, we get hung process, but with a nice backtrace and hopefully other things (that don't need that lock) still continue to work.

But if I read it correctly, the adaptive spin code will instead just hang. Exactly because "task_is_current()" will also trigger for that case, and now you get an infinite loop, with the process spinning until it looses its own CPU, which obviously will never happen.

Yes, this is the behavior we get with spinlocks too, and yes, lock debugging will talk about it, but it's a regression. We've historically had a _lot_ more bad deadlocks on mutexes than we have had on spinlocks, exactly because mutexes can be held over much more complex code. So regressing on it and making it less debuggable is bad.

Quoted 7 lines

IOW, if we do this, then I think we need a

	BUG_ON(task == owner);

in the waiting slow-path. I realize the test already exists for the DEBUG case, but I think we just want it even for production kernels. Especially since we'd only ever need it in the slow-path.

yeah, sounds good.

One thought:

BUG_ON()'s do_exit() shows a slightly misleading failure pattern to users:
instead of a 'hanging' task, we'd get a misbehaving app due to one of its tasks exiting spuriously. It can even go completely unnoticed [users dont look at kernel logs normally] - while a hanging task generally does get noticed. (because there's no progress in processing)

So instead of the BUG_ON() we could emit a WARN_ONCE() perhaps, plus not do any spinning and just block - resulting in an uninterruptible task (that the user will probably notice) and a scary message in the syslog? [all in the slowpath]

So in this case WARN_ONCE() is both more passive (it does not run do_exit()), and shows the more intuitive failure pattern to users. No strong feelings though.

Ingo

#341 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 8 lines · Ingo Molnar

One thought:

BUG_ON()'s do_exit() shows a slightly misleading failure pattern to
users: instead of a 'hanging' task, we'd get a misbehaving app due to one of its tasks exiting spuriously. It can even go completely unnoticed [users dont look at kernel logs normally] - while a hanging task generally does get noticed. (because there's no progress in processing)

Quoted 4 lines

So instead of the BUG_ON() we could emit a WARN_ONCE() perhaps, plus not do any spinning and just block - resulting in an uninterruptible task (that the user will probably notice) and a scary message in the syslog? [all in the slowpath]

And we'd strictly do an uninterruptible sleep here, unconditionally: even if this is within mutex_lock_interruptible() - we dont want a Ctrl-C or a SIGKILL to allow to 'break out' the app from the deadlock.

Ingo

#342 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Ingo Molnar
Quoted 5 lines · Ingo Molnar

So instead of the BUG_ON() we could emit a WARN_ONCE() perhaps, plus not do any spinning and just block - resulting in an uninterruptible task (that the user will probably notice) and a scary message in the syslog? [all in the slowpath]

Sure. You could put it in the adaptive function thing, with something like

	if (WARN_ONCE(waiter == owner))
		return 1;

which should fall back on the old behavior and do the one-time warning.

Linus

#343 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Linus Torvalds
Quoted 17 lines · Linus Torvalds
Quoted 6 lines · Ingo Molnar

The thing i like most about Peter's patch (compared to most other adaptive spinning approaches i've seen, which all sucked as they included various ugly heuristics complicating the whole thing) is that it solves the "how long should we spin" question elegantly: we spin until the owner runs on a CPU.

The other way around, you mean: we spin until the owner is no longer holding a cpu.

I agree that it's better than the normal "spin for some random time" model, but I can't say I like the "return 0" cases where it just retries the whole loop if the semaphore was gotten by somebody else instead. Sounds like an easyish live-lock to me.

Quoted 5 lines

I also still strongly suspect that whatever lock actually needs this, should be seriously re-thought.

But apart from the "return 0" craziness I at least dont' _hate_ this patch. Do we have numbers? Do we know which locks this matters on?

This discussion was kicked off by an unconditional spin (512 tries) against mutex_trylock in the btrfs tree locking code.

Btrfs is using mutexes to protect the btree blocks, and btree searching often hits hot nodes that are always in cache. For these nodes, the spinning is much faster, but btrfs also needs to be able to sleep with the locks held so it can read from the disk and do other complex operations.

For btrfs, dbench 50 performance doubles with the unconditional spin, mostly because that workload is almost all in ram.

For 50 procs creating 4k files in parallel, the spin is 30-50% faster. This workload is a mixture of disk bound and CPU bound.

Yes, there is definitely some low hanging fruit to tune the btrfs btree searches and locking. But, I think the adaptive model is a good fit for on disk btrees in general.

-chris

#344 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Ingo Molnar
Quoted 9 lines

Linus, what do you think about this particular approach of spin-mutexes? It's not the typical spin-mutex i think.

The thing i like most about Peter's patch (compared to most other adaptive spinning approaches i've seen, which all sucked as they included various ugly heuristics complicating the whole thing) is that it solves the "how long should we spin" question elegantly: we spin until the owner runs on a CPU.

Well; if there's a timeout, that's obviously safe.

But this has no timeout, and Linus wants to play games with accessing 'does owner run on cpu?' lockless. Now, can it mistakenly spin when the owner is scheduled away? That would deadlock, and without locking, I'm not sure if we prevent that....

Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
#345 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Peter Zijlstra
Quoted 5 lines · Peter Zijlstra

Subject: mutex: adaptive spin
From: Peter Zijlstra <[email protected]>
Date: Tue Jan 06 12:32:12 CET 2009

Based on the code in -rt, provide adaptive spins on generic mutexes.

I guess it would be nice to add another type so you can test/convert callsites individually. I've got no objections to improving synchronisation primitives, but I would be interested to see good results from some mutex that can't be achieved by improving the locking (by improving I don't mean inventing some crazy lockless algorithm, but simply making it reasonably sane and scalable).

Good area to investigate though, I think.

Quoted 248 lines
---
 include/linux/mutex.h |    4 ++--
 include/linux/sched.h |    1 +
 kernel/mutex-debug.c  |   11 ++---------
 kernel/mutex-debug.h  |    8 --------
 kernel/mutex.c        |   46 +++++++++++++++++++++++++++++++++++++++-------
 kernel/mutex.h        |    2 --
 kernel/sched.c        |    5 +++++
 7 files changed, 49 insertions(+), 28 deletions(-)

Index: linux-2.6/include/linux/mutex.h
===================================================================

include/linux/mutex.h +2 -2
@@ -50,8 +50,8 @@ struct mutex {
 	atomic_t		count;
 	spinlock_t		wait_lock;
 	struct list_head	wait_list;
+	struct task_struct	*owner;
 #ifdef CONFIG_DEBUG_MUTEXES
-	struct thread_info	*owner;
 	const char 		*name;
 	void			*magic;
 #endif
@@ -67,8 +67,8 @@ struct mutex {
 struct mutex_waiter {
 	struct list_head	list;
 	struct task_struct	*task;
-#ifdef CONFIG_DEBUG_MUTEXES
 	struct mutex		*lock;
+#ifdef CONFIG_DEBUG_MUTEXES
 	void			*magic;
 #endif
 };

Index: linux-2.6/include/linux/sched.h
===================================================================

include/linux/sched.h +1 -0
@@ -249,6 +249,7 @@ extern void init_idle(struct task_struct
 extern void init_idle_bootup_task(struct task_struct *idle);
 
 extern int runqueue_is_locked(void);
+extern int task_is_current(struct task_struct *p);
 extern void task_rq_unlock_wait(struct task_struct *p);
 
 extern cpumask_var_t nohz_cpu_mask;

Index: linux-2.6/kernel/mutex-debug.c
===================================================================

kernel/mutex-debug.c +2 -9
@@ -26,11 +26,6 @@
 /*
  * Must be called with lock->wait_lock held.
  */
-void debug_mutex_set_owner(struct mutex *lock, struct thread_info *new_owner)
-{
-	lock->owner = new_owner;
-}
-
 void debug_mutex_lock_common(struct mutex *lock, struct mutex_waiter *waiter)
 {
 	memset(waiter, MUTEX_DEBUG_INIT, sizeof(*waiter));
@@ -59,7 +54,6 @@ void debug_mutex_add_waiter(struct mutex
 
 	/* Mark the current thread as blocked on the lock: */
 	ti->task->blocked_on = waiter;
-	waiter->lock = lock;
 }
 
 void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter,
@@ -80,9 +74,9 @@ void debug_mutex_unlock(struct mutex *lo
 		return;
 
 	DEBUG_LOCKS_WARN_ON(lock->magic != lock);
-	DEBUG_LOCKS_WARN_ON(lock->owner != current_thread_info());
+	DEBUG_LOCKS_WARN_ON(lock->owner != current);
 	DEBUG_LOCKS_WARN_ON(!lock->wait_list.prev && !lock->wait_list.next);
-	DEBUG_LOCKS_WARN_ON(lock->owner != current_thread_info());
+	DEBUG_LOCKS_WARN_ON(lock->owner != current);
 }
 
 void debug_mutex_init(struct mutex *lock, const char *name,
@@ -95,7 +89,6 @@ void debug_mutex_init(struct mutex *lock
 	debug_check_no_locks_freed((void *)lock, sizeof(*lock));
 	lockdep_init_map(&lock->dep_map, name, key, 0);
 #endif
-	lock->owner = NULL;
 	lock->magic = lock;
 }
 

Index: linux-2.6/kernel/mutex-debug.h
===================================================================

kernel/mutex-debug.h +0 -8
@@ -13,14 +13,6 @@
 /*
  * This must be called with lock->wait_lock held.
  */
-extern void
-debug_mutex_set_owner(struct mutex *lock, struct thread_info *new_owner);
-
-static inline void debug_mutex_clear_owner(struct mutex *lock)
-{
-	lock->owner = NULL;
-}
-
 extern void debug_mutex_lock_common(struct mutex *lock,
 				    struct mutex_waiter *waiter);
 extern void debug_mutex_wake_waiter(struct mutex *lock,

Index: linux-2.6/kernel/mutex.c
===================================================================

kernel/mutex.c +39 -7
@@ -46,6 +46,7 @@ __mutex_init(struct mutex *lock, const c
 	atomic_set(&lock->count, 1);
 	spin_lock_init(&lock->wait_lock);
 	INIT_LIST_HEAD(&lock->wait_list);
+	lock->owner = NULL;
 
 	debug_mutex_init(lock, name, key);
 }
@@ -120,6 +121,28 @@ void __sched mutex_unlock(struct mutex *
 
 EXPORT_SYMBOL(mutex_unlock);
 
+#ifdef CONFIG_SMP
+static int adaptive_wait(struct mutex_waiter *waiter,
+			 struct task_struct *owner, long state)
+{
+	for (;;) {
+		if (signal_pending_state(state, waiter->task))
+			return 0;
+		if (waiter->lock->owner != owner)
+			return 0;
+		if (!task_is_current(owner))
+			return 1;
+		cpu_relax();
+	}
+}
+#else
+static int adaptive_wait(struct mutex_waiter *waiter,
+			 struct task_struct *owner, long state)
+{
+	return 1;
+}
+#endif
+
 /*
  * Lock a mutex (possibly interruptible), slowpath:
  */
@@ -127,7 +150,7 @@ static inline int __sched
 __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	       	unsigned long ip)
 {
-	struct task_struct *task = current;
+	struct task_struct *owner, *task = current;
 	struct mutex_waiter waiter;
 	unsigned int old_val;
 	unsigned long flags;
@@ -141,6 +164,7 @@ __mutex_lock_common(struct mutex *lock, 
 	/* add waiting tasks to the end of the waitqueue (FIFO): */
 	list_add_tail(&waiter.list, &lock->wait_list);
 	waiter.task = task;
+	waiter.lock = lock;
 
 	old_val = atomic_xchg(&lock->count, -1);
 	if (old_val == 1)
@@ -175,11 +199,19 @@ __mutex_lock_common(struct mutex *lock, 
 			debug_mutex_free_waiter(&waiter);
 			return -EINTR;
 		}
-		__set_task_state(task, state);
 
-		/* didnt get the lock, go to sleep: */
+		owner = lock->owner;
+		get_task_struct(owner);
 		spin_unlock_mutex(&lock->wait_lock, flags);
-		schedule();
+
+		if (adaptive_wait(&waiter, owner, state)) {
+			put_task_struct(owner);
+			__set_task_state(task, state);
+			/* didnt get the lock, go to sleep: */
+			schedule();
+		} else
+			put_task_struct(owner);
+
 		spin_lock_mutex(&lock->wait_lock, flags);
 	}
 
@@ -187,7 +219,7 @@ done:
 	lock_acquired(&lock->dep_map, ip);
 	/* got the lock - rejoice! */
 	mutex_remove_waiter(lock, &waiter, task_thread_info(task));
-	debug_mutex_set_owner(lock, task_thread_info(task));
+	lock->owner = task;
 
 	/* set it to 0 if there are no waiters left: */
 	if (likely(list_empty(&lock->wait_list)))
@@ -260,7 +292,7 @@ __mutex_unlock_common_slowpath(atomic_t 
 		wake_up_process(waiter->task);
 	}
 
-	debug_mutex_clear_owner(lock);
+	lock->owner = NULL;
 
 	spin_unlock_mutex(&lock->wait_lock, flags);
 }
@@ -352,7 +384,7 @@ static inline int __mutex_trylock_slowpa
 
 	prev = atomic_xchg(&lock->count, -1);
 	if (likely(prev == 1)) {
-		debug_mutex_set_owner(lock, current_thread_info());
+		lock->owner = current;
 		mutex_acquire(&lock->dep_map, 0, 1, _RET_IP_);
 	}
 	/* Set it back to 0 if there are no waiters: */

Index: linux-2.6/kernel/sched.c
===================================================================

kernel/sched.c +5 -0
@@ -697,6 +697,11 @@ int runqueue_is_locked(void)
 	return ret;
 }
 
+int task_is_current(struct task_struct *p)
+{
+	return task_rq(p)->curr == p;
+}
+
 /*
  * Debugging: various feature bits
  */

Index: linux-2.6/kernel/mutex.h
===================================================================

kernel/mutex.h +0 -2
@@ -16,8 +16,6 @@
 #define mutex_remove_waiter(lock, waiter, ti) \
 		__list_del((waiter)->list.prev, (waiter)->list.next)
 
-#define debug_mutex_set_owner(lock, new_owner)		do { } while (0)
-#define debug_mutex_clear_owner(lock)			do { } while (0)
 #define debug_mutex_wake_waiter(lock, waiter)		do { } while (0)
 #define debug_mutex_free_waiter(waiter)			do { } while (0)
 #define debug_mutex_add_waiter(lock, waiter, ti)	do { } while (0)
#346 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Peter Zijlstra
Quoted 5 lines · Peter Zijlstra

Subject: mutex: adaptive spin
From: Peter Zijlstra <[email protected]>
Date: Tue Jan 06 12:32:12 CET 2009

Based on the code in -rt, provide adaptive spins on generic mutexes.

I already sent Peter details, but the patch has problems without mutex debugging turned on. So it isn't quite ready for benchmarking yet.

-chris

#347 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Peter Zijlstra
Quoted 6 lines · On Tue, 06 Jan 2009 12:40:31 +0100 Peter Zijlstra <[email protected]> wrote:

Subject: mutex: adaptive spin
From: Peter Zijlstra <[email protected]>
Date: Tue Jan 06 12:32:12 CET 2009

Based on the code in -rt, provide adaptive spins on generic mutexes.

How dumb is it to send a lump of uncommented, changelogged code as an rfc, only to have Ingo reply, providing the changelog for you?

Sigh.

Quoted 18 lines
kernel/mutex.c +5 -0
@@ -46,6 +46,7 @@ __mutex_init(struct mutex *lock, const c
 	atomic_set(&lock->count, 1);
 	spin_lock_init(&lock->wait_lock);
 	INIT_LIST_HEAD(&lock->wait_list);
+	lock->owner = NULL;
 
 	debug_mutex_init(lock, name, key);
 }
@@ -120,6 +121,28 @@ void __sched mutex_unlock(struct mutex *
 
 EXPORT_SYMBOL(mutex_unlock);
 
+#ifdef CONFIG_SMP
+static int adaptive_wait(struct mutex_waiter *waiter,
+			 struct task_struct *owner, long state)
+{

kernel/mutex.c void __sched mutex_unlock(struct mutex * · line 137

Quoted 10 lines
kernel/mutex.c +10 -0
+	for (;;) {
+		if (signal_pending_state(state, waiter->task))
+			return 0;
+		if (waiter->lock->owner != owner)
+			return 0;
+		if (!task_is_current(owner))
+			return 1;
+		cpu_relax();
+	}
+}

Each of the tests in this function should be carefully commented. It's really the core piece of the design.

Quoted 29 lines
kernel/mutex.c +10 -1
+#else
+static int adaptive_wait(struct mutex_waiter *waiter,
+			 struct task_struct *owner, long state)
+{
+	return 1;
+}
+#endif
+
 /*
  * Lock a mutex (possibly interruptible), slowpath:
  */
@@ -127,7 +150,7 @@ static inline int __sched
 __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	       	unsigned long ip)
 {
-	struct task_struct *task = current;
+	struct task_struct *owner, *task = current;
 	struct mutex_waiter waiter;
 	unsigned int old_val;
 	unsigned long flags;
@@ -141,6 +164,7 @@ __mutex_lock_common(struct mutex *lock, 
 	/* add waiting tasks to the end of the waitqueue (FIFO): */
 	list_add_tail(&waiter.list, &lock->wait_list);
 	waiter.task = task;
+	waiter.lock = lock;
 
 	old_val = atomic_xchg(&lock->count, -1);
 	if (old_val == 1)

kernel/mutex.c __mutex_lock_common(struct mutex *lock, · line 203

Quoted 7 lines
kernel/mutex.c +1 -2
@@ -175,11 +199,19 @@ __mutex_lock_common(struct mutex *lock, 
 			debug_mutex_free_waiter(&waiter);
 			return -EINTR;
 		}
-		__set_task_state(task, state);
 
-		/* didnt get the lock, go to sleep: */
+		owner = lock->owner;

What prevents *owner from exitting right here?

Quoted 47 lines
kernel/mutex.c +13 -4
+		get_task_struct(owner);
 		spin_unlock_mutex(&lock->wait_lock, flags);
-		schedule();
+
+		if (adaptive_wait(&waiter, owner, state)) {
+			put_task_struct(owner);
+			__set_task_state(task, state);
+			/* didnt get the lock, go to sleep: */
+			schedule();
+		} else
+			put_task_struct(owner);
+
 		spin_lock_mutex(&lock->wait_lock, flags);
 	}
 
@@ -187,7 +219,7 @@ done:
 	lock_acquired(&lock->dep_map, ip);
 	/* got the lock - rejoice! */
 	mutex_remove_waiter(lock, &waiter, task_thread_info(task));
-	debug_mutex_set_owner(lock, task_thread_info(task));
+	lock->owner = task;
 
 	/* set it to 0 if there are no waiters left: */
 	if (likely(list_empty(&lock->wait_list)))
@@ -260,7 +292,7 @@ __mutex_unlock_common_slowpath(atomic_t 
 		wake_up_process(waiter->task);
 	}
 
-	debug_mutex_clear_owner(lock);
+	lock->owner = NULL;
 
 	spin_unlock_mutex(&lock->wait_lock, flags);
 }
@@ -352,7 +384,7 @@ static inline int __mutex_trylock_slowpa
 
 	prev = atomic_xchg(&lock->count, -1);
 	if (likely(prev == 1)) {
-		debug_mutex_set_owner(lock, current_thread_info());
+		lock->owner = current;
 		mutex_acquire(&lock->dep_map, 0, 1, _RET_IP_);
 	}
 	/* Set it back to 0 if there are no waiters: */

Index: linux-2.6/kernel/sched.c
===================================================================

kernel/sched.c int runqueue_is_locked(void) · line 703

Quoted 7 lines
kernel/sched.c +4 -0
@@ -697,6 +697,11 @@ int runqueue_is_locked(void)
 	return ret;
 }
 
+int task_is_current(struct task_struct *p)
+{
+	return task_rq(p)->curr == p;
+}

Please don't add kernel-wide infrastructure and leave it completely undocumented. Particularly functions which are as vague and dangerous as this one.

What locking must the caller provide? What are the semantics of the return value?

What must the caller do to avoid oopses if *p is concurrently exiting?

etc.

The overall design intent seems very smart to me, as long as the races can be plugged, if they're indeed present.

#348 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 11 lines · Andrew Morton
Quoted 6 lines · On Tue, 06 Jan 2009 12:40:31 +0100 Peter Zijlstra <[email protected]> wrote:

Subject: mutex: adaptive spin
From: Peter Zijlstra <[email protected]>
Date: Tue Jan 06 12:32:12 CET 2009

Based on the code in -rt, provide adaptive spins on generic mutexes.

How dumb is it to send a lump of uncommented, changelogged code as an rfc, only to have Ingo reply, providing the changelog for you?

Sounds smart to me. He was able to get someone else to do the work. ;-)

Quoted 26 lines

Sigh.

Quoted 23 lines
kernel/mutex.c +10 -0
@@ -46,6 +46,7 @@ __mutex_init(struct mutex *lock, const c
 	atomic_set(&lock->count, 1);
 	spin_lock_init(&lock->wait_lock);
 	INIT_LIST_HEAD(&lock->wait_list);
+	lock->owner = NULL;
 
 	debug_mutex_init(lock, name, key);
 }
@@ -120,6 +121,28 @@ void __sched mutex_unlock(struct mutex *
 
 EXPORT_SYMBOL(mutex_unlock);
 
+#ifdef CONFIG_SMP
+static int adaptive_wait(struct mutex_waiter *waiter,
+			 struct task_struct *owner, long state)
+{
+	for (;;) {
+		if (signal_pending_state(state, waiter->task))
+			return 0;
+		if (waiter->lock->owner != owner)
+			return 0;
Quoted 8 lines

kernel/mutex.c void __sched mutex_unlock(struct mutex * · line 137

Quoted 5 lines
kernel/mutex.c +5 -0
+		if (!task_is_current(owner))
+			return 1;
+		cpu_relax();
+	}
+}

Each of the tests in this function should be carefully commented. It's really the core piece of the design.

Yep, I agree here too.

Quoted 35 lines
Quoted 35 lines
kernel/mutex.c +10 -2
+#else
+static int adaptive_wait(struct mutex_waiter *waiter,
+			 struct task_struct *owner, long state)
+{
+	return 1;
+}
+#endif
+
 /*
  * Lock a mutex (possibly interruptible), slowpath:
  */
@@ -127,7 +150,7 @@ static inline int __sched
 __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	       	unsigned long ip)
 {
-	struct task_struct *task = current;
+	struct task_struct *owner, *task = current;
 	struct mutex_waiter waiter;
 	unsigned int old_val;
 	unsigned long flags;
@@ -141,6 +164,7 @@ __mutex_lock_common(struct mutex *lock, 
 	/* add waiting tasks to the end of the waitqueue (FIFO): */
 	list_add_tail(&waiter.list, &lock->wait_list);
 	waiter.task = task;
+	waiter.lock = lock;
 
 	old_val = atomic_xchg(&lock->count, -1);
 	if (old_val == 1)
@@ -175,11 +199,19 @@ __mutex_lock_common(struct mutex *lock, 
 			debug_mutex_free_waiter(&waiter);
 			return -EINTR;
 		}
-		__set_task_state(task, state);
 
Quoted 4 lines

kernel/mutex.c __mutex_lock_common(struct mutex *lock, · line 203

Quoted 2 lines
kernel/mutex.c +1 -1
-		/* didnt get the lock, go to sleep: */
+		owner = lock->owner;

What prevents *owner from exitting right here?

Yeah, this should be commented. Why this is not a race is because the owner has the mutex here, and we have the lock->wait_lock. When the owner releases the mutex it must go into the slow unlock path and grab the lock->wait_lock spinlock. Thus it will block and not go away.

Of course if there's a bug elsewhere in the kernel that lets the task exit without releasing the mutex, this will fail. But in that case, there's bigger problems that need to be fixed.

Quoted 3 lines

kernel/mutex.c __mutex_lock_common(struct mutex *lock, · line 205

Quoted 3 lines
kernel/mutex.c +1 -0
+		get_task_struct(owner);
 		spin_unlock_mutex(&lock->wait_lock, flags);

Here, we get the owner before releasing the wait_lock.

Quoted 60 lines
Quoted 45 lines
kernel/mutex.c +12 -4
-		schedule();
+
+		if (adaptive_wait(&waiter, owner, state)) {
+			put_task_struct(owner);
+			__set_task_state(task, state);
+			/* didnt get the lock, go to sleep: */
+			schedule();
+		} else
+			put_task_struct(owner);
+
 		spin_lock_mutex(&lock->wait_lock, flags);
 	}
 
@@ -187,7 +219,7 @@ done:
 	lock_acquired(&lock->dep_map, ip);
 	/* got the lock - rejoice! */
 	mutex_remove_waiter(lock, &waiter, task_thread_info(task));
-	debug_mutex_set_owner(lock, task_thread_info(task));
+	lock->owner = task;
 
 	/* set it to 0 if there are no waiters left: */
 	if (likely(list_empty(&lock->wait_list)))
@@ -260,7 +292,7 @@ __mutex_unlock_common_slowpath(atomic_t 
 		wake_up_process(waiter->task);
 	}
 
-	debug_mutex_clear_owner(lock);
+	lock->owner = NULL;
 
 	spin_unlock_mutex(&lock->wait_lock, flags);
 }
@@ -352,7 +384,7 @@ static inline int __mutex_trylock_slowpa
 
 	prev = atomic_xchg(&lock->count, -1);
 	if (likely(prev == 1)) {
-		debug_mutex_set_owner(lock, current_thread_info());
+		lock->owner = current;
 		mutex_acquire(&lock->dep_map, 0, 1, _RET_IP_);
 	}
 	/* Set it back to 0 if there are no waiters: */

Index: linux-2.6/kernel/sched.c
===================================================================

kernel/sched.c int runqueue_is_locked(void) · line 703

Quoted 7 lines
kernel/sched.c +4 -0
@@ -697,6 +697,11 @@ int runqueue_is_locked(void)
 	return ret;
 }
 
+int task_is_current(struct task_struct *p)
+{
+	return task_rq(p)->curr == p;
+}

Please don't add kernel-wide infrastructure and leave it completely undocumented. Particularly functions which are as vague and dangerous as this one.

What locking must the caller provide? What are the semantics of the return value?

Quoted 7 lines

What must the caller do to avoid oopses if *p is concurrently exiting?

etc.

The overall design intent seems very smart to me, as long as the races can be plugged, if they're indeed present.

Thanks for the complement on the design. It came about lots of work by many people in the -rt tree. What we need here is to comment the code for those that did not see the evolution of the changes that were made.

-- Steve

#349 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Peter Zijlstra

Ok, last comment, I promise.

Quoted 11 lines · Peter Zijlstra
kernel/mutex.c +2 -3
@@ -175,11 +199,19 @@ __mutex_lock_common(struct mutex *lock, 
 			debug_mutex_free_waiter(&waiter);
 			return -EINTR;
 		}
-		__set_task_state(task, state);
 
-		/* didnt get the lock, go to sleep: */
+		owner = lock->owner;
+		get_task_struct(owner);
 		spin_unlock_mutex(&lock->wait_lock, flags);
-		schedule();

kernel/mutex.c __mutex_lock_common(struct mutex *lock, · line 215

Quoted 10 lines
kernel/mutex.c +9 -0
+
+		if (adaptive_wait(&waiter, owner, state)) {
+			put_task_struct(owner);
+			__set_task_state(task, state);
+			/* didnt get the lock, go to sleep: */
+			schedule();
+		} else
+			put_task_struct(owner);
+
 		spin_lock_mutex(&lock->wait_lock, flags);

So I really dislike the whole get_task_struct/put_task_struct thing. It seems very annoying. And as far as I can tell, it's there _only_ to protect "task->rq" and nothing else (ie to make sure that the task doesn't exit and get freed and the pointer now points to la-la-land).

Wouldn't it be much nicer to just cache the rq pointer (take it while still holding the spinlock), and then pass it in to adaptive_wait()?

Then, adaptive_wait() can just do

	if (lock->owner != owner)
		return 0;

	if (rq->task != owner)
		return 1;

Sure - the owner may have rescheduled to another CPU, but if it did that, then we really might as well sleep. So we really don't need to dereference that (possibly stale) owner task_struct at all - because we don't care. All we care about is whether the owner is still busy on that other CPU that it was on.

Hmm? So it looks to me that we don't really need that annoying "try to protect the task pointer" crud. We can do the sufficient (and limited) sanity checking without the task even existing, as long as we originally load the ->rq pointer at a point where it was stable (ie inside the spinlock, when we know that the task must be still alive since it owns the lock).

Linus

#350 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 22 lines · Linus Torvalds

Ok, last comment, I promise.

Quoted 18 lines · Peter Zijlstra
kernel/mutex.c +9 -3
@@ -175,11 +199,19 @@ __mutex_lock_common(struct mutex *lock, 
 			debug_mutex_free_waiter(&waiter);
 			return -EINTR;
 		}
-		__set_task_state(task, state);
 
-		/* didnt get the lock, go to sleep: */
+		owner = lock->owner;
+		get_task_struct(owner);
 		spin_unlock_mutex(&lock->wait_lock, flags);
-		schedule();
+
+		if (adaptive_wait(&waiter, owner, state)) {
+			put_task_struct(owner);
+			__set_task_state(task, state);
+			/* didnt get the lock, go to sleep: */
+			schedule();
+		} else
Quoted 8 lines

kernel/mutex.c __mutex_lock_common(struct mutex *lock, · line 215

Quoted 3 lines
kernel/mutex.c +2 -0
+			put_task_struct(owner);
+
 		spin_lock_mutex(&lock->wait_lock, flags);

So I really dislike the whole get_task_struct/put_task_struct thing. It seems very annoying. And as far as I can tell, it's there _only_ to protect "task->rq" and nothing else (ie to make sure that the task doesn't exit and get freed and the pointer now points to la-la-land).

Yeah, that was not one of the things that we liked either. We tried other ways to get around the get_task_struct but, ended up with the get_task_struct in the end anyway.

Quoted 18 lines

Wouldn't it be much nicer to just cache the rq pointer (take it while still holding the spinlock), and then pass it in to adaptive_wait()?

Then, adaptive_wait() can just do

	if (lock->owner != owner)
		return 0;

	if (rq->task != owner)
		return 1;

Sure - the owner may have rescheduled to another CPU, but if it did that, then we really might as well sleep. So we really don't need to dereference that (possibly stale) owner task_struct at all - because we don't care. All we care about is whether the owner is still busy on that other CPU that it was on.

Quoted 6 lines

Hmm? So it looks to me that we don't really need that annoying "try to protect the task pointer" crud. We can do the sufficient (and limited) sanity checking without the task even existing, as long as we originally load the ->rq pointer at a point where it was stable (ie inside the spinlock, when we know that the task must be still alive since it owns the lock).

Caching the rq is an interesting idea. But since the rq struct is local to sched.c, what would be a good API to do this?

in mutex.c:

	void *rq;

	[...]

	rq = get_task_rq(owner);
	spin_unlock(&lock->wait_lock);

	[...]

	if (!task_running_on_rq(rq, owner))

in sched.c:

	void *get_task_rq(struct task_struct *p)
	{
		return task_rq(p);
	}

	int task_running_on_rq(void *r, struct task_sturct *p)
	{
		struct rq *rq = r;

		return rq->curr == p;
	}

??

-- Steve

#351 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 3 lines · Steven Rostedt

Caching the rq is an interesting idea. But since the rq struct is local to sched.c, what would be a good API to do this?

Just move the whole "spin_or_schedule()" into sched.c, and you're all done.

Yeah, that requires having sched.c know a bit about mutex locking rules, but the data structures are already exported in <linux/mutex.h>, and while _normal_ code should never care or know exactly how it is used, I think the scheduler might as well. Mutexes are clearly very much a scheduling entity, so it's not too much of a break with internal knowledge.

Linus

#352 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

In reply to Linus Torvalds
Quoted 3 lines · Linus Torvalds

Sure - the owner may have rescheduled to another CPU, but if it did that, then we really might as well sleep.

.. or at least re-try the loop.

It might be worth it to move the whole sleeping behavior into that helper function (mutex_spin_or_sleep()), and just make the logic be:

- if we _enter_ the function with the owner not on a runqueue, then we sleep

- otherwise, we spin as long as the owner stays on the same runqueue.

and then we loop over the whole "get mutex spinlock and revalidate it all" after either sleeping or spinning for a while.

That seems much simpler in all respects. And it should simplify the whole patch too, because it literally means that in the main __mutex_lock_common(), the only real difference is

	-             __set_task_state(task, state);
	-             spin_unlock_mutex(&lock->wait_lock, flags);
	-             schedule();

becoming instead

	+		mutex_spin_or_schedule(owner, task, lock, state);

and then all the "spin-or-schedule" logic is in just that one simple routine (that has to look up the rq and drop the lock and re-take it).

The "mutex_spin_or_schedule()" code would literally look something like

	void mutex_spin_or_schedule(owner, task, lock, state)
	{
		struct rq *owner_rq = owner->rq;

		if (owner_rq->curr != owner) {
			__set_task_state(task, state);
			spin_unlock_mutex(&lock->wait_lock, flags);
			schedule();
		} else {
			spin_unlock_mutex(&lock->wait_lock, flags);
			do {
				cpu_relax();
			while (lock->owner == owner &&
				owner_rq->curr == owner);
		}
		spin_lock_mutex(&lock->wait_lock, flags);
	}

or something.

Btw, this also fixes a bug: your patch did

	+                     __set_task_state(task, state);
	+                     /* didnt get the lock, go to sleep: */
	+                     schedule();

for the schedule case without holding the mutex spinlock.

And that seems very buggy and racy indeed: since it doesn't hold the mutex lock, if the old owner releases the mutex at just the right point (yeah, yeah, it requires a scheduling event on another CPU in order to also miss the whole "task_is_current()" logic), the wakeup can get lost, because you set the state to sleeping perhaps _after_ the task just got woken up. So we stay sleeping even though the mutex is clear.

So I'm going to NAK the original patch, and just -require- the cleanup I'm suggesting as also fixing what looks like a bug.

Of course, once I see the actual patch, maybe I'm going to find something _else_ to kwetch about.

Linus

#353 lore raw

Re: [PATCH][RFC]: mutex: adaptive spin

Quoted 8 lines

Btw, this also fixes a bug: your patch did

	+                     __set_task_state(task, state);
	+                     /* didnt get the lock, go to sleep: */
	+                     schedule();
Quoted 8 lines

for the schedule case without holding the mutex spinlock.

And that seems very buggy and racy indeed: since it doesn't hold the mutex lock, if the old owner releases the mutex at just the right point (yeah, yeah, it requires a scheduling event on another CPU in order to also miss the whole "task_is_current()" logic), the wakeup can get lost, because you set the state to sleeping perhaps _after_ the task just got woken up. So we stay sleeping even though the mutex is clear.

That is indeed a bug.

Peter, why did you need to move __set_task_state down here? The -rt patch does not do this.

-- Steve

#354 lore raw
In reply to Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Quoted 4 lines · Matthew Wilcox
Quoted 3 lines

- locking.c needs a lot of cleanup.
If combination spinlocks/mutexes are really a win they should be in the generic mutex framework. And I'm still dubious on the

hardcoded

Quoted 8 lines
Quoted 1 line

numbers.

I don't think this needs to be cleaned up before merge. I've spent an hour or two looking at it, and while we can do a somewhat better job as part of the generic mutex framework, it's quite tricky (due to the different <asm/mutex.h> implementations). It has the potential to introduce some hard-to-hit bugs in the generic mutexes, and there's some API discussions to have.

Quoted 3 lines

I'm really opposed to having this in some filesystem. Please remove it before merging it.

It is 5 lines in a single function that is local to btrfs. I'll be happy to take it out when a clear path to a replacement is in.

I know people have been doing work in this area for -rt, and do not want to start a parallel effort to change things.

I'm not trying to jump into the design discussions because there are people already working on it who know the issues much better than I do.

But, if anyone working on adaptive mutexes is looking for a coder, tester, use case, or benchmark for their locking scheme, my hand is up.

Until then, this is my for loop, there are many like it, but this one is mine.

-chris

#355 lore raw
In reply to Chris Mason

Hi Chris,

Does this means that disk format finalised or at least backward compatible?

Quoted 28 lines · Chris Mason

Hello everyone,

I've done some testing against Linus' git tree from last night and the current btrfs trees still work well.

There are a few bug fixes that I need to include from while I was on vacation but I haven't made any large changes since early in December:

Btrfs details and usage information can be found:

http://btrfs.wiki.kernel.org/

The btrfs kernel code is here:

http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-unstable.git;a=summary

And the utilities are here:

http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-progs-unstable.git;a=summary

-chris

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#356 lore raw
Quoted 6 lines · Gabor MICSKO

Hi Chris,

Does this means that disk format finalised or at least backward compatible?

We're making every effort to avoid new disk format changes now (that are not backward compatible). Only a critical bug would result in a disk format change now.

-chris

#357 lore raw
Quoted 11 lines · Chris Mason
Quoted 6 lines · Gabor MICSKO

Hi Chris,

Does this means that disk format finalised or at least backward compatible?

We're making every effort to avoid new disk format changes now (that are not backward compatible). Only a critical bug would result in a disk format change now.

Is this means that new format is ready for RAID5-like disk layout?

Signature · 2 lines
Tomasz Torcz                Only gods can safely risk perfection,
[email protected]     it's a dangerous thing for a man.  -- Alia
#358 lore raw
Quoted 9 lines · Tomasz Torcz
Quoted 8 lines · Chris Mason
Quoted 6 lines · Gabor MICSKO

Hi Chris,

Does this means that disk format finalised or at least backward compatible?

Quoted 7 lines
Quoted 3 lines

We're making every effort to avoid new disk format changes now (that are not backward compatible). Only a critical bug would result in a disk format change now.

Is this means that new format is ready for RAID5-like disk layout?

That will be done through forward compat bits. So you won't be able to use today's code to mount a RAID5 FS, but the raid5 fs will understand today's FS.

-chris

#359 lore raw
In reply to Chris Mason

Hello everyone,

Thanks for all of the comments so far. I've pushed out a number of fixes for btrfs mainline, covering most of the comments from this thread.

* All LINUX_KERNEL_VERSION checks are gone.
* checkpatch.pl fixes
* Extra permission checks on the ioctls
* Some important bug fixes from the btrfs list
* Andi found a buggy use of kmap_atomic during checksum verification
* Drop EXPORT_SYMBOLs from extent_io.c

Unresolved from this reviewing thread:

* Should it be named btrfsdev? My vote is no, it is extra work for the distros when we finally do rename it, and I don't think btrfs really has the reputation for stability right now. But if Linus or Andrew would prefer the dev on there, I'll do it.

* My ugly mutex_trylock spin. It's a hefty performance gain so I'm hoping to keep it until there is a generic adaptive lock.

The full kernel tree is here:

http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-unstable.git;a=summary

The standalone tree just has the btrfs files and commits, reviewers may find it easier:

http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-unstable-standalone.git;a=summary

The utilities can be found here:

http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-progs-unstable.git;a=summary

-chris

#360 lore raw
Quoted 6 lines · Chris Mason

Hello everyone,

Thanks for all of the comments so far. I've pushed out a number of fixes for btrfs mainline, covering most of the comments from this thread.

Quoted 6 lines

* All LINUX_KERNEL_VERSION checks are gone.
* checkpatch.pl fixes
* Extra permission checks on the ioctls
* Some important bug fixes from the btrfs list
* Andi found a buggy use of kmap_atomic during checksum verification
* Drop EXPORT_SYMBOLs from extent_io.c

Looking good...

Quoted 6 lines

Unresolved from this reviewing thread:

* Should it be named btrfsdev? My vote is no, it is extra work for the distros when we finally do rename it, and I don't think btrfs really has the reputation for stability right now. But if Linus or Andrew would prefer the dev on there, I'll do it.

I agree; I don't think there's any particular need for the 'dev' suffix. It's already dependent on CONFIG_EXPERIMENTAL, after all.

Quoted 2 lines

* My ugly mutex_trylock spin. It's a hefty performance gain so I'm hoping to keep it until there is a generic adaptive lock.

If a better option is forthcoming, by all means use it -- but I wouldn't see the existing version as a barrier to merging.

One more thing I'd suggest is removing the INSTALL file. The parts about having to build libcrc32c aren't relevant when it's part of the kernel tree and you have 'select LIBCRC32C', and the documentation on the userspace utilities probably lives _with_ the userspace repo. Might be worth adding a pointer to the userspace utilities though, in Documentation/filesystems/btrfs.txt

I think you can drop your own copy of the GPL too.

Signature · 2 lines
David Woodhouse                            Open Source Technology Centre
[email protected]                              Intel Corporation
#361 lore raw
Quoted 11 lines · David Woodhouse

On Tue, 2009-01-06 at 14:41 -0500, Chris Mason wrote:

One more thing I'd suggest is removing the INSTALL file. The parts about having to build libcrc32c aren't relevant when it's part of the kernel tree and you have 'select LIBCRC32C', and the documentation on the userspace utilities probably lives _with_ the userspace repo. Might be worth adding a pointer to the userspace utilities though, in Documentation/filesystems/btrfs.txt

I think you can drop your own copy of the GPL too.

I've pushed out your patch for this, thanks.

-chris

#362 lore raw
In reply to Chris Mason
Quoted 7 lines · Chris Mason

Unresolved from this reviewing thread:

* Should it be named btrfsdev? My vote is no, it is extra work for the distros when we finally do rename it, and I don't think btrfs really has the reputation for stability right now. But if Linus or Andrew would prefer the dev on there, I'll do it.

We know who has the last word on this.

This is just additional background for those who commented.

Using tricks such as btrfsdev, mount "unsafe", or kernel messages won't provide a guarantee that btrfs is only used in appropriate and risk-free ways. Those tricks also won't prevent all problems caused by booting a broken old (or new) release. And the perceived quality and performance of any filesystem release, even between stable versions, depends very much on individual system configuration and use.

Before Chris posted the code, we had some btrfs concall discussions about the best way to set user expectations on btrfs mainline 1.0. Consensus was that the best way we could do this was to warn them when they did mkfs.btrfs.

Today I sent a patch to Chris (which he may ignore/change) so mkfs.btrfs will say:

WARNING! - Btrfs v0.16-39-gf9972b4 IS EXPERIMENTAL WARNING! - see http://btrfs.wiki.kernel.org before using

with a blank line before and after. They don't have to confirm since they can just mkfs a different filesystem if I scared them away. The version is auto-generated.

jim

#365 lore raw

Hi,

Quoted 3 lines · Chris Mason
Quoted 2 lines · Andrew Morton

http://bugzilla.kernel.org/show_bug.cgi?id=12435

This is by far the biggest issue btrfs has for simple/domestic users. Its probably the most tested miss-feature of btrfs, something almost all new testers encounter & report.

Is fixing this having maximum priority?
The sooner this is fixed, less energy is spend by everyone (entusiasts, testers, bug reporters, bug triagers, mailing list campers..etc) and we might save some whales, dolphins and pinguins by reducing our carbon footprint. :)

Kind regards.

Quoted 7 lines
Quoted 1 line

Congratulations ;)

Rejected documented, that's the best buzilla tag ever ;)

Thanks,
Chris

Signature · 1 line
Miguel Sousa Filipe
#366 lore raw
Quoted 11 lines · Miguel Figueiredo Mascarenhas Sousa Filipe

Hi,

Quoted 3 lines · Chris Mason
Quoted 2 lines · Andrew Morton

http://bugzilla.kernel.org/show_bug.cgi?id=12435

This is by far the biggest issue btrfs has for simple/domestic users. Its probably the most tested miss-feature of btrfs, something almost all new testers encounter & report.

Quoted 6 lines

Is fixing this having maximum priority?
The sooner this is fixed, less energy is spend by everyone (entusiasts, testers, bug reporters, bug triagers, mailing list campers..etc) and we might save some whales, dolphins and pinguins by reducing our carbon footprint. :)

Yes, this definitely at the top of my list. Along with better documentation of the project as a whole.

-chris