Page MenuHomePhabricator

[RFC] Implementation of Clang randstruct
Needs RevisionPublic

Authored by connorkuehl on Mar 12 2019, 7:42 AM.

Details

Summary

This patch set is the draft of the code that accompanies our RFC located here: http://lists.llvm.org/pipermail/cfe-dev/2019-March/061607.html

Event Timeline

connorkuehl created this revision.Mar 12 2019, 7:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 12 2019, 7:42 AM
connorkuehl edited the summary of this revision. (Show Details)Mar 12 2019, 8:08 AM
connorkuehl added inline comments.
clang/lib/AST/DeclBase.cpp
1262

Apologies that this is included. I've left a comment on clang/lib/AST/RecordFieldReorganizer.cpp describing our issues with this code. I also mention experimenting with fixing it in that comment as well, and in those experiments we've been able to remove this change from BuildDeclChain. We're just waiting for further advice before we change the code too rapidly.

clang/lib/AST/RecordFieldReorganizer.cpp
58

This part of the code where we rebuild the new DeclChain with the new order of fields is resulting in a Clang compiler that segfaults when building the Linux kernel.

Any advice with how we can safely manage the DeclContext field chain is greatly appreciated here.

In our experimentation (which isn't present in this diff here) we thought our best bet to was to save the LastDecl's next pointer before BuildDeclChain is called and then we set the NEW LastDecl's next pointer to it in an effort to preserve whatever context chaining is happening.

Truthfully, we don't fully understand the machinery of the DeclContext or why our assumptions about this linked list of fields are incorrect.

More troubleshooting information regarding this particular instance is on our github issue: https://github.com/clang-randstruct/llvm-project/issues/42

rsmith added a reviewer: kcc.Mar 12 2019, 1:29 PM
pcc added a subscriber: pcc.Mar 12 2019, 1:55 PM

This needs a test under test/CodeGen at least.

clang/include/clang/AST/RecordFieldReorganizer.h
54

I don't think we can use default_random_engine for this because the behaviour would need to be consistent between C++ standard library implementations, and the behaviour of default_random_engine is implementation defined. Similarly, I don't think that we can use std::shuffle (see note in https://en.cppreference.com/w/cpp/algorithm/random_shuffle ).

In D59254#1426809, @pcc wrote:

This needs a test under test/CodeGen at least.

Will do, thank you!

connorkuehl added inline comments.Mar 13 2019, 7:25 AM
clang/include/clang/AST/RecordFieldReorganizer.h
54

Sure thing, we'll begin investigating alternatives.

timpugh added inline comments.Mar 13 2019, 8:16 PM
clang/include/clang/AST/RecordFieldReorganizer.h
54

@pcc if we were to swap default_random_engine for a pre-defined random generator such as mt19937_64 would this suffice? It is included in the random number library.

https://en.cppreference.com/w/cpp/numeric/random

clang/include/clang/AST/RecordFieldReorganizer.h
54

In that case the random numbers would be deterministic; however, std::shuffle would still vary by implementation (as mentioned in the note Peter linked to.) A quick search didn't reveal a deterministic shuffle in the LLVM code so you may have to implement one.

jfb added a subscriber: jfb.Mar 14 2019, 8:59 AM
jfb requested changes to this revision.Mar 14 2019, 9:22 AM

I find it easier to understand the code by looking at the tests. When you add tests, please make sure you test for:

  • Alignment attribute
  • Packed attribute
  • No unique address attribute
  • Bit-fields
  • Zero-width bit-field
  • Zero or unsized array at end of struct
  • C++ inheritance with vtables
  • C++ virtual inheritance
  • Anonymous unions (and the anonymous struct extension)
  • Types with common initial sequence

I assume you only change field location, not their constructor's call order? i.e. class S { std::string a, b; }; always constructs a before b, but might reorder them.

There are cases where a developer could observe the difference in field order. For example, bit_cast or memcpy of a type which got reordered. What are the gotchas? Can you diagnose them?

clang/include/clang/AST/RandstructSeed.h
1

This file needs the standard license comment.

6

Returning a string is weird, and so it extern stuff. Is randomness a property of something in particular? Seems like Module or something similar might be the right place.

clang/include/clang/AST/RecordFieldReorganizer.h
54

Module::createRNG was created to support randomization of things. You should look at the discussion that led to its addition: in parts it tries to offer stable output when it can, and the idea was that you could inject a seed if you wanted to.

Unfortunately the other randomization patches weren't committed, but they're also on Phabricator.

clang/include/clang/Basic/AttrDocs.td
4161

I'm not sure you need to document what happens when both are present. If people do it the message they get should be sufficient.

clang/lib/AST/RecordFieldReorganizer.cpp
95

https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size will provide this. I have an RFC on how to implement it, haven't gotten to it. Just leave a FIXME. 64 is the right value, we all know ;-)

This revision now requires changes to proceed.Mar 14 2019, 9:22 AM
daloni added a subscriber: daloni.May 30 2019, 2:22 AM
shawnl added a subscriber: shawnl.Jun 16 2019, 12:16 PM
jfb added a comment.Jul 1 2019, 9:09 PM

Do you intend on moving this forward? It seems like a Good Thing overall, and I'd love to help review some more.

In D59254#1565961, @jfb wrote:

Do you intend on moving this forward? It seems like a Good Thing overall, and I'd love to help review some more.

Yes. I'm sorry it's been in limbo so long. I haven't touched base with the rest of my team so I can't speak for them, but I'm interested in moving this along. I've been busy settling into work and post-university life lately.

From your initial review it sounds like there's quite a bit to be done by way of providing sufficient test coverage for this and some code cleanup. A few other kind contributors have left us advice on our github repo for some blocking issues with designated initializers.

I'll be reviewing all the advice we've been given here and on our repo and figuring out the best way to start making progress on this again. There's definitely a good basis here.

That said, I'm still interested in and would appreciate any advice or pointers to resources. I don't suppose there's an LLVM/Clang mentorship type program?

shawnl added a comment.EditedJul 2 2019, 7:54 AM

I think the essential functionality of this patch should be in LLVM and not Clang, so that all front-ends can benefit. Too many generally useful things are in Clang when they should be in LLVM (e.g. C ABI for ARM and x86; ranged switch statements). I opened an upstream bug to discuss this. https://github.com/clang-randstruct/llvm-project/issues/52

jfb added a comment.Jul 2 2019, 9:09 AM

I think the essential functionality of this patch should be in LLVM and not Clang, so that all front-ends can benefit. Too many generally useful things are in Clang when they should be in LLVM (e.g. C ABI for ARM and x86; ranged switch statements). I opened an upstream bug to discuss this. https://github.com/clang-randstruct/llvm-project/issues/52

C and C++ layout decisions definitely belong in clang, not in LLVM. There might be opportunity to opt certain structures into re-layout through attributes, but generally speaking most of it needs to stay in clang.

My point is that most languages these days that intend to be compiled to machine code want compatibility with the C ABI, and randstruct will be part of that (and can be made compatible between languages by sharing the seed). LLVM knows what a struct is.

jfb added a comment.Jul 2 2019, 10:49 AM

My point is that most languages these days that intend to be compiled to machine code want compatibility with the C ABI, and randstruct will be part of that (and can be made compatible between languages by sharing the seed). LLVM knows what a struct is.

Basic stuff, sure LLVM can know about and move fields around, especially if clang slaps an attribute on the struct saying it's fine.

However, struct layout is deeply ingrained in code generation. Too deeply to just move it to LLVM. Consider this simple example:

template <int Size>
struct Arr {
    int arr[Size];
};

struct A { int a, b, c; char d, e, f, g; };

Arr<__builtin_offsetof(A, d)> arr;

There's way more complex stuff that falls out of how C and C++ specify the language. That complexity really shouldn't be in scope for this patch.

In D59254#1429401, @jfb wrote:

I find it easier to understand the code by looking at the tests. When you add tests, please make sure you test for:

  • Bit-fields
  • Zero-width bit-field

Hi JF,

Could you elaborate on what I should be testing for here regarding the zero-width bit-field? I'm not sure zero-width bit-fields are a concern since I think they're illegal. I just tried compiling a "hello world" program with a struct that has a zero width bit-field as one of its members and the compiler emitted an error pointing at it.

error: named bit-field 'z' has zero width
        int z : 0;
            ^
1 error generated.

For regular bit-fields the current implementation will keep adjacent bit-fields together and will preserve their original order but the overall group of adjacent bit-fields may relocate. My next revision will have a unit test describing and testing this behavior.