C undefined behavior fix

[Cc: to gcc list, in case someone wants to argue about standards]

The appended patch fix incorrect code, which interferes badly with optimizations in GCC 3.0.4 and GCC 3.1.

The GCC tries to replace the strcpy from a constant string source with a memcpy, since the length is know at compile time.

Thus
strcpy (dst, "abcdef" + 2)
gives
memcpy (dst, "abcdef" + 2, 5)

However, GCC does not handle the case, when the above offset (2) is not within the bounds of the string, which result in undefined behavior according to ANSI/ISO C99.

The error is that
strcpy (namep, "linux,phandle" + 0xc0000000);
gets emitted as
memcpy (namep, "linux,phandle" + 0xc0000000, 14 - 0xc0000000);

Regards,
-velco

@@ -997,7 +997,7 @@
 		prev_propp = &pp->next;
 		namep = (char *) (pp + 1);
 		pp->name = PTRUNRELOC(namep);
-		strcpy(namep, RELOC("linux,phandle"));
+		memcpy (namep, RELOC("linux,phandle"), sizeof("linux,phandle"));
 		mem_start = ALIGN((unsigned long)namep + strlen(namep) + 1);
 		pp->value = (unsigned char *) PTRUNRELOC(&np->node);
 		pp->length = sizeof(np->node);

Check the linuxppc-dev archives, but this has been discussed before, and it came down to a few things.
1) gcc shouldn't be making this optimization, and Paulus (who wrote the code) disliked this new feature. As a subnote, what you sent was sent to Linus with a comment about working around a gcc-3.0 bug/feature, and was rejected because of this.
2) We could modify the RELOC macro, and not have this problem. The patch was posted, but not acted upon.
3) We could also try turning off this particular optimization (-fno-builtin perhaps) on this file, and not worry about it.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

In particular, it would probably make sense for the kernel to use -ffreestanding (which implies -fno-builtin) throughout then selectively enable the built-in functions that are wanted with macros such as

#define strcpy(d, s) __builtin_strcpy((d), (s))

in an appropriate header, then #undef these macros in the files that shouldn't use the built-in functions.

Joseph S. Myers
[email protected]

Tom> Check the linuxppc-dev archives, but this has been discussed before, and Tom> it came down to a few things.

Well, you may discuss it again, but this time after actually reading the C standard:

"6.3.6 Additive operators
...

9 Unless both the pointer operand and the result point to
elements of the same array object, or the pointer operand points one past the last element of an array object and the result points to an element of the same array object, the behavior is undefined if the result is used as an operand of a unary * operator that is actually evaluated."

Tom> 1) gcc shouldn't be making this optimization, and Paulus (who wrote the Tom> code) disliked this new feature.

Why gcc shouldn't be making some optimization. Because a particular person doesn't like it or ? What kind of statement is that anyway ?

Tom> As a subnote, what you sent was sent
Tom> to Linus with a comment about working around a gcc-3.0 bug/feature, and Tom> was rejected because of this.

It is not a workaround, it is a fix to an invalid code, which gets triggered by particular optimization.

Tom> 2) We could modify the RELOC macro, and not have this problem. The Tom> patch was posted, but not acted upon.

Although all uses of the RELOC macro violate the standard, this kind of pointer arithmetic is far too common and usually produces the expected behavior, thus it make sense to optimize the cases where ut breaks

Tom> 3) We could also try turning off this particular optimization Tom> (-fno-builtin perhaps) on this file, and not worry about it.

*mutters something about head and sand* ;)

Regards,
-velco

One of the reasons why C is a good language for the kernel is that its memory model is a good match to the memory organization used by the processors that linux runs on. Thus, for these processors, adding an offset to a pointer is in fact simply an arithmetic addition. Combine that with the fact that the kernel is far more aware of how stuff is laid out in its virtual memory space than most C programs, and you can see that it is reasonable for the kernel to do pointer arithmetic which might be undefined according to the strict letter of the law, but which in fact works correctly on the class of processors that Linux runs on, for all reasonable compiler implementations.

