Shared EEPROM storage management across multiple apps

One thing to consider with a self managing EEPROM system is the amount of code required to do the “messy work” of allocating and locating frames. The Arduboy is very limited for code space, and people will want as much as possible to provide more levels, better graphics, longer music scores, etc. A system that eats up a lot of code just to provide a few bytes of EEPROM isn’t going to fly for some people.

My method requires manual management of EEPROM space using “pen and paper” (or the equivalent spread sheet, or possibly an offline program), but it has very little code overhead at runtime.

The method used will have to trade off between convenience and code size.

If you write directly, without going through an API, it could make things difficult for porting to a nonlinear or abstracted storage space, such as an SD card with a file system. And even with EEPROM, using direct access could require modifying the sketch if we decided to change the block size in the future.

Are you still proposing fixed length blocks? If so, what happens if a sketch needs space larger than one block? How will that be managed? If blocks must be contiguous, how do you prevent fragmentation and lost space due to small gaps?

Again, the code required to manage the sequence numbers and handle allocation when all frames are in use will use precious space.

Running short of code space is an outlier situation. You are already short on code, so you will be cutting corners every where you can. Rather than fussing with an API at all you will be writing custom methods to get the job done. No API of any kind would be used in this case. Your library already foots the bill.

API’s are for developers who are new to the topic, or who are looking for the convenience. It is also a way of encouraging standardization. Something that an off line spread sheet would not accomplish. The byte count for the code should be minimized, but that should not be the goal. Ease of use and standardization should be.

Porting? Again, if your app is running short on space, you are cutting corners every where you can. Porting to another system isn’t a consideration in this case. Porting is another application for an easy to use API.

What I am suggesting is continuous block of fixed length frames, managed by a block count byte rather than a linked chain. This idea matches you goal of smaller and faster code in the API. The storage would be inefficient, but not drastically so. You would either have enough continuous blocks or you wouldn’t. If you didn’t you would just commandeer blocks from other apps until you found a large enough continuous block. Not as nice as modern paging, but the trade offs in the long run on a system that can only have one app loaded at a time would be minor. An app that needs lots of eeprom slots, needs a lot of eeprom slots. Its going to disrupt things regardless of how it is organized. An added benefit is that with a continuous block is that you have much more control over the structure of your storage. You can make the code accessing it as tight, and fast as you need.

The code required to manage sequencing would be minor. And it would provided for a logical way of removing older blocks. A single byte of reserved eeprom memory. A single byte in each block of frames. And then a for loop that is run only once after the program is loaded.

My proposal would have a largish (by Arduboy standards) and complex Initialization method. But that is it. Once your app has its needed block of memory, staring point and length, accessing it would take almost nothing from the code segment.

Space is precious, yes. But so is development time. Those who are willing to trade a little space for ease of use would use the API being discussed here. Those who are only interested in space would write their own, or use the one you have already provided.

So now you’ve got some really nice games that walk all over the EEPROM that uses the API, and games using the API walking all over the games that do it their own way.

Therefore, for ease of use, you may as well just let everyone use the EEPROM calls directly and do it however they want, and we just recommend that all sketches have #defines with standardized names at the beginning, which set the start address and length of EEPROM space they’re using.

At least by standardizing on the names for the #defines, a script could be written that walks though all the sketches in your Sketchbook and outputs a report on what each sketch is using.

By just using the standard Arduino EEPROM functions you can easily write and read any variable or structure you like in one operation using EEPROM.put() and EEPROM.get()

Ummmm… No.

Those ideas do not lead from one to the other. Your spread sheet idea, or compiler based utility would not prevent people from miss using the eeprom. Quite the opposite. Someone looking to set up a save system for their game isn’t going to want to negotiate for a few frames. No, they are just going to choose a location at random and write the data.

Just like I did for the high score system in the game I’m writing. Without something automated, it does not matter how efficient it is, no one is going to use it.

And off device automation isn’t a solution either. Ignoring how uncomfortable your average developer will be having an automated system modifying source code… As the push for installing games without the compiler comes through, scanning the source code will stop even being an option.

And remember, we are not talking about a multi taking system with gigabiyts of storage. We are taking about a system with 1kilobyte of save space, and the ability to load only a single game.

Any developer can use the direct write commands right now. There is nothing to stop them. Nothing. Absolutely nothing. Nothing we discuss or decide here will change that in any way.

Without enforcement, discussion of edge cases, and violations are a meaningless waste of time.

And this is a good thing. It is the reason we all plunked down the money for the Arduboy in the first place.

