[Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Richard Cochran]

I know that this is a bit off topic, yet perhaps some on this list
have interest or knowledge in this area. I am also posting this idea
to the linux-arm-kernel list.

I would like to implement the ARM FCSE under Linux, using the Intel
IXP425 board. Before I start, I would like to ask:

1. Has any work already been done in this area?

2. Is there something about the current Linux MM that would make this
   impractical?

3. Does anyone else have interest in this?

I had once proposed this task as a student project, and so I append
the long project description, below.

Thanks,
Richard

ARM Fast Context Switch Extension for Linux

Motivation

 The ARM v5 CPUs are inexpensive, low power, 32 bit processors widely
 used in embedded systems. However, because of these processors' cache
 implementation, using memory protection on these systems may incur a
 performance penalty that is too great for real time applications. The
 aim of this study is to achieve both memory protection and good cache
 performance under the Linux 2.6 operating system, by implementing
 the Fast Context Switch Extension (FCSE).

Task

 ARM v5 processors access the cache by virtual addresses. As a result,
 the cache is invalidated after a context switch, since no two
 processes share the same address space. Reloading the cache from main
 memory is a very expensive operation.

 One approach to address this problem, used for example in vxWorks or
 uClinux, is to use one "flat" address space, shared by the operating
 system kernel and all user processes. This avoids the context switch
 penalty while sacrificing memory protection. The obvious drawback
 under this scenario is that any one misbehaving program can corrupt
 the kernel or other programs.

 Another solution, not yet implemented under Linux, is to use the
 "Process ID" register found on some ARM CPUs, for example the Intel
 IXP425. This register contains a 7 bit process identifier that can be
 combined with a 25 bit virtual address. Using this method allows 128
 distinct 32 MB address spaces, so that up to 128 processes may safely
 co-exist, without paying the context switch penalty. The resulting
 limitation of 128 processes and 32 MB address space is acceptable for
 many embedded systems.

 The tasks of this study would be:

 1. Research and summarize the existing work in this area.

 2. Benchmark the current implementations to demonstrate the problem,
    using "standard" Linux, Xenomai, and the PREEMPT_RT patch set.

 3. Illuminate the Linux memory management subsystem.

 4. Implement FCSE in the Linux memory management subsystem.

 5. Benchmark the result of the improved kernel.

Selected references:

o A short summary of the issue and the approach used by QNX:
  http://www.qnx.com/developers/docs/6.3.0/neutrino/prog/arm_memory.html

o Context Switching and IPC Performance Comparison between uClinux and
  Linux on the ARM9 based Processor
  http://opensrc.sec.samsung.com/document/uc-linux-04_sait.pdf

o Fast Address-Space Switching for ARM Linux Kernels
  http://www.ertos.nicta.com.au/software/fass/

o Context Switch Overheads for Linux on ARM Platforms
  http://choices.cs.uiuc.edu/contextswitching.pdf

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Gilles Chanteperdrix]

On 9/20/07, Richard Cochran <richard.cochran@domain.hid> wrote:
> I know that this is a bit off topic, yet perhaps some on this list
> have interest or knowledge in this area. I am also posting this idea
> to the linux-arm-kernel list.
>
> I would like to implement the ARM FCSE under Linux, using the Intel
> IXP425 board. Before I start, I would like to ask:
>
> 1. Has any work already been done in this area?
>
> 2. Is there something about the current Linux MM that would make this
>    impractical?

All I have read about it is the FASS project, which you cite. Somebody
recently asked the question on the ARM linux mailing list, maybe
reading the answer would help you know what ARM linux maintainers
think about this idea.
http://lists.arm.linux.org.uk/pipermail/linux-arm-kernel/2007-August/041832.html

-- 
                                               Gilles Chanteperdrix

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 4706 bytes --]

Richard Cochran wrote:
> I know that this is a bit off topic, yet perhaps some on this list
> have interest or knowledge in this area. I am also posting this idea
> to the linux-arm-kernel list.
> 
> I would like to implement the ARM FCSE under Linux, using the Intel
> IXP425 board. Before I start, I would like to ask:
> 
> 1. Has any work already been done in this area?
> 
> 2. Is there something about the current Linux MM that would make this
>    impractical?

