<commit_before>#!/usr/bin/env python 
#
# Cloudlet Infrastructure for Mobile Computing
#
#   Author: <NAME> <<EMAIL>>
#
#   Copyright (C) 2011-2013 Carnegie Mellon University
#   Licensed under the Apache License, Version 2.0 (the "License");
#   you may not use this file except in compliance with the License.
#   You may obtain a copy of the License at
#
#       http://www.apache.org/licenses/LICENSE-2.0
#
#   Unless required by applicable law or agreed to in writing, software
#   distributed under the License is distributed on an "AS IS" BASIS,
#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#   See the License for the specific language governing permissions and
#   limitations under the License.
#

import sys
import os
import functools
import subprocess
import Memory
import Disk
import vmnetfs
import vmnetx
import stat
import delta
import xray
import hashlib
import libvirt
import shutil
import multiprocessing

from synthesis.db import api as db_api
from synthesis.db import table_def as db_table
from synthesis.Configuration import Const
from synthesis.Configuration import Options
from synthesis.Configuration import Discovery_Const
from synthesis.delta import DeltaList
from synthesis.delta import DeltaItem
from synthesis import msgpack
from synthesis.progressbar import AnimatedProgressBar

from xml.etree import ElementTree
from xml.etree.ElementTree import Element
from uuid import uuid4
from tempfile import NamedTemporaryFile
from time import time
from time import sleep
import threading
from optparse import OptionParser

from synthesis.tool import comp_lzma
from synthesis.tool import diff_files
from synthesis.tool import decomp_overlay
from synthesis import log as logging

LOG = logging.getLogger(__name__)


class CloudletGenerationError(Exception):
    pass


def wrap_vm_fault(function):
    """Wraps a method to catch exceptions related to instances.
    This decorator wraps a method to catch any exceptions and
    terminate the request gracefully.
    """
    @functools.wraps(function)
    def decorated_function(self, *args, **kwargs):
        try:
            return function(self, *args, **kwargs)
        except Exception, e:
            if hasattr(self, 'exception_handler'):
                self.exception_handler()
            kwargs.update(dict(zip(function.func_code.co_varnames[2:], args)))
            LOG.error("failed with : %s" % str(kwargs))

    return decorated_function

def libvirt_err_callback(ctxt, err):
    # we intentionally ignore seek error from libvirt since we have cause
    # that by using named pipe
    if err[3] == libvirt.VIR_ERR_ERROR and \
            err[0] == libvirt.VIR_FROM_STREAMS and \
            err[1] == libvirt.VIR_FROM_QEMU:
        pass
    elif err[3] == libvirt.VIR_ERR_WARNING:
        LOG.warning(err[2])
    elif err[3] == libvirt.VIR_ERR_ERROR:
        LOG.error(err[2])
libvirt.registerErrorHandler(f=libvirt_err_callback, ctx=None)


class VM_Overlay(threading.Thread):
    def __init__(self, base_disk, options, qemu_args=None,
            base_mem=None, base_diskmeta=None,
            base_memmeta=None, base_hashvalue=None,
            vm_xml=None, nova_util=None):
        # create user customized overlay.
        # First resume VM, then let user edit its VM
        # Finally, return disk/memory binary as an overlay
        # base_disk: path to base disk
        self.base_disk = os.path.abspath(base_disk)
        self.options = options
        self.vm_xml = vm_xml or None
        self.qemu_args = qemu_args or None
        (self.base_diskmeta, self.base_mem, self.base_memmeta) = \
                Const.get_basepath(self.base_disk, check_exist=False)
        self.base_mem = base_mem or self.base_mem
        self.base_diskmeta = base_diskmeta or self.base_diskmeta
        self.base_memmeta = base_memmeta or self.base_memmeta
        # use abs path
        self.base_mem = os.path.abspath(self.base_mem)
        self.base_diskmeta = os.path.abspath(self.base_diskmeta)
        self.base_memmeta = os.path.abspath(self.base_memmeta)
        self.nova_util = nova_util

        # find base vm's hashvalue from DB
        self.base_hashvalue = base_hashvalue or None
        if self.base_hashvalue == None:
            dbconn = db_api.DBConnector()
            basevm_list = dbconn.list_item(db_table.BaseVM)
            for basevm_row in basevm_list:
                basevm_row_disk = os.path.abspath(basevm_row.disk_path)
                if basevm_row_disk == self.base_disk:
                    self.base_hashvalue = basevm_row.hash_value
            if self.base_hashvalue == None:
                msg = "Cannot find hashvalue for %s" % self.base_disk
                raise CloudletGenerationError(msg)

        self.log_path = os.path.join(os.path.dirname(self.base_disk), \
                                os.path.basename(self.base_disk) + Const.OVERLAY_LOG)
        threading.Thread.__init__(self, target=self.create_overlay)

    def resume_basevm(self):
        if (self.options == None) or (isinstance(self.options, Options) == False):
            raise CloudletGenerationError("Given option class is invalid: %s" % str(self.options))

        # filename for overlay VM
        self.qemu_logfile = NamedTemporaryFile(prefix="cloudlet-qemu-log-", delete=False)
        os.chmod(self.qemu_logfile.name, stat.S_IROTH | stat.S_IWOTH | \
                stat.S_IRUSR | stat.S_IWUSR | stat.S_IRGRP | stat.S_IWGRP)

        # option for data-intensive application
        self.cache_manager = None
        self.mount_point = None
        if self.options.DATA_SOURCE_URI != None:
            cache_manager, mount_point = self._start_emulate_cache_fs()

        # make FUSE disk & memory
        self.fuse = run_fuse(Const.VMNETFS_PATH, Const.CHUNK_SIZE,
                self.base_disk, os.path.getsize(self.base_disk),
                self.base_mem, os.path.getsize(self.base_mem))
        self.modified_disk = os.path.join(self.fuse.mountpoint, 'disk', 'image')
        self.base_mem_fuse = os.path.join(self.fuse.mountpoint, 'memory', 'image')
        self.modified_mem = NamedTemporaryFile(prefix="cloudlet-mem-", delete=False)
        # monitor modified chunks
        stream_modified = os.path.join(self.fuse.mountpoint, 'disk', 'streams', 'chunks_modified')
        stream_access = os.path.join(self.fuse.mountpoint, 'disk', 'streams', 'chunks_accessed')
        memory_access = os.path.join(self.fuse.mountpoint, 'memory', 'streams', 'chunks_accessed')
        self.fuse_stream_monitor = vmnetfs.StreamMonitor()
        self.fuse_stream_monitor.add_path(stream_modified, vmnetfs.StreamMonitor.DISK_MODIFY)
        self.fuse_stream_monitor.add_path(stream_access, vmnetfs.StreamMonitor.DISK_ACCESS)
        self.fuse_stream_monitor.add_path(memory_access, vmnetfs.StreamMonitor.MEMORY_ACCESS)
        self.fuse_stream_monitor.start()
        self.qemu_monitor = vmnetfs.FileMonitor(self.qemu_logfile.name, vmnetfs.FileMonitor.QEMU_LOG)
        self.qemu_monitor.start()

        # 1. resume & get modified disk
        LOG.info("[INFO] * Overlay creation configuration")
        LOG.info("[INFO]  - %s" % str(self.options))
        conn = get_libvirt_connection()
        self.machine = run_snapshot(conn, self.modified_disk, self.base_mem_fuse, \
                qemu_logfile=self.qemu_logfile.name, qemu_args=self.qemu_args,
                new_xml=self.vm_xml)
        return self.machine

    @wrap_vm_fault
    def create_overlay(self):
        # 2. get montoring info
        monitoring_info = _get_monitoring_info(self.machine, self.options,
                self.base_memmeta, self.base_diskmeta,
                self.fuse_stream_monitor,
                self.base_disk, self.base_mem,
                self.modified_disk, self.modified_mem.name,
                self.qemu_logfile, 
                nova_util=self.nova_util)
        self._terminate_vm()

        # 3. get overlay VM
        overlay_deltalist = get_overlay_deltalist(monitoring_info, self.options,
                self.base_disk, self.base_mem, self.base_memmeta, 
                self.modified_disk, self.modified_mem.name)

        # 4. create_overlayfile
        image_name = os.path.basename(self.base_disk).split(".")[0]
        dir_path = os.path.dirname(self.base_mem)
        overlay_prefix = os.path.join(dir_path,
                image_name+Const.OVERLAY_FILE_PREFIX)
        overlay_metapath = os.path.join(dir_path, image_name+Const.OVERLAY_META)

        self.overlay_metafile, self.overlay_files = \
                generate_overlayfile(overlay_deltalist, self.options, 
                self.base_hashvalue, os.path.getsize(self.modified_disk), 
                os.path.getsize(self.modified_mem.name),
                overlay_metapath, overlay_prefix)

        # option for data-intensive application
        if self.options.DATA_SOURCE_URI != None:
            overlay_uri_meta = os.path.join(dir_path, image_name+Const.OVERLAY_URIs)
            self.overlay_uri_meta =  self._terminate_emulate_cache_fs(overlay_uri_meta)

        # 5. terminting
        self.fuse.terminate()
        self.fuse_stream_monitor.terminate()
        self.qemu_monitor.terminate()
        self.fuse_stream_monitor.join()
        self.qemu_monitor.join()
        self.fuse.join()
        if hasattr(self, "cache_manager") and self.cache_manager != None:
            self.cache_manager.terminate()
            self.cache_manager.join()
        if hasattr(self, "mount_point") and self.mount_point != None and os.path.lexists(self.mount_point):
            os.unlink(self.mount_point)

        if self.options.MEMORY_SAVE_PATH:
            LOG.debug("[INFO] moving memory sansphost to %s" % self.options.MEMORY_SAVE_PATH)
            shutil.move(self.modified_mem.name, self.options.MEMORY_SAVE_PATH)
        else:
            os.unlink(self.modified_mem.name)

        if os.path.exists(self.qemu_logfile.name):
            os.remove(self.qemu_logfile.name)

    def _terminate_vm(self):
        if self.machine is not None:
            machine_id = self.machine.ID()
            conn = get_libvirt_connection()
            try:
                for each_id in conn.listDomainsID():
                    if each_id == machine_id:
                        each_machine = conn.lookupByID(machine_id)
                        state, reason = each_machine.state(0)
                        if state != libvirt.VIR_DOMAIN_SHUTOFF:
                            each_machine.destroy()
            except libvirt.libvirtError, e:
                pass
            self.machine = None

    def exception_handler(self):
        # make sure to destory the VM
        self._terminate_vm()

    def _start_emulate_cache_fs(self):
        # check samba
        if os.path.exists(Discovery_Const.HOST_SAMBA_DIR) == False:
            msg = "Cloudlet does not have samba directory at %s\n" % \
                    Discovery_Const.HOST_SAMBA_DIR
            msg += "You can change samba path at Configuration.py\n"
            raise CloudletGenerationError(msg)
        # fetch URI to cache
        try:
            cache_manager = cache.CacheManager(Discovery_Const.CACHE_ROOT, \
                    Discovery_Const.REDIS_ADDR, Discovery_Const.CACHE_FUSE_BINPATH)
                    
            cache_manager.start()
            self.compiled_list = cache.Util.get_compiled_URIs( \
                    cache_manager.cache_dir, self.options.DATA_SOURCE_URI)
            #cache_manager.fetch_compiled_URIs(compiled_list)
            cache_fuse = cache_manager.launch_fuse(self.compiled_list)
            LOG.debug("[INFO] cache fuse mount : %s, %s\n" % \
                    (cache_fuse.url_root, cache_fuse.mountpoint))
        except cache.CachingError, e:
            msg = "Cannot retrieve data from URI: %s" % str(e)
            raise CloudletGenerationError(msg)
        # create symbolic link to samba dir
        mount_point = os.path.join(Discovery_Const.HOST_SAMBA_DIR, cache_fuse.url_root)
        if os.path.lexists(mount_point) == True:
            os.unlink(mount_point)
        os.symlink(cache_fuse.mountpoint, mount_point)
        LOG.debug("[INFO] create symbolic link to %s" % mount_point)

        return cache_manager, cache_fuse.mountpoint

    def _terminate_emulate_cache_fs(self, overlay_uri_meta):
        uri_list = []
        for each_info in self.compiled_list:
            uri_list.append(each_info.get_uri())
        uri_data = {
                'source_URI' : self.options.DATA_SOURCE_URI,
                'compiled_URIs' : uri_list,
                }
        with open(overlay_uri_meta, "w+b") as f:
            import json
            f.write(json.dumps(uri_data))
        return overlay_uri_meta


