Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Portability & Data Management

Source Code Accompanies This Article. Download It Now.


Andrei is principal architect at McObject. He can be reached at [email protected]


Whether an embedded-systems database is developed for a specific application or as a commercial product, portability matters. Most embedded data-management code is still homegrown, and when external forces drive an operating system or hardware change, data-management code portability saves significant development time. This is especially important because the lifespan of hardware is increasingly shorter than that of firmware. For database vendors, compatibility with the dozens of hardware designs, operating systems, and compilers used in embedded systems provides a major marketing advantage.

For real-time embedded systems, database code portability means more than the ability to compile and execute on different platforms: Portability strategies also tie into performance. Software developed for a specific OS, hardware platform, and compiler often performs poorly when moved to a new environment, and optimizations to remedy this are very time consuming. Truly portable embedded systems data-management code carries its optimization with it, requiring the absolute minimum adaptation to deliver the best performance in new environments.

Using Standard C

Writing portable code traditionally begins with a commitment to use only ANSI C. But this is easier said than done. Even code written with the purest ANSI C intentions frequently makes assumptions about the target hardware and operating environment. In addition, programmers often tend to use available compiler extensions. Many of the extensions—prototypes, stronger type checking, and so on—enhance portability, but others may add to platform dependencies.

Platform assumptions are often considered necessary for performance reasons. Embedded code is intended to run optimally on targets ranging from the low-end 8051 family, to 32-bit DSP processors, to high-end Pentium-based SMP machines. Therefore, after the software has been successfully built for the specific target, it is customary to have a performance tuning stage that concentrates on bringing out the best of the ported software on the particular platform. This process can be as straightforward as using compiler-specific flags and optimizations, but often becomes complex and time-consuming and involves patching the code with hardware-specific assembler. Even with C language patches, hardware-optimized code is often obscure and, more importantly, performs poorly on different machines.

