Defined and undefined C pointer manipulation

Discussion in 'C Programming' started by James Harris, Apr 26, 2014.

  1. James Harris

    James Harris Guest

    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
     
    James Harris, Apr 26, 2014
    #1
    1. Advertisements

  2. James Harris

    Stefan Ram Guest

    »Each of the operands shall have integer type.«

    6.5.12 Bitwise inclusive OR operator, N1570
    The C-like way is not to implement malloc, but to use malloc.
     
    Stefan Ram, Apr 26, 2014
    #2
    1. Advertisements

  3. 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.)
    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?
    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.
     
    Keith Thompson, Apr 26, 2014
    #3
  4. 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.
     
    Malcolm McLean, Apr 27, 2014
    #4
  5. James Harris

    BartC Guest

    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).
    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!)
    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!)
     
    BartC, Apr 27, 2014
    #5
  6. 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.
     
    Malcolm McLean, Apr 27, 2014
    #6
  7. James Harris

    James Harris Guest

    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 *?

    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?
    Yes. This is for a specific use but I would rather write code that depends
    on C guarantees, if possible.

    James
     
    James Harris, Apr 27, 2014
    #7
  8. James Harris

    James Harris Guest

    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.
    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
     
    James Harris, Apr 27, 2014
    #8
  9. This won't handle the case where uintptr_t is a typedef.
    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
     
    Barry Schwarz, Apr 27, 2014
    #9
  10. James Harris

    Stefan Ram Guest

    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.
     
    Stefan Ram, Apr 27, 2014
    #10
  11. 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.
     
    Keith Thompson, Apr 27, 2014
    #11
  12. James Harris

    James Harris Guest



    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.
    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
     
    James Harris, Apr 27, 2014
    #12
  13. James Harris

    BartC Guest

    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.)
     
    BartC, Apr 27, 2014
    #13
  14. 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
    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.
    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.)

    [...]
    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, Apr 27, 2014
    #14


  15. 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.

    [...]
    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, Apr 27, 2014
    #15
  16. 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.
    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.

    [...]
    The "usual arithmetic conversions" and "integer promotions" never apply
    to pointers, as you can see if you read the descriptions of those terms.
     
    Keith Thompson, Apr 27, 2014
    #16
  17. James Harris

    James Harris Guest

    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, Apr 27, 2014
    #17
  18. James Harris

    James Harris Guest

    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.

    ....
    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.
    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
     
    James Harris, Apr 27, 2014
    #18
  19. 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.
    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.
     
    Keith Thompson, Apr 27, 2014
    #19
  20. James Harris

    Stefan Ram Guest

    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.
     
    Stefan Ram, Apr 27, 2014
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.