Nothing is impossible (specifically as FASS proves its feasibility),
it's just a question how much work it is to implement it AND maintain it
or merge it into standard Linux. And I cannot imagine ARM or its
licensees dropping this feature without an acceptable alternative once
Linux started to use it broadly...

> 
> 3. Does anyone else have interest in this?

I can only repeat that I think this is a worthwhile effort - at least
until we know the real effort required for hacking this into Linux and
then Xenomai :). It would be really great for ARM real-time applications
if you could once isolate then in their own address range, reducing the
context switch latencies significantly!

So, please try to find out more details about the requirements and
limitations, let us know about them even if some realisation turns out
to be too much for a student job. Maybe other will jump on this, maybe I
can organise some support then (no promise, consider this yet as my
private idea... :) ).

> 
> I had once proposed this task as a student project, and so I append
> the long project description, below.
> 
> Thanks,
> Richard
> 
> ARM Fast Context Switch Extension for Linux
> 
> Motivation
> 
>  The ARM v5 CPUs are inexpensive, low power, 32 bit processors widely
>  used in embedded systems. However, because of these processors' cache
>  implementation, using memory protection on these systems may incur a
>  performance penalty that is too great for real time applications. The
>  aim of this study is to achieve both memory protection and good cache
>  performance under the Linux 2.6 operating system, by implementing
>  the Fast Context Switch Extension (FCSE).
> 
> Task
> 
>  ARM v5 processors access the cache by virtual addresses. As a result,
>  the cache is invalidated after a context switch, since no two
>  processes share the same address space. Reloading the cache from main
>  memory is a very expensive operation.
> 
>  One approach to address this problem, used for example in vxWorks or
>  uClinux, is to use one "flat" address space, shared by the operating
>  system kernel and all user processes. This avoids the context switch
>  penalty while sacrificing memory protection. The obvious drawback
>  under this scenario is that any one misbehaving program can corrupt
>  the kernel or other programs.
> 
>  Another solution, not yet implemented under Linux, is to use the
>  "Process ID" register found on some ARM CPUs, for example the Intel
>  IXP425. This register contains a 7 bit process identifier that can be
>  combined with a 25 bit virtual address. Using this method allows 128
>  distinct 32 MB address spaces, so that up to 128 processes may safely
>  co-exist, without paying the context switch penalty. The resulting
>  limitation of 128 processes and 32 MB address space is acceptable for
>  many embedded systems.
> 
>  The tasks of this study would be:
> 
>  1. Research and summarize the existing work in this area.
> 
>  2. Benchmark the current implementations to demonstrate the problem,
>     using "standard" Linux, Xenomai, and the PREEMPT_RT patch set.
> 
>  3. Illuminate the Linux memory management subsystem.
> 
>  4. Implement FCSE in the Linux memory management subsystem.
> 
>  5. Benchmark the result of the improved kernel.
> 
> Selected references:
> 
> o A short summary of the issue and the approach used by QNX:
>   http://www.qnx.com/developers/docs/6.3.0/neutrino/prog/arm_memory.html
> 
> o Context Switching and IPC Performance Comparison between uClinux and
>   Linux on the ARM9 based Processor
>   http://opensrc.sec.samsung.com/document/uc-linux-04_sait.pdf
> 
> o Fast Address-Space Switching for ARM Linux Kernels
>   http://www.ertos.nicta.com.au/software/fass/

The "funny" thing is that some marketing people use this to argue that
para-virtualised Linux over some specific microkernel is even faster
than native Linux. They just forget to mention the minor technical
details about the origin and the domain of these numbers.

> 
> o Context Switch Overheads for Linux on ARM Platforms
>   http://choices.cs.uiuc.edu/contextswitching.pdf
> 

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Gilles Chanteperdrix]

