From mboxrd@z Thu Jan 1 00:00:00 1970 From: David Laight Date: Wed, 19 Aug 2020 15:55:47 +0000 Subject: RE: [PATCH 00/11] Introduce kernel_clone(), kill _do_fork() Message-Id: List-Id: References: <20200818173411.404104-1-christian.brauner@ubuntu.com> <20200818174447.GV17456@casper.infradead.org> <20200819074340.GW2674@hirez.programming.kicks-ass.net> <20200819084556.im5zfpm2iquzvzws@wittgenstein> <20200819111851.GY17456@casper.infradead.org> <87a6yq222c.fsf@x220.int.ebiederm.org> <20200819134629.mvd4nupme7q2hmtz@wittgenstein> <87mu2qznlv.fsf@x220.int.ebiederm.org> <20200819154521.GE17456@casper.infradead.org> In-Reply-To: <20200819154521.GE17456@casper.infradead.org> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: 'Matthew Wilcox' Cc: "'Eric W. Biederman'" , Christian Brauner , "peterz@infradead.org" , Christoph Hewllig , "linux-kernel@vger.kernel.org" , Linus Torvalds , "linux-arch@vger.kernel.org" , Jonathan Corbet , Yoshinori Sato , Tony Luck , Fenghua Yu , Geert Uytterhoeven , Ley Foon Tan , "David S. Miller" , Thomas Gleixner , Ingo Molnar , Borislav Petkov , "x86@kernel.org" , Arnd Bergmann , Steven Rostedt , Stafford Horne , Kars de Jong , Kees Cook , Greentime Hu , Mauro Carvalho Chehab , Alexandre Chartre , Masami Hiramatsu , Tom Zanussi , Xiao Yang , "linux-doc@vger.kernel.org" , "uclinux-h8-devel@lists.sourceforge.jp" , "linux-ia64@vger.kernel.org" , "linux-m68k@lists.linux-m68k.org" , "sparclinux@vger.kernel.org" , "kgdb-bugreport@lists.sourceforge.net" , "linux-kselftest@vger.kernel.org" From: Matthew Wilcox > Sent: 19 August 2020 16:45 > > On Wed, Aug 19, 2020 at 03:41:48PM +0000, David Laight wrote: > > Does linux have an O(1) (or do I mean o(1)) pid allocator? > > Or does it have to do a linear scan to find a gap?? > > O(log(n)). It uses the IDR allocator, so 'n' in this case is the > number of PIDs currently allocated, and it's log_64 rather than log_2 > (which makes no difference to O() but does make a bit of a difference > to performance) Still worse that O(1) - when that is just replacing a variable with a value read out of an array. Made pid lookup a trivial O(1) as well. David - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)