1/* 2 * ntfs_runlist.c - NTFS kernel runlist operations. 3 * 4 * Copyright (c) 2001-2008 Anton Altaparmakov. All Rights Reserved. 5 * Portions Copyright (c) 2002-2005 Richard Russon. All Rights Reserved. 6 * Portions Copyright (c) 2006-2008 Apple Inc. All Rights Reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright notice, 12 * this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright notice, 14 * this list of conditions and the following disclaimer in the documentation 15 * and/or other materials provided with the distribution. 16 * 3. Neither the name of Apple Inc. ("Apple") nor the names of its 17 * contributors may be used to endorse or promote products derived from this 18 * software without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 21 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 22 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 23 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 24 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 25 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 26 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 27 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 29 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 * 31 * ALTERNATIVELY, provided that this notice and licensing terms are retained in 32 * full, this file may be redistributed and/or modified under the terms of the 33 * GNU General Public License (GPL) Version 2, in which case the provisions of 34 * that version of the GPL will apply to you instead of the license terms 35 * above. You can obtain a copy of the GPL Version 2 at 36 * http://developer.apple.com/opensource/licenses/gpl-2.txt. 37 */ 38 39#include <sys/buf.h> 40#include <sys/errno.h> 41 42#include <string.h> 43 44#include <libkern/OSMalloc.h> 45 46#include <kern/debug.h> 47#include <kern/locks.h> 48 49#include "ntfs.h" 50#include "ntfs_debug.h" 51#include "ntfs_layout.h" 52#include "ntfs_types.h" 53#include "ntfs_volume.h" 54 55/* 56 * For a description of the runlist structure and various values of LCNs, 57 * please read the ntfs_runlist.h header file. 58 */ 59#include "ntfs_runlist.h" 60 61/** 62 * ntfs_rl_copy - copy a runlist or runlist fragment 63 * 64 * It is up to the caller to serialize access to the runlists. 65 */ 66static inline void ntfs_rl_copy(ntfs_rl_element *dst, ntfs_rl_element *src, 67 const unsigned size) 68{ 69 if (size > 0) 70 memcpy(dst, src, size * sizeof(ntfs_rl_element)); 71} 72 73/** 74 * ntfs_rl_inc - append runlist elements to an existing runlist 75 * @runlist: runlist for which to increment the number of runlist elements 76 * @delta: number of elements to add to the runlist 77 * 78 * Increment the number of elements in the array of runlist elements of the 79 * runlist @runlist by @delta. Reallocate the array buffer if needed. 80 * 81 * Return 0 on success and ENOMEM if not enough memory to reallocate the 82 * runlist, in which case the runlist @runlist is left unmodified. 83 * 84 * Locking: - The caller must have locked the runlist for writing. 85 * - The runlist is modified. 86 */ 87static errno_t ntfs_rl_inc(ntfs_runlist *runlist, unsigned delta) 88{ 89 unsigned new_elements, alloc, new_alloc; 90 91 new_elements = runlist->elements + delta; 92 alloc = runlist->alloc; 93 new_alloc = (new_elements * sizeof(ntfs_rl_element) + 94 NTFS_ALLOC_BLOCK - 1) & ~(NTFS_ALLOC_BLOCK - 1); 95 if (new_alloc > alloc) { 96 ntfs_rl_element *new_rl; 97 98 new_rl = OSMalloc(new_alloc, ntfs_malloc_tag); 99 if (!new_rl) 100 return ENOMEM; 101 ntfs_rl_copy(new_rl, runlist->rl, runlist->elements); 102 if (alloc) 103 OSFree(runlist->rl, alloc, ntfs_malloc_tag); 104 runlist->rl = new_rl; 105 runlist->alloc = new_alloc; 106 } 107 runlist->elements = new_elements; 108 return 0; 109} 110 111/** 112 * ntfs_rl_move - move a fragment of a runlist within the runlist 113 * 114 * It is up to the caller to serialize access to the runlists. 115 */ 116static inline void ntfs_rl_move(ntfs_rl_element *dst, ntfs_rl_element* src, 117 const unsigned size) 118{ 119 if (dst != src && size > 0) 120 memmove(dst, src, size * sizeof(ntfs_rl_element)); 121} 122 123/** 124 * ntfs_rl_ins - insert runlist elements into an existing runlist 125 * @runlist: runlist to insert elements into 126 * @pos: position (in units of runlist elements) at which to insert 127 * @count: number of runlist elements to insert at @pos 128 * 129 * Insert @count runlist elements at position @pos in the runlist @runlist. If 130 * there is not enough space in the allocated array of runlist elements, the 131 * memory is reallocated thus you cannot use old pointers into the array of 132 * runlist elements. 133 * 134 * The inserted elements are not initialized, the caller is assumed to do this 135 * after a successful return from ntfs_rl_ins(). 136 * 137 * Return 0 on success and ENOMEM if not enough memory to reallocate the 138 * runlist, in which case the runlist @runlist is left unmodified. 139 * 140 * Locking: - The caller must have locked the runlist for writing. 141 * - The runlist is modified and potentially reallocated. 142 */ 143static errno_t ntfs_rl_ins(ntfs_runlist *runlist, unsigned pos, unsigned count) 144{ 145 ntfs_rl_element *new_rl = runlist->rl; 146 unsigned new_elements, alloc, new_alloc; 147 148 ntfs_debug("Entering with pos %u, count %u.", pos, count); 149 if (pos > runlist->elements) 150 panic("%s(): pos > runlist->elements\n", __FUNCTION__); 151 new_elements = runlist->elements + count; 152 alloc = runlist->alloc; 153 new_alloc = (new_elements * sizeof(ntfs_rl_element) + 154 NTFS_ALLOC_BLOCK - 1) & ~(NTFS_ALLOC_BLOCK - 1); 155 /* If no memory reallocation needed, it is a simple memmove(). */ 156 if (new_alloc <= alloc) { 157 if (count) { 158 new_rl += pos; 159 ntfs_rl_move(new_rl + count, new_rl, 160 runlist->elements - pos); 161 runlist->elements = new_elements; 162 } 163 ntfs_debug("Done: Simple."); 164 return 0; 165 } 166 /* 167 * Reallocate memory, then do a split memcpy() to the correct locations 168 * of the newly allocated array of runlist elements unless @pos is zero 169 * in which case a single memcpy() is sufficient. 170 */ 171 new_rl = OSMalloc(new_alloc, ntfs_malloc_tag); 172 if (!new_rl) 173 return ENOMEM; 174 ntfs_rl_copy(new_rl, runlist->rl, pos); 175 ntfs_rl_copy(new_rl + pos + count, runlist->rl + pos, 176 runlist->elements - pos); 177 if (alloc) 178 OSFree(runlist->rl, alloc, ntfs_malloc_tag); 179 runlist->rl = new_rl; 180 runlist->elements = new_elements; 181 runlist->alloc = new_alloc; 182 ntfs_debug("Done: Realloc."); 183 return 0; 184} 185 186/** 187 * ntfs_rl_can_merge - test if two runlists can be joined together 188 * @dst: original runlist element 189 * @src: new runlist element to test for mergeability with @dst 190 * 191 * Test if two runlists can be joined together. For this, their VCNs and LCNs 192 * must be adjacent. 193 * 194 * It is up to the caller to serialize access to the runlists. 195 * 196 * Return 1 if the runlists can be merged and 0 otherwise. 197 */ 198static unsigned ntfs_rl_can_merge(ntfs_rl_element *dst, ntfs_rl_element *src) 199{ 200 if (!dst || !src) 201 panic("%s(): !dst || !src\n", __FUNCTION__); 202 /* We can merge unmapped regions even if they are misaligned. */ 203 if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED)) 204 return 1; 205 /* If the runs are misaligned, we cannot merge them. */ 206 if ((dst->vcn + dst->length) != src->vcn) 207 return 0; 208 /* If both runs are non-sparse and contiguous, we can merge them. */ 209 if ((dst->lcn >= 0) && (src->lcn >= 0) && 210 ((dst->lcn + dst->length) == src->lcn)) 211 return 1; 212 /* If we are merging two holes, we can merge them. */ 213 if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE)) 214 return 1; 215 /* Cannot merge. */ 216 return 0; 217} 218 219/** 220 * __ntfs_rl_merge - merge two runlists without testing if they can be merged 221 * @dst: original, destination runlist 222 * @src: new runlist to merge with @dst 223 * 224 * Merge the two runlists, writing into the destination runlist @dst. The 225 * caller must make sure the runlists can be merged or this will corrupt the 226 * destination runlist. 227 * 228 * It is up to the caller to serialize access to the runlists. 229 */ 230static inline void __ntfs_rl_merge(ntfs_rl_element *dst, ntfs_rl_element *src) 231{ 232 dst->length += src->length; 233} 234 235/** 236 * ntfs_rl_replace - overwrite a runlist element with another runlist 237 * @dst_runlist: destination runlist to work on 238 * @src: array of runlist elements to be inserted 239 * @s_size: number of elements in @src (excluding end marker) 240 * @loc: index in destination to overwrite with @src 241 * 242 * Replace the runlist element @loc in the destination runlist @dst_runlist 243 * with @src. Merge the left and right ends of the inserted runlist, if 244 * necessary. 245 * 246 * It is up to the caller to serialize access to the runlists. 247 * 248 * Return 0 on success and ENOMEM if not enough memory to reallocate the 249 * runlist, in which case the destination runlist is left unmodified. 250 */ 251static errno_t ntfs_rl_replace(ntfs_runlist *dst_runlist, ntfs_rl_element *src, 252 unsigned s_size, unsigned loc) 253{ 254 ntfs_rl_element *d_rl; 255 long delta; 256 unsigned d_elements; 257 unsigned tail; /* Start of tail of @dst_runlist. */ 258 unsigned marker;/* End of the inserted runs. */ 259 unsigned left; /* Left end of @src needs merging. */ 260 unsigned right; /* Right end of @src needs merging. */ 261 262 ntfs_debug("Entering."); 263 if (!dst_runlist || !src || !s_size) 264 panic("%s(): !dst_runlist || !src || !s_size\n", __FUNCTION__); 265 d_rl = dst_runlist->rl; 266 d_elements = dst_runlist->elements; 267 /* First, see if the left and right ends need merging. */ 268 left = 0; 269 if (loc > 0) 270 left = ntfs_rl_can_merge(d_rl + loc - 1, src); 271 right = 0; 272 if (loc + 1 < d_elements) 273 right = ntfs_rl_can_merge(src + s_size - 1, d_rl + loc + 1); 274 /* 275 * First run after the @src runs that have been inserted, i.e. where 276 * the tail of @dst needs to be moved to. Nominally, @marker equals 277 * @loc + @s_size, i.e. location + number of runs in @src. However, if 278 * @left, then the first run of @src will be merged with one in @dst. 279 */ 280 marker = loc + s_size - left; 281 /* 282 * Offset of the tail of the destination runlist. This needs to be 283 * moved out of the way to make space for the runs to be copied from 284 * @src, i.e. this is the first run of the tail of the destination 285 * runlist. Nominally, @tail equals @loc + 1, i.e. location, skipping 286 * the replaced run. However, if @right, then one of the runs of the 287 * destination runlist will be merged into @src. 288 */ 289 tail = loc + 1 + right; 290 /* 291 * Extend the destination runlist reallocating the array buffer if 292 * needed. Note we will need less if the left, right, or both ends get 293 * merged. The -1 accounts for the run being replaced. 294 * 295 * If @delta < 0, we cannot reallocate or we would loose the end @delta 296 * element(s) of the destination runlist. Thus we cheat by not 297 * reallocating at all and by postponing the update of 298 * @dst_runlist->elements to later. 299 */ 300 delta = s_size - 1 - left - right; 301 if (delta > 0) { 302 errno_t err; 303 304 /* 305 * TODO: Optimise by using ntfs_rl_ins() but then the below 306 * becomes different for the delta > 0 and delta <= 0 cases. 307 */ 308 err = ntfs_rl_inc(dst_runlist, delta); 309 if (err) 310 return err; 311 d_rl = dst_runlist->rl; 312 } 313 /* 314 * We are guaranteed to succeed from here so can start modifying the 315 * original runlists. 316 */ 317 /* 318 * First, merge the left and right ends, if necessary. Note, right end 319 * goes first because, if s_size is 1, and both right and left are 1, 320 * @src is updated in the right merge and the updated value is needed 321 * for the left merge. 322 */ 323 if (right) 324 __ntfs_rl_merge(src + s_size - 1, d_rl + loc + 1); 325 if (left) 326 __ntfs_rl_merge(d_rl + loc - 1, src); 327 /* Move the tail of @dst to its destination. */ 328 ntfs_rl_move(d_rl + marker, d_rl + tail, d_elements - tail); 329 /* Copy in @src. */ 330 ntfs_rl_copy(d_rl + loc, src + left, s_size - left); 331 /* We may have changed the length of the file, so fix the end marker. */ 332 if (d_elements - tail > 0 && d_rl[marker].lcn == LCN_ENOENT) 333 d_rl[marker].vcn = d_rl[marker - 1].vcn + 334 d_rl[marker - 1].length; 335 /* If we postponed the @dst_runlist->elements update, do it now. */ 336 if (delta < 0) 337 dst_runlist->elements += delta; 338 ntfs_debug("Done, delta %ld.", delta); 339 return 0; 340} 341 342/** 343 * ntfs_rl_insert - insert a runlist into another 344 * @dst_runlist: destination runlist to work on 345 * @src: array of runlist elements to be inserted 346 * @s_size: number of elements in @src (excluding end marker) 347 * @loc: index in destination before which to insert @src 348 * 349 * Insert the runlist @src before the runlist element @loc in the runlist 350 * @dst_runlist. Merge the left end of the new runlist, if necessary. Adjust 351 * the size of the hole after the inserted runlist. 352 * 353 * Note this function can only be used if not the whole hole is being filled. 354 * 355 * It is up to the caller to serialize access to the runlists. 356 * 357 * Return 0 on success and ENOMEM if not enough memory to reallocate the 358 * runlist, in which case the destination runlist is left unmodified. 359 */ 360static errno_t ntfs_rl_insert(ntfs_runlist *dst_runlist, ntfs_rl_element *src, 361 unsigned s_size, unsigned loc) 362{ 363 ntfs_rl_element *d_rl; 364 errno_t err; 365 unsigned d_elements; 366 unsigned left; /* Left end of @src needs merging. */ 367 unsigned disc; /* Discontinuity between @dst_runlist and @src. */ 368 unsigned marker;/* End of the inserted runs. */ 369 370 ntfs_debug("Entering."); 371 if (!dst_runlist || !src || !s_size) 372 panic("%s(): !dst_runlist || !src || !s_size\n", __FUNCTION__); 373 d_rl = dst_runlist->rl; 374 d_elements = dst_runlist->elements; 375 /* 376 * Determine if there is a discontinuity between the end of the 377 * destination runlist and the start of @src. This means we might need 378 * to insert a "not mapped" run. 379 */ 380 disc = 0; 381 if (!loc) { 382 left = 0; 383 if (src[0].vcn > 0) 384 disc = 1; 385 } else { 386 s64 merged_length; 387 388 left = ntfs_rl_can_merge(d_rl + loc - 1, src); 389 merged_length = d_rl[loc - 1].length; 390 if (left) 391 merged_length += src[0].length; 392 if (src[0].vcn > d_rl[loc - 1].vcn + merged_length) 393 disc = 1; 394 } 395 /* 396 * Space required: @dst_runlist size + @src size, less 1 if we will 397 * merge the run on the left, plus 1 if there was a discontinuity. 398 */ 399 /* TODO: Optimise by using ntfs_rl_ins(). */ 400 err = ntfs_rl_inc(dst_runlist, s_size - left + disc); 401 if (err) 402 return err; 403 d_rl = dst_runlist->rl; 404 /* 405 * We are guaranteed to succeed from here so can start modifying the 406 * original runlist. 407 */ 408 if (left) 409 __ntfs_rl_merge(d_rl + loc - 1, src); 410 /* 411 * First run after the @src runs that have been inserted. Nominally, 412 * @marker equals @loc + @s_size, i.e. location + number of runs in 413 * @src. However, if @left, then the first run in @src has been merged 414 * with one in @dst. And if @disc, then @dst and @src do not meet and 415 * we need an extra run to fill the gap. 416 */ 417 marker = loc + s_size - left + disc; 418 /* Move the tail of @dst_runlist out of the way, then copy in @src. */ 419 ntfs_rl_move(d_rl + marker, d_rl + loc, d_elements - loc); 420 ntfs_rl_copy(d_rl + loc + disc, src + left, s_size - left); 421 /* Adjust both VCN and length of the first run after the insertion. */ 422 d_rl[marker].vcn = d_rl[marker - 1].vcn + d_rl[marker - 1].length; 423 if (d_rl[marker].lcn == LCN_HOLE || 424 d_rl[marker].lcn == LCN_RL_NOT_MAPPED) 425 d_rl[marker].length = d_rl[marker + 1].vcn - d_rl[marker].vcn; 426 /* Writing beyond the end of the file and there is a discontinuity. */ 427 if (disc) { 428 if (loc > 0) { 429 d_rl[loc].vcn = d_rl[loc - 1].vcn + 430 d_rl[loc - 1].length; 431 d_rl[loc].length = d_rl[loc + 1].vcn - d_rl[loc].vcn; 432 } else { 433 d_rl[loc].vcn = 0; 434 d_rl[loc].length = d_rl[loc + 1].vcn; 435 } 436 d_rl[loc].lcn = LCN_RL_NOT_MAPPED; 437 } 438 ntfs_debug("Done."); 439 return 0; 440} 441 442/** 443 * ntfs_rl_append - append a runlist after a given element 444 * @dst_runlist: destination runlist to work on 445 * @src: array of runlist elements to be inserted 446 * @s_size: number of elements in @src (excluding end marker) 447 * @loc: index in destination after which to append @src 448 * 449 * Append the runlist @src after the runlist element @loc in the runlist 450 * @dst_runlist. Merge the right end of the new runlist, if necessary. Adjust 451 * the size of the hole before the appended runlist. 452 * 453 * It is up to the caller to serialize access to the runlists. 454 * 455 * Return 0 on success and ENOMEM if not enough memory to reallocate the 456 * runlist, in which case the destination runlist is left unmodified. 457 */ 458static errno_t ntfs_rl_append(ntfs_runlist *dst_runlist, ntfs_rl_element *src, 459 unsigned s_size, unsigned loc) 460{ 461 ntfs_rl_element *d_rl; 462 errno_t err; 463 unsigned d_elements; 464 unsigned right; /* Right end of @src needs merging. */ 465 unsigned marker;/* End of the inserted runs. */ 466 467 ntfs_debug("Entering."); 468 if (!dst_runlist || !src || !s_size) 469 panic("%s(): !dst_runlist || !src || !s_size\n", __FUNCTION__); 470 d_rl = dst_runlist->rl; 471 d_elements = dst_runlist->elements; 472 /* First, check if the right hand end needs merging. */ 473 right = 0; 474 if (loc + 1 < d_elements) 475 right = ntfs_rl_can_merge(src + s_size - 1, d_rl + loc + 1); 476 /* 477 * Space required: @dst_runlist size + @src size, less 1 if we will 478 * merge the run on the right. 479 */ 480 /* TODO: Optimise by using ntfs_rl_ins(). */ 481 err = ntfs_rl_inc(dst_runlist, s_size - right); 482 if (err) 483 return err; 484 d_rl = dst_runlist->rl; 485 /* 486 * We are guaranteed to succeed from here so can start modifying the 487 * original runlists. 488 */ 489 /* First, merge the right hand end, if necessary. */ 490 if (right) 491 __ntfs_rl_merge(src + s_size - 1, d_rl + loc + 1); 492 /* First run after the @src runs that have been inserted. */ 493 marker = loc + s_size + 1; 494 /* Move the tail of @dst_runlist out of the way, then copy in @src. */ 495 ntfs_rl_move(d_rl + marker, d_rl + loc + 1 + right, 496 d_elements - (loc + 1 + right)); 497 ntfs_rl_copy(d_rl + loc + 1, src, s_size); 498 /* Adjust the size of the preceding hole. */ 499 d_rl[loc].length = d_rl[loc + 1].vcn - d_rl[loc].vcn; 500 /* We may have changed the length of the file, so fix the end marker. */ 501 if (d_rl[marker].lcn == LCN_ENOENT) 502 d_rl[marker].vcn = d_rl[marker - 1].vcn + 503 d_rl[marker - 1].length; 504 ntfs_debug("Done."); 505 return 0; 506} 507 508/** 509 * ntfs_rl_split - insert a runlist into the centre of a hole 510 * @dst_runlist: destination runlist to insert into 511 * @src: array of runlist elements to be inserted 512 * @s_size: number of elements in @src (excluding end marker) 513 * @loc: index in destination at which to split and insert @src 514 * 515 * Split the runlist @dst_runlist at @loc into two and insert @src in between 516 * the two fragments. No merging of runlists is necessary. Adjust the size of 517 * the holes either side. 518 * 519 * It is up to the caller to serialize access to the runlists. 520 * 521 * Return 0 on success and ENOMEM if not enough memory to reallocate the 522 * runlist, in which case the destination runlist is left unmodified. 523 */ 524static errno_t ntfs_rl_split(ntfs_runlist *dst_runlist, ntfs_rl_element *src, 525 unsigned s_size, unsigned loc) 526{ 527 ntfs_rl_element *d_rl; 528 errno_t err; 529 530 ntfs_debug("Entering."); 531 if (!dst_runlist || !src || !s_size) 532 panic("%s(): !dst_runlist || !src || !s_size\n", __FUNCTION__); 533 /* 534 * Move the tail of the destination runlist out of the way, 535 * reallocating the array buffer if needed. Note we need space for 536 * both the source runlist and for a new hole. 537 */ 538 err = ntfs_rl_ins(dst_runlist, loc + 1, s_size + 1); 539 if (err) 540 return err; 541 d_rl = dst_runlist->rl; 542 /* Copy @src into the destination runlist. */ 543 ntfs_rl_copy(d_rl + loc + 1, src, s_size); 544 /* Adjust the size of the holes either size of @src. */ 545 d_rl[loc].length = d_rl[loc + 1].vcn - d_rl[loc].vcn; 546 d_rl[loc + s_size + 1].lcn = d_rl[loc].lcn; 547 loc += s_size; 548 d_rl[loc + 1].vcn = d_rl[loc].vcn + d_rl[loc].length; 549 loc += 1; 550 d_rl[loc].length = d_rl[loc + 1].vcn - d_rl[loc].vcn; 551 ntfs_debug("Done."); 552 return 0; 553} 554 555/** 556 * ntfs_rl_merge - merge two runlists into one 557 * @dst_runlist: destination runlist to merge source runlist into 558 * @src_runlist: source runlist to merge into destination 559 * 560 * First we sanity check the two runlists @dst_runlist and @src_runlist to make 561 * sure that they are sensible and can be merged. The source runlist 562 * @src_runlist must be either after the destination runlist @dst_runlist or 563 * completely within a hole (or unmapped region) of @dst_runlist. 564 * 565 * Merging of runlists is necessary in two cases: 566 * 1. When attribute lists are used and a further extent is being mapped. 567 * 2. When new clusters are allocated to fill a hole or extend a file. 568 * 569 * There are four possible ways the source runlist can be merged. It can: 570 * - be inserted at the beginning of a hole, 571 * - split the hole in two and be inserted between the two fragments, 572 * - be appended at the end of a hole, or it can 573 * - replace the whole hole. 574 * It can also be appended to the end of the runlist, which is just a variant 575 * of the insert case. 576 * 577 * On success, return 0 and @dst_runlist is updated to be the merged runlist. 578 * Note, @src_runlist is deinitialized and the runlist element arrays of both 579 * @src_runlist and @dst_runlist are deallocated before returning so you cannot 580 * use old pointers into the arrays for anything any more. (Strictly speaking 581 * the merged runlist may be the same as @dst_runlist but this is irrelevant.) 582 * 583 * On error, return errno, in which case both runlists are left unmodified. 584 * The following error codes are defined: 585 * ENOMEM - Not enough memory to allocate runlist array. 586 * EINVAL - Invalid parameters were passed in. 587 * ERANGE - The runlists overlap and cannot be merged. 588 * 589 * Locking: - The caller must have locked the destination runlist for writing. 590 * - The lock of the source runlist is not touched thus is irrelevant. 591 * It is assumed that the source is just a temporary runlist. 592 * - The destination runlist is modified. 593 * - The source runlist's array of runlist elements is deallocated. 594 */ 595errno_t ntfs_rl_merge(ntfs_runlist *dst_runlist, ntfs_runlist *src_runlist) 596{ 597 VCN marker_vcn; 598 ntfs_rl_element *d_rl, *s_rl; 599 unsigned d_elements, s_elements, d_alloc, s_alloc; 600 unsigned di, si; /* Current index in @[ds]_rl. */ 601 unsigned s_start; /* First index in @s_rl with lcn >= LCN_HOLE. */ 602 unsigned d_ins; /* Index in @d_rl at which to insert @s_rl. */ 603 unsigned d_final; /* Last index in @d_rl with lcn >= LCN_HOLE. */ 604 unsigned s_final; /* Last index in @s_rl with lcn >= LCN_HOLE. */ 605 unsigned ss; /* Number of relevant elements in @s_rl. */ 606 unsigned marker; 607 errno_t err; 608 BOOL start, finish; 609 610 ntfs_debug("Destination runlist:"); 611 ntfs_debug_runlist_dump(dst_runlist); 612 ntfs_debug("Source runlist:"); 613 ntfs_debug_runlist_dump(src_runlist); 614 if (!src_runlist || !dst_runlist) 615 panic("%s(): No %s runlist was supplied.\n", __FUNCTION__, 616 !src_runlist ? "source" : "destination"); 617 s_rl = src_runlist->rl; 618 s_elements = src_runlist->elements; 619 s_alloc = src_runlist->alloc; 620 /* If the source runlist is empty, nothing to do. */ 621 if (!s_elements) { 622 if (s_alloc) 623 OSFree(s_rl, s_alloc, ntfs_malloc_tag); 624 goto done; 625 } 626 d_rl = dst_runlist->rl; 627 d_elements = dst_runlist->elements; 628 d_alloc = dst_runlist->alloc; 629 /* Check for the case where the first mapping is being done now. */ 630 if (!d_elements) { 631 /* Complete the source runlist if necessary. */ 632 if (s_rl[0].vcn) { 633 err = ntfs_rl_ins(src_runlist, 0, 1); 634 if (err) 635 return err; 636 s_rl = src_runlist->rl; 637 s_rl[0].vcn = 0; 638 s_rl[0].lcn = LCN_RL_NOT_MAPPED; 639 s_rl[0].length = s_rl[1].vcn; 640 } 641 /* Return the source runlist as the destination. */ 642 if (d_alloc) 643 OSFree(d_rl, d_alloc, ntfs_malloc_tag); 644 dst_runlist->rl = src_runlist->rl; 645 dst_runlist->elements = src_runlist->elements; 646 dst_runlist->alloc = src_runlist->alloc; 647 goto done; 648 } 649 /* 650 * We have two runlists which we need to merge. Start, by skipping all 651 * unmapped start elements in the source runlist. 652 */ 653 si = 0; 654 while (s_rl[si].length && s_rl[si].lcn < LCN_HOLE) 655 si++; 656 /* May not have an entirely unmapped source runlist. */ 657 if (!s_rl[si].length) 658 panic("%s(): Source runlist is entirely unmapped!\n", 659 __FUNCTION__); 660 /* Record the starting point in @s_rl at which to begin merging. */ 661 s_start = si; 662 /* 663 * Skip forward in @d_rl until we reach the position where @s_rl needs 664 * to be inserted. If we reach the end of @d_rl, @s_rl just needs to 665 * be appended to @d_rl. 666 */ 667 for (d_ins = 0; d_rl[d_ins].length; d_ins++) { 668 if (d_rl[d_ins + 1].vcn > s_rl[s_start].vcn) 669 break; 670 } 671 /* Sanity check for illegal overlaps. */ 672 if ((d_rl[d_ins].vcn == s_rl[s_start].vcn) && (d_rl[d_ins].lcn >= 0) && 673 (s_rl[s_start].lcn >= 0)) { 674 ntfs_error(NULL, "Runlists overlap. Cannot merge!"); 675 return ERANGE; 676 } 677 /* Scan backwards for the last element with lcn >= LCN_HOLE. */ 678 for (s_final = s_elements - 1; s_final > 0; s_final--) { 679 if (s_rl[s_final].lcn >= LCN_HOLE) 680 break; 681 } 682 for (d_final = d_elements - 1; d_final > 0; d_final--) { 683 if (d_rl[d_final].lcn >= LCN_HOLE) 684 break; 685 } 686 /* Calculate the number of elements relevant to the merge. */ 687 ss = s_final - s_start + 1; 688 /* 689 * Work out the type of merge needed. To do so we setup to variables. 690 * 691 * If @start is true, the merge point is either at the end of the 692 * destination runlist, i.e. at the end of the attribute represented by 693 * the destination runlist, or at the start of a hole or an unmapped 694 * region. 695 * 696 * If @start is false, the merge point is not at the end of the 697 * destination runlist nor is it at the start of a hole or unmapped 698 * region. 699 * 700 * If @finish is true, the merge point is not at the end of the 701 * destination runlist (thus it must be in a hole or unmapped region) 702 * and the end of the hole or unmapped region lies within the end of 703 * the source runlist. 704 * 705 * If @finish is false, the merge point is either at the end of the 706 * destination runlist or the end of the hole or unmapped region lies 707 * outside the end of the source runlist. 708 */ 709 start = (d_rl[d_ins].lcn < LCN_RL_NOT_MAPPED || 710 d_rl[d_ins].vcn == s_rl[s_start].vcn); 711 finish = (d_rl[d_ins].lcn >= LCN_RL_NOT_MAPPED && 712 d_rl[d_ins].vcn + d_rl[d_ins].length <= 713 s_rl[s_elements - 1].vcn); 714 /* Or we will lose an end marker. */ 715 if (finish && !d_rl[d_ins].length) 716 ss++; 717 /* 718 * Is there an end of attribute marker in the source runlist that we 719 * need to preserve? 720 */ 721 marker = 0; 722 marker_vcn = 0; 723 if (s_rl[s_elements - 1].lcn == LCN_ENOENT) { 724 marker = s_elements - 1; 725 marker_vcn = s_rl[marker].vcn; 726 if (d_rl[d_ins].vcn + d_rl[d_ins].length > 727 s_rl[s_elements - 2].vcn) 728 finish = FALSE; 729 } 730#if 1 731 ntfs_debug("d_final %d, d_elements %d", d_final, d_elements); 732 ntfs_debug("s_start = %d, s_final = %d, s_elements = %d", s_start, 733 s_final, s_elements); 734 ntfs_debug("start = %d, finish = %d", start ? 1 : 0, finish ? 1 : 0); 735 ntfs_debug("ss = %d, d_ins = %d", ss, d_ins); 736#endif 737 /* See above for meanings of @start and @finish. */ 738 if (start) { 739 if (finish) 740 err = ntfs_rl_replace(dst_runlist, s_rl + s_start, ss, 741 d_ins); 742 else 743 err = ntfs_rl_insert(dst_runlist, s_rl + s_start, ss, 744 d_ins); 745 } else { 746 if (finish) 747 err = ntfs_rl_append(dst_runlist, s_rl + s_start, ss, 748 d_ins); 749 else 750 err = ntfs_rl_split(dst_runlist, s_rl + s_start, ss, 751 d_ins); 752 } 753 if (err) { 754 ntfs_error(NULL, "Merge failed (error %d).", (int)err); 755 return err; 756 } 757 /* Merged, can discard source runlist now. */ 758 OSFree(s_rl, s_alloc, ntfs_malloc_tag); 759 d_rl = dst_runlist->rl; 760 di = dst_runlist->elements - 1; 761 /* Deal with the end of attribute marker if @s_rl ended after @d_rl. */ 762 if (marker && d_rl[di].vcn <= marker_vcn) { 763 unsigned slots; 764 765 ntfs_debug("Triggering marker code."); 766 d_alloc = dst_runlist->alloc; 767 if (d_rl[di].vcn == marker_vcn) { 768 ntfs_debug("Old marker = 0x%llx, replacing with " 769 "LCN_ENOENT.", 770 (unsigned long long)d_rl[di].lcn); 771 d_rl[di].lcn = LCN_ENOENT; 772 goto done; 773 } 774 /* 775 * We need to create an unmapped runlist element in @d_rl or 776 * extend an existing one before adding the LCN_ENOENT 777 * terminator element. 778 */ 779 slots = 0; 780 /* 781 * We can discard an existing LCN_ENOENT terminator and hence 782 * gain a slot. 783 */ 784 if (d_rl[di].lcn == LCN_ENOENT) { 785 di--; 786 slots = 1; 787 } 788 /* 789 * If not unmapped, add an unmapped runlist element. 790 * Otherwise simply extend the unmapped element. 791 */ 792 if (d_rl[di].lcn != LCN_RL_NOT_MAPPED) { 793 if (!slots) { 794 slots = 2; 795 err = ntfs_rl_inc(dst_runlist, 2); 796 if (err) { 797fatal_oom: 798 panic("%s(): Fatal out of memory " 799 "condition " 800 "encountered (slots " 801 "%d).\n", 802 __FUNCTION__, slots); 803 } 804 d_rl = dst_runlist->rl; 805 /* Need to set vcn. */ 806 d_rl[di + 1].vcn = d_rl[di].vcn + 807 d_rl[di].length; 808 } 809 di++; 810 d_rl[di].lcn = LCN_RL_NOT_MAPPED; 811 /* We now used up a slot. */ 812 slots--; 813 } 814 d_rl[di].length = marker_vcn - d_rl[di].vcn; 815 /* Finally add the LCN_ENOENT terminator. */ 816 di++; 817 if (!slots) { 818 err = ntfs_rl_inc(dst_runlist, 1); 819 if (err) { 820 slots = 1; 821 goto fatal_oom; 822 } 823 d_rl = dst_runlist->rl; 824 } 825 d_rl[di].vcn = marker_vcn; 826 d_rl[di].lcn = LCN_ENOENT; 827 d_rl[di].length = 0; 828 } 829done: 830 /* The merge was completed successfully. */ 831 ntfs_debug("Merged runlist:"); 832 ntfs_debug_runlist_dump(dst_runlist); 833 return 0; 834} 835 836/** 837 * ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist 838 * @vol: ntfs volume on which the attribute resides 839 * @a: attribute record whose mapping pairs array to decompress 840 * @runlist: runlist in which to insert @a's runlist 841 * 842 * Decompress the attribute @a's mapping pairs array into a runlist. On 843 * success, return the decompressed runlist in @runlist. 844 * 845 * If @runlist already contains a runlist, the decompressed runlist is inserted 846 * into the appropriate place in @runlist and the resultant, combined runlist 847 * is returned in @runlist. 848 * 849 * On error, return errno. @runlist is left unmodified in that case. 850 * 851 * The following error codes are defined: 852 * ENOMEM - Not enough memory to allocate runlist array. 853 * EIO - Corrupt attribute. 854 * EINVAL - Invalid parameters were passed in. 855 * ERANGE - The two runlists overlap. 856 * 857 * Locking: - The caller must have locked the runlist for writing. 858 * - This function does not touch the lock. 859 * - The runlist is modified. 860 * 861 * FIXME: For now we take the conceptionally simplest approach of creating the 862 * new runlist disregarding the already existing one and then splicing the two 863 * into one, if that is possible (we check for overlap and discard the new 864 * runlist if overlap is present before returning ERANGE). 865 */ 866errno_t ntfs_mapping_pairs_decompress(ntfs_volume *vol, const ATTR_RECORD *a, 867 ntfs_runlist *runlist) 868{ 869 VCN vcn; /* Current vcn. */ 870 LCN lcn; /* Current lcn. */ 871 s64 deltaxcn; /* Change in [vl]cn. */ 872 ntfs_rl_element *rl; /* The output runlist. */ 873 u8 *buf; /* Current position in mapping pairs array. */ 874 u8 *a_end; /* End of attribute. */ 875 unsigned rlsize; /* Size of runlist buffer. */ 876 unsigned rlpos; /* Current runlist position in units of 877 ntfs_rl_elements. */ 878 unsigned b; /* Current byte offset in buf. */ 879 errno_t err = EIO; 880 881 /* Make sure @a exists and is non-resident. */ 882 if (!a || !a->non_resident || sle64_to_cpu(a->lowest_vcn) < (VCN)0) { 883 ntfs_error(vol->mp, "Invalid arguments."); 884 return EINVAL; 885 } 886 /* Start at vcn = lowest_vcn and lcn 0. */ 887 vcn = sle64_to_cpu(a->lowest_vcn); 888 lcn = 0; 889 /* Get start of the mapping pairs array. */ 890 buf = (u8*)a + le16_to_cpu(a->mapping_pairs_offset); 891 a_end = (u8*)a + le32_to_cpu(a->length); 892 if (buf < (u8*)a || buf > a_end) { 893 ntfs_error(vol->mp, "Corrupt attribute."); 894 return EIO; 895 } 896 /* If the mapping pairs array is valid but empty, nothing to do. */ 897 if (!vcn && !*buf) 898 return 0; 899 /* Current position in runlist array. */ 900 rlpos = 0; 901 rlsize = NTFS_ALLOC_BLOCK; 902 /* Allocate NTFS_ALLOC_BLOCK bytes for the runlist. */ 903 rl = OSMalloc(rlsize, ntfs_malloc_tag); 904 if (!rl) 905 return ENOMEM; 906 /* Insert unmapped starting element if necessary. */ 907 if (vcn) { 908 rl->vcn = 0; 909 rl->lcn = LCN_RL_NOT_MAPPED; 910 rl->length = vcn; 911 rlpos++; 912 } 913 while (buf < a_end && *buf) { 914 /* 915 * Allocate more memory if needed, including space for the 916 * not-mapped and terminator elements. 917 */ 918 if (((rlpos + 3) * sizeof(*rl)) > rlsize) { 919 ntfs_rl_element *rl2; 920 921 rl2 = OSMalloc(rlsize + NTFS_ALLOC_BLOCK, 922 ntfs_malloc_tag); 923 if (!rl2) { 924 err = ENOMEM; 925 goto err; 926 } 927 memcpy(rl2, rl, rlsize); 928 OSFree(rl, rlsize, ntfs_malloc_tag); 929 rl = rl2; 930 rlsize += NTFS_ALLOC_BLOCK; 931 } 932 /* Enter the current vcn into the current runlist element. */ 933 rl[rlpos].vcn = vcn; 934 /* 935 * Get the change in vcn, i.e. the run length in clusters. 936 * Doing it this way ensures that we sign-extend negative 937 * values. A negative run length does not make any sense, but 938 * hey, I did not design NTFS... 939 */ 940 b = *buf & 0xf; 941 if (b) { 942 if (buf + b >= a_end) 943 goto io_err; 944 for (deltaxcn = (s8)buf[b--]; b; b--) 945 deltaxcn = (deltaxcn << 8) + buf[b]; 946 } else { /* The length entry is compulsory. */ 947 ntfs_error(vol->mp, "Missing length entry in mapping " 948 "pairs array."); 949 deltaxcn = (s64)-1; 950 } 951 /* 952 * Assume a negative length to indicate data corruption and 953 * hence clean-up and return NULL. 954 */ 955 if (deltaxcn < 0) { 956 ntfs_error(vol->mp, "Invalid length in mapping pairs " 957 "array."); 958 goto err; 959 } 960 /* 961 * Enter the current run length into the current runlist 962 * element. 963 */ 964 rl[rlpos].length = deltaxcn; 965 /* Increment the current vcn by the current run length. */ 966 vcn += deltaxcn; 967 /* 968 * There might be no lcn change at all, as is the case for 969 * sparse clusters on NTFS 3.0+, in which case we set the lcn 970 * to LCN_HOLE. 971 */ 972 if (!(*buf & 0xf0)) 973 rl[rlpos].lcn = LCN_HOLE; 974 else { 975 /* Get the lcn change which really can be negative. */ 976 u8 b2 = *buf & 0xf; 977 b = b2 + ((*buf >> 4) & 0xf); 978 if (buf + b >= a_end) 979 goto io_err; 980 for (deltaxcn = (s8)buf[b--]; b > b2; b--) 981 deltaxcn = (deltaxcn << 8) + buf[b]; 982 /* Change the current lcn to its new value. */ 983 lcn += deltaxcn; 984#ifdef DEBUG 985 /* 986 * On NTFS 1.2-, apparently one can have lcn == -1 to 987 * indicate a hole. But we have not verified ourselves 988 * whether it is really the lcn or the deltaxcn that is 989 * -1. So if either is found give us a message so we 990 * can investigate it further! 991 */ 992 if (vol->major_ver < 3) { 993 if (deltaxcn == (LCN)-1) 994 ntfs_error(vol->mp, "lcn delta == -1"); 995 if (lcn == (LCN)-1) 996 ntfs_error(vol->mp, "lcn == -1"); 997 } 998#endif 999 /* Check lcn is not below -1. */ 1000 if (lcn < (LCN)-1) { 1001 ntfs_error(vol->mp, "Invalid LCN < -1 in " 1002 "mapping pairs array."); 1003 goto err; 1004 } 1005 /* Enter the current lcn into the runlist element. */ 1006 rl[rlpos].lcn = lcn; 1007 } 1008 /* Get to the next runlist element. */ 1009 rlpos++; 1010 /* Increment the buffer position to the next mapping pair. */ 1011 buf += (*buf & 0xf) + ((*buf >> 4) & 0xf) + 1; 1012 } 1013 if (buf >= a_end) 1014 goto io_err; 1015 /* 1016 * The highest_vcn must be equal to the final vcn in the runlist - 1, 1017 * or something has gone badly wrong. 1018 */ 1019 deltaxcn = sle64_to_cpu(a->highest_vcn); 1020 if (vcn - 1 != deltaxcn) 1021 goto io_err; 1022 /* Setup not mapped runlist element if this is the base extent. */ 1023 if (!a->lowest_vcn) { 1024 VCN max_cluster; 1025 1026 max_cluster = ((sle64_to_cpu(a->allocated_size) + 1027 vol->cluster_size_mask) >> 1028 vol->cluster_size_shift) - 1; 1029 /* 1030 * If there is a difference between the highest_vcn and the 1031 * highest cluster, the runlist is either corrupt or, more 1032 * likely, there are more extents following this one. 1033 */ 1034 if (deltaxcn < max_cluster) { 1035 ntfs_debug("More extents to follow; deltaxcn = " 1036 "0x%llx, max_cluster = 0x%llx", 1037 (unsigned long long)deltaxcn, 1038 (unsigned long long)max_cluster); 1039 rl[rlpos].vcn = vcn; 1040 vcn += rl[rlpos].length = max_cluster - deltaxcn; 1041 rl[rlpos].lcn = LCN_RL_NOT_MAPPED; 1042 rlpos++; 1043 } else if (deltaxcn > max_cluster) { 1044 ntfs_error(vol->mp, "Corrupt attribute. deltaxcn = " 1045 "0x%llx, max_cluster = 0x%llx", 1046 (unsigned long long)deltaxcn, 1047 (unsigned long long)max_cluster); 1048 goto io_err; 1049 } 1050 rl[rlpos].lcn = LCN_ENOENT; 1051 } else /* Not the base extent. There may be more extents to follow. */ 1052 rl[rlpos].lcn = LCN_RL_NOT_MAPPED; 1053 /* Setup terminating runlist element. */ 1054 rl[rlpos].vcn = vcn; 1055 rl[rlpos].length = (s64)0; 1056 /* If no existing runlist was specified, we are done. */ 1057 if (!runlist->elements) { 1058 if (runlist->alloc) 1059 OSFree(runlist->rl, runlist->alloc, ntfs_malloc_tag); 1060 runlist->rl = rl; 1061 runlist->elements = rlpos + 1; 1062 runlist->alloc = rlsize; 1063 ntfs_debug("Mapping pairs array successfully decompressed:"); 1064 ntfs_debug_runlist_dump(runlist); 1065 return 0; 1066 } else { 1067 ntfs_runlist tmp_rl; 1068 1069 /* 1070 * An existing runlist was specified, now combine the new and 1071 * old runlists checking for overlaps. 1072 */ 1073 tmp_rl.rl = rl; 1074 tmp_rl.elements = rlpos + 1; 1075 tmp_rl.alloc = rlsize; 1076 err = ntfs_rl_merge(runlist, &tmp_rl); 1077 if (!err) 1078 return err; 1079 ntfs_error(vol->mp, "Failed to merge runlists."); 1080 } 1081err: 1082 OSFree(rl, rlsize, ntfs_malloc_tag); 1083 return err; 1084io_err: 1085 ntfs_error(vol->mp, "Corrupt mapping pairs array in non-resident " 1086 "attribute."); 1087 err = EIO; 1088 goto err; 1089} 1090 1091/** 1092 * ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist 1093 * @rl: runlist to use for conversion 1094 * @vcn: vcn to convert 1095 * @clusters: optional return pointer for the number of contiguous clusters 1096 * 1097 * Convert the virtual cluster number @vcn of an attribute into a logical 1098 * cluster number (lcn) of a device using the runlist @rl to map vcns to their 1099 * corresponding lcns. 1100 * 1101 * If @clusters is not NULL, on success (i.e. we return >= LCN_HOLE) we return 1102 * the number of contiguous clusters after the returned lcn in *@clusters. 1103 * 1104 * Since lcns must be >= 0, we use negative return codes with special meaning: 1105 * 1106 * Return code Meaning / Description 1107 * ================================================== 1108 * LCN_HOLE Hole / not allocated on disk. 1109 * LCN_RL_NOT_MAPPED This is part of the runlist which has not been 1110 * inserted into the runlist yet. 1111 * LCN_ENOENT There is no such vcn in the attribute. 1112 * 1113 * Locking: - The caller must have locked the runlist (for reading or writing). 1114 * - This function does not touch the lock. 1115 * - The runlist is not modified. 1116 * 1117 * TODO: If we pass in the number of runlist elements we could attempt to 1118 * optimise the for loop into a quasi binary search. 1119 */ 1120LCN ntfs_rl_vcn_to_lcn(const ntfs_rl_element *rl, const VCN vcn, s64 *clusters) 1121{ 1122 unsigned i; 1123 1124 if (vcn < 0) 1125 panic("%s(): vcn < 0\n", __FUNCTION__); 1126 /* 1127 * If @rl is NULL, assume that we have found an unmapped runlist. The 1128 * caller can then attempt to map it and fail appropriately if 1129 * necessary. 1130 */ 1131 if (!rl) 1132 return LCN_RL_NOT_MAPPED; 1133 /* Catch out of lower bounds vcn. */ 1134 if (vcn < rl[0].vcn) 1135 return LCN_ENOENT; 1136 for (i = 0; rl[i].length; i++) { 1137 if (vcn < rl[i + 1].vcn) { 1138 const s64 ofs = vcn - rl[i].vcn; 1139 if (clusters) 1140 *clusters = rl[i].length - ofs; 1141 if (rl[i].lcn >= (LCN)0) 1142 return rl[i].lcn + ofs; 1143 return rl[i].lcn; 1144 } 1145 } 1146 /* 1147 * Set *@clusters just in case rl[i].lcn is LCN_HOLE. That should 1148 * never happen since the terminator element should never be of type 1149 * LCN_HOLE but better be safe than sorry. 1150 */ 1151 if (clusters) 1152 *clusters = 0; 1153 /* 1154 * The terminator element is setup to the correct value, i.e. one of 1155 * LCN_HOLE, LCN_RL_NOT_MAPPED, or LCN_ENOENT. 1156 */ 1157 if (rl[i].lcn < (LCN)0) 1158 return rl[i].lcn; 1159 /* Just in case... We could replace this with panic() some day. */ 1160 return LCN_ENOENT; 1161} 1162 1163/** 1164 * ntfs_rl_find_vcn_nolock - find a vcn in a runlist 1165 * @rl: runlist to search 1166 * @vcn: vcn to find 1167 * 1168 * Find the virtual cluster number @vcn in the runlist @rl and return the 1169 * address of the runlist element containing the @vcn on success. 1170 * 1171 * Return NULL if @rl is NULL or @vcn is in an unmapped part/out of bounds of 1172 * the runlist. 1173 * 1174 * Locking: The runlist must be locked on entry. 1175 */ 1176ntfs_rl_element *ntfs_rl_find_vcn_nolock(ntfs_rl_element *rl, const VCN vcn) 1177{ 1178 if (vcn < 0) 1179 panic("%s(): vcn < 0\n", __FUNCTION__); 1180 if (!rl || vcn < rl[0].vcn) 1181 return NULL; 1182 while (rl->length) { 1183 if (vcn < rl[1].vcn) { 1184 if (rl->lcn >= LCN_HOLE) 1185 return rl; 1186 return NULL; 1187 } 1188 rl++; 1189 } 1190 if (rl->lcn == LCN_ENOENT) 1191 return rl; 1192 return NULL; 1193} 1194 1195/** 1196 * ntfs_get_nr_significant_bytes - get number of bytes needed to store a number 1197 * @n: number for which to get the number of bytes for 1198 * 1199 * Return the number of bytes required to store @n unambiguously as 1200 * a signed number. 1201 * 1202 * This is used in the context of the mapping pairs array to determine how 1203 * many bytes will be needed in the array to store a given logical cluster 1204 * number (lcn) or a specific run length. 1205 * 1206 * Return the number of bytes written. This function cannot fail. 1207 */ 1208static inline int ntfs_get_nr_significant_bytes(const s64 n) 1209{ 1210 s64 l = n; 1211 int i; 1212 s8 j; 1213 1214 i = 0; 1215 do { 1216 l >>= 8; 1217 i++; 1218 } while (l != 0 && l != -1); 1219 j = (s8)(n >> (8 * (i - 1))) & 0xff; 1220 /* If the sign bit is wrong, we need an extra byte. */ 1221 if ((n < 0 && j >= 0) || (n > 0 && j < 0)) 1222 i++; 1223 return i; 1224} 1225 1226/** 1227 * ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array 1228 * @vol: ntfs volume (needed for the ntfs version) 1229 * @rl: locked runlist to determine the size of the mapping pairs of 1230 * @first_vcn: first vcn which to include in the mapping pairs array 1231 * @last_vcn: last vcn which to include in the mapping pairs array 1232 * @mp_size: destination pointer in which to return the size 1233 * 1234 * Walk the locked runlist @rl and calculate the size in bytes of the mapping 1235 * pairs array corresponding to the runlist @rl, starting at vcn @first_vcn and 1236 * finishing with vcn @last_vcn and return the size in *@mp_size. 1237 * 1238 * A @last_vcn of -1 means end of runlist and in that case the size of the 1239 * mapping pairs array corresponding to the runlist starting at vcn @first_vcn 1240 * and finishing at the end of the runlist is determined. 1241 * 1242 * This for example allows us to allocate a buffer of the right size when 1243 * building the mapping pairs array. 1244 * 1245 * If @rl is NULL, just return *@mp_size = 1 (for the single terminator byte). 1246 * 1247 * Return 0 on success and errno on error. On error *@mp_size is undefined. 1248 * The following error codes are defined: 1249 * EINVAL - Run list contains unmapped elements. Make sure to only pass 1250 * fully mapped runlists to this function. 1251 * EIO - The runlist is corrupt. 1252 * 1253 * Locking: @rl must be locked on entry (either for reading or writing), it 1254 * remains locked throughout, and is left locked upon return. 1255 */ 1256errno_t ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol, 1257 const ntfs_rl_element *rl, const VCN first_vcn, 1258 const VCN last_vcn, unsigned *mp_size) 1259{ 1260 LCN prev_lcn; 1261 int rls; 1262 BOOL the_end = FALSE; 1263 1264 if (first_vcn < 0) 1265 panic("%s(): first_vcn < 0\n", __FUNCTION__); 1266 if (last_vcn < -1) 1267 panic("%s(): last_vcn < -1\n", __FUNCTION__); 1268 if (last_vcn >= 0 && first_vcn > last_vcn) 1269 panic("%s(): last_vcn >= 0 && first_vcn > last_vcn\n", 1270 __FUNCTION__); 1271 if (!rl) { 1272 if (first_vcn) 1273 panic("%s(): first_vcn\n", __FUNCTION__); 1274 if (last_vcn > 0) 1275 panic("%s(): last_vcn > 0\n", __FUNCTION__); 1276 *mp_size = 1; 1277 return 0; 1278 } 1279 /* Skip to runlist element containing @first_vcn. */ 1280 while (rl->length && first_vcn >= rl[1].vcn) 1281 rl++; 1282 if ((!rl->length && first_vcn > rl->vcn) || first_vcn < rl->vcn) 1283 return EINVAL; 1284 prev_lcn = 0; 1285 /* Always need the termining zero byte. */ 1286 rls = 1; 1287 /* Do the first partial run if present. */ 1288 if (first_vcn > rl->vcn) { 1289 s64 delta, length = rl->length; 1290 1291 /* We know rl->length != 0 already. */ 1292 if (length < 0 || rl->lcn < LCN_HOLE) 1293 goto err; 1294 /* 1295 * If @last_vcn is given and finishes inside this run, cap the 1296 * run length. 1297 */ 1298 if (last_vcn >= 0 && rl[1].vcn > last_vcn) { 1299 s64 s1 = last_vcn + 1; 1300 if (rl[1].vcn > s1) 1301 length = s1 - rl->vcn; 1302 the_end = TRUE; 1303 } 1304 delta = first_vcn - rl->vcn; 1305 /* Header byte + length. */ 1306 rls += 1 + ntfs_get_nr_significant_bytes(length - delta); 1307 /* 1308 * If the logical cluster number (lcn) denotes a hole and we 1309 * are on NTFS 3.0+, we don't store it at all, i.e. we need 1310 * zero space. On earlier NTFS versions we just store the lcn. 1311 * Note: this assumes that on NTFS 1.2-, holes are stored with 1312 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1). 1313 */ 1314 if (rl->lcn >= 0 || vol->major_ver < 3) { 1315 prev_lcn = rl->lcn; 1316 if (rl->lcn >= 0) 1317 prev_lcn += delta; 1318 /* Change in lcn. */ 1319 rls += ntfs_get_nr_significant_bytes(prev_lcn); 1320 } 1321 /* Go to next runlist element. */ 1322 rl++; 1323 } 1324 /* Do the full runs. */ 1325 for (; rl->length && !the_end; rl++) { 1326 s64 length = rl->length; 1327 1328 if (length < 0 || rl->lcn < LCN_HOLE) 1329 goto err; 1330 /* 1331 * If @last_vcn is given and finishes inside this run, cap the 1332 * run length. 1333 */ 1334 if (last_vcn >= 0 && rl[1].vcn > last_vcn) { 1335 s64 s1 = last_vcn + 1; 1336 if (rl[1].vcn > s1) 1337 length = s1 - rl->vcn; 1338 the_end = TRUE; 1339 } 1340 /* Header byte + length. */ 1341 rls += 1 + ntfs_get_nr_significant_bytes(length); 1342 /* 1343 * If the logical cluster number (lcn) denotes a hole and we 1344 * are on NTFS 3.0+, we don't store it at all, i.e. we need 1345 * zero space. On earlier NTFS versions we just store the lcn. 1346 * Note: this assumes that on NTFS 1.2-, holes are stored with 1347 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1). 1348 */ 1349 if (rl->lcn >= 0 || vol->major_ver < 3) { 1350 /* Change in lcn. */ 1351 rls += ntfs_get_nr_significant_bytes(rl->lcn - 1352 prev_lcn); 1353 prev_lcn = rl->lcn; 1354 } 1355 } 1356 *mp_size = rls; 1357 return 0; 1358err: 1359 if (rl->lcn == LCN_RL_NOT_MAPPED) 1360 rls = EINVAL; 1361 else 1362 rls = EIO; 1363 return rls; 1364} 1365 1366/** 1367 * ntfs_write_significant_bytes - write the significant bytes of a number 1368 * @dst: destination buffer to write to 1369 * @dst_max: pointer to last byte of destination buffer for bounds checking 1370 * @n: number whose significant bytes to write 1371 * 1372 * Store in @dst, the minimum bytes of the number @n which are required to 1373 * identify @n unambiguously as a signed number, taking care not to exceed 1374 * @dest_max, the maximum position within @dst to which we are allowed to 1375 * write. 1376 * 1377 * This is used when building the mapping pairs array of a runlist to compress 1378 * a given logical cluster number (lcn) or a specific run length to the minumum 1379 * size possible. 1380 * 1381 * Return the number of bytes written on success. On error, i.e. the 1382 * destination buffer @dst is too small, return -ENOSPC. 1383 */ 1384static inline int ntfs_write_significant_bytes(s8 *dst, const s8 *dst_max, 1385 const s64 n) 1386{ 1387 s64 l = n; 1388 int i; 1389 s8 j; 1390 1391 i = 0; 1392 do { 1393 if (dst > dst_max) 1394 goto err; 1395 *dst++ = (s8)l & 0xff; 1396 l >>= 8; 1397 i++; 1398 } while (l != 0 && l != -1); 1399 j = (s8)(n >> (8 * (i - 1))) & 0xff; 1400 /* If the sign bit is wrong, we need an extra byte. */ 1401 if (n < 0 && j >= 0) { 1402 if (dst > dst_max) 1403 goto err; 1404 i++; 1405 *dst = (s8)-1; 1406 } else if (n > 0 && j < 0) { 1407 if (dst > dst_max) 1408 goto err; 1409 i++; 1410 *dst = (s8)0; 1411 } 1412 return i; 1413err: 1414 return -ENOSPC; 1415} 1416 1417/** 1418 * ntfs_mapping_pairs_build - build the mapping pairs array from a runlist 1419 * @vol: ntfs volume (needed for the ntfs version) 1420 * @dst: destination buffer to which to write the mapping pairs array 1421 * @dst_len: size of destination buffer @dst in bytes 1422 * @rl: locked runlist for which to build the mapping pairs array 1423 * @first_vcn: first vcn which to include in the mapping pairs array 1424 * @last_vcn: last vcn which to include in the mapping pairs array 1425 * @stop_vcn: first vcn outside destination buffer on success or ENOSPC 1426 * 1427 * Create the mapping pairs array from the locked runlist @rl, starting at vcn 1428 * @first_vcn and finishing with vcn @last_vcn and save the array in @dst. 1429 * @dst_len is the size of @dst in bytes and it should be at least equal to the 1430 * value obtained by calling ntfs_get_size_for_mapping_pairs(). 1431 * 1432 * A @last_vcn of -1 means end of runlist and in that case the mapping pairs 1433 * array corresponding to the runlist starting at vcn @first_vcn and finishing 1434 * at the end of the runlist is created. 1435 * 1436 * If @rl is NULL, just write a single terminator byte to @dst. 1437 * 1438 * On success or ENOSPC error, if @stop_vcn is not NULL, *@stop_vcn is set to 1439 * the first vcn outside the destination buffer. Note that on error, @dst has 1440 * been filled with all the mapping pairs that will fit, thus it can be treated 1441 * as partial success, in that a new attribute extent needs to be created or 1442 * the next extent has to be used and the mapping pairs build has to be 1443 * continued with @first_vcn set to *@stop_vcn. 1444 * 1445 * Return 0 on success and errno on error. The following error codes are 1446 * defined: 1447 * EINVAL - Run list contains unmapped elements. Make sure to only pass 1448 * fully mapped runlists to this function. 1449 * EIO - The runlist is corrupt. 1450 * ENOSPC - The destination buffer is too small. 1451 * 1452 * Locking: @rl must be locked on entry (either for reading or writing), it 1453 * remains locked throughout, and is left locked upon return. 1454 */ 1455errno_t ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst, 1456 const unsigned dst_len, const ntfs_rl_element *rl, 1457 const VCN first_vcn, const VCN last_vcn, VCN *const stop_vcn) 1458{ 1459 LCN prev_lcn; 1460 s8 *dst_max, *dst_next; 1461 errno_t err = ENOSPC; 1462 BOOL the_end = FALSE; 1463 s8 len_len, lcn_len; 1464 1465 if (first_vcn < 0) 1466 panic("%s(): first_vcn < 0\n", __FUNCTION__); 1467 if (last_vcn < -1) 1468 panic("%s(): last_vcn < -1\n", __FUNCTION__); 1469 if (last_vcn >= 0 && first_vcn > last_vcn) 1470 panic("%s(): last_vcn >= 0 && first_vcn > last_vcn\n", 1471 __FUNCTION__); 1472 if (dst_len < 1) 1473 panic("%s(): dst_len < 1\n", __FUNCTION__); 1474 if (!rl) { 1475 if (first_vcn) 1476 panic("%s(): first_vcn\n", __FUNCTION__); 1477 if (last_vcn > 0) 1478 panic("%s(): last_vcn > 0\n", __FUNCTION__); 1479 if (stop_vcn) 1480 *stop_vcn = 0; 1481 /* Terminator byte. */ 1482 *dst = 0; 1483 return 0; 1484 } 1485 /* Skip to runlist element containing @first_vcn. */ 1486 while (rl->length && first_vcn >= rl[1].vcn) 1487 rl++; 1488 if ((!rl->length && first_vcn > rl->vcn) || first_vcn < rl->vcn) 1489 return EINVAL; 1490 /* 1491 * @dst_max is used for bounds checking in 1492 * ntfs_write_significant_bytes(). 1493 */ 1494 dst_max = dst + dst_len - 1; 1495 prev_lcn = 0; 1496 /* Do the first partial run if present. */ 1497 if (first_vcn > rl->vcn) { 1498 s64 delta, length = rl->length; 1499 1500 /* We know rl->length != 0 already. */ 1501 if (length < 0 || rl->lcn < LCN_HOLE) 1502 goto err; 1503 /* 1504 * If @last_vcn is given and finishes inside this run, cap the 1505 * run length. 1506 */ 1507 if (last_vcn >= 0 && rl[1].vcn > last_vcn) { 1508 s64 s1 = last_vcn + 1; 1509 if (rl[1].vcn > s1) 1510 length = s1 - rl->vcn; 1511 the_end = TRUE; 1512 } 1513 delta = first_vcn - rl->vcn; 1514 /* Write length. */ 1515 len_len = ntfs_write_significant_bytes(dst + 1, dst_max, 1516 length - delta); 1517 if (len_len < 0) 1518 goto size_err; 1519 /* 1520 * If the logical cluster number (lcn) denotes a hole and we 1521 * are on NTFS 3.0+, we don't store it at all, i.e. we need 1522 * zero space. On earlier NTFS versions we just write the lcn 1523 * change. FIXME: Do we need to write the lcn change or just 1524 * the lcn in that case? Not sure as I have never seen this 1525 * case on NT4. - We assume that we just need to write the lcn 1526 * change until someone tells us otherwise... (AIA) 1527 */ 1528 if (rl->lcn >= 0 || vol->major_ver < 3) { 1529 prev_lcn = rl->lcn; 1530 if (rl->lcn >= 0) 1531 prev_lcn += delta; 1532 /* Write change in lcn. */ 1533 lcn_len = ntfs_write_significant_bytes(dst + 1 + 1534 len_len, dst_max, prev_lcn); 1535 if (lcn_len < 0) 1536 goto size_err; 1537 } else 1538 lcn_len = 0; 1539 dst_next = dst + len_len + lcn_len + 1; 1540 if (dst_next > dst_max) 1541 goto size_err; 1542 /* Update header byte. */ 1543 *dst = lcn_len << 4 | len_len; 1544 /* Position at next mapping pairs array element. */ 1545 dst = dst_next; 1546 /* Go to next runlist element. */ 1547 rl++; 1548 } 1549 /* Do the full runs. */ 1550 for (; rl->length && !the_end; rl++) { 1551 s64 length = rl->length; 1552 1553 if (length < 0 || rl->lcn < LCN_HOLE) 1554 goto err; 1555 /* 1556 * If @last_vcn is given and finishes inside this run, cap the 1557 * run length. 1558 */ 1559 if (last_vcn >= 0 && rl[1].vcn > last_vcn) { 1560 s64 s1 = last_vcn + 1; 1561 if (rl[1].vcn > s1) 1562 length = s1 - rl->vcn; 1563 the_end = TRUE; 1564 } 1565 /* Write length. */ 1566 len_len = ntfs_write_significant_bytes(dst + 1, dst_max, 1567 length); 1568 if (len_len < 0) 1569 goto size_err; 1570 /* 1571 * If the logical cluster number (lcn) denotes a hole and we 1572 * are on NTFS 3.0+, we don't store it at all, i.e. we need 1573 * zero space. On earlier NTFS versions we just write the lcn 1574 * change. FIXME: Do we need to write the lcn change or just 1575 * the lcn in that case? Not sure as I have never seen this 1576 * case on NT4. - We assume that we just need to write the lcn 1577 * change until someone tells us otherwise... (AIA) 1578 */ 1579 if (rl->lcn >= 0 || vol->major_ver < 3) { 1580 /* Write change in lcn. */ 1581 lcn_len = ntfs_write_significant_bytes(dst + 1 + 1582 len_len, dst_max, rl->lcn - prev_lcn); 1583 if (lcn_len < 0) 1584 goto size_err; 1585 prev_lcn = rl->lcn; 1586 } else 1587 lcn_len = 0; 1588 dst_next = dst + len_len + lcn_len + 1; 1589 if (dst_next > dst_max) 1590 goto size_err; 1591 /* Update header byte. */ 1592 *dst = lcn_len << 4 | len_len; 1593 /* Position at next mapping pairs array element. */ 1594 dst = dst_next; 1595 } 1596 /* Success. */ 1597 err = 0; 1598size_err: 1599 /* Set stop vcn. */ 1600 if (stop_vcn) 1601 *stop_vcn = rl->vcn; 1602 /* Add terminator byte. */ 1603 *dst = 0; 1604 return err; 1605err: 1606 if (rl->lcn == LCN_RL_NOT_MAPPED) 1607 err = EINVAL; 1608 else 1609 err = EIO; 1610 return err; 1611} 1612 1613/** 1614 * ntfs_rl_shrink - remove runlist elements from the end of an existing runlist 1615 * @runlist: runlist to shrink 1616 * @new_elements: new number of elements for the runlist 1617 * 1618 * Shrink the number of elements in the array of runlist elements of the 1619 * runlist @runlist making the new number of elements to be @new_elements. 1620 * 1621 * Reallocate the array buffer if that would save memory. If the reallocation 1622 * fails reduce the number of elements anyway as the only side effect is that 1623 * we waste a bit of memory for a while. 1624 * 1625 * This function cannot fail. 1626 * 1627 * Locking: - The caller must have locked the runlist for writing. 1628 * - The runlist is modified. 1629 */ 1630static void ntfs_rl_shrink(ntfs_runlist *runlist, unsigned new_elements) 1631{ 1632 unsigned alloc, new_alloc; 1633 1634 if (new_elements > runlist->elements) 1635 panic("%s(): new_elements > runlist->elements\n", 1636 __FUNCTION__); 1637 alloc = runlist->alloc; 1638 if (!alloc || !runlist->rl) 1639 panic("%s(): !alloc || !runlist->rl\n", __FUNCTION__); 1640 new_alloc = (new_elements * sizeof(ntfs_rl_element) + 1641 NTFS_ALLOC_BLOCK - 1) & ~(NTFS_ALLOC_BLOCK - 1); 1642 if (new_alloc < alloc) { 1643 ntfs_rl_element *new_rl; 1644 1645 new_rl = OSMalloc(new_alloc, ntfs_malloc_tag); 1646 if (new_rl) { 1647 ntfs_rl_copy(new_rl, runlist->rl, new_elements); 1648 OSFree(runlist->rl, alloc, ntfs_malloc_tag); 1649 runlist->rl = new_rl; 1650 runlist->alloc = new_alloc; 1651 } else 1652 ntfs_debug("Failed to shrink runlist buffer. This " 1653 "just wastes a bit of memory " 1654 "temporarily so we ignore it."); 1655 } else if (new_alloc != alloc) 1656 panic("%s(): new_alloc != alloc\n", __FUNCTION__); 1657 runlist->elements = new_elements; 1658} 1659 1660/** 1661 * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn 1662 * @vol: ntfs volume (needed for error output) 1663 * @runlist: runlist to truncate 1664 * @new_length: the new length of the runlist in VCNs 1665 * 1666 * Truncate the runlist described by @runlist as well as the memory buffer 1667 * holding the runlist elements to a length of @new_length VCNs. 1668 * 1669 * If @new_length lies within the runlist, the runlist elements with VCNs of 1670 * @new_length and above are discarded. As a special case if @new_length is 1671 * zero, the runlist is discarded and set to NULL. 1672 * 1673 * If @new_length lies beyond the runlist, a sparse runlist element is added to 1674 * the end of the runlist @runlist or if the last runlist element is a sparse 1675 * one already, this is extended. 1676 * 1677 * Note, no checking is done for unmapped runlist elements. It is assumed that 1678 * the caller has mapped any elements that need to be mapped already. 1679 * 1680 * Return 0 on success and errno on error. 1681 * 1682 * Locking: The caller must hold @runlist->lock for writing. 1683 */ 1684errno_t ntfs_rl_truncate_nolock(const ntfs_volume *vol, 1685 ntfs_runlist *const runlist, const s64 new_length) 1686{ 1687 ntfs_rl_element *rl; 1688 unsigned last_element, element; 1689 1690 ntfs_debug("Entering for new_length 0x%llx.", 1691 (unsigned long long)new_length); 1692 if (!runlist) 1693 panic("%s(): !runlist\n", __FUNCTION__); 1694 rl = runlist->rl; 1695 if (!rl && runlist->alloc) 1696 panic("%s(): !rl && runlist->alloc\n", __FUNCTION__); 1697 if (rl && !runlist->alloc) 1698 panic("%s(): rl && !runlist->alloc\n", __FUNCTION__); 1699 if (new_length < 0) 1700 panic("%s(): new_length < 0\n", __FUNCTION__); 1701 ntfs_debug_runlist_dump(runlist); 1702 if (!new_length) { 1703 ntfs_debug("Freeing runlist."); 1704 if (rl) { 1705 OSFree(rl, runlist->alloc, ntfs_malloc_tag); 1706 runlist->rl = NULL; 1707 runlist->alloc = runlist->elements = 0; 1708 } 1709 return 0; 1710 } 1711 if (!runlist->elements) { 1712 errno_t err; 1713 1714 /* 1715 * Create a runlist consisting of a sparse runlist element of 1716 * length @new_length followed by a terminator runlist element. 1717 */ 1718 err = ntfs_rl_inc(runlist, 2); 1719 if (err) { 1720 ntfs_error(vol->mp, "Not enough memory to allocate " 1721 "runlist element buffer."); 1722 return err; 1723 } 1724 rl = runlist->rl; 1725 rl[1].length = rl->vcn = 0; 1726 rl->lcn = LCN_HOLE; 1727 rl[1].vcn = rl->length = new_length; 1728 rl[1].lcn = LCN_ENOENT; 1729 goto done; 1730 } 1731 if (new_length < rl->vcn) 1732 panic("%s(): new_length < rl->vcn\n", __FUNCTION__); 1733 /* Find @new_length in the runlist. */ 1734 last_element = runlist->elements - 1; 1735 for (element = 0; element < last_element && 1736 new_length >= rl[element + 1].vcn; element++) 1737 ; 1738 /* 1739 * If not at the end of the runlist we need to shrink it. Otherwise we 1740 * need to expand it. 1741 */ 1742 if (element < last_element) { 1743 ntfs_debug("Shrinking runlist."); 1744 /* Truncate the run. */ 1745 rl[element].length = new_length - rl[element].vcn; 1746 /* 1747 * If a run was partially truncated, make the following runlist 1748 * element a terminator. 1749 */ 1750 if (rl[element].length) { 1751 element++; 1752 rl[element].vcn = new_length; 1753 rl[element].length = 0; 1754 } 1755 rl[element].lcn = LCN_ENOENT; 1756 /* Shrink the number of runlist elements. */ 1757 ntfs_rl_shrink(runlist, element + 1); 1758 } else /* if (element == last_element) */ { 1759 if (rl[element].length) 1760 panic("%s(): rl[element].length\n", __FUNCTION__); 1761 /* 1762 * If the runlist length is already @new_length, there is 1763 * nothing to do except to set the terminator to be LCN_ENOENT. 1764 * Otherwise need to expand the runlist. 1765 */ 1766 if (new_length > rl[element].vcn) { 1767 unsigned prev_element; 1768 1769 ntfs_debug("Expanding runlist."); 1770 /* 1771 * If there is a previous runlist element and it is a 1772 * sparse one, extend it. Otherwise need to add a new, 1773 * sparse runlist element. 1774 */ 1775 if (element > 0 && (prev_element = element - 1, 1776 rl[prev_element].lcn == LCN_HOLE)) 1777 rl[prev_element].length = new_length - 1778 rl[prev_element].vcn; 1779 else { 1780 errno_t err; 1781 1782 /* Add one runlist element to the runlist. */ 1783 err = ntfs_rl_inc(runlist, 1); 1784 if (err) { 1785 ntfs_error(vol->mp, "Not enough " 1786 "memory to expand " 1787 "runlist element " 1788 "buffer."); 1789 return err; 1790 } 1791 rl = runlist->rl; 1792 /* 1793 * Switch the old terminator runlist element to 1794 * a sparse runlist element and adjust its 1795 * length. 1796 */ 1797 rl[element].lcn = LCN_HOLE; 1798 rl[element].length = new_length - 1799 rl[element].vcn; 1800 /* Add a new terminator runlist element. */ 1801 element++; 1802 rl[element].length = 0; 1803 } 1804 rl[element].vcn = new_length; 1805 } 1806 rl[element].lcn = LCN_ENOENT; 1807 } 1808done: 1809 ntfs_debug_runlist_dump(runlist); 1810 ntfs_debug("Done."); 1811 return 0; 1812} 1813 1814/** 1815 * ntfs_rl_punch_nolock - punch a hole into a runlist 1816 * @vol: ntfs volume (needed for error output) 1817 * @runlist: runlist to punch a hole into 1818 * @start_vcn: vcn in the runlist @runlist at which to start the hole 1819 * @len: size of the hole to be created in units of clusters 1820 * 1821 * Punch a hole into the runlist @runlist starting at VCN @start_vcn and of 1822 * size @len clusters. 1823 * 1824 * Return 0 on success and errno on error, in which case @runlist has not been 1825 * modified. 1826 * 1827 * If @start_vcn and/or @start_vcn + @len are outside the runlist return error 1828 * ENOENT. 1829 * 1830 * If the runlist contains unmapped or error elements between @start_vcn and 1831 * @start_vcn + @len return error EINVAL. 1832 * 1833 * Locking: The caller must hold @runlist->lock for writing. 1834 */ 1835errno_t ntfs_rl_punch_nolock(const ntfs_volume *vol, ntfs_runlist *runlist, 1836 const VCN start_vcn, const s64 len) 1837{ 1838 const VCN end_vcn = start_vcn + len; 1839 s64 delta; 1840 ntfs_rl_element *rl, *rl_end, *trl; 1841 unsigned hole_size; 1842 errno_t err; 1843 BOOL lcn_fixup = FALSE; 1844 1845 ntfs_debug("Entering for start_vcn 0x%llx, len 0x%llx.", 1846 (unsigned long long)start_vcn, (unsigned long long)len); 1847 if (!runlist || start_vcn < 0 || len < 0 || end_vcn < 0) 1848 panic("%s(): !runlist || start_vcn < 0 || len < 0 || " 1849 "end_vcn < 0\n", __FUNCTION__); 1850 if (!runlist->elements) { 1851 if (!start_vcn && !len) 1852 return 0; 1853 return ENOENT; 1854 } 1855 rl = runlist->rl; 1856 if (!runlist->alloc || !rl) 1857 panic("%s(): !runlist->alloc || !rl\n", __FUNCTION__); 1858 /* Find @start_vcn in the runlist. */ 1859 while (rl->length && start_vcn >= rl[1].vcn) 1860 rl++; 1861 rl_end = rl; 1862 /* Find @end_vcn in the runlist. */ 1863 hole_size = 0; 1864 while (rl_end->length && end_vcn >= rl_end[1].vcn) { 1865 /* Verify there are no unmapped or error elements. */ 1866 if (rl_end->lcn < LCN_HOLE) 1867 return EINVAL; 1868 rl_end++; 1869 hole_size++; 1870 } 1871 /* Check the last element. */ 1872 if (rl_end->length && rl_end->lcn < LCN_HOLE) 1873 return EINVAL; 1874 /* This covers @start_vcn being out of bounds, too. */ 1875 if (!rl_end->length && end_vcn > rl_end->vcn) 1876 return ENOENT; 1877 if (!len) 1878 return 0; 1879 if (!rl->length) 1880 return ENOENT; 1881 /* If @start is in a hole simply extend the hole. */ 1882 if (rl->lcn == LCN_HOLE) { 1883 /* 1884 * If both @start_vcn and @end_vcn are in the same sparse run, 1885 * we are done. 1886 */ 1887 if (end_vcn <= rl[1].vcn) { 1888 ntfs_debug("Done (requested hole is already sparse)."); 1889 return 0; 1890 } 1891extend_hole: 1892 /* Extend the hole. */ 1893 rl->length = end_vcn - rl->vcn; 1894 /* If @end_vcn is in a hole, merge it with the current one. */ 1895 if (rl_end->lcn == LCN_HOLE) { 1896 rl_end++; 1897 hole_size++; 1898 rl->length = rl_end->vcn - rl->vcn; 1899 } 1900 /* We have done the hole. Now deal with the remaining tail. */ 1901 rl++; 1902 hole_size--; 1903 /* Cut out all runlist elements up to @end. */ 1904 if (rl < rl_end) 1905 memmove(rl, rl_end, (u8*)&runlist->rl[ 1906 runlist->elements] - (u8*)rl_end); 1907 /* Adjust the beginning of the tail if necessary. */ 1908 if (end_vcn > rl->vcn) { 1909 delta = end_vcn - rl->vcn; 1910 rl->vcn = end_vcn; 1911 rl->length -= delta; 1912 /* Only adjust the lcn if it is real. */ 1913 if (rl->lcn >= 0) 1914 rl->lcn += delta; 1915 } 1916shrink_allocation: 1917 /* Reallocate memory if the allocation changed. */ 1918 if (rl < rl_end) 1919 ntfs_rl_shrink(runlist, runlist->elements - hole_size); 1920 ntfs_debug("Done (extend hole)."); 1921 return 0; 1922 } 1923 /* 1924 * If @start_vcn is at the beginning of a run things are easier as 1925 * there is no need to split the first run. 1926 */ 1927 if (start_vcn == rl->vcn) { 1928 /* 1929 * @start_vcn is at the beginning of a run. 1930 * 1931 * If the previous run is sparse, extend its hole. 1932 * 1933 * If @end_vcn is not in the same run, switch the run to be 1934 * sparse and extend the newly created hole. 1935 * 1936 * Thus both of these cases reduce the problem to the above 1937 * case of "@start_vcn is in a hole". 1938 */ 1939 if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) { 1940 rl--; 1941 hole_size++; 1942 goto extend_hole; 1943 } 1944 if (end_vcn >= rl[1].vcn) { 1945 rl->lcn = LCN_HOLE; 1946 goto extend_hole; 1947 } 1948 /* 1949 * The final case is when @end_vcn is in the same run as 1950 * @start_vcn. For this need to split the run into two. One 1951 * run for the sparse region between the beginning of the old 1952 * run, i.e. @start_vcn, and @end_vcn and one for the remaining 1953 * non-sparse region, i.e. between @end_vcn and the end of the 1954 * old run. 1955 */ 1956 trl = runlist->rl; 1957 err = ntfs_rl_inc(runlist, 1); 1958 if (err) 1959 goto err; 1960 /* 1961 * If the runlist buffer was reallocated need to update our 1962 * pointers. 1963 */ 1964 if (runlist->rl != trl) 1965 rl = (ntfs_rl_element*)((u8*)runlist->rl + 1966 ((u8*)rl - (u8*)trl)); 1967split_end: 1968 /* Shift all the runs up by one. */ 1969 memmove((u8*)rl + sizeof(*rl), rl, (u8*)&runlist->rl[ 1970 runlist->elements - 1] - (u8*)rl); 1971 /* Finally, setup the two split runs. */ 1972 rl->lcn = LCN_HOLE; 1973 rl->length = len; 1974 rl++; 1975 rl->vcn += len; 1976 /* Only adjust the lcn if it is real. */ 1977 if (rl->lcn >= 0 || lcn_fixup) 1978 rl->lcn += len; 1979 rl->length -= len; 1980 ntfs_debug("Done (split one)."); 1981 return 0; 1982 } 1983 /* 1984 * @start_vcn is neither in a hole nor at the beginning of a run. 1985 * 1986 * If @end_vcn is in a hole, things are easier as simply truncating the 1987 * run @start_vcn is in to end at @start_vcn - 1, deleting all runs 1988 * after that up to @end_vcn, and finally extending the beginning of 1989 * the run @end_vcn is in to be @start_vcn is all that is needed. 1990 */ 1991 if (rl_end->lcn == LCN_HOLE) { 1992 /* Truncate the run containing @start. */ 1993 rl->length = start_vcn - rl->vcn; 1994 rl++; 1995 hole_size--; 1996 /* Cut out all runlist elements up to @end. */ 1997 if (rl < rl_end) 1998 memmove(rl, rl_end, (u8*)&runlist->rl[ 1999 runlist->elements] - (u8*)rl_end); 2000 /* Extend the beginning of the run @end is in to be @start. */ 2001 rl->vcn = start_vcn; 2002 rl->length = rl[1].vcn - start_vcn; 2003 goto shrink_allocation; 2004 } 2005 /* 2006 * If @end_vcn is not in a hole there are still two cases to 2007 * distinguish. Either @end_vcn is or is not in the same run as 2008 * @start_vcn. 2009 * 2010 * The second case is easier as it can be reduced to an already solved 2011 * problem by truncating the run @start_vcn is in to end at @start_vcn 2012 * - 1. Then, if @end_vcn is in the next run need to split the run 2013 * into a sparse run followed by a non-sparse run which we already 2014 * covered above and if @end_vcn is not in the next run switching it to 2015 * be sparse reduces the problem to the case of "@start_vcn is in a 2016 * hole" which we also covered above. 2017 */ 2018 if (end_vcn >= rl[1].vcn) { 2019 /* 2020 * If @end_vcn is not in the next run, reduce the problem to 2021 * the case of "@start_vcn is in a hole". 2022 */ 2023 if (rl[1].length && end_vcn >= rl[2].vcn) { 2024 /* Truncate the run containing @start_vcn. */ 2025 rl->length = start_vcn - rl->vcn; 2026 rl++; 2027 hole_size--; 2028 rl->vcn = start_vcn; 2029 rl->lcn = LCN_HOLE; 2030 goto extend_hole; 2031 } 2032 trl = runlist->rl; 2033 err = ntfs_rl_inc(runlist, 1); 2034 if (err) 2035 goto err; 2036 /* 2037 * If the runlist buffer was reallocated need to update our 2038 * pointers. 2039 */ 2040 if (runlist->rl != trl) 2041 rl = (ntfs_rl_element*)((u8*)runlist->rl + 2042 ((u8*)rl - (u8*)trl)); 2043 /* Truncate the run containing @start_vcn. */ 2044 rl->length = start_vcn - rl->vcn; 2045 rl++; 2046 /* 2047 * @end_vcn is in the next run, reduce the problem to the case 2048 * where "@start_vcn is at the beginning of a run and @end_vcn 2049 * is in the same run as @start_vcn". 2050 */ 2051 delta = rl->vcn - start_vcn; 2052 rl->vcn = start_vcn; 2053 if (rl->lcn >= 0) { 2054 rl->lcn -= delta; 2055 /* Need this in case the lcn just became negative. */ 2056 lcn_fixup = TRUE; 2057 } 2058 rl->length += delta; 2059 goto split_end; 2060 } 2061 /* 2062 * The first case from above, i.e. @end_vcn is in the same non-sparse 2063 * run as @start_vcn. We need to split the run into three. One run 2064 * for the non-sparse region between the beginning of the old run and 2065 * @start_vcn, one for the sparse region between @start_vcn and 2066 * @end_vcn, and one for the remaining non-sparse region, i.e. between 2067 * @end_vcn and the end of the old run. 2068 */ 2069 trl = runlist->rl; 2070 err = ntfs_rl_inc(runlist, 2); 2071 if (err) 2072 goto err; 2073 /* If the runlist buffer was reallocated need to update our pointers. */ 2074 if (runlist->rl != trl) 2075 rl = (ntfs_rl_element*)((u8*)runlist->rl + 2076 ((u8*)rl - (u8*)trl)); 2077 /* Shift all the runs up by two. */ 2078 memmove((u8*)rl + 2 * sizeof(*rl), rl, 2079 (u8*)&runlist->rl[runlist->elements - 2] - (u8*)rl); 2080 /* Finally, setup the three split runs. */ 2081 rl->length = start_vcn - rl->vcn; 2082 rl++; 2083 rl->vcn = start_vcn; 2084 rl->lcn = LCN_HOLE; 2085 rl->length = len; 2086 rl++; 2087 delta = end_vcn - rl->vcn; 2088 rl->vcn = end_vcn; 2089 rl->lcn += delta; 2090 rl->length -= delta; 2091 ntfs_debug("Done (split both)."); 2092 return 0; 2093err: 2094 ntfs_error(vol->mp, "Failed to extend runlist buffer (error %d).", err); 2095 return err; 2096} 2097 2098/** 2099 * ntfs_rl_read - load data described by an runlist from disk 2100 * @vol: ntfs volume from which to read 2101 * @runlist: runlist describing vcn to lcn mapping of data 2102 * @dst: destination buffer 2103 * @size: size of the destination buffer in bytes 2104 * @initialized_size: initialized size of the data in the runlist 2105 * 2106 * Walk the runlist @runlist and load all clusters from it copying them into 2107 * the linear buffer @dst. The maximum number of bytes copied to @dst is @size 2108 * bytes. Note, @size does not need to be a multiple of the cluster size. If 2109 * @initialized_size is less than @size, the region in @dst between 2110 * @initialized_size and @size will be zeroed (and in fact not read at all). 2111 * 2112 * Return 0 on success or errno on error. 2113 * 2114 * Note: Sparse runlists are not supported as this function is only used to 2115 * load the attribute list attribute value which may not be sparse. 2116 * 2117 * Locking: The caller must have locked the runlist or otherwise ensure that no 2118 * one is modifying the runlist under whilst ntfs_rl_read() is 2119 * executing. 2120 */ 2121errno_t ntfs_rl_read(ntfs_volume *vol, ntfs_runlist *runlist, u8 *dst, 2122 const s64 size, const s64 initialized_size) 2123{ 2124 u8 *dst_end = dst + initialized_size; 2125 ntfs_rl_element *rl; 2126 vnode_t dev_vn = vol->dev_vn; 2127 buf_t buf; 2128 errno_t err; 2129 unsigned block_size = vol->sector_size; 2130 const u8 cluster_to_block_shift = vol->cluster_size_shift - 2131 vol->sector_size_shift; 2132 2133 ntfs_debug("Entering."); 2134 if (!vol || !runlist || !dst || size <= 0 || initialized_size < 0 || 2135 initialized_size > size) { 2136 ntfs_error(vol->mp, "Received invalid arguments."); 2137 return EINVAL; 2138 } 2139 if (!initialized_size) { 2140 bzero(dst, size); 2141 ntfs_debug("Done (!initialized_size)."); 2142 return 0; 2143 } 2144 rl = runlist->rl; 2145 if (!rl) { 2146 ntfs_error(vol->mp, "Cannot read attribute list since runlist " 2147 "is missing."); 2148 return EIO; 2149 } 2150 /* Read all clusters specified by the runlist one run at a time. */ 2151 while (rl->length) { 2152 daddr64_t block, max_block; 2153 2154 ntfs_debug("Reading vcn 0x%llx, lcn 0x%llx, length 0x%llx.", 2155 (unsigned long long)rl->vcn, 2156 (unsigned long long)rl->lcn, 2157 (unsigned long long)rl->length); 2158 /* The runlist may not be sparse. */ 2159 if (rl->lcn < 0) { 2160 ntfs_error(vol->mp, "Runlist is invalid, not mapped, " 2161 "or sparse. Cannot read data."); 2162 return EIO; 2163 } 2164 /* Read the run from device in chunks of block_size bytes. */ 2165 block = rl->lcn << cluster_to_block_shift; 2166 max_block = block + (rl->length << cluster_to_block_shift); 2167 ntfs_debug("max_block 0x%llx.", (unsigned long long)max_block); 2168 do { 2169 u8 *src; 2170 2171 ntfs_debug("Reading block 0x%llx.", 2172 (unsigned long long)block); 2173 err = buf_meta_bread(dev_vn, block, block_size, NOCRED, 2174 &buf); 2175 if (err) { 2176 ntfs_error(vol->mp, "buf_meta_bread() failed " 2177 "(error %d). Cannot read " 2178 "data.", (int)err); 2179 goto err; 2180 } 2181 err = buf_map(buf, (caddr_t*)&src); 2182 if (err) { 2183 ntfs_error(vol->mp, "buf_map() failed (error " 2184 "%d). Cannot read data.", 2185 (int)err); 2186 goto err; 2187 } 2188 /* Copy the data into the buffer. */ 2189 if (dst + block_size > dst_end) 2190 block_size = dst_end - dst; 2191 memcpy(dst, src, block_size); 2192 err = buf_unmap(buf); 2193 if (err) 2194 ntfs_error(vol->mp, "buf_unmap() failed " 2195 "(error %d).", (int)err); 2196 buf_brelse(buf); 2197 dst += block_size; 2198 if (dst >= dst_end) 2199 goto done; 2200 } while (++block < max_block); 2201 rl++; 2202 } 2203done: 2204 /* If the runlist was too short, zero out the unread part. */ 2205 if (dst < dst_end) 2206 bzero(dst, dst_end - dst); 2207 /* Zero the uninitialized region if present. */ 2208 if (initialized_size < size) 2209 bzero(dst_end, size - initialized_size); 2210 ntfs_debug("Done."); 2211 return 0; 2212err: 2213 buf_brelse(buf); 2214 return err; 2215} 2216 2217/** 2218 * ntfs_rl_write - write data to disk as described by an runlist 2219 * @vol: ntfs volume to which to write 2220 * @src: source buffer 2221 * @size: size of source buffer @src in bytes 2222 * @runlist: runlist describing vcn to lcn mapping of data 2223 * @ofs: offset into buffer/runlist at which to start writing 2224 * @cnt: number of bytes to write starting at @ofs or zero 2225 * 2226 * Walk the runlist @runlist and write the data contained in @src starting at 2227 * offset @ofs into @src to the corresponding clusters as specified by the 2228 * runlist starting at offset @ofs into the runlist. If @cnt is not zero it is 2229 * the number of bytes to write starting at @ofs. If @cnt is zero we write 2230 * until the end of the source buffer @src is reached. 2231 * 2232 * Note @ofs will be aligned to a device block boundary and @cnt will be 2233 * adjusted accordingly and it will be rounded up to the next device block 2234 * boundary and anything outside @size will be written as zeroes. 2235 * 2236 * Return 0 on success and errno on error. 2237 * 2238 * Note: Sparse runlists are not supported by this function. 2239 * 2240 * Locking: The caller must have locked the runlist or otherwise ensure that no 2241 * one is modifying the runlist under whilst ntfs_rl_write() is 2242 * executing. 2243 */ 2244errno_t ntfs_rl_write(ntfs_volume *vol, u8 *src, const s64 size, 2245 ntfs_runlist *runlist, s64 ofs, const s64 cnt) 2246{ 2247 VCN vcn; 2248 u8 *src_end, *src_stop; 2249 ntfs_rl_element *rl; 2250 vnode_t dev_vn = vol->dev_vn; 2251 errno_t err; 2252 unsigned block_size, block_shift, cluster_shift, shift, delta, vcn_ofs; 2253 2254 ntfs_debug("Entering for size 0x%llx, ofs 0x%llx.", 2255 (unsigned long long)size, (unsigned long long)ofs); 2256 if (!vol || !src || size <= 0 || !runlist || !runlist->elements || 2257 ofs < 0 || cnt < 0 || ofs + cnt > size) { 2258 ntfs_error(vol->mp, "Received invalid arguments."); 2259 return EINVAL; 2260 } 2261 src_stop = src_end = src + size; 2262 if (cnt) { 2263 src_stop = src + ofs + cnt; 2264 if (src_stop > src_end) 2265 panic("%s(): src_stop > src_end\n", __FUNCTION__); 2266 } 2267 block_size = vol->sector_size; 2268 block_shift = vol->sector_size_shift; 2269 cluster_shift = vol->cluster_size_shift; 2270 shift = cluster_shift - block_shift; 2271 /* 2272 * Align the start offset to contain a whole buffer. This makes things 2273 * simpler. 2274 */ 2275 delta = ofs & vol->sector_size_mask; 2276 ofs -= delta; 2277 src += ofs; 2278 rl = runlist->rl; 2279 /* Skip to the start offset @ofs in the runlist. */ 2280 vcn = ofs >> cluster_shift; 2281 vcn_ofs = ofs & vol->cluster_size_mask; 2282 rl = ntfs_rl_find_vcn_nolock(rl, vcn); 2283 if (!rl || !rl->length) 2284 panic("%s(): !rl || !rl->length\n", __FUNCTION__); 2285 /* Write the clusters specified by the runlist one at a time. */ 2286 do { 2287 LCN lcn; 2288 daddr64_t block, end_block; 2289 2290 lcn = ntfs_rl_vcn_to_lcn(rl, vcn, NULL); 2291 if (lcn < 0) 2292 panic("%s(): lcn < 0\n", __FUNCTION__); 2293 ntfs_debug("Writing vcn 0x%llx, start offset 0x%x, lcn " 2294 "0x%llx.", (unsigned long long)vcn, vcn_ofs, 2295 (unsigned long long)lcn); 2296 /* Write to the device in chunks of sectors. */ 2297 block = ((lcn << cluster_shift) + vcn_ofs) >> block_shift; 2298 end_block = (lcn + 1) << shift; 2299 ntfs_debug("end_block 0x%llx.", (unsigned long long)end_block); 2300 do { 2301 buf_t buf; 2302 u8 *dst; 2303 2304 ntfs_debug("Writing block 0x%llx.", 2305 (unsigned long long)block); 2306 /* Obtain the buffer, possibly not uptodate. */ 2307 buf = buf_getblk(dev_vn, block, block_size, 0, 0, 2308 BLK_META); 2309 if (!buf) 2310 panic("%s(): !buf\n", __FUNCTION__); 2311 err = buf_map(buf, (caddr_t*)&dst); 2312 if (err) { 2313 ntfs_error(vol->mp, "buf_map() failed (error " 2314 "%d).", err); 2315 buf_brelse(buf); 2316 goto err; 2317 } 2318 /* 2319 * Zero the area outside the size of the attribute list 2320 * attribute in the final partial buffer. 2321 */ 2322 if (src + block_size > src_end) { 2323 delta = src_end - src; 2324 bzero(dst + delta, block_size - delta); 2325 block_size = delta; 2326 } 2327 /* 2328 * Copy the modified data into the buffer and write it 2329 * synchronously. 2330 */ 2331 memcpy(dst, src, block_size); 2332 err = buf_unmap(buf); 2333 if (err) 2334 ntfs_error(vol->mp, "buf_unmap() failed " 2335 "(error %d).", err); 2336 err = buf_bwrite(buf); 2337 if (err) { 2338 ntfs_error(vol->mp, "buf_bwrite() failed " 2339 "(error %d).", err); 2340 goto err; 2341 } 2342 src += block_size; 2343 if (src >= src_stop) 2344 goto done; 2345 } while (++block < end_block); 2346 if (++vcn >= rl[1].vcn) { 2347 rl++; 2348 if (!rl->length) 2349 break; 2350 } 2351 vcn_ofs = 0; 2352 } while (1); 2353done: 2354 ntfs_debug("Done."); 2355 return 0; 2356err: 2357 ntfs_error(vol->mp, "Failed to update attribute list attribute on " 2358 "disk due to i/o error on buffer write. Leaving " 2359 "inconsistent metadata. Run chkdsk."); 2360 NVolSetErrors(vol); 2361 return EIO; 2362} 2363 2364/** 2365 * ntfs_rl_set - fill data on disk as described by an runlist with a value 2366 * @vol: ntfs volume to which to write 2367 * @rl: runlist describing clusters to fill with value 2368 * @val: value to fill each byte in the clusters with 2369 * 2370 * Walk the runlist elements in at @rl and fill all bytes in all clusters @rl 2371 * describes with the value @val. 2372 * 2373 * Return 0 on success and errno on error. 2374 * 2375 * Note: This function will simply skip unmapped and sparse runs thus you need 2376 * to make sure that all wanted runs are mapped. 2377 * 2378 * Locking: - The caller must have locked the runlist for writing. 2379 * - The runlist is not modified. 2380 */ 2381errno_t ntfs_rl_set(ntfs_volume *vol, const ntfs_rl_element *rl, const u8 val) 2382{ 2383 VCN vcn; 2384 vnode_t dev_vn = vol->dev_vn; 2385 errno_t err; 2386 unsigned block_size, shift; 2387 2388 ntfs_debug("Entering (val 0x%x).", (unsigned)val); 2389 if (!vol || !rl || !rl->length) { 2390 ntfs_error(vol->mp, "Received invalid arguments."); 2391 return EINVAL; 2392 } 2393 block_size = vol->sector_size; 2394 shift = vol->cluster_size_shift - vol->sector_size_shift; 2395 /* Write the clusters specified by the runlist one at a time. */ 2396 do { 2397 LCN lcn; 2398 daddr64_t block, end_block; 2399 2400 vcn = rl->vcn; 2401 if (vcn < 0) 2402 panic("%s(): vcn < 0\n", __FUNCTION__); 2403 lcn = rl->lcn; 2404 if (lcn < 0) { 2405 if (lcn == LCN_HOLE || lcn == LCN_RL_NOT_MAPPED) 2406 continue; 2407 ntfs_error(vol->mp, "Invalid LCN (%lld) in runlist.", 2408 (long long)lcn); 2409 return EIO; 2410 } 2411 /* Write to the device in chunks of sectors. */ 2412 block = lcn << shift; 2413 end_block = (lcn + rl->length) << shift; 2414 ntfs_debug("end_block 0x%llx.", (unsigned long long)end_block); 2415 do { 2416 buf_t buf; 2417 u8 *dst; 2418 2419 ntfs_debug("Setting block 0x%llx.", 2420 (unsigned long long)block); 2421 /* Obtain the buffer, possibly not uptodate. */ 2422 buf = buf_getblk(dev_vn, block, block_size, 0, 0, 2423 BLK_META); 2424 if (!buf) 2425 panic("%s(): !buf\n", __FUNCTION__); 2426 err = buf_map(buf, (caddr_t*)&dst); 2427 if (err) { 2428 ntfs_error(vol->mp, "buf_map() failed (error " 2429 "%d).", err); 2430 buf_brelse(buf); 2431 return err; 2432 } 2433 /* 2434 * Set the bytes in the buffer to @val and write it 2435 * synchronously. 2436 */ 2437 memset(dst, val, block_size); 2438 err = buf_unmap(buf); 2439 if (err) 2440 ntfs_error(vol->mp, "buf_unmap() failed " 2441 "(error %d).", err); 2442 err = buf_bwrite(buf); 2443 if (err) { 2444 ntfs_error(vol->mp, "buf_bwrite() failed " 2445 "(error %d).", err); 2446 return err; 2447 } 2448 } while (++block < end_block); 2449 } while ((++rl)->length); 2450 ntfs_debug("Done."); 2451 return 0; 2452} 2453 2454/** 2455 * ntfs_rl_get_nr_real_clusters - determine number of real clusters in a runlist 2456 * @runlist: runlist for which to determine the number of real clusters 2457 * @start_vcn: vcn at which to start counting the real clusters 2458 * @cnt: number of clusters to scan starting at @start_vcn 2459 * 2460 * Find the virtual cluster number @start_vcn in the runlist @runlist and add 2461 * up the number of real clusters in the range @start_vcn to @start_vcn + @cnt. 2462 * 2463 * If @cnt is -1 it is taken to mean the end of the runlist. 2464 * 2465 * Return the numbero f real clusters in the range. 2466 * 2467 * Locking: The runlist must be locked on entry. 2468 */ 2469s64 ntfs_rl_get_nr_real_clusters(ntfs_runlist *runlist, const VCN start_vcn, 2470 const s64 cnt) 2471{ 2472 VCN end_vcn; 2473 s64 nr_real_clusters; 2474 ntfs_rl_element *rl; 2475 2476 if (!runlist || start_vcn < 0 || cnt < 0) 2477 panic("%s(): !runlist || start_vcn < 0 || cnt < 0\n", 2478 __FUNCTION__); 2479 nr_real_clusters = 0; 2480 if (!runlist->elements || !cnt) 2481 goto done; 2482 end_vcn = -1; 2483 if (cnt >= 0) 2484 end_vcn = start_vcn + cnt; 2485 rl = runlist->rl; 2486 if (start_vcn > 0) 2487 rl = ntfs_rl_find_vcn_nolock(rl, start_vcn); 2488 if (!rl || !rl->length) 2489 goto done; 2490 if (rl->lcn >= 0) { 2491 s64 delta; 2492 2493 delta = start_vcn - rl->vcn; 2494 nr_real_clusters = rl[1].vcn - delta; 2495 if (nr_real_clusters > cnt) { 2496 nr_real_clusters = cnt; 2497 goto done; 2498 } 2499 } 2500 rl++; 2501 while (rl->length) { 2502 /* 2503 * If this is the last run of interest, deal with it specially 2504 * as it may be partial and then we are done. 2505 */ 2506 if (end_vcn >= 0 && rl[1].vcn >= end_vcn) { 2507 if (rl->lcn >= 0) 2508 nr_real_clusters += end_vcn - rl->vcn; 2509 break; 2510 } 2511 if (rl->lcn >= 0) 2512 nr_real_clusters += rl->length; 2513 rl++; 2514 } 2515done: 2516 ntfs_debug("Done (nr_real_clusters 0x%llx).", nr_real_clusters); 2517 return nr_real_clusters; 2518} 2519