[RFC] Implementation of Clang randstruct

[connorkuehl]

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

[connorkuehl]

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

[pcc]

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

[connorkuehl]

In D59254#1426809, @pcc wrote:

This needs a test under test/CodeGen at least.

Will do, thank you!

[connorkuehl]

clang/include/clang/AST/RecordFieldReorganizer.h

54

Sure thing, we'll begin investigating alternatives.

[timpugh]

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

[vlad.tsyrklevich]

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]

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

[jfb]

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

[connorkuehl]

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]

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]

In D59254#1566711, @shawnl wrote:

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.

[shawnl]

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]

In D59254#1566895, @shawnl wrote:

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.

[connorkuehl]

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.

[xbolva00]

Re-ping

[connorkuehl]

In D59254#1792068, @xbolva00 wrote:

Re-ping

Still under development here: https://github.com/connorkuehl/llvm-project/tree/randstruct

[void]

In D59254#1792134, @connorkuehl wrote:

In D59254#1792068, @xbolva00 wrote:

Re-ping

Still under development here: https://github.com/connorkuehl/llvm-project/tree/randstruct

Hi @connorkuehl,

I was asked by @kees to take a look at implementing this, with the view to support it in the Linux kernel. There doesn't seem to have been a lot of work on this recently. Is it effectively in limbo at the moment?

[connorkuehl]

In D59254#3298184, @void wrote:

In D59254#1792134, @connorkuehl wrote:

In D59254#1792068, @xbolva00 wrote:

Re-ping

Still under development here: https://github.com/connorkuehl/llvm-project/tree/randstruct

Hi @connorkuehl,

I was asked by @kees to take a look at implementing this, with the view to support it in the Linux kernel. There doesn't seem to have been a lot of work on this recently. Is it effectively in limbo at the moment?

@void Cool! Yeah, I haven't done anything with this. The git tree in the quoted comment (https://github.com/connorkuehl/llvm-project/tree/randstruct) does have a lot more progress compared to this Phabricator submission in terms of some bug fixes and unit test coverage, though there's still room for improvement in terms of performance (and possibly correctness, iirc compiling Linux segfaulted Clang with those patches). Furthermore, the patchset is quite old, so I would be entirely shocked if it applied without much fuss on a recent LLVM tree. As you can see, the latest commit was in late 2019.

Best of luck! I hope at least some of it is helpful to you.

[Dan]

Hi @void, @connorkuehl

Reminding that I also participated in working on this, and back then in 2019 I did manage to compile and boot a working Linux kernel with this feature enabled in Clang. It was a fully built Fedora Linux 5.3 kernel. I remember though that @connorkuehl made various cleanups and refactoring following from my branch, but work stopped at some point and I don't remember at what state we left it it exactly.. :(

This is the Fedora Copr repo with the kernel RPM and all the LLVM/Clang package sources that used to build it: https://copr.fedorainfracloud.org/coprs/alonid/llvm-experimental

As for LLVM source, the git branch which was used back then is randstruct-demo-fc30 in my Github fork - https://github.com/da-x/llvm-project/

[void]

In D59254#3299150, @Dan wrote:

Hi @void, @connorkuehl

Reminding that I also participated in working on this, and back then in 2019 I did manage to compile and boot a working Linux kernel with this feature enabled in Clang. It was a fully built Fedora Linux 5.3 kernel. I remember though that @connorkuehl made various cleanups and refactoring following from my branch, but work stopped at some point and I don't remember at what state we left it it exactly.. :(

This is the Fedora Copr repo with the kernel RPM and all the LLVM/Clang package sources that used to build it: https://copr.fedorainfracloud.org/coprs/alonid/llvm-experimental

As for LLVM source, the git branch which was used back then is randstruct-demo-fc30 in my Github fork - https://github.com/da-x/llvm-project/

Thanks, @Dan and @connorkuehl!

I cherry-picked Connor's changes to top-of-tree LLVM. It wasn't too bad. I'll see how it works with the current Linux kernel. @jfb mentioned some really good issues having to do with C++. Because of how horrible it would be to support C++, I propose restricting this feature to C (probably a decision that's already been made).

clang/include/clang/AST/Decl.h

 class FunctionTemplateDecl;
 class FunctionTemplateSpecializationInfo;
 class LabelStmt;
 class MemberSpecializationInfo;
 class Module;
 class NamespaceDecl;
 class ParmVarDecl;
 class RecordDecl;
+class RecordFieldReorganizer;
 class Stmt;
 class StringLiteral;
 class TagDecl;
 class TemplateArgumentList;
 class TemplateArgumentListInfo;
 class TemplateParameterList;
 class TypeAliasTemplateDecl;
 class TypeLoc;

