// Copyright 2023 Google LLC
//
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

#include "bitmap.h"

#include "zfstlog.h"

extern int usage(void);
extern int post_process_bitmap_pair_zst(ram_bitmap_pair_t *bitmap_pair, const char* clone1_holes_file);
extern ram_bitmap_pair_t * generate_bitmap_zst(const char *parent, const char *child, int separate_bitmaps, const char* clone1_holes_file);
extern int create_bitmap_zst(const char *parent, const char *child, const char *bitmap, int separate_bitmaps, const char *clone1_holes_file);
extern ram_bitmap_t * generate_bitmap_raw(const char *parent, const char *child, uint64_t byte_offset, uint64_t byte_length);
extern int verify_bitmaps(const char *parent, const char *child, uint64_t byte_offset, uint64_t byte_length, int separate_bitmaps, const char* clone1_holes);
extern void show_bitmap(char *bitmap_file, uint64_t offset);

#ifndef ZFS_MAXNAMELEN
#define ZFS_MAXNAMELEN  (MAXNAMELEN - 1)
#endif

#define GRAINSIZE   ((unsigned)(64*1024))

int verbosity = 0;
int debug = 0;
unsigned int grainsize = GRAINSIZE;

void debug_print(int level, const char * file, const char * function, int line, const char * fmt, ...)
{
	char buffer[2048];
        va_list ap;
	if(verbosity >= level)
	{
		va_start(ap, fmt);
		vsnprintf(buffer, sizeof(buffer), fmt, ap);
		va_end(ap);
		fprintf(stderr,"[%s:%3d] (%s) %s\n", file, line, function, buffer);
	}
}

int usage(void)
{
    printf("Bitmap generation usage:\n");
    printf("  zfstool [options] [bitmap|zst-bitmap] clone1-name clone2-name /path/to/bitmap/file\n");
    printf("\toptions include:\n"
           "\t -v - verbosity (repeated one or more times, e.g. -v -v -v)\n"
           "\t -g size - grain size in bytes, default %d\n"
           "\t -z - generate a separate bitmap of writes, stored in /path/to/bitmap/file,\n"
	   "\t\t and a bitmap of holes, stored in /path/to/bitmap/file.holes,\n"
	   "\t -c /path/to/clone1/holes - option is valid only if -z is provided,\n"
	   "\t\t provides path to the hole bitmap file for clone1\n",
	grainsize);
    printf("\tcommands include:\n"
           "\t bitmap - use ZFS send stream to produce bitmap\n"
           "\t zst-bitmap - same as bitmap, included for backward compatibility\n");
    printf("Bitmap verification test usage:\n");
    printf("  zfstool [options] bitmap-verify clone-name clone-name {byte_offset}\n");
    printf("\toptions include:\n"
           "\t -v - verbosity (repeated one or more times, e.g. -v -v -v)\n"
           "\t -g size - grain size in bytes, default %d\n"
           "\t -z - generate separate bitmaps for writes  and frees\n"
	   "\t -c /path/to/clone1/holes - option is valid only if -z is provided,\n"
	   "\t\t provides path to the hole bitmap file for clone1\n"
           "\t if the byte_offset is specified, check the corresponding grain,\n"
           "\t otherwise, the whole bitmap is verified\n",
           grainsize);
    printf("Bitmap display usage:\n");
    printf("  zfstool bitmap-show bitmap-file {byte_offset}\n"
           "\t if the byte_offset is specified, show the corresponding grain,\n"
           "\t otherwise, the whole bitmap is displayed\n");
    return (-1);
}

/* ZFS send style bitmap calculation */
#include <sys/fs/zfs.h>
#include <libzfs.h>
#include <sys/zfs_ioctl.h>

#include "zst.h"

#define ZVOL_OBJECT     (1)
#define ZVOL_OBJLEN_MARKER  (~0ULL)

typedef struct {
    ram_bitmap_pair_t *bitmap_pair;
    uint64_t parent_volsize;
    uint64_t child_volsize;
} zst_callback_arg_t;

/*
 * Callbacks to be registered with ZST for getting the block level volume diffs
 */
