From owner-freebsd-hackers@FreeBSD.ORG Sat Mar 26 03:04:29 2005 Return-Path: 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 87CC716A4CE for ; Sat, 26 Mar 2005 03:04:29 +0000 (GMT) Received: from VARK.MIT.EDU (VARK.MIT.EDU [18.95.3.179]) by mx1.FreeBSD.org (Postfix) with ESMTP id 95F8543D5F for ; Sat, 26 Mar 2005 03:04:28 +0000 (GMT) (envelope-from das@FreeBSD.ORG) Received: from VARK.MIT.EDU (localhost [127.0.0.1]) by VARK.MIT.EDU (8.13.3/8.13.1) with ESMTP id j2Q34PF6041577; Fri, 25 Mar 2005 22:04:25 -0500 (EST) (envelope-from das@FreeBSD.ORG) Received: (from das@localhost) by VARK.MIT.EDU (8.13.3/8.13.1/Submit) id j2Q34O7R041576; Fri, 25 Mar 2005 22:04:24 -0500 (EST) (envelope-from das@FreeBSD.ORG) Date: Fri, 25 Mar 2005 22:04:24 -0500 From: David Schultz To: Andriy Tkachuk Message-ID: <20050326030424.GA41481@VARK.MIT.EDU> Mail-Followup-To: Andriy Tkachuk , freebsd-hackers@FreeBSD.ORG References: <006401c53128$e6c6d390$090210ac@BORJA> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <006401c53128$e6c6d390$090210ac@BORJA> cc: freebsd-hackers@FreeBSD.ORG Subject: Re: contributing to fbsd X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 26 Mar 2005 03:04:29 -0000 On Fri, Mar 25, 2005, Andriy Tkachuk wrote: > As I see now there is for example O(n) algorithm for > process IDs allocation... In linux it is addressed > using bit-mapping (as far as i understand). > In Oct 2003 there was topic in this list: > "Some mmap observations compared to Linux 2.6/OpenBSD" > in which allocation in mmap was discussed. > As it was appeared that fbsd use O(n) algorithm here compared > to Linux and OpenBSD. I don't know the presend state of this. tjr has some patches to do O(1) pid allocation, although I believe he's been busy with work recently. Jun Su ported NetBSD's O(1) pid allocator, although that allocator is significantly more complicated, and not measurably faster. So basically this is already done; someone just needs to get around to integrating it. pids are hard to do generically because of the special rules about allocating them. You don't want to recycle them too quickly, for instance. > Anyway as for me it looks very attractive to have > universal O(1) facility for allocation of any kernel resources > as well as on smp-configurations than using differend > adhoc's in different parts of kernel. > I seems to me, that Linux doesn't also use some > universal allocation approach but O(1) adhocs instead. > I may mistaken in this. You should also take a look at FreeBSD's kern/subr_unit.c. It isn't as fast as vmem, but perhaps it's fast enough. The first thing to do would be to do some profiling on current and potential applications of the allocator to see where your time would be best spent.