clang/include/clang/AST/DeclBase.h

 class DeclContext {
   /// For makeDeclVisibleInContextImpl
   friend class ASTDeclReader;
   /// For reconcileExternalVisibleStorage, CreateStoredDeclsMap,
   /// hasNeedToReconcileExternalVisibleStorage
   friend class ExternalASTSource;
   /// For CreateStoredDeclsMap
   friend class DependentDiagnostic;
+  /// For fine-grained control of field order
+  friend class RecordFieldReorganizer;
   /// For hasNeedToReconcileExternalVisibleStorage,
   /// hasLazyLocalLexicalLookups, hasLazyExternalLexicalLookups
   friend class ASTWriter;
 
   // We use uint64_t in the bit-fields below since some bit-fields
   // cross the unsigned boundary and this breaks the packing.
 
   /// Stores the bits used by DeclContext.

clang/include/clang/AST/RandstructSeed.h

+#ifndef RANDSTRUCTSEED_H
+#define RANDSTRUCTSEED_H
+#include <string>
+namespace clang {
+extern std::string RandstructSeed;
+extern bool RandstructAutoSelect;
+}
+#endif

clang/include/clang/AST/RecordFieldReorganizer.h

+//===-- RecordFieldReorganizer.h - Interface for manipulating field order --*-
+// C++
+//-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This header file contains the base class that defines an interface for
+// manipulating a RecordDecl's field layouts.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIB_AST_RECORDFIELDREORGANIZER_H
+#define LLVM_CLANG_LIB_AST_RECORDFIELDREORGANIZER_H
+
+#include "Decl.h"
+#include <random>
+
+namespace clang {
+
+// FIXME: Find a better alternative to SmallVector with hardcoded size!
+
+class RecordFieldReorganizer {
+public:
+  virtual ~RecordFieldReorganizer() = default;
+  void reorganizeFields(const ASTContext &C, const RecordDecl *D);
+
+protected:
+  virtual void reorganize(const ASTContext &C, const RecordDecl *D,
+                          SmallVector<Decl *, 64> &NewOrder) = 0;
+
+private:
+  void commit(const RecordDecl *D,
+              SmallVectorImpl<Decl *> &NewFieldOrder) const;
+};
+
+class Randstruct : public RecordFieldReorganizer {
+public:
+  Randstruct(std::string seed) : Seq(seed.begin(), seed.end()), rng(Seq) {}
+
+  /// Determines if the Record can be safely and easily randomized based on certain criteria (see implementation).
+  static bool isTriviallyRandomizable(const RecordDecl *D);
+protected:
+  SmallVector<Decl *, 64> randomize(SmallVector<Decl *, 64> fields);
+  SmallVector<Decl *, 64> perfrandomize(const ASTContext &ctx,
+                                      SmallVector<Decl *, 64> fields);
+  virtual void reorganize(const ASTContext &C, const RecordDecl *D,
+                          SmallVector<Decl *, 64> &NewOrder) override;
+private:
+  std::seed_seq Seq;
+  std::default_random_engine rng;
+};
+
+} // namespace clang
+
+#endif

clang/include/clang/Basic/Attr.td

 }
 
 def ObjCExternallyRetained : InheritableAttr {
   let LangOpts = [ObjCAutoRefCount];
   let Spellings = [Clang<"objc_externally_retained">];
   let Subjects = SubjectList<[NonParmVar, Function, Block, ObjCMethod]>;
   let Documentation = [ObjCExternallyRetainedDocs];
 }
+
+def RandomizeLayout : InheritableAttr {
+  let Spellings = [GCC<"randomize_layout">, Declspec<"randomize_layout">,
+    Keyword<"randomize_layout">];
+  let Subjects = SubjectList<[Record]>;
+  let Documentation = [ClangRandstructDocs];
+}
+
+def NoRandomizeLayout : InheritableAttr {
+  let Spellings = [GCC<"no_randomize_layout">, Declspec<"no_randomize_layout">,
+    Keyword<"no_randomize_layout">];
+  let Subjects = SubjectList<[Record]>;
+  let Documentation = [ClangRandstructDocs];
+}

clang/include/clang/Basic/AttrDocs.td

 added to arbitrary functions that need to follow the same convention - for
 example, a user can add them to auxiliary functions called by the server routine
 that have their return value of type ``kern_return_t`` unconditionally returned
 from the routine. The attribute can be applied to C++ methods, and in this case
 it will be automatically applied to overrides if the method is virtual. The
 attribute can also be written using C++11 syntax: ``[[mig::server_routine]]``.
 }];
 }
