Defined and undefined C pointer manipulation

[James Harris]

I understand that a C pointer can have some basic arithmetic operations
applied to it such as having an integer added or subtracted to step a whole
number of the referred-to data type, or two pointers to the same data type
being subtracted. However....

To write a couple of memory management routines to implement malloc and free
it would be handy to take one bit from a pointer to use as an indicator of
whether a piece of memory is in use or is unused. Because each piece of
memory will be aligned any valid pointer will have its lower bit(s) clear so
it makes sense to take the lowest bit of a pointer and use it to indicate
whether a region is used or unused. That would lead to expressions like
these:

ptr |= 1;
ptr &= ~1;
if (ptr & 1) ...

My question is whether C's behaviour is defined or undefined for such
pointer manipulations. Would the pointers need to be cast to char pointers
for this to work? Any other issues I should be aware of?

I'm pretty sure that any implementation of C that I am likely to use will
allow the kinds of pointer masking that I have in mind but are there better,
more C-like ways to go about this? Are there implementations on which it
might not work? And would it be acceptable to manipulate the pointers as
pointers to char even though malloc and free are defined to work with
pointers to void?

James

 

[Stefan Ram]

ptr |= 1;

»Each of the operands shall have integer type.«

6.5.12 Bitwise inclusive OR operator, N1570

I'm pretty sure that any implementation of C that I am likely to use will
allow the kinds of pointer masking that I have in mind but are there better,
more C-like ways to go about this?

The C-like way is not to implement malloc, but to use malloc.

 

[Keith Thompson]

I understand that a C pointer can have some basic arithmetic operations
applied to it such as having an integer added or subtracted to step a whole
number of the referred-to data type, or two pointers to the same data type
being subtracted. However....

To write a couple of memory management routines to implement malloc and free
it would be handy to take one bit from a pointer to use as an indicator of
whether a piece of memory is in use or is unused. Because each piece of
memory will be aligned any valid pointer will have its lower bit(s) clear so
it makes sense to take the lowest bit of a pointer and use it to indicate
whether a region is used or unused. That would lead to expressions like
these:

ptr |= 1;
ptr &= ~1;
if (ptr & 1) ...

To use bitwise operations on pointers, you'd have to convert
to uintptr_t and back again. (That's assuming uintptr_t exists,
which it won't if no integer type is big enough to hold a converted
pointer value without loss of information. That's a reasonably
safe assumption, and if it's violated on some exotic system your
code will fail to compile.)

My question is whether C's behaviour is defined or undefined for such
pointer manipulations. Would the pointers need to be cast to char pointers
for this to work? Any other issues I should be aware of?

The behavior is undefined, and I've worked on systems where it would
fail.

On Cray vector machines (T90, SV1), a machine address is a 64-bit
quantity containing the address of a 64-bit word in memory. The C
compiler has CHAR_BIT==8 (required because Unicos is a Unix-like
system). It implements byte pointers by storing a byte offset in the
(otherwise unused) high-order 3 bits of a 64-bit pointer value; this
offset is manipulated in software by code generated by the compiler.

(One result of this is that although Cray vector systems have blazingly
fast floating-point performance, string manipulation can be relatively
painfully slow.)

This means that, for a pointer of type char*, the low-order bit tells
you whether the word containing the pointed-to byte is at an odd or even
word address.

You're not likely to encounter any current system, but who knows what
architectures will be in common use, say, 10 years from now?

I'm pretty sure that any implementation of C that I am likely to use will
allow the kinds of pointer masking that I have in mind but are there better,
more C-like ways to go about this? Are there implementations on which it
might not work? And would it be acceptable to manipulate the pointers as
pointers to char even though malloc and free are defined to work with
pointers to void?

The C standard require char*, unsigned char*, signed char*, and void*
to have the same representation.

The *portable* way to do this would be to store the "used" bit
separately from the pointer. For example, if you know the base
address of the region of memory managed by malloc and free, you
can have a bit array (implemented with the usual shifts and masks)
containing one bit for each address within that region.

In C implementations, the code that implements malloc and free
*doesn't have to be portable*, and it commonly isn't. It's typically
optimized for different targets. It just as to behave as specified.

