504316 - inspect all unions of pointers for type-punning safety

Status: RESOLVED FIXED

(Tamarin Graveyard :: Virtual Machine, defect, P5)

Description

[Edwin Smith]

The section on "Casting through a union (3)" in this document
http://www.cellperformance.com/mike_acton/2006/06/understanding_strict_aliasing.html

describes an unsafe practice that we've used in several places in tamarin-redux.  At the time of this bug, "grep union" returns 128 hits in 53 files, which is a tractable number of sites to manually inspect and fix if necessary.

gcc 4.3.2 -O3 on Ubuntu is known to problems in manually written examples such as this one:

#include <stdio.h>

int main(int argc, char** argv)
{
    union {
        int *c;
        double *d;
    };
    int bytes[2];
    c = bytes;
    c[0] = 37;
    *d = 3.14159;
    printf("%d\n", c[0]); // 110 on gcc 4.0.1 on mac, 37 on gcc 4.3.2 on linux
}

List of possible sites to be added as a comment in this bug.

Comment 1

[Jeff Dyer]

Attachment: fix to one instance, which broke the unix frr build

Comment 2

[Steven Johnson]

Comment on attachment 391484 [details] [diff] [review]
fix to one instance, which broke the unix frr build

pushed as changeset:   2273:0d7b931de251

Comment 3

[Steven Johnson]

Attachment: proper dict fix

previous fix to diff was totally wrong and crashy -- I am ashamed to have review+'ed it

proper fix enclosed (I hope)

Comment 4

[Steven Johnson]

Comment on attachment 391506 [details] [diff] [review]
proper dict fix

pushed as changeset:   2277:f63f68db0129

Comment 5

[Steven Johnson]

Attachment: Partial fix

This patch attempts to fix a lot of the suspect unions, and flags a few more that I am unsure about (or lack the time to test properly at this time). Referencing the same article at cellperformance.com, these fixes follow "Casting through a union (2)" -- "Casting proper may be done between a pointer to a type and a pointer to an aggregate or union type which contains a member of a compatible type"; if I understand this correctly, the revised usages should be in compliance with strict aliasing requirements.

That said -- more work is probably needed here: the items flagged above need to be revisited, and there are probably other strict-aliasing-unsafe items (both union and not) that need attention.

Comment 6

[Lars T Hansen]

I don't think this change is right in the sense that it doesn't fix anything that may or may not be broken.  Consider the new body of AllocDouble:

{
 char* const c = (char*)GetGC()->AllocDouble();
 union U_char_double { char c; double d; } * const u = (U_char_double*)c;
 u->d = n;
 return kDoubleType | (uintptr_t)u;
}

I fail to understand why this is not in every way equivalent to this:

{
 double* d = (double*)GetGC()->AllocDouble();
 *d = n;
 return kDoubleType | (uintptr_t)d;
}

Why?  Because the "char* c" is nowhere exposed to calling code, so there's no aliasing between c and d possible.  Any aliasing problem could occur later, when the atom is cast to different pointer types and updated and read through pointers of different types.  But once u or d is cast to uintptr_t the origins of the value are lost; the union ceases to have any effect at all.  This should be true even taking inlining and optimization into account.

Comment 7

[Lars T Hansen]

Comment on attachment 391743 [details] [diff] [review]
Partial fix

Removing self from review; I think it needs more work but I won't be here for it.

Comment 8

[Edwin Smith]

Comment on attachment 391743 [details] [diff] [review]
Partial fix

we should split this up into smaller pieces and at least fix AllocDouble as Lars describes -- digging deeper, its not even clear (to me anyway) why GC::AllocDouble even returns void*... why not cast to double* immediately after Alloc, which of course is safe?

Comment 9

[Mike Morearty]

+1 on everything Lars said in comment 6.

