From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on archive.lwn.net X-Spam-Level: X-Spam-Status: No, score=-5.8 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham autolearn_force=no version=3.4.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by archive.lwn.net (Postfix) with ESMTP id 755CB7D08A for ; Thu, 8 Nov 2018 14:07:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727336AbeKHXmw (ORCPT ); Thu, 8 Nov 2018 18:42:52 -0500 Received: from bombadil.infradead.org ([198.137.202.133]:58586 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727252AbeKHXmv (ORCPT ); Thu, 8 Nov 2018 18:42:51 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=In-Reply-To:Content-Type:MIME-Version :References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=DTB5Db2QQGkl5qIo6RBvU8cT7ULvRooewpvdpybfBlc=; b=qtgZpzN24OGaQGpEG0gcHxOXX 4q5sJ/7lr+vCr2TJ62vWILyHEyF2qzBalDvyExPK+QtUV79BIyOyBLBOdR8nkbtLJnFokqOpMEtFT yd5B6qbzQ7sNOIiaLo7FeIp+mBE1YqezvNct1bahCH7+Z+N+tuDuDn4QDvp2zYmN6BzgmgHW4Bqh/ eHYMDespxt/ZF6ToIiA+rjuzKLWlNy5atzwYUip4/TCJQuecljm3y5LCjxXMjXc6O1hCLeZMgjVlr mRb5b3C4a8eRFMRqONijMLIfjpnpCYmRlSDc9TH5uh4F+oNMEiPtNHgAfh7ZHf6qHolEVQOz+xm+O 0ryH9WegA==; Received: from willy by bombadil.infradead.org with local (Exim 4.90_1 #2 (Red Hat Linux)) id 1gKkxf-0002os-TG; Thu, 08 Nov 2018 14:07:07 +0000 Date: Thu, 8 Nov 2018 06:07:07 -0800 From: Matthew Wilcox To: David Laight Cc: 'Martin Steigerwald' , Michal Hocko , Daniel Colascione , linux-kernel , "rppt@linux.ibm.com" , Tim Murray , Joel Fernandes , Suren Baghdasaryan , Jonathan Corbet , Andrew Morton , Roman Gushchin , Mike Rapoport , Vlastimil Babka , "Kirill A. Shutemov" , "Dennis Zhou (Facebook)" , Prashant Dhamdhere , "open list:DOCUMENTATION" Subject: Re: [PATCH v2] Document /proc/pid PID reuse behavior Message-ID: <20181108140707.GO3074@bombadil.infradead.org> References: <20181031150625.147369-1-dancol@google.com> <20181107160015.GI27423@dhcp22.suse.cz> <4536090.43ZsV6LvYe@merkaba> <0c5610f128fa49fb9d8f7859e6f61b90@AcuMS.aculab.com> <20181108122747.GM3074@bombadil.infradead.org> <47072118046a450b904556ca8154f5c9@AcuMS.aculab.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <47072118046a450b904556ca8154f5c9@AcuMS.aculab.com> User-Agent: Mutt/1.9.2 (2017-12-15) Sender: linux-doc-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-doc@vger.kernel.org On Thu, Nov 08, 2018 at 01:42:41PM +0000, David Laight wrote: > From: Matthew Wilcox > > On Thu, Nov 08, 2018 at 12:02:49PM +0000, David Laight wrote: > > > This can be mitigated by only allocating 'big' numbers on systems > > > that have a lot of pids. > > > You also really want an O(1) allocator. > > > > The allocator is O(log n) -- it's the IDR allocator, used in cyclic mode. > > n in this case is the highest ID which is still in use. The tree is > > log_64(n) levels high. It walks to the bottom of the tree and puts a > > pointer into the tree. If the cursor has wrapped to the beginning of > > the tree, it may encounter a PID which is still in use; if it does, > > it does a bitmap scan of that node, and will then walk up the tree, > > doing a bitmap scan forward at each level until it finds a free PID. > > Right, but you can choose the pid so that you get a perfect hash. > You can then put a FIFO free list through the unused entries of > the hash table (just an array). > Then pid allocate just picks the oldest free entry and ups the > high bits (that the hash masks out) to make the old value stale. > Almost no cache lines are involved in the whole operation. You'd be looking for something like dynamic perfect hashing then? I think that'd make a great project for someone to try out. I don't have the time to look into it myself, and I'm not convinced there's a real workload that would benefit. But it'd be a great project for a university student.