O tampão circular no Flash

Question

Eu preciso armazenar itens de comprimento variável em uma fila circular em um chip flash. Cada item terá o seu encapsulamento para que eu possa descobrir o quão grande ele é e onde o item seguinte começa. Quando há itens suficientes no buffer, ele vai embrulhar para o início.

O que é uma boa maneira de armazenar uma fila circular em um chip flash?

Há uma possibilidade de dezenas de milhares de itens que eu gostaria de armazenar. Então, começando no início e lendo até o fim do buffer não é o ideal, porque ele vai ter tempo para pesquisar até o fim.

Além disso, porque é circular, eu preciso ser capaz de distinguir o primeiro item do passado.

O último problema é que esta é armazenada em flash, assim apagando cada bloco é tanto demorado e só pode ser feito um número definido de vezes para cada bloco.

Answer 1

gestão Primeiro, bloco:

Coloque um cabeçalho menor no início de cada bloco. A principal coisa que você precisa para acompanhar o "mais velho" e "novo" é um número de bloco, que simplesmente incrementos módulo k . k deve ser maior que o número total de blocos. Idealmente, make k menor do que o seu valor máximo (por exemplo 0xFFFF), assim você pode facilmente dizer o que é um bloco apagado.

No arranque, o seu código lê os cabeçalhos de cada bloco, por sua vez, e localiza os primeiros e últimos blocos na seqüência que é n _{i + 1} = (n _i + 1) MODULO k. Tome cuidado para não se confundir com blocos apagados (número do bloco é por exemplo 0xFFFF) ou dados que são de alguma forma corrompida (apagar por exemplo incompleto).

Dentro de cada bloco

Cada bloco começa inicialmente vazio (cada byte é 0xFF). Cada registro é escrito simplesmente um após o outro. Se você tem registros de tamanho fixo, então você pode acessá-lo com um índice simples. Se você tem registros variável de tamanho, em seguida, lê-lo você tem que digitalizar a partir do início do bloco, estilo de lista ligada.

Se você quiser ter registros variável de tamanho, mas evite linear varredura, então você pode ter um cabeçalho bem definidas em cada registro. Por exemplo. usar 0 como um delimitador de registro e ESPIGAS -encode (ou COBS / R -encode ) cada ficha. Ou usar um byte de sua escolha como um delimitador, e 'escape' que byte se ele ocorre em cada registro (semelhante ao PPP protocolo ).

No arranque, uma vez que você sabe que seu último bloco, você pode fazer uma varredura linear para o último disco. Ou registros ou delimitadores de registro de tamanho fixo se você tiver, você poderia fazer uma pesquisa binária.

Apagar programação

Para alguns chips de memória flash, apagar um bloco pode levar um tempo significativo - por exemplo. 5 segundos. Considere agendar uma apagar como uma tarefa em segundo plano um pouco "antes do tempo". Por exemplo. quando o bloco atual é de x% completo, em seguida, começar a apagar o próximo bloco.

Gravar numeração

Você pode querer registros numéricos. A maneira que eu tenho feito isso no passado é colocar, no cabeçalho de cada bloco, o número de registro do primeiro registro. Então, o software tem que manter a contagem dos números de cada registro dentro do bloco.

Checksum ou CRC

Se você quiser detectar dados corrompidos (por exemplo incompleta escreve ou apaga devido à falha de energia inesperada), então você pode adicionar um checksum ou CRC para cada registro, e talvez para o cabeçalho do bloco. Observe o cabeçalho do bloco CRC cobriria apenas o próprio cabeçalho, e não os registros, uma vez que não poderia ser quando cada novo registro é gravado re-escrita.

Answer 2

Mantenha um bloco separado que contém um ponteiro para o início do primeiro registro e no final do último registro. Você também pode manter mais informações como o número total de registros, etc.

Até que você inicialmente ficar sem espaço, acrescentando registros é tão simples como gravá-los no final do buffer e atualizar o ponteiro cauda.

Como você precisa para recuperar o espaço, excluir registros suficientes para que você pode ajustar o seu registro atual. Atualizar o ponteiro cabeça como você excluir registros.

Você vai precisar para manter o controle de quanto espaço extra foi libertado. Se você manter um ponteiro para terminar do último registro, a próxima vez que você precisa adicionar um registro, você pode comparar isso com o ponteiro para o primeiro registro para determinar se você precisa excluir qualquer mais registros.

Além disso, se este é NAND, você ou o controlador de flash vai precisar fazer desbloqueio e nivelamento de desgaste, mas que devem ser todos em uma camada mais baixa do que a alocação de espaço para o buffer circular.

Answer 3

Eu acho que eu entendo agora. Parece que o seu maior problema será, depois de ter preenchido o espaço disponível para a gravação, o que acontece? Os novos dados devem substituir os dados mais antigos, o que é que eu acredito que você entende por um buffer circular. Mas desde que os dados não é fixo comprimento que você pode substituir mais de um registro.

Estou assumindo que a quantidade de variabilidade de comprimento é alta o suficiente para que o preenchimento de tudo para um comprimento fixo não é uma opção.

