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