1 /** 2 * lcnalloc.c - Cluster (de)allocation code. Part of the Linux-NTFS project. 3 * 4 * Copyright (c) 2002-2004 Anton Altaparmakov 5 * Copyright (c) 2004 Yura Pakhuchiy 6 * 7 * This program/include file is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License as published 9 * by the Free Software Foundation; either version 2 of the License, or 10 * (at your option) any later version. 11 * 12 * This program/include file is distributed in the hope that it will be 13 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty 14 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program (in the main directory of the Linux-NTFS 19 * distribution in the file COPYING); if not, write to the Free Software 20 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 21 */ 22 23 #ifdef HAVE_CONFIG_H 24 #include "config.h" 25 #endif 26 27 #ifdef HAVE_STDLIB_H 28 #include <stdlib.h> 29 #endif 30 #ifdef HAVE_STDIO_H 31 #include <stdio.h> 32 #endif 33 #ifdef HAVE_ERRNO_H 34 #include <errno.h> 35 #endif 36 37 #include "compat.h" 38 #include "types.h" 39 #include "attrib.h" 40 #include "bitmap.h" 41 #include "debug.h" 42 #include "runlist.h" 43 #include "volume.h" 44 #include "lcnalloc.h" 45 #include "logging.h" 46 47 /** 48 * ntfs_cluster_alloc - allocate clusters on an ntfs volume 49 * @vol: mounted ntfs volume on which to allocate the clusters 50 * @start_vcn: vcn to use for the first allocated cluster 51 * @count: number of clusters to allocate 52 * @start_lcn: starting lcn at which to allocate the clusters (or -1 if none) 53 * @zone: zone from which to allocate the clusters 54 * 55 * Allocate @count clusters preferably starting at cluster @start_lcn or at the 56 * current allocator position if @start_lcn is -1, on the mounted ntfs volume 57 * @vol. @zone is either DATA_ZONE for allocation of normal clusters and 58 * MFT_ZONE for allocation of clusters for the master file table, i.e. the 59 * $MFT/$DATA attribute. 60 * 61 * On success return a runlist describing the allocated cluster(s). 62 * 63 * On error return NULL with errno set to the error code. 64 * 65 * Notes on the allocation algorithm 66 * ================================= 67 * 68 * There are two data zones. First is the area between the end of the mft zone 69 * and the end of the volume, and second is the area between the start of the 70 * volume and the start of the mft zone. On unmodified/standard NTFS 1.x 71 * volumes, the second data zone doesn't exist due to the mft zone being 72 * expanded to cover the start of the volume in order to reserve space for the 73 * mft bitmap attribute. 74 * 75 * This is not the prettiest function but the complexity stems from the need of 76 * implementing the mft vs data zoned approach and from the fact that we have 77 * access to the lcn bitmap in portions of up to 8192 bytes at a time, so we 78 * need to cope with crossing over boundaries of two buffers. Further, the fact 79 * that the allocator allows for caller supplied hints as to the location of 80 * where allocation should begin and the fact that the allocator keeps track of 81 * where in the data zones the next natural allocation should occur, contribute 82 * to the complexity of the function. But it should all be worthwhile, because 83 * this allocator should: 1) be a full implementation of the MFT zone approach 84 * used by Windows, 2) cause reduction in fragmentation as much as possible, 85 * and 3) be speedy in allocations (the code is not optimized for speed, but 86 * the algorithm is, so further speed improvements are probably possible). 87 * 88 * FIXME: We should be monitoring cluster allocation and increment the MFT zone 89 * size dynamically but this is something for the future. We will just cause 90 * heavier fragmentation by not doing it and I am not even sure Windows would 91 * grow the MFT zone dynamically, so it might even be correct not to do this. 92 * The overhead in doing dynamic MFT zone expansion would be very large and 93 * unlikely worth the effort. (AIA) 94 * 95 * TODO: I have added in double the required zone position pointer wrap around 96 * logic which can be optimized to having only one of the two logic sets. 97 * However, having the double logic will work fine, but if we have only one of 98 * the sets and we get it wrong somewhere, then we get into trouble, so 99 * removing the duplicate logic requires _very_ careful consideration of _all_ 100 * possible code paths. So at least for now, I am leaving the double logic - 101 * better safe than sorry... (AIA) 102 */ 103 runlist *ntfs_cluster_alloc(ntfs_volume *vol, VCN start_vcn, s64 count, 104 LCN start_lcn, const NTFS_CLUSTER_ALLOCATION_ZONES zone) 105 { 106 LCN zone_start, zone_end, bmp_pos, bmp_initial_pos, last_read_pos, lcn; 107 LCN prev_lcn = 0, prev_run_len = 0, mft_zone_size; 108 s64 clusters, br; 109 runlist *rl = NULL, *trl; 110 u8 *buf, *byte; 111 int err = 0, rlpos, rlsize, buf_size; 112 u8 pass, done_zones, search_zone, need_writeback, bit; 113 114 ntfs_log_trace("Entering with count = 0x%llx, start_lcn = 0x%llx, zone = " 115 "%s_ZONE.\n", (long long)count, (long long)start_lcn, 116 zone == MFT_ZONE ? "MFT" : "DATA"); 117 if (!vol || count < 0 || start_lcn < -1 || !vol->lcnbmp_na || 118 (s8)zone < FIRST_ZONE || zone > LAST_ZONE) { 119 ntfs_log_trace("Invalid arguments!\n"); 120 errno = EINVAL; 121 return NULL; 122 } 123 124 /* Return empty runlist if @count == 0 */ 125 if (!count) { 126 rl = ntfs_malloc(0x1000); 127 if (!rl) 128 return NULL; 129 rl[0].vcn = start_vcn; 130 rl[0].lcn = LCN_RL_NOT_MAPPED; 131 rl[0].length = 0; 132 return rl; 133 } 134 135 /* Allocate memory. */ 136 buf = (u8*)ntfs_malloc(8192); 137 if (!buf) 138 return NULL; 139 /* 140 * If no specific @start_lcn was requested, use the current data zone 141 * position, otherwise use the requested @start_lcn but make sure it 142 * lies outside the mft zone. Also set done_zones to 0 (no zones done) 143 * and pass depending on whether we are starting inside a zone (1) or 144 * at the beginning of a zone (2). If requesting from the MFT_ZONE, 145 * we either start at the current position within the mft zone or at 146 * the specified position. If the latter is out of bounds then we start 147 * at the beginning of the MFT_ZONE. 148 */ 149 done_zones = 0; 150 pass = 1; 151 /* 152 * zone_start and zone_end are the current search range. search_zone 153 * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of 154 * volume) and 4 for data zone 2 (start of volume till start of mft 155 * zone). 156 */ 157 zone_start = start_lcn; 158 if (zone_start < 0) { 159 if (zone == DATA_ZONE) 160 zone_start = vol->data1_zone_pos; 161 else 162 zone_start = vol->mft_zone_pos; 163 if (!zone_start) { 164 /* 165 * Zone starts at beginning of volume which means a 166 * single pass is sufficient. 167 */ 168 pass = 2; 169 } 170 } else if (zone == DATA_ZONE && zone_start >= vol->mft_zone_start && 171 zone_start < vol->mft_zone_end) { 172 zone_start = vol->mft_zone_end; 173 /* 174 * Starting at beginning of data1_zone which means a single 175 * pass in this zone is sufficient. 176 */ 177 pass = 2; 178 } else if (zone == MFT_ZONE && (zone_start < vol->mft_zone_start || 179 zone_start >= vol->mft_zone_end)) { 180 zone_start = vol->mft_lcn; 181 if (!vol->mft_zone_end) 182 zone_start = 0; 183 /* 184 * Starting at beginning of volume which means a single pass 185 * is sufficient. 186 */ 187 pass = 2; 188 } 189 if (zone == MFT_ZONE) { 190 zone_end = vol->mft_zone_end; 191 search_zone = 1; 192 } else /* if (zone == DATA_ZONE) */ { 193 /* Skip searching the mft zone. */ 194 done_zones |= 1; 195 if (zone_start >= vol->mft_zone_end) { 196 zone_end = vol->nr_clusters; 197 search_zone = 2; 198 } else { 199 zone_end = vol->mft_zone_start; 200 search_zone = 4; 201 } 202 } 203 /* 204 * bmp_pos is the current bit position inside the bitmap. We use 205 * bmp_initial_pos to determine whether or not to do a zone switch. 206 */ 207 bmp_pos = bmp_initial_pos = zone_start; 208 209 /* Loop until all clusters are allocated, i.e. clusters == 0. */ 210 clusters = count; 211 rlpos = rlsize = 0; 212 while (1) { 213 ntfs_log_trace("Start of outer while loop: done_zones = 0x%x, " 214 "search_zone = %i, pass = %i, zone_start = " 215 "0x%llx, zone_end = 0x%llx, bmp_initial_pos = " 216 "0x%llx, bmp_pos = 0x%llx, rlpos = %i, rlsize = " 217 "%i.\n", done_zones, search_zone, pass, 218 (long long)zone_start, (long long)zone_end, 219 (long long)bmp_initial_pos, (long long)bmp_pos, 220 rlpos, rlsize); 221 /* Loop until we run out of free clusters. */ 222 last_read_pos = bmp_pos >> 3; 223 ntfs_log_trace("last_read_pos = 0x%llx.\n", (long long)last_read_pos); 224 br = ntfs_attr_pread(vol->lcnbmp_na, last_read_pos, 8192, buf); 225 if (br <= 0) { 226 if (!br) { 227 /* Reached end of attribute. */ 228 ntfs_log_trace("End of attribute reached. Skipping " 229 "to zone_pass_done.\n"); 230 goto zone_pass_done; 231 } 232 err = errno; 233 ntfs_log_trace("ntfs_attr_pread() failed. Aborting.\n"); 234 goto err_ret; 235 } 236 /* 237 * We might have read less than 8192 bytes if we are close to 238 * the end of the attribute. 239 */ 240 buf_size = (int)br << 3; 241 lcn = bmp_pos & 7; 242 bmp_pos &= ~7; 243 need_writeback = 0; 244 ntfs_log_trace("Before inner while loop: buf_size = %i, lcn = " 245 "0x%llx, bmp_pos = 0x%llx, need_writeback = %i.\n", 246 buf_size, (long long)lcn, (long long)bmp_pos, 247 need_writeback); 248 while (lcn < buf_size && lcn + bmp_pos < zone_end) { 249 byte = buf + (lcn >> 3); 250 ntfs_log_trace("In inner while loop: buf_size = %i, lcn = " 251 "0x%llx, bmp_pos = 0x%llx, " 252 "need_writeback = %i, byte ofs = 0x%x, " 253 "*byte = 0x%x.\n", buf_size, 254 (long long)lcn, (long long)bmp_pos, 255 need_writeback, (unsigned int)(lcn >> 3), 256 (unsigned int)*byte); 257 /* Skip full bytes. */ 258 if (*byte == 0xff) { 259 lcn = (lcn + 8) & ~7; 260 ntfs_log_trace("continuing while loop 1.\n"); 261 continue; 262 } 263 bit = 1 << (lcn & 7); 264 ntfs_log_trace("bit = %i.\n", bit); 265 /* If the bit is already set, go onto the next one. */ 266 if (*byte & bit) { 267 lcn++; 268 ntfs_log_trace("continuing while loop 2.\n"); 269 continue; 270 } 271 /* Reallocate memory if necessary. */ 272 if ((rlpos + 2) * (int)sizeof(runlist) >= rlsize) { 273 ntfs_log_trace("Reallocating space.\n"); 274 if (!rl) 275 ntfs_log_trace("First free bit is at LCN = " 276 "0x%llx.\n", (long long)(lcn + bmp_pos)); 277 rlsize += 4096; 278 trl = (runlist*)realloc(rl, rlsize); 279 if (!trl) { 280 err = ENOMEM; 281 ntfs_log_trace("Failed to allocate memory, " 282 "going to wb_err_ret.\n"); 283 goto wb_err_ret; 284 } 285 rl = trl; 286 ntfs_log_trace("Reallocated memory, rlsize = " 287 "0x%x.\n", rlsize); 288 } 289 /* Allocate the bitmap bit. */ 290 *byte |= bit; 291 vol->nr_free_clusters--; 292 /* We need to write this bitmap buffer back to disk! */ 293 need_writeback = 1; 294 ntfs_log_trace("*byte = 0x%x, need_writeback is set.\n", 295 (unsigned int)*byte); 296 /* 297 * Coalesce with previous run if adjacent LCNs. 298 * Otherwise, append a new run. 299 */ 300 ntfs_log_trace("Adding run (lcn 0x%llx, len 0x%llx), " 301 "prev_lcn = 0x%llx, lcn = 0x%llx, " 302 "bmp_pos = 0x%llx, prev_run_len = " 303 "0x%llx, rlpos = %i.\n", 304 (long long)(lcn + bmp_pos), 1LL, 305 (long long)prev_lcn, (long long)lcn, 306 (long long)bmp_pos, 307 (long long)prev_run_len, rlpos); 308 if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) { 309 ntfs_log_trace("Coalescing to run (lcn 0x%llx, len " 310 "0x%llx).\n", 311 (long long)rl[rlpos - 1].lcn, 312 (long long) rl[rlpos - 1].length); 313 rl[rlpos - 1].length = ++prev_run_len; 314 ntfs_log_trace("Run now (lcn 0x%llx, len 0x%llx), " 315 "prev_run_len = 0x%llx.\n", 316 (long long)rl[rlpos - 1].lcn, 317 (long long)rl[rlpos - 1].length, 318 (long long)prev_run_len); 319 } else { 320 if (rlpos) { 321 ntfs_log_trace("Adding new run, (previous " 322 "run lcn 0x%llx, len 0x%llx).\n", 323 (long long) rl[rlpos - 1].lcn, 324 (long long) rl[rlpos - 1].length); 325 rl[rlpos].vcn = rl[rlpos - 1].vcn + 326 prev_run_len; 327 } else { 328 ntfs_log_trace("Adding new run, is first run.\n"); 329 rl[rlpos].vcn = start_vcn; 330 } 331 rl[rlpos].lcn = prev_lcn = lcn + bmp_pos; 332 rl[rlpos].length = prev_run_len = 1; 333 rlpos++; 334 } 335 /* Done? */ 336 if (!--clusters) { 337 LCN tc; 338 /* 339 * Update the current zone position. Positions 340 * of already scanned zones have been updated 341 * during the respective zone switches. 342 */ 343 tc = lcn + bmp_pos + 1; 344 ntfs_log_trace("Done. Updating current zone " 345 "position, tc = 0x%llx, search_zone = %i.\n", 346 (long long)tc, search_zone); 347 switch (search_zone) { 348 case 1: 349 ntfs_log_trace("Before checks, vol->mft_zone_pos = 0x%llx.\n", 350 (long long) vol->mft_zone_pos); 351 if (tc >= vol->mft_zone_end) { 352 vol->mft_zone_pos = 353 vol->mft_lcn; 354 if (!vol->mft_zone_end) 355 vol->mft_zone_pos = 0; 356 } else if ((bmp_initial_pos >= 357 vol->mft_zone_pos || 358 tc > vol->mft_zone_pos) 359 && tc >= vol->mft_lcn) 360 vol->mft_zone_pos = tc; 361 ntfs_log_trace("After checks, vol->mft_zone_pos = 0x%llx.\n", 362 (long long) vol->mft_zone_pos); 363 break; 364 case 2: 365 ntfs_log_trace("Before checks, vol->data1_zone_pos = 0x%llx.\n", 366 (long long) vol->data1_zone_pos); 367 if (tc >= vol->nr_clusters) 368 vol->data1_zone_pos = 369 vol->mft_zone_end; 370 else if ((bmp_initial_pos >= 371 vol->data1_zone_pos || 372 tc > vol->data1_zone_pos) 373 && tc >= vol->mft_zone_end) 374 vol->data1_zone_pos = tc; 375 ntfs_log_trace("After checks, vol->data1_zone_pos = 0x%llx.\n", 376 (long long) vol->data1_zone_pos); 377 break; 378 case 4: 379 ntfs_log_trace("Before checks, vol->data2_zone_pos = 0x%llx.\n", 380 (long long) vol->data2_zone_pos); 381 if (tc >= vol->mft_zone_start) 382 vol->data2_zone_pos = 0; 383 else if (bmp_initial_pos >= 384 vol->data2_zone_pos || 385 tc > vol->data2_zone_pos) 386 vol->data2_zone_pos = tc; 387 ntfs_log_trace("After checks, vol->data2_zone_pos = 0x%llx.\n", 388 (long long) vol->data2_zone_pos); 389 break; 390 default: 391 free(rl); 392 free(buf); 393 NTFS_BUG("switch (search_zone) 1"); 394 return NULL; 395 } 396 ntfs_log_trace("Going to done_ret.\n"); 397 goto done_ret; 398 } 399 lcn++; 400 } 401 bmp_pos += buf_size; 402 ntfs_log_trace("After inner while loop: buf_size = 0x%x, lcn = " 403 "0x%llx, bmp_pos = 0x%llx, need_writeback = %i.\n", 404 buf_size, (long long)lcn, 405 (long long)bmp_pos, need_writeback); 406 if (need_writeback) { 407 s64 bw; 408 ntfs_log_trace("Writing back.\n"); 409 need_writeback = 0; 410 bw = ntfs_attr_pwrite(vol->lcnbmp_na, last_read_pos, 411 br, buf); 412 if (bw != br) { 413 if (bw == -1) 414 err = errno; 415 else 416 err = EIO; 417 ntfs_log_trace("Bitmap writeback failed in read next " 418 "buffer code path with error code %i.\n", err); 419 goto err_ret; 420 } 421 } 422 if (bmp_pos < zone_end) { 423 ntfs_log_trace("Continuing outer while loop, bmp_pos = " 424 "0x%llx, zone_end = 0x%llx.\n", 425 (long long)bmp_pos, 426 (long long)zone_end); 427 continue; 428 } 429 zone_pass_done: /* Finished with the current zone pass. */ 430 ntfs_log_trace("At zone_pass_done, pass = %i.\n", pass); 431 if (pass == 1) { 432 /* 433 * Now do pass 2, scanning the first part of the zone 434 * we omitted in pass 1. 435 */ 436 pass = 2; 437 zone_end = zone_start; 438 switch (search_zone) { 439 case 1: /* mft_zone */ 440 zone_start = vol->mft_zone_start; 441 break; 442 case 2: /* data1_zone */ 443 zone_start = vol->mft_zone_end; 444 break; 445 case 4: /* data2_zone */ 446 zone_start = 0; 447 break; 448 default: 449 NTFS_BUG("switch (search_zone) 2"); 450 } 451 /* Sanity check. */ 452 if (zone_end < zone_start) 453 zone_end = zone_start; 454 bmp_pos = zone_start; 455 ntfs_log_trace("Continuing outer while loop, pass = 2, " 456 "zone_start = 0x%llx, zone_end = " 457 "0x%llx, bmp_pos = 0x%llx.\n", 458 zone_start, zone_end, bmp_pos); 459 continue; 460 } /* pass == 2 */ 461 done_zones_check: 462 ntfs_log_trace("At done_zones_check, search_zone = %i, done_zones " 463 "before = 0x%x, done_zones after = 0x%x.\n", 464 search_zone, done_zones, done_zones | search_zone); 465 done_zones |= search_zone; 466 if (done_zones < 7) { 467 ntfs_log_trace("Switching zone.\n"); 468 /* Now switch to the next zone we haven't done yet. */ 469 pass = 1; 470 switch (search_zone) { 471 case 1: 472 ntfs_log_trace("Switching from mft zone to data1 " 473 "zone.\n"); 474 /* Update mft zone position. */ 475 if (rlpos) { 476 LCN tc; 477 ntfs_log_trace("Before checks, vol->mft_zone_pos = 0x%llx.\n", 478 (long long) vol->mft_zone_pos); 479 tc = rl[rlpos - 1].lcn + 480 rl[rlpos - 1].length; 481 if (tc >= vol->mft_zone_end) { 482 vol->mft_zone_pos = 483 vol->mft_lcn; 484 if (!vol->mft_zone_end) 485 vol->mft_zone_pos = 0; 486 } else if ((bmp_initial_pos >= 487 vol->mft_zone_pos || 488 tc > vol->mft_zone_pos) 489 && tc >= vol->mft_lcn) 490 vol->mft_zone_pos = tc; 491 ntfs_log_trace("After checks, vol->mft_zone_pos = 0x%llx.\n", 492 (long long) vol->mft_zone_pos); 493 } 494 /* Switch from mft zone to data1 zone. */ 495 switch_to_data1_zone: search_zone = 2; 496 zone_start = bmp_initial_pos = 497 vol->data1_zone_pos; 498 zone_end = vol->nr_clusters; 499 if (zone_start == vol->mft_zone_end) 500 pass = 2; 501 if (zone_start >= zone_end) { 502 vol->data1_zone_pos = zone_start = 503 vol->mft_zone_end; 504 pass = 2; 505 } 506 break; 507 case 2: 508 ntfs_log_trace("Switching from data1 zone to data2 " 509 "zone.\n"); 510 /* Update data1 zone position. */ 511 if (rlpos) { 512 LCN tc; 513 ntfs_log_trace("Before checks, vol->data1_zone_pos = 0x%llx.\n", 514 (long long) vol->data1_zone_pos); 515 tc = rl[rlpos - 1].lcn + 516 rl[rlpos - 1].length; 517 if (tc >= vol->nr_clusters) 518 vol->data1_zone_pos = 519 vol->mft_zone_end; 520 else if ((bmp_initial_pos >= 521 vol->data1_zone_pos || 522 tc > vol->data1_zone_pos) 523 && tc >= vol->mft_zone_end) 524 vol->data1_zone_pos = tc; 525 ntfs_log_trace("After checks, vol->data1_zone_pos = 0x%llx.\n", 526 (long long) vol->data1_zone_pos); 527 } 528 /* Switch from data1 zone to data2 zone. */ 529 search_zone = 4; 530 zone_start = bmp_initial_pos = 531 vol->data2_zone_pos; 532 zone_end = vol->mft_zone_start; 533 if (!zone_start) 534 pass = 2; 535 if (zone_start >= zone_end) { 536 vol->data2_zone_pos = zone_start = 537 bmp_initial_pos = 0; 538 pass = 2; 539 } 540 break; 541 case 4: 542 ntfs_log_debug("Switching from data2 zone to data1 " 543 "zone.\n"); 544 /* Update data2 zone position. */ 545 if (rlpos) { 546 LCN tc; 547 ntfs_log_trace("Before checks, vol->data2_zone_pos = 0x%llx.\n", 548 (long long) vol->data2_zone_pos); 549 tc = rl[rlpos - 1].lcn + 550 rl[rlpos - 1].length; 551 if (tc >= vol->mft_zone_start) 552 vol->data2_zone_pos = 0; 553 else if (bmp_initial_pos >= 554 vol->data2_zone_pos || 555 tc > vol->data2_zone_pos) 556 vol->data2_zone_pos = tc; 557 ntfs_log_trace("After checks, vol->data2_zone_pos = 0x%llx.\n", 558 (long long) vol->data2_zone_pos); 559 } 560 /* Switch from data2 zone to data1 zone. */ 561 goto switch_to_data1_zone; /* See above. */ 562 default: 563 NTFS_BUG("switch (search_zone) 3"); 564 } 565 ntfs_log_trace("After zone switch, search_zone = %i, pass = " 566 "%i, bmp_initial_pos = 0x%llx, " 567 "zone_start = 0x%llx, zone_end = " 568 "0x%llx.\n", search_zone, pass, 569 (long long)bmp_initial_pos, 570 (long long)zone_start, 571 (long long)zone_end); 572 bmp_pos = zone_start; 573 if (zone_start == zone_end) { 574 ntfs_log_trace("Empty zone, going to " 575 "done_zones_check.\n"); 576 /* Empty zone. Don't bother searching it. */ 577 goto done_zones_check; 578 } 579 ntfs_log_trace("Continuing outer while loop.\n"); 580 continue; 581 } /* done_zones == 7 */ 582 ntfs_log_trace("All zones are finished.\n"); 583 /* 584 * All zones are finished! If DATA_ZONE, shrink mft zone. If 585 * MFT_ZONE, we have really run out of space. 586 */ 587 mft_zone_size = vol->mft_zone_end - vol->mft_zone_start; 588 ntfs_log_trace("vol->mft_zone_start = 0x%llx, vol->mft_zone_end = " 589 "0x%llx, mft_zone_size = 0x%llx.\n", 590 (long long)vol->mft_zone_start, 591 (long long)vol->mft_zone_end, 592 (long long)mft_zone_size); 593 if (zone == MFT_ZONE || mft_zone_size <= 0) { 594 ntfs_log_trace("No free clusters left, going to err_ret.\n"); 595 /* Really no more space left on device. */ 596 err = ENOSPC; 597 goto err_ret; 598 } /* zone == DATA_ZONE && mft_zone_size > 0 */ 599 ntfs_log_trace("Shrinking mft zone.\n"); 600 zone_end = vol->mft_zone_end; 601 mft_zone_size >>= 1; 602 if (mft_zone_size > 0) 603 vol->mft_zone_end = vol->mft_zone_start + mft_zone_size; 604 else /* mft zone and data2 zone no longer exist. */ 605 vol->data2_zone_pos = vol->mft_zone_start = 606 vol->mft_zone_end = 0; 607 if (vol->mft_zone_pos >= vol->mft_zone_end) { 608 vol->mft_zone_pos = vol->mft_lcn; 609 if (!vol->mft_zone_end) 610 vol->mft_zone_pos = 0; 611 } 612 bmp_pos = zone_start = bmp_initial_pos = 613 vol->data1_zone_pos = vol->mft_zone_end; 614 search_zone = 2; 615 pass = 2; 616 done_zones &= ~2; 617 ntfs_log_trace("After shrinking mft zone, mft_zone_size = 0x%llx, " 618 "vol->mft_zone_start = 0x%llx, " 619 "vol->mft_zone_end = 0x%llx, vol->mft_zone_pos " 620 "= 0x%llx, search_zone = 2, pass = 2, " 621 "dones_zones = 0x%x, zone_start = 0x%llx, " 622 "zone_end = 0x%llx, vol->data1_zone_pos = " 623 "0x%llx, continuing outer while loop.\n", 624 (long long)mft_zone_size, 625 (long long)vol->mft_zone_start, 626 (long long)vol->mft_zone_end, 627 (long long)vol->mft_zone_pos, 628 done_zones, 629 (long long)zone_start, 630 (long long)zone_end, 631 (long long)vol->data1_zone_pos); 632 } 633 ntfs_log_debug("After outer while loop.\n"); 634 done_ret: 635 ntfs_log_debug("At done_ret.\n"); 636 /* Add runlist terminator element. */ 637 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; 638 rl[rlpos].lcn = LCN_RL_NOT_MAPPED; 639 rl[rlpos].length = 0; 640 if (need_writeback) { 641 s64 bw; 642 ntfs_log_trace("Writing back.\n"); 643 need_writeback = 0; 644 bw = ntfs_attr_pwrite(vol->lcnbmp_na, last_read_pos, br, buf); 645 if (bw != br) { 646 if (bw < 0) 647 err = errno; 648 else 649 err = EIO; 650 ntfs_log_trace("Bitmap writeback failed in done code path " 651 "with error code %i.\n", err); 652 goto err_ret; 653 } 654 } 655 done_err_ret: 656 ntfs_log_debug("At done_err_ret (follows done_ret).\n"); 657 free(buf); 658 /* Done! */ 659 if (!err) 660 return rl; 661 ntfs_log_trace("Failed to allocate clusters. Returning with error code " 662 "%i.\n", err); 663 errno = err; 664 return NULL; 665 wb_err_ret: 666 ntfs_log_trace("At wb_err_ret.\n"); 667 if (need_writeback) { 668 s64 bw; 669 ntfs_log_trace("Writing back.\n"); 670 need_writeback = 0; 671 bw = ntfs_attr_pwrite(vol->lcnbmp_na, last_read_pos, br, buf); 672 if (bw != br) { 673 if (bw < 0) 674 err = errno; 675 else 676 err = EIO; 677 ntfs_log_trace("Bitmap writeback failed in error code path " 678 "with error code %i.\n", err); 679 } 680 } 681 err_ret: 682 ntfs_log_trace("At err_ret.\n"); 683 if (rl) { 684 if (err == ENOSPC) { 685 ntfs_log_trace("err = ENOSPC, first free lcn = 0x%llx, could " 686 "allocate up to = 0x%llx clusters.\n", 687 (long long)rl[0].lcn, 688 (long long)count - clusters); 689 } 690 /* Add runlist terminator element. */ 691 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; 692 rl[rlpos].lcn = LCN_RL_NOT_MAPPED; 693 rl[rlpos].length = 0; 694 /* Deallocate all allocated clusters. */ 695 ntfs_log_trace("Deallocating allocated clusters.\n"); 696 ntfs_cluster_free_from_rl(vol, rl); 697 /* Free the runlist. */ 698 free(rl); 699 rl = NULL; 700 } else { 701 if (err == ENOSPC) { 702 ntfs_log_trace("No space left at all, err = ENOSPC, first " 703 "free lcn = 0x%llx.\n", 704 (long long)vol->data1_zone_pos); 705 } 706 } 707 ntfs_log_trace("rl = NULL, going to done_err_ret.\n"); 708 goto done_err_ret; 709 } 710 711 /** 712 * ntfs_cluster_free_from_rl - free clusters from runlist 713 * @vol: mounted ntfs volume on which to free the clusters 714 * @rl: runlist from which deallocate clusters 715 * 716 * On success return 0 and on error return -1 with errno set to the error code. 717 */ 718 int ntfs_cluster_free_from_rl(ntfs_volume *vol, runlist *rl) 719 { 720 ntfs_log_trace("Entering.\n"); 721 722 for (; rl->length; rl++) { 723 724 ntfs_log_trace("Dealloc lcn 0x%llx, len 0x%llx.\n", 725 (long long)rl->lcn, (long long)rl->length); 726 727 if (rl->lcn >= 0 && ntfs_bitmap_clear_run(vol->lcnbmp_na, 728 rl->lcn, rl->length)) { 729 int eo = errno; 730 ntfs_log_trace("Eeek! Deallocation of clusters failed.\n"); 731 errno = eo; 732 return -1; 733 } 734 } 735 return 0; 736 } 737 738 /** 739 * ntfs_cluster_free - free clusters on an ntfs volume 740 * @vol: mounted ntfs volume on which to free the clusters 741 * @na: attribute whose runlist describes the clusters to free 742 * @start_vcn: vcn in @rl at which to start freeing clusters 743 * @count: number of clusters to free or -1 for all clusters 744 * 745 * Free @count clusters starting at the cluster @start_vcn in the runlist 746 * described by the attribute @na from the mounted ntfs volume @vol. 747 * 748 * If @count is -1, all clusters from @start_vcn to the end of the runlist 749 * are deallocated. 750 * 751 * On success return the number of deallocated clusters (not counting sparse 752 * clusters) and on error return -1 with errno set to the error code. 753 */ 754 int ntfs_cluster_free(ntfs_volume *vol, ntfs_attr *na, VCN start_vcn, s64 count) 755 { 756 runlist *rl; 757 s64 nr_freed, delta, to_free; 758 759 if (!vol || !vol->lcnbmp_na || !na || start_vcn < 0 || 760 (count < 0 && count != -1)) { 761 ntfs_log_trace("Invalid arguments!\n"); 762 errno = EINVAL; 763 return -1; 764 } 765 ntfs_log_trace("Entering for inode 0x%llx, attr 0x%x, count 0x%llx, " 766 "vcn 0x%llx.\n", (unsigned long long)na->ni->mft_no, 767 na->type, (long long)count, (long long)start_vcn); 768 769 rl = ntfs_attr_find_vcn(na, start_vcn); 770 if (!rl) { 771 if (errno == ENOENT) 772 return 0; 773 else 774 return -1; 775 } 776 777 if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { 778 errno = EIO; 779 return -1; 780 } 781 782 /* Find the starting cluster inside the run that needs freeing. */ 783 delta = start_vcn - rl->vcn; 784 785 /* The number of clusters in this run that need freeing. */ 786 to_free = rl->length - delta; 787 if (count >= 0 && to_free > count) 788 to_free = count; 789 790 if (rl->lcn != LCN_HOLE) { 791 /* Do the actual freeing of the clusters in this run. */ 792 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn + delta, 793 to_free)) 794 return -1; 795 /* We have freed @to_free real clusters. */ 796 nr_freed = to_free; 797 } else { 798 /* No real clusters were freed. */ 799 nr_freed = 0; 800 } 801 802 /* Go to the next run and adjust the number of clusters left to free. */ 803 ++rl; 804 if (count >= 0) 805 count -= to_free; 806 807 /* 808 * Loop over the remaining runs, using @count as a capping value, and 809 * free them. 810 */ 811 for (; rl->length && count != 0; ++rl) { 812 // FIXME: Need to try ntfs_attr_map_runlist() for attribute 813 // list support! (AIA) 814 if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { 815 // FIXME: Eeek! We need rollback! (AIA) 816 ntfs_log_trace("Eeek! invalid lcn (= %lli). Should attempt " 817 "to map runlist! Leaving inconsistent " 818 "metadata!\n", (long long)rl->lcn); 819 errno = EIO; 820 return -1; 821 } 822 823 /* The number of clusters in this run that need freeing. */ 824 to_free = rl->length; 825 if (count >= 0 && to_free > count) 826 to_free = count; 827 828 if (rl->lcn != LCN_HOLE) { 829 /* Do the actual freeing of the clusters in the run. */ 830 if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn, 831 to_free)) { 832 int eo = errno; 833 834 // FIXME: Eeek! We need rollback! (AIA) 835 ntfs_log_trace("Eeek! bitmap clear run failed. " 836 "Leaving inconsistent metadata!\n"); 837 errno = eo; 838 return -1; 839 } 840 /* We have freed @to_free real clusters. */ 841 nr_freed += to_free; 842 } 843 844 if (count >= 0) 845 count -= to_free; 846 } 847 848 if (count != -1 && count != 0) { 849 // FIXME: Eeek! BUG() 850 ntfs_log_trace("Eeek! count still not zero (= %lli). Leaving " 851 "inconsistent metadata!\n", (long long)count); 852 errno = EIO; 853 return -1; 854 } 855 856 /* Done. Return the number of actual clusters that were freed. */ 857 return nr_freed; 858 }