Algoritmo leve de registro circular (tipo sistema de arquivos) para armazenamento baseado em flash

8

Atualmente, estou trabalhando em um projeto que envolve o registro rápido e contínuo de uma métrica específica do aplicativo durante uma longa vida útil. Para fazer isso, acabei usando um NXP M0 e um chip flash 32MiB SPI. O registro é contínuo e precisa durar muitos anos no campo (10+), e é verificado periodicamente por um ser humano para detectar tendências. Eventualmente, o buffer é preenchido e começa a sobrescrever dados antigos, o que é perfeitamente correto. Eu vim com um algoritmo simples para percorrer todo o dispositivo flash e encontrar a cabeça atual após uma inicialização (o dispositivo é desligado com frequência fora do meu controle), para que o registro possa continuar de onde parou. Eu posso apenas força bruta nessa caminhada e fazê-lo com ~ 4s no pior cenário possível.

Isso me fez pensar: existem sistemas de arquivos estruturados em log que são fornecidos para dispositivos flash e microcontroladores? O JFFS e todos os outros FSs estruturados em log bem conhecidos que eu imagino seriam um pouco pesados ​​para um microcontrolador simples (depende da aplicação, é claro). Para ser mais específico, eu gostaria de saber sobre qualquer algoritmo projetado para ser especificamente um log circular com tempo de busca rápida e / ou qualquer um projetado para um sistema de arquivos "tradicional" em um dispositivo flash que possa ser executado em um microcontrolador. Tradicional nesse sentido, é parecido com o JFFS, onde há uma estrutura de dados que representa uma coleção de arquivos de acesso aleatório mutáveis ​​em um espaço de nome hierárquico.

Kris Bahnsen
fonte
FAT32 ou FAT16 em um cartão SD é muito lento?
vicatcu
2
Esta questão é totalmente sobre tópico aqui, mas se você não obtiver ótimas respostas, provavelmente o StackOverflow pode ajudar. Vamos esperar que possamos obter boas respostas aqui!
24412 Kellenjb
@vicatcu Não é muito lento, para o meu aplicativo o cartão SD mais o conector é mais caro e os cartões SD podem ser menos confiáveis. Kellenjb Eu não tinha certeza de onde colocá-lo. Como muitas questões de design incorporadas, esse tipo de coisa cai no meio. Se não der certo aqui, eu ficaria feliz em movê-lo.
Kris Bahnsen
É um chip flash bruto? Se sim, como você lida com blocos mortos? Grande parte do negócio de implementação flash do FS com blocos mortos. Se você acha que o JFFS / JFFS2 é muito pesado, convém verificar o YAFFS. Parece um sistema de arquivos muito simples, pelo menos, por isso deve ser bastante leve.
31312 Leo
Sim, ele é. Blocos defeituosos não são terríveis nesse aplicativo em particular, pois são tão longos que os dados extraídos são apenas uma tendência aproximada e, na maioria dos casos, duvido que o registro seja usado.
Kris Bahnsen

Respostas:

2

estrutura de dados da corda

