by ·0 Comments

Copied from Wikipedia:

An intrinsic function is a function available for use in a given programming language whose implementation is handled specially by the compiler. Typically, it substitutes a sequence of automatically generated instructions for the original function call, similar to an inline function. Unlike an inline function though, the compiler has an intimate knowledge of the intrinsic function and can therefore better integrate it and optimize it for the situation. This is also called builtin function in many languages.

A code snippet is written to check the code generation when intrinsic is enabled or not:

Generated assembly:

Only printf() is in code. No abs() nor memcpy(). Since they are intrinsic, as listed here in gcc’s online document.

Intrinsic can be explicitly disabled. For instance, CRT intrinsic must be disabled for kernel development. Add -fno-builtin flag to gcc, or remove /Oi switch in MSVC. Only paste the generated code in gcc case here:

There _are_ abs() and memcpy() now. General MSVC intrinsic can be found here.

Intrinsic is easier than inline assembly. It is used to increase performance in most cases. Both gcc and MSVC provide intrinsic support for Intel’s MMX, SSE and SSE2 instrument set. Code snippet to use MMX:

Assembly looks like:

You see MMX registers and instruments this time. -mmmx flag is required to build for gcc. MSVC also generate similar code. Reference for these instrument set is available on Intel’s website.

A simple benchmark to use SSE is avalable here.

by ·0 Comments

There was a misleading in my knowledge of a conditional jump: It checks only the result of CMP and TEST instruments. So when it appears after other instruments like ADD or SUB, I can find no clue on how it works.

Actually, a conditional jump checks flags in the EFLAGS control register. From Intel’s manual, vol 1, 3.4.3:

The status flags (bits 0, 2, 4, 6, 7, and 11) of the EFLAGS register indicate the results of arithmetic instructions, such as the ADD, SUB, MUL, and DIV instructions. The status flag functions are:

CF (bit 0) Carry flag: Set if an arithmetic operation generates a carry or a borrow out of the most-significant bit of the result; cleared otherwise. This flag indicates an overflow condition for unsigned-integer arithmetic. It is also used in multiple-precision arithmetic.

PF (bit 2) Parity flag: Set if the least-significant byte of the result contains an even number of 1 bits; cleared otherwise.
AF (bit 4) Adjust flag: Set if an arithmetic operation generates a carry or a borrow out of bit 3 of the result; cleared otherwise. This flag is used in binary-coded decimal (BCD) arithmetic.

ZF (bit 6) Zero flag: Set if the result is zero; cleared otherwise.

SF (bit 7) Sign flag: Set equal to the most-significant bit of the result, which is the sign bit of a signed integer. (0 indicates a positive value and 1 indicates a negative value.)

OF (bit 11) Overflow flag: Set if the integer result is too large a positive number or too small a negative number (excluding the sign-bit) to fit in the destination operand; cleared otherwise. This flag indicates an overflow condition for signed-integer (two’s complement) arithmetic.

And again from vol 2a, section Jcc Jump if Condition is met, more details. I just copy content from here:

Instruction Description signed? Flags short
jump
opcodes		 near
jump
opcodes
JO Jump if overflow OF = 1 70 0F 80
JNO Jump if not overflow OF = 0 71 0F 81
JS Jump if sign SF = 1 78 0F 88
JNS Jump if not sign SF = 0 79 0F 89
JE
JZ		 Jump if equal
Jump if zero		 ZF = 1 74 0F 84
JNE
JNZ		 Jump if not equal
Jump if not zero		 ZF = 0 75 0F 85
JB
JNAE
JC		 Jump if below
Jump if not above or equal
Jump if carry		 unsigned CF = 1 72 0F 82
JNB
JAE
JNC		 Jump if not below
Jump if above or equal
Jump if not carry		 unsigned CF = 0 73 0F 83
JBE
JNA		 Jump if below or equal
Jump if not above		 unsigned CF = 1 or ZF = 1 76 0F 86
JA
JNBE		 Jump if above
Jump if not below or equal		 unsigned CF = 0 and ZF = 0 77 0F 87
JL
JNGE		 Jump if less
Jump if not greater or equal		 signed SF <> OF 7C 0F 8C
JGE
JNL		 Jump if greater or equal
Jump if not less		 signed SF = OF 7D 0F 8D
JLE
JNG		 Jump if less or equal
Jump if not greater		 signed ZF = 1 or SF <> OF 7E 0F 8E
JG
JNLE		 Jump if greater
Jump if not less or equal		 signed ZF = 0 and SF = OF 7F 0F 8F
JP
JPE		 Jump if parity
Jump if parity even		 PF = 1 7A 0F 8A
JNP
JPO		 Jump if not parity
Jump if parity odd		 PF = 0 7B 0F 8B
JCXZ
JECXZ		 Jump if %CX register is 0
Jump if %ECX register is 0		 %CX = 0
%ECX = 0		 E3 E3

