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

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

Aliasing and subtyping structs

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

Contents

  Aliasing and subtyping structs Andreas <nospam@invalid.invalid> - 2016-11-01 13:15 +0100
    Re: Aliasing and subtyping structs Andreas <nospam@invalid.invalid> - 2016-11-01 13:34 +0100
      Re: Aliasing and subtyping structs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-11-01 15:27 +0000
        Re: Aliasing and subtyping structs Andreas <nospam@invalid.invalid> - 2016-11-02 09:47 +0100
          Re: Aliasing and subtyping structs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-11-02 15:47 +0000
            Re: Aliasing and subtyping structs Andreas <nospam@invalid.invalid> - 2016-11-08 00:24 +0100
              Re: Aliasing and subtyping structs supercat@casperkitty.com - 2016-11-07 21:42 -0800
          Re: Aliasing and subtyping structs <william@wilbur.25thandClement.com> - 2016-11-03 18:53 -0700
            Re: Aliasing and subtyping structs supercat@casperkitty.com - 2016-11-04 09:56 -0700
            Re: Aliasing and subtyping structs Andreas <nospam@invalid.invalid> - 2016-11-08 21:53 +0100
    Re: Aliasing and subtyping structs James Kuyper <jameskuyper@verizon.net> - 2016-11-01 11:41 -0400
      Re: Aliasing and subtyping structs Andreas <nospam@invalid.invalid> - 2016-11-02 09:55 +0100
    "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Anton Shepelev <anton.txt@g{oogle}mail.com> - 2016-11-21 16:59 +0300
      Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-21 07:32 -0800
      Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "James R. Kuyper" <jameskuyper@verizon.net> - 2016-11-21 11:15 -0500
        Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-21 08:35 -0800
          Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Anton Shepelev <anton.txt@g{oogle}mail.com> - 2016-11-22 11:42 +0300
            Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-22 06:50 -0800
              Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-11-22 16:07 +0000
                Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-22 12:02 -0800
                  Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-11-22 23:36 +0000
                    Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-22 16:24 -0800
                      Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Richard Damon <Richard@Damon-Family.org> - 2016-11-22 22:21 -0500
                        Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-23 08:31 -0800
                          Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] me <crisdunbar@gmail.com> - 2016-11-23 09:01 -0800
                            Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-23 12:05 -0800
        Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Anton Shepelev <anton.txt@gmail.com> - 2016-11-22 23:23 +0300
          Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "James R. Kuyper" <jameskuyper@verizon.net> - 2016-11-22 16:02 -0500
            Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-22 14:13 -0800
              Re: container_of() macro Noob <root@127.0.0.1> - 2016-11-23 01:10 +0100
                Re: container_of() macro <william@wilbur.25thandClement.com> - 2016-11-22 20:10 -0800
                  Re: container_of() macro "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-23 15:10 -0800
                Re: container_of() macro David Brown <david.brown@hesbynett.no> - 2016-11-23 11:31 +0100
                  Re: container_of() macro Anton Shepelev <anton.txt@g{oogle}mail.com> - 2016-11-23 14:07 +0300
                  Re: container_of() macro supercat@casperkitty.com - 2016-11-23 08:41 -0800
            Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Anton Shepelev <anton.txt@gmail.com> - 2016-11-30 00:14 +0300
              Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "James R. Kuyper" <jameskuyper@verizon.net> - 2016-11-29 17:23 -0500
                Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Anton Shepelev <anton.txt@gmail.com> - 2016-12-04 18:48 +0300
                  Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "James R. Kuyper" <jameskuyper@verizon.net> - 2016-12-04 12:17 -0500
                    Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Anton Shepelev <anton.txt@gmail.com> - 2016-12-04 22:15 +0300
                      Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "James R. Kuyper" <jameskuyper@verizon.net> - 2016-12-04 15:06 -0500
                        Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Anton Shepelev <anton.txt@gmail.com> - 2016-12-12 22:31 +0300
      Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-23 13:39 -0800
        Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] luser droog <luser.droog@gmail.com> - 2016-11-23 15:10 -0800
          Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-23 15:13 -0800
            Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] luser droog <luser.droog@gmail.com> - 2016-11-23 18:29 -0800
            Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Anton Shepelev <anton.txt@g{oogle}mail.com> - 2016-11-24 11:41 +0300
            Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Thiago Adams <thiago.adams@gmail.com> - 2016-11-24 03:29 -0800
              Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-24 17:37 -0800
                Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-25 09:55 -0800
                Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Thiago Adams <thiago.adams@gmail.com> - 2016-11-25 15:22 -0800
                  Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-11-28 18:18 -0800
                    Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Thiago Adams <thiago.adams@gmail.com> - 2016-11-29 04:48 -0800
                      Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-29 07:28 -0800
                        Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Thiago Adams <thiago.adams@gmail.com> - 2016-11-30 08:26 -0800
                          Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] supercat@casperkitty.com - 2016-11-30 09:13 -0800
                      Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-12-12 16:44 -0800
                        Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Melzzzzz <mel@zzzzz.com> - 2016-12-13 02:18 +0100
                        Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Thiago Adams <thiago.adams@gmail.com> - 2016-12-14 09:47 -0800
                          Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs] Thiago Adams <thiago.adams@gmail.com> - 2016-12-14 10:14 -0800

