2.3.3.2 Kernel bureaucracy

In order to wait for a resource to reach a given state, or to do long-term waiting due to resources being temporarily unavailable, we use Bureaucrats. Each resource that may cause long-term waiting (abstract resources) will provide one or more Bureaucrats so that shuttles block on them until some new state is reached. Bureaucrats can be understood as condition variables but can be implemented by other means.

The use of condition variables is not an obstacle to system distribution because we will be using lists of identifiers (and not lists of objects) to represent the set of shuttles waiting on condition variables. Thus a single list may span several nodes.

<Off bureaucrat. >= (U->)
// Bureaucracy shuttles sleep in. 
//
class off_Bureaucrat {
private:
  <Other private members of off_Bureaucrat. >
public:
  // Puts 'who' to sleep on this bureaucrat.
  err_t wait(const off_shtl_id_t &who);
  // Signals this condition. Just one will be awaken. 
  // Returns FALSE if not every shuttle has been awaken.  
  boolean_t signal(off_shtl_id_t &who = OFF_SHTL_NULL);

  <Other public methods of off_Bureaucrat. >
};

Defines off_Bureaucrat (links are to index).

To implement a Bureaucrat we must maintain a list of blocked shuttles. We use pools of shuttle identifiers to store the list. On bureaucrat creation time a pool must be supplied. The list of shuttle identifiers will be kept in that pool. Bureaucrats do not include locks, thus they use the locks of the objects they are contained in (Note that the pool must synchronize access, using its own locking facilities, because multiple bureaucrats could be accessing it at the same time).

<Other public methods of off_Bureaucrat. >= (<-U)
// Creates a Bureaucrat.
off_Bureaucrat(off_TBlockAllocator<off_LinkedId> *id_pool);
// Destroyes a Bureaucrat
virtual ~off_Bureaucrat(void);

Bureaucrats include a dynamic queue of identifiers (IdQueue) that allocates its nodes using an allocator of queue nodes (which is in turn a specific kind of block allocator, BlockAllocator; see section  for details.).

<Off bureaucrat node. >= (U->)
class off_LinkedId : public DLinkedNode {
public:
  off_id_t l_id;
};

<Other private members of off_Bureaucrat. >= (<-U) [D->]
off_TBlockAllocator<off_LinkedId> *b_alloc; // Queue nodes
DLinkedQueue                       b_shtls; // Queue of shuttle identifiers.

<off_Bureaucrat::off_Bureaucrat implementation. >= (U->)
// Creates a Bureaucrat.
off_Bureaucrat::off_Bureaucrat(off_TBlockAllocator<off_LinkedId> *id_pool) :
  b_alloc(id_pool),
  b_shtls()
{
  assert(id_pool);
  b_nwait=0;
}

We also maintain a count of shuttles waiting on this bureaucrat.

<Other private members of off_Bureaucrat. >+= (<-U) [<-D]
natural_t   b_nwait;          // # of shuttles waiting. 

A bureaucrat will assume that the lock on the object is already held when wait or signal is called. Besides, the shuttle is not really blocked by the bureaucrat, the object calling to the bureaucrat should prevent the shuttle from being run and release the lock on the object.

<off_Bureaucrat::wait implementation. >= (U->)
// Puts WHO in the bureaucrat wait queue. 
// Container object must be locked. 
// Does not block WHO. 
err_t off_Bureaucrat::wait(const off_shtl_id_t &who)
{
   off_LinkedId *i = (off_LinkedId*)b_alloc->allocate();
   if (!i)
     return ENOMEM;
   b_nwait++;
   i->l_id=who;
   b_shtls.enqueue(i);
   return EOK;
}

The implementation of signal will unblock the signaled shuttle (if any), the caller is only responsible of holding the lock during the call to signal.

<off_Bureaucrat::signal implementation. >= (U->)
// Awakes WHO from the Bureaucrat wait queue, if any. 
// Container object must be locked. 
boolean_t off_Bureaucrat::signal(off_shtl_id_t &who)
{
  off_LinkedId *id=NULL;
   if (!b_nwait)
     return FALSE;
   else {
     b_nwait--;
     assert(!b_shtls.is_empty());
     if (who == OFF_SHTL_NULL) {
       id=(off_LinkedId*)b_shtls.get_first();
     }
     else {
       DLinkedQueueItr itr = b_shtls.get_head(); 
       DLinkedQueueItr head= itr;
       do {
         if ( ((off_LinkedId*)itr.get_element())->l_id == who)
           id=(off_LinkedId*)itr.get_element();
         ++itr;
       } while (!id && itr != head);
       
     }
     if (id) {
       b_shtls.dequeue(id);
       //shtl.ready(who);  XXXX uncomment this
       who=id->l_id;
       b_alloc->deallocate(id);

     }
     return (id!=NULL);
   }
}

We have used some methods that will be described below. Namely, IdQueue::enqueue and IdQueue::dequeue to insert and remove elements in a queue of identifiers and also ShtlSrv::ready to unblock a shuttle.

When a Bureaucrat is destroyed it will try to awake every shuttle sleeping on it.

<off_Bureaucrat::~off_Bureaucrat implementation. >= (U->)
// Destroyes a bureaucrat.
off_Bureaucrat::~off_Bureaucrat(void)
{
  for (off_shtl_id_t s=OFF_SHTL_NULL; signal(s); s=OFF_SHTL_NULL)
    ;
  assert(b_shtls.is_empty());
}

\subsubsection{Bureaucracy \cpp{} source files} The source files containing this code are named klib/Bureaucrat.h and klib/Bureaucrat.C.

The interface is only visible inside the kernel.

<Bureaucrat.h*>=
<Read the literate code instead warning. >
#ifndef __OFF_BUREAUCRAT_H
#define  __OFF_BUREAUCRAT_H 1

#ifdef __KERNEL__

#include <assert.h>             // for assert
#include <klib/ids.h>           // for off_shtl_id_t 
#include <klib/err.h>           // for err_t 
#include <klib/BlockAllocator.h> // for off_BlockAllocator
#include <klib/dqueue.h>        // for DLinkedQueue et al
#include <flux/types.h>         // for boolean_t, natural_t et al.

<Off bureaucrat node. >
<Off bureaucrat. >

#endif // __KERNEL__
#endif // __OFF_BUREAUCRAT_H

<Bureaucrat.C*>=
<Read the literate code instead warning. >

#include <klib/Bureaucrat.h>    // Exported interface.
//#include <shtl/ShtlSrv.h>       // for ready() XXX uncomment this

<off_Bureaucrat::off_Bureaucrat implementation. >
<off_Bureaucrat::~off_Bureaucrat implementation. >
<off_Bureaucrat::wait implementation. >
<off_Bureaucrat::signal implementation. >

%% --------------------------------------------------------------