The rules in the C standard are designed to allow a program to run consistently on a wide variety of machine architectures, including things like the DEC PDP-10 which weren't directly byte-addressable. (Yes the PDP-10 had "byte pointers" but they were a different kind of object from an ordinary pointer.) The Linux kernel runs on a more restricted range of machines and IMHO we are entitled to assume things because of that.

This is the kernel. If I say strcpy I want the compiler to call a function called strcpy, not to try to second-guess me and do something different. If I want memcpy I'll write "memcpy".

If the gcc maintainers think they are entitled to change the memory model so as to break pointer arithmetic that "violates" the standard, then we will have to use a different compiler.

As for the original problem, my preferred solution at the moment is to add an label in arch/ppc/lib/string.S so that string_copy() is the same function as strcpy(), and use string_copy instead of strcpy in prom.c.

Paul.

Florian> Doesn't this still trigger undefined behavior, as far as the C Florian> standard is concerned? It's probably a better idea to fix the linker, Florian> so that it performs proper relocation.

Well, strictly speaking it _is_ undefined, however adding/subtracting __PAGE_OFFSET is far too common operation and one can resonably expect to get away with it in the _vast_ majority of cases. IMHO, it is better to fix the particular case, which triggers the undefined behaviour, as these cases are bound to be _very_ rare.

Regards,
-velco

IMHO gcc should not be touching these function calls, as they are not made to a standard C library, and thus have different behaviors. I'm suprised that gcc tries to optimize calls to these functions just based on their names.

The gcc manpage mentions

-ffreestanding
Assert that compilation takes place in a freestanding environment. This implies -fno-builtin. A freestand­ ing environment is one in which the standard library may not exist, and program startup may not necessarily be at "main". The most obvious example is an OS ker­ nel. This is equivalent to -fno-hosted.

Why is Linux not using this? It sounds very appropriate. The only things the manpage mentions that -fno-builtin would inhibit from being optimized are memcpy() and alloca(). memcpy() has its own assembly optimization and inlining on some (most?) archs, and as for alloca(), I only see it being used a bit in the S/390 code, where the gcc optimizations could quite possibly break something. I think -ffreestanding definately should be used by the kernel to prevent gcc from messing with its code in broken ways.

There are others in newer gcc's, and on the whole gcc does a very good job with them, so IMHO it is worth being nice to gcc to get the advantages.

-ffreestanding for the compiler versions that support it can be added to arch specific flags anyway

Aaron> IMHO gcc should not be touching these function calls, as they are not Aaron> made to a standard C library, and thus have different behaviors. I'm Aaron> suprised that gcc tries to optimize calls to these functions just Aaron> based on their names.

IIRC, these identifiers are reserved by the C standard, thus the compiler is right to assume that they have standard behavior. And note that they DO have the standard behavior. It even doesn't matter if GCC is right to judge by the names in each and every case, it is right in _this_ case.

Aaron> The gcc manpage mentions

Aaron> -ffreestanding

Aaron>            Assert that compilation takes place in a freestanding
Aaron>            environment.  This implies -fno-builtin.  A freestand­
Aaron>            ing environment is one in which the standard library
Aaron>            may not exist, and program startup may not necessarily
Aaron>            be at "main".  The most obvious example is an OS ker­
Aaron>            nel.  This is equivalent to -fno-hosted.

Aaron> Why is Linux not using this? It sounds very appropriate. The only

Because it results in less optimization. I see no point in deliberately preventing the compiler from doing optimizations.

Regards,
-velco

IMHO the best thing is to change the RELOC macro, so that gcc cannot optimize this.
E.g.:
-#define PTRRELOC(x) ((typeof(x))((unsigned long)(x) + offset))

+#define PTRRELOC(x)     ({ unsigned long __x = (unsigned long)(x);	\
			    asm ("" : "=r" (__x) : "0" (__x));		\
			    (typeof(x))(__x + offset); })

This way gcc cannot assume anything about it.

Jakub

Well, Paulus wrote 'strcpy' not 'memcpy', so why does gcc get to assume it's safe to change it? In this case it's certainly not.

By a particular optimization that's not present before gcc-3.0, and happens to break things under some conditions, as you've seen.

