+#pragma mark -
+#pragma mark dispatch introspection deadlock detection
+
+typedef struct dispatch_queue_order_entry_s *dispatch_queue_order_entry_t;
+struct dispatch_queue_order_entry_s {
+ TAILQ_ENTRY(dispatch_queue_order_entry_s) dqoe_order_top_list;
+ TAILQ_ENTRY(dispatch_queue_order_entry_s) dqoe_order_bottom_list;
+ const char *dqoe_top_label;
+ const char *dqoe_bottom_label;
+ dispatch_queue_t dqoe_top_tq;
+ dispatch_queue_t dqoe_bottom_tq;
+ int dqoe_pcs_n;
+ void *dqoe_pcs[];
+};
+
+static void
+_dispatch_introspection_queue_order_dispose(dispatch_queue_t dq)
+{
+ dispatch_queue_order_entry_t e, te;
+ dispatch_queue_t otherq;
+ TAILQ_HEAD(, dispatch_queue_order_entry_s) head;
+
+ // this whole thing happens with _dispatch_introspection.queues_lock locked
+
+ _dispatch_unfair_lock_lock(&dq->diq_order_top_head_lock);
+ head.tqh_first = dq->diq_order_top_head.tqh_first;
+ head.tqh_last = dq->diq_order_top_head.tqh_last;
+ TAILQ_INIT(&dq->diq_order_top_head);
+ _dispatch_unfair_lock_unlock(&dq->diq_order_top_head_lock);
+
+ TAILQ_FOREACH_SAFE(e, &head, dqoe_order_top_list, te) {
+ otherq = e->dqoe_bottom_tq;
+ _dispatch_unfair_lock_lock(&otherq->diq_order_bottom_head_lock);
+ TAILQ_REMOVE(&otherq->diq_order_bottom_head, e, dqoe_order_bottom_list);
+ _dispatch_unfair_lock_unlock(&otherq->diq_order_bottom_head_lock);
+ free(e);
+ }
+
+ _dispatch_unfair_lock_lock(&dq->diq_order_bottom_head_lock);
+ head.tqh_first = dq->diq_order_bottom_head.tqh_first;
+ head.tqh_last = dq->diq_order_bottom_head.tqh_last;
+ TAILQ_INIT(&dq->diq_order_bottom_head);
+ _dispatch_unfair_lock_unlock(&dq->diq_order_bottom_head_lock);
+
+ TAILQ_FOREACH_SAFE(e, &head, dqoe_order_bottom_list, te) {
+ otherq = e->dqoe_top_tq;
+ _dispatch_unfair_lock_lock(&otherq->diq_order_top_head_lock);
+ TAILQ_REMOVE(&otherq->diq_order_top_head, e, dqoe_order_top_list);
+ _dispatch_unfair_lock_unlock(&otherq->diq_order_top_head_lock);
+ free(e);
+ }
+}
+
+// caller must make sure dq is not a root quueue
+DISPATCH_ALWAYS_INLINE
+static inline dispatch_queue_t
+_dispatch_queue_bottom_target_queue(dispatch_queue_t dq)
+{
+ while (dq->do_targetq->do_targetq) {
+ dq = dq->do_targetq;
+ }
+ return dq;
+}
+
+typedef struct dispatch_order_frame_s *dispatch_order_frame_t;
+struct dispatch_order_frame_s {
+ dispatch_order_frame_t dof_prev;
+ dispatch_queue_order_entry_t dof_e;
+};
+
+DISPATCH_NOINLINE DISPATCH_NORETURN
+static void
+_dispatch_introspection_lock_inversion_fail(dispatch_order_frame_t dof,
+ dispatch_queue_t top_q, dispatch_queue_t bottom_q)
+{
+ _SIMPLE_STRING buf = _simple_salloc();
+ const char *leading_word = "with";
+
+ _simple_sprintf(buf, "%s Lock inversion detected\n"
+ "queue [%s] trying to sync onto queue [%s] conflicts\n",
+ DISPATCH_ASSERTION_FAILED_MESSAGE,
+ bottom_q->dq_label ?: "", top_q->dq_label ?: "");
+
+ while (dof) {
+ dispatch_queue_order_entry_t e = dof->dof_e;
+ char **symbols;
+
+ _simple_sprintf(buf,
+ "%s queue [%s] syncing onto queue [%s] at:\n", leading_word,
+ dof->dof_e->dqoe_bottom_label, dof->dof_e->dqoe_top_label);
+
+ symbols = backtrace_symbols(e->dqoe_pcs, e->dqoe_pcs_n);
+ if (symbols) {
+ for (int i = 0; i < e->dqoe_pcs_n; i++) {
+ _simple_sprintf(buf, "%s\n", symbols[i]);
+ }
+ free(symbols);
+ } else {
+ _simple_sappend(buf, "<missing backtrace>\n");
+ }
+
+ leading_word = "and";
+ dof = dof->dof_prev;
+ }
+
+ // <rdar://problem/25053293> turn off the feature for crash handlers
+ _dispatch_introspection.debug_queue_inversions = false;
+ _dispatch_assert_crash(_simple_string(buf));
+ _simple_sfree(buf);
+}
+
+static void
+_dispatch_introspection_order_check(dispatch_order_frame_t dof_prev,
+ dispatch_queue_t top_q, dispatch_queue_t top_tq,
+ dispatch_queue_t bottom_q, dispatch_queue_t bottom_tq)
+{
+ struct dispatch_order_frame_s dof = { .dof_prev = dof_prev };
+
+ // has anyone above bottom_tq ever sync()ed onto top_tq ?
+ _dispatch_unfair_lock_lock(&bottom_tq->diq_order_top_head_lock);
+ TAILQ_FOREACH(dof.dof_e, &bottom_tq->diq_order_top_head, dqoe_order_top_list) {
+ if (slowpath(dof.dof_e->dqoe_bottom_tq == top_tq)) {
+ _dispatch_introspection_lock_inversion_fail(&dof, top_q, bottom_q);
+ }
+ _dispatch_introspection_order_check(&dof, top_q, top_tq,
+ bottom_q, dof.dof_e->dqoe_bottom_tq);
+ }
+ _dispatch_unfair_lock_unlock(&bottom_tq->diq_order_top_head_lock);
+}
+
+void
+_dispatch_introspection_order_record(dispatch_queue_t top_q,
+ dispatch_queue_t bottom_q)
+{
+ dispatch_queue_order_entry_t e, it;
+ const int pcs_skip = 1, pcs_n_max = 128;
+ void *pcs[pcs_n_max];
+ int pcs_n;
+
+ if (!bottom_q || !bottom_q->do_targetq || !top_q->do_targetq) {
+ return;
+ }
+
+ dispatch_queue_t top_tq = _dispatch_queue_bottom_target_queue(top_q);
+ dispatch_queue_t bottom_tq = _dispatch_queue_bottom_target_queue(bottom_q);
+
+ _dispatch_unfair_lock_lock(&top_tq->diq_order_top_head_lock);
+ TAILQ_FOREACH(it, &top_tq->diq_order_top_head, dqoe_order_top_list) {
+ if (it->dqoe_bottom_tq == bottom_tq) {
+ // that dispatch_sync() is known and validated
+ // move on
+ _dispatch_unfair_lock_unlock(&top_tq->diq_order_top_head_lock);
+ return;
+ }
+ }
+ _dispatch_unfair_lock_unlock(&top_tq->diq_order_top_head_lock);
+
+ _dispatch_introspection_order_check(NULL, top_q, top_tq, bottom_q, bottom_tq);
+ pcs_n = MAX(backtrace(pcs, pcs_n_max) - pcs_skip, 0);
+
+ bool copy_top_label = false, copy_bottom_label = false;
+ size_t size = sizeof(struct dispatch_queue_order_entry_s)
+ + (size_t)pcs_n * sizeof(void *);
+
+ if (_dispatch_queue_label_needs_free(top_q)) {
+ size += strlen(top_q->dq_label) + 1;
+ copy_top_label = true;
+ }
+ if (_dispatch_queue_label_needs_free(bottom_q)) {
+ size += strlen(bottom_q->dq_label) + 1;
+ copy_bottom_label = true;
+ }
+
+ e = _dispatch_calloc(1, size);
+ e->dqoe_top_tq = top_tq;
+ e->dqoe_bottom_tq = bottom_tq;
+ e->dqoe_pcs_n = pcs_n;
+ memcpy(e->dqoe_pcs, pcs + pcs_skip, (size_t)pcs_n * sizeof(void *));
+ // and then lay out the names of the queues at the end
+ char *p = (char *)(e->dqoe_pcs + pcs_n);
+ if (copy_top_label) {
+ e->dqoe_top_label = strcpy(p, top_q->dq_label);
+ p += strlen(p) + 1;
+ } else {
+ e->dqoe_top_label = top_q->dq_label ?: "";
+ }
+ if (copy_bottom_label) {
+ e->dqoe_bottom_label = strcpy(p, bottom_q->dq_label);
+ } else {
+ e->dqoe_bottom_label = bottom_q->dq_label ?: "";
+ }
+
+ _dispatch_unfair_lock_lock(&top_tq->diq_order_top_head_lock);
+ TAILQ_FOREACH(it, &top_tq->diq_order_top_head, dqoe_order_top_list) {
+ if (slowpath(it->dqoe_bottom_tq == bottom_tq)) {
+ // someone else validated it at the same time
+ // go away quickly
+ _dispatch_unfair_lock_unlock(&top_tq->diq_order_top_head_lock);
+ free(e);
+ return;
+ }
+ }
+ TAILQ_INSERT_HEAD(&top_tq->diq_order_top_head, e, dqoe_order_top_list);
+ _dispatch_unfair_lock_unlock(&top_tq->diq_order_top_head_lock);
+
+ _dispatch_unfair_lock_lock(&bottom_tq->diq_order_bottom_head_lock);
+ TAILQ_INSERT_HEAD(&bottom_tq->diq_order_bottom_head, e, dqoe_order_bottom_list);
+ _dispatch_unfair_lock_unlock(&bottom_tq->diq_order_bottom_head_lock);
+}
+
+void
+_dispatch_introspection_target_queue_changed(dispatch_queue_t dq)
+{
+ if (!_dispatch_introspection.debug_queue_inversions) return;
+
+ if (_dispatch_queue_atomic_flags(dq) & DQF_TARGETED) {
+ _dispatch_log(
+ "BUG IN CLIENT OF LIBDISPATCH: queue inversion debugging "
+ "cannot be used with code that changes the target "
+ "of a queue already targeted by other dispatch objects\n"
+ "queue %p[%s] was already targeted by other dispatch objects",
+ dq, dq->dq_label ?: "");
+ _dispatch_introspection.debug_queue_inversions = false;
+ return;
+ }
+
+ static char const * const reasons[] = {
+ [1] = "an initiator",
+ [2] = "a recipient",
+ [3] = "both an initiator and a recipient"
+ };
+ bool as_top = !TAILQ_EMPTY(&dq->diq_order_top_head);
+ bool as_bottom = !TAILQ_EMPTY(&dq->diq_order_top_head);
+
+ if (as_top || as_bottom) {
+ _dispatch_log(
+ "BUG IN CLIENT OF LIBDISPATCH: queue inversion debugging "
+ "expects queues to not participate in dispatch_sync() "
+ "before their setup is complete\n"
+ "forgetting that queue 0x%p[%s] participated as %s of "
+ "a dispatch_sync", dq, dq->dq_label ?: "",
+ reasons[(int)as_top + 2 * (int)as_bottom]);
+ _dispatch_unfair_lock_lock(&_dispatch_introspection.queues_lock);
+ _dispatch_introspection_queue_order_dispose(dq);
+ _dispatch_unfair_lock_unlock(&_dispatch_introspection.queues_lock);
+ }
+}
+
projects / apple / libdispatch.git / blobdiff