Experimentos para testar os limites do sistema

Os limites do sistema podem ser levantados utilizando a função ulimit. Basta digitar ulimit para verificar os parâmetros que podem ser passados e então encontrar o valor que o sistema limita.
Os experimentos criados são para testar o quanto esses valores são seguidos, para isso foram criados alguns programas para essa análise. É importante ressaltar que os programas descritos podem trazer instabilidade para o sistema, por isso optou-se por realizar os testes numa máquina de testes (máquina virtual criada com o VirtualBox da Sun) com 512 MB de memória física.

Quantos processos podem ser criados?
Para este teste, utilizou-se a chamda fork em um loop infinito, que termina com o lançamento de uma exceção quando mais nenhum fork pode ser chamado.

#include <stdio.h>
#include <stdlib.h>

int main(){
int i=0;
while(fork()>0){
i++;
}
FILE* arquivo;
arquivo = fopen("registro","w+");
fprintf(arquivo, "Processo: %d\n", i);
fclose(arquivo);
sleep();
}

A saída para a execução deste programa foi:

Processo: 7077

O resultado foi obtido do arquivo registro após reiniciar o computador, uma vez que a execução do programa causou o travamento do computador. E o número indica, portanto, aproximadamente o número máximo de processos que podem ser criados.

Qual é o maior tamanho de processo?

$ ulimit -a
core file size (blocks, -c) 0
data seg size (kbytes, -d) unlimited
scheduling priority (-e) 20
file size (blocks, -f) unlimited
pending signals (-i) 16382
max locked memory (kbytes, -l) 64
max memory size (kbytes, -m) unlimited
open files (-n) 1024
pipe size (512 bytes, -p) 8
POSIX message queues (bytes, -q) 819200
real-time priority (-r) 0
stack size (kbytes, -s) 8192
cpu time (seconds, -t) unlimited
max user processes (-u) unlimited
virtual memory (kbytes, -v) unlimited
file locks (-x) unlimited

Qual é a maior área de heap?
A área de heap é a área que o sistema reserva para cada processo alocar memória dinamicamente, portanto o teste natural para encontrar este limite foi utilizar a chamada malloc da mesma maneira que com o fork.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MB 1024*1024

int main()
{
void *ponteiro = NULL;
int i = 0;

while(1)
{
ponteiro = (void *) malloc(MB);
if (!ponteiro) break;
memset(ponteiro,1, MB);
printf("Memória alocada: %d MB\n",++i);
}
exit(0);

}

O resultado obtido foi com a execução do programa compilado expressa o tamanho da heap:

Memória alocada: 569 MB
Killed

Esta era apresentada como ilimitada na chamada de sistema ulimit -d!

Qual é a maior área de pilha?
Toda vez que se chama uma função, o processo guarda o endereço atual na pilha e vai para o endereço da função, por isso o teste utilizado foi fazer uma função que chama a si mesma indefinidamente.

#include <stdio.h>
int i;

void funcao(){
printf("Chamada %d\n",++i);
funcao();
}

int main(){
i = 0;
funcao();
}

A execução do programa acima apresentou uma saída final:

Chamada 523826
Segmentation fault

O que significa que, se considerarmos que são 8192kB de pilha, temos que cada chamada de função armazena 16B de dados na pilha que, de fato, equivale ao tamanho do endereço.

A área de swap pode ser esgotada?
A área de swap pode ser esgotada e um dos efeitos que isso causa é o trashing da memória, isto é, os processos são retirados e recolocados na memória a ponto de mal conseguirem manter seu caminho normal de execução. Dessa maneira, o tempo de processamento aumenta muito e torna a dificulta ainda mais a liberação de memória, já que menos processos conseguem terminar sua execução.
Uma solução que foi implementada foi a utilização de swap tokens, que são uma espécie de passe para que os processos terminem sua execução e liberem espaço, evitando o trashing da memória.

Área de swap

Como ela é utilizada?
A área de swap é utilizada quando o kernel está sem memória devido a chamada de um fork para criar um processo filho, um brk para aumentar o segmento de dados, para alocar uma pilha que estourou o espaço alocado ou para trazer de volta um processo que já estava no disco.
Para determinar quem será guardado no disco, o swapper procura por arquivos que estão bloqueados, que estão há mais tempo parados e pela prioridade.
Após isso, o swapper ainda verifica de quando em quando se é possível recolocar um processo que está no disco de volta para a memória. Algumas vezes, é preciso fazer o swap de processos na memória para devolver um processo que estava no disco (o que é chamado de hard swap).
A área de swap é ativada principalmente para compensar o excesso de consumo de memória de alguns programas, algum eventual processo que ocupe muito mais memória do que o esperado, para otimizar o uso da memória desalocando processos da memória para dar lugar à memória-cache, e para hibernar o sistema.

Qual o tamanho ideal da área de swap?
O tamanho ideal para a área de swap é bastante discutido e o senso comum é de que o ideal é que esse tamanho esteja entre n e 2*n, onde n é o tamanho de sua memória física.
Note que o processo de hibernação guarda toda a ram no swap, portanto nesse caso o swap deve possuir no mínimo o tamanho da ram!

