| /* ============================================================ |
| * Copyright (c) 2014 Actifio Inc. All Rights Reserved |
| * ============================================================= |
| */ |
| |
| #include <stdlib.h> |
| #include <assert.h> |
| #include <sys/stat.h> |
| #include <errno.h> |
| #include <stdbool.h> |
| #include <fcntl.h> |
| |
| #include "bitmap.h" |
| |
| extern int verbosity; |
| |
| #define COMPRESSION_LEVEL 6 |
| void bitmap_fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream); |
| bool is_buffer_zeroed(unsigned char *buffer, uint64_t size); |
| int pwrite_data(const int fd, const void *buf, size_t size, off_t write_offset); |
| int bitmap_write_sparse(const int fd, uint64_t bitmap_size_bytes, unsigned char *buf); |
| |
| ram_bitmap_t *bitmap_create(uint64_t volsize, unsigned int grainsize) |
| { |
| uint64_t size = sizeof(fc_bitmap_hdr_t) + sizeof(fc_bitmap_mq_hdr_t); |
| /* Roundup to grainsize and to the next byte */ |
| uint64_t bmsize = (((volsize + grainsize - 1) / grainsize) + 8 - 1) / 8; |
| |
| if (volsize % LBAS_SIZE || grainsize % LBAS_SIZE) { |
| printf("Invalid alignment: volsize/grainsize %"PRIi64"/%u " |
| "should be multible of LBAS %u\n", volsize, grainsize, LBAS_SIZE); |
| return NULL; |
| } |
| if (volsize % grainsize) { |
| printf("Invalid alignment: volsize %"PRIi64" should be multible of grainsize %u\n", |
| volsize, grainsize); |
| return NULL; |
| } |
| size += bmsize; |
| |
| ram_bitmap_t * bitmap = (ram_bitmap_t *) malloc(size); |
| |
| assert(bitmap); |
| memset(bitmap,0,size); |
| |
| bitmap->mqhdr.grain_size_lbas = grainsize/LBAS_SIZE; |
| bitmap->mqhdr.vdisk_size_lbas = volsize/LBAS_SIZE; |
| bitmap->mqhdr.bitmap_size_bytes = bmsize; |
| |
| bitmap->mqhdr.bitmap_mq_magic[0] = ((FC_BITMAP_MQ_MAGIC >> 24) & 0xFF); |
| bitmap->mqhdr.bitmap_mq_magic[1] = ((FC_BITMAP_MQ_MAGIC >> 16) & 0xFF); |
| bitmap->mqhdr.bitmap_mq_magic[2] = ((FC_BITMAP_MQ_MAGIC >> 8) & 0xFF); |
| bitmap->mqhdr.bitmap_mq_magic[3] = (FC_BITMAP_MQ_MAGIC & 0xFF); |
| |
| // Let's make sure we did this right. |
| assert( bitmap->mqhdr.bitmap_size_bytes == bmsize); |
| |
| return bitmap; |
| } |
| |
| ram_bitmap_t *bitmap_dup(ram_bitmap_t *bitmap) |
| { |
| ram_bitmap_t *new_bitmap = |
| bitmap_create(bitmap->mqhdr.vdisk_size_lbas*LBAS_SIZE, |
| bitmap->mqhdr.grain_size_lbas*LBAS_SIZE); |
| if (new_bitmap) |
| bcopy(&(bitmap->bits[0]), &(new_bitmap->bits[0]), |
| bitmap->mqhdr.bitmap_size_bytes); |
| |
| return (new_bitmap); |
| } |
| |
| void bitmap_destroy(ram_bitmap_t *bitmap) |
| { |
| free(bitmap); |
| } |
| |
| ram_bitmap_pair_t *bitmap_pair_create(uint64_t volsize, unsigned int grainsize) |
| { |
| ram_bitmap_pair_t *pair = malloc(sizeof(ram_bitmap_pair_t)); |
| if (pair == NULL) |
| return NULL; |
| |
| pair->diff_bitmap = bitmap_create(volsize, grainsize); |
| if (pair->diff_bitmap == NULL) { |
| free(pair); |
| return NULL; |
| } |
| |
| pair->free_bitmap = bitmap_create(volsize, grainsize); |
| if (pair->free_bitmap == NULL) { |
| free(pair->diff_bitmap); |
| free(pair); |
| return NULL; |
| } |
| |
| return pair; |
| } |
| |
| void bitmap_pair_destroy(ram_bitmap_pair_t *pair) |
| { |
| if (pair) { |
| if (pair->free_bitmap) |
| bitmap_destroy(pair->free_bitmap); |
| if (pair->diff_bitmap) |
| bitmap_destroy(pair->diff_bitmap); |
| free(pair); |
| } |
| } |
| |
| void bitmap_addbit(ram_bitmap_t *diffbitmap, uint64_t rangeaddr, uint64_t rangesize) |
| { |
| /* |
| * Get the (first) grain that contains rangeaddr, get the (last) grain that contains |
| * rangeadd+rangesize, then walk through the range of grains including the last |
| * changed grain and set the bits |
| */ |
| uint64_t start_block = rangeaddr/(diffbitmap->mqhdr.grain_size_lbas * LBAS_SIZE); |
| uint64_t end_block = (rangeaddr + rangesize - 1)/(diffbitmap->mqhdr.grain_size_lbas * LBAS_SIZE); |
| uint64_t b; |
| |
| for (b = start_block; b <= end_block; b++) { |
| uint64_t byte_idx = b / 8; |
| int bit_idx = b % 8; |
| diffbitmap->bits[byte_idx] |= (uint8_t)(1 << bit_idx); |
| } |
| } |
| |
| void bitmap_fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream) |
| { |
| if (fwrite(ptr, size, nmemb, stream) != nmemb) |
| { |
| fprintf(stderr,"Error: cannot write to bitmap file\n"); |
| exit(-1); |
| } |
| } |
| |
| |
| bool is_buffer_zeroed(unsigned char *buffer, uint64_t size) |
| { |
| return !(bool)(*buffer || memcmp(buffer, buffer + 1, (size_t)size - 1)); |
| } |
| |
| /* This routine will keep calling pwrite until all the bytes in a block gets written. |
| * Subsequent pwrite calls will attempt to write only the remaining bytes. |
| * At any point of time if pwrite returns a value <= 0, error will be thrown. |
| */ |
| int pwrite_data(const int fd, const void *buf, size_t size, off_t write_offset) |
| { |
| off_t read_offset = 0; |
| int rem = size; |
| while (rem) { |
| int nbytes = pwrite(fd, buf + read_offset, rem, write_offset); |
| if (nbytes <= 0) |
| return -1; |
| rem -= nbytes; |
| read_offset += nbytes; |
| write_offset += nbytes; |
| } |
| return 0; |
| } |
| /* |
| * Write bitmap portion (without headers) of ram_bitmap_t in sparse manner |
| */ |
| int bitmap_write_sparse(const int fd, uint64_t bitmap_size_bytes, unsigned char *buf) |
| { |
| ftruncate(fd, (FC_BITMAP_BITMAP_OFFSET + bitmap_size_bytes)); |
| int64_t i, remainder, chunks; |
| off_t read_offset = 0; |
| off_t write_offset = FC_BITMAP_BITMAP_OFFSET; |
| chunks = bitmap_size_bytes / LBAS_SIZE; |
| remainder = bitmap_size_bytes % LBAS_SIZE; |
| |
| for (i = 0; i < chunks; i++) { |
| if (!(is_buffer_zeroed(&buf[read_offset], LBAS_SIZE))) { |
| if (pwrite_data(fd, buf + read_offset, LBAS_SIZE, write_offset) < 0) |
| return -1; |
| } |
| read_offset += LBAS_SIZE; |
| write_offset += LBAS_SIZE; |
| } |
| |
| if (remainder) { |
| if (pwrite_data(fd, buf + read_offset, remainder, write_offset) < 0) |
| return -1; |
| } |
| return 0; |
| } |
| |
| void bitmap_write(ram_bitmap_t *diff_bitmap, const char * bitmap) |
| { |
| struct stat sb; |
| int fd = open(bitmap, O_CREAT|O_WRONLY, 0666); |
| if(fd < 0) { |
| fprintf(stderr,"Error: cannot create bitmap file %s: %s\n", bitmap, strerror(errno)); |
| exit(-1); |
| } |
| |
| if(fstat(fd, &sb)) { |
| fprintf(stderr,"Error: cannot retrieve file info %s: %s\n", bitmap, strerror(errno)); |
| close(fd); |
| exit(-1); |
| } |
| /* write out the bm header only if this is a new file |
| * for existing bitmap, bmhdr is already up to date, we just need to update mqhdr and |
| * the actual bitmap |
| */ |
| if(!sb.st_size && (pwrite_data(fd, &diff_bitmap->bmhdr, sizeof(diff_bitmap->bmhdr), 0) < 0)) |
| goto write_fail; |
| |
| /* mqhdr needs to be updated even if it is an already existing file. Bitmap size (initially 0) |
| * and other fields of mqhdr will be modified here |
| */ |
| if (pwrite_data(fd, &diff_bitmap->mqhdr, sizeof(diff_bitmap->mqhdr), FC_BITMAP_MQ_HDR_OFFSET) < 0) |
| goto write_fail; |
| |
| if (bitmap_write_sparse(fd, diff_bitmap->mqhdr.bitmap_size_bytes, diff_bitmap->bits) < 0) |
| goto write_fail; |
| |
| if (close(fd)) { |
| fprintf(stderr, "Error: unable to close fd %s: %s\n", bitmap, strerror(errno)); |
| exit(-1); |
| } |
| return; |
| |
| write_fail: |
| fprintf(stderr, "Error: unable to write bitmap %s : %s\n", bitmap, strerror(errno)); |
| close(fd); |
| exit(-1); |
| } |
| |
| extern size_t gzip_compress(void *src, void *dst, size_t s_len, size_t d_len, int level); |
| extern int gzip_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n); |
| |
| /* |
| * Because of runs of 1s, holemap files don't sparsify well. |
| * This function will compress the bitmap portion of ram_bitmap_t before |
| * persisting it to the disk |
| */ |
| void holemap_write(ram_bitmap_t *free_bitmap, const char * holemap) |
| { |
| int exists = 0; |
| struct stat sb; |
| // size_t nread; |
| FILE *bm; |
| unsigned char * compressed_bitmap; |
| |
| u_int64_t size = free_bitmap->mqhdr.bitmap_size_bytes; |
| compressed_bitmap = (unsigned char *) malloc(size); |
| assert(compressed_bitmap); |
| memset(compressed_bitmap,0,size); |
| |
| /* In some cases compression output is worse than input, and thus it won't fit. This will cause the |
| * library to return failure. gzip_compress() indicates this failure by returning original input size. |
| * However in failure case, gzip_compress() simply copies data from src to dest buffer if s_len, d_len |
| * parameters have the same value. Therefore to avoid unnecessary copying, dst_len = src-len - 1 is |
| * being passed. |
| * If return value of gzip_compress() equals original size, it'll be identified as error scenario and |
| * original uncompressed bitmap will be written to the disk. |
| */ |
| u_int64_t dest_size = gzip_compress(free_bitmap->bits, compressed_bitmap, size, size-1, COMPRESSION_LEVEL); |
| |
| if(stat(holemap, &sb)==0) |
| exists = 1; |
| |
| if (exists) { |
| bm = fopen(holemap, "r+b"); |
| if(!bm) { |
| fprintf(stderr,"Error: cannot open holemap file %s: %s\n", holemap, strerror(errno)); |
| free(compressed_bitmap); |
| exit(-1); |
| } |
| fseek(bm, 0, size); |
| fread(&free_bitmap->bmhdr, sizeof(free_bitmap->bmhdr), 1, bm); |
| // nread = fread(&free_bitmap->bmhdr, sizeof(free_bitmap->bmhdr), 1, bm); |
| } else { |
| bm = fopen(holemap, "w+b"); |
| if(!bm) { |
| fprintf(stderr,"Error: cannot create holemap file %s: %s\n", holemap, strerror(errno)); |
| free(compressed_bitmap); |
| exit(-1); |
| } |
| } |
| |
| if (dest_size != size) { |
| /* compressed length < source length |
| * i.e. compression was successful |
| */ |
| free_bitmap->bmhdr.compressed_size = dest_size; |
| free_bitmap->bmhdr.is_compressed = 1; |
| fseek(bm, 0, SEEK_SET); |
| bitmap_fwrite(&free_bitmap->bmhdr, sizeof(free_bitmap->bmhdr), 1, bm); |
| bitmap_fwrite(&free_bitmap->mqhdr, sizeof(free_bitmap->mqhdr), 1, bm); |
| fseek(bm, FC_BITMAP_BITMAP_OFFSET, SEEK_SET); |
| /* write compressed bitmap */ |
| bitmap_fwrite(compressed_bitmap, dest_size, 1, bm); |
| } else { |
| /* compressed length = source length: this can happen only |
| * in case of failure |
| */ |
| fseek(bm, 0, SEEK_SET); |
| bitmap_fwrite(&free_bitmap->bmhdr, sizeof(free_bitmap->bmhdr), 1, bm); |
| bitmap_fwrite(&free_bitmap->mqhdr, sizeof(free_bitmap->mqhdr), 1, bm); |
| fseek(bm, FC_BITMAP_BITMAP_OFFSET, SEEK_SET); |
| /* write uncompressed bitmap */ |
| bitmap_fwrite(free_bitmap->bits, size, 1, bm); |
| } |
| |
| free(compressed_bitmap); |
| if (fclose(bm)) { |
| fprintf(stderr, "Error: unable to close file %s : %s\n", holemap, strerror(errno)); |
| exit(-1); |
| } |
| } |
| |
| /* |
| * Read bitmap/holemap file from disk. |
| * holemap files will be decompressed before populating ram_bitmap_t |
| */ |
| ram_bitmap_t *bitmap_read(const char *bitmap) |
| { |
| size_t nread, compressed_size; |
| int ret; |
| unsigned char * compressed_bitmap = NULL; |
| fc_bitmap_mq_hdr_t mqhdr; |
| ram_bitmap_t *ram_bitmap = NULL; |
| FILE *bm = fopen(bitmap, "r"); |
| |
| if (!bm) |
| goto fail; |
| |
| /* get the size of the bitmap */ |
| fseek(bm, FC_BITMAP_MQ_HDR_OFFSET, SEEK_SET); |
| nread = fread(&mqhdr, sizeof(mqhdr), 1, bm); |
| if (nread != 1) |
| goto fail; |
| |
| /* create the bitmap */ |
| if ((ram_bitmap = bitmap_create(mqhdr.vdisk_size_lbas*LBAS_SIZE, |
| mqhdr.grain_size_lbas*LBAS_SIZE)) == NULL) |
| goto fail; |
| |
| /* |
| * now that the properly sized bitmap is created, read it in |
| * first, read the headers |
| * then, read the bits |
| */ |
| fseek(bm, 0, SEEK_SET); |
| nread = fread (&ram_bitmap->bmhdr, sizeof(ram_bitmap->bmhdr), 1, bm); |
| if (nread != 1) |
| goto fail; |
| |
| /* |
| * this is initialized by bitmap_create(), but still rewrite, |
| * just to make sure the header is exactly the same as on disk |
| */ |
| ram_bitmap->mqhdr = mqhdr; |
| /* read in the bitmap bits */ |
| fseek(bm, FC_BITMAP_BITMAP_OFFSET, SEEK_SET); |
| |
| /* check if bitmap needs to be decompressed before storing*/ |
| if (ram_bitmap->bmhdr.is_compressed) { |
| compressed_size = ram_bitmap->bmhdr.compressed_size; |
| compressed_bitmap = (unsigned char *) malloc(compressed_size); |
| nread = fread(compressed_bitmap, compressed_size, 1, bm); |
| if (nread != 1) |
| goto fail; |
| ret = gzip_decompress(compressed_bitmap, ram_bitmap->bits, compressed_size, |
| ram_bitmap->mqhdr.bitmap_size_bytes, COMPRESSION_LEVEL); |
| if (ret < 0) { |
| fprintf(stderr,"Error: holemap file decompression failed\n"); |
| goto fail; |
| } |
| free(compressed_bitmap); |
| } else { |
| nread = fread(ram_bitmap->bits, ram_bitmap->mqhdr.bitmap_size_bytes, 1, bm); |
| if (nread != 1) |
| goto fail; |
| } |
| fclose(bm); |
| |
| return ram_bitmap; |
| fail: |
| perror("Failed to read bitmap"); |
| if (bm) |
| fclose(bm); |
| if (ram_bitmap) |
| free(ram_bitmap); |
| if (compressed_bitmap) |
| free(compressed_bitmap); |
| return (NULL); |
| } |
| |
| |
| /* |
| * Produce a result bitmap which is a logical OR of the |
| * left- and righ-hand-side bitmap arguments |
| * the lhs and rhs arguments can be of different sizes, |
| * but the result has to be of the largest size |
| */ |
| int bitmap_add(ram_bitmap_t *result, ram_bitmap_t *lhs, ram_bitmap_t *rhs) |
| { |
| fc_bitmap_mq_hdr_t *hdr_res = &(result->mqhdr), |
| *hdr_lhs = &(lhs->mqhdr), *hdr_rhs = &(rhs->mqhdr); |
| unsigned char *bits_res = &(result->bits[0]), *bits_lhs = &(lhs->bits[0]), |
| *bits_rhs = &(rhs->bits[0]), *bits_remainder = NULL; |
| uint64_t i, min_size, max_size; |
| |
| /* compare grains and sizes */ |
| if (hdr_lhs->grain_size_lbas != hdr_rhs->grain_size_lbas || |
| hdr_lhs->grain_size_lbas != hdr_res->grain_size_lbas) { |
| fprintf(stderr, "different bitmap grain size detected," |
| " cannot add bitmaps\n"); |
| return (-1); |
| } |
| |
| if (hdr_lhs->bitmap_size_bytes > hdr_rhs->bitmap_size_bytes) { |
| min_size = hdr_rhs->bitmap_size_bytes; |
| max_size = hdr_lhs->bitmap_size_bytes; |
| bits_remainder = bits_lhs; |
| } else { |
| min_size = hdr_lhs->bitmap_size_bytes; |
| max_size = hdr_rhs->bitmap_size_bytes; |
| bits_remainder = bits_rhs; |
| } |
| |
| if (max_size != hdr_res->bitmap_size_bytes) { |
| fprintf(stderr, "resulting bitmap is of wrong byte size," |
| " cannot add bitmaps\n"); |
| return (-1); |
| } |
| |
| /* OR the common parts of the bitmaps */ |
| for (i = 0; i < min_size; i++) |
| bits_res[i] = bits_lhs[i] | bits_rhs[i]; |
| |
| /* fill in the rest using the larger bitmap */ |
| for ( ; i < max_size; i++) |
| bits_res[i] = bits_remainder[i]; |
| |
| return (0); |
| } |
| |
| /* |
| * Produce a result bitmap which is a logical AND of the |
| * left-hand-side bitmap and the inverse of the right-hand-size bitmap |
| * We will require that the rhs bitmap is not larger than the lhs bitmap, |
| * and the lhs bitmap is not larger than the lhs bitmap |
| */ |
| int bitmap_subtract(ram_bitmap_t *result, ram_bitmap_t *lhs, ram_bitmap_t *rhs) |
| { |
| fc_bitmap_mq_hdr_t *hdr_res = &(result->mqhdr), |
| *hdr_lhs = &(lhs->mqhdr), *hdr_rhs = &(rhs->mqhdr); |
| unsigned char *bits_res = &(result->bits[0]), *bits_lhs = &(lhs->bits[0]), |
| *bits_rhs = &(rhs->bits[0]); |
| uint64_t i; |
| |
| /* compare grains and byte sizes */ |
| if (hdr_lhs->grain_size_lbas != hdr_rhs->grain_size_lbas || |
| hdr_lhs->grain_size_lbas != hdr_res->grain_size_lbas) { |
| fprintf(stderr, "different bitmap grain sizes detected," |
| " cannot subtract bitmaps\n"); |
| return (-1); |
| } |
| |
| if (hdr_lhs->bitmap_size_bytes < hdr_rhs->bitmap_size_bytes || |
| hdr_res->bitmap_size_bytes < hdr_lhs->bitmap_size_bytes) { |
| fprintf(stderr, "bitmap sizes are incompatible," |
| " cannot subtract bitmaps\n"); |
| return (-1); |
| } |
| |
| /* subtract up to the rhs size */ |
| for (i = 0; i < hdr_rhs->bitmap_size_bytes; i++) |
| bits_res[i] = bits_lhs[i] & (~bits_rhs[i]); |
| |
| /* copy up to the lhs size */ |
| for ( ; i < hdr_lhs->bitmap_size_bytes; i++) |
| bits_res[i] = bits_lhs[i]; |
| |
| return (0); |
| } |
| |
| |
| |
| /* assumes the string of length at least 9 is managed by the caller */ |
| char *bitmap_show_bits(char *string, const char bits) |
| { |
| /* print out bits 0-7 left to right */ |
| char *ptr; |
| int i; |
| for (i = 0, ptr = string; i < 8; i++, ptr++) { |
| sprintf(ptr, "%d", (bits & (1 << i)) >> i); |
| } |
| string[8] = '\0'; |
| return string; |
| } |
| |
| |
| void bitmap_show(ram_bitmap_t *bitmap, uint64_t offset) |
| { |
| uint64_t i, j, ngrains; |
| |
| if ((bitmap->mqhdr.bitmap_mq_magic[0] != ((FC_BITMAP_MQ_MAGIC >> 24) & 0xFF)) || |
| (bitmap->mqhdr.bitmap_mq_magic[1] != ((FC_BITMAP_MQ_MAGIC >> 16) & 0xFF)) || |
| (bitmap->mqhdr.bitmap_mq_magic[2] != ((FC_BITMAP_MQ_MAGIC >> 8) & 0xFF)) || |
| (bitmap->mqhdr.bitmap_mq_magic[3] != (FC_BITMAP_MQ_MAGIC & 0xFF))) { |
| fprintf(stderr, "Invalid magic number in the bitmap mq header\n"); |
| exit(-1); |
| } |
| |
| fprintf(stdout, "Bitmap header:\n"); |
| fprintf(stdout, "\tbitmap size: 0x%"PRIx64" grains\n", bitmap->mqhdr.bitmap_size_bytes*8); |
| fprintf(stdout, "\tvdisk size: 0x%"PRIx64"\n", bitmap->mqhdr.vdisk_size_lbas*LBAS_SIZE); |
| fprintf(stdout, "\tgrain size: 0x%"PRIx32"\n", bitmap->mqhdr.grain_size_lbas*LBAS_SIZE); |
| |
| if (offset != ~0ULL) { |
| /* just find the grain and tell if it is set */ |
| uint64_t grain = offset / (bitmap->mqhdr.grain_size_lbas*LBAS_SIZE); |
| fprintf(stdout, |
| "bitmap offset 0x%"PRIx64" belongs to grain 0x%"PRIx64" that is %s\n", |
| offset, grain, (bitmap->bits[grain/8] & (1 << (grain%8))) ? "set" : "cleared"); |
| return; |
| } |
| |
| ngrains = bitmap->mqhdr.bitmap_size_bytes * 8; |
| |
| fprintf(stdout, "Bitmap bitset:"); |
| for (i = 0; i < bitmap->mqhdr.bitmap_size_bytes; i++) { |
| char bit_string[9]; |
| if ((i % 8) == 0) |
| fprintf(stdout, "\n\t"); |
| fprintf(stdout, "%s ", bitmap_show_bits(bit_string, bitmap->bits[i])); |
| } |
| fprintf(stdout, "\n"); |
| |
| fprintf(stdout, "Bitmap range list:\n"); |
| for (i = 0; i < ngrains; i = j) { |
| uint64_t start, end; |
| int iset = (bitmap->bits[i/8] & (1 << (i%8))) >> (i%8); |
| /* find next cleared/set range */ |
| for (j = i; (j < ngrains); j++) { |
| int jset = (bitmap->bits[j/8] & (1 << (j%8))) >> (j%8); |
| if (jset != iset) |
| break; |
| } |
| start = bitmap->mqhdr.grain_size_lbas*LBAS_SIZE*i; |
| end = bitmap->mqhdr.grain_size_lbas*LBAS_SIZE*j; |
| fprintf(stdout, "\tbitmap range: [0x%"PRIx64",0x%"PRIx64") is %s (0x%"PRIx64" grain%s)\n", |
| start, end, (iset) ? "set" : "cleared", j - i, ((j - i) > 1) ? "s" : ""); |
| } |
| |
| return; |
| } |
| |
| |
| /* |
| * return 0 if bitmap1 is a subset of bitmap2 (or equal to it), |
| * and return -1 otherwise |
| */ |
| int bitmap_compare(ram_bitmap_t *bm1, ram_bitmap_t *bm2) |
| { |
| fc_bitmap_mq_hdr_t *hdr1 = &(bm1->mqhdr), *hdr2 = &(bm2->mqhdr); |
| unsigned char *bitmap1 = &(bm1->bits[0]), *bitmap2 = &(bm2->bits[0]); |
| uint64_t i, missing_bits = 0, extra_bits = 0; |
| |
| /* compare headers */ |
| if (hdr1->grain_size_lbas != hdr2->grain_size_lbas) { |
| fprintf(stderr, "different bitmap grain size (%d vs %d), " |
| "cannot compare bitmaps\n", |
| hdr1->grain_size_lbas, hdr2->grain_size_lbas); |
| return (-1); |
| } |
| if (hdr1->bitmap_size_bytes > hdr2->bitmap_size_bytes) { |
| uint64_t diff_first_byte = |
| hdr2->bitmap_size_bytes*8*hdr2->grain_size_lbas*LBAS_SIZE, |
| diff_last_byte = |
| hdr1->bitmap_size_bytes*8*hdr1->grain_size_lbas*LBAS_SIZE; |
| fprintf(stderr, "unexpected differences found in byte range " |
| "[0x%"PRIx64",0x%"PRIx64") (all data different) \n", |
| diff_first_byte, diff_last_byte); |
| return (-1); |
| } |
| |
| for (i = 0; i < hdr1->bitmap_size_bytes; i++) { |
| char bm_byte[2][9]; |
| uint8_t mask = (uint8_t)(bitmap1[i] & ~bitmap2[i]); |
| uint64_t diff_first_byte = |
| i*8*hdr1->grain_size_lbas*LBAS_SIZE, |
| diff_last_byte = |
| diff_first_byte + 8*hdr1->grain_size_lbas*LBAS_SIZE; |
| uint32_t grain_bytes = hdr1->grain_size_lbas*LBAS_SIZE; |
| |
| /* |
| * are there some bits in bitmap1[i] that are not |
| * present in bitmap2[i] ? |
| */ |
| mask = (uint8_t)(bitmap1[i] & ~bitmap2[i]); |
| if (mask) { |
| if (verbosity) { |
| fprintf(stderr, "missing bits found in byte range " |
| "[0x%"PRIx64",0x%"PRIx64"), grain size 0x%x bytes, " |
| "range diffs (gain units) %s vs %s\n", |
| diff_first_byte, diff_last_byte, grain_bytes, |
| bitmap_show_bits(bm_byte[0], bitmap1[i]), |
| bitmap_show_bits(bm_byte[1], bitmap2[i])); |
| } |
| missing_bits = 1; |
| } |
| /* |
| * are there some bits in bitmap2[i] that are not |
| * present in bitmap1[i] (extra bits)? |
| */ |
| mask = (uint8_t)(bitmap2[i] & ~bitmap1[i]); |
| if (mask) { |
| if (verbosity) { |
| fprintf(stderr, "extra bits found in byte range " |
| "[0x%"PRIx64",0x%"PRIx64"), grain size 0x%x bytes, " |
| "range diffs (grain units) %s vs %s\n", |
| diff_first_byte, diff_last_byte, grain_bytes, |
| bitmap_show_bits(bm_byte[0], bitmap1[i]), |
| bitmap_show_bits(bm_byte[1], bitmap2[i])); |
| } |
| extra_bits = 1; |
| } |
| } |
| |
| if (missing_bits) { |
| fprintf(stderr, "bitmap is missing some bits\n"); |
| return (-1); |
| } |
| |
| if (extra_bits) |
| fprintf(stderr, "bitmap has some extra bits\n"); |
| |
| /* bitmap1 is a subset of (or equal to) bitmap2 */ |
| return (0); |
| } |
| |
| uint64_t bitmap_get_bitcount(ram_bitmap_t *bm) |
| { |
| const uint64_t bitmap_size_bytes = bm->mqhdr.bitmap_size_bytes; |
| const unsigned char *bitmap = &(bm->bits[0]); |
| uint64_t i, j, bitcount; |
| |
| /* walk the bitmap and count the bits */ |
| for (bitcount = 0, i = 0; i < bitmap_size_bytes; i++) { |
| if (bitmap[i] == 0) |
| continue; |
| for (j = 0; j < 8; j++) { |
| if (bitmap[i] & (1 << j)) |
| bitcount++; |
| } |
| } |
| |
| return (bitcount); |
| } |
| |
| int bitmap_get_bit(ram_bitmap_t *bm, uint64_t byte_offset) |
| { |
| const unsigned char *bitmap = &(bm->bits[0]); |
| uint64_t grainsize = bm->mqhdr.grain_size_lbas * LBAS_SIZE; |
| uint64_t abs_bit = byte_offset / grainsize; |
| uint64_t byte = abs_bit / 8, bit = abs_bit % 8; |
| |
| if (byte >= bm->mqhdr.bitmap_size_bytes) |
| return -1; |
| |
| return ((bitmap[byte] & (1 << bit)) >> bit); |
| } |
