next up previous contents
Next: 6. Miscellaneous data structures Up: 5.4 Kernel address space Previous: 5.4 Kernel address space

5.4.0.1 Growing memory region

It a region which should not fault and grows by

Thus, we use one of two kinds of GrowingRegions depending on existing DTLB support. 

<Off resizeable kernel virtual memory region. >= (U->)
// A kernel growing region. 
//
class off_GrowingRegion : public off_NullFaultingRegion {
protected:
  <Other protected methods of off_GrowingRegion. >
  <Other protected members of off_GrowingRegion. >

};

// A kernel growing region without dtlb support.
class off_GrowingPRegion : public off_GrowingRegion {
public:
  <Other public methods of off_GrowingPRegion. >
};

// A kernel growing memory region with dtlb support. 
class off_GrowingVRegion : public off_GrowingRegion {
public:
  <Other public methods of off_GrowingVRegion. >
};
Defines off_GrowingPRegion, off_GrowingRegion, off_GrowingVRegion (links are to index).

When a growing region is created it is given a valid starting (kernel virtual) address and a size limit. It then grows as memory is allocated by mapping new kernel pages right after the last mapped one.

Besides, regions may grow to higher addresses or to lower addresses, such parameter must be specified in advance. 

<Other protected methods of off_GrowingRegion. >= (<-U) [D->]
// Creates a growing memory region.
// By default it grows left (low addresses) to right (high addresses)
off_GrowingRegion(vm_offset_t start, vm_offset_t end, 
                  boolean_t left2right =TRUE);

Note how GrowingRegions can not be instantiated. Constructors for GrowingPRegions and GrowingVRegions are available and receive the same arguments. 

<Other public methods of off_GrowingPRegion. >= (<-U) [D->]
// Creates a growing memory region.
// By default it grows left (low addresses) to right (high addresses)
off_GrowingPRegion(vm_offset_t start, vm_size_t limit, 
                   boolean_t left2right =TRUE) :
  off_GrowingRegion(start,limit,left2right)
{;}


<Other public methods of off_GrowingVRegion. >= (<-U) [D->]
// Creates a growing memory region.
// By default it grows left (low addresses) to right (high addresses)
off_GrowingVRegion(vm_offset_t start, vm_size_t limit, 
                   boolean_t left2right =TRUE) :
  off_GrowingRegion(start,limit,left2right)
{;}

What we do to handle a growing region is to keep the (signed) size for each mapped page and the address where the next page should be mapped. 

<Other protected members of off_GrowingRegion. >= (<-U)
vm_offset_t g_end;              // End of mapped memory.
int         g_sz;               // Mapped page size.

We initialize g_sz so that by adding it to g_end we make g_end grow in the appropriate direction. 

<off_GrowingRegion::off_GrowingRegion implementation. >= (U->)
// Creates a growing memory region.
off_GrowingRegion::off_GrowingRegion(vm_offset_t start, vm_offset_t end,
                                     boolean_t left2right ):
  off_NullFaultingRegion(start,end),
  g_end((left2right)?start:end),
  g_sz((left2right)?off_MBank::get_pgsize():(0-(int)off_MBank::get_pgsize()))
{;}

After that, allocation proceeds differently depending on \dtlb{} support by mapping pages at g_end and adjusting g_end to the next unmapped page. Deallocation requests are silently discarded.

To implement them it is handy to know if a resize would pass the region limit and the starting address to be mapped to make the region grow. 

<Other protected methods of off_GrowingRegion. >+= (<-U) [<-D]
// Does this grow operation (n pages) fit in region limits?
inline boolean_t grow_fits(natural_t n) const;
// What is the map start address for the new memory?
inline vm_offset_t grow_start(natural_t n) const;


<off_GrowingRegion::grow_fits implementation. >= (U->)
// Does this grow operation (n pages) fit in region limits?
inline boolean_t off_GrowingRegion::grow_fits(natural_t n) const
{
  vm_offset_t new_end=n*g_sz + g_end;
  return r_start <= new_end && new_end <= r_end;
}



