Home

Lightweight RTAI for IA-32 (revised version)

1. 3 3 Merged build systemsl 2 222 2 oo oo mn Implementation details Al The boot process 4 2 The nano SLOB memory 43 Memory layout 44 Problems I Measurements DA 2 3 29 29x43 2442309393555 5 2 Scheduling latencies 5 3 Image size and memory Conclusions Sample implementation for using a private heap Building the LRTAI kernel image GnuPG signature of the LRTAI tarball Copyright notice omenclature References l lt Ee 39 39 43 46 48 51 51 22 53 57 VII List of Figures 2 1 Introduction of an explicit preemption point in fs dcache c 5 2 2 Stacked layers in a Linux RTAI system 7 2 3 make menuconfig provides dialog based kernel configu ration for choosing between various features and or for tuning TIERE 13 3 Simplified overview of vital file layouts on IA 32 23 4 Traditional boot sector layout on a PC architecture 40 4 2 Simplified exemplary boot process IA 32 42 4 3 Example of a memory map provided by the BIOS for a system with 4 MiB RAM installed 48 5 1 Latency of Linux RTAI in oneshot mode 54 5 2 Latency of Lightweight RTAI in oneshot mode 54 5 3 Latenc
2. usable reserved reserved usable ACPI data ACPI NVS reserved Figure 4 3 Example of a memory map provided by the BIOS for a system with 4 MiB RAM installed time At runtime the major factor is the BIOS which provides information about the current system configuration This 15 used by the kernel while requesting a memory map from the BIOS before switching the CPU into protected mode This map is a simple list of use able and or reserved memory areas in the system An example of such a map is shown in Figure Important memory points and the resulting memory layout of the real mode kernel part should be evident from Figure Beside the flow of execution it shows where the kernel image respectively its parts are located in memory A standard boot process 1 e via a bootloader on a system with more than 1 MiB of RAM was taken as a basis After switching into protected mode and remaining at its final location the kernel 15 able to generate a list of usable RAM areas founding on the received memory map and its built in knowledge of its own location The last important step in the memory management is to free the areas which are marked as sections This is done after the major initializations routines have finished and the code and data is not needed anymore By simply marking the relevant pages as free they can be utilized by the bootmem allocator for subsequent memory requests 4 4 Problems Ev
3. CHEMNITZ UNIVERSITY OF TECHNOLOGY Faculty of Computer Science Chair for Real Time Systems Diploma Thesis Lightweight RTAI for IA 32 revised version Michael Heimpold Chemnitz June 21 2007 Supervisor Dr Ing Robert Baumgartl Heimpold Michael Lightweight RTAI for LA 32 revised version Diploma Thesis Faculty of Computer Science Chair for Real Time Systems Chemnitz University of Technology June 21 2007 Abstract Using the IA 32 platform for time critical tasks allows the highest computing performance at reasonable hardware costs However systems with restricted resources have been limited to proprietary real time operating systems As many of available open source real time distributions base on the Linux ker nel the relatively high requirements of Linux also apply to these systems In this work a porting of the open source RTAI distribution to a bare machine 1s presented which eliminates Linux core subsystems Thus the image size and the memory footprint are optimized for small systems Henceforth a freely available efficient and well supported real time operating system can be used on A 32 with restricted resources Acknowledgements I would l ke to use the chance at th s point to thank everybody who supported me during preparation of this work At first I thank my parents who made my studies possible at all Furthermore I want to thank my family especially my wife and friends for the patience they
4. Also the special use case above would result to an RTAI heap in RTAI heap scenario which could potentially lead to confusion 3 1 6 3 RTAl s own memory management RTAI comes with an additional layer of memory management as has already became evident This 1s necessary to fulfill hard real time constraints Since the original Linux system tries always to serve memory requests e g by freeing unused caches it can suspend the execution of the requesting task However using this mechanisms could break the timing of a real time application The RTAI module rtai_malloc bypasses these problems by preallocating memory blocks from the Linux memory manager and by distributing this space via its own interface to RTAI applications To fulfill the timing constraints it can be forced to operate in a time bounded fashion Thereto the used memory heap from which the request should be served needs to be non extendable Otherwise on a standard Linux RTAI system when the heap is marked extend 28 3 1 Taken over concepts able the allocat on request can also tr gger a dynamic enlargement losing hard real time Although this functionality is still documented in the manuals there was no code found the sources which provide this feature Support for dynamic expansion seems to be dropped silently from RTAT s upstream It could be reimplemented easily with a few lines of code But since in LRTAI only hard real time tasks exists which usually sh
5. RM 0x1000 ER 0 7 00 0x8000 0x24000 0x68000 640 kiB 1 MiB y SC stage GRUB stack stage S x stage 2 Heap Not ad ressable boot loader 0x2000 F 4 n a The bootloader loads the kernel image into memory an passes control to it by jumping to a well known entry point 0x1000 640kiB 1 MiB RM boot sector loader decompressor gzip compressed data Not addressable Kernel arch i386 boot setup S The kernel moves the decompfessor stub and the compressed block down and relocates itself to a well known address 0x1000 0x90000 b 640 kiB 1 MiB RM 1 decompressor gzip compressed data boot sector loader Not addressable Kernel x arch i386 boot setup S The decompressor stub and the compressed block is moved down the real mode code relocates itself both to a well known address Finally the CPU is switched to protected mode and the protected mode code decompressor is called 0x1000 640 1 MiB PM 1 gzip compressed data Kernel arch i386 boot compressed head S 0x1000 640 kiB 1 MiB PM J uncompressed code Kernel x arch i386 kernel head S RM Real Mode x Execution location PM Protected Mode Figure 4 2 Simplified exemplary boot process on IA 32 42 4 2 The nano SLOB memory allocator comparison to a standard Linux RTAI system the relevant makefile was writ ten with this in mind In the end the original hal module is initialized first which registers the RTAI domain in the IPIPE sys
6. 16 bit code This entry point is the startup function located in arch i566 boot setup S which does some elementary initialization e g tries to determine how much memory is installed Later the protected mode part which is still compressed is moved down in the memory After these preparations the CPU 1 finally switched into protected mode and a startup 32 archi386 boot compressed head S function is called This routine sets up a basic environment e g a tiny stack and clears the Block Started by Symbol BSS area Subsequently the underlying ker nel is decompressed through a call to a C function decompress kernel arch 40 4 1 The boot process i386 boot compressed misc c This code is located in a small non compressed stub which heads the compressed part cf Figure 3 1 The remaining compressed code just places the Image at the memory location which was chosen at configuration time This will be discussed in detail in section Finally yet another startup_32 located arch i566 kernel head S function is called which initializes the page tables detects the CPU type and the FPU and starts the paging Then it passes control to start kernel init main c which runs the non architecture specific boot routines This can be regarded as the kernel s main function in comparison to a normal C program Figure 4 2 trates an example of a boot process using GRUB from hard disk until the call of startup 32 in arch i366
7. 21 09 2006 Abgabedatum 21 06 2007 Tag der Abgabe 111 Contents 1 2 State of the art 3 2 Linux kernel s native real time support 3 2 1 1 Historical non preemptibility 3 TT 4 FR SURE MURS SE d m 4 2 1 4 Final approach full preemptibility 5 THEM 6 Principle a s lt nu 0 an RU ER EO 9 xS 6 rr 9 22222 Scheduline u x Q s zu zu be Q N XE REOR 9 2 2 4 Memory management 10 2 25 Additional 11 TV 12 2 3 1 13 2 52 Mak AlS ss we dee doe Sted D Q b Q 14 ee eee 14 5525 55 Ee Ee 15 2 6 Other related work 16 19 3 1 Taken over 2 3 1 1 Binary image layout 21 3 1 2 Image compression 08 4 24 3 1 3 Kernel command line 25 olx Initealls x 023 4o ERE EAE 44 25 3 1 5 Initialization memory freeing 26 3 1 6 Memory management 27 Contents 3 1 6 1 Bootmem memory allocator 3 1 6 2 Nano SLOB allocator 3 1 6 3 own memory management 3 1 6 4 Private heaps of real time applications 3 1 7 Console output via printk 2 2 22 22 2 3 1 8 Tracking time with fies 2 222222 2200 32 Spurned features
8. Linux Kernel Development Second Edition Novell Press 2005 ISBN 0 67232 720 1 5 Homepage of MontaVista Software Inc ttp www mvista com June 21 2007 x 6 The Preemption Patches at Robert Love s kernel org space ttp www kernel org pub linux kernel people rml preempt kernel June 21 2007 7 Clark Williams Linux Scheduler Latency Red Hat Inc March 2002 ttp www linuxdevices com files article027 rh rtpaper pdf June 21 2007 8 Linux Kernel Organization The Linux Kernel Archives ttp www kernel org June 21 2007 x x p References 9 Victor Yodaiken and Michael Barabanov A Real Time Linux New 10 11 12 13 14 15 XII Mexico Institute of Technology 1996 1997 tp luz cs nmt edu pub rtlinux papers usenix Offline ttp citeseer ist psu edu 6239 html June 21 2007 E Paolo Mantegazza DIAPM RTAI for Linux WHYs WHATs and HOWs Real Time Linux Workshop at Vienna University of Technology Decem ber 1999 ttps www rtai org index php module ocuments amp JAS DocumentManager op ownloadFile amp JAS File id 31 June 21 2007 Markus Franke A Quantitative Comparison of Realtime Linux Solutions Seminar paper Chemnitz University of Technology March 5 2007 ttp rtg informatik tu chemnitz de docs a sa txt sa franm pdf The ADEOS Project ttp home gna org adeos June 21 2007 D Marshall K McKusick and Mi
9. a DSP architecture was performed by 1 and 2 Also a lower bound of the required memory for the newly developed system will be discussed and this 15 expected to simplify the decision whether the use of LRTAI for a real time system should be considered or if a traditional Linux RTAI system would be more appropriate Chapter 2 State of the 2 1 Linux kernel s native real time support 2 1 1 Historical non preemptibility As already mentioned the Linux kernel was originally not designed for real time awareness One indication for this 1s that all interrupts are treated as equal For a possible prioritization the kernel relies on the hardware to care for this Also it was not a preemptive kernel at all It was assumed that when entering the kernel from a trap or a system call the current user space process would not change unexpectedly In kernel version 2 0 a global kernel lock was inserted to ease the introduc tion of symmetric multiprocessing SMP support This was needed to protect some critical sections and to serialize the access to important data structures If a process wanted to enter the kernel t had to acquire this so called Big Kernel Lock BKL The kernel itself could therefore be seen as a big critical section which was not preemptible However it was possible that a process calls the scheduler voluntary A kernel with such properties is not suitable for real time systems If a hard ware interrupt occurs which
10. a Linux RTAI system the first version under the acronym RTAI was finally released Meanwhile the project 1 not solely a research work but a distributed open source commu nity project and a widely used real time distribution More of the history of the project can be found in and an overview of the various Linux based real time distributions and their mutual influences 1 given in 11 As already mentioned the RTAI concept bases on the kernel dualism ap proach For this a hardware abstraction layer HAL 15 used This layer 15 inserted between the real hardware and the Linux kernel and covers in sub stance only the interrupt system Figure 2 2 illustrates the stacked layers in a Linux RTAI system The idea behind such an abstraction layer is that deter minism of a scheduling algorithm can only be achieved when full control over the interrupt system 16 available This 16 explained in the following subsection Furthermore RTAI comes with a separate scheduling algorithm which en ables the resulting system to run tasks which are completely independent from the Linux kernel The RTOS base is completed by a real time aware mem Chapter 2 State of the art management and some inter process communication IPC tools These concepts are also Introduced in the following paragraphs 2 2 2 The interrupt pipeline The interrupt pipeline in short PIPE is the core of the two kernel strategy What 1s called kernel depends on the used
11. complexity should not exceed this upper bound while being less complex s acceptable A metric for the efficiency 1s given by the comparison of the scheduling latencies The values of the new RTOS should not be worse than those of an established Linux RTAI system Therefore measurement should be done to confirm this thesis Broadly there are two possible approaches of dealing with this task The first one 1s to take the existing RTAI code as a base and looking through the sources which global variables and data structures respectively which functions are used It has to be examined if these are relevant for functionality on the given platform In this case these have to be reimplemented later and pushed un derneath the RTAI system Otherwise they can be replaced with a simple stub function or they could be simply dropped Then the referring parts of the ex isting code need probably to be adopted to fit the new base system While this approach gives the possibility to completely ignore the previous base system and therefore allows an entire redesign of the new code this is at the same time the main disadvantage The whole new code has to be written from scratch This is not a problem by itself however it could negatively influence the ac ceptance of the project by the industry which prefers matured and well tested code to save cost intensive test cases The second way takes an established Linux RTAI system as a base and then cuts the unneed
12. excludes lt M gt modularizes features Press lt Esc gt lt Esc gt to exit lt gt for Help lt gt for Search Legend built in excluded M module lt gt symmetric multi processing support ubarchitecture Type PC compatible gt rocessor family 586 K5 5x86 6x86 6x86MX gt eneric x86 support H ET Timer Support reemption Model No Forced Preemption Server nterrupt pipeline ocal APIC support on uniprocessors M chine Check Exception oshiba Laptop support ell laptop support Figure 2 3 A make menuconfig provides a dialog based kernel configuration for choosing between var ous features and or for tuning parameters Each configuration tem has a data type which defines which values the tem can hold The most important types are Int bool and tristate where the last mentioned will accept the values n or m This 1 usually used to decide whether an item should be included statically in the kernel image y or if it should be built as a loadable module m A value of n indicates that the feature behind the item 1s not used The kernel build system knows which configuration items are available by inspecting the various Kconfig files spread over the source tree To keep the overview the items are grouped into menus at different levels Since some modules this 1s true for the statically included one
13. had with me in the last months and for their moral support A special thanks goes to J rg R del for proof reading this work Last but not least I want to thank my supervisor Dr Ing Robert Baumgartl for supporting this work and for his understanding of the problems I had with it Aufgabenstellung Das Realt me Application Interface ist ein Weg die Echtzeitf higkeit von Linux zu erreichen Nachteilig ist jedoch der verh ltnism ig gro e Spei cherplatzbedarf eines RTAI Systems sowie die fehlende Separierung zwischen Echtzeit Applikationen und Linux Kernel Ziel der Arbeit ist es daher f r die PC Architektur IA 32 das Linux Subsystem aus einem RTAI System zu elimi nieren F r eine DSP Architektur 1st dies bereits erfolgreich durchgef hrt worden DA Jens Kretzschmar die Intel Architektur bietet jedoch einige Herausforde rungen da vielf ltige Beziehungen zwischen RTAI und dem Linux Subsystem bestehen Unter anderem muss der Bootvorgang und der Start des Systems neu konzipiert werden der traditionelle insmod rmmod Mechanismus steht nicht mehr zur Verf gung Das resultierende System ist ein sehr kleiner bersichtlicher und effizien ter Echtzeitkernel der die RTAI API bietet und f r Systeme mit stark einge schr nkten Ressourcen pr destiniert ist Bearbeiter Michael Heimpold geb am 15 05 1981 n Werdau Betreuender Hochschullehrer Dr Ing Robert Baumgartl Juniorprofessur Echtzeit Systeme Ausgabedatum
14. no changes necessary This will keep the efforts for maintenance low e g when if the system is ported to a new kernel version 37 Chapter 3 Design 38 Chapter 4 Implementation details 4 1 The boot process The process of booting a Linux RTAI system consists of a number of stages When the system is powered on or reset the CPU instruction pointer register is set to a hard wired well known value and thus executing code at a well known location In standard PCs this code 1 located in the systems BIOS stored in a small flash memory on the motherboard Usually a modern BIOS 15 very flexible in the further boot process 1 e the user can choose between a wide range of boot media e g floppy disks hard disks USB flash memory or even the network In case of booting from a disk and the decision which device 1s used if multiple ones are present In the system the BIOS tries to load the first sector from this device usually 512 byte into memory and executes this code by jumping to the first address of the loaded sector Since a normal bootloader does not fit into the maximum available size of 446 bytes see Figure this first sector contains the first stage of the bootloader and the code s job s solely to locate a further stage of the loader This is done traditionally by scanning through the partition table for an active flagged partition and loading a pre defined number of additional sectors from this partition Modern b
15. ns nin 11162 ns 2248 ns Figure 5 4 Latency of Lightweight RTAI in periodic mode 55 Chapter 5 Measurements 56 Chapter 6 Conclusions In this thesis a lightweight porting of the Real Time Application Interface API to a bare machine was presented The work started from an established Lin ux RTAI system and reduced the system to a minimal set of Linux core func tions which are strictly required by the original RTAI implementation There fore the Linux RTAI symbiosis was analyzed both at compile time and at run time Important dependencies were pointed out With the compiled knowledge and some design goals the actual implementation was started The core mod ules and some additional IPC modules of the RTAI distribution were statically merged with the original Linux kernel On the other hand subsystems which are usually included in Linux default distribution but now are unused or un wanted could be excluded successfully Finally some measurements were done to prove that the newly created system is an equal replacement of the traditional Linux RTAI compositions With its reduced memory footprint LRTAI is pre destined for systems with restricted resources The resulting LRTAI system is not yet optimal There are still some depen dencies of RTAT s scheduler implementation which still require access to some Linux code paths This is because the scheduler 15 capable of not only handling proper tasks but it is a
16. problem References to files which could be directly identified as not being used or necessary were dropped immediately All other files were reviewed by hand and the exported functions were replaced with a stub So 49 Chapter 4 Implementation details it was possible to compile the project at every time The goal was to restore the files later with the original code When all references to a file were elimi nated then it could be finally dropped from the makefile For files which export needed variables or functions it has to be determined if preprocessing instruc tions were used to exclude unused code or to extract the used code to a new file The later approach 1 not covered by the development s goals but used as a temporary solution The final result should be a patch for a specific kernel ver sion which excludes all unused code segments Such a patch could be applied easily to newer kernel source trees Another problem occurred while porting RTAT s configuration system Usu ally the kernel build system differentiates cleanly between flags being defined or not and integer values Not so for RTAI Many source files use the directives directly in statements which resulted in some compile errors after integrating the config system The reason for this was that Linux build system undefines non selected items whereas RTAT s system defines the items with a zero value So for some items a workaround was implemented in the rtai_config h which re
17. project was called Embedded RTLinux 17 In the meanwhile some drawbacks of the original SA RTL implementation occurred and this new approach tried to solve these problems The problems identified were 2 f this is was possible at all as both projects know of each other 3 Actually RTLinux GPL The word RTLinux always refers to RTLinux GPL in this work 16 2 6 Other related work The compatibility of SA RIL is limited to source level This means that the source code of the desired RTLinux application has to be available and it must be recompiled for use in SA RTL Binary only applications will not run in the system The maintainability of SA RTL s code base As already mentioned SA RTL was created by copying code from a specific version of RTLinux GPL This approach did not allow it to stay always synchronized with RTLinux upstream The result was complicated support and increased porting efforts with every new release of RTLinux The new Embedded RTLinux tries to solve these problems Instead of com pletely eliminating the Linux system it is just replaced with a thin software layer Thus it 1s possible to run an unmodified version of RTLinux on top of this thin layer achieving the desired binary compatibility 17 Chapter 2 State of the art 18 Chapter 3 Design The goal of this work s to create a new real time operating system kernel which s suitable for embedded systems with low resources Thi
18. some kind of preprocessor magic An extract of a possible implementation is given in Appendix 3 1 7 Console output via printk Normally a computer system has the possibility to display errors or other mes sages to the user Combined with the option for receiving user Input Linux defines the concept of a console like many other UNIX like operating systems do This console 1s simply a data structure with pointers to functions that will input or output the given data The default console usually uses the build in video graphics card for text output to a monitor and a directly attached key board for data input But it can alternatively use a serial port a line printer etc For LRTAI the full power of this concept 15 not used The main purpose is to get messages out to an attached display The possibility to input data via a keyboard has to be reimplemented later as a real time aware device driver For embedded devices it is not unusual to have no display attached as there is often no need for it For debugging purposes a serial console is often used instead But using a serial port 1s difficult on real time systems If using a polling mode the system has to actively wait for all status changes The other interrupt driven approach requires a working interrupt system of course and so output would not be possible if the interrupt system is not yet started As default LRTAI will assume that a VGA compatible video card 1s installed Such a card h
19. the requested memory size s greater than the s ze of a page the SLOB allocator calculates the so called order of the request This order is the loga rithmic size of the group of contiguous pages which will be requested from the memory manager below the SLOB system requested_bs PAGE SIZE 1 og PAGE SIZE The assigned block size arises out of assigned bs PAGE SIZE 2 If an application does not request accidental the calculated and assigned block size the so assigned block 1s always larger than the actually requested one and a trailing part of the block will be unused This space cannot be reclaimed by further memory requests unless the original application wishes to resize the block If the new size still fits into the already assigned block this can be easily 44 4 2 The nano SLOB memory allocator performed a major benefit of th s approach It depends largely on the used applications 1f this resizing support s really necessary The back of th s procedure 15 that the larger the request 15 the larger s the ass gned block The problem here is that the finally assigned block s ze has to be available as free memory not only the requested size This increases the probability of larger memory allocations to be rejected As an example A requested blocksize of 524289 Byte 1s assumed To satisfy the allocation a minimum of 129 pages must be free The SLOB allocator calculates an order of eight which would resu
20. the source code The motive is that such marked functions or data are solely used during the boot process This could be e g the initialization function of a driver After execution of the code it 1s not needed anymore could be dropped from memory and the resulting free space could be given to the memory man agement Especially on system with memory constraints such a feature is very use ful Since LRTAI is already stripped down to a minimum there are only few functions remaining which can be freed after usage Nevertheless this feature is implemented This is to support the users when they need or expect such behavior and to optimize the memory footprint of LRTAI 26 3 1 Taken over concepts 3 1 6 Memory management Every operation system needs to manage the available memory Usually this Is done with multiple layers or levels for simplicity On a standard Linux RTAI system there are up to three memory subsystems involved before a real time application receives its requested memory block 3 1 6 1 Bootmem memory allocator The closest level to the hardware 1 the memory page management where whole physical pages are marked as used or free Since a page 15 typically 4 KiB on A 32 it would be a waste when an application tries to allocate a few hundreds of bytes and 1s given a whole page So an additional level of memory allocation is introduced the SLAB or especially as replacement for embedded systems SLOB allocator This seco
21. 3 Design Since this allocator is quite complex a replacement exists This replacement is the so called SLOB system which can be chosen at compile time It was designed to be used on embedded systems which do not need the full power of the SLAB system As it provides SLAB s interface it replaces the traditional SLAB system silently The SLOB allocator serves as a base Since it requires the original page management by default it has to be adopted to use the bootmem allocator which will manage the physical free pages not solely while booting Addition ally some functions concerning cache management are dropped since these are mainly needed by device drivers and other kernel subsystems which will be dropped from LRTAI The remaining SLOB allocator solely supplies the kmalloc ksize and kfree functions It is only used during the boot process where various functions of the original Linux kernel requires dynamically allocated memory Another use case is when an RTAI module desires its own real time heap In a Linux RTAI system it would allocate a chunk of memory via kmalloc and passes this block to a RTAI function which converts the block into a real time aware heap So the existence of the SLOB layer is mainly for retaining compatibility with the described application case The alternative choice would have been to map the three above mentioned functions to the RTAT s counterparts But then major changes to the RTAI level would have been necessary
22. G_LRTAI fs_initcall heap_init endif static int _ exit heap_exit void Either use rtheap destroy or kfree never both x if heapaddr kfree heapaddr return 0 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 12 73 74 75 76 77 78 79 Appendix A Sample implementation for using a private heap Rest of module implementation static int __init myapp_init void int rv ifndef CONFIG_LRTAI if heap init printk myapp could not init return 1 endif if heapaddr amp amp rv rtheap_init amp heap heapaddr kfree heapaddr return 1 Rest of initialization printk myapp loaded n return 0 static void _ exit myapp_exit void Rest of destructor if heap exit printk myapp could not destroy heap Mn printk myapp unloaded n module_init myapp_init module_exit myapp_exit SIZE PAGE_SIZE printk myapp rtheap_init failed with d Nn Appendix Building the LRTAI kernel image The tarball with the source code of this work s stored on the attached data medium or can be obtained via Internet at 21 To build the LRTAI kernel Image extract the tarball to the usr src direc tory on your Linux workstation If you use this suggested location you do not ne
23. LRTAI project The reason for this 1s that the code 15 quite complex and provides a lot of functionality which is not required anymore For example the elimination of the user space functions which care about correct user space to kernel mode transition and back again 4AS they are not needed anymore The same applies to the ability to memory map files Additionally the memory management is strongly interwoven with the filesystem layer which is going to be dropped These dependencies result from performance demands which are put on a general purpose operating system like Linux However for a tight and small real time kernel this over fulfills the requirements Since a Working memory management is fundamental for an OS Linux tries to set it up as soon as possible while booting Before this setup process finishes it uses a boot time configuration which has less functionality and 1s limited to a total of 8 MiB RAM Less functionality hereby means that the page table are statically initialized with a linear mapping between the available memory and the existing address space However this configuration 15 for LRTAI sufficient and so it 1 not replaced with another memory management system but it 15 kept after the boot process Some code parts which relay on the mapping or unmapping of memory ranges have to be dropped in consequence Since this affects mainly the func tions which try to work around some hardware flaws this 1s of no further inter est F
24. _shm module This module was originally intended to only provide shared memory capabilities but by sharing the memory segments with unique identifier the behaviour of a global heap could easily be emulated For new applications the documentation suggests to solely use the methods pro vided by the shared memory module This is because of the symmetrical API which became available for user space tasks during the transition to support hard real time aware user space applications However as the shared memory module uses the kernels page re mapping infrastructure the functions better assumed as not affording real time per formance as stated in 14 Therefore for LRTAI the rtai_malloc will be pre ferred for providing memory services 2 2 5 Additional features The already presented modules only provides elementary functionality for real time applications Beside the functions which make the virtualized interrupt system available the RTAI distribution consists additionally of a few further modules which expand the described base system by some inter process com munication facilities The modules which are to be used can be chosen at compile time In detail this modules are non exhaustive list rtai bits With this module it 1 possible to use compound synchronization facili ties which base on logical AND OR operations executed on 32 bit vari ables This functionality 1s often referred as flag or event handling The differen
25. as a video memory which is mapped into the I O address range In text mode writing to the screen 1s simply copying the data from a buffer to the 3l Chapter 3 Design video memory no need for dispatching interrupts or other complex stuff This is used by the early vga console which 1s included in the default Linux system But it s not activated by default so the LRTAI version has to be modified On regular systems the early console 1s dropped as soon as the remaining kernel drivers are initialized so that these can overtake the management of the console Since there is only limited driver support for various hardware on LRTAI and the functionality of the early vga console 1 sufficient support for replacing it during boot process 1 not needed and 15 therefore omitted 3 1 8 Tracking time with jiffies Keeping track of time 15 one of the most critical tasks In every operating system The Linux kernel therefore uses a global variable jiffies which 15 a simple 64 bit counter It gets increased with every tick of the timer The time lag between two timer ticks depends on the target platform and a configuration value set at compile time On IA 32 it 1s traditionally 10 ms n newer kernel versions and or on newer systems 4 ms or even 1 ms is not unusual RTAI uses this global variable in some places when it was configured to use the Intel 8254 PIT as timer chip Since support for APICS is not yet included in LRTAI the preconfiguration ha
26. ce to semaphores is that signaling depends not only on a single value but on a bit combination rtai mbx In this module some mailbox related functions are implemented This could be used to pass messages of arbitrarily size between two processes rtai msg The module implements real time aware message handling functions 11 Chapter 2 State of the art rtai sem This module contains semaphore and spinlock implementations The RTAI user manual explains A semaphore can be used for communication and synchro nization among real time tasks A spinlock s an active wait synchronization mechanism useful for multiprocessors very short synchronization when it is more efficient to wait at a meeting point instead of being suspended and then reac tivated as by using semaphores to acquire ownership of any object 2 3 The Linux kernel build system The Linux kernel is distributed as a so called tarball which can be down loaded from The Linux Kernel Archives 8 After unpacking the build system of the kernel will assist to turn the source packages into something useful 1 e to compile the kernel Therefore the build system has to address several points First it is the face of the kernel sources which 15 seen by a user A person is considered as a user when he she solely wants to compile a recent kernel for his her Linux distri bution but not actually take a look into the kernel sources themselves Such a
27. ced with an accordingly patched kernel 5 2 Scheduling latencies To prove the thesis of chapter 3 that the scheduling latencies of the new LR TAI system should not be worse than that of an established Linux RTAI sys tem some measurements are done Therefore the latency measurement module found in tarball was slightly adopted to fit for both environments This was necessary as it 1s split into two parts a kernel mode task and a user space process While the kernel module calculates the actual data the user space counterpart reads the measured data from a FIFO This concept could not be used since in LRTAI the user space has gone Therefore the data 15 simply output by the kernel module via rt printk The mentioned module sets up a periodic task which calculates the differ ence between the expected and the actual activation time The default period of 100 Ls was used In each measurement 250 000 values were collected On the Linux RTAI system the system was stressed with I O and CPU load This could be achieved by running several flood pings and intensive hard disk ac cess For CPU utilization the tool cpuburn was used On the LRTAI system only CPU load could be generated For this the initialization routine finalizes with an endless loop and not with a call to cpu_idle The results are plotted in Figures 5 1 5 4 Figure shows the measured latencies on the Linux RTAI system using the oneshot timer mode While the major part of th
28. chael J Karels Design of a General Pur pose Memory Allocator for the 4 3BSD UNIX Kernel In Proceedings of the San Francisco USENIX Conference pp 295 303 June 1998 ttp docs FreeBSD org 44doc papers kernmalloc df ge ttps www rtai org index php module ocuments amp JAS DocumentManager op viewDocument amp JAS Document id 44 June 21 2007 as 4 lt o 0 C 4 o ar p o ga c N N lt gt S 3 lt Q S Peter Miller Recursive Make Considered Harmful AUUGN Journal of AUUG Inc 19 1 pp 14 25 ttp aegis sourceforge net auug97 pdf D References 16 Vicente Esteve Ismael Ripoll and Alfons Crespo Stand Alone RTLinux GPL Universidad Politcnica de Valencia October 20 2003 ttp www rtlinux gpl org vesteve docs ws2003 df O gt 17 Miguel Masmano Apolinar Gonz lez Ismael Ripoll and Alfons Crespo Embedded RTLinux A New Stand Alone RTLinux Approach Eighth Real T me Linux Workshop at Lanzhou University SISE China October 2006 tp ftp realtimelinuxfoundation org pub events rtlws 2006 paper 07 pdf x 18 Jean loup Gailly and Mark Adler zlib Home Site ttp www zlib net gt O EN NO c I 19 Intel Corporation Intel Pentium Processor Invalid Instruction Erratum Overview ttp support intel com support
29. count DEFINE RESCHED COUNT redo Spin lock amp dcache lock Spin lock amp dcache lock for for if TEST RESCHED COUNT 100 RESCHED COUNT 1 if conditional schedule needed Spin unlock amp dcache lock unconditional schedule t goto redo prolonged work x prolonged work x spin_unlock amp dcache_lock spin_unlock amp dcache_lock M OO CQ U Ne e nm O CN N KF Figure 2 1 Introduction of explicit preemption point in fs dcache c The most popular example of such an explicit preemption point is shown in Figure One may notice that the test for the rescheduling condition is enveloped by a test of the iteration progress of the loop This 1 necessary to avoid the so called live locks which may occur on heavy system load Then the rescheduling condition would almost be true resulting in a loop which is solely interrupted but does not do any work With the test of the iteration count at least a minimal progress of the intended work is assured Compared to the former one this patch seems to achieve better results as shown in 7 too Even though the concept of the low latency patch 15 s mple the main work has to be done during implementation Firstly potentially long term running code blocks have to be identified and then it has to be examined if an explicit preemption point could b
30. defines the flags accordingly However for a cleaner implementation this should be fixed in RTAT s upstream 50 Chapter 5 Measurements 5 1 Test system As a test system a somewhat ancient PC got into action Since LRTAI still has limited peripheral support and no access to filesystems is available a method had to be found to transfer the measured data from LRTAI to a host system As a working solution the serial console was used It had to be activated via a kernel command line parameter e g earlyprintk ttySO On the host system the input was redirected into a file from where the data was extracted later Therefore the measured raw data was prefixed with a short tag to allow easier distinction from normal kernel messages Due to the lack of a present serial port on newer systems the mentioned ancient PC system was used How ever in the measurements the absolute values are of minor interest the relative ones have to be interpreted The used system consists of the following parameters AMD AMD K6 CPU running at 200 MHz 128 MiB RAM installed but only 8 MiB used by LRTAI Linux kernel version 2 6 17 ADEOS IPIPE version 1 3 08 e RTAI version 3 4 Linux timer interrupt 1 running at 100 Hz 51 Chapter 5 Measurements These parameters are kept constant for all measurements on a LRTAI system and a normal Linux RTAI installation For the later a Debian Sarge system was chosen as a base where the kernel was repla
31. definition From my point of view the resulting combination does not add up to independently executable stances apart from the fact that the original Linux kernel will do without the IPIPE system However the ADEOS Adaptive Domain Environment for Op erating Systems project from which the IPIPE system originates refers to the ADEOS nanokernel beneath the Linux kernel 12 In fact it neither man ages other resources than the interrupts nor does it provide any inter domain communication facilities The basic idea of the ADEOS interrupt management consists of virtualizing all available interrupt sources and introducing some additional virtual inter rupts This means that all hardware interrupts are caught by the ADEOS layer and translated into interrupt events Therefore ADEOS groups the hardware interrupt access into the so called domains of different and fixed priority The code which is actually inserted n the Linux code base modifies Linux original interrupt management to handle these new interrupts events The Linux system 1s therefore migrated into the root domain which 1 able to open up further ADEOS domains This is used by RTAT s hardware adaption layer module rtai hal which spans a second domain during initialization RTAI do main s priority is higher than that of the root domain The priority of the domains are used when dispatching a hardware interrupt source As every domain is allowed to register an interrupt handle
32. e g could be triggered from an active I O device while a process 1s running in kernel mode the interrupt handler 15 delayed un til the running process finishes its work One sees that the interrupt response time 1s subject to large fluctuations which 15 not useable in real time operating systems During the further kernel development on version 2 2 and 2 4 the big kernel lock was increasingly replaced with finer grained localized locks of particular critical sections This improved the response times slightly but the kernel could Chapter 2 State of the art still not be regarded as real time aware The lack of real time support has some simple reasons Linus Torvalds the original author and maintainer of the Linux kernel defied adding real time rel evant patches for a long time following the idea of high stability and throughput of traditional UNIX kernels But the then current situation was not satisfying for many Linux users So two independent works started to resolve the problem The results of these works were some patches which could be applied to the kernel s sources tree As they were not included in the kernel s upstream both were maintained out side the kernel tree for a long time Both patches which actually are patch sets are shortly presented in the following two subsections 2 1 2 The Preemption Patches The embedded Linux vendor MontaVista Software Inc was one of the ac tivists After publishing in the year 2000 the
33. e configuration overhead at runtime and makes this method unfavourable Also this initialization procedure has a further drawback It requests the memory from the Linux memory management in blocks of extentsize bytes As the default kmalloc implementation poses an upper limit of 128 KiB for each request RTAI uses this limit which is neither configurable at compile time without direct modification of the sources of course nor at run time As by definition all extents are of the same size for small systems this extent size could be too large and could result in memory blocks which remain unusable For LRTAI this initialization code has to be rewritten to eliminate this two drawbacks or one or more new initialization strategy should be implemented The later approach was chosen to provide the user the highest compatibility but 29 Chapter 3 Design also to fit optimally to the new environment The new implementation lets the user to choose at compile which allocation strategies are compiled in and at runtime which one is actually taken Actually two new algorithms are added The first is called greedy as it tries to allocate as much memory as possible from the bootmem allocator Like the original approach this 1s done in smaller or larger extents but the extent size could also be given dynamically The method has still the drawback that memory requests which are larger than one extent cannot be satisfied as 5 allocation function ca
34. e dependent low level functions or for performance reasons is an assembler used To pre serve readability the sources are split over multiple files so that all parts have to be merged together finally This step is done by the linker The linker output does usually not only consist of native processing instructions but is rather a meta format containing additional information which is needed on the target OS to load the application For the Linux kernel the Executable and Linking 2 Chapter 3 Design Format ELF is used as it 1s the default binary format for applications on most UNIX based operation systems and on Linux itself An ELF file can consist of several sections mainly a text code section a data and a so called BSS Block Started by Symbol section Additional sec tions may be included e g symbols for debugging or comments The linker creates an ELF file upon the data found in the used linker script which de scribes how the sections of the input files should be mapped into the output file and how the memory layout of the application looks like Since the Linux kernel is not a common application this meta information is not needed and so it s discarded in the further build process However the layout of the sections is kept in the final binary To run the Linux kernel on the target machine the 1mage has to be loaded into the RAM and then control needs to be passed On a PC architecture the boot process has many histor
35. e information on what should be replaced and where and by what Using a patch instead of distributing modified copies of the original work has some advantages First though the patch may carry significant changes the modifications to the source code are usually small So resources are saved during transmission and while archiving Secondly patches tend to be easy to maintain For example when reducing a function to a stub by inserting prepro cessor directives only the header and the tail of the implementation has to be modified the actual implementation does not matter A patch which consists only of the modification and a few context lines would also apply to a function where the inner implementation has changed completely Thus a patch can often be used with subsequent software releases too An adaption is only nec essary where changes directly conflict or cases where the original changed significantly 15 Chapter 2 State of the art 2 6 Other related work As already mentioned RTAI was only one approach of enhancing Linux with real time capabilities The most competitive solution was RTLinux which was also mentioned above Originally developed at the university of Socorro New Mexico USA the development was soon migrated to a newly launched com pany As a result the code was available as a proprietary commercial product and a free open source variant The later Is also known as RTLinux Free or more specifically as RTLinux GPL a
36. e safely inserted The official inclusion of this patch set was delayed for a long time too Finally they got integrated into kernel version 2 6 11 2 1 4 Final approach full preemptibility The two patch sets which were presented above improve both the kernel re sponse times when applied independently It was also possible to apply both patches in common which is actually true for kernel versions greater than 2 6 11 Chapter 2 State of the art However the kernel can not yet be called an RTOS kernel as some important RTOS specific features e g priority inheritance are still missing Also the kernel is still not fully preemptible as interrupt service routines were not yet preemptible It was Ingo Moln r again who presented a solution This new patch set is called preempt rt standing for real time preemption patches subset of this patch set was already integrated into kernel version 2 6 18 However it is still under development The final goal of this work 15 a full preemptible kernel and therefore a fully deterministic scheduling behavior This shows that major attributes and fea tures of a RTOS are slightly integrated into the Linux kernel s upstream So it could be expected that the vanilla kernel will play an increasing role in the real time market 2 2 The Real Time Application Interface 2 2 1 Principles The Real Time Application Interface RTAI is not a standalone RTOS It is rather one of the efforts to enha
37. e values is around 20000 ns the maximum measured latency is with 44419 ns more than twice as long In Figure 5 2 which illustrates the same measurement an LRTAI system it can be noticed that the average latency has minimally improved in comparison to the Linux RTAI system This 1s due to the fact that on the LRTAI system no further interrupts need to be processed which is the case in the Linux RTAI system Also the values show a lower jitter The remaining Figures 5 345 4 show the measured values using the periodic mode of the schedulers Here too the latency of the LRTAI is minimally better than the one of the Linux RTAI system The jitter could also be improved The 32 5 3 Image size and memory footprint negative times prove that the scheduler does some kind of calibration trying to minimize the jitter of real time tasks However in some cases the time delays are less than expected and the real time task 1s activated before the requested time This behavior can be optimized by presetting the calibration manually via the kernel command line or by directly compiling in the target systems values The result of these measurements are that the LRTAI system behaves nearly like a traditional Linux RTAI system This means that its efficiency 1s quite as good and the system can therefore be used as an alternative solution 5 3 Image size and memory footprint The values listed in this section are only for completeness A comparison be twe
38. ed macros are redefined so that every occurrence adds an entry to a so called initcall table This table is simply list of pointers to initialization func tions These are grouped by functionality or precedence into separate subsec tions Currently there are seven predefined subsections namely initcall postcore initcall arch initcall subsys initcall fs initcall device initcall and late initcall During boot process the initcall table is processed in order start ing with the core initcalls Ordering inside the subsections 1s determined by link order 1 e a module which is referred to later the makefiles and there fore linked in later is also initialized later Even though many original subsystems of Linux are dropped for LRTAI and hence the remaining ones could be initialized by hand this concept 15 overtaken to LRTAI This 1 to achieve source code compatibility to existing RTAI modules which usually make use of the described macros Since the module support is dropped for this first LRTAI version the macros expands to the initcall table implementation as described More exactly the usually used module init translates to a device initcall That will later be of interest when the memory allocations are discussed 3 1 5 Initialization memory freeing In Figure an area in vmlinux is highlighted In this area the linker places initialization data and functions which are explicitly marked by the authors in
39. ed parts away The existing code has to be reviewed also to detect dependencies on functions and global variables But this differs from the first approach in so far as it tries to reuse as much as possible the existing code and base system Particularly the design of the taken over sub systems 15 left unchanged or only minimally adapted In this respect this approach should guarantee or improve the acceptance in comparison to the first one At first sight it looks easy to discover which parts of the code are needed and which ones can be dropped since the RTAI code 15 very modular and well structured The core RTAI modules mutually depends only weakly and mainly in a linear fashion 1 e one module uses only services of the other one and not vice versa However the Linux part has to be analysed as well And this code 15 not as well structured as it could and should be When deselecting e g the sysfs feature via the kernel config system at compile time there are still many code references to it and several data structures are included which are unused in 20 3 1 Taken over concepts the end This 1s because the kernel is not fully designed for systems with low resources and at a normal system a few bytes of code and data more or less do not matter in the memory footprint For this reason it is necessary to review the whole Linux sources moreover there are many features and subsystems which cannot be deselected by the original configuration
40. ed to update the included makefiles otherwise you have to adopt the vari ables KERNELSRC and or KERNELOUTPUT in the build directory s top level Makefile After this just changing into the build directory usr src Irtai build per recommendation and running make builds the image If changes to the LRTAI system are needed a make menuconfig step gives a graphical user interface for configuration Changes in the Linux kernel orig inated part are not yet recommended in RTAI s part some presets can be changed Also IPC modules can be chosen It is assumed that the build is done as a user root It was not tested but it should be possible to run this as an unprivileged user Use appropriated tools like fakeroot if necessary extract tarball to usr src buildsys tar C usr src xvjtf lrtai 0 1 tar bz2 configure LRTAI neither necessary nor recommended for the initial release buildsys cd usr src lrtai 0 1 build amp amp make menuconfig build the zImage buildsys cd usr src lrtai 0 1 build amp amp make Figure B 1 Transcript of building the LRTAI kernel image Appendix Building the LRTAI kernel image IV Appendix GnuPG signature of the LRTAI tarball Version GnuPG v1 4 6 GNU Linux iD8DBOBGeXU9KGO9ZzVRhqoRAL3GAJ9r3BhOkFt5Wj dloUoZG80KbZ2ggCZATV1 OJrWAklddt40AQZpL7qlMyc wbIg Appendix GnuPG signature of the LRTAI tarball VI Appendix Copyright notice For files of the
41. emory layout On systems with low memory it 1s not only essential to know how much mem 15 available but also how it is organized and used 1 e which constraints are given by the underlying operating system and or the hardware architecture itself On a PC system for example there is a memory hole which can not be used as normal RAM but s used for accessing the ISA bus and the sys tem s BIOS This hole starts at address 0x000A0000 640 KiB and ends at 0x00100000 1 MiB a VGA compatible video adapter s video memory could be addressed starting from 0 000 8000 for example When a system has more than 1 MiB of RAM installed this memory hole therefore divides the RAM into two memory areas While this 1 not a problem per se this placing in the middle of the available address space can be subop timal under certain conditions e g when searching a contiguous free memory block However this cannot be changed as it s an architectural and histori cal limitation The remaining option is to exploit this restriction This is what Linux tries to do in its original implementation As the kernel 1mage has to be placed somewhere in memory the default configuration 15 to place it starting at 0x00100000 As a result the kernel image and the memory hole forms a contiguous reserved memory block so the kernel image s code section which 46 4 3 Memory layout will usually resist statically In memory does not make the situation worse by op
42. en a Linux RTAI and a LRTAI would not be meaningful because of the oppositional design goals The kernel image size of the generated z mage 1 about 122 KiB The cor responding memory footprint is about 370 KiB thus it 1s possible to run the kernel on systems with less than 1 MiB of RAM installed With continuation of the work it should be possible to lower this bound further 53 Chapter 5 Measurements nunber of neasurenents nunber of neasurenents 54 98888 Linux RTAL 80000 0008 66668 28888 46666 39008 20008 16666 B 16666 15666 20006 25088 30088 33008 46666 45666 latency ns min 18895 ns 44419 ns Figure 5 1 Latency of Linux RTAI in oneshot mode 128868 Lightweight RTAI mamam 186888 0000 60000 46666 20000 B8 G88 16666 12006 14866 16008 13666 280088 22008 24088 26008 latency ns min 9219 ns 24385 ns Figure 5 2 Latency of Lightweight RTAI In oneshot mode number of neasurenents number of neasurenents 5 3 Image size and memory footprint 45000 Linux RTAL EE 46668 35808 38808 25808 zB0HBB8 15888 16866 5888 2508H 20008 1588H 19008 5088 B 5866 16666 15666 latency ns min 21219 ns 19847 ns Figure 5 3 Latency of Linux RTAI in periodic mode 50008 tueight u 56666 46666 20008 18888 B 12000 180888 B 8H AHHH 2004 B8 2008 4666 latency
43. en though the chosen approach of this work 1 straightforward some prob lems appeared when implementing and these had to be solved As described earlier the resulting LRTAI system does not require many of the features drivers or subsystems which come with Linux by default To drop 48 4 4 Problems them from the project there were two possibilities The first naive option is to physically delete the concerned files and directories from the filesystem But this approach failed due to the static references In the makefiles which were not updated It resulted in a source tree which did not even build an original Linux kernel at all which was not considered as a good starting point A further variant was to solely drop the addressed references in the make files This would result in reviewing every single makefile around 500 which are potential candidates for the IA 32 architecture It should be remembered that one of the goals was to minimize the needed changes to the original Linux source tree to retain maintainability and to ease the porting to a newer kernel version if needed So this variant was also rejected to a large extent and only some hand picked makefiles were chosen as pointed out later Since the most features can be individually selected or deselected in the kernels configuration step this approach was the preferred one as it 1s already built in and well supported So a minimal configuration was created which excludes almost every
44. eneral purpose operating system GPOS and does not yet deserve being called an RTOS However using Linux as a starting point for a real time environment does make sense because of the code maturity and support for the most common hardware Basically there exist two strategies to enhance the Linux kernel with real time capabilities Modifying the Linux kernel itself to provide the wanted determinism and predictability For historical reasons this approach was developed in par allel to the kernel as some of the original design goals were oppositional to what would be needed by a real time operating system But today Chapter 1 Introduction there s an ongoing development to integrate native real time support into the Linux as shown in the following paragraphs Using an additional real time kernel which encloses bases the standard Linux kernel While this concept seems to be very similar to using a micro or nano kernel driven approach t differs n so far as the added real time part could be and usually 1 interwoven closely with the stan dard kernel Also in a micro or nano kernel based system only the core components run in kernel mode whereas the non essential services in this domain then called servers resist in user space When the development on Linux started it was solely designed to run on In tel s 386 or 486 CPUs And it tried to use all available features of the CPU particularly paging and the 32 bit protected mode The
45. ening a second hole Because of this an original Linux system requires at least 2 MiB of phys ical RAM installed or booting is denied before decompressing the kernel im age into memory This limitation makes only sense if the final location of the kernel image 16 kept To potentially allow embedded systems with less than 2 MiB of RAM the memory size check 15 disabled relying on the developer s involvement This is to carefully choose the kernel configuration value CON FIG PHYSICAL START which contains the physical starting address of the uncompressed kernel image Leaving this value on its default value 0 100000 locates the 1mage starting at the first mebibyte Of course the target system should have sufficient RAM installed to house the uncompressed image If the target device has only one mebibyte or even less of RAM the value must be de creased But the new starting address has to be chosen carefully As the image is compressed by default both the uncompressed image and the compressed one must fit into the available memory as the decompression mechanism does not support in place decompression On systems with an extreme low count of RAM the abandonment of the image compression should be considered cf section 3 1 2 Both approaches that 15 the use of compression and the use of a non compressed image have in common that the physical start address 15 a hard coded value in the kernel 1mage So the kernel image requires to be placed at t
46. equires a small decompression stub in the final image Of course the com pression can only be justified when the added overhead plus the compressed part is smaller than the uncompressed piece of code As the zLib implementation is not an in place algorithm the target system must have enough memory to hold both the compressed and the uncompressed images On systems with extreme low resources this could be a problem as described later in section 4 3 This could be a potential argument against using compression at all however it remains for the developer to make this decision and to choose the preferred or necessary variant Today there are already some bootloaders which natively support the kernel s compression Then the bootloader itself decompresses the kernel image to its final location usually by reading the data from a flash memory directly so that it is not necessary to have both images in RAM Additionally when using compression the booting time of the system 15 af fected While a smaller image results loading less blocks g from a disk and should speedup therefore the boot process a low performance CPU could spend more time in decompressing the code On modern CPUs the decom pression should be a negligible factor however the time needed for booting the system can carry weight for an embedded system Though this time depends on various conditions it is still possible to measure it for a specific system as it should remain consta
47. h its own implementation of a serial port device driver which is real time aware other original Linux drivers have to be audited before they could be used In LRTAI many parts of the infrastructure which original device drivers are used to found are dropped So they could not be taken over directly and a code review is needed But since LRTAI should only provide a framework which can be adapted to special needs by its future users such driver examinations are assumed to be done by the users Only the drivers for the interrupt timer circuit are included by LRTAI With the omission of the remaining device driver and since the filesystem support is dropped the infrastructure and the need for the block and character devices 1s lost too These special filesystem nodes enable user space applica tions and system tools to communicate with drivers 1 e to load and store data and or setting configuration values As can be seen from the task formulation the Linux subsystem should be eliminated from the project However an exact definition of the term was not given so the most logical one is assumed It 1s supposed that the Linux subsys tem covers all kernel parts which are unconditionally needed for spanning the user space That means in particular that the Linux system calls syscalls are no longer required since they are solely used by user space applications Since the kernel subsystems are located the same address space they can call
48. he address or else a recompilation with a changed configuration value 1s needed This will be at least true until kernel version 2 6 22 1s released In this version experimental support for relocating the kernel at runtime will be introduced by keeping the necessary relocation information in the final 1mage So a recompilation will not be needed anymore but a tiny relocation function adopts the offset addresses at runtime However the already available docu mentation states that this functionality increases the final image size by around 10 percent So it depends again on the developer s choice and or the target system resources if the use of this new feature 1s favourable Obviously the actual memory layout depends on a multiple of factors The most important one is the actual installed amount of RAM which is physically present in the system As pointed out above the information as to whether more than 2 MiB are available or not should be known beforehand at compile The current LRTAI implementation bases on kernel version 2 6 17 47 Chapter 4 Implementation details BIOS provided physical RAM map BIOS e820 BIOS e820 BIOS e820 BIOS 6520 BIOS e820 BIOS e820 BIOS e820 0000000000000000 O0000000000916G00 00000000000e0000 0000000000100000 000000000053 0000 000000000053 f000 00000000fffc0000 000000000009fc00 00000000000 0000 0000000000100000 000000000053 0000 00000000005 f000 0000000000400000 0000000100000000
49. ical vices the important ones are described later in detail In this context 1t 1 sufficient to mention that the Linux kernel was traditionally prepended by a small boot sector and a loader which puts the remaining parts of the kernel into memory In Figure a simplified overview 15 given of the various files generated during the build process and their binary layouts for the A 32 architecture The image layout mainly affects how bootloaders deal with the image Nowa days there exist lots of bootloaders for various environments Many of them have built in support for the Linux kernel This 1s necessary because the boot loader is able to pass some additional information to the kernel during the boot process As this s also a wanted feature of the new LRTAI system cf section 3 1 3 the backup strategy implemented in nearly every bootloader could not be used This strategy of handling unknown boot objects involves loading the whole image into memory and jumping to the first address where the image was loaded Booting this way no information could be passed to the kernel Actually the kernel would not boot at all since the included boot sector prints only a notice that booting without a loader is not supported anymore For reaching the mentioned design goal the bootloaders ought to be ex panded to support the new LRTAI kernels Even though many of the poten tially used bootloaders are open source and could be adopted it wou
50. iency While in a standard desktop system an economic usage of the available RAM 15 a minor issue nowadays a desktop has plenty of RAM installed and other factors e g inter active response time emerge an embedded system s OS should not allow the chance to leave resources lying dormant In a Linux system most memory requests are handled by the SLAB or SLOB system As already mentioned in section 1 6 2 the SLOB system was chosen for LRTAI because it is much simpler than the SLAB system but it provides the same API In general these allocator systems were primarily developed to prevent memory fragmentation as a result of frequent and small memory allo cations Small means in this context that the requested memory size 1 usually less than the physical page size However also larger requests are handled by 43 Chapter 4 Implementation details Requested blocksize Required SLOB allocation Worst case pages Order Pages waste I KiB 2 1 2 0 2KiB IB 3 2 4 1 16KiB IB 5 3 8 3 32 KiB IB 9 4 16 7 64 IB 17 5 32 15 128 IB 33 6 64 3 256 KIB IB 65 7 128 63 512 IB 129 9 256 127 I MiB 257 9 512 23 2MiB IB 513 10 1024 511 4MiB IB 1025 11 2048 1023 8 IB 2049 12 4096 2047 Table 4 1 Exemplary worst case blocksizes of memory requests which max imizes the wasted page count of the allocated block for a part cular order f Linux default SLOB allocator would be used these systems If
51. ir work was quickly picked up by the Linux community and consists of the actual preemption patch and a real time scheduler Usually this work is referred to as the preemption patches which are maintained by Robert Love in the meantime and can be obtained from his kernel org space 6 The work tries to minimize the time lag between an incoming event e g an interrupt and the next invocation of the scheduler To achieve this some locking primitives are modified together with some slight adaptation of the interrupt handlers In the result the scheduler is called more often and can faster react to a pending rescheduling request In 7 some measurements are done which confirm the improved scheduler latency Even though the patches are relatively small and good to maintain the inclu sion into the Linux kernel s upstream was delayed until version 2 5 4 in 2002 2 1 3 The Low Latency Patches The second approach which was presented by Ingo Molnar in the year 2001 tries to attack the response time problem from another direction He examined the existing source code looking for long time running uninterruptible code blocks The goal was to break this blocks into smaller chunks by explicit calls to the scheduler after some amount of work is done The original task would be resumed at the interrupted position when the scheduler comes back later 2 1 Linux kernel s nat ve real time support void prune_dcache int count void prune_dcache int
52. kernel head S As already mentioned start kernel 15 a high level non architecture depen dent initialization function However its first step 15 to call a further high level but architecture variable procedure by name setup arch In this function a data structure containing various information about the CPU 15 filled This structure 15 used at multiple places all over the code as it holds among others the list of features supported by the CPU Further on setup arch prints the memory map provided by the BIOS preprocesses early command line param eters and finally setups the main memory At this stage the bootmem allocator is also setup Back in start kernel the remaining part of the command line is processed and the trap and interrupt system is setup After initializing the time subsystem which solely increases the jiffies counter the IPIPE root domain 1s opened and the interrupt subsystem 1 enabled The start kernel function is marked as __init function cf section 1 5 This means that the code would be freed after the initialization completes So its last call is to invoke a init function namely rest_init which finalizes the kernel startup Here the already mentioned init calls are processed and the init memory section 15 freed After that the CPU enters the idle loop The RTAI domain s initialization 15 done via the initcall mechanism As the RTAI code was originally implemented as kernel module the sources
53. ld be easier to use the existing support for Linux kernel and the way through which param eters are passed This results in keeping the major image layout for LRTAI so that bootloaders would detect a standard Linux kernel This way all familiar bootloaders would be able to bootstrap the LRTAI system as they can use their 22 3 1 Taken over concepts execption kernel symbol 17 M initcall table table data inittext init data T bss text strip objcopy raw binary gzip gzip compressed data included via special data section decompressor stub gzip compressed data strip objcopy raw binary attached via helper utility boot sector loader compressed code data non compressed text data init sections compressed text data Figure 3 1 Simplified overview of vital file layouts on IA 32 23 Chapter 3 Design existing knowledge to determine the entry point 3 1 2 Image compression As the Image size of the Linux kernel increased continuously over time by added features some size constraints notably those of IA 32 hit and limited the static core kernel Compression of the image was chosen as the way out The used compression algorithm is zl b by Jean loup Gailly and Mark Adler which was originally intended for compressing pictures Using image compression the kernel should be able to decompress itself and this r
54. lso able to steal and return tasks to Linux scheduler Therefore Linux internal implementations are called directly to achieve the desired functionality This could be improved by continued work In spite of the code which 15 still required by the scheduler and thus still enlarges the whole system the already achieved image size and the size of the memory footprint proves the feasibility of the project and justifies its continu ation Also a continued work could further reduce the changes introduced in the build system Likewise new features could be implemented For example support for APICs could be introduced which would be the base for SMP 57 Chapter 6 Conclusions 58 O oo co tA FW L rn Appendix Sample implementation for using a private heap Listing A 1 properheap c include lt linux kernel h gt include lt linux module h gt include lt rtai h gt include lt rtai_config h gt include lt rtai_malloc h gt MODULE DESCRIPTION Sample application which 11 a private heap MODULE AUTHOR Michael Heimpold _ lt michael heimpold s2000 tu chemnitz de gt MODULE_LICENSE GPLv2 define HEAP_SIZE 512 x 1024 rtheap_t heap void xheapaddr NULL static int _ init heap_init void if heapaddr kmalloc HEAP SIZE KERNEL 1 printk myapp kmalloc failed n return 1 printk myapp heap inited n return 0 ifdef CONFI
55. lt in an actual memory allocation of 256 pages If the count of free pages 1s between 129 and 255 the allocation would fail though it could be successfully performed If further a successful allocation 1s assumed and that the application does not try to resize the block later 127 pages are wasted Of course this is one of the worst case scenarios Table 4 1 lists for each order an exemplary worst case blocksize resulting in a maximum of wasted pages of the allocated block In an LRTAI system there are only a few memory allocations which accesses the SLOB system directly The usual case 1s that applications acquire their memory by calling the corresponding RTAI functions which then again call the SLOB system However as the RTAI system acts as a proxy it usually requests blocks from the SLOB allocator whose sizes are multiples of a page 517 For this reason the support for resizing an already assigned memory area Is only a minor Issue There again the potential waste of memory should be minimized For this the SLOB allocator was modified to drop the concept of acquiring blocks by their orders Actually the order 1s simply redefined to the minimal count of pages which are necessary to satisfy the requested block Hus PAGE SIZE 1 order PAGE_SIZE While the functionality of resizing a block s still available it is now de generated so that a resize request could increase the block size at most by PAGE SIZE 1 bytes Ho
56. m presented in 13 However the allocator could not simply distribute memory As the RTAI subsystem 15 usually loaded after the Linux system is already up and running the Linux memory management has already grabbed all available memory Therefore RTAI must firstly request some chunks of free memory via Linux API This is done for example when the rtai_malloc module is loaded It re quests a configurable amount of memory which forms a global heap and can be used later in a time bounded fashion as described To avoid any further negative influence of Linux management the allocated pages are usually locked which means that they are not considered for being swapped out to disk This applies at least for the user space parts of a real time application The kernel mode real time tasks uses either the kmalloc and or vmalloc kernel functions to preacquire some memory which 15 later converted into a real time aware memory heap or they use the memory API of RTAI directly In the second case the global heap 15 used actually But in both cases Linux kernel memory 1s used so there is no need to lock these pages to prevent Linux from interfering as kernel memory is never swapped to disk However the pages are still marked as reserved 10 2 2 The Real Time Application Interface In the current RTAI distribution the rtai_malloc module 1s of minor impor tance only The reason s that a second implementation for a global heap s available in the rtai
57. means that is 1s loaded by the insmod command line tool This tools open the file and copies the content to a memory location in the user space After that a system call 1s invoked to insert the module in kernel space and to start the execution of the new code if the module provides a defined entry point While running this initialization code the module can fork off new real time processes which are subsequently managed by the RTAI domain Thus it appears that the RTAI API starts at process level there are no API functions which deal with loading or storing data on disks etc Thus in LRTAI there 15 no need for such functionality too and the code concerned can be dropped from the project With dropping filesystem support the ability to dynamically insert modules at runtime is also lost since there 1s no source anymore which could hold the modules object code A possible solution would be to feed a module via serial port to the system Since a real time aware device driver for the serial port exists in RTAI a serial protocol could be established between a host system and the embedded device to transfer object code to the targets RAM After the transfer the existing routines of RTAI could be invoked to initialize the new code and to start new processes as requested by the modules initialization procedures As the main focus of this work is to get a standalone RTAI system running the ability to dynamically load modules is considered as a feature tha
58. nce the Linux kernel with hard real time capa bilities RTAI was developed in Italy in the Dipartimento di Ingegneria Aerospaziale at Politecnico di Milano The project evolved from former real time experi ences of the group around professor Paolo Mantegazza Their previous work was called PCDOS DIAPM RTOS standing for an RTOS running in 16 bit real mode of Intel compatible standard PCs For the transition to 32 bit pro tected mode the group evaluated several approaches and systems which should provide a new basis for the 32 bit code base Around the same time a patch for the Linux kernel was presented which added elementary support for real time tasks This RTLinux patch was devel oped at the New Mexico Institute of Mining and Technology by Victor Yo daiken and Michael Barabanov 9 Using this patch Mantegazza and his team discovered that an own imple mentation was needed due to bad performance As a reason for this bad perfor mance the so called shot mode was identified In middle of April 1999 l Vanilla kernels are the official Linux kernels released from 8 2 2 The Real Time Application Interface User space tasks RTAI kernel tasks Kernel threads Scheduler Eur I IPC Linux kernel RTAI HAL Root domain RTAI domain ADEOS IPIPE Hardware CPU Peripherals Memory Figure 2 2 Stacked layers In
59. nd is a community supported project It was already mentioned that RTAI was influenced by the work which 15 also the base for the project So it does not surprise that the same kernel dualism approach 15 used here too However both projects were developed indepen dently which in the meanwhile resulted 1n drifting apart This can be verified by the different application programming interfaces of both projects In the year 2003 a work similar to this thesis was presented for the RTLinux GPL project It was published by the group around Alfons Crespo at the Uni versidad Politcnica de Valencia Spain 16 The work presented a porting of RTLinux a bare machine called Stand Alone RTLinux GPL SA RTL Here too the intention was to create a real time kernel which is suitable for systems with low resources The work was done by an incremental code migration from the RTLinux tree to the SA RTL code base Though many lines of code were directly transferred the original Linux identity however was completely eliminated from the new system The final system provides solely the RTLinux API Additionally a new multi level memory protection scheme was introduced With that it shall be possible to protect not only the core RTLinux executive but also the mutual real time tasks The implementation of this protection scheme is achieved with very low overhead In autumn 2006 the successor of the previous work was presented by almost the same group The new
60. nd stage s described in the following subsection Since the original page management of Linux 1s quite complex and strongly interwoven with the remaining memory management and therefore the file and file system handling code the decision was to replace and simplify the whole system Fortunately the original Linux comes with an alternate page management system which was designed to be used solely during booting The bootmem allocator This 1s a small bitmap based allocator which will completely satisfy our requirements for lowest level allocations Originally the code 1s marked to be freed after initialization completes see above so it requires some changes to fit for the new LRTAI system Also the code assumes that 1s running solely on one CPU as SMP support is normally not yet enabled at the stage when the bootmem allocator 15 used To prepare LRTAI for SMP n the first implementation SMP support will not yet be included the allocator 1s also enveloped with spinlocks to prevent con current modifications of the internal data structures by multiple threads tasks When compiling for uniprocessor systems the kernel s macro magic will opti mise the calls to simple interrupt preventing implementations so there will be no overhead introduced 3 1 6 2 The Nano SLOB allocator The second level of memory management is normally done by the SLAB al locator originally developed by Jeff Bonwick for the SunOS 5 4 kernel 20 24 Chapter
61. nnot split the request over multiple extents A further algorithm should be provided to support such large allocations It 1s called largest as it simply allocates the largest available free block in one step It is not divided into smaller extents but forms only one extent The special case where multiple large blocks of the same size are available is not handled even though these could be treated as several extents It could be implemented easily such functionality 1s needed As mentioned above the user can choose between these two new algorithms and the traditional one using the kernel command line This is also used to pass the parameters e g the extent size to the greedy algorithm As a default the greedy implementation is chosen for LRTAI with an extent size of 128 KiB 3 1 6 4 Private heaps of real time applications RTAI provides applications the possibility to use not only global heap but also to request their own memory block which 1s converted into a private heap This is useful e g when an application exactly knows about its memory consumption and does not want to interfere with other applications The normal process of registering such a private heap 1 to allocate a mem ory block of the desired size from Linux SLAB SLOB system which is later passed to RTAI With respect of the initialization order of the embedded mod ules and when using a modified global heap initialization algorithm as de scribed above the
62. nt For LRTAI support for image compression is desirable since it allows the user to burn the image into a small flash chip instead of using large hard disks Even though larger flash memory chips become available a small footprint of the base system leaves a margin for more user defined data or functionality Another option could be to include both a live and a rescue system in the same flash memory This could be used to provide the user software updates 24 3 1 Taken over concepts which overwrite the live area while keeping a fail safe var ant n another flash segment If an update fails or the new system is flawy the user could easily activate the backup system e g by pushing a reset button while powering on the device 3 1 3 Kernel command line As already mentioned above the original Linux kernel has the ability to receive Information during boot process from the bootloader and or thereby from the user itself indirectly This 1 mostly used to pass semi dynamic configuration information preventing the user from compiling the whole kernel a new when only some minor changes are needed This interface 1 represented as a simple command line string which can be filled with several tokens and or key value pairs These arguments are usually preconfigured in the bootloaders configuration Additionally many bootloaders permit the user to modify this string Disclosing it finally to the kernel is done by writing the memory address
63. of the string to a well known memory address inside the loaded kernel image Then while booting the kernel iterates over the elements of the command line invoking a callback function which was registered at compile time for each possible element Many callbacks simply set an internal kernel variable to a new value but also complex functions are possible Since this concept is quite simple and anyhow powerful it is kept in LRTAI Additionally as t is widely supported by bootloaders it guarantees the user highest flexibility 3 1 4 Initcalls During kernel configuration at compile time the user has for nearly all features the possibility to choose between building it as a dynamically loadable kernel module or linking it statically into the kernel Mostly a feature encapsulates a specific subsystem g a hardware driver This often needs an explicit initial ization procedure e g resetting the corresponding hardware device When the feature 1s inserted into the kernel as a module at runtime the kernel uses a well known interface to invoke the module s initialization function if one is defined The author of the module feature can use predefined macros for this 25 Chapter 3 Design in the source code providing a kind of abstraction layer so that the real kernel implementation could change Actually th s source level abstraction for kernel modules s also used when linking the module statically into the kernel Then the mention
64. ompiling stuff which will not be used This speeds up the kernel build time Important to know 15 that the build system uses the makefiles in an inconsis tent fashion As the kernel sources are split over multiple directories there are potential problems with resolving build dependencies see for details A solution for this problem is to generate a big virtual makefile which includes the makefiles of lower level rather than to descend into lower level with new makefile processes Linux build system mostly uses the virtual makefile ap proach however some targets are defined explicitly and launch new processes These internals are hidden from a user who initiates the whole process by a simple single make zImage or make bzImage call 2 4 build system RTAT s original build system is tricky It successfully combines the most pow erful features of two worlds namely the intuitive user interface and depen dency system of the kernel build system and the powerful host tool chain which is provided by GNU s autoconf automake libtool system This complexity was necessary to fulfill the multiple requirements e g a GUI based configuration system cross compilation support and a reliable host feature detection Fur thermore RTAI supports the C programming language for its applications whereas the original kernel code 1 restricted to be written C and assembler Building the RTAI distribution is very similar to building a kernel Fir
65. only This module will be used in LRTAI The scheduler s implementation 15 almost platform independent only a few parts are done in assembler e g the task switch The two mentioned incarna tions arise when toggling a flag at compile time The standard build system Chapter 2 State of the art compiles both modules by default The generated kernel modules contains ad ditionally almost all functions of the RTAI API Only the memory management and inter process communication facilities are provided by their own modules as described in the following sub sections 2 2 4 Memory management To fulfill the hard timing constraints of a real time system RTAI comes also with its own memory management module This is necessary as Linux being a general purpose operating system for desktop and server system implements oppositional design goals at least partly For example Linux tries hard to ful fill a memory request for an application Therefore it can be configured to swap memory to disks Another option was to reduce some buffers which had been grown when free memory had been available In the result the process requesting memory could be sent to sleep until the allocation could be success fully terminated Such a behavior is not suitable for hard real time systems The request should be processed in a time bounded manner so that the timing constraints are not broken For this RTAI implements its own memory allocator which bases on the algorith
66. ootloaders e g GRUB do not rely on this partition flag but the first stage code 1 config ured statically with the sector addresses of the following code Adhering to the example of GRUB this 15 called stage 1 5 and implements a tiny filesystem driver for the target partition so it varies between the used filesystems Hav ing loaded that code the bootloader has gained the ability to find its further stage s and finally the kernel image etc in the filesystem which provides a Menu based or even graphical GUI 39 Chapter 4 Implementation details Offset 0x200 Magic Number 2 bytes 0 1 Primary Partition Table 64 bytes 0 1 Partition 4 Partition 3 Boot loader 25 n Partition 2 Partition 1 0x000 Status Start CHS Partition End CHS Start LBA Length Figure 4 1 Traditional boot sector layout on a PC architecture larger flexibility and stops the need for updating the master boot sector if the position of the kernel image on the disk changes Usually this 15 also used to give the user the possibility to choose between multiple kernel images After this selection the kernel image is loaded into RAM and the bootloader passes control to the kernel by jumping to a well known start address in the kernel image The processor is still running in real mode at this stage therefore the kernel entry has also to be
67. or example there was a bug in the early Intel Pentium models which can be prevented with a special memory mapping It is assumed that LRTAI will l The bug is known as the FOOF Bug See for details 35 Chapter 3 Design not be used on such hardware g that the hardware is operating correctly 3 3 Merged build systems As already described the original Linux build system and RTAT s uses the same configuration system before compiling So t seems to be the best solution to integrate configuration in the existing one of Linux But not only the configuration stage 15 used but also the complete or ginal build system for the following reasons Since there will be no user space anymore all real time applications are built in into the kernel so the need for the user space tool chain support has gone Also cross compiling support 1s given by Linux tree The Linux ker nel itself comes with a lot of configurable features changes to system would be hard to maintain In comparison after stripping down RTAI to its core elements only a few features will remain Since most configuration choices come with a sensible preset and some items are hardly prechosen for LRTAI the need of the configuration would be only to select additional services e g for inter process communications However as some new configuration items were added to be able to choose between the global heap allocation methods a modified version of RTAT s config
68. original Linux kernel or of the RTAI distribution the licenses which were distributed with the particular packages or files apply Modifica tions of such files are usually covered by the same license see the included license documents for details For all other files which were created by this work and does not contain an explicit copyright notice and or license term the following applies Copyright C 2007 Michael Heimpold michael heimpold at s2000 tu chemnitz de gt This program is free software you can redistribute it and or modify it under the terms of the GNU General Public License version 2 as published by the Free Software Foundation This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details You should have received a copy of the GNU General Public License along with this program if not write to the Free Software Foundation Inc 51 Franklin Street Fifth Floor Boston 02110 1301 USA VII 1 ADEOS Adapt ve Domain Environment for Operating Systems PAPE Application Programming Interface APIC veces Advanced Programmable Interrupt Controller BIOS Bas c Input Output System BKL Big Kernel Lock BSS audio deos Block Started by Symbol adesse Central Processing Unit Digi
69. ould not use this feature this is not necessary While configuring the RTAI sources at compile time the user can choose whether the RTAI module should use Linux kmalloc or vmalloc The latter one does not give any advantage on LRTAI actually the whole memory in LRTAI will be linearly mapped so that there is no difference between both variants For LRTAI this configuration option is therefore preselected to kmalloc Another choice is the amount of memory which should be preallocated from Linux Here the user presets the size of the global heap which is provided and used by RTAI applications if these do not allocate their own heap It is still pos sible to change this value at runtime passing a module parameter when loading the module By the way for compiled in modules such parameters can also be set via the kernel command line Then the parameter has to be prepended by the modules name and a dot e g the parameter rtai global heap size be comes rtai malloc rtai global heap size This way the user could still set the memory which RTAI should use Actually the user has to preset this value in the bootloader if he she had not compiled in the right value If the compiled in value is larger than the available memory the initialization routine exits with an error and the global heap 15 not initialized at all On the other hand if the value is too small there might be much memory which can not be used for RTAT s global heap So this needs som
70. person needs an interface to choose between the many subsystem modules drivers and other features This interface should be reasonable easy to use 1 e it should guide the user and prevent incorrect use The second target group are the developers who actively work with the ker nel sources e g by maintaining a subsystem or device driver For these people the build system should provide rich functionality to ease their work The process of building a kernel can be divided into two parts The first part consists of the configuration step As the kernel comes with lots of drivers and as the subsystems are highly modularized it can be freely chosen which of the features should go into the static kernel image which ones are built as kernel modules for dynamical loading at runtime and which features are not needed at all After this first step the second one 15 executed which finally compiles all source files and links the object files together 12 2 3 The Linux kernel build system 2 3 1 Configuration The process of kernel configuration is usually initiated by running one of the make menu x g old rand def allmod allyes allno config commands where the first four targets will give a different graphical user interface and the later ones differently preset the configurable items Processor type and features Arrow keys navigate the menu Enter selects submenus gt Highlighted letters are hotkeys Pressing Y includes lt N gt
71. processors entium ppiie index htm June 21 2007 20 Jeff Bonwick The Slab Allocator An Object Caching Kernel Memory Allocator 1994 ttp www usenix org publications library roceedings bos94 full papers bonwick ps June 21 2007 x 21 Homepage of Michael Heimpold ttp www heimpold de ci c N I XIII TECHNISCHE UNIVERSITAT CHEMNITZ Zentrales Pr fungsamt Eidesstattliche Erkl rung Bitte Ausf llhinweise beachten Name Heimpold 1 Nur Block oder Maschinenschrift verwenden Vorname Michael geb am 15 05 1981 Matr Nr 24902 Ich erkl re an Eides statt gegen ber der Technischen Universit t Chemnitz dass ich die vorliegende Diplomarbeit selbstst ndig und ohne Benutzung anderer als der angegebenen Quellen und Hilfsmittel angefertigt habe Diese Arbeit wurde in gleicher oder hnlicher Form noch bei keinem anderen Pr fer als Pr fungsleistung eingereicht Datum 21 06 2007 Unterschrift fu I SS UP e b o hoa Anragsoler f A Diese Erkl rung ist der eigenst ndig erstellten Arbeit als Anhang beizuf gen Arbeiten ohne diese Erkl rung werden nicht angenommen Auf die strafrechtliche Relevanz einer falschen Eidesstattlichen Erkl rung wird hiermit hingewiesen
72. r within the ADEOS system for every available interrupt source it 1s not guaranteed that it will be called at all When an interrupt event occurs the domain list is processed in order of decreasing priority which means that a registered interrupt handler of a high priority domain s called first Dependent upon its return value and the corresponding domains configuration it 1s decided whether the lower 1n terrupt handlers are called or the event is not further dispatched Hence the name interrupt pipeline With higher priority it has full control over all available interrupt re sources and can decide which interrupts are passed to Linux It is also possible to stop the pipeline Then no interrupts are passed at all to lower domains The 2 2 The Real Time Application Interface handlers of the stalled interrupts are called soonest when the current domain restarts the pipeline As already remarked both the original Linux domain and RTAI s domain run in the same security level of the CPU i e ring level zero which is called kernel mode In this mode all instructions of the CPU are available and the code executed in this mode has full access to the hardware That means that Linux kernel code could easily circumvent the restrictions imposed upon it by directly interfering in the interrupt handling e g by clearing or setting the global interrupt flag of the CPU The cleaner and therefore compatible way of dealing with hardware in
73. reasons for this be comes clear when remembering the historic situation of these days Linux was intended to be a replacement for the Minix system which was mostly used as an educational operating system Linux itself however was and still 1s strictly user oriented That means that during the evolution and in the following time only those features which were actively used and needed get integrated The two main fields of application were desktop and server systems for a long time Therefore and as hardware particularly RAM becomes more and more avail able at reasonable costs other goals dominated the development and compro mises geared towards economical resource use were needed By the example of RAM the result is that a minimal Linux kernel requires at least 2 MiB of installed RAM in the target system RTAI 1 an enhancement for the Linux kernel to provided real time support The minimal requirements of the resulting system with respect to e g the memory size do not change On the contrary the extension tries to manage with the resources provided by the host system Therefore to reduce the total requirements the Linux side of the requirements has to be trimmed or the Linux subsystem has to be eliminated altogether In this work such a trimmed version of a RTAI enabled kernel is presented forming a lightweight implementation LRTAI of the RTAI Thereby only the traditional Intel architecture A 32 is focused similar work for e g
74. s kernel has to provide the RTAI API as an interface between applications and the system In the task formulat on some further development goals are stated Small size of the resulting kernel image Embedded devices often do without large hard disks The reasons for this are manifold Usually normal hard disks are not robust enough to pro vide continued service under the environmental conditions in which the embedded system 15 installed Otherwise there 15 often simply no need for large data memories and so using hard disks for bootstrapping only would be a waste and increases the price of the whole system For this reasons flash memory is the most commonly used solution today Being mechanically resilient it also offers a good trade off In cost benefit con siderations Larger flash memory 15 available and relatively inexpensive today Regardless of this more memory always implies a higher power con sumption So the overall embedded system profits when the operating system 15 already designed economically Clear and efficient design This goal 15 hard to achieve as there 1s no explicit metric given For ample it depends usually on the subject s previous knowledge to distin guish between a clear and unclean design However implicit metrics are used for verifying the results Since the Linux kernel is open source its complexity can be studied by everyone so it serves as a base The 19 Chapter 3 Design result s
75. s to choose the 8254 code paths Therefore the jiffies counter needs to be included too The original Linux timer inter rupt handler is reduced to update this variable solely This interrupt handler is the only one which remains from the original Linux part all other IRQs are managed in the real time domain 3 2 Spurned features As a general purpose operation system Linux has a lot of features Many of them would be useful if included in LRTAI some feature implementations are actually required by RTAI while sharing the existing code e g spinlocks However including many features implies a large footprint in the end Re ducing the system to fit on small embedded systems means to omit code and functionality Many parts of the original Linux are not strictly necessary for an RTOS Especially since the new LRTAI should only provide the original RTAI API 22 3 2 Spurned features some features can simply be dropped as there Is no corresponding or equivalent functionality It 1s for this reason that for instance the filesystem layer can be completely omitted The original RTAI does not care about the representation of data on disk or other media It relies on the Linux subsystem to manage these tasks For instance while bootstrapping new processes from loadable RTAI modules these modules are usually stored as a file in a filesystem When a module should be loaded into the kernel it is handled like a usual Linux kernel module which
76. s too require the presence of services provided by other kernel parts a dependency information can be associated with each item The build system evaluates these dependencies and adopts the configuration dynamically if changes are needed The result of the kernel configuration is finally saved in KERNELOUTPUT y config In the further build process this file Is transformed in a header file which can be included in the C source files and it 1s split into multiple small include files which serves for easier dependency tracking 13 Chapter 2 State of the art 2 3 2 Makefiles The kernel build system relies heavily on GNU s make tool which can usually be found on every Linux installation This tool assists larger projects by pro viding build dependencies so that it can determine automatically which pieces of the sources need to be recompiled if something changed The needed infor mation is given in the so called makefiles It is also possible to define macros and variables which are evaluated at runtime To support kernel developers and to keep the complexity of maintenance as low as possible the kernel build system uses such makefiles to implement a powerful framework Thus it can be achieved that when adding new features only a few lines must be added to the corresponding makefile Also the kernel configuration 1s included and can be referred to So it 1 possible to selectively compile the wanted features and avoid spending time on c
77. situation can occur that the requested blocksize is not avail able anymore when the application s memory request is executed Without modifications to the application s sources this problem can only be solved by changing the global heap allocation algorithm as described or at least restricting its greediness During LRTAI s configuration a margin could be given which is not allocated and therefore can be obtained from kmalloc Other solutions imply at least slight changes 1 the application sources One solution 30 3 1 Taken over concepts could be to use the global heap instead of spanning up its own However this could undesirable Another way could be to allocate a big memory block as a whole from the global heap This results in the heap in heap phenomenon The third variant could be to split up the memory allocation from the remaining ini tialization code To that end the order of the initcalls can be used As described in section 3 1 4 module init macro expands to device initcall which is ex ecuted lately Assuming that arch initcall and subsys_initcall should not be misused the remaining candidate is fs initcall This choice seems reason able as LRTAI comes without filesystem support It has to be mentioned that a traditional kernel module should only have one initialization macro referred to when compiling as a loadable module So to achieve source highest compatibility the second call should be hidden with
78. st the 14 2 5 Patches vanilla kernel sources has to be patched to include the ADEOS IPIPE This patch is included in the original RTAI tarball and has to be applied before configuring the kernel The modified and added parts integrates smoothly in the remaining system No special care must be taken by users so that thereafter the kernel could be compiled as usual 1 e first the configuration step followed by the actual build When the kernel build 15 finished for RTAI a similar configuration step can be run In this stage a configuration rtai config is generated which is RTAT s counterpart of Linux config But RTAT s build system passes this file to au toconf which finally creates rtai config h a header which contains the whole configuration and 15 therefore included in nearly every source file Also the makefiles for the RTAI modules are generated during this stage 2 5 Patches Among many other things the word patch has the sense of being a form of source code modification Usually intended to correct small errors in software systems the patch utility is somewhat misused in open source communities Here patches are also used to distribute significant changes in the software as already shown inD 1 2 andD 1 3 A patch file can have various layouts The most useful layout 1 where the actual modifications are enveloped by some lines of the original context An other layout carries only the line number as a hint beside th
79. system at compile time These code parts have to be dropped manually and the remaining refer ences has to be deleted or replaced with stubs In this work the second approach was chosen for the following reasons Firstly the task formulation suggests this way indirectly by eliminate the Linux subsystem Another reason 15 already given above The results of this work should not remain a proof of concept implementation but be already us able by real world applications In addition it is deemed that maintaining a complete new operating system kernel which was the result of the first ap proach would require much more time and known how as the maintenance of some patches for the established Linux system And finally there are many concepts already implemented which seem to be optimal for the resulting sys tem and a new OS kernel from scratch would be like reinventing the wheel These concepts are briefly discussed in the following sections 3 1 Taken over concepts 3 1 1 Binary image layout Usually when creating software the processor instructions are not put in bi nary form into a file but a compiler collection i e a preprocessor a compiler an assembler and finally a linker are used This tool chain translates the human readable source files to a binary representation which 15 executed on the target CPU For the Linux kernel most of the source code is written in the C program ming language which 1s highly portable Only for some hardwar
80. t would be nice to have but not strictly required It 1 further assumed that the code which is intended to run on an embedded target system 1 infrequently changed and therefore can be included in the kernel image at compile time It results that the sources of the included code have to be available and only source level capability to the existing RTAI projects can be achieved Another reason for omitting a loader 15 that tests of new modules could be done on normal PC systems where dynamic loading 1 available When the development process of the module is finished it can be ported easily to LRTAI as only minor changes 33 Chapter 3 Design in the core implementation are done Thus the behaviour is nearly identical to the developer machine when the same release of the kernel and RTAI s used Another topic 1s the device driver support 1n LRTAI Since all parts of the original Linux kernel run at the same CPU privilege level on x86 all code in kernel mode runs at the so called ring 0 all codes invariably have access to the hardware So no further differentiation between core kernel parts network subsystem or in particular drivers can be made This opens the possibility to device drivers to disable the interrupt system completely on the CPU If this is used by a driver implementation it would break the whole hard real time environment To prevent this all drivers have to be implemented with these facts in mind RTAI therefore comes wit
81. tal Signal Processor Executable Linking Format LI s bes Floating point unit CONU eos buo kawsas GNU is Not Unix OPI cecidi n GNU General Public License sa Gerneral Purpose Operating System GRUB 24 25 cause GRand Unified Bootloader GUE 32a Graphical User Interface HAB 44 4254 Hardware Abstraction Layer VON tuber Input Output Inter Process Communication IX Appendix D Copyright notice u sasa Interrupt PIPEline IR Or Interrupt request ISAC sus Industry Standard Architecture Lightweight RTAI Personal Computer PUL ies ee Programmable Interrupt Timer RAM Random Access Memory RTAI Real Time Application Interface RTOS Real Time Operating System SA RTL Stand Alone RTLinux ser Symmetric Multiprocessing USB Universal Serial Bus Video Graphics Array References 1 Jens Kretzschmar mplementing RTAI on a DSP without Linux Diploma thesis Chemnitz University of Technology 2005 ttp rtg informatik tu chemnitz de docs a sa txt da krej pdf 2 Michael Luft Completing and Testing Lightweight RTAI C6x Seminar paper Chemnitz University of Technology June 2006 ttp rtg informatik tu chemnitz de docs a sa txt sa luft pdf O 3 Dantel P Bovet and Marco Cesati Understanding the Linux Kernel Third Edition O Reilly Media 2005 ISBN 0 59600 565 2 4 Robert Love
82. tem and sets up the basic interrupt system for RTAI After this RTAI s own memory allocator is installed module rtai_malloc This module initializes a global heap which can be used by RTAI applications Finally the RTAI scheduler rtai sched is setup and the timer interrupt system 1s enabled After this an elementary RTAI system is up and running In the LRTAI sources a trivial sample RTAI application 15 included which 1 initialized after the above steps have finished When an LRTAI user adds his her own applications to the source tree he she has to take care of this initialization order A special sub directory rtai apps 1s provided where the custom applications and the corresponding makefile should be placed The higher level makefiles ensure that this directory 1s linked in after the RTAI core components This way the user has to track only his her own module dependencies and it is guaranteed that the RTAI subsystem is already available when the custom applications start Note that at least one application has to trigger the RTAI domain execution by calling start rt timer This is not done by default as the period to use should be specified by the user to fit best the application s requirements 4 2 The nano SLOB memory allocator As already stated above the memory management 15 the most critical task of an operating system Especially when the target system has restricted resources it 1s essential to maximize the utilization and effic
83. terrupts is to use the provided macros in the source code These are subject to be changed by the ADEOS patch and will be re placed with safer code which maps the desired functionality to the hardware abstraction layer So the Linux sources will be turned into a well behaving team mate in the system 2 2 3 Scheduling When introducing new real time tasks there must be a possibility to manage these new tasks The Linux kernel would provide some data structures ma tured task management code and a scheduler which operates on these data structures However the scheduler 1s was not suitable for real time tasks Ad ditionally it is a very complex system so any modification would have been hard to maintain Thus RTAI implemented the needed data structures and code parts itself not to be restricted to the limited capabilities of the Linux scheduler Nowadays in recent RTAI distributions the scheduler is available in two In carnations the first one is built as a module called sched the second one can be found rtai_lxrt The implementation of both modules is almost the same only the type of objects which can be handled is different The later scheduler 15 provided for user space based real time applications These appli cations are mainly used while developing and they ease this process since user space debugging be used The first module 1 only capable of scheduling own lightweight tasks which use the kernel mode
84. the requested functions directly and do not need to use the indirection of syscalls The implementation of the original Linux syscalls 15 usually composed of at least two functions for each syscall One function encapsulates the main func tionality and can be considered as the worker code the other one is used as the kernel mode entry function which is indirectly called from the user space This wrapper usually checks the given arguments calls the worker and returns 34 3 2 Spurned features the result or error code to the user space For LRTAI all wrapper functions can be dropped since the user space 1 not used anymore However the remaining code has to examined if it still requires some worker functions The Linux subsystem consists additionally of all code which handle the tasks in user space This is mainly the scheduler but also the signal management or the capability subsystem for example In kernel mode there should not remain any thread or activity which is not covered by the RTAI execution domain That means that all kernel threads and real time applications have to be managed by the RTAT s own scheduler This included all interrupt service routines with one exception The original timer interrupt is not migrated to RTAI and will be executed in the IPIPE s Linux domain At last the Linux memory management 15 dropped Being one of the most significant struts which characterizes an operating system the code does not fit into the
85. thing which could be deselected Together with a clean source tree a kernel image was built which had a size of about 450 KiB However it was detected that many code parts were compiled into the kernel which were thought to have been unselected deliberately By examining the sources the major cause could be determined Starting with Linux kernel ver sion 2 6 the kernel 1s equipped with the kobject infrastructure As this system maintains a close relationship with the sysfs filesystem it was determined that it would be disabled by not using the sysfs filesystem Many source files enclose the relevant code parts with preprocessing directives which ignore the code if sysfs 1s not going to be used However there are many source files which do not do this For LRTAI this files were patched with simple preprocessing in structions to statically exclude these lines of code As this is a straightforward solution it should be reverted later too The goal should be to supply a clean patch for the Linux kernel which could be included in the kernel s upstream Since the core kernel subsystems cannot be deselected during kernel config uration a few makefiles have to be touched But simply dropping the files from the makefiles would result also in a lot of undefined references as there tem porarily may still exist code parts during development which use the source module s functions and or variables A systematic iterative method was cho sen to solve this
86. uration should be merged into the kernel s The configuration items which will be newly present are now managed with the kernel s dynamic include system The rtai_config h which is normally the central include file for RTAI applications and which is generated after configu ration degenerates to a static file which holds some not yet migrated or legacy definitions and refers for the rest to Linux includes Actually the LRTAI will not yet be well prepared for the most configurable options on Linux side For example choosing LAPIC support would be de sirable however support is not yet implemented In LRTAI So it ships with a sensible preset of the config file For compiling the RTAI source files within the Linux tree the required C files are simply copied into a new sub directory The existing Linux top makefile has to be adopted to descend into this new directory As the orig inal RTAI makefiles depends heavily on the auto generated makefiles which are produced by the mentioned user space tool chain system they cannot be simply copied but have to be replaced Because the kernel build system brings 36 3 3 Merged build systems along a lot of functionality these replacements are quite simple and often only consist of a few lines So it will be easy to transfer additional RTAI features which are not yet included In LRTAI Except the mentioned adaption of the Linux top makefile and the replaced ones for the RTAI subtree there should be
87. use the module init macro to mark the module s entry functions While linking a kernel module statically into the kernel this macro translates to the initcall mechanism While in a standard Linux RTAI system the modules initializa tion order is determined by the order of loading the modules the initcalls are invoked in order of linking the module sources into the main binary This order can be controlled by the arrangement in the makefiles To keep the order in 41 Chapter 4 Implementation details CPU mode Execution Domain Source file Important Content of RAM description OxFFFFFFFO 4GB RM jmp BIOSENTRY HW BIOS I After power on reset the x86 CPU register EIP is filled with 0xFFF0 and CS with the value 0xF000 Due to the hidden base portion of CS containing OxFFFF0000 the n a actually starting address is OxFFFFFFFO a memory location which is mapped to the BIOS by th chipset and usually contains a jump to the BIOS entry point After this first far jump the hidden base value will be back in sync with the CS value resulting in an address space trunkated to the first mebibyte 0x7C00 640 kiB 1 MiB RM y umo BIOS I n a BIOS reads master boot record from disk copies it to 0x7C00 and then jumps to this address
88. wever this is also the worst case value of wasted memory space for each allocation request to the modified SLOB system With replacing this allocation mechanism a bug in the SLOB system of the used kernel version silently disappears As pointed out above the order of the requested block size is determined by the allocator Interestingly enough 45 Chapter 4 Implementation details this calculation is faulty the original kernel version for block sizes which are close to a wrap to the next higher order The consequence of this wrong compu tation 1 that the returned memory block 15 too small However the requesting application does not know this If it fully utilizes the memory area there is a high probability that it overwrites codes or data from other applications This would even be worse as there is no memory protection between the core kernel and the RTAI applications An unexpected crash or core dumps would have been a typical reaction The reason for calling the modified SLOB system nano SLOB allocator was already mentioned in section functions which deal with the cache memory management originating from SLAB but also build on top of the SLOB system were dropped This concretely concerns the functions whose names start with kmem_cache_ As the RTAI subsystem does not use these memory caches and all other modules which usually use these caches are also already dropped these functions are no longer necessary 4 3 M
89. y of Linux RTAI in periodic mode 55 5 4 Latency of Lightweight RTAI in periodic mode 55 B 1 Transcript of building the LRTAI kernel image HI Chapter 1 Introduction In the recent past there was an increasing demand for applications that run with strict timing constraints The fields of such applications spread over processing audio and or video data 1 e for telecommunications to dealing with complex calculations in motor control units All this applications have something in common and that is they need to fulfill their work n a time bounded fashion to avoid service degeneration or damage to the system to which they belong Usually the development of such applications does not start from scratch for the desired target environment that means the CPU the system board etc but an existing operating system is used which provides a more or less extensive set of functionality Nowadays there is a wide range of various commercial and or proprietary real time operation systems RTOS and open source vari ants Using the later ones does not only result in cost saving but also in having a white box system which guarantees full control over it This 15 true also for the progress of the development as needed modifications could be integrated upstream So using open source additionally provides investment security At the time of writing Linux as the most commonly known open source operating system 15 still a g

Lightweight RTAI for IA-32 (revised version)

Contents

Download Pdf Manuals

Related Search

Related Contents