NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/std/c/3313

Text File | 1993-01-02 | 6.3 KB | 152 lines

Newsgroups: comp.std.c
Path: sparky!uunet!uunet.ca!wildcan!sq!msb
From: [e-mail] (Mark Brader)
Subject: Re: Struct hack one last time (one last time)
Message-ID: <[e-mail]>
Summary: Where last element not char, legal only if special arrangements made
Organization: SoftQuad Inc., Toronto, Canada
References: <[e-mail]> <[e-mail]>
Date: Sat, 2 Jan 93 07:29:08 GMT
Lines: 140

> > [Is] the notorious "struct hack" was still conformant if the tail array
> > in the struct [is] of type other than char[?] ... My reading of the
> > earlier thread on this topic was that the hack was indeed legal, but
> > all the previous examples used an array of char in their examples.
> > Thus, is there any reason it would not be legal to declare:
> >    struct vector {
> >        int  size;
> >        double v[1];
> >    } *vec;
> > and then code (for example):
> >    vec = malloc(sizeof(struct vector) + (n - 1) * sizeof(double));
> >    vec->size = n;
> >    for ( i = 0;  i < vec->size;  i++ )  vec->v[i] = 0.0;

I will assume for brevity that n > 1 in the above code.  Also, I assume
that "legal" means "can occur and be executed in a strictly conforming
ANSI C program".

I previously believed that this code was indeed legal, but I have lately
come to the opposite opinion.  Return to the classic struct hack:

    struct hack /* well, what else? */ {
        int len;
        char arr[1];
    } *p;
    p = malloc(sizeof(struct hack) + n-1);  /* where n > 1 */

In this, access to p->arr[1] is legal because p->arr decays to a
pointer which points to some element of the object returned by
malloc -- you can identify which one by using offsetof -- and
the pointer p->arr+1 also points to some element of this object,
thus meeting the requirement specified by 3.3.6/6.3.6.

(The people who still think it's not legal are either taking the point
of view that that section should be interpreted to mean something
other than what it says, or are confused.  If they want to disagree
with the above statement, they are asked to change the Subject line
to "legality of struct hack", to distinguish it from this thread.
I'll ignore any posting that doesn't add something new to the extensive
and rather repetitive previous discussions of the topic.)

In the other example using double, we still know that the pointer
obtained by decay of vec->v points to a double which is somewhere
within the object returned by the malloc(), but we do NOT know that it
points to a double that would be an element of that object if we viewed
it as an array of doubles.  And this distinction, I fear, is critical.

To make the example more specific, let's add these lines in the
obvious places:

    double *dp;
and
    dp = (void *)vec;

Now (void *)vec is the same as the pointer returned by malloc(),
so dp now contains a pointer to what is the first element of the
object that the malloc() returned, if that object is viewed as an
array of doubles.  Now suppose that sizeof(int) < sizeof(double).

If the implementation insists that doubles must be aligned on
multiples of sizeof(double) bytes, then offsetof(struct vec, v)
will be sizeof(double), and the pointer decayed from vec->v will
be equal to dp+1.  Then vec->v[1] is the same as dp[2], all
references are within the object returned by malloc() viewed as
an array of doubles, and all is well.

But if the implementation allows *any* alignment of doubles, then
vec->v will not be equal to dp or dp+1; instead, it will point to
an object overlapping the objects that dp and dp+1 point to.
The access to vec->v[1] is legal only if vec->v[0] and vec->v[1]
are both elements of some array.  The arguments given earlier
completely fail in this case, since the array to whose first
argument dp points is useless for this purpose.  So we are left
with only the array vec->v, which is too short to help.  Ergo,
the code is not legal after all.

I believe it would become legal if the struct was designed in such
a way that offsetof(struct vec,v) % sizeof(double) was known to be 0.

3.5.2.1/6.5.2.1 says that padding may be inserted in a struct
"as necessary to achieve the appropriate alignment".  I interpret
this in such a way as to believe that the following redefinition
of the struct would render the code legal:

    /* Divide a by b, rounding any fraction upward.
       Both numbers assumed to be positive. */
    #define DIVRUP(a,b)    (((a)+(b)-1) / (b))

    struct template
    {
        union {
            int    size;
            double    align[DIVRUP(sizeof(int),sizeof(double))];
        } u;
        double    v[1];
    };

Of course, vec->size has to become vec->u.size.  Other tricks also
exist that could be used to obtain the same alignment knowledge instead,
but all the ones I can think of have some similar ugliness.


> I don't see that the type of the array makes any difference.

It matters because objects are made up of bytes, which are the same as
chars, and therefore if an object is viewed as an array of chars (as
the object returned by malloc() may be viewed), then any pointer which
points into the middle of that object points to one of its elements;
but this is not true for larger types than char.

> I do believe that the hack is not strictly conforming, however, since
> you would be using array indices outside the declared array bounds
> (char or double makes no difference).  The results of doing so are
> undefined.

The declared array is irrelevant; see above.

> I have thought of a plausible implementation where the struct hack
> would fail, however.
>
> An implementation is allowed to add padding to the end of a struct.

An implementation is allowed to add padding to the end of a struct
(or union) "as necessary to achieve the appropriate alignment were
the structure or union to be a member of an array"; no license is
given to insert padding for other reasons.

> Suppose that the implementation adds space to the end of each struct
> type where it encodes information used for run-time error checking.
> The struct hack would fail in this case, since it would overwrite data
> used by the run-time system.  I believe the implementation would still
> be conforming, since we are in the arena of undefined behavior.

On the contrary, since the struct hack is legal (conforming), such an
implementation must be illegal (non-conforming).
--
Mark Brader, SoftQuad Inc., Toronto    "Constrain your data early and often."
utzoo!sq!msb, [e-mail]             -- C. M. Sperberg-McQueen

This article is in the public domain.