<off_GrowingRegion::grow_start implementation. >= (U->)
// What is the map start address for the new memory?
inline vm_offset_t off_GrowingRegion::grow_start(natural_t n) const
{
  return (g_sz > 0) ? g_end : (g_end + g_sz*n);
}

Methods pg_alloc and pg_free are implemented in GrowingPRegions and GrowingVRegions. 

<Other public methods of off_GrowingPRegion. >+= (<-U) [<-D]
// Allocates a kernel page.
// Chooses the location if at is 0.
virtual vm_offset_t pg_alloc(vm_offset_t at);
// Allocates n kernel pages.
// Chooses the location if at is 0.
virtual vm_offset_t pg_alloc(vm_offset_t at, natural_t n);

When no \dtlb{} is available we must restrict ourselves to the range specified at creation time as there is no address translation. Thus we try to allocate the first available page in the allocation region.

Thus, we simply use the page allocator to request pages at the break. 

<off_GrowingPRegion::pg_alloc implementation. >= (U->)
// Allocates a kernel page.
// Chooses the location if at is 0.
vm_offset_t off_GrowingPRegion::pg_alloc(vm_offset_t at) 
{
  if (!grow_fits(1))
    return 0;
  at=r_palloc->alloc(grow_start(1));
  g_end+=g_sz;
  return at;
}

// Allocates n kernel pages.
// Chooses the location if at is 0.
vm_offset_t off_GrowingPRegion::pg_alloc(vm_offset_t at, natural_t n) 
{
  if (!grow_fits(n))
    return 0;
  at=r_palloc->alloc(grow_start(n),n);
  g_end +=g_sz*n;
  return at;
}

When \dtlb{} support is available we can request any page frame and map it at the break. This is not yet implemented and will be implemented as soon as DTLBs are stable enough. 

<Other public methods of off_GrowingVRegion. >+= (<-U) [<-D]
// Allocates a kernel page.
// Chooses the location if at is 0.
virtual vm_offset_t pg_alloc(vm_offset_t at) { (void)at; return 0; }

// Allocates n kernel pages.
// Chooses the location if at is 0.
virtual vm_offset_t pg_alloc(vm_offset_t at, natural_t n) {
  (void)at; (void)n; return 0;
}

\subsubsection{Block allocator and kernel stack regions}

We need a new couple of region types. 

<Off self resizeable kernel virtual memory region. >= (U->)
// A self resizeable kernel virtual memory region. 
//
class off_SelfGrowingPRegion : public off_GrowingPRegion {
public:
  off_SelfGrowingPRegion(vm_offset_t start, vm_offset_t end,
                         boolean_t left2right = TRUE );
};

class off_SelfGrowingVRegion : public off_GrowingVRegion {
public:
  off_SelfGrowingVRegion(vm_offset_t start, vm_offset_t end,
                         boolean_t left2right = TRUE ) :
    off_GrowingVRegion(start,end,left2right)
  {;}

  <Other public methods of off_SelfGrowingVRegion. >
};
Defines off_SelfGrowingPRegion, off_SelfGrowingVRegion (links are to index).

The one without \dtlb{} support simply allocates every page in the region right from the start. 

<off_SelfGrowingPRegion::off_SelfGrowingPRegion implementation. >= (U->)
off_SelfGrowingPRegion::off_SelfGrowingPRegion(vm_offset_t start, 
                                               vm_offset_t end,
                                               boolean_t left2right ) :
  off_GrowingPRegion(start,end,left2right)
{
  vm_offset_t v=r_palloc->alloc(start,off_MBank::a2p(end-start));
  assert(v);
}

The one with \dtlb{} support handles page faults and allocates memory on demand. It is not yet implemented. 

