mapdb_i.h

Go to the documentation of this file.

// AUTOMATICALLY GENERATED -- DO NOT EDIT!         -*- c++ -*-

#ifndef mapdb_i_h
#define mapdb_i_h

#include "config.h"

/* The mapping database.

 * This implementation encodes mapping trees in very compact arrays of
 * fixed sizes, prefixed by a tree header (Mapping_tree).  Array
 * sizes can vary from 4 mappings to 4<<15 mappings.  For each size,
 * we set up a slab allocator.  To grow or shrink the size of an
 * array, we have to allocate a larger or smaller tree from the
 * corresponding allocator and then copy the array elements.
 * 
 * The array elements (Mapping) contain a tree depth element.  This
 * depth and the relative position in the array is all information we
 * need to derive tree structure information.  Here is an example:
 * 
 * array
 * element   depth
 * number    value    comment
 * --------------------------
 * 0         0        Sigma0 mapping
 * 1         1        child of element #0 with depth 0
 * 2         2        child of element #1 with depth 1
 * 3         2        child of element #1 with depth 1
 * 4         3        child of element #3 with depth 2
 * 5         2        child of element #1 with depth 1
 * 6         3        child of element #5 with depth 2
 * 7         1        child of element #0 with depth 0
 * 
 * This array is a pre-order encoding of the following tree:
 * 
 *                   0
 *                /     \ 
 *               1       7
 *            /  |  \                   
 *           2   3   5
 *               |   |
 *               4   6
                   
 * IDEAS for enhancing this implementation: 

 * We often have to find a tree header corresponding to a mapping.
 * Currently, we do this by iterating backwards over the array
 * containing the mappings until we find the Sigma0 mapping, from
 * whose address we can compute the address of the tree header.  If
 * this becomes a problem, we could add one more byte to the mappings
 * with a hint (negative array offset) where to find the sigma0
 * mapping.  (If the hint value overflows, just iterate using the hint
 * value of the mapping we find with the first hint value.)  Another
 * idea (from Adam) would be to just look up the tree header by using
 * the physical address from the page-table lookup, but we would need
 * to change the interface of the mapping database for that (pass in
 * the physical address at all times), or we would have to include the
 * physical address (or just the address of the tree header) in the
 * Mapdb-user-visible Mapping (which could be different from the
 * internal tree representation).  (XXX: Implementing one of these
 * ideas is probably worthwile doing!)

 * Instead of copying whole trees around when they grow or shrink a
 * lot, or copying parts of trees when inserting an element, we could
 * give up the array representation and add a "next" pointer to the
 * elements -- that is, keep the tree of mappings in a
 * pre-order-encoded singly-linked list (credits to: Christan Szmajda
 * and Adam Wiggins).  24 bits would probably be enough to encode that
 * pointer.  Disadvantages: Mapping entries would be larger, and the
 * cache-friendly space-locality of tree entries would be lost.

 * The current handling of superpages sucks rocks both in this module
 * and in our user, map_util.cpp.  We could support multiple page sizes
 * by not using a physframe[] array only for the largest page size.
 * (Entries of that array point to the top-level mappings -- sigma0
 * mappings.)  Mapping-tree entries would then either be regular
 * mappings or pointers to an array of mappings of the next-smaller
 * size. (credits: Christan Szmajda)
 * One problem with this approach is that lookups become more expensive as
 * a task's mapping potentially can be in many subtrees.
 *
 *        physframe[]
 *        -------------------------------
 *        | | | | | | | | | | | | | | | | array of ptr to 4M Mapping_tree's
 *        ---|---------------------------
 *           |
 *           v a Mapping_tree
 *           ---------------
 *           |             | tree header
 *           |-------------|
 *           |             | Mapping *or* ptr to array of ptr to 4K trees
 *           |             | e.g.
 *           |      ----------------|
 *           |             |        v array of ptr to 4M Mapping_tree's
 *           ---------------        -------------------------------
 *                                  | | | | | | | | | | | | | | | |
 *                                  ---|---------------------------
 *                                     |
 *                                     v a Mapping_tree
 *                                     ---------------
 *                                     |             | tree header
 *                                     |-------------|
 *                                     |             | Mapping
 *                                     |             |
 *                                     |             |
 *                                     |             |
 *                                     ---------------
 */

#include <cassert>
#include <cstring>

#include <auto_ptr.h>

#include "config.h"
#include "globals.h"
#include "helping_lock.h"
#include "mapped_alloc.h"
#include "kmem_slab.h"
#include "std_macros.h"

// 
// Mapping_tree
// 
struct Mapping_tree
{
  //friend class Mapdb;
  // DATA
  unsigned _count: 16;          
  unsigned _size_id: 4;         
  unsigned _empty_count: 11;    
                                //   XXX currently never read, except in
                                //   sanity checks

  unsigned _unused: 1;          // (make this 32 bits to avoid a compiler bug)

  Mapping _mappings[0] __attribute__((packed));

public:  
  inline void* operator new (size_t, unsigned size_factor);
  
  inline void operator delete (void* block, size_t);
  
  //inline NEEDS[Mapping_depth, Mapping_tree::last]
  Mapping_tree(unsigned size_factor, unsigned page_number);
  