So again, the eeprom api should be kept tight, but it should focus on ease of use. This ease of use is what will encourage developers to stick to the standard we decide on. Which is why I suggested blocks of frames rather than linked frames. Easier to use, resulting in tighter code, that is more likely to be used by developers.

1 Like

I worked up a detailed algorithm for the EEProm initialization routine. This is where all the complexity will hide. While it may seem a bit complex this should represent two loops and four to five if statements. With this in
place the read and write routines should be fall of the log simple. I made some assumptions concerning how the EEProm block will be formatted (copied at the bottom). The first frame is reserved for the Arduboy and the frame manager. The second through fourth frames are reserved for general purpose and are not assigned to apps. This is for apps that just want to save the game state, or a single high score and have no interest in data persistent across reinstalls of the apps. I image this will be most apps. Or, I imagine that most apps will use this area for game state and other fleeting data, and only use the frames for High Scores, level achieved and other persistent data.

This general use area is also ideal for developers who want to keep their code small as there is no need to include this API to access it.

EEPromManager::Initialize() Algorithm

//------------------------------------------------------------------------
// Goal of initialization: - Set the offset address and length for the
// block in the EEProm frames this app will be using. If not found, set up
// a new block.
//
// 1) obtain the number from the first frame. Check
// the frame for the matching app id. If found, set the global variables
// for offset and length, and return. No further processing needed
// == After first run of the app, this is all that will be needed. ==
// 2) obtain the systems < FrameSequenceNum > from the first frame.
// increment the value. This will allow us to track how recently this
// app was previously installed, and which other app needs to be removed
// if space is needed.
// 3) Search for the ID of the current app. If found set the globals for
// the offset and length of the frame block needed by this app. Update
// the sequence number to match the systems sequence number. Update the
// systems current app frame number to match this making the search
// unnecessary in the future. A match will be found if this app was
// previously installed, and this is the first run after the reinstall.
// – during the search, take note of the first empty frame block large
// enough to fit the apps data.
// – also take note of the smallest app sequence number encountered with
// a block big enough for this app to use. This information will be used
// if a large enough empty block is not found.
// – If a sequence number is encountered that is larger then the current
// system sequence number flip the logic and record the location of the
// largest app sequence number. This handles the wrap condition (255+
// installs).
// 4) If the app’s ID is not found:
// – If an empty block was found, null out the memory, set up the block
// to be used by this app and set the global variables containing this
// offset and length of the frame block. – If the EEProms memory is
// randomized by the factory, this case may never happen.
// – If the no empty block was found, use the location of the least
// recently used block of the needed size and set it up as described above.
// – If no matching used block is found, appropriate first n blocks to
// match the needs of this app and set them up as described above.
//------------------------------------------------------------------------

EEProm Memory Map
//EEProm Manager
//Memory size = 1024
//Block size = 16
//Number of blocks = 1024 / 16 = 64
//Frame Usage:
//#0 = Reserved for Arduboy and block manager
//#2-4 = Non-reserved - General use - Save data (48 bytes)
//#5-63 = Reserved on a first come first serve basis. When full, blocks are reassigned by least recently used

//Frame #0
//Byte:       0        1          2-13           14               15
//      <Brightness><AudioFlag><undefined><CurrentAppFrame><frameSeqenceNum>

//Frames #1-3  -- Can be used by any app, any time, for any purpose
//Byte: 0-15  --  0-15 --  0-15
//     <non-reserved - undefined>

//Frames #4-63 -- first frame in an app block
//Byte:   0-5       6         7-15
//      <AppID><frameCount><app data>

//Frames #5-63 -- second+ frame in an app block
//Byte:     0-15
//      <<app data>

Maybe not stop them, but there’s something that can dissuade them; endorsement and peer pressure. An “official” games list or registry, such as what we have now or something similar, could refuse to list games that don’t “play nice” with their use of EEPROM. If not outright unlisted, they could at least be put in a “has caviets” category. Another deterrent would be complaints like “After using this game, my high scores for <another_game> were wiped out :frowning2:”.

However, correct me if I’m wrong, but I believe you’re saying that if a sketch needs more code space, you feel it would be OK for it to abandon your library and use whatever methods it wants to. This attitude makes things worse for your proposal. Since the block(s) allocated to a given sketch can vary based on the number of sketches that have previously used EEPROM and the order in which they’ve been loaded, there’s no way to know which sketch’s blocks will be blown away by a sketch that doesn’t use the library, or vice versa.

