using range locks instead of mm_sem

using range locks instead of mm_sem

[Shady Issa]

Hi Davidlohr,

I am interested in the idea of using range locks to replace mm_sem. I 
wanted to
start trying out using more fine-grained ranges instead of the full 
range acquisitions
that are used in this patch (https://lkml.org/lkml/2018/2/4/235). 
However, it does not
seem straight forward to me how this is possible.

First, the ranges that can be defined before acquiring the range lock 
based on the
caller's input(i.e. ranges supplied by mprotect, mmap, munmap, etc.) are 
oblivious of
the underlying VMAs. Two non-overlapping ranges can fall within the same 
VMA and
thus should not be allowed to run concurrently in case they are writes.

Second, even if ranges from the caller function are aligned with VMAs, 
the extent of the
effect of operation is unknown. It is probable that an operation 
touching one VMA will
end up performing modifications to the VMAs rbtree structure due to 
splits, merges, etc.,
which requires the full range acquisition and is unknown beforehand.

I was wondering if I am missing something with this thought process, 
because with the
current givings, it seems to me that range locks will boil down to just 
r/w semaphore.
I would also be very grateful if you can point me to any more recent 
discussions regarding
the use of range locks after this patch from February.

Best regards
Shady Issa

Re: using range locks instead of mm_sem

[Davidlohr Bueso]

On Wed, 22 Aug 2018, Shady Issa wrote:

>
>Hi Davidlohr,
>
>I am interested in the idea of using range locks to replace mm_sem. I 
>wanted to
>start trying out using more fine-grained ranges instead of the full 
>range acquisitions
>that are used in this patch (https://lkml.org/lkml/2018/2/4/235). 
>However, it does not
>seem straight forward to me how this is possible.
>
>First, the ranges that can be defined before acquiring the range lock 
>based on the
>caller's input(i.e. ranges supplied by mprotect, mmap, munmap, etc.) 
>are oblivious of
>the underlying VMAs. Two non-overlapping ranges can fall within the 
>same VMA and
>thus should not be allowed to run concurrently in case they are writes.

Yes. This is a _big_ issue with range locking the addr space. I have yet
to find a solution other than delaying vma modifying ops to avoid the races,
which is fragile. Obviously locking the full range in such scenarios cannot
be done either.

>
>Second, even if ranges from the caller function are aligned with VMAs, 
>the extent of the
>effect of operation is unknown. It is probable that an operation 
>touching one VMA will
>end up performing modifications to the VMAs rbtree structure due to 
>splits, merges, etc.,
>which requires the full range acquisition and is unknown beforehand.

Yes, this is similar to the above as well.

>
>I was wondering if I am missing something with this thought process, 
>because with the
>current givings, it seems to me that range locks will boil down to 
>just r/w semaphore.
>I would also be very grateful if you can point me to any more recent 
>discussions regarding
>the use of range locks after this patch from February.

You're on the right page.

Thanks,
Davidlohr

Re: using range locks instead of mm_sem

[Laurent Dufour]

On 22/08/2018 16:46, Davidlohr Bueso wrote:
> On Wed, 22 Aug 2018, Shady Issa wrote:
> 
>>
>> Hi Davidlohr,
>>
>> I am interested in the idea of using range locks to replace mm_sem. I wanted to
>> start trying out using more fine-grained ranges instead of the full range
>> acquisitions
>> that are used in this patch (https://lkml.org/lkml/2018/2/4/235). However, it
>> does not
>> seem straight forward to me how this is possible.
>>
>> First, the ranges that can be defined before acquiring the range lock based
>> on the
>> caller's input(i.e. ranges supplied by mprotect, mmap, munmap, etc.) are
>> oblivious of
>> the underlying VMAs. Two non-overlapping ranges can fall within the same VMA and
>> thus should not be allowed to run concurrently in case they are writes.
> 
> Yes. This is a _big_ issue with range locking the addr space. I have yet
> to find a solution other than delaying vma modifying ops to avoid the races,
> which is fragile. Obviously locking the full range in such scenarios cannot
> be done either.

I think the range locked should be aligned to the underlying VMA plus one page
on each side to prevent that VMA to be merged.
But this raises a concern with the VMA merging mechanism which tends to limit
the number of VMAs and could lead to a unique VMA, limiting the advantage of a
locking based on the VMA's boundaries.

>>
>> Second, even if ranges from the caller function are aligned with VMAs, the
>> extent of the
>> effect of operation is unknown. It is probable that an operation touching one
>> VMA will
>> end up performing modifications to the VMAs rbtree structure due to splits,
>> merges, etc.,
>> which requires the full range acquisition and is unknown beforehand.
> 
> Yes, this is similar to the above as well.
> 
>>
>> I was wondering if I am missing something with this thought process, because
>> with the
>> current givings, it seems to me that range locks will boil down to just r/w
>> semaphore.
>> I would also be very grateful if you can point me to any more recent
>> discussions regarding
>> the use of range locks after this patch from February.
> 
> You're on the right page.
> 
> Thanks,
> Davidlohr
> 

Re: using range locks instead of mm_sem

[Shady Issa]

On 08/24/2018 03:40 AM, Laurent Dufour wrote:
> On 22/08/2018 16:46, Davidlohr Bueso wrote:
>> On Wed, 22 Aug 2018, Shady Issa wrote:
>>
>>> Hi Davidlohr,
>>>
>>> I am interested in the idea of using range locks to replace mm_sem. I wanted to
>>> start trying out using more fine-grained ranges instead of the full range
>>> acquisitions
>>> that are used in this patch (https://urldefense.proofpoint.com/v2/url?u=https-3A__lkml.org_lkml_2018_2_4_235&d=DwICaQ&c=RoP1YumCXCgaWHvlZYR8PZh8Bv7qIrMUB65eapI_JnE&r=Q-zBmi7tP5HosTvB8kUZjTYqSFMRtxg-kOQa59-zx9I&m=ZCN6CnHZsYyZ_V0nWMSZgLmp-GobwtrhI3Wx8UAIQuY&s=LtbMxuR2njAX0dm3L2lNQKvztbnLTfKjBd-S20cDPbE&e=). However, it
>>> does not
>>> seem straight forward to me how this is possible.
>>>
>>> First, the ranges that can be defined before acquiring the range lock based
>>> on the
>>> caller's input(i.e. ranges supplied by mprotect, mmap, munmap, etc.) are
>>> oblivious of
>>> the underlying VMAs. Two non-overlapping ranges can fall within the same VMA and
>>> thus should not be allowed to run concurrently in case they are writes.
>> Yes. This is a _big_ issue with range locking the addr space. I have yet
>> to find a solution other than delaying vma modifying ops to avoid the races,
>> which is fragile. Obviously locking the full range in such scenarios cannot
>> be done either.
> I think the range locked should be aligned to the underlying VMA plus one page
> on each side to prevent that VMA to be merged.
> But this raises a concern with the VMA merging mechanism which tends to limit
> the number of VMAs and could lead to a unique VMA, limiting the advantage of a
> locking based on the VMA's boundaries.
To do so, the current merge implementation should be changed so that
it does not access VMAs beyond the locked range, right? Also, this will
not stop a merge from happening in case of a range spanning two VMAs
for example.
>
>>> Second, even if ranges from the caller function are aligned with VMAs, the
>>> extent of the
>>> effect of operation is unknown. It is probable that an operation touching one
>>> VMA will
>>> end up performing modifications to the VMAs rbtree structure due to splits,
>>> merges, etc.,
>>> which requires the full range acquisition and is unknown beforehand.
>> Yes, this is similar to the above as well.
>>
>>> I was wondering if I am missing something with this thought process, because
>>> with the
>>> current givings, it seems to me that range locks will boil down to just r/w
>>> semaphore.
>>> I would also be very grateful if you can point me to any more recent
>>> discussions regarding
>>> the use of range locks after this patch from February.
>> You're on the right page.
>>
>> Thanks,
>> Davidlohr
>>

Re: using range locks instead of mm_sem

[Alex Kogan]

> On Aug 24, 2018, at 6:39 PM, Shady Issa <shady.issa@oracle.com> wrote:
> 
> 
> 
> On 08/24/2018 03:40 AM, Laurent Dufour wrote:
>> On 22/08/2018 16:46, Davidlohr Bueso wrote:
>>> On Wed, 22 Aug 2018, Shady Issa wrote:
>>> 
>>>> Hi Davidlohr,
>>>> 
>>>> I am interested in the idea of using range locks to replace mm_sem. I wanted to
>>>> start trying out using more fine-grained ranges instead of the full range
>>>> acquisitions
>>>> that are used in this patch (https://urldefense.proofpoint.com/v2/url?u=https-3A__lkml.org_lkml_2018_2_4_235&d=DwICaQ&c=RoP1YumCXCgaWHvlZYR8PZh8Bv7qIrMUB65eapI_JnE&r=Q-zBmi7tP5HosTvB8kUZjTYqSFMRtxg-kOQa59-zx9I&m=ZCN6CnHZsYyZ_V0nWMSZgLmp-GobwtrhI3Wx8UAIQuY&s=LtbMxuR2njAX0dm3L2lNQKvztbnLTfKjBd-S20cDPbE&e=). However, it
>>>> does not
>>>> seem straight forward to me how this is possible.
>>>> 
>>>> First, the ranges that can be defined before acquiring the range lock based
>>>> on the
>>>> caller's input(i.e. ranges supplied by mprotect, mmap, munmap, etc.) are
>>>> oblivious of
>>>> the underlying VMAs. Two non-overlapping ranges can fall within the same VMA and
>>>> thus should not be allowed to run concurrently in case they are writes.
>>> Yes. This is a _big_ issue with range locking the addr space. I have yet
>>> to find a solution other than delaying vma modifying ops to avoid the races,
>>> which is fragile. Obviously locking the full range in such scenarios cannot
>>> be done either.
>> I think the range locked should be aligned to the underlying VMA plus one page
>> on each side to prevent that VMA to be merged.
How would one find the underlying VMA for the range lock acquisition?
Looks like that would require searching the rb-tree (currently protected by mm_sem), and that search has to be synchronized with concurrent tree modifications.

Regards,
— Alex

>> But this raises a concern with the VMA merging mechanism which tends to limit
>> the number of VMAs and could lead to a unique VMA, limiting the advantage of a
>> locking based on the VMA's boundaries.
> To do so, the current merge implementation should be changed so that
> it does not access VMAs beyond the locked range, right? Also, this will
> not stop a merge from happening in case of a range spanning two VMAs
> for example.
>> 
>>>> Second, even if ranges from the caller function are aligned with VMAs, the
>>>> extent of the
>>>> effect of operation is unknown. It is probable that an operation touching one
>>>> VMA will
>>>> end up performing modifications to the VMAs rbtree structure due to splits,
>>>> merges, etc.,
>>>> which requires the full range acquisition and is unknown beforehand.
>>> Yes, this is similar to the above as well.
>>> 
>>>> I was wondering if I am missing something with this thought process, because
>>>> with the
>>>> current givings, it seems to me that range locks will boil down to just r/w
>>>> semaphore.
>>>> I would also be very grateful if you can point me to any more recent
>>>> discussions regarding
>>>> the use of range locks after this patch from February.
>>> You're on the right page.
>>> 
>>> Thanks,
>>> Davidlohr
>>> 
> 

Re: using range locks instead of mm_sem

[Laurent Dufour]

On 27/08/2018 21:41, Alex Kogan wrote:
> 
>> On Aug 24, 2018, at 6:39 PM, Shady Issa <shady.issa@oracle.com> wrote:
>>
>>
>>
>> On 08/24/2018 03:40 AM, Laurent Dufour wrote:
>>> On 22/08/2018 16:46, Davidlohr Bueso wrote:
>>>> On Wed, 22 Aug 2018, Shady Issa wrote:
>>>>
>>>>> Hi Davidlohr,
>>>>>
>>>>> I am interested in the idea of using range locks to replace mm_sem. I wanted to
>>>>> start trying out using more fine-grained ranges instead of the full range
>>>>> acquisitions
>>>>> that are used in this patch (https://urldefense.proofpoint.com/v2/url?u=https-3A__lkml.org_lkml_2018_2_4_235&d=DwICaQ&c=RoP1YumCXCgaWHvlZYR8PZh8Bv7qIrMUB65eapI_JnE&r=Q-zBmi7tP5HosTvB8kUZjTYqSFMRtxg-kOQa59-zx9I&m=ZCN6CnHZsYyZ_V0nWMSZgLmp-GobwtrhI3Wx8UAIQuY&s=LtbMxuR2njAX0dm3L2lNQKvztbnLTfKjBd-S20cDPbE&e=). However, it
>>>>> does not
>>>>> seem straight forward to me how this is possible.
>>>>>
>>>>> First, the ranges that can be defined before acquiring the range lock based
>>>>> on the
>>>>> caller's input(i.e. ranges supplied by mprotect, mmap, munmap, etc.) are
>>>>> oblivious of
>>>>> the underlying VMAs. Two non-overlapping ranges can fall within the same VMA and
>>>>> thus should not be allowed to run concurrently in case they are writes.
>>>> Yes. This is a _big_ issue with range locking the addr space. I have yet
>>>> to find a solution other than delaying vma modifying ops to avoid the races,
>>>> which is fragile. Obviously locking the full range in such scenarios cannot
>>>> be done either.
>>> I think the range locked should be aligned to the underlying VMA plus one page
>>> on each side to prevent that VMA to be merged.
> How would one find the underlying VMA for the range lock acquisition?
> Looks like that would require searching the rb-tree (currently protected by mm_sem), and that search has to be synchronized with concurrent tree modifications.

The rb-tree will need its own protection through a lock or a RCU like mechanism.

Laurent.



> Regards,
> a?? Alex
> 
>>> But this raises a concern with the VMA merging mechanism which tends to limit
>>> the number of VMAs and could lead to a unique VMA, limiting the advantage of a
>>> locking based on the VMA's boundaries.
>> To do so, the current merge implementation should be changed so that
>> it does not access VMAs beyond the locked range, right? Also, this will
>> not stop a merge from happening in case of a range spanning two VMAs
>> for example.
>>>
>>>>> Second, even if ranges from the caller function are aligned with VMAs, the
>>>>> extent of the
>>>>> effect of operation is unknown. It is probable that an operation touching one
>>>>> VMA will
>>>>> end up performing modifications to the VMAs rbtree structure due to splits,
>>>>> merges, etc.,
>>>>> which requires the full range acquisition and is unknown beforehand.
>>>> Yes, this is similar to the above as well.
>>>>
>>>>> I was wondering if I am missing something with this thought process, because
>>>>> with the
>>>>> current givings, it seems to me that range locks will boil down to just r/w
>>>>> semaphore.
>>>>> I would also be very grateful if you can point me to any more recent
>>>>> discussions regarding
>>>>> the use of range locks after this patch from February.
>>>> You're on the right page.
>>>>
>>>> Thanks,
>>>> Davidlohr
>>>>
>>
>