fs/ntfs3/index.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  *
   4  * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
   5  *
   6  */
   7
   8 #include <linux/blkdev.h>
   9 #include <linux/buffer_head.h>
  10 #include <linux/fs.h>
  11
  12 #include "debug.h"
  13 #include "ntfs.h"
  14 #include "ntfs_fs.h"
  15
  16 static const struct INDEX_NAMES {
  17         const __le16 *name;
  18         u8 name_len;
  19 } s_index_names[INDEX_MUTEX_TOTAL] = {
  20         { I30_NAME, ARRAY_SIZE(I30_NAME) }, { SII_NAME, ARRAY_SIZE(SII_NAME) },
  21         { SDH_NAME, ARRAY_SIZE(SDH_NAME) }, { SO_NAME, ARRAY_SIZE(SO_NAME) },
  22         { SQ_NAME, ARRAY_SIZE(SQ_NAME) },   { SR_NAME, ARRAY_SIZE(SR_NAME) },
  23 };
  24
  25 /*
  26  * cmp_fnames - Compare two names in index.
  27  *
  28  * if l1 != 0
  29  *   Both names are little endian on-disk ATTR_FILE_NAME structs.
  30  * else
  31  *   key1 - cpu_str, key2 - ATTR_FILE_NAME
  32  */
  33 static int cmp_fnames(const void *key1, size_t l1, const void *key2, size_t l2,
  34                       const void *data)
  35 {
  36         const struct ATTR_FILE_NAME *f2 = key2;
  37         const struct ntfs_sb_info *sbi = data;
  38         const struct ATTR_FILE_NAME *f1;
  39         u16 fsize2;
  40         bool both_case;
  41
  42         if (l2 <= offsetof(struct ATTR_FILE_NAME, name))
  43                 return -1;
  44
  45         fsize2 = fname_full_size(f2);
  46         if (l2 < fsize2)
  47                 return -1;
  48
  49         both_case = f2->type != FILE_NAME_DOS /*&& !sbi->options.nocase*/;
  50         if (!l1) {
  51                 const struct le_str *s2 = (struct le_str *)&f2->name_len;
  52
  53                 /*
  54                  * If names are equal (case insensitive)
  55                  * try to compare it case sensitive.
  56                  */
  57                 return ntfs_cmp_names_cpu(key1, s2, sbi->upcase, both_case);
  58         }
  59
  60         f1 = key1;
  61         return ntfs_cmp_names(f1->name, f1->name_len, f2->name, f2->name_len,
  62                               sbi->upcase, both_case);
  63 }
  64
  65 /*
  66  * cmp_uint - $SII of $Secure and $Q of Quota
  67  */
  68 static int cmp_uint(const void *key1, size_t l1, const void *key2, size_t l2,
  69                     const void *data)
  70 {
  71         const u32 *k1 = key1;
  72         const u32 *k2 = key2;
  73
  74         if (l2 < sizeof(u32))
  75                 return -1;
  76
  77         if (*k1 < *k2)
  78                 return -1;
  79         if (*k1 > *k2)
  80                 return 1;
  81         return 0;
  82 }
  83
  84 /*
  85  * cmp_sdh - $SDH of $Secure
  86  */
  87 static int cmp_sdh(const void *key1, size_t l1, const void *key2, size_t l2,
  88                    const void *data)
  89 {
  90         const struct SECURITY_KEY *k1 = key1;
  91         const struct SECURITY_KEY *k2 = key2;
  92         u32 t1, t2;
  93
  94         if (l2 < sizeof(struct SECURITY_KEY))
  95                 return -1;
  96
  97         t1 = le32_to_cpu(k1->hash);
  98         t2 = le32_to_cpu(k2->hash);
  99
 100         /* First value is a hash value itself. */
 101         if (t1 < t2)
 102                 return -1;
 103         if (t1 > t2)
 104                 return 1;
 105
 106         /* Second value is security Id. */
 107         if (data) {
 108                 t1 = le32_to_cpu(k1->sec_id);
 109                 t2 = le32_to_cpu(k2->sec_id);
 110                 if (t1 < t2)
 111                         return -1;
 112                 if (t1 > t2)
 113                         return 1;
 114         }
 115
 116         return 0;
 117 }
 118
 119 /*
 120  * cmp_uints - $O of ObjId and "$R" for Reparse.
 121  */
 122 static int cmp_uints(const void *key1, size_t l1, const void *key2, size_t l2,
 123                      const void *data)
 124 {
 125         const __le32 *k1 = key1;
 126         const __le32 *k2 = key2;
 127         size_t count;
 128
 129         if ((size_t)data == 1) {
 130                 /*
 131                  * ni_delete_all -> ntfs_remove_reparse ->
 132                  * delete all with this reference.
 133                  * k1, k2 - pointers to REPARSE_KEY
 134                  */
 135
 136                 k1 += 1; // Skip REPARSE_KEY.ReparseTag
 137                 k2 += 1; // Skip REPARSE_KEY.ReparseTag
 138                 if (l2 <= sizeof(int))
 139                         return -1;
 140                 l2 -= sizeof(int);
 141                 if (l1 <= sizeof(int))
 142                         return 1;
 143                 l1 -= sizeof(int);
 144         }
 145
 146         if (l2 < sizeof(int))
 147                 return -1;
 148
 149         for (count = min(l1, l2) >> 2; count > 0; --count, ++k1, ++k2) {
 150                 u32 t1 = le32_to_cpu(*k1);
 151                 u32 t2 = le32_to_cpu(*k2);
 152
 153                 if (t1 > t2)
 154                         return 1;
 155                 if (t1 < t2)
 156                         return -1;
 157         }
 158
 159         if (l1 > l2)
 160                 return 1;
 161         if (l1 < l2)
 162                 return -1;
 163
 164         return 0;
 165 }
 166
 167 static inline NTFS_CMP_FUNC get_cmp_func(const struct INDEX_ROOT *root)
 168 {
 169         switch (root->type) {
 170         case ATTR_NAME:
 171                 if (root->rule == NTFS_COLLATION_TYPE_FILENAME)
 172                         return &cmp_fnames;
 173                 break;
 174         case ATTR_ZERO:
 175                 switch (root->rule) {
 176                 case NTFS_COLLATION_TYPE_UINT:
 177                         return &cmp_uint;
 178                 case NTFS_COLLATION_TYPE_SECURITY_HASH:
 179                         return &cmp_sdh;
 180                 case NTFS_COLLATION_TYPE_UINTS:
 181                         return &cmp_uints;
 182                 default:
 183                         break;
 184                 }
 185                 break;
 186         default:
 187                 break;
 188         }
 189
 190         return NULL;
 191 }
 192
 193 struct bmp_buf {
 194         struct ATTRIB *b;
 195         struct mft_inode *mi;
 196         struct buffer_head *bh;
 197         ulong *buf;
 198         size_t bit;
 199         u32 nbits;
 200         u64 new_valid;
 201 };
 202
 203 static int bmp_buf_get(struct ntfs_index *indx, struct ntfs_inode *ni,
 204                        size_t bit, struct bmp_buf *bbuf)
 205 {
 206         struct ATTRIB *b;
 207         size_t data_size, valid_size, vbo, off = bit >> 3;
 208         struct ntfs_sb_info *sbi = ni->mi.sbi;
 209         CLST vcn = off >> sbi->cluster_bits;
 210         struct ATTR_LIST_ENTRY *le = NULL;
 211         struct buffer_head *bh;
 212         struct super_block *sb;
 213         u32 blocksize;
 214         const struct INDEX_NAMES *in = &s_index_names[indx->type];
 215
 216         bbuf->bh = NULL;
 217
 218         b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
 219                          &vcn, &bbuf->mi);
 220         bbuf->b = b;
 221         if (!b)
 222                 return -EINVAL;
 223
 224         if (!b->non_res) {
 225                 data_size = le32_to_cpu(b->res.data_size);
 226
 227                 if (off >= data_size)
 228                         return -EINVAL;
 229
 230                 bbuf->buf = (ulong *)resident_data(b);
 231                 bbuf->bit = 0;
 232                 bbuf->nbits = data_size * 8;
 233
 234                 return 0;
 235         }
 236
 237         data_size = le64_to_cpu(b->nres.data_size);
 238         if (WARN_ON(off >= data_size)) {
 239                 /* Looks like filesystem error. */
 240                 return -EINVAL;
 241         }
 242
 243         valid_size = le64_to_cpu(b->nres.valid_size);
 244
 245         bh = ntfs_bread_run(sbi, &indx->bitmap_run, off);
 246         if (!bh)
 247                 return -EIO;
 248
 249         if (IS_ERR(bh))
 250                 return PTR_ERR(bh);
 251
 252         bbuf->bh = bh;
 253
 254         if (buffer_locked(bh))
 255                 __wait_on_buffer(bh);
 256
 257         lock_buffer(bh);
 258
 259         sb = sbi->sb;
 260         blocksize = sb->s_blocksize;
 261
 262         vbo = off & ~(size_t)sbi->block_mask;
 263
 264         bbuf->new_valid = vbo + blocksize;
 265         if (bbuf->new_valid <= valid_size)
 266                 bbuf->new_valid = 0;
 267         else if (bbuf->new_valid > data_size)
 268                 bbuf->new_valid = data_size;
 269
 270         if (vbo >= valid_size) {
 271                 memset(bh->b_data, 0, blocksize);
 272         } else if (vbo + blocksize > valid_size) {
 273                 u32 voff = valid_size & sbi->block_mask;
 274
 275                 memset(bh->b_data + voff, 0, blocksize - voff);
 276         }
 277
 278         bbuf->buf = (ulong *)bh->b_data;
 279         bbuf->bit = 8 * (off & ~(size_t)sbi->block_mask);
 280         bbuf->nbits = 8 * blocksize;
 281
 282         return 0;
 283 }
 284
 285 static void bmp_buf_put(struct bmp_buf *bbuf, bool dirty)
 286 {
 287         struct buffer_head *bh = bbuf->bh;
 288         struct ATTRIB *b = bbuf->b;
 289
 290         if (!bh) {
 291                 if (b && !b->non_res && dirty)
 292                         bbuf->mi->dirty = true;
 293                 return;
 294         }
 295
 296         if (!dirty)
 297                 goto out;
 298
 299         if (bbuf->new_valid) {
 300                 b->nres.valid_size = cpu_to_le64(bbuf->new_valid);
 301                 bbuf->mi->dirty = true;
 302         }
 303
 304         set_buffer_uptodate(bh);
 305         mark_buffer_dirty(bh);
 306
 307 out:
 308         unlock_buffer(bh);
 309         put_bh(bh);
 310 }
 311
 312 /*
 313  * indx_mark_used - Mark the bit @bit as used.
 314  */
 315 static int indx_mark_used(struct ntfs_index *indx, struct ntfs_inode *ni,
 316                           size_t bit)
 317 {
 318         int err;
 319         struct bmp_buf bbuf;
 320
 321         err = bmp_buf_get(indx, ni, bit, &bbuf);
 322         if (err)
 323                 return err;
 324
 325         __set_bit(bit - bbuf.bit, bbuf.buf);
 326
 327         bmp_buf_put(&bbuf, true);
 328
 329         return 0;
 330 }
 331
 332 /*
 333  * indx_mark_free - Mark the bit @bit as free.
 334  */
 335 static int indx_mark_free(struct ntfs_index *indx, struct ntfs_inode *ni,
 336                           size_t bit)
 337 {
 338         int err;
 339         struct bmp_buf bbuf;
 340
 341         err = bmp_buf_get(indx, ni, bit, &bbuf);
 342         if (err)
 343                 return err;
 344
 345         __clear_bit(bit - bbuf.bit, bbuf.buf);
 346
 347         bmp_buf_put(&bbuf, true);
 348
 349         return 0;
 350 }
 351
 352 /*
 353  * scan_nres_bitmap
 354  *
 355  * If ntfs_readdir calls this function (indx_used_bit -> scan_nres_bitmap),
 356  * inode is shared locked and no ni_lock.
 357  * Use rw_semaphore for read/write access to bitmap_run.
 358  */
 359 static int scan_nres_bitmap(struct ntfs_inode *ni, struct ATTRIB *bitmap,
 360                             struct ntfs_index *indx, size_t from,
 361                             bool (*fn)(const ulong *buf, u32 bit, u32 bits,
 362                                        size_t *ret),
 363                             size_t *ret)
 364 {
 365         struct ntfs_sb_info *sbi = ni->mi.sbi;
 366         struct super_block *sb = sbi->sb;
 367         struct runs_tree *run = &indx->bitmap_run;
 368         struct rw_semaphore *lock = &indx->run_lock;
 369         u32 nbits = sb->s_blocksize * 8;
 370         u32 blocksize = sb->s_blocksize;
 371         u64 valid_size = le64_to_cpu(bitmap->nres.valid_size);
 372         u64 data_size = le64_to_cpu(bitmap->nres.data_size);
 373         sector_t eblock = bytes_to_block(sb, data_size);
 374         size_t vbo = from >> 3;
 375         sector_t blk = (vbo & sbi->cluster_mask) >> sb->s_blocksize_bits;
 376         sector_t vblock = vbo >> sb->s_blocksize_bits;
 377         sector_t blen, block;
 378         CLST lcn, clen, vcn, vcn_next;
 379         size_t idx;
 380         struct buffer_head *bh;
 381         bool ok;
 382
 383         *ret = MINUS_ONE_T;
 384
 385         if (vblock >= eblock)
 386                 return 0;
 387
 388         from &= nbits - 1;
 389         vcn = vbo >> sbi->cluster_bits;
 390
 391         down_read(lock);
 392         ok = run_lookup_entry(run, vcn, &lcn, &clen, &idx);
 393         up_read(lock);
 394
 395 next_run:
 396         if (!ok) {
 397                 int err;
 398                 const struct INDEX_NAMES *name = &s_index_names[indx->type];
 399
 400                 down_write(lock);
 401                 err = attr_load_runs_vcn(ni, ATTR_BITMAP, name->name,
 402                                          name->name_len, run, vcn);
 403                 up_write(lock);
 404                 if (err)
 405                         return err;
 406                 down_read(lock);
 407                 ok = run_lookup_entry(run, vcn, &lcn, &clen, &idx);
 408                 up_read(lock);
 409                 if (!ok)
 410                         return -EINVAL;
 411         }
 412
 413         blen = (sector_t)clen * sbi->blocks_per_cluster;
 414         block = (sector_t)lcn * sbi->blocks_per_cluster;
 415
 416         for (; blk < blen; blk++, from = 0) {
 417                 bh = ntfs_bread(sb, block + blk);
 418                 if (!bh)
 419                         return -EIO;
 420
 421                 vbo = (u64)vblock << sb->s_blocksize_bits;
 422                 if (vbo >= valid_size) {
 423                         memset(bh->b_data, 0, blocksize);
 424                 } else if (vbo + blocksize > valid_size) {
 425                         u32 voff = valid_size & sbi->block_mask;
 426
 427                         memset(bh->b_data + voff, 0, blocksize - voff);
 428                 }
 429
 430                 if (vbo + blocksize > data_size)
 431                         nbits = 8 * (data_size - vbo);
 432
 433                 ok = nbits > from ? (*fn)((ulong *)bh->b_data, from, nbits, ret)
 434                                   : false;
 435                 put_bh(bh);
 436
 437                 if (ok) {
 438                         *ret += 8 * vbo;
 439                         return 0;
 440                 }
 441
 442                 if (++vblock >= eblock) {
 443                         *ret = MINUS_ONE_T;
 444                         return 0;
 445                 }
 446         }
 447         blk = 0;
 448         vcn_next = vcn + clen;
 449         down_read(lock);
 450         ok = run_get_entry(run, ++idx, &vcn, &lcn, &clen) && vcn == vcn_next;
 451         if (!ok)
 452                 vcn = vcn_next;
 453         up_read(lock);
 454         goto next_run;
 455 }
 456
 457 static bool scan_for_free(const ulong *buf, u32 bit, u32 bits, size_t *ret)
 458 {
 459         size_t pos = find_next_zero_bit(buf, bits, bit);
 460
 461         if (pos >= bits)
 462                 return false;
 463         *ret = pos;
 464         return true;
 465 }
 466
 467 /*
 468  * indx_find_free - Look for free bit.
 469  *
 470  * Return: -1 if no free bits.
 471  */
 472 static int indx_find_free(struct ntfs_index *indx, struct ntfs_inode *ni,
 473                           size_t *bit, struct ATTRIB **bitmap)
 474 {
 475         struct ATTRIB *b;
 476         struct ATTR_LIST_ENTRY *le = NULL;
 477         const struct INDEX_NAMES *in = &s_index_names[indx->type];
 478         int err;
 479
 480         b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
 481                          NULL, NULL);
 482
 483         if (!b)
 484                 return -ENOENT;
 485
 486         *bitmap = b;
 487         *bit = MINUS_ONE_T;
 488
 489         if (!b->non_res) {
 490                 u32 nbits = 8 * le32_to_cpu(b->res.data_size);
 491                 size_t pos = find_next_zero_bit(resident_data(b), nbits, 0);
 492
 493                 if (pos < nbits)
 494                         *bit = pos;
 495         } else {
 496                 err = scan_nres_bitmap(ni, b, indx, 0, &scan_for_free, bit);
 497
 498                 if (err)
 499                         return err;
 500         }
 501
 502         return 0;
 503 }
 504
 505 static bool scan_for_used(const ulong *buf, u32 bit, u32 bits, size_t *ret)
 506 {
 507         size_t pos = find_next_bit(buf, bits, bit);
 508
 509         if (pos >= bits)
 510                 return false;
 511         *ret = pos;
 512         return true;
 513 }
 514
 515 /*
 516  * indx_used_bit - Look for used bit.
 517  *
 518  * Return: MINUS_ONE_T if no used bits.
 519  */
 520 int indx_used_bit(struct ntfs_index *indx, struct ntfs_inode *ni, size_t *bit)
 521 {
 522         struct ATTRIB *b;
 523         struct ATTR_LIST_ENTRY *le = NULL;
 524         size_t from = *bit;
 525         const struct INDEX_NAMES *in = &s_index_names[indx->type];
 526         int err;
 527
 528         b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
 529                          NULL, NULL);
 530
 531         if (!b)
 532                 return -ENOENT;
 533
 534         *bit = MINUS_ONE_T;
 535
 536         if (!b->non_res) {
 537                 u32 nbits = le32_to_cpu(b->res.data_size) * 8;
 538                 size_t pos = find_next_bit(resident_data(b), nbits, from);
 539
 540                 if (pos < nbits)
 541                         *bit = pos;
 542         } else {
 543                 err = scan_nres_bitmap(ni, b, indx, from, &scan_for_used, bit);
 544                 if (err)
 545                         return err;
 546         }
 547
 548         return 0;
 549 }
 550
 551 /*
 552  * hdr_find_split
 553  *
 554  * Find a point at which the index allocation buffer would like to be split.
 555  * NOTE: This function should never return 'END' entry NULL returns on error.
 556  */
 557 static const struct NTFS_DE *hdr_find_split(const struct INDEX_HDR *hdr)
 558 {
 559         size_t o;
 560         const struct NTFS_DE *e = hdr_first_de(hdr);
 561         u32 used_2 = le32_to_cpu(hdr->used) >> 1;
 562         u16 esize;
 563
 564         if (!e || de_is_last(e))
 565                 return NULL;
 566
 567         esize = le16_to_cpu(e->size);
 568         for (o = le32_to_cpu(hdr->de_off) + esize; o < used_2; o += esize) {
 569                 const struct NTFS_DE *p = e;
 570
 571                 e = Add2Ptr(hdr, o);
 572
 573                 /* We must not return END entry. */
 574                 if (de_is_last(e))
 575                         return p;
 576
 577                 esize = le16_to_cpu(e->size);
 578         }
 579
 580         return e;
 581 }
 582
 583 /*
 584  * hdr_insert_head - Insert some entries at the beginning of the buffer.
 585  *
 586  * It is used to insert entries into a newly-created buffer.
 587  */
 588 static const struct NTFS_DE *hdr_insert_head(struct INDEX_HDR *hdr,
 589                                              const void *ins, u32 ins_bytes)
 590 {
 591         u32 to_move;
 592         struct NTFS_DE *e = hdr_first_de(hdr);
 593         u32 used = le32_to_cpu(hdr->used);
 594
 595         if (!e)
 596                 return NULL;
 597
 598         /* Now we just make room for the inserted entries and jam it in. */
 599         to_move = used - le32_to_cpu(hdr->de_off);
 600         memmove(Add2Ptr(e, ins_bytes), e, to_move);
 601         memcpy(e, ins, ins_bytes);
 602         hdr->used = cpu_to_le32(used + ins_bytes);
 603
 604         return e;
 605 }
 606
 607 void fnd_clear(struct ntfs_fnd *fnd)
 608 {
 609         int i;
 610
 611         for (i = 0; i < fnd->level; i++) {
 612                 struct indx_node *n = fnd->nodes[i];
 613
 614                 if (!n)
 615                         continue;
 616
 617                 put_indx_node(n);
 618                 fnd->nodes[i] = NULL;
 619         }
 620         fnd->level = 0;
 621         fnd->root_de = NULL;
 622 }
 623
 624 static int fnd_push(struct ntfs_fnd *fnd, struct indx_node *n,
 625                     struct NTFS_DE *e)
 626 {
 627         int i;
 628
 629         i = fnd->level;
 630         if (i < 0 || i >= ARRAY_SIZE(fnd->nodes))
 631                 return -EINVAL;
 632         fnd->nodes[i] = n;
 633         fnd->de[i] = e;
 634         fnd->level += 1;
 635         return 0;
 636 }
 637
 638 static struct indx_node *fnd_pop(struct ntfs_fnd *fnd)
 639 {
 640         struct indx_node *n;
 641         int i = fnd->level;
 642
 643         i -= 1;
 644         n = fnd->nodes[i];
 645         fnd->nodes[i] = NULL;
 646         fnd->level = i;
 647
 648         return n;
 649 }
 650
 651 static bool fnd_is_empty(struct ntfs_fnd *fnd)
 652 {
 653         if (!fnd->level)
 654                 return !fnd->root_de;
 655
 656         return !fnd->de[fnd->level - 1];
 657 }
 658
 659 /*
 660  * hdr_find_e - Locate an entry the index buffer.
 661  *
 662  * If no matching entry is found, it returns the first entry which is greater
 663  * than the desired entry If the search key is greater than all the entries the
 664  * buffer, it returns the 'end' entry. This function does a binary search of the
 665  * current index buffer, for the first entry that is <= to the search value.
 666  *
 667  * Return: NULL if error.
 668  */
 669 static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 670                                   const struct INDEX_HDR *hdr, const void *key,
 671                                   size_t key_len, const void *ctx, int *diff)
 672 {
 673         struct NTFS_DE *e;
 674         NTFS_CMP_FUNC cmp = indx->cmp;
 675         u32 e_size, e_key_len;
 676         u32 end = le32_to_cpu(hdr->used);
 677         u32 off = le32_to_cpu(hdr->de_off);
 678
 679 #ifdef NTFS3_INDEX_BINARY_SEARCH
 680         struct NTFS_DE *found = NULL;
 681         int min_idx = 0, mid_idx, max_idx = 0;
 682         int diff2;
 683         u16 offs[64];
 684
 685         if (end > 0x10000)
 686                 goto next;
 687
 688 fill_table:
 689         if (off + sizeof(struct NTFS_DE) > end)
 690                 return NULL;
 691
 692         e = Add2Ptr(hdr, off);
 693         e_size = le16_to_cpu(e->size);
 694
 695         if (e_size < sizeof(struct NTFS_DE) || off + e_size > end)
 696                 return NULL;
 697
 698         if (!de_is_last(e)) {
 699                 offs[max_idx] = off;
 700                 off += e_size;
 701
 702                 max_idx++;
 703                 if (max_idx < ARRAY_SIZE(offs))
 704                         goto fill_table;
 705
 706                 max_idx--;
 707         }
 708
 709 binary_search:
 710         e_key_len = le16_to_cpu(e->key_size);
 711
 712         diff2 = (*cmp)(key, key_len, e + 1, e_key_len, ctx);
 713         if (diff2 > 0) {
 714                 if (found) {
 715                         min_idx = mid_idx + 1;
 716                 } else {
 717                         if (de_is_last(e))
 718                                 return NULL;
 719
 720                         max_idx = 0;
 721                         goto fill_table;
 722                 }
 723         } else if (diff2 < 0) {
 724                 if (found)
 725                         max_idx = mid_idx - 1;
 726                 else
 727                         max_idx--;
 728
 729                 found = e;
 730         } else {
 731                 *diff = 0;
 732                 return e;
 733         }
 734
 735         if (min_idx > max_idx) {
 736                 *diff = -1;
 737                 return found;
 738         }
 739
 740         mid_idx = (min_idx + max_idx) >> 1;
 741         e = Add2Ptr(hdr, offs[mid_idx]);
 742
 743         goto binary_search;
 744 #endif
 745
 746 next:
 747         /*
 748          * Entries index are sorted.
 749          * Enumerate all entries until we find entry
 750          * that is <= to the search value.
 751          */
 752         if (off + sizeof(struct NTFS_DE) > end)
 753                 return NULL;
 754
 755         e = Add2Ptr(hdr, off);
 756         e_size = le16_to_cpu(e->size);
 757
 758         if (e_size < sizeof(struct NTFS_DE) || off + e_size > end)
 759                 return NULL;
 760
 761         off += e_size;
 762
 763         e_key_len = le16_to_cpu(e->key_size);
 764
 765         *diff = (*cmp)(key, key_len, e + 1, e_key_len, ctx);
 766         if (!*diff)
 767                 return e;
 768
 769         if (*diff <= 0)
 770                 return e;
 771
 772         if (de_is_last(e)) {
 773                 *diff = 1;
 774                 return e;
 775         }
 776         goto next;
 777 }
 778
 779 /*
 780  * hdr_insert_de - Insert an index entry into the buffer.
 781  *
 782  * 'before' should be a pointer previously returned from hdr_find_e.
 783  */
 784 static struct NTFS_DE *hdr_insert_de(const struct ntfs_index *indx,
 785                                      struct INDEX_HDR *hdr,
 786                                      const struct NTFS_DE *de,
 787                                      struct NTFS_DE *before, const void *ctx)
 788 {
 789         int diff;
 790         size_t off = PtrOffset(hdr, before);
 791         u32 used = le32_to_cpu(hdr->used);
 792         u32 total = le32_to_cpu(hdr->total);
 793         u16 de_size = le16_to_cpu(de->size);
 794
 795         /* First, check to see if there's enough room. */
 796         if (used + de_size > total)
 797                 return NULL;
 798
 799         /* We know there's enough space, so we know we'll succeed. */
 800         if (before) {
 801                 /* Check that before is inside Index. */
 802                 if (off >= used || off < le32_to_cpu(hdr->de_off) ||
 803                     off + le16_to_cpu(before->size) > total) {
 804                         return NULL;
 805                 }
 806                 goto ok;
 807         }
 808         /* No insert point is applied. Get it manually. */
 809         before = hdr_find_e(indx, hdr, de + 1, le16_to_cpu(de->key_size), ctx,
 810                             &diff);
 811         if (!before)
 812                 return NULL;
 813         off = PtrOffset(hdr, before);
 814
 815 ok:
 816         /* Now we just make room for the entry and jam it in. */
 817         memmove(Add2Ptr(before, de_size), before, used - off);
 818
 819         hdr->used = cpu_to_le32(used + de_size);
 820         memcpy(before, de, de_size);
 821
 822         return before;
 823 }
 824
 825 /*
 826  * hdr_delete_de - Remove an entry from the index buffer.
 827  */
 828 static inline struct NTFS_DE *hdr_delete_de(struct INDEX_HDR *hdr,
 829                                             struct NTFS_DE *re)
 830 {
 831         u32 used = le32_to_cpu(hdr->used);
 832         u16 esize = le16_to_cpu(re->size);
 833         u32 off = PtrOffset(hdr, re);
 834         int bytes = used - (off + esize);
 835
 836         if (off >= used || esize < sizeof(struct NTFS_DE) ||
 837             bytes < sizeof(struct NTFS_DE))
 838                 return NULL;
 839
 840         hdr->used = cpu_to_le32(used - esize);
 841         memmove(re, Add2Ptr(re, esize), bytes);
 842
 843         return re;
 844 }
 845
 846 void indx_clear(struct ntfs_index *indx)
 847 {
 848         run_close(&indx->alloc_run);
 849         run_close(&indx->bitmap_run);
 850 }
 851
 852 int indx_init(struct ntfs_index *indx, struct ntfs_sb_info *sbi,
 853               const struct ATTRIB *attr, enum index_mutex_classed type)
 854 {
 855         u32 t32;
 856         const struct INDEX_ROOT *root = resident_data(attr);
 857
 858         /* Check root fields. */
 859         if (!root->index_block_clst)
 860                 return -EINVAL;
 861
 862         indx->type = type;
 863         indx->idx2vbn_bits = __ffs(root->index_block_clst);
 864
 865         t32 = le32_to_cpu(root->index_block_size);
 866         indx->index_bits = blksize_bits(t32);
 867
 868         /* Check index record size. */
 869         if (t32 < sbi->cluster_size) {
 870                 /* Index record is smaller than a cluster, use 512 blocks. */
 871                 if (t32 != root->index_block_clst * SECTOR_SIZE)
 872                         return -EINVAL;
 873
 874                 /* Check alignment to a cluster. */
 875                 if ((sbi->cluster_size >> SECTOR_SHIFT) &
 876                     (root->index_block_clst - 1)) {
 877                         return -EINVAL;
 878                 }
 879
 880                 indx->vbn2vbo_bits = SECTOR_SHIFT;
 881         } else {
 882                 /* Index record must be a multiple of cluster size. */
 883                 if (t32 != root->index_block_clst << sbi->cluster_bits)
 884                         return -EINVAL;
 885
 886                 indx->vbn2vbo_bits = sbi->cluster_bits;
 887         }
 888
 889         init_rwsem(&indx->run_lock);
 890
 891         indx->cmp = get_cmp_func(root);
 892         return indx->cmp ? 0 : -EINVAL;
 893 }
 894
 895 static struct indx_node *indx_new(struct ntfs_index *indx,
 896                                   struct ntfs_inode *ni, CLST vbn,
 897                                   const __le64 *sub_vbn)
 898 {
 899         int err;
 900         struct NTFS_DE *e;
 901         struct indx_node *r;
 902         struct INDEX_HDR *hdr;
 903         struct INDEX_BUFFER *index;
 904         u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
 905         u32 bytes = 1u << indx->index_bits;
 906         u16 fn;
 907         u32 eo;
 908
 909         r = kzalloc(sizeof(struct indx_node), GFP_NOFS);
 910         if (!r)
 911                 return ERR_PTR(-ENOMEM);
 912
 913         index = kzalloc(bytes, GFP_NOFS);
 914         if (!index) {
 915                 kfree(r);
 916                 return ERR_PTR(-ENOMEM);
 917         }
 918
 919         err = ntfs_get_bh(ni->mi.sbi, &indx->alloc_run, vbo, bytes, &r->nb);
 920
 921         if (err) {
 922                 kfree(index);
 923                 kfree(r);
 924                 return ERR_PTR(err);
 925         }
 926
 927         /* Create header. */
 928         index->rhdr.sign = NTFS_INDX_SIGNATURE;
 929         index->rhdr.fix_off = cpu_to_le16(sizeof(struct INDEX_BUFFER)); // 0x28
 930         fn = (bytes >> SECTOR_SHIFT) + 1; // 9
 931         index->rhdr.fix_num = cpu_to_le16(fn);
 932         index->vbn = cpu_to_le64(vbn);
 933         hdr = &index->ihdr;
 934         eo = ALIGN(sizeof(struct INDEX_BUFFER) + fn * sizeof(short), 8);
 935         hdr->de_off = cpu_to_le32(eo);
 936
 937         e = Add2Ptr(hdr, eo);
 938
 939         if (sub_vbn) {
 940                 e->flags = NTFS_IE_LAST | NTFS_IE_HAS_SUBNODES;
 941                 e->size = cpu_to_le16(sizeof(struct NTFS_DE) + sizeof(u64));
 942                 hdr->used =
 943                         cpu_to_le32(eo + sizeof(struct NTFS_DE) + sizeof(u64));
 944                 de_set_vbn_le(e, *sub_vbn);
 945                 hdr->flags = 1;
 946         } else {
 947                 e->size = cpu_to_le16(sizeof(struct NTFS_DE));
 948                 hdr->used = cpu_to_le32(eo + sizeof(struct NTFS_DE));
 949                 e->flags = NTFS_IE_LAST;
 950         }
 951
 952         hdr->total = cpu_to_le32(bytes - offsetof(struct INDEX_BUFFER, ihdr));
 953
 954         r->index = index;
 955         return r;
 956 }
 957
 958 struct INDEX_ROOT *indx_get_root(struct ntfs_index *indx, struct ntfs_inode *ni,
 959                                  struct ATTRIB **attr, struct mft_inode **mi)
 960 {
 961         struct ATTR_LIST_ENTRY *le = NULL;
 962         struct ATTRIB *a;
 963         const struct INDEX_NAMES *in = &s_index_names[indx->type];
 964
 965         a = ni_find_attr(ni, NULL, &le, ATTR_ROOT, in->name, in->name_len, NULL,
 966                          mi);
 967         if (!a)
 968                 return NULL;
 969
 970         if (attr)
 971                 *attr = a;
 972
 973         return resident_data_ex(a, sizeof(struct INDEX_ROOT));
 974 }
 975
 976 static int indx_write(struct ntfs_index *indx, struct ntfs_inode *ni,
 977                       struct indx_node *node, int sync)
 978 {
 979         struct INDEX_BUFFER *ib = node->index;
 980
 981         return ntfs_write_bh(ni->mi.sbi, &ib->rhdr, &node->nb, sync);
 982 }
 983
 984 /*
 985  * indx_read
 986  *
 987  * If ntfs_readdir calls this function
 988  * inode is shared locked and no ni_lock.
 989  * Use rw_semaphore for read/write access to alloc_run.
 990  */
 991 int indx_read(struct ntfs_index *indx, struct ntfs_inode *ni, CLST vbn,
 992               struct indx_node **node)
 993 {
 994         int err;
 995         struct INDEX_BUFFER *ib;
 996         struct runs_tree *run = &indx->alloc_run;
 997         struct rw_semaphore *lock = &indx->run_lock;
 998         u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
 999         u32 bytes = 1u << indx->index_bits;
1000         struct indx_node *in = *node;
1001         const struct INDEX_NAMES *name;
1002
1003         if (!in) {
1004                 in = kzalloc(sizeof(struct indx_node), GFP_NOFS);
1005                 if (!in)
1006                         return -ENOMEM;
1007         } else {
1008                 nb_put(&in->nb);
1009         }
1010
1011         ib = in->index;
1012         if (!ib) {
1013                 ib = kmalloc(bytes, GFP_NOFS);
1014                 if (!ib) {
1015                         err = -ENOMEM;
1016                         goto out;
1017                 }
1018         }
1019
1020         down_read(lock);
1021         err = ntfs_read_bh(ni->mi.sbi, run, vbo, &ib->rhdr, bytes, &in->nb);
1022         up_read(lock);
1023         if (!err)
1024                 goto ok;
1025
1026         if (err == -E_NTFS_FIXUP)
1027                 goto ok;
1028
1029         if (err != -ENOENT)
1030                 goto out;
1031
1032         name = &s_index_names[indx->type];
1033         down_write(lock);
1034         err = attr_load_runs_range(ni, ATTR_ALLOC, name->name, name->name_len,
1035                                    run, vbo, vbo + bytes);
1036         up_write(lock);
1037         if (err)
1038                 goto out;
1039
1040         down_read(lock);
1041         err = ntfs_read_bh(ni->mi.sbi, run, vbo, &ib->rhdr, bytes, &in->nb);
1042         up_read(lock);
1043         if (err == -E_NTFS_FIXUP)
1044                 goto ok;
1045
1046         if (err)
1047                 goto out;
1048
1049 ok:
1050         if (err == -E_NTFS_FIXUP) {
1051                 ntfs_write_bh(ni->mi.sbi, &ib->rhdr, &in->nb, 0);
1052                 err = 0;
1053         }
1054
1055         in->index = ib;
1056         *node = in;
1057
1058 out:
1059         if (ib != in->index)
1060                 kfree(ib);
1061
1062         if (*node != in) {
1063                 nb_put(&in->nb);
1064                 kfree(in);
1065         }
1066
1067         return err;
1068 }
1069
1070 /*
1071  * indx_find - Scan NTFS directory for given entry.
1072  */
1073 int indx_find(struct ntfs_index *indx, struct ntfs_inode *ni,
1074               const struct INDEX_ROOT *root, const void *key, size_t key_len,
1075               const void *ctx, int *diff, struct NTFS_DE **entry,
1076               struct ntfs_fnd *fnd)
1077 {
1078         int err;
1079         struct NTFS_DE *e;
1080         const struct INDEX_HDR *hdr;
1081         struct indx_node *node;
1082
1083         if (!root)
1084                 root = indx_get_root(&ni->dir, ni, NULL, NULL);
1085
1086         if (!root) {
1087                 err = -EINVAL;
1088                 goto out;
1089         }
1090
1091         hdr = &root->ihdr;
1092
1093         /* Check cache. */
1094         e = fnd->level ? fnd->de[fnd->level - 1] : fnd->root_de;
1095         if (e && !de_is_last(e) &&
1096             !(*indx->cmp)(key, key_len, e + 1, le16_to_cpu(e->key_size), ctx)) {
1097                 *entry = e;
1098                 *diff = 0;
1099                 return 0;
1100         }
1101
1102         /* Soft finder reset. */
1103         fnd_clear(fnd);
1104
1105         /* Lookup entry that is <= to the search value. */
1106         e = hdr_find_e(indx, hdr, key, key_len, ctx, diff);
1107         if (!e)
1108                 return -EINVAL;
1109
1110         if (fnd)
1111                 fnd->root_de = e;
1112
1113         err = 0;
1114
1115         for (;;) {
1116                 node = NULL;
1117                 if (*diff >= 0 || !de_has_vcn_ex(e)) {
1118                         *entry = e;
1119                         goto out;
1120                 }
1121
1122                 /* Read next level. */
1123                 err = indx_read(indx, ni, de_get_vbn(e), &node);
1124                 if (err)
1125                         goto out;
1126
1127                 /* Lookup entry that is <= to the search value. */
1128                 e = hdr_find_e(indx, &node->index->ihdr, key, key_len, ctx,
1129                                diff);
1130                 if (!e) {
1131                         err = -EINVAL;
1132                         put_indx_node(node);
1133                         goto out;
1134                 }
1135
1136                 fnd_push(fnd, node, e);
1137         }
1138
1139 out:
1140         return err;
1141 }
1142
1143 int indx_find_sort(struct ntfs_index *indx, struct ntfs_inode *ni,
1144                    const struct INDEX_ROOT *root, struct NTFS_DE **entry,
1145                    struct ntfs_fnd *fnd)
1146 {
1147         int err;
1148         struct indx_node *n = NULL;
1149         struct NTFS_DE *e;
1150         size_t iter = 0;
1151         int level = fnd->level;
1152
1153         if (!*entry) {
1154                 /* Start find. */
1155                 e = hdr_first_de(&root->ihdr);
1156                 if (!e)
1157                         return 0;
1158                 fnd_clear(fnd);
1159                 fnd->root_de = e;
1160         } else if (!level) {
1161                 if (de_is_last(fnd->root_de)) {
1162                         *entry = NULL;
1163                         return 0;
1164                 }
1165
1166                 e = hdr_next_de(&root->ihdr, fnd->root_de);
1167                 if (!e)
1168                         return -EINVAL;
1169                 fnd->root_de = e;
1170         } else {
1171                 n = fnd->nodes[level - 1];
1172                 e = fnd->de[level - 1];
1173
1174                 if (de_is_last(e))
1175                         goto pop_level;
1176
1177                 e = hdr_next_de(&n->index->ihdr, e);
1178                 if (!e)
1179                         return -EINVAL;
1180
1181                 fnd->de[level - 1] = e;
1182         }
1183
1184         /* Just to avoid tree cycle. */
1185 next_iter:
1186         if (iter++ >= 1000)
1187                 return -EINVAL;
1188
1189         while (de_has_vcn_ex(e)) {
1190                 if (le16_to_cpu(e->size) <
1191                     sizeof(struct NTFS_DE) + sizeof(u64)) {
1192                         if (n) {
1193                                 fnd_pop(fnd);
1194                                 kfree(n);
1195                         }
1196                         return -EINVAL;
1197                 }
1198
1199                 /* Read next level. */
1200                 err = indx_read(indx, ni, de_get_vbn(e), &n);
1201                 if (err)
1202                         return err;
1203
1204                 /* Try next level. */
1205                 e = hdr_first_de(&n->index->ihdr);
1206                 if (!e) {
1207                         kfree(n);
1208                         return -EINVAL;
1209                 }
1210
1211                 fnd_push(fnd, n, e);
1212         }
1213
1214         if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1215                 *entry = e;
1216                 return 0;
1217         }
1218
1219 pop_level:
1220         for (;;) {
1221                 if (!de_is_last(e))
1222                         goto next_iter;
1223
1224                 /* Pop one level. */
1225                 if (n) {
1226                         fnd_pop(fnd);
1227                         kfree(n);
1228                 }
1229
1230                 level = fnd->level;
1231
1232                 if (level) {
1233                         n = fnd->nodes[level - 1];
1234                         e = fnd->de[level - 1];
1235                 } else if (fnd->root_de) {
1236                         n = NULL;
1237                         e = fnd->root_de;
1238                         fnd->root_de = NULL;
1239                 } else {
1240                         *entry = NULL;
1241                         return 0;
1242                 }
1243
1244                 if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1245                         *entry = e;
1246                         if (!fnd->root_de)
1247                                 fnd->root_de = e;
1248                         return 0;
1249                 }
1250         }
1251 }
1252
1253 int indx_find_raw(struct ntfs_index *indx, struct ntfs_inode *ni,
1254                   const struct INDEX_ROOT *root, struct NTFS_DE **entry,
1255                   size_t *off, struct ntfs_fnd *fnd)
1256 {
1257         int err;
1258         struct indx_node *n = NULL;
1259         struct NTFS_DE *e = NULL;
1260         struct NTFS_DE *e2;
1261         size_t bit;
1262         CLST next_used_vbn;
1263         CLST next_vbn;
1264         u32 record_size = ni->mi.sbi->record_size;
1265
1266         /* Use non sorted algorithm. */
1267         if (!*entry) {
1268                 /* This is the first call. */
1269                 e = hdr_first_de(&root->ihdr);
1270                 if (!e)
1271                         return 0;
1272                 fnd_clear(fnd);
1273                 fnd->root_de = e;
1274
1275                 /* The first call with setup of initial element. */
1276                 if (*off >= record_size) {
1277                         next_vbn = (((*off - record_size) >> indx->index_bits))
1278                                    << indx->idx2vbn_bits;
1279                         /* Jump inside cycle 'for'. */
1280                         goto next;
1281                 }
1282
1283                 /* Start enumeration from root. */
1284                 *off = 0;
1285         } else if (!fnd->root_de)
1286                 return -EINVAL;
1287
1288         for (;;) {
1289                 /* Check if current entry can be used. */
1290                 if (e && le16_to_cpu(e->size) > sizeof(struct NTFS_DE))
1291                         goto ok;
1292
1293                 if (!fnd->level) {
1294                         /* Continue to enumerate root. */
1295                         if (!de_is_last(fnd->root_de)) {
1296                                 e = hdr_next_de(&root->ihdr, fnd->root_de);
1297                                 if (!e)
1298                                         return -EINVAL;
1299                                 fnd->root_de = e;
1300                                 continue;
1301                         }
1302
1303                         /* Start to enumerate indexes from 0. */
1304                         next_vbn = 0;
1305                 } else {
1306                         /* Continue to enumerate indexes. */
1307                         e2 = fnd->de[fnd->level - 1];
1308
1309                         n = fnd->nodes[fnd->level - 1];
1310
1311                         if (!de_is_last(e2)) {
1312                                 e = hdr_next_de(&n->index->ihdr, e2);
1313                                 if (!e)
1314                                         return -EINVAL;
1315                                 fnd->de[fnd->level - 1] = e;
1316                                 continue;
1317                         }
1318
1319                         /* Continue with next index. */
1320                         next_vbn = le64_to_cpu(n->index->vbn) +
1321                                    root->index_block_clst;
1322                 }
1323
1324 next:
1325                 /* Release current index. */
1326                 if (n) {
1327                         fnd_pop(fnd);
1328                         put_indx_node(n);
1329                         n = NULL;
1330                 }
1331
1332                 /* Skip all free indexes. */
1333                 bit = next_vbn >> indx->idx2vbn_bits;
1334                 err = indx_used_bit(indx, ni, &bit);
1335                 if (err == -ENOENT || bit == MINUS_ONE_T) {
1336                         /* No used indexes. */
1337                         *entry = NULL;
1338                         return 0;
1339                 }
1340
1341                 next_used_vbn = bit << indx->idx2vbn_bits;
1342
1343                 /* Read buffer into memory. */
1344                 err = indx_read(indx, ni, next_used_vbn, &n);
1345                 if (err)
1346                         return err;
1347
1348                 e = hdr_first_de(&n->index->ihdr);
1349                 fnd_push(fnd, n, e);
1350                 if (!e)
1351                         return -EINVAL;
1352         }
1353
1354 ok:
1355         /* Return offset to restore enumerator if necessary. */
1356         if (!n) {
1357                 /* 'e' points in root, */
1358                 *off = PtrOffset(&root->ihdr, e);
1359         } else {
1360                 /* 'e' points in index, */
1361                 *off = (le64_to_cpu(n->index->vbn) << indx->vbn2vbo_bits) +
1362                        record_size + PtrOffset(&n->index->ihdr, e);
1363         }
1364
1365         *entry = e;
1366         return 0;
1367 }
1368
1369 /*
1370  * indx_create_allocate - Create "Allocation + Bitmap" attributes.
1371  */
1372 static int indx_create_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
1373                                 CLST *vbn)
1374 {
1375         int err;
1376         struct ntfs_sb_info *sbi = ni->mi.sbi;
1377         struct ATTRIB *bitmap;
1378         struct ATTRIB *alloc;
1379         u32 data_size = 1u << indx->index_bits;
1380         u32 alloc_size = ntfs_up_cluster(sbi, data_size);
1381         CLST len = alloc_size >> sbi->cluster_bits;
1382         const struct INDEX_NAMES *in = &s_index_names[indx->type];
1383         CLST alen;
1384         struct runs_tree run;
1385
1386         run_init(&run);
1387
1388         err = attr_allocate_clusters(sbi, &run, 0, 0, len, NULL, 0, &alen, 0,
1389                                      NULL);
1390         if (err)
1391                 goto out;
1392
1393         err = ni_insert_nonresident(ni, ATTR_ALLOC, in->name, in->name_len,
1394                                     &run, 0, len, 0, &alloc, NULL);
1395         if (err)
1396                 goto out1;
1397
1398         alloc->nres.valid_size = alloc->nres.data_size = cpu_to_le64(data_size);
1399
1400         err = ni_insert_resident(ni, bitmap_size(1), ATTR_BITMAP, in->name,
1401                                  in->name_len, &bitmap, NULL, NULL);
1402         if (err)
1403                 goto out2;
1404
1405         if (in->name == I30_NAME) {
1406                 ni->vfs_inode.i_size = data_size;
1407                 inode_set_bytes(&ni->vfs_inode, alloc_size);
1408         }
1409
1410         memcpy(&indx->alloc_run, &run, sizeof(run));
1411
1412         *vbn = 0;
1413
1414         return 0;
1415
1416 out2:
1417         mi_remove_attr(NULL, &ni->mi, alloc);
1418
1419 out1:
1420         run_deallocate(sbi, &run, false);
1421
1422 out:
1423         return err;
1424 }
1425
1426 /*
1427  * indx_add_allocate - Add clusters to index.
1428  */
1429 static int indx_add_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
1430                              CLST *vbn)
1431 {
1432         int err;
1433         size_t bit;
1434         u64 data_size;
1435         u64 bmp_size, bmp_size_v;
1436         struct ATTRIB *bmp, *alloc;
1437         struct mft_inode *mi;
1438         const struct INDEX_NAMES *in = &s_index_names[indx->type];
1439
1440         err = indx_find_free(indx, ni, &bit, &bmp);
1441         if (err)
1442                 goto out1;
1443
1444         if (bit != MINUS_ONE_T) {
1445                 bmp = NULL;
1446         } else {
1447                 if (bmp->non_res) {
1448                         bmp_size = le64_to_cpu(bmp->nres.data_size);
1449                         bmp_size_v = le64_to_cpu(bmp->nres.valid_size);
1450                 } else {
1451                         bmp_size = bmp_size_v = le32_to_cpu(bmp->res.data_size);
1452                 }
1453
1454                 bit = bmp_size << 3;
1455         }
1456
1457         data_size = (u64)(bit + 1) << indx->index_bits;
1458
1459         if (bmp) {
1460                 /* Increase bitmap. */
1461                 err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
1462                                     &indx->bitmap_run, bitmap_size(bit + 1),
1463                                     NULL, true, NULL);
1464                 if (err)
1465                         goto out1;
1466         }
1467
1468         alloc = ni_find_attr(ni, NULL, NULL, ATTR_ALLOC, in->name, in->name_len,
1469                              NULL, &mi);
1470         if (!alloc) {
1471                 err = -EINVAL;
1472                 if (bmp)
1473                         goto out2;
1474                 goto out1;
1475         }
1476
1477         /* Increase allocation. */
1478         err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
1479                             &indx->alloc_run, data_size, &data_size, true,
1480                             NULL);
1481         if (err) {
1482                 if (bmp)
1483                         goto out2;
1484                 goto out1;
1485         }
1486
1487         *vbn = bit << indx->idx2vbn_bits;
1488
1489         return 0;
1490
1491 out2:
1492         /* Ops. No space? */
1493         attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
1494                       &indx->bitmap_run, bmp_size, &bmp_size_v, false, NULL);
1495
1496 out1:
1497         return err;
1498 }
1499
1500 /*
1501  * indx_insert_into_root - Attempt to insert an entry into the index root.
1502  *
1503  * @undo - True if we undoing previous remove.
1504  * If necessary, it will twiddle the index b-tree.
1505  */
1506 static int indx_insert_into_root(struct ntfs_index *indx, struct ntfs_inode *ni,
1507                                  const struct NTFS_DE *new_de,
1508                                  struct NTFS_DE *root_de, const void *ctx,
1509                                  struct ntfs_fnd *fnd, bool undo)
1510 {
1511         int err = 0;
1512         struct NTFS_DE *e, *e0, *re;
1513         struct mft_inode *mi;
1514         struct ATTRIB *attr;
1515         struct INDEX_HDR *hdr;
1516         struct indx_node *n;
1517         CLST new_vbn;
1518         __le64 *sub_vbn, t_vbn;
1519         u16 new_de_size;
1520         u32 hdr_used, hdr_total, asize, to_move;
1521         u32 root_size, new_root_size;
1522         struct ntfs_sb_info *sbi;
1523         int ds_root;
1524         struct INDEX_ROOT *root, *a_root;
1525
1526         /* Get the record this root placed in. */
1527         root = indx_get_root(indx, ni, &attr, &mi);
1528         if (!root)
1529                 return -EINVAL;
1530
1531         /*
1532          * Try easy case:
1533          * hdr_insert_de will succeed if there's
1534          * room the root for the new entry.
1535          */
1536         hdr = &root->ihdr;
1537         sbi = ni->mi.sbi;
1538         new_de_size = le16_to_cpu(new_de->size);
1539         hdr_used = le32_to_cpu(hdr->used);
1540         hdr_total = le32_to_cpu(hdr->total);
1541         asize = le32_to_cpu(attr->size);
1542         root_size = le32_to_cpu(attr->res.data_size);
1543
1544         ds_root = new_de_size + hdr_used - hdr_total;
1545
1546         /* If 'undo' is set then reduce requirements. */
1547         if ((undo || asize + ds_root < sbi->max_bytes_per_attr) &&
1548             mi_resize_attr(mi, attr, ds_root)) {
1549                 hdr->total = cpu_to_le32(hdr_total + ds_root);
1550                 e = hdr_insert_de(indx, hdr, new_de, root_de, ctx);
1551                 WARN_ON(!e);
1552                 fnd_clear(fnd);
1553                 fnd->root_de = e;
1554
1555                 return 0;
1556         }
1557
1558         /* Make a copy of root attribute to restore if error. */
1559         a_root = kmemdup(attr, asize, GFP_NOFS);
1560         if (!a_root)
1561                 return -ENOMEM;
1562
1563         /*
1564          * Copy all the non-end entries from
1565          * the index root to the new buffer.
1566          */
1567         to_move = 0;
1568         e0 = hdr_first_de(hdr);
1569
1570         /* Calculate the size to copy. */
1571         for (e = e0;; e = hdr_next_de(hdr, e)) {
1572                 if (!e) {
1573                         err = -EINVAL;
1574                         goto out_free_root;
1575                 }
1576
1577                 if (de_is_last(e))
1578                         break;
1579                 to_move += le16_to_cpu(e->size);
1580         }
1581
1582         if (!to_move) {
1583                 re = NULL;
1584         } else {
1585                 re = kmemdup(e0, to_move, GFP_NOFS);
1586                 if (!re) {
1587                         err = -ENOMEM;
1588                         goto out_free_root;
1589                 }
1590         }
1591
1592         sub_vbn = NULL;
1593         if (de_has_vcn(e)) {
1594                 t_vbn = de_get_vbn_le(e);
1595                 sub_vbn = &t_vbn;
1596         }
1597
1598         new_root_size = sizeof(struct INDEX_ROOT) + sizeof(struct NTFS_DE) +
1599                         sizeof(u64);
1600         ds_root = new_root_size - root_size;
1601
1602         if (ds_root > 0 && asize + ds_root > sbi->max_bytes_per_attr) {
1603                 /* Make root external. */
1604                 err = -EOPNOTSUPP;
1605                 goto out_free_re;
1606         }
1607
1608         if (ds_root)
1609                 mi_resize_attr(mi, attr, ds_root);
1610
1611         /* Fill first entry (vcn will be set later). */
1612         e = (struct NTFS_DE *)(root + 1);
1613         memset(e, 0, sizeof(struct NTFS_DE));
1614         e->size = cpu_to_le16(sizeof(struct NTFS_DE) + sizeof(u64));
1615         e->flags = NTFS_IE_HAS_SUBNODES | NTFS_IE_LAST;
1616
1617         hdr->flags = 1;
1618         hdr->used = hdr->total =
1619                 cpu_to_le32(new_root_size - offsetof(struct INDEX_ROOT, ihdr));
1620
1621         fnd->root_de = hdr_first_de(hdr);
1622         mi->dirty = true;
1623
1624         /* Create alloc and bitmap attributes (if not). */
1625         err = run_is_empty(&indx->alloc_run)
1626                       ? indx_create_allocate(indx, ni, &new_vbn)
1627                       : indx_add_allocate(indx, ni, &new_vbn);
1628
1629         /* Layout of record may be changed, so rescan root. */
1630         root = indx_get_root(indx, ni, &attr, &mi);
1631         if (!root) {
1632                 /* Bug? */
1633                 ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1634                 err = -EINVAL;
1635                 goto out_free_re;
1636         }
1637
1638         if (err) {
1639                 /* Restore root. */
1640                 if (mi_resize_attr(mi, attr, -ds_root))
1641                         memcpy(attr, a_root, asize);
1642                 else {
1643                         /* Bug? */
1644                         ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1645                 }
1646                 goto out_free_re;
1647         }
1648
1649         e = (struct NTFS_DE *)(root + 1);
1650         *(__le64 *)(e + 1) = cpu_to_le64(new_vbn);
1651         mi->dirty = true;
1652
1653         /* Now we can create/format the new buffer and copy the entries into. */
1654         n = indx_new(indx, ni, new_vbn, sub_vbn);
1655         if (IS_ERR(n)) {
1656                 err = PTR_ERR(n);
1657                 goto out_free_re;
1658         }
1659
1660         hdr = &n->index->ihdr;
1661         hdr_used = le32_to_cpu(hdr->used);
1662         hdr_total = le32_to_cpu(hdr->total);
1663
1664         /* Copy root entries into new buffer. */
1665         hdr_insert_head(hdr, re, to_move);
1666
1667         /* Update bitmap attribute. */
1668         indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
1669
1670         /* Check if we can insert new entry new index buffer. */
1671         if (hdr_used + new_de_size > hdr_total) {
1672                 /*
1673                  * This occurs if MFT record is the same or bigger than index
1674                  * buffer. Move all root new index and have no space to add
1675                  * new entry classic case when MFT record is 1K and index
1676                  * buffer 4K the problem should not occurs.
1677                  */
1678                 kfree(re);
1679                 indx_write(indx, ni, n, 0);
1680
1681                 put_indx_node(n);
1682                 fnd_clear(fnd);
1683                 err = indx_insert_entry(indx, ni, new_de, ctx, fnd, undo);
1684                 goto out_free_root;
1685         }
1686
1687         /*
1688          * Now root is a parent for new index buffer.
1689          * Insert NewEntry a new buffer.
1690          */
1691         e = hdr_insert_de(indx, hdr, new_de, NULL, ctx);
1692         if (!e) {
1693                 err = -EINVAL;
1694                 goto out_put_n;
1695         }
1696         fnd_push(fnd, n, e);
1697
1698         /* Just write updates index into disk. */
1699         indx_write(indx, ni, n, 0);
1700
1701         n = NULL;
1702
1703 out_put_n:
1704         put_indx_node(n);
1705 out_free_re:
1706         kfree(re);
1707 out_free_root:
1708         kfree(a_root);
1709         return err;
1710 }
1711
1712 /*
1713  * indx_insert_into_buffer
1714  *
1715  * Attempt to insert an entry into an Index Allocation Buffer.
1716  * If necessary, it will split the buffer.
1717  */
1718 static int
1719 indx_insert_into_buffer(struct ntfs_index *indx, struct ntfs_inode *ni,
1720                         struct INDEX_ROOT *root, const struct NTFS_DE *new_de,
1721                         const void *ctx, int level, struct ntfs_fnd *fnd)
1722 {
1723         int err;
1724         const struct NTFS_DE *sp;
1725         struct NTFS_DE *e, *de_t, *up_e = NULL;
1726         struct indx_node *n2 = NULL;
1727         struct indx_node *n1 = fnd->nodes[level];
1728         struct INDEX_HDR *hdr1 = &n1->index->ihdr;
1729         struct INDEX_HDR *hdr2;
1730         u32 to_copy, used;
1731         CLST new_vbn;
1732         __le64 t_vbn, *sub_vbn;
1733         u16 sp_size;
1734
1735         /* Try the most easy case. */
1736         e = fnd->level - 1 == level ? fnd->de[level] : NULL;
1737         e = hdr_insert_de(indx, hdr1, new_de, e, ctx);
1738         fnd->de[level] = e;
1739         if (e) {
1740                 /* Just write updated index into disk. */
1741                 indx_write(indx, ni, n1, 0);
1742                 return 0;
1743         }
1744
1745         /*
1746          * No space to insert into buffer. Split it.
1747          * To split we:
1748          *  - Save split point ('cause index buffers will be changed)
1749          * - Allocate NewBuffer and copy all entries <= sp into new buffer
1750          * - Remove all entries (sp including) from TargetBuffer
1751          * - Insert NewEntry into left or right buffer (depending on sp <=>
1752          *     NewEntry)
1753          * - Insert sp into parent buffer (or root)
1754          * - Make sp a parent for new buffer
1755          */
1756         sp = hdr_find_split(hdr1);
1757         if (!sp)
1758                 return -EINVAL;
1759
1760         sp_size = le16_to_cpu(sp->size);
1761         up_e = kmalloc(sp_size + sizeof(u64), GFP_NOFS);
1762         if (!up_e)
1763                 return -ENOMEM;
1764         memcpy(up_e, sp, sp_size);
1765
1766         if (!hdr1->flags) {
1767                 up_e->flags |= NTFS_IE_HAS_SUBNODES;
1768                 up_e->size = cpu_to_le16(sp_size + sizeof(u64));
1769                 sub_vbn = NULL;
1770         } else {
1771                 t_vbn = de_get_vbn_le(up_e);
1772                 sub_vbn = &t_vbn;
1773         }
1774
1775         /* Allocate on disk a new index allocation buffer. */
1776         err = indx_add_allocate(indx, ni, &new_vbn);
1777         if (err)
1778                 goto out;
1779
1780         /* Allocate and format memory a new index buffer. */
1781         n2 = indx_new(indx, ni, new_vbn, sub_vbn);
1782         if (IS_ERR(n2)) {
1783                 err = PTR_ERR(n2);
1784                 goto out;
1785         }
1786
1787         hdr2 = &n2->index->ihdr;
1788
1789         /* Make sp a parent for new buffer. */
1790         de_set_vbn(up_e, new_vbn);
1791
1792         /* Copy all the entries <= sp into the new buffer. */
1793         de_t = hdr_first_de(hdr1);
1794         to_copy = PtrOffset(de_t, sp);
1795         hdr_insert_head(hdr2, de_t, to_copy);
1796
1797         /* Remove all entries (sp including) from hdr1. */
1798         used = le32_to_cpu(hdr1->used) - to_copy - sp_size;
1799         memmove(de_t, Add2Ptr(sp, sp_size), used - le32_to_cpu(hdr1->de_off));
1800         hdr1->used = cpu_to_le32(used);
1801
1802         /*
1803          * Insert new entry into left or right buffer
1804          * (depending on sp <=> new_de).
1805          */
1806         hdr_insert_de(indx,
1807                       (*indx->cmp)(new_de + 1, le16_to_cpu(new_de->key_size),
1808                                    up_e + 1, le16_to_cpu(up_e->key_size),
1809                                    ctx) < 0
1810                               ? hdr2
1811                               : hdr1,
1812                       new_de, NULL, ctx);
1813
1814         indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
1815
1816         indx_write(indx, ni, n1, 0);
1817         indx_write(indx, ni, n2, 0);
1818
1819         put_indx_node(n2);
1820
1821         /*
1822          * We've finished splitting everybody, so we are ready to
1823          * insert the promoted entry into the parent.
1824          */
1825         if (!level) {
1826                 /* Insert in root. */
1827                 err = indx_insert_into_root(indx, ni, up_e, NULL, ctx, fnd, 0);
1828                 if (err)
1829                         goto out;
1830         } else {
1831                 /*
1832                  * The target buffer's parent is another index buffer.
1833                  * TODO: Remove recursion.
1834                  */
1835                 err = indx_insert_into_buffer(indx, ni, root, up_e, ctx,
1836                                               level - 1, fnd);
1837                 if (err)
1838                         goto out;
1839         }
1840
1841 out:
1842         kfree(up_e);
1843
1844         return err;
1845 }
1846
1847 /*
1848  * indx_insert_entry - Insert new entry into index.
1849  *
1850  * @undo - True if we undoing previous remove.
1851  */
1852 int indx_insert_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
1853                       const struct NTFS_DE *new_de, const void *ctx,
1854                       struct ntfs_fnd *fnd, bool undo)
1855 {
1856         int err;
1857         int diff;
1858         struct NTFS_DE *e;
1859         struct ntfs_fnd *fnd_a = NULL;
1860         struct INDEX_ROOT *root;
1861
1862         if (!fnd) {
1863                 fnd_a = fnd_get();
1864                 if (!fnd_a) {
1865                         err = -ENOMEM;
1866                         goto out1;
1867                 }
1868                 fnd = fnd_a;
1869         }
1870
1871         root = indx_get_root(indx, ni, NULL, NULL);
1872         if (!root) {
1873                 err = -EINVAL;
1874                 goto out;
1875         }
1876
1877         if (fnd_is_empty(fnd)) {
1878                 /*
1879                  * Find the spot the tree where we want to
1880                  * insert the new entry.
1881                  */
1882                 err = indx_find(indx, ni, root, new_de + 1,
1883                                 le16_to_cpu(new_de->key_size), ctx, &diff, &e,
1884                                 fnd);
1885                 if (err)
1886                         goto out;
1887
1888                 if (!diff) {
1889                         err = -EEXIST;
1890                         goto out;
1891                 }
1892         }
1893
1894         if (!fnd->level) {
1895                 /*
1896                  * The root is also a leaf, so we'll insert the
1897                  * new entry into it.
1898                  */
1899                 err = indx_insert_into_root(indx, ni, new_de, fnd->root_de, ctx,
1900                                             fnd, undo);
1901                 if (err)
1902                         goto out;
1903         } else {
1904                 /*
1905                  * Found a leaf buffer, so we'll insert the new entry into it.
1906                  */
1907                 err = indx_insert_into_buffer(indx, ni, root, new_de, ctx,
1908                                               fnd->level - 1, fnd);
1909                 if (err)
1910                         goto out;
1911         }
1912
1913 out:
1914         fnd_put(fnd_a);
1915 out1:
1916         return err;
1917 }
1918
1919 /*
1920  * indx_find_buffer - Locate a buffer from the tree.
1921  */
1922 static struct indx_node *indx_find_buffer(struct ntfs_index *indx,
1923                                           struct ntfs_inode *ni,
1924                                           const struct INDEX_ROOT *root,
1925                                           __le64 vbn, struct indx_node *n)
1926 {
1927         int err;
1928         const struct NTFS_DE *e;
1929         struct indx_node *r;
1930         const struct INDEX_HDR *hdr = n ? &n->index->ihdr : &root->ihdr;
1931
1932         /* Step 1: Scan one level. */
1933         for (e = hdr_first_de(hdr);; e = hdr_next_de(hdr, e)) {
1934                 if (!e)
1935                         return ERR_PTR(-EINVAL);
1936
1937                 if (de_has_vcn(e) && vbn == de_get_vbn_le(e))
1938                         return n;
1939
1940                 if (de_is_last(e))
1941                         break;
1942         }
1943
1944         /* Step2: Do recursion. */
1945         e = Add2Ptr(hdr, le32_to_cpu(hdr->de_off));
1946         for (;;) {
1947                 if (de_has_vcn_ex(e)) {
1948                         err = indx_read(indx, ni, de_get_vbn(e), &n);
1949                         if (err)
1950                                 return ERR_PTR(err);
1951
1952                         r = indx_find_buffer(indx, ni, root, vbn, n);
1953                         if (r)
1954                                 return r;
1955                 }
1956
1957                 if (de_is_last(e))
1958                         break;
1959
1960                 e = Add2Ptr(e, le16_to_cpu(e->size));
1961         }
1962
1963         return NULL;
1964 }
1965
1966 /*
1967  * indx_shrink - Deallocate unused tail indexes.
1968  */
1969 static int indx_shrink(struct ntfs_index *indx, struct ntfs_inode *ni,
1970                        size_t bit)
1971 {
1972         int err = 0;
1973         u64 bpb, new_data;
1974         size_t nbits;
1975         struct ATTRIB *b;
1976         struct ATTR_LIST_ENTRY *le = NULL;
1977         const struct INDEX_NAMES *in = &s_index_names[indx->type];
1978
1979         b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
1980                          NULL, NULL);
1981
1982         if (!b)
1983                 return -ENOENT;
1984
1985         if (!b->non_res) {
1986                 unsigned long pos;
1987                 const unsigned long *bm = resident_data(b);
1988
1989                 nbits = (size_t)le32_to_cpu(b->res.data_size) * 8;
1990
1991                 if (bit >= nbits)
1992                         return 0;
1993
1994                 pos = find_next_bit(bm, nbits, bit);
1995                 if (pos < nbits)
1996                         return 0;
1997         } else {
1998                 size_t used = MINUS_ONE_T;
1999
2000                 nbits = le64_to_cpu(b->nres.data_size) * 8;
2001
2002                 if (bit >= nbits)
2003                         return 0;
2004
2005                 err = scan_nres_bitmap(ni, b, indx, bit, &scan_for_used, &used);
2006                 if (err)
2007                         return err;
2008
2009                 if (used != MINUS_ONE_T)
2010                         return 0;
2011         }
2012
2013         new_data = (u64)bit << indx->index_bits;
2014
2015         err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
2016                             &indx->alloc_run, new_data, &new_data, false, NULL);
2017         if (err)
2018                 return err;
2019
2020         bpb = bitmap_size(bit);
2021         if (bpb * 8 == nbits)
2022                 return 0;
2023
2024         err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
2025                             &indx->bitmap_run, bpb, &bpb, false, NULL);
2026
2027         return err;
2028 }
2029
2030 static int indx_free_children(struct ntfs_index *indx, struct ntfs_inode *ni,
2031                               const struct NTFS_DE *e, bool trim)
2032 {
2033         int err;
2034         struct indx_node *n;
2035         struct INDEX_HDR *hdr;
2036         CLST vbn = de_get_vbn(e);
2037         size_t i;
2038
2039         err = indx_read(indx, ni, vbn, &n);
2040         if (err)
2041                 return err;
2042
2043         hdr = &n->index->ihdr;
2044         /* First, recurse into the children, if any. */
2045         if (hdr_has_subnode(hdr)) {
2046                 for (e = hdr_first_de(hdr); e; e = hdr_next_de(hdr, e)) {
2047                         indx_free_children(indx, ni, e, false);
2048                         if (de_is_last(e))
2049                                 break;
2050                 }
2051         }
2052
2053         put_indx_node(n);
2054
2055         i = vbn >> indx->idx2vbn_bits;
2056         /*
2057          * We've gotten rid of the children; add this buffer to the free list.
2058          */
2059         indx_mark_free(indx, ni, i);
2060
2061         if (!trim)
2062                 return 0;
2063
2064         /*
2065          * If there are no used indexes after current free index
2066          * then we can truncate allocation and bitmap.
2067          * Use bitmap to estimate the case.
2068          */
2069         indx_shrink(indx, ni, i + 1);
2070         return 0;
2071 }
2072
2073 /*
2074  * indx_get_entry_to_replace
2075  *
2076  * Find a replacement entry for a deleted entry.
2077  * Always returns a node entry:
2078  * NTFS_IE_HAS_SUBNODES is set the flags and the size includes the sub_vcn.
2079  */
2080 static int indx_get_entry_to_replace(struct ntfs_index *indx,
2081                                      struct ntfs_inode *ni,
2082                                      const struct NTFS_DE *de_next,
2083                                      struct NTFS_DE **de_to_replace,
2084                                      struct ntfs_fnd *fnd)
2085 {
2086         int err;
2087         int level = -1;
2088         CLST vbn;
2089         struct NTFS_DE *e, *te, *re;
2090         struct indx_node *n;
2091         struct INDEX_BUFFER *ib;
2092
2093         *de_to_replace = NULL;
2094
2095         /* Find first leaf entry down from de_next. */
2096         vbn = de_get_vbn(de_next);
2097         for (;;) {
2098                 n = NULL;
2099                 err = indx_read(indx, ni, vbn, &n);
2100                 if (err)
2101                         goto out;
2102
2103                 e = hdr_first_de(&n->index->ihdr);
2104                 fnd_push(fnd, n, e);
2105
2106                 if (!de_is_last(e)) {
2107                         /*
2108                          * This buffer is non-empty, so its first entry
2109                          * could be used as the replacement entry.
2110                          */
2111                         level = fnd->level - 1;
2112                 }
2113
2114                 if (!de_has_vcn(e))
2115                         break;
2116
2117                 /* This buffer is a node. Continue to go down. */
2118                 vbn = de_get_vbn(e);
2119         }
2120
2121         if (level == -1)
2122                 goto out;
2123
2124         n = fnd->nodes[level];
2125         te = hdr_first_de(&n->index->ihdr);
2126         /* Copy the candidate entry into the replacement entry buffer. */
2127         re = kmalloc(le16_to_cpu(te->size) + sizeof(u64), GFP_NOFS);
2128         if (!re) {
2129                 err = -ENOMEM;
2130                 goto out;
2131         }
2132
2133         *de_to_replace = re;
2134         memcpy(re, te, le16_to_cpu(te->size));
2135
2136         if (!de_has_vcn(re)) {
2137                 /*
2138                  * The replacement entry we found doesn't have a sub_vcn.
2139                  * increase its size to hold one.
2140                  */
2141                 le16_add_cpu(&re->size, sizeof(u64));
2142                 re->flags |= NTFS_IE_HAS_SUBNODES;
2143         } else {
2144                 /*
2145                  * The replacement entry we found was a node entry, which
2146                  * means that all its child buffers are empty. Return them
2147                  * to the free pool.
2148                  */
2149                 indx_free_children(indx, ni, te, true);
2150         }
2151
2152         /*
2153          * Expunge the replacement entry from its former location,
2154          * and then write that buffer.
2155          */
2156         ib = n->index;
2157         e = hdr_delete_de(&ib->ihdr, te);
2158
2159         fnd->de[level] = e;
2160         indx_write(indx, ni, n, 0);
2161
2162         /* Check to see if this action created an empty leaf. */
2163         if (ib_is_leaf(ib) && ib_is_empty(ib))
2164                 return 0;
2165
2166 out:
2167         fnd_clear(fnd);
2168         return err;
2169 }
2170
2171 /*
2172  * indx_delete_entry - Delete an entry from the index.
2173  */
2174 int indx_delete_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
2175                       const void *key, u32 key_len, const void *ctx)
2176 {
2177         int err, diff;
2178         struct INDEX_ROOT *root;
2179         struct INDEX_HDR *hdr;
2180         struct ntfs_fnd *fnd, *fnd2;
2181         struct INDEX_BUFFER *ib;
2182         struct NTFS_DE *e, *re, *next, *prev, *me;
2183         struct indx_node *n, *n2d = NULL;
2184         __le64 sub_vbn;
2185         int level, level2;
2186         struct ATTRIB *attr;
2187         struct mft_inode *mi;
2188         u32 e_size, root_size, new_root_size;
2189         size_t trim_bit;
2190         const struct INDEX_NAMES *in;
2191
2192         fnd = fnd_get();
2193         if (!fnd) {
2194                 err = -ENOMEM;
2195                 goto out2;
2196         }
2197
2198         fnd2 = fnd_get();
2199         if (!fnd2) {
2200                 err = -ENOMEM;
2201                 goto out1;
2202         }
2203
2204         root = indx_get_root(indx, ni, &attr, &mi);
2205         if (!root) {
2206                 err = -EINVAL;
2207                 goto out;
2208         }
2209
2210         /* Locate the entry to remove. */
2211         err = indx_find(indx, ni, root, key, key_len, ctx, &diff, &e, fnd);
2212         if (err)
2213                 goto out;
2214
2215         if (!e || diff) {
2216                 err = -ENOENT;
2217                 goto out;
2218         }
2219
2220         level = fnd->level;
2221
2222         if (level) {
2223                 n = fnd->nodes[level - 1];
2224                 e = fnd->de[level - 1];
2225                 ib = n->index;
2226                 hdr = &ib->ihdr;
2227         } else {
2228                 hdr = &root->ihdr;
2229                 e = fnd->root_de;
2230                 n = NULL;
2231         }
2232
2233         e_size = le16_to_cpu(e->size);
2234
2235         if (!de_has_vcn_ex(e)) {
2236                 /* The entry to delete is a leaf, so we can just rip it out. */
2237                 hdr_delete_de(hdr, e);
2238
2239                 if (!level) {
2240                         hdr->total = hdr->used;
2241
2242                         /* Shrink resident root attribute. */
2243                         mi_resize_attr(mi, attr, 0 - e_size);
2244                         goto out;
2245                 }
2246
2247                 indx_write(indx, ni, n, 0);
2248
2249                 /*
2250                  * Check to see if removing that entry made
2251                  * the leaf empty.
2252                  */
2253                 if (ib_is_leaf(ib) && ib_is_empty(ib)) {
2254                         fnd_pop(fnd);
2255                         fnd_push(fnd2, n, e);
2256                 }
2257         } else {
2258                 /*
2259                  * The entry we wish to delete is a node buffer, so we
2260                  * have to find a replacement for it.
2261                  */
2262                 next = de_get_next(e);
2263
2264                 err = indx_get_entry_to_replace(indx, ni, next, &re, fnd2);
2265                 if (err)
2266                         goto out;
2267
2268                 if (re) {
2269                         de_set_vbn_le(re, de_get_vbn_le(e));
2270                         hdr_delete_de(hdr, e);
2271
2272                         err = level ? indx_insert_into_buffer(indx, ni, root,
2273                                                               re, ctx,
2274                                                               fnd->level - 1,
2275                                                               fnd)
2276                                     : indx_insert_into_root(indx, ni, re, e,
2277                                                             ctx, fnd, 0);
2278                         kfree(re);
2279
2280                         if (err)
2281                                 goto out;
2282                 } else {
2283                         /*
2284                          * There is no replacement for the current entry.
2285                          * This means that the subtree rooted at its node
2286                          * is empty, and can be deleted, which turn means
2287                          * that the node can just inherit the deleted
2288                          * entry sub_vcn.
2289                          */
2290                         indx_free_children(indx, ni, next, true);
2291
2292                         de_set_vbn_le(next, de_get_vbn_le(e));
2293                         hdr_delete_de(hdr, e);
2294                         if (level) {
2295                                 indx_write(indx, ni, n, 0);
2296                         } else {
2297                                 hdr->total = hdr->used;
2298
2299                                 /* Shrink resident root attribute. */
2300                                 mi_resize_attr(mi, attr, 0 - e_size);
2301                         }
2302                 }
2303         }
2304
2305         /* Delete a branch of tree. */
2306         if (!fnd2 || !fnd2->level)
2307                 goto out;
2308
2309         /* Reinit root 'cause it can be changed. */
2310         root = indx_get_root(indx, ni, &attr, &mi);
2311         if (!root) {
2312                 err = -EINVAL;
2313                 goto out;
2314         }
2315
2316         n2d = NULL;
2317         sub_vbn = fnd2->nodes[0]->index->vbn;
2318         level2 = 0;
2319         level = fnd->level;
2320
2321         hdr = level ? &fnd->nodes[level - 1]->index->ihdr : &root->ihdr;
2322
2323         /* Scan current level. */
2324         for (e = hdr_first_de(hdr);; e = hdr_next_de(hdr, e)) {
2325                 if (!e) {
2326                         err = -EINVAL;
2327                         goto out;
2328                 }
2329
2330                 if (de_has_vcn(e) && sub_vbn == de_get_vbn_le(e))
2331                         break;
2332
2333                 if (de_is_last(e)) {
2334                         e = NULL;
2335                         break;
2336                 }
2337         }
2338
2339         if (!e) {
2340                 /* Do slow search from root. */
2341                 struct indx_node *in;
2342
2343                 fnd_clear(fnd);
2344
2345                 in = indx_find_buffer(indx, ni, root, sub_vbn, NULL);
2346                 if (IS_ERR(in)) {
2347                         err = PTR_ERR(in);
2348                         goto out;
2349                 }
2350
2351                 if (in)
2352                         fnd_push(fnd, in, NULL);
2353         }
2354
2355         /* Merge fnd2 -> fnd. */
2356         for (level = 0; level < fnd2->level; level++) {
2357                 fnd_push(fnd, fnd2->nodes[level], fnd2->de[level]);
2358                 fnd2->nodes[level] = NULL;
2359         }
2360         fnd2->level = 0;
2361
2362         hdr = NULL;
2363         for (level = fnd->level; level; level--) {
2364                 struct indx_node *in = fnd->nodes[level - 1];
2365
2366                 ib = in->index;
2367                 if (ib_is_empty(ib)) {
2368                         sub_vbn = ib->vbn;
2369                 } else {
2370                         hdr = &ib->ihdr;
2371                         n2d = in;
2372                         level2 = level;
2373                         break;
2374                 }
2375         }
2376
2377         if (!hdr)
2378                 hdr = &root->ihdr;
2379
2380         e = hdr_first_de(hdr);
2381         if (!e) {
2382                 err = -EINVAL;
2383                 goto out;
2384         }
2385
2386         if (hdr != &root->ihdr || !de_is_last(e)) {
2387                 prev = NULL;
2388                 while (!de_is_last(e)) {
2389                         if (de_has_vcn(e) && sub_vbn == de_get_vbn_le(e))
2390                                 break;
2391                         prev = e;
2392                         e = hdr_next_de(hdr, e);
2393                         if (!e) {
2394                                 err = -EINVAL;
2395                                 goto out;
2396                         }
2397                 }
2398
2399                 if (sub_vbn != de_get_vbn_le(e)) {
2400                         /*
2401                          * Didn't find the parent entry, although this buffer
2402                          * is the parent trail. Something is corrupt.
2403                          */
2404                         err = -EINVAL;
2405                         goto out;
2406                 }
2407
2408                 if (de_is_last(e)) {
2409                         /*
2410                          * Since we can't remove the end entry, we'll remove
2411                          * its predecessor instead. This means we have to
2412                          * transfer the predecessor's sub_vcn to the end entry.
2413                          * Note: This index block is not empty, so the
2414                          * predecessor must exist.
2415                          */
2416                         if (!prev) {
2417                                 err = -EINVAL;
2418                                 goto out;
2419                         }
2420
2421                         if (de_has_vcn(prev)) {
2422                                 de_set_vbn_le(e, de_get_vbn_le(prev));
2423                         } else if (de_has_vcn(e)) {
2424                                 le16_sub_cpu(&e->size, sizeof(u64));
2425                                 e->flags &= ~NTFS_IE_HAS_SUBNODES;
2426                                 le32_sub_cpu(&hdr->used, sizeof(u64));
2427                         }
2428                         e = prev;
2429                 }
2430
2431                 /*
2432                  * Copy the current entry into a temporary buffer (stripping
2433                  * off its down-pointer, if any) and delete it from the current
2434                  * buffer or root, as appropriate.
2435                  */
2436                 e_size = le16_to_cpu(e->size);
2437                 me = kmemdup(e, e_size, GFP_NOFS);
2438                 if (!me) {
2439                         err = -ENOMEM;
2440                         goto out;
2441                 }
2442
2443                 if (de_has_vcn(me)) {
2444                         me->flags &= ~NTFS_IE_HAS_SUBNODES;
2445                         le16_sub_cpu(&me->size, sizeof(u64));
2446                 }
2447
2448                 hdr_delete_de(hdr, e);
2449
2450                 if (hdr == &root->ihdr) {
2451                         level = 0;
2452                         hdr->total = hdr->used;
2453
2454                         /* Shrink resident root attribute. */
2455                         mi_resize_attr(mi, attr, 0 - e_size);
2456                 } else {
2457                         indx_write(indx, ni, n2d, 0);
2458                         level = level2;
2459                 }
2460
2461                 /* Mark unused buffers as free. */
2462                 trim_bit = -1;
2463                 for (; level < fnd->level; level++) {
2464                         ib = fnd->nodes[level]->index;
2465                         if (ib_is_empty(ib)) {
2466                                 size_t k = le64_to_cpu(ib->vbn) >>
2467                                            indx->idx2vbn_bits;
2468
2469                                 indx_mark_free(indx, ni, k);
2470                                 if (k < trim_bit)
2471                                         trim_bit = k;
2472                         }
2473                 }
2474
2475                 fnd_clear(fnd);
2476                 /*fnd->root_de = NULL;*/
2477
2478                 /*
2479                  * Re-insert the entry into the tree.
2480                  * Find the spot the tree where we want to insert the new entry.
2481                  */
2482                 err = indx_insert_entry(indx, ni, me, ctx, fnd, 0);
2483                 kfree(me);
2484                 if (err)
2485                         goto out;
2486
2487                 if (trim_bit != -1)
2488                         indx_shrink(indx, ni, trim_bit);
2489         } else {
2490                 /*
2491                  * This tree needs to be collapsed down to an empty root.
2492                  * Recreate the index root as an empty leaf and free all
2493                  * the bits the index allocation bitmap.
2494                  */
2495                 fnd_clear(fnd);
2496                 fnd_clear(fnd2);
2497
2498                 in = &s_index_names[indx->type];
2499
2500                 err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
2501                                     &indx->alloc_run, 0, NULL, false, NULL);
2502                 err = ni_remove_attr(ni, ATTR_ALLOC, in->name, in->name_len,
2503                                      false, NULL);
2504                 run_close(&indx->alloc_run);
2505
2506                 err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
2507                                     &indx->bitmap_run, 0, NULL, false, NULL);
2508                 err = ni_remove_attr(ni, ATTR_BITMAP, in->name, in->name_len,
2509                                      false, NULL);
2510                 run_close(&indx->bitmap_run);
2511
2512                 root = indx_get_root(indx, ni, &attr, &mi);
2513                 if (!root) {
2514                         err = -EINVAL;
2515                         goto out;
2516                 }
2517
2518                 root_size = le32_to_cpu(attr->res.data_size);
2519                 new_root_size =
2520                         sizeof(struct INDEX_ROOT) + sizeof(struct NTFS_DE);
2521
2522                 if (new_root_size != root_size &&
2523                     !mi_resize_attr(mi, attr, new_root_size - root_size)) {
2524                         err = -EINVAL;
2525                         goto out;
2526                 }
2527
2528                 /* Fill first entry. */
2529                 e = (struct NTFS_DE *)(root + 1);
2530                 e->ref.low = 0;
2531                 e->ref.high = 0;
2532                 e->ref.seq = 0;
2533                 e->size = cpu_to_le16(sizeof(struct NTFS_DE));
2534                 e->flags = NTFS_IE_LAST; // 0x02
2535                 e->key_size = 0;
2536                 e->res = 0;
2537
2538                 hdr = &root->ihdr;
2539                 hdr->flags = 0;
2540                 hdr->used = hdr->total = cpu_to_le32(
2541                         new_root_size - offsetof(struct INDEX_ROOT, ihdr));
2542                 mi->dirty = true;
2543         }
2544
2545 out:
2546         fnd_put(fnd2);
2547 out1:
2548         fnd_put(fnd);
2549 out2:
2550         return err;
2551 }
2552
2553 /*
2554  * Update duplicated information in directory entry
2555  * 'dup' - info from MFT record
2556  */
2557 int indx_update_dup(struct ntfs_inode *ni, struct ntfs_sb_info *sbi,
2558                     const struct ATTR_FILE_NAME *fname,
2559                     const struct NTFS_DUP_INFO *dup, int sync)
2560 {
2561         int err, diff;
2562         struct NTFS_DE *e = NULL;
2563         struct ATTR_FILE_NAME *e_fname;
2564         struct ntfs_fnd *fnd;
2565         struct INDEX_ROOT *root;
2566         struct mft_inode *mi;
2567         struct ntfs_index *indx = &ni->dir;
2568
2569         fnd = fnd_get();
2570         if (!fnd)
2571                 return -ENOMEM;
2572
2573         root = indx_get_root(indx, ni, NULL, &mi);
2574         if (!root) {
2575                 err = -EINVAL;
2576                 goto out;
2577         }
2578
2579         /* Find entry in directory. */
2580         err = indx_find(indx, ni, root, fname, fname_full_size(fname), sbi,
2581                         &diff, &e, fnd);
2582         if (err)
2583                 goto out;
2584
2585         if (!e) {
2586                 err = -EINVAL;
2587                 goto out;
2588         }
2589
2590         if (diff) {
2591                 err = -EINVAL;
2592                 goto out;
2593         }
2594
2595         e_fname = (struct ATTR_FILE_NAME *)(e + 1);
2596
2597         if (!memcmp(&e_fname->dup, dup, sizeof(*dup))) {
2598                 /*
2599                  * Nothing to update in index! Try to avoid this call.
2600                  */
2601                 goto out;
2602         }
2603
2604         memcpy(&e_fname->dup, dup, sizeof(*dup));
2605
2606         if (fnd->level) {
2607                 /* Directory entry in index. */
2608                 err = indx_write(indx, ni, fnd->nodes[fnd->level - 1], sync);
2609         } else {
2610                 /* Directory entry in directory MFT record. */
2611                 mi->dirty = true;
2612                 if (sync)
2613                         err = mi_write(mi, 1);
2614                 else
2615                         mark_inode_dirty(&ni->vfs_inode);
2616         }
2617
2618 out:
2619         fnd_put(fnd);
2620         return err;
2621 }