Archipelago » qemu

/*

 *  virtual page mapping and translated block handling

 *

 *  Copyright (c) 2003 Fabrice Bellard

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2 of the License, or (at your option) any later version.

 *

 * This library 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

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA  02110-1301 USA

 */

#include "config.h"

#ifdef _WIN32

#define WIN32_LEAN_AND_MEAN

#include <windows.h>

#else

#include <sys/types.h>

#include <sys/mman.h>

#endif

#include <stdlib.h>

#include <stdio.h>

#include <stdarg.h>

#include <string.h>

#include <errno.h>

#include <unistd.h>

#include <inttypes.h>

#include "cpu.h"

#include "exec-all.h"

#include "qemu-common.h"

#include "tcg.h"

#include "hw/hw.h"

#include "osdep.h"

#include "kvm.h"

#if defined(CONFIG_USER_ONLY)

#include <qemu.h>

#endif

//#define DEBUG_TB_INVALIDATE

//#define DEBUG_FLUSH

//#define DEBUG_TLB

//#define DEBUG_UNASSIGNED

/* make various TB consistency checks */

//#define DEBUG_TB_CHECK

//#define DEBUG_TLB_CHECK

//#define DEBUG_IOPORT

//#define DEBUG_SUBPAGE

#if !defined(CONFIG_USER_ONLY)

/* TB consistency checks only implemented for usermode emulation.  */

#undef DEBUG_TB_CHECK

#endif

#define SMC_BITMAP_USE_THRESHOLD 10

#define MMAP_AREA_START        0x00000000

#define MMAP_AREA_END          0xa8000000

#if defined(TARGET_SPARC64)

#define TARGET_PHYS_ADDR_SPACE_BITS 41

#elif defined(TARGET_SPARC)

#define TARGET_PHYS_ADDR_SPACE_BITS 36

#elif defined(TARGET_ALPHA)

#define TARGET_PHYS_ADDR_SPACE_BITS 42

#define TARGET_VIRT_ADDR_SPACE_BITS 42

#elif defined(TARGET_PPC64)

#define TARGET_PHYS_ADDR_SPACE_BITS 42

#elif defined(TARGET_X86_64) && !defined(USE_KQEMU)

#define TARGET_PHYS_ADDR_SPACE_BITS 42

#elif defined(TARGET_I386) && !defined(USE_KQEMU)

#define TARGET_PHYS_ADDR_SPACE_BITS 36

#else

/* Note: for compatibility with kqemu, we use 32 bits for x86_64 */

#define TARGET_PHYS_ADDR_SPACE_BITS 32

#endif

static TranslationBlock *tbs;

int code_gen_max_blocks;

TranslationBlock *tb_phys_hash[CODE_GEN_PHYS_HASH_SIZE];

static int nb_tbs;

/* any access to the tbs or the page table must use this lock */

spinlock_t tb_lock = SPIN_LOCK_UNLOCKED;

#if defined(__arm__) || defined(__sparc_v9__)

/* The prologue must be reachable with a direct jump. ARM and Sparc64

 have limited branch ranges (possibly also PPC) so place it in a

 section close to code segment. */

#define code_gen_section                                \

    __attribute__((__section__(".gen_code")))           \

    __attribute__((aligned (32)))

#else

#define code_gen_section                                \

    __attribute__((aligned (32)))

#endif

uint8_t code_gen_prologue[1024] code_gen_section;

static uint8_t *code_gen_buffer;

static unsigned long code_gen_buffer_size;

/* threshold to flush the translated code buffer */

static unsigned long code_gen_buffer_max_size;

uint8_t *code_gen_ptr;

#if !defined(CONFIG_USER_ONLY)

ram_addr_t phys_ram_size;

int phys_ram_fd;

uint8_t *phys_ram_base;

uint8_t *phys_ram_dirty;

static int in_migration;

static ram_addr_t phys_ram_alloc_offset = 0;

#endif

CPUState *first_cpu;

/* current CPU in the current thread. It is only valid inside

   cpu_exec() */

CPUState *cpu_single_env;

/* 0 = Do not count executed instructions.

   1 = Precise instruction counting.

   2 = Adaptive rate instruction counting.  */

int use_icount = 0;

/* Current instruction counter.  While executing translated code this may

   include some instructions that have not yet been executed.  */

int64_t qemu_icount;

typedef struct PageDesc {

    /* list of TBs intersecting this ram page */

    TranslationBlock *first_tb;

    /* in order to optimize self modifying code, we count the number

       of lookups we do to a given page to use a bitmap */

    unsigned int code_write_count;

    uint8_t *code_bitmap;

#if defined(CONFIG_USER_ONLY)

    unsigned long flags;

#endif

} PageDesc;

typedef struct PhysPageDesc {

    /* offset in host memory of the page + io_index in the low bits */

    ram_addr_t phys_offset;

    ram_addr_t region_offset;

} PhysPageDesc;

#define L2_BITS 10

#if defined(CONFIG_USER_ONLY) && defined(TARGET_VIRT_ADDR_SPACE_BITS)

/* XXX: this is a temporary hack for alpha target.

 *      In the future, this is to be replaced by a multi-level table

 *      to actually be able to handle the complete 64 bits address space.

 */

#define L1_BITS (TARGET_VIRT_ADDR_SPACE_BITS - L2_BITS - TARGET_PAGE_BITS)

#else

#define L1_BITS (32 - L2_BITS - TARGET_PAGE_BITS)

#endif

#define L1_SIZE (1 << L1_BITS)

#define L2_SIZE (1 << L2_BITS)

unsigned long qemu_real_host_page_size;

unsigned long qemu_host_page_bits;

unsigned long qemu_host_page_size;

unsigned long qemu_host_page_mask;

/* XXX: for system emulation, it could just be an array */

static PageDesc *l1_map[L1_SIZE];

static PhysPageDesc **l1_phys_map;

#if !defined(CONFIG_USER_ONLY)

static void io_mem_init(void);