static int
write_callback(int type, void *arg1, void *arg2)
{
    LOG_TRACE();
    struct drr_write *drrw = (struct drr_write *)arg1;
    zst_callback_arg_t *arg = (zst_callback_arg_t *)arg2;

    assert(type == DRR_WRITE);

    /* skip non-zvol object */
    if (drrw->drr_object != ZVOL_OBJECT)
    {
        LOG_ERR("drrw->drr_object != ZVOL_OBJECT");
        return (0);
    }

    if (drrw->drr_offset + drrw->drr_logical_size > arg->child_volsize) {
        LOG_INFO( "Write [0x%" PRIx64 ":0x%" PRIx64 ") outside zvol "
                "byte range [0x0:0x%" PRIx64 ")",
                drrw->drr_offset, drrw->drr_logical_size, arg->child_volsize);
        return (EINVAL);
    }

    LOG_INFO( "Write record found [0x%" PRIx64 ":0x%" PRIx64 ")",
                drrw->drr_offset, drrw->drr_offset + drrw->drr_logical_size);

    /* make a call to change the bitmap */
    bitmap_addbit(arg->bitmap_pair->diff_bitmap, drrw->drr_offset, drrw->drr_logical_size);

    return (0);
}

static int
write_embedded_callback(int type, void *arg1, void *arg2)
{
    LOG_TRACE();
    struct drr_write_embedded *drrwe = (struct drr_write_embedded *)arg1;
    zst_callback_arg_t *arg = (zst_callback_arg_t *)arg2;

    assert(type == DRR_WRITE_EMBEDDED);

    if (drrwe->drr_offset + drrwe->drr_length > arg->child_volsize) {
        LOG_INFO( "Write [%" PRIx64 ":%" PRIx64 ") outside zvol "
                "byte range [0:%" PRIx64 ")",
                drrwe->drr_offset, drrwe->drr_length, arg->child_volsize);
        return (EINVAL);
    }

    /* skip non-zvol object */
    if (drrwe->drr_object != ZVOL_OBJECT)
        return (0);

    LOG_INFO( "Write record found [%" PRIx64 ":%" PRIx64 ")",
                drrwe->drr_offset, drrwe->drr_offset + drrwe->drr_length);

    /* make a call to change the bitmap */
    bitmap_addbit(arg->bitmap_pair->diff_bitmap, drrwe->drr_offset, drrwe->drr_length);

    return (0);
}

static int
free_callback(int type, void *arg1, void *arg2)
{
    LOG_TRACE();
    struct drr_free *drrf = (struct drr_free *)arg1;
    zst_callback_arg_t *arg = (zst_callback_arg_t *)arg2;

    assert(type == DRR_FREE);

    /* skip non-zvol object */
    if (drrf->drr_object != ZVOL_OBJECT)
        return (0);

    if (drrf->drr_length == ZVOL_OBJLEN_MARKER) {
        LOG_INFO( "Truncate record found; offset 0x%" PRIx64 ,
                    drrf->drr_offset);
        if (drrf->drr_offset > arg->child_volsize) {
            LOG_INFO( "Offset 0x%" PRIx64 " in trancate record is "
                    "greater than child_volsize 0x%" PRIx64 ,
                    drrf->drr_offset, arg->child_volsize);
            return (EINVAL);
        }
        /*
         * avoid writing zeros in place of a whole at the end of the child
         * volume; update the size to the last offset used
         */
        arg->child_volsize = drrf->drr_offset;
        return (0);
    }

    LOG_INFO( "Free record found [0x%" PRIx64 ":0x%" PRIx64 ")",
            drrf->drr_offset, drrf->drr_offset + drrf->drr_length);

    /*
     * it is necessary to keep track of new holes that can be ligitimately
     * created with overwrites with zeros and block discards
     */

    if (drrf->drr_offset + drrf->drr_length > arg->child_volsize) {
        LOG_INFO( "\tThis free record goes outside the larger zvol "
                    "byte range [0x0:0x%"PRIx64"), perhaps due to previously "
                    "encountered truncate", arg->child_volsize);
        if (drrf->drr_offset >= arg->child_volsize) {
            LOG_INFO( "\tThis free record if entirely outside "
                        "zvol byte range [0x0:0x%"PRIx64"), perhaps due to "
                        "previously encountered truncate",
                        arg->child_volsize);
            return (0);
        }
        /*
         * adjust the length such that the change is within the zvol byte range
         */
        drrf->drr_length = arg->child_volsize - drrf->drr_offset;
        LOG_INFO( "Adjusted record to [0x%" PRIx64 ":0x%" PRIx64 ")",
                    drrf->drr_offset, drrf->drr_offset + drrf->drr_length);
    }

    /*
     * Make a call to change bitmaps.
     * If free_bitmap is present, generate separate bitmaps for writes and frees
     * and therefore, update the free_bitmap; otherwise, generate a consolidated
     * bitmap by writing free bits into the diff_bitmap.
     */
    if (arg->bitmap_pair->free_bitmap) {
	LOG_INFO( "Generating separate bitmap diffs for free region");
	bitmap_addbit(arg->bitmap_pair->free_bitmap, drrf->drr_offset, drrf->drr_length);
    } else {
	 LOG_INFO( "Generating consolidated bitmap diffs for free region");
	bitmap_addbit(arg->bitmap_pair->diff_bitmap, drrf->drr_offset, drrf->drr_length);
    }

    return (0);
}


