util/manibuilder

/******************************************************************************
 * arch/x86/mm/shadow/common.c
 *
 * Shadow code that does not need to be multiply compiled.
 * Parts of this code are Copyright (c) 2006 by XenSource Inc.
 * Parts of this code are Copyright (c) 2006 by Michael A Fetterman
 * Parts based on earlier work by Michael A Fetterman, Ian Pratt et al.
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <xen/config.h>
#include <xen/types.h>
#include <xen/mm.h>
#include <xen/trace.h>
#include <xen/sched.h>
#include <xen/perfc.h>
#include <xen/irq.h>
#include <xen/domain_page.h>
#include <xen/guest_access.h>
#include <xen/keyhandler.h>
#include <asm/event.h>
#include <asm/page.h>
#include <asm/current.h>
#include <asm/flushtlb.h>
#include <asm/shadow.h>
#include <xen/numa.h>
#include "private.h"

DEFINE_PER_CPU(uint32_t,trace_shadow_path_flags);

/* Set up the shadow-specific parts of a domain struct at start of day.
 * Called for every domain from arch_domain_create() */
void shadow_domain_init(struct domain *d, unsigned int domcr_flags)
{
    shadow_lock_init(d);
    INIT_PAGE_LIST_HEAD(&d->arch.paging.shadow.freelist);
    INIT_PAGE_LIST_HEAD(&d->arch.paging.shadow.pinned_shadows);

    /* Use shadow pagetables for log-dirty support */
    paging_log_dirty_init(d, shadow_enable_log_dirty, 
                          shadow_disable_log_dirty, shadow_clean_dirty_bitmap);

#if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC)
    d->arch.paging.shadow.oos_active = 0;
    d->arch.paging.shadow.oos_off = (domcr_flags & DOMCRF_oos_off) ?  1 : 0;
#endif
    d->arch.paging.shadow.pagetable_dying_op = 0;
}

/* Setup the shadow-specfic parts of a vcpu struct. Note: The most important
 * job is to initialize the update_paging_modes() function pointer, which is
 * used to initialized the rest of resources. Therefore, it really does not
 * matter to have v->arch.paging.mode pointing to any mode, as long as it can
 * be compiled.
 */
void shadow_vcpu_init(struct vcpu *v)
{
#if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC)
    int i, j;

    for ( i = 0; i < SHADOW_OOS_PAGES; i++ )
    {
        v->arch.paging.shadow.oos[i] = _mfn(INVALID_MFN);
        v->arch.paging.shadow.oos_snapshot[i] = _mfn(INVALID_MFN);
        for ( j = 0; j < SHADOW_OOS_FIXUPS; j++ )
            v->arch.paging.shadow.oos_fixup[i].smfn[j] = _mfn(INVALID_MFN);
    }
#endif

    v->arch.paging.mode = &SHADOW_INTERNAL_NAME(sh_paging_mode, 3);
}

#if SHADOW_AUDIT
int shadow_audit_enable = 0;

static void shadow_audit_key(unsigned char key)
{
    shadow_audit_enable = !shadow_audit_enable;
    printk("%s shadow_audit_enable=%d\n",
           __func__, shadow_audit_enable);
}

static struct keyhandler shadow_audit_keyhandler = {
    .u.fn = shadow_audit_key,
    .desc = "toggle shadow audits"
};

static int __init shadow_audit_key_init(void)
{
    register_keyhandler('O', &shadow_audit_keyhandler);
    return 0;
}
__initcall(shadow_audit_key_init);
#endif /* SHADOW_AUDIT */

int _shadow_mode_refcounts(struct domain *d)
{
    return shadow_mode_refcounts(d);
}


/**************************************************************************/
/* x86 emulator support for the shadow code
 */

struct segment_register *hvm_get_seg_reg(
    enum x86_segment seg, struct sh_emulate_ctxt *sh_ctxt)
{
    struct segment_register *seg_reg = &sh_ctxt->seg_reg[seg];
    if ( !__test_and_set_bit(seg, &sh_ctxt->valid_seg_regs) )
        hvm_get_segment_register(current, seg, seg_reg);
    return seg_reg;
}

static int hvm_translate_linear_addr(
    enum x86_segment seg,
    unsigned long offset,
    unsigned int bytes,
    enum hvm_access_type access_type,
    struct sh_emulate_ctxt *sh_ctxt,
    unsigned long *paddr)
{
    struct segment_register *reg = hvm_get_seg_reg(seg, sh_ctxt);
    int okay;

    okay = hvm_virtual_to_linear_addr(
        seg, reg, offset, bytes, access_type, sh_ctxt->ctxt.addr_size, paddr);

    if ( !okay )
    {
        hvm_inject_exception(TRAP_gp_fault, 0, 0);
        return X86EMUL_EXCEPTION;
    }

    return 0;
}

static int
hvm_read(enum x86_segment seg,
         unsigned long offset,
         void *p_data,
         unsigned int bytes,
         enum hvm_access_type access_type,
         struct sh_emulate_ctxt *sh_ctxt)
{
    unsigned long addr;
    int rc;

    rc = hvm_translate_linear_addr(
        seg, offset, bytes, access_type, sh_ctxt, &addr);
    if ( rc )
        return rc;

    if ( access_type == hvm_access_insn_fetch )
        rc = hvm_fetch_from_guest_virt(p_data, addr, bytes, 0);
    else
        rc = hvm_copy_from_guest_virt(p_data, addr, bytes, 0);

    switch ( rc )
    {
    case HVMCOPY_okay:
        return X86EMUL_OKAY;
    case HVMCOPY_bad_gva_to_gfn:
        return X86EMUL_EXCEPTION;
    case HVMCOPY_bad_gfn_to_mfn:
    case HVMCOPY_unhandleable:
        return X86EMUL_UNHANDLEABLE;
    case HVMCOPY_gfn_paged_out:
    case HVMCOPY_gfn_shared:
        return X86EMUL_RETRY;
    }

    BUG();
    return X86EMUL_UNHANDLEABLE;
}

static int
hvm_emulate_read(enum x86_segment seg,
                 unsigned long offset,
                 void *p_data,
                 unsigned int bytes,
                 struct x86_emulate_ctxt *ctxt)
{
    if ( !is_x86_user_segment(seg) )
        return X86EMUL_UNHANDLEABLE;
    return hvm_read(seg, offset, p_data, bytes, hvm_access_read,
                    container_of(ctxt, struct sh_emulate_ctxt, ctxt));
}

static int
hvm_emulate_insn_fetch(enum x86_segment seg,
                       unsigned long offset,
                       void *p_data,
                       unsigned int bytes,
                       struct x86_emulate_ctxt *ctxt)
{
    struct sh_emulate_ctxt *sh_ctxt =
        container_of(ctxt, struct sh_emulate_ctxt, ctxt);
    unsigned int insn_off = offset - sh_ctxt->insn_buf_eip;

    ASSERT(seg == x86_seg_cs);

    /* Fall back if requested bytes are not in the prefetch cache. */
    if ( unlikely((insn_off + bytes) > sh_ctxt->insn_buf_bytes) )
        return hvm_read(seg, offset, p_data, bytes,
                        hvm_access_insn_fetch, sh_ctxt);

    /* Hit the cache. Simple memcpy. */
    memcpy(p_data, &sh_ctxt->insn_buf[insn_off], bytes);
    return X86EMUL_OKAY;
}

static int
hvm_emulate_write(enum x86_segment seg,
                  unsigned long offset,
                  void *p_data,
                  unsigned int bytes,
                  struct x86_emulate_ctxt *ctxt)
{
    struct sh_emulate_ctxt *sh_ctxt =
        container_of(ctxt, struct sh_emulate_ctxt, ctxt);
    struct vcpu *v = current;
    unsigned long addr;
    int rc;

    if ( !is_x86_user_segment(seg) )
        return X86EMUL_UNHANDLEABLE;

    /* How many emulations could we save if we unshadowed on stack writes? */
    if ( seg == x86_seg_ss )
        perfc_incr(shadow_fault_emulate_stack);

    rc = hvm_translate_linear_addr(
        seg, offset, bytes, hvm_access_write, sh_ctxt, &addr);
    if ( rc )
        return rc;

    return v->arch.paging.mode->shadow.x86_emulate_write(
        v, addr, p_data, bytes, sh_ctxt);
}

static int 
hvm_emulate_cmpxchg(enum x86_segment seg,
                    unsigned long offset,
                    void *p_old,
                    void *p_new,
                    unsigned int bytes,
                    struct x86_emulate_ctxt *ctxt)
{
    struct sh_emulate_ctxt *sh_ctxt =
        container_of(ctxt, struct sh_emulate_ctxt, ctxt);
    struct vcpu *v = current;
    unsigned long addr, old[2], new[2];
    int rc;

    if ( !is_x86_user_segment(seg) )
        return X86EMUL_UNHANDLEABLE;

    rc = hvm_translate_linear_addr(
        seg, offset, bytes, hvm_access_write, sh_ctxt, &addr);
    if ( rc )
        return rc;

    old[0] = new[0] = 0;
    memcpy(old, p_old, bytes);
    memcpy(new, p_new, bytes);

    if ( bytes <= sizeof(long) )
        return v->arch.paging.mode->shadow.x86_emulate_cmpxchg(
            v, addr, old[0], new[0], bytes, sh_ctxt);

#ifdef __i386__
    if ( bytes == 8 )
        return v->arch.paging.mode->shadow.x86_emulate_cmpxchg8b(
            v, addr, old[0], old[1], new[0], new[1], sh_ctxt);
#endif

    return X86EMUL_UNHANDLEABLE;
}