And for the case it breaks?

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

But unless you trigger undefined behaviour, strcpy(x, "foobar" + n) is equal to memcpy(x, "foobar" + n, sizeof("foobar") - n); and the latter is more efficient (you don't have to check for end-of-string during copying).

It just happens to do a different thing than it used to when seeing code with particular case of undefined behaviour.

Jakub

This has been suggested too. And if someone implemements this in the 2.5.x timeframe it might even go in (as long as it works w/ gcc-2.95.x, which really should be doable).

This is what Franz Sirl suggested awhile back, which should work, but doesn't look too nice. If gcc-3.0.x is going to be expected to produce a working kernel on all arches, I suppose this is the best fix for now.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

Right. The problem here is that this happens to be at a very early point in the code (from arch/ppc/kernel/prom.c):
/*
* Note that prom_init() and anything called from prom_init() must
* use the RELOC/PTRRELOC macros to access any static data in
* memory, since the kernel may be running at an address that is
* different from the address that it was linked at.
* (Note that strings count as static variables.)
*/

Which is where the trouble comes in.

Right. There's only a very small number of files which _might_ be effected by this optimization.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

Jakub> But unless you trigger undefined behaviour, strcpy(x, "foobar" Jakub> + n) is equal to memcpy(x, "foobar" + n, sizeof("foobar") - Jakub> n); and the latter is more efficient (you don't have to check Jakub> for end-of-string during copying).

I'd say it's the same even if you DO trigger undefined behavior.

"Undefined" means "anything can happen, don't blame the compiler". In particular, different things may happen at different times, under different compilers, under different phases of the moon, etc...

The change from strcpy to memcpy either replaces a defined action by the equivalent one, or replaces an undefined action by an undefined action. In the undefined case, the outcome may be different after the change, but that's perfectly ok, that's what "undefined" means.

It might be interesting for the compiler to warn about this coding error (since it presumably can detect it). But "fixing" the behavior of undefined code seems like a strange thing to do.

paul

Okay, here's a summary of all of the options we have:
1) Change this particular strcpy to a memcpy
2) Add -ffreestanding to the CFLAGS of arch/ppc/kernel/prom.o (If this optimization comes back on with this flag later on, it would be a compiler bug, yes?)
3) Modify the RELOC() marco in such a way that GCC won't attempt to optimize anything which touches it [1]. (Franz, again by Jakub)
4) Introduce a function to do the calculations [2]. (Corey Minyard)
5) 'Properly' set things up so that we don't need the RELOC() macros (-mrelocatable or so?), and forget this mess altogether.

I think that if we're going to make sure that gcc-3.0.x works with 2.4.x kernels, we should pick one of the first 4 initially. If this is only a 2.5.x matter, we should probably try and do #5 as a long-term goal, and pick something else for now. But either way I do think it's time to pick some solution. Comments?

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

[1] http://lists.linuxppc.org/linuxppc-dev/200109/msg00155.html
[2] http://lists.linuxppc.org/linuxppc-dev/200112/msg00038.html

2) will prevent any future gcc from ever assuming it can transform the strcpy into anything but a call to strcpy, or assume anything about the semantics of strcpy. Be careful with 3), as trying to fool the optimizer is likely to be only a temporary solution (meaning that the kernel people will return to flame the gcc people when the optimizer gets changed again).

If we go with this, it also might make sense to split all of the {PTR,UN,}RELOC() macro users into a different file or split up btext.c a bit more, just to be safe.

Well, it's one of those changes that really should stop gcc, unless there's a bug on the gcc side, if I read the patch/comments about it right.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

I would add:

6) change strcpy to string_copy so gcc doesn't think it knows what the function does
7) code RELOC etc. in assembly, which would let us get rid of the

	offset = reloc_offset();

at the beginning of each function which uses RELOC.

Maybe 7 is the way to go, at least it will shut the bush-lawyers up.

Paul.

No. You still have the problem of using pointer arithmetic past one past the end of the object.

C99 6.5.6/8:

If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

r~

