[4/5] arm64: mm: Support ASID isolation feature

  After a rollover, the global generation will be flushed, which will
cause the process mm->context.id on all CPUs do not match the
generation. Thus, the process will compete for the global spinlock lock
to reallocate a new ASID and refresh the TLBs of all CPUs on context
switch. This will lead to the increase of scheduling delay and TLB miss.

In some delay-sensitive scenarios, for example, part of CPUs are
isolated, only a limited number of processes are deployed to run on the
isolated CPUs. In this case, we do not want these key processes to be
affected by the rollover of ASID.

An ASID isolation method can reduce interference. We divide the
asid_generation into different domains, for example, HOUSEKEEPING and
ISOLATION. Processes in different domains allocate ASID from the shared
asid_map pool, then combine with the generation of local domain as the
mm->context.id. After an ASID rollover, the generation of the
HOUSEKEEPING domain can be flushed independently, and only the TLB of
HOUSEKEEPING domain CPUs will be flushed, so the processes of ISOLATION
domain will not be affected.

In addition, the ASID of the ISOLATION domain is stored in the
isolated_asid bitmap. When the asid_map is refreshed, the isolated_asid
must be copied to the asid_map to ensure that the ASID of the ISOLATION
domain is not allocated by other processes.

The following figure shows the example:

    HOUSEKEEPING (genid: G1)            ISOLATION (genid: G2)

    task1(G1,1)                         task2(G2,2)     task3(G2,3)

    cpu0        cpu1                    cpu3    cpu4    cpu5
    -------------------------           -----------------------
                            \           /              |
                             \         /      isolated_asid: [2,3]
                              \       /
                 asid_map: [1,2,3,4,...,65536]

The task1 is running on the HOUSEKEEPING domain, it allocate ASID 1 from
shared asid_map, so the context id of task1 is (G1,1). The task2 and
task3 are running on the ISOLATION domain, they allocate ASID 2,3 from
shared asid_map, and store ASID 2,3 to isolated_asid. the context id of
task2 is (G2,2), and the context id of task3 is (G2,3). After a
rollover, the generation of HOUSEKEEPING doamin is flushed, for example,
it becomes to G3, then the context id of task1 is changed to (G3,1). In
this time, the generation of ISOLATION domain is not affected.

In some scenarios, a process has multiple threads, and different threads
run in different domains, or processes migrate between different domains.
But the process has only one context ID, there is a problem that how to
select generation in this case. The way we're thinking is, as long as
the process has run to ISOLATION doamin, select generation of ISOLATION
doamin.

For example:

    HOUSEKEEPING (genid: G1)            ISOLATION (genid: G2)

    task1(G1,1)               ====>     task1(G2,1)
    task2(G2,2)               <====     task2(G2,2)

    cpu0        cpu1                    cpu3    cpu4    cpu5
    -------------------------           -----------------------

When task1 is migrated from HOUSEKEEPING domain to ISOLATION domain, the
generation G1 must be changed to G2, and save the ASID 1 to isolated_asid
bitmap. But when task2 is migrated from ISOLATION domain to HOUSEKEEPING
domain, it still use generation G2. In this way, we solve the problem
that which generation should be selected in the scenario of process
migration.

As mentioned before, the generation of different domains is different.
we divide the generation into two parts, the lowest bit is used as the
Flag bit to indicate the HOUSEKEEPING and ISOLATION domain, and the rest
bits are used as the Upper-generation. After a rollover, only the
Upper-generation is flushed, the Flag part does not change in the entire
life. This ensures that the genrentaion of different domains is different.

    asid_generation    |---------------------------|-|--------|
                              Upper-generation     Flag

Finally, it is important to select which domain generation and TLBs are
flushed after a rollover. By default, only the HOUSEKEEPING domain is
selected. When the number of ASIDs in the ISOLATION domain exceeds the
max threshold, the ISOLATION domain is selected too.

By default, the ASID isolation feature is disabled, and a cmdline
parameter is provided to control whether the ASID isolation feature is
enabled.

Signed-off-by: Yunfeng Ye <yeyunfeng@huawei.com>
---
 arch/arm64/mm/context.c | 203 ++++++++++++++++++++++++++++++++++++----
 1 file changed, 183 insertions(+), 20 deletions(-)
  

On Mon, Oct 17, 2022 at 04:32:02PM +0800, Yunfeng Ye wrote:
> After a rollover, the global generation will be flushed, which will
> cause the process mm->context.id on all CPUs do not match the
> generation. Thus, the process will compete for the global spinlock lock
> to reallocate a new ASID and refresh the TLBs of all CPUs on context
> switch. This will lead to the increase of scheduling delay and TLB miss.
> 
> In some delay-sensitive scenarios, for example, part of CPUs are
> isolated, only a limited number of processes are deployed to run on the
> isolated CPUs. In this case, we do not want these key processes to be
> affected by the rollover of ASID.

Part of this commit log should also go in the cover letter and it would
help to back this up by some numbers, e.g. what percentage improvement
you get with this patchset by running hackbench on an isolated CPU.