class _MonitoringInfo(object):
    BASEDISK_HASHLIST       = "basedisk_hashlist"
    BASEMEM_HASHLIST        = "basemem_hashlist"
    DISK_MODIFIED_BLOCKS    = "disk_modified_block" # from fuse monitoring
    DISK_USED_BLOCKS        = "disk_used_block" # from xray support
    DISK_FREE_BLOCKS        = "disk_free_block"
    MEMORY_FREE_BLOCKS      = "memory_free_block"

    def __init__(self, properties):
        for k, v in properties.iteritems():
            setattr(self, k, v)

    def __str__(self):
        ret = ""
        for k, v in self.__dict__.iteritems():
            ret += "%s\t:\t%s\n" % (str(k), str(v))
        return ret

    def __getitem__(self, item):
        return self.__dict__[item]


class SynthesizedVM(threading.Thread):
    def __init__(self, launch_disk, launch_mem, fuse, disk_only=False, qemu_args=None, **kwargs):
        # kwargs
        self.vm_xml = kwargs.get("vm_xml", None)
        self.LOG = kwargs.get("log", None)
        if self.LOG == None:
            self.LOG = open("/dev/null", "w+b")

        # monitor modified chunks
        self.machine = None
        self.disk_only = disk_only
        self.qemu_args = qemu_args
        self.fuse = fuse
        self.launch_disk = launch_disk
        self.launch_mem = launch_mem
        self.qemu_logfile = NamedTemporaryFile(prefix="cloudlet-qemu-log-", delete=False)
        os.chmod(self.qemu_logfile.name, stat.S_IROTH | stat.S_IWOTH | \
                stat.S_IRUSR | stat.S_IWUSR | stat.S_IRGRP | stat.S_IWGRP)
        self.resumed_disk = os.path.join(fuse.mountpoint, 'disk', 'image')
        self.resumed_mem = os.path.join(fuse.mountpoint, 'memory', 'image')
        self.stream_modified = os.path.join(fuse.mountpoint, 'disk', 'streams', 'chunks_modified')
        self.stream_disk_access = os.path.join(fuse.mountpoint, 'disk', 'streams', 'chunks_accessed')
        self.stream_memory_access = os.path.join(fuse.mountpoint, 'memory', 'streams', 'chunks_accessed')
        self.monitor = vmnetfs.StreamMonitor()
        self.monitor.add_path(self.stream_modified, vmnetfs.StreamMonitor.DISK_MODIFY)
        self.monitor.add_path(self.stream_disk_access, vmnetfs.StreamMonitor.DISK_ACCESS)
        self.monitor.add_path(self.stream_memory_access, vmnetfs.StreamMonitor.MEMORY_ACCESS)
        self.monitor.start()
        self.qemu_monitor = vmnetfs.FileMonitor(self.qemu_logfile.name, vmnetfs.FileMonitor.QEMU_LOG)
        self.qemu_monitor.start()
        threading.Thread.__init__(self, target=self.resume)

    def resume(self):
        #resume VM
        conn = get_libvirt_connection()
        self.resume_time = {'time':-100}
        try:
            if self.disk_only:
                # edit default XML to have new disk path
                conn = get_libvirt_connection()
                xml = ElementTree.fromstring(open(Const.TEMPLATE_XML, "r").read())
                new_xml_string = _convert_xml(xml, conn, disk_path=self.resumed_disk, \
                        uuid=str(uuid4()), qemu_args=self.qemu_args)
                self.machine = run_vm(conn, new_xml_string, vnc_disable=True)
            else:
                self.machine = run_snapshot(conn, self.resumed_disk, self.resumed_mem,
                        qemu_logfile=self.qemu_logfile.name, resume_time=self.resume_time,
                        qemu_args=self.qemu_args, new_xml=self.vm_xml)
        except Exception as e:
            sys.stdout.write(str(e)+"\n")

        return self.machine

    def terminate(self):
        try:
            if self.machine:
                self.machine.destroy()
        except libvirt.libvirtError as e:
            pass

        # terminate
        self.fuse.terminate()
        self.monitor.terminate()
        self.qemu_monitor.terminate()
        self.monitor.join()
        self.qemu_monitor.join()

        # delete all temporary file
        if os.path.exists(self.launch_disk):
            os.unlink(self.launch_disk)
        if os.path.exists(self.launch_mem):
            os.unlink(self.launch_mem)
        if os.path.exists(self.qemu_logfile.name):
            os.unlink(self.qemu_logfile.name)


def _create_overlay_meta(base_hash, overlay_metafile, modified_disksize, modified_memsize,
        blob_info):
    fout = open(overlay_metafile, "wrb")

    meta_dict = dict()
    meta_dict[Const.META_BASE_VM_SHA256] = base_hash
    meta_dict[Const.META_RESUME_VM_DISK_SIZE] = long(modified_disksize)
    meta_dict[Const.META_RESUME_VM_MEMORY_SIZE] = long(modified_memsize)
    meta_dict[Const.META_OVERLAY_FILES] = blob_info

    serialized = msgpack.packb(meta_dict)
    fout.write(serialized)
    fout.close()


def _update_overlay_meta(original_meta, new_path, blob_info=None):
    fout = open(new_path, "wrb")

    if blob_info:
        original_meta[Const.META_OVERLAY_FILES] = blob_info
    serialized = msgpack.packb(original_meta)
    fout.write(serialized)
    fout.close()


def _test_dma_accuracy(dma_dict, disk_deltalist, mem_deltalist):
    dma_start_time = time()
    dma_read_counter = 0
    dma_write_counter = 0
    dma_read_overlay_dedup = 0
    dma_write_overlay_dedup = 0
    dma_read_base_dedup = 0
    dma_write_base_dedup = 0
    disk_delta_dict = dict([(delta.offset/Const.CHUNK_SIZE, delta) for delta in disk_deltalist])
    mem_delta_dict = dict([(delta.offset/Const.CHUNK_SIZE, delta) for delta in mem_deltalist])
    for dma_disk_chunk in dma_dict.keys():
        item = dma_dict.get(dma_disk_chunk)
        is_dma_read = item['read']
        dma_mem_chunk = item['mem_chunk']
        if is_dma_read:
            dma_read_counter += 1
        else:
            dma_write_counter += 1

        disk_delta = disk_delta_dict.get(dma_disk_chunk, None)
        if disk_delta:
            # first search at overlay disk
            if disk_delta.ref_id != DeltaItem.REF_OVERLAY_MEM:
#                LOG.info("dma disk chunk is same, but is it not deduped with overlay mem(%d)" \
#                        % (disk_delta.ref_id))
                continue
            delta_mem_chunk = disk_delta.data/Const.CHUNK_SIZE
            if delta_mem_chunk == dma_mem_chunk:
                if is_dma_read:
                    dma_read_overlay_dedup += 1
                else:
                    dma_write_overlay_dedup += 1
        else:
            # search at overlay mem
            mem_delta = mem_delta_dict.get(dma_mem_chunk, None)
            if mem_delta:
                if mem_delta.ref_id != DeltaItem.REF_BASE_DISK:
#                    LOG.info("dma memory chunk is same, but is it not deduped with base disk(%d)" \
#                            % (mem_delta.ref_id))
                    continue
                delta_disk_chunk = mem_delta.data/Const.CHUNK_SIZE
                if delta_disk_chunk == dma_disk_chunk:
                    if is_dma_read:
                        dma_read_base_dedup += 1
                    else:
                        dma_write_base_dedup += 1

    dma_end_time = time()
    LOG.debug("[DMA] Total DMA: %ld\n " % (len(dma_dict)))
    LOG.debug("[DMA] Total DMA READ: %ld, WRITE: %ld\n " % (dma_read_counter, dma_write_counter))
    LOG.debug("[DMA] WASTED TIME: %f\n " % (dma_end_time-dma_start_time))
    LOG.debug("[DMA] 1) DMA READ Overlay Deduplication: %ld(%f %%)\n " % \
            (dma_read_overlay_dedup, 100.0*dma_read_overlay_dedup/dma_read_counter))
    LOG.debug("[DMA]    DMA READ Base Deduplication: %ld(%f %%)\n " % \
            (dma_read_base_dedup, 100.0*dma_read_base_dedup/dma_read_counter))
    LOG.debug("[DMA] 2) DMA WRITE Overlay Deduplication: %ld(%f %%)\n " % \
            (dma_write_overlay_dedup, 100.0*dma_write_overlay_dedup/dma_write_counter))
    LOG.debug("[DMA]    DMA WRITE Base Deduplication: %ld(%f %%)\n " % \
            (dma_write_base_dedup, 100.0*dma_write_base_dedup/dma_write_counter))


