Shared EEPROM storage management across multiple apps


(Scott) #41

How is it good programming? What “good” does it do? How does hiding the parameters affect the use of the API or the readability of the code?

It’s not a matter of assuming people are stupid. It’s a way of simplifying the ability to have more than one library provide the same functionality, as transparently and easily as possible for the sketch developer and/or maintainer.

Then I wouldn’t have the choice of what I wanted to name the object, unless a macro or function is used, like:

CREATE_EEPROM_OBJECT(savedData)

Which IMHO is even more obscure. And without hiding it two different ways, I wouldn’t have the choice between doing the equivalent of one of:

ArduboyEeprom savedData(...);
// or
ArduboyEeprom *savedDatap = new ArduboyEeprom(...);

Other disadvantages of not hiding the parameters:

  • Instead of the universal API documentation saying:

To invoke the constructor use:
ArduboyEeprom <objectName>(EEPROM_PARMS);

It would have to say:

To invoke the constructor use:
AduboyEeprom <objectName>(<parm1>, <parm2>, ...);
For the proper number and types of the parameters, see the individual documentation for the library you have chosen to use.

And each individual library would have to provide that documentation, or the main document would have to contain a list which would need to be kept up to date.

  • The developer would have to decide up front which EEPROM library was to be used, then locate and use it’s specific constructor documentation.

  • As I’ve already said, if at some point it was desired to switch libraries, the sketch’s .ino file, or one of its secondary .c or .cpp files containing the constructor, would have to be changed, instead of just swapping in and editing only the new library’s localEEPROM.h file. If the code is maintained in a Git repository or some other source control system, the file containing the parameter changes would have to be committed.

    Say an Arduboy Arcade exists containing many sketches that all use the decided upon “default” library. At some future time, the maintainers of the arcade decide to switch to a different library as the “default”. They could ask the original authors to update their sketches, but likely for a good many sketches the authors may not be available to do so, thus leaving it up to someone else. That person will have to hunt down the locations of the constructor in each sketch. This would be more time consuming than just swapping in and editing localEEPROM.h from a common template.

    To make things more difficult, there might even be multiple places where an object was instantiated. There could be a function to save high scores and another to save a game. To save RAM usage, an object could be created within each function that used it, instead of making the object global, thus freeing up the RAM that the object uses, when the function isn’t running.


(Josh Goebel) #42

I’m not going to argue. If there is some common wrapper that helps me and provides value to others who wish to use a differently library I’ll try it. If it requires me to do weird things like make obvious function calls obscure then I just won’t use that part.

Everyone can do as they please.


(Scott) #43

@Dreamer3, I’m comfortable with just agreeing to disagree. I’d like to see a standard #define for the constructor arguments made available in the header and documented, for those who find it convenient. For you, and others, who don’t like the obfuscation that it creates, there’s nothing preventing the actual arguments list being passed.

If an alternate way of wrapping the constructor, to allow varying arguments per library, is proposed and accepted, I’d entertain that as well.

Anyway, this discussion appears to be academic. No one else is participating lately and I see no signs of interest in defining and recommending an EEPROM management scheme (official, de facto or otherwise). I fear we’ll just end up with “every man for himself” chaos.

I think for now I’m just going to leave this conversation as it stands. I’m still willing to discuss and help refine and document a system if/when interest resumes.


(mlp) #44

I’m going to jump right in and try to kick start the discussion again.

I love the basic idea that Dreamer3 put forth. Setting up app frames. As a developer it would be very nice, at setup during the first run, to simply ask for a free frame and let the API handle the messy work. Once I have the frame, I could either go through the API to save the information at that location, or write directly to the memory location nyself.

How I would tweak it:

  1. Think of the frame setup as a separate piece. Having this piece alone would provide 99% of what is needed for developers and apps to play nice with each other. And apps that are just interested in saving a few bytes, this is all they would need. Everything else could be handled by a few quick writes to directly to the provided frame address.
  2. Skip chaining blocks. Too complicated. With only 1k of memory the same thing can be accomplished with a single byte at the end of the app ID.
  3. I would add a byte with a sequence number that would be incremented with the initial frame request from each new app. Once the frames are all filled up, this byte could be used to reuse frames in a Last-in-first-out or Least-recently-used basis.
  4. And you could easily do a low foot print version of the same thing. Two bytes for the user/app ID. One byte for the frame count. One byte for the sequence count.

Thoughts?


(Scott) #45

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.


(mlp) #46

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.


(Scott) #47

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()


(mlp) #48

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.


(mlp) #49

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>

(Scott) #50

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.


(Scott) #51

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.


(mlp) #52

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.


(Scott) #53

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.


#54

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:


(Josh Goebel) #55

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:


(Holmes) #56

I 100% agree with this!


(Chris Smith) #57

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.


(Holmes) #58

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.


(Chris Smith) #59

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.


(Holmes) #60

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.