<Other public methods of off_SelfGrowingVRegion. >= (<-U)
// Handles page faults 
err_t pg_fault(off_PgFltReq *pgf) { 
  assert(pgf);
  (void)pgf;
  do_debug(kcout << "page fault on kernel stack not supported." << nl);
  return ENOSYS; 
}


<Off kernel virtual memory region dependencies. >+= (U->) [<-D]
#include <flux/debug.h>         // for do_debug

\subsubsection{Splitting memory into regions}

After the kernel is loaded, the remaining virtual address space of the kernel is assigned to a potential set of NREGS_MAX (growing) regions. These regions are created by requesting a new region of a certain kind to the KVM. 

<Other public methods of off_KVM. >+= (<-U) [<-D]
// Creates a region of the specified kind and returns its 
// starting (kernel virtual) address.
// The region is for a kernel stack unless otherwise specified. 
off_KVMRegion *create_region(void);
off_KVMRegion *create_kstack(void);

When every kernel allocator has been started new regions are created only for up to NKSTKS_MAX kernel stacks. Besides, SMP support might require these stacks to be aligned to a boundary of MDEP_KSTK_MAX bytes (see section [*]).

In any case, To determine the region layouts, the KVM calls fix_regions when it is started. 

<Other private methods of off_KVM. >+= (<-U) [<-D->]
// Fix starting addresses and length for kernel regions.
void  fix_regions(void);


<Initialize KVM regions starting at end with dtlb_support. >= (<-U) [D->]
fix_regions();

To implement it we need to now how much (kernel virtual) memory is available. The kvm uses these methods to calculate that. 

<Other private methods of off_KVM. >+= (<-U) [<-D->]
// How much memory available for kernel usage?
vm_size_t get_kavail(void);

In turn, it uses this other. 

<Other private methods of off_KVM. >+= (<-U) [<-D->]
// Where does our KVM ends?
vm_offset_t get_kmax(void);

When using virtual memory we have from k_end up to the kernel virtual address space end, otherwise we are limited by the physical core size. If there is no DTLB support, we stick to a percentage of the remaining physical memory which is assigned to the kernel. 

<off_KVM::get_kavail implementation. >= (U->)
// How much memory available for kernel usage?
vm_size_t off_KVM::get_kavail(void) 
{
  return get_kmax() - k_end;
}



<off_KVM::get_kmax implementation. >= (U->)
// Where does our KVM ends?
vm_offset_t off_KVM::get_kmax(void) 
{
  vm_offset_t at;
  if (k_hasdtlb)
   at= OFF_USER_VM_START-1;
  else 
   at=k_end+off_MBank::get_coresize()/OFF_KERN_MEM_FRAC;
  at =  off_MBank::ptrunc(at)+off_MBank::pmask();

  return at;
}



<Off kernel virtual memory manager implementation dependencies. >+= (U->) [<-D]
#include <hw/MBank.h>           // for off_MBank 
#include <dmm/mdep/mKVM.h>      // for OFF_USER_VM_START et al.

Where OFF_USER_VM_START is the first user virtual address (which determines the end of the kernel virtual address space) and OFF_KERN_MEM_FRAC is the fraction of memory to be consumed by the kernel. Both things are system limits. 

<Off limits. >+= [<-D]
const int         OFF_KERN_MEM_FRAC=8;        // 1/8 memory for the kernel.

We first divide the available memory into the total number of regions, then we reserve the last NKSTKS_MAX blocks (MDEP_KSTK_MAX-aligned; maybe) for kernel stacks and store in three new members the address for the first kernel stack, the maximum number of kernel stacks, and the starting address for the first kernel stack. 

<Other private members of off_KVM. >+= (<-U) [<-D]
vm_offset_t k_stack0;           // low address for the first kernel stack.
natural_t   k_nstacks;          // Max # of OFF_MDEP_KSTK_MAX-sized kern. stcks
vm_size_t   k_rsize;            // Size of non stack regions. 


