From owner-freebsd-hackers@FreeBSD.ORG  Wed Aug  6 15:20:04 2003
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: freebsd-hackers@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id 3568737B401
	for <freebsd-hackers@freebsd.org>;
	Wed,  6 Aug 2003 15:20:04 -0700 (PDT)
Received: from smtp5.Stanford.EDU (smtp5.Stanford.EDU [171.67.16.30])
	by mx1.FreeBSD.org (Postfix) with ESMTP id C08E043F93
	for <freebsd-hackers@freebsd.org>;
	Wed,  6 Aug 2003 15:20:03 -0700 (PDT)
	(envelope-from tedu@stanford.edu)
Received: (from root@localhost)
	by smtp5.Stanford.EDU (8.12.9/8.12.9) id h76MK3FN024793
	for freebsd-hackers@freebsd.org; Wed, 6 Aug 2003 15:20:03 -0700 (PDT)
Received: from saga0.Stanford.EDU (saga0.Stanford.EDU [171.64.15.130])
	by smtp5.Stanford.EDU (8.12.9/8.12.9) with ESMTP id h76MK1x9024773
	for <freebsd-hackers@freebsd.org>;
	Wed, 6 Aug 2003 15:20:02 -0700 (PDT)
Date: Wed, 6 Aug 2003 15:20:02 -0700 (PDT)
From: Ted Unangst <tedu@stanford.edu>
To: freebsd-hackers@freebsd.org
Message-ID: <Pine.GSO.4.44.0308061506120.29218-100000@saga0.Stanford.EDU>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Subject: possible deadlocks?
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.1
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Wed, 06 Aug 2003 22:20:04 -0000

My advisor Dawson Engler has written a deadlock detector, and we'd like
some verification. They look like bugs, unless there is some other reason
why two call chains cannot happen at the same time.

deadlock between ktrace_mtx and sema_mtx.  is it possible to call
sema_timewait on ktrace_sema?  call chain below.

thread 1:
_sema_timedwait(sema, ...)
  mtx_lock(&sema->sema_mtx) /* gets this lock */
    cv_timewait()
      ktrcsw()
        ktr_getrequest()
          mtx_lock(&ktrace_mtx) /* waits for thread 2 */

thread 2:
ktr_submitrequest
  mtx_lock(&ktrace_mtx) /* gets this lock */
    _sema_post(&ktrace_sema)
      mtx_lock(&sema->sema_mtx) /* waits for thread 1 */

second one in bpf, between bpfif_lock and bpfd_lock.

thread 1:
bpf_tap() /* or bpf_mtap */
  BPFIF_LOCK(bp); /* gets this lock */
  for (d = bp->bif_dlist; d != 0; d = d->bd_next) {
	BPFD_LOCK(d); /* waits for thread 2 */

thread 2:
bpf_setdlt()
  BPFD_LOCK(d); /* gets lock */
  bpf_detachd(d); /* or bpf_attachd */
    BPFIF_LOCK(bp); /* waits for thread 1 */





-- 
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
      - M. Barry, Mayor of Washington, DC