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