Programmers also attempt to maintain portability through conditional code (#ifdef/#else) in a master version that is preprocessed to create platform-specific versions. Yet in practice, this method can create the customization and version-management headaches that portability is meant to eliminate. Another conditional code approach, implementing if-else conditions to select a processor-specific execution path at runtime, results in both unmanageable code and wasted CPU cycles.

All told, it's better to stick to ANSI C and to use truly platform-independent data structures and access methods as much as possible to work around compiler- and platform-specific issues.

In the process of creating the eXtremeDB in-memory embedded database at McObject (where I work), we developed several techniques that are useful for any developer seeking to write highly portable, maintainable, and efficient embedded code. Some of these techniques apply to embedded systems portability generally, but are particularly important for data management. In many cases, an embedded application's database is its most complex component, and getting it right the first time (by implementing highly portable code) saves programmer-months down the road. Other techniques I present here, such as building lightweight database synchronization based on a user-mode spinlock, constitute specific key building blocks for portable embedded systems databases.

Word Sizes

One proven technique is to avoid making assumptions about integer and pointer sizes. Defining the sizes of all base types used throughout the database engine code, and putting theses typedefs in a separate header file, makes it much easier to change them when moving the code from one platform to another or even using a different compiler for the same hardware platform; see Listing One.

Defining a pointer size as a sizeof(void*) and using the definition to calculate memory layout offsets or using it in pointer arithmetic expressions avoids surprises when moving to a platform such as ZiLOG eZ80 with 3-byte pointers:

#define PTRSIZE sizeof(void *)

The void* type is guaranteed to have enough bits to hold a pointer to any data object or to a function.

Data Alignment

Data alignment can be a portability killer. For instance, on various hardware architectures a 4-byte integer may start at any address, or start only at an even address, or start only at a multiple-of-four address. In particular, a structure could have its elements at different offsets on different architectures, even if the element is the same size. To compensate, our in-memory data layout requires data object allocation to start from a given position, and aligns elements via platform-independent macros. Listing Two aligns the position of the data object (pos) at a 4-byte boundary.

Another alignment-related pitfall is that, on some processors (such as SPARC), all data types must be aligned on their natural boundaries. Using Standard C data types, integers are aligned as follows:

  • short integers are aligned on 16-bit boundaries.
  • int integers are aligned on 32-bit boundaries.
  • long integers are aligned on either 32-bit boundaries or 64-bit boundaries, depending on whether the data model of the kernel is 64-bit or 32-bit.
  • long long integers are aligned on 64-bit boundaries.

Usually, the compiler handles these alignment issues and aligns the variables automatically; see Listing Three. But redefining the way a variable or a structure element is accessed, while possible and sometimes desirable, can be risky. For example, consider the declaration in Listing Four of an object handle (assuming the data object size is N bytes). Such opaque handle declarations are commonly used to hide data object representation details from applications that access the data object with an interface function, using the handle merely as the object identifier as shown in Listing Five. Because d is a byte array, the address is not memory aligned. The handle is further used as an identifier of the object to the library:

void* function ( appData *handle);

Furthermore, internally the library "knows" about the detail behind the handle and declares the object as a structure with the elements defined as short integers, long integers, references, and so on; see Listing Six.

Accessing object elements leads to a bus error because they are not correctly aligned. To avoid the problem, we declare in Listing Seven the object handle as an array of operands of the maximum size (as opposed to a byte array). In this case, the compiler automatically aligns the operands to their natural boundaries, preventing the bus error.

Word Endianness

Byte order is the way the processor stores multibyte numbers in memory. Big-endian machines, such as Motorola 68k and SPARC, store the byte with the highest value digits at the lowest address while Little-endian machines (Intel 80x86) store it at the highest address. Furthermore, some CPUs can toggle between Big- and Little-endian by setting a processor register to the desired endian-architecture (IBM PowerPC, MIPS, and Intel Itanium offer this flexibility). Therefore, code that depends on a particular orientation of bits in a data object is inherently nonportable and should be avoided. Portable, endian-neutral code should make no assumptions of the underlying processor architecture, instead wrapping the access to data and memory structures with a set of interfaces implemented via processor-independent macros, which automatically compile the code for a particular architecture.

Furthermore, a few simple rules help keep the internal data access interfaces portable across different CPU architectures.

  • Access data types natively; for instance, read an int as an integer number as opposed to reading 4 bytes.
  • Always read/write byte arrays as byte arrays instead of different data types.
  • Bit fields defined across byte boundaries or smaller than 8 bits are nonportable. When necessary, to access a bit field that is not on byte boundaries, access the entire byte and use bit masks to obtain the desired bits.
  • Pointer casts should be used with care. In endian-neural code, casting pointers that change the size of the pointed-to data must be avoided. For example, casting a pointer to a 32-bit value 0x12345678 to a byte pointer would point to 0x12 on a Big-endian and to 0x78 on a Little-endian machine.

Compiler Differences

Compiler differences often play a significant role in embedded systems portability. Although many embedded environments are said to conform to ANSI Standards, it is well known that in practice, many do not. These nonconformance cases are politely called "limitations." For example, although required by the Standard, some older compilers recognize void, but don't recognize void*. It is difficult to know in advance whether a compiler is in fact a strict ANSI C compiler, but it is very important for any portable code to follow the Standard. Many compilers allow extensions; however, even common extensions can lead to portability problems. In our development, we have come across several issues worth mentioning to avoid compiler-dependent problems.

When char types are used in expressions, some compilers treat them as unsigned, while others treat them as signed. Therefore, portable code requires that char variables be explicitly cast when used in expressions; see Listing Eight.

Some compilers cannot initialize autoaggregate types. For example, Listing Nine may not be allowed by the compiler. The most portable solution is to add code that performs initialization, as in Listing Ten.

C-Runtime Library

Databases in nonembedded settings make extensive use of the C runtime. However, embedded systems developers commonly avoid using the C runtime, to reduce memory footprint. In addition, in some embedded environments, C-runtime functions, such as dynamic memory allocations/deallocations (malloc()/free()), are implemented so poorly as to be virtually useless.

An alternative, implementing the necessary C-runtime functionality within the database runtime itself, reduces memory overhead and increases portability. For main-memory databases, implementing dynamic memory management through the database runtime becomes vitally important because these engines' functionality and performance are based on the efficiency of memory-oriented algorithms. We incorporate a number of portable embedded memory-management components that neither rely on OS-specific, low-level memory-management primitives, nor make any fundamental assumptions about the underlying hardware architecture. Each of the memory managers employs its own algorithms, and is used by the database runtime to accomplish a specific task.

  • A dynamic memory allocator provides functionality equivalent to the standard C runtime library functions malloc(), calloc(), free(), and realloc() according to the POSIX Standard. The heap allocator is used extensively by the database runtime, but also can be used by applications.
  • Another memory manager is a comprehensive data layout page manager that implements an allocation strategy adapted to the database runtime requirements. Special care is taken to avoid introducing unnecessary performance overhead associated with multithreaded access to the managed memory pools.
  • A simple and fast single-threaded memory manager is used while parsing SQL query statements at runtime, and so on.

Synchronization

Databases must provide concurrent access across multiple simultaneously running tasks. Regardless of the database locking policies (optimistic or pessimistic, record level or table level, and the like), this mechanism is usually based on kernel synchronization objects, such as semaphores, provided by the underlying OS. While each operating system provides very similar basic synchronization objects, they do so with considerably different syntax and usage, making it nontrivial to write portable multithreaded synchronization code. In addition, an embedded systems database must strive to minimize the expense associated with acquiring kernel-level objects. Operating-system semaphores and mutexes are usually too expensive, in performance terms, to be used in embedded settings.

In our case, the solution was to build up the database runtime synchronization mechanism based on a simple synchronization primitive—the test-and-set method—that is available on most hardware architectures. Foregoing the kernel for a hardware-based mechanism reduces overhead and increases portability. All we must do is port three functions to a specific target. This approach can also be used for ultra low-overhead embedded systems where no operating system is present (hence, no kernel-based synchronization mechanism is available). Furthermore, the performance of the test-and-set "latch" in Listing Eleven remains the same regardless of the target operating system and depends only on the actual target's CPU speed. Listing Twelve(a) provides implementations for Win32, Listing Twelve(b) the Sun SPARC platform, and Listing Twelve(c) is the Green Hills INTEGRITY OS.

The concept of mutual exclusion is crucial in database development—it provides a foundation for the ACID properties that guarantee safe sharing of data. The synchronization approach just discussed slants toward the assumption that for embedded systems databases, it is often more efficient to poll for the availability of a lock rather than allow fair preemption of the task accessing the shared database.

It is important to note that even though this approach is portable in the sense that it provides consistent performance of the synchronization mechanism over multiple operating systems and targets, it does not protect against the "starvation" of tasks waiting for, but not getting, access to the data. Also, provisions must be made for the database system to clean itself up if the task holding the lock unexpectedly dies, so that other tasks in line for the spinlock do not wait eternally. In any case, embedded data management is often built entirely in memory, generally requires a low number of simultaneous transactions, and the transactions themselves are short in duration. Therefore, the chances of a resource conflict are low and the task's wait to gain access to data is generally shorter than the time needed for a context switch.

Nonportable Features

While replacing C runtime library functionality and memory managers, and implementing custom synchronization primitives lead to greater data-management code portability, sometimes it is not possible or practical to overload the database with functionality—such as network communications or filesystem operations—that belongs to the operating system. A solution is to not use these services directly, or recreate them in the database, but instead create an abstraction of them that is used throughout the database engine code. The actual implementation of the service is delegated to the application. This allows hooking up service implementations without changing the core engine code, which again contributes to portability.

For example, data-management solutions often include online backup/restore features that, by their nature, require file system or network interaction. Creating an abstraction of stream-based read and write operations, and using this abstraction layer within the database runtime during backup, allows the database to implement the backup/restore logic while staying independent of the actual I/O implementation. At the same time, this approach allows a file-based, socket-based, or other custom stream-based transport to be plugged in with no changes needed to the database runtime. Listing Thirteen illustrates such a plug-in interface. The application needs to implement the actual read-from-stream/write-to-stream functionality; see Listing Fourteen.

Another example of the database "outsourcing" services to the application involves network communications. Embedded databases often must provide a way to replicate the data between several databases over a network. Embedded settings always demand highly configurable and often deterministic communication that is achieved using a great variety of media access protocols and transports. Thus, as a practical matter, a database should be able to adopt the communication protocol used for any given embedded application, regardless of the underlying hardware or the operating system. Instead of communicating directly with the transport or a protocol, a database runtime goes through a thin abstraction layer that provides a notion of a "communication channel." Like the backup/restore interfaces, the network communication channel can also be implemented via a stream-based transport; see Listing Fifteen. The database uses a set of API functions that provide the ability to initiate and close the channel, send and receive the data, and so on.

Conclusion

By following general rules of developing portable code—such as using Standard C and avoiding assumptions about hardware related parameters—you can greatly simplify the reuse of your data-management code in new environments. And new approaches to implementing standard database services, such as those presented here, can ensure that the old concept of a database delivers the portability, performance, and low-resource consumption demanded for embedded systems.

DDJ



Listing One

#ifndef BASE_TYPES_DEFINED

typedef unsigned char   uint1;
typedef unsigned short  uint2;
typedef unsigned int    uint4;
typedef signed char     int1;
typedef short           int2;
typedef int             int4; 

#endif
Back to article


Listing Two
#define ALIGNEDPOS(pos, align) ( ((pos) + (align)-1) & ~((align)-1) ) 
pos = ALIGNEDPOS(pos, 4);
Back to article


Listing Three
char c;
//(padding)
long  l;       - the address is aligned
Back to article


Listing Four
#define handle_size      N  
typedef uint1 hobject    [handle_size ]; 
Back to article


Listing Five
typedef struct  appData_ { hobject h; } appData;
char c;
appData d;    /* d is not aligned */
Back to article


Listing Six
typedef struct objhandle_t_
{
  ...
  obj_h         po;            
  ...
  uint4         mo;            
  uint2         code;
  ...
} objhandle_t;
Back to article


Listing Seven
#define handle_size      N  
#define handle_size_w 
((( handle_size + (sizeof(void*) -1)) & ~(sizeof (void*) -1)) / sizeof(void*));

typedef void * hobject [handle_size_w ]; 
Back to article


Listing Eight
#if defined( CFG_CHAR_CMP_SIGNED )
#define CMPCHARS(c1,c2) ((int)(signed char)(c1)-(int)(signed char)(c2) )
#elif defined( CFG_CHAR_CMP_UNSIGNED )
#define CMPCHARS(c1,c2) ((int)(unsigned char)(c1)-(int)(unsigned char)(c2) )
#else
#define CMPCHARS(c1,c2) ( (int)(char)(c1) - (int)(char)(c2) )
#endif
Back to article


Listing Nine
struct S { int i; int j; };
S s = {3,4};
Back to article


Listing Ten
struct S { int i; int j; };
S s;
s.i = 3; s.j = 4;
Back to article


Listing Eleven
/* this is the TAS (test-and-set) latch template*/
void sys_yield()
{
  /* relinquish control to another thread */    
}
void sys_delay(int msec)
{
  /* sleep */
}
int  sys_testandset( /*volatile*/ long * p_spinlock)
{
  /* The spinlock size is up to a long ;
   * This function performs the atomic swap (1, *p_spinlock) and returns
   * the previous spinlock value as an integer, which could be 1 or 0
  */
}
Back to article


Listing Twelve (a)
#ifndef SYS_WIN32_H__
#define SYS_WIN32_H__

/* sys.h definitions for WIN32 */

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <process.h>

#define sys_yield() SleepEx(0,1) /*yield()*/
#define sys_delay(msec) SleepEx(msec,1)
#define sys_testandset(ptr) InterlockedExchange(ptr,1)

#endif  /* SYS_WIN32_H__ */
Back to article


(b)
#ifndef SYS_SOL_H__
#define SYS_SOL_H__

/* sys.h definitions for Solaris */

#include <sys/time.h>
#include <unistd.h>
#include <sched.h>

int  sys_testandset( /*volatile*/ long * p_spinlock)
{
  register char result = 1;
  volatile char *spinlock = ( volatile char * ) p_spinlock;
    __asm__ __volatile__(
        "   ldstub  [%2], %0    \n"
:       "=r"(result), "=m"(*spinlock)
:       "r"(spinlock));
    return (int) result;
}
void sys_yield()
{
  sched_yield();
}
void sys_delay(int msec)
{ /* */ }

(c)
#ifndef SYS_GHSI_H__
#define SYS_GHSI_H__

/* sys.h definitions for Green Hills Integrity OS */
#include <INTEGRITY.h>

void sys_yield()
{
  Yield();
}
void sys_delay(int msec)
{
}
int  sys_testandset(long * p_spinlock)
{
  return ! ( Success == TestAndSet(p_spinlock, 0, 1) );
}
Back to article


Listing Thirteen
/* abstraction of write and read stream interfaces;
 * a stream handle is a pointer to the implementation-specific data 
*/
typedef int (*stream_write)
  ( void *stream_handle, const void * from, unsigned nbytes);
typedef int (*stream_read)
  ( void *stream_handle, /*OUT*/ void * to, unsigned max_nbytes);
/* backup the database content to the output stream */
RETCODE db_backup
  ( void * stream_handle, stream_write output_stream_writer, void * app_data);
/* restore the database from input stream */
RETCODE  db_load
   ( void * stream_handle, stream_read input_stream_reader, void *app_data);
Back to article


Listing Fourteen
int file_writer(void *stream_handle, const void * from, unsigned nbytes)
{
  FILE *f = (FILE*)stream_handle;
  int nbytes = fwrite(from,1,nbytes,f);
  return nbytes;
}
int file_reader(void *stream_handle, void * to, unsigned max_nbytes)
{
  FILE *f = (FILE*)stream_handle;
  int nbytes = fread(to,1,max_nbytes,f);
  return nbytes;
}
Back to article


Listing Fifteen
#define channel_h void* 
typedef int (*xstream_write)(channel_h ch, const void * from,
                             unsigned nbytes, void * app_data);
typedef int (*xstream_read) (channel_h ch, void * to,
                             unsigned max_nbytes, void* app_data);
typedef struct {
  xstream_write fsend;
  xstream_read  frecv;
  ...
 } channel_t, *channel_h;
Back to article


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.