Referências
http://jno.glas.net/data/prog_books/lin_kern_2.6/0596005652/understandlk-CHP-17-SECT-4.html
http://www.cab.u-szeged.hu/local/linux/doc/sag/node63.html
https://help.ubuntu.com/community/SwapFaq
http://se9.blogspot.com/2008/02/design-issue-i-came-across-while.html
A.S.Tanbaum, Modern Operating System 2nd ed

Segurança

O Linux utiliza o conceito de usuários e grupos, cada um identificado por um ID de 16 bits. A associação de usuários com grupos é feita por um administrador do sistema (que pertence ao grupo de administradores). Quando um processo é criado, ele carrega o UID (ID do usuário) e GID (ID do grupo) do seu criador. Quando um arquivo é criado, ele carrega as UID e GID do processo que o criou.
Esse sistema é utilizado para determinar permissões para arquivos, que são representadas por 9 bits, que representam permissão de leitura, escrita e execução para o criador, grupo do criador e todos (representado por rwxrwxrwx na ordem).
Um mecanismo especial do Linux é ter o SETUID bit nos programas, que funciona da seguinte forma: se um usuário executa o programa, o UID do processo torna-se o UID do criador do programa, e não do usuário que executou o programa; dessa forma é possível criar permissões que se aplicam a programas, e não a usuários que executam os programas.

A seguir, vamos analisar alguns tópicos sobre a segurança do Linux: invasão de áreas de outros processos e de sistema, acesso à áreas não autorizadas e transferência de dados do Kernel para processos e vice-versa.

Um processo pode invadir áreas de outros processos?
Não. Cada processo possui seu próprio espaço de endereçamento, não permitindo que um processo invada a área de outros processos.
Os espaços de endereçamento dos processos são administrados pelo kernel, que controla o acesso à área de cada processo.

Um processo pode invadir áreas do sistema?
O acesso às áreas do sistema são controlados a partir de permissões. O sistema verifica as permissões do processo que requer acesso e, a partir do nível de permissão concedido ao processo, determina se o acesso é autorizado ou não.

O que acontece quando um processo tenta acessar uma área não autorizada?
O acesso à uma área não autorizada caracteriza uma exceção, que será tratada pelo kernel.
Por exemplo, ao tentar acessar uma área não autorizada, podemos gerar uma Bounds Check fault, que ocorre quando uma instrução é realizada com operandos fora das áreas de endereço válidos. Neste caso, o sinal gerado é um SIGSEGV.

Como ocorre a tranferência de dados do kernel para processos e vice-versa?
A presença de dados inconsistentes ou maliciosos no kernel pode trazer instabilidades e insegurança ao sistema. Por isto, é necessário verificar previamente os dados antes de transmití-los ao kernel. Isto ocorre através de uma série de funções pertencentes à API do kernel do linux.
A transferência de dados ocorre de acordo com a figura abaixo, realizando um armazenamento prévio em buffer, de modo a verificar a consistencia e validade dos dados. Uma vez verificado, os dados são transmitidos para o kernel.



Referências:
http://www.gelato.unsw.edu.au/~dsw/public-files/kernel-docs/kernel-api/index.html
http://tldp.org/HOWTO/Security-HOWTO/
http://www.ibm.com/developerworks/br/library/j-zerocopy/index.html
http://en.wikipedia.org/wiki/Security-Enhanced_Linux

Tratamento de Áreas de Memória Fixas

Existem páginas na memória que não podem ser desalocadas no processo de swap, sendo portanto áreas de memória fixas.
Isso é uma característica importante em programas de tempo-real, uma vez que ocasionais faltas de página podem denegrir a performance devido ao processo de recuperação de página que inclui a busca dos dados da página, a busca por um página vagável na memória física e a ocupação da página.
A interface para utilizar este mecanismo é o mlock() e munlock() que serão brevemente descritos abaixo (também existem os mlockall()/munlockall() e memcntl()).
É bom saber que a região da memória a ser fixada é quantizada em páginas, e por isso a os endereços de memória que serão fixados devem se referir a extremos de páginas. Além disso, há dois fatores que devem ser levados em consideração antes de se projetar a utilização de áreas de memória fixas: o processo deve ter os privilégios necessários para utilizar este artifício e a quantidade da área de memória fixada não pode extrapolar certos limites, pois o SO reserva uma área de memória que não pode ser fixada.
As funções mlock e munlock estão na biblioteca sys/mman.h e recebem os mesmos parâmetros:
1) Endereço: Endereço de início da área memória que deve ser fixada.
2) Comprimento: Tamanho da área de memória que será fixada.

É interessante citar que as funções que terminam com all fazem o tratamento de todo o espaço de endereço do processo.

Referências
http://blogs.sun.com/thejel/entry/locking_memory
http://linux.die.net/man/2/mlock

Mapeamento de Arquivos na Memória Virtual

O mapeamento de arquivos na memória virtual consiste no mapeamento de uma seção do arquivo (o que pode ser o arquivo inteiro) na memória e criação de ponteiros para esta área na memória. Deste modo, é possível ter acesso ao conteúdo do arquivo através de ponteiros.
Uma utilização trivial deste tipo de mecanismo é o próprio carregamento dos processos na memória, quando o SO pega o arquivo com o programa e carrega na área de texto.
Isto também é muito utilizado para compartilhamento entre processos. Quando dois processos acessam o mesmo arquivo, é preciso "reabrir" o arquivo a todo o momento, o mapeamento na memória evita esse tipo de problema, mas é essencial que os processos utilizem semáforos para evitar problemas de concorrência.
A chamada de sistema que realiza esta função é o mmap(...) que deve receber um arquivo que possui um descritor gerado com a chamada de sistema fopen(...).
Um exemplo de utilização é:

