2.4.9.2 The software allocator

The SwAllocator is a BKAllocator with a simple allocation scheme. Its implementation may vary, but in general it consists on an array and a linked list of free nodes. We call it ``software'' allocator because its allocation table is not used by the hardware (other system allocators use machine dependent data structures needed by the hardware to maintain the allocation table). Again, we provide first a void pointer based allocator which can be further wrapped by a type-safe interface.

<Off software allocator. >= (U->)

// A software-table based allocator.
//
class off_SwAllocator : public off_KernAllocator {
private:
  <Other private members of off_SwAllocator. >
protected:
  <Other protected members of off_SwAllocator. >
public:
  // Allows declarations of uninitialized software allocators.
  off_SwAllocator(void){;}

  // Creates a software allocator.
  off_SwAllocator(off_Exhausted *r, const off_Indexable *i, 
                  void *first, natural_t len         ) : 
    off_KernAllocator(r,i,first,len),
    <Initialize other aggregate members of off_SwAllocator. >
  { ;  }

  // Allocate (deallocate) units. 
  // Return NULL when allocation failed. 
  void *allocate(boolean_t use_revocation=FALSE );
  void *allocate(natural_t at, boolean_t use_revocation=FALSE);

  void  deallocate(void *p);

  <Other public methods of off_SwAllocator. >
};

Defines off_SwAllocator (links are to index).

<Off software allocator dependencies. >= (U->) [D->]
#include <flux/types.h>         // for boolean_t natural_t et al.
#include <klib/KernAllocator.h> // for off_KernAllocator
#include <klib/Indexer.h>       // for off_Indexable

Objects are allocated from the raw store (k_items) left to right. Initially, all the nodes in the array will be available; during system operation the array will have allocated nodes on the left section and available nodes on the right section. A pointer to the start of the unallocated section, s_next, is used to distinguish between those sections. A free list is used to reuse nodes that are no longer useful. Nodes of the store must match the type DLinkedNode, so that they could be linked without using dynamic memory.

<Other protected members of off_SwAllocator. >= (<-U)
void *s_next;                   // first unallocated element in the arry.

<Off software allocator dependencies. >+= (U->) [<-D->]
#include <klib/dlist.h>         // for DLinkedNode et al.

The free list is a single linked list which does not allocate memory for its nodes (a DLinkedList). Instead, it uses another raw allocator to maintain the list.

<Other private members of off_SwAllocator. >= (<-U)
DLinkedList s_free;             // list of free nodes.

We still have to initialize the new members defined above.

<Initialize other aggregate members of off_SwAllocator. >= (<-U)
s_free(),s_next(k_first)

<Off software allocator dependencies. >+= (U->) [<-D->]
#include <assert.h>             // for assert

Allocation is simple, provided there is enough memory. We first try the free list. If it is exhausted we will take the memory from the unallocated part of the array. Be no free node available, we must trigger revocation.

<off_SwAllocator::allocate implementation. >= (U->) [D->]
// Allocates units.
// Returns NULL when allocation fails.
void *off_SwAllocator::allocate(boolean_t use_revocation)
{
  assert(ptr_valid(s_next));
  if (!get_nfree())
    if (use_revocation)
      exhausted();
    else
      return NULL;
  assert(ptr_valid(s_next));
  if (!s_free.is_empty()){
    off_BKAllocator::allocate();
    assert(ptr_valid(s_next));
    return (void*)s_free.unlink_head();
  }
  else {
    void *nd=s_next; 
    k_idx->inc(s_next);
    off_BKAllocator::allocate();
    assert(ptr_valid(s_next));
    return nd;
  }
}

To allocate an element at a given position we must check the given index for validity. When the node is present in the unallocated part of the array we move previous unallocated nodes into the free list and mark the node as allocated. Otherwise it can be allocated only when it is found in the free list.

<off_SwAllocator::allocate implementation. >+= (U->) [<-D]
// Allocates units.
// Returns NULL when allocation fails.
void *off_SwAllocator::allocate(natural_t at, 
                                boolean_t use_revocation)
{
  DLinkedNode *n=(DLinkedNode*)(k_idx->add(k_first,at));
  
  assert(n && ptr_valid(s_next));

  if (!ptr_valid(n))
    return NULL;
  else {
    if (s_next<=(void*)n){
      for( ;s_next<(void*)n; k_idx->inc(s_next))
        s_free.link_first((DLinkedNode*)s_next);
      k_idx->inc(s_next);
      off_BKAllocator::allocate();
      assert(ptr_valid(s_next));
      return (void*)n;
    }
    else if (s_free.is_linked(n)){
      s_free.unlink(n);
      off_BKAllocator::allocate();
      assert(ptr_valid(s_next));
      return (void*)n;
    }
    else
      return NULL;
  }
}

We have used is_free. We export this method as a convenience for users.

<Other public methods of off_SwAllocator. >= (<-U) [D->]
// Is it free?
boolean_t is_free(natural_t at) const { 
  void *p=k_idx->add(k_first,at);
  assert(ptr_valid(p));
  return s_free.is_linked((DLinkedNode*)p) || p >= s_next;  }

Deallocation is the most simple method.

<off_SwAllocator::deallocate implementation. >= (U->)
// Dellocates units.
void off_SwAllocator::deallocate( void *p)
{
  assert(p && ptr_valid(s_next) && ptr_valid(p));
  off_BKAllocator::deallocate();
  s_free.link_first((DLinkedNode*)p);
}

Users should not instantiate this allocator, that is why we are not going to implement type-safe wrappers for it.

Now that we have a complete allocator with a software-based machine independent allocation table, we must provide two kinds of allocator: a fixed-size static allocator and a growing dynamic allocator.