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