#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>

int descritor_de_arquivo, tamanho_da_pagina;
char *dados;

descritor_de_arquivo = fopen("arquivo", O_RDONLY);
tamanho_da_pagina = getpagesize();
dados = mmap((caddr_t)0, 10*tamanho_da_pagina, PROT_READ, MAP_SHARED, descritor_de_arquivo, 0);

Os parâmetros da função mmap são:
1) Endereço: Ao utilizar (caddr_t)0, por padrão o sistema atribui para um endereço que é retornado na chamada da função (caso contrário, a variável dados poderia receber o endereço pré-determinado e apontaria para a mesma região).
2) Tamanho: É a quantidade de dados que queremos mapear (preferencialmente utiliza-se um múltiplo do tamanho da página caso contrário será mapeada uma quantidade de 0's que complete o tamanho da página e que não será persistida no disco).
3) Proteção: Recebe os valores (PROT_READ|PROT_WRITE|PROT_EXEC) que podem ser separados por '|' caso sejam permitidos mais de um tipo de permissão de acesso. É importante ressaltar que a permissão do mapeamento deve ser coerente com a permissão encontrada no descritor do arquivo.
4) Flags: Há diversos tipos de flags que podem ser setados, mas sempre um de MAP_SHARED e MAP_PRIVATE deve ser citado (o primeiro é para mapeamentos compartilhados entre processos e o segundo para mapeamentos privados), outros valores para isso podem ser encontrados com uma descrição mais detalhada no site http://linux.die.net/man/2/mmap
5) Descritor de Arquivo: O descritor do arquivo que será mapeado e que deve ter sido inicializado anteriormente.
6) Endereço do Arquivo Inicial: Indica onde o mapeamento do arquivo deve iniciar, uma vez que é possível mapear apenas a parte desejada do arquivo.

Para desmapear o arquivo, pode-se terminar o processo ou utilizar a chamda munmap(...), no entanto, é interessante notar que acabar com o descritor não irá desmapear o arquivo.
A chamada ummap pode desmapear apenas parte do arquivo, veja os parâmetros que são passados:
1) Endereço: Pode ser o endereço recebido da função mmap ou esse valor acrescido do endereço no arquivo inicial do desmapeamento.
2) Comprimento: É o tamanho do bloco que será desmapeado.

Isto resume o mapeamento de memória no linux utilizado com foco no compartilhamento de dados entre processos.

Referências
http://www.ecst.csuchico.edu/~beej/guide/ipc/mmap.html
http://en.wikipedia.org/wiki/Memory-mapped_file
http://linux.die.net/man/2/mmap

Mapeamento de Arquivos na Memória Virtual

Referências:
http://en.wikipedia.org/wiki/Virtual_memory

Compartilhamento de Memória

A memória compartilhada consiste de uma região de memória que pode ser acessada por dois ou mais processos.
Esta área comum aos processos é utilizada por cada um deles como pertencente à sua área de memória e é utilizada também como um modo eficiente de realizarmos troca de dados entre os
processos.
Como todos os processos podem alterar esta área de memória, certos cuidados devem ser tomados. Como por exemplo, não permitindo acesso simultâneo à esta área compartilhada através do uso de semáforos.

O compartilhamento de memória envolve a criação de um segmento de memória compartilhada, acoplamento e desacoplamento ao segmento de memória compartilhada e as operações de ler e escrever (acesso à memória compartilhada).

A criação do segmento é realizada através da chamada shmget(), que possui o seguinte protótipo:

 int shmget(key_t key, size_t size, int shmflg);

Nesta criação, define-se as permissões de acesso e o tamanho de bytes do segmento. O retorno desta função é um inteiro, responsável por identificar o segmento de memória compartilhado. Este identificador deve ser utilizado pelos processos que desejam ler ou escrever nesta memória compartilhada.
Antes de ler ou escrever, precisamos acoplar o processo ao segmento de memória compartilhada, através da função shmat(), passando o identificador do segmento como parâmetro. A função possui o seguinte protótipo:

void *shmat(int shmid, void *shmaddr, int shmflg);

A função retorna um ponteiro, que é utilizado para desacoplar o processo do segmento compartilhado.
Para desacoplar o processo do segmento de memória compartilhada, utilizamos a função, passando como parâmetro o ponteiro de retorno de shmat. A função possui o seguinte protótipo:

 int shmdt(void *shmaddr);

Para maiores informações e um exemplo de uso destas funções descritas acima, consulte as referências.

Referências:
http://www.ecst.csuchico.edu/~beej/guide/ipc/shmem.html

Interfaces para Gerenciamento de Memória

No linux, os processos são representados por uma grande estrutura chamada de task_struct. Nesta estrutura, temos todos os dados necessários para representar o processo e manter a relação de processos pais e filhos. A task_struct reside em ./linux/include/linux/sched.h.
No gerenciamento de memória do Linux, a maioria dos processos são criados dinâmicamente e representados pela task_struct. Um exemplo disso pode ser visto em ./linux/arch/i386/kernel/init_task.c.
Os processos no Linux podem ser coletados de duas formas:
- hashtable: os processos são colocados em hash pelo valor de PID
- lista duplamente encadeada

