/* 
 *   Copyright (c) 1998, 2002 Michael J. Roberts.  All Rights Reserved.
 *   
 *   Please see the accompanying license file, LICENSE.TXT, for information
 *   on using and copying this software.  
 */
/*
Name
  vmpool.h - VM constant pool manager
Function
  
Notes
  
Modified
  10/20/98 MJRoberts  - Creation
*/

#ifndef VMPOOL_H
#define VMPOOL_H

#include <stdlib.h>
#include <memory.h>

#include "vmtype.h"

/* include the pool selection mechanism */
#include "vmpoolsl.h"

/* ------------------------------------------------------------------------ */
/*
 *   Constant pool page information.  This structure tracks memory for one
 *   page.  
 */
struct CVmPool_pg
{
    /* memory containing the data in this page */
    const char *mem;
};

   
/* ------------------------------------------------------------------------ */
/*
 *   Constant Pool Backing Store Interface.  This is an abstract interface
 *   that pool clients must implement to provide the pool with the means
 *   of loading pages.
 *   
 *   Note that the backing store, like the pool itself, is considered
 *   read-only by the pool manager.  The pool manager never needs to write
 *   data to the backing store, and expects the backing store to remain
 *   constant throughout the existence of the pool (hence the pool never
 *   needs to reload any data from the backing store that it already has
 *   in cache).  
 */
class CVmPoolBackingStore
{
public:
    /* 
     *   since this class is abstract, make sure all subclasses have virtual
     *   destructors 
     */
    virtual ~CVmPoolBackingStore() { }
    
    /*
     *   Determine the total number of pages that are available to be
     *   loaded.  Implementations of the pool manager that pre-load all
     *   pages use this function to determine how many pages are available
     *   for loading.  
     */
    virtual size_t vmpbs_get_page_count() = 0;

    /*
     *   Get the common page size in the underying store.  Individual
     *   pages may not use the entire page size, but no page may be larger
     *   than the common size.  
     */
    virtual size_t vmpbs_get_common_page_size() = 0;

    /*
     *   Given a starting offset and a page size, calculate how much space is
     *   actually needed for the page at the offset.  This is provided to
     *   allow for partial pages, which don't need the full page size
     *   allocated.  Simple implementations can simply always return the full
     *   page size.  
     */
    virtual size_t vmpbs_get_page_size(pool_ofs_t ofs, size_t page_size) = 0;

    /*
     *   Given a starting offset, allocate space for the given page and
     *   load it into memory.  page_size is the normal page size in bytes,
     *   and load_size is the actual number of bytes to be allocated and
     *   loaded (this will be the value previously returned by
     *   vmpbs_get_page_size for the page).
     *   
     *   This should throw an exception if an error occurs.  
     */
    virtual const char
        *vmpbs_alloc_and_load_page(pool_ofs_t ofs, size_t page_size,
                                   size_t load_size) = 0;

    /*
     *   Delete memory allocated by vmpbs_alloc_and_load_page().  The pool
     *   will call this for each page previously allocated.  'page_size'
     *   is the normal page size in bytes for the entire pool.  
     */
    virtual void vmpbs_free_page(const char *mem, pool_ofs_t ofs,
                                 size_t page_size) = 0;

    /*
     *   Given a starting offset, load the page into the given memory,
     *   which is allocated and managed by the caller.  page_size is the
     *   normal page size in bytes, and load_size is the actual number of
     *   bytes to be loaded (this will be the value previously returned by
     *   vmpbs_get_page_size for the page).
     *   
     *   This should throw an exception if an error occurs.  
     */
    virtual void vmpbs_load_page(pool_ofs_t ofs, size_t page_size,
                                 size_t load_size, char *mem) = 0;

    /*
     *   Determine if my pages are writable.  Returns true if so, false if
     *   not.  If the pool pages are directly mapped to the underlying
     *   data file, this should return false.  For example, an
     *   implementation for a palm-top computer without an external
     *   storage device might simply store the image file directly in
     *   memory, and the backing store would map directly onto this memory
     *   so that the original copy of the image file in memory can be used
     *   as the loaded version as well.  In such cases, the backing store
     *   should certainly not be writable.  For an implementation that
     *   copies data from an external storage device (typically a hard
     *   disk), writing to the backing store copy would cause no change to
     *   the original image file data, hence this can return true in such
     *   cases.  
     */
    virtual int vmpbs_is_writable() { return FALSE; }
};


/* ------------------------------------------------------------------------ */
/*
 *   Base constant memory pool class 
 */
class CVmPool
{
public:
    CVmPool() { }
    virtual ~CVmPool() { }