def _convert_xml(xml, conn, vm_name=None, disk_path=None, uuid=None, \
        logfile=None, qemu_args=None):

    # delete padding
    padding_element = xml.find("description")
    if padding_element != None:
        xml.remove(padding_element)

    if vm_name != None:
        name_element = xml.find('name')
        if name_element == None:
            raise CloudletGenerationError("Malfomed XML input: %s", Const.TEMPLATE_XML)
        name_element.text = vm_name

    old_uuid = None
    if uuid != None:
        uuid_element = xml.find('uuid')
        old_uuid = str(uuid_element.text)
        uuid_element.text = str(uuid)

        # update sysinfo entry's uuid if it exist
        # it has to match with uuid of the VM
        sysinfo_entries = xml.findall('sysinfo/system/entry')
        for entry in sysinfo_entries:
            if(entry.attrib['name'] == 'uuid'):
                entry.text = str(uuid)

    # Use custom QEMU
    qemu_emulator = xml.find('devices/emulator')
    if qemu_emulator == None:
        qemu_emulator = Element("emulator")
        device_element = xml.find("devices")
        device_element.append(qemu_emulator)
    qemu_emulator.text = Const.QEMU_BIN_PATH

    # disk path is required
    if disk_path == None:
        raise CloudletGenerationError("Need disk_path to run new VM")

    # find all disk element(hdd, cdrom)
    disk_elements = xml.findall('devices/disk')
    hdd_source = None
    cdrom_source = None
    for disk_element in disk_elements:
        disk_type = disk_element.attrib['device']
        if disk_type == 'disk':
            hdd_source = disk_element.find('source')
            hdd_driver = disk_element.find("driver")
            if hdd_driver != None and hdd_driver.get("type", None) != None:
                hdd_driver.set("type", "raw")
        if disk_type == 'cdrom':
            cdrom_source = disk_element.find('source')

    # hdd path setting
    if hdd_source == None:
        raise CloudletGenerationError("Malfomed XML input: %s", Const.TEMPLATE_XML)
    hdd_source.set("file", os.path.abspath(disk_path))

    # ovf path setting
    if cdrom_source != None:
        cdrom_source.set("file", os.path.abspath(Const.TEMPLATE_OVF))

    # append QEMU-argument
    if logfile != None:
        qemu_xmlns="http://libvirt.org/schemas/domain/qemu/1.0"
        qemu_element = xml.find("{%s}commandline" % qemu_xmlns)
        if qemu_element == None:
            qemu_element = Element("{%s}commandline" % qemu_xmlns)
            xml.append(qemu_element)

        # remove previsou cloudlet argument if it is
        argument_list = qemu_element.findall("{%s}arg" % qemu_xmlns)
        remove_list = list()
        for argument_item in argument_list:
            arg_value = argument_item.get('value').strip() 
            if (arg_value== '-cloudlet') or (arg_value.startswith('logfile=')):
                remove_list.append(argument_item)
        for item in remove_list:
            qemu_element.remove(item)

        # append new cloudlet logpath
        qemu_element.append(Element("{%s}arg" % qemu_xmlns, {'value':'-cloudlet'}))
        qemu_element.append(Element("{%s}arg" % qemu_xmlns, {'value':"logfile=%s" % logfile}))

    # append qemu argument give from user
    if qemu_args:
        qemu_xmlns="http://libvirt.org/schemas/domain/qemu/1.0"
        qemu_element = xml.find("{%s}commandline" % qemu_xmlns)
        if qemu_element == None:
            qemu_element = Element("{%s}commandline" % qemu_xmlns)
            xml.append(qemu_element)
        for each_argument in qemu_args:
            qemu_element.append(Element("{%s}arg" % qemu_xmlns, {'value':each_argument}))

    device_element = xml.find("devices")
    console_element = device_element.find("console")
    if console_element != None:
        device_element.remove(console_element)

    # drop original security label
    # TODO: cope with appropriate security model
    sec_element = xml.find("seclabel")
    if sec_element != None:
        xml.remove(sec_element)
    network_element = device_element.find("interface")
    network_filter = network_element.find("filterref")
    if network_filter != None:
        network_element.remove(network_filter)

    new_xml_str = ElementTree.tostring(xml)
    if old_uuid != None and uuid != None:
        new_xml_str = new_xml_str.replace(old_uuid, str(uuid))
    return new_xml_str


def _get_monitoring_info(machine, options,
        base_memmeta, base_diskmeta,
        fuse_stream_monitor,
        base_disk, base_mem,
        modified_disk, modified_mem,
        qemu_logfile, nova_util=None):
    ''' return montioring information including
        1) base vm hash list
        2) used/freed disk block list
        3) freed memory page
    '''

    # 1-2. Stop monitoring for memory access (snapshot will create a lot of access)
    fuse_stream_monitor.del_path(vmnetfs.StreamMonitor.MEMORY_ACCESS)
    # TODO: support stream of modified memory rather than tmp file
    if not options.DISK_ONLY:
        save_mem_snapshot(machine, modified_mem, nova_util=nova_util)

    # 1-3. get hashlist of base memory and disk
    basemem_hashlist = Memory.base_hashlist(base_memmeta)
    basedisk_hashlist = Disk.base_hashlist(base_diskmeta)

    # 1-4. get dma & discard information
    if options.TRIM_SUPPORT:
        dma_dict, trim_dict = Disk.parse_qemu_log(qemu_logfile.name, Const.CHUNK_SIZE)
        if len(trim_dict) == 0:
            LOG.warning("No TRIM Discard, Check /etc/fstab configuration")
    else:
        trim_dict = dict()
    free_memory_dict = dict()

    # 1-5. get used sector information from x-ray
    used_blocks_dict = None
    if options.XRAY_SUPPORT:
        used_blocks_dict = xray.get_used_blocks(modified_disk)

    m_chunk_dict = fuse_stream_monitor.modified_chunk_dict

    info_dict = dict()
    info_dict[_MonitoringInfo.BASEDISK_HASHLIST] = basedisk_hashlist
    info_dict[_MonitoringInfo.BASEMEM_HASHLIST] = basemem_hashlist
    info_dict[_MonitoringInfo.DISK_USED_BLOCKS] = used_blocks_dict
    info_dict[_MonitoringInfo.DISK_MODIFIED_BLOCKS] = m_chunk_dict
    info_dict[_MonitoringInfo.DISK_FREE_BLOCKS] = trim_dict
    info_dict[_MonitoringInfo.MEMORY_FREE_BLOCKS] = free_memory_dict
    monitoring_info = _MonitoringInfo(info_dict)
    return monitoring_info


def copy_disk(in_path, out_path):
    LOG.info("Copying disk image to %s" % out_path)
    cmd = ["cp",  "%s" % (in_path), "%s" % (out_path)]
    cp_proc = subprocess.Popen(cmd, close_fds=True)
    cp_proc.wait()
    if cp_proc.returncode != 0:
        raise IOError("Copy failed: from %s to %s " % (in_path, out_path))


def get_libvirt_connection():
    conn = libvirt.open("qemu:///session")
    return conn


def get_overlay_deltalist(monitoring_info, options,
        base_image, base_mem, base_memmeta, 
        modified_disk, modified_mem,
        old_deltalist=None):
    '''return overlay deltalist
    Get difference between base vm (base_image, base_mem) and 
    launch vm (modified_disk, modified_mem) using monitoring information

    Args:
        prev_mem_deltalist : Option only for creating_residue.
            Different from disk, we create whole memory snapshot even for residue.
            So, to get the precise difference between previous memory overlay,
            we need previous memory deltalist
    '''

    INFO = _MonitoringInfo
    basedisk_hashlist = getattr(monitoring_info, INFO.BASEDISK_HASHLIST, None)
    basemem_hashlist = getattr(monitoring_info, INFO.BASEMEM_HASHLIST, None)
    free_memory_dict = getattr(monitoring_info, INFO.MEMORY_FREE_BLOCKS, None)
    m_chunk_dict = getattr(monitoring_info, INFO.DISK_MODIFIED_BLOCKS, None)
    trim_dict = getattr(monitoring_info, INFO.DISK_FREE_BLOCKS, None)
    used_blocks_dict = getattr(monitoring_info, INFO.DISK_USED_BLOCKS, None)
    dma_dict = dict()

    # 2-1. get memory overlay
    if options.DISK_ONLY:
        mem_deltalist = list()
    else:
        mem_deltalist= Memory.create_memory_deltalist(modified_mem,
                basemem_meta=base_memmeta, basemem_path=base_mem,
                apply_free_memory=options.FREE_SUPPORT,
                free_memory_info=free_memory_dict)
        if old_deltalist and len(old_deltalist) > 0:
            diff_deltalist = delta.residue_diff_deltalists(old_deltalist,
                    mem_deltalist, base_mem)
            mem_deltalist = diff_deltalist

    # 2-2. get disk overlay
    disk_statistics = dict()
    disk_deltalist = Disk.create_disk_deltalist(modified_disk,
        m_chunk_dict, Const.CHUNK_SIZE,
        basedisk_hashlist=basedisk_hashlist, basedisk_path=base_image,
        trim_dict=trim_dict,
        apply_discard = True,
        dma_dict=dma_dict,
        used_blocks_dict=used_blocks_dict,
        ret_statistics=disk_statistics)
        


    # 2-3. Merge disk & memory delta_list to generate overlay file
    # deduplication
    merged_deltalist = delta.create_overlay(
            mem_deltalist, Memory.Memory.RAM_PAGE_SIZE,
            disk_deltalist, Const.CHUNK_SIZE,
            basedisk_hashlist=basedisk_hashlist,
            basemem_hashlist=basemem_hashlist)
            

    free_memory_dict = getattr(monitoring_info, _MonitoringInfo.MEMORY_FREE_BLOCKS, None)
    free_pfn_counter = long(free_memory_dict.get("freed_counter", 0))
    disk_discarded_count = disk_statistics.get('trimed', 0)
    DeltaList.statistics(merged_deltalist, 
            mem_discarded=free_pfn_counter,
            disk_discarded=disk_discarded_count)

    return merged_deltalist


def generate_overlayfile(overlay_deltalist, options, 
        base_hashvalue, launchdisk_size, launchmem_size,
        overlay_metapath, overlayfile_prefix):
    ''' generate overlay metafile and file
    Return:
        [overlay_metapath, [overlayfilepath1, overlayfilepath2]]
    '''

    # Compression
    LOG.info("[LZMA] Compressing overlay blobs")
    blob_list = delta.divide_blobs(overlay_deltalist, overlayfile_prefix,
            Const.OVERLAY_BLOB_SIZE_KB, Const.CHUNK_SIZE,
            Memory.Memory.RAM_PAGE_SIZE)

    # create metadata
    if not options.DISK_ONLY:
        _create_overlay_meta(base_hashvalue, overlay_metapath,
                launchdisk_size, launchmem_size, blob_list)
    else:
        _create_overlay_meta(base_hashvalue, overlay_metapath,
                launchdisk_size, launchmem_size, blob_list)

    overlay_files = [item[Const.META_OVERLAY_FILE_NAME] for item in blob_list]
    dirpath = os.path.dirname(overlayfile_prefix)
    overlay_files = [os.path.join(dirpath, item) for item in overlay_files]

    return overlay_metapath, overlay_files


def run_delta_compression(output_list, **kwargs):
    # kwargs
    # LOG = log object for nova
    # nova_util = nova_util is executioin wrapper for nova framework
    #           You should use nova_util in OpenStack, or subprocess
    #           will be returned without finishing their work
    # custom_delta
    log = kwargs.get('log', None)
    nova_util = kwargs.get('nova_util', None)
    custom_delta = kwargs.get('custom_delta', False)

    # xdelta and compression
    ret_files = []
    for (base, modified, overlay) in output_list:
        start_time = time()

        # xdelta
        if custom_delta:
            diff_files(base, modified, overlay, nova_util=nova_util)
        else:
            diff_files(base, modified, overlay, nova_util=nova_util)
        LOG.info('[TIME] time for creating overlay : ', str(time()-start_time))
        LOG.info('[TIME](%d)-(%d)=(%d): ' % (os.path.getsize(base), os.path.getsize(modified), os.path.getsize(overlay)))

        # compression
        comp = overlay + '.lzma'
        comp, time1 = comp_lzma(overlay, comp, nova_util=nova_util)
        ret_files.append(comp)

        # remove temporary files
        os.remove(modified)
        os.remove(overlay)

    return ret_files


