arithmetic operations on pointer

[variksla]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:
if (ptr) free(((void**)ptr)[-1]);

 

[James Kuyper]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:
if (ptr) free(((void**)ptr)[-1]);

It might not be. Looking at the web page that you cited, the relevant
code that sets ptr has many serious problems:

void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;

The left operand of the unary & operator is a pointer. That's a
constraint violation: "Each of the operands shall have integer type."
(6.5.10p2). The only requirement on a conforming implementation of C
when processing such code is that it must generate at least one
diagnostic message. After doing so, it is free to generate an
executable; if it does, you are free to run the executable, but the
behavior when it runs is undefined.

If an implementation supports uint_ptr_t (which is optional), then

uintptr_t temp = (uintptr_t)(((char*)mem+sizeof(void*)+15) & 0x0F;

would produce a number satisfying:

temp % 16 == 0
temp/16 == (uintptr_t)((char*)mem+sizeof(void*)+15)/16

Which is probably precisely what that author expected would be the
result of his bitwise-and expression. As a result, that person probably
expected that ptr would 16 byte aligned

ptr >=(char*)mem+sizeof(void*)
ptr <= (char*)mem+sizeof(void*) + 15

On many implementations, all of those expectations will be met. But
there is no justification in the C standard for any of those
expectations (even if you use the uintptr_t approach). All that the C
standard says about the result of that conversion is that "the result is
implementation-defined, might not be correctly aligned, might not point
to an entity of the referenced type, and might be a trap
representation." (6.3.2.3p5)

It would have been perfectly legal to use ptr = (void**)mem + 1, and if
that had been done, then

if (ptr) free(((void**)ptr)[-1]);

would have been perfectly safe. The only problem it that it doesn't
necessarily meet the specification, which requires that ptr be 16-byte
aligned.

The original question, of producing a pointer that is 16-byte aligned,
has no portable solution. malloc() is required to return a pointer
correctly aligned for any type, so on systems where achieving 16-byte
alignment actually matters, a simple call to malloc() is sufficient,
there's no need to do any fiddling with the result. On other systems,
there's no portable way to compute such a pointer, but also no
legitimate need to do so.

In C2011, the _Alignas() alignment specifier was provided, so you could
answer part a) with:

{char _Alignas(16) array[1024];

and answer part b) with:

}

However, there is a constraint on the argument of _Alignas(): "The
constant expression shall be an integer constant expression. It shall
evaluate to a valid fundamental alignment, or to a valid extended
alignment supported by the implementation in the context in which it
appears, or to zero." (6.7.5p3). A fundamental alignment is one that is
less than or equal to _Alignof(max_align_t). (6.2.8p2). On an
implementation where _Alignof(max_align_t) < 16, it's implementation
defined whether 16 is a valid extended alignment; if it's not, the
_Alignas() approach is also a constraint violation.

 

[Phil Carmody]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:
if (ptr) free(((void**)ptr)[-1]);

It might not be. Looking at the web page that you cited, the relevant
code that sets ptr has many serious problems:

void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;

The left operand of the unary & operator is a pointer. That's a
constraint violation: "Each of the operands shall have integer type."
(6.5.10p2). The only requirement on a conforming implementation of C
when processing such code is that it must generate at least one
diagnostic message. After doing so, it is free to generate an
executable; if it does, you are free to run the executable, but the
behavior when it runs is undefined.

If an implementation supports uint_ptr_t (which is optional), then

