From owner-freebsd-arch@FreeBSD.ORG Mon Nov 13 21:40:01 2006 Return-Path: X-Original-To: arch@freebsd.org Delivered-To: freebsd-arch@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 5CD5716A4CE for ; Mon, 13 Nov 2006 21:40:01 +0000 (UTC) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (xorpc.icir.org [192.150.187.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id 393DB43D67 for ; Mon, 13 Nov 2006 21:33:01 +0000 (GMT) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (localhost [127.0.0.1]) by xorpc.icir.org (8.12.11/8.13.6) with ESMTP id kADLWbLv029073; Mon, 13 Nov 2006 13:32:37 -0800 (PST) (envelope-from rizzo@xorpc.icir.org) Received: (from rizzo@localhost) by xorpc.icir.org (8.12.11/8.12.3/Submit) id kADLWbt1029072; Mon, 13 Nov 2006 13:32:37 -0800 (PST) (envelope-from rizzo) Date: Mon, 13 Nov 2006 13:32:37 -0800 From: Luigi Rizzo To: Poul-Henning Kamp Message-ID: <20061113133236.A28926@xorpc.icir.org> References: <7105.1163451221@critter.freebsd.dk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <7105.1163451221@critter.freebsd.dk>; from phk@phk.freebsd.dk on Mon, Nov 13, 2006 at 08:53:41PM +0000 Cc: arch@freebsd.org Subject: Re: a proposed callout API X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 13 Nov 2006 21:40:01 -0000 On Mon, Nov 13, 2006 at 08:53:41PM +0000, Poul-Henning Kamp wrote: > > A number of problems have been identified with our current callout > code and I have been thinking about and discussed various aspects > with people during the EuroBSDcon2007 conference. > > A lot of people are interested in this, so here is a quick sketch > of what I'm thinking about: ...
i am a bit curious on why you want to split the callouts among multiple data structures. Basically the heap that you suggest is a very nice and efficient one, (it is used in dummynet among other places), and has O(log N) cost per insertion/deletion. Say you have 64k callouts in total, even if you manage to trim the number of events that you put in the heap to 128-256, you only halve the (small) cost of updates to the heap, but the periodic work for moving events from the extra queues towards the heap can be large, and especially you need to be careful and scatter it, a bit at each tick, to avoid having to scan 10k+ entries at once. cheers luigi > The Problems > ------------ > > 1. We need better resolution than a periodic "hz" clock can give us. > Highspeed networking, gaming servers and other real-time apps want > this. > > 2. We "pollute" our call-wheel with tons of callouts that we know are > unlikely to happen. > > 3. We have many operations on the callout wheel because certain > callouts gets rearmed for later in the future. (TCP keepalives). > > 4. We execute all callouts on one CPU only. > > 5. Most of the specified timeouts are bogus, because of the imprecision > inheret in the current 1/hz method of scheduling them. > > and a number of other issues. > > > The proposed API > ---------------- > > tick_t XXX_ns_tick(unsigned nsec, unsigned *low, unsigned *high); > Caculate the tick value for a given timeout. > Optionally return theoretical lower and upper limits to > actual value, > > tick_t XXX_s_tick(unsigned seconds) > Caculate the tick value for a given timeout. > > The point behind these two functions is that we do not want to > incur a scaling operating at every arming of a callout. Very > few callouts use varying timeouts (and for those, no avoidance > is possible), but for the rest, precalculating the correct > (opaque) number is a good optimization. > > XXX_arm(struct xxx*, tick_t, func *, arg *, int flag, struct mtx *); > Arm timer. > Struct xxx must be zeroed before first call. > > If mtx pointer is non-NULL, acq mutex before calling. > > flags: > XXX_REPEAT > XXX_UNLIKELY > > Arm a callout with a number of optional behaviours specified. > > XXX_rearm(struct xxx*, tick_t) > Rearm timer. > > XXX_disarm(struct xxx*) > Unarm the timer. > > XXX_drain(struct xxx*) > Drain the timer. > > > The functions above will actually be wrappers for a more generic > set of the same family, which also takes a pointer to a callout-group. > > This is so that we can have different groups of callouts, for > instance one group for the/each netstack and one for the disk-I/O > stuff etc. > > > Implementation > -------------- > > Behind the scenes, we will have to support hardware that only > has a HZ style periodic interrupt but also hardware that > can do deadline interrupts (like HPET). > > Short callouts, less than 2 seconds, will be stored in a binary > heap (A tree where a node is numerically lower than its parents.) > > The depth of the heap is Log2(nodes) and there are very efficient > ways to store and access the heap. > > Locking will be with one mutex for the heap. > > The top element which is always the next one to be executed, > will be left in place during execution, so that any rescheduling > (automatic or explicit) will only have to do as little work as > necessary to trickle it down to the right place in the heap. > > Rescheduling a callout is a matter of trickling it up- or downwards > in the tree to a correct position. > > For the long callouts, and for callouts unlikely to happen, a group > of lists are used for storage. > > Imagine the number of lists is four, we then label them with Tnow+2s, > Tnow+8s, Tnow+32s and "the rest". > > Armed callouts go into the first list that is labeled with a higher > strike time. > > If a callout is rescheduled to later, it's timeout is updated, but > it is not moved in the list. > > If a callout is cancled, it is removed from the list. > > Twice per second, the first list is scanned, and any due callouts > called and any callouts later than the lists strike time is moved > into the right list. > > When "Tnow+2s" rolls around, the lists are rotated to the left: > the Tnow+8s becomes "Tnow+2s" etc. > > The idea behind this (untried) scheme for the long callouts, is to > distribute the callouts somewhat evenly in the lists, while maintaining > only the relevant entries in the first list, the point being that > most of them (TCP keepalive, CAM etc) will never happen, so spending > time sorting them more than necessary is pointless. Obviously, > this algorithm needs to be tested in practice and tuned/changed/discared > depending on the results. > > All numbers given are subject to tuning. > > -- > Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 > phk@FreeBSD.ORG | TCP/IP since RFC 956 > FreeBSD committer | BSD since 4.3-tahoe > Never attribute to malice what can adequately be explained by incompetence. > _______________________________________________ > freebsd-arch@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-arch > To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org"