static const struct x86_emulate_ops hvm_shadow_emulator_ops = {
    .read       = hvm_emulate_read,
    .insn_fetch = hvm_emulate_insn_fetch,
    .write      = hvm_emulate_write,
    .cmpxchg    = hvm_emulate_cmpxchg,
};

static int
pv_emulate_read(enum x86_segment seg,
                unsigned long offset,
                void *p_data,
                unsigned int bytes,
                struct x86_emulate_ctxt *ctxt)
{
    unsigned int rc;

    if ( !is_x86_user_segment(seg) )
        return X86EMUL_UNHANDLEABLE;

    if ( (rc = copy_from_user(p_data, (void *)offset, bytes)) != 0 )
    {
        propagate_page_fault(offset + bytes - rc, 0); /* read fault */
        return X86EMUL_EXCEPTION;
    }

    return X86EMUL_OKAY;
}

static int
pv_emulate_write(enum x86_segment seg,
                 unsigned long offset,
                 void *p_data,
                 unsigned int bytes,
                 struct x86_emulate_ctxt *ctxt)
{
    struct sh_emulate_ctxt *sh_ctxt =
        container_of(ctxt, struct sh_emulate_ctxt, ctxt);
    struct vcpu *v = current;
    if ( !is_x86_user_segment(seg) )
        return X86EMUL_UNHANDLEABLE;
    return v->arch.paging.mode->shadow.x86_emulate_write(
        v, offset, p_data, bytes, sh_ctxt);
}

static int 
pv_emulate_cmpxchg(enum x86_segment seg,
                   unsigned long offset,
                   void *p_old,
                   void *p_new,
                   unsigned int bytes,
                   struct x86_emulate_ctxt *ctxt)
{
    struct sh_emulate_ctxt *sh_ctxt =
        container_of(ctxt, struct sh_emulate_ctxt, ctxt);
    unsigned long old[2], new[2];
    struct vcpu *v = current;

    if ( !is_x86_user_segment(seg) )
        return X86EMUL_UNHANDLEABLE;

    old[0] = new[0] = 0;
    memcpy(old, p_old, bytes);
    memcpy(new, p_new, bytes);

    if ( bytes <= sizeof(long) )
        return v->arch.paging.mode->shadow.x86_emulate_cmpxchg(
            v, offset, old[0], new[0], bytes, sh_ctxt);

#ifdef __i386__
    if ( bytes == 8 )
        return v->arch.paging.mode->shadow.x86_emulate_cmpxchg8b(
            v, offset, old[0], old[1], new[0], new[1], sh_ctxt);
#endif

    return X86EMUL_UNHANDLEABLE;
}

static const struct x86_emulate_ops pv_shadow_emulator_ops = {
    .read       = pv_emulate_read,
    .insn_fetch = pv_emulate_read,
    .write      = pv_emulate_write,
    .cmpxchg    = pv_emulate_cmpxchg,
};

const struct x86_emulate_ops *shadow_init_emulation(
    struct sh_emulate_ctxt *sh_ctxt, struct cpu_user_regs *regs)
{
    struct segment_register *creg, *sreg;
    struct vcpu *v = current;
    unsigned long addr;

    sh_ctxt->ctxt.regs = regs;
    sh_ctxt->ctxt.force_writeback = 0;

    if ( !is_hvm_vcpu(v) )
    {
        sh_ctxt->ctxt.addr_size = sh_ctxt->ctxt.sp_size = BITS_PER_LONG;
        return &pv_shadow_emulator_ops;
    }

    /* Segment cache initialisation. Primed with CS. */
    sh_ctxt->valid_seg_regs = 0;
    creg = hvm_get_seg_reg(x86_seg_cs, sh_ctxt);

    /* Work out the emulation mode. */
    if ( hvm_long_mode_enabled(v) && creg->attr.fields.l )
    {
        sh_ctxt->ctxt.addr_size = sh_ctxt->ctxt.sp_size = 64;
    }
    else
    {
        sreg = hvm_get_seg_reg(x86_seg_ss, sh_ctxt);
        sh_ctxt->ctxt.addr_size = creg->attr.fields.db ? 32 : 16;
        sh_ctxt->ctxt.sp_size   = sreg->attr.fields.db ? 32 : 16;
    }

    /* Attempt to prefetch whole instruction. */
    sh_ctxt->insn_buf_eip = regs->eip;
    sh_ctxt->insn_buf_bytes =
        (!hvm_translate_linear_addr(
            x86_seg_cs, regs->eip, sizeof(sh_ctxt->insn_buf),
            hvm_access_insn_fetch, sh_ctxt, &addr) &&
         !hvm_fetch_from_guest_virt_nofault(
             sh_ctxt->insn_buf, addr, sizeof(sh_ctxt->insn_buf), 0))
        ? sizeof(sh_ctxt->insn_buf) : 0;

    return &hvm_shadow_emulator_ops;
}

/* Update an initialized emulation context to prepare for the next 
 * instruction */
void shadow_continue_emulation(struct sh_emulate_ctxt *sh_ctxt, 
                               struct cpu_user_regs *regs)
{
    struct vcpu *v = current;
    unsigned long addr, diff;

    /* We don't refetch the segment bases, because we don't emulate
     * writes to segment registers */

    if ( is_hvm_vcpu(v) )
    {
        diff = regs->eip - sh_ctxt->insn_buf_eip;
        if ( diff > sh_ctxt->insn_buf_bytes )
        {
            /* Prefetch more bytes. */
            sh_ctxt->insn_buf_bytes =
                (!hvm_translate_linear_addr(
                    x86_seg_cs, regs->eip, sizeof(sh_ctxt->insn_buf),
                    hvm_access_insn_fetch, sh_ctxt, &addr) &&
                 !hvm_fetch_from_guest_virt_nofault(
                     sh_ctxt->insn_buf, addr, sizeof(sh_ctxt->insn_buf), 0))
                ? sizeof(sh_ctxt->insn_buf) : 0;
            sh_ctxt->insn_buf_eip = regs->eip;
        }
    }
}
 

#if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC)
/**************************************************************************/
/* Out-of-sync shadows. */ 

/* From time to time, we let a shadowed pagetable page go out of sync 
 * with its shadow: the guest is allowed to write directly to the page, 
 * and those writes are not synchronously reflected in the shadow.
 * This lets us avoid many emulations if the guest is writing a lot to a 
 * pagetable, but it relaxes a pretty important invariant in the shadow 
 * pagetable design.  Therefore, some rules:
 *
 * 1. Only L1 pagetables may go out of sync: any page that is shadowed
 *    at at higher level must be synchronously updated.  This makes
 *    using linear shadow pagetables much less dangerous.
 *    That means that: (a) unsyncing code needs to check for higher-level
 *    shadows, and (b) promotion code needs to resync.
 * 
 * 2. All shadow operations on a guest page require the page to be brought
 *    back into sync before proceeding.  This must be done under the
 *    shadow lock so that the page is guaranteed to remain synced until
 *    the operation completes.
 *
 *    Exceptions to this rule: the pagefault and invlpg handlers may 
 *    update only one entry on an out-of-sync page without resyncing it. 
 *
 * 3. Operations on shadows that do not start from a guest page need to
 *    be aware that they may be handling an out-of-sync shadow.
 *
 * 4. Operations that do not normally take the shadow lock (fast-path 
 *    #PF handler, INVLPG) must fall back to a locking, syncing version 
 *    if they see an out-of-sync table. 
 *
 * 5. Operations corresponding to guest TLB flushes (MOV CR3, INVLPG)
 *    must explicitly resync all relevant pages or update their
 *    shadows.
 *
 * Currently out-of-sync pages are listed in a simple open-addressed
 * hash table with a second chance (must resist temptation to radically
 * over-engineer hash tables...)  The virtual address of the access
 * which caused us to unsync the page is also kept in the hash table, as
 * a hint for finding the writable mappings later.
 *
 * We keep a hash per vcpu, because we want as much as possible to do
 * the re-sync on the save vcpu we did the unsync on, so the VA hint
 * will be valid.
 */


#if SHADOW_AUDIT & SHADOW_AUDIT_ENTRIES_FULL
static void sh_oos_audit(struct domain *d) 
{
    int idx, expected_idx, expected_idx_alt;
    struct page_info *pg;
    struct vcpu *v;
    
    for_each_vcpu(d, v) 
    {
        for ( idx = 0; idx < SHADOW_OOS_PAGES; idx++ )
        {
            mfn_t *oos = v->arch.paging.shadow.oos;
            if ( !mfn_valid(oos[idx]) )
                continue;
            
            expected_idx = mfn_x(oos[idx]) % SHADOW_OOS_PAGES;
            expected_idx_alt = ((expected_idx + 1) % SHADOW_OOS_PAGES);
            if ( idx != expected_idx && idx != expected_idx_alt )
            {
                printk("%s: idx %d contains gmfn %lx, expected at %d or %d.\n",
                       __func__, idx, mfn_x(oos[idx]), 
                       expected_idx, expected_idx_alt);
                BUG();
            }
            pg = mfn_to_page(oos[idx]);
            if ( !(pg->count_info & PGC_page_table) )
            {
                printk("%s: idx %x gmfn %lx not a pt (count %"PRIx32")\n",
                       __func__, idx, mfn_x(oos[idx]), pg->count_info);
                BUG();
            }
            if ( !(pg->shadow_flags & SHF_out_of_sync) )
            {
                printk("%s: idx %x gmfn %lx not marked oos (flags %lx)\n",
                       __func__, idx, mfn_x(oos[idx]), pg->shadow_flags);
                BUG();
            }
            if ( (pg->shadow_flags & SHF_page_type_mask & ~SHF_L1_ANY) )
            {
                printk("%s: idx %x gmfn %lx shadowed as non-l1 (flags %lx)\n",
                       __func__, idx, mfn_x(oos[idx]), pg->shadow_flags);
                BUG();
            }
        }
    }
}
#endif