In theory it looks like CPU isolation would benefit from this patchset
but we try not to touch this code often, so any modification should come
with proper justification, backed by numbers.

Note that I haven't reviewed the algorithm you are proposing in detail,
only had a brief look.
  

On 2022/11/9 20:43, Catalin Marinas wrote:
> On Mon, Oct 17, 2022 at 04:32:02PM +0800, Yunfeng Ye wrote:
>> After a rollover, the global generation will be flushed, which will
>> cause the process mm->context.id on all CPUs do not match the
>> generation. Thus, the process will compete for the global spinlock lock
>> to reallocate a new ASID and refresh the TLBs of all CPUs on context
>> switch. This will lead to the increase of scheduling delay and TLB miss.
>>
>> In some delay-sensitive scenarios, for example, part of CPUs are
>> isolated, only a limited number of processes are deployed to run on the
>> isolated CPUs. In this case, we do not want these key processes to be
>> affected by the rollover of ASID.
> 
> Part of this commit log should also go in the cover letter and it would> help to back this up by some numbers, e.g. what percentage improvement
> you get with this patchset by running hackbench on an isolated CPU.
> 
> In theory it looks like CPU isolation would benefit from this patchset
> but we try not to touch this code often, so any modification should come
> with proper justification, backed by numbers.
> 
Yes, CPU isolation will benefit from this patchset. We use cyclictest tool
to test the maximum scheduling and interrupt delays, found that the
sched_switch process takes several microseconds sometimes, The analysis
result shows that the delay is caused by the ASID refresh.

We use simple test cases to construct the case of quickly consumption of
ASIDs, this increases the ASID refresh frequency and the contention for
the global ASID spin lock. In this case, the delay between sched_switch
and tlb_flush can reach 63 us. The following is the trace log:

    stress-ng-2864907 [012] dN.. 17006.430048: sched_stat_runtime: comm=stress-ng pid=2864907 runtime=859130 [ns] vruntime=9015202524211 [ns]
    stress-ng-2864907 [012] d... 17006.430048: sched_switch: prev_comm=stress-ng prev_pid=2864907 prev_prio=120 prev_state=R ==> next_comm=cyclictest next_pid=2866344 next_prio=19
    stress-ng-2864907 [012] d... 17006.430111: tlb_flush: pages:-1 reason:flush on task switch (0)
// 17006.430111 - 17006.430048 = 63 us

    cyclictest-2866344 [012] .... 17006.430112: kfree: call_site=__audit_syscall_exit+0x210/0x250 ptr=0000000000000000
    cyclictest-2866344 [012] .... 17006.430112: sys_exit: NR 115 = 0
    cyclictest-2866344 [012] .... 17006.430112: sys_clock_nanosleep -> 0x0
    cyclictest-2866344 [012] d... 17006.430113: user_enter:
    cyclictest-2866344 [012] d... 17006.430126: user_exit:
    cyclictest-2866344 [012] .... 17006.430126: sys_enter: NR 64 (4, ffffa451c4d0, 1f, 0, 3b, 0)
    cyclictest-2866344 [012] .... 17006.430126: sys_write(fd: 4, buf: ffffa451c4d0, count: 1f)
    cyclictest-2866344 [012] .... 17006.430129: tracing_mark_write: hit latency threshold (72 > 30)

The delay caused by ASID interference is variable, may be several nanoseconds,
or may be several microseconds, it depends on the concurrent competition.
If this patch series is used, the delay caused by ASID interference on the
isolated CPU can be reduced.

Thanks.

> Note that I haven't reviewed the algorithm you are proposing in detail,
> only had a brief look.
>
  

On Thu, Nov 10, 2022 at 03:07:53PM +0800, Yunfeng Ye wrote:
> On 2022/11/9 20:43, Catalin Marinas wrote:
> > On Mon, Oct 17, 2022 at 04:32:02PM +0800, Yunfeng Ye wrote:
> >> After a rollover, the global generation will be flushed, which will
> >> cause the process mm->context.id on all CPUs do not match the
> >> generation. Thus, the process will compete for the global spinlock lock
> >> to reallocate a new ASID and refresh the TLBs of all CPUs on context
> >> switch. This will lead to the increase of scheduling delay and TLB miss.
> >>
> >> In some delay-sensitive scenarios, for example, part of CPUs are
> >> isolated, only a limited number of processes are deployed to run on the
> >> isolated CPUs. In this case, we do not want these key processes to be
> >> affected by the rollover of ASID.
> > 
> > Part of this commit log should also go in the cover letter and it would> help to back this up by some numbers, e.g. what percentage improvement
> > you get with this patchset by running hackbench on an isolated CPU.
> > 
> > In theory it looks like CPU isolation would benefit from this patchset
> > but we try not to touch this code often, so any modification should come
> > with proper justification, backed by numbers.
> > 
> Yes, CPU isolation will benefit from this patchset. We use cyclictest tool
> to test the maximum scheduling and interrupt delays, found that the
> sched_switch process takes several microseconds sometimes, The analysis
> result shows that the delay is caused by the ASID refresh.

