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