blob: f5b2ac929081eb16c1f3bc0b83c3af295d240264 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/**
2 * runlist.c - NTFS runlist handling code. Part of the Linux-NTFS project.
3 *
Anton Altaparmakov1a0df152005-02-03 12:04:36 +00004 * Copyright (c) 2001-2005 Anton Altaparmakov
Linus Torvalds1da177e2005-04-16 15:20:36 -07005 * Copyright (c) 2002 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 */
34static inline void ntfs_rl_mm(runlist_element *base, int dst, int src,
35 int size)
36{
37 if (likely((dst != src) && (size > 0)))
Anton Altaparmakov9529d462005-09-08 16:33:12 +010038 memmove(base + dst, base + src, size * sizeof(*base));
Linus Torvalds1da177e2005-04-16 15:20:36 -070039}
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 */
47static 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
Anton Altaparmakov1a0df152005-02-03 12:04:36 +000062 * memory, this function returns an entire page of memory.
Linus Torvalds1da177e2005-04-16 15:20:36 -070063 *
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 */
74static 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/**
Anton Altaparmakov9529d462005-09-08 16:33:12 +010098 * 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 */
120static 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/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143 * 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 */
155static inline BOOL ntfs_are_rl_mergeable(runlist_element *dst,
156 runlist_element *src)
157{
158 BUG_ON(!dst);
159 BUG_ON(!src);
160
Anton Altaparmakov37e4c132005-02-18 10:03:13 +0000161 if ((dst->lcn < 0) || (src->lcn < 0)) { /* Are we merging holes? */
162 if (dst->lcn == LCN_HOLE && src->lcn == LCN_HOLE)
163 return TRUE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164 return FALSE;
Anton Altaparmakov37e4c132005-02-18 10:03:13 +0000165 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700166 if ((dst->lcn + dst->length) != src->lcn) /* Are the runs contiguous? */
167 return FALSE;
168 if ((dst->vcn + dst->length) != src->vcn) /* Are the runs misaligned? */
169 return FALSE;
170
171 return TRUE;
172}
173
174/**
175 * __ntfs_rl_merge - merge two runlists without testing if they can be merged
176 * @dst: original, destination runlist
177 * @src: new runlist to merge with @dst
178 *
179 * Merge the two runlists, writing into the destination runlist @dst. The
180 * caller must make sure the runlists can be merged or this will corrupt the
181 * destination runlist.
182 *
183 * It is up to the caller to serialize access to the runlists @dst and @src.
184 */
185static inline void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
186{
187 dst->length += src->length;
188}
189
190/**
191 * ntfs_rl_append - append a runlist after a given element
192 * @dst: original runlist to be worked on
193 * @dsize: number of elements in @dst (including end marker)
194 * @src: runlist to be inserted into @dst
195 * @ssize: number of elements in @src (excluding end marker)
196 * @loc: append the new runlist @src after this element in @dst
197 *
198 * Append the runlist @src after element @loc in @dst. Merge the right end of
199 * the new runlist, if necessary. Adjust the size of the hole before the
200 * appended runlist.
201 *
202 * It is up to the caller to serialize access to the runlists @dst and @src.
203 *
204 * On success, return a pointer to the new, combined, runlist. Note, both
205 * runlists @dst and @src are deallocated before returning so you cannot use
206 * the pointers for anything any more. (Strictly speaking the returned runlist
207 * may be the same as @dst but this is irrelevant.)
208 *
209 * On error, return -errno. Both runlists are left unmodified. The following
210 * error codes are defined:
211 * -ENOMEM - Not enough memory to allocate runlist array.
212 * -EINVAL - Invalid parameters were passed in.
213 */
214static inline runlist_element *ntfs_rl_append(runlist_element *dst,
215 int dsize, runlist_element *src, int ssize, int loc)
216{
217 BOOL right;
218 int magic;
219
220 BUG_ON(!dst);
221 BUG_ON(!src);
222
223 /* First, check if the right hand end needs merging. */
224 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
225
226 /* Space required: @dst size + @src size, less one if we merged. */
227 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
228 if (IS_ERR(dst))
229 return dst;
230 /*
231 * We are guaranteed to succeed from here so can start modifying the
232 * original runlists.
233 */
234
235 /* First, merge the right hand end, if necessary. */
236 if (right)
237 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
238
239 magic = loc + ssize;
240
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);
244
245 /* Adjust the size of the preceding hole. */
246 dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
247
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;
251
252 return dst;
253}
254
255/**
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
262 *
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.
266 *
267 * It is up to the caller to serialize access to the runlists @dst and @src.
268 *
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.)
273 *
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.
278 */
279static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
280 int dsize, runlist_element *src, int ssize, int loc)
281{
282 BOOL left = FALSE;
283 BOOL disc = FALSE; /* Discontinuity */
284 BOOL hole = FALSE; /* Following a hole */
285 int magic;
286
287 BUG_ON(!dst);
288 BUG_ON(!src);
289
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. */
294 if (loc == 0)
295 disc = (src[0].vcn > 0);
296 else {
297 s64 merged_length;
298
299 left = ntfs_are_rl_mergeable(dst + loc - 1, src);
300
301 merged_length = dst[loc - 1].length;
302 if (left)
303 merged_length += src->length;
304
305 disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
306 if (disc)
307 hole = (dst[loc - 1].lcn == LCN_HOLE);
308 }
309
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);
313 if (IS_ERR(dst))
314 return dst;
315 /*
316 * We are guaranteed to succeed from here so can start modifying the
317 * original runlist.
318 */
319
320 if (left)
321 __ntfs_rl_merge(dst + loc - 1, src);
322
323 magic = loc + ssize - left + disc - hole;
324
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);
328
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;
335
336 /* Writing beyond the end of the file and there's a discontinuity. */
337 if (disc) {
338 if (hole)
339 dst[loc - 1].length = dst[loc].vcn - dst[loc - 1].vcn;
340 else {
341 if (loc > 0) {
342 dst[loc].vcn = dst[loc - 1].vcn +
343 dst[loc - 1].length;
344 dst[loc].length = dst[loc + 1].vcn -
345 dst[loc].vcn;
346 } else {
347 dst[loc].vcn = 0;
348 dst[loc].length = dst[loc + 1].vcn;
349 }
350 dst[loc].lcn = LCN_RL_NOT_MAPPED;
351 }
352
353 magic += hole;
354
355 if (dst[magic].lcn == LCN_ENOENT)
356 dst[magic].vcn = dst[magic - 1].vcn +
357 dst[magic - 1].length;
358 }
359 return dst;
360}
361
362/**
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
369 *
370 * Replace the runlist element @dst at @loc with @src. Merge the left and
371 * right ends of the inserted runlist, if necessary.
372 *
373 * It is up to the caller to serialize access to the runlists @dst and @src.
374 *
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.)
379 *
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.
384 */
385static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
386 int dsize, runlist_element *src, int ssize, int loc)
387{
388 BOOL left = FALSE;
389 BOOL right;
390 int magic;
391
392 BUG_ON(!dst);
393 BUG_ON(!src);
394
395 /* First, merge the left and right ends, if necessary. */
396 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
397 if (loc > 0)
398 left = ntfs_are_rl_mergeable(dst + loc - 1, src);
399
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);
403 if (IS_ERR(dst))
404 return dst;
405 /*
406 * We are guaranteed to succeed from here so can start modifying the
407 * original runlists.
408 */
409 if (right)
410 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
411 if (left)
412 __ntfs_rl_merge(dst + loc - 1, src);
413
414 /* FIXME: What does this mean? (AIA) */
415 magic = loc + ssize - left;
416
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);
420
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;
424 return dst;
425}
426
427/**
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
434 *
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
437 * holes either side.
438 *
439 * It is up to the caller to serialize access to the runlists @dst and @src.
440 *
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.)
445 *
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.
450 */
451static inline runlist_element *ntfs_rl_split(runlist_element *dst, int dsize,
452 runlist_element *src, int ssize, int loc)
453{
454 BUG_ON(!dst);
455 BUG_ON(!src);
456
457 /* Space required: @dst size + @src size + one new hole. */
458 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize + 1);
459 if (IS_ERR(dst))
460 return dst;
461 /*
462 * We are guaranteed to succeed from here so can start modifying the
463 * original runlists.
464 */
465
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);
469
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;
474
475 return dst;
476}
477
478/**
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
482 *
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.
486 *
487 * It is up to the caller to serialize access to the runlists @drl and @srl.
488 *
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.
492 *
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.
500 *
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.)
505 *
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.
511 */
512runlist_element *ntfs_runlists_merge(runlist_element *drl,
513 runlist_element *srl)
514{
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
520 lcn >= LCN_HOLE. */
521 int marker = 0;
522 VCN marker_vcn = 0;
523
524#ifdef DEBUG
525 ntfs_debug("dst:");
526 ntfs_debug_dump_runlist(drl);
527 ntfs_debug("src:");
528 ntfs_debug_dump_runlist(srl);
529#endif
530
531 /* Check for silly calling... */
532 if (unlikely(!srl))
533 return drl;
534 if (IS_ERR(srl) || IS_ERR(drl))
535 return ERR_PTR(-EINVAL);
536
537 /* Check for the case where the first mapping is being done now. */
538 if (unlikely(!drl)) {
539 drl = srl;
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++)
544 ;
Anton Altaparmakov84d6ebe2005-09-08 16:46:55 +0100545 dend++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700546 drl = ntfs_rl_realloc(drl, dend, dend + 1);
547 if (IS_ERR(drl))
548 return drl;
549 /* Insert start element at the front of the runlist. */
550 ntfs_rl_mm(drl, 1, 0, dend);
551 drl[0].vcn = 0;
552 drl[0].lcn = LCN_RL_NOT_MAPPED;
553 drl[0].length = drl[1].vcn;
554 }
555 goto finished;
556 }
557
558 si = di = 0;
559
560 /* Skip any unmapped start element(s) in the source runlist. */
561 while (srl[si].length && srl[si].lcn < LCN_HOLE)
562 si++;
563
564 /* Can't have an entirely unmapped source runlist. */
565 BUG_ON(!srl[si].length);
566
567 /* Record the starting points. */
568 sstart = si;
569
570 /*
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
573 * appended to @drl.
574 */
575 for (; drl[di].length; di++) {
576 if (drl[di].vcn + drl[di].length > srl[sstart].vcn)
577 break;
578 }
579 dins = di;
580
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);
586 }
587
588 /* Scan to the end of both runlists in order to know their sizes. */
589 for (send = si; srl[send].length; send++)
590 ;
591 for (dend = di; drl[dend].length; dend++)
592 ;
593
594 if (srl[send].lcn == LCN_ENOENT)
595 marker_vcn = srl[marker = send].vcn;
596
597 /* Scan to the last element with lcn >= LCN_HOLE. */
598 for (sfinal = send; sfinal >= 0 && srl[sfinal].lcn < LCN_HOLE; sfinal--)
599 ;
600 for (dfinal = dend; dfinal >= 0 && drl[dfinal].lcn < LCN_HOLE; dfinal--)
601 ;
602
603 {
604 BOOL start;
605 BOOL finish;
606 int ds = dend + 1; /* Number of elements in drl & srl */
607 int ss = sfinal - sstart + 1;
608
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)));
614
Anton Altaparmakov84d6ebe2005-09-08 16:46:55 +0100615 /* Or we will lose an end marker. */
616 if (finish && !drl[dins].length)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700617 ss++;
618 if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn))
619 finish = FALSE;
620#if 0
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);
625#endif
626 if (start) {
627 if (finish)
628 drl = ntfs_rl_replace(drl, ds, srl + sstart, ss, dins);
629 else
630 drl = ntfs_rl_insert(drl, ds, srl + sstart, ss, dins);
631 } else {
632 if (finish)
633 drl = ntfs_rl_append(drl, ds, srl + sstart, ss, dins);
634 else
635 drl = ntfs_rl_split(drl, ds, srl + sstart, ss, dins);
636 }
637 if (IS_ERR(drl)) {
638 ntfs_error(NULL, "Merge failed.");
639 return drl;
640 }
641 ntfs_free(srl);
642 if (marker) {
643 ntfs_debug("Triggering marker code.");
644 for (ds = dend; drl[ds].length; ds++)
645 ;
646 /* We only need to care if @srl ended after @drl. */
647 if (drl[ds].vcn <= marker_vcn) {
648 int slots = 0;
649
650 if (drl[ds].vcn == marker_vcn) {
651 ntfs_debug("Old marker = 0x%llx, replacing "
652 "with LCN_ENOENT.",
653 (unsigned long long)
654 drl[ds].lcn);
655 drl[ds].lcn = LCN_ENOENT;
656 goto finished;
657 }
658 /*
659 * We need to create an unmapped runlist element in
660 * @drl or extend an existing one before adding the
661 * ENOENT terminator.
662 */
663 if (drl[ds].lcn == LCN_ENOENT) {
664 ds--;
665 slots = 1;
666 }
667 if (drl[ds].lcn != LCN_RL_NOT_MAPPED) {
668 /* Add an unmapped runlist element. */
669 if (!slots) {
Anton Altaparmakov9529d462005-09-08 16:33:12 +0100670 drl = ntfs_rl_realloc_nofail(drl, ds,
671 ds + 2);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672 slots = 2;
673 }
674 ds++;
675 /* Need to set vcn if it isn't set already. */
676 if (slots != 1)
677 drl[ds].vcn = drl[ds - 1].vcn +
678 drl[ds - 1].length;
679 drl[ds].lcn = LCN_RL_NOT_MAPPED;
680 /* We now used up a slot. */
681 slots--;
682 }
683 drl[ds].length = marker_vcn - drl[ds].vcn;
684 /* Finally add the ENOENT terminator. */
685 ds++;
Anton Altaparmakov9529d462005-09-08 16:33:12 +0100686 if (!slots)
687 drl = ntfs_rl_realloc_nofail(drl, ds, ds + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700688 drl[ds].vcn = marker_vcn;
689 drl[ds].lcn = LCN_ENOENT;
690 drl[ds].length = (s64)0;
691 }
692 }
693 }
694
695finished:
696 /* The merge was completed successfully. */
697 ntfs_debug("Merged runlist:");
698 ntfs_debug_dump_runlist(drl);
699 return drl;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700}
701
702/**
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
707 *
708 * It is up to the caller to serialize access to the runlist @old_rl.
709 *
710 * Decompress the attribute @attr's mapping pairs array into a runlist. On
711 * success, return the decompressed runlist.
712 *
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.
716 *
717 * On error, return -errno. @old_rl is left unmodified in that case.
718 *
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.
724 *
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)).
729 */
730runlist_element *ntfs_mapping_pairs_decompress(const ntfs_volume *vol,
731 const ATTR_RECORD *attr, runlist_element *old_rl)
732{
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
741 runlist_elements. */
742 u8 b; /* Current byte offset in buf. */
743
744#ifdef DEBUG
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);
750 }
751#endif
752 /* Start at vcn = lowest_vcn and lcn 0. */
753 vcn = sle64_to_cpu(attr->data.non_resident.lowest_vcn);
754 lcn = 0;
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);
762 }
Anton Altaparmakov2b0ada22005-09-08 16:52:31 +0100763 /* If the mapping pairs array is valid but empty, nothing to do. */
764 if (!vcn && !*buf)
765 return old_rl;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700766 /* Current position in runlist array. */
767 rlpos = 0;
768 /* Allocate first page and set current runlist size to one page. */
769 rl = ntfs_malloc_nofs(rlsize = PAGE_SIZE);
770 if (unlikely(!rl))
771 return ERR_PTR(-ENOMEM);
772 /* Insert unmapped starting element if necessary. */
773 if (vcn) {
774 rl->vcn = 0;
775 rl->lcn = LCN_RL_NOT_MAPPED;
776 rl->length = vcn;
777 rlpos++;
778 }
779 while (buf < attr_end && *buf) {
780 /*
781 * Allocate more memory if needed, including space for the
782 * not-mapped and terminator elements. ntfs_malloc_nofs()
783 * operates on whole pages only.
784 */
785 if (((rlpos + 3) * sizeof(*old_rl)) > rlsize) {
786 runlist_element *rl2;
787
788 rl2 = ntfs_malloc_nofs(rlsize + (int)PAGE_SIZE);
789 if (unlikely(!rl2)) {
790 ntfs_free(rl);
791 return ERR_PTR(-ENOMEM);
792 }
793 memcpy(rl2, rl, rlsize);
794 ntfs_free(rl);
795 rl = rl2;
796 rlsize += PAGE_SIZE;
797 }
798 /* Enter the current vcn into the current runlist element. */
799 rl[rlpos].vcn = vcn;
800 /*
801 * Get the change in vcn, i.e. the run length in clusters.
802 * Doing it this way ensures that we signextend negative values.
803 * A negative run length doesn't make any sense, but hey, I
804 * didn't make up the NTFS specs and Windows NT4 treats the run
805 * length as a signed value so that's how it is...
806 */
807 b = *buf & 0xf;
808 if (b) {
809 if (unlikely(buf + b > attr_end))
810 goto io_error;
811 for (deltaxcn = (s8)buf[b--]; b; b--)
812 deltaxcn = (deltaxcn << 8) + buf[b];
813 } else { /* The length entry is compulsory. */
814 ntfs_error(vol->sb, "Missing length entry in mapping "
815 "pairs array.");
816 deltaxcn = (s64)-1;
817 }
818 /*
819 * Assume a negative length to indicate data corruption and
820 * hence clean-up and return NULL.
821 */
822 if (unlikely(deltaxcn < 0)) {
823 ntfs_error(vol->sb, "Invalid length in mapping pairs "
824 "array.");
825 goto err_out;
826 }
827 /*
828 * Enter the current run length into the current runlist
829 * element.
830 */
831 rl[rlpos].length = deltaxcn;
832 /* Increment the current vcn by the current run length. */
833 vcn += deltaxcn;
834 /*
835 * There might be no lcn change at all, as is the case for
836 * sparse clusters on NTFS 3.0+, in which case we set the lcn
837 * to LCN_HOLE.
838 */
839 if (!(*buf & 0xf0))
840 rl[rlpos].lcn = LCN_HOLE;
841 else {
842 /* Get the lcn change which really can be negative. */
843 u8 b2 = *buf & 0xf;
844 b = b2 + ((*buf >> 4) & 0xf);
845 if (buf + b > attr_end)
846 goto io_error;
847 for (deltaxcn = (s8)buf[b--]; b > b2; b--)
848 deltaxcn = (deltaxcn << 8) + buf[b];
849 /* Change the current lcn to its new value. */
850 lcn += deltaxcn;
851#ifdef DEBUG
852 /*
853 * On NTFS 1.2-, apparently can have lcn == -1 to
854 * indicate a hole. But we haven't verified ourselves
855 * whether it is really the lcn or the deltaxcn that is
856 * -1. So if either is found give us a message so we
857 * can investigate it further!
858 */
859 if (vol->major_ver < 3) {
860 if (unlikely(deltaxcn == (LCN)-1))
861 ntfs_error(vol->sb, "lcn delta == -1");
862 if (unlikely(lcn == (LCN)-1))
863 ntfs_error(vol->sb, "lcn == -1");
864 }
865#endif
866 /* Check lcn is not below -1. */
867 if (unlikely(lcn < (LCN)-1)) {
868 ntfs_error(vol->sb, "Invalid LCN < -1 in "
869 "mapping pairs array.");
870 goto err_out;
871 }
872 /* Enter the current lcn into the runlist element. */
873 rl[rlpos].lcn = lcn;
874 }
875 /* Get to the next runlist element. */
876 rlpos++;
877 /* Increment the buffer position to the next mapping pair. */
878 buf += (*buf & 0xf) + ((*buf >> 4) & 0xf) + 1;
879 }
880 if (unlikely(buf >= attr_end))
881 goto io_error;
882 /*
883 * If there is a highest_vcn specified, it must be equal to the final
884 * vcn in the runlist - 1, or something has gone badly wrong.
885 */
886 deltaxcn = sle64_to_cpu(attr->data.non_resident.highest_vcn);
887 if (unlikely(deltaxcn && vcn - 1 != deltaxcn)) {
888mpa_err:
889 ntfs_error(vol->sb, "Corrupt mapping pairs array in "
890 "non-resident attribute.");
891 goto err_out;
892 }
893 /* Setup not mapped runlist element if this is the base extent. */
894 if (!attr->data.non_resident.lowest_vcn) {
895 VCN max_cluster;
896
Anton Altaparmakov1a0df152005-02-03 12:04:36 +0000897 max_cluster = ((sle64_to_cpu(
Linus Torvalds1da177e2005-04-16 15:20:36 -0700898 attr->data.non_resident.allocated_size) +
899 vol->cluster_size - 1) >>
Anton Altaparmakov1a0df152005-02-03 12:04:36 +0000900 vol->cluster_size_bits) - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700901 /*
Anton Altaparmakov1a0df152005-02-03 12:04:36 +0000902 * A highest_vcn of zero means this is a single extent
903 * attribute so simply terminate the runlist with LCN_ENOENT).
Linus Torvalds1da177e2005-04-16 15:20:36 -0700904 */
Anton Altaparmakov1a0df152005-02-03 12:04:36 +0000905 if (deltaxcn) {
906 /*
907 * If there is a difference between the highest_vcn and
908 * the highest cluster, the runlist is either corrupt
909 * or, more likely, there are more extents following
910 * this one.
911 */
912 if (deltaxcn < max_cluster) {
913 ntfs_debug("More extents to follow; deltaxcn "
914 "= 0x%llx, max_cluster = "
915 "0x%llx",
916 (unsigned long long)deltaxcn,
917 (unsigned long long)
918 max_cluster);
919 rl[rlpos].vcn = vcn;
920 vcn += rl[rlpos].length = max_cluster -
921 deltaxcn;
922 rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
923 rlpos++;
924 } else if (unlikely(deltaxcn > max_cluster)) {
925 ntfs_error(vol->sb, "Corrupt attribute. "
926 "deltaxcn = 0x%llx, "
927 "max_cluster = 0x%llx",
928 (unsigned long long)deltaxcn,
929 (unsigned long long)
930 max_cluster);
931 goto mpa_err;
932 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700933 }
934 rl[rlpos].lcn = LCN_ENOENT;
935 } else /* Not the base extent. There may be more extents to follow. */
936 rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
937
938 /* Setup terminating runlist element. */
939 rl[rlpos].vcn = vcn;
940 rl[rlpos].length = (s64)0;
941 /* If no existing runlist was specified, we are done. */
942 if (!old_rl) {
943 ntfs_debug("Mapping pairs array successfully decompressed:");
944 ntfs_debug_dump_runlist(rl);
945 return rl;
946 }
947 /* Now combine the new and old runlists checking for overlaps. */
948 old_rl = ntfs_runlists_merge(old_rl, rl);
949 if (likely(!IS_ERR(old_rl)))
950 return old_rl;
951 ntfs_free(rl);
952 ntfs_error(vol->sb, "Failed to merge runlists.");
953 return old_rl;
954io_error:
955 ntfs_error(vol->sb, "Corrupt attribute.");
956err_out:
957 ntfs_free(rl);
958 return ERR_PTR(-EIO);
959}
960
961/**
962 * ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist
963 * @rl: runlist to use for conversion
964 * @vcn: vcn to convert
965 *
966 * Convert the virtual cluster number @vcn of an attribute into a logical
967 * cluster number (lcn) of a device using the runlist @rl to map vcns to their
968 * corresponding lcns.
969 *
970 * It is up to the caller to serialize access to the runlist @rl.
971 *
Anton Altaparmakovc0c1cc02005-03-07 21:43:38 +0000972 * Since lcns must be >= 0, we use negative return codes with special meaning:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973 *
Anton Altaparmakovc0c1cc02005-03-07 21:43:38 +0000974 * Return code Meaning / Description
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975 * ==================================================
Anton Altaparmakovc0c1cc02005-03-07 21:43:38 +0000976 * LCN_HOLE Hole / not allocated on disk.
977 * LCN_RL_NOT_MAPPED This is part of the runlist which has not been
978 * inserted into the runlist yet.
979 * LCN_ENOENT There is no such vcn in the attribute.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980 *
981 * Locking: - The caller must have locked the runlist (for reading or writing).
Anton Altaparmakovc0c1cc02005-03-07 21:43:38 +0000982 * - This function does not touch the lock, nor does it modify the
983 * runlist.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700984 */
985LCN ntfs_rl_vcn_to_lcn(const runlist_element *rl, const VCN vcn)
986{
987 int i;
988
989 BUG_ON(vcn < 0);
990 /*
991 * If rl is NULL, assume that we have found an unmapped runlist. The
992 * caller can then attempt to map it and fail appropriately if
993 * necessary.
994 */
995 if (unlikely(!rl))
996 return LCN_RL_NOT_MAPPED;
997
998 /* Catch out of lower bounds vcn. */
999 if (unlikely(vcn < rl[0].vcn))
1000 return LCN_ENOENT;
1001
1002 for (i = 0; likely(rl[i].length); i++) {
1003 if (unlikely(vcn < rl[i+1].vcn)) {
1004 if (likely(rl[i].lcn >= (LCN)0))
1005 return rl[i].lcn + (vcn - rl[i].vcn);
1006 return rl[i].lcn;
1007 }
1008 }
1009 /*
1010 * The terminator element is setup to the correct value, i.e. one of
1011 * LCN_HOLE, LCN_RL_NOT_MAPPED, or LCN_ENOENT.
1012 */
1013 if (likely(rl[i].lcn < (LCN)0))
1014 return rl[i].lcn;
1015 /* Just in case... We could replace this with BUG() some day. */
1016 return LCN_ENOENT;
1017}
1018
Anton Altaparmakov53d59aa2005-03-17 10:51:33 +00001019#ifdef NTFS_RW
1020
1021/**
1022 * ntfs_rl_find_vcn_nolock - find a vcn in a runlist
1023 * @rl: runlist to search
1024 * @vcn: vcn to find
1025 *
1026 * Find the virtual cluster number @vcn in the runlist @rl and return the
1027 * address of the runlist element containing the @vcn on success.
1028 *
1029 * Return NULL if @rl is NULL or @vcn is in an unmapped part/out of bounds of
1030 * the runlist.
1031 *
1032 * Locking: The runlist must be locked on entry.
1033 */
1034runlist_element *ntfs_rl_find_vcn_nolock(runlist_element *rl, const VCN vcn)
1035{
1036 BUG_ON(vcn < 0);
1037 if (unlikely(!rl || vcn < rl[0].vcn))
1038 return NULL;
1039 while (likely(rl->length)) {
1040 if (unlikely(vcn < rl[1].vcn)) {
1041 if (likely(rl->lcn >= LCN_HOLE))
1042 return rl;
1043 return NULL;
1044 }
1045 rl++;
1046 }
1047 if (likely(rl->lcn == LCN_ENOENT))
1048 return rl;
1049 return NULL;
1050}
1051
Linus Torvalds1da177e2005-04-16 15:20:36 -07001052/**
1053 * ntfs_get_nr_significant_bytes - get number of bytes needed to store a number
1054 * @n: number for which to get the number of bytes for
1055 *
1056 * Return the number of bytes required to store @n unambiguously as
1057 * a signed number.
1058 *
1059 * This is used in the context of the mapping pairs array to determine how
1060 * many bytes will be needed in the array to store a given logical cluster
1061 * number (lcn) or a specific run length.
1062 *
1063 * Return the number of bytes written. This function cannot fail.
1064 */
1065static inline int ntfs_get_nr_significant_bytes(const s64 n)
1066{
1067 s64 l = n;
1068 int i;
1069 s8 j;
1070
1071 i = 0;
1072 do {
1073 l >>= 8;
1074 i++;
1075 } while (l != 0 && l != -1);
1076 j = (n >> 8 * (i - 1)) & 0xff;
1077 /* If the sign bit is wrong, we need an extra byte. */
1078 if ((n < 0 && j >= 0) || (n > 0 && j < 0))
1079 i++;
1080 return i;
1081}
1082
1083/**
1084 * ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array
1085 * @vol: ntfs volume (needed for the ntfs version)
1086 * @rl: locked runlist to determine the size of the mapping pairs of
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001087 * @first_vcn: first vcn which to include in the mapping pairs array
1088 * @last_vcn: last vcn which to include in the mapping pairs array
Linus Torvalds1da177e2005-04-16 15:20:36 -07001089 *
1090 * Walk the locked runlist @rl and calculate the size in bytes of the mapping
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001091 * pairs array corresponding to the runlist @rl, starting at vcn @first_vcn and
1092 * finishing with vcn @last_vcn.
1093 *
1094 * A @last_vcn of -1 means end of runlist and in that case the size of the
1095 * mapping pairs array corresponding to the runlist starting at vcn @first_vcn
1096 * and finishing at the end of the runlist is determined.
1097 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07001098 * This for example allows us to allocate a buffer of the right size when
1099 * building the mapping pairs array.
1100 *
1101 * If @rl is NULL, just return 1 (for the single terminator byte).
1102 *
1103 * Return the calculated size in bytes on success. On error, return -errno.
1104 * The following error codes are defined:
1105 * -EINVAL - Run list contains unmapped elements. Make sure to only pass
1106 * fully mapped runlists to this function.
1107 * -EIO - The runlist is corrupt.
1108 *
1109 * Locking: @rl must be locked on entry (either for reading or writing), it
1110 * remains locked throughout, and is left locked upon return.
1111 */
1112int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol,
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001113 const runlist_element *rl, const VCN first_vcn,
1114 const VCN last_vcn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001115{
1116 LCN prev_lcn;
1117 int rls;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001118 BOOL the_end = FALSE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001119
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001120 BUG_ON(first_vcn < 0);
1121 BUG_ON(last_vcn < -1);
1122 BUG_ON(last_vcn >= 0 && first_vcn > last_vcn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001123 if (!rl) {
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001124 BUG_ON(first_vcn);
1125 BUG_ON(last_vcn > 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001126 return 1;
1127 }
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001128 /* Skip to runlist element containing @first_vcn. */
1129 while (rl->length && first_vcn >= rl[1].vcn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001130 rl++;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001131 if (unlikely((!rl->length && first_vcn > rl->vcn) ||
1132 first_vcn < rl->vcn))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001133 return -EINVAL;
1134 prev_lcn = 0;
1135 /* Always need the termining zero byte. */
1136 rls = 1;
1137 /* Do the first partial run if present. */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001138 if (first_vcn > rl->vcn) {
1139 s64 delta, length = rl->length;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001140
1141 /* We know rl->length != 0 already. */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001142 if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001143 goto err_out;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001144 /*
1145 * If @stop_vcn is given and finishes inside this run, cap the
1146 * run length.
1147 */
1148 if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
1149 s64 s1 = last_vcn + 1;
1150 if (unlikely(rl[1].vcn > s1))
1151 length = s1 - rl->vcn;
1152 the_end = TRUE;
1153 }
1154 delta = first_vcn - rl->vcn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001155 /* Header byte + length. */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001156 rls += 1 + ntfs_get_nr_significant_bytes(length - delta);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001157 /*
1158 * If the logical cluster number (lcn) denotes a hole and we
1159 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1160 * zero space. On earlier NTFS versions we just store the lcn.
1161 * Note: this assumes that on NTFS 1.2-, holes are stored with
1162 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
1163 */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001164 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001165 prev_lcn = rl->lcn;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001166 if (likely(rl->lcn >= 0))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001167 prev_lcn += delta;
1168 /* Change in lcn. */
1169 rls += ntfs_get_nr_significant_bytes(prev_lcn);
1170 }
1171 /* Go to next runlist element. */
1172 rl++;
1173 }
1174 /* Do the full runs. */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001175 for (; rl->length && !the_end; rl++) {
1176 s64 length = rl->length;
1177
1178 if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001179 goto err_out;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001180 /*
1181 * If @stop_vcn is given and finishes inside this run, cap the
1182 * run length.
1183 */
1184 if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
1185 s64 s1 = last_vcn + 1;
1186 if (unlikely(rl[1].vcn > s1))
1187 length = s1 - rl->vcn;
1188 the_end = TRUE;
1189 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001190 /* Header byte + length. */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001191 rls += 1 + ntfs_get_nr_significant_bytes(length);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001192 /*
1193 * If the logical cluster number (lcn) denotes a hole and we
1194 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1195 * zero space. On earlier NTFS versions we just store the lcn.
1196 * Note: this assumes that on NTFS 1.2-, holes are stored with
1197 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
1198 */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001199 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001200 /* Change in lcn. */
1201 rls += ntfs_get_nr_significant_bytes(rl->lcn -
1202 prev_lcn);
1203 prev_lcn = rl->lcn;
1204 }
1205 }
1206 return rls;
1207err_out:
1208 if (rl->lcn == LCN_RL_NOT_MAPPED)
1209 rls = -EINVAL;
1210 else
1211 rls = -EIO;
1212 return rls;
1213}
1214
1215/**
1216 * ntfs_write_significant_bytes - write the significant bytes of a number
1217 * @dst: destination buffer to write to
1218 * @dst_max: pointer to last byte of destination buffer for bounds checking
1219 * @n: number whose significant bytes to write
1220 *
1221 * Store in @dst, the minimum bytes of the number @n which are required to
1222 * identify @n unambiguously as a signed number, taking care not to exceed
1223 * @dest_max, the maximum position within @dst to which we are allowed to
1224 * write.
1225 *
1226 * This is used when building the mapping pairs array of a runlist to compress
1227 * a given logical cluster number (lcn) or a specific run length to the minumum
1228 * size possible.
1229 *
1230 * Return the number of bytes written on success. On error, i.e. the
1231 * destination buffer @dst is too small, return -ENOSPC.
1232 */
1233static inline int ntfs_write_significant_bytes(s8 *dst, const s8 *dst_max,
1234 const s64 n)
1235{
1236 s64 l = n;
1237 int i;
1238 s8 j;
1239
1240 i = 0;
1241 do {
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001242 if (unlikely(dst > dst_max))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001243 goto err_out;
1244 *dst++ = l & 0xffll;
1245 l >>= 8;
1246 i++;
1247 } while (l != 0 && l != -1);
1248 j = (n >> 8 * (i - 1)) & 0xff;
1249 /* If the sign bit is wrong, we need an extra byte. */
1250 if (n < 0 && j >= 0) {
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001251 if (unlikely(dst > dst_max))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252 goto err_out;
1253 i++;
1254 *dst = (s8)-1;
1255 } else if (n > 0 && j < 0) {
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001256 if (unlikely(dst > dst_max))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001257 goto err_out;
1258 i++;
1259 *dst = (s8)0;
1260 }
1261 return i;
1262err_out:
1263 return -ENOSPC;
1264}
1265
1266/**
1267 * ntfs_mapping_pairs_build - build the mapping pairs array from a runlist
1268 * @vol: ntfs volume (needed for the ntfs version)
1269 * @dst: destination buffer to which to write the mapping pairs array
1270 * @dst_len: size of destination buffer @dst in bytes
1271 * @rl: locked runlist for which to build the mapping pairs array
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001272 * @first_vcn: first vcn which to include in the mapping pairs array
1273 * @last_vcn: last vcn which to include in the mapping pairs array
Linus Torvalds1da177e2005-04-16 15:20:36 -07001274 * @stop_vcn: first vcn outside destination buffer on success or -ENOSPC
1275 *
1276 * Create the mapping pairs array from the locked runlist @rl, starting at vcn
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001277 * @first_vcn and finishing with vcn @last_vcn and save the array in @dst.
1278 * @dst_len is the size of @dst in bytes and it should be at least equal to the
1279 * value obtained by calling ntfs_get_size_for_mapping_pairs().
1280 *
1281 * A @last_vcn of -1 means end of runlist and in that case the mapping pairs
1282 * array corresponding to the runlist starting at vcn @first_vcn and finishing
1283 * at the end of the runlist is created.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001284 *
1285 * If @rl is NULL, just write a single terminator byte to @dst.
1286 *
1287 * On success or -ENOSPC error, if @stop_vcn is not NULL, *@stop_vcn is set to
1288 * the first vcn outside the destination buffer. Note that on error, @dst has
1289 * been filled with all the mapping pairs that will fit, thus it can be treated
1290 * as partial success, in that a new attribute extent needs to be created or
1291 * the next extent has to be used and the mapping pairs build has to be
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001292 * continued with @first_vcn set to *@stop_vcn.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001293 *
1294 * Return 0 on success and -errno on error. The following error codes are
1295 * defined:
1296 * -EINVAL - Run list contains unmapped elements. Make sure to only pass
1297 * fully mapped runlists to this function.
1298 * -EIO - The runlist is corrupt.
1299 * -ENOSPC - The destination buffer is too small.
1300 *
1301 * Locking: @rl must be locked on entry (either for reading or writing), it
1302 * remains locked throughout, and is left locked upon return.
1303 */
1304int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst,
1305 const int dst_len, const runlist_element *rl,
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001306 const VCN first_vcn, const VCN last_vcn, VCN *const stop_vcn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001307{
1308 LCN prev_lcn;
1309 s8 *dst_max, *dst_next;
1310 int err = -ENOSPC;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001311 BOOL the_end = FALSE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001312 s8 len_len, lcn_len;
1313
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001314 BUG_ON(first_vcn < 0);
1315 BUG_ON(last_vcn < -1);
1316 BUG_ON(last_vcn >= 0 && first_vcn > last_vcn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001317 BUG_ON(dst_len < 1);
1318 if (!rl) {
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001319 BUG_ON(first_vcn);
1320 BUG_ON(last_vcn > 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001321 if (stop_vcn)
1322 *stop_vcn = 0;
1323 /* Terminator byte. */
1324 *dst = 0;
1325 return 0;
1326 }
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001327 /* Skip to runlist element containing @first_vcn. */
1328 while (rl->length && first_vcn >= rl[1].vcn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329 rl++;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001330 if (unlikely((!rl->length && first_vcn > rl->vcn) ||
1331 first_vcn < rl->vcn))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001332 return -EINVAL;
1333 /*
1334 * @dst_max is used for bounds checking in
1335 * ntfs_write_significant_bytes().
1336 */
1337 dst_max = dst + dst_len - 1;
1338 prev_lcn = 0;
1339 /* Do the first partial run if present. */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001340 if (first_vcn > rl->vcn) {
1341 s64 delta, length = rl->length;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001342
1343 /* We know rl->length != 0 already. */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001344 if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001345 goto err_out;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001346 /*
1347 * If @stop_vcn is given and finishes inside this run, cap the
1348 * run length.
1349 */
1350 if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
1351 s64 s1 = last_vcn + 1;
1352 if (unlikely(rl[1].vcn > s1))
1353 length = s1 - rl->vcn;
1354 the_end = TRUE;
1355 }
1356 delta = first_vcn - rl->vcn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001357 /* Write length. */
1358 len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001359 length - delta);
1360 if (unlikely(len_len < 0))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361 goto size_err;
1362 /*
1363 * If the logical cluster number (lcn) denotes a hole and we
1364 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1365 * zero space. On earlier NTFS versions we just write the lcn
1366 * change. FIXME: Do we need to write the lcn change or just
1367 * the lcn in that case? Not sure as I have never seen this
1368 * case on NT4. - We assume that we just need to write the lcn
1369 * change until someone tells us otherwise... (AIA)
1370 */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001371 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001372 prev_lcn = rl->lcn;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001373 if (likely(rl->lcn >= 0))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001374 prev_lcn += delta;
1375 /* Write change in lcn. */
1376 lcn_len = ntfs_write_significant_bytes(dst + 1 +
1377 len_len, dst_max, prev_lcn);
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001378 if (unlikely(lcn_len < 0))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001379 goto size_err;
1380 } else
1381 lcn_len = 0;
1382 dst_next = dst + len_len + lcn_len + 1;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001383 if (unlikely(dst_next > dst_max))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001384 goto size_err;
1385 /* Update header byte. */
1386 *dst = lcn_len << 4 | len_len;
1387 /* Position at next mapping pairs array element. */
1388 dst = dst_next;
1389 /* Go to next runlist element. */
1390 rl++;
1391 }
1392 /* Do the full runs. */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001393 for (; rl->length && !the_end; rl++) {
1394 s64 length = rl->length;
1395
1396 if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001397 goto err_out;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001398 /*
1399 * If @stop_vcn is given and finishes inside this run, cap the
1400 * run length.
1401 */
1402 if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
1403 s64 s1 = last_vcn + 1;
1404 if (unlikely(rl[1].vcn > s1))
1405 length = s1 - rl->vcn;
1406 the_end = TRUE;
1407 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001408 /* Write length. */
1409 len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001410 length);
1411 if (unlikely(len_len < 0))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001412 goto size_err;
1413 /*
1414 * If the logical cluster number (lcn) denotes a hole and we
1415 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1416 * zero space. On earlier NTFS versions we just write the lcn
1417 * change. FIXME: Do we need to write the lcn change or just
1418 * the lcn in that case? Not sure as I have never seen this
1419 * case on NT4. - We assume that we just need to write the lcn
1420 * change until someone tells us otherwise... (AIA)
1421 */
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001422 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001423 /* Write change in lcn. */
1424 lcn_len = ntfs_write_significant_bytes(dst + 1 +
1425 len_len, dst_max, rl->lcn - prev_lcn);
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001426 if (unlikely(lcn_len < 0))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001427 goto size_err;
1428 prev_lcn = rl->lcn;
1429 } else
1430 lcn_len = 0;
1431 dst_next = dst + len_len + lcn_len + 1;
Anton Altaparmakovfa3be9232005-06-25 17:15:36 +01001432 if (unlikely(dst_next > dst_max))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001433 goto size_err;
1434 /* Update header byte. */
1435 *dst = lcn_len << 4 | len_len;
1436 /* Position at next mapping pairs array element. */
1437 dst = dst_next;
1438 }
1439 /* Success. */
1440 err = 0;
1441size_err:
1442 /* Set stop vcn. */
1443 if (stop_vcn)
1444 *stop_vcn = rl->vcn;
1445 /* Add terminator byte. */
1446 *dst = 0;
1447 return err;
1448err_out:
1449 if (rl->lcn == LCN_RL_NOT_MAPPED)
1450 err = -EINVAL;
1451 else
1452 err = -EIO;
1453 return err;
1454}
1455
1456/**
1457 * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn
Anton Altaparmakov3ffc5a42005-09-08 20:23:06 +01001458 * @vol: ntfs volume (needed for error output)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001459 * @runlist: runlist to truncate
1460 * @new_length: the new length of the runlist in VCNs
1461 *
1462 * Truncate the runlist described by @runlist as well as the memory buffer
1463 * holding the runlist elements to a length of @new_length VCNs.
1464 *
1465 * If @new_length lies within the runlist, the runlist elements with VCNs of
Anton Altaparmakov3ffc5a42005-09-08 20:23:06 +01001466 * @new_length and above are discarded. As a special case if @new_length is
1467 * zero, the runlist is discarded and set to NULL.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001468 *
1469 * If @new_length lies beyond the runlist, a sparse runlist element is added to
1470 * the end of the runlist @runlist or if the last runlist element is a sparse
1471 * one already, this is extended.
1472 *
Anton Altaparmakov3ffc5a42005-09-08 20:23:06 +01001473 * Note, no checking is done for unmapped runlist elements. It is assumed that
1474 * the caller has mapped any elements that need to be mapped already.
1475 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07001476 * Return 0 on success and -errno on error.
1477 *
1478 * Locking: The caller must hold @runlist->lock for writing.
1479 */
1480int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist,
1481 const s64 new_length)
1482{
1483 runlist_element *rl;
1484 int old_size;
1485
1486 ntfs_debug("Entering for new_length 0x%llx.", (long long)new_length);
1487 BUG_ON(!runlist);
1488 BUG_ON(new_length < 0);
1489 rl = runlist->rl;
Anton Altaparmakov3ffc5a42005-09-08 20:23:06 +01001490 if (!new_length) {
1491 ntfs_debug("Freeing runlist.");
1492 runlist->rl = NULL;
1493 if (rl)
1494 ntfs_free(rl);
1495 return 0;
1496 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001497 if (unlikely(!rl)) {
1498 /*
1499 * Create a runlist consisting of a sparse runlist element of
1500 * length @new_length followed by a terminator runlist element.
1501 */
1502 rl = ntfs_malloc_nofs(PAGE_SIZE);
1503 if (unlikely(!rl)) {
1504 ntfs_error(vol->sb, "Not enough memory to allocate "
1505 "runlist element buffer.");
1506 return -ENOMEM;
1507 }
1508 runlist->rl = rl;
1509 rl[1].length = rl->vcn = 0;
1510 rl->lcn = LCN_HOLE;
1511 rl[1].vcn = rl->length = new_length;
1512 rl[1].lcn = LCN_ENOENT;
1513 return 0;
1514 }
1515 BUG_ON(new_length < rl->vcn);
1516 /* Find @new_length in the runlist. */
1517 while (likely(rl->length && new_length >= rl[1].vcn))
1518 rl++;
1519 /*
1520 * If not at the end of the runlist we need to shrink it.
1521 * If at the end of the runlist we need to expand it.
1522 */
1523 if (rl->length) {
1524 runlist_element *trl;
1525 BOOL is_end;
1526
1527 ntfs_debug("Shrinking runlist.");
1528 /* Determine the runlist size. */
1529 trl = rl + 1;
1530 while (likely(trl->length))
1531 trl++;
1532 old_size = trl - runlist->rl + 1;
1533 /* Truncate the run. */
1534 rl->length = new_length - rl->vcn;
1535 /*
1536 * If a run was partially truncated, make the following runlist
1537 * element a terminator.
1538 */
1539 is_end = FALSE;
1540 if (rl->length) {
1541 rl++;
1542 if (!rl->length)
1543 is_end = TRUE;
1544 rl->vcn = new_length;
1545 rl->length = 0;
1546 }
1547 rl->lcn = LCN_ENOENT;
1548 /* Reallocate memory if necessary. */
1549 if (!is_end) {
1550 int new_size = rl - runlist->rl + 1;
1551 rl = ntfs_rl_realloc(runlist->rl, old_size, new_size);
1552 if (IS_ERR(rl))
1553 ntfs_warning(vol->sb, "Failed to shrink "
1554 "runlist buffer. This just "
1555 "wastes a bit of memory "
1556 "temporarily so we ignore it "
1557 "and return success.");
1558 else
1559 runlist->rl = rl;
1560 }
1561 } else if (likely(/* !rl->length && */ new_length > rl->vcn)) {
1562 ntfs_debug("Expanding runlist.");
1563 /*
1564 * If there is a previous runlist element and it is a sparse
1565 * one, extend it. Otherwise need to add a new, sparse runlist
1566 * element.
1567 */
1568 if ((rl > runlist->rl) && ((rl - 1)->lcn == LCN_HOLE))
1569 (rl - 1)->length = new_length - (rl - 1)->vcn;
1570 else {
1571 /* Determine the runlist size. */
1572 old_size = rl - runlist->rl + 1;
1573 /* Reallocate memory if necessary. */
1574 rl = ntfs_rl_realloc(runlist->rl, old_size,
1575 old_size + 1);
1576 if (IS_ERR(rl)) {
1577 ntfs_error(vol->sb, "Failed to expand runlist "
1578 "buffer, aborting.");
1579 return PTR_ERR(rl);
1580 }
1581 runlist->rl = rl;
1582 /*
1583 * Set @rl to the same runlist element in the new
1584 * runlist as before in the old runlist.
1585 */
1586 rl += old_size - 1;
1587 /* Add a new, sparse runlist element. */
1588 rl->lcn = LCN_HOLE;
1589 rl->length = new_length - rl->vcn;
1590 /* Add a new terminator runlist element. */
1591 rl++;
1592 rl->length = 0;
1593 }
1594 rl->vcn = new_length;
1595 rl->lcn = LCN_ENOENT;
1596 } else /* if (unlikely(!rl->length && new_length == rl->vcn)) */ {
1597 /* Runlist already has same size as requested. */
1598 rl->lcn = LCN_ENOENT;
1599 }
1600 ntfs_debug("Done.");
1601 return 0;
1602}
Anton Altaparmakov53d59aa2005-03-17 10:51:33 +00001603
Anton Altaparmakov6e483212005-09-08 20:26:34 +01001604/**
1605 * ntfs_rl_punch_nolock - punch a hole into a runlist
1606 * @vol: ntfs volume (needed for error output)
1607 * @runlist: runlist to punch a hole into
1608 * @start: starting VCN of the hole to be created
1609 * @length: size of the hole to be created in units of clusters
1610 *
1611 * Punch a hole into the runlist @runlist starting at VCN @start and of size
1612 * @length clusters.
1613 *
1614 * Return 0 on success and -errno on error, in which case @runlist has not been
1615 * modified.
1616 *
1617 * If @start and/or @start + @length are outside the runlist return error code
1618 * -ENOENT.
1619 *
1620 * If the runlist contains unmapped or error elements between @start and @start
1621 * + @length return error code -EINVAL.
1622 *
1623 * Locking: The caller must hold @runlist->lock for writing.
1624 */
1625int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist,
1626 const VCN start, const s64 length)
1627{
1628 const VCN end = start + length;
1629 s64 delta;
1630 runlist_element *rl, *rl_end, *rl_real_end, *trl;
1631 int old_size;
1632 BOOL lcn_fixup = FALSE;
1633
1634 ntfs_debug("Entering for start 0x%llx, length 0x%llx.",
1635 (long long)start, (long long)length);
1636 BUG_ON(!runlist);
1637 BUG_ON(start < 0);
1638 BUG_ON(length < 0);
1639 BUG_ON(end < 0);
1640 rl = runlist->rl;
1641 if (unlikely(!rl)) {
1642 if (likely(!start && !length))
1643 return 0;
1644 return -ENOENT;
1645 }
1646 /* Find @start in the runlist. */
1647 while (likely(rl->length && start >= rl[1].vcn))
1648 rl++;
1649 rl_end = rl;
1650 /* Find @end in the runlist. */
1651 while (likely(rl_end->length && end >= rl_end[1].vcn)) {
1652 /* Verify there are no unmapped or error elements. */
1653 if (unlikely(rl_end->lcn < LCN_HOLE))
1654 return -EINVAL;
1655 rl_end++;
1656 }
1657 /* Check the last element. */
1658 if (unlikely(rl_end->length && rl_end->lcn < LCN_HOLE))
1659 return -EINVAL;
1660 /* This covers @start being out of bounds, too. */
1661 if (!rl_end->length && end > rl_end->vcn)
1662 return -ENOENT;
1663 if (!length)
1664 return 0;
1665 if (!rl->length)
1666 return -ENOENT;
1667 rl_real_end = rl_end;
1668 /* Determine the runlist size. */
1669 while (likely(rl_real_end->length))
1670 rl_real_end++;
1671 old_size = rl_real_end - runlist->rl + 1;
1672 /* If @start is in a hole simply extend the hole. */
1673 if (rl->lcn == LCN_HOLE) {
1674 /*
1675 * If both @start and @end are in the same sparse run, we are
1676 * done.
1677 */
1678 if (end <= rl[1].vcn) {
1679 ntfs_debug("Done (requested hole is already sparse).");
1680 return 0;
1681 }
1682extend_hole:
1683 /* Extend the hole. */
1684 rl->length = end - rl->vcn;
1685 /* If @end is in a hole, merge it with the current one. */
1686 if (rl_end->lcn == LCN_HOLE) {
1687 rl_end++;
1688 rl->length = rl_end->vcn - rl->vcn;
1689 }
1690 /* We have done the hole. Now deal with the remaining tail. */
1691 rl++;
1692 /* Cut out all runlist elements up to @end. */
1693 if (rl < rl_end)
1694 memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
1695 sizeof(*rl));
1696 /* Adjust the beginning of the tail if necessary. */
1697 if (end > rl->vcn) {
1698 s64 delta = end - rl->vcn;
1699 rl->vcn = end;
1700 rl->length -= delta;
1701 /* Only adjust the lcn if it is real. */
1702 if (rl->lcn >= 0)
1703 rl->lcn += delta;
1704 }
1705shrink_allocation:
1706 /* Reallocate memory if the allocation changed. */
1707 if (rl < rl_end) {
1708 rl = ntfs_rl_realloc(runlist->rl, old_size,
1709 old_size - (rl_end - rl));
1710 if (IS_ERR(rl))
1711 ntfs_warning(vol->sb, "Failed to shrink "
1712 "runlist buffer. This just "
1713 "wastes a bit of memory "
1714 "temporarily so we ignore it "
1715 "and return success.");
1716 else
1717 runlist->rl = rl;
1718 }
1719 ntfs_debug("Done (extend hole).");
1720 return 0;
1721 }
1722 /*
1723 * If @start is at the beginning of a run things are easier as there is
1724 * no need to split the first run.
1725 */
1726 if (start == rl->vcn) {
1727 /*
1728 * @start is at the beginning of a run.
1729 *
1730 * If the previous run is sparse, extend its hole.
1731 *
1732 * If @end is not in the same run, switch the run to be sparse
1733 * and extend the newly created hole.
1734 *
1735 * Thus both of these cases reduce the problem to the above
1736 * case of "@start is in a hole".
1737 */
1738 if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) {
1739 rl--;
1740 goto extend_hole;
1741 }
1742 if (end >= rl[1].vcn) {
1743 rl->lcn = LCN_HOLE;
1744 goto extend_hole;
1745 }
1746 /*
1747 * The final case is when @end is in the same run as @start.
1748 * For this need to split the run into two. One run for the
1749 * sparse region between the beginning of the old run, i.e.
1750 * @start, and @end and one for the remaining non-sparse
1751 * region, i.e. between @end and the end of the old run.
1752 */
1753 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
1754 if (IS_ERR(trl))
1755 goto enomem_out;
1756 old_size++;
1757 if (runlist->rl != trl) {
1758 rl = trl + (rl - runlist->rl);
1759 rl_end = trl + (rl_end - runlist->rl);
1760 rl_real_end = trl + (rl_real_end - runlist->rl);
1761 runlist->rl = trl;
1762 }
1763split_end:
1764 /* Shift all the runs up by one. */
1765 memmove(rl + 1, rl, (rl_real_end - rl + 1) * sizeof(*rl));
1766 /* Finally, setup the two split runs. */
1767 rl->lcn = LCN_HOLE;
1768 rl->length = length;
1769 rl++;
1770 rl->vcn += length;
1771 /* Only adjust the lcn if it is real. */
1772 if (rl->lcn >= 0 || lcn_fixup)
1773 rl->lcn += length;
1774 rl->length -= length;
1775 ntfs_debug("Done (split one).");
1776 return 0;
1777 }
1778 /*
1779 * @start is neither in a hole nor at the beginning of a run.
1780 *
1781 * If @end is in a hole, things are easier as simply truncating the run
1782 * @start is in to end at @start - 1, deleting all runs after that up
1783 * to @end, and finally extending the beginning of the run @end is in
1784 * to be @start is all that is needed.
1785 */
1786 if (rl_end->lcn == LCN_HOLE) {
1787 /* Truncate the run containing @start. */
1788 rl->length = start - rl->vcn;
1789 rl++;
1790 /* Cut out all runlist elements up to @end. */
1791 if (rl < rl_end)
1792 memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
1793 sizeof(*rl));
1794 /* Extend the beginning of the run @end is in to be @start. */
1795 rl->vcn = start;
1796 rl->length = rl[1].vcn - start;
1797 goto shrink_allocation;
1798 }
1799 /*
1800 * If @end is not in a hole there are still two cases to distinguish.
1801 * Either @end is or is not in the same run as @start.
1802 *
1803 * The second case is easier as it can be reduced to an already solved
1804 * problem by truncating the run @start is in to end at @start - 1.
1805 * Then, if @end is in the next run need to split the run into a sparse
1806 * run followed by a non-sparse run (already covered above) and if @end
1807 * is not in the next run switching it to be sparse, again reduces the
1808 * problem to the already covered case of "@start is in a hole".
1809 */
1810 if (end >= rl[1].vcn) {
1811 /*
1812 * If @end is not in the next run, reduce the problem to the
1813 * case of "@start is in a hole".
1814 */
1815 if (rl[1].length && end >= rl[2].vcn) {
1816 /* Truncate the run containing @start. */
1817 rl->length = start - rl->vcn;
1818 rl++;
1819 rl->vcn = start;
1820 rl->lcn = LCN_HOLE;
1821 goto extend_hole;
1822 }
1823 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
1824 if (IS_ERR(trl))
1825 goto enomem_out;
1826 old_size++;
1827 if (runlist->rl != trl) {
1828 rl = trl + (rl - runlist->rl);
1829 rl_end = trl + (rl_end - runlist->rl);
1830 rl_real_end = trl + (rl_real_end - runlist->rl);
1831 runlist->rl = trl;
1832 }
1833 /* Truncate the run containing @start. */
1834 rl->length = start - rl->vcn;
1835 rl++;
1836 /*
1837 * @end is in the next run, reduce the problem to the case
1838 * where "@start is at the beginning of a run and @end is in
1839 * the same run as @start".
1840 */
1841 delta = rl->vcn - start;
1842 rl->vcn = start;
1843 if (rl->lcn >= 0) {
1844 rl->lcn -= delta;
1845 /* Need this in case the lcn just became negative. */
1846 lcn_fixup = TRUE;
1847 }
1848 rl->length += delta;
1849 goto split_end;
1850 }
1851 /*
1852 * The first case from above, i.e. @end is in the same run as @start.
1853 * We need to split the run into three. One run for the non-sparse
1854 * region between the beginning of the old run and @start, one for the
1855 * sparse region between @start and @end, and one for the remaining
1856 * non-sparse region, i.e. between @end and the end of the old run.
1857 */
1858 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 2);
1859 if (IS_ERR(trl))
1860 goto enomem_out;
1861 old_size += 2;
1862 if (runlist->rl != trl) {
1863 rl = trl + (rl - runlist->rl);
1864 rl_end = trl + (rl_end - runlist->rl);
1865 rl_real_end = trl + (rl_real_end - runlist->rl);
1866 runlist->rl = trl;
1867 }
1868 /* Shift all the runs up by two. */
1869 memmove(rl + 2, rl, (rl_real_end - rl + 1) * sizeof(*rl));
1870 /* Finally, setup the three split runs. */
1871 rl->length = start - rl->vcn;
1872 rl++;
1873 rl->vcn = start;
1874 rl->lcn = LCN_HOLE;
1875 rl->length = length;
1876 rl++;
1877 delta = end - rl->vcn;
1878 rl->vcn = end;
1879 rl->lcn += delta;
1880 rl->length -= delta;
1881 ntfs_debug("Done (split both).");
1882 return 0;
1883enomem_out:
1884 ntfs_error(vol->sb, "Not enough memory to extend runlist buffer.");
1885 return -ENOMEM;
1886}
1887
Anton Altaparmakov53d59aa2005-03-17 10:51:33 +00001888#endif /* NTFS_RW */