    /*
     *   Get the dynamic data manager for the pool.  If the pool supports
     *   dynamic data, it should return a non-null pointer.  If the pool
     *   doesn't support dynamic data, it should return null.  
     */
    virtual class CVmPoolDynamic *get_dynamic_ifc() { return 0; }

    /* 
     *   Attach to the given backing store to provide the the page data.  
     */
    virtual void
        attach_backing_store(class CVmPoolBackingStore *backing_store) = 0;

    /* 
     *   Detach from backing store - this must be called before the backing
     *   store object can be deleted.  
     */
    virtual void detach_backing_store() { backing_store_ = 0; }

    /* 
     *   Translate an address from a pool offset to a physical location.
     *   Note that translating an address may invalidate a previously
     *   translated address in a swapping implementation of the pool manager,
     *   so callers should take care to assume only one translated address in
     *   a given pool is valid at a time.
     *   
     *   Because this routine is called extremely frequently, we don't make
     *   it a virtual.  Instead, we depend upon the final subclass to define
     *   the method as a non-virtual, so that it can be in-lined.  This means
     *   that pool object references must all be declared with the final
     *   subclass.  
     */
    /* virtual const char *get_ptr(pool_ofs_t ofs) = 0; */

    /*
     *   Translate an address from a pool offset to a physical location, and
     *   return a writable pointer to the location.  This will fail for any
     *   type of pool implementation that doesn't support writable memory
     *   pointers (for example, the swapping pool doesn't allow write
     *   pointers, because it doesn't keep track of dirty pages when
     *   performing swapping).
     *   
     *   As with get_ptr(), this isn't actually virtual, but is instead to be
     *   defined in each final subclass.  
     */
    /* virtual char *get_writable_ptr(pool_ofs_t ofs) = 0; */

    /* 
     *   Get the page size.  This reflects the size of the pages in the
     *   backing store (usually the image file); this doesn't necessarily
     *   indicate anything about the way we manage the pool memory. 
     */
    size_t get_page_size() const { return page_size_; }

    /* get the number of pages in the pool */
    size_t get_page_count() const;

protected:
    /* 
     *   page size in bytes - this is simply the number of bytes on each page
     *   (each page in the pool has the same number of bytes) 
     */
    size_t page_size_;

    /* backing store */
    class CVmPoolBackingStore *backing_store_;

    /* our single contiguous allocation block */
    char *mem_;
};

/* ------------------------------------------------------------------------ */
/*
 *   "Flat" memory pool.  This type of pool loads all pages into a single
 *   contiguous chunk of memory.  This is suitable for platforms with large
 *   linear memory spaces, such as 32-bit platforms.
 *   
 *   This type of pool does not support dynamic allocation, so it's not
 *   suitable for use in a debugger build or other configurations that
 *   require dynamic allocation of pool space.  
 */
class CVmPoolFlat: public CVmPool
{
public:
    CVmPoolFlat()
    {
        /* we don't have our memory chunk yet */
        mem_ = 0;
    }
    ~CVmPoolFlat();

    /* terminate - we don't need to do anything here */
    void terminate() { }

    /* attach to the backing store - loads all pages */
    void attach_backing_store(class CVmPoolBackingStore *backing_store);

    /* detach from the backing store */
    void detach_backing_store();

    /* 
     *   Translate an address.  Since all of our memory is in one large
     *   contiguous chunk, this is extremely simple: just return the base of
     *   our memory block, offset by the pool offset.  
     */
    inline const char *get_ptr(pool_ofs_t ofs) { return mem_ + ofs; }

    /* we do not support writable pointers */
    inline char *get_writable_ptr(pool_ofs_t ofs) { return 0; }
};

/* ------------------------------------------------------------------------ */
/*
 *   Paged constant pool.
 *   
 *   This type of pool is divided into pages.  A given object must be
 *   entirely contained in a single page.
 *   
 *   Each object is referenced by its address in the constant pool.  An
 *   object address is simply an offset into the pool.  
 */
class CVmPoolPaged: public CVmPool
{
public:
    /* create the pool */
    CVmPoolPaged()
    {
        /* no page slots allocated yet */
        pages_ = 0;
        page_slots_ = 0;
        page_slots_max_ = 0;

        /* we don't have a backing store yet */
        backing_store_ = 0;

        /* we don't know the page size yet */
        page_size_ = 0;
        log2_page_size_ = 0;
    }

    /* 
     *   Delete the pool.  Call our non-virtual termination routine, as we
     *   can't use virtuals in destructors (not in the normal fashion,
     *   anyway).  
     */
    virtual ~CVmPoolPaged() { terminate_nv(); }