def recover_launchVM(base_image, meta_info, overlay_file, **kwargs):
    # kwargs
    # skip_validation   :   skip sha1 validation
    # LOG = log object for nova
    # nova_util = nova_util is executioin wrapper for nova framework
    #           You should use nova_util in OpenStack, or subprocess
    #           will be returned without finishing their work
    base_mem = kwargs.get('base_mem', None)
    base_diskmeta = kwargs.get('base_diskmeta', None)
    base_memmeta = kwargs.get('base_memmeta', None)

    if (not base_mem) or (not base_diskmeta) or (not base_memmeta):
        (base_diskmeta, base_mem, base_memmeta) = \
                Const.get_basepath(base_image, check_exist=True)
    launch_mem = NamedTemporaryFile(prefix="cloudlet-launch-mem-", delete=False)
    launch_disk = NamedTemporaryFile(prefix="cloudlet-launch-disk-", delete=False)

    # Get modified list from overlay_meta
    vm_disk_size = meta_info[Const.META_RESUME_VM_DISK_SIZE]
    vm_memory_size = meta_info[Const.META_RESUME_VM_MEMORY_SIZE]
    memory_chunk_list = list()
    disk_chunk_list = list()
    for each_file in meta_info[Const.META_OVERLAY_FILES]:
        memory_chunks = each_file[Const.META_OVERLAY_FILE_MEMORY_CHUNKS]
        disk_chunks = each_file[Const.META_OVERLAY_FILE_DISK_CHUNKS]
        memory_chunk_list.extend(["%ld:0" % item for item in memory_chunks])
        disk_chunk_list.extend(["%ld:0" % item for item in disk_chunks])
    disk_overlay_map = ','.join(disk_chunk_list)
    memory_overlay_map = ','.join(memory_chunk_list)

    # make FUSE disk & memory
    kwargs['meta_info'] = meta_info
    fuse = run_fuse(Const.VMNETFS_PATH, Const.CHUNK_SIZE,
            base_image, vm_disk_size, base_mem, vm_memory_size,
            resumed_disk=launch_disk.name,  disk_overlay_map=disk_overlay_map,
            resumed_memory=launch_mem.name, memory_overlay_map=memory_overlay_map,
            **kwargs)
    LOG.info("Start FUSE")

    # Recover Modified Memory
    named_pipename = overlay_file+".fifo"
    os.mkfifo(named_pipename)

    delta_proc = delta.Recovered_delta(base_image, base_mem, overlay_file, \
            launch_mem.name, vm_memory_size,
            launch_disk.name, vm_disk_size, Const.CHUNK_SIZE,
            out_pipename=named_pipename)
    fuse_thread = vmnetfs.FuseFeedingThread(fuse,
            named_pipename, delta.Recovered_delta.END_OF_PIPE)
    return [launch_disk.name, launch_mem.name, fuse, delta_proc, fuse_thread]


def run_fuse(bin_path, chunk_size, original_disk, fuse_disk_size,
        original_memory, fuse_memory_size,
        resumed_disk=None, disk_overlay_map=None,
        resumed_memory=None, memory_overlay_map=None,
        **kwargs):
    if fuse_disk_size <= 0:
        raise CloudletGenerationError("FUSE disk size should be bigger than 0")
    if original_memory != None and fuse_memory_size <= 0:
        raise CloudletGenerationError("FUSE memory size should be bigger than 0")

    # run fuse file system
    resumed_disk = os.path.abspath(resumed_disk) if resumed_disk else ""
    resumed_memory = os.path.abspath(resumed_memory) if resumed_memory else ""
    disk_overlay_map = str(disk_overlay_map) if disk_overlay_map else ""
    memory_overlay_map = str(memory_overlay_map) if memory_overlay_map else ""

    # launch fuse
    execute_args = ['', '', \
            # disk parameter
            '%s' % vmnetfs.VMNetFS.FUSE_TYPE_DISK,
            "%s" % os.path.abspath(original_disk),  # base path
            "%s" % resumed_disk,                    # overlay path
            "%s" % disk_overlay_map,                # overlay map
            '%d' % fuse_disk_size,                       # size of base
            '0',                                    # segment size
            "%d" % chunk_size]
    if original_memory:
        for parameter in [
                # memory parameter
                '%s' % vmnetfs.VMNetFS.FUSE_TYPE_MEMORY,
                "%s" % os.path.abspath(original_memory),
                "%s" % resumed_memory,
                "%s" % memory_overlay_map,
                '%d' % fuse_memory_size,
                '0',\
                "%d" % chunk_size
                ]:
            execute_args.append(parameter)

    fuse_process = vmnetfs.VMNetFS(bin_path, execute_args, **kwargs)
    fuse_process.launch()
    fuse_process.start()
    return fuse_process


def run_vm(conn, domain_xml, **kwargs):
    # kwargs
    # vnc_disable       :   do not show vnc console
    # wait_vnc          :   wait until vnc finishes if vnc_enabled
    machine = conn.createXML(domain_xml, 0)

    # Run VNC and wait until user finishes working
    if kwargs.get('vnc_disable'):
        return machine

    # Get VNC port
    vnc_port = 5900
    try:
        running_xml_string = machine.XMLDesc(libvirt.VIR_DOMAIN_XML_SECURE)
        running_xml = ElementTree.fromstring(running_xml_string)
        vnc_port = running_xml.find("devices/graphics").get("port")
        vnc_port = int(vnc_port)-5900
    except AttributeError as e:
        LOG.error("Warning, Possible VNC port error:%s" % str(e))

    _PIPE = subprocess.PIPE
    vnc_process = subprocess.Popen(["gvncviewer", "localhost:%d" % vnc_port],
            stdout=_PIPE, stderr=_PIPE,
            close_fds=True)
    if kwargs.get('wait_vnc'):
        try:
            vnc_process.wait()
        except KeyboardInterrupt as e:
            LOG.info("keyboard interrupt while waiting VNC")
            if machine:
                machine.destroy()
    return machine


class MemoryReadProcess(multiprocessing.Process):
    #class MemoryReadProcess(threading.Thread):
    RET_SUCCESS = 1
    RET_ERRROR = 2

    def __init__(self, input_path, output_path, 
            machine_memory_size, output_queue):
        self.input_path = input_path
        self.output_path = output_path
        self.output_queue = output_queue
        self.machine_memory_size = machine_memory_size*1024
        multiprocessing.Process.__init__(self, target=self.read_mem_snapshot)
        #threading.Thread.__init__(self, target=self.read_mem_snapshot)

    def read_mem_snapshot(self):
        if os.path.isfile(self.input_path) != False:
            self.output_queue.put(self.RET_ERRROR)
            self.output_queue.put("Cannot open named pipe")

        # create memory snapshot aligned with 4KB
        try:
            self.in_fd = open(self.input_path, 'rb')
            self.out_fd = open(self.output_path, 'wb')

            total_read_size = 0
            # read first 40KB and aligen header with 4KB
            data = self.in_fd.read(Memory.Memory.RAM_PAGE_SIZE*10)
            libvirt_header = vmnetx._QemuMemoryHeaderData(data)
            original_header = libvirt_header.get_header()
            align_size = Memory.Memory.RAM_PAGE_SIZE*2
            new_header = libvirt_header.get_aligned_header(align_size)
            self.out_fd.write(new_header)
            total_read_size += len(new_header)
            self.out_fd.write(data[len(original_header):])
            total_read_size += len(data[len(original_header):])

            # write rest of the memory data
            prog_bar = AnimatedProgressBar(end=100, width=80, stdout=sys.stdout)
            while True:
                data = self.in_fd.read(1024 * 1024)
                if data == None or len(data) <= 0:
                    break
                self.out_fd.write(data)
                total_read_size += len(data)
                prog_bar.set_percent(100.0*total_read_size/self.machine_memory_size)
                prog_bar.show_progress()
            self.out_fd.flush()
            prog_bar.finish()
            if total_read_size != self.out_fd.tell():
                raise Exception("output file size is different from stream size")
        except Exception, e:
            LOG.error(str(e))
            self.output_queue.put(self.RET_ERRROR)
            self.output_queue.put(str(e))
        else:
            self.output_queue.put(self.RET_SUCCESS)


def save_mem_snapshot(machine, fout_path, **kwargs):
    #Set migration speed
    nova_util = kwargs.get('nova_util', None)
    ret = machine.migrateSetMaxSpeed(1000000, 0)   # 1000 Gbps, unlimited
    if ret != 0:
        raise CloudletGenerationError("Cannot set migration speed : %s", machine.name())

    # Pause VM
    machine.suspend()

    # get VM information
    machine_memory_size = machine.memoryStats().get('actual', None)
    if machine_memory_size is None:
        # libvirt <= 0.9.3
        xml = ElementTree.fromstring(machine.XMLDesc(libvirt.VIR_DOMAIN_XML_SECURE))
        memory_element = xml.find('memory')
        if memory_element is not None:
            machine_memory_size = long(memory_element.text)
    

    #Save memory state
    LOG.info("save VM memory state at %s" % fout_path)
    LOG.info("This could take up to minute depend on VM's memory size")
    LOG.info("(Check file at %s)" % fout_path)
    try:
        named_pipe_output = fout_path + ".fifo"
        output_queue = multiprocessing.Queue()
        os.mkfifo(named_pipe_output)
        memory_read_proc = MemoryReadProcess(named_pipe_output, fout_path, 
                machine_memory_size, output_queue)
        memory_read_proc.start()
        ret = machine.save(named_pipe_output)
        memory_read_proc.join()
    except libvirt.libvirtError, e:
        # we intentionally ignore seek error from libvirt since we have cause
        # that by using named pipe
        if os.path.exists(named_pipe_output):
            os.remove(named_pipe_output)
        if str(e).startswith('unable to seek') == False:
            raise CloudletGenerationError("libvirt memory save : " + str(e))

    try:
        proc_ret = output_queue.get()
        if proc_ret != MemoryReadProcess.RET_SUCCESS:
            error_reason = output_queue.get()
            msg = "Failed to create memory snapshot : %s" % str(error_reason)
            LOG.error(msg)
            raise CloudletGenerationError(msg)
        if nova_util != None:
            # OpenStack runs VM with nova account and snapshot 
            # is generated from system connection
            nova_util.chown(fout_path, os.getuid())
    except vmnetx.MachineGenerationError, e:
        raise CloudletGenerationError("Machine Generation Error: " + str(e))

    if ret != 0:
        raise CloudletGenerationError("libvirt: Cannot save memory state")


def run_snapshot(conn, disk_image, mem_snapshot, **kwargs):
    # kwargs
    # qemu_logfile      :   log file for QEMU-KVM
    # resume_time       :   write back the resumed_time
    received_xml = kwargs.get('new_xml', None)
    resume_time = kwargs.get('resume_time', None)
    logfile = kwargs.get('qemu_logfile', None)
    qemu_args = kwargs.get('qemu_args', None)
    if resume_time != None:
        start_resume_time = time()

    new_uuid = uuid4()
    if received_xml == None:
        # read embedded XML at memory snapshot to change disk path
        hdr = vmnetx._QemuMemoryHeader(open(mem_snapshot))
        old_xml = ElementTree.fromstring(hdr.xml)
        new_xml_string = _convert_xml(old_xml, conn, disk_path=disk_image,
                uuid=new_uuid, logfile=logfile, qemu_args=qemu_args)
    else:
        # get uuid and network information from new_xml
        hdr = vmnetx._QemuMemoryHeader(open(mem_snapshot))
        old_xml = ElementTree.fromstring(hdr.xml)
        new_xml = ElementTree.fromstring(received_xml)
        uuid_element = new_xml.find('uuid')<commit_msg>libvirt 0.9.8 does not shutoff the VM after save mem. So explicitly terminated it<commit_after>#!/usr/bin/env python 
