Addition of a utility class for cycling writes

[Titantompa]

Hey,

I wrote a utility class for your library and though I'd ask you if you'd like to include it in your main library (rather than me registering yet another minimal library that can only be used with your's).

My use case is that I have various devices that need the ability to retain their state between power cycles. While they may not lose power that frequently the changes to their state are much more frequent. I also expect them to operate indefinitely without any periodic mentainance. So I figured I can extend the expected use of an eeprom by simply spreading the writes evenly over the available pages - hoping that it will simply suffice.

So, to do this I implemented this template class that writes the data to the next higher position in memory each time and starts over at address zero when the end of the eeprom has been reached. In order to know what was the last writted position it adds a header to the data containing an incremental version number. At initialization it locates the highest version number (by a partitioning search) and simply continues where it left off.

So, please have a look at it and add it to your lib if you think it is suitable! (I've tried to keep the code similar to how you have written yours, so that it wouldn't look haphazard.) Please squash the commit so that all my interim ones are left out!

Oh, and I also updated the code that figures out the page size, since it didn't handle larger eeproms.

Cheers

[RobTillaart]

Question: If as system restarts, how does it know the last slot used to read the last good value from EEPROM? Reuse same location is straightforward, however your class explicitly use multiple locations to reduce 'overused locations'

[RobTillaart]

Please also check the CI build .... als it need to be green before merge

• https://github.com/Arduino-CI/arduino_ci/blob/master/REFERENCE.md

[RobTillaart]

Q: should the class have some statistics? (No is a valid answer...)

[Titantompa]

Question: If as system restarts, how does it know the last slot used to read the last good value from EEPROM? Reuse same location is straightforward, however your class explicitly use multiple locations to reduce 'overused locations'

Question: If as system restarts, how does it know the last slot used to read the last good value from EEPROM? Reuse same location is straightforward, however your class explicitly use multiple locations to reduce 'overused locations'

Since it does the writes in sequential order from the start of the general idea is that you, starting from the first slot, simply fast forward as long as the version number is higher than the previous one. This is not very optimal, if you have hundreds or thousands of pages, so I wrote a simple partitioning search.

It checks the centre-point of the search set - if the version number is higher than the start it means that the last must be after the centrepoint so it reduces the search set to the upper half and "recurses" into that. Similarly, if the centre-point has lower than that of the first slot the highest version number must be in the lower half of the search set... I'm not sure how to express the number of comarisons mathematically, but it does the same number of comparisons regardless of where the highest version is. E g if you have 512 pages it will find the highest version number in nine iterations.

This is implemented in the initialize() method.

[Titantompa]

Q: should the class have some statistics? (No is a valid answer...)

I had a few thoughts but at the same time felt like they were more of a debugging or anecdotal nature?

Adding a few more fields to the header would allow for a lot more interesting metrics but I'm hesitant to using eeprom memory as it could significantly reduce the expected number of writes to the chip (if they'd cause the slot to require one more write page).

Maybe if it could provide a metric that indicates how many of the expected writes have been consumed? E g: u = x / ( v / (p / b) ) u = used % of expected writes x = expected available writes p = total number of pages b = buffer page size

Maybe there is a reasonable default value to use for the expected number of writes? So that it could be written as a simple method that returns a float between 0.0 and 1.0?

[RobTillaart]

Question: If as system restarts, how does it know the last slot used to read the last good value from EEPROM? Reuse same location is straightforward, however your class explicitly use multiple locations to reduce 'overused locations'

Since it does the writes in sequential order from the start of the general idea is that you, starting from the first slot, simply fast forward as long as the version number is higher than the previous one. This is not very optimal, if you have hundreds or thousands of pages, so I wrote a simple partitioning search.

It checks the centre-point of the search set - if the version number is higher than the start it means that the last must be after the centrepoint so it reduces the search set to the upper half and "recurses" into that. Similarly, if the centre-point has lower than that of the first slot the highest version number must be in the lower half of the search set... I'm not sure how to express the number of comarisons mathematically, but it does the same number of comparisons regardless of where the highest version is. E g if you have 512 pages it will find the highest version number in nine iterations.

This is implemented in the initialize() method.

This strategy is called binary search and the number of steps needed are O( 2log(size) ). That means that if there are 64 elements you need O(2log(64)) steps = 6 iterations, 100 elements need 6.64... = 7 iterations, 1024 elements need ~10 iterations, a million = 20 steps etc

[RobTillaart]

A review of initialize shows some (minor) improvements.

bool initialize()
{
  uint16_t startSlot, probeSlot, endSlot;
  uint32_t current;

  _eeprom->readBlock(0,  (uint8_t *) &current, sizeof(uint32_t));

  // Memory is blank == first time use
  if (current == ~0UL)
  {
    _isEmpty = true;
    _currentSlot = 0;
    _currentVersion = 0;
    _isInitialized = true;
    return true;
  }

  // Find the current block by binary search
  startSlot = 0;
  endSlot   = (_totalPages/_bufferPages) - 1;         // Index of last slot
  probeSlot = startSlot + ((endSlot - startSlot)/2);  // Midway between start and end

  while (startSlot < probeSlot)
  {
    _eeprom->readBlock(probeSlot * _pageSize * _bufferPages, (uint8_t *) &current, sizeof(uint32_t));
    if ( current == ~0UL)
    {
      endSlot   = probeSlot;
    }
    else
    {
      startSlot = probeSlot;
    }
    probeSlot = startSlot + ((endSlot - startSlot)/2);
  }
  _currentSlot = startSlot;
  _currentVersion = current;
  _isEmpty = false;
  _isInitialized = true;
  return true;
};