uintptr_t temp = (uintptr_t)(((char*)mem+sizeof(void*)+15) & 0x0F;

~0x0f

Given that there's aligned_alloc(), isn't this discussion a little
dated?

Phil

 

[James Kuyper]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:
if (ptr) free(((void**)ptr)[-1]);

It might not be. Looking at the web page that you cited, the relevant
code that sets ptr has many serious problems:

void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;

The left operand of the unary & operator is a pointer. That's a
constraint violation: "Each of the operands shall have integer type."
(6.5.10p2). The only requirement on a conforming implementation of C
when processing such code is that it must generate at least one
diagnostic message. After doing so, it is free to generate an
executable; if it does, you are free to run the executable, but the
behavior when it runs is undefined.

If an implementation supports uint_ptr_t (which is optional), then

uintptr_t temp = (uintptr_t)(((char*)mem+sizeof(void*)+15) & 0x0F;

~0x0f

Given that there's aligned_alloc(), isn't this discussion a little
dated?

Not really; aligned_alloc() is new in C2011; there's still relatively
few compilers that fully conform, and even people who have such
compilers often still have to produce code that will work with C99, or
even possibly C90.

Also, the restrictions on the alignment passed to aligned_malloc() are
precisely the same as the restrictions for the _Alignas() approach
mentioned in the part of my message which you clipped, and I find the
_Alignas() approach somewhat simpler.

 

[anish kumar]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of

how to get aligned memory for malloc.

I don't understand how this is valid:

if (ptr) free(((void**)ptr)[-1]);

They appear to be storing the address of the actually allocated block

immediately in front of the "aligned" block returned, and they're

retrieving that address to pass to free.

((void**)ptr)[-1] = *((void**)ptr -1)
(void **)ptr is doing what?
and then we subtract -1 and what is this doing?

 

[James Kuyper]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:

if (ptr) free(((void**)ptr)[-1]);

They appear to be storing the address of the actually allocated block
immediately in front of the "aligned" block returned, and they're
retrieving that address to pass to free.

((void**)ptr)[-1] = *((void**)ptr -1)
(void **)ptr is doing what?

It converts ptr, which is a pointer to void, into a pointer to a pointer
to void.

and then we subtract -1 and what is this doing?

That shifts the location that the pointer is pointing at, backwards by
one position. Since, after the conversion, the pointer points at void*
objects, it moves the position backwards in memory by the size of 1
void* object. As a result, ((void**)ptr)[-1] is an lvalue of type
'void*' referring to that location, in which a void* value can be
stored, from which a void* value can be retrieved.

The original code stored a void* pointer value returned by malloc() in
((void**)ptr)[-1]; it it therefore perfectly acceptable to retrieve the
value stored in that location, and pass it to free().

 

[Edward A. Falk]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me


I don't understand how this is valid:

if (ptr) free(((void**)ptr)[-1]);

In C, "[]" is really another notation for pointer arithmatic.

foo[bar] is the same as *(foo+bar)

(ignoring some semantic differences which don't apply here)

In fact, it can be fun to write this:

3["abcde"]

and let people try to figure out what the hell is going on.

So at any rate, the philosphy of C is to assume the programmer
knows what they're doing and "ptr[-1]" simply means "reference the
memory location one unit *before* whatever ptr points at.


Putting it all together:

What the programmer has done is allocate a buffer big enough to be
aligned to 16 bytes *and* hold a spare copy of the original pointer (mem).
Then, the allocated memory is used as follows:

xxxxxxxxMMMMbbbbbbb...
^ ^
| |
mem ptr

Where xxx is padding, MMMM is a copy of "mem", and bbbb is the buffer
returned to the caller.

When the time comes to free ptr, the code casts it to a pointer to
a void* pointer and then uses [-1] to read one void* prior to
ptr and recover mem.

It could have been written as:

void *mem;
void **ptr2 = (void**)ptr;
ptr2 -= 1;
mem = *ptr2;
free(mem);

 

[Tim Rentsch]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:
if (ptr) free(((void**)ptr)[-1]);

It might not be. Looking at the web page that you cited, the
relevant code that sets ptr has many serious problems:

void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;

The left operand of the unary & operator is a pointer.
[snip continuation]

That's funny, I thought the unary & operator only ever
had right operands.

 

[Edward A. Falk]

It might not be. Looking at the web page that you cited, the
relevant code that sets ptr has many serious problems:

void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;

The left operand of the unary & operator is a pointer.
[snip continuation]

That's funny, I thought the unary & operator only ever
had right operands.

I'm pretty sure he meant binary.

At any rate, he's right. You need to cast both sides to whatever
size int is large enough to hold both a size_t and a pointer.

I suspect there's no truly architecture-independent way to solve
this problem and if I were being asked this question in an interview,
I would state that up front before I tried to solve it.

 

[Tim Rentsch]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:
if (ptr) free(((void**)ptr)[-1]);

It might not be. Looking at the web page that you cited, the relevant
code that sets ptr has many serious problems:

void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;

The left operand of the unary & operator is a pointer. That's a
constraint violation: "Each of the operands shall have integer type."
(6.5.10p2). The only requirement on a conforming implementation of C
when processing such code is that it must generate at least one
diagnostic message. After doing so, it is free to generate an
executable; if it does, you are free to run the executable, but the
behavior when it runs is undefined.

If an implementation supports uint_ptr_t (which is optional), then

uintptr_t temp = (uintptr_t)(((char*)mem+sizeof(void*)+15) & 0x0F;

~0x0f

Given that there's aligned_alloc(), isn't this discussion a little
dated?

Not at all. We might want to allocate some memory with an
alignment greater than _Alignof (max_align_t), or for the size of
the allocation not to be a multiple of the alignment. Calls to
aligned_alloc() are undefined behavior if the alignment argument
is not a valid alignment for the implementation, or if the size
argument is not a multiple of the alignment argument.

 

[Tim Rentsch]

It might not be. Looking at the web page that you cited, the
relevant code that sets ptr has many serious problems:

void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;

The left operand of the unary & operator is a pointer.
[snip continuation]

That's funny, I thought the unary & operator only ever
had right operands.

I'm pretty sure he meant binary.

Obviously he meant something other than what he wrote, that's
why I put in the smiley.

At any rate, he's right. You need to cast both sides to whatever
size int is large enough to hold both a size_t and a pointer.

I believe your analysis is off. There is no reason size_t has to
enter into consideration. The only plausible choice for the
pointer operand is uintptr_t (or the moral equivalent in C90,
etc), which will be wide enough to represent the result so the
right hand side cast could be to that type. If we take the two
operands of the & operand as given the way they are written (not
counting a cast of each operand), casting won't work if uintptr_t
has greater width than size_t. (And a cast back to (void *) is
needed to turn whatever integer type is used back to a pointer.)

A better way to do this, under basically the same assumptions, is
to express the calculation in pointer space rather than integer
space:

size_t extra = sizeof (void*) + 15;
char *mem = malloc( extra + size );
void *ptr = mem + extra - ((uintptr_t)(mem + extra) & 15);

I suspect there's no truly architecture-independent way to solve
this problem

Most certainly there is not. Given the context, however, it
seems pretty likely they are looking for something that would
work on a garden variety architecture; probably worth checking,
but unlikely to give more than a moment's pause in producing an
answer.

and if I were being asked thisb question in an interview, I would
state that up front before I tried to solve it.

For a more interesting challenge, consider writing an aligned
allocation routine (architecture specific is okay) whose result
can be freed just by calling free() on the returned value. It
should accept power-of-two alignment values, not just a single
fixed one.

 

[James Kuyper]

It might not be. Looking at the web page that you cited, the
relevant code that sets ptr has many serious problems:

void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;

The left operand of the unary & operator is a pointer.
[snip continuation]

That's funny, I thought the unary & operator only ever
had right operands.

I'm pretty sure he meant binary.

I sure did. Aargh!

 

[Rosario1903]

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:
if (ptr) free(((void**)ptr)[-1]);

if mem is a return address from malloc, the way of free it is
free(mem);

and for me "free(((void**) ptr)[-1] )" with ptr defined below, could
be right only in one machine cpu compiler os malloc function, and for
me is wrong there too

if for example mem=0x12378 => ptr=0x12380
so whay ((void**)ptr)[-1]==0x12378 ??????

if i see right, the above line suppose
linear address unsigned returned from malloc to "mem" variable;
& would be one "and operator" for unsigned and "pointers" [out the
standard C] [and pointer to char see as unsigned]

than "ptr" point to one address as 0xFFFFFF0 0x89a9b90 0xc8393930
all with the "0" in the end
so this code would find memory 16 aligned
there would be code for find the new memory size for "ptr"...

The left operand of the unary & operator is a pointer.
[snip continuation]

That's funny, I thought the unary & operator only ever
had right operands.

 

[Keith Thompson]

I don't think uintptr_t is needed.

You are assuming that the alignment of a pointer p can be deduced from
the lowest bits of (uintptr_t) p. I would assume that it can just as
well be deduced from the lowest bits of (unsigned char) p, for example
(for alignment up to 256 bytes).

That requires an additional assumption: that converting a pointer to
a narrow integer type copies the "low-order" bits of the pointer.
It's likely to be correct, but why make extra assumptions when you
don't really have to?

On the other hand, using uintptr_t assumes that uintptr_t actually
exists.

 

[Eric Sosman]

I don't think uintptr_t is needed.

You are assuming that the alignment of a pointer p can be deduced from the lowest bits of (uintptr_t) p. I would assume that it can just as well be deduced from the lowest bits of (unsigned char) p, for example (for alignment up to 256 bytes).

Probably, but "just as well" still means "not for sure." Here's
a cautionary footnote from Bentley & McIlroy's classic "Engineering a
Sort Function:"

The strange formula to check data size and alignment
works even on Cray computers, where plausible code such as
((long)a | es) % sizeof(long) fails because the least
significant part of a byte address occupies the most
significant part of a long.

The paper is from 1993 and hence predates the introduction of
uintptr_t, but substituting uintptr_t (or char) for long in the
"plausible code" wouldn't help -- unless Cray's conversion of a
pointer to uintptr_t acted differently from conversion to other
integer types, in which case "just as well" means "less well."

As to the question posed to the O.P., I do not believe there
is a fully-portable solution. Every C implementation has some
way to solve the problem, but no single solution is guaranteed to
work for all C implementations.

 

[Keith Thompson]

Probably, but "just as well" still means "not for sure." Here's
a cautionary footnote from Bentley & McIlroy's classic "Engineering a
Sort Function:"

The strange formula to check data size and alignment
works even on Cray computers, where plausible code such as
((long)a | es) % sizeof(long) fails because the least
significant part of a byte address occupies the most
significant part of a long.

The paper is from 1993 and hence predates the introduction of
uintptr_t, but substituting uintptr_t (or char) for long in the
"plausible code" wouldn't help -- unless Cray's conversion of a
pointer to uintptr_t acted differently from conversion to other
integer types, in which case "just as well" means "less well."

Cray's pointer-to-integer conversion just copied the bits, including
the byte offset in the high-order 3 bits of the 64-bit word.

I'm not sure what converting a pointer to unsigned char would do;
it would probably copy the low-order 8 bits, but I never tried it.
All integer types other than the 3 character types were the same
size as a pointer. (Yes, short was 64 bits.)

 

[anish kumar]

On Mon, 25 Nov 2013 00:43:52 -0800 (PST), (e-mail address removed) wrote:

http://stackoverflow.com/questions/...nment-in-c-interview-question-that-stumped-me

In this link there is explanation of
how to get aligned memory for malloc.

I don't understand how this is valid:

if (ptr) free(((void**)ptr)[-1]);

They appear to be storing the address of the actually allocated block
immediately in front of the "aligned" block returned, and they're
retrieving that address to pass to free.

((void**)ptr)[-1] = *((void**)ptr -1)

(void **)ptr is doing what?

It converts ptr, which is a pointer to void, into a pointer to a pointer

to void.

and then we subtract -1 and what is this doing?

That shifts the location that the pointer is pointing at, backwards by

one position. Since, after the conversion, the pointer points at void*

objects, it moves the position backwards in memory by the size of 1

void* object. As a result, ((void**)ptr)[-1] is an lvalue of type

'void*' referring to that location, in which a void* value can be

stored, from which a void* value can be retrieved.

So it can be written this way as well right?
*((void **)(ptr -1)) this can hold a pointer right

The original code stored a void* pointer value returned by malloc() in

((void**)ptr)[-1]; it it therefore perfectly acceptable to retrieve the

value stored in that location, and pass it to free().

 

[James Kuyper]

void* object. As a result, ((void**)ptr)[-1] is an lvalue of type
'void*' referring to that location, in which a void* value can be
stored, from which a void* value can be retrieved.

So it can be written this way as well right?
*((void **)(ptr -1)) this can hold a pointer right

Yes. The expression a is defined as equivalent to *(a+b).

 

[anish kumar]

It would need to be:



*(((void **) ptr) -1)



You need to convert the type of the pointer to void** before doing the

address arithmatic on it.

but ptr is a pointer to void so if i subtract -1 from it
and then cast it to void ** and do a derefrence as below
then how it is different:
*((void **)(ptr -1))

 

[Barry Schwarz]

but ptr is a pointer to void so if i subtract -1 from it
and then cast it to void ** and do a derefrence as below
then how it is different:
*((void **)(ptr -1))

You cannot perform arithmetic on a pointer to void.

Consider an int* p. The expression p-1 evaluates to the address of
the int just before the int currently pointed to. Conceptually, p-1
point to the int one to the left of the current int. It evaluates to
sizeof(int) bytes before the current value of p.

Note that void is an incomplete type. There is no concept of a void
to the left of the current void. And sizeof(void) is invalid.