« back to all changes in this revision
Viewing changes to libntfs/runlist.c
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Bazaar Package Importer
- Author(s): David Martínez Moreno
- Date: 2004-03-12 00:03:30 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20040312000330-xv94ve7yg6bwplwu
Tags: 1.9.0-1
* New upstream release:
- Merged Debian diff with upstream.
- Fixed mkntfs for large volumes.
- Add relocation support to ntfsresize. This modifies the command line
options a little as well as the returned output so applications using
ntfsresize might need modifications before they will work with the
updated ntfsresize.
- Revamped the build system completely.
- Provide always own byteswap constant versions in order to avoid the mess
that some architectures define only some of them (read m68k, ppc,
mips...).
- Made the warnings on 64 bit architectures go away.
- Fixed lots of typos in the documentation.
- Lots of fixes in general.
* Resolved several FTBFS (Fail To Build From Source) bugs (closes: #226989,
#234104). With this, all the architectures go in sync again.
- Merged Debian diff with upstream.
- Fixed mkntfs for large volumes.
- Add relocation support to ntfsresize. This modifies the command line
options a little as well as the returned output so applications using
ntfsresize might need modifications before they will work with the
updated ntfsresize.
- Revamped the build system completely.
- Provide always own byteswap constant versions in order to avoid the mess
that some architectures define only some of them (read m68k, ppc,
mips...).
- Made the warnings on 64 bit architectures go away.
- Fixed lots of typos in the documentation.
- Lots of fixes in general.
* Resolved several FTBFS (Fail To Build From Source) bugs (closes: #226989,
#234104). With this, all the architectures go in sync again.
- files added:
- TODO.libntfs
- include/ntfs
- ntfsprogs
- files removed:
- TODO.mkntfs
- ntfstools
- files modified:
- AUTHORS
added
removed
libntfs/runlist.c
1
/*
2
* runlist.c - Run list handling code. Part of the Linux-NTFS project.
3
*
4
* Copyright (c) 2002-2004 Anton Altaparmakov
5
* 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 "config.h"
24
25
#include <stdio.h>
26
#include <string.h>
27
#include <stdlib.h>
28
#include <errno.h>
29
30
#include "compat.h"
31
32
#include "types.h"
33
#include "attrib.h"
34
#include "volume.h"
35
#include "layout.h"
36
#include "debug.h"
37
#include "device.h"
38
39
/**
40
* Internal:
41
*
42
* ntfs_rl_mm - runlist memmove
43
*/
44
static __inline__ void ntfs_rl_mm(runlist_element *base, int dst, int src,
45
int size)
46
{
47
if ((dst != src) && (size > 0))
48
memmove(base + dst, base + src, size * sizeof(*base));
49
}
50
51
/**
52
* Internal:
53
*
54
* rl_mc - runlist memory copy
55
*/
56
static __inline__ void ntfs_rl_mc(runlist_element *dstbase, int dst,
57
runlist_element *srcbase, int src, int size)
58
{
59
if (size > 0)
60
memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
61
}
62
63
/**
64
* Internal:
65
*
66
* ntfs_rl_realloc - Reallocate memory for runlists
67
* @rl: original runlist
68
* @old_size: number of runlist elements in the original runlist @rl
69
* @new_size: number of runlist elements we need space for
70
*
71
* As the runlists grow, more memory will be required. To prevent large
72
* numbers of small reallocations of memory, this function returns a 4kiB block
73
* of memory.
74
*
75
* N.B. If the new allocation doesn't require a different number of 4kiB
76
* blocks in memory, the function will return the original pointer.
77
*
78
* On success, return a pointer to the newly allocated, or recycled, memory.
79
* On error, return NULL with errno set to the error code.
80
*/
81
static __inline__ runlist_element *ntfs_rl_realloc(runlist_element *rl,
82
int old_size, int new_size)
83
{
84
old_size = (old_size * sizeof(runlist_element) + 0xfff) & ~0xfff;
85
new_size = (new_size * sizeof(runlist_element) + 0xfff) & ~0xfff;
86
if (old_size == new_size)
87
return rl;
88
return realloc(rl, new_size);
89
}
90
91
/**
92
* Internal:
93
*
94
* ntfs_rl_are_mergeable - test if two runlists can be joined together
95
* @dst: original runlist
96
* @src: new runlist to test for mergeability with @dst
97
*
98
* Test if two runlists can be joined together. For this, their VCNs and LCNs
99
* must be adjacent.
100
*
101
* Return: TRUE Success, the runlists can be merged.
102
* FALSE Failure, the runlists cannot be merged.
103
*/
104
static __inline__ BOOL ntfs_rl_are_mergeable(runlist_element *dst,
105
runlist_element *src)
106
{
107
if (!dst || !src) {
108
Dputs("Eeek. ntfs_rl_are_mergeable() invoked with NULL "
109
"pointer!");
110
return FALSE;
111
}
112
113
if ((dst->lcn < 0) || (src->lcn < 0)) /* Are we merging holes? */
114
return FALSE;
115
if ((dst->lcn + dst->length) != src->lcn) /* Are the runs contiguous? */
116
return FALSE;
117
if ((dst->vcn + dst->length) != src->vcn) /* Are the runs misaligned? */
118
return FALSE;
119
120
return TRUE;
121
}
122
123
/**
124
* Internal:
125
*
126
* __ntfs_rl_merge - merge two runlists without testing if they can be merged
127
* @dst: original, destination runlist
128
* @src: new runlist to merge with @dst
129
*
130
* Merge the two runlists, writing into the destination runlist @dst. The
131
* caller must make sure the runlists can be merged or this will corrupt the
132
* destination runlist.
133
*/
134
static __inline__ void __ntfs_rl_merge(runlist_element *dst,
135
runlist_element *src)
136
{
137
dst->length += src->length;
138
}
139
140
/**
141
* Internal:
142
*
143
* ntfs_rl_merge - test if two runlists can be joined together and merge them
144
* @dst: original, destination runlist
145
* @src: new runlist to merge with @dst
146
*
147
* Test if two runlists can be joined together. For this, their VCNs and LCNs
148
* must be adjacent. If they can be merged, perform the merge, writing into
149
* the destination runlist @dst.
150
*
151
* Return: TRUE Success, the runlists have been merged.
152
* FALSE Failure, the runlists cannot be merged and have not been
153
* modified.
154
*/
155
static __inline__ BOOL ntfs_rl_merge(runlist_element *dst,
156
runlist_element *src)
157
{
158
BOOL merge = ntfs_rl_are_mergeable(dst, src);
159
160
if (merge)
161
__ntfs_rl_merge(dst, src);
162
return merge;
163
}
164
165
/**
166
* Internal:
167
*
168
* ntfs_rl_append - append a runlist after a given element
169
* @dst: original runlist to be worked on
170
* @dsize: number of elements in @dst (including end marker)
171
* @src: runlist to be inserted into @dst
172
* @ssize: number of elements in @src (excluding end marker)
173
* @loc: append the new runlist @src after this element in @dst
174
*
175
* Append the runlist @src after element @loc in @dst. Merge the right end of
176
* the new runlist, if necessary. Adjust the size of the hole before the
177
* appended runlist.
178
*
179
* On success, return a pointer to the new, combined, runlist. Note, both
180
* runlists @dst and @src are deallocated before returning so you cannot use
181
* the pointers for anything any more. (Strictly speaking the returned runlist
182
* may be the same as @dst but this is irrelevant.)
183
*
184
* On error, return NULL, with errno set to the error code. Both runlists are
185
* left unmodified.
186
*/
187
static __inline__ runlist_element *ntfs_rl_append(runlist_element *dst,
188
int dsize, runlist_element *src, int ssize, int loc)
189
{
190
BOOL right;
191
int magic;
192
193
if (!dst || !src) {
194
Dputs("Eeek. ntfs_rl_append() invoked with NULL pointer!");
195
errno = EINVAL;
196
return NULL;
197
}
198
199
/* First, check if the right hand end needs merging. */
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 dst;
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
/* FIXME: What does this mean? (AIA) */
216
magic = loc + ssize;
217
218
/* Move the tail of @dst out of the way, then copy in @src. */
219
ntfs_rl_mm(dst, magic + 1, 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[magic + 1].lcn == LCN_ENOENT)
227
dst[magic + 1].vcn = dst[magic].vcn + dst[magic].length;
228
229
return dst;
230
}
231
232
/**
233
* Internal:
234
*
235
* ntfs_rl_insert - insert a runlist into another
236
* @dst: original runlist to be worked on
237
* @dsize: number of elements in @dst (including end marker)
238
* @src: new runlist to be inserted
239
* @ssize: number of elements in @src (excluding end marker)
240
* @loc: insert the new runlist @src before this element in @dst
241
*
242
* Insert the runlist @src before element @loc in the runlist @dst. Merge the
243
* left end of the new runlist, if necessary. Adjust the size of the hole
244
* after the inserted runlist.
245
*
246
* On success, return a pointer to the new, combined, runlist. Note, both
247
* runlists @dst and @src are deallocated before returning so you cannot use
248
* the pointers for anything any more. (Strictly speaking the returned runlist
249
* may be the same as @dst but this is irrelevant.)
250
*
251
* On error, return NULL, with errno set to the error code. Both runlists are
252
* left unmodified.
253
*/
254
static __inline__ runlist_element *ntfs_rl_insert(runlist_element *dst,
255
int dsize, runlist_element *src, int ssize, int loc)
256
{
257
BOOL left = FALSE;
258
BOOL disc = FALSE; /* Discontinuity */
259
BOOL hole = FALSE; /* Following a hole */
260
int magic;
261
262
if (!dst || !src) {
263
Dputs("Eeek. ntfs_rl_insert() invoked with NULL pointer!");
264
errno = EINVAL;
265
return NULL;
266
}
267
268
/* disc => Discontinuity between the end of @dst and the start of @src.
269
* This means we might need to insert a hole.
270
* hole => @dst ends with a hole or an unmapped region which we can
271
* extend to match the discontinuity.
272
*/
273
if (loc == 0)
274
disc = (src[0].vcn > 0);
275
else {
276
s64 merged_length;
277
278
left = ntfs_rl_are_mergeable(dst + loc - 1, src);
279
280
merged_length = dst[loc - 1].length;
281
if (left)
282
merged_length += src->length;
283
284
disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
285
if (disc)
286
hole = (dst[loc - 1].lcn == LCN_HOLE);
287
}
288
289
/* Space required: @dst size + @src size, less one if we merged, plus
290
* one if there was a discontinuity, less one for a trailing hole.
291
*/
292
dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc - hole);
293
if (!dst)
294
return dst;
295
/*
296
* We are guaranteed to succeed from here so can start modifying the
297
* original runlist.
298
*/
299
300
if (left)
301
__ntfs_rl_merge(dst + loc - 1, src);
302
303
/* FIXME: What does this mean? (AIA) */
304
magic = loc + ssize - left + disc - hole;
305
306
/* Move the tail of @dst out of the way, then copy in @src. */
307
ntfs_rl_mm(dst, magic, loc, dsize - loc);
308
ntfs_rl_mc(dst, loc + disc - hole, src, left, ssize - left);
309
310
/* Adjust the VCN of the last run ... */
311
if (dst[magic].lcn <= LCN_HOLE)
312
dst[magic].vcn = dst[magic - 1].vcn + dst[magic - 1].length;
313
/* ... and the length. */
314
if (dst[magic].lcn == LCN_HOLE || dst[magic].lcn == LCN_RL_NOT_MAPPED)
315
dst[magic].length = dst[magic + 1].vcn - dst[magic].vcn;
316
317
/* Writing beyond the end of the file and there's a discontinuity. */
318
if (disc) {
319
if (hole)
320
dst[loc - 1].length = dst[loc].vcn - dst[loc - 1].vcn;
321
else {
322
if (loc > 0) {
323
dst[loc].vcn = dst[loc - 1].vcn +
324
dst[loc - 1].length;
325
dst[loc].length = dst[loc + 1].vcn -
326
dst[loc].vcn;
327
} else {
328
dst[loc].vcn = 0;
329
dst[loc].length = dst[loc + 1].vcn;
330
}
331
dst[loc].lcn = LCN_RL_NOT_MAPPED;
332
}
333
334
magic += hole;
335
336
if (dst[magic].lcn == LCN_ENOENT)
337
dst[magic].vcn = dst[magic - 1].vcn +
338
dst[magic - 1].length;
339
}
340
return dst;
341
}
342
343
/**
344
* Internal:
345
*
346
* ntfs_rl_replace - overwrite a runlist element with another runlist
347
* @dst: original runlist to be worked on
348
* @dsize: number of elements in @dst (including end marker)
349
* @src: new runlist to be inserted
350
* @ssize: number of elements in @src (excluding end marker)
351
* @loc: index in runlist @dst to overwrite with @src
352
*
353
* Replace the runlist element @dst at @loc with @src. Merge the left and
354
* right ends of the inserted runlist, if necessary.
355
*
356
* On success, return a pointer to the new, combined, runlist. Note, both
357
* runlists @dst and @src are deallocated before returning so you cannot use
358
* the pointers for anything any more. (Strictly speaking the returned runlist
359
* may be the same as @dst but this is irrelevant.)
360
*
361
* On error, return NULL, with errno set to the error code. Both runlists are
362
* left unmodified.
363
*/
364
static __inline__ runlist_element *ntfs_rl_replace(runlist_element *dst,
365
int dsize, runlist_element *src, int ssize, int loc)
366
{
367
BOOL left = FALSE;
368
BOOL right;
369
int magic;
370
371
if (!dst || !src) {
372
Dputs("Eeek. ntfs_rl_replace() invoked with NULL pointer!");
373
errno = EINVAL;
374
return NULL;
375
}
376
377
/* First, merge the left and right ends, if necessary. */
378
right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
379
if (loc > 0)
380
left = ntfs_rl_are_mergeable(dst + loc - 1, src);
381
382
/* Allocate some space. We'll need less if the left, right, or both
383
* ends were merged.
384
*/
385
dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left - right);
386
if (!dst)
387
return dst;
388
/*
389
* We are guaranteed to succeed from here so can start modifying the
390
* original runlists.
391
*/
392
if (right)
393
__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
394
if (left)
395
__ntfs_rl_merge(dst + loc - 1, src);
396
397
/* FIXME: What does this mean? (AIA) */
398
magic = loc + ssize - left;
399
400
/* Move the tail of @dst out of the way, then copy in @src. */
401
ntfs_rl_mm(dst, magic, loc + right + 1, dsize - loc - right - 1);
402
ntfs_rl_mc(dst, loc, src, left, ssize - left);
403
404
/* We may have changed the length of the file, so fix the end marker */
405
if (dst[magic].lcn == LCN_ENOENT)
406
dst[magic].vcn = dst[magic - 1].vcn + dst[magic - 1].length;
407
return dst;
408
}
409
410
/**
411
* Internal:
412
*
413
* ntfs_rl_split - insert a runlist into the centre of a hole
414
* @dst: original runlist to be worked on
415
* @dsize: number of elements in @dst (including end marker)
416
* @src: new runlist to be inserted
417
* @ssize: number of elements in @src (excluding end marker)
418
* @loc: index in runlist @dst at which to split and insert @src
419
*
420
* Split the runlist @dst at @loc into two and insert @new in between the two
421
* fragments. No merging of runlists is necessary. Adjust the size of the
422
* holes either side.
423
*
424
* On success, return a pointer to the new, combined, runlist. Note, both
425
* runlists @dst and @src are deallocated before returning so you cannot use
426
* the pointers for anything any more. (Strictly speaking the returned runlist
427
* may be the same as @dst but this is irrelevant.)
428
*
429
* On error, return NULL, with errno set to the error code. Both runlists are
430
* left unmodified.
431
*/
432
static __inline__ runlist_element *ntfs_rl_split(runlist_element *dst,
433
int dsize, runlist_element *src, int ssize, int loc)
434
{
435
if (!dst || !src) {
436
Dputs("Eeek. ntfs_rl_split() invoked with NULL pointer!");
437
errno = EINVAL;
438
return NULL;
439
}
440
441
/* Space required: @dst size + @src size + one new hole. */
442
dst = ntfs_rl_realloc(dst, dsize, dsize + ssize + 1);
443
if (!dst)
444
return dst;
445
/*
446
* We are guaranteed to succeed from here so can start modifying the
447
* original runlists.
448
*/
449
450
/* Move the tail of @dst out of the way, then copy in @src. */
451
ntfs_rl_mm(dst, loc + 1 + ssize, loc, dsize - loc);
452
ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
453
454
/* Adjust the size of the holes either size of @src. */
455
dst[loc].length = dst[loc+1].vcn - dst[loc].vcn;
456
dst[loc+ssize+1].vcn = dst[loc+ssize].vcn + dst[loc+ssize].length;
457
dst[loc+ssize+1].length = dst[loc+ssize+2].vcn - dst[loc+ssize+1].vcn;
458
459
return dst;
460
}
461
462
463
/**
464
* ntfs_runlists_merge - merge two runlists into one
465
* @drl: original runlist to be worked on
466
* @srl: new runlist to be merged into @drl
467
*
468
* First we sanity check the two runlists @srl and @drl to make sure that they
469
* are sensible and can be merged. The runlist @srl must be either after the
470
* runlist @drl or completely within a hole (or unmapped region) in @drl.
471
*
472
* Merging of runlists is necessary in two cases:
473
* 1. When attribute lists are used and a further extent is being mapped.
474
* 2. When new clusters are allocated to fill a hole or extend a file.
475
*
476
* There are four possible ways @srl can be merged. It can:
477
* - be inserted at the beginning of a hole,
478
* - split the hole in two and be inserted between the two fragments,
479
* - be appended at the end of a hole, or it can
480
* - replace the whole hole.
481
* It can also be appended to the end of the runlist, which is just a variant
482
* of the insert case.
483
*
484
* On success, return a pointer to the new, combined, runlist. Note, both
485
* runlists @drl and @srl are deallocated before returning so you cannot use
486
* the pointers for anything any more. (Strictly speaking the returned runlist
487
* may be the same as @dst but this is irrelevant.)
488
*
489
* On error, return NULL, with errno set to the error code. Both runlists are
490
* left unmodified. The following error codes are defined:
491
* ENOMEM Not enough memory to allocate runlist array.
492
* EINVAL Invalid parameters were passed in.
493
* ERANGE The runlists overlap and cannot be merged.
494
*/
495
runlist_element *ntfs_runlists_merge(runlist_element *drl,
496
runlist_element *srl)
497
{
498
int di, si; /* Current index into @[ds]rl. */
499
int sstart; /* First index with lcn > LCN_RL_NOT_MAPPED. */
500
int dins; /* Index into @drl at which to insert @srl. */
501
int dend, send; /* Last index into @[ds]rl. */
502
int dfinal, sfinal; /* The last index into @[ds]rl with
503
lcn >= LCN_HOLE. */
504
int marker = 0;
505
VCN marker_vcn = 0;
506
507
Dputs("dst:");
508
ntfs_debug_runlist_dump(drl);
509
Dputs("src:");
510
ntfs_debug_runlist_dump(srl);
511
512
/* Check for silly calling... */
513
if (!srl)
514
return drl;
515
516
/* Check for the case where the first mapping is being done now. */
517
if (!drl) {
518
drl = srl;
519
/* Complete the source runlist if necessary. */
520
if (drl[0].vcn) {
521
/* Scan to the end of the source runlist. */
522
for (dend = 0; drl[dend].length; dend++)
523
;
524
drl = ntfs_rl_realloc(drl, dend, dend + 1);
525
if (!drl)
526
return drl;
527
/* Insert start element at the front of the runlist. */
528
ntfs_rl_mm(drl, 1, 0, dend);
529
drl[0].vcn = 0;
530
drl[0].lcn = LCN_RL_NOT_MAPPED;
531
drl[0].length = drl[1].vcn;
532
}
533
goto finished;
534
}
535
536
si = di = 0;
537
538
/* Skip any unmapped start element(s) in the source runlist. */
539
while (srl[si].length && srl[si].lcn < (LCN)LCN_HOLE)
540
si++;
541
542
/* Can't have an entirely unmapped source runlist. */
543
if (!srl[si].length) {
544
Dputs("Eeek! ntfs_runlists_merge() received entirely "
545
"unmapped source runlist.");
546
errno = EINVAL;
547
return NULL;
548
}
549
550
/* Record the starting points. */
551
sstart = si;
552
553
/*
554
* Skip forward in @drl until we reach the position where @srl needs to
555
* be inserted. If we reach the end of @drl, @srl just needs to be
556
* appended to @drl.
557
*/
558
for (; drl[di].length; di++) {
559
if (drl[di].vcn + drl[di].length > srl[sstart].vcn)
560
break;
561
}
562
dins = di;
563
564
/* Sanity check for illegal overlaps. */
565
if ((drl[di].vcn == srl[si].vcn) && (drl[di].lcn >= 0) &&
566
(srl[si].lcn >= 0)) {
567
Dputs("Run lists overlap. Cannot merge!");
568
errno = ERANGE;
569
return NULL;
570
}
571
572
/* Scan to the end of both runlists in order to know their sizes. */
573
for (send = si; srl[send].length; send++)
574
;
575
for (dend = di; drl[dend].length; dend++)
576
;
577
578
if (srl[send].lcn == (LCN)LCN_ENOENT)
579
marker_vcn = srl[marker = send].vcn;
580
581
/* Scan to the last element with lcn >= LCN_HOLE. */
582
for (sfinal = send; sfinal >= 0 && srl[sfinal].lcn < LCN_HOLE; sfinal--)
583
;
584
for (dfinal = dend; dfinal >= 0 && drl[dfinal].lcn < LCN_HOLE; dfinal--)
585
;
586
587
{
588
BOOL start;
589
BOOL finish;
590
int ds = dend + 1; /* Number of elements in drl & srl */
591
int ss = sfinal - sstart + 1;
592
593
start = ((drl[dins].lcn < LCN_RL_NOT_MAPPED) || /* End of file */
594
(drl[dins].vcn == srl[sstart].vcn)); /* Start of hole */
595
finish = ((drl[dins].lcn >= LCN_RL_NOT_MAPPED) && /* End of file */
596
((drl[dins].vcn + drl[dins].length) <= /* End of hole */
597
(srl[send - 1].vcn + srl[send - 1].length)));
598
599
/* Or we'll lose an end marker */
600
if (start && finish && (drl[dins].length == 0))
601
ss++;
602
if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn))
603
finish = FALSE;
604
#ifdef DEBUG
605
Dprintf("dfinal = %i, dend = %i\n", dfinal, dend);
606
Dprintf("sstart = %i, sfinal = %i, send = %i\n", sstart, sfinal, send);
607
Dprintf("start = %i, finish = %i\n", start, finish);
608
Dprintf("ds = %i, ss = %i, dins = %i\n", ds, ss, dins);
609
#endif
610
if (start) {
611
if (finish)
612
drl = ntfs_rl_replace(drl, ds, srl + sstart, ss, dins);
613
else
614
drl = ntfs_rl_insert(drl, ds, srl + sstart, ss, dins);
615
} else {
616
if (finish)
617
drl = ntfs_rl_append(drl, ds, srl + sstart, ss, dins);
618
else
619
drl = ntfs_rl_split(drl, ds, srl + sstart, ss, dins);
620
}
621
if (!drl) {
622
Dprintf("%s(): Merge failed: %s\n", __FUNCTION__,
623
strerror(errno));
624
return drl;
625
}
626
free(srl);
627
if (marker) {
628
Dputs("Triggering marker code.");
629
for (ds = dend; drl[ds].length; ds++)
630
;
631
/* We only need to care if @srl ended after @drl. */
632
if (drl[ds].vcn <= marker_vcn) {
633
int slots = 0;
634
635
if (drl[ds].vcn == marker_vcn) {
636
Dprintf("Old marker = %lli, replacing with "
637
"LCN_ENOENT.\n",
638
(long long)drl[ds].lcn);
639
drl[ds].lcn = (LCN)LCN_ENOENT;
640
goto finished;
641
}
642
/*
643
* We need to create an unmapped runlist element in
644
* @drl or extend an existing one before adding the
645
* ENOENT terminator.
646
*/
647
if (drl[ds].lcn == (LCN)LCN_ENOENT) {
648
ds--;
649
slots = 1;
650
}
651
if (drl[ds].lcn != (LCN)LCN_RL_NOT_MAPPED) {
652
/* Add an unmapped runlist element. */
653
if (!slots) {
654
/* FIXME/TODO: We need to have the
655
* extra memory already! (AIA)
656
*/
657
drl = ntfs_rl_realloc(drl, ds, ds + 2);
658
if (!drl)
659
goto critical_error;
660
slots = 2;
661
}
662
ds++;
663
/* Need to set vcn if it isn't set already. */
664
if (slots != 1)
665
drl[ds].vcn = drl[ds - 1].vcn +
666
drl[ds - 1].length;
667
drl[ds].lcn = (LCN)LCN_RL_NOT_MAPPED;
668
/* We now used up a slot. */
669
slots--;
670
}
671
drl[ds].length = marker_vcn - drl[ds].vcn;
672
/* Finally add the ENOENT terminator. */
673
ds++;
674
if (!slots) {
675
/* FIXME/TODO: We need to have the extra
676
* memory already! (AIA)
677
*/
678
drl = ntfs_rl_realloc(drl, ds, ds + 1);
679
if (!drl)
680
goto critical_error;
681
}
682
drl[ds].vcn = marker_vcn;
683
drl[ds].lcn = (LCN)LCN_ENOENT;
684
drl[ds].length = (s64)0;
685
}
686
}
687
}
688
689
finished:
690
/* The merge was completed successfully. */
691
Dputs("Merged runlist:");
692
ntfs_debug_runlist_dump(drl);
693
return drl;
694
695
critical_error:
696
/* Critical error! We cannot afford to fail here. */
697
Dperror("libntfs: Critical error");
698
Dputs("Forcing segmentation fault!");
699
marker_vcn = ((runlist*)NULL)->lcn;
700
return drl;
701
}
702
703
/**
704
* ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist
705
* @vol: ntfs volume on which the attribute resides
706
* @attr: attribute record whose mapping pairs array to decompress
707
* @old_rl: optional runlist in which to insert @attr's runlist
708
*
709
* Decompress the attribute @attr's mapping pairs array into a runlist. On
710
* success, return the decompressed runlist.
711
*
712
* If @old_rl is not NULL, decompressed runlist is inserted into the
713
* appropriate place in @old_rl and the resultant, combined runlist is
714
* returned. The original @old_rl is deallocated.
715
*
716
* On error, return NULL with errno set to the error code. @old_rl is left
717
* 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 NULL, with errno = ERANGE).
729
*/
730
runlist_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
const u8 *buf; /* Current position in mapping pairs array. */
738
const u8 *attr_end; /* End of attribute. */
739
int err, 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
Dprintf("%s(): Entering for attr 0x%x.\n", __FUNCTION__,
745
le32_to_cpu(attr->type));
746
/* Make sure attr exists and is non-resident. */
747
if (!attr || !attr->non_resident ||
748
sle64_to_cpu(attr->lowest_vcn) < (VCN)0) {
749
errno = EINVAL;
750
return NULL;
751
}
752
/* Start at vcn = lowest_vcn and lcn 0. */
753
vcn = sle64_to_cpu(attr->lowest_vcn);
754
lcn = 0;
755
/* Get start of the mapping pairs array. */
756
buf = (const u8*)attr + le16_to_cpu(attr->mapping_pairs_offset);
757
attr_end = (const u8*)attr + le32_to_cpu(attr->length);
758
if (buf < (const u8*)attr || buf > attr_end) {
759
Dputs("Corrupt attribute.");
760
errno = EIO;
761
return NULL;
762
}
763
/* Current position in runlist array. */
764
rlpos = 0;
765
/* Allocate first 4kiB block and set current runlist size to 4kiB. */
766
rl = malloc(rlsize = 0x1000);
767
if (!rl)
768
return NULL;
769
/* Insert unmapped starting element if necessary. */
770
if (vcn) {
771
rl->vcn = (VCN)0;
772
rl->lcn = (LCN)LCN_RL_NOT_MAPPED;
773
rl->length = vcn;
774
rlpos++;
775
}
776
while (buf < attr_end && *buf) {
777
/*
778
* Allocate more memory if needed, including space for the
779
* not-mapped and terminator elements.
780
*/
781
if ((int)((rlpos + 3) * sizeof(*old_rl)) > rlsize) {
782
runlist_element *rl2;
783
784
rlsize += 0x1000;
785
rl2 = realloc(rl, rlsize);
786
if (!rl2) {
787
int eo = errno;
788
free(rl);
789
errno = eo;
790
return NULL;
791
}
792
rl = rl2;
793
}
794
/* Enter the current vcn into the current runlist element. */
795
rl[rlpos].vcn = vcn;
796
/*
797
* Get the change in vcn, i.e. the run length in clusters.
798
* Doing it this way ensures that we signextend negative values.
799
* A negative run length doesn't make any sense, but hey, I
800
* didn't make up the NTFS specs and Windows NT4 treats the run
801
* length as a signed value so that's how it is...
802
*/
803
b = *buf & 0xf;
804
if (b) {
805
if (buf + b > attr_end)
806
goto io_error;
807
for (deltaxcn = (s8)buf[b--]; b; b--)
808
deltaxcn = (deltaxcn << 8) + buf[b];
809
} else { /* The length entry is compulsory. */
810
Dputs("Missing length entry in mapping pairs array.");
811
deltaxcn = (s64)-1;
812
}
813
/*
814
* Assume a negative length to indicate data corruption and
815
* hence clean-up and return NULL.
816
*/
817
if (deltaxcn < 0) {
818
Dputs("Invalid length in mapping pairs array.");
819
goto err_out;
820
}
821
/*
822
* Enter the current run length into the current runlist
823
* element.
824
*/
825
rl[rlpos].length = deltaxcn;
826
/* Increment the current vcn by the current run length. */
827
vcn += deltaxcn;
828
/*
829
* There might be no lcn change at all, as is the case for
830
* sparse clusters on NTFS 3.0+, in which case we set the lcn
831
* to LCN_HOLE.
832
*/
833
if (!(*buf & 0xf0))
834
rl[rlpos].lcn = (LCN)LCN_HOLE;
835
else {
836
/* Get the lcn change which really can be negative. */
837
u8 b2 = *buf & 0xf;
838
b = b2 + ((*buf >> 4) & 0xf);
839
if (buf + b > attr_end)
840
goto io_error;
841
for (deltaxcn = (s8)buf[b--]; b > b2; b--)
842
deltaxcn = (deltaxcn << 8) + buf[b];
843
/* Change the current lcn to it's new value. */
844
lcn += deltaxcn;
845
#ifdef DEBUG
846
/*
847
* On NTFS 1.2-, apparently can have lcn == -1 to
848
* indicate a hole. But we haven't verified ourselves
849
* whether it is really the lcn or the deltaxcn that is
850
* -1. So if either is found give us a message so we
851
* can investigate it further!
852
*/
853
if (vol->major_ver < 3) {
854
if (deltaxcn == (LCN)-1)
855
Dputs("lcn delta == -1");
856
if (lcn == (LCN)-1)
857
Dputs("lcn == -1");
858
}
859
#endif
860
/* Check lcn is not below -1. */
861
if (lcn < (LCN)-1) {
862
Dputs("Invalid LCN < -1 in mapping pairs "
863
"array.");
864
goto err_out;
865
}
866
/* Enter the current lcn into the runlist element. */
867
rl[rlpos].lcn = lcn;
868
}
869
/* Get to the next runlist element. */
870
rlpos++;
871
/* Increment the buffer position to the next mapping pair. */
872
buf += (*buf & 0xf) + ((*buf >> 4) & 0xf) + 1;
873
}
874
if (buf >= attr_end)
875
goto io_error;
876
/*
877
* If there is a highest_vcn specified, it must be equal to the final
878
* vcn in the runlist - 1, or something has gone badly wrong.
879
*/
880
deltaxcn = sle64_to_cpu(attr->highest_vcn);
881
if (deltaxcn && vcn - 1 != deltaxcn) {
882
mpa_err:
883
Dputs("Corrupt mapping pairs array in non-resident attribute.");
884
goto err_out;
885
}
886
/* Setup not mapped runlist element if this is the base extent. */
887
if (!attr->lowest_vcn) {
888
VCN max_cluster;
889
890
max_cluster = (sle64_to_cpu(attr->allocated_size) +
891
vol->cluster_size - 1) >>
892
vol->cluster_size_bits;
893
/*
894
* If there is a difference between the highest_vcn and the
895
* highest cluster, the runlist is either corrupt or, more
896
* likely, there are more extents following this one.
897
*/
898
if (deltaxcn < --max_cluster) {
899
Dprintf("More extents to follow; deltaxcn = 0x%llx, "
900
"max_cluster = 0x%llx\n",
901
(long long)deltaxcn,
902
(long long)max_cluster);
903
rl[rlpos].vcn = vcn;
904
vcn += rl[rlpos].length = max_cluster - deltaxcn;
905
rl[rlpos].lcn = (LCN)LCN_RL_NOT_MAPPED;
906
rlpos++;
907
} else if (deltaxcn > max_cluster) {
908
Dprintf("Corrupt attribute. deltaxcn = 0x%llx, "
909
"max_cluster = 0x%llx",
910
(long long)deltaxcn,
911
(long long)max_cluster);
912
goto mpa_err;
913
}
914
rl[rlpos].lcn = (LCN)LCN_ENOENT;
915
} else /* Not the base extent. There may be more extents to follow. */
916
rl[rlpos].lcn = (LCN)LCN_RL_NOT_MAPPED;
917
918
/* Setup terminating runlist element. */
919
rl[rlpos].vcn = vcn;
920
rl[rlpos].length = (s64)0;
921
/* If no existing runlist was specified, we are done. */
922
if (!old_rl) {
923
Dputs("Mapping pairs array successfully decompressed:");
924
ntfs_debug_runlist_dump(rl);
925
return rl;
926
}
927
/* Now combine the new and old runlists checking for overlaps. */
928
old_rl = ntfs_runlists_merge(old_rl, rl);
929
if (old_rl)
930
return old_rl;
931
err = errno;
932
free(rl);
933
Dputs("Failed to merge runlists.");
934
errno = err;
935
return NULL;
936
io_error:
937
Dputs("Corrupt attribute.");
938
err_out:
939
free(rl);
940
errno = EIO;
941
return NULL;
942
}
943
944
/**
945
* ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist
946
* @rl: runlist to use for conversion
947
* @vcn: vcn to convert
948
*
949
* Convert the virtual cluster number @vcn of an attribute into a logical
950
* cluster number (lcn) of a device using the runlist @rl to map vcns to their
951
* corresponding lcns.
952
*
953
* Since lcns must be >= 0, we use negative return values with special meaning:
954
*
955
* Return value Meaning / Description
956
* ==================================================
957
* -1 = LCN_HOLE Hole / not allocated on disk.
958
* -2 = LCN_RL_NOT_MAPPED This is part of the runlist which has not been
959
* inserted into the runlist yet.
960
* -3 = LCN_ENOENT There is no such vcn in the attribute.
961
* -4 = LCN_EINVAL Input parameter error.
962
*/
963
LCN ntfs_rl_vcn_to_lcn(const runlist_element *rl, const VCN vcn)
964
{
965
int i;
966
967
if (vcn < (VCN)0)
968
return (LCN)LCN_EINVAL;
969
/*
970
* If rl is NULL, assume that we have found an unmapped runlist. The
971
* caller can then attempt to map it and fail appropriately if
972
* necessary.
973
*/
974
if (!rl)
975
return (LCN)LCN_RL_NOT_MAPPED;
976
977
/* Catch out of lower bounds vcn. */
978
if (vcn < rl[0].vcn)
979
return (LCN)LCN_ENOENT;
980
981
for (i = 0; rl[i].length; i++) {
982
if (vcn < rl[i+1].vcn) {
983
if (rl[i].lcn >= (LCN)0)
984
return rl[i].lcn + (vcn - rl[i].vcn);
985
return rl[i].lcn;
986
}
987
}
988
/*
989
* The terminator element is setup to the correct value, i.e. one of
990
* LCN_HOLE, LCN_RL_NOT_MAPPED, or LCN_ENOENT.
991
*/
992
if (rl[i].lcn < (LCN)0)
993
return rl[i].lcn;
994
/* Just in case... We could replace this with BUG() some day. */
995
return (LCN)LCN_ENOENT;
996
}
997
998
/**
999
* ntfs_rl_pread - gather read from disk
1000
* @vol: ntfs volume to read from
1001
* @rl: runlist specifying where to read the data from
1002
* @pos: byte position within runlist @rl at which to begin the read
1003
* @count: number of bytes to read
1004
* @b: data buffer into which to read from disk
1005
*
1006
* This function will read @count bytes from the volume @vol to the data buffer
1007
* @b gathering the data as specified by the runlist @rl. The read begins at
1008
* offset @pos into the runlist @rl.
1009
*
1010
* On success, return the number of successfully read bytes. If this number is
1011
* lower than @count this means that the read reached end of file or that an
1012
* error was encountered during the read so that the read is partial. 0 means
1013
* nothing was read (also return 0 when @count is 0).
1014
*
1015
* On error and nothing has been read, return -1 with errno set appropriately
1016
* to the return code of ntfs_pread(), or to EINVAL in case of invalid
1017
* arguments.
1018
*
1019
* NOTE: If we encounter EOF while reading we return EIO because we assume that
1020
* the run list must point to valid locations within the ntfs volume.
1021
*/
1022
s64 ntfs_rl_pread(const ntfs_volume *vol, const runlist_element *rl,
1023
const s64 pos, s64 count, void *b)
1024
{
1025
s64 bytes_read, to_read, ofs, total;
1026
int err = EIO;
1027
1028
if (!vol || !rl || pos < 0 || count < 0) {
1029
errno = EINVAL;
1030
return -1;
1031
}
1032
if (!count)
1033
return count;
1034
/* Seek in @rl to the run containing @pos. */
1035
for (ofs = 0; rl->length && (ofs + rl->length <= pos); rl++)
1036
ofs += rl->length;
1037
/* Offset in the run at which to begin reading. */
1038
ofs = pos - ofs;
1039
for (total = 0LL; count; rl++, ofs = 0) {
1040
if (!rl->length)
1041
goto rl_err_out;
1042
if (rl->lcn < (LCN)0) {
1043
if (rl->lcn != (LCN)LCN_HOLE)
1044
goto rl_err_out;
1045
/* It is a hole. Just fill buffer @b with zeroes. */
1046
to_read = min(count, (rl->length <<
1047
vol->cluster_size_bits) - ofs);
1048
memset(b, 0, to_read);
1049
/* Update counters and proceed with next run. */
1050
total += to_read;
1051
count -= to_read;
1052
(u8*)b += to_read;
1053
continue;
1054
}
1055
/* It is a real lcn, read it from the volume. */
1056
to_read = min(count, (rl->length << vol->cluster_size_bits) -
1057
ofs);
1058
retry:
1059
bytes_read = ntfs_pread(vol->dev, (rl->lcn <<
1060
vol->cluster_size_bits) + ofs, to_read, b);
1061
/* If everything ok, update progress counters and continue. */
1062
if (bytes_read > 0) {
1063
total += bytes_read;
1064
count -= bytes_read;
1065
(u8*)b += bytes_read;
1066
continue;
1067
}
1068
/* If the syscall was interrupted, try again. */
1069
if (bytes_read == (s64)-1 && errno == EINTR)
1070
goto retry;
1071
if (bytes_read == (s64)-1)
1072
err = errno;
1073
goto rl_err_out;
1074
}
1075
/* Finally, return the number of bytes read. */
1076
return total;
1077
rl_err_out:
1078
if (total)
1079
return total;
1080
errno = err;
1081
return -1;
1082
}
1083
1084
/**
1085
* ntfs_rl_pwrite - scatter write to disk
1086
* @vol: ntfs volume to write to
1087
* @rl: runlist specifying where to write the data to
1088
* @pos: byte position within runlist @rl at which to begin the write
1089
* @count: number of bytes to write
1090
* @b: data buffer to write to disk
1091
*
1092
* This function will write @count bytes from data buffer @b to the volume @vol
1093
* scattering the data as specified by the runlist @rl. The write begins at
1094
* offset @pos into the runlist @rl.
1095
*
1096
* On success, return the number of successfully written bytes. If this number
1097
* is lower than @count this means that the write has been interrupted in
1098
* flight or that an error was encountered during the write so that the write
1099
* is partial. 0 means nothing was written (also return 0 when @count is 0).
1100
*
1101
* On error and nothing has been written, return -1 with errno set
1102
* appropriately to the return code of ntfs_pwrite(), or to to EINVAL in case
1103
* of invalid arguments.
1104
*/
1105
s64 ntfs_rl_pwrite(const ntfs_volume *vol, const runlist_element *rl,
1106
const s64 pos, s64 count, void *b)
1107
{
1108
s64 written, to_write, ofs, total;
1109
int err = EIO;
1110
1111
if (!vol || !rl || pos < 0 || count < 0) {
1112
errno = EINVAL;
1113
return -1;
1114
}
1115
if (!count)
1116
return count;
1117
/* Seek in @rl to the run containing @pos. */
1118
for (ofs = 0; rl->length && (ofs + rl->length <= pos); rl++)
1119
ofs += rl->length;
1120
/* Offset in the run at which to begin writing. */
1121
ofs = pos - ofs;
1122
for (total = 0LL; count; rl++, ofs = 0) {
1123
if (!rl->length)
1124
goto rl_err_out;
1125
if (rl->lcn < (LCN)0) {
1126
s64 t;
1127
int cnt;
1128
1129
if (rl->lcn != (LCN)LCN_HOLE)
1130
goto rl_err_out;
1131
/*
1132
* It is a hole. Check if the buffer is zero in this
1133
* region and if not abort with error.
1134
*/
1135
to_write = min(count, (rl->length <<
1136
vol->cluster_size_bits) - ofs);
1137
written = to_write / sizeof(unsigned long);
1138
for (t = 0; t < written; t++) {
1139
if (((unsigned long*)b)[t])
1140
goto rl_err_out;
1141
}
1142
cnt = to_write & (sizeof(unsigned long) - 1);
1143
if (cnt) {
1144
int i;
1145
u8 *b2;
1146
1147
b2 = (u8*)b + (to_write &
1148
~(sizeof(unsigned long) - 1));
1149
for (i = 0; i < cnt; i++) {
1150
if (b2[i])
1151
goto rl_err_out;
1152
}
1153
}
1154
/*
1155
* The buffer region is zero, update progress counters
1156
* and proceed with next run.
1157
*/
1158
total += to_write;
1159
count -= to_write;
1160
(u8*)b += to_write;
1161
continue;
1162
}
1163
/* It is a real lcn, write it to the volume. */
1164
to_write = min(count, (rl->length << vol->cluster_size_bits) -
1165
ofs);
1166
retry:
1167
if (!NVolReadOnly(vol))
1168
written = ntfs_pwrite(vol->dev, (rl->lcn <<
1169
vol->cluster_size_bits) + ofs,
1170
to_write, b);
1171
else
1172
written = to_write;
1173
/* If everything ok, update progress counters and continue. */
1174
if (written > 0) {
1175
total += written;
1176
count -= written;
1177
(u8*)b += written;
1178
continue;
1179
}
1180
/* If the syscall was interrupted, try again. */
1181
if (written == (s64)-1 && errno == EINTR)
1182
goto retry;
1183
if (written == (s64)-1)
1184
err = errno;
1185
goto rl_err_out;
1186
}
1187
/* Finally, return the number of bytes written. */
1188
return total;
1189
rl_err_out:
1190
if (total)
1191
return total;
1192
errno = err;
1193
return -1;
1194
}
1195
1196
/**
1197
* ntfs_get_nr_significant_bytes - get number of bytes needed to store a number
1198
* @n: number for which to get the number of bytes for
1199
*
1200
* Return the number of bytes required to store @n unambiguously as
1201
* a signed number.
1202
*
1203
* This is used in the context of the mapping pairs array to determine how
1204
* many bytes will be needed in the array to store a given logical cluster
1205
* number (lcn) or a specific run length.
1206
*
1207
* Return the number of bytes written. This function cannot fail.
1208
*/
1209
__inline__ int ntfs_get_nr_significant_bytes(const s64 n)
1210
{
1211
s64 l = n;
1212
int i;
1213
s8 j;
1214
1215
i = 0;
1216
do {
1217
l >>= 8;
1218
i++;
1219
} while (l != 0LL && l != -1LL);
1220
j = (n >> 8 * (i - 1)) & 0xff;
1221
/* If the sign bit is wrong, we need an extra byte. */
1222
if ((n < 0LL && j >= 0) || (n > 0LL && j < 0))
1223
i++;
1224
return i;
1225
}
1226
1227
/**
1228
* ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array
1229
* @vol: ntfs volume (needed for the ntfs version)
1230
* @rl: runlist for which to determine the size of the mapping pairs
1231
*
1232
* Walk the runlist @rl and calculate the size in bytes of the mapping pairs
1233
* array corresponding to the runlist @rl. This for example allows us to
1234
* allocate a buffer of the right size when building the mapping pairs array.
1235
*
1236
* Return the calculated size in bytes on success. If @rl is NULL return 0.
1237
* On error, return -1 with errno set to the error code. The following error
1238
* codes are defined:
1239
* EINVAL - Run list contains unmapped elements. Make sure to only pass
1240
* fully mapped runlists to this function.
1241
* EIO - The runlist is corrupt.
1242
*/
1243
int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol,
1244
const runlist_element *rl)
1245
{
1246
LCN prev_lcn;
1247
int i, rls;
1248
1249
if (!rl)
1250
return 0;
1251
/* Always need the termining zero byte. */
1252
rls = 1;
1253
for (prev_lcn = i = 0; rl[i].length; i++) {
1254
if (rl[i].length < 0 || rl[i].lcn < LCN_HOLE)
1255
goto err_out;
1256
/* Header byte + length. */
1257
rls += 1 + ntfs_get_nr_significant_bytes(rl[i].length);
1258
/*
1259
* If the logical cluster number (lcn) denotes a hole and we
1260
* are on NTFS 3.0+, we don't store it at all, i.e. we need
1261
* zero space. On earlier NTFS versions we just store the lcn.
1262
*/
1263
if (rl[i].lcn == LCN_HOLE && vol->major_ver >= 3)
1264
continue;
1265
/*
1266
* Change in lcn. Note: this assumes that on NTFS 1.2-, holes
1267
* are stored with an lcn of -1 and _not_ a delta_lcn of -1
1268
* (unless both are -1).
1269
*/
1270
rls += ntfs_get_nr_significant_bytes(rl[i].lcn - prev_lcn);
1271
prev_lcn = rl[i].lcn;
1272
}
1273
return rls;
1274
err_out:
1275
if (rl[i].lcn == LCN_RL_NOT_MAPPED)
1276
errno = EINVAL;
1277
else
1278
errno = EIO;
1279
return -1;
1280
}
1281
1282
/**
1283
* ntfs_write_significant_bytes - write the significant bytes of a number
1284
* @dst: destination buffer to write to
1285
* @dst_max: pointer to last byte of destination buffer for bounds checking
1286
* @n: number whose significant bytes to write
1287
*
1288
* Store in @dst, the minimum bytes of the number @n which are required to
1289
* identify @n unambiguously as a signed number, taking care not to exceed
1290
* @dest_max, the maximum position within @dst to which we are allowed to
1291
* write.
1292
*
1293
* This is used when building the mapping pairs array of a runlist to compress
1294
* a given logical cluster number (lcn) or a specific run length to the minumum
1295
* size possible.
1296
*
1297
* Return the number of bytes written on success. On error, i.e. the
1298
* destination buffer @dst is too small, return -1 with errno set ENOSPC.
1299
*/
1300
__inline__ int ntfs_write_significant_bytes(s8 *dst, const s8 *dst_max,
1301
const s64 n)
1302
{
1303
s64 l = n;
1304
int i;
1305
s8 j;
1306
1307
i = 0;
1308
do {
1309
if (dst > dst_max)
1310
goto err_out;
1311
*dst++ = l & 0xffLL;
1312
l >>= 8;
1313
i++;
1314
} while (l != 0LL && l != -1LL);
1315
j = (n >> 8 * (i - 1)) & 0xff;
1316
/* If the sign bit is wrong, we need an extra byte. */
1317
if (n < 0LL && j >= 0) {
1318
if (dst > dst_max)
1319
goto err_out;
1320
i++;
1321
*dst = (s8)-1;
1322
} else if (n > 0LL && j < 0) {
1323
if (dst > dst_max)
1324
goto err_out;
1325
i++;
1326
*dst = (s8)0;
1327
}
1328
return i;
1329
err_out:
1330
errno = ENOSPC;
1331
return -1;
1332
}
1333
1334
/**
1335
* ntfs_mapping_pairs_build - build the mapping pairs array from a runlist
1336
* @vol: ntfs volume (needed for the ntfs version)
1337
* @dst: destination buffer to which to write the mapping pairs array
1338
* @dst_len: size of destination buffer @dst in bytes
1339
* @rl: runlist for which to build the mapping pairs array
1340
*
1341
* Create the mapping pairs array from the runlist @rl and save the array in
1342
* @dst. @dst_len is the size of @dst in bytes and it should be at least equal
1343
* to the value obtained by calling ntfs_get_size_for_mapping_pairs().
1344
*
1345
* Return 0 on success or when @rl is NULL. On error, return -1 with errno set
1346
* to the error code. The following error codes are defined:
1347
* EINVAL - Run list contains unmapped elements. Make sure to only pass
1348
* fully mapped runlists to this function.
1349
* EIO - The runlist is corrupt.
1350
* ENOSPC - The destination buffer is too small.
1351
*/
1352
int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst,
1353
const int dst_len, const runlist_element *rl)
1354
{
1355
LCN prev_lcn;
1356
s8 *dst_max;
1357
int i;
1358
s8 len_len, lcn_len;
1359
1360
if (!rl)
1361
return 0;
1362
/*
1363
* @dst_max is used for bounds checking in
1364
* ntfs_write_significant_bytes().
1365
*/
1366
dst_max = dst + dst_len - 1;
1367
for (prev_lcn = i = 0; rl[i].length; i++) {
1368
if (rl[i].length < 0 || rl[i].lcn < LCN_HOLE)
1369
goto err_out;
1370
/* Write length. */
1371
len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1372
rl[i].length);
1373
if (len_len < 0)
1374
goto size_err;
1375
/*
1376
* If the logical cluster number (lcn) denotes a hole and we
1377
* are on NTFS 3.0+, we don't store it at all, i.e. we need
1378
* zero space. On earlier NTFS versions we just write the lcn
1379
* change. FIXME: Do we need to write the lcn change or just
1380
* the lcn in that case? Not sure as I have never seen this
1381
* case on NT4. - We assume that we just need to write the lcn
1382
* change until someone tells us otherwise... (AIA)
1383
*/
1384
if (rl[i].lcn != LCN_HOLE || vol->major_ver < 3) {
1385
lcn_len = ntfs_write_significant_bytes(dst + 1 +
1386
len_len, dst_max, rl[i].lcn - prev_lcn);
1387
if (lcn_len < 0)
1388
goto size_err;
1389
prev_lcn = rl[i].lcn;
1390
} else
1391
lcn_len = 0;
1392
/* Update header byte. */
1393
*dst = lcn_len << 4 | len_len;
1394
/* Position ourselves at next mapping pairs array element. */
1395
dst += 1 + len_len + lcn_len;
1396
}
1397
if (dst <= dst_max) {
1398
/* Terminator byte. */
1399
*dst = 0;
1400
return 0;
1401
}
1402
size_err:
1403
errno = ENOSPC;
1404
return -1;
1405
err_out:
1406
if (rl[i].lcn == LCN_RL_NOT_MAPPED)
1407
errno = EINVAL;
1408
else
1409
errno = EIO;
1410
return -1;
1411
}
1412
1413
/**
1414
* ntfs_rl_truncate - truncate a runlist starting at a specified vcn
1415
* @arl: address of runlist to truncate
1416
* @start_vcn: first vcn which should be cut off
1417
*
1418
* Truncate the runlist *@arl starting at vcn @start_vcn as well as the memory
1419
* buffer holding the runlist.
1420
*
1421
* Return 0 on success and -1 on error with errno set to the error code.
1422
*
1423
* NOTE: @arl is the address of the runlist. We need the address so we can
1424
* modify the pointer to the runlist with the new, reallocated memory buffer.
1425
*/
1426
int ntfs_rl_truncate(runlist **arl, const VCN start_vcn)
1427
{
1428
runlist *rl;
1429
BOOL is_end;
1430
1431
if (!arl || !*arl) {
1432
errno = EINVAL;
1433
return -1;
1434
}
1435
rl = *arl;
1436
if (start_vcn < rl->vcn) {
1437
// FIXME: Eeek! BUG()
1438
fprintf(stderr, "%s(): Eeek! start_vcn lies outside front of "
1439
"runlist! Aborting.\n", __FUNCTION__);
1440
errno = EIO;
1441
return -1;
1442
}
1443
/* Find the starting vcn in the run list. */
1444
while (rl->length) {
1445
if (start_vcn < rl[1].vcn)
1446
break;
1447
rl++;
1448
}
1449
if (!rl->length) {
1450
// FIXME: Weird, probably a BUG()!
1451
fprintf(stderr, "%s(): Weird! Asking to truncate already "
1452
"truncated runlist?!? Abort.\n", __FUNCTION__);
1453
errno = EIO;
1454
return -1;
1455
}
1456
if (start_vcn < rl->vcn) {
1457
// FIXME: Eeek! BUG()
1458
fprintf(stderr, "%s(): Eeek! start_vcn < rl->vcn! Aborting.\n",
1459
__FUNCTION__);
1460
errno = EIO;
1461
return -1;
1462
}
1463
if (rl->length) {
1464
is_end = FALSE;
1465
/* Truncate the run. */
1466
rl->length = start_vcn - rl->vcn;
1467
/*
1468
* If a run was partially truncated, make the following runlist
1469
* element a terminator instead of the truncated runlist
1470
* element itself.
1471
*/
1472
if (rl->length) {
1473
++rl;
1474
if (!rl->length)
1475
is_end = TRUE;
1476
rl->vcn = start_vcn;
1477
rl->length = 0;
1478
}
1479
} else
1480
is_end = TRUE;
1481
rl->lcn = (LCN)LCN_ENOENT;
1482
/* Reallocate memory if necessary. */
1483
if (!is_end) {
1484
size_t new_size = (rl - *arl + 1) * sizeof(runlist_element);
1485
rl = realloc(*arl, new_size);
1486
if (rl)
1487
*arl = rl;
1488
else if (!new_size)
1489
*arl = NULL;
1490
else {
1491
// FIXME: Eeek!
1492
fprintf(stderr, "%s(): Eeek! Failed to reallocate "
1493
"runlist buffer! Continuing "
1494
"regardless and returning success.\n",
1495
__FUNCTION__);
1496
}
1497
}
1498
/* Done! */
1499
return 0;
1500
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1