1 /**
2 * runlist.c - Run list handling code. Part of the Linux-NTFS project.
3 *
4 * Copyright (c) 2002-2005 Anton Altaparmakov
5 * Copyright (c) 2002-2005 Richard Russon
6 * Copyright (c) 2002-2006 Szabolcs Szakacsits
7 * Copyright (c) 2004-2007 Yura Pakhuchiy
8 *
9 * This program/include file is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License as published
11 * by the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
13 *
14 * This program/include file is distributed in the hope that it will be
15 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
16 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program (in the main directory of the Linux-NTFS
21 * distribution in the file COPYING); if not, write to the Free Software
22 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 */
24
25 #ifdef HAVE_CONFIG_H
26 #include "config.h"
27 #endif
28
29 #ifdef HAVE_STDIO_H
30 #include <stdio.h>
31 #endif
32 #ifdef HAVE_STRING_H
33 #include <string.h>
34 #endif
35 #ifdef HAVE_STDLIB_H
36 #include <stdlib.h>
37 #endif
38 #ifdef HAVE_ERRNO_H
39 #include <errno.h>
40 #endif
41
42 #include "compat.h"
43 #include "types.h"
44 #include "volume.h"
45 #include "layout.h"
46 #include "debug.h"
47 #include "device.h"
48 #include "logging.h"
49
50 /**
51 * ntfs_rl_mm - runlist memmove
52 * @base:
53 * @dst:
54 * @src:
55 * @size:
56 *
57 * Description...
58 *
59 * Returns:
60 */
61 static __inline__ void ntfs_rl_mm(runlist_element *base, int dst, int src,
62 int size)
63 {
64 if ((dst != src) && (size > 0))
65 memmove(base + dst, base + src, size * sizeof(*base));
66 }
67
68 /**
69 * ntfs_rl_mc - runlist memory copy
70 * @dstbase:
71 * @dst:
72 * @srcbase:
73 * @src:
74 * @size:
75 *
76 * Description...
77 *
78 * Returns:
79 */
80 static __inline__ void ntfs_rl_mc(runlist_element *dstbase, int dst,
81 runlist_element *srcbase, int src, int size)
82 {
83 if (size > 0)
84 memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
85 }
86
87 /**
88 * ntfs_rl_realloc - Reallocate memory for runlists
89 * @rl: original runlist
90 * @old_size: number of runlist elements in the original runlist @rl
91 * @new_size: number of runlist elements we need space for
92 *
93 * As the runlists grow, more memory will be required. To prevent large
94 * numbers of small reallocations of memory, this function returns a 4kiB block
95 * of memory.
96 *
97 * N.B. If the new allocation doesn't require a different number of 4kiB
98 * blocks in memory, the function will return the original pointer.
99 *
100 * On success, return a pointer to the newly allocated, or recycled, memory.
101 * On error, return NULL with errno set to the error code.
102 */
103 static runlist_element *ntfs_rl_realloc(runlist_element *rl,
104 int old_size, int new_size)
105 {
106 old_size = (old_size * sizeof(runlist_element) + 0xfff) & ~0xfff;
107 new_size = (new_size * sizeof(runlist_element) + 0xfff) & ~0xfff;
108 if (old_size == new_size)
109 return rl;
110 return realloc(rl, new_size);
111 }
112
113 /**
114 * ntfs_rl_are_mergeable - test if two runlists can be joined together
115 * @dst: original runlist
116 * @src: new runlist to test for mergeability with @dst
117 *
118 * Test if two runlists can be joined together. For this, their VCNs and LCNs
119 * must be adjacent.
120 *
121 * Return: TRUE Success, the runlists can be merged.
122 * FALSE Failure, the runlists cannot be merged.
123 */
124 static BOOL ntfs_rl_are_mergeable(runlist_element *dst,
125 runlist_element *src)
126 {
127 if (!dst || !src) {
128 ntfs_log_debug("Eeek. ntfs_rl_are_mergeable() invoked with NULL "
129 "pointer!\n");
130 return FALSE;
131 }
132
133 /* We can merge unmapped regions even if they are misaligned. */
134 if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
135 return TRUE;
136 /* If the runs are misaligned, we cannot merge them. */
137 if ((dst->vcn + dst->length) != src->vcn)
138 return FALSE;
139 /* If both runs are non-sparse and contiguous, we can merge them. */
140 if ((dst->lcn >= 0) && (src->lcn >= 0) &&
141 ((dst->lcn + dst->length) == src->lcn))
142 return TRUE;
143 /* If we are merging two holes, we can merge them. */
144 if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
145 return TRUE;
146 /* Cannot merge. */
147 return FALSE;
148 }
149
150 /**
151 * __ntfs_rl_merge - merge two runlists without testing if they can be merged
152 * @dst: original, destination runlist
153 * @src: new runlist to merge with @dst
154 *
155 * Merge the two runlists, writing into the destination runlist @dst. The
156 * caller must make sure the runlists can be merged or this will corrupt the
157 * destination runlist.
158 */
159 static __inline__ void __ntfs_rl_merge(runlist_element *dst,
160 runlist_element *src)
161 {
162 dst->length += src->length;
163 }
164
165 /**
166 * ntfs_rl_append - append a runlist after a given element
167 * @dst: original runlist to be worked on
168 * @dsize: number of elements in @dst (including end marker)
169 * @src: runlist to be inserted into @dst
170 * @ssize: number of elements in @src (excluding end marker)
171 * @loc: append the new runlist @src after this element in @dst
172 *
173 * Append the runlist @src after element @loc in @dst. Merge the right end of
174 * the new runlist, if necessary. Adjust the size of the hole before the
175 * appended runlist.
176 *
177 * On success, return a pointer to the new, combined, runlist. Note, both
178 * runlists @dst and @src are deallocated before returning so you cannot use
179 * the pointers for anything any more. (Strictly speaking the returned runlist
180 * may be the same as @dst but this is irrelevant.)
181 *
182 * On error, return NULL, with errno set to the error code. Both runlists are
183 * left unmodified.
184 */
185 static runlist_element *ntfs_rl_append(runlist_element *dst,
186 int dsize, runlist_element *src, int ssize, int loc)
187 {
188 BOOL right = FALSE; /* Right end of @src needs merging */
189 int marker; /* End of the inserted runs */
190
191 if (!dst || !src) {
192 ntfs_log_debug("Eeek. ntfs_rl_append() invoked with NULL "
193 "pointer!\n");
194 errno = EINVAL;
195 return NULL;
196 }
197
198 /* First, check if the right hand end needs merging. */
199 if ((loc + 1) < dsize)
200 right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
201
202 /* Space required: @dst size + @src size, less one if we merged. */
203 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
204 if (!dst)
205 return NULL;
206 /*
207 * We are guaranteed to succeed from here so can start modifying the
208 * original runlists.
209 */
210
211 /* First, merge the right hand end, if necessary. */
212 if (right)
213 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
214
215 /* marker - First run after the @src runs that have been inserted */
216 marker = loc + ssize + 1;
217
218 /* Move the tail of @dst out of the way, then copy in @src. */
219 ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - loc - 1 - right);
220 ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
221
222 /* Adjust the size of the preceding hole. */
223 dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
224
225 /* We may have changed the length of the file, so fix the end marker */
226 if (dst[marker].lcn == LCN_ENOENT)
227 dst[marker].vcn = dst[marker-1].vcn + dst[marker-1].length;
228
229 return dst;
230 }
231
232 /**
233 * ntfs_rl_insert - insert a runlist into another
234 * @dst: original runlist to be worked on
235 * @dsize: number of elements in @dst (including end marker)
236 * @src: new runlist to be inserted
237 * @ssize: number of elements in @src (excluding end marker)
238 * @loc: insert the new runlist @src before this element in @dst
239 *
240 * Insert the runlist @src before element @loc in the runlist @dst. Merge the
241 * left end of the new runlist, if necessary. Adjust the size of the hole
242 * after the inserted runlist.
243 *
244 * On success, return a pointer to the new, combined, runlist. Note, both
245 * runlists @dst and @src are deallocated before returning so you cannot use
246 * the pointers for anything any more. (Strictly speaking the returned runlist
247 * may be the same as @dst but this is irrelevant.)
248 *
249 * On error, return NULL, with errno set to the error code. Both runlists are
250 * left unmodified.
251 */
252 static runlist_element *ntfs_rl_insert(runlist_element *dst,
253 int dsize, runlist_element *src, int ssize, int loc)
254 {
255 BOOL left = FALSE; /* Left end of @src needs merging */
256 BOOL disc = FALSE; /* Discontinuity between @dst and @src */
257 int marker; /* End of the inserted runs */
258
259 if (!dst || !src) {
260 ntfs_log_debug("Eeek. ntfs_rl_insert() invoked with NULL "
261 "pointer!\n");
262 errno = EINVAL;
263 return NULL;
264 }
265
266 /* disc => Discontinuity between the end of @dst and the start of @src.
267 * This means we might need to insert a "notmapped" run.
268 */
269 if (loc == 0)
270 disc = (src[0].vcn > 0);
271 else {
272 s64 merged_length;
273
274 left = ntfs_rl_are_mergeable(dst + loc - 1, src);
275
276 merged_length = dst[loc - 1].length;
277 if (left)
278 merged_length += src->length;
279
280 disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
281 }
282
283 /* Space required: @dst size + @src size, less one if we merged, plus
284 * one if there was a discontinuity.
285 */
286 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
287 if (!dst)
288 return NULL;
289 /*
290 * We are guaranteed to succeed from here so can start modifying the
291 * original runlist.
292 */
293
294 if (left)
295 __ntfs_rl_merge(dst + loc - 1, src);
296
297 /*
298 * marker - First run after the @src runs that have been inserted
299 * Nominally: marker = @loc + @ssize (location + number of runs in @src)
300 * If "left", then the first run in @src has been merged with one in @dst.
301 * If "disc", then @dst and @src don't meet and we need an extra run to fill the gap.
302 */
303 marker = loc + ssize - left + disc;
304
305 /* Move the tail of @dst out of the way, then copy in @src. */
306 ntfs_rl_mm(dst, marker, loc, dsize - loc);
307 ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
308
309 /* Adjust the VCN of the first run after the insertion ... */
310 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
311 /* ... and the length. */
312 if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
313 dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;
314
315 /* Writing beyond the end of the file and there's a discontinuity. */
316 if (disc) {
317 if (loc > 0) {
318 dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
319 dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
320 } else {
321 dst[loc].vcn = 0;
322 dst[loc].length = dst[loc + 1].vcn;
323 }
324 dst[loc].lcn = LCN_RL_NOT_MAPPED;
325 }
326 return dst;
327 }
328
329 /**
330 * ntfs_rl_replace - overwrite a runlist element with another runlist
331 * @dst: original runlist to be worked on
332 * @dsize: number of elements in @dst (including end marker)
333 * @src: new runlist to be inserted
334 * @ssize: number of elements in @src (excluding end marker)
335 * @loc: index in runlist @dst to overwrite with @src
336 *
337 * Replace the runlist element @dst at @loc with @src. Merge the left and
338 * right ends of the inserted runlist, if necessary.
339 *
340 * On success, return a pointer to the new, combined, runlist. Note, both
341 * runlists @dst and @src are deallocated before returning so you cannot use
342 * the pointers for anything any more. (Strictly speaking the returned runlist
343 * may be the same as @dst but this is irrelevant.)
344 *
345 * On error, return NULL, with errno set to the error code. Both runlists are
346 * left unmodified.
347 */
348 static runlist_element *ntfs_rl_replace(runlist_element *dst,
349 int dsize, runlist_element *src, int ssize, int loc)
350 {
351 signed delta;
352 BOOL left = FALSE; /* Left end of @src needs merging */
353 BOOL right = FALSE; /* Right end of @src needs merging */
354 int tail; /* Start of tail of @dst */
355 int marker; /* End of the inserted runs */
356
357 if (!dst || !src) {
358 ntfs_log_debug("Eeek. ntfs_rl_replace() invoked with NULL "
359 "pointer!\n");
360 errno = EINVAL;
361 return NULL;
362 }
363
364 /* First, see if the left and right ends need merging. */
365 if ((loc + 1) < dsize)
366 right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
367 if (loc > 0)
368 left = ntfs_rl_are_mergeable(dst + loc - 1, src);
369
370 /* Allocate some space. We'll need less if the left, right, or both
371 * ends get merged. The -1 accounts for the run being replaced.
372 */
373 delta = ssize - 1 - left - right;
374 if (delta > 0) {
375 dst = ntfs_rl_realloc(dst, dsize, dsize + delta);
376 if (!dst)
377 return NULL;
378 }
379 /*
380 * We are guaranteed to succeed from here so can start modifying the
381 * original runlists.
382 */
383
384 /* First, merge the left and right ends, if necessary. */
385 if (right)
386 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
387 if (left)
388 __ntfs_rl_merge(dst + loc - 1, src);
389
390 /*
391 * tail - Offset of the tail of @dst
392 * Nominally: @tail = @loc + 1 (location, skipping the replaced run)
393 * If "right", then one of @dst's runs is already merged into @src.
394 */
395 tail = loc + right + 1;
396
397 /*
398 * marker - First run after the @src runs that have been inserted
399 * Nominally: @marker = @loc + @ssize (location + number of runs in @src)
400 * If "left", then the first run in @src has been merged with one in @dst.
401 */
402 marker = loc + ssize - left;
403
404 /* Move the tail of @dst out of the way, then copy in @src. */
405 ntfs_rl_mm(dst, marker, tail, dsize - tail);
406 ntfs_rl_mc(dst, loc, src, left, ssize - left);
407
408 /* We may have changed the length of the file, so fix the end marker */
409 if (((dsize - tail) > 0) && (dst[marker].lcn == LCN_ENOENT))
410 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
411
412 return dst;
413 }
414
415 /**
416 * ntfs_rl_split - insert a runlist into the centre of a hole
417 * @dst: original runlist to be worked on
418 * @dsize: number of elements in @dst (including end marker)
419 * @src: new runlist to be inserted
420 * @ssize: number of elements in @src (excluding end marker)
421 * @loc: index in runlist @dst at which to split and insert @src
422 *
423 * Split the runlist @dst at @loc into two and insert @new in between the two
424 * fragments. No merging of runlists is necessary. Adjust the size of the
425 * holes either side.
426 *
427 * On success, return a pointer to the new, combined, runlist. Note, both
428 * runlists @dst and @src are deallocated before returning so you cannot use
429 * the pointers for anything any more. (Strictly speaking the returned runlist
430 * may be the same as @dst but this is irrelevant.)
431 *
432 * On error, return NULL, with errno set to the error code. Both runlists are
433 * left unmodified.
434 */
435 static runlist_element *ntfs_rl_split(runlist_element *dst,
436 int dsize, runlist_element *src, int ssize, int loc)
437 {
438 if (!dst || !src) {
439 ntfs_log_trace("Invoked with NULL pointer!\n");
440 errno = EINVAL;
441 return NULL;
442 }
443
444 /* Space required: @dst size + @src size + one new hole. */
445 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize + 1);
446 if (!dst)
447 return dst;
448 /*
449 * We are guaranteed to succeed from here so can start modifying the
450 * original runlists.
451 */
452
453 /* Move the tail of @dst out of the way, then copy in @src. */
454 ntfs_rl_mm(dst, loc + 1 + ssize, loc, dsize - loc);
455 ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
456
457 /* Adjust the size of the holes either size of @src. */
458 dst[loc].length = dst[loc+1].vcn - dst[loc].vcn;
459 dst[loc+ssize+1].vcn = dst[loc+ssize].vcn + dst[loc+ssize].length;
460 dst[loc+ssize+1].length = dst[loc+ssize+2].vcn - dst[loc+ssize+1].vcn;
461
462 return dst;
463 }
464
465
466 /**
467 * ntfs_runlists_merge - merge two runlists into one
468 * @drl: original runlist to be worked on
469 * @srl: new runlist to be merged into @drl
470 *
471 * First we sanity check the two runlists @srl and @drl to make sure that they
472 * are sensible and can be merged. The runlist @srl must be either after the
473 * runlist @drl or completely within a hole (or unmapped region) in @drl.
474 *
475 * Merging of runlists is necessary in two cases:
476 * 1. When attribute lists are used and a further extent is being mapped.
477 * 2. When new clusters are allocated to fill a hole or extend a file.
478 *
479 * There are four possible ways @srl can be merged. It can:
480 * - be inserted at the beginning of a hole,
481 * - split the hole in two and be inserted between the two fragments,
482 * - be appended at the end of a hole, or it can
483 * - replace the whole hole.
484 * It can also be appended to the end of the runlist, which is just a variant
485 * of the insert case.
486 *
487 * On success, return a pointer to the new, combined, runlist. Note, both
488 * runlists @drl and @srl are deallocated before returning so you cannot use
489 * the pointers for anything any more. (Strictly speaking the returned runlist
490 * may be the same as @dst but this is irrelevant.)
491 *
492 * On error, return NULL, with errno set to the error code. Both runlists are
493 * left unmodified. The following error codes are defined:
494 * ENOMEM Not enough memory to allocate runlist array.
495 * EINVAL Invalid parameters were passed in.
496 * ERANGE The runlists overlap and cannot be merged.
497 */
498 runlist_element *ntfs_runlists_merge(runlist_element *drl,
499 runlist_element *srl)
500 {
501 int di, si; /* Current index into @[ds]rl. */
502 int sstart; /* First index with lcn > LCN_RL_NOT_MAPPED. */
503 int dins; /* Index into @drl at which to insert @srl. */
504 int dend, send; /* Last index into @[ds]rl. */
505 int dfinal, sfinal; /* The last index into @[ds]rl with
506 lcn >= LCN_HOLE. */
507 int marker = 0;
508 VCN marker_vcn = 0;
509
510 ntfs_log_debug("dst:\n");
511 ntfs_debug_runlist_dump(drl);
512 ntfs_log_debug("src:\n");
513 ntfs_debug_runlist_dump(srl);
514
515 /* Check for silly calling... */
516 if (!srl)
517 return drl;
518
519 /* Check for the case where the first mapping is being done now. */
520 if (!drl) {
521 drl = srl;
522 /* Complete the source runlist if necessary. */
523 if (drl[0].vcn) {
524 /* Scan to the end of the source runlist. */
525 for (dend = 0; drl[dend].length; dend++)
526 ;
527 dend++;
528 drl = ntfs_rl_realloc(drl, dend, dend + 1);
529 if (!drl)
530 return drl;
531 /* Insert start element at the front of the runlist. */
532 ntfs_rl_mm(drl, 1, 0, dend);
533 drl[0].vcn = 0;
534 drl[0].lcn = LCN_RL_NOT_MAPPED;
535 drl[0].length = drl[1].vcn;
536 }
537 goto finished;
538 }
539
540 si = di = 0;
541
542 /* Skip any unmapped start element(s) in the source runlist. */
543 while (srl[si].length && srl[si].lcn < (LCN)LCN_HOLE)
544 si++;
545
546 /* Can't have an entirely unmapped source runlist. */
547 if (!srl[si].length) {
548 ntfs_log_debug("Eeek! ntfs_runlists_merge() received entirely "
549 "unmapped source runlist.\n");
550 errno = EINVAL;
551 return NULL;
552 }
553
554 /* Record the starting points. */
555 sstart = si;
556
557 /*
558 * Skip forward in @drl until we reach the position where @srl needs to
559 * be inserted. If we reach the end of @drl, @srl just needs to be
560 * appended to @drl.
561 */
562 for (; drl[di].length; di++) {
563 if (drl[di].vcn + drl[di].length > srl[sstart].vcn)
564 break;
565 }
566 dins = di;
567
568 /* Sanity check for illegal overlaps. */
569 if ((drl[di].vcn == srl[si].vcn) && (drl[di].lcn >= 0) &&
570 (srl[si].lcn >= 0)) {
571 ntfs_log_debug("Run lists overlap. Cannot merge!\n");
572 errno = ERANGE;
573 return NULL;
574 }
575
576 /* Scan to the end of both runlists in order to know their sizes. */
577 for (send = si; srl[send].length; send++)
578 ;
579 for (dend = di; drl[dend].length; dend++)
580 ;
581
582 if (srl[send].lcn == (LCN)LCN_ENOENT)
583 marker_vcn = srl[marker = send].vcn;
584
585 /* Scan to the last element with lcn >= LCN_HOLE. */
586 for (sfinal = send; sfinal >= 0 && srl[sfinal].lcn < LCN_HOLE; sfinal--)
587 ;
588 for (dfinal = dend; dfinal >= 0 && drl[dfinal].lcn < LCN_HOLE; dfinal--)
589 ;
590
591 {
592 BOOL start;
593 BOOL finish;
594 int ds = dend + 1; /* Number of elements in drl & srl */
595 int ss = sfinal - sstart + 1;
596
597 start = ((drl[dins].lcn < LCN_RL_NOT_MAPPED) || /* End of file */
598 (drl[dins].vcn == srl[sstart].vcn)); /* Start of hole */
599 finish = ((drl[dins].lcn >= LCN_RL_NOT_MAPPED) && /* End of file */
600 ((drl[dins].vcn + drl[dins].length) <= /* End of hole */
601 (srl[send - 1].vcn + srl[send - 1].length)));
602
603 /* Or we'll lose an end marker */
604 if (finish && !drl[dins].length)
605 ss++;
606 if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn))
607 finish = FALSE;
608
609 ntfs_log_debug("dfinal = %i, dend = %i\n", dfinal, dend);
610 ntfs_log_debug("sstart = %i, sfinal = %i, send = %i\n", sstart, sfinal, send);
611 ntfs_log_debug("start = %i, finish = %i\n", start, finish);
612 ntfs_log_debug("ds = %i, ss = %i, dins = %i\n", ds, ss, dins);
613
614 if (start) {
615 if (finish)
616 drl = ntfs_rl_replace(drl, ds, srl + sstart, ss, dins);
617 else
618 drl = ntfs_rl_insert(drl, ds, srl + sstart, ss, dins);
619 } else {
620 if (finish)
621 drl = ntfs_rl_append(drl, ds, srl + sstart, ss, dins);
622 else
623 drl = ntfs_rl_split(drl, ds, srl + sstart, ss, dins);
624 }
625 if (!drl) {
626 ntfs_log_perror("Merge failed");
627 return drl;
628 }
629 free(srl);
630 if (marker) {
631 ntfs_log_debug("Triggering marker code.\n");
632 for (ds = dend; drl[ds].length; ds++)
633 ;
634 /* We only need to care if @srl ended after @drl. */
635 if (drl[ds].vcn <= marker_vcn) {
636 int slots = 0;
637
638 if (drl[ds].vcn == marker_vcn) {
639 ntfs_log_debug("Old marker = %lli, replacing with "
640 "LCN_ENOENT.\n",
641 (long long)drl[ds].lcn);
642 drl[ds].lcn = (LCN)LCN_ENOENT;
643 goto finished;
644 }
645 /*
646 * We need to create an unmapped runlist element in
647 * @drl or extend an existing one before adding the
648 * ENOENT terminator.
649 */
650 if (drl[ds].lcn == (LCN)LCN_ENOENT) {
651 ds--;
652 slots = 1;
653 }
654 if (drl[ds].lcn != (LCN)LCN_RL_NOT_MAPPED) {
655 /* Add an unmapped runlist element. */
656 if (!slots) {
657 /* FIXME/TODO: We need to have the
658 * extra memory already! (AIA)
659 */
660 drl = ntfs_rl_realloc(drl, ds, ds + 2);
661 if (!drl)
662 goto critical_error;
663 slots = 2;
664 }
665 ds++;
666 /* Need to set vcn if it isn't set already. */
667 if (slots != 1)
668 drl[ds].vcn = drl[ds - 1].vcn +
669 drl[ds - 1].length;
670 drl[ds].lcn = (LCN)LCN_RL_NOT_MAPPED;
671 /* We now used up a slot. */
672 slots--;
673 }
674 drl[ds].length = marker_vcn - drl[ds].vcn;
675 /* Finally add the ENOENT terminator. */
676 ds++;
677 if (!slots) {
678 /* FIXME/TODO: We need to have the extra
679 * memory already! (AIA)
680 */
681 drl = ntfs_rl_realloc(drl, ds, ds + 1);
682 if (!drl)
683 goto critical_error;
684 }
685 drl[ds].vcn = marker_vcn;
686 drl[ds].lcn = (LCN)LCN_ENOENT;
687 drl[ds].length = (s64)0;
688 }
689 }
690 }
691
692 finished:
693 /* The merge was completed successfully. */
694 ntfs_log_debug("Merged runlist:\n");
695 ntfs_debug_runlist_dump(drl);
696 return drl;
697
698 critical_error:
699 /* Critical error! We cannot afford to fail here. */
700 ntfs_log_perror("libntfs: Critical error");
701 ntfs_log_debug("Forcing segmentation fault!\n");
702 marker_vcn = ((runlist*)NULL)->lcn;
703 return drl;
704 }
705
706 /**
707 * ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist
708 * @vol: ntfs volume on which the attribute resides
709 * @attr: attribute record whose mapping pairs array to decompress
710 * @old_rl: optional runlist in which to insert @attr's runlist
711 *
712 * Decompress the attribute @attr's mapping pairs array into a runlist. On
713 * success, return the decompressed runlist.
714 *
715 * If @old_rl is not NULL, decompressed runlist is inserted into the
716 * appropriate place in @old_rl and the resultant, combined runlist is
717 * returned. The original @old_rl is deallocated.
718 *
719 * On error, return NULL with errno set to the error code. @old_rl is left
720 * unmodified in that case.
721 *
722 * The following error codes are defined:
723 * ENOMEM Not enough memory to allocate runlist array.
724 * EIO Corrupt runlist.
725 * EINVAL Invalid parameters were passed in.
726 * ERANGE The two runlists overlap.
727 *
728 * FIXME: For now we take the conceptionally simplest approach of creating the
729 * new runlist disregarding the already existing one and then splicing the
730 * two into one, if that is possible (we check for overlap and discard the new
731 * runlist if overlap present before returning NULL, with errno = ERANGE).
732 */
733 runlist_element *ntfs_mapping_pairs_decompress(const ntfs_volume *vol,
734 const ATTR_RECORD *attr, runlist_element *old_rl)
735 {
736 VCN vcn; /* Current vcn. */
737 LCN lcn; /* Current lcn. */
738 s64 deltaxcn; /* Change in [vl]cn. */
739 runlist_element *rl; /* The output runlist. */
740 const u8 *buf; /* Current position in mapping pairs array. */
741 const u8 *attr_end; /* End of attribute. */
742 int err, rlsize; /* Size of runlist buffer. */
743 u16 rlpos; /* Current runlist position in units of
744 runlist_elements. */
745 u8 b; /* Current byte offset in buf. */
746
747 ntfs_log_trace("Entering for attr 0x%x.\n",
748 (unsigned)le32_to_cpu(attr->type));
749 /* Make sure attr exists and is non-resident. */
750 if (!attr || !attr->non_resident ||
751 sle64_to_cpu(attr->u.nonres.lowest_vcn) < (VCN)0) {
752 errno = EINVAL;
753 return NULL;
754 }
755 /* Start at vcn = lowest_vcn and lcn 0. */
756 vcn = sle64_to_cpu(attr->u.nonres.lowest_vcn);
757 lcn = 0;
758 /* Get start of the mapping pairs array. */
759 buf = (const u8*)attr + le16_to_cpu(attr->u.nonres.mapping_pairs_offset);
760 attr_end = (const u8*)attr + le32_to_cpu(attr->length);
761 if (buf < (const u8*)attr || buf > attr_end) {
762 ntfs_log_debug("Corrupt attribute.\n");
763 errno = EIO;
764 return NULL;
765 }
766 /* Current position in runlist array. */
767 rlpos = 0;
768 /* Allocate first 4kiB block and set current runlist size to 4kiB. */
769 rlsize = 0x1000;
770 rl = ntfs_malloc(rlsize);
771 if (!rl)
772 return NULL;
773 /* Insert unmapped starting element if necessary. */
774 if (vcn) {
775 rl->vcn = (VCN)0;
776 rl->lcn = (LCN)LCN_RL_NOT_MAPPED;
777 rl->length = vcn;
778 rlpos++;
779 }
780 while (buf < attr_end && *buf) {
781 /*
782 * Allocate more memory if needed, including space for the
783 * not-mapped and terminator elements.
784 */
785 if ((int)((rlpos + 3) * sizeof(*old_rl)) > rlsize) {
786 runlist_element *rl2;
787
788 rlsize += 0x1000;
789 rl2 = realloc(rl, rlsize);
790 if (!rl2) {
791 int eo = errno;
792 free(rl);
793 errno = eo;
794 return NULL;
795 }
796 rl = rl2;
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 (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_log_debug("Missing length entry in mapping pairs "
815 "array.\n");
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 (deltaxcn < 0) {
823 ntfs_log_debug("Invalid length in mapping pairs array.\n");
824 goto err_out;
825 }
826 /*
827 * Enter the current run length into the current runlist
828 * element.
829 */
830 rl[rlpos].length = deltaxcn;
831 /* Increment the current vcn by the current run length. */
832 vcn += deltaxcn;
833 /*
834 * There might be no lcn change at all, as is the case for
835 * sparse clusters on NTFS 3.0+, in which case we set the lcn
836 * to LCN_HOLE.
837 */
838 if (!(*buf & 0xf0))
839 rl[rlpos].lcn = (LCN)LCN_HOLE;
840 else {
841 /* Get the lcn change which really can be negative. */
842 u8 b2 = *buf & 0xf;
843 b = b2 + ((*buf >> 4) & 0xf);
844 if (buf + b > attr_end)
845 goto io_error;
846 for (deltaxcn = (s8)buf[b--]; b > b2; b--)
847 deltaxcn = (deltaxcn << 8) + buf[b];
848 /* Change the current lcn to it's new value. */
849 lcn += deltaxcn;
850 #ifdef DEBUG
851 /*
852 * On NTFS 1.2-, apparently can have lcn == -1 to
853 * indicate a hole. But we haven't verified ourselves
854 * whether it is really the lcn or the deltaxcn that is
855 * -1. So if either is found give us a message so we
856 * can investigate it further!
857 */
858 if (vol->major_ver < 3) {
859 if (deltaxcn == (LCN)-1)
860 ntfs_log_debug("lcn delta == -1\n");
861 if (lcn == (LCN)-1)
862 ntfs_log_debug("lcn == -1\n");
863 }
864 #endif
865 /* Check lcn is not below -1. */
866 if (lcn < (LCN)-1) {
867 ntfs_log_debug("Invalid LCN < -1 in mapping pairs "
868 "array.\n");
869 goto err_out;
870 }
871 /* Enter the current lcn into the runlist element. */
872 rl[rlpos].lcn = lcn;
873 }
874 /* Get to the next runlist element. */
875 rlpos++;
876 /* Increment the buffer position to the next mapping pair. */
877 buf += (*buf & 0xf) + ((*buf >> 4) & 0xf) + 1;
878 }
879 if (buf >= attr_end)
880 goto io_error;
881 /*
882 * If there is a highest_vcn specified, it must be equal to the final
883 * vcn in the runlist - 1, or something has gone badly wrong.
884 */
885 deltaxcn = sle64_to_cpu(attr->u.nonres.highest_vcn);
886 if (deltaxcn && vcn - 1 != deltaxcn) {
887 mpa_err:
888 ntfs_log_debug("Corrupt mapping pairs array in non-resident "
889 "attribute.\n");
890 goto err_out;
891 }
892 /* Setup not mapped runlist element if this is the base extent. */
893 if (!attr->u.nonres.lowest_vcn) {
894 VCN max_cluster;
895
896 max_cluster = ((sle64_to_cpu(attr->u.nonres.allocated_size) +
897 vol->cluster_size - 1) >>
898 vol->cluster_size_bits) - 1;
899 /*
900 * A highest_vcn of zero means this is a single extent
901 * attribute so simply terminate the runlist with LCN_ENOENT).
902 */
903 if (deltaxcn) {
904 /*
905 * If there is a difference between the highest_vcn and
906 * the highest cluster, the runlist is either corrupt
907 * or, more likely, there are more extents following
908 * this one.
909 */
910 if (deltaxcn < max_cluster) {
911 ntfs_log_debug("More extents to follow; deltaxcn = "
912 "0x%llx, max_cluster = 0x%llx\n",
913 (long long)deltaxcn,
914 (long long)max_cluster);
915 rl[rlpos].vcn = vcn;
916 vcn += rl[rlpos].length = max_cluster - deltaxcn;
917 rl[rlpos].lcn = (LCN)LCN_RL_NOT_MAPPED;
918 rlpos++;
919 } else if (deltaxcn > max_cluster) {
920 ntfs_log_debug("Corrupt attribute. deltaxcn = "
921 "0x%llx, max_cluster = 0x%llx\n",
922 (long long)deltaxcn,
923 (long long)max_cluster);
924 goto mpa_err;
925 }
926 }
927 rl[rlpos].lcn = (LCN)LCN_ENOENT;
928 } else /* Not the base extent. There may be more extents to follow. */
929 rl[rlpos].lcn = (LCN)LCN_RL_NOT_MAPPED;
930
931 /* Setup terminating runlist element. */
932 rl[rlpos].vcn = vcn;
933 rl[rlpos].length = (s64)0;
934 /* If no existing runlist was specified, we are done. */
935 if (!old_rl) {
936 ntfs_log_debug("Mapping pairs array successfully decompressed:\n");
937 ntfs_debug_runlist_dump(rl);
938 return rl;
939 }
940 /* Now combine the new and old runlists checking for overlaps. */
941 old_rl = ntfs_runlists_merge(old_rl, rl);
942 if (old_rl)
943 return old_rl;
944 err = errno;
945 free(rl);
946 ntfs_log_debug("Failed to merge runlists.\n");
947 errno = err;
948 return NULL;
949 io_error:
950 ntfs_log_debug("Corrupt attribute.\n");
951 err_out:
952 free(rl);
953 errno = EIO;
954 return NULL;
955 }
956
957 /**
958 * ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist
959 * @rl: runlist to use for conversion
960 * @vcn: vcn to convert
961 *
962 * Convert the virtual cluster number @vcn of an attribute into a logical
963 * cluster number (lcn) of a device using the runlist @rl to map vcns to their
964 * corresponding lcns.
965 *
966 * Since lcns must be >= 0, we use negative return values with special meaning:
967 *
968 * Return value Meaning / Description
969 * ==================================================
970 * -1 = LCN_HOLE Hole / not allocated on disk.
971 * -2 = LCN_RL_NOT_MAPPED This is part of the runlist which has not been
972 * inserted into the runlist yet.
973 * -3 = LCN_ENOENT There is no such vcn in the attribute.
974 * -4 = LCN_EINVAL Input parameter error.
975 */
976 LCN ntfs_rl_vcn_to_lcn(const runlist_element *rl, const VCN vcn)
977 {
978 int i;
979
980 if (vcn < (VCN)0)
981 return (LCN)LCN_EINVAL;
982 /*
983 * If rl is NULL, assume that we have found an unmapped runlist. The
984 * caller can then attempt to map it and fail appropriately if
985 * necessary.
986 */
987 if (!rl)
988 return (LCN)LCN_RL_NOT_MAPPED;
989
990 /* Catch out of lower bounds vcn. */
991 if (vcn < rl[0].vcn)
992 return (LCN)LCN_ENOENT;
993
994 for (i = 0; rl[i].length; i++) {
995 if (vcn < rl[i+1].vcn) {
996 if (rl[i].lcn >= (LCN)0)
997 return rl[i].lcn + (vcn - rl[i].vcn);
998 return rl[i].lcn;
999 }
1000 }
1001 /*
1002 * The terminator element is setup to the correct value, i.e. one of
1003 * LCN_HOLE, LCN_RL_NOT_MAPPED, or LCN_ENOENT.
1004 */
1005 if (rl[i].lcn < (LCN)0)
1006 return rl[i].lcn;
1007 /* Just in case... We could replace this with BUG() some day. */
1008 return (LCN)LCN_ENOENT;
1009 }
1010
1011 /**
1012 * ntfs_rl_pread - gather read from disk
1013 * @vol: ntfs volume to read from
1014 * @rl: runlist specifying where to read the data from
1015 * @pos: byte position within runlist @rl at which to begin the read
1016 * @count: number of bytes to read
1017 * @b: data buffer into which to read from disk
1018 *
1019 * This function will read @count bytes from the volume @vol to the data buffer
1020 * @b gathering the data as specified by the runlist @rl. The read begins at
1021 * offset @pos into the runlist @rl.
1022 *
1023 * On success, return the number of successfully read bytes. If this number is
1024 * lower than @count this means that the read reached end of file or that an
1025 * error was encountered during the read so that the read is partial. 0 means
1026 * nothing was read (also return 0 when @count is 0).
1027 *
1028 * On error and nothing has been read, return -1 with errno set appropriately
1029 * to the return code of ntfs_pread(), or to EINVAL in case of invalid
1030 * arguments.
1031 *
1032 * NOTE: If we encounter EOF while reading we return EIO because we assume that
1033 * the run list must point to valid locations within the ntfs volume.
1034 */
1035 s64 ntfs_rl_pread(const ntfs_volume *vol, const runlist_element *rl,
1036 const s64 pos, s64 count, void *b)
1037 {
1038 s64 bytes_read, to_read, ofs, total;
1039 int err = EIO;
1040
1041 if (!vol || !rl || pos < 0 || count < 0) {
1042 errno = EINVAL;
1043 return -1;
1044 }
1045 if (!count)
1046 return count;
1047 /* Seek in @rl to the run containing @pos. */
1048 for (ofs = 0; rl->length && (ofs + (rl->length <<
1049 vol->cluster_size_bits) <= pos); rl++)
1050 ofs += (rl->length << vol->cluster_size_bits);
1051 /* Offset in the run at which to begin reading. */
1052 ofs = pos - ofs;
1053 for (total = 0LL; count; rl++, ofs = 0) {
1054 if (!rl->length)
1055 goto rl_err_out;
1056 if (rl->lcn < (LCN)0) {
1057 if (rl->lcn != (LCN)LCN_HOLE)
1058 goto rl_err_out;
1059 /* It is a hole. Just fill buffer @b with zeroes. */
1060 to_read = min(count, (rl->length <<
1061 vol->cluster_size_bits) - ofs);
1062 memset(b, 0, to_read);
1063 /* Update counters and proceed with next run. */
1064 total += to_read;
1065 count -= to_read;
1066 b = (u8*)b + to_read;
1067 continue;
1068 }
1069 /* It is a real lcn, read it from the volume. */
1070 to_read = min(count, (rl->length << vol->cluster_size_bits) -
1071 ofs);
1072 retry:
1073 bytes_read = ntfs_pread(vol->u.dev, (rl->lcn <<
1074 vol->cluster_size_bits) + ofs, to_read, b);
1075 /* If everything ok, update progress counters and continue. */
1076 if (bytes_read > 0) {
1077 total += bytes_read;
1078 count -= bytes_read;
1079 b = (u8*)b + bytes_read;
1080 continue;
1081 }
1082 /* If the syscall was interrupted, try again. */
1083 if (bytes_read == (s64)-1 && errno == EINTR)
1084 goto retry;
1085 if (bytes_read == (s64)-1)
1086 err = errno;
1087 goto rl_err_out;
1088 }
1089 /* Finally, return the number of bytes read. */
1090 return total;
1091 rl_err_out:
1092 if (total)
1093 return total;
1094 errno = err;
1095 return -1;
1096 }
1097
1098 /**
1099 * ntfs_rl_pwrite - scatter write to disk
1100 * @vol: ntfs volume to write to
1101 * @rl: runlist specifying where to write the data to
1102 * @pos: byte position within runlist @rl at which to begin the write
1103 * @count: number of bytes to write
1104 * @b: data buffer to write to disk
1105 *
1106 * This function will write @count bytes from data buffer @b to the volume @vol
1107 * scattering the data as specified by the runlist @rl. The write begins at
1108 * offset @pos into the runlist @rl.
1109 *
1110 * On success, return the number of successfully written bytes. If this number
1111 * is lower than @count this means that the write has been interrupted in
1112 * flight or that an error was encountered during the write so that the write
1113 * is partial. 0 means nothing was written (also return 0 when @count is 0).
1114 *
1115 * On error and nothing has been written, return -1 with errno set
1116 * appropriately to the return code of ntfs_pwrite(), or to to EINVAL in case
1117 * of invalid arguments.
1118 */
1119 s64 ntfs_rl_pwrite(const ntfs_volume *vol, const runlist_element *rl,
1120 const s64 pos, s64 count, void *b)
1121 {
1122 s64 written, to_write, ofs, total;
1123 int err = EIO;
1124
1125 if (!vol || !rl || pos < 0 || count < 0) {
1126 errno = EINVAL;
1127 return -1;
1128 }
1129 if (!count)
1130 return count;
1131 /* Seek in @rl to the run containing @pos. */
1132 for (ofs = 0; rl->length && (ofs + (rl->length <<
1133 vol->cluster_size_bits) <= pos); rl++)
1134 ofs += (rl->length << vol->cluster_size_bits);
1135 /* Offset in the run at which to begin writing. */
1136 ofs = pos - ofs;
1137 for (total = 0LL; count; rl++, ofs = 0) {
1138 if (!rl->length)
1139 goto rl_err_out;
1140 if (rl->lcn < (LCN)0) {
1141 s64 t;
1142 int cnt;
1143
1144 if (rl->lcn != (LCN)LCN_HOLE)
1145 goto rl_err_out;
1146 /*
1147 * It is a hole. Check if the buffer is zero in this
1148 * region and if not abort with error.
1149 */
1150 to_write = min(count, (rl->length <<
1151 vol->cluster_size_bits) - ofs);
1152 written = to_write / sizeof(unsigned long);
1153 for (t = 0; t < written; t++) {
1154 if (((unsigned long*)b)[t])
1155 goto rl_err_out;
1156 }
1157 cnt = to_write & (sizeof(unsigned long) - 1);
1158 if (cnt) {
1159 int i;
1160 u8 *b2;
1161
1162 b2 = (u8*)b + (to_write &
1163 ~(sizeof(unsigned long) - 1));
1164 for (i = 0; i < cnt; i++) {
1165 if (b2[i])
1166 goto rl_err_out;
1167 }
1168 }
1169 /*
1170 * The buffer region is zero, update progress counters
1171 * and proceed with next run.
1172 */
1173 total += to_write;
1174 count -= to_write;
1175 b = (u8*)b + to_write;
1176 continue;
1177 }
1178 /* It is a real lcn, write it to the volume. */
1179 to_write = min(count, (rl->length << vol->cluster_size_bits) -
1180 ofs);
1181 retry:
1182 if (!NVolReadOnly(vol))
1183 written = ntfs_pwrite(vol->u.dev, (rl->lcn <<
1184 vol->cluster_size_bits) + ofs,
1185 to_write, b);
1186 else
1187 written = to_write;
1188 /* If everything ok, update progress counters and continue. */
1189 if (written > 0) {
1190 total += written;
1191 count -= written;
1192 b = (u8*)b + written;
1193 continue;
1194 }
1195 /* If the syscall was interrupted, try again. */
1196 if (written == (s64)-1 && errno == EINTR)
1197 goto retry;
1198 if (written == (s64)-1)
1199 err = errno;
1200 goto rl_err_out;
1201 }
1202 /* Finally, return the number of bytes written. */
1203 return total;
1204 rl_err_out:
1205 if (total)
1206 return total;
1207 errno = err;
1208 return -1;
1209 }
1210
1211 /**
1212 * ntfs_rl_fill_zero - fill given region with zeroes
1213 * @vol: ntfs volume to write to
1214 * @rl: runlist specifying where to write zeroes to
1215 * @pos: byte position within runlist @rl at which to begin the zeroing
1216 * @count: number of bytes to fill with zeros
1217 *
1218 * Return 0 on success and -1 on error with errno set to the error code.
1219 */
1220 int ntfs_rl_fill_zero(const ntfs_volume *vol, const runlist *rl, s64 pos,
1221 const s64 count)
1222 {
1223 char *buf;
1224 s64 written, size, end = pos + count;
1225 int ret = 0;
1226
1227 ntfs_log_trace("pos %lld, count %lld\n", (long long)pos,
1228 (long long)count);
1229
1230 if (!vol || !rl || pos < 0 || count < 0) {
1231 errno = EINVAL;
1232 return -1;
1233 }
1234
1235 buf = ntfs_calloc(NTFS_BUF_SIZE);
1236 if (!buf)
1237 return -1;
1238
1239 while (pos < end) {
1240 size = min(end - pos, NTFS_BUF_SIZE);
1241 written = ntfs_rl_pwrite(vol, rl, pos, size, buf);
1242 if (written <= 0) {
1243 ntfs_log_perror("Failed to zero space");
1244 ret = -1;
1245 break;
1246 }
1247 pos += written;
1248 }
1249 free(buf);
1250 return ret;
1251 }
1252
1253 /**
1254 * ntfs_get_nr_significant_bytes - get number of bytes needed to store a number
1255 * @n: number for which to get the number of bytes for
1256 *
1257 * Return the number of bytes required to store @n unambiguously as
1258 * a signed number.
1259 *
1260 * This is used in the context of the mapping pairs array to determine how
1261 * many bytes will be needed in the array to store a given logical cluster
1262 * number (lcn) or a specific run length.
1263 *
1264 * Return the number of bytes written. This function cannot fail.
1265 */
1266 int ntfs_get_nr_significant_bytes(const s64 n)
1267 {
1268 s64 l = n;
1269 int i;
1270 s8 j;
1271
1272 i = 0;
1273 do {
1274 l >>= 8;
1275 i++;
1276 } while (l != 0LL && l != -1LL);
1277 j = (n >> 8 * (i - 1)) & 0xff;
1278 /* If the sign bit is wrong, we need an extra byte. */
1279 if ((n < 0LL && j >= 0) || (n > 0LL && j < 0))
1280 i++;
1281 return i;
1282 }
1283
1284 /**
1285 * ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array
1286 * @vol: ntfs volume (needed for the ntfs version)
1287 * @rl: runlist for which to determine the size of the mapping pairs
1288 * @start_vcn: vcn at which to start the mapping pairs array
1289 *
1290 * Walk the runlist @rl and calculate the size in bytes of the mapping pairs
1291 * array corresponding to the runlist @rl, starting at vcn @start_vcn. This
1292 * for example allows us to allocate a buffer of the right size when building
1293 * the mapping pairs array.
1294 *
1295 * If @rl is NULL, just return 1 (for the single terminator byte).
1296 *
1297 * Return the calculated size in bytes on success. On error, return -1 with
1298 * errno set to the error code. The following error codes are defined:
1299 * EINVAL - Run list contains unmapped elements. Make sure to only pass
1300 * fully mapped runlists to this function.
1301 * - @start_vcn is invalid.
1302 * EIO - The runlist is corrupt.
1303 */
1304 int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol,
1305 const runlist_element *rl, const VCN start_vcn)
1306 {
1307 LCN prev_lcn;
1308 int rls;
1309
1310 if (start_vcn < 0) {
1311 ntfs_log_trace("start_vcn %lld (should be >= 0)\n",
1312 (long long) start_vcn);
1313 errno = EINVAL;
1314 return -1;
1315 }
1316 if (!rl) {
1317 if (start_vcn) {
1318 ntfs_log_trace("rl NULL, start_vcn %lld (should be > 0)\n",
1319 (long long) start_vcn);
1320 errno = EINVAL;
1321 return -1;
1322 }
1323 return 1;
1324 }
1325 /* Skip to runlist element containing @start_vcn. */
1326 while (rl->length && start_vcn >= rl[1].vcn)
1327 rl++;
1328 if ((!rl->length && start_vcn > rl->vcn) || start_vcn < rl->vcn) {
1329 errno = EINVAL;
1330 return -1;
1331 }
1332 prev_lcn = 0;
1333 /* Always need the terminating zero byte. */
1334 rls = 1;
1335 /* Do the first partial run if present. */
1336 if (start_vcn > rl->vcn) {
1337 s64 delta;
1338
1339 /* We know rl->length != 0 already. */
1340 if (rl->length < 0 || rl->lcn < LCN_HOLE)
1341 goto err_out;
1342 delta = start_vcn - rl->vcn;
1343 /* Header byte + length. */
1344 rls += 1 + ntfs_get_nr_significant_bytes(rl->length - delta);
1345 /*
1346 * If the logical cluster number (lcn) denotes a hole and we
1347 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1348 * zero space. On earlier NTFS versions we just store the lcn.
1349 * Note: this assumes that on NTFS 1.2-, holes are stored with
1350 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
1351 */
1352 if (rl->lcn >= 0 || vol->major_ver < 3) {
1353 prev_lcn = rl->lcn;
1354 if (rl->lcn >= 0)
1355 prev_lcn += delta;
1356 /* Change in lcn. */
1357 rls += ntfs_get_nr_significant_bytes(prev_lcn);
1358 }
1359 /* Go to next runlist element. */
1360 rl++;
1361 }
1362 /* Do the full runs. */
1363 for (; rl->length; rl++) {
1364 if (rl->length < 0 || rl->lcn < LCN_HOLE)
1365 goto err_out;
1366 /* Header byte + length. */
1367 rls += 1 + ntfs_get_nr_significant_bytes(rl->length);
1368 /*
1369 * If the logical cluster number (lcn) denotes a hole and we
1370 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1371 * zero space. On earlier NTFS versions we just store the lcn.
1372 * Note: this assumes that on NTFS 1.2-, holes are stored with
1373 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
1374 */
1375 if (rl->lcn >= 0 || vol->major_ver < 3) {
1376 /* Change in lcn. */
1377 rls += ntfs_get_nr_significant_bytes(rl->lcn -
1378 prev_lcn);
1379 prev_lcn = rl->lcn;
1380 }
1381 }
1382 return rls;
1383 err_out:
1384 if (rl->lcn == LCN_RL_NOT_MAPPED)
1385 errno = EINVAL;
1386 else
1387 errno = EIO;
1388 return -1;
1389 }
1390
1391 /**
1392 * ntfs_write_significant_bytes - write the significant bytes of a number
1393 * @dst: destination buffer to write to
1394 * @dst_max: pointer to last byte of destination buffer for bounds checking
1395 * @n: number whose significant bytes to write
1396 *
1397 * Store in @dst, the minimum bytes of the number @n which are required to
1398 * identify @n unambiguously as a signed number, taking care not to exceed
1399 * @dest_max, the maximum position within @dst to which we are allowed to
1400 * write.
1401 *
1402 * This is used when building the mapping pairs array of a runlist to compress
1403 * a given logical cluster number (lcn) or a specific run length to the minimum
1404 * size possible.
1405 *
1406 * Return the number of bytes written on success. On error, i.e. the
1407 * destination buffer @dst is too small, return -1 with errno set ENOSPC.
1408 */
1409 int ntfs_write_significant_bytes(u8 *dst, const u8 *dst_max, const s64 n)
1410 {
1411 s64 l = n;
1412 int i;
1413 s8 j;
1414
1415 i = 0;
1416 do {
1417 if (dst > dst_max)
1418 goto err_out;
1419 *dst++ = l & 0xffLL;
1420 l >>= 8;
1421 i++;
1422 } while (l != 0LL && l != -1LL);
1423 j = (n >> 8 * (i - 1)) & 0xff;
1424 /* If the sign bit is wrong, we need an extra byte. */
1425 if (n < 0LL && j >= 0) {
1426 if (dst > dst_max)
1427 goto err_out;
1428 i++;
1429 *dst = (u8)-1;
1430 } else if (n > 0LL && j < 0) {
1431 if (dst > dst_max)
1432 goto err_out;
1433 i++;
1434 *dst = 0;
1435 }
1436 return i;
1437 err_out:
1438 errno = ENOSPC;
1439 return -1;
1440 }
1441
1442 /**
1443 * ntfs_mapping_pairs_build - build the mapping pairs array from a runlist
1444 * @vol: ntfs volume (needed for the ntfs version)
1445 * @dst: destination buffer to which to write the mapping pairs array
1446 * @dst_len: size of destination buffer @dst in bytes
1447 * @rl: runlist for which to build the mapping pairs array
1448 * @start_vcn: vcn at which to start the mapping pairs array
1449 * @stop_vcn: first vcn outside destination buffer on success or ENOSPC error
1450 *
1451 * Create the mapping pairs array from the runlist @rl, starting at vcn
1452 * @start_vcn and save the array in @dst. @dst_len is the size of @dst in
1453 * bytes and it should be at least equal to the value obtained by calling
1454 * ntfs_get_size_for_mapping_pairs().
1455 *
1456 * If @rl is NULL, just write a single terminator byte to @dst.
1457 *
1458 * On success or ENOSPC error, if @stop_vcn is not NULL, *@stop_vcn is set to
1459 * the first vcn outside the destination buffer. Note that on error @dst has
1460 * been filled with all the mapping pairs that will fit, thus it can be treated
1461 * as partial success, in that a new attribute extent needs to be created or the
1462 * next extent has to be used and the mapping pairs build has to be continued
1463 * with @start_vcn set to *@stop_vcn.
1464 *
1465 * Return 0 on success. On error, return -1 with errno set to the error code.
1466 * The following error codes are defined:
1467 * EINVAL - Run list contains unmapped elements. Make sure to only pass
1468 * fully mapped runlists to this function.
1469 * - @start_vcn is invalid.
1470 * EIO - The runlist is corrupt.
1471 * ENOSPC - The destination buffer is too small.
1472 */
1473 int ntfs_mapping_pairs_build(const ntfs_volume *vol, u8 *dst,
1474 const int dst_len, const runlist_element *rl,
1475 const VCN start_vcn, VCN *const stop_vcn)
1476 {
1477 LCN prev_lcn;
1478 u8 *dst_max, *dst_next;
1479 s8 len_len, lcn_len;
1480
1481 if (start_vcn < 0)
1482 goto val_err;
1483 if (!rl) {
1484 if (start_vcn)
1485 goto val_err;
1486 if (stop_vcn)
1487 *stop_vcn = 0;
1488 if (dst_len < 1) {
1489 errno = ENOSPC;
1490 return -1;
1491 }
1492 /* Terminator byte. */
1493 *dst = 0;
1494 return 0;
1495 }
1496 /* Skip to runlist element containing @start_vcn. */
1497 while (rl->length && start_vcn >= rl[1].vcn)
1498 rl++;
1499 if ((!rl->length && start_vcn > rl->vcn) || start_vcn < rl->vcn)
1500 goto val_err;
1501 /*
1502 * @dst_max is used for bounds checking in
1503 * ntfs_write_significant_bytes().
1504 */
1505 dst_max = dst + dst_len - 1;
1506 prev_lcn = 0;
1507 /* Do the first partial run if present. */
1508 if (start_vcn > rl->vcn) {
1509 s64 delta;
1510
1511 /* We know rl->length != 0 already. */
1512 if (rl->length < 0 || rl->lcn < LCN_HOLE)
1513 goto err_out;
1514 delta = start_vcn - rl->vcn;
1515 /* Write length. */
1516 len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1517 rl->length - delta);
1518 if (len_len < 0)
1519 goto size_err;
1520 /*
1521 * If the logical cluster number (lcn) denotes a hole and we
1522 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1523 * zero space. On earlier NTFS versions we just write the lcn
1524 * change. FIXME: Do we need to write the lcn change or just
1525 * the lcn in that case? Not sure as I have never seen this
1526 * case on NT4. - We assume that we just need to write the lcn
1527 * change until someone tells us otherwise... (AIA)
1528 */
1529 if (rl->lcn >= 0 || vol->major_ver < 3) {
1530 prev_lcn = rl->lcn;
1531 if (rl->lcn >= 0)
1532 prev_lcn += delta;
1533 /* Write change in lcn. */
1534 lcn_len = ntfs_write_significant_bytes(dst + 1 +
1535 len_len, dst_max, prev_lcn);
1536 if (lcn_len < 0)
1537 goto size_err;
1538 } else
1539 lcn_len = 0;
1540 dst_next = dst + len_len + lcn_len + 1;
1541 if (dst_next > dst_max)
1542 goto size_err;
1543 /* Update header byte. */
1544 *dst = lcn_len << 4 | len_len;
1545 /* Position at next mapping pairs array element. */
1546 dst = dst_next;
1547 /* Go to next runlist element. */
1548 rl++;
1549 }
1550 /* Do the full runs. */
1551 for (; rl->length; rl++) {
1552 if (rl->length < 0 || rl->lcn < LCN_HOLE)
1553 goto err_out;
1554 /* Write length. */
1555 len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1556 rl->length);
1557 if (len_len < 0)
1558 goto size_err;
1559 /*
1560 * If the logical cluster number (lcn) denotes a hole and we
1561 * are on NTFS 3.0+, we don't store it at all, i.e. we need
1562 * zero space. On earlier NTFS versions we just write the lcn
1563 * change. FIXME: Do we need to write the lcn change or just
1564 * the lcn in that case? Not sure as I have never seen this
1565 * case on NT4. - We assume that we just need to write the lcn
1566 * change until someone tells us otherwise... (AIA)
1567 */
1568 if (rl->lcn >= 0 || vol->major_ver < 3) {
1569 /* Write change in lcn. */
1570 lcn_len = ntfs_write_significant_bytes(dst + 1 +
1571 len_len, dst_max, rl->lcn - prev_lcn);
1572 if (lcn_len < 0)
1573 goto size_err;
1574 prev_lcn = rl->lcn;
1575 } else
1576 lcn_len = 0;
1577 dst_next = dst + len_len + lcn_len + 1;
1578 if (dst_next > dst_max)
1579 goto size_err;
1580 /* Update header byte. */
1581 *dst = lcn_len << 4 | len_len;
1582 /* Position at next mapping pairs array element. */
1583 dst += 1 + len_len + lcn_len;
1584 }
1585 /* Set stop vcn. */
1586 if (stop_vcn)
1587 *stop_vcn = rl->vcn;
1588 /* Add terminator byte. */
1589 *dst = 0;
1590 return 0;
1591 size_err:
1592 /* Set stop vcn. */
1593 if (stop_vcn)
1594 *stop_vcn = rl->vcn;
1595 /* Add terminator byte. */
1596 *dst = 0;
1597 errno = ENOSPC;
1598 return -1;
1599 val_err:
1600 errno = EINVAL;
1601 return -1;
1602 err_out:
1603 if (rl->lcn == LCN_RL_NOT_MAPPED)
1604 errno = EINVAL;
1605 else
1606 errno = EIO;
1607 return -1;
1608 }
1609
1610 /**
1611 * ntfs_rl_truncate - truncate a runlist starting at a specified vcn
1612 * @arl: address of runlist to truncate
1613 * @start_vcn: first vcn which should be cut off
1614 *
1615 * Truncate the runlist *@arl starting at vcn @start_vcn as well as the memory
1616 * buffer holding the runlist.
1617 *
1618 * Return 0 on success and -1 on error with errno set to the error code.
1619 *
1620 * NOTE: @arl is the address of the runlist. We need the address so we can
1621 * modify the pointer to the runlist with the new, reallocated memory buffer.
1622 */
1623 int ntfs_rl_truncate(runlist **arl, const VCN start_vcn)
1624 {
1625 runlist *rl;
1626
1627 if (!arl || !*arl) {
1628 errno = EINVAL;
1629 ntfs_log_perror("rl_truncate error: arl: %p *arl: %p", arl, *arl);
1630 return -1;
1631 }
1632
1633 rl = *arl;
1634
1635 if (start_vcn < rl->vcn) {
1636 errno = EINVAL;
1637 ntfs_log_perror("Start_vcn lies outside front of runlist");
1638 return -1;
1639 }
1640
1641 /* Find the starting vcn in the run list. */
1642 while (rl->length) {
1643 if (start_vcn < rl[1].vcn)
1644 break;
1645 rl++;
1646 }
1647
1648 if (!rl->length) {
1649 errno = EIO;
1650 ntfs_log_trace("Truncating already truncated runlist?\n");
1651 return -1;
1652 }
1653
1654 /* Truncate the run. */
1655 rl->length = start_vcn - rl->vcn;
1656
1657 /*
1658 * If a run was partially truncated, make the following runlist
1659 * element a terminator instead of the truncated runlist
1660 * element itself.
1661 */
1662 if (rl->length) {
1663 ++rl;
1664 rl->vcn = start_vcn;
1665 rl->length = 0;
1666 }
1667 rl->lcn = (LCN)LCN_ENOENT;
1668 return 0;
1669 }
1670
1671 /**
1672 * ntfs_rl_sparse - check whether runlist have sparse regions or not.
1673 * @rl: runlist to check
1674 *
1675 * This function just skips not mapped regions assuming they are not sparse,
1676 * so you need to ensure that runlist is fully mapped if you want perform full
1677 * check.
1678 *
1679 * Return 1 if have, 0 if not, -1 on error with errno set to the error code.
1680 */
1681 int ntfs_rl_sparse(runlist *rl)
1682 {
1683 runlist *rlc;
1684
1685 if (!rl) {
1686 ntfs_log_trace("Invalid argument passed.\n");
1687 errno = EINVAL;
1688 return -1;
1689 }
1690
1691 for (rlc = rl; rlc->length; rlc++) {
1692 if (rlc->lcn < 0) {
1693 if (rlc->lcn == LCN_RL_NOT_MAPPED)
1694 continue;
1695 if (rlc->lcn != LCN_HOLE) {
1696 ntfs_log_trace("Bad runlist.\n");
1697 errno = EIO;
1698 return -1;
1699 }
1700 return 1;
1701 }
1702 }
1703 return 0;
1704 }
1705
1706 /**
1707 * ntfs_rl_get_compressed_size - calculate length of non sparse regions
1708 * @vol: ntfs volume (need for cluster size)
1709 * @rl: runlist to calculate for
1710 *
1711 * Return compressed size or -1 on error with errno set to the error code.
1712 */
1713 s64 ntfs_rl_get_compressed_size(ntfs_volume *vol, runlist *rl)
1714 {
1715 runlist *rlc;
1716 s64 ret = 0;
1717
1718 if (!rl) {
1719 ntfs_log_trace("Invalid argument passed.\n");
1720 errno = EINVAL;
1721 return -1;
1722 }
1723
1724 for (rlc = rl; rlc->length; rlc++) {
1725 if (rlc->lcn < 0) {
1726 if (rlc->lcn != LCN_HOLE) {
1727 ntfs_log_trace("Received unmapped runlist.\n");
1728 errno = EINVAL;
1729 return -1;
1730 }
1731 } else
1732 ret += rlc->length;
1733 }
1734 return ret << vol->cluster_size_bits;
1735 }
1736
1737
1738 #ifdef NTFS_TEST
1739 /**
1740 * test_rl_helper
1741 */
1742 #define MKRL(R,V,L,S) \
1743 (R)->vcn = V; \
1744 (R)->lcn = L; \
1745 (R)->length = S;
1746 /*
1747 }
1748 */
1749 /**
1750 * test_rl_dump_runlist - Runlist test: Display the contents of a runlist
1751 * @rl:
1752 *
1753 * Description...
1754 *
1755 * Returns:
1756 */
1757 static void test_rl_dump_runlist(const runlist_element *rl)
1758 {
1759 int abbr = 0; /* abbreviate long lists */
1760 int len = 0;
1761 int i;
1762 const char *lcn_str[5] = { "HOLE", "NOTMAP", "ENOENT", "XXXX" };
1763
1764 if (!rl) {
1765 printf(" Run list not present.\n");
1766 return;
1767 }
1768
1769 if (abbr)
1770 for (len = 0; rl[len].length; len++) ;
1771
1772 printf(" VCN LCN len\n");
1773 for (i = 0; ; i++, rl++) {
1774 LCN lcn = rl->lcn;
1775
1776 if ((abbr) && (len > 20)) {
1777 if (i == 4)
1778 printf(" ...\n");
1779 if ((i > 3) && (i < (len - 3)))
1780 continue;
1781 }
1782
1783 if (lcn < (LCN)0) {
1784 int ind = -lcn - 1;
1785
1786 if (ind > -LCN_ENOENT - 1)
1787 ind = 3;
1788 printf("%8lld %8s %8lld\n",
1789 rl->vcn, lcn_str[ind], rl->length);
1790 } else
1791 printf("%8lld %8lld %8lld\n",
1792 rl->vcn, rl->lcn, rl->length);
1793 if (!rl->length)
1794 break;
1795 }
1796 if ((abbr) && (len > 20))
1797 printf(" (%d entries)\n", len+1);
1798 printf("\n");
1799 }
1800
1801 /**
1802 * test_rl_runlists_merge - Runlist test: Merge two runlists
1803 * @drl:
1804 * @srl:
1805 *
1806 * Description...
1807 *
1808 * Returns:
1809 */
1810 static runlist_element * test_rl_runlists_merge(runlist_element *drl, runlist_element *srl)
1811 {
1812 runlist_element *res = NULL;
1813
1814 printf("dst:\n");
1815 test_rl_dump_runlist(drl);
1816 printf("src:\n");
1817 test_rl_dump_runlist(srl);
1818
1819 res = ntfs_runlists_merge(drl, srl);
1820
1821 printf("res:\n");
1822 test_rl_dump_runlist(res);
1823
1824 return res;
1825 }
1826
1827 /**
1828 * test_rl_read_buffer - Runlist test: Read a file containing a runlist
1829 * @file:
1830 * @buf:
1831 * @bufsize:
1832 *
1833 * Description...
1834 *
1835 * Returns:
1836 */
1837 static int test_rl_read_buffer(const char *file, u8 *buf, int bufsize)
1838 {
1839 FILE *fptr;
1840
1841 fptr = fopen(file, "r");
1842 if (!fptr) {
1843 printf("open %s\n", file);
1844 return 0;
1845 }
1846
1847 if (fread(buf, bufsize, 1, fptr) == 99) {
1848 printf("read %s\n", file);
1849 return 0;
1850 }
1851
1852 fclose(fptr);
1853 return 1;
1854 }
1855
1856 /**
1857 * test_rl_pure_src - Runlist test: Complicate the simple tests a little
1858 * @contig:
1859 * @multi:
1860 * @vcn:
1861 * @len:
1862 *
1863 * Description...
1864 *
1865 * Returns:
1866 */
1867 static runlist_element * test_rl_pure_src(BOOL contig, BOOL multi, int vcn, int len)
1868 {
1869 runlist_element *result;
1870 int fudge;
1871
1872 if (contig)
1873 fudge = 0;
1874 else
1875 fudge = 999;
1876
1877 result = ntfs_malloc(4096);
1878 if (!result)
1879 return NULL;
1880
1881 if (multi) {
1882 MKRL(result+0, vcn + (0*len/4), fudge + vcn + 1000 + (0*len/4), len / 4)
1883 MKRL(result+1, vcn + (1*len/4), fudge + vcn + 1000 + (1*len/4), len / 4)
1884 MKRL(result+2, vcn + (2*len/4), fudge + vcn + 1000 + (2*len/4), len / 4)
1885 MKRL(result+3, vcn + (3*len/4), fudge + vcn + 1000 + (3*len/4), len / 4)
1886 MKRL(result+4, vcn + (4*len/4), LCN_RL_NOT_MAPPED, 0)
1887 } else {
1888 MKRL(result+0, vcn, fudge + vcn + 1000, len)
1889 MKRL(result+1, vcn + len, LCN_RL_NOT_MAPPED, 0)
1890 }
1891 return result;
1892 }
1893
1894 /**
1895 * test_rl_pure_test - Runlist test: Perform tests using simple runlists
1896 * @test:
1897 * @contig:
1898 * @multi:
1899 * @vcn:
1900 * @len:
1901 * @file:
1902 * @size:
1903 *
1904 * Description...
1905 *
1906 * Returns:
1907 */
1908 static void test_rl_pure_test(int test, BOOL contig, BOOL multi, int vcn, int len, runlist_element *file, int size)
1909 {
1910 runlist_element *src;
1911 runlist_element *dst;
1912 runlist_element *res;
1913
1914 src = test_rl_pure_src(contig, multi, vcn, len);
1915 dst = malloc(4096);
1916
1917 memcpy(dst, file, size);
1918
1919 printf("Test %2d ----------\n", test);
1920 res = test_rl_runlists_merge(dst, src);
1921
1922 free(res);
1923 }
1924
1925 /**
1926 * test_rl_pure - Runlist test: Create tests using simple runlists
1927 * @contig:
1928 * @multi:
1929 *
1930 * Description...
1931 *
1932 * Returns:
1933 */
1934 static void test_rl_pure(char *contig, char *multi)
1935 {
1936 /* VCN, LCN, len */
1937 static runlist_element file1[] = {
1938 { 0, -1, 100 }, /* HOLE */
1939 { 100, 1100, 100 }, /* DATA */
1940 { 200, -1, 100 }, /* HOLE */
1941 { 300, 1300, 100 }, /* DATA */
1942 { 400, -1, 100 }, /* HOLE */
1943 { 500, -3, 0 } /* NOENT */
1944 };
1945 static runlist_element file2[] = {
1946 { 0, 1000, 100 }, /* DATA */
1947 { 100, -1, 100 }, /* HOLE */
1948 { 200, -3, 0 } /* NOENT */
1949 };
1950 static runlist_element file3[] = {
1951 { 0, 1000, 100 }, /* DATA */
1952 { 100, -3, 0 } /* NOENT */
1953 };
1954 static runlist_element file4[] = {
1955 { 0, -3, 0 } /* NOENT */
1956 };
1957 static runlist_element file5[] = {
1958 { 0, -2, 100 }, /* NOTMAP */
1959 { 100, 1100, 100 }, /* DATA */
1960 { 200, -2, 100 }, /* NOTMAP */
1961 { 300, 1300, 100 }, /* DATA */
1962 { 400, -2, 100 }, /* NOTMAP */
1963 { 500, -3, 0 } /* NOENT */
1964 };
1965 static runlist_element file6[] = {
1966 { 0, 1000, 100 }, /* DATA */
1967 { 100, -2, 100 }, /* NOTMAP */
1968 { 200, -3, 0 } /* NOENT */
1969 };
1970 BOOL c, m;
1971
1972 if (strcmp(contig, "contig") == 0)
1973 c = TRUE;
1974 else if (strcmp(contig, "noncontig") == 0)
1975 c = FALSE;
1976 else {
1977 printf("rl pure [contig|noncontig] [single|multi]\n");
1978 return;
1979 }
1980 if (strcmp(multi, "multi") == 0)
1981 m = TRUE;
1982 else if (strcmp(multi, "single") == 0)
1983 m = FALSE;
1984 else {
1985 printf("rl pure [contig|noncontig] [single|multi]\n");
1986 return;
1987 }
1988
1989 test_rl_pure_test(1, c, m, 0, 40, file1, sizeof(file1));
1990 test_rl_pure_test(2, c, m, 40, 40, file1, sizeof(file1));
1991 test_rl_pure_test(3, c, m, 60, 40, file1, sizeof(file1));
1992 test_rl_pure_test(4, c, m, 0, 100, file1, sizeof(file1));
1993 test_rl_pure_test(5, c, m, 200, 40, file1, sizeof(file1));
1994 test_rl_pure_test(6, c, m, 240, 40, file1, sizeof(file1));
1995 test_rl_pure_test(7, c, m, 260, 40, file1, sizeof(file1));
1996 test_rl_pure_test(8, c, m, 200, 100, file1, sizeof(file1));
1997 test_rl_pure_test(9, c, m, 400, 40, file1, sizeof(file1));
1998 test_rl_pure_test(10, c, m, 440, 40, file1, sizeof(file1));
1999 test_rl_pure_test(11, c, m, 460, 40, file1, sizeof(file1));
2000 test_rl_pure_test(12, c, m, 400, 100, file1, sizeof(file1));
2001 test_rl_pure_test(13, c, m, 160, 100, file2, sizeof(file2));
2002 test_rl_pure_test(14, c, m, 100, 140, file2, sizeof(file2));
2003 test_rl_pure_test(15, c, m, 200, 40, file2, sizeof(file2));
2004 test_rl_pure_test(16, c, m, 240, 40, file2, sizeof(file2));
2005 test_rl_pure_test(17, c, m, 100, 40, file3, sizeof(file3));
2006 test_rl_pure_test(18, c, m, 140, 40, file3, sizeof(file3));
2007 test_rl_pure_test(19, c, m, 0, 40, file4, sizeof(file4));
2008 test_rl_pure_test(20, c, m, 40, 40, file4, sizeof(file4));
2009 test_rl_pure_test(21, c, m, 0, 40, file5, sizeof(file5));
2010 test_rl_pure_test(22, c, m, 40, 40, file5, sizeof(file5));
2011 test_rl_pure_test(23, c, m, 60, 40, file5, sizeof(file5));
2012 test_rl_pure_test(24, c, m, 0, 100, file5, sizeof(file5));
2013 test_rl_pure_test(25, c, m, 200, 40, file5, sizeof(file5));
2014 test_rl_pure_test(26, c, m, 240, 40, file5, sizeof(file5));
2015 test_rl_pure_test(27, c, m, 260, 40, file5, sizeof(file5));
2016 test_rl_pure_test(28, c, m, 200, 100, file5, sizeof(file5));
2017 test_rl_pure_test(29, c, m, 400, 40, file5, sizeof(file5));
2018 test_rl_pure_test(30, c, m, 440, 40, file5, sizeof(file5));
2019 test_rl_pure_test(31, c, m, 460, 40, file5, sizeof(file5));
2020 test_rl_pure_test(32, c, m, 400, 100, file5, sizeof(file5));
2021 test_rl_pure_test(33, c, m, 160, 100, file6, sizeof(file6));
2022 test_rl_pure_test(34, c, m, 100, 140, file6, sizeof(file6));
2023 }
2024
2025 /**
2026 * test_rl_zero - Runlist test: Merge a zero-length runlist
2027 *
2028 * Description...
2029 *
2030 * Returns:
2031 */
2032 static void test_rl_zero(void)
2033 {
2034 runlist_element *jim = NULL;
2035 runlist_element *bob = NULL;
2036
2037 bob = calloc(3, sizeof(runlist_element));
2038 if (!bob)
2039 return;
2040
2041 MKRL(bob+0, 10, 99, 5)
2042 MKRL(bob+1, 15, LCN_RL_NOT_MAPPED, 0)
2043
2044 jim = test_rl_runlists_merge(jim, bob);
2045 if (!jim)
2046 return;
2047
2048 free(jim);
2049 }
2050
2051 /**
2052 * test_rl_frag_combine - Runlist test: Perform tests using fragmented files
2053 * @vol:
2054 * @attr1:
2055 * @attr2:
2056 * @attr3:
2057 *
2058 * Description...
2059 *
2060 * Returns:
2061 */
2062 static void test_rl_frag_combine(ntfs_volume *vol, ATTR_RECORD *attr1, ATTR_RECORD *attr2, ATTR_RECORD *attr3)
2063 {
2064 runlist_element *run1;
2065 runlist_element *run2;
2066 runlist_element *run3;
2067
2068 run1 = ntfs_mapping_pairs_decompress(vol, attr1, NULL);
2069 if (!run1)
2070 return;
2071
2072 run2 = ntfs_mapping_pairs_decompress(vol, attr2, NULL);
2073 if (!run2)
2074 return;
2075
2076 run1 = test_rl_runlists_merge(run1, run2);
2077
2078 run3 = ntfs_mapping_pairs_decompress(vol, attr3, NULL);
2079 if (!run3)
2080 return;
2081
2082 run1 = test_rl_runlists_merge(run1, run3);
2083
2084 free(run1);
2085 }
2086
2087 /**
2088 * test_rl_frag - Runlist test: Create tests using very fragmented files
2089 * @test:
2090 *
2091 * Description...
2092 *
2093 * Returns:
2094 */
2095 static void test_rl_frag(char *test)
2096 {
2097 ntfs_volume vol;
2098 ATTR_RECORD *attr1 = ntfs_malloc(1024);
2099 ATTR_RECORD *attr2 = ntfs_malloc(1024);
2100 ATTR_RECORD *attr3 = ntfs_malloc(1024);
2101
2102 if (!attr1 || !attr2 || !attr3)
2103 goto out;
2104
2105 vol.sb = NULL;
2106 vol.sector_size_bits = 9;
2107 vol.cluster_size = 2048;
2108 vol.cluster_size_bits = 11;
2109 vol.major_ver = 3;
2110
2111 if (!test_rl_read_buffer("runlist-data/attr1.bin", (u8*) attr1, 1024))
2112 goto out;
2113 if (!test_rl_read_buffer("runlist-data/attr2.bin", (u8*) attr2, 1024))
2114 goto out;
2115 if (!test_rl_read_buffer("runlist-data/attr3.bin", (u8*) attr3, 1024))
2116 goto out;
2117
2118 if (strcmp(test, "123") == 0) test_rl_frag_combine(&vol, attr1, attr2, attr3);
2119 else if (strcmp(test, "132") == 0) test_rl_frag_combine(&vol, attr1, attr3, attr2);
2120 else if (strcmp(test, "213") == 0) test_rl_frag_combine(&vol, attr2, attr1, attr3);
2121 else if (strcmp(test, "231") == 0) test_rl_frag_combine(&vol, attr2, attr3, attr1);
2122 else if (strcmp(test, "312") == 0) test_rl_frag_combine(&vol, attr3, attr1, attr2);
2123 else if (strcmp(test, "321") == 0) test_rl_frag_combine(&vol, attr3, attr2, attr1);
2124 else
2125 printf("Frag: No such test '%s'\n", test);
2126
2127 out:
2128 free(attr1);
2129 free(attr2);
2130 free(attr3);
2131 }
2132
2133 /**
2134 * test_rl_main - Runlist test: Program start (main)
2135 * @argc:
2136 * @argv:
2137 *
2138 * Description...
2139 *
2140 * Returns:
2141 */
2142 int test_rl_main(int argc, char *argv[])
2143 {
2144 if ((argc == 2) && (strcmp(argv[1], "zero") == 0)) test_rl_zero();
2145 else if ((argc == 3) && (strcmp(argv[1], "frag") == 0)) test_rl_frag(argv[2]);
2146 else if ((argc == 4) && (strcmp(argv[1], "pure") == 0)) test_rl_pure(argv[2], argv[3]);
2147 else
2148 printf("rl [zero|frag|pure] {args}\n");
2149
2150 return 0;
2151 }
2152
2153 #endif
2154