If you want something "portable" in the sense that it's not too
difficult to modify the code for porting to another system (as
opposed to recompiling it with no change), you might consider
writing a set of macros to handle the "used" bit, and to convert
back and forth between an annotated pointer and a unannotated
pointer. You can use a set of #ifdefs to switch between different
implementations of those macros for different systems.

Or you can just *assume* that an aligned pointer will always have
its low-order bit set to 0, at the cost of not supporting systems
where that assumption doesn't hold.

 

[Malcolm McLean]

To write a couple of memory management routines to implement malloc and free
it would be handy to take one bit from a pointer to use as an indicator of
whether a piece of memory is in use or is unused. Because each piece of
memory will be aligned any valid pointer will have its lower bit(s) clear so
it makes sense to take the lowest bit of a pointer and use it to indicate
whether a region is used or unused. That would lead to expressions like
these:

ptr |= 1;

ptr &= ~1;

if (ptr & 1) ...

My question is whether C's behaviour is defined or undefined for such
pointer manipulations. Would the pointers need to be cast to char pointers
for this to work? Any other issues I should be aware of?

Technically undefined I believe. It might be illegal for address variables to
have the low bit set on particular hardware.
In reality, setting the low bit of a pointer to indicate that the address
is in use is a reasonable thing to do. You expect to have to tweak malloc()
implementations for different hardware anyway, because of issues such as
address space, alignment, and access to RAM pools.

It's perfectly normal to implement a memory allocator in C. Just not for
the average Windows / Unix box program.

 

[BartC]

Technically undefined I believe. It might be illegal for address variables
to
have the low bit set on particular hardware.

But if it is possible, then you want to be able to do that without the
language (C) getting in your way.

It might only be undefined because the C standard can't guarantee it working
on every conceivable hardware that C runs on (and it's not hard to invent
some exotic machine where it can't work).

In reality, setting the low bit of a pointer to indicate that the address
is in use is a reasonable thing to do.

It would be reasonable if it will work with the sorts of platform you want
to run on (so in my case, x86 and ARM, others may have longer lists).

Although you can't rule out C still making it difficult, for example by an
optimising compiler knowing that the low order bits of a pointer are zero,
and somehow taking advantage of that (by not loading or saving those bits,
or using them for its own purposes!)

It's perfectly normal to implement a memory allocator in C. Just not for
the average Windows / Unix box program.

I tend to use my own allocator for small objects, because it's more
efficient than malloc. It uses large blocks obtained by malloc (but could
come direct from the OS). On one actual application, using malloc instead
made the program run at half the speed.

(Also I don't like the extra malloc overhead involved in managing the sizes
of memory blocks; I don't need that feature when I have millions of 16-byte
blocks to deal with for example; I /know/ they are 16 bytes long!)

 

[Malcolm McLean]

I tend to use my own allocator for small objects, because it's more
efficient than malloc. It uses large blocks obtained by malloc (but could
come direct from the OS). On one actual application, using malloc instead
made the program run at half the speed.

Allocating fixed blocks is much more efficient than calling a general-purpose
allocator, both in space and speed terms, especially for small blocks.
But usually it's an extra dependency that isn't tolerable for code that
needs to run in many different environments.

 

[James Harris]

To use bitwise operations on pointers, you'd have to convert
to uintptr_t and back again. (That's assuming uintptr_t exists,
which it won't if no integer type is big enough to hold a converted
pointer value without loss of information. That's a reasonably
safe assumption, and if it's violated on some exotic system your
code will fail to compile.)

One compiler I use doesn't have uintptr_t or intptr_t. Sadly its limits.h
also has no constant that conceivably relates to the width of an address so
I cannot see an easy way to set up a suitable integer. I could possibly do
something like (untested)

#ifndef uintptr_t
#define uintptr_t size_t
#endif

It might be good to have some code that will check when the program starts
that the conditions are satisfied such as

if (sizeof(char *) != sizeof(uintptr_t)) ...

A reasonable compromise? Would void * be any better there than char *?

The behavior is undefined, and I've worked on systems where it would
fail.

On Cray vector machines (T90, SV1), a machine address is a 64-bit
quantity containing the address of a 64-bit word in memory. The C
compiler has CHAR_BIT==8 (required because Unicos is a Unix-like
system). It implements byte pointers by storing a byte offset in the
(otherwise unused) high-order 3 bits of a 64-bit pointer value; this
offset is manipulated in software by code generated by the compiler.

(One result of this is that although Cray vector systems have blazingly
fast floating-point performance, string manipulation can be relatively
painfully slow.)

This means that, for a pointer of type char*, the low-order bit tells
you whether the word containing the pointed-to byte is at an odd or even
word address.

Even in that environment couldn't a C program align addresses to two machine
words (128-bit in this case) by clearing the lowest bit of a pointer
(perhaps after rounding)? Then that bit could be used as a flag. I suppose
one would need to start with the null pointer or something else that was
guaranteed not to have any of the top three bits set but as long as that was
maintained as an invariant couldn't the use of the lowest bit be treated as
a flag?

You're not likely to encounter any current system, but who knows what
architectures will be in common use, say, 10 years from now?

Yes. This is for a specific use but I would rather write code that depends
on C guarantees, if possible.

James

 

[James Harris]

»Each of the operands shall have integer type.«

6.5.12 Bitwise inclusive OR operator, N1570

That's an interesting point. Since C allows (or at least implementations of
C allow) such operations on a pointer and, as you point out, the operands
are required by the standard to be of integer type does that imply that the
pointer gets 'converted' to an integer for the bitwise operation to take
place? In other words, does the compiler perform an implementation specific
conversion to an integer so that the bitwise OR can be done? And if it does
wouldn't it 'convert' it to a intptr_t? Maybe it's going too far to say
that would be safe.