#if SHADOW_AUDIT & SHADOW_AUDIT_ENTRIES
void oos_audit_hash_is_present(struct domain *d, mfn_t gmfn) 
{
    int idx;
    struct vcpu *v;
    mfn_t *oos;

    ASSERT(mfn_is_out_of_sync(gmfn));
    
    for_each_vcpu(d, v) 
    {
        oos = v->arch.paging.shadow.oos;
        idx = mfn_x(gmfn) % SHADOW_OOS_PAGES;
        if ( mfn_x(oos[idx]) != mfn_x(gmfn) )
            idx = (idx + 1) % SHADOW_OOS_PAGES;
        
        if ( mfn_x(oos[idx]) == mfn_x(gmfn) )
            return;
    }

    SHADOW_ERROR("gmfn %lx marked OOS but not in hash table\n", mfn_x(gmfn));
    BUG();
}
#endif

/* Update the shadow, but keep the page out of sync. */
static inline void _sh_resync_l1(struct vcpu *v, mfn_t gmfn, mfn_t snpmfn)
{
    struct page_info *pg = mfn_to_page(gmfn);

    ASSERT(mfn_valid(gmfn));
    ASSERT(page_is_out_of_sync(pg));

    /* Call out to the appropriate per-mode resyncing function */
    if ( pg->shadow_flags & SHF_L1_32 )
        SHADOW_INTERNAL_NAME(sh_resync_l1, 2)(v, gmfn, snpmfn);
    else if ( pg->shadow_flags & SHF_L1_PAE )
        SHADOW_INTERNAL_NAME(sh_resync_l1, 3)(v, gmfn, snpmfn);
#if CONFIG_PAGING_LEVELS >= 4
    else if ( pg->shadow_flags & SHF_L1_64 )
        SHADOW_INTERNAL_NAME(sh_resync_l1, 4)(v, gmfn, snpmfn);
#endif
}


/*
 * Fixup arrays: We limit the maximum number of writable mappings to
 * SHADOW_OOS_FIXUPS and store enough information to remove them
 * quickly on resync.
 */

static inline int oos_fixup_flush_gmfn(struct vcpu *v, mfn_t gmfn,
                                       struct oos_fixup *fixup)
{
    int i;
    for ( i = 0; i < SHADOW_OOS_FIXUPS; i++ )
    {
        if ( mfn_x(fixup->smfn[i]) != INVALID_MFN )
        {
            sh_remove_write_access_from_sl1p(v, gmfn,
                                             fixup->smfn[i], 
                                             fixup->off[i]);
            fixup->smfn[i] = _mfn(INVALID_MFN);
        }
    }

    /* Always flush the TLBs. See comment on oos_fixup_add(). */
    return 1;
}

void oos_fixup_add(struct vcpu *v, mfn_t gmfn,
                   mfn_t smfn,  unsigned long off)
{
    int idx, next;
    mfn_t *oos;
    struct oos_fixup *oos_fixup;
    struct domain *d = v->domain;

    perfc_incr(shadow_oos_fixup_add);
    
    for_each_vcpu(d, v) 
    {
        oos = v->arch.paging.shadow.oos;
        oos_fixup = v->arch.paging.shadow.oos_fixup;
        idx = mfn_x(gmfn) % SHADOW_OOS_PAGES;
        if ( mfn_x(oos[idx]) != mfn_x(gmfn) )
            idx = (idx + 1) % SHADOW_OOS_PAGES;
        if ( mfn_x(oos[idx]) == mfn_x(gmfn) )
        {
            int i;
            for ( i = 0; i < SHADOW_OOS_FIXUPS; i++ )
            {
                if ( mfn_valid(oos_fixup[idx].smfn[i])
                     && (mfn_x(oos_fixup[idx].smfn[i]) == mfn_x(smfn))
                     && (oos_fixup[idx].off[i] == off) )
                    return;
            }

            next = oos_fixup[idx].next;

            if ( mfn_x(oos_fixup[idx].smfn[next]) != INVALID_MFN )
            {
                TRACE_SHADOW_PATH_FLAG(TRCE_SFLAG_OOS_FIXUP_EVICT);

                /* Reuse this slot and remove current writable mapping. */
                sh_remove_write_access_from_sl1p(v, gmfn, 
                                                 oos_fixup[idx].smfn[next],
                                                 oos_fixup[idx].off[next]);
                perfc_incr(shadow_oos_fixup_evict);
                /* We should flush the TLBs now, because we removed a
                   writable mapping, but since the shadow is already
                   OOS we have no problem if another vcpu write to
                   this page table. We just have to be very careful to
                   *always* flush the tlbs on resync. */
            }

            oos_fixup[idx].smfn[next] = smfn;
            oos_fixup[idx].off[next] = off;
            oos_fixup[idx].next = (next + 1) % SHADOW_OOS_FIXUPS;

            TRACE_SHADOW_PATH_FLAG(TRCE_SFLAG_OOS_FIXUP_ADD);
            return;
        }
    }

    SHADOW_ERROR("gmfn %lx was OOS but not in hash table\n", mfn_x(gmfn));
    BUG();
}

static int oos_remove_write_access(struct vcpu *v, mfn_t gmfn,
                                   struct oos_fixup *fixup)
{
    int ftlb = 0;

    ftlb |= oos_fixup_flush_gmfn(v, gmfn, fixup);

    switch ( sh_remove_write_access(v, gmfn, 0, 0) )
    {
    default:
    case 0:
        break;

    case 1:
        ftlb |= 1;
        break;

    case -1:
        /* An unfindable writeable typecount has appeared, probably via a
         * grant table entry: can't shoot the mapping, so try to unshadow 
         * the page.  If that doesn't work either, the guest is granting
         * his pagetables and must be killed after all.
         * This will flush the tlb, so we can return with no worries. */
        sh_remove_shadows(v, gmfn, 0 /* Be thorough */, 1 /* Must succeed */);
        return 1;
    }

    if ( ftlb )
        flush_tlb_mask(&v->domain->domain_dirty_cpumask);

    return 0;
}


static inline void trace_resync(int event, mfn_t gmfn)
{
    if ( tb_init_done )
    {
        /* Convert gmfn to gfn */
        unsigned long gfn = mfn_to_gfn(current->domain, gmfn);
        __trace_var(event, 0/*!tsc*/, sizeof(gfn), &gfn);
    }
}

/* Pull all the entries on an out-of-sync page back into sync. */
static void _sh_resync(struct vcpu *v, mfn_t gmfn,
                       struct oos_fixup *fixup, mfn_t snp)
{
    struct page_info *pg = mfn_to_page(gmfn);

    ASSERT(shadow_locked_by_me(v->domain));
    ASSERT(mfn_is_out_of_sync(gmfn));
    /* Guest page must be shadowed *only* as L1 when out of sync. */
    ASSERT(!(mfn_to_page(gmfn)->shadow_flags & SHF_page_type_mask 
             & ~SHF_L1_ANY));
    ASSERT(!sh_page_has_multiple_shadows(mfn_to_page(gmfn)));

    SHADOW_PRINTK("d=%d, v=%d, gmfn=%05lx\n",
                  v->domain->domain_id, v->vcpu_id, mfn_x(gmfn));

    /* Need to pull write access so the page *stays* in sync. */
    if ( oos_remove_write_access(v, gmfn, fixup) )
    {
        /* Page has been unshadowed. */
        return;
    }

    /* No more writable mappings of this page, please */
    pg->shadow_flags &= ~SHF_oos_may_write;

    /* Update the shadows with current guest entries. */
    _sh_resync_l1(v, gmfn, snp);

    /* Now we know all the entries are synced, and will stay that way */
    pg->shadow_flags &= ~SHF_out_of_sync;
    perfc_incr(shadow_resync);
    trace_resync(TRC_SHADOW_RESYNC_FULL, gmfn);
}


/* Add an MFN to the list of out-of-sync guest pagetables */
static void oos_hash_add(struct vcpu *v, mfn_t gmfn)
{
    int i, idx, oidx, swap = 0;
    void *gptr, *gsnpptr;
    mfn_t *oos = v->arch.paging.shadow.oos;
    mfn_t *oos_snapshot = v->arch.paging.shadow.oos_snapshot;
    struct oos_fixup *oos_fixup = v->arch.paging.shadow.oos_fixup;
    struct oos_fixup fixup = { .next = 0 };
    
    for (i = 0; i < SHADOW_OOS_FIXUPS; i++ )
        fixup.smfn[i] = _mfn(INVALID_MFN);

    idx = mfn_x(gmfn) % SHADOW_OOS_PAGES;
    oidx = idx;

    if ( mfn_valid(oos[idx]) 
         && (mfn_x(oos[idx]) % SHADOW_OOS_PAGES) == idx )
    {
        /* Punt the current occupant into the next slot */
        SWAP(oos[idx], gmfn);
        SWAP(oos_fixup[idx], fixup);
        swap = 1;
        idx = (idx + 1) % SHADOW_OOS_PAGES;
    }
    if ( mfn_valid(oos[idx]) )
   {
        /* Crush the current occupant. */
        _sh_resync(v, oos[idx], &oos_fixup[idx], oos_snapshot[idx]);
        perfc_incr(shadow_unsync_evict);
    }
    oos[idx] = gmfn;
    oos_fixup[idx] = fixup;

    if ( swap )
        SWAP(oos_snapshot[idx], oos_snapshot[oidx]);

    gptr = sh_map_domain_page(oos[oidx]);
    gsnpptr = sh_map_domain_page(oos_snapshot[oidx]);
    memcpy(gsnpptr, gptr, PAGE_SIZE);
    sh_unmap_domain_page(gptr);
    sh_unmap_domain_page(gsnpptr);
}