+
+def ClangRandstructDocs : Documentation {
+  let Category = DocCatVariable;
+  let Heading = "randomize_layout, no_randomize_layout";
+  let Content = [{
+The attributes ``randomize_layout`` and ``no_randomize_layout`` can be applied
+to a record.
+
+``randomize_layout`` instructs the compiler to randomize the memory layout
+of the member variables of the record.
+
+Conversely, ``no_randomize_layout`` is used to indicate that if using the
+automatic strucuture selection feature of the Randstruct implementation, the
+compiler should not shuffle the members of the record.
+
+In the event that a record is labeled with both attributes, the compiler will
+emit a warning indicating that these two cannot be used on the same record.
+The default behavior in this case is to not randomize the struct, as the
+attribute ``no_randomize_layout`` takes precedence over ``randomize_layout``.
+This is implementation defined behavior.
+
+.. code-block:: c
+
+  // Indicates that this struct should be randomized by Randstruct implementation.
+  struct s {
+    char *a;
+    char *b;
+    char *c;
+  }__attribute__((randomize_layout));
+
+  // Indicates that this struct should NOT be randomized by Randstruct implementation.
+  struct s {
+    char *a;
+    char *b;
+    char *c;
+  }__attribute__((no_randomize_layout));
+
+  // Emits compiler warning. Struct is NOT randomized by Randstruct implementation.
+  struct s {
+    char *a;
+    char *b;
+    char *c;
+  }__attribute__((randomize_layout)) __attribute__((no_randomize_layout));
+}];
+}

clang/include/clang/Basic/DiagnosticASTKinds.td

def warn_padded_struct_anon_field : Warning<
   "padding %select{struct|interface|class}0 %1 with %2 "
   "%select{byte|bit}3%s2 to align anonymous bit-field">,
   InGroup<Padded>, DefaultIgnore;
 def warn_padded_struct_size : Warning<
   "padding size of %0 with %1 %select{byte|bit}2%s1 to alignment boundary">,
   InGroup<Padded>, DefaultIgnore;
 def warn_unnecessary_packed : Warning<
   "packed attribute is unnecessary for %0">, InGroup<Packed>, DefaultIgnore;
+def warn_randomize_attr_union : Warning<
+  "union declared with 'randomize_layout' attribute">, InGroup<DiagGroup<"randomize-layout">>;
+def warn_randomize_attr_conflict : Warning<
+  "struct declared with 'randomize_layout' and 'no_randomize_layout' attributes; "
+  "attribute 'no_randomize_layout' takes precedence">, InGroup<DiagGroup<"no-randomize-layout">>;
 }

clang/include/clang/Driver/CC1Options.td

def fconstexpr_backtrace_limit : Separate<["-"], "fconstexpr-backtrace-limit">, MetaVarName<"<N>">,
   HelpText<"Set the maximum number of entries to print in a constexpr evaluation backtrace (0 = no limit).">;
 def fspell_checking_limit : Separate<["-"], "fspell-checking-limit">, MetaVarName<"<N>">,
   HelpText<"Set the maximum number of times to perform spell checking on unrecognized identifiers (0 = no limit).">;
 def fcaret_diagnostics_max_lines :
   Separate<["-"], "fcaret-diagnostics-max-lines">, MetaVarName<"<N>">,
   HelpText<"Set the maximum number of source lines to show in a caret diagnostic">;
 def fmessage_length : Separate<["-"], "fmessage-length">, MetaVarName<"<N>">,
   HelpText<"Format message diagnostics so that they fit within N columns or fewer, when possible.">;
+def randstruct_seed : Separate<["-"], "randstruct-seed">, MetaVarName<"<N>">,
+  HelpText<"Randomization seed for random struct layouts">;
 def verify_EQ : CommaJoined<["-"], "verify=">,
   MetaVarName<"<prefixes>">,
   HelpText<"Verify diagnostic output using comment directives that start with"
            " prefixes in the comma-separated sequence <prefixes>">;
 def verify : Flag<["-"], "verify">,
   HelpText<"Equivalent to -verify=expected">;
 def verify_ignore_unexpected : Flag<["-"], "verify-ignore-unexpected">,
   HelpText<"Ignore unexpected diagnostic messages">;

clang/include/clang/Driver/Options.td

 def fthinlto_index_EQ : Joined<["-"], "fthinlto-index=">,
   Flags<[CC1Option]>, Group<f_Group>,
   HelpText<"Perform ThinLTO importing using provided function summary index">;
 def fmacro_backtrace_limit_EQ : Joined<["-"], "fmacro-backtrace-limit=">,
                                 Group<f_Group>, Flags<[DriverOption, CoreOption]>;
 def fmerge_all_constants : Flag<["-"], "fmerge-all-constants">, Group<f_Group>,
   Flags<[CC1Option, CoreOption]>, HelpText<"Allow merging of constants">;
 def fmessage_length_EQ : Joined<["-"], "fmessage-length=">, Group<f_Group>;
