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