One solution to this would be to divide EEPROM into two sections, one for the API and another for “do as you please”. I don’t know how you would decide on the proportions, though.

Don’t get me wrong, I like much of what you propose, I’m just worried that the amount of code that it will eat up may dissuade many sketches from using it, resulting it the “chaos” scenarios discussed. So, let me refine and elaborate on your proposal with some ideas:

The implementation

  • Still use an API similar to what I proposed:

  • A standard localEEPROM.h file to be included and customized for each sketch. As before, its purpose would be to provide information needed to allocate and identify a sketch’s EEPROM space.

  • API Functions find() allocate() free() read() and write(). There would be byte and block versions of read() and write(). Equivalents to EEPROM.get() and EEPROM.put() could also be added.

  • Direct access to EEPROM would be allowed with the caution that it may break if the underlying storage system changed in the future (E.g. it were changed to a system where a sketch’s space could be fragmented.) So, access via the API functions would be recommended but direct access might reduce code size with the risk of future breakage.

  • Your block based system would be used in a library to implement the API.

  • Although using a string based sketch ID is nice, it takes a fair amount of EEPROM space and would probably require a fair bit of code to set and search. I’d lean towards striving for a “low foot print” version, with a 2 byte user ID and a 1 byte sketch ID. There would be the issue of how to assign the user IDs but I think a wiki, or a topic in the forum where you ask for an ID and it would be assigned and added by a moderator to the head article, would work, at least initially.

  • If a one byte sequence number wraps from 255 to 0, how do you know whether a low number is very old or very new? I’d consider using a 2 byte sequence number. With the capability of a count up to 65535, the processor’s rated lifetime of 10000 flash writes would likely cause it to fail before the sequence number wrapped.

  • So the header would consist of 2 bytes user ID, 1 byte sketch ID, 1 byte frame count and 2 byte sequence number, for 6 bytes total.

How to get the “need more code space” people on board