+def randstruct_seed_EQ : Joined<["-"], "randstruct-seed=">, Group<f_Group>;
 def fms_extensions : Flag<["-"], "fms-extensions">, Group<f_Group>, Flags<[CC1Option, CoreOption]>,
   HelpText<"Accept some non-standard constructs supported by the Microsoft compiler">;
 def fms_compatibility : Flag<["-"], "fms-compatibility">, Group<f_Group>, Flags<[CC1Option, CoreOption]>,
   HelpText<"Enable full Microsoft Visual C++ compatibility">;
 def fms_volatile : Joined<["-"], "fms-volatile">, Group<f_Group>, Flags<[CC1Option]>;
 def fmsc_version : Joined<["-"], "fmsc-version=">, Group<f_Group>, Flags<[DriverOption, CoreOption]>,
   HelpText<"Microsoft compiler version number to report in _MSC_VER (0 = don't define it (default))">;
 def fms_compatibility_version

 def funroll_loops : Flag<["-"], "funroll-loops">, Group<f_Group>,
   HelpText<"Turn on loop unroller">, Flags<[CC1Option]>;
 def fno_unroll_loops : Flag<["-"], "fno-unroll-loops">, Group<f_Group>,
   HelpText<"Turn off loop unroller">, Flags<[CC1Option]>;
 def freroll_loops : Flag<["-"], "freroll-loops">, Group<f_Group>,
   HelpText<"Turn on loop reroller">, Flags<[CC1Option]>;
 def fno_reroll_loops : Flag<["-"], "fno-reroll-loops">, Group<f_Group>,
   HelpText<"Turn off loop reroller">;
+def randstruct_auto : Flag<["-"], "randstruct-auto">,
+  HelpText<"Enable automatic structure selection for field randomization; "
+           "Disable for specific structures with attribute no_randomize_layout">, Flags<[CC1Option]>;
 def ftrigraphs : Flag<["-"], "ftrigraphs">, Group<f_Group>,
   HelpText<"Process trigraph sequences">, Flags<[CC1Option]>;
 def fno_trigraphs : Flag<["-"], "fno-trigraphs">, Group<f_Group>,
   HelpText<"Do not process trigraph sequences">, Flags<[CC1Option]>;
 def funsigned_bitfields : Flag<["-"], "funsigned-bitfields">, Group<f_Group>;
 def funsigned_char : Flag<["-"], "funsigned-char">, Group<f_Group>;
 def fno_unsigned_char : Flag<["-"], "fno-unsigned-char">;
 def funwind_tables : Flag<["-"], "funwind-tables">, Group<f_Group>;

clang/lib/AST/CMakeLists.txt

