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 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->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 VCN *ntfs_ie_get_vcn_addr(INDEX_ENTRY *ie) 195{ 196 return (VCN *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(VCN)); 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_le64(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 int ntfs_ia_check(ntfs_index_context *icx, INDEX_BLOCK *ib, VCN vcn) 392{ 393 u32 ib_size = (unsigned)le32_to_cpu(ib->index.allocated_size) + 0x18; 394 395 ntfs_log_trace("Entering\n"); 396 397 if (!ntfs_is_indx_record(ib->magic)) { 398 399 ntfs_log_error("Corrupt index block signature: vcn %lld inode " 400 "%llu\n", (long long)vcn, 401 (unsigned long long)icx->ni->mft_no); 402 return -1; 403 } 404 405 if (sle64_to_cpu(ib->index_block_vcn) != vcn) { 406 407 ntfs_log_error("Corrupt index block: VCN (%lld) is different " 408 "from expected VCN (%lld) in inode %llu\n", 409 (long long)sle64_to_cpu(ib->index_block_vcn), 410 (long long)vcn, 411 (unsigned long long)icx->ni->mft_no); 412 return -1; 413 } 414 415 if (ib_size != icx->block_size) { 416 417 ntfs_log_error("Corrupt index block : VCN (%lld) of inode %llu " 418 "has a size (%u) differing from the index " 419 "specified size (%u)\n", (long long)vcn, 420 (unsigned long long)icx->ni->mft_no, ib_size, 421 icx->block_size); 422 return -1; 423 } 424 return 0; 425} 426 427static INDEX_ROOT *ntfs_ir_lookup(ntfs_inode *ni, ntfschar *name, 428 u32 name_len, ntfs_attr_search_ctx **ctx) 429{ 430 ATTR_RECORD *a; 431 INDEX_ROOT *ir = NULL; 432 433 ntfs_log_trace("Entering\n"); 434 435 *ctx = ntfs_attr_get_search_ctx(ni, NULL); 436 if (!*ctx) 437 return NULL; 438 439 if (ntfs_attr_lookup(AT_INDEX_ROOT, name, name_len, CASE_SENSITIVE, 440 0, NULL, 0, *ctx)) { 441 ntfs_log_perror("Failed to lookup $INDEX_ROOT"); 442 goto err_out; 443 } 444 445 a = (*ctx)->attr; 446 if (a->non_resident) { 447 errno = EINVAL; 448 ntfs_log_perror("Non-resident $INDEX_ROOT detected"); 449 goto err_out; 450 } 451 452 ir = (INDEX_ROOT *)((char *)a + le16_to_cpu(a->value_offset)); 453err_out: 454 if (!ir) { 455 ntfs_attr_put_search_ctx(*ctx); 456 *ctx = NULL; 457 } 458 return ir; 459} 460 461static INDEX_ROOT *ntfs_ir_lookup2(ntfs_inode *ni, ntfschar *name, u32 len) 462{ 463 ntfs_attr_search_ctx *ctx; 464 INDEX_ROOT *ir; 465 466 ir = ntfs_ir_lookup(ni, name, len, &ctx); 467 if (ir) 468 ntfs_attr_put_search_ctx(ctx); 469 return ir; 470} 471 472/** 473 * Find a key in the index block. 474 * 475 * Return values: 476 * STATUS_OK with errno set to ESUCCESS if we know for sure that the 477 * entry exists and @ie_out points to this entry. 478 * STATUS_NOT_FOUND with errno set to ENOENT if we know for sure the 479 * entry doesn't exist and @ie_out is the insertion point. 480 * STATUS_KEEP_SEARCHING if we can't answer the above question and 481 * @vcn will contain the node index block. 482 * STATUS_ERROR with errno set if on unexpected error during lookup. 483 */ 484static int ntfs_ie_lookup(const void *key, const int key_len, 485 ntfs_index_context *icx, INDEX_HEADER *ih, 486 VCN *vcn, INDEX_ENTRY **ie_out) 487{ 488 INDEX_ENTRY *ie; 489 u8 *index_end; 490 int rc, item = 0; 491 492 ntfs_log_trace("Entering\n"); 493 494 index_end = ntfs_ie_get_end(ih); 495 496 /* 497 * Loop until we exceed valid memory (corruption case) or until we 498 * reach the last entry. 499 */ 500 for (ie = ntfs_ie_get_first(ih); ; ie = ntfs_ie_get_next(ie)) { 501 /* Bounds checks. */ 502 if ((u8 *)ie + sizeof(INDEX_ENTRY_HEADER) > index_end || 503 (u8 *)ie + le16_to_cpu(ie->length) > index_end) { 504 errno = ERANGE; 505 ntfs_log_error("Index entry out of bounds in inode " 506 "%llu.\n", 507 (unsigned long long)icx->ni->mft_no); 508 return STATUS_ERROR; 509 } 510 /* 511 * The last entry cannot contain a key. It can however contain 512 * a pointer to a child node in the B+tree so we just break out. 513 */ 514 if (ntfs_ie_end(ie)) 515 break; 516 /* 517 * Not a perfect match, need to do full blown collation so we 518 * know which way in the B+tree we have to go. 519 */ 520 if (!icx->collate) { 521 ntfs_log_error("Collation function not defined\n"); 522 errno = EOPNOTSUPP; 523 return STATUS_ERROR; 524 } 525 rc = icx->collate(icx->ni->vol, key, key_len, 526 &ie->key, le16_to_cpu(ie->key_length)); 527 if (rc == NTFS_COLLATION_ERROR) { 528 ntfs_log_error("Collation error. Perhaps a filename " 529 "contains invalid characters?\n"); 530 errno = ERANGE; 531 return STATUS_ERROR; 532 } 533 /* 534 * If @key collates before the key of the current entry, there 535 * is definitely no such key in this index but we might need to 536 * descend into the B+tree so we just break out of the loop. 537 */ 538 if (rc == -1) 539 break; 540 541 if (!rc) { 542 *ie_out = ie; 543 errno = 0; 544 icx->parent_pos[icx->pindex] = item; 545 return STATUS_OK; 546 } 547 548 item++; 549 } 550 /* 551 * We have finished with this index block without success. Check for the 552 * presence of a child node and if not present return with errno ENOENT, 553 * otherwise we will keep searching in another index block. 554 */ 555 if (!(ie->ie_flags & INDEX_ENTRY_NODE)) { 556 ntfs_log_debug("Index entry wasn't found.\n"); 557 *ie_out = ie; 558 errno = ENOENT; 559 return STATUS_NOT_FOUND; 560 } 561 562 /* Get the starting vcn of the index_block holding the child node. */ 563 *vcn = ntfs_ie_get_vcn(ie); 564 if (*vcn < 0) { 565 errno = EINVAL; 566 ntfs_log_perror("Negative vcn in inode %llu", 567 (unsigned long long)icx->ni->mft_no); 568 return STATUS_ERROR; 569 } 570 571 ntfs_log_trace("Parent entry number %d\n", item); 572 icx->parent_pos[icx->pindex] = item; 573 574 return STATUS_KEEP_SEARCHING; 575} 576 577static ntfs_attr *ntfs_ia_open(ntfs_index_context *icx, ntfs_inode *ni) 578{ 579 ntfs_attr *na; 580 581 na = ntfs_attr_open(ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len); 582 if (!na) { 583 ntfs_log_perror("Failed to open index allocation of inode " 584 "%llu", (unsigned long long)ni->mft_no); 585 return NULL; 586 } 587 588 return na; 589} 590 591static int ntfs_ib_read(ntfs_index_context *icx, VCN vcn, INDEX_BLOCK *dst) 592{ 593 s64 pos, ret; 594 595 ntfs_log_trace("vcn: %lld\n", (long long)vcn); 596 597 pos = ntfs_ib_vcn_to_pos(icx, vcn); 598 599 ret = ntfs_attr_mst_pread(icx->ia_na, pos, 1, icx->block_size, (u8 *)dst); 600 if (ret != 1) { 601 if (ret == -1) 602 ntfs_log_perror("Failed to read index block"); 603 else 604 ntfs_log_error("Failed to read full index block at " 605 "%lld\n", (long long)pos); 606 return -1; 607 } 608 609 if (ntfs_ia_check(icx, dst, vcn)) 610 return -1; 611 612 return 0; 613} 614 615static int ntfs_icx_parent_inc(ntfs_index_context *icx) 616{ 617 icx->pindex++; 618 if (icx->pindex >= MAX_PARENT_VCN) { 619 errno = EOPNOTSUPP; 620 ntfs_log_perror("Index is over %d level deep", MAX_PARENT_VCN); 621 return STATUS_ERROR; 622 } 623 return STATUS_OK; 624} 625 626static int ntfs_icx_parent_dec(ntfs_index_context *icx) 627{ 628 icx->pindex--; 629 if (icx->pindex < 0) { 630 errno = EINVAL; 631 ntfs_log_perror("Corrupt index pointer (%d)", icx->pindex); 632 return STATUS_ERROR; 633 } 634 return STATUS_OK; 635} 636 637/** 638 * ntfs_index_lookup - find a key in an index and return its index entry 639 * @key: [IN] key for which to search in the index 640 * @key_len: [IN] length of @key in bytes 641 * @icx: [IN/OUT] context describing the index and the returned entry 642 * 643 * Before calling ntfs_index_lookup(), @icx must have been obtained from a 644 * call to ntfs_index_ctx_get(). 645 * 646 * Look for the @key in the index specified by the index lookup context @icx. 647 * ntfs_index_lookup() walks the contents of the index looking for the @key. 648 * 649 * If the @key is found in the index, 0 is returned and @icx is setup to 650 * describe the index entry containing the matching @key. @icx->entry is the 651 * index entry and @icx->data and @icx->data_len are the index entry data and 652 * its length in bytes, respectively. 653 * 654 * If the @key is not found in the index, -1 is returned, errno = ENOENT and 655 * @icx is setup to describe the index entry whose key collates immediately 656 * after the search @key, i.e. this is the position in the index at which 657 * an index entry with a key of @key would need to be inserted. 658 * 659 * If an error occurs return -1, set errno to error code and @icx is left 660 * untouched. 661 * 662 * When finished with the entry and its data, call ntfs_index_ctx_put() to free 663 * the context and other associated resources. 664 * 665 * If the index entry was modified, call ntfs_index_entry_mark_dirty() before 666 * the call to ntfs_index_ctx_put() to ensure that the changes are written 667 * to disk. 668 */ 669int ntfs_index_lookup(const void *key, const int key_len, ntfs_index_context *icx) 670{ 671 VCN old_vcn, vcn; 672 ntfs_inode *ni = icx->ni; 673 INDEX_ROOT *ir; 674 INDEX_ENTRY *ie; 675 INDEX_BLOCK *ib = NULL; 676 int ret, err = 0; 677 678 ntfs_log_trace("Entering\n"); 679 680 if (!key || key_len <= 0) { 681 errno = EINVAL; 682 ntfs_log_perror("key: %p key_len: %d", key, key_len); 683 return -1; 684 } 685 686 ir = ntfs_ir_lookup(ni, icx->name, icx->name_len, &icx->actx); 687 if (!ir) { 688 if (errno == ENOENT) 689 errno = EIO; 690 return -1; 691 } 692 693 icx->block_size = le32_to_cpu(ir->index_block_size); 694 if (icx->block_size < NTFS_BLOCK_SIZE) { 695 errno = EINVAL; 696 ntfs_log_perror("Index block size (%d) is smaller than the " 697 "sector size (%d)", icx->block_size, NTFS_BLOCK_SIZE); 698 goto err_out; 699 } 700 701 if (ni->vol->cluster_size <= icx->block_size) 702 icx->vcn_size_bits = ni->vol->cluster_size_bits; 703 else 704 icx->vcn_size_bits = NTFS_BLOCK_SIZE_BITS; 705 /* get the appropriate collation function */ 706 icx->collate = ntfs_get_collate_function(ir->collation_rule); 707 if (!icx->collate) { 708 err = errno = EOPNOTSUPP; 709 ntfs_log_perror("Unknown collation rule 0x%x", 710 (unsigned)le32_to_cpu(ir->collation_rule)); 711 goto err_out; 712 } 713 714 old_vcn = VCN_INDEX_ROOT_PARENT; 715 /* 716 * FIXME: check for both ir and ib that the first index entry is 717 * within the index block. 718 */ 719 ret = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie); 720 if (ret == STATUS_ERROR) { 721 err = errno; 722 goto err_out; 723 } 724 725 icx->ir = ir; 726 727 if (ret != STATUS_KEEP_SEARCHING) { 728 /* STATUS_OK or STATUS_NOT_FOUND */ 729 err = errno; 730 icx->is_in_root = TRUE; 731 icx->parent_vcn[icx->pindex] = old_vcn; 732 goto done; 733 } 734 735 /* Child node present, descend into it. */ 736 737 icx->ia_na = ntfs_ia_open(icx, ni); 738 if (!icx->ia_na) 739 goto err_out; 740 741 ib = ntfs_malloc(icx->block_size); 742 if (!ib) { 743 err = errno; 744 goto err_out; 745 } 746 747descend_into_child_node: 748 749 icx->parent_vcn[icx->pindex] = old_vcn; 750 if (ntfs_icx_parent_inc(icx)) { 751 err = errno; 752 goto err_out; 753 } 754 old_vcn = vcn; 755 756 ntfs_log_debug("Descend into node with VCN %lld\n", (long long)vcn); 757 758 if (ntfs_ib_read(icx, vcn, ib)) 759 goto err_out; 760 761 ret = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie); 762 if (ret != STATUS_KEEP_SEARCHING) { 763 err = errno; 764 if (ret == STATUS_ERROR) 765 goto err_out; 766 767 /* STATUS_OK or STATUS_NOT_FOUND */ 768 icx->is_in_root = FALSE; 769 icx->ib = ib; 770 icx->parent_vcn[icx->pindex] = vcn; 771 goto done; 772 } 773 774 if ((ib->index.ih_flags & NODE_MASK) == LEAF_NODE) { 775 ntfs_log_error("Index entry with child node found in a leaf " 776 "node in inode 0x%llx.\n", 777 (unsigned long long)ni->mft_no); 778 goto err_out; 779 } 780 781 goto descend_into_child_node; 782err_out: 783 free(ib); 784 if (!err) 785 err = EIO; 786 errno = err; 787 return -1; 788done: 789 icx->entry = ie; 790 icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key); 791 icx->data_len = le16_to_cpu(ie->key_length); 792 ntfs_log_trace("Done.\n"); 793 if (err) { 794 errno = err; 795 return -1; 796 } 797 return 0; 798 799} 800 801static INDEX_BLOCK *ntfs_ib_alloc(VCN ib_vcn, u32 ib_size, 802 INDEX_HEADER_FLAGS node_type) 803{ 804 INDEX_BLOCK *ib; 805 int ih_size = sizeof(INDEX_HEADER); 806 807 ntfs_log_trace("ib_vcn: %lld ib_size: %u\n", (long long)ib_vcn, ib_size); 808 809 ib = ntfs_calloc(ib_size); 810 if (!ib) 811 return NULL; 812 813 ib->magic = magic_INDX; 814 ib->usa_ofs = cpu_to_le16(sizeof(INDEX_BLOCK)); 815 ib->usa_count = cpu_to_le16(ib_size / NTFS_BLOCK_SIZE + 1); 816 /* Set USN to 1 */ 817 *(u16 *)((char *)ib + le16_to_cpu(ib->usa_ofs)) = cpu_to_le16(1); 818 ib->lsn = cpu_to_le64(0); 819 820 ib->index_block_vcn = cpu_to_sle64(ib_vcn); 821 822 ib->index.entries_offset = cpu_to_le32((ih_size + 823 le16_to_cpu(ib->usa_count) * 2 + 7) & ~7); 824 ib->index.index_length = 0; 825 ib->index.allocated_size = cpu_to_le32(ib_size - 826 (sizeof(INDEX_BLOCK) - ih_size)); 827 ib->index.ih_flags = node_type; 828 829 return ib; 830} 831 832/** 833 * Find the median by going through all the entries 834 */ 835static INDEX_ENTRY *ntfs_ie_get_median(INDEX_HEADER *ih) 836{ 837 INDEX_ENTRY *ie, *ie_start; 838 u8 *ie_end; 839 int i = 0, median; 840 841 ntfs_log_trace("Entering\n"); 842 843 ie = ie_start = ntfs_ie_get_first(ih); 844 ie_end = (u8 *)ntfs_ie_get_end(ih); 845 846 while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) { 847 ie = ntfs_ie_get_next(ie); 848 i++; 849 } 850 /* 851 * NOTE: this could be also the entry at the half of the index block. 852 */ 853 median = i / 2 - 1; 854 855 ntfs_log_trace("Entries: %d median: %d\n", i, median); 856 857 for (i = 0, ie = ie_start; i <= median; i++) 858 ie = ntfs_ie_get_next(ie); 859 860 return ie; 861} 862 863static s64 ntfs_ibm_vcn_to_pos(ntfs_index_context *icx, VCN vcn) 864{ 865 return ntfs_ib_vcn_to_pos(icx, vcn) / icx->block_size; 866} 867 868static s64 ntfs_ibm_pos_to_vcn(ntfs_index_context *icx, s64 pos) 869{ 870 return ntfs_ib_pos_to_vcn(icx, pos * icx->block_size); 871} 872 873static int ntfs_ibm_add(ntfs_index_context *icx) 874{ 875 u8 bmp[8]; 876 877 ntfs_log_trace("Entering\n"); 878 879 if (ntfs_attr_exist(icx->ni, AT_BITMAP, icx->name, icx->name_len)) 880 return STATUS_OK; 881 /* 882 * AT_BITMAP must be at least 8 bytes. 883 */ 884 memset(bmp, 0, sizeof(bmp)); 885 if (ntfs_attr_add(icx->ni, AT_BITMAP, icx->name, icx->name_len, 886 bmp, sizeof(bmp))) { 887 ntfs_log_perror("Failed to add AT_BITMAP"); 888 return STATUS_ERROR; 889 } 890 891 return STATUS_OK; 892} 893 894static int ntfs_ibm_modify(ntfs_index_context *icx, VCN vcn, int set) 895{ 896 u8 byte; 897 s64 pos = ntfs_ibm_vcn_to_pos(icx, vcn); 898 u32 bpos = pos / 8; 899 u32 bit = 1 << (pos % 8); 900 ntfs_attr *na; 901 int ret = STATUS_ERROR; 902 903 ntfs_log_trace("%s vcn: %lld\n", set ? "set" : "clear", (long long)vcn); 904 905 na = ntfs_attr_open(icx->ni, AT_BITMAP, icx->name, icx->name_len); 906 if (!na) { 907 ntfs_log_perror("Failed to open $BITMAP attribute"); 908 return -1; 909 } 910 911 if (set) { 912 if (na->data_size < bpos + 1) { 913 if (ntfs_attr_truncate(na, (na->data_size + 8) & ~7)) { 914 ntfs_log_perror("Failed to truncate AT_BITMAP"); 915 goto err_na; 916 } 917 } 918 } 919 920 if (ntfs_attr_pread(na, bpos, 1, &byte) != 1) { 921 ntfs_log_perror("Failed to read $BITMAP"); 922 goto err_na; 923 } 924 925 if (set) 926 byte |= bit; 927 else 928 byte &= ~bit; 929 930 if (ntfs_attr_pwrite(na, bpos, 1, &byte) != 1) { 931 ntfs_log_perror("Failed to write $Bitmap"); 932 goto err_na; 933 } 934 935 ret = STATUS_OK; 936err_na: 937 ntfs_attr_close(na); 938 return ret; 939} 940 941 942static int ntfs_ibm_set(ntfs_index_context *icx, VCN vcn) 943{ 944 return ntfs_ibm_modify(icx, vcn, 1); 945} 946 947static int ntfs_ibm_clear(ntfs_index_context *icx, VCN vcn) 948{ 949 return ntfs_ibm_modify(icx, vcn, 0); 950} 951 952static VCN ntfs_ibm_get_free(ntfs_index_context *icx) 953{ 954 u8 *bm; 955 int bit; 956 s64 vcn, byte, size; 957 958 ntfs_log_trace("Entering\n"); 959 960 bm = ntfs_attr_readall(icx->ni, AT_BITMAP, icx->name, icx->name_len, 961 &size); 962 if (!bm) 963 return (VCN)-1; 964 965 for (byte = 0; byte < size; byte++) { 966 967 if (bm[byte] == 255) 968 continue; 969 970 for (bit = 0; bit < 8; bit++) { 971 if (!(bm[byte] & (1 << bit))) { 972 vcn = ntfs_ibm_pos_to_vcn(icx, byte * 8 + bit); 973 goto out; 974 } 975 } 976 } 977 978 vcn = ntfs_ibm_pos_to_vcn(icx, size * 8); 979out: 980 ntfs_log_trace("allocated vcn: %lld\n", (long long)vcn); 981 982 if (ntfs_ibm_set(icx, vcn)) 983 vcn = (VCN)-1; 984 985 free(bm); 986 return vcn; 987} 988 989static INDEX_BLOCK *ntfs_ir_to_ib(INDEX_ROOT *ir, VCN ib_vcn) 990{ 991 INDEX_BLOCK *ib; 992 INDEX_ENTRY *ie_last; 993 char *ies_start, *ies_end; 994 int i; 995 996 ntfs_log_trace("Entering\n"); 997 998 ib = ntfs_ib_alloc(ib_vcn, le32_to_cpu(ir->index_block_size), LEAF_NODE); 999 if (!ib) 1000 return NULL; 1001 1002 ies_start = (char *)ntfs_ie_get_first(&ir->index); 1003 ies_end = (char *)ntfs_ie_get_end(&ir->index); 1004 ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end); 1005 /* 1006 * Copy all entries, including the termination entry 1007 * as well, which can never have any data. 1008 */ 1009 i = (char *)ie_last - ies_start + le16_to_cpu(ie_last->length); 1010 memcpy(ntfs_ie_get_first(&ib->index), ies_start, i); 1011 1012 ib->index.ih_flags = ir->index.ih_flags; 1013 ib->index.index_length = cpu_to_le32(i + 1014 le32_to_cpu(ib->index.entries_offset)); 1015 return ib; 1016} 1017 1018static void ntfs_ir_nill(INDEX_ROOT *ir) 1019{ 1020 INDEX_ENTRY *ie_last; 1021 char *ies_start, *ies_end; 1022 1023 ntfs_log_trace("Entering\n"); 1024 /* 1025 * TODO: This function could be much simpler. 1026 */ 1027 ies_start = (char *)ntfs_ie_get_first(&ir->index); 1028 ies_end = (char *)ntfs_ie_get_end(&ir->index); 1029 ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end); 1030 /* 1031 * Move the index root termination entry forward 1032 */ 1033 if ((char *)ie_last > ies_start) { 1034 memmove(ies_start, (char *)ie_last, le16_to_cpu(ie_last->length)); 1035 ie_last = (INDEX_ENTRY *)ies_start; 1036 } 1037} 1038 1039static int ntfs_ib_copy_tail(ntfs_index_context *icx, INDEX_BLOCK *src, 1040 INDEX_ENTRY *median, VCN new_vcn) 1041{ 1042 u8 *ies_end; 1043 INDEX_ENTRY *ie_head; /* first entry after the median */ 1044 int tail_size, ret; 1045 INDEX_BLOCK *dst; 1046 1047 ntfs_log_trace("Entering\n"); 1048 1049 dst = ntfs_ib_alloc(new_vcn, icx->block_size, 1050 src->index.ih_flags & NODE_MASK); 1051 if (!dst) 1052 return STATUS_ERROR; 1053 1054 ie_head = ntfs_ie_get_next(median); 1055 1056 ies_end = (u8 *)ntfs_ie_get_end(&src->index); 1057 tail_size = ies_end - (u8 *)ie_head; 1058 memcpy(ntfs_ie_get_first(&dst->index), ie_head, tail_size); 1059 1060 dst->index.index_length = cpu_to_le32(tail_size + 1061 le32_to_cpu(dst->index.entries_offset)); 1062 ret = ntfs_ib_write(icx, dst); 1063 1064 free(dst); 1065 return ret; 1066} 1067 1068static int ntfs_ib_cut_tail(ntfs_index_context *icx, INDEX_BLOCK *ib, 1069 INDEX_ENTRY *ie) 1070{ 1071 char *ies_start, *ies_end; 1072 INDEX_ENTRY *ie_last; 1073 1074 ntfs_log_trace("Entering\n"); 1075 1076 ies_start = (char *)ntfs_ie_get_first(&ib->index); 1077 ies_end = (char *)ntfs_ie_get_end(&ib->index); 1078 1079 ie_last = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end); 1080 if (ie_last->ie_flags & INDEX_ENTRY_NODE) 1081 ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie)); 1082 1083 memcpy(ie, ie_last, le16_to_cpu(ie_last->length)); 1084 1085 ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) + 1086 le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset)); 1087 1088 if (ntfs_ib_write(icx, ib)) 1089 return STATUS_ERROR; 1090 1091 return STATUS_OK; 1092} 1093 1094static int ntfs_ia_add(ntfs_index_context *icx) 1095{ 1096 ntfs_log_trace("Entering\n"); 1097 1098 if (ntfs_ibm_add(icx)) 1099 return -1; 1100 1101 if (!ntfs_attr_exist(icx->ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) { 1102 1103 if (ntfs_attr_add(icx->ni, AT_INDEX_ALLOCATION, icx->name, 1104 icx->name_len, NULL, 0)) { 1105 ntfs_log_perror("Failed to add AT_INDEX_ALLOCATION"); 1106 return -1; 1107 } 1108 } 1109 1110 icx->ia_na = ntfs_ia_open(icx, icx->ni); 1111 if (!icx->ia_na) 1112 return -1; 1113 1114 return 0; 1115} 1116 1117static int ntfs_ir_reparent(ntfs_index_context *icx) 1118{ 1119 ntfs_attr_search_ctx *ctx = NULL; 1120 INDEX_ROOT *ir; 1121 INDEX_ENTRY *ie; 1122 INDEX_BLOCK *ib = NULL; 1123 VCN new_ib_vcn; 1124 int ix_root_size; 1125 int ret = STATUS_ERROR; 1126 1127 ntfs_log_trace("Entering\n"); 1128 1129 ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len); 1130 if (!ir) 1131 goto out; 1132 1133 if ((ir->index.ih_flags & NODE_MASK) == SMALL_INDEX) 1134 if (ntfs_ia_add(icx)) 1135 goto out; 1136 1137 new_ib_vcn = ntfs_ibm_get_free(icx); 1138 if (new_ib_vcn == -1) 1139 goto out; 1140 1141 ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len); 1142 if (!ir) 1143 goto clear_bmp; 1144 1145 ib = ntfs_ir_to_ib(ir, new_ib_vcn); 1146 if (ib == NULL) { 1147 ntfs_log_perror("Failed to move index root to index block"); 1148 goto clear_bmp; 1149 } 1150 1151 if (ntfs_ib_write(icx, ib)) 1152 goto clear_bmp; 1153 1154retry : 1155 ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len, &ctx); 1156 if (!ir) 1157 goto clear_bmp; 1158 1159 ntfs_ir_nill(ir); 1160 1161 ie = ntfs_ie_get_first(&ir->index); 1162 ie->ie_flags |= INDEX_ENTRY_NODE; 1163 ie->length = cpu_to_le16(sizeof(INDEX_ENTRY_HEADER) + sizeof(VCN)); 1164 1165 ir->index.ih_flags = LARGE_INDEX; 1166 ir->index.index_length = cpu_to_le32(le32_to_cpu(ir->index.entries_offset) 1167 + le16_to_cpu(ie->length)); 1168 ir->index.allocated_size = ir->index.index_length; 1169 ix_root_size = sizeof(INDEX_ROOT) - sizeof(INDEX_HEADER) 1170 + le32_to_cpu(ir->index.allocated_size); 1171 if (ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr, 1172 ix_root_size)) { 1173 /* 1174 * When there is no space to build a non-resident 1175 * index, we may have to move the root to an extent 1176 */ 1177 if ((errno == ENOSPC) 1178 && !ctx->al_entry 1179 && !ntfs_inode_add_attrlist(icx->ni)) { 1180 ntfs_attr_put_search_ctx(ctx); 1181 ctx = (ntfs_attr_search_ctx*)NULL; 1182 ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len, 1183 &ctx); 1184 if (ir 1185 && !ntfs_attr_record_move_away(ctx, ix_root_size 1186 - le32_to_cpu(ctx->attr->value_length))) { 1187 ntfs_attr_put_search_ctx(ctx); 1188 ctx = (ntfs_attr_search_ctx*)NULL; 1189 goto retry; 1190 } 1191 } 1192 /* FIXME: revert index root */ 1193 goto clear_bmp; 1194 } 1195 /* 1196 * FIXME: do it earlier if we have enough space in IR (should always), 1197 * so in error case we wouldn't lose the IB. 1198 */ 1199 ntfs_ie_set_vcn(ie, new_ib_vcn); 1200 1201 ret = STATUS_OK; 1202err_out: 1203 free(ib); 1204 ntfs_attr_put_search_ctx(ctx); 1205out: 1206 return ret; 1207clear_bmp: 1208 ntfs_ibm_clear(icx, new_ib_vcn); 1209 goto err_out; 1210} 1211 1212/** 1213 * ntfs_ir_truncate - Truncate index root attribute 1214 * 1215 * Returns STATUS_OK, STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT or STATUS_ERROR. 1216 */ 1217static int ntfs_ir_truncate(ntfs_index_context *icx, int data_size) 1218{ 1219 ntfs_attr *na; 1220 int ret; 1221 1222 ntfs_log_trace("Entering\n"); 1223 1224 na = ntfs_attr_open(icx->ni, AT_INDEX_ROOT, icx->name, icx->name_len); 1225 if (!na) { 1226 ntfs_log_perror("Failed to open INDEX_ROOT"); 1227 return STATUS_ERROR; 1228 } 1229 /* 1230 * INDEX_ROOT must be resident and its entries can be moved to 1231 * INDEX_BLOCK, so ENOSPC isn't a real error. 1232 */ 1233 ret = ntfs_attr_truncate(na, data_size + offsetof(INDEX_ROOT, index)); 1234 if (ret == STATUS_OK) { 1235 1236 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len); 1237 if (!icx->ir) 1238 return STATUS_ERROR; 1239 1240 icx->ir->index.allocated_size = cpu_to_le32(data_size); 1241 1242 } else if (ret == STATUS_ERROR) 1243 ntfs_log_perror("Failed to truncate INDEX_ROOT"); 1244 1245 ntfs_attr_close(na); 1246 return ret; 1247} 1248 1249/** 1250 * ntfs_ir_make_space - Make more space for the index root attribute 1251 * 1252 * On success return STATUS_OK or STATUS_KEEP_SEARCHING. 1253 * On error return STATUS_ERROR. 1254 */ 1255static int ntfs_ir_make_space(ntfs_index_context *icx, int data_size) 1256{ 1257 int ret; 1258 1259 ntfs_log_trace("Entering\n"); 1260 1261 ret = ntfs_ir_truncate(icx, data_size); 1262 if (ret == STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT) { 1263 1264 ret = ntfs_ir_reparent(icx); 1265 if (ret == STATUS_OK) 1266 ret = STATUS_KEEP_SEARCHING; 1267 else 1268 ntfs_log_perror("Failed to nodify INDEX_ROOT"); 1269 } 1270 1271 return ret; 1272} 1273 1274/* 1275 * NOTE: 'ie' must be a copy of a real index entry. 1276 */ 1277static int ntfs_ie_add_vcn(INDEX_ENTRY **ie) 1278{ 1279 INDEX_ENTRY *p, *old = *ie; 1280 1281 old->length = cpu_to_le16(le16_to_cpu(old->length) + sizeof(VCN)); 1282 p = realloc(old, le16_to_cpu(old->length)); 1283 if (!p) 1284 return STATUS_ERROR; 1285 1286 p->ie_flags |= INDEX_ENTRY_NODE; 1287 *ie = p; 1288 1289 return STATUS_OK; 1290} 1291 1292static int ntfs_ih_insert(INDEX_HEADER *ih, INDEX_ENTRY *orig_ie, VCN new_vcn, 1293 int pos) 1294{ 1295 INDEX_ENTRY *ie_node, *ie; 1296 int ret = STATUS_ERROR; 1297 VCN old_vcn; 1298 1299 ntfs_log_trace("Entering\n"); 1300 1301 ie = ntfs_ie_dup(orig_ie); 1302 if (!ie) 1303 return STATUS_ERROR; 1304 1305 if (!(ie->ie_flags & INDEX_ENTRY_NODE)) 1306 if (ntfs_ie_add_vcn(&ie)) 1307 goto out; 1308 1309 ie_node = ntfs_ie_get_by_pos(ih, pos); 1310 old_vcn = ntfs_ie_get_vcn(ie_node); 1311 ntfs_ie_set_vcn(ie_node, new_vcn); 1312 1313 ntfs_ie_insert(ih, ie, ie_node); 1314 ntfs_ie_set_vcn(ie_node, old_vcn); 1315 ret = STATUS_OK; 1316out: 1317 free(ie); 1318 1319 return ret; 1320} 1321 1322static VCN ntfs_icx_parent_vcn(ntfs_index_context *icx) 1323{ 1324 return icx->parent_vcn[icx->pindex]; 1325} 1326 1327static VCN ntfs_icx_parent_pos(ntfs_index_context *icx) 1328{ 1329 return icx->parent_pos[icx->pindex]; 1330} 1331 1332 1333static int ntfs_ir_insert_median(ntfs_index_context *icx, INDEX_ENTRY *median, 1334 VCN new_vcn) 1335{ 1336 u32 new_size; 1337 int ret; 1338 1339 ntfs_log_trace("Entering\n"); 1340 1341 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len); 1342 if (!icx->ir) 1343 return STATUS_ERROR; 1344 1345 new_size = le32_to_cpu(icx->ir->index.index_length) + 1346 le16_to_cpu(median->length); 1347 if (!(median->ie_flags & INDEX_ENTRY_NODE)) 1348 new_size += sizeof(VCN); 1349 1350 ret = ntfs_ir_make_space(icx, new_size); 1351 if (ret != STATUS_OK) 1352 return ret; 1353 1354 icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len); 1355 if (!icx->ir) 1356 return STATUS_ERROR; 1357 1358 return ntfs_ih_insert(&icx->ir->index, median, new_vcn, 1359 ntfs_icx_parent_pos(icx)); 1360} 1361 1362static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib); 1363 1364/** 1365 * On success return STATUS_OK or STATUS_KEEP_SEARCHING. 1366 * On error return STATUS_ERROR. 1367 */ 1368static int ntfs_ib_insert(ntfs_index_context *icx, INDEX_ENTRY *ie, VCN new_vcn) 1369{ 1370 INDEX_BLOCK *ib; 1371 u32 idx_size, allocated_size; 1372 int err = STATUS_ERROR; 1373 VCN old_vcn; 1374 1375 ntfs_log_trace("Entering\n"); 1376 1377 ib = ntfs_malloc(icx->block_size); 1378 if (!ib) 1379 return -1; 1380 1381 old_vcn = ntfs_icx_parent_vcn(icx); 1382 1383 if (ntfs_ib_read(icx, old_vcn, ib)) 1384 goto err_out; 1385 1386 idx_size = le32_to_cpu(ib->index.index_length); 1387 allocated_size = le32_to_cpu(ib->index.allocated_size); 1388 /* FIXME: sizeof(VCN) should be included only if ie has no VCN */ 1389 if (idx_size + le16_to_cpu(ie->length) + sizeof(VCN) > allocated_size) { 1390 err = ntfs_ib_split(icx, ib); 1391 if (err == STATUS_OK) 1392 err = STATUS_KEEP_SEARCHING; 1393 goto err_out; 1394 } 1395 1396 if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx))) 1397 goto err_out; 1398 1399 if (ntfs_ib_write(icx, ib)) 1400 goto err_out; 1401 1402 err = STATUS_OK; 1403err_out: 1404 free(ib); 1405 return err; 1406} 1407 1408/** 1409 * ntfs_ib_split - Split an index block 1410 * 1411 * On success return STATUS_OK or STATUS_KEEP_SEARCHING. 1412 * On error return is STATUS_ERROR. 1413 */ 1414static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib) 1415{ 1416 INDEX_ENTRY *median; 1417 VCN new_vcn; 1418 int ret; 1419 1420 ntfs_log_trace("Entering\n"); 1421 1422 if (ntfs_icx_parent_dec(icx)) 1423 return STATUS_ERROR; 1424 1425 median = ntfs_ie_get_median(&ib->index); 1426 new_vcn = ntfs_ibm_get_free(icx); 1427 if (new_vcn == -1) 1428 return STATUS_ERROR; 1429 1430 if (ntfs_ib_copy_tail(icx, ib, median, new_vcn)) { 1431 ntfs_ibm_clear(icx, new_vcn); 1432 return STATUS_ERROR; 1433 } 1434 1435 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) 1436 ret = ntfs_ir_insert_median(icx, median, new_vcn); 1437 else 1438 ret = ntfs_ib_insert(icx, median, new_vcn); 1439 1440 if (ret != STATUS_OK) { 1441 ntfs_ibm_clear(icx, new_vcn); 1442 return ret; 1443 } 1444 1445 ret = ntfs_ib_cut_tail(icx, ib, median); 1446 1447 return ret; 1448} 1449 1450/* JPA static */ 1451int ntfs_ie_add(ntfs_index_context *icx, INDEX_ENTRY *ie) 1452{ 1453 INDEX_HEADER *ih; 1454 int allocated_size, new_size; 1455 int ret = STATUS_ERROR; 1456 1457#ifdef DEBUG 1458/* removed by JPA to make function usable for security indexes 1459 char *fn; 1460 fn = ntfs_ie_filename_get(ie); 1461 ntfs_log_trace("file: '%s'\n", fn); 1462 ntfs_attr_name_free(&fn); 1463*/ 1464#endif 1465 1466 while (1) { 1467 1468 if (!ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx)) { 1469 errno = EEXIST; 1470 ntfs_log_perror("Index already have such entry"); 1471 goto err_out; 1472 } 1473 if (errno != ENOENT) { 1474 ntfs_log_perror("Failed to find place for new entry"); 1475 goto err_out; 1476 } 1477 1478 if (icx->is_in_root) 1479 ih = &icx->ir->index; 1480 else 1481 ih = &icx->ib->index; 1482 1483 allocated_size = le32_to_cpu(ih->allocated_size); 1484 new_size = le32_to_cpu(ih->index_length) + le16_to_cpu(ie->length); 1485 1486 if (new_size <= allocated_size) 1487 break; 1488 1489 ntfs_log_trace("index block sizes: allocated: %d needed: %d\n", 1490 allocated_size, new_size); 1491 1492 if (icx->is_in_root) { 1493 if (ntfs_ir_make_space(icx, new_size) == STATUS_ERROR) 1494 goto err_out; 1495 } else { 1496 if (ntfs_ib_split(icx, icx->ib) == STATUS_ERROR) 1497 goto err_out; 1498 } 1499 1500 ntfs_inode_mark_dirty(icx->actx->ntfs_ino); 1501 ntfs_index_ctx_reinit(icx); 1502 } 1503 1504 ntfs_ie_insert(ih, ie, icx->entry); 1505 ntfs_index_entry_mark_dirty(icx); 1506 1507 ret = STATUS_OK; 1508err_out: 1509 ntfs_log_trace("%s\n", ret ? "Failed" : "Done"); 1510 return ret; 1511} 1512 1513/** 1514 * ntfs_index_add_filename - add filename to directory index 1515 * @ni: ntfs inode describing directory to which index add filename 1516 * @fn: FILE_NAME attribute to add 1517 * @mref: reference of the inode which @fn describes 1518 * 1519 * Return 0 on success or -1 on error with errno set to the error code. 1520 */ 1521int ntfs_index_add_filename(ntfs_inode *ni, FILE_NAME_ATTR *fn, MFT_REF mref) 1522{ 1523 INDEX_ENTRY *ie; 1524 ntfs_index_context *icx; 1525 int fn_size, ie_size, err, ret = -1; 1526 1527 ntfs_log_trace("Entering\n"); 1528 1529 if (!ni || !fn) { 1530 ntfs_log_error("Invalid arguments.\n"); 1531 errno = EINVAL; 1532 return -1; 1533 } 1534 1535 fn_size = (fn->file_name_length * sizeof(ntfschar)) + 1536 sizeof(FILE_NAME_ATTR); 1537 ie_size = (sizeof(INDEX_ENTRY_HEADER) + fn_size + 7) & ~7; 1538 1539 ie = ntfs_calloc(ie_size); 1540 if (!ie) 1541 return -1; 1542 1543 ie->indexed_file = cpu_to_le64(mref); 1544 ie->length = cpu_to_le16(ie_size); 1545 ie->key_length = cpu_to_le16(fn_size); 1546 memcpy(&ie->key, fn, fn_size); 1547 1548 icx = ntfs_index_ctx_get(ni, NTFS_INDEX_I30, 4); 1549 if (!icx) 1550 goto out; 1551 1552 ret = ntfs_ie_add(icx, ie); 1553 err = errno; 1554 ntfs_index_ctx_put(icx); 1555 errno = err; 1556out: 1557 free(ie); 1558 return ret; 1559} 1560 1561static int ntfs_ih_takeout(ntfs_index_context *icx, INDEX_HEADER *ih, 1562 INDEX_ENTRY *ie, INDEX_BLOCK *ib) 1563{ 1564 INDEX_ENTRY *ie_roam; 1565 int ret = STATUS_ERROR; 1566 1567 ntfs_log_trace("Entering\n"); 1568 1569 ie_roam = ntfs_ie_dup_novcn(ie); 1570 if (!ie_roam) 1571 return STATUS_ERROR; 1572 1573 ntfs_ie_delete(ih, ie); 1574 1575 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) 1576 ntfs_inode_mark_dirty(icx->actx->ntfs_ino); 1577 else 1578 if (ntfs_ib_write(icx, ib)) 1579 goto out; 1580 1581 ntfs_index_ctx_reinit(icx); 1582 1583 ret = ntfs_ie_add(icx, ie_roam); 1584out: 1585 free(ie_roam); 1586 return ret; 1587} 1588 1589/** 1590 * Used if an empty index block to be deleted has END entry as the parent 1591 * in the INDEX_ROOT which is the only one there. 1592 */ 1593static void ntfs_ir_leafify(ntfs_index_context *icx, INDEX_HEADER *ih) 1594{ 1595 INDEX_ENTRY *ie; 1596 1597 ntfs_log_trace("Entering\n"); 1598 1599 ie = ntfs_ie_get_first(ih); 1600 ie->ie_flags &= ~INDEX_ENTRY_NODE; 1601 ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(VCN)); 1602 1603 ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) - sizeof(VCN)); 1604 ih->ih_flags &= ~LARGE_INDEX; 1605 1606 /* Not fatal error */ 1607 ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length)); 1608} 1609 1610/** 1611 * Used if an empty index block to be deleted has END entry as the parent 1612 * in the INDEX_ROOT which is not the only one there. 1613 */ 1614static int ntfs_ih_reparent_end(ntfs_index_context *icx, INDEX_HEADER *ih, 1615 INDEX_BLOCK *ib) 1616{ 1617 INDEX_ENTRY *ie, *ie_prev; 1618 1619 ntfs_log_trace("Entering\n"); 1620 1621 ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx)); 1622 ie_prev = ntfs_ie_prev(ih, ie); 1623 1624 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(ie_prev)); 1625 1626 return ntfs_ih_takeout(icx, ih, ie_prev, ib); 1627} 1628 1629static int ntfs_index_rm_leaf(ntfs_index_context *icx) 1630{ 1631 INDEX_BLOCK *ib = NULL; 1632 INDEX_HEADER *parent_ih; 1633 INDEX_ENTRY *ie; 1634 int ret = STATUS_ERROR; 1635 1636 ntfs_log_trace("pindex: %d\n", icx->pindex); 1637 1638 if (ntfs_icx_parent_dec(icx)) 1639 return STATUS_ERROR; 1640 1641 if (ntfs_ibm_clear(icx, icx->parent_vcn[icx->pindex + 1])) 1642 return STATUS_ERROR; 1643 1644 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) 1645 parent_ih = &icx->ir->index; 1646 else { 1647 ib = ntfs_malloc(icx->block_size); 1648 if (!ib) 1649 return STATUS_ERROR; 1650 1651 if (ntfs_ib_read(icx, ntfs_icx_parent_vcn(icx), ib)) 1652 goto out; 1653 1654 parent_ih = &ib->index; 1655 } 1656 1657 ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx)); 1658 if (!ntfs_ie_end(ie)) { 1659 ret = ntfs_ih_takeout(icx, parent_ih, ie, ib); 1660 goto out; 1661 } 1662 1663 if (ntfs_ih_zero_entry(parent_ih)) { 1664 1665 if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) { 1666 ntfs_ir_leafify(icx, parent_ih); 1667 goto ok; 1668 } 1669 1670 ret = ntfs_index_rm_leaf(icx); 1671 goto out; 1672 } 1673 1674 if (ntfs_ih_reparent_end(icx, parent_ih, ib)) 1675 goto out; 1676ok: 1677 ret = STATUS_OK; 1678out: 1679 free(ib); 1680 return ret; 1681} 1682 1683static int ntfs_index_rm_node(ntfs_index_context *icx) 1684{ 1685 int entry_pos, pindex; 1686 VCN vcn; 1687 INDEX_BLOCK *ib = NULL; 1688 INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry; 1689 INDEX_HEADER *ih; 1690 u32 new_size; 1691 int delta, ret = STATUS_ERROR; 1692 1693 ntfs_log_trace("Entering\n"); 1694 1695 if (!icx->ia_na) { 1696 icx->ia_na = ntfs_ia_open(icx, icx->ni); 1697 if (!icx->ia_na) 1698 return STATUS_ERROR; 1699 } 1700 1701 ib = ntfs_malloc(icx->block_size); 1702 if (!ib) 1703 return STATUS_ERROR; 1704 1705 ie_succ = ntfs_ie_get_next(icx->entry); 1706 entry_pos = icx->parent_pos[icx->pindex]++; 1707 pindex = icx->pindex; 1708descend: 1709 vcn = ntfs_ie_get_vcn(ie_succ); 1710 if (ntfs_ib_read(icx, vcn, ib)) 1711 goto out; 1712 1713 ie_succ = ntfs_ie_get_first(&ib->index); 1714 1715 if (ntfs_icx_parent_inc(icx)) 1716 goto out; 1717 1718 icx->parent_vcn[icx->pindex] = vcn; 1719 icx->parent_pos[icx->pindex] = 0; 1720 1721 if ((ib->index.ih_flags & NODE_MASK) == INDEX_NODE) 1722 goto descend; 1723 1724 if (ntfs_ih_zero_entry(&ib->index)) { 1725 errno = EIO; 1726 ntfs_log_perror("Empty index block"); 1727 goto out; 1728 } 1729 1730 ie = ntfs_ie_dup(ie_succ); 1731 if (!ie) 1732 goto out; 1733 1734 if (ntfs_ie_add_vcn(&ie)) 1735 goto out2; 1736 1737 ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry)); 1738 1739 if (icx->is_in_root) 1740 ih = &icx->ir->index; 1741 else 1742 ih = &icx->ib->index; 1743 1744 delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length); 1745 new_size = le32_to_cpu(ih->index_length) + delta; 1746 if (delta > 0) { 1747 if (icx->is_in_root) { 1748 ret = ntfs_ir_make_space(icx, new_size); 1749 if (ret != STATUS_OK) 1750 goto out2; 1751 1752 ih = &icx->ir->index; 1753 entry = ntfs_ie_get_by_pos(ih, entry_pos); 1754 1755 } else if (new_size > le32_to_cpu(ih->allocated_size)) { 1756 icx->pindex = pindex; 1757 ret = ntfs_ib_split(icx, icx->ib); 1758 if (ret == STATUS_OK) 1759 ret = STATUS_KEEP_SEARCHING; 1760 goto out2; 1761 } 1762 } 1763 1764 ntfs_ie_delete(ih, entry); 1765 ntfs_ie_insert(ih, ie, entry); 1766 1767 if (icx->is_in_root) { 1768 if (ntfs_ir_truncate(icx, new_size)) 1769 goto out2; 1770 } else 1771 if (ntfs_icx_ib_write(icx)) 1772 goto out2; 1773 1774 ntfs_ie_delete(&ib->index, ie_succ); 1775 1776 if (ntfs_ih_zero_entry(&ib->index)) { 1777 if (ntfs_index_rm_leaf(icx)) 1778 goto out2; 1779 } else 1780 if (ntfs_ib_write(icx, ib)) 1781 goto out2; 1782 1783 ret = STATUS_OK; 1784out2: 1785 free(ie); 1786out: 1787 free(ib); 1788 return ret; 1789} 1790 1791/** 1792 * ntfs_index_rm - remove entry from the index 1793 * @icx: index context describing entry to delete 1794 * 1795 * Delete entry described by @icx from the index. Index context is always 1796 * reinitialized after use of this function, so it can be used for index 1797 * lookup once again. 1798 * 1799 * Return 0 on success or -1 on error with errno set to the error code. 1800 */ 1801/*static JPA*/ 1802int ntfs_index_rm(ntfs_index_context *icx) 1803{ 1804 INDEX_HEADER *ih; 1805 int err, ret = STATUS_OK; 1806 1807 ntfs_log_trace("Entering\n"); 1808 1809 if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) { 1810 ntfs_log_error("Invalid arguments.\n"); 1811 errno = EINVAL; 1812 goto err_out; 1813 } 1814 if (icx->is_in_root) 1815 ih = &icx->ir->index; 1816 else 1817 ih = &icx->ib->index; 1818 1819 if (icx->entry->ie_flags & INDEX_ENTRY_NODE) { 1820 1821 ret = ntfs_index_rm_node(icx); 1822 1823 } else if (icx->is_in_root || !ntfs_ih_one_entry(ih)) { 1824 1825 ntfs_ie_delete(ih, icx->entry); 1826 1827 if (icx->is_in_root) { 1828 err = ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length)); 1829 if (err != STATUS_OK) 1830 goto err_out; 1831 } else 1832 if (ntfs_icx_ib_write(icx)) 1833 goto err_out; 1834 } else { 1835 if (ntfs_index_rm_leaf(icx)) 1836 goto err_out; 1837 } 1838out: 1839 return ret; 1840err_out: 1841 ret = STATUS_ERROR; 1842 goto out; 1843} 1844 1845int ntfs_index_remove(ntfs_inode *dir_ni, ntfs_inode *ni, 1846 const void *key, const int keylen) 1847{ 1848 int ret = STATUS_ERROR; 1849 ntfs_index_context *icx; 1850 1851 icx = ntfs_index_ctx_get(dir_ni, NTFS_INDEX_I30, 4); 1852 if (!icx) 1853 return -1; 1854 1855 while (1) { 1856 1857 if (ntfs_index_lookup(key, keylen, icx)) 1858 goto err_out; 1859 1860 if ((((FILE_NAME_ATTR *)icx->data)->file_attributes & 1861 FILE_ATTR_REPARSE_POINT) 1862 && !ntfs_possible_symlink(ni)) { 1863 errno = EOPNOTSUPP; 1864 goto err_out; 1865 } 1866 1867 ret = ntfs_index_rm(icx); 1868 if (ret == STATUS_ERROR) 1869 goto err_out; 1870 else if (ret == STATUS_OK) 1871 break; 1872 1873 ntfs_inode_mark_dirty(icx->actx->ntfs_ino); 1874 ntfs_index_ctx_reinit(icx); 1875 } 1876 1877 ntfs_inode_mark_dirty(icx->actx->ntfs_ino); 1878out: 1879 ntfs_index_ctx_put(icx); 1880 return ret; 1881err_out: 1882 ret = STATUS_ERROR; 1883 ntfs_log_perror("Delete failed"); 1884 goto out; 1885} 1886 1887/** 1888 * ntfs_index_root_get - read the index root of an attribute 1889 * @ni: open ntfs inode in which the ntfs attribute resides 1890 * @attr: attribute for which we want its index root 1891 * 1892 * This function will read the related index root an ntfs attribute. 1893 * 1894 * On success a buffer is allocated with the content of the index root 1895 * and which needs to be freed when it's not needed anymore. 1896 * 1897 * On error NULL is returned with errno set to the error code. 1898 */ 1899INDEX_ROOT *ntfs_index_root_get(ntfs_inode *ni, ATTR_RECORD *attr) 1900{ 1901 ntfs_attr_search_ctx *ctx; 1902 ntfschar *name; 1903 INDEX_ROOT *root = NULL; 1904 1905 name = (ntfschar *)((u8 *)attr + le16_to_cpu(attr->name_offset)); 1906 1907 if (!ntfs_ir_lookup(ni, name, attr->name_length, &ctx)) 1908 return NULL; 1909 1910 root = ntfs_malloc(sizeof(INDEX_ROOT)); 1911 if (!root) 1912 goto out; 1913 1914 *root = *((INDEX_ROOT *)((u8 *)ctx->attr + 1915 le16_to_cpu(ctx->attr->value_offset))); 1916out: 1917 ntfs_attr_put_search_ctx(ctx); 1918 return root; 1919} 1920 1921 1922/* 1923 * Walk down the index tree (leaf bound) 1924 * until there are no subnode in the first index entry 1925 * returns the entry at the bottom left in subnode 1926 */ 1927 1928static INDEX_ENTRY *ntfs_index_walk_down(INDEX_ENTRY *ie, 1929 ntfs_index_context *ictx) 1930{ 1931 INDEX_ENTRY *entry; 1932 s64 vcn; 1933 1934 entry = ie; 1935 do { 1936 vcn = ntfs_ie_get_vcn(entry); 1937 if (ictx->is_in_root) { 1938 1939 /* down from level zero */ 1940 1941 ictx->ir = (INDEX_ROOT*)NULL; 1942 ictx->ib = (INDEX_BLOCK*)ntfs_malloc(ictx->block_size); 1943 ictx->pindex = 1; 1944 ictx->is_in_root = FALSE; 1945 } else { 1946 1947 /* down from non-zero level */ 1948 1949 ictx->pindex++; 1950 } 1951 ictx->parent_pos[ictx->pindex] = 0; 1952 ictx->parent_vcn[ictx->pindex] = vcn; 1953 if (!ntfs_ib_read(ictx,vcn,ictx->ib)) { 1954 ictx->entry = ntfs_ie_get_first(&ictx->ib->index); 1955 entry = ictx->entry; 1956 } else 1957 entry = (INDEX_ENTRY*)NULL; 1958 } while (entry && (entry->ie_flags & INDEX_ENTRY_NODE)); 1959 return (entry); 1960} 1961 1962/* 1963 * Walk up the index tree (root bound) 1964 * until there is a valid data entry in parent 1965 * returns the parent entry or NULL if no more parent 1966 */ 1967 1968static INDEX_ENTRY *ntfs_index_walk_up(INDEX_ENTRY *ie, 1969 ntfs_index_context *ictx) 1970{ 1971 INDEX_ENTRY *entry; 1972 s64 vcn; 1973 1974 entry = ie; 1975 if (ictx->pindex > 0) { 1976 do { 1977 ictx->pindex--; 1978 if (!ictx->pindex) { 1979 1980 /* we have reached the root */ 1981 1982 free(ictx->ib); 1983 ictx->ib = (INDEX_BLOCK*)NULL; 1984 ictx->is_in_root = TRUE; 1985 /* a new search context is to be allocated */ 1986 if (ictx->actx) 1987 free(ictx->actx); 1988 ictx->ir = ntfs_ir_lookup(ictx->ni, 1989 ictx->name, ictx->name_len, 1990 &ictx->actx); 1991 if (ictx->ir) 1992 entry = ntfs_ie_get_by_pos( 1993 &ictx->ir->index, 1994 ictx->parent_pos[ictx->pindex]); 1995 else 1996 entry = (INDEX_ENTRY*)NULL; 1997 } else { 1998 /* up into non-root node */ 1999 vcn = ictx->parent_vcn[ictx->pindex]; 2000 if (!ntfs_ib_read(ictx,vcn,ictx->ib)) { 2001 entry = ntfs_ie_get_by_pos( 2002 &ictx->ib->index, 2003 ictx->parent_pos[ictx->pindex]); 2004 } else 2005 entry = (INDEX_ENTRY*)NULL; 2006 } 2007 ictx->entry = entry; 2008 } while (entry && (ictx->pindex > 0) 2009 && (entry->ie_flags & INDEX_ENTRY_END)); 2010 } else 2011 entry = (INDEX_ENTRY*)NULL; 2012 return (entry); 2013} 2014 2015/* 2016 * Get next entry in an index according to collating sequence. 2017 * Must be initialized through a ntfs_index_lookup() 2018 * 2019 * Returns next entry or NULL if none 2020 * 2021 * Sample layout : 2022 * 2023 * +---+---+---+---+---+---+---+---+ n ptrs to subnodes 2024 * | | | 10| 25| 33| | | | n-1 keys in between 2025 * +---+---+---+---+---+---+---+---+ no key in last entry 2026 * | A | A 2027 * | | | +-------------------------------+ 2028 * +--------------------------+ | +-----+ | 2029 * | +--+ | | 2030 * V | V | 2031 * +---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+---+ 2032 * | 11| 12| 13| 14| 15| 16| 17| | | | 26| 27| 28| 29| 30| 31| 32| | 2033 * +---+---+---+---+---+---+---+---+ | +---+---+---+---+---+---+---+---+ 2034 * | | 2035 * +-----------------------+ | 2036 * | | 2037 * +---+---+---+---+---+---+---+---+ 2038 * | 18| 19| 20| 21| 22| 23| 24| | 2039 * +---+---+---+---+---+---+---+---+ 2040 */ 2041 2042INDEX_ENTRY *ntfs_index_next(INDEX_ENTRY *ie, ntfs_index_context *ictx) 2043{ 2044 INDEX_ENTRY *next; 2045 int flags; 2046 2047 /* 2048 * lookup() may have returned an invalid node 2049 * when searching for a partial key 2050 * if this happens, walk up 2051 */ 2052 2053 if (ie->ie_flags & INDEX_ENTRY_END) 2054 next = ntfs_index_walk_up(ie, ictx); 2055 else { 2056 /* 2057 * get next entry in same node 2058 * there is always one after any entry with data 2059 */ 2060 2061 next = (INDEX_ENTRY*)((char*)ie + le16_to_cpu(ie->length)); 2062 ++ictx->parent_pos[ictx->pindex]; 2063 flags = next->ie_flags; 2064 2065 /* walk down if it has a subnode */ 2066 2067 if (flags & INDEX_ENTRY_NODE) { 2068 next = ntfs_index_walk_down(next,ictx); 2069 } else { 2070 2071 /* walk up it has no subnode, nor data */ 2072 2073 if (flags & INDEX_ENTRY_END) { 2074 next = ntfs_index_walk_up(next, ictx); 2075 } 2076 } 2077 } 2078 /* return NULL if stuck at end of a block */ 2079 2080 if (next && (next->ie_flags & INDEX_ENTRY_END)) 2081 next = (INDEX_ENTRY*)NULL; 2082 return (next); 2083} 2084 2085 2086