Monday, December 26, 2005

Implementación de colas ligadas en Toro

Implementación de colas ligadas en Toro :

Las colas ligadas son un método eficaz para mantener agrupados una cantidad ilimitada de elementos . En Toro son utilizadas para agrupar los procesos , los timers , los superbloques , los inodos , los buffers , etc. , se le ha dado gran cantida de uso .

Podemos clasificarlas en dos tipo : simplemente ligadas o doblemente ligadas .

Por lo general las estructuras que se encuentran en una cola simplemente ligada posee solo un campo que apunta a la siguiente estructura y la ultima de la cola posee este campo a un puntero nulo , es decir solo pueden ser recorridas en un solo sentido .
A diferencia de estas , las doblemente ligadas posee dos campos una punteando a la siguiente estructura y otra a la anterior , pudiéndose así recorrerla en ambos sentidos y de manera cíclica .

La principal diferencia es para què van a ser utilizada . Por un lado las simplemente ligadas posee un campo menos , es decir ocupan menos memoria , pero si en la cola se están agregando y quitando elementos continuamente se consume mucha cpu , porque por cada elemento que debo quitar debo recorrer toda la cola para encontrar el anterior! .
Este problema se soluciona creando un nuevo campo apuntando al elemento anterior , así surgen las doblemente ligadas .
Es por eso que las colas que mantiene a los procesos , inodos , timers ,etc. , son colas doblemente ligadas , mientras que las colas que mantiene a los buffers que deben ser escritos a disco se encuentran en colas simplemente ligadas , cada buffer es agregado al comienzo y cuando deben ser quitados por la llamada sync() , se recorre la lista desde el inicio sacando de a uno todos .

Todo muy lindo , pero el hecho de que sean tan utilizadas hace necesarios procedimiento muy rápidos y eficientes , y este es el motivo del articulo .
Lo que se trato de crear fue procedimientos generales para el tratamiento de colas ligadas , tal como lo hace linux , pero en freepascal .

Todo el código del manejo de colas ligadas se encuentra en el archivo Include/Head/list.h

Este como se ve no es una unidad sino solo un archivo que debe ser incluido en la unidad luego de IMPLEMENTATION

Para que funcione deben ser declarados en la unidad cuatro símbolos ,de la manera tradicional , {$DEFINE Use_Tail} , estos son :

Use_Tail : le indica al compilador que el código de manejo de las lista debe ser incluido

nodo_struct : Debe contener la estructura de los elementos dentro de la cola , por ejemplo para una cola ligada de procesos valdría :

{$DEFINE nodo_struct = p_tarea_struc}

Siempre se considera a nodo_struct como un puntero .



nodo_tail : Puntea al elemento cabecera de la lista , puede estar definido o no .

next_nodo y prev_nodo : Estas estructuras poseen los campo dentro de los elementos de la lista que puntean al siguiente elemento y al anterior , por ejemplo para el caso de cola de procesos , estos valdrían :

{$DEFINE next_nodo = next_tarea }
{$DEFINE prev_nodo = prev_tarea}


El procedimiento para encolar un elemento , si se ha definido nodo_tail :

procedure Push_Node(Nodo : nodo_struct) ; inline ;

o en el caso de que no se haya definido nodo_tail :

procedure Push_Node(Nodo : nodo_struct;var Nodo_Tail : nodo_struct);inline;

La diferencia de que se defina o no nodo_tail , es la capacidad de trabajar en una unidad con mas de una cola ligada , puesto que de lo contrario se definiría un único valor para el símbolo nodo_tail , con esto se especifica el nodo cabecera de la cola en cada llamada .

Siempre el elemento es agregado al comienzo de la cola .

Ojo! nodo_tail no es una estructura sino solo un puntero al primer elemento de la cola .



Para quitar un elemento sucede lo mismo :

El procedimiento para quitar un elemento , si se ha definido nodo_tail :

procedure Pop_Node(Nodo : nodo_struct );inline;

o en el caso de que no se haya definido nodo_tail :

procedure Pop_Node(Nodo : nodo_struct;var Nodo_tail : nodo_struct);inline;

Como se ve todos los procedimiento son declarados como inline para acelerar su ejecución

Para hacer un poco mas “entendible” el código suelo definir otro símbolo que oculte a estos procedimientos :

{$DEFINE push_buffer = push_node }
{$DEFINE pop_buffer = pop_node }

Lo bueno de esto que definiendo un par de símbolos ya tenes todo el código para la manipulación de listas ligadas sin importar las estructuras , campos , etc .


Para el caso de colas simplemente ligadas , se debe definir el símbolo Use_Simple_Tail
para comenzar a trabajar con ella .
Igual que en el caso de las doblemente ligadas se cuenta con los procedimientos :

para agregar un elemento :

procedure Push_Snode (Nodo , sNodo_Tail : snode_struct);inline;

y para quitar un elemento :

procedure Pop_Snode (Nodo,sNodo_Tail : snode_struct);inline;

