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