<off_KVM::fix_regions implementation. >= (U->)
// Determines the starting address for a new region.
void off_KVM::fix_regions(void)
{
  vm_size_t   avail;

  
  k_end=off_MBank::pround(k_end);
  avail= get_kavail();
  k_rsize=off_MBank::ptrunc(avail/OFF_NREGS_MAX);

  <Determine k_nstacks and k_rsize. >
  if (!k_nstacks)
    panic("No memory for kernel stacks");
  assert(k_nstacks);
  <Determine k_stack0. > 
  if (k_stack0+OFF_MDEP_KSTK_MAX > get_kmax())
    panic("No memory for even a single kernel stack.");
  assert(k_nstacks>=1);
  
}

The number of kernel stacks is set initially to NKSTKS_MAX, and then reduced until we are sure that each region can be at least MDEP_KSTK_MSK. 

<Determine k_nstacks and k_rsize. >= (<-U)
for(k_nstacks=OFF_NKSTKS_MAX; k_nstacks && k_rsize < OFF_MDEP_KSTK_MAX;
    k_nstacks--){
  k_rsize=off_MBank::ptrunc(avail/(OFF_NKBLKS_MAX+k_nstacks));
}

The first stack (low address) will start after reserving (virtual) space for non-stack regions (which can be up to NKBLKS_MAX). For aligned kernel stacks we must also align it. 

<Determine k_stack0 for aligned stacks. >=
k_stack0= ((k_end+OFF_NKBLKS_MAX*k_rsize) + OFF_MDEP_KSTK_MSK)
  & ~OFF_MDEP_KSTK_MSK;

For non-aligned stacks it is simpler. 

<Determine k_stack0. >= (<-U)
{
  extern char end[];
  k_stack0=(register_t)(end+OFF_NKBLKS_MAX*k_rsize);
}

Finally, if stacks were aligned we should adjust k_nstacks and k_stack0 to be user we have enough aligned space. 

<Adjust k_nstacks and k_stack0 due to alignment constraints. >=
avail=get_kmax()-(k_stack0+OFF_MDEP_KSTK_MAX);
kstack_end=get_kmax() & ~OFF_MDEP_KSTK_MSK;
k_nstacks = (kstack_end - k_stack0) / OFF_MDEP_KSTK_MAX;

Once limits are fixed the KVM can instantiate new regions. First it will be asked for up to OFF_NKBLKS_MAX generic regions, then up to k_nstacks.

These methods are handy to determine the starting address and limit for regions being created. 

<Other private methods of off_KVM. >+= (<-U) [<-D]
// Determines the starting address for a new region.
vm_offset_t fix_region_start(void);
// Determines the limit (size) for a new region.
vm_size_t fix_region_limit(void) const;
// Determines the starting address for a new kernel stack.
vm_offset_t fix_stack_start(void);
// Determines the limit (size) for a new kernel stack.
vm_size_t fix_stack_limit(void) const;

Each new region will start either at k_end or k_stack0; and k_end adjusted past the limit of that region. 

<off_KVM::fix_region_start implementation. >= (U->)
// Determines the starting address for a new region.
vm_offset_t off_KVM::fix_region_start(void)
{
  vm_offset_t start=k_end;
  k_end += k_rsize;
  return start;
}



<off_KVM::fix_stack_start implementation. >= (U->)
// Determines the starting address for a new kernel stack.
vm_offset_t off_KVM::fix_stack_start(void)
{
  vm_offset_t start=k_stack0;
  k_stack0 += OFF_MDEP_KSTK_MAX;
  return start;
}



<off_KVM::fix_region_limit implementation. >= (U->)
// Determines the limit (size) for a new region.
vm_size_t off_KVM::fix_region_limit(void) const
{
  return k_rsize;
}



<off_KVM::fix_stack_limit implementation. >= (U->)
// Determines the limit (size) for a new stack.
vm_size_t off_KVM::fix_stack_limit(void) const
{
  return OFF_MDEP_KSTK_MAX;
}