Eu sou fascinado pela estrutura de dados da corda. Eu tenho um projeto de hobby tentando adaptá-lo a um microcontrolador com apenas alguns bytes de RAM conectados a uma enorme memória Flash, para que eu possa inserir e excluir e editar arbitrariamente texto de tamanho variável em grandes arquivos de texto. Arquivos de texto muito grandes para caber na RAM. Apagar a última metade do arquivo e reescrevê-lo para piscar, alternado em um byte, toda vez que insiro ou excluo um caractere no meio de um arquivo de texto com vários megabytes, seria muito lento, mas a estrutura de dados da corda pode fazer isso muito mais rápido. Como a estrutura de dados da corda pode representar arquivos de tamanho variável de acesso aleatório mutáveis, como pedaços imutáveis ​​de comprimento fixo, parece ser uma boa combinação para a memória flash - todas as edições são escritas de maneira circular. Infelizmente, todos os erros ainda não foram resolvidos no meu código. :-(

toras cronológicas de comprimento fixo

Consegui um sistema circular circular semelhante para um produto que ajudei a desenvolver.

Simplesmente escrevi registros de comprimento fixo, um após o outro, preenchendo o flash como uma matriz circular.

(Com um flash completamente em branco, comecei a gravar registros cerca de três blocos antes do final da matriz, para poder testar o contorno circular depois que apenas alguns registros de dados foram armazenados, em vez de começar no registro zero e aguardar um dados do mês a serem gravados antes de descobrir que havia um erro no meu código de contorno).

Eu me certifiquei de que sempre houvesse pelo menos 2 "blocos de apagamento" apagados, prontos para serem gravados. Depois de gravar um registro, se houvesse apenas 2 "blocos apagados" depois dele, eu apagaria incondicionalmente o bloco de dados mais antigo - o terceiro bloco de dados mais antigos depois dos 2 "blocos apagados". (Perto do final da memória flash, "depois" significa "envolver até o início da memória flash.) (Talvez um único bloco apagado fosse adequado - esqueço por que pensei que precisava de pelo menos 2 e às vezes 3) .

Esqueço exatamente quantos registros coloquei em cada "bloco de apagamento", mas assegurei-me de nunca ter um registro montado em dois blocos de apagamento - os primeiros 2 bytes de cada bloco de apagamento do flash eram o valor "apagado" 0xFFFF, ou os dois primeiros bytes de uma soma de verificação Fletcher-16 (que nunca é 0xFFFF) no cabeçalho de cada registro.

Isso tornou rápido a varredura na próxima vez em que foi ligada e o cabeçalho do log circular - eu só precisei olhar nos dois primeiros bytes de cada bloco de apagamento para distinguir entre os blocos "apagados" e "dados". (Eu estava um pouco preocupado com "falta de energia no meio da exclusão de um bloco", fazendo com que os dois primeiros bytes fossem apagados em 0xFFFF, mas deixando bytes não apagados no meio do bloco, então escrevi o código para o microcontrolador verificar para isso e reinicie o processo "apagar um bloco").

Diga-me se você encontrar outras estruturas de dados ou sistemas de arquivos compatíveis com flash.

davidcary
fonte
Sua abordagem parece um pouco semelhante à minha. Eu sugeriria adicionar outra reviravolta, no entanto: reserve alguns bytes em cada bloco para indicar que ele foi "iniciado" e "cheio". Todos os blocos, exceto os apagados, devem ter os bits "iniciados" programados. Quando chegar a hora de apagar um bloco, defina o byte "completo" no último byte de dados, apague o bloco e defina imediatamente o bit "iniciado" do bloco apagado mais antigo. Na inicialização, se você vir que o "último" bloco está "cheio", em vez de "iniciado", refaça a exclusão.
Supercat 13/03/12
Essa abordagem pode parecer um exagero, mas se um bloco flash for parcialmente apagado, é possível que os bytes decidam arbitrariamente ler FF ou outra coisa. O fato de um bloco aparecer em branco não garante que os bits não "apareçam" espontaneamente lá. Se você perder energia enquanto uma exclusão estiver em andamento, aguarde um pouco na próxima inicialização e repita a exclusão mesmo se o bloco aparecer em branco .
Supercat 13/03
Obrigado pela informação, examinarei um pouco mais a fundo quando eu clicar no código do armazenamento em flash e informar o que acontece.
Kris Bahnsen
@ supercat: Obrigado, isso parece uma ótima idéia.
Davidcary
@ DavidDary: Eu não sei se eu já tive um bloco que parecia totalmente em branco e não era, mas eu tive um bloco que produziria resultados diferentes em leituras consecutivas. É possível que o bloco tenha sido lido incorretamente como em branco. Meu código tentou programá-lo de qualquer maneira, resultando em uma estranha mistura de novos dados programados e lixo velho de apagamento interrompido. De qualquer forma, um cenário em que um bloco às vezes aparece em branco dificilmente é realista.
Supercat 17/03
0

Já faz alguns anos, mas eu queria acompanhar isso, caso alguém passasse por lá. Parece que existem alguns projetos hoje em dia, que são mantidos ativamente (a partir de janeiro de 2020) que são sistemas de arquivos destinados a microcontroladores direcionados ao flash NOR SPI.

Observe que eu não os testei em nenhuma capacidade, mas eles fazem exatamente o que a pergunta original estava procurando: "... estrutura de dados que representa uma coleção de arquivos de acesso aleatório mutáveis ​​..."

https://github.com/ARMmbed/littlefs - Criado por ARM, BSD licenciado

https://github.com/joembedded/JesFs - Não parece realmente licenciado, mas foi projetado especificamente para o flash SPI NOR.

Kris Bahnsen
fonte