Microkernel(relative to monolithic kernel)

Microkernel(relative to monolithic kernel)

Microkernel is the near-minimum amount of software that can provide the mechanisms needed to implement an operating system (OS). From this sentence, we can get several points below:

1) Microkernel is very small.

2) Microkernel contains some program such as low-level address space management, thread management, scheduling, IPC(inter-process communication) and so on which are all very basic tools.

3) The functionalities mentioned above are all very necessary for a OS kernel(here kernel don't need to provide these features any more, maybe just some drivers, internet module or something else). So Microkernel OS is much more portable because of its small size.

4) Here other operating systems are implemented on user mode above the microkernel.

5) From the picture below, we can see that an obvious difference between Microkernel and Monolithic kernel is that application in Monolithic kernel communicate with kernel level through system call. However application in Microkernel OS communicate with drivers, servers, and other applications through IPC instead of system call.

As a microkernel must allow building arbitrary operating system services on top, it must provide some core functionality. At the least, this includes:

    1) some mechanisms for dealing with address spaces — this is required for managing memory protection;

    2) some execution abstraction to manage CPU allocation — typically threads or scheduler activations; and

    3) inter-process communication — required to invoke servers running in their own address spaces.

Full stack and empty stack

Full stack and empty stack

Full stack:

A full stack is where the stack pointer points to the last data item written

Empty stack:

Empty stack is where the stack pointer points to the first free slot.

How to manage a stack:

Only 56 instructions in ARM Cortex-M0

16-Bit Thumb Instructions Supported on the Cortex-M0 Processor

ADC      ADD        ADR     AND     ASR     B           BIC        BLX          BKPT     BX

CMN     CMP        CPS      EOR     LDM     LDR     LDRH     LDRSH     LDRB     LDRSB

LSL        LSR         MOV    MVN    MUL    NOP     ORR       POP          PUSH     REV

REV16   REVSH    ROR     RSB      SBC     SEV      STM       STR          STRH      STRB

SUB       SVC         SXTB   SXTH   TST      UXTB   UXTH    WFE         WFI         YIELD

32-Bit Thumb Instructions Supported on the Cortex-M0 Processor

BL     DSB     DMB     ISB     MRS     MSR

The instructions in the Cortex-M0 processor can be divided into various groups based on functionality:

• Moving data within the processor (MOV  MRS  MSR)
• Memory accesses (LDR  LDRH  LDRB  LDRSH  LDRSB  STR  STRH  STRB  LDM  STM)
• Stack memory accesses (PUSH  POP)
• Arithmetic operations (ADD  ADR  SUB  ADC  SBC  RSB  MUL  CMP  CMN)
• Logic operations (AND  ORR  EOR  BIC  MVN  TST)
• Shift and rotate operations (ASR  LSL  LSR  ROR )
• Extend and reverse ordering operations (REV  REV16  REVSH  SXTB  SXTH  UXTB  UXTH)
• Program flow control (branch, conditional branch, and function calls) (B  BL  BX  BLX)
• Memory barrier instructions (DMB  DSB  ISB)
• Exception-related instructions (SVC  CPS)
• Sleep mode feature-related instructions (WFI  WFE  SEV)
• Other functions (NOP  BKPT  YIELD)

Status flags

Status flags in ARM processor

The most common status flags are: V (overflow), N (sign status), Z (zero or not), C (carry bit, remember it is not borrow bit of substraction).

• V - This flag is set when the sign of result is wrong. This methodology is called "twos complement"
• • For addition, V is set if msb (s) is equal to msb (d) and msb (result) is not equal to msb (d), which means the addition two positive numbers is negative, or the addition of two negative numbers is positive.
  • For substraction, V is set if msb (s) is not equal to msb (d) and msb (result) is not equal to msb (d), which means the result of one positive number substracting negative number is negative, or the result of one negative number substracting positive number is positive.
  • Anyway, because the most significant bit represents the sign bit, so when we do some operation with large number which will make the result exceed the scope of operand. V represents the wrong operation. 
  • Because assembly number cannot recognize signed or unsigned, so with the help of V bit we can control the calculation is signed or unsigned.
