Wednesday 30 March 2011

Itsy-OS Kernel: Preemptive Switcher & Memory Manager

Itsy-OS v0.1 is a small 8086 operating system kernel providing two basic services: a simple preemptive task switcher and memory management. If necessary, simple IPC and task management can be added to provide the features of a traditional microkernel.

Weighing in at about 380 bytes, Itsy should port well to tiny architectures.

Memory Control Blocks


Each block of memory is preceded by a memory control block which is 32 bytes long. The blocks of memory are arranged as a circular linked list. The first memory control block resides in segment 050h.

org 0h
; -----------------------------
; [Master Memory Control Block]
; -----------------------------

M_NEXT:dw 0             ; address of next MCB
M_LAST:dw 0             ; address of previous MCB
M_PARA:dw 0             ; size of this block in paragraphs including MCB
M_FLAG:db 0             ; flags
       db 0             ;
M_NPRO:dw 0             ; next MCB containing process, zero if not in queue
M_LPRO:dw 0             ; previous MCB containing process, or zero
M_STKP:dw 0             ; stack pointer
M_STKS:dw 0             ; stack segment

M_TIME:dw 0             ; time allocated / de-allocated
M_DATE:dw 0             ; date allocated / de-allocated
M_OWNR:dw 0             ; user number who owns this memory
M_NAME:db '          '  ; name of this memory block

; ---------------------------------------------------------------------------

; flag bits
F_FREE equ 01h          ; zero if this is free memory
F_ACTI equ 02h          ; zero if no task ready for CPU

; ---------------------------------------------------------------------------

  jmp E_INIT            ; setup kernel

; ---------------------------------------------------------------------------

; -------------------
; [Nucleus Data Area]
; -------------------

D_PCP:dw 0              ; segment of current process's MCB
D_SWEN:db 0             ; set to zero when switching disabled

Task Switcher


The task switcher is called by the timer interrupt. First it checks whether switching is disabled. If not:

  • disable switching
  • save the registers of the current task on the stack
  • save the stack pointer of the current task in it's MCB
  • find the next MCB with an available task
  • restore the new task's stack pointer and registers
  • enable switching and transfer control to the new task

; ---------------
; [Task Switcher]
; ---------------

E_SWITCHER:
; test if the switcher is enabled or disabled (indivisible test and set)
  pushf
  push cx
  xor cx,cx
  cs xchg cl,byte[D_SWEN]
  jcxz N_NOSWITCH

; save the registers of the current process
  push ax
  push dx
  push bx
  push bp
  push si
  push di
  push es
  push ds

; save the stack of the current process
  mov di,M_STKP
  cs mov ds,word[di+D_PCP-M_STKP]
  mov word[di],sp     ; M_STKP
  mov word[di+2],ss   ; M_STKS


E_SHORTCUT:

; select an active task to switch to
N_SELTASK:
  mov ds,word[di-4]        ; M_NPRO
  test byte[di-6],F_ACTI   ; M_FLAG
  jz N_SELTASK             ; is this task active?
  cs mov word[di+D_PCP-M_STKP],ds

; restore saved state of process being switched to
  mov sp,word[di]          ; M_STKP
  mov ss,word[di+2]        ; M_STKS
  pop ds
  pop es
  pop di
  pop si
  pop bp
  pop bx
  pop dx
  pop ax
  call E_ENABLE
N_NOSWITCH:
  pop cx
  popf
  iret

Deallocate Memory


Called with DS = MCB of memory to free. Deallocated memory is wiped with 0CCh.

Switching is disabled while the memory structure is being modified. If the memory being deallocated contains a process, it is removed from the process queue. If adjacent memory blocks are marked as free, the blocks are combined.

; -------------------
; [deallocate memory]
; -------------------

E_MEMDEALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di                   ; M_NEXT
  mov ax,word[di+M_NPRO]      ; see if there is entry in process queue
  test ax,ax
  jz N_NOPROC                 ; if there isn't, simply free the memory
  mov es,word[di+M_LPRO]      ; and if there is, remove it!
  es mov word[di+M_NPRO],ax
  mov bx,es
  mov es,ax
  es mov word[di+M_LPRO],bx

  mov ax,ds
  cs cmp ax,word[D_PCP]       ; check if process being killed is the current
  jnz N_NOPROC
  cs mov word[D_PCP],bx       ; if so, set last process as current

  call N_NOPROC               ; free the memory,
  mov di,M_STKP
  jmp short E_SHORTCUT        ; and then afterwards, switch to another task


