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: 48+ 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 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 01/11] fork: introduce kernel_clone() Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 02/11] h8300: switch to kernel_clone() Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 03/11] ia64: " Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 04/11] m68k: " Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-19 8:45 ` Geert Uytterhoeven
2020-08-19 8:45 ` Geert Uytterhoeven
2020-08-18 17:34 ` [PATCH 05/11] nios2: " Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 06/11] sparc: " Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 07/11] x86: " Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 08/11] kprobes: " Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 09/11] kgdbts: " Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 10/11] tracing: " Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:34 ` [PATCH 11/11] sched: remove _do_fork() Christian Brauner
2020-08-18 17:34 ` Christian Brauner
2020-08-18 17:44 ` [PATCH 00/11] Introduce kernel_clone(), kill _do_fork() Matthew Wilcox
2020-08-18 17:44 ` Matthew Wilcox
2020-08-18 17:57 ` Christian Brauner
2020-08-18 17:57 ` Christian Brauner
2020-08-19 7:43 ` peterz
2020-08-19 7:43 ` peterz
2020-08-19 8:45 ` Christian Brauner
2020-08-19 8:45 ` Christian Brauner
2020-08-19 11:18 ` Matthew Wilcox
2020-08-19 11:18 ` Matthew Wilcox
2020-08-19 13:32 ` Eric W. Biederman
2020-08-19 13:32 ` Eric W. Biederman
2020-08-19 13:46 ` Christian Brauner
2020-08-19 13:46 ` Christian Brauner
2020-08-19 15:01 ` Eric W. Biederman
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:45 ` Matthew Wilcox
2020-08-19 15:55 ` David Laight [this message]
2020-08-19 16:24 ` Matthew Wilcox
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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.