CES33 - Sistemas Operacionais (Gerenciamento de memória no Linux)

Prévia do material em texto

ces33.wikidot.com
Gerenciamento de memória no linux -
CES33
20–28 minutos
Descrição. Principais características
O Linux usa paginação para gerenciar a memória.
Cada processo do Linux, em uma máquina de 32 bits, dispõe de 3GB
de espaço de endereçamento virtual para si próprio, com 1GB
restante para reservado para suas tabelas de páginas e outros dados
do núcleo. O 1GB do núcleo não é visível quando o processo executa
no modo usuário, mas torna-se acessível quando o processo faz uma
chamada ao núcleo.
Assim:
Endereço de 0x00000000 a PAGE_OFFSET-1 pode ser endereçado
tanto pelo modo usuário e modo kernel. user or kernel mode
Endereço de PAGE_OFFSET to 0xffffffff pode ser endereçado
somente no modo kernel
O PAGE_OFFSET é normalmente igual a 0xc00000000,para
arquitetura de 32 bits.
O espaço de endereçamento virtual é dividido em áreas ou regiões
organizadas em páginas contíguas homogêneas. Isso quer dizer que
cada área consiste de uma série de páginas consecutivas com
proteção e propriedades de paginação idênticas.
O tamanho das páginas varia de arquitetura para arquitetura,
entretanto a maioria costuma usar paginas de 4096 bytes. (A
constante PAGE_SIZE informa o tamanho da página para uma dada
arquitetura).
O endereço da memória virtual ou física é dividido em número de
pagina (PAGE_MASK) e offset (PAGE_SIZE). Se a página tem um
tamanho 4096 bytes, e a arquitetura suporta endereços de 32 bits por
exemplo, então os últimos 12 bits menos significativos corresponde
ao offset, e o restante corresponde ao número de página.
Cada endereço virtual é quebrado em até quatro campos. O campo
PGD (campo diretório) é usado como índice de diretório global, sendo
que existe um privado para cada processo. O valor encontrado é um
ponteiro para PMD (diretório intermediário de página), o quel é
indexado por um campo de endereço virtual. A entrada selecionada
aponta para PTE (tabela de página final), indexada pelo campo
página do endereço virtual. A entrada encontrada aponta para a
página requisitada.
Como funciona a TLB
Normalmente, os sistemas modernos incluem um cache de acesso
rápido usado para acelerar o processo de tradução de um endereço
linear.
Quando um endereço virtual é usado pela primeira vez, o endereço
físico correspondente é obtido através de acessos às Tabelas na
RAM, um processo lento demais para se repetir a cada acesso à
memória. A fim de melhorar o tempo de acesso, este endereço virtual
e seu respectivo endereço físico são salvos em uma tabela que
mapeia endereços virtual-fisico rapidamente. Essa tabela de página,
chamada TLB, fica armazenada no cachê no processador.
Então, quando a CPU acessa um endereço de memória virtual,
procura-se pela tradução adequada na seguinte ordem:
Procuramos a tradução associada àquele endereço de memória
virtual na TLB. Se o endereço é encontrado, a tradução é realizada;
Se o endereço de memória virtual não está na CPU, então a tradução
é feita através da tabela de página armazenada na RAM.
Tabela de páginas
Como mensionado, a tabela de páginas segue o padrão de
paginação em três níveis: Page Directory, Page Middle Directory e
Page Table. Cada endereço virtual é quebrado em até quatro campos
Cada processo tem seu próprio PGD (Page Global Directory) que é
pagina física contendo um array de pgd_t, na arquitetura específica é
definido em .
A tabela de página é lida diferentemente em cada arquitetura. Na x86,
a tabela de pagina do processo é lida copiando o ponteiro de PGD no
registrado cr3. Cada entrada ativa na tabela PGD aponta para a
moldura de página no array do PMD (Page Middle Directory) com
entradas do tipo pmd_t, que retorna um ponteiro para uma moldura
de página contendo PTE (Page Table Entries) do tipo pte_t, que
finalmente aponta para moldura de página contendo real dados do
usuário.
Segue o algoritmo do sistema de mapeamento da tabela de página:
pgd_t *pgd;
pmd_t *pmd;
pte_t *ptep, pte;
pgd = pgd_offset(mm, address);
if (pgd_none(*pgd) || pgd_bad(*pgd))
 goto out;
