UEFI Application Programming: SysList and SysListO (Part 2)

In the previous article I introduced the basic functions of the System Object library that I use when writing C applications in UEFI. In this article I will extend this by introducing two container objects: a list of arbitrary data and a list of objects. To those of you wondering, "Where's the UEFI?" I understand. Don't worry, in the next article I will introduce the next two containers and use them in my UEFI HII application.

 

SysList
The SysList container is derived from the System Object and acts as a list of pointers to arbitrary data. The list does not free the data when removed from the list. Each of the list entries points to the data. In this way, the list can organize any data.

 

The first entry in the list is called the head. The last entry in the list is called the tail. New list entries can be added before the head, after the tail or before or after any other entry. It is possible to navigate to the next entry or the previous entry, but there is no easy way to navigate to the nth entry. Arrays are more suitable for that sort of behavior.

 

SysList is implemented with the SYS_LIST structure, as follows:

typedef struct _SYS_LIST {
  SYS_OBJ Obj; // standard object structure. must be first.

  SYS_LIST_ENTRY Header;
} SYS_LIST; 

The first thing to notice is that the System Object structure, SYS_OBJ is placed first. This is true for all of the derived object containers. Header, in turn, acts as a dummy list entry which points to the first and last list entries. The entries look like this:

typedef struct _SYS_LIST_ENTRY {
  SYS_LIST_ENTRY *Prev;
  SYS_LIST_ENTRY *Next;
  VOID *Value;
} SYS_LIST_ENTRY;

 

Each entry points to the next and previous list entry OR the header's dummy entry. If it points to the dummy entry, it means it is either the first or the last list entry. Each entry also points to the data. That is, the list itself does not contain the data, only a pointer to the data.

 

Here are the standard functions for manipulating lists:

• SysListInit - Initialize an empty list container.
• SysListEmpty - Free all list entries and reset to empty. Does not free data.
• SysListIsValid - Return if pointer points to a valid list container.
• SysListIsEmpty - Return whether list contains any list entries.
• SysListAddTail - Add a new list entry for data after the last list entry.
• SysListRemoveTail - Remove last list entry and return pointer to data.
• SysListRemoveHead - Remove first list entry and return pointer to data.
• SysListGetNext - Iterate through a list container.

Here are some common tasks using lists:

 

1. Initialize a declared list:

 

SYS_LIST l;
SysListInit(&l);

 

2. Create a new list:

 

SYS_LIST *pl;
pl == SysNew(SysList);
if (pl == NULL) {
  // error...
}

 

3. Add an entry to the list:

 

VOID *p;  // ptr to data
SYS_LIST *pl;
if (!SysListAddTail (pl, p)) {
  // error...
}

 

4. Remove all entries in a list:

 

SYS_LIST *pl;
SysListEmpty(pl);

 

5. Remove and free all entries in a list:

 

SYS_LIST *pl;
while (!SysListIsEmpty(pl)) {
  free (SysListRemoveTail(pl));
}

 

6. Walk through all entries in the list. This function uses SYS_LIST_POS as an abstract type that refers to the current position in a list, as opposed to the list's data.

 

SYS_LIST *pl;
SYS_LIST_POS pos;
VOID *p;
for (pos = NULL; SysListGetNext (pl, &pos, &p); ) {
  // ... do something with p ...
}

 

SysListO
The SysListO container is derived from SysList. But, instead of pointers to arbitrary data, the list contains system objects. When adding objects to the list, a copy is made of the specified object and when delete list entries, the object is deleted. Any object derived from SysObj can be in the list.

The SysListO is a simple, repurposed version of SysList. So, it doesn't need much more than a typedef and a few new library functions that talk about SysObj instead of VOID *. For example:

typedef SYS_LIST SYS_LIST_O;

And here's an example of a  function prototype that uses SYS_OBJ instead of VOID *:

BOOLEAN
SysListOGetNext (
  IN CONST SYS_LIST_O *p,
  IN OUT SYS_LIST_POS *Pos,
  OUT SYS_OBJ **Value
  );

Here are the functions provided by the library for object lists.

