13 Jul 2017, 00:00

Layout of a stack frame in x86_64

Stack frame in x86_64

Just for a memo:

                         +--------------+
                         |              |
                    +    |              |
                    |    +--------------+
                    |    |              |
                    |    |   arg(N-1)   |  starts from 7'th argument for x86_64
                    |    |              |
                    |    +--------------+
                    |    |              |
                    |    |     argN     |
                    |    |              |
                    |    +--------------+
                    |    |              |
                    |    |Return address|  %rbp + 8
Stack grows down    |    |              |
                    |    +--------------+
                    |    |              |
                    |    |     %rbp     |  Frame base pointer
                    |    |              |
                    |    +--------------+
                    |    |              |
                    |    |  local var1  |  %rbp - 8
                    |    |              |
                    |    +--------------+
                    |    |              |
                    |    | local ^ar 2  | <-- %rsp
                    |    |              |
                    v    +--------------+
                         |              |
                         |              |
                         +--------------+

05 Jan 2016, 00:00

How does GNU GRUB work

This blog post is closely related with my interest in low-level stuff. As you already may know, I’ve started to be interested in such things like: How N works, where the N is something like - what does occur when we turn on the computer, pressing key on keyboard, how does an operating system load a program and many many more. I have found answers on some of my questions. You can look on the set if blog posts which are decribe some aspects of the assembly programming or the linux-insides book which describes internals of the Linux kernel.

Yes. This answered on some of my questions, but not at all. Lately, besides the Linux kernel, I’ve also learned internals of the GNU GRUB. In the previous year I’ve got many thank you words from different people for the linux-insides. Seems that low-level stuff is interesting not only for me and I decided to write this blog post which will cover some parts of the GNU GRUB and we will see answer on the question which is in the title of this post - How GNU GRUB works. Hope, that it will be useful for somebody.

If you use Linux, you likely know about GNU GRUB. But just in case, wikipedia says that:

GNU GRUB (short for GNU GRand Unified Bootloader) is a boot loader package from the GNU Project

So, the GNU GRUB is a bootloader. Main point of a bootloader is to load an operating system kernel and to transfer control to it. GNU GRUB has many features like support of different types of executable file formats, dynamic configuration, graphical menu interface, support for different types of file systems and etc.

So the point of the bootloader is clear - to load an operating system kernel. In this post we will see how the GNU GRUB loads the Linux kernel. But before this let’s take a little look on architecture of the GNU GRUB. Even if you are newbie Linux user, you can guess that all boot related data is placed in the /boot directory. For me it looks like:

boot-dir

This directory contains two initrd images, the Linux kernel image and the grub directory which contains GNU GRUB related data:

boot-grub-dir

Directory with fonts, GNU GRUB configuration file, themes, locales, the grubenv file that contains GNU GRUB environment variables which are can be used in runtime and the i386-pc directory which contains GNU GRUB images and modules. Content of the i386-pc directory is the most interesting for us. Yes the /boot/grub directory contains many other interesting directories/files besides the /boot/grub directory, but this post will not cover topics like how to make GNU GRUB menu beautiful, readable and etc. If we will open the /boot/grub/i386-pc directory, we will find three types of files there:

  • *.lst files - contain lists of available options depends on file. For example, the /boot/grub/i386-pc/video.lst contains list of available video modes or the /boot/grub/i386-pc/fs.list file contains information about supported file systems;
  • *.mod files - 32-bit ELF files which provide additional functional for GNU GRUB. For example, the /boot/grub/i386-pc/acpi.mod adds support of the Advanced Configuration and Power Interface which is used to perform various power-related functions or /boot/grub/i386-pc/ext2.mod provides support for ext2 file system;
  • *.img files - only two files: /boot/grub/i386-pc/boot.img and /boot/grub/i386-pc/core.img. We need to look closer on this file.

The first boot.img file is the entry of the bootloader on a PC BIOS system. The content of this file is written to the first sector of the disk or in the Master boot record. The main point of the boot.img is to load first sector (512 bytes) of the core.img which will continue to do main job of the bootloader. As boot.img is in the master boot record, it must meet several conditions. First of all its size must be 512-bytes and the last two bytes must be 0xAA55. We can see that boot.img is 512 bytes size file:

boot.img

and contains two magic bytes in the end:

~$ hexdump -s 510 /boot/grub/i386-pc/boot.img
00001fe aa55

Besides two magic bytes, the Master boot record must contain bootstrap code which will load second stage of the bootloader which can be much more than 512 bytes and partition table with four 16-bytes partition entries. Generall structure of the MBR must be like this:

0   +--------------------+
    |                    |
    |   Bootstrap code   |
446 |                    |
    |                    |
    |  Partition entry 1 |
    |  Partition entry 2 |
    |  Partition entry 3 |
    |  Partition entry 4 |
510 |        0x55        |
511 |        0xaa        |
512 +--------------------+

The second core.img file does the main job for us. It contains file system drivers, so it can load configuration from the /boot/grub/grub.cfg file and modules. The main point of the core.img is to transfer control to the last - second stage of the grub. At this moment, the GNU GRUB will have loaded modules, so it will know everything about operating system kernels which are needed to load. It draws menu, reacts on selection and etc.

Before we will start to dive into low-level source code of the GNU GRUB. We need to understand how all of this data occurs on a disk of computer. Besides bootloader functions, the GNU GRUB provides a rich set of utils:

grub-utils

And one of this util may help us to install GNU GRUB on a computer. The name of this util is - grub-install. As we can read in the grub-instal manual page. The grub-install util:

grub-install - install GRUB on your drive

We just saw a little about GNU GRUB related files and now is time to see how the grub-install installs master boot record and this files. Let’s look on the source code if the grub-install.

The grub-install util

Implementation of the GNU GRUB utils is located in the utils directory. In our case, implementation of the grub-install utils is in the grub-install.c. If we will look on its main function, we will see that it starts from the call of the grub_util_host_init function which defined in the grub-core/osdep/basic/init.c source code file and produces standard stuff for a C programs, like the call of the set_program_name, setting locale and etc.

After the first inital initialization, we can see the call of the arg_parse function which as we may understand from the name - parses command line arguments of the grub-install util. We will not dive into details of implementation of the argp_parse function in ths post. I don’t know how about you, but now, its interesting for me only low-level stuff in the GRUB. At the next step as we parsed command line arguments of the grub-install util, we start to check these arguments and do something depend on their values. First of all, we check the -v or --verbose flag which allows us to see verbose output of the grub-instal work. If this flag is set we set debug=all environment variable of GRUB with the call of the grub_env_set function:

  if (verbosity > 1)
    grub_env_set ("debug", "all");

GRUB stores its environment variables in the hashtable which is represented by the following structure:

struct grub_env_context
{
  struct grub_env_var *vars[HASHSZ];
  struct grub_env_context *prev;
};

The implementation of the grub_env_set function is simple. It just calculates index in the grub_env_context hashtable and stores a given variable in it. After this we can see the call of the:

grub_util_load_config (&config);

function. This function just fills the grub_util_config structure from the GRUB configuration file (located in the /etc/default/grub). This structure consists from two fields. Both fields are depends on the following environment variables:

  • GRUB_ENABLE_CRYPTODISK - allows to install GRUB on the encrypted disk.
  • GRUB_DISTRIBUTOR - provides string which is associated with the distributor. For example, for me now it is:
$ cat /etc/default/grub | grep DIST
GRUB_DISTRIBUTOR="Arch"

After this we check the GRUB_DISTRIBUTOR value and if we’ve found it in the GRUB configuration file we save it in the bootloader_id variable. In other way the bootloader_id will contain "grub" string by default. At the next step we need to check current platform and exit in a failure case. The grub-install util does it with the call of the get_default_platform function. This function checks gcc directives and returns our platform:

static const char *
get_default_platform (void)
{
#ifdef __powerpc__
   return "powerpc-ieee1275";
   ...
   ...
   ...
#elif defined (__amd64__) || defined (__x86_64__) || defined (__i386__)
   return grub_install_get_default_x86_platform ();
#else
   return NULL;
#endif
}

The grub_install_get_default_x86_platform () function returns x86_64-efi, i386-efi or just i386-pc on x86_64 platform. So, now we know target machine and now we need to get the path of directory where grub-install util will install its modules. In our case it will be /lib/grub/i386-pc and the grub_install_source_directory variable will contain this path. Besides the name of the target platform, we need to get information about this platform. The grub-install util will do it with the call of the grub_install_get_target() function. The main point of this function is to return item from the platforms array:

static struct
{
  const char *cpu;
  const char *platform;
} platforms[GRUB_INSTALL_PLATFORM_MAX] =
  {
    [GRUB_INSTALL_PLATFORM_I386_PC] =          { "i386",    "pc"        },
    [GRUB_INSTALL_PLATFORM_I386_EFI] =         { "i386",    "efi"       },
    [GRUB_INSTALL_PLATFORM_I386_QEMU] =        { "i386",    "qemu"      },
	...
	...
	...
}

and print information about it:

{
    char *platname = grub_install_get_platform_name (platform);
    fprintf (stderr, _("Installing for %s platform.\n"), platname);
    free (platname);
}

At the next step we need to select GRUB’s disk module depends on the platform name. In our case it will be biosdisk module:

switch (platform)
{
    case GRUB_INSTALL_PLATFORM_I386_PC:
      if (!disk_module)
	disk_module = xstrdup ("biosdisk");
      break;
	  ...
	  ...
}