Yes, but you're on much safer ground here, since the conversion is implementation defined. Practical considerations almost guarantee the implementation choice will be "int == address" for targets where this makes sense (e.g. has a simple, flat, contiguous address space).

Also, in the latest version of the C standard, you do have a int type that can contain a pointer.

Allowing people to treat pointers as if they were "just" integers prevents a whole slew of interesting and useful compiler transformations, which is why the standard frowns upon such behavior. Buffer overflow checks are an example. It's possible to build bounded pointer implementations for strict ANSI C, but impossible for the "all pointers are just integers" variant.

Do the compiler a favor. If you're playing with pointers as if they are integers, make them integers. Types are your friend.

-Tim

Well, the problem is that we aren't running where the compiler thinks we are yet. So what would the right fix be for this?

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

Obviously -ffreestanding isn't, because this problem could crop up pretty much anywhere. The involvement of standard library functions is almost coincidence and so -ffreestanding would only fix the current symptom.

I'm not much of a kernel hacker, but a quick (and not very efficient, granted) fix could be to make the offset an extern variable, yes? That would force the compiler to fall back on the basic "your gun, your foot, your choice" memory model.

Jeroen

Assembly.

r~

That's not really an option.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

Oh come on. It shouldn't take very much code at all to properly relocate the binary. You can use either -fpic or -mrelocatable to get hold of the set of addresses in question.

r~

Have you looked at all of the code in question? We're doing a lot of things before we properly relocate ourself. And as long as things aren't being optimized away, it just works.

And the other thing is if we want gcc-3.0 to produce a good kernel on PPC in 2.4.x, the kernel-side changes should be as minimal as possible.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

After thinking about this a bit more, why wouldn't this be the fix? The problem is that gcc is assuming that this is a 'normal' program (or in this case, part of a program) and that it, and that the standard rules apply, so it optimizes the strcpy into a memcpy. But in this small bit of the kernel, it's not. It's not even using the 'standard library functions', but what the kernel provides. This problem can only crop up in the time before we finish moving ourself around.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

I think 7 sounds good for 2.4 at least, and maybe we can convince Franz to look into 5 for 2.5 (since that would make things look a bit more clean)..

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

Paul> One of the reasons why C is a good language for the kernel is that its Paul> memory model is a good match to the memory organization used by the Paul> processors that linux runs on. Thus, for these processors, adding an Paul> offset to a pointer is in fact simply an arithmetic addition. Combine Paul> that with the fact that the kernel is far more aware of how stuff is Paul> laid out in its virtual memory space than most C programs, and you can Paul> see that it is reasonable for the kernel to do pointer arithmetic Paul> which might be undefined according to the strict letter of the law, Paul> but which in fact works correctly on the class of processors that Paul> Linux runs on, for all reasonable compiler implementations.

Paul> The rules in the C standard are designed to allow a program to run Paul> consistently on a wide variety of machine architectures, including Paul> things like the DEC PDP-10 which weren't directly byte-addressable. Paul> (Yes the PDP-10 had "byte pointers" but they were a different kind of Paul> object from an ordinary pointer.) The Linux kernel runs on a more Paul> restricted range of machines and IMHO we are entitled to assume things Paul> because of that.

Paul> This is the kernel. If I say strcpy I want the compiler to call a Paul> function called strcpy, not to try to second-guess me and do something Paul> different. If I want memcpy I'll write "memcpy".

This is C. If you use ``strcpy'', an identifier reserved by the standard, it means that you want to move some bytes from here to there and please let the compiler decide how to do that. Much in the same way as when you assign structures and compiler uses ``memcpy'' or maybe it doesn't if it wouldn't be a win.

Paul> If the gcc maintainers think they are entitled to change the memory Paul> model so as to break pointer arithmetic that "violates" the standard, Paul> then we will have to use a different compiler.

Where do you see changes in pointer arithmetic ? Or in the "memory model" (whatever that means) ?

I'd dare to state that _very_ few people would join the quest for writing the kernel in something other than C.

Paul> As for the original problem, my preferred solution at the moment is to Paul> add an label in arch/ppc/lib/string.S so that string_copy() is the Paul> same function as strcpy(), and use string_copy instead of strcpy in Paul> prom.c.