There are signed and unsigned versions when comparing: JA Vs JG, JB Vs JL etc.. Let’s take JA and JG to explain the difference. For JA, it’s clear that it requires CF=0(no borrow bit) and ZF=0(not equal). For JG, when two operands are both positive or negative, it requires ZF=0 and SF=OF=0. When two operands have different signs, it requires ZF=0 and the first operand is positive, thus requires SF=OF=1.

Note, the following 2 lines(AT&T syntax) are equivalent. CPU does arithmetic calculation, it does not care about whether it is signed or unsigned. It only set flags. It is we that make the signed or unsigned jump decision.

Last, I’d like to use ndisasm(install nasm package to get it) to illustrate how jump instruments are encoded, including short jump, near jump and far jump:

by ·0 Comments

Continue with Updating Kernel in Lucid, I want to decrease overview build time this time. My benchmark is run in Ubuntu 10.04 installed in Virtualbox. My CPU is i5-2540M at 2.6GHz.

I’m learning kernel code these days. A minimal kernel will save a lot of build time. As you see, it took 64min to build 2772 modules when running oldconfig target:

Build Time Build Modules Package Size
oldconfig 64min 2772 33MB
localmodconfig 16min 244 7MB
localmodconfig + ccache 1st time 19min 244 7MB
localmodconfig + ccache 2nd time 7min 244 7MB

Fortunately, a new build target localmodconfig was added in kernel 2.6.32 that just helps:

It runs “lsmod” to find all the modules loaded on the current running system. It will read all the Makefiles to map which CONFIG enables a module. It will read the Kconfig files to find the dependencies and selects that may be needed to support a CONFIG. Finally, it reads the .config file and removes any module “=m” that is not needed to enable the currently loaded modules. With this tool, you can strip a distro .config of all the unuseful drivers that are not needed in our machine, and it will take much less time to build the kernel.

The build time was dramatically decreased to 16min to build only 244 modules. It could still boot my VM to desktop, and everything was working fine. However, it failed to mount an *.iso file, since the module was not in lsmod when building I think. To use localmodconfig target, run:

It may end up with errors. Please ignore, a new .config file is already generated. Then remember to turn off the CONFIG_DEBUG_KERNEL option in the .config file, as mentioned in my previous article.

Then ccache is used. I downloaded the source code and built myself, since the 3.x version seems to be faster than 2.4.x version:

Default prefix(/usr/local) is used here. Last 2 lines created symbolic links(named as the compiler) to ccache, to let ccache masquerade as the compiler. This is suggested in ccache’s man page.

So why bother a compiler cache? The makefile doesn’t work?

If you ever run “make clean; make” then you can probably benefit from ccache. It is very common for developers to do a clean build of a project for a whole host of reasons, and this throws away all the information from your previous compiles. By using ccache you can get exactly the same effect as “make clean; make” but much faster. Compiler output is kept in $HOME/.ccache, by default.

The first run creates the cache, and the second benefits from the cache. That’s it.

To display ccache statistics, run:

by ·0 Comments

MSVC’s inline assembly is easier to use, as compared to gcc’s version. It is easier to write right code than wrong one, I think. Still a simple add function is used to illustrate:

The corresponding inline version:

__asm keyword is used to specify a inline assembly block. From MSDN, there is another asm keyword which is not recommended:

Visual C++ support for the Standard C++ asm keyword is limited to the fact that the compiler will not generate an error on the keyword. However, an asm block will not generate any meaningful code. Use __asm instead of asm.

Symbols in C/C++ code can be used directly in inline assembly. This is much more convenient than gcc. And it is also not necessary to load parameters into registers before usage as in gcc. MSVC does the job right even in optimization case.

NOTE: Inline assembly is not supported on the Itanium and x64 processors.

Let’s see the generated code:

Output:

Function parameters are located in [ebp+12] and [ebp+8] as referred by symbol a and b. Then, what happened if registers other than scratch registers are specified?

Output assembly code:

As you see, MSVC automatically preserves ebx for us. From MSDN:

When using __asm to write assembly language in C/C++ functions, you don’t need to preserve the EAX, EBX, ECX, EDX, ESI, or EDI registers.

Let’s see the case when stdcall calling convention is used:

Output:

In stdcall, stack is cleaned up by callee. So, there’s a ret 8 before return. And the function name is mangled to _add4@8.

MSVC also supports fastcall calling convention, but it causes register conflicts as mentioned on MSDN, and is not recommended. Just test it here, the code happens to work:)

Output:

Function parameters are passed in ecx and edx when using fastcall. But they are saved to stack first. It seems we get no benefit using this calling convention. Maybe MSVC does not implement it well. The function name is mangled to @add5@8.

Last, we can tell MSVC that we want to write our own prolog/epilog code sequences using __declspec(naked) directive:

Output:

Normal prolog/epilog is used here. MSVC does not generate duplicate these code when using __declspec(naked) directive.

by ·0 Comments

Inline assembly is used in Linux kernel to optimize performance or access hardware. So I decided to check it first. Before digging deeper, you may wanna read the GCC Inline Assembly HOWTO to get a general understanding. In C, a simple add function looks like:

Its inline assembly version may be:

Or simpler:

Here’s its generated code by gcc:

Output:

Our inline assembly is surrounded by #APP and #NO_APP comments. Redundant gcc directives are already removed, the remaining are just function prolog/epilog code. add2() and add3() works fine using default gcc flags. But it is not the case when -O2 optimize flag is passed. From the output of gcc -S -O2(try it yourself), I found these 2 function calls are inlined in their caller, no function call at all. These 2 issues prevent the inline assembly from working: – Depending on %eax to be the return value. But it is silently ignored in -O2. – Depending on 12(%ebp) and 8(%ebp) as parameters of function. But it is not guaranteed that parameters are there in -O2. To solve issue 1, an explicit return should be used:

To solve issue 2, parameters are required to be loaded in registers first:

add5() now works in -O2. The default calling convention is cdecl for gcc. %eax, %ecx and %edx can be used from scratch in a function. It’s the function caller’s duty to preserve these registers. These registers are so-called scratch registers. So what if we specify to use other registers other than these scratch registers, like %esi and %edi?

Again with gcc -S:

It seems that code generation of gcc in default optimize level is not so efficient:) But you should actually noticed that %esi and %edi are pushed onto stack before their usage, and popped out when finishing. These code generation is automatically done by gcc, since you have specified to use %esi(“S”) and %edi(“D”) in input list of the inline assembly. Actually, the code can be simpler by specify %eax as both input and output:

We can tell gcc to use a general register(“r”) available in current context in inline assembly:

And wrong code generation again…:

%eax is moved to %eax? gcc selected %eax and %edx as general registers to use.  The code accidentally does the right job, but it is still a potential pitfall. Clobber list can be used to avoid this:

As commented inline: The clobber list tells gcc which registers(or memory) are changed by the asm, but not listed as an output. Now gcc does not use %eax as a candidate of general registers any more. gcc can also generate code to preserve(push onto stack) registers in clobber list if necessary.