Categories
algorithm Arduino software

Virtual arrays using an SD card

It is common for operating systems to use a hard disk swap files to increase the amount of available system RAM by swapping blocks(or pages) of memory between real RAM and the hard drive. As many applications use RAM linearly, this imposes relatively modest decrease in performance for the bigger benefit of increased temporary RAM.

It seemed to me that, for particular applications, this concept could be applicable to providing management of arrays to increase what could be stored in a microcontroller’s very limited memory resources.

Virtual RAM

Virtual memory is a memory management technique that creates the illusion to users of a very large (main) memory by using a combination of hardware and software to map memory addresses used by a program into physical addresses in computer memory.

Memory storage appears as a contiguous address space. Software or hardware manages virtual address spaces and the movement of data between real and virtual memory. This creates a virtual address space that exceeds the capacity of real memory and thus allows an application to reference more memory than is physically present in the computer.

This primary benefit of virtual memory management is often implemented using the technique of paging. This is where the virtual memory is divided into pages, or blocks, of contiguous virtual memory addresses that could be located in or out of RAM.

When a reference is made to a page by the hardware or software, if the page table entry for the page indicates that it is not currently in real memory, the hardware raises a page fault exception. This invokes the paging supervisor component to load the memory into RAM for use by the application.

Implementing Virtual Arrays

It turns out that implementing virtual arrays as an Arduino class, swapping blocks to an SD card, is a relatively straightforward exercise. The advantage of using a class is that the swapping can happen transparently to the application and is managed ‘in real time’ as the boundaries of the current page are exceeded. This technique is especially suited to applications where the array data is processed or traversed sequentially, forwards or backwards, during processing.

In this section I’ll describe the main class methods in and how they work to provide the required functionality. Code for the complete class and test sketch are included at the end of this post.

Firstly, the implementation is defined as a template that allow declaration contiguous of virtual RAM arrays for all basic data types. If required, extension to arrays of more complex structures should be straightforward.

The object declaration (the variable ram in the example sketch) allows the user sketch to initialize the number of array elements to be retained in memory (page or block size). This allows the application to make the trade off between memory swapping and application performance by selecting an appropriate page size.

bool begin(const uint32_t numElements, bool bClear = false, const char* fname = nullptr)
  {
    char tmp[] = "VA.DAT";
    const char *szFile = (fname == nullptr ? tmp : fname);

    PRINT("\nVA begin: ", szFile);
    PRINT(" block size=", _blockSize);

    // clean up the previous begin() if there is stuff still open
    if (_fp.isOpen()) { PRINTS(" close");  _fp.close(); }
    if (_blockData != nullptr) { PRINTS(" free");  free(_blockData); _blockData = nullptr; }

    // now create new environment
    if (_blockData == nullptr)      // allocate the memory required
      _blockData = (T *)malloc(_blockSize * sizeof(uint8_t));

    if (_blockData != nullptr)      // we have memory buffer - open file and load first page
    {
      PRINTS(" malloc");
      if (_fp.open(szFile, O_RDWR | O_CREAT)) // file can be opened
      {
        PRINTS(" open");
        _numElements = numElements;

        if (bClear)    // initialize only if we should
        { 
          PRINTS(" init");  
          initialize(); 
        }

        if (_fp.fileSize() / sizeof(T) >= _numElements) // file is big enough for the array
          loadBlock(0);             // load the first block into memory
        else                        // file too small - abort this
        {
          PRINTS(" close");
          _fp.close();
        }
      }
    }

    return(_blockData != nullptr && _fp.isOpen());
  }

The begin() method manages initialization of the total number of array elements, whether they should be set to zero, and the file name for the paging file. The last 2 parameters are optional and the default is not to initialize a file called VA.DAT. Allowing an optional initialization allows a sketch to persist values between microprocessor resets, which could be a useful feature.

This method also cleans up any open files or allocated memory before allocating enough memory for the in-RAM elements, opening/creating the file and initializing the virtual RAM. Basically anything that needs to be done to set up is done here.

  void set(uint32_t addr, T value)
  {
    PRINT("\nVA set: idx=", addr);
    PRINT(" value=", value);
    if (addr < _blockBaseAddr || addr >= _blockBaseAddr + _blockSize)
    {
      // save the page if it has changed
      saveBlock(_blockBaseAddr);

      // load the new page
      _blockBaseAddr = (addr / _blockSize) * _blockSize;
      if (_blockBaseAddr + _blockSize >= _numElements)
        _blockBaseAddr = _numElements - _blockSize;
      PRINT(", block load ", _blockBaseAddr);
      loadBlock(_blockBaseAddr);
    }

    PRINT(", offset ", addr - _blockBaseAddr);
    _blockData[addr - _blockBaseAddr] = value;
    _blockChanged = true;
  }

The set() method sets a particular array element to the value specified. The first thing this does is check if the address specified is mapped into the currently loaded block. If not, the page is swapped out by first writing the current block to the file and then replacing this with the block that does contains the specified address. One small wrinkle is that the total number of elements may not be an even multiple of the block size, so an adjustment for the ‘last’ page needs to be considered.

