pointer one past malloc.ed memory

[Sushil]

Hi Gurus

I've tried to come up with a small logical example of my problem.
The problem is platform specific (MIPS) which I understand should not
be discussed here.

So here goes my example:

Code is doing malloc of variable sizes.
The last byte of malloc.ed memory is written a magic.
Since the size if variable (and iit ncludes magic), the code adds size
and subtracts sizeof magic to access the magic.
Now this is where the problem comes.
The calculation of address generates an overflow exception.

Let me give an example (it's a corner case I ran into)
0x8000 0000 is end of the malloc.ed memory and magic is 8 bytes
so it is a lw $v0, -8($v0)

0x8000 0000 + -8 is generating an overflow exception for address.
The address 0x7fff fff8, is perfectly valid to dereference but
*computation* of the address is overflowing.

Sorry i had to give some platform specific details.
But I am hoping it will clarify my question.

Now my question to you about C language is:
Can we have the address 1 byte beyond the malloc.ed area (no it is not
dereferenced) and then a negative offset into it to legitimately
dereference the memory malloc.ed by malloc()?
What does the standard say here?
Or is it just another case of overflow and we can not blame MIPS
load-store unit for overflown address generation (thats what I think).

I've solved the problem by first subtracting 8 then adding size . i.e.
instead of load from -8(ptr) I forced the code to do ptr to point to 8
bytes earlier and then load from 0(ptr). But I want to know what the
standard says about the address of malloc.ed memory.

Thanks
- Ramachandran

 

[pete]

Can we have the address 1 byte beyond the malloc.ed area (no it is not
dereferenced) and then a negative offset into it to legitimately
dereference the memory malloc.ed by malloc()?

Yes.

 

[Joe Wright]

Hi Gurus

I've tried to come up with a small logical example of my problem.
The problem is platform specific (MIPS) which I understand should not
be discussed here.

So here goes my example:

Code is doing malloc of variable sizes.
The last byte of malloc.ed memory is written a magic.
Since the size if variable (and iit ncludes magic), the code adds size
and subtracts sizeof magic to access the magic.
Now this is where the problem comes.
The calculation of address generates an overflow exception.

Let me give an example (it's a corner case I ran into)
0x8000 0000 is end of the malloc.ed memory and magic is 8 bytes
so it is a lw $v0, -8($v0)

0x8000 0000 + -8 is generating an overflow exception for address.
The address 0x7fff fff8, is perfectly valid to dereference but
*computation* of the address is overflowing.

Sorry i had to give some platform specific details.
But I am hoping it will clarify my question.

Now my question to you about C language is:
Can we have the address 1 byte beyond the malloc.ed area (no it is not
dereferenced) and then a negative offset into it to legitimately
dereference the memory malloc.ed by malloc()?
What does the standard say here?
Or is it just another case of overflow and we can not blame MIPS
load-store unit for overflown address generation (thats what I think).

I've solved the problem by first subtracting 8 then adding size . i.e.
instead of load from -8(ptr) I forced the code to do ptr to point to 8
bytes earlier and then load from 0(ptr). But I want to know what the
standard says about the address of malloc.ed memory.

Thanks
- Ramachandran

We generally don't know MIPS assembler and as a C programmer, you
shouldn't care. If you care to post some C code which exhibits the
problem, several people here might be more able to help you.

Note that 0x80000000 is -2147483648 or INT_MIN on 32-bit systems.

 

[Sushil]

We generally don't know MIPS assembler and as a C programmer, you

shouldn't care. If you care to post some C code which exhibits the
problem, several people here might be more able to help you.

Note that 0x80000000 is -2147483648 or INT_MIN on 32-bit systems.

Thanks for your reply Joe and Pete.

The simplified code is like this
magic_struct *magic_ptr = ((magic_struct *) ((uchar *) ptr +
ptr->size))- 1;
where magic_struct contains two magic ulongs.

The issue is ptr + ptr->size becomes 0x80000000 and -1 after pointer
arithmetic is 8 bytes since sizeof(magic_struct) is 8. However, the
compiler does not do the -8 part since it is compiled with -O3 (okay I
know this is offtopic). Instead, when magic_ptr->magic1 is referenced
(later) compiler offsets -8 from the above address at that point. This
is overflowing and causing an address exception.

The way I fixed it is I rearranged code
magic_struct *magicptr = ((uchar *) ptr - sizeof(magic_struct)) +
ptr->size;

Question 1:
Do you think this trick(the parentheses) will force it to calculate
entire thing (it is working right now - but I am not confident it
always will). I want to make sure that the compiler calculates
magic_ptr fully and offsets 0 from it instead of optimising and
offseting -8. The code is in fast path and I dont wish to turn off
optimisation. I guess the standard does not specify any of this.
But if you've some wisdom from experience, please enlighten me.

Question 2:
What does the language say about the address calculation.
What is the signedness of address when it comes to address arithemtic.
For example pointer to a struct. Is it signed or unsigned.

I'm not a clc language lawyer and I am learning C so please bear
with me.
Thanks for your understanding and tolerance and sharing your C
knowledge.

You guys are very helpful,
With regards
- Sushil Ramachandran

 

[pete]

Thanks for your reply Joe and Pete.

The simplified code is like this
magic_struct *magic_ptr = ((magic_struct *) ((uchar *) ptr +
ptr->size))- 1;
where magic_struct contains two magic ulongs.

The issue is ptr + ptr->size becomes 0x80000000 and -1 after pointer
arithmetic is 8 bytes since sizeof(magic_struct) is 8. However, the
compiler does not do the -8 part since it is compiled with -O3 (okay I
know this is offtopic). Instead, when magic_ptr->magic1 is referenced
(later) compiler offsets -8 from the above address at that point. This
is overflowing and causing an address exception.

The way I fixed it is I rearranged code
magic_struct *magicptr = ((uchar *) ptr - sizeof(magic_struct)) +
ptr->size;

If ptr is the lowest byte of the object,
then it is not safe to subtract from it.
It is safe to calculate the integer part first
and then add it the pointer.

magic_struct *magicptr
= ptr->size - sizeof(magic_struct) + (uchar *)ptr;

Question 1:
Do you think this trick(the parentheses) will force it to calculate
entire thing (it is working right now - but I am not confident it
always will).

No.

Question 2:
What does the language say about the address calculation.

There is a rule which explicitly allows the calculation
of an address one byte beyond an object, as long as it
is not dereferenced. There is no such rule for addresses
lower than an object lowest addressable byte.

What is the signedness of address when it comes to address arithemtic.
For example pointer to a struct. Is it signed or unsigned.

No. Pointers are scalar but not integer types.
The difference between two pointers,
is a signed integer type called ptrdiff_t, defined in stddef.h

 

[Richard Bos]

Thanks for your reply Joe and Pete.

The simplified code is like this
magic_struct *magic_ptr = ((magic_struct *) ((uchar *) ptr +
ptr->size))- 1;
where magic_struct contains two magic ulongs.

I presume uchar is just a typedef for unsigned char? If not, that's your
bug right there.

The issue is ptr + ptr->size becomes 0x80000000 and -1 after pointer
arithmetic is 8 bytes since sizeof(magic_struct) is 8. However, the
compiler does not do the -8 part since it is compiled with -O3 (okay I
know this is offtopic). Instead, when magic_ptr->magic1 is referenced
(later) compiler offsets -8 from the above address at that point. This
is overflowing and causing an address exception.

Hohum... I don't think that's conforming. If there really is a block of
memory of ptr->size bytes at ptr, then (char *)ptr + ptr->size _must_ be
a valid pointer, albeit a non-dereferencable one. Since what you're
doing with it does _not_ involve dereferencing, you should be all right.

Perhaps you should post the definition of a magic_struct, and the
declaration and initialisation of ptr. It may be that not all is what it
seems.

The way I fixed it is I rearranged code
magic_struct *magicptr = ((uchar *) ptr - sizeof(magic_struct)) +
ptr->size;

This, however, is not correct. You create an intermediate pointer,
(uchar *)ptr - sizeof (magic_struct), which is before the start of the
block - at least, if ptr points at the start of it, which seems to be
the case.

This is how I would do it:

magic_struct *magicptr=(uchar *)ptr + (ptr->size - sizeof *magicptr);

This calculates the size of the offset first, and then adds it to the
pointer, guaranteeing that, as long as the result lies within the memory
belonging to ptr and ptr->size fits in a size_t, no intermediate result
can overflow.

Question 1:
Do you think this trick(the parentheses) will force it to calculate
entire thing (it is working right now - but I am not confident it
always will). I want to make sure that the compiler calculates
magic_ptr fully and offsets 0 from it instead of optimising and
offseting -8.

_Nothing_ in ISO C can stop your compiler from optimising, just as
nothing can force it to optimise. Efficiency falls beyond the scope of
the Standard. Basically, as long as your implementation does _what_ it
is required to do, ISO C doesn't care _how_ it does it, and even less
how efficiently.

Question 2:
What does the language say about the address calculation.
What is the signedness of address when it comes to address arithemtic.
For example pointer to a struct. Is it signed or unsigned.

That cannot be answered. You can only:
- add or subtract an integer to (from) an object pointer;
- subtract two pointers to the same object.
Both of these are well-defined; neither of them involves a "sign" of the
pointer. Moreover, for both of these, it does not matter what kind of
object the pointer(s) point(s) at; adding an integer to a struct pointer
works exactly the same way as adding an integer to a char pointer,
except for the size of the objects.

Richard

 

[Eric Sosman]

Note that 0x80000000 is -2147483648 or INT_MIN on 32-bit systems.

0x80000000 is the *positive* value 2147483648.
If this value exceeds INT_MAX (as it will with 32-bit
integers), the constant does not have `int' type but
either `unsigned int' (if UINT_MAX is big enough)
or `long' (if LONG_MAX is big enough) or `unsigned long'
(ULONG_MAX is guaranteed to be big enough).

 

[Chris Torek]

Summary, including machine-specific info that may or may not be
relevant:

a) The hardware traps integer overflow, including address arithmetic
overflow. (C unsigned types use non-trapping instructions, and
in fact, C signed types generally use these as well, but the
pointer-offset address format apparently uses the trapping form
of arithmetic.)

b) The C code in question is somehow obtaining a pointer value that
lies near the end of 32-bit-integer space, 0x7ffffff8 for
instance.