N_NOPROC:
  mov bp,ds                   ; bp = first paragraph to clear
  mov bx,word[di+M_PARA]      ; bx = number of paragraphs to clear

  mov es,word[di]
  es test byte[di+M_FLAG],F_FREE        ; is next block free?
  jnz N_NNOTJOIN                        ; if not, can't join them

  es mov ax,word[di+M_PARA]             ; get size of next block
  add word[di+M_PARA],ax                ; add to size of this block
  es mov ax,word[di]                    ; move M_NEXT of next...
  mov word[di],ax                       ;  ...to M_NEXT of current
  inc bx                                ; an extra 2 paragraphs to clear
  inc bx
N_NNOTJOIN:
  and byte[di+M_FLAG],0FFh-F_FREE-F_ACTI       ; mark as free

  mov es,word[di+M_LAST]
  es test byte[di+M_FLAG],F_FREE        ; is previous block free?
  jnz N_PNOTJOIN                        ; if not, can't join them

  mov ax,word[di+M_PARA]                ; get size of this block
  es add word[di+M_PARA],ax             ; add to size of previous block
  mov ax,word[di]                       ; move M_NEXT of current...
  es mov word[di],ax                    ;  ... to M_NEXT of previous
  jmp short N_EXTRA2P
                                        ; block already marked as free
N_PNOTJOIN:
  inc bp              ; don't clear MCB
  inc bp
  dec bx
  dec bx

N_EXTRA2P:
  cld                 ; clear memory - bp=location, bx=paragraphs
  mov ax,0CCCCh       ; code for an INT3 instruction to fill memory with
  mov dx,01000h
N_CLRGO:
  mov es,bp
  sub bx,dx
  jc N_CLRFIN
  mov cx,08000h
  rep stosw
  add bp,dx
  jmp short N_CLRGO

N_CLRFIN:
  add bx,dx
  mov cl,3
  shl bx,cl
  mov cx,bx
  rep stosw

E_ENABLE:
  cs inc byte[D_SWEN] ; enable switching
  ret

Allocate Memory


Called with AX = number of paragraphs required. Returns DS = location of memory, or DS = 0 if no memory available. Switching is disabled while the memory structure is being modified. Allocation uses a simple best fit algorithm.

; -----------------
; [allocate memory]
; -----------------

E_MEMALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di
  xor dx,dx                    ; segment of current choice
  xor cx,cx                    ; left-over memory from current choice
  inc ax
  inc ax
  mov bx,050                   ; MMCB

N_MOREMEM:
  mov ds,bx
  test byte[di+M_FLAG],F_FREE  ; is the block we are looking at empty?
  jnz N_WONTFIT                ; if it isn't, move on

  mov bx,word[di+M_PARA]
  sub bx,ax                    ; check size
  jc N_WONTFIT
  jz N_EXACT                   ; perfect fit :-)

; ** KLUDGE ***
  cmp bx,3                     ; if leftover memory block smaller than 3
  jc N_WONTFIT                 ; paragraphs, it would be too small to contain
                               ; a MCB.  Maybe handle this better later

  cmp cx,bx                    ; bx= size of potential leftover memory block
  jc N_WONTFIT                 ; have we found a better fit?
  mov cx,bx
  mov dx,ds                    ; if so, then select it!
