Feedback Search Top Backward Forward
EDM/2

An OS/2 Allocator for the STL

An Allocator Class For The C++ Standard Template Library That Uses The OS/2 API Memory Functions

Written by Vincent Patrick LaBella

Linkbar

 

Abstract

Have you ever wondered how the allocators in the C++ Standard Template Library (STL) work? Have you ever wanted to write your own allocator class? Did you even know you could? This article explores the answers to these questions by examining the workings of allocators in the STL and developing a new allocator class, os2_allocator, for the STL which uses the OS/2 memory management functions, DosAllocMem() and DosFreeMem(). This allocator class can be useful to programmers who like to use the OS/2 API for memory allocation and still want to use the STL. Also, it is necessary when using STL containers inside threads created with DosCreateThread(), where one shouldn't use the standard library calls new() and delete() as the standard allocator (stdalloc.h) does. The method presented here can be used to develop allocators for other operating system's API or memory models.

Introduction

The Standard Template Library (STL) provides the C++ programmer with many useful type independent generic containers, such as vectors, linked-lists and queues. If you are a C++ programmer and have not discovered the STL, I highly recommend learning how to use it. Once you have used STL, you will never want to code without it. There are two reasons why the STL container classes are so attractive. The first is that they are type independent. This means you can create vectors of chars, ints, doubles or any other user defined class or type. Secondly, the container classes are independent of the memory model. This keeps the code portable across the numerous memory models found on the various operating systems in use today.

The way the authors of the STL kept the code memory model-independent was through the use of allocators. Simply put, an allocator class is a template class that allocates and de-allocates storage for the container classes. The default allocator, contained in defalloc.h, uses new() and delete() to allocate and de-allocate memory from the free store. The design is flexible enough to incorporate any memory allocation functions to allocate and de-allocate memory. In this article I will describe how to write and use a allocator class, called os2_allocator, for the STL that uses the OS/2 memory allocation functions DosAllocMem() and DosFreeMem().

Allocator Design

To write a new allocator it is necessary to understand how the allocator works in the STL. Each STL container class declares an allocator class as a private member. The container uses this class to allocate and de-allocate memory, and construct and destroy the members of the container class. The standard distribution of the STL comes with several allocators. The default allocator, contained in defalloc.h, uses new and delete to allocate and de-allocate memory from the free store. Other allocators include: faralloc.h, neralloc.h, lngalloc.h, and hugalloc.h.

Each allocator works by separating the tasks of object construction and memory allocation and likewise, object destruction and memory de-allocation for the objects of the container classes. They do this by providing 4 global functions allocate(), construct(), deallocate(), and destroy(), which are shown below. 


  //code fragment from "defalloc.h":

  template <class T>
  inline T* allocate(long size, T*) {
      set_new_handler(0);
    T* tmp = (T*)(::operator new((unsigned long)(size * sizeof(T))));
      if (tmp == 0) {
          cerr << "out of memory" << endl;
          exit(1);
      }
      return tmp;
  }

  template <class T1, class T2>
  inline void construct( T1* p, const T2& value) {
      new (p) T1(value);
  }

  template <class T>
  inline void deallocate(T* buffer) {
      ::operator delete(buffer);
  }

  template <class T>
  inline void destroy(T* pointer) {
      pointer->~T();
  }
Separating the de-allocation and destruction processes is easily accomplished since it is okay to explicitly call the destructor as seen in the function destroy(). To de-allocate memory the allocator uses deallocate() which contains a delete() call. This type of delete call with the parenthesis is similar to the standard C function free() except that delete() is used for memory allocated with new() (i.e. free store memory). The ::operator command instructs the compiler to call the global delete function, in case it has been overloaded by the class in the container. To destroy the object, the global function destroy() is provided which simply calls the destructor.

Separating object construction and memory allocation is a little bit trickier, since ANSI C++ forbids the programmer from explicitly calling the constructor, but it is not impossible. This is done using what is called the new placement syntax. To understand how the allocator uses the new expression let's look at several different ways the new operator can be used. 


  // standard way, allocates memory and calls constructor
  FOO* foo1;
  FOO* foo2;
  foo1 = new FOO();

  // allocate memory from free store only. Does NOT call constructor
  void *p;
  p = new(sizeof(FOO));

  // call constructor only, but we need a pointer to available memory
  // use placement new syntax
  foo2 = new (p) FOO(); // construct object foo2 at location p
It is the last two methods that the allocator class uses when separating construction and allocation in the functions construct() and allocate(). In the function allocate(long size, T*) the call to new is shown below. 

    T* tmp = (T*)(::operator new((unsigned long)(size * sizeof(T))));
The ::operator command before the new() command tells the compiler to call the global default new function. This is done in case you have overloaded the new operator in your class. The new(size * sizeof(T)) function allocates enough memory for size elements of type T from the free store. This free store memory is then returned by new and stored in the pointer tmp. Note, the new(size_t) function does not call the constructor. To construct the object the allocator uses the function construct() which uses the new placement syntax. 

    new (p) T1(value);
This line of code constructs object T1 in object p by applying T1's default copy constructor with the object value. To put it another way T1's constructor is called and the object is put in the memory location p. The difference between these two uses of the new function is the key to understanding how the STL authors separated memory allocation and object construction.

OS/2 Allocator Design and Usage