Agora, vamos analisar as interfaces existentes no Linux para realizar a criação e remoção de processos, a troca de contexto e o page-fault.


Criação de Processos:
A criação de processos ocorre através da chamada fork(). A partir dela, uma sequência de chamadas são realizadas, como mostrado na figura abaixo.


Na chamada do_fork, realizamos a alocação de um PID para o novo processo. Em seguida, realizamos uma análise no processo pai, para passar os flags, registradores e situação de pilha.
Na chamada copy_process, criamos o processo filho como uma cópia do pai.
Em seguida, dup_task_struct (encontrada em ./linux/kernel/fork.c) é chamada, alocando um novo task_struct e copiando os descritores do processo atual nele.

Troca de Contexto entre Processos:
A troca de contexto entre processos é responsável por armazenar as informações sobre o estado operacional do processo, de modo que este processo possa retomar sua operação de uma posição idêntica. Além disso, o ato de remover o processo de atividade e colocar outro é conhecido como troca de contexto.
O contecto de um processo envolve seu espaço de endereço, espaço de pilha, espaço de endereço virtual, registro de imagem fixa, ponteiro de pilha, registro de instrução e registradores de uso geral.
Ao realizar uma interrupção, o escalonador é responsável por armazenar o estado atual de task_struct e substituir o ponteiro de tarefas atual por um ponteiro para o task_struct do novo processo.

Page Fault:
Uma página é um bloco de memória de tamanho fixo que é utilizado como unidade de transferência entre a memória física e um dispositivo externo.
Uma page-fault é uma interrupção ao software gerada por hardware quando um programa acessa uma página que está mapeada no espaço de endereços, mas não está carregada na memória física.
O hardware responsável por identificar esta situação é o MMU. O software responsável por tratar esta interrupção faz parte do sistema operacional e tenta disponibilizar a página requerida ou então finaliza o programa, no caso de um acesso ilegal.
Os page-faults são comums e necessários para aumentar a quantidade de memória disponível aos programas nos sistemas operacionais.

Remoção de Processos:
A remoção do processo ocorre após a chamada de término de um processo. O término do processo ocorre através da chamada exit().
A chamada exit() realiza a chamada da função do_exit(), presente no kernel, como mostrado na figura abaixo.


A função do_exit é responsável por remover todas as referências do processo atual do sistema operacional. Após remover o processo, seu estado é alterado para PF_DEAD e a função schedule é chamada para selecionar um novo processo para execução.
A função do_exit com o auxílio de outras chamadas como: exit_mm, exit_keys e exit_notify.
A chamada exit_mm é responsável por remover as páginas da memória e
A chamada exit_notify é responsável por notificar os outros processos a respeito da saída deste processo (Ex: processo pai notificado da saída do filho).

Referências:
http://www.ibm.com/developerworks/br/library/l-linux-process-management/index.html
http://lzanuz.sites.uol.com.br/processos.htm
http://en.wikipedia.org/wiki/Page_fault
http://www.linux-tutorial.info/modules.php?name=MContent&pageid=326

Projeto de um device-driver USB para o Linux.

Introdução
O kernel é responsável por executar diferentes tarefas que podem ser divididas em gerenciamento de processos, gerenciamento de memória, comunicação em rede, sistema de arquivos e controle de dispositivos. Nesse último, encontramos os device-drivers, que são códigos para controle de dispositivos específicos. E o kernel precisa ter os devidos device-drivers para cada um de seus periféricos: HD, teclado, impressora, monitor, etc. Os device-drivers fazem parte do processo de entrada e saída do sistema operacional. Quando um usuário imprime um documento, ele está utilizando entre outras coisas um device-driver que transmite para a impressora o que ela deve imprimir de uma forma que ela entenda. Quando ele está digitando algo no teclado, é um device-driver que traduz o sinal do teclado para o computador. Os device-drivers são o canal de comunicação entre o kernel e o dispositivo. Através dele, o usuário consegue acionar funcionalidades do dispositivo sem precisar conhecer especificamente o funcionamento do dispositivo. No Linux, os device-drivers seguem uma interface padronizada que facilita ainda mais o uso dos drivers. Devido a essa interface, o sistema pode disponibilizar algumas chamadas padronizadas e independentes dos drivers para o usuário. Para ilustra melhor o papel dos device-drivers, a figura abaixo apresenta o posicionamento lógico dos device drivers.
Na arquitetura dos devices-drivers no Linux, eles se enquadram na categoria de módulos. Isto permite que drivers sejam adicionados e removidos do kernel dinamicamente, isto é, sem a necessidade de reiniciar o sistema, por exemplo. Dentro dos módulos, eles ainda podem ser classificados em módulos de caractere, de bloco e de rede. Módulos de caractere disponibilizam uma interface que podem ser acessada como uma stream de bytes e disponibiliza as funções de open, close, read e write, e a diferença deles para arquivos é que geralmente eles devem ser acessados sequencialmente. Módulos de bloco suportam sistemas de arquivos e podem manusear operações de transferência de blocos de dados. No Linux, os módulos de blocos podem ser utilizados como módulos de caractere, sendo que a modulação é interna ao kernal e, portanto, transparente ao usuário. Módulos de rede, diferentemente dos outros, tratam do envio e recebimento de pacotes de dados, dentro do subsistema de comunicação em rede do kernel. Assim, o módulo de rede cuida apenas de enviar e receber os pacotes, sendo que o endereçamento dos dados e protocolo utilizado é tratado acima do driver.
É importante voltar a ressaltar que o papel dos drivers é traduzir chamadas de funções para operações de entrada e saída. Portanto não é o driver que vai implementar o sistema de arquivo de um disco rígido, por exemplo. Haverá um processo tratando especificamente disso e repassando chamadas simples de leitura e escrita para o driver executar a devida operação no disco.