/*
 * Given the separate bitmaps for writes and frees, post-process as follows:
 *
 * - if the clone1_holes_file is available, filter the old holes (clone1_holes)
 * out from the new holes bitmap (free_bitmap)
 * - consolidate the writes and holes bitmaps into the diff_bitmap
 */
int
post_process_bitmap_pair_zst(ram_bitmap_pair_t *bitmap_pair,
			     const char* clone1_holes_file)
{
    struct stat cbstat;
    int rc = 0;
    ram_bitmap_t *clone1_holes = NULL, *consolidated_holes = NULL;
    
    if ((consolidated_holes = bitmap_dup(bitmap_pair->free_bitmap)) == NULL)
	return (-1);

    if (debug) {
	fprintf(stdout, "Writes bitmap as calculated:\n");
	bitmap_show(bitmap_pair->diff_bitmap, ~0ULL);
	fprintf(stdout, "Holes bitmap as calculated:\n");
	bitmap_show(bitmap_pair->free_bitmap, ~0ULL);
    }

    do {
	if (stat(clone1_holes_file, &cbstat) == 0) {
	    if ((clone1_holes = bitmap_read(clone1_holes_file)) == NULL)
		break;
	    if (debug) {
		fprintf(stdout, "Clone1 holes bitmap as specified:\n");
		bitmap_show(clone1_holes, ~0ULL);
	    }
	    /*
	     * consolidate the holes by adding old consolidated holes and 
	     * new holes, then subtracting the writes (in the common code
	     * path below)
	     */
	    if ((rc = bitmap_add(consolidated_holes, clone1_holes,
				 bitmap_pair->free_bitmap)))
		break;
	    if (debug) {
		fprintf(stdout, "Consolidated holes before subtracting writes:\n");
		bitmap_show(consolidated_holes, ~0ULL);
	    }
	    /*
	     * calculate new holes by subtracting old consolidated holes
	     * from the calculated new holes
	     */
	    if ((rc = bitmap_subtract(bitmap_pair->free_bitmap,
				      bitmap_pair->free_bitmap, clone1_holes)))
		break;
	    if (debug) {
		fprintf(stdout, "New holes (calculated - old holes):\n");
		bitmap_show(bitmap_pair->free_bitmap, ~0ULL);
	    }

	    bitmap_destroy(clone1_holes);
	    clone1_holes = NULL;
	}

	/*
	 * subtract the new writes from the consolidated holes
	 */
	if ((rc = bitmap_subtract(consolidated_holes, consolidated_holes,
				  bitmap_pair->diff_bitmap)))
	    break;
	/*
	 * at this point, the consolidated_holes are new consolidated holes, and
	 * the bitmap_pair->free_bitmap is new holes with old ones filtered out
	 *
	 * now calculate the diff bitmap by OR-ing bitmap_pair->diff_bitmap and
	 * the filtered bitmap_pair->free_bitmap
	 */
	if ((rc = bitmap_add(bitmap_pair->diff_bitmap, bitmap_pair->diff_bitmap,
			     bitmap_pair->free_bitmap)))
	    break;
	/*
	 * now replace free_bitmap in the pair with the new consolidated bitmap
	 */
	bitmap_destroy(bitmap_pair->free_bitmap);
	bitmap_pair->free_bitmap = consolidated_holes;
	
	if (debug) {
	    fprintf(stdout, "Diff bitmap post-processed:\n");
	    bitmap_show(bitmap_pair->diff_bitmap, ~0ULL);
	    fprintf(stdout, "Holes bitmap post-processed:\n");
	    bitmap_show(bitmap_pair->free_bitmap, ~0ULL);
	}
    } while (0);

    /* cleanup */
    if (rc) {
	if (clone1_holes)
	    bitmap_destroy(clone1_holes);
	if (consolidated_holes)
	    bitmap_destroy(consolidated_holes);
    }

    return (rc);
}

