From owner-freebsd-current  Wed Sep 24 12:02:10 1997
Return-Path: <owner-freebsd-current>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id MAA18496
          for current-outgoing; Wed, 24 Sep 1997 12:02:10 -0700 (PDT)
Received: from alpo.whistle.com (alpo.whistle.com [207.76.204.38])
          by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id MAA18485
          for <current@FreeBSD.ORG>; Wed, 24 Sep 1997 12:02:05 -0700 (PDT)
Received: (from daemon@localhost)
	by alpo.whistle.com (8.8.5/8.8.5) id MAA06036;
	Wed, 24 Sep 1997 12:00:18 -0700 (PDT)
Received: from current1.whistle.com(207.76.205.22)
 via SMTP by alpo.whistle.com, id smtpd006027; Wed Sep 24 19:00:09 1997
Message-ID: <3429630C.167EB0E7@whistle.com>
Date: Wed, 24 Sep 1997 11:59:24 -0700
From: Julian Elischer <julian@whistle.com>
Organization: Whistle Communications
X-Mailer: Mozilla 3.0Gold (X11; I; FreeBSD 2.2-CURRENT i386)
MIME-Version: 1.0
To: "Justin T. Gibbs" <gibbs@plutotech.com>
CC: Nate Williams <nate@mt.sri.com>, Terry Lambert <tlambert@primenet.com>,
        bde@zeta.org.au, current@FreeBSD.ORG
Subject: Re: new timeout routines
References: <199709241651.KAA23972@pluto.plutotech.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-freebsd-current@FreeBSD.ORG
X-Loop: FreeBSD.org
Precedence: bulk

Justin T. Gibbs wrote:
> 
> >> No-one said this wasn't possible.  It just takes additional space and
> >> makes untimeout's running time non-deterministic.  I decided it was
> >> an unacceptable tradeoff.
> >
> >How do you figure?  untimeout is now the same as it was before, or
> >aren't the cookies based on a hash table?
> 
> The cookie is essentially a direct pointer to the entry that needs to
> be removed.  So, removal takes constant time.  In your scheme, you need
> to allocate an additional hash table and add a set of links to each
> callout entry so it can live both in the callwheel and in the hash
> table.  Then, in untimeout, you must traverse a hash chain of indeterminate
> length in order to find the entry, hence it is no longer a constant time
> operation.  This wouldn't be a problem if untimeout wasn't called from
> interrupt contexts, but it is.
> 
so what happens if I call untimeout twice?
there is an assumption in a lot of code that untimeout is idempotent
(did I get that right?). It can be called whenever you are recovering
from unknown situations with the sure knowledge that the appropriate
timeout will be removed.

1/ there is no way to do this without lots of work now.
2/ old code will break.


do you check for a NULL pointer? (I have read the paper but not the code
(yet)

> >Nate
> 
> --
> Justin T. Gibbs
> ===========================================
>   FreeBSD: Turning PCs into workstations
> ===========================================