The C-like way is not to implement malloc, but to use malloc.

I know what you mean - when programming in C we nearly always use malloc for
memory allocation - though it could be argued that malloc is not a C
function. AIUI malloc is not part of C at all but merely part of the
standard library, and that some other allocator could be used just as well
and the program which still be wholly C.

James

 

[Barry Schwarz]

One compiler I use doesn't have uintptr_t or intptr_t. Sadly its limits.h
also has no constant that conceivably relates to the width of an address so
I cannot see an easy way to set up a suitable integer. I could possibly do
something like (untested)

#ifndef uintptr_t

This won't handle the case where uintptr_t is a typedef.

#define uintptr_t size_t
#endif

It might be good to have some code that will check when the program starts
that the conditions are satisfied such as

if (sizeof(char *) != sizeof(uintptr_t)) ...

A reasonable compromise? Would void * be any better there than char *?

I think void* would be better intuitively since the pointer in
question can have any valid type.

You could also try to make the code self adjusting in case you change
compilers.

#if sizeof(void*) <= sizeof(unsigned char)
typedef unsigned char myintptr_t;
#elif sizeof(void*) <= sizeof(unsigned short)
typedef unsigned short myintptr_t;
#elif sizeof(void*) <= sizeof(unsigned int)
typedef unsigned int myintptr_t;
#elif sizeof(void*) <= sizeof(unsigned long)
typedef unsigned long myintptr_t;
#elif sizeof(void*) <= sizeof(unsigned long long)
typedef unsigned long long myintptr_t;
#else
#error No integer type large enough to hold pointer value
#endif

 

[Stefan Ram]

I know what you mean - when programming in C we nearly always use malloc for
memory allocation - though it could be argued that malloc is not a C
function. AIUI malloc is not part of C at all but merely part of the
standard library, and that some other allocator could be used just as well
and the program which still be wholly C.

Yeah, there is no »malloc« in a /freestanding/
implementation of C IIRC, which nonetheless is a conforming
implementation of C.

I thought more along the lines that not every average
programer is capable of writing an implementation of
malloc that is better than the malloc provided by the
library in a /hosted/ implementation of C, so in a hosted
environment, it is usually common to use the malloc provided.

This does not necessarily exclude custom memory management,
e.g., by returning objects to a pool instead of using »free«,
by allocating small chunks in a large block managed by
custom functions, or by implementing a garbage collector.
But these can be built on top of the standard malloc and do
not have to replace it.

 

[Keith Thompson]

This won't handle the case where uintptr_t is a typedef.

uintptr_t, if it's defined, is *always* a typedef. A conforming
implementation is not permitted to define it as a macro.

