3 Comentários

TLSF - Gerenciador de memória em tempo real para sistemas embarcados

tlsf

Olá caro leitor, não, eu sei, este não é mais um post sobre controle digital ou processamento de sinais, fato é que além desses dois ramos super legais relacionadas a engenharia embarcada, estou também a compartilhar técnicas e soluções de firmware do meu dia-a-dia. No assunto de hoje falaremos sobre um tópico polêmico no ponto de vista de software para máquinas de poucos recursos, memória dinâmica! Sim, você não entendeu errado, aquele malloc() e free() que professores e colegas de profissão nos dizem pra nunca usar pelos mais variados motivos. Apresentaremos aqui um pequeno gerenciador de memória capaz de operar em tempo real (ou seja, ele garante o tempo de execução constante para qualquer que seja o tamanho do bloco desejado) e com bons resultados em termos de desperdício de memória, a fragmentação. Eis que o gerenciador é chamado TLSF - "Two Level Segregate Fit".

Mas vale a pena usar alocação dinâmica em um sistema embarcado?

Provavelmente essa deve ser a primeira pergunta que o leitor deve fazer. Como já disse antes esse é um assunto cujas opiniões divergem bastante entre profissionais, entusiastas e professores. Muitos dizem que é legal possuir uma forma de reservar memória e liberar depois para uso futuro, outros postulam em jamais usar tal técnica por causa dos overheads envolvidos, e pelo perigo de alocar memória sem liberar depois e bagunçar todo o Heap (região comumente reservada no linker para ser usada para alocação e liberação dinâmica). O objetivo deste artigo não é discutir quem está certo mas sim assumir que usar alocação dinâmica em sistemas embarcados de tempo real pode ser interessante e apresentar uma alternativa a alguns dos desafios que esse tipo de módulo costuma oferecer na sua implementação. Para estimular o leitor, a alocação dinâmica de memória tem basicamente alguns benefícios a seguir:

  • Reutilização de memória em caso de variáveis temporárias (exemplo, structs criadas somente dentro de uma função);
  • Facilidade para implementação de estrutura de dados de tamanhos variáveis (Queues ou Stacks baseados em listas ligadas);
  • Ajuda demais a implementar tópicos de orientação a objeto;
  • Especificamente o TLSF pode susbtituir o operador new em C++ (ou outra linguagem), tornando a criação de objetos computacionalmente mais leve.

Ok, de posse dessa visão a respeito de gerenciar memória em vez de alocar todas as nossas variáveis em tempo de compilação, vamos dar uma olhada no que o TLSF tem para nos oferecer em termos de diferencial.

O gerenciador de memória com complexidade O(1)

Quem já utilizou gerenciamento de memória em algum projeto de firmware, sabe que esse tipo de módulo possui alguns desafios de implementação. O primeiro que vem à cabeça é justamente a incerteza do tempo de execução, ou seja, ao efetuar um malloc() o tempo que essa função irá levar para executar vai variar demais em função do tamanho do bloco solicitado e do estado da região usada como heap, podendo levar ora 10 ciclos, ora 100. Esse tipo de comportamento é inadmissível para um sistema de tempo real, ah e detalhe, pode variar sua execução e ainda pode retornar uma belo ponteiro nulo representando que está sem memória, frustrante não?

O segundo ponto que envolve constantemente o uso do gerenciador de memória, é o quão bem ele a gerencia. Após uma bateria de execução de malloc() e free() qual a porcentagem da região do heap continua reutilizável, ou seja, quanto dessa região foi fragmentada. O terceiro ponto trata do overhead necessário para gerenciar um bloco de B bytes, ou seja, além da região de memória de tamanho B bytes que queremos gerenciar, quantos bytes extras devo adicionar a essa região para armazenar as estruturas de controle da memória a ser gerenciada. O quarto e último ponto trata da política da adequação do tamanho de bloco obtido ao tamanho requisitado, podendo ser:

  • Best Fit: O bloco possui exatamente o mesmo tamanho do que foi requisitado, ignorando qualquer problema de desalinhamento de memória, permitindo assim zero de desperdício de heap;
  • Good Fit: O bloco possui o tamanho pelo menos igual, ou maior ao requisitado, sendo adequando mas tolerando algum desperdício para lidar com problemas como desalinhamento de memória;
  • First Fit: O bloco requisitado possui tamanho pelo menos igual ou maior à necessidade, sendo o primeiro bloco a satisfazer essa condição, ignorando qualquer possível problema com desperdício de memória.

