From: David Laight <David.Laight@ACULAB.COM>
To: 'Matthew Wilcox' <willy@infradead.org>
Cc: "'Eric W. Biederman'" <ebiederm@xmission.com>,
Christian Brauner <christian.brauner@ubuntu.com>,
"peterz@infradead.org" <peterz@infradead.org>,
Christoph Hewllig <hch@infradead.org>,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
Linus Torvalds <torvalds@linux-foundation.org>,
"linux-arch@vger.kernel.org" <linux-arch@vger.kernel.org>,
Jonathan Corbet <corbet@lwn.net>,
"Yoshinori Sato" <ysato@users.sourceforge.jp>,
Tony Luck <tony.luck@intel.com>,
"Fenghua Yu" <fenghua.yu@intel.com>,
Geert Uytterhoeven <geert@linux-m68k.org>,
"Ley Foon Tan" <ley.foon.tan@intel.com>,
"David S. Miller" <davem@davemloft.net>,
Thomas Gleixner <tglx@linutronix.de>,
Ingo Molnar <mingo@redhat.com>, Borislav Petkov <bp@alien8.de>,
"x86@kernel.org" <x86@kernel.org>,
"Arnd Bergmann" <arnd@arndb.de>,
Steven Rostedt <rostedt@goodmis.org>,
"Stafford Horne" <shorne@gmail.com>,
Kars de Jong <jongk@linux-m68k.org>,
Kees Cook <keescook@chromium.org>,
Greentime Hu <green.hu@gmail.com>,
"Mauro Carvalho Chehab" <mchehab+huawei@kernel.org>,
Alexandre Chartre <alexandre.chartre@oracle.com>,
Masami Hiramatsu <mhiramat@kernel.org>,
"Tom Zanussi" <zanussi@kernel.org>,
Xiao Yang <yangx.jy@cn.fujitsu.com>,
"linux-doc@vger.kernel.org" <linux-doc@vger.kernel.org>,
"uclinux-h8-devel@lists.sourceforge.jp"
<uclinux-h8-devel@lists.sourceforge.jp>,
"linux-ia64@vger.kernel.org" <linux-ia64@vger.kernel.org>,
"linux-m68k@lists.linux-m68k.org"
<linux-m68k@lists.linux-m68k.org>,
"sparclinux@vger.kernel.org" <sparclinux@vger.kernel.org>,
"kgdb-bugreport@lists.sourceforge.net"
<kgdb-bugreport@lists.sourceforge.net>,
"linux-kselftest@vger.kernel.org"
<linux-kselftest@vger.kernel.org>
Subject: RE: [PATCH 00/11] Introduce kernel_clone(), kill _do_fork()
Date: Wed, 19 Aug 2020 15:55:47 +0000 [thread overview]
Message-ID: <ee30fecfbd534c19a6bfd11d2c4b8263@AcuMS.aculab.com> (raw)
In-Reply-To: <20200819154521.GE17456@casper.infradead.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)
next prev parent reply other threads:[~2020-08-19 15:55 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-08-18 17:34 [PATCH 00/11] Introduce kernel_clone(), kill _do_fork() Christian Brauner
2020-08-18 17:34 ` [PATCH 01/11] fork: introduce kernel_clone() Christian Brauner
2020-08-18 17:34 ` [PATCH 02/11] h8300: switch to kernel_clone() Christian Brauner
2020-08-18 17:34 ` [PATCH 03/11] ia64: " Christian Brauner
2020-08-18 17:34 ` [PATCH 04/11] m68k: " Christian Brauner
2020-08-19 8:45 ` Geert Uytterhoeven
2020-08-18 17:34 ` [PATCH 05/11] nios2: " Christian Brauner
2020-08-18 17:34 ` [PATCH 06/11] sparc: " Christian Brauner
2020-08-18 17:34 ` [PATCH 07/11] x86: " Christian Brauner
2020-08-18 17:34 ` [PATCH 08/11] kprobes: " Christian Brauner
2020-08-18 17:34 ` [PATCH 09/11] kgdbts: " Christian Brauner
2020-08-18 17:34 ` [PATCH 10/11] tracing: " Christian Brauner
2020-08-18 17:34 ` [PATCH 11/11] sched: remove _do_fork() Christian Brauner
2020-08-18 17:44 ` [PATCH 00/11] Introduce kernel_clone(), kill _do_fork() Matthew Wilcox
2020-08-18 17:57 ` Christian Brauner
2020-08-19 7:43 ` peterz
2020-08-19 8:45 ` Christian Brauner
2020-08-19 11:18 ` Matthew Wilcox
2020-08-19 13:32 ` Eric W. Biederman
2020-08-19 13:46 ` Christian Brauner
2020-08-19 15:01 ` Eric W. Biederman
2020-08-19 15:41 ` David Laight
2020-08-19 15:45 ` Matthew Wilcox
2020-08-19 15:55 ` David Laight [this message]
2020-08-19 16:24 ` Matthew Wilcox
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=ee30fecfbd534c19a6bfd11d2c4b8263@AcuMS.aculab.com \
--to=david.laight@aculab.com \
--cc=alexandre.chartre@oracle.com \
--cc=arnd@arndb.de \
--cc=bp@alien8.de \
--cc=christian.brauner@ubuntu.com \
--cc=corbet@lwn.net \
--cc=davem@davemloft.net \
--cc=ebiederm@xmission.com \
--cc=fenghua.yu@intel.com \
--cc=geert@linux-m68k.org \
--cc=green.hu@gmail.com \
--cc=hch@infradead.org \
--cc=jongk@linux-m68k.org \
--cc=keescook@chromium.org \
--cc=kgdb-bugreport@lists.sourceforge.net \
--cc=ley.foon.tan@intel.com \
--cc=linux-arch@vger.kernel.org \
--cc=linux-doc@vger.kernel.org \
--cc=linux-ia64@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-kselftest@vger.kernel.org \
--cc=linux-m68k@lists.linux-m68k.org \
--cc=mchehab+huawei@kernel.org \
--cc=mhiramat@kernel.org \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
--cc=rostedt@goodmis.org \
--cc=shorne@gmail.com \
--cc=sparclinux@vger.kernel.org \
--cc=tglx@linutronix.de \
--cc=tony.luck@intel.com \
--cc=torvalds@linux-foundation.org \
--cc=uclinux-h8-devel@lists.sourceforge.jp \
--cc=willy@infradead.org \
--cc=x86@kernel.org \
--cc=yangx.jy@cn.fujitsu.com \
--cc=ysato@users.sourceforge.jp \
--cc=zanussi@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).