Seu segmento de gravação precisa manter o controle do endereço que representa o início do próximo registro para gravação. Se você souber o tamanho de um bloco para escrever antes do tempo, você pode dizer se você está indo para acabar no final do buffer de lógica e começar de novo em '0'. Eu não iria dividir um registro com alguns no final e alguns no início.

Um registo separado pode acompanhar o início; Estes são os dados mais antigo que não tenha sido substituído ainda. Se você foi para ler os dados isto é onde você iria começar.

O escritor de dados, em seguida, iria verificar, dado o endereço write-start e o comprimento dos dados a sua prestes a cometer, se ele deve bater o registo de leitura, o que iria examinar o primeiro bloco e ver o comprimento, e avançar para a próxima gravar, até que haja espaço suficiente para escrever o que os dados são. Haverá um intervalo de dados de lixo que vive entre o fim dos dados gravados e o início dos dados mais antigos, provavelmente. Mas desta forma, você pode apenas estar escrevendo um endereço ou dois como a sobrecarga, e não reorganizar blocos.

Pelo menos, isso é provavelmente o que eu faria. HTH

Answer 4

Eu vejo três opções:

option1: é para preencher tudo para fora para o mesmo tamanho, isso é simples, armazenar um ponteiro para a cabeça ea cauda do buffer para que você saiba onde escrever e onde começar a leitura de, use o tamanho de cada objeto para se um deslocamento para o próximo, isso significa que você precisa para atravessar a reserva como se fosse uma lista ligada, aka seu lento se você precisar de item de 5000.

opção2: é armazenar apenas ponteiros para os dados reais no buffer circular, que forma, quando você volta ao redor você não tem que lidar com tamanho mis-matchs. se você armazenar os dados reais em um buffer circular e não fazê-pad-lo para fora, você poderia correr em situações onde o seu mais witting vários itens com um novo objeto de dados, eu assumo isso não é ok.

armazenar os dados reais em outros lugares em flash, mais flash irá ter algum tipo de nivelamento de desgaste embutido, se assim você não precisa se preocupar com a substituição no mesmo local várias vezes, o IC vai descobrir onde realmente armazená-lo no chip, basta escrever para o próximo espaço livre disponível.

Isto significa que você precisa escolher um tamanho máximo para o buffer circular como você faz isso depende da variabilidade dos dados. Se o tamanho dos dados apenas mudar muito, dizem que por apenas alguns bytes, então você deve apenas pad-lo e usá opção 1. Se o tamanho muda descontroladamente e imprevisível, escolher o maior tamanho que poderia ser e descobrir quantos objetos desse tamanho iria caber no seu flash, usar isso como o número máximo de entradas no buffer. Isto significa que você perder um monte de espaço.

Opção 3: se o objeto pode realmente ser de qualquer tamanho, o seu no ponto onde você deve apenas usar um sistema de arquivos, nomeie os arquivos em ordem e loop de volta quando a sua manutenção integral em mente, se sua nova entrada é grande você pode tem que apagar várias entradas antigas para ajustá-lo. Isto é realmente apenas uma extensão da opção 2 como opção2 é em muitos aspectos um sistema de arquivos simples.

Answer 5

O "circular" em um flash pode ser feito com base em tamanho do bloco, o que significa que você deve declarar o quanto os blocos do flash você alocar para este buffer.

O tamanho real do tampão será em cada momento particular entre N-1 (n é o número de blocos) e n.

Cada bloco deve começar com um cabeçalho que contém o número sequencial ou timestamp que poderia ser utilizado para determinar qual bloco é mais velhos do que o outro.

Cada item encapsulado com um cabeçalho e um rodapé. o cabeçalho padrão contém o que quiser, mas de acordo com este cabeçalho você deve saber o tamanho do item. O rodapé padrão é 0xFFFFFFFF. Este valor indica uma terminação nula.

Em sua memória RAM você deve salvar um ponteiro para o bloco mais antigo e o mais recente bloco e ponteiro para o item mais antigo e mais recente item. Ao ligar você passar por cima de todos os blocos de encontrar os blocos relevantes e carregar esse membros.

Quando você quiser armazenar um novo item, você verifique se o último bloco de conter espaço suficiente para este item. Se isso acontecer você salvar o item no final do item anterior ea mudança no rodapé anterior para apontar para este item. Se ele não contém espaço suficiente, você precisa apagar o bloco mais antigo. Antes de apagar este bloco mudar os membros mais antigos do bloco (RAM) para apontar na próxima quadra e o item mais antigo a ponto sobre o primeiro item de participação neste bloco. Então você pode salvar o novo item neste bloco e alterar o rodapé do último item para apontar este item.

Eu sei que a explicação pode parecer complicado, mas o processo é muito simples e se você escrevê-lo corrigir você pode torná-lo ainda poder fail safe (sempre ter em mente que você a ordem das gravações).

Preste atenção que a circularidade do buffer não é salvo no flash, mas o flash contém apenas blocos com itens que você pode decidir de acordo com os blocos de cabeçalhos e itens cabeçalhos Qual é a ordem desses itens