UINTPTR_MAX is a macro that's defined if and only if uintptr_t exists,
so you can use #ifndef on that.

 

[James Harris]

ptr |= 1;

»Each of the operands shall have integer type.«

6.5.12 Bitwise inclusive OR operator, N1570

That's an interesting point. Since C allows (or at least implementations
of
C allow) such operations on a pointer and, as you point out, the operands
are required by the standard to be of integer type does that imply that
the
pointer gets 'converted' to an integer for the bitwise operation to take
place? In other words, does the compiler perform an implementation
specific
conversion to an integer so that the bitwise OR can be done? And if it
does
wouldn't it 'convert' it to a intptr_t? Maybe it's going too far to
say
that would be safe.

....

Having a pointer type as one of the parameters to a bitwise operator is
a constraint violation that REQUIRES a diagnostic.

Out of interest, why is a diagnostic required? Do the clauses below apply
only to explicit conversions? I see in n869 (which is not, AFAIK,
authoritative):

6.3.2.3 Pointers

5 An integer may be converted to any pointer type. Except as previously
specified, the result is implementation-defined, might not be properly
aligned, and might not point to an entity of the referenced type.49)


6 Any pointer type may be converted to an integer type. Except as previously
specified, the result is implementation-defined. If the result cannot be
represented in the integer type, the behavior is undefined. The result need
not be in the range of values of any integer type.

Any compiler that
does not give one is non-conforming. After giving that diagnostic, if
the compiler produces output, the results of running said program is
undefined by the standard.

That said, there are some compilers, which as an extension, (and having
a non-conforming mode which suppresses said required diagnostic), will
allow the implicit conversion of a pointer to (effectively) uintptr_t.

Section 6.3 speaks about implicit conversions and refers to the conversions
performed *by most ordinary operators* in 6.3.1.8 which gives the "Usual
arithmetic conversions" and after speaking about floating point promotions
it says:

Otherwise, the integer promotions are performed on both operands. Then the
following rules are applied to the promoted operands...
Doesn't that state the integer promotions are performed on both operands
irrespective of whether one is a pointer or not?

James

 

[BartC]

This does not necessarily exclude custom memory management,
e.g., by returning objects to a pool instead of using »free«,
by allocating small chunks in a large block managed by
custom functions, or by implementing a garbage collector.
But these can be built on top of the standard malloc and do
not have to replace it.

You still have the annoying problem that malloc needs somehow to remember
the size of each allocated block.

So if you're trying to make use of nice sensible allocation blocks such as
4096 bytes in size, you will find that each uses somewhat more memory
than 4096 bytes. In some tests I've just done, sizes of 4104, 4112, 4116,
and 4128 bytes! (Ie. overheads of 8, 16, 20, and 32 bytes.)

Sometimes you just don't want that (and would also prefer an allocation
aligned to the block size you've chosen, so lower 12 bits zero in this
example. Instead you might get it aligned to a multiple of 8, which itself
is odd.)

 

[Keith Thompson]

One compiler I use doesn't have uintptr_t or intptr_t. Sadly its limits.h
also has no constant that conceivably relates to the width of an address so
I cannot see an easy way to set up a suitable integer. I could possibly do
something like (untested)

If your implementation (compiler plus runtime library) doesn't define
uintptr_t and inptr_t, it's *probably* because it doesn't implement C99,
the standard that introduce those types and the <stdint.h> header that
defines them.

What compiler are you using? Some compilers don't attempt to conform to
C99 unless you use an option that tells them to do so.

uintptr_t, intptr_t, and the macros that define their limits are defined

#ifndef uintptr_t
#define uintptr_t size_t
#endif

That's reasonably likely to be correct, but it's not guaranteed. size_t
has to be big enough to hold the size of any single object. void*, and
therefore uintptr_t, has to be big enough to specify *any byte* of any
object. For a typical system with a monolithic addressing space,
they're likely to be the same size. For a system with a segmented
memory scheme, where there can be multiple segments but no single object
can occupy more than one segment, size_t might not be big enough to hold
a void* value without loss of information.

It might be good to have some code that will check when the program starts
that the conditions are satisfied such as

if (sizeof(char *) != sizeof(uintptr_t)) ...

