From mboxrd@z Thu Jan 1 00:00:00 1970 From: Matthew Wilcox Date: Wed, 19 Aug 2020 15:45:21 +0000 Subject: Re: [PATCH 00/11] Introduce kernel_clone(), kill _do_fork() Message-Id: <20200819154521.GE17456@casper.infradead.org> 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> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: David Laight 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" 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)