/* Remove an MFN from the list of out-of-sync guest pagetables */
static void oos_hash_remove(struct vcpu *v, mfn_t gmfn)
{
    int idx;
    mfn_t *oos;
    struct domain *d = v->domain;

    SHADOW_PRINTK("D%dV%d gmfn %lx\n",
                  v->domain->domain_id, v->vcpu_id, mfn_x(gmfn)); 

    for_each_vcpu(d, v) 
    {
        oos = v->arch.paging.shadow.oos;
        idx = mfn_x(gmfn) % SHADOW_OOS_PAGES;
        if ( mfn_x(oos[idx]) != mfn_x(gmfn) )
            idx = (idx + 1) % SHADOW_OOS_PAGES;
        if ( mfn_x(oos[idx]) == mfn_x(gmfn) )
        {
            oos[idx] = _mfn(INVALID_MFN);
            return;
        }
    }

    SHADOW_ERROR("gmfn %lx was OOS but not in hash table\n", mfn_x(gmfn));
    BUG();
}

mfn_t oos_snapshot_lookup(struct vcpu *v, mfn_t gmfn)
{
    int idx;
    mfn_t *oos;
    mfn_t *oos_snapshot;
    struct domain *d = v->domain;
    
    for_each_vcpu(d, v) 
    {
        oos = v->arch.paging.shadow.oos;
        oos_snapshot = v->arch.paging.shadow.oos_snapshot;
        idx = mfn_x(gmfn) % SHADOW_OOS_PAGES;
        if ( mfn_x(oos[idx]) != mfn_x(gmfn) )
            idx = (idx + 1) % SHADOW_OOS_PAGES;
        if ( mfn_x(oos[idx]) == mfn_x(gmfn) )
        {
            return oos_snapshot[idx];
        }
    }

    SHADOW_ERROR("gmfn %lx was OOS but not in hash table\n", mfn_x(gmfn));
    BUG();
    return _mfn(INVALID_MFN);
}

/* Pull a single guest page back into sync */
void sh_resync(struct vcpu *v, mfn_t gmfn)
{
    int idx;
    mfn_t *oos;
    mfn_t *oos_snapshot;
    struct oos_fixup *oos_fixup;
    struct domain *d = v->domain;

    for_each_vcpu(d, v) 
    {
        oos = v->arch.paging.shadow.oos;
        oos_fixup = v->arch.paging.shadow.oos_fixup;
        oos_snapshot = v->arch.paging.shadow.oos_snapshot;
        idx = mfn_x(gmfn) % SHADOW_OOS_PAGES;
        if ( mfn_x(oos[idx]) != mfn_x(gmfn) )
            idx = (idx + 1) % SHADOW_OOS_PAGES;
        
        if ( mfn_x(oos[idx]) == mfn_x(gmfn) )
        {
            _sh_resync(v, gmfn, &oos_fixup[idx], oos_snapshot[idx]);
            oos[idx] = _mfn(INVALID_MFN);
            return;
        }
    }

    SHADOW_ERROR("gmfn %lx was OOS but not in hash table\n", mfn_x(gmfn));
    BUG();
}

/* Figure out whether it's definitely safe not to sync this l1 table,
 * by making a call out to the mode in which that shadow was made. */
static int sh_skip_sync(struct vcpu *v, mfn_t gl1mfn)
{
    struct page_info *pg = mfn_to_page(gl1mfn);
    if ( pg->shadow_flags & SHF_L1_32 )
        return SHADOW_INTERNAL_NAME(sh_safe_not_to_sync, 2)(v, gl1mfn);
    else if ( pg->shadow_flags & SHF_L1_PAE )
        return SHADOW_INTERNAL_NAME(sh_safe_not_to_sync, 3)(v, gl1mfn);
#if CONFIG_PAGING_LEVELS >= 4
    else if ( pg->shadow_flags & SHF_L1_64 )
        return SHADOW_INTERNAL_NAME(sh_safe_not_to_sync, 4)(v, gl1mfn);
#endif
    SHADOW_ERROR("gmfn 0x%lx was OOS but not shadowed as an l1.\n", 
                 mfn_x(gl1mfn));
    BUG();
    return 0; /* BUG() is no longer __attribute__((noreturn)). */
}


/* Pull all out-of-sync pages back into sync.  Pages brought out of sync
 * on other vcpus are allowed to remain out of sync, but their contents
 * will be made safe (TLB flush semantics); pages unsynced by this vcpu
 * are brought back into sync and write-protected.  If skip != 0, we try
 * to avoid resyncing at all if we think we can get away with it. */
void sh_resync_all(struct vcpu *v, int skip, int this, int others, int do_locking)
{
    int idx;
    struct vcpu *other;
    mfn_t *oos = v->arch.paging.shadow.oos;
    mfn_t *oos_snapshot = v->arch.paging.shadow.oos_snapshot;
    struct oos_fixup *oos_fixup = v->arch.paging.shadow.oos_fixup;

    SHADOW_PRINTK("d=%d, v=%d\n", v->domain->domain_id, v->vcpu_id);

    ASSERT(do_locking || shadow_locked_by_me(v->domain));

    if ( !this )
        goto resync_others;

    if ( do_locking )
        shadow_lock(v->domain);

    /* First: resync all of this vcpu's oos pages */
    for ( idx = 0; idx < SHADOW_OOS_PAGES; idx++ ) 
        if ( mfn_valid(oos[idx]) )
        {
            /* Write-protect and sync contents */
            _sh_resync(v, oos[idx], &oos_fixup[idx], oos_snapshot[idx]);
            oos[idx] = _mfn(INVALID_MFN);
        }

    if ( do_locking )
        shadow_unlock(v->domain);

 resync_others:
    if ( !others )
        return;

    /* Second: make all *other* vcpus' oos pages safe. */
    for_each_vcpu(v->domain, other)
    {
        if ( v == other ) 
            continue;

        if ( do_locking )
            shadow_lock(v->domain);

        oos = other->arch.paging.shadow.oos;
        oos_fixup = other->arch.paging.shadow.oos_fixup;
        oos_snapshot = other->arch.paging.shadow.oos_snapshot;

        for ( idx = 0; idx < SHADOW_OOS_PAGES; idx++ ) 
        {
            if ( !mfn_valid(oos[idx]) )
                continue;

            if ( skip )
            {
                /* Update the shadows and leave the page OOS. */
                if ( sh_skip_sync(v, oos[idx]) )
                    continue;
                trace_resync(TRC_SHADOW_RESYNC_ONLY, oos[idx]);
                _sh_resync_l1(other, oos[idx], oos_snapshot[idx]);
            }
            else
            {
                /* Write-protect and sync contents */
                _sh_resync(other, oos[idx], &oos_fixup[idx], oos_snapshot[idx]);
                oos[idx] = _mfn(INVALID_MFN);
            }
        }
        
        if ( do_locking )
            shadow_unlock(v->domain);
    }
}

/* Allow a shadowed page to go out of sync. Unsyncs are traced in
 * multi.c:sh_page_fault() */
int sh_unsync(struct vcpu *v, mfn_t gmfn)
{
    struct page_info *pg;
    
    ASSERT(shadow_locked_by_me(v->domain));

    SHADOW_PRINTK("d=%d, v=%d, gmfn=%05lx\n",
                  v->domain->domain_id, v->vcpu_id, mfn_x(gmfn));

    pg = mfn_to_page(gmfn);
 
    /* Guest page must be shadowed *only* as L1 and *only* once when out
     * of sync.  Also, get out now if it's already out of sync. 
     * Also, can't safely unsync if some vcpus have paging disabled.*/
    if ( pg->shadow_flags & 
         ((SHF_page_type_mask & ~SHF_L1_ANY) | SHF_out_of_sync) 
         || sh_page_has_multiple_shadows(pg)
         || !is_hvm_domain(v->domain)
         || !v->domain->arch.paging.shadow.oos_active )
        return 0;

    pg->shadow_flags |= SHF_out_of_sync|SHF_oos_may_write;
    oos_hash_add(v, gmfn);
    perfc_incr(shadow_unsync);
    TRACE_SHADOW_PATH_FLAG(TRCE_SFLAG_UNSYNC);
    return 1;
}

#endif /* (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC) */


/**************************************************************************/
/* Code for "promoting" a guest page to the point where the shadow code is
 * willing to let it be treated as a guest page table.  This generally
 * involves making sure there are no writable mappings available to the guest
 * for this page.
 */
void shadow_promote(struct vcpu *v, mfn_t gmfn, unsigned int type)
{
    struct page_info *page = mfn_to_page(gmfn);

    ASSERT(mfn_valid(gmfn));

#if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC) 
    /* Is the page already shadowed and out of sync? */
    if ( page_is_out_of_sync(page) ) 
        sh_resync(v, gmfn);
#endif

    /* We should never try to promote a gmfn that has writeable mappings */
    ASSERT((page->u.inuse.type_info & PGT_type_mask) != PGT_writable_page
           || (page->u.inuse.type_info & PGT_count_mask) == 0
           || v->domain->is_shutting_down);

    /* Is the page already shadowed? */
    if ( !test_and_set_bit(_PGC_page_table, &page->count_info) )
        page->shadow_flags = 0;

    ASSERT(!test_bit(type, &page->shadow_flags));
    set_bit(type, &page->shadow_flags);
    TRACE_SHADOW_PATH_FLAG(TRCE_SFLAG_PROMOTE);
}

