1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * NTFS kernel index handling. 4 * 5 * Copyright (c) 2004-2005 Anton Altaparmakov 6 * Copyright (c) 2025 LG Electronics Co., Ltd. 7 * 8 * Part of this file is based on code from the NTFS-3G. 9 * and is copyrighted by the respective authors below: 10 * Copyright (c) 2004-2005 Anton Altaparmakov 11 * Copyright (c) 2004-2005 Richard Russon 12 * Copyright (c) 2005-2006 Yura Pakhuchiy 13 * Copyright (c) 2005-2008 Szabolcs Szakacsits 14 * Copyright (c) 2007-2021 Jean-Pierre Andre 15 */ 16 17 #include "collate.h" 18 #include "index.h" 19 #include "ntfs.h" 20 #include "attrlist.h" 21 22 /* 23 * ntfs_index_entry_inconsistent - Check the consistency of an index entry 24 * 25 * Make sure data and key do not overflow from entry. 26 * As a side effect, an entry with zero length is rejected. 27 * This entry must be a full one (no INDEX_ENTRY_END flag), and its 28 * length must have been checked beforehand to not overflow from the 29 * index record. 30 */ 31 int ntfs_index_entry_inconsistent(struct ntfs_index_context *icx, 32 struct ntfs_volume *vol, const struct index_entry *ie, 33 __le32 collation_rule, u64 inum) 34 { 35 if (icx) { 36 struct index_header *ih; 37 u8 *ie_start, *ie_end; 38 39 if (icx->is_in_root) 40 ih = &icx->ir->index; 41 else 42 ih = &icx->ib->index; 43 44 if ((le32_to_cpu(ih->index_length) > le32_to_cpu(ih->allocated_size)) || 45 (le32_to_cpu(ih->index_length) > icx->block_size)) { 46 ntfs_error(vol->sb, "%s Index entry(0x%p)'s length is too big.", 47 icx->is_in_root ? "Index root" : "Index block", 48 (u8 *)icx->entry); 49 return -EINVAL; 50 } 51 52 ie_start = (u8 *)ih + le32_to_cpu(ih->entries_offset); 53 ie_end = (u8 *)ih + le32_to_cpu(ih->index_length); 54 55 if (ie_start > (u8 *)ie || 56 ie_end <= (u8 *)ie + le16_to_cpu(ie->length) || 57 le16_to_cpu(ie->length) > le32_to_cpu(ih->allocated_size) || 58 le16_to_cpu(ie->length) > icx->block_size) { 59 ntfs_error(vol->sb, "Index entry(0x%p) is out of range from %s", 60 (u8 *)icx->entry, 61 icx->is_in_root ? "index root" : "index block"); 62 return -EIO; 63 } 64 } 65 66 if (ie->key_length && 67 ((le16_to_cpu(ie->key_length) + offsetof(struct index_entry, key)) > 68 le16_to_cpu(ie->length))) { 69 ntfs_error(vol->sb, "Overflow from index entry in inode %lld\n", 70 (long long)inum); 71 return -EIO; 72 73 } else { 74 if (collation_rule == COLLATION_FILE_NAME) { 75 if ((offsetof(struct index_entry, key.file_name.file_name) + 76 ie->key.file_name.file_name_length * sizeof(__le16)) > 77 le16_to_cpu(ie->length)) { 78 ntfs_error(vol->sb, 79 "File name overflow from index entry in inode %lld\n", 80 (long long)inum); 81 return -EIO; 82 } 83 } else { 84 if (ie->data.vi.data_length && 85 ((le16_to_cpu(ie->data.vi.data_offset) + 86 le16_to_cpu(ie->data.vi.data_length)) > 87 le16_to_cpu(ie->length))) { 88 ntfs_error(vol->sb, 89 "Data overflow from index entry in inode %lld\n", 90 (long long)inum); 91 return -EIO; 92 } 93 } 94 } 95 96 return 0; 97 } 98 99 /* 100 * ntfs_index_entry_mark_dirty - mark an index entry dirty 101 * @ictx: ntfs index context describing the index entry 102 * 103 * Mark the index entry described by the index entry context @ictx dirty. 104 * 105 * If the index entry is in the index root attribute, simply mark the inode 106 * containing the index root attribute dirty. This ensures the mftrecord, and 107 * hence the index root attribute, will be written out to disk later. 108 * 109 * If the index entry is in an index block belonging to the index allocation 110 * attribute, set ib_dirty to true, thus index block will be updated during 111 * ntfs_index_ctx_put. 112 */ 113 void ntfs_index_entry_mark_dirty(struct ntfs_index_context *ictx) 114 { 115 if (ictx->is_in_root) 116 mark_mft_record_dirty(ictx->actx->ntfs_ino); 117 else if (ictx->ib) 118 ictx->ib_dirty = true; 119 } 120 121 static s64 ntfs_ib_vcn_to_pos(struct ntfs_index_context *icx, s64 vcn) 122 { 123 return vcn << icx->vcn_size_bits; 124 } 125 126 static s64 ntfs_ib_pos_to_vcn(struct ntfs_index_context *icx, s64 pos) 127 { 128 return pos >> icx->vcn_size_bits; 129 } 130 131 static int ntfs_ib_write(struct ntfs_index_context *icx, struct index_block *ib) 132 { 133 s64 ret, vcn = le64_to_cpu(ib->index_block_vcn); 134 135 ntfs_debug("vcn: %lld\n", vcn); 136 137 ret = pre_write_mst_fixup((struct ntfs_record *)ib, icx->block_size); 138 if (ret) 139 return -EIO; 140 141 ret = ntfs_inode_attr_pwrite(VFS_I(icx->ia_ni), 142 ntfs_ib_vcn_to_pos(icx, vcn), icx->block_size, 143 (u8 *)ib, icx->sync_write); 144 if (ret != icx->block_size) { 145 ntfs_debug("Failed to write index block %lld, inode %llu", 146 vcn, (unsigned long long)icx->idx_ni->mft_no); 147 return ret; 148 } 149 150 return 0; 151 } 152 153 static int ntfs_icx_ib_write(struct ntfs_index_context *icx) 154 { 155 int err; 156 157 err = ntfs_ib_write(icx, icx->ib); 158 if (err) 159 return err; 160 161 icx->ib_dirty = false; 162 163 return 0; 164 } 165 166 int ntfs_icx_ib_sync_write(struct ntfs_index_context *icx) 167 { 168 int ret; 169 170 if (icx->ib_dirty == false) 171 return 0; 172 173 icx->sync_write = true; 174 175 ret = ntfs_ib_write(icx, icx->ib); 176 if (!ret) { 177 kvfree(icx->ib); 178 icx->ib = NULL; 179 icx->ib_dirty = false; 180 } else { 181 post_write_mst_fixup((struct ntfs_record *)icx->ib); 182 icx->sync_write = false; 183 } 184 185 return ret; 186 } 187 188 /* 189 * ntfs_index_ctx_get - allocate and initialize a new index context 190 * @ni: ntfs inode with which to initialize the context 191 * @name: name of the which context describes 192 * @name_len: length of the index name 193 * 194 * Allocate a new index context, initialize it with @ni and return it. 195 * Return NULL if allocation failed. 196 */ 197 struct ntfs_index_context *ntfs_index_ctx_get(struct ntfs_inode *ni, 198 __le16 *name, u32 name_len) 199 { 200 struct ntfs_index_context *icx; 201 202 ntfs_debug("Entering\n"); 203 204 if (!ni) 205 return NULL; 206 207 if (ni->nr_extents == -1) 208 ni = ni->ext.base_ntfs_ino; 209 210 icx = kmem_cache_alloc(ntfs_index_ctx_cache, GFP_NOFS); 211 if (icx) 212 *icx = (struct ntfs_index_context) { 213 .idx_ni = ni, 214 .name = name, 215 .name_len = name_len, 216 }; 217 return icx; 218 } 219 220 static void ntfs_index_ctx_free(struct ntfs_index_context *icx) 221 { 222 ntfs_debug("Entering\n"); 223 224 if (icx->actx) { 225 ntfs_attr_put_search_ctx(icx->actx); 226 icx->actx = NULL; 227 } 228 229 if (!icx->is_in_root) { 230 if (icx->ib_dirty) 231 ntfs_ib_write(icx, icx->ib); 232 kvfree(icx->ib); 233 icx->ib = NULL; 234 } 235 236 if (icx->ia_ni) { 237 iput(VFS_I(icx->ia_ni)); 238 icx->ia_ni = NULL; 239 } 240 } 241 242 /* 243 * ntfs_index_ctx_put - release an index context 244 * @icx: index context to free 245 * 246 * Release the index context @icx, releasing all associated resources. 247 */ 248 void ntfs_index_ctx_put(struct ntfs_index_context *icx) 249 { 250 ntfs_index_ctx_free(icx); 251 kmem_cache_free(ntfs_index_ctx_cache, icx); 252 } 253 254 /* 255 * ntfs_index_ctx_reinit - reinitialize an index context 256 * @icx: index context to reinitialize 257 * 258 * Reinitialize the index context @icx so it can be used for ntfs_index_lookup. 259 */ 260 void ntfs_index_ctx_reinit(struct ntfs_index_context *icx) 261 { 262 ntfs_debug("Entering\n"); 263 264 ntfs_index_ctx_free(icx); 265 266 *icx = (struct ntfs_index_context) { 267 .idx_ni = icx->idx_ni, 268 .name = icx->name, 269 .name_len = icx->name_len, 270 }; 271 } 272 273 static __le64 *ntfs_ie_get_vcn_addr(struct index_entry *ie) 274 { 275 return (__le64 *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(s64)); 276 } 277 278 /* 279 * Get the subnode vcn to which the index entry refers. 280 */ 281 static s64 ntfs_ie_get_vcn(struct index_entry *ie) 282 { 283 return le64_to_cpup(ntfs_ie_get_vcn_addr(ie)); 284 } 285 286 static struct index_entry *ntfs_ie_get_first(struct index_header *ih) 287 { 288 return (struct index_entry *)((u8 *)ih + le32_to_cpu(ih->entries_offset)); 289 } 290 291 static struct index_entry *ntfs_ie_get_next(struct index_entry *ie) 292 { 293 return (struct index_entry *)((char *)ie + le16_to_cpu(ie->length)); 294 } 295 296 static u8 *ntfs_ie_get_end(struct index_header *ih) 297 { 298 return (u8 *)ih + le32_to_cpu(ih->index_length); 299 } 300 301 static int ntfs_ie_end(struct index_entry *ie) 302 { 303 return ie->flags & INDEX_ENTRY_END || !ie->length; 304 } 305 306 /* 307 * Find the last entry in the index block 308 */ 309 static struct index_entry *ntfs_ie_get_last(struct index_entry *ie, char *ies_end) 310 { 311 ntfs_debug("Entering\n"); 312 313 while ((char *)ie < ies_end && !ntfs_ie_end(ie)) 314 ie = ntfs_ie_get_next(ie); 315 316 return ie; 317 } 318 319 static struct index_entry *ntfs_ie_get_by_pos(struct index_header *ih, int pos) 320 { 321 struct index_entry *ie; 322 323 ntfs_debug("pos: %d\n", pos); 324 325 ie = ntfs_ie_get_first(ih); 326 327 while (pos-- > 0) 328 ie = ntfs_ie_get_next(ie); 329 330 return ie; 331 } 332 333 static struct index_entry *ntfs_ie_prev(struct index_header *ih, struct index_entry *ie) 334 { 335 struct index_entry *ie_prev = NULL; 336 struct index_entry *tmp; 337 338 ntfs_debug("Entering\n"); 339 340 tmp = ntfs_ie_get_first(ih); 341 342 while (tmp != ie) { 343 ie_prev = tmp; 344 tmp = ntfs_ie_get_next(tmp); 345 } 346 347 return ie_prev; 348 } 349 350 static int ntfs_ih_numof_entries(struct index_header *ih) 351 { 352 int n; 353 struct index_entry *ie; 354 u8 *end; 355 356 ntfs_debug("Entering\n"); 357 358 end = ntfs_ie_get_end(ih); 359 ie = ntfs_ie_get_first(ih); 360 for (n = 0; !ntfs_ie_end(ie) && (u8 *)ie < end; n++) 361 ie = ntfs_ie_get_next(ie); 362 return n; 363 } 364 365 static int ntfs_ih_one_entry(struct index_header *ih) 366 { 367 return (ntfs_ih_numof_entries(ih) == 1); 368 } 369 370 static int ntfs_ih_zero_entry(struct index_header *ih) 371 { 372 return (ntfs_ih_numof_entries(ih) == 0); 373 } 374 375 static void ntfs_ie_delete(struct index_header *ih, struct index_entry *ie) 376 { 377 u32 new_size; 378 379 ntfs_debug("Entering\n"); 380 381 new_size = le32_to_cpu(ih->index_length) - le16_to_cpu(ie->length); 382 ih->index_length = cpu_to_le32(new_size); 383 memmove(ie, (u8 *)ie + le16_to_cpu(ie->length), 384 new_size - ((u8 *)ie - (u8 *)ih)); 385 } 386 387 static void ntfs_ie_set_vcn(struct index_entry *ie, s64 vcn) 388 { 389 *ntfs_ie_get_vcn_addr(ie) = cpu_to_le64(vcn); 390 } 391 392 /* 393 * Insert @ie index entry at @pos entry. Used @ih values should be ok already. 394 */ 395 static void ntfs_ie_insert(struct index_header *ih, struct index_entry *ie, 396 struct index_entry *pos) 397 { 398 int ie_size = le16_to_cpu(ie->length); 399 400 ntfs_debug("Entering\n"); 401 402 ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) + ie_size); 403 memmove((u8 *)pos + ie_size, pos, 404 le32_to_cpu(ih->index_length) - ((u8 *)pos - (u8 *)ih) - ie_size); 405 memcpy(pos, ie, ie_size); 406 } 407 408 static struct index_entry *ntfs_ie_dup(struct index_entry *ie) 409 { 410 ntfs_debug("Entering\n"); 411 412 return kmemdup(ie, le16_to_cpu(ie->length), GFP_NOFS); 413 } 414 415 static struct index_entry *ntfs_ie_dup_novcn(struct index_entry *ie) 416 { 417 struct index_entry *dup; 418 int size = le16_to_cpu(ie->length); 419 420 ntfs_debug("Entering\n"); 421 422 if (ie->flags & INDEX_ENTRY_NODE) 423 size -= sizeof(s64); 424 425 dup = kmemdup(ie, size, GFP_NOFS); 426 if (dup) { 427 dup->flags &= ~INDEX_ENTRY_NODE; 428 dup->length = cpu_to_le16(size); 429 } 430 return dup; 431 } 432 433 /* 434 * Check the consistency of an index block 435 * 436 * Make sure the index block does not overflow from the index record. 437 * The size of block is assumed to have been checked to be what is 438 * defined in the index root. 439 * 440 * Returns 0 if no error was found -1 otherwise (with errno unchanged) 441 * 442 * |<--->| offsetof(struct index_block, index) 443 * | |<--->| sizeof(struct index_header) 444 * | | | 445 * | | | seq index entries unused 446 * |=====|=====|=====|===========================|==============| 447 * | | | | | 448 * | |<--------->| entries_offset | | 449 * | |<---------------- index_length ------->| | 450 * | |<--------------------- allocated_size --------------->| 451 * |<--------------------------- block_size ------------------->| 452 * 453 * size(struct index_header) <= ent_offset < ind_length <= alloc_size < bk_size 454 */ 455 static int ntfs_index_block_inconsistent(struct ntfs_index_context *icx, 456 struct index_block *ib, s64 vcn) 457 { 458 u32 ib_size = (unsigned int)le32_to_cpu(ib->index.allocated_size) + 459 offsetof(struct index_block, index); 460 struct super_block *sb = icx->idx_ni->vol->sb; 461 unsigned long long inum = icx->idx_ni->mft_no; 462 463 ntfs_debug("Entering\n"); 464 465 if (!ntfs_is_indx_record(ib->magic)) { 466 467 ntfs_error(sb, "Corrupt index block signature: vcn %lld inode %llu\n", 468 vcn, (unsigned long long)icx->idx_ni->mft_no); 469 return -1; 470 } 471 472 if (le64_to_cpu(ib->index_block_vcn) != vcn) { 473 ntfs_error(sb, 474 "Corrupt index block: s64 (%lld) is different from expected s64 (%lld) in inode %llu\n", 475 (long long)le64_to_cpu(ib->index_block_vcn), 476 vcn, inum); 477 return -1; 478 } 479 480 if (ib_size != icx->block_size) { 481 ntfs_error(sb, 482 "Corrupt index block : s64 (%lld) of inode %llu has a size (%u) differing from the index specified size (%u)\n", 483 vcn, inum, ib_size, icx->block_size); 484 return -1; 485 } 486 487 if (le32_to_cpu(ib->index.entries_offset) < sizeof(struct index_header)) { 488 ntfs_error(sb, "Invalid index entry offset in inode %lld\n", inum); 489 return -1; 490 } 491 if (le32_to_cpu(ib->index.index_length) <= 492 le32_to_cpu(ib->index.entries_offset)) { 493 ntfs_error(sb, "No space for index entries in inode %lld\n", inum); 494 return -1; 495 } 496 if (le32_to_cpu(ib->index.allocated_size) < 497 le32_to_cpu(ib->index.index_length)) { 498 ntfs_error(sb, "Index entries overflow in inode %lld\n", inum); 499 return -1; 500 } 501 502 return 0; 503 } 504 505 static struct index_root *ntfs_ir_lookup(struct ntfs_inode *ni, __le16 *name, 506 u32 name_len, struct ntfs_attr_search_ctx **ctx) 507 { 508 struct attr_record *a; 509 struct index_root *ir = NULL; 510 511 ntfs_debug("Entering\n"); 512 *ctx = ntfs_attr_get_search_ctx(ni, NULL); 513 if (!*ctx) { 514 ntfs_error(ni->vol->sb, "%s, Failed to get search context", __func__); 515 return NULL; 516 } 517 518 if (ntfs_attr_lookup(AT_INDEX_ROOT, name, name_len, CASE_SENSITIVE, 519 0, NULL, 0, *ctx)) { 520 ntfs_error(ni->vol->sb, "Failed to lookup $INDEX_ROOT"); 521 goto err_out; 522 } 523 524 a = (*ctx)->attr; 525 if (a->non_resident) { 526 ntfs_error(ni->vol->sb, "Non-resident $INDEX_ROOT detected"); 527 goto err_out; 528 } 529 530 ir = (struct index_root *)((char *)a + le16_to_cpu(a->data.resident.value_offset)); 531 err_out: 532 if (!ir) { 533 ntfs_attr_put_search_ctx(*ctx); 534 *ctx = NULL; 535 } 536 return ir; 537 } 538 539 static struct index_root *ntfs_ir_lookup2(struct ntfs_inode *ni, __le16 *name, u32 len) 540 { 541 struct ntfs_attr_search_ctx *ctx; 542 struct index_root *ir; 543 544 ir = ntfs_ir_lookup(ni, name, len, &ctx); 545 if (ir) 546 ntfs_attr_put_search_ctx(ctx); 547 return ir; 548 } 549 550 /* 551 * Find a key in the index block. 552 */ 553 static int ntfs_ie_lookup(const void *key, const u32 key_len, 554 struct ntfs_index_context *icx, struct index_header *ih, 555 s64 *vcn, struct index_entry **ie_out) 556 { 557 struct index_entry *ie; 558 u8 *index_end; 559 int rc, item = 0; 560 561 ntfs_debug("Entering\n"); 562 563 index_end = ntfs_ie_get_end(ih); 564 565 /* 566 * Loop until we exceed valid memory (corruption case) or until we 567 * reach the last entry. 568 */ 569 for (ie = ntfs_ie_get_first(ih); ; ie = ntfs_ie_get_next(ie)) { 570 /* Bounds checks. */ 571 if ((u8 *)ie + sizeof(struct index_entry_header) > index_end || 572 (u8 *)ie + le16_to_cpu(ie->length) > index_end) { 573 ntfs_error(icx->idx_ni->vol->sb, 574 "Index entry out of bounds in inode %llu.\n", 575 (unsigned long long)icx->idx_ni->mft_no); 576 return -ERANGE; 577 } 578 579 /* 580 * The last entry cannot contain a key. It can however contain 581 * a pointer to a child node in the B+tree so we just break out. 582 */ 583 if (ntfs_ie_end(ie)) 584 break; 585 586 /* 587 * Not a perfect match, need to do full blown collation so we 588 * know which way in the B+tree we have to go. 589 */ 590 rc = ntfs_collate(icx->idx_ni->vol, icx->cr, key, key_len, &ie->key, 591 le16_to_cpu(ie->key_length)); 592 if (rc == -EINVAL) { 593 ntfs_error(icx->idx_ni->vol->sb, 594 "Collation error. Perhaps a filename contains invalid characters?\n"); 595 return -ERANGE; 596 } 597 /* 598 * If @key collates before the key of the current entry, there 599 * is definitely no such key in this index but we might need to 600 * descend into the B+tree so we just break out of the loop. 601 */ 602 if (rc == -1) 603 break; 604 605 if (!rc) { 606 *ie_out = ie; 607 icx->parent_pos[icx->pindex] = item; 608 return 0; 609 } 610 611 item++; 612 } 613 /* 614 * We have finished with this index block without success. Check for the 615 * presence of a child node and if not present return with errno ENOENT, 616 * otherwise we will keep searching in another index block. 617 */ 618 if (!(ie->flags & INDEX_ENTRY_NODE)) { 619 ntfs_debug("Index entry wasn't found.\n"); 620 *ie_out = ie; 621 return -ENOENT; 622 } 623 624 /* Get the starting vcn of the index_block holding the child node. */ 625 *vcn = ntfs_ie_get_vcn(ie); 626 if (*vcn < 0) { 627 ntfs_error(icx->idx_ni->vol->sb, "Negative vcn in inode %llu\n", 628 (unsigned long long)icx->idx_ni->mft_no); 629 return -EINVAL; 630 } 631 632 ntfs_debug("Parent entry number %d\n", item); 633 icx->parent_pos[icx->pindex] = item; 634 635 return -EAGAIN; 636 } 637 638 struct ntfs_inode *ntfs_ia_open(struct ntfs_index_context *icx, struct ntfs_inode *ni) 639 { 640 struct inode *ia_vi; 641 642 ia_vi = ntfs_index_iget(VFS_I(ni), icx->name, icx->name_len); 643 if (IS_ERR(ia_vi)) { 644 ntfs_error(icx->idx_ni->vol->sb, 645 "Failed to open index allocation of inode %llu", 646 (unsigned long long)ni->mft_no); 647 return NULL; 648 } 649 650 return NTFS_I(ia_vi); 651 } 652 653 static int ntfs_ib_read(struct ntfs_index_context *icx, s64 vcn, struct index_block *dst) 654 { 655 s64 pos, ret; 656 657 ntfs_debug("vcn: %lld\n", vcn); 658 659 pos = ntfs_ib_vcn_to_pos(icx, vcn); 660 661 ret = ntfs_inode_attr_pread(VFS_I(icx->ia_ni), pos, icx->block_size, (u8 *)dst); 662 if (ret != icx->block_size) { 663 if (ret == -1) 664 ntfs_error(icx->idx_ni->vol->sb, "Failed to read index block"); 665 else 666 ntfs_error(icx->idx_ni->vol->sb, 667 "Failed to read full index block at %lld\n", pos); 668 return -1; 669 } 670 671 post_read_mst_fixup((struct ntfs_record *)((u8 *)dst), icx->block_size); 672 if (ntfs_index_block_inconsistent(icx, dst, vcn)) 673 return -1; 674 675 return 0; 676 } 677 678 static int ntfs_icx_parent_inc(struct ntfs_index_context *icx) 679 { 680 icx->pindex++; 681 if (icx->pindex >= MAX_PARENT_VCN) { 682 ntfs_error(icx->idx_ni->vol->sb, "Index is over %d level deep", MAX_PARENT_VCN); 683 return -EOPNOTSUPP; 684 } 685 return 0; 686 } 687 688 static int ntfs_icx_parent_dec(struct ntfs_index_context *icx) 689 { 690 icx->pindex--; 691 if (icx->pindex < 0) { 692 ntfs_error(icx->idx_ni->vol->sb, "Corrupt index pointer (%d)", icx->pindex); 693 return -EINVAL; 694 } 695 return 0; 696 } 697 698 /* 699 * ntfs_index_lookup - find a key in an index and return its index entry 700 * @key: key for which to search in the index 701 * @key_len: length of @key in bytes 702 * @icx: context describing the index and the returned entry 703 * 704 * Before calling ntfs_index_lookup(), @icx must have been obtained from a 705 * call to ntfs_index_ctx_get(). 706 * 707 * Look for the @key in the index specified by the index lookup context @icx. 708 * ntfs_index_lookup() walks the contents of the index looking for the @key. 709 * 710 * If the @key is found in the index, 0 is returned and @icx is setup to 711 * describe the index entry containing the matching @key. @icx->entry is the 712 * index entry and @icx->data and @icx->data_len are the index entry data and 713 * its length in bytes, respectively. 714 * 715 * If the @key is not found in the index, -ENOENT is returned and 716 * @icx is setup to describe the index entry whose key collates immediately 717 * after the search @key, i.e. this is the position in the index at which 718 * an index entry with a key of @key would need to be inserted. 719 * 720 * When finished with the entry and its data, call ntfs_index_ctx_put() to free 721 * the context and other associated resources. 722 * 723 * If the index entry was modified, call ntfs_index_entry_mark_dirty() before 724 * the call to ntfs_index_ctx_put() to ensure that the changes are written 725 * to disk. 726 */ 727 int ntfs_index_lookup(const void *key, const u32 key_len, struct ntfs_index_context *icx) 728 { 729 s64 old_vcn, vcn; 730 struct ntfs_inode *ni = icx->idx_ni; 731 struct super_block *sb = ni->vol->sb; 732 struct index_root *ir; 733 struct index_entry *ie; 734 struct index_block *ib = NULL; 735 int err = 0; 736 737 ntfs_debug("Entering\n"); 738 739 if (!key) { 740 ntfs_error(sb, "key: %p key_len: %d", key, key_len); 741 return -EINVAL; 742 } 743 744 ir = ntfs_ir_lookup(ni, icx->name, icx->name_len, &icx->actx); 745 if (!ir) 746 return -EIO; 747 748 icx->block_size = le32_to_cpu(ir->index_block_size); 749 if (icx->block_size < NTFS_BLOCK_SIZE) { 750 err = -EINVAL; 751 ntfs_error(sb, 752 "Index block size (%d) is smaller than the sector size (%d)", 753 icx->block_size, NTFS_BLOCK_SIZE); 754 goto err_out; 755 } 756 757 if (ni->vol->cluster_size <= icx->block_size) 758 icx->vcn_size_bits = ni->vol->cluster_size_bits; 759 else 760 icx->vcn_size_bits = ni->vol->sector_size_bits; 761 762 icx->cr = ir->collation_rule; 763 if (!ntfs_is_collation_rule_supported(icx->cr)) { 764 err = -EOPNOTSUPP; 765 ntfs_error(sb, "Unknown collation rule 0x%x", 766 (unsigned int)le32_to_cpu(icx->cr)); 767 goto err_out; 768 } 769 770 old_vcn = VCN_INDEX_ROOT_PARENT; 771 err = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie); 772 if (err == -ERANGE || err == -EINVAL) 773 goto err_out; 774 775 icx->ir = ir; 776 if (err != -EAGAIN) { 777 icx->is_in_root = true; 778 icx->parent_vcn[icx->pindex] = old_vcn; 779 goto done; 780 } 781 782 /* Child node present, descend into it. */ 783 icx->ia_ni = ntfs_ia_open(icx, ni); 784 if (!icx->ia_ni) { 785 err = -ENOENT; 786 goto err_out; 787 } 788 789 ib = kvzalloc(icx->block_size, GFP_NOFS); 790 if (!ib) { 791 err = -ENOMEM; 792 goto err_out; 793 } 794 795 descend_into_child_node: 796 icx->parent_vcn[icx->pindex] = old_vcn; 797 if (ntfs_icx_parent_inc(icx)) { 798 err = -EIO; 799 goto err_out; 800 } 801 old_vcn = vcn; 802 803 ntfs_debug("Descend into node with s64 %lld.\n", vcn); 804 805 if (ntfs_ib_read(icx, vcn, ib)) { 806 err = -EIO; 807 goto err_out; 808 } 809 err = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie); 810 if (err != -EAGAIN) { 811 if (err == -EINVAL || err == -ERANGE) 812 goto err_out; 813 814 icx->is_in_root = false; 815 icx->ib = ib; 816 icx->parent_vcn[icx->pindex] = vcn; 817 goto done; 818 } 819 820 if ((ib->index.flags & NODE_MASK) == LEAF_NODE) { 821 ntfs_error(icx->idx_ni->vol->sb, 822 "Index entry with child node found in a leaf node in inode 0x%llx.\n", 823 (unsigned long long)ni->mft_no); 824 goto err_out; 825 } 826 827 goto descend_into_child_node; 828 err_out: 829 if (icx->actx) { 830 ntfs_attr_put_search_ctx(icx->actx); 831 icx->actx = NULL; 832 } 833 kvfree(ib); 834 if (!err) 835 err = -EIO; 836 return err; 837 done: 838 icx->entry = ie; 839 icx->data = (u8 *)ie + offsetof(struct index_entry, key); 840 icx->data_len = le16_to_cpu(ie->key_length); 841 ntfs_debug("Done.\n"); 842 return err; 843 844 } 845 846 static struct index_block *ntfs_ib_alloc(s64 ib_vcn, u32 ib_size, 847 u8 node_type) 848 { 849 struct index_block *ib; 850 int ih_size = sizeof(struct index_header); 851 852 ntfs_debug("Entering ib_vcn = %lld ib_size = %u\n", ib_vcn, ib_size); 853 854 ib = kvzalloc(ib_size, GFP_NOFS); 855 if (!ib) 856 return NULL; 857 858 ib->magic = magic_INDX; 859 ib->usa_ofs = cpu_to_le16(sizeof(struct index_block)); 860 ib->usa_count = cpu_to_le16(ib_size / NTFS_BLOCK_SIZE + 1); 861 /* Set USN to 1 */ 862 *(__le16 *)((char *)ib + le16_to_cpu(ib->usa_ofs)) = cpu_to_le16(1); 863 ib->lsn = 0; 864 ib->index_block_vcn = cpu_to_le64(ib_vcn); 865 ib->index.entries_offset = cpu_to_le32((ih_size + 866 le16_to_cpu(ib->usa_count) * 2 + 7) & ~7); 867 ib->index.index_length = 0; 868 ib->index.allocated_size = cpu_to_le32(ib_size - 869 (sizeof(struct index_block) - ih_size)); 870 ib->index.flags = node_type; 871 872 return ib; 873 } 874 875 /* 876 * Find the median by going through all the entries 877 */ 878 static struct index_entry *ntfs_ie_get_median(struct index_header *ih) 879 { 880 struct index_entry *ie, *ie_start; 881 u8 *ie_end; 882 int i = 0, median; 883 884 ntfs_debug("Entering\n"); 885 886 ie = ie_start = ntfs_ie_get_first(ih); 887 ie_end = (u8 *)ntfs_ie_get_end(ih); 888 889 while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) { 890 ie = ntfs_ie_get_next(ie); 891 i++; 892 } 893 /* 894 * NOTE: this could be also the entry at the half of the index block. 895 */ 896 median = i / 2 - 1; 897 898 ntfs_debug("Entries: %d median: %d\n", i, median); 899 900 for (i = 0, ie = ie_start; i <= median; i++) 901 ie = ntfs_ie_get_next(ie); 902 903 return ie; 904 } 905 906 static u64 ntfs_ibm_vcn_to_pos(struct ntfs_index_context *icx, s64 vcn) 907 { 908 u64 pos = ntfs_ib_vcn_to_pos(icx, vcn); 909 910 do_div(pos, icx->block_size); 911 return pos; 912 } 913 914 static s64 ntfs_ibm_pos_to_vcn(struct ntfs_index_context *icx, s64 pos) 915 { 916 return ntfs_ib_pos_to_vcn(icx, pos * icx->block_size); 917 } 918 919 static int ntfs_ibm_add(struct ntfs_index_context *icx) 920 { 921 u8 bmp[8]; 922 923 ntfs_debug("Entering\n"); 924 925 if (ntfs_attr_exist(icx->idx_ni, AT_BITMAP, icx->name, icx->name_len)) 926 return 0; 927 /* 928 * AT_BITMAP must be at least 8 bytes. 929 */ 930 memset(bmp, 0, sizeof(bmp)); 931 if (ntfs_attr_add(icx->idx_ni, AT_BITMAP, icx->name, icx->name_len, 932 bmp, sizeof(bmp))) { 933 ntfs_error(icx->idx_ni->vol->sb, "Failed to add AT_BITMAP"); 934 return -EINVAL; 935 } 936 937 return 0; 938 } 939 940 static int ntfs_ibm_modify(struct ntfs_index_context *icx, s64 vcn, int set) 941 { 942 u8 byte; 943 u64 pos = ntfs_ibm_vcn_to_pos(icx, vcn); 944 u32 bpos = pos / 8; 945 u32 bit = 1 << (pos % 8); 946 struct ntfs_inode *bmp_ni; 947 struct inode *bmp_vi; 948 int ret = 0; 949 950 ntfs_debug("%s vcn: %lld\n", set ? "set" : "clear", vcn); 951 952 bmp_vi = ntfs_attr_iget(VFS_I(icx->idx_ni), AT_BITMAP, icx->name, icx->name_len); 953 if (IS_ERR(bmp_vi)) { 954 ntfs_error(icx->idx_ni->vol->sb, "Failed to open $BITMAP attribute"); 955 return PTR_ERR(bmp_vi); 956 } 957 958 bmp_ni = NTFS_I(bmp_vi); 959 960 if (set) { 961 if (bmp_ni->data_size < bpos + 1) { 962 ret = ntfs_attr_truncate(bmp_ni, (bmp_ni->data_size + 8) & ~7); 963 if (ret) { 964 ntfs_error(icx->idx_ni->vol->sb, "Failed to truncate AT_BITMAP"); 965 goto err; 966 } 967 i_size_write(bmp_vi, (loff_t)bmp_ni->data_size); 968 } 969 } 970 971 if (ntfs_inode_attr_pread(bmp_vi, bpos, 1, &byte) != 1) { 972 ret = -EIO; 973 ntfs_error(icx->idx_ni->vol->sb, "Failed to read $BITMAP"); 974 goto err; 975 } 976 977 if (set) 978 byte |= bit; 979 else 980 byte &= ~bit; 981 982 if (ntfs_inode_attr_pwrite(bmp_vi, bpos, 1, &byte, false) != 1) { 983 ret = -EIO; 984 ntfs_error(icx->idx_ni->vol->sb, "Failed to write $Bitmap"); 985 goto err; 986 } 987 988 err: 989 iput(bmp_vi); 990 return ret; 991 } 992 993 static int ntfs_ibm_set(struct ntfs_index_context *icx, s64 vcn) 994 { 995 return ntfs_ibm_modify(icx, vcn, 1); 996 } 997 998 static int ntfs_ibm_clear(struct ntfs_index_context *icx, s64 vcn) 999 { 1000 return ntfs_ibm_modify(icx, vcn, 0); 1001 } 1002 1003 static s64 ntfs_ibm_get_free(struct ntfs_index_context *icx) 1004 { 1005 u8 *bm; 1006 int bit; 1007 s64 vcn, byte, size; 1008 1009 ntfs_debug("Entering\n"); 1010 1011 bm = ntfs_attr_readall(icx->idx_ni, AT_BITMAP, icx->name, icx->name_len, 1012 &size); 1013 if (!bm) 1014 return (s64)-1; 1015 1016 for (byte = 0; byte < size; byte++) { 1017 if (bm[byte] == 255) 1018 continue; 1019 1020 for (bit = 0; bit < 8; bit++) { 1021 if (!(bm[byte] & (1 << bit))) { 1022 vcn = ntfs_ibm_pos_to_vcn(icx, byte * 8 + bit); 1023 goto out; 1024 } 1025 } 1026 } 1027 1028 vcn = ntfs_ibm_pos_to_vcn(icx, size * 8); 1029 out: 1030 ntfs_debug("allocated vcn: %lld\n", vcn); 1031 1032 if (ntfs_ibm_set(icx, vcn)) 1033 vcn = (s64)-1; 1034 1035 kvfree(bm); 1036 return vcn; 1037 } 1038 1039 static struct index_block *ntfs_ir_to_ib(struct index_root *ir, s64 ib_vcn) 1040 { 1041 struct index_block *ib; 1042 struct index_entry *ie_last; 1043 char *ies_start, *ies_end; 1044 int i; 1045 1046 ntfs_debug("Entering\n"); 1047 1048 ib = ntfs_ib_alloc(ib_vcn, le32_to_cpu(ir->index_block_size), LEAF_NODE); 1049 if (!ib) 1050 return NULL; 1051 1052 ies_start = (char *)ntfs_ie_get_first(&ir->index); 1053 ies_end = (char *)ntfs_ie_get_end(&ir->index); 1054 ie_last = ntfs_ie_get_last((struct index_entry *)ies_start, ies_end); 1055 /* 1056 * Copy all entries, including the termination entry 1057 * as well, which can never have any data. 1058 */ 1059 i = (char *)ie_last - ies_start + le16_to_cpu(ie_last->length); 1060 memcpy(ntfs_ie_get_first(&ib->index), ies_start, i); 1061 1062 ib->index.flags = ir->index.flags; 1063 ib->index.index_length = cpu_to_le32(i + 1064 le32_to_cpu(ib->index.entries_offset)); 1065 return ib; 1066 } 1067 1068 static void ntfs_ir_nill(struct index_root *ir) 1069 { 1070 struct index_entry *ie_last; 1071 char *ies_start, *ies_end; 1072 1073 ntfs_debug("Entering\n"); 1074 1075 ies_start = (char *)ntfs_ie_get_first(&ir->index); 1076 ies_end = (char *)ntfs_ie_get_end(&ir->index); 1077 ie_last = ntfs_ie_get_last((struct index_entry *)ies_start, ies_end); 1078 /* 1079 * Move the index root termination entry forward 1080 */ 1081 if ((char *)ie_last > ies_start) { 1082 memmove((char *)ntfs_ie_get_first(&ir->index), 1083 (char *)ie_last, le16_to_cpu(ie_last->length)); 1084 ie_last = (struct index_entry *)ies_start; 1085 } 1086 } 1087 1088 static int ntfs_ib_copy_tail(struct ntfs_index_context *icx, struct index_block *src, 1089 struct index_entry *median, s64 new_vcn) 1090 { 1091 u8 *ies_end; 1092 struct index_entry *ie_head; /* first entry after the median */ 1093 int tail_size, ret; 1094 struct index_block *dst; 1095 1096 ntfs_debug("Entering\n"); 1097 1098 dst = ntfs_ib_alloc(new_vcn, icx->block_size, 1099 src->index.flags & NODE_MASK); 1100 if (!dst) 1101 return -ENOMEM; 1102 1103 ie_head = ntfs_ie_get_next(median); 1104 1105 ies_end = (u8 *)ntfs_ie_get_end(&src->index); 1106 tail_size = ies_end - (u8 *)ie_head; 1107 memcpy(ntfs_ie_get_first(&dst->index), ie_head, tail_size); 1108 1109 dst->index.index_length = cpu_to_le32(tail_size + 1110 le32_to_cpu(dst->index.entries_offset)); 1111 ret = ntfs_ib_write(icx, dst); 1112 1113 kvfree(dst); 1114 return ret; 1115 } 1116 1117 static int ntfs_ib_cut_tail(struct ntfs_index_context *icx, struct index_block *ib, 1118 struct index_entry *ie) 1119 { 1120 char *ies_start, *ies_end; 1121 struct index_entry *ie_last; 1122 int ret; 1123 1124 ntfs_debug("Entering\n"); 1125 1126 ies_start = (char *)ntfs_ie_get_first(&ib->index); 1127 ies_end = (char *)ntfs_ie_get_end(&ib->index); 1128 1129 ie_last = ntfs_ie_get_last((struct index_entry *)ies_start, ies_end); 1130 if (ie_last->flags & INDEX_ENTRY_NODE) 1131 ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie)); 1132 1133 unsafe_memcpy(ie, ie_last, le16_to_cpu(ie_last->length), 1134 /* alloc is larger than ie_last->length, see ntfs_ie_get_last() */); 1135 1136 ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) + 1137 le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset)); 1138 1139 ret = ntfs_ib_write(icx, ib); 1140 return ret; 1141 } 1142 1143 static int ntfs_ia_add(struct ntfs_index_context *icx) 1144 { 1145 int ret; 1146 1147 ntfs_debug("Entering\n"); 1148 1149 ret = ntfs_ibm_add(icx); 1150 if (ret) 1151 return ret; 1152 1153 if (!ntfs_attr_exist(icx->idx_ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) { 1154 ret = ntfs_attr_add(icx->idx_ni, AT_INDEX_ALLOCATION, icx->name, 1155 icx->name_len, NULL, 0); 1156 if (ret) { 1157 ntfs_error(icx->idx_ni->vol->sb, "Failed to add AT_INDEX_ALLOCATION"); 1158 return ret; 1159 } 1160 } 1161 1162 icx->ia_ni = ntfs_ia_open(icx, icx->idx_ni); 1163 if (!icx->ia_ni) 1164 return -ENOENT; 1165 1166 return 0; 1167 } 1168 1169 static int ntfs_ir_reparent(struct ntfs_index_context *icx) 1170 { 1171 struct ntfs_attr_search_ctx *ctx = NULL; 1172 struct index_root *ir; 1173 struct index_entry *ie; 1174 struct index_block *ib = NULL; 1175 s64 new_ib_vcn; 1176 int ix_root_size; 1177 int ret = 0; 1178 1179 ntfs_debug("Entering\n"); 1180 1181 ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len); 1182 if (!ir) { 1183 ret = -ENOENT; 1184 goto out; 1185 } 1186 1187 if ((ir->index.flags & NODE_MASK) == SMALL_INDEX) { 1188 ret = ntfs_ia_add(icx); 1189 if (ret) 1190 goto out; 1191 } 1192 1193 new_ib_vcn = ntfs_ibm_get_free(icx); 1194 if (new_ib_vcn < 0) { 1195 ret = -EINVAL; 1196 goto out; 1197 } 1198 1199 ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len); 1200 if (!ir) { 1201 ret = -ENOENT; 1202 goto clear_bmp; 1203 } 1204 1205 ib = ntfs_ir_to_ib(ir, new_ib_vcn); 1206 if (ib == NULL) { 1207 ret = -EIO; 1208 ntfs_error(icx->idx_ni->vol->sb, "Failed to move index root to index block"); 1209 goto clear_bmp; 1210 } 1211 1212 ret = ntfs_ib_write(icx, ib); 1213 if (ret) 1214 goto clear_bmp; 1215 1216 retry: 1217 ir = ntfs_ir_lookup(icx->idx_ni, icx->name, icx->name_len, &ctx); 1218 if (!ir) { 1219 ret = -ENOENT; 1220 goto clear_bmp; 1221 } 1222 1223 ntfs_ir_nill(ir); 1224 1225 ie = ntfs_ie_get_first(&ir->index); 1226 ie->flags |= INDEX_ENTRY_NODE; 1227 ie->length = cpu_to_le16(sizeof(struct index_entry_header) + sizeof(s64)); 1228 1229 ir->index.flags = LARGE_INDEX; 1230 NInoSetIndexAllocPresent(icx->idx_ni); 1231 ir->index.index_length = cpu_to_le32(le32_to_cpu(ir->index.entries_offset) + 1232 le16_to_cpu(ie->length)); 1233 ir->index.allocated_size = ir->index.index_length; 1234 1235 ix_root_size = sizeof(struct index_root) - sizeof(struct index_header) + 1236 le32_to_cpu(ir->index.allocated_size); 1237 ret = ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr, ix_root_size); 1238 if (ret) { 1239 /* 1240 * When there is no space to build a non-resident 1241 * index, we may have to move the root to an extent 1242 */ 1243 if ((ret == -ENOSPC) && (ctx->al_entry || !ntfs_inode_add_attrlist(icx->idx_ni))) { 1244 ntfs_attr_put_search_ctx(ctx); 1245 ctx = NULL; 1246 ir = ntfs_ir_lookup(icx->idx_ni, icx->name, icx->name_len, &ctx); 1247 if (ir && !ntfs_attr_record_move_away(ctx, ix_root_size - 1248 le32_to_cpu(ctx->attr->data.resident.value_length))) { 1249 if (ntfs_attrlist_update(ctx->base_ntfs_ino ? 1250 ctx->base_ntfs_ino : ctx->ntfs_ino)) 1251 goto clear_bmp; 1252 ntfs_attr_put_search_ctx(ctx); 1253 ctx = NULL; 1254 goto retry; 1255 } 1256 } 1257 goto clear_bmp; 1258 } else { 1259 icx->idx_ni->data_size = icx->idx_ni->initialized_size = ix_root_size; 1260 icx->idx_ni->allocated_size = (ix_root_size + 7) & ~7; 1261 } 1262 ntfs_ie_set_vcn(ie, new_ib_vcn); 1263 1264 err_out: 1265 kvfree(ib); 1266 if (ctx) 1267 ntfs_attr_put_search_ctx(ctx); 1268 out: 1269 return ret; 1270 clear_bmp: 1271 ntfs_ibm_clear(icx, new_ib_vcn); 1272 goto err_out; 1273 } 1274 1275 /* 1276 * ntfs_ir_truncate - Truncate index root attribute 1277 * @icx: index context 1278 * @data_size: new data size for the index root 1279 */ 1280 static int ntfs_ir_truncate(struct ntfs_index_context *icx, int data_size) 1281 { 1282 int ret; 1283 1284 ntfs_debug("Entering\n"); 1285 1286 /* 1287 * INDEX_ROOT must be resident and its entries can be moved to 1288 * struct index_block, so ENOSPC isn't a real error. 1289 */ 1290 ret = ntfs_attr_truncate(icx->idx_ni, data_size + offsetof(struct index_root, index)); 1291 if (!ret) { 1292 i_size_write(VFS_I(icx->idx_ni), icx->idx_ni->initialized_size); 1293 icx->ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len); 1294 if (!icx->ir) 1295 return -ENOENT; 1296 1297 icx->ir->index.allocated_size = cpu_to_le32(data_size); 1298 } else if (ret != -ENOSPC) 1299 ntfs_error(icx->idx_ni->vol->sb, "Failed to truncate INDEX_ROOT"); 1300 1301 return ret; 1302 } 1303 1304 /* 1305 * ntfs_ir_make_space - Make more space for the index root attribute 1306 * @icx: index context 1307 * @data_size: required data size for the index root 1308 */ 1309 static int ntfs_ir_make_space(struct ntfs_index_context *icx, int data_size) 1310 { 1311 int ret; 1312 1313 ntfs_debug("Entering\n"); 1314 1315 ret = ntfs_ir_truncate(icx, data_size); 1316 if (ret == -ENOSPC) { 1317 ret = ntfs_ir_reparent(icx); 1318 if (!ret) 1319 ret = -EAGAIN; 1320 else 1321 ntfs_error(icx->idx_ni->vol->sb, "Failed to modify INDEX_ROOT"); 1322 } 1323 1324 return ret; 1325 } 1326 1327 /* 1328 * NOTE: 'ie' must be a copy of a real index entry. 1329 */ 1330 static int ntfs_ie_add_vcn(struct index_entry **ie) 1331 { 1332 struct index_entry *p, *old = *ie; 1333 1334 old->length = cpu_to_le16(le16_to_cpu(old->length) + sizeof(s64)); 1335 p = krealloc(old, le16_to_cpu(old->length), GFP_NOFS); 1336 if (!p) 1337 return -ENOMEM; 1338 1339 p->flags |= INDEX_ENTRY_NODE; 1340 *ie = p; 1341 return 0; 1342 } 1343 1344 static int ntfs_ih_insert(struct index_header *ih, struct index_entry *orig_ie, s64 new_vcn, 1345 int pos) 1346 { 1347 struct index_entry *ie_node, *ie; 1348 int ret = 0; 1349 s64 old_vcn; 1350 1351 ntfs_debug("Entering\n"); 1352 ie = ntfs_ie_dup(orig_ie); 1353 if (!ie) 1354 return -ENOMEM; 1355 1356 if (!(ie->flags & INDEX_ENTRY_NODE)) { 1357 ret = ntfs_ie_add_vcn(&ie); 1358 if (ret) 1359 goto out; 1360 } 1361 1362 ie_node = ntfs_ie_get_by_pos(ih, pos); 1363 old_vcn = ntfs_ie_get_vcn(ie_node); 1364 ntfs_ie_set_vcn(ie_node, new_vcn); 1365 1366 ntfs_ie_insert(ih, ie, ie_node); 1367 ntfs_ie_set_vcn(ie_node, old_vcn); 1368 out: 1369 kfree(ie); 1370 return ret; 1371 } 1372 1373 static s64 ntfs_icx_parent_vcn(struct ntfs_index_context *icx) 1374 { 1375 return icx->parent_vcn[icx->pindex]; 1376 } 1377 1378 static s64 ntfs_icx_parent_pos(struct ntfs_index_context *icx) 1379 { 1380 return icx->parent_pos[icx->pindex]; 1381 } 1382 1383 static int ntfs_ir_insert_median(struct ntfs_index_context *icx, struct index_entry *median, 1384 s64 new_vcn) 1385 { 1386 u32 new_size; 1387 int ret; 1388 1389 ntfs_debug("Entering\n"); 1390 1391 icx->ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len); 1392 if (!icx->ir) 1393 return -ENOENT; 1394 1395 new_size = le32_to_cpu(icx->ir->index.index_length) + 1396 le16_to_cpu(median->length); 1397 if (!(median->flags & INDEX_ENTRY_NODE)) 1398 new_size += sizeof(s64); 1399 1400 ret = ntfs_ir_make_space(icx, new_size); 1401 if (ret) 1402 return ret; 1403 1404 icx->ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len); 1405 if (!icx->ir) 1406 return -ENOENT; 1407 1408 return ntfs_ih_insert(&icx->ir->index, median, new_vcn, 1409 ntfs_icx_parent_pos(icx)); 1410 } 1411 1412 static int ntfs_ib_split(struct ntfs_index_context *icx, struct index_block *ib); 1413 1414 struct split_info { 1415 struct list_head entry; 1416 s64 new_vcn; 1417 struct index_block *ib; 1418 }; 1419 1420 static int ntfs_ib_insert(struct ntfs_index_context *icx, struct index_entry *ie, s64 new_vcn, 1421 struct split_info *si) 1422 { 1423 struct index_block *ib; 1424 u32 idx_size, allocated_size; 1425 int err; 1426 s64 old_vcn; 1427 1428 ntfs_debug("Entering\n"); 1429 1430 ib = kvzalloc(icx->block_size, GFP_NOFS); 1431 if (!ib) 1432 return -ENOMEM; 1433 1434 old_vcn = ntfs_icx_parent_vcn(icx); 1435 1436 err = ntfs_ib_read(icx, old_vcn, ib); 1437 if (err) 1438 goto err_out; 1439 1440 idx_size = le32_to_cpu(ib->index.index_length); 1441 allocated_size = le32_to_cpu(ib->index.allocated_size); 1442 if (idx_size + le16_to_cpu(ie->length) + sizeof(s64) > allocated_size) { 1443 si->ib = ib; 1444 si->new_vcn = new_vcn; 1445 return -EAGAIN; 1446 } 1447 1448 err = ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)); 1449 if (err) 1450 goto err_out; 1451 1452 err = ntfs_ib_write(icx, ib); 1453 1454 err_out: 1455 kvfree(ib); 1456 return err; 1457 } 1458 1459 /* 1460 * ntfs_ib_split - Split an index block 1461 * @icx: index context 1462 * @ib: index block to split 1463 */ 1464 static int ntfs_ib_split(struct ntfs_index_context *icx, struct index_block *ib) 1465 { 1466 struct index_entry *median; 1467 s64 new_vcn; 1468 int ret; 1469 struct split_info *si; 1470 LIST_HEAD(ntfs_cut_tail_list); 1471 1472 ntfs_debug("Entering\n"); 1473 1474 resplit: 1475 ret = ntfs_icx_parent_dec(icx); 1476 if (ret) 1477 goto out; 1478 1479 median = ntfs_ie_get_median(&ib->index); 1480 new_vcn = ntfs_ibm_get_free(icx); 1481 if (new_vcn < 0) { 1482 ret = -EINVAL; 1483 goto out; 1484 } 1485 1486 ret = ntfs_ib_copy_tail(icx, ib, median, new_vcn); 1487 if (ret) { 1488 ntfs_ibm_clear(icx, new_vcn); 1489 goto out; 1490 } 1491 1492 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) { 1493 ret = ntfs_ir_insert_median(icx, median, new_vcn); 1494 if (ret) { 1495 ntfs_ibm_clear(icx, new_vcn); 1496 goto out; 1497 } 1498 } else { 1499 si = kzalloc(sizeof(struct split_info), GFP_NOFS); 1500 if (!si) { 1501 ntfs_ibm_clear(icx, new_vcn); 1502 ret = -ENOMEM; 1503 goto out; 1504 } 1505 1506 ret = ntfs_ib_insert(icx, median, new_vcn, si); 1507 if (ret == -EAGAIN) { 1508 list_add_tail(&si->entry, &ntfs_cut_tail_list); 1509 ib = si->ib; 1510 goto resplit; 1511 } else if (ret) { 1512 kvfree(si->ib); 1513 kfree(si); 1514 ntfs_ibm_clear(icx, new_vcn); 1515 goto out; 1516 } 1517 kfree(si); 1518 } 1519 1520 ret = ntfs_ib_cut_tail(icx, ib, median); 1521 1522 out: 1523 while (!list_empty(&ntfs_cut_tail_list)) { 1524 si = list_last_entry(&ntfs_cut_tail_list, struct split_info, entry); 1525 ntfs_ibm_clear(icx, si->new_vcn); 1526 kvfree(si->ib); 1527 list_del(&si->entry); 1528 kfree(si); 1529 if (!ret) 1530 ret = -EAGAIN; 1531 } 1532 1533 return ret; 1534 } 1535 1536 int ntfs_ie_add(struct ntfs_index_context *icx, struct index_entry *ie) 1537 { 1538 struct index_header *ih; 1539 int allocated_size, new_size; 1540 int ret; 1541 1542 while (1) { 1543 ret = ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx); 1544 if (!ret) { 1545 ret = -EEXIST; 1546 ntfs_error(icx->idx_ni->vol->sb, "Index already have such entry"); 1547 goto err_out; 1548 } 1549 if (ret != -ENOENT) { 1550 ntfs_error(icx->idx_ni->vol->sb, "Failed to find place for new entry"); 1551 goto err_out; 1552 } 1553 ret = 0; 1554 1555 if (icx->is_in_root) 1556 ih = &icx->ir->index; 1557 else 1558 ih = &icx->ib->index; 1559 1560 allocated_size = le32_to_cpu(ih->allocated_size); 1561 new_size = le32_to_cpu(ih->index_length) + le16_to_cpu(ie->length); 1562 1563 if (new_size <= allocated_size) 1564 break; 1565 1566 ntfs_debug("index block sizes: allocated: %d needed: %d\n", 1567 allocated_size, new_size); 1568 1569 if (icx->is_in_root) 1570 ret = ntfs_ir_make_space(icx, new_size); 1571 else 1572 ret = ntfs_ib_split(icx, icx->ib); 1573 if (ret && ret != -EAGAIN) 1574 goto err_out; 1575 1576 mark_mft_record_dirty(icx->actx->ntfs_ino); 1577 ntfs_index_ctx_reinit(icx); 1578 } 1579 1580 ntfs_ie_insert(ih, ie, icx->entry); 1581 ntfs_index_entry_mark_dirty(icx); 1582 1583 err_out: 1584 ntfs_debug("%s\n", ret ? "Failed" : "Done"); 1585 return ret; 1586 } 1587 1588 /* 1589 * ntfs_index_add_filename - add filename to directory index 1590 * @ni: ntfs inode describing directory to which index add filename 1591 * @fn: FILE_NAME attribute to add 1592 * @mref: reference of the inode which @fn describes 1593 */ 1594 int ntfs_index_add_filename(struct ntfs_inode *ni, struct file_name_attr *fn, u64 mref) 1595 { 1596 struct index_entry *ie; 1597 struct ntfs_index_context *icx; 1598 int fn_size, ie_size, err; 1599 1600 ntfs_debug("Entering\n"); 1601 1602 if (!ni || !fn) 1603 return -EINVAL; 1604 1605 fn_size = (fn->file_name_length * sizeof(__le16)) + 1606 sizeof(struct file_name_attr); 1607 ie_size = (sizeof(struct index_entry_header) + fn_size + 7) & ~7; 1608 1609 ie = kzalloc(ie_size, GFP_NOFS); 1610 if (!ie) 1611 return -ENOMEM; 1612 1613 ie->data.dir.indexed_file = cpu_to_le64(mref); 1614 ie->length = cpu_to_le16(ie_size); 1615 ie->key_length = cpu_to_le16(fn_size); 1616 1617 unsafe_memcpy(&ie->key, fn, fn_size, 1618 /* "fn_size" was correctly calculated above */); 1619 1620 icx = ntfs_index_ctx_get(ni, I30, 4); 1621 if (!icx) { 1622 err = -ENOMEM; 1623 goto out; 1624 } 1625 1626 err = ntfs_ie_add(icx, ie); 1627 ntfs_index_ctx_put(icx); 1628 out: 1629 kfree(ie); 1630 return err; 1631 } 1632 1633 static int ntfs_ih_takeout(struct ntfs_index_context *icx, struct index_header *ih, 1634 struct index_entry *ie, struct index_block *ib) 1635 { 1636 struct index_entry *ie_roam; 1637 int freed_space; 1638 bool full; 1639 int ret = 0; 1640 1641 ntfs_debug("Entering\n"); 1642 1643 full = ih->index_length == ih->allocated_size; 1644 ie_roam = ntfs_ie_dup_novcn(ie); 1645 if (!ie_roam) 1646 return -ENOMEM; 1647 1648 ntfs_ie_delete(ih, ie); 1649 1650 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) { 1651 /* 1652 * Recover the space which may have been freed 1653 * while deleting an entry from root index 1654 */ 1655 freed_space = le32_to_cpu(ih->allocated_size) - 1656 le32_to_cpu(ih->index_length); 1657 if (full && (freed_space > 0) && !(freed_space & 7)) { 1658 ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length)); 1659 /* do nothing if truncation fails */ 1660 } 1661 1662 mark_mft_record_dirty(icx->actx->ntfs_ino); 1663 } else { 1664 ret = ntfs_ib_write(icx, ib); 1665 if (ret) 1666 goto out; 1667 } 1668 1669 ntfs_index_ctx_reinit(icx); 1670 1671 ret = ntfs_ie_add(icx, ie_roam); 1672 out: 1673 kfree(ie_roam); 1674 return ret; 1675 } 1676 1677 /* 1678 * Used if an empty index block to be deleted has END entry as the parent 1679 * in the INDEX_ROOT which is the only one there. 1680 */ 1681 static void ntfs_ir_leafify(struct ntfs_index_context *icx, struct index_header *ih) 1682 { 1683 struct index_entry *ie; 1684 1685 ntfs_debug("Entering\n"); 1686 1687 ie = ntfs_ie_get_first(ih); 1688 ie->flags &= ~INDEX_ENTRY_NODE; 1689 ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(s64)); 1690 1691 ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) - sizeof(s64)); 1692 ih->flags &= ~LARGE_INDEX; 1693 NInoClearIndexAllocPresent(icx->idx_ni); 1694 1695 /* Not fatal error */ 1696 ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length)); 1697 } 1698 1699 /* 1700 * Used if an empty index block to be deleted has END entry as the parent 1701 * in the INDEX_ROOT which is not the only one there. 1702 */ 1703 static int ntfs_ih_reparent_end(struct ntfs_index_context *icx, struct index_header *ih, 1704 struct index_block *ib) 1705 { 1706 struct index_entry *ie, *ie_prev; 1707 1708 ntfs_debug("Entering\n"); 1709 1710 ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx)); 1711 ie_prev = ntfs_ie_prev(ih, ie); 1712 if (!ie_prev) 1713 return -EIO; 1714 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(ie_prev)); 1715 1716 return ntfs_ih_takeout(icx, ih, ie_prev, ib); 1717 } 1718 1719 static int ntfs_index_rm_leaf(struct ntfs_index_context *icx) 1720 { 1721 struct index_block *ib = NULL; 1722 struct index_header *parent_ih; 1723 struct index_entry *ie; 1724 int ret; 1725 1726 ntfs_debug("pindex: %d\n", icx->pindex); 1727 1728 ret = ntfs_icx_parent_dec(icx); 1729 if (ret) 1730 return ret; 1731 1732 ret = ntfs_ibm_clear(icx, icx->parent_vcn[icx->pindex + 1]); 1733 if (ret) 1734 return ret; 1735 1736 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) 1737 parent_ih = &icx->ir->index; 1738 else { 1739 ib = kvzalloc(icx->block_size, GFP_NOFS); 1740 if (!ib) 1741 return -ENOMEM; 1742 1743 ret = ntfs_ib_read(icx, ntfs_icx_parent_vcn(icx), ib); 1744 if (ret) 1745 goto out; 1746 1747 parent_ih = &ib->index; 1748 } 1749 1750 ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx)); 1751 if (!ntfs_ie_end(ie)) { 1752 ret = ntfs_ih_takeout(icx, parent_ih, ie, ib); 1753 goto out; 1754 } 1755 1756 if (ntfs_ih_zero_entry(parent_ih)) { 1757 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) { 1758 ntfs_ir_leafify(icx, parent_ih); 1759 goto out; 1760 } 1761 1762 ret = ntfs_index_rm_leaf(icx); 1763 goto out; 1764 } 1765 1766 ret = ntfs_ih_reparent_end(icx, parent_ih, ib); 1767 out: 1768 kvfree(ib); 1769 return ret; 1770 } 1771 1772 static int ntfs_index_rm_node(struct ntfs_index_context *icx) 1773 { 1774 int entry_pos, pindex; 1775 s64 vcn; 1776 struct index_block *ib = NULL; 1777 struct index_entry *ie_succ, *ie, *entry = icx->entry; 1778 struct index_header *ih; 1779 u32 new_size; 1780 int delta, ret; 1781 1782 ntfs_debug("Entering\n"); 1783 1784 if (!icx->ia_ni) { 1785 icx->ia_ni = ntfs_ia_open(icx, icx->idx_ni); 1786 if (!icx->ia_ni) 1787 return -EINVAL; 1788 } 1789 1790 ib = kvzalloc(icx->block_size, GFP_NOFS); 1791 if (!ib) 1792 return -ENOMEM; 1793 1794 ie_succ = ntfs_ie_get_next(icx->entry); 1795 entry_pos = icx->parent_pos[icx->pindex]++; 1796 pindex = icx->pindex; 1797 descend: 1798 vcn = ntfs_ie_get_vcn(ie_succ); 1799 ret = ntfs_ib_read(icx, vcn, ib); 1800 if (ret) 1801 goto out; 1802 1803 ie_succ = ntfs_ie_get_first(&ib->index); 1804 1805 ret = ntfs_icx_parent_inc(icx); 1806 if (ret) 1807 goto out; 1808 1809 icx->parent_vcn[icx->pindex] = vcn; 1810 icx->parent_pos[icx->pindex] = 0; 1811 1812 if ((ib->index.flags & NODE_MASK) == INDEX_NODE) 1813 goto descend; 1814 1815 if (ntfs_ih_zero_entry(&ib->index)) { 1816 ret = -EIO; 1817 ntfs_error(icx->idx_ni->vol->sb, "Empty index block"); 1818 goto out; 1819 } 1820 1821 ie = ntfs_ie_dup(ie_succ); 1822 if (!ie) { 1823 ret = -ENOMEM; 1824 goto out; 1825 } 1826 1827 ret = ntfs_ie_add_vcn(&ie); 1828 if (ret) 1829 goto out2; 1830 1831 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry)); 1832 1833 if (icx->is_in_root) 1834 ih = &icx->ir->index; 1835 else 1836 ih = &icx->ib->index; 1837 1838 delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length); 1839 new_size = le32_to_cpu(ih->index_length) + delta; 1840 if (delta > 0) { 1841 if (icx->is_in_root) { 1842 ret = ntfs_ir_make_space(icx, new_size); 1843 if (ret != 0) 1844 goto out2; 1845 1846 ih = &icx->ir->index; 1847 entry = ntfs_ie_get_by_pos(ih, entry_pos); 1848 1849 } else if (new_size > le32_to_cpu(ih->allocated_size)) { 1850 icx->pindex = pindex; 1851 ret = ntfs_ib_split(icx, icx->ib); 1852 if (!ret) 1853 ret = -EAGAIN; 1854 goto out2; 1855 } 1856 } 1857 1858 ntfs_ie_delete(ih, entry); 1859 ntfs_ie_insert(ih, ie, entry); 1860 1861 if (icx->is_in_root) 1862 ret = ntfs_ir_truncate(icx, new_size); 1863 else 1864 ret = ntfs_icx_ib_write(icx); 1865 if (ret) 1866 goto out2; 1867 1868 ntfs_ie_delete(&ib->index, ie_succ); 1869 1870 if (ntfs_ih_zero_entry(&ib->index)) 1871 ret = ntfs_index_rm_leaf(icx); 1872 else 1873 ret = ntfs_ib_write(icx, ib); 1874 1875 out2: 1876 kfree(ie); 1877 out: 1878 kvfree(ib); 1879 return ret; 1880 } 1881 1882 /* 1883 * ntfs_index_rm - remove entry from the index 1884 * @icx: index context describing entry to delete 1885 * 1886 * Delete entry described by @icx from the index. Index context is always 1887 * reinitialized after use of this function, so it can be used for index 1888 * lookup once again. 1889 */ 1890 int ntfs_index_rm(struct ntfs_index_context *icx) 1891 { 1892 struct index_header *ih; 1893 int ret = 0; 1894 1895 ntfs_debug("Entering\n"); 1896 1897 if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) { 1898 ret = -EINVAL; 1899 goto err_out; 1900 } 1901 if (icx->is_in_root) 1902 ih = &icx->ir->index; 1903 else 1904 ih = &icx->ib->index; 1905 1906 if (icx->entry->flags & INDEX_ENTRY_NODE) { 1907 ret = ntfs_index_rm_node(icx); 1908 if (ret) 1909 goto err_out; 1910 } else if (icx->is_in_root || !ntfs_ih_one_entry(ih)) { 1911 ntfs_ie_delete(ih, icx->entry); 1912 1913 if (icx->is_in_root) 1914 ret = ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length)); 1915 else 1916 ret = ntfs_icx_ib_write(icx); 1917 if (ret) 1918 goto err_out; 1919 } else { 1920 ret = ntfs_index_rm_leaf(icx); 1921 if (ret) 1922 goto err_out; 1923 } 1924 1925 return 0; 1926 err_out: 1927 return ret; 1928 } 1929 1930 int ntfs_index_remove(struct ntfs_inode *dir_ni, const void *key, const u32 keylen) 1931 { 1932 int ret = 0; 1933 struct ntfs_index_context *icx; 1934 1935 icx = ntfs_index_ctx_get(dir_ni, I30, 4); 1936 if (!icx) 1937 return -EINVAL; 1938 1939 while (1) { 1940 ret = ntfs_index_lookup(key, keylen, icx); 1941 if (ret) 1942 goto err_out; 1943 1944 ret = ntfs_index_rm(icx); 1945 if (ret && ret != -EAGAIN) 1946 goto err_out; 1947 else if (!ret) 1948 break; 1949 1950 mark_mft_record_dirty(icx->actx->ntfs_ino); 1951 ntfs_index_ctx_reinit(icx); 1952 } 1953 1954 mark_mft_record_dirty(icx->actx->ntfs_ino); 1955 1956 ntfs_index_ctx_put(icx); 1957 return 0; 1958 err_out: 1959 ntfs_index_ctx_put(icx); 1960 ntfs_error(dir_ni->vol->sb, "Delete failed"); 1961 return ret; 1962 } 1963 1964 /* 1965 * ntfs_index_walk_down - walk down the index tree (leaf bound) 1966 * until there are no subnode in the first index entry returns 1967 * the entry at the bottom left in subnode 1968 */ 1969 struct index_entry *ntfs_index_walk_down(struct index_entry *ie, struct ntfs_index_context *ictx) 1970 { 1971 struct index_entry *entry; 1972 s64 vcn; 1973 1974 entry = ie; 1975 do { 1976 vcn = ntfs_ie_get_vcn(entry); 1977 if (ictx->is_in_root) { 1978 /* down from level zero */ 1979 ictx->ir = NULL; 1980 ictx->ib = kvzalloc(ictx->block_size, GFP_NOFS); 1981 ictx->pindex = 1; 1982 ictx->is_in_root = false; 1983 } else { 1984 /* down from non-zero level */ 1985 ictx->pindex++; 1986 } 1987 1988 ictx->parent_pos[ictx->pindex] = 0; 1989 ictx->parent_vcn[ictx->pindex] = vcn; 1990 if (!ntfs_ib_read(ictx, vcn, ictx->ib)) { 1991 ictx->entry = ntfs_ie_get_first(&ictx->ib->index); 1992 entry = ictx->entry; 1993 } else 1994 entry = NULL; 1995 } while (entry && (entry->flags & INDEX_ENTRY_NODE)); 1996 1997 return entry; 1998 } 1999 2000 /* 2001 * ntfs_index_walk_up - walk up the index tree (root bound) until 2002 * there is a valid data entry in parent returns the parent entry 2003 * or NULL if no more parent. 2004 * @ie: current index entry 2005 * @ictx: index context 2006 */ 2007 static struct index_entry *ntfs_index_walk_up(struct index_entry *ie, 2008 struct ntfs_index_context *ictx) 2009 { 2010 struct index_entry *entry = ie; 2011 s64 vcn; 2012 2013 if (ictx->pindex <= 0) 2014 return NULL; 2015 2016 do { 2017 ictx->pindex--; 2018 if (!ictx->pindex) { 2019 /* we have reached the root */ 2020 kfree(ictx->ib); 2021 ictx->ib = NULL; 2022 ictx->is_in_root = true; 2023 /* a new search context is to be allocated */ 2024 if (ictx->actx) 2025 ntfs_attr_put_search_ctx(ictx->actx); 2026 ictx->ir = ntfs_ir_lookup(ictx->idx_ni, ictx->name, 2027 ictx->name_len, &ictx->actx); 2028 if (ictx->ir) 2029 entry = ntfs_ie_get_by_pos( 2030 &ictx->ir->index, 2031 ictx->parent_pos[ictx->pindex]); 2032 else 2033 entry = NULL; 2034 } else { 2035 /* up into non-root node */ 2036 vcn = ictx->parent_vcn[ictx->pindex]; 2037 if (!ntfs_ib_read(ictx, vcn, ictx->ib)) { 2038 entry = ntfs_ie_get_by_pos( 2039 &ictx->ib->index, 2040 ictx->parent_pos[ictx->pindex]); 2041 } else 2042 entry = NULL; 2043 } 2044 ictx->entry = entry; 2045 } while (entry && (ictx->pindex > 0) && 2046 (entry->flags & INDEX_ENTRY_END)); 2047 return entry; 2048 } 2049 2050 /* 2051 * ntfs_index_next - get next entry in an index according to collating sequence. 2052 * Returns next entry or NULL if none. 2053 * 2054 * Sample layout : 2055 * 2056 * +---+---+---+---+---+---+---+---+ n ptrs to subnodes 2057 * | | | 10| 25| 33| | | | n-1 keys in between 2058 * +---+---+---+---+---+---+---+---+ no key in last entry 2059 * | A | A 2060 * | | | +-------------------------------+ 2061 * +--------------------------+ | +-----+ | 2062 * | +--+ | | 2063 * V | V | 2064 * +---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+---+ 2065 * | 11| 12| 13| 14| 15| 16| 17| | | | 26| 27| 28| 29| 30| 31| 32| | 2066 * +---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+---+ 2067 * | | 2068 * +-----------------------+ | 2069 * | | 2070 * +---+---+---+---+---+---+---+---+ 2071 * | 18| 19| 20| 21| 22| 23| 24| | 2072 * +---+---+---+---+---+---+---+---+ 2073 * 2074 * @ie: current index entry 2075 * @ictx: index context 2076 */ 2077 struct index_entry *ntfs_index_next(struct index_entry *ie, struct ntfs_index_context *ictx) 2078 { 2079 struct index_entry *next; 2080 __le16 flags; 2081 2082 /* 2083 * lookup() may have returned an invalid node 2084 * when searching for a partial key 2085 * if this happens, walk up 2086 */ 2087 if (ie->flags & INDEX_ENTRY_END) 2088 next = ntfs_index_walk_up(ie, ictx); 2089 else { 2090 /* 2091 * get next entry in same node 2092 * there is always one after any entry with data 2093 */ 2094 next = (struct index_entry *)((char *)ie + le16_to_cpu(ie->length)); 2095 ++ictx->parent_pos[ictx->pindex]; 2096 flags = next->flags; 2097 2098 /* walk down if it has a subnode */ 2099 if (flags & INDEX_ENTRY_NODE) { 2100 if (!ictx->ia_ni) 2101 ictx->ia_ni = ntfs_ia_open(ictx, ictx->idx_ni); 2102 2103 next = ntfs_index_walk_down(next, ictx); 2104 } else { 2105 2106 /* walk up it has no subnode, nor data */ 2107 if (flags & INDEX_ENTRY_END) 2108 next = ntfs_index_walk_up(next, ictx); 2109 } 2110 } 2111 2112 /* return NULL if stuck at end of a block */ 2113 if (next && (next->flags & INDEX_ENTRY_END)) 2114 next = NULL; 2115 2116 return next; 2117 } 2118