1/* 2 * ntfs_hash.c - NTFS kernel inode hash operations. 3 * 4 * Copyright (c) 2006-2011 Anton Altaparmakov. All Rights Reserved. 5 * Portions Copyright (c) 2006-2011 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/cdefs.h> 39 40#include <sys/errno.h> 41#include <sys/kernel_types.h> 42#include <sys/malloc.h> 43#include <sys/mount.h> 44#include <sys/queue.h> 45#include <sys/systm.h> 46#include <sys/ucred.h> 47#include <sys/vnode.h> 48 49#include <libkern/OSAtomic.h> 50#include <libkern/OSMalloc.h> 51 52#include <kern/locks.h> 53 54#include "ntfs.h" 55#include "ntfs_debug.h" 56#include "ntfs_hash.h" 57#include "ntfs_inode.h" 58#include "ntfs_layout.h" 59#include "ntfs_types.h" 60#include "ntfs_inode.h" 61#include "ntfs_volume.h" 62 63/* Structures associated with ntfs inode caching. */ 64static ntfs_inode_list_head *ntfs_inode_hash_table; 65static unsigned long ntfs_inode_hash_mask; 66 67/* A sleeping lock to protect concurrent accesses to the ntfs inode hash. */ 68lck_mtx_t ntfs_inode_hash_lock; 69 70/** 71 * ntfs_inode_hash_init - initialize the ntfs inode hash 72 * 73 * Initialize the ntfs inode hash. 74 */ 75errno_t ntfs_inode_hash_init(void) 76{ 77 /* Create the ntfs inode hash. */ 78 ntfs_inode_hash_table = hashinit(desiredvnodes, M_TEMP, 79 &ntfs_inode_hash_mask); 80 if (!ntfs_inode_hash_table) { 81 ntfs_error(NULL, "Failed to allocate ntfs inode hash table."); 82 return ENOMEM; 83 } 84 ntfs_debug("ntfs_inode_hash_mask 0x%lx.", ntfs_inode_hash_mask); 85 /* Initialize the ntfs inode hash lock. */ 86 lck_mtx_init(&ntfs_inode_hash_lock, ntfs_lock_grp, ntfs_lock_attr); 87 return 0; 88} 89 90/** 91 * ntfs_inode_hash_deinit - deinitialize the ntfs inode hash 92 * 93 * Deinitialize the ntfs inode hash. 94 */ 95void ntfs_inode_hash_deinit(void) 96{ 97 /* Deinitialize the ntfs inode hash lock. */ 98 lck_mtx_destroy(&ntfs_inode_hash_lock, ntfs_lock_grp); 99 /* 100 * Free the ntfs inode hash. 101 * 102 * FIXME: There is no hashdeinit() function so we do it ourselves but 103 * this means that if the implementation of hashinit() changes, this 104 * code will need to be adapted. 105 */ 106 FREE(ntfs_inode_hash_table, M_TEMP); 107} 108 109/** 110 * ntfs_inode_hash - calculate the hash for a given ntfs inode 111 * @vol: ntfs volume to which the inode belongs 112 * @mft_no: inode number/mft record number of the ntfs inode 113 * 114 * Return the hash for the ntfs inode with mft record number @mft_no on the 115 * volume @vol. 116 */ 117static inline unsigned long ntfs_inode_hash(const ntfs_volume *vol, 118 const ino64_t mft_no) 119{ 120 return (vol->dev + mft_no) & ntfs_inode_hash_mask; 121} 122 123/** 124 * ntfs_inode_hash_list - get the hash bucket list for a given ntfs inode 125 * @vol: ntfs volume to which the inode belongs 126 * @mft_no: inode number/mft record number of the ntfs inode 127 * 128 * Return the hash bucket list for the ntfs inode with mft record number 129 * @mft_no on the volume @vol. 130 */ 131static inline ntfs_inode_list_head *ntfs_inode_hash_list(const ntfs_volume *vol, 132 const ino64_t mft_no) 133{ 134 return ntfs_inode_hash_table + ntfs_inode_hash(vol, mft_no); 135} 136 137/** 138 * ntfs_inode_hash_list_find_nolock - find and return a loaded ntfs inode 139 * 140 * Search the ntfs inode hash bucket @list for the ntfs inode matching @na and 141 * if present return it. If not present return NULL. 142 * 143 * Locking: Caller must hold the @ntfs_inode_hash_lock. Note the lock may be 144 * dropped if an inode is found to be under reclaim or in the process 145 * of being loaded, in which cases we drop the lock and wait for the 146 * inode to be reclaimed/loaded and then we retry the search again. 147 */ 148static inline ntfs_inode *ntfs_inode_hash_list_find_nolock( 149 const ntfs_volume *vol, const ntfs_inode_list_head *list, 150 const ntfs_attr *na) 151{ 152 ntfs_inode *ni; 153 154 /* 155 * Iterate over all the entries in the hash bucket matching @mp and 156 * @mft_no. If the ntfs_inode is not in cache, the loop is exited with 157 * @ni set to NULL. 158 */ 159retry: 160 LIST_FOREACH(ni, list, hash) { 161 if (ni->vol != vol) 162 continue; 163 if (!ntfs_inode_test(ni, na)) 164 continue; 165 /* 166 * Make sure that the inode cannot disappear under us at this 167 * point by going to sleep and retrying if it is in the process 168 * of being discarded or allocated. 169 */ 170 if (NInoReclaim(ni) || NInoAlloc(ni)) { 171#ifdef DEBUG 172 const char *op; 173 174 if (NInoReclaim(ni)) 175 op = "reclaim"; 176 else /* if (NInoAlloc(ni)) */ 177 op = "allocat"; 178 ntfs_debug("Inode is being %sed, waiting and " 179 "retrying.", op); 180#endif 181 /* Drops the hash lock. */ 182 ntfs_inode_wait(ni, &ntfs_inode_hash_lock); 183 lck_mtx_lock(&ntfs_inode_hash_lock); 184 goto retry; 185 } 186 /* Found the inode. */ 187 break; 188 } 189 return ni; 190} 191 192/** 193 * ntfs_inode_hash_list_find - find and return a loaded ntfs inode 194 * 195 * Search the ntfs inode hash bucket @list for the ntfs inode matching @na and 196 * if present return it. If not present return NULL. 197 * 198 * If the found ntfs inode has a vnode attached, then get an iocount reference 199 * on the vnode. 200 */ 201static inline ntfs_inode *ntfs_inode_hash_list_find(const ntfs_volume *vol, 202 const ntfs_inode_list_head *list, const ntfs_attr *na) 203{ 204 ntfs_inode *ni; 205 206retry: 207 lck_mtx_lock(&ntfs_inode_hash_lock); 208 ni = ntfs_inode_hash_list_find_nolock(vol, list, na); 209 if (ni) { 210 vnode_t vn; 211 u32 vn_id = 0; 212 213 // FIXME: If this is an extent inode (i.e. it has no vnode), do 214 // we want to take an iocount reference on its base vnode? If 215 // so we would need to make sure to release it when finished 216 // with the extent inode. -> Need to do that but only when we 217 // start looking up extent inodes from the $MFT pageout code 218 // path so that the base inode cannot disappear under us which 219 // would also cause the extent ntfs inode to disappear under 220 // us. 221 vn = ni->vn; 222 if (vn) 223 vn_id = vnode_vid(vn); 224 lck_mtx_unlock(&ntfs_inode_hash_lock); 225 if (vn && vnode_getwithvid(vn, vn_id)) 226 goto retry; 227 return ni; 228 } 229 lck_mtx_unlock(&ntfs_inode_hash_lock); 230 return ni; 231} 232 233/** 234 * ntfs_inode_hash_lookup - find and return a loaded ntfs inode 235 * 236 * Search the ntfs inode hash for the ntfs inode matching @na and if present 237 * return it. If not present return NULL. 238 * 239 * If the found ntfs inode has a vnode attached, then get an iocount reference 240 * on the vnode. 241 */ 242ntfs_inode *ntfs_inode_hash_lookup(ntfs_volume *vol, const ntfs_attr *na) 243{ 244 ntfs_inode_list_head *list; 245 ntfs_inode *ni; 246 247 ntfs_debug("Entering for mft_no 0x%llx, type 0x%x, name_len 0x%x.", 248 (unsigned long long)na->mft_no, 249 (unsigned)le32_to_cpu(na->type), na->name_len); 250 list = ntfs_inode_hash_list(vol, na->mft_no); 251 ni = ntfs_inode_hash_list_find(vol, list, na); 252 ntfs_debug("Done (ntfs_inode %sfound in cache).", ni ? "" : "not "); 253 return ni; 254} 255 256/** 257 * ntfs_inode_hash_get - find or allocate, and return a loaded ntfs inode 258 * 259 * Search the ntfs inode hash for the ntfs inode matching @na and if present 260 * return it. 261 * 262 * If the found ntfs inode has a vnode attached, then get an iocount reference 263 * on the vnode. 264 * 265 * If not present, allocate the ntfs inode, add it to the hash, and initialize 266 * it before returning it. The inode will be marked NInoAlloc() and no vnode 267 * will be attached yet. 268 */ 269ntfs_inode *ntfs_inode_hash_get(ntfs_volume *vol, const ntfs_attr *na) 270{ 271 ntfs_inode_list_head *list; 272 ntfs_inode *ni, *nni; 273 274 ntfs_debug("Entering for mft_no 0x%llx, type 0x%x, name_len 0x%x.", 275 (unsigned long long)na->mft_no, 276 (unsigned)le32_to_cpu(na->type), na->name_len); 277 list = ntfs_inode_hash_list(vol, na->mft_no); 278 ni = ntfs_inode_hash_list_find(vol, list, na); 279 if (ni) { 280 ntfs_debug("Done (ntfs_inode found in cache)."); 281 return ni; 282 } 283 /* Not found, allocate a new ntfs_inode and initialize it. */ 284 nni = OSMalloc(sizeof(ntfs_inode), ntfs_malloc_tag); 285 if (!nni) { 286 ntfs_error(vol->mp, "Failed to allocate new ntfs_inode."); 287 return nni; 288 } 289 if (ntfs_inode_init(vol, nni, na)) { 290 OSFree(nni, sizeof(ntfs_inode), ntfs_malloc_tag); 291 ntfs_error(vol->mp, "Failed to initialize new ntfs_inode."); 292 return NULL; 293 } 294 /* 295 * Take the hash lock and ensure a racing process did not already 296 * allocate the inode by searching for it again in the cache. 297 */ 298retry: 299 lck_mtx_lock(&ntfs_inode_hash_lock); 300 ni = ntfs_inode_hash_list_find_nolock(vol, list, na); 301 if (ni) { 302 /* 303 * Someone else already added the ntfs inode so return that and 304 * throw away ours. 305 */ 306 vnode_t vn; 307 u32 vn_id = 0; 308 309 vn = ni->vn; 310 if (vn) 311 vn_id = vnode_vid(vn); 312 /* Drops the hash lock. */ 313 ntfs_inode_wait_locked(ni, &ntfs_inode_hash_lock); 314 if (vn && vnode_getwithvid(vn, vn_id)) 315 goto retry; 316 OSFree(nni, sizeof(ntfs_inode), ntfs_malloc_tag); 317 ntfs_debug("Done (ntfs_inode found in cache - lost race))."); 318 return ni; 319 } 320 /* 321 * We have allocated a new ntfs inode, it is NInoLocked() and 322 * NInoAlloc() and we hold the hash lock so we can now add our inode to 323 * the hash list bucket and drop the hash lock. 324 */ 325 LIST_INSERT_HEAD(list, nni, hash); 326 lck_mtx_unlock(&ntfs_inode_hash_lock); 327 /* Add the inode to the list of inodes in the volume. */ 328 lck_mtx_lock(&vol->inodes_lock); 329 LIST_INSERT_HEAD(&vol->inodes, nni, inodes); 330 lck_mtx_unlock(&vol->inodes_lock); 331 ntfs_debug("Done (new ntfs_inode added to cache)."); 332 return nni; 333} 334 335/** 336 * ntfs_inode_hash_rm - remove an ntfs inode from the ntfs inode hash 337 * @ni: ntfs inode to remove from the hash 338 * 339 * Remove the ntfs inode @ni from the ntfs inode hash. 340 */ 341void ntfs_inode_hash_rm(ntfs_inode *ni) 342{ 343 lck_mtx_lock(&ntfs_inode_hash_lock); 344 ntfs_inode_hash_rm_nolock(ni); 345 lck_mtx_unlock(&ntfs_inode_hash_lock); 346} 347