• SysListOInit - Initialize object list.
• SysListOEmpty - Empty an object list.
• SysListOAddTail - Add a copy of an object to the end of the list.
• SysListORemoveTail - Remove the last object from the list and return a pointer to it.
• SysListORemoveHead - Remove the first object from the list and return a pointer to it.
• SysListOGetNext - Iterate through all objects in the list, returning a pointer.

Conclusion
So this gives us a real container! Simple, non-invasive and powerful.

Next time, I will introduce how I use these in a real program as two new containers SysStrA (a dynamic ASCII string container) and SysListStrA (a list of ASCII strings) make their appearance in the command-line handling of my UEFI HII parser.

The full source code for the library will be available at the end of this blog series, but if you want more right now, you can see much of the code for SysList in the next section. SysListO is very similar.

The Nitty-Gritty Details

SysListInit - Initialize a List

SYS_LIST *
SysListInit (OUT SYS_LIST *p)
{
  if (SysObjInit (
        &p->Obj,
        SYS_LIST_SIGNATURE,
        sizeof (SYS_LIST),
        (SYS_OBJ_INIT) SysListInit,
        (SYS_OBJ_EMPTY) SysListEmpty,
        NULL,
        (SYS_OBJ_VALID) SysListIsValid,
        NULL) == NULL) {
    SYSINFO ("unable to initialize List container.\n");
    return NULL;
  }
 
  p->Header.Prev = p->Header.Next = &p->Header;
  p->Header.Value = 0;
  return p;
}

SysListEmpty - Empty a List

SYS_LIST *
SysListEmpty (IN OUT SYS_LIST *p)
{
  if (!SysIsValid (p)) {
    SYSINFO ("unable to empty List container.");
    return NULL;
  }
 
  while (!SysListIsEmpty (p)) {    // remove all entries.
    SysListRemoveHead (p);
  }
 
  return p;                         // return pointer to now-empty List container.
}

SysListIsValid - Check whether list is valid  

 

BOOLEAN
SysListIsValid (IN CONST SYS_LIST *p)
{
  if (!SysObjIsValid (&p->Obj, SYS_LIST_SIGNATURE, sizeof (SYS_LIST))) {
    SYSINFO ("invalid List container.\n");
    return FALSE;
  }
 
  return TRUE;
}

SysListAddTail - Add a list entry to the end of the list 

 

BOOLEAN
SysListAddTail (
  IN OUT SYS_LIST *p,
  IN VOID *v
  )
{
  SYS_LIST_ENTRY *e;

  if (!SysListIsValid (p)) {
    SYSINFO ("unable to add tail.\n");
    return FALSE;
  }

  e = malloc (sizeof (SYS_LIST_ENTRY));
  if (e == NULL) {
    SYSINFO ("out of memory.\n");
    return FALSE;
  }

 

  e->Prev = p->Header.Prev;
  e->Next = &p->Header;
  e->Value = v;

  p->Header.Prev->Next = e;
  p->Header.Prev = e;
  return TRUE;
}

 

SysListRemoveTail - Remove last list entry in the list

VOID *
SysListRemoveTail (IN OUT SYS_LIST *p)
{
  SYS_LIST_ENTRY *e;
  VOID *v;
  if (!SysListIsValid (p)) {
    SYSINFO ("unable to remove tail.\n");
    return NULL;
  }
 
  if (SysListIsEmpty (p)) {
    SYSERR ("list is empty. unable to remove List element.\n");
    return NULL;
  }
  e = p->Header.Prev;                // retrieve the tail entry.
  p->Header.Prev->Next = e->Next;    // unlink the tail entry.
  p->Header.Prev = e->Prev;
  v = e->Value;                   // retrieve the value from old tail entry.
  free(e);                           // delete the old tail entry.
  return v;    
}

SysListGetNext - Iterate through list entries
BOOLEAN
SysListGetNext (
  IN CONST SYS_LIST *p,
  IN OUT SYS_LIST_POS *Pos,
  OUT VOID **Value
  )
{
  SYS_LIST_ENTRY *pe;

  if (!SysListIsValid (p)) {
    SYSINFO ("unable to get next element.\n");
    return FALSE;
  }

  if (Pos == NULL) {
    SYSINFO ("invalid list position. unable to get next element\n");
    return FALSE;
  }

  if (*Pos == NULL) {
    *Pos = (SYS_LIST_POS) p->Header.Next;
  }

  pe = (SYS_LIST_ENTRY *)(*Pos);
  if (pe->Next == &p->Header) {
    *Pos = NULL;
  } else {
   *Pos = (SYS_LIST_POS)(pe->Next);
  }

  if (*Pos == NULL) {
    *Value = NULL;
    return FALSE;
  }
  *Value = pe->Value;
  return TRUE;
}

