A simple binary tree program -- in assembler

I believe every programmer must learn assembly programming. It brings the programmer and the machine closer and strengthens the bond between them. I learned the term GIGO (Garbage In Garbage Out) when I got first introduced to computer programming. Nothing has changed since. The languages and their environments have become better beyond doubt. Still, a computer and its resources are as good as its programmer. Assembly language makes you understand how the machine is working beyond all that glittery higher level languages. If you are a system programmer, learning assembly becomes a must because there are things that C can't handle. I will leave more discussion on "Why learning assembly is important" for later post. Every new architecture that I learn, I learn its assembler first. When I got first introduced to MIPS, I learned its assembly language. Below is a program that I wrote to achieve that.     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Handling out of memory (OOM) in embedded systems without swap

Background Swap is a logical and slow extension of physical RAM. Whenever the system runs out of the physical RAM, the Linux kernel writes the least used data from RAM to swap in turn freeing up some RAM. Typically, swap is setup on a separate dedicated partition on secondary storage or a separate storage itself. Sometimes, specially created files on an existing filesystem are also used as swap. A lot of embedded systems use NAND flashes or SSDs as their secondary storage drives. These devices are typically divided in fixed size blocks. The blocks needs to be erased before they can be written to again. These devices don’t have mechanical parts in them which fails them. Its their write/erase or program/erase cycles that age them out. The write/erase cycles are limited on these devices which define their age. This property makes them unsuitable to be used as a swap device. The Problem Sometime ago, I faced an out of memory problem on a project I was working o

MIPS Bootstrapping

Bootstrapping is the process of taking a CPU just out of reset, fetching and executing instructions serially, to a more complex running environment. The program that does that is called a "Boot loader" or "Boot strap code" or simply "Boot code". First Instruction Fetch When power is applied to a processor and it comes out of reset, it fetches its first instruction from an address that is hardwired. This address is known as the " Boot Vector " or the " Reset Vector ". The MIPS processors' boot vector is located at physical address 0x1FC00000. The MIPS processors have MMU enabled as soon as they are powered on. The MIPS core thus presents a virtual address of 0xBFC00000. The MMU translates this address to physical address of 0x1FC00000, the boot vector. This translation again is hardwired. Typically, a boot device is present at this address and responds to the read request of the processor2. See Firgure 1.  The offset 0 of bootstr

MIPS Virtualization: VCPU Address Map

Xvisor sees and works on the actual address map as defined by the MIPS architecure. But for the virtual CPUs (VCPUs) the address space is different. The VCPU running the guest OS sees the KSEG0 (Mapped cached region) starting from 0x00000000. This is where the RAM for the VCPU is mapped. When VCPU is in Kernel Mode or its EXL bit is set, the 2GB region starting from 0x00000000 pretends to be the region enclosed between addresses 0x80000000 - 0xFFFFFFFF on an actual MIPS CPU. When not running in kernel mode, this 2GB region is the regular USEG0. When a VCPU starts, its EXL bit is set and its essentially running in Kernel mode. So USEG0 of CPU is presented as usual kernel mode segments by the hypervisor. Since in this mode, 512 MB region starting at 0x20000000 becomes KSEG1 (mapped, uncached), the VCPU starts running at virtual address 0x3FC00000 (i.e. it becomes the start_pc of VCPU).This is the region marked as "ROM" region under guest in DTS file. The physical address ma

Atomthreads on MIPS architecture

Atomthread's port to MIPS architecture is complete. A few of the test cases are working fine. Some of them need to be fixed. Working on them. The source can be pulled from here . Its upto Kelvin now when he wants to pull in the changes. Since this is new port to a 32-bit architecture, there are some changes in the core kernel code itself. Hopefully, MIPS will get merged soon. Once I am done with validating and fixing all the test cases, I can go back to the reason I started this port -- my hypervisor. I have not been working on it for one and a half week now. Last one and a half week, I was busy with porting atomthreads to MIPS. I started this port because for testing the hypervisor, I wanted a small OS that doesn't play with MMU much. My first target is to test the instruction emulation framework for which Linux would be too heavy. Hope I will get back to hypervisor soon.

MIPS: non-virtualizable architecture (Part 1)

MIPS is a wonderful architecture. But when it was design virtualization wasn't much in the air. As a result, this architecture isn't compleletly virtualizable. It isn't as notorious as x86. One requirement for virtualization is the access priviledges to syste registers. MIPS does provide this. All system registers are in CP0. Any access from user space will falt. Modification access to TLBs will also fault. Then what is the problem? The problem is with the way virtual address space is laid out. For 32 bit architecture 4 GB virtual address space is available. MIPS specification reserve upper 2 GB for kernel/supervisor mode. Any access to 3rd GB in kernel mode will go untranslated by MMU. The last 4th GB will go via MMU but is only usable in kernel mode. For running a guest, only first 2 GB is available. Both guest and its userspace programs can only have 2GB of virtual address space. Linux assumes many things about address space layout. It is linked in kseg0. Kmap a

Making of Hyperthreads

I have been working on a fun project where I am trying to virtualize a MIPS machine. For a QEMU emulated NE2000 based network device and for couple of system daemons, I needed a light threaded framework. While the earlier design was that anything in hypervisor context was run on CPU and thus was completely serialized. So we decided on doing something differently here. We created a virtual CPU and named it hypercore. This virtual CPU is supposed to run anything in context of hypervisor. This virtual CPU, whenever scheduled, always works in kernel mode. The idea was simple, anything of _maintenance_ sort was scheduled later on that hypercore. I then went on implementing the threading mechanism. Its very similar to what is know as kernel threads in Linux(R) world. There is one function which the thread is supposed to execute. Threads have a lifetime: they are created, run, paused, run again and then finally destroyed. Initial implementation was non-preemtible. This means that threa