1/* 2 * ntfs_bitmap.c - NTFS kernel bitmap handling. 3 * 4 * Copyright (c) 2006-2008 Anton Altaparmakov. All Rights Reserved. 5 * Portions Copyright (c) 2006-2008 Apple Inc. All Rights Reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright notice, 11 * this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright notice, 13 * this list of conditions and the following disclaimer in the documentation 14 * and/or other materials provided with the distribution. 15 * 3. Neither the name of Apple Inc. ("Apple") nor the names of its 16 * contributors may be used to endorse or promote products derived from this 17 * software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 23 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 26 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * ALTERNATIVELY, provided that this notice and licensing terms are retained in 31 * full, this file may be redistributed and/or modified under the terms of the 32 * GNU General Public License (GPL) Version 2, in which case the provisions of 33 * that version of the GPL will apply to you instead of the license terms 34 * above. You can obtain a copy of the GPL Version 2 at 35 * http://developer.apple.com/opensource/licenses/gpl-2.txt. 36 */ 37 38#include <sys/errno.h> 39 40#include <string.h> 41 42#include <kern/debug.h> 43 44#include "ntfs_bitmap.h" 45#include "ntfs_debug.h" 46#include "ntfs_inode.h" 47#include "ntfs_page.h" 48#include "ntfs_types.h" 49#include "ntfs_volume.h" 50 51/** 52 * __ntfs_bitmap_set_bits_in_run - set a run of bits in a bitmap to a value 53 * @ni: ntfs inode describing the bitmap 54 * @start_bit: first bit to set 55 * @count: number of bits to set 56 * @value: value to set the bits to (i.e. 0 or 1) 57 * @is_rollback: if true this is a rollback operation 58 * 59 * Set @count bits starting at bit @start_bit in the bitmap described by the 60 * ntfs inode @ni to @value, where @value is either 0 or 1. 61 * 62 * @is_rollback should always be false, it is for internal use to rollback 63 * errors. You probably want to use ntfs_bitmap_set_bits_in_run() instead. 64 * 65 * Return 0 on success and errno on error. 66 * 67 * Locking: The caller must hold @ni->lock. 68 */ 69errno_t __ntfs_bitmap_set_bits_in_run(ntfs_inode *ni, const s64 start_bit, 70 const s64 count, const u8 value, const BOOL is_rollback) 71{ 72 s64 rem, cnt = count; 73 u64 ofs, end_ofs; 74 upl_t upl; 75 upl_page_info_array_t pl; 76 u8 *kaddr; 77 unsigned pos, len; 78 errno_t err, err2; 79 u8 bit; 80 81 if (!ni) 82 panic("%s(): !ni\n", __FUNCTION__); 83 ntfs_debug("Entering for mft_no 0x%llx, start_bit 0x%llx, count " 84 "0x%llx, value %u.%s", (unsigned long long)ni->mft_no, 85 (unsigned long long)start_bit, (unsigned long long)cnt, 86 (unsigned)value, is_rollback ? " (rollback)" : ""); 87 if (start_bit < 0) 88 panic("%s(): start_bit < 0\n", __FUNCTION__); 89 if (cnt < 0) 90 panic("%s(): cnt < 0\n", __FUNCTION__); 91 if (value > 1) 92 panic("%s(): value > 1\n", __FUNCTION__); 93 /* 94 * Calculate the offsets for the pages containing the first and last 95 * bits, i.e. @start_bit and @start_bit + @cnt - 1, respectively. 96 */ 97 ofs = (start_bit >> 3) & ~PAGE_MASK_64; 98 end_ofs = ((start_bit + cnt - 1) >> 3) & ~PAGE_MASK_64; 99 /* Get the page containing the first bit (@start_bit). */ 100 err = ntfs_page_map(ni, ofs, &upl, &pl, &kaddr, TRUE); 101 if (err) { 102 if (!is_rollback) 103 ntfs_error(ni->vol->mp, "Failed to map first page " 104 "(error %d), aborting.", err); 105 return err; 106 } 107 /* Set @pos to the position of the byte containing @start_bit. */ 108 pos = (start_bit >> 3) & PAGE_MASK; 109 /* Calculate the position of @start_bit in the first byte. */ 110 bit = start_bit & 7; 111 /* If the first byte is partial, modify the appropriate bits in it. */ 112 if (bit) { 113 u8 *byte = kaddr + pos; 114 while ((bit & 7) && cnt) { 115 cnt--; 116 if (value) 117 *byte |= 1 << bit++; 118 else 119 *byte &= ~(1 << bit++); 120 } 121 /* If we are done, unmap the page and return success. */ 122 if (!cnt) 123 goto done; 124 /* Update @pos to the new position. */ 125 pos++; 126 } 127 /* 128 * Depending on @value, modify all remaining whole bytes in the page up 129 * to @cnt. 130 */ 131 len = PAGE_SIZE - pos; 132 rem = cnt >> 3; 133 if (len > rem) 134 len = rem; 135 memset(kaddr + pos, value ? 0xff : 0, len); 136 cnt -= len << 3; 137 /* Update @len to point to the first not-done byte in the page. */ 138 if (cnt < 8) 139 len += pos; 140 /* If we are not in the last page, deal with all subsequent pages. */ 141 while (ofs < end_ofs) { 142 if (cnt <= 0) 143 panic("%s(): cnt <= 0\n", __FUNCTION__); 144 /* Mark the current page dirty and unmap it. */ 145 ntfs_page_unmap(ni, upl, pl, TRUE); 146 /* Update @ofs and get the next page. */ 147 ofs += PAGE_SIZE; 148 err = ntfs_page_map(ni, ofs, &upl, &pl, &kaddr, TRUE); 149 if (err) 150 goto rollback; 151 /* 152 * Depending on @value, modify all remaining whole bytes in the 153 * page up to @cnt. 154 */ 155 len = PAGE_SIZE; 156 rem = cnt >> 3; 157 if (len > rem) 158 len = rem; 159 memset(kaddr, value ? 0xff : 0, len); 160 cnt -= len << 3; 161 } 162 /* 163 * The currently mapped page is the last one. If the last byte is 164 * partial, modify the appropriate bits in it. Note, @len is the 165 * position of the last byte inside the page. 166 */ 167 if (cnt) { 168 u8 *byte; 169 170 if (cnt > 7) 171 panic("%s(): cnt > 7\n", __FUNCTION__); 172 bit = cnt; 173 byte = kaddr + len; 174 while (bit--) { 175 if (value) 176 *byte |= 1 << bit; 177 else 178 *byte &= ~(1 << bit); 179 } 180 } 181done: 182 /* We are done. Unmap the page and return success. */ 183 ntfs_page_unmap(ni, upl, pl, TRUE); 184 ntfs_debug("Done."); 185 return 0; 186rollback: 187 /* 188 * Current state: 189 * - no pages are mapped 190 * - @count - @cnt is the number of bits that have been modified 191 */ 192 if (is_rollback) 193 return err; 194 err2 = 0; 195 if (count != cnt) 196 err2 = __ntfs_bitmap_set_bits_in_run(ni, start_bit, 197 count - cnt, value ? 0 : 1, TRUE); 198 if (!err2) { 199 /* Rollback was successful. */ 200 ntfs_error(ni->vol->mp, "Failed to map subsequent page (error " 201 "%d), aborting.", err); 202 } else { 203 /* Rollback failed. */ 204 ntfs_error(ni->vol->mp, "Failed to map subsequent page (error " 205 "%d) and rollback failed (error %d). " 206 "Aborting and leaving inconsistent metadata. " 207 "Unmount and run chkdsk.", err, err2); 208 NVolSetErrors(ni->vol); 209 } 210 return err; 211} 212