HOW-TO: EFI_GUID vs. Registry GUID Format

Did you ever wonder how to translate a GUID in registry format (i.e. 7133e7ab-cc00-416a-84d3-2e84c583b14f) into an EFI_GUID structure initializer? Well, so did I, today. I'll give you the rule and then I'll teach you the simple way to remember:

Here is the original GUID format:

aabbccdd-eeff-gghh-iijj-kkllmmnnoopp
Here's the translated version:

EFI_GUID gXGuid = \
  {0xaabbccdd, 0xeeff, 0xgghh, \
  {0xii, 0xjj, 0xkk, 0xll, 0xmm, 0xnn, 0xoo, 0xpp}};
Or, if you forget, the uuidgen utility has an option -S which displays like this:

INTERFACENAME = { /* 7133e7ab-cc00-416a-84d3-2e84c583b14f */
    0x7133e7ab,
    0xcc00,
    0x416a,
    {0x84, 0xd3, 0x2e, 0x84, 0xc5, 0x83, 0xb1, 0x4f}
  };

The registry GUID format is in the /* */ comment.

Creating an Interactive Fiction Game in UEFI (Part 3: Playing the Game)

So I thought it might be a good idea to show a few screenshots of the game in progress.  Click the images to enlarge.

This is a shot of the game's beginning.  I didn't finish writing all the little details and such of the game, so right now, it just says "Intro Message" when you start it up.  That would normally be a long introduction of the game, describing the setting, the character, and your goal.  You can see here some examples of instructions and the results.  "Look" describes the room you're currently in.  But moving to a new room will also display the description.

The following pictures are just some more screenshots of moving through the game world and interacting with objects.

The game's still pretty rough, and I haven't implemented the key to win the game, so you can just wander endlessly around this world.  But I did include a way to quit the game.   It could use a few formatting fixes, and perhaps a more detailed end message, but it quits the game and gets back to the Shell.  I also left the original print messages from the basic Main application, so that's why they print those random welcome messages.

That's all! My next goal is to be able to display an image using EDKII

UEFI Application Programming: System Object Library (Part 1)

This article is the first in a series on writing UEFI applications. There are examples available on www.tianocore.org, but very little in terms of explaining what is going on. I tried to do a better job of this in the book that I co-wrote, Harnessing The UEFI Shell, where I took real, working programs and dissected them line-by-line. But that book suffered from working with an unfinished Shell 2.0 and I had to make a number of compromises and assumptions.

One of the key pieces of working in UEFI is having a base set of libraries that provide basic functionality. The EDK2 has done a good job of creating functions that give easy access to some UEFI features. And the StdLib is a fully-functioning version of the C standard library. And the Nt32Pkg provides a decent Windows-hosted UEFI environment that is really useful for debugging the applications.

My irritation is that I learned C++ before I learned C. So I grew used to having a set of container classes, whether MFC from Microsoft or the Standard Template Library (STL) that (now) comes with every C++ compiler. In C++, container classes like strings, lists, arrays, buffers/streams and maps/dictionaries manage collections of data structures, including all of the associated memory management.

But now I work with UEFI. UEFI is tied closely to C. The open-source implementations don’t support C++, including the necessary library to support to handle operators like new and delete. I like containers, and I have used them throughout my programming career.

So the first thing I did when it came to writing UEFI applications was to create a library to manage real containers. The library, called SysLib, was designed with a few goals in mind. And yes, I’ll publish the source code.

1)      Easily be converted to C++. This meant that the functions all used the pointer to the container as the first (‘this’) parameter. This allowed my C containers to be easily converted into C++ classes.