The API functions to read and write EEPROM would be quite small, and direct access could be used to even further reduce code. The allocation and locating of a sketch’s EEPROM space is what requires the majority of code. Two things could be done to address this, with trade offs on ease of use:

  1. Eliminate the need for a sketch to allocate. A separate sketch could be written which would accept the input of a user ID, a sketch ID and a length. This sketch would then check if that particular space already exists and, if not, allocate it. The real sketch would then not need to use the allocate() function. It would only need to use find(). If the find() failed the sketch could somehow indicate to the user that the allocation sketch needed to be run, or optionally allow the sketch to run but not save anything to EEPROM.

  2. Additionally, eliminate the need to do find(). As an extreme measure, the sketch could just have a hard coded (using #define) block address. This address would be provided by the above allocation sketch and would need to be manually set in the real sketch before compiling. A simple verify() function could be added to the API. The sketch wouldn’t use allocate() or find() but would be required to call verify(), with the hard coded block number, in order to be API compliant. If verify() returned indicating that the block didn’t match the sketch’s user ID or sketch ID, then it would indicate this to the user, and as above, optionally allow the sketch to run but not save anything to EEPROM. Sketches that only verified would not work well as pre-compiled hex files.

Freeing up of blocks is another function that could use a fair amount of code. Freeing blocks isn’t really necessary if a “take over oldest or least used blocks” feature is implemented, but some people may wish to free up blocks that aren’t the oldest/least used. For instance, someone might try a game and decide that they will likely never use it again, so want its space freed up instead of loosing data for other games. The ability to free up blocks could be added to the allocate sketch, so sketches wouldn’t need to use it. Instead of an allocate sketch, it would be more of a general EEPROM space management sketch.

I don’t think the saving the current app frame is required. You may as well just always do a full search. The code to do it will be pulled in anyway. The code that makes use of the current app frame value would just take extra space.

You didn’t include a sequence number in each frame. I assume there should be one.

I wouldn’t treat the system EEPROM area as the first block. It should be considered to be separate from user EEPROM frames. You could decide to change your frame size from 16 to 32 but the system area would remain being 16, so it wouldn’t really be a frame anymore.

And now we’re Apple. And developers hate this about Apple. The only reason Apple gets away with it is because of the mountain of money that can be made. Plus, do you have any idea of the resources that apple expends approving apps? Money and resources are not options here. If we make it easy, if we make it clear; people will play along. No threat necessary.

Exactly. If we make the memory map simple and easy to understand a developer in this postilion will still follow guide lines, even if they are writing the code themselves.

Again, exactly. The automation is there for those who want to use it. Everyone else can write their own custom code that follows the standard or go wild west and accept the consequences of grumpy users using an app that doesn’t play well with others.

I think we posted simultaneously and missed that my algorithm accounts for this by setting aside three frames for non structured use. The value three was chosen arbitrarily and is open to discussion.

It will take up very little code. About 1kb is my pre-development guess. A large percentage for a system with only 32kb to work with, but reasonable for those who want the ease of use. Again for those who are starving for memory, it will be on them to play nice.

Ummm… No. No one is going to use a system that requires a custom header file. This is clearly a job for passing parameters into the initialization routine. This needs to be self contained and if possible importable as an Arduino library.

Sure. I was thinking Initialize,ReadByte, WriteByte only. With parameters accepting the data byte, the frame offset and the offset inside the frame. You can add lots of convenience routines for block size, and specifically accessing the general purpose frames at the beginning, but that will just add to the size of the library. My thought is, outside of Initialize, keep it lean.

No attempts at policing the system should be made. This API should be well explained as a convenience and left at that. If someone writes an app that disrupts others that are playing along, that is on that lone developer. Not everyone else. And not on this library.

Yes.

No. Two bytes is not enough. People tend to choose the same pass codes over and over again, and since this is automated with no governing body we need to give developers a little room to work with. I chose six characters for no real good reason. Three for the company ID and three for the app ID seemed like a good compromise. Thinking about it in a little more detail, the frame count and sequence number should swap places with the app ID. This would allow for the app ID’s to be null terminated. This would let the developer make the ID’s as long or as short as they need to address convenience or size considerations.

No, 255 is plenty. If you install and uninstall unique sketches once an hour 24 hours a day, it would take more than ten days to reach the limit. The logic supporting the wrap won’t take up much room, it saves storage space, and can’t be hurt by the future.

Two fixed bytes, the sequence number, and the frame count. One variable size for the app ID. As little as three bytes. As many as 15.

You don’t. Just as I am working up a custom version of Aruboy.cpp and Core.cpp, removing the stuff I don’t need for my app, other developers can copy and paste the parts of the library that they need and discard the rest. We get them to follow the standard in the process by making the library easy to use. The easier to use, the more apps that take advantage of it, the less likely someone will be willing to go their own way.

These are both clever ideas. But no one would make use of them. You automate the initialization routine. You make the code clear and easy to understand. Most people will then use it. Those few who are left will be doing their own thing, but they will have the initialization routine as an example of best practices. There is no need to specify the details of these edge cases.

This is why I decided chaining frames together was too complex. As for those very few people who may wish to take over more recent blocks, they are free to write the code to do so. There is no reason to take up valuable memory handling this or any other special condition.

This is a single byte that saves a great deal of run time and complexity for 99.9% of run conditions. It’s worth that extra byte. And the extra few bytes the if statement to support it will require.

Nope. The frames are continuous, the frame count byte defines how large the block is. There is no need to waste the byte in every frame.

A minor consideration. You define a zero block for the sake of consistency. If the block size grows you can just state the unused parts as undefined and add it to the general purpose block at the beginning. With a byte for the current app frame, you can directly address 4kb of EEProm memory… which I believe is more that any Arduio has ever had on board.

One of the really, really great parts of the Arduboy is that there simply isn’t the resources to accommodate every edge condition. The correct answer is this is to not address any of the edge conditions.

Keep it simple. Make it easy. And leave the Wild West to the gun slingers.

Actually, less than 20k to work with. The bootloader takes up 4k. An absolute minimum (and useless) sketch, consisting of an empty setup() and loop() uses another 4k. A bare minimum Arduboy sketch, consisting of just arduboy.begin() uses around 10k (my experimental derivative of the current development library can get that down to below 7k).

Anyway, I’ve given my input. All I can say is go for it. If you provide lots of documentation and examples it just might catch on. It looks like other than you and me there are just tumbleweeds blowing around in this topic.

The main reason for that is more than likely a fair few of us don’t quite understand the entire conversation.
I get the principle of it, and what you’re both trying to achieve, but the technical side of things is a little over my head.

I only skimmed some of the conversation above, but I’d rather see the eeprom broken into small sections of whatever arbitrary size and make the developers work within that constraint. In the end, it doesn’t matter what you do, you’re not going to keep everyone happy, and not everyone is going to play by the rules.

Back to lurking… :slight_smile:

1 Like

It’d be far easier to say screw it and divide the memory into 8 large blocks and treat it like those early Playstation save cartridges… where everything just knows if a slot is used or not and you get 8 slots… and a game needing more space could allocate more slots. Couldn’t save much room for tiny games with tiny requirements, but oh well.

OR maybe 8 large blocks and x smaller blocks. At this point I have no confidence this will ever get sorted. :slight_smile:

1 Like

I 100% agree with this!

The simplicity of this solution solves another problem I’ve been seeing - if you never reload an app that owns a block, how do you free up the block?

Keeping myself to about three lines of specification.

  • 64 blocks of 16 bytes each, because 16 is big enough for lots of things
  • make last 8 bytes of “reserved EEPROM 16 bytes” a bit array 0 = free, 1 = in use
  • only API calls are .eeprom_state(x) .eeprom_use(x) .eeprom_free(x)

This lets you play nice and find a block for yourself. You need to recognize your own blocks.

But if you want to own all the stuff, you can just override everyone (please say you are are doing this). Or if you just want to be standard, mark everything as busy and take over.

for (i=1;i<64;i++) arduboy.eeprom_use(i);

block(0) is always owned because it is reserved.

Just as an example … you can get 3 letters in two bytes. If you fit a score in 3 bytes (about 16,000,000) then you can get 3 high scores with initials in one 16 byte block, using that one extra byte as a magic value to hint the block is yours.

If we make the blocks big enough, we could have some kind of identifier at the beginning of each block. A game could search for that identifier to see if it has a save or not on the system. This would also allow a game to use multiple blocks without them being together.

If a dev wanted to store up to 4 blocks of data, they would traditionally need to allocate a chunk of space that size, but if they don’t need to use all 4 (maybe the game uses more the more the player progresses), the other unused blocks will be free for other games/apps.

Obviously, the smaller the blocks, the bigger the percentage of space the identifiers would use, so it would no longer be worthwhile.

Or - search through in-use 16 byte blocks for one that has your unique signature in it, where only you know how to evaluate the signature. The latter half of that block is a list - in order - of the blocks you are using. All of those other in-use blocks do not need to carry yoru signature - or at most need a way to detect modifications.

I really think that many of us have been infected by a big picture approach on this question. But I think we forget that changing applications on an Arduboy is more difficult than on most systems we have worked on elsewhere. Every commercial game system that offers new games uses some form of media, and most computers let us load and discard software with the touch of a key.

With that in mind, any advanced functionality involving things like multiple blocks is going to get almost zero workout. Anything that would work in the confined spaces of the ATmega32u4 will likely be too limited if there is a more advanced version available later with much more space or swappable storage.

The more I think on it, the more I see very little point in any standard for block identity. Arduboy apps will not have any reason to recognize anything other than their own blocks, so a single bit to mark a block as in-use is enough.

EEPROM is literally one of the only features of the Arduboy. I don’t think it’s too much to ask for it to have at least some form of standardization. If we don’t do this now, I can see beginner developers and devs who don’t use the forums often enough writing a great program that saves over a lot of other data for other games without warning.

Standards for block usage? Yes. Standards for identity? Not so much.

A program only cares about one thing for EEPROM - can I write here? Yes or no. If the block is used, then no, otherwise yes. Programs will be cramped for space as it is, so I really cannot see developers wanting to spend anything more than the most minimal of resources on dealing with someone elses data.

As it is, I have been actively developing for about a week - and I have already run into resource limitations imposed by the API. I know there are more coming. At least one item I am working on will likely warn you and then clobber all of EEPROM - if you don’t give it the EEPROM, it just won’t run. I expect I will start creating my own variation of the standard library for my use within a couple of weeks. I hate the idea of doing that, but the ultimate standardization is the hardware - as long as things run on the hardware, that’s going to be what counts.

If you want developers to adhere to standards, then you have to ensure that the standards are flexible enough to not impose an undue penalty on getting as much out of the platform as possible.

Incidentally, I note that the default loaded game by TEAM a.r.g. does not use the default library. It is quite possible that they decided that things like the boot up logo took too many resources that could be better deployed in the game, rather than used once for one second.

It’s more the case that the library wasn’t standard at the time Team A.R.G. started developing for Arduboy. Back then, even what few other examples existed just included a copy for the the library within the sketch itself. By the time Arduboy was actually a stand alone library, Team A.R.G. had customised theirs enough that they just continued to stick with it.

Using Arduboy2 may help.
http://community.arduboy.com/t/arduboy2-an-alternative-to-the-arduboy-library/1887/1

I am merely suggesting something like a leading byte identifier that is somewhat unique to each game that needs to save data.