• N - It is set is msb of the result is 1 which means the result can be treated as negative number.
• Z - It is set if the result is zero.
• C - It is set if the result of addition exceed the destination register and is cleared if a substraction generates a borrow bit. We will talk about this in the next part for detail.

Carry flag vs. Borrow flag[1]

"While the carry flag is well-defined for addition, there are two possible ways to use the carry flag for subtractive operations.

One uses the bit as a borrow flag, setting it if a<b when computing a−b, and a borrow must be performed. A subtract with borrow (SBB) instruction will compute a−b−C = a−(b+C), while a subtract without borrow (SUB) acts as if the borrow bit were clear. The 8080, Z80, x86 and 68k families (among others) use a borrow bit.^[1]

The other takes advantage of the identity that −x = not(x)+1 and computes a−b as a+not(b)+1. The carry flag is set according to this addition, and subtract with carry computes a+not(b)+C, while subtract without carry acts as if the carry bit were set. The 6502 and PowerPC processors use this convention. The 6502 is a particularly well-known example because it does not have a subtract without carry operation, so software must ensure that the carry flag is set before every subtract operation where a borrow is not required.

The modern convention is to refer to the first alternative as a "borrow bit", while the second is called a "carry bit". However, there are exceptions in both directions; the VAX and NS320xx architectures use the borrow bit convention, but call their a−b−C operation "subtract with carry" (SBWC). PA-RISC uses a carry bit convention, but calls its a+not(b)+C operation "subtract with borrow" (SUBB)."

There are two types of substract with carry bit: a-b-C type and a+not(b)+C.

a-b-C type:

When borrow, it is set as 1. When no borrow, set 0.

a+not(b)+C type:

When borrow, it is set as 0. When no borrow, set 1. In fact, this type of substraction calculation is exactly addition calculation. Here must remember "not(b)+1" is the complement of "b".

References:

[1] Carry flag, http://en.wikipedia.org/wiki/Carry_flag

[2] Status flags, http://en.wikipedia.org/wiki/Status_register

TQ2440 linux 移植

这里使用的都是天嵌公司提供的资源来移植的。

内核编译：

首先编译系统内核，这个可以按照《linux移植之step by step》的附录5来一步步操作。当然我已经将配置好的config文件保存起来了，即/opt/EmbedSky/linux-2.6.30.4/arch/arm/configs/s3c2410_defconfig。（这里一定要注意一点，配置完内核后要保存配置信息，同时还要保存为另一个配置文件名称.config，否则系统会按默认的配置进行内核编译。），执行make和make zImage来编译内核。

编译内核时，要使用root用户，否则会出现各种莫名其妙的错误。

根文件系统编译：

接着创建根文件系统，首先创建一系列目录以及目录中相关的文件，然后使用命令mkyaffs2image命令来将整个文件夹制作成根文件系统镜像。

以后，每次编译完新的程序就可以放到该文件系统目录中，然后再编译整个目录，再下载到板子中。

如果每次都将根文件系统下载到flash中，不但损伤flash，同时也会浪费时间(写入flash的时间要比写入SDRAM的时间要长)。所以最好可以把文件系统直接下载到SDRAM来进行程序调试。基本上有两种方法可以提供：

• 使用u-boot中的tftp指令来将内核或者根文件系统下载到SDRAM。
• 使用openjtag，用软件openocd来直接将内核和文件系统下载到指定位置。

用TFTP协议来下载文件(ubuntu10.10):

1, 首先下载tftp软件包 - tftp(客户端)， tftpd(服务器)， xinetd(网络请求的守护进程, 当xinetd接到连接时，它能够确定连接所需的程序，启动相应的进程，并把socket交给它)。

sudo apt-get install xinetd tftpd tftp

2, 创建tftp配置文件/etc/xinetd.d/tftp。

sudo vi /etc/xinetd.d/tftp

配置如下:

service tftp

{

           protocol = udp

           port = 69

           socket_type = dgram

           wait = yes

           user = nobody

           server = /usr/sbin/in.tftpd

           server_args = /tftpboot

           disable = no

}

3, 产生服务器目录/tftpboot:

sudo mkdir /tftpboot

sudo chmod -R 777 /tftpboot

sudo chown -R nobody /tftpboot

4, 重新启动xinetd服务:

sudo /etc/init.d/xinetd stop

