Re: [PATCH v11 2/3] ipc: Conserve sequence numbers in ipcmni_extend mode

[Manfred Spraul]

On 2/27/19 9:30 PM, Waiman Long wrote:
On 11/20/2018 02:41 PM, Manfred Spraul wrote:
 From 6bbade73d21884258a995698f21ad3128df8e98a Mon Sep 17 00:00:00 2001
From: Manfred Spraul<manf...@colorfullife.com>
Date: Sat, 29 Sep 2018 15:43:28 +0200
Subject: [PATCH 2/2] ipc/util.c: use idr_alloc_cyclic() for ipc allocations
A bit related to the patch that increases IPC_MNI, and
partially based on the mail fromwi...@infradead.org:

(User space) id reuse create the risk of data corruption:

Process A: calls ipc function
Process A: sleeps just at the beginning of the syscall
Process B: Frees the ipc object (i.e.: calls ...ctl(IPC_RMID)
Process B: Creates a new ipc object (i.e.: calls ...get())
        <If new object and old object have the same id>
Process A: is woken up, and accesses the new object

To reduce the probability that the new and the old object have the
same id, the current implementation adds a sequence number to the
index of the object in the idr tree.

To further reduce the probability for a reuse, perform a cyclic
allocation, and increase the sequence number only when there is
a wrap-around. Unfortunately, idr_alloc_cyclic cannot be used,
because the sequence number must be increased when a wrap-around
occurs.

The patch cycles over at least RADIX_TREE_MAP_SIZE, i.e.
if there is only a small number of objects, the accesses
continue to be direct.

Signed-off-by: Manfred Spraul<manf...@colorfullife.com>
---
  ipc/util.c | 48 ++++++++++++++++++++++++++++++++++++++++++++----
  1 file changed, 44 insertions(+), 4 deletions(-)

diff --git a/ipc/util.c b/ipc/util.c
index 07ae117ccdc0..fa7b8fa7a14c 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -216,10 +216,49 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids, 
struct kern_ipc_perm *new)
         */
  
  	if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */
-               new->seq = ids->seq++;
-               if (ids->seq > IPCID_SEQ_MAX)
-                       ids->seq = 0;
-               idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT);
+               int idx_max;
+
+               /*
+                * If a user space visible id is reused, then this creates a
+                * risk for data corruption. To reduce the probability that
+                * a number is reused, three approaches are used:
+                * 1) the idr index is allocated cyclically.
+                * 2) the use space id is build by concatenating the
+                *    internal idr index with a sequence number.
+                * 3) The sequence number is only increased when the index
+                *    wraps around.
+                * Note that this code cannot use idr_alloc_cyclic:
+                * new->seq must be set before the entry is inserted in the
+                * idr.

I don't think that is true. The IDR code just need to associate a 
pointer to the given ID. It is not going to access anything inside. So 
we don't need to set the seq number first before calling idr_alloc().

We must, sorry - there is even a CVE associate to that bug:

CVE-2015-7613, 
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=b9a532277938798b53178d5a66af6e2915cb27cf

The problem is not the IDR code, the problem is that 
ipc_obtain_object_check() calls ipc_checkid(), and ipc_checkid() 
accesses ipcp->seq.

And since the ipc_checkid() is called before acquiring any locks, 
everything must be fully initialized before idr_alloc().

+                */
+               idx_max = ids->in_use*2;
+               if (idx_max < RADIX_TREE_MAP_SIZE)
+                       idx_max = RADIX_TREE_MAP_SIZE;
+               if (idx_max > ipc_mni)
+                       idx_max = ipc_mni;
+
+               if (ids->ipcs_idr.idr_next <= idx_max) {
+                       new->seq = ids->seq;
+                       idx = idr_alloc(&ids->ipcs_idr, new,
+                                               ids->ipcs_idr.idr_next,
+                                               idx_max, GFP_NOWAIT);
+               }
+
+               if ((idx == -ENOSPC) && (ids->ipcs_idr.idr_next > 0)) {
+                       /*
+                        * A wrap around occurred.
+                        * Increase ids->seq, update new->seq
+                        */
+                       ids->seq++;
+                       if (ids->seq > IPCID_SEQ_MAX)
+                               ids->seq = 0;
+                       new->seq = ids->seq;
+
+                       idx = idr_alloc(&ids->ipcs_idr, new, 0, idx_max,
+                                               GFP_NOWAIT);
+               }
+               if (idx >= 0)
+                       ids->ipcs_idr.idr_next = idx+1;

This code has dependence on the internal implementation of the IDR 
code. So if the IDR code is changed and the one who does it forgets to 
update the IPC code, we may have a problem. Using idr_alloc_cyclic() 
for all will likely increase memory footprint which can be a problem 
on IoT devices that have little memory. That is the main reason why I 
opted to use idr_alloc_cyclic() only when in ipcmni_extend mode which 
I am sure won't be activated on systems with little memory.

I know.

But IoT devices with little memory will compile out sysv (as it is done 
by Android).


--

    Manfred