The specified array element is then changed and a global flag set to indicate that the this block has been changed. This flag is used to prevent rewriting unchanged blocks back to the SD card (a slow operation).

  T get(uint32_t addr)
  {
    PRINT("\nVA get: idx=", addr);
    if (addr < _blockBaseAddr || addr >= _blockBaseAddr + _blockSize)
    {
      // save the page if it has changed
      saveBlock(_blockBaseAddr);

      // load the new page
      _blockBaseAddr = (addr / _blockSize) * _blockSize; 
      if (_blockBaseAddr + _blockSize >= _numElements)
        _blockBaseAddr = _numElements - _blockSize;
      PRINT(", block load ", _blockBaseAddr);
      loadBlock(_blockBaseAddr);
    }

    PRINT(", offset ", addr - _blockBaseAddr);
    PRINT(", value=", _blockData[addr - _blockBaseAddr])
    return(_blockData[addr - _blockBaseAddr]);
  }

The get() method returns the value for the specified array element. This has similar page swap logic to set(), but then simply copies the required array element as the return value.

And that’s it! While the performance of a small Arduino processor with an SD card will not set the world on fire, the application of virtual arrays, and hiding the file management, can make it simplifies the implementation of extended data collection or processing.


// Virtual Arrays using an SD card and memory buffers.
// 
// Dependencies
// SDFat at https://github.com/greiman?tab=repositories
//

#include <SdFat.h>

#define DEBUG 0

#if DEBUG
#define PRINTS(s)     do { Serial.print(F(s)); } while (false);
#define PRINT(s, v)   do { Serial.print(F(s)); Serial.print(v); } while (false);
#define PRINTX(s, v)  do { Serial.print(F(s)); Serial.print (F("0x")); Serial.print(v, HEX); } while (false);
#else
#define PRINTS(s)
#define PRINT(s, v)
#define PRINTX(s, v)
#endif

// Constants and Macros
#define ARRAY_SIZE(a) (sizeof(a)/sizeof((a)[0]))

const uint8_t SD_SELECT = 10;             // SD chip select pin for SPI comms

const int32_t NUM_ELEMENTS = 30000;       // size of the memory in array elements

template <class T> class cVirtualArray
{
public:
  cVirtualArray(uint16_t blockSize): _blockData(nullptr), _blockSize(blockSize) {}
  ~cVirtualArray() { _fp.close(); free(_blockData); }

  inline bool isLoaded(void) { return(_fp.isOpen()); }
  inline bool isInBounds(uint32_t addr) { return (addr <= _numElements); }

  
  T get(uint32_t addr)
  {
    PRINT("\nVA get: idx=", addr);
    if (addr < _blockBaseAddr || addr >= _blockBaseAddr + _blockSize)
    {
      // save the page if it has changed
      saveBlock(_blockBaseAddr);

      // load the new page
      _blockBaseAddr = (addr / _blockSize) * _blockSize; 
      if (_blockBaseAddr + _blockSize >= _numElements)
        _blockBaseAddr = _numElements - _blockSize;
      PRINT(", block load ", _blockBaseAddr);
      loadBlock(_blockBaseAddr);
    }

    PRINT(", offset ", addr - _blockBaseAddr);
    PRINT(", value=", _blockData[addr - _blockBaseAddr])
    return(_blockData[addr - _blockBaseAddr]);
  }

  void set(uint32_t addr, T value)
  {
    PRINT("\nVA set: idx=", addr);
    PRINT(" value=", value);
    if (addr < _blockBaseAddr || addr >= _blockBaseAddr + _blockSize)
    {
      // save the page if it has changed
      saveBlock(_blockBaseAddr);

      // load the new page
      _blockBaseAddr = (addr / _blockSize) * _blockSize;
      if (_blockBaseAddr + _blockSize >= _numElements)
        _blockBaseAddr = _numElements - _blockSize;
      PRINT(", block load ", _blockBaseAddr);
      loadBlock(_blockBaseAddr);
    }

    PRINT(", offset ", addr - _blockBaseAddr);
    _blockData[addr - _blockBaseAddr] = value;
    _blockChanged = true;
  }

private:
  SdFile _fp;              // array file object
  uint32_t _numElements;   // the number of elements in this array
  T *_blockData;           // pointer to data block with _blockSize elements
  uint16_t _blockSize;     // in number of type T elements (NOT bytes)
  uint32_t _blockBaseAddr; // base array index for the block
  bool _blockChanged;      // true if the block has changed

  void initialize(void)
  // create and initialise the memory file
  {
    PRINT("\nVA init size ", _numElements * sizeof(T));
    _fp.rewind();   // move to the start of the file
    for (uint32_t i = 0; i < _numElements * sizeof(T); i++)
      _fp.write((uint8_t)0);
  }

  void loadBlock(uint32_t addr)
  {
    PRINT("\nVA load: id=:", addr);
    _fp.seekSet(addr * sizeof(T));
    _fp.read(_blockData, _blockSize * sizeof(T));
    _blockBaseAddr = addr;
    _blockChanged = false;
  }

  void saveBlock(uint32_t addr)
  {
    if (_blockChanged)
    {
      PRINT("\nVA save: id=:", addr);
      _fp.seekSet(addr * sizeof(T));
      _fp.write(_blockData, _blockSize * sizeof(T));
    }
  }
};

// Global Data
SdFat SD;
cVirtualArray<uint16_t> ram(100);

void setup(void)
{
  Serial.begin(57600);
  Serial.print("\n[VirtualArray]\n");
  
  // Initialize SD
  if (!SD.begin(SD_SELECT, SPI_FULL_SPEED))
  {
    Serial.print(F("\nSD init fail!"));
    Serial.flush();
    while (true);
  }

  ram.begin(NUM_ELEMENTS, true);

  for (uint8_t i = 0; i < 150; i++)
    ram.set(i, i);

  for (uint8_t i = 0; i < 150; i++)
    Serial.println(ram.get(i));
}

void loop(void)
{
}


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s