Gerenciador de Dispositivos PCI em próprio OS: Estrutura Hierárquica

Fala pessoal, Hello World!! Há pouco tempo atrás eu fiz um post falando sobre os algoritmos de ordenação em Assembly & linguagem C que programei, e falei sobre meu algoritmo predileto: O RadixSort. Pois então, neste artigo eu vou mostrar como eu utilizei este método de ordenação de forma aplicada no sistema operacional KiddieOS em Assembly.

Executável 32-bit do Sistema Operacional KiddieOS

Atualmente estou trabalhando numa aplicação KXE (Executável do KiddieOS) que se comunica com um Driver PCI via interrupção de software. No libasm.inc contém as macros que deixa a sintaxe semelhante a linguagem C e rotinas chamadas pelas Macros que vão passar argumentos para os registradores e chamar a INT 0xCE, este libasm.inc é incluído no devmgr.asm e uma coisa que não falei é que fiz uma estrutura básica inicial que contém a entrada do MAIN, tamanho da aplicação e endereço de alocação de dados, etc... E é aí que entra esta parte da estrutura - O Endereço de alocação. Achei necessário por causa das novas funções que escrevi em Assembly: Malloc() e Free(). O Malloc utiliza este endereço para reservar um espaço na memória de (A x B) bytes onde A é a quantidade de valores possíveis e B é o tamanho do tipo de cada valor (inteiro, char, etc..), desta forma criamos um Vetor dinâmico que pode alterar de tamanho durante a execução de um programa. Esta alocação de memória via Malloc é utilizado pelo algoritmo RadixSort (Veja sobre Algoritmos de ordenação após ler o artigo) para criar um vetor auxiliar além do vetor principal, filtrando cada dígito de cada índice do vetor principal que serve posteriormente como índice do vetor auxiliar.

Falha de Proteção Geral

No início, o programa devmgr.kxe estava com muitos problemas, um deles foi o erro de proteção geral, ou GPF Error que é uma falha causada por violação de acesso, e naturalmente isso ocorre em sistemas de modo protegido, quando o usuário tenta forçadamente utilizar um endereço proibido ou uma instrução que não pode ser utilizada neste modo do processador. Então pra facilitar, programei as ISRs necessárias no gerenciador das syscalls para quando o processador cair na ISR 13 do GPF, o sistema operacional se encarrega de apresentar ao usuário uma mensagem formatada e amigável sobre o erro e o endereço do erro, assim durante a depuração, o usuário poderá identificar o problema e corrigi-lo.

O problema real da Aplicação

Após a identificação e correção do erro que causava a Falha GP, havia outro problema mais sério, que não era problema de acesso e nem erro de semântica mas algo pior: Alta complexidade algorítmica... lentidão! O sistema poderia sim apresentar ao usuário informações em formato hierárquico, mas para este sistema ser possível, demandava uma grande quantidade de ciclos, de forma extremamente exagerada, que deixava o sistema extremamente lento no processamento dos dados e na apresentação de cada nome de classe e subclasse (Levava um intervalo de 1 segundo para cada Classe com suas respectivas subclasses apresentar na tela). Só pra se ter uma ideia: Um escaneamento PCI do tipo Brute Force (Brute Force Scan), ler 8 funções de cada dispositivo e 32 dispositivos de cada barramento e 256 barramentos dentro de um ciclo, que totaliza -> 256 x 32 x 8 = 65536 ciclos, digamos que dentre estes parâmetros, o número de dispositivos PCI existentes na máquina é 20, neste número existem 5 Classes repetidas, logo 20 - 5 = 15 + 1 = 16, então nós temos 16 Classes no geral, que será o valor de N, N = 16. O Algoritmo anterior teria que processar 65536 ciclos para cada classe, ou seja, 65536 x 16 = 1048576 ciclos apenas para apresentar informações em um formato de árvore de exibição, sem contar um pequeno ciclo interno em sub-vetores (Isso significa que é muito maior que 1048576 ciclos, é só uma faixa), isto porque as respectivas subclasses de cada classe não vem numa ordem sequencial quando lidas, Exemplo: um dispositivo de classe 08 pode estar na 4ª e 5ª posição, enquanto que outro dispositivo da mesma classe pode estar na 10ª e 13ª posição, como você vai apresentar apenas dispositivos da Classe 0x08 primeiro e depois todos da Classe 09, e 10, ??? Refleti bastante nesta questão, antes de projetar um algoritmo que trabalhasse exatamente para responder esta questão, sem aquela lentidão. O outro algoritmo chegava numa complexidade O(N² x K) ou O(Kn²), onde N é o número de Classes, K o número máximo de dispositivos PCI e a potência é o pequeno ciclo de comparação de classes anteriores. Agora o novo algoritmo foi reduzido a complexidade O(N + K). Ou seja, apenas 2 Loops diferentes para construir a exibição hierárquica e que tornou o sistema muito mais rápido.

Eis a solução do problema...

