Data Structures on Codesys, Part 1 : Double Linked List

In the world of computer science, we make a big deal about data structures and algorithms - that is, the knowledge of data organization and effective manipulation. In the world of PLC programming, we know about arrays. Maybe queues. And that's pretty much it.

To be fair, most PLC platforms do not give us the opportunity to play with traditional data structures, due to the lack of heap memory allocation. Codesys is an outlier here, as an amount of heap memory can be set aside for dynamic instantiation. Usually, PLC runtimes keep all memory preallocated: before the program ever runs we know the type of every variable used. With dynamic allocation, we can create new objects and structures at runtime. This gives us the opportunity to have some fun with the software.

This post will concern the double linked list. I will start with a base skeleton, that I will refine and present as time goes on.

I also want to note that this is NOT for production use. This is an educational exploration into the Codesys memory model using programming methods that are unusual outside of that platform.

Using the heap in a production program is discouraged because of the risk of dangling pointers (pointers referencing manually freed or out of scope memory), memory leaks (unreclaimable bits of memory which contain data but are pointed to by nothing) and null pointer access, all of which can crash a program (and thus a machine), causing loss of control of the machine and unpredictable, possibly dangerous results.

This is especially true using __NEW() and __DELETE() as I will be doing to play in the heap. Creating objects on the heap in this manner is expensive, can affect PLC cycle time in unpredictable ways and as our data will be of different sizes and we will not standardize that, heap memory will inevitably become fragmented like Swiss cheese over time.

For our didactic purposes, __NEW() and __DELETE() are good enough, but if you're interested in dynamic instantiation, 3S has libraries available that mitigate these problems. I will not be using them here for simplicity's sake and this should reinforce the fact that this is not production code.

Finally, keep in mind that unlike a traditional PC program, a PLC program has a scan cycle and it's all too easy to write code that will create objects on the heap every scan. That will MAJOR FAULT a PLC quickly.

If for whatever crazy reason you decide to take niche code from a random person on the Internet and put that into your machine, keep in mind that any code example is provided AS-IS, has not been tested in an industrial environment (and will not be) and is provided without warranty, express or implied. You accept any and all responsibility for the behaviour and safety of your machine. If you truly need some kind of linked list implementation, 3S has a library for element collections which contains linked lists. Use that instead.

The double linked list

For those of us coming from a more traditional controls background, I will explain a little about this data structure.

The double linked list is composed of a series of node structures stored in the heap which are cross-linked with each other. Each node structure contains a stored value, a pointer to the previous node in the chain and a pointer to the next node in the chain. This allows for easy bidirectional traversal through the list.

A diagram of a double linked list

Unlike an array, the size of a linked list is dynamic. The nodes are dynamically constructed on the heap and thus not contiguous in memory. This allows the linked list to naturally grow and shrink in size as we add or remove nodes. There is no need to displace other data or the structure itself in a space with a larger contiguous memory block. For the mechanically inclined among us, it's a bit like a chain versus a timing belt. If you need to change the size of your timing belt, you need to buy another one, but you can just add or remove links to the chain.

The downside to this dynamic nature is that some common operations tend to be slower. Because of this dynamic nature, operations in the middle of the linked list have a worst case complexity of O(n), where n is the number of nodes in the list. In particular, any array element access is O(1), or constant time, no matter the size of the array or the position of the element. Linked list element access by positional index is O(n) due to the traversal. Operations at the start or the end of a linked list are constant time, due to the linked list itself always possessing a pointer to its ends. Notably, insertion at the front of a linked list is O(1) whereas insertion at the front of an array is O(n) because all existing elements need to be shifted one position for the insertion to happen.

Genericity

A data structure is most useful when it is generic: when it can contain any type of element. Before generics or templates, a data node would contain one type and if we needed other types, we would need to add a new type of node. Modern languages now have generic or template support, where the same code may be reused for many different types without modification to the underlying code.

Codesys has limited generic support due to the nature of PLC programming. IEC 61131-3 specifies the ANY type which stands for, well, any type, as well as more limited subsets (such as ANY_DATE, ANY_NUM, and so on). These types are useful when we want to design polymorphic functions, but of limited utility for true genericity. In Codesys, ANY can only be used as an input to a function, function block or method.

However, what underlies ANY is a struct called __SYSTEM.AnyType. This struct has the following members:

STRUCT AnyType:
    pValue: POINTER TO Byte; // a pointer to the first byte of the data underneath ANY
    diSize: DINT; // the size in bytes of the data
    TypeClass: __SYSTEM.TYPE_CLASS; // the type of the data

Because this is a mangled __SYSTEM struct, we're probably not meant to use it. For educational purposes, it makes a bit of sense here. Note that the TypeClass member is not exhaustive, because Codesys regards any FB or UDT as a TYPE_CLASS.USERDEF. Their actual types are erased at runtime. This structure thus gives us some protection against, say, putting a REAL into a DINT, but won't restrict us from trying to copy FB_Motor into UDT_UserInfo if both happen to be the same size in memory. For genericity, I think that's the best we can do. Feel free to email me with other solutions, though.