sudo /etc/init.d/xinetd start

5, 测试tftp server是否设置好:

tftp 192.168.0.123 （服务器ip地址）

tftp>  get zImage

tftp>  quit

6, 更改有线网卡的ip地址。

sudo ifconfig eth0 192.168.0.123  (这里ip地址对应于板子上uboot的设置，注意eth0一定是你连接的那个网卡)

7, 你也可以查看和设置板子上uboot的参数

printenv   (查看uboot的参数，包括serverip和ipaddr等)

setenv serverip 192.168.0.123  (更改uboot的参数，同理可以更改ipaddr等)

saveenv     (更改完参数后一定要记住保存，否则重启后参数更新)

6, 完毕，现在就可以利用网络来下载内核及文件系统

uboot>  tftp 30000000 zImage  (S3C2440的SDRAM区间从30000000开始)

uboot>  tftp 30008000 root.bin

使用tftp的注意事项:

纠结了一天，始终连接不上的原因是选错网卡了，现在的笔记本一般都既有兼有有线网卡和无线网卡，由于我们要使用有线网卡，所以一定要注意选对网卡，然后再更改ip地址。

下一步要研究一下如何可以在板子上的linux系统通过网络mount主机(host)的目录，这样有助于调试的方便。

引用:

[1] Installing and Testing TFTP Server in Ubuntu/Debian, http://mohammadthalif.wordpress.com/2010/03/05/installing-and-testing-tftpd-in-ubuntudebian/

How to compile drivers into linux kernel

The working principle of kernel compiling:

There are files need to change in the relevant directory - Kconfig and Makefile.

• All these configures and makefiles are based on the great program "make".
• When we enter "make menuconfig", the "make" program will build a visual configure interface according to Kconfig files existing in different directories.
• After finish configuring the system, "make" will produce a configure file ".config" which contains the information of your configure options.
• Then compile the system using "make", gcc will compile the system according to the Makefiles which will choose to compile drivers as kernel, or module, or not according to the configure file ".config".

The format of Kconfig file:

menu "Name of menu"

config SYMBOL1                                      

           tristate (or bool) "The function of this option"

           default M (or Y)

           ---help---

           Here we can illustrate what is the configure option used for

config SYMBOL2                                      

           tristate (or bool) "The function of this option"

           default M (or Y)

           ---help---

           Here we can illustrate what is the configure option used for

config SYMBOL3                                      

           tristate (or bool) "The function of this option"

           default M (or Y)

           ---help---

           Here we can illustrate what is the configure option used for

...

endmenu

"config SYMBOL" here config is a keyword which illustrates the following symbol is a configure option, and symbol is used to identity the configure which will be changed into CONFIG_SYMBOL and be valued as Y, M, or empty in .config file. Then further, Makefile can use these CONFIG_SYMBOLs to choose to compile drivers as kernel, module or not compile.

There is another useful keyword of Kconfig - source.

This keyword is used in the parent directory which usually is used to enter the Kconfig file of subdirectory.

Its usage is shown below:

menu "Name of the menu"

source "currentdirectoty/subdirectory1/Kconfig"

source "currentdirectoty/subdirectory2/Kconfig"

source "currentdirectoty/subdirectory3/Kconfig"

source "currentdirectoty/subdirectory4/Kconfig"

source "currentdirectoty/subdirectory5/Kconfig"

...

endmenu

The root of Kconfig structure:

Kconfig files make a configure tree of kernel. So there must be a root which can be used as the entry of kernel configure system. You must modify the root Kconfig file to add driver or modify driver, otherwise it cannot display when you do "make menuconfig". So the root Kconfig file is : /arch/xxx(processor architecture)/Kconfig. This is the entry (main menu) of  the whole configure interface of kernel.

How to write Makefile according to Kconfig:

After writing Kconfig file, we need to write Makefile to response to Kconfig.

We already knew that the Makefile need to use the configure file .config to compile the source code.

So we need to use the SYMBOLs we talked above to choose to compile drivers as kernel (Y), or module (M) or not compile (empty).

It is written as following:

obj - $(CONFIG_SYMBOL1) (tab tab ...) += xxxx1.o  

obj - $(CONFIG_SYMBOL2) (tab tab ...) += xxxx2.o  