/*
 * The function calculates "GRAIN"-wise differential bitmap, and optionally,
 * generates bitmap of holes reported in the zfs send stream, between two zfs
 * snapshots. The parent and child names below are device names of the clones
 * in the format 'poolname/volname'; the clones' 'origin'
 * property contains the snapshot names to be diffed.
 * Therefore, proceed as follows:
 *    obtain the snapshot names (snap1 - parent, snap2 - child)
 *    call zfs send -Bi snap1 snap2 | diff_fd
 *    read stream records form diff_fd and fill out the (initially empty) bitmap(s)
 */
ram_bitmap_pair_t *
generate_bitmap_zst(const char *parent, const char *child, int separate_bitmaps,
		    const char* clone1_holes_file)
{
    libzfs_handle_t *g_zfs = NULL;
    zfs_handle_t *parent_zhp = NULL, *child_zhp = NULL;
    zst_handle_t *hdl = NULL;
    zprop_source_t src;
    char parent_origin[ZFS_MAXNAMELEN];
    char child_origin[ZFS_MAXNAMELEN];
    char buffer[64 + 2 * ZFS_MAXNAMELEN];
    int diff_fd = -1, i;
    FILE *diff_fp = NULL;
    uint64_t parent_volsize = ~0ULL, child_volsize = ~0ULL;
    uint64_t blocksize = ~0ULL;
    zst_callback_descr_t zc[3];
    ram_bitmap_pair_t *bitmap_pair = NULL;
    zst_callback_arg_t arg;
    int rc = 0;

    /* init libzfs handle */
    if ((g_zfs = libzfs_init()) == NULL) {
        LOG_ERR( "Failed to initialize libzfs handle");
        exit(-1);
    }

    /* must be zvols */
    if ((parent_zhp = zfs_open(g_zfs, parent, ZFS_TYPE_VOLUME)) == NULL ||
        (child_zhp = zfs_open(g_zfs, child, ZFS_TYPE_VOLUME)) == NULL) {
        LOG_ERR( "Parent %s or child %s is not a volume",
                parent, child);
        exit(-1);
    }

    /* get origin and size properties */
    (void) zfs_prop_get(parent_zhp, ZFS_PROP_ORIGIN, parent_origin,
                        ZFS_MAXNAMELEN, &src, NULL, 0, B_FALSE);
    (void) zfs_prop_get(child_zhp, ZFS_PROP_ORIGIN, child_origin,
                        ZFS_MAXNAMELEN, &src, NULL, 0, B_FALSE);
    (void) zfs_prop_get(parent_zhp, ZFS_PROP_VOLSIZE, buffer,
                        ZFS_MAXNAMELEN, &src, NULL, 0, B_TRUE);
    sscanf(buffer, "%" PRIu64 "", &parent_volsize);
    (void) zfs_prop_get(child_zhp, ZFS_PROP_VOLSIZE, buffer,
                        ZFS_MAXNAMELEN, &src, NULL, 0, B_TRUE);
    sscanf(buffer, "%" PRIu64 "", &child_volsize);
    (void) zfs_prop_get(child_zhp, ZFS_PROP_VOLBLOCKSIZE, buffer,
                        ZFS_MAXNAMELEN, &src, NULL, 0, B_TRUE);
    sscanf(buffer, "%" PRIu64 "", &blocksize);

    /* done with the datasets */
    zfs_close(parent_zhp);
    zfs_close(child_zhp);
    libzfs_fini(g_zfs);

    /* must be a snapshot name */
    if (NULL == strchr(parent_origin, '@') ||
        NULL == strchr(child_origin, '@')) {
        LOG_INFO( "Origin of parent %s or child %s (%s/%s) is not a "
                "snapshot", parent, child, parent_origin, child_origin);
    }

    if (parent_volsize > child_volsize) {
        LOG_ERR( "Parent volume size 0x%" PRIx64 " cannot be larger "
                "than child volume size 0x%" PRIx64 ,
                parent_volsize, child_volsize);
        exit(-1);
    }

    /* create the bitmap */
    bitmap_pair = bitmap_pair_create(child_volsize, grainsize);
    if (bitmap_pair == NULL) {
        LOG_ERR( "Failed to create bitmaps, not enough memory");
        exit(-1);
    }

    if (separate_bitmaps == 0) {
	/* free the bitmap to indicate consolidated bitmap processing */
	bitmap_destroy(bitmap_pair->free_bitmap);
	bitmap_pair->free_bitmap = NULL;
    }

    /* build callback context argument */
    arg.bitmap_pair = bitmap_pair;
    arg.parent_volsize = parent_volsize;
    arg.child_volsize = child_volsize;

    /* run zfs send and get the output in a pipe */
    (void) snprintf(buffer, sizeof(buffer), "zfs send -B -i %s %s",
                    parent_origin, child_origin);
    LOG_DEBUG("Running zfs command: %s", buffer);

    diff_fp = popen(buffer, "r");
    if (NULL == diff_fp) {
        LOG_ERR( "failed to run %s", buffer);
        exit(-1);
    }
    diff_fd = fileno(diff_fp);
    if (diff_fd == -1) {
        LOG_ERR( "invalid file descriptor from popen(%s)", buffer);
        exit(-1);
    }

    /* init send stream traversal handle */
    if ((hdl = zst_init(diff_fd)) == NULL) {
        LOG_ERR( "zst_init() failed, not enough memory");
        exit(-1);
    }

    /* register traversal callbacks */
    zc[0].rtype = DRR_WRITE;
    zc[0].cb = write_callback;
    zc[0].arg = &arg;
    zc[1].rtype = DRR_WRITE_EMBEDDED;
    zc[1].cb = write_embedded_callback;
    zc[1].arg = &arg;
    zc[2].rtype = DRR_FREE;
    zc[2].cb = free_callback;
    zc[2].arg = &arg;

    for (i = 0; i < 3; i++) {
        if (zst_register_callback(hdl, &zc[i]) < 0) {
            LOG_ERR( "zst_register_callback() failed");
            exit(-1);
        }
    }

    /* invoke traversal */
    if ((rc = zst_traverse(hdl))) {
        LOG_ERR( "zst_traverse() error: %d", rc);
    }

    /* fini handle */
    if (zst_fini(hdl) < 0) {
        LOG_ERR( "zsf_fini() error");
        exit(-1);
    }

    /* done with the pipe */
    (void) pclose(diff_fp);

    if (rc) {
        bitmap_pair_destroy(bitmap_pair);
        return (NULL);
    }
    
    if (separate_bitmaps) {
	/*
	 * make sure that the grain is less or equal to the block size
	 * if using the separate bitmap optimization
	 */
	if (blocksize % grainsize) {
	    LOG_ERR(
		    "cannot use separate bitmaps when blocksize %" PRIu64 
		    " is not a multiple of grainsize %d",
		    blocksize, grainsize);
	    exit(-1);
	}

	rc = post_process_bitmap_pair_zst(bitmap_pair, clone1_holes_file);
	if (rc) {
	    LOG_ERR( "bitmap post-process error");
	    exit(-1);
	}
    }

    return (bitmap_pair);
}