void shadow_demote(struct vcpu *v, mfn_t gmfn, u32 type)
{
    struct page_info *page = mfn_to_page(gmfn);

    ASSERT(test_bit(_PGC_page_table, &page->count_info));
    ASSERT(test_bit(type, &page->shadow_flags));

    clear_bit(type, &page->shadow_flags);

    if ( (page->shadow_flags & SHF_page_type_mask) == 0 )
    {
#if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC) 
        /* Was the page out of sync? */
        if ( page_is_out_of_sync(page) ) 
        {
            oos_hash_remove(v, gmfn);
        }
#endif 
        clear_bit(_PGC_page_table, &page->count_info);
    }

    TRACE_SHADOW_PATH_FLAG(TRCE_SFLAG_DEMOTE);
}

/**************************************************************************/
/* Validate a pagetable change from the guest and update the shadows.
 * Returns a bitmask of SHADOW_SET_* flags. */

int
sh_validate_guest_entry(struct vcpu *v, mfn_t gmfn, void *entry, u32 size)
{
    int result = 0;
    struct page_info *page = mfn_to_page(gmfn);

    paging_mark_dirty(v->domain, mfn_x(gmfn));
    
    // Determine which types of shadows are affected, and update each.
    //
    // Always validate L1s before L2s to prevent another cpu with a linear
    // mapping of this gmfn from seeing a walk that results from 
    // using the new L2 value and the old L1 value.  (It is OK for such a
    // guest to see a walk that uses the old L2 value with the new L1 value,
    // as hardware could behave this way if one level of the pagewalk occurs
    // before the store, and the next level of the pagewalk occurs after the
    // store.
    //
    // Ditto for L2s before L3s, etc.
    //

    if ( !(page->count_info & PGC_page_table) )
        return 0;  /* Not shadowed at all */

    if ( page->shadow_flags & SHF_L1_32 ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl1e, 2)
            (v, gmfn, entry, size);
    if ( page->shadow_flags & SHF_L2_32 ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl2e, 2)
            (v, gmfn, entry, size);

    if ( page->shadow_flags & SHF_L1_PAE ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl1e, 3)
            (v, gmfn, entry, size);
    if ( page->shadow_flags & SHF_L2_PAE ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl2e, 3)
            (v, gmfn, entry, size);
    if ( page->shadow_flags & SHF_L2H_PAE ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl2he, 3)
            (v, gmfn, entry, size);

#if CONFIG_PAGING_LEVELS >= 4 
    if ( page->shadow_flags & SHF_L1_64 ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl1e, 4)
            (v, gmfn, entry, size);
    if ( page->shadow_flags & SHF_L2_64 ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl2e, 4)
            (v, gmfn, entry, size);
    if ( page->shadow_flags & SHF_L2H_64 ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl2he, 4)
            (v, gmfn, entry, size);
    if ( page->shadow_flags & SHF_L3_64 ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl3e, 4)
            (v, gmfn, entry, size);
    if ( page->shadow_flags & SHF_L4_64 ) 
        result |= SHADOW_INTERNAL_NAME(sh_map_and_validate_gl4e, 4)
            (v, gmfn, entry, size);
#else /* 32-bit hypervisor does not support 64-bit guests */
    ASSERT((page->shadow_flags 
            & (SHF_L4_64|SHF_L3_64|SHF_L2H_64|SHF_L2_64|SHF_L1_64)) == 0);
#endif
    this_cpu(trace_shadow_path_flags) |= (result<<(TRCE_SFLAG_SET_CHANGED)); 

    return result;
}


void
sh_validate_guest_pt_write(struct vcpu *v, mfn_t gmfn,
                           void *entry, u32 size)
/* This is the entry point for emulated writes to pagetables in HVM guests and
 * PV translated guests.
 */
{
    struct domain *d = v->domain;
    int rc;

    ASSERT(shadow_locked_by_me(v->domain));
    rc = sh_validate_guest_entry(v, gmfn, entry, size);
    if ( rc & SHADOW_SET_FLUSH )
        /* Need to flush TLBs to pick up shadow PT changes */
        flush_tlb_mask(&d->domain_dirty_cpumask);
    if ( rc & SHADOW_SET_ERROR ) 
    {
        /* This page is probably not a pagetable any more: tear it out of the 
         * shadows, along with any tables that reference it.  
         * Since the validate call above will have made a "safe" (i.e. zero) 
         * shadow entry, we can let the domain live even if we can't fully 
         * unshadow the page. */
        sh_remove_shadows(v, gmfn, 0, 0);
    }
}

int shadow_write_guest_entry(struct vcpu *v, intpte_t *p,
                             intpte_t new, mfn_t gmfn)
/* Write a new value into the guest pagetable, and update the shadows 
 * appropriately.  Returns 0 if we page-faulted, 1 for success. */
{
    int failed;
    shadow_lock(v->domain);
    failed = __copy_to_user(p, &new, sizeof(new));
    if ( failed != sizeof(new) )
        sh_validate_guest_entry(v, gmfn, p, sizeof(new));
    shadow_unlock(v->domain);
    return (failed == 0);
}

int shadow_cmpxchg_guest_entry(struct vcpu *v, intpte_t *p,
                               intpte_t *old, intpte_t new, mfn_t gmfn)
/* Cmpxchg a new value into the guest pagetable, and update the shadows 
 * appropriately. Returns 0 if we page-faulted, 1 if not.
 * N.B. caller should check the value of "old" to see if the
 * cmpxchg itself was successful. */
{
    int failed;
    intpte_t t = *old;
    shadow_lock(v->domain);
    failed = cmpxchg_user(p, t, new);
    if ( t == *old )
        sh_validate_guest_entry(v, gmfn, p, sizeof(new));
    *old = t;
    shadow_unlock(v->domain);
    return (failed == 0);
}


/**************************************************************************/
/* Memory management for shadow pages. */ 

/* Allocating shadow pages
 * -----------------------
 *
 * Most shadow pages are allocated singly, but there is one case where
 * we need to allocate multiple pages together: shadowing 32-bit guest
 * tables on PAE or 64-bit shadows.  A 32-bit guest l1 table covers 4MB
 * of virtual address space, and needs to be shadowed by two PAE/64-bit
 * l1 tables (covering 2MB of virtual address space each).  Similarly, a
 * 32-bit guest l2 table (4GB va) needs to be shadowed by four
 * PAE/64-bit l2 tables (1GB va each).  These multi-page shadows are
 * not contiguous in memory; functions for handling offsets into them are
 * defined in shadow/multi.c (shadow_l1_index() etc.)
 *    
 * This table shows the allocation behaviour of the different modes:
 *
 * Xen paging      pae  pae  64b  64b  64b
 * Guest paging    32b  pae  32b  pae  64b
 * PV or HVM       HVM   *   HVM  HVM   * 
 * Shadow paging   pae  pae  pae  pae  64b
 *
 * sl1 size         8k   4k   8k   4k   4k
 * sl2 size        16k   4k  16k   4k   4k
 * sl3 size         -    -    -    -    4k
 * sl4 size         -    -    -    -    4k
 *
 * In HVM guests, the p2m table is built out of shadow pages, and we provide 
 * a function for the p2m management to steal pages, in max-order chunks, from 
 * the free pool.  We don't provide for giving them back, yet.
 */

/* Figure out the least acceptable quantity of shadow memory.
 * The minimum memory requirement for always being able to free up a
 * chunk of memory is very small -- only three max-order chunks per
 * vcpu to hold the top level shadows and pages with Xen mappings in them.  
 *
 * But for a guest to be guaranteed to successfully execute a single
 * instruction, we must be able to map a large number (about thirty) VAs
 * at the same time, which means that to guarantee progress, we must
 * allow for more than ninety allocated pages per vcpu.  We round that
 * up to 128 pages, or half a megabyte per vcpu, and add 1 more vcpu's 
 * worth to make sure we never return zero. */
static unsigned int shadow_min_acceptable_pages(struct domain *d) 
{
    u32 vcpu_count = 1;
    struct vcpu *v;

    for_each_vcpu(d, v)
        vcpu_count++;

    return (vcpu_count * 128);
} 

/* Figure out the size (in pages) of a given shadow type */
static inline u32
shadow_size(unsigned int shadow_type) 
{
    static const u32 type_to_size[SH_type_unused] = {
        1, /* SH_type_none           */
        2, /* SH_type_l1_32_shadow   */
        2, /* SH_type_fl1_32_shadow  */
        4, /* SH_type_l2_32_shadow   */
        1, /* SH_type_l1_pae_shadow  */
        1, /* SH_type_fl1_pae_shadow */
        1, /* SH_type_l2_pae_shadow  */
        1, /* SH_type_l2h_pae_shadow */
        1, /* SH_type_l1_64_shadow   */
        1, /* SH_type_fl1_64_shadow  */
        1, /* SH_type_l2_64_shadow   */
        1, /* SH_type_l2h_64_shadow  */
        1, /* SH_type_l3_64_shadow   */
        1, /* SH_type_l4_64_shadow   */
        1, /* SH_type_p2m_table      */
        1, /* SH_type_monitor_table  */
        1  /* SH_type_oos_snapshot   */
        };
    ASSERT(shadow_type < SH_type_unused);
    return type_to_size[shadow_type];
}

/* Dispatcher function: call the per-mode function that will unhook the
 * non-Xen mappings in this top-level shadow mfn.  With user_only == 1,
 * unhooks only the user-mode mappings. */
