MSc Thesis Project: Minix Embedded System

Wednesday 7th.4.2004
TODAY!

Tuesday 6th.4.2004
(PLAN 1) Boot sequence in MINIX

Saturday 3rd.4.2004

(PLAN 1) I/O in MINIX (Source: Chapter 3 of OSDI)

Today, I read chapter 3 of MINIX book. It's getting clearer as I read this book again and again.

(PLAN 2) Embedded System and Embedded Processor (Source: chapter 1 & 2 of STEVE HEATH:Embedded Systems Design)

This book focuses on hardware parts of embedded system. I do not really need to read this book. However, I thought I need to have a basic understanding of hardware used in modern embedded system. This book was quite hard to read at first but it gave me an enough knowledge on what embedded system is and basic hardware used in embedded systems. At the end of book, there is a chapter on real-time operating system, I should read that chapter tomorrow.

The definition of embedded system is given in this book: "An embedded system is a microprocessor-based system that is built to control a range of functions and is not designed to be programmed by the end user in the same way that a PC is. A user can make choices concerning functionality but cannot change the functionality of the system by adding/ reaplcing software". The last point is what makes embedded system different from PC. However, PCs have provided an easily accessible source of hardware and software for embedded systems and that they form the basis of many embedded system. Embedded system usually has the following four components: processor, memory, peripherals, and software.(1) processor: This is a major component of an embedded system which determines if the embedded system has enough power needed to perform a specific tasks within the system. However, we shouldn't rely on the performance measurements provided by the vendor. Because they may execute completely out of cache memory and thus give an artificially high performance level which the final system can not meet because its software does not fit in the cache. (2) memory: memory is where software and data are stored. It is heavily influenced by the software design. (3) Peripherals: Embedded system communicates with outside world using peripherals. (4) Software: The software components is what decide what the embedded system does and how well it does it. There are many examples of embedded system: microcontroller, integrated processor, discrete processor. Microcontroller can be considered as self-contained systems with a processor, memory, and peripherals so that in many cases all that is needed to use them within an embedded system is to add software. They normally use very low-end processor such as 8-bit accumulator processors. Integrated processor combines all other components within a single chip like microprocessor. However, it uses a more powerful processors like the ones use in PC. This book also explained many embedded processors used in embedded system. For more detail, read chapter 2.

Friday 2nd.4.2004
(PLAN 2) Input and Output (Source: Chapter 3 of OSDI)

Thursday 1st.4.2004

