All of lore.kernel.org
 help / color / mirror / Atom feed
From: ebiederm-aS9lmoZGLiVWk0Htik3J/w@public.gmane.org (Eric W. Biederman)
To: Manfred Spraul <manfred-nhLOkwUX5cPe2c5cEj3t2g@public.gmane.org>
Cc: Davidlohr Bueso <dave-h16yJtLeMjHk1uMJSBkQmQ@public.gmane.org>,
	Stanislav Kinsbursky
	<skinsbursky-bzQdu9zFT3WakBO8gow8eQ@public.gmane.org>,
	Kees Cook <keescook-F7+t8E8rja9g9hUCZPvPmw@public.gmane.org>,
	linux-api-u79uwXL29TY76Z2rM5mHXA@public.gmane.org,
	Linux Containers
	<containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org>,
	linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org,
	Matthew Wilcox <willy-wEGCiKHe2LqWVfeAwA7xHQ@public.gmane.org>,
	"Luis R. Rodriguez"
	<mcgrof-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org>,
	Michael Kerrisk
	<mtk.manpages-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>,
	linux-fsdevel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org,
	Waiman Long <longman-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>,
	Andrew Morton
	<akpm-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org>,
	Al Viro <viro-RmSDqhL/yNMiFSDQTTA3OLVCufUGDwFn@public.gmane.org>
