From owner-freebsd-hackers@FreeBSD.ORG Sun Feb 19 03:42:49 2012 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 21097106566B; Sun, 19 Feb 2012 03:42:49 +0000 (UTC) (envelope-from mavbsd@gmail.com) Received: from mail-wi0-f182.google.com (mail-wi0-f182.google.com [209.85.212.182]) by mx1.freebsd.org (Postfix) with ESMTP id 839C68FC23; Sun, 19 Feb 2012 03:42:48 +0000 (UTC) Received: by wibhn14 with SMTP id hn14so3596521wib.13 for ; Sat, 18 Feb 2012 19:42:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=KCvprXBcf8T22f4yb3FMicX2y5uFeV/N6FAYET98ByI=; b=vHtfa3jltjEVEQLPdaqsXoFcSuV8pYcUwElYAHFjVUyZs2nQDqxKBXgCAG6ODOZ9dC TqpFMc6UXH7fPZR6xR6hlMkzqs7wPNn6V951b2mJoIIrUbkRZyfpA77jMGHtDHKb4vfw DRVR+FX8wRNeZBm6QOce+v5wO29VXvjIlg4cs= Received: by 10.181.12.106 with SMTP id ep10mr7303403wid.8.1329622967513; Sat, 18 Feb 2012 19:42:47 -0800 (PST) Received: from mavbook.mavhome.dp.ua (95-109-204-113.dialup.umc.net.ua. [95.109.204.113]) by mx.google.com with ESMTPS id ec3sm7109707wib.1.2012.02.18.19.42.42 (version=SSLv3 cipher=OTHER); Sat, 18 Feb 2012 19:42:46 -0800 (PST) Sender: Alexander Motin Message-ID: <4F406FA2.4040502@FreeBSD.org> Date: Sun, 19 Feb 2012 05:42:26 +0200 From: Alexander Motin User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:9.0) Gecko/20120116 Thunderbird/9.0 MIME-Version: 1.0 To: Andriy Gapon References: <4F3FF690.5050600@FreeBSD.org> <4F3FFF33.2050700@FreeBSD.org> <4F400CC1.8030504@FreeBSD.org> In-Reply-To: <4F400CC1.8030504@FreeBSD.org> Content-Type: text/plain; charset=KOI8-R; format=flowed Content-Transfer-Encoding: 7bit Cc: freebsd-hackers@FreeBSD.org Subject: Re: callouts precision X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 19 Feb 2012 03:42:49 -0000 On 18.02.2012 22:40, Andriy Gapon wrote: > on 18/02/2012 21:42 Alexander Motin said the following: >> On 18.02.2012 21:05, Andriy Gapon wrote: >>> Just want to double-check myself. >>> It seems that currently, thanks to event timers, we mostly should be able to >>> schedule a hardware timer to fire at almost arbitrary moment with very fine >>> precision. >>> OTOH, our callout subsystem still seems to be completely tick oriented in the >>> sense that all timeouts are specified and kept in ticks. >>> As a result, it's impossible to use e.g. nanosleep(2) with a precision better >>> than HZ. >>> >>> How deeply ticks are ingrained into callout(9)? Are they used only as a measure >>> of time? Or are there any dependencies on them being integers, like for >>> indexing, etc? >>> In other words, how hard it would be to replace ticks with e.g. bintime as an >>> internal representation of time in callout(9) [leaving interfaces alone for the >>> start]? Is it easier to retrofit that code or to replace it with something new? >> >> Pending callouts are now stored in large array of unsorted lists, where last >> bits of callout time is the array index. It is quite effective for insert/delete >> operation. It is ineffective for getting next event time needed for new event >> timers, but it is rare operation. Using arbitrary time values in that case is >> very problematic. It would require complete internal redesign. >> > > I see. Thank you for the insight! > > One possible hack that I can think of is to use "pseudo-ticks" in the callout > implementation instead of real ticks. E.g. such a pseudo-tick could be set > equal to 1 microsecond instead of 1/hz (it could be tunable). Then, of course, > instead of driving the callouts via hardclock/softclock, they would have to be > driven directly from event timers. And they would have to use current > microseconds uptime instead of ticks, obviously. This would also require a > revision of types used to store timeout values. Current 'int' would not be > adequate anymore, it seems. I don't think it will work. With so high frequency it will make callouts distribution over the array almost random. While insert / remove operations will still be cheap, search for the next event will be 1000 times more expensive. Unless you propose increase array size 1000 times, it will not be better then just using single unsorted link, > It looks like Timer_Wheel_T from ACE has some useful enhancements in this direction. > > BTW, it seems that with int ticks and HZ of 1000, ticks would overflow from > INT_MAX to INT_MIN in ~24 days. I can imagine that some code might get confused > by such an overflow. But that's a different topic. Probably you are right. I've seen few dangerous comparisons in ULE code. -- Alexander Motin