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/kernel.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 /*
 609  * index_hdr_check
 610  *
 611  * return true if INDEX_HDR is valid
 612  */
 613 static bool index_hdr_check(const struct INDEX_HDR *hdr, u32 bytes)
 614 {
 615         u32 end = le32_to_cpu(hdr->used);
 616         u32 tot = le32_to_cpu(hdr->total);
 617         u32 off = le32_to_cpu(hdr->de_off);
 618
 619         if (!IS_ALIGNED(off, 8) || tot > bytes || end > tot ||
 620             off + sizeof(struct NTFS_DE) > end) {
 621                 /* incorrect index buffer. */
 622                 return false;
 623         }
 624
 625         return true;
 626 }
 627
 628 /*
 629  * index_buf_check
 630  *
 631  * return true if INDEX_BUFFER seems is valid
 632  */
 633 static bool index_buf_check(const struct INDEX_BUFFER *ib, u32 bytes,
 634                             const CLST *vbn)
 635 {
 636         const struct NTFS_RECORD_HEADER *rhdr = &ib->rhdr;
 637         u16 fo = le16_to_cpu(rhdr->fix_off);
 638         u16 fn = le16_to_cpu(rhdr->fix_num);
 639
 640         if (bytes <= offsetof(struct INDEX_BUFFER, ihdr) ||
 641             rhdr->sign != NTFS_INDX_SIGNATURE ||
 642             fo < sizeof(struct INDEX_BUFFER)
 643             /* Check index buffer vbn. */
 644             || (vbn && *vbn != le64_to_cpu(ib->vbn)) || (fo % sizeof(short)) ||
 645             fo + fn * sizeof(short) >= bytes ||
 646             fn != ((bytes >> SECTOR_SHIFT) + 1)) {
 647                 /* incorrect index buffer. */
 648                 return false;
 649         }
 650
 651         return index_hdr_check(&ib->ihdr,
 652                                bytes - offsetof(struct INDEX_BUFFER, ihdr));
 653 }
 654
 655 void fnd_clear(struct ntfs_fnd *fnd)
 656 {
 657         int i;
 658
 659         for (i = fnd->level - 1; i >= 0; i--) {
 660                 struct indx_node *n = fnd->nodes[i];
 661
 662                 if (!n)
 663                         continue;
 664
 665                 put_indx_node(n);
 666                 fnd->nodes[i] = NULL;
 667         }
 668         fnd->level = 0;
 669         fnd->root_de = NULL;
 670 }
 671
 672 static int fnd_push(struct ntfs_fnd *fnd, struct indx_node *n,
 673                     struct NTFS_DE *e)
 674 {
 675         int i;
 676
 677         i = fnd->level;
 678         if (i < 0 || i >= ARRAY_SIZE(fnd->nodes))
 679                 return -EINVAL;
 680         fnd->nodes[i] = n;
 681         fnd->de[i] = e;
 682         fnd->level += 1;
 683         return 0;
 684 }
 685
 686 static struct indx_node *fnd_pop(struct ntfs_fnd *fnd)
 687 {
 688         struct indx_node *n;
 689         int i = fnd->level;
 690
 691         i -= 1;
 692         n = fnd->nodes[i];
 693         fnd->nodes[i] = NULL;
 694         fnd->level = i;
 695
 696         return n;
 697 }
 698
 699 static bool fnd_is_empty(struct ntfs_fnd *fnd)
 700 {
 701         if (!fnd->level)
 702                 return !fnd->root_de;
 703
 704         return !fnd->de[fnd->level - 1];
 705 }
 706
 707 /*
 708  * hdr_find_e - Locate an entry the index buffer.
 709  *
 710  * If no matching entry is found, it returns the first entry which is greater
 711  * than the desired entry If the search key is greater than all the entries the
 712  * buffer, it returns the 'end' entry. This function does a binary search of the
 713  * current index buffer, for the first entry that is <= to the search value.
 714  *
 715  * Return: NULL if error.
 716  */
 717 static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 718                                   const struct INDEX_HDR *hdr, const void *key,
 719                                   size_t key_len, const void *ctx, int *diff)
 720 {
 721         struct NTFS_DE *e, *found = NULL;
 722         NTFS_CMP_FUNC cmp = indx->cmp;
 723         int min_idx = 0, mid_idx, max_idx = 0;
 724         int diff2;
 725         int table_size = 8;
 726         u32 e_size, e_key_len;
 727         u32 end = le32_to_cpu(hdr->used);
 728         u32 off = le32_to_cpu(hdr->de_off);
 729         u32 total = le32_to_cpu(hdr->total);
 730         u16 offs[128];
 731
 732 fill_table:
 733         if (end > total)
 734                 return NULL;
 735
 736         if (off + sizeof(struct NTFS_DE) > end)
 737                 return NULL;
 738
 739         e = Add2Ptr(hdr, off);
 740         e_size = le16_to_cpu(e->size);
 741
 742         if (e_size < sizeof(struct NTFS_DE) || off + e_size > end)
 743                 return NULL;
 744
 745         if (!de_is_last(e)) {
 746                 offs[max_idx] = off;
 747                 off += e_size;
 748
 749                 max_idx++;
 750                 if (max_idx < table_size)
 751                         goto fill_table;
 752
 753                 max_idx--;
 754         }
 755
 756 binary_search:
 757         e_key_len = le16_to_cpu(e->key_size);
 758
 759         diff2 = (*cmp)(key, key_len, e + 1, e_key_len, ctx);
 760         if (diff2 > 0) {
 761                 if (found) {
 762                         min_idx = mid_idx + 1;
 763                 } else {
 764                         if (de_is_last(e))
 765                                 return NULL;
 766
 767                         max_idx = 0;
 768                         table_size = min(table_size * 2,
 769                                          (int)ARRAY_SIZE(offs));
 770                         goto fill_table;
 771                 }
 772         } else if (diff2 < 0) {
 773                 if (found)
 774                         max_idx = mid_idx - 1;
 775                 else
 776                         max_idx--;
 777
 778                 found = e;
 779         } else {
 780                 *diff = 0;
 781                 return e;
 782         }
 783
 784         if (min_idx > max_idx) {
 785                 *diff = -1;
 786                 return found;
 787         }
 788
 789         mid_idx = (min_idx + max_idx) >> 1;
 790         e = Add2Ptr(hdr, offs[mid_idx]);
 791
 792         goto binary_search;
 793 }
 794
 795 /*
 796  * hdr_insert_de - Insert an index entry into the buffer.
 797  *
 798  * 'before' should be a pointer previously returned from hdr_find_e.
 799  */
 800 static struct NTFS_DE *hdr_insert_de(const struct ntfs_index *indx,
 801                                      struct INDEX_HDR *hdr,
 802                                      const struct NTFS_DE *de,
 803                                      struct NTFS_DE *before, const void *ctx)
 804 {
 805         int diff;
 806         size_t off = PtrOffset(hdr, before);
 807         u32 used = le32_to_cpu(hdr->used);
 808         u32 total = le32_to_cpu(hdr->total);
 809         u16 de_size = le16_to_cpu(de->size);
 810
 811         /* First, check to see if there's enough room. */
 812         if (used + de_size > total)
 813                 return NULL;
 814
 815         /* We know there's enough space, so we know we'll succeed. */
 816         if (before) {
 817                 /* Check that before is inside Index. */
 818                 if (off >= used || off < le32_to_cpu(hdr->de_off) ||
 819                     off + le16_to_cpu(before->size) > total) {
 820                         return NULL;
 821                 }
 822                 goto ok;
 823         }
 824         /* No insert point is applied. Get it manually. */
 825         before = hdr_find_e(indx, hdr, de + 1, le16_to_cpu(de->key_size), ctx,
 826                             &diff);
 827         if (!before)
 828                 return NULL;
 829         off = PtrOffset(hdr, before);
 830
 831 ok:
 832         /* Now we just make room for the entry and jam it in. */
 833         memmove(Add2Ptr(before, de_size), before, used - off);
 834
 835         hdr->used = cpu_to_le32(used + de_size);
 836         memcpy(before, de, de_size);
 837
 838         return before;
 839 }
 840
 841 /*
 842  * hdr_delete_de - Remove an entry from the index buffer.
 843  */
 844 static inline struct NTFS_DE *hdr_delete_de(struct INDEX_HDR *hdr,
 845                                             struct NTFS_DE *re)
 846 {
 847         u32 used = le32_to_cpu(hdr->used);
 848         u16 esize = le16_to_cpu(re->size);
 849         u32 off = PtrOffset(hdr, re);
 850         int bytes = used - (off + esize);
 851
 852         /* check INDEX_HDR valid before using INDEX_HDR */
 853         if (!check_index_header(hdr, le32_to_cpu(hdr->total)))
 854                 return NULL;
 855
 856         if (off >= used || esize < sizeof(struct NTFS_DE) ||
 857             bytes < sizeof(struct NTFS_DE))
 858                 return NULL;
 859
 860         hdr->used = cpu_to_le32(used - esize);
 861         memmove(re, Add2Ptr(re, esize), bytes);
 862
 863         return re;
 864 }
 865
 866 void indx_clear(struct ntfs_index *indx)
 867 {
 868         run_close(&indx->alloc_run);
 869         run_close(&indx->bitmap_run);
 870 }
 871
 872 int indx_init(struct ntfs_index *indx, struct ntfs_sb_info *sbi,
 873               const struct ATTRIB *attr, enum index_mutex_classed type)
 874 {
 875         u32 t32;
 876         const struct INDEX_ROOT *root = resident_data(attr);
 877
 878         t32 = le32_to_cpu(attr->res.data_size);
 879         if (t32 <= offsetof(struct INDEX_ROOT, ihdr) ||
 880             !index_hdr_check(&root->ihdr,
 881                              t32 - offsetof(struct INDEX_ROOT, ihdr))) {
 882                 goto out;
 883         }
 884
 885         /* Check root fields. */
 886         if (!root->index_block_clst)
 887                 goto out;
 888
 889         indx->type = type;
 890         indx->idx2vbn_bits = __ffs(root->index_block_clst);
 891
 892         t32 = le32_to_cpu(root->index_block_size);
 893         indx->index_bits = blksize_bits(t32);
 894
 895         /* Check index record size. */
 896         if (t32 < sbi->cluster_size) {
 897                 /* Index record is smaller than a cluster, use 512 blocks. */
 898                 if (t32 != root->index_block_clst * SECTOR_SIZE)
 899                         goto out;
 900
 901                 /* Check alignment to a cluster. */
 902                 if ((sbi->cluster_size >> SECTOR_SHIFT) &
 903                     (root->index_block_clst - 1)) {
 904                         goto out;
 905                 }
 906
 907                 indx->vbn2vbo_bits = SECTOR_SHIFT;
 908         } else {
 909                 /* Index record must be a multiple of cluster size. */
 910                 if (t32 != root->index_block_clst << sbi->cluster_bits)
 911                         goto out;
 912
 913                 indx->vbn2vbo_bits = sbi->cluster_bits;
 914         }
 915
 916         init_rwsem(&indx->run_lock);
 917
 918         indx->cmp = get_cmp_func(root);
 919         if (!indx->cmp)
 920                 goto out;
 921
 922         return 0;
 923
 924 out:
 925         ntfs_set_state(sbi, NTFS_DIRTY_DIRTY);
 926         return -EINVAL;
 927 }
 928
 929 static struct indx_node *indx_new(struct ntfs_index *indx,
 930                                   struct ntfs_inode *ni, CLST vbn,
 931                                   const __le64 *sub_vbn)
 932 {
 933         int err;
 934         struct NTFS_DE *e;
 935         struct indx_node *r;
 936         struct INDEX_HDR *hdr;
 937         struct INDEX_BUFFER *index;
 938         u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
 939         u32 bytes = 1u << indx->index_bits;
 940         u16 fn;
 941         u32 eo;
 942
 943         r = kzalloc(sizeof(struct indx_node), GFP_NOFS);
 944         if (!r)
 945                 return ERR_PTR(-ENOMEM);
 946
 947         index = kzalloc(bytes, GFP_NOFS);
 948         if (!index) {
 949                 kfree(r);
 950                 return ERR_PTR(-ENOMEM);
 951         }
 952
 953         err = ntfs_get_bh(ni->mi.sbi, &indx->alloc_run, vbo, bytes, &r->nb);
 954
 955         if (err) {
 956                 kfree(index);
 957                 kfree(r);
 958                 return ERR_PTR(err);
 959         }
 960
 961         /* Create header. */
 962         index->rhdr.sign = NTFS_INDX_SIGNATURE;
 963         index->rhdr.fix_off = cpu_to_le16(sizeof(struct INDEX_BUFFER)); // 0x28
 964         fn = (bytes >> SECTOR_SHIFT) + 1; // 9
 965         index->rhdr.fix_num = cpu_to_le16(fn);
 966         index->vbn = cpu_to_le64(vbn);
 967         hdr = &index->ihdr;
 968         eo = ALIGN(sizeof(struct INDEX_BUFFER) + fn * sizeof(short), 8);
 969         hdr->de_off = cpu_to_le32(eo);
 970
 971         e = Add2Ptr(hdr, eo);
 972
 973         if (sub_vbn) {
 974                 e->flags = NTFS_IE_LAST | NTFS_IE_HAS_SUBNODES;
 975                 e->size = cpu_to_le16(sizeof(struct NTFS_DE) + sizeof(u64));
 976                 hdr->used =
 977                         cpu_to_le32(eo + sizeof(struct NTFS_DE) + sizeof(u64));
 978                 de_set_vbn_le(e, *sub_vbn);
 979                 hdr->flags = 1;
 980         } else {
 981                 e->size = cpu_to_le16(sizeof(struct NTFS_DE));
 982                 hdr->used = cpu_to_le32(eo + sizeof(struct NTFS_DE));
 983                 e->flags = NTFS_IE_LAST;
 984         }
 985
 986         hdr->total = cpu_to_le32(bytes - offsetof(struct INDEX_BUFFER, ihdr));
 987
 988         r->index = index;
 989         return r;
 990 }
 991
 992 struct INDEX_ROOT *indx_get_root(struct ntfs_index *indx, struct ntfs_inode *ni,
 993                                  struct ATTRIB **attr, struct mft_inode **mi)
 994 {
 995         struct ATTR_LIST_ENTRY *le = NULL;
 996         struct ATTRIB *a;
 997         const struct INDEX_NAMES *in = &s_index_names[indx->type];
 998
 999         a = ni_find_attr(ni, NULL, &le, ATTR_ROOT, in->name, in->name_len, NULL,
1000                          mi);
1001         if (!a)
1002                 return NULL;
1003
1004         if (attr)
1005                 *attr = a;
1006
1007         return resident_data_ex(a, sizeof(struct INDEX_ROOT));
1008 }
1009
1010 static int indx_write(struct ntfs_index *indx, struct ntfs_inode *ni,
1011                       struct indx_node *node, int sync)
1012 {
1013         struct INDEX_BUFFER *ib = node->index;
1014
1015         return ntfs_write_bh(ni->mi.sbi, &ib->rhdr, &node->nb, sync);
1016 }
1017
1018 /*
1019  * indx_read
1020  *
1021  * If ntfs_readdir calls this function
1022  * inode is shared locked and no ni_lock.
1023  * Use rw_semaphore for read/write access to alloc_run.
1024  */
1025 int indx_read(struct ntfs_index *indx, struct ntfs_inode *ni, CLST vbn,
1026               struct indx_node **node)
1027 {
1028         int err;
1029         struct INDEX_BUFFER *ib;
1030         struct runs_tree *run = &indx->alloc_run;
1031         struct rw_semaphore *lock = &indx->run_lock;
1032         u64 vbo = (u64)vbn << indx->vbn2vbo_bits;
1033         u32 bytes = 1u << indx->index_bits;
1034         struct indx_node *in = *node;
1035         const struct INDEX_NAMES *name;
1036
1037         if (!in) {
1038                 in = kzalloc(sizeof(struct indx_node), GFP_NOFS);
1039                 if (!in)
1040                         return -ENOMEM;
1041         } else {
1042                 nb_put(&in->nb);
1043         }
1044
1045         ib = in->index;
1046         if (!ib) {
1047                 ib = kmalloc(bytes, GFP_NOFS);
1048                 if (!ib) {
1049                         err = -ENOMEM;
1050                         goto out;
1051                 }
1052         }
1053
1054         down_read(lock);
1055         err = ntfs_read_bh(ni->mi.sbi, run, vbo, &ib->rhdr, bytes, &in->nb);
1056         up_read(lock);
1057         if (!err)
1058                 goto ok;
1059
1060         if (err == -E_NTFS_FIXUP)
1061                 goto ok;
1062
1063         if (err != -ENOENT)
1064                 goto out;
1065
1066         name = &s_index_names[indx->type];
1067         down_write(lock);
1068         err = attr_load_runs_range(ni, ATTR_ALLOC, name->name, name->name_len,
1069                                    run, vbo, vbo + bytes);
1070         up_write(lock);
1071         if (err)
1072                 goto out;
1073
1074         down_read(lock);
1075         err = ntfs_read_bh(ni->mi.sbi, run, vbo, &ib->rhdr, bytes, &in->nb);
1076         up_read(lock);
1077         if (err == -E_NTFS_FIXUP)
1078                 goto ok;
1079
1080         if (err)
1081                 goto out;
1082
1083 ok:
1084         if (!index_buf_check(ib, bytes, &vbn)) {
1085                 ntfs_inode_err(&ni->vfs_inode, "directory corrupted");
1086                 ntfs_set_state(ni->mi.sbi, NTFS_DIRTY_ERROR);
1087                 err = -EINVAL;
1088                 goto out;
1089         }
1090
1091         if (err == -E_NTFS_FIXUP) {
1092                 ntfs_write_bh(ni->mi.sbi, &ib->rhdr, &in->nb, 0);
1093                 err = 0;
1094         }
1095
1096         /* check for index header length */
1097         if (offsetof(struct INDEX_BUFFER, ihdr) + ib->ihdr.used > bytes) {
1098                 err = -EINVAL;
1099                 goto out;
1100         }
1101
1102         in->index = ib;
1103         *node = in;
1104
1105 out:
1106         if (err == -E_NTFS_CORRUPT) {
1107                 ntfs_inode_err(&ni->vfs_inode, "directory corrupted");
1108                 ntfs_set_state(ni->mi.sbi, NTFS_DIRTY_ERROR);
1109                 err = -EINVAL;
1110         }
1111
1112         if (ib != in->index)
1113                 kfree(ib);
1114
1115         if (*node != in) {
1116                 nb_put(&in->nb);
1117                 kfree(in);
1118         }
1119
1120         return err;
1121 }
1122
1123 /*
1124  * indx_find - Scan NTFS directory for given entry.
1125  */
1126 int indx_find(struct ntfs_index *indx, struct ntfs_inode *ni,
1127               const struct INDEX_ROOT *root, const void *key, size_t key_len,
1128               const void *ctx, int *diff, struct NTFS_DE **entry,
1129               struct ntfs_fnd *fnd)
1130 {
1131         int err;
1132         struct NTFS_DE *e;
1133         struct indx_node *node;
1134
1135         if (!root)
1136                 root = indx_get_root(&ni->dir, ni, NULL, NULL);
1137
1138         if (!root) {
1139                 /* Should not happen. */
1140                 return -EINVAL;
1141         }
1142
1143         /* Check cache. */
1144         e = fnd->level ? fnd->de[fnd->level - 1] : fnd->root_de;
1145         if (e && !de_is_last(e) &&
1146             !(*indx->cmp)(key, key_len, e + 1, le16_to_cpu(e->key_size), ctx)) {
1147                 *entry = e;
1148                 *diff = 0;
1149                 return 0;
1150         }
1151
1152         /* Soft finder reset. */
1153         fnd_clear(fnd);
1154
1155         /* Lookup entry that is <= to the search value. */
1156         e = hdr_find_e(indx, &root->ihdr, key, key_len, ctx, diff);
1157         if (!e)
1158                 return -EINVAL;
1159
1160         fnd->root_de = e;
1161
1162         for (;;) {
1163                 node = NULL;
1164                 if (*diff >= 0 || !de_has_vcn_ex(e))
1165                         break;
1166
1167                 /* Read next level. */
1168                 err = indx_read(indx, ni, de_get_vbn(e), &node);
1169                 if (err)
1170                         return err;
1171
1172                 /* Lookup entry that is <= to the search value. */
1173                 e = hdr_find_e(indx, &node->index->ihdr, key, key_len, ctx,
1174                                diff);
1175                 if (!e) {
1176                         put_indx_node(node);
1177                         return -EINVAL;
1178                 }
1179
1180                 fnd_push(fnd, node, e);
1181         }
1182
1183         *entry = e;
1184         return 0;
1185 }
1186
1187 int indx_find_sort(struct ntfs_index *indx, struct ntfs_inode *ni,
1188                    const struct INDEX_ROOT *root, struct NTFS_DE **entry,
1189                    struct ntfs_fnd *fnd)
1190 {
1191         int err;
1192         struct indx_node *n = NULL;
1193         struct NTFS_DE *e;
1194         size_t iter = 0;
1195         int level = fnd->level;
1196
1197         if (!*entry) {
1198                 /* Start find. */
1199                 e = hdr_first_de(&root->ihdr);
1200                 if (!e)
1201                         return 0;
1202                 fnd_clear(fnd);
1203                 fnd->root_de = e;
1204         } else if (!level) {
1205                 if (de_is_last(fnd->root_de)) {
1206                         *entry = NULL;
1207                         return 0;
1208                 }
1209
1210                 e = hdr_next_de(&root->ihdr, fnd->root_de);
1211                 if (!e)
1212                         return -EINVAL;
1213                 fnd->root_de = e;
1214         } else {
1215                 n = fnd->nodes[level - 1];
1216                 e = fnd->de[level - 1];
1217
1218                 if (de_is_last(e))
1219                         goto pop_level;
1220
1221                 e = hdr_next_de(&n->index->ihdr, e);
1222                 if (!e)
1223                         return -EINVAL;
1224
1225                 fnd->de[level - 1] = e;
1226         }
1227
1228         /* Just to avoid tree cycle. */
1229 next_iter:
1230         if (iter++ >= 1000)
1231                 return -EINVAL;
1232
1233         while (de_has_vcn_ex(e)) {
1234                 if (le16_to_cpu(e->size) <
1235                     sizeof(struct NTFS_DE) + sizeof(u64)) {
1236                         if (n) {
1237                                 fnd_pop(fnd);
1238                                 kfree(n);
1239                         }
1240                         return -EINVAL;
1241                 }
1242
1243                 /* Read next level. */
1244                 err = indx_read(indx, ni, de_get_vbn(e), &n);
1245                 if (err)
1246                         return err;
1247
1248                 /* Try next level. */
1249                 e = hdr_first_de(&n->index->ihdr);
1250                 if (!e) {
1251                         kfree(n);
1252                         return -EINVAL;
1253                 }
1254
1255                 fnd_push(fnd, n, e);
1256         }
1257
1258         if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1259                 *entry = e;
1260                 return 0;
1261         }
1262
1263 pop_level:
1264         for (;;) {
1265                 if (!de_is_last(e))
1266                         goto next_iter;
1267
1268                 /* Pop one level. */
1269                 if (n) {
1270                         fnd_pop(fnd);
1271                         kfree(n);
1272                 }
1273
1274                 level = fnd->level;
1275
1276                 if (level) {
1277                         n = fnd->nodes[level - 1];
1278                         e = fnd->de[level - 1];
1279                 } else if (fnd->root_de) {
1280                         n = NULL;
1281                         e = fnd->root_de;
1282                         fnd->root_de = NULL;
1283                 } else {
1284                         *entry = NULL;
1285                         return 0;
1286                 }
1287
1288                 if (le16_to_cpu(e->size) > sizeof(struct NTFS_DE)) {
1289                         *entry = e;
1290                         if (!fnd->root_de)
1291                                 fnd->root_de = e;
1292                         return 0;
1293                 }
1294         }
1295 }
1296
1297 int indx_find_raw(struct ntfs_index *indx, struct ntfs_inode *ni,
1298                   const struct INDEX_ROOT *root, struct NTFS_DE **entry,
1299                   size_t *off, struct ntfs_fnd *fnd)
1300 {
1301         int err;
1302         struct indx_node *n = NULL;
1303         struct NTFS_DE *e = NULL;
1304         struct NTFS_DE *e2;
1305         size_t bit;
1306         CLST next_used_vbn;
1307         CLST next_vbn;
1308         u32 record_size = ni->mi.sbi->record_size;
1309
1310         /* Use non sorted algorithm. */
1311         if (!*entry) {
1312                 /* This is the first call. */
1313                 e = hdr_first_de(&root->ihdr);
1314                 if (!e)
1315                         return 0;
1316                 fnd_clear(fnd);
1317                 fnd->root_de = e;
1318
1319                 /* The first call with setup of initial element. */
1320                 if (*off >= record_size) {
1321                         next_vbn = (((*off - record_size) >> indx->index_bits))
1322                                    << indx->idx2vbn_bits;
1323                         /* Jump inside cycle 'for'. */
1324                         goto next;
1325                 }
1326
1327                 /* Start enumeration from root. */
1328                 *off = 0;
1329         } else if (!fnd->root_de)
1330                 return -EINVAL;
1331
1332         for (;;) {
1333                 /* Check if current entry can be used. */
1334                 if (e && le16_to_cpu(e->size) > sizeof(struct NTFS_DE))
1335                         goto ok;
1336
1337                 if (!fnd->level) {
1338                         /* Continue to enumerate root. */
1339                         if (!de_is_last(fnd->root_de)) {
1340                                 e = hdr_next_de(&root->ihdr, fnd->root_de);
1341                                 if (!e)
1342                                         return -EINVAL;
1343                                 fnd->root_de = e;
1344                                 continue;
1345                         }
1346
1347                         /* Start to enumerate indexes from 0. */
1348                         next_vbn = 0;
1349                 } else {
1350                         /* Continue to enumerate indexes. */
1351                         e2 = fnd->de[fnd->level - 1];
1352
1353                         n = fnd->nodes[fnd->level - 1];
1354
1355                         if (!de_is_last(e2)) {
1356                                 e = hdr_next_de(&n->index->ihdr, e2);
1357                                 if (!e)
1358                                         return -EINVAL;
1359                                 fnd->de[fnd->level - 1] = e;
1360                                 continue;
1361                         }
1362
1363                         /* Continue with next index. */
1364                         next_vbn = le64_to_cpu(n->index->vbn) +
1365                                    root->index_block_clst;
1366                 }
1367
1368 next:
1369                 /* Release current index. */
1370                 if (n) {
1371                         fnd_pop(fnd);
1372                         put_indx_node(n);
1373                         n = NULL;
1374                 }
1375
1376                 /* Skip all free indexes. */
1377                 bit = next_vbn >> indx->idx2vbn_bits;
1378                 err = indx_used_bit(indx, ni, &bit);
1379                 if (err == -ENOENT || bit == MINUS_ONE_T) {
1380                         /* No used indexes. */
1381                         *entry = NULL;
1382                         return 0;
1383                 }
1384
1385                 next_used_vbn = bit << indx->idx2vbn_bits;
1386
1387                 /* Read buffer into memory. */
1388                 err = indx_read(indx, ni, next_used_vbn, &n);
1389                 if (err)
1390                         return err;
1391
1392                 e = hdr_first_de(&n->index->ihdr);
1393                 fnd_push(fnd, n, e);
1394                 if (!e)
1395                         return -EINVAL;
1396         }
1397
1398 ok:
1399         /* Return offset to restore enumerator if necessary. */
1400         if (!n) {
1401                 /* 'e' points in root, */
1402                 *off = PtrOffset(&root->ihdr, e);
1403         } else {
1404                 /* 'e' points in index, */
1405                 *off = (le64_to_cpu(n->index->vbn) << indx->vbn2vbo_bits) +
1406                        record_size + PtrOffset(&n->index->ihdr, e);
1407         }
1408
1409         *entry = e;
1410         return 0;
1411 }
1412
1413 /*
1414  * indx_create_allocate - Create "Allocation + Bitmap" attributes.
1415  */
1416 static int indx_create_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
1417                                 CLST *vbn)
1418 {
1419         int err;
1420         struct ntfs_sb_info *sbi = ni->mi.sbi;
1421         struct ATTRIB *bitmap;
1422         struct ATTRIB *alloc;
1423         u32 data_size = 1u << indx->index_bits;
1424         u32 alloc_size = ntfs_up_cluster(sbi, data_size);
1425         CLST len = alloc_size >> sbi->cluster_bits;
1426         const struct INDEX_NAMES *in = &s_index_names[indx->type];
1427         CLST alen;
1428         struct runs_tree run;
1429
1430         run_init(&run);
1431
1432         err = attr_allocate_clusters(sbi, &run, 0, 0, len, NULL, 0, &alen, 0,
1433                                      NULL);
1434         if (err)
1435                 goto out;
1436
1437         err = ni_insert_nonresident(ni, ATTR_ALLOC, in->name, in->name_len,
1438                                     &run, 0, len, 0, &alloc, NULL, NULL);
1439         if (err)
1440                 goto out1;
1441
1442         alloc->nres.valid_size = alloc->nres.data_size = cpu_to_le64(data_size);
1443
1444         err = ni_insert_resident(ni, bitmap_size(1), ATTR_BITMAP, in->name,
1445                                  in->name_len, &bitmap, NULL, NULL);
1446         if (err)
1447                 goto out2;
1448
1449         if (in->name == I30_NAME) {
1450                 ni->vfs_inode.i_size = data_size;
1451                 inode_set_bytes(&ni->vfs_inode, alloc_size);
1452         }
1453
1454         memcpy(&indx->alloc_run, &run, sizeof(run));
1455
1456         *vbn = 0;
1457
1458         return 0;
1459
1460 out2:
1461         mi_remove_attr(NULL, &ni->mi, alloc);
1462
1463 out1:
1464         run_deallocate(sbi, &run, false);
1465
1466 out:
1467         return err;
1468 }
1469
1470 /*
1471  * indx_add_allocate - Add clusters to index.
1472  */
1473 static int indx_add_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
1474                              CLST *vbn)
1475 {
1476         int err;
1477         size_t bit;
1478         u64 data_size;
1479         u64 bmp_size, bmp_size_v;
1480         struct ATTRIB *bmp, *alloc;
1481         struct mft_inode *mi;
1482         const struct INDEX_NAMES *in = &s_index_names[indx->type];
1483
1484         err = indx_find_free(indx, ni, &bit, &bmp);
1485         if (err)
1486                 goto out1;
1487
1488         if (bit != MINUS_ONE_T) {
1489                 bmp = NULL;
1490         } else {
1491                 if (bmp->non_res) {
1492                         bmp_size = le64_to_cpu(bmp->nres.data_size);
1493                         bmp_size_v = le64_to_cpu(bmp->nres.valid_size);
1494                 } else {
1495                         bmp_size = bmp_size_v = le32_to_cpu(bmp->res.data_size);
1496                 }
1497
1498                 bit = bmp_size << 3;
1499         }
1500
1501         data_size = (u64)(bit + 1) << indx->index_bits;
1502
1503         if (bmp) {
1504                 /* Increase bitmap. */
1505                 err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
1506                                     &indx->bitmap_run, bitmap_size(bit + 1),
1507                                     NULL, true, NULL);
1508                 if (err)
1509                         goto out1;
1510         }
1511
1512         alloc = ni_find_attr(ni, NULL, NULL, ATTR_ALLOC, in->name, in->name_len,
1513                              NULL, &mi);
1514         if (!alloc) {
1515                 err = -EINVAL;
1516                 if (bmp)
1517                         goto out2;
1518                 goto out1;
1519         }
1520
1521         /* Increase allocation. */
1522         err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
1523                             &indx->alloc_run, data_size, &data_size, true,
1524                             NULL);
1525         if (err) {
1526                 if (bmp)
1527                         goto out2;
1528                 goto out1;
1529         }
1530
1531         *vbn = bit << indx->idx2vbn_bits;
1532
1533         return 0;
1534
1535 out2:
1536         /* Ops. No space? */
1537         attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
1538                       &indx->bitmap_run, bmp_size, &bmp_size_v, false, NULL);
1539
1540 out1:
1541         return err;
1542 }
1543
1544 /*
1545  * indx_insert_into_root - Attempt to insert an entry into the index root.
1546  *
1547  * @undo - True if we undoing previous remove.
1548  * If necessary, it will twiddle the index b-tree.
1549  */
1550 static int indx_insert_into_root(struct ntfs_index *indx, struct ntfs_inode *ni,
1551                                  const struct NTFS_DE *new_de,
1552                                  struct NTFS_DE *root_de, const void *ctx,
1553                                  struct ntfs_fnd *fnd, bool undo)
1554 {
1555         int err = 0;
1556         struct NTFS_DE *e, *e0, *re;
1557         struct mft_inode *mi;
1558         struct ATTRIB *attr;
1559         struct INDEX_HDR *hdr;
1560         struct indx_node *n;
1561         CLST new_vbn;
1562         __le64 *sub_vbn, t_vbn;
1563         u16 new_de_size;
1564         u32 hdr_used, hdr_total, asize, to_move;
1565         u32 root_size, new_root_size;
1566         struct ntfs_sb_info *sbi;
1567         int ds_root;
1568         struct INDEX_ROOT *root, *a_root;
1569
1570         /* Get the record this root placed in. */
1571         root = indx_get_root(indx, ni, &attr, &mi);
1572         if (!root)
1573                 return -EINVAL;
1574
1575         /*
1576          * Try easy case:
1577          * hdr_insert_de will succeed if there's
1578          * room the root for the new entry.
1579          */
1580         hdr = &root->ihdr;
1581         sbi = ni->mi.sbi;
1582         new_de_size = le16_to_cpu(new_de->size);
1583         hdr_used = le32_to_cpu(hdr->used);
1584         hdr_total = le32_to_cpu(hdr->total);
1585         asize = le32_to_cpu(attr->size);
1586         root_size = le32_to_cpu(attr->res.data_size);
1587
1588         ds_root = new_de_size + hdr_used - hdr_total;
1589
1590         /* If 'undo' is set then reduce requirements. */
1591         if ((undo || asize + ds_root < sbi->max_bytes_per_attr) &&
1592             mi_resize_attr(mi, attr, ds_root)) {
1593                 hdr->total = cpu_to_le32(hdr_total + ds_root);
1594                 e = hdr_insert_de(indx, hdr, new_de, root_de, ctx);
1595                 WARN_ON(!e);
1596                 fnd_clear(fnd);
1597                 fnd->root_de = e;
1598
1599                 return 0;
1600         }
1601
1602         /* Make a copy of root attribute to restore if error. */
1603         a_root = kmemdup(attr, asize, GFP_NOFS);
1604         if (!a_root)
1605                 return -ENOMEM;
1606
1607         /*
1608          * Copy all the non-end entries from
1609          * the index root to the new buffer.
1610          */
1611         to_move = 0;
1612         e0 = hdr_first_de(hdr);
1613
1614         /* Calculate the size to copy. */
1615         for (e = e0;; e = hdr_next_de(hdr, e)) {
1616                 if (!e) {
1617                         err = -EINVAL;
1618                         goto out_free_root;
1619                 }
1620
1621                 if (de_is_last(e))
1622                         break;
1623                 to_move += le16_to_cpu(e->size);
1624         }
1625
1626         if (!to_move) {
1627                 re = NULL;
1628         } else {
1629                 re = kmemdup(e0, to_move, GFP_NOFS);
1630                 if (!re) {
1631                         err = -ENOMEM;
1632                         goto out_free_root;
1633                 }
1634         }
1635
1636         sub_vbn = NULL;
1637         if (de_has_vcn(e)) {
1638                 t_vbn = de_get_vbn_le(e);
1639                 sub_vbn = &t_vbn;
1640         }
1641
1642         new_root_size = sizeof(struct INDEX_ROOT) + sizeof(struct NTFS_DE) +
1643                         sizeof(u64);
1644         ds_root = new_root_size - root_size;
1645
1646         if (ds_root > 0 && asize + ds_root > sbi->max_bytes_per_attr) {
1647                 /* Make root external. */
1648                 err = -EOPNOTSUPP;
1649                 goto out_free_re;
1650         }
1651
1652         if (ds_root)
1653                 mi_resize_attr(mi, attr, ds_root);
1654
1655         /* Fill first entry (vcn will be set later). */
1656         e = (struct NTFS_DE *)(root + 1);
1657         memset(e, 0, sizeof(struct NTFS_DE));
1658         e->size = cpu_to_le16(sizeof(struct NTFS_DE) + sizeof(u64));
1659         e->flags = NTFS_IE_HAS_SUBNODES | NTFS_IE_LAST;
1660
1661         hdr->flags = 1;
1662         hdr->used = hdr->total =
1663                 cpu_to_le32(new_root_size - offsetof(struct INDEX_ROOT, ihdr));
1664
1665         fnd->root_de = hdr_first_de(hdr);
1666         mi->dirty = true;
1667
1668         /* Create alloc and bitmap attributes (if not). */
1669         err = run_is_empty(&indx->alloc_run)
1670                       ? indx_create_allocate(indx, ni, &new_vbn)
1671                       : indx_add_allocate(indx, ni, &new_vbn);
1672
1673         /* Layout of record may be changed, so rescan root. */
1674         root = indx_get_root(indx, ni, &attr, &mi);
1675         if (!root) {
1676                 /* Bug? */
1677                 ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1678                 err = -EINVAL;
1679                 goto out_free_re;
1680         }
1681
1682         if (err) {
1683                 /* Restore root. */
1684                 if (mi_resize_attr(mi, attr, -ds_root)) {
1685                         memcpy(attr, a_root, asize);
1686                 } else {
1687                         /* Bug? */
1688                         ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1689                 }
1690                 goto out_free_re;
1691         }
1692
1693         e = (struct NTFS_DE *)(root + 1);
1694         *(__le64 *)(e + 1) = cpu_to_le64(new_vbn);
1695         mi->dirty = true;
1696
1697         /* Now we can create/format the new buffer and copy the entries into. */
1698         n = indx_new(indx, ni, new_vbn, sub_vbn);
1699         if (IS_ERR(n)) {
1700                 err = PTR_ERR(n);
1701                 goto out_free_re;
1702         }
1703
1704         hdr = &n->index->ihdr;
1705         hdr_used = le32_to_cpu(hdr->used);
1706         hdr_total = le32_to_cpu(hdr->total);
1707
1708         /* Copy root entries into new buffer. */
1709         hdr_insert_head(hdr, re, to_move);
1710
1711         /* Update bitmap attribute. */
1712         indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
1713
1714         /* Check if we can insert new entry new index buffer. */
1715         if (hdr_used + new_de_size > hdr_total) {
1716                 /*
1717                  * This occurs if MFT record is the same or bigger than index
1718                  * buffer. Move all root new index and have no space to add
1719                  * new entry classic case when MFT record is 1K and index
1720                  * buffer 4K the problem should not occurs.
1721                  */
1722                 kfree(re);
1723                 indx_write(indx, ni, n, 0);
1724
1725                 put_indx_node(n);
1726                 fnd_clear(fnd);
1727                 err = indx_insert_entry(indx, ni, new_de, ctx, fnd, undo);
1728                 goto out_free_root;
1729         }
1730
1731         /*
1732          * Now root is a parent for new index buffer.
1733          * Insert NewEntry a new buffer.
1734          */
1735         e = hdr_insert_de(indx, hdr, new_de, NULL, ctx);
1736         if (!e) {
1737                 err = -EINVAL;
1738                 goto out_put_n;
1739         }
1740         fnd_push(fnd, n, e);
1741
1742         /* Just write updates index into disk. */
1743         indx_write(indx, ni, n, 0);
1744
1745         n = NULL;
1746
1747 out_put_n:
1748         put_indx_node(n);
1749 out_free_re:
1750         kfree(re);
1751 out_free_root:
1752         kfree(a_root);
1753         return err;
1754 }
1755
1756 /*
1757  * indx_insert_into_buffer
1758  *
1759  * Attempt to insert an entry into an Index Allocation Buffer.
1760  * If necessary, it will split the buffer.
1761  */
1762 static int
1763 indx_insert_into_buffer(struct ntfs_index *indx, struct ntfs_inode *ni,
1764                         struct INDEX_ROOT *root, const struct NTFS_DE *new_de,
1765                         const void *ctx, int level, struct ntfs_fnd *fnd)
1766 {
1767         int err;
1768         const struct NTFS_DE *sp;
1769         struct NTFS_DE *e, *de_t, *up_e;
1770         struct indx_node *n2;
1771         struct indx_node *n1 = fnd->nodes[level];
1772         struct INDEX_HDR *hdr1 = &n1->index->ihdr;
1773         struct INDEX_HDR *hdr2;
1774         u32 to_copy, used;
1775         CLST new_vbn;
1776         __le64 t_vbn, *sub_vbn;
1777         u16 sp_size;
1778
1779         /* Try the most easy case. */
1780         e = fnd->level - 1 == level ? fnd->de[level] : NULL;
1781         e = hdr_insert_de(indx, hdr1, new_de, e, ctx);
1782         fnd->de[level] = e;
1783         if (e) {
1784                 /* Just write updated index into disk. */
1785                 indx_write(indx, ni, n1, 0);
1786                 return 0;
1787         }
1788
1789         /*
1790          * No space to insert into buffer. Split it.
1791          * To split we:
1792          *  - Save split point ('cause index buffers will be changed)
1793          * - Allocate NewBuffer and copy all entries <= sp into new buffer
1794          * - Remove all entries (sp including) from TargetBuffer
1795          * - Insert NewEntry into left or right buffer (depending on sp <=>
1796          *     NewEntry)
1797          * - Insert sp into parent buffer (or root)
1798          * - Make sp a parent for new buffer
1799          */
1800         sp = hdr_find_split(hdr1);
1801         if (!sp)
1802                 return -EINVAL;
1803
1804         sp_size = le16_to_cpu(sp->size);
1805         up_e = kmalloc(sp_size + sizeof(u64), GFP_NOFS);
1806         if (!up_e)
1807                 return -ENOMEM;
1808         memcpy(up_e, sp, sp_size);
1809
1810         if (!hdr1->flags) {
1811                 up_e->flags |= NTFS_IE_HAS_SUBNODES;
1812                 up_e->size = cpu_to_le16(sp_size + sizeof(u64));
1813                 sub_vbn = NULL;
1814         } else {
1815                 t_vbn = de_get_vbn_le(up_e);
1816                 sub_vbn = &t_vbn;
1817         }
1818
1819         /* Allocate on disk a new index allocation buffer. */
1820         err = indx_add_allocate(indx, ni, &new_vbn);
1821         if (err)
1822                 goto out;
1823
1824         /* Allocate and format memory a new index buffer. */
1825         n2 = indx_new(indx, ni, new_vbn, sub_vbn);
1826         if (IS_ERR(n2)) {
1827                 err = PTR_ERR(n2);
1828                 goto out;
1829         }
1830
1831         hdr2 = &n2->index->ihdr;
1832
1833         /* Make sp a parent for new buffer. */
1834         de_set_vbn(up_e, new_vbn);
1835
1836         /* Copy all the entries <= sp into the new buffer. */
1837         de_t = hdr_first_de(hdr1);
1838         to_copy = PtrOffset(de_t, sp);
1839         hdr_insert_head(hdr2, de_t, to_copy);
1840
1841         /* Remove all entries (sp including) from hdr1. */
1842         used = le32_to_cpu(hdr1->used) - to_copy - sp_size;
1843         memmove(de_t, Add2Ptr(sp, sp_size), used - le32_to_cpu(hdr1->de_off));
1844         hdr1->used = cpu_to_le32(used);
1845
1846         /*
1847          * Insert new entry into left or right buffer
1848          * (depending on sp <=> new_de).
1849          */
1850         hdr_insert_de(indx,
1851                       (*indx->cmp)(new_de + 1, le16_to_cpu(new_de->key_size),
1852                                    up_e + 1, le16_to_cpu(up_e->key_size),
1853                                    ctx) < 0
1854                               ? hdr2
1855                               : hdr1,
1856                       new_de, NULL, ctx);
1857
1858         indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
1859
1860         indx_write(indx, ni, n1, 0);
1861         indx_write(indx, ni, n2, 0);
1862
1863         put_indx_node(n2);
1864
1865         /*
1866          * We've finished splitting everybody, so we are ready to
1867          * insert the promoted entry into the parent.
1868          */
1869         if (!level) {
1870                 /* Insert in root. */
1871                 err = indx_insert_into_root(indx, ni, up_e, NULL, ctx, fnd, 0);
1872                 if (err)
1873                         goto out;
1874         } else {
1875                 /*
1876                  * The target buffer's parent is another index buffer.
1877                  * TODO: Remove recursion.
1878                  */
1879                 err = indx_insert_into_buffer(indx, ni, root, up_e, ctx,
1880                                               level - 1, fnd);
1881                 if (err)
1882                         goto out;
1883         }
1884
1885 out:
1886         kfree(up_e);
1887
1888         return err;
1889 }
1890
1891 /*
1892  * indx_insert_entry - Insert new entry into index.
1893  *
1894  * @undo - True if we undoing previous remove.
1895  */
1896 int indx_insert_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
1897                       const struct NTFS_DE *new_de, const void *ctx,
1898                       struct ntfs_fnd *fnd, bool undo)
1899 {
1900         int err;
1901         int diff;
1902         struct NTFS_DE *e;
1903         struct ntfs_fnd *fnd_a = NULL;
1904         struct INDEX_ROOT *root;
1905
1906         if (!fnd) {
1907                 fnd_a = fnd_get();
1908                 if (!fnd_a) {
1909                         err = -ENOMEM;
1910                         goto out1;
1911                 }
1912                 fnd = fnd_a;
1913         }
1914
1915         root = indx_get_root(indx, ni, NULL, NULL);
1916         if (!root) {
1917                 err = -EINVAL;
1918                 goto out;
1919         }
1920
1921         if (fnd_is_empty(fnd)) {
1922                 /*
1923                  * Find the spot the tree where we want to
1924                  * insert the new entry.
1925                  */
1926                 err = indx_find(indx, ni, root, new_de + 1,
1927                                 le16_to_cpu(new_de->key_size), ctx, &diff, &e,
1928                                 fnd);
1929                 if (err)
1930                         goto out;
1931
1932                 if (!diff) {
1933                         err = -EEXIST;
1934                         goto out;
1935                 }
1936         }
1937
1938         if (!fnd->level) {
1939                 /*
1940                  * The root is also a leaf, so we'll insert the
1941                  * new entry into it.
1942                  */
1943                 err = indx_insert_into_root(indx, ni, new_de, fnd->root_de, ctx,
1944                                             fnd, undo);
1945                 if (err)
1946                         goto out;
1947         } else {
1948                 /*
1949                  * Found a leaf buffer, so we'll insert the new entry into it.
1950                  */
1951                 err = indx_insert_into_buffer(indx, ni, root, new_de, ctx,
1952                                               fnd->level - 1, fnd);
1953                 if (err)
1954                         goto out;
1955         }
1956
1957 out:
1958         fnd_put(fnd_a);
1959 out1:
1960         return err;
1961 }
1962
1963 /*
1964  * indx_find_buffer - Locate a buffer from the tree.
1965  */
1966 static struct indx_node *indx_find_buffer(struct ntfs_index *indx,
1967                                           struct ntfs_inode *ni,
1968                                           const struct INDEX_ROOT *root,
1969                                           __le64 vbn, struct indx_node *n)
1970 {
1971         int err;
1972         const struct NTFS_DE *e;
1973         struct indx_node *r;
1974         const struct INDEX_HDR *hdr = n ? &n->index->ihdr : &root->ihdr;
1975
1976         /* Step 1: Scan one level. */
1977         for (e = hdr_first_de(hdr);; e = hdr_next_de(hdr, e)) {
1978                 if (!e)
1979                         return ERR_PTR(-EINVAL);
1980
1981                 if (de_has_vcn(e) && vbn == de_get_vbn_le(e))
1982                         return n;
1983
1984                 if (de_is_last(e))
1985                         break;
1986         }
1987
1988         /* Step2: Do recursion. */
1989         e = Add2Ptr(hdr, le32_to_cpu(hdr->de_off));
1990         for (;;) {
1991                 if (de_has_vcn_ex(e)) {
1992                         err = indx_read(indx, ni, de_get_vbn(e), &n);
1993                         if (err)
1994                                 return ERR_PTR(err);
1995
1996                         r = indx_find_buffer(indx, ni, root, vbn, n);
1997                         if (r)
1998                                 return r;
1999                 }
2000
2001                 if (de_is_last(e))
2002                         break;
2003
2004                 e = Add2Ptr(e, le16_to_cpu(e->size));
2005         }
2006
2007         return NULL;
2008 }
2009
2010 /*
2011  * indx_shrink - Deallocate unused tail indexes.
2012  */
2013 static int indx_shrink(struct ntfs_index *indx, struct ntfs_inode *ni,
2014                        size_t bit)
2015 {
2016         int err = 0;
2017         u64 bpb, new_data;
2018         size_t nbits;
2019         struct ATTRIB *b;
2020         struct ATTR_LIST_ENTRY *le = NULL;
2021         const struct INDEX_NAMES *in = &s_index_names[indx->type];
2022
2023         b = ni_find_attr(ni, NULL, &le, ATTR_BITMAP, in->name, in->name_len,
2024                          NULL, NULL);
2025
2026         if (!b)
2027                 return -ENOENT;
2028
2029         if (!b->non_res) {
2030                 unsigned long pos;
2031                 const unsigned long *bm = resident_data(b);
2032
2033                 nbits = (size_t)le32_to_cpu(b->res.data_size) * 8;
2034
2035                 if (bit >= nbits)
2036                         return 0;
2037
2038                 pos = find_next_bit(bm, nbits, bit);
2039                 if (pos < nbits)
2040                         return 0;
2041         } else {
2042                 size_t used = MINUS_ONE_T;
2043
2044                 nbits = le64_to_cpu(b->nres.data_size) * 8;
2045
2046                 if (bit >= nbits)
2047                         return 0;
2048
2049                 err = scan_nres_bitmap(ni, b, indx, bit, &scan_for_used, &used);
2050                 if (err)
2051                         return err;
2052
2053                 if (used != MINUS_ONE_T)
2054                         return 0;
2055         }
2056
2057         new_data = (u64)bit << indx->index_bits;
2058
2059         err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
2060                             &indx->alloc_run, new_data, &new_data, false, NULL);
2061         if (err)
2062                 return err;
2063
2064         bpb = bitmap_size(bit);
2065         if (bpb * 8 == nbits)
2066                 return 0;
2067
2068         err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
2069                             &indx->bitmap_run, bpb, &bpb, false, NULL);
2070
2071         return err;
2072 }
2073
2074 static int indx_free_children(struct ntfs_index *indx, struct ntfs_inode *ni,
2075                               const struct NTFS_DE *e, bool trim)
2076 {
2077         int err;
2078         struct indx_node *n = NULL;
2079         struct INDEX_HDR *hdr;
2080         CLST vbn = de_get_vbn(e);
2081         size_t i;
2082
2083         err = indx_read(indx, ni, vbn, &n);
2084         if (err)
2085                 return err;
2086
2087         hdr = &n->index->ihdr;
2088         /* First, recurse into the children, if any. */
2089         if (hdr_has_subnode(hdr)) {
2090                 for (e = hdr_first_de(hdr); e; e = hdr_next_de(hdr, e)) {
2091                         indx_free_children(indx, ni, e, false);
2092                         if (de_is_last(e))
2093                                 break;
2094                 }
2095         }
2096
2097         put_indx_node(n);
2098
2099         i = vbn >> indx->idx2vbn_bits;
2100         /*
2101          * We've gotten rid of the children; add this buffer to the free list.
2102          */
2103         indx_mark_free(indx, ni, i);
2104
2105         if (!trim)
2106                 return 0;
2107
2108         /*
2109          * If there are no used indexes after current free index
2110          * then we can truncate allocation and bitmap.
2111          * Use bitmap to estimate the case.
2112          */
2113         indx_shrink(indx, ni, i + 1);
2114         return 0;
2115 }
2116
2117 /*
2118  * indx_get_entry_to_replace
2119  *
2120  * Find a replacement entry for a deleted entry.
2121  * Always returns a node entry:
2122  * NTFS_IE_HAS_SUBNODES is set the flags and the size includes the sub_vcn.
2123  */
2124 static int indx_get_entry_to_replace(struct ntfs_index *indx,
2125                                      struct ntfs_inode *ni,
2126                                      const struct NTFS_DE *de_next,
2127                                      struct NTFS_DE **de_to_replace,
2128                                      struct ntfs_fnd *fnd)
2129 {
2130         int err;
2131         int level = -1;
2132         CLST vbn;
2133         struct NTFS_DE *e, *te, *re;
2134         struct indx_node *n;
2135         struct INDEX_BUFFER *ib;
2136
2137         *de_to_replace = NULL;
2138
2139         /* Find first leaf entry down from de_next. */
2140         vbn = de_get_vbn(de_next);
2141         for (;;) {
2142                 n = NULL;
2143                 err = indx_read(indx, ni, vbn, &n);
2144                 if (err)
2145                         goto out;
2146
2147                 e = hdr_first_de(&n->index->ihdr);
2148                 fnd_push(fnd, n, e);
2149
2150                 if (!de_is_last(e)) {
2151                         /*
2152                          * This buffer is non-empty, so its first entry
2153                          * could be used as the replacement entry.
2154                          */
2155                         level = fnd->level - 1;
2156                 }
2157
2158                 if (!de_has_vcn(e))
2159                         break;
2160
2161                 /* This buffer is a node. Continue to go down. */
2162                 vbn = de_get_vbn(e);
2163         }
2164
2165         if (level == -1)
2166                 goto out;
2167
2168         n = fnd->nodes[level];
2169         te = hdr_first_de(&n->index->ihdr);
2170         /* Copy the candidate entry into the replacement entry buffer. */
2171         re = kmalloc(le16_to_cpu(te->size) + sizeof(u64), GFP_NOFS);
2172         if (!re) {
2173                 err = -ENOMEM;
2174                 goto out;
2175         }
2176
2177         *de_to_replace = re;
2178         memcpy(re, te, le16_to_cpu(te->size));
2179
2180         if (!de_has_vcn(re)) {
2181                 /*
2182                  * The replacement entry we found doesn't have a sub_vcn.
2183                  * increase its size to hold one.
2184                  */
2185                 le16_add_cpu(&re->size, sizeof(u64));
2186                 re->flags |= NTFS_IE_HAS_SUBNODES;
2187         } else {
2188                 /*
2189                  * The replacement entry we found was a node entry, which
2190                  * means that all its child buffers are empty. Return them
2191                  * to the free pool.
2192                  */
2193                 indx_free_children(indx, ni, te, true);
2194         }
2195
2196         /*
2197          * Expunge the replacement entry from its former location,
2198          * and then write that buffer.
2199          */
2200         ib = n->index;
2201         e = hdr_delete_de(&ib->ihdr, te);
2202
2203         fnd->de[level] = e;
2204         indx_write(indx, ni, n, 0);
2205
2206         /* Check to see if this action created an empty leaf. */
2207         if (ib_is_leaf(ib) && ib_is_empty(ib))
2208                 return 0;
2209
2210 out:
2211         fnd_clear(fnd);
2212         return err;
2213 }
2214
2215 /*
2216  * indx_delete_entry - Delete an entry from the index.
2217  */
2218 int indx_delete_entry(struct ntfs_index *indx, struct ntfs_inode *ni,
2219                       const void *key, u32 key_len, const void *ctx)
2220 {
2221         int err, diff;
2222         struct INDEX_ROOT *root;
2223         struct INDEX_HDR *hdr;
2224         struct ntfs_fnd *fnd, *fnd2;
2225         struct INDEX_BUFFER *ib;
2226         struct NTFS_DE *e, *re, *next, *prev, *me;
2227         struct indx_node *n, *n2d = NULL;
2228         __le64 sub_vbn;
2229         int level, level2;
2230         struct ATTRIB *attr;
2231         struct mft_inode *mi;
2232         u32 e_size, root_size, new_root_size;
2233         size_t trim_bit;
2234         const struct INDEX_NAMES *in;
2235
2236         fnd = fnd_get();
2237         if (!fnd) {
2238                 err = -ENOMEM;
2239                 goto out2;
2240         }
2241
2242         fnd2 = fnd_get();
2243         if (!fnd2) {
2244                 err = -ENOMEM;
2245                 goto out1;
2246         }
2247
2248         root = indx_get_root(indx, ni, &attr, &mi);
2249         if (!root) {
2250                 err = -EINVAL;
2251                 goto out;
2252         }
2253
2254         /* Locate the entry to remove. */
2255         err = indx_find(indx, ni, root, key, key_len, ctx, &diff, &e, fnd);
2256         if (err)
2257                 goto out;
2258
2259         if (!e || diff) {
2260                 err = -ENOENT;
2261                 goto out;
2262         }
2263
2264         level = fnd->level;
2265
2266         if (level) {
2267                 n = fnd->nodes[level - 1];
2268                 e = fnd->de[level - 1];
2269                 ib = n->index;
2270                 hdr = &ib->ihdr;
2271         } else {
2272                 hdr = &root->ihdr;
2273                 e = fnd->root_de;
2274                 n = NULL;
2275         }
2276
2277         e_size = le16_to_cpu(e->size);
2278
2279         if (!de_has_vcn_ex(e)) {
2280                 /* The entry to delete is a leaf, so we can just rip it out. */
2281                 hdr_delete_de(hdr, e);
2282
2283                 if (!level) {
2284                         hdr->total = hdr->used;
2285
2286                         /* Shrink resident root attribute. */
2287                         mi_resize_attr(mi, attr, 0 - e_size);
2288                         goto out;
2289                 }
2290
2291                 indx_write(indx, ni, n, 0);
2292
2293                 /*
2294                  * Check to see if removing that entry made
2295                  * the leaf empty.
2296                  */
2297                 if (ib_is_leaf(ib) && ib_is_empty(ib)) {
2298                         fnd_pop(fnd);
2299                         fnd_push(fnd2, n, e);
2300                 }
2301         } else {
2302                 /*
2303                  * The entry we wish to delete is a node buffer, so we
2304                  * have to find a replacement for it.
2305                  */
2306                 next = de_get_next(e);
2307
2308                 err = indx_get_entry_to_replace(indx, ni, next, &re, fnd2);
2309                 if (err)
2310                         goto out;
2311
2312                 if (re) {
2313                         de_set_vbn_le(re, de_get_vbn_le(e));
2314                         hdr_delete_de(hdr, e);
2315
2316                         err = level ? indx_insert_into_buffer(indx, ni, root,
2317                                                               re, ctx,
2318                                                               fnd->level - 1,
2319                                                               fnd)
2320                                     : indx_insert_into_root(indx, ni, re, e,
2321                                                             ctx, fnd, 0);
2322                         kfree(re);
2323
2324                         if (err)
2325                                 goto out;
2326                 } else {
2327                         /*
2328                          * There is no replacement for the current entry.
2329                          * This means that the subtree rooted at its node
2330                          * is empty, and can be deleted, which turn means
2331                          * that the node can just inherit the deleted
2332                          * entry sub_vcn.
2333                          */
2334                         indx_free_children(indx, ni, next, true);
2335
2336                         de_set_vbn_le(next, de_get_vbn_le(e));
2337                         hdr_delete_de(hdr, e);
2338                         if (level) {
2339                                 indx_write(indx, ni, n, 0);
2340                         } else {
2341                                 hdr->total = hdr->used;
2342
2343                                 /* Shrink resident root attribute. */
2344                                 mi_resize_attr(mi, attr, 0 - e_size);
2345                         }
2346                 }
2347         }
2348
2349         /* Delete a branch of tree. */
2350         if (!fnd2 || !fnd2->level)
2351                 goto out;
2352
2353         /* Reinit root 'cause it can be changed. */
2354         root = indx_get_root(indx, ni, &attr, &mi);
2355         if (!root) {
2356                 err = -EINVAL;
2357                 goto out;
2358         }
2359
2360         n2d = NULL;
2361         sub_vbn = fnd2->nodes[0]->index->vbn;
2362         level2 = 0;
2363         level = fnd->level;
2364
2365         hdr = level ? &fnd->nodes[level - 1]->index->ihdr : &root->ihdr;
2366
2367         /* Scan current level. */
2368         for (e = hdr_first_de(hdr);; e = hdr_next_de(hdr, e)) {
2369                 if (!e) {
2370                         err = -EINVAL;
2371                         goto out;
2372                 }
2373
2374                 if (de_has_vcn(e) && sub_vbn == de_get_vbn_le(e))
2375                         break;
2376
2377                 if (de_is_last(e)) {
2378                         e = NULL;
2379                         break;
2380                 }
2381         }
2382
2383         if (!e) {
2384                 /* Do slow search from root. */
2385                 struct indx_node *in;
2386
2387                 fnd_clear(fnd);
2388
2389                 in = indx_find_buffer(indx, ni, root, sub_vbn, NULL);
2390                 if (IS_ERR(in)) {
2391                         err = PTR_ERR(in);
2392                         goto out;
2393                 }
2394
2395                 if (in)
2396                         fnd_push(fnd, in, NULL);
2397         }
2398
2399         /* Merge fnd2 -> fnd. */
2400         for (level = 0; level < fnd2->level; level++) {
2401                 fnd_push(fnd, fnd2->nodes[level], fnd2->de[level]);
2402                 fnd2->nodes[level] = NULL;
2403         }
2404         fnd2->level = 0;
2405
2406         hdr = NULL;
2407         for (level = fnd->level; level; level--) {
2408                 struct indx_node *in = fnd->nodes[level - 1];
2409
2410                 ib = in->index;
2411                 if (ib_is_empty(ib)) {
2412                         sub_vbn = ib->vbn;
2413                 } else {
2414                         hdr = &ib->ihdr;
2415                         n2d = in;
2416                         level2 = level;
2417                         break;
2418                 }
2419         }
2420
2421         if (!hdr)
2422                 hdr = &root->ihdr;
2423
2424         e = hdr_first_de(hdr);
2425         if (!e) {
2426                 err = -EINVAL;
2427                 goto out;
2428         }
2429
2430         if (hdr != &root->ihdr || !de_is_last(e)) {
2431                 prev = NULL;
2432                 while (!de_is_last(e)) {
2433                         if (de_has_vcn(e) && sub_vbn == de_get_vbn_le(e))
2434                                 break;
2435                         prev = e;
2436                         e = hdr_next_de(hdr, e);
2437                         if (!e) {
2438                                 err = -EINVAL;
2439                                 goto out;
2440                         }
2441                 }
2442
2443                 if (sub_vbn != de_get_vbn_le(e)) {
2444                         /*
2445                          * Didn't find the parent entry, although this buffer
2446                          * is the parent trail. Something is corrupt.
2447                          */
2448                         err = -EINVAL;
2449                         goto out;
2450                 }
2451
2452                 if (de_is_last(e)) {
2453                         /*
2454                          * Since we can't remove the end entry, we'll remove
2455                          * its predecessor instead. This means we have to
2456                          * transfer the predecessor's sub_vcn to the end entry.
2457                          * Note: This index block is not empty, so the
2458                          * predecessor must exist.
2459                          */
2460                         if (!prev) {
2461                                 err = -EINVAL;
2462                                 goto out;
2463                         }
2464
2465                         if (de_has_vcn(prev)) {
2466                                 de_set_vbn_le(e, de_get_vbn_le(prev));
2467                         } else if (de_has_vcn(e)) {
2468                                 le16_sub_cpu(&e->size, sizeof(u64));
2469                                 e->flags &= ~NTFS_IE_HAS_SUBNODES;
2470                                 le32_sub_cpu(&hdr->used, sizeof(u64));
2471                         }
2472                         e = prev;
2473                 }
2474
2475                 /*
2476                  * Copy the current entry into a temporary buffer (stripping
2477                  * off its down-pointer, if any) and delete it from the current
2478                  * buffer or root, as appropriate.
2479                  */
2480                 e_size = le16_to_cpu(e->size);
2481                 me = kmemdup(e, e_size, GFP_NOFS);
2482                 if (!me) {
2483                         err = -ENOMEM;
2484                         goto out;
2485                 }
2486
2487                 if (de_has_vcn(me)) {
2488                         me->flags &= ~NTFS_IE_HAS_SUBNODES;
2489                         le16_sub_cpu(&me->size, sizeof(u64));
2490                 }
2491
2492                 hdr_delete_de(hdr, e);
2493
2494                 if (hdr == &root->ihdr) {
2495                         level = 0;
2496                         hdr->total = hdr->used;
2497
2498                         /* Shrink resident root attribute. */
2499                         mi_resize_attr(mi, attr, 0 - e_size);
2500                 } else {
2501                         indx_write(indx, ni, n2d, 0);
2502                         level = level2;
2503                 }
2504
2505                 /* Mark unused buffers as free. */
2506                 trim_bit = -1;
2507                 for (; level < fnd->level; level++) {
2508                         ib = fnd->nodes[level]->index;
2509                         if (ib_is_empty(ib)) {
2510                                 size_t k = le64_to_cpu(ib->vbn) >>
2511                                            indx->idx2vbn_bits;
2512
2513                                 indx_mark_free(indx, ni, k);
2514                                 if (k < trim_bit)
2515                                         trim_bit = k;
2516                         }
2517                 }
2518
2519                 fnd_clear(fnd);
2520                 /*fnd->root_de = NULL;*/
2521
2522                 /*
2523                  * Re-insert the entry into the tree.
2524                  * Find the spot the tree where we want to insert the new entry.
2525                  */
2526                 err = indx_insert_entry(indx, ni, me, ctx, fnd, 0);
2527                 kfree(me);
2528                 if (err)
2529                         goto out;
2530
2531                 if (trim_bit != -1)
2532                         indx_shrink(indx, ni, trim_bit);
2533         } else {
2534                 /*
2535                  * This tree needs to be collapsed down to an empty root.
2536                  * Recreate the index root as an empty leaf and free all
2537                  * the bits the index allocation bitmap.
2538                  */
2539                 fnd_clear(fnd);
2540                 fnd_clear(fnd2);
2541
2542                 in = &s_index_names[indx->type];
2543
2544                 err = attr_set_size(ni, ATTR_ALLOC, in->name, in->name_len,
2545                                     &indx->alloc_run, 0, NULL, false, NULL);
2546                 err = ni_remove_attr(ni, ATTR_ALLOC, in->name, in->name_len,
2547                                      false, NULL);
2548                 run_close(&indx->alloc_run);
2549
2550                 err = attr_set_size(ni, ATTR_BITMAP, in->name, in->name_len,
2551                                     &indx->bitmap_run, 0, NULL, false, NULL);
2552                 err = ni_remove_attr(ni, ATTR_BITMAP, in->name, in->name_len,
2553                                      false, NULL);
2554                 run_close(&indx->bitmap_run);
2555
2556                 root = indx_get_root(indx, ni, &attr, &mi);
2557                 if (!root) {
2558                         err = -EINVAL;
2559                         goto out;
2560                 }
2561
2562                 root_size = le32_to_cpu(attr->res.data_size);
2563                 new_root_size =
2564                         sizeof(struct INDEX_ROOT) + sizeof(struct NTFS_DE);
2565
2566                 if (new_root_size != root_size &&
2567                     !mi_resize_attr(mi, attr, new_root_size - root_size)) {
2568                         err = -EINVAL;
2569                         goto out;
2570                 }
2571
2572                 /* Fill first entry. */
2573                 e = (struct NTFS_DE *)(root + 1);
2574                 e->ref.low = 0;
2575                 e->ref.high = 0;
2576                 e->ref.seq = 0;
2577                 e->size = cpu_to_le16(sizeof(struct NTFS_DE));
2578                 e->flags = NTFS_IE_LAST; // 0x02
2579                 e->key_size = 0;
2580                 e->res = 0;
2581
2582                 hdr = &root->ihdr;
2583                 hdr->flags = 0;
2584                 hdr->used = hdr->total = cpu_to_le32(
2585                         new_root_size - offsetof(struct INDEX_ROOT, ihdr));
2586                 mi->dirty = true;
2587         }
2588
2589 out:
2590         fnd_put(fnd2);
2591 out1:
2592         fnd_put(fnd);
2593 out2:
2594         return err;
2595 }
2596
2597 /*
2598  * Update duplicated information in directory entry
2599  * 'dup' - info from MFT record
2600  */
2601 int indx_update_dup(struct ntfs_inode *ni, struct ntfs_sb_info *sbi,
2602                     const struct ATTR_FILE_NAME *fname,
2603                     const struct NTFS_DUP_INFO *dup, int sync)
2604 {
2605         int err, diff;
2606         struct NTFS_DE *e = NULL;
2607         struct ATTR_FILE_NAME *e_fname;
2608         struct ntfs_fnd *fnd;
2609         struct INDEX_ROOT *root;
2610         struct mft_inode *mi;
2611         struct ntfs_index *indx = &ni->dir;
2612
2613         fnd = fnd_get();
2614         if (!fnd)
2615                 return -ENOMEM;
2616
2617         root = indx_get_root(indx, ni, NULL, &mi);
2618         if (!root) {
2619                 err = -EINVAL;
2620                 goto out;
2621         }
2622
2623         /* Find entry in directory. */
2624         err = indx_find(indx, ni, root, fname, fname_full_size(fname), sbi,
2625                         &diff, &e, fnd);
2626         if (err)
2627                 goto out;
2628
2629         if (!e) {
2630                 err = -EINVAL;
2631                 goto out;
2632         }
2633
2634         if (diff) {
2635                 err = -EINVAL;
2636                 goto out;
2637         }
2638
2639         e_fname = (struct ATTR_FILE_NAME *)(e + 1);
2640
2641         if (!memcmp(&e_fname->dup, dup, sizeof(*dup))) {
2642                 /*
2643                  * Nothing to update in index! Try to avoid this call.
2644                  */
2645                 goto out;
2646         }
2647
2648         memcpy(&e_fname->dup, dup, sizeof(*dup));
2649
2650         if (fnd->level) {
2651                 /* Directory entry in index. */
2652                 err = indx_write(indx, ni, fnd->nodes[fnd->level - 1], sync);
2653         } else {
2654                 /* Directory entry in directory MFT record. */
2655                 mi->dirty = true;
2656                 if (sync)
2657                         err = mi_write(mi, 1);
2658                 else
2659                         mark_inode_dirty(&ni->vfs_inode);
2660         }
2661
2662 out:
2663         fnd_put(fnd);
2664         return err;
2665 }