Sometimes we have a fixed number of allocatable resource units but we know in advance that only a small subset of units will be allocated at most. In that case we want a fixed allocator but we don't want to maintain bookkeeping information for every existing resource unit.
For such occasions we use a sparse allocator. At instantiation time it will receive the theoretical size along with the real one.
<Off sparse allocator. >= (U->)
// An sparse fixed allocator.
//
class off_SparseAllocator : protected off_FixedAllocator {
private:
natural_t s_len;
protected:
<Other protected members of off_SparseAllocator. >
<Other protected methods of off_SparseAllocator. >
public:
// So that we could declare uninitialized instances.
off_SparseAllocator(void){;}
// Creates an sparse allocator.
off_SparseAllocator(off_Exhausted *r, const off_Indexable *i,
void *first, natural_t real_len, natural_t len ) :
off_FixedAllocator(r,i,first,real_len),
s_len(len)
{
<Initialize other protected members of off_SparseAllocator. >
}
// Allocate (deallocate) units.
// Return NULL when allocation failed.
void *allocate(natural_t at, boolean_t use_revocation=FALSE);
void deallocate( void *p);
<Other public methods of off_SparseAllocator. >
};
Definesoff_SparseAllocator(links are to index).
<Off sparse allocator dependencies. >= (U->) #include <klib/FixedAllocator.h> // for off_FixedAllocator
Each allocated item has a real position in the FixedAllocator as
well as an official position as seen by the user. To map the user view
to the reality we use an array of indexes. The ith item in the array
maintains the official index for the element in FixedAllocator[i] .
<Other protected members of off_SparseAllocator. >= (<-U)
natural_t *s_pos;
<Initialize other protected members of off_SparseAllocator. >= (<-U)
s_pos = new natural_t[real_len];
for (natural_t i=0; i<real_len; i++)
s_pos[i]=s_len; // ANY invalid value
To allocate a given unit we scan the s_pos array and allocate a
new slot when it was not already allocated.
<off_SparseAllocator::allocate implementation. >= (U->)
// Allocate units.
// Return NULL when allocation failed.
void *off_SparseAllocator::allocate(natural_t at, boolean_t use_revocation)
{
void *n;
if (lookup(at) || (n=off_FixedAllocator::allocate(use_revocation)) == NULL)
return NULL;
else {
s_pos[off_FixedAllocator::pos(n)] = at;
return n;
}
}
We used lookup which converts an official index into a real one.
<Other protected methods of off_SparseAllocator. >= (<-U)
// Translates the official index at to the real one.
// returns TRUE when the item was found.
boolean_t lookup(natural_t &at) const;
<off_SparseAllocator::lookup implementation. >= (U->)
// Translates the official index at to the real one.
// returns TRUE when the item was found.
boolean_t off_SparseAllocator::lookup(natural_t &at) const
{
for (natural_t i=0; i<off_BKAllocator::get_length(); i++)
if (s_pos[i]==at){
at = i;
return TRUE;
}
return FALSE;
}
<off_SparseAllocator::deallocate implementation. >= (U->)
void off_SparseAllocator::deallocate( void *p)
{
assert(ptr_valid(p));
s_pos[off_FixedAllocator::pos(p)]= s_len;
}
Now we have to redefine those methods using indexes to operate on the ``official'' ones.
<Other public methods of off_SparseAllocator. >= (<-U) [D->]
// Is it free?
boolean_t is_free(natural_t at) const { return !lookup(at); }
void *operator+(natural_t at) const;
natural_t pos(const void*p);
natural_t get_length(void) const { return s_len;}
It now must scan the list of nodes and consider the given one to be free only when it is not found in the list of official slots.
<off_SparseAllocator::operator+ implementation. >= (U->)
void *off_SparseAllocator::operator+(natural_t at) const
{
if( lookup(at) )
return this->off_FixedAllocator::operator+(at);
else
return NULL;
}
<off_SparseAllocator::pos implementation. >= (U->)
natural_t off_SparseAllocator::pos(const void*p)
{
if (!ptr_valid(p))
return (natural_t)-1;
else
return s_pos[off_FixedAllocator::pos(p)];
}
Although above methods redefine the allocated unit positions, it is convenient to maintain another method which could be used to access resources with real indexes (mostly to pre-initialize the allocated resources).
<Other public methods of off_SparseAllocator. >+= (<-U) [<-D]
void *real_add(natural_t at) const {
return this->off_FixedAllocator::operator+(at);
}
To use a SparseAllocator this type-safe version should be
preferred.
<Off type safe sparse allocator. >= (U->)
// An sparse fixed allocator.
//
template <class T>
class off_TSparseAllocator : private off_SparseAllocator {
public:
off_TSparseAllocator(void): off_SparseAllocator() {;}
// Creates an sparse allocator.
off_TSparseAllocator(off_Exhausted *r, const off_Indexable *i,
T *first, natural_t real_len, natural_t len ) :
off_SparseAllocator(r, i, (void*)first, real_len, len )
{;}
// Allocate (deallocate) units.
// Return NULL when allocation failed.
T *allocate(natural_t at, boolean_t use_revocation=FALSE) {
return (T*)off_SparseAllocator::allocate(at,use_revocation);
}
void deallocate( T *p) { off_SparseAllocator::deallocate((void*)p); }
// Is it free?
off_SparseAllocator::is_free;
T *operator+(natural_t at) const {
return (T*)(this->off_SparseAllocator::operator+(at));
}
natural_t pos(const T*p) { return off_SparseAllocator::pos((void*)p);}
off_SparseAllocator::get_length;
T *real_add(natural_t at) const {
return (T*)off_SparseAllocator::real_add(at);
}
off_BKAllocator::get_nfree;
off_BKAllocator::get_nalloc;
off_BKAllocator::get_maxalloc;
off_BKAllocator::get_num_allocrq;
off_BKAllocator::get_num_freerq;
<Other public methods of off_TSparseAllocator. >
};
Definesoff_TSparseAllocator(links are to index).
To allow initialization of pre-allocated TSparseAllocators an operator
new is provided.
<Other public methods of off_TSparseAllocator. >= (<-U)
void * operator new(size_t s, void *p) { (void)s; return p; }
\subsubsection{The block allocator}
The BlockAllocator is an allocator which can grow dynamically.
<Off block allocator. >= (U->)
// A growing allocator.
//
class off_BlockAllocator: public off_SwAllocator {
private:
<Other private members of off_BlockAllocator. >
public:
// Allows declarations of uninitialized block allocators.
off_BlockAllocator(void){;}
// Makes it grow.
boolean_t grow(void);
<Other public methods of off_BlockAllocator. >
};
Definesoff_BlockAllocator(links are to index).
<Off block allocator dependencies. >= (U->) [D->] #include <flux/types.h> // for boolean_t natural_t et al. #include <klib/SwAllocator.h> // for off_BKAllocator
To be able to obtain new kernel virtual memory, block allocators need certain services from the kernel DMM. When no DTLB support is included in the kernel, these allocators may fail to grow. Nevertheless, they are unaware of \dtlb{} support.
What they do know is how to allocate and deallocate a page of kernel
memory (virtual or physical; depending on DTLB availability) and
what is the size of pages being allocated. The constructor receives a
pointer to an object (KVMRegion, see section ![[*]](/usr/local/install/latex2html/icons.gif/cross_ref_motif.gif){kind=icon}
)
providing page allocation routines. It also receives a revocation
trigger (Exhausted).
<Other public methods of off_BlockAllocator. >= (<-U) [D->]
// Creates a block allocator.
off_BlockAllocator(off_Exhausted *r, const off_Indexable *i,
off_KVMRegion *reg);
<Off block allocator dependencies. >+= (U->) [<-D->] #include <dmm/KVMRegion.h> // for off_KVMRegion
To create a block allocator we simply record the information needed
for normal operation. It is supposed that the allocator has been
assigned initially a single memory page. It will keep in b_end a
pointer the end of the allocated memory area.
<Other private members of off_BlockAllocator. >= (<-U)
off_KVMRegion *b_region; // Page allocator.
vm_size_t b_pgsz; // Page size.
vm_offset_t b_end; // End of preallocated memory.
<off_BlockAllocator::off_BlockAllocator implementation. >= (U->)
// Creates a block allocator.
off_BlockAllocator::off_BlockAllocator(
off_Exhausted *r, const off_Indexable *i,
off_KVMRegion *reg ) :
off_SwAllocator(r,i,(void*)reg->get_start(),
i->sub_unaligned((void*)((reg->get_start())
+reg->get_pgsz()),
(void*)reg->get_start())),
b_region(reg),
b_pgsz(reg->get_pgsz()),
b_end(reg->get_start()+reg->get_pgsz())
{
assert(reg!=NULL && b_pgsz>0 && reg->get_start()>0);
}
<Off block allocator dependencies. >+= (U->) [<-D->] #include <assert.h> // for assert
Once created, block allocator information can be copied.
<Other public methods of off_BlockAllocator. >+= (<-U) [<-D->]
off_BlockAllocator &operator=(const off_BlockAllocator &other){
return (*this=other);
}
The block allocator uses raw memory allocation routines to request
free pages to be used as the array of the SwAllocator. Besides,
when no free node is available, more memory will be allocated.
<Other public methods of off_BlockAllocator. >+= (<-U) [<-D]
// Allocates units from a growing store.
// Returns NULL when allocation fails.
void *allocate(boolean_t use_revocation=FALSE)
{
if (!get_nfree())
grow();
return off_SwAllocator::allocate(use_revocation);
}
As we do not redefine allocation at a specified position (we do now
grow automatically in such case), we be careful when using this
method. In a future kernel version the array should grow and use
zero-fill on demand kernel virtual memory. In that case, the
allocation algorithm must be changed to skip sparse allocated nodes
(because of the current assumption that every nodes after b_next
are available will no longer hold).
To make the array grow we ask for another page of memory. We specify its address so the array behaves as an array (i.e. it is contiguous). If we are using kernel virtual memory2.13 the page might be zero-fill on demand, so that we could make the array grow arbitrarily without wasting physical memory.
<off_BlockAllocator::grow implementation. >= (U->)
// Resizes the store.
// Returns non-zero if successful.
boolean_t off_BlockAllocator::grow(void)
{
void *olast=k_last;
if (b_region->pg_alloc(b_end) != b_end)
return FALSE;
k_last = k_idx->add(k_first,k_idx->sub_unaligned((void*)b_end,k_first));
resize(k_idx->sub(k_last,olast));
assert(ptr_valid(s_next));
return TRUE;
}
A type safe block allocator is also provided.
<Off type safe block allocator. >= (U->)
// A growing allocator.
//
template <class T>
class off_TBlockAllocator: private off_BlockAllocator {
public:
// Allows declarations of uninitialized block allocators.
off_TBlockAllocator(void) : off_BlockAllocator() {;}
// Creates a block allocator.
off_TBlockAllocator(off_Exhausted *r, const off_Indexable *i,
off_KVMRegion *reg ):
off_BlockAllocator(r, i, reg)
{do_debug(putchar('B'));}
off_BlockAllocator::grow;
// Allocates units from a growing store.
// Returns NULL when allocation fails.
T *allocate(boolean_t use_revocation=FALSE) {
return (T*)off_BlockAllocator::allocate(use_revocation);
}
T *allocate(natural_t at, boolean_t use_revocation=FALSE) {
return (T*)off_SwAllocator::allocate(at,use_revocation);
}
void deallocate(T *p) { off_BlockAllocator::deallocate((void*)p);}
off_SwAllocator::is_free;
off_BKAllocator::get_nfree;
off_BKAllocator::get_nalloc;
off_BKAllocator::get_maxalloc;
off_BKAllocator::get_num_allocrq;
off_BKAllocator::get_num_freerq;
off_BKAllocator::get_length;
natural_t pos(T *p) { return off_KernAllocator::pos((void*)p); }
<Other public methods of off_TBlockAllocator. >
};
Definesoff_TBlockAllocator(links are to index).
<Off block allocator dependencies. >+= (U->) [<-D] #include <flux/debug.h> // for do_debug et al.
To allow initialization of pre-allocated TBlockAllocators an operator
new is provided.
<Other public methods of off_TBlockAllocator. >= (<-U) [D->]
void * operator new(size_t s, void *p) { (void)s; return p; }