Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #43600 > unrolled thread

Defined and undefined C pointer manipulation

Back to article view | Back to comp.lang.c

Contents

  Defined and undefined C pointer manipulation "James Harris" <james.harris.1@gmail.com> - 2014-04-26 18:35 +0100
    Re: Defined and undefined C pointer manipulation Keith Thompson <kst-u@mib.org> - 2014-04-26 12:04 -0700
      Re: Defined and undefined C pointer manipulation "James Harris" <james.harris.1@gmail.com> - 2014-04-27 19:11 +0100
        Re: Defined and undefined C pointer manipulation Barry Schwarz <schwarzb@dqel.com> - 2014-04-27 11:46 -0700
          Re: Defined and undefined C pointer manipulation Keith Thompson <kst-u@mib.org> - 2014-04-27 12:46 -0700
          Re: Defined and undefined C pointer manipulation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-04-28 02:53 +0100
        Re: Defined and undefined C pointer manipulation Keith Thompson <kst-u@mib.org> - 2014-04-27 12:57 -0700
          Re: Defined and undefined C pointer manipulation "James Harris" <james.harris.1@gmail.com> - 2014-04-27 21:56 +0100
            Re: Defined and undefined C pointer manipulation Keith Thompson <kst-u@mib.org> - 2014-04-27 14:25 -0700
              Re: Defined and undefined C pointer manipulation glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-27 22:51 +0000
    Re: Defined and undefined C pointer manipulation Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-27 06:21 -0700
      Re: Defined and undefined C pointer manipulation "BartC" <bc@freeuk.com> - 2014-04-27 16:51 +0100
        Re: Defined and undefined C pointer manipulation Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-27 10:36 -0700
        Re: Defined and undefined C pointer manipulation Ian Collins <ian-news@hotmail.com> - 2014-04-28 11:40 +1200
    Re: Defined and undefined C pointer manipulation "James Harris" <james.harris.1@gmail.com> - 2014-04-27 19:23 +0100
      Re: Defined and undefined C pointer manipulation Richard Damon <Richard@Damon-Family.org> - 2014-04-27 14:56 -0400
        Re: Defined and undefined C pointer manipulation "James Harris" <james.harris.1@gmail.com> - 2014-04-27 20:52 +0100
          Re: Defined and undefined C pointer manipulation Keith Thompson <kst-u@mib.org> - 2014-04-27 13:16 -0700
      Re: Defined and undefined C pointer manipulation "BartC" <bc@freeuk.com> - 2014-04-27 20:55 +0100
        Re: Defined and undefined C pointer manipulation "James Harris" <james.harris.1@gmail.com> - 2014-04-27 21:20 +0100
          Re: Defined and undefined C pointer manipulation glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-27 22:39 +0000
          Re: Defined and undefined C pointer manipulation glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-04-27 22:43 +0000
          Re: Defined and undefined C pointer manipulation "BartC" <bc@freeuk.com> - 2014-04-28 00:13 +0100
      Re: Defined and undefined C pointer manipulation Keith Thompson <kst-u@mib.org> - 2014-04-27 13:01 -0700
      Re: Defined and undefined C pointer manipulation James Kuyper <jameskuyper@verizon.net> - 2014-04-27 22:07 -0400
      Re: Defined and undefined C pointer manipulation Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-28 00:47 -0700
        Re: Defined and undefined C pointer manipulation Ian Collins <ian-news@hotmail.com> - 2014-04-28 20:01 +1200
          Re: Defined and undefined C pointer manipulation Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-28 02:11 -0700
            Re: Defined and undefined C pointer manipulation Ian Collins <ian-news@hotmail.com> - 2014-04-28 22:38 +1200
              Re: Defined and undefined C pointer manipulation Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-28 04:50 -0700
        Re: Defined and undefined C pointer manipulation "BartC" <bc@freeuk.com> - 2014-04-28 09:22 +0100
          Re: Defined and undefined C pointer manipulation Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-04-28 05:31 -0700

Page 1 of 2  [1] 2  Next page →

#43600 — Defined and undefined C pointer manipulation

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

[toc] | [next] | [standalone]

#43607

"James Harris" <james.harris.1@gmail.com> writes:
> 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.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#43663

"Keith Thompson" <kst-u@mib.org> wrote in message 
news:lnppk3rjxh.fsf@nuthaus.mib.org...
> "James Harris" <james.harris.1@gmail.com> writes:
>> 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.)

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

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


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

[toc] | [prev] | [next] | [standalone]

#43666

On Sun, 27 Apr 2014 19:11:31 +0100, "James Harris"
<james.harris.1@gmail.com> wrote:

>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

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#43672

Barry Schwarz <schwarzb@dqel.com> writes:
> On Sun, 27 Apr 2014 19:11:31 +0100, "James Harris"
> <james.harris.1@gmail.com> wrote:
>
>>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.

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 (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#43692

Barry Schwarz <schwarzb@dqel.com> writes:
<snip>
> 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

This won't work because, to put it rather informally, # lines are
processed before sizeof means anything.  Sorry I can't offer an
alternative.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#43675

"James Harris" <james.harris.1@gmail.com> writes:
> "Keith Thompson" <kst-u@mib.org> wrote in message 
> news:lnppk3rjxh.fsf@nuthaus.mib.org...
>> "James Harris" <james.harris.1@gmail.com> writes:
>>> 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.)
>
> 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
in <stdint.h>, not in <limits.h>.

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

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

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#43682