#
# Cloudlet Infrastructure for Mobile Computing
#
#   Author: <NAME> <<EMAIL>>
#
#   Copyright (C) 2011-2013 Carnegie Mellon University
#   Licensed under the Apache License, Version 2.0 (the "License");
#   you may not use this file except in compliance with the License.
#   You may obtain a copy of the License at
#
#       http://www.apache.org/licenses/LICENSE-2.0
#
#   Unless required by applicable law or agreed to in writing, software
#   distributed under the License is distributed on an "AS IS" BASIS,
#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#   See the License for the specific language governing permissions and
#   limitations under the License.
#

import sys
import os
import functools
import subprocess
import Memory
import Disk
import vmnetfs
import vmnetx
import stat
import delta
import xray
import hashlib
import libvirt
import shutil
import multiprocessing

from synthesis.db import api as db_api
from synthesis.db import table_def as db_table
from synthesis.Configuration import Const
from synthesis.Configuration import Options
from synthesis.Configuration import Discovery_Const
from synthesis.delta import DeltaList
from synthesis.delta import DeltaItem
from synthesis import msgpack
from synthesis.progressbar import AnimatedProgressBar

from xml.etree import ElementTree
from xml.etree.ElementTree import Element
from uuid import uuid4
from tempfile import NamedTemporaryFile
from time import time
from time import sleep
import threading
from optparse import OptionParser

from synthesis.tool import comp_lzma
from synthesis.tool import diff_files
from synthesis.tool import decomp_overlay
from synthesis import log as logging

LOG = logging.getLogger(__name__)


class CloudletGenerationError(Exception):
    pass


def wrap_vm_fault(function):
    """Wraps a method to catch exceptions related to instances.
    This decorator wraps a method to catch any exceptions and
    terminate the request gracefully.
    """
    @functools.wraps(function)
    def decorated_function(self, *args, **kwargs):
        try:
            return function(self, *args, **kwargs)
        except Exception, e:
            if hasattr(self, 'exception_handler'):
                self.exception_handler()
            kwargs.update(dict(zip(function.func_code.co_varnames[2:], args)))
            LOG.error("failed with : %s" % str(kwargs))

    return decorated_function

def libvirt_err_callback(ctxt, err):
    # we intentionally ignore seek error from libvirt since we have cause
    # that by using named pipe
    if err[3] == libvirt.VIR_ERR_ERROR and \
            err[0] == libvirt.VIR_FROM_STREAMS and \
            err[1] == libvirt.VIR_FROM_QEMU:
        pass
    elif err[3] == libvirt.VIR_ERR_WARNING:
        LOG.warning(err[2])
    elif err[3] == libvirt.VIR_ERR_ERROR:
        LOG.error(err[2])
libvirt.registerErrorHandler(f=libvirt_err_callback, ctx=None)


class VM_Overlay(threading.Thread):
    def __init__(self, base_disk, options, qemu_args=None,
            base_mem=None, base_diskmeta=None,
            base_memmeta=None, base_hashvalue=None,
            vm_xml=None, nova_util=None):
        # create user customized overlay.
        # First resume VM, then let user edit its VM
        # Finally, return disk/memory binary as an overlay
        # base_disk: path to base disk
        self.base_disk = os.path.abspath(base_disk)
        self.options = options
        self.vm_xml = vm_xml or None
        self.qemu_args = qemu_args or None
        (self.base_diskmeta, self.base_mem, self.base_memmeta) = \
                Const.get_basepath(self.base_disk, check_exist=False)
        self.base_mem = base_mem or self.base_mem
        self.base_diskmeta = base_diskmeta or self.base_diskmeta
        self.base_memmeta = base_memmeta or self.base_memmeta
        # use abs path
        self.base_mem = os.path.abspath(self.base_mem)
        self.base_diskmeta = os.path.abspath(self.base_diskmeta)
        self.base_memmeta = os.path.abspath(self.base_memmeta)
        self.nova_util = nova_util

        # find base vm's hashvalue from DB
        self.base_hashvalue = base_hashvalue or None
        if self.base_hashvalue == None:
            dbconn = db_api.DBConnector()
            basevm_list = dbconn.list_item(db_table.BaseVM)
            for basevm_row in basevm_list:
                basevm_row_disk = os.path.abspath(basevm_row.disk_path)
                if basevm_row_disk == self.base_disk:
                    self.base_hashvalue = basevm_row.hash_value
            if self.base_hashvalue == None:
                msg = "Cannot find hashvalue for %s" % self.base_disk
                raise CloudletGenerationError(msg)

        self.log_path = os.path.join(os.path.dirname(self.base_disk), \
                                os.path.basename(self.base_disk) + Const.OVERLAY_LOG)
        threading.Thread.__init__(self, target=self.create_overlay)

    def resume_basevm(self):
        if (self.options == None) or (isinstance(self.options, Options) == False):
            raise CloudletGenerationError("Given option class is invalid: %s" % str(self.options))

        # filename for overlay VM
        self.qemu_logfile = NamedTemporaryFile(prefix="cloudlet-qemu-log-", delete=False)
        os.chmod(self.qemu_logfile.name, stat.S_IROTH | stat.S_IWOTH | \
                stat.S_IRUSR | stat.S_IWUSR | stat.S_IRGRP | stat.S_IWGRP)

        # option for data-intensive application
        self.cache_manager = None
        self.mount_point = None
        if self.options.DATA_SOURCE_URI != None:
            cache_manager, mount_point = self._start_emulate_cache_fs()

        # make FUSE disk & memory
        self.fuse = run_fuse(Const.VMNETFS_PATH, Const.CHUNK_SIZE,
                self.base_disk, os.path.getsize(self.base_disk),
                self.base_mem, os.path.getsize(self.base_mem))
        self.modified_disk = os.path.join(self.fuse.mountpoint, 'disk', 'image')
        self.base_mem_fuse = os.path.join(self.fuse.mountpoint, 'memory', 'image')
        self.modified_mem = NamedTemporaryFile(prefix="cloudlet-mem-", delete=False)
        # monitor modified chunks
        stream_modified = os.path.join(self.fuse.mountpoint, 'disk', 'streams', 'chunks_modified')
        stream_access = os.path.join(self.fuse.mountpoint, 'disk', 'streams', 'chunks_accessed')
        memory_access = os.path.join(self.fuse.mountpoint, 'memory', 'streams', 'chunks_accessed')
        self.fuse_stream_monitor = vmnetfs.StreamMonitor()
        self.fuse_stream_monitor.add_path(stream_modified, vmnetfs.StreamMonitor.DISK_MODIFY)
        self.fuse_stream_monitor.add_path(stream_access, vmnetfs.StreamMonitor.DISK_ACCESS)
        self.fuse_stream_monitor.add_path(memory_access, vmnetfs.StreamMonitor.MEMORY_ACCESS)
        self.fuse_stream_monitor.start()
        self.qemu_monitor = vmnetfs.FileMonitor(self.qemu_logfile.name, vmnetfs.FileMonitor.QEMU_LOG)
        self.qemu_monitor.start()

        # 1. resume & get modified disk
        LOG.info("[INFO] * Overlay creation configuration")
        LOG.info("[INFO]  - %s" % str(self.options))
        conn = get_libvirt_connection()
        self.machine = run_snapshot(conn, self.modified_disk, self.base_mem_fuse, \
                qemu_logfile=self.qemu_logfile.name, qemu_args=self.qemu_args,
                new_xml=self.vm_xml)
        return self.machine

    @wrap_vm_fault
    def create_overlay(self):
        # 2. get montoring info
        monitoring_info = _get_monitoring_info(self.machine, self.options,
                self.base_memmeta, self.base_diskmeta,
                self.fuse_stream_monitor,
                self.base_disk, self.base_mem,
                self.modified_disk, self.modified_mem.name,
                self.qemu_logfile, 
                nova_util=self.nova_util)

        # 3. get overlay VM
        overlay_deltalist = get_overlay_deltalist(monitoring_info, self.options,
                self.base_disk, self.base_mem, self.base_memmeta, 
                self.modified_disk, self.modified_mem.name)

        # 4. create_overlayfile
        image_name = os.path.basename(self.base_disk).split(".")[0]
        dir_path = os.path.dirname(self.base_mem)
        overlay_prefix = os.path.join(dir_path,
                image_name+Const.OVERLAY_FILE_PREFIX)
        overlay_metapath = os.path.join(dir_path, image_name+Const.OVERLAY_META)

        self.overlay_metafile, self.overlay_files = \
                generate_overlayfile(overlay_deltalist, self.options, 
                self.base_hashvalue, os.path.getsize(self.modified_disk), 
                os.path.getsize(self.modified_mem.name),
                overlay_metapath, overlay_prefix)

        # option for data-intensive application
        if self.options.DATA_SOURCE_URI != None:
            overlay_uri_meta = os.path.join(dir_path, image_name+Const.OVERLAY_URIs)
            self.overlay_uri_meta =  self._terminate_emulate_cache_fs(overlay_uri_meta)

        # 5. terminting
        self.fuse.terminate()
        self.fuse_stream_monitor.terminate()
        self.qemu_monitor.terminate()
        self.fuse_stream_monitor.join()
        self.qemu_monitor.join()
        self.fuse.join()
        if hasattr(self, "cache_manager") and self.cache_manager != None:
            self.cache_manager.terminate()
            self.cache_manager.join()
        if hasattr(self, "mount_point") and self.mount_point != None and os.path.lexists(self.mount_point):
            os.unlink(self.mount_point)

        if self.options.MEMORY_SAVE_PATH:
            LOG.debug("[INFO] moving memory sansphost to %s" % self.options.MEMORY_SAVE_PATH)
            shutil.move(self.modified_mem.name, self.options.MEMORY_SAVE_PATH)
        else:
            os.unlink(self.modified_mem.name)

        if os.path.exists(self.qemu_logfile.name):
            os.remove(self.qemu_logfile.name)

    def exception_handler(self):
        # make sure to destory the VM
        if self.machine is not None:
            _terminate_vm(self.machine)
            self.machine = None

    def _start_emulate_cache_fs(self):
        # check samba
        if os.path.exists(Discovery_Const.HOST_SAMBA_DIR) == False:
            msg = "Cloudlet does not have samba directory at %s\n" % \
                    Discovery_Const.HOST_SAMBA_DIR
            msg += "You can change samba path at Configuration.py\n"
            raise CloudletGenerationError(msg)
        # fetch URI to cache
        try:
            cache_manager = cache.CacheManager(Discovery_Const.CACHE_ROOT, \
                    Discovery_Const.REDIS_ADDR, Discovery_Const.CACHE_FUSE_BINPATH)
                    
            cache_manager.start()
            self.compiled_list = cache.Util.get_compiled_URIs( \
                    cache_manager.cache_dir, self.options.DATA_SOURCE_URI)
            #cache_manager.fetch_compiled_URIs(compiled_list)
            cache_fuse = cache_manager.launch_fuse(self.compiled_list)
            LOG.debug("[INFO] cache fuse mount : %s, %s\n" % \
                    (cache_fuse.url_root, cache_fuse.mountpoint))
        except cache.CachingError, e:
            msg = "Cannot retrieve data from URI: %s" % str(e)
            raise CloudletGenerationError(msg)
        # create symbolic link to samba dir
        mount_point = os.path.join(Discovery_Const.HOST_SAMBA_DIR, cache_fuse.url_root)
        if os.path.lexists(mount_point) == True:
            os.unlink(mount_point)
        os.symlink(cache_fuse.mountpoint, mount_point)
        LOG.debug("[INFO] create symbolic link to %s" % mount_point)

        return cache_manager, cache_fuse.mountpoint

    def _terminate_emulate_cache_fs(self, overlay_uri_meta):
        uri_list = []
        for each_info in self.compiled_list:
            uri_list.append(each_info.get_uri())
        uri_data = {
                'source_URI' : self.options.DATA_SOURCE_URI,
                'compiled_URIs' : uri_list,
                }
        with open(overlay_uri_meta, "w+b") as f:
            import json
            f.write(json.dumps(uri_data))
        return overlay_uri_meta