2)      Non-invasive. For many C container implementations, putting a data structure in the container requires the data structure be modified, usually with container’s book-keeping information. Then there is often weird pointer math to deduce the pointer to the beginning of the data structure from the pointer of that book-keeping data. An example of this is the EDK2’s LIST_ENTRY data structure from BaseLib.

3)      Constructor/Destructor. In C++, a class can provide a constructor, which initializes the class’ members to some default value. In C++, a class can also provide a destructor, which is responsible for releasing all resources allocated during the lifetime that object.

4)      Run-Time Type Information. In C++, run-time type information can be used to query whether an object is of a specific type. This allows the user to take advantage of specific capabilities of that object, including verifying that the pointer is a pointer to a valid container object.

5)      Debug Support. I wanted to be able to query any container to see if it was valid and to dump out the container’s contents.

6)      Virtual Functions. In C++, this is handled through a hidden data structure member that points to a table of pointers.  In UEFI, this has been simulated through (non-hidden) function pointers.

7)      Inheritance. All containers in this library derive from a common base class. It is possible to extend a class via a sort of “single-inheritance” by placing the data structure for a container at the beginning of a new container’s data structure and then pointing the virtual function pointer members to a new function. Since the C compiler doesn’t support inheritance, there is always some sort of type-casting involved (to get the parent type) but it works. Primitive, but effective.

8)      Light-Weight. Hey, let’s not take all of our valuable ROM resources or single-threaded UEFI computing time in making this work, ok?

Pretty nice list.  Now let’s look at some features that are not supported:

1)      Data hiding. This is C. So all structure members are available for inspection. Of course, you can always use the PIMPL idiom if data-hiding is important, but I don’t use it.

2)      Multiple Inheritance. I never used it in C++. When I first disassembled C++ code and looked at how it was really implemented, I started feeling queasy and decided I’d use aggregation instead.

SysObj

So the first step is to introduce you to SysObj, which is the parent of all of the container classes that I will introduce in future articles. This structure is designed to sit as the first member of a container class structure.

typedef struct _SYS_OBJ {

  UINT32 Signature;                     // object-specific signature.

  UINT32 Size;                          // size of object, in bytes.

  SYS_OBJ_INIT Init;                    // initialize new object.

  SYS_OBJ_EMPTY Empty;                  // free all allocated resources.

  SYS_OBJ_COPY Copy;                    // create copy at new location.

  SYS_OBJ_VALID IsValid;                // check object validity.

  SYS_OBJ_DUMP Dump;                    // debug dump of object contents.

} SYS_OBJ;

 
So, let’s walk through the data structure, piece-by-piece and then I’ll introduce you to the handy library functions and macros that make life easy.

·         Signature. The signature is a unique 32-bit integer that identifies the object type. Each of the classes that I will introduce later has a signature and uses that number of verify that the object pointer that is passed is of the correct type. This is primitive run-time type information. I considered using a pointer to a string, but I wanted the type verification to be low-overhead.

·         Size. The size of the object, in bytes. This includes the size of the SYS_OBJ structure. While not strictly necessary, it provides a convenient way to do pointer validation and the default implementation of Init() and Dump().

·         Init. A pointer to the virtual initialization function, which initializes a block of memory so to be a valid, empty object. All of the members of this structure must also be set. It does not consider what was in the memory already.

·         Empty. A pointer to the virtual empty function, which frees all resources allocated within the object, but not the object itself. The default version simply returns.

·         Copy. A pointer to the virtual copy function, which copies the contents of an object to a new memory location. The default version simply copies the entire object, byte-for-byte.

·         IsValid. A pointer to the virtual validity-checking function, which checks whether a pointer in fact points to a valid object. The default version just checks to see if the pointer is non-NULL and that Size is, at least, the size of the SYS_OBJ structure.  Most objects implement a version which uses the helper function SysObjIsValid(), which also checks the signature against a known value.

·         Dump. A pointer to the virtual debug-dump function, which prints out the contents of the object as text to the console. When I’m debugging, it is often useful to just dump out an object so I can see what it contained at a specific point in time. By providing this as a fundamental part of SysObj, I get, at least, some debug dump capabilities, because the default version, SysObjDump(), will print out the signature and a hex dump of the object’s contents. More advanced versions can add more details.

SysObj Macros
Now, let’s take a look at some of the useful macros that automate using some of the typical uses of objects:

·         SysInit(type, ptr). Initialize a previously allocated block of memory (ptr) as an empty object of type type. This macro is used, for example, to initialize global or local (stack) objects. Since there is no way to automatically invoke a “constructor” in C when an object is declared, we have to do it manually. And this is the macro that does it.

·         SysInitWith(ptr1, ptr2). Initialize a previously allocated block (ptr1) with the contents of another object (ptr2).

·         SysNew(type). Return a pointer to a newly allocated object of type type, or NULL if initialization failed or memory could not be allocated.

·         SysDelete(ptr). Free all resources associated with the object (ptr) and free the object. This is used with objects which were allocated with SysNew. Global or local objects initialized with SysInit should use SysEmpty instead.

·         SysEmpty(ptr). Free all resources associated with the object (ptr) and make it appear “empty” but do not free the object. This is used with objects which were initialized with SysInit().

·         SysCopy(ptr1,ptr2). Copy the contents of object ptr2 into object ptr1. This uses the virtual Copy function.

·         SysDup(ptr).Return a pointer to a newly allocated copy of object ptr.

·         SysIsValid(ptr). Return whether the object ptr is a valid object.

·         SysDump(ptr). Dump the contents of the object ptr to the console.

·         SysDebugDump(ptr). Dump the contents of the object ptr to the console if library debugging is enabled. The global flag (SYSLIB_DEBUG) controls whether library debugging is enabled. I haven’t updated this to use EDK2’s PCDs yet. Yes, it is on my todo list.

SysObj Functions

This section walks through key support functions provided by the library for new objects:

SysObjInit

This function is used by Init() virtual member functions to set up the SysObj members to correct values. It also performs some basis error checking. Two important notes: the SYS_INFO is a debug macro used for informational output. It can be separately turned on or off. Also, four of the virtual functions can be NULL, wherein they will provide a default function which assumes no allocated resources and byte-by-byte copy.

SYS_OBJ *
SysObjInit (
  OUT SYS_OBJ *Obj,
  IN UINT32 Signature,
  IN UINT32 Size,
  IN SYS_OBJ_INIT Init,
  IN SYS_OBJ_EMPTY Empty OPTIONAL,
  IN SYS_OBJ_COPY Copy OPTIONAL,
  IN SYS_OBJ_VALID IsValid OPTIONAL,
  IN SYS_OBJ_DUMP Dump OPTIONAL
  )
{
  if (Obj == NULL) {
    SYSINFO ("invalid object pointer. pointer is NULL.\n");
    return NULL;
  }

  if (Init == NULL) {

    SYSINFO ("invalid object Init function pointer.\n");
    return NULL;
  }

  if (Size < sizeof (SYS_OBJ)) {

    SYSINFO ("invalid object size. must be at least %d bytes (%d specified).\n", \
      sizeof (SYS_OBJ), Size);
    return NULL;
  }

  Obj->Signature = Signature;

  Obj->Size = Size;
  Obj->Init = Init;
  Obj->Empty = (Empty == NULL) ? SysObjEmptyDummy : Empty;
  Obj->Copy = (Copy == NULL) ? SysObjCopy : Copy;
  Obj->IsValid = (IsValid == NULL) ? SysObjIsValidDummy : IsValid;
  Obj->Dump = (Dump == NULL) ? SysObjDump : Dump;
  return Obj;
}

SysObjDump

This is the default version of the Dump() virtual member function, which prints out the signature and then a hex dump of any object data.

VOID

SysObjDump (IN CONST SYS_OBJ *p)
{
  UINT32 i;
  UINT8 *b;
 
  if (!p->IsValid (p)) {
    printf ("invalid object pointer.\n");
  }
  printf ("Object: %c%c%c%c\n",
    (char) (p->Signature & 0xff),
    (char) ((p->Signature & 0xff00) >> 8),
    (char) ((p->Signature & 0xff0000) >> 16),
    (char) ((p->Signature & 0xff000000) >> 24));
  printf ("Size  : %d bytes\n", p->Size);
 
  b = (UINT8 *) (p + 1);                // points just after end of SYS_OBJ structure.
  for (i = 0; i < p->Size - sizeof (SYS_OBJ); i++) {
    printf ("0x%02x ", b[i]);
    if (i % 16 == 15) {
      printf ("\n");
    }
  }
}