Now we can implement create_region and create_kstack. 

<off_KVM::create_region implementation. >= (U->)
// Creates a region of the specified kind and returns its 
// starting (kernel virtual) address.
off_KVMRegion *off_KVM::create_region(void)
{
  vm_offset_t start;
  vm_size_t   sz;

  start = fix_region_start();
  sz    = fix_region_limit();
  if (k_hasdtlb)
    k_regions[k_nregions]= new off_GrowingVRegion(start,sz);
  else
    k_regions[k_nregions]= new off_GrowingPRegion(start,sz);
  assert (k_regions[k_nregions]!=NULL);
  return k_regions[k_nregions++];
}



<off_KVM::create_kstack implementation. >= (U->)
// Creates a region of the specified kind and returns its 
// starting (kernel virtual) address.
off_KVMRegion *off_KVM::create_kstack(void)
{
  vm_offset_t start=fix_stack_start();
  vm_size_t   sz=fix_stack_limit();
  if (k_hasdtlb)
    k_regions[k_nregions]= 
      new off_SelfGrowingVRegion(start,sz,off_mdepStck::grows_to_right());
  else
    k_regions[k_nregions]= 
      new off_SelfGrowingPRegion(start,sz,off_mdepStck::grows_to_right());
  assert (k_regions[k_nregions]!=NULL);
  k_nregions++;
  return k_regions[k_nregions++];
}


<Off kernel virtual memory manager dependencies. >+= (U->) [<-D]
#include <klib/mdep/mStck.h>

The KVM itself instantiates an initial region for dynamic memory. 

<Initialize KVM regions starting at end with dtlb_support. >+= (<-U) [<-D]
create_region();

\subsubsection{Kernel page allocator \cpp{} source files}

The kernel page allocator is kept in dmm/KPgAllocator.h and dmm/KPgAllocator.C. 

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

<Off kernel page allocator dependencies. >

#ifdef __KERNEL__
<Off kernel page allocator. >
#endif // __KERNEL__

#endif // __OFF_K_PG_ALLOCATOR_H


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

#include <dmm/KPgAllocator.h>   // exported interface.
<Off kernel page allocator implementation dependencies. >

<off_KPgAllocator::off_KPgAllocator implementation. >
<off_KPgAllocator::reconsider implementation. >
<off_KPgAllocator::find_range implementation. >
<off_KPgAllocator::alloc implementation. >
<off_KPgAllocator::free implementation. >

\subsection{Supporting kernel dynamic memory}

Dynamic memory is allocated with the new operator. This operator uses malloc in turn. 

<Off kernel dynamic memory implementation dependencies. >= (U->) [D->]
#include <assert.h>             // for assert
#include <malloc.h>             // for malloc

At boot time every free page is removed from the ``free memory pool'' used by malloc. Such pool is the OSKit malloc_lmm. Thus, we implement morecore. It is called by malloc when more free memory is needed to satisfy an allocation request. The convention is that kernel pages are assigned to the node domain.

We simply ask for any available page, which will be allocated by the KVM in the kernel allocation region. 

<off_morecore implementation. >= (U->)
// Makes more memory available for malloc. 
int morecore(size_t size)
{
  vm_offset_t va=0;
  assert(size);
  if (size & off_MBank::pmask())                 /* round to K*pgsz */
    size  = (size & ~off_MBank::pmask()) +1;
  
  if (size <= off_MBank::get_pgsize()){
    va=kvm.pg_alloc(0);
  }
  else{
    va=kvm.pg_alloc(0,off_MBank::a2p(size));
  }
  if (va){
    lmm_add_free(&malloc_lmm,(void*)va,size);
  }
  return va;
}
Defines off_morecore (links are to index).

Note how a PFrame* is converted to an vm_offset_t using an operator provided by PFrames. 

