1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
|
//===--- Randstruct.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
//
//===----------------------------------------------------------------------===//
//
// This file contains the implementation for Clang's structure field layout
// randomization.
//
//===----------------------------------------------------------------------===//
#include "clang/AST/Randstruct.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/ASTDiagnostic.h"
#include "clang/AST/Attr.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclCXX.h" // For StaticAssertDecl
#include "clang/Basic/Diagnostic.h"
#include "llvm/ADT/SmallVector.h"
#include <algorithm>
#include <random>
#include <set>
#include <sstream>
#include <string>
using clang::ASTContext;
using clang::FieldDecl;
using llvm::SmallVector;
namespace {
// FIXME: Replace this with some discovery once that mechanism exists.
enum { CACHE_LINE = 64 };
// The Bucket class holds the struct fields we're trying to fill to a
// cache-line.
class Bucket {
SmallVector<FieldDecl *, 64> Fields;
int Size = 0;
public:
virtual ~Bucket() = default;
SmallVector<FieldDecl *, 64> &fields() { return Fields; }
void addField(FieldDecl *Field, int FieldSize);
virtual bool canFit(int FieldSize) const {
return Size + FieldSize <= CACHE_LINE;
}
virtual bool isBitfieldRun() const { return false; }
bool full() const { return Size >= CACHE_LINE; }
};
void Bucket::addField(FieldDecl *Field, int FieldSize) {
Size += FieldSize;
Fields.push_back(Field);
}
struct BitfieldRunBucket : public Bucket {
bool canFit(int FieldSize) const override { return true; }
bool isBitfieldRun() const override { return true; }
};
void randomizeStructureLayoutImpl(const ASTContext &Context,
llvm::SmallVectorImpl<FieldDecl *> &FieldsOut,
std::mt19937 &RNG) {
// All of the Buckets produced by best-effort cache-line algorithm.
SmallVector<std::unique_ptr<Bucket>, 16> Buckets;
// The current bucket of fields that we are trying to fill to a cache-line.
std::unique_ptr<Bucket> CurrentBucket;
// The current bucket containing the run of adjacent bitfields to ensure they
// remain adjacent.
std::unique_ptr<BitfieldRunBucket> CurrentBitfieldRun;
// 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 (!FieldsOut.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 >= FieldsOut.size()) {
Skipped = 0;
Buckets.push_back(std::move(CurrentBucket));
}
// Take the first field that needs to be put in a bucket.
auto FieldIter = FieldsOut.begin();
FieldDecl *FD = *FieldIter;
if (FD->isBitField() && !FD->isZeroLengthBitField(Context)) {
// Start a bitfield run if this is the first bitfield we have found.
if (!CurrentBitfieldRun)
CurrentBitfieldRun = std::make_unique<BitfieldRunBucket>();
// We've placed the field, and can remove it from the "awaiting Buckets"
// vector called "Fields."
CurrentBitfieldRun->addField(FD, /*FieldSize is irrelevant here*/ 1);
FieldsOut.erase(FieldIter);
continue;
}
// 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 = std::make_unique<Bucket>();
uint64_t Width = Context.getTypeInfo(FD->getType()).Width;
if (Width >= CACHE_LINE) {
std::unique_ptr<Bucket> OverSized = std::make_unique<Bucket>();
OverSized->addField(FD, Width);
FieldsOut.erase(FieldIter);
Buckets.push_back(std::move(OverSized));
continue;
}
// If it fits, add it.
if (CurrentBucket->canFit(Width)) {
CurrentBucket->addField(FD, Width);
FieldsOut.erase(FieldIter);
// 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.
FieldsOut.push_back(FD);
FieldsOut.erase(FieldIter);
}
}
// 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 the Buckets.
SmallVector<FieldDecl *, 16> FinalOrder;
for (const std::unique_ptr<Bucket> &B : Buckets) {
llvm::SmallVectorImpl<FieldDecl *> &RandFields = B->fields();
if (!B->isBitfieldRun())
std::shuffle(std::begin(RandFields), std::end(RandFields), RNG);
FinalOrder.insert(FinalOrder.end(), RandFields.begin(), RandFields.end());
}
FieldsOut = FinalOrder;
}
} // anonymous namespace
namespace clang {
namespace randstruct {
bool randomizeStructureLayout(const ASTContext &Context, RecordDecl *RD,
SmallVectorImpl<Decl *> &FinalOrdering) {
SmallVector<FieldDecl *, 64> RandomizedFields;
SmallVector<Decl *, 8> PostRandomizedFields;
unsigned TotalNumFields = 0;
for (Decl *D : RD->decls()) {
++TotalNumFields;
if (auto *FD = dyn_cast<FieldDecl>(D))
RandomizedFields.push_back(FD);
else if (isa<StaticAssertDecl>(D) || isa<IndirectFieldDecl>(D))
PostRandomizedFields.push_back(D);
else
FinalOrdering.push_back(D);
}
if (RandomizedFields.empty())
return false;
// Struct might end with a flexible array or an array of size 0 or 1,
// in which case we don't want to randomize it.
FieldDecl *FlexibleArray =
RD->hasFlexibleArrayMember() ? RandomizedFields.pop_back_val() : nullptr;
if (!FlexibleArray) {
if (const auto *CA =
dyn_cast<ConstantArrayType>(RandomizedFields.back()->getType()))
if (CA->getSize().sle(2))
FlexibleArray = RandomizedFields.pop_back_val();
}
std::string Seed =
Context.getLangOpts().RandstructSeed + RD->getNameAsString();
std::seed_seq SeedSeq(Seed.begin(), Seed.end());
std::mt19937 RNG(SeedSeq);
randomizeStructureLayoutImpl(Context, RandomizedFields, RNG);
// Plorp the randomized decls into the final ordering.
FinalOrdering.insert(FinalOrdering.end(), RandomizedFields.begin(),
RandomizedFields.end());
// Add fields that belong towards the end of the RecordDecl.
FinalOrdering.insert(FinalOrdering.end(), PostRandomizedFields.begin(),
PostRandomizedFields.end());
// Add back the flexible array.
if (FlexibleArray)
FinalOrdering.push_back(FlexibleArray);
assert(TotalNumFields == FinalOrdering.size() &&
"Decl count has been altered after Randstruct randomization!");
(void)TotalNumFields;
return true;
}
} // end namespace randstruct
} // end namespace clang
|
