compiler/rustc_query_system/src/query/job.rs

   1 use crate::dep_graph::DepKind;
   2 use crate::error::CycleStack;
   3 use crate::query::plumbing::CycleError;
   4 use crate::query::{QueryContext, QueryStackFrame};
   5 use core::marker::PhantomData;
   6
   7 use rustc_data_structures::fx::FxHashMap;
   8 use rustc_errors::{
   9     Diagnostic, DiagnosticBuilder, ErrorGuaranteed, Handler, IntoDiagnostic, Level,
  10 };
  11 use rustc_hir::def::DefKind;
  12 use rustc_session::Session;
  13 use rustc_span::Span;
  14
  15 use std::hash::Hash;
  16 use std::num::NonZeroU64;
  17
  18 #[cfg(parallel_compiler)]
  19 use {
  20     parking_lot::{Condvar, Mutex},
  21     rustc_data_structures::fx::FxHashSet,
  22     rustc_data_structures::sync::Lock,
  23     rustc_data_structures::sync::Lrc,
  24     rustc_data_structures::{jobserver, OnDrop},
  25     rustc_rayon_core as rayon_core,
  26     rustc_span::DUMMY_SP,
  27     std::iter,
  28     std::process,
  29 };
  30
  31 /// Represents a span and a query key.
  32 #[derive(Clone, Debug)]
  33 pub struct QueryInfo<D: DepKind> {
  34     /// The span corresponding to the reason for which this query was required.
  35     pub span: Span,
  36     pub query: QueryStackFrame<D>,
  37 }
  38
  39 pub type QueryMap<D> = FxHashMap<QueryJobId, QueryJobInfo<D>>;
  40
  41 /// A value uniquely identifying an active query job.
  42 #[derive(Copy, Clone, Eq, PartialEq, Hash)]
  43 pub struct QueryJobId(pub NonZeroU64);
  44
  45 impl QueryJobId {
  46     fn query<D: DepKind>(self, map: &QueryMap<D>) -> QueryStackFrame<D> {
  47         map.get(&self).unwrap().query.clone()
  48     }
  49
  50     #[cfg(parallel_compiler)]
  51     fn span<D: DepKind>(self, map: &QueryMap<D>) -> Span {
  52         map.get(&self).unwrap().job.span
  53     }
  54
  55     #[cfg(parallel_compiler)]
  56     fn parent<D: DepKind>(self, map: &QueryMap<D>) -> Option<QueryJobId> {
  57         map.get(&self).unwrap().job.parent
  58     }
  59
  60     #[cfg(parallel_compiler)]
  61     fn latch<D: DepKind>(self, map: &QueryMap<D>) -> Option<&QueryLatch<D>> {
  62         map.get(&self).unwrap().job.latch.as_ref()
  63     }
  64 }
  65
  66 #[derive(Clone)]
  67 pub struct QueryJobInfo<D: DepKind> {
  68     pub query: QueryStackFrame<D>,
  69     pub job: QueryJob<D>,
  70 }
  71
  72 /// Represents an active query job.
  73 #[derive(Clone)]
  74 pub struct QueryJob<D: DepKind> {
  75     pub id: QueryJobId,
  76
  77     /// The span corresponding to the reason for which this query was required.
  78     pub span: Span,
  79
  80     /// The parent query job which created this job and is implicitly waiting on it.
  81     pub parent: Option<QueryJobId>,
  82
  83     /// The latch that is used to wait on this job.
  84     #[cfg(parallel_compiler)]
  85     latch: Option<QueryLatch<D>>,
  86     spooky: core::marker::PhantomData<D>,
  87 }
  88
  89 impl<D: DepKind> QueryJob<D> {
  90     /// Creates a new query job.
  91     #[inline]
  92     pub fn new(id: QueryJobId, span: Span, parent: Option<QueryJobId>) -> Self {
  93         QueryJob {
  94             id,
  95             span,
  96             parent,
  97             #[cfg(parallel_compiler)]
  98             latch: None,
  99             spooky: PhantomData,
 100         }
 101     }
 102
 103     #[cfg(parallel_compiler)]
 104     pub(super) fn latch(&mut self) -> QueryLatch<D> {
 105         if self.latch.is_none() {
 106             self.latch = Some(QueryLatch::new());
 107         }
 108         self.latch.as_ref().unwrap().clone()
 109     }
 110
 111     /// Signals to waiters that the query is complete.
 112     ///
 113     /// This does nothing for single threaded rustc,
 114     /// as there are no concurrent jobs which could be waiting on us
 115     #[inline]
 116     pub fn signal_complete(self) {
 117         #[cfg(parallel_compiler)]
 118         {
 119             if let Some(latch) = self.latch {
 120                 latch.set();
 121             }
 122         }
 123     }
 124 }
 125
 126 impl QueryJobId {
 127     #[cold]
 128     #[inline(never)]
 129     #[cfg(not(parallel_compiler))]
 130     pub(super) fn find_cycle_in_stack<D: DepKind>(
 131         &self,
 132         query_map: QueryMap<D>,
 133         current_job: &Option<QueryJobId>,
 134         span: Span,
 135     ) -> CycleError<D> {
 136         // Find the waitee amongst `current_job` parents
 137         let mut cycle = Vec::new();
 138         let mut current_job = Option::clone(current_job);
 139
 140         while let Some(job) = current_job {
 141             let info = query_map.get(&job).unwrap();
 142             cycle.push(QueryInfo { span: info.job.span, query: info.query.clone() });
 143
 144             if job == *self {
 145                 cycle.reverse();
 146
 147                 // This is the end of the cycle
 148                 // The span entry we included was for the usage
 149                 // of the cycle itself, and not part of the cycle
 150                 // Replace it with the span which caused the cycle to form
 151                 cycle[0].span = span;
 152                 // Find out why the cycle itself was used
 153                 let usage = info
 154                     .job
 155                     .parent
 156                     .as_ref()
 157                     .map(|parent| (info.job.span, parent.query(&query_map)));
 158                 return CycleError { usage, cycle };
 159             }
 160
 161             current_job = info.job.parent;
 162         }
 163
 164         panic!("did not find a cycle")
 165     }
 166
 167     #[cold]
 168     #[inline(never)]
 169     pub fn try_find_layout_root<D: DepKind>(
 170         &self,
 171         query_map: QueryMap<D>,
 172     ) -> Option<(QueryJobInfo<D>, usize)> {
 173         let mut last_layout = None;
 174         let mut current_id = Some(*self);
 175         let mut depth = 0;
 176
 177         while let Some(id) = current_id {
 178             let info = query_map.get(&id).unwrap();
 179             // FIXME: This string comparison should probably not be done.
 180             if format!("{:?}", info.query.dep_kind) == "layout_of" {
 181                 depth += 1;
 182                 last_layout = Some((info.clone(), depth));
 183             }
 184             current_id = info.job.parent;
 185         }
 186         last_layout
 187     }
 188 }
 189
 190 #[cfg(parallel_compiler)]
 191 struct QueryWaiter<D: DepKind> {
 192     query: Option<QueryJobId>,
 193     condvar: Condvar,
 194     span: Span,
 195     cycle: Lock<Option<CycleError<D>>>,
 196 }
 197
 198 #[cfg(parallel_compiler)]
 199 impl<D: DepKind> QueryWaiter<D> {
 200     fn notify(&self, registry: &rayon_core::Registry) {
 201         rayon_core::mark_unblocked(registry);
 202         self.condvar.notify_one();
 203     }
 204 }
 205
 206 #[cfg(parallel_compiler)]
 207 struct QueryLatchInfo<D: DepKind> {
 208     complete: bool,
 209     waiters: Vec<Lrc<QueryWaiter<D>>>,
 210 }
 211
 212 #[cfg(parallel_compiler)]
 213 #[derive(Clone)]
 214 pub(super) struct QueryLatch<D: DepKind> {
 215     info: Lrc<Mutex<QueryLatchInfo<D>>>,
 216 }
 217
 218 #[cfg(parallel_compiler)]
 219 impl<D: DepKind> QueryLatch<D> {
 220     fn new() -> Self {
 221         QueryLatch {
 222             info: Lrc::new(Mutex::new(QueryLatchInfo { complete: false, waiters: Vec::new() })),
 223         }
 224     }
 225
 226     /// Awaits for the query job to complete.
 227     pub(super) fn wait_on(
 228         &self,
 229         query: Option<QueryJobId>,
 230         span: Span,
 231     ) -> Result<(), CycleError<D>> {
 232         let waiter =
 233             Lrc::new(QueryWaiter { query, span, cycle: Lock::new(None), condvar: Condvar::new() });
 234         self.wait_on_inner(&waiter);
 235         // FIXME: Get rid of this lock. We have ownership of the QueryWaiter
 236         // although another thread may still have a Lrc reference so we cannot
 237         // use Lrc::get_mut
 238         let mut cycle = waiter.cycle.lock();
 239         match cycle.take() {
 240             None => Ok(()),
 241             Some(cycle) => Err(cycle),
 242         }
 243     }
 244
 245     /// Awaits the caller on this latch by blocking the current thread.
 246     fn wait_on_inner(&self, waiter: &Lrc<QueryWaiter<D>>) {
 247         let mut info = self.info.lock();
 248         if !info.complete {
 249             // We push the waiter on to the `waiters` list. It can be accessed inside
 250             // the `wait` call below, by 1) the `set` method or 2) by deadlock detection.
 251             // Both of these will remove it from the `waiters` list before resuming
 252             // this thread.
 253             info.waiters.push(waiter.clone());
 254
 255             // If this detects a deadlock and the deadlock handler wants to resume this thread
 256             // we have to be in the `wait` call. This is ensured by the deadlock handler
 257             // getting the self.info lock.
 258             rayon_core::mark_blocked();
 259             jobserver::release_thread();
 260             waiter.condvar.wait(&mut info);
 261             // Release the lock before we potentially block in `acquire_thread`
 262             drop(info);
 263             jobserver::acquire_thread();
 264         }
 265     }
 266
 267     /// Sets the latch and resumes all waiters on it
 268     fn set(&self) {
 269         let mut info = self.info.lock();
 270         debug_assert!(!info.complete);
 271         info.complete = true;
 272         let registry = rayon_core::Registry::current();
 273         for waiter in info.waiters.drain(..) {
 274             waiter.notify(&registry);
 275         }
 276     }
 277
 278     /// Removes a single waiter from the list of waiters.
 279     /// This is used to break query cycles.
 280     fn extract_waiter(&self, waiter: usize) -> Lrc<QueryWaiter<D>> {
 281         let mut info = self.info.lock();
 282         debug_assert!(!info.complete);
 283         // Remove the waiter from the list of waiters
 284         info.waiters.remove(waiter)
 285     }
 286 }
 287
 288 /// A resumable waiter of a query. The usize is the index into waiters in the query's latch
 289 #[cfg(parallel_compiler)]
 290 type Waiter = (QueryJobId, usize);
 291
 292 /// Visits all the non-resumable and resumable waiters of a query.
 293 /// Only waiters in a query are visited.
 294 /// `visit` is called for every waiter and is passed a query waiting on `query_ref`
 295 /// and a span indicating the reason the query waited on `query_ref`.
 296 /// If `visit` returns Some, this function returns.
 297 /// For visits of non-resumable waiters it returns the return value of `visit`.
 298 /// For visits of resumable waiters it returns Some(Some(Waiter)) which has the
 299 /// required information to resume the waiter.
 300 /// If all `visit` calls returns None, this function also returns None.
 301 #[cfg(parallel_compiler)]
 302 fn visit_waiters<F, D>(
 303     query_map: &QueryMap<D>,
 304     query: QueryJobId,
 305     mut visit: F,
 306 ) -> Option<Option<Waiter>>
 307 where
 308     F: FnMut(Span, QueryJobId) -> Option<Option<Waiter>>,
 309     D: DepKind,
 310 {
 311     // Visit the parent query which is a non-resumable waiter since it's on the same stack
 312     if let Some(parent) = query.parent(query_map) {
 313         if let Some(cycle) = visit(query.span(query_map), parent) {
 314             return Some(cycle);
 315         }
 316     }
 317
 318     // Visit the explicit waiters which use condvars and are resumable
 319     if let Some(latch) = query.latch(query_map) {
 320         for (i, waiter) in latch.info.lock().waiters.iter().enumerate() {
 321             if let Some(waiter_query) = waiter.query {
 322                 if visit(waiter.span, waiter_query).is_some() {
 323                     // Return a value which indicates that this waiter can be resumed
 324                     return Some(Some((query, i)));
 325                 }
 326             }
 327         }
 328     }
 329
 330     None
 331 }
 332
 333 /// Look for query cycles by doing a depth first search starting at `query`.
 334 /// `span` is the reason for the `query` to execute. This is initially DUMMY_SP.
 335 /// If a cycle is detected, this initial value is replaced with the span causing
 336 /// the cycle.
 337 #[cfg(parallel_compiler)]
 338 fn cycle_check<D: DepKind>(
 339     query_map: &QueryMap<D>,
 340     query: QueryJobId,
 341     span: Span,
 342     stack: &mut Vec<(Span, QueryJobId)>,
 343     visited: &mut FxHashSet<QueryJobId>,
 344 ) -> Option<Option<Waiter>> {
 345     if !visited.insert(query) {
 346         return if let Some(p) = stack.iter().position(|q| q.1 == query) {
 347             // We detected a query cycle, fix up the initial span and return Some
 348
 349             // Remove previous stack entries
 350             stack.drain(0..p);
 351             // Replace the span for the first query with the cycle cause
 352             stack[0].0 = span;
 353             Some(None)
 354         } else {
 355             None
 356         };
 357     }
 358
 359     // Query marked as visited is added it to the stack
 360     stack.push((span, query));
 361
 362     // Visit all the waiters
 363     let r = visit_waiters(query_map, query, |span, successor| {
 364         cycle_check(query_map, successor, span, stack, visited)
 365     });
 366
 367     // Remove the entry in our stack if we didn't find a cycle
 368     if r.is_none() {
 369         stack.pop();
 370     }
 371
 372     r
 373 }
 374
 375 /// Finds out if there's a path to the compiler root (aka. code which isn't in a query)
 376 /// from `query` without going through any of the queries in `visited`.
 377 /// This is achieved with a depth first search.
 378 #[cfg(parallel_compiler)]
 379 fn connected_to_root<D: DepKind>(
 380     query_map: &QueryMap<D>,
 381     query: QueryJobId,
 382     visited: &mut FxHashSet<QueryJobId>,
 383 ) -> bool {
 384     // We already visited this or we're deliberately ignoring it
 385     if !visited.insert(query) {
 386         return false;
 387     }
 388
 389     // This query is connected to the root (it has no query parent), return true
 390     if query.parent(query_map).is_none() {
 391         return true;
 392     }
 393
 394     visit_waiters(query_map, query, |_, successor| {
 395         connected_to_root(query_map, successor, visited).then_some(None)
 396     })
 397     .is_some()
 398 }
 399
 400 // Deterministically pick an query from a list
 401 #[cfg(parallel_compiler)]
 402 fn pick_query<'a, T, F, D>(query_map: &QueryMap<D>, queries: &'a [T], f: F) -> &'a T
 403 where
 404     F: Fn(&T) -> (Span, QueryJobId),
 405     D: DepKind,
 406 {
 407     // Deterministically pick an entry point
 408     // FIXME: Sort this instead
 409     queries
 410         .iter()
 411         .min_by_key(|v| {
 412             let (span, query) = f(v);
 413             let hash = query.query(query_map).hash;
 414             // Prefer entry points which have valid spans for nicer error messages
 415             // We add an integer to the tuple ensuring that entry points
 416             // with valid spans are picked first
 417             let span_cmp = if span == DUMMY_SP { 1 } else { 0 };
 418             (span_cmp, hash)
 419         })
 420         .unwrap()
 421 }
 422
 423 /// Looks for query cycles starting from the last query in `jobs`.
 424 /// If a cycle is found, all queries in the cycle is removed from `jobs` and
 425 /// the function return true.
 426 /// If a cycle was not found, the starting query is removed from `jobs` and
 427 /// the function returns false.
 428 #[cfg(parallel_compiler)]
 429 fn remove_cycle<D: DepKind>(
 430     query_map: &QueryMap<D>,
 431     jobs: &mut Vec<QueryJobId>,
 432     wakelist: &mut Vec<Lrc<QueryWaiter<D>>>,
 433 ) -> bool {
 434     let mut visited = FxHashSet::default();
 435     let mut stack = Vec::new();
 436     // Look for a cycle starting with the last query in `jobs`
 437     if let Some(waiter) =
 438         cycle_check(query_map, jobs.pop().unwrap(), DUMMY_SP, &mut stack, &mut visited)
 439     {
 440         // The stack is a vector of pairs of spans and queries; reverse it so that
 441         // the earlier entries require later entries
 442         let (mut spans, queries): (Vec<_>, Vec<_>) = stack.into_iter().rev().unzip();
 443
 444         // Shift the spans so that queries are matched with the span for their waitee
 445         spans.rotate_right(1);
 446
 447         // Zip them back together
 448         let mut stack: Vec<_> = iter::zip(spans, queries).collect();
 449
 450         // Remove the queries in our cycle from the list of jobs to look at
 451         for r in &stack {
 452             if let Some(pos) = jobs.iter().position(|j| j == &r.1) {
 453                 jobs.remove(pos);
 454             }
 455         }
 456
 457         // Find the queries in the cycle which are
 458         // connected to queries outside the cycle
 459         let entry_points = stack
 460             .iter()
 461             .filter_map(|&(span, query)| {
 462                 if query.parent(query_map).is_none() {
 463                     // This query is connected to the root (it has no query parent)
 464                     Some((span, query, None))
 465                 } else {
 466                     let mut waiters = Vec::new();
 467                     // Find all the direct waiters who lead to the root
 468                     visit_waiters(query_map, query, |span, waiter| {
 469                         // Mark all the other queries in the cycle as already visited
 470                         let mut visited = FxHashSet::from_iter(stack.iter().map(|q| q.1));
 471
 472                         if connected_to_root(query_map, waiter, &mut visited) {
 473                             waiters.push((span, waiter));
 474                         }
 475
 476                         None
 477                     });
 478                     if waiters.is_empty() {
 479                         None
 480                     } else {
 481                         // Deterministically pick one of the waiters to show to the user
 482                         let waiter = *pick_query(query_map, &waiters, |s| *s);
 483                         Some((span, query, Some(waiter)))
 484                     }
 485                 }
 486             })
 487             .collect::<Vec<(Span, QueryJobId, Option<(Span, QueryJobId)>)>>();
 488
 489         // Deterministically pick an entry point
 490         let (_, entry_point, usage) = pick_query(query_map, &entry_points, |e| (e.0, e.1));
 491
 492         // Shift the stack so that our entry point is first
 493         let entry_point_pos = stack.iter().position(|(_, query)| query == entry_point);
 494         if let Some(pos) = entry_point_pos {
 495             stack.rotate_left(pos);
 496         }
 497
 498         let usage = usage.as_ref().map(|(span, query)| (*span, query.query(query_map)));
 499
 500         // Create the cycle error
 501         let error = CycleError {
 502             usage,
 503             cycle: stack
 504                 .iter()
 505                 .map(|&(s, ref q)| QueryInfo { span: s, query: q.query(query_map) })
 506                 .collect(),
 507         };
 508
 509         // We unwrap `waiter` here since there must always be one
 510         // edge which is resumable / waited using a query latch
 511         let (waitee_query, waiter_idx) = waiter.unwrap();
 512
 513         // Extract the waiter we want to resume
 514         let waiter = waitee_query.latch(query_map).unwrap().extract_waiter(waiter_idx);
 515
 516         // Set the cycle error so it will be picked up when resumed
 517         *waiter.cycle.lock() = Some(error);
 518
 519         // Put the waiter on the list of things to resume
 520         wakelist.push(waiter);
 521
 522         true
 523     } else {
 524         false
 525     }
 526 }
 527
 528 /// Detects query cycles by using depth first search over all active query jobs.
 529 /// If a query cycle is found it will break the cycle by finding an edge which
 530 /// uses a query latch and then resuming that waiter.
 531 /// There may be multiple cycles involved in a deadlock, so this searches
 532 /// all active queries for cycles before finally resuming all the waiters at once.
 533 #[cfg(parallel_compiler)]
 534 pub fn deadlock<D: DepKind>(query_map: QueryMap<D>, registry: &rayon_core::Registry) {
 535     let on_panic = OnDrop(|| {
 536         eprintln!("deadlock handler panicked, aborting process");
 537         process::abort();
 538     });
 539
 540     let mut wakelist = Vec::new();
 541     let mut jobs: Vec<QueryJobId> = query_map.keys().cloned().collect();
 542
 543     let mut found_cycle = false;
 544
 545     while jobs.len() > 0 {
 546         if remove_cycle(&query_map, &mut jobs, &mut wakelist) {
 547             found_cycle = true;
 548         }
 549     }
 550
 551     // Check that a cycle was found. It is possible for a deadlock to occur without
 552     // a query cycle if a query which can be waited on uses Rayon to do multithreading
 553     // internally. Such a query (X) may be executing on 2 threads (A and B) and A may
 554     // wait using Rayon on B. Rayon may then switch to executing another query (Y)
 555     // which in turn will wait on X causing a deadlock. We have a false dependency from
 556     // X to Y due to Rayon waiting and a true dependency from Y to X. The algorithm here
 557     // only considers the true dependency and won't detect a cycle.
 558     assert!(found_cycle);
 559
 560     // FIXME: Ensure this won't cause a deadlock before we return
 561     for waiter in wakelist.into_iter() {
 562         waiter.notify(registry);
 563     }
 564
 565     on_panic.disable();
 566 }
 567
 568 #[inline(never)]
 569 #[cold]
 570 pub(crate) fn report_cycle<'a, D: DepKind>(
 571     sess: &'a Session,
 572     CycleError { usage, cycle: stack }: &CycleError<D>,
 573 ) -> DiagnosticBuilder<'a, ErrorGuaranteed> {
 574     assert!(!stack.is_empty());
 575
 576     let span = stack[0].query.default_span(stack[1 % stack.len()].span);
 577
 578     let mut cycle_stack = Vec::new();
 579
 580     use crate::error::StackCount;
 581     let stack_count = if stack.len() == 1 { StackCount::Single } else { StackCount::Multiple };
 582
 583     for i in 1..stack.len() {
 584         let query = &stack[i].query;
 585         let span = query.default_span(stack[(i + 1) % stack.len()].span);
 586         cycle_stack.push(CycleStack { span, desc: query.description.to_owned() });
 587     }
 588
 589     let mut cycle_usage = None;
 590     if let Some((span, ref query)) = *usage {
 591         cycle_usage = Some(crate::error::CycleUsage {
 592             span: query.default_span(span),
 593             usage: query.description.to_string(),
 594         });
 595     }
 596
 597     let alias = if stack.iter().all(|entry| entry.query.def_kind == Some(DefKind::TyAlias)) {
 598         Some(crate::error::Alias::Ty)
 599     } else if stack.iter().all(|entry| entry.query.def_kind == Some(DefKind::TraitAlias)) {
 600         Some(crate::error::Alias::Trait)
 601     } else {
 602         None
 603     };
 604
 605     let cycle_diag = crate::error::Cycle {
 606         span,
 607         cycle_stack,
 608         stack_bottom: stack[0].query.description.to_owned(),
 609         alias,
 610         cycle_usage: cycle_usage,
 611         stack_count,
 612     };
 613
 614     cycle_diag.into_diagnostic(&sess.parse_sess.span_diagnostic)
 615 }
 616
 617 pub fn print_query_stack<Qcx: QueryContext>(
 618     qcx: Qcx,
 619     mut current_query: Option<QueryJobId>,
 620     handler: &Handler,
 621     num_frames: Option<usize>,
 622 ) -> usize {
 623     // Be careful relying on global state here: this code is called from
 624     // a panic hook, which means that the global `Handler` may be in a weird
 625     // state if it was responsible for triggering the panic.
 626     let mut i = 0;
 627     let query_map = qcx.try_collect_active_jobs();
 628
 629     while let Some(query) = current_query {
 630         if Some(i) == num_frames {
 631             break;
 632         }
 633         let Some(query_info) = query_map.as_ref().and_then(|map| map.get(&query)) else {
 634             break;
 635         };
 636         let mut diag = Diagnostic::new(
 637             Level::FailureNote,
 638             &format!("#{} [{:?}] {}", i, query_info.query.dep_kind, query_info.query.description),
 639         );
 640         diag.span = query_info.job.span.into();
 641         handler.force_print_diagnostic(diag);
 642
 643         current_query = query_info.job.parent;
 644         i += 1;
 645     }
 646
 647     i
 648 }