The Problem

In deeply-embedded systems, associations between conceptual entities often take the form of a small static lookup array. Given a pointer to a UART, as one typical example, the middleware layer wants to memoise the UART handles in use and keep an associated list of say handler functions for that minimal set of registered UART handles as an implicit one-to-many association.

One Solution

MIT sources at GitHub.

Take that very specific STM32 exemplar: registering UART handles. The solution requires a new FreeRTOS-style function with the signature:

size_t xRegisteredCardinalOfUART(UART_HandleTypeDef *pxUART);

It answers an unsigned “cardinal” number for any pointer to ST’s UART_HandleTypeDef. The function does not initially know what UART pointers exist. Its only requirement is to remember any that it sees and always give the same cardinal for each. It also prescribes a limited number of associations.

The listing below presents a ‘registered opaque’ implementation of the function.

#ifdef HAL_UART_MODULE_ENABLED

#include "registered_opaques.h"

static size_t prvHashOfOpaque(void *pvOpaque) {
  UART_HandleTypeDef *pUART = pvOpaque;
  return (uint32_t)pUART->Instance >> 10U;
}

size_t xRegisteredCardinalOfUART(UART_HandleTypeDef *pxUART) {
  static void *pvOpaques[stm32xx_uartMAX_INSTANCES];
  static struct RegisteredOpaques prvRegisteredOpaques = {
      .ppvOpaques = pvOpaques,
      .xNumberOfOpaques = stm32xx_uartMAX_INSTANCES,
      .pxHashOfOpaqueFunction = prvHashOfOpaque};
  return xRegisteredCardinalOfOpaque(&prvRegisteredOpaques, pxUART);
}

#endif

Things to note:

The static opaques depend on stm32xx_uartMAX_INSTANCES which defines the maximum number of UARTs supported by the embedded device, or typically 5U.
The hashing function utilises the Instance member which for STM32’s hardware abstraction layer corresponds to the memory-mapped base address of the peripheral bus. Shifting right by 10 effectively hashes out the bus address to spread the UARTs throughout the opaque vector so that searching usually needs only one successful comparison, i.e. O(1) performance or very close to it.

It relies on a structure and a function: struct RegisteredOpaques and xRegisteredCardinalOfOpaque. Implementations follow.

Registered Opaques

Introducing a hash of registered opaques: Imagine an abstraction that binds a small and fixed number of opaque pointers with a hashing function used to shortcut the opaque-to-cardinal search.

#include <stddef.h>

struct RegisteredOpaques {
  void **ppvOpaques;
  size_t xNumberOfOpaques;
  size_t (*pxHashOfOpaqueFunction)(void *pvOpaque);
};

typedef struct RegisteredOpaques *RegisteredOpaques_t;

Search such a thing by hashing. Create the association if it does not already exist:

size_t xRegisteredCardinalOfOpaque(RegisteredOpaques_t xRegisteredOpaques,
                                   void *pvOpaque) {
  size_t xCardinal = xRegisteredHashOfOpaque(xRegisteredOpaques, pvOpaque);
  void **ppvOpaque =
      ppvRegisteredOpaque(xRegisteredOpaques, pvOpaque, xCardinal);
  if (ppvOpaque == NULL) {
    ppvOpaque = ppvRegisteredOpaque(xRegisteredOpaques, NULL, xCardinal);
    configASSERT(ppvOpaque);
    *ppvOpaque = pvOpaque;
  }
  return ppvOpaque - xRegisteredOpaques->ppvOpaques;
}

Notice the FreeRTOS configASSERT. The assertion must always succeed. It can only fail if the number of opaques available runs out and that can never happen by design since

the opaques always have a limited number and
the hash size matches or exceeds that number.

The ppvRegisteredOpaque dependency is a static helper function that scans for a matching opaque pointer in a circular way starting at the hashed cardinal, as follows.

static void **ppvRegisteredOpaque(RegisteredOpaques_t xRegisteredOpaques,
                                  void *pvOpaque, size_t xCardinal) {
  for (size_t xOrdinal = xRegisteredOpaques->xNumberOfOpaques; xOrdinal;
       xOrdinal--) {
    void **ppvRegisteredOpaque = xRegisteredOpaques->ppvOpaques + xCardinal;
    if (*ppvRegisteredOpaque == pvOpaque)
      return ppvRegisteredOpaque;
    if (++xCardinal == xRegisteredOpaques->xNumberOfOpaques)
      xCardinal = 0U;
  }
  return NULL;
}

See the Gist (link above) for the implementation of xRegisteredHashOfOpaque. It defaults to answering zero if no hash function.

Conclusions

The listings utilise FreeRTOS naming conventions:

ppv for pointer to pointer to void and
x for size_t and other non-standard but portable layer-defined types.

In tests, the solution works well in performance terms as well as for a convenient abstraction mechanism. The developer can easily multiply the registry hashes with little wrapper functions for all kinds of embedded entities.