int
create_bitmap_zst(const char *parent, const char *child,
		  const char *bitmap, int separate_bitmaps,
		  const char *clone1_holes_file)
{
    ram_bitmap_pair_t *bitmap_pair = NULL;

    if ((bitmap_pair = generate_bitmap_zst(parent, child,
					   separate_bitmaps,
					   clone1_holes_file)) == NULL){
    	LOG_ERR("generate_bitmap_zst failed");
        return (-1);
    }

    if (separate_bitmaps) {
	/*
	 * get path for the new holes file - 'bitmap-path'.holes\0
	 * write out the new holes
	 */
	char *new_path = malloc(strlen(bitmap)+strlen(".holes")+1);
	strcpy(new_path, bitmap);
	strcat(new_path, ".holes");
        holemap_write(bitmap_pair->free_bitmap, new_path);
	free(new_path);
    }
    
    bitmap_write(bitmap_pair->diff_bitmap, bitmap);
    bitmap_pair_destroy(bitmap_pair);

    return (0);
}

/* Bitmap verification modes */

ram_bitmap_t *
generate_bitmap_raw(const char *parent, const char *child, uint64_t byte_offset, uint64_t byte_length)
{
    enum { PARENT, CHILD, DONE};
    int fd[DONE];
    ram_bitmap_t *diff_bitmap = NULL; 
    libzfs_handle_t *g_zfs = NULL;
    zfs_handle_t *parent_zhp = NULL, *child_zhp = NULL;
    zprop_source_t src;
    char buffer[64 + ZFS_MAXNAMELEN];
    uint64_t parent_volsize = ~0ULL, child_volsize = ~0ULL;
    uint64_t i = 0;
    /* round down start offset */
    uint64_t grain_offset_start = byte_offset / grainsize;
    /* round up end offset */
    uint64_t grain_offset_end = (byte_offset + byte_length + grainsize - 1) / grainsize;

    /* init libzfs handle */
    if ((g_zfs = libzfs_init()) == NULL) {
        LOG_ERR( "Failed to initialize libzfs handle");
        exit(-1);
    }

    /* must be zvols */
    if ((parent_zhp = zfs_open(g_zfs, parent, ZFS_TYPE_VOLUME)) == NULL ||
        (child_zhp = zfs_open(g_zfs, child, ZFS_TYPE_VOLUME)) == NULL) {
        LOG_ERR( "Parent %s or child %s is not a volume",
                parent, child);
        exit(-1);
    }

    /* get size properties */
    (void) zfs_prop_get(parent_zhp, ZFS_PROP_VOLSIZE, buffer,
                        ZFS_MAXNAMELEN, &src, NULL, 0, B_TRUE);
    sscanf(buffer, "%" PRIu64 "", &parent_volsize);
    (void) zfs_prop_get(child_zhp, ZFS_PROP_VOLSIZE, buffer,
                        ZFS_MAXNAMELEN, &src, NULL, 0, B_TRUE);
    sscanf(buffer, "%" PRIu64 "", &child_volsize);

    /* done with the datasets */
    zfs_close(parent_zhp);
    zfs_close(child_zhp);
    libzfs_fini(g_zfs);

    if (parent_volsize > child_volsize) {
        LOG_ERR( "Parent volume size 0x%" PRIx64 " cannot be larger "
                "than child volume size 0x%" PRIx64 "",
                parent_volsize, child_volsize);
        exit(-1);
    }

    /* volume sizes should be integer number of grains */
    if (parent_volsize % grainsize || child_volsize % grainsize) {
        LOG_ERR( "Parent volume size 0x%" PRIx64
                "or child volume size 0x%" PRIx64
                "is not a multiple of grain size 0x%x",
                parent_volsize, child_volsize, grainsize);
        exit(-1);
    }

    /* create the bitmap */
    diff_bitmap = bitmap_create(child_volsize, grainsize);
    if (diff_bitmap == NULL) {
        LOG_ERR( "Failed to create bitmap, not enough memory");
        return (NULL);
    }
    /* open parent and child */
    snprintf(buffer, sizeof(buffer), "/dev/zvol/%s", parent);
    if ((fd[PARENT] = open(buffer, O_RDONLY)) < 0) {
        char errbuf[256];
	memset(errbuf,0,sizeof(errbuf));
	strerror_r(errno, errbuf, sizeof(errbuf)-1);
	LOG_ERR("%s: parent %s open() failed", errbuf, parent);
        exit(-1);
    }
    snprintf(buffer, sizeof(buffer), "/dev/zvol/%s", child);
    if ((fd[CHILD] = open(buffer, O_RDONLY)) < 0) {
        char errbuf[256];
	memset(errbuf,0,sizeof(errbuf));
	strerror_r(errno, errbuf, sizeof(errbuf)-1);
	LOG_ERR("%s: child %s open() failed", errbuf, child);
        exit(-1);
    }

    /* read grains from parent and child and memcmp() those */
    for (i = 0; i < parent_volsize/grainsize; i++) {
        char dbuffer[DONE][grainsize];
        ssize_t rd, rc;
        int a;

        /* only interested in one specific byte range */
        if ((byte_offset != ~0ULL) &&
	    (i < grain_offset_start || i >= grain_offset_end))
            continue;

        for (a = PARENT; a < DONE; a++) {
            for (rd = 0; rd < grainsize; rd += rc) {
		    rc = pread(fd[a], &(dbuffer[a][rd]), grainsize, i * grainsize);
                if (rc <= 0)
                    break;
            }
            if (rd < grainsize) {
                LOG_ERR( "read() of %s failed", (a == PARENT) ? "parent" : "child");
                exit(-1);
            }
        }
        if (memcmp(&(dbuffer[PARENT][0]), &(dbuffer[CHILD][0]), grainsize)) {
            /* grain is different, add bit to the bitmap */
            bitmap_addbit(diff_bitmap, i*grainsize, grainsize);
        }
    }

    /*
     * if child is larger than the parent, all but zero-filled grains beyond the
     * parent size are different; the latter is due to the sparse nature of zvols
     * that are used
     */
    if (i < child_volsize/grainsize) {
        char zeros[grainsize];

        memset(zeros, 0, grainsize);

        for (; i < child_volsize/grainsize; i++) {
            char dbuffer[grainsize];
            ssize_t rd, rc;

            for (rd = 0; rd < grainsize; rd += rc) {
                rc = read(fd[CHILD], &(dbuffer[rd]), grainsize);
                if (rc <= 0)
                    break;
            }
            if (rd < grainsize) {
                LOG_ERR( "read() of child failed");
                exit(-1);
            }

            if (memcmp(&(dbuffer[0]), &(zeros[0]), grainsize)) {
                /* grain is different, add bit to the bitmap */
                bitmap_addbit(diff_bitmap, i*grainsize, grainsize);
            }
        }
    }

    close(fd[PARENT]);
    close(fd[CHILD]);

    return (diff_bitmap);
}