O que é desejável de um device-driver?
Outra característica de design dos device-drivers no Linux é a separação de mecanismo e política, ou seja, o que o driver oferece e o que pode ser utilizado. No caso, a camada dos device-drivers é responsável pelo mecanismo, de modo que não deve haver nenhum tratamento do de permissões na implementação de um driver, a não ser que seja alguma limitação do dispositivo.
Desse modo, os drivers são flexíveis para diferentes utilizações. Como algumas vezes o excesso de opções dificulta mais do que facilita a utilização, alguns drivers vêm acompanhados de aplicativos que tratam da política e facilitam a configuração e utilização dos drivers (deixando o usuário livre para utilizar ou não esse auxílio).
Além disso, é essencial que os drivers sejam desenhados pensando na segurança do kernel, uma vez que serão “inseridos” como parte do código dele. É imprescindível que haja, por exemplo, verificação de que o que está sendo colocado no buffer não vai estourar sua capacidade, ou que os dados que o usuário insere serão transferidos temporariamente a uma área protegida, para serem verificados. Tomando o devido cuidado, garante-se que o driver não irá inserir falhas de segurança ao kernel.

O que é necessário para poder desenvolver um device-driver no Linux?
É preciso ter um bom conhecimento da arquitetura de drivers do Linux, além de saber programar em C e ter conhecimento das bibliotecas específicas que serão utilizadas. Como ferramentas de programação, é preciso que o usuário possua um compilador e as bibliotecas de desenvolvimento para Linux.
Também é desejável que o usuário tenha acesso a uma máquina de testes (ou no mínimo um backup completo do sistema), uma vez que existe o risco de que device-drivers problemáticos causem dano ao sistema operacional, podendo ocasionar até perda de dados.

Desenvolvimento de uma implementação de driver USB
O próprio Linux facilita e muito o trabalho com dispositivos USB através do subsistema ‘USB core’, que cuida de boa parte da complexa interação com os dispositivos. O ‘USB core’ disponibiliza uma API mais simplificada para ser acessada pelo driver. O driver, então, interage com o USB core ao invés de interagir diretamente com o controlador do dispositivo.
Do lado do dispositivo, o USB pode disponibilizar diversas interfaces para o usuário, cada interface com diversas saídas, sendo que cada interface é responsável por uma conexão lógica (comunicação, interface com usuário, áudio, etc) e cada saída possui uma função (controle, interrupção, troca de dados). Para se comunicar com as saídas, um dos mecanismos que o kernel utiliza é o urb (USB request block – bloco de pedido de USB). O urb é um bloco de comunicação unidirecional que, portanto, pode ser utilizado ou para enviar ou para transmitir dados, nunca os dois.
Para programar um driver, é preciso primeiramente registrar o driver no USB core. Para isso, o módulo deve conter uma estrutura que representa o driver como:

static struct usb_driver skel_driver = {
.owner = THIS_MODULE,
.name = "skeleton",
.id_table = skel_table,
.probe = skel_probe,
.disconnect = skel_disconnect,
};

