fs/ntfs3/attrib.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  *
   4  * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
   5  *
   6  * TODO: Merge attr_set_size/attr_data_get_block/attr_allocate_frame?
   7  */
   8
   9 #include <linux/fs.h>
  10 #include <linux/slab.h>
  11 #include <linux/kernel.h>
  12
  13 #include "debug.h"
  14 #include "ntfs.h"
  15 #include "ntfs_fs.h"
  16
  17 /*
  18  * You can set external NTFS_MIN_LOG2_OF_CLUMP/NTFS_MAX_LOG2_OF_CLUMP to manage
  19  * preallocate algorithm.
  20  */
  21 #ifndef NTFS_MIN_LOG2_OF_CLUMP
  22 #define NTFS_MIN_LOG2_OF_CLUMP 16
  23 #endif
  24
  25 #ifndef NTFS_MAX_LOG2_OF_CLUMP
  26 #define NTFS_MAX_LOG2_OF_CLUMP 26
  27 #endif
  28
  29 // 16M
  30 #define NTFS_CLUMP_MIN (1 << (NTFS_MIN_LOG2_OF_CLUMP + 8))
  31 // 16G
  32 #define NTFS_CLUMP_MAX (1ull << (NTFS_MAX_LOG2_OF_CLUMP + 8))
  33
  34 static inline u64 get_pre_allocated(u64 size)
  35 {
  36         u32 clump;
  37         u8 align_shift;
  38         u64 ret;
  39
  40         if (size <= NTFS_CLUMP_MIN) {
  41                 clump = 1 << NTFS_MIN_LOG2_OF_CLUMP;
  42                 align_shift = NTFS_MIN_LOG2_OF_CLUMP;
  43         } else if (size >= NTFS_CLUMP_MAX) {
  44                 clump = 1 << NTFS_MAX_LOG2_OF_CLUMP;
  45                 align_shift = NTFS_MAX_LOG2_OF_CLUMP;
  46         } else {
  47                 align_shift = NTFS_MIN_LOG2_OF_CLUMP - 1 +
  48                               __ffs(size >> (8 + NTFS_MIN_LOG2_OF_CLUMP));
  49                 clump = 1u << align_shift;
  50         }
  51
  52         ret = (((size + clump - 1) >> align_shift)) << align_shift;
  53
  54         return ret;
  55 }
  56
  57 /*
  58  * attr_load_runs - Load all runs stored in @attr.
  59  */
  60 static int attr_load_runs(struct ATTRIB *attr, struct ntfs_inode *ni,
  61                           struct runs_tree *run, const CLST *vcn)
  62 {
  63         int err;
  64         CLST svcn = le64_to_cpu(attr->nres.svcn);
  65         CLST evcn = le64_to_cpu(attr->nres.evcn);
  66         u32 asize;
  67         u16 run_off;
  68
  69         if (svcn >= evcn + 1 || run_is_mapped_full(run, svcn, evcn))
  70                 return 0;
  71
  72         if (vcn && (evcn < *vcn || *vcn < svcn))
  73                 return -EINVAL;
  74
  75         asize = le32_to_cpu(attr->size);
  76         run_off = le16_to_cpu(attr->nres.run_off);
  77
  78         if (run_off > asize)
  79                 return -EINVAL;
  80
  81         err = run_unpack_ex(run, ni->mi.sbi, ni->mi.rno, svcn, evcn,
  82                             vcn ? *vcn : svcn, Add2Ptr(attr, run_off),
  83                             asize - run_off);
  84         if (err < 0)
  85                 return err;
  86
  87         return 0;
  88 }
  89
  90 /*
  91  * run_deallocate_ex - Deallocate clusters.
  92  */
  93 static int run_deallocate_ex(struct ntfs_sb_info *sbi, struct runs_tree *run,
  94                              CLST vcn, CLST len, CLST *done, bool trim)
  95 {
  96         int err = 0;
  97         CLST vcn_next, vcn0 = vcn, lcn, clen, dn = 0;
  98         size_t idx;
  99
 100         if (!len)
 101                 goto out;
 102
 103         if (!run_lookup_entry(run, vcn, &lcn, &clen, &idx)) {
 104 failed:
 105                 run_truncate(run, vcn0);
 106                 err = -EINVAL;
 107                 goto out;
 108         }
 109
 110         for (;;) {
 111                 if (clen > len)
 112                         clen = len;
 113
 114                 if (!clen) {
 115                         err = -EINVAL;
 116                         goto out;
 117                 }
 118
 119                 if (lcn != SPARSE_LCN) {
 120                         if (sbi) {
 121                                 /* mark bitmap range [lcn + clen) as free and trim clusters. */
 122                                 mark_as_free_ex(sbi, lcn, clen, trim);
 123                         }
 124                         dn += clen;
 125                 }
 126
 127                 len -= clen;
 128                 if (!len)
 129                         break;
 130
 131                 vcn_next = vcn + clen;
 132                 if (!run_get_entry(run, ++idx, &vcn, &lcn, &clen) ||
 133                     vcn != vcn_next) {
 134                         /* Save memory - don't load entire run. */
 135                         goto failed;
 136                 }
 137         }
 138
 139 out:
 140         if (done)
 141                 *done += dn;
 142
 143         return err;
 144 }
 145
 146 /*
 147  * attr_allocate_clusters - Find free space, mark it as used and store in @run.
 148  */
 149 int attr_allocate_clusters(struct ntfs_sb_info *sbi, struct runs_tree *run,
 150                            CLST vcn, CLST lcn, CLST len, CLST *pre_alloc,
 151                            enum ALLOCATE_OPT opt, CLST *alen, const size_t fr,
 152                            CLST *new_lcn, CLST *new_len)
 153 {
 154         int err;
 155         CLST flen, vcn0 = vcn, pre = pre_alloc ? *pre_alloc : 0;
 156         size_t cnt = run->count;
 157
 158         for (;;) {
 159                 err = ntfs_look_for_free_space(sbi, lcn, len + pre, &lcn, &flen,
 160                                                opt);
 161
 162                 if (err == -ENOSPC && pre) {
 163                         pre = 0;
 164                         if (*pre_alloc)
 165                                 *pre_alloc = 0;
 166                         continue;
 167                 }
 168
 169                 if (err)
 170                         goto out;
 171
 172                 if (vcn == vcn0) {
 173                         /* Return the first fragment. */
 174                         if (new_lcn)
 175                                 *new_lcn = lcn;
 176                         if (new_len)
 177                                 *new_len = flen;
 178                 }
 179
 180                 /* Add new fragment into run storage. */
 181                 if (!run_add_entry(run, vcn, lcn, flen, opt & ALLOCATE_MFT)) {
 182                         /* Undo last 'ntfs_look_for_free_space' */
 183                         mark_as_free_ex(sbi, lcn, len, false);
 184                         err = -ENOMEM;
 185                         goto out;
 186                 }
 187
 188                 if (opt & ALLOCATE_ZERO) {
 189                         u8 shift = sbi->cluster_bits - SECTOR_SHIFT;
 190
 191                         err = blkdev_issue_zeroout(sbi->sb->s_bdev,
 192                                                    (sector_t)lcn << shift,
 193                                                    (sector_t)flen << shift,
 194                                                    GFP_NOFS, 0);
 195                         if (err)
 196                                 goto out;
 197                 }
 198
 199                 vcn += flen;
 200
 201                 if (flen >= len || (opt & ALLOCATE_MFT) ||
 202                     (fr && run->count - cnt >= fr)) {
 203                         *alen = vcn - vcn0;
 204                         return 0;
 205                 }
 206
 207                 len -= flen;
 208         }
 209
 210 out:
 211         /* Undo 'ntfs_look_for_free_space' */
 212         if (vcn - vcn0) {
 213                 run_deallocate_ex(sbi, run, vcn0, vcn - vcn0, NULL, false);
 214                 run_truncate(run, vcn0);
 215         }
 216
 217         return err;
 218 }
 219
 220 /*
 221  * attr_make_nonresident
 222  *
 223  * If page is not NULL - it is already contains resident data
 224  * and locked (called from ni_write_frame()).
 225  */
 226 int attr_make_nonresident(struct ntfs_inode *ni, struct ATTRIB *attr,
 227                           struct ATTR_LIST_ENTRY *le, struct mft_inode *mi,
 228                           u64 new_size, struct runs_tree *run,
 229                           struct ATTRIB **ins_attr, struct page *page)
 230 {
 231         struct ntfs_sb_info *sbi;
 232         struct ATTRIB *attr_s;
 233         struct MFT_REC *rec;
 234         u32 used, asize, rsize, aoff, align;
 235         bool is_data;
 236         CLST len, alen;
 237         char *next;
 238         int err;
 239
 240         if (attr->non_res) {
 241                 *ins_attr = attr;
 242                 return 0;
 243         }
 244
 245         sbi = mi->sbi;
 246         rec = mi->mrec;
 247         attr_s = NULL;
 248         used = le32_to_cpu(rec->used);
 249         asize = le32_to_cpu(attr->size);
 250         next = Add2Ptr(attr, asize);
 251         aoff = PtrOffset(rec, attr);
 252         rsize = le32_to_cpu(attr->res.data_size);
 253         is_data = attr->type == ATTR_DATA && !attr->name_len;
 254
 255         align = sbi->cluster_size;
 256         if (is_attr_compressed(attr))
 257                 align <<= COMPRESSION_UNIT;
 258         len = (rsize + align - 1) >> sbi->cluster_bits;
 259
 260         run_init(run);
 261
 262         /* Make a copy of original attribute. */
 263         attr_s = kmemdup(attr, asize, GFP_NOFS);
 264         if (!attr_s) {
 265                 err = -ENOMEM;
 266                 goto out;
 267         }
 268
 269         if (!len) {
 270                 /* Empty resident -> Empty nonresident. */
 271                 alen = 0;
 272         } else {
 273                 const char *data = resident_data(attr);
 274
 275                 err = attr_allocate_clusters(sbi, run, 0, 0, len, NULL,
 276                                              ALLOCATE_DEF, &alen, 0, NULL,
 277                                              NULL);
 278                 if (err)
 279                         goto out1;
 280
 281                 if (!rsize) {
 282                         /* Empty resident -> Non empty nonresident. */
 283                 } else if (!is_data) {
 284                         err = ntfs_sb_write_run(sbi, run, 0, data, rsize, 0);
 285                         if (err)
 286                                 goto out2;
 287                 } else if (!page) {
 288                         char *kaddr;
 289
 290                         page = grab_cache_page(ni->vfs_inode.i_mapping, 0);
 291                         if (!page) {
 292                                 err = -ENOMEM;
 293                                 goto out2;
 294                         }
 295                         kaddr = kmap_atomic(page);
 296                         memcpy(kaddr, data, rsize);
 297                         memset(kaddr + rsize, 0, PAGE_SIZE - rsize);
 298                         kunmap_atomic(kaddr);
 299                         flush_dcache_page(page);
 300                         SetPageUptodate(page);
 301                         set_page_dirty(page);
 302                         unlock_page(page);
 303                         put_page(page);
 304                 }
 305         }
 306
 307         /* Remove original attribute. */
 308         used -= asize;
 309         memmove(attr, Add2Ptr(attr, asize), used - aoff);
 310         rec->used = cpu_to_le32(used);
 311         mi->dirty = true;
 312         if (le)
 313                 al_remove_le(ni, le);
 314
 315         err = ni_insert_nonresident(ni, attr_s->type, attr_name(attr_s),
 316                                     attr_s->name_len, run, 0, alen,
 317                                     attr_s->flags, &attr, NULL, NULL);
 318         if (err)
 319                 goto out3;
 320
 321         kfree(attr_s);
 322         attr->nres.data_size = cpu_to_le64(rsize);
 323         attr->nres.valid_size = attr->nres.data_size;
 324
 325         *ins_attr = attr;
 326
 327         if (is_data)
 328                 ni->ni_flags &= ~NI_FLAG_RESIDENT;
 329
 330         /* Resident attribute becomes non resident. */
 331         return 0;
 332
 333 out3:
 334         attr = Add2Ptr(rec, aoff);
 335         memmove(next, attr, used - aoff);
 336         memcpy(attr, attr_s, asize);
 337         rec->used = cpu_to_le32(used + asize);
 338         mi->dirty = true;
 339 out2:
 340         /* Undo: do not trim new allocated clusters. */
 341         run_deallocate(sbi, run, false);
 342         run_close(run);
 343 out1:
 344         kfree(attr_s);
 345 out:
 346         return err;
 347 }
 348
 349 /*
 350  * attr_set_size_res - Helper for attr_set_size().
 351  */
 352 static int attr_set_size_res(struct ntfs_inode *ni, struct ATTRIB *attr,
 353                              struct ATTR_LIST_ENTRY *le, struct mft_inode *mi,
 354                              u64 new_size, struct runs_tree *run,
 355                              struct ATTRIB **ins_attr)
 356 {
 357         struct ntfs_sb_info *sbi = mi->sbi;
 358         struct MFT_REC *rec = mi->mrec;
 359         u32 used = le32_to_cpu(rec->used);
 360         u32 asize = le32_to_cpu(attr->size);
 361         u32 aoff = PtrOffset(rec, attr);
 362         u32 rsize = le32_to_cpu(attr->res.data_size);
 363         u32 tail = used - aoff - asize;
 364         char *next = Add2Ptr(attr, asize);
 365         s64 dsize = ALIGN(new_size, 8) - ALIGN(rsize, 8);
 366
 367         if (dsize < 0) {
 368                 memmove(next + dsize, next, tail);
 369         } else if (dsize > 0) {
 370                 if (used + dsize > sbi->max_bytes_per_attr)
 371                         return attr_make_nonresident(ni, attr, le, mi, new_size,
 372                                                      run, ins_attr, NULL);
 373
 374                 memmove(next + dsize, next, tail);
 375                 memset(next, 0, dsize);
 376         }
 377
 378         if (new_size > rsize)
 379                 memset(Add2Ptr(resident_data(attr), rsize), 0,
 380                        new_size - rsize);
 381
 382         rec->used = cpu_to_le32(used + dsize);
 383         attr->size = cpu_to_le32(asize + dsize);
 384         attr->res.data_size = cpu_to_le32(new_size);
 385         mi->dirty = true;
 386         *ins_attr = attr;
 387
 388         return 0;
 389 }
 390
 391 /*
 392  * attr_set_size - Change the size of attribute.
 393  *
 394  * Extend:
 395  *   - Sparse/compressed: No allocated clusters.
 396  *   - Normal: Append allocated and preallocated new clusters.
 397  * Shrink:
 398  *   - No deallocate if @keep_prealloc is set.
 399  */
 400 int attr_set_size(struct ntfs_inode *ni, enum ATTR_TYPE type,
 401                   const __le16 *name, u8 name_len, struct runs_tree *run,
 402                   u64 new_size, const u64 *new_valid, bool keep_prealloc,
 403                   struct ATTRIB **ret)
 404 {
 405         int err = 0;
 406         struct ntfs_sb_info *sbi = ni->mi.sbi;
 407         u8 cluster_bits = sbi->cluster_bits;
 408         bool is_mft =
 409                 ni->mi.rno == MFT_REC_MFT && type == ATTR_DATA && !name_len;
 410         u64 old_valid, old_size, old_alloc, new_alloc, new_alloc_tmp;
 411         struct ATTRIB *attr = NULL, *attr_b;
 412         struct ATTR_LIST_ENTRY *le, *le_b;
 413         struct mft_inode *mi, *mi_b;
 414         CLST alen, vcn, lcn, new_alen, old_alen, svcn, evcn;
 415         CLST next_svcn, pre_alloc = -1, done = 0;
 416         bool is_ext, is_bad = false;
 417         u32 align;
 418         struct MFT_REC *rec;
 419
 420 again:
 421         alen = 0;
 422         le_b = NULL;
 423         attr_b = ni_find_attr(ni, NULL, &le_b, type, name, name_len, NULL,
 424                               &mi_b);
 425         if (!attr_b) {
 426                 err = -ENOENT;
 427                 goto bad_inode;
 428         }
 429
 430         if (!attr_b->non_res) {
 431                 err = attr_set_size_res(ni, attr_b, le_b, mi_b, new_size, run,
 432                                         &attr_b);
 433                 if (err)
 434                         return err;
 435
 436                 /* Return if file is still resident. */
 437                 if (!attr_b->non_res)
 438                         goto ok1;
 439
 440                 /* Layout of records may be changed, so do a full search. */
 441                 goto again;
 442         }
 443
 444         is_ext = is_attr_ext(attr_b);
 445         align = sbi->cluster_size;
 446         if (is_ext)
 447                 align <<= attr_b->nres.c_unit;
 448
 449         old_valid = le64_to_cpu(attr_b->nres.valid_size);
 450         old_size = le64_to_cpu(attr_b->nres.data_size);
 451         old_alloc = le64_to_cpu(attr_b->nres.alloc_size);
 452
 453 again_1:
 454         old_alen = old_alloc >> cluster_bits;
 455
 456         new_alloc = (new_size + align - 1) & ~(u64)(align - 1);
 457         new_alen = new_alloc >> cluster_bits;
 458
 459         if (keep_prealloc && new_size < old_size) {
 460                 attr_b->nres.data_size = cpu_to_le64(new_size);
 461                 mi_b->dirty = true;
 462                 goto ok;
 463         }
 464
 465         vcn = old_alen - 1;
 466
 467         svcn = le64_to_cpu(attr_b->nres.svcn);
 468         evcn = le64_to_cpu(attr_b->nres.evcn);
 469
 470         if (svcn <= vcn && vcn <= evcn) {
 471                 attr = attr_b;
 472                 le = le_b;
 473                 mi = mi_b;
 474         } else if (!le_b) {
 475                 err = -EINVAL;
 476                 goto bad_inode;
 477         } else {
 478                 le = le_b;
 479                 attr = ni_find_attr(ni, attr_b, &le, type, name, name_len, &vcn,
 480                                     &mi);
 481                 if (!attr) {
 482                         err = -EINVAL;
 483                         goto bad_inode;
 484                 }
 485
 486 next_le_1:
 487                 svcn = le64_to_cpu(attr->nres.svcn);
 488                 evcn = le64_to_cpu(attr->nres.evcn);
 489         }
 490         /*
 491          * Here we have:
 492          * attr,mi,le - last attribute segment (containing 'vcn').
 493          * attr_b,mi_b,le_b - base (primary) attribute segment.
 494          */
 495 next_le:
 496         rec = mi->mrec;
 497         err = attr_load_runs(attr, ni, run, NULL);
 498         if (err)
 499                 goto out;
 500
 501         if (new_size > old_size) {
 502                 CLST to_allocate;
 503                 size_t free;
 504
 505                 if (new_alloc <= old_alloc) {
 506                         attr_b->nres.data_size = cpu_to_le64(new_size);
 507                         mi_b->dirty = true;
 508                         goto ok;
 509                 }
 510
 511                 /*
 512                  * Add clusters. In simple case we have to:
 513                  *  - allocate space (vcn, lcn, len)
 514                  *  - update packed run in 'mi'
 515                  *  - update attr->nres.evcn
 516                  *  - update attr_b->nres.data_size/attr_b->nres.alloc_size
 517                  */
 518                 to_allocate = new_alen - old_alen;
 519 add_alloc_in_same_attr_seg:
 520                 lcn = 0;
 521                 if (is_mft) {
 522                         /* MFT allocates clusters from MFT zone. */
 523                         pre_alloc = 0;
 524                 } else if (is_ext) {
 525                         /* No preallocate for sparse/compress. */
 526                         pre_alloc = 0;
 527                 } else if (pre_alloc == -1) {
 528                         pre_alloc = 0;
 529                         if (type == ATTR_DATA && !name_len &&
 530                             sbi->options->prealloc) {
 531                                 pre_alloc =
 532                                         bytes_to_cluster(
 533                                                 sbi,
 534                                                 get_pre_allocated(new_size)) -
 535                                         new_alen;
 536                         }
 537
 538                         /* Get the last LCN to allocate from. */
 539                         if (old_alen &&
 540                             !run_lookup_entry(run, vcn, &lcn, NULL, NULL)) {
 541                                 lcn = SPARSE_LCN;
 542                         }
 543
 544                         if (lcn == SPARSE_LCN)
 545                                 lcn = 0;
 546                         else if (lcn)
 547                                 lcn += 1;
 548
 549                         free = wnd_zeroes(&sbi->used.bitmap);
 550                         if (to_allocate > free) {
 551                                 err = -ENOSPC;
 552                                 goto out;
 553                         }
 554
 555                         if (pre_alloc && to_allocate + pre_alloc > free)
 556                                 pre_alloc = 0;
 557                 }
 558
 559                 vcn = old_alen;
 560
 561                 if (is_ext) {
 562                         if (!run_add_entry(run, vcn, SPARSE_LCN, to_allocate,
 563                                            false)) {
 564                                 err = -ENOMEM;
 565                                 goto out;
 566                         }
 567                         alen = to_allocate;
 568                 } else {
 569                         /* ~3 bytes per fragment. */
 570                         err = attr_allocate_clusters(
 571                                 sbi, run, vcn, lcn, to_allocate, &pre_alloc,
 572                                 is_mft ? ALLOCATE_MFT : ALLOCATE_DEF, &alen,
 573                                 is_mft ? 0
 574                                        : (sbi->record_size -
 575                                           le32_to_cpu(rec->used) + 8) /
 576                                                          3 +
 577                                                  1,
 578                                 NULL, NULL);
 579                         if (err)
 580                                 goto out;
 581                 }
 582
 583                 done += alen;
 584                 vcn += alen;
 585                 if (to_allocate > alen)
 586                         to_allocate -= alen;
 587                 else
 588                         to_allocate = 0;
 589
 590 pack_runs:
 591                 err = mi_pack_runs(mi, attr, run, vcn - svcn);
 592                 if (err)
 593                         goto undo_1;
 594
 595                 next_svcn = le64_to_cpu(attr->nres.evcn) + 1;
 596                 new_alloc_tmp = (u64)next_svcn << cluster_bits;
 597                 attr_b->nres.alloc_size = cpu_to_le64(new_alloc_tmp);
 598                 mi_b->dirty = true;
 599
 600                 if (next_svcn >= vcn && !to_allocate) {
 601                         /* Normal way. Update attribute and exit. */
 602                         attr_b->nres.data_size = cpu_to_le64(new_size);
 603                         goto ok;
 604                 }
 605
 606                 /* At least two MFT to avoid recursive loop. */
 607                 if (is_mft && next_svcn == vcn &&
 608                     ((u64)done << sbi->cluster_bits) >= 2 * sbi->record_size) {
 609                         new_size = new_alloc_tmp;
 610                         attr_b->nres.data_size = attr_b->nres.alloc_size;
 611                         goto ok;
 612                 }
 613
 614                 if (le32_to_cpu(rec->used) < sbi->record_size) {
 615                         old_alen = next_svcn;
 616                         evcn = old_alen - 1;
 617                         goto add_alloc_in_same_attr_seg;
 618                 }
 619
 620                 attr_b->nres.data_size = attr_b->nres.alloc_size;
 621                 if (new_alloc_tmp < old_valid)
 622                         attr_b->nres.valid_size = attr_b->nres.data_size;
 623
 624                 if (type == ATTR_LIST) {
 625                         err = ni_expand_list(ni);
 626                         if (err)
 627                                 goto undo_2;
 628                         if (next_svcn < vcn)
 629                                 goto pack_runs;
 630
 631                         /* Layout of records is changed. */
 632                         goto again;
 633                 }
 634
 635                 if (!ni->attr_list.size) {
 636                         err = ni_create_attr_list(ni);
 637                         /* In case of error layout of records is not changed. */
 638                         if (err)
 639                                 goto undo_2;
 640                         /* Layout of records is changed. */
 641                 }
 642
 643                 if (next_svcn >= vcn) {
 644                         /* This is MFT data, repeat. */
 645                         goto again;
 646                 }
 647
 648                 /* Insert new attribute segment. */
 649                 err = ni_insert_nonresident(ni, type, name, name_len, run,
 650                                             next_svcn, vcn - next_svcn,
 651                                             attr_b->flags, &attr, &mi, NULL);
 652
 653                 /*
 654                  * Layout of records maybe changed.
 655                  * Find base attribute to update.
 656                  */
 657                 le_b = NULL;
 658                 attr_b = ni_find_attr(ni, NULL, &le_b, type, name, name_len,
 659                                       NULL, &mi_b);
 660                 if (!attr_b) {
 661                         err = -EINVAL;
 662                         goto bad_inode;
 663                 }
 664
 665                 if (err) {
 666                         /* ni_insert_nonresident failed. */
 667                         attr = NULL;
 668                         goto undo_2;
 669                 }
 670
 671                 if (!is_mft)
 672                         run_truncate_head(run, evcn + 1);
 673
 674                 svcn = le64_to_cpu(attr->nres.svcn);
 675                 evcn = le64_to_cpu(attr->nres.evcn);
 676
 677                 /*
 678                  * Attribute is in consistency state.
 679                  * Save this point to restore to if next steps fail.
 680                  */
 681                 old_valid = old_size = old_alloc = (u64)vcn << cluster_bits;
 682                 attr_b->nres.valid_size = attr_b->nres.data_size =
 683                         attr_b->nres.alloc_size = cpu_to_le64(old_size);
 684                 mi_b->dirty = true;
 685                 goto again_1;
 686         }
 687
 688         if (new_size != old_size ||
 689             (new_alloc != old_alloc && !keep_prealloc)) {
 690                 /*
 691                  * Truncate clusters. In simple case we have to:
 692                  *  - update packed run in 'mi'
 693                  *  - update attr->nres.evcn
 694                  *  - update attr_b->nres.data_size/attr_b->nres.alloc_size
 695                  *  - mark and trim clusters as free (vcn, lcn, len)
 696                  */
 697                 CLST dlen = 0;
 698
 699                 vcn = max(svcn, new_alen);
 700                 new_alloc_tmp = (u64)vcn << cluster_bits;
 701
 702                 if (vcn > svcn) {
 703                         err = mi_pack_runs(mi, attr, run, vcn - svcn);
 704                         if (err)
 705                                 goto out;
 706                 } else if (le && le->vcn) {
 707                         u16 le_sz = le16_to_cpu(le->size);
 708
 709                         /*
 710                          * NOTE: List entries for one attribute are always
 711                          * the same size. We deal with last entry (vcn==0)
 712                          * and it is not first in entries array
 713                          * (list entry for std attribute always first).
 714                          * So it is safe to step back.
 715                          */
 716                         mi_remove_attr(NULL, mi, attr);
 717
 718                         if (!al_remove_le(ni, le)) {
 719                                 err = -EINVAL;
 720                                 goto bad_inode;
 721                         }
 722
 723                         le = (struct ATTR_LIST_ENTRY *)((u8 *)le - le_sz);
 724                 } else {
 725                         attr->nres.evcn = cpu_to_le64((u64)vcn - 1);
 726                         mi->dirty = true;
 727                 }
 728
 729                 attr_b->nres.alloc_size = cpu_to_le64(new_alloc_tmp);
 730
 731                 if (vcn == new_alen) {
 732                         attr_b->nres.data_size = cpu_to_le64(new_size);
 733                         if (new_size < old_valid)
 734                                 attr_b->nres.valid_size =
 735                                         attr_b->nres.data_size;
 736                 } else {
 737                         if (new_alloc_tmp <=
 738                             le64_to_cpu(attr_b->nres.data_size))
 739                                 attr_b->nres.data_size =
 740                                         attr_b->nres.alloc_size;
 741                         if (new_alloc_tmp <
 742                             le64_to_cpu(attr_b->nres.valid_size))
 743                                 attr_b->nres.valid_size =
 744                                         attr_b->nres.alloc_size;
 745                 }
 746                 mi_b->dirty = true;
 747
 748                 err = run_deallocate_ex(sbi, run, vcn, evcn - vcn + 1, &dlen,
 749                                         true);
 750                 if (err)
 751                         goto out;
 752
 753                 if (is_ext) {
 754                         /* dlen - really deallocated clusters. */
 755                         le64_sub_cpu(&attr_b->nres.total_size,
 756                                      ((u64)dlen << cluster_bits));
 757                 }
 758
 759                 run_truncate(run, vcn);
 760
 761                 if (new_alloc_tmp <= new_alloc)
 762                         goto ok;
 763
 764                 old_size = new_alloc_tmp;
 765                 vcn = svcn - 1;
 766
 767                 if (le == le_b) {
 768                         attr = attr_b;
 769                         mi = mi_b;
 770                         evcn = svcn - 1;
 771                         svcn = 0;
 772                         goto next_le;
 773                 }
 774
 775                 if (le->type != type || le->name_len != name_len ||
 776                     memcmp(le_name(le), name, name_len * sizeof(short))) {
 777                         err = -EINVAL;
 778                         goto bad_inode;
 779                 }
 780
 781                 err = ni_load_mi(ni, le, &mi);
 782                 if (err)
 783                         goto out;
 784
 785                 attr = mi_find_attr(mi, NULL, type, name, name_len, &le->id);
 786                 if (!attr) {
 787                         err = -EINVAL;
 788                         goto bad_inode;
 789                 }
 790                 goto next_le_1;
 791         }
 792
 793 ok:
 794         if (new_valid) {
 795                 __le64 valid = cpu_to_le64(min(*new_valid, new_size));
 796
 797                 if (attr_b->nres.valid_size != valid) {
 798                         attr_b->nres.valid_size = valid;
 799                         mi_b->dirty = true;
 800                 }
 801         }
 802
 803 ok1:
 804         if (ret)
 805                 *ret = attr_b;
 806
 807         /* Update inode_set_bytes. */
 808         if (((type == ATTR_DATA && !name_len) ||
 809              (type == ATTR_ALLOC && name == I30_NAME))) {
 810                 bool dirty = false;
 811
 812                 if (ni->vfs_inode.i_size != new_size) {
 813                         ni->vfs_inode.i_size = new_size;
 814                         dirty = true;
 815                 }
 816
 817                 if (attr_b->non_res) {
 818                         new_alloc = le64_to_cpu(attr_b->nres.alloc_size);
 819                         if (inode_get_bytes(&ni->vfs_inode) != new_alloc) {
 820                                 inode_set_bytes(&ni->vfs_inode, new_alloc);
 821                                 dirty = true;
 822                         }
 823                 }
 824
 825                 if (dirty) {
 826                         ni->ni_flags |= NI_FLAG_UPDATE_PARENT;
 827                         mark_inode_dirty(&ni->vfs_inode);
 828                 }
 829         }
 830
 831         return 0;
 832
 833 undo_2:
 834         vcn -= alen;
 835         attr_b->nres.data_size = cpu_to_le64(old_size);
 836         attr_b->nres.valid_size = cpu_to_le64(old_valid);
 837         attr_b->nres.alloc_size = cpu_to_le64(old_alloc);
 838
 839         /* Restore 'attr' and 'mi'. */
 840         if (attr)
 841                 goto restore_run;
 842
 843         if (le64_to_cpu(attr_b->nres.svcn) <= svcn &&
 844             svcn <= le64_to_cpu(attr_b->nres.evcn)) {
 845                 attr = attr_b;
 846                 le = le_b;
 847                 mi = mi_b;
 848         } else if (!le_b) {
 849                 err = -EINVAL;
 850                 goto bad_inode;
 851         } else {
 852                 le = le_b;
 853                 attr = ni_find_attr(ni, attr_b, &le, type, name, name_len,
 854                                     &svcn, &mi);
 855                 if (!attr)
 856                         goto bad_inode;
 857         }
 858
 859 restore_run:
 860         if (mi_pack_runs(mi, attr, run, evcn - svcn + 1))
 861                 is_bad = true;
 862
 863 undo_1:
 864         run_deallocate_ex(sbi, run, vcn, alen, NULL, false);
 865
 866         run_truncate(run, vcn);
 867 out:
 868         if (is_bad) {
 869 bad_inode:
 870                 _ntfs_bad_inode(&ni->vfs_inode);
 871         }
 872         return err;
 873 }
 874
 875 /*
 876  * attr_data_get_block - Returns 'lcn' and 'len' for given 'vcn'.
 877  *
 878  * @new == NULL means just to get current mapping for 'vcn'
 879  * @new != NULL means allocate real cluster if 'vcn' maps to hole
 880  * @zero - zeroout new allocated clusters
 881  *
 882  *  NOTE:
 883  *  - @new != NULL is called only for sparsed or compressed attributes.
 884  *  - new allocated clusters are zeroed via blkdev_issue_zeroout.
 885  */
 886 int attr_data_get_block(struct ntfs_inode *ni, CLST vcn, CLST clen, CLST *lcn,
 887                         CLST *len, bool *new, bool zero)
 888 {
 889         int err = 0;
 890         struct runs_tree *run = &ni->file.run;
 891         struct ntfs_sb_info *sbi;
 892         u8 cluster_bits;
 893         struct ATTRIB *attr = NULL, *attr_b;
 894         struct ATTR_LIST_ENTRY *le, *le_b;
 895         struct mft_inode *mi, *mi_b;
 896         CLST hint, svcn, to_alloc, evcn1, next_svcn, asize, end, vcn0, alen;
 897         unsigned fr;
 898         u64 total_size;
 899
 900         if (new)
 901                 *new = false;
 902
 903         /* Try to find in cache. */
 904         down_read(&ni->file.run_lock);
 905         if (!run_lookup_entry(run, vcn, lcn, len, NULL))
 906                 *len = 0;
 907         up_read(&ni->file.run_lock);
 908
 909         if (*len) {
 910                 if (*lcn != SPARSE_LCN || !new)
 911                         return 0; /* Fast normal way without allocation. */
 912                 else if (clen > *len)
 913                         clen = *len;
 914         }
 915
 916         /* No cluster in cache or we need to allocate cluster in hole. */
 917         sbi = ni->mi.sbi;
 918         cluster_bits = sbi->cluster_bits;
 919
 920         ni_lock(ni);
 921         down_write(&ni->file.run_lock);
 922
 923         le_b = NULL;
 924         attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL, 0, NULL, &mi_b);
 925         if (!attr_b) {
 926                 err = -ENOENT;
 927                 goto out;
 928         }
 929
 930         if (!attr_b->non_res) {
 931                 *lcn = RESIDENT_LCN;
 932                 *len = 1;
 933                 goto out;
 934         }
 935
 936         asize = le64_to_cpu(attr_b->nres.alloc_size) >> cluster_bits;
 937         if (vcn >= asize) {
 938                 err = -EINVAL;
 939                 goto out;
 940         }
 941
 942         svcn = le64_to_cpu(attr_b->nres.svcn);
 943         evcn1 = le64_to_cpu(attr_b->nres.evcn) + 1;
 944
 945         attr = attr_b;
 946         le = le_b;
 947         mi = mi_b;
 948
 949         if (le_b && (vcn < svcn || evcn1 <= vcn)) {
 950                 attr = ni_find_attr(ni, attr_b, &le, ATTR_DATA, NULL, 0, &vcn,
 951                                     &mi);
 952                 if (!attr) {
 953                         err = -EINVAL;
 954                         goto out;
 955                 }
 956                 svcn = le64_to_cpu(attr->nres.svcn);
 957                 evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
 958         }
 959
 960         /* Load in cache actual information. */
 961         err = attr_load_runs(attr, ni, run, NULL);
 962         if (err)
 963                 goto out;
 964
 965         if (!*len) {
 966                 if (run_lookup_entry(run, vcn, lcn, len, NULL)) {
 967                         if (*lcn != SPARSE_LCN || !new)
 968                                 goto ok; /* Slow normal way without allocation. */
 969
 970                         if (clen > *len)
 971                                 clen = *len;
 972                 } else if (!new) {
 973                         /* Here we may return -ENOENT.
 974                          * In any case caller gets zero length. */
 975                         goto ok;
 976                 }
 977         }
 978
 979         if (!is_attr_ext(attr_b)) {
 980                 /* The code below only for sparsed or compressed attributes. */
 981                 err = -EINVAL;
 982                 goto out;
 983         }
 984
 985         vcn0 = vcn;
 986         to_alloc = clen;
 987         fr = (sbi->record_size - le32_to_cpu(mi->mrec->used) + 8) / 3 + 1;
 988         /* Allocate frame aligned clusters.
 989          * ntfs.sys usually uses 16 clusters per frame for sparsed or compressed.
 990          * ntfs3 uses 1 cluster per frame for new created sparsed files. */
 991         if (attr_b->nres.c_unit) {
 992                 CLST clst_per_frame = 1u << attr_b->nres.c_unit;
 993                 CLST cmask = ~(clst_per_frame - 1);
 994
 995                 /* Get frame aligned vcn and to_alloc. */
 996                 vcn = vcn0 & cmask;
 997                 to_alloc = ((vcn0 + clen + clst_per_frame - 1) & cmask) - vcn;
 998                 if (fr < clst_per_frame)
 999                         fr = clst_per_frame;
1000                 zero = true;
1001
1002                 /* Check if 'vcn' and 'vcn0' in different attribute segments. */
1003                 if (vcn < svcn || evcn1 <= vcn) {
1004                         /* Load attribute for truncated vcn. */
1005                         attr = ni_find_attr(ni, attr_b, &le, ATTR_DATA, NULL, 0,
1006                                             &vcn, &mi);
1007                         if (!attr) {
1008                                 err = -EINVAL;
1009                                 goto out;
1010                         }
1011                         svcn = le64_to_cpu(attr->nres.svcn);
1012                         evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
1013                         err = attr_load_runs(attr, ni, run, NULL);
1014                         if (err)
1015                                 goto out;
1016                 }
1017         }
1018
1019         if (vcn + to_alloc > asize)
1020                 to_alloc = asize - vcn;
1021
1022         /* Get the last LCN to allocate from. */
1023         hint = 0;
1024
1025         if (vcn > evcn1) {
1026                 if (!run_add_entry(run, evcn1, SPARSE_LCN, vcn - evcn1,
1027                                    false)) {
1028                         err = -ENOMEM;
1029                         goto out;
1030                 }
1031         } else if (vcn && !run_lookup_entry(run, vcn - 1, &hint, NULL, NULL)) {
1032                 hint = -1;
1033         }
1034
1035         /* Allocate and zeroout new clusters. */
1036         err = attr_allocate_clusters(sbi, run, vcn, hint + 1, to_alloc, NULL,
1037                                      zero ? ALLOCATE_ZERO : ALLOCATE_DEF, &alen,
1038                                      fr, lcn, len);
1039         if (err)
1040                 goto out;
1041         *new = true;
1042
1043         end = vcn + alen;
1044         total_size = le64_to_cpu(attr_b->nres.total_size) +
1045                      ((u64)alen << cluster_bits);
1046
1047         if (vcn != vcn0) {
1048                 if (!run_lookup_entry(run, vcn0, lcn, len, NULL)) {
1049                         err = -EINVAL;
1050                         goto out;
1051                 }
1052                 if (*lcn == SPARSE_LCN) {
1053                         /* Internal error. Should not happened. */
1054                         WARN_ON(1);
1055                         err = -EINVAL;
1056                         goto out;
1057                 }
1058                 /* Check case when vcn0 + len overlaps new allocated clusters. */
1059                 if (vcn0 + *len > end)
1060                         *len = end - vcn0;
1061         }
1062
1063 repack:
1064         err = mi_pack_runs(mi, attr, run, max(end, evcn1) - svcn);
1065         if (err)
1066                 goto out;
1067
1068         attr_b->nres.total_size = cpu_to_le64(total_size);
1069         inode_set_bytes(&ni->vfs_inode, total_size);
1070         ni->ni_flags |= NI_FLAG_UPDATE_PARENT;
1071
1072         mi_b->dirty = true;
1073         mark_inode_dirty(&ni->vfs_inode);
1074
1075         /* Stored [vcn : next_svcn) from [vcn : end). */
1076         next_svcn = le64_to_cpu(attr->nres.evcn) + 1;
1077
1078         if (end <= evcn1) {
1079                 if (next_svcn == evcn1) {
1080                         /* Normal way. Update attribute and exit. */
1081                         goto ok;
1082                 }
1083                 /* Add new segment [next_svcn : evcn1 - next_svcn). */
1084                 if (!ni->attr_list.size) {
1085                         err = ni_create_attr_list(ni);
1086                         if (err)
1087                                 goto out;
1088                         /* Layout of records is changed. */
1089                         le_b = NULL;
1090                         attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL,
1091                                               0, NULL, &mi_b);
1092                         if (!attr_b) {
1093                                 err = -ENOENT;
1094                                 goto out;
1095                         }
1096
1097                         attr = attr_b;
1098                         le = le_b;
1099                         mi = mi_b;
1100                         goto repack;
1101                 }
1102         }
1103
1104         svcn = evcn1;
1105
1106         /* Estimate next attribute. */
1107         attr = ni_find_attr(ni, attr, &le, ATTR_DATA, NULL, 0, &svcn, &mi);
1108
1109         if (attr) {
1110                 CLST alloc = bytes_to_cluster(
1111                         sbi, le64_to_cpu(attr_b->nres.alloc_size));
1112                 CLST evcn = le64_to_cpu(attr->nres.evcn);
1113
1114                 if (end < next_svcn)
1115                         end = next_svcn;
1116                 while (end > evcn) {
1117                         /* Remove segment [svcn : evcn). */
1118                         mi_remove_attr(NULL, mi, attr);
1119
1120                         if (!al_remove_le(ni, le)) {
1121                                 err = -EINVAL;
1122                                 goto out;
1123                         }
1124
1125                         if (evcn + 1 >= alloc) {
1126                                 /* Last attribute segment. */
1127                                 evcn1 = evcn + 1;
1128                                 goto ins_ext;
1129                         }
1130
1131                         if (ni_load_mi(ni, le, &mi)) {
1132                                 attr = NULL;
1133                                 goto out;
1134                         }
1135
1136                         attr = mi_find_attr(mi, NULL, ATTR_DATA, NULL, 0,
1137                                             &le->id);
1138                         if (!attr) {
1139                                 err = -EINVAL;
1140                                 goto out;
1141                         }
1142                         svcn = le64_to_cpu(attr->nres.svcn);
1143                         evcn = le64_to_cpu(attr->nres.evcn);
1144                 }
1145
1146                 if (end < svcn)
1147                         end = svcn;
1148
1149                 err = attr_load_runs(attr, ni, run, &end);
1150                 if (err)
1151                         goto out;
1152
1153                 evcn1 = evcn + 1;
1154                 attr->nres.svcn = cpu_to_le64(next_svcn);
1155                 err = mi_pack_runs(mi, attr, run, evcn1 - next_svcn);
1156                 if (err)
1157                         goto out;
1158
1159                 le->vcn = cpu_to_le64(next_svcn);
1160                 ni->attr_list.dirty = true;
1161                 mi->dirty = true;
1162
1163                 next_svcn = le64_to_cpu(attr->nres.evcn) + 1;
1164         }
1165 ins_ext:
1166         if (evcn1 > next_svcn) {
1167                 err = ni_insert_nonresident(ni, ATTR_DATA, NULL, 0, run,
1168                                             next_svcn, evcn1 - next_svcn,
1169                                             attr_b->flags, &attr, &mi, NULL);
1170                 if (err)
1171                         goto out;
1172         }
1173 ok:
1174         run_truncate_around(run, vcn);
1175 out:
1176         up_write(&ni->file.run_lock);
1177         ni_unlock(ni);
1178
1179         return err;
1180 }
1181
1182 int attr_data_read_resident(struct ntfs_inode *ni, struct page *page)
1183 {
1184         u64 vbo;
1185         struct ATTRIB *attr;
1186         u32 data_size;
1187
1188         attr = ni_find_attr(ni, NULL, NULL, ATTR_DATA, NULL, 0, NULL, NULL);
1189         if (!attr)
1190                 return -EINVAL;
1191
1192         if (attr->non_res)
1193                 return E_NTFS_NONRESIDENT;
1194
1195         vbo = page->index << PAGE_SHIFT;
1196         data_size = le32_to_cpu(attr->res.data_size);
1197         if (vbo < data_size) {
1198                 const char *data = resident_data(attr);
1199                 char *kaddr = kmap_atomic(page);
1200                 u32 use = data_size - vbo;
1201
1202                 if (use > PAGE_SIZE)
1203                         use = PAGE_SIZE;
1204
1205                 memcpy(kaddr, data + vbo, use);
1206                 memset(kaddr + use, 0, PAGE_SIZE - use);
1207                 kunmap_atomic(kaddr);
1208                 flush_dcache_page(page);
1209                 SetPageUptodate(page);
1210         } else if (!PageUptodate(page)) {
1211                 zero_user_segment(page, 0, PAGE_SIZE);
1212                 SetPageUptodate(page);
1213         }
1214
1215         return 0;
1216 }
1217
1218 int attr_data_write_resident(struct ntfs_inode *ni, struct page *page)
1219 {
1220         u64 vbo;
1221         struct mft_inode *mi;
1222         struct ATTRIB *attr;
1223         u32 data_size;
1224
1225         attr = ni_find_attr(ni, NULL, NULL, ATTR_DATA, NULL, 0, NULL, &mi);
1226         if (!attr)
1227                 return -EINVAL;
1228
1229         if (attr->non_res) {
1230                 /* Return special error code to check this case. */
1231                 return E_NTFS_NONRESIDENT;
1232         }
1233
1234         vbo = page->index << PAGE_SHIFT;
1235         data_size = le32_to_cpu(attr->res.data_size);
1236         if (vbo < data_size) {
1237                 char *data = resident_data(attr);
1238                 char *kaddr = kmap_atomic(page);
1239                 u32 use = data_size - vbo;
1240
1241                 if (use > PAGE_SIZE)
1242                         use = PAGE_SIZE;
1243                 memcpy(data + vbo, kaddr, use);
1244                 kunmap_atomic(kaddr);
1245                 mi->dirty = true;
1246         }
1247         ni->i_valid = data_size;
1248
1249         return 0;
1250 }
1251
1252 /*
1253  * attr_load_runs_vcn - Load runs with VCN.
1254  */
1255 int attr_load_runs_vcn(struct ntfs_inode *ni, enum ATTR_TYPE type,
1256                        const __le16 *name, u8 name_len, struct runs_tree *run,
1257                        CLST vcn)
1258 {
1259         struct ATTRIB *attr;
1260         int err;
1261         CLST svcn, evcn;
1262         u16 ro;
1263
1264         if (!ni) {
1265                 /* Is record corrupted? */
1266                 return -ENOENT;
1267         }
1268
1269         attr = ni_find_attr(ni, NULL, NULL, type, name, name_len, &vcn, NULL);
1270         if (!attr) {
1271                 /* Is record corrupted? */
1272                 return -ENOENT;
1273         }
1274
1275         svcn = le64_to_cpu(attr->nres.svcn);
1276         evcn = le64_to_cpu(attr->nres.evcn);
1277
1278         if (evcn < vcn || vcn < svcn) {
1279                 /* Is record corrupted? */
1280                 return -EINVAL;
1281         }
1282
1283         ro = le16_to_cpu(attr->nres.run_off);
1284
1285         if (ro > le32_to_cpu(attr->size))
1286                 return -EINVAL;
1287
1288         err = run_unpack_ex(run, ni->mi.sbi, ni->mi.rno, svcn, evcn, svcn,
1289                             Add2Ptr(attr, ro), le32_to_cpu(attr->size) - ro);
1290         if (err < 0)
1291                 return err;
1292         return 0;
1293 }
1294
1295 /*
1296  * attr_load_runs_range - Load runs for given range [from to).
1297  */
1298 int attr_load_runs_range(struct ntfs_inode *ni, enum ATTR_TYPE type,
1299                          const __le16 *name, u8 name_len, struct runs_tree *run,
1300                          u64 from, u64 to)
1301 {
1302         struct ntfs_sb_info *sbi = ni->mi.sbi;
1303         u8 cluster_bits = sbi->cluster_bits;
1304         CLST vcn;
1305         CLST vcn_last = (to - 1) >> cluster_bits;
1306         CLST lcn, clen;
1307         int err;
1308
1309         for (vcn = from >> cluster_bits; vcn <= vcn_last; vcn += clen) {
1310                 if (!run_lookup_entry(run, vcn, &lcn, &clen, NULL)) {
1311                         err = attr_load_runs_vcn(ni, type, name, name_len, run,
1312                                                  vcn);
1313                         if (err)
1314                                 return err;
1315                         clen = 0; /* Next run_lookup_entry(vcn) must be success. */
1316                 }
1317         }
1318
1319         return 0;
1320 }
1321
1322 #ifdef CONFIG_NTFS3_LZX_XPRESS
1323 /*
1324  * attr_wof_frame_info
1325  *
1326  * Read header of Xpress/LZX file to get info about frame.
1327  */
1328 int attr_wof_frame_info(struct ntfs_inode *ni, struct ATTRIB *attr,
1329                         struct runs_tree *run, u64 frame, u64 frames,
1330                         u8 frame_bits, u32 *ondisk_size, u64 *vbo_data)
1331 {
1332         struct ntfs_sb_info *sbi = ni->mi.sbi;
1333         u64 vbo[2], off[2], wof_size;
1334         u32 voff;
1335         u8 bytes_per_off;
1336         char *addr;
1337         struct page *page;
1338         int i, err;
1339         __le32 *off32;
1340         __le64 *off64;
1341
1342         if (ni->vfs_inode.i_size < 0x100000000ull) {
1343                 /* File starts with array of 32 bit offsets. */
1344                 bytes_per_off = sizeof(__le32);
1345                 vbo[1] = frame << 2;
1346                 *vbo_data = frames << 2;
1347         } else {
1348                 /* File starts with array of 64 bit offsets. */
1349                 bytes_per_off = sizeof(__le64);
1350                 vbo[1] = frame << 3;
1351                 *vbo_data = frames << 3;
1352         }
1353
1354         /*
1355          * Read 4/8 bytes at [vbo - 4(8)] == offset where compressed frame starts.
1356          * Read 4/8 bytes at [vbo] == offset where compressed frame ends.
1357          */
1358         if (!attr->non_res) {
1359                 if (vbo[1] + bytes_per_off > le32_to_cpu(attr->res.data_size)) {
1360                         ntfs_inode_err(&ni->vfs_inode, "is corrupted");
1361                         return -EINVAL;
1362                 }
1363                 addr = resident_data(attr);
1364
1365                 if (bytes_per_off == sizeof(__le32)) {
1366                         off32 = Add2Ptr(addr, vbo[1]);
1367                         off[0] = vbo[1] ? le32_to_cpu(off32[-1]) : 0;
1368                         off[1] = le32_to_cpu(off32[0]);
1369                 } else {
1370                         off64 = Add2Ptr(addr, vbo[1]);
1371                         off[0] = vbo[1] ? le64_to_cpu(off64[-1]) : 0;
1372                         off[1] = le64_to_cpu(off64[0]);
1373                 }
1374
1375                 *vbo_data += off[0];
1376                 *ondisk_size = off[1] - off[0];
1377                 return 0;
1378         }
1379
1380         wof_size = le64_to_cpu(attr->nres.data_size);
1381         down_write(&ni->file.run_lock);
1382         page = ni->file.offs_page;
1383         if (!page) {
1384                 page = alloc_page(GFP_KERNEL);
1385                 if (!page) {
1386                         err = -ENOMEM;
1387                         goto out;
1388                 }
1389                 page->index = -1;
1390                 ni->file.offs_page = page;
1391         }
1392         lock_page(page);
1393         addr = page_address(page);
1394
1395         if (vbo[1]) {
1396                 voff = vbo[1] & (PAGE_SIZE - 1);
1397                 vbo[0] = vbo[1] - bytes_per_off;
1398                 i = 0;
1399         } else {
1400                 voff = 0;
1401                 vbo[0] = 0;
1402                 off[0] = 0;
1403                 i = 1;
1404         }
1405
1406         do {
1407                 pgoff_t index = vbo[i] >> PAGE_SHIFT;
1408
1409                 if (index != page->index) {
1410                         u64 from = vbo[i] & ~(u64)(PAGE_SIZE - 1);
1411                         u64 to = min(from + PAGE_SIZE, wof_size);
1412
1413                         err = attr_load_runs_range(ni, ATTR_DATA, WOF_NAME,
1414                                                    ARRAY_SIZE(WOF_NAME), run,
1415                                                    from, to);
1416                         if (err)
1417                                 goto out1;
1418
1419                         err = ntfs_bio_pages(sbi, run, &page, 1, from,
1420                                              to - from, REQ_OP_READ);
1421                         if (err) {
1422                                 page->index = -1;
1423                                 goto out1;
1424                         }
1425                         page->index = index;
1426                 }
1427
1428                 if (i) {
1429                         if (bytes_per_off == sizeof(__le32)) {
1430                                 off32 = Add2Ptr(addr, voff);
1431                                 off[1] = le32_to_cpu(*off32);
1432                         } else {
1433                                 off64 = Add2Ptr(addr, voff);
1434                                 off[1] = le64_to_cpu(*off64);
1435                         }
1436                 } else if (!voff) {
1437                         if (bytes_per_off == sizeof(__le32)) {
1438                                 off32 = Add2Ptr(addr, PAGE_SIZE - sizeof(u32));
1439                                 off[0] = le32_to_cpu(*off32);
1440                         } else {
1441                                 off64 = Add2Ptr(addr, PAGE_SIZE - sizeof(u64));
1442                                 off[0] = le64_to_cpu(*off64);
1443                         }
1444                 } else {
1445                         /* Two values in one page. */
1446                         if (bytes_per_off == sizeof(__le32)) {
1447                                 off32 = Add2Ptr(addr, voff);
1448                                 off[0] = le32_to_cpu(off32[-1]);
1449                                 off[1] = le32_to_cpu(off32[0]);
1450                         } else {
1451                                 off64 = Add2Ptr(addr, voff);
1452                                 off[0] = le64_to_cpu(off64[-1]);
1453                                 off[1] = le64_to_cpu(off64[0]);
1454                         }
1455                         break;
1456                 }
1457         } while (++i < 2);
1458
1459         *vbo_data += off[0];
1460         *ondisk_size = off[1] - off[0];
1461
1462 out1:
1463         unlock_page(page);
1464 out:
1465         up_write(&ni->file.run_lock);
1466         return err;
1467 }
1468 #endif
1469
1470 /*
1471  * attr_is_frame_compressed - Used to detect compressed frame.
1472  */
1473 int attr_is_frame_compressed(struct ntfs_inode *ni, struct ATTRIB *attr,
1474                              CLST frame, CLST *clst_data)
1475 {
1476         int err;
1477         u32 clst_frame;
1478         CLST clen, lcn, vcn, alen, slen, vcn_next;
1479         size_t idx;
1480         struct runs_tree *run;
1481
1482         *clst_data = 0;
1483
1484         if (!is_attr_compressed(attr))
1485                 return 0;
1486
1487         if (!attr->non_res)
1488                 return 0;
1489
1490         clst_frame = 1u << attr->nres.c_unit;
1491         vcn = frame * clst_frame;
1492         run = &ni->file.run;
1493
1494         if (!run_lookup_entry(run, vcn, &lcn, &clen, &idx)) {
1495                 err = attr_load_runs_vcn(ni, attr->type, attr_name(attr),
1496                                          attr->name_len, run, vcn);
1497                 if (err)
1498                         return err;
1499
1500                 if (!run_lookup_entry(run, vcn, &lcn, &clen, &idx))
1501                         return -EINVAL;
1502         }
1503
1504         if (lcn == SPARSE_LCN) {
1505                 /* Sparsed frame. */
1506                 return 0;
1507         }
1508
1509         if (clen >= clst_frame) {
1510                 /*
1511                  * The frame is not compressed 'cause
1512                  * it does not contain any sparse clusters.
1513                  */
1514                 *clst_data = clst_frame;
1515                 return 0;
1516         }
1517
1518         alen = bytes_to_cluster(ni->mi.sbi, le64_to_cpu(attr->nres.alloc_size));
1519         slen = 0;
1520         *clst_data = clen;
1521
1522         /*
1523          * The frame is compressed if *clst_data + slen >= clst_frame.
1524          * Check next fragments.
1525          */
1526         while ((vcn += clen) < alen) {
1527                 vcn_next = vcn;
1528
1529                 if (!run_get_entry(run, ++idx, &vcn, &lcn, &clen) ||
1530                     vcn_next != vcn) {
1531                         err = attr_load_runs_vcn(ni, attr->type,
1532                                                  attr_name(attr),
1533                                                  attr->name_len, run, vcn_next);
1534                         if (err)
1535                                 return err;
1536                         vcn = vcn_next;
1537
1538                         if (!run_lookup_entry(run, vcn, &lcn, &clen, &idx))
1539                                 return -EINVAL;
1540                 }
1541
1542                 if (lcn == SPARSE_LCN) {
1543                         slen += clen;
1544                 } else {
1545                         if (slen) {
1546                                 /*
1547                                  * Data_clusters + sparse_clusters =
1548                                  * not enough for frame.
1549                                  */
1550                                 return -EINVAL;
1551                         }
1552                         *clst_data += clen;
1553                 }
1554
1555                 if (*clst_data + slen >= clst_frame) {
1556                         if (!slen) {
1557                                 /*
1558                                  * There is no sparsed clusters in this frame
1559                                  * so it is not compressed.
1560                                  */
1561                                 *clst_data = clst_frame;
1562                         } else {
1563                                 /* Frame is compressed. */
1564                         }
1565                         break;
1566                 }
1567         }
1568
1569         return 0;
1570 }
1571
1572 /*
1573  * attr_allocate_frame - Allocate/free clusters for @frame.
1574  *
1575  * Assumed: down_write(&ni->file.run_lock);
1576  */
1577 int attr_allocate_frame(struct ntfs_inode *ni, CLST frame, size_t compr_size,
1578                         u64 new_valid)
1579 {
1580         int err = 0;
1581         struct runs_tree *run = &ni->file.run;
1582         struct ntfs_sb_info *sbi = ni->mi.sbi;
1583         struct ATTRIB *attr = NULL, *attr_b;
1584         struct ATTR_LIST_ENTRY *le, *le_b;
1585         struct mft_inode *mi, *mi_b;
1586         CLST svcn, evcn1, next_svcn, len;
1587         CLST vcn, end, clst_data;
1588         u64 total_size, valid_size, data_size;
1589
1590         le_b = NULL;
1591         attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL, 0, NULL, &mi_b);
1592         if (!attr_b)
1593                 return -ENOENT;
1594
1595         if (!is_attr_ext(attr_b))
1596                 return -EINVAL;
1597
1598         vcn = frame << NTFS_LZNT_CUNIT;
1599         total_size = le64_to_cpu(attr_b->nres.total_size);
1600
1601         svcn = le64_to_cpu(attr_b->nres.svcn);
1602         evcn1 = le64_to_cpu(attr_b->nres.evcn) + 1;
1603         data_size = le64_to_cpu(attr_b->nres.data_size);
1604
1605         if (svcn <= vcn && vcn < evcn1) {
1606                 attr = attr_b;
1607                 le = le_b;
1608                 mi = mi_b;
1609         } else if (!le_b) {
1610                 err = -EINVAL;
1611                 goto out;
1612         } else {
1613                 le = le_b;
1614                 attr = ni_find_attr(ni, attr_b, &le, ATTR_DATA, NULL, 0, &vcn,
1615                                     &mi);
1616                 if (!attr) {
1617                         err = -EINVAL;
1618                         goto out;
1619                 }
1620                 svcn = le64_to_cpu(attr->nres.svcn);
1621                 evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
1622         }
1623
1624         err = attr_load_runs(attr, ni, run, NULL);
1625         if (err)
1626                 goto out;
1627
1628         err = attr_is_frame_compressed(ni, attr_b, frame, &clst_data);
1629         if (err)
1630                 goto out;
1631
1632         total_size -= (u64)clst_data << sbi->cluster_bits;
1633
1634         len = bytes_to_cluster(sbi, compr_size);
1635
1636         if (len == clst_data)
1637                 goto out;
1638
1639         if (len < clst_data) {
1640                 err = run_deallocate_ex(sbi, run, vcn + len, clst_data - len,
1641                                         NULL, true);
1642                 if (err)
1643                         goto out;
1644
1645                 if (!run_add_entry(run, vcn + len, SPARSE_LCN, clst_data - len,
1646                                    false)) {
1647                         err = -ENOMEM;
1648                         goto out;
1649                 }
1650                 end = vcn + clst_data;
1651                 /* Run contains updated range [vcn + len : end). */
1652         } else {
1653                 CLST alen, hint = 0;
1654                 /* Get the last LCN to allocate from. */
1655                 if (vcn + clst_data &&
1656                     !run_lookup_entry(run, vcn + clst_data - 1, &hint, NULL,
1657                                       NULL)) {
1658                         hint = -1;
1659                 }
1660
1661                 err = attr_allocate_clusters(sbi, run, vcn + clst_data,
1662                                              hint + 1, len - clst_data, NULL,
1663                                              ALLOCATE_DEF, &alen, 0, NULL,
1664                                              NULL);
1665                 if (err)
1666                         goto out;
1667
1668                 end = vcn + len;
1669                 /* Run contains updated range [vcn + clst_data : end). */
1670         }
1671
1672         total_size += (u64)len << sbi->cluster_bits;
1673
1674 repack:
1675         err = mi_pack_runs(mi, attr, run, max(end, evcn1) - svcn);
1676         if (err)
1677                 goto out;
1678
1679         attr_b->nres.total_size = cpu_to_le64(total_size);
1680         inode_set_bytes(&ni->vfs_inode, total_size);
1681
1682         mi_b->dirty = true;
1683         mark_inode_dirty(&ni->vfs_inode);
1684
1685         /* Stored [vcn : next_svcn) from [vcn : end). */
1686         next_svcn = le64_to_cpu(attr->nres.evcn) + 1;
1687
1688         if (end <= evcn1) {
1689                 if (next_svcn == evcn1) {
1690                         /* Normal way. Update attribute and exit. */
1691                         goto ok;
1692                 }
1693                 /* Add new segment [next_svcn : evcn1 - next_svcn). */
1694                 if (!ni->attr_list.size) {
1695                         err = ni_create_attr_list(ni);
1696                         if (err)
1697                                 goto out;
1698                         /* Layout of records is changed. */
1699                         le_b = NULL;
1700                         attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL,
1701                                               0, NULL, &mi_b);
1702                         if (!attr_b) {
1703                                 err = -ENOENT;
1704                                 goto out;
1705                         }
1706
1707                         attr = attr_b;
1708                         le = le_b;
1709                         mi = mi_b;
1710                         goto repack;
1711                 }
1712         }
1713
1714         svcn = evcn1;
1715
1716         /* Estimate next attribute. */
1717         attr = ni_find_attr(ni, attr, &le, ATTR_DATA, NULL, 0, &svcn, &mi);
1718
1719         if (attr) {
1720                 CLST alloc = bytes_to_cluster(
1721                         sbi, le64_to_cpu(attr_b->nres.alloc_size));
1722                 CLST evcn = le64_to_cpu(attr->nres.evcn);
1723
1724                 if (end < next_svcn)
1725                         end = next_svcn;
1726                 while (end > evcn) {
1727                         /* Remove segment [svcn : evcn). */
1728                         mi_remove_attr(NULL, mi, attr);
1729
1730                         if (!al_remove_le(ni, le)) {
1731                                 err = -EINVAL;
1732                                 goto out;
1733                         }
1734
1735                         if (evcn + 1 >= alloc) {
1736                                 /* Last attribute segment. */
1737                                 evcn1 = evcn + 1;
1738                                 goto ins_ext;
1739                         }
1740
1741                         if (ni_load_mi(ni, le, &mi)) {
1742                                 attr = NULL;
1743                                 goto out;
1744                         }
1745
1746                         attr = mi_find_attr(mi, NULL, ATTR_DATA, NULL, 0,
1747                                             &le->id);
1748                         if (!attr) {
1749                                 err = -EINVAL;
1750                                 goto out;
1751                         }
1752                         svcn = le64_to_cpu(attr->nres.svcn);
1753                         evcn = le64_to_cpu(attr->nres.evcn);
1754                 }
1755
1756                 if (end < svcn)
1757                         end = svcn;
1758
1759                 err = attr_load_runs(attr, ni, run, &end);
1760                 if (err)
1761                         goto out;
1762
1763                 evcn1 = evcn + 1;
1764                 attr->nres.svcn = cpu_to_le64(next_svcn);
1765                 err = mi_pack_runs(mi, attr, run, evcn1 - next_svcn);
1766                 if (err)
1767                         goto out;
1768
1769                 le->vcn = cpu_to_le64(next_svcn);
1770                 ni->attr_list.dirty = true;
1771                 mi->dirty = true;
1772
1773                 next_svcn = le64_to_cpu(attr->nres.evcn) + 1;
1774         }
1775 ins_ext:
1776         if (evcn1 > next_svcn) {
1777                 err = ni_insert_nonresident(ni, ATTR_DATA, NULL, 0, run,
1778                                             next_svcn, evcn1 - next_svcn,
1779                                             attr_b->flags, &attr, &mi, NULL);
1780                 if (err)
1781                         goto out;
1782         }
1783 ok:
1784         run_truncate_around(run, vcn);
1785 out:
1786         if (new_valid > data_size)
1787                 new_valid = data_size;
1788
1789         valid_size = le64_to_cpu(attr_b->nres.valid_size);
1790         if (new_valid != valid_size) {
1791                 attr_b->nres.valid_size = cpu_to_le64(valid_size);
1792                 mi_b->dirty = true;
1793         }
1794
1795         return err;
1796 }
1797
1798 /*
1799  * attr_collapse_range - Collapse range in file.
1800  */
1801 int attr_collapse_range(struct ntfs_inode *ni, u64 vbo, u64 bytes)
1802 {
1803         int err = 0;
1804         struct runs_tree *run = &ni->file.run;
1805         struct ntfs_sb_info *sbi = ni->mi.sbi;
1806         struct ATTRIB *attr = NULL, *attr_b;
1807         struct ATTR_LIST_ENTRY *le, *le_b;
1808         struct mft_inode *mi, *mi_b;
1809         CLST svcn, evcn1, len, dealloc, alen;
1810         CLST vcn, end;
1811         u64 valid_size, data_size, alloc_size, total_size;
1812         u32 mask;
1813         __le16 a_flags;
1814
1815         if (!bytes)
1816                 return 0;
1817
1818         le_b = NULL;
1819         attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL, 0, NULL, &mi_b);
1820         if (!attr_b)
1821                 return -ENOENT;
1822
1823         if (!attr_b->non_res) {
1824                 /* Attribute is resident. Nothing to do? */
1825                 return 0;
1826         }
1827
1828         data_size = le64_to_cpu(attr_b->nres.data_size);
1829         alloc_size = le64_to_cpu(attr_b->nres.alloc_size);
1830         a_flags = attr_b->flags;
1831
1832         if (is_attr_ext(attr_b)) {
1833                 total_size = le64_to_cpu(attr_b->nres.total_size);
1834                 mask = (sbi->cluster_size << attr_b->nres.c_unit) - 1;
1835         } else {
1836                 total_size = alloc_size;
1837                 mask = sbi->cluster_mask;
1838         }
1839
1840         if ((vbo & mask) || (bytes & mask)) {
1841                 /* Allow to collapse only cluster aligned ranges. */
1842                 return -EINVAL;
1843         }
1844
1845         if (vbo > data_size)
1846                 return -EINVAL;
1847
1848         down_write(&ni->file.run_lock);
1849
1850         if (vbo + bytes >= data_size) {
1851                 u64 new_valid = min(ni->i_valid, vbo);
1852
1853                 /* Simple truncate file at 'vbo'. */
1854                 truncate_setsize(&ni->vfs_inode, vbo);
1855                 err = attr_set_size(ni, ATTR_DATA, NULL, 0, &ni->file.run, vbo,
1856                                     &new_valid, true, NULL);
1857
1858                 if (!err && new_valid < ni->i_valid)
1859                         ni->i_valid = new_valid;
1860
1861                 goto out;
1862         }
1863
1864         /*
1865          * Enumerate all attribute segments and collapse.
1866          */
1867         alen = alloc_size >> sbi->cluster_bits;
1868         vcn = vbo >> sbi->cluster_bits;
1869         len = bytes >> sbi->cluster_bits;
1870         end = vcn + len;
1871         dealloc = 0;
1872
1873         svcn = le64_to_cpu(attr_b->nres.svcn);
1874         evcn1 = le64_to_cpu(attr_b->nres.evcn) + 1;
1875
1876         if (svcn <= vcn && vcn < evcn1) {
1877                 attr = attr_b;
1878                 le = le_b;
1879                 mi = mi_b;
1880         } else if (!le_b) {
1881                 err = -EINVAL;
1882                 goto out;
1883         } else {
1884                 le = le_b;
1885                 attr = ni_find_attr(ni, attr_b, &le, ATTR_DATA, NULL, 0, &vcn,
1886                                     &mi);
1887                 if (!attr) {
1888                         err = -EINVAL;
1889                         goto out;
1890                 }
1891
1892                 svcn = le64_to_cpu(attr->nres.svcn);
1893                 evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
1894         }
1895
1896         for (;;) {
1897                 if (svcn >= end) {
1898                         /* Shift VCN- */
1899                         attr->nres.svcn = cpu_to_le64(svcn - len);
1900                         attr->nres.evcn = cpu_to_le64(evcn1 - 1 - len);
1901                         if (le) {
1902                                 le->vcn = attr->nres.svcn;
1903                                 ni->attr_list.dirty = true;
1904                         }
1905                         mi->dirty = true;
1906                 } else if (svcn < vcn || end < evcn1) {
1907                         CLST vcn1, eat, next_svcn;
1908
1909                         /* Collapse a part of this attribute segment. */
1910                         err = attr_load_runs(attr, ni, run, &svcn);
1911                         if (err)
1912                                 goto out;
1913                         vcn1 = max(vcn, svcn);
1914                         eat = min(end, evcn1) - vcn1;
1915
1916                         err = run_deallocate_ex(sbi, run, vcn1, eat, &dealloc,
1917                                                 true);
1918                         if (err)
1919                                 goto out;
1920
1921                         if (!run_collapse_range(run, vcn1, eat)) {
1922                                 err = -ENOMEM;
1923                                 goto out;
1924                         }
1925
1926                         if (svcn >= vcn) {
1927                                 /* Shift VCN */
1928                                 attr->nres.svcn = cpu_to_le64(vcn);
1929                                 if (le) {
1930                                         le->vcn = attr->nres.svcn;
1931                                         ni->attr_list.dirty = true;
1932                                 }
1933                         }
1934
1935                         err = mi_pack_runs(mi, attr, run, evcn1 - svcn - eat);
1936                         if (err)
1937                                 goto out;
1938
1939                         next_svcn = le64_to_cpu(attr->nres.evcn) + 1;
1940                         if (next_svcn + eat < evcn1) {
1941                                 err = ni_insert_nonresident(
1942                                         ni, ATTR_DATA, NULL, 0, run, next_svcn,
1943                                         evcn1 - eat - next_svcn, a_flags, &attr,
1944                                         &mi, &le);
1945                                 if (err)
1946                                         goto out;
1947
1948                                 /* Layout of records maybe changed. */
1949                                 attr_b = NULL;
1950                         }
1951
1952                         /* Free all allocated memory. */
1953                         run_truncate(run, 0);
1954                 } else {
1955                         u16 le_sz;
1956                         u16 roff = le16_to_cpu(attr->nres.run_off);
1957
1958                         if (roff > le32_to_cpu(attr->size)) {
1959                                 err = -EINVAL;
1960                                 goto out;
1961                         }
1962
1963                         run_unpack_ex(RUN_DEALLOCATE, sbi, ni->mi.rno, svcn,
1964                                       evcn1 - 1, svcn, Add2Ptr(attr, roff),
1965                                       le32_to_cpu(attr->size) - roff);
1966
1967                         /* Delete this attribute segment. */
1968                         mi_remove_attr(NULL, mi, attr);
1969                         if (!le)
1970                                 break;
1971
1972                         le_sz = le16_to_cpu(le->size);
1973                         if (!al_remove_le(ni, le)) {
1974                                 err = -EINVAL;
1975                                 goto out;
1976                         }
1977
1978                         if (evcn1 >= alen)
1979                                 break;
1980
1981                         if (!svcn) {
1982                                 /* Load next record that contains this attribute. */
1983                                 if (ni_load_mi(ni, le, &mi)) {
1984                                         err = -EINVAL;
1985                                         goto out;
1986                                 }
1987
1988                                 /* Look for required attribute. */
1989                                 attr = mi_find_attr(mi, NULL, ATTR_DATA, NULL,
1990                                                     0, &le->id);
1991                                 if (!attr) {
1992                                         err = -EINVAL;
1993                                         goto out;
1994                                 }
1995                                 goto next_attr;
1996                         }
1997                         le = (struct ATTR_LIST_ENTRY *)((u8 *)le - le_sz);
1998                 }
1999
2000                 if (evcn1 >= alen)
2001                         break;
2002
2003                 attr = ni_enum_attr_ex(ni, attr, &le, &mi);
2004                 if (!attr) {
2005                         err = -EINVAL;
2006                         goto out;
2007                 }
2008
2009 next_attr:
2010                 svcn = le64_to_cpu(attr->nres.svcn);
2011                 evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
2012         }
2013
2014         if (!attr_b) {
2015                 le_b = NULL;
2016                 attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL, 0, NULL,
2017                                       &mi_b);
2018                 if (!attr_b) {
2019                         err = -ENOENT;
2020                         goto out;
2021                 }
2022         }
2023
2024         data_size -= bytes;
2025         valid_size = ni->i_valid;
2026         if (vbo + bytes <= valid_size)
2027                 valid_size -= bytes;
2028         else if (vbo < valid_size)
2029                 valid_size = vbo;
2030
2031         attr_b->nres.alloc_size = cpu_to_le64(alloc_size - bytes);
2032         attr_b->nres.data_size = cpu_to_le64(data_size);
2033         attr_b->nres.valid_size = cpu_to_le64(min(valid_size, data_size));
2034         total_size -= (u64)dealloc << sbi->cluster_bits;
2035         if (is_attr_ext(attr_b))
2036                 attr_b->nres.total_size = cpu_to_le64(total_size);
2037         mi_b->dirty = true;
2038
2039         /* Update inode size. */
2040         ni->i_valid = valid_size;
2041         ni->vfs_inode.i_size = data_size;
2042         inode_set_bytes(&ni->vfs_inode, total_size);
2043         ni->ni_flags |= NI_FLAG_UPDATE_PARENT;
2044         mark_inode_dirty(&ni->vfs_inode);
2045
2046 out:
2047         up_write(&ni->file.run_lock);
2048         if (err)
2049                 _ntfs_bad_inode(&ni->vfs_inode);
2050
2051         return err;
2052 }
2053
2054 /*
2055  * attr_punch_hole
2056  *
2057  * Not for normal files.
2058  */
2059 int attr_punch_hole(struct ntfs_inode *ni, u64 vbo, u64 bytes, u32 *frame_size)
2060 {
2061         int err = 0;
2062         struct runs_tree *run = &ni->file.run;
2063         struct ntfs_sb_info *sbi = ni->mi.sbi;
2064         struct ATTRIB *attr = NULL, *attr_b;
2065         struct ATTR_LIST_ENTRY *le, *le_b;
2066         struct mft_inode *mi, *mi_b;
2067         CLST svcn, evcn1, vcn, len, end, alen, hole, next_svcn;
2068         u64 total_size, alloc_size;
2069         u32 mask;
2070         __le16 a_flags;
2071         struct runs_tree run2;
2072
2073         if (!bytes)
2074                 return 0;
2075
2076         le_b = NULL;
2077         attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL, 0, NULL, &mi_b);
2078         if (!attr_b)
2079                 return -ENOENT;
2080
2081         if (!attr_b->non_res) {
2082                 u32 data_size = le32_to_cpu(attr_b->res.data_size);
2083                 u32 from, to;
2084
2085                 if (vbo > data_size)
2086                         return 0;
2087
2088                 from = vbo;
2089                 to = min_t(u64, vbo + bytes, data_size);
2090                 memset(Add2Ptr(resident_data(attr_b), from), 0, to - from);
2091                 return 0;
2092         }
2093
2094         if (!is_attr_ext(attr_b))
2095                 return -EOPNOTSUPP;
2096
2097         alloc_size = le64_to_cpu(attr_b->nres.alloc_size);
2098         total_size = le64_to_cpu(attr_b->nres.total_size);
2099
2100         if (vbo >= alloc_size) {
2101                 /* NOTE: It is allowed. */
2102                 return 0;
2103         }
2104
2105         mask = (sbi->cluster_size << attr_b->nres.c_unit) - 1;
2106
2107         bytes += vbo;
2108         if (bytes > alloc_size)
2109                 bytes = alloc_size;
2110         bytes -= vbo;
2111
2112         if ((vbo & mask) || (bytes & mask)) {
2113                 /* We have to zero a range(s). */
2114                 if (frame_size == NULL) {
2115                         /* Caller insists range is aligned. */
2116                         return -EINVAL;
2117                 }
2118                 *frame_size = mask + 1;
2119                 return E_NTFS_NOTALIGNED;
2120         }
2121
2122         down_write(&ni->file.run_lock);
2123         run_init(&run2);
2124         run_truncate(run, 0);
2125
2126         /*
2127          * Enumerate all attribute segments and punch hole where necessary.
2128          */
2129         alen = alloc_size >> sbi->cluster_bits;
2130         vcn = vbo >> sbi->cluster_bits;
2131         len = bytes >> sbi->cluster_bits;
2132         end = vcn + len;
2133         hole = 0;
2134
2135         svcn = le64_to_cpu(attr_b->nres.svcn);
2136         evcn1 = le64_to_cpu(attr_b->nres.evcn) + 1;
2137         a_flags = attr_b->flags;
2138
2139         if (svcn <= vcn && vcn < evcn1) {
2140                 attr = attr_b;
2141                 le = le_b;
2142                 mi = mi_b;
2143         } else if (!le_b) {
2144                 err = -EINVAL;
2145                 goto bad_inode;
2146         } else {
2147                 le = le_b;
2148                 attr = ni_find_attr(ni, attr_b, &le, ATTR_DATA, NULL, 0, &vcn,
2149                                     &mi);
2150                 if (!attr) {
2151                         err = -EINVAL;
2152                         goto bad_inode;
2153                 }
2154
2155                 svcn = le64_to_cpu(attr->nres.svcn);
2156                 evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
2157         }
2158
2159         while (svcn < end) {
2160                 CLST vcn1, zero, hole2 = hole;
2161
2162                 err = attr_load_runs(attr, ni, run, &svcn);
2163                 if (err)
2164                         goto done;
2165                 vcn1 = max(vcn, svcn);
2166                 zero = min(end, evcn1) - vcn1;
2167
2168                 /*
2169                  * Check range [vcn1 + zero).
2170                  * Calculate how many clusters there are.
2171                  * Don't do any destructive actions.
2172                  */
2173                 err = run_deallocate_ex(NULL, run, vcn1, zero, &hole2, false);
2174                 if (err)
2175                         goto done;
2176
2177                 /* Check if required range is already hole. */
2178                 if (hole2 == hole)
2179                         goto next_attr;
2180
2181                 /* Make a clone of run to undo. */
2182                 err = run_clone(run, &run2);
2183                 if (err)
2184                         goto done;
2185
2186                 /* Make a hole range (sparse) [vcn1 + zero). */
2187                 if (!run_add_entry(run, vcn1, SPARSE_LCN, zero, false)) {
2188                         err = -ENOMEM;
2189                         goto done;
2190                 }
2191
2192                 /* Update run in attribute segment. */
2193                 err = mi_pack_runs(mi, attr, run, evcn1 - svcn);
2194                 if (err)
2195                         goto done;
2196                 next_svcn = le64_to_cpu(attr->nres.evcn) + 1;
2197                 if (next_svcn < evcn1) {
2198                         /* Insert new attribute segment. */
2199                         err = ni_insert_nonresident(ni, ATTR_DATA, NULL, 0, run,
2200                                                     next_svcn,
2201                                                     evcn1 - next_svcn, a_flags,
2202                                                     &attr, &mi, &le);
2203                         if (err)
2204                                 goto undo_punch;
2205
2206                         /* Layout of records maybe changed. */
2207                         attr_b = NULL;
2208                 }
2209
2210                 /* Real deallocate. Should not fail. */
2211                 run_deallocate_ex(sbi, &run2, vcn1, zero, &hole, true);
2212
2213 next_attr:
2214                 /* Free all allocated memory. */
2215                 run_truncate(run, 0);
2216
2217                 if (evcn1 >= alen)
2218                         break;
2219
2220                 /* Get next attribute segment. */
2221                 attr = ni_enum_attr_ex(ni, attr, &le, &mi);
2222                 if (!attr) {
2223                         err = -EINVAL;
2224                         goto bad_inode;
2225                 }
2226
2227                 svcn = le64_to_cpu(attr->nres.svcn);
2228                 evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
2229         }
2230
2231 done:
2232         if (!hole)
2233                 goto out;
2234
2235         if (!attr_b) {
2236                 attr_b = ni_find_attr(ni, NULL, NULL, ATTR_DATA, NULL, 0, NULL,
2237                                       &mi_b);
2238                 if (!attr_b) {
2239                         err = -EINVAL;
2240                         goto bad_inode;
2241                 }
2242         }
2243
2244         total_size -= (u64)hole << sbi->cluster_bits;
2245         attr_b->nres.total_size = cpu_to_le64(total_size);
2246         mi_b->dirty = true;
2247
2248         /* Update inode size. */
2249         inode_set_bytes(&ni->vfs_inode, total_size);
2250         ni->ni_flags |= NI_FLAG_UPDATE_PARENT;
2251         mark_inode_dirty(&ni->vfs_inode);
2252
2253 out:
2254         run_close(&run2);
2255         up_write(&ni->file.run_lock);
2256         return err;
2257
2258 bad_inode:
2259         _ntfs_bad_inode(&ni->vfs_inode);
2260         goto out;
2261
2262 undo_punch:
2263         /*
2264          * Restore packed runs.
2265          * 'mi_pack_runs' should not fail, cause we restore original.
2266          */
2267         if (mi_pack_runs(mi, attr, &run2, evcn1 - svcn))
2268                 goto bad_inode;
2269
2270         goto done;
2271 }
2272
2273 /*
2274  * attr_insert_range - Insert range (hole) in file.
2275  * Not for normal files.
2276  */
2277 int attr_insert_range(struct ntfs_inode *ni, u64 vbo, u64 bytes)
2278 {
2279         int err = 0;
2280         struct runs_tree *run = &ni->file.run;
2281         struct ntfs_sb_info *sbi = ni->mi.sbi;
2282         struct ATTRIB *attr = NULL, *attr_b;
2283         struct ATTR_LIST_ENTRY *le, *le_b;
2284         struct mft_inode *mi, *mi_b;
2285         CLST vcn, svcn, evcn1, len, next_svcn;
2286         u64 data_size, alloc_size;
2287         u32 mask;
2288         __le16 a_flags;
2289
2290         if (!bytes)
2291                 return 0;
2292
2293         le_b = NULL;
2294         attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL, 0, NULL, &mi_b);
2295         if (!attr_b)
2296                 return -ENOENT;
2297
2298         if (!is_attr_ext(attr_b)) {
2299                 /* It was checked above. See fallocate. */
2300                 return -EOPNOTSUPP;
2301         }
2302
2303         if (!attr_b->non_res) {
2304                 data_size = le32_to_cpu(attr_b->res.data_size);
2305                 alloc_size = data_size;
2306                 mask = sbi->cluster_mask; /* cluster_size - 1 */
2307         } else {
2308                 data_size = le64_to_cpu(attr_b->nres.data_size);
2309                 alloc_size = le64_to_cpu(attr_b->nres.alloc_size);
2310                 mask = (sbi->cluster_size << attr_b->nres.c_unit) - 1;
2311         }
2312
2313         if (vbo > data_size) {
2314                 /* Insert range after the file size is not allowed. */
2315                 return -EINVAL;
2316         }
2317
2318         if ((vbo & mask) || (bytes & mask)) {
2319                 /* Allow to insert only frame aligned ranges. */
2320                 return -EINVAL;
2321         }
2322
2323         /*
2324          * valid_size <= data_size <= alloc_size
2325          * Check alloc_size for maximum possible.
2326          */
2327         if (bytes > sbi->maxbytes_sparse - alloc_size)
2328                 return -EFBIG;
2329
2330         vcn = vbo >> sbi->cluster_bits;
2331         len = bytes >> sbi->cluster_bits;
2332
2333         down_write(&ni->file.run_lock);
2334
2335         if (!attr_b->non_res) {
2336                 err = attr_set_size(ni, ATTR_DATA, NULL, 0, run,
2337                                     data_size + bytes, NULL, false, NULL);
2338
2339                 le_b = NULL;
2340                 attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL, 0, NULL,
2341                                       &mi_b);
2342                 if (!attr_b) {
2343                         err = -EINVAL;
2344                         goto bad_inode;
2345                 }
2346
2347                 if (err)
2348                         goto out;
2349
2350                 if (!attr_b->non_res) {
2351                         /* Still resident. */
2352                         char *data = Add2Ptr(attr_b,
2353                                              le16_to_cpu(attr_b->res.data_off));
2354
2355                         memmove(data + bytes, data, bytes);
2356                         memset(data, 0, bytes);
2357                         goto done;
2358                 }
2359
2360                 /* Resident files becomes nonresident. */
2361                 data_size = le64_to_cpu(attr_b->nres.data_size);
2362                 alloc_size = le64_to_cpu(attr_b->nres.alloc_size);
2363         }
2364
2365         /*
2366          * Enumerate all attribute segments and shift start vcn.
2367          */
2368         a_flags = attr_b->flags;
2369         svcn = le64_to_cpu(attr_b->nres.svcn);
2370         evcn1 = le64_to_cpu(attr_b->nres.evcn) + 1;
2371
2372         if (svcn <= vcn && vcn < evcn1) {
2373                 attr = attr_b;
2374                 le = le_b;
2375                 mi = mi_b;
2376         } else if (!le_b) {
2377                 err = -EINVAL;
2378                 goto bad_inode;
2379         } else {
2380                 le = le_b;
2381                 attr = ni_find_attr(ni, attr_b, &le, ATTR_DATA, NULL, 0, &vcn,
2382                                     &mi);
2383                 if (!attr) {
2384                         err = -EINVAL;
2385                         goto bad_inode;
2386                 }
2387
2388                 svcn = le64_to_cpu(attr->nres.svcn);
2389                 evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
2390         }
2391
2392         run_truncate(run, 0); /* clear cached values. */
2393         err = attr_load_runs(attr, ni, run, NULL);
2394         if (err)
2395                 goto out;
2396
2397         if (!run_insert_range(run, vcn, len)) {
2398                 err = -ENOMEM;
2399                 goto out;
2400         }
2401
2402         /* Try to pack in current record as much as possible. */
2403         err = mi_pack_runs(mi, attr, run, evcn1 + len - svcn);
2404         if (err)
2405                 goto out;
2406
2407         next_svcn = le64_to_cpu(attr->nres.evcn) + 1;
2408
2409         while ((attr = ni_enum_attr_ex(ni, attr, &le, &mi)) &&
2410                attr->type == ATTR_DATA && !attr->name_len) {
2411                 le64_add_cpu(&attr->nres.svcn, len);
2412                 le64_add_cpu(&attr->nres.evcn, len);
2413                 if (le) {
2414                         le->vcn = attr->nres.svcn;
2415                         ni->attr_list.dirty = true;
2416                 }
2417                 mi->dirty = true;
2418         }
2419
2420         if (next_svcn < evcn1 + len) {
2421                 err = ni_insert_nonresident(ni, ATTR_DATA, NULL, 0, run,
2422                                             next_svcn, evcn1 + len - next_svcn,
2423                                             a_flags, NULL, NULL, NULL);
2424
2425                 le_b = NULL;
2426                 attr_b = ni_find_attr(ni, NULL, &le_b, ATTR_DATA, NULL, 0, NULL,
2427                                       &mi_b);
2428                 if (!attr_b) {
2429                         err = -EINVAL;
2430                         goto bad_inode;
2431                 }
2432
2433                 if (err) {
2434                         /* ni_insert_nonresident failed. Try to undo. */
2435                         goto undo_insert_range;
2436                 }
2437         }
2438
2439         /*
2440          * Update primary attribute segment.
2441          */
2442         if (vbo <= ni->i_valid)
2443                 ni->i_valid += bytes;
2444
2445         attr_b->nres.data_size = cpu_to_le64(data_size + bytes);
2446         attr_b->nres.alloc_size = cpu_to_le64(alloc_size + bytes);
2447
2448         /* ni->valid may be not equal valid_size (temporary). */
2449         if (ni->i_valid > data_size + bytes)
2450                 attr_b->nres.valid_size = attr_b->nres.data_size;
2451         else
2452                 attr_b->nres.valid_size = cpu_to_le64(ni->i_valid);
2453         mi_b->dirty = true;
2454
2455 done:
2456         ni->vfs_inode.i_size += bytes;
2457         ni->ni_flags |= NI_FLAG_UPDATE_PARENT;
2458         mark_inode_dirty(&ni->vfs_inode);
2459
2460 out:
2461         run_truncate(run, 0); /* clear cached values. */
2462
2463         up_write(&ni->file.run_lock);
2464
2465         return err;
2466
2467 bad_inode:
2468         _ntfs_bad_inode(&ni->vfs_inode);
2469         goto out;
2470
2471 undo_insert_range:
2472         svcn = le64_to_cpu(attr_b->nres.svcn);
2473         evcn1 = le64_to_cpu(attr_b->nres.evcn) + 1;
2474
2475         if (svcn <= vcn && vcn < evcn1) {
2476                 attr = attr_b;
2477                 le = le_b;
2478                 mi = mi_b;
2479         } else if (!le_b) {
2480                 goto bad_inode;
2481         } else {
2482                 le = le_b;
2483                 attr = ni_find_attr(ni, attr_b, &le, ATTR_DATA, NULL, 0, &vcn,
2484                                     &mi);
2485                 if (!attr) {
2486                         goto bad_inode;
2487                 }
2488
2489                 svcn = le64_to_cpu(attr->nres.svcn);
2490                 evcn1 = le64_to_cpu(attr->nres.evcn) + 1;
2491         }
2492
2493         if (attr_load_runs(attr, ni, run, NULL))
2494                 goto bad_inode;
2495
2496         if (!run_collapse_range(run, vcn, len))
2497                 goto bad_inode;
2498
2499         if (mi_pack_runs(mi, attr, run, evcn1 + len - svcn))
2500                 goto bad_inode;
2501
2502         while ((attr = ni_enum_attr_ex(ni, attr, &le, &mi)) &&
2503                attr->type == ATTR_DATA && !attr->name_len) {
2504                 le64_sub_cpu(&attr->nres.svcn, len);
2505                 le64_sub_cpu(&attr->nres.evcn, len);
2506                 if (le) {
2507                         le->vcn = attr->nres.svcn;
2508                         ni->attr_list.dirty = true;
2509                 }
2510                 mi->dirty = true;
2511         }
2512
2513         goto out;
2514 }