-
Notifications
You must be signed in to change notification settings - Fork 10.8k
/
TUScheduler.cpp
1871 lines (1714 loc) · 71.7 KB
/
TUScheduler.cpp
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
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//===--- TUScheduler.cpp -----------------------------------------*-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
//
//===----------------------------------------------------------------------===//
// TUScheduler manages a worker per active file. This ASTWorker processes
// updates (modifications to file contents) and reads (actions performed on
// preamble/AST) to the file.
//
// Each ASTWorker owns a dedicated thread to process updates and reads to the
// relevant file. Any request gets queued in FIFO order to be processed by that
// thread.
//
// An update request replaces current praser inputs to ensure any subsequent
// read sees the version of the file they were requested. It will also issue a
// build for new inputs.
//
// ASTWorker processes the file in two parts, a preamble and a main-file
// section. A preamble can be reused between multiple versions of the file until
// invalidated by a modification to a header, compile commands or modification
// to relevant part of the current file. Such a preamble is called compatible.
// An update is considered dead if no read was issued for that version and
// diagnostics weren't requested by client or could be generated for a later
// version of the file. ASTWorker eliminates such requests as they are
// redundant.
//
// In the presence of stale (non-compatible) preambles, ASTWorker won't publish
// diagnostics for update requests. Read requests will be served with ASTs build
// with stale preambles, unless the read is picky and requires a compatible
// preamble. In such cases it will block until new preamble is built.
//
// ASTWorker owns a PreambleThread for building preambles. If the preamble gets
// invalidated by an update request, a new build will be requested on
// PreambleThread. Since PreambleThread only receives requests for newer
// versions of the file, in case of multiple requests it will only build the
// last one and skip requests in between. Unless client force requested
// diagnostics(WantDiagnostics::Yes).
//
// When a new preamble is built, a "golden" AST is immediately built from that
// version of the file. This ensures diagnostics get updated even if the queue
// is full.
//
// Some read requests might just need preamble. Since preambles can be read
// concurrently, ASTWorker runs these requests on their own thread. These
// requests will receive latest build preamble, which might possibly be stale.
#include "TUScheduler.h"
#include "CompileCommands.h"
#include "Compiler.h"
#include "Config.h"
#include "Diagnostics.h"
#include "GlobalCompilationDatabase.h"
#include "ParsedAST.h"
#include "Preamble.h"
#include "clang-include-cleaner/Record.h"
#include "support/Cancellation.h"
#include "support/Context.h"
#include "support/Logger.h"
#include "support/MemoryTree.h"
#include "support/Path.h"
#include "support/ThreadCrashReporter.h"
#include "support/Threading.h"
#include "support/Trace.h"
#include "clang/Basic/Stack.h"
#include "clang/Frontend/CompilerInvocation.h"
#include "clang/Tooling/CompilationDatabase.h"
#include "llvm/ADT/FunctionExtras.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Errc.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/Threading.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <functional>
#include <memory>
#include <mutex>
#include <optional>
#include <queue>
#include <string>
#include <thread>
#include <type_traits>
#include <utility>
#include <vector>
namespace clang {
namespace clangd {
using std::chrono::steady_clock;
namespace {
// Tracks latency (in seconds) of FS operations done during a preamble build.
// build_type allows to split by expected VFS cache state (cold on first
// preamble, somewhat warm after that when building first preamble for new file,
// likely ~everything cached on preamble rebuild.
constexpr trace::Metric
PreambleBuildFilesystemLatency("preamble_fs_latency",
trace::Metric::Distribution, "build_type");
// Tracks latency of FS operations done during a preamble build as a ratio of
// preamble build time. build_type is same as above.
constexpr trace::Metric PreambleBuildFilesystemLatencyRatio(
"preamble_fs_latency_ratio", trace::Metric::Distribution, "build_type");
constexpr trace::Metric PreambleBuildSize("preamble_build_size",
trace::Metric::Distribution);
constexpr trace::Metric PreambleSerializedSize("preamble_serialized_size",
trace::Metric::Distribution);
void reportPreambleBuild(const PreambleBuildStats &Stats,
bool IsFirstPreamble) {
auto RecordWithLabel = [&Stats](llvm::StringRef Label) {
PreambleBuildFilesystemLatency.record(Stats.FileSystemTime, Label);
if (Stats.TotalBuildTime > 0) // Avoid division by zero.
PreambleBuildFilesystemLatencyRatio.record(
Stats.FileSystemTime / Stats.TotalBuildTime, Label);
};
static llvm::once_flag OnceFlag;
llvm::call_once(OnceFlag, [&] { RecordWithLabel("first_build"); });
RecordWithLabel(IsFirstPreamble ? "first_build_for_file" : "rebuild");
PreambleBuildSize.record(Stats.BuildSize);
PreambleSerializedSize.record(Stats.SerializedSize);
}
class ASTWorker;
} // namespace
static clang::clangd::Key<std::string> FileBeingProcessed;
std::optional<llvm::StringRef> TUScheduler::getFileBeingProcessedInContext() {
if (auto *File = Context::current().get(FileBeingProcessed))
return llvm::StringRef(*File);
return std::nullopt;
}
/// An LRU cache of idle ASTs.
/// Because we want to limit the overall number of these we retain, the cache
/// owns ASTs (and may evict them) while their workers are idle.
/// Workers borrow ASTs when active, and return them when done.
class TUScheduler::ASTCache {
public:
using Key = const ASTWorker *;
ASTCache(unsigned MaxRetainedASTs) : MaxRetainedASTs(MaxRetainedASTs) {}
/// Returns result of getUsedBytes() for the AST cached by \p K.
/// If no AST is cached, 0 is returned.
std::size_t getUsedBytes(Key K) {
std::lock_guard<std::mutex> Lock(Mut);
auto It = findByKey(K);
if (It == LRU.end() || !It->second)
return 0;
return It->second->getUsedBytes();
}
/// Store the value in the pool, possibly removing the last used AST.
/// The value should not be in the pool when this function is called.
void put(Key K, std::unique_ptr<ParsedAST> V) {
std::unique_lock<std::mutex> Lock(Mut);
assert(findByKey(K) == LRU.end());
LRU.insert(LRU.begin(), {K, std::move(V)});
if (LRU.size() <= MaxRetainedASTs)
return;
// We're past the limit, remove the last element.
std::unique_ptr<ParsedAST> ForCleanup = std::move(LRU.back().second);
LRU.pop_back();
// Run the expensive destructor outside the lock.
Lock.unlock();
ForCleanup.reset();
}
/// Returns the cached value for \p K, or std::nullopt if the value is not in
/// the cache anymore. If nullptr was cached for \p K, this function will
/// return a null unique_ptr wrapped into an optional.
/// If \p AccessMetric is set records whether there was a hit or miss.
std::optional<std::unique_ptr<ParsedAST>>
take(Key K, const trace::Metric *AccessMetric = nullptr) {
// Record metric after unlocking the mutex.
std::unique_lock<std::mutex> Lock(Mut);
auto Existing = findByKey(K);
if (Existing == LRU.end()) {
if (AccessMetric)
AccessMetric->record(1, "miss");
return std::nullopt;
}
if (AccessMetric)
AccessMetric->record(1, "hit");
std::unique_ptr<ParsedAST> V = std::move(Existing->second);
LRU.erase(Existing);
// GCC 4.8 fails to compile `return V;`, as it tries to call the copy
// constructor of unique_ptr, so we call the move ctor explicitly to avoid
// this miscompile.
return std::optional<std::unique_ptr<ParsedAST>>(std::move(V));
}
private:
using KVPair = std::pair<Key, std::unique_ptr<ParsedAST>>;
std::vector<KVPair>::iterator findByKey(Key K) {
return llvm::find_if(LRU, [K](const KVPair &P) { return P.first == K; });
}
std::mutex Mut;
unsigned MaxRetainedASTs;
/// Items sorted in LRU order, i.e. first item is the most recently accessed
/// one.
std::vector<KVPair> LRU; /* GUARDED_BY(Mut) */
};
/// A map from header files to an opened "proxy" file that includes them.
/// If you open the header, the compile command from the proxy file is used.
///
/// This inclusion information could also naturally live in the index, but there
/// are advantages to using open files instead:
/// - it's easier to achieve a *stable* choice of proxy, which is important
/// to avoid invalidating the preamble
/// - context-sensitive flags for libraries with multiple configurations
/// (e.g. C++ stdlib sensitivity to -std version)
/// - predictable behavior, e.g. guarantees that go-to-def landing on a header
/// will have a suitable command available
/// - fewer scaling problems to solve (project include graphs are big!)
///
/// Implementation details:
/// - We only record this for mainfiles where the command was trustworthy
/// (i.e. not inferred). This avoids a bad inference "infecting" other files.
/// - Once we've picked a proxy file for a header, we stick with it until the
/// proxy file is invalidated *and* a new candidate proxy file is built.
/// Switching proxies is expensive, as the compile flags will (probably)
/// change and therefore we'll end up rebuilding the header's preamble.
/// - We don't capture the actual compile command, but just the filename we
/// should query to get it. This avoids getting out of sync with the CDB.
///
/// All methods are threadsafe. In practice, update() comes from preamble
/// threads, remove()s mostly from the main thread, and get() from ASTWorker.
/// Writes are rare and reads are cheap, so we don't expect much contention.
class TUScheduler::HeaderIncluderCache {
// We should be a little careful how we store the include graph of open
// files, as each can have a large number of transitive headers.
// This representation is O(unique transitive source files).
llvm::BumpPtrAllocator Arena;
struct Association {
llvm::StringRef MainFile;
// Circular-linked-list of associations with the same mainFile.
// Null indicates that the mainfile was removed.
Association *Next;
};
llvm::StringMap<Association, llvm::BumpPtrAllocator &> HeaderToMain;
llvm::StringMap<Association *, llvm::BumpPtrAllocator &> MainToFirst;
std::atomic<size_t> UsedBytes; // Updated after writes.
mutable std::mutex Mu;
void invalidate(Association *First) {
Association *Current = First;
do {
Association *Next = Current->Next;
Current->Next = nullptr;
Current = Next;
} while (Current != First);
}
// Create the circular list and return the head of it.
Association *associate(llvm::StringRef MainFile,
llvm::ArrayRef<std::string> Headers) {
Association *First = nullptr, *Prev = nullptr;
for (const std::string &Header : Headers) {
auto &Assoc = HeaderToMain[Header];
if (Assoc.Next)
continue; // Already has a valid association.
Assoc.MainFile = MainFile;
Assoc.Next = Prev;
Prev = &Assoc;
if (!First)
First = &Assoc;
}
if (First)
First->Next = Prev;
return First;
}
void updateMemoryUsage() {
auto StringMapHeap = [](const auto &Map) {
// StringMap stores the hashtable on the heap.
// It contains pointers to the entries, and a hashcode for each.
return Map.getNumBuckets() * (sizeof(void *) + sizeof(unsigned));
};
size_t Usage = Arena.getTotalMemory() + StringMapHeap(MainToFirst) +
StringMapHeap(HeaderToMain) + sizeof(*this);
UsedBytes.store(Usage, std::memory_order_release);
}
public:
HeaderIncluderCache() : HeaderToMain(Arena), MainToFirst(Arena) {
updateMemoryUsage();
}
// Associate each header with MainFile (unless already associated).
// Headers not in the list will have their associations removed.
void update(PathRef MainFile, llvm::ArrayRef<std::string> Headers) {
std::lock_guard<std::mutex> Lock(Mu);
auto It = MainToFirst.try_emplace(MainFile, nullptr);
Association *&First = It.first->second;
if (First)
invalidate(First);
First = associate(It.first->first(), Headers);
updateMemoryUsage();
}
// Mark MainFile as gone.
// This will *not* disassociate headers with MainFile immediately, but they
// will be eligible for association with other files that get update()d.
void remove(PathRef MainFile) {
std::lock_guard<std::mutex> Lock(Mu);
Association *&First = MainToFirst[MainFile];
if (First) {
invalidate(First);
First = nullptr;
}
// MainToFirst entry should stay alive, as Associations might be pointing at
// its key.
}
/// Get the mainfile associated with Header, or the empty string if none.
std::string get(PathRef Header) const {
std::lock_guard<std::mutex> Lock(Mu);
return HeaderToMain.lookup(Header).MainFile.str();
}
size_t getUsedBytes() const {
return UsedBytes.load(std::memory_order_acquire);
}
};
namespace {
bool isReliable(const tooling::CompileCommand &Cmd) {
return Cmd.Heuristic.empty();
}
/// Threadsafe manager for updating a TUStatus and emitting it after each
/// update.
class SynchronizedTUStatus {
public:
SynchronizedTUStatus(PathRef FileName, ParsingCallbacks &Callbacks)
: FileName(FileName), Callbacks(Callbacks) {}
void update(llvm::function_ref<void(TUStatus &)> Mutator) {
std::lock_guard<std::mutex> Lock(StatusMu);
Mutator(Status);
emitStatusLocked();
}
/// Prevents emitting of further updates.
void stop() {
std::lock_guard<std::mutex> Lock(StatusMu);
CanPublish = false;
}
private:
void emitStatusLocked() {
if (CanPublish)
Callbacks.onFileUpdated(FileName, Status);
}
const Path FileName;
std::mutex StatusMu;
TUStatus Status;
bool CanPublish = true;
ParsingCallbacks &Callbacks;
};
// An attempt to acquire resources for a task using PreambleThrottler.
// Initially it is unsatisfied, it (hopefully) becomes satisfied later but may
// be destroyed before then. Destruction releases all resources.
class PreambleThrottlerRequest {
public:
// The condition variable is signalled when the request is satisfied.
PreambleThrottlerRequest(llvm::StringRef Filename,
PreambleThrottler *Throttler,
std::condition_variable &CV)
: Throttler(Throttler),
Satisfied(Throttler == nullptr) {
// If there is no throttler, this dummy request is always satisfied.
if (!Throttler)
return;
ID = Throttler->acquire(Filename, [&] {
Satisfied.store(true, std::memory_order_release);
CV.notify_all();
});
}
bool satisfied() const { return Satisfied.load(std::memory_order_acquire); }
// When the request is destroyed:
// - if resources are not yet obtained, stop trying to get them.
// - if resources were obtained, release them.
~PreambleThrottlerRequest() {
if (Throttler)
Throttler->release(ID);
}
private:
PreambleThrottler::RequestID ID;
PreambleThrottler *Throttler;
std::atomic<bool> Satisfied = {false};
};
/// Responsible for building preambles. Whenever the thread is idle and the
/// preamble is outdated, it starts to build a fresh preamble from the latest
/// inputs. If RunSync is true, preambles are built synchronously in update()
/// instead.
class PreambleThread {
public:
PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks,
bool StorePreambleInMemory, bool RunSync,
PreambleThrottler *Throttler, SynchronizedTUStatus &Status,
TUScheduler::HeaderIncluderCache &HeaderIncluders,
ASTWorker &AW)
: FileName(FileName), Callbacks(Callbacks),
StoreInMemory(StorePreambleInMemory), RunSync(RunSync),
Throttler(Throttler), Status(Status), ASTPeer(AW),
HeaderIncluders(HeaderIncluders) {}
/// It isn't guaranteed that each requested version will be built. If there
/// are multiple update requests while building a preamble, only the last one
/// will be built.
void update(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
std::vector<Diag> CIDiags, WantDiagnostics WantDiags) {
Request Req = {std::move(CI), std::move(PI), std::move(CIDiags), WantDiags,
Context::current().clone()};
if (RunSync) {
build(std::move(Req));
Status.update([](TUStatus &Status) {
Status.PreambleActivity = PreambleAction::Idle;
});
return;
}
{
std::unique_lock<std::mutex> Lock(Mutex);
// If NextReq was requested with WantDiagnostics::Yes we cannot just drop
// that on the floor. Block until we start building it. This won't
// dead-lock as we are blocking the caller thread, while builds continue
// on preamble thread.
ReqCV.wait(Lock, [this] {
return !NextReq || NextReq->WantDiags != WantDiagnostics::Yes;
});
NextReq = std::move(Req);
}
// Let the worker thread know there's a request, notify_one is safe as there
// should be a single worker thread waiting on it.
ReqCV.notify_all();
}
void run() {
// We mark the current as the stack bottom so that clang running on this
// thread can notice the stack usage and prevent stack overflow with best
// efforts. Same applies to other calls thoughout clangd.
clang::noteBottomOfStack();
while (true) {
std::optional<PreambleThrottlerRequest> Throttle;
{
std::unique_lock<std::mutex> Lock(Mutex);
assert(!CurrentReq && "Already processing a request?");
// Wait until stop is called or there is a request.
ReqCV.wait(Lock, [&] { return NextReq || Done; });
if (Done)
break;
{
Throttle.emplace(FileName, Throttler, ReqCV);
std::optional<trace::Span> Tracer;
// If acquire succeeded synchronously, avoid status jitter.
if (!Throttle->satisfied()) {
Tracer.emplace("PreambleThrottle");
Status.update([&](TUStatus &Status) {
Status.PreambleActivity = PreambleAction::Queued;
});
}
ReqCV.wait(Lock, [&] { return Throttle->satisfied() || Done; });
}
if (Done)
break;
// While waiting for the throttler, the request may have been updated!
// That's fine though, there's still guaranteed to be some request.
CurrentReq = std::move(*NextReq);
NextReq.reset();
}
{
WithContext Guard(std::move(CurrentReq->Ctx));
// Note that we don't make use of the ContextProvider here.
// Preamble tasks are always scheduled by ASTWorker tasks, and we
// reuse the context/config that was created at that level.
// Build the preamble and let the waiters know about it.
build(std::move(*CurrentReq));
}
// Releasing the throttle before destroying the request assists testing.
Throttle.reset();
bool IsEmpty = false;
{
std::lock_guard<std::mutex> Lock(Mutex);
CurrentReq.reset();
IsEmpty = !NextReq;
}
if (IsEmpty) {
// We don't perform this above, before waiting for a request to make
// tests more deterministic. As there can be a race between this thread
// and client thread(clangdserver).
Status.update([](TUStatus &Status) {
Status.PreambleActivity = PreambleAction::Idle;
});
}
ReqCV.notify_all();
}
dlog("Preamble worker for {0} stopped", FileName);
}
/// Signals the run loop to exit.
void stop() {
dlog("Preamble worker for {0} received stop", FileName);
{
std::lock_guard<std::mutex> Lock(Mutex);
Done = true;
NextReq.reset();
}
// Let the worker thread know that it should stop.
ReqCV.notify_all();
}
bool blockUntilIdle(Deadline Timeout) const {
std::unique_lock<std::mutex> Lock(Mutex);
return wait(Lock, ReqCV, Timeout, [&] { return !NextReq && !CurrentReq; });
}
private:
/// Holds inputs required for building a preamble. CI is guaranteed to be
/// non-null.
struct Request {
std::unique_ptr<CompilerInvocation> CI;
ParseInputs Inputs;
std::vector<Diag> CIDiags;
WantDiagnostics WantDiags;
Context Ctx;
};
bool isDone() {
std::lock_guard<std::mutex> Lock(Mutex);
return Done;
}
/// Builds a preamble for \p Req, might reuse LatestBuild if possible.
/// Notifies ASTWorker after build finishes.
void build(Request Req);
mutable std::mutex Mutex;
bool Done = false; /* GUARDED_BY(Mutex) */
std::optional<Request> NextReq; /* GUARDED_BY(Mutex) */
std::optional<Request> CurrentReq; /* GUARDED_BY(Mutex) */
// Signaled whenever a thread populates NextReq or worker thread builds a
// Preamble.
mutable std::condition_variable ReqCV; /* GUARDED_BY(Mutex) */
// Accessed only by preamble thread.
std::shared_ptr<const PreambleData> LatestBuild;
const Path FileName;
ParsingCallbacks &Callbacks;
const bool StoreInMemory;
const bool RunSync;
PreambleThrottler *Throttler;
SynchronizedTUStatus &Status;
ASTWorker &ASTPeer;
TUScheduler::HeaderIncluderCache &HeaderIncluders;
};
class ASTWorkerHandle;
/// Owns one instance of the AST, schedules updates and reads of it.
/// Also responsible for building and providing access to the preamble.
/// Each ASTWorker processes the async requests sent to it on a separate
/// dedicated thread.
/// The ASTWorker that manages the AST is shared by both the processing thread
/// and the TUScheduler. The TUScheduler should discard an ASTWorker when
/// remove() is called, but its thread may be busy and we don't want to block.
/// So the workers are accessed via an ASTWorkerHandle. Destroying the handle
/// signals the worker to exit its run loop and gives up shared ownership of the
/// worker.
class ASTWorker {
friend class ASTWorkerHandle;
ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
TUScheduler::ASTCache &LRUCache,
TUScheduler::HeaderIncluderCache &HeaderIncluders,
Semaphore &Barrier, bool RunSync, const TUScheduler::Options &Opts,
ParsingCallbacks &Callbacks);
public:
/// Create a new ASTWorker and return a handle to it.
/// The processing thread is spawned using \p Tasks. However, when \p Tasks
/// is null, all requests will be processed on the calling thread
/// synchronously instead. \p Barrier is acquired when processing each
/// request, it is used to limit the number of actively running threads.
static ASTWorkerHandle
create(PathRef FileName, const GlobalCompilationDatabase &CDB,
TUScheduler::ASTCache &IdleASTs,
TUScheduler::HeaderIncluderCache &HeaderIncluders,
AsyncTaskRunner *Tasks, Semaphore &Barrier,
const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks);
~ASTWorker();
void update(ParseInputs Inputs, WantDiagnostics, bool ContentChanged);
void
runWithAST(llvm::StringRef Name,
llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
TUScheduler::ASTActionInvalidation);
bool blockUntilIdle(Deadline Timeout) const;
std::shared_ptr<const PreambleData> getPossiblyStalePreamble(
std::shared_ptr<const ASTSignals> *ASTSignals = nullptr) const;
/// Used to inform ASTWorker about a new preamble build by PreambleThread.
/// Diagnostics are only published through this callback. This ensures they
/// are always for newer versions of the file, as the callback gets called in
/// the same order as update requests.
void updatePreamble(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
std::shared_ptr<const PreambleData> Preamble,
std::vector<Diag> CIDiags, WantDiagnostics WantDiags);
/// Returns compile command from the current file inputs.
tooling::CompileCommand getCurrentCompileCommand() const;
/// Wait for the first build of preamble to finish. Preamble itself can be
/// accessed via getPossiblyStalePreamble(). Note that this function will
/// return after an unsuccessful build of the preamble too, i.e. result of
/// getPossiblyStalePreamble() can be null even after this function returns.
void waitForFirstPreamble() const;
TUScheduler::FileStats stats() const;
bool isASTCached() const;
private:
// Details of an update request that are relevant to scheduling.
struct UpdateType {
// Do we want diagnostics from this version?
// If Yes, we must always build this version.
// If No, we only need to build this version if it's read.
// If Auto, we build if it's read or if the debounce expires.
WantDiagnostics Diagnostics;
// Did the main-file content of the document change?
// If so, we're allowed to cancel certain invalidated preceding reads.
bool ContentChanged;
};
/// Publishes diagnostics for \p Inputs. It will build an AST or reuse the
/// cached one if applicable. Assumes LatestPreamble is compatible for \p
/// Inputs.
void generateDiagnostics(std::unique_ptr<CompilerInvocation> Invocation,
ParseInputs Inputs, std::vector<Diag> CIDiags);
void updateASTSignals(ParsedAST &AST);
// Must be called exactly once on processing thread. Will return after
// stop() is called on a separate thread and all pending requests are
// processed.
void run();
/// Signal that run() should finish processing pending requests and exit.
void stop();
/// Adds a new task to the end of the request queue.
void startTask(llvm::StringRef Name, llvm::unique_function<void()> Task,
std::optional<UpdateType> Update,
TUScheduler::ASTActionInvalidation);
/// Runs a task synchronously.
void runTask(llvm::StringRef Name, llvm::function_ref<void()> Task);
/// Determines the next action to perform.
/// All actions that should never run are discarded.
/// Returns a deadline for the next action. If it's expired, run now.
/// scheduleLocked() is called again at the deadline, or if requests arrive.
Deadline scheduleLocked();
/// Should the first task in the queue be skipped instead of run?
bool shouldSkipHeadLocked() const;
struct Request {
llvm::unique_function<void()> Action;
std::string Name;
steady_clock::time_point AddTime;
Context Ctx;
std::optional<Context> QueueCtx;
std::optional<UpdateType> Update;
TUScheduler::ASTActionInvalidation InvalidationPolicy;
Canceler Invalidate;
};
/// Handles retention of ASTs.
TUScheduler::ASTCache &IdleASTs;
TUScheduler::HeaderIncluderCache &HeaderIncluders;
const bool RunSync;
/// Time to wait after an update to see whether another update obsoletes it.
const DebouncePolicy UpdateDebounce;
/// File that ASTWorker is responsible for.
const Path FileName;
/// Callback to create processing contexts for tasks.
const std::function<Context(llvm::StringRef)> ContextProvider;
const GlobalCompilationDatabase &CDB;
/// Callback invoked when preamble or main file AST is built.
ParsingCallbacks &Callbacks;
Semaphore &Barrier;
/// Whether the 'onMainAST' callback ran for the current FileInputs.
bool RanASTCallback = false;
/// Guards members used by both TUScheduler and the worker thread.
mutable std::mutex Mutex;
/// File inputs, currently being used by the worker.
/// Writes and reads from unknown threads are locked. Reads from the worker
/// thread are not locked, as it's the only writer.
ParseInputs FileInputs; /* GUARDED_BY(Mutex) */
/// Times of recent AST rebuilds, used for UpdateDebounce computation.
llvm::SmallVector<DebouncePolicy::clock::duration>
RebuildTimes; /* GUARDED_BY(Mutex) */
/// Set to true to signal run() to finish processing.
bool Done; /* GUARDED_BY(Mutex) */
std::deque<Request> Requests; /* GUARDED_BY(Mutex) */
std::optional<Request> CurrentRequest; /* GUARDED_BY(Mutex) */
/// Signalled whenever a new request has been scheduled or processing of a
/// request has completed.
mutable std::condition_variable RequestsCV;
std::shared_ptr<const ASTSignals> LatestASTSignals; /* GUARDED_BY(Mutex) */
/// Latest build preamble for current TU.
/// std::nullopt means no builds yet, null means there was an error while
/// building. Only written by ASTWorker's thread.
std::optional<std::shared_ptr<const PreambleData>> LatestPreamble;
std::deque<Request> PreambleRequests; /* GUARDED_BY(Mutex) */
/// Signaled whenever LatestPreamble changes state or there's a new
/// PreambleRequest.
mutable std::condition_variable PreambleCV;
/// Guards the callback that publishes results of AST-related computations
/// (diagnostics) and file statuses.
std::mutex PublishMu;
// Used to prevent remove document + add document races that lead to
// out-of-order callbacks for publishing results of onMainAST callback.
//
// The lifetime of the old/new ASTWorkers will overlap, but their handles
// don't. When the old handle is destroyed, the old worker will stop reporting
// any results to the user.
bool CanPublishResults = true; /* GUARDED_BY(PublishMu) */
std::atomic<unsigned> ASTBuildCount = {0};
std::atomic<unsigned> PreambleBuildCount = {0};
SynchronizedTUStatus Status;
PreambleThread PreamblePeer;
};
/// A smart-pointer-like class that points to an active ASTWorker.
/// In destructor, signals to the underlying ASTWorker that no new requests will
/// be sent and the processing loop may exit (after running all pending
/// requests).
class ASTWorkerHandle {
friend class ASTWorker;
ASTWorkerHandle(std::shared_ptr<ASTWorker> Worker)
: Worker(std::move(Worker)) {
assert(this->Worker);
}
public:
ASTWorkerHandle(const ASTWorkerHandle &) = delete;
ASTWorkerHandle &operator=(const ASTWorkerHandle &) = delete;
ASTWorkerHandle(ASTWorkerHandle &&) = default;
ASTWorkerHandle &operator=(ASTWorkerHandle &&) = default;
~ASTWorkerHandle() {
if (Worker)
Worker->stop();
}
ASTWorker &operator*() {
assert(Worker && "Handle was moved from");
return *Worker;
}
ASTWorker *operator->() {
assert(Worker && "Handle was moved from");
return Worker.get();
}
/// Returns an owning reference to the underlying ASTWorker that can outlive
/// the ASTWorkerHandle. However, no new requests to an active ASTWorker can
/// be schedule via the returned reference, i.e. only reads of the preamble
/// are possible.
std::shared_ptr<const ASTWorker> lock() { return Worker; }
private:
std::shared_ptr<ASTWorker> Worker;
};
ASTWorkerHandle
ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
TUScheduler::ASTCache &IdleASTs,
TUScheduler::HeaderIncluderCache &HeaderIncluders,
AsyncTaskRunner *Tasks, Semaphore &Barrier,
const TUScheduler::Options &Opts,
ParsingCallbacks &Callbacks) {
std::shared_ptr<ASTWorker> Worker(
new ASTWorker(FileName, CDB, IdleASTs, HeaderIncluders, Barrier,
/*RunSync=*/!Tasks, Opts, Callbacks));
if (Tasks) {
Tasks->runAsync("ASTWorker:" + llvm::sys::path::filename(FileName),
[Worker]() { Worker->run(); });
Tasks->runAsync("PreambleWorker:" + llvm::sys::path::filename(FileName),
[Worker]() { Worker->PreamblePeer.run(); });
}
return ASTWorkerHandle(std::move(Worker));
}
ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
TUScheduler::ASTCache &LRUCache,
TUScheduler::HeaderIncluderCache &HeaderIncluders,
Semaphore &Barrier, bool RunSync,
const TUScheduler::Options &Opts,
ParsingCallbacks &Callbacks)
: IdleASTs(LRUCache), HeaderIncluders(HeaderIncluders), RunSync(RunSync),
UpdateDebounce(Opts.UpdateDebounce), FileName(FileName),
ContextProvider(Opts.ContextProvider), CDB(CDB), Callbacks(Callbacks),
Barrier(Barrier), Done(false), Status(FileName, Callbacks),
PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory, RunSync,
Opts.PreambleThrottler, Status, HeaderIncluders, *this) {
// Set a fallback command because compile command can be accessed before
// `Inputs` is initialized. Other fields are only used after initialization
// from client inputs.
FileInputs.CompileCommand = CDB.getFallbackCommand(FileName);
}
ASTWorker::~ASTWorker() {
// Make sure we remove the cached AST, if any.
IdleASTs.take(this);
#ifndef NDEBUG
std::lock_guard<std::mutex> Lock(Mutex);
assert(Done && "handle was not destroyed");
assert(Requests.empty() && !CurrentRequest &&
"unprocessed requests when destroying ASTWorker");
#endif
}
void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags,
bool ContentChanged) {
llvm::StringLiteral TaskName = "Update";
auto Task = [=]() mutable {
// Get the actual command as `Inputs` does not have a command.
// FIXME: some build systems like Bazel will take time to preparing
// environment to build the file, it would be nice if we could emit a
// "PreparingBuild" status to inform users, it is non-trivial given the
// current implementation.
auto Cmd = CDB.getCompileCommand(FileName);
// If we don't have a reliable command for this file, it may be a header.
// Try to find a file that includes it, to borrow its command.
if (!Cmd || !isReliable(*Cmd)) {
std::string ProxyFile = HeaderIncluders.get(FileName);
if (!ProxyFile.empty()) {
auto ProxyCmd = CDB.getCompileCommand(ProxyFile);
if (!ProxyCmd || !isReliable(*ProxyCmd)) {
// This command is supposed to be reliable! It's probably gone.
HeaderIncluders.remove(ProxyFile);
} else {
// We have a reliable command for an including file, use it.
Cmd = tooling::transferCompileCommand(std::move(*ProxyCmd), FileName);
}
}
}
if (Cmd)
Inputs.CompileCommand = std::move(*Cmd);
else
Inputs.CompileCommand = CDB.getFallbackCommand(FileName);
bool InputsAreTheSame =
std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
std::tie(Inputs.CompileCommand, Inputs.Contents);
// Cached AST is invalidated.
if (!InputsAreTheSame) {
IdleASTs.take(this);
RanASTCallback = false;
}
// Update current inputs so that subsequent reads can see them.
{
std::lock_guard<std::mutex> Lock(Mutex);
FileInputs = Inputs;
}
log("ASTWorker building file {0} version {1} with command {2}\n[{3}]\n{4}",
FileName, Inputs.Version, Inputs.CompileCommand.Heuristic,
Inputs.CompileCommand.Directory,
printArgv(Inputs.CompileCommand.CommandLine));
StoreDiags CompilerInvocationDiagConsumer;
std::vector<std::string> CC1Args;
std::unique_ptr<CompilerInvocation> Invocation = buildCompilerInvocation(
Inputs, CompilerInvocationDiagConsumer, &CC1Args);
// Log cc1 args even (especially!) if creating invocation failed.
if (!CC1Args.empty())
vlog("Driver produced command: cc1 {0}", printArgv(CC1Args));
std::vector<Diag> CompilerInvocationDiags =
CompilerInvocationDiagConsumer.take();
if (!Invocation) {
elog("Could not build CompilerInvocation for file {0}", FileName);
// Remove the old AST if it's still in cache.
IdleASTs.take(this);
RanASTCallback = false;
// Report the diagnostics we collected when parsing the command line.
Callbacks.onFailedAST(FileName, Inputs.Version,
std::move(CompilerInvocationDiags),
[&](llvm::function_ref<void()> Publish) {
// Ensure we only publish results from the worker
// if the file was not removed, making sure there
// are not race conditions.
std::lock_guard<std::mutex> Lock(PublishMu);
if (CanPublishResults)
Publish();
});
// Note that this might throw away a stale preamble that might still be
// useful, but this is how we communicate a build error.
LatestPreamble.emplace();
// Make sure anyone waiting for the preamble gets notified it could not be
// built.
PreambleCV.notify_all();
return;
}
// Inform preamble peer, before attempting to build diagnostics so that they
// can be built concurrently.
PreamblePeer.update(std::make_unique<CompilerInvocation>(*Invocation),
Inputs, CompilerInvocationDiags, WantDiags);
// Emit diagnostics from (possibly) stale preamble while waiting for a
// rebuild. Newly built preamble cannot emit diagnostics before this call
// finishes (ast callbacks are called from astpeer thread), hence we
// guarantee eventual consistency.
if (LatestPreamble && WantDiags != WantDiagnostics::No)
generateDiagnostics(std::move(Invocation), std::move(Inputs),
std::move(CompilerInvocationDiags));
std::unique_lock<std::mutex> Lock(Mutex);
PreambleCV.wait(Lock, [this] {
// Block until we reiceve a preamble request, unless a preamble already
// exists, as patching an empty preamble would imply rebuilding it from
// scratch.
// We block here instead of the consumer to prevent any deadlocks. Since
// LatestPreamble is only populated by ASTWorker thread.
return LatestPreamble || !PreambleRequests.empty() || Done;
});
};
startTask(TaskName, std::move(Task), UpdateType{WantDiags, ContentChanged},
TUScheduler::NoInvalidation);
}
void ASTWorker::runWithAST(
llvm::StringRef Name,
llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
TUScheduler::ASTActionInvalidation Invalidation) {
// Tracks ast cache accesses for read operations.
static constexpr trace::Metric ASTAccessForRead(
"ast_access_read", trace::Metric::Counter, "result");
auto Task = [=, Action = std::move(Action)]() mutable {
if (auto Reason = isCancelled())
return Action(llvm::make_error<CancelledError>(Reason));
std::optional<std::unique_ptr<ParsedAST>> AST =
IdleASTs.take(this, &ASTAccessForRead);
if (!AST) {
StoreDiags CompilerInvocationDiagConsumer;
std::unique_ptr<CompilerInvocation> Invocation =
buildCompilerInvocation(FileInputs, CompilerInvocationDiagConsumer);
// Try rebuilding the AST.
vlog("ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Name,
FileName, FileInputs.Version);
// FIXME: We might need to build a patched ast once preamble thread starts
// running async. Currently getPossiblyStalePreamble below will always
// return a compatible preamble as ASTWorker::update blocks.
std::optional<ParsedAST> NewAST;
if (Invocation) {
NewAST = ParsedAST::build(FileName, FileInputs, std::move(Invocation),
CompilerInvocationDiagConsumer.take(),
getPossiblyStalePreamble());
++ASTBuildCount;
}
AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
}