The next step after we have selected disk module is initialization of all modules:

  grub_init_all ();
  grub_gcry_init_all ();
  grub_hostfs_init ();
  grub_host_init ();

The source code of GRUB modules is located in different parts of GRUB source code, but each module contains definition of the GRUB_MOD_INIT and GRUB_MOD_FINI macros which make all initialization stuff. After all modules are initialized we are copying/installing to the /boot/grub directory all GRUB files (modules, locales, themes and etc.) to the source directory by the call of the:

  grub_install_copy_files (grub_install_source_directory,
			   grubdir, platform);

function. After all of this manipulations, the grub-install util executes many different thing. It creates the /boot/grub/envblk file which is the GRUB environment block that is stores GRUB’s environment variables. You can use the grub-editevn --list util to lust the GRUB environment variables. At the next step, the grub-install checks the given device, tries to understand type of files system on a given device and loads module for the certain file system type. It loads the module which provides functional for a disk reading. You can remember that it is the biosdisk for us. But the main point of the grub-install utils is to install MBR, the core.img and the kernel.img. The most interesting part for us is the call of the:

if (install_bootsector)
	grub_util_bios_setup (platdir, "boot.img", "core.img",
                          install_drive, force,
				          fs_probe, allow_floppy, add_rs_codes);

function. The grub_util_bios_setup function defined in the util/setup.c source code file and its main point is to setup MBR. This function takes eight arguments:

  • platdir - platform dependend directory wich contains GRUB modules, image and etc. (For example - /lib/grub/i386-pc);
  • GRUB boot image;
  • GRUB core image;
  • install_drive - name of the device where to install GRUB;
  • force - install or not if any problems are presented;
  • fs_probe - allows GRUB to skip file system probes for the given device;
  • allow_floppy - makes a drive bootable as floppy;
  • add_rs_codes - shows apply or not reed-solomon codes during core-img embedding.

The grub_util_bios_setup function reads the boot.img and the core.img from the disk, sets the root device, copies partition table (will see more about it later), reads partition table, checks errors and writes the core.img and the boot.img:

for (i = 0; i < nsec; i++)
	grub_disk_write (dest_dev->disk, sectors[i], 0,
		             GRUB_DISK_SECTOR_SIZE,
		             core_img + i * GRUB_DISK_SECTOR_SIZE);
...
...
...
if (grub_disk_write (dest_dev->disk, BOOT_SECTOR,
                     0, GRUB_DISK_SECTOR_SIZE, boot_img))
    grub_util_error ("%s", grub_errmsg);

That’s all. Now we have installed master boot record and other boot-related GRUB parts on our machine.

Booting process

The booting process starts when BIOS reads first sector (first 512 bytes) from a disk and loads it into memory by 0x0000:0x7c000 address. The GNU GRUB MBR code is implemented in the grub-core/boot/i386/pc/boot.S assembly source code file. As I already wrote above, the main point of the master boot record bootstrap code is to load second second sector from disk and control transfer to it. Besides this, bootstrap code does not do almost anything, because as you remember it is very small, only 512 bytes size. Let’s look on the implementation of the bootstrap code.

In the beginning of the grub-core/boot/i386/pc/boot.S source code file we can see definition of the global labels and the jump to the local label:

.globl _start, start;
_start:
start:
	jmp	LOCAL(after_BPB)
	nop

The LOCAL macro defined in the include/grub/symbol.h header file and expands to the concatenation of the L_ and given symbol:

#define LOCAL(sym)	L_ ## sym

in our case it will expand to the L_after_BPB label. This label represents the BIOS parameter block which contains information about physycal layout of a disk. At the start of the L_after_BPB label we disable interrupts with the cli instruction to prevent erasing of the dl register which stores number of hard drive from which we have loaded. After this we test value of the dl register and set to 0x80 (first hard drive in the system) if buggy BIOS did not set it:

	cli
    testb   $0x80, %dl
    jz      2f
2:
    movb    $0x80, %dl

At the next step we set data segment and stack segment registers to the known value - it is zero in our case, setup stack pointer to the top of the stack segment (0x2000) and enable interrupts again, because from this point we are safe now:

	xorw	%ax, %ax
	movw	%ax, %ds
	movw	%ax, %ss

	movw	$GRUB_BOOT_MACHINE_STACK_SEG, %sp
	sti		/* we're safe again */

We just made enabled interrupts, so we can print Welcome message to the screen with the MSG macro:

MSG(notification_string)

#define MSG(x)	movw $x, %si; call LOCAL(message)

notification_string:	.asciz "GRUB "

LOCAL(message):
	lodsb			/* loads character from %si to %al */
	cmpb	$0, %al /* check that we are at the end of string */
	jne	1b          /* display character if we are not at the end of string */
	ret

/* %si stores pointer to the notification_string */
/* %bx represents foreground color */
/* %ah number of BIOS service */
/* int $10 - http://www.ctyme.com/intr/rb-0106.htm */
1:  movw	$0x0001, %bx
	movb	$0xe, %ah
	int	$0x10

After we saw the notification_string in our screen, the boot.S starts to load first sector of the core.img file which is represented by the diskboot.img image. To read first sector of the core.img we will use the 0x42 function of the 0x13 interrupt. First of all we need to check support of the LBA in the BIOS by the call of the 0x41 fuction of the 0x13 interrupt:

	movb	$0x41, %ah
	movw	$0x55aa, %bx
	int	$0x13

If the extended read or LBA is supported we start to read first 512 bytes from the core.img. To use extended read we must call the 0x42 function of the 0x13 interrupt with the following set of arguments:

  • %ah register must contain number of the function, 0x42 in our case;
  • %dl register must contain number of the hard drive (starts from 0x80);
  • %ds:%si registers must point to the disk address packet structure.

The disk address packet structure is a data structure which contains data that helps to convert logical block addressing information to physical parameters (Cylinders, Heads, Sectors) of a disk. Before the call of the 0x13 interrupt, we need to fill disk address packet structure. In the our code it starts at the disk_address_packet label. General structure of the disk address packet structure is:

Offset
      +---------------------------------+
  0	  |  Packet size in bytes           |
  1   |  Reserved (must be 0)           |
  2   |  Number of blocks to transfer   |
  3   |  Reserved (must be 0)           |
  4   |  Address of transfer buffer     |
  8   |  Started absolute block number  |
      +---------------------------------+

Address of the disk address packet structure is located in the %si register:

	movw	$disk_address_packet, %si

So, we can set reserved bytes to zero and packet size in our disk_packet_packet with the:

movw	$0x0010, (%si)

packets size will be 16 bytes here. We will read one 512 bytes block:

	xorw	%ax, %ax
	...
	incw	%ax
	movw	%ax, 2(%si)

In the end we need to set block number:

	movl	LOCAL(kernel_sector), %ebx
	movl	%ebx, 8(%si)
	movl	LOCAL(kernel_sector_high), %ebx
	movl	%ebx, 12(%si)

and pointer to the buffer where we will read data from disk:

	movw	$GRUB_BOOT_MACHINE_BUFFER_SEG, 6(%si)

and call the 0x13 interrupt:

	movb	$0x42, %ah
	int	    $0x13

If all is good, the GRUB_BOOT_MACHINE_BUFFER_SEG will point to the beginning of the diskboot.img image in memory. In the of the grub-core/boot/i386/pc/boot.S we relocate our buffer to the GRUB_BOOT_MACHINE_KERNEL_ADDR or address and jump into it:

	jmp	*(LOCAL(kernel_address))

From this moment we have diskboot.img (which is first 512 bytes of the core.img) in the memory. As you may remember, the main point of the diskboot.img is to load rest of the core.img and jump into it. I will not describe this process here, it is pretty easy to understand if you understood previous description of how the boot.S loads diskboot.img. Both of these processes are prety similar. After the diskboot.img will load rest of the core.img it jumps to the GNU GRUB kernel code at grub-core/boot/i386/pc/startup_raw.S source code file. The main point of this code is to make preparation before the C code. You can remember that we need to prepare BSS section for global uninitialized data to run C code and stack. Besides this we execute transition to protected mode. Let’s look on this.

Before the transition to the protected mode, we set segment registers to the known value (zero in our case) and setup stack. After this we call the real_to_prot function which is implemented in the grub-core/kern/i386/realmode.S assembly file. It starts from the loading of Global Descriptor Table with the lgdt instruction:

lgdtl	gdtdesc

Where the gdtdesc contains description of four segments:

  • Code segment;
  • Data segment;
  • Real-mode code segment;
  • Real-mode data segment.

I will not describe what is it GDT and why do we need in it in this post. More about it you can read more about it in the second part of the linux-insides book. After we set the Global Descriptor Table, we turn on protected mode by the setting PE bit in the %cr0 control register:

	movl	%cr0, %eax
	orl	$GRUB_MEMORY_CPU_CR0_PE_ON, %eax
	movl	%eax, %cr0

and jump to the protected mode. Next we clear segment registers, setup protected mode stack and load interrupt descriptor table by the call of the lidtl instruction:

lidt protidt