Programming the basics

We will create our linked list in a library, so we can benefit from the INTERNAL access modifier to hide away some implementation details. At first, we will make just a linked list and we will keep it concrete, without using interfaces. We will attempt to abstract it more in later revisits.

First of all, we need to turn on dynamic heap allocation as well as allocate a suitable allowed memory amount. Limit the heap size to some reasonable amount of memory, like 4 MB or so.

Codesys memory setting screenshot

Node

Let's start with the Node.

{attribute 'enable_dynamic_creation'}
FUNCTION_BLOCK INTERNAL Node
VAR
	_value: POINTER TO BYTE; // Pointer to the data
	_size: DINT; // Data size
	_typeClass: __SYSTEM.TYPE_CLASS; // Data type
	_next: POINTER TO Node; // The next node is the list
	_previous: POINTER TO Node; // The previous node in the list
END_VAR

The pragma {attribute 'enable_dynamic_creation} is necessary in order to instantiate the nodes on the heap.

This function block has no I/O and no body. It only contains two pointers to its neighbours and a destructured version of the __SYSTEM.AnyType structure we've seen. I've found it is easier to handle the contents of the structure from its component parts this way, but I'm sure this could be successful by keeping a structure inside the function block instead.

The first thing we need to do is to declare an FB_Init method to actually be able to initialize this naturally. Through my tests, I've found that ANY does not play well with FB_Init so we will not be able to initialize the value with that method. But because this isn't a user-facing object, that's OK with me.

METHOD FB_Init: BOOL
VAR_INPUT
    bInitRetains: BOOL; // TRUE: the retain variables are initialized (reset warm / reset cold)
    bInCopyCode: BOOL;  // TRUE: the instance will be copied to the copy code afterward (online change)   
	previous: POINTER TO Node;
	next: POINTER TO Node;
END_VAR


THIS^._next := next;
THIS^._previous := previous;

// Instantiate new value destructured AnyType to null
THIS^._value := 0;
THIS^._size := 0;
THIS^._typeClass := TYPE_CLASS.TYPE_NONE;

In this initialization method, we set the provided neighbours and initialize our destructured AnyType to null or zero values. As noted previously, we will set the data later.

The _value field will act as a private buffer for the data, so the node will hold a copy of whatever was passed in.

Now we define the accessor and mutator properties. We will return references instead of pointers for the nodes, since they make the syntax a bit more pleasant (no need for endless dereferences).

PROPERTY INTERNAL Previous : REFERENCE TO Node

Previous REF= THIS^._previous^; // Get
THIS^._previous := ADR(Previous); // Set

PROPERTY INTERNAL Next : REFERENCE TO Node

Next REF= THIS^._next^; // Get
THIS^._next := ADR(Next); // Set

PROPERTY INTERNAL Value : __SYSTEM.AnyType

// Get
VAR
	val: __SYSTEM.AnyType;
END_VAR

// Reconstruct AnyType struct
// This passes the POINTER, it does not pass the VALUE by copy
val.pValue := THIS^._value;
val.diSize := THIS^._size;
val.TypeClass := THIS^._typeClass;
Value := val;

The first two are relatively straightforward. I'm passing out references to the nodes instead of pointers, because it makes the syntax a bit nicer (cuts on the dereferencing) and allows for the use of "fluent interfaces" where we can chain multiple access calls (example: node.Previous.Next.Previous). I just have to be careful to use REF= instead of := every time I want to pass this reference around because with references, := will attempt a copy by value, which is not usually the behaviour we want in this library.

The Value property is doing some lifting. We're reconstructing the __SYSTEM.AnyType object and passing it out to the caller. The caller has the original pointer, which allows for a bit quicker access later when we'll do the linked list methods.

Now you're might be thinking, we're still not setting any data here. I've offloaded this to a separate method to use a pattern we will see again later when we implement the list.

METHOD INTERNAL TrySetValue : BOOL
VAR_INPUT
	value: ANY;
END_VAR
VAR
	newBuffer: POINTER TO BYTE;
END_VAR

// If sizes are different we need to recreate the memory buffer
IF value.diSize <> THIS^._size THEN
	// Attempt to initialize a new buffer
	newBuffer := __NEW(BYTE, value.diSize);
	
	IF newBuffer = 0 THEN
		TrySetValue := FALSE;
		RETURN;
	END_IF
	
	// If this node already held an address in its value pointer
	// then free that memory
	IF THIS^._value <> 0 THEN
		__DELETE(THIS^._value);
	END_IF

	// Assign newly obtained pointer. This node now points to
	// wherever newBuffer is
	THIS^._value := newBuffer;
END_IF

// Deep copy the data inside the memory location
SysMem.SysMemCpy(THIS^._value, value.pValue, value.diSize);

// Assign size and type
THIS^._size := value.diSize;
THIS^._typeClass := value.TypeClass;

// Successfully completed
TrySetValue := TRUE;

The crux of the issue here is that creating a node on the heap and creating a buffer on the heap are two different operations but the node cannot function without the heap. We need a way to know whether creating the buffer has succeeded so the node is legal, because if the buffer creation fails I'll get a new valid node FB with a buffer pointing to null, which is...problematic. I've chosen the old school Try___ as found in C#. This attempts to write the new value to the node, returning TRUE on success and FALSE on failure. We will be able to know if a node is in an invalid state with the __NEW() returning null or this returning FALSE.

If the memory buffers are the same size, I can just overwrite the data. This helps reduce the occurrence of heap creation, which can be taxing on the PLC.

With this implementation, the node gets a deep copy of the data passed inside the method. The source data object remains with the caller. Therefore, the node fully owns its memory. Because the list methods will be handing copies of node data, this reduces the risk of dangling pointers as the user is not responsible for handling node memory.

It's worth noting that I'm not doing anything special as of yet if the data types differ. This allows the node to change its contents, even at runtime, and to have a list containing many different types of data throughout its nodes. Once we get to refinements this is probably going to change.

Because this node creates stuff on the heap in FB_Init, it is responsible for destroying it when needed. Therefore, we'll need an implementation for FB_Exit too.

METHOD FB_Exit: BOOL
VAR_INPUT
    bInCopyCode: BOOL;  // TRUE: the exit method is called in order to leave the instance which will be copied afterwards (online change).  
END_VAR


// If value pointer contains something, free the memory
IF THIS^._value <> 0 THEN
	__DELETE(THIS^._value);
END_IF

This simply frees the memory occupied by the copy of the value inside the node, if it exists.

Starting the DoubleLinkedList

We have our Node container FB. Those are the "links" of the linked list. Now we can start on the double linked list itself.

FUNCTION_BLOCK PUBLIC DoubleLinkedList
VAR
	_head: POINTER TO Node; // Sentinel node - start of list
	_tail: POINTER TO Node; // Sentinel node - end of list
	_size: DINT; // The size of the list in number of nodes, minus the sentinels
	_ready: BOOL := FALSE; // The linked list has been correctly initialized and is ready to use
END_VAR

We are using a "dual sentinel" linked list style. When instantiating the block, we will create two empty sentinel nodes to represent the end nodes of the queue. This will simplify the code for the methods on the list since we will always know where the beginning and the end of the list are. We do not need to treat operations on the beginning or the end of the list as special cases, and all this costs is two more nodes in the heap. I'll take that trade.

Again a pretty simple function block with only local variables and no body. We'll also be doing most of our works through methods on this one. Let's start with FB_Init.

METHOD FB_Init: BOOL
VAR_INPUT
    bInitRetains: BOOL; // TRUE: the retain variables are initialized (reset warm / reset cold)
    bInCopyCode: BOOL;  // TRUE: the instance will be copied to the copy code afterward (online change) 
END_VAR

// Do not recreate sentinels on online edit!
IF bInCopyCode THEN 
	RETURN;
END_IF

// Create sentinels on the heap. These will not carry values.
THIS^._head := __NEW(Node(next := 0, previous := 0));
THIS^._tail := __NEW(Node(next := 0, previous := 0));

// Guard for null pointers
IF THIS^._head <> 0 AND THIS^._tail <> 0 THEN
    // Point sentinels to each other
    THIS^._head^.Next REF= THIS^._tail^;
    THIS^._tail^.Previous REF= THIS^._head^;
    
    // Initialize size
    THIS^._size := 0;
    
    // List initialized and ready
    THIS^._ready := TRUE;
ELSE
    // Clean up whichever node has instantiated in the heap
    IF THIS^._head <> 0 THEN
        __DELETE(THIS^._head);
        THIS^._head := 0;
    END_IF
    
    IF THIS^._tail <> 0 THEN
        __DELETE(THIS^._tail);
        THIS^._tail := 0;
    END_IF
END_IF

During initialization, we summon the sentinels to the heap, point them towards each other and set the size to zero. We leave the value field of these nodes pointing to null, and the Previous node of _head and the Next node of _tail will be null pointers also.

Some important remarks here: first of all, if the runtime fails to create a node on the heap, the pointer returned will be null. We will be in the unenviable position of having an unusable linked list without one or both of its sentinels, so we must guard against this eventuality. I included a _ready flag that will indicate whether the linked list is correctly initialized and ready to use, and we will use this to block any access to a list which failed to initialize correctly.

Finally, notice the use of the input bInCopyCode to return early from the initialization. That input is a system input triggered during online edits when, in certain conditions, static memory must be shuffled around (for example, because a FB implementation changed in size). Not blocking the initialization at this stage would risk creating a huge memory leak as the linked list would be reset to a pair of sentinel nodes and all the other nodes would be lost in the ether.

Following steps

I will stop this post here as it's getting pretty long. We now have:

Usable Node function block with some janitorial memory management
Basic DoubleLinkedList function block

For the next step, we will need to decide how to give access to the user to elements of the list. We will be creating yet another function block for this functionality, and we will also start implementing some methods of the linked list with this function block. Stay tuned.

MajorFault.io