2.7 Resource unit availability: Relocation tables

A relocation table is responsible for talking (i.e. upcalling) to the user and ask for local copies of remote resources. Synchronization is taken into account by relocation tables, so it can be ignored by relocation table users.

<Off relocation table. >= (U->)
// A relocation table. It is used to bring resources to the local node
// with the help of system users. 
class off_RelocTbl : public off_Lockable {
private:
  <Other private members of off_RelocTbl. >
public:
  <Other public members of off_RelocTbl. >
  <Other public methods of off_RelocTbl. >
};

Defines off_RelocTbl (links are to index).

<Off relocation table dependencies. >= (U->) [D->]
#include <klib/ids.h>           // for off_prtl_id_t et al.
#include <klib/err.h>           // for err_t and error numbers.
#include <klib/Magic.h>         // for off_Magic

A RelocTbl implement two important methods: is_relocated and missing. The missing method (which is usually invoked from make_available) delivers a MISSING exception and request for a particular resource unit to be made available.

<Other public methods of off_RelocTbl. >= (<-U) [D->]
// Looks up for resource id and updates the given id to reflect
// the actual (local) location or returns FALSE to state that the
// resource is not being cached. 
// If reference is TRUE, a new reference is counted for the given
// resource relocation.
boolean_t is_relocated(off_id_t &id, boolean_t reference=FALSE);

// Talks to the user at ex to fetch ID which is missing.
// Returns 0 when resource has been made available (error code otherwise).
err_t missing(const off_prtl_id_t &ex, 
              const off_Magic id_type,off_id_t &id);

// Establishes a new relocation and counts a reference to it.
err_t relocate(const off_id_t &lcl, const off_id_t &rem);

// Releases an existing relocation (actually, discounts a reference to it). 
void unrelocate(const off_id_t &rem);

<Off relocation table dependencies. >+= (U->) [<-D->]
#include <flux/types.h>         // for boolean_t natural_t et al.
#include <klib/ids.h>           // for off_eu_id_t et al. 
#include <klib/err.h>           // for err_t and error numbers.
#include <klib/RelocTbl.h>      // for off_RelocTbl. 
#include <klib/Magic.h>     // for off_Magic

\subsection{Relocation hash tables} The relocation table maintains a table of translations for resource units being cached. It uses a block allocator to keep its relocation entries and a hash table to do efficient lookups.

<Other private members of off_RelocTbl. >= (<-U) [D->]
static off_TBlockAllocator<off_RelocTblEnt> r_alloc; // Entry allocator.
static DHashTbl<off_RelocTblEnt,off_RelocTblHasher,off_id_t,OFF_RLC_NENTS> 
   r_hash;                                          // Hash table. 

<Off relocation table static members. >= (U->) [D->]
// Entry allocator.
off_TBlockAllocator<off_RelocTblEnt> off_RelocTbl::r_alloc; 
// Hash table. 
DHashTbl<off_RelocTblEnt,off_RelocTblHasher,off_id_t,OFF_RLC_NENTS> 
   off_RelocTbl::r_hash;

<Off relocation table dependencies. >+= (U->) [<-D->]
#include <klib/BlockAllocator.h> // for off_BlockAllocator
#include <klib/dhash.h>          // for DHashTbl

To create a relocation table, the creator might supply the information needed to instantiate a block allocator (the hash table uses it).

<Other public members of off_RelocTbl. >= (<-U)
// Creates a new RelocTbl
off_RelocTbl(void);

However, the block allocator is not created at relocation table instantiation time, we simply keep that information needed to create it.

<off_RelocTbl::off_RelocTbl implementation. >= (U->)
// Creates a new RelocTbl
off_RelocTbl::off_RelocTbl(void) 
{ 
  r_revocator = (off_Exhausted*)this;
}

<Other private members of off_RelocTbl. >+= (<-U) [<-D->]
static off_Exhausted *r_revocator;

<Off relocation table static members. >+= (U->) [<-D->]
off_Exhausted *off_RelocTbl::r_revocator;

Instead, the allocator is created when the relocation table is explicitly started by means of start.

<Other public methods of off_RelocTbl. >+= (<-U) [<-D->]
// Starts relocation table operation.
static err_t start(off_KVMRegion *reg);

<Off relocation table dependencies. >+= (U->) [<-D->]
#include <dmm/KVMRegion.h>

What we do is to use a special new operator defined for block allocators which permits initialization of pre-allocated block allocators.

<off_RelocTbl::start implementation. >= (U->)
// Starts a new RelocTbl
err_t off_RelocTbl::start(off_KVMRegion *reg) 
{
  off_TBlockAllocator<off_RelocTblEnt>  *alloc;
  
  alloc= new((void*)&r_alloc) 
            off_TBlockAllocator<off_RelocTblEnt>(r_revocator,
                                                 (const off_Indexable*)&r_idx,
                                                 reg);
  assert(reg && alloc);
  return (alloc) ? EOK : ENOMEM;
}

Where r_idx is an indexer for relocation table entries.

<Other private members of off_RelocTbl. >+= (<-U) [<-D->]
static off_Indexer<off_RelocTblEnt> r_idx;