  //inline NEEDS[Mapping_depth, Mapping_tree::last]
  Mapping_tree(unsigned size_factor, Mapping_tree* from_tree);
  
  // public routines with inline implementations
  inline unsigned number_of_entries() const;
  
  inline Mapping * mappings();
  
  inline Mapping * end();
  
  inline Mapping * last();
  
  // This function copies the elements of mapping tree src to mapping
  // tree dst, ignoring empty elements (that is, compressing the
  // source tree.  In-place compression is supported.
  static void copy_compact_tree(Mapping_tree *dst, Mapping_tree *src);
  
  inline void check_integrity();
};

enum Mapping_depth 
{
  Depth_root = 0, Depth_max = 252, 
  Depth_subtree = 253, Depth_empty = 254, Depth_end = 255 
};

// Helpers

//
// Mapping-tree allocators
// 

enum Mapping_tree_size
{
  Size_factor = 4, 
  Size_id_max = 8               // can be up to 15 (4 bits)
};

class mapping_tree_allocators 
{
  auto_ptr<Kmem_slab> _allocator [Size_id_max + 1];

  friend class foo;             // Avoid warning about not being constructible

public:  
  inline Kmem_slab * allocator_for_treesize(int size);
  
  static inline mapping_tree_allocators& instance();

private:  
  mapping_tree_allocators();
};

// 
// Physframe
// 

class Physframe
{
  friend class Mapdb;
  friend class Jdb_mapdb;

  // DATA
  auto_ptr<Mapping_tree> tree;
  //Mapping_tree* tree;
  Helping_lock lock;

  // CONSTRUCTORS
  Physframe ()
    // Optimization: do this using memset in operator new []
    //: tree (0)
  {}

  ~Physframe()
  {
    assert (! lock.test());

#if 0
    if (tree)
      {
        // Find next-level trees.
        for (Mapping* m = tree->mappings(); 
             m;
             m = m->next (tree->end()))
          {
            if (m->subtree())
              delete m->subtree();
          }
      }
#endif
  }

  void* operator new [] (size_t size)
    {
      size = (size + Config::PAGE_SIZE - 1) >> Config::PAGE_SHIFT;
      void* block = Mapped_allocator::allocator()->unaligned_alloc (size);
      if (block)
        memset(block, 0, size);  // Optimization: See constructor
      return block;
    }

  void operator delete [] (void* block, size_t size)
    {
      if (! block)
        return;
      size = (size + Config::PAGE_SIZE - 1) >> Config::PAGE_SHIFT;
      Mapped_allocator::allocator()->unaligned_free (size, block);
    }
}; // struct Physframe

//
// IMPLEMENTATION of inline functions follows
//




inline Mapping::Mapping()
{}


inline bool
Mapping::unused()
{
  return data()->depth > Depth_subtree;
}



inline bool
Mapping::is_end_tag()
{
  return data()->depth == Depth_end;
}



inline Mapping *
Mapping::next(const Mapping* end_of_tree)
{
  for (Mapping* m = this + 1; 
       m < end_of_tree && ! m->is_end_tag(); 
       m++)
    {
      if (! m->unused())
        return m;
    }

  return 0;
}



static inline Kmem_slab *
allocator_for_treesize(int size)
{
  return mapping_tree_allocators::instance().allocator_for_treesize(size);
}



inline void*
Mapping_tree::operator new (size_t, unsigned size_factor)
{
  return allocator_for_treesize(size_factor)->alloc();
}



inline void
Mapping_tree::operator delete (void* block, size_t)
{
  if (!block)
    return;

  // Try to guess right allocator object -- XXX unportable!
  Mapping_tree* t = static_cast<Mapping_tree*>(block);

  t->check_integrity();

  allocator_for_treesize(t->_size_id)->free(block);
}


// public routines with inline implementations

inline unsigned 
Mapping_tree::number_of_entries() const
{
  return Size_factor << _size_id;
}



inline Mapping *
Mapping_tree::mappings()
{
  return & _mappings[0];
}



inline Mapping *
Mapping_tree::end()
{
  return mappings() + number_of_entries();
}



inline Mapping *
Mapping_tree::last()
{
  return end() - 1;
}



inline void
Mapping_tree::check_integrity()
{
#ifndef NDEBUG
  // Sanity checking
  assert (// Either each entry is used
          number_of_entries() == _count + _empty_count
          // Or the last used entry is end tag
          || mappings()[_count + _empty_count].is_end_tag());

  Mapping* m = mappings();

  assert (! m->unused()         // The first entry is never unused.
          && m->data()->space_is_sigma0()
          && m->data()->depth == 0);

  unsigned 
    used = 0,
    dead = 0;

  while (m < end()
           && ! m->is_end_tag())
    {
      if (m->unused())
        dead++;
      else
        used++;

      m++;
    }

  assert (_count == used);
  assert (_empty_count == dead);
#endif // ! NDEBUG
}



inline Kmem_slab *
mapping_tree_allocators::allocator_for_treesize(int size)
{
  return _allocator[size].get();
}


inline mapping_tree_allocators&
mapping_tree_allocators::instance()
{
  static mapping_tree_allocators tree_allocators;

  return tree_allocators;
}  

#endif // mapdb_i_h

---