Re: [RFC][PATCH] ipc: Remove IPCMNI

all subsystems

Cc'ing mtk, Manfred and linux-api.

See below.

On Thu, 15 Mar 2018, Waiman Long wrote:

On 03/15/2018 03:00 PM, Eric W. Biederman wrote:
Waiman Long [off-list ref] writes:

On 03/14/2018 08:49 PM, Eric W. Biederman wrote:
The define IPCMNI was originally the size of a statically sized array in
the kernel and that has long since been removed.  Therefore there is no
fundamental reason for IPCMNI.

The only remaining use IPCMNI serves is as a convoluted way to format
the ipc id to userspace.  It does not appear that anything except for
the CHECKPOINT_RESTORE code even cares about this variety of assignment
and the CHECKPOINT_RESTORE code only cares about this weirdness because
it has to restore these peculiar ids.

Therefore make the assignment of ipc ids match the description in
Advanced Programming in the Unix Environment and assign the next id
until INT_MAX is hit then loop around to the lower ids.

This can be implemented trivially with the current code using idr_alloc_cyclic.

To make it possible to keep checkpoint/restore working I have renamed
the sysctls from xxx_next_id to xxx_nextid.  That is enough change that
a smart CRIU implementation can see that what is exported has changed,
and act accordingly.  New kernels will be able to restore the old id's.

This code still needs some real world testing to verify my assumptions.
And some work with the CRIU implementations to actually add the code
that deals with the new for of id assignment.

Updates: 03f595668017 ("ipc: add sysctl to specify desired next object id")
Signed-off-by: "Eric W. Biederman" <redacted>
---

Waiman please take a look at this and run it through some tests etc,
I am pretty certain something like this patch is all you need to do
to sort out ipc assignment.  Not messing with sysctls needed.

 include/linux/ipc.h           |  2 --
 include/linux/ipc_namespace.h |  1 -
 ipc/ipc_sysctl.c              |  6 ++--
I share these fears.

Thanks,
Davidlohr

My original thinking was to have an extended mode where the IPCMNI
becomes 8M from 32k. That will reduce the sequence number from 16 bits
to 8 bits. The extended mode is enabled by adding, for example, a boot
option. So this will be an opt-in feature instead of as a default.

Which comes down to the fundamental question what depends upon what.
How do other operating systems like Solaris handle this?
I don't know how Solaris handle this, but I know they support up to 2^24
shm segments.

Does any nix flavor support more that 16bits worth of shm segments?

The API has been deprecated for the last 20 years and we are still
keeping it alive.  Sigh.

Still there is fundamentally only one thing the kernel can do if we wish
to increase the number of shm segments.

Please take my patch and test it out and see if you can find anything
that cares about the change. Except for needing id reuse to be
infrequent I can not imagine that there is anything that cares.

It could very reasonably be argued that my when shmmni is < INT_MAX
my patch implements a version of the existing algorithm.  As we go
through all of the possible ids before we reuse any of them.

Eric
Thanks for the patch, I am still thinking about what is the best way to
handle this.

Cheers,
Longman

Hello together,

On 03/29/2018 04:14 AM, Davidlohr Bueso wrote:
Cc'ing mtk, Manfred and linux-api.

See below.

On Thu, 15 Mar 2018, Waiman Long wrote:

On 03/15/2018 03:00 PM, Eric W. Biederman wrote:
Waiman Long [off-list ref] writes:

On 03/14/2018 08:49 PM, Eric W. Biederman wrote:
The define IPCMNI was originally the size of a statically sized array in
the kernel and that has long since been removed. Therefore there is no
fundamental reason for IPCMNI.

The only remaining use IPCMNI serves is as a convoluted way to format
the ipc id to userspace.  It does not appear that anything except for
the CHECKPOINT_RESTORE code even cares about this variety of assignment
and the CHECKPOINT_RESTORE code only cares about this weirdness because
it has to restore these peculiar ids.
My assumption is that if an array is recreated, it should get a different id.
    a=semget(1234,,);
    semctl(a,,IPC_RMID);
    b=semget(1234,,);
now a!=b.

Rational: semop() calls only refer to the array by the id.
If there is a stale process in the system that tries to access the "old" array and the new array has the same id, then the locking gets corrupted.
Therefore make the assignment of ipc ids match the description in
Advanced Programming in the Unix Environment and assign the next id
until INT_MAX is hit then loop around to the lower ids.
Ok, sounds good.
That way we really cycle through INT_MAX, right now a==b would happen after 128k RMID calls.
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?

semop() that do not sleep are fairly fast.
The same applies for msgsnd/msgrcv, if the message is small enough.

@Davidlohr:
Do you know if there are application that frequently call semop() and it doesn't have to sleep?
From the scalability that was pushed into the kernel, I assume that this exists.

I have myself only checked postgresql, and postgresql always sleeps.
(and this was long ago)
To make it possible to keep checkpoint/restore working I have renamed
the sysctls from xxx_next_id to xxx_nextid.  That is enough change that
a smart CRIU implementation can see that what is exported has changed,
and act accordingly.  New kernels will be able to restore the old id's.

This code still needs some real world testing to verify my assumptions.
And some work with the CRIU implementations to actually add the code
that deals with the new for of id assignment.
It means that all existing checkpoint/restore application will not work with a new kernel.
Everyone must first update the checkpoint/restore application, then update the kernel.

Is this acceptable?

--
    Manfred
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 have plans to make the representation more efficient and bring
the specific case of one element with a high ID down to one pointer
dereference and 2 cachelines, but I have not yet had time to implement
those plans.

From a memory consumption point of view, 6 layers of tree will consume
6/7 of a page on a 64-bit x86 kernel.  I'm aiming to bring that down to
1/7 of a page.  We get 7 radix_tree_nodes per 4kB page.

(The old IDR tree had 256 entries per level which would have taken only
four layers to get us to 31 bits, but the cost was getting only 3 layers
per 8kB order-1 page, so we'd've taken 2 + 2/3 page to accomplish the
same goal).
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.

--
    Manfred
_______________________________________________
Containers mailing list
Containers@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/containers
On Thu, Mar 29, 2018 at 08:07:44PM +0200, Manfred Spraul wrote:
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, and once there's a realistic workload, I'll be happy to prioritise
adapting the data structure to reduce the pointer chases.

FWIW, the plan is this:

There's currently an unused 32-bit field (on 64-bit machines) which I plan
to make the 'base' field.  So at each step down the tree, one subtracts
that field from the index in order to decide which slot to look at next.
Something like this:

index=0x3000'0000
(root) -> order=24
          offset=48 -> order=18
                       offset=0 -> order=12
                                   offset=0 -> order=6
                                               offset=0 -> order=0
                                                           offset=0 -> data

compresses to a single node:
(root) -> order=0
          base=3000'0000
          offset=0 -> data

If one has one entry at 5 and another entry at 0x3000'0000, the tree
looks like this (three nodes):

(root) -> order=24
          base=0
          offset=0  -> order=0
                       base=0
                       offset=5 -> entry1
          offset=48 -> order=0
                       base=0
                       offset=0 -> entry2

The trick is making sure that looking up offset 0x300'1000 returns NULL
and not entry2, but I can make that work.

An alternative is to go to something a little more libJudy and have

`h`	back out one level
`j`	next message in thread / next series-diff position
`k`	previous message in thread / previous series-diff position
`l`	drill in
`Esc`	close help / fold thread tree
`?`	toggle this help