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