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<manfred@xxxxxxxxxxxxxxxx>
> > 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 fromwilly@xxxxxxxxxxxxx:
> >
> > (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<manfred@xxxxxxxxxxxxxxxx>
> > ---
> >   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