Jan Kiszka wrote:
 > Richard Cochran wrote:
 > > I know that this is a bit off topic, yet perhaps some on this list
 > > have interest or knowledge in this area. I am also posting this idea
 > > to the linux-arm-kernel list.
 > > 
 > > I would like to implement the ARM FCSE under Linux, using the Intel
 > > IXP425 board. Before I start, I would like to ask:
 > > 
 > > 1. Has any work already been done in this area?
 > > 
 > > 2. Is there something about the current Linux MM that would make this
 > >    impractical?
 > 
 > Nothing is impossible (specifically as FASS proves its feasibility),
 > it's just a question how much work it is to implement it AND maintain it
 > or merge it into standard Linux. And I cannot imagine ARM or its
 > licensees dropping this feature without an acceptable alternative once
 > Linux started to use it broadly...

The feature was already dropped, it is deprecated in ARMv6.

-- 


					    Gilles Chanteperdrix.

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 1602 bytes --]

Gilles Chanteperdrix wrote:
> Jan Kiszka wrote:
>  > Richard Cochran wrote:
>  > > I know that this is a bit off topic, yet perhaps some on this list
>  > > have interest or knowledge in this area. I am also posting this idea
>  > > to the linux-arm-kernel list.
>  > > 
>  > > I would like to implement the ARM FCSE under Linux, using the Intel
>  > > IXP425 board. Before I start, I would like to ask:
>  > > 
>  > > 1. Has any work already been done in this area?
>  > > 
>  > > 2. Is there something about the current Linux MM that would make this
>  > >    impractical?
>  > 
>  > Nothing is impossible (specifically as FASS proves its feasibility),
>  > it's just a question how much work it is to implement it AND maintain it
>  > or merge it into standard Linux. And I cannot imagine ARM or its
>  > licensees dropping this feature without an acceptable alternative once
>  > Linux started to use it broadly...
> 
> The feature was already dropped, it is deprecated in ARMv6.
> 

I'm not claiming to be an ARM insider, but browsing through some manuals
makes me think that "The c13, Context ID Register, [...] replaces the
FCSE PID register. Use of the FCSE PID Register is deprecated."
Moreover: "The ARM1136JF-S processor implements the Fast Context Switch
Extension (FCSE) and high vectors extension that are required to run
Microsoft WindowsCE." Given this popular user, it is highly unlikely
that a feature comparable to FCSE is going to be removed from the ARM
architecture - at least as long as its cache is located at such an
unpleasant place.

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Richard Cochran]

> -----Original Message----- From: Gilles Chanteperdrix > 
> The feature was already dropped, it is deprecated in ARMv6.

Doesn't ARMv6 have a new cache design based on physical addresses?

I thought I saw this somewhere...

Richard

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Richard Cochran]

> -----Original Message----- From: jan.kiszka@domain.hid
> Sent: Monday, September 24, 2007 7:48 PM
>
> So, please try to find out more details about the requirements and
> limitations, let us know about them even if some realisation turns
> out to be too much for a student job. Maybe other will jump on this,
> maybe I can organise some support then (no promise, consider this
> yet as my private idea... :) ).

Okay, I have posted to the linux-arm-kernel list to see if there is
any more general interest in this.

After that, I will try to form a working group for this project,
either on that list or elsewhere.

Richard

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 542 bytes --]

Richard Cochran wrote:
>> -----Original Message----- From: Gilles Chanteperdrix > 
>> The feature was already dropped, it is deprecated in ARMv6.
> 
> Doesn't ARMv6 have a new cache design based on physical addresses?
> 
> I thought I saw this somewhere...

Just grabbed this:

"Version 6 now supports physically tagged caches, reducing software
overhead on context switches."

[http://www.simplemachines.it/doc/ARMv6_Architecture.pdf]

But does this mean this layout is optional or mandatory for ARMv6
integrators?

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Sebastian Smolorz]

Richard Cochran wrote:
> I know that this is a bit off topic, yet perhaps some on this list
> have interest or knowledge in this area. I am also posting this idea
> to the linux-arm-kernel list.
>
> I would like to implement the ARM FCSE under Linux, using the Intel
> IXP425 board. Before I start, I would like to ask:
>
> 1. Has any work already been done in this area?