SysObjIsValid

This is a helper function that can be used by objects to implement the IsValid() member functions. It verifies that there is a valid pointer, that the size is at least the minimum size and that the signature matches.

BOOLEAN

SysObjIsValid (
  IN CONST SYS_OBJ *Obj,
  IN UINT32 Signature,
  IN UINT32 Size
  )
{
  if (Obj == NULL) {
    SYSINFO ("invalid object pointer. pointer is NULL.\n");
    return FALSE;
  }
 
  if (Obj->Size < sizeof (SYS_OBJ) || Obj->Size != Size) {
    SYSINFO ("invalid object pointer. invalid object size. must be %d bytes \
     (%d found).\n", Size, Obj->Size);
    return FALSE;
  }
 
  if (Obj->Signature != Signature) {
    SYSINFO ("invalid object pointer. invalid signature.\n");
    return FALSE;
  }
 
  return TRUE;
} 

SysObjCopy

This is the default version of the Copy() member function, which performs a simple byte-by-byte copy.

SYS_OBJ *

SysObjCopy (
  OUT SYS_OBJ *ObjDest,
  IN CONST SYS_OBJ *ObjSrc
  )
{
  return (SYS_OBJ *) memcpy (ObjDest, ObjSrc, ObjDest->Size);
}

Conclusion

Some of you are probably wondering what this has to do with UEFI. Good question. In fact, these libraries could work just as well under Windows, because they only depend on the C library. But I have packaged them for EDK2 build and they are the building blocks for more serious UEFI applications to come, including some fun HII code.

In the next article, we’ll look at a few actual container classes built on top of SysObj, including SysList, a basic double-linked list container and then SysOList, which extends this to manage (“own”) the objects in the list.

P.S. Some of you sharp-eyed readers will note that I said, “allowed my C++ containers” implying that I had done the work to make a C++ wrapper. Well, I have, but it involved a few hacks to EDK2, including the build tools and libraries. If I have time, I’ll try and point out how I did it.

The Nitty-Gritty EDK2 Library Details

Most of you can stop reading now, since most of what follows gives the low-level details of how I got this to build in EDK2. Don’t worry, you won’t miss anything, since I’ll show it all later, but I thought I’d give a quick tour.

SysLib.dec

The whole library is in a package called SysLib. Every package in EDK2 needs a .DEC file. This one is about as simple as it gets.

[Defines]

  DEC_SPECIFICATION              = 0x00010005
  PACKAGE_NAME                   = SysLib
  PACKAGE_GUID                   = 1842ace0-5d82-11e1-b86c-0800200c9a66
  PACKAGE_VERSION                = 0.01

[Includes]
  Include

SysLib.inf

Here’s the actual INF file used to build the library.

[defines]

  INF_VERSION                    = 0x00010005
  BASE_NAME                      = SysLib
  FILE_GUID                      = 4847bcc0-5d85-11e1-b86c-0800200c9a66
  MODULE_TYPE                    = UEFI_APPLICATION
  VERSION_STRING                 = 1.0
  LIBRARY_CLASS                  = SysLib
 
#
#  VALID_ARCHITECTURES           = IA32 X64 IPF
#
 
[LibraryClasses]
  LibC
  DebugLib
  PrintLib
 
[Packages]
  MdePkg/MdePkg.dec
  StdLib/StdLib.dec
  SysLib/SysLib.dec
 
[Sources]
  SysLib.c
  Debug.c
  CLibSupplement.c
  Uefi.c 

Nt32Pkg.dsc

This is the master DSC file for building the Windows-hosted UEFI environment. Most of this is pretty standard: add the library class (SysLib) to the [LibraryClasses] section.

  SysLib|SysLib/Source/SysLib.inf

 
But when writing a new library which both works with Nt32 and uses the StdLib, you have to tell the EDK2 build environment to ignore the standard Visual Studio build paths, as follows (in the [Components] section) using the /X command-line option.

  SysLib/Source/SysLib.inf {

   
      MSFT:*_*_*_CC_FLAGS    = /X /Zc:wchar_t /GL-
  }