fs/ntfs/runlist.c

   1 /**
   2  * runlist.c - NTFS runlist handling code.  Part of the Linux-NTFS project.
   3  *
   4  * Copyright (c) 2001-2005 Anton Altaparmakov
   5  * Copyright (c) 2002-2005 Richard Russon
   6  *
   7  * This program/include file is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License as published
   9  * by the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program/include file is distributed in the hope that it will be
  13  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program (in the main directory of the Linux-NTFS
  19  * distribution in the file COPYING); if not, write to the Free Software
  20  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  */
  22
  23 #include "debug.h"
  24 #include "dir.h"
  25 #include "endian.h"
  26 #include "malloc.h"
  27 #include "ntfs.h"
  28
  29 /**
  30  * ntfs_rl_mm - runlist memmove
  31  *
  32  * It is up to the caller to serialize access to the runlist @base.
  33  */
  34 static inline void ntfs_rl_mm(runlist_element *base, int dst, int src,
  35                 int size)
  36 {
  37         if (likely((dst != src) && (size > 0)))
  38                 memmove(base + dst, base + src, size * sizeof(*base));
  39 }
  40
  41 /**
  42  * ntfs_rl_mc - runlist memory copy
  43  *
  44  * It is up to the caller to serialize access to the runlists @dstbase and
  45  * @srcbase.
  46  */
  47 static inline void ntfs_rl_mc(runlist_element *dstbase, int dst,
  48                 runlist_element *srcbase, int src, int size)
  49 {
  50         if (likely(size > 0))
  51                 memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
  52 }
  53
  54 /**
  55  * ntfs_rl_realloc - Reallocate memory for runlists
  56  * @rl:         original runlist
  57  * @old_size:   number of runlist elements in the original runlist @rl
  58  * @new_size:   number of runlist elements we need space for
  59  *
  60  * As the runlists grow, more memory will be required.  To prevent the
  61  * kernel having to allocate and reallocate large numbers of small bits of
  62  * memory, this function returns an entire page of memory.
  63  *
  64  * It is up to the caller to serialize access to the runlist @rl.
  65  *
  66  * N.B.  If the new allocation doesn't require a different number of pages in
  67  *       memory, the function will return the original pointer.
  68  *
  69  * On success, return a pointer to the newly allocated, or recycled, memory.
  70  * On error, return -errno. The following error codes are defined:
  71  *      -ENOMEM - Not enough memory to allocate runlist array.
  72  *      -EINVAL - Invalid parameters were passed in.
  73  */
  74 static inline runlist_element *ntfs_rl_realloc(runlist_element *rl,
  75                 int old_size, int new_size)
  76 {
  77         runlist_element *new_rl;
  78
  79         old_size = PAGE_ALIGN(old_size * sizeof(*rl));
  80         new_size = PAGE_ALIGN(new_size * sizeof(*rl));
  81         if (old_size == new_size)
  82                 return rl;
  83
  84         new_rl = ntfs_malloc_nofs(new_size);
  85         if (unlikely(!new_rl))
  86                 return ERR_PTR(-ENOMEM);
  87
  88         if (likely(rl != NULL)) {
  89                 if (unlikely(old_size > new_size))
  90                         old_size = new_size;
  91                 memcpy(new_rl, rl, old_size);
  92                 ntfs_free(rl);
  93         }
  94         return new_rl;
  95 }
  96
  97 /**
  98  * ntfs_rl_realloc_nofail - Reallocate memory for runlists
  99  * @rl:         original runlist
 100  * @old_size:   number of runlist elements in the original runlist @rl
 101  * @new_size:   number of runlist elements we need space for
 102  *
 103  * As the runlists grow, more memory will be required.  To prevent the
 104  * kernel having to allocate and reallocate large numbers of small bits of
 105  * memory, this function returns an entire page of memory.
 106  *
 107  * This function guarantees that the allocation will succeed.  It will sleep
 108  * for as long as it takes to complete the allocation.
 109  *
 110  * It is up to the caller to serialize access to the runlist @rl.
 111  *
 112  * N.B.  If the new allocation doesn't require a different number of pages in
 113  *       memory, the function will return the original pointer.
 114  *
 115  * On success, return a pointer to the newly allocated, or recycled, memory.
 116  * On error, return -errno. The following error codes are defined:
 117  *      -ENOMEM - Not enough memory to allocate runlist array.
 118  *      -EINVAL - Invalid parameters were passed in.
 119  */
 120 static inline runlist_element *ntfs_rl_realloc_nofail(runlist_element *rl,
 121                 int old_size, int new_size)
 122 {
 123         runlist_element *new_rl;
 124
 125         old_size = PAGE_ALIGN(old_size * sizeof(*rl));
 126         new_size = PAGE_ALIGN(new_size * sizeof(*rl));
 127         if (old_size == new_size)
 128                 return rl;
 129
 130         new_rl = ntfs_malloc_nofs_nofail(new_size);
 131         BUG_ON(!new_rl);
 132
 133         if (likely(rl != NULL)) {
 134                 if (unlikely(old_size > new_size))
 135                         old_size = new_size;
 136                 memcpy(new_rl, rl, old_size);
 137                 ntfs_free(rl);
 138         }
 139         return new_rl;
 140 }
 141
 142 /**
 143  * ntfs_are_rl_mergeable - test if two runlists can be joined together
 144  * @dst:        original runlist
 145  * @src:        new runlist to test for mergeability with @dst
 146  *
 147  * Test if two runlists can be joined together. For this, their VCNs and LCNs
 148  * must be adjacent.
 149  *
 150  * It is up to the caller to serialize access to the runlists @dst and @src.
 151  *
 152  * Return: TRUE   Success, the runlists can be merged.
 153  *         FALSE  Failure, the runlists cannot be merged.
 154  */
 155 static inline BOOL ntfs_are_rl_mergeable(runlist_element *dst,
 156                 runlist_element *src)
 157 {
 158         BUG_ON(!dst);
 159         BUG_ON(!src);
 160
 161         if ((dst->lcn < 0) || (src->lcn < 0)) {   /* Are we merging holes? */
 162                 if (dst->lcn == LCN_HOLE && src->lcn == LCN_HOLE)
 163                         return TRUE;
 164                 return FALSE;
 165         }
 166         if ((dst->lcn + dst->length) != src->lcn) /* Are the runs contiguous? */
 167                 return FALSE;
 168         if ((dst->vcn + dst->length) != src->vcn) /* Are the runs misaligned? */
 169                 return FALSE;
 170
 171         return TRUE;
 172 }
 173
 174 /**
 175  * __ntfs_rl_merge - merge two runlists without testing if they can be merged
 176  * @dst:        original, destination runlist
 177  * @src:        new runlist to merge with @dst
 178  *
 179  * Merge the two runlists, writing into the destination runlist @dst. The
 180  * caller must make sure the runlists can be merged or this will corrupt the
 181  * destination runlist.
 182  *
 183  * It is up to the caller to serialize access to the runlists @dst and @src.
 184  */
 185 static inline void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
 186 {
 187         dst->length += src->length;
 188 }
 189
 190 /**
 191  * ntfs_rl_append - append a runlist after a given element
 192  * @dst:        original runlist to be worked on
 193  * @dsize:      number of elements in @dst (including end marker)
 194  * @src:        runlist to be inserted into @dst
 195  * @ssize:      number of elements in @src (excluding end marker)
 196  * @loc:        append the new runlist @src after this element in @dst
 197  *
 198  * Append the runlist @src after element @loc in @dst.  Merge the right end of
 199  * the new runlist, if necessary. Adjust the size of the hole before the
 200  * appended runlist.
 201  *
 202  * It is up to the caller to serialize access to the runlists @dst and @src.
 203  *
 204  * On success, return a pointer to the new, combined, runlist. Note, both
 205  * runlists @dst and @src are deallocated before returning so you cannot use
 206  * the pointers for anything any more. (Strictly speaking the returned runlist
 207  * may be the same as @dst but this is irrelevant.)
 208  *
 209  * On error, return -errno. Both runlists are left unmodified. The following
 210  * error codes are defined:
 211  *      -ENOMEM - Not enough memory to allocate runlist array.
 212  *      -EINVAL - Invalid parameters were passed in.
 213  */
 214 static inline runlist_element *ntfs_rl_append(runlist_element *dst,
 215                 int dsize, runlist_element *src, int ssize, int loc)
 216 {
 217         BOOL right;     /* Right end of @src needs merging. */
 218         int marker;     /* End of the inserted runs. */
 219
 220         BUG_ON(!dst);
 221         BUG_ON(!src);
 222
 223         /* First, check if the right hand end needs merging. */
 224         right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
 225
 226         /* Space required: @dst size + @src size, less one if we merged. */
 227         dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
 228         if (IS_ERR(dst))
 229                 return dst;
 230         /*
 231          * We are guaranteed to succeed from here so can start modifying the
 232          * original runlists.
 233          */
 234
 235         /* First, merge the right hand end, if necessary. */
 236         if (right)
 237                 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
 238
 239         /* First run after the @src runs that have been inserted. */
 240         marker = loc + ssize + 1;
 241
 242         /* Move the tail of @dst out of the way, then copy in @src. */
 243         ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - (loc + 1 + right));
 244         ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
 245
 246         /* Adjust the size of the preceding hole. */
 247         dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
 248
 249         /* We may have changed the length of the file, so fix the end marker */
 250         if (dst[marker].lcn == LCN_ENOENT)
 251                 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
 252
 253         return dst;
 254 }
 255
 256 /**
 257  * ntfs_rl_insert - insert a runlist into another
 258  * @dst:        original runlist to be worked on
 259  * @dsize:      number of elements in @dst (including end marker)
 260  * @src:        new runlist to be inserted
 261  * @ssize:      number of elements in @src (excluding end marker)
 262  * @loc:        insert the new runlist @src before this element in @dst
 263  *
 264  * Insert the runlist @src before element @loc in the runlist @dst. Merge the
 265  * left end of the new runlist, if necessary. Adjust the size of the hole
 266  * after the inserted runlist.
 267  *
 268  * It is up to the caller to serialize access to the runlists @dst and @src.
 269  *
 270  * On success, return a pointer to the new, combined, runlist. Note, both
 271  * runlists @dst and @src are deallocated before returning so you cannot use
 272  * the pointers for anything any more. (Strictly speaking the returned runlist
 273  * may be the same as @dst but this is irrelevant.)
 274  *
 275  * On error, return -errno. Both runlists are left unmodified. The following
 276  * error codes are defined:
 277  *      -ENOMEM - Not enough memory to allocate runlist array.
 278  *      -EINVAL - Invalid parameters were passed in.
 279  */
 280 static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
 281                 int dsize, runlist_element *src, int ssize, int loc)
 282 {
 283         BOOL left = FALSE;      /* Left end of @src needs merging. */
 284         BOOL disc = FALSE;      /* Discontinuity between @dst and @src. */
 285         int marker;             /* End of the inserted runs. */
 286
 287         BUG_ON(!dst);
 288         BUG_ON(!src);
 289
 290         /*
 291          * disc => Discontinuity between the end of @dst and the start of @src.
 292          *         This means we might need to insert a "not mapped" run.
 293          */
 294         if (loc == 0)
 295                 disc = (src[0].vcn > 0);
 296         else {
 297                 s64 merged_length;
 298
 299                 left = ntfs_are_rl_mergeable(dst + loc - 1, src);
 300
 301                 merged_length = dst[loc - 1].length;
 302                 if (left)
 303                         merged_length += src->length;
 304
 305                 disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
 306         }
 307         /*
 308          * Space required: @dst size + @src size, less one if we merged, plus
 309          * one if there was a discontinuity.
 310          */
 311         dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
 312         if (IS_ERR(dst))
 313                 return dst;
 314         /*
 315          * We are guaranteed to succeed from here so can start modifying the
 316          * original runlist.
 317          */
 318         if (left)
 319                 __ntfs_rl_merge(dst + loc - 1, src);
 320         /*
 321          * First run after the @src runs that have been inserted.
 322          * Nominally,  @marker equals @loc + @ssize, i.e. location + number of
 323          * runs in @src.  However, if @left, then the first run in @src has
 324          * been merged with one in @dst.  And if @disc, then @dst and @src do
 325          * not meet and we need an extra run to fill the gap.
 326          */
 327         marker = loc + ssize - left + disc;
 328
 329         /* Move the tail of @dst out of the way, then copy in @src. */
 330         ntfs_rl_mm(dst, marker, loc, dsize - loc);
 331         ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
 332
 333         /* Adjust the VCN of the first run after the insertion... */
 334         dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
 335         /* ... and the length. */
 336         if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
 337                 dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;
 338
 339         /* Writing beyond the end of the file and there is a discontinuity. */
 340         if (disc) {
 341                 if (loc > 0) {
 342                         dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
 343                         dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
 344                 } else {
 345                         dst[loc].vcn = 0;
 346                         dst[loc].length = dst[loc + 1].vcn;
 347                 }
 348                 dst[loc].lcn = LCN_RL_NOT_MAPPED;
 349         }
 350         return dst;
 351 }
 352
 353 /**
 354  * ntfs_rl_replace - overwrite a runlist element with another runlist
 355  * @dst:        original runlist to be worked on
 356  * @dsize:      number of elements in @dst (including end marker)
 357  * @src:        new runlist to be inserted
 358  * @ssize:      number of elements in @src (excluding end marker)
 359  * @loc:        index in runlist @dst to overwrite with @src
 360  *
 361  * Replace the runlist element @dst at @loc with @src. Merge the left and
 362  * right ends of the inserted runlist, if necessary.
 363  *
 364  * It is up to the caller to serialize access to the runlists @dst and @src.
 365  *
 366  * On success, return a pointer to the new, combined, runlist. Note, both
 367  * runlists @dst and @src are deallocated before returning so you cannot use
 368  * the pointers for anything any more. (Strictly speaking the returned runlist
 369  * may be the same as @dst but this is irrelevant.)
 370  *
 371  * On error, return -errno. Both runlists are left unmodified. The following
 372  * error codes are defined:
 373  *      -ENOMEM - Not enough memory to allocate runlist array.
 374  *      -EINVAL - Invalid parameters were passed in.
 375  */
 376 static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
 377                 int dsize, runlist_element *src, int ssize, int loc)
 378 {
 379         BOOL left = FALSE;      /* Left end of @src needs merging. */
 380         BOOL right;             /* Right end of @src needs merging. */
 381         int tail;               /* Start of tail of @dst. */
 382         int marker;             /* End of the inserted runs. */
 383
 384         BUG_ON(!dst);
 385         BUG_ON(!src);
 386
 387         /* First, merge the left and right ends, if necessary. */
 388         right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
 389         if (loc > 0)
 390                 left = ntfs_are_rl_mergeable(dst + loc - 1, src);
 391         /*
 392          * Allocate some space.  We will need less if the left, right, or both
 393          * ends were merged.
 394          */
 395         dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left - right);
 396         if (IS_ERR(dst))
 397                 return dst;
 398         /*
 399          * We are guaranteed to succeed from here so can start modifying the
 400          * original runlists.
 401          */
 402         if (right)
 403                 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
 404         if (left)
 405                 __ntfs_rl_merge(dst + loc - 1, src);
 406         /*
 407          * First run of @dst that needs to be moved out of the way to make
 408          * space for the runs to be copied from @src, i.e. the first run of the
 409          * tail of @dst.
 410          */
 411         tail = loc + right + 1;
 412         /*
 413          * First run after the @src runs that have been inserted, i.e. where
 414          * the tail of @dst needs to be moved to.
 415          * Nominally, marker equals @loc + @ssize, i.e. location + number of
 416          * runs in @src).  However, if @left, then the first run in @src has
 417          * been merged with one in @dst.
 418          */
 419         marker = loc + ssize - left;
 420
 421         /* Move the tail of @dst out of the way, then copy in @src. */
 422         ntfs_rl_mm(dst, marker, tail, dsize - tail);
 423         ntfs_rl_mc(dst, loc, src, left, ssize - left);
 424
 425         /* We may have changed the length of the file, so fix the end marker. */
 426         if (dsize - tail > 0 && dst[marker].lcn == LCN_ENOENT)
 427                 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
 428         return dst;
 429 }
 430
 431 /**
 432  * ntfs_rl_split - insert a runlist into the centre of a hole
 433  * @dst:        original runlist to be worked on
 434  * @dsize:      number of elements in @dst (including end marker)
 435  * @src:        new runlist to be inserted
 436  * @ssize:      number of elements in @src (excluding end marker)
 437  * @loc:        index in runlist @dst at which to split and insert @src
 438  *
 439  * Split the runlist @dst at @loc into two and insert @new in between the two
 440  * fragments. No merging of runlists is necessary. Adjust the size of the
 441  * holes either side.
 442  *
 443  * It is up to the caller to serialize access to the runlists @dst and @src.
 444  *
 445  * On success, return a pointer to the new, combined, runlist. Note, both
 446  * runlists @dst and @src are deallocated before returning so you cannot use
 447  * the pointers for anything any more. (Strictly speaking the returned runlist
 448  * may be the same as @dst but this is irrelevant.)
 449  *
 450  * On error, return -errno. Both runlists are left unmodified. The following
 451  * error codes are defined:
 452  *      -ENOMEM - Not enough memory to allocate runlist array.
 453  *      -EINVAL - Invalid parameters were passed in.
 454  */
 455 static inline runlist_element *ntfs_rl_split(runlist_element *dst, int dsize,
 456                 runlist_element *src, int ssize, int loc)
 457 {
 458         BUG_ON(!dst);
 459         BUG_ON(!src);
 460
 461         /* Space required: @dst size + @src size + one new hole. */
 462         dst = ntfs_rl_realloc(dst, dsize, dsize + ssize + 1);
 463         if (IS_ERR(dst))
 464                 return dst;
 465         /*
 466          * We are guaranteed to succeed from here so can start modifying the
 467          * original runlists.
 468          */
 469
 470         /* Move the tail of @dst out of the way, then copy in @src. */
 471         ntfs_rl_mm(dst, loc + 1 + ssize, loc, dsize - loc);
 472         ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
 473
 474         /* Adjust the size of the holes either size of @src. */
 475         dst[loc].length         = dst[loc+1].vcn       - dst[loc].vcn;
 476         dst[loc+ssize+1].vcn    = dst[loc+ssize].vcn   + dst[loc+ssize].length;
 477         dst[loc+ssize+1].length = dst[loc+ssize+2].vcn - dst[loc+ssize+1].vcn;
 478
 479         return dst;
 480 }
 481
 482 /**
 483  * ntfs_runlists_merge - merge two runlists into one
 484  * @drl:        original runlist to be worked on
 485  * @srl:        new runlist to be merged into @drl
 486  *
 487  * First we sanity check the two runlists @srl and @drl to make sure that they
 488  * are sensible and can be merged. The runlist @srl must be either after the
 489  * runlist @drl or completely within a hole (or unmapped region) in @drl.
 490  *
 491  * It is up to the caller to serialize access to the runlists @drl and @srl.
 492  *
 493  * Merging of runlists is necessary in two cases:
 494  *   1. When attribute lists are used and a further extent is being mapped.
 495  *   2. When new clusters are allocated to fill a hole or extend a file.
 496  *
 497  * There are four possible ways @srl can be merged. It can:
 498  *      - be inserted at the beginning of a hole,
 499  *      - split the hole in two and be inserted between the two fragments,
 500  *      - be appended at the end of a hole, or it can
 501  *      - replace the whole hole.
 502  * It can also be appended to the end of the runlist, which is just a variant
 503  * of the insert case.
 504  *
 505  * On success, return a pointer to the new, combined, runlist. Note, both
 506  * runlists @drl and @srl are deallocated before returning so you cannot use
 507  * the pointers for anything any more. (Strictly speaking the returned runlist
 508  * may be the same as @dst but this is irrelevant.)
 509  *
 510  * On error, return -errno. Both runlists are left unmodified. The following
 511  * error codes are defined:
 512  *      -ENOMEM - Not enough memory to allocate runlist array.
 513  *      -EINVAL - Invalid parameters were passed in.
 514  *      -ERANGE - The runlists overlap and cannot be merged.
 515  */
 516 runlist_element *ntfs_runlists_merge(runlist_element *drl,
 517                 runlist_element *srl)
 518 {
 519         int di, si;             /* Current index into @[ds]rl. */
 520         int sstart;             /* First index with lcn > LCN_RL_NOT_MAPPED. */
 521         int dins;               /* Index into @drl at which to insert @srl. */
 522         int dend, send;         /* Last index into @[ds]rl. */
 523         int dfinal, sfinal;     /* The last index into @[ds]rl with
 524                                    lcn >= LCN_HOLE. */
 525         int marker = 0;
 526         VCN marker_vcn = 0;
 527
 528 #ifdef DEBUG
 529         ntfs_debug("dst:");
 530         ntfs_debug_dump_runlist(drl);
 531         ntfs_debug("src:");
 532         ntfs_debug_dump_runlist(srl);
 533 #endif
 534
 535         /* Check for silly calling... */
 536         if (unlikely(!srl))
 537                 return drl;
 538         if (IS_ERR(srl) || IS_ERR(drl))
 539                 return ERR_PTR(-EINVAL);
 540
 541         /* Check for the case where the first mapping is being done now. */
 542         if (unlikely(!drl)) {
 543                 drl = srl;
 544                 /* Complete the source runlist if necessary. */
 545                 if (unlikely(drl[0].vcn)) {
 546                         /* Scan to the end of the source runlist. */
 547                         for (dend = 0; likely(drl[dend].length); dend++)
 548                                 ;
 549                         dend++;
 550                         drl = ntfs_rl_realloc(drl, dend, dend + 1);
 551                         if (IS_ERR(drl))
 552                                 return drl;
 553                         /* Insert start element at the front of the runlist. */
 554                         ntfs_rl_mm(drl, 1, 0, dend);
 555                         drl[0].vcn = 0;
 556                         drl[0].lcn = LCN_RL_NOT_MAPPED;
 557                         drl[0].length = drl[1].vcn;
 558                 }
 559                 goto finished;
 560         }
 561
 562         si = di = 0;
 563
 564         /* Skip any unmapped start element(s) in the source runlist. */
 565         while (srl[si].length && srl[si].lcn < LCN_HOLE)
 566                 si++;
 567
 568         /* Can't have an entirely unmapped source runlist. */
 569         BUG_ON(!srl[si].length);
 570
 571         /* Record the starting points. */
 572         sstart = si;
 573
 574         /*
 575          * Skip forward in @drl until we reach the position where @srl needs to
 576          * be inserted. If we reach the end of @drl, @srl just needs to be
 577          * appended to @drl.
 578          */
 579         for (; drl[di].length; di++) {
 580                 if (drl[di].vcn + drl[di].length > srl[sstart].vcn)
 581                         break;
 582         }
 583         dins = di;
 584
 585         /* Sanity check for illegal overlaps. */
 586         if ((drl[di].vcn == srl[si].vcn) && (drl[di].lcn >= 0) &&
 587                         (srl[si].lcn >= 0)) {
 588                 ntfs_error(NULL, "Run lists overlap. Cannot merge!");
 589                 return ERR_PTR(-ERANGE);
 590         }
 591
 592         /* Scan to the end of both runlists in order to know their sizes. */
 593         for (send = si; srl[send].length; send++)
 594                 ;
 595         for (dend = di; drl[dend].length; dend++)
 596                 ;
 597
 598         if (srl[send].lcn == LCN_ENOENT)
 599                 marker_vcn = srl[marker = send].vcn;
 600
 601         /* Scan to the last element with lcn >= LCN_HOLE. */
 602         for (sfinal = send; sfinal >= 0 && srl[sfinal].lcn < LCN_HOLE; sfinal--)
 603                 ;
 604         for (dfinal = dend; dfinal >= 0 && drl[dfinal].lcn < LCN_HOLE; dfinal--)
 605                 ;
 606
 607         {
 608         BOOL start;
 609         BOOL finish;
 610         int ds = dend + 1;              /* Number of elements in drl & srl */
 611         int ss = sfinal - sstart + 1;
 612
 613         start  = ((drl[dins].lcn <  LCN_RL_NOT_MAPPED) ||    /* End of file   */
 614                   (drl[dins].vcn == srl[sstart].vcn));       /* Start of hole */
 615         finish = ((drl[dins].lcn >= LCN_RL_NOT_MAPPED) &&    /* End of file   */
 616                  ((drl[dins].vcn + drl[dins].length) <=      /* End of hole   */
 617                   (srl[send - 1].vcn + srl[send - 1].length)));
 618
 619         /* Or we will lose an end marker. */
 620         if (finish && !drl[dins].length)
 621                 ss++;
 622         if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn))
 623                 finish = FALSE;
 624 #if 0
 625         ntfs_debug("dfinal = %i, dend = %i", dfinal, dend);
 626         ntfs_debug("sstart = %i, sfinal = %i, send = %i", sstart, sfinal, send);
 627         ntfs_debug("start = %i, finish = %i", start, finish);
 628         ntfs_debug("ds = %i, ss = %i, dins = %i", ds, ss, dins);
 629 #endif
 630         if (start) {
 631                 if (finish)
 632                         drl = ntfs_rl_replace(drl, ds, srl + sstart, ss, dins);
 633                 else
 634                         drl = ntfs_rl_insert(drl, ds, srl + sstart, ss, dins);
 635         } else {
 636                 if (finish)
 637                         drl = ntfs_rl_append(drl, ds, srl + sstart, ss, dins);
 638                 else
 639                         drl = ntfs_rl_split(drl, ds, srl + sstart, ss, dins);
 640         }
 641         if (IS_ERR(drl)) {
 642                 ntfs_error(NULL, "Merge failed.");
 643                 return drl;
 644         }
 645         ntfs_free(srl);
 646         if (marker) {
 647                 ntfs_debug("Triggering marker code.");
 648                 for (ds = dend; drl[ds].length; ds++)
 649                         ;
 650                 /* We only need to care if @srl ended after @drl. */
 651                 if (drl[ds].vcn <= marker_vcn) {
 652                         int slots = 0;
 653
 654                         if (drl[ds].vcn == marker_vcn) {
 655                                 ntfs_debug("Old marker = 0x%llx, replacing "
 656                                                 "with LCN_ENOENT.",
 657                                                 (unsigned long long)
 658                                                 drl[ds].lcn);
 659                                 drl[ds].lcn = LCN_ENOENT;
 660                                 goto finished;
 661                         }
 662                         /*
 663                          * We need to create an unmapped runlist element in
 664                          * @drl or extend an existing one before adding the
 665                          * ENOENT terminator.
 666                          */
 667                         if (drl[ds].lcn == LCN_ENOENT) {
 668                                 ds--;
 669                                 slots = 1;
 670                         }
 671                         if (drl[ds].lcn != LCN_RL_NOT_MAPPED) {
 672                                 /* Add an unmapped runlist element. */
 673                                 if (!slots) {
 674                                         drl = ntfs_rl_realloc_nofail(drl, ds,
 675                                                         ds + 2);
 676                                         slots = 2;
 677                                 }
 678                                 ds++;
 679                                 /* Need to set vcn if it isn't set already. */
 680                                 if (slots != 1)
 681                                         drl[ds].vcn = drl[ds - 1].vcn +
 682                                                         drl[ds - 1].length;
 683                                 drl[ds].lcn = LCN_RL_NOT_MAPPED;
 684                                 /* We now used up a slot. */
 685                                 slots--;
 686                         }
 687                         drl[ds].length = marker_vcn - drl[ds].vcn;
 688                         /* Finally add the ENOENT terminator. */
 689                         ds++;
 690                         if (!slots)
 691                                 drl = ntfs_rl_realloc_nofail(drl, ds, ds + 1);
 692                         drl[ds].vcn = marker_vcn;
 693                         drl[ds].lcn = LCN_ENOENT;
 694                         drl[ds].length = (s64)0;
 695                 }
 696         }
 697         }
 698
 699 finished:
 700         /* The merge was completed successfully. */
 701         ntfs_debug("Merged runlist:");
 702         ntfs_debug_dump_runlist(drl);
 703         return drl;
 704 }
 705
 706 /**
 707  * ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist
 708  * @vol:        ntfs volume on which the attribute resides
 709  * @attr:       attribute record whose mapping pairs array to decompress
 710  * @old_rl:     optional runlist in which to insert @attr's runlist
 711  *
 712  * It is up to the caller to serialize access to the runlist @old_rl.
 713  *
 714  * Decompress the attribute @attr's mapping pairs array into a runlist. On
 715  * success, return the decompressed runlist.
 716  *
 717  * If @old_rl is not NULL, decompressed runlist is inserted into the
 718  * appropriate place in @old_rl and the resultant, combined runlist is
 719  * returned. The original @old_rl is deallocated.
 720  *
 721  * On error, return -errno. @old_rl is left unmodified in that case.
 722  *
 723  * The following error codes are defined:
 724  *      -ENOMEM - Not enough memory to allocate runlist array.
 725  *      -EIO    - Corrupt runlist.
 726  *      -EINVAL - Invalid parameters were passed in.
 727  *      -ERANGE - The two runlists overlap.
 728  *
 729  * FIXME: For now we take the conceptionally simplest approach of creating the
 730  * new runlist disregarding the already existing one and then splicing the
 731  * two into one, if that is possible (we check for overlap and discard the new
 732  * runlist if overlap present before returning ERR_PTR(-ERANGE)).
 733  */
 734 runlist_element *ntfs_mapping_pairs_decompress(const ntfs_volume *vol,
 735                 const ATTR_RECORD *attr, runlist_element *old_rl)
 736 {
 737         VCN vcn;                /* Current vcn. */
 738         LCN lcn;                /* Current lcn. */
 739         s64 deltaxcn;           /* Change in [vl]cn. */
 740         runlist_element *rl;    /* The output runlist. */
 741         u8 *buf;                /* Current position in mapping pairs array. */
 742         u8 *attr_end;           /* End of attribute. */
 743         int rlsize;             /* Size of runlist buffer. */
 744         u16 rlpos;              /* Current runlist position in units of
 745                                    runlist_elements. */
 746         u8 b;                   /* Current byte offset in buf. */
 747
 748 #ifdef DEBUG
 749         /* Make sure attr exists and is non-resident. */
 750         if (!attr || !attr->non_resident || sle64_to_cpu(
 751                         attr->data.non_resident.lowest_vcn) < (VCN)0) {
 752                 ntfs_error(vol->sb, "Invalid arguments.");
 753                 return ERR_PTR(-EINVAL);
 754         }
 755 #endif
 756         /* Start at vcn = lowest_vcn and lcn 0. */
 757         vcn = sle64_to_cpu(attr->data.non_resident.lowest_vcn);
 758         lcn = 0;
 759         /* Get start of the mapping pairs array. */
 760         buf = (u8*)attr + le16_to_cpu(
 761                         attr->data.non_resident.mapping_pairs_offset);
 762         attr_end = (u8*)attr + le32_to_cpu(attr->length);
 763         if (unlikely(buf < (u8*)attr || buf > attr_end)) {
 764                 ntfs_error(vol->sb, "Corrupt attribute.");
 765                 return ERR_PTR(-EIO);
 766         }
 767         /* If the mapping pairs array is valid but empty, nothing to do. */
 768         if (!vcn && !*buf)
 769                 return old_rl;
 770         /* Current position in runlist array. */
 771         rlpos = 0;
 772         /* Allocate first page and set current runlist size to one page. */
 773         rl = ntfs_malloc_nofs(rlsize = PAGE_SIZE);
 774         if (unlikely(!rl))
 775                 return ERR_PTR(-ENOMEM);
 776         /* Insert unmapped starting element if necessary. */
 777         if (vcn) {
 778                 rl->vcn = 0;
 779                 rl->lcn = LCN_RL_NOT_MAPPED;
 780                 rl->length = vcn;
 781                 rlpos++;
 782         }
 783         while (buf < attr_end && *buf) {
 784                 /*
 785                  * Allocate more memory if needed, including space for the
 786                  * not-mapped and terminator elements. ntfs_malloc_nofs()
 787                  * operates on whole pages only.
 788                  */
 789                 if (((rlpos + 3) * sizeof(*old_rl)) > rlsize) {
 790                         runlist_element *rl2;
 791
 792                         rl2 = ntfs_malloc_nofs(rlsize + (int)PAGE_SIZE);
 793                         if (unlikely(!rl2)) {
 794                                 ntfs_free(rl);
 795                                 return ERR_PTR(-ENOMEM);
 796                         }
 797                         memcpy(rl2, rl, rlsize);
 798                         ntfs_free(rl);
 799                         rl = rl2;
 800                         rlsize += PAGE_SIZE;
 801                 }
 802                 /* Enter the current vcn into the current runlist element. */
 803                 rl[rlpos].vcn = vcn;
 804                 /*
 805                  * Get the change in vcn, i.e. the run length in clusters.
 806                  * Doing it this way ensures that we signextend negative values.
 807                  * A negative run length doesn't make any sense, but hey, I
 808                  * didn't make up the NTFS specs and Windows NT4 treats the run
 809                  * length as a signed value so that's how it is...
 810                  */
 811                 b = *buf & 0xf;
 812                 if (b) {
 813                         if (unlikely(buf + b > attr_end))
 814                                 goto io_error;
 815                         for (deltaxcn = (s8)buf[b--]; b; b--)
 816                                 deltaxcn = (deltaxcn << 8) + buf[b];
 817                 } else { /* The length entry is compulsory. */
 818                         ntfs_error(vol->sb, "Missing length entry in mapping "
 819                                         "pairs array.");
 820                         deltaxcn = (s64)-1;
 821                 }
 822                 /*
 823                  * Assume a negative length to indicate data corruption and
 824                  * hence clean-up and return NULL.
 825                  */
 826                 if (unlikely(deltaxcn < 0)) {
 827                         ntfs_error(vol->sb, "Invalid length in mapping pairs "
 828                                         "array.");
 829                         goto err_out;
 830                 }
 831                 /*
 832                  * Enter the current run length into the current runlist
 833                  * element.
 834                  */
 835                 rl[rlpos].length = deltaxcn;
 836                 /* Increment the current vcn by the current run length. */
 837                 vcn += deltaxcn;
 838                 /*
 839                  * There might be no lcn change at all, as is the case for
 840                  * sparse clusters on NTFS 3.0+, in which case we set the lcn
 841                  * to LCN_HOLE.
 842                  */
 843                 if (!(*buf & 0xf0))
 844                         rl[rlpos].lcn = LCN_HOLE;
 845                 else {
 846                         /* Get the lcn change which really can be negative. */
 847                         u8 b2 = *buf & 0xf;
 848                         b = b2 + ((*buf >> 4) & 0xf);
 849                         if (buf + b > attr_end)
 850                                 goto io_error;
 851                         for (deltaxcn = (s8)buf[b--]; b > b2; b--)
 852                                 deltaxcn = (deltaxcn << 8) + buf[b];
 853                         /* Change the current lcn to its new value. */
 854                         lcn += deltaxcn;
 855 #ifdef DEBUG
 856                         /*
 857                          * On NTFS 1.2-, apparently can have lcn == -1 to
 858                          * indicate a hole. But we haven't verified ourselves
 859                          * whether it is really the lcn or the deltaxcn that is
 860                          * -1. So if either is found give us a message so we
 861                          * can investigate it further!
 862                          */
 863                         if (vol->major_ver < 3) {
 864                                 if (unlikely(deltaxcn == (LCN)-1))
 865                                         ntfs_error(vol->sb, "lcn delta == -1");
 866                                 if (unlikely(lcn == (LCN)-1))
 867                                         ntfs_error(vol->sb, "lcn == -1");
 868                         }
 869 #endif
 870                         /* Check lcn is not below -1. */
 871                         if (unlikely(lcn < (LCN)-1)) {
 872                                 ntfs_error(vol->sb, "Invalid LCN < -1 in "
 873                                                 "mapping pairs array.");
 874                                 goto err_out;
 875                         }
 876                         /* Enter the current lcn into the runlist element. */
 877                         rl[rlpos].lcn = lcn;
 878                 }
 879                 /* Get to the next runlist element. */
 880                 rlpos++;
 881                 /* Increment the buffer position to the next mapping pair. */
 882                 buf += (*buf & 0xf) + ((*buf >> 4) & 0xf) + 1;
 883         }
 884         if (unlikely(buf >= attr_end))
 885                 goto io_error;
 886         /*
 887          * If there is a highest_vcn specified, it must be equal to the final
 888          * vcn in the runlist - 1, or something has gone badly wrong.
 889          */
 890         deltaxcn = sle64_to_cpu(attr->data.non_resident.highest_vcn);
 891         if (unlikely(deltaxcn && vcn - 1 != deltaxcn)) {
 892 mpa_err:
 893                 ntfs_error(vol->sb, "Corrupt mapping pairs array in "
 894                                 "non-resident attribute.");
 895                 goto err_out;
 896         }
 897         /* Setup not mapped runlist element if this is the base extent. */
 898         if (!attr->data.non_resident.lowest_vcn) {
 899                 VCN max_cluster;
 900
 901                 max_cluster = ((sle64_to_cpu(
 902                                 attr->data.non_resident.allocated_size) +
 903                                 vol->cluster_size - 1) >>
 904                                 vol->cluster_size_bits) - 1;
 905                 /*
 906                  * A highest_vcn of zero means this is a single extent
 907                  * attribute so simply terminate the runlist with LCN_ENOENT).
 908                  */
 909                 if (deltaxcn) {
 910                         /*
 911                          * If there is a difference between the highest_vcn and
 912                          * the highest cluster, the runlist is either corrupt
 913                          * or, more likely, there are more extents following
 914                          * this one.
 915                          */
 916                         if (deltaxcn < max_cluster) {
 917                                 ntfs_debug("More extents to follow; deltaxcn "
 918                                                 "= 0x%llx, max_cluster = "
 919                                                 "0x%llx",
 920                                                 (unsigned long long)deltaxcn,
 921                                                 (unsigned long long)
 922                                                 max_cluster);
 923                                 rl[rlpos].vcn = vcn;
 924                                 vcn += rl[rlpos].length = max_cluster -
 925                                                 deltaxcn;
 926                                 rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
 927                                 rlpos++;
 928                         } else if (unlikely(deltaxcn > max_cluster)) {
 929                                 ntfs_error(vol->sb, "Corrupt attribute.  "
 930                                                 "deltaxcn = 0x%llx, "
 931                                                 "max_cluster = 0x%llx",
 932                                                 (unsigned long long)deltaxcn,
 933                                                 (unsigned long long)
 934                                                 max_cluster);
 935                                 goto mpa_err;
 936                         }
 937                 }
 938                 rl[rlpos].lcn = LCN_ENOENT;
 939         } else /* Not the base extent. There may be more extents to follow. */
 940                 rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
 941
 942         /* Setup terminating runlist element. */
 943         rl[rlpos].vcn = vcn;
 944         rl[rlpos].length = (s64)0;
 945         /* If no existing runlist was specified, we are done. */
 946         if (!old_rl) {
 947                 ntfs_debug("Mapping pairs array successfully decompressed:");
 948                 ntfs_debug_dump_runlist(rl);
 949                 return rl;
 950         }
 951         /* Now combine the new and old runlists checking for overlaps. */
 952         old_rl = ntfs_runlists_merge(old_rl, rl);
 953         if (likely(!IS_ERR(old_rl)))
 954                 return old_rl;
 955         ntfs_free(rl);
 956         ntfs_error(vol->sb, "Failed to merge runlists.");
 957         return old_rl;
 958 io_error:
 959         ntfs_error(vol->sb, "Corrupt attribute.");
 960 err_out:
 961         ntfs_free(rl);
 962         return ERR_PTR(-EIO);
 963 }
 964
 965 /**
 966  * ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist
 967  * @rl:         runlist to use for conversion
 968  * @vcn:        vcn to convert
 969  *
 970  * Convert the virtual cluster number @vcn of an attribute into a logical
 971  * cluster number (lcn) of a device using the runlist @rl to map vcns to their
 972  * corresponding lcns.
 973  *
 974  * It is up to the caller to serialize access to the runlist @rl.
 975  *
 976  * Since lcns must be >= 0, we use negative return codes with special meaning:
 977  *
 978  * Return code          Meaning / Description
 979  * ==================================================
 980  *  LCN_HOLE            Hole / not allocated on disk.
 981  *  LCN_RL_NOT_MAPPED   This is part of the runlist which has not been
 982  *                      inserted into the runlist yet.
 983  *  LCN_ENOENT          There is no such vcn in the attribute.
 984  *
 985  * Locking: - The caller must have locked the runlist (for reading or writing).
 986  *          - This function does not touch the lock, nor does it modify the
 987  *            runlist.
 988  */
 989 LCN ntfs_rl_vcn_to_lcn(const runlist_element *rl, const VCN vcn)
 990 {
 991         int i;
 992
 993         BUG_ON(vcn < 0);
 994         /*
 995          * If rl is NULL, assume that we have found an unmapped runlist. The
 996          * caller can then attempt to map it and fail appropriately if
 997          * necessary.
 998          */
 999         if (unlikely(!rl))
1000                 return LCN_RL_NOT_MAPPED;
1001
1002         /* Catch out of lower bounds vcn. */
1003         if (unlikely(vcn < rl[0].vcn))
1004                 return LCN_ENOENT;
1005
1006         for (i = 0; likely(rl[i].length); i++) {
1007                 if (unlikely(vcn < rl[i+1].vcn)) {
1008                         if (likely(rl[i].lcn >= (LCN)0))
1009                                 return rl[i].lcn + (vcn - rl[i].vcn);
1010                         return rl[i].lcn;
1011                 }
1012         }
1013         /*
1014          * The terminator element is setup to the correct value, i.e. one of
1015          * LCN_HOLE, LCN_RL_NOT_MAPPED, or LCN_ENOENT.
1016          */
1017         if (likely(rl[i].lcn < (LCN)0))
1018                 return rl[i].lcn;
1019         /* Just in case... We could replace this with BUG() some day. */
1020         return LCN_ENOENT;
1021 }
1022
1023 #ifdef NTFS_RW
1024
1025 /**
1026  * ntfs_rl_find_vcn_nolock - find a vcn in a runlist
1027  * @rl:         runlist to search
1028  * @vcn:        vcn to find
1029  *
1030  * Find the virtual cluster number @vcn in the runlist @rl and return the
1031  * address of the runlist element containing the @vcn on success.
1032  *
1033  * Return NULL if @rl is NULL or @vcn is in an unmapped part/out of bounds of
1034  * the runlist.
1035  *
1036  * Locking: The runlist must be locked on entry.
1037  */
1038 runlist_element *ntfs_rl_find_vcn_nolock(runlist_element *rl, const VCN vcn)
1039 {
1040         BUG_ON(vcn < 0);
1041         if (unlikely(!rl || vcn < rl[0].vcn))
1042                 return NULL;
1043         while (likely(rl->length)) {
1044                 if (unlikely(vcn < rl[1].vcn)) {
1045                         if (likely(rl->lcn >= LCN_HOLE))
1046                                 return rl;
1047                         return NULL;
1048                 }
1049                 rl++;
1050         }
1051         if (likely(rl->lcn == LCN_ENOENT))
1052                 return rl;
1053         return NULL;
1054 }
1055
1056 /**
1057  * ntfs_get_nr_significant_bytes - get number of bytes needed to store a number
1058  * @n:          number for which to get the number of bytes for
1059  *
1060  * Return the number of bytes required to store @n unambiguously as
1061  * a signed number.
1062  *
1063  * This is used in the context of the mapping pairs array to determine how
1064  * many bytes will be needed in the array to store a given logical cluster
1065  * number (lcn) or a specific run length.
1066  *
1067  * Return the number of bytes written.  This function cannot fail.
1068  */
1069 static inline int ntfs_get_nr_significant_bytes(const s64 n)
1070 {
1071         s64 l = n;
1072         int i;
1073         s8 j;
1074
1075         i = 0;
1076         do {
1077                 l >>= 8;
1078                 i++;
1079         } while (l != 0 && l != -1);
1080         j = (n >> 8 * (i - 1)) & 0xff;
1081         /* If the sign bit is wrong, we need an extra byte. */
1082         if ((n < 0 && j >= 0) || (n > 0 && j < 0))
1083                 i++;
1084         return i;
1085 }
1086
1087 /**
1088  * ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array
1089  * @vol:        ntfs volume (needed for the ntfs version)
1090  * @rl:         locked runlist to determine the size of the mapping pairs of
1091  * @first_vcn:  first vcn which to include in the mapping pairs array
1092  * @last_vcn:   last vcn which to include in the mapping pairs array
1093  *
1094  * Walk the locked runlist @rl and calculate the size in bytes of the mapping
1095  * pairs array corresponding to the runlist @rl, starting at vcn @first_vcn and
1096  * finishing with vcn @last_vcn.
1097  *
1098  * A @last_vcn of -1 means end of runlist and in that case the size of the
1099  * mapping pairs array corresponding to the runlist starting at vcn @first_vcn
1100  * and finishing at the end of the runlist is determined.
1101  *
1102  * This for example allows us to allocate a buffer of the right size when
1103  * building the mapping pairs array.
1104  *
1105  * If @rl is NULL, just return 1 (for the single terminator byte).
1106  *
1107  * Return the calculated size in bytes on success.  On error, return -errno.
1108  * The following error codes are defined:
1109  *      -EINVAL - Run list contains unmapped elements.  Make sure to only pass
1110  *                fully mapped runlists to this function.
1111  *      -EIO    - The runlist is corrupt.
1112  *
1113  * Locking: @rl must be locked on entry (either for reading or writing), it
1114  *          remains locked throughout, and is left locked upon return.
1115  */
1116 int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol,
1117                 const runlist_element *rl, const VCN first_vcn,
1118                 const VCN last_vcn)
1119 {
1120         LCN prev_lcn;
1121         int rls;
1122         BOOL the_end = FALSE;
1123
1124         BUG_ON(first_vcn < 0);
1125         BUG_ON(last_vcn < -1);
1126         BUG_ON(last_vcn >= 0 && first_vcn > last_vcn);
1127         if (!rl) {
1128                 BUG_ON(first_vcn);
1129                 BUG_ON(last_vcn > 0);
1130                 return 1;
1131         }
1132         /* Skip to runlist element containing @first_vcn. */
1133         while (rl->length && first_vcn >= rl[1].vcn)
1134                 rl++;
1135         if (unlikely((!rl->length && first_vcn > rl->vcn) ||
1136                         first_vcn < rl->vcn))
1137                 return -EINVAL;
1138         prev_lcn = 0;
1139         /* Always need the termining zero byte. */
1140         rls = 1;
1141         /* Do the first partial run if present. */
1142         if (first_vcn > rl->vcn) {
1143                 s64 delta, length = rl->length;
1144
1145                 /* We know rl->length != 0 already. */
1146                 if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
1147                         goto err_out;
1148                 /*
1149                  * If @stop_vcn is given and finishes inside this run, cap the
1150                  * run length.
1151                  */
1152                 if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
1153                         s64 s1 = last_vcn + 1;
1154                         if (unlikely(rl[1].vcn > s1))
1155                                 length = s1 - rl->vcn;
1156                         the_end = TRUE;
1157                 }
1158                 delta = first_vcn - rl->vcn;
1159                 /* Header byte + length. */
1160                 rls += 1 + ntfs_get_nr_significant_bytes(length - delta);
1161                 /*
1162                  * If the logical cluster number (lcn) denotes a hole and we
1163                  * are on NTFS 3.0+, we don't store it at all, i.e. we need
1164                  * zero space.  On earlier NTFS versions we just store the lcn.
1165                  * Note: this assumes that on NTFS 1.2-, holes are stored with
1166                  * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
1167                  */
1168                 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
1169                         prev_lcn = rl->lcn;
1170                         if (likely(rl->lcn >= 0))
1171                                 prev_lcn += delta;
1172                         /* Change in lcn. */
1173                         rls += ntfs_get_nr_significant_bytes(prev_lcn);
1174                 }
1175                 /* Go to next runlist element. */
1176                 rl++;
1177         }
1178         /* Do the full runs. */
1179         for (; rl->length && !the_end; rl++) {
1180                 s64 length = rl->length;
1181
1182                 if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
1183                         goto err_out;
1184                 /*
1185                  * If @stop_vcn is given and finishes inside this run, cap the
1186                  * run length.
1187                  */
1188                 if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
1189                         s64 s1 = last_vcn + 1;
1190                         if (unlikely(rl[1].vcn > s1))
1191                                 length = s1 - rl->vcn;
1192                         the_end = TRUE;
1193                 }
1194                 /* Header byte + length. */
1195                 rls += 1 + ntfs_get_nr_significant_bytes(length);
1196                 /*
1197                  * If the logical cluster number (lcn) denotes a hole and we
1198                  * are on NTFS 3.0+, we don't store it at all, i.e. we need
1199                  * zero space.  On earlier NTFS versions we just store the lcn.
1200                  * Note: this assumes that on NTFS 1.2-, holes are stored with
1201                  * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
1202                  */
1203                 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
1204                         /* Change in lcn. */
1205                         rls += ntfs_get_nr_significant_bytes(rl->lcn -
1206                                         prev_lcn);
1207                         prev_lcn = rl->lcn;
1208                 }
1209         }
1210         return rls;
1211 err_out:
1212         if (rl->lcn == LCN_RL_NOT_MAPPED)
1213                 rls = -EINVAL;
1214         else
1215                 rls = -EIO;
1216         return rls;
1217 }
1218
1219 /**
1220  * ntfs_write_significant_bytes - write the significant bytes of a number
1221  * @dst:        destination buffer to write to
1222  * @dst_max:    pointer to last byte of destination buffer for bounds checking
1223  * @n:          number whose significant bytes to write
1224  *
1225  * Store in @dst, the minimum bytes of the number @n which are required to
1226  * identify @n unambiguously as a signed number, taking care not to exceed
1227  * @dest_max, the maximum position within @dst to which we are allowed to
1228  * write.
1229  *
1230  * This is used when building the mapping pairs array of a runlist to compress
1231  * a given logical cluster number (lcn) or a specific run length to the minumum
1232  * size possible.
1233  *
1234  * Return the number of bytes written on success.  On error, i.e. the
1235  * destination buffer @dst is too small, return -ENOSPC.
1236  */
1237 static inline int ntfs_write_significant_bytes(s8 *dst, const s8 *dst_max,
1238                 const s64 n)
1239 {
1240         s64 l = n;
1241         int i;
1242         s8 j;
1243
1244         i = 0;
1245         do {
1246                 if (unlikely(dst > dst_max))
1247                         goto err_out;
1248                 *dst++ = l & 0xffll;
1249                 l >>= 8;
1250                 i++;
1251         } while (l != 0 && l != -1);
1252         j = (n >> 8 * (i - 1)) & 0xff;
1253         /* If the sign bit is wrong, we need an extra byte. */
1254         if (n < 0 && j >= 0) {
1255                 if (unlikely(dst > dst_max))
1256                         goto err_out;
1257                 i++;
1258                 *dst = (s8)-1;
1259         } else if (n > 0 && j < 0) {
1260                 if (unlikely(dst > dst_max))
1261                         goto err_out;
1262                 i++;
1263                 *dst = (s8)0;
1264         }
1265         return i;
1266 err_out:
1267         return -ENOSPC;
1268 }
1269
1270 /**
1271  * ntfs_mapping_pairs_build - build the mapping pairs array from a runlist
1272  * @vol:        ntfs volume (needed for the ntfs version)
1273  * @dst:        destination buffer to which to write the mapping pairs array
1274  * @dst_len:    size of destination buffer @dst in bytes
1275  * @rl:         locked runlist for which to build the mapping pairs array
1276  * @first_vcn:  first vcn which to include in the mapping pairs array
1277  * @last_vcn:   last vcn which to include in the mapping pairs array
1278  * @stop_vcn:   first vcn outside destination buffer on success or -ENOSPC
1279  *
1280  * Create the mapping pairs array from the locked runlist @rl, starting at vcn
1281  * @first_vcn and finishing with vcn @last_vcn and save the array in @dst.
1282  * @dst_len is the size of @dst in bytes and it should be at least equal to the
1283  * value obtained by calling ntfs_get_size_for_mapping_pairs().
1284  *
1285  * A @last_vcn of -1 means end of runlist and in that case the mapping pairs
1286  * array corresponding to the runlist starting at vcn @first_vcn and finishing
1287  * at the end of the runlist is created.
1288  *
1289  * If @rl is NULL, just write a single terminator byte to @dst.
1290  *
1291  * On success or -ENOSPC error, if @stop_vcn is not NULL, *@stop_vcn is set to
1292  * the first vcn outside the destination buffer.  Note that on error, @dst has
1293  * been filled with all the mapping pairs that will fit, thus it can be treated
1294  * as partial success, in that a new attribute extent needs to be created or
1295  * the next extent has to be used and the mapping pairs build has to be
1296  * continued with @first_vcn set to *@stop_vcn.
1297  *
1298  * Return 0 on success and -errno on error.  The following error codes are
1299  * defined:
1300  *      -EINVAL - Run list contains unmapped elements.  Make sure to only pass
1301  *                fully mapped runlists to this function.
1302  *      -EIO    - The runlist is corrupt.
1303  *      -ENOSPC - The destination buffer is too small.
1304  *
1305  * Locking: @rl must be locked on entry (either for reading or writing), it
1306  *          remains locked throughout, and is left locked upon return.
1307  */
1308 int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst,
1309                 const int dst_len, const runlist_element *rl,
1310                 const VCN first_vcn, const VCN last_vcn, VCN *const stop_vcn)
1311 {
1312         LCN prev_lcn;
1313         s8 *dst_max, *dst_next;
1314         int err = -ENOSPC;
1315         BOOL the_end = FALSE;
1316         s8 len_len, lcn_len;
1317
1318         BUG_ON(first_vcn < 0);
1319         BUG_ON(last_vcn < -1);
1320         BUG_ON(last_vcn >= 0 && first_vcn > last_vcn);
1321         BUG_ON(dst_len < 1);
1322         if (!rl) {
1323                 BUG_ON(first_vcn);
1324                 BUG_ON(last_vcn > 0);
1325                 if (stop_vcn)
1326                         *stop_vcn = 0;
1327                 /* Terminator byte. */
1328                 *dst = 0;
1329                 return 0;
1330         }
1331         /* Skip to runlist element containing @first_vcn. */
1332         while (rl->length && first_vcn >= rl[1].vcn)
1333                 rl++;
1334         if (unlikely((!rl->length && first_vcn > rl->vcn) ||
1335                         first_vcn < rl->vcn))
1336                 return -EINVAL;
1337         /*
1338          * @dst_max is used for bounds checking in
1339          * ntfs_write_significant_bytes().
1340          */
1341         dst_max = dst + dst_len - 1;
1342         prev_lcn = 0;
1343         /* Do the first partial run if present. */
1344         if (first_vcn > rl->vcn) {
1345                 s64 delta, length = rl->length;
1346
1347                 /* We know rl->length != 0 already. */
1348                 if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
1349                         goto err_out;
1350                 /*
1351                  * If @stop_vcn is given and finishes inside this run, cap the
1352                  * run length.
1353                  */
1354                 if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
1355                         s64 s1 = last_vcn + 1;
1356                         if (unlikely(rl[1].vcn > s1))
1357                                 length = s1 - rl->vcn;
1358                         the_end = TRUE;
1359                 }
1360                 delta = first_vcn - rl->vcn;
1361                 /* Write length. */
1362                 len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1363                                 length - delta);
1364                 if (unlikely(len_len < 0))
1365                         goto size_err;
1366                 /*
1367                  * If the logical cluster number (lcn) denotes a hole and we
1368                  * are on NTFS 3.0+, we don't store it at all, i.e. we need
1369                  * zero space.  On earlier NTFS versions we just write the lcn
1370                  * change.  FIXME: Do we need to write the lcn change or just
1371                  * the lcn in that case?  Not sure as I have never seen this
1372                  * case on NT4. - We assume that we just need to write the lcn
1373                  * change until someone tells us otherwise... (AIA)
1374                  */
1375                 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
1376                         prev_lcn = rl->lcn;
1377                         if (likely(rl->lcn >= 0))
1378                                 prev_lcn += delta;
1379                         /* Write change in lcn. */
1380                         lcn_len = ntfs_write_significant_bytes(dst + 1 +
1381                                         len_len, dst_max, prev_lcn);
1382                         if (unlikely(lcn_len < 0))
1383                                 goto size_err;
1384                 } else
1385                         lcn_len = 0;
1386                 dst_next = dst + len_len + lcn_len + 1;
1387                 if (unlikely(dst_next > dst_max))
1388                         goto size_err;
1389                 /* Update header byte. */
1390                 *dst = lcn_len << 4 | len_len;
1391                 /* Position at next mapping pairs array element. */
1392                 dst = dst_next;
1393                 /* Go to next runlist element. */
1394                 rl++;
1395         }
1396         /* Do the full runs. */
1397         for (; rl->length && !the_end; rl++) {
1398                 s64 length = rl->length;
1399
1400                 if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
1401                         goto err_out;
1402                 /*
1403                  * If @stop_vcn is given and finishes inside this run, cap the
1404                  * run length.
1405                  */
1406                 if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
1407                         s64 s1 = last_vcn + 1;
1408                         if (unlikely(rl[1].vcn > s1))
1409                                 length = s1 - rl->vcn;
1410                         the_end = TRUE;
1411                 }
1412                 /* Write length. */
1413                 len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1414                                 length);
1415                 if (unlikely(len_len < 0))
1416                         goto size_err;
1417                 /*
1418                  * If the logical cluster number (lcn) denotes a hole and we
1419                  * are on NTFS 3.0+, we don't store it at all, i.e. we need
1420                  * zero space.  On earlier NTFS versions we just write the lcn
1421                  * change.  FIXME: Do we need to write the lcn change or just
1422                  * the lcn in that case?  Not sure as I have never seen this
1423                  * case on NT4. - We assume that we just need to write the lcn
1424                  * change until someone tells us otherwise... (AIA)
1425                  */
1426                 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
1427                         /* Write change in lcn. */
1428                         lcn_len = ntfs_write_significant_bytes(dst + 1 +
1429                                         len_len, dst_max, rl->lcn - prev_lcn);
1430                         if (unlikely(lcn_len < 0))
1431                                 goto size_err;
1432                         prev_lcn = rl->lcn;
1433                 } else
1434                         lcn_len = 0;
1435                 dst_next = dst + len_len + lcn_len + 1;
1436                 if (unlikely(dst_next > dst_max))
1437                         goto size_err;
1438                 /* Update header byte. */
1439                 *dst = lcn_len << 4 | len_len;
1440                 /* Position at next mapping pairs array element. */
1441                 dst = dst_next;
1442         }
1443         /* Success. */
1444         err = 0;
1445 size_err:
1446         /* Set stop vcn. */
1447         if (stop_vcn)
1448                 *stop_vcn = rl->vcn;
1449         /* Add terminator byte. */
1450         *dst = 0;
1451         return err;
1452 err_out:
1453         if (rl->lcn == LCN_RL_NOT_MAPPED)
1454                 err = -EINVAL;
1455         else
1456                 err = -EIO;
1457         return err;
1458 }
1459
1460 /**
1461  * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn
1462  * @vol:        ntfs volume (needed for error output)
1463  * @runlist:    runlist to truncate
1464  * @new_length: the new length of the runlist in VCNs
1465  *
1466  * Truncate the runlist described by @runlist as well as the memory buffer
1467  * holding the runlist elements to a length of @new_length VCNs.
1468  *
1469  * If @new_length lies within the runlist, the runlist elements with VCNs of
1470  * @new_length and above are discarded.  As a special case if @new_length is
1471  * zero, the runlist is discarded and set to NULL.
1472  *
1473  * If @new_length lies beyond the runlist, a sparse runlist element is added to
1474  * the end of the runlist @runlist or if the last runlist element is a sparse
1475  * one already, this is extended.
1476  *
1477  * Note, no checking is done for unmapped runlist elements.  It is assumed that
1478  * the caller has mapped any elements that need to be mapped already.
1479  *
1480  * Return 0 on success and -errno on error.
1481  *
1482  * Locking: The caller must hold @runlist->lock for writing.
1483  */
1484 int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist,
1485                 const s64 new_length)
1486 {
1487         runlist_element *rl;
1488         int old_size;
1489
1490         ntfs_debug("Entering for new_length 0x%llx.", (long long)new_length);
1491         BUG_ON(!runlist);
1492         BUG_ON(new_length < 0);
1493         rl = runlist->rl;
1494         if (!new_length) {
1495                 ntfs_debug("Freeing runlist.");
1496                 runlist->rl = NULL;
1497                 if (rl)
1498                         ntfs_free(rl);
1499                 return 0;
1500         }
1501         if (unlikely(!rl)) {
1502                 /*
1503                  * Create a runlist consisting of a sparse runlist element of
1504                  * length @new_length followed by a terminator runlist element.
1505                  */
1506                 rl = ntfs_malloc_nofs(PAGE_SIZE);
1507                 if (unlikely(!rl)) {
1508                         ntfs_error(vol->sb, "Not enough memory to allocate "
1509                                         "runlist element buffer.");
1510                         return -ENOMEM;
1511                 }
1512                 runlist->rl = rl;
1513                 rl[1].length = rl->vcn = 0;
1514                 rl->lcn = LCN_HOLE;
1515                 rl[1].vcn = rl->length = new_length;
1516                 rl[1].lcn = LCN_ENOENT;
1517                 return 0;
1518         }
1519         BUG_ON(new_length < rl->vcn);
1520         /* Find @new_length in the runlist. */
1521         while (likely(rl->length && new_length >= rl[1].vcn))
1522                 rl++;
1523         /*
1524          * If not at the end of the runlist we need to shrink it.
1525          * If at the end of the runlist we need to expand it.
1526          */
1527         if (rl->length) {
1528                 runlist_element *trl;
1529                 BOOL is_end;
1530
1531                 ntfs_debug("Shrinking runlist.");
1532                 /* Determine the runlist size. */
1533                 trl = rl + 1;
1534                 while (likely(trl->length))
1535                         trl++;
1536                 old_size = trl - runlist->rl + 1;
1537                 /* Truncate the run. */
1538                 rl->length = new_length - rl->vcn;
1539                 /*
1540                  * If a run was partially truncated, make the following runlist
1541                  * element a terminator.
1542                  */
1543                 is_end = FALSE;
1544                 if (rl->length) {
1545                         rl++;
1546                         if (!rl->length)
1547                                 is_end = TRUE;
1548                         rl->vcn = new_length;
1549                         rl->length = 0;
1550                 }
1551                 rl->lcn = LCN_ENOENT;
1552                 /* Reallocate memory if necessary. */
1553                 if (!is_end) {
1554                         int new_size = rl - runlist->rl + 1;
1555                         rl = ntfs_rl_realloc(runlist->rl, old_size, new_size);
1556                         if (IS_ERR(rl))
1557                                 ntfs_warning(vol->sb, "Failed to shrink "
1558                                                 "runlist buffer.  This just "
1559                                                 "wastes a bit of memory "
1560                                                 "temporarily so we ignore it "
1561                                                 "and return success.");
1562                         else
1563                                 runlist->rl = rl;
1564                 }
1565         } else if (likely(/* !rl->length && */ new_length > rl->vcn)) {
1566                 ntfs_debug("Expanding runlist.");
1567                 /*
1568                  * If there is a previous runlist element and it is a sparse
1569                  * one, extend it.  Otherwise need to add a new, sparse runlist
1570                  * element.
1571                  */
1572                 if ((rl > runlist->rl) && ((rl - 1)->lcn == LCN_HOLE))
1573                         (rl - 1)->length = new_length - (rl - 1)->vcn;
1574                 else {
1575                         /* Determine the runlist size. */
1576                         old_size = rl - runlist->rl + 1;
1577                         /* Reallocate memory if necessary. */
1578                         rl = ntfs_rl_realloc(runlist->rl, old_size,
1579                                         old_size + 1);
1580                         if (IS_ERR(rl)) {
1581                                 ntfs_error(vol->sb, "Failed to expand runlist "
1582                                                 "buffer, aborting.");
1583                                 return PTR_ERR(rl);
1584                         }
1585                         runlist->rl = rl;
1586                         /*
1587                          * Set @rl to the same runlist element in the new
1588                          * runlist as before in the old runlist.
1589                          */
1590                         rl += old_size - 1;
1591                         /* Add a new, sparse runlist element. */
1592                         rl->lcn = LCN_HOLE;
1593                         rl->length = new_length - rl->vcn;
1594                         /* Add a new terminator runlist element. */
1595                         rl++;
1596                         rl->length = 0;
1597                 }
1598                 rl->vcn = new_length;
1599                 rl->lcn = LCN_ENOENT;
1600         } else /* if (unlikely(!rl->length && new_length == rl->vcn)) */ {
1601                 /* Runlist already has same size as requested. */
1602                 rl->lcn = LCN_ENOENT;
1603         }
1604         ntfs_debug("Done.");
1605         return 0;
1606 }
1607
1608 /**
1609  * ntfs_rl_punch_nolock - punch a hole into a runlist
1610  * @vol:        ntfs volume (needed for error output)
1611  * @runlist:    runlist to punch a hole into
1612  * @start:      starting VCN of the hole to be created
1613  * @length:     size of the hole to be created in units of clusters
1614  *
1615  * Punch a hole into the runlist @runlist starting at VCN @start and of size
1616  * @length clusters.
1617  *
1618  * Return 0 on success and -errno on error, in which case @runlist has not been
1619  * modified.
1620  *
1621  * If @start and/or @start + @length are outside the runlist return error code
1622  * -ENOENT.
1623  *
1624  * If the runlist contains unmapped or error elements between @start and @start
1625  * + @length return error code -EINVAL.
1626  *
1627  * Locking: The caller must hold @runlist->lock for writing.
1628  */
1629 int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist,
1630                 const VCN start, const s64 length)
1631 {
1632         const VCN end = start + length;
1633         s64 delta;
1634         runlist_element *rl, *rl_end, *rl_real_end, *trl;
1635         int old_size;
1636         BOOL lcn_fixup = FALSE;
1637
1638         ntfs_debug("Entering for start 0x%llx, length 0x%llx.",
1639                         (long long)start, (long long)length);
1640         BUG_ON(!runlist);
1641         BUG_ON(start < 0);
1642         BUG_ON(length < 0);
1643         BUG_ON(end < 0);
1644         rl = runlist->rl;
1645         if (unlikely(!rl)) {
1646                 if (likely(!start && !length))
1647                         return 0;
1648                 return -ENOENT;
1649         }
1650         /* Find @start in the runlist. */
1651         while (likely(rl->length && start >= rl[1].vcn))
1652                 rl++;
1653         rl_end = rl;
1654         /* Find @end in the runlist. */
1655         while (likely(rl_end->length && end >= rl_end[1].vcn)) {
1656                 /* Verify there are no unmapped or error elements. */
1657                 if (unlikely(rl_end->lcn < LCN_HOLE))
1658                         return -EINVAL;
1659                 rl_end++;
1660         }
1661         /* Check the last element. */
1662         if (unlikely(rl_end->length && rl_end->lcn < LCN_HOLE))
1663                 return -EINVAL;
1664         /* This covers @start being out of bounds, too. */
1665         if (!rl_end->length && end > rl_end->vcn)
1666                 return -ENOENT;
1667         if (!length)
1668                 return 0;
1669         if (!rl->length)
1670                 return -ENOENT;
1671         rl_real_end = rl_end;
1672         /* Determine the runlist size. */
1673         while (likely(rl_real_end->length))
1674                 rl_real_end++;
1675         old_size = rl_real_end - runlist->rl + 1;
1676         /* If @start is in a hole simply extend the hole. */
1677         if (rl->lcn == LCN_HOLE) {
1678                 /*
1679                  * If both @start and @end are in the same sparse run, we are
1680                  * done.
1681                  */
1682                 if (end <= rl[1].vcn) {
1683                         ntfs_debug("Done (requested hole is already sparse).");
1684                         return 0;
1685                 }
1686 extend_hole:
1687                 /* Extend the hole. */
1688                 rl->length = end - rl->vcn;
1689                 /* If @end is in a hole, merge it with the current one. */
1690                 if (rl_end->lcn == LCN_HOLE) {
1691                         rl_end++;
1692                         rl->length = rl_end->vcn - rl->vcn;
1693                 }
1694                 /* We have done the hole.  Now deal with the remaining tail. */
1695                 rl++;
1696                 /* Cut out all runlist elements up to @end. */
1697                 if (rl < rl_end)
1698                         memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
1699                                         sizeof(*rl));
1700                 /* Adjust the beginning of the tail if necessary. */
1701                 if (end > rl->vcn) {
1702                         s64 delta = end - rl->vcn;
1703                         rl->vcn = end;
1704                         rl->length -= delta;
1705                         /* Only adjust the lcn if it is real. */
1706                         if (rl->lcn >= 0)
1707                                 rl->lcn += delta;
1708                 }
1709 shrink_allocation:
1710                 /* Reallocate memory if the allocation changed. */
1711                 if (rl < rl_end) {
1712                         rl = ntfs_rl_realloc(runlist->rl, old_size,
1713                                         old_size - (rl_end - rl));
1714                         if (IS_ERR(rl))
1715                                 ntfs_warning(vol->sb, "Failed to shrink "
1716                                                 "runlist buffer.  This just "
1717                                                 "wastes a bit of memory "
1718                                                 "temporarily so we ignore it "
1719                                                 "and return success.");
1720                         else
1721                                 runlist->rl = rl;
1722                 }
1723                 ntfs_debug("Done (extend hole).");
1724                 return 0;
1725         }
1726         /*
1727          * If @start is at the beginning of a run things are easier as there is
1728          * no need to split the first run.
1729          */
1730         if (start == rl->vcn) {
1731                 /*
1732                  * @start is at the beginning of a run.
1733                  *
1734                  * If the previous run is sparse, extend its hole.
1735                  *
1736                  * If @end is not in the same run, switch the run to be sparse
1737                  * and extend the newly created hole.
1738                  *
1739                  * Thus both of these cases reduce the problem to the above
1740                  * case of "@start is in a hole".
1741                  */
1742                 if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) {
1743                         rl--;
1744                         goto extend_hole;
1745                 }
1746                 if (end >= rl[1].vcn) {
1747                         rl->lcn = LCN_HOLE;
1748                         goto extend_hole;
1749                 }
1750                 /*
1751                  * The final case is when @end is in the same run as @start.
1752                  * For this need to split the run into two.  One run for the
1753                  * sparse region between the beginning of the old run, i.e.
1754                  * @start, and @end and one for the remaining non-sparse
1755                  * region, i.e. between @end and the end of the old run.
1756                  */
1757                 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
1758                 if (IS_ERR(trl))
1759                         goto enomem_out;
1760                 old_size++;
1761                 if (runlist->rl != trl) {
1762                         rl = trl + (rl - runlist->rl);
1763                         rl_end = trl + (rl_end - runlist->rl);
1764                         rl_real_end = trl + (rl_real_end - runlist->rl);
1765                         runlist->rl = trl;
1766                 }
1767 split_end:
1768                 /* Shift all the runs up by one. */
1769                 memmove(rl + 1, rl, (rl_real_end - rl + 1) * sizeof(*rl));
1770                 /* Finally, setup the two split runs. */
1771                 rl->lcn = LCN_HOLE;
1772                 rl->length = length;
1773                 rl++;
1774                 rl->vcn += length;
1775                 /* Only adjust the lcn if it is real. */
1776                 if (rl->lcn >= 0 || lcn_fixup)
1777                         rl->lcn += length;
1778                 rl->length -= length;
1779                 ntfs_debug("Done (split one).");
1780                 return 0;
1781         }
1782         /*
1783          * @start is neither in a hole nor at the beginning of a run.
1784          *
1785          * If @end is in a hole, things are easier as simply truncating the run
1786          * @start is in to end at @start - 1, deleting all runs after that up
1787          * to @end, and finally extending the beginning of the run @end is in
1788          * to be @start is all that is needed.
1789          */
1790         if (rl_end->lcn == LCN_HOLE) {
1791                 /* Truncate the run containing @start. */
1792                 rl->length = start - rl->vcn;
1793                 rl++;
1794                 /* Cut out all runlist elements up to @end. */
1795                 if (rl < rl_end)
1796                         memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
1797                                         sizeof(*rl));
1798                 /* Extend the beginning of the run @end is in to be @start. */
1799                 rl->vcn = start;
1800                 rl->length = rl[1].vcn - start;
1801                 goto shrink_allocation;
1802         }
1803         /*
1804          * If @end is not in a hole there are still two cases to distinguish.
1805          * Either @end is or is not in the same run as @start.
1806          *
1807          * The second case is easier as it can be reduced to an already solved
1808          * problem by truncating the run @start is in to end at @start - 1.
1809          * Then, if @end is in the next run need to split the run into a sparse
1810          * run followed by a non-sparse run (already covered above) and if @end
1811          * is not in the next run switching it to be sparse, again reduces the
1812          * problem to the already covered case of "@start is in a hole".
1813          */
1814         if (end >= rl[1].vcn) {
1815                 /*
1816                  * If @end is not in the next run, reduce the problem to the
1817                  * case of "@start is in a hole".
1818                  */
1819                 if (rl[1].length && end >= rl[2].vcn) {
1820                         /* Truncate the run containing @start. */
1821                         rl->length = start - rl->vcn;
1822                         rl++;
1823                         rl->vcn = start;
1824                         rl->lcn = LCN_HOLE;
1825                         goto extend_hole;
1826                 }
1827                 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
1828                 if (IS_ERR(trl))
1829                         goto enomem_out;
1830                 old_size++;
1831                 if (runlist->rl != trl) {
1832                         rl = trl + (rl - runlist->rl);
1833                         rl_end = trl + (rl_end - runlist->rl);
1834                         rl_real_end = trl + (rl_real_end - runlist->rl);
1835                         runlist->rl = trl;
1836                 }
1837                 /* Truncate the run containing @start. */
1838                 rl->length = start - rl->vcn;
1839                 rl++;
1840                 /*
1841                  * @end is in the next run, reduce the problem to the case
1842                  * where "@start is at the beginning of a run and @end is in
1843                  * the same run as @start".
1844                  */
1845                 delta = rl->vcn - start;
1846                 rl->vcn = start;
1847                 if (rl->lcn >= 0) {
1848                         rl->lcn -= delta;
1849                         /* Need this in case the lcn just became negative. */
1850                         lcn_fixup = TRUE;
1851                 }
1852                 rl->length += delta;
1853                 goto split_end;
1854         }
1855         /*
1856          * The first case from above, i.e. @end is in the same run as @start.
1857          * We need to split the run into three.  One run for the non-sparse
1858          * region between the beginning of the old run and @start, one for the
1859          * sparse region between @start and @end, and one for the remaining
1860          * non-sparse region, i.e. between @end and the end of the old run.
1861          */
1862         trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 2);
1863         if (IS_ERR(trl))
1864                 goto enomem_out;
1865         old_size += 2;
1866         if (runlist->rl != trl) {
1867                 rl = trl + (rl - runlist->rl);
1868                 rl_end = trl + (rl_end - runlist->rl);
1869                 rl_real_end = trl + (rl_real_end - runlist->rl);
1870                 runlist->rl = trl;
1871         }
1872         /* Shift all the runs up by two. */
1873         memmove(rl + 2, rl, (rl_real_end - rl + 1) * sizeof(*rl));
1874         /* Finally, setup the three split runs. */
1875         rl->length = start - rl->vcn;
1876         rl++;
1877         rl->vcn = start;
1878         rl->lcn = LCN_HOLE;
1879         rl->length = length;
1880         rl++;
1881         delta = end - rl->vcn;
1882         rl->vcn = end;
1883         rl->lcn += delta;
1884         rl->length -= delta;
1885         ntfs_debug("Done (split both).");
1886         return 0;
1887 enomem_out:
1888         ntfs_error(vol->sb, "Not enough memory to extend runlist buffer.");
1889         return -ENOMEM;
1890 }
1891
1892 #endif /* NTFS_RW */