void shadow_unhook_mappings(struct vcpu *v, mfn_t smfn, int user_only)
{
    struct page_info *sp = mfn_to_page(smfn);
    switch ( sp->u.sh.type )
    {
    case SH_type_l2_32_shadow:
        SHADOW_INTERNAL_NAME(sh_unhook_32b_mappings, 2)(v, smfn, user_only);
        break;
    case SH_type_l2_pae_shadow:
    case SH_type_l2h_pae_shadow:
        SHADOW_INTERNAL_NAME(sh_unhook_pae_mappings, 3)(v, smfn, user_only);
        break;
#if CONFIG_PAGING_LEVELS >= 4
    case SH_type_l4_64_shadow:
        SHADOW_INTERNAL_NAME(sh_unhook_64b_mappings, 4)(v, smfn, user_only);
        break;
#endif
    default:
        SHADOW_ERROR("top-level shadow has bad type %08x\n", sp->u.sh.type);
        BUG();
    }
}

static inline void trace_shadow_prealloc_unpin(struct domain *d, mfn_t smfn)
{
    if ( tb_init_done )
    {
        /* Convert smfn to gfn */
        unsigned long gfn;
        ASSERT(mfn_valid(smfn));
        gfn = mfn_to_gfn(d, backpointer(mfn_to_page(smfn)));
        __trace_var(TRC_SHADOW_PREALLOC_UNPIN, 0/*!tsc*/, sizeof(gfn), &gfn);
    }
}

/* Make sure there are at least count order-sized pages
 * available in the shadow page pool. */
static void _shadow_prealloc(
    struct domain *d,
    unsigned int pages)
{
    /* Need a vpcu for calling unpins; for now, since we don't have
     * per-vcpu shadows, any will do */
    struct vcpu *v, *v2;
    struct page_info *sp, *t;
    mfn_t smfn;
    int i;

    if ( d->arch.paging.shadow.free_pages >= pages ) return;
    
    v = current;
    if ( v->domain != d )
        v = d->vcpu[0];
    ASSERT(v != NULL); /* Shouldn't have enabled shadows if we've no vcpus  */

    /* Stage one: walk the list of pinned pages, unpinning them */
    perfc_incr(shadow_prealloc_1);
    foreach_pinned_shadow(d, sp, t)
    {
        smfn = page_to_mfn(sp);

        /* Unpin this top-level shadow */
        trace_shadow_prealloc_unpin(d, smfn);
        sh_unpin(v, smfn);

        /* See if that freed up enough space */
        if ( d->arch.paging.shadow.free_pages >= pages ) return;
    }

    /* Stage two: all shadow pages are in use in hierarchies that are
     * loaded in cr3 on some vcpu.  Walk them, unhooking the non-Xen
     * mappings. */
    perfc_incr(shadow_prealloc_2);

    for_each_vcpu(d, v2) 
        for ( i = 0 ; i < 4 ; i++ )
        {
            if ( !pagetable_is_null(v2->arch.shadow_table[i]) )
            {
                TRACE_SHADOW_PATH_FLAG(TRCE_SFLAG_PREALLOC_UNHOOK);
                shadow_unhook_mappings(v, 
                               pagetable_get_mfn(v2->arch.shadow_table[i]), 0);

                /* See if that freed up enough space */
                if ( d->arch.paging.shadow.free_pages >= pages )
                {
                    flush_tlb_mask(&d->domain_dirty_cpumask);
                    return;
                }
            }
        }
    
    /* Nothing more we can do: all remaining shadows are of pages that
     * hold Xen mappings for some vcpu.  This can never happen. */
    SHADOW_ERROR("Can't pre-allocate %u shadow pages!\n"
                 "  shadow pages total = %u, free = %u, p2m=%u\n",
                 pages,
                 d->arch.paging.shadow.total_pages,
                 d->arch.paging.shadow.free_pages,
                 d->arch.paging.shadow.p2m_pages);
    BUG();
}

/* Make sure there are at least count pages of the order according to
 * type available in the shadow page pool.
 * This must be called before any calls to shadow_alloc().  Since this
 * will free existing shadows to make room, it must be called early enough
 * to avoid freeing shadows that the caller is currently working on. */
void shadow_prealloc(struct domain *d, u32 type, unsigned int count)
{
    return _shadow_prealloc(d, shadow_size(type) * count);
}

/* Deliberately free all the memory we can: this will tear down all of
 * this domain's shadows */
static void shadow_blow_tables(struct domain *d) 
{
    struct page_info *sp, *t;
    struct vcpu *v = d->vcpu[0];
    mfn_t smfn;
    int i;

    ASSERT(v != NULL);

    /* Pass one: unpin all pinned pages */
    foreach_pinned_shadow(d, sp, t)
    {
        smfn = page_to_mfn(sp);
        sh_unpin(v, smfn);
    }
        
    /* Second pass: unhook entries of in-use shadows */
    for_each_vcpu(d, v) 
        for ( i = 0 ; i < 4 ; i++ )
            if ( !pagetable_is_null(v->arch.shadow_table[i]) )
                shadow_unhook_mappings(v, 
                               pagetable_get_mfn(v->arch.shadow_table[i]), 0);

    /* Make sure everyone sees the unshadowings */
    flush_tlb_mask(&d->domain_dirty_cpumask);
}

void shadow_blow_tables_per_domain(struct domain *d)
{
    if ( shadow_mode_enabled(d) && d->vcpu != NULL && d->vcpu[0] != NULL ) {
        shadow_lock(d);
        shadow_blow_tables(d);
        shadow_unlock(d);
    }
}

#ifndef NDEBUG
/* Blow all shadows of all shadowed domains: this can be used to cause the
 * guest's pagetables to be re-shadowed if we suspect that the shadows
 * have somehow got out of sync */
static void shadow_blow_all_tables(unsigned char c)
{
    struct domain *d;
    printk("'%c' pressed -> blowing all shadow tables\n", c);
    rcu_read_lock(&domlist_read_lock);
    for_each_domain(d)
    {
        if ( shadow_mode_enabled(d) && d->vcpu != NULL && d->vcpu[0] != NULL )
        {
            shadow_lock(d);
            shadow_blow_tables(d);
            shadow_unlock(d);
        }
    }
    rcu_read_unlock(&domlist_read_lock);
}

static struct keyhandler shadow_blow_all_tables_keyhandler = {
    .u.fn = shadow_blow_all_tables,
    .desc = "reset shadow pagetables"
};

/* Register this function in the Xen console keypress table */
static __init int shadow_blow_tables_keyhandler_init(void)
{
    register_keyhandler('S', &shadow_blow_all_tables_keyhandler);
    return 0;
}
__initcall(shadow_blow_tables_keyhandler_init);
#endif /* !NDEBUG */

/* Accessors for the singly-linked list that's used for hash chains */
static inline struct page_info *
next_shadow(const struct page_info *sp)
{
    return sp->next_shadow ? pdx_to_page(sp->next_shadow) : NULL;
}

static inline void
set_next_shadow(struct page_info *sp, struct page_info *next)
{
    sp->next_shadow = next ? page_to_pdx(next) : 0;
}

/* Allocate another shadow's worth of (contiguous, aligned) pages,
 * and fill in the type and backpointer fields of their page_infos. 
 * Never fails to allocate. */
mfn_t shadow_alloc(struct domain *d,  
                    u32 shadow_type,
                    unsigned long backpointer)
{
    struct page_info *sp = NULL;
    unsigned int pages = shadow_size(shadow_type);
    struct page_list_head tmp_list;
    cpumask_t mask;
    void *p;
    int i;

    ASSERT(shadow_locked_by_me(d));
    ASSERT(shadow_type != SH_type_none);
    perfc_incr(shadow_alloc);

    if ( d->arch.paging.shadow.free_pages < pages )
    {
        /* If we get here, we failed to allocate. This should never
         * happen.  It means that we didn't call shadow_prealloc()
         * correctly before we allocated.  We can't recover by calling
         * prealloc here, because we might free up higher-level pages
         * that the caller is working on. */
        SHADOW_ERROR("Can't allocate %i shadow pages!\n", pages);
        BUG();
    }
    d->arch.paging.shadow.free_pages -= pages;

    /* Backpointers that are MFNs need to be packed into PDXs (PFNs don't) */
    switch (shadow_type)
    {
    case SH_type_fl1_32_shadow:
    case SH_type_fl1_pae_shadow:
    case SH_type_fl1_64_shadow:
        break;
    default:
        backpointer = pfn_to_pdx(backpointer);
        break;
    }

    /* Page lists don't have pointers back to the head structure, so
     * it's safe to use a head structure on the stack to link the pages
     * together. */
    INIT_PAGE_LIST_HEAD(&tmp_list);

    /* Init page info fields and clear the pages */
    for ( i = 0; i < pages ; i++ ) 
    {
        sp = page_list_remove_head(&d->arch.paging.shadow.freelist);
        /* Before we overwrite the old contents of this page, 
         * we need to be sure that no TLB holds a pointer to it. */
        mask = d->domain_dirty_cpumask;
        tlbflush_filter(mask, sp->tlbflush_timestamp);
        if ( unlikely(!cpus_empty(mask)) )
        {
            perfc_incr(shadow_alloc_tlbflush);
            flush_tlb_mask(&mask);
        }
        /* Now safe to clear the page for reuse */
        p = __map_domain_page(sp);
        ASSERT(p != NULL);
        clear_page(p);
        sh_unmap_domain_page(p);
        INIT_PAGE_LIST_ENTRY(&sp->list);
        page_list_add(sp, &tmp_list);
        sp->u.sh.type = shadow_type;
        sp->u.sh.pinned = 0;
        sp->u.sh.count = 0;
        sp->u.sh.head = 0;
        sp->v.sh.back = backpointer;
        set_next_shadow(sp, NULL);
        perfc_incr(shadow_alloc_count);
    }
    if ( shadow_type >= SH_type_min_shadow 
         && shadow_type <= SH_type_max_shadow )
        sp->u.sh.head = 1;
    return page_to_mfn(sp);
}