Interrupt descriptor table contains addresses of the interrupt handlers which are will be called when an interrupt occurs. After all of this manipulations we are in protected mode and may return to the grub-core/boot/i386/pc/startup_raw.S assembly file. In the end, we fill %edx, %edi, %ecx and %eax registers with the number of boot device, addresses of the prot_to_real and real_to_prot function which are helpers for transition between real/protected modes and address of the interrupt descriptor table. Now we can jump to the GNU GRUB kernel:

movl	LOCAL(boot_dev), %edx
movl	$prot_to_real, %edi
movl	$real_to_prot, %ecx
movl	$LOCAL(realidt), %eax
jmp	*%esi

The GNU GRUB kernel for x86 entry is in the grub-core/kern/i386/pc/startup.S assembly file. We are clearing space for the BSS section and call the first function which is written in C programming language:

call EXT_C(grub_main)

For this moment, we’ve been through the low-level part of the GNU GRUB. Of course, it is not the end of the assembly. But for now we have loaded kernel of the GNU GRUB into memory and transfered control to it which is writen mostly in C programming language. Well, let’s continue.

GNU GRUB kernel

The grub_main function defined in the grub-core/kern/main.c source code file and its main purpose is to initialize architecture-specific stuff, to load/parse configuration file and modules, to set some environment variables and to load normal mode. It starts from the call of the grub_machine_init() function which is defined in the grub-core/kern/i386/pc/init.c source code file. The grub_machine_init function initializes console by the call of the:

grub_console_init ();

which just call of:

grub_term_register_output ("console", &grub_console_term_output);
grub_term_register_input ("console", &grub_console_term_input);

functions. These functions takes two parameters: the first is name of a console and the second is pointer to a structure which contains pointer to the actions on a given console, like putchar, cls and etc. In the next time, when print-like function will be called, the GNU GRUB will go through a list of registered consoles and will call their print API. After this the grub_machine_init() function initializes memory regions and intializes Time stamp counter.

After this we return to the grub_main () function which calls the grub_load_config() function. As you can understand from the function’s name, it loads configuration file. The next step is loading of GNU GRUB modules which are represented by the ELF files in the /boot/grub/arch. For example:

grub-mod

After the GNU GRUB kernel will load modules, it sets root and prefix environment variables which are represent root device and prefix of GNU GRUB directory (by default it is /boot/grub), parses configuration file, registers four core command: ls, set, unset and insmod. The last step of execution of the grub_main () function is the grub_load_normal_mode () function. This function defined in the same source code file as the grub_main() function and it tries to load and execute the normal module.

This module represents main module of GNU GRUB which starts to work after all of main low-level preparation. As we can read in the documentation:

In normal mode, commands, filesystem modules, and cryptography modules are automatically loaded, and the full GRUB script parser is available

So, the normal module/command is responsible for the user menu, loading of modules which are defined in the GNU GRUB configuration file with insmod command, handling of user input and transfering control to the real loader of an operating system kernel. Let’s take a closer look on the normal mode.

Normal mode

All code which is related to the normal mode is located in the grub-core/normal directory. As well as all the modules of GNU GRUB, the normal.mod has definition of the GRUB_MOD_INIT and GRUB_MOD_FINI macros which are responsible for a module initialization and finalization. The normal.mod sets a couple of environment variables like target processor, colors, pager and etc. Also it registers a set of command to clear screen, exit from normal mode and etc. In the end of the grub_main() function we could see the call of the:

grub_command_execute ("normal", 0, 0);

function which executes already registred command in the GRUB_MOD_INIT("normal"). It looks:

grub_register_command ("normal", grub_cmd_normal,
			           0, N_("Enter normal mode."));

So, after the last step of the grub_main() function, we will be in the grub_cmd_normal() function. This function enters to the normal mode. Practically it means that it reads configuration file of the GNU GRUB (/boot/grub/grub.cfg) to the grub_menu_t type which represents menu of the GNU GRUB and renders menu. We will skip many parts of this, like how menu renders and how it is represented in the source code of the GNU GRUB, because its not related directly with bootloading. The interesting part for us is that grub_normal_execute() function calls the grub_show_menu() function from the grub-core/normal/menu.c source code file which in turn calls the run_menu function.

The run_menu function provides interruptible sleep until a menu item is selected and returns the selected menu item:

boot_entry = run_menu (menu, nested, &auto_boot);

After the run_menu() function will return index of selected menu item which is represented by the grub_menu_entry structure, we need to execute this menu entry by the call of the grub_menu_execute_entry function. This function takes two parameters:

  • Selected menu entry;
  • auto_boot - shows that nothing was selected and timer is expired.

The grub_menu_execute_entry() function is big enough. It checks that an user selected submenu and renders it in this case, it checks that selected menu entry needs in authentication if we put something like --users user1 to a menu entry and etc. But the greatest interest for us is the following code:

grub_script_execute_new_scope (entry->sourcecode, entry->argc, entry->args);
...
...
...
if (grub_errno == GRUB_ERR_NONE && grub_loader_is_loaded ())
    grub_command_execute ("boot", 0, 0);

The first function takes the body of the selected menu entry, count of arguments and arguments of the GNU GRUB function and tries to execute it. For example if a body of your menu entry will be like this:

linux	/vmlinuz-linux root=UUID=4680b48e-595e-4d03-9115-2db79206e9f9 rw  quiet
echo	'Loading initial ramdisk ...'
initrd	 /initramfs-linux.img

The grub_cmd_linux(), grub_cmd_initrd() and the grub_cmd_echo() functions will be called. After the GNU GRUB will handle script we check an error and that loader is loaded. If both conditions will be good, we execute boot commands which will start to boot a kernel. Now we are stopped on the last step - loading of the Linux kernel.

Ok, finally lets load it

A loader will be loaded during linux command execution in the grub_cmd_linux() function. This function is defined in the grub-core/loader/i386/linux.c source code file. If you will look on the definition of the linux command in your /boot/grub/grub.cfg configuration file, you will see that this command takes path of the Linux kernel image as first argument. So, the grub_cmd_linux() function starts from the check of the number of command line arguments:

if (argc == 0)
{
    grub_error (GRUB_ERR_BAD_ARGUMENT, N_("filename expected"));
	goto fail;
}

If we have no command line arguments, print error and go to fail label. After this we try to open and read the header of the Linux kernel image by the given path in the first command line argument. We are reading the Linux kernel image to the struct linux_kernel_header lh structure which defined in the include/grub/i386/linux.h header file and contains fields which are mapped to the Linux boot protocol v 2.10. After we have read the header of the Linux kernel image, we make some checks for magic number (0xaa55), that setup_sects field is not greater than 64 and etc. As we finished with checks, we need to calculate size of the Linux kernel image and read it full. After this we need to fill/calculate fields which are marked in the Linux boot protocol as write. There fields are:

  • code32_start - entry point of the Linux kernel in protected mode. It is not neccecary, but can be updated for realocation;
  • ramdisk_image - the 32-bit linear address of the initial ramdisk or ramfs;
  • ramdisk_image_size - the size of the initial ramdisk or ramfs;
  • heap_end_ptr - the offset of the end of the setup stack/heap, minus 0x0200;
  • loadflags - bitmask which provides boot related flags.
  • and etc.

So, we are setting the type of the bootloader which is the GNU GRUB (0x72) in our case, offset for the Linux kernel command line, ramdisk_image and ramdisk_size to zero (these fields will be filled in the grub_cmd_initrd()) and other fields:

linux_params.type_of_loader = GRUB_LINUX_BOOT_LOADER_TYPE;
linux_params.cl_magic = GRUB_LINUX_CL_MAGIC;
linux_params.cl_offset = 0x1000;
linux_params.ramdisk_image = 0;
linux_params.ramdisk_size = 0;
linux_params.heap_end_ptr = GRUB_LINUX_HEAP_END_OFFSET;
linux_params.loadflags |= GRUB_LINUX_FLAG_CAN_USE_HEAP;
...
...
...

After we have load the Linux kernel image into memory and have filled Linux kernel header with constructed command line, we check errors and set callback function for the Linux kernel booting. In our case this function will be grub_linux_boot() function:

if (grub_errno == GRUB_ERR_NONE)
{
    grub_loader_set (grub_linux_boot, grub_linux_unload, 0);
    loaded = 1;
}

where the grub_loader_set() function sets:

grub_loader_set (grub_err_t (*boot) (void),
                 grub_err_t (*unload) (void),
		         int flags)
{
    ...
    grub_loader_boot_func = boot;
    ...
}

Now let’s return to the grub_menu_execute_entry() function. We have stopped at the following code there:

grub_script_execute_new_scope (entry->sourcecode, entry->argc, entry->args);

if (grub_errno == GRUB_ERR_NONE && grub_loader_is_loaded ())
    grub_command_execute ("boot", 0, 0);

The first line of code is executed and as we just saw, this function reads the body of a selected menu entry and executes commands from it. After the grub_script_execute_new_scope will be finished, at least linux and initrd commands of GNU GRUB will be executed. This means that the header of the Linux kernel and initrd will be loaded into the memory and fields of the Linux kernel header are parsed and needed fields of it will be calculated and filled. If everything is ok, the if condition after the call of the grub_script_execute_new_scope() function will return true and the boot command will be execute.

The entry of the boot command is the grub_cmd_boot() function which defined in the grub-core/commands/boot.c source code file. Besides a couple of check, the point of the grub_cmd_boot() function is to call boot callback function which is set by the loader:

err = (grub_loader_boot_func) ();