Subject: Re: [RFC][PATCH] ipc: Remove IPCMNI
Date: Thu, 29 Mar 2018 13:52:25 -0500	[thread overview]
Message-ID: <87lgea7lzq.fsf__5416.98908568851$1522349513$gmane$org@xmission.com> (raw)
In-Reply-To: <05772f83-d680-aea1-b222-cef2430dcc83-nhLOkwUX5cPe2c5cEj3t2g@public.gmane.org> (Manfred Spraul's message of "Thu, 29 Mar 2018 20:07:44 +0200")

Manfred Spraul <manfred-nhLOkwUX5cPe2c5cEj3t2g@public.gmane.org> writes:

> Hello Mathew,
>
> On 03/29/2018 12:56 PM, Matthew Wilcox wrote:
>> On Thu, Mar 29, 2018 at 10:47:45AM +0200, Manfred Spraul wrote:
>>>>>>>> This can be implemented trivially with the current code
>>>>>>>> using idr_alloc_cyclic.
>>> Is there a performance impact?
>>> Right now, the idr tree is only large if there are lots of objects.
>>> What happens if we have only 1 object, with id=INT_MAX-1?
>> The radix tree uses a branching factor of 64 entries (6 bits) per level.
>> The maximum ID is 31 bits (positive signed 32-bit integer).  So the
>> worst case for a single object is 6 pointer dereferences to find the
>> object anywhere in the range (INT_MAX/2 - INT_MAX].  That will read 12
>> cachelines.  If we were to constrain ourselves to a maximum of INT_MAX/2
>> (30 bits), we'd reduce that to 5 pointer dereferences and 10 cachelines.
> I'm concerned about the up to 6 branches.
> But this is just guessing, we need a test with a realistic workload.

Yes.

My primary purpose with the patch was to show that the issues with the
current limits could be resolved in a straght forward manner.  I really
don't know if idrs are the appropriate data structure.  It is possible
rbtrees are a better fit.


I think my algorithm I proposed for generating identifiers is as likely
as any to be a good one.  It does need testing on a wide variety of
applications to see what applications actually care about and for that I
think my proposed patch is more than sufficient.

By not keeping a generation counters in the slots themselves linux
already differs substantially from traditional implementations.

Doing something to free us from using a fixed number of bits for the
counter and a fixed number of bits to encode the slot we can support
much larger use of this API.

Eric

  parent reply	other threads:[~2018-03-29 18:52 UTC|newest]

Thread overview: 54+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-03-12 20:15 [PATCH v4 0/6] ipc: Clamp *mni to the real IPCMNI limit Waiman Long
2018-03-12 20:15 ` [PATCH v4 1/6] sysctl: Add flags to support min/max range clamping Waiman Long
2018-03-12 20:44   ` Luis R. Rodriguez
2018-03-12 20:48     ` Waiman Long
2018-03-13 17:46   ` Eric W. Biederman
2018-03-13 18:49     ` Waiman Long
2018-03-12 20:15 ` [PATCH v4 2/6] proc/sysctl: Check for invalid flags bits Waiman Long
2018-03-12 20:46   ` Luis R. Rodriguez
2018-03-12 20:54     ` Waiman Long
2018-03-12 20:59       ` Luis R. Rodriguez
2018-03-12 21:02         ` Waiman Long
2018-03-12 20:52   ` Andrew Morton
2018-03-12 22:12     ` Waiman Long
2018-03-12 22:42       ` Andrew Morton
2018-03-12 20:15 ` [PATCH v4 3/6] sysctl: Warn when a clamped sysctl parameter is set out of range Waiman Long
2018-03-12 20:50   ` Luis R. Rodriguez
2018-03-12 21:07     ` Waiman Long
2018-03-12 21:00   ` Andrew Morton
2018-03-12 21:04     ` Waiman Long
2018-03-12 20:15 ` [PATCH v4 4/6] ipc: Clamp msgmni and shmmni to the real IPCMNI limit Waiman Long
2018-03-13 18:17   ` Eric W. Biederman
2018-03-13 18:39     ` Waiman Long
2018-03-13 20:29       ` Eric W. Biederman
2018-03-13 21:06         ` Waiman Long
     [not found]           ` <935a7c50-50cc-2dc0-33bb-92c000d039bc-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
2018-03-15  0:49             ` [RFC][PATCH] ipc: Remove IPCMNI Eric W. Biederman
2018-03-15  0:49               ` Eric W. Biederman
     [not found]               ` <87woyego2u.fsf_-_-aS9lmoZGLiVWk0Htik3J/w@public.gmane.org>
2018-03-15 17:02                 ` Waiman Long
2018-03-15 19:45                 ` Matthew Wilcox
2018-03-15 17:02               ` Waiman Long
     [not found]                 ` <047c6ed6-6581-b543-ba3d-cadc543d3d25-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
2018-03-15 19:00                   ` Eric W. Biederman
2018-03-15 19:00                     ` Eric W. Biederman
     [not found]                     ` <87h8ph6u67.fsf-aS9lmoZGLiVWk0Htik3J/w@public.gmane.org>
2018-03-15 21:46                       ` Waiman Long
2018-03-15 21:46                         ` Waiman Long
     [not found]                         ` <7d3a1f93-f8e5-5325-f9a7-0079f7777b6f-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
2018-03-29  2:14                           ` Davidlohr Bueso
2018-03-29  2:14                             ` Davidlohr Bueso
2018-03-29  8:47                             ` Manfred Spraul
2018-03-29  8:47                             ` Manfred Spraul
     [not found]                               ` <3e201de2-bed2-6f7d-0783-700d095142e0-nhLOkwUX5cPe2c5cEj3t2g@public.gmane.org>
2018-03-29 10:56                                 ` Matthew Wilcox
2018-03-29 20:08                                 ` Eric W. Biederman
2018-03-29 10:56                               ` Matthew Wilcox
     [not found]                                 ` <20180329105601.GA597-PfSpb0PWhxZc2C7mugBRk2EX/6BAtgUQ@public.gmane.org>
2018-03-29 18:07                                   ` Manfred Spraul
2018-03-29 18:07                                     ` Manfred Spraul
2018-03-29 18:52                                     ` Eric W. Biederman
2018-03-29 19:32                                     ` Matthew Wilcox
     [not found]                                     ` <05772f83-d680-aea1-b222-cef2430dcc83-nhLOkwUX5cPe2c5cEj3t2g@public.gmane.org>
2018-03-29 18:52                                       ` Eric W. Biederman [this message]
2018-03-29 19:32                                       ` Matthew Wilcox
2018-03-29 20:08                               ` Eric W. Biederman
2018-03-15 19:45               ` Matthew Wilcox
2018-03-12 20:15 ` [PATCH v4 5/6] ipc: Clamp semmni to the real IPCMNI limit Waiman Long
2018-03-12 20:52   ` Luis R. Rodriguez
2018-03-12 20:59     ` Waiman Long
2018-03-12 20:15 ` [PATCH v4 6/6] test_sysctl: Add range clamping test Waiman Long
2018-03-12 20:53   ` Luis R. Rodriguez
2018-03-12 21:00     ` Waiman Long

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='87lgea7lzq.fsf__5416.98908568851$1522349513$gmane$org@xmission.com' \
    --to=ebiederm-as9lmozglivwk0htik3j/w@public.gmane.org \
    --cc=akpm-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org \
    --cc=containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org \
    --cc=dave-h16yJtLeMjHk1uMJSBkQmQ@public.gmane.org \
    --cc=keescook-F7+t8E8rja9g9hUCZPvPmw@public.gmane.org \
    --cc=linux-api-u79uwXL29TY76Z2rM5mHXA@public.gmane.org \
    --cc=linux-fsdevel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org \
    --cc=linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org \
    --cc=longman-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org \
    --cc=manfred-nhLOkwUX5cPe2c5cEj3t2g@public.gmane.org \
    --cc=mcgrof-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org \
    --cc=mtk.manpages-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org \
    --cc=skinsbursky-bzQdu9zFT3WakBO8gow8eQ@public.gmane.org \
    --cc=viro-RmSDqhL/yNMiFSDQTTA3OLVCufUGDwFn@public.gmane.org \
    --cc=willy-wEGCiKHe2LqWVfeAwA7xHQ@public.gmane.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.