A reasonable compromise? Would void * be any better there than char *?

void* is probably clearer that char*, but void* and char* are required
to have the same size and representation.

But uintptr_t could be *bigger* than void*. You can convert a void* to
uintptr_t and back again without loss of information, but there's no
guarantee in the other direction. (Still, they're the same size on
every system I've heard of.)

[...]

Even in that environment couldn't a C program align addresses to two machine
words (128-bit in this case) by clearing the lowest bit of a pointer
(perhaps after rounding)? Then that bit could be used as a flag. I suppose
one would need to start with the null pointer or something else that was
guaranteed not to have any of the top three bits set but as long as that was
maintained as an invariant couldn't the use of the lowest bit be treated as
a flag?

I don't believe there's any advantage to using an alignment stricter
than 1 64-bit word. I'd hesitate to impose such a requirement.

You could put the flag in the 4th bit from the top, which I believe is
always 0 for a valid pointer. (The addressing space is much less than
2**60 words.) Use a macro to define which bit you're using for the
flag. You'd have to configure it manually, but that's not unreasonable
for this kind of low-level bit-twiddling.

 

[Keith Thompson]

»Each of the operands shall have integer type.«

6.5.12 Bitwise inclusive OR operator, N1570

That's an interesting point. Since C allows (or at least implementations of
C allow) such operations on a pointer and, as you point out, the operands
are required by the standard to be of integer type does that imply that the
pointer gets 'converted' to an integer for the bitwise operation to take
place? In other words, does the compiler perform an implementation specific
conversion to an integer so that the bitwise OR can be done? And if it does
wouldn't it 'convert' it to a intptr_t? Maybe it's going too far to say
that would be safe.

No, it means that any code that attempts to apply the bitwise OR
operator "|" to a pointer value violates a constraint. A conforming
compiler must diagnose it and may reject it. (A decent compiler, IMHO,
will reject it.)

If you want to perform bitwise operations on pointer representations,
you simply have to convert them yourself.

[...]

I know what you mean - when programming in C we nearly always use malloc for
memory allocation - though it could be argued that malloc is not a C
function. AIUI malloc is not part of C at all but merely part of the
standard library, and that some other allocator could be used just as well
and the program which still be wholly C.

The malloc() function is part of the C standard library. Section 6 of
the C standard describes the language; section 7 defines the library.
malloc() is as much a part of standard C as "int" and "+" (except that,
like most of the library, it's optional for freestanding
implementations).

malloc() needn't be *implemented* in C, but I don't think that's the
point you were making.

 

[Keith Thompson]

Out of interest, why is a diagnostic required?

Because the standard says so.

The relevant wording has already been cited, but I'll quote a bit more
of it here:

N1570 6.5.11 Bitwise exclusive OR operator

Syntax
...

Constraints
Each of the operands shall have integer type.

There's no wiggle room there. If either operand has a non-integer type,
a constraint is violated and a diagnostic is required.

Do the clauses below apply
only to explicit conversions? I see in n869 (which is not, AFAIK,
authoritative):

6.3.2.3 Pointers

5 An integer may be converted to any pointer type. Except as previously
specified, the result is implementation-defined, might not be properly
aligned, and might not point to an entity of the referenced type.49)

Yes, an integer type may be converted to any pointer type -- but the
conversions that may be done implicitly are described elsewhere, and do
*not* include any pointer-to-integer conversions.

[...]

Section 6.3 speaks about implicit conversions and refers to the conversions
performed *by most ordinary operators* in 6.3.1.8 which gives the "Usual
arithmetic conversions" and after speaking about floating point promotions
it says:

Otherwise, the integer promotions are performed on both operands. Then the
following rules are applied to the promoted operands...
Doesn't that state the integer promotions are performed on both operands
irrespective of whether one is a pointer or not?

The "usual arithmetic conversions" and "integer promotions" never apply
to pointers, as you can see if you read the descriptions of those terms.

 

[James Harris]

You still have the annoying problem that malloc needs somehow to remember
the size of each allocated block.

So if you're trying to make use of nice sensible allocation blocks such as
4096 bytes in size, you will find that each uses somewhat more memory
than 4096 bytes. In some tests I've just done, sizes of 4104, 4112, 4116,
and 4128 bytes! (Ie. overheads of 8, 16, 20, and 32 bytes.)