In our case, this callback function was set in the grub_loader_set() function and this function is grub_linux_boot() function which defined in the grub-core/loader/i386/linux.c source code file. The grub_linux_boot() function sets video mode which is depends on values of video parameters from the Linux kernel header, sets the Linux kernel command line offset, fills register and start

state.ebp = state.edi = state.ebx = 0;
state.esi = ctx.real_mode_target;
state.esp = ctx.real_mode_target;
state.eip = ctx.params->code32_start;
return grub_relocator32_boot (relocator, state, 0);

The relocator of the GNU GRUB is big piece of code which prepares all registers to the state which is good for the Linux kernel, prepares environment to the actual processor mode which depends on relocator type (may be in real, protected or long mode), calculates base physical address of the Linux kernel and jumps on it.

From this moment we are in the kernel!

That’s all.

Conclusion

We saw how the GNU GRUB loads the Linux kernel in this post. Of course, it is not fully cover booting process of the Linux kernel and it also does not cover full aspects of the GNU GRUB. We have missed some things like how does GRUB manage filesystem related work, memory management related stuff, styles and appereance of menu and etc. This is not real to cover all of this topics and especially full source code of the such project like the GNU GRUB in one post. But I hope, you’ll like it and you will research other boot related things with yourself.

Questions/Suggestions: Feel free about any questions or suggestions by pinging me at twitter @0xAX, adding an issue or just drop me an email.

Please note that English is not my first language and I am really sorry for any inconvenience. If you found any mistakes please send me PR to 0xax.github.com or just drop me an email

01 Dec 2014, 00:00

Say hello to x86_64 Assembly [part 8]

It is eight and final part of Say hello to x86_64 Assembly and here we will take a look on how to work with non-integer numbers in assembler. There are a couple of ways how to work with floating point data:

  • fpu
  • sse

First of all let’s look how floating point number stored in memory. There are three floating point data types:

  • single-precision
  • double-precision
  • double-extended precision

As Intel’s 64-ia-32-architecture-software-developer-vol-1-manual described:

The data formats for these data types correspond directly to formats specified in the IEEE Standard 754 for Binary Floating-Point Arithmetic.

Single-precision floating-point float point data presented in memory:

  • sign - 1 bit
  • exponent - 8 bits
  • mantissa - 23 bits

So for example if we have following number:

| sign  | exponent | mantissa
|-------|----------|-------------------------
| 0     | 00001111 | 110000000000000000000000

Exponent is either an 8 bit signed integer from −128 to 127 or an 8 bit unsigned integer from 0 to 255. Sign bit is zero, so we have positive number. Exponent is 00001111b or 15 in decimal. For single-precision displacement is 127, it means that we need to calculate exponent - 127 or 15 - 127 = -112. Since the normalized binary integer part of the mantissa is always equal to one, then in the mantissa is recorded only its fractional part, so mantissa or our number is 1,110000000000000000000000. Result value will be:

value = mantissa * 2^-112

Double precision number is 64 bit of memory where:

  • sign - 1 bit
  • exponent - 11 bit
  • mantissa - 52 bit

Result number we can get by:

value = (-1)^sign * (1 + mantissa / 2 ^ 52) * 2 ^ exponent - 1023)

Extended precision is 80 bit numbers where:

  • sign - 1 bit
  • exponent - 15 bit
  • mantissa - 112 bit

Read more about it - here. Let’s look at simple example.

x87 FPU

The x87 Floating-Point Unit (FPU) provides high-performance floating-point processing. It supports the floating-point, integer, and packed BCD integer data types and the floating-point processing algorithms. x87 provides following instructions set:

  • Data transfer instructions
  • Basic arithmetic instructions
  • Comparison instructions
  • Transcendental instructions
  • Load constant instructions
  • x87 FPU control instructions

Of course we will not see all instructions here provided by x87, for additional information see 64-ia-32-architecture-software-developer-vol-1-manual Chapter 8. There are a couple of data transfer instructions:

  • FDL - load floating point
  • FST - store floating point (in ST(0) register)
  • FSTP - store floating point and pop (in ST(0) register)

Arithmetic instructions:

  • FADD - add floating point
  • FIADD - add integer to floating point
  • FSUB - subtract floating point
  • FISUB - subtract integer from floating point
  • FABS - get absolute value
  • FIMUL - multiply integer and floating point
  • FIDIV - device integer and floating point

and etc… FPU has eight 10 byte registers organized in a ring stack. Top of the stack - register ST(0), other registers are ST(1), ST(2) … ST(7). We usually uses it when we are working with floating point data.

For example:

section .data
    x dw 1.0

fld dword [x]

pushes value of x to this stack. Operator can be 32bit, 64bit or 80bit. It works as usual stack, if we push another value with fld, x value will be in ST(1) and new value will be in ST(0). FPU instructions can use these registers, for example:

;;
;; adds st0 value to st3 and saves it in st0
;;
fadd st0, st3

;;
;; adds x and y and saves it in st0
;;
fld dword [x]
fld dword [y]
fadd

Let’s look on simple example. We will have circle radius and calculate circle square and print it:

extern printResult

section .data
		radius    dq  1.7
		result    dq  0

		SYS_EXIT  equ 60
		EXIT_CODE equ 0

global _start
section .text

_start:
		fld qword [radius]
		fld qword [radius]
		fmul

		fldpi
		fmul
		fstp qword [result]

		mov rax, 0
		movq xmm0, [result]
		call printResult

		mov rax, SYS_EXIT
		mov rdi, EXIT_CODE
		syscall

Let’s try to understand how it works: First of all there is data section with predefined radius data and result which we will use for storing result. After this 2 constants for calling exit system call. Next we see entry point of program - _start. There we stores radius value in st0 and st1 with fld instruction and multiply this two values with fmul instruction. After this operations we will have result of radius on radius multiplication in st0 register. Next we load The number π with fldpi instruction to the st0 register, and after it radius * radius value will be in st1 register. After this execute multiplication with fmul on st0 (pi) and st1 (value of radius * radius), result will be in st0 register. Ok, now we have circle square in st0 register and can extract it with fstp instruction to the result. Next point is to pass result to the C function and call it. Remember we call C function from assembly code in previous blog post. We need to know x86_64 calling convention. In usual way we pass function parameters through registers rdi (arg1), rsi (arg2) and etc…, but here is floating point data. There is special registers: xmm0 - xmm15 provided by sse. First of all we need to put number of xmmN register to rax register (0 for our case), and put result to xmm0 register. Now we can call C function for printing result:

#include <stdio.h>

extern int printResult(double result);

int printResult(double result) {
	printf("Circle radius is - %f\n", result);
	return 0;
}

We can build it with:

build:
	gcc  -g -c circle_fpu_87c.c -o c.o
	nasm -f elf64 circle_fpu_87.asm -o circle_fpu_87.o
	ld   -dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc circle_fpu_87.o  c.o -o testFloat1

clean:
	rm -rf *.o
	rm -rf testFloat1

And run:

result

10 Oct 2014, 00:00

Say hello to x86_64 Assembly [part 7]

It is seventh part of Say hello to x86_64 Assembly and here we will look on how we can use C together with assembler.

Actually we have 3 ways to use it together:

  • Call assembly routines from C code
  • Call c routines from assembly code
  • Use inline assembly in C code

Let’s write 3 simple Hello world programs which shows us how to use assembly and C together.

Call assembly from C

First of all let’s write simple C program like this:

#include <string.h>

int main() {
	char* str = "Hello World\n";
	int len = strlen(str);
	printHelloWorld(str, len);
	return 0;
}

Here we can see C code which defines two variables: our Hello world string which we will write to stdout and length of this string. Next we call printHelloWorld assembly function with this 2 variables as parameters. As we use x86_64 Linux, we must know x86_64 linux calling convetions, so we will know how to write printHelloWorld function, how to get incoming parameters and etc… When we call function first six parameters passes through rdi, rsi, rdx, rcx, r8 and r9 general purpose registers, all another through the stack. So we can get first and second parameter from rdi and rsi registers and call write syscall and than return from function with ret instruction:

global printHelloWorld

section .text
printHelloWorld:
		;; 1 arg
		mov r10, rdi
		;; 2 arg
		mov r11, rsi
		;; call write syscall
		mov rax, 1
		mov rdi, 1
		mov rsi, r10
		mov rdx, r11
		syscall
		ret

Now we can build it with:

build:
	nasm -f elf64 -o casm.o casm.asm
	gcc casm.o casm.c -o casm

Inline assembly

The following method is to write assembly code directly in C code. There is special syntax for this. It has general view:

asm [volatile] ("assembly code" : output operand : input operand : clobbers);

As we can read in gcc documentation volatile keyword means:

The typical use of Extended asm statements is to manipulate input values to produce output values. However, your asm statements may also produce side effects. If so, you may need to use the volatile qualifier to disable certain optimizations

Each operand is described by constraint string followed by C expression in parentheses. There are a number of constraints:

  • r - Kept variable value in general purpose register
  • g - Any register, memory or immediate integer operand is allowed, except for registers that are not general registers.
  • f - Floating point register
  • m - A memory operand is allowed, with any kind of address that the machine supports in general.
  • and etc…

So our hello world will be:

#include <string.h>

int main() {
	char* str = "Hello World\n";
	long len = strlen(str);
	int ret = 0;

	__asm__("movq $1, %%rax \n\t"
		"movq $1, %%rdi \n\t"
		"movq %1, %%rsi \n\t"
		"movl %2, %%edx \n\t"
		"syscall"
		: "=g"(ret)
		: "g"(str), "g" (len));

	return 0;
}

