1/** 2 * lcnalloc.c - Cluster (de)allocation code. Originated from the Linux-NTFS project. 3 * 4 * Copyright (c) 2002-2004 Anton Altaparmakov 5 * Copyright (c) 2004 Yura Pakhuchiy 6 * Copyright (c) 2004-2008 Szabolcs Szakacsits 7 * Copyright (c) 2008-2009 Jean-Pierre Andre 8 * 9 * This program/include file is free software; you can redistribute it and/or 10 * modify it under the terms of the GNU General Public License as published 11 * by the Free Software Foundation; either version 2 of the License, or 12 * (at your option) any later version. 13 * 14 * This program/include file is distributed in the hope that it will be 15 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty 16 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 * GNU General Public License for more details. 18 * 19 * You should have received a copy of the GNU General Public License 20 * along with this program (in the main directory of the NTFS-3G 21 * distribution in the file COPYING); if not, write to the Free Software 22 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 23 */ 24 25#ifdef HAVE_CONFIG_H 26#include "config.h" 27#endif 28 29#ifdef HAVE_STDLIB_H 30#include <stdlib.h> 31#endif 32#ifdef HAVE_STDIO_H 33#include <stdio.h> 34#endif 35#ifdef HAVE_ERRNO_H 36#include <errno.h> 37#endif 38 39#include "types.h" 40#include "attrib.h" 41#include "bitmap.h" 42#include "debug.h" 43#include "runlist.h" 44#include "volume.h" 45#include "lcnalloc.h" 46#include "logging.h" 47#include "misc.h" 48 49/* 50 * Plenty possibilities for big optimizations all over in the cluster 51 * allocation, however at the moment the dominant bottleneck (~ 90%) is 52 * the update of the mapping pairs which converges to the cubic Faulhaber's 53 * formula as the function of the number of extents (fragments, runs). 54 */ 55#define NTFS_LCNALLOC_BSIZE 4096 56#define NTFS_LCNALLOC_SKIP NTFS_LCNALLOC_BSIZE 57 58enum { 59 ZONE_MFT = 1, 60 ZONE_DATA1 = 2, 61 ZONE_DATA2 = 4 62} ; 63 64static void ntfs_cluster_set_zone_pos(LCN start, LCN end, LCN *pos, LCN tc) 65{ 66 ntfs_log_trace("pos: %lld tc: %lld\n", (long long)*pos, (long long)tc); 67 68 if (tc >= end) 69 *pos = start; 70 else if (tc >= start) 71 *pos = tc; 72} 73 74static void ntfs_cluster_update_zone_pos(ntfs_volume *vol, u8 zone, LCN tc) 75{ 76 ntfs_log_trace("tc = %lld, zone = %d\n", (long long)tc, zone); 77 78 if (zone == ZONE_MFT) 79 ntfs_cluster_set_zone_pos(vol->mft_lcn, vol->mft_zone_end, 80 &vol->mft_zone_pos, tc); 81 else if (zone == ZONE_DATA1) 82 ntfs_cluster_set_zone_pos(vol->mft_zone_end, vol->nr_clusters, 83 &vol->data1_zone_pos, tc); 84 else /* zone == ZONE_DATA2 */ 85 ntfs_cluster_set_zone_pos(0, vol->mft_zone_start, 86 &vol->data2_zone_pos, tc); 87} 88 89/* 90 * Unmark full zones when a cluster has been freed in a full zone 91 * 92 * Next allocation will reuse the freed cluster 93 */ 94 95static void update_full_status(ntfs_volume *vol, LCN lcn) 96{ 97 if (lcn >= vol->mft_zone_end) { 98 if (vol->full_zones & ZONE_DATA1) { 99 ntfs_cluster_update_zone_pos(vol, ZONE_DATA1, lcn); 100 vol->full_zones &= ~ZONE_DATA1; 101 } 102 } else 103 if (lcn < vol->mft_zone_start) { 104 if (vol->full_zones & ZONE_DATA2) { 105 ntfs_cluster_update_zone_pos(vol, ZONE_DATA2, lcn); 106 vol->full_zones &= ~ZONE_DATA2; 107 } 108 } else { 109 if (vol->full_zones & ZONE_MFT) { 110 ntfs_cluster_update_zone_pos(vol, ZONE_MFT, lcn); 111 vol->full_zones &= ~ZONE_MFT; 112 } 113 } 114} 115 116static s64 max_empty_bit_range(unsigned char *buf, int size) 117{ 118 int i, j, run = 0; 119 int max_range = 0; 120 s64 start_pos = -1; 121 122 ntfs_log_trace("Entering\n"); 123 124 i = 0; 125 while (i < size) { 126 switch (*buf) { 127 case 0 : 128 do { 129 buf++; 130 run += 8; 131 i++; 132 } while ((i < size) && !*buf); 133 break; 134 case 255 : 135 if (run > max_range) { 136 max_range = run; 137 start_pos = (s64)i * 8 - run; 138 } 139 run = 0; 140 do { 141 buf++; 142 i++; 143 } while ((i < size) && (*buf == 255)); 144 break; 145 default : 146 for (j = 0; j < 8; j++) { 147 148 int bit = *buf & (1 << j); 149 150 if (bit) { 151 if (run > max_range) { 152 max_range = run; 153 start_pos = (s64)i * 8 + (j - run); 154 } 155 run = 0; 156 } else 157 run++; 158 } 159 i++; 160 buf++; 161 162 } 163 } 164 165 if (run > max_range) 166 start_pos = (s64)i * 8 - run; 167 168 return start_pos; 169} 170 171static int bitmap_writeback(ntfs_volume *vol, s64 pos, s64 size, void *b, 172 u8 *writeback) 173{ 174 s64 written; 175 176 ntfs_log_trace("Entering\n"); 177 178 if (!*writeback) 179 return 0; 180 181 *writeback = 0; 182 183 written = ntfs_attr_pwrite(vol->lcnbmp_na, pos, size, b); 184 if (written != size) { 185 if (!written) 186 errno = EIO; 187 ntfs_log_perror("Bitmap write error (%lld, %lld)", 188 (long long)pos, (long long)size); 189 return -1; 190 } 191 192 return 0; 193} 194 195/** 196 * ntfs_cluster_alloc - allocate clusters on an ntfs volume 197 * @vol: mounted ntfs volume on which to allocate the clusters 198 * @start_vcn: vcn to use for the first allocated cluster 199 * @count: number of clusters to allocate 200 * @start_lcn: starting lcn at which to allocate the clusters (or -1 if none) 201 * @zone: zone from which to allocate the clusters 202 * 203 * Allocate @count clusters preferably starting at cluster @start_lcn or at the 204 * current allocator position if @start_lcn is -1, on the mounted ntfs volume 205 * @vol. @zone is either DATA_ZONE for allocation of normal clusters and 206 * MFT_ZONE for allocation of clusters for the master file table, i.e. the 207 * $MFT/$DATA attribute. 208 * 209 * On success return a runlist describing the allocated cluster(s). 210 * 211 * On error return NULL with errno set to the error code. 212 * 213 * Notes on the allocation algorithm 214 * ================================= 215 * 216 * There are two data zones. First is the area between the end of the mft zone 217 * and the end of the volume, and second is the area between the start of the 218 * volume and the start of the mft zone. On unmodified/standard NTFS 1.x 219 * volumes, the second data zone doesn't exist due to the mft zone being 220 * expanded to cover the start of the volume in order to reserve space for the 221 * mft bitmap attribute. 222 * 223 * The complexity stems from the need of implementing the mft vs data zoned 224 * approach and from the fact that we have access to the lcn bitmap via up to 225 * NTFS_LCNALLOC_BSIZE bytes at a time, so we need to cope with crossing over 226 * boundaries of two buffers. Further, the fact that the allocator allows for 227 * caller supplied hints as to the location of where allocation should begin 228 * and the fact that the allocator keeps track of where in the data zones the 229 * next natural allocation should occur, contribute to the complexity of the 230 * function. But it should all be worthwhile, because this allocator: 231 * 1) implements MFT zone reservation 232 * 2) causes reduction in fragmentation. 233 * The code is not optimized for speed. 234 */ 235runlist *ntfs_cluster_alloc(ntfs_volume *vol, VCN start_vcn, s64 count, 236 LCN start_lcn, const NTFS_CLUSTER_ALLOCATION_ZONES zone) 237{ 238 LCN zone_start, zone_end; /* current search range */ 239 LCN last_read_pos, lcn; 240 LCN bmp_pos; /* current bit position inside the bitmap */ 241 LCN prev_lcn = 0, prev_run_len = 0; 242 s64 clusters, br; 243 runlist *rl = NULL, *trl; 244 u8 *buf, *byte, bit, writeback; 245 u8 pass = 1; /* 1: inside zone; 2: start of zone */ 246 u8 search_zone; /* 4: data2 (start) 1: mft (middle) 2: data1 (end) */ 247 u8 done_zones = 0; 248 u8 has_guess, used_zone_pos; 249 int err = 0, rlpos, rlsize, buf_size; 250 251 ntfs_log_enter("Entering with count = 0x%llx, start_lcn = 0x%llx, " 252 "zone = %s_ZONE.\n", (long long)count, (long long) 253 start_lcn, zone == MFT_ZONE ? "MFT" : "DATA"); 254 255 if (!vol || count < 0 || start_lcn < -1 || !vol->lcnbmp_na || 256 (s8)zone < FIRST_ZONE || zone > LAST_ZONE) { 257 errno = EINVAL; 258 ntfs_log_perror("%s: vcn: %lld, count: %lld, lcn: %lld", 259 __FUNCTION__, (long long)start_vcn, 260 (long long)count, (long long)start_lcn); 261 goto out; 262 } 263 264 /* Return empty runlist if @count == 0 */ 265 if (!count) { 266 rl = ntfs_malloc(0x1000); 267 if (rl) { 268 rl[0].vcn = start_vcn; 269 rl[0].lcn = LCN_RL_NOT_MAPPED; 270 rl[0].length = 0; 271 } 272 goto out; 273 } 274 275 buf = ntfs_malloc(NTFS_LCNALLOC_BSIZE); 276 if (!buf) 277 goto out; 278 /* 279 * If no @start_lcn was requested, use the current zone 280 * position otherwise use the requested @start_lcn. 281 */ 282 has_guess = 1; 283 zone_start = start_lcn; 284 285 if (zone_start < 0) { 286 if (zone == DATA_ZONE) 287 zone_start = vol->data1_zone_pos; 288 else 289 zone_start = vol->mft_zone_pos; 290 has_guess = 0; 291 } 292 293 used_zone_pos = has_guess ? 0 : 1; 294 295 if (!zone_start || zone_start == vol->mft_zone_start || 296 zone_start == vol->mft_zone_end) 297 pass = 2; 298 299 if (zone_start < vol->mft_zone_start) { 300 zone_end = vol->mft_zone_start; 301 search_zone = ZONE_DATA2; 302 } else if (zone_start < vol->mft_zone_end) { 303 zone_end = vol->mft_zone_end; 304 search_zone = ZONE_MFT; 305 } else { 306 zone_end = vol->nr_clusters; 307 search_zone = ZONE_DATA1; 308 } 309 310 bmp_pos = zone_start; 311 312 /* Loop until all clusters are allocated. */ 313 clusters = count; 314 rlpos = rlsize = 0; 315 while (1) { 316 /* check whether we have exhausted the current zone */ 317 if (search_zone & vol->full_zones) 318 goto zone_pass_done; 319 last_read_pos = bmp_pos >> 3; 320 br = ntfs_attr_pread(vol->lcnbmp_na, last_read_pos, 321 NTFS_LCNALLOC_BSIZE, buf); 322 if (br <= 0) { 323 if (!br) 324 goto zone_pass_done; 325 err = errno; 326 ntfs_log_perror("Reading $BITMAP failed"); 327 goto err_ret; 328 } 329 /* 330 * We might have read less than NTFS_LCNALLOC_BSIZE bytes 331 * if we are close to the end of the attribute. 332 */ 333 buf_size = (int)br << 3; 334 lcn = bmp_pos & 7; 335 bmp_pos &= ~7; 336 writeback = 0; 337 338 while (lcn < buf_size) { 339 byte = buf + (lcn >> 3); 340 bit = 1 << (lcn & 7); 341 if (has_guess) { 342 if (*byte & bit) { 343 has_guess = 0; 344 break; 345 } 346 } else { 347 lcn = max_empty_bit_range(buf, br); 348 if (lcn < 0) 349 break; 350 has_guess = 1; 351 continue; 352 } 353 354 /* First free bit is at lcn + bmp_pos. */ 355 356 /* Reallocate memory if necessary. */ 357 if ((rlpos + 2) * (int)sizeof(runlist) >= rlsize) { 358 rlsize += 4096; 359 trl = realloc(rl, rlsize); 360 if (!trl) { 361 err = ENOMEM; 362 ntfs_log_perror("realloc() failed"); 363 goto wb_err_ret; 364 } 365 rl = trl; 366 } 367 368 /* Allocate the bitmap bit. */ 369 *byte |= bit; 370 writeback = 1; 371 if (vol->free_clusters <= 0) 372 ntfs_log_error("Non-positive free clusters " 373 "(%lld)!\n", 374 (long long)vol->free_clusters); 375 else 376 vol->free_clusters--; 377 378 /* 379 * Coalesce with previous run if adjacent LCNs. 380 * Otherwise, append a new run. 381 */ 382 if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) { 383 ntfs_log_debug("Cluster coalesce: prev_lcn: " 384 "%lld lcn: %lld bmp_pos: %lld " 385 "prev_run_len: %lld\n", 386 (long long)prev_lcn, 387 (long long)lcn, (long long)bmp_pos, 388 (long long)prev_run_len); 389 rl[rlpos - 1].length = ++prev_run_len; 390 } else { 391 if (rlpos) 392 rl[rlpos].vcn = rl[rlpos - 1].vcn + 393 prev_run_len; 394 else { 395 rl[rlpos].vcn = start_vcn; 396 ntfs_log_debug("Start_vcn: %lld\n", 397 (long long)start_vcn); 398 } 399 400 rl[rlpos].lcn = prev_lcn = lcn + bmp_pos; 401 rl[rlpos].length = prev_run_len = 1; 402 rlpos++; 403 } 404 405 ntfs_log_debug("RUN: %-16lld %-16lld %-16lld\n", 406 (long long)rl[rlpos - 1].vcn, 407 (long long)rl[rlpos - 1].lcn, 408 (long long)rl[rlpos - 1].length); 409 /* Done? */ 410 if (!--clusters) { 411 if (used_zone_pos) 412 ntfs_cluster_update_zone_pos(vol, 413 search_zone, lcn + bmp_pos + 1 + 414 NTFS_LCNALLOC_SKIP); 415 goto done_ret; 416 } 417 418 lcn++; 419 } 420 421 if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) { 422 err = errno; 423 goto err_ret; 424 } 425 426 if (!used_zone_pos) { 427 428 used_zone_pos = 1; 429 430 if (search_zone == ZONE_MFT) 431 zone_start = vol->mft_zone_pos; 432 else if (search_zone == ZONE_DATA1) 433 zone_start = vol->data1_zone_pos; 434 else 435 zone_start = vol->data2_zone_pos; 436 437 if (!zone_start || zone_start == vol->mft_zone_start || 438 zone_start == vol->mft_zone_end) 439 pass = 2; 440 bmp_pos = zone_start; 441 } else 442 bmp_pos += buf_size; 443 444 if (bmp_pos < zone_end) 445 continue; 446 447zone_pass_done: 448 ntfs_log_trace("Finished current zone pass(%i).\n", pass); 449 if (pass == 1) { 450 pass = 2; 451 zone_end = zone_start; 452 453 if (search_zone == ZONE_MFT) 454 zone_start = vol->mft_zone_start; 455 else if (search_zone == ZONE_DATA1) 456 zone_start = vol->mft_zone_end; 457 else 458 zone_start = 0; 459 460 /* Sanity check. */ 461 if (zone_end < zone_start) 462 zone_end = zone_start; 463 464 bmp_pos = zone_start; 465 466 continue; 467 } 468 /* pass == 2 */ 469done_zones_check: 470 done_zones |= search_zone; 471 vol->full_zones |= search_zone; 472 if (done_zones < (ZONE_MFT + ZONE_DATA1 + ZONE_DATA2)) { 473 ntfs_log_trace("Switching zone.\n"); 474 pass = 1; 475 if (rlpos) { 476 LCN tc = rl[rlpos - 1].lcn + 477 rl[rlpos - 1].length + NTFS_LCNALLOC_SKIP; 478 479 if (used_zone_pos) 480 ntfs_cluster_update_zone_pos(vol, 481 search_zone, tc); 482 } 483 484 switch (search_zone) { 485 case ZONE_MFT: 486 ntfs_log_trace("Zone switch: mft -> data1\n"); 487switch_to_data1_zone: search_zone = ZONE_DATA1; 488 zone_start = vol->data1_zone_pos; 489 zone_end = vol->nr_clusters; 490 if (zone_start == vol->mft_zone_end) 491 pass = 2; 492 break; 493 case ZONE_DATA1: 494 ntfs_log_trace("Zone switch: data1 -> data2\n"); 495 search_zone = ZONE_DATA2; 496 zone_start = vol->data2_zone_pos; 497 zone_end = vol->mft_zone_start; 498 if (!zone_start) 499 pass = 2; 500 break; 501 case ZONE_DATA2: 502 if (!(done_zones & ZONE_DATA1)) { 503 ntfs_log_trace("data2 -> data1\n"); 504 goto switch_to_data1_zone; 505 } 506 ntfs_log_trace("Zone switch: data2 -> mft\n"); 507 search_zone = ZONE_MFT; 508 zone_start = vol->mft_zone_pos; 509 zone_end = vol->mft_zone_end; 510 if (zone_start == vol->mft_zone_start) 511 pass = 2; 512 break; 513 } 514 515 bmp_pos = zone_start; 516 517 if (zone_start == zone_end) { 518 ntfs_log_trace("Empty zone, skipped.\n"); 519 goto done_zones_check; 520 } 521 522 continue; 523 } 524 525 ntfs_log_trace("All zones are finished, no space on device.\n"); 526 err = ENOSPC; 527 goto err_ret; 528 } 529done_ret: 530 ntfs_log_debug("At done_ret.\n"); 531 /* Add runlist terminator element. */ 532 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; 533 rl[rlpos].lcn = LCN_RL_NOT_MAPPED; 534 rl[rlpos].length = 0; 535 if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) { 536 err = errno; 537 goto err_ret; 538 } 539done_err_ret: 540 free(buf); 541 if (err) { 542 errno = err; 543 ntfs_log_perror("Failed to allocate clusters"); 544 rl = NULL; 545 } 546out: 547 ntfs_log_leave("\n"); 548 return rl; 549 550wb_err_ret: 551 ntfs_log_trace("At wb_err_ret.\n"); 552 if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) 553 err = errno; 554err_ret: 555 ntfs_log_trace("At err_ret.\n"); 556 if (rl) { 557 /* Add runlist terminator element. */ 558 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; 559 rl[rlpos].lcn = LCN_RL_NOT_MAPPED; 560 rl[rlpos].length = 0; 561 ntfs_debug_runlist_dump(rl); 562 ntfs_cluster_free_from_rl(vol, rl); 563 free(rl); 564 rl = NULL; 565 } 566 goto done_err_ret; 567} 568 569/** 570 * ntfs_cluster_free_from_rl - free clusters from runlist 571 * @vol: mounted ntfs volume on which to free the clusters 572 * @rl: runlist from which deallocate clusters 573 * 574 * On success return 0 and on error return -1 with errno set to the error code. 575 */ 576int ntfs_cluster_free_from_rl(ntfs_volume *vol, runlist *rl) 577{ 578 s64 nr_freed = 0; 579 int ret = -1; 580 581 ntfs_log_trace("Entering.\n"); 582 583 for (; rl->length; rl++) { 584 585 ntfs_log_trace("Dealloc lcn 0x%llx, len 0x%llx.\n", 586 (long long)rl->lcn, (long long)rl->length); 587 588 if (rl->lcn >= 0) { 589 update_full_status(vol,rl->lcn); 590 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn, 591 rl->length)) { 592 ntfs_log_perror("Cluster deallocation failed " 593 "(%lld, %lld)", 594 (long long)rl->lcn, 595 (long long)rl->length); 596 goto out; 597 } 598 nr_freed += rl->length ; 599 } 600 } 601 602 ret = 0; 603out: 604 vol->free_clusters += nr_freed; 605 if (vol->free_clusters > vol->nr_clusters) 606 ntfs_log_error("Too many free clusters (%lld > %lld)!", 607 (long long)vol->free_clusters, 608 (long long)vol->nr_clusters); 609 return ret; 610} 611 612/* 613 * Basic cluster run free 614 * Returns 0 if successful 615 */ 616 617int ntfs_cluster_free_basic(ntfs_volume *vol, s64 lcn, s64 count) 618{ 619 s64 nr_freed = 0; 620 int ret = -1; 621 622 ntfs_log_trace("Entering.\n"); 623 ntfs_log_trace("Dealloc lcn 0x%llx, len 0x%llx.\n", 624 (long long)lcn, (long long)count); 625 626 if (lcn >= 0) { 627 update_full_status(vol,lcn); 628 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, lcn, 629 count)) { 630 ntfs_log_perror("Cluster deallocation failed " 631 "(%lld, %lld)", 632 (long long)lcn, 633 (long long)count); 634 goto out; 635 } 636 nr_freed += count; 637 } 638 ret = 0; 639out: 640 vol->free_clusters += nr_freed; 641 if (vol->free_clusters > vol->nr_clusters) 642 ntfs_log_error("Too many free clusters (%lld > %lld)!", 643 (long long)vol->free_clusters, 644 (long long)vol->nr_clusters); 645 return ret; 646} 647 648/** 649 * ntfs_cluster_free - free clusters on an ntfs volume 650 * @vol: mounted ntfs volume on which to free the clusters 651 * @na: attribute whose runlist describes the clusters to free 652 * @start_vcn: vcn in @rl at which to start freeing clusters 653 * @count: number of clusters to free or -1 for all clusters 654 * 655 * Free @count clusters starting at the cluster @start_vcn in the runlist 656 * described by the attribute @na from the mounted ntfs volume @vol. 657 * 658 * If @count is -1, all clusters from @start_vcn to the end of the runlist 659 * are deallocated. 660 * 661 * On success return the number of deallocated clusters (not counting sparse 662 * clusters) and on error return -1 with errno set to the error code. 663 */ 664int ntfs_cluster_free(ntfs_volume *vol, ntfs_attr *na, VCN start_vcn, s64 count) 665{ 666 runlist *rl; 667 s64 delta, to_free, nr_freed = 0; 668 int ret = -1; 669 670 if (!vol || !vol->lcnbmp_na || !na || start_vcn < 0 || 671 (count < 0 && count != -1)) { 672 ntfs_log_trace("Invalid arguments!\n"); 673 errno = EINVAL; 674 return -1; 675 } 676 677 ntfs_log_enter("Entering for inode 0x%llx, attr 0x%x, count 0x%llx, " 678 "vcn 0x%llx.\n", (unsigned long long)na->ni->mft_no, 679 na->type, (long long)count, (long long)start_vcn); 680 681 rl = ntfs_attr_find_vcn(na, start_vcn); 682 if (!rl) { 683 if (errno == ENOENT) 684 ret = 0; 685 goto leave; 686 } 687 688 if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { 689 errno = EIO; 690 ntfs_log_perror("%s: Unexpected lcn (%lld)", __FUNCTION__, 691 (long long)rl->lcn); 692 goto leave; 693 } 694 695 /* Find the starting cluster inside the run that needs freeing. */ 696 delta = start_vcn - rl->vcn; 697 698 /* The number of clusters in this run that need freeing. */ 699 to_free = rl->length - delta; 700 if (count >= 0 && to_free > count) 701 to_free = count; 702 703 if (rl->lcn != LCN_HOLE) { 704 /* Do the actual freeing of the clusters in this run. */ 705 update_full_status(vol,rl->lcn + delta); 706 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn + delta, 707 to_free)) 708 goto leave; 709 nr_freed = to_free; 710 } 711 712 /* Go to the next run and adjust the number of clusters left to free. */ 713 ++rl; 714 if (count >= 0) 715 count -= to_free; 716 717 /* 718 * Loop over the remaining runs, using @count as a capping value, and 719 * free them. 720 */ 721 for (; rl->length && count != 0; ++rl) { 722 // FIXME: Need to try ntfs_attr_map_runlist() for attribute 723 // list support! (AIA) 724 if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { 725 // FIXME: Eeek! We need rollback! (AIA) 726 errno = EIO; 727 ntfs_log_perror("%s: Invalid lcn (%lli)", 728 __FUNCTION__, (long long)rl->lcn); 729 goto out; 730 } 731 732 /* The number of clusters in this run that need freeing. */ 733 to_free = rl->length; 734 if (count >= 0 && to_free > count) 735 to_free = count; 736 737 if (rl->lcn != LCN_HOLE) { 738 update_full_status(vol,rl->lcn); 739 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn, 740 to_free)) { 741 // FIXME: Eeek! We need rollback! (AIA) 742 ntfs_log_perror("%s: Clearing bitmap run failed", 743 __FUNCTION__); 744 goto out; 745 } 746 nr_freed += to_free; 747 } 748 749 if (count >= 0) 750 count -= to_free; 751 } 752 753 if (count != -1 && count != 0) { 754 // FIXME: Eeek! BUG() 755 errno = EIO; 756 ntfs_log_perror("%s: count still not zero (%lld)", __FUNCTION__, 757 (long long)count); 758 goto out; 759 } 760 761 ret = nr_freed; 762out: 763 vol->free_clusters += nr_freed ; 764 if (vol->free_clusters > vol->nr_clusters) 765 ntfs_log_error("Too many free clusters (%lld > %lld)!", 766 (long long)vol->free_clusters, 767 (long long)vol->nr_clusters); 768leave: 769 ntfs_log_leave("\n"); 770 return ret; 771} 772