Home

AN EMBEDDED SYSTEMS KERNEL IMM

1. I 1 1 1 168 pin SDRAM socket ra CBUS 1 Galileo EPLD i GT64120 SysAD MIPS64 7064 gt System 5 CPU 1 l Controller 1 Conf jumpers i HP LA debug Clock generation 1 1 OP MMC exco EF NEED SVP Figure 5 1 Overview of the CoreLV card The Galileo is an integrated system controller with three different interfaces and is especially designed for MIPS CPUS including 64bit MIPS CPUs Galileo s main functions in the CoreLV device includes 5 1 The Malta system 19 e Host to PCI bridge functionality e Synchronous DRAM controller and host to SDRAM interface The SDRAM controller support an address space of 512Mb but only 64 is installed in the test equipment The SDRAM type has to be PC100 RAM e Device bus interface The device bus from the Galileo is modified in the EPLD component on the Core card to provide the CBUS which is used for access to Boot Flash Flash memory and peripheral devices as LED s and switches places on the motherboard The Galileo is connected to the CPU bus SysAD which allows the CPU to access the PCI and memory buses It should be noted already here that due to a bug in the Galileo chip all register contents are effectively byte swapped in big endian mode which should be taken into ac
2. SAVE push noat AT R_AT sp SAVE TEMP vl t0 R T0 sp t1 R_T1 sp v1 R Hl sp vi t2 R_ T2 sp t3 R_T3 sp vl t4 R t5 R t6 R t7 R t8 R SAVE STATIC s0 R_SO sp sl R_S1 sp s2 R S2 sp s3 R S3 sp s4 R_S4 sp s5 R_S5 sp s6 R_S6 sp s7 R_S7 sp s8 R S8 sp SAVE_ALL SAVE_AT SAVE TEMP SAVE STATIC endm macro RESTORE SOME set set mfc0 set ori xori push reorder t0 CPO STATUS pop t0 Ox1f t0 Ox1f 124 Appendix B Source code mtc0 t0 CPO STATUS li v1 0 00 and tO vl 1 v0 R STATUS sp nor vl zero vl and vO vl or vO t0 set push reorder 1 v0 R STATUS sp set pop dmtcO0 v0 CPO STATUS ld v1 R EPC sp dmtc0O vl CPO EPC Id ra R RA sp ld gp R GP sp ld t9 R_T9 sp ld a3 R_A3 sp ld a2 R A2 sp ld al R Al sp ld a0 R AO sp ld vl R_V1 sp ld v0 R VO sp endm macro RESTORE AT set push set noat 1 AT R AT sp set pop endm macro RESTORE TEMP ld t8 R_LO sp ld t0 R T0 sp ld t1 R_T1 sp mtlo t8 ld t8 R Hl sp ld t2 R_T2 sp ld t3 R_T3 sp mthi t8 ld t4 R_T4 sp ld t5 R T5 sp ld t6 R_T6 sp ld t7 R_T7 sp ld t8 R_T8 sp endm macro RESTORE STATIC ld s0 R SO sp ld sl R_S1 sp ld s2 R S2 sp ld s3 R S3 sp ld s4 R_S4 sp ld s5 R_S5 sp ld s6 R S6 sp ld s7 R S7 sp 125 1 58 R S8 sp endm macro RE
3. 77 10 6 LCD display addresses Base address is 0x1f00 0400 78 10 7 LCD driver 78 10 8 Serial terminal 80 vili LIST OF TABLES Chapter 1 Preface 1 1 Executive summary The present report is the result of a master thesis entitled Embedded Systems Kernel The process of composing a development system envi ronment suitable for embedded system development in a Free Software environment is discussed The theory of protection and sharing of mem in a single space operating system is presented design for a small embedded systems kernel is presented the actual implementation of the kernel is described and a generalized bootstrap is proposed The actual implementation of the kernel is included in the appendix The kernel developed is released under the GNU General Public License The reason for this decision is that I want to allow people to use it freely modify it as they wish and then give their ideas and modifications back to the community 1 2 Prerequisites The prerequisites for reading this report is a common knowledge of op erating system kernels and operating systems in general Terms such as remote procedure calls and virtual memory should be familiar to the reader 2 Chapter 1 Preface A basic knowledge of C programming MIPS assembler and the use of the GNU development tools is preferable Finally some basic u
4. i ix10 s 705 return i void memset void s int c unsigned long count char x 5 while count XS return 5 static int strnlen const char x s int count const char xsc for sc s count amp amp sc 0 sc nothing return sc s j static char number char str long long num int base int size int precision int type char c sign tmp 66 const char xdigits 0123456789abcdefghijkImnopqrstuvwxyZ int i if type amp LARGE digits 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ if type amp LEFT Appendix B Source code 132 type amp ZEROPAD if base lt 2 base gt 36 return 0 type amp ZEROPAD 0 sign 0 if type amp SIGN if num lt 0 sign num num size else if type amp PLUS sign size else if type amp SPACE sign size if type amp SPECIAL if base 16 size 2 else if base 8 size i 0 if num 0 tmp i 0 else while num 0 tmp i digits do_div num base if i gt precision precision i size precision if 1 type amp ZEROPAD LEFT while size gt 0 5 if sign xstr sign if type amp SPECIAL if base 8 xstr 70
5. The correct compare value should be set in the timer driver write 32bit cp0 register CP0 COMPARE 0 void cpu init void unsigned int bits Init the CPU Config register Disable cache this has to be done in start S cpu speed bits STO KX STO SX STO_UX set cpO status bits bits kernel interrupt c Interrupt handling code Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include lt stddef h gt 139 include include lt add include include lt mip include include include include lt piix include inte lt kernel h gt rspace h gt lt regoffset h gt sregs h gt lt system h gt lt sched h gt lt printf h gt 4 h gt rrupt h gt extern void mipsIRQ void Counter for the nesting level x int interrupt nested define MAX INT 16 Array of interrupt handlers x static interrupt handler interrupt_action NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL 3 82C59 interrupt controllers Make come addresses for fast access x static volatile unsigned char xctr static static static static static This contains the interrupt mask for both 82 59 interrup
6. 4 chip It is relied on YAMON to do this initialization properly before the kernel is 9 8 Summary 65 runned Fortunately this is the case and it saves the kernel a lot of work during the kernel bootstrapping 9 8 Summary From this long discussion of bootstrapping and boot loaders the conclusion is even though no code can be reused from one bootstrap to another the skeleton on which the bootstrap is build has been the same on all systems studied in this project Another thing which should be noted is that even though hardware man ufacturers provide the hardware with a BIOS this should not be relied on to heavily since it may be buggy and it decreases the protability of the kernel if the supplied BIOS functions are used 66 Chapter 9 Bootstrapping 67 Chapter 10 Kernel implementation This chapter describes the kernel implementation The main focus will be on how to interface with the hardware since this subject has been the most time consuming part of the kernel implementation The chapter finishes with a brief description of the actual kernel construction All the source code for the kernel is listed in appendix During the chapter interfaces to several kernel components will be de scribed The prototypes for these interface functions will not be included in the interface description since if would not contribute significantly to the understanding of the semantics of the interface 10 1 Comp
7. R_ macros are bytes but stack ops are word size so divide by 8 ok a hack Reserve stack space Area is allready zero ed from initialization so that is not nessecary if sizeof reg offset 304 panic reg offset problem stack_regs sizeof reg offset Return address for both ra and epc registerx stack regs gt ra unsigned long function stack regs gt 0_ unsigned long function These two also needs special attention x stack regs gt 5 unsigned long stack regs stack regs fp unsigned long stack regs sizeof reg offset Save status register x save flags stack regs gt cp0 _status Update stack regs cpO status enable interrupts stack regs gt cp0 status STO IE IE IRQO IE IRQ1 IE IRQ2 IE IRQ3 IE IRQA IE IRQ5 Stack R SIZE 8 Return address for both ra and epc register stack R RA 8 unsigned long function stack R EPC 8 unsigned long function These two also needs special attention x stack R_SP 8 unsigned long stack WRONG stack R_S8 8 unsigned long stack R SIZE WRONG Save status register x save flags stack R STATUS 8 154 Appendix B Source code Update stack R STATUS enable interrupts Update the process structure x P gt stack pointer unsigned long stack regs
8. aa Qe OES Bee a B 9 Timer a ecc m PX ER eG abd oe T p 8 4 1 Message passing 8 5 Interrupt 8 6 Context switch 8 7 Global exception 8 8 Summary 9 Bootstrapping 9 1 Bootstrapping in 9 2 Introduction to boot 9 3 Bootstrapping 5 0 4 MIPS vs 11886 om AS Bee ik ae T 9 7 Kernel 9 8 Summary 10 Kernel implementation 10 1 Compiling 10 1 1 The 10 1 2 Source code 10 1 3 Compilation 10 2 Linking 10 3 Header files A1 41 44 45 47 48 48 51 52 53 55 55 58 59 61 61 63 64 65 iv CONTENTS oo oh RRR EE 72 73 10 4 2 Combined hardware interrupt 73 ICT 74 10 5 Context switch 74 Ae qnt 2 0 0 URS 75 76 10 _ 76 10 7 1 Timer driver 76 10 7 2 LCD 77 10 7 3 Serial terminal driver 79 TT aA et AS 80 10 9 Summary RR REY P ee ee 81 11 Status 83 11 1 Current kerne
9. gptab sdata gptab data x gptab sdata gptab sbss gptab bss gptab sbss Provide the symbols etext edata and end if they are not defined by the kernel It in the ISO ANSI C standard that these should be defined PROVIDE etext etext PROVIDE edata PROVIDE end include addrspace h x This header defines the address space stuff for the Malta board e g convertion macros and addresses Some of the macros has been taken from the Linux kernel This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details X 0 X X 0X X X ifndef ADDRSPACE define ADDRSPACE H H 101 When addressing byte you have to byteswap the address due to bug in the Galileo chip when running in big endian mode ifdef EB define swap8addr addr addr 0x0000000000000003 yelse define swap8addr addr addr Ffendif define MALTA_GT_PORT_BASE KSEGIADDR 0x18000000 Malta RTC device addresses define MALTA_RTC_ADR_REG 0x70 define MALTA_RTC_DAT_REG 0x71 addresses define TTYSO 0x3F8 define TTYS1 Ox2F8 Memory segments 64bit kernel mode addresses define KUSEG 0x0000000000000000 define KSEGO 0 xffffffff8S0000000 define KSEG1 0 xffffffffa0000000 define KSEG2 0 x
10. kernel Icd c LCD Display driver This file Public License this archive for more details include lt addrspace h gt Display register base is subject to the terms and conditions of the GNU General See the file COPYING in the main directory of define LCD DISPLAY WORD BASE KSEG1ADDR 0x1f000410 define LCD DISPLAY POS BASE KSEG1ADDR 0x1f000418 define MALTA PORT BASE KSEGIADDR 0x18000000 void lcd int unsigned int num 145 volatile unsigned int display void LCD DISPLAY WORD BASE display num void lcd_message const char str volatile unsigned int display void LCD DISPLAY POS BASE int i for i 0 i lt 14 i i 2 if str display i str else display 1 kernel list c Double non circular linked list functions Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include lt list h gt Initialize list void list init t list head pHead pHead number 0 pHead gt pFirst NULL pHead gt pLast NULL x Put element at end of list void list put t list head pHead t list element pElement pElement pNext NULL if pHead gt pLast NULL Head gt pFirst pElement Elemen
11. 224 239 Ta DLE Po b b Dy Ez D B E 240 255 define ismask x _ctype int unsigned char x define isalnum c ismask c amp U L D 0 define isalpha c ismask c amp U L 0 define iscntrl c ismask c amp C 0 define isdigit c ismask c amp D 0 define isgraph c ismask c amp P U L D 0 define islower c ismask c amp _L 0 define isprint c ismask c amp P U L _ D SP 0 define ispunct c ismask c amp P 0 define isspace c ismask c amp S 0 define isupper c ismask c amp _U 0 define isxdigit c ismask c amp _D _ X 0 define isascii c unsigned char c 0x7f define toascii c unsigned char c amp 0x7f static inline unsigned char _tolower unsigned char c if isupper c c A a return c 131 static inline unsigned char _toupper unsigned char if islower g r return define tolower c tolower c define toupper c toupper c Hey we re already 64 bit need to play games Replace this if you are going to port the kernel define do_div n base int res res unsigned long n unsigned base V n unsigned long n unsigned base V res static int skip_atoi const char xxs int i 0 while isdigit
12. Get the process with highest priority This one is alway the first in the list process highest process_base process list pFirst printf schedule cur_ id u high id u n process current gt id process_highest gt id If there is a higher priority ready task switch to it if process_current gt id process highest id process old process current process new process highest process new state RUNNING process current process new Mark old process ready if it was running x if process old state RUNNING process_old gt state READY printf schedule old_sp x cur_sp x n process old stack pointer process current stack pointer Switch the stacks stack_switch New process will be running here x printf schedule high id u n process current gt id process highest id printf schedule old_sp x 5 process old stack pointer process current stack pointer This is used when using calling scheduling from interrupt void schedule frominterrupt void t process process old 156 Appendix B Source code t process process_new t process process_highest Get the process with highest priority This one is alway the first in the list process highest process base process li
13. kernel panic o kernel test1 o kernel test2 o ib vsprintf o RR aa 2 k k k k k k k k Rules k K KKR KK gt K gt K gt K K gt K K 96 0 96 c CC W_OPTS CC OPTS o lt 96 0 96 8 CC W OPTS A CC OPTS A o lt all prepare IMAGE BIN IMAGE REC IMAGE DIS prepare rm f include arch In s ARCH include arch rm f kernel arch In s ARCH kernel arch IMAGE BIN IMAGE_ELF OBJCOPY O binary IMAGE_ELF IMAGE_BIN IMAGE_REC IMAGE_ELF OBJCOPY O srec IMAGE ELF IMAGE_REC IMAGE_DIS IMAGE ELF OBJDUMP S IMAGE_ELF gt IMAGE DIS IMAGE ELF OBJ LD LD_OPTS OBJ OBJCOPY O LD FORMAT change addresses OxffFffffff00000000 IMAGE ELF S IMAGE ELF install IMAGE REC cp IMAGE REC S TFTPDIR clean rm f OBJ IMAGE BIN IMAGE REC IMAGE DIS 99 rm f IMAGE ELF IMAGE MAP realclean clean rm f include arch rm f kernel arch find name xargs rm f find name semantic cachex xargs rm f kernel mips64 link xn Linker script for the kernel Created for the 64bit mips big endian achitecture Since the linker sucks at 64bit elf we link in 32bit elf and then change it afterwards with objcopy OUTPUT kernel elf OUTPUT ARCH m
14. Chapter 8 Kernel design This chapter describes the kernel design All major components of the ker nel are described that includes the timer the synchronization mechanisms the interrupt handling and scheduling The chapter finishes with a brief analysis of exceptions in C but first an overview of the kernel is given 8 1 Kernel overview The kernel is not going to be designed to solve specific tasks instead the design aims to make the kernel general within the previous mentioned kernel properties in chapter 3 General means that the kernel is going to include the common features of an embedded systems kernel These features can then be tuned for specific purposes in future use of the kernel As described in the kernel properties chapter the kernel should have a micro kernel like structure that is a small kernel with several kernel sub systems running as separate processes and where processes are able to communicate with each other and with the kernel Besides having a micro kernel structure the design also strives to fulfill the following areas e Separate the process management and scheduling completely from the hardware dependent code This serves two important purposes first you do not have to touch the process management and schedul ing code if you want to port the kernel to a different architecture 42 Chapter 8 Kernel design and secondly you can easily change the scheduler without having to modify strange a
15. Get first element of process t_list_element pLower pHead gt pFirst Handle the case of an empty list x if pHead gt number 0 list_put pHead pElement return Walk down the ordered list until a lower priority process is found while pLower pNext NULL If the priority is lower the we found the right place for our new process Congrats if process base pLower priority lt priority break Next element x pLower pLower gt pNext Insert the new process into the list here x 1156 before pHead pLower pElement Reorders process process list void process_reorder t list head pHead t list element pElement done by removing and inserting list remove pHead pElement process insert pHead pElement Create new task and initialize its state void process create void xfunction void int priority int stack _size 153 if 0 reg offset stack_regs Get a free process x t process amp process allocated nextId Initialize the task specific data P id nextId J 4 P state READY P priority priority P gt orig_priority priority Allocate a stack stack_regs reg offset process stackalloc stack_size Build a state corresponding to an interrupted or or stack switched process
16. else if base 16 xstr 70 str digits 33 if type amp LEFT while size gt 0 str while i lt precision str 70 while i gt 0 str tmp i while size gt xstr return str 133 vsprintf Format string and place it in buffer buf The buffer to place the result into fmt The format string to use args Arguments for the format string Call this function if you are already dealing with a va_list You probably want sprintf instead int vsprintf char buf const char fmt va_list args int len unsigned long long num int i base char str const char xs int flags flags to number int field width width of output field x int precision min of digits for integers max number of chars for from string int qualifier h 1 or L for integer fields z support added 23 7 1999 S H z changed to Z davidm 1 25 99 for str buf fmt fmt if fmt 7 str fmt continue process flags x flags 0 repeat fmt this also skips first 7 x switch fmt case flags LEFT goto repeat case flags PLUS goto repeat case flags SPACE goto repeat case flags SPECIAL goto repeat case 0 flags ZEROPAD goto repeat
17. 2 values for divider stage reset others for testing purposes only define RTC_DIV_RESET1 0x60 define RTC DIV RESET2 0x70 Periodic intr Square wave rate select 0 1 32 8kHz 15 2Hz define RTC RATE SELECT OxOF define RTC CONTROL RTC REG B define RTC SET 0x80 disable updates for clock setting x define RTC_PIE 0x40 periodic interrupt enable x define RTC AIE 0x20 alarm interrupt enable x define RTC_UIE 0x10 update finished interrupt enable define RTC SQWE 0x08 enable square wave output x define RTC DM BINARY 0x04 all time date values are BCD if clear define RT C 24H 0x02 24 hour mode else hours bit 7 means pm define RTC_DST_EN 0x01 auto switch DST works f USA only define RTC INTR FLAGS RTC REG C caution cleared by read x define RTC IRQF 0x80 any of the following 3 is active x define RTC PF 0x40 define RTC AF 0x20 define RTC UF 0x10 define RTC VALID RTC REG D define RT C_VRT 0x80 valid RAM and time RTC H include sched h Sched Header Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details ifndef SCHED H define SCHED H 119 extern int sched now void schedule void void frominterrupt void en
18. Intel 1386 61 9 4 MIPS vs Intel 1886 In the following a comparison of the startup sequence on the Malta system and the Intel platform is made On the standard Intel PC the initialization after power on is as follows BIOS boot loader kernel Whereas the initialization on the Malta system with its combined BIOS and boot loader is YAMON kernel When creating embedded systems for real world applications the standard Intel PC boards are rarely used This may seem strange since it is so widely available One of the main reasons is that the BIOS is extremely slow at initializing the hardware From power on to the actual boot loader is running takes approximately 10 seconds whereas on the Malta it takes approximately 2 seconds People using embedded systems often expect the system to be up and running in no time making the standard Intel PC unusable for these purposes Initiatives to solve the long boot times on the Intel platform is in the works The most promising project is the LinuxBIOS 29 project which is able to reduce the startup time to 3 seconds from power on to a stripped down Linux kernel is running The only problem with this project is that the hardware vendors are not very co operative when it comes to datasheets for their hardware Another problem which could be noted is that many of the features pro vided by the PC BIOS is unusable in modern operating systems since they always run in protected
19. Releasing code un der the GPL and using a non free compiler could lead to licensing problems A requirement will therefore be that the compiler is also under a free software license The obvious choice could be the GNU compiler collection GCC but other compilers under GPL compat ible licenses could also do This choice creates some restrictions in possible hardware choices since not all platforms are well supported by a GPL compatible compiler 10 Chapter 3 Kernel properties 3 3 Summary This chapter has listed several properties to the kernel the tools used in the development and to what should be of concern in the analysis and design phase of the kernel Some relation exists among these kernel properties and some may argue against each other but this is unavoidable The chapter has also defined a basis for the kernel to the extent that feasible choices of hardware and software used for the implementation can be made 11 Chapter 4 Choosing hardware This chapter describes the process of choosing the right hardware for the development of the kernel The different hardware which has been consid ered will be described 4 1 Introduction With the previous defined kernel properties in mind it is now possible to choose hardware for the project The different requirements to the hard ware can be summed up to The price It is a personal wish that the price of the development hard ware for the embedded system is low T
20. This may seem like a nice and dynamic solution compared to Opal but the result is a lot of unnecessary management of objects that are not shared Another issue is that if an object is an instance of a data structure which is able to expand it would not be expanded continuously in the virtual memory Even though this fine grained management of object does reduce the per formance it does provides the ability to create very advanced management of the objects Angel takes advantage of this by allowing the possibility of creating dependencies between the capabilities of object For example ex pressing that one object is not accessible before another is also accessible The communication between the protected domains are in essence the same as in Opal but instead they are called light weight remote procedure calls 38 Chapter 7 SASOS The key point in the Angel s handling of protection and sharing of mem ory is the use of objects with associated capatilities in protection domains and the protection domains are controlled by the system instead of by the processes themselves 7 4 Mungi The final system to be discussed is Mungi I3 Mungi is the first real native implementation of a SASOS on standard 64 bit hardware The previously discussed systems Opal and Angel are both proof of concept implemen tations and have not been able to fully demonstrate the potential of SASOS Mungi is built on top of the L4 microkernel and is develo
21. additional priority levels also means a worse performance Sitting in a loop and moving across all the pending interrupt bits is not the answer the common case is one pending interrupt so it is optimized in that direction 8 6 Context switch Context switch the switch between two processes can happen in two dif ferent ways when a process releases or locks semaphore and during interrupt handling The context switch is done by switching the stacks The stack contains the state to which it should restore to after the context switch When changing from one process to another by switching the stacks special attention has to be paid to the problem as to whether it is an interrupt who triggered the context switch or a process using a semaphore In systems where processes uses system calls to the kernel it is customary to trigger a software interrupt and then by means of this switch to the kernel In these types of systems only the interrupt handler is used to save and restore a given process state In systems where the context switch can be done by means of a routine call to the kernel or by means of an interrupt handler doing the context switch these two methods has to coorporate This leads to four special cases of context switches 1 Changing from a process preempted by an interrupt to a process preempted by a using a semaphore 2 Changing from a process preempted by a using a semaphore to a process preempted by an interrup
22. define 1 lt lt 5 define 5 1 lt lt 17 Events counted by counter 0 define CEO CYCLES define CEO_INSN_ISSUED define CEO LPSC ISSUED define CEO_S_ISSUED define CEO SC ISSUED define CEO_SC_FAILED define BRANCH DECODED define CE0 QW WB SECONDARY 7 define CEO0 CORRECTED ECC ERRORS 8 define CEO0 ICACHE MISSES 9 aQokWnNnro 111 define CE0 SCACHE I MISSES 10 define CE0 SCACHE I WAY MISSPREDICTED 11 define INTERVENTIONS REQ 12 define CEO EXT_INVALIDATE_REQ 13 define CEO0 VIRTUAL COHERENCY COND 14 define CEO_INSN GRADUATED 15 Events counted by counter 1 define 1 CYCLES define CE1 INSN GRADUATED define CEI LPSC GRADUATED define CE1 S GRADUATED define CE1_SC GRADUATED define CE1 FP INSN GRADUATED define 1 WB PRIMARY define CE1_TLB_REFILL define CE1_BRANCH_MISSPREDICTED 8 define CE1 DCACHE MISS 9 define CE1_SCACHE_D_MISSES 10 define CE1 SCACHE D WAY MISSPREDICTED 11 define CE1 EXT INTERVENTION HITS 12 define CE1_EXT_INVALIDATE_REQ 13 define CE1 SP HINT TO CEXCL SC BLOCKS 14 define CE1 SP HINT TO SHARED SC BLOCKS 15 NOnkRWNRO These flags define which priviledge mode the counters count events define USER 8 Count events in user mode EXL ERL 0 define CEB SUPERVISOR 4 x Count events in supvervisor m
23. get field width field width 1 if isdigit fmt field width skip_atoi amp fmt else if fmt T fmt it s the next argument field width va_arg args int if field width lt 0 field width field width flags LEFT get the precision 134 Appendix B Source code precision 1 if fmt fmt if isdigit fmt precision skip atoi amp fmt else if fmt fmt it s the next argument precision va_arg args int if precision lt 0 precision 0 get the conversion qualifier x qualifier 1 if fmt h fmt fmt L fmt Z qualifier fmt fmt default base base 10 switch fmt case c if flags amp LEFT while field_width gt 0 str xstr unsigned char va arg args int while field width gt 0 continue case s s va arg args char x if 15 s lt NULL gt len strnlen s precision if flags amp LEFT while len lt field width xstr for i 0 i lt len i str s while len lt field width str continue case p if field width 1 field_width 2xsizeof void flags ZEROPAD str number str unsigned long va_arg args void
24. opment and argued which tools to use It also gave a small description of 30 Chapter 6 Software the very usefull library which is used to some extend in this project Now it is time for some real work 31 Chapter 7 SASOS This chapter describes Single Address Space Operating Systems SASOS It begins by introducing single address space operating systems with com parison to the traditional multiple address space operating systems After this introduction three different single address space operating systems are discussed namely Angel Opal and Mungi The focus will be on the sharing and protection of memory between processes in the single address space op erating system The three single address space operating systems are very similar in the mechanisms they use for sharing and protection of memory Therefore the first system described which is Opal will be used as a ref erence model when discussing the last two single address space operating systems 7 1 Introduction As described in Kernel Properties chapter 3 the context switch between two processes will be a stack based context switch That is when changing from one process to another the context switch should be done by manip ulating the stack as described in chapter B The address space is therefore the same before and after a context switch hence the kernel will only run in one address space Running several processes in the same address space could
25. time for example the brakes has to work immediately 4 Chapter 2 Introduction 2 2 Introduction to the project An important concern in the development of kernels for operating systems or embedded systems in general is portability across different hardware platforms Most kernel subsystems including the ones that are machine dependent are written in high level languages such as C or C As a result very little machine dependent assembly code needs to be rewritten for each new port But writing a kernel in a high level language is not enough for a kernel to be easy portable If all the machine independent code is mixed together with the machine dependent you still have to touch most of the kernel code in the porting process More recently the notion of nanokernels 11 has been introduced represent ing the virtual hardware support for the rest of the machine independent kernel This project strives to create a small nanokernel and a few subsys tems for use in embedded systems The kernel subsystems will therefore have a clean interface to the nanokernel The problems concerning coldboot will be analysed with the goal of reduc ing dependencies to the hardware to as little as possible If coldboot is neglected the embedded system can be considered as one program with more activities There will only be one activity when the program starts and this activity will be executed without restrictions in privileges The creation of a
26. 10 4 Handling interrupts In the MIPS architecture interrupts traps system calls and everything else that disrupts the normal flow of execution are called exceptions The 5Kc CPU is hard coded to execute program code at one of five different locations depending on the type of exception which has occurred This could be a cache error exception an interrupt exception etc In this kernel only interrupt exceptions are of interest and all other types of exceptions are left up to YAMON to handle In the following interrupt exceptions will be called interrupts for simplicity The types of interrupt that can occur are a timer interrupt from the 5Kc CPU and a combined hardware interrupt generated by the interrupt con troller that is located in the PIIX4 device on the MALTA board The interrupt controller located the device is a standard 82C95 inter rupt controller 10 4 Handling interrupts 73 10 4 1 Registering the interrupt handler As mentioned above the CPU is hard coded to execute program code at specific location when an interrupt is asserted In the 5Kc CPU the address is Ox f ff f 80000200 and there is exactly room to put 32 bytes of code to handle the interrupt at this address Instead of copying a full interrupt handler to this address a jump instruction to the real interrupt handler should be copied on this address The jump instruction is composed of the op code for the jump instruction and the
27. 8 bit microcontroller originally developed by Intel in 1980 Now it is made by many independent manufacturers typical 8051 con tains a CPU with boolean processor 5 or 6 interrupts 2 or 3 16 bit timer counters a programmable full duplex serial port and 32 I O lines Some models also include RAM or ROM EPROM Single board computers with an 8051 integrated come in many shapes and normally cost at most 100 Since it is a widely used microcontroller there are also a lot of development tools for this microcontroller Of the free tools available the SDCC Small Device C Compiler project 27 looks the most promising After talking to a long time 8051 developer the conclusion was that it is not suitable for developing a small microkernel which is heavily based on stack usage This is due to the fact that the 8051 compiler does not use the stack to save parameters to functions as we know it from e g Intel s 1386 systems If we did use the stack anyway the result would be slow and not usable 4 3 Atmel AVR 8 Bit RISC 13 4 3 Atmel AVR 8 Bit RISC Atmel has a series of AVR microcontrollers that have an 8 bit RISC core running single cycle instructions and a well defined I O structure that lim its the need for external components Internal oscillators timers UART analog comparator and watchdog timers are some of the features that are found in AVR devices The AVR instructions are tuned to decrease the size of the program whe
28. and some interesting reasonably fast and easy to use hardware with a good community and commercial support The resulting kernel which has been developed during this thesis is very small The source code is approximately 3500 lines of C and assembly code and this includes all comments and header files Even though its size is very limited it does include some important features to mention a few e Effective timer implementation e Binary Semaphores which implements the basic priority inheritance protocol e pre emptive nano kernel which reduces latency The resulting kernel is highly modularized and the scheduler can be changed with minimum effort With reasonably little coding effort the kernel could be used in hard real time systems The kernel has been designed and implemented with portability in mind and as much code as possible has been written in C The result is a kernel where the porting process to another architecture can be done almost by rewriting the assembly routines to fit the new architecture Even though there has been hard times carrying out this thesis with linker bugs and hardware bugs that took several weeks to work around it has been 88 Chapter 12 Conclusion an interesting and educational project It has given me good understand ing of embedded development hardware bootstrapping and initialization as well as good insight to many different aspects of operating system s theory Is has also been a g
29. define PIIX4 ICTLRI ICW2 0x21 7 define PIIX4 ICTLR1 0x21 define PIIX4 ICTLR1 4 0x21 7 define PIIX4 ICTLR2 ICW1 0 define PIIX4 ICTLR2 ICW2 1 define PIIX4 ICTLR2 ICWS3 1 7 define PIIX4 ICTLR2 ICWA 1 define PIIX4 ICTLRI OCWI 0x21 7 define ICTLRI OCW2 0x20 define PIIX4_ICTLR1_OCW3 0x20 define PIIX4 ICTLRI OCWA 0x20 define PIIX4 ICTLR2 OCWI 1 7 define PIIX4 ICTLR2 OCW2 0 define PIIX4 ICTLR2 OCWS3 0 define PIIX4 ICTLR2 OCWA 0 DOC ACC ak sk ak sk ak Register encodings define PIIX4 OCW2 NSEOI 0 1 lt lt 5 define PIIX4 OCW2 SEOI 0 3 lt lt 5 define PIIX4 OCW2 RNSEOI 0x5 lt lt 5 define PIIX4 OCW2 RAEOIS 0 4 lt lt 5 define PIIX4 OCW2 RAEOIC 0 0 lt lt 5 define PIIX4 OCW2 RSEOI 0x7 lt lt 5 define PIIX4 OCW2 SP 0x6 lt lt 5 define PIIX4 OCW2 NOP 0x2 5 define PIIXA OCW2 SEL 0 0 lt lt 3 define PIIX4 OCW2 5 0 define PIIX4 OCW2 ILS 1 define PIIX4 OCW2 ILS 2 define PIIX4 OCW2 ILS 3 define PIIX4 OCW2 ILS 4 define PIIX4 OCW2 ILS 5 define PIIX4 OCW2 ILS 6 define PIIX4 OCW2 ILS 7 define
30. display ASCIIPOS6 0x000 0048 Writing an ASCII value to this address updates position 6 on the LCD display ASCIIPOS7 0x000 0050 Writing an ASCII value to this address updates position 7 on the LCD display Table 10 6 LCD display addresses Base address is 0x1f00 0400 lcd int Takes an integer as argument an prints it in hex on the LCD display lcd message Takes a string as argument and displays the eight first characters on the LCD display Table 10 7 LCD driver interface 10 7 Kernel drivers 79 10 7 3 Serial terminal driver This driver controls the serial VT220 terminal connected to the Malta system s serial port The serial port on the MALTA board is controlled by a Super I O Con troller from SMcS and incorporates two full function UARTs The file serial h defines all the register addresses in the UART and most of the register settings of this writing input on the serial line is not supported but it should be fairly simple to implement as the interrupt handler is already registered to receive the data from the UART Since DMA is not supported by the Super I O Controller the data should simply be read from directly from the memory mapped serial buffer Initialization The VT220 terminal is configured to run at 19 200 baud with 8 bit data one stop bit and no parity so the serial port in the Super I O Controller has to be initialized the same way The serial port
31. enable irq irq j Register an combined interrupt x void interrupt register int irq interrupt handler handler No irq sharing if interrupt action irq NULL printf IRQ 96d is already in use irq panic PANIC No irq sharing interrupt action irq handler Initialize the interrupt handler void interrupt_init reset nesting level x interrupt_nested 0 Set the interrupt vector x interrupt setvector mipsIRQ Until now the interrupt has been disabled so now we start everything by enabling the interrupts and setting the interrupt mask set cpO status STO IM IE IRQO IE IRQ1 IE IRQ2 IE IRQ3 IE IRQ4 IE IRQS sti kernel kernel c Highlevel kernel entry Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details 143 include lt yamon h gt include lt cpu h gt include lt serial h gt include lt timer h gt include lt process h gt include lt interrupt h gt include lt printf h gt include lt setjmp h gt include lt sched h gt include lt mipsregs h gt include lt system h gt Declare processes here extern void process 1 void extern void process 2 void jmp buf buf static void foo void printf In foo Nn longjmp buf 1 printf
32. handle EOF like the standard library is required to 130 Appendix B Source code define U 0x01 upper define _L 0x02 lower x define D 0x04 digit define C Ox08 cntrl define _P Ox10 x punct define S 0x20 white space space If tab define _X Ox40 hex digit x define SP 0x80 x hard space 0x20 unsigned char ctype i C C 0 7 5 5 5 5 5 8 15 0 6 6 0 0 6 16 23 C C C C C C C C 24 31 S SP P P P P P P P x 32 39 P P P P P P P P 40 47 D D D D D D D D Jx 48 55 x D D P P P P P P 56 63 P _U _X _U _X _U _X _U _X _U _X U _X U 64 71 x U _U _U U _U _U _U _U 72 79 U _U _U _U _U _U _U _U 80 87 U U U P P P P P 88 95 L X L X L X L 96 103 ESSI Db 104 111 x iy 1 lay Jx 112 119 1 1 1 P P P P C 120 127 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 128 143 x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 144 159 x S SP P P P P P P P P P P P P P P P 160 175 P P P P P P P P P P P P P P P P 116 191 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 192 207 U _U _U _U _U _U _U _P _U _U _U _U _U _U _U _L 208 223 JI Ds ES 2B Ls Ds Dic i
33. mode whereas the BIOS can only be used in real mode Many of the features that the PC BIOS provides are only for backwards compatibility with DOS 9 5 Probing hardware Above it has been mentioned that after the CPU and RAM have been initialized all the different hardware parts of the system are initialized 62 Chapter 9 Bootstrapping or at least the ones that are actually used But how do you know which hardware is in the system The method for finding hardware is called probing the hardware Since not much hardware is supported in this kernel not much hardware is actually probed The only hardware probed is the CPU type and the CPU speed this is implemented in cpu c To identify the MIPS CPU type the CPU contains an implementation number and a manufacturer defined revision level in a register called PRId in the coprocessor in the CPU However it is best not to rely on the revision level information since changes in the CPU are not always reflected in the revision level The implementation number on the other hand characterizes the CPU and from this it can be varified that the kernel is really running on 5Kc CPU The CPU speed is needed when creating a timer The CPU speed is often found by running a loop of known length that will take a fixed large number of CPU cycles and then compare the count register before and after running the loop The count register is described in section 10 7 1 I have chosen
34. nested nop addu a0 a0 1 Sw a0 interrupt nested if interrupt nested 0 amp amp sched_now sched now 0 schedule frominterrupt j lw a0 interrupt nested bne a0 zero dont schedule lw a0 sched now beq a0 zero dont schedule nop sched now 0 Sw zero sched now Update current process x jal schedule frominterrupt dont schedule sp process current stack pointer stack pointer has offset 32 ld a0 process current ld sp 32 a0 lt This makes the stuff halt At this point we have handled the exception maybe even context switched So we now load the registers from whatever stack we have and return noreorder RESTORE ALL eret set at END return kernel panic c panic function 150 Appendix B Source code This file is subject to the terms and conditions of the GNU General x Public License See the file COPYING in the main directory of this archive for more details include lt serial h gt void panic char buf char xp for p buf xp p if p n serial_putchar r serial_putchar xp while 1 now panic kernel process c Process management Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archiv
35. not fulfill the price requirement of being a low budget system since the price is approximately 3000 but it is definitely a nice system to develop on It has all the right tools for development and as the AT91 it has a wide community support 4 6 Summary This chapter has discussed the different single board computers which have been investigated thoroughly for this project The choice in hardware fell 4 6 Summary 15 on the MIPS Malta development board with 64 bit CPU It was chosen even though the system did not fulfill the price requirement of being a low budget system But who can say no to a free 64 bits MIPS system 16 Chapter 4 Choosing hardware 17 Chapter 5 Hardware To be able to explain the specific implementation of the kernel in the fol lowing chapters an overview of the hardware is given The level of detail in the hardware description is just enough to understand some hardware spe cific implementation issues This hardware description includes the main board the CPU and the test bed used for development 5 1 The Malta system The Malta system is designed to provide a platform for software devel opment with MIPS32 4Kc and MIPS64 5Kc based processors A Malta system is composed of two parts The Malta motherboard holds the CPU independent parts of the circuitry and the daughter card holds the proces sor core system controller and fast SDRAM memory The daughter card can easily be swapped to a
36. process blocks one or more higher priority processes it ignores its original priority assignment and executes its critical section at the highest priority level of all the jobs it blocks This protocol only deals with priority inversion and does not prevent dead lock If for example process locks S1 and then tries to lock 52 but S2 gets locked by a higher priority process which now tries to lock S1 and a deadlock occurs Instead of using PIP the Priority Ceiling Protocol or Highest Locker could be used This would prevent deadlock as well as priority inversion 8 4 1 Message passing As mentioned in chapter B message passing between processes should be in troduced by a simple send and receive mechanism as known from Minix 17 This however does not have to be a part of the nano kernel since this can be solved by implementing the producer consumer problem 19 using the binary semaphore provided by the nano kernel This feature is then up to the user of the kernel to implement and therefore not included as a nano kernel functionality It is no requirement that message is introduced at all to use the kernel One could just as well choose to have a monolithic kernel structure with shared memory between the processes 8 5 Interrupt handling When designing interrupt handling several design issues have to be taken into account 1 Decide how the interrupts priority should be 8 5 Interrupt handling 49 2 Decide whether i
37. result in strange behavior or system crashes in an embedded system if there is nothing to 32 Chapter 7 SASOS prevent a misbehaving process from writing in another process memory It would be even worse in a multiuser operating system if there were no pro tection between processes because it would be impossible to give different privileges to different users of the system Another issue is finding bugs and recovering from a process failure If a process writes data in some place where is was not supposed to there will be no warning from the system and the bug would be very hard to find It would also be impossible to recover from this situation since the system will give no warning when the process begins to misbehave Because these problems with single address space operating systems are also valid in this kernel project it was natural to research solutions to protecting processes from each other There have been several attempts to create Single Address Space Operating Systems SASOS and three of these will be described in the following Before examining the concepts of a single address space operating system it is useful to review the multiple address space approach 12 where every process has its own private address space The major advantage of private address spaces are 1 They increase the amount of address space available to all programs 2 They provide hard memory protection boundaries 3 They permit easy clea
38. the format string int sprintf char buf const char fmt va list args int i va start args fmt i vsprintf buf fmt args va end args return i Send print message to the console driver void printf char fmt char buf 1024 va list args int i Format the string x va start args fmt i vsprintf buf fmt args va end args serial print buf kernel cpu c CPU functions Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include lt addrspace h gt include lt regoffset h gt include lt mipsregs h gt 137 include lt system h gt include lt rtc h gt include lt kernel h gt include lt cpu h gt include lt printf h gt include lt timer h gt static unsigned char rtc_read unsigned long addr volatile unsigned char rtc_add unsigned char swap8addr MALTA_GT_PORT_BASE MALTA RTC ADR REG volatile unsigned char rtc dat unsigned char swap8addr MALTA_GT_PORT_BASE MALTA RTC DAT REG rtc add addr return xrtc dat static void rtc write unsigned char data unsigned long addr volatile unsigned char xrtc add unsigned char swap8addr MALTA_GT_PORT_BASE MALTA RTC ADR REG volatile unsigned char rtc dat unsigned char swap8addr MALTA_GT_PORT_BASE MALTA
39. the semaphore pS gt owner process _current printf taken n The semaphore is taken test to see if the process using the semaphore has lower priority process semlocker pS gt owner if process semlocker priority lt process_current gt priority if process semlocker state READY panic PANIC Nested semaphores are not allowed n Bump up the process priority of the semaphore owner x process semlocker priority process current priority Reorder the process list x process reorder amp process list amp process semlocker gt process elem Add the calling task to the waiting list x process calling process current process calling state WAITING list remove amp process 115 amp process calling process elem process insert amp pS gt list waiting amp process calling process elem printf _sem call n process_list_print amp process list Now lets get a new process x schedule When the semaphore is released the caller begins executing here restore flags flags Signal for a semaphore x void semaphore signal t_semaphore pS 158 Appendix B Source code long flags t process process waiting save and cli flags printf sem signal if pS gt state LOCKED Get first waiting process process_waiting process_base p
40. to other systems is made and the chapter finishes with a description of how bootstrapping a kernel is done in practice on the Malta system 9 1 Bootstrapping in general In operating systems the term bootstrapping denotes the process of bringing the operating system s kernel into main memory and executing it It is highly system dependent how much work is actually required of the system programmer to get an operating system s kernel up and running Often the bootstrapping process is simplified by the introduction of a BIOS firmware boot loaders and so forth When the system cold boots that is when it starts up just after a power on nearly all the hardware is in a random state and has to be initialized before it is used The classical system startup is devided into the following three steps 1 In the first step the BIOS firmware or similar is executed This is the first code that is actually executed after power on This code is 56 Chapter 9 Bootstrapping provided by hardware manufacturer and will in the following be re ferred to as the BIOS Its main job is to initialize the basic hardware such as the CPU the CPU cache and the RAM It is completely up to the hardware vendor how much functionality is actually included in this part of the system startup For instance the previously men tioned AT91 system has no BIOS at all and all initialization has to be written from scratch Depending on the system configuration the BIO
41. unsigned long s7 unsigned long t8 unsigned long t9 unsigned long k0 unsigned long kl unsigned long gp unsigned long sp unsigned long s8 unsigned long fp unsigned long ra Other saved registers unsigned long lo unsigned long hi Saved 0 registers unsigned long 0 unsigned long cp0_badvaddr unsigned long cpO status unsigned long cp0 cause reg offset yelse MIPS define define define define define 7 define 7 define 7 define define define define define 7 define define define define define define define 7 define 7 define define define 7 define register offsets for use in assembler R_AT R VO R V1 R A0 R AI R A2 R_A3 R TO R T1 R T2 R T3 R T4 R T5 R T6 R T7 R_SO R S1 R S2 R S3 R_S4 R_S5 R_S6 R S7 R ZERO 0 8 16 24 32 40 48 56 64 117 define R T8 192 define R T9 200 define R KO 208 define R K1 216 define R GP 224 define RSP 232 define R S8 240 define 240 define 248 define 256 define R HI 264 define _ 272 define R BVADDR 280 define R STATUS 288 define R CAUSE 296 define R_SIZE 304 tendif LANGUAGE_ASSEMBLY x fendif REGOFFSET H x include rtc h Register definitions for the Real Time Clock CMOS RAM Modified for use in this kernel by Lars Munch 2001 Copyright Torsten Duwe lt duwe info
42. where devices are mapped in memory The chapter also described the test bed used for kernel development 24 Chapter 5 Hardware 25 Chapter 6 Software This chapter contains a description of the software used in the implemen tation of the kernel This includes the compiler toolchain the debugger and the considerations done when choosing development tools 6 1 Introduction As mentioned earlier the obvious choice for a C compiler is to use the C compiler included in GCC GNU Compiler Collection This may sound easy but as it turns out it is very difficult to find a good version of the compiler for the MIPS architecture The problem is that there are so many different versions and every developer is using his own patched version of the toolchain There is no central place where patches are gathered so it is a difficult job to collect information about creating a good working toolchain Another problem is that when a new version of the GCC is released it does not have MIPS as it primary target and it will most likely not compile for this architecture without patching So the option to select the latest and greatest release could lead to problems 26 Chapter 6 Software 6 2 The different toolchains In the following some of the most important toolchains will be described A toolchain includes a cross compiler linker assembler and sometimes even C library Hard Hat Linux Monta Vista 22 is a company
43. 0 define STO_CU1 0x20000000 define STO_CU2 0x40000000 define STO_CU3 0x80000000 define ST0 XX 0x80000000 MIPS IV naming Bitfields and bit numbers in the coprocessor 0 cause register 110 Appendix B Source code Refer to your MIPS R4xx0 manual chapter 5 for explanation define CAUSEB_EXCCODE 2 define CAUSEF_EXCCODE 31 lt lt 2 define CAUSEB_IP 8 define CAUSEF IP 255 lt lt 8 define 8 define CAUSEF_IPO 1 lt lt 8 define CAUSEB IP1 9 define CAUSEF_IP1 1 lt lt 9 define CAUSEB IP2 10 define CAUSEF_IP2 1 lt lt 10 define CAUSEB_IP3 11 define CAUSEF_IP3 1 lt lt 11 define CAUSEB IPA 12 define CAUSEF_IP4 1 lt lt 12 define CAUSEB_IP5 13 define CAUSEF_IP5 1 lt lt 13 define CAUSEB_IP6 14 define CAUSEF IP6 1 lt lt 14 define CAUSEB IP7 15 define CAUSEF_IP7 1 lt lt 15 define CAUSEB IV 23 define CAUSEF_IV 1 lt lt 23 define CAUSEB CE 28 define CAUSEF_CE 5 lt lt 28 define CAUSEB BD 31 define CAUSEF BD 1 31 Bits in the coprozessor config register define CONF CM CACHABLE NO WA 0 define CONF CM CACHABLE WA 1 define CONF CM UNCACHED 2 define CONF CM CACHABLE N define CONF CM CACHABLE C define CONF CM CACHABLE COW 5 E C E A define CONF CM CACHABLE define CONF CM CACHABLI CCELERATED 7 define CONF_CM_CMASK T define CONF_DB 1 lt lt 4
44. 0u n timer cur restore flags flags return 0 int timer waitfor t timerx pT Dont wait if its not active x if pT gt state ACTIVE return 1 Wait for the timer to expire x semaphore wait amp pT semaphore return 0 void timer cancel t timer Remove the timer from the timer list x if pT gt state ACTIVE list remove amp timer list amp pT timer elem Reset the timer s state pT state IDLE Release the semaphore semaphore signal amp pT gt semaphore void timer interrupt t timer pT t list element pLE unsigned int offset tmp timer offset Run through the timer list and decrement the counter Mark all of the expired timers done remove them and signal there semaphore for pLE timer list pFirst pLE NULL pLE pLE gt pNext pT timer base pLE pT gt count timer offset T 167 if pT gt count 0 if pT gt state WAITING x This counter has expired x semaphore signal amp pT gt semaphore Restart or idle the timer depending on its type if pT gt type PERIODIC 4 pT gt state ACTIVE pT gt count pT gt length else list_remove amp timer list amp pT timer elem pT gt state IDLE else if pT gt count lt timer offset Get the closest deadline x offset
45. 1 Timer driver On Intel based architectures it is normal to create a timer using the 8253A chip which is placed on almost all Intel based motherboards In the 10 7 Kernel drivers 77 MIPS64 CPU there are two registers which are very useful when creating a timer namely the count and compare registers These two registers will be used for the timer implementation instead of the usual timer hardware The count register acts as a timer incrementing by one every other clock cycle whether or not an instruction executed The count register can be written for diagnostic purposes as it is during boot in this kernel This register is 32 bits long The compare register is used in conjunction with the count register The compare register contains a value which does not change unless explicitly updated by software When the value of the count register is equal to the value of the compare register hardware interrupt 5 is asserted and the interrupt pending bit is raised in the cause register Hardware interrupt 5 is asserted and continues to be asserted until the compare register is written to by software This register is also 32 bits long From the kernel users point of view the interface to the timer driver consists of four functions which are implemented in the file timer c timer_setup This function initializes a timer structure timer_start This function starts the timer timer_waitfor This function blocks the process unt
46. 16 field_ width precision flags 135 continue case if qualifier 1 long ip va arg args long xip str buf else if qualifier Z unsigned long ip va_arg args unsigned long xip str buf else int ip va_arg args int str buf continue case xstr 96 continue integer number formats set up the flags and break x case 7 base 8 break case X flags LARGE case x base 16 break case d case 717 flags 2 SIGN case u break default xstr 96 if fmt str fmt else fmt continue if qualifier L num va arg args long long else if qualifier num va arg args unsigned long if flags amp SIGN num signed long num else if qualifier Z num va arg args unsigned long else if qualifier h num unsigned short va_arg args int if flags amp SIGN num signed short num else 136 Appendix B Source code num va arg args unsigned int if flags amp SIGN num signed int num str number str num base field width precision flags str 0 return str buf sprintf Format string and place it in a buffer buf The buffer to place the result into fmt The format string to use args Arguments for
47. 4 volatile unsigned char xuart data unsign swap8addr MALTA GT PORT BASE Wait for transmit hold register empty while uart sr amp UART_LSR_THRE 0 nothing Now write the data directly uart data c return 1 Print string to the serial console void serial print char xbuf char xp long flags save and cli flags for p buf p p if p n serial_putchar r serial_putchar xp restore flags flags handler for the serial interrupt x void serial_interrupt void void serialinit void long flags ne state the GNU General Public License See the file COPYING in the main directory of char x TTYS1 UART LSR ed char x TTYS1 UART TX 160 Appendix B Source code Status for ine Control Register LCR x volatile unsigned char uart_Icr unsigned char swap8addr MALTA_GT_PORT_BASE TTYS1 UART_LCR Divisor latch volatile unsigned char uart_dll unsigned char swap8addr MALTA_GT_PORT_BASE TTYS1 UART DLL volatile unsigned char xuart_dlm unsigned char swap8addr MALTA_GT_PORT_BASE TTYS1 UART_DLM Modem control register x volatile unsigned char uart_mcr unsigned char swap8addr MALTA_GT_PORT_BASE TTYS1 UART_MCR Clean interrupts while configuring serial port They should actually
48. 5 Hardware 5 2 Test bed Figure 5 3 shows the development test bed used for kernel development The workstation is connected to a LAN and has server installed on which the kernel is placed From the workstation to the Malta system is serial line used for remote debugging facilities included in YAMON The Malta system is also connected to the LAN and is with help from YAMON able to download and run the kernel served on the TFTP server Finally there is also a serial line connecting the Malta system with an old vt220 terminal This terminal is used as console output and to interface and control the YAMON monitor The serial line connected to the old terminal could just as well be connected to the workstation but due to the lack of a second serial port in the workstation the good old terminal came in handy again MIPS Malta system LAN Remote debugging Yamon and console output QOO OOOO X yy 5 X AAA OOOO MOR 0009 Q MN 9 xXx d 9 X SE Workstation with debugger Old 220 terminal Figure 5 3 Development test bed 5 3 Summary 23 5 3 Summary This chapter has given a short description of the hardware which should be sufficient to understand the kernel implementation The main focus has been on how the different components interfaces and
49. 8 Appendix B Source code process current gt stack pointer sp stack pointer has offset 32 ld a0 process current sd sp 32 a0 interrupt nested 4 lw a0 interrupt nested nop addu a0 a0 1 Sw a0 interrupt nested get irq mask x PROM_PRINT _INT n 50 CPO CAUSE nop First we check for 4 timer interrupt x andi a0 50 CAUSEF IP7 beq a0 zero not timer delay slot check hw0 interrupt andi a0 s0 CAUSEF IP2 We got a timer interrupt move a0 sp jal timer interrupt nop delay slot j return nop delay slot not timer beq a0 zero not hardware nop delay slot We got combined hardware level zero interrupt x Update the interrupt mask for nested interrupts x TO BE DONE x Now just enable interrupts again x STI move a0 sp jal interrupt hw nop delay slot j return nop delay slot not_hardware mistake This is possible what happen is that the time we take the exception the IRQ pin goes low so just leave if this is the case Another option is that the interrupt masks are fucked up 149 PROM PRINT Missed an interrupt n sj return nop delay slot END mipsIRQ LEAF return set noat set reorder Disable interrupts CLI interrupt nested lw a0 interrupt
50. 99 by Ralf Baechle ifndef ASM BYTEORDER define ASM BYTEORDER H include lt asm types h gt ifdef _GNUC_ if defined _STRICT_ANSI_ defined _KERNEL__ define BYTEORDER HAS U64 Ffendif tendif _GNUC__ if defined MIPSEB include lt linux byteorder big_ endian h gt elif defined MIPSEL include lt linux byteorder littleendian h gt yelse error MIPS but neither nor MIPSEL endif endif x ASM BYTEORDER H x 104 Appendix B Source code include cpu h CPU functions Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details ifndef CPU define CPU H Assigned values for the product ID register In order to detect a certain CPU type exactly eventually additional registers may need to be examined 7 define PRID_IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID_IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM 7 define PRID IM define PRID IM P R2000 0x0100 P R3000 0 0200 Same as 2000 P R6000 0 0300 Same as
51. AN EMBEDDED SYSTEMS KERNEL Lars Munch Christensen IMM THESIS 2001 47 lt lt Trykt af IMM DTU Foreword The present report is the result of master thesis entitled Embedded Systems Kernel The project was done from mid February until the end of October 2001 I would like to use the opportunity to thank all the parties who have con tributed to this project special thank you goes to my wife Eva who has used valuable time finding spelling and grammar errors in the report I would also like to thank MIPS for sponsoring hardware and thank you to the people at the linux mips mailing list for valuable MIPS information October 26th 2001 Lars Munch Christensen Abstract The process of composing a development system environment suitable for embedded system development in a Free Software environment is dis cussed The theory of protection and sharing of memory in a single space operating system is presented design for small embedded systems nel is presented and the actual implementation of the kernel is described generalized bootstrap is proposed The actual implementation of the kernel is included in the appendix Keywords Embedded systems kernel development and implementation single address space operating systems generalized bootstrapping Contents 1 1 Executive Wong badd B BORGO TII ES l2 e e 2 I
52. PIIX4 OCW2 ILS 8 define PIIX4 OCW2 ILS 9 define PIIX4 OCW2 ILS 10 define OCW2 ILS 11 define PIIX4 OCW2 ILS 12 define PIIX4 OCW2 ILS 13 define PIIX4 OCW2 ILS 14 define PIIX4 OCW2 ILS 15 NOOBRWNFONDUBRWNFO define PIIX4 0CW3_SEL 0x1 lt lt 3 113 define PIIX4 OCWS3 IRR 0x2 define PIIX4 OCW3 ISR 0x3 x PIIX4 x include printf h Printf Header is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details This file ifndef PRINTF H define PRINTF H include lt arch stdarg h gt Format a string and place it in a buffer int sprintf char buf const char fmt Send print message to the console driver Used for debug only void printf char fmt endif PRINTF H include process h Process header file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details This file ifndef PROCESS H define PROCESS H include lt list h gt Size of the kernel idle process stack in dwords define KERNEL_STACK 2000 The maximum number of processes x define MAX PROCESSES 20 Process states define RI EADY 0 define RUNNING 1 114 Appendix B S
53. R3000A P_R4000 0x0400 P R6000A 0x0600 P R10000 0x0900 P_R12000 0x0e00 P_R4300 0x0b00 P R12000 0x0e00 P_R8000 0x1000 P_R4600 0x2000 P_R4700 0x2100 P_R4640 0x2200 P_R4650 0x2200 Same as R4640 P_R5000 0x2300 P_SONIC 0x2400 P_MAGIC 0x2500 P RM7000 0x2700 P_NEVADA 0x2800 P_5KC 0x8100 P 20KC 0x8200 void cpu_init void void cpu status void void cpu_probe void void cpu speed void fendif x CPU H x include interrupt h Interrupt functions Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details 105 ifndef INTERRUPT H define INTERRUPT H include regoffset h extern int interrupt nested typedef void interrupt handler void void interrupt register int irq interrupt handler handler void interrupt hw reg offset regs void interrupt timer struct reg offset regs void interrupt init void tendif INTERRUPT H include kernel h Kernel header Global kernel stuff This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details ifndef KERNEL H define KERNEL H void panic char xbuf endif KERNEL H x include Icd h LCD Display driver header Th
54. RTC DAT REG rtc add addr rtc dat data x Probe for cpu type void cpu probe void unsigned long type read 32bit cpO register CPO_PRID switch type amp Oxff00 case PRID IMP 5KC printf The CPU type is 5KC n break default panic PANIC Unsupported CPU n Find the cpu speed void cpu speed void unsigned int cpu freq bus freq Set Data mode binary rtc write rtc read RTC CONTROL RTC DM BINARY RTC_CONTROL 138 Appendix B Source code printf calculating cpu speed n Start counter exactly on falling edge of update flag while rtc read RTC REG A amp RTC UIP while rtc read RTC REG A amp RTC UIP Start r4k counter x write 32bit cp0 register COUNT 0 Read counter exactly on falling edge of update flag while rtc read RTC REG A amp RTC_UIP while rtc read RTC REG A amp RTC_UIP Read the r4k counter and calculate the offset The value in timer offset is needed in timer driver init timer offset read 32bit cpO register CP0 COUNT bus freq timer offset 5000 Round off x bus freq bus_freq 10000 CPU freq 2 bus timer freq cpu freq bus freq bus freq printf CPU Bus frequency d 02d d 02d MHz n cpu freq 1000000 cpu_freq 1000000 100 1000000 bus freq 1000000 bus_freq 1000000 100 1000000
55. RedBoot This is an open source boot loader called YAMON and it is described futher below Whether or not a boot loader is really necessary on an embedded system all depends on the BIOS features provided with the hardware and the actual location of the kernel 9 3 Bootstrapping MIPS Above it has been generalized how bootstrapping is done on a general system with at least some memory and a CPU Now the low level details of how to cool boot the MIPS Malta system will be described During a power on or cold reset the SI_ColdReset signal is asserted The SI_ColdReset is a hard reset signal and the assertion of the SI ColdReset signal completely initializes the internal state machines of the 5Kc CPU without saving any state information When SI_ColdReset is deasserted a reset exception is taken by the 5Kc CPU When the 5Kc CPU takes the reset exception it is hard coded to execute the code located at the address OxFFFF FFFF BFC0 0000 and this is where the YAMON boot loader is located When YAMON gets the control of the CPU it first disables the interrupts determines the endianess of the system initializes the status register of the CPU creates a small stack and then jumps to the first C function which 60 Chapter 9 Bootstrapping does the rest of the initialization Furtunately the chipset on the board is able to initialize the RAM so this step can be ignored This should be compared with the traditional MIPS startup sequen
56. S list waiting pFirst if process waiting NULL 4 Wake the first process on the waiting list and insert into our ready list list remove amp pS gt list waiting amp process waiting gt process elem process_waiting gt state READY amp process list amp process_waiting gt process_elem printf wakeup id amp process_waiting gt process_elem Bump down our own priority and reorder if necessarily x if process_current gt priority process_current gt orig_priority process_current gt priority process current gt orig_priority process reorder amp process list amp process current process elem Now lets call schedule releasing a semaphore might schedule When the semaphore is released the caller begins executing here else pS gt state FREE restore flags flags kernel serial c 159 Putting things on the screen serial line No setup of UART just assume YAMON left in sa Bit of a hack but it works This file is subject to the terms and conditions of this archive for more details include lt arch stdarg h gt include lt addrspace h gt include lt serial h gt include lt system h gt int serial putchar char c volatile unsigned char uart sr unsigned swap8addr MALTA_GT_PORT_BASE
57. S transfers the CPU control to the boot loader or the operating systems kernel itself 2 In the second step the boot loader is executed Whether this is nec essary or not depends on the BIOS but the boot loader provides a convenient way to choose between which different system configu rations to run This could be different operating systems different kernel versions or different kernel configurations by passing options to the kernel 3 The third and last step executed on system startup is the kernel bootstrap One could expect this part to be small but on the contrary this part is rather big since much of the hardware is initialized all over again It is generally believed that the BIOS is filled with bugs and therefore the hardware state cannot be trusted when the kernel bootstrap gets control of the CPU so the hardware is initialized once again s one can imagine there are huge differences in hardware and the function ality provided in the BIOS by the hardware manufacturer and therefore the system startup is different from system to system However due to the uncertainty of the BIOS functionality and the hardware state after the BIOS has been executed an increasingly amount of the hardware initial ization code is going into the modern operating system s kernel bootstrap s a consequence to this the BIOS has become almost negligible in the system startup Another consequence is that the kernel bootstrap can be generaliz
58. STORE_SP ld sp R SP sp endm macro RESTORE_ALL RESTORE SOME RESTORE AT RESTORE_TEMP RESTORE STATIC RESTORE SP endm Disable interrupts macro CLI push reorder t0 CPO STATUS set pop li tl STO ERL STO_EXL STO IE or tO 61 xori t0 STO_ERL STO_EXL STO IE mtc0 t0 CPO STATUS endm Enable interrupts macro STI push reorder t0 CPO STATUS set pop li tl STO_ERL STO_EXL STO IE or tO 61 xori t0 STO ERL STO EXL mtc0 t0 CPO STATUS endm Just move to kernel mode and leave interrupts as they are macro KMODE push reorder mfc0 t0 CPO STATUS set pop li tl KSU USER KSU SUPERVISOR STO ERL STO EXL or tO t1 xori t0 KSU USER KSU SUPERVISOR STO ERL STO EXL mtc0 t0 CPO STATUS endm tendif x STACKFRAME H x 126 Appendix B Source code include stddef h Standard definitions header This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of x this archive for more details ifndef STDDEF H define STDDEF H define NULL void x 0 endif STDDEF_H include system h functions for setting clearing interrupt flags Functions are taken from the Linux kernel This file is subject to the terms and conditions of t
59. Semaphores components The nano kernel components are divided into three different groups Hardware independent kernel components These compo nents are written in C and should be portable without changing the code Partly hardware dependent kernel components These are the components written in C but they still depend some what on the hardware If implemented carefully the com ponents could be portable between platforms Hardware dependent kernel components These are the com ponents that have to be implemented in assembly code 44 Chapter 8 Kernel design It could be argued that the Serial I O as well as the Timer component should not be in the nano kernel Serial I O is included for simplicity because the boot console is part of that component If this component eventually becomes a full featured serial driver it should be moved out of the nano kernel into its own process The Timer components have been kept in the nano kernel for performance issues because when a timer in terrupt occurs it should be handled as fast as possible closer look at the Minix kernel revealed that it requires several hacks to circumvent the fact that the timer was placed in its own driver in Minix All the processes has a unique priority associated and its own stack The nano kernel does not have its own stack it uses the stack of the current running process when handling interrupts All processes are started up at kernel boot time and all proce
60. This should never be seen Wn int entry unsigned int argc Number of tokens in argv array char xxargv Array of tokens first is go t yamon env var Array of env variables x unsigned int memsize Size of memory byte count x int i ttimer t Init serial driver x serialinit Init the CPU cpu init Init timer driver timer init Create some processes x process init 2 5 5000 process create process 1 4 5000 Pause to show init status for i 0 i lt 2000000 i do nothing x Test setjmp x printf here 1 n setjmp buf 144 Appendix B Source code printf here 2 n if setjmp buf printf Back in main n else printf First time n foo printf kernel call n process list print amp process list Init interrupts this starts the kernel x interrupt init Schedule the highest priority process x schedule Test timer timer setup amp t timer _start amp t 3000 PERIODIC This is idle loop x while 1 printf Idle process printf idle_ 010u read_32bit_cp0_register OPO COUNT for i 0 i lt 1000000 i do nothing x set cp0 status STO IM IE IRQO IE IRQ1 IE IRQ2 IE IRQ3 IE IRQ4 IE IRQ5 sti 0 return 0
61. _tmp pT gt count timer offset offset tmp Acknowledge interrupt printf timer int 010u_ 010u gt read_32bit_cp0_register CP0 COUNT read 32bit cpO0 register timer cur read 32bit cpO register CPO COMPARE timer offset write_32bit_cp0_register COMPARE timer cur printf 96010uWVn timer cur void timer init void Init the timer list x list_init amp timer list CPU should be initialized before Timer x timer tick per ms timer offset 1000
62. address see figure 10 3 The address is not allowed to be more than 28 bits and has to lie on 32 bit word boundaries since the last two bits are thrown away during the op code generation 31 26 25 0 001000 Interrupt handler address gt gt 2 Opcode for Jump J Figure 10 3 Jump op code construction Normally the cache would have to be flushed after writing the jump op code into the memory but as previously mentioned the cache has been disabled to avoid these sort of problems When the cache is enabled in future versions of the kernel special attention has to be paid to all the places where the kernel writes to memory mapped hardware which is mapped in the cache able memory 10 4 2 Combined hardware interrupt When the interrupt handler receives a combined hardware interrupt the function interrupt hw in interrupt c is called Its primary job is to figure out which device caused the interrupt and then call the appropriate interrupt handler for the device By requesting information from the 82C59 interrupt controller the IRQ which triggered the combined hardware interrupt is found By using this 74 Chapter 10 Kernel implementation IRQ as an index in a interrupt handler table the right handler can be found and called in constant time 10 4 3 Interrupt interface The interface to the interrupt component consists of only two functions see table I0 3 These are implemented in the file interrupt c i
63. al This register is set to the address of an array of string point ers holding the arguments for example argv 0 go and so forth a2 This register holds a pointer to a table holding YAMON environment variables a3 This register holds the memory size of the SDRAM mounted on the core card ra This register holds the return address that the kernel can use to return to YAMON when it is done running This will never be used Table 9 1 Initial Application Context The registers a0 through a3 are argument registers hence if they are un changed in the kernel bootstrap the first C function can have the following prototype which gives easy access to the kernel parameters int entry unsigned int argc Number of tokens in argv array char xxargv Array of tokens first is go t yamon env var env Array of env variables x unsigned int memsize Size of memory byte count Listing 9 1 Prototype for first C entry An example of the use of kernel parameters could tell the kernel which serial port the serial terminal is connected to 64 Chapter 9 Bootstrapping Besides providing the functionality of loading kernels YAMON also pro vides a set of functions which can be used from the kernel The function ality includes functions to register exeception service routines reading and writing to the serial port Even though these functions would be very con vinient to use they are not use
64. another approach to this problem The Malta system comes with a Real Time Clock RTC included in the PIIX4 chip see figure 5 2 This RTC is updated every second and at every update a flag is set in the RIC By using the flag and the count register the CPU speed is easy to get 1 Wait for the flag to be raised 2 Reset the count register 3 Wait for the flag to be raised again 4 Read the value count register The count register now contains half the numbers of clock cycles the 5Kc CPU has in one second It is half the numbers of clock cycles since the count register is only updated at every other clock cycle By multiplying this number by two the result is the CPU speed in Hz The resulting probed CPU speed is 40MHz Running several tests verify that this method is very precise with a deviation of only 1 Hz 9 6 Bootstrapping the kernel using YAMON 63 9 6 Bootstrapping the kernel using YAMON As mentioned above YAMON serves both as a BIOS and a boot loader for the Malta system On power on the Malta system will initialize and end up in the YAMON shell From this shell the command load can be used to load a kernel and the command go to run a kernel The state of the CPU when the kernel bootstrap begins is called the Initial Application Context and is as follows Register Value a0 This register is set to the argument count from the YAMON shell The arguments are tokens seperated with white spaces
65. as several processes running it is feasible to introduce the concept of shared memory between the processes common way to get mutual exclusion to shared memory is by introducing semaphores Scheduling The scheduler should be simple and the interface to the sched uler should be generic This will enable one to write a completely different scheduler without dealing with architecture specific issues and without changing the nanokernel The scheduler itself should be kept as simple as possible and is not considered as the important part of this project Modularized design The kernel itself will not maintain the protection between processes Instead protection will be introduced by using an modularized design in the kernel Different solutions to the problem will be discussed and one will be implemented Global exception handling Using exceptions in an embedded system to handle failures in modular manner could be of great advan tage in bug finding and system recovery Different methods for doing exceptions in C will be analysed Portability Portability is also an important property of the kernel Im plementing the kernel as a nanokernel is definitely a huge step in the right direction But other things such as the size of pointers and the addressing should be paid attention The use of assembler should be kept at a minimum C Compiler requirements The kernel will be licensed under the GPL license which is the license of the GNU project
66. be off at this point so this is just paranoid save and cli flags Set 1 stop bit no parity 8 data bits no break an raise Divisor latch access bit uart lcr UART LCR WLENS UART LCR DLAB Set 19200 baud 0x06 uart dlm 0x00 Lower Divisor latch access bit x uart lcr xuart_lcr amp UART LCR DLAB Initialize interrupts interrupt register irq serialinterrupt Restore interrupts restore flags flags V T220 term clear home escape sequence is ESC 2J ESC 0 0H x serial print 033 1332J 033 1330 0H kernel setjmp S Implementation of setjmp and longjmp for MIPS64 This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details ox X X X include lt asm h gt include lt regdef h gt int setjmp jmp buf LEAF setjmp 161 sd s0 O a0 sd sl 8 a0 sd s2 16 a0 sd s3 24 0 sd 4 32 0 s5 40 0 s6 48 0 s7 56 0 160 0 sd fp 168 a0 sd ra 176 a0 move v zero j ra END setjmp void longjmp jmp buf int LEAF longjmp ld s0 0 0 ld sl 8 a0 ld s2 16 a0 ld s3 24 a0 ld 4 32 0 ld s5 40 0 ld s6 48 0 ld s7 56 a0 ld sp 160 a0 ld fp 168 a0 ld ra 176 a0 bne al zero lf li al l 1 mov
67. betragtes som en v sentlig del af projektet 91 Bibliography SMcS FDC37817 Super I O Controller datasheet Atmel AVR Microcontrollers STK500 Starter Kit and Development system Atmel AT91EB40 Evaluation Board Users Guide Galileo Technology GT 64120A System Controller for RC4650 4700 5000 and RM526x 527x 7000 CPUs Intel 82371AB PCI TO ISA IDE XCELERATOR PIIX4 MIPS Technologies CoreLV User s Manual Document Number MD00007 Revision 02 06 MIPS Technologies Processor Core Family Software User s Manual Document Number MD00012 Revision 02 04 MIPS Technologies 5Kc Processor Core Datasheet January 15 2001 GNU linker Id version 2 10 91 info pages GNU Automake version 1 4 info pages S Tan et al An Object Oriented Nano Kernel for Operating System Hardware Support Proceedings of the Fourth IWOOOS IEEE Computer Society Aug 1995 Lund Sweden 92 BIBLIOGRAPHY 12 13 14 15 16 17 18 19 20 21 22 23 24 Jeffrey S Chase Henry M Levy Michale J Feeley and Edward D Lazowska Sharing and Protection in a Single Address Space Oper ating System Department of Computer Science and Engineering FR 35 University of Washington Seattle WA 98195 USA Design and implementation of an Object Oriented 64 bit Single Address Space Microkernel Kevin Murray Tim Wilkinson Peter Osmon SARC City University Ashley Saulsbury Swedish Institute of C
68. ce as described in See MIPS Run 20 which is as follows Reset exeption entry point Initialize status registers Initialize and check the RAM integrity Make contact with the outside world Initialize stack and registers to call C function Initialize the cache ove EmRer5r The comparison shows that YAMON follows the traditional MIPS startup sequence almost to the point except for the fact that contact to the outside world is postponed in YAMON until all devices are initialized The C function that takes the Malta system through the rest of the initial ization is slightly simplified as follows 1 Initialize the PITX4 chip e Initialize the ISA bus on which the Super I O Controller is con nected to the the chip see figure 5 2 Initialize the serial ports Initialize the parallel port Initialize the keyboard and mouse IRQs e Enable IO access to Power Management device 2 Initialize the peripherals e Initialize the exception handlers e Initialize the real time clock e Initialize the PCI bus memory mapping e Initialize the network adapter 3 Start the YAMON shell As noted above the traditional MIPS startup sequences and the YAMON startup sequence are very similar but it should also be noted that these startup sequences fit very nicely into the generic startup sequence described in section 9 1 A study of bootstrapping a PowerPC also turned out to fit in the generic startup sequence as well 9 4 MIPS vs
69. char display string AN EMBEDDED SYSTEMS KERNEL define DISPLAY COUNT sizeof display string 8 void process_2 void t_timer t int display_count 0 timer setup amp t while 1 timer start amp t 5000 PERIODIO timer waitfor amp t Display message x lcd message amp display string display count4 if display count MAX DISPLAY COUNT display count 0 kernel timer c Timer driver Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include regoffset h include lt system h gt include lt timer h gt include lt mipsregs h gt Amount to increment compare reg unsigned int timer offset Self explain able unsigned int timer tick per ms What counter should be at next timer irq x static unsigned int timer cur List of timers tlist head timer list 165 Setup new timer structure void timer setup t timerx pT Start a timer pT state IDLE pT type ONCE pT gt length 0 pT gt count 0 semaphore_setup amp pT gt semaphore int timer start t_timer pT unsigned int msec int timerType long flags unsigned int tmp t_list_element pLE Do not start it more than one time if pT gt state IDLE retur
70. contains a programmable Baud Rate Generator that is capable of dividing the internal UART clock by any divisor from 1 to 65535 The clock runs at 1 8462Mhz and the output from the Baud Rate Generator is 16 times the baud rate therefore to set the desirable baud rate the divisor is calculated like this U ART clock speed Baud rate divisor aud rate divisor 16x bpe Inserting the numbers in question the resulting baud rate divisor is 1846200Hz 16 19200bps The baud rate divisor is therefore 6 when a baud rate of 19200 is desired This value should be written to the divisor registers The high register with the value 0 and the low with the value 6 These registers are the same as 80 Chapter 10 Kernel implementation the transmitter and receiver registers so a special bit DLAB has to be set high to tell the serial port that the baud rate is going to be set The rest of the configuration of the serial port is done by writing to the Line Control Register The interrupt is not initialized since the input is not read anyway Initial ization of this interrupt should be located in the function serial init along with the rest of the serial terminal initialization Serial terminal driver interface From the kernel users point of view the interface to the serial terminal driver consists of two functions see table 0 8 Through these functions special control characters can be sent to the serial terminal to control cur
71. control input devices such as keyboard and mouse as well as standard serial and parallel ports The CBUS exists to allow the CPU to access peripherals which have to be available before the CPU bus is configured for instance the flash memory YAMON is booting from The CBUS is also used for those peripherals that require simple low latency access e g the ASCII display The largest difference from using peripherals on the MIPS Malta and on a standard PC is that all devices are memory mapped This really eases the task of controlling hardware tremendously The physical memory mapping is shown on table 5 1 In some memory areas the mapping depends on the implementation of the CoreLV card and of the software configuration of these areas but the table shows a typical configuration Base address Size Function 0000 0000 128Mb Typically SDRAM 0800 0000 256Mb Typically PCI 1800 0000 62Mb Typically PCI 1 0 0000 2 Typically system controllers inter nal registers 1C00 0000 32Mb Typically not used 1E00 0000 4Mb Monitor flash 1 40 0000 12Mb reserved 1F00 0000 12Mb Switches LEDs ACSII display soft reset FPGA revision number CBUS UART tty2 General pur pose I O I C controller 1F10 0000 11Mb Typically system controller specific 1FC0 0000 4Mb Maps to monitor flash 1FD0 0000 3Mb Typically system controller specific Table 5 1 Malta physical memory map 22 Chapter
72. count The CPU mounted on the CoreLV card is a MIPS64 5Kc 7 CPU which is 64 bit MIPS RISC microprocessor core that is designed for high performance low cost and low power embedded systems The CPU ex ecutes the MIPS64TM instruction set architecture but also provides 32 bit compatibility mode in which code compiled for MIPS32TM processors can run unaltered Features of the 5Kc CPU include e Two pipelines One six stage integer pipeline and a separate execu tion pipeline for multiply and divide operations The two pipelines operate in parallel e System Controller Coprocessor This is responsible for virtual to physical address translation and cache protocols the exception control system and the operating modes Kernel Supervisor User and Debug e Cache Controller The cache controller supports several different cache protocols write around write through and write back Write around is the same as disabling the cache The Memory Management Unit MMU in the 5Kc CPU provides a 64 bit virtual address space subdivided into four segments Two for the Kernel mode one for Supervisor mode and one for User mode To provide com patibility for MIPS32 programs a 2 byte compatibility address space is defined For further information on the MMU refer to 5Kc Processor Core Datasheet 8 20 Chapter 5 Hardware 5 1 2 The motherboard The motherboard contains several components and how they interact are roughly show
73. ctivities should be expressed by means of the nanokernel s routines and both voluntary and forced process switch should be supported The concrete goal for the project is to implement a nanokernel and some subsystems exercising it so far that an embedded system is able to coldboot and use a simple external device The project should also provide a useful basis for further work 2 3 Motivation for the project There are several motivations for the project both personal and educational My personal motivation for the project is a long time interest in kernel development and operating systems To get the opportunity and time 2 4 Organization 5 to build a kernel is absolutely the best way to learn practical embedded systems implementation The educational motivation was to try and create a very small kernel providing only the necessary features for use in an embedded system with parallel processes Perhaps the most important motivation was to start up a kernel devel opment project on which several different kernel related projects could be based This project is the first project in a hopefully long series of projects concerning the construction of nanokernels for embedded systems 2 4 Organization The report contains 12 chapters two appendixes and an annotated bibli ography The 12 chapters are divided into four parts The first part that consists of chapters 1 through 6 contains introductory contents Chapter 7 presents
74. d in this kernel The reasoning behind this decision is that a kernel should control the hardware itself and no rely on system specific functions which the YAMON provided functions are 9 7 Kernel bootstrap When the kernel bootstrap is executed it goes through the following steps this is implemented in the file start 5 1 Disable interrupts and disable the cache 2 Setup a stack the address of the stack top is hard coded in the linker script Initialize the bss section to zero see figure 10 2 4 Call the first C function entry which does the rest of the initial ization pa This bootstrap also fits nicely into the generic startup sequence described in section 0 1 The first C function that is called is named entry and is implemented in the file kernel c This function takes the kernel through the rest of the initialization 1 Initialize the serial terminal driver This is done already here because it enables kernel to write status messages to the terminal during the rest of the initialization Initialize CPU and probe CPU type and speed Initialize timer driver Initialize the process manager and register the processes Initialize and enable interrupts Call schedule and the kernel is up and running Ao wh It should be noted here that not all peripherals that are used in the kernel are initialized during the kernel bootstrap This includes setting up the memory mapping of the PCI bus and initializing the
75. d the problem simply by not using any floating point operations at all If floating point for some reason is needed for this kernel I would recommend using newlib since it is much easier to integrate than a real kernel floating point emulator and you get the benefit of the rest of newlib as well i e memory copying functions string comparing functions etc 6 4 Remote debugging Since the MALTA board supports remote debugging one might as well take advantage of this A debugger is not a part of the SGI Linux project cross development toolchain so this should be retrived elsewhere One option is to use the nice debugger from the GNUpro package if one has already invested in the GNUPro package see figure 6 1 It has a graph ical interface for viewing registers stacks memory and source code The graphical interface is build on top of the GNU debugger and is very usable Another option is to use standard GNU debugger gdb which is free It may not have a nice graphical user interface but it works just as well There exists free graphical frontends for gdb but these have not been investigated The only downside to gdb is that you have to build it yourself but compared to building GCC this is an easy job Using a debugger for kernel development does not come without costs There must be some kernel support for the debugger otherwise you will only be able to execute the kernel through the debugger and nothing else See Kernel impl
76. define t3 11 115 Z define t4 define t5 define t6 define t7 define s0 7 define 51 7 define s2 define s3 define 54 define s5 define s6 define s7 define t8 define t9 define k0 define 7 define gp 7 define sp 7 define fp define s8 define endif REGDEF H 31 caller callee caller callee kernel global saved x saved x saved x address for PIC temp temporary x pointer caller saved for PIC x stack pointer x frame pointer x callee saved x return address x include regoffset h MIPS regs offsets is subject to the terms and conditions of the GNU General See the file COPYING in the main directory of Public License this archive for more details This file ifndef REGOFFSET define RI EGOFFSET H ifndef LANGUAGE ASSEMBLY MIPS register offsets for use in C typedef struct Saved main processor registers unsigned long zero unsigned long at unsigned long v0 unsigned long v1 unsigned long a0 unsigned long al unsigned long a2 unsigned long a3 unsigned long t0 unsigned long t1 unsigned long t2 unsigned long t3 unsigned long t4 unsigned long t5 unsigned long t6 116 Appendix B Source code unsigned long t7 unsigned long s0 unsigned long sl unsigned long s2 unsigned long 53 unsigned long 54 unsigned long s5 unsigned long s6
77. dif SCHED H x include semaphore h Semaphore definitions This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details ifndef SEMAPHORE H define SEMAPHORE H include lt list h gt include lt process h gt Semaphore state define FREE 0 define LOCKED 1 typedef struct t list head list waiting Waiting processes list x int state Semaphore state t process owner process using the semaphore t_semaphore void semaphore setup t semaphorex pS void semaphore_wait t_semaphore pS void semaphore signal t_semaphore pS endif SEMAPHORE H include serial h This header file defines all the registers and settings of the FDC37M817 on the Malta board x Should be compatible with the NS16C550A the 16450 ACE and the NS16C550A This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details ifndef SERIAL define SERIAL H Addressing the Serial Port 120 Appendix B Source code define UART_RX define UART_TX define UART DLL define UART In Receive buffer DLAB 0 Out Transmit buffer DLAB 0 Out Divisor Latch Low DLAB 1 I O Interrupt Enable Reg
78. duler Scheduler responsible for doing scheduling decisions Boot console responsible for console output at boot time Debugger component responsible for debugger hooks in the kernel Interface component responsible for providing a single in terface for accessing the hardware 8 1 Kernel overview 43 The problem is where to draw the line between the nano kernel and the processes and what hardware to create an abstraction layer for in the nano kernel For example it makes no sense to abstract a PCI bus with a general bus interface since the PCI bus is used the same way whether implemented on a PowerPC MIPS or Intel platform On the other hand it makes perfect sense to abstract I O to devices in the nano kernel since I O to devices is not the same on the Intel platform and the MIPS Idle 1 2 Process Process Process M Processes Partly hardware dependent kernel components Proces Hardware independent M Scheduler anagement kernel components Interrupt Bootstrap Stack Hardware dependent Handling Handling kernel components Figure 8 1 Overview of the kernel On figure an overview of the kernel is shown The dotted line delim its the nano kernel and the small arrows denotes function calls from the processes to the nano kernel shown on the figure process only inter faces the kernel through the I O interfaces and the services provided by the Timer and
79. e vO al j ra END longjmp kernel stack S Switch the stacks Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include include include include include lt asm h gt lt regdef h gt lt regoffset h gt lt mipsregs h gt lt stackframe h gt text LEAF stack switch noreorder Save current state x 162 Appendix B Source code ALL process_old gt stack_pointer sp stack pointer has offset 32 ld a0 process old sd sp 32 a0 sp process current stack pointer stack pointer has offset 32 reorder PROM PRINT SWITCHWn ld a0 process current ld sp 32 a0 noreorder Restore new state and return x RESTORE ALL j ra nop delay slot crucial END stack switch kernel start S Starting point for everything Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include lt asm h gt include lt regdef h gt include regoffset h include lt mipsregs h gt include lt stackframe h gt text LEAF start Disable interrupts CLI Disable kseg0 caching as soon as possible x t0 CPO CONFIG and
80. e for more details include regoffset h include lt mipsregs h gt include lt process h gt include lt kernel h gt include lt system h gt include lt printf h gt Pointer to current running process t process process_current t_process process old Sorted of ready processes t _list head process list Static allocation of the maximum allowed number of processes x static t process process allocated MAX PROCI ESSI ES Incremental process ID x static int nextlId Allocate a stack stack_size should be in dwords static unsigned long process stackalloc int stack size These the hardcoded values from the linker script extern unsigned long sp end extern unsigned long sp Calculate the first free stack top static long stack top unsigned long amp sp 8 KERNEL STACK 151 if stack top 8 stack size lt unsigned long amp sp end panic PANIC Not enough stack n return stack top 8xstack size Prints and verifies process list void process_list_print t list head pHead t process p t list element pNext t list element pPrev NULL int length 0 test the empty list if pHead number if pHead gt pFirst NULL printf First element is not empty and length is 0 n if pHead gt pLast NULL printf Last element is not empt
81. e kernel were handed over to another project student At the time of the handover context switch as described in section 10 5 of Kernel implementation was not fully working thus the kernel was not tested as a whole before the han dover 84 Chapter 11 Status 11 2 Small kernel improvements Besides fixing bugs in the context switch implementation there are several other small improvements which should be done e Every time the kernel changes to the Idle process it does a full context switch This is unnecessary and it increases latency e Currently the cache is disabled Enabling the cache again will give a vast increase in the performance This would require implementing cache flush functions and call these after a write to devices which are mapped in the cache able memory segment e Create a real serial driver interface Chances are that the serial port will be used for other devices than the serial terminal and this would require a clean interface to the serial port e faster scheduler implementation especially the switch from the Idle process can improved 11 3 Large kernel related projects There are several kernel or operating system related projects which could be based on this kernel project To name a few Memory protection Experimenting with memory protection domains as a way of protecting processes from each other For example creating the worlds smallest SASOS Experiment with other types of memor
82. e net The RedBoot Home Page http www redhat com embedded technologies redl The Embedded PowerPC Linux Boot Project http ppcboot sourceforge net 94 BIBLIOGRAPHY Appendix B Source code File Page File Page Makefile include stddef h 126 kernel mips64 link xn include system h include addrspace h include asm h include byteorder h include cpu h include interrupt h include kernel h include lcd h include list h include mipsregs h include piix4 h include printf h include process h include regdef h include regoffset h include rtc h include sched h include semaphore h include serial h include setjmp h include stackframe h I N N include timer h include yamon h kernel cpu c kernel interrupt c kernel kernel c kernel led c kernel list c kernel mipsirq S kernel panic c kernel process c kernel sched c kernel semaphore c kernel serial c kernel setjmp S kernel stack S kernel start S kernel test1 c kernel test2 c kernel timer c on E 96 Appendix B Source code Makefile Kernel installation dir OCC III I I I I I I I 1 I 1 K gt K gt K gt K K K K TFTPDIR kernel I I I I KK KK a a gt K K Active compilation toolchain FE F k k k k k k
83. ecution thread can explicitly attach that segment to its protection domain and thereby permitting the thread to access the segment directly The opposite is also possible a thread can detach a segment from a protection domain and thereby deny access to the segment The attach request can specify a par ticular access directly to a segment for example read only access The attach request can only request the rights that are permitted by the capa bilities at a given segment The attach request is very similar to Linux s BSD mmap system call for mapping files into a process except that in Opal the system rather than an application always chooses the mapped address Another difference from mmap is that in Opal all segments are potentially attachable given the right capabilities so no data is inherently private to a particular thread To enable communication from one protection domain to another a portal is used A portal is an entry point to a protected domain and can be 7 2 Opal 35 Protection domain Protection domain B Figure 7 1 Opal threads can be placed in overlapping protection domains and more than one thread is able to run in each protection domain 36 Chapter 7 SASOS used to implement servers or protected objects Any thread that knows the existence of a given portal can make a system call that transfers the control into the protected domain as
84. ed since it always has to go through a certain number of steps in a certain order no matter what hardware the kernel is running on The kernel bootstrap code suffers from the clash of two opposing but desir able goals On one hand it is robust to make minimal or no assumptions about the state of the hardware and then attemt to initialize and check every subsystem before it is used On the other hand it is desirable to 9 1 Bootstrapping in general 57 minimize the amount of tricky assembler code but changing to a high level language like C tends to require more subsystems to be operational The above classical system startup sequence step 1 through step 3 can be generalized to the following generic startup sequence where 1 is the first code to be executed at power on 1 Initialize CPU registers e g setup addressing modes and disable interrupts 2 Check and initialize RAM This is often a very hard part since RAM chips seems to differ a lot Fortunately modern chipsets do this tedious initialization 3 Now establish some contact with the outside world This could be through the parallel port which has become the most standard way on modern PCs This step is not a necessity but it is convenient to see what is actually going on during startup 4 Initialize a stack registers and call a C function Now the rest of the initialization can be done from C 5 Initialize any other devices needed to load the kernel and load
85. efine PERFORMANCE 25 define _ 26 define CPO CACHEERR 27 define CPO_TAGLO 28 define CPO_TAGHI 29 define CPO_ERROREPC 30 define CPO_DESAVE 31 108 Appendix B Source code Macros to access the system control coprocessor define read_32bit_cp0_register source f int res asm volatile gt mfc0Nt 60 STR source r res SE define write_32bit_cp0_register register value asm__ volatile mtc0 t 0 STR register Fk re r value aa R4x00 interrupt enable cause bits 7 define IE SWO 1 lt lt 8 define IE SW1 1 9 7 define IE IRQO 1 lt lt 10 define IE IRQ1 1 lt lt 11 define IE IRQ2 define IE IRQ3 1 lt lt 13 define IE IRQ4 3 define IE IRQ5 R4x00 interrupt cause bits define C_SWO 1 lt lt 8 define C_SW1 1 lt lt 9 define C_IRQO 1 lt lt 10 define C IRQ1 1 lt lt 11 define 2 1 lt lt 12 define C_IRQ3 1 lt lt 13 define C_IRQ4 1 lt lt 14 define C_IRQ5 1 lt lt 15 ifndef LANGUAGE ASSEMBLY Manipulate the status register Mostly used to access the interrupt bits define __BUILD_SET_CPO name register extern inline unsigned int set_cp0_ name unsigned int change unsigned int new unsigned int res res read 32bit cpO register register res amp change
86. ementation chapter for more information about re mote debugging 6 5 Newlib As mentioned above newlib 26 is a C library intended for use in embedded systems It is a collection of several library parts all under the GPL license 6 6 Summary 29 window its The Registers you visually i window reveals maad debug b fhe state of all ve lt registers and assembly n ar vanguage modrhcanons on the fy tabular View of standard conditional and temporary breakpoints The Local Variables window allows 4 you to view and modify vanabies and analyze data structures Figure 6 1 GNUPro debugger In being a C library it contains usefull functions for kernel development especially the string functions memset and strcpy which most likely will be required in the kernel s a part of newlib there is a library called libgloss Libgloss contains code to bootstrap kernels and applications for different architectures including MIPS In this kernel project only small code snippets of the newlib have been used In future work newlib would be a good thing to include especially if the kernel is going to by ported to another architecture since most of the functions in newlib has been tested on a variety of different platforms Also libgloss could save you from writing the bootstrap code all over again 6 6 Summary This chapter has described the different tools for doing MIPS kernel devel
87. esult was a single address space microkernel named Angel Angel is in many ways similar to Opal and many of the design ideas are also a direct derivation of Opal s design Angel has a similar concept of protection domains as the one previously described in the Opal system which is that a protection domain is an execution context for threads see figure 7 2 For some reason Angel groups protection domains together and calls this for a process This grouping serves no real purpose and is 7 3 Angel 37 somewhat misleading since a protection domain is very similar to a normal UNIX process Process A Process B Protection domains AT EN E nm lis AN B _ E Objects Figure 7 2 Protection domains in Angel The protection in Angel is provided on objects which consist of one or more pages of virtual memory Objects cannot overlap nor must they be contained within other objects As with Opal the system manages the objects and not the applications themselves The semantic of an object differs from segments in Opal An object in Angel is an instance of C class whereas a segment in Opal was merely a chunk of memory which could be used by a thread in a protected manor The consequence of using objects instead of segments is that every time a new instance of an object is created it is assigned with capabilities and explicitly protected by the system as the segments are in Opal
88. ffffffffc0000000 define KSEG3 0 xffffffffe0000000 Returns the kernel segment base of a given address define KSEGX a unsigned long a amp 0xe0000000 an address to certain kernel segment define KSEGOADDR a typeof a unsigned long amp 0x000000fffffffffUL KSEGO define KSEG1IADDR a typeof__ a unsigned long a amp 0x000000fffffffffUL KSEG1 define KSEG2ADDR a typeof a unsigned long a amp 0x000000fffffffffUL KSEG2 define KSEG3ADDR a typeof__ a unsigned long amp 0x000000ffffffff UL KSEG3 Memory segments 64bit kernel mode addresses define XKUSEG 0x0000000000000000 define XKSSEG 0x4000000000000000 define XKPHYS 0x8000000000000000 102 Appendix B Source code define XKSEG define CKSEGO define CKSEG1 define CKSSEG define CKSEG3 0 000000000000000 0 xffffffff8S0000000 0 xffffffffa0000000 0 xffffffffc0000000 0 xffffffffe0000000 Memory segments sizes define KUSIZE define KUSIZE 64 define KOSIZE define KISIZE define K2SIZE define KSEGSIZE T 0x0000010000000000 0x0000010000000000 0x0000001000000000 0x0000001000000000 0x000000ff80000000 0x000000ff80000000 endif ADDRSPACE x 27240 27240 27236 27236 max syssegsz include asm h Some useful macros for MIPS a
89. fied time and when the time is up the process waiting for the timer will be put in the ready queue Cyclic timer will when started wait for a specified time and when the time is up the process will be put in the ready queue If a process is not waiting it has probably missed its deadline so to avoid kernel panic the timer will be reset and the process will try to catch the next deadline After this the timer will be reset and start over again Every timer can have one and only one process waiting Initialized timers can be in three states idle active and done Idle state is when the timer is initialized but not started and active is when the timer has been started The done state indicates that the timer is not used anymore and should be removed from the timer list mentioned previously the only time process is in the waiting state is when it waits for a semaphore to be released This also applies to at process waiting for a timer When a timer is started a semaphore associated to the timer is locked when the timer is fired the semaphore is released and the process waiting for the timer can continue The idea of using the semaphores for the timer comes from the Adeos I8 kernel and simplifies timer implementation The speciel case where there is no process waiting to be activated has to be handled gracefully There are two reasons why there can be no processes waiting first the process could have missed its deadli
90. for this first of all they are well tested so most problems are known secondly they are also build for MIPS64 and I would really like for the kernel to run in 64 bit mode and thirdly it is easy to get support for compiler problems It should be noted already here that the MIPS64 linker is very broken but that there are solutions for this 6 3 Floating point The Malta board does not contain a floating point processor and this could potentially lead to problems if floating points are used There are three solutions to this of which the two first are the most common 1 Create floating point emulation in the kernel Every time a process uses a floating point instruction the system traps to the emulator in the kernel This has become the most common way to solve the problem in the Linux world 2 Use the emulated floating point in the C library This is the option called msoft float This does require the C library to be espe cially build with soft floating point Using the C library is not a good idea for kernel development since the C library is huge and there fore not recommended to compile into a kernel for small embedded systems 28 Chapter 6 Software 3 Use the emulated floating point from the small C library newlib Newlib is a small C library created especially for embedded systems this library can be build to emulate floating point and is small enough to include in a kernel More about newlib below I have solve
91. he GNU General x Public License See the file COPYING in the main directory of this archive for more details ifndef SYSTEM H define SYSTEM H extern inline void sti void asm volatile set tnoreorder n t set tnoat n t mfcO t 1 12 n t ori t 1 0x1f n t xori t 1 0xle n t mtcO t 1 12 n t set tat n t set treorder x no outputs x no inputs x 1 memory For cli we have to insert nops to make shure that the new value has actually arrived in the status register before the end of this macro R4000 R4400 need three nops the R4600 two nops and the R10000 needs no nops at all extern inline void cli void X asm volatile 127 set tnoreorder n t set tnoat n t mfcO t 1 12 n t ori t 1 1 n t xori t 1 1 n t mtcO t 1 12 n t nop n t nop n t nop n t set tat n t set treorder no outputs no inputs 7817 memory define save flags x asm volatile set tnoreorder n t mfc0 t 0 12 n t set treorder Psp define __save_and_cli x asm volatile set tnoreorder n t set tnoat n t mfc0 t 0 12 n t ori t 1 0 1 n t xori t 1 1 n t mtcO t 1 12 n t nop n t nop n t no
92. he motivation for this is that everyone interested in using the kernel should be able to get the hardware without being ruined Having cheap development equip ment motivates using it in all kinds of devices such as home build MP3 players Single board computer The development hardware has to be in the cat egory of single board computers A single board computer is a small motherboard with a processor some memory and input output de vices Many single board computers also contains network adapters USB and other peripherals 12 Chapter 4 Choosing hardware Fast stack operations Since the kernel is going to have a microkernel structure it is crucial that the stack operations on the single board computer runs at a decent speed If not the kernel will run too slow and be unusable Fast stack operations are often a matter of good access speed to memory Free tools available Development tools for the given hardware have to come with a free software license which is compatible with the GPL license the kernel is released under In the following the four different single board computers which have been investigated are described 4 2 Intel 8051 Despite its relatively old age the 8051 is one of the most popular micro controllers in use today Many of the derivative microcontrollers that have been developed since are based on and compatible with the 8051 The 8051 is used in everything from DVD drives to smartcards The 8051 is an
93. il the time is up timer_cancel This function cancels a timer This function must be used if the timer is no longer in use Table 10 5 Timer interface 10 7 2 LCD driver The LCD display is a small 1x8 characters wide LCD display mounted on the Malta board The LCD display can be used for debugging purposes or just to show off The driver is extremely simple and is used for writing characters or numbers on the LCD display mounted on the MALTA board The LCD display works by writing to the addresses listed in table The interface to the driver consists of the two functions listed in table 0 7 78 Chapter 10 Kernel implementation Name Offset Function ASCIIWORD 0x000 0010 Writing 32 bit number to this address will cause the LCD display to show the number in hex on the display ASCIIPOSO 0x000 0018 Writing an ASCII value to this address updates position 0 on the LCD display 0x000 0020 Writing an ASCII value to this address updates position 1 on the LCD display ASCIIPOS2 0x000 0028 Writing an ASCII value to this address updates position 2 on the LCD display ASCIIPOS3 0x000 0030 Writing an ASCII value to this address updates position 3 on the LCD display ASCHUPOS4 0x000 0038 Writing an ASCII value to this address updates position 4 on the LCD display ASCIIPOSS 0x000 0040 Writing an ASCII value to this address updates position 5 on the LCD
94. iling This section describes the compilation of the kernel This includes the Makefile the source code layout and the compilation parameters 10 1 1 The Makefile The Makefile for building the kernel is created in a very naive way There is a perfectly good reason for this and that is while the source code is settling it would require to much work to keep changing an very advanced 68 Chapter 10 Kernel implementation build system every time the source code is moved around and files are renamed The Makefile has been created with portability in mind and therefore there are several user configurable options in the Makefile These are listed below TFTPDIR This is where the kernel is placed upon installation The TFTP server must be configured to point here The default is kernel TOOLCHAIN This option sets the tool chain the kernel is compiled with By default it is the tool chain for generating a kernel for big endian MIPS64 ARCH This option sets the architecture for which the kernel is going to be compiled By default this is the MIPS64 architecture ENDIAN This option chooses the endianess The default target is big endian Table 10 1 Options in the Makefile 10 1 2 Source code layout The source code is organized as shown on figure As the figure shows the root of the tree has three branches one for include files one for the kernel and one for the library functions The include a
95. initions for the Interrupt Identification Register define UART IIR NO INT 0x01 No interrupts pending define UART IIR ID 0x06 Mask for the interrupt ID define UART_IIR_MSI 0x00 Modem status interrupt x define UART_IIR THRI 0x02 Transmitter holding register empty define UART IIR RDI 0x04 Receiver data interrupt define UART IIR RLSI 0x06 Receiver line status interrupt define UART IIR CTII 0x0C Character timeout ID interrupt These are the definitions for the Line Control Register LCR x Note if the word length is 5 bits UART LCR WLENS5 then setting UART LCR STOP will select 1 5 stop bits not 2 stop bits define UART LCR WLENS 0x00 Wordlength 5 bits x define UART LCR WLENG 0x01 Wordlength 6 bits x define UART_LCR_WLEN7 0x02 Wordlength 7 bits x define UART LCR WLENS 0x03 Wordlength 8 bits x 121 define UART LCR STOP 0x04 x Stop bits 0 1 stop bit 1 2 stop bits x define UART LCR PARITY 0x08 Parity Enable define UART LCR EPAR 0x10 Even parity select define UART_LCR_SPAR 0x20 Stick parity define UART LCR SBC 0x40 Set break control x define UART LCR DLAB 0x80 Divisor latch access bit These are the definitions for the Modem Control Register MCR define UART MCR DTR 0x01 DTR complement define UART MCR RTS 0x02 RTS complemen
96. ips ENTRY start SECTIONS Default output name Output arch is mips no shit x Entry point of kernel x Code and read only data xxxx 0x80200000 text ftext kernel start o text x text ecode rodata ALIGN 8 etext 0 Initialised data data fdata data ALIGN 8 x lit8 lita sdata ALIGN 8 edata x Here the code should be loaded so we x set the location counter to this x address x Start of code and read only data This must be the first file since x this has the kernel entry point x The rest of the object files x End of code x End of code and read only data x Start of initialised data x Place 8 byte constants here Place 4 byte constants here x Place subsequent data x End of initialised data x 100 Appendix B Source code Uninitialised data fbss Start of uninitialised data x sbss x dynsbss x sbss x sbss x scommon Place small common symbols here bss dynbss bss bss Place common symbols here x sp end Allocate room for stack x ALIGN 8 0x100000 sp 16 end End of unitialised data x These must appear regardless of
97. is needed due to the previous mentioned MIPS64 linker bug G num Puts the global and static items less than or equal to num bytes into the small data or bss sections instead of the normal data or bss section This allows the assembler to emit one word memory reference instructions based on the global pointer gp instead of the normal two words used Us ing this type of global pointer optimization could lead to problems and is therefore eliminated by supplying the compiler with the value 0 for num Tlink script Specifies the custom linker script Table 10 2 Compilation options 10 2 Linking 71 2 Putting the file start o at the very beginning of the linked kernel This file contains the bootstrap 3 Setting the stack size of the kernel This is hard coded in the linker script but could be changed into an option to the linking process 4 Defining a symbol in the kernel which enables the kernel to get the size of the stack available This symbol is called sp end In ISO ANSI C the symbols end edata and etext are elements of the space of names reserved for the user Thus they have to be defined by the linker script to conform to the standard Figure 10 2 shows the layout of the different sections of the linked kernel Stack top sp end Sbss bss Uninialized data 8 end Common symbols edata data Initialized data etext Read only data text Remaining object files s
98. is at least 5e 03Hz The precision of the timer is in the magnitude of 0 5 micro seconds Compared to the traditional timer implementations this is a huge step in the right direction 8 4 Synchronization To introduce synchronization between processes I have decided to use a binary semaphore with a queue of suspended processes which is sorted by priority High Priority Process Medium Priority Process 1 1 1 1 Low Priority Process i 1 1 Time Ss Process blocked Figure 8 3 An example of priority inversion The introduction of semaphores is not without cost Consider the following example 18 on figure 8 3 there are three processes high priority medium priority and low priority Low becomes ready first indicated by the rising edge and shortly thereafter it takes a semaphore which is also used by the high priority process Now when high becomes ready it must block on the semaphore until the low priority process releases it The 48 Chapter 8 Kernel design problem then arises when the medium process becomes ready then it is able to preempt the low priority process and thereby delay the high priority process This phenomena is called priority inversion There are several solutions to the priority inversion problem I have decided to use the Basic Priority Inheritance Protocol PIP In short the protocol works like this When a
99. is file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details ifndef LCD H define LCD H void Icd int unsigned int num void lcd message const charx str tendif LCD H include list h 106 Appendix B Source code Double non circular linked list functions Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General x this archive for more details ifndef LIST H define LIST H include lt stddef h gt The StructOffset macro returns the byte offset of the field field in the structure st define StructOffset st field V long amp st 0 field The StructBase returns a pointer to the structure of type st where ptr is pointing to the filed field in that structure define StructBase ptr st field 5 unsigned charx ptr StructOffset st field typedef struct s_list_element struct s list element pNext struct s list element pPrev t list element typedef struct int number t_list element pFirst t list element pLast t list head define list empty pHead int pHead gt pFirst NULL void list init t list head pHead void list put t list head pHead t list element pEle
100. is locked by a lower priority process the priority of lower priority process is raised to 76 Chapter 10 Kernel implementation the priority of the process wanting the semaphore After this a re schedule is issued e When a process releases a semaphore the process priority is lowered to its original priority and a re schedule is issued All operations in the semaphore implementation which has to be done as an atomic operation has been put in a critical section by disable and enabling interrupts The MIPS CPU has special support for atomic operations but these have not been used because the semaphore implementation would then be hardware specific 10 6 1 Semaphore interface The interface to the semaphore is similar to the one used in M Ben Ari 19 and is implemented in the file semaphore c The component works as follows semaphore setup Setup the semaphore and initialize its waiting queue semaphore wait Takes the semaphore if it is available or waits if it is locked semaphore signal Releases a semaphore Table 10 4 Semaphore component interface 10 7 Kernel drivers In the following the three kernel drivers will be described During the description of the driver interfaces the expression from the kernel users point of view is used By this is meant the functions in the interface that are of relevance for the kernel user e g a person implementing processes to run on the nano kernel 10 7
101. ister DLAB 0 Out Divisor Latch High DLAB 1 In Interrupt ID Register x Out FIFO Control Register I O Line Control Register I O Modem Control Register x I O Line Status Register 1 0 Modem Status Register x 1 0 Scratchpad HOOG T define UART_DLM define UART IIR define UART_FCR define UART LCR define define UART LSR define MSR define SCR These are the definitions for the Interrupt Enable Register IER NOOR WNNE Ds define UART IER RDI 0x01 Enable receiver data available interrupt define UART IER THRI 0x02 Enable Transmitter holding empty register int define UART IER RLSI 0x04 Enable receiver line status interrupt define UART_IER_MSI 0x08 Enable Modem status interrupt These the definitions for the FIFO Control Register FCR define UART FCR ENABLE FIFO 0x01 Enable the RCVR XMIT FIFO x define UART FCR CLEAR RCVR 0x02 Clear the RCVR FIFO x define UART FCR CLEAR XMIT 0x04 Clear the XMIT FIFO x define UART FCR TRIGGER 1 0x00 Mask for trigger set at 1 define UART FCR TRIGGER 4 0x40 Mask for trigger set at 4 define UART_FCR_TRIGGER 8 0x80 Mask for trigger set at 8 define UART FCR TRIGGER 14 0 0 Mask for trigger set at 14 These the def
102. itch function At this point an interrupt handler was implemented and tested using the timer interrupt e Once this was running a timer driver was implemented e The missing link before combining all the pieces was to implement semaphores and process management These two components were implemented and tested as far as possible at this stage of develop ment Finally all the components were combined The kernel status as of this writing is described in the next chapter 10 9 Summary In this chapter most of the kernel implementation has been described The main focus has been on hardware architecture specific issues and how the hardware is used in the kernel 82 Chapter 10 Kernel implementation 83 Chapter 11 Status This chapter first gives a short overview of the kernel status as of this writing After this the future development of the kernel is described Dur ing the development of the kernel a lot of ideas for future projects came to mind as well as some small improvements This chapter gives a summary of some of those ideas 11 1 Current kernel status All the components described in Kernel design chapter 8 has been im plemented and tested to the extend possible at the time of the implementa tion The components have not been exhaustively tested since this would be very difficult before all the components of the kernel have been com bined After all the kernel components were combined th
103. k k k k a gt K K gt K K TOOLCHAIN mips64 TOOLCHAIN mips64el FE Fk k k k k ak k k k a k KK KK KK gt K K gt K K Architecture K K K ARCH mips64 KK K K gt K K K K ji Endianness EL Fk k k ak k ak k k k ENDIAN EB ENDIAN EL FE Fk k k k k k k I k k I K gt K K Name of kernel I I a a a IMAGENAME kernel JE RCC IC KK KK KK K K K The following stuff should not be touched k k I k I I KK KK KK a K Directories 2 k k k k k k k k k ROOT SUBDIRS lib kernel SRCDIR ROOT VPATH SRCDIR BINDIR ROOT Fk k k k k k k k k ak k a EKK KK KK KK KK gt K K K K Image file names and map disassembly file FE 2 k k k k k ak k k k GG KK KK 1 K gt K K gt K K IMAGE BIN IMAGENAME bin IMAGE REC IMAGENAME rec IMAGE ELF IMAGENAME elf IMAGE MAP IMAGENAME map IMAGE DIS IMAGENAME dis 97 Compiler toolchain FE Fk k k k k k k k k k k k k k K k I KK KK gt K K a K ifeq TOOLCHAIN mipsel CC mipsel linux gcc LD mipsel linux ld OBJCOPY mipsel linux objcopy OBJDUMP mipsel linux objdump endif ifeq TOOLCHAIN mips64 mips64 linux gcc LD mips64 linux
104. l 5 83 ee di 84 84 11 4 Summ ry Rm ES 85 87 89 95 List of Figures 3 1 Generic embedded 8 5 1 Overview of the CoreLV 18 5 2 Overview of the motherboard 20 5 3 Development test bed 22 61 GNUPro debugger 29 7 1 threads can be placed in overlapping protection do mains and more than one thread is able to run in each pro ee ee re G 35 7 2 Protection domains in Angel 37 8 1 Overview of the 43 8 2 different process 45 8 3 example of priority inversion 47 10 1 Kernel directory 69 10 2 Overview of the linked 71 10 8 Jump op code construction 73 vi LIST OF FIGURES vii List of Tables 5 1 Malta physical memory map 21 8 1 Used MIPS 49 9 1 Initial Application Context 63 10 1 Options in the Makefile lens 68 10 2 Compilation 70 10 3 Interrupt component interface 74 10 4 Semaphore component interface 76 10 5 Timer
105. l there is need for complete control of positions size and alignment of the different sections so the default linker script is not suffi cient and a custom linker script has been written see the file link xn in appendix B The custom linker script solves four kernel specific linking issues 1 Organizing the text section at the address 0x80200000 which is where YAMON loads the kernel The rest of the sections will follow the text section continuously 70 Chapter 10 Kernel implementation 02 This level of optimization should be safe mcpu r4600 Choose the RISC 4600 cpu type mabi 64 Choose the mips3 instruction set fno strict egcs 1 1 invokes this optimization per default but prototype this optimization is rather untested and should therefore not be used nostdinc Do not search the standard system directories for header files Only the directories that are specified with options are searched fomit fram Do not keep the frame pointer in a register for pointer functions that don t need one This avoids the in structions to save set up and restore frame point ers it also makes an extra register available in many functions Remove this option if remote de bugging is implemented as the latest version of gdb does not support this Wa 32 This is an undocumented but very important op tion It tells the assembler to generate 32 bit ELF code instead of the default 64 bit ELF This
106. ld OBJCOPY mips64 linux objcopy OBJDUMP mips64 linux objdump endif ifeq TOOLCHAIN mips64el CC mips64el linux gcc LD mips64el linux ld OBJCOPY mips64el linux objcopy OBJDUMP mips64el linux objdump endif Compiler and linker options 2 k k k k k k k k k K K K K K K K K K K K K gt K K gt K gt K gt K K gt K K INCLUDE I ROOT include W OPTS Wimplicit Wformat Wall Wstrict prototypes W OPTS A Wformat Wall Wstrict prototypes ifeq ARCH mipsel DEFS CC_OPTS endif ifeq ARCH mips64 DEFS CC_OPTS g Wa 32 mcpu r4600 mabi 64 mips3 GO pipe V D ENDIAN fno strict aliasing g c O2 nostdinc INCLUDE DEFS CC OPTS A CC_OPTS endif LD_SCRIPT ROOT kernel ARCH link xn LD_OPTS g G 0 static T LD SCRIPT o IMAGE_ELF V Map IMAGE MAP ifeq TOOLCHAIN mips64 LD_FORMAT elf64 bigmips endif ifeq TOOLCHAIN mips64el LD_FORMAT elf64 littlemips endif II II KK KK gt K a a a Files to be compiled 98 Appendix B Source code FE OCG OBJ kernel start o kernel mipsirq o kernel stack o kernel kernel o kernel serial o kernel Icd o kernel setjmp o kernel cpu o kernel list o kernel timer o kernel interrupt o kernel process o kernel sched o kernel semaphore o
107. ler static void enable_irq unsigned int irq_nr unsigned long flags if irq nr gt MAX INT printf whee invalid irq nr d n irq nr panic IRQ you lose save and cli flags cached int mask amp 1 lt lt irq nr if irq_nr amp 8 ctrl21 cached_int mask gt gt 8 amp Oxff Enable 2 cascade interrupt cached int mask amp 1 lt lt 2 ctrll1 cached_int_mask amp Oxff else xctrlll cached_int_mask amp Oxff restore_flags flags Acknowledge interrupt x static void ack int int irq if irq amp 8 Specific EOI to cascade x ctrll2 PIIX4 OCW2 _SEL PIIX4 OCW2 NSEOI PIIX4 OCW2 ILS 2 Non specific EOI to cascade ctrl22 PIIX4 OCW2 SEL PIIX4 OCW2 NSEOI else Non specific EOI to cascade 112 PIIX4 OCW2 SEL PIIX4 OCW2 NSEOI Get the interrupt x static int get irq int 141 Determine highest priority pending interrupt by performing a PCI Interrupt Acknowledge cycle Interrupt acknowledge offset define GT_PCIO_IACK_OFS 0 34 define MIPS GT BASE KSEGIADDR 0x1be00000 Interrupt acknowledge register is read only Read acces to this register forces an interrupt acknowledge cycle on PCIO volatile unsigned int gt irq void MIPS_GT_BASE GT PCIO IACK OFS Store irq number in xirq gt_i
108. llow a system to be evaluated with a range of MIPS based processors It can be used stand alone or in a suitable ATX rack system The daughter card used in this project is the CoreLV card and it is described below Malta is designed around a standard PC chipset giving all the advantages of easy to obtain software drivers It is supplied with the YAMON Yet Another MONitor ROM monitor in the on board flash memory which if required can be reprogrammed from a PC or workstation via the parallel 18 Chapter 5 Hardware port YAMON contains a lot of nice features like RAM configuration PCI configuration debug interface and simple networking support The YAMON ROM monitor will be described further in chapter 9 The feature set of the Malta system extends from low level debugging aids such as DIP switches LED displays and logic analyzer connectors to so phisticated EJTAG debugger connectivity limited audio support IDE and flash disks and Ethernet Four PCI slots on the board give the user a high degree of flexibility enabling the user to extend the functionality of the system 5 1 1 The CoreLV As mentioned above the daughter card is MIPS CoreLV 6 The card contains several components and how they interact is roughly shown in the block diagram on figure B I The two main components are the Galileo System Controller 4 and the MIPS64 5Kc CPU 9 Motherboard e Motherboard connectors
109. ment void list put after t list head pHead t list element pElement1 t list element pElement2 void list put before t list head pHead t list element pElement1 t list element pElement2 t list element list get t list head pHead void list remove t list head pHead t list element pElement int list length t list head pHead 107 endif LIST H include mipsregs h MIPS registers This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details ox X x 0X ifndef MIPSREGS H define MIPSREGS H The following macros are especially useful for __asm__ inline assembler ifndef STR define _STR x Ffendif ifndef STR define STR x STR x Ffendif Coprocessor control register names define INDEX 0 define RANDOM 1 define CPO_ENTRYLOO 2 define CPO_ENTRYLO1 3 define CPO CONTEXT 4 define CPO PAGEMASK 5 define WIRED 6 define CPO BADVADDR 8 define CPO_COUNT 9 define CPO ENTRYHI 10 define CP0 COMPARE 11 define CPO_STATUS 12 define CPO_CAUSE 13 define CPO EPC 14 define CP0 PRID 15 define CPO_CONFIG 16 define CPO LLADDR 17 define CPO_WATCHLO 18 define CPO_WATCHHI 19 define CPO XCONTEXT 20 define CPO_FRAMEMASK 21 define CPO_DIAGNOSTIC 22 d
110. n 1 Take the semaphore It will be released when the timer expires This should return immediately as the semaphore is supposed to be free semaphore wait amp pT semaphore Initialize the timer pT type timerType pT gt length msec timer tick per ms pT gt count msec timer tick per ms pT gt state ACTIVE Uninterruptable timer list operations save and flags if timer list pFirst NULL This is the only active timer Update the compare register timer offset pT length timer cur read_32bit_cp0_register CP0 COUNT timer offset write 32bit cpO register CPO COMPARE timer cur else Other active timers exist x tmp read_32bit_cp0_register CPO_COUNT if pT gt length lt timer cur tmp This timer expires before the current closest deadline Not quite straightforward Decrement other timers counters until now for pLE timer list pFirst pLE NULL pLE pLE gt pNext 166 Appendix B Source code timer base pLE gt count tmp timer cur timer offset Update the compare register with new deadline x timer offset pT gt length timer cur tmp timer offset write 32bit cpO register COMPARE timer cur Add the timer to the timer list x list_put amp timer list amp pT timer elem printf timer start exp 01
111. n figure 8 2 a process be in three different states waiting ready and running Only one process can be in the running state at a time and all processes in the waiting state are waiting on a semaphore to be released More about this below Running Ready lt Waiting Figure 8 2 The different process states Preemption of a process can happen while the process is doing a routine call to the nano kernel Being able to preempt a process while it is run ning a routine call in the nano kernel gives a more responsive system but it also introduces some problems To avoid problems some parts of the nano kernel should run without interruption and all functions provided by the nano kernel to the processes should be re entrant One of the ob vious places where the nano kernel must have a critical section to avoid interruption is during scheduling The scheduling decisions will happen when a timer has expired resulting in a process being ready again and during process synchronization using semaphores Timers and process synchronization will be described further below 8 3 Timer In embedded systems some types of jobs must run once after a given time and other types of jobs must run cyclic with a fixed period and this requires the use of a timer I have decided to have two different types of timers 46 Chapter 8 Kernel design One shot timer will when started wait for a speci
112. n in the block diagram on figure 5 2 From the CoreLV card there are three interfaces to the motherboard of which only the PCI and CBUS interface are shown on the figure The third interface is a bus which is not used in this project SysAD System RAM 7 Galileo L 5Kc CPU CLK CoreLV interface Serial ports PCI CBUS Interrupts etc DIL Switch SMsC KBD mouse FDC37M817 LED ASCII LED mm Super I O Controller Parallel port CBUS FPGA ISA Intel Monitor Flash IDE Flash 82371EB 4Mb South Bridge USB Timer RTC AMD Ethernet Am79C973 Interrupt Ethernet FSH i i Controller Controller PCI slot 1 4 Figure 5 2 Overview of the motherboard The PCI bus is connected to a multi function PCI device an on board ethernet device and of course to the four PCI slots The PIIXA is a standard Intel chipset found on many modern PC motherboards It im 5 1 Malta system 21 plements PCI to ISA bridge function a PCI IDE function and a Universal Serial Bus host hub function If a Compact Flash is installed this chip is also able to control this device through the IDE interface To the ISA bridge of the PIIX4 a Super I O Controller from SMsC I is connected This I O controller contains functionality to
113. n interrupt handlers The register is safe to use since exceptions are disabled during both context saving and context restoring and this prevents other exceptions handlers changing the register while it is in use The context switch in the interrupt handler is implemented in the file mipsirq S and works as follow 1 Save the EPC register in k0 Save the current CPU context on the stack Save the stack pointer Handle the interrupt Get a new stack pointer for the next process to run Restore to the new context Restore the saved EPC register Return from the interrupt handler 9 Oo s wD The context switch used when using semaphores is implemented in the file stack S and works as follow Save the return address ra register in the register Save the current context on the stack Save the stack pointer Get a new stack pointer for the next process to run Restore to the new context The k0 register now contains the return address so this is used as return address po bob All the macros used for saving and restoring the states are located in the file stack rame h 10 6 Semaphores As previously mentioned the semaphore is a binary semaphore with a waiting queue of blocked processes sorted after priority The basic priority inversion protocol described in chapter 8 has been im plemented as part of the semaphore This is basically done e If process tries to take a semaphore which
114. nd kernel branch each has architecture specific branches The mips branch contains generic MIPS code the mips32 branch contains MIPS32 specific code and the mips64 branch contains MIPS64 specific code The arch file is a symbolic link that links to the architecture to be com piled This link is created at compile time by the Makefile and the destina tion point for the link depends on the user defined options in the Makefile described above 10 1 3 Compilation options When developing normal applications the compile options are not that important and the default options are sufficient for most purposes When 10 2 Linking 69 include arch gt mips64 mips mips32 mips64 L kernel r arch e mips64 mips mips32 mips64 lib Figure 10 1 Kernel directory structure developing kernels on a cross development platform the compile options can be crucial and should be carefully chosen In table 10 2 the most important compiler options are listed 10 2 Linking Every link is controlled by a linker script This script is written in a linker command language The main purpose of the linker script is to describe how the sections in the input files should be mapped into the output file and to control the memory layout of the output file Most linker scripts do nothing more than this However when necessary the linker script can also direct the linker to perform many other operations In the kerne
115. nderstanding of standard PC hardware will come in handy 1 3 Typographical conventions The following typographical conventions are used throughout the report Italic is used for the introduction of new terms Constant width is used for names of files functions programs methods and routines Chapter 2 Introduction This chapter contains an introduction to embedded systems and to the project itself The chapter finishes with a section describing the motivation for this project 2 1 Introduction to the embedded systems An embedded system is a combination of computer hardware software and and perhaps additional mechanical parts designed to perform a specific function good example is the microwave oven Millions of people use one every day but very few realize that a processor and software are involved in preparation of their dinner The embedded system is in direct contrast to the personal computer since it is not designed to perform a specific function but to do many different things The term general purpose computer may be more suitable to make that distinction clear Often an embedded system is component within a larger system For example modern cars contain many embedded systems one controls the brakes another controls the emission and a third controls the dashboard An embedded system is therefore designed to run on its own without human intervention and may also be required to respond to events in real
116. ne and secondly if the process does not cancel the timer it has created In both cases the cyclic timer simply ignores that there are no processes waiting and continues a new cycle In hard real time systems it would be a disaster to miss a deadline but in this kernel it is ignored and the process missing a deadline will simply try and catch the next one In most operating systems the timer hardware is programmed to interrupt at a rate within the magnitude of 50Hz 200Hz There are two problems with this when creating a timer first the timer is not very precise due to the low frequency and secondly the overhead of handling the timer interrupt is unnecessary if the timer is not used for anything when the timer hardware interrupts To overcome this problem the amount of time until the next timer interrupt should occur is calculated and the timer hardware is adjusted accordingly 8 4 Synchronization 47 The next timer interrupt should occur when the nearest timer should be activated By using this method all unnecessary timer interrupts are elim inated unless a process creates a cyclic timer with a period greater than the value which the timer hardware could be programmed The maximum amount of time the timer interrupt can be postponed is dependent on the timer hardware used and the CPU speed On the MIPS64 hardware used in this project the timer interrupt can be postponed around 200 seconds that is it has to tick with a rate which
117. nse See the file COPYING in the main directory of this archive for more details 122 Appendix B Source code ifndef SETJMP H define SETJMP H define JBLEN 23 define JBTYPE long long typedef JBTYPE jmp buf JBLEN int setjmp jmp buf void longjmp jmp buf int endif SETJMP H include stackframe h Stackframe macros Based on code from the Linux kernel This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details ifndef STACKFRAME H define STACKFRAME H include lt asm h gt include lt addrspace h gt include lt regdef h gt include regoffset h Macros to save the current state macro SAVE_SOME set push reorder move kl sp move k0 sp dsubu sp sp R SIZE sd k0 R SP sp sd vl R_V1 sp sd zero R_ZERO sp dmfcO v1 CPO STATUS sd v0 R_VO sp sd v1 R STATUS sp sd a0 R_AO sp dmfcO vl CPO CAUSE sd al R_Al sp sd v1 R CAUSE sp sd a2 R_A2 sp dmfc0 vl CPO_EPC sd R A3 sp sd v1 R EPC sp 123 Macros to restore to some state sd sd sd set endm macro set set set endm macro mfhi sd sd sd sd sd sd sd sd sd sd sd endm macro sd sd sd sd sd sd sd sd sd endm macro SAVE SOME t9 R T9 sp ra _
118. nterrupt handler should be nested or not The MIPS CPU has a simpleminded approach to interrupt priority in that all interrupts are equal This leaves it completely up to the programmer to decide how the interrupts should be prioritized The MIPS CPU has two software and six hardware interrupts see table 8 1 In this kernel there is no need for software interrupts so these will be ignored All interrupts for the Malta board end up in a combined hardware interrupt MIPS IRQ 2 which is asserted when devices such as the serial port interrupts When receiving this type of interrupt the external interrupt controller has to be checked to actually see which device asserted the interrupt The last interrupt of interest is the timer interrupt asserted by the CPU itself the rest are ignored in this kernel This leaves the choice of creating a priority scheme between the timer interrupt and the combined interrupt I have decided to give the timer the highest priority and the combined hardware interrupt the lowest priority that is if the two types of interrupts is asserted at the same time the timer interrupt should be handled first MIPS IRQ Source 0 Software ignored Software ignored Combined hardware interrupt Hardware ignored Hardware ignored Hardware ignored Hardware ignored Timer interrupt Table 8 1 Used MIPS interrupts The nesting of interrupts is closely connected to the priority of inte
119. nterrupt init This function initializes the interrupt com ponent and registers the interrupt handler which receives MIPS interrupts interrupt register This function takes two arguments namely the IRQ number and the interrupt handler It then registers the handler in the interrupt table If an interrupt handler for a given IRQ is already registered the kernel will panic since shared interrupts are not sup ported in this kernel This function should only be called during kernel initialization Table 10 3 Interrupt component interface 10 5 Context switch As mentioned in chapter B two different types of context switches have to cooperate e g a context switch by using a semaphore and context switch during interrupt The real difference between these two types of context switches lie in the way they return to a new process after restoring a new context When returning from an interrupt the instruction eret is used When the eret instruction is executed it clears a bit in the status register and then jumps to the address held in the EPC register When returning from a context switch which has been issued by using semaphore it uses a normal jump instruction To make these two cases work together gracefully the special register k0 is used to store the address to which a process should continue after both types of context switch The is a special register that is 10 6 Semaphores 75 reserved for use i
120. ntroduction 2 1 Introduction to the embedded systems 2 2 Introduction to the project 2 3 Motivation for the 2 4 Organization sso acas een e CQ I 3 Kernel properties 9 1 Introduction 22 22 ooo rs 7 3 2 Kernel 7 3 9 SUMMARY WURDE do ek XR ee 10 4 Choosing hardware 11 4 1 Introduction lt a sese zo m R 9 M 11 42 s0bl 222 4430 3 e Te ar EARS 12 ii CONTENTS C IPC 13 4 4 Atmel 91 ARM 13 4 5 MIPS Malta development board 14 4 6 Summary 525444866 RR REY ee 14 17 17 18 5 1 2 The 20 52 Testbed i amp uos eee SL Rege ath A 22 Did X EGER 23 25 oo ede OBR ge be ee a ed 25 6 2 The different 26 6 3 27 6 4 Remote 28 NEWB ic Greer 28 6 6 Summary lt 4 o9 om aS RO Ree m o 29 7 SASOS 31 T 31 2 Opal ooo RR late at oe a a Ge 34 Ta Angel ee EAE ER oe we eos 36 v ae he Se ot a nc oe Se ee ee 38 O Summary ae Oe a ea 38 CONTENTS iii 8 Kernel design de ee B 2 5
121. nup when a program exits The disadvantage of this approach is that the mechanism for memory pro tection which is isolating a program within a private virtual address space is an obstacle for efficient communication between two protected processes Especially pointers have no meaning outside a process memory protection boundary and the primary communication mechanisms rely on copying data between private virtual memories The address translation between two private virtual memories can be calculated fast but the copying is expensive The common communication choices between processes are to exchange data through pipes files or messages and neither choice is adequate for programs requiring high performance Most modern operating systems have introduced facilities for shared memory for example in Linux there are two methods for sharing memory namely System V IPC and BSD mmap However the mix of shared and private memory regions does introduce 7 1 Introduction 33 several problems private data pointers are difficult to handle in a shared memory region and private code pointers cannot be shared Single address space operating systems avoid these problems by treating a single virtual address as a global resource controlled by the operating system just as the disc space or the physical memory is a global resource controlled by the system With the appearance of 64 bit address space architectures the need to re use addresses which is
122. o the Intel platform this would be the best boot loader to use if the kernel is loaded from a disc media EtherBoot EtherBoot 32 is a boot loader which is created for discless computers The boot loader is placed in a flash ROM on an ethernet adapter and supports loading a kernel over the network using a TFTP server The boot loader located in the ethernet adapters flash ROM is called right after the PC BIOS is done initializing the hardware as it was the case with the other boot loaders mentioned above To load the kernel over an ethernet EtherBoot has to provide special driver 9 3 Bootstrapping MIPS 59 support for the ethernet adapter in question and a small network stack RedBoot RedBoot 33 is possibly the most advanced free software boot loader available RedBoot combines the BIOS and the boot loader RedBoot is available for a wide range of platforms including ARM MIPS PowerPC and Intel platforms The features include network booting flash booting and remote debugging Unfortunately the bootloader only works with the eCos kernel and the Linux kernel Of all of the above described boot loaders only RedBoot runs on the MIPS platform The reason for this is that MIPS based hardware products often come with a boot loader especially designed for the system and therefore there has never been a real need for other boot loaders for the MIPS plat form The MIPS Malta system comes with a combined BIOS and boot loader very similar to
123. ocesses though some of the other options will not provide the same level off protection as the operating systems described in this chapter The solution to protection and sharing of memory in the discussed systems has been to use protection domains and a mechanism similar to remote procudure calls to communicate between threads in different protection domains This is done with a heavy use of the virtual memory mecha nisms provided by the hardware This indicates that this is the best known method to do protection and sharing in a SASOS without sacrificing the level of protection The major difference in the three systems lie in how they actual manage the protected domain This management has not been discussed in detail since it was not the primary focus of this chapter Whether one version of the protection domain management is better than the other is very difficult to conclude Personally I liked Mungi the best due to its very clean and simple way to manage objects in its protection domains Mungi also seems to have combined the best from Angel and Opal into one system Personally I feel that there is a need for research on mechanisms for pro tection and sharing of memory in a SASOS without using virtual memory Even though the main motivation for designing a SASOS was the huge virtual address space I am sure that small real time systems running on limited hardware could benefit from this research 40 Chapter 7 SASOS 41
124. ode EXL ERL 0 x define CEB KERNEL 2 Count events in kernel mode EXL ERL 0 define CEB_EXL 1 Count events with EXL 1 ERL 0 endif MIPSREGS H x include piix4 h Carsten Langgaard carstenl mips com x Copyright C 2000 MIPS Technologies Inc All rights reserved This program is free software you can distribute 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 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 59 Temple Place Suite 330 Boston MA 02111 1307 USA x Register definitions for Intel 4 South Bridge Device 112 Appendix B Source code ifndef PIIX4 define PIIX4 DOC ASC SKK ak I ak sk ak IO register offsets define PIIX4 ICTLR1 ICW1 0x20 7
125. omputer Science Tom Stiemerling Paul Kelly Imperial College Implementation and Performance of the Mungi Single Address Space Operating System Jochen Liedtke The University of New South Wales S Tan et al An Object Oriented Nano Kernel for Operating System Hardware Support Department of Computer Science University of Illinois at Urbana Champaign Exception Handling in Embedded C Programs C C Users Jour nal Yonatan Lehman A S Tannenbaum A S Woolhull Second edition Operating Systems Design and implementation Prentice Hall 1997 Michael Barr Programming embedded Systems O Reilly and Asso ciates 1999 M Ben Ari Principles of Concurrent Programming Dominic Sweetman See MIPS Run Morgan Kaufmann Publishers Inc GNU Project http gcc gnu org MontaVista http www mvista com Linux VR Project http www linux vr org Red Hat Inc http www redhat com BIBLIOGRAPHY 93 25 26 27 28 29 30 31 32 33 34 Linux on SGI MIPS http oss sgi com mips Newlib Library http sources redhat com newlib Small Device C Compiler project SDCC http sdcc sourceforge net Red Hat eCos http www redhat com embedded technologies ecos The LinuxBIOS Home Page http www acl lanl gov linuxbios index html The LILO Home Page http brun dyndns org pub linux lilo The GRUB Home Page http www gnu org software grub The EtherBoot Home Page http etherboot sourceforg
126. ong Listing 8 1 Exception example in C There are basically two methods for implementing exceptions in C The first method is by using the POSIX functions calls set jmp and long jmp These functions have been implemented in the file set jmp S in appendix B The set jmp function saves the stack context for non local goto and long jmp makes non local jump to a saved stack context The two func tions calls can easily be wrapped into two macros throw and try where throw would use Long jmp to jump to an exception handler and try would use set jmp to save the exception environment The result is actually a very nice implementation of exceptions in C but it does have some prob lems 8 8 Summary 53 The problems with the setjmp method is that C lack of stack cleanup facilities which means that code written to be exception safe must include far more try blocks than it would in C or Java Another issue is that the exception implementation has to be threadsafe since the kernel is running several processes which are able to use the exceptions Implementation of a threadsafe exception is not a trivial task For these reasons this method is not used The second method was described in the C C Users Journal I6 and implemented using the goto call The method requires that an error status is passed on to every function and after all function calls this value must be checked If the error status indicates an error it would thr
127. ood experience to hand over this kernel project to another student and enable him to carry on the future kernel work 89 Appendix Project description Danish title Bidrag til udvikling af nanokerne English title Contribution to development of a nanokernel Participant Lars Munch Christensen Danish project description Det langsigtede m l er at konstruere biblioteksrutiner der kan karakteris eres som en nanokerne idet de skal kunne l nkes sammen med dels anvendel ses dels maskinspecifikke rutiner til indlejrede systemer Ses bort fra kold start skal et indlejret system kunne opfattes som et enkelt program med flere aktiviteter N r programmet starter eksisterer kun en enkelt aktivitet der afvikles uden begr nsninger i privilegier Oprettelse og start af aktiviteter skal kunne udtrykkes ved hj lp af nanok ernens rutiner Der skal kunne styres b de frivilligt og p tvungent pro cesskifte Til udnyttelse af materiel til underst ttelse af begr nsninger i forskellige aktiviteters privilegier s ges udarbejdet og afpr vet et s t passende kon ventioner Koldstartsproblemer skal analyseres og behandles med henblik p at re 90 Appendix A Project description ducere afh ngigheder af materiel s meget som muligt Det konkrete m l for projektet er at implementere en nanokerne s vidt at et indlejret system kan koldstartes og udnytte en simpel ydre enhed Ind hentning af oplysninger om lignende systemer
128. ource code define WAITING 2 typedef struct t_list_element process elem int id int priority int orig priority original priority of a process int state unsigned longx stack pointer t_process define process base ple StructBase ple t process process elem Pointer to current running process x extern t process process current extern t process process old Sorted of ready processes extern t list head process list void process init void void process insert t list head pHead t list element pElement void process reorder t list head pHead t list element pElement void process create void function void int priority int stack size void process list print t list head pHead endif PROCESS H include regdef h Register definitions This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details ifndef REGDEF H define REGDEF H define zero 0 wired zero define AT at assembler temp uppercase because of set at define v0 2 return value caller saved x define v1 3 define a0 4 argument registers define al 5 define a2 6 define a3 7 define t0 8 caller saved in 32 bit arg reg 64 bit define t1 9 define t2 10
129. ow an ex ception After some experimentation with the code described in the article the conclusion was that it was clumsy to use and made the code difficult to read Besides that I did not like the fact that an extra parameter was required to be passed on to every function call Since the exception handling is not used another approach to handling errors should be taken I choose to use a very brutal method if something goes wrong then report the error and make a kernel panic immediately If exceptions were used the panic would instead be in the exception handler so when the kernel panics it would not be in the same state as when the error ocurred Besides there is absolutely no reason to try to continue execution if the kernel enters some unexpected state so the best approach is to create a kernel panic and fix the bug In real world embedded systems the kernel panic should be combined with a failure handler which often just restarts the whole system 8 8 Summary This chapter covered the kernel design All the major components of the kernel have been designed and described and the general kernel structure is now clear 54 Chapter 8 Kernel design 55 Chapter 9 Bootstrapping This chapter first describes bootstrapping in general and then gives an introduction to boot loaders This is followed by a description of what happens the moment after the Malta system has been powered on Then a comparison of the MIPS bootstrapping
130. p n t set tat n t treorder no inputs 7817 memory define restore flags flags do unsigned long tmpl asm volatile set tnoreorder t t t restore flags n t set tnoat n t mfcO t 1 12 n t andi t 0 1 n t ori t 1 1 n t xori t 1 1 n t orNt260 1 n t mtcO0 t 0 12 n t nop n t nop n t nop n t set tat n t set treorder d Pd 128 Appendix B Source code pap _tmp1 0 flags 7817 memory while 0 define cli cli define sti sti define save_flags x save flags x define restore flags x restore flags x define save and cli x __ x endif SYSTEM H x aa include timer h Timer Header Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details ifndef TIMER H define TIMER H include regoffset h include lt semaphore h gt include lt list h gt Amount to increment compare reg each time extern unsigned int timer offset Timer state x define IDLE 0 define ACTIVE 1 define DONE 2 Timer type define ONCE 0 define PERIODIC 1 typedef struct t list element timer_elem t_semaphore semapho
131. ped at The University of New South Wales Department of Computer Systems Mungi is very similar to Opal even the type of capabilities it uses are the same The only thing that is different in the design of protection and sharing is that objects are used instead of segments Due to the great similarity to Opal Mungi s design of protection and sharing will not be covered in detail It should be noted though that the actual management of objects by the system is somewhat simplified compared to the management used in Angel This is definitely a good decision since what is gained by having a single address space should not be lost in a complex and time consuming object management Another thing which should be noted even though it is off topic in this chapter is that Mungi has been performance tested very thoroughly and the result has shown a vast improvement in performance compared to tra ditional multiple address space systems The most significant improvement was with database operations 7 5 Summary Even though this kernel project as of this writing does not have any mech anisms to protect one process from another it is interesting to see how other kernel projects have solved this problem in a single address space operating system As it will be described briefly in Kernel design chapter 8 there 7 5 Summary 39 are other options than using protection domains for creating protection and sharing of memory between pr
132. printf Process id u stack x n P id P stack pointer Insert the process into the ready list x process insert amp process list amp P process elem Create new linked list of tasks void process init void t process P nextId 0 list_init amp process list Create idle process The idle process uses the kernel stack well actually the idle is the kernel P amp process allocated nextId P id P gt state READY P gt priority 0 Insert the idle process process insert amp process list amp P process elem The current process is the idle process process current P kernel sched c Scheduler code Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include lt stddef h gt include lt process h gt include lt interrupt h gt int sched_now 1 t process process old t process process_new t process process highest A valid declaration 155 extern void stack switch void Select new process to be run void schedule void Dont schedule if we are nesting but we raise a flag to indicate that schedule was intended if interrupt nested 0 sched now 1 return
133. re int state int type unsigned int length unsigned int count t timer define timer_base ple StructBase ple t timer timer elem void timer interrupt void void timer init void void timer setup t timerx 129 int timer start t timer pT unsigned int msec int timerType int timer waitfor t timer x void timer cancel t timerx endif TIMER_H x include yamon h ifndef YAMON H define YAMON H Basic types x typedef unsigned int t yamon uint32 typedef signed int t_yamon_int32 typedef unsigned char t_yamon_bool YAMON Environment variable x typedef struct char name char t yamon env var YAMON H lib vsprintf c This file contains vsprintf function This code is heavily based on stuff by Lars Wirzenius amp Linus Torvalds from the linus kernel This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details include lt arch stdarg h gt include lt serial h gt o 0X X X X X define ZEROPAD 1 pad with zero x define SIGN 2 unsigned signed long x define PLUS 4 show plus x define SPACE 8 space if plus x define LEFT 16 left justified x define SPECIAL 32 Ox define LARGE 64 use ABCDEF instead of abcdef NOTE This ctype does not
134. required on 32 bit ar chitectures is eliminated A 32 bit address space may be enough for a single address space embedded system not requiring that many resources but for general purpose systems 32 bit is no longer sufficient as a single global virtual address space The main goal of single address space systems is to enhance sharing and to improve performance of co operation programs The problems with a mix of shared and private memory regions in multiple address systems can in fact be avoided in single address space operating systems without sacrificing the previously mentioned advantages of multiple address space systems That is a SASOS will still be able to 1 provide sufficient address space without multiple address spaces due to the use of 64 bit architectures 2 provide the same protecetion level as the multiple address space s system 3 cleanup after a process without adding complexity to this action There are of course also several tradeoffs in a single address space system For example the virtual address space is managed as a global system re source which has to be used fairly and this requires accounting and quotas Another example is that process memory region may not be continuous in the address space There are a lot of pros and cons for both single and multiple address space systems but these will not be discussed futher In the following the main focus will be on how the single address space oper ating s
135. res new amp change write 32bit cpO register register res DORO a aa aaa aaa return res 109 BUILD SET CP0 status CP0 STATUS BUILD SET CPO0 cause CP0 CAUSE BUILD SET CPO config CPO0 CONFIG endif defined LANGUAGE ASSEMBLY Bitfields in the R4xx0 0 status register define 5 0x00000001 define STO_EXL 0x00000002 define STO ERL 0x00000004 define STO_KSU 0x00000018 define KSU USER 0x00000010 define KSU SUPERVISOR 0 00000008 define KSULKERNEL 0x00000000 define ST0 UX 0x00000020 define STO_SX 0x00000040 define STO KX 0x00000080 define STO DE 0x00010000 define STO_CE 0x00020000 Status register bits available in all MIPS CPUs define ST0 IM 0x0000ff00 define STATUSB IPO 8 define STATUSF_IPO 1 lt lt 8 define STATUSB_IP1 9 define STATUSF_IP1 1 9 define STATUSB_IP2 10 define STATUSF_IP2 1 lt lt 10 define STATUSB_IP3 11 define STATUSF_IP3 1 lt lt 11 define STATUSB_IP4 12 define STATUSF_IP4 1 lt lt 12 define STATUSB_IP5 13 define STATUSF_IP5 1 lt lt 13 define STATUSB IP6 14 define STATUSF_IP6 1 lt lt 14 define STATUSB_IP7 15 define STATUSF_IP7 1 lt lt 15 define STO_CH 0x00040000 define STO SR 0x00100000 define STO_TS 0x00200000 define STO_BEV 0x00400000 define STO RE 0x02000000 define ST0 FR 0x04000000 define STO_CU Oxf0000000 define STO CUO 0x1000000
136. rmatik uni erlangen de gt 1993 derived from Data Sheet Copyright Motorola 1984 It was written to be part of the Linux operating system This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details x X X X X KK X ifndef RTC H define RTC H Registers x define RTC SECONDS 0 define RTC SECONDS ALARM 1 define RTC MINUTES 2 define RTC MINUTES ALARM 3 define RTC HOURS 4 define RTC HOURS ALARM 5 define RTC_DAY_OF_WEEK 6 define RTC DAY OF MONTH 7 define RTC MONTH 8 define RTC YEAR 9 Control registers x define RTC REG A 10 define RTC REG B 11 define RTC REG C 12 define RTC REG D 13 118 Appendix B Source code SK A x register details ORSA REE define RTC FREQ SELECT RTC REG A update in progress set to 1 244 microsecs before RTC goes off the bus reset after update may take 1 984ms 32768Hz RefClock is complete totalling to a max high interval of 2 228 ms define RT C UIP 0x80 define RTC DIV CTL 0x70 divider control refclock values 4 194 1 049 MHz 32 768 kHz x define RTC REF CLCK AMHZ 0x00 define RTC REF CLCK 1MHZ 0x10 define RTC REF CLCK 32KHZ 0x20
137. rq irq amp OxFF IRQ7 is used to detect spurious interrupts The interrupt acknowledge cycle returns IRQ7 if no interrupts is requested We can differentiate between this situation and a Normal IRQ7 by reading the ISR irq 7 hx X X x i ctrl13 PIIX4 OCW3 SEL PIIX4 OCW3 ISR if x ctrl13 amp 1 lt lt 7 return 1 Spurious interrupt return 0 RR ak side effect of the way this is implemented we re limited x to interrupt handlers in the address range from KSEGO lt x lt KSEGO 256mb void interrupt setvector void xaddr Normaly we would have to flush the cache to ensure that the interrupt handler actually get registered right away but just disable cache to avoid strange problems unsigned long handler unsigned long addr volatile unsigned int KSEG0 0x200 0x08000000 0 x03F F amp handler gt gt 2 Handle the combined interrupt x void interrupt hw reg offset xregs interrupt handler action 142 Appendix B Source code int irq 0 if get amp return interrupt has already been cleared x disable irq irq int irq action interrupt action irq Handler registered x if action NULL call handler x action else printf IRQ 96d but no handler irq
138. rrupt For example nesting should not be allowed when handling the highest priority interrupt on the other hand it is preferable to be able to handle the timer interrupt while handling an interrupt from the serial port My solution sums up to 1 Disable all interrupts when handling the timer interrupt 2 Disable all but the timer interrupt when handling the combined hard ware interrupt 50 Chapter 8 Kernel design Disabling all but the timer interrupt when handling the combined hardware interrupt may be a brutal decision and one could argue that combined hardware interrupts with a higher priority should be allowed to interrupt another combined hardware interrupts with lower priority I have decided to keep things simple and handle the combined hardware interrupt with the highest priority first and without interrupts Another important issue when designing an interrupt handler is the per formance of the interrupt handling If the interrupt handling takes a long period of time the system will then not be responsive to other events during this time The two topics which deserves special attention are e The interrupt latency time should be minimized e The interrupt handling time should be minimized The time that passes between the interrupt and the execution of the inter rupt handler is called the interrupt latency The interrupt handling time is the time passed between the first intruction in the interrupt handler is executed to
139. rsonal prefer ences while others are made for pure educational purposes The idea of these kernel properties are to narrow down the huge number of possibilities one is faced with when designing a kernel for an embedded system 3 2 Kernel properties All embedded systems contain a processor and software but they also have other features in common In order to have software there must be a place to store the executable code and a storage for runtime data manipulation This storage will take the form of RAM and maybe also ROM All embed ded systems also contain a kind of input and output system Figure 8 1 shows a generic embedded system 8 Chapter 3 Kernel properties Memory Inputs Outputs Processor 99 Figure 3 1 Generic embedded system The kernel developed in this project will take form of a generic embedded system and will strive to be the smallest common kernel for embedded systems When choosing a language in which the kernel should be implemented there are several choices It could be implemented in ADA Java C and several others I choose to implement it in C and assembler The motivation for implementing the kernel in C is that C more or less has become the standard language in the embedded world and free C compilers exists for almost all platforms The following list describes the properties the kernel strives to follow Micro kernel structure The kernel can be con
140. se pHead gt pFirst pRet gt pNext pHead gt pFirst gt pPrev NULL pRet gt pNext NULL 147 pRet gt pPrev NULL pHead gt number return pRet Remove specific Element void list remove t_list_head pHead t list element pElement if pElement gt pPrev NULL if pHead gt pFirst pElement printf Inconsistent list Vn pHead gt pFirst pElement gt pNext else pElement pPrev pNext pElement gt pNext if pElement gt pNext NULL if pHead gt pLast pElement printf Inconsistent list Vn Head pLast pElement gt pPrev else pElement pNext gt pElement gt pPrev pElement pNext NULL pElement pPrev NULL pHead gt number int list length t list head pHead return pHead number kernel mipsirq S Interrupt exception dispatch code The idea of how to handle interrupts comes from the Linux exception dispatch code This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details include lt asm h gt include lt regdef h gt include regoffset h include lt mipsregs h gt include lt stackframe h gt text LEAF mipsIRQ CLI SAVE ALL 14
141. sidered as one program with more activities This is almost the same as saying that the kernel has a micro kernel structure in the sense that a micro kernel also has several activities running as separate processes The Minix 17 kernel is divided into I O tasks and server processes In this kernel there will be no real difference in these processes besides their priority so to be able to differentiate between these processes a process controlling a device will be called a driver and a process doing a non device related task will just be called a task If the term process is used it includes both drivers and tasks Stack based context switch When changing from one process to an other the context should be saved and restored by manipulating the stack Each process will have its own stack and use this to save and restore the context This will be discussed further in the Kernel De sign chapter 8 The kernel will only run in one address space so 3 2 Kernel properties 9 after a context switch we will still be in the same address space but in a different process This type of context switching is very similar to the principles used in coroutines Message passing To communicate between two processes the concept of message passing should be introduced and a simple send and receive mechanism will be used to implement this The semantics of these will be very similar to the ones used in the Minix kernel Semaphores Since the kernel h
142. single space operating systems Chapters 8 and 9 contains the de sign of the kernel and the boot process Chapter 10 contains a description of the kernel implementation and chapter 11 describes the current status of the kernel The report finishes in chapter 12 with a conclusion Chapter 2 you are reading it Chapter 3 describes the properties that the kernel were given before choos ing hardware and before going into a detailed kernel design Chapter 4 describes the process of choosing the right hardware for the development of the kernel The different hardware which where con sidered will be described Chapter 5 contains a description of the hardware used in this project This includes a description of the main board the CPU and the test bed used for development Chapter 6 contains a description of the software used in the implementa tion of the kernel This includes the compiler toolchain the debugger and the considerations done when choosing development tools Chapter 7 describes Single Address Space Operating Systems SASOS It begins by introducing single address space operating systems with comparison to the traditional multiple address space operating sys tems After this introduction three different single address space operating systems are discussed 6 Chapter 2 Introduction Chapter 8 describes the kernel design All major components of the ker nel are described that includes the timer the synchronization mech ani
143. sms the interrupt handling and scheduling Chapter 9 describes bootstrapping in general and then gives an intro duction to boot loaders This is followed by a description of what happens the moment after the Malta system has been powered on The chapter finishes with a description of how bootstrapping a kernel is done in practice on the Malta system Chapter 10 describes the kernel implementation The main focus will be on how to interface with the hardware since this subject has been the most time consuming part of the kernel implementation Chapter 11 first gives a short overview of kernel status as of this writing After this the future development of the kernel is described Chapter 12 contains the conclusion Throughout the report I have eliminated minor details to make it more readable but in some cases small details may have taken significant time to figure out or solve these will then be described thoroughly This will hopefully save future project students a lot of hair pulling The report is also written in a way that enables future students to make a jump start to continuing work on the kernel project Chapter 3 Kernel properties This chapter describes the properties that the kernel were given before choosing hardware and before going into a detailed kernel design 3 1 Introduction Before going into a detailed kernel design some general kernel properties have to be given Some of these properties are made from pe
144. sociated with the portal The name space for portals is global in Opal and allows the exchange of data during uses of a portal through shared memory The result is that there is no copying of data in communication between protection domains The key point in the Opal s handling of protection and sharing of memory is the use of protection domains where a group of threads in a protection domain can communicate in a protected and controlled manner by attach ing and detaching segments If communication has to be done with threads in another protection domain portals are used The portals are essentially the same as a remote procedure call where the data is passed along through the use of shared memory segment between the two protection domains as shown in figure 7 1 where a thread is running in a temporarily overlapping protection domain 7 3 Angel Angel I3 is a single address space operating system developed at the City University of London Angel was developed after a study on how to address some of the problems with the two microkernels Topsy and Meshix e The Meshix operating system exhibited poor performance especially in the message passing system e It was difficult to extend the base system to provide more complex services e The UNIX environment proved too restrictive as a research platform Adaption of the Meshix platform could not address these problems and a radically different operating system structure was required The r
145. sor position and to print characters an the terminal These functions are implemented in the file serial c serial putchar Prints a character on the terminal serial print Prints a string on the terminal Table 10 8 Serial terminal interface In future development this driver should be split into two one for the UART itself and one for the VT220 terminal using the UART but during the kernel development this implementation has been sufficient 10 8 Kernel construction In the above the implementation has been described but not how the kernel was actually constructed In the following the steps I went through to get the kernel up and running is summarized e First thing to be implemented was the bootstrap This was debugged by writing to the LCD display e Once the bootstrap was working an environment for changing from MIPS assembler into C was created 10 9 Summary 81 Next the serial terminal driver was created and nice printf func tion was included The main reason for the inclusion of a full blown printf function at this early stage of development was that it would speed up the debugging process Then an implementation of coroutines was made This was done using a yield function which where very similar to a combination of the set jmp and long jmp functions which are implemented in the file set jmp S This was tried out with disabled interrupts The yield function later evolved into a stack sw
146. ssembler code This file Public License this archive for more details ifndef ASM H define ASM symbol 2 symbol function symbol 0 sp 0 ra NESTED declare nested routine entry point define NESTED symbol framesize rpc symbol 2 symbol function symbol 0 sp framesize rpc LEAF declare leaf routine define LEAF symbol globl align type ent symbol frame globl align type ent symbol frame END mark end of function define END function end size function function function gt is subject to the terms and conditions of the GNU General See the file COPYING in the main directory of 103 EXPORT export definition of symbol define EXPORT symbol globl symbol X symbol Print formated string define PROM PRINT string N push reorder N la 0 8 jal serial_print string define TEXT msg data N 8 asciiz msg N previous tendif ASM H include byteorder h Id byteorder h v 1 1 1 1 2001 09 23 15 00 00 Imc Exp This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details Copyright C 1996 19
147. ssembly routines The processes in the kernel could range from drivers controlling the ethernet subsystems implementing an IP stack and processes which would normally be running in userspace with lower priority The last is very unusual from normal micro kernels but also very powerful in embedded systems for example if some calculation is more impor tant to get done in time it may have to have a higher priority than a driver This is not be possible in a system like Minix without mod ifying the kernel Build the processes around a nano kernel This has become a com mon way for constructing modern micro kernels I5 More on this below Build the kernel as a single address space kernel without using the memory management unit The advantages of this is as described earlier that the message passing can be done very fast Another im portant issue is that many micro controllers like the previous men tioned AT91 do not have a memory management unit at all so the kernel has to seek other methods for protecting the different processes from each other The definition of a nano kernel is not unambiguous thus there is no list of components which are allowed in the nano kernel and what hardware that has to be abstracted in the nano kernel Common components of the nano kernel 15 is Boot component responsible for booting and initializing the system Interrupt handler responsible for handling interrupts and ac tivation of the sche
148. sses have to run forever When a process is initialized a predefined stack size is allocated for the task If the kernel runs out of stack it will panic during the initialization Even though the kernel is highly modularized it does not prevent a process from writing in other processes data area It will therefore require some coding discipline to use the kernel as it is The modularization could be taken one step further by using the GNU C extension of nested functions Each process could be wrapped into one function and thereby creating an environment for this process only For other processes to access the nested function would require explicit authorization by giving the function pointer to another process If the kernel were restructured using the GNU C nested functions extention it might have an influence the interpretation of what should be called a nano kernel This is because the boundary between the nano kernel and the kernel processes will become more blurred The subject of encapsulating the processes using nested functions is out of scope for this project but as of this writing an initiative to do this is already in progress by another student at DTU 8 2 Scheduling As mentioned previously the scheduling should be kept simple and easy to replace The scheduling is based on the process priority and follow the 8 3 Timer 45 rule at any given time only the process with highest priority should be running As shown o
149. st pFirst If there is a higher priority ready task switch to it if process current id process highest id process old process current process new process highest process new state RUNNING process current process new process old state READY kernel semaphore c x Semaphore implementation This semaphore is implemented as a binary semaphore with a queue sorted by priority The idea for this semaphore implementation comes from ADEOS ADEOS do not have PIP protocol This file is subject to the terms and conditions of the GNU General Public License See the file COPYING in the main directory of this archive for more details x X 0X X X X X include lt system h gt include lt process h gt include lt semaphore h gt include lt kernel h gt include lt sched h gt void semaphore_setup t_semaphore pS long flags save and cli flags pS state FREE list_init amp pS gt list_waiting restore flags flags j Wait for a semaphore void semaphore wait t semaphorex pS 157 long flags t process process calling t_process process_semlocker save and cli flags printf if pS else sem_wait_ gt state FREE printf free Ya The semaphore is available take it pS state LOCKED Update who owns
150. t define UART_MCR_OUT1 0x04 Out1 complement define UART_MCR_OUT2 0x08 Out2 complement define UART MCR LOOP 0x10 Enable loopback test mode These the definitions for the Line Status Register LSR define UART LSR DR 0x01 Receiver data ready define UART LSR OE 0x02 x Overrun error indicator x define UART LSR PE 0x04 Parity error indicator define UART LSR FE 0x08 Frame error indicator x define UART LSR BI 0x10 x Break interrupt indicator define UART LSR THRE 0x20 Transmit hold register empty x define UART LSR TEMT 0x40 Transmitter empty x These are the definitions for the Modem Status Register MSR define UART MSR DCTS 0x01 Delta CTS define UART MSR DDSR 0x02 Delta DSR x define UART MSR TERI 0x04 Trailing edge ring indicator define UART MSR DDCD 0x08 Delta DCD x define UART ANY DELTA 0x0F Any of the delta bits define UART CTS 0x10 Clear to Send x define UART MSR DSR 0x20 Data Set Ready define UART MSR RI 0x40 Ring Indicator define UART MSR DCD 0x80 Data Carrier Detect int serial putchar char c void serial print char buf void serialinit void endif SERIAL_H x include setjmp h setjmp header This file is MIPS64 specific This file is subject to the terms and conditions of the GNU General Public Lice
151. t pPrev NULL VO else pElement pPrev pHead gt pLast pHead gt pLast gt pNext pElement pHead gt pLast pElement pHead number4 4 146 Appendix B Source code Put Element2 after Element1 void list put after t list head pHead t list element pElement1 t list element pElement2 if pElement1 NULL pElementl pHead gt pLast list put pHead pElement2 return pElement2 gt pNext pElement1 pNext pElement1 pNext pElement2 pElement2 pPrev pElement1 pElement2 pNext pPrev pElement2 pHead number4 4 Put Element2 before Element1 void list put before t list head pHead t list element pElement1 t list element pElement2 if pElement1 pHead gt pFirst pElement2 gt pPrev NULL pElement2 pNext pElement1 pElement1 pPrev pElement2 pHead gt pFirst pElement2 else pElement1 gt pPrev gt pNext pElement2 pElement2 pNext pElement1 pElement2 gt pPrev pElement1 pPrev pElement1 pPrev pElement2 pHead number4 4 Get first element from list t list element list get t list head pHead t list element pRet if pRet pHead gt pFirst NULL return NULL if pRet pHead gt pLast pHead gt pFirst pHead gt pLast NULL el
152. t 3 Changing from a process preempted by an interrupt to a process preempted by an interrupt 4 Changing from a process preempted by a using a semaphore to process preempted by a using a semaphore 52 Chapter 8 Kernel design It is point 1 and 2 which make things difficult because the two different types of context switch have to coorporate How this is solved in practice is described in detail in chapter 10 8 7 Global exception handling As stated in Kernel properties chapter 8 the use of global exception handling in an embedded system to handle failures in a modular manner could be of great advantage in bug finding and system recovery thus meth ods for implementing exceptions in C should be analysed This issue will in the following only be described briefly since it was not used in the kernel and the reasoning for not using exceptions will be stated Exception handling provides a way of transferring control and information from a point in the execution of a program to an exception handler asso ciated with a point previously passed by the execution handler will be invoked only by a throw expression invoked in code executed in the han dler s try block or in functions called from the handler s try block What is trying to be achieved in C is something similar to the following try Do something and throw an exception if something goes wrong x catch Handle it here if something went wr
153. t controllers swap8ad volatile swap8ad volatile swap8ad volatile swap8ad volatile swap8ad volatile swap8ad 11 dr MALTA GT PORT BA unsigned char ctr 21 dr MALTA GT PORT BA unsigned char xctr 12 dr MALTA GT PORT BA unsigned char ctr 22 dr MALTA GT PORT BA unsigned char xctr 13 dr MALTA GT PORT unsigned char xctr dr MALTA GT PORT BASE specific functions x unsigned char x SE uns SE uns SE uns SE uns SE 23 uns PI PI PI PI PI static unsigned int cached_int_mask Oxffff Disable irq in the 82C59 interrupt controller x static void disable unsigned int irq nr unsigned long flags if irq n r gt MAX_INT PI XA XA XA XA XA XA CTL igned char CTL igned char CTL igned char CTL igned char CTL igned char CTL R1 OCWI1 R2 OCWI1 R1 OCWJ2 R2 OCWJ2 R1 OCW3 R2 OCW3 140 Appendix B Source code printf whee invalid irq nr d n irq nr panic IRQ you lose save and cli flags cached int mask 1 lt lt irq nr if amp 8 ctrl21 cached int mask gt gt 8 amp Oxff else xctrlll cached_int_mask amp Oxff restore flags flags Enable irq in the 82C59 interrupt control
154. t0 CONF CM CMASK or t0 CONF CM UNCACHED mtc0 t0 CPO CONFIG nop Some nops to let the dust settle x nop nop 163 Setup stack pointer la Sp sp Clear bss la t0 fbss First address la tl end Last address x bbs zero sw zero 0 0 bne 40 t1 bbs zero addiu t0 4 Get ready to jump to main move 850 ra la t0 entry Jump to main x jal 0 Delay slot We should never en up here PROM PRINTY Kernel terminated n set reorder END start kernel test1 c Test process 1 Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include lt printf h gt include lt timer h gt void process_1 void t_timer t int i timer setup amp t timer start amp t 10000 PERIODIC while 1 printf Test process 1 n printf 1 call n process list print amp process list timer_waitfor amp t for i 0 i lt 1000000 i do nothing x kernel test2 c 164 Appendix B Source code Test process 2 Public License See the file COPYING in the main directory of This file is subject to the terms and conditions of the GNU General this archive for more details include lt lcd h gt include lt timer h gt static
155. tart o 0x80200000 Figure 10 2 Overview of the linked kernel After the linking of the kernel it is still not ready for use on the MIPS64 system As mentioned previously the output format of the file is 32 bits elf code but it has to be 64 bits elf code since it is a 64 bit kernel Besides that all the addresses have to be converted from 32 bits addresses to 64 bits addresses Both of these conversions are easily done by the program objcopy 72 Chapter 10 Kernel implementation To be able to load the kernel on the MIPS64 system the linked kernel has to be converted into srec format since this is the only file format that YAMON can handle The srec format is the Motorola S records format which is a format that makes it easier to transfer files over low speed connection with a high error rate and using an extremely simple protocol like the TFTP protocol This conversion is done with objcopy as well 10 3 Header files There is only one special thing which has to be noted about the header files and this is the use of the file stdarg h This is a header from the glibc library which defines a set of hardware specific macros for implementing the functionality of passing an arbitrary number of arguments passed on to functions The header file does not provide any function prototypes to glibc itself and can therefore safely be used in the kernel implementation To be more specific it is used in the kernel implementation of printf
156. tches are included in the RPM as well RedHat GNUpro This is RedHat s 24 commercial version of the GNU toolkits Even though it is not free it is worth mentioning this toolkit The toolkit includes support for a lot of different platforms includ ing MIPS 32 64 One really nice feature of the compiler toolchain is that you can choose between little endian and big endian and be tween MIPS 32 and MIPS 64 ABI Application Binary Interface as 6 3 Floating point 27 a compile option In the normal GCC toolchain you will have to have a different toolchain for each architecture Another great thing is the graphical debugger interface to gdb see 6 4 chapter Besides lot of great features you will also get support if you buy this product Instead of getting a pre compiled cross development toolchain you can build the toolchain yourself as mentioned earlier this could very well lead to problems but it is possible The information on actually doing this is very sparse and the official cross compiler HOWTO has not been updated for several years If the latest toolchain for some reason is needed for this kernel project the trick is then to first build binutils ld gasm etc and then only enable the C language when building GCC There is then no need for the C library which is not used for this kernel development anyway For this project I chose to use the pre compiled RPM from the SGI Linux project There are several reasons
157. the hardware That is if the hardware manufacturer provides hardware with a small BIOS or no BIOS at all this has to be compensated for in the boot loader In the following four different free software boot loaders will be described and some of their system specific features will be mentioned LILO LInux LOader LILO 30 has been the standard boot loader for Linux on the Intel platform for a long time It is placed in the boot sector of a floppy disc or in the master boot record of a harddisc and is therefore executed right after the PC BIOS is done with hardware initialization To enable LILO to load a kernel the location of a kernel on the disc media is hardcoded into LILO As an example on how the boot loader compensates for the shortcomings of the PC BIOS LILO extends the PC BIOS harddisc drivers since older PC BIOSes cannot address a kernel if it is not located within the first 1024 cylinders of the harddics GRUB GRand Unified Bootloader 81 is a very dynamic boot loader and for that reason becoming an increasingly popular boot loader for the Intel platform GRUB is file system aware so that the location of the kernel on a disc media does not have to be hard coded into boot loader as it was the case with LILO GRUB is also compliant to the Multiboot Specification which is an initiative to standardize the booting of different operating system s kernels If the kernel developed in this project is going to be ported t
158. the kernel or call the boot loader which loads the kernel 6 Transfer the control to the loaded kernel and the kernel bootstrap is executed The kernel bootstrap is most likely the same as step 1 through 4 again Step number 5 is the one step that differs mostly from system to system since the kernel can be loaded from a lot of different devices such as from a flash disc a floppy disc a harddisc over an ethernet or even over the Internet All of these different devices have to have a device driver to provide access for the boot loader or the BIOS to load the kernel One could say that step 5 provides the glue between the initial bootstrapping and the kernel bootstrapping and that the glue is provided by the BIOS or a boot loader More about boot loaders below In very small systems like the previously mentioned AT91 step 1 through 4 are the kernel bootstrap and step 5 and 6 are not needed This is because the bootstrap and the kernel lie as one continuous piece of code in the flash RAM and the kernel can therefore be loaded without special communication with other devices 58 Chapter 9 Bootstrapping 9 2 Introduction to boot loaders mentioned above the boot loader provides the glue between the BIOS and the actual kernel bootstrapping that is it is responsible for loading a kernel and transferring the control to the kernel Boot loaders vary a lot from system to system due to the differences in the BIOS provided by
159. the last instruction in the interrupt handler is executed In the above the interrupt latency for the timer interrupt has been mini mized by allowing nesting of interrupts The interrupt handling time can be reduced in several ways First most of the interrupt handler could be written in assembly code reducing un necessary code generated by the compiler Secondly and this is often the issue which takes the most time not calling the scheduler at every inter rupt When handling an interrupt the handler is often aware of whether a scheduling is needed or not In this kernel all waiting processes are wait ing for a semaphore to be released If the interrupt handler releases a semaphore it knows that a scheduling decision has to be made and marks this by raising a flag This design removes all unnecessarily scheduling decisions The interrupt handler is summarized in the following Save the current state Increment the nesting level If timer interrupt then call its handler and go to 5 If combined hardware interrupt then enable the timer interrupt and call the combined hardware interrupt handler 5 If the flag indicating a scheduling decision has to be made is raised then call the scheduler Expo ll E 8 6 Context switch 51 6 Decrement the nesting level 7 Restore to the previous state or a new state and return This interrupt handler could easily be generalized to handle more than two priority levels But on the other hand
160. ther the code is written in C or Assembly does not matter It has on chip in system programmable Flash and EEPROM which makes it possible to upgrade the embedded software even after the microcontroller has been implemented in a larger system To do development on the AVR a viable choice would be to buy the STK500 development kit 2 which costs around 100 This development kit in cludes the 9058515 microcontroller which has 8Kb of flash memory but only 5Kb RAM The development kit comes with all necessary tools for developing software for the microcontroller but GCC also have very good support for all the different AVR microcontrollers The price and the development tools fulfill the requirements but the AVR is too limited in FLASH and RAM The RAM can be extended but only with SRAM and SRAM is very difficult to find since it has been replaced with newer types of RAM 4 4 Atmel AT91 ARM Thumb The Atmel AT91 microcontrollers are targeted at low power real time con trol applications They have already been successfully designed into MP3 players Data Acquisition products Pagers Medical equipment GPS and Networking systems Atmel s AT91 ARM Thumb microcontrollers provide the 32 bit perfor mance every 8 bit microcontroller user is dreaming of while staying within a tight system budget The AT91EB40 Evaluation costs around 200 and includes the AT91R40807 microcontroller This microcontroller has 16 bit instruc
161. tion set 136Kb of on chip SRAM 1Mb of flash 32 14 Chapter 4 Choosing hardware programmable I O lines 2 UART s 16 bit timers watchdog timers and many other features The GNU Compiler Collection also have a port of their tools for this mi crocontroller Red Hat has even ported their real time kernel eCos 28 to this microcontroller so the community support for this microcontroller is good This microcontroller definitely fulfills all the requirements given to the hard ware It is cheap it has the right tools it has enough memory to do a lot of stack operations and it has a wide community support 4 5 MIPS Malta development board The MIPS processors are widely used in the industry and comes in many shapes MIPS has several development boards where the MIPS Malta development board is the most comfortable system to develop embedded kernels on The Malta board which is used in this project contains the 64 bits 5Kc MIPS CPU with 16x64Kb cache This may be a more powerful system than originally intended for this project The CPU is so powerful that Infineon Technologies chose to use it in their specialized local area net work switching applications The MIPS Malta development board will be described further in the next chapter MIPS supports the free software community very well and it is even pos sible to get a Linux kernel running on the Malta board The GCC is also ported to both MIPS32 and MIPS64 This system does
162. which specializes in em bedded Linux distributions and development kits They have a ver sion of their Hard Hat Linux distribution that runs on the MALTA board with a MIPS 32 processor Monta Vista supplies cross development toolchains with their product for MIPS 32 and for both little and big endian architecture All of Monta Vista s cross development packages come in forms of RPM packages Linux VR project Linux VR project 23 is a project that brings the Linux operating system to NEC VRSeries devices most of which were originally designed to run Windows CE The NEC VRSeries devices all contain MIPS processors The project developers have created a set of RPM packages that even includes the C library The difference compared to all the other toolchains is that this toolchain uses soft floating point More about this below SGI MIPS project SGI MIPS project 25 is SGI s project to create a Linux distribution for their MIPS based workstations like the Indy The SGI MIPS project has more or less become the centerpoint for all Linux MIPS development and a lot of valuable information can be received by joining their mailing list SGI MIPS project has created a nice collection of RPM s for doing cross development to both MIPS32 and MIPS64 The toolchains are based on a rather old version of the C compiler namely the EGCS compiler which is now merged with GCC Because it is old it is well tested and easy to install and all relevant pa
163. y protection such as the one mentioned in section Porting Porting the kernel to other platforms such as the AT91 or the Intel 1386 architecture The kernel has been designed and implemented with portability in mind and should be fairly easy to port to other platforms Remote debugging Remote debugging requires special support in the kernel Enabling remote kernel debugging would be a useful feature and an interesting project Scheduling Scheduling experimentation and analysis The kernel is small and easy to edit and different scheduling algorithms could be tried out without modifying much of the kernel For example changing the scheduler to earliest deadline first would not require touching any tricky assembly code at all 11 4 Summary 85 Real time Modification of the kernel in such way that it would be suitable hard real time system This would not require much coding but a thorough analysis of the kernel Kernel locking Create a finer grained locking and maybe even new mech anisms for the locking such as spin locks reduce the kernel latency locking needs thorough analysing 11 4 Summary Hopefully some of the above suggestion will inspire other students to con tinue the work on this kernel project 86 Chapter 11 Status 87 Chapter 12 Conclusion development system environment suitable for embedded system devel opment has been composed The environment includes Free Software tools
164. y and length is 0 n return j test first element x if process base pHead pFirst process elem pPrev NULL printf First element previous is NULL n test last element if process base pHead pLast gt process elem pNext NULL printf Last element next is not NULL An return print contents damn this loop is ugly for pNext pHead gt pFirst pNext NULL pNext process_base pNext gt process_elem pNext process_base pNext printf ID 96d Priority d State p gt id p gt priority switch p state case READY printf READY Wn break case RUNNING printf RUNNING Wn break case WAITING printf WAITING An break Test prevoius pointer if p gt process_elem pPrev pPrev printf Wrong previous pointer n pPrev pNext length test length 152 Appendix B Source code if length pHead gt number printf Wrong list length Counted 96d Expected d n length pHead number test last actually is last if pPrev pHead gt pLast printf Wrong last element in list n Insert process into ordered process list Highest front void process insert t list head pHead t list element pElement Get priority int priority process_base pElement gt priority
165. ystems implements the sharing and protection of memory between processes 34 Chapter 7 SASOS 7 2 Opal 12 is an experimental operating system developed at the University of Washington Seattle The purpose of Opal is to explore the strengths and weaknesses of the single address space approach Opal is built on top of the Mach 3 0 microkernel The fundamental mechanisms used for management of the single address space are described in the following In Opal a unit of protected allocated storage is called a segment A segment is in essence a contiguous set of virtual pages and the virtual address is permanently set by the system at allocation time The smallest possible segment is one page but segments are allocated in bigger chunks by the system to allow continuous growth of the data contained in the segment In Opal all processes are called threads and a protection domain is an execution context for threads which restricts their access to a specific set of segments at a particular instant in time Many threads may execute in the same protection domain see figure 7 1 The Opal protection domain is very similar to process on the Linux platform except that protection domains are not a private virtual address space The resources protection domains and segments are named by capabili ties capability is a reference that grant permission to operate on the resource in a specific way Given a segment capability an ex

AN EMBEDDED SYSTEMS KERNEL IMM

Contents

Download Pdf Manuals

Related Search

Related Contents