Once it is understood how the STL allocators work, it is simple to write an allocator that uses any memory allocation and de-allocation routine. To write an allocator that uses the OS/2 APIs calls, simply change the new() and delete() calls in the allocate() and deallocate() functions to use the DosAllocMem() and DosFreeMem() APIs. The modified code is shown below. 


  template <class T>
  inline T* allocate(long size, T*) {
      set_new_handler(0);
      T* tmp;
      DosAllocMem((void**)&tmp, size * sizeof(T),
                  OS2_ALLOC_MEM_FLAGS); if (tmp == 0) {
           cerr << "out of memory" << endl;
           exit(1);
      }
      return tmp;
  }

  template <class T>
  inline void deallocate(T* buffer) {
      DosFreeMem((void*) buffer);
  }
In this listing the new() call is replaced by DosAllocMem() and the delete() call is replaced with DosFreeMem() along with the appropriate casts to void pointers.

There are two other functions that need to be modified when using a different memory model in an allocator class. They are init_page_size() and max_size(). The first of these functions returns the number of elements of type T that can fit into one page of the memory model in use. STL comes with the page size 4096 hard coded into default allocator. OS/2's page size is the same 4KB, so there is no change needed here. A macro was defined at the top of the source for clarity. The max_size() returns the maximum number of objects of type T that a container can have for the current memory model. The default allocator uses UINT_MAX as the maximum amount of memory the operating system can access. UINT_MAX is defined in limits.h as 0xffffffffU which is 4GB. Again, OS/2's maximum memory size is the same 4GB, but a macro was added for clarity. The entire os2_allocator class listing is at the end of this article.

Using the OS/2 allocator is straight forward. Simply specify os2_allocator as the allocator of choice when initializing your container. For example. 


  #define INCL_DOS
  #include<os2.h>
  #include<os2alloc.h>
  #include<vector.h>
  ...
  vector<double> std_foo;                // uses the default allocator
  vector<double,os2_allocator> os2_foo;  // uses the OS/2 allocator
This last line, vector<double,os2_allocator> os2_foo;, is not supported by todays compilers. The existing generation of C++ compilers do not support default template arguments that are templates themselves. Until they are up to date we have to use the work-around that exists in the STL today. Each container uses the preprocessor to define the word Allocator which is used in the class definition. If Allocator is undefined then the default is used. This is done with the following code in the beginning of all the container class files. 

  #ifndef Allocator
  #define Allocator allocator
  #include <defalloc.h>
  #endif
To use the os2_allocator simply define the Allocator word before the container class does. For example: 

  #include<os2alloc.h>
  #define Allocator os2_allocator
  #include<vector.h>
  ...
  vector<double> os2_foo;  // uses the OS/2 Allocator
However, this work-around causes every container in the source file to use the os2_allocator. This is one of the unfortunate side effects but it is not catastrophic and soon will be fixed with the new generation of compilers arrives.

If you want to use two different kinds of containers with the OS/2 Allocator you must redefine the Allocator word before the include statement of each container. For example: 


  #include<os2alloc.h>
  #define Allocator os2_allocator
  #include<vector.h>
  // redefine it
  #define Allocator os2_allocator
  #include<list.h>
  ...
  vector<double>  os2_vector; // uses the OS/2 Allocator
  list<double>  os2_list; // uses the OS/2 Allocator
This is needed since every container class has a #undef Allocator line at the end of it.

Future and Further Reading

This article only skims the surface of the workings of allocators in the STL. For a more detailed discussion of the STL and allocators see C++ Programmer's Guide To The Standard Template Library by Mark Nelson (IDG Books). For an excellent series of articles on the intricacies of using new and delete see Dan Sacks' Columns in C/C++ User's Journal, Volume 15, Issues 1--7, (1997). Also, The OS/2 allocator presented here may be able to be expanded to include more features of the OS/2 API memory management functions, such as shared memory and/or memory sub-allocation. It may be worthwhile to write allocator classes that support these two memory constructs. Also, the use of OS/2's APIs for error detection and exception handling may be added as well. This method can easily be adapted for use in other operating system's memory models.

Conclusions

The design and use of the allocator in the STL containers keeps the container classes very flexible when it comes to memory model use. The os2_allocator presented in this article is an interesting and instructional extension of the OS/2 API to the STL API and, makes the STL containers able to be used in threads created with DosCreateThread(). In addition, when using the STL the programmer keeps the code memory model independent. To change models, just use a different allocator. One word of caution: This allocator allows for the possibility that a class within a container can use new() to allocate its own internal memory while the memory for the class itself was allocated using DosAllocMem(). This may cause problems and the programmer should be aware of this.

One other caution on the use of the STL in threads: Before this writing, the standard allocator (stdalloc.h) allowed STL containers to be used in threads created with _beginthread() only, not DosCreatThread(). This new OS/2 allocator makes it possible to use the STL containers in threads created with the OS/2 API DosCreateThread(). However, neither of these allocators make it possible to safely share STL containers amongst multiple threads. Eberhard Mattes has informed me that he has a fix for this latter problem in his release of emx0.9c (fix 3) in /emx/src/lib/io/_fd.c and _fdinit.c. Other than that, this allocator class may prove to be very useful. Grab the following code, save it in your include path and enjoy.

Code Listing: os2alloc.h

 

Linkbar