class _MonitoringInfo(object):
    BASEDISK_HASHLIST       = "basedisk_hashlist"
    BASEMEM_HASHLIST        = "basemem_hashlist"
    DISK_MODIFIED_BLOCKS    = "disk_modified_block" # from fuse monitoring
    DISK_USED_BLOCKS        = "disk_used_block" # from xray support
    DISK_FREE_BLOCKS        = "disk_free_block"
    MEMORY_FREE_BLOCKS      = "memory_free_block"

    def __init__(self, properties):
        for k, v in properties.iteritems():
            setattr(self, k, v)

    def __str__(self):
        ret = ""
        for k, v in self.__dict__.iteritems():
            ret += "%s\t:\t%s\n" % (str(k), str(v))
        return ret

    def __getitem__(self, item):
        return self.__dict__[item]


class SynthesizedVM(threading.Thread):
    def __init__(self, launch_disk, launch_mem, fuse, disk_only=False, qemu_args=None, **kwargs):
        # kwargs
        self.vm_xml = kwargs.get("vm_xml", None)
        self.LOG = kwargs.get("log", None)
        if self.LOG == None:
            self.LOG = open("/dev/null", "w+b")

        # monitor modified chunks
        self.machine = None
        self.disk_only = disk_only
        self.qemu_args = qemu_args
        self.fuse = fuse
        self.launch_disk = launch_disk
        self.launch_mem = launch_mem
        self.qemu_logfile = NamedTemporaryFile(prefix="cloudlet-qemu-log-", delete=False)
        os.chmod(self.qemu_logfile.name, stat.S_IROTH | stat.S_IWOTH | \
                stat.S_IRUSR | stat.S_IWUSR | stat.S_IRGRP | stat.S_IWGRP)
        self.resumed_disk = os.path.join(fuse.mountpoint, 'disk', 'image')
        self.resumed_mem = os.path.join(fuse.mountpoint, 'memory', 'image')
        self.stream_modified = os.path.join(fuse.mountpoint, 'disk', 'streams', 'chunks_modified')
        self.stream_disk_access = os.path.join(fuse.mountpoint, 'disk', 'streams', 'chunks_accessed')
        self.stream_memory_access = os.path.join(fuse.mountpoint, 'memory', 'streams', 'chunks_accessed')
        self.monitor = vmnetfs.StreamMonitor()
        self.monitor.add_path(self.stream_modified, vmnetfs.StreamMonitor.DISK_MODIFY)
        self.monitor.add_path(self.stream_disk_access, vmnetfs.StreamMonitor.DISK_ACCESS)
        self.monitor.add_path(self.stream_memory_access, vmnetfs.StreamMonitor.MEMORY_ACCESS)
        self.monitor.start()
        self.qemu_monitor = vmnetfs.FileMonitor(self.qemu_logfile.name, vmnetfs.FileMonitor.QEMU_LOG)
        self.qemu_monitor.start()
        threading.Thread.__init__(self, target=self.resume)

    def resume(self):
        #resume VM
        conn = get_libvirt_connection()
        self.resume_time = {'time':-100}
        try:
            if self.disk_only:
                # edit default XML to have new disk path
                conn = get_libvirt_connection()
                xml = ElementTree.fromstring(open(Const.TEMPLATE_XML, "r").read())
                new_xml_string = _convert_xml(xml, conn, disk_path=self.resumed_disk, \
                        uuid=str(uuid4()), qemu_args=self.qemu_args)
                self.machine = run_vm(conn, new_xml_string, vnc_disable=True)
            else:
                self.machine = run_snapshot(conn, self.resumed_disk, self.resumed_mem,
                        qemu_logfile=self.qemu_logfile.name, resume_time=self.resume_time,
                        qemu_args=self.qemu_args, new_xml=self.vm_xml)
        except Exception as e:
            sys.stdout.write(str(e)+"\n")

        return self.machine

    def terminate(self):
        try:
            if self.machine:
                self.machine.destroy()
        except libvirt.libvirtError as e:
            pass

        # terminate
        self.fuse.terminate()
        self.monitor.terminate()
        self.qemu_monitor.terminate()
        self.monitor.join()
        self.qemu_monitor.join()

        # delete all temporary file
        if os.path.exists(self.launch_disk):
            os.unlink(self.launch_disk)
        if os.path.exists(self.launch_mem):
            os.unlink(self.launch_mem)
        if os.path.exists(self.qemu_logfile.name):
            os.unlink(self.qemu_logfile.name)

def _terminate_vm(machine):
    machine_id = machine.ID()
    conn = get_libvirt_connection()
    try:
        for each_id in conn.listDomainsID():
            if each_id == machine_id:
                each_machine = conn.lookupByID(machine_id)
                state, reason = each_machine.state(0)
                if state != libvirt.VIR_DOMAIN_SHUTOFF:
                    each_machine.destroy()
    except libvirt.libvirtError, e:
        pass

def _create_overlay_meta(base_hash, overlay_metafile, modified_disksize, modified_memsize,
        blob_info):
    fout = open(overlay_metafile, "wrb")

    meta_dict = dict()
    meta_dict[Const.META_BASE_VM_SHA256] = base_hash
    meta_dict[Const.META_RESUME_VM_DISK_SIZE] = long(modified_disksize)
    meta_dict[Const.META_RESUME_VM_MEMORY_SIZE] = long(modified_memsize)
    meta_dict[Const.META_OVERLAY_FILES] = blob_info

    serialized = msgpack.packb(meta_dict)
    fout.write(serialized)
    fout.close()


def _update_overlay_meta(original_meta, new_path, blob_info=None):
    fout = open(new_path, "wrb")

    if blob_info:
        original_meta[Const.META_OVERLAY_FILES] = blob_info
    serialized = msgpack.packb(original_meta)
    fout.write(serialized)
    fout.close()


def _test_dma_accuracy(dma_dict, disk_deltalist, mem_deltalist):
    dma_start_time = time()
    dma_read_counter = 0
    dma_write_counter = 0
    dma_read_overlay_dedup = 0
    dma_write_overlay_dedup = 0
    dma_read_base_dedup = 0
    dma_write_base_dedup = 0
    disk_delta_dict = dict([(delta.offset/Const.CHUNK_SIZE, delta) for delta in disk_deltalist])
    mem_delta_dict = dict([(delta.offset/Const.CHUNK_SIZE, delta) for delta in mem_deltalist])
    for dma_disk_chunk in dma_dict.keys():
        item = dma_dict.get(dma_disk_chunk)
        is_dma_read = item['read']
        dma_mem_chunk = item['mem_chunk']
        if is_dma_read:
            dma_read_counter += 1
        else:
            dma_write_counter += 1

        disk_delta = disk_delta_dict.get(dma_disk_chunk, None)
        if disk_delta:
            # first search at overlay disk
            if disk_delta.ref_id != DeltaItem.REF_OVERLAY_MEM:
#                LOG.info("dma disk chunk is same, but is it not deduped with overlay mem(%d)" \
#                        % (disk_delta.ref_id))
                continue
            delta_mem_chunk = disk_delta.data/Const.CHUNK_SIZE
            if delta_mem_chunk == dma_mem_chunk:
                if is_dma_read:
                    dma_read_overlay_dedup += 1
                else:
                    dma_write_overlay_dedup += 1
        else:
            # search at overlay mem
            mem_delta = mem_delta_dict.get(dma_mem_chunk, None)
            if mem_delta:
                if mem_delta.ref_id != DeltaItem.REF_BASE_DISK:
#                    LOG.info("dma memory chunk is same, but is it not deduped with base disk(%d)" \
#                            % (mem_delta.ref_id))
                    continue
                delta_disk_chunk = mem_delta.data/Const.CHUNK_SIZE
                if delta_disk_chunk == dma_disk_chunk:
                    if is_dma_read:
                        dma_read_base_dedup += 1
                    else:
                        dma_write_base_dedup += 1

    dma_end_time = time()
    LOG.debug("[DMA] Total DMA: %ld\n " % (len(dma_dict)))
    LOG.debug("[DMA] Total DMA READ: %ld, WRITE: %ld\n " % (dma_read_counter, dma_write_counter))
    LOG.debug("[DMA] WASTED TIME: %f\n " % (dma_end_time-dma_start_time))
    LOG.debug("[DMA] 1) DMA READ Overlay Deduplication: %ld(%f %%)\n " % \
            (dma_read_overlay_dedup, 100.0*dma_read_overlay_dedup/dma_read_counter))
    LOG.debug("[DMA]    DMA READ Base Deduplication: %ld(%f %%)\n " % \
            (dma_read_base_dedup, 100.0*dma_read_base_dedup/dma_read_counter))
    LOG.debug("[DMA] 2) DMA WRITE Overlay Deduplication: %ld(%f %%)\n " % \
            (dma_write_overlay_dedup, 100.0*dma_write_overlay_dedup/dma_write_counter))
    LOG.debug("[DMA]    DMA WRITE Base Deduplication: %ld(%f %%)\n " % \
            (dma_write_base_dedup, 100.0*dma_write_base_dedup/dma_write_counter))


