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 (NVolFreeSpaceKnown(vol)) { 372 if (vol->free_clusters <= 0) 373 ntfs_log_error("Non-positive free" 374 " clusters (%lld)!\n", 375 (long long)vol->free_clusters); 376 else 377 vol->free_clusters--; 378 } 379 380 /* 381 * Coalesce with previous run if adjacent LCNs. 382 * Otherwise, append a new run. 383 */ 384 if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) { 385 ntfs_log_debug("Cluster coalesce: prev_lcn: " 386 "%lld lcn: %lld bmp_pos: %lld " 387 "prev_run_len: %lld\n", 388 (long long)prev_lcn, 389 (long long)lcn, (long long)bmp_pos, 390 (long long)prev_run_len); 391 rl[rlpos - 1].length = ++prev_run_len; 392 } else { 393 if (rlpos) 394 rl[rlpos].vcn = rl[rlpos - 1].vcn + 395 prev_run_len; 396 else { 397 rl[rlpos].vcn = start_vcn; 398 ntfs_log_debug("Start_vcn: %lld\n", 399 (long long)start_vcn); 400 } 401 402 rl[rlpos].lcn = prev_lcn = lcn + bmp_pos; 403 rl[rlpos].length = prev_run_len = 1; 404 rlpos++; 405 } 406 407 ntfs_log_debug("RUN: %-16lld %-16lld %-16lld\n", 408 (long long)rl[rlpos - 1].vcn, 409 (long long)rl[rlpos - 1].lcn, 410 (long long)rl[rlpos - 1].length); 411 /* Done? */ 412 if (!--clusters) { 413 if (used_zone_pos) 414 ntfs_cluster_update_zone_pos(vol, 415 search_zone, lcn + bmp_pos + 1 + 416 NTFS_LCNALLOC_SKIP); 417 goto done_ret; 418 } 419 420 lcn++; 421 } 422 423 if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) { 424 err = errno; 425 goto err_ret; 426 } 427 428 if (!used_zone_pos) { 429 430 used_zone_pos = 1; 431 432 if (search_zone == ZONE_MFT) 433 zone_start = vol->mft_zone_pos; 434 else if (search_zone == ZONE_DATA1) 435 zone_start = vol->data1_zone_pos; 436 else 437 zone_start = vol->data2_zone_pos; 438 439 if (!zone_start || zone_start == vol->mft_zone_start || 440 zone_start == vol->mft_zone_end) 441 pass = 2; 442 bmp_pos = zone_start; 443 } else 444 bmp_pos += buf_size; 445 446 if (bmp_pos < zone_end) 447 continue; 448 449zone_pass_done: 450 ntfs_log_trace("Finished current zone pass(%i).\n", pass); 451 if (pass == 1) { 452 pass = 2; 453 zone_end = zone_start; 454 455 if (search_zone == ZONE_MFT) 456 zone_start = vol->mft_zone_start; 457 else if (search_zone == ZONE_DATA1) 458 zone_start = vol->mft_zone_end; 459 else 460 zone_start = 0; 461 462 /* Sanity check. */ 463 if (zone_end < zone_start) 464 zone_end = zone_start; 465 466 bmp_pos = zone_start; 467 468 continue; 469 } 470 /* pass == 2 */ 471done_zones_check: 472 done_zones |= search_zone; 473 vol->full_zones |= search_zone; 474 if (done_zones < (ZONE_MFT + ZONE_DATA1 + ZONE_DATA2)) { 475 ntfs_log_trace("Switching zone.\n"); 476 pass = 1; 477 if (rlpos) { 478 LCN tc = rl[rlpos - 1].lcn + 479 rl[rlpos - 1].length + NTFS_LCNALLOC_SKIP; 480 481 if (used_zone_pos) 482 ntfs_cluster_update_zone_pos(vol, 483 search_zone, tc); 484 } 485 486 switch (search_zone) { 487 case ZONE_MFT: 488 ntfs_log_trace("Zone switch: mft -> data1\n"); 489switch_to_data1_zone: search_zone = ZONE_DATA1; 490 zone_start = vol->data1_zone_pos; 491 zone_end = vol->nr_clusters; 492 if (zone_start == vol->mft_zone_end) 493 pass = 2; 494 break; 495 case ZONE_DATA1: 496 ntfs_log_trace("Zone switch: data1 -> data2\n"); 497 search_zone = ZONE_DATA2; 498 zone_start = vol->data2_zone_pos; 499 zone_end = vol->mft_zone_start; 500 if (!zone_start) 501 pass = 2; 502 break; 503 case ZONE_DATA2: 504 if (!(done_zones & ZONE_DATA1)) { 505 ntfs_log_trace("data2 -> data1\n"); 506 goto switch_to_data1_zone; 507 } 508 ntfs_log_trace("Zone switch: data2 -> mft\n"); 509 search_zone = ZONE_MFT; 510 zone_start = vol->mft_zone_pos; 511 zone_end = vol->mft_zone_end; 512 if (zone_start == vol->mft_zone_start) 513 pass = 2; 514 break; 515 } 516 517 bmp_pos = zone_start; 518 519 if (zone_start == zone_end) { 520 ntfs_log_trace("Empty zone, skipped.\n"); 521 goto done_zones_check; 522 } 523 524 continue; 525 } 526 527 ntfs_log_trace("All zones are finished, no space on device.\n"); 528 err = ENOSPC; 529 goto err_ret; 530 } 531done_ret: 532 ntfs_log_debug("At done_ret.\n"); 533 /* Add runlist terminator element. */ 534 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; 535 rl[rlpos].lcn = LCN_RL_NOT_MAPPED; 536 rl[rlpos].length = 0; 537 if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) { 538 err = errno; 539 goto err_ret; 540 } 541done_err_ret: 542 free(buf); 543 if (err) { 544 errno = err; 545 ntfs_log_perror("Failed to allocate clusters"); 546 rl = NULL; 547 } 548out: 549 ntfs_log_leave("\n"); 550 return rl; 551 552wb_err_ret: 553 ntfs_log_trace("At wb_err_ret.\n"); 554 if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) 555 err = errno; 556err_ret: 557 ntfs_log_trace("At err_ret.\n"); 558 if (rl) { 559 /* Add runlist terminator element. */ 560 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; 561 rl[rlpos].lcn = LCN_RL_NOT_MAPPED; 562 rl[rlpos].length = 0; 563 ntfs_debug_runlist_dump(rl); 564 ntfs_cluster_free_from_rl(vol, rl); 565 free(rl); 566 rl = NULL; 567 } 568 goto done_err_ret; 569} 570 571/** 572 * ntfs_cluster_free_from_rl - free clusters from runlist 573 * @vol: mounted ntfs volume on which to free the clusters 574 * @rl: runlist from which deallocate clusters 575 * 576 * On success return 0 and on error return -1 with errno set to the error code. 577 */ 578int ntfs_cluster_free_from_rl(ntfs_volume *vol, runlist *rl) 579{ 580 s64 nr_freed = 0; 581 int ret = -1; 582 583 ntfs_log_trace("Entering.\n"); 584 585 for (; rl->length; rl++) { 586 587 ntfs_log_trace("Dealloc lcn 0x%llx, len 0x%llx.\n", 588 (long long)rl->lcn, (long long)rl->length); 589 590 if (rl->lcn >= 0) { 591 update_full_status(vol,rl->lcn); 592 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn, 593 rl->length)) { 594 ntfs_log_perror("Cluster deallocation failed " 595 "(%lld, %lld)", 596 (long long)rl->lcn, 597 (long long)rl->length); 598 goto out; 599 } 600 nr_freed += rl->length ; 601 } 602 } 603 604 ret = 0; 605out: 606 vol->free_clusters += nr_freed; 607 if (NVolFreeSpaceKnown(vol) 608 && (vol->free_clusters > vol->nr_clusters)) 609 ntfs_log_error("Too many free clusters (%lld > %lld)!", 610 (long long)vol->free_clusters, 611 (long long)vol->nr_clusters); 612 return ret; 613} 614 615/* 616 * Basic cluster run free 617 * Returns 0 if successful 618 */ 619 620int ntfs_cluster_free_basic(ntfs_volume *vol, s64 lcn, s64 count) 621{ 622 s64 nr_freed = 0; 623 int ret = -1; 624 625 ntfs_log_trace("Entering.\n"); 626 ntfs_log_trace("Dealloc lcn 0x%llx, len 0x%llx.\n", 627 (long long)lcn, (long long)count); 628 629 if (lcn >= 0) { 630 update_full_status(vol,lcn); 631 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, lcn, 632 count)) { 633 ntfs_log_perror("Cluster deallocation failed " 634 "(%lld, %lld)", 635 (long long)lcn, 636 (long long)count); 637 goto out; 638 } 639 nr_freed += count; 640 } 641 ret = 0; 642out: 643 vol->free_clusters += nr_freed; 644 if (vol->free_clusters > vol->nr_clusters) 645 ntfs_log_error("Too many free clusters (%lld > %lld)!", 646 (long long)vol->free_clusters, 647 (long long)vol->nr_clusters); 648 return ret; 649} 650 651/** 652 * ntfs_cluster_free - free clusters on an ntfs volume 653 * @vol: mounted ntfs volume on which to free the clusters 654 * @na: attribute whose runlist describes the clusters to free 655 * @start_vcn: vcn in @rl at which to start freeing clusters 656 * @count: number of clusters to free or -1 for all clusters 657 * 658 * Free @count clusters starting at the cluster @start_vcn in the runlist 659 * described by the attribute @na from the mounted ntfs volume @vol. 660 * 661 * If @count is -1, all clusters from @start_vcn to the end of the runlist 662 * are deallocated. 663 * 664 * On success return the number of deallocated clusters (not counting sparse 665 * clusters) and on error return -1 with errno set to the error code. 666 */ 667int ntfs_cluster_free(ntfs_volume *vol, ntfs_attr *na, VCN start_vcn, s64 count) 668{ 669 runlist *rl; 670 s64 delta, to_free, nr_freed = 0; 671 int ret = -1; 672 673 if (!vol || !vol->lcnbmp_na || !na || start_vcn < 0 || 674 (count < 0 && count != -1)) { 675 ntfs_log_trace("Invalid arguments!\n"); 676 errno = EINVAL; 677 return -1; 678 } 679 680 ntfs_log_enter("Entering for inode 0x%llx, attr 0x%x, count 0x%llx, " 681 "vcn 0x%llx.\n", (unsigned long long)na->ni->mft_no, 682 le32_to_cpu(na->type), (long long)count, (long long)start_vcn); 683 684 rl = ntfs_attr_find_vcn(na, start_vcn); 685 if (!rl) { 686 if (errno == ENOENT) 687 ret = 0; 688 goto leave; 689 } 690 691 if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { 692 errno = EIO; 693 ntfs_log_perror("%s: Unexpected lcn (%lld)", __FUNCTION__, 694 (long long)rl->lcn); 695 goto leave; 696 } 697 698 /* Find the starting cluster inside the run that needs freeing. */ 699 delta = start_vcn - rl->vcn; 700 701 /* The number of clusters in this run that need freeing. */ 702 to_free = rl->length - delta; 703 if (count >= 0 && to_free > count) 704 to_free = count; 705 706 if (rl->lcn != LCN_HOLE) { 707 /* Do the actual freeing of the clusters in this run. */ 708 update_full_status(vol,rl->lcn + delta); 709 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn + delta, 710 to_free)) 711 goto leave; 712 nr_freed = to_free; 713 } 714 715 /* Go to the next run and adjust the number of clusters left to free. */ 716 ++rl; 717 if (count >= 0) 718 count -= to_free; 719 720 /* 721 * Loop over the remaining runs, using @count as a capping value, and 722 * free them. 723 */ 724 for (; rl->length && count != 0; ++rl) { 725 // FIXME: Need to try ntfs_attr_map_runlist() for attribute 726 // list support! (AIA) 727 if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { 728 // FIXME: Eeek! We need rollback! (AIA) 729 errno = EIO; 730 ntfs_log_perror("%s: Invalid lcn (%lli)", 731 __FUNCTION__, (long long)rl->lcn); 732 goto out; 733 } 734 735 /* The number of clusters in this run that need freeing. */ 736 to_free = rl->length; 737 if (count >= 0 && to_free > count) 738 to_free = count; 739 740 if (rl->lcn != LCN_HOLE) { 741 update_full_status(vol,rl->lcn); 742 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn, 743 to_free)) { 744 // FIXME: Eeek! We need rollback! (AIA) 745 ntfs_log_perror("%s: Clearing bitmap run failed", 746 __FUNCTION__); 747 goto out; 748 } 749 nr_freed += to_free; 750 } 751 752 if (count >= 0) 753 count -= to_free; 754 } 755 756 if (count != -1 && count != 0) { 757 // FIXME: Eeek! BUG() 758 errno = EIO; 759 ntfs_log_perror("%s: count still not zero (%lld)", __FUNCTION__, 760 (long long)count); 761 goto out; 762 } 763 764 ret = nr_freed; 765out: 766 vol->free_clusters += nr_freed ; 767 if (vol->free_clusters > vol->nr_clusters) 768 ntfs_log_error("Too many free clusters (%lld > %lld)!", 769 (long long)vol->free_clusters, 770 (long long)vol->nr_clusters); 771leave: 772 ntfs_log_leave("\n"); 773 return ret; 774} 775