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

[Manfred Spraul <manfred@colorfullife.com>]

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@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 fromwilly@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<manfred@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