Sometimes you just don't want that (and would also prefer an allocation
aligned to the block size you've chosen, so lower 12 bits zero in this
example. Instead you might get it aligned to a multiple of 8, which itself
is odd.)

ISTM that most malloc implementations place their memory managment nodes
between the allocated memory spaces which would cause the alignment creep
you mention. It is also potentially fragile because 1) those spaces cannot
be protected, and 2) a pointer going just beyond where it should could lead
to corruption of a node.

I came up with an idea for a memory allocator which stores all of its
metadata elsewhere (though I am not looking at impementing that just now).
It is a little more complex and wouldn't have such good free() performance.
free() normally just has to offset the pointer it is passed in order to find
the node but if not stored relative to the start of the allocated memory
space the node would need to be found. Storing the node-type data elsewhere,
though, does buy you quite a bit: greater security, the alignments you want
and often faster scanning for malloc to find space.

Don't forget that alignment creep can be a good thing if it ends up
offsetting cache lines that are used together so perfect alignment can
sometimes be a bad thing - less of a problem now with CPUs which have
many-way caches.

James

 

[James Harris]

....


If your implementation (compiler plus runtime library) doesn't define
uintptr_t and inptr_t, it's *probably* because it doesn't implement C99,
the standard that introduce those types and the <stdint.h> header that
defines them.

What compiler are you using? Some compilers don't attempt to conform to
C99 unless you use an option that tells them to do so.

One I have used (the challenging one) is bcc (Bruce's, not Borland's). It is
not C99 compliant or anything like it. It is not even a true ansi C compiler
though given the right compile options including the -ansi switch it does
handle the ansi-type C I feed it.

Nevertheless, I would rather write code which conforms to the rules. Some of
the code I write also has to compile under gcc so I try to write code that
will work on any valid compiler.

....

I don't believe there's any advantage to using an alignment stricter
than 1 64-bit word. I'd hesitate to impose such a requirement.

This would only be for allocating blocks of memory. It can make sense to
allocate those blocks on two-word boundaries (or coarser such as four-word
boundaries) and won't do any harm.

You could put the flag in the 4th bit from the top, which I believe is
always 0 for a valid pointer. (The addressing space is much less than
2**60 words.) Use a macro to define which bit you're using for the
flag. You'd have to configure it manually, but that's not unreasonable
for this kind of low-level bit-twiddling.

If I were to align memory in any program it would always have to be the
lowest bits that got zeroed. If that wouldn't cause coarser alignement on
some unusual machines that would be surprising. The point of this thread is
to avoid writing code specifically for any given target machine as far as
possible.

James

 

[Keith Thompson]

This would only be for allocating blocks of memory. It can make sense to
allocate those blocks on two-word boundaries (or coarser such as four-word
boundaries) and won't do any harm.

Probably true.

For a byte pointer, setting the low-order bit to zero deosn't mean much;
it can still be misaligned. But if you're limiting yourself to word
pointers, then yes, you can do that.

If I were to align memory in any program it would always have to be the
lowest bits that got zeroed. If that wouldn't cause coarser alignement on
some unusual machines that would be surprising. The point of this thread is
to avoid writing code specifically for any given target machine as far as
possible.

You're still making assumptions about pointer representation that go
beyond what the C standard guarantees.

Parameterizing which bit you use for a flag could *in principle* let
your code work correctly on some implementations where it might fail if
you always use the low-order bit, at the expense of having to change a
one-line macro definition for some targets. I don't know enough about
your goals and requirements to tell you whether that's worthwhile.
Using a bit outside the pointer could let you write 100% portable C
code, but at the expense of allocating extra memory. The tradeoffs are
up to you.

 

[Stefan Ram]

I came up with an idea for a memory allocator which stores all of its
metadata elsewhere (though I am not looking at impementing that just now).

Often, the size of an object is known statically and does not have
to be stored in memory at all. On the Amiga, one can use operating
system functions like:

if( m = AllocMem( 100, MEMF_ANY )){ use( m ); FreeMem( m, 100); }

, and as you can see, one has to pass »100« to »FreeMem« again.