Samuel Jacob's Weblog

Here is my thoughts about how to combine a Heap and AVL tree and get benefit of both them from a single data structure.

A self balancing binary search tree such as AVL tree can do faster lookup for a item in the tree in O(log n). Heaps are mainly used to implement priority queues which needs to find min/max elements quickly. Heap achieves this in O(1) time complexity.

Lets revisit a basic property of binary search tree – In a binary search tree min element is at the left most leaf position. Similarly in a BST max element is at the right most leaf position. So finding min/max element in a BST is O(h) where h is the depth of the tree. If the BST is a balanced tree then O(h) is O(log n) in worst case(otherwise the worst case O(n), since we considering only balanced trees here lets ignore the unbalanced cases). The following diagram illustrates a basic property of the BST – min element is always on the left most node.

Using this basic property, min remove operation can be optimized. The first and simplest optimization comes to mind is store a pointer to min/max elements. This caching will result in O(1) time complexity for finding min/max elements. However this would increase the cost of node insert/delete because the min/max pointer has to be updated during insert and deletion. The cost of finding and deleting a min node is O(log(n)) which is same as if we havent had the cache pointers. The picture in the right shows advantage of having cached pointer to find a min element. Obviously this method cant be used for priority queues where find min/delete operation is used together.

In the above method the problem was the complexity finding next smallest element in the tree from min element is O(log n). So if we have pointer to next smallest element from all nodes then find and delete opearation would be of complexity O(1).

Lets look at the BST from slightly different angle. Usual declaration of BST in C as follows:

[c]
struct binary_tree
{
struct binary_tree *left;
struct binary_tree *right;
};
[/c]

When we(me and +Dilip Simha) were implementing ADT for AceOS we decided to experiment BST in a different way. We saw tree as recursive lists rather than a recursive pointers.

In the following picture you could see 6 lists(not counting sub-lists):

1. (300, 200, 100, 50)
2. (300, 400, 500, 600)
3. (200, 250, 275)
4. (100, 150)
5. (400, 350)
6. (500, 450)

Now consider this list is a doubly linked circular list. This is illustrated in the following figure. You may argue that this will make the BST to become cyclic directed graph. But for the sake of simplicity lets continue to call this as balanced BST. In the picture I left out few arrows to keep it cleaner.

[c]
typedef struct list LIST, * LIST_PTR;
struct list {
LIST_PTR next;
LIST_PTR prev;
};

typedef struct binary_tree
{
LIST left;
LIST right;
}BINARY_TREE;

typedef struct avl_tree
{
int height; /*! height of the node*/
BINARY_TREE bintree; /*! low level binary tree*/
}AVL_TREE;
[/c]

AVL tree in Ace OS  is implemented in this way. You can see the data structure declarations below. Initially we did it for reusing the code. But after implementing this we figured out some interesting properties. This balanced tree/graph can find any node in O(log(n)) and also offers findmin operation in O(1) complexity. This also reduces the complexity of delete operation(since we can find right node’s left most child in O(1) operation). But delete operation might result in balancing the tree.

I wrote ACPI driver for Ace and try to load it into kernel. It was failing with the error message symbol not found.

The log file content says AcpiGetName was not found.
[shell]
$ cat log.txt
Driver for id acpi : acpi.sys
../src/kernel/pm/elf.c:343:FindElfSymbolByName(): Symbol not found AcpiGetName(c01a2148:1869) string table c01aa619
[shell]

After exploring the Acpi-CA source code and Ace kernel code, I couldn’t figure out why the symbol is missing. Then I tried to dump the symbol table for Acpi library and kernel.sys.
[shell]
$ nm build/default/src/kernel/libacpi.a | grep GetName
U AcpiExGetNameString
000001e3 T AcpiExGetNameString
000001b7 T AcpiPsGetName
000000f4 T AcpiGetName

$ nm build/default/src/kernel/kernel.sys | grep GetName
c0135163 T AcpiExGetNameString
c0137bfb T AcpiPsGetName
[/shell]

It is obvious during kernel link process some how the linker is losing AcpiGetName. Within few seconds I realized that the linker is doing optimization on the output to remove unreferenced sections. So I googled for how to avoid this and found –no-gc-sections is the ld option to do it. However even after giving this option to linker to was removing the unreferenced symbols; I kept on trying to find a solution for making the linker to include unreferenced symbols in the output… I didn’t find the solution.
Then I started thinking how linux kernel is avoiding this problem and I it flashed seeing EXPORT_SYMBOL kind of macro in some source. So I googled for it and got the answer – use the symbol in storage, so that it will be referenced, so that linker will include it in the output.
[c]
struct kernel_symbol
{
unsigned long symbol;
char * name;
};