    /* delete everything in the pool using our base terminator routine */
    virtual void terminate() { terminate_nv(); }

    /* 
     *   Attach to the given backing store to provide the the page data.  
     */
    virtual void
        attach_backing_store(class CVmPoolBackingStore *backing_store);

protected:
    /* non-virtual termination routine */
    void terminate_nv()
    {
        /* free our page memory */
        delete_page_list();
    }
    
    /* delete our page list, if any */
    void delete_page_list();

    /* allocate or expand the page slot list */
    void alloc_page_slots(size_t slots);
    
    /* 
     *   Calculate which page we need, and the offset within the page, for
     *   a given pool offset.  The page is the offset divided by the page
     *   size; since the page size is a power of two, this is simply a bit
     *   shift by log2(page_size).  The page offset is the remainder after
     *   dividing the offset by the page size; again because the page size
     *   is a power of two, we can calculate this remainder simply by
     *   AND'ing the offset with the page size minus one.  (Using these
     *   shift and mask operations may seem a little obscure, but it's so
     *   much faster on most machines than integer division that we're
     *   willing to be a little obscure in exchange for the performance
     *   gain.)  
     */
    inline size_t get_page_for_ofs(pool_ofs_t ofs) const
    {
        return (size_t)(ofs >> log2_page_size_);
    }

    inline size_t get_ofs_for_ofs(pool_ofs_t ofs) const
    {
        return (size_t)(ofs & (page_size_ - 1));
    }

    /* get the starting offset on the given page */
    pool_ofs_t get_page_start_ofs(size_t pg) const
    {
        return ((pool_ofs_t)pg) << log2_page_size_;
    }

    /*
     *   The page list.  This is an array of CVmPool_pg structures; each
     *   structure keeps track of one page in the pool. 
     *   
     *   The page identified by the first page information structure contains
     *   pool offsets 0 through (page_size - 1); the next contains offsets
     *   page_size through (2*page_size - 1); and so on.  
     */
    CVmPool_pg *pages_;

    /* 
     *   The number of page slots in the page list.  This starts at the
     *   initial page size and can grow dynamically as more pages are added.
     */
    size_t page_slots_;

    /* 
     *   The maximum of allocated pages_ array entries.  This might be larger
     *   than page_slots_, because we sometimes allocate more slots than we
     *   currently need to avoid having to allocate on every new page
     *   addition.  
     */
    size_t page_slots_max_;

    /* log2 of the page size */
    int log2_page_size_;
};


/* ------------------------------------------------------------------------ */
/*
 *   Two-tiered paged pool.  This is similar to the paged pool
 *   implementation, but uses a two-level page table: the first-level page
 *   table containers pointers to the second-level tables, and the
 *   second-level tables contain the pointers to the actual pages.
 *   
 *   This class is not currently used, because the two-level scheme isn't
 *   required in practice for modern machines and is less efficient than the
 *   single-level page table implemented in CVmPoolPaged.  We retain this
 *   two-level code in case it's ever needed, though, because the two-level
 *   scheme might be useful for 16-bit segmented architectures.
 *   
 *   The advantage of the two-level scheme is that it allows very large
 *   memory spaces to be addressable without any single large allocations;
 *   the single-tier paged pool requires a single allocation equal to the
 *   total aggregate memory size divided by the page size times the size of a
 *   page pointer, which could be a fairly large single allocation for an
 *   extremely large aggregate pool size.  However, it doesn't currently
 *   appear that the single-tier paging scheme will impose any limits that
 *   will be encountered in actual practice.  
 */
#if 0

/* number of page information structures in each subarray */
const size_t VMPOOL_SUBARRAY_SIZE = 4096;

class CVmPoolPaged2
{
public:
    /* create the pool */
    CVmPoolPaged2()
    {
        /* no page slots allocated yet */
        pages_ = 0;
        page_slots_ = 0;

        /* we don't have a backing store yet */
        backing_store_ = 0;

        /* we don't know the page size yet */
        page_size_ = 0;
        log2_page_size_ = 0;
    }

    /* delete the pool */
    virtual ~CVmPoolPaged2();

    /* 
     *   Attach to the given backing store to provide the the page data.  
     */
    virtual void
        attach_backing_store(class CVmPoolBackingStore *backing_store);

protected:
    /* delete our page list, if any */
    void delete_page_list();

    /* allocate or expand the page slot list */
    void alloc_page_slots(size_t slots);