pmd = pmd_offset(pgd, address);
if (pmd_none(*pmd) || pmd_bad(*pmd))
 goto out;
ptep = pte_offset(pmd, address);
if (!ptep)
 goto out;
pte = *ptep;
Algoritmo de remoção de página
Páginas de um espaço de endereçamento linear de um processo não
estão necessariamente linear na memória, assim quando ocorre uma
requisição de página por uma que não está na memória, há uma
Page Fault.
Existem dois tipos de Page fault: falta maior ou menor. A falta maior
de páginas ocorre quando dados tem que ser lido do disco que é uma
operação cara (lenta), caso não seja, a falta é considerada como
menor ou falta de páginas soft.
O algoritmo usado pelo Linux para remover páginas da memória é o
do algoritmo LRU (Least Recently Used).
O LRU remove da memória a página que não foi utilizada por mais
tempo. Isso baseia-se na suposição de que páginas que não foram
recentemente utilizadas também não o serão nas próximas
instruções, enquanto páginas bastante utilizadas agora tendem a ser
bastante utilizadas na instruções seguintes também.
Para implementar esse algoritmo, o Linux tem uma lista duplamente
encadeadas, uma lista de paginas ativas e outra com paginas
inativas. As paginas ativas correspondem as páginas acessadas
recentemente. A segunda lista contém as páginas não acessadas há
algum tempos. O objetivo do LRU é remover as páginas inativas.
Para verificar se as páginas são referenciadas ou modificadas,
verificasse as flags PG_reference e PG_active, respectivamente, da
estrutura de pagina.
Interfaces para o gerenciamento de memória
Criação de processos
Um sistema UNIX cria um processo através da chamada a sistema
fork(), e o seu término é executado por exit(). A implementação do
Linux para eles reside em e . Executar
o "Forking" é fácil, fork.c é curto e de fácil leitura. Sua principal tarefa é
suprir a estrutura de dados para o novo processo. Passos relevantes
nesse processo são:
• Criar uma página livre para dar suporte à task_struct
• Encontrar um process slot livre (find_empty_process())
• Criar uma outra página livre para o kernel_stack_page
• Copiar a LTD do processo pai para o processo filho
• Duplicar o mmap (Memory map - memoria virtual) do processo pai
fork() cria um novo processo com um novo espaço de
endereçamento. Todas as paginas são marcadas com Copy-On-
Write (COW) e são compartilhadas entre dois processos (processo
pai e processo filho) até que ocorra uma falta de pagina (page fault).
Uma vez que uma falta de escrita ocorre, uma cópia é feita da página
COW para o processo que causou a falta. Alguma vezes é
referenciado como quebra da pagina COW.
Troca de contexto de processos
Para ocorrer a troca de contexto de processos, é feita
armazenamento da estrutura que guarda o status do processo pai, e,
em seguida, o novo processo passa a ser o processo “atual”. Para
isso, é necessário que o espaço de endereçamento utilizado no
processo filho seja mudado, que é feito pela troca do PGD (Page
Global Directory).
Page-fault
O manipulador de page fault é uma peça critica do código no kernel
do Linux que tem a maio influencia na performance do subsistema de
memória. Qualquer acesso a áreas da memória não mapeada pelo
tabela de paginas resulta na geração do sinal de page fault pela CPU.
Os sistemas operacionais devem prover um manipulador de page
fault que lide com essas situações e determine qual processo deve
continuar.
Espera-se do manipulador de page fault que ele reconheça e atua em
um numero diferente de tipos de page faults. Cada arquitetura
registra uma função especifica para o manipulador de page faults.
Quanto ao nome da função, é arbitrário, mas a escolha comum é
do_page_fault()
Essa função informa qual o endereço da page fault, se a pagina
simplesmente não foi encontrada ou se foi um erro de proteção, se
era uma falta de leitura ou escrita, e se essa falta era do espaço de
usuário ou kernel. Elaé ainda responsável por determinar qual o tipo
de falta ocorreu e como dever ser manipulada por um código
independente de arquitetura.
O handle_mm_fault() é uma função de alto nivel independete da
arquitetura que lida com page fault para armazenamento, execução
de COW e outras coisas.
Se retornar 1, é uma falta menor, s2 é uma falta maior, e 0 envia um
sinal de erro SIGBUS e qualquer outro valor chama para fora o
manipulador de memória.
Remoção de processos
A morte de um processo é difícil, porque o processo pai necessita ser
notificado sobre qualquer filhos que existam (ou deixem de existir).
Além disso, um processo pode ser morto (kill()) por outro processo. O
arquivo exit.c é, portanto, a casa do sys_kill() e de variados aspectos
de sys_wait(), em acréscimo à sys_exit(). O código pertencente à
exit.c trabalha com uma quantidade de detalhes para manter o
sistema em um estado consistente.
Quando se finaliza um processo, é realizada a chamada a exit_mm()
do kernel, que serve para limpar o descritor de memória do processo
e todas as estruturas relacionadas. A maior parte desta tarefa é
realizada pela chamada mmput() que libera a LDT, os descritores das
regiões de memória e as tabelas de páginas.
O descritor, em si, é liberado quando o processo é, finalmente,
desprezado pelo processador, através da chamada
finish_task_switch().
Compartilhamento de memória
Embora memória virtual permita processos terem espaços de
endereçamento separados (endereço virtual), há momentos quando
é necessário compartilhar memória. O compartilhamento de memória
serve para compartilhar informações sobre processos que utilizam as
mesmas variáveis, por exemplo.
O compartilhamento de dados pode ser feito de duas maneiras:
realizando a comunicação direta interprocessos ou fazendo dois
processos apontar para o mesmo lugar na memória RAM.
A memória virtual torna fácil para vários processos compartilharem a
memória. Todo acesso a memória são feito pela tabela de página e
cada processo tem sua própria tabela de paginas separada. Para
dois processos compartilharem a mesma pagina física da memória,
sua moldura de página física deve aparecer como entrada na tabela
de página de cada processo.
Figure acima mostra dois processos que compartilha a moldura de
pagina física numero 4. Para processo X, sua pagina virtual é a de
numero 4, enquanto que para o processo y esta mesma página é
mapeada pela pagina virtual 6. Isso ilustra um importante ponto sobre
compartilhamento de memória: a pagina fisica compartilhada não tem
que realmente existir no mesmo lugar dentro da memória virtual para
algum ou todos os processos que a compartilham.
Mapeamento de arquivo na memória
Um arquivo mapeado na memória pode ser considerado como o
resultado da associação de o conteúdo de um arquivo com a porção
do espaço de um endereço virtual de um processo. Ele pode ser
utilizado para compartilhar um arquivo ou memória entre dois ou mais
processos.
Cada espaço de endereçamento consiste de um numero de regiões
de paginas aninhadas na memória que está em uso. Eles nunca se
sobrepõem e representam um conjunto de endereços que contem
paginas que são relacionadas a outras em termos de proteção ou
propósito. Essas regiões são presentadas pela estrutura
vm_area_struct.
Ao carregar um arquivo, em geral, várias páginas da memória virtual
são associadas ao arquivo, de modo que o arquivo fica distribuído em
várias páginas.
Tratamento de áreas de memória fixas
Tanto paginas quanto regiões na memória tem flag para reservar, ou
seja, não é permitido trocar o conteúdo dessas partes da memória.
Para paginas, o flag é PG_reserved e é setado pelo Boot Alocator
durante a inicialização do sistema.
Para regiões, o flag é VM_reserved e é usado quando deseja-se
reservar regiões na memória para device drivers.
Quando o sistema é inicializado, é feita uma chamada
setup_memory(). Entre as várias tarefas que são executadas, ele
calcula o tamanho da memória física e cria um mapa de bits para ela.
Daí, é feita uma chamada reserve_bootmem() para reservar a página
necessária ao mapa de bits.
Segurança
As entradas das tabelas de páginas também contem informações do
controle de acesso. Quando um processador já está usando uma
tabela de páginas para mapear endereços virtuais em endereços
físicos, ele pode facilmente usar as informações do controle de
acesso para checar que processo não está acessando a memória da
forma que deveria.
Existem muitas razões do porque se quer restringir o acesso a areas
da memória. Algumas partes da memória, como as que contem
código executável, é naturalmente uma região de somente leitura; o
sistema operacional não deve permitir um processo escrever dados
sobre um código executável. Em contraste, páginas contendo dados
podem ser escritas, mas tentativas de executar esta memória como
instruções devem ser evitadas.
Muitos processadores tem no mínimo dois modos de execução:
kernel e usuários. Isso adiciona um nível de segurança para o
sistema operacional. Por ele ser o núcleo do sistema operacional e,
portanto, pode fazer qualquer coisa, o código do kernel é somente
executado quando a CPU está no modo kernel. Não é desejável que
o código do kernel seja executado por um usuário ou as estruturas de
dados do kernel sejam acessíveis, exceto quando o processador
esteja rodando no modo kernel.
No Linux há três modelos de controle de acesso básicos: Read, Write
e Execution.
Em processos que estão rodando em modo usuário, não é possível
ocorrer invasão na região da memória física de outro processo que
esteja rodando em modo usuário também. Além de mesmos
endereços virtuais serem mapeados em endereços físicos diferentes,
quando um processo usuário tenta acessar uma área que não foi
mapeada para ele, o sistema apresenta um erro SEGSEGV que é
enviado ao processo.
Em contrapartida, um processo que esteja executando em modo
kernel não possui restrições para acessar dados de outros
processos, assim, dados de um processo usuário podem ser alterado
por um processo no kernel.
A forma de um processo usuário transferir dados para o kernel é
através de uma chamada ao sistema (system call). Essa chamada
armazena o estado de execução do processo que requisitou e inicia a
execução do processo requerido em modo kernel. Quando o
processo kernel é finalizado, o processo que requisitou a chamada ao
sistema obtém o controle da CPU
Área de swap
Um sistema em execuçao eventualmente usa todas as molduras de
paginas, e, então, o Linux precisa selecionar uma página que já está
a mais tempo na memória que pode ser liberada e invalidada por
novos usuários antes da memória física ficar escassa.
O Linux, por ter suporte a memória virtual, ele utiliza o disco como
extensão da memória RAM, fazendo com que o tamanho de
memória disponível cresça consideravelmente. A parte do disco que
é usada como memória virtual é chamada área de troca ou área de
swap. E o processo responsável por isso é o swap daemon
O kernel swap daemon é um tipo especial de processo, um kernel
thread. Os kernel thread são processos que não possuem memória
virtual, ao invés disso, eles executam no modo kernel diretamente no
espaço de endereçamento físico.
O kernel swap daemon garante que exista suficientes paginas livres
no sistema para manter o sistema de gerenciamento de memória
operando eficientemente.
O kernel swap daemon (kswapd) é iniciado pelo kernel init processo
na inicialização do sistema
O swap daemon procura por processes no sistema que sejam um
bom candidate para troca. Bons candidates são processos que
podem ser trocados e que tenham uma ou mais paginas que podem
ser trocas ou discartadas da memória. Paginas são trocadas da
memória física para dentro do sistema de arquivos de troca somente
se os dados nelas não poderem ser obtidos de outras formas.
Uma vez que processo tenha sido localizado, o swap daemon
procura por toda a sua região da memória virtual em busca de áreas
quenão sejam compartilhadas ou protegidas.
Linux não troca todos as paginas trocáveis de um determinado
processo que foi selecionado. Ele apenas remove uma pequena
quantidade delas.
Páginas não podem ser trocadas ou discartadas se elas estiverem
bloqueadas na memoria.
O algoritmo de troca do linux usa idade das paginas. Cada página
tem um contando, que fica na estrutura de dados mem_map_t, o qual
indica ao kernel swap daemon alguma idéia sobre a vantagem da
troca. Idade diminue quando as paginas não são usadas e aumenta
quando acessadas; o swap daemon somente troca paginas antigas
(idade = 0).
O Linux pode usar tanto um arquivo normal de um sistema de
arquivos quanto uma partição separada para área de troca.
Uma vez que, o kernel utiliza páginas de memória de 4 kb de
tamanho, o tamanho ideal para área de swap deve ser múltiplo desse
número. O gerenciador de memória do Linux limita o tamanho da
área de troca em cerca de 127 MB. Pode-se porém utilizar até 16
áreas de troca simultaneamente, totalizando cerca de 2 GB.
Experimentos para explorar limites do sistema
Números de processos criados
A idéia para testar limite máximo de processos criados, devemos
fazer várias chamadas fork() para criação de novos processos. Esse
teste é conhecido também como fork bomb.
Um fork bomb funciona criando um grande número de processo
muito rapidamente em direção a saturação do espaço disponível na
lista de processos mantidos pelo sistema operacional. Se a tabela de
processos tornar-se saturada, nenhum novo programa pode
começar até que outro tenha terminado. Mesmo que isso venha a
ocorrer, não é provável que um programa útil venha a ser iniciado,
uma vez que as instancias do programa bomba tomaram para si a
posse de novo slot recém liberado.
Uma forma de implementar o fork bomb em C/C++ é:
#include 
int main(void)
{
 for(;;)
 fork();
 return 0;
}
Um fork bomb é uma forma de ataque DoS (Denial of Service). Uma
maneira de prevenir que o fork bomb derrube o sistema é limitar o
número de processos que um usuário pode ter. Quando o processo
tenta criar qualquer outro processo além do máximo permitido, a
criação falha. Sistemas baseados em Unix, como o Linux, tem uma
forma de limitar, com o comando ulimit:
ulimit -u 1000
Onde 1000 é o número de máximo de processos por usuário.
Tamanho do processo
Os comandos getrlimit e setrlimit obtém e modifica o limite de
recursos de um processo. Cada recurso tem associado um soft e
hard limit, e como definido pela estrutura rlimity
rlimit {
 rlim_t rlim_cur; /* Soft limit */
 rlim_t rlim_max; /* Hard limit (ceiling for 
rlim_cur) */
};
O soft limite é o valor que o kernel obriga ao correspondente recurso.
O hard limite atua como o teto para o soft limite, ou seja, um processo
sem privilégios pode somente modificar o valor do soft limite para um
valor na faixa de 0 ao hard limite.
Para verificar o tamanho máximo de processo devemos obter o valor
de RLIMIT_AS com o getrlimit().RLIMIT_AS é o tamanho máximo de
toda a memória disponivel de um processo, em bytes. Se esse limite
é excessivo, as funcoes malloc() e mmap() devem falhar e returner
um erro [ENOMEM].
Uma implementação possível é:
#include 
#include 
#include 
void max_process_size() {
 struct rlimit max_size_p;
 if(getrlimit(RLIMIT_AS, & max_size_p) == 0) {
 printf("Maximum size of process: %ld %ld\n", 
max_size_p.rlim_max, max_size_p.rlim_cur);
 }
}
Tamanho da área de heap
Podemos abstrair um processo e dividi-lo em três áreas: programa,
variáveis globais, pilha e heap.
A área de programa armazena o código executável. Na área de
variáveis globais são alocadas todas as variáveis globais e estáticas;
enquanto que a área de heap é reservada para alocação local e
dinâmica de memória. Finalmente, a área de pilha é usada para
salvar registradores, salvar o endereço de retorno de subrotinas, criar
variáveis locais bem como para passar parâmetros na chamada de
funções.
Para causar um overflow na heap e verificar o seu tamanho máximo,
é necessário alocar continuamente com a função malloc()
Uma possivel implementação para o ataque é:
#include 
#include 
int main() {
 int size_heap=0;
 void* p;
 whiel(p=malloc(size_heap) {
 size_heap++;
free(p);
 }
 printf(“Heap’s size is: %d\n",size_heap);
 return 0;
}
Área de pilha
Como já dito, uma área de endereçamento de pilha guarda
endereços de retorno de subrotinas. Assim, para testar os limites da
pilha, temos que colocar uma função com recursão praticamente sem
corpo.
Para verificar o tamanho da pilha de um processo, podemos dar um
getrlimit() em RLIMIT_STACK
Uma possível implementação é:
#include 
int size_stack = 0;
void function(void){
 printf("Stack size is almost: %d\n", ++size_stack);
 function();
}
int main() { 
 struct rlimit size_s;
 if(getrlimit(RLIMIT_STACK, & size_s) == 0) {
 printf("Size of stack is: %ld %ld\n", 
size_s.rlim_max, size_s. rlim_cur);
 funcao_recursiva();
}
Área de swap
Como já é de conhecimento, a área swap não é infinita, logo existe
um tamanho máximo para ela. É possível esgotá-la, causando
travamento no sistema.
Referencias