#ifndef MODULE_SYMBOL_PREFIX
#define MODULE_SYMBOL_PREFIX “”
#endif

#define __EXPORT_SYMBOL(sym, sec) \
static const char __kstrtab_##sym[] \
__attribute__((section(“__ksymtab_strings”))) \
= MODULE_SYMBOL_PREFIX#sym; \
static const struct kernel_symbol __ksymtab_##sym \
__attribute__((section(“__ksymtab” sec), unused)) \
= { (unsigned long)&sym, __kstrtab_##sym }

#define EXPORT_SYMBOL(sym) \
__EXPORT_SYMBOL(sym, “”)

[/c]

In this post, I will explain how to easy it is to compile/port C programs and makefiles designed for GCC(GNU compiler collection) can be used with ICC(Intel C Compiler)

The necessity for using ICC happened to me because gcc was generating too big object files. Ace is using ACPI-CA(http://acpica.org/) as it is ACPI driver. After compilation the ACPI library is around 7M in debug version and around 500K in non-debug version. But from http://acpica.org/download/changes.txt it seems Microsoft C compiler produce smaller code.
[shell]
Non-Debug Version:  81.2K Code, 17.0K Data,  98.2K Total
Debug Version:     155.8K Code, 49.1K Data, 204.9K Total
[/shell]

So I decided to try “Intel Compiler” as replacement for GCC. Things were easy, since icc has options which is similar to gcc.
You can get the details of portability options from icc documentation – http://www.intel.com/software/products/compilers/docs/clin/main_cls/index.htm.

I just changed my make.conf file to check the compiler in use and use appropriate options. I removed -fno-leading-underscore and –Wall. I removed –Wall because it was giving lot of warnings, we have to fix our code sometime soon. I removed -fno-leading-underscore because there is no equivalent option in icc, however icc does not adds underscores to symbols anyway.

I added –O1 option because the kernel was panicked during boot with invalid opcode exception, I believe it was because of some MMX register usage by icc. So I settled with –O1 now.
[shell]
ifeq ($(CC),gcc)
DEBUG_FLAGS= -gdwarf-2 -g3
CFLAGS+= -Wall -Wno-multichar $(DEFINES) -nostartfiles -ffreestanding -funsigned-char -fno-leading-underscore -c -fno-stack-protector $(DEBUG_FLAGS) $(CUSTOM_FLAG)
else
DEBUG_FLAGS= -gdwarf-2 -g
CFLAGS+= -O1 -Wno-multichar $(DEFINES) -nostartfiles -ffreestanding -funsigned-char -c -fno-stack-protector $(DEBUG_FLAGS) $(CUSTOM_FLAG)
endif
[/shell]

I also made some static variables in kernel/i386/gdb_stub.c to non-static because icc appends .0 to static variables but it forgets the same name when referenced in a inline assembly code in the same file. After removing the static attribute it is working fine.

Compilation time:
gcc compiler took the following time to compile Ace source code.
[shell]
real 0m51.125s
user 0m36.975s
sys 0m11.185s
[/shell]

icc compiler took the following time to compile Ace source code.
[shell]
real 1m44.366s
user 0m59.107s
sys 0m20.946s
[/shell]

Size:
Gcc produced double the size of kernel.sys produced by icc. (I used GNU linker(ld) and ar).
gcc output size:
[c]
$ ls -lh /home/samuel/Projects/Ace3/obj/
-rw-rw-r– 1 samuel samuel 372K 2008-11-22 18:17 acpi.a
-rw-rw-r– 1 samuel samuel 545K 2008-11-22 18:17 arch.a
-rwxrwxr-x 1 samuel samuel 1.3M 2008-11-22 18:17 kernel.sys
-rw-rw-r– 1 samuel samuel 62K 2008-11-22 18:17 libds.a
-rw-rw-r– 1 samuel samuel 40K 2008-11-22 18:17 libheap.a
-rw-rw-r– 1 samuel samuel 39K 2008-11-22 18:17 libstring.a
-rw-rw-r– 1 samuel samuel 9.5K 2008-11-22 18:17 libsync.a
-rw-rw-r– 1 samuel samuel 91K 2008-11-22 18:17 pic.a
-rw-rw-r– 1 samuel samuel 23K 2008-11-22 18:17 pit.a
-rw-rw-r– 1 samuel samuel 21K 2008-11-22 18:17 rtc.a
[/c]
icc output:
[c]
$ ls -lh /home/samuel/Projects/Ace3/obj/
-rw-rw-r– 1 samuel samuel 352K 2008-11-22 16:25 acpi.a
-rw-rw-r– 1 samuel samuel 230K 2008-11-22 16:24 arch.a
-rwxrwxr-x 1 samuel samuel 528K 2008-11-22 16:25 kernel.sys
-rw-rw-r– 1 samuel samuel 38K 2008-11-22 16:23 libds.a
-rw-rw-r– 1 samuel samuel 22K 2008-11-22 16:23 libheap.a
-rw-rw-r– 1 samuel samuel 21K 2008-11-22 16:23 libstring.a
-rw-rw-r– 1 samuel samuel 11K 2008-11-22 16:23 libsync.a
-rw-rw-r– 1 samuel samuel 19K 2008-11-22 16:24 pic.a
-rw-rw-r– 1 samuel samuel 8.4K 2008-11-22 16:24 pit.a
-rw-rw-r– 1 samuel samuel 13K 2008-11-22 16:24 rtc.a
[/c]

Conclusion: So it is easy to switch to icc instead of gcc.

After creating Ace bootable CD, I decided to try to make Ace bootable from network also to completely avoid creation of disk images. Network booting also helps to boot test machine (real machine) on the same network with ease.

Earlier I had grub installed (on a disk) on a test machine (real machine) with network support. Grub can get the kernel using tftp and boots the system.

Now I wanted to avoid installing grub on a disk. So I had only one option diskless boot. So I decided to use PXE(Preboot eXecution Environment).

To make PXE work, I needed a DHCP server and TFTP server. There are lot of tools available for Linux but for Windows, very very less tools available. After some internet searches, I found and downloaded perfect tools: Dual Server http://sourceforge.net/projects/dhcp-dns-server/ and TFTP Server http://sourceforge.net/projects/tftp-server/ both projects are developed and maintained by Achal Dhir. The other tftp/dhcp servers available windows doesn’t have large set of options provided by Dual Server and TFTP server.

Since I wanted to try PXE boot on emulators, I needed to create software network tap adapter. Without software tap adapter, emulated network card cant talk to the physical network. So I downloaded OpenVPN, which has tool to create tap devices from http://openvpn.net/index.php/downloads.html

If you are using real machine, you may need to download and install PXE roms from etherboot.org http://rom-o-matic.net/

To boot from network, grub should be compiled with appropriate network driver and other flags. Since grub has some problem with compiling under Windows, I used a Linux machine to compile.
cvs -z3 -d:pserver:anonymous@cvs.savannah.gnu.org:/sources/grub co grub
cd grub
./configure –-enable-diskless –-enable-pxe –-enable-rtl8139
You might want to compile in the preset menu also using the –preset option.

Now configure Dual DHCP server to provide IP address, boot file information to qemu
#qemu-ne2k-pci
[52:54:00:12:34:56]
IP_Addr=192.168.2.200
HostName=QemuBox
DNS_Server=192.168.2.10
Router=192.168.2.10
Boot_File=pxegrub-ne2k-pci
Next_Server=192.168.2.10

Then configure TFTP server for the correct tftp home folder.

Now it is time to run, Qemu. Note – Windows port of Qemu 0.9.0 has some problem with obtaining DHCP, so install Qemu 0.9.1 and run the following command, it will boot from network.

qemu -L “$QEMU_BIOS_DIR” -M pc -m 32 -no-kqemu -hdc c.img -boot n -net nic,model=ne2k_pci,macaddr=52:54:00:12:34:56,vlan=0 -net tap,vlan=0,ifname=tap0

I am able to PXE boot qemu only with NE2000 cards, for other cards it failing. PXE boot on vmware only works if I configure grub using ifconfig command. Otherwise vmware machines get assigned with some wrong gateway address. No luck to PXE boot Ace on bochs.

For booting my test machine(real machine), I setup my router (DD-WRT box) with boot-dhcp option in DNSMasq.
http://www.dd-wrt.com/phpBB2/viewtopic.php?t=4662&highlight=pxe

Last week, I decided to boot Ace using CD image rather than floppy image because booting was slow when floppy image is used in bochs.

To create bootable cd with grub, stage2_eltorito should compiled from the grub source. The mkisofs is also needed to create the image. http://smithii.com/cdrtools contains windows cygwin port of the cdrtools which contains mkisofs.

[shell]
mkdir -p $ACE_ROOT/img/iso/boot/grub
cp $ACE_ROOT/img/boot/grub/stage2_eltorito $ACE_ROOT/img/iso/boot/grub
cp $ACE_ROOT/img/boot/grub/menu.lst $ACE_ROOT/img/iso/boot/grub
cp $ACE_ROOT/obj/kernel.sys $ACE_ROOT/img/iso/

mkisofs -R -b boot/grub/stage2_eltorito -no-emul-boot -boot-load-size 4 -boot-info-table -o $ACE_ROOT/img/bootcd.iso $ACE_ROOT/img/iso
[/shell]

This image can be written to a CD using any CD burning software.