    /* 
     *   Calculate which page we need, and the offset within the page, for a
     *   given pool offset.  The page is the offset divided by the page size;
     *   since the page size is a power of two, this is simply a bit shift by
     *   log2(page_size).  The page offset is the remainder after dividing
     *   the offset by the page size; again because the page size is a power
     *   of two, we can calculate this remainder simply by AND'ing the offset
     *   with the page size minus one.  (Using these shift and mask
     *   operations may seem a little obscure, but it's so much faster on
     *   most machines than integer division that we're willing to be a
     *   little obscure in exchange for the performance gain.)  
     */
    inline size_t get_page_for_ofs(pool_ofs_t ofs) const
    {
        return (size_t)(ofs >> log2_page_size_);
    }

    inline size_t get_ofs_for_ofs(pool_ofs_t ofs) const
    {
        return (size_t)(ofs & (page_size_ - 1));
    }

    /* get the starting offset on the given page */
    pool_ofs_t get_page_start_ofs(size_t pg) const
    {
        return ((pool_ofs_t)pg) << log2_page_size_;
    }

    /* get the number of subarrays */
    size_t get_subarray_count() const
        { return ((page_slots_ + VMPOOL_SUBARRAY_SIZE - 1)
                  / VMPOOL_SUBARRAY_SIZE); }

    /* get the page information structure for a given index */
    inline CVmPool_pg *get_page_info(size_t idx) const
        { return &(pages_[idx / VMPOOL_SUBARRAY_SIZE]
                   [idx % VMPOOL_SUBARRAY_SIZE]); }

    /*
     *   The page list.  Each entry in this array is a subarray containing
     *   VMPOOL_SUBARRAY_SIZE page information structures, each of contains
     *   information on a page.  Conceptually, the two-tiered array forms a
     *   single array; we keep two levels of arrays to accommodate 16-bit
     *   machines where a single large could be too large for a single 64k
     *   segment.
     *   
     *   The page identified by the first page information structure contains
     *   pool offsets 0 through (page_size - 1); the next contains offsets
     *   page_size through (2*page_size - 1); and so on.  
     */
    CVmPool_pg **pages_;

    /* 
     *   The number of slots allocated in the page list.  This starts at
     *   the initial page size and can grow dynamically as more pages are
     *   added. 
     */
    size_t page_slots_;

    /* log2 of the page size */
    int log2_page_size_;
};
#endif /* 0 */

/* ------------------------------------------------------------------------ */
/*
 *   Dynamic pool manager interface.  This is an abstract interface that
 *   provides a way to create new pool objects dynamically, and later
 *   delete those objects.
 *   
 *   Some types of pools support this interface, others do not.  
 */

/*
 *   Dynamic pool object handle.  Each object in a dynamic pool is
 *   identified by an object handle.  When the dynpool_compress() method
 *   is called in the dynamic pool interface, the pool addresses of
 *   objects can change.  
 */
class CVmPoolDynObj
{
public:
    CVmPoolDynObj(pool_ofs_t ofs, size_t len)
    {
        /* remember my location and size */
        ofs_ = ofs;
        len_ = len;

        /* not in a list yet */
        nxt_ = prv_ = 0;

        /* presume it's in use */
        is_free_ = FALSE;
    }
    
    /* get/set the current pool address of this object */
    pool_ofs_t get_ofs() const { return ofs_; }
    void set_ofs(pool_ofs_t ofs) { ofs_ = ofs; }

    /* get/set my length */
    size_t get_len() const { return len_; }
    void set_len(size_t len) { len_ = len; }

    /* get/set the next object in the list */
    CVmPoolDynObj *get_next() const { return nxt_; }
    void set_next(CVmPoolDynObj *obj) { nxt_ = obj; }

    /* get/set the previous object in the list */
    CVmPoolDynObj *get_prev() const { return prv_; }
    void set_prev(CVmPoolDynObj *obj) { prv_ = obj; }

    /* get/set the 'free' flag */
    int is_free() const { return is_free_; }
    void set_free(int f) { is_free_ = f; }

private:
    /* my pool address */
    pool_ofs_t ofs_;

    /* my length */
    size_t len_;

    /* next/previous dynamic object in the list */
    CVmPoolDynObj *nxt_;
    CVmPoolDynObj *prv_;

    /* flag: this object's pool space is free */
    uint is_free_ : 1;
};

/*
 *   dynamic pool manager interface 
 */
class CVmPoolDynamic
{
public:
    /* 
     *   Allocate a new object in the pool.  Returns a non-null object
     *   handle on success, or zero on failure.  This can fail for
     *   different reasons: the object might be too large to fit in a
     *   single pool page, or there might be insufficient physical memory
     *   available.  
     */
    virtual CVmPoolDynObj *dynpool_alloc(size_t len) = 0;

