Bug Summary

File:src/gnu/usr.bin/clang/llvm-objcopy/../../../llvm/llvm/include/llvm/Support/Alignment.h
Warning:line 85, column 47
The result of the left shift is undefined due to shifting by '255', which is greater or equal to the width of type 'uint64_t'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name MachOLayoutBuilder.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/llvm-objcopy/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/llvm-objcopy/obj/../include/llvm-objcopy -I /usr/src/gnu/usr.bin/clang/llvm-objcopy/../../../llvm/llvm/tools/llvm-objcopy -I /usr/src/gnu/usr.bin/clang/llvm-objcopy/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/llvm-objcopy/../include -I /usr/src/gnu/usr.bin/clang/llvm-objcopy/obj -I /usr/src/gnu/usr.bin/clang/llvm-objcopy/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/llvm-objcopy/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/llvm-objcopy/../../../llvm/llvm/tools/llvm-objcopy/MachO/MachOLayoutBuilder.cpp

/usr/src/gnu/usr.bin/clang/llvm-objcopy/../../../llvm/llvm/tools/llvm-objcopy/MachO/MachOLayoutBuilder.cpp

→
1//===- MachOLayoutBuilder.cpp -----------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "MachOLayoutBuilder.h"
10#include "llvm/Support/Alignment.h"
11#include "llvm/Support/Errc.h"
12#include "llvm/Support/ErrorHandling.h"
13
14using namespace llvm;
15using namespace llvm::objcopy::macho;
16
17StringTableBuilder::Kind
18MachOLayoutBuilder::getStringTableBuilderKind(const Object &O, bool Is64Bit) {
19 if (O.Header.FileType == MachO::HeaderFileType::MH_OBJECT)
20 return Is64Bit ? StringTableBuilder::MachO64 : StringTableBuilder::MachO;
21 return Is64Bit ? StringTableBuilder::MachO64Linked
22 : StringTableBuilder::MachOLinked;
23}
24
25uint32_t MachOLayoutBuilder::computeSizeOfCmds() const {
26 uint32_t Size = 0;
27 for (const LoadCommand &LC : O.LoadCommands) {
28 const MachO::macho_load_command &MLC = LC.MachOLoadCommand;
29 auto cmd = MLC.load_command_data.cmd;
30 switch (cmd) {
31 case MachO::LC_SEGMENT:
32 Size += sizeof(MachO::segment_command) +
33 sizeof(MachO::section) * LC.Sections.size();
34 continue;
35 case MachO::LC_SEGMENT_64:
36 Size += sizeof(MachO::segment_command_64) +
37 sizeof(MachO::section_64) * LC.Sections.size();
38 continue;
39 }
40
41 switch (cmd) {
42#define HANDLE_LOAD_COMMAND(LCName, LCValue, LCStruct) \
43 case MachO::LCName: \
44 Size += sizeof(MachO::LCStruct) + LC.Payload.size(); \
45 break;
46#include "llvm/BinaryFormat/MachO.def"
47#undef HANDLE_LOAD_COMMAND
48 }
49 }
50
51 return Size;
52}
53
54void MachOLayoutBuilder::constructStringTable() {
55 for (std::unique_ptr<SymbolEntry> &Sym : O.SymTable.Symbols)
56 StrTableBuilder.add(Sym->Name);
57 StrTableBuilder.finalize();
58}
59
60void MachOLayoutBuilder::updateSymbolIndexes() {
61 uint32_t Index = 0;
62 for (auto &Symbol : O.SymTable.Symbols)
63 Symbol->Index = Index++;
64}
65
66// Updates the index and the number of local/external/undefined symbols.
67void MachOLayoutBuilder::updateDySymTab(MachO::macho_load_command &MLC) {
68 assert(MLC.load_command_data.cmd == MachO::LC_DYSYMTAB)((void)0);
69 // Make sure that nlist entries in the symbol table are sorted by the those
70 // types. The order is: local < defined external < undefined external.
71 assert(llvm::is_sorted(O.SymTable.Symbols,((void)0)
72 [](const std::unique_ptr<SymbolEntry> &A,((void)0)
73 const std::unique_ptr<SymbolEntry> &B) {((void)0)
74 bool AL = A->isLocalSymbol(),((void)0)
75 BL = B->isLocalSymbol();((void)0)
76 if (AL != BL)((void)0)
77 return AL;((void)0)
78 return !AL && !A->isUndefinedSymbol() &&((void)0)
79 B->isUndefinedSymbol();((void)0)
80 }) &&((void)0)
81 "Symbols are not sorted by their types.")((void)0);
82
83 uint32_t NumLocalSymbols = 0;
84 auto Iter = O.SymTable.Symbols.begin();
85 auto End = O.SymTable.Symbols.end();
86 for (; Iter != End; ++Iter) {
87 if ((*Iter)->isExternalSymbol())
88 break;
89
90 ++NumLocalSymbols;
91 }
92
93 uint32_t NumExtDefSymbols = 0;
94 for (; Iter != End; ++Iter) {
95 if ((*Iter)->isUndefinedSymbol())
96 break;
97
98 ++NumExtDefSymbols;
99 }
100
101 MLC.dysymtab_command_data.ilocalsym = 0;
102 MLC.dysymtab_command_data.nlocalsym = NumLocalSymbols;
103 MLC.dysymtab_command_data.iextdefsym = NumLocalSymbols;
104 MLC.dysymtab_command_data.nextdefsym = NumExtDefSymbols;
105 MLC.dysymtab_command_data.iundefsym = NumLocalSymbols + NumExtDefSymbols;
106 MLC.dysymtab_command_data.nundefsym =
107 O.SymTable.Symbols.size() - (NumLocalSymbols + NumExtDefSymbols);
108}
109
110// Recomputes and updates offset and size fields in load commands and sections
111// since they could be modified.
112uint64_t MachOLayoutBuilder::layoutSegments() {
113 auto HeaderSize =
114 Is64Bit ? sizeof(MachO::mach_header_64) : sizeof(MachO::mach_header);
2
←
Assuming field 'Is64Bit' is false
→
3
←
'?' condition is false
→
115 const bool IsObjectFile =
116 O.Header.FileType == MachO::HeaderFileType::MH_OBJECT;
4
←
Assuming field 'FileType' is equal to MH_OBJECT
→
117 uint64_t Offset = IsObjectFile
4.1
'IsObjectFile' is true
4.1
'IsObjectFile' is true
 ? (HeaderSize + O.Header.SizeOfCmds) : 0;
5
←
'?' condition is true
→
118 for (LoadCommand &LC : O.LoadCommands) {
119 auto &MLC = LC.MachOLoadCommand;
120 StringRef Segname;
121 uint64_t SegmentVmAddr;
122 uint64_t SegmentVmSize;
123 switch (MLC.load_command_data.cmd) {
6
←
Control jumps to 'case LC_SEGMENT:' at line 124
→
124 case MachO::LC_SEGMENT:
125 SegmentVmAddr = MLC.segment_command_data.vmaddr;
126 SegmentVmSize = MLC.segment_command_data.vmsize;
127 Segname = StringRef(MLC.segment_command_data.segname,
128 strnlen(MLC.segment_command_data.segname,
129 sizeof(MLC.segment_command_data.segname)));
130 break;
7
←
 Execution continues on line 142
→
131 case MachO::LC_SEGMENT_64:
132 SegmentVmAddr = MLC.segment_command_64_data.vmaddr;
133 SegmentVmSize = MLC.segment_command_64_data.vmsize;
134 Segname = StringRef(MLC.segment_command_64_data.segname,
135 strnlen(MLC.segment_command_64_data.segname,
136 sizeof(MLC.segment_command_64_data.segname)));
137 break;
138 default:
139 continue;
140 }
141
142 if (Segname == "__LINKEDIT") {
8
←
Assuming the condition is false
→
9
←
Taking false branch
→
143 // We update the __LINKEDIT segment later (in layoutTail).
144 assert(LC.Sections.empty() && "__LINKEDIT segment has sections")((void)0);
145 LinkEditLoadCommand = &MLC;
146 continue;
147 }
148
149 // Update file offsets and sizes of sections.
150 uint64_t SegOffset = Offset;
151 uint64_t SegFileSize = 0;
152 uint64_t VMSize = 0;
153 for (std::unique_ptr<Section> &Sec : LC.Sections) {
154 assert(SegmentVmAddr <= Sec->Addr &&((void)0)
155 "Section's address cannot be smaller than Segment's one")((void)0);
156 uint32_t SectOffset = Sec->Addr - SegmentVmAddr;
157 if (IsObjectFile
9.1
'IsObjectFile' is true
9.1
'IsObjectFile' is true
) {
10
←
Taking true branch
→
158 if (!Sec->hasValidOffset()) {
11
←
Taking false branch
→
159 Sec->Offset = 0;
160 } else {
161 uint64_t PaddingSize =
162 offsetToAlignment(SegFileSize, Align(1ull << Sec->Align));
12
←
Calling 'offsetToAlignment'
→
163 Sec->Offset = SegOffset + SegFileSize + PaddingSize;
164 Sec->Size = Sec->Content.size();
165 SegFileSize += PaddingSize + Sec->Size;
166 }
167 } else {
168 if (!Sec->hasValidOffset()) {
169 Sec->Offset = 0;
170 } else {
171 Sec->Offset = SegOffset + SectOffset;
172 Sec->Size = Sec->Content.size();
173 SegFileSize = std::max(SegFileSize, SectOffset + Sec->Size);
174 }
175 }
176 VMSize = std::max(VMSize, SectOffset + Sec->Size);
177 }
178
179 if (IsObjectFile) {
180 Offset += SegFileSize;
181 } else {
182 Offset = alignTo(Offset + SegFileSize, PageSize);
183 SegFileSize = alignTo(SegFileSize, PageSize);
184 // Use the original vmsize if the segment is __PAGEZERO.
185 VMSize =
186 Segname == "__PAGEZERO" ? SegmentVmSize : alignTo(VMSize, PageSize);
187 }
188
189 switch (MLC.load_command_data.cmd) {
190 case MachO::LC_SEGMENT:
191 MLC.segment_command_data.cmdsize =
192 sizeof(MachO::segment_command) +
193 sizeof(MachO::section) * LC.Sections.size();
194 MLC.segment_command_data.nsects = LC.Sections.size();
195 MLC.segment_command_data.fileoff = SegOffset;
196 MLC.segment_command_data.vmsize = VMSize;
197 MLC.segment_command_data.filesize = SegFileSize;
198 break;
199 case MachO::LC_SEGMENT_64:
200 MLC.segment_command_64_data.cmdsize =
201 sizeof(MachO::segment_command_64) +
202 sizeof(MachO::section_64) * LC.Sections.size();
203 MLC.segment_command_64_data.nsects = LC.Sections.size();
204 MLC.segment_command_64_data.fileoff = SegOffset;
205 MLC.segment_command_64_data.vmsize = VMSize;
206 MLC.segment_command_64_data.filesize = SegFileSize;
207 break;
208 }
209 }
210
211 return Offset;
212}
213
214uint64_t MachOLayoutBuilder::layoutRelocations(uint64_t Offset) {
215 for (LoadCommand &LC : O.LoadCommands)
216 for (std::unique_ptr<Section> &Sec : LC.Sections) {
217 Sec->RelOff = Sec->Relocations.empty() ? 0 : Offset;
218 Sec->NReloc = Sec->Relocations.size();
219 Offset += sizeof(MachO::any_relocation_info) * Sec->NReloc;
220 }
221
222 return Offset;
223}
224
225Error MachOLayoutBuilder::layoutTail(uint64_t Offset) {
226 // If we are building the layout of an executable or dynamic library
227 // which does not have any segments other than __LINKEDIT,
228 // the Offset can be equal to zero by this time. It happens because of the
229 // convention that in such cases the file offsets specified by LC_SEGMENT
230 // start with zero (unlike the case of a relocatable object file).
231 const uint64_t HeaderSize =
232 Is64Bit ? sizeof(MachO::mach_header_64) : sizeof(MachO::mach_header);
233 assert((!(O.Header.FileType == MachO::HeaderFileType::MH_OBJECT) ||((void)0)
234 Offset >= HeaderSize + O.Header.SizeOfCmds) &&((void)0)
235 "Incorrect tail offset")((void)0);
236 Offset = std::max(Offset, HeaderSize + O.Header.SizeOfCmds);
237
238 // The order of LINKEDIT elements is as follows:
239 // rebase info, binding info, weak binding info, lazy binding info, export
240 // trie, data-in-code, symbol table, indirect symbol table, symbol table
241 // strings, code signature.
242 uint64_t NListSize = Is64Bit ? sizeof(MachO::nlist_64) : sizeof(MachO::nlist);
243 uint64_t StartOfLinkEdit = Offset;
244 uint64_t StartOfRebaseInfo = StartOfLinkEdit;
245 uint64_t StartOfBindingInfo = StartOfRebaseInfo + O.Rebases.Opcodes.size();
246 uint64_t StartOfWeakBindingInfo = StartOfBindingInfo + O.Binds.Opcodes.size();
247 uint64_t StartOfLazyBindingInfo =
248 StartOfWeakBindingInfo + O.WeakBinds.Opcodes.size();
249 uint64_t StartOfExportTrie =
250 StartOfLazyBindingInfo + O.LazyBinds.Opcodes.size();
251 uint64_t StartOfFunctionStarts = StartOfExportTrie + O.Exports.Trie.size();
252 uint64_t StartOfDataInCode =
253 StartOfFunctionStarts + O.FunctionStarts.Data.size();
254 uint64_t StartOfLinkerOptimizationHint =
255 StartOfDataInCode + O.DataInCode.Data.size();
256 uint64_t StartOfSymbols =
257 StartOfLinkerOptimizationHint + O.LinkerOptimizationHint.Data.size();
258 uint64_t StartOfIndirectSymbols =
259 StartOfSymbols + NListSize * O.SymTable.Symbols.size();
260 uint64_t StartOfSymbolStrings =
261 StartOfIndirectSymbols +
262 sizeof(uint32_t) * O.IndirectSymTable.Symbols.size();
263 uint64_t StartOfCodeSignature =
264 StartOfSymbolStrings + StrTableBuilder.getSize();
265 if (O.CodeSignatureCommandIndex)
266 StartOfCodeSignature = alignTo(StartOfCodeSignature, 16);
267 uint64_t LinkEditSize =
268 (StartOfCodeSignature + O.CodeSignature.Data.size()) - StartOfLinkEdit;
269
270 // Now we have determined the layout of the contents of the __LINKEDIT
271 // segment. Update its load command.
272 if (LinkEditLoadCommand) {
273 MachO::macho_load_command *MLC = LinkEditLoadCommand;
274 switch (LinkEditLoadCommand->load_command_data.cmd) {
275 case MachO::LC_SEGMENT:
276 MLC->segment_command_data.cmdsize = sizeof(MachO::segment_command);
277 MLC->segment_command_data.fileoff = StartOfLinkEdit;
278 MLC->segment_command_data.vmsize = alignTo(LinkEditSize, PageSize);
279 MLC->segment_command_data.filesize = LinkEditSize;
280 break;
281 case MachO::LC_SEGMENT_64:
282 MLC->segment_command_64_data.cmdsize = sizeof(MachO::segment_command_64);
283 MLC->segment_command_64_data.fileoff = StartOfLinkEdit;
284 MLC->segment_command_64_data.vmsize = alignTo(LinkEditSize, PageSize);
285 MLC->segment_command_64_data.filesize = LinkEditSize;
286 break;
287 }
288 }
289
290 for (LoadCommand &LC : O.LoadCommands) {
291 auto &MLC = LC.MachOLoadCommand;
292 auto cmd = MLC.load_command_data.cmd;
293 switch (cmd) {
294 case MachO::LC_CODE_SIGNATURE:
295 MLC.linkedit_data_command_data.dataoff = StartOfCodeSignature;
296 MLC.linkedit_data_command_data.datasize = O.CodeSignature.Data.size();
297 break;
298 case MachO::LC_SYMTAB:
299 MLC.symtab_command_data.symoff = StartOfSymbols;
300 MLC.symtab_command_data.nsyms = O.SymTable.Symbols.size();
301 MLC.symtab_command_data.stroff = StartOfSymbolStrings;
302 MLC.symtab_command_data.strsize = StrTableBuilder.getSize();
303 break;
304 case MachO::LC_DYSYMTAB: {
305 if (MLC.dysymtab_command_data.ntoc != 0 ||
306 MLC.dysymtab_command_data.nmodtab != 0 ||
307 MLC.dysymtab_command_data.nextrefsyms != 0 ||
308 MLC.dysymtab_command_data.nlocrel != 0 ||
309 MLC.dysymtab_command_data.nextrel != 0)
310 return createStringError(llvm::errc::not_supported,
311 "shared library is not yet supported");
312
313 if (!O.IndirectSymTable.Symbols.empty()) {
314 MLC.dysymtab_command_data.indirectsymoff = StartOfIndirectSymbols;
315 MLC.dysymtab_command_data.nindirectsyms =
316 O.IndirectSymTable.Symbols.size();
317 }
318
319 updateDySymTab(MLC);
320 break;
321 }
322 case MachO::LC_DATA_IN_CODE:
323 MLC.linkedit_data_command_data.dataoff = StartOfDataInCode;
324 MLC.linkedit_data_command_data.datasize = O.DataInCode.Data.size();
325 break;
326 case MachO::LC_LINKER_OPTIMIZATION_HINT:
327 MLC.linkedit_data_command_data.dataoff = StartOfLinkerOptimizationHint;
328 MLC.linkedit_data_command_data.datasize =
329 O.LinkerOptimizationHint.Data.size();
330 break;
331 case MachO::LC_FUNCTION_STARTS:
332 MLC.linkedit_data_command_data.dataoff = StartOfFunctionStarts;
333 MLC.linkedit_data_command_data.datasize = O.FunctionStarts.Data.size();
334 break;
335 case MachO::LC_DYLD_INFO:
336 case MachO::LC_DYLD_INFO_ONLY:
337 MLC.dyld_info_command_data.rebase_off =
338 O.Rebases.Opcodes.empty() ? 0 : StartOfRebaseInfo;
339 MLC.dyld_info_command_data.rebase_size = O.Rebases.Opcodes.size();
340 MLC.dyld_info_command_data.bind_off =
341 O.Binds.Opcodes.empty() ? 0 : StartOfBindingInfo;
342 MLC.dyld_info_command_data.bind_size = O.Binds.Opcodes.size();
343 MLC.dyld_info_command_data.weak_bind_off =
344 O.WeakBinds.Opcodes.empty() ? 0 : StartOfWeakBindingInfo;
345 MLC.dyld_info_command_data.weak_bind_size = O.WeakBinds.Opcodes.size();
346 MLC.dyld_info_command_data.lazy_bind_off =
347 O.LazyBinds.Opcodes.empty() ? 0 : StartOfLazyBindingInfo;
348 MLC.dyld_info_command_data.lazy_bind_size = O.LazyBinds.Opcodes.size();
349 MLC.dyld_info_command_data.export_off =
350 O.Exports.Trie.empty() ? 0 : StartOfExportTrie;
351 MLC.dyld_info_command_data.export_size = O.Exports.Trie.size();
352 break;
353 // Note that LC_ENCRYPTION_INFO.cryptoff despite its name and the comment in
354 // <mach-o/loader.h> is not an offset in the binary file, instead, it is a
355 // relative virtual address. At the moment modification of the __TEXT
356 // segment of executables isn't supported anyway (e.g. data in code entries
357 // are not recalculated). Moreover, in general
358 // LC_ENCRYPT_INFO/LC_ENCRYPTION_INFO_64 are nontrivial to update because
359 // without making additional assumptions (e.g. that the entire __TEXT
360 // segment should be encrypted) we do not know how to recalculate the
361 // boundaries of the encrypted part. For now just copy over these load
362 // commands until we encounter a real world usecase where
363 // LC_ENCRYPT_INFO/LC_ENCRYPTION_INFO_64 need to be adjusted.
364 case MachO::LC_ENCRYPTION_INFO:
365 case MachO::LC_ENCRYPTION_INFO_64:
366 case MachO::LC_LOAD_DYLINKER:
367 case MachO::LC_MAIN:
368 case MachO::LC_RPATH:
369 case MachO::LC_SEGMENT:
370 case MachO::LC_SEGMENT_64:
371 case MachO::LC_VERSION_MIN_MACOSX:
372 case MachO::LC_VERSION_MIN_IPHONEOS:
373 case MachO::LC_VERSION_MIN_TVOS:
374 case MachO::LC_VERSION_MIN_WATCHOS:
375 case MachO::LC_BUILD_VERSION:
376 case MachO::LC_ID_DYLIB:
377 case MachO::LC_LOAD_DYLIB:
378 case MachO::LC_LOAD_WEAK_DYLIB:
379 case MachO::LC_UUID:
380 case MachO::LC_SOURCE_VERSION:
381 case MachO::LC_THREAD:
382 case MachO::LC_UNIXTHREAD:
383 // Nothing to update.
384 break;
385 default:
386 // Abort if it's unsupported in order to prevent corrupting the object.
387 return createStringError(llvm::errc::not_supported,
388 "unsupported load command (cmd=0x%x)", cmd);
389 }
390 }
391
392 return Error::success();
393}
394
395Error MachOLayoutBuilder::layout() {
396 O.Header.NCmds = O.LoadCommands.size();
397 O.Header.SizeOfCmds = computeSizeOfCmds();
398 constructStringTable();
399 updateSymbolIndexes();
400 uint64_t Offset = layoutSegments();
1
Calling 'MachOLayoutBuilder::layoutSegments'
→
401 Offset = layoutRelocations(Offset);
402 return layoutTail(Offset);
403}
←

/usr/src/gnu/usr.bin/clang/llvm-objcopy/../../../llvm/llvm/include/llvm/Support/Alignment.h

1//===-- llvm/Support/Alignment.h - Useful alignment functions ---*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains types to represent alignments.
10// They are instrumented to guarantee some invariants are preserved and prevent
11// invalid manipulations.
12//
13// - Align represents an alignment in bytes, it is always set and always a valid
14// power of two, its minimum value is 1 which means no alignment requirements.
15//
16// - MaybeAlign is an optional type, it may be undefined or set. When it's set
17// you can get the underlying Align type by using the getValue() method.
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_SUPPORT_ALIGNMENT_H_
22#define LLVM_SUPPORT_ALIGNMENT_H_
23
24#include "llvm/ADT/Optional.h"
25#include "llvm/Support/MathExtras.h"
26#include <cassert>
27#ifndef NDEBUG1
28#include <string>
29#endif // NDEBUG
30
31namespace llvm {
32
33#define ALIGN_CHECK_ISPOSITIVE(decl) \
34 assert(decl > 0 && (#decl " should be defined"))((void)0)
35
36/// This struct is a compact representation of a valid (non-zero power of two)
37/// alignment.
38/// It is suitable for use as static global constants.
39struct Align {
40private:
41 uint8_t ShiftValue = 0; /// The log2 of the required alignment.
42 /// ShiftValue is less than 64 by construction.
43
44 friend struct MaybeAlign;
45 friend unsigned Log2(Align);
46 friend bool operator==(Align Lhs, Align Rhs);
47 friend bool operator!=(Align Lhs, Align Rhs);
48 friend bool operator<=(Align Lhs, Align Rhs);
49 friend bool operator>=(Align Lhs, Align Rhs);
50 friend bool operator<(Align Lhs, Align Rhs);
51 friend bool operator>(Align Lhs, Align Rhs);
52 friend unsigned encode(struct MaybeAlign A);
53 friend struct MaybeAlign decodeMaybeAlign(unsigned Value);
54
55 /// A trivial type to allow construction of constexpr Align.
56 /// This is currently needed to workaround a bug in GCC 5.3 which prevents
57 /// definition of constexpr assign operators.
58 /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic
59 /// FIXME: Remove this, make all assign operators constexpr and introduce user
60 /// defined literals when we don't have to support GCC 5.3 anymore.
61 /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain
62 struct LogValue {
63 uint8_t Log;
64 };
65
66public:
67 /// Default is byte-aligned.
68 constexpr Align() = default;
69 /// Do not perform checks in case of copy/move construct/assign, because the
70 /// checks have been performed when building `Other`.
71 constexpr Align(const Align &Other) = default;
72 constexpr Align(Align &&Other) = default;
73 Align &operator=(const Align &Other) = default;
74 Align &operator=(Align &&Other) = default;
75
76 explicit Align(uint64_t Value) {
77 assert(Value > 0 && "Value must not be 0")((void)0);
78 assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2")((void)0);
79 ShiftValue = Log2_64(Value);
80 assert(ShiftValue < 64 && "Broken invariant")((void)0);
81 }
82
83 /// This is a hole in the type system and should not be abused.
84 /// Needed to interact with C for instance.
85 uint64_t value() const { return uint64_t(1) << ShiftValue; }
16
←
The result of the left shift is undefined due to shifting by '255', which is greater or equal to the width of type 'uint64_t'
86
87 /// Allow constructions of constexpr Align.
88 template <size_t kValue> constexpr static LogValue Constant() {
89 return LogValue{static_cast<uint8_t>(CTLog2<kValue>())};
90 }
91
92 /// Allow constructions of constexpr Align from types.
93 /// Compile time equivalent to Align(alignof(T)).
94 template <typename T> constexpr static LogValue Of() {
95 return Constant<std::alignment_of<T>::value>();
96 }
97
98 /// Constexpr constructor from LogValue type.
99 constexpr Align(LogValue CA) : ShiftValue(CA.Log) {}
100};
101
102/// Treats the value 0 as a 1, so Align is always at least 1.
103inline Align assumeAligned(uint64_t Value) {
104 return Value ? Align(Value) : Align();
105}
106
107/// This struct is a compact representation of a valid (power of two) or
108/// undefined (0) alignment.
109struct MaybeAlign : public llvm::Optional<Align> {
110private:
111 using UP = llvm::Optional<Align>;
112
113public:
114 /// Default is undefined.
115 MaybeAlign() = default;
116 /// Do not perform checks in case of copy/move construct/assign, because the
117 /// checks have been performed when building `Other`.
118 MaybeAlign(const MaybeAlign &Other) = default;
119 MaybeAlign &operator=(const MaybeAlign &Other) = default;
120 MaybeAlign(MaybeAlign &&Other) = default;
121 MaybeAlign &operator=(MaybeAlign &&Other) = default;
122
123 /// Use llvm::Optional<Align> constructor.
124 using UP::UP;
125
126 explicit MaybeAlign(uint64_t Value) {
127 assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&((void)0)
128 "Alignment is neither 0 nor a power of 2")((void)0);
129 if (Value)
130 emplace(Value);
131 }
132
133 /// For convenience, returns a valid alignment or 1 if undefined.
134 Align valueOrOne() const { return hasValue() ? getValue() : Align(); }
135};
136
137/// Checks that SizeInBytes is a multiple of the alignment.
138inline bool isAligned(Align Lhs, uint64_t SizeInBytes) {
139 return SizeInBytes % Lhs.value() == 0;
140}
141
142/// Checks that Addr is a multiple of the alignment.
143inline bool isAddrAligned(Align Lhs, const void *Addr) {
144 return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr));
145}
146
147/// Returns a multiple of A needed to store `Size` bytes.
148inline uint64_t alignTo(uint64_t Size, Align A) {
149 const uint64_t Value = A.value();
15
←
Calling 'Align::value'
→
150 // The following line is equivalent to `(Size + Value - 1) / Value * Value`.
151
152 // The division followed by a multiplication can be thought of as a right
153 // shift followed by a left shift which zeros out the extra bits produced in
154 // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out
155 // are just zero.
156
157 // Most compilers can generate this code but the pattern may be missed when
158 // multiple functions gets inlined.
159 return (Size + Value - 1) & ~(Value - 1U);
160}
161
162/// If non-zero \p Skew is specified, the return value will be a minimal integer
163/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
164/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
165/// Skew mod \p A'.
166///
167/// Examples:
168/// \code
169/// alignTo(5, Align(8), 7) = 7
170/// alignTo(17, Align(8), 1) = 17
171/// alignTo(~0LL, Align(8), 3) = 3
172/// \endcode
173inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) {
174 const uint64_t Value = A.value();
175 Skew %= Value;
176 return ((Size + Value - 1 - Skew) & ~(Value - 1U)) + Skew;
177}
178
179/// Returns a multiple of A needed to store `Size` bytes.
180/// Returns `Size` if current alignment is undefined.
181inline uint64_t alignTo(uint64_t Size, MaybeAlign A) {
182 return A ? alignTo(Size, A.getValue()) : Size;
183}
184
185/// Aligns `Addr` to `Alignment` bytes, rounding up.
186inline uintptr_t alignAddr(const void *Addr, Align Alignment) {
187 uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr);
188 assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=((void)0)
189 ArithAddr &&((void)0)
190 "Overflow")((void)0);
191 return alignTo(ArithAddr, Alignment);
192}
193
194/// Returns the offset to the next integer (mod 2**64) that is greater than
195/// or equal to \p Value and is a multiple of \p Align.
196inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
197 return alignTo(Value, Alignment) - Value;
13
←
The value 255 is assigned to 'A.ShiftValue'
→
14
←
Calling 'alignTo'
→
198}
199
200/// Returns the necessary adjustment for aligning `Addr` to `Alignment`
201/// bytes, rounding up.
202inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
203 return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
204}
205
206/// Returns the log2 of the alignment.
207inline unsigned Log2(Align A) { return A.ShiftValue; }
208
209/// Returns the alignment that satisfies both alignments.
210/// Same semantic as MinAlign.
211inline Align commonAlignment(Align A, Align B) { return std::min(A, B); }
212
213/// Returns the alignment that satisfies both alignments.
214/// Same semantic as MinAlign.
215inline Align commonAlignment(Align A, uint64_t Offset) {
216 return Align(MinAlign(A.value(), Offset));
217}
218
219/// Returns the alignment that satisfies both alignments.
220/// Same semantic as MinAlign.
221inline MaybeAlign commonAlignment(MaybeAlign A, MaybeAlign B) {
222 return A && B ? commonAlignment(*A, *B) : A ? A : B;
223}
224
225/// Returns the alignment that satisfies both alignments.
226/// Same semantic as MinAlign.
227inline MaybeAlign commonAlignment(MaybeAlign A, uint64_t Offset) {
228 return MaybeAlign(MinAlign((*A).value(), Offset));
229}
230
231/// Returns a representation of the alignment that encodes undefined as 0.
232inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
233
234/// Dual operation of the encode function above.
235inline MaybeAlign decodeMaybeAlign(unsigned Value) {
236 if (Value == 0)
237 return MaybeAlign();
238 Align Out;
239 Out.ShiftValue = Value - 1;
240 return Out;
241}
242
243/// Returns a representation of the alignment, the encoded value is positive by
244/// definition.
245inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }
246
247/// Comparisons between Align and scalars. Rhs must be positive.
248inline bool operator==(Align Lhs, uint64_t Rhs) {
249 ALIGN_CHECK_ISPOSITIVE(Rhs);
250 return Lhs.value() == Rhs;
251}
252inline bool operator!=(Align Lhs, uint64_t Rhs) {
253 ALIGN_CHECK_ISPOSITIVE(Rhs);
254 return Lhs.value() != Rhs;
255}
256inline bool operator<=(Align Lhs, uint64_t Rhs) {
257 ALIGN_CHECK_ISPOSITIVE(Rhs);
258 return Lhs.value() <= Rhs;
259}
260inline bool operator>=(Align Lhs, uint64_t Rhs) {
261 ALIGN_CHECK_ISPOSITIVE(Rhs);
262 return Lhs.value() >= Rhs;
263}
264inline bool operator<(Align Lhs, uint64_t Rhs) {
265 ALIGN_CHECK_ISPOSITIVE(Rhs);
266 return Lhs.value() < Rhs;
267}
268inline bool operator>(Align Lhs, uint64_t Rhs) {
269 ALIGN_CHECK_ISPOSITIVE(Rhs);
270 return Lhs.value() > Rhs;
271}
272
273/// Comparisons between MaybeAlign and scalars.
274inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) {
275 return Lhs ? (*Lhs).value() == Rhs : Rhs == 0;
276}
277inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) {
278 return Lhs ? (*Lhs).value() != Rhs : Rhs != 0;
279}
280
281/// Comparisons operators between Align.
282inline bool operator==(Align Lhs, Align Rhs) {
283 return Lhs.ShiftValue == Rhs.ShiftValue;
284}
285inline bool operator!=(Align Lhs, Align Rhs) {
286 return Lhs.ShiftValue != Rhs.ShiftValue;
287}
288inline bool operator<=(Align Lhs, Align Rhs) {
289 return Lhs.ShiftValue <= Rhs.ShiftValue;
290}
291inline bool operator>=(Align Lhs, Align Rhs) {
292 return Lhs.ShiftValue >= Rhs.ShiftValue;
293}
294inline bool operator<(Align Lhs, Align Rhs) {
295 return Lhs.ShiftValue < Rhs.ShiftValue;
296}
297inline bool operator>(Align Lhs, Align Rhs) {
298 return Lhs.ShiftValue > Rhs.ShiftValue;
299}
300
301// Don't allow relational comparisons with MaybeAlign.
302bool operator<=(Align Lhs, MaybeAlign Rhs) = delete;
303bool operator>=(Align Lhs, MaybeAlign Rhs) = delete;
304bool operator<(Align Lhs, MaybeAlign Rhs) = delete;
305bool operator>(Align Lhs, MaybeAlign Rhs) = delete;
306
307bool operator<=(MaybeAlign Lhs, Align Rhs) = delete;
308bool operator>=(MaybeAlign Lhs, Align Rhs) = delete;
309bool operator<(MaybeAlign Lhs, Align Rhs) = delete;
310bool operator>(MaybeAlign Lhs, Align Rhs) = delete;
311
312bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
313bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
314bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
315bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
316
317inline Align operator*(Align Lhs, uint64_t Rhs) {
318 assert(Rhs > 0 && "Rhs must be positive")((void)0);
319 return Align(Lhs.value() * Rhs);
320}
321
322inline MaybeAlign operator*(MaybeAlign Lhs, uint64_t Rhs) {
323 assert(Rhs > 0 && "Rhs must be positive")((void)0);
324 return Lhs ? Lhs.getValue() * Rhs : MaybeAlign();
325}
326
327inline Align operator/(Align Lhs, uint64_t Divisor) {
328 assert(llvm::isPowerOf2_64(Divisor) &&((void)0)
329 "Divisor must be positive and a power of 2")((void)0);
330 assert(Lhs != 1 && "Can't halve byte alignment")((void)0);
331 return Align(Lhs.value() / Divisor);
332}
333
334inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) {
335 assert(llvm::isPowerOf2_64(Divisor) &&((void)0)
336 "Divisor must be positive and a power of 2")((void)0);
337 return Lhs ? Lhs.getValue() / Divisor : MaybeAlign();
338}
339
340inline Align max(MaybeAlign Lhs, Align Rhs) {
341 return Lhs && *Lhs > Rhs ? *Lhs : Rhs;
342}
343
344inline Align max(Align Lhs, MaybeAlign Rhs) {
345 return Rhs && *Rhs > Lhs ? *Rhs : Lhs;
346}
347
348#ifndef NDEBUG1
349// For usage in LLVM_DEBUG macros.
350inline std::string DebugStr(const Align &A) {
351 return std::to_string(A.value());
352}
353// For usage in LLVM_DEBUG macros.
354inline std::string DebugStr(const MaybeAlign &MA) {
355 if (MA)
356 return std::to_string(MA->value());
357 return "None";
358}
359#endif // NDEBUG
360
361#undef ALIGN_CHECK_ISPOSITIVE
362
363} // namespace llvm
364
365#endif // LLVM_SUPPORT_ALIGNMENT_H_