Here we can see the same 2 variables as in previous example and inline assembly definition. First of all we put 1 to rax and rdi registers (write system call number, and stdout) as we did it in our plain assembly hello world. Next we do similar operation with rsi and rdi registers but first operands starts with % symbol instead $. It means str is the output operand referred by %1 and len second output operand referred by %2, so we put values of str and len to rsi and rdi with %n notation, where n is number of output operand. Also there is %% prefixed to the register name.

    This helps GCC to distinguish between the operands and registers. operands have a single % as prefix

We can build it with:

build:
	gcc casm.c -o casm

Call C from assembly

And the last method is to call C function from assembly code. For example we have following simple C code with one function which just prints Hello world:

#include <stdio.h>

extern int print();

int print() {
	printf("Hello World\n");
	return 0;
}

Now we can define this function as extern in our assembly code and call it with call instruction as we do it much times in previous posts:

global _start

extern print

section .text

_start:
		call print

		mov rax, 60
		mov rdi, 0
		syscall

Build it with:

build:
	gcc  -c casm.c -o c.o
	nasm -f elf64 casm.asm -o casm.o
	ld   -dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc casm.o c.o -o casm

and now we can run our third hello world.

01 Oct 2014, 00:00

Say hello to x86_64 Assembly [part 6]

It is sixth part of Say hello to x86_64 Assembly and here we will look on AT&T assembler syntax. Previously we used nasm assembler in all parts, but there are some another assemblers with different syntax, fasm, yasm and others. As i wrote above we will look on gas (GNU assembler) and difference between it’s syntax and nasm. GCC uses GNU assembler, so if you see at assembler output for simple hello world:

#include <unistd.h>

int main(void) {
	write(1, "Hello World\n", 15);
	return 0;
}

You will see following output:

	.file	"test.c"
	.section	.rodata
.LC0:
	.string	"Hello World\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB0:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	$15, %edx
	movl	$.LC0, %esi
	movl	$1, %edi
	call	write
	movl	$0, %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 4.9.1-16ubuntu6) 4.9.1"
	.section	.note.GNU-stack,"",@progbits

Looks different then nasm Hello world, let’s look on some differences.

AT&T syntax

Sections

I don’t know how about you, but when I start to write assembler program, usually I’m starting from sections definition. Let’s look on simple example:

.data
    //
    // initialized data definition
    //
.text
    .global _start

_start:
    //
    // main routine
    //

You can note two little differences here:

  • Section definition starts with . symbol
  • Main routine defines with .globl instead global as we do it in nasm

Also gas uses another directives for data defintion:

.section .data
    // 1 byte
    var1: .byte 10
    // 2 byte
    var2: .word 10
    // 4 byte
    var3: .int 10
    // 8 byte
    var4: .quad 10
    // 16 byte
    var5: .octa 10

    // assembles each string (with no automatic trailing zero byte) into consecutive addresses
    str1: .asci "Hello world"
    // just like .ascii, but each string is followed by a zero byte
    str2: .asciz "Hello world"
    // Copy the characters in str to the object file
    str3: .string "Hello world"

Operands order When we write assembler program with nasm, we have following general syntax for data manipulation:

mov destination, source

With GNU assembler we have back order i.e.:

mov source, destination

For example:

;;
;; nasm syntax
;;
mov rax, rcx

//
// gas syntax
//
mov %rcx, %rax

Also you can not here that registers starts with % symbol. If you’re using direct operands, need to use $ symbol:

movb $10, %rax

Size of operands and operation syntax

Sometimes when we need to get part of memory, for example first byte of 64 register, we used following syntax:

mov ax, word [rsi]

There is another way for such operations in gas. We don’t define size in operands but in instruction:

movw (%rsi), %ax

GNU assembler has 6 postfixes for operations:

  • b - 1 byte operands
  • w - 2 bytes operands
  • l - 4 bytes operands
  • q - 8 bytes operands
  • t - 10 bytes operands
  • o - 16 bytes operands

This rule is not only mov instruction, but also for all another like addl, xorb, cmpw and etc…

Memory access

You can note that we used () brackets in previous example instead [] in nasm example. To dereference values in parentheses are used GAS: (%rax), for example:

movq -8(%rbp),%rdi
movq 8(%rbp),%rdi

Jumps

GNU assembler supports following operators for far functions call and jumps:

lcall $section, $offset

Far jump - a jump to an instruction located in a different segment than the current code segment but at the same privilege level, sometimes referred to as an intersegment jump.

Comments

GNU assembler supports 3 types of comments:

    # - single line comments
    // - single line comments
    /* */ - for multiline comments

20 Sep 2014, 00:00

Say hello to x86_64 Assembly [part 5]

It is a fifth part of Say hello to x86_64 Assembly and here we will look at macros. It will not be blog post about x86_64, mainly it will be about nasm assembler and it’s preprocessor. If you’re interesting in it read next.

Macros

NASM supports two form of macro:

  • single-line
  • multiline

All single-line macro must start from %define directive. It form is following:

%define macro_name(parameter) value

Nasm macro behaves and looks very similar as in C. For example, we can create following single-line macro:

%define argc rsp + 8
%define cliArg1 rsp + 24

and than use it in code:

;;
;; argc will be expanded to rsp + 8
;;
mov rax, [argc]
cmp rax, 3
jne .mustBe3args

Multiline macro starts with %macro nasm directive and end with %endmacro. It general form is following:

%macro number_of_parameters
    instruction
    instruction
    instruction
%endmacro

For example:

%macro bootstrap 1
          push ebp
          mov ebp,esp
%endmacro

And we can use it:

_start:
    bootstrap

For example let’s look at PRINT macro:

%macro PRINT 1
    pusha
    pushf
    jmp %%astr
%%str db %1, 0
%%strln equ $-%%str
%%astr: _syscall_write %%str, %%strln
popf
popa
%endmacro

%macro _syscall_write 2
	mov rax, 1
        mov rdi, 1
        mov rsi, %%str
        mov rdx, %%strln
        syscall
%endmacro

Let’s try to go through it macro and understand how it works: At first line we defined PRINT macro with one parameter. Than we push all general registers (with pusha instruction) and flag register with (with pushf instruction). After this we jump to %%astr label. Pay attention that all labels which defined in macro must start with %%. Now we move to __syscall_write macro with 2 parameter. Let’s look on __syscall_write implementation. You can remember that we use write system call in all previous posts for printing string to stdout. It looks like this:

;; write syscall number
mov rax, 1
;; file descriptor, standard output
mov rdi, 1
;; message address
mov rsi, msg
;; length of message
mov rdx, 14
;; call write syscall
syscall

In our __syscall_write macro we define first two instruction for putting 1 to rax (write system call number) and rdi (stdout file descriptor). Than we put %%str to rsi register (pointer to string), where %%str is local label to which is get first parameter of PRINT macro (pay attention that macro parameter access by $parameter_number) and end with 0 (every string must end with zero). And %%strlen which calculates string length. After this we call system call with syscall instruction and that’s all.

Now we can use it:

label: PRINT "Hello World!"

Useful standard macros

NASM supports following standard macros:

STRUC

We can use STRUC and ENDSTRUC for data structure defintion. For example:

struc person
   name: resb 10
   age:  resb 1
endstruc

And now we can make instance of our structure:

section .data
    p: istruc person
      at name db "name"
      at age  db 25
    iend

section .text
_start:
    mov rax, [p + person.name]

%include

We can include other assembly files and jump to there labels or call functions with %include directive.

01 Sep 2014, 00:00

Say hello to x86_64 Assembly [part 4]

Some time ago i started to write series of blog posts about assembly programming for x86_64. You can find it by asm tag. Unfortunately i was busy last time and there were not new post, so today I continue to write posts about assembly, and will try to do it every week.

Today we will look at strings and some strings operations. We still use nasm assembler, and linux x86_64.

Reverse string

Of course when we talk about assembly programming language we can’t talk about string data type, actually we’re dealing with array of bytes. Let’s try to write simple example, we will define string data and try to reverse and write result to stdout. This tasks seems pretty simple and popular when we start to learn new programming language. Let’s look on implementation.

First of all, I define initialized data. It will be placed in data section (You can read about sections in part):

section .data
		SYS_WRITE equ 1
		STD_OUT   equ 1
		SYS_EXIT  equ 60
		EXIT_CODE equ 0

		NEW_LINE db 0xa
		INPUT db "Hello world!"

Here we can see four constants:

  • SYS_WRITE - ‘write’ syscall number
  • STD_OUT - stdout file descriptor
  • SYS_EXIT - ‘exit’ syscall number
  • EXIT_CODE - exit code

syscall list you can find - here. Also there defined:

  • NEW_LINE - new line (\n) symbol
  • INPUT - our input string, which we will reverse

Next we define bss section for our buffer, where we will put reversed string:

section .bss
		OUTPUT resb 12

Ok we have some data and buffer where to put result, now we can define text section for code. Let’s start from main _start routine:

_start:
		mov rsi, INPUT
		xor rcx, rcx
		cld
		mov rdi, $ + 15
		call calculateStrLength
		xor rax, rax
		xor rdi, rdi
		jmp reverseStr