Cada uma dos campos da estrutura contém uma explicação mais aprofundada na página 348 do livro Linux Device Drivers da O’Reilly (disponível em http://oreilly.com/catalog/linuxdrive3/book/ch13.pdf). Elas são utilizadas para que o USB core possa acessar dados/funções do driver. Ou seja, o core possui uma listagem de estruturas USB_driver e acessa as funcionalidades do driver através dessa estrutura.
Também devem ser fornecidas pelo menos as funções probe e disconnect. A função probe de cada driver USB é chamada pelo USB core para verificar se o driver é adequado para manusear o dispositivo. A função disconnect é chamada quando o dispositivo é desconectado ou removido da listagem do USB core.
Como foi explicado na "Introdução" os drivers são módulos que podem ser carregados no kernel do Linux. Portanto, o registro do driver USB no core ocorre na inicialização do módulo, como por exemplo em:

#include <linux/init.h>
#include <linux/module.h>
#include <linux/usb.h>
static int __init usb_skel_init(void)
{
int result;
/* register this driver with the USB subsystem */
result = usb_register(&skel_driver);
if (result)
err("usb_register failed. Error number %d", result);
return result;
}
module_init(usb_skel_init)

Analogamente, ao remover o módulo do kernel, deve-se desregistrar o driver do USB core:

static void __exit usb_skel_exit(void)
{
/* deregister this driver with the USB subsystem */
usb_deregister(&skel_driver);
}
module_exit(usb_skel_exit)

Sendo assim, temos o suficiente para que, quando um dispositivo USB for instalado no computador, o USB core irá tentar atribuir algum driver para o manuseio deste dispositivo. Através da função probe, o USB core irá verificar se o driver se adéqua e, em caso positivo, ele deve inicializar estruturas para gerenciar o dispositivo. No exemplo abaixo, é ilustrado uma forma de registrar os primeiros terminais bulk de entrada e saída:

/* set up the endpoint information */
/* use only the first bulk-in and bulk-out endpoints */
iface_desc = interface->cur_altsetting;
for (i = 0; i <>desc.bNumEndpoints; ++i) {
endpoint = &iface_desc->endpoint[i].desc;
if (!dev->bulk_in_endpointAddr &&
(endpoint->bEndpointAddress & USB_DIR_IN) &&
((endpoint->bmAttributes & USB_ENDPOINT_XFERTYPE_MASK)
= = USB_ENDPOINT_XFER_BULK)) {
/* we found a bulk in endpoint */
buffer_size = endpoint->wMaxPacketSize;
dev->bulk_in_size = buffer_size;
dev->bulk_in_endpointAddr = endpoint->bEndpointAddress;
dev->bulk_in_buffer = kmalloc(buffer_size, GFP_KERNEL);
if (!dev->bulk_in_buffer) {
err("Could not allocate bulk_in_buffer");
goto error;
}
}
if (!dev->bulk_out_endpointAddr &&
!(endpoint->bEndpointAddress & USB_DIR_IN) &&
((endpoint->bmAttributes & USB_ENDPOINT_XFERTYPE_MASK)
= = USB_ENDPOINT_XFER_BULK)) {
/* we found a bulk out endpoint */
dev->bulk_out_endpointAddr = endpoint->bEndpointAddress;
}
}
if (!(dev->bulk_in_endpointAddr && dev->bulk_out_endpointAddr)) {
err("Could not find both bulk-in and bulk-out endpoints");
goto error;
}
/* save our data pointer in this interface device */
usb_set_intfdata(interface, dev);

Abaixo, é apresentada uma maneira de recuperar esses dados guardados na interface de dispositivo:

struct usb_skel *dev;
struct usb_interface *interface;
int subminor;
int retval = 0;
subminor = iminor(inode);
interface = usb_find_interface(&skel_driver, subminor);
if (!interface) {
err ("%s - error, can't find device for minor %d",
__FUNCTION__, subminor);
retval = -ENODEV;
goto exit;
}
dev = usb_get_intfdata(interface);
if (!dev) {
retval = -ENODEV;
goto exit;
}

Para registrar o dispositivo, deve ser utilizada a função USB_register_dev que passa a interface e uma USB_class_driver que será atrelada à interface. A USB_class_driver contém diversos parâmetros para registrar um “minor number”, que se refere ao dispositivo. Nela haverá informações como o nome, as operações para acessar o dispositivo, entre outros.
Para a desconexão do dispositivo, deve ser removido o USB_class_driver associado à interface e o dispositivo deve ser removido do registro no core:

static void skel_disconnect(struct usb_interface *interface)
{
struct usb_skel *dev;
int minor = interface->minor;
/* prevent skel_open( ) from racing skel_disconnect( ) */
lock_kernel( );
dev = usb_get_intfdata(interface);
usb_set_intfdata(interface, NULL);
/* give back our minor */
usb_deregister_dev(interface, &skel_class);
unlock_kernel( );
/* decrement our usage count */
kref_put(&dev->kref, skel_delete);
info("USB Skeleton #%d now disconnected", minor);
}

Para a transferência de dados, será abordado como utilizar os URBs, embora seja possível se comunicar com o dispositivo através de mensagens bulk e control. Para se comunicar através das urbs é preciso alocá-las, o que pode ser feito da seguinte forma:

urb = usb_alloc_urb(0, GFP_KERNEL);
if (!urb) {
retval = -ENOMEM;
goto error;
}

Após isso, é bom criar um buffer DMA para realizar a transferência de maneira mais eficiente:

buf = usb_buffer_alloc(dev->udev, count, GFP_KERNEL, &urb->transfer_dma);
if (!buf) {
retval = -ENOMEM;
goto error;
}
if (copy_from_user(buf, user_buffer, count)) {
retval = -EFAULT;
goto error;
}

Com a urb alocada e o buffer local carregado é preciso inicializar a urb com esses dados:

/* initialize the urb properly */
usb_fill_bulk_urb(urb, dev->udev,
usb_sndbulkpipe(dev->udev, dev->bulk_out_endpointAddr),
buf, count, skel_write_bulk_callback, dev);
urb->transfer_flags |= URB_NO_TRANSFER_DMA_MAP;

Somente após isso é realizada a transferência de dados para o dispositivo:

/* send the data out the bulk port */
retval = usb_submit_urb(urb, GFP_KERNEL);
if (retval) {
err("%s - failed submitting write urb,
error %d", __FUNCTION__, retval);
goto error;
}

Como no envio foi enviado um ponteiro para skel_write_bulk_callback, o USB core irá chamar essa função quando a transmissão de dados for concluída. Um exemplo de implementação pode ser:

static void skel_write_bulk_callback(struct urb *urb, struct pt_regs *regs)
{
/* sync/async unlink faults aren't errors */
if (urb->status &&
!(urb->status = = -ENOENT ||
urb->status = = -ECONNRESET ||
urb->status = = -ESHUTDOWN)) {
dbg("%s - nonzero write bulk status received: %d",
__FUNCTION__, urb->status);
}
/* free up our allocated buffer */
usb_buffer_free(urb->dev, urb->transfer_buffer_length,
urb->transfer_buffer, urb->transfer_dma);
}

Resumindo, para a implementação de um driver USB, devemos escrever os códigos de inserção e remoção do módulo, depois devemos escrever as funções callback, que serão acessadas pelo USB core para atrelar novos dispositivos USB ao driver e devemos programar as funções de operações de arquivos que o driver irá disponibilizar para o kernel interagir com o dispositivo.

Instalação
Como os device-drivers são módulos do Linux, sua instalação é feita através da inserção de módulos ao kernel. Como foi visto, isto é realizável através da função insmod após compilar o módulo:

>> cd (endereço do driver)
>> make
>> insmod (endereço do driver)/(arquivo do driver).o

Isso irá fazer com que seja adicionado um /dev/(arquivo do driver) para o Ubuntu, por exemplo.

Como testar o device-driver?
Para testar um device-driver, uma idéia é colocar arquivo do driver na pasta /tmp que é apagada sempre que o sistema reinicia e colocar na pasta de drivers um link para o arquivo. Desse modo, caso o driver dê crash no kernel e este não consiga iniciar, o problema será resolvido automaticamente reiniciando o computador.
Enquanto isso, é possível verificar as rotinas de _init(), _info() e _attach() e verificar se o comportamento do dispositivo está dentro do esperado, com menos riscos para o sistema.

Referências.
http://www.faqs.org/qa/qa-16964.html
http://www.lrr.in.tum.de/Par/arch/usb/download/usbdoc/usbdoc-1.32.pdf
http://oreilly.com/catalog/9780596005900/book/index.csp

Remoção de Páginas

Neste tópico, abordaremos os algoritmos e estruturas de dados que podem ser utilizados para se remover uma página.
A remoção de uma página ocorre quando a tabela de página está cheia e, em um acesso à memória, não encontramos a página desejada na tabela de páginas. Isto gera um page fault, que busca diretamente esta página na memória. Ao encontrá-la, esta página é carregada na tabela de páginas no lugar de uma outra página, como ilustrado abaixo. A escolha da página que irá sair da memória é o alvo de estudo deste tópico.

Pelo diagrama acima, podemos observar que a remoção de uma página deve ocorrer quando a memória estiver cheia e não encontrarmos a página na TLB.
Os algoritmos são:

Algoritmo Ótimo:
Este algoritmo é apenas teórico. Foi proposto por Belady em 1966 e exemplifica a situação ideal, em que minimizamos a quantidade de faltas de página. A idéia do algoritmo é remover a página que levará mais tempo para ser acessada. Portanto, o algoritmo precisa ter conhecimento dos instantes ou intervalos de tempo em que a memória será acessada.
Como é impossível prever os instantes em que as informções serão exigidas, este algoritmo não é realizável na prática.
Por apresentar a melhor aproximação com o cenário ideal, este algoritmo é utilizado como referência para comparação com os demais algoritmos.

Algoritmo NRU:
Este algoritmo é simples para se entender e implementar, e apresenta uma performance que pode ser adequada.
Utilizamos 2 bits para classificar as páginas e, em seguida, removê-las de acordo com sua classificação. O primeiro bit é o de referência e o segundo bit refere-se à modificação. Setamos o bit de referência se a página é referenciada para leitura ou escrita. E setamos o bit de modificação quando modificamos a página.
Quando um dos bits é setado, ele permanece em 1 até que o sistema operacional o resete no software.
Em seguida, classificamos as páginas como:
-Classe 0: não referenciada, não modificada
-Classe 1: não referenciada, modificada
-Classe 2: referenciada, não modificada
-Classe 3: referenciada, modificada

Ao remover uma página, buscamos a página que possui o menor número de classe, de acordo com a classificação acima. Nesta busca, zeramos os bits de referência.

Algoritmo FIFO:
O algoritmo é implementado com o auxílio de uma fila. Utilizando a idéia de First In First Out, este algoritmo é simples de se entender e implementar. Ele apenas remove da memória, a página que foi carregada a mais tempo na memória.
Como este algoritmo não considera a frequência de uso das páginas, ele não reflete adequadamente as páginas que devem permanecer na memória, podendo resultar em perda de desempenho.
Um exemplo desta falta de adequação é observado no evento conhecido como Anomalia de Belady, em que a quantidade de faltas de página aumenta quando adicionamos memória.
Mais informações sobre a Anomalia de Belady podem ser obtidas em http://en.wikipedia.org/wiki/Belady%27s_anomaly.

Algoritmo da Segunda Chance:
Com o objetivo de adequar a fila às páginas acessadas com maior frequência, realizou-se uma alteração no Algoritmo FIFO.
Com o algoritmo da Segunda Chance, se uma página existente na memória for acessada, ela passa para o final da fila. Deste modo, as páginas que são frequentemente utilizadas não estarão no final da fila e não serão removidas.
Contudo, este algoritmo apresenta uma ineficiência, já que é necessário deslocar parte da fila, sempre que uma página pertencente a fila for acessada.


Algoritmo Clock:
Como solução para o problema de ineficiência encontrado no algoritmo de Segunda Chance, utilizamos o algoritmo Clock. Neste algoritmo, as páginas são mantidas em uma lista circular e controlados por um bit R.
Se o bit de controle indica R=0, então a página pode ser removida.
Se o bit de controle indica R=1, então colocamos R=0 e deslocamos o ponteiro.

Inserimos a nova página no local da página removida e deslocamos o ponteiro para a próxima da lista circular.

Algoritmo LRU:
O algoritmo Least Recently Used remove a página menos recentemente utilizada. Esta idéia surgiu da observação que páginas intensamente acessadas possuem maior probabilidade de serem acessadas novamente do que páginas que são pouco referenciadas.

O algoritmo LRU é realizável, mas não é barato. Para implementar o LRU, devemos manter uma lista ligada de todas as páginas na memória, com a página mais recentemente utilizada na frente da lista e as páginas menos recentemente utilizadas atrás na lista. Desse modo, a dificuldade reside em atualizar esta lista em todas as referências à memória.


Algoritmo WS:
Este algoritmo possui a mesma idéia do algoritmo de LRU. Ao invés de remover a página que foi utilizada menos recentemente, este algoritmo define um tempo de vida, tal que se a página não for referenciada por um tempo maior ou igual ao tempo de vida definido, a página pode ser removida da memória.
Cada página guarda o tempo de seu último acesso, que será utilizado para calcular seu tempo de vida, e o bit de referência R.
A cada acesso, temos 3 situações possíveis:
R = 1: setamos o tempo de último acesso para o tempo atual e setamos R=0
R = 0: se o tempo de vida desta página for maior que o tempo de vida definido pelo algoritmo, então removemos esta página, inserindo a nova página neste local. Se o tempo de vida desta página for menor do que o tempo de vida definido pelo algoritmo, então setamos R=1 e passamos para a próximoa página.
Esta situação pode ser observada pela seguinte figura:




Referencias:
http://en.wikipedia.org/wiki/Belady%27s_Min#Belady.27s_Algorithm
http://en.wikipedia.org/wiki/Page_replacement_algorithm
http://en.wikipedia.org/wiki/Cache_algorithms

Tabelas de Página

Todo processo possui seu próprio espaço de endereçamento virtual e, como explicado nos posts antigos, o endereço virtual é transformado em um endereço físico. Esta conversão de endereço virtual para endereço físico é realizada com o auxílio da tabela de páginas.
O endereço virtual é separado em duas partes: o número da página virtual e o offset. Considere o exemplo de endereços de 16 bits, utilizando 4 bits para definir a página virtual e os 12 bits restantes para definir o offset dentro da página.
Os 4 bits definem um índice que será utilizado para encontrar o número da página que será utilizado para formar o endereço físico a ser procurado na memória. Este índice é passado para a tabela de página, que guarda o índice da página que devemos procurar na memória.
Desse modo, concluímos que a função da tabela de páginas é mapear endereços virtuais em endereços físicos.

A arquitetura mais simplificada da tabela de páginas consiste de um array de registradores com uma entrada para cada página virtual, sendo acessada através do número da página virtual. Contudo, como cada processo possui sua própria tabela de páginas, teríamos uma área muito grande ne memória principal sendo ocupada pela tabela de páginas, o que resultaria em uma perda de desempenho e aumento no custo do hardware a ser projetado.

Como solução, utilizamos uma tabela de páginas multinível. armazenada também na memória principal. Neste modelo, que permite um armazenamento não contiguo, alocamos novas páginas a medida que os processos crescem, preenchendo a tabela de páginas.


Observemos que na descrição da Tabela de Páginas, quando desejamos acessar a memória, devemos acessar inicialmente a tabela de páginas para obter o endereço físico e, em seguida, realizar um acesso à memória física para obter o dado ou instrução.

Como funciona a TLB

A TLB, também conhecida como Translation Lookaside Buffer é um pequeno dispositivo de hardware utilizado para realizar o mapeamento de endereços virtuais em endereços físicos sem necessitar de acesso à tabela de páginas. Normalmente, a TLB reside dentro da MMU e possui uma quantidade pequena de entradas. Cada entrada da TLB contém informações a respeito de uma página, incluindo o número virtual da página, um bit indicando se a página foi modificada ou não, o código de proteção da página e a localização real da página na memória como ilustrado na figura abaixo:

Quando um programa manda um endereço virtual à MMU, o hardware compara este endereço com todas as entradas da tabela TLB simultaneamente e se encontra um match, esta página é carregada diretamente da TLB, sem passar à tabela de página.
Desse modo, concluímos que a principal função da TLB é acelerar o acesso à memória, melhorando a performance do sistema. A melhora na performance do programa é resultado da observação que a maioria dos programas tende a utilizar uma grande quantidade de referências à uma pequena quantidade de páginas.
Quando a busca na TLB não retorna um match, então realizamos a busca pela página na tabela de páginas. Além disso, atualizamos a TLB de modo que esta nova página pertença à TLB. Para isto, devemos remover uma das páginas pertencentes à TLB.