The C standard says that doing pointer arithmetic is only valid within the bounds of a particular array of objects; do anything outside that and the behaviour is "undefined". The reason it says that is that it is trying to lay down the rules that will ensure that your program will work on a PDP-10 or on a 286 with 64kB segments, as well as on reasonable architectures (such as those that Linux runs on).

Now the claim is that RELOC is bad because it adds an offset to a pointer, and the offset is usually around 0xc0000000, and thus we are "violating" the C standard. Thus we are being told that someday this will break and cause a lot of grief. My contention is that this will only break if a pointer becomes something other than a simple address and pointer arithmetic becomes something other than simple 2's complement addition, subtraction, etc. If that happens then C will have become useless for implementing a kernel, IMHO.

The kernel is already written in a dialect of C that breaks some of the rules in the C standard. Look at virt_to_phys, phys_to_virt, __pa, __va, etc. for a start. I don't see that changing.

Paul.

Well, pointer arithmetic on the HPPA isn't simple 2's complement due to the way implicit space register selection works.

For example in an unscaled indexed addressing mode like

ldbx srcreg1(srcreg2), dstreg

Is not equivalent to

ldbx srcreg2(srcreg1), dstreg

ie x + y != y + x for computing an address in a memory operation.

For the same reason computing an address outside of an object into a register, then using a displacement in a memory operation to generate an address that is within the bounds of the object may not work. ie, you can't do something like this and expect it to work:

int a[10];
int *z = a - 10;

foo()
{
return z[10];
}

And before anyone says the PA is unbelievably strange and nobody else would make the same mistakes -- the mn10300 (for which a linux port does exist) has the same failings.

jeff

I tried to locate info about this port, but I couldn't find any. Do you have any pointers?

Lars Brinkhoff          http://lars.nocrew.org/     Linux, GCC, PDP-10
Brinkhoff Consulting    http://www.brinkhoff.se/    programming

I'm not arguing your facts, but the "abnormality" is in the different workings of memory addresses, not in anything related to the standard library. What if these functions were named differently but gcc were able to inline them? AFAICS that might trigger the same problem--no cstdlib confusion involved.

Conversely, what if these were the real stdlib calls that they seem to be? Still the same bug. Absence or presence of the standard library is not essential to the problem, and so -ffreestanding can be a fragile workaround at best.

The bug just happens to get triggered by a 'builtin' optimization, because gcc 3.0.3 is a little more aggressive with those. We can't keep the progress of gcc's optimizer back just for a kernel. Asking for a new option or #pragma, okay. But weeding out otherwise valid assumptions that help many inputs but break one? Better to fix the one, even if it does cost you some speed there.

Oh, and another suggestion: would having RELOC cast the pointer to the intermediate type "const volatile void *" make gcc drop its assumptions on that one pointer, and avoid the optimization? It may not be exactly what the Standard had in mind when it defined "volatile," but then again the definition was deliberately left vague.

OTOH it may have to be cast away again to make strcpy() work at all, and so that trick might still break...

Jeroen

And then optimizes it to something that fails to work in this particular case.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

Paul> I would add:

Paul> 6) change strcpy to string_copy so gcc doesn't think it knows what the
Paul> function does

GCC thinks exactly what the function does.

I'm not sure.. We do:

#define RELOC(x) (*PTRRELOC(&(x)))
#define PTRRELOC(x) ((typeof(x))((unsigned long)(x) + offset))

unsigned long offset = reloc_offset();
...
strcpy(namep, RELOC("linux,phandle"));

Which is basically inlining, yes?

Yes, but doesn't -ffreestanding imply that gcc _can't_ assume this is the standard library, and that strcpy _might_ not be what it thinks, and to just call strpy?

We aren't saying this is always a bad thing, but what if we want to turn off a built-in optimization? Unless -ffreestanding stops implying -fno-builtin (maybe we could just add -fno-builtin for this one file..), this line should be fine.

I _think_ this is option 3 or so that I mentioned in another email. Modify RELOC so that gcc will drop its assumptions and just do what we explicitly say.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