c) The compiler generates non-trapping code when not optimizing, but
trapping code when optimising.

[Someone wrote:]

Thanks for your reply Joe and Pete.

The simplified code is like this
magic_struct *magic_ptr = ((magic_struct *) ((uchar *) ptr + ptr->size))- 1;
where magic_struct contains two magic ulongs.

The issue is ptr + ptr->size becomes 0x80000000 and -1 after pointer
arithmetic is 8 bytes since sizeof(magic_struct) is 8. However, the
compiler does not do the -8 part since it is compiled with -O3 (okay I
know this is offtopic).

Actually, it may not be off-topic (although it is not "on" topic
either -- it might just be irrelevant, as far as conformance goes).

Instead, when magic_ptr->magic1 is referenced (later) compiler offsets
-8 from the above address at that point. This is overflowing and
causing an address exception.

Specifically, the compiler transforms:

struct S *p;
...
p = (expr) - 1; /* where (expr) has type "struct S *" and
points "just past the end" of an array of "struct S" */
use(p->foo);

into:

p = expr;
use(p[-1].foo);

when asked to optimize (via -O3). When not optimizing, the compiler
actually computes "p = expr - 1" as originally directed, then uses
p[0].foo to access p->foo, generating address offsets of the form
0(reg) instead of -8(reg). When optimizing, the compiler uses the
second form. As it happens, "reg" holds 0x7ffffff8 when offset by
0 (not optimizing) or 0x80000000 when offset by -8 (optimizing).
The former works, and the latter does not.