obj - $(CONFIG_SYMBOL3) (tab tab ...) += xxxx3.o  

After change the Makefile in the current directory, you have to modify the Makefile in the parent directory to add the path of your new drivers, otherwise when compiling the kernel, it cannot find your new driver. This sentence should be like following:

obj - $(CONFIG_SYMBOL1) (tab tab ...) += mydrivers/ 

obj - $(CONFIG_SYMBOL2) (tab tab ...) += mydrivers/

obj - $(CONFIG_SYMBOL3) (tab tab ...) += mydrivers/  

References:

[1] Linux 内核源码树学习: Kconfig 和 Makefile http://www.linuxidc.com/Linux/2009-11/23091.htm

[2] Linux source code.

[3] Linux设备驱动开发详解, P61.

The differences between array and pointer

In fact, the name of array and pointer are totally different stuff. 

The name of array represents a certain kind of data structure of array.

For example, when you declare an array with "char amessage[]= "now is the time" ". Then declare a pointer with "char *pmessage="now is the time"".

Then array amessage is built as a data structure which contains the whole copy of string "now is the time". However pointer pmessage just contains the address of the string literal.

So the size of amessage is 16, however the size of pmessage is only 4.

But why sometimes the name of array can be used as pointer?

This is because of the compiler. When the compiler finds that the name of array appears in the right of a statement without index, the compiler will make it act as pointer - something like &amessage. 

But whatever the name of array is not pointer after all, so it cannot appear in the left of statement.

Compile the following code, you can also get the conclusion we talked above.

#include <string.h>

#include <iostream.h>

int main (int argc, char* argv[])

{

     char str[10];

     char *pStr = str;

     cout << sizeof(str) <<endl;

     cout << sizeof(pStr) <<endl;

     return 0;

}

However, when the name of array appears as formal parameter in subfunctions, it becomes a pointer, because we are not supposed to declare a large formal parameter, or a parameter which is fixed with some value. So from these points, pointer is the best choice.

Summary:

• The name of array is not pointer, it is just a data structure.
• The name of array cannot appear in the left of statement.
• When the the name of array appears as formal parameter in subfunctions, it becomes pointer.

References: 

[1] 数组名不等于指针 http://blog.csdn.net/rjzou2006/article/details/2292698

[2] 在C语言中"指针和数组等价"到底是什么意思? http://c-faq-chn.sourceforge.net/ccfaq/node78.html

[3] C: differences between pointer and array http://stackoverflow.com/questions/1335786/c-differences-between-pointer-and-array

Software Requirement Specification

Software Requirement Specification

What is SRS and its usages?

SRS (Software Requirements Specification) is used to describe the behavior of a system. SRS should include functional requirements and non-functional requirements. Funcational requirements tell you about what the software is used for and how it interact with users. Non-functional requirements tells how good the software should perform. Basically, it is some constrains imposed on the design and implementation (Remember every system has constraints, otherwise you will be able to do anything you want, that is unreasonable. So when you try to do something in life, find the constraints. This is not just about software development, it is pratical for everything). Take game development as an example. Functional requirement should think about what kind game it is, how to play it, how the players operate the console, etc. And non-functional requirements should consider how much footprint will be used, how the performance, the reliability (it should not go to crash frequently during playing), etc.

So SRS can be used as the guidance during the whole development period. It can be used as the basis of testing.

How to form a good requirements statement?

A good requirement should contain: Capabilities, Conditions, Constraints. 

However in the beginning, maybe you did not have an overall understanding of the system, so you can just state some capabilities, but as the progress carries on, you must complete the statements with conditions and constraints, otherwise the program cannot proceed.

• Here ca pabilities are used to describe what the embedded system shall or must do.
• Conditions are measurable qualitative or quantitative attributes and characteristics associated with the capability.One thing you need to know is when you implement one function. It must be associated with numbers or options. For example, when you design a blockbreaker game, you cannot just say I need to design blocks, panel and ball. You should say how many and how big blocks are, and the size of panel and ball, etc. Otherwise it is unrealizable.
• Constraints is some limitations imposed on the requirements by circumstances, force or compulsion. It is something makes you design software in a limited environment, where you cannot do whatever you want. You should always be aware of these constraints when you design. For example, when you design a blockbreaker game, you should say these blocks should exist in a limited size of screen.