Page 1 of 3  [1] 2 3  Next page →

#95500 — Aliasing and subtyping structs

Hi all,

while searching the web I've found a lot of assertions that a common
idiom of subtyping structs in C is well-defined by virtue of the first
struct member always having the same address as the surrounding struct.
What I'm concerned about is aliasing in this context.

struct sub_type
{
        uint8_t super_tag;
        ...
};

struct super_type
{
        struct sub_type super;
        ...
};

struct hyper_type
{
        struct super_type super;
        ...
};

void foo (struct sub_type* base)
{
        struct super_type* up = 0;
        struct hyper_type* upper = 0;
        if (base->super_tag == UP_ID)
        {
                up = (struct super_type*) base; // *NOT aliasing!?*
                ...
        }
        else if (base->super_tag == UP_ID)
        {
                upper = (struct hyper_type*) base; // *NOT aliasing!?*
                ...
        }
        ...
}

void bar (struct super_type* up, struct hyper_type* upper)
{
        struct sub_type* base1 = (struct sub_type*) up; // *ALIASING?*
        struct sub_type* base2 = (struct sub_type*) upper; // *ALIASING?*
        struct sub_type* base1 = up.super;
        struct sub_type* base2 = upper.super.super;
        ...
}

Sorry for the lengthy code ...

Could you please tell me whether my assumptions in the comments above
are right or not?


TIA,

Andreas

-- 
What do you mean? An African or a European swallow?

[toc] | [next] | [standalone]

#95503

Following up to myself to add missing address operators to sample code:

struct sub_type
{
        uint8_t super_tag;
        ...
};

struct super_type
{
        struct sub_type super;
        ...
};

struct hyper_type
{
        struct super_type super;
        ...
};

void foo (struct sub_type* base)
{
        struct super_type* up = 0;
        struct hyper_type* upper = 0;
        if (base->super_tag == UP_ID)
        {
                up = (struct super_type*) base; // *NOT aliasing!?*
                ...
        }
        else if (base->super_tag == UP_ID)
        {
                upper = (struct hyper_type*) base; // *NOT aliasing!?*
                ...
        }
        ...
}

void bar (struct super_type* up, struct hyper_type* upper)
{
        struct sub_type* base1 = (struct sub_type*) up; // *ALIASING?*
        struct sub_type* base2 = (struct sub_type*) upper; // *ALIASING?*
        struct sub_type* base3 = &up.super;
        struct sub_type* base4 = &upper.super.super;
        ...
}

Sorry,

Andreas

-- 
What do you mean? An African or a European swallow?

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

#95515

Andreas <nospam@invalid.invalid> writes:

> Following up to myself to add missing address operators to sample code:
>
> struct sub_type
> {
>         uint8_t super_tag;
>         ...
> };
>
> struct super_type
> {
>         struct sub_type super;
>         ...
> };
>
> struct hyper_type
> {
>         struct super_type super;
>         ...
> };

This looks odd to me.  I'd expect more and more specific classes to be
progressively derived from a base class.  Those derived classes would be
sub- (and sub-sub-classes).  But this is a sketch so I might have the
wrong end of the stick.

> void foo (struct sub_type* base)
> {
>         struct super_type* up = 0;
>         struct hyper_type* upper = 0;
>         if (base->super_tag == UP_ID)
>         {
>                 up = (struct super_type*) base; // *NOT aliasing!?*
>                 ...
>         }
>         else if (base->super_tag == UP_ID)
>         {
>                 upper = (struct hyper_type*) base; // *NOT aliasing!?*
>                 ...
>         }
>         ...
> }
>
> void bar (struct super_type* up, struct hyper_type* upper)
> {
>         struct sub_type* base1 = (struct sub_type*) up; // *ALIASING?*
>         struct sub_type* base2 = (struct sub_type*) upper; // *ALIASING?*
>         struct sub_type* base3 = &up.super;
>         struct sub_type* base4 = &upper.super.super;

(you need -> rather than the first .)

>         ...
> }

You ask if your comments are correct.  The trouble is that aliasing is a
very general word.  In this context two pointers to the same object are
always aliases -- that's all it means -- so all of your pointer
assignments set up aliases.

I think what you are asking is whether the aliases conflict with places
where the compiler may assume that no aliasing is taking place.  That
will crop up in places where you don't have any comments.  For example
since 'up' and 'upper' are pointers to distinct types, the compiler may
assume that they do not alias.

