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