Here are some new things. Let’s see how it works: First of all we put INPUT address to si register at line 2, as we did for writing to stdout and write zeros to rcx register, it will be counter for calculating length of our string. At line 4 we can see cld operator. It resets df flag to zero. We need in it because when we will calculate length of string, we will go through symbols of this string, and if df flag will be 0, we will handle symbols of string from left to right. Next we call calculateStrLength function. I missed line 5 with mov rdi, $ + 15 instruction, i will tell about it little later. And now let’s look at calculateStrLength implementation:

calculateStrLength:
		;; check is it end of string
		cmp byte [rsi], 0
		;; if yes exit from function
		je exitFromRoutine
		;; load byte from rsi to al and inc rsi
		lodsb
		;; push symbol to stack
		push rax
		;; increase counter
		inc rcx
		;; loop again
		jmp calculateStrLength

As you can understand by it’s name, it just calculates length of INPUT string and store result in rcx register. First of all we check that rsi register doesn’t point to zero, if so this is the end of string and we can exit from function. Next is lodsb instruction. It’s simple, it just put 1 byte to al register (low part of 16 bit ax) and changes rsi pointer. As we executed cld instruction, lodsb everytime will move rsi to one byte from left to right, so we will move by string symbols. After it we push rax value to stack, now it contains symbol from our string (lodsb puts byte from si to al, al is low 8 bit of rax). Why we did push symbol to stack? You must remember how stack works, it works by principle LIFO (last input, first output). It is very good for us. We will take first symbol from si, push it to stack, than second and so on. So there will be last symbol of string at the stack top. Than we just pop symbol by symbol from stack and write to OUTPUT buffer. After it we increment our counter (rcx) and loop again to the start of routine.

Ok, we pushed all symbols from string to stack, now we can jump to exitFromRoutine return to _start there. How to do it? We have ret instruction for this. But if code will be like this:

exitFromRoutine:
		;; return to _start
		ret

It will not work. Why? It is tricky. Remember we called calculateStrLength at _start. What occurs when we call a function? First of all function’s parameters pushes to stack from right to left. After it return address pushes to stack. So function will know where to return after end of execution. But look at calculateStrLength, we pushed symbols from our string to stack and now there is no return address of stack top and function doesn’t know where to return. How to be with it. Now we must take a look to the weird instruction before call:

    mov rdi, $ + 15

First all:

  • $ - returns position in memory of string where $ defined
  • $$ - returns position in memory of current section start

So we have position of mov rdi, $ + 15, but why we add 15 here? Look, we need to know position of next line after calculateStrLength. Let’s open our file with objdump util:

objdump -D reverse

reverse:     file format elf64-x86-64

Disassembly of section .text:

00000000004000b0 <_start>:
  4000b0:	48 be 41 01 60 00 00 	movabs $0x600141,%rsi
  4000b7:	00 00 00
  4000ba:	48 31 c9             	xor    %rcx,%rcx
  4000bd:	fc                   	cld
  4000be:	48 bf cd 00 40 00 00 	movabs $0x4000cd,%rdi
  4000c5:	00 00 00
  4000c8:	e8 08 00 00 00       	callq  4000d5 <calculateStrLength>
  4000cd:	48 31 c0             	xor    %rax,%rax
  4000d0:	48 31 ff             	xor    %rdi,%rdi
  4000d3:	eb 0e                	jmp    4000e3 <reverseStr>

We can see here that line 12 (our mov rdi, $ + 15) takes 10 bytes and function call at line 16 - 5 bytes, so it takes 15 bytes. That’s why our return address will be mov rdi, $ + 15. Now we can push return address from rdi to stack and return from function:

exitFromRoutine:
		;; push return addres to stack again
		push rdi
		;; return to _start
		ret

Now we return to start. After call of the calculateStrLength we write zeros to rax and rdi and jump to reverseStr label. It’s implementation is following:

reverseStr:
		cmp rcx, 0
		je printResult
		pop rax
		mov [OUTPUT + rdi], rax
		dec rcx
		inc rdi
		jmp reverseStr

Here we check our counter which is length of string and if it is zero we wrote all symbols to buffer and can print it. After checking counter we pop from stack to rax register first symbol and write it to OUTPUT buffer. We add rdi because in other way we’ll write symbol to first byte of buffer. After this we increase rdi for moving next by OUTPUT buffer, decrease length counter and jump to the start of label.

After execution of reverseStr we have reversed string in OUTPUT buffer and can write result to stdout with new line:

printResult:
		mov rdx, rdi
		mov rax, 1
		mov rdi, 1
		mov rsi, OUTPUT
                syscall
		jmp printNewLine

printNewLine:
		mov rax, SYS_WRITE
		mov rdi, STD_OUT
		mov rsi, NEW_LINE
		mov rdx, 1
		syscall
		jmp exit

and exit from the our program:

exit:
		mov rax, SYS_EXIT
		mov rdi, EXIT_CODE
		syscall

That’s all, now we can compile our program with:

all:
	nasm -g -f elf64 -o reverse.o reverse.asm
	ld -o reverse reverse.o

clean:
	rm reverse reverse.o

and run it:

result

String operations

Of course there are many other instructions for string/bytes manipulations:

  • REP - repeat while rcx is not zero
  • MOVSB - copy a string of bytes (MOVSW, MOVSD and etc..)
  • CMPSB - byte string comparison
  • SCASB - byte string scanning
  • STOSB - write byte to string

15 Aug 2014, 00:00

Say hello to x86_64 Assembly [part 3]

The stack is special region in memory, which operates on the principle lifo (Last Input, First Output).

We have 16 general-purpose registers for temporary data storage. They are RAX, RBX, RCX, RDX, RDI, RSI, RBP, RSP and R8-R15. It’s too few for serious applications. So we can store data in the stack. Yet another usage of stack is following: When we call a function, return address copied in stack. After end of function execution, address copied in commands counter (RIP) and application continue to executes from next place after function.

For example:

global _start

section .text

_start:
		mov rax, 1
		call incRax
		cmp rax, 2
		jne exit
		;;
		;; Do something
		;;

incRax:
		inc rax
		ret

Here we can see that after application runnning, rax is equal to 1. Then we call a function incRax, which increases rax value to 1, and now rax value must be 2. After this execution continues from 8 line, where we compare rax value with 2. Also as we can read in System V AMD64 ABI, the first six function arguments passed in registers. They are:

  • rdi - first argument
  • rsi - second argument
  • rdx - third argument
  • rcx - fourth argument
  • r8 - fifth argument
  • r9 - sixth

Next arguments will be passed in stack. So if we have function like this:

int foo(int a1, int a2, int a3, int a4, int a5, int a6, int a7)
{
    return (a1 + a2 - a3 - a4 + a5 - a6) * a7;
}

Then first six arguments will be passed in registers, but 7 argument will be passed in stack.

Stack pointer

As i wroute about we have 16 general-purpose registers, and there are two interesting registers - RSP and RBP. RBP is the base pointer register. It points to the base of the current stack frame. RSP is the stack pointer, which points to the top of current stack frame.

Commands

We have two commands for work with stack:

  • push argument - increments stack pointer (RSP) and stores argument in location pointed by stack pointer
  • pop argument - copied data to argument from location pointed by stack pointer

Let’s look on one simple example:

global _start

section .text

_start:
		mov rax, 1
		mov rdx, 2
		push rax
		push rdx

		mov rax, [rsp + 8]

		;;
		;; Do something
		;;

Here we can see that we put 1 to rax register and 2 to rdx register. After it we push to stack values of these registers. Stack works as LIFO (Last In First Out). So after this stack or our application will have following structure:

stack diagram

Then we copy value from stack which has address rsp + 8. It means we get address of top of stack, add 8 to it and copy data by this address to rax. After it rax value will be 1.

Example

Let’s see one example. We will write simple program, which will get two command line arguments. Will get sum of this arguments and print result.

section .data
		SYS_WRITE equ 1
		STD_IN    equ 1
		SYS_EXIT  equ 60
		EXIT_CODE equ 0

		NEW_LINE   db 0xa
		WRONG_ARGC db "Must be two command line argument", 0xa

First of all we define .data section with some values. Here we have four constants for linux syscalls, for sys_write, sys_exit and etc… And also we have two strings: First is just new line symbol and second is error message.

Let’s look on the .text section, which consists from code of program:

section .text
        global _start

_start:
		pop rcx
		cmp rcx, 3
		jne argcError

		add rsp, 8
		pop rsi
		call str_to_int

		mov r10, rax
		pop rsi
		call str_to_int
		mov r11, rax

		add r10, r11

Let’s try to understand, what is happening here: After _start label first instruction get first value from stack and puts it to rcx register. If we run application with command line arguments, all of their will be in stack after running in following order:

    [rsp] - top of stack will contain arguments count.
    [rsp + 8] - will contain argv[0]
    [rsp + 16] - will contain argv[1]
    and so on...

So we get command line arguments count and put it to rcx. After it we compare rcx with 3. And if they are not equal we jump to argcError label which just prints error message:

argcError:
    ;; sys_write syscall
    mov     rax, 1
    ;; file descritor, standard output
	mov     rdi, 1
    ;; message address
    mov     rsi, WRONG_ARGC
    ;; length of message
    mov     rdx, 34
    ;; call write syscall
    syscall
    ;; exit from program
	jmp exit

