How to manage "dynamical collection" on persistent memory?

Go To Last Post
10 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi.

 

I'm trying to implement Dynamical size collection to EEPROM, which should support deletion from middle of it if/when needed, but write cycles should be kept in mind.

 

what i have thinked of is to reserve X amount of space from static location to have index what to load on system boot, and keep track of next free "slot" in the collection and such, but this doesn't support deletion of multiple items too well, would be easy to manage thought.

 

or i could reserve byte or two per entry in the collection and mark it as deleted, then always read it all to find out where to write next entry, maybe even always write new entry as last item of the collection until i have no choice than to overwrite allready deleted items .(i guess this help with the wearing of EEPROM since i don't have to write to same location so often) 

 

How would you do it?

  • Data size is constant per collection, was it uint8_t or typedef struct foo, the collection should only contain one type of entrys (i don't think re-ordering is the thing one wants to do when saving stuff in eeprom)
  • Efficient in terms of endurance of the eeprom and memory footprint.

 

This topic has a solution.
Last Edited: Fri. Aug 23, 2019 - 03:15 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

JoniS wrote:
How would you do it?

...

  • Efficient in terms of endurance of the eeprom and memory footprint.
MRAM

Serial Peripheral Interface | Everspin

 

"Dare to be naïve." - Buckminster Fuller

This reply has been marked as the solution. 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Things like FAT filling show interesting approaches to this kind of thing. The File Allocation Tables effectively keep a "map" of what is used and what isn't.  For EEPROM you could perhaps imagine an array of bits where each bit indicates if the corresponding byte is being used. Or perhaps the granularity of the storage is larger? Perhaps you always store a group of 4 or 5 bytes (a struct?) so now the 1 bit entries in the occupation map could indicate whole 4/5 bytes groups used / not used? In FAT16 for example one 16 bit word may show whether an entire 16KB or 32KB is occupied or not. Of course the downside of such a scheme is that even if only 1 byte is stored in an "allocation unit" an entire 16/32KB is marked as used.

 

To store a new "thing" you'd then scan the bitmap for the first "unused" marker then store the new data in  the corresponding entry (then mark that one active in the map). "Deletion" is the n simply a case of marking a bit as inactive (you can actually leave the "dead" data itself behind, filing systems do which is why forensics can find "deleted" data)

Last Edited: Thu. Aug 22, 2019 - 08:29 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

Things like FAT filling show interesting approaches to this kind of thing. The File Allocation Tables effectively keep a "map" of what is used and what isn't.  For EEPROM you could perhaps imagine an array of bits where each bit indicates if the corresponding byte is being used. Or perhaps the granularity of the storage is larger? Perhaps you always store a group of 4 or 5 bytes (a struct?) so now the 1 bit entries in the occupation map could indicate whole 4/5 bytes groups used / not used? In FAT16 for example one 16 bit word may show whether an entire 16KB or 32KB is occupied or not. Of course the downside of such a scheme is that even if only 1 byte is stored in an "allocation unit" an entire 16/32KB is marked as used.

 

To store a new "thing" you'd then scan the bitmap for the first "unused" marker then store the new data in  the corresponding entry (then mark that one active in the map). "Deletion" is the n simply a case of marking a bit as inactive (you can actually leave the "dead" data itself behind, filing systems do which is why forensics can find "deleted" data)

Using bit flags could work and should be quite straight forward to implement, it's 512kb eeprom sliced to 128byte pages, with ~15 pages I could map the whole memory with the data size i have in my current project.

This would also let me make it generic "driver" pretty easily, to re-use in future.

Only downside i can see is that the smaller the data size is the more it needs space to handle it, but way or other some sacrifice have to be made.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Does order matter?

If so, you will almost certainly need a linked list or some such.

Inserting or deleting an item will usually

require changing the link of another item.

If you are using an EEPROM as a substitute SRAM,

write amplification is an issue.

What is the granularity of a write?

If you have a 120 byte struct and a 64 byte page,

you should consider padding to 128.

How do you want to select items?

If you just need to step through all of them,

then you do not need much of anything.

You just need to be able to tell whether a slot is occupied.

 

What will most affect your performance and

endurance will be your caching system.

"Demons after money.
Whatever happened to the still beating heart of a virgin?
No one has any standards anymore." -- Giles

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Ordering of the entrys does not matter to me, it's just collection of different configuration data which needs to be loaded on power cycle or on demand(if user chooses to change settings runtime), and storing is also only on user demand so performance is not a concern, one can wait that some time.

It's mostly matter of finding a proper way to make general enought implementation which can be used across multiple projects as it is, or with minimal modifications.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

JoniS wrote:
and storing is also only on user demand so performance is not a concern, one can wait that some time.
In that case, almost anything would do: Ten writes per day is less than 4,000 per year.

I'd expect your EEPROM to last 25 years or more.

"Demons after money.
Whatever happened to the still beating heart of a virgin?
No one has any standards anymore." -- Giles

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

skeeve wrote:

JoniS wrote:
and storing is also only on user demand so performance is not a concern, one can wait that some time.
In that case, almost anything would do: Ten writes per day is less than 4,000 per year.

I'd expect your EEPROM to last 25 years or more.

 

Yes, in this project the endurance wont be a proplem if i don't introduce some really nasty bug.

 

I'm more conserned about "how to do it the correct way", better invest time in writing good re-usable code once than bad code multiple times, i did the mistake of hacking stuff together too many times in past which always did lead to spaghetti code all around and re-factoring was a nightmare.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I like your approach. The secret of good software is time spent in the design phase.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

I like your approach. The secret of good software is time spent in the design phase.

 

after thinking about the implementation i want it to be something simple as this at the "application level", what do you think could this work? 

class EmbeddedDB {
public:
	
	enum class EmbeddedDBStatus {
		Success,
		Fail,
		Full,
		Empty
	};
	
	EmbeddedDB(M95512_EEPROM eeprom, uint32_t size, uint16_t startAddr, uint16_t datasize);

	EmbeddedDBStatus Insert(uint8_t* data);
	EmbeddedDBStatus Get(uint8_t* dataout, "someother parameter");
	EmbeddedDBStatus Delete("some parameter");
	
}

Obviously it should accept any EEPROM library not just the one i wrote for the current software, i guess that needs a base class to derive from.