def _convert_xml(xml, conn, vm_name=None, disk_path=None, uuid=None, \
        logfile=None, qemu_args=None):

    # delete padding
    padding_element = xml.find("description")
    if padding_element != None:
        xml.remove(padding_element)

    if vm_name != None:
        name_element = xml.find('name')
        if name_element == None:
            raise CloudletGenerationError("Malfomed XML input: %s", Const.TEMPLATE_XML)
        name_element.text = vm_name

    old_uuid = None
    if uuid != None:
        uuid_element = xml.find('uuid')
        old_uuid = str(uuid_element.text)
        uuid_element.text = str(uuid)

        # update sysinfo entry's uuid if it exist
        # it has to match with uuid of the VM
        sysinfo_entries = xml.findall('sysinfo/system/entry')
        for entry in sysinfo_entries:
            if(entry.attrib['name'] == 'uuid'):
                entry.text = str(uuid)

    # Use custom QEMU
    qemu_emulator = xml.find('devices/emulator')
    if qemu_emulator == None:
        qemu_emulator = Element("emulator")
        device_element = xml.find("devices")
        device_element.append(qemu_emulator)
    qemu_emulator.text = Const.QEMU_BIN_PATH

    # disk path is required
    if disk_path == None:
        raise CloudletGenerationError("Need disk_path to run new VM")

    # find all disk element(hdd, cdrom)
    disk_elements = xml.findall('devices/disk')
    hdd_source = None
    cdrom_source = None
    for disk_element in disk_elements:
        disk_type = disk_element.attrib['device']
        if disk_type == 'disk':
            hdd_source = disk_element.find('source')
            hdd_driver = disk_element.find("driver")
            if hdd_driver != None and hdd_driver.get("type", None) != None:
                hdd_driver.set("type", "raw")
        if disk_type == 'cdrom':
            cdrom_source = disk_element.find('source')

    # hdd path setting
    if hdd_source == None:
        raise CloudletGenerationError("Malfomed XML input: %s", Const.TEMPLATE_XML)
    hdd_source.set("file", os.path.abspath(disk_path))

    # ovf path setting
    if cdrom_source != None:
        cdrom_source.set("file", os.path.abspath(Const.TEMPLATE_OVF))

    # append QEMU-argument
    if logfile != None:
        qemu_xmlns="http://libvirt.org/schemas/domain/qemu/1.0"
        qemu_element = xml.find("{%s}commandline" % qemu_xmlns)
        if qemu_element == None:
            qemu_element = Element("{%s}commandline" % qemu_xmlns)
            xml.append(qemu_element)

        # remove previsou cloudlet argument if it is
        argument_list = qemu_element.findall("{%s}arg" % qemu_xmlns)
        remove_list = list()
        for argument_item in argument_list:
            arg_value = argument_item.get('value').strip() 
            if (arg_value== '-cloudlet') or (arg_value.startswith('logfile=')):
                remove_list.append(argument_item)
        for item in remove_list:
            qemu_element.remove(item)

        # append new cloudlet logpath
        qemu_element.append(Element("{%s}arg" % qemu_xmlns, {'value':'-cloudlet'}))
        qemu_element.append(Element("{%s}arg" % qemu_xmlns, {'value':"logfile=%s" % logfile}))

    # append qemu argument give from user
    if qemu_args:
        qemu_xmlns="http://libvirt.org/schemas/domain/qemu/1.0"
        qemu_element = xml.find("{%s}commandline" % qemu_xmlns)
        if qemu_element == None:
            qemu_element = Element("{%s}commandline" % qemu_xmlns)
            xml.append(qemu_element)
        for each_argument in qemu_args:
            qemu_element.append(Element("{%s}arg" % qemu_xmlns, {'value':each_argument}))

    device_element = xml.find("devices")
    console_element = device_element.find("console")
    if console_element != None:
        device_element.remove(console_element)

    # drop original security label
    # TODO: cope with appropriate security model
    sec_element = xml.find("seclabel")
    if sec_element != None:
        xml.remove(sec_element)
    network_element = device_element.find("interface")
    network_filter = network_element.find("filterref")
    if network_filter != None:
        network_element.remove(network_filter)

    new_xml_str = ElementTree.tostring(xml)
    if old_uuid != None and uuid != None:
        new_xml_str = new_xml_str.replace(old_uuid, str(uuid))
    return new_xml_str


def _get_monitoring_info(machine, options,
        base_memmeta, base_diskmeta,
        fuse_stream_monitor,
        base_disk, base_mem,
        modified_disk, modified_mem,
        qemu_logfile, nova_util=None):
    ''' return montioring information including
        1) base vm hash list
        2) used/freed disk block list
        3) freed memory page
    '''

    # 1-2. Stop monitoring for memory access (snapshot will create a lot of access)
    fuse_stream_monitor.del_path(vmnetfs.StreamMonitor.MEMORY_ACCESS)
    # TODO: support stream of modified memory rather than tmp file
    if not options.DISK_ONLY:
        save_mem_snapshot(machine, modified_mem, nova_util=nova_util)

    # 1-3. get hashlist of base memory and disk
    basemem_hashlist = Memory.base_hashlist(base_memmeta)
    basedisk_hashlist = Disk.base_hashlist(base_diskmeta)

    # 1-4. get dma & discard information
    if options.TRIM_SUPPORT:
        dma_dict, trim_dict = Disk.parse_qemu_log(qemu_logfile.name, Const.CHUNK_SIZE)
        if len(trim_dict) == 0:
            LOG.warning("No TRIM Discard, Check /etc/fstab configuration")
    else:
        trim_dict = dict()
    free_memory_dict = dict()

    # 1-5. get used sector information from x-ray
    used_blocks_dict = None
    if options.XRAY_SUPPORT:
        used_blocks_dict = xray.get_used_blocks(modified_disk)

    m_chunk_dict = fuse_stream_monitor.modified_chunk_dict

    info_dict = dict()
    info_dict[_MonitoringInfo.BASEDISK_HASHLIST] = basedisk_hashlist
    info_dict[_MonitoringInfo.BASEMEM_HASHLIST] = basemem_hashlist
    info_dict[_MonitoringInfo.DISK_USED_BLOCKS] = used_blocks_dict
    info_dict[_MonitoringInfo.DISK_MODIFIED_BLOCKS] = m_chunk_dict
    info_dict[_MonitoringInfo.DISK_FREE_BLOCKS] = trim_dict
    info_dict[_MonitoringInfo.MEMORY_FREE_BLOCKS] = free_memory_dict
    monitoring_info = _MonitoringInfo(info_dict)
    return monitoring_info


def copy_disk(in_path, out_path):
    LOG.info("Copying disk image to %s" % out_path)
    cmd = ["cp",  "%s" % (in_path), "%s" % (out_path)]
    cp_proc = subprocess.Popen(cmd, close_fds=True)
    cp_proc.wait()
    if cp_proc.returncode != 0:
        raise IOError("Copy failed: from %s to %s " % (in_path, out_path))


def get_libvirt_connection():
    conn = libvirt.open("qemu:///session")
    return conn


def get_overlay_deltalist(monitoring_info, options,
        base_image, base_mem, base_memmeta, 
        modified_disk, modified_mem,
        old_deltalist=None):
    '''return overlay deltalist
    Get difference between base vm (base_image, base_mem) and 
    launch vm (modified_disk, modified_mem) using monitoring information

    Args:
        prev_mem_deltalist : Option only for creating_residue.
            Different from disk, we create whole memory snapshot even for residue.
            So, to get the precise difference between previous memory overlay,
            we need previous memory deltalist
    '''

    INFO = _MonitoringInfo
    basedisk_hashlist = getattr(monitoring_info, INFO.BASEDISK_HASHLIST, None)
    basemem_hashlist = getattr(monitoring_info, INFO.BASEMEM_HASHLIST, None)
    free_memory_dict = getattr(monitoring_info, INFO.MEMORY_FREE_BLOCKS, None)
    m_chunk_dict = getattr(monitoring_info, INFO.DISK_MODIFIED_BLOCKS, None)
    trim_dict = getattr(monitoring_info, INFO.DISK_FREE_BLOCKS, None)
    used_blocks_dict = getattr(monitoring_info, INFO.DISK_USED_BLOCKS, None)
    dma_dict = dict()

    # 2-1. get memory overlay
    if options.DISK_ONLY:
        mem_deltalist = list()
    else:
        mem_deltalist= Memory.create_memory_deltalist(modified_mem,
                basemem_meta=base_memmeta, basemem_path=base_mem,
                apply_free_memory=options.FREE_SUPPORT,
                free_memory_info=free_memory_dict)
        if old_deltalist and len(old_deltalist) > 0:
            diff_deltalist = delta.residue_diff_deltalists(old_deltalist,
                    mem_deltalist, base_mem)
            mem_deltalist = diff_deltalist

    # 2-2. get disk overlay
    disk_statistics = dict()
    disk_deltalist = Disk.create_disk_deltalist(modified_disk,
        m_chunk_dict, Const.CHUNK_SIZE,
        basedisk_hashlist=basedisk_hashlist, basedisk_path=base_image,
        trim_dict=trim_dict,
        apply_discard = True,
        dma_dict=dma_dict,
        used_blocks_dict=used_blocks_dict,
        ret_statistics=disk_statistics)
        


    # 2-3. Merge disk & memory delta_list to generate overlay file
    # deduplication
    merged_deltalist = delta.create_overlay(
            mem_deltalist, Memory.Memory.RAM_PAGE_SIZE,
            disk_deltalist, Const.CHUNK_SIZE,
            basedisk_hashlist=basedisk_hashlist,
            basemem_hashlist=basemem_hashlist)
            

    free_memory_dict = getattr(monitoring_info, _MonitoringInfo.MEMORY_FREE_BLOCKS, None)
    free_pfn_counter = long(free_memory_dict.get("freed_counter", 0))
    disk_discarded_count = disk_statistics.get('trimed', 0)
    DeltaList.statistics(merged_deltalist, 
            mem_discarded=free_pfn_counter,
            disk_discarded=disk_discarded_count)

    return merged_deltalist


def generate_overlayfile(overlay_deltalist, options, 
        base_hashvalue, launchdisk_size, launchmem_size,
        overlay_metapath, overlayfile_prefix):
    ''' generate overlay metafile and file
    Return:
        [overlay_metapath, [overlayfilepath1, overlayfilepath2]]
    '''

    # Compression
    LOG.info("[LZMA] Compressing overlay blobs")
    blob_list = delta.divide_blobs(overlay_deltalist, overlayfile_prefix,
            Const.OVERLAY_BLOB_SIZE_KB, Const.CHUNK_SIZE,
            Memory.Memory.RAM_PAGE_SIZE)

    # create metadata
    if not options.DISK_ONLY:
        _create_overlay_meta(base_hashvalue, overlay_metapath,
                launchdisk_size, launchmem_size, blob_list)
    else:
        _create_overlay_meta(base_hashvalue, overlay_metapath,
                launchdisk_size, launchmem_size, blob_list)

    overlay_files = [item[Const.META_OVERLAY_FILE_NAME] for item in blob_list]
    dirpath = os.path.dirname(overlayfile_prefix)
    overlay_files = [os.path.join(dirpath, item) for item in overlay_files]

    return overlay_metapath, overlay_files


def run_delta_compression(output_list, **kwargs):
    # kwargs
    # LOG = log object for nova
    # nova_util = nova_util is executioin wrapper for nova framework
    #           You should use nova_util in OpenStack, or subprocess
    #           will be returned without finishing their work
    # custom_delta
    log = kwargs.get('log', None)
    nova_util = kwargs.get('nova_util', None)
    custom_delta = kwargs.get('custom_delta', False)

    # xdelta and compression
    ret_files = []
    for (base, modified, overlay) in output_list:
        start_time = time()

        # xdelta
        if custom_delta:
            diff_files(base, modified, overlay, nova_util=nova_util)
        else:
            diff_files(base, modified, overlay, nova_util=nova_util)
        LOG.info('[TIME] time for creating overlay : ', str(time()-start_time))
        LOG.info('[TIME](%d)-(%d)=(%d): ' % (os.path.getsize(base), os.path.getsize(modified), os.path.getsize(overlay)))

        # compression
        comp = overlay + '.lzma'
        comp, time1 = comp_lzma(overlay, comp, nova_util=nova_util)
        ret_files.append(comp)

        # remove temporary files
        os.remove(modified)
        os.remove(overlay)

    return ret_files