Why we compare with 3 when we have two arguments. It’s simple. First argument is a program name, and all after it are command line arguments which we passed to program. Ok, if we passed two command line arguments we go next to 10 line. Here we shift rsp to 8 and thereby missing the first argument - the name of the program. Now rsp points to first command line argument which we passed. We get it with pop command and put it to rsi register and call function for converting it to integer. Next we read about str_to_int implementation. After our function ends to work we have integer value in rax register and we save it in r10 register. After this we do the same operation but with r11. In the end we have two integer values in r10 and r11 registers, now we can get sum of it with add command. Now we must convert result to string and print it. Let’s see how to do it:

mov rax, r10
;; number counter
xor r12, r12
;; convert to string
jmp int_to_str

Here we put sum of command line arguments to rax register, set r12 to zero and jump to int_to_str. Ok now we have base of our program. We already know how to print string and we have what to print. Let’s see at str_to_int and int_to_str implementation.

str_to_int:
            xor rax, rax
            mov rcx,  10
next:
	    cmp [rsi], byte 0
	    je return_str
	    mov bl, [rsi]
            sub bl, 48
	    mul rcx
	    add rax, rbx
	    inc rsi
	    jmp next

return_str:
	    ret

At the start of str_to_int, we set up rax to 0 and rcx to 10. Then we go to next label. As you can see in above example (first line before first call of str_to_int) we put argv[1] in rsi from stack. Now we compare first byte of rsi with 0, because every string ends with NULL symbol and if it is we return. If it is not 0 we copy it’s value to one byte bl register and substract 48 from it. Why 48? All numbers from 0 to 9 have 48 to 57 codes in asci table. So if we substract from number symbol 48 (for example from 57) we get number. Then we multiply rax on rcx (which has value - 10). After this we increment rsi for getting next byte and loop again. Algorthm is simple. For example if rsi points to ‘5’ ‘7’ ‘6’ ‘\000’ sequence, then will be following steps:

    rax = 0
    get first byte - 5 and put it to rbx
    rax * 10 --> rax = 0 * 10
    rax = rax + rbx = 0 + 5
    Get second byte - 7 and put it to rbx
    rax * 10 --> rax = 5 * 10 = 50
    rax = rax + rbx = 50 + 7 = 57
    and loop it while rsi is not \000

After str_to_int we will have number in rax. Now let’s look at int_to_str:

int_to_str:
		mov rdx, 0
		mov rbx, 10
		div rbx
		add rdx, 48
		add rdx, 0x0
		push rdx
		inc r12
		cmp rax, 0x0
		jne int_to_str
		jmp print

Here we put 0 to rdx and 10 to rbx. Than we exeute div rbx. If we look above at code before str_to_int call. We will see that rax contains integer number - sum of two command line arguments. With this instruction we devide rax value on rbx value and get reminder in rdx and whole part in rax. Next we add to rdx 48 and 0x0. After adding 48 we’ll get asci symbol of this number and all strings much be ended with 0x0. After this we save symbol to stack, increment r12 (it’s 0 at first iteration, we set it to 0 at the _start) and compare rax with 0, if it is 0 it means that we ended to convert integer to string. Algorithm step by step is following: For example we have number 23

    123 / 10. rax = 12; rdx = 3
    rdx + 48 = "3"
    push "3" to stack
    compare rax with 0 if no go again
    12 / 10. rax = 1; rdx = 2
    rdx + 48 = "2"
    push "2" to stack
    compare rax with 0, if yes we can finish function execution and we will have "2" "3" ... in stack

We implemented two useful function int_to_str and str_to_int for converting integer number to string and vice versa. Now we have sum of two integers which was converted into string and saved in the stack. We can print result:

print:
	;;;; calculate number length
	mov rax, 1
	mul r12
	mov r12, 8
	mul r12
	mov rdx, rax

	;;;; print sum
	mov rax, SYS_WRITE
	mov rdi, STD_IN
	mov rsi, rsp
	;; call sys_write
	syscall

    jmp exit

We already know how to print string with sys_write syscall, but here is one interesting part. We must to calculate length of string. If you will look on the int_to_str, you will see that we increment r12 register every iteration, so it contains amount of digits in our number. We must multiple it to 8 (because we pushed every symbol to stack) and it will be length of our string which need to print. After this we as everytime put 1 to rax (sys_write number), 1 to rdi (stdin), string length to rdx and pointer to the top of stack to rsi (start of string). And finish our program:

exit:
	mov rax, SYS_EXIT
	exit code
	mov rdi, EXIT_CODE
	syscall

That’s All.

10 Aug 2014, 00:00

Say hello to x86_64 Assembly [part 2]

Some days ago I wrote the first blog post - introduction to x64 assembly - Say hello to x64 Assembly [part 1] which to my surprise caused great interest:

newscombinator reddit

It motivates me even more to describe my way of learning. During this days I got many feedback from different people. There were many grateful words, but what is more important for me, there were many advices and adequate critics. Especially I want to say thank you words for great feedback to:

It motivates me even more to describe my way of learning. During this days I got many feedback from different people. There were many grateful words, but what is more important for me, there were many advices and adequate critics. Especially I want to say thank you words for great feedback to:

And all who took a part in discussion at Reddit and Hacker News. There were many opinions, that first part was a not very clear for absolute beginner, that’s why i decided to write more informative posts. So, let’s start with second part of Say hello to x86_64 assembly.

Terminology and Concepts

As i wrote above, I got many feedback from different people that some parts of first post are not clear, that’s why let’s start from description of some terminology that we will see in this and next parts.

Register - register is a small amount of storage inside processor. Main point of processor is data processing. Processor can get data from memory, but it is slow operation. That’s why processor has own internal restricted set of data storage which name is - register.

Little-endian - we can imagine memory as one large array. It contains bytes. Each address stores one element of the memory “array”. Each element is one byte. For example we have 4 bytes: AA 56 AB FF. In little-endian the least significant byte has the smallest address:

    0 FF
    1 AB
    2 56
    3 AA

where 0,1,2 and 3 are memory addresses.

Big-endian - big-endian stores bytes in opposite order than little-endian. So if we have AA 56 AB FF bytes sequence it will be:

    0 AA
    1 56
    2 AB
    3 FF

Syscall - is the way a user level program asks the operating system to do something for it. You can find syscall table - here.

Stack - processor has a very restricted count of registers. So stack is a continuous area of ​​memory addressable special registers RSP,SS,RIP and etc. We will take a closer look on stack in next parts.

Section - every assembly program consists from sections. There are following sections:

  • data - section is used for declaring initialized data or constants
  • bss - section is used for declaring non initialized variables
  • text - section is used for code

General-purpose registers - there are 16 general-purpose registers - rax, rbx, rcx, rdx, rbp, rsp, rsi, rdi, r8, r9, r10, r11, r12, r13, r14, r15. Of course, it is not a full list of terms and concepts which related with assembly programming. If we will meet another strange and unfamiliar words in next blog posts, there will be explanation of this words.

Data Types

The fundamental data types are bytes, words, doublewords, quadwords, and double quadwords. A byte is eight bits, a word is 2 bytes, a doubleword is 4 bytes, a quadword is 8 bytes and a double quadword is 16 bytes (128 bits).

Now we will work only with integer numbers, so let’s see to it. There two types of integer: unsigned and signed. Unsigned integers are unsigned binary numbers contained in a byte, word, doubleword, and quadword. Their values range from 0 to 255 for an unsigned byte integer, from 0 to 65,535 for an unsigned word integer, from 0 to 2^32 – 1 for an unsigned doubleword integer, and from 0 to 2^64 – 1 for an unsigned quadword integer. Signed integers are signed binary numbers held as unsigned in a byte, word and etc… The sign bit is set for negative integers and cleared for positive integers and zero. Integer values range from –128 to +127 for a byte integer, from –32,768 to +32,767 for a word integer,from –2^31 to +2^31 – 1 for a doubleword integer, and from –2^63 to +2^63 – 1 for a quadword integer.

Sections

As i wrote above, every assembly program consists from sections, it can be data section, text section and bss section. Let’s look on data section.It’s main point - to declare initialized constants. For example:

section .data
    num1:   equ 100
    num2:   equ 50
    msg:    db "Sum is correct", 10

Ok, it is almost all clear here. 3 constants with name num1, num2, msg and with values 100, 50 and “Sum is correct”, 10. But what is it db, equ? Actual NASM supports a number of pseudo-instructions:

  • DB, DW, DD, DQ, DT, DO, DY and DZ - are used for declaring initialized data. For example:
;; Initialize 4 bytes 1h, 2h, 3h, 4h
db 0x01,0x02,0x03,0x04

;; Initialize word to 0x12 0x34
dw    0x1234
  • RESB, RESW, RESD, RESQ, REST, RESO, RESY and RESZ - are used for declaring non initialized variables
  • INCBIN - includes External Binary Files
  • EQU - defines constant. For example:
;; now one is 1
one equ 1
  • TIMES - Repeating Instructions or Data. (description will be in next posts)

Arithmetic operations

There is short list of arithmetic instructions:

  • ADD - integer add
  • SUB - substract
  • MUL - unsigned multiply
  • IMUL - signed multiply
  • DIV - unsigned divide
  • IDIV - signed divide
  • INC - increment
  • DEC - decrement
  • NEG - negate

Some of it we will see at practice in this post. Other will be covered in next posts.

Control flow

