The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/ntfs/runlist.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: 214ec4f53147898275c7d8ece9fbad01


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.