    /*
     *   Delete an object in the pool. 
     */
    virtual void dynpool_delete(CVmPoolDynObj *obj) = 0;

    /*
     *   Compress the pool.  To the extent possible, rearranges the
     *   dynamic objects in the pool to remove space left vacant by
     *   deleted objects.  When this is called, the addresses of pool
     *   objects can change; this is the only time that addresses can
     *   change.  This should be called after each batch of deletions to
     *   ensure that pool space is not wasted.  (Deleting an object
     *   doesn't automatically compress the pool, so that a single
     *   compression pass can be made after a batch of deletions.)  
     */
    virtual void dynpool_compress() = 0;
};

/* ------------------------------------------------------------------------ */
/*
 *   In-memory pool implementation.  This pool implementation pre-loads
 *   all available pages in the pool and keeps the complete pool in memory
 *   at all times.  
 */
class CVmPoolInMem: public CVmPoolPaged, public CVmPoolDynamic
{
public:
    CVmPoolInMem()
    {
        /* no pages yet -> no dynamic pages */
        first_dyn_page_ = 0;

        /* no dynamic objects yet */
        dyn_head_ = dyn_tail_ = 0;
    }

    /* 
     *   delete - call our non-virtual terminator (use the non-virtual
     *   version, as this will just do our local termination; since we'll
     *   implicitly inherit the base class destructor, we don't want to
     *   explicitly inherit its termination as well) 
     */
    ~CVmPoolInMem() { terminate_nv(); }

    /* terminate */
    void terminate()
    {
        /* call our own non-virtual termination routine */
        terminate_nv();

        /* inherit our base class handling */
        CVmPoolPaged::terminate();
    }

    /* I provide a dynamic pool interface */
    virtual class CVmPoolDynamic *get_dynamic_ifc() { return this; }

    /* attach to the backing store - loads all pages */
    void attach_backing_store(class CVmPoolBackingStore *backing_store);

    /* detach from the backing store */
    void detach_backing_store();

    /* 
     *   translate an address - since the pool is always in memory, we can
     *   translate an address simply by doing the arithmetic and finding
     *   the needed page, which is always loaded 
     */
    inline const char *get_ptr(pool_ofs_t ofs)
    {
        /* translate the address through our page array */
        return (pages_[get_page_for_ofs(ofs)].mem + get_ofs_for_ofs(ofs));
    }

    /* 
     *   get a writable pointer - we allow write pointers as long as the
     *   backing store does 
     */
    inline char *get_writable_ptr(pool_ofs_t ofs)
    {
        /* 
         *   If the backing store allows writing to its pages, allow
         *   writing.  In any case, if the offset is in a dynamic page, we
         *   can always write to it, regardless of backing store policy,
         *   because we allocate and control the dynamic pages ourselves.  
         */
        if (backing_store_->vmpbs_is_writable()
            || get_page_for_ofs(ofs) >= first_dyn_page_)
        {
            /* 
             *   the backing store memory is writable - return a writable
             *   version of the normal pointer to this memory 
             */
            return (char *)get_ptr(ofs);
        }
        else
        {
            /* the backing store memory is non-writable - return failure */
            return 0;
        }
    }

    /* 
     *   dynamic pool interface 
     */

    /* allocate a dynamic object */
    virtual CVmPoolDynObj *dynpool_alloc(size_t len);

    /* delete a dyanmic object */
    virtual void dynpool_delete(CVmPoolDynObj *obj);

    /* compress the dynamic portion of the pool */
    virtual void dynpool_compress();

private:
    /* non-virtual termination */
    void terminate_nv();

    /* free any pages we allocated from the backing store */
    void free_backing_pages();

    /* add a dynamic handle at the end of the list */
    void append_dyn(CVmPoolDynObj *obj);

    /* insert a dynamic handle after the given dynamic handle */
    void insert_dyn(CVmPoolDynObj *obj, CVmPoolDynObj *new_obj);

    /* unlink a dynamic handle from the list */
    void unlink_dyn(CVmPoolDynObj *obj);

    /* 
     *   First dynamically-allocated page index - all pages from this page
     *   to the last page are dynamic.  If this page index is equal to the
     *   total number of pages, there are no dynamic pages, since this
     *   index refers to an invalid page.  
     */
    size_t first_dyn_page_;

    /* head and tail of list of dynamic pool objects */
    CVmPoolDynObj *dyn_head_;
    CVmPoolDynObj *dyn_tail_;
};

#endif /* VMPOOL_H */