Ahora los símbolos nodo_struct y nodo_tail pasan a llamarse snode_tail y snode_struct respectivamente


Espero que les haya servido este pequeño articulo .
Una saludo



Matias E. Vara
Toro.sourceforge.net
matiasvara@yahoo.com

Sunday, November 06, 2005

Generando un kernel con FreePascal

Bueno tal vez el titulo no sea muy descriptivo pero básicamente lo que tratare de explicar es como generar un ejecutable en freepascal sin que este utilice llamadas al sistema , llevando obviamente a la caída del sistema .

A la hora de comenzar a escribir un S.O. la principal duda q se me planteo fue que compilador iba a utilizar . Elegí Freepascal , porque además de gustarme el lenguaje me era fácil portarlo puesto que es independiente del S.O. sobre el cual corra , esto no significa que no utilice llamadas al sistema sino que posee un capa de abstracción de llamadas primitivas las cuales son adaptadas al S.O. sobre el cual corra , es por eso que al compilador no le interesa el S.O. sobre el que se ejecuta .

En el caso de la versión 1.0.6 de FP utilizando el extensor go32v2 el tema es bastante fácil . Cuando se utilizan procedimientos y funciones dependientes del S.O. como por ejemplo writeln , write , read ,etc . ( no así sizeof () , len() , etc . ) el compilador enlazada nuestro ejecutable al archivo objeto donde se encuentran estas llamadas , básicamente lo que se hizo en Toro es capturar estas llamadas , creando el archivo Lib/fpclib/fpclib.pas con estas llamadas y linkeandolo junto con todo el kernel .
Por ejemplo :

llamada muy utilizada para el tratamiento de strings

procedure int_strconcat(s1,s2:pointer);[public,alias:'FPC_SHORTSTR_CONCAT'];
var
s1l, s2l : byte;
type
pstring = ^string;
begin
if (s1=nil) or (s2=nil) then
exit;
s1l:=length(pstring(s1)^);
s2l:=length(pstring(s2)^);
if s1l+s2l>255 then
s1l:=255-s2l;
move(pstring(s1)^[1],pstring(s2)^[s2l+1],s1l);
pstring(s2)^[0]:=chr(s1l+s2l);
end;


También se podría haber linkeado directamente el archivo objeto de FP donde se encontrase la llamada , pero haría crecer el kernel enormemente!!! .


En las unidades mientras no se utilicen llamadas que depende del S.O. o que provengan de unidades externas no hay problema , el compilador no realizara llamadas al sistema .
La cosa cambia con un ejecutable . Cuando se compila el archivo kernel/kernel.pas , este ya no es una unidad sino que es un programa , para volverlo “limpio” de llamadas al sistema lo que se hace es simplemente quitarlas del código assembler :

Extracto del archivo /kernel/Makefile .

$(FPC) $(FPC_FLAGS) kernel.pas

$(GREP) -iv "INIT$$SYSTEM" kernel.s > kernel.tmq
$(GREP) -iv "FPC_INITIALIZEUNITS" kernel.tmq > kernel.tmp
$(GREP) -iv "FPC_DO_EXIT" kernel.tmp > kernel.kkk
$(GREP) -iv "OBJPAS" kernel.kkk > kernel.s


Estas son los símbolos que deben ser retirados y que llevan a la caída del kernel cuando bootea ( a la caída me refiero a una excepción , muy común la 13 )


Una vez compilados todos los archivos objetos son linkeados con ld , puede pasar que tire errores de símbolos desconocidos , es decir hay funciones o procedimiento que están llamando a otros que no se encuentran en los archivos objetos linkeados . Lo mas posible es que haya errores en el tipeado de nombres , o que el head de la función no haya sido declara como publica . Si todo esto no es correcto habría que ver si es una llamada a librerías del compilador , si es así , se debería buscar el procedimiento o función en el código de FP , copiarlo al archivo lib/fpclib/fpclib.pas y declararlo como publico con el alias devuelto como error en ld .



FPC 2.0.0 sobre win32 y linux :

Sobre estas plataformas la cosa no me resulto fácil , lamento informa que no he llegado a una versión booteable del kernel de toro compilado sobre win32 , es por eso que las distribuciones se harán por ahora para go32v2 y para linux , o tal ves solo para linux puesto que se dejaron producir versiones de FPC para DOS .

Para el caso de FPC 2.0.0 sobre linux , al compilar el archivo kernel/kernel.pas solo se quita el símbolo :

$(GREP) -i 'FPC_INITIALIZEUNITS' -v kernel.s > kernel.q


Para el caso de llamadas al sistema lo que opte hacer ahora fue directamente el linkeo de los archivos objeto que contienen las llamadas utilizadas por el compilador estas son :

/usr/lib/fpc/2.0.0/units/i386-linux/rtl/prt0.o
/usr/lib/fpc/2.0.0/units/i386-linux/rtl/system.o
/usr/lib/fpc/2.0.0/units/i386-linux/rtl/objpas.o

Lo que hace es incrementar enormemente el archivo toro-1.1 , que posee casi el triple del mismo archivo generado con el FPC para DOS .