<Off relocation table static members. >+= (U->) [<-D]
off_Indexer<off_RelocTblEnt> off_RelocTbl::r_idx;

As we see (to pass the this parameter), relocation tables must implement the revocation interface.

<Other public methods of off_RelocTbl. >+= (<-U) [<-D]
virtual void notify(void) { ;}

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

The hash table uses a RelocTblHasher implementing the hash function responsible for hashing off_id_t elements.

<Off relocation table hasher. >= (U->)
// A hasher for off_id_t's
// Hashs into  set [0,OFF_RLC_NENTS-1]
//
class off_RelocTblHasher {
public:
  natural_t hash(const off_id_t &key) {
     return (key.i_offset ^ key.i_seq ^ key.i_node)
            % OFF_RLC_NENTS;
  }
  
  boolean_t match(off_RelocTblEnt *nd, const off_id_t &key) {
    return nd->r_remote == key;
  }

};

Defines off_RelocTblHasher (links are to index).

The size of the hash table is a system defined limit.

<Off limits. >= [D->]
const int OFF_RLC_NENTS = 255;  // size of the hash in HW relocation tables.  

Defines OFF_HWR_NENTS (links are to index).

<Off relocation table dependencies. >+= (U->) [<-D]
#include <klib/limits.h>        // for OFF_HWR_NENTS

Entries contain translations from remote to local identifiers and are reference counted. They must inherit from DLinkedNode to be in the relocation table allocator.

<Off relocation table entry. >= (U->)
// A relocation table entry.
class off_RelocTblEnt : public DLinkedNode {
private:
  <Off private members for reference counting objects. >
public:
  off_id_t r_remote;         // remote resource being chached.
  off_id_t r_local;          // local resource used as a cache. 

  // Creates are relocation table entry.
  off_RelocTblEnt(const off_id_t &rem=OFF_ID_NULL, 
                  const off_id_t &lcl=OFF_ID_NULL) :
    r_remote(rem),
    r_local(lcl)
  {
    <Off initialization for reference counting objects. >
  }

  <Off public methods for reference counting objects. >  
  <Other public methods of off_RelocTblEnt. >

};

Defines off_RelocTblEnt (links are to index).

Remember that RelocTblEnts are used in hash tables. Therefore, they must implement the get_key method.

<Other public methods of off_RelocTblEnt. >= (<-U) [D->]
off_id_t get_key(void) const { return r_remote; }

We are now in position to implement the is_relocated method by means of the hash table.

<off_RelocTbl::is_relocated implementation. >= (U->)
// Looks up for resource id and updates the given id to reflect
// the actual (local) location or returns FALSE to state that the
// resource is not being cached. 
// If reference is TRUE, a new reference is counted for the given
// resource relocation.
boolean_t off_RelocTbl::is_relocated(off_id_t &id,
                                     boolean_t reference)
{
   off_RelocTblEnt *el;
   r_lock();
   el=r_hash.lookup(id);
   r_unlock();
   if (el==NULL)
     return FALSE;
   else {
     id=el->r_local;
     if (reference)
       el->reference();
     return TRUE;
   }
}

A new relocation is just a new entry added to the hash table.

<off_RelocTbl::relocate implementation. >= (U->)
// Establishes a new relocation (perhaps replacing an old one).
err_t off_RelocTbl::relocate(const off_id_t &lcl, const off_id_t &rem)
{
   boolean_t res=TRUE;
   off_RelocTblEnt *ent;
   w_lock();
   ent= new off_RelocTblEnt;
   if (ent){
     ent->r_remote=rem;
     ent->r_local=lcl;
     ent->reference();
     r_hash.insert(ent);
   }
   w_unlock();
   return (ent&&res)?EOK:ENOMEM; 
}

<off_RelocTbl::unrelocate implementation. >= (U->)
// Releases an existing relocation (actually, discounts a reference to it). 
void off_RelocTbl::unrelocate(const off_id_t &rem) 
{
   off_RelocTblEnt *ent;
   w_lock();
   ent= r_hash.lookup(rem);
   if (ent){
      ent->unreference();
   }
   w_unlock();
}

Note how unreference could call unused on the RelocTblEnt.

<Other public methods of off_RelocTblEnt. >+= (<-U) [<-D->]
void unused(void)
{
  delete this;
}

We used new and delete. They are defined using the relocation table allocation facilities.

<Other public methods of off_RelocTblEnt. >+= (<-U) [<-D]
// Allocates a new entry.
static void * operator new(const size_t size);
static void operator delete(void *item);

<off_RelocTblEnt::new/delete implementation. >= (U->)
void * off_RelocTblEnt::operator new(const size_t size)
{
  (void)size;
  return (void*) off_RelocTbl::r_alloc.allocate();
}

void off_RelocTblEnt::operator delete(void *item)
{
  assert(item);
  off_RelocTbl::r_alloc.deallocate((off_RelocTblEnt*)item);
}

To access r_alloc, we must be declared friends.

<Other private members of off_RelocTbl. >+= (<-U) [<-D]
friend void *off_RelocTblEnt::operator new(const size_t size);
friend void off_RelocTblEnt::operator delete(void *item);