Unfortunately I can't follow what you are doing in enough detail to
comment on whether it's OK or not.

-- 
Ben.

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

#95566

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

>
> This looks odd to me.  I'd expect more and more specific classes to be
> progressively derived from a base class.  Those derived classes would be
> sub- (and sub-sub-classes).  But this is a sketch so I might have the
> wrong end of the stick.

It has been some time since I have used usenet, so my question was
completely misleading/wrong.  I'll try again below ...

> Unfortunately I can't follow what you are doing in enough detail to
> comment on whether it's OK or not.

I reformulate in OOP terms ...

struct base_type
{
        uint8_t type_tag;
        ...
};

struct derived_type
{
        struct base_type base;
        // more specific data here
        ...
};

struct more_derived_type
{
        struct derived_type base;
        // even more specific data here
        ...
};

I find many references to this idiom, often asking whether the language
standard supports it.  Unfortunately I can only find answers referring
to the fact that the 'base' members above are guaranteed by C (and
consequentially for PODs by C++) to have the same address as each value
of their containing struct types.

That's fine but I believe that there is another aspect to be considered
when using this idiom, namely aliasing.  Regarding this aspect I find
the following reference in both C99 (I refer to draft N 1256) and C11
(as of draft N 1570) in paragraph 6.5.7:

<quote N 1256>

An object shall have its stored value accessed only by an lvalue
expression that has one of the following types:

...

- an aggregate or union type that includes one of the aforementioned
types among its members (including, recursively, a member of a
subaggregate or contained union)

...

</quote N 1256>

When using the idiom mentioned above it is often necessary to cast a
pointer from a derived type to a base type (upcast) or vice (downcast).

