X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/6601e61aa18bf4f09af135ff61fc7f4771d23b06..f427ee49d309d8fc33ebf3042c3a775f2f530ded:/bsd/dev/vn/shadow.c diff --git a/bsd/dev/vn/shadow.c b/bsd/dev/vn/shadow.c index cb5fbfd6d..717b9dee0 100644 --- a/bsd/dev/vn/shadow.c +++ b/bsd/dev/vn/shadow.c @@ -1,24 +1,29 @@ - /* - * Copyright (c) 2001 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2001-2006 Apple Computer, Inc. All rights reserved. + * + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ + * + * This file contains Original Code and/or Modifications of Original Code + * as defined in and that are subject to the Apple Public Source License + * Version 2.0 (the 'License'). You may not use this file except in + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. * - * @APPLE_LICENSE_HEADER_START@ - * - * The contents of this file constitute Original Code as defined in and - * are subject to the Apple Public Source License Version 1.1 (the - * "License"). You may not use this file except in compliance with the - * License. Please obtain a copy of the License at - * http://www.apple.com/publicsource and read it before using this file. - * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. + * + * The Original Code and all software distributed under the License are + * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the - * License for the specific language governing rights and limitations - * under the License. - * - * @APPLE_LICENSE_HEADER_END@ + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and + * limitations under the License. + * + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ /* @@ -34,7 +39,7 @@ * 2) a band map to map a "band" within the original file to a corresponding * "band" in the shadow file. Each band has the same size. * - * The band map is used to ensure that blocks that are contiguous in the + * The band map is used to ensure that blocks that are contiguous in the * original file will remain contiguous in the shadow file. * * For debugging purposes, this file can be compiled standalone using: @@ -44,7 +49,7 @@ /* * Modification History * - * December 21, 2001 Dieter Siegmund (dieter@apple.com) + * December 21, 2001 Dieter Siegmund (dieter@apple.com) * - initial revision */ #include @@ -56,55 +61,55 @@ #ifdef TEST_SHADOW #include #include -#define my_malloc(a) malloc(a) -#define my_free(a) free(a) +#define my_malloc(a) malloc(a) +#define my_free(a) free(a) #else /* !TEST_SHADOW */ #include -#define my_malloc(a) _MALLOC(a, M_TEMP, M_WAITOK) -#define my_free(a) FREE(a, M_TEMP) +#define my_malloc(a) _MALLOC(a, M_TEMP, M_WAITOK) +#define my_free(a) FREE(a, M_TEMP) #include #endif /* TEST_SHADOW */ #include "shadow.h" -#define ULONG_ALL_ONES ((u_long)(-1)) -#define USHORT_ALL_ONES ((u_short)(-1)) -#define UCHAR_ALL_ONES ((u_char)(-1)) +#define UINT32_ALL_ONES ((uint32_t)(-1)) +#define USHORT_ALL_ONES ((u_short)(-1)) +#define UCHAR_ALL_ONES ((u_char)(-1)) -#define my_trunc(value, divisor) ((value) / (divisor) * (divisor)) +#define my_trunc(value, divisor) ((value) / (divisor) * (divisor)) /* a band size of 128K can represent a file up to 8GB */ -#define BAND_SIZE_DEFAULT_POWER_2 17 -#define BAND_SIZE_DEFAULT (1 << BAND_SIZE_DEFAULT_POWER_2) +#define BAND_SIZE_DEFAULT_POWER_2 17 +#define BAND_SIZE_DEFAULT (1 << BAND_SIZE_DEFAULT_POWER_2) -typedef u_short band_number_t; -#define BAND_ZERO ((band_number_t)0) -#define BAND_MAX ((band_number_t)65535) +typedef u_short band_number_t; +#define BAND_ZERO ((band_number_t)0) +#define BAND_MAX ((band_number_t)65535) struct shadow_map { - u_long blocks_per_band;/* size in blocks */ - u_long block_size; - u_char * block_bitmap; /* 1 bit per block; 1=written */ - band_number_t * bands; /* band map array */ - u_long file_size_blocks; /* size of file in bands */ - u_long shadow_size_bands; /* size of shadow in bands */ - u_long next_band; /* next free band */ - u_long zeroth_band; /* special-case 0th band */ + uint32_t blocks_per_band;/* size in blocks */ + uint32_t block_size; + u_char * block_bitmap; /* 1 bit per block; 1=written */ + band_number_t * bands; /* band map array */ + uint32_t file_size_blocks; /* size of file in bands */ + uint32_t shadow_size_bands; /* size of shadow in bands */ + uint32_t next_band; /* next free band */ + uint32_t zeroth_band; /* special-case 0th band */ }; typedef struct { - u_long byte; - u_long bit; + uint64_t byte; + uint32_t bit; } bitmap_offset_t; static __inline__ u_char bit(int b) { - return ((u_char)(1 << b)); + return (u_char)(1 << b); } -/* +/* * Function: bits_lower * Purpose: * Return a byte value in which bits numbered lower than 'b' are set. @@ -112,7 +117,7 @@ bit(int b) static __inline__ u_char bits_lower(int b) { - return ((u_char)(bit(b) - 1)); + return (u_char)(bit(b) - 1); } /* @@ -123,20 +128,20 @@ bits_lower(int b) static __inline__ u_char byte_set_bits(int start, int end) { - return ((u_char)((~bits_lower(start)) & (bits_lower(end) | bit(end)))); + return (u_char)((~bits_lower(start)) & (bits_lower(end) | bit(end))); } static __inline__ bitmap_offset_t bitmap_offset(off_t where) { - bitmap_offset_t b; + bitmap_offset_t b; - b.byte = where / NBBY; - b.bit = where % NBBY; - return (b); + b.byte = where / NBBY; + b.bit = where % NBBY; + return b; } -/* +/* * Function: bitmap_set * * Purpose: @@ -146,49 +151,50 @@ bitmap_offset(off_t where) * units, using longs, then a short, then a byte, then bits. */ static void -bitmap_set(u_char * map, u_long start_bit, u_long bit_count) +bitmap_set(u_char * map, off_t start_bit, size_t bit_count) { - bitmap_offset_t start; - bitmap_offset_t end; - - start = bitmap_offset(start_bit); - end = bitmap_offset(start_bit + bit_count); - if (start.byte < end.byte) { - u_long n_bytes; - - if (start.bit) { - map[start.byte] |= byte_set_bits(start.bit, NBBY - 1); - start.bit = 0; - start.byte++; - if (start.byte == end.byte) - goto end; - } - - n_bytes = end.byte - start.byte; - - while (n_bytes >= (sizeof(u_long))) { - *((u_long *)(map + start.byte)) = ULONG_ALL_ONES; - start.byte += sizeof(u_long); - n_bytes -= sizeof(u_long); - } - if (n_bytes >= sizeof(u_short)) { - *((u_short *)(map + start.byte)) = USHORT_ALL_ONES; - start.byte += sizeof(u_short); - n_bytes -= sizeof(u_short); - } - if (n_bytes == 1) { - map[start.byte] = UCHAR_ALL_ONES; - start.byte++; - n_bytes = 0; + bitmap_offset_t start; + bitmap_offset_t end; + + start = bitmap_offset(start_bit); + end = bitmap_offset(start_bit + bit_count); + if (start.byte < end.byte) { + uint64_t n_bytes; + + if (start.bit) { + map[start.byte] |= byte_set_bits(start.bit, NBBY - 1); + start.bit = 0; + start.byte++; + if (start.byte == end.byte) { + goto end; + } + } + + n_bytes = end.byte - start.byte; + + while (n_bytes >= (sizeof(uint32_t))) { + *((uint32_t *)(map + start.byte)) = UINT32_ALL_ONES; + start.byte += sizeof(uint32_t); + n_bytes -= sizeof(uint32_t); + } + if (n_bytes >= sizeof(u_short)) { + *((u_short *)(map + start.byte)) = USHORT_ALL_ONES; + start.byte += sizeof(u_short); + n_bytes -= sizeof(u_short); + } + if (n_bytes == 1) { + map[start.byte] = UCHAR_ALL_ONES; + start.byte++; + n_bytes = 0; + } } - } - end: - if (end.bit > start.bit) { - map[start.byte] |= byte_set_bits(start.bit, end.bit - 1); - } +end: + if (end.bit > start.bit) { + map[start.byte] |= byte_set_bits(start.bit, end.bit - 1); + } - return; + return; } /* @@ -203,111 +209,111 @@ bitmap_set(u_char * map, u_long start_bit, u_long bit_count) * a byte, then any remaining bits to find the bit that is different. */ -static u_long -bitmap_get(u_char * map, u_long start_bit, u_long bit_count, - boolean_t * ret_is_set) +static uint32_t +bitmap_get(u_char * map, off_t start_bit, size_t bit_count, + boolean_t * ret_is_set) { - u_long count; - int i; - boolean_t is_set; - bitmap_offset_t start; - bitmap_offset_t end; - - start = bitmap_offset(start_bit); - end = bitmap_offset(start_bit + bit_count); - - is_set = (map[start.byte] & bit(start.bit)) ? TRUE : FALSE; - count = 0; - - if (start.byte < end.byte) { - u_long n_bytes; - - if (start.bit) { /* try to align to a byte */ - for (i = start.bit; i < NBBY; i++) { - boolean_t this_is_set; + uint32_t count; + int i; + boolean_t is_set; + bitmap_offset_t start; + bitmap_offset_t end; + + start = bitmap_offset(start_bit); + end = bitmap_offset(start_bit + bit_count); + + is_set = (map[start.byte] & bit(start.bit)) ? TRUE : FALSE; + count = 0; + + if (start.byte < end.byte) { + uint64_t n_bytes; + + if (start.bit) { /* try to align to a byte */ + for (i = start.bit; i < NBBY; i++) { + boolean_t this_is_set; + + this_is_set = (map[start.byte] & bit(i)) ? TRUE : FALSE; + if (this_is_set != is_set) { + goto done; /* found bit that was different, we're done */ + } + count++; + } + start.bit = 0; /* made it to the next byte */ + start.byte++; + if (start.byte == end.byte) { + goto end; /* no more bytes, check for any leftover bits */ + } + } + /* calculate how many bytes are left in the range */ + n_bytes = end.byte - start.byte; + + /* check for 4 bytes of the same bits */ + while (n_bytes >= sizeof(uint32_t)) { + uint32_t * valPtr = (uint32_t *)(map + start.byte); + if ((is_set && *valPtr == UINT32_ALL_ONES) + || (!is_set && *valPtr == 0)) { + count += sizeof(*valPtr) * NBBY; + start.byte += sizeof(*valPtr); + n_bytes -= sizeof(*valPtr); + } else { + break; /* bits differ */ + } + } + /* check for 2 bytes of the same bits */ + if (n_bytes >= sizeof(u_short)) { + u_short * valPtr = (u_short *)(map + start.byte); + + if ((is_set && *valPtr == USHORT_ALL_ONES) + || (!is_set && (*valPtr == 0))) { + count += sizeof(*valPtr) * NBBY; + start.byte += sizeof(*valPtr); + n_bytes -= sizeof(*valPtr); + } + } - this_is_set = (map[start.byte] & bit(i)) ? TRUE : FALSE; - if (this_is_set != is_set) { - goto done; /* found bit that was different, we're done */ + /* check for 1 byte of the same bits */ + if (n_bytes) { + if ((is_set && map[start.byte] == UCHAR_ALL_ONES) + || (!is_set && map[start.byte] == 0)) { + count += NBBY; + start.byte++; + n_bytes--; + } + /* we found bits that were different, find the first one */ + if (n_bytes) { + for (i = 0; i < NBBY; i++) { + boolean_t this_is_set; + + this_is_set = (map[start.byte] & bit(i)) ? TRUE : FALSE; + if (this_is_set != is_set) { + break; + } + count++; + } + goto done; + } } - count++; - } - start.bit = 0; /* made it to the next byte */ - start.byte++; - if (start.byte == end.byte) - goto end; /* no more bytes, check for any leftover bits */ } - /* calculate how many bytes are left in the range */ - n_bytes = end.byte - start.byte; - - /* check for 4 bytes of the same bits */ - while (n_bytes >= sizeof(u_long)) { - u_long * valPtr = (u_long *)(map + start.byte); - if ((is_set && *valPtr == ULONG_ALL_ONES) - || (!is_set && *valPtr == 0)) { - count += sizeof(*valPtr) * NBBY; - start.byte += sizeof(*valPtr); - n_bytes -= sizeof(*valPtr); - } - else - break; /* bits differ */ - } - /* check for 2 bytes of the same bits */ - if (n_bytes >= sizeof(u_short)) { - u_short * valPtr = (u_short *)(map + start.byte); - - if ((is_set && *valPtr == USHORT_ALL_ONES) - || (!is_set && (*valPtr == 0))) { - count += sizeof(*valPtr) * NBBY; - start.byte += sizeof(*valPtr); - n_bytes -= sizeof(*valPtr); - } - } +end: + for (i = start.bit; i < (int)end.bit; i++) { + boolean_t this_is_set = (map[start.byte] & bit(i)) ? TRUE : FALSE; - /* check for 1 byte of the same bits */ - if (n_bytes) { - if ((is_set && map[start.byte] == UCHAR_ALL_ONES) - || (!is_set && map[start.byte] == 0)) { - count += NBBY; - start.byte++; - n_bytes--; - } - /* we found bits that were different, find the first one */ - if (n_bytes) { - for (i = 0; i < NBBY; i++) { - boolean_t this_is_set; - - this_is_set = (map[start.byte] & bit(i)) ? TRUE : FALSE; - if (this_is_set != is_set) { + if (this_is_set != is_set) { break; - } - count++; } - goto done; - } - } - } - - end: - for (i = start.bit; i < (int)end.bit; i++) { - boolean_t this_is_set = (map[start.byte] & bit(i)) ? TRUE : FALSE; - - if (this_is_set != is_set) { - break; + count++; } - count++; - } - done: - *ret_is_set = is_set; - return (count); +done: + *ret_is_set = is_set; + return count; } static __inline__ band_number_t -shadow_map_block_to_band(shadow_map_t * map, unsigned long block) +shadow_map_block_to_band(shadow_map_t * map, off_t block) { - return (block / map->blocks_per_band); + return (band_number_t)(block / map->blocks_per_band); } /* @@ -319,90 +325,88 @@ shadow_map_block_to_band(shadow_map_t * map, unsigned long block) */ static boolean_t shadow_map_mapped_band(shadow_map_t * map, band_number_t band, - boolean_t map_it, band_number_t * mapped_band) + boolean_t map_it, band_number_t * mapped_band) { - boolean_t is_mapped = FALSE; - - if (band == map->zeroth_band) { - *mapped_band = BAND_ZERO; - is_mapped = TRUE; - } - else { - *mapped_band = map->bands[band]; - if (*mapped_band == BAND_ZERO) { - if (map_it) { - /* grow the file */ - if (map->next_band == 0) { - /* remember the zero'th band */ - map->zeroth_band = band; - } - *mapped_band = map->bands[band] = map->next_band++; + boolean_t is_mapped = FALSE; + + if (band == map->zeroth_band) { + *mapped_band = BAND_ZERO; is_mapped = TRUE; - } - } - else { - is_mapped = TRUE; + } else { + *mapped_band = map->bands[band]; + if (*mapped_band == BAND_ZERO) { + if (map_it) { + /* grow the file */ + if (map->next_band == 0) { + /* remember the zero'th band */ + map->zeroth_band = band; + } + *mapped_band = map->bands[band] = (band_number_t)map->next_band++; + is_mapped = TRUE; + } + } else { + is_mapped = TRUE; + } } - } - return (is_mapped); + return is_mapped; } -/* +/* * Function: shadow_map_contiguous * * Purpose: - * Return the first offset within the range position..(position + count) + * Return the first offset within the range position..(position + count) * that is not a contiguous mapped band. * * If called with is_write = TRUE, this function will map bands as it goes. */ -static u_long -shadow_map_contiguous(shadow_map_t * map, u_long start_block, - u_long num_blocks, boolean_t is_write) +static off_t +shadow_map_contiguous(shadow_map_t * map, off_t start_block, + size_t num_blocks, boolean_t is_write) { - band_number_t band = shadow_map_block_to_band(map, start_block); - u_long end_block = start_block + num_blocks; - boolean_t is_mapped; - band_number_t mapped_band; - u_long ret_end_block = end_block; - u_long p; - - is_mapped = shadow_map_mapped_band(map, band, is_write, &mapped_band); - if (is_write == FALSE && is_mapped == FALSE) { - static int happened = 0; - /* this can't happen */ - if (happened == 0) { - printf("shadow_map_contiguous: this can't happen!\n"); - happened = 1; - } - return (start_block); - } - for (p = my_trunc(start_block + map->blocks_per_band, - map->blocks_per_band); - p < end_block; p += map->blocks_per_band) { - band_number_t next_mapped_band; - - band++; - is_mapped = shadow_map_mapped_band(map, band, is_write, - &next_mapped_band); + band_number_t band = shadow_map_block_to_band(map, start_block); + off_t end_block = start_block + num_blocks; + boolean_t is_mapped; + band_number_t mapped_band; + off_t ret_end_block = end_block; + off_t p; + + is_mapped = shadow_map_mapped_band(map, band, is_write, &mapped_band); if (is_write == FALSE && is_mapped == FALSE) { - return (p); + static int happened = 0; + /* this can't happen */ + if (happened == 0) { + printf("shadow_map_contiguous: this can't happen!\n"); + happened = 1; + } + return start_block; } - if ((mapped_band + 1) != next_mapped_band) { - /* not contiguous */ - ret_end_block = p; - break; + for (p = my_trunc(start_block + map->blocks_per_band, + map->blocks_per_band); + p < end_block; p += map->blocks_per_band) { + band_number_t next_mapped_band; + + band++; + is_mapped = shadow_map_mapped_band(map, band, is_write, + &next_mapped_band); + if (is_write == FALSE && is_mapped == FALSE) { + return p; + } + if ((mapped_band + 1) != next_mapped_band) { + /* not contiguous */ + ret_end_block = p; + break; + } + mapped_band = next_mapped_band; } - mapped_band = next_mapped_band; - } - return (ret_end_block); + return ret_end_block; } -/* +/* * Function: block_bitmap_size * Purpose: - * The number of bytes required in a block bitmap to represent a file of size + * The number of bytes required in a block bitmap to represent a file of size * file_size. * * The bytes required is the number of blocks in the file, @@ -414,11 +418,11 @@ shadow_map_contiguous(shadow_map_t * map, u_long start_block, * particularly since most of the bits will be zero. * A sparse bitmap would really help in this case. */ -static __inline__ u_long -block_bitmap_size(off_t file_size, u_long block_size) +static __inline__ size_t +block_bitmap_size(off_t file_size, uint32_t block_size) { - off_t blocks = howmany(file_size, block_size); - return (howmany(blocks, NBBY)); + off_t blocks = howmany(file_size, block_size); + return howmany(blocks, NBBY); } /* @@ -432,10 +436,10 @@ block_bitmap_size(off_t file_size, u_long block_size) * The output values (*incr_block_offset, *incr_block_count) refer to the * shadow file if the return value is TRUE. They refer to the original * file if the return value is FALSE. - + * * Blocks within a band may or may not have been written, in addition, * Bands are not necessarily contiguous, therefore: - * *incr_block_count <= block_count + * *incr_block_count <= block_count * The caller must be prepared to call this function interatively * to complete the whole i/o. * Returns: @@ -443,39 +447,38 @@ block_bitmap_size(off_t file_size, u_long block_size) * should be read. */ boolean_t -shadow_map_read(shadow_map_t * map, u_long block_offset, u_long block_count, - u_long * incr_block_offset, u_long * incr_block_count) +shadow_map_read(shadow_map_t * map, off_t block_offset, size_t block_count, + off_t * incr_block_offset, size_t * incr_block_count) { - boolean_t written = FALSE; - u_long n_blocks; - - if (block_offset >= map->file_size_blocks - || (block_offset + block_count) > map->file_size_blocks) { - printf("shadow_map_read: request (%ld, %ld) exceeds file size %ld\n", - block_offset, block_count, map->file_size_blocks); - *incr_block_count = 0; - } - n_blocks = bitmap_get(map->block_bitmap, block_offset, block_count, - &written); - if (written == FALSE) { - *incr_block_count = n_blocks; - *incr_block_offset = block_offset; - } - else { /* start has been written, and therefore mapped */ - band_number_t mapped_band; - u_long band_limit; - - mapped_band = map->bands[shadow_map_block_to_band(map, block_offset)]; - *incr_block_offset = mapped_band * map->blocks_per_band - + (block_offset % map->blocks_per_band); - band_limit - = shadow_map_contiguous(map, block_offset, block_count, FALSE); - *incr_block_count = band_limit - block_offset; - if (*incr_block_count > n_blocks) { - *incr_block_count = n_blocks; + boolean_t written = FALSE; + uint32_t n_blocks; + + if (block_offset >= map->file_size_blocks + || (block_offset + block_count) > map->file_size_blocks) { + printf("shadow_map_read: request (%lld, %lu) exceeds file size %d\n", + block_offset, block_count, map->file_size_blocks); + *incr_block_count = 0; + } + n_blocks = bitmap_get(map->block_bitmap, block_offset, block_count, + &written); + if (written == FALSE) { + *incr_block_count = n_blocks; + *incr_block_offset = block_offset; + } else { /* start has been written, and therefore mapped */ + band_number_t mapped_band; + off_t band_limit; + + mapped_band = map->bands[shadow_map_block_to_band(map, block_offset)]; + *incr_block_offset = mapped_band * map->blocks_per_band + + (block_offset % map->blocks_per_band); + band_limit + = shadow_map_contiguous(map, block_offset, block_count, FALSE); + *incr_block_count = band_limit - block_offset; + if (*incr_block_count > n_blocks) { + *incr_block_count = n_blocks; + } } - } - return (written); + return written; } /* @@ -484,55 +487,55 @@ shadow_map_read(shadow_map_t * map, u_long block_offset, u_long block_count, * Purpose: * Calculate the block offset within the shadow to write, and the number * blocks to write. The input values (block_offset, block_count) refer - * to the original file. The output values + * to the original file. The output values * (*incr_block_offset, *incr_block_count) refer to the shadow file. * * Bands are not necessarily contiguous, therefore: - * *incr_block_count <= block_count + * *incr_block_count <= block_count * The caller must be prepared to call this function interatively * to complete the whole i/o. * Returns: - * TRUE if the shadow file was grown, FALSE otherwise. + * TRUE if the shadow file was grown, FALSE otherwise. */ boolean_t -shadow_map_write(shadow_map_t * map, u_long block_offset, - u_long block_count, u_long * incr_block_offset, - u_long * incr_block_count) +shadow_map_write(shadow_map_t * map, off_t block_offset, + size_t block_count, off_t * incr_block_offset, + size_t * incr_block_count) { - u_long band_limit; - band_number_t mapped_band; - boolean_t shadow_grew = FALSE; - - if (block_offset >= map->file_size_blocks - || (block_offset + block_count) > map->file_size_blocks) { - printf("shadow_map_write: request (%ld, %ld) exceeds file size %ld\n", - block_offset, block_count, map->file_size_blocks); - *incr_block_count = 0; - } - - band_limit = shadow_map_contiguous(map, block_offset, block_count, TRUE); - mapped_band = map->bands[shadow_map_block_to_band(map, block_offset)]; - *incr_block_offset = mapped_band * map->blocks_per_band - + (block_offset % map->blocks_per_band); - *incr_block_count = band_limit - block_offset; - - /* mark these blocks as written */ - bitmap_set(map->block_bitmap, block_offset, *incr_block_count); - - if (map->next_band > map->shadow_size_bands) { - map->shadow_size_bands = map->next_band; - shadow_grew = TRUE; - } - return (shadow_grew); + off_t band_limit; + band_number_t mapped_band; + boolean_t shadow_grew = FALSE; + + if (block_offset >= map->file_size_blocks + || (block_offset + block_count) > map->file_size_blocks) { + printf("shadow_map_write: request (%lld, %zu) exceeds file size %d\n", + block_offset, block_count, map->file_size_blocks); + *incr_block_count = 0; + } + + band_limit = shadow_map_contiguous(map, block_offset, block_count, TRUE); + mapped_band = map->bands[shadow_map_block_to_band(map, block_offset)]; + *incr_block_offset = mapped_band * map->blocks_per_band + + (block_offset % map->blocks_per_band); + *incr_block_count = band_limit - block_offset; + + /* mark these blocks as written */ + bitmap_set(map->block_bitmap, block_offset, *incr_block_count); + + if (map->next_band > map->shadow_size_bands) { + map->shadow_size_bands = map->next_band; + shadow_grew = TRUE; + } + return shadow_grew; } boolean_t -shadow_map_is_written(shadow_map_t * map, u_long block_offset) +shadow_map_is_written(shadow_map_t * map, off_t block_offset) { - bitmap_offset_t b; + bitmap_offset_t b; - b = bitmap_offset(block_offset); - return ((map->block_bitmap[b.byte] & bit(b.bit)) ? TRUE : FALSE); + b = bitmap_offset(block_offset); + return (map->block_bitmap[b.byte] & bit(b.bit)) ? TRUE : FALSE; } /* @@ -541,13 +544,13 @@ shadow_map_is_written(shadow_map_t * map, u_long block_offset) * Purpose: * To return the size of the shadow file in blocks. */ -u_long +uint32_t shadow_map_shadow_size(shadow_map_t * map) { - return (map->shadow_size_bands * map->blocks_per_band); + return map->shadow_size_bands * map->blocks_per_band; } -/* +/* * Function: shadow_map_create * * Purpose: @@ -557,64 +560,67 @@ shadow_map_shadow_size(shadow_map_t * map) * NULL if an error occurred. */ shadow_map_t * -shadow_map_create(off_t file_size, off_t shadow_size, - u_long band_size, u_long block_size) +shadow_map_create(off_t file_size, off_t shadow_size, + uint32_t band_size, uint32_t block_size) { - void * block_bitmap = 0; - u_long bitmap_size; - band_number_t * bands = 0; - shadow_map_t * map; - u_long n_bands = 0; - - if (band_size == 0) { - band_size = BAND_SIZE_DEFAULT; - } - - n_bands = howmany(file_size, band_size); - if (n_bands > (BAND_MAX + 1)) { - printf("file is too big: %ld > %d\n", - n_bands, BAND_MAX); - goto failure; - } - - /* create a block bitmap, one bit per block */ - bitmap_size = block_bitmap_size(file_size, block_size); - block_bitmap = my_malloc(bitmap_size); - if (block_bitmap == NULL) { - printf("failed to allocate bitmap\n"); - goto failure; - } - bzero(block_bitmap, bitmap_size); - - /* get the band map */ - bands = (band_number_t *)my_malloc(n_bands * sizeof(band_number_t)); - if (bands == NULL) { - printf("failed to allocate bands\n"); - goto failure; - } - bzero(bands, n_bands * sizeof(band_number_t)); - - map = my_malloc(sizeof(*map)); - if (map == NULL) { - printf("failed to allocate map\n"); - goto failure; - } - map->blocks_per_band = band_size / block_size; - map->block_bitmap = block_bitmap; - map->bands = bands; - map->file_size_blocks = n_bands * map->blocks_per_band; - map->next_band = 0; - map->zeroth_band = -1; - map->shadow_size_bands = howmany(shadow_size, band_size); - map->block_size = block_size; - return (map); - - failure: - if (block_bitmap) - my_free(block_bitmap); - if (bands) - my_free(bands); - return (NULL); + void * block_bitmap = NULL; + size_t bitmap_size; + band_number_t * bands = NULL; + shadow_map_t * map; + uint32_t n_bands = 0; + + if (band_size == 0) { + band_size = BAND_SIZE_DEFAULT; + } + + off_t many = howmany(file_size, band_size); + if (many > (BAND_MAX + 1)) { + printf("file is too big: %lld > %d\n", + many, BAND_MAX); + goto failure; + } + n_bands = (uint32_t)many; + + /* create a block bitmap, one bit per block */ + bitmap_size = block_bitmap_size(file_size, block_size); + block_bitmap = my_malloc(bitmap_size); + if (block_bitmap == NULL) { + printf("failed to allocate bitmap\n"); + goto failure; + } + bzero(block_bitmap, bitmap_size); + + /* get the band map */ + bands = (band_number_t *)my_malloc(n_bands * sizeof(band_number_t)); + if (bands == NULL) { + printf("failed to allocate bands\n"); + goto failure; + } + bzero(bands, n_bands * sizeof(band_number_t)); + + map = my_malloc(sizeof(*map)); + if (map == NULL) { + printf("failed to allocate map\n"); + goto failure; + } + map->blocks_per_band = band_size / block_size; + map->block_bitmap = block_bitmap; + map->bands = bands; + map->file_size_blocks = n_bands * map->blocks_per_band; + map->next_band = 0; + map->zeroth_band = -1; + map->shadow_size_bands = (uint32_t)howmany(shadow_size, band_size); + map->block_size = block_size; + return map; + +failure: + if (block_bitmap) { + my_free(block_bitmap); + } + if (bands) { + my_free(bands); + } + return NULL; } /* @@ -624,113 +630,115 @@ shadow_map_create(off_t file_size, off_t shadow_size, */ void shadow_map_free(shadow_map_t * map) -{ - if (map->block_bitmap) - my_free(map->block_bitmap); - if (map->bands) - my_free(map->bands); - map->block_bitmap = 0; - map->bands = 0; - my_free(map); - return; +{ + if (map->block_bitmap) { + my_free(map->block_bitmap); + } + if (map->bands) { + my_free(map->bands); + } + map->block_bitmap = NULL; + map->bands = NULL; + my_free(map); + return; } #ifdef TEST_SHADOW -#define BAND_SIZE_BLOCKS (BAND_SIZE_DEFAULT / 512) +#define BAND_SIZE_BLOCKS (BAND_SIZE_DEFAULT / 512) enum { - ReadRequest, - WriteRequest, + ReadRequest, + WriteRequest, }; typedef struct { - int type; - u_long offset; - u_long count; + int type; + uint32_t offset; + uint32_t count; } block_request_t; int main() { - shadow_map_t * map; - int i; - block_request_t requests[] = { - { WriteRequest, BAND_SIZE_BLOCKS * 2, 1 }, - { ReadRequest, BAND_SIZE_BLOCKS / 2, BAND_SIZE_BLOCKS * 2 - 2 }, - { WriteRequest, BAND_SIZE_BLOCKS * 1, 5 * BAND_SIZE_BLOCKS + 3}, - { ReadRequest, 0, BAND_SIZE_BLOCKS * 10 }, - { WriteRequest, BAND_SIZE_BLOCKS * (BAND_MAX - 1), - BAND_SIZE_BLOCKS * 2}, - { 0, 0 }, - }; - - map = shadow_map_create(1024 * 1024 * 1024 * 8ULL, 0, 0, 512); - if (map == NULL) { - printf("shadow_map_create failed\n"); - exit(1); - } - for (i = 0; TRUE; i++) { - u_long offset; - u_long resid; - boolean_t shadow_grew; - boolean_t read_shadow; - - if (requests[i].count == 0) { - break; + shadow_map_t * map; + int i; + block_request_t requests[] = { + { WriteRequest, BAND_SIZE_BLOCKS * 2, 1 }, + { ReadRequest, BAND_SIZE_BLOCKS / 2, BAND_SIZE_BLOCKS * 2 - 2 }, + { WriteRequest, BAND_SIZE_BLOCKS * 1, 5 * BAND_SIZE_BLOCKS + 3}, + { ReadRequest, 0, BAND_SIZE_BLOCKS * 10 }, + { WriteRequest, BAND_SIZE_BLOCKS * (BAND_MAX - 1), + BAND_SIZE_BLOCKS * 2}, + { 0, 0 }, + }; + + map = shadow_map_create(1024 * 1024 * 1024 * 8ULL, 0, 0, 512); + if (map == NULL) { + printf("shadow_map_create failed\n"); + exit(1); } - offset = requests[i].offset; - resid = requests[i].count; - printf("\n%s REQUEST (%ld, %ld)\n", - requests[i].type == WriteRequest ? "WRITE" : "READ", - offset, resid); - switch (requests[i].type) { - case WriteRequest: - while (resid > 0) { - u_long this_offset; - u_long this_count; - - shadow_grew = shadow_map_write(map, offset, - resid, - &this_offset, - &this_count); - printf("\t(%ld, %ld) => (%ld, %ld)", - offset, resid, this_offset, this_count); - resid -= this_count; - offset += this_count; - if (shadow_grew) { - printf(" shadow grew to %ld", shadow_map_shadow_size(map)); + for (i = 0; TRUE; i++) { + uint32_t offset; + uint32_t resid; + boolean_t shadow_grew; + boolean_t read_shadow; + + if (requests[i].count == 0) { + break; } - printf("\n"); - } - break; - case ReadRequest: - while (resid > 0) { - u_long this_offset; - u_long this_count; - - read_shadow = shadow_map_read(map, offset, - resid, - &this_offset, - &this_count); - printf("\t(%ld, %ld) => (%ld, %ld)%s\n", - offset, resid, this_offset, this_count, - read_shadow ? " from shadow" : ""); - if (this_count == 0) { - printf("this_count is 0, aborting\n"); - break; + offset = requests[i].offset; + resid = requests[i].count; + printf("\n%s REQUEST (%ld, %ld)\n", + requests[i].type == WriteRequest ? "WRITE" : "READ", + offset, resid); + switch (requests[i].type) { + case WriteRequest: + while (resid > 0) { + uint32_t this_offset; + uint32_t this_count; + + shadow_grew = shadow_map_write(map, offset, + resid, + &this_offset, + &this_count); + printf("\t(%ld, %ld) => (%ld, %ld)", + offset, resid, this_offset, this_count); + resid -= this_count; + offset += this_count; + if (shadow_grew) { + printf(" shadow grew to %ld", shadow_map_shadow_size(map)); + } + printf("\n"); + } + break; + case ReadRequest: + while (resid > 0) { + uint32_t this_offset; + uint32_t this_count; + + read_shadow = shadow_map_read(map, offset, + resid, + &this_offset, + &this_count); + printf("\t(%ld, %ld) => (%ld, %ld)%s\n", + offset, resid, this_offset, this_count, + read_shadow ? " from shadow" : ""); + if (this_count == 0) { + printf("this_count is 0, aborting\n"); + break; + } + resid -= this_count; + offset += this_count; + } + break; + default: + break; } - resid -= this_count; - offset += this_count; - } - break; - default: - break; } - } - if (map) { - shadow_map_free(map); - } - exit(0); - return (0); + if (map) { + shadow_map_free(map); + } + exit(0); + return 0; } #endif