/* io memory support */

CPUWriteMemoryFunc *io_mem_write[IO_MEM_NB_ENTRIES][4];

CPUReadMemoryFunc *io_mem_read[IO_MEM_NB_ENTRIES][4];

void *io_mem_opaque[IO_MEM_NB_ENTRIES];

static int io_mem_nb;

static int io_mem_watch;

#endif

/* log support */

static const char *logfilename = "/tmp/qemu.log";

FILE *logfile;

int loglevel;

static int log_append = 0;

/* statistics */

static int tlb_flush_count;

static int tb_flush_count;

static int tb_phys_invalidate_count;

#define SUBPAGE_IDX(addr) ((addr) & ~TARGET_PAGE_MASK)

typedef struct subpage_t {

    target_phys_addr_t base;

    CPUReadMemoryFunc **mem_read[TARGET_PAGE_SIZE][4];

    CPUWriteMemoryFunc **mem_write[TARGET_PAGE_SIZE][4];

    void *opaque[TARGET_PAGE_SIZE][2][4];

    ram_addr_t region_offset[TARGET_PAGE_SIZE][2][4];

} subpage_t;

#ifdef _WIN32

static void map_exec(void *addr, long size)

{

    DWORD old_protect;

    VirtualProtect(addr, size,

                   PAGE_EXECUTE_READWRITE, &old_protect);

}

#else

static void map_exec(void *addr, long size)

{

    unsigned long start, end, page_size;

    page_size = getpagesize();

    start = (unsigned long)addr;

    start &= ~(page_size - 1);

    end = (unsigned long)addr + size;

    end += page_size - 1;

    end &= ~(page_size - 1);

    mprotect((void *)start, end - start,

             PROT_READ | PROT_WRITE | PROT_EXEC);

}

#endif

static void page_init(void)

{

    /* NOTE: we can always suppose that qemu_host_page_size >=

       TARGET_PAGE_SIZE */

#ifdef _WIN32

    {

        SYSTEM_INFO system_info;

        GetSystemInfo(&system_info);

        qemu_real_host_page_size = system_info.dwPageSize;

    }

#else

    qemu_real_host_page_size = getpagesize();

#endif

    if (qemu_host_page_size == 0)

        qemu_host_page_size = qemu_real_host_page_size;

    if (qemu_host_page_size < TARGET_PAGE_SIZE)

        qemu_host_page_size = TARGET_PAGE_SIZE;

    qemu_host_page_bits = 0;

    while ((1 << qemu_host_page_bits) < qemu_host_page_size)

        qemu_host_page_bits++;

    qemu_host_page_mask = ~(qemu_host_page_size - 1);

    l1_phys_map = qemu_vmalloc(L1_SIZE * sizeof(void *));

    memset(l1_phys_map, 0, L1_SIZE * sizeof(void *));

#if !defined(_WIN32) && defined(CONFIG_USER_ONLY)

    {

        long long startaddr, endaddr;

        FILE *f;

        int n;

        mmap_lock();

        last_brk = (unsigned long)sbrk(0);

        f = fopen("/proc/self/maps", "r");

        if (f) {

            do {

                n = fscanf (f, "%llx-%llx %*[^\n]\n", &startaddr, &endaddr);

                if (n == 2) {

                    startaddr = MIN(startaddr,

                                    (1ULL << TARGET_PHYS_ADDR_SPACE_BITS) - 1);

                    endaddr = MIN(endaddr,

                                    (1ULL << TARGET_PHYS_ADDR_SPACE_BITS) - 1);

                    page_set_flags(startaddr & TARGET_PAGE_MASK,

                                   TARGET_PAGE_ALIGN(endaddr),

                                   PAGE_RESERVED); 

                }

            } while (!feof(f));

            fclose(f);

        }

        mmap_unlock();

    }

#endif

}

static inline PageDesc **page_l1_map(target_ulong index)

{

#if TARGET_LONG_BITS > 32

    /* Host memory outside guest VM.  For 32-bit targets we have already

       excluded high addresses.  */

    if (index > ((target_ulong)L2_SIZE * L1_SIZE))

        return NULL;

#endif

    return &l1_map[index >> L2_BITS];

}

static inline PageDesc *page_find_alloc(target_ulong index)