add_clang_library(clangAST
   ExprCXX.cpp
   ExprObjC.cpp
   ExternalASTMerger.cpp
   ExternalASTSource.cpp
   FormatString.cpp
   InheritViz.cpp
   ItaniumCXXABI.cpp
   ItaniumMangle.cpp
+  RecordFieldReorganizer.cpp
   Mangle.cpp
   MicrosoftCXXABI.cpp
   MicrosoftMangle.cpp
   NestedNameSpecifier.cpp
   NSAPI.cpp
   ODRHash.cpp
   OSLog.cpp
   OpenMPClause.cpp

clang/lib/AST/DeclBase.cpp

for (auto *D : Decls) {
     if (PrevDecl)
       PrevDecl->NextInContextAndBits.setPointer(D);
     else
       FirstNewDecl = D;
 
     PrevDecl = D;
   }
 
+  // The last one in the chain should have a null next!
+  PrevDecl->NextInContextAndBits.setPointer(nullptr);
+
   return std::make_pair(FirstNewDecl, PrevDecl);
 }
 
 /// We have just acquired external visible storage, and we already have
 /// built a lookup map. For every name in the map, pull in the new names from
 /// the external storage.
 void DeclContext::reconcileExternalVisibleStorage() const {
   assert(hasNeedToReconcileExternalVisibleStorage() && LookupPtr);

clang/lib/AST/RecordFieldReorganizer.cpp

+//===----- RecordFieldReorganizer.cpp - Implementation for field reorder -*- C++
+//-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Contains the implementation for RecordDecl field reordering.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/RecordFieldReorganizer.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/RandstructSeed.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <random>
+#include <set>
+#include <vector>
+
+// FIXME: Find a better alternative to SmallVector with hardcoded size!
+
+namespace clang {
+std::string RandstructSeed = "";
+bool RandstructAutoSelect = false;
+
+void RecordFieldReorganizer::reorganizeFields(const ASTContext &C,
+                                              const RecordDecl *D) {
+  // Save original fields for asserting later that a subclass hasn't
+  // sabotaged the RecordDecl by removing or adding fields
+  std::set<Decl *> mutateGuard;
+
+  SmallVector<Decl *, 64> fields;
+  for (auto f : D->fields()) {
+    mutateGuard.insert(f);
+    fields.push_back(f);
+  }
+  // Now allow subclass implementations to reorder the fields
+  reorganize(C, D, fields);
+
+  // Assert all fields are still present
+  assert(mutateGuard.size() == fields.size() &&
+         "Field count altered after reorganization");
+  for (auto f : fields) {
+    auto found = std::find(std::begin(mutateGuard), std::end(mutateGuard), f);
+    assert(found != std::end(mutateGuard) &&
+           "Unknown field encountered after reorganization");
+  }
+
+  commit(D, fields);
+}
+void RecordFieldReorganizer::commit(
+    const RecordDecl *D, SmallVectorImpl<Decl *> &NewFieldOrder) const {
+  Decl *First, *Last;
+  std::tie(First, Last) = DeclContext::BuildDeclChain(
+      NewFieldOrder, D->hasLoadedFieldsFromExternalStorage());
+  D->FirstDecl = First;
+  D->LastDecl = Last;
+}
+
+/// Bucket to store fields up to size of a cache line during randomization.
+class Bucket {
+public:
+  virtual ~Bucket() = default;
+  /// Returns a randomized version of the bucket.
+  virtual SmallVector<FieldDecl *, 64> randomize(std::default_random_engine &rng);
+  /// Checks if an added element would fit in a cache line.
+  virtual bool canFit(size_t size) const;
+  /// Adds a field to the bucket.
+  void add(FieldDecl *field, size_t size);
+  /// Is this bucket for bitfields?
+  virtual bool isBitfieldRun() const;
+  /// Is this bucket full?
+  bool full() const;
+  bool empty() const;
+
+protected:
+  size_t size;
+  SmallVector<FieldDecl *, 64> fields;
+};
+
+/// BitfieldRun is a bucket for storing adjacent bitfields that may
+/// exceed the size of a cache line.
+class BitfieldRun : public Bucket {
+public:
+  virtual SmallVector<FieldDecl *, 64> randomize(std::default_random_engine &rng) override;
+  virtual bool canFit(size_t size) const override;
+  virtual bool isBitfieldRun() const override;
+};
+
+// FIXME: Is there a way to detect this? (i.e. on 32bit system vs 64?)
+const size_t CACHE_LINE = 64;
+
+SmallVector<FieldDecl *, 64> Bucket::randomize(std::default_random_engine &rng) {
+  std::shuffle(std::begin(fields), std::end(fields), rng);
+  return fields;
+}
+
+bool Bucket::canFit(size_t size) const {
+  // We will say we can fit any size if the bucket is empty
+  // because there are many instances where a field is much
+  // larger than 64 bits (i.e., an array, a structure, etc)
+  // but it still must be placed into a bucket.
+  //
+  // Otherwise, if the bucket has elements and we're still
+  // trying to create a cache-line sized grouping, we cannot
+  // fit a larger field in here.
+  return empty() || this->size + size <= CACHE_LINE;
+}
+
+void Bucket::add(FieldDecl *field, size_t size) {
+  fields.push_back(field);
+  this->size += size;
+}
+
+bool Bucket::isBitfieldRun() const {
+  // The normal bucket is not a bitfieldrun. This is to avoid RTTI.
+  return false;
+}
+
+bool Bucket::full() const {
+  // We're full if our size is a cache line.
+  return size >= CACHE_LINE;
+}
+
+bool Bucket::empty() const { return size == 0; }
+
+SmallVector<FieldDecl *, 64> BitfieldRun::randomize(std::default_random_engine &rng) {
+  // Keep bit fields adjacent, we will not scramble them.
+  return fields;
+}
+
+bool BitfieldRun::canFit(size_t size) const {
+  // We can always fit another adjacent bitfield.
+  return true;
+}
+
+bool BitfieldRun::isBitfieldRun() const { return true; }
+
+SmallVector<Decl *, 64> Randstruct::randomize(SmallVector<Decl *, 64> fields) {
+  std::shuffle(std::begin(fields), std::end(fields), rng);
+  return fields;
+}
+
+SmallVector<Decl *, 64> Randstruct::perfrandomize(const ASTContext &ctx,
+                                      SmallVector<Decl *, 64> fields) {
+  // All of the buckets produced by best-effort cache-line algorithm.
+  std::vector<std::unique_ptr<Bucket>> buckets;
+
+  // The current bucket of fields that we are trying to fill to a cache-line.
+  std::unique_ptr<Bucket> currentBucket = nullptr;
+  // The current bucket containing the run of adjacent  bitfields to ensure
+  // they remain adjacent.
+  std::unique_ptr<Bucket> currentBitfieldRun = nullptr;
+
+  // Tracks the number of fields that we failed to fit to the current bucket,
+  // and thus still need to be added later.
+  size_t skipped = 0;
+
+  while (!fields.empty()) {
+    // If we've skipped more fields than we have remaining to place,
+    // that means that they can't fit in our current bucket, and we
+    // need to start a new one.
+    if (skipped >= fields.size()) {
+      skipped = 0;
+      buckets.push_back(std::move(currentBucket));
+    }
+
+    // Take the first field that needs to be put in a bucket.
+    auto field = fields.begin();
+    auto *f = llvm::cast<FieldDecl>(*field);
+
+    if (f->isBitField()) {
+      // Start a bitfield run if this is the first bitfield
+      // we have found.
+      if (!currentBitfieldRun) {
+        currentBitfieldRun = llvm::make_unique<BitfieldRun>();
+      }
+
+      // We've placed the field, and can remove it from the
+      // "awaiting buckets" vector called "fields"
+      currentBitfieldRun->add(f, 1);
+      fields.erase(field);
+    } else {
+      // Else, current field is not a bitfield
+      // If we were previously in a bitfield run, end it.
+      if (currentBitfieldRun) {
+        buckets.push_back(std::move(currentBitfieldRun));
+      }
+      // If we don't have a bucket, make one.
+      if (!currentBucket) {
+        currentBucket = llvm::make_unique<Bucket>();
+      }
+
+      auto width = ctx.getTypeInfo(f->getType()).Width;
+
+      // If we can fit, add it.
+      if (currentBucket->canFit(width)) {
+        currentBucket->add(f, width);
+        fields.erase(field);
+
+        // If it's now full, tie off the bucket.
+        if (currentBucket->full()) {
+          skipped = 0;
+          buckets.push_back(std::move(currentBucket));
+        }
+      } else {
+        // We can't fit it in our current bucket.
+        // Move to the end for processing later.
+        ++skipped; // Mark it skipped.
+        fields.push_back(f);
+        fields.erase(field);
+      }
+    }
+  }
+
+  // Done processing the fields awaiting a bucket.
+
+  // If we were filling a bucket, tie it off.
+  if (currentBucket) {
+    buckets.push_back(std::move(currentBucket));
+  }
+
+  // If we were processing a bitfield run bucket, tie it off.
+  if (currentBitfieldRun) {
+    buckets.push_back(std::move(currentBitfieldRun));
+  }
+
+  std::shuffle(std::begin(buckets), std::end(buckets), rng);
+
+  // Produce the new ordering of the elements from our buckets.
+  SmallVector<Decl *, 64> finalOrder;
+  for (auto &bucket : buckets) {
+    auto randomized = bucket->randomize(rng);
+    finalOrder.insert(finalOrder.end(), randomized.begin(), randomized.end());
+  }
+
+  return finalOrder;
+}
+
+void Randstruct::reorganize(const ASTContext &C, const RecordDecl *D,
+                            SmallVector<Decl *, 64> &NewOrder) {
+  SmallVector<Decl *, 64> randomized = perfrandomize(C, NewOrder);
+  NewOrder = randomized;
+}
+bool Randstruct::isTriviallyRandomizable(const RecordDecl *D) {
+  for (auto f : D->fields()){
+    //If an element of the structure does not have a
+    //function type is not a function pointer
+    if(f->getFunctionType() == nullptr){ return false; }
+  }
+  return true;
+}
+} // namespace clang

clang/lib/AST/RecordLayoutBuilder.cpp

 //=== RecordLayoutBuilder.cpp - Helper class for building record layouts ---==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "clang/AST/RandstructSeed.h"
 #include "clang/AST/RecordLayout.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/CXXInheritance.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/Expr.h"
+#include "clang/AST/RecordFieldReorganizer.h"
 #include "clang/Basic/TargetInfo.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/MathExtras.h"
 
 using namespace clang;
 
 namespace {
ASTContext::getASTRecordLayout(const RecordDecl *D) const {
   // Look up this layout, if already laid out, return what we have.
   // Note that we can't save a reference to the entry because this function
   // is recursive.
   const ASTRecordLayout *Entry = ASTRecordLayouts[D];
   if (Entry) return *Entry;
 
   const ASTRecordLayout *NewEntry = nullptr;
 
+  bool ShouldBeRandomized = D->getAttr<RandomizeLayoutAttr>() != nullptr;
+  bool NotToBeRandomized = D->getAttr<NoRandomizeLayoutAttr>() != nullptr;
+  bool AutoSelectable = RandstructAutoSelect && Randstruct::isTriviallyRandomizable(D);
+
+  if (ShouldBeRandomized && NotToBeRandomized) {
+    getDiagnostics().Report(D->getLocation(), diag::warn_randomize_attr_conflict);
+  }
+
+  if (ShouldBeRandomized && D->isUnion()) {
+      getDiagnostics().Report(D->getLocation(), diag::warn_randomize_attr_union);
+      NotToBeRandomized = true;
+  }
+
+  if (!NotToBeRandomized && (ShouldBeRandomized || AutoSelectable)) {
+    Randstruct randstruct(RandstructSeed);
+    randstruct.reorganizeFields(*this,D);
+  }
+
   if (isMsLayout(*this)) {
     MicrosoftRecordLayoutBuilder Builder(*this);
     if (const auto *RD = dyn_cast<CXXRecordDecl>(D)) {
       Builder.cxxLayout(RD);
       NewEntry = new (*this) ASTRecordLayout(
           *this, Builder.Size, Builder.Alignment, Builder.Alignment,
           Builder.RequiredAlignment,
           Builder.HasOwnVFPtr, Builder.HasOwnVFPtr || Builder.PrimaryBase,

clang/lib/Driver/ToolChains/Clang.cpp

if (Arg *A = Args.getLastArg(options::OPT_fmessage_length_EQ)) {
     CmdArgs.push_back(A->getValue());
   } else {
     // If -fmessage-length=N was not specified, determine whether this is a
     // terminal and, if so, implicitly define -fmessage-length appropriately.
     unsigned N = llvm::sys::Process::StandardErrColumns();
     CmdArgs.push_back(Args.MakeArgString(Twine(N)));
   }
 
+  // -randstruct-seed parent process
+  if (Arg *A = Args.getLastArg(options::OPT_randstruct_seed_EQ)) {
+    CmdArgs.push_back( "-randstruct-seed" );
+    CmdArgs.push_back(A->getValue(0));
+  }
+
+  if (Arg *A = Args.getLastArg(options::OPT_randstruct_auto)) {
+    CmdArgs.push_back( "-randstruct-auto" );
+  }
+
   // -fvisibility= and -fvisibility-ms-compat are of a piece.
   if (const Arg *A = Args.getLastArg(options::OPT_fvisibility_EQ,
                                      options::OPT_fvisibility_ms_compat)) {
     if (A->getOption().matches(options::OPT_fvisibility_EQ)) {
       CmdArgs.push_back("-fvisibility");
       CmdArgs.push_back(A->getValue());
     } else {
       assert(A->getOption().matches(options::OPT_fvisibility_ms_compat));

clang/lib/Frontend/CompilerInvocation.cpp

 //===- CompilerInvocation.cpp ---------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "clang/AST/RandstructSeed.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "TestModuleFileExtension.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/CharInfo.h"
 #include "clang/Basic/CodeGenOptions.h"
 #include "clang/Basic/CommentOptions.h"
 #include "clang/Basic/DebugInfoOptions.h"
 #include "clang/Basic/Diagnostic.h"
if (const Arg *A = Args.getLastArg(OPT_Action_Group)) {
     }
   }
 
   if (const Arg* A = Args.getLastArg(OPT_plugin)) {
     Opts.Plugins.emplace_back(A->getValue(0));
     Opts.ProgramAction = frontend::PluginAction;
     Opts.ActionName = A->getValue();
   }
+  // child process handle arguments
+  if (const Arg* A = Args.getLastArg(OPT_randstruct_seed)) {
+    RandstructSeed = A->getValue(0);
+  }
+  if (const Arg* A = Args.getLastArg(OPT_randstruct_auto)) {
+    RandstructAutoSelect = true;
+  }
   Opts.AddPluginActions = Args.getAllArgValues(OPT_add_plugin);
   for (const auto *AA : Args.filtered(OPT_plugin_arg))
     Opts.PluginArgs[AA->getValue(0)].emplace_back(AA->getValue(1));
 
   for (const std::string &Arg :
          Args.getAllArgValues(OPT_ftest_module_file_extension_EQ)) {
     std::string BlockName;
     unsigned MajorVersion;

clang/lib/Sema/SemaDeclAttr.cpp

case ParsedAttr::AT_SpeculativeLoadHardening:
     handleSimpleAttributeWithExclusions<SpeculativeLoadHardeningAttr,
                                         NoSpeculativeLoadHardeningAttr>(S, D,
                                                                         AL);
     break;
   case ParsedAttr::AT_NoSpeculativeLoadHardening:
     handleSimpleAttributeWithExclusions<NoSpeculativeLoadHardeningAttr,
                                         SpeculativeLoadHardeningAttr>(S, D, AL);
     break;
+  case ParsedAttr::AT_RandomizeLayout:
+    handleSimpleAttribute<RandomizeLayoutAttr>(S, D, AL);
+    break;
+  case ParsedAttr::AT_NoRandomizeLayout:
+    handleSimpleAttribute<NoRandomizeLayoutAttr>(S, D, AL);
+    break;
   case ParsedAttr::AT_CodeSeg:
     handleCodeSegAttr(S, D, AL);
     break;
   case ParsedAttr::AT_Target:
     handleTargetAttr(S, D, AL);
     break;
   case ParsedAttr::AT_MinVectorWidth:
     handleMinVectorWidthAttr(S, D, AL);

clang/test/Misc/pragma-attribute-supported-attributes-list.test

 // CHECK-NEXT: NoDebug (SubjectMatchRule_hasType_functionType, SubjectMatchRule_objc_method, SubjectMatchRule_variable_not_is_parameter)
 // CHECK-NEXT: NoDestroy (SubjectMatchRule_variable)
 // CHECK-NEXT: NoDuplicate (SubjectMatchRule_function)
 // CHECK-NEXT: NoEscape (SubjectMatchRule_variable_is_parameter)
 // CHECK-NEXT: NoInline (SubjectMatchRule_function)
 // CHECK-NEXT: NoInstrumentFunction (SubjectMatchRule_function)
 // CHECK-NEXT: NoMicroMips (SubjectMatchRule_function)
 // CHECK-NEXT: NoMips16 (SubjectMatchRule_function)
+// CHECK-NEXT: NoRandomizeLayout (SubjectMatchRule_record)
 // CHECK-NEXT: NoSanitize (SubjectMatchRule_function, SubjectMatchRule_objc_method, SubjectMatchRule_variable_is_global)
 // CHECK-NEXT: NoSanitizeSpecific (SubjectMatchRule_function, SubjectMatchRule_variable_is_global)
 // CHECK-NEXT: NoSpeculativeLoadHardening (SubjectMatchRule_function, SubjectMatchRule_objc_method)
 // CHECK-NEXT: NoSplitStack (SubjectMatchRule_function)
 // CHECK-NEXT: NoStackProtector (SubjectMatchRule_function)
 // CHECK-NEXT: NoThreadSafetyAnalysis (SubjectMatchRule_function)
 // CHECK-NEXT: NoThrow (SubjectMatchRule_function)
 // CHECK-NEXT: NotTailCalled (SubjectMatchRule_function)

 // CHECK-NEXT: ObjCRuntimeVisible (SubjectMatchRule_objc_interface)
 // CHECK-NEXT: ObjCSubclassingRestricted (SubjectMatchRule_objc_interface)
 // CHECK-NEXT: OpenCLIntelReqdSubGroupSize (SubjectMatchRule_function)
 // CHECK-NEXT: OpenCLNoSVM (SubjectMatchRule_variable)
 // CHECK-NEXT: OptimizeNone (SubjectMatchRule_function, SubjectMatchRule_objc_method)
 // CHECK-NEXT: Overloadable (SubjectMatchRule_function)
 // CHECK-NEXT: ParamTypestate (SubjectMatchRule_variable_is_parameter)
 // CHECK-NEXT: PassObjectSize (SubjectMatchRule_variable_is_parameter)
+// CHECK-NEXT: RandomizeLayout (SubjectMatchRule_record)
 // CHECK-NEXT: RenderScriptKernel (SubjectMatchRule_function)
 // CHECK-NEXT: ReqdWorkGroupSize (SubjectMatchRule_function)
 // CHECK-NEXT: RequireConstantInit (SubjectMatchRule_variable_is_global)
 // CHECK-NEXT: Restrict (SubjectMatchRule_function)
 // CHECK-NEXT: ReturnTypestate (SubjectMatchRule_function, SubjectMatchRule_variable_is_parameter)
 // CHECK-NEXT: ReturnsNonNull (SubjectMatchRule_objc_method, SubjectMatchRule_function)
 // CHECK-NEXT: ReturnsTwice (SubjectMatchRule_function)
 // CHECK-NEXT: ScopedLockable (SubjectMatchRule_record)