Usually programming languages have ability to change order of evaluation (with if statement, case statement, goto and etc…) and assembly has it too. Here we will see some of it. There is cmp instruction for performing comparison between two values. It is used along with the conditional jump instruction for decision making. For example:

;; compare rax with 50
cmp rax, 50

The cmp instruction just compares 2 values, but doesn’t affect them and doesn’t execute anything depend on result of comparison. For performing any actions after comparison there is conditional jump instructions. It can be one of it:

  • JE - if equal
  • JZ - if zero
  • JNE - if not equal
  • JNZ - if not zero
  • JG - if first operand is greater than second
  • JGE - if first operand is greater or equal to second
  • JA - the same that JG, but performs unsigned comparison
  • JAE - the same that JGE, but performs unsigned comparison

For example if we want to make something like if/else statement in C:

if (rax != 50) {
    exit();
} else {
    right();
}

will be in assembly:

;; compare rax with 50
cmp rax, 50
;; perform .exit if rax is not equal 50
jne .exit
jmp .right

There is also unconditional jump with syntax:

JMP label

For example:

_start:
    ;; ....
    ;; do something and jump to .exit label
    ;; ....
    jmp .exit

.exit:
    mov    rax, 60
    mov    rdi, 0
    syscall

Here we have can have some code which will be after _start label, and all of this code will be executed, assembly transfer control to .exit label, and code after .exit: will start to execute.

Often unconditional jump uses in loops. For example we have label and some code after it. This code executes anything, than we have condition and jump to the start of this code if condition is not successfully. Loops will be covered in next parts.

Example

Let’s see simple example. It will take two integer numbers, get sum of these numbers and compare it with predefined number. If predefined number is equal to sum, it will print something on the screen, if not - just exit. Here is the source code of our example:

section .data
    ; Define constants
    num1:   equ 100
    num2:   equ 50
    ; initialize message
    msg:    db "Sum is correct\n"

section .text

    global _start

;; entry point
_start:
    ; set num1's value to rax
    mov rax, num1
    ; set num2's value to rbx
    mov rbx, num2
    ; get sum of rax and rbx, and store it's value in rax
    add rax, rbx
    ; compare rax and 150
    cmp rax, 150
    ; go to .exit label if rax and 150 are not equal
    jne .exit
    ; go to .rightSum label if rax and 150 are equal
    jmp .rightSum

; Print message that sum is correct
.rightSum:
    ;; write syscall
    mov     rax, 1
    ;; file descritor, standard output
    mov     rdi, 1
    ;; message address
    mov     rsi, msg
    ;; length of message
    mov     rdx, 15
    ;; call write syscall
    syscall
    ; exit from program
    jmp .exit

; exit procedure
.exit:
    ; exit syscall
    mov    rax, 60
    ; exit code
    mov    rdi, 0
    ; call exit syscall
    syscall

Let’s go through the source code. First of all there is data section with two constants num1, num2 and variable msg with “Sum is correct\n” value. Now look at 14 line. There is begin of program’s entry point. We transfer num1 and num2 values to general purpose registers rax and rbx. Sum it with add instruction. After execution of add instruction, it calculates sum of values from rax and rbx and store it’s value to rax. Now we have sum of num1 and num2 in the rax register.

Ok we have num1 which is 100 and num2 which is 50. Our sum must be 150. Let’s check it with cmp instruction. After comparison rax and 150 we check result of comparison, if rax and 150 are not equal (checking it with jne) we go to .exit label, if they are equal we go to .rightSum label.

Now we have two labels: .exit and .rightSum. First is just sets 60 to rax, it is exit system call number, and 0 to rdi, it is a exit code. Second is .rightSum is pretty easy, it just prints Sum is correct.

01 Aug 2014, 00:00

Say hello to x86_64 Assembly [part 1]

Introduction

There are many developers between us. We write a tons of code every day. Sometime, it is even not a bad code :) Every of us can easily write the simplest code like this:

#include <stdio.h>

int main() {
  int x = 10;
  int y = 100;
  printf("x + y = %d", x + y);
  return 0;
}

Every of us can understand what’s this C code does. But… How this code works at low level? I think that not all of us can answer on this question, and me too. I thought that i can write code on high level programming languages like Haskell, Erlang, Go and etc…, but i absolutely don’t know how it works at low level, after compilation. So I decided to take a few deep steps down, to assembly, and to describe my learning way about this. Hope it will be interesting, not only for me. Something about 5 - 6 years ago I already used assembly for writing simple programs, it was in university and i used Turbo assembly and DOS operating system. Now I use Linux-x86-64 operating system. Yes, must be big difference between Linux 64 bit and DOS 16 bit. So let’s start.

Preparation

Before we started, we must to prepare some things like As I wrote about, I use Ubuntu (Ubuntu 14.04.1 LTS 64 bit), thus my posts will be for this operating system and architecture. Different CPU supports different set of instructions. I use Intel Core i7 870 processor, and all code will be written processor. Also i will use nasm assembly. You can install it with:

$ sudo apt-get install nasm

It’s version must be 2.0.0 or greater. I use NASM version 2.10.09 compiled on Dec 29 2013 version. And the last part, you will need in text editor where you will write you assembly code. I use Emacs with nasm-mode.el for this. It is not mandatory, of course you can use your favourite text editor. If you use Emacs as me you can download nasm-mode.el and configure your Emacs like this:

(load "~/.emacs.d/lisp/nasm.el")
(require 'nasm-mode)
(add-to-list 'auto-mode-alist '("\\.\\(asm\\|s\\)$" . nasm-mode))

That’s all we need for this moment. Other tools will be describe in next posts.

Syntax of nasm assembly

Here I will not describe full assembly syntax, we’ll mention only those parts of the syntax, which we will use in this post. Usually NASM program divided into sections. In this post we’ll meet 2 following sections:

  • data section
  • text section

The data section is used for declaring constants. This data does not change at runtime. You can declare various math or other constants and etc… The syntax for declaring data section is:

    section .data

The text section is for code. This section must begin with the declaration global _start, which tells the kernel where the program execution begins.

    section .text
    global _start
    _start:

Comments starts with the ; symbol. Every NASM source code line contains some combination of the following four fields:

[label:] instruction [operands] [; comment]

Fields which are in square brackets are optional. A basic NASM instruction consists from two parts. The first one is the name of the instruction which is to be executed, and the second are the operands of this command. For example:

    MOV COUNT, 48 ; Put value 48 in the COUNT variable

Hello world

Let’s write first program with NASM assembly. And of course it will be traditional Hello world program. Here is the code of it:

section .data
    msg db      "hello, world!"

section .text
    global _start
_start:
    mov     rax, 1
    mov     rdi, 1
    mov     rsi, msg
    mov     rdx, 13
    syscall
    mov    rax, 60
    mov    rdi, 0
    syscall

Yes, it doesn’t look like printf(“Hello world”). Let’s try to understand what is it and how it works. Take a look 1-2 lines. We defined data section and put there msg constant with Hello world value. Now we can use this constant in our code. Next is declaration text section and entry point of program. Program will start to execute from 7 line. Now starts the most interesting part. We already know what is it mov instruction, it gets 2 operands and put value of second to first. But what is it these rax, rdi and etc… As we can read in the wikipedia:

A central processing unit (CPU) is the hardware within a computer that carries out the instructions of a computer program by performing the basic arithmetical, logical, and input/output operations of the system.

Ok, CPU performs some operations, arithmetical and etc… But where can it get data for this operations? The first answer in memory. However, reading data from and storing data into memory slows down the processor, as it involves complicated processes of sending the data request across the control bus. Thus CPU has own internal memory storage locations called registers:

registers

So when we write mov rax, 1, it means to put 1 to the rax register. Now we know what is it rax, rdi, rbx and etc… But need to know when to use rax but when rsi and etc…

  • rax - temporary register; when we call a syscal, rax must contain syscall number
  • rdx - used to pass 3rd argument to functions
  • rdi - used to pass 1st argument to functions
  • rsi - pointer used to pass 2nd argument to functions

In another words we just make a call of sys_write syscall. Take a look on sys_write:

size_t sys_write(unsigned int fd, const char * buf, size_t count);

It has 3 arguments:

  • fd - file descriptor. Can be 0, 1 and 2 for standard input, standard output and standard error
  • buf - points to a character array, which can be used to store content obtained from the file pointed to by fd.
  • count - specifies the number of bytes to be written from the file into the character array

So we know that sys_write syscall takes three arguments and has number one in syscall table. Let’s look again to our hello world implementation. We put 1 to rax register, it means that we will use sys_write system call. In next line we put 1 to rdi register, it will be first argument of sys_write, 1 - standard output. Then we store pointer to msg at rsi register, it will be second buf argument for sys_write. And then we pass the last (third) parameter (length of string) to rdx, it will be third argument of sys_write. Now we have all arguments of the sys_write and we can call it with syscall function at 11 line. Ok, we printed “Hello world” string, now need to do correctly exit from program. We pass 60 to rax register, 60 is a number of exit syscall. And pass also 0 to rdi register, it will be error code, so with 0 our program must exit successfully. That’s all for “Hello world”. Quite simple :) Now let’s build our program. For example we have this code in hello.asm file. Then we need to execute following commands:

$ nasm -f elf64 -o hello.o hello.asm
$ ld -o hello hello.o

After it we will have executable hello file which we can run with ./hello and will see Hello world string in the terminal.