<Off kernel dynamic memory implementation dependencies. >+= (U->) [<-D]
#include <flux/lmm.h>           // for lmm_add_free et al.
#include <dmm/KVM.h>            // for pg_alloc et al.
#include <hw/MBank.h>           // for off_MBank 
#include <hw/PFrame.h>          // for off_PFrame

\subsubsection{Kernel dynamic memory \cpp{} source files}

These routines are kept in new.C. 

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

<Off kernel dynamic memory implementation dependencies. >

extern "C" {
  <off_morecore implementation. >
};                              // C linkage

\subsection{Kernel address space manager \cpp{} source files}

The KVM is kept in dmm/KVM.h and dmm/KVM.C. 

<KVM.h*>=
<Read the literate code instead warning. >
#ifndef __OFF_KVM_H
#define __OFF_KVM_H

<Off kernel virtual memory manager dependencies. >

<Off KVM region numbers. >

#ifdef __KERNEL__
<Off kernel virtual memory manager. >
<Off KVM exported variables. >
#endif // __KERNEL__

#endif // __OFF_KVM_H


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

#include <dmm/KVM.h>            // Exported interface.
<Off kernel virtual memory manager implementation dependencies. >

<off_KVM static members. >
<Off KVM instance. >

<Off kernel virtual memory manager static members. >
<off_KVM::off_KVM implementation. >
<off_KVM::start implementation. >
<off_KVM::get_kavail implementation. >
<off_KVM::find_region implementation. >
<off_KVM::fix_regions implementation. >
<off_KVM::fix_region_start implementation. >
<off_KVM::fix_stack_start implementation. >
<off_KVM::fix_region_limit implementation. >
<off_KVM::fix_stack_limit implementation. >
<off_KVM::create_region implementation. >
<off_KVM::create_kstack implementation. >
<off_KVM::get_kmax implementation. >

<off_KVM::pg_alloc implementation. >
<off_KVM::pg_free implementation. >
<off_KVM::pg_fault implementation. >

Kernel region code is in dmm/KVMRegion.h and dmm/KVMRegion.C. 

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

<Off kernel virtual memory region dependencies. >

#ifdef __KERNEL__
<Off kernel virtual memory region. >
<Off fixed and faulting kernel virtual memory region. >
<Off resizeable kernel virtual memory region. >
<Off self resizeable kernel virtual memory region. >
#endif // __KERNEL__

#ifdef __KERNEL__
<off_KVMRegion::get_start and get_end implementation. >
<off_GrowingRegion::grow_fits implementation. >
<off_GrowingRegion::grow_start implementation. >
#endif // __KERNEL__

#endif // __OFF_KVM_REGION_H


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

#include <dmm/KVMRegion.h>      // Exported interface. 
<Off kernel virtual memory region implementation dependencies. >

<off_KVMRegion static members. >

<off_KVMRegion::off_KVMRegion implementation. >
<off_NullFaultingRegion::off_NullFaultingRegion implementation. >
<off_GrowingRegion::off_GrowingRegion implementation. >
<off_SelfGrowingPRegion::off_SelfGrowingPRegion implementation. >
<off_NullFaultingRegion::pg_fault implementation. >
<off_GrowingPRegion::pg_alloc implementation. >
<off_KVMRegion::get_pgsize implementation. >

\section{Kernel address space manager for ix86 based architectures}

It defines the first valid user virtual address. 

<mdep mKVM.h*>=
<Read the literate code instead warning. >
#ifndef __OFF_MDEP_KVM_H
#define __OFF_MDEP_KVM_H 1

#include <flux/machine/base_gdt.h> // for USER_OFF

const vm_offset_t OFF_USER_VM_START=USER_OFF;

#endif // __OFF_MDEP_KVM_H

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

next up previous contents
Next: 6. Miscellaneous data structures Up: 5.4 Kernel address space Previous: 5.4 Kernel address space
Francisco J. Ballesteros
1998-05-25