The expression I have denoted "expr" here has the general form of
"one past the last byte in an object". The C standard explicitly
allows such computations, and you may even use the second form
yourself in your C code. The system is obliged, as if by contract,
to make this work (in Standard C).

If the value in "expr" is obtained by ordinary (and conforming) C
code (see example below), the compiler optimization occurring here
causes the overall system to fail to conform. I suggest that the
bug here is either that the system is handing out "the last address"
-- it should make sure that the expression "expr" never goes "above"
0x7fffffff, i.e., it should never put an object beyond address
0x7ffffffe, and even further back from the edge for objects larger
than 1 byte -- or else the compiler must not perform the optimization
it is doing.

On the other hand, if the value in "ptr" is obtained by something
not part of Standard C, the system as a whole can still conform.
That is, the Standard C part of the system might in fact hand out
address 0x7ffffffe as a valid one-byte object, but be careful to
make sure that all valid forms of address arithmetic -- including
the "one byte past the end" cases -- never exceed 0x7fffffff. In
this case, no matter how big p is, p+1 will be 0x7fffffff at most,
and negative offsets from a register holding p will work.

Assuming the Standard C part of the system conforms (by not handing
out "address smack dab at end of address space"), whether handing
out such an address is a bug in the non-"Standard C" part of the
system is up to the non-"Standard C" part. That is, the Standard
cannot tell you whether this is right or wrong -- only the system's
own documentation about its own special non-standard extensions
and behaviors can say so.

The way I fixed it is I rearranged code
magic_struct *magicptr = ((uchar *) ptr - sizeof(magic_struct)) +
ptr->size;

Question 1:
Do you think this trick(the parentheses) will force it to [work] ...

Not in general, no. (Tricks involving variables marked "volatile"
will, though.)

Question 2:
What does the language say about the address calculation.

Virtually nothing. The language *does* say that it is legal to
compute an address "one beyond the end" of any object, so if:

char *p;
size_t size;
struct S *q;
...
size = N * sizeof *q; /* where N > 0 */
p = malloc(size);
if (p == NULL) ... handle error ...
p += size;
q = p;
q[-1].field = val;

fails at runtime, the compiler fails to conform. *How* the C system
makes this work -- whether that involves any signedness of addresses,
for instance -- is not specified. On the other hand, as soon as you
write something like:

p = (char *)0x7ffffff8;