Some minor thoughts

• _pageSize * _bufferPages, could be out of the loop as it is a constant.
• initialize always returns true, which is pointless at the moment but can be a preparation for error indication. Better to return an uint8_t as that can have 256 distinct values from which e.g. 0 == OK

[Titantompa]

A review of initialize shows some (minor) improvements.

bool initialize()
{
  uint16_t startSlot, probeSlot, endSlot;
  uint32_t current;

  _eeprom->readBlock(0,  (uint8_t *) &current, sizeof(uint32_t));

  // Memory is blank == first time use
  if (current == ~0UL)
  {
    _isEmpty = true;
    _currentSlot = 0;
    _currentVersion = 0;
    _isInitialized = true;
    return true;
  }

  // Find the current block by binary search
  startSlot = 0;
  endSlot   = (_totalPages/_bufferPages) - 1;         // Index of last slot
  probeSlot = startSlot + ((endSlot - startSlot)/2);  // Midway between start and end

  while (startSlot < probeSlot)
  {
    _eeprom->readBlock(probeSlot * _pageSize * _bufferPages, (uint8_t *) &current, sizeof(uint32_t));
    if ( current == ~0UL)
    {
      endSlot   = probeSlot;
    }
    else
    {
      startSlot = probeSlot;
    }
    probeSlot = startSlot + ((endSlot - startSlot)/2);
  }
  _currentSlot = startSlot;
  _currentVersion = current;
  _isEmpty = false;
  _isInitialized = true;
  return true;
};

Some minor thoughts

• _pageSize * _bufferPages, could be out of the loop as it is a constant.
• initialize always returns true, which is pointless at the moment but can be a preparation for error indication. Better to return an uint8_t as that can have 256 distinct values from which e.g. 0 == OK

I've moved the calculation of the buffer length to outside the loop. 👍

I also made it propagate read errors from the I2C_eeprom class itself so it now actually can return either true or false. As there is no further information from the underlying calls I thought it better to simply return a boolean. If the call to begin() is improved in the future, featuring an int return value carrying more detailed failure information it would be better to remove or make the current interface obsolete - with a reference to the new improved one so that users can adapt their code appropriately.

This resonates a little with the read() and write() calls where the first has no error information and the latter would need to encapsule or translate the Wire error codes to make room for the possibility that the instance hasn't been initialized properly. Facing the complexity of it, I've opted to keep it light weight and a little crude.

Surprisingly this code also featured a re-surfaced bug, with finding the current of an even number of slots, that I fixed. Again.

[Titantompa]

Q: should the class have some statistics? (No is a valid answer...)

I had a few thoughts but at the same time felt like they were more of a debugging or anecdotal nature?

Adding a few more fields to the header would allow for a lot more interesting metrics but I'm hesitant to using eeprom memory as it could significantly reduce the expected number of writes to the chip (if they'd cause the slot to require one more write page).

Maybe if it could provide a metric that indicates how many of the expected writes have been consumed? E g: u = x / ( v / (p / b) ) u = used % of expected writes x = expected available writes p = total number of pages b = buffer page size

Maybe there is a reasonable default value to use for the expected number of writes? So that it could be written as a simple method that returns a float between 0.0 and 1.0?

I added a getMetrics() method that returns the number of slots and the number of writes - that way you can calculate the average number of page writes to guesstimate how far along you are.

[RobTillaart]

Did you do a performance test with the proposed format (setBlock variant) ? As most applications will use it seldom it does not matter that much.

I will review coming week (If I find a slot maybe today)

[Titantompa]

Did you do a performance test with the proposed format (setBlock variant) ? As most applications will use it seldom it does not matter that much.

I will review coming week (If I find a slot maybe today)

Yes, the setBlock() variant takes approximately five times longer.

[RobTillaart]

Idea, although quite some work

• would it be better to create a derived class with this extra functionality?
• the user only has one object to consider
• interfaces may be simpler
• would make it easier to move functionality from derived -> base when appropriate..

[Titantompa]

Idea, although quite some work

• would it be better to create a derived class with this extra functionality?
• the user only has one object to consider
• interfaces may be simpler
• would make it easier to move functionality from derived -> base when appropriate..

A valid point, but I'd argue against a specialization as it skyrockets the complexity. There are undisputed advantages of the composition pattern...

It would maybe be better to enable this class to act as a facade by adding a variation of begin() that creates an instance of I2C_eeprom that is kept behind the scenes? It adds a lot of code (relatively) since this would have to include overloads for all parameter variations to the I2C_eeprom constructor and the begin() method. I'm also not sure it would make life easier for a user as the number of options would increase to the point where it might obfuscate things..?

One thing that could be considered for future versions is if it would be worthwhile to create abstract base classes for this and I2C_eeprom so that mock implementations could be used in unit tests?

[RobTillaart]

I will squash and merge the commits , keeping the unique commit comments. OK?

[Titantompa]

I will squash and merge the commits , keeping the unique commit comments. OK?

Absolutely! Thanks! 👍

[RobTillaart]

@Titantompa done