strcpy is part of the C standard. You'd need a -fits-not-c-its-linux

If you want a strcpy that isnt strcpy then change its name or use a different language 8)

(cc list trimmed)

The former is not necessarily sufficient in this case. You've still done the broken pointer arithmetic, so even if the function isn't called strcpy() the compiler is _still_ entitled to replace it with a call to memcpy() or even machine_restart() before sleeping with your mother and starting WW III.

Granted, it probably _won't_ do any of those today, but you should know better than to rely on that.

What part of 'undefined behaviour' is so difficult for people to understand?

--
dwmw2

I don't have the ANSI standard in front of me, isn't it the case that casting a pointer to/from an integer is implementation defined, rather than undefined, so people who need to do pointer arithmatic that relies on the machine's memory map can do
(void *)(((int)p) + some_magic_number)

and have some sort of assurance that the compiler won't mess with it?

-JKL

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

I think it comes down to an expectation that if the behaviour is undefined, anything _could_ happen, but what should happen is that it should just be passed along to (in this case) strcpy un-modified. Anything _could_ happen, but why do something that probably won't help all the same?

But this is moot anyhow since I _think_ Paul's suggestion of doing RELOC and friends as asm will work (and echo'd by rth?).

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

The behaviour is undefined by the C standard. But the mentioned pointer arithmetic is defined in the environment where it has been used. GCC tries to optimize undefined C-standard behaviour. And IMHO that's the point. It may optimize defined behaviour and should not touch things undefined by the standard.

Ciao, ET.

PS: Hey, we are talking about C, the de luxe assembler! *g*

Edgar> The behaviour is undefined by the C standard. But the mentioned Edgar> pointer arithmetic is defined in the environment where it has been Edgar> used. GCC tries to optimize undefined C-standard behaviour. And Edgar> IMHO that's the point. It may optimize defined behaviour and should Edgar> not touch things undefined by the standard.

How do you imagine that "not touch" ? like "#if 0 ... #endif" ?

Edgar> PS: Hey, we are talking about C, the de luxe assembler! *g*

Standard is a standard. Broken code is broken code. Sometimes you can get away with it, sometimes you can't and when you can't you fix the code. Or define your own standard and make a compiler implementing it.

Ah, if only things were that easy! The whole reason the rules are as they are in C is that it is not generally decidable whether or not the code falls within those rules. Removing the assumptions we're talking about from the rules would make the ability to optimize code an exception instead of the rule.

Jeroen

No, that's not true. We're passing a pointer as an argument. It is a valid pointer - dereferencing it may not be valid, but the pointer is perfectly legal! There is nothing wrong with this case. The problem lies in calling a function whose name is special to GCC and to the C language, which GCC can then transform.

Daniel Jacobowitz                           Carnegie Mellon University
MontaVista Software                         Debian GNU/Linux Developer

Hi!

gcc is allowed not to pass it anywhere. You may not second guess optimizer. If it is not defined, it is not defined.

Imagine

strcpy(a, "xyzzy"+b);
if (b>16)

	printf("foo");

. gcc is permitted to kill printf(), because if b<0 or b>16 behaviour is undefined. So gcc may assume b<=16.

Quoting alan:

################################################################################
# What part of 'undefined behaviour' is so difficult for people to understand? #
################################################################################

Pavel

(about SSSCA) "I don't say this lightly.  However, I really think that the U.S.
no longer is classifiable as a democracy, but rather as a plutocracy." --hpa

So... I'm curious. How is the result of virt_to_phys ever anything other than undefined?

Paul.

Ignore strcpy. Yes, that's what visibly causing a failure here, but the bug is in the funny pointer arithmetic. Leave that in there and the compiler _will_ bite your ass sooner or later.

r~

I look forward to seeing your patch to remove all uses of virt_to_phys, phys_to_virt, __pa, __va, etc. from arch/alpha... :)

Paul.

Isn't this why we use unsigned long' to represent physical addresses, and void *' to represent kernel virtual addresses? Not only helps it against a user dereferencing a physical address `pointer', but also against gcc trying to be (too) smart.

