Open draggett opened 9 years ago
I've made a start at a C++ implementation along with JSON using AVL trees for associative arrays. I am using C++ string for now, but plan to migrate to Arduino String. I am not sure how to handle JSON stringify and reckon that it will need to be to a statically allocated buffer, e.g. for marshalling messages. JSON arrays are another challenge! Do we really need them for this server?
Benoit Blanchon is the developer of the C++ ArduinoJSON library. This uses a fixed memory allocation and claims to have a small footprint. You get to specify the size of the allocated buffer when using the library.
Whilst we could use that library, it may be more efficient to create our own code that combines JSON support with associative arrays for thing properties and actions. We will need to parse models to build objects for things, as well as to parse and serialise JSON messages. Here is potential C code for interacting with things.
I am not big fun of the fixed allocated buffer in ArduinoJSON either but the library seems to work and to work well. I also found another library called jsmn and is even smaller, also very simple and doesn't require and fixed amount of allocated memory.
Encoding and decoding JSON has been solved by many people numerous times so picking a library from the shelf can save precious development time. Any thoughts on this matter?
I have used jsmn on a project for ESP8266 and I am quite satisfied with it. It is small and simple to use.
jsmn looks good as a building block for a parser, and I have done something similar in the distant past. When creating associative arrays equivalent to JavaScript objects, we need to consider the lifetime of these objects compared to the strings used as their keys. Are the strings literals in the program code? Are the strings part of a message buffer that will be overwritten by the next incoming message? Can we discard the associative array after sending a response message?
The thing metadata will need to persist until the thing is unregistered. For a thing hosted by this server, we could assume string literals on the developer's sketch. For a proxy for a thing on another server, we would need to create copies of the strings. If we expect that the dynamic same string value will occur multiple time, then we could save memory with a hash table that will always maps a given string value to the same address.
For messaging, we need a way to marshall messages prior to sending them, and I am thinking of first trying CBOR as a reasonably efficient binary encoding that has been designed for constrained environments. Arduino CBOR library looks very promising. There are a suite of methods for writing data of different kinds, and likewise call backs for different kinds of data when parsing incoming messages. There is a lack of examples for how to use the library, however from the source files, it is clear that the encoder supports passing strings either as Arduino String, or as pointer and a length. The decoder provides a pointer to a null terminated string in the decoding buffer and casts it to an Arduino String before passing it to the call back. I don't yet understand what memory management if any that Arduino String makes use of, and plan to inspect its implementation to find out.
In the Web of Things, we have a variety of incoming message classes, including:
The code for handling this will know whether a given string value needs to be kept around, e.g. as the value of a thing's property, or can be discarded, e.g. as a name used to access a thing's properties. An open question is whether we should design the respective methods to uniformly pass strings in terms of their start and stop addresses, or whether null terminated strings would prove easier overall.
The Arduino Uno has 2 Kbytes RAM, 1 KByte EEProm and 32 KBytes Flash. This is a challenge! On further study I have arrived at the following approach. For the thing's that a server hosts, the models are declared as string literals in program memory (i.e. Flash). jsmn is used to tokenise models and create an internal object representation. This representation uses symbols in place of strings. A symbol table is needed during the processing of the models, but if necessary could be discarded afterwards. The table would reference substrings in the string literal in program memory. Because the symbols are derived in a deterministic manner from the models, we can use symbols in place of strings for messages between the proxy and the thing it proxies.
If the Uno is used as a proxy server, it will have to retrieve the models for the proxied things and process them as above. With small packet sizes, the complete string source of the model won't need to be held in RAM. However, field names will need to be held in RAM until the symbol table can be discarded. This will necessitate support for a string pool, which could be allocated on the program stack as a simple way to ensure its disposal after processing a thing model.
I have implemented a simple approach to marshalling and unmarshalling messages that makes use of thing dependent symbols for compact messages. Each item in the message starts with a byte code. Symbols and small integers can be expressed with a single byte. Other byte codes provide support for strings, numbers, arrays and objects as well as true, false and null. This is for experimental purposes, and I am looking for help with support for other encodings such as CBOR and EXI, especially for how to use them with shared symbol tables.
I am in the process of adding support for arrays, treating arrays akin to strings, with a sequence of pointers to successive array items and a null pointer as the terminator. The challenge is to deal with nested lists. I think I will need to have a way to keeping track of which arrays are still being parsed, so that their pointer sequences can be moved up to make space for a finished nested array. In essence, we need a reference to the parent array.
When a nested array is started, the parent array won't have pushed a null pointer, so we can search back for the preceding null pointer or buffer start (whichever is found first) to locate the end of the nearest finished array. We can then shuffle up the unfinished arrays to make space. This leaves unresolved how to find the unfinished array objects so that we can adjust the pointer each holds to the start of the array. In principle, this could be passed back as an adjustment that needs to be applied after parsing an array item. A static variable should suffice whose value is updated at the end of parse_array(), assuming that JSON parse is not re-entrant!
To allow for run-time modification to array lengths, we could arrange for the pointer sequence for arrays to start with a pointer to the array object and end with a null pointer. You can then find array objects by scanning back from the top of the array pool.
Given up on using pointer sequences for arrays - just too complicated to be worth it. Instead switched to using AVL trees. Objects properties can be indexed by names (which map to numeric symbols) or array indices. The tree nodes store symbols as negative integers to distinguish them from array indices which are always zero or positive. The first symbol is 1, (i.e. stored as -1) to avoid a clash with array index 0.
To reduce the RAM needed to represent JSON nodes, I have used getters and setters to store the node's tag and the length field for string valued nodes into a single 16 bit value. This works because there are 14 tags which fits nicely into 4 bits, leaving 12 bits for the length, thereby allowing strings of up to 4095 bytes long.
With some macros and a sed script I am now able to compile successfully on the Arduino IDE. This uses arduino.sh to copy and massage the files, and Arduino.h as a standing for the genuine Arduino header file when compiling away from the Arduino environment. Together with the UIP network library, I now see a sketch size of 12,044 bytes and global variables at 1,332 bytes. I've moved all of the string literals to program memory to save RAM. Most of these are in any case for debugging.
The PROGMEM macro can be used as follows:
const char agent12[] PROGMEM = "agent12";
and the F macro within print statements, e.g.
Serial.print(F("JSON Pool is using "));
Serial.print(JSON::json_pool_used());
Serial.println(F("% of available nodes"));
There is a suite of functions for operating on variables in program memory. You first need to include #include <avr/pgmspace.h> at the top of the file. This includes variants of basic string handling functions with a _P suffix, e.g. strcmp_P
strcmp_P(“RAM string”, PSTR(“flash string”));
The UIP library works with the ENC28J60 ethernet board and uses considerably less RAM than the regular Arduino Ethernet shield. The compiler is however complaining about there being two network libraries.
I would like to better understand how much memory my code is using and where.
On some further study, I think I can reduce both AvlNode and JSON node to 6 bytes, and to do so in a way that is easy to relax on more powerful devices like the Arduino Due and the ESP8266. On the Uno, we could thus have a joint total of 150 nodes for a cost of 900 bytes. I am working towards this, but sadly broke the AVL tree code in the process and run out of time today to fix it. This is looking promising, but I wonder how much RAM will be sucked up for encryption and protocols.
With both JSON and AVL nodes occupying 6 bytes on the Uno, it makes sense to allocate them both from a single memory pool. I will use a C union to play it safe. Further detective work is needed to pin down the unknown globals that are currently using about 512 bytes. I suspect that these may be allocated by libraries I am using, suggesting the possibility of writing my own code if that would help.
I need to rethink the interface for registering a new thing given that the mapping of property names to symbols is currently discarded after parsing the JSON source for the thing's model. One idea is to call a user supplied function after parsing and before discarding the hash table. This would be in addition to the start method, which is only called when the things dependencies have been resolved. This set up function would be able to look properties up by name. I need to experiment and see what works best.
I am now able to run make from the command line and see how much RAM is being allocated at link time. The avr tool avr-nm can be used with the -C -v options on the .elf file to view the symbols and see how much memory they use. This shows me that the USB serial library (Serial) consumes 157 bytes. I should therefore wrap print statements with #ifdef ... #endif to save RAM when the server is running normally. Uninitialised global or static variables will be assigned to the BSS memory section and automatically cleared when the program starts running. The compiler is smart enough to spot when a variable is initialised to zero, and assign it to the BSS section. Another potentially useful technique is to allocate memory on the stack frame with the alloca() call. This will be automatically freed when the calling function itself returns. This technique is appropriate when you can't simply use a local variable within a function.
Addendum: I've wrapped all print statements and print functions in #ifdef DEBUF #endif and have saved the 157 bytes previously allocated to Serial. This is looking very promising.
I need a plan for using EEPROM to support persistent configuration info. The Uno has 1Kbytes of EEPROM, and it should be possible to add more via I2C. EEPROM could be used to store the source of thing models and associated maps from names to symbols, freeing up RAM. EEPROM should be relevant to speedy recovery from deep sleep. It can also be used for data logging, taking into account the 100,000 update cycle limit noted in the specifications. In other words, updates should be limited in frequency, e.g. every 20 minutes would yield an expected lifetime of approximately 4 years. External EEPROM is typically rated for 1 million cycles, which would allow updates every 2 minutes for the same 4 year lifetime.
n.b. the Arduino ESP8266 support maps the EEPROM library to use a single sector of Flash memory. The library will take care to erase the sector before committing the new data.
Another challenge is sleeping to save battery life. Nick Gammon has some useful information for the ATmega328 as used on the Uno. He shows how to radically reduce power consumption for a bare bones board, i.e. the ATmega328, a Crystal, and a few capacitors and resistors. However, for an Internet of Things application, you still need a way to connect to the device.
If RAM is powered down, the software will need to re-initialise and this takes time and energy. This is particularly applicable when using the ESP8266 with the Arduino tool chain. This device has a deep sleep mode that upon waking triggers a full system restart. If the server has to do a lot of initialisation, this could take a long while. This makes it worth looking at ways to cache state in EEPROM or Flash memory as a means to accelerate the initialisation process. I need to come back to this once I have the server working without sleeping. I am hoping that it will not necessitate a massive refactoring of the code.
Now working on the design for the Thing and Proxy classes. These need to reference the URI, data model, property values, actions, event observers and the set of remote proxies for a given thing or proxy. The URI is a string and may be stored in program memory (i.e. Flash). The data model is the internal representation of the JSON-LD source, as obtained from JSON::parse().
The properties could be represented as a JSON object. Individual actions could be represented as a special version of a JSON node holding a function pointer. A JSON object would provide the mapping from symbols to actions.
The event observers is a set of functions to call for a given event. We could use a JSON object to map from the symbol denoting the event to a JSON array of functions, using the same node tag as for actions.
This leaves the challenge of representing remote dependencies, i.e. proxies on other servers for things or proxies on this server. The server assigns an id to each thing it hosts, 1 for the first, 2 for the second and so forth. The id for a thing is used to route an incoming message to that thing. This implies the need for the message for registering a proxy to pass the id to use in messages to the remote server, and for the response to the message for registering a proxy to pass the id for the thing on this server.
I plan further abuse of the JSON node mechanism to hold the id for the remote node along with a pointer to the protocol info needed to talk to it.
The Thing and Proxy classe each consume 10 bytes on the ATmega328 by storing the index for the JSON node rather than a pointer. The node pool uses an 8 bit index which provides for a maximum of 255 nodes (1530 bytes), but the ATmega328 only has 2 Kbytes RAM, so we will have to live with a limited number of nodes. This should be okay for simple "things". For devices with more memory, e.g. 96 Kbytes of RAM as on the Arduino Due and ESP8266, we could use an16 bit index to cater for more "things" with richer models.
I next need to work on the network code. I need an event driven software architecture where hardware interrupts push events onto the event queue, and the main loop dispatches the events one at a time. The Arduino Ethernet shield has solder jumpers that need to be connected to enable hardware interrupts on pin 2. The Wiznet W5100 has 16 Kbytes RAM for 4 sockets, and thus allows for packet sizes up to 2 Kbytes. The Arduino EthernetUDP library is cumbersome and blocks waiting for incoming packets, so I won't use that library. The Arduino Socket library provides a recvAvailable function which you can use to get the size of a packet before reading it. However the recv and recvfrom methods expect to copy the complete packet to the MCU's RAM. On the ATmega328P, there is only 2 Kbytes RAM, so that doesn't sound very attractive. I therefore plan to write my own UDP handler that replaces the Socket library, and re-uses much of its code.
The desire is to avoid blocking the microcontroller by waiting for incoming packets, and instead support an event driven architecture. This requires an event queue that can be pushed to from interrupt service routines and from regular application code. The main loop consists of an event dispatcher that pops an event from the queue and calls the registered event handler. If there no events pending, the loop puts the microcontroller to sleep until the next interrupt. This assumes a sleep mode that preserves RAM state. The event dispatcher could prioritise particular kinds of events as appropriate. The event queue could be implemented as a statically assigned buffer with rotating free space. High priority events could be pushed onto the front of the queue, and lower priority events onto the end of the queue.
To save battery life further, the server could be programmed to power down system components and enter a deeper sleep mode until it is scheduled by a timer to wake up. At this point the server would need to power up system components and re-initialise them. On some devices, where the RAM state is not preserved in deep sleep, the code needs to be reloaded from Flash memory. EEPROM could be used to preserve configuration settings, potentially, including thing state and models.
For thing data models, I should be able to parse models without needing to load the model in its entirety into the MCU's RAM. If the server want's to export a thing that is a proxy for a thing on another server, then I would need to retain the symbol to string mapping. I could do this in EEPROM. The ATmega328P has 1 Kbytes EEPROM, but it is straight forward to extend that with an external chip via I2C. On the ESP8266, you could use flash as a substitute for EEPROM, and the Arduino ESP8266 code implements the Arduino EEPROM library in exactly that way. Alternatively you could use an external EEPROM chip via I2C. A similar situation applies to the ARM STM32.
These boards support a wired Ethernet connection and are controlled by SPI. Both boards provide a hardware interrupt line, although you need to solder a jumper on the W5100 board. I plan to use the Arduino w5100 library and a corresponding library for the ENC28J60. This would sit below the UDP library mentioned above.
Further study shows a clear advantage for the W5100 which has native support for IP protocols such as ARP, ICMP, IGMP, UDP and TCP. The ENC28J60 by contrast only supports layer 4 (Ethernet) necessitating a sizeable library.
The Arduino ESP8266 project enables you to use the Arduino IDE to develop programs for execution on the ESP8266. This is a powerful chip with 96 Kbytes RAM and between 512 Kbytes and 4 Mbytes Flash as well as an integrated WiFi transceiver. The ESP8266WiFi library and WiFiUdp libraries provide the means to sign in with access points, and to determine how much data can be read from a given packet. However, I don't yet know how to set up an interrupt service handler for when incoming packets are available.
The ESP-01 provides a very cheap WiFi solution for use with other microcontrollers. You connect to it via a UART and control it via AT commands. There is a pin for powering the ESP8266 down to save power, and a reset pin for resetting it. An interrupt service handler can be used to detect when the ESP is about to send data to the MCU. You can use the Arduino Serial library to communicate with the ESP, or you can save memory by using a lower level UART driver.
I've been working on the networking library, starting with the Arduino Ethernet shield which uses the Wiznet W5100 chip. By going back to the Wiznet example driver, I have been able to create my own UDP library that drives the W5100 directly via the ATmega328P's SPI bus hardware. So far my code polls the W5100 for received packets, but the next step will be an interrupt based version. I also plan to add optional support for DHCP and for using multicast, e.g. to discover a hub or to allow the IoT device itself to be discovered over the local network.
The W5100 has 16 Kbytes RAM for network buffers, so there is a temptation to use some of this as a cache, e.g. for thing data models, as in many cases a server only needs to support a single socket. This also makes it practical to support large UDP packet sizes, e.g. 4 Kbytes if you assign 8 Kbytes to one socket and the remaining 8 Kbytes for use as a cache. I therefore plan to provide convenience methods for parsing data held in RAM buffers on the W5100 and likewise for writing messages element by element to the RAM buffers. This avoids the need to copy the entire packet to the very limited RAM on the ATmega328P.
I have separately worked on the eventing model which is needed to support the events associated with "things". The approach uses interrupt service handlers to push events onto a queue, which is then popped by an event dispatcher in the microcontroller's main loop. The idea is to ensure that one event handler can't interrupt another, so that coding remains simple with no need for mutexes and other horrors of threaded programming. Long lived tasks need to be broken into a sequence of events, but that isn't that difficult for web developers who are used to the discipline of not blocking on the UI thread of a web browser. I therefore plan to provide an API for pushing events to the queue from software, along with some abstractions for using the timers for timeouts or repeated operations.
I've ordered some samples of the Atmel ATECC108A and ATAES103A chips to play around with hardware based security. Both of these chips are available in 8 pin SOIC devices and support the I2C bus. The ATECC108A supports ecliptic curve public key cryptography and includes a high quality random number generator, SHAR256 hash function, and secure tamper proof storage of keys and certificates. The ATAES103A supports the AES based symmetric encryption/decryption. These chips allow you to perform calculations 10,000 times faster than in software, and just as importantly, avoid the issue of trying to fit large a crypto library into a small Flash memory.
Ecliptic curve public keys can be used to authenticate an IoT device, and likewise for the IoT device to authenticate a server, and importantly software updates from that server. Symmetric encryption and decryption, are more convenient for protecting regular messages. The challenge is how to provision a new IoT device. The public key pair(s) could be set up in the factory, or when the device is installed. Further challenges include periodic updates to crypto settings, and how to handle software updates given that the device typically won't have lots of memory to buffer an update. This suggests a boot strapping process that can be used to recover when an update fails halfway through.
The Web of Things framework needs to expose APIs for registering a new thing along with its model and implementation, and for registering a proxy for a thing identified by a URI for its model. Both APIs are asynchronous.
The code for the framework takes the model and uses it to generate an object with the corresponding events, properties and actions. For a new thing, the properties are bound to getter and setter methods. The getter can be used to couple the thing to a sensor. The setter can be used to couple the thing to an actuator, but must also couple to the transport layer to notify proxies of changes to this property. Actions are bound by name to implementation methods. The implementation must also provide start and stop methods for initialising and de-initialising the thing. For a proxy properties are bound to getter and setter methods that couple to the transport layer. Actions are likewise bound to the transport layer, and can deliver asynchronous results.
C and C++ are a statically typed programming languages, but lacks standard support for reflection. C does support structs, macros and enums, but not getters and setters. C++ further supports classes. Properties can be implemented as a pair of such functions, that support getting and setting the property. Given that the Arduino IDE supports C++, we may as well use C++ for cleaner code. For dynamic types, you can use unions where a tag value can be used to select the correct type. Alternatively, you can directly cast (void *) pointers to be a pointer for the appropriate type.
Here is an example of registering a new thing with the NodeJS server:
The thing() method takes 3 arguments. The first is the name of the thing, which is used to generate the URI that the server will use to expose the thing's model. The second is the thing's model. The third is the thing's implementation with start and stop methods, and a unlock method corresponding to the unlock action.
In the example, the thing has two events named "bell" and "key". The "bell" event has no data, whilst the "key" event has a single boolean argument named "valid". There is a single property "is_open" which is a boolean. There is a single method "unlock" which has no arguments and returns no data. If it did, these would be defined via an object with fields for the arguments and the response. Objects can likewise be used for metadata for properties, e.g. to indicate minimum and maximum values for numeric properties.
To map the above example into C or C++, the first step is to use multiline string literals:
The compiler will concatenate the sequence of string literals into a single literal. Note the use of backslash before every occurrence of the double quote character as JSON requires the use of double quote marks to delimit strings. For a longer model this becomes cumbersome, and it may be more convenient to save models as JSON-LD files. The Arduino Ethernet shield includes an onboard micro SD card slot which can be used to provide a file system via the SD library. Another use for this is to log sensor data for later transfer.
JSON requires a way to support associative arrays. On embedded systems with constrained memory, dynamic memory allocation is problematic, and it is generally better to use statically allocated buffers. A statically allocated memory pool can be used for dynamic allocation. Strings can be stored one after the other with a null byte terminator. The string buffer can then be allocated based upon the average string length for each key. String literals in program code are pre-allocated by the compiler and don't need to be copied to the memory pool. Note that there is an Arduino String library which is worth investigating to see how large it is.
Techniques for implementing associative arrays include hash tables and binary trees. A hash table can be allocated with a fixed number of entries. Each entry references a string and the value. If two strings hash to the same entry, you switch to the next entry (modulo the table size) and try again. The size of the table can be chosen to match the expected number of keys you will need. Allocating a hash table for each JSON associative array would be expensive in memory.
AVL Trees are a variant on balanced binary trees. At each node in the tree you compare the key with the string for that node, if the key is less than the node's string you take the left path. If it is greater you take the right path, otherwise the key is the same as the node's string so you can terminate the search and return the value stored in the node. The nodes are all the same size and hence can be easily allocated from a memory pool. You don't need to compare each byte of the string if you have a string pool that maps each string to a unique number. This can be done with a hash table. This technique offers faster access at the cost of a little more memory, e.g. something like 12 bytes times the maximum number of strings to cater for.
Benoit Blanchon is the developer of the C++ ArduinoJSON library. This uses a fixed memory allocation and claims to have a small footprint. You get to specify the size of the allocated buffer when using the library. Looking at his code, it looks like it is more heavyweight than we need.
Whilst we could use that library, it may be more efficient to create our own code that combines JSON support with associative arrays for thing properties and actions. We will need to parse models to build objects for things, as well as to parse and serialise JSON messages. Here is potential C code for interacting with things.
This assumes that the unlock function takes no arguments and has no results. The C++ invoke function could be declared as:
We can now use va_arg to retrieve the arguments that need to be passed to the action's implementation, as well as the pointer to the function to pass the results to, along with the pointer to the thing itself. For this to work, invoke() would need to access the thing's metadata for this action to determine the number of arguments to pass to the invoked function. It might be simpler to always expect a fixed number of arguments and to recognise when arguments are missing.
How do we set the function to be used when invoking a method on a thing?
Where door12_model is a string literal for the JSON-LD model, door12_start is a function you've provided that takes a single Thing* argument, and unlock_door is a function you've provided that should match the signature for the corresponding named action in the thing's model.
We also need to define the bindings to CoAP and MQTT, along with the supported data encodings. For instance do we plan to support CBOR for a binary encoding of JSON based messages?
A further challenge will be to support discovery of servers and the things they host.
CoAP servers should support GET on the URI ./well-known/core, which returns a list of resources hosted by this server in the CoRE Link Format. This format essentially describes each resource with an RDF triple with the server as the implicit subject, a URI for the link type, and a URI for the resource, and some relation type attributes (rt and if). Here is an example from section 5 in RFC6690:
The rt attribute can be used for a space separated list of names for application specific semantics, whilst the if attribute can be used for a space separated list of names for specific REST interface definition. In both cases, you can use either registered names or URIs. Presumably W3C could register a name such as wotf to indicate support for the CoAP binding for the Web of Things Framework. For example:
This would signal that the server hosts two things, one at the path /sensors/door and the other at the path /sensors/light. A GET on the path would provide the current state of that sensor. CoAP also provides a pub-sub pattern which can be used to listen to asynchronous notifications of updates to the sensor's state. An extended GET request results in a sequence responses.
How is the CoAP server itself discovered? According to RFC6690, the server could listen on a multicast socket. A hub would send a GET request to the appropriate multicast address. Alternatively, the server could discover a hub and then register itself with that hub. Firewalls and Network Address Translation (NAT) present further challenges.
MQTT is different in that an MQTT client must register with an MQTT broker. Having done so, a Web of Things MQTT client could then advertise the things it hosts. The URI for the broker could be preconfigured as in the case for a broker on the Internet (i.e. beyond the firewall). Otherwise we need a way for the MQTT client to discover a broker. Some ideas for broker auto discovery have been proposed by Andy Piper. Andy's ideas would also work for discovery of hubs.
We need to consult more broadly to find out what is considered to be the best practice for both CoAP and MQTT.