La unidad Lib/fpclib/fpclib.pas deja de utilizarse para el FPC sobre linux . Por supuesto , posiblemente dentro de estos archivos objetos hayan funciones que realicen llamadas al sistema , pero no causaran problemas mientras no se las llame :) .




Espero que este articulo les sirva para saber como se puede generar un ejecutable totalmente booteable (por ejemplo un elf para grub o un binario para un booteador propio) sin que posibles llamadas del compilador lleven a excepciones no deseadas .

Aclaración! si el elf generado va a ser utilizado por un booteador como grub tiene que ser creado bajo la norma multiboot sino grub no podrá levantarlo , toro fue creado bajo ese Standard , en próximos documentos describiré como hacer un elf que pueda ser levantado con grub .



Matias Vara
Toro.sourceforge.net
matiasvara@yahoo.com

Tuesday, November 01, 2005

Compilando el kernel de Toro – 1.1

Este procedimiento es aplicable a partir de la versión 1.1 de Toro .


Una vez obtenido el paquete zip de la versión de Toro debe ser extraído sobre un directorio cualquiera o bien sobre un disket sobre el cual previamente se debe haber instalado grub . En el raíz del disket deben figurar tres directorio : usr , bin y boot , para que grub pueda bootear .

Para comenzar la compilación se debe modificar el archivo /usr/toro-1.1/make.rules completando las variables de make con sus ubicaciones correctas .

El siguiente paso es hacer un make sobre el directorio /usr/toro-1.1/ y listo! , si todo resulta bien será generado el archivo elf ejecutable toro-1.1 y se moverá al directorio /boot para ser levantado por grub durante el booteo .

También deberán ser compiladas la utilidades que se encuentran en el directorio /usr/tools realizando un make en cada directorio y los ejecutables serán movidos al directorio /bin donde se encuentran todos los binarios .

Una vez tenido compilado correctamente Toro sobre el disket podrá ser booteado bien sobre un emulador o directamente sobre la maquina .

También pude ser compilado sobre linux cualquiera sea el booteador instalado mientras levante el elf de Toro , pero de todos modos en este caso también Toro buscara la shell en la disketera .

En próximas versión Toro podrá bootear sobre discos duros o cualquier dispositivo siempre y cuando tenga los drivers requeridos .


Matias E. Vara
Toro.sourceforge.net
matiasvara@yahoo.com

Nuevos posteos

Ire posteando los documentos que se encontraban en papers y otros docuementos de como programar sobre , etc . Espero que les sea interesante . Un sa ludo Matias Vara .

Tuesday, October 11, 2005

Trabajando en la version 1.1.1

Estoy trabajando en volver alta mente estable la version 1.1 , esta nueva version no incluira nuevas implementacion solo sera muy estable . Espero que me comenten los bug que encontraron en la version 1.1 y asi podre depurarla bien .
Un saludo Matias Vara .

Pd : Ahora puede postear cualquiera asi espero sus comentarios .

Thursday, September 15, 2005

Bug en el paquete de la version 1.1

He encontrado un error en el codigo de la version 1.1 , este se encuentra en el archivo toro-1.1/filesystem/exec.pas , el error se encuentra en la declaracion de la funcion Sys_Exec , esta deveria ser : [public , alias : 'SYS_EXEC'] , en vez de 'SYS_EXE' , Esta se encuentra tanto en el paquete para go32v2 como para el de linux .
Un saludo Matias Vara .

Friday, August 19, 2005

Toro compilado sobre fpc-linux

Ya esta disponible el paquete .zip te toro-1.1 para ser compilado sobre la utlima version de fpc sobre linux .
Un saludo Matias Vara .

Monday, August 01, 2005

Recien salido del horno Toro 1.1!!

Despues de mucho trabajo ya se encuentra la version 1.1 de Toro . Esta fue distribuda de dos formas un paquete zip con todo el codigo y listo para ser compilado; y la imagen de un disket de 3 1/2 listo para ser ejecutado . Bueno espero que la pruben y me den sus comentarios . Esta version fue compilada con la version de FPC para go32v2 , puesto que me esta trayendo dolor de cabeza compilarlo con la version para win32 .
Un saludo Matias Vara .

Saturday, July 16, 2005

Implementaciones de Toro 1.1

Aunque la version de Toro 1.1 todavia no ha sido publicada el principal motivo es la gran cantidad de cambios que esta presenta , a continuacion se citaran algunas :

- Implementacion del VFS .
- Se deja de utilizar el torofs para implementar driver para fat12fs .
- Soporte multiboot , toro es booteable sobre grub .
- Reescritura de la unidad dma.pas .Creacion de una pila con paginas para dma .
- Reserva de areas de memoria para io con dispositivos hard.
- Reescritura de la unidad scheduler.pas , Implementacion de los algoritmos RR y FIFO en tiempo real .
- Reescritura de la unidad signal.pas
Y algunas cosas mas

Es por eso que mencionar una fecha es imposible .
Un saludo Matias Vara .