/* Return some shadow pages to the pool. */
void shadow_free(struct domain *d, mfn_t smfn)
{
    struct page_info *next = NULL, *sp = mfn_to_page(smfn); 
    unsigned int pages;
    u32 shadow_type;
    int i;

    ASSERT(shadow_locked_by_me(d));
    perfc_incr(shadow_free);

    shadow_type = sp->u.sh.type;
    ASSERT(shadow_type != SH_type_none);
    ASSERT(sp->u.sh.head || (shadow_type > SH_type_max_shadow));
    pages = shadow_size(shadow_type);

    for ( i = 0; i < pages; i++ ) 
    {
#if SHADOW_OPTIMIZATIONS & (SHOPT_WRITABLE_HEURISTIC | SHOPT_FAST_EMULATION)
        struct vcpu *v;
        for_each_vcpu(d, v) 
        {
#if SHADOW_OPTIMIZATIONS & SHOPT_WRITABLE_HEURISTIC
            /* No longer safe to look for a writeable mapping in this shadow */
            if ( v->arch.paging.shadow.last_writeable_pte_smfn 
                 == mfn_x(page_to_mfn(sp)) ) 
                v->arch.paging.shadow.last_writeable_pte_smfn = 0;
#endif
#if SHADOW_OPTIMIZATIONS & SHOPT_FAST_EMULATION
            v->arch.paging.last_write_emul_ok = 0;
#endif
        }
#endif
        /* Get the next page before we overwrite the list header */
        if ( i < pages - 1 )
            next = pdx_to_page(sp->list.next);
        /* Strip out the type: this is now a free shadow page */
        sp->u.sh.type = sp->u.sh.head = 0;
        /* Remember the TLB timestamp so we will know whether to flush 
         * TLBs when we reuse the page.  Because the destructors leave the
         * contents of the pages in place, we can delay TLB flushes until
         * just before the allocator hands the page out again. */
        sp->tlbflush_timestamp = tlbflush_current_time();
        perfc_decr(shadow_alloc_count);
        page_list_add_tail(sp, &d->arch.paging.shadow.freelist);
        sp = next;
    }

    d->arch.paging.shadow.free_pages += pages;
}

/* Divert a page from the pool to be used by the p2m mapping.
 * This action is irreversible: the p2m mapping only ever grows.
 * That's OK because the p2m table only exists for translated domains,
 * and those domains can't ever turn off shadow mode. */
static struct page_info *
shadow_alloc_p2m_page(struct domain *d)
{
    struct page_info *pg;
    int do_locking;

    /* This is called both from the p2m code (which never holds the 
     * shadow lock) and the log-dirty code (which sometimes does). */
    do_locking = !shadow_locked_by_me(d);
    if ( do_locking )
        shadow_lock(d);

    if ( d->arch.paging.shadow.total_pages 
         < shadow_min_acceptable_pages(d) + 1 )
    {
        if ( do_locking )
            shadow_unlock(d);
        return NULL;
    }
 
    shadow_prealloc(d, SH_type_p2m_table, 1);
    pg = mfn_to_page(shadow_alloc(d, SH_type_p2m_table, 0));
    d->arch.paging.shadow.p2m_pages++;
    d->arch.paging.shadow.total_pages--;

    if ( do_locking )
        shadow_unlock(d);

    /* Unlike shadow pages, mark p2m pages as owned by the domain.
     * Marking the domain as the owner would normally allow the guest to
     * create mappings of these pages, but these p2m pages will never be
     * in the domain's guest-physical address space, and so that is not
     * believed to be a concern. */
    page_set_owner(pg, d);
    pg->count_info |= 1;
    return pg;
}

static void
shadow_free_p2m_page(struct domain *d, struct page_info *pg)
{
    int do_locking;

    ASSERT(page_get_owner(pg) == d);
    /* Should have just the one ref we gave it in alloc_p2m_page() */
    if ( (pg->count_info & PGC_count_mask) != 1 )
    {
        SHADOW_ERROR("Odd p2m page count c=%#lx t=%"PRtype_info"\n",
                     pg->count_info, pg->u.inuse.type_info);
    }
    pg->count_info &= ~PGC_count_mask;
    pg->u.sh.type = SH_type_p2m_table; /* p2m code reuses type-info */
    page_set_owner(pg, NULL); 

    /* This is called both from the p2m code (which never holds the 
     * shadow lock) and the log-dirty code (which sometimes does). */
    do_locking = !shadow_locked_by_me(d);
    if ( do_locking )
        shadow_lock(d);

    shadow_free(d, page_to_mfn(pg));
    d->arch.paging.shadow.p2m_pages--;
    d->arch.paging.shadow.total_pages++;

    if ( do_locking )
        shadow_unlock(d);
}

#if CONFIG_PAGING_LEVELS == 3
static void p2m_install_entry_in_monitors(struct domain *d, 
                                          l3_pgentry_t *l3e) 
/* Special case, only used for external-mode domains on PAE hosts:
 * update the mapping of the p2m table.  Once again, this is trivial in
 * other paging modes (one top-level entry points to the top-level p2m,
 * no maintenance needed), but PAE makes life difficult by needing a
 * copy the eight l3es of the p2m table in eight l2h slots in the
 * monitor table.  This function makes fresh copies when a p2m l3e
 * changes. */
{
    l2_pgentry_t *ml2e;
    struct vcpu *v;
    unsigned int index;

    index = ((unsigned long)l3e & ~PAGE_MASK) / sizeof(l3_pgentry_t);
    ASSERT(index < MACHPHYS_MBYTES>>1);

    for_each_vcpu(d, v) 
    {
        if ( pagetable_get_pfn(v->arch.monitor_table) == 0 ) 
            continue;
        ASSERT(shadow_mode_external(v->domain));

        SHADOW_DEBUG(P2M, "d=%u v=%u index=%u mfn=%#lx\n",
                      d->domain_id, v->vcpu_id, index, l3e_get_pfn(*l3e));

        if ( v == current ) /* OK to use linear map of monitor_table */
            ml2e = __linear_l2_table + l2_linear_offset(RO_MPT_VIRT_START);
        else 
        {
            l3_pgentry_t *ml3e;
            ml3e = sh_map_domain_page(pagetable_get_mfn(v->arch.monitor_table));
            ASSERT(l3e_get_flags(ml3e[3]) & _PAGE_PRESENT);
            ml2e = sh_map_domain_page(_mfn(l3e_get_pfn(ml3e[3])));
            ml2e += l2_table_offset(RO_MPT_VIRT_START);
            sh_unmap_domain_page(ml3e);
        }
        ml2e[index] = l2e_from_pfn(l3e_get_pfn(*l3e), __PAGE_HYPERVISOR);
        if ( v != current )
            sh_unmap_domain_page(ml2e);
    }
}
#endif

/* Set the pool of shadow pages to the required number of pages.
 * Input will be rounded up to at least shadow_min_acceptable_pages(),
 * plus space for the p2m table.
 * Returns 0 for success, non-zero for failure. */
static unsigned int sh_set_allocation(struct domain *d, 
                                      unsigned int pages,
                                      int *preempted)
{
    struct page_info *sp;
    unsigned int lower_bound;

    ASSERT(shadow_locked_by_me(d));

    if ( pages > 0 )
    {
        /* Check for minimum value. */
        if ( pages < d->arch.paging.shadow.p2m_pages )
            pages = 0;
        else
            pages -= d->arch.paging.shadow.p2m_pages;
        
        /* Don't allocate less than the minimum acceptable, plus one page per
         * megabyte of RAM (for the p2m table) */
        lower_bound = shadow_min_acceptable_pages(d) + (d->tot_pages / 256);
        if ( pages < lower_bound )
            pages = lower_bound;
    }

    SHADOW_PRINTK("current %i target %i\n", 
                   d->arch.paging.shadow.total_pages, pages);

    while ( d->arch.paging.shadow.total_pages != pages ) 
    {
        if ( d->arch.paging.shadow.total_pages < pages ) 
        {
            /* Need to allocate more memory from domheap */
            sp = (struct page_info *)
                alloc_domheap_page(NULL, MEMF_node(domain_to_node(d)));
            if ( sp == NULL ) 
            { 
                SHADOW_PRINTK("failed to allocate shadow pages.\n");
                return -ENOMEM;
            }
            d->arch.paging.shadow.free_pages++;
            d->arch.paging.shadow.total_pages++;
            sp->u.sh.type = 0;
            sp->u.sh.pinned = 0;
            sp->u.sh.count = 0;
            sp->tlbflush_timestamp = 0; /* Not in any TLB */
            page_list_add_tail(sp, &d->arch.paging.shadow.freelist);
        } 
        else if ( d->arch.paging.shadow.total_pages > pages ) 
        {
            /* Need to return memory to domheap */
            _shadow_prealloc(d, 1);
            sp = page_list_remove_head(&d->arch.paging.shadow.freelist);
            ASSERT(sp);
            /*
             * The pages were allocated anonymously, but the owner field
             * gets overwritten normally, so need to clear it here.
             */
            page_set_owner(sp, NULL);
            d->arch.paging.shadow.free_pages--;
            d->arch.paging.shadow.total_pages--;
            free_domheap_page(sp);
        }

        /* Check to see if we need to yield and try again */
        if ( preempted && hypercall_preempt_check() )
        {
            *preempted = 1;
            return 0;
        }
    }

    return 0;
}

/* Return the size of the shadow pool, rounded up to the nearest MB */
static unsigned int shadow_get_allocation(struct domain *d)
{
    unsigned int pg = d->arch.paging.shadow.total_pages
        + d->arch.paging.shadow.p2m_pages;
    return ((pg >> (20 - PAGE_SHIFT))
            + ((pg & ((1 << (20 - PAGE_SHIFT)) - 1)) ? 1 : 0));
}

