kindman.org

I’m working on a library for plotting graphs; check it out in the page jsPlot.

jsPlot is a JavaScript library for plotting graphs.
It plots graphs into HTML pages, using jQuery and CSS2 (no canvas).

jsPlot Example

This morning Gilson and I were talking about the structure of disk’s partition table/master boot record (mbr)/boot loaders.
After reading a bit about it [1] [2], we learned where the boot loader code goes in, and decided to change that code to do something else – to print ‘Hello World’, of course!
Maluta was around at the moment and suggested me to post about it. Here it goes :-)

In this post I detail assembly examples (using NASM [3]) printing text on boot, note some points on mbr and testing with QEMU [4].

The Boot Process

When switched on or reset, an x86 processor executes instructions at address FFFFh:0000h.
In IBM PC compatibles, this address is mapped to a ROM chip that contains the computer’s BIOS code.

After tests and initializations, the BIOS executes the actual boot loading, performing (among other things) the following steps:

1. Choose boot-device (setup-configured priority)
2. Check for boot-device signature (the value 0xAA55 in the last 2 bytes of device’s first sector)
3. Load the first sector (or boot sector) of boot-device into RAM (at address 0000:7C00) and initiate its execution

Testing with QEMU

To test the examples, the only thing needed is a virtual disk – a disk image file.
Actually, the only thing needed is it’s first sector; a 512-byte image file.

One way is to create the image file by using dd:

dd if=/dev/zero of=disk.img bs=512 count=1

The file is really small, tough.
It is possible to create such a file from the assembler too, allocating bytes in the code so that it end up with a 512-byte file.

Actually the latter is better in this case, as it also provides a simple way to insert the boot-device signature in the image file.

The assembly code can be assembled with:
nasm example.asm -o disk.img

Then launch QEMU using the image file as primary hard disk.

qemu -hda disk.img

Examples

The examples use the interrupts [5] [6] 10h (Video BIOS Services) and 16h (Keyboard BIOS Services), respectively used to write a single character to the video screen and read a single character from the keyboard (actually used to pause the program).

In the 2 first examples, for legibility’s sake, the code for generating a 512-byte file and the boot signature will be omitted; that code is presented in the 3rd example.

• Printing a single character (‘H‘)

; Print Character ('H')
mov		ah, 0Eh
mov		al, 'H'
int		10h
 
; Read Character
mov		ah, 00h
int		16h

QEMU Output

Booting from Hard Disk...
H


• Printing 10 characters (‘ABCDEFGHIJ‘) in a loop

start:	mov	cx, 0Ah			; Loop Counter: 10 (0Ah) times
 
	mov	ah, 0Eh			; Set 'int 10h' Operation
	mov	al, 'A'			; Start with character 'A'
 
loop:	int	10h			; Print character
	inc	al			; Change to next character
 
	dec	cx			; Check Loop End
	jnz	loop			; Loop Again
 
done:	mov	ah, 00h			; Read Character
	int	16h

QEMU Output

Booting from Hard Disk...
ABCDEFGHIJ


• Generating a 512-byte file with boot signature

; These lines go after your code.
 
zero		times	512 -($-$$) -2	db 0	; zero remaining-to-512 bytes, except the last 2 bytes.
signature	dw	0xAA55			; last 2 bytes: boot signature

Try opening disk.img in an hexadecimal editor. ;-)

• Printing Hello World

This is the final example, based on [7]. It is a bit more complex, as it is complete and 3 new features were used:

1. Zero-ended String
2. Pointers
3. Effective Addresses

To ease understanding the code, it is commented with a C-style algorithm.

org	7C00h					; needed as using effective addresses (lea)
start:	mov	ah, 0Eh				; operation op = PRINT_CHAR;
 
	lea	si, [message]			; for (char *currentChar = &message[0]; ...
						; {
print:	mov	al, [si]			;	char buffer = *currentChar;
 
	cmp	al, 0				; ... *currentChar != 0; ...
	jz	done
 
	int	10h				; 	executeOperation(VIDEO, op, buffer);
						; }
 
	inc	si				; ... currentChar++)
	jmp 	print
 
done:	mov	ah, 00h				; op = READ_CHAR;
	int	16h				; executeOperation(KEYBOARD, op, NULL)
 
message		db	'Hello World!', 0	; char message[] = "Hello World!"
zero		times	512 -($-$$) -2	db 0	; char empty[512 - bytesUntilHere() - 2] = 0;
signature	dw	0xAA55			; char signature[2] = 0xAA55;

QEMU Output

Booting from Hard Disk...
Hello World!


Related Errors

• Image file smaller than 512-byte

QEMU Output

Booting from Hard Disk...
Boot failed: could not read the boot disk


Reason
The disk need at least one complete sector, and that is 512 bytes.

• Image file without boot signature

QEMU Output

Booting from Hard Disk...
Boot failed: not a bootable disk


Reason
The BIOS checks for the boot signature.

Special Thanks

• Gilson, for the chatting
• John, for joining me in this ‘assembly day’
• Maluta, for the post suggestion
• Vantuil, for assembly classes that made Hello World really seem easy like Hello Worlds (lol..)

Ending

I hope this post may be useful for you.
Until next post. ;-)

References

[1] Wikipedia; Master Boot Record
[2] Wikibooks; x86 Assembly/Bootloaders
[3] NASM: The Netwide Assembler
[4] QEMU; About
[5] Interrupt Services DOS, BIOS, EMS und Mouse
[6] Interrupt 10h
[7] Make your own operating system with x86 assembly (part 1)

Some excerpts:

1940s – Various “computers” are “programmed” using direct wiring and switches. Engineers do this in order to avoid the tabs vs spaces debate.

