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
58 enum {
59 ZONE_MFT = 1,
60 ZONE_DATA1 = 2,
61 ZONE_DATA2 = 4
62 } ;
63
ntfs_cluster_set_zone_pos(LCN start,LCN end,LCN * pos,LCN tc)64 static 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
ntfs_cluster_update_zone_pos(ntfs_volume * vol,u8 zone,LCN tc)74 static 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
update_full_status(ntfs_volume * vol,LCN lcn)95 static 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
max_empty_bit_range(unsigned char * buf,int size)116 static 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
bitmap_writeback(ntfs_volume * vol,s64 pos,s64 size,void * b,u8 * writeback)171 static 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 */
ntfs_cluster_alloc(ntfs_volume * vol,VCN start_vcn,s64 count,LCN start_lcn,const NTFS_CLUSTER_ALLOCATION_ZONES zone)235 runlist *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
449 zone_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 */
471 done_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");
489 switch_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 }
531 done_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 }
541 done_err_ret:
542 free(buf);
543 if (err) {
544 errno = err;
545 ntfs_log_perror("Failed to allocate clusters");
546 rl = NULL;
547 }
548 out:
549 ntfs_log_leave("\n");
550 return rl;
551
552 wb_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;
556 err_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 */
ntfs_cluster_free_from_rl(ntfs_volume * vol,runlist * rl)578 int 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;
605 out:
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
ntfs_cluster_free_basic(ntfs_volume * vol,s64 lcn,s64 count)620 int 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;
642 out:
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 */
ntfs_cluster_free(ntfs_volume * vol,ntfs_attr * na,VCN start_vcn,s64 count)667 int 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;
765 out:
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);
771 leave:
772 ntfs_log_leave("\n");
773 return ret;
774 }
775