Of course this also implies we have to change the pointer argument in readb() and friends, since it's not a real pointer but a magic cookie. But we already had that discussion last year...

[ and the conclusion was: keep the pointer, so we can do readl(&base->field) ]

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

Thank you for taking it all and putting it in a nutshell.

Jeroen

Which it may do with another function *or expression* as well, because the real bug has already happened before the function call comes into the issue.

As far as I'm concerned the options are: fix RELOC; obviate RELOC; use an appropriate gcc option if available (-fPIC might be it, -ffreestanding certainly isn't--see above); *extend* (not fix, extend) gcc; or work around all individual cases. In rough descending order of preference.

Jeroen

Er, which part of the 'funny pointer arithmetic' ? I take it you aren't a fan of the 'change to memcpy(namep,RELOC("linux,phandle"),sizeof("linux,phandle"));' fix. We need to do funny things here, and thus need a way to tell gcc to just do what we're saying.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

What's the bug? The 'funny' arithmetic?

How?

Maybe for 2.5. Too invasive for 2.4.x (initially at least).

Er, say what?

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

That depends on your definition of bug--symptom, "sighting" (thank you Intel), or underlying problem. The funny arithmetic, in C terms, is the underlying problem. The symptom is obvious. The sighting involves calls to what appear to be calls to the standard library, but in this case happen not to be. We'd still have the same problem if this really were the standard C library.

That's the EUR 64 * 10^6 question, isn't it? It's likely to cost some performance, but I suspect this would be the easiest solution.

I'm not saying these are attractive or even feasible, just prioritizing the options I see. I'm sure I'll have forgotten some, but I'm convinced -ffreestanding isn't among them.

Let's say RELOC also broke in other places, for the exact same reason but without (names familiar from) the standard library come into play. How would one recognize those cases? And once diagnosed, how to go about working around them? Even worse, what if gcc tries to help but still uses the stricter assumptions in some forgotten case?

Those would take time, and I can't see why none of these would arise at some point. That's why I feel -ffreestanding is too brittle as a workaround.

In rough descending order of _my_ preference, that is--falls within the scope of the "as far as I'm concerned." :)

But yes, requiring gcc to support RELOC through anything else than an existing option (and once again, -ffreestanding only works around one instance where it breaks) would be an extension to gcc. If it didn't break in the past, that was essentially a coincidence. Unless it's in some forgotten corner of the docs: possible, but not probable AFAICS.

Optimizing C is hard to do. Pointer arithmetic is hell on an optimizer, and the rules were made to give the latter a fair chance of doing a good job. I'm not arguing against having some specific option to relax those rules--kernels need to be written, and written in C. But that option is by definition a compiler-specific extension to the language.

Jeroen

What's currently inside RELOC.

While it's true that you have requirements on doing runtime relocation, what you absolutely do not want to do is expose this to gcc.

Hide it inside inline assembly if you must. Better is to do your relocation before you enter C at all.

r~

I'm partial to Paul's' suggestion of redoing RELOC and friends in asm.

Well, Franz Sirl mentioned this before as a possible (or rather, why aren't we doing it like this?), so maybe later someone will look into this.

Well, RELOC _always_ is doing funny arithmetic, and there's not much we can do about it. At this point in the bootup we aren't running where things think we are yet, and have to adjust things as such.

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

On Wed, Jan 02, 2002 at 12:09:10PM -0700, Tom Rini <[email protected]> wrote:

| On Wed, Jan 02, 2002 at 01:03:25AM +0200, Momchil Velikov wrote:
| > The GCC tries to replace the strcpy from a constant string source with
| > a memcpy, since the length is know at compile time.
| 
| Okay, here's a summary of all of the options we have:
| 1) Change this particular strcpy to a memcpy
| 2) Add -ffreestanding to the CFLAGS of arch/ppc/kernel/prom.o (If this
| optimization comes back on with this flag later on, it would be a
| compiler bug, yes?)
| 3) Modify the RELOC() marco in such a way that GCC won't attempt to
| optimize anything which touches it [1]. (Franz, again by Jakub)
| 4) Introduce a function to do the calculations [2]. (Corey Minyard)
| 5) 'Properly' set things up so that we don't need the RELOC() macros
| (-mrelocatable or so?), and forget this mess altogether.