you have left the Standard behind in the dust, and can no longer
ask anything from it. You are now at the mercy of your particular
system. If:

p += 8;
q = p;
q[-1].field = val;

subsequently fails, the Standard cannot help. This is true EVEN
IF THIS OCCURS ELSEWHERE IN THE CODE, using a different value in
p! A single occurrence of "undefined behavior" anywhere officially
terminates your "contract" with the C Standard. In practice, of
course, if the original undefined behavior is harmless on your
system, it probably has no effect on "disconnected" code -- which
is handy when debugging -- but strange things can happen. (For
instance, suppose the first bit of "undefined behavior" you invoke
is something like:

_implementation_hook("set time bomb to go off in 5 minutes");

If and when the time bomb does go off, it can affect everything.)

 

[Sushil]

Summary, including machine-specific info that may or may not be
relevant:

I want to thank you Chris (and others).
That was a very detailed explanation.

clc rocks.
-Sushil Ramachandran

 

[Sushil]

If ptr is the lowest byte of the object,
then it is not safe to subtract from it.
It is safe to calculate the integer part first
and then add it the pointer.

magic_struct *magicptr
= ptr->size - sizeof(magic_struct) + (uchar *)ptr;


No.

Turns out that in some other release of the above "fix", it indeed did
not work. The trick failed. So now I want to know why you said that it
wont work.

originally
a = x + y - z;

my "fix" to avoid overflow
a = x + (y-z);

1. Either there is flaw in my "fix" and in my assumption that x + (y -
z) will avoid possible overflow in x + y - z or the compiler has a
bug.

Does not (y-z) cause a precedence?
If the compiler optimises x + (y - z) and yet generates code
equivalent to x + y - z then can I say that the compiler is broken? Or
is it not fair to ask compiler folks to make their optimisation ouput
ISO C conforming?

If you think it is broken, can someone point me to the relevant text
in standard that will explain this (so that I can point the compiler
folks to it)?

2. I even did this
temp = y -z;
a = x + temp;
It did not work (but I am not surprised at that) since it's a simple
optimisation for the compiler.

So in essense
expression1;
expression2;

Is not the compiler supposed to finish expression1 and then generate
code for expression2? Is not that a 'sequence point'?

I'm asked to turn off the optimisation (which I can not do :-( but it
does generate the correct code) but then, in real life, there has to
be a balance between no optimisation and optimisation with *correct*
code.

<OT>
I suspect that it is because the function which has this code is a
static inline and so there is code above and below it, and so by the
time the optimiser kicks in, it may "lose" the parenthesis. Turning
off gcse flag (global common subexpression elimination pass) worked.
Removing the inline worked too - perhaps because the compiler had
lesser chance to optimise and move things around since it's a small
function.
</OT>

3.Finally how can I enforce (y-z) evaluation in
a = x + (y - z);

Seeking enlightment
-Sushil

 

[pete]

Turns out that in some other release of the above "fix", it indeed did
not work. The trick failed. So now I want to know why you said that it
wont work.

originally
a = x + y - z;

my "fix" to avoid overflow
a = x + (y-z);

1. Either there is flaw in my "fix" and in my assumption that x + (y -
z) will avoid possible overflow in x + y - z or the compiler has a
bug.

Does not (y-z) cause a precedence?

Addition and subtraction between pointers and integers,
is more complicated than addition and subtraction
between just integers.

(y-z) is an undefined expression, if y is the address of an object,
which is not part of an aggregate object, and z is positive.

(x+y) has potential overflow, as you stated.

(x-z) is a positive number which won't cause overflow.
It had better be, or your assignment has no chance.

You want y+(x-z), more simpley expressed as: x-z+y

(big_size - small_size + pointer)

 

[Chris Torek]

Turns out that in some other release of the above "fix", it indeed did
not work. ...

3.Finally how can I enforce (y-z) evaluation in
a = x + (y - z);

This is not the real problem (at least, not as you described it
originally). I already hinted how to do it. Suppose your structure
type is S:

struct S *p = expr1 - expr2;
... p->field ...

The compiler is optimizing this into:

struct S *p = expr1;
... p[-expr2].field ...

Normally this would be OK, but you are going outside the C standard
(I suspect), so that "expr1" is not a valid C pointer nor the address
"one byte beyond the end" of a valid C object.

The solution at which I hinted is to pass the result of the
subtraction through a volatile-qualified variable:

struct S *p;
volatile struct S *tmp;

tmp = expr1 - expr2;
p = (struct S *)tmp;

The removal of the "volatile" qualifier requires a cast (unfortunately)
but the act of passing the value through "tmp" will force the subtraction
to occur earlier, despite any other optimization.

This does depend on a lot of slightly-shaky assumptions about your
compiler(s), but I predict it will work on your system.