lkml.org 
[lkml]   [2019]   [Mar]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH v11 2/3] ipc: Conserve sequence numbers in ipcmni_extend mode
From
Date
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

\
 
 \ /
  Last update: 2019-03-10 13:48    [W:0.067 / U:0.676 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site