Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Subject: Re: [RFC, PATCH] ipc/util.c: use idr_alloc_cyclic() for ipc
 allocations
To:     Waiman Long <longman@redhat.com>,
        LKML <linux-kernel@vger.kernel.org>,
        Davidlohr Bueso <dave@stgolabs.net>
Cc:     1vier1@web.de, Andrew Morton <akpm@linux-foundation.org>,
        Kees Cook <keescook@chromium.org>,
        "Luis R . Rodriguez" <mcgrof@kernel.org>,
        Matthew Wilcox <willy@infradead.org>
References: <20181002161942.1037-1-manfred@colorfullife.com>
 <1b8bcd5c-1264-08da-0b91-ebb4c02f6035@redhat.com>
From:   Manfred Spraul <manfred@colorfullife.com>
Message-ID: <268a5f08-c2d7-aeba-80f6-70daa093c548@colorfullife.com>
Date:   Wed, 3 Oct 2018 13:37:07 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.0
MIME-Version: 1.0
In-Reply-To: <1b8bcd5c-1264-08da-0b91-ebb4c02f6035@redhat.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Content-Language: en-US
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On 10/2/18 8:27 PM, Waiman Long wrote:
> On 10/02/2018 12:19 PM, Manfred Spraul wrote:
>> A bit related to the patch series that increases IPC_MNI:
>>
>> (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, switch from
>> idr_alloc to idr_alloc_cyclic.
>>
>> 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.
>>
>> As an option, this could be made dependent on the extended
>> mode: In extended mode, cycle over e.g. at least 16k ids.
>>
>> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
>> ---
>>
>> Open questions:
>> - Is there a significant performance advantage, especially
>>    there are many ipc ids?
>> - Over how many ids should the code cycle always?
>> - Further review remarks?
>>
>>   ipc/util.c | 22 +++++++++++++++++++++-
>>   1 file changed, 21 insertions(+), 1 deletion(-)
>>
>> diff --git a/ipc/util.c b/ipc/util.c
>> index 0af05752969f..6f83841f6761 100644
>> --- a/ipc/util.c
>> +++ b/ipc/util.c
>> @@ -216,10 +216,30 @@ 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 */
>> +		int idr_max;
>> +
>>   		new->seq = ids->seq++;
>>   		if (ids->seq > IPCID_SEQ_MAX)
>>   			ids->seq = 0;
>> -		idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT);
>> +
>> +		/*
>> +		 * If a user space visible id is reused, then this creates a
>> +		 * risk for data corruption. To reduce the probability that
>> +		 * a number is reduced, two approaches are used:
>    reduced -> reused?
Of course.
>
>> +		 * 1) the idr index is allocated cyclically.
>> +		 * 2) the use space id is build by concatenating the
>> +		 *    internal idr index with a sequence number
>> +		 * To avoid that both numbers have the same cycle time, try
>> +		 * to set the size for the cyclic alloc to an odd number.
>> +		 */
>> +		idr_max = ids->in_use*2+1;
>> +		if (idr_max < RADIX_TREE_MAP_SIZE-1)
>> +			idr_max = RADIX_TREE_MAP_SIZE-1;
>> +		if (idr_max > IPCMNI)
>> +			idr_max = IPCMNI;
>> +
>> +		idx = idr_alloc_cyclic(&ids->ipcs_idr, new, 0, idr_max,
>> +					GFP_NOWAIT);
>>   	} else {
>>   		new->seq = ipcid_to_seqx(next_id);
>>   		idx = idr_alloc(&ids->ipcs_idr, new, ipcid_to_idx(next_id),
>
> Each of IPC components have their own sysctl parameters limiting the max
> number of objects that can be allocated. With cyclic allocation, you
> will have to make sure that idr_max is not larger than the corresponding
> IPC sysctl parameters. That may require moving the limits to the
> corresponding ipc_ids structure so that it can be used in ipc_idr_alloc().

First, I would disagree:

the sysctl limits specify how many objects can exist.

idr_max is the maximum index in the radix tree that can exist. There is 
a hard limit of IPCMNI, but that's it.


But:

The name is wrong, I will rename the variable to idx_max

> What is the point of comparing idr_max against RADIX_TREE_MAP_SIZE-1? Is
> it for performance reason.

Let's assume you have only 1 ipc object, and you alloc/release that object.

At alloc time, ids->in_use is 0 -> idr_max 1 -> every object will end up 
with idx=0.

This would defeat the whole purpose of using a cyclic alloc.

Thus: cycle over at least 63 ids -> 5 additional bits to avoid collisions.


--

     Manfred