(For the record, the URL of the article mentioned in comment 1 has changed: It is now http://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html )

In fact, although I haven't read through all of the unions in the code, I would argue that:

(1) Most of them do NOT have any strict-aliasing risk.  (The few I've looked at that were in Steven's patch did not have any such risk, IMO.)

(2) Despite this, it would still be worthwhile changing them from unions to casts (as Lars did in his comment), because code with the cast is easier to understand.  To reiterate, if we changed them, it would be for clarity reasons, not for safety reasons.

To explain what I mean by (1): The key risk with aliasing is that you shouldn't assume that writing to *p1 will change the data at *p2.  When a compiler is assuming strict aliasing, it is free to decide that a write to *p1 can't touch the memory at *p2, and optimize the code based on that assumption.

So:

- In Ed's example in comment 1, both *c and *d are written to, thus there is a risk.
- In the section "Casting Through a Union (3)" in the above-linked article, the code assumes that writing to *sp will cause *wp to be modified, thus there is a risk.

But here are some examples of code that do not, as far as I can tell, have any strict-aliasing risk:

- The original allocDouble function, although somewhat hard to read, is safe:

REALLY_INLINE Atom allocDouble(double n)
{
    union { 
        double *d;
        void *v;
    };
    v = GetGC()->AllocDouble();
    *d = n;
    return kDoubleType | (uintptr)v;
}

This code assumes, correctly, that assigning a value to v will cause the value of d to change; but it does not assume that assigning a value to *v (if such a thing were possible) would change the value of *d, or vice versa.

The proposed rewrite in attachment 391743 [details] [diff] [review] is also safe, but is no better, and IMO is still hard to read; Lars's rewrite is also safe, and is easier to read.

- The original function write<T>() in Sampler.cpp is, similarly, hard to read but safe:

template<class T>
static void inline write(uint8_t*& p, T u)
{
    union Foo {
        uint8_t* p8;
        T* pT;
    };
    Foo foo;
    foo.p8 = p;
    *foo.pT = u;
    p += sizeof(T);
}

Again, the code assumes that assigning a value to p8 causes the value of pT to change, but makes no assumption that writing to *p8 changes *pT, or vice versa.

And again, the proposed rewrite in attachment 391743 [details] [diff] [review] is safe but no better -- in fact, I'd say it is more confusing, because it is using a union for no reason (U.u is never accessed):

template<class T>
static void inline write(uint8_t*& p, T t)
{
    union U { uint8_t u; T t; } * const u = (U*)(p);
    u->t = t;
    p += sizeof(T);
}

A better rewrite, IMO -- and this rewrite is only for clarity, not for safety -- would be this:

template<class T>
static void inline write(uint8_t*& p, T t)
{
    *(T*)p = t;
    p += sizeof(T);
}

(Or use reinterpret_cast if you prefer.)

Comment 10

[Mike Morearty]

BTW, when I said that I suspect most of our unions do not have any aliasing risk, I didn't mean to imply that this bug is invalid -- it is worthwhile to check them all, because there may be some that are unsafe.

Comment 11

[Mike Morearty]

Attachment: Patch for FileClass::read()

I read through all the unions in tamarin-redux, and almost all of them appear to me to be safe.  The only two that worry me are:

1. nanojit/CodeAlloc.h, line 77:

union {
    // this union is used in leu of pointer punning in code
    // the end of this block is always the address of the next higher block
    CodeList* higher;   // adjacent block at higher address
    NIns* end;          // points just past the end
};

I'm pretty sure all the uses of this are safe, but it's sort of hard to tell.  Someone who is more familiar with that code should probably take a look.

2. shell/FileClass.cpp, line 99:

union {
    uint8_t* c;
    wchar* c_w;
};

This is the only one that looks to me like it might have a real risk of aliasing problems, because the code writes to *c, and then passes c_w to a function that is going to read from *c_w.  I'm not 100% sure, but I think this might run into trouble with a highly optimizing compiler.  I've attached a patch.

Comment 12

[Lars T Hansen]

Comment on attachment 433115 [details] [diff] [review]
Patch for FileClass::read()

R+ on the change in general, with the following comment: Why are you using reinterpret_cast one place and a C cast, which if I'm not mistaken is equivalent to a reinterpret_cast, another place?

Comment 13

[Mike Morearty]

Good question -- there's no good reason.  I first wrote the code with just traditional casts, and then later, looking at the second cast, I thought, "Hmm, maybe I'll change that to a reinterpret_cast, that might be cleaner" -- but didn't notice that another part of my patch was still using a C cast.

Comment 14

[Edwin Smith]

if they really are equivalent, my eyes are happier parsing C style casts.

Comment 15

[Mike Morearty]

Attachment: Patch for FileClass::read()

Comment 16

[Mike Morearty]

Comment on attachment 433375 [details] [diff] [review]
Patch for FileClass::read()

Fair enough -- created a new patch that uses a C cast instead of reinterpret_cast.

(The only difference between a C cast and a reinterpret_cast is that reinterpret_cast won't let you cast away const or volatile; it makes the code more explicit about the fact that you are reinterpreting a value but not trying to change its const or volatile attributes.  But I agree, it's harder to look at.)

Comment 17

[Lars T Hansen]

(In reply to comment #14)
> if they really are equivalent, my eyes are happier parsing C style casts.

I'm the other way around -- C style casts are inherently dangerous and really should not be used anywhere -- but I'm paranoid about random compiler X not handling the C++ style casts...

Comment 18

[Mike Morearty]

Pushed attachment 433375 [details] [diff] [review] to tamarin-redux as changeset 4127:adf2c74df504, to fix FileClass::read()

Comment 19

[Mike Morearty]

Attachment: Patch for ByteArrayObject::_toString()

Found another case of pointer aliasing in ByteArrayObject::_toString(), essentially identical to the one I just fixed in FileClass::read().  I don't know why I didn't see this one during my previous check of all unions -- I should have caught it then.  In any case, the fix is essentially identical to the fix for FileClass::read().

Comment 20

[Mike Morearty]

Pushed attachment 434355 [details] [diff] [review] to tamarin-redux as changeset 4140:ddfdeeab9d49, to fix ByteArrayObject::_toString()

Comment 21

[Dan Smith]

Orphan bug that appears closed, marking so.