1 /* 2 * index.c - NTFS kernel index handling. Part of the Linux-NTFS project. 3 * 4 * Copyright (c) 2004 Anton Altaparmakov 5 * 6 * This program/include file is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU General Public License as published 8 * by the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * This program/include file is distributed in the hope that it will be 12 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty 13 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program (in the main directory of the Linux-NTFS 18 * distribution in the file COPYING); if not, write to the Free Software 19 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20 */ 21 22 #include "aops.h" 23 #include "collate.h" 24 #include "debug.h" 25 #include "index.h" 26 #include "ntfs.h" 27 28 /** 29 * ntfs_index_ctx_get - allocate and initialize a new index context 30 * @idx_ni: ntfs index inode with which to initialize the context 31 * 32 * Allocate a new index context, initialize it with @idx_ni and return it. 33 * Return NULL if allocation failed. 34 * 35 * Locking: Caller must hold i_sem on the index inode. 36 */ 37 ntfs_index_context *ntfs_index_ctx_get(ntfs_inode *idx_ni) 38 { 39 ntfs_index_context *ictx; 40 41 ictx = kmem_cache_alloc(ntfs_index_ctx_cache, SLAB_NOFS); 42 if (ictx) { 43 ictx->idx_ni = idx_ni; 44 ictx->entry = NULL; 45 ictx->data = NULL; 46 ictx->data_len = 0; 47 ictx->is_in_root = 0; 48 ictx->ir = NULL; 49 ictx->actx = NULL; 50 ictx->base_ni = NULL; 51 ictx->ia = NULL; 52 ictx->page = NULL; 53 } 54 return ictx; 55 } 56 57 /** 58 * ntfs_index_ctx_put - release an index context 59 * @ictx: index context to free 60 * 61 * Release the index context @ictx, releasing all associated resources. 62 * 63 * Locking: Caller must hold i_sem on the index inode. 64 */ 65 void ntfs_index_ctx_put(ntfs_index_context *ictx) 66 { 67 if (ictx->entry) { 68 if (ictx->is_in_root) { 69 if (ictx->actx) 70 ntfs_attr_put_search_ctx(ictx->actx); 71 if (ictx->base_ni) 72 unmap_mft_record(ictx->base_ni); 73 } else { 74 struct page *page = ictx->page; 75 if (page) { 76 BUG_ON(!PageLocked(page)); 77 unlock_page(page); 78 ntfs_unmap_page(page); 79 } 80 } 81 } 82 kmem_cache_free(ntfs_index_ctx_cache, ictx); 83 return; 84 } 85 86 /** 87 * ntfs_index_lookup - find a key in an index and return its index entry 88 * @key: [IN] key for which to search in the index 89 * @key_len: [IN] length of @key in bytes 90 * @ictx: [IN/OUT] context describing the index and the returned entry 91 * 92 * Before calling ntfs_index_lookup(), @ictx must have been obtained from a 93 * call to ntfs_index_ctx_get(). 94 * 95 * Look for the @key in the index specified by the index lookup context @ictx. 96 * ntfs_index_lookup() walks the contents of the index looking for the @key. 97 * 98 * If the @key is found in the index, 0 is returned and @ictx is setup to 99 * describe the index entry containing the matching @key. @ictx->entry is the 100 * index entry and @ictx->data and @ictx->data_len are the index entry data and 101 * its length in bytes, respectively. 102 * 103 * If the @key is not found in the index, -ENOENT is returned and @ictx is 104 * setup to describe the index entry whose key collates immediately after the 105 * search @key, i.e. this is the position in the index at which an index entry 106 * with a key of @key would need to be inserted. 107 * 108 * If an error occurs return the negative error code and @ictx is left 109 * untouched. 110 * 111 * When finished with the entry and its data, call ntfs_index_ctx_put() to free 112 * the context and other associated resources. 113 * 114 * If the index entry was modified, call flush_dcache_index_entry_page() 115 * immediately after the modification and either ntfs_index_entry_mark_dirty() 116 * or ntfs_index_entry_write() before the call to ntfs_index_ctx_put() to 117 * ensure that the changes are written to disk. 118 * 119 * Locking: - Caller must hold i_sem on the index inode. 120 * - Each page cache page in the index allocation mapping must be 121 * locked whilst being accessed otherwise we may find a corrupt 122 * page due to it being under ->writepage at the moment which 123 * applies the mst protection fixups before writing out and then 124 * removes them again after the write is complete after which it 125 * unlocks the page. 126 */ 127 int ntfs_index_lookup(const void *key, const int key_len, 128 ntfs_index_context *ictx) 129 { 130 VCN vcn, old_vcn; 131 ntfs_inode *idx_ni = ictx->idx_ni; 132 ntfs_volume *vol = idx_ni->vol; 133 struct super_block *sb = vol->sb; 134 ntfs_inode *base_ni = idx_ni->ext.base_ntfs_ino; 135 MFT_RECORD *m; 136 INDEX_ROOT *ir; 137 INDEX_ENTRY *ie; 138 INDEX_ALLOCATION *ia; 139 u8 *index_end, *kaddr; 140 ntfs_attr_search_ctx *actx; 141 struct address_space *ia_mapping; 142 struct page *page; 143 int rc, err = 0; 144 145 ntfs_debug("Entering."); 146 BUG_ON(!NInoAttr(idx_ni)); 147 BUG_ON(idx_ni->type != AT_INDEX_ALLOCATION); 148 BUG_ON(idx_ni->nr_extents != -1); 149 BUG_ON(!base_ni); 150 BUG_ON(!key); 151 BUG_ON(key_len <= 0); 152 if (!ntfs_is_collation_rule_supported( 153 idx_ni->itype.index.collation_rule)) { 154 ntfs_error(sb, "Index uses unsupported collation rule 0x%x. " 155 "Aborting lookup.", le32_to_cpu( 156 idx_ni->itype.index.collation_rule)); 157 return -EOPNOTSUPP; 158 } 159 /* Get hold of the mft record for the index inode. */ 160 m = map_mft_record(base_ni); 161 if (IS_ERR(m)) { 162 ntfs_error(sb, "map_mft_record() failed with error code %ld.", 163 -PTR_ERR(m)); 164 return PTR_ERR(m); 165 } 166 actx = ntfs_attr_get_search_ctx(base_ni, m); 167 if (unlikely(!actx)) { 168 err = -ENOMEM; 169 goto err_out; 170 } 171 /* Find the index root attribute in the mft record. */ 172 err = ntfs_attr_lookup(AT_INDEX_ROOT, idx_ni->name, idx_ni->name_len, 173 CASE_SENSITIVE, 0, NULL, 0, actx); 174 if (unlikely(err)) { 175 if (err == -ENOENT) { 176 ntfs_error(sb, "Index root attribute missing in inode " 177 "0x%lx.", idx_ni->mft_no); 178 err = -EIO; 179 } 180 goto err_out; 181 } 182 /* Get to the index root value (it has been verified in read_inode). */ 183 ir = (INDEX_ROOT*)((u8*)actx->attr + 184 le16_to_cpu(actx->attr->data.resident.value_offset)); 185 index_end = (u8*)&ir->index + le32_to_cpu(ir->index.index_length); 186 /* The first index entry. */ 187 ie = (INDEX_ENTRY*)((u8*)&ir->index + 188 le32_to_cpu(ir->index.entries_offset)); 189 /* 190 * Loop until we exceed valid memory (corruption case) or until we 191 * reach the last entry. 192 */ 193 for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) { 194 /* Bounds checks. */ 195 if ((u8*)ie < (u8*)actx->mrec || (u8*)ie + 196 sizeof(INDEX_ENTRY_HEADER) > index_end || 197 (u8*)ie + le16_to_cpu(ie->length) > index_end) 198 goto idx_err_out; 199 /* 200 * The last entry cannot contain a key. It can however contain 201 * a pointer to a child node in the B+tree so we just break out. 202 */ 203 if (ie->flags & INDEX_ENTRY_END) 204 break; 205 /* Further bounds checks. */ 206 if ((u32)sizeof(INDEX_ENTRY_HEADER) + 207 le16_to_cpu(ie->key_length) > 208 le16_to_cpu(ie->data.vi.data_offset) || 209 (u32)le16_to_cpu(ie->data.vi.data_offset) + 210 le16_to_cpu(ie->data.vi.data_length) > 211 le16_to_cpu(ie->length)) 212 goto idx_err_out; 213 /* If the keys match perfectly, we setup @ictx and return 0. */ 214 if ((key_len == le16_to_cpu(ie->key_length)) && !memcmp(key, 215 &ie->key, key_len)) { 216 ir_done: 217 ictx->is_in_root = TRUE; 218 ictx->actx = actx; 219 ictx->base_ni = base_ni; 220 ictx->ia = NULL; 221 ictx->page = NULL; 222 done: 223 ictx->entry = ie; 224 ictx->data = (u8*)ie + 225 le16_to_cpu(ie->data.vi.data_offset); 226 ictx->data_len = le16_to_cpu(ie->data.vi.data_length); 227 ntfs_debug("Done."); 228 return err; 229 } 230 /* 231 * Not a perfect match, need to do full blown collation so we 232 * know which way in the B+tree we have to go. 233 */ 234 rc = ntfs_collate(vol, idx_ni->itype.index.collation_rule, key, 235 key_len, &ie->key, le16_to_cpu(ie->key_length)); 236 /* 237 * If @key collates before the key of the current entry, there 238 * is definitely no such key in this index but we might need to 239 * descend into the B+tree so we just break out of the loop. 240 */ 241 if (rc == -1) 242 break; 243 /* 244 * A match should never happen as the memcmp() call should have 245 * cought it, but we still treat it correctly. 246 */ 247 if (!rc) 248 goto ir_done; 249 /* The keys are not equal, continue the search. */ 250 } 251 /* 252 * We have finished with this index without success. Check for the 253 * presence of a child node and if not present setup @ictx and return 254 * -ENOENT. 255 */ 256 if (!(ie->flags & INDEX_ENTRY_NODE)) { 257 ntfs_debug("Entry not found."); 258 err = -ENOENT; 259 goto ir_done; 260 } /* Child node present, descend into it. */ 261 /* Consistency check: Verify that an index allocation exists. */ 262 if (!NInoIndexAllocPresent(idx_ni)) { 263 ntfs_error(sb, "No index allocation attribute but index entry " 264 "requires one. Inode 0x%lx is corrupt or " 265 "driver bug.", idx_ni->mft_no); 266 goto err_out; 267 } 268 /* Get the starting vcn of the index_block holding the child node. */ 269 vcn = sle64_to_cpup((sle64*)((u8*)ie + le16_to_cpu(ie->length) - 8)); 270 ia_mapping = VFS_I(idx_ni)->i_mapping; 271 /* 272 * We are done with the index root and the mft record. Release them, 273 * otherwise we deadlock with ntfs_map_page(). 274 */ 275 ntfs_attr_put_search_ctx(actx); 276 unmap_mft_record(base_ni); 277 m = NULL; 278 actx = NULL; 279 descend_into_child_node: 280 /* 281 * Convert vcn to index into the index allocation attribute in units 282 * of PAGE_CACHE_SIZE and map the page cache page, reading it from 283 * disk if necessary. 284 */ 285 page = ntfs_map_page(ia_mapping, vcn << 286 idx_ni->itype.index.vcn_size_bits >> PAGE_CACHE_SHIFT); 287 if (IS_ERR(page)) { 288 ntfs_error(sb, "Failed to map index page, error %ld.", 289 -PTR_ERR(page)); 290 err = PTR_ERR(page); 291 goto err_out; 292 } 293 lock_page(page); 294 kaddr = (u8*)page_address(page); 295 fast_descend_into_child_node: 296 /* Get to the index allocation block. */ 297 ia = (INDEX_ALLOCATION*)(kaddr + ((vcn << 298 idx_ni->itype.index.vcn_size_bits) & ~PAGE_CACHE_MASK)); 299 /* Bounds checks. */ 300 if ((u8*)ia < kaddr || (u8*)ia > kaddr + PAGE_CACHE_SIZE) { 301 ntfs_error(sb, "Out of bounds check failed. Corrupt inode " 302 "0x%lx or driver bug.", idx_ni->mft_no); 303 goto unm_err_out; 304 } 305 /* Catch multi sector transfer fixup errors. */ 306 if (unlikely(!ntfs_is_indx_record(ia->magic))) { 307 ntfs_error(sb, "Index record with vcn 0x%llx is corrupt. " 308 "Corrupt inode 0x%lx. Run chkdsk.", 309 (long long)vcn, idx_ni->mft_no); 310 goto unm_err_out; 311 } 312 if (sle64_to_cpu(ia->index_block_vcn) != vcn) { 313 ntfs_error(sb, "Actual VCN (0x%llx) of index buffer is " 314 "different from expected VCN (0x%llx). Inode " 315 "0x%lx is corrupt or driver bug.", 316 (unsigned long long) 317 sle64_to_cpu(ia->index_block_vcn), 318 (unsigned long long)vcn, idx_ni->mft_no); 319 goto unm_err_out; 320 } 321 if (le32_to_cpu(ia->index.allocated_size) + 0x18 != 322 idx_ni->itype.index.block_size) { 323 ntfs_error(sb, "Index buffer (VCN 0x%llx) of inode 0x%lx has " 324 "a size (%u) differing from the index " 325 "specified size (%u). Inode is corrupt or " 326 "driver bug.", (unsigned long long)vcn, 327 idx_ni->mft_no, 328 le32_to_cpu(ia->index.allocated_size) + 0x18, 329 idx_ni->itype.index.block_size); 330 goto unm_err_out; 331 } 332 index_end = (u8*)ia + idx_ni->itype.index.block_size; 333 if (index_end > kaddr + PAGE_CACHE_SIZE) { 334 ntfs_error(sb, "Index buffer (VCN 0x%llx) of inode 0x%lx " 335 "crosses page boundary. Impossible! Cannot " 336 "access! This is probably a bug in the " 337 "driver.", (unsigned long long)vcn, 338 idx_ni->mft_no); 339 goto unm_err_out; 340 } 341 index_end = (u8*)&ia->index + le32_to_cpu(ia->index.index_length); 342 if (index_end > (u8*)ia + idx_ni->itype.index.block_size) { 343 ntfs_error(sb, "Size of index buffer (VCN 0x%llx) of inode " 344 "0x%lx exceeds maximum size.", 345 (unsigned long long)vcn, idx_ni->mft_no); 346 goto unm_err_out; 347 } 348 /* The first index entry. */ 349 ie = (INDEX_ENTRY*)((u8*)&ia->index + 350 le32_to_cpu(ia->index.entries_offset)); 351 /* 352 * Iterate similar to above big loop but applied to index buffer, thus 353 * loop until we exceed valid memory (corruption case) or until we 354 * reach the last entry. 355 */ 356 for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) { 357 /* Bounds checks. */ 358 if ((u8*)ie < (u8*)ia || (u8*)ie + 359 sizeof(INDEX_ENTRY_HEADER) > index_end || 360 (u8*)ie + le16_to_cpu(ie->length) > index_end) { 361 ntfs_error(sb, "Index entry out of bounds in inode " 362 "0x%lx.", idx_ni->mft_no); 363 goto unm_err_out; 364 } 365 /* 366 * The last entry cannot contain a key. It can however contain 367 * a pointer to a child node in the B+tree so we just break out. 368 */ 369 if (ie->flags & INDEX_ENTRY_END) 370 break; 371 /* Further bounds checks. */ 372 if ((u32)sizeof(INDEX_ENTRY_HEADER) + 373 le16_to_cpu(ie->key_length) > 374 le16_to_cpu(ie->data.vi.data_offset) || 375 (u32)le16_to_cpu(ie->data.vi.data_offset) + 376 le16_to_cpu(ie->data.vi.data_length) > 377 le16_to_cpu(ie->length)) { 378 ntfs_error(sb, "Index entry out of bounds in inode " 379 "0x%lx.", idx_ni->mft_no); 380 goto unm_err_out; 381 } 382 /* If the keys match perfectly, we setup @ictx and return 0. */ 383 if ((key_len == le16_to_cpu(ie->key_length)) && !memcmp(key, 384 &ie->key, key_len)) { 385 ia_done: 386 ictx->is_in_root = FALSE; 387 ictx->actx = NULL; 388 ictx->base_ni = NULL; 389 ictx->ia = ia; 390 ictx->page = page; 391 goto done; 392 } 393 /* 394 * Not a perfect match, need to do full blown collation so we 395 * know which way in the B+tree we have to go. 396 */ 397 rc = ntfs_collate(vol, idx_ni->itype.index.collation_rule, key, 398 key_len, &ie->key, le16_to_cpu(ie->key_length)); 399 /* 400 * If @key collates before the key of the current entry, there 401 * is definitely no such key in this index but we might need to 402 * descend into the B+tree so we just break out of the loop. 403 */ 404 if (rc == -1) 405 break; 406 /* 407 * A match should never happen as the memcmp() call should have 408 * cought it, but we still treat it correctly. 409 */ 410 if (!rc) 411 goto ia_done; 412 /* The keys are not equal, continue the search. */ 413 } 414 /* 415 * We have finished with this index buffer without success. Check for 416 * the presence of a child node and if not present return -ENOENT. 417 */ 418 if (!(ie->flags & INDEX_ENTRY_NODE)) { 419 ntfs_debug("Entry not found."); 420 err = -ENOENT; 421 goto ia_done; 422 } 423 if ((ia->index.flags & NODE_MASK) == LEAF_NODE) { 424 ntfs_error(sb, "Index entry with child node found in a leaf " 425 "node in inode 0x%lx.", idx_ni->mft_no); 426 goto unm_err_out; 427 } 428 /* Child node present, descend into it. */ 429 old_vcn = vcn; 430 vcn = sle64_to_cpup((sle64*)((u8*)ie + le16_to_cpu(ie->length) - 8)); 431 if (vcn >= 0) { 432 /* 433 * If vcn is in the same page cache page as old_vcn we recycle 434 * the mapped page. 435 */ 436 if (old_vcn << vol->cluster_size_bits >> 437 PAGE_CACHE_SHIFT == vcn << 438 vol->cluster_size_bits >> 439 PAGE_CACHE_SHIFT) 440 goto fast_descend_into_child_node; 441 unlock_page(page); 442 ntfs_unmap_page(page); 443 goto descend_into_child_node; 444 } 445 ntfs_error(sb, "Negative child node vcn in inode 0x%lx.", 446 idx_ni->mft_no); 447 unm_err_out: 448 unlock_page(page); 449 ntfs_unmap_page(page); 450 err_out: 451 if (!err) 452 err = -EIO; 453 if (actx) 454 ntfs_attr_put_search_ctx(actx); 455 if (m) 456 unmap_mft_record(base_ni); 457 return err; 458 idx_err_out: 459 ntfs_error(sb, "Corrupt index. Aborting lookup."); 460 goto err_out; 461 } 462