fs/ntfs3/index.c

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