Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 8 Aug 2002 17:46:11 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 8 Aug 2002 17:46:11 -0400 Received: from e1.ny.us.ibm.com ([32.97.182.101]:7371 "EHLO e1.ny.us.ibm.com") by vger.kernel.org with ESMTP id ; Thu, 8 Aug 2002 17:46:08 -0400 Subject: Re: [PATCH] Linux-2.5 fix/improve get_pid() To: Linus Torvalds Cc: Andrew Morton , andrea@suse.de, davej@suse.de, lkml , Paul Larson X-Mailer: Lotus Notes Release 5.0.10 March 22, 2002 Message-ID: From: Hubertus Franke Date: Thu, 8 Aug 2002 17:50:16 -0400 X-MIMETrack: Serialize by Router on D01ML244/01/M/IBM(Build V60_M14_08012002 Release Candidate|August 01, 2002) at 08/08/2002 17:48:41 MIME-Version: 1.0 Content-type: text/plain; charset=US-ASCII Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 4202 Lines: 92 Agreed .... The mark-and-sweep is the correct method for 16-bits ! For 32-bits its not possible ! Two level is over-engineered (as I told Paul). If you want I can post the data that I collected comparing (a) stock kernel (b) my mark and sweep (c) my double mark and sweep (try looking forward and then scan task list) ? Let me know if you are interested. That should clear up the issue quickly giving you some average allocation times etc..... as a function of random used pids. Hubertus Franke Enterprise Linux Group (Mgr), Linux Technology Center (Member Scalability) , OS-PIC (Chair) email: frankeh@us.ibm.com (w) 914-945-2003 (fax) 914-945-4425 TL: 862-2003 Linus Torvalds ta.com> cc: Paul Larson , lkml , , Hubertus Franke/Watson/IBM@IBMUS, 08/08/2002 04:24 Subject: Re: [PATCH] Linux-2.5 fix/improve get_pid() PM On Wed, 7 Aug 2002, Andrew Morton wrote: > > Has this been evaluated against Bill Irwin's constant-time > allocator? Bill says it has slightly worse normal-case and > vastly improved worst-case performance over the stock allocator. > Not sure how it stacks up against this one. Plus it's much nicer > looking code. Guys, this discussion is getting ridiculous. Doing a bit allocator should be trivial, but it's hard to know when a bit is to be free'd. You can't just do it at "exit()" time, because even if pid X exits, that doesn't mean that X can be re-used: it may still be used as a pgid or a tid by some other process Y. So if you really want to take this approach, you need to count the uses of "pid X", and free the bitmap entry only when that count goes to zero. I see no such logic in Bill Irwin's code, only a comment about last use (which doesn't explain how to notice that last use). Without that per-pid-count thing clarified, I don't think the (otherwise fairly straightforward) approach of Bills really flies. For that reason I think the mark-and-sweep thing is the right thing to do, but I think the two-level algorithm is just over-engineering and not worth it. And I do hate that getpid_mutex thing. Having a blocking lock for something as simple as pid allocation just smells horribly wrong to me. Moving the pid allocation to later (so that it doesn't need to handle operations that block in between allocation and "we're done" and the pid allocation can be a spinlock) sounds like a fairly obvious thing to do. I don't see why we would need the "pid" until the very last moment, at which point we already have the tasklist lock, in fact. And I hate overengineering. Linus - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/