/*
 * Verify the bitmap generation code by comparing a bitmap generated with
 * ZST based approaches with a raw bitmap generated by bitwise comparison
 * of grain size blocks of the parent and the child
 */
int verify_bitmaps(const char *parent, const char *child, uint64_t byte_offset,
		   uint64_t byte_length, int separate_bitmaps,
		   const char* clone1_holes)
{
    ram_bitmap_pair_t *bmap_pair_zst = NULL;
    ram_bitmap_t *bmap_raw = NULL;
    int rc = 0;

    printf("Verifying ZST based bitmap by bitwise comparison of the volumes\n");

    bmap_pair_zst = generate_bitmap_zst(parent, child, separate_bitmaps,
					clone1_holes);
    bmap_raw = generate_bitmap_raw(parent, child, byte_offset, byte_length);

    /* Make sure the grainsize argument is correct */
    if (grainsize != bmap_pair_zst->diff_bitmap->mqhdr.grain_size_lbas*LBAS_SIZE) {
	printf("Invalid grain size %u specified - the bitmap uses %u\n", grainsize,
	       bmap_pair_zst->diff_bitmap->mqhdr.grain_size_lbas*LBAS_SIZE);
	return (EINVAL);
    }

    if (byte_offset == ~0ULL) {
        /* generate/verify whole bitmaps */
	uint64_t 
	    raw_bits = bitmap_get_bitcount(bmap_raw),
	    write_bits = bitmap_get_bitcount(bmap_pair_zst->diff_bitmap),
	    free_bits = (bmap_pair_zst->free_bitmap) ? 
	    bitmap_get_bitcount(bmap_pair_zst->free_bitmap) : 0;
        printf("Summary: %s has %"PRIi64" bits set, "
               "%s has %"PRIi64" bits set, "
               "%s has %"PRIi64" bits set\n",
               "raw bitmap", raw_bits,
               "write bitmap", write_bits,
	       "free bitmap", free_bits);
        /*
         * compare - in this comparison, we are looking to make sure that the
         * the second bitmap is not missing any bits set in the first bitmap
         */
        printf("Verifying ZST based bitmap against raw bitmap\n");
        rc = bitmap_compare(bmap_raw, bmap_pair_zst->diff_bitmap);
        if (rc)
            printf("Error - missing bits in ZST bitmap\n");
        else
            printf("ZST bitmap has at least as many bits as "
                   "raw bitmap\n");
    } else {
        /* grain range check */
	uint64_t i;

	printf("%24s %5s %5s %5s\n", "Byte offset", "Diff", "Raw", "Hole");
	for (i = byte_offset; i < (byte_offset + byte_length); i+=grainsize) {
	    int zst_bit = bitmap_get_bit(bmap_pair_zst->diff_bitmap, i);
	    int raw_bit = bitmap_get_bit(bmap_raw, i);
	    int hole_bit = bitmap_get_bit(bmap_pair_zst->diff_bitmap, i);

	    printf("0x%-21"PRIx64" %5d %5d %5d\n", i, zst_bit, raw_bit, hole_bit);
	}
    }

    if (rc) {
	    /* write out the bitmaps for further analysis */
	    printf("Bitmaps are saved for further analysis in /tmp/bitmap.*\n");
	    bitmap_write(bmap_pair_zst->diff_bitmap, "/tmp/bitmap.diff");
	    if (bmap_pair_zst->free_bitmap)
		bitmap_write(bmap_pair_zst->free_bitmap, "/tmp/bitmap.hole");
	    bitmap_write(bmap_raw, "/tmp/bitmap.raw");
    }

    /* cleanup */
    bitmap_pair_destroy(bmap_pair_zst);
    bitmap_destroy(bmap_raw);

    return (rc);
}