1964 – John Kemeny and Thomas Kurtz create BASIC, an unstructured programming language for non-computer scientists.

1965 – Kemeny and Kurtz go to 1964.

1972 – Dennis Ritchie invents a powerful gun that shoots both forward and backward simultaneously. Not satisfied with the number of deaths and permanent maimings from that invention he invents C and Unix.

1995 – Brendan Eich reads up on every mistake ever made in designing a programming language, invents a few more, and creates LiveScript. Later, in an effort to cash in on the popularity of Java the language is renamed JavaScript.

Original post, via One Div Zero.
Recommended by my great friend Arsinoé Wilche. ;-)

Last post I mentioned the topic distributed systems was involved in my new project.
Now here it goes.

After setting up a small (16-machine) cluster at UNIFEI (will post about it soon) for academic experiments, the time has come for running stuff in it.
Since manually submitting and verifying jobs is very inefficient (tedious, sluggish and fail-prone), a job scheduler was required.

There are a many tools for cluster management (special thanks to Walbon) featuring job schedulers, but all too sophisticated for this application.
For this reason and 2 more, I decided to create the job scheduler. The other 2 reasons?

• It is a not a that-difficult task
• I’m a C programmer, and as so I like to recreate everything.. (lol)
• It would be so much fun! (Ok. This would be a third reason.. but actually it is emotion. ;-)

It took between 16 and 20 hours to design, implement and bugfix (see Important in Scheduler).

Design

• Dispatch a job (shell command) to an available node (using blocking-semantics)
• Only shell script (ssh, named pipes)
• Monitor nodes’ current activity (start time, job)

Usage

# Launch Scheduler
$ cd scheduler/
$ mkfifo jobs nodes
$ ./sched.sh
 
# Add nodes to the node pipe
$ echo "10.0.0.1" > nodes &
$ echo "10.0.0.2" > nodes &
 
# Add jobs to the job pipe
$ echo "process /folder/data.txt" > jobs &
$ echo "make -j9" > jobs &
 
# Watch the scheduler :-)

Implementation

• Dispatcher
  

#!/bin/bash
 
# dispatch.sh
#
# This is a job dispatcher to network nodes.
#
# (C) Copyright 2010, Mauricio Faria de Oliveira
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License version 2
# as published by the Free Software Foundation;
 
# Variables
node_pipe="nodes"
 
# Parameters
node="$1"
shift
job="$@"
 
# Checks
#	1. Parameters.
if [ "$node" == "" || "$job" == "" ]; then
    echo "Usage: $0 node job"
    exit 1;
fi
 
# Log
echo ".. (dispatch) node '$node': '$job'"
 
# Dispatch job to node via ssh
ssh "$node" "$job" > /dev/null
 
# Put node back into nodes named pipe
echo "$node" > "$node_pipe"

• Scheduler

#!/bin/bash
 
# sched.sh
#
# This is a 2-fifo-blocking job-scheduler to network nodes.
#
# (C) Copyright 2010, Mauricio Faria de Oliveira
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License version 2
# as published by the Free Software Foundation;
 
# Variables
job_pipe="jobs"
node_pipe="nodes"
dispatcher="./dispatch.sh"
 
# Checks
#	1. Check if named pipes exist.
 
if [ ! -p "$job_pipe" -o \
     ! -p "$node_pipe" ];
then
    echo "Check for the fifos 'jobs' and 'nodes' (mkfifo jobs; mkfifo nodes)"
    exit 1;
fi
 
# Algorithm
#
#	1. For each available job ('jobs' named pipe, blocking),
#	2. For an available node ('nodes' named pipe, blocking),
#	3. Dispatch job to node (asynchronously).
#
# Important
#
#	1. The named pipes are NOT guaranteed to be 'fifo'.
#		Jobs and nodes are added/return asynchronously.
#		Only the blocking behavior is guaranteed.
#
#	2. There is no way to remove a single line from a named pipe, [is it?]
#		Then:
#		1. All lines are removed,
#		2. First line is used,
#		3. Other lines are put back (asynchronously).
#
#	3. If the 'cat <> jobs' hangs for even a little while
#		jobs in this little while are lost. [why?]
#		So things are asynchronous inside this loop.
#
#	4. Never use >> (append) asynchronously with named pipes.
#		It _seems_ append on pipes works as follows:
#		1. Buffer contents
#		2. Add new stuff to buffer
#		3. Overwrite contents with buffer
#
#		If something is removed (i.e. 'cat') between steps 1 and 3,
#		it will be inserted back on step 3, due to content buffering.
#
###############################################################################
# Code                                                                        #
###############################################################################
 
#	1.	For each available job ('jobs' named pipe, blocking),
cat <> "$job_pipe" | while read job; do
 
    echo
    echo "(job): $job"
 
    # 2. For an available node ('nodes' named pipe, blocking),
 
    # 2.1. All lines are removed,
    linecount=0
    cat "$node_pipe" | while read node; do
        echo -n ".. (node): $node (#${linecount}) "
 
        # 2.2. First line is used,
        if [ "$linecount" == "0" ]; then
 
            # 3. Dispatch job to node (asynchronously).
            echo "(dispatch)"
            $dispatcher $node $job &
 
        # 2.3. Other lines are put back.
        else
            echo "(put back)"
            echo "$node" > nodes &
        fi
 
        linecount=$(($linecount + 1))
 
    done
 
    echo
 
done

• Monitor
  Scheduled for a next post. ;-)

Will be back soon!

If we think of the Spirit as software and the Body as hardware,
it’s clear in Spiritism that God makes portable software.