{

    PageDesc **lp, *p;

    lp = page_l1_map(index);

    if (!lp)

        return NULL;

    p = *lp;

    if (!p) {

        /* allocate if not found */

#if defined(CONFIG_USER_ONLY)

        size_t len = sizeof(PageDesc) * L2_SIZE;

        /* Don't use qemu_malloc because it may recurse.  */

        p = mmap(0, len, PROT_READ | PROT_WRITE,

                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

        *lp = p;

        if (h2g_valid(p)) {

            unsigned long addr = h2g(p);

            page_set_flags(addr & TARGET_PAGE_MASK,

                           TARGET_PAGE_ALIGN(addr + len),

                           PAGE_RESERVED); 

        }

#else

        p = qemu_mallocz(sizeof(PageDesc) * L2_SIZE);

        *lp = p;

#endif

    }

    return p + (index & (L2_SIZE - 1));

}

static inline PageDesc *page_find(target_ulong index)

{

    PageDesc **lp, *p;

    lp = page_l1_map(index);

    if (!lp)

        return NULL;

    p = *lp;

    if (!p)

        return 0;

    return p + (index & (L2_SIZE - 1));

}

static PhysPageDesc *phys_page_find_alloc(target_phys_addr_t index, int alloc)

{

    void **lp, **p;

    PhysPageDesc *pd;

    p = (void **)l1_phys_map;

#if TARGET_PHYS_ADDR_SPACE_BITS > 32

#if TARGET_PHYS_ADDR_SPACE_BITS > (32 + L1_BITS)

#error unsupported TARGET_PHYS_ADDR_SPACE_BITS

#endif

    lp = p + ((index >> (L1_BITS + L2_BITS)) & (L1_SIZE - 1));

    p = *lp;

    if (!p) {

        /* allocate if not found */

        if (!alloc)

            return NULL;

        p = qemu_vmalloc(sizeof(void *) * L1_SIZE);

        memset(p, 0, sizeof(void *) * L1_SIZE);

        *lp = p;

    }

#endif

    lp = p + ((index >> L2_BITS) & (L1_SIZE - 1));

    pd = *lp;

    if (!pd) {

        int i;

        /* allocate if not found */

        if (!alloc)

            return NULL;

        pd = qemu_vmalloc(sizeof(PhysPageDesc) * L2_SIZE);

        *lp = pd;

        for (i = 0; i < L2_SIZE; i++)

          pd[i].phys_offset = IO_MEM_UNASSIGNED;

    }

    return ((PhysPageDesc *)pd) + (index & (L2_SIZE - 1));

}

static inline PhysPageDesc *phys_page_find(target_phys_addr_t index)

{

    return phys_page_find_alloc(index, 0);

}

#if !defined(CONFIG_USER_ONLY)

static void tlb_protect_code(ram_addr_t ram_addr);

static void tlb_unprotect_code_phys(CPUState *env, ram_addr_t ram_addr,

                                    target_ulong vaddr);

#define mmap_lock() do { } while(0)

#define mmap_unlock() do { } while(0)

#endif

#define DEFAULT_CODE_GEN_BUFFER_SIZE (32 * 1024 * 1024)

#if defined(CONFIG_USER_ONLY)

/* Currently it is not recommanded to allocate big chunks of data in

   user mode. It will change when a dedicated libc will be used */

#define USE_STATIC_CODE_GEN_BUFFER

#endif

#ifdef USE_STATIC_CODE_GEN_BUFFER

static uint8_t static_code_gen_buffer[DEFAULT_CODE_GEN_BUFFER_SIZE];

#endif

static void code_gen_alloc(unsigned long tb_size)

{

#ifdef USE_STATIC_CODE_GEN_BUFFER

    code_gen_buffer = static_code_gen_buffer;

    code_gen_buffer_size = DEFAULT_CODE_GEN_BUFFER_SIZE;

    map_exec(code_gen_buffer, code_gen_buffer_size);

#else

    code_gen_buffer_size = tb_size;

    if (code_gen_buffer_size == 0) {

#if defined(CONFIG_USER_ONLY)

        /* in user mode, phys_ram_size is not meaningful */

        code_gen_buffer_size = DEFAULT_CODE_GEN_BUFFER_SIZE;

#else

        /* XXX: needs ajustments */

        code_gen_buffer_size = (unsigned long)(phys_ram_size / 4);

#endif

    }

    if (code_gen_buffer_size < MIN_CODE_GEN_BUFFER_SIZE)

        code_gen_buffer_size = MIN_CODE_GEN_BUFFER_SIZE;

    /* The code gen buffer location may have constraints depending on

       the host cpu and OS */

#if defined(__linux__) 

    {

        int flags;

        void *start = NULL;

        flags = MAP_PRIVATE | MAP_ANONYMOUS;

#if defined(__x86_64__)

        flags |= MAP_32BIT;

        /* Cannot map more than that */

        if (code_gen_buffer_size > (800 * 1024 * 1024))

            code_gen_buffer_size = (800 * 1024 * 1024);

#elif defined(__sparc_v9__)

        // Map the buffer below 2G, so we can use direct calls and branches

        flags |= MAP_FIXED;

        start = (void *) 0x60000000UL;

        if (code_gen_buffer_size > (512 * 1024 * 1024))

            code_gen_buffer_size = (512 * 1024 * 1024);

#elif defined(__arm__)

        /* Map the buffer below 32M, so we can use direct calls and branches */

        flags |= MAP_FIXED;

        start = (void *) 0x01000000UL;

        if (code_gen_buffer_size > 16 * 1024 * 1024)

            code_gen_buffer_size = 16 * 1024 * 1024;

#endif

        code_gen_buffer = mmap(start, code_gen_buffer_size,

                               PROT_WRITE | PROT_READ | PROT_EXEC,

                               flags, -1, 0);

        if (code_gen_buffer == MAP_FAILED) {

            fprintf(stderr, "Could not allocate dynamic translator buffer\n");

            exit(1);

        }

    }

#elif defined(__FreeBSD__)

    {

        int flags;

        void *addr = NULL;

        flags = MAP_PRIVATE | MAP_ANONYMOUS;

#if defined(__x86_64__)

        /* FreeBSD doesn't have MAP_32BIT, use MAP_FIXED and assume

         * 0x40000000 is free */

        flags |= MAP_FIXED;

        addr = (void *)0x40000000;

        /* Cannot map more than that */

        if (code_gen_buffer_size > (800 * 1024 * 1024))

            code_gen_buffer_size = (800 * 1024 * 1024);

#endif

        code_gen_buffer = mmap(addr, code_gen_buffer_size,

                               PROT_WRITE | PROT_READ | PROT_EXEC, 

                               flags, -1, 0);

        if (code_gen_buffer == MAP_FAILED) {

            fprintf(stderr, "Could not allocate dynamic translator buffer\n");

            exit(1);

        }

    }

#else

    code_gen_buffer = qemu_malloc(code_gen_buffer_size);

    map_exec(code_gen_buffer, code_gen_buffer_size);

#endif

#endif /* !USE_STATIC_CODE_GEN_BUFFER */

    map_exec(code_gen_prologue, sizeof(code_gen_prologue));

    code_gen_buffer_max_size = code_gen_buffer_size - 

        code_gen_max_block_size();

    code_gen_max_blocks = code_gen_buffer_size / CODE_GEN_AVG_BLOCK_SIZE;

    tbs = qemu_malloc(code_gen_max_blocks * sizeof(TranslationBlock));

}

/* Must be called before using the QEMU cpus. 'tb_size' is the size

   (in bytes) allocated to the translation buffer. Zero means default

   size. */

void cpu_exec_init_all(unsigned long tb_size)

{

    cpu_gen_init();

    code_gen_alloc(tb_size);

    code_gen_ptr = code_gen_buffer;

    page_init();

#if !defined(CONFIG_USER_ONLY)

    io_mem_init();

#endif

}

#if defined(CPU_SAVE_VERSION) && !defined(CONFIG_USER_ONLY)

#define CPU_COMMON_SAVE_VERSION 1

static void cpu_common_save(QEMUFile *f, void *opaque)

{

    CPUState *env = opaque;

    qemu_put_be32s(f, &env->halted);

    qemu_put_be32s(f, &env->interrupt_request);

}

static int cpu_common_load(QEMUFile *f, void *opaque, int version_id)

{

    CPUState *env = opaque;

    if (version_id != CPU_COMMON_SAVE_VERSION)

        return -EINVAL;

    qemu_get_be32s(f, &env->halted);

    qemu_get_be32s(f, &env->interrupt_request);

    tlb_flush(env, 1);

    return 0;

}

#endif

void cpu_exec_init(CPUState *env)

{

    CPUState **penv;

    int cpu_index;

    env->next_cpu = NULL;

    penv = &first_cpu;

    cpu_index = 0;

    while (*penv != NULL) {

        penv = (CPUState **)&(*penv)->next_cpu;

        cpu_index++;

    }

    env->cpu_index = cpu_index;

    TAILQ_INIT(&env->breakpoints);

    TAILQ_INIT(&env->watchpoints);

    *penv = env;

#if defined(CPU_SAVE_VERSION) && !defined(CONFIG_USER_ONLY)

    register_savevm("cpu_common", cpu_index, CPU_COMMON_SAVE_VERSION,

                    cpu_common_save, cpu_common_load, env);

    register_savevm("cpu", cpu_index, CPU_SAVE_VERSION,

                    cpu_save, cpu_load, env);

#endif

}

static inline void invalidate_page_bitmap(PageDesc *p)

{

    if (p->code_bitmap) {

        qemu_free(p->code_bitmap);

        p->code_bitmap = NULL;

    }

    p->code_write_count = 0;

}

/* set to NULL all the 'first_tb' fields in all PageDescs */

static void page_flush_tb(void)

{

    int i, j;

    PageDesc *p;

    for(i = 0; i < L1_SIZE; i++) {

        p = l1_map[i];

        if (p) {

            for(j = 0; j < L2_SIZE; j++) {

                p->first_tb = NULL;

                invalidate_page_bitmap(p);

                p++;

            }

        }

    }

}

/* flush all the translation blocks */

/* XXX: tb_flush is currently not thread safe */

void tb_flush(CPUState *env1)

{

    CPUState *env;

#if defined(DEBUG_FLUSH)

    printf("qemu: flush code_size=%ld nb_tbs=%d avg_tb_size=%ld\n",

           (unsigned long)(code_gen_ptr - code_gen_buffer),

           nb_tbs, nb_tbs > 0 ?

           ((unsigned long)(code_gen_ptr - code_gen_buffer)) / nb_tbs : 0);

#endif

    if ((unsigned long)(code_gen_ptr - code_gen_buffer) > code_gen_buffer_size)

        cpu_abort(env1, "Internal error: code buffer overflow\n");

    nb_tbs = 0;

    for(env = first_cpu; env != NULL; env = env->next_cpu) {

        memset (env->tb_jmp_cache, 0, TB_JMP_CACHE_SIZE * sizeof (void *));

    }

    memset (tb_phys_hash, 0, CODE_GEN_PHYS_HASH_SIZE * sizeof (void *));

    page_flush_tb();

    code_gen_ptr = code_gen_buffer;

    /* XXX: flush processor icache at this point if cache flush is

       expensive */

    tb_flush_count++;

}

#ifdef DEBUG_TB_CHECK

static void tb_invalidate_check(target_ulong address)

{

    TranslationBlock *tb;

    int i;

    address &= TARGET_PAGE_MASK;

    for(i = 0;i < CODE_GEN_PHYS_HASH_SIZE; i++) {

        for(tb = tb_phys_hash[i]; tb != NULL; tb = tb->phys_hash_next) {

            if (!(address + TARGET_PAGE_SIZE <= tb->pc ||

                  address >= tb->pc + tb->size)) {

                printf("ERROR invalidate: address=%08lx PC=%08lx size=%04x\n",

                       address, (long)tb->pc, tb->size);

            }

        }

    }

}

/* verify that all the pages have correct rights for code */

static void tb_page_check(void)

{

    TranslationBlock *tb;

    int i, flags1, flags2;

    for(i = 0;i < CODE_GEN_PHYS_HASH_SIZE; i++) {

        for(tb = tb_phys_hash[i]; tb != NULL; tb = tb->phys_hash_next) {

            flags1 = page_get_flags(tb->pc);

            flags2 = page_get_flags(tb->pc + tb->size - 1);

            if ((flags1 & PAGE_WRITE) || (flags2 & PAGE_WRITE)) {

                printf("ERROR page flags: PC=%08lx size=%04x f1=%x f2=%x\n",

                       (long)tb->pc, tb->size, flags1, flags2);

            }

        }

    }

}

static void tb_jmp_check(TranslationBlock *tb)

{

    TranslationBlock *tb1;

    unsigned int n1;

    /* suppress any remaining jumps to this TB */

    tb1 = tb->jmp_first;

    for(;;) {

        n1 = (long)tb1 & 3;

        tb1 = (TranslationBlock *)((long)tb1 & ~3);

        if (n1 == 2)

            break;

        tb1 = tb1->jmp_next[n1];

    }

    /* check end of list */

    if (tb1 != tb) {

        printf("ERROR: jmp_list from 0x%08lx\n", (long)tb);

    }

}

#endif

/* invalidate one TB */

static inline void tb_remove(TranslationBlock **ptb, TranslationBlock *tb,

                             int next_offset)

{

    TranslationBlock *tb1;

    for(;;) {

        tb1 = *ptb;

        if (tb1 == tb) {

            *ptb = *(TranslationBlock **)((char *)tb1 + next_offset);

            break;

        }

        ptb = (TranslationBlock **)((char *)tb1 + next_offset);

    }

}

static inline void tb_page_remove(TranslationBlock **ptb, TranslationBlock *tb)

{

    TranslationBlock *tb1;

    unsigned int n1;

    for(;;) {

        tb1 = *ptb;

        n1 = (long)tb1 & 3;

        tb1 = (TranslationBlock *)((long)tb1 & ~3);

        if (tb1 == tb) {

            *ptb = tb1->page_next[n1];

            break;

        }

        ptb = &tb1->page_next[n1];

    }

}

static inline void tb_jmp_remove(TranslationBlock *tb, int n)

{

    TranslationBlock *tb1, **ptb;

    unsigned int n1;

    ptb = &tb->jmp_next[n];

    tb1 = *ptb;

    if (tb1) {

        /* find tb(n) in circular list */

        for(;;) {

            tb1 = *ptb;

            n1 = (long)tb1 & 3;

            tb1 = (TranslationBlock *)((long)tb1 & ~3);

            if (n1 == n && tb1 == tb)

                break;

            if (n1 == 2) {

                ptb = &tb1->jmp_first;

            } else {

                ptb = &tb1->jmp_next[n1];

            }

        }

        /* now we can suppress tb(n) from the list */

        *ptb = tb->jmp_next[n];

        tb->jmp_next[n] = NULL;

    }

}

/* reset the jump entry 'n' of a TB so that it is not chained to

   another TB */

static inline void tb_reset_jump(TranslationBlock *tb, int n)

{

    tb_set_jmp_target(tb, n, (unsigned long)(tb->tc_ptr + tb->tb_next_offset[n]));

}

void tb_phys_invalidate(TranslationBlock *tb, target_ulong page_addr)

{

    CPUState *env;

    PageDesc *p;

    unsigned int h, n1;

    target_phys_addr_t phys_pc;

    TranslationBlock *tb1, *tb2;

    /* remove the TB from the hash list */

    phys_pc = tb->page_addr[0] + (tb->pc & ~TARGET_PAGE_MASK);

    h = tb_phys_hash_func(phys_pc);

    tb_remove(&tb_phys_hash[h], tb,

              offsetof(TranslationBlock, phys_hash_next));

    /* remove the TB from the page list */

    if (tb->page_addr[0] != page_addr) {

        p = page_find(tb->page_addr[0] >> TARGET_PAGE_BITS);

        tb_page_remove(&p->first_tb, tb);

        invalidate_page_bitmap(p);

    }

    if (tb->page_addr[1] != -1 && tb->page_addr[1] != page_addr) {

        p = page_find(tb->page_addr[1] >> TARGET_PAGE_BITS);

        tb_page_remove(&p->first_tb, tb);

        invalidate_page_bitmap(p);

    }

    tb_invalidated_flag = 1;

    /* remove the TB from the hash list */

    h = tb_jmp_cache_hash_func(tb->pc);

    for(env = first_cpu; env != NULL; env = env->next_cpu) {

        if (env->tb_jmp_cache[h] == tb)

            env->tb_jmp_cache[h] = NULL;

    }

    /* suppress this TB from the two jump lists */

    tb_jmp_remove(tb, 0);

    tb_jmp_remove(tb, 1);

    /* suppress any remaining jumps to this TB */

    tb1 = tb->jmp_first;

    for(;;) {

        n1 = (long)tb1 & 3;

        if (n1 == 2)

            break;

        tb1 = (TranslationBlock *)((long)tb1 & ~3);

        tb2 = tb1->jmp_next[n1];

        tb_reset_jump(tb1, n1);

        tb1->jmp_next[n1] = NULL;

        tb1 = tb2;

    }

    tb->jmp_first = (TranslationBlock *)((long)tb | 2); /* fail safe */

    tb_phys_invalidate_count++;

}

static inline void set_bits(uint8_t *tab, int start, int len)

{

    int end, mask, end1;

    end = start + len;

    tab += start >> 3;

    mask = 0xff << (start & 7);

    if ((start & ~7) == (end & ~7)) {

        if (start < end) {

            mask &= ~(0xff << (end & 7));

            *tab |= mask;

        }

    } else {

        *tab++ |= mask;

        start = (start + 8) & ~7;

        end1 = end & ~7;

        while (start < end1) {

            *tab++ = 0xff;

            start += 8;

        }

        if (start < end) {

            mask = ~(0xff << (end & 7));

            *tab |= mask;

        }

    }

}

static void build_page_bitmap(PageDesc *p)

{

    int n, tb_start, tb_end;

    TranslationBlock *tb;

    p->code_bitmap = qemu_mallocz(TARGET_PAGE_SIZE / 8);

    tb = p->first_tb;

    while (tb != NULL) {

        n = (long)tb & 3;

        tb = (TranslationBlock *)((long)tb & ~3);

        /* NOTE: this is subtle as a TB may span two physical pages */

        if (n == 0) {

            /* NOTE: tb_end may be after the end of the page, but

               it is not a problem */

            tb_start = tb->pc & ~TARGET_PAGE_MASK;

            tb_end = tb_start + tb->size;

            if (tb_end > TARGET_PAGE_SIZE)

                tb_end = TARGET_PAGE_SIZE;

        } else {

            tb_start = 0;

            tb_end = ((tb->pc + tb->size) & ~TARGET_PAGE_MASK);

        }

        set_bits(p->code_bitmap, tb_start, tb_end - tb_start);

        tb = tb->page_next[n];

    }

}

TranslationBlock *tb_gen_code(CPUState *env,

                              target_ulong pc, target_ulong cs_base,

                              int flags, int cflags)

{

    TranslationBlock *tb;

    uint8_t *tc_ptr;

    target_ulong phys_pc, phys_page2, virt_page2;

    int code_gen_size;

    phys_pc = get_phys_addr_code(env, pc);

    tb = tb_alloc(pc);

    if (!tb) {

        /* flush must be done */

        tb_flush(env);

        /* cannot fail at this point */

        tb = tb_alloc(pc);

        /* Don't forget to invalidate previous TB info.  */

        tb_invalidated_flag = 1;

    }

    tc_ptr = code_gen_ptr;

    tb->tc_ptr = tc_ptr;

    tb->cs_base = cs_base;

    tb->flags = flags;

    tb->cflags = cflags;

    cpu_gen_code(env, tb, &code_gen_size);

    code_gen_ptr = (void *)(((unsigned long)code_gen_ptr + code_gen_size + CODE_GEN_ALIGN - 1) & ~(CODE_GEN_ALIGN - 1));

    /* check next page if needed */

    virt_page2 = (pc + tb->size - 1) & TARGET_PAGE_MASK;

    phys_page2 = -1;

    if ((pc & TARGET_PAGE_MASK) != virt_page2) {

        phys_page2 = get_phys_addr_code(env, virt_page2);

    }

    tb_link_phys(tb, phys_pc, phys_page2);

    return tb;

}

/* invalidate all TBs which intersect with the target physical page

   starting in range [start;end[. NOTE: start and end must refer to

   the same physical page. 'is_cpu_write_access' should be true if called

   from a real cpu write access: the virtual CPU will exit the current

   TB if code is modified inside this TB. */

void tb_invalidate_phys_page_range(target_phys_addr_t start, target_phys_addr_t end,

                                   int is_cpu_write_access)

{

    TranslationBlock *tb, *tb_next, *saved_tb;

    CPUState *env = cpu_single_env;

    target_ulong tb_start, tb_end;

    PageDesc *p;

    int n;

#ifdef TARGET_HAS_PRECISE_SMC

    int current_tb_not_found = is_cpu_write_access;

    TranslationBlock *current_tb = NULL;

    int current_tb_modified = 0;

    target_ulong current_pc = 0;

    target_ulong current_cs_base = 0;

    int current_flags = 0;

#endif /* TARGET_HAS_PRECISE_SMC */

    p = page_find(start >> TARGET_PAGE_BITS);

    if (!p)

        return;

    if (!p->code_bitmap &&

        ++p->code_write_count >= SMC_BITMAP_USE_THRESHOLD &&

        is_cpu_write_access) {

        /* build code bitmap */

        build_page_bitmap(p);

    }

    /* we remove all the TBs in the range [start, end[ */

    /* XXX: see if in some cases it could be faster to invalidate all the code */

    tb = p->first_tb;

    while (tb != NULL) {

        n = (long)tb & 3;

        tb = (TranslationBlock *)((long)tb & ~3);

        tb_next = tb->page_next[n];

        /* NOTE: this is subtle as a TB may span two physical pages */

        if (n == 0) {

            /* NOTE: tb_end may be after the end of the page, but

               it is not a problem */

            tb_start = tb->page_addr[0] + (tb->pc & ~TARGET_PAGE_MASK);

            tb_end = tb_start + tb->size;

        } else {

            tb_start = tb->page_addr[1];

            tb_end = tb_start + ((tb->pc + tb->size) & ~TARGET_PAGE_MASK);

        }

        if (!(tb_end <= start || tb_start >= end)) {

#ifdef TARGET_HAS_PRECISE_SMC

            if (current_tb_not_found) {

                current_tb_not_found = 0;

                current_tb = NULL;

                if (env->mem_io_pc) {

                    /* now we have a real cpu fault */

                    current_tb = tb_find_pc(env->mem_io_pc);

                }

            }

            if (current_tb == tb &&

                (current_tb->cflags & CF_COUNT_MASK) != 1) {

                /* If we are modifying the current TB, we must stop

                its execution. We could be more precise by checking

                that the modification is after the current PC, but it

                would require a specialized function to partially

                restore the CPU state */

                current_tb_modified = 1;

                cpu_restore_state(current_tb, env,

                                  env->mem_io_pc, NULL);

                cpu_get_tb_cpu_state(env, &current_pc, &current_cs_base,

                                     &current_flags);

            }

#endif /* TARGET_HAS_PRECISE_SMC */

            /* we need to do that to handle the case where a signal

               occurs while doing tb_phys_invalidate() */

            saved_tb = NULL;

            if (env) {

                saved_tb = env->current_tb;

                env->current_tb = NULL;

            }

            tb_phys_invalidate(tb, -1);

            if (env) {

                env->current_tb = saved_tb;

                if (env->interrupt_request && env->current_tb)

                    cpu_interrupt(env, env->interrupt_request);

            }

        }

        tb = tb_next;

    }

#if !defined(CONFIG_USER_ONLY)

    /* if no code remaining, no need to continue to use slow writes */

    if (!p->first_tb) {

        invalidate_page_bitmap(p);

        if (is_cpu_write_access) {

            tlb_unprotect_code_phys(env, start, env->mem_io_vaddr);

        }

    }

#endif

#ifdef TARGET_HAS_PRECISE_SMC

    if (current_tb_modified) {

        /* we generate a block containing just the instruction

           modifying the memory. It will ensure that it cannot modify

           itself */

        env->current_tb = NULL;

        tb_gen_code(env, current_pc, current_cs_base, current_flags, 1);

        cpu_resume_from_signal(env, NULL);

    }

#endif

}

/* len must be <= 8 and start must be a multiple of len */

static inline void tb_invalidate_phys_page_fast(target_phys_addr_t start, int len)

{

    PageDesc *p;

    int offset, b;

#if 0

    if (1) {

        qemu_log("modifying code at 0x%x size=%d EIP=%x PC=%08x\n",

                  cpu_single_env->mem_io_vaddr, len,

                  cpu_single_env->eip,

                  cpu_single_env->eip + (long)cpu_single_env->segs[R_CS].base);

    }

#endif

    p = page_find(start >> TARGET_PAGE_BITS);

    if (!p)

        return;

    if (p->code_bitmap) {

        offset = start & ~TARGET_PAGE_MASK;

        b = p->code_bitmap[offset >> 3] >> (offset & 7);

        if (b & ((1 << len) - 1))

            goto do_invalidate;

    } else {

    do_invalidate:

        tb_invalidate_phys_page_range(start, start + len, 1);

    }

}

#if !defined(CONFIG_SOFTMMU)

static void tb_invalidate_phys_page(target_phys_addr_t addr,

                                    unsigned long pc, void *puc)

{

    TranslationBlock *tb;

    PageDesc *p;

    int n;

#ifdef TARGET_HAS_PRECISE_SMC

    TranslationBlock *current_tb = NULL;

    CPUState *env = cpu_single_env;

    int current_tb_modified = 0;

    target_ulong current_pc = 0;

    target_ulong current_cs_base = 0;

    int current_flags = 0;

#endif

    addr &= TARGET_PAGE_MASK;

    p = page_find(addr >> TARGET_PAGE_BITS);

    if (!p)

        return;

    tb = p->first_tb;

#ifdef TARGET_HAS_PRECISE_SMC

    if (tb && pc != 0) {

        current_tb = tb_find_pc(pc);

    }

#endif

    while (tb != NULL) {

        n = (long)tb & 3;

        tb = (TranslationBlock *)((long)tb & ~3);

#ifdef TARGET_HAS_PRECISE_SMC

        if (current_tb == tb &&

            (current_tb->cflags & CF_COUNT_MASK) != 1) {

                /* If we are modifying the current TB, we must stop

                   its execution. We could be more precise by checking

                   that the modification is after the current PC, but it

                   would require a specialized function to partially

                   restore the CPU state */

            current_tb_modified = 1;

            cpu_restore_state(current_tb, env, pc, puc);

            cpu_get_tb_cpu_state(env, &current_pc, &current_cs_base,

                                 &current_flags);

        }

#endif /* TARGET_HAS_PRECISE_SMC */

        tb_phys_invalidate(tb, addr);

        tb = tb->page_next[n];

    }

    p->first_tb = NULL;

#ifdef TARGET_HAS_PRECISE_SMC

    if (current_tb_modified) {

        /* we generate a block containing just the instruction

           modifying the memory. It will ensure that it cannot modify

           itself */

        env->current_tb = NULL;

        tb_gen_code(env, current_pc, current_cs_base, current_flags, 1);

        cpu_resume_from_signal(env, puc);

    }

#endif

}

#endif

/* add the tb in the target page and protect it if necessary */

static inline void tb_alloc_page(TranslationBlock *tb,

                                 unsigned int n, target_ulong page_addr)

{

    PageDesc *p;

    TranslationBlock *last_first_tb;

    tb->page_addr[n] = page_addr;

    p = page_find_alloc(page_addr >> TARGET_PAGE_BITS);

    tb->page_next[n] = p->first_tb;

    last_first_tb = p->first_tb;

    p->first_tb = (TranslationBlock *)((long)tb | n);

    invalidate_page_bitmap(p);

#if defined(TARGET_HAS_SMC) || 1

#if defined(CONFIG_USER_ONLY)

    if (p->flags & PAGE_WRITE) {

        target_ulong addr;

        PageDesc *p2;

        int prot;

        /* force the host page as non writable (writes will have a

           page fault + mprotect overhead) */

        page_addr &= qemu_host_page_mask;

        prot = 0;

        for(addr = page_addr; addr < page_addr + qemu_host_page_size;

            addr += TARGET_PAGE_SIZE) {

            p2 = page_find (addr >> TARGET_PAGE_BITS);

            if (!p2)

                continue;

            prot |= p2->flags;

            p2->flags &= ~PAGE_WRITE;

            page_get_flags(addr);

          }

        mprotect(g2h(page_addr), qemu_host_page_size,

                 (prot & PAGE_BITS) & ~PAGE_WRITE);

#ifdef DEBUG_TB_INVALIDATE

        printf("protecting code page: 0x" TARGET_FMT_lx "\n",

               page_addr);

#endif

    }

#else

    /* if some code is already present, then the pages are already

       protected. So we handle the case where only the first TB is

       allocated in a physical page */

    if (!last_first_tb) {

        tlb_protect_code(page_addr);

    }

#endif

#endif /* TARGET_HAS_SMC */

}

/* Allocate a new translation block. Flush the translation buffer if

   too many translation blocks or too much generated code. */

TranslationBlock *tb_alloc(target_ulong pc)

{

    TranslationBlock *tb;

    if (nb_tbs >= code_gen_max_blocks ||

        (code_gen_ptr - code_gen_buffer) >= code_gen_buffer_max_size)

        return NULL;

    tb = &tbs[nb_tbs++];

    tb->pc = pc;

    tb->cflags = 0;

    return tb;

}

void tb_free(TranslationBlock *tb)

{

    /* In practice this is mostly used for single use temporary TB

       Ignore the hard cases and just back up if this TB happens to

       be the last one generated.  */

    if (nb_tbs > 0 && tb == &tbs[nb_tbs - 1]) {

        code_gen_ptr = tb->tc_ptr;

        nb_tbs--;

    }

}

/* add a new TB and link it to the physical page tables. phys_page2 is

   (-1) to indicate that only one page contains the TB. */

void tb_link_phys(TranslationBlock *tb,

                  target_ulong phys_pc, target_ulong phys_page2)

{

    unsigned int h;

    TranslationBlock **ptb;

    /* Grab the mmap lock to stop another thread invalidating this TB

       before we are done.  */

    mmap_lock();

    /* add in the physical hash table */

    h = tb_phys_hash_func(phys_pc);

    ptb = &tb_phys_hash[h];

    tb->phys_hash_next = *ptb;

    *ptb = tb;

    /* add in the page list */

    tb_alloc_page(tb, 0, phys_pc & TARGET_PAGE_MASK);

    if (phys_page2 != -1)

        tb_alloc_page(tb, 1, phys_page2);

    else

        tb->page_addr[1] = -1;

    tb->jmp_first = (TranslationBlock *)((long)tb | 2);

    tb->jmp_next[0] = NULL;

    tb->jmp_next[1] = NULL;

    /* init original jump addresses */

    if (tb->tb_next_offset[0] != 0xffff)

        tb_reset_jump(tb, 0);

    if (tb->tb_next_offset[1] != 0xffff)

        tb_reset_jump(tb, 1);

#ifdef DEBUG_TB_CHECK

    tb_page_check();

#endif

    mmap_unlock();

}

/* find the TB 'tb' such that tb[0].tc_ptr <= tc_ptr <

   tb[1].tc_ptr. Return NULL if not found */

TranslationBlock *tb_find_pc(unsigned long tc_ptr)

{

    int m_min, m_max, m;

    unsigned long v;

    TranslationBlock *tb;

    if (nb_tbs <= 0)

        return NULL;

    if (tc_ptr < (unsigned long)code_gen_buffer ||

        tc_ptr >= (unsigned long)code_gen_ptr)

        return NULL;

    /* binary search (cf Knuth) */

    m_min = 0;

    m_max = nb_tbs - 1;

    while (m_min <= m_max) {

        m = (m_min + m_max) >> 1;

        tb = &tbs[m];

        v = (unsigned long)tb->tc_ptr;

        if (v == tc_ptr)

            return tb;

        else if (tc_ptr < v) {

            m_max = m - 1;

        } else {

            m_min = m + 1;

        }

    }

    return &tbs[m_max];

}

static void tb_reset_jump_recursive(TranslationBlock *tb);

static inline void tb_reset_jump_recursive2(TranslationBlock *tb, int n)

{

    TranslationBlock *tb1, *tb_next, **ptb;

    unsigned int n1;

    tb1 = tb->jmp_next[n];

    if (tb1 != NULL) {

        /* find head of list */

        for(;;) {

            n1 = (long)tb1 & 3;

            tb1 = (TranslationBlock *)((long)tb1 & ~3);

            if (n1 == 2)

                break;

            tb1 = tb1->jmp_next[n1];

        }

        /* we are now sure now that tb jumps to tb1 */

        tb_next = tb1;

        /* remove tb from the jmp_first list */

        ptb = &tb_next->jmp_first;

        for(;;) {

            tb1 = *ptb;

            n1 = (long)tb1 & 3;

            tb1 = (TranslationBlock *)((long)tb1 & ~3);

            if (n1 == n && tb1 == tb)

                break;

            ptb = &tb1->jmp_next[n1];

        }

        *ptb = tb->jmp_next[n];

        tb->jmp_next[n] = NULL;

        /* suppress the jump to next tb in generated code */

        tb_reset_jump(tb, n);

        /* suppress jumps in the tb on which we could have jumped */

        tb_reset_jump_recursive(tb_next);

    }

}

static void tb_reset_jump_recursive(TranslationBlock *tb)

{

    tb_reset_jump_recursive2(tb, 0);

    tb_reset_jump_recursive2(tb, 1);

}

#if defined(TARGET_HAS_ICE)

static void breakpoint_invalidate(CPUState *env, target_ulong pc)

{

    target_phys_addr_t addr;

    target_ulong pd;

    ram_addr_t ram_addr;

    PhysPageDesc *p;

    addr = cpu_get_phys_page_debug(env, pc);

    p = phys_page_find(addr >> TARGET_PAGE_BITS);

    if (!p) {

        pd = IO_MEM_UNASSIGNED;

    } else {

        pd = p->phys_offset;

    }

    ram_addr = (pd & TARGET_PAGE_MASK) | (pc & ~TARGET_PAGE_MASK);

    tb_invalidate_phys_page_range(ram_addr, ram_addr + 1, 0);

}

#endif

/* Add a watchpoint.  */

int cpu_watchpoint_insert(CPUState *env, target_ulong addr, target_ulong len,

                          int flags, CPUWatchpoint **watchpoint)

{

    target_ulong len_mask = ~(len - 1);

    CPUWatchpoint *wp;

    /* sanity checks: allow power-of-2 lengths, deny unaligned watchpoints */

    if ((len != 1 && len != 2 && len != 4 && len != 8) || (addr & ~len_mask)) {

        fprintf(stderr, "qemu: tried to set invalid watchpoint at "

                TARGET_FMT_lx ", len=" TARGET_FMT_lu "\n", addr, len);

        return -EINVAL;

    }

    wp = qemu_malloc(sizeof(*wp));

    wp->vaddr = addr;

    wp->len_mask = len_mask;

    wp->flags = flags;

    /* keep all GDB-injected watchpoints in front */

    if (flags & BP_GDB)

        TAILQ_INSERT_HEAD(&env->watchpoints, wp, entry);

    else

        TAILQ_INSERT_TAIL(&env->watchpoints, wp, entry);

    tlb_flush_page(env, addr);

    if (watchpoint)

        *watchpoint = wp;

    return 0;

}

/* Remove a specific watchpoint.  */

int cpu_watchpoint_remove(CPUState *env, target_ulong addr, target_ulong len,

                          int flags)

{

    target_ulong len_mask = ~(len - 1);

    CPUWatchpoint *wp;

    TAILQ_FOREACH(wp, &env->watchpoints, entry) {

        if (addr == wp->vaddr && len_mask == wp->len_mask

                && flags == (wp->flags & ~BP_WATCHPOINT_HIT)) {

            cpu_watchpoint_remove_by_ref(env, wp);

            return 0;

        }

    }

    return -ENOENT;

}

/* Remove a specific watchpoint by reference.  */

void cpu_watchpoint_remove_by_ref(CPUState *env, CPUWatchpoint *watchpoint)

{

    TAILQ_REMOVE(&env->watchpoints, watchpoint, entry);

    tlb_flush_page(env, watchpoint->vaddr);