Gerenciamento de memória no linux

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.

descricao1

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.

descricao2

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 <asm/page.h>.
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.

tabelapagina1

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.

algoritmo1

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.

algoritmo2

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 <kernel/fork.c> e <kernel/exit.c>. 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.

interfaces1.jpg

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.

interfaces2.jpg

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.

compartilhamento1.jpg

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.

tratamento1.jpg

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.

seguranca1.jpg

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 que nã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 <unistd.h>

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 <sys/resource.h>
#include <stdlib.h>
#include <stdio.h>

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 <stdlib.h>
#include <stdio.h>

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 <stdio.h>

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License