As a use case consider a library defining the base type and allowing for
the user to define derived types using the idiom above.  When there are
callbacks from the lib to user code, usually there are downcast in user
code necessary to restore the more detailed information from the derived
types (that the lib code doesn't know), i.e. something along the lines:

void downcaster (struct base_type* sth)
{
        struct derived_type* detailed = 0;
        struct more_derived_type* more_detailed = 0;

        if (sth->type_tag == DERIVED_ID)
        {
                detailed = (struct derived_type*) sth; // OK
        }
        else if (sth->type_tag == MORE_DERIVED_ID)
        {
                more_detailed = (struct more_derived_type*) sth; // OK
        }
        ...
}

My understanding of section 6.5.7 is that neither 'detailed' nor
'more_detailed' alias the object pointed to by 'sth'.

On the other hand when user code calls library APIs it will be necessary
to upcast pointers, as the library API will only know about base types.

void upcaster (struct derived_type* d, struct more_derived_type* md)
{
        struct base_type* b1 = (struct base_type*) d; // NOK
        struct base_type* b2 = (struct base_type*) md; // NOK

        struct base_type* b3 = & (d->base);
        struct base_type* b4 = & (md->base->base);

        call_lib_api (b[1234]);
        ...
}

I understand paragraph 6.5.7 so that 'b1' is aliasing 'd' and 'b2' is
aliasing 'md', while 'b3' and'b4' are obviously ok.

My question is: Is my understanding, as described above, correct or am I
lost in standardese here?


TIA,

Andreas

-- 
What do you mean? An African or a European swallow?

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

#95595

Andreas <nospam@invalid.invalid> writes:
<snip>
> struct base_type
> {
>         uint8_t type_tag;
>         ...
> };
>
> struct derived_type
> {
>         struct base_type base;
>         // more specific data here
>         ...
> };
>
> struct more_derived_type
> {
>         struct derived_type base;
>         // even more specific data here
>         ...
> };
>
> I find many references to this idiom, often asking whether the language
> standard supports it.  Unfortunately I can only find answers referring
> to the fact that the 'base' members above are guaranteed by C (and
> consequentially for PODs by C++) to have the same address as each value
> of their containing struct types.

Right, but address is a little vague.  A C pointer is an address with a
type and, whist the offset of the first (non-bitfield) member of a
struct is guaranteed to be zero, a pointer to the struct and a pointer
to the first member will have different types.  This matters because the
effective type rules you are concerned with are all about types.  The
address is not really the issue.

> That's fine but I believe that there is another aspect to be considered
> when using this idiom, namely aliasing.  Regarding this aspect I find
> the following reference in both C99 (I refer to draft N 1256) and C11
> (as of draft N 1570) in paragraph 6.5.7:
>
> <quote N 1256>
>
> An object shall have its stored value accessed only by an lvalue
> expression that has one of the following types:
>
> ...
>
> - an aggregate or union type that includes one of the aforementioned
> types among its members (including, recursively, a member of a
> subaggregate or contained union)
>
> ...
>
> </quote N 1256>
>
> When using the idiom mentioned above it is often necessary to cast a
> pointer from a derived type to a base type (upcast) or vice (downcast).
>
> As a use case consider a library defining the base type and allowing for
> the user to define derived types using the idiom above.  When there are
> callbacks from the lib to user code, usually there are downcast in user
> code necessary to restore the more detailed information from the derived
> types (that the lib code doesn't know), i.e. something along the lines:
>
> void downcaster (struct base_type* sth)
> {
>         struct derived_type* detailed = 0;
>         struct more_derived_type* more_detailed = 0;
>
>         if (sth->type_tag == DERIVED_ID)
>         {
>                 detailed = (struct derived_type*) sth; // OK
>         }
>         else if (sth->type_tag == MORE_DERIVED_ID)
>         {
>                 more_detailed = (struct more_derived_type*) sth; // OK
>         }
>         ...
> }
>
> My understanding of section 6.5.7 is that neither 'detailed' nor
> 'more_detailed' alias the object pointed to by 'sth'.

No, they are all aliases.

> On the other hand when user code calls library APIs it will be necessary
> to upcast pointers, as the library API will only know about base types.
>
> void upcaster (struct derived_type* d, struct more_derived_type* md)
> {
>         struct base_type* b1 = (struct base_type*) d; // NOK
>         struct base_type* b2 = (struct base_type*) md; // NOK
>
>         struct base_type* b3 = & (d->base);
>         struct base_type* b4 = & (md->base->base);
>
>         call_lib_api (b[1234]);

What's b?

>         ...
> }
>
> I understand paragraph 6.5.7 so that 'b1' is aliasing 'd' and 'b2' is
> aliasing 'md', while 'b3' and'b4' are obviously ok.

They are all aliases and they are all in some vague sense OK.

The key issue is not what aliases what, but what will go wrong when the
compiler assumes that two references do not alias a signle object when
in fact they do.  Your sketch has no cases where that is a problem (as
far as I can see) and I think such code is usually OK.

Do you have an example of something that someone has said is a problem
that is worrying you?

-- 
Ben.

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

#96048

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Do you have an example of something that someone has said is a problem
> that is worrying you?

I did some experiments (inspired by
http://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html),
sorry for the somewhat lengthy code following:

<test_alias.c>
#include <stddef.h>		/* size_t */
#include <stdint.h>		/* fixed-width integers */
#include <string.h>		/* memcpy */

struct foo
{
  uint16_t a;
};

struct bar
{
  uint16_t b;
};

struct base
{
  uint32_t b;
};

struct derived
{
  struct base base;
  uint32_t d;
};

struct more_derived
{
  struct derived base;
  uint32_t m;
};


uint32_t foobar1 (uint32_t v)
{
  uint16_t* const sp = (uint16_t*) &v;
  uint16_t hi = sp[0];
  uint16_t lo = sp[1];

  sp[1] = hi;
  sp[0] = lo;

  return v;
}

uint32_t foobar2 (uint32_t v)
{
  uint8_t tmp[2] = {};
  uint8_t* const b = (uint8_t*) &v;

  (void) memcpy (tmp, b + 2, 2);
  (void) memcpy (b + 2, b, 2);
  (void) memcpy (b, tmp, 2);

  return v;
}

void foobar3 (uint32_t* four, uint16_t* two, size_t len)
{
  size_t x;

  for (x = 0; x < len; ++x)
    {
      four[x] = ((uint32_t) *two) + x;
    }
}

void foobar4 (uint32_t* four, int32_t* ofour, size_t len)
{
  size_t x;

  for (x = 0; x < len; ++x)
    {
      four[x] = ((uint32_t) *ofour) + x;
    }
}

void foobar5 (struct foo* f, struct bar* b, size_t len)
{
  size_t x;

  for (x = 0; x < len; ++x)
    {
      f[x].a = b->b + x;
    }
}

void foobar6 (struct derived* d, struct base* b, size_t len)
{
  size_t x;

  for (x = 0; x < len; ++x)
    {
      *((uint32_t*) &d[x]) = b->b + x;
    }
}

void foobar7 (struct more_derived* m, struct base* b, size_t len)
{
  size_t x;

  for (x = 0; x < len; ++x)
    {
      *((uint32_t*) &m[x]) = b->b + x;
    }
}

void foobar8 (struct base* b, uint32_t* v, size_t len)
{
  size_t x;

  for (x = 0; x < len; ++x)
    {
      b[x].b = *v + x;
    }
}

void foobar9 (struct base* b, uint16_t* v, size_t len)
{
  size_t x;

  for (x = 0; x < len; ++x)
    {
      b[x].b = *v + x;
    }
}
</test_alias.c>

If you compile that code with (GCC 4.9 and CLANG 3.5):

gcc -g -fverbose-asm -Wall -m32 -fstrict-aliasing -O3 -S -o test_alias_32_O3.s test_alias.c
clang -g -fverbose-asm -Wall -m32 -fstrict-aliasing -O3 -S -o test_alias_clang_32_O3.s test_alias.c

than this results in the following:

- foobar1: v and b do not alias, although they probably could according
  to c99 6.5.7 (I guess strictly speaking it could just return v without
  doing anything else)

- foobar2: v and b do not alias and must not acc. to 6.5.7; it swaps
  words portably

Interestingly enough both compilers emit identical code for foobar1 and
foobar2 (NB: GCC emits good code, two fetches and three stores, but the
code produced by CLANG is impressive; I guess one cannot write faster
assembler code complying to x86 standard calling convention even
manually)

- foobar3: four and two alias; if they somewhere refer to the same
  stored value, results may not be, what you expect (nasal daemons etc.)

- foobar4: four and ofour do not alias as expected acc. to 6.5.7

- foobar5: f and b alias as expected acc. to 6.5.7

- foobar6: d and b do not alias as expected acc. to 6.5.7

- foobar7: m and b do not alias as expected acc. to 6.5.7

- foobar8: b and v do not alias as expected acc. to 6.5.7; note that
  struct base contains a member of type uint32_t

- foobar9: b and v alias as expected acc. to 6.5.7; no uint16_t in
  struct base

So my initial doubt about casting from base to derived and vice versa
not being reflexive in the standard was based on fallacy.  I guess it
does not matter how two pointers get their values, but the aliasing rule
in the standard just says that the compiler needs to assume that a
pointer to base and a pointer to derived might refer the same stored
value.


Thanks for your support,

Andreas

-- 
What do you mean? An African or a European swallow?

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

#96060

On Monday, November 7, 2016 at 5:25:40 PM UTC-6, Andreas wrote:
> - foobar1: v and b do not alias, although they probably could according
>   to c99 6.5.7 (I guess strictly speaking it could just return v without
>   doing anything else)

If a pointer p of type T is cast to another type the resulting pointer is
accessed, gcc will often recognize the access as modifying *p, but will
not recognize aliasing with any objects of type T that are accessed
elsewhere via other means.  As of 6.2, it will also in some cases omit
code generation for assignments in cases where the destination holds the
same bit pattern as the source, even if the assignment should force the
compiler to recognize an object as a different type (e.g. given:

	#include <stdint.h>

    union lll { long l; long long ll; };

    long testlll(long *lp, long long *llp, union lll *up)
    {
      long long t;
      if (*lp != 1234)
        return 1234;
      t=up->l;
      up->ll = t;
      *llp = 5;
      t=up->ll;
      up->l = t;
      return *lp;  
    }
    long testlll2(void)
    {
      union lll lv;
      lv.l=1234;
      return testlll(&lv.l, &lv.ll, &lv);
    }

gcc 6.2 will generate code for testlll2 that unconditionally returns 1234
even though the compiler should have no problem recognizing aliasing
in testlll between *lp and *up->l (since they're both the same type), nor
between *llp and *up->ll.  In this example, there is no type punning of
any form except in the compiler's imagination, but in both cases where
code writes to *up it reinterprets the value that was there as the new
type and observes that it matches the new value, thus omitting the write.

If you want to see whether gcc is properly recognizing aliasing, use code
more like the above.  Otherwise you may hit upon situations where it
happens to correctly recognize aliasing and reach false conclusions about
the cases where it actually will.

[Incidentally, I must begrudging praise gcc for at least being "honest"
in how it processes in-lining with examples like the above; if a function
won't recognize aliasing in the general case, gcc will generally not have
it recognize aliasing even if it is in-lined with arguments that are
conspicuously aliased.]

> - foobar3: four and two alias; if they somewhere refer to the same
>   stored value, results may not be, what you expect (nasal daemons etc.)

While it might be sensible for a compiler to assume that *two won't
alias *four, I see no justification for that in the Standard.  Of course,
if the intention is that a compiler not be required to recognize that a
pointer may alias other things, one may achieve that using "restrict".

> So my initial doubt about casting from base to derived and vice versa
> not being reflexive in the standard was based on fallacy.  I guess it
> does not matter how two pointers get their values, but the aliasing rule
> in the standard just says that the compiler needs to assume that a
> pointer to base and a pointer to derived might refer the same stored
> value.

Having derived types contain a structure of the base type will satisfy the
aliasing rules, but if the length of the common members is not a multiple
of their alignment, it might not satisfy layout requirements--especially if
code needs to communicate with a library that doesn't waste space in its
structures.

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

#95715

Andreas <nospam@invalid.invalid> wrote:
<snip>
> I find many references to this idiom, often asking whether the language
> standard supports it.  Unfortunately I can only find answers referring
> to the fact that the 'base' members above are guaranteed by C (and
> consequentially for PODs by C++) to have the same address as each value
> of their containing struct types.
> 
> That's fine but I believe that there is another aspect to be considered
> when using this idiom, namely aliasing.  Regarding this aspect I find
> the following reference in both C99 (I refer to draft N 1256) and C11
> (as of draft N 1570) in paragraph 6.5.7:
> 
> <quote N 1256>
> 
> An object shall have its stored value accessed only by an lvalue
> expression that has one of the following types:
> 
> ...
> 
> - an aggregate or union type that includes one of the aforementioned
> types among its members (including, recursively, a member of a
> subaggregate or contained union)
> 
> ...
> 
> </quote N 1256>
> 
> When using the idiom mentioned above it is often necessary to cast a
> pointer from a derived type to a base type (upcast) or vice (downcast).

I don't think I can provide any more clarity than what has been stated
elsethread, but perhaps this recent GCC regression and ensuing discussion
might help:

  https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71120

The GCC optimization bug shows how compilers are applying the aliasing
rules. Pay attention to not only what GCC was doing wrong, but to what it
was doing that wasn't wrong. Be sure to follow the link to the glibc issue
page, too.

I think the thing to keep in mind is that the rules are designed so that
compilers can track side-effects and, under heavy optimization, avoid
eliding operations that your code depends on. The most pertinent part of the
6.5p7 quote isn't "of the following types", but "shall have its stored value
accessed only by an [compatible] lvalue".

In the absence of the restrict qualifier, and without any other information,
compilers must assume that pointers might alias the same object. So if you
pass two pointers, a and b, to a function and cast them willy-nilly, as long
as the effective type of any lvalue expression, inside or outside of that
function, is the same as the preceding store, you're good. The issue is when
the compiler can prove (or thinks it can prove) that the pointers don't
alias (such as by proving that they couldn't alias in a well-defined
program) and then decides to elide some side-effect under license of the
as-if rule.

I'll abstain from providing a simpler example here because I'll probably get
some detail wrong and just add to the confusion.

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

#95769

On Thursday, November 3, 2016 at 8:55:29 PM UTC-5, > I think the thing to keep in mind is that the rules are designed so that
> compilers can track side-effects and, under heavy optimization, avoid
> eliding operations that your code depends on. The most pertinent part of the
> 6.5p7 quote isn't "of the following types", but "shall have its stored value
> accessed only by an [compatible] lvalue".

The present rules are a mess because the authors of the original standard
don't seem to have put much thought into the original rules beyond the idea
that a compilers given something like:

    float f;

    float test(int *p)
    {
      f = 23.0f;
      *p = 5;
      return f;
    }

shouldn't be required to make pessimistic aliasing assumptions about the
possibility of "p" aliasing "f".  If the authors of the original Standard
had given the matter more thought than that, they haven't produced any
evidence of it that I've seen.

C was in wide use before the Standard was written, and there was a
substantial corpus of code that uses forms of aliasing not provided for
in C89.  The authors of the C89 Standard, however said they wanted to
avoid making any breaking changes.  The only way I can see to reconcile
those viewpoints was that they expected compiler writers to behave as
though the Standard included a proviso that implementation authors should
also support other forms of aliasing which would be useful for the
implementations' target platform and intended application field.  To have
actually said such a thing could have been considered condescending, but
I can't imagine they expected that people wanting to write useful
implementations would do otherwise.

Note also, btw, that for the kinds of optimization that most compilers
would want to do in 1989 or 1999, it would be easy to achieve compatibility
with most code that relied upon aliasing, at relatively little cost in
efficiency, by adding one simple rule: flush all register-cached
variables of a given type whenever a pointer of that type is cast to any
other.  Such a rule would not be usefully applied to types which have
padding bits and trap representations such that no value written as an "int"
would be readable as "float", however, and the Standard does not tend to
mandate rules which make sense for some platforms but not others.

Later standards claim to merely be "clarifying" previous rules, but under
a presumption that no code would ever need to do anything which had been
provided as a result of near-unanimous judgment of compiler writers, rather
than mandated by the previous Standard.  If rules were being designed from
the ground up to allow vectorization, but with the intention that they
be sufficient to accommodate programmers' needs, they'd be very different.
There are many kinds of optimizations they'd allow which are presently
forbidden, but they'd also recognize more usable constructs than are
presently recognized (e.g. by providing a form of pointer declaration for
a pointer which can be used to interpret as an X, storage which might also
be holding a Y or Z).

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

#96136

William,

<william@wilbur.25thandClement.com> writes:

>   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71120

thanks for a very interesting read.  I've never had to use the POSIX
socket API directly in serious code, but the way it approaches
genericity made and makes me feel uncomfortable.

-- 
What do you mean? An African or a European swallow?

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

#95521

On 11/01/2016 08:15 AM, Andreas wrote:
> Hi all,
> 
> while searching the web I've found a lot of assertions that a common
> idiom of subtyping structs in C is well-defined by virtue of the first
> struct member always having the same address as the surrounding struct.
> What I'm concerned about is aliasing in this context.
> 
> struct sub_type
> {
>         uint8_t super_tag;
>         ...
> };
> 
> struct super_type
> {
>         struct sub_type super;
>         ...
> };
> 
> struct hyper_type
> {
>         struct super_type super;
>         ...
> };
> 
> void foo (struct sub_type* base)
> {
>         struct super_type* up = 0;
>         struct hyper_type* upper = 0;
>         if (base->super_tag == UP_ID)
>         {
>                 up = (struct super_type*) base; // *NOT aliasing!?*
>                 ...
>         }
>         else if (base->super_tag == UP_ID)
>         {
>                 upper = (struct hyper_type*) base; // *NOT aliasing!?*
>                 ...
>         }
>         ...
> }
> 
> void bar (struct super_type* up, struct hyper_type* upper)
> {
>         struct sub_type* base1 = (struct sub_type*) up; // *ALIASING?*
>         struct sub_type* base2 = (struct sub_type*) upper; // *ALIASING?*

Yes, it is guaranteed that "A pointer to a structure object, suitably
converted, points to its initial member (or if that member is a
bit-field, then to the unit in which it resides), and vice versa.".
(6.7.2.1p15). Technically, that means that you'd have to use (struct
sub_type*)(struct super_type*) co convert upper to base2. The standard
does NOT guarantee that this pair of conversions has the same effect as
the direct conversion to struct sub_type*. However, in practice, that's
unlikely to be problematic.

*base1 is now an alias for up.super, and *base2 is now an alias for
upper.super.super. This is not a problem in itself, but it is something
to be aware of.

>         struct sub_type* base1 = up.super;
>         struct sub_type* base2 = upper.super.super;

That code contains at least two errors on each line, possibly more, so
I'm not sure what was intended. It looks like you are defining two new
variables, base1 and base2, in the same scope where you've already
defined variables with those names. I see two possibilities: you
intended this as an alternative to the first pair of lines - in that
case, you should have used #if #else #endif to separate the two
alternatives. The other possibility is that you forgot to give these
variables new names, such as base3 and base4.

The next problem is that the initializers for those definitions have the
type "struct sub_type", while those variables have the type "struct
sub_type*". I suspect that there's a missing "&" after the "=" in each
of those definitions.

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

#95568

James,

thanks for your review, you are completely right: my original posting was
written both misleading and syntactically wrong, i.e. very careless;
please consider my followup to Ben's response.  I hope I have got it
right this time ...

-- 
What do you mean? An African or a European swallow?

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

#97197 — "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs]

Andreas:

>Hi all,
>
>while  searching the web I've found a lot of asser-
>tions that a common idiom of subtyping structs in C
>is  well-defined by virtue of the first struct mem-
>ber always having the same address as the surround-
>ing  struct.   What I'm concerned about is aliasing
>in this context.
>
>struct sub_type
>{
>        uint8_t super_tag;
>        ...
>};
>
>struct super_type
>{
>        struct sub_type super;
>        ...
>};
>
>struct hyper_type
>{
>        struct super_type super;
>        ...
>};
>[...]

Am I right in thinking  that  "Object-oriented  pro-
gramming in C":

      http://www.cs.rit.edu/~ats/books/ooc.pdf

is  based entirely on the violation of strict alias-
ing?

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

#97207 — Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs]

On Monday, November 21, 2016 at 7:59:35 AM UTC-6, Anton Shepelev wrote:
> Am I right in thinking  that  "Object-oriented  pro-
> gramming in C":
> 
>       http://www.cs.rit.edu/~ats/books/ooc.pdf
> 
> is  based entirely on the violation of strict alias-
> ing?

That book goes to some extra lengths to comply with the aliasing rules,
which can sometimes make structure layouts less efficient than it would
otherwise be.  If one wants to have some structures whose header's size
isn't a multiple of the alignment, then in Ritchie's language one could
write the code as e.g. :

    struct header { void *info; uint16_t flags };
    struct thing1 { void *info; uint16_t flags;
                    uint16_t coords[3]; };
    struct thing2 { void *info, uint16_t flags;
                    uint8_t label[7]; uint32_t dat[]};

and cast pointers to either thing1 or thing2 into pointers of type header.
The approach exemplified by the book, however, would make thing1 and thing2
each contain a field of type "struct header", thus increasing the size of
those structures thing1 and thing2 by 8 bytes each [a 50% increase in the
case of thing1].

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

#97211 — Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs]

On 11/21/2016 08:59 AM, Anton Shepelev wrote:
> Andreas:
>
>> Hi all,
>>
>> while  searching the web I've found a lot of asser-
>> tions that a common idiom of subtyping structs in C
>> is  well-defined by virtue of the first struct mem-
>> ber always having the same address as the surround-
>> ing  struct.   What I'm concerned about is aliasing
>> in this context.
>>
>> struct sub_type
>> {
>>        uint8_t super_tag;
>>        ...
>> };
>>
>> struct super_type
>> {
>>        struct sub_type super;
>>        ...
>> };
>>
>> struct hyper_type
>> {
>>        struct super_type super;
>>        ...
>> };
>> [...]
>
> Am I right in thinking  that  "Object-oriented  pro-
> gramming in C":
>
>       http://www.cs.rit.edu/~ats/books/ooc.pdf
>
> is  based entirely on the violation of strict alias-
> ing?

I don't have time to read that entire document right now. Could you cite 
a particular page that involves such violations? I know that the general 
concept of "object-oriented programming in C" (as opposed to the book of 
that title) does not rely violation of C's aliasing rules.

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

#97216 — Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs]

On Monday, November 21, 2016 at 10:15:56 AM UTC-6, James R. Kuyper wrote:
> I don't have time to read that entire document right now. Could you cite 
> a particular page that involves such violations? I know that the general 
> concept of "object-oriented programming in C" (as opposed to the book of 
> that title) does not rely violation of C's aliasing rules.

Object-oriented code targeting compilers which impose looser rules than what
the Standard would allow can sometimes be written in more efficient or
readable fashion than code which abides gcc's interpretation of the Standard.
Among other things, if one has an array of pointers which are all going to
target things of derived type, but will needs to be able to pass it to a
function which expects an array of base-type pointers, the Standard would
require that the function either accept a pointer of the header type or
void*, and that the type of the array match that choice.  All code which
needs to use the array as the derived type would then have to explicitly cast
its contents at every use.

Despite C's reputation for flexible pointer semantics, even Java has far more
flexible semantics here than what C supports, since Java allows a function
which expects a reference to an array of references to Animal to be given
a reference to an array of references to Cat, provided that it doesn't try
to store a reference to something that isn't a Cat (or subtype thereof) into
the array.

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

#97229 — Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs]

supercat:

>Despite  C's reputation for flexible pointer seman-
>tics, even Java has  far  more  flexible  semantics
>here  than  what  C  supports,  since Java allows a
>function which expects a reference to an  array  of
>references  to Animal to be given a reference to an
>array  of  references  to  Cat,  provided  that  it
>doesn't  try to store a reference to something that
>isn't a Cat (or subtype thereof) into the array.

Covariance of collection elements, or of  array  el-
emetns  in your example, is a relatevely new feature
in computer languages.  Did any  classic  procedural
languages have it?

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

#97265 — Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs]

On Tuesday, November 22, 2016 at 2:42:39 AM UTC-6, Anton Shepelev wrote:
> Covariance of collection elements, or of  array  el-
> emetns  in your example, is a relatevely new feature
> in computer languages.  Did any  classic  procedural
> languages have it?

C74 could certainly handle such constructs without any difficulty whatsoever.
I'm not sure when or whether it was deliberately removed from the language,
but it's very clear that C74 supported such things, and today's compilers do
not.

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

#97280 — Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs]

supercat@casperkitty.com writes:
<snip>
> C74

What's that?  Do you have a reference for it?

-- 
Ben.

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

#97303 — Re: "Object-oriented programming in C" [was: Re: Aliasing and subtyping structs]

On Tuesday, November 22, 2016 at 10:07:39 AM UTC-6, Ben Bacarisse wrote:
> supercat writes:
> <snip>
> > C74
> 
> What's that?  Do you have a reference for it?

Sorry--I thought you'd seen other posts where I've used the term previously
as an informal name for the language described by the 1974 C Reference
Manual.

See https://www.bell-labs.com/usr/dmr/www/cman.pdf paying particular
attention to 7.1.7 and 7.1.8 which make it abundantly clear that given:

    struct s1 {double foo; int bar; int baz;};
    struct s2 {double foo; int bar; float woozle; };

the types "struct s1*" and "struct s2*" may be used interchangeably by code
which only needed to access "foo" and "bar".  The lack of any type checking
at all wasn't a good thing, but it was clearly possible to write functions
that could operate on objects of either type, pointers to either type, or
arrays of pointers to either type, without having to care about the exact
structure type in question.

The fact that later versions of the language would require casts when
converting between the two pointer types does not imply that there would
need to have been any problem allowing code which uses such casts to
achieve the same semantics as had been possible under C74.  What is not
clear is whether the removal of such semantics from the language was
deliberate, or if the Committee expected that the Common Initial Sequence
rule was sufficient to express the intent that such semantics remain
available, and that compiler writers would recognize the usefulness of
related aspects whether or not the Standard identified them all.

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web