N_WONTFIT:
  mov bx,word[di]              ; M_NEXT
  cmp bx,050                   ; are we at MMCB?
  jnz N_MOREMEM

  test dx,dx
  jne N_ALLOCIT
  mov ds,dx                   ; out of memory :-(
  jmp short N_ALEXIT
N_ALLOCIT:
  mov ds,dx
  mov es,word[di]              ; M_NEXT, es= next block

  mov bx,word[di+M_PARA]       ; bx= number of paragraphs for this block
  add bx,dx                    ; bx= end of this block
  sub bx,ax                    ; bx= location of new block's MCB        

  es mov word[di+M_LAST],bx    ; point next block to new block
  mov word[di],bx              ; M_NEXT, point this block to new block
  sub word[di+M_PARA],ax       ; resize this block
  push ds
  mov ds,bx                    ; point es to new block
  pop bx

  mov word[di+M_LAST],bx       ; initialise new block's M_LAST
  mov word[di+M_PARA],ax       ; initialise new block's M_PARA
  mov word[di],es              ; initialise new block's M_NEXT

N_EXACT:
  mov byte[di+M_FLAG],F_FREE   ; mark new block as no longer free
  mov word[di+M_NPRO],di
  mov word[di+M_LPRO],di
N_ALEXIT:
  jmp short E_ENABLE

Setup


Simply sets up the timer interrupt.

E_INT1C:
  call E_SWITCHER
  db 0EAh
D_OLDINT1C:
  dw 0,0

; ---------------------------------------------------------------------------

E_INIT:
  push cs
  pop es
  xor ax,ax
  mov ds,ax
  mov si,01Ch*4
  mov di,D_OLDINT1C
  cld
  push si
  movsw
  movsw
  pop di
  cli
  push ds
  pop es
  mov ax,050h
  stosw
  mov ax,E_INT1C
  stosw
  sti
; ...

Thursday 17 March 2011

Alternatives to Windows Notepad for Programmers

When I upgraded to Windows 7 I was horrified to discover the text editor I've been using for years no longer works. After suffering Windows Notepad for a few days I set out on a quest to discover the perfect replacement.

My search criteria is pretty basic:

  • can be installed on a memory stick
  • works with UNIX / DOS end-of-line
  • supports syntax highlighting
  • the ability to edit multiple files
  • supports regular expression search
  • requires less than 10MB disk space

After testing a number of free programmer's editors I discovered several which meet (or almost meet) the requirements:


screenshot of ConTEXT programmer's text editor
ConTEXT is a free programmer's text editor. It boasts a number of useful features include the ability to export code to HTML.

(The thumbnail links to a 800×560px screenshot.)

screenshot of Crimson programmer's text editor
Crimson is a source code editor to replace Windows Notepad. Unfortunately the default colour scheme for syntax highlighting doesn't really distinguish between text, delimiters and constants.

screenshot of gedit programmer's text editor
gedit is the text editor from the GNOME desktop enviroment and is also available for Windows. Unfortunately the standard package lacks regex search and it's a heavyweight, weighing in at 65MB+.

screenshot of jEdit programmer's text editor
jEdit is a Java programmer's text editor and has an active community of developers. Hundreds of plugins are available to add a wide range of features. jEdit is another heavyweight, consuming 25MB+ of diskspace.

screenshot of Notepad++ programmer's text editor
Notepad++ is a replacement for Windows Notepad. Features include code folding and support for numerous plugins developed by Notepad++'s active community.

screenshot of Notepad2 programmer's text editor
Notepad2 is a replacement for Windows Notepad that only installs two files. It features a semi-transparent mode allowing users to keep an eye on other programs while editing full screen. Unfortunately Notepad2 can only edit one file at once.

screenshot of Programmer's Notepad text editor
Programmer's Notepad is a programmer's editor with features including code folding, exporting code to HTML and Python scripting. Programmer's Notepad has an active user community.

screenshot of PSPad programmer's text editor
PSPad is a free programmer's editor. The font selector only shows fixed width fonts which is handy, but I'd like to have the option to use a proportional font. PSPad has a feature to export code to HTML. Requires just over 14MB of disk space.

screenshot of SciTE programmer's text editor
SciTE is the demo for the free Scintilla code editing component (used by several editors listed here) and is available as a single file installation. Supports code folding and exporting code to HTML. Unfortunately changing the settings requires the user to poke around in SciTE's config files.


In the end I've settled for Programmer's Notepad. Which editor are you using and what features do you consider essential? :-)

Sunday 13 March 2011

Efficiency in Forth

I'm busy implementing my own Forth at the moment and it's taking a little longer than anticipated. Each Forth word is a puzzle in itself:

  • What's the least number of words needed to write it?
  • What's the most efficient implementation?

For example, take a look at Implementing MIN in Forth without Conditional Code. The smallest version of MIN is 2 words shorter than eForth's MIN.

Even words with a trivial implementation can pose an interesting problem. For example which of the following is most efficient:

Jones Forth TUCK


: TUCK DUP -ROT ;

Alternative TUCK


: TUCK SWAP OVER ;

If DUP, -ROT, SWAP and OVER are all primitive, the alternative implementation will execute two fewer instructions on an 80x86 Forth. However, -ROT is often implemented in Forth which would cause the Jones Forth TUCK to be substantially slower. Here's a typical implementation of -ROT:

: -ROT SWAP >R SWAP R> ;

If you can think of an alternative two word implementation of TUCK or four word implementation of -ROT, please let me know. :-)