/**************************************************************************/
/* Hash table for storing the guest->shadow mappings.
 * The table itself is an array of pointers to shadows; the shadows are then 
 * threaded on a singly-linked list of shadows with the same hash value */

#define SHADOW_HASH_BUCKETS 251
/* Other possibly useful primes are 509, 1021, 2039, 4093, 8191, 16381 */

/* Hash function that takes a gfn or mfn, plus another byte of type info */
typedef u32 key_t;
static inline key_t sh_hash(unsigned long n, unsigned int t) 
{
    unsigned char *p = (unsigned char *)&n;
    key_t k = t;
    int i;
    for ( i = 0; i < sizeof(n) ; i++ ) k = (u32)p[i] + (k<<6) + (k<<16) - k;
    return k % SHADOW_HASH_BUCKETS;
}

#if SHADOW_AUDIT & (SHADOW_AUDIT_HASH|SHADOW_AUDIT_HASH_FULL)

/* Before we get to the mechanism, define a pair of audit functions
 * that sanity-check the contents of the hash table. */
static void sh_hash_audit_bucket(struct domain *d, int bucket)
/* Audit one bucket of the hash table */
{
    struct page_info *sp, *x;

    if ( !(SHADOW_AUDIT_ENABLE) )
        return;

    sp = d->arch.paging.shadow.hash_table[bucket];
    while ( sp )
    {
        /* Not a shadow? */
        BUG_ON( (sp->count_info & PGC_count_mask )!= 0 ) ;
        /* Bogus type? */
        BUG_ON( sp->u.sh.type == 0 );
        BUG_ON( sp->u.sh.type > SH_type_max_shadow );
        /* Wrong page of a multi-page shadow? */
        BUG_ON( !sp->u.sh.head );
        /* Wrong bucket? */
        BUG_ON( sh_hash(__backpointer(sp), sp->u.sh.type) != bucket );
        /* Duplicate entry? */
        for ( x = next_shadow(sp); x; x = next_shadow(x) )
            BUG_ON( x->v.sh.back == sp->v.sh.back &&
                    x->u.sh.type == sp->u.sh.type );
        /* Follow the backpointer to the guest pagetable */
        if ( sp->u.sh.type != SH_type_fl1_32_shadow
             && sp->u.sh.type != SH_type_fl1_pae_shadow
             && sp->u.sh.type != SH_type_fl1_64_shadow )
        {
            struct page_info *gpg = mfn_to_page(backpointer(sp));
            /* Bad shadow flags on guest page? */
            BUG_ON( !(gpg->shadow_flags & (1<<sp->u.sh.type)) );
            /* Bad type count on guest page? */
#if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC)
            if ( sp->u.sh.type == SH_type_l1_32_shadow
                 || sp->u.sh.type == SH_type_l1_pae_shadow
                 || sp->u.sh.type == SH_type_l1_64_shadow )
            {
                if ( (gpg->u.inuse.type_info & PGT_type_mask) == PGT_writable_page
                     && (gpg->u.inuse.type_info & PGT_count_mask) != 0 )
                {
                    if ( !page_is_out_of_sync(gpg) )
                    {
                        SHADOW_ERROR("MFN %#"PRI_mfn" shadowed (by %#"PRI_mfn")"
                                     " and not OOS but has typecount %#lx\n",
                                     __backpointer(sp),
                                     mfn_x(page_to_mfn(sp)), 
                                     gpg->u.inuse.type_info);
                        BUG();
                    }
                }
            }
            else /* Not an l1 */
#endif
            if ( (gpg->u.inuse.type_info & PGT_type_mask) == PGT_writable_page 
                 && (gpg->u.inuse.type_info & PGT_count_mask) != 0 )
            {
                SHADOW_ERROR("MFN %#"PRI_mfn" shadowed (by %#"PRI_mfn")"
                             " but has typecount %#lx\n",
                             __backpointer(sp), mfn_x(page_to_mfn(sp)),
                             gpg->u.inuse.type_info);
                BUG();
            }
        }
        /* That entry was OK; on we go */
        sp = next_shadow(sp);
    }
}

#else
#define sh_hash_audit_bucket(_d, _b) do {} while(0)
#endif /* Hashtable bucket audit */


#if SHADOW_AUDIT & SHADOW_AUDIT_HASH_FULL

static void sh_hash_audit(struct domain *d)
/* Full audit: audit every bucket in the table */
{
    int i;

    if ( !(SHADOW_AUDIT_ENABLE) )
        return;

    for ( i = 0; i < SHADOW_HASH_BUCKETS; i++ ) 
    {
        sh_hash_audit_bucket(d, i);
    }
}

#else
#define sh_hash_audit(_d) do {} while(0)
#endif /* Hashtable bucket audit */

/* Allocate and initialise the table itself.  
 * Returns 0 for success, 1 for error. */
static int shadow_hash_alloc(struct domain *d)
{
    struct page_info **table;

    ASSERT(shadow_locked_by_me(d));
    ASSERT(!d->arch.paging.shadow.hash_table);

    table = xmalloc_array(struct page_info *, SHADOW_HASH_BUCKETS);
    if ( !table ) return 1;
    memset(table, 0, 
           SHADOW_HASH_BUCKETS * sizeof (struct page_info *));
    d->arch.paging.shadow.hash_table = table;
    return 0;
}

/* Tear down the hash table and return all memory to Xen.
 * This function does not care whether the table is populated. */
static void shadow_hash_teardown(struct domain *d)
{
    ASSERT(shadow_locked_by_me(d));
    ASSERT(d->arch.paging.shadow.hash_table);

    xfree(d->arch.paging.shadow.hash_table);
    d->arch.paging.shadow.hash_table = NULL;
}


mfn_t shadow_hash_lookup(struct vcpu *v, unsigned long n, unsigned int t)
/* Find an entry in the hash table.  Returns the MFN of the shadow,
 * or INVALID_MFN if it doesn't exist */
{
    struct domain *d = v->domain;
    struct page_info *sp, *prev;
    key_t key;

    ASSERT(shadow_locked_by_me(d));
    ASSERT(d->arch.paging.shadow.hash_table);
    ASSERT(t);

    sh_hash_audit(d);

    perfc_incr(shadow_hash_lookups);
    key = sh_hash(n, t);
    sh_hash_audit_bucket(d, key);

    sp = d->arch.paging.shadow.hash_table[key];
    prev = NULL;
    while(sp)
    {
        if ( __backpointer(sp) == n && sp->u.sh.type == t )
        {
            /* Pull-to-front if 'sp' isn't already the head item */
            if ( unlikely(sp != d->arch.paging.shadow.hash_table[key]) )
            {
                if ( unlikely(d->arch.paging.shadow.hash_walking != 0) )
                    /* Can't reorder: someone is walking the hash chains */
                    return page_to_mfn(sp);
                else 
                {
                    ASSERT(prev);
                    /* Delete sp from the list */
                    prev->next_shadow = sp->next_shadow;                    
                    /* Re-insert it at the head of the list */
                    set_next_shadow(sp, d->arch.paging.shadow.hash_table[key]);
                    d->arch.paging.shadow.hash_table[key] = sp;
                }
            }
            else
            {
                perfc_incr(shadow_hash_lookup_head);
            }
            return page_to_mfn(sp);
        }
        prev = sp;
        sp = next_shadow(sp);
    }

    perfc_incr(shadow_hash_lookup_miss);
    return _mfn(INVALID_MFN);
}

void shadow_hash_insert(struct vcpu *v, unsigned long n, unsigned int t, 
                        mfn_t smfn)
/* Put a mapping (n,t)->smfn into the hash table */
{
    struct domain *d = v->domain;
    struct page_info *sp;
    key_t key;
    
    ASSERT(shadow_locked_by_me(d));
    ASSERT(d->arch.paging.shadow.hash_table);
    ASSERT(t);

    sh_hash_audit(d);

    perfc_incr(shadow_hash_inserts);
    key = sh_hash(n, t);
    sh_hash_audit_bucket(d, key);
    
    /* Insert this shadow at the top of the bucket */
    sp = mfn_to_page(smfn);
    set_next_shadow(sp, d->arch.paging.shadow.hash_table[key]);
    d->arch.paging.shadow.hash_table[key] = sp;
    
    sh_hash_audit_bucket(d, key);
}

void shadow_hash_delete(struct vcpu *v, unsigned long n, unsigned int t, 
                        mfn_t smfn)
/* Excise the mapping (n,t)->smfn from the hash table */
{
    struct domain *d = v->domain;
    struct page_info *sp, *x;
    key_t key;

    ASSERT(shadow_locked_by_me(d));
    ASSERT(d->arch.paging.shadow.hash_table);
Mode	Name	Size
-rw-r--r--	Dockerfile.alpine	389	log stats plain
-rw-r--r--	Dockerfile.anita	2268	log stats plain
-rw-r--r--	Dockerfile.centos	383	log stats plain
-rw-r--r--	Dockerfile.debian-debootstrap	561	log stats plain
-rw-r--r--	Dockerfile.djgpp	954	log stats plain
-rw-r--r--	Dockerfile.fedora	434	log stats plain
-rw-r--r--	Dockerfile.qemu-user-static	103	log stats plain
-rw-r--r--	Dockerfile.ubuntu-debootstrap	1011	log stats plain
-rw-r--r--	Makefile	2933	log stats plain
-rw-r--r--	Makefile.anita	2410	log stats plain
-rw-r--r--	Makefile.targets	5611	log stats plain
-rw-r--r--	README.md	3584	log stats plain
-rw-r--r--	anita-wrapper.sh	405	log stats plain
-rw-r--r--	mani-wrapper.sh	114	log stats plain