"Keith Thompson" <kst-u@mib.org> wrote in message 
news:lnzjj6pmui.fsf@nuthaus.mib.org...
> "James Harris" <james.harris.1@gmail.com> writes:

...

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

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.

...

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

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

[toc] | [prev] | [next] | [standalone]

#43683

"James Harris" <james.harris.1@gmail.com> writes:
> "Keith Thompson" <kst-u@mib.org> wrote in message 
> news:lnzjj6pmui.fsf@nuthaus.mib.org...
[...]
>> 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.

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

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 (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#43687

Keith Thompson <kst-u@mib.org> wrote:

(snip)

> 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.
 
(snip)

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

The BLAST program for DNA and protein sequence searching does that.
It generates finite state automata in an array of pointers, but also
needs a bit to indicate when a match is made. On word addressed 
machines, where pointer pointers have low zero bits, it uses the
low bit. On word addressed Cray machines, a high order bit.
(More specifically, it generates a DAWG.)

I believe the comments specifically indicate Cray. 

In normal use, most characters are not matches, so the pointer is
used directly, for a very fast inner loop. In the case of a match,
it exits the loop and processes the hit.

(It was some years ago that I was working with BLAST source.
It could have changed by now.)

-- glen

[toc] | [prev] | [next] | [standalone]

#43647

On Saturday, April 26, 2014 6:35:03 PM UTC+1, James Harris wrote:
> 
> 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. 

[toc] | [prev] | [next] | [standalone]

#43659

"Malcolm McLean" <malcolm.mclean5@btinternet.com> wrote in message
news:e835afea-a732-43f4-bba2-f6452995be1b@googlegroups.com...
> On Saturday, April 26, 2014 6:35:03 PM UTC+1, James Harris wrote:
>>
>> 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

>> My question is whether C's behaviour is defined or undefined for such
>> pointer manipulations.

> 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!)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#43662

On Sunday, April 27, 2014 4:51:31 PM UTC+1, Bart wrote:
> "Malcolm McLean" <malcolm.mclean5@btinternet.com> wrote in message
> 
> 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. 

[toc] | [prev] | [next] | [standalone]

#43690

BartC wrote:
>
> 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.

I find it's better to stick to the standard interface and use the best 
memory allocator library (at least in the Unix world, there tend to be 
several allocator libraries available on any one platform) for a 
particular application.  What works best in a single threaded 
application may be hopeless in a multi-threaded one.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#43664

"Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message 
news:pointers-20140426195429@ram.dialup.fu-berlin.de...
> "James Harris" <james.harris.1@gmail.com> writes:
>>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 [u]intptr_t? Maybe it's going too far to say 
that would be safe.

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

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

[toc] | [prev] | [next] | [standalone]

#43667

On 4/27/14, 2:23 PM, James Harris wrote:
> "Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message 
> news:pointers-20140426195429@ram.dialup.fu-berlin.de...
>> "James Harris" <james.harris.1@gmail.com> writes:
>>> 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 [u]intptr_t? Maybe it's going too far to say 
> that would be safe.
> 
...
> 
> James
> 
> 

Having a pointer type as one of the parameters to a bitwise operator is
a constraint violation that REQUIRES a diagnostic. 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.

How safe that is would be up to you. It is non-conforming code, relying
on extra-standard promises by the implementation (I don't want to say
implementation defined, because that is a term the standard defines, and
this doesn't quite fall into that definition). It IS "well defined" by
the implementation, so as long as you are willing to restrict yourself
to implementations that make the same promises, you are fine.

[toc] | [prev] | [next] | [standalone]

#43673

"Richard Damon" <Richard@Damon-Family.org> wrote in message 
news:Lpc7v.64776$rL7.53357@en-nntp-16.dc1.easynews.com...
> On 4/27/14, 2:23 PM, James Harris wrote:
>> "Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message
>> news:pointers-20140426195429@ram.dialup.fu-berlin.de...
>>> "James Harris" <james.harris.1@gmail.com> writes:
>>>> 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 [u]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

[toc] | [prev] | [next] | [standalone]

#43678

"James Harris" <james.harris.1@gmail.com> writes:
> "Richard Damon" <Richard@Damon-Family.org> wrote in message 
> news:Lpc7v.64776$rL7.53357@en-nntp-16.dc1.easynews.com...
[...]
>> 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?

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.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#43674

"Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message
news:malloc-20140427210817@ram.dialup.fu-berlin.de...
> "James Harris" <james.harris.1@gmail.com> writes:
>>"Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message
>>>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.

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

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#43679

"BartC" <bc@freeuk.com> wrote in message 
news:Qgd7v.167912$Ey6.6980@fx24.am4...
>
>
> "Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message
> news:malloc-20140427210817@ram.dialup.fu-berlin.de...
>> "James Harris" <james.harris.1@gmail.com> writes:
>>>"Stefan Ram" <ram@zedat.fu-berlin.de> wrote in message
>>>>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.
>
>>  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.)

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web