def recover_launchVM(base_image, meta_info, overlay_file, **kwargs):
    # kwargs
    # skip_validation   :   skip sha1 validation
    # LOG = log object for nova
    # nova_util = nova_util is executioin wrapper for nova framework
    #           You should use nova_util in OpenStack, or subprocess
    #           will be returned without finishing their work
    base_mem = kwargs.get('base_mem', None)
    base_diskmeta = kwargs.get('base_diskmeta', None)
    base_memmeta = kwargs.get('base_memmeta', None)

    if (not base_mem) or (not base_diskmeta) or (not base_memmeta):
        (base_diskmeta, base_mem, base_memmeta) = \
                Const.get_basepath(base_image, check_exist=True)
    launch_mem = NamedTemporaryFile(prefix="cloudlet-launch-mem-", delete=False)
    launch_disk = NamedTemporaryFile(prefix="cloudlet-launch-disk-", delete=False)

    # Get modified list from overlay_meta
    vm_disk_size = meta_info[Const.META_RESUME_VM_DISK_SIZE]
    vm_memory_size = meta_info[Const.META_RESUME_VM_MEMORY_SIZE]
    memory_chunk_list = list()
    disk_chunk_list = list()
    for each_file in meta_info[Const.META_OVERLAY_FILES]:
        memory_chunks = each_file[Const.META_OVERLAY_FILE_MEMORY_CHUNKS]
        disk_chunks = each_file[Const.META_OVERLAY_FILE_DISK_CHUNKS]
        memory_chunk_list.extend(["%ld:0" % item for item in memory_chunks])
        disk_chunk_list.extend(["%ld:0" % item for item in disk_chunks])
    disk_overlay_map = ','.join(disk_chunk_list)
    memory_overlay_map = ','.join(memory_chunk_list)

    # make FUSE disk & memory
    kwargs['meta_info'] = meta_info
    fuse = run_fuse(Const.VMNETFS_PATH, Const.CHUNK_SIZE,
            base_image, vm_disk_size, base_mem, vm_memory_size,
            resumed_disk=launch_disk.name,  disk_overlay_map=disk_overlay_map,
            resumed_memory=launch_mem.name, memory_overlay_map=memory_overlay_map,
            **kwargs)
    LOG.info("Start FUSE")

    # Recover Modified Memory
    named_pipename = overlay_file+".fifo"
    os.mkfifo(named_pipename)

    delta_proc = delta.Recovered_delta(base_image, base_mem, overlay_file, \
            launch_mem.name, vm_memory_size,
            launch_disk.name, vm_disk_size, Const.CHUNK_SIZE,
            out_pipename=named_pipename)
    fuse_thread = vmnetfs.FuseFeedingThread(fuse,
            named_pipename, delta.Recovered_delta.END_OF_PIPE)
    return [launch_disk.name, launch_mem.name, fuse, delta_proc, fuse_thread]


def run_fuse(bin_path, chunk_size, original_disk, fuse_disk_size,
        original_memory, fuse_memory_size,
        resumed_disk=None, disk_overlay_map=None,
        resumed_memory=None, memory_overlay_map=None,
        **kwargs):
    if fuse_disk_size <= 0:
        raise CloudletGenerationError("FUSE disk size should be bigger than 0")
    if original_memory != None and fuse_memory_size <= 0:
        raise CloudletGenerationError("FUSE memory size should be bigger than 0")

    # run fuse file system
    resumed_disk = os.path.abspath(resumed_disk) if resumed_disk else ""
    resumed_memory = os.path.abspath(resumed_memory) if resumed_memory else ""
    disk_overlay_map = str(disk_overlay_map) if disk_overlay_map else ""
    memory_overlay_map = str(memory_overlay_map) if memory_overlay_map else ""

    # launch fuse
    execute_args = ['', '', \
            # disk parameter
            '%s' % vmnetfs.VMNetFS.FUSE_TYPE_DISK,
            "%s" % os.path.abspath(original_disk),  # base path
            "%s" % resumed_disk,                    # overlay path
            "%s" % disk_overlay_map,                # overlay map
            '%d' % fuse_disk_size,                       # size of base
            '0',                                    # segment size
            "%d" % chunk_size]
    if original_memory:
        for parameter in [
                # memory parameter
                '%s' % vmnetfs.VMNetFS.FUSE_TYPE_MEMORY,
                "%s" % os.path.abspath(original_memory),
                "%s" % resumed_memory,
                "%s" % memory_overlay_map,
                '%d' % fuse_memory_size,
                '0',\
                "%d" % chunk_size
                ]:
            execute_args.append(parameter)

    fuse_process = vmnetfs.VMNetFS(bin_path, execute_args, **kwargs)
    fuse_process.launch()
    fuse_process.start()
    return fuse_process


def run_vm(conn, domain_xml, **kwargs):
    # kwargs
    # vnc_disable       :   do not show vnc console
    # wait_vnc          :   wait until vnc finishes if vnc_enabled
    machine = conn.createXML(domain_xml, 0)

    # Run VNC and wait until user finishes working
    if kwargs.get('vnc_disable'):
        return machine

    # Get VNC port
    vnc_port = 5900
    try:
        running_xml_string = machine.XMLDesc(libvirt.VIR_DOMAIN_XML_SECURE)
        running_xml = ElementTree.fromstring(running_xml_string)
        vnc_port = running_xml.find("devices/graphics").get("port")
        vnc_port = int(vnc_port)-5900
    except AttributeError as e:
        LOG.error("Warning, Possible VNC port error:%s" % str(e))

    _PIPE = subprocess.PIPE
    vnc_process = subprocess.Popen(["gvncviewer", "localhost:%d" % vnc_port],
            stdout=_PIPE, stderr=_PIPE,
            close_fds=True)
    if kwargs.get('wait_vnc'):
        try:
            vnc_process.wait()
        except KeyboardInterrupt as e:
            LOG.info("keyboard interrupt while waiting VNC")
            if machine:
                machine.destroy()
    return machine


class MemoryReadProcess(multiprocessing.Process):
    #class MemoryReadProcess(threading.Thread):
    RET_SUCCESS = 1
    RET_ERRROR = 2

    def __init__(self, input_path, output_path, 
            machine_memory_size, output_queue):
        self.input_path = input_path
        self.output_path = output_path
        self.output_queue = output_queue
        self.machine_memory_size = machine_memory_size*1024
        multiprocessing.Process.__init__(self, target=self.read_mem_snapshot)
        #threading.Thread.__init__(self, target=self.read_mem_snapshot)

    def read_mem_snapshot(self):
        if os.path.isfile(self.input_path) != False:
            self.output_queue.put(self.RET_ERRROR)
            self.output_queue.put("Cannot open named pipe")

        # create memory snapshot aligned with 4KB
        try:
            self.in_fd = open(self.input_path, 'rb')
            self.out_fd = open(self.output_path, 'wb')

            total_read_size = 0
            # read first 40KB and aligen header with 4KB
            data = self.in_fd.read(Memory.Memory.RAM_PAGE_SIZE*10)
            libvirt_header = vmnetx._QemuMemoryHeaderData(data)
            original_header = libvirt_header.get_header()
            align_size = Memory.Memory.RAM_PAGE_SIZE*2
            new_header = libvirt_header.get_aligned_header(align_size)
            self.out_fd.write(new_header)
            total_read_size += len(new_header)
            self.out_fd.write(data[len(original_header):])
            total_read_size += len(data[len(original_header):])

            # write rest of the memory data
            prog_bar = AnimatedProgressBar(end=100, width=80, stdout=sys.stdout)
            while True:
                data = self.in_fd.read(1024 * 1024)
                if data == None or len(data) <= 0:
                    break
                self.out_fd.write(data)
                total_read_size += len(data)
                prog_bar.set_percent(100.0*total_read_size/self.machine_memory_size)
                prog_bar.show_progress()
            self.out_fd.flush()
            prog_bar.finish()
            if total_read_size != self.out_fd.tell():
                raise Exception("output file size is different from stream size")
        except Exception, e:
            LOG.error(str(e))
            self.output_queue.put(self.RET_ERRROR)
            self.output_queue.put(str(e))
        else:
            self.output_queue.put(self.RET_SUCCESS)


def save_mem_snapshot(machine, fout_path, **kwargs):
    #Set migration speed
    nova_util = kwargs.get('nova_util', None)
    ret = machine.migrateSetMaxSpeed(1000000, 0)   # 1000 Gbps, unlimited
    if ret != 0:
        raise CloudletGenerationError("Cannot set migration speed : %s", machine.name())

    # Pause VM
    machine.suspend()

    # get VM information
    machine_memory_size = machine.memoryStats().get('actual', None)
    if machine_memory_size is None:
        # libvirt <= 0.9.3
        xml = ElementTree.fromstring(machine.XMLDesc(libvirt.VIR_DOMAIN_XML_SECURE))
        memory_element = xml.find('memory')
        if memory_element is not None:
            machine_memory_size = long(memory_element.text)
    

    #Save memory state
    LOG.info("save VM memory state at %s" % fout_path)
    LOG.info("This could take up to minute depend on VM's memory size")
    LOG.info("(Check file at %s)" % fout_path)
    try:
        named_pipe_output = fout_path + ".fifo"
        output_queue = multiprocessing.Queue()
        os.mkfifo(named_pipe_output)
        memory_read_proc = MemoryReadProcess(named_pipe_output, fout_path, 
                machine_memory_size, output_queue)
        memory_read_proc.start()
        ret = machine.save(named_pipe_output)
        memory_read_proc.join()
    except libvirt.libvirtError, e:
        # we intentionally ignore seek error from libvirt since we have cause
        # that by using named pipe
        if os.path.exists(named_pipe_output):
            os.remove(named_pipe_output)
        if str(e).startswith('unable to seek') == False:
            raise CloudletGenerationError("libvirt memory save : " + str(e))
    finally:
        if machine is not None:
            _terminate_vm(machine)
            machine = None

    try:
        proc_ret = output_queue.get()
        if proc_ret != MemoryReadProcess.RET_SUCCESS:
            error_reason = output_queue.get()
            msg = "Failed to create memory snapshot : %s" % str(error_reason)
            LOG.error(msg)
            raise CloudletGenerationError(msg)
        if nova_util != None:
            # OpenStack runs VM with nova account and snapshot 
            # is generated from system connection
            nova_util.chown(fout_path, os.getuid())
    except vmnetx.MachineGenerationError, e:
        raise CloudletGenerationError("Machine Generation Error: " + str(e))
    finally:
        if machine is not None:
            _terminate_vm(machine)
            machine = None

    if ret != 0:
        raise CloudletGenerationError("libvirt: Cannot save memory state")


def run_snapshot(conn, disk_image, mem_snapshot, **kwargs):
    # kwargs
    # qemu_logfile      :   log file for QEMU-KVM
    # resume_time       :   write back the resumed_time
    received_xml = kwargs.get('new_xml', None)
    resume_time = kwargs.get('resume_time', None)
    logfile = kwargs.get('qemu_logfile', None)
    qemu_args = kwargs.get('qemu_args', None)
    if resume_time != None:
        start_resume_time = time()

    new_uuid = uuid4()
    if received_xml == None:
        # read embedded XML at memory snapshot to change disk path
        hdr = vmnetx._QemuMemoryHeader(open(mem_snapshot))
        old_xml = ElementTree.fromstring(hdr.xml)
        new_xml_string = _convert_xml(old_xml, conn, disk_path=disk_image,
                uuid=new_uuid, logfile=logfile, qemu_args=qemu_args)
    else:
        # get uuid and network information from new_xml
        hdr = vmnetx._QemuMemoryHeader(open(mem_snapshot))
        old_xml = ElementTree.fromstring(hdr.xml)
        new_xml = ElementTree.fromstring(received_xml)
        uuid_element = new_xml.find('uuid')
{'fraction_non_alphanumeric': 0.09167890190186773, 'fraction_numerical': 0.0037217878239491926, 'mean_word_length': 2.675772915533615, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 140}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5423982', 'n_tokens_mistral': 28458, 'n_tokens_neox': 27527, 'n_words': 5557}