Dudes, maybe I'm missing something here, but why don't you just mark the source data as volatile? Then it _can't_ assume it knows the length of the strcpy because it can't assume it knows the content:

If PTRRELOC cast the pointer type to

volatile void *

or something else suitable generic but volatile then this discussion might not be happening. It would at least move the optimisation into "definite compiler bug" if it still happens.

Cameron Simpson, DoD#743        [email protected]    http://www.zip.com.au/~cs/

I think... Therefore I ride.  I ride... Therefore I am.
	- Mark Pope <[email protected]>

That's what 3 does.

See the rest of the thread for why various people don't like that this doesn't work 'as-is' anymore, and why other people don't like what it's doing period (in C anyhow).

Tom Rini (TR1265)
http://gate.crashing.org/~trini/

I don't dereference them either, do I?

r~

Does that matter? To quote your earlier message:

I don't have a copy of the C standard handy, but that sounds to me like the result of (unsigned long)(&x) - KERNELBASE is undefined.

Also, what does the standard say about casting pointers to integral types? IIRC you aren't entitled to assume that a pointer will fit in any integral type, or anything about the bit patterns that you get.

My point is that the kernel makes some assumptions about how pointers are represented, which are eminently reasonable assumptions, but which "portable" C programs are not entitled to make according to the C standard.

Paul.

So am I--with the portable fallback of turning RELOC into an extern function. As an added benefit, that would probably eliminate a lot of individual offset variables and hide the ugliness in a single place.

Just so it's documented, here's why I think the changes I coined earlier won't work:

(1) Turn offset into an extern variable.

This doesn't work in cases like "strlen("string" + offset)", which the compiler may translate to the equivalent of "strlen("string") - offset", ie. "6 - offset" which of course still breaks.

(2) Cast to const volatile void *.

This *might* work, because gcc ought to suppress some optimizations upon finding the 'volatile,' but the volatile would have to be cast out again to make functions accept it as a nonvolatile parameter. And if it's cast out, gcc might decide to ignore it as well--or even perform its regular constant propagation regardless. Not casting the volatile away again OTOH might make the code a lot slower.

(3) Use -fPIC.

This isn't supported by all architectures, and requires special linker support which may not be available yet at the time it's needed.

IIRC SAS/C used to have an option to allocate strings in the same section of the object file as the code, and use PC-relative addressing to get at them. Anyone know if gcc has anything like that? That should also fix the problem by deferring computation of the string's address to computation time. Frankly though I don't even know if all architectures have PC-relative addressing...

The arithmetic can't be helped--agreed. We just have to break some assumptions that gcc is allowed to make based on the information it has and the C memory model.

Let's just make sure we break them beyond repair. :-)

Jeroen

Hi!

Is there problem with doing what Jakub suggested?
Pavel

(about SSSCA) "I don't say this lightly.  However, I really think that the U.S.
no longer is classifiable as a democracy, but rather as a plutocracy." --hpa

No, but I think it better to extract all of the relocation up front rather than scattering it about the source code.

r~

But this is not the memory model of C! Adding an offset to a pointer is an operation involving objects defined by the C language, and not machine registers. Sometimes, this makes a noticeable difference.

Sorry, you are correct. I should have written "One of the reasons why C used to be a good language for writing operating system kernels ..."

Paul.

No, it doesn't. C pointers do not behave like machine addresses, there are additional constraints.

This casting falls into the category "additional language constructs supported by GCC". The standard contains wording which encourages implementors to include a meaningfull conversion from a pointer type to an integral type, but there is no requirement that this has the semantics expected by most programmers.

That doesn't fix the undefined behavior.

That doesn't fix the undefined behavior.

That *does* fix the undefined behavior, and it seems that GCC is going to stay the same in the future, so this is a feasible workaround.

That doesn't fix the undefined behavior.

This is the clean approach, and thus preferable in the long term. (3) seems to be the best short-time solution.