void show_bitmap(char *bitmap_file, uint64_t offset)
{
    ram_bitmap_t *bitmap = bitmap_read(bitmap_file);

    if (bitmap == NULL)
	exit(-1);

    bitmap_show(bitmap, offset);
    bitmap_destroy(bitmap);
}

int main(int argc, char **argv)
{
    int rc = 0, opt, index = 0, separate_bitmaps = 0;
    char *clone1_holes = NULL;

    /* process getopt-style arguments */
    while ((opt = getopt(argc, argv, "hvzdg:c:")) != -1) {
        switch (opt) {
        case 'h':
            usage();
            return (0);
            break;
        case 'v':
            verbosity++;
            index++;
            break;
        case 'd':
	    debug++;
            index++;
            break;
        case 'g':
            index++;
            grainsize = (unsigned)atoi(optarg);
            index++;
            break;
        case 'z':
            separate_bitmaps = 1;
            index++;
            break;
	case 'c':
            index++;
	    clone1_holes = optarg;
            index++;
            break;
        case '?':
            usage();
            LOG_ERR( "invalid argument %c\n", optopt);
            return (-1);
        }
    }

    /* fast-forward the arguments */
    argc -= index;
    argv += index;

    if (argc < 3)
        return (usage());
    if (separate_bitmaps == 0 && clone1_holes)
	return (usage());
    do {
	int mask;
	for (mask = grainsize - 1; (mask && (mask & 1)); mask >>= 1)
	    ;
	if (mask) {
	    LOG_ERR( "grainsize %u is not a power of two\n", grainsize);
	}
    } while (0);
	
    if ((strcmp (argv[1], "bitmap") == 0) ||
        (strcmp (argv[1], "zst-bitmap") == 0)) {
        /*
         * invoke ZFS send-based bitmap generation code
         */
        if (argc != 5)
            return (usage());
        rc = create_bitmap_zst(argv[2], argv[3], argv[4],
			       separate_bitmaps, clone1_holes);
        if (rc) {
            fprintf(stdout, "failed to generate bitmap, error %d\n", rc);
        }
    }
    else if (strcmp (argv[1], "bitmap-verify") == 0) {
	uint64_t offset = ~0ULL, length = 0ULL;
        if (argc < 4)
            return (usage());
        if (argc > 4)
            sscanf(argv[4], "%"PRIi64"", &offset);
        if (argc > 5)
            sscanf(argv[5], "%"PRIi64"", &length);
        rc = verify_bitmaps(argv[2], argv[3], offset, length,
			    separate_bitmaps, clone1_holes);
        if (rc) {
            fprintf(stdout, "failed to verify bitmap, error %d\n", rc);
        }
    }
    else if (strcmp (argv[1], "bitmap-show") == 0) {
        uint64_t offset = ~0ULL;
        if (argc < 3)
            return (usage());
        if (argc > 3)
            sscanf(argv[3], "%"PRIi64"", &offset);
        show_bitmap(argv[2], offset);
    }
    else return usage();

    return (rc);
}