How to obtain requirements?

1, Getting Inputs

Get inputs from customers, environment and technical community.

Cusomers can provide:

• Concept of operations/system concepts. Here we can know how the user operate the machine.
• Marketing specifications
• Request for proposals
• External interfaces

• • Computer to computer
  • User to computer
  • Computer to sensors and actuators
  • Computer to data links
• Feedback

Enviroment camn provide:

• Political influence. For example, some countries may not allow some services, or they may require that the language on device have to be their local language.
• Market influence
• • Market needs
  • Distribution and accessibility
  • Competition
• Standards and Technical policies influence
• Cultural influence. For example, you design a game in Iran, when players win, you put a THUMB UP picture in the end, they will kick your ass.
• Organizational influence

Technical community can provide technical feedback from various perspectives:

• Desgin
• Implementation
• Integration
• Test
• Manufacturing
• Deployment
• Operations
• Maintenance

2, Identify and Analyze Requirements

Then we need to identify and analyze the requirements from inputs. Here you can discuss with customers, do surveys, observations, reverse engineering, simulations or prototyping, etc to identify and analyze the requirements. The goal of requirements analysis is:

• Identify implicit requirements from the inputs and derive further requirements.
• Identify mis-match or inconsistencies between requirements.
• Identify missing requirements for further discussions with customers.
• Identify missing requirements for further discussions with customers.
• Identify workflow, patterns of behavior, attributes, system modes, data flow or capacity.

Techniques to analyze requirements:

- Scenario Analysis (Try to imagine scenario how users will use the system, and how the system response to users):

• Very effective in systems involving some form of external stimuli (system interacting with some users)
• Can be expressed in terms of use cases, sequence diagrams, flow charts, activity diagram, statecharts.
• Starts with customers describing typical use scenarios.
• Proceeds to consider different users or actors involved in the use of the system.
• Exception scenarios are conceptualized, using various entry points in the typical use scenarios and asking "What if".

- Functional Analysis (analyze the functions the system contains, and try to analyze each function):

• Very effective in analyzeing the inernals of the system
• Very useful for autonomous and embedded control systems analysis
• Often represented using function diagrams, data flow diagrams, control flow diagrams and even entity relationship diagrams
• Starts with the interfaces and identify functions
• Trace the data flows and event flows, to understand how data and event flows are handled

In most cases, scenario analysis and functional analysis are combined together to do requirements analysis. Scenario analysis is used when we design interfaces which need to interact with users, because here designers and customers can imagine how the user will operate it. And functional analysis is good for analyzing the internal functions of system: how many modules the system is composed of, how the data flow is passed. Functional analysis is for designers' perspectives. There are functional analysis examples from answering machine:

   

Function diagram

Data flow diagram

Event flow diagram

3, Organize and Review Requirements

When you finish all the requirement analysis, then organize well the requirements and make sure the requirements are:

• Requirements are well-organized
• Well formed. Follow the rules of capability, condition and constraints.
• Readable.
• • Use a data dictionary to explain unique terminologies
  • Write with the customers or reviewers in mind
• Testable. Keep testing of the software in mind, to make sure the test team can understand the testing tasks clearly, which can help the test team to test the system. Don't put them in a terrible situation where they think what the hell should I do holding the requirement specification document.

References: 

[1] List of system quality attributes, http://en.wikipedia.org/wiki/List_of_system_quality_attributes

[2] IEEE Recommended Practice for Software Requirements Specifications

Programming tricks

1. Swap the contents of two registers.
   XOR R0, R1
   XOR R1, R0
   XOR R0, R1
   Remember "1" in result means differences, while "0" means same. However when the number apears in operation of XOR, "1" means reverse and "0" means keep.
2. To judge if two numbers are equal, we can also use XOR.
   XOR R0, R1
   If the result is 0, then R0 and R1 are equal. Otherwise they are not.
3. Struct type allows the specification of elements of a structure into a fixed number of bits.
   struct fivebits
   {
       unsigned int flag : 1; // act as switch, on (1) or off (0)
       signed int num   : 4; // number ranges from -8...7
                               : 3; // empty 3 bits used to align to 8bits, this is necessary for manipulation
   }