(PLAN 1) ACK Assembler in MINIX (Source: MINIX FAQ and Wangzhiyi's MINIX assmbler manual)

(PLAN 1)Boot sequence of MINIX (Source: /src/include/boot and MOP)

Wednesday 31th.3.2004

(PLAN 1) CPU architecture, System organization (Source: Machine Architecture)

(PLAN 2) Assembly in Linux (Chapter 13 of Assembly SBS)

I finally finished reading this book! By studying assembly book, I gained a deeper knowledge of how computer system works.

Tuesday 30th.3.2004
(PLAN 1)Assembly language in Linux (Chapter 13 of Assembly SBS)

Monday 29th.3.2004
(PLAN 1)Interrupt Handling in MINIX (Chapter 2 of OSDI) The following is a detailed explanation of how interrupt handling is on for systems with 32-bit Intel CPU. Hardware interrupts are electrical signals, generated by hardware when it needs to communicate with CPU. Since CPU has only one input for sensing an interrupt. It needs to get help from other devices. This device is called an interrupt controller. An interrupt controller can sense a number of interrupts and for each one genertae a unique data pattern on the processor's data bus. In this way, CPU can determine which device generated the interrupt. In PCs using Intel 32-bit CPU, there are normally two interrupt controller, which one capable of handling eight inputs. When an interrupt occurs, A interrupt controller sends a signal to CPU's INT pin to notify CPU. CPU then sends INTA(interrupt acknowledge) signal to the controoler responsible for the interrupt to put data on the system bus telling which service routine to execute. Each interrupt controllers are programmed during system initialization, when main calls intr-init. There is a interrupt descriptor table which contains a table of up to 256 interrupt gate descriptors. An interrupt gate descriptor is a 8 byte structure with serveral fields. Some fields of the interrupt gate descriptors point to the service routin's executable code segment and the starting address within it. When CPU receives an interrupt while running a process, it sets up a new stack for interrupt service. The location of this new stack is determined by an entry in Task State Segment (TSS). This structure provides space for storage of processor registers and other information that must be saved when a task switch is made. In MINIX, we only use the fields that define where a new stack is to be built when an interrupt occurs. There is ony only stack state segment structure for entire system and it is modified as each process is started. The location of new stack starts at the end of the stackframe_s structure within the process table entry of the interrupted process. The CPU automatically pushes several key registers onto this new stack, including those necessary to reinstate the interrupted process' own stack and restore its program counter. When the interrupt handler code starts running, it uses this area in the process table as its stack, and much of the information needed to return to the interrupted process will have already been stored. The interrupt handler pushes the contents of additional registers, fillling the stackframe, and then switches to a stack provided by kernel while it does whatever must be done to service the interrupt. Termination of an interrupt service routines is done by switching the stack from the kernel stack back to a stackframe in the process table, explicitly pooing addtional registers, and executing an iretd instruction. Iretd restores the state that existed before an interrupt, restoring the registers that were pushed by the wardware and switching back to a stack that was in use use before an interrupt. Remember that nothing is stored on the interrupted process' working stack during an interrupt. To start a different process all that is required is to point the stack pointer to another process' stackframe, pop the registers that were explicitly pushed, and execute an iretd. CPU automatically disables all interrupts when it receives an interrupt. It ensures that nothing can occur to cause the stackframe iwthin a profcess table entry to overflow. The interrupt handler re-enables interrupts aftering switching to the kernel stack, located outside the process table. For more detailed discussion of how an interrupt is handled in MINIX, please read page 128 -137 of OSDI. Software interrupt is very similar to hardware interrupt. It only differs from hardware interrupt that it is caused by system call called by process. Software interrupt can be thought as an interrupt which does not interrupt anything. It provides mechanism for user-process request kernel to do some-work on behalf of user process. In addition to hardware and software interrupt, various error conditions internal to the CPU can cause the initiation of an exeception. Exceptions are handled by the same mechanism as interrupts, using descriptors in the interrupt descriptors table. (PLAN 2)Interprocess communication in MINIX (Chapter 2 of OSDI) In MINIX, all interprocess communications are performed using the rendezvous message passing. By rendezvous, we mean no buffering, that is, the sender is blocked until the receiver actually receives messages. User-process is only allowed to talk to FS,MM. It is also restricted to use send_rec method. When a process process sends a message using this message, it has to wait for the reply from FS,MM. This is to prevent from user process sending a message to MM or FS and not receiving a reply, thus blocking MM or FS. (PLAN 3)Scheduling in MINIX (Chapter 2 of OSDI) In MINIX, there are 3 scheduling queues: task queue, server queue, and userprocess queue. When MINIX needs to pick a process to run, It first looks at task queue and run the first element in this queue. If it is empty, it looks at the server queue and run the first element in this queue. If server queue is empty as well, it looks at userprocess queue and run the first process in the queue. In MINIX, task and server can run as long as they want. The only exception is interrupt. User process, on the other hand, is given a fixed amount of time slice. When user process uses up all its time slice, it is put at the end of userprocess queue. (PLAN 3)Bootsequence in MINIX (MOP Website> (PLAN 4)Relevant messages from MINIX newsgroup There has been a lot of discussion going on in MINIX newsgroup on whether MINIX is a segmented OS or not. The following message is from Kees on this matter. Date: Sat, 27 Mar 2004 11:20:37 +0100 From: Kees J Bot Newsgroups: comp.os.minix Subject: Re: how works linking and loading in minix? In article , Giovanni Falzoni wrote: > >But this doesn't make Minix implemented as a "Flat" system with no >segmentation at all. I remembered to late that I don't like theoretical discussions, because they tend to turn into a quarrel about definitions. (Besides, I'm not good at it.) So I just say this: If Minix use of i*86 segments makes it a segmented operating system, then me putting on a wool coat makes me a sheep. For an OS to be a segmented OS it has to use segments throughout, by putting files and objects in segments, processes shareing segments with other processes, etc. The usual example for an OS that did such things is Multics. The following message explains how interrupt process communication is done in MINIX. More detailed explanation on MINIX interprocess communication can be found on 137-140 OF ODSI. All the interprocses communication related stuffs are handled in handled in proc.h and proc.h >I read Tanenbaum's book that Minix enforces a restriction that user >processes may not directly communicate with I/O tasks. That's mostly for security reasons. User processes can only use sendrec() because they must stall waiting for a reply (we don't want them to do send() and then never bother to receive()). We don't let them talk to tasks so that tasks don't have to bother checking who they're dealing with. And we don't allow user processes to talk to other user processes, because they might stall on each other in a way that MM and FS can't undo. >And each >process or task can send and receive messages from processes and tasks >in its own layer and from those in the layer directly below it. Don't think of it as layers, it's different. To avoid deadlock if task or server X calls Y then Y may never call X. So there's a partial ordering of who may call who[1]: User processes -> MM or FS MM -> FS MM or FS -> tasks tasks -> CLOCK >If my thinking is wrong, hope someone gives me hands. So what also >caused trouble to clock? All the troubles with unbuffered message passing stem from the partial ordering above. As long as communication is driven from the top there is no problem, but asynchronous events (timers and interrupts) mess things up. The CLOCK task handles timers in two ways: They are either turned into signals or they are handled by the synchronous alarm task. The SYN_AL task only sends messages, so it's outside the partial ordering. With timers done we are left with interrupts and signals. Interrupts are turned by interrupt handlers into interrupt messages that are delivered in a special way. If possible they are delivered immediately to the task that must handle them, but if the task is blocked then a bit is set in the process table to tell that an interrupt message must be sent as soon as the task is listening. (This is rather nonsimple, see kernel/proc.c::interrupt().) This leaves signals. Signals are like interrupts, but at user level. MM takes a running process, dumps the current state on its stack, puts the address of the signal handler in the program counter and lets the program continue from there. Unless the signal is ignored, masked or unhandled, then nothing is done, the signal is set "pending" or the process is killed. Signals can be generated in MM, but they can also start in FS (SIGPIPE) or in tasks (SIGALRM, SIGINT, etc.). Alas MM is at the top of the task/server call graph, so sending it a signal message may cause deadlock. FS solves the problem by making it someone elses problem, it asks the SYSTEM task to do it. So now only the tasks need to send signal messages to MM. The tasks live in the kernel, so they know what state MM is in simply by looking at MM's flags in the process table. So if MM is listening then it gets a signal message, otherwise a bit is set for the signal with the user process that it should be sent to, and delivery is postponed until MM is willing to listen. Since there's only one bit per signal per process this means that only one signal can be remembered, the rest are discarded. (Interrupts and signals are "at least once".) See system.c::cause_sig() and inform() for the signal code.

Monday 29th.3.2004

(PLAN 1)Interrupt Handling in MINIX (Chapter 2 of OSDI)

The following is a detailed explanation of how interrupt handling is on for systems with 32-bit Intel CPU. Hardware interrupts are electrical signals, generated by hardware when it needs to communicate with CPU. Since CPU has only one input for sensing an interrupt. It needs to get help from other devices. This device is called an interrupt controller. An interrupt controller can sense a number of interrupts and for each one genertae a unique data pattern on the processor's data bus. In this way, CPU can determine which device generated the interrupt. In PCs using Intel 32-bit CPU, there are normally two interrupt controller, which one capable of handling eight inputs. When an interrupt occurs, A interrupt controller sends a signal to CPU's INT pin to notify CPU. CPU then sends INTA(interrupt acknowledge) signal to the controoler responsible for the interrupt to put data on the system bus telling which service routine to execute. Each interrupt controllers are programmed during system initialization, when main calls intr-init. There is a interrupt descriptor table which contains a table of up to 256 interrupt gate descriptors. An interrupt gate descriptor is a 8 byte structure with serveral fields. Some fields of the interrupt gate descriptors point to the service routin's executable code segment and the starting address within it. When CPU receives an interrupt while running a process, it sets up a new stack for interrupt service. The location of this new stack is determined by an entry in Task State Segment (TSS). This structure provides space for storage of processor registers and other information that must be saved when a task switch is made. In MINIX, we only use the fields that define where a new stack is to be built when an interrupt occurs. There is ony only stack state segment structure for entire system and it is modified as each process is started. The location of new stack starts at the end of the stackframe_s structure within the process table entry of the interrupted process. The CPU automatically pushes several key registers onto this new stack, including those necessary to reinstate the interrupted process' own stack and restore its program counter. When the interrupt handler code starts running, it uses this area in the process table as its stack, and much of the information needed to return to the interrupted process will have already been stored. The interrupt handler pushes the contents of additional registers, fillling the stackframe, and then switches to a stack provided by kernel while it does whatever must be done to service the interrupt. Termination of an interrupt service routines is done by switching the stack from the kernel stack back to a stackframe in the process table, explicitly pooing addtional registers, and executing an iretd instruction. Iretd restores the state that existed before an interrupt, restoring the registers that were pushed by the wardware and switching back to a stack that was in use use before an interrupt. Remember that nothing is stored on the interrupted process' working stack during an interrupt. To start a different process all that is required is to point the stack pointer to another process' stackframe, pop the registers that were explicitly pushed, and execute an iretd. CPU automatically disables all interrupts when it receives an interrupt. It ensures that nothing can occur to cause the stackframe iwthin a profcess table entry to overflow. The interrupt handler re-enables interrupts aftering switching to the kernel stack, located outside the process table. For more detailed discussion of how an interrupt is handled in MINIX, please read page 128 -137 of OSDI. Software interrupt is very similar to hardware interrupt. It only differs from hardware interrupt that it is caused by system call called by process. Software interrupt can be thought as an interrupt which does not interrupt anything. It provides mechanism for user-process request kernel to do some-work on behalf of user process. In addition to hardware and software interrupt, various error conditions internal to the CPU can cause the initiation of an exeception. Exceptions are handled by the same mechanism as interrupts, using descriptors in the interrupt descriptors table.

(PLAN 2)Interprocess communication in MINIX (Chapter 2 of OSDI)

In MINIX, all interprocess communications are performed using the rendezvous message passing. By rendezvous, we mean no buffering, that is, the sender is blocked until the receiver actually receives messages. User-process is only allowed to talk to FS,MM. It is also restricted to use send_rec method. When a process process sends a message using this message, it has to wait for the reply from FS,MM. This is to prevent from user process sending a message to MM or FS and not receiving a reply, thus blocking MM or FS.

(PLAN 3)Scheduling in MINIX (Chapter 2 of OSDI)

In MINIX, there are 3 scheduling queues: task queue, server queue, and userprocess queue. When MINIX needs to pick a process to run, It first looks at task queue and run the first element in this queue. If it is empty, it looks at the server queue and run the first element in this queue. If server queue is empty as well, it looks at userprocess queue and run the first process in the queue. In MINIX, task and server can run as long as they want. The only exception is interrupt. User process, on the other hand, is given a fixed amount of time slice. When user process uses up all its time slice, it is put at the end of userprocess queue.

(PLAN 3)Bootsequence in MINIX (MOP Website>

(PLAN 4)Relevant messages from MINIX newsgroup

There has been a lot of discussion going on in MINIX newsgroup on whether MINIX is a segmented OS or not. The following message is from Kees on this matter.

      Date: Sat, 27 Mar 2004 11:20:37 +0100
From: Kees J Bot 
Newsgroups: comp.os.minix
Subject: Re: how works linking and loading in minix?

In article ,
Giovanni Falzoni   wrote:
>
>But this doesn't make Minix implemented as a "Flat" system with no
>segmentation at all.

I remembered to late that I don't like theoretical discussions, because
they tend to turn into a quarrel about definitions.  (Besides, I'm not
good at it.)  So I just say this:

If Minix use of i*86 segments makes it a segmented operating system, then
me putting on a wool coat makes me a sheep.  For an OS to be a segmented
OS it has to use segments throughout, by putting files and objects in
segments, processes shareing segments with other processes, etc.  The
usual example for an OS that did such things is Multics.

The following message explains how interrupt process communication is done in MINIX. More detailed explanation on MINIX interprocess communication can be found on 137-140 OF ODSI. All the interprocses communication related stuffs are handled in handled in proc.h and proc.h

>I read Tanenbaum's book that Minix enforces a restriction that user
>processes may not directly communicate with I/O tasks.
                                                                       
That's mostly for security reasons.  User processes can only use
sendrec() because they must stall waiting for a reply (we don't want
them to do send() and then never bother to receive()).  We don't let
them talk to tasks so that tasks don't have to bother checking who
they're dealing with.  And we don't allow user processes to talk to
other user processes, because they might stall on each other in a way
that MM and FS can't undo.
                                                                             
>And each
>process or task can send and receive messages from processes and tasks
>in its own layer and from those in the layer directly below it.
                                                                         
Don't think of it as layers, it's different.  To avoid deadlock if task
or server X calls Y then Y may never call X.  So there's a partial
ordering of who may call who[1]:
                                                                       
        User processes ->  MM or FS
        MM -> FS
        MM or FS -> tasks
        tasks -> CLOCK
                                                                         
>If my thinking is wrong, hope someone gives me hands. So what also
>caused trouble to clock?
                                                                         
All the troubles with unbuffered message passing stem from the partial
ordering above.  As long as communication is driven from the top there
is no problem, but asynchronous events (timers and interrupts) mess
things up.
The CLOCK task handles timers in two ways: They are either turned into
signals or they are handled by the synchronous alarm task.  The SYN_AL
task only sends messages, so it's outside the partial ordering.
                                                                         
With timers done we are left with interrupts and signals.  Interrupts
are turned by interrupt handlers into interrupt messages that are
delivered in a special way.  If possible they are delivered immediately
to the task that must handle them, but if the task is blocked then a bit
is set in the process table to tell that an interrupt message must be
sent as soon as the task is listening.  (This is rather nonsimple, see
kernel/proc.c::interrupt().)
                                                                         
This leaves signals.  Signals are like interrupts, but at user level.
MM takes a running process, dumps the current state on its stack, puts
the address of the signal handler in the program counter and lets the
program continue from there.  Unless the signal is ignored, masked or
unhandled, then nothing is done, the signal is set "pending" or the
process is killed.  Signals can be generated in MM, but they can also
start in FS (SIGPIPE) or in tasks (SIGALRM, SIGINT, etc.).
                                                                       
Alas MM is at the top of the task/server call graph, so sending it a
signal message may cause deadlock.  FS solves the problem by making it
someone elses problem, it asks the SYSTEM task to do it.  So now only
the tasks need to send signal messages to MM.
                                                                        
The tasks live in the kernel, so they know what state MM is in simply by
looking at MM's flags in the process table.  So if MM is listening then
it gets a signal message, otherwise a bit is set for the signal with the
user process that it should be sent to, and delivery is postponed until
MM is willing to listen.  Since there's only one bit per signal per
process this means that only one signal can be remembered, the rest are
discarded.  (Interrupts and signals are "at least once".)  See
system.c::cause_sig() and inform() for the signal code.

Sundary 28th.3.2004

(PLAN 1) How boot monitor loads MINIX image in MINIX(Source: Chapter2 of OSDI)

*mpx386.s on 06468-6491 of MINIX source book & on page 120 of ODSI*

      .sizes:
              .data2 0x526F 
              .space 16*2*2-2

The first insturction allocates 2 bytes in the memory and write 0x526F in there. And the last instruction reserves 62 bytes. The size of _sizes array is (62+2=64). At the very beginning of kernel's data segment, _size array is created. It contains the magic number which is used to identify a valid MINIX kernel (this information is written by compiler). This number is read by, and then overwritten by the boot monitor. It will contain sizes of kernle, mm,fs, fs filled in by boot. This must be the first data entry monitor uses beprevious word._size array also contains addtional space which can be used to hold the sizes of idfferent parts of the MINIX system by boot monitor.

*page 122 of ODSI* MINIX image loadded by boot is nothring more than a concatenation of the individual files produced by the compier when the kernel, memory manager, file system, and init programs are compiled. Each of these compomenents includes a short header of type defied in include/a.out.h (It defines the header for the executable file in MINIX), and from the information in the header of each part, boot determines how much space to reserve for uninitialized data after loading the executable code, and initialize data for each part, so the next part can be loaded at the proper place. The _size array mentioned in the the above also receives a copy of this information so the kernel itself can have access to the locations and sizes of all the modules loaded by boot. The regions of memory available for loading the bootsector, boot itself, and MINIX will depend unon th hardware

*page 126 of OSDI* 8088 CPU had read-only memory at the top of the usable range of memory, which is limited to 1 MB. For compatibility reasons, all modern pc-compatible machines still have read-only memory at the same address as the older machines. Thus, the read-write memory is discontinuous, with a block of ROM between the lower 640KB and the upper range above 1MB. All servers are placed above 1MB so file system can have very large block caches without bumping into the read-only memory.

*HARDWARE process* in MINIX, this process is credited with the time used while servicing an interrupt.

Saturday 27th.3.2004

(PLAN 1) Assembly language in Linux (Source: Chapter 12 of Assembly SBS)

I've read chapter 12 of Assembly SBS, which explains how to use assembly language in Linux. The following is a brief summary of the chapter.

It first starts off by explaining what GNU tools are. Back in late 1970s, a guy named Richard Stallman started to write his own copy of UNIX. First, he decided to write all the tools (compilers, linkers, assemblers, and debugger) required to write the operating system. Stallman had named his version of UNIX GNU. GNU stands for GNU's Not Unix. Although he could not finish writing GNU. He sets up Free Software Software Foundation as the home base of GNU tools and created a software license called the GNU Public License(GPL). He released all GNU tools under the GPL, which not only required that the software be free (including all source code, but prevented people from making minor mods to the software and claiming the derivate work as their own. Changes and improvements had to be given back to GNU community. Many software has been released under GPL because large number of people were using it and improving it and giving back the improvements. Linux was one of them. It was built using GNU tools sets.

*The process of making a executable program out of C source codes using GNU tools in Linux* When a user invokes a gcc to generate an executable binary file from C source code, gcc first invokes a utility, called cpp. cpp is a c-preprocessor who job is to read in c source codes and handles all preprocessor directives in them. When cpp finishes all the preprocessing, it gives its output to gcc, which generates assembly language source codes file with .s file extensions. When gcc has completed its job, gas is called by gcc to assemble all the .s files produced by gcc. The final step is linking all object files, produced by gas, to form an executible binary. ld is called by gcc to handle all the linking process. However, ld does knot what part of the standard libraries are needed. gcc provides all the relevant informations, such as what needs to be linked, to ld.

*using makefile* a make file is a blueprint which defines all the dependencies required to create each parts of program. Each dependency specifies what parts of a programs are needed to create other parts of the program and how it should be done.

*AT&T instruction Mnemonics used in gas (GNU Assembler)* There is only one machine instruction set on a particular CPU. Each machine instruction set is a pure binary bit patterns that were never intended to be readable by human. A mnemonic is just a way for human beings to remember each binary bit pattern. There can be many different set of instruction mnemonics on given machine instruction set. In Unix world, they use different mnemonic sets. It is because the poeple who originally created UNIX also wished to create a family of nearly portable assemblers to help implement UNIX on a new platforms. What they did was create a set of global conventions that all assemblers within the UNIX family would adhere to. This convention is called AT&T mnemonics. Here is a list of the differents between Intel mnemonic set and AT&T mnemonic set. (1) AT&T mnemonics and register names are invariably in lowecase. (2) Register names are always preceded by % (3) Every AT&T machine instruction mnemonic that has operands has a single-character suffix indicating how large its operands are. For exmplae, MOV BX,AX would be written movw %ax,%bx (4) In the AT&T syntax, source and destination operands are placed in the opposite order from Intex syntax. (5) In the AT&T syntax, immediate operads are always preceded by $ (6) Not all intel instruction mnemonics have AT&T equivalents. (7) In the AT&T syntax, displacements in memory references are signed quantites placed outside parentheses containing the base,index, and scale values. (8) When an instruction does not take operands, it does not have an operand-size suffix. (9) When referenced, the name of a message string is prefixed by & the same way that numeric literals are (10) Comments delimeter is # (11) +-disp(base,index,scale) <- AT&T memory reference (11) We use () instead of [] when accessing the contents in specific memory address.

(TO BE CONTINUED)

(PLAN 2) Implementation of Processes in MINIX(Source: Chapter 2 of Minix)

SangHyeb Lee(shlee@cs.otago.ac.nz)

Last updated: Thursday, March 11, 2004 8:57 AM