compiler/rustc_query_system/src/query/job.rs

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