Yes, we at emlix evaluate the feasibility of porting the FASS patch to a 
modern 2.6 kernel in the context of a customer project. It is far more work 
than expected because central MM implementations both ARM-specific and 
Linux-general have changed since the 2.4 days. What we have done is to take 
the FASS patch and tried to make it work with the 2.6 line rather than 
implementing the concepts from scratch. So far, we are able to compile a 
FASS-patched 2.6.21 kernel but it fails when trying to start init. We expect 
a huge amount of bugs hiding inside the code yet. No wonder, we are still in 
the middle of the work. I would call the code far from being releasable but 
before you also begin to do the work we have already performed it is 
reasonable to post our current status.

We consider to set up a git repository so that you and all interested people 
will be able to clone from it. If anyone feels prepared to contribute code to 
this project we either can provide write access to the repository or do it 
the Linus' way (i.e. we would pull from others' repositories), whichever is 
preferred.


Regards,

Sebastian

-- 
Dipl.-Ing. Sebastian Smolorz, emlix GmbH, http://www.emlix.com
Fon +49 551 30664-0, Fax -11, Bahnhofsallee 1b, 37081 Göttingen, Germany
Geschäftsführung: Dr. Uwe Kracke, Dr. Cord Seele, Ust-IdNr.: DE 205 198 055
Sitz der Gesellschaft: Göttingen, Amtsgericht Göttingen HR B 3160

emlix - your embedded linux partner

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Richard Cochran]

> -----Original Message----- From: Sebastian Smolorz
> Sent: Wednesday, September 26, 2007 11:28 AM
>
> We consider to set up a git repository so that you and all
> interested people will be able to clone from it. If anyone feels
> prepared to contribute code to this project we either can provide
> write access to the repository or do it the Linus' way (i.e. we
> would pull from others' repositories), whichever is preferred.

For now, can you post a diff against a known vanilla kernel version?

Perhaps later we can set up a public project.

Thanks,
Richard

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Sebastian Smolorz]

Richard Cochran wrote:
> > -----Original Message----- From: Sebastian Smolorz
> > Sent: Wednesday, September 26, 2007 11:28 AM
> >
> > We consider to set up a git repository so that you and all
> > interested people will be able to clone from it. If anyone feels
> > prepared to contribute code to this project we either can provide
> > write access to the repository or do it the Linus' way (i.e. we
> > would pull from others' repositories), whichever is preferred.
>
> For now, can you post a diff against a known vanilla kernel version?
>
> Perhaps later we can set up a public project.

Nevertheless, here comes our git repository:
http://git.opensource.emlix.com

Note that this patch is far less than finished. It is hackish, it does not 
work, but you asked for it. ;-)

The current status is: Sometimes the kernel boots properly and I get a shell 
prompt. Then a 'ls' is possible, sometimes two but then the systems freezes.

Still a lot of work to do but we are ready to do it and are confident of 
getting this beast running.

If anyone is interested: Don't hesitate to help.


Regards,

Sebastian

-- 
Dipl.-Ing. Sebastian Smolorz, emlix GmbH, http://www.emlix.com
Fon +49 551 30664-0, Fax -11, Bahnhofsallee 1b, 37081 Göttingen, Germany
Geschäftsführung: Dr. Uwe Kracke, Dr. Cord Seele, Ust-IdNr.: DE 205 198 055
Sitz der Gesellschaft: Göttingen, Amtsgericht Göttingen HR B 3160

emlix - your embedded linux partner

Re: [Xenomai-core] [RFC] Fast Context Switch Extension for ARM Linux

[Richard Cochran]

> -----Original Message----- From: Sebastian Smolorz
> Sent: Friday, September 28, 2007 6:48 PM

> Nevertheless, here comes our git repository:
> http://git.opensource.emlix.com

Thank you for that. I will take a look...

> Still a lot of work to do but we are ready to do it and are
> confident of getting this beast running.

That's the spirit!

> If anyone is interested: Don't hesitate to help.

I have introduced this idea (and your git link) on the
linux-arm-kernel list. Please look there for the continuation of this
discussion.

Thanks again,
Richard