diff --git a/clang/include/clang/AST/Decl.h b/clang/include/clang/AST/Decl.h --- a/clang/include/clang/AST/Decl.h +++ b/clang/include/clang/AST/Decl.h @@ -65,6 +65,7 @@ class NamespaceDecl; class ParmVarDecl; class RecordDecl; +class RecordFieldReorganizer; class Stmt; class StringLiteral; class TagDecl; diff --git a/clang/include/clang/AST/DeclBase.h b/clang/include/clang/AST/DeclBase.h --- a/clang/include/clang/AST/DeclBase.h +++ b/clang/include/clang/AST/DeclBase.h @@ -1270,6 +1270,8 @@ 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; diff --git a/clang/include/clang/AST/RandstructSeed.h b/clang/include/clang/AST/RandstructSeed.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/AST/RandstructSeed.h @@ -0,0 +1,8 @@ +#ifndef RANDSTRUCTSEED_H +#define RANDSTRUCTSEED_H +#include +namespace clang { +extern std::string RandstructSeed; +extern bool RandstructAutoSelect; +} +#endif diff --git a/clang/include/clang/AST/RecordFieldReorganizer.h b/clang/include/clang/AST/RecordFieldReorganizer.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/AST/RecordFieldReorganizer.h @@ -0,0 +1,59 @@ +//===-- 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 + +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 &NewOrder) = 0; + +private: + void commit(const RecordDecl *D, + SmallVectorImpl &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 randomize(SmallVector fields); + SmallVector perfrandomize(const ASTContext &ctx, + SmallVector fields); + virtual void reorganize(const ASTContext &C, const RecordDecl *D, + SmallVector &NewOrder) override; +private: + std::seed_seq Seq; + std::default_random_engine rng; +}; + +} // namespace clang + +#endif diff --git a/clang/include/clang/Basic/Attr.td b/clang/include/clang/Basic/Attr.td --- a/clang/include/clang/Basic/Attr.td +++ b/clang/include/clang/Basic/Attr.td @@ -3214,3 +3214,17 @@ 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]; +} diff --git a/clang/include/clang/Basic/AttrDocs.td b/clang/include/clang/Basic/AttrDocs.td --- a/clang/include/clang/Basic/AttrDocs.td +++ b/clang/include/clang/Basic/AttrDocs.td @@ -4116,3 +4116,48 @@ 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)); +}]; +} diff --git a/clang/include/clang/Basic/DiagnosticASTKinds.td b/clang/include/clang/Basic/DiagnosticASTKinds.td --- a/clang/include/clang/Basic/DiagnosticASTKinds.td +++ b/clang/include/clang/Basic/DiagnosticASTKinds.td @@ -343,4 +343,9 @@ InGroup, DefaultIgnore; def warn_unnecessary_packed : Warning< "packed attribute is unnecessary for %0">, InGroup, DefaultIgnore; +def warn_randomize_attr_union : Warning< + "union declared with 'randomize_layout' attribute">, InGroup>; +def warn_randomize_attr_conflict : Warning< + "struct declared with 'randomize_layout' and 'no_randomize_layout' attributes; " + "attribute 'no_randomize_layout' takes precedence">, InGroup>; } diff --git a/clang/include/clang/Driver/CC1Options.td b/clang/include/clang/Driver/CC1Options.td --- a/clang/include/clang/Driver/CC1Options.td +++ b/clang/include/clang/Driver/CC1Options.td @@ -422,6 +422,8 @@ HelpText<"Set the maximum number of source lines to show in a caret diagnostic">; def fmessage_length : Separate<["-"], "fmessage-length">, MetaVarName<"">, HelpText<"Format message diagnostics so that they fit within N columns or fewer, when possible.">; +def randstruct_seed : Separate<["-"], "randstruct-seed">, MetaVarName<"">, + HelpText<"Randomization seed for random struct layouts">; def verify_EQ : CommaJoined<["-"], "verify=">, MetaVarName<"">, HelpText<"Verify diagnostic output using comment directives that start with" diff --git a/clang/include/clang/Driver/Options.td b/clang/include/clang/Driver/Options.td --- a/clang/include/clang/Driver/Options.td +++ b/clang/include/clang/Driver/Options.td @@ -1267,6 +1267,7 @@ def fmerge_all_constants : Flag<["-"], "fmerge-all-constants">, Group, Flags<[CC1Option, CoreOption]>, HelpText<"Allow merging of constants">; def fmessage_length_EQ : Joined<["-"], "fmessage-length=">, Group; +def randstruct_seed_EQ : Joined<["-"], "randstruct-seed=">, Group; def fms_extensions : Flag<["-"], "fms-extensions">, Group, Flags<[CC1Option, CoreOption]>, HelpText<"Accept some non-standard constructs supported by the Microsoft compiler">; def fms_compatibility : Flag<["-"], "fms-compatibility">, Group, Flags<[CC1Option, CoreOption]>, @@ -1759,6 +1760,9 @@ HelpText<"Turn on loop reroller">, Flags<[CC1Option]>; def fno_reroll_loops : Flag<["-"], "fno-reroll-loops">, 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, HelpText<"Process trigraph sequences">, Flags<[CC1Option]>; def fno_trigraphs : Flag<["-"], "fno-trigraphs">, Group, diff --git a/clang/lib/AST/CMakeLists.txt b/clang/lib/AST/CMakeLists.txt --- a/clang/lib/AST/CMakeLists.txt +++ b/clang/lib/AST/CMakeLists.txt @@ -44,6 +44,7 @@ InheritViz.cpp ItaniumCXXABI.cpp ItaniumMangle.cpp + RecordFieldReorganizer.cpp Mangle.cpp MicrosoftCXXABI.cpp MicrosoftMangle.cpp diff --git a/clang/lib/AST/DeclBase.cpp b/clang/lib/AST/DeclBase.cpp --- a/clang/lib/AST/DeclBase.cpp +++ b/clang/lib/AST/DeclBase.cpp @@ -1258,6 +1258,9 @@ PrevDecl = D; } + // The last one in the chain should have a null next! + PrevDecl->NextInContextAndBits.setPointer(nullptr); + return std::make_pair(FirstNewDecl, PrevDecl); } diff --git a/clang/lib/AST/RecordFieldReorganizer.cpp b/clang/lib/AST/RecordFieldReorganizer.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/RecordFieldReorganizer.cpp @@ -0,0 +1,257 @@ +//===----- 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 +#include +#include +#include +#include + +// 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 mutateGuard; + + SmallVector 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 &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 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 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 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 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 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 Randstruct::randomize(SmallVector fields) { + std::shuffle(std::begin(fields), std::end(fields), rng); + return fields; +} + +SmallVector Randstruct::perfrandomize(const ASTContext &ctx, + SmallVector fields) { + // All of the buckets produced by best-effort cache-line algorithm. + std::vector> buckets; + + // The current bucket of fields that we are trying to fill to a cache-line. + std::unique_ptr currentBucket = nullptr; + // The current bucket containing the run of adjacent bitfields to ensure + // they remain adjacent. + std::unique_ptr 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(*field); + + if (f->isBitField()) { + // Start a bitfield run if this is the first bitfield + // we have found. + if (!currentBitfieldRun) { + currentBitfieldRun = llvm::make_unique(); + } + + // 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(); + } + + 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 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 &NewOrder) { + SmallVector 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 diff --git a/clang/lib/AST/RecordLayoutBuilder.cpp b/clang/lib/AST/RecordLayoutBuilder.cpp --- a/clang/lib/AST/RecordLayoutBuilder.cpp +++ b/clang/lib/AST/RecordLayoutBuilder.cpp @@ -6,6 +6,7 @@ // //===----------------------------------------------------------------------===// +#include "clang/AST/RandstructSeed.h" #include "clang/AST/RecordLayout.h" #include "clang/AST/ASTContext.h" #include "clang/AST/ASTDiagnostic.h" @@ -15,6 +16,7 @@ #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" @@ -2984,6 +2986,24 @@ const ASTRecordLayout *NewEntry = nullptr; + bool ShouldBeRandomized = D->getAttr() != nullptr; + bool NotToBeRandomized = D->getAttr() != 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(D)) { diff --git a/clang/lib/Driver/ToolChains/Clang.cpp b/clang/lib/Driver/ToolChains/Clang.cpp --- a/clang/lib/Driver/ToolChains/Clang.cpp +++ b/clang/lib/Driver/ToolChains/Clang.cpp @@ -4427,6 +4427,16 @@ 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)) { diff --git a/clang/lib/Frontend/CompilerInvocation.cpp b/clang/lib/Frontend/CompilerInvocation.cpp --- a/clang/lib/Frontend/CompilerInvocation.cpp +++ b/clang/lib/Frontend/CompilerInvocation.cpp @@ -6,6 +6,7 @@ // //===----------------------------------------------------------------------===// +#include "clang/AST/RandstructSeed.h" #include "clang/Frontend/CompilerInvocation.h" #include "TestModuleFileExtension.h" #include "clang/Basic/Builtins.h" @@ -1673,6 +1674,13 @@ 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)); diff --git a/clang/lib/Sema/SemaDeclAttr.cpp b/clang/lib/Sema/SemaDeclAttr.cpp --- a/clang/lib/Sema/SemaDeclAttr.cpp +++ b/clang/lib/Sema/SemaDeclAttr.cpp @@ -6966,6 +6966,12 @@ handleSimpleAttributeWithExclusions(S, D, AL); break; + case ParsedAttr::AT_RandomizeLayout: + handleSimpleAttribute(S, D, AL); + break; + case ParsedAttr::AT_NoRandomizeLayout: + handleSimpleAttribute(S, D, AL); + break; case ParsedAttr::AT_CodeSeg: handleCodeSegAttr(S, D, AL); break; diff --git a/clang/test/Misc/pragma-attribute-supported-attributes-list.test b/clang/test/Misc/pragma-attribute-supported-attributes-list.test --- a/clang/test/Misc/pragma-attribute-supported-attributes-list.test +++ b/clang/test/Misc/pragma-attribute-supported-attributes-list.test @@ -81,6 +81,7 @@ // 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) @@ -118,6 +119,7 @@ // 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)