Do you know whether it's predominantly the spinlock or the TLBI that's
causing this (or just a combination of the two)?

I was talking to Will and concluded we should try to reuse the ASID
pinning code that's already in that file rather than adding a new
bitmap. At a high level, a thread migrating to an isolated CPU can have
its ASID pinned. If context switching only happens between pinned ASIDs
on an isolated CPU, we may be able to avoid the lock even if the
generation rolled over on another CPU.

I think the tricky problem is when a pinned ASID task eventually dies,
possibly after migrating to another CPU. If we avoided the TLBI on
generation roll-over for the isolated CPU, it will have stale entries.
One option would be to broadcast a TLBI for the pinned ASID when the
task dies, though this would introduce some jitter. An alternative may
be to track whether a pinned ASID ever run on a CPU and do a local TLBI
for that ASID when a pinned thread is migrated.

All these need a lot more thinking and (formal) modelling. I have a TLA+
model but I haven't updated it to cover the pinned ASIDs. Or,
alternatively, make the current code stand-alone and get it through CBMC
(faking the spinlock as pthread mutexes and implementing some of the
atomics in plain C with __CPROVER_atomic_begin/end).
  

On 2022/11/29 1:00, Catalin Marinas wrote:
> On Thu, Nov 10, 2022 at 03:07:53PM +0800, Yunfeng Ye wrote:
>> On 2022/11/9 20:43, Catalin Marinas wrote:
>>> On Mon, Oct 17, 2022 at 04:32:02PM +0800, Yunfeng Ye wrote:
>>>> After a rollover, the global generation will be flushed, which will
>>>> cause the process mm->context.id on all CPUs do not match the
>>>> generation. Thus, the process will compete for the global spinlock lock
>>>> to reallocate a new ASID and refresh the TLBs of all CPUs on context
>>>> switch. This will lead to the increase of scheduling delay and TLB miss.
>>>>
>>>> In some delay-sensitive scenarios, for example, part of CPUs are
>>>> isolated, only a limited number of processes are deployed to run on the
>>>> isolated CPUs. In this case, we do not want these key processes to be
>>>> affected by the rollover of ASID.
>>>
>>> Part of this commit log should also go in the cover letter and it would> help to back this up by some numbers, e.g. what percentage improvement
>>> you get with this patchset by running hackbench on an isolated CPU.
>>>
>>> In theory it looks like CPU isolation would benefit from this patchset
>>> but we try not to touch this code often, so any modification should come
>>> with proper justification, backed by numbers.
>>>
>> Yes, CPU isolation will benefit from this patchset. We use cyclictest tool
>> to test the maximum scheduling and interrupt delays, found that the
>> sched_switch process takes several microseconds sometimes, The analysis
>> result shows that the delay is caused by the ASID refresh.
> 
> Do you know whether it's predominantly the spinlock or the TLBI that's
> causing this (or just a combination of the two)?
> 
I think the spinlock is the main factor, I didn't distinguish how much
time it took for each of the two. On the other hand, the TLBI is processed
under the spinlock currently, its time-consuming will increase the
time-consuming of the spinlock too.

> I was talking to Will and concluded we should try to reuse the ASID
> pinning code that's already in that file rather than adding a new
> bitmap. At a high level, a thread migrating to an isolated CPU can have
At first, I want to reuse the ASID pinned bitmap too, which is the same
idea with you. but there is a difference between pinned bitmap and isolation
bitmap, the pinned bitmap will not be changed when the generation roll-over,
while the isolation bitmap need to be flushed.

The idea "broadcast a TLBI for the pinned ASID when the task dies" you
mentioned below maybe can reuse the pinned bitmap. I've considered this idea
too, I think this method is not as good as the current two bitmap method:

1. This will introduce some TLBI jitter, and maybe increase the contention
of spinlock when updating the pinned bitmap, which we don't want the jitter
on the isolation CPU.

2. Another disadvantage is that if only one pinned bitmap is used and a large
number of processes are on the isolation domain but the processes are not dead,
the available ASIDs are insufficient. for example, more than 65536 processes
running or sleeping on the isolation CPU, how to handle this situation?

> its ASID pinned. If context switching only happens between pinned ASIDs
> on an isolated CPU, we may be able to avoid the lock even if the
> generation rolled over on another CPU.
> 
> I think the tricky problem is when a pinned ASID task eventually dies,
> possibly after migrating to another CPU. If we avoided the TLBI on
> generation roll-over for the isolated CPU, it will have stale entries.
> One option would be to broadcast a TLBI for the pinned ASID when the
> task dies, though this would introduce some jitter. An alternative may
> be to track whether a pinned ASID ever run on a CPU and do a local TLBI
> for that ASID when a pinned thread is migrated.
> 
> All these need a lot more thinking and (formal) modelling. I have a TLA+
> model but I haven't updated it to cover the pinned ASIDs. Or,
> alternatively, make the current code stand-alone and get it through CBMC
> (faking the spinlock as pthread mutexes and implementing some of the
> atomics in plain C with __CPROVER_atomic_begin/end).
>