A minha primeira estratégia foi construir um enorme vetor de tamanho fixo para o loop fazer uma varredura e comparações, depois alterei para alocação dinâmica utilizando Malloc e depois definitivamente decidi utilizar nenhum dos dois: A estratégia definitiva foi utilizar apenas a pilha como forma de armazenamento do vetor. Em um endereço definido, o loop de 65536 ciclos consegue contabilizar a quantidade de dispositivos PCI e ainda ao mesmo tempo construir uma estrutura sequencial dos dispositivos neste endereço, esta estrutura a princípio fica desordenada, mas não temos como saber a ordem correta dos dispositivos apenas baseado nos parâmetros: barramento, dispositivo & função, o que totaliza 3 bytes aí. É preciso de +1 byte que eu nomiei de "identificador". Este identificador é um byte de ID, dividido por 2 nibbles: O Nibble menos significativo representa a "ordem" da subclasse (não o código da SubClasse) e o nibble mais significativo representa a "ordem" da Classe (não o código da Classe). Uma maneira melhor de explicar como o sistema cria o ID: A Cada nova Classe identificada pelo escaneamento, o sistema adiciona + 0x10 no maior ID armazenado e a cada nova SubClasse de uma Classe, o sistema adiciona + 0x01 no ID da última SubClasse armazenada daquela Classe. Após construir o ID do dispositivo, é mesclado este ID e os parâmetros PCI em 1 só inteiro, este inteiro será armazenado na última posição do vetor daquele último endereço salvo da pilha. Após isto, uma estruturação hierárquica desordenada foi gerada com sucesso, então o sistema imprime o número de dispositivos na tela e tudo que o algoritmo de ordenação RadixSort faz é ordenar o vetor estruturado, já por si só, após a ordenação, o próprio RadixSort cria a árvore da estrutura, pois a própria ordenação dos valores, é o que o torna uma estrutura hierárquica dos dados, por isto eu disse o termo "Estruturação Hierárquica Desordenada", pois o sistema hierárquico já estava pronto, pelo 1ª algoritmo, só bastava ordenar os valores. A apresentação dos valores só precisa de 9 ciclos (No exemplo da minha máquina virtual), cada ciclo 1 comparação, ou seja, N = 9. O 1ª algoritmo que fez a estrutura hierárquica só precisou de 65535 ciclos, cada ciclo 1 comparação, logo K = 65536. Então O(N + K). Mesmo que adicionássemos os ciclos do RadixSort, representado pela Variável S, seria uma diferença pequena, pois o RadixSort não trabalha com comparações e sim, com cálculos de dígitos, o que o torna complexidade O(N log N) e um dos algoritmos de ordenação mais eficiente.

Funcionalidades iniciais do gerenciador de dispositivos

Como vocês podem ver no código da aplicação "Devmgr.asm", foi dividido por funções chamadas via instrução CALL, a função que executa 9 ciclos para imprimir informações em formato de árvore é a "__show_hierarchical_visual" no arquivo "libdvmgr.inc", cuja responsabilidade é filtrar o ID atual e exibir diretamente o dispositivo PCI, sem um BruteForce Scan. Caso um AND do Nibble menos significativo do ID resultar em 0, significa que é uma Classe, então Get_Class_Name() é chamada retornando a String e Get_SubClass_Name() pra exibir a 1ª SubClasse da Classe atual. Caso um AND do Nibble menos significativo não resultar em 0, significa que é apenas uma SubClasse que deve ser apresentada, e a Classe correta desta SubClasse já pode ser filtrada diretamente pelos parâmetros PCI no Vetor, graças a função de estruturação __build_sequential_struct e o RadixSort ser executado anteriormente. Desta forma, podemos apresentar todos os dispositivos PCI da máquina de forma hierárquica, no entanto, seria um pouco mais complicado adaptar esta estratégia algorítmica para apresentar as Interfaces de cada SubClasse ou os Drivers instalados com seus respectivos DeviceIDs. Como pode ser visto na imagem do Shell KiddieOS, eu limitei pra apresentar apenas 5 dispositivos (ECX - 4) na tela justamente porque ainda não fiz o sistema de rolagem de tela em modo protegido, apenas em modo real e como esta aplicação está rodando em modo protegido, não seria viável voltar ao modo real só pra utilizar as funções de rolagem de tela da CLI, então é preciso construir uma função interna alternativa que seriam chamadas automaticamente pelas funções de impressão de caracteres em modo protegido, isto também será bastante útil quando for criada uma aplicação de Editor semelhante ao Vim e o Nano do Linux.

Pois é galera, esta postagem ficou um pouco grandinha mas terminando por aqui, toda esta estratégia pode ser um arcabouço até para apresentação de pastas e diretórios do sistema de arquivos ou infinitas aplicações, depende da sua criatividade. Então, se quiserem dar uma olhada nos códigos-fontes do GitHub que acabei de atualizar, sintam-se a vontade e agradeceria uma estrelinha também Rs, ficaria bastante feliz! Falow Devs, até mais!

Links de Códigos-fontes

Repositório do Gerenciador de Dispositivos e SysCalls:

https://github.com/FrancisBFTC/KiddieOS_SysCall

Repositório do Driver PCI escrito em Assembly:

https://github.com/FrancisBFTC/Sistemas-de-Drivers-em-Assembly

Aprenda a criar seu próprio sistema operacional:

https://www.youtube.com/playlist?list=PLsoiO2Be-2z8BfsSkspJfDiuKeC9-LSca

Links úteis para meus outros Artigos da DIO:

SYSCALLs 32-bit em Assembly

Sobre o Curso de criação de sistemas operacionais

Algoritmos de Ordenação em Assembly & C

#cursodsos #desenvolvendosistemasoperacionais #assembly #kiddieos #sortingmethods