blob: 9eb907cd9a026b1682e8dda65ed97cf79026b9b0
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 | |
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 | |
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 | |
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 | |
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 | |
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 | */ |
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 (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 | |
447 | zone_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 */ |
469 | done_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"); |
487 | switch_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 | } |
529 | done_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 | } |
539 | done_err_ret: |
540 | free(buf); |
541 | if (err) { |
542 | errno = err; |
543 | ntfs_log_perror("Failed to allocate clusters"); |
544 | rl = NULL; |
545 | } |
546 | out: |
547 | ntfs_log_leave("\n"); |
548 | return rl; |
549 | |
550 | wb_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; |
554 | err_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 | */ |
576 | int 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; |
603 | out: |
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 | * ntfs_cluster_free - free clusters on an ntfs volume |
614 | * @vol: mounted ntfs volume on which to free the clusters |
615 | * @na: attribute whose runlist describes the clusters to free |
616 | * @start_vcn: vcn in @rl at which to start freeing clusters |
617 | * @count: number of clusters to free or -1 for all clusters |
618 | * |
619 | * Free @count clusters starting at the cluster @start_vcn in the runlist |
620 | * described by the attribute @na from the mounted ntfs volume @vol. |
621 | * |
622 | * If @count is -1, all clusters from @start_vcn to the end of the runlist |
623 | * are deallocated. |
624 | * |
625 | * On success return the number of deallocated clusters (not counting sparse |
626 | * clusters) and on error return -1 with errno set to the error code. |
627 | */ |
628 | int ntfs_cluster_free(ntfs_volume *vol, ntfs_attr *na, VCN start_vcn, s64 count) |
629 | { |
630 | runlist *rl; |
631 | s64 delta, to_free, nr_freed = 0; |
632 | int ret = -1; |
633 | |
634 | if (!vol || !vol->lcnbmp_na || !na || start_vcn < 0 || |
635 | (count < 0 && count != -1)) { |
636 | ntfs_log_trace("Invalid arguments!\n"); |
637 | errno = EINVAL; |
638 | return -1; |
639 | } |
640 | |
641 | ntfs_log_enter("Entering for inode 0x%llx, attr 0x%x, count 0x%llx, " |
642 | "vcn 0x%llx.\n", (unsigned long long)na->ni->mft_no, |
643 | na->type, (long long)count, (long long)start_vcn); |
644 | |
645 | rl = ntfs_attr_find_vcn(na, start_vcn); |
646 | if (!rl) { |
647 | if (errno == ENOENT) |
648 | ret = 0; |
649 | goto leave; |
650 | } |
651 | |
652 | if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { |
653 | errno = EIO; |
654 | ntfs_log_perror("%s: Unexpected lcn (%lld)", __FUNCTION__, |
655 | (long long)rl->lcn); |
656 | goto leave; |
657 | } |
658 | |
659 | /* Find the starting cluster inside the run that needs freeing. */ |
660 | delta = start_vcn - rl->vcn; |
661 | |
662 | /* The number of clusters in this run that need freeing. */ |
663 | to_free = rl->length - delta; |
664 | if (count >= 0 && to_free > count) |
665 | to_free = count; |
666 | |
667 | if (rl->lcn != LCN_HOLE) { |
668 | /* Do the actual freeing of the clusters in this run. */ |
669 | update_full_status(vol,rl->lcn + delta); |
670 | if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn + delta, |
671 | to_free)) |
672 | goto leave; |
673 | nr_freed = to_free; |
674 | } |
675 | |
676 | /* Go to the next run and adjust the number of clusters left to free. */ |
677 | ++rl; |
678 | if (count >= 0) |
679 | count -= to_free; |
680 | |
681 | /* |
682 | * Loop over the remaining runs, using @count as a capping value, and |
683 | * free them. |
684 | */ |
685 | for (; rl->length && count != 0; ++rl) { |
686 | // FIXME: Need to try ntfs_attr_map_runlist() for attribute |
687 | // list support! (AIA) |
688 | if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { |
689 | // FIXME: Eeek! We need rollback! (AIA) |
690 | errno = EIO; |
691 | ntfs_log_perror("%s: Invalid lcn (%lli)", |
692 | __FUNCTION__, (long long)rl->lcn); |
693 | goto out; |
694 | } |
695 | |
696 | /* The number of clusters in this run that need freeing. */ |
697 | to_free = rl->length; |
698 | if (count >= 0 && to_free > count) |
699 | to_free = count; |
700 | |
701 | if (rl->lcn != LCN_HOLE) { |
702 | update_full_status(vol,rl->lcn); |
703 | if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn, |
704 | to_free)) { |
705 | // FIXME: Eeek! We need rollback! (AIA) |
706 | ntfs_log_perror("%s: Clearing bitmap run failed", |
707 | __FUNCTION__); |
708 | goto out; |
709 | } |
710 | nr_freed += to_free; |
711 | } |
712 | |
713 | if (count >= 0) |
714 | count -= to_free; |
715 | } |
716 | |
717 | if (count != -1 && count != 0) { |
718 | // FIXME: Eeek! BUG() |
719 | errno = EIO; |
720 | ntfs_log_perror("%s: count still not zero (%lld)", __FUNCTION__, |
721 | (long long)count); |
722 | goto out; |
723 | } |
724 | |
725 | ret = nr_freed; |
726 | out: |
727 | vol->free_clusters += nr_freed ; |
728 | if (vol->free_clusters > vol->nr_clusters) |
729 | ntfs_log_error("Too many free clusters (%lld > %lld)!", |
730 | (long long)vol->free_clusters, |
731 | (long long)vol->nr_clusters); |
732 | leave: |
733 | ntfs_log_leave("\n"); |
734 | return ret; |
735 | } |
736 |