2 * runlist.c - NTFS runlist handling code. Part of the Linux-NTFS project.
4 * Copyright (c) 2001-2005 Anton Altaparmakov
5 * Copyright (c) 2002 Richard Russon
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.
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.
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
30 * ntfs_rl_mm - runlist memmove
32 * It is up to the caller to serialize access to the runlist @base.
34 static inline void ntfs_rl_mm(runlist_element
*base
, int dst
, int src
,
37 if (likely((dst
!= src
) && (size
> 0)))
38 memmove(base
+ dst
, base
+ src
, size
* sizeof(*base
));
42 * ntfs_rl_mc - runlist memory copy
44 * It is up to the caller to serialize access to the runlists @dstbase and
47 static inline void ntfs_rl_mc(runlist_element
*dstbase
, int dst
,
48 runlist_element
*srcbase
, int src
, int size
)
51 memcpy(dstbase
+ dst
, srcbase
+ src
, size
* sizeof(*dstbase
));
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
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.
64 * It is up to the caller to serialize access to the runlist @rl.
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.
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.
74 static inline runlist_element
*ntfs_rl_realloc(runlist_element
*rl
,
75 int old_size
, int new_size
)
77 runlist_element
*new_rl
;
79 old_size
= PAGE_ALIGN(old_size
* sizeof(*rl
));
80 new_size
= PAGE_ALIGN(new_size
* sizeof(*rl
));
81 if (old_size
== new_size
)
84 new_rl
= ntfs_malloc_nofs(new_size
);
85 if (unlikely(!new_rl
))
86 return ERR_PTR(-ENOMEM
);
88 if (likely(rl
!= NULL
)) {
89 if (unlikely(old_size
> new_size
))
91 memcpy(new_rl
, rl
, old_size
);
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
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.
107 * This function guarantees that the allocation will succeed. It will sleep
108 * for as long as it takes to complete the allocation.
110 * It is up to the caller to serialize access to the runlist @rl.
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.
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.
120 static inline runlist_element
*ntfs_rl_realloc_nofail(runlist_element
*rl
,
121 int old_size
, int new_size
)
123 runlist_element
*new_rl
;
125 old_size
= PAGE_ALIGN(old_size
* sizeof(*rl
));
126 new_size
= PAGE_ALIGN(new_size
* sizeof(*rl
));
127 if (old_size
== new_size
)
130 new_rl
= ntfs_malloc_nofs_nofail(new_size
);
133 if (likely(rl
!= NULL
)) {
134 if (unlikely(old_size
> new_size
))
136 memcpy(new_rl
, rl
, old_size
);
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
147 * Test if two runlists can be joined together. For this, their VCNs and LCNs
150 * It is up to the caller to serialize access to the runlists @dst and @src.
152 * Return: TRUE Success, the runlists can be merged.
153 * FALSE Failure, the runlists cannot be merged.
155 static inline BOOL
ntfs_are_rl_mergeable(runlist_element
*dst
,
156 runlist_element
*src
)
161 if ((dst
->lcn
< 0) || (src
->lcn
< 0)) { /* Are we merging holes? */
162 if (dst
->lcn
== LCN_HOLE
&& src
->lcn
== LCN_HOLE
)
166 if ((dst
->lcn
+ dst
->length
) != src
->lcn
) /* Are the runs contiguous? */
168 if ((dst
->vcn
+ dst
->length
) != src
->vcn
) /* Are the runs misaligned? */
175 * __ntfs_rl_merge - merge two runlists without testing if they can be merged
176 * @dst: original, destination runlist
177 * @src: new runlist to merge with @dst
179 * Merge the two runlists, writing into the destination runlist @dst. The
180 * caller must make sure the runlists can be merged or this will corrupt the
181 * destination runlist.
183 * It is up to the caller to serialize access to the runlists @dst and @src.
185 static inline void __ntfs_rl_merge(runlist_element
*dst
, runlist_element
*src
)
187 dst
->length
+= src
->length
;
191 * ntfs_rl_append - append a runlist after a given element
192 * @dst: original runlist to be worked on
193 * @dsize: number of elements in @dst (including end marker)
194 * @src: runlist to be inserted into @dst
195 * @ssize: number of elements in @src (excluding end marker)
196 * @loc: append the new runlist @src after this element in @dst
198 * Append the runlist @src after element @loc in @dst. Merge the right end of
199 * the new runlist, if necessary. Adjust the size of the hole before the
202 * It is up to the caller to serialize access to the runlists @dst and @src.
204 * On success, return a pointer to the new, combined, runlist. Note, both
205 * runlists @dst and @src are deallocated before returning so you cannot use
206 * the pointers for anything any more. (Strictly speaking the returned runlist
207 * may be the same as @dst but this is irrelevant.)
209 * On error, return -errno. Both runlists are left unmodified. The following
210 * error codes are defined:
211 * -ENOMEM - Not enough memory to allocate runlist array.
212 * -EINVAL - Invalid parameters were passed in.
214 static inline runlist_element
*ntfs_rl_append(runlist_element
*dst
,
215 int dsize
, runlist_element
*src
, int ssize
, int loc
)
223 /* First, check if the right hand end needs merging. */
224 right
= ntfs_are_rl_mergeable(src
+ ssize
- 1, dst
+ loc
+ 1);
226 /* Space required: @dst size + @src size, less one if we merged. */
227 dst
= ntfs_rl_realloc(dst
, dsize
, dsize
+ ssize
- right
);
231 * We are guaranteed to succeed from here so can start modifying the
235 /* First, merge the right hand end, if necessary. */
237 __ntfs_rl_merge(src
+ ssize
- 1, dst
+ loc
+ 1);
241 /* Move the tail of @dst out of the way, then copy in @src. */
242 ntfs_rl_mm(dst
, magic
+ 1, loc
+ 1 + right
, dsize
- loc
- 1 - right
);
243 ntfs_rl_mc(dst
, loc
+ 1, src
, 0, ssize
);
245 /* Adjust the size of the preceding hole. */
246 dst
[loc
].length
= dst
[loc
+ 1].vcn
- dst
[loc
].vcn
;
248 /* We may have changed the length of the file, so fix the end marker */
249 if (dst
[magic
+ 1].lcn
== LCN_ENOENT
)
250 dst
[magic
+ 1].vcn
= dst
[magic
].vcn
+ dst
[magic
].length
;
256 * ntfs_rl_insert - insert a runlist into another
257 * @dst: original runlist to be worked on
258 * @dsize: number of elements in @dst (including end marker)
259 * @src: new runlist to be inserted
260 * @ssize: number of elements in @src (excluding end marker)
261 * @loc: insert the new runlist @src before this element in @dst
263 * Insert the runlist @src before element @loc in the runlist @dst. Merge the
264 * left end of the new runlist, if necessary. Adjust the size of the hole
265 * after the inserted runlist.
267 * It is up to the caller to serialize access to the runlists @dst and @src.
269 * On success, return a pointer to the new, combined, runlist. Note, both
270 * runlists @dst and @src are deallocated before returning so you cannot use
271 * the pointers for anything any more. (Strictly speaking the returned runlist
272 * may be the same as @dst but this is irrelevant.)
274 * On error, return -errno. Both runlists are left unmodified. The following
275 * error codes are defined:
276 * -ENOMEM - Not enough memory to allocate runlist array.
277 * -EINVAL - Invalid parameters were passed in.
279 static inline runlist_element
*ntfs_rl_insert(runlist_element
*dst
,
280 int dsize
, runlist_element
*src
, int ssize
, int loc
)
283 BOOL disc
= FALSE
; /* Discontinuity */
284 BOOL hole
= FALSE
; /* Following a hole */
290 /* disc => Discontinuity between the end of @dst and the start of @src.
291 * This means we might need to insert a hole.
292 * hole => @dst ends with a hole or an unmapped region which we can
293 * extend to match the discontinuity. */
295 disc
= (src
[0].vcn
> 0);
299 left
= ntfs_are_rl_mergeable(dst
+ loc
- 1, src
);
301 merged_length
= dst
[loc
- 1].length
;
303 merged_length
+= src
->length
;
305 disc
= (src
[0].vcn
> dst
[loc
- 1].vcn
+ merged_length
);
307 hole
= (dst
[loc
- 1].lcn
== LCN_HOLE
);
310 /* Space required: @dst size + @src size, less one if we merged, plus
311 * one if there was a discontinuity, less one for a trailing hole. */
312 dst
= ntfs_rl_realloc(dst
, dsize
, dsize
+ ssize
- left
+ disc
- hole
);
316 * We are guaranteed to succeed from here so can start modifying the
321 __ntfs_rl_merge(dst
+ loc
- 1, src
);
323 magic
= loc
+ ssize
- left
+ disc
- hole
;
325 /* Move the tail of @dst out of the way, then copy in @src. */
326 ntfs_rl_mm(dst
, magic
, loc
, dsize
- loc
);
327 ntfs_rl_mc(dst
, loc
+ disc
- hole
, src
, left
, ssize
- left
);
329 /* Adjust the VCN of the last run ... */
330 if (dst
[magic
].lcn
<= LCN_HOLE
)
331 dst
[magic
].vcn
= dst
[magic
- 1].vcn
+ dst
[magic
- 1].length
;
332 /* ... and the length. */
333 if (dst
[magic
].lcn
== LCN_HOLE
|| dst
[magic
].lcn
== LCN_RL_NOT_MAPPED
)
334 dst
[magic
].length
= dst
[magic
+ 1].vcn
- dst
[magic
].vcn
;
336 /* Writing beyond the end of the file and there's a discontinuity. */
339 dst
[loc
- 1].length
= dst
[loc
].vcn
- dst
[loc
- 1].vcn
;
342 dst
[loc
].vcn
= dst
[loc
- 1].vcn
+
344 dst
[loc
].length
= dst
[loc
+ 1].vcn
-
348 dst
[loc
].length
= dst
[loc
+ 1].vcn
;
350 dst
[loc
].lcn
= LCN_RL_NOT_MAPPED
;
355 if (dst
[magic
].lcn
== LCN_ENOENT
)
356 dst
[magic
].vcn
= dst
[magic
- 1].vcn
+
357 dst
[magic
- 1].length
;
363 * ntfs_rl_replace - overwrite a runlist element with another runlist
364 * @dst: original runlist to be worked on
365 * @dsize: number of elements in @dst (including end marker)
366 * @src: new runlist to be inserted
367 * @ssize: number of elements in @src (excluding end marker)
368 * @loc: index in runlist @dst to overwrite with @src
370 * Replace the runlist element @dst at @loc with @src. Merge the left and
371 * right ends of the inserted runlist, if necessary.
373 * It is up to the caller to serialize access to the runlists @dst and @src.
375 * On success, return a pointer to the new, combined, runlist. Note, both
376 * runlists @dst and @src are deallocated before returning so you cannot use
377 * the pointers for anything any more. (Strictly speaking the returned runlist
378 * may be the same as @dst but this is irrelevant.)
380 * On error, return -errno. Both runlists are left unmodified. The following
381 * error codes are defined:
382 * -ENOMEM - Not enough memory to allocate runlist array.
383 * -EINVAL - Invalid parameters were passed in.
385 static inline runlist_element
*ntfs_rl_replace(runlist_element
*dst
,
386 int dsize
, runlist_element
*src
, int ssize
, int loc
)
395 /* First, merge the left and right ends, if necessary. */
396 right
= ntfs_are_rl_mergeable(src
+ ssize
- 1, dst
+ loc
+ 1);
398 left
= ntfs_are_rl_mergeable(dst
+ loc
- 1, src
);
400 /* Allocate some space. We'll need less if the left, right, or both
401 * ends were merged. */
402 dst
= ntfs_rl_realloc(dst
, dsize
, dsize
+ ssize
- left
- right
);
406 * We are guaranteed to succeed from here so can start modifying the
410 __ntfs_rl_merge(src
+ ssize
- 1, dst
+ loc
+ 1);
412 __ntfs_rl_merge(dst
+ loc
- 1, src
);
414 /* FIXME: What does this mean? (AIA) */
415 magic
= loc
+ ssize
- left
;
417 /* Move the tail of @dst out of the way, then copy in @src. */
418 ntfs_rl_mm(dst
, magic
, loc
+ right
+ 1, dsize
- loc
- right
- 1);
419 ntfs_rl_mc(dst
, loc
, src
, left
, ssize
- left
);
421 /* We may have changed the length of the file, so fix the end marker */
422 if (dst
[magic
].lcn
== LCN_ENOENT
)
423 dst
[magic
].vcn
= dst
[magic
- 1].vcn
+ dst
[magic
- 1].length
;
428 * ntfs_rl_split - insert a runlist into the centre of a hole
429 * @dst: original runlist to be worked on
430 * @dsize: number of elements in @dst (including end marker)
431 * @src: new runlist to be inserted
432 * @ssize: number of elements in @src (excluding end marker)
433 * @loc: index in runlist @dst at which to split and insert @src
435 * Split the runlist @dst at @loc into two and insert @new in between the two
436 * fragments. No merging of runlists is necessary. Adjust the size of the
439 * It is up to the caller to serialize access to the runlists @dst and @src.
441 * On success, return a pointer to the new, combined, runlist. Note, both
442 * runlists @dst and @src are deallocated before returning so you cannot use
443 * the pointers for anything any more. (Strictly speaking the returned runlist
444 * may be the same as @dst but this is irrelevant.)
446 * On error, return -errno. Both runlists are left unmodified. The following
447 * error codes are defined:
448 * -ENOMEM - Not enough memory to allocate runlist array.
449 * -EINVAL - Invalid parameters were passed in.
451 static inline runlist_element
*ntfs_rl_split(runlist_element
*dst
, int dsize
,
452 runlist_element
*src
, int ssize
, int loc
)
457 /* Space required: @dst size + @src size + one new hole. */
458 dst
= ntfs_rl_realloc(dst
, dsize
, dsize
+ ssize
+ 1);
462 * We are guaranteed to succeed from here so can start modifying the
466 /* Move the tail of @dst out of the way, then copy in @src. */
467 ntfs_rl_mm(dst
, loc
+ 1 + ssize
, loc
, dsize
- loc
);
468 ntfs_rl_mc(dst
, loc
+ 1, src
, 0, ssize
);
470 /* Adjust the size of the holes either size of @src. */
471 dst
[loc
].length
= dst
[loc
+1].vcn
- dst
[loc
].vcn
;
472 dst
[loc
+ssize
+1].vcn
= dst
[loc
+ssize
].vcn
+ dst
[loc
+ssize
].length
;
473 dst
[loc
+ssize
+1].length
= dst
[loc
+ssize
+2].vcn
- dst
[loc
+ssize
+1].vcn
;
479 * ntfs_runlists_merge - merge two runlists into one
480 * @drl: original runlist to be worked on
481 * @srl: new runlist to be merged into @drl
483 * First we sanity check the two runlists @srl and @drl to make sure that they
484 * are sensible and can be merged. The runlist @srl must be either after the
485 * runlist @drl or completely within a hole (or unmapped region) in @drl.
487 * It is up to the caller to serialize access to the runlists @drl and @srl.
489 * Merging of runlists is necessary in two cases:
490 * 1. When attribute lists are used and a further extent is being mapped.
491 * 2. When new clusters are allocated to fill a hole or extend a file.
493 * There are four possible ways @srl can be merged. It can:
494 * - be inserted at the beginning of a hole,
495 * - split the hole in two and be inserted between the two fragments,
496 * - be appended at the end of a hole, or it can
497 * - replace the whole hole.
498 * It can also be appended to the end of the runlist, which is just a variant
499 * of the insert case.
501 * On success, return a pointer to the new, combined, runlist. Note, both
502 * runlists @drl and @srl are deallocated before returning so you cannot use
503 * the pointers for anything any more. (Strictly speaking the returned runlist
504 * may be the same as @dst but this is irrelevant.)
506 * On error, return -errno. Both runlists are left unmodified. The following
507 * error codes are defined:
508 * -ENOMEM - Not enough memory to allocate runlist array.
509 * -EINVAL - Invalid parameters were passed in.
510 * -ERANGE - The runlists overlap and cannot be merged.
512 runlist_element
*ntfs_runlists_merge(runlist_element
*drl
,
513 runlist_element
*srl
)
515 int di
, si
; /* Current index into @[ds]rl. */
516 int sstart
; /* First index with lcn > LCN_RL_NOT_MAPPED. */
517 int dins
; /* Index into @drl at which to insert @srl. */
518 int dend
, send
; /* Last index into @[ds]rl. */
519 int dfinal
, sfinal
; /* The last index into @[ds]rl with
526 ntfs_debug_dump_runlist(drl
);
528 ntfs_debug_dump_runlist(srl
);
531 /* Check for silly calling... */
534 if (IS_ERR(srl
) || IS_ERR(drl
))
535 return ERR_PTR(-EINVAL
);
537 /* Check for the case where the first mapping is being done now. */
538 if (unlikely(!drl
)) {
540 /* Complete the source runlist if necessary. */
541 if (unlikely(drl
[0].vcn
)) {
542 /* Scan to the end of the source runlist. */
543 for (dend
= 0; likely(drl
[dend
].length
); dend
++)
546 drl
= ntfs_rl_realloc(drl
, dend
, dend
+ 1);
549 /* Insert start element at the front of the runlist. */
550 ntfs_rl_mm(drl
, 1, 0, dend
);
552 drl
[0].lcn
= LCN_RL_NOT_MAPPED
;
553 drl
[0].length
= drl
[1].vcn
;
560 /* Skip any unmapped start element(s) in the source runlist. */
561 while (srl
[si
].length
&& srl
[si
].lcn
< LCN_HOLE
)
564 /* Can't have an entirely unmapped source runlist. */
565 BUG_ON(!srl
[si
].length
);
567 /* Record the starting points. */
571 * Skip forward in @drl until we reach the position where @srl needs to
572 * be inserted. If we reach the end of @drl, @srl just needs to be
575 for (; drl
[di
].length
; di
++) {
576 if (drl
[di
].vcn
+ drl
[di
].length
> srl
[sstart
].vcn
)
581 /* Sanity check for illegal overlaps. */
582 if ((drl
[di
].vcn
== srl
[si
].vcn
) && (drl
[di
].lcn
>= 0) &&
583 (srl
[si
].lcn
>= 0)) {
584 ntfs_error(NULL
, "Run lists overlap. Cannot merge!");
585 return ERR_PTR(-ERANGE
);
588 /* Scan to the end of both runlists in order to know their sizes. */
589 for (send
= si
; srl
[send
].length
; send
++)
591 for (dend
= di
; drl
[dend
].length
; dend
++)
594 if (srl
[send
].lcn
== LCN_ENOENT
)
595 marker_vcn
= srl
[marker
= send
].vcn
;
597 /* Scan to the last element with lcn >= LCN_HOLE. */
598 for (sfinal
= send
; sfinal
>= 0 && srl
[sfinal
].lcn
< LCN_HOLE
; sfinal
--)
600 for (dfinal
= dend
; dfinal
>= 0 && drl
[dfinal
].lcn
< LCN_HOLE
; dfinal
--)
606 int ds
= dend
+ 1; /* Number of elements in drl & srl */
607 int ss
= sfinal
- sstart
+ 1;
609 start
= ((drl
[dins
].lcn
< LCN_RL_NOT_MAPPED
) || /* End of file */
610 (drl
[dins
].vcn
== srl
[sstart
].vcn
)); /* Start of hole */
611 finish
= ((drl
[dins
].lcn
>= LCN_RL_NOT_MAPPED
) && /* End of file */
612 ((drl
[dins
].vcn
+ drl
[dins
].length
) <= /* End of hole */
613 (srl
[send
- 1].vcn
+ srl
[send
- 1].length
)));
615 /* Or we will lose an end marker. */
616 if (finish
&& !drl
[dins
].length
)
618 if (marker
&& (drl
[dins
].vcn
+ drl
[dins
].length
> srl
[send
- 1].vcn
))
621 ntfs_debug("dfinal = %i, dend = %i", dfinal
, dend
);
622 ntfs_debug("sstart = %i, sfinal = %i, send = %i", sstart
, sfinal
, send
);
623 ntfs_debug("start = %i, finish = %i", start
, finish
);
624 ntfs_debug("ds = %i, ss = %i, dins = %i", ds
, ss
, dins
);
628 drl
= ntfs_rl_replace(drl
, ds
, srl
+ sstart
, ss
, dins
);
630 drl
= ntfs_rl_insert(drl
, ds
, srl
+ sstart
, ss
, dins
);
633 drl
= ntfs_rl_append(drl
, ds
, srl
+ sstart
, ss
, dins
);
635 drl
= ntfs_rl_split(drl
, ds
, srl
+ sstart
, ss
, dins
);
638 ntfs_error(NULL
, "Merge failed.");
643 ntfs_debug("Triggering marker code.");
644 for (ds
= dend
; drl
[ds
].length
; ds
++)
646 /* We only need to care if @srl ended after @drl. */
647 if (drl
[ds
].vcn
<= marker_vcn
) {
650 if (drl
[ds
].vcn
== marker_vcn
) {
651 ntfs_debug("Old marker = 0x%llx, replacing "
655 drl
[ds
].lcn
= LCN_ENOENT
;
659 * We need to create an unmapped runlist element in
660 * @drl or extend an existing one before adding the
663 if (drl
[ds
].lcn
== LCN_ENOENT
) {
667 if (drl
[ds
].lcn
!= LCN_RL_NOT_MAPPED
) {
668 /* Add an unmapped runlist element. */
670 drl
= ntfs_rl_realloc_nofail(drl
, ds
,
675 /* Need to set vcn if it isn't set already. */
677 drl
[ds
].vcn
= drl
[ds
- 1].vcn
+
679 drl
[ds
].lcn
= LCN_RL_NOT_MAPPED
;
680 /* We now used up a slot. */
683 drl
[ds
].length
= marker_vcn
- drl
[ds
].vcn
;
684 /* Finally add the ENOENT terminator. */
687 drl
= ntfs_rl_realloc_nofail(drl
, ds
, ds
+ 1);
688 drl
[ds
].vcn
= marker_vcn
;
689 drl
[ds
].lcn
= LCN_ENOENT
;
690 drl
[ds
].length
= (s64
)0;
696 /* The merge was completed successfully. */
697 ntfs_debug("Merged runlist:");
698 ntfs_debug_dump_runlist(drl
);
703 * ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist
704 * @vol: ntfs volume on which the attribute resides
705 * @attr: attribute record whose mapping pairs array to decompress
706 * @old_rl: optional runlist in which to insert @attr's runlist
708 * It is up to the caller to serialize access to the runlist @old_rl.
710 * Decompress the attribute @attr's mapping pairs array into a runlist. On
711 * success, return the decompressed runlist.
713 * If @old_rl is not NULL, decompressed runlist is inserted into the
714 * appropriate place in @old_rl and the resultant, combined runlist is
715 * returned. The original @old_rl is deallocated.
717 * On error, return -errno. @old_rl is left unmodified in that case.
719 * The following error codes are defined:
720 * -ENOMEM - Not enough memory to allocate runlist array.
721 * -EIO - Corrupt runlist.
722 * -EINVAL - Invalid parameters were passed in.
723 * -ERANGE - The two runlists overlap.
725 * FIXME: For now we take the conceptionally simplest approach of creating the
726 * new runlist disregarding the already existing one and then splicing the
727 * two into one, if that is possible (we check for overlap and discard the new
728 * runlist if overlap present before returning ERR_PTR(-ERANGE)).
730 runlist_element
*ntfs_mapping_pairs_decompress(const ntfs_volume
*vol
,
731 const ATTR_RECORD
*attr
, runlist_element
*old_rl
)
733 VCN vcn
; /* Current vcn. */
734 LCN lcn
; /* Current lcn. */
735 s64 deltaxcn
; /* Change in [vl]cn. */
736 runlist_element
*rl
; /* The output runlist. */
737 u8
*buf
; /* Current position in mapping pairs array. */
738 u8
*attr_end
; /* End of attribute. */
739 int rlsize
; /* Size of runlist buffer. */
740 u16 rlpos
; /* Current runlist position in units of
742 u8 b
; /* Current byte offset in buf. */
745 /* Make sure attr exists and is non-resident. */
746 if (!attr
|| !attr
->non_resident
|| sle64_to_cpu(
747 attr
->data
.non_resident
.lowest_vcn
) < (VCN
)0) {
748 ntfs_error(vol
->sb
, "Invalid arguments.");
749 return ERR_PTR(-EINVAL
);
752 /* Start at vcn = lowest_vcn and lcn 0. */
753 vcn
= sle64_to_cpu(attr
->data
.non_resident
.lowest_vcn
);
755 /* Get start of the mapping pairs array. */
756 buf
= (u8
*)attr
+ le16_to_cpu(
757 attr
->data
.non_resident
.mapping_pairs_offset
);
758 attr_end
= (u8
*)attr
+ le32_to_cpu(attr
->length
);
759 if (unlikely(buf
< (u8
*)attr
|| buf
> attr_end
)) {
760 ntfs_error(vol
->sb
, "Corrupt attribute.");
761 return ERR_PTR(-EIO
);
763 /* Current position in runlist array. */
765 /* Allocate first page and set current runlist size to one page. */
766 rl
= ntfs_malloc_nofs(rlsize
= PAGE_SIZE
);
768 return ERR_PTR(-ENOMEM
);
769 /* Insert unmapped starting element if necessary. */
772 rl
->lcn
= LCN_RL_NOT_MAPPED
;
776 while (buf
< attr_end
&& *buf
) {
778 * Allocate more memory if needed, including space for the
779 * not-mapped and terminator elements. ntfs_malloc_nofs()
780 * operates on whole pages only.
782 if (((rlpos
+ 3) * sizeof(*old_rl
)) > rlsize
) {
783 runlist_element
*rl2
;
785 rl2
= ntfs_malloc_nofs(rlsize
+ (int)PAGE_SIZE
);
786 if (unlikely(!rl2
)) {
788 return ERR_PTR(-ENOMEM
);
790 memcpy(rl2
, rl
, rlsize
);
795 /* Enter the current vcn into the current runlist element. */
798 * Get the change in vcn, i.e. the run length in clusters.
799 * Doing it this way ensures that we signextend negative values.
800 * A negative run length doesn't make any sense, but hey, I
801 * didn't make up the NTFS specs and Windows NT4 treats the run
802 * length as a signed value so that's how it is...
806 if (unlikely(buf
+ b
> attr_end
))
808 for (deltaxcn
= (s8
)buf
[b
--]; b
; b
--)
809 deltaxcn
= (deltaxcn
<< 8) + buf
[b
];
810 } else { /* The length entry is compulsory. */
811 ntfs_error(vol
->sb
, "Missing length entry in mapping "
816 * Assume a negative length to indicate data corruption and
817 * hence clean-up and return NULL.
819 if (unlikely(deltaxcn
< 0)) {
820 ntfs_error(vol
->sb
, "Invalid length in mapping pairs "
825 * Enter the current run length into the current runlist
828 rl
[rlpos
].length
= deltaxcn
;
829 /* Increment the current vcn by the current run length. */
832 * There might be no lcn change at all, as is the case for
833 * sparse clusters on NTFS 3.0+, in which case we set the lcn
837 rl
[rlpos
].lcn
= LCN_HOLE
;
839 /* Get the lcn change which really can be negative. */
841 b
= b2
+ ((*buf
>> 4) & 0xf);
842 if (buf
+ b
> attr_end
)
844 for (deltaxcn
= (s8
)buf
[b
--]; b
> b2
; b
--)
845 deltaxcn
= (deltaxcn
<< 8) + buf
[b
];
846 /* Change the current lcn to its new value. */
850 * On NTFS 1.2-, apparently can have lcn == -1 to
851 * indicate a hole. But we haven't verified ourselves
852 * whether it is really the lcn or the deltaxcn that is
853 * -1. So if either is found give us a message so we
854 * can investigate it further!
856 if (vol
->major_ver
< 3) {
857 if (unlikely(deltaxcn
== (LCN
)-1))
858 ntfs_error(vol
->sb
, "lcn delta == -1");
859 if (unlikely(lcn
== (LCN
)-1))
860 ntfs_error(vol
->sb
, "lcn == -1");
863 /* Check lcn is not below -1. */
864 if (unlikely(lcn
< (LCN
)-1)) {
865 ntfs_error(vol
->sb
, "Invalid LCN < -1 in "
866 "mapping pairs array.");
869 /* Enter the current lcn into the runlist element. */
872 /* Get to the next runlist element. */
874 /* Increment the buffer position to the next mapping pair. */
875 buf
+= (*buf
& 0xf) + ((*buf
>> 4) & 0xf) + 1;
877 if (unlikely(buf
>= attr_end
))
880 * If there is a highest_vcn specified, it must be equal to the final
881 * vcn in the runlist - 1, or something has gone badly wrong.
883 deltaxcn
= sle64_to_cpu(attr
->data
.non_resident
.highest_vcn
);
884 if (unlikely(deltaxcn
&& vcn
- 1 != deltaxcn
)) {
886 ntfs_error(vol
->sb
, "Corrupt mapping pairs array in "
887 "non-resident attribute.");
890 /* Setup not mapped runlist element if this is the base extent. */
891 if (!attr
->data
.non_resident
.lowest_vcn
) {
894 max_cluster
= ((sle64_to_cpu(
895 attr
->data
.non_resident
.allocated_size
) +
896 vol
->cluster_size
- 1) >>
897 vol
->cluster_size_bits
) - 1;
899 * A highest_vcn of zero means this is a single extent
900 * attribute so simply terminate the runlist with LCN_ENOENT).
904 * If there is a difference between the highest_vcn and
905 * the highest cluster, the runlist is either corrupt
906 * or, more likely, there are more extents following
909 if (deltaxcn
< max_cluster
) {
910 ntfs_debug("More extents to follow; deltaxcn "
911 "= 0x%llx, max_cluster = "
913 (unsigned long long)deltaxcn
,
917 vcn
+= rl
[rlpos
].length
= max_cluster
-
919 rl
[rlpos
].lcn
= LCN_RL_NOT_MAPPED
;
921 } else if (unlikely(deltaxcn
> max_cluster
)) {
922 ntfs_error(vol
->sb
, "Corrupt attribute. "
923 "deltaxcn = 0x%llx, "
924 "max_cluster = 0x%llx",
925 (unsigned long long)deltaxcn
,
931 rl
[rlpos
].lcn
= LCN_ENOENT
;
932 } else /* Not the base extent. There may be more extents to follow. */
933 rl
[rlpos
].lcn
= LCN_RL_NOT_MAPPED
;
935 /* Setup terminating runlist element. */
937 rl
[rlpos
].length
= (s64
)0;
938 /* If no existing runlist was specified, we are done. */
940 ntfs_debug("Mapping pairs array successfully decompressed:");
941 ntfs_debug_dump_runlist(rl
);
944 /* Now combine the new and old runlists checking for overlaps. */
945 old_rl
= ntfs_runlists_merge(old_rl
, rl
);
946 if (likely(!IS_ERR(old_rl
)))
949 ntfs_error(vol
->sb
, "Failed to merge runlists.");
952 ntfs_error(vol
->sb
, "Corrupt attribute.");
955 return ERR_PTR(-EIO
);
959 * ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist
960 * @rl: runlist to use for conversion
961 * @vcn: vcn to convert
963 * Convert the virtual cluster number @vcn of an attribute into a logical
964 * cluster number (lcn) of a device using the runlist @rl to map vcns to their
965 * corresponding lcns.
967 * It is up to the caller to serialize access to the runlist @rl.
969 * Since lcns must be >= 0, we use negative return codes with special meaning:
971 * Return code Meaning / Description
972 * ==================================================
973 * LCN_HOLE Hole / not allocated on disk.
974 * LCN_RL_NOT_MAPPED This is part of the runlist which has not been
975 * inserted into the runlist yet.
976 * LCN_ENOENT There is no such vcn in the attribute.
978 * Locking: - The caller must have locked the runlist (for reading or writing).
979 * - This function does not touch the lock, nor does it modify the
982 LCN
ntfs_rl_vcn_to_lcn(const runlist_element
*rl
, const VCN vcn
)
988 * If rl is NULL, assume that we have found an unmapped runlist. The
989 * caller can then attempt to map it and fail appropriately if
993 return LCN_RL_NOT_MAPPED
;
995 /* Catch out of lower bounds vcn. */
996 if (unlikely(vcn
< rl
[0].vcn
))
999 for (i
= 0; likely(rl
[i
].length
); i
++) {
1000 if (unlikely(vcn
< rl
[i
+1].vcn
)) {
1001 if (likely(rl
[i
].lcn
>= (LCN
)0))
1002 return rl
[i
].lcn
+ (vcn
- rl
[i
].vcn
);
1007 * The terminator element is setup to the correct value, i.e. one of
1008 * LCN_HOLE, LCN_RL_NOT_MAPPED, or LCN_ENOENT.
1010 if (likely(rl
[i
].lcn
< (LCN
)0))
1012 /* Just in case... We could replace this with BUG() some day. */
1019 * ntfs_rl_find_vcn_nolock - find a vcn in a runlist
1020 * @rl: runlist to search
1023 * Find the virtual cluster number @vcn in the runlist @rl and return the
1024 * address of the runlist element containing the @vcn on success.
1026 * Return NULL if @rl is NULL or @vcn is in an unmapped part/out of bounds of
1029 * Locking: The runlist must be locked on entry.
1031 runlist_element
*ntfs_rl_find_vcn_nolock(runlist_element
*rl
, const VCN vcn
)
1034 if (unlikely(!rl
|| vcn
< rl
[0].vcn
))
1036 while (likely(rl
->length
)) {
1037 if (unlikely(vcn
< rl
[1].vcn
)) {
1038 if (likely(rl
->lcn
>= LCN_HOLE
))
1044 if (likely(rl
->lcn
== LCN_ENOENT
))
1050 * ntfs_get_nr_significant_bytes - get number of bytes needed to store a number
1051 * @n: number for which to get the number of bytes for
1053 * Return the number of bytes required to store @n unambiguously as
1056 * This is used in the context of the mapping pairs array to determine how
1057 * many bytes will be needed in the array to store a given logical cluster
1058 * number (lcn) or a specific run length.
1060 * Return the number of bytes written. This function cannot fail.
1062 static inline int ntfs_get_nr_significant_bytes(const s64 n
)
1072 } while (l
!= 0 && l
!= -1);
1073 j
= (n
>> 8 * (i
- 1)) & 0xff;
1074 /* If the sign bit is wrong, we need an extra byte. */
1075 if ((n
< 0 && j
>= 0) || (n
> 0 && j
< 0))
1081 * ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array
1082 * @vol: ntfs volume (needed for the ntfs version)
1083 * @rl: locked runlist to determine the size of the mapping pairs of
1084 * @first_vcn: first vcn which to include in the mapping pairs array
1085 * @last_vcn: last vcn which to include in the mapping pairs array
1087 * Walk the locked runlist @rl and calculate the size in bytes of the mapping
1088 * pairs array corresponding to the runlist @rl, starting at vcn @first_vcn and
1089 * finishing with vcn @last_vcn.
1091 * A @last_vcn of -1 means end of runlist and in that case the size of the
1092 * mapping pairs array corresponding to the runlist starting at vcn @first_vcn
1093 * and finishing at the end of the runlist is determined.
1095 * This for example allows us to allocate a buffer of the right size when
1096 * building the mapping pairs array.
1098 * If @rl is NULL, just return 1 (for the single terminator byte).
1100 * Return the calculated size in bytes on success. On error, return -errno.
1101 * The following error codes are defined:
1102 * -EINVAL - Run list contains unmapped elements. Make sure to only pass
1103 * fully mapped runlists to this function.
1104 * -EIO - The runlist is corrupt.
1106 * Locking: @rl must be locked on entry (either for reading or writing), it
1107 * remains locked throughout, and is left locked upon return.
1109 int ntfs_get_size_for_mapping_pairs(const ntfs_volume
*vol
,
1110 const runlist_element
*rl
, const VCN first_vcn
,
1115 BOOL the_end
= FALSE
;
1117 BUG_ON(first_vcn
< 0);
1118 BUG_ON(last_vcn
< -1);
1119 BUG_ON(last_vcn
>= 0 && first_vcn
> last_vcn
);
1122 BUG_ON(last_vcn
> 0);
1125 /* Skip to runlist element containing @first_vcn. */
1126 while (rl
->length
&& first_vcn
>= rl
[1].vcn
)
1128 if (unlikely((!rl
->length
&& first_vcn
> rl
->vcn
) ||
1129 first_vcn
< rl
->vcn
))
1132 /* Always need the termining zero byte. */
1134 /* Do the first partial run if present. */
1135 if (first_vcn
> rl
->vcn
) {
1136 s64 delta
, length
= rl
->length
;
1138 /* We know rl->length != 0 already. */
1139 if (unlikely(length
< 0 || rl
->lcn
< LCN_HOLE
))
1142 * If @stop_vcn is given and finishes inside this run, cap the
1145 if (unlikely(last_vcn
>= 0 && rl
[1].vcn
> last_vcn
)) {
1146 s64 s1
= last_vcn
+ 1;
1147 if (unlikely(rl
[1].vcn
> s1
))
1148 length
= s1
- rl
->vcn
;
1151 delta
= first_vcn
- rl
->vcn
;
1152 /* Header byte + length. */
1153 rls
+= 1 + ntfs_get_nr_significant_bytes(length
- delta
);
1155 * If the logical cluster number (lcn) denotes a hole and we
1156 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1157 * zero space. On earlier NTFS versions we just store the lcn.
1158 * Note: this assumes that on NTFS 1.2-, holes are stored with
1159 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
1161 if (likely(rl
->lcn
>= 0 || vol
->major_ver
< 3)) {
1163 if (likely(rl
->lcn
>= 0))
1165 /* Change in lcn. */
1166 rls
+= ntfs_get_nr_significant_bytes(prev_lcn
);
1168 /* Go to next runlist element. */
1171 /* Do the full runs. */
1172 for (; rl
->length
&& !the_end
; rl
++) {
1173 s64 length
= rl
->length
;
1175 if (unlikely(length
< 0 || rl
->lcn
< LCN_HOLE
))
1178 * If @stop_vcn is given and finishes inside this run, cap the
1181 if (unlikely(last_vcn
>= 0 && rl
[1].vcn
> last_vcn
)) {
1182 s64 s1
= last_vcn
+ 1;
1183 if (unlikely(rl
[1].vcn
> s1
))
1184 length
= s1
- rl
->vcn
;
1187 /* Header byte + length. */
1188 rls
+= 1 + ntfs_get_nr_significant_bytes(length
);
1190 * If the logical cluster number (lcn) denotes a hole and we
1191 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1192 * zero space. On earlier NTFS versions we just store the lcn.
1193 * Note: this assumes that on NTFS 1.2-, holes are stored with
1194 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
1196 if (likely(rl
->lcn
>= 0 || vol
->major_ver
< 3)) {
1197 /* Change in lcn. */
1198 rls
+= ntfs_get_nr_significant_bytes(rl
->lcn
-
1205 if (rl
->lcn
== LCN_RL_NOT_MAPPED
)
1213 * ntfs_write_significant_bytes - write the significant bytes of a number
1214 * @dst: destination buffer to write to
1215 * @dst_max: pointer to last byte of destination buffer for bounds checking
1216 * @n: number whose significant bytes to write
1218 * Store in @dst, the minimum bytes of the number @n which are required to
1219 * identify @n unambiguously as a signed number, taking care not to exceed
1220 * @dest_max, the maximum position within @dst to which we are allowed to
1223 * This is used when building the mapping pairs array of a runlist to compress
1224 * a given logical cluster number (lcn) or a specific run length to the minumum
1227 * Return the number of bytes written on success. On error, i.e. the
1228 * destination buffer @dst is too small, return -ENOSPC.
1230 static inline int ntfs_write_significant_bytes(s8
*dst
, const s8
*dst_max
,
1239 if (unlikely(dst
> dst_max
))
1241 *dst
++ = l
& 0xffll
;
1244 } while (l
!= 0 && l
!= -1);
1245 j
= (n
>> 8 * (i
- 1)) & 0xff;
1246 /* If the sign bit is wrong, we need an extra byte. */
1247 if (n
< 0 && j
>= 0) {
1248 if (unlikely(dst
> dst_max
))
1252 } else if (n
> 0 && j
< 0) {
1253 if (unlikely(dst
> dst_max
))
1264 * ntfs_mapping_pairs_build - build the mapping pairs array from a runlist
1265 * @vol: ntfs volume (needed for the ntfs version)
1266 * @dst: destination buffer to which to write the mapping pairs array
1267 * @dst_len: size of destination buffer @dst in bytes
1268 * @rl: locked runlist for which to build the mapping pairs array
1269 * @first_vcn: first vcn which to include in the mapping pairs array
1270 * @last_vcn: last vcn which to include in the mapping pairs array
1271 * @stop_vcn: first vcn outside destination buffer on success or -ENOSPC
1273 * Create the mapping pairs array from the locked runlist @rl, starting at vcn
1274 * @first_vcn and finishing with vcn @last_vcn and save the array in @dst.
1275 * @dst_len is the size of @dst in bytes and it should be at least equal to the
1276 * value obtained by calling ntfs_get_size_for_mapping_pairs().
1278 * A @last_vcn of -1 means end of runlist and in that case the mapping pairs
1279 * array corresponding to the runlist starting at vcn @first_vcn and finishing
1280 * at the end of the runlist is created.
1282 * If @rl is NULL, just write a single terminator byte to @dst.
1284 * On success or -ENOSPC error, if @stop_vcn is not NULL, *@stop_vcn is set to
1285 * the first vcn outside the destination buffer. Note that on error, @dst has
1286 * been filled with all the mapping pairs that will fit, thus it can be treated
1287 * as partial success, in that a new attribute extent needs to be created or
1288 * the next extent has to be used and the mapping pairs build has to be
1289 * continued with @first_vcn set to *@stop_vcn.
1291 * Return 0 on success and -errno on error. The following error codes are
1293 * -EINVAL - Run list contains unmapped elements. Make sure to only pass
1294 * fully mapped runlists to this function.
1295 * -EIO - The runlist is corrupt.
1296 * -ENOSPC - The destination buffer is too small.
1298 * Locking: @rl must be locked on entry (either for reading or writing), it
1299 * remains locked throughout, and is left locked upon return.
1301 int ntfs_mapping_pairs_build(const ntfs_volume
*vol
, s8
*dst
,
1302 const int dst_len
, const runlist_element
*rl
,
1303 const VCN first_vcn
, const VCN last_vcn
, VCN
*const stop_vcn
)
1306 s8
*dst_max
, *dst_next
;
1308 BOOL the_end
= FALSE
;
1309 s8 len_len
, lcn_len
;
1311 BUG_ON(first_vcn
< 0);
1312 BUG_ON(last_vcn
< -1);
1313 BUG_ON(last_vcn
>= 0 && first_vcn
> last_vcn
);
1314 BUG_ON(dst_len
< 1);
1317 BUG_ON(last_vcn
> 0);
1320 /* Terminator byte. */
1324 /* Skip to runlist element containing @first_vcn. */
1325 while (rl
->length
&& first_vcn
>= rl
[1].vcn
)
1327 if (unlikely((!rl
->length
&& first_vcn
> rl
->vcn
) ||
1328 first_vcn
< rl
->vcn
))
1331 * @dst_max is used for bounds checking in
1332 * ntfs_write_significant_bytes().
1334 dst_max
= dst
+ dst_len
- 1;
1336 /* Do the first partial run if present. */
1337 if (first_vcn
> rl
->vcn
) {
1338 s64 delta
, length
= rl
->length
;
1340 /* We know rl->length != 0 already. */
1341 if (unlikely(length
< 0 || rl
->lcn
< LCN_HOLE
))
1344 * If @stop_vcn is given and finishes inside this run, cap the
1347 if (unlikely(last_vcn
>= 0 && rl
[1].vcn
> last_vcn
)) {
1348 s64 s1
= last_vcn
+ 1;
1349 if (unlikely(rl
[1].vcn
> s1
))
1350 length
= s1
- rl
->vcn
;
1353 delta
= first_vcn
- rl
->vcn
;
1355 len_len
= ntfs_write_significant_bytes(dst
+ 1, dst_max
,
1357 if (unlikely(len_len
< 0))
1360 * If the logical cluster number (lcn) denotes a hole and we
1361 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1362 * zero space. On earlier NTFS versions we just write the lcn
1363 * change. FIXME: Do we need to write the lcn change or just
1364 * the lcn in that case? Not sure as I have never seen this
1365 * case on NT4. - We assume that we just need to write the lcn
1366 * change until someone tells us otherwise... (AIA)
1368 if (likely(rl
->lcn
>= 0 || vol
->major_ver
< 3)) {
1370 if (likely(rl
->lcn
>= 0))
1372 /* Write change in lcn. */
1373 lcn_len
= ntfs_write_significant_bytes(dst
+ 1 +
1374 len_len
, dst_max
, prev_lcn
);
1375 if (unlikely(lcn_len
< 0))
1379 dst_next
= dst
+ len_len
+ lcn_len
+ 1;
1380 if (unlikely(dst_next
> dst_max
))
1382 /* Update header byte. */
1383 *dst
= lcn_len
<< 4 | len_len
;
1384 /* Position at next mapping pairs array element. */
1386 /* Go to next runlist element. */
1389 /* Do the full runs. */
1390 for (; rl
->length
&& !the_end
; rl
++) {
1391 s64 length
= rl
->length
;
1393 if (unlikely(length
< 0 || rl
->lcn
< LCN_HOLE
))
1396 * If @stop_vcn is given and finishes inside this run, cap the
1399 if (unlikely(last_vcn
>= 0 && rl
[1].vcn
> last_vcn
)) {
1400 s64 s1
= last_vcn
+ 1;
1401 if (unlikely(rl
[1].vcn
> s1
))
1402 length
= s1
- rl
->vcn
;
1406 len_len
= ntfs_write_significant_bytes(dst
+ 1, dst_max
,
1408 if (unlikely(len_len
< 0))
1411 * If the logical cluster number (lcn) denotes a hole and we
1412 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1413 * zero space. On earlier NTFS versions we just write the lcn
1414 * change. FIXME: Do we need to write the lcn change or just
1415 * the lcn in that case? Not sure as I have never seen this
1416 * case on NT4. - We assume that we just need to write the lcn
1417 * change until someone tells us otherwise... (AIA)
1419 if (likely(rl
->lcn
>= 0 || vol
->major_ver
< 3)) {
1420 /* Write change in lcn. */
1421 lcn_len
= ntfs_write_significant_bytes(dst
+ 1 +
1422 len_len
, dst_max
, rl
->lcn
- prev_lcn
);
1423 if (unlikely(lcn_len
< 0))
1428 dst_next
= dst
+ len_len
+ lcn_len
+ 1;
1429 if (unlikely(dst_next
> dst_max
))
1431 /* Update header byte. */
1432 *dst
= lcn_len
<< 4 | len_len
;
1433 /* Position at next mapping pairs array element. */
1441 *stop_vcn
= rl
->vcn
;
1442 /* Add terminator byte. */
1446 if (rl
->lcn
== LCN_RL_NOT_MAPPED
)
1454 * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn
1455 * @runlist: runlist to truncate
1456 * @new_length: the new length of the runlist in VCNs
1458 * Truncate the runlist described by @runlist as well as the memory buffer
1459 * holding the runlist elements to a length of @new_length VCNs.
1461 * If @new_length lies within the runlist, the runlist elements with VCNs of
1462 * @new_length and above are discarded.
1464 * If @new_length lies beyond the runlist, a sparse runlist element is added to
1465 * the end of the runlist @runlist or if the last runlist element is a sparse
1466 * one already, this is extended.
1468 * Return 0 on success and -errno on error.
1470 * Locking: The caller must hold @runlist->lock for writing.
1472 int ntfs_rl_truncate_nolock(const ntfs_volume
*vol
, runlist
*const runlist
,
1473 const s64 new_length
)
1475 runlist_element
*rl
;
1478 ntfs_debug("Entering for new_length 0x%llx.", (long long)new_length
);
1480 BUG_ON(new_length
< 0);
1482 if (unlikely(!rl
)) {
1484 * Create a runlist consisting of a sparse runlist element of
1485 * length @new_length followed by a terminator runlist element.
1487 rl
= ntfs_malloc_nofs(PAGE_SIZE
);
1488 if (unlikely(!rl
)) {
1489 ntfs_error(vol
->sb
, "Not enough memory to allocate "
1490 "runlist element buffer.");
1494 rl
[1].length
= rl
->vcn
= 0;
1496 rl
[1].vcn
= rl
->length
= new_length
;
1497 rl
[1].lcn
= LCN_ENOENT
;
1500 BUG_ON(new_length
< rl
->vcn
);
1501 /* Find @new_length in the runlist. */
1502 while (likely(rl
->length
&& new_length
>= rl
[1].vcn
))
1505 * If not at the end of the runlist we need to shrink it.
1506 * If at the end of the runlist we need to expand it.
1509 runlist_element
*trl
;
1512 ntfs_debug("Shrinking runlist.");
1513 /* Determine the runlist size. */
1515 while (likely(trl
->length
))
1517 old_size
= trl
- runlist
->rl
+ 1;
1518 /* Truncate the run. */
1519 rl
->length
= new_length
- rl
->vcn
;
1521 * If a run was partially truncated, make the following runlist
1522 * element a terminator.
1529 rl
->vcn
= new_length
;
1532 rl
->lcn
= LCN_ENOENT
;
1533 /* Reallocate memory if necessary. */
1535 int new_size
= rl
- runlist
->rl
+ 1;
1536 rl
= ntfs_rl_realloc(runlist
->rl
, old_size
, new_size
);
1538 ntfs_warning(vol
->sb
, "Failed to shrink "
1539 "runlist buffer. This just "
1540 "wastes a bit of memory "
1541 "temporarily so we ignore it "
1542 "and return success.");
1546 } else if (likely(/* !rl->length && */ new_length
> rl
->vcn
)) {
1547 ntfs_debug("Expanding runlist.");
1549 * If there is a previous runlist element and it is a sparse
1550 * one, extend it. Otherwise need to add a new, sparse runlist
1553 if ((rl
> runlist
->rl
) && ((rl
- 1)->lcn
== LCN_HOLE
))
1554 (rl
- 1)->length
= new_length
- (rl
- 1)->vcn
;
1556 /* Determine the runlist size. */
1557 old_size
= rl
- runlist
->rl
+ 1;
1558 /* Reallocate memory if necessary. */
1559 rl
= ntfs_rl_realloc(runlist
->rl
, old_size
,
1562 ntfs_error(vol
->sb
, "Failed to expand runlist "
1563 "buffer, aborting.");
1568 * Set @rl to the same runlist element in the new
1569 * runlist as before in the old runlist.
1572 /* Add a new, sparse runlist element. */
1574 rl
->length
= new_length
- rl
->vcn
;
1575 /* Add a new terminator runlist element. */
1579 rl
->vcn
= new_length
;
1580 rl
->lcn
= LCN_ENOENT
;
1581 } else /* if (unlikely(!rl->length && new_length == rl->vcn)) */ {
1582 /* Runlist already has same size as requested. */
1583 rl
->lcn
= LCN_ENOENT
;
1585 ntfs_debug("Done.");
1589 #endif /* NTFS_RW */