1//==-------- DynamicAllocator.cpp - Dynamic allocations ----------*- 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 "DynamicAllocator.h"
10#include "InterpBlock.h"
11#include "InterpState.h"
12
13using namespace clang;
14using namespace clang::interp;
15
16DynamicAllocator::~DynamicAllocator() { cleanup(); }
17
18void DynamicAllocator::cleanup() {
19 // Invoke destructors of all the blocks and as a last restort,
20 // reset all the pointers pointing to them to null pointees.
21 // This should never show up in diagnostics, but it's necessary
22 // for us to not cause use-after-free problems.
23 for (auto &Iter : AllocationSites) {
24 auto &AllocSite = Iter.second;
25 for (auto &Alloc : AllocSite.Allocations) {
26 Block *B = Alloc.block();
27 assert(!B->isDead());
28 assert(B->isInitialized());
29 B->invokeDtor();
30 B->removePointers();
31 }
32 }
33
34 AllocationSites.clear();
35}
36
37Block *DynamicAllocator::allocate(const Expr *Source, PrimType T,
38 size_t NumElements, unsigned EvalID,
39 Form AllocForm) {
40 // Create a new descriptor for an array of the specified size and
41 // element type.
42 const Descriptor *D =
43 allocateDescriptor(Args&: Source, Args: nullptr, Args&: T, Args: Descriptor::InlineDescMD,
44 Args&: NumElements, /*IsConst=*/Args: false,
45 /*IsTemporary=*/Args: false, /*IsMutable=*/Args: false,
46 /*IsVolatile=*/Args: false);
47
48 return allocate(D, EvalID, AllocForm);
49}
50
51Block *DynamicAllocator::allocate(const Descriptor *ElementDesc,
52 size_t NumElements, unsigned EvalID,
53 Form AllocForm) {
54 assert(ElementDesc->getMetadataSize() == 0);
55 // Create a new descriptor for an array of the specified size and
56 // element type.
57 // FIXME: Pass proper element type.
58 const Descriptor *D = allocateDescriptor(
59 Args: ElementDesc->asExpr(), Args: nullptr, Args&: ElementDesc, Args: Descriptor::InlineDescMD,
60 Args&: NumElements,
61 /*IsConst=*/Args: false, /*IsTemporary=*/Args: false, /*IsMutable=*/Args: false);
62 return allocate(D, EvalID, AllocForm);
63}
64
65Block *DynamicAllocator::allocate(const Descriptor *D, unsigned EvalID,
66 Form AllocForm) {
67 assert(D);
68 assert(D->asExpr());
69
70 // Garbage collection. Remove all dead allocations that don't have pointers to
71 // them anymore.
72 llvm::erase_if(C&: DeadAllocations, P: [](Allocation &Alloc) -> bool {
73 return !Alloc.block()->hasPointers();
74 });
75
76 auto Memory =
77 std::make_unique<std::byte[]>(num: sizeof(Block) + D->getAllocSize());
78 auto *B = new (Memory.get()) Block(EvalID, D, /*isStatic=*/false);
79 B->invokeCtorNoMemset();
80
81 assert(D->getMetadataSize() == sizeof(InlineDescriptor));
82 InlineDescriptor *ID = reinterpret_cast<InlineDescriptor *>(B->rawData());
83 ID->Desc = D;
84 ID->IsActive = true;
85 ID->Offset = sizeof(InlineDescriptor);
86 ID->IsBase = false;
87 ID->IsFieldMutable = false;
88 ID->IsConst = false;
89 ID->IsInitialized = false;
90 ID->IsVolatile = false;
91
92 if (D->isCompositeArray())
93 ID->LifeState = Lifetime::Started;
94 else
95 ID->LifeState =
96 AllocForm == Form::Operator ? Lifetime::Ended : Lifetime::Started;
97
98 if (auto It = AllocationSites.find(Val: D->asExpr());
99 It != AllocationSites.end()) {
100 It->second.Allocations.emplace_back(Args: std::move(Memory));
101 B->setDynAllocId(It->second.NumAllocs);
102 ++It->second.NumAllocs;
103 } else {
104 AllocationSites.insert(
105 KV: {D->asExpr(), AllocationSite(std::move(Memory), AllocForm)});
106 B->setDynAllocId(0);
107 }
108 assert(B->isDynamic());
109 return B;
110}
111
112bool DynamicAllocator::deallocate(const Expr *Source,
113 const Block *BlockToDelete) {
114 auto It = AllocationSites.find(Val: Source);
115 if (It == AllocationSites.end())
116 return false;
117
118 auto &Site = It->second;
119 assert(!Site.empty());
120
121 // Find the Block to delete.
122 auto *AllocIt = llvm::find_if(Range&: Site.Allocations, P: [&](const Allocation &A) {
123 return BlockToDelete == A.block();
124 });
125
126 // The allocation site it fine, but this block doesn't belong to it. Must've
127 // already been deleted.
128 if (AllocIt == Site.Allocations.end())
129 return false;
130
131 Block *B = AllocIt->block();
132 assert(B->isInitialized());
133 assert(!B->isDead());
134 B->invokeDtor();
135
136 // Almost all our dynamic allocations have a pointer pointing to them
137 // when we deallocate them, since otherwise we can't call delete() at all.
138 // This means that we would usually need to create DeadBlocks for all of them.
139 // To work around that, we instead mark them as dead without moving the data
140 // over to a DeadBlock and simply keep the block in a separate DeadAllocations
141 // list.
142 if (B->hasPointers()) {
143 B->AccessFlags |= Block::DeadFlag;
144 DeadAllocations.push_back(Elt: std::move(*AllocIt));
145 Site.Allocations.erase(CI: AllocIt);
146
147 if (Site.size() == 0)
148 AllocationSites.erase(I: It);
149 return true;
150 }
151
152 // Get rid of the allocation altogether.
153 Site.Allocations.erase(CI: AllocIt);
154 if (Site.empty())
155 AllocationSites.erase(I: It);
156
157 return true;
158}
159