Agora que conhecemos um pouco os desafios de se implementar um gerenciador de memória (em especial em sistemas embarcados), apresentamos o gerenciador TLSF, escrito originalmente por Miguel Masmano. Como sua tese de doutorado, ele implementou um gerenciador de memória que contorna muito bem todos os desafios apresentados, sendo suas principais características:

  • Tempo real: O tempo de execução para alocar e desalocar memória é sempre constante, independente do tamanho do bloco requisitado;
  • Razoável em termos de fragmentação, chegando em torno de 15% da área reservada como heap;
  • Baixo overhead de memória, necessita apenas de uma estrutura de controle no começo do heap;
  • Política de alocação Good-Fit, garantindo um bloco de tamanho adequado com baixo desperdício de memória.

TLSF, como funciona?

O leitor mais curioso pode acessar a tese de doutorado inteira de Miguel Masmano. Do documento em questão vamos extrair os fundamentos de como o TLSF consegue atingir o tempo de execução constante (a principal variável em um sistema de tempo real). Masmano percebeu em outros alocadores baseados em listas segregadas, como o conhecido DLMalloc, que ele poderia acelerar a busca de um bloco de tamanho aceitável se subdividisse a região de heap em um grupo de listas de dois níveis, sendo o nível mais alto para os intervalos de tamanhos incrementais em potência de base 2, e o segundo nível como sendo blocos dentro de cada intervalo somado a um offset de 4 bytes (tamanho mínimo permitido na alocação) para cada bloco.

Esses blocos são acessíveis na forma de ponteiros e armazenados em um vetor bidimensional. Mas e aí, como acessar o bloco desejado em tempo de execução constante? Diferente de alocadores como o Binary Buddy e o DLMalloc, que possuem um loop de busca similar a uma busca binária para acessar os níveis e subníveis de suas listas segregadas, Masmano utilizou uma estratégia baseada na localização de posição de bits do tamanho do bloco requisitado. Assim como as listas segregadas estão ordenadas por potência de base 2 sabemos que cada bit em um word corresponde imediatamente a uma dessas potências. Então o gerenciador mapeia através do primeiro bit mais significativo colocado em 1 o tamanho de base do bloco. A posição desse bit será utilizada para mapear o primeiro nível da lista segregada. O segundo nível, menos elementar, é mapeado através de uma segunda aritmética de bits entre o primeiro nível, os bits menos significativos e uma terceira variável constante que trata da profundidade da lista segregada de segundo nível. Os dois resultados são combinados e concatenados, formando os pares de acesso ao vetor bidimensional de ponteiros e assim otendo-se o bloco livre (se houver) ou nulo, caso não haja mais espaço.

A liberação de um bloco de memória que não é mais necessário ocorre de forma similar, porém oculto ao bloco usado. Pode ser acessado o tamanho do bloco juntamente com endereço do bloco livre prévio. A partir do tamanho, é possível atualizar o mapa de bits da estrutura de controle do heap, e verificar se o bloco prévio é adjacente ao bloco que estamos liberando, permitindo realizar fusão e obter um bloco maior de memória livre (durante a alocação o inverso é feito caso o bloco obtido seja muito grande). Na figura abaixo podemos ver o que fisicamente é realizado na memória gerenciada: 

tlsf: listas segregadas
Figura 1: Listas segregadas usadas no TLSF

Eis o que acontece no heap, temos os dois níveis, vejam que o primeiro é bem separado nas potências de base 2, com ele acessamos primeiramente um segundo mapa de bits, onde contém blocos naquele intervalo somado algum offset em bytes. Uma vez que o bloco seja alocado, o mesmo é colocado em uma lista ligada segregada que aponta ao bloco prévio livre e guarda algumas informações sobre tamanho e uso. E quando desalocado, o mesmo é colocado de volta em sua lista com nível e subnível correspondente.

Implementando o gerenciador de memória TLSF

O documento com a tese de doutorado de Masmano descreve em detalhes, bem como o passo-a-passo para implementar as funções malloc() e free(). A função realloc(), até a escrita deste texto, não era suportada. O documento descreve as funções de busca e as operações de bits necessárias para mapear um bloco no heap. O pseudo-código encontra-se escrito em algo similar à linguagem Pascal, contudo esse gerenciador se tornou popular e acabou ganhando versões que vão, inclusive, embarcadas em distribuições do kenel Linux como Crux, patchs como o Xenomai e vários kernels de tempo real. Com isso implementações mais simples e mesmo em outras linguagens como o popular C, estão disponíveis a partir do trabalho de Masmano.

Esse que vos escreve implelementou uma versão do gerenciador TLSF para uso pessoal (que será embarcado no futuro RTOS que pretendo soltar ano que vem) mínima, apenas com as funções de alocação, liberação, inicialização e quantidade de bytes disponíveis no heap, sendo indicado pra quem quer colocar gerenciamento de memória naquele projetinho de final de semana com ARM, ou mesmo substituir o operador "new" e usar com seu Arduino. Lembrando que o valor mínimo de um bloco pode ser de 4 bytes e o tamanho máximo é limitado ao tamanho reservado para o heap (que pode ser feito via linker, ou estaticamente).

Abaixo temos o arquivo tlsf.c:

Nesse arquivo temos o ponto onde a mágica ocorre, as funções do algoritmo implementado pelo autor original bem como algumas macros para facilitar a inserção e retirada de blocos. As funções públicas estão ao final e permitem a implementação de mecanismos de sincronização como Mutex ou Semáforos  ao acessar o heap. Abaixo temos tlsf.h:

Esse arquivo é o famoso "glue module", ou seja, pega todas as funções que podem tornar-se públicas, e junta tudo num único lugar, bastando o usuário incluir esse arquivo no seu projeto que estará apto a utilizar o gerenciador de memória. Logo abaixo temos o arquivo bits.c:

Esse é uma interface para as funções de posição de bits, seu objetivo é apenas servir como camada de abstração caso o desenvolvedor queira implementar versões otimizadas dessas funções, utilizando o hardware do processador para isso. No caso da implementação, isso foi feito gerando o arquivo bits_a.S abaixo:

Não torça o nariz pro código Assembly, caro leitor. Ele é auto-explicativo, apenas foram aproveitadas duas instruções por hardware do processador (no caso um ARMv7-M) para fazer a busca de bits de forma rápida. Mas caso não seja o seu caso, você pode implementar dentro de bits.c seu próprio algoritmo de posição de bits, vejam aqui.

E abaixo, temos uma pequena forma de como tal código pode ser utilizado, se o leitor tiver um ambiente previamente montado com o QEMU configurável é possível ver esse trecho de código em ação:

Descrevendo rapidamente, a função HeapInit() é responsável por receber e inicializar uma área de memória para ser usada com o TLSF, lembre-se que diferentemente do exemplo, que a área de memória está reservada de forma estática. Podemos fazer com que isso seja transparente à aplicação, criando um .section correspondente no arquivo de ligação (os famosos .ld usados pelo Linker), as demais linhas são auto-explicativas, com impressão de strings no console (dai o uso do QEMU, zero necessidade de configurar o stdout) para ver o estado do heap antes e depois da alocação de memória.

Conclusão

Ok, sabemos que mesmo com um gerenciador como o TLSF, que possui execução em termo de tempo constante, tendo baixo overhead e magnitude de fragmentação, todo e qualquer gerenciador de memória deve ser usado com cautela, estando grande parte dela a cargo do programador. Pois sem as devidas providências de segurança e prevenção de acesso múltiplo ao heap o resultado pode ser frustrante, fazendo o leitor acabar mais cedo lendo o artigo sobre debug de hardfault. Mas se bem utilizado, um módulo que reserva e desaloca memória em tempo de execução, pode ser bem poderoso sendo útil em casos onde o Arduino é utilizado, pensem na possibilidade de substituir o operador "new" por uma forma rápida e real time de pegar memória do sistema para implementar objetos dos mais variados tipos e com máxima flexibilidade. E você leitor, o que acha dessa opção? Até a próxima.

Referências

MASMANO, Miguel - Gestion de Memoria Dinámica em Sistemas de Tiempo Real, 2007

LEA, Doug - A Memory Allocator, 1995

Alocador "Binary Buddy"

CRUX Linux

Xenomai, Real Time Framework for Linux

Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Receba os melhores conteúdos sobre sistemas eletrônicos embarcados, dicas, tutoriais e promoções.

Software » TLSF - Gerenciador de memória em tempo real para sistemas embarcados
Talvez você goste:
Comentários:

3
Deixe um comentário

avatar
3 Comentários
0 Respostas
0 Seguidores
 
Discussão de maior alcance
Discussão mais quente
3 Autores de comentários
Gabriel SantosSergio PradoMax Prass Comentários recentes
  Notificações  
recentes antigos mais votados
Notificar
Max Prass
Visitante
Max Jeison Prass

Primeiramente, parabéns pela implementação. Ela realmente é muito complexa! Estou tentando executar o TLFS que você disponibilizou para avaliar desempenho, fragmentação, etc. Mas tive dois problemas. A primeira é que não possuo a função 'optMemSet', o que ela faz é inicializar o array com zeros, eu poderia fazer assim? "int array[i] = { 0 }". A outra questão, não sei se foi problema do optMemSet, mas enfim, ocorre problema na inicialização do heap, especificamente na macro "INSERT_BLOCK", o erro é a que segue: "Exception thrown at 0x000320C3 in c.exe: 0xC0000005: Access violation writing location 0x0003AFAC." Para conseguir ver exatamente em… Leia mais »

Gabriel Santos
Visitante
Gabriel Santos

Parabéns pelo artigo!

Já tem algum tempo que eu estou tentando iniciar este tipo de aplicação para embarcados mas sempre senti falta de algo concreto para começar estudar.
Muito esclarecedor!

Sergio Prado
Visitante

Ótimo artigo Felipe!

Séries

Menu