Root/
1 | /* |
2 | * lcnalloc.c - Cluster (de)allocation code. Part of the Linux-NTFS project. |
3 | * |
4 | * Copyright (c) 2004-2005 Anton Altaparmakov |
5 | * |
6 | * This program/include file is free software; you can redistribute it and/or |
7 | * modify it under the terms of the GNU General Public License as published |
8 | * by the Free Software Foundation; either version 2 of the License, or |
9 | * (at your option) any later version. |
10 | * |
11 | * This program/include file is distributed in the hope that it will be |
12 | * useful, but WITHOUT ANY WARRANTY; without even the implied warranty |
13 | * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | * GNU General Public License for more details. |
15 | * |
16 | * You should have received a copy of the GNU General Public License |
17 | * along with this program (in the main directory of the Linux-NTFS |
18 | * distribution in the file COPYING); if not, write to the Free Software |
19 | * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
20 | */ |
21 | |
22 | #ifdef NTFS_RW |
23 | |
24 | #include <linux/pagemap.h> |
25 | |
26 | #include "lcnalloc.h" |
27 | #include "debug.h" |
28 | #include "bitmap.h" |
29 | #include "inode.h" |
30 | #include "volume.h" |
31 | #include "attrib.h" |
32 | #include "malloc.h" |
33 | #include "aops.h" |
34 | #include "ntfs.h" |
35 | |
36 | /** |
37 | * ntfs_cluster_free_from_rl_nolock - free clusters from runlist |
38 | * @vol: mounted ntfs volume on which to free the clusters |
39 | * @rl: runlist describing the clusters to free |
40 | * |
41 | * Free all the clusters described by the runlist @rl on the volume @vol. In |
42 | * the case of an error being returned, at least some of the clusters were not |
43 | * freed. |
44 | * |
45 | * Return 0 on success and -errno on error. |
46 | * |
47 | * Locking: - The volume lcn bitmap must be locked for writing on entry and is |
48 | * left locked on return. |
49 | */ |
50 | int ntfs_cluster_free_from_rl_nolock(ntfs_volume *vol, |
51 | const runlist_element *rl) |
52 | { |
53 | struct inode *lcnbmp_vi = vol->lcnbmp_ino; |
54 | int ret = 0; |
55 | |
56 | ntfs_debug("Entering."); |
57 | if (!rl) |
58 | return 0; |
59 | for (; rl->length; rl++) { |
60 | int err; |
61 | |
62 | if (rl->lcn < 0) |
63 | continue; |
64 | err = ntfs_bitmap_clear_run(lcnbmp_vi, rl->lcn, rl->length); |
65 | if (unlikely(err && (!ret || ret == -ENOMEM) && ret != err)) |
66 | ret = err; |
67 | } |
68 | ntfs_debug("Done."); |
69 | return ret; |
70 | } |
71 | |
72 | /** |
73 | * ntfs_cluster_alloc - allocate clusters on an ntfs volume |
74 | * @vol: mounted ntfs volume on which to allocate the clusters |
75 | * @start_vcn: vcn to use for the first allocated cluster |
76 | * @count: number of clusters to allocate |
77 | * @start_lcn: starting lcn at which to allocate the clusters (or -1 if none) |
78 | * @zone: zone from which to allocate the clusters |
79 | * @is_extension: if 'true', this is an attribute extension |
80 | * |
81 | * Allocate @count clusters preferably starting at cluster @start_lcn or at the |
82 | * current allocator position if @start_lcn is -1, on the mounted ntfs volume |
83 | * @vol. @zone is either DATA_ZONE for allocation of normal clusters or |
84 | * MFT_ZONE for allocation of clusters for the master file table, i.e. the |
85 | * $MFT/$DATA attribute. |
86 | * |
87 | * @start_vcn specifies the vcn of the first allocated cluster. This makes |
88 | * merging the resulting runlist with the old runlist easier. |
89 | * |
90 | * If @is_extension is 'true', the caller is allocating clusters to extend an |
91 | * attribute and if it is 'false', the caller is allocating clusters to fill a |
92 | * hole in an attribute. Practically the difference is that if @is_extension |
93 | * is 'true' the returned runlist will be terminated with LCN_ENOENT and if |
94 | * @is_extension is 'false' the runlist will be terminated with |
95 | * LCN_RL_NOT_MAPPED. |
96 | * |
97 | * You need to check the return value with IS_ERR(). If this is false, the |
98 | * function was successful and the return value is a runlist describing the |
99 | * allocated cluster(s). If IS_ERR() is true, the function failed and |
100 | * PTR_ERR() gives you the error code. |
101 | * |
102 | * Notes on the allocation algorithm |
103 | * ================================= |
104 | * |
105 | * There are two data zones. First is the area between the end of the mft zone |
106 | * and the end of the volume, and second is the area between the start of the |
107 | * volume and the start of the mft zone. On unmodified/standard NTFS 1.x |
108 | * volumes, the second data zone does not exist due to the mft zone being |
109 | * expanded to cover the start of the volume in order to reserve space for the |
110 | * mft bitmap attribute. |
111 | * |
112 | * This is not the prettiest function but the complexity stems from the need of |
113 | * implementing the mft vs data zoned approach and from the fact that we have |
114 | * access to the lcn bitmap in portions of up to 8192 bytes at a time, so we |
115 | * need to cope with crossing over boundaries of two buffers. Further, the |
116 | * fact that the allocator allows for caller supplied hints as to the location |
117 | * of where allocation should begin and the fact that the allocator keeps track |
118 | * of where in the data zones the next natural allocation should occur, |
119 | * contribute to the complexity of the function. But it should all be |
120 | * worthwhile, because this allocator should: 1) be a full implementation of |
121 | * the MFT zone approach used by Windows NT, 2) cause reduction in |
122 | * fragmentation, and 3) be speedy in allocations (the code is not optimized |
123 | * for speed, but the algorithm is, so further speed improvements are probably |
124 | * possible). |
125 | * |
126 | * FIXME: We should be monitoring cluster allocation and increment the MFT zone |
127 | * size dynamically but this is something for the future. We will just cause |
128 | * heavier fragmentation by not doing it and I am not even sure Windows would |
129 | * grow the MFT zone dynamically, so it might even be correct not to do this. |
130 | * The overhead in doing dynamic MFT zone expansion would be very large and |
131 | * unlikely worth the effort. (AIA) |
132 | * |
133 | * TODO: I have added in double the required zone position pointer wrap around |
134 | * logic which can be optimized to having only one of the two logic sets. |
135 | * However, having the double logic will work fine, but if we have only one of |
136 | * the sets and we get it wrong somewhere, then we get into trouble, so |
137 | * removing the duplicate logic requires _very_ careful consideration of _all_ |
138 | * possible code paths. So at least for now, I am leaving the double logic - |
139 | * better safe than sorry... (AIA) |
140 | * |
141 | * Locking: - The volume lcn bitmap must be unlocked on entry and is unlocked |
142 | * on return. |
143 | * - This function takes the volume lcn bitmap lock for writing and |
144 | * modifies the bitmap contents. |
145 | */ |
146 | runlist_element *ntfs_cluster_alloc(ntfs_volume *vol, const VCN start_vcn, |
147 | const s64 count, const LCN start_lcn, |
148 | const NTFS_CLUSTER_ALLOCATION_ZONES zone, |
149 | const bool is_extension) |
150 | { |
151 | LCN zone_start, zone_end, bmp_pos, bmp_initial_pos, last_read_pos, lcn; |
152 | LCN prev_lcn = 0, prev_run_len = 0, mft_zone_size; |
153 | s64 clusters; |
154 | loff_t i_size; |
155 | struct inode *lcnbmp_vi; |
156 | runlist_element *rl = NULL; |
157 | struct address_space *mapping; |
158 | struct page *page = NULL; |
159 | u8 *buf, *byte; |
160 | int err = 0, rlpos, rlsize, buf_size; |
161 | u8 pass, done_zones, search_zone, need_writeback = 0, bit; |
162 | |
163 | ntfs_debug("Entering for start_vcn 0x%llx, count 0x%llx, start_lcn " |
164 | "0x%llx, zone %s_ZONE.", (unsigned long long)start_vcn, |
165 | (unsigned long long)count, |
166 | (unsigned long long)start_lcn, |
167 | zone == MFT_ZONE ? "MFT" : "DATA"); |
168 | BUG_ON(!vol); |
169 | lcnbmp_vi = vol->lcnbmp_ino; |
170 | BUG_ON(!lcnbmp_vi); |
171 | BUG_ON(start_vcn < 0); |
172 | BUG_ON(count < 0); |
173 | BUG_ON(start_lcn < -1); |
174 | BUG_ON(zone < FIRST_ZONE); |
175 | BUG_ON(zone > LAST_ZONE); |
176 | |
177 | /* Return NULL if @count is zero. */ |
178 | if (!count) |
179 | return NULL; |
180 | /* Take the lcnbmp lock for writing. */ |
181 | down_write(&vol->lcnbmp_lock); |
182 | /* |
183 | * If no specific @start_lcn was requested, use the current data zone |
184 | * position, otherwise use the requested @start_lcn but make sure it |
185 | * lies outside the mft zone. Also set done_zones to 0 (no zones done) |
186 | * and pass depending on whether we are starting inside a zone (1) or |
187 | * at the beginning of a zone (2). If requesting from the MFT_ZONE, |
188 | * we either start at the current position within the mft zone or at |
189 | * the specified position. If the latter is out of bounds then we start |
190 | * at the beginning of the MFT_ZONE. |
191 | */ |
192 | done_zones = 0; |
193 | pass = 1; |
194 | /* |
195 | * zone_start and zone_end are the current search range. search_zone |
196 | * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of |
197 | * volume) and 4 for data zone 2 (start of volume till start of mft |
198 | * zone). |
199 | */ |
200 | zone_start = start_lcn; |
201 | if (zone_start < 0) { |
202 | if (zone == DATA_ZONE) |
203 | zone_start = vol->data1_zone_pos; |
204 | else |
205 | zone_start = vol->mft_zone_pos; |
206 | if (!zone_start) { |
207 | /* |
208 | * Zone starts at beginning of volume which means a |
209 | * single pass is sufficient. |
210 | */ |
211 | pass = 2; |
212 | } |
213 | } else if (zone == DATA_ZONE && zone_start >= vol->mft_zone_start && |
214 | zone_start < vol->mft_zone_end) { |
215 | zone_start = vol->mft_zone_end; |
216 | /* |
217 | * Starting at beginning of data1_zone which means a single |
218 | * pass in this zone is sufficient. |
219 | */ |
220 | pass = 2; |
221 | } else if (zone == MFT_ZONE && (zone_start < vol->mft_zone_start || |
222 | zone_start >= vol->mft_zone_end)) { |
223 | zone_start = vol->mft_lcn; |
224 | if (!vol->mft_zone_end) |
225 | zone_start = 0; |
226 | /* |
227 | * Starting at beginning of volume which means a single pass |
228 | * is sufficient. |
229 | */ |
230 | pass = 2; |
231 | } |
232 | if (zone == MFT_ZONE) { |
233 | zone_end = vol->mft_zone_end; |
234 | search_zone = 1; |
235 | } else /* if (zone == DATA_ZONE) */ { |
236 | /* Skip searching the mft zone. */ |
237 | done_zones |= 1; |
238 | if (zone_start >= vol->mft_zone_end) { |
239 | zone_end = vol->nr_clusters; |
240 | search_zone = 2; |
241 | } else { |
242 | zone_end = vol->mft_zone_start; |
243 | search_zone = 4; |
244 | } |
245 | } |
246 | /* |
247 | * bmp_pos is the current bit position inside the bitmap. We use |
248 | * bmp_initial_pos to determine whether or not to do a zone switch. |
249 | */ |
250 | bmp_pos = bmp_initial_pos = zone_start; |
251 | |
252 | /* Loop until all clusters are allocated, i.e. clusters == 0. */ |
253 | clusters = count; |
254 | rlpos = rlsize = 0; |
255 | mapping = lcnbmp_vi->i_mapping; |
256 | i_size = i_size_read(lcnbmp_vi); |
257 | while (1) { |
258 | ntfs_debug("Start of outer while loop: done_zones 0x%x, " |
259 | "search_zone %i, pass %i, zone_start 0x%llx, " |
260 | "zone_end 0x%llx, bmp_initial_pos 0x%llx, " |
261 | "bmp_pos 0x%llx, rlpos %i, rlsize %i.", |
262 | done_zones, search_zone, pass, |
263 | (unsigned long long)zone_start, |
264 | (unsigned long long)zone_end, |
265 | (unsigned long long)bmp_initial_pos, |
266 | (unsigned long long)bmp_pos, rlpos, rlsize); |
267 | /* Loop until we run out of free clusters. */ |
268 | last_read_pos = bmp_pos >> 3; |
269 | ntfs_debug("last_read_pos 0x%llx.", |
270 | (unsigned long long)last_read_pos); |
271 | if (last_read_pos > i_size) { |
272 | ntfs_debug("End of attribute reached. " |
273 | "Skipping to zone_pass_done."); |
274 | goto zone_pass_done; |
275 | } |
276 | if (likely(page)) { |
277 | if (need_writeback) { |
278 | ntfs_debug("Marking page dirty."); |
279 | flush_dcache_page(page); |
280 | set_page_dirty(page); |
281 | need_writeback = 0; |
282 | } |
283 | ntfs_unmap_page(page); |
284 | } |
285 | page = ntfs_map_page(mapping, last_read_pos >> |
286 | PAGE_CACHE_SHIFT); |
287 | if (IS_ERR(page)) { |
288 | err = PTR_ERR(page); |
289 | ntfs_error(vol->sb, "Failed to map page."); |
290 | goto out; |
291 | } |
292 | buf_size = last_read_pos & ~PAGE_CACHE_MASK; |
293 | buf = page_address(page) + buf_size; |
294 | buf_size = PAGE_CACHE_SIZE - buf_size; |
295 | if (unlikely(last_read_pos + buf_size > i_size)) |
296 | buf_size = i_size - last_read_pos; |
297 | buf_size <<= 3; |
298 | lcn = bmp_pos & 7; |
299 | bmp_pos &= ~(LCN)7; |
300 | ntfs_debug("Before inner while loop: buf_size %i, lcn 0x%llx, " |
301 | "bmp_pos 0x%llx, need_writeback %i.", buf_size, |
302 | (unsigned long long)lcn, |
303 | (unsigned long long)bmp_pos, need_writeback); |
304 | while (lcn < buf_size && lcn + bmp_pos < zone_end) { |
305 | byte = buf + (lcn >> 3); |
306 | ntfs_debug("In inner while loop: buf_size %i, " |
307 | "lcn 0x%llx, bmp_pos 0x%llx, " |
308 | "need_writeback %i, byte ofs 0x%x, " |
309 | "*byte 0x%x.", buf_size, |
310 | (unsigned long long)lcn, |
311 | (unsigned long long)bmp_pos, |
312 | need_writeback, |
313 | (unsigned int)(lcn >> 3), |
314 | (unsigned int)*byte); |
315 | /* Skip full bytes. */ |
316 | if (*byte == 0xff) { |
317 | lcn = (lcn + 8) & ~(LCN)7; |
318 | ntfs_debug("Continuing while loop 1."); |
319 | continue; |
320 | } |
321 | bit = 1 << (lcn & 7); |
322 | ntfs_debug("bit 0x%x.", bit); |
323 | /* If the bit is already set, go onto the next one. */ |
324 | if (*byte & bit) { |
325 | lcn++; |
326 | ntfs_debug("Continuing while loop 2."); |
327 | continue; |
328 | } |
329 | /* |
330 | * Allocate more memory if needed, including space for |
331 | * the terminator element. |
332 | * ntfs_malloc_nofs() operates on whole pages only. |
333 | */ |
334 | if ((rlpos + 2) * sizeof(*rl) > rlsize) { |
335 | runlist_element *rl2; |
336 | |
337 | ntfs_debug("Reallocating memory."); |
338 | if (!rl) |
339 | ntfs_debug("First free bit is at LCN " |
340 | "0x%llx.", |
341 | (unsigned long long) |
342 | (lcn + bmp_pos)); |
343 | rl2 = ntfs_malloc_nofs(rlsize + (int)PAGE_SIZE); |
344 | if (unlikely(!rl2)) { |
345 | err = -ENOMEM; |
346 | ntfs_error(vol->sb, "Failed to " |
347 | "allocate memory."); |
348 | goto out; |
349 | } |
350 | memcpy(rl2, rl, rlsize); |
351 | ntfs_free(rl); |
352 | rl = rl2; |
353 | rlsize += PAGE_SIZE; |
354 | ntfs_debug("Reallocated memory, rlsize 0x%x.", |
355 | rlsize); |
356 | } |
357 | /* Allocate the bitmap bit. */ |
358 | *byte |= bit; |
359 | /* We need to write this bitmap page to disk. */ |
360 | need_writeback = 1; |
361 | ntfs_debug("*byte 0x%x, need_writeback is set.", |
362 | (unsigned int)*byte); |
363 | /* |
364 | * Coalesce with previous run if adjacent LCNs. |
365 | * Otherwise, append a new run. |
366 | */ |
367 | ntfs_debug("Adding run (lcn 0x%llx, len 0x%llx), " |
368 | "prev_lcn 0x%llx, lcn 0x%llx, " |
369 | "bmp_pos 0x%llx, prev_run_len 0x%llx, " |
370 | "rlpos %i.", |
371 | (unsigned long long)(lcn + bmp_pos), |
372 | 1ULL, (unsigned long long)prev_lcn, |
373 | (unsigned long long)lcn, |
374 | (unsigned long long)bmp_pos, |
375 | (unsigned long long)prev_run_len, |
376 | rlpos); |
377 | if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) { |
378 | ntfs_debug("Coalescing to run (lcn 0x%llx, " |
379 | "len 0x%llx).", |
380 | (unsigned long long) |
381 | rl[rlpos - 1].lcn, |
382 | (unsigned long long) |
383 | rl[rlpos - 1].length); |
384 | rl[rlpos - 1].length = ++prev_run_len; |
385 | ntfs_debug("Run now (lcn 0x%llx, len 0x%llx), " |
386 | "prev_run_len 0x%llx.", |
387 | (unsigned long long) |
388 | rl[rlpos - 1].lcn, |
389 | (unsigned long long) |
390 | rl[rlpos - 1].length, |
391 | (unsigned long long) |
392 | prev_run_len); |
393 | } else { |
394 | if (likely(rlpos)) { |
395 | ntfs_debug("Adding new run, (previous " |
396 | "run lcn 0x%llx, " |
397 | "len 0x%llx).", |
398 | (unsigned long long) |
399 | rl[rlpos - 1].lcn, |
400 | (unsigned long long) |
401 | rl[rlpos - 1].length); |
402 | rl[rlpos].vcn = rl[rlpos - 1].vcn + |
403 | prev_run_len; |
404 | } else { |
405 | ntfs_debug("Adding new run, is first " |
406 | "run."); |
407 | rl[rlpos].vcn = start_vcn; |
408 | } |
409 | rl[rlpos].lcn = prev_lcn = lcn + bmp_pos; |
410 | rl[rlpos].length = prev_run_len = 1; |
411 | rlpos++; |
412 | } |
413 | /* Done? */ |
414 | if (!--clusters) { |
415 | LCN tc; |
416 | /* |
417 | * Update the current zone position. Positions |
418 | * of already scanned zones have been updated |
419 | * during the respective zone switches. |
420 | */ |
421 | tc = lcn + bmp_pos + 1; |
422 | ntfs_debug("Done. Updating current zone " |
423 | "position, tc 0x%llx, " |
424 | "search_zone %i.", |
425 | (unsigned long long)tc, |
426 | search_zone); |
427 | switch (search_zone) { |
428 | case 1: |
429 | ntfs_debug("Before checks, " |
430 | "vol->mft_zone_pos " |
431 | "0x%llx.", |
432 | (unsigned long long) |
433 | vol->mft_zone_pos); |
434 | if (tc >= vol->mft_zone_end) { |
435 | vol->mft_zone_pos = |
436 | vol->mft_lcn; |
437 | if (!vol->mft_zone_end) |
438 | vol->mft_zone_pos = 0; |
439 | } else if ((bmp_initial_pos >= |
440 | vol->mft_zone_pos || |
441 | tc > vol->mft_zone_pos) |
442 | && tc >= vol->mft_lcn) |
443 | vol->mft_zone_pos = tc; |
444 | ntfs_debug("After checks, " |
445 | "vol->mft_zone_pos " |
446 | "0x%llx.", |
447 | (unsigned long long) |
448 | vol->mft_zone_pos); |
449 | break; |
450 | case 2: |
451 | ntfs_debug("Before checks, " |
452 | "vol->data1_zone_pos " |
453 | "0x%llx.", |
454 | (unsigned long long) |
455 | vol->data1_zone_pos); |
456 | if (tc >= vol->nr_clusters) |
457 | vol->data1_zone_pos = |
458 | vol->mft_zone_end; |
459 | else if ((bmp_initial_pos >= |
460 | vol->data1_zone_pos || |
461 | tc > vol->data1_zone_pos) |
462 | && tc >= vol->mft_zone_end) |
463 | vol->data1_zone_pos = tc; |
464 | ntfs_debug("After checks, " |
465 | "vol->data1_zone_pos " |
466 | "0x%llx.", |
467 | (unsigned long long) |
468 | vol->data1_zone_pos); |
469 | break; |
470 | case 4: |
471 | ntfs_debug("Before checks, " |
472 | "vol->data2_zone_pos " |
473 | "0x%llx.", |
474 | (unsigned long long) |
475 | vol->data2_zone_pos); |
476 | if (tc >= vol->mft_zone_start) |
477 | vol->data2_zone_pos = 0; |
478 | else if (bmp_initial_pos >= |
479 | vol->data2_zone_pos || |
480 | tc > vol->data2_zone_pos) |
481 | vol->data2_zone_pos = tc; |
482 | ntfs_debug("After checks, " |
483 | "vol->data2_zone_pos " |
484 | "0x%llx.", |
485 | (unsigned long long) |
486 | vol->data2_zone_pos); |
487 | break; |
488 | default: |
489 | BUG(); |
490 | } |
491 | ntfs_debug("Finished. Going to out."); |
492 | goto out; |
493 | } |
494 | lcn++; |
495 | } |
496 | bmp_pos += buf_size; |
497 | ntfs_debug("After inner while loop: buf_size 0x%x, lcn " |
498 | "0x%llx, bmp_pos 0x%llx, need_writeback %i.", |
499 | buf_size, (unsigned long long)lcn, |
500 | (unsigned long long)bmp_pos, need_writeback); |
501 | if (bmp_pos < zone_end) { |
502 | ntfs_debug("Continuing outer while loop, " |
503 | "bmp_pos 0x%llx, zone_end 0x%llx.", |
504 | (unsigned long long)bmp_pos, |
505 | (unsigned long long)zone_end); |
506 | continue; |
507 | } |
508 | zone_pass_done: /* Finished with the current zone pass. */ |
509 | ntfs_debug("At zone_pass_done, pass %i.", pass); |
510 | if (pass == 1) { |
511 | /* |
512 | * Now do pass 2, scanning the first part of the zone |
513 | * we omitted in pass 1. |
514 | */ |
515 | pass = 2; |
516 | zone_end = zone_start; |
517 | switch (search_zone) { |
518 | case 1: /* mft_zone */ |
519 | zone_start = vol->mft_zone_start; |
520 | break; |
521 | case 2: /* data1_zone */ |
522 | zone_start = vol->mft_zone_end; |
523 | break; |
524 | case 4: /* data2_zone */ |
525 | zone_start = 0; |
526 | break; |
527 | default: |
528 | BUG(); |
529 | } |
530 | /* Sanity check. */ |
531 | if (zone_end < zone_start) |
532 | zone_end = zone_start; |
533 | bmp_pos = zone_start; |
534 | ntfs_debug("Continuing outer while loop, pass 2, " |
535 | "zone_start 0x%llx, zone_end 0x%llx, " |
536 | "bmp_pos 0x%llx.", |
537 | (unsigned long long)zone_start, |
538 | (unsigned long long)zone_end, |
539 | (unsigned long long)bmp_pos); |
540 | continue; |
541 | } /* pass == 2 */ |
542 | done_zones_check: |
543 | ntfs_debug("At done_zones_check, search_zone %i, done_zones " |
544 | "before 0x%x, done_zones after 0x%x.", |
545 | search_zone, done_zones, |
546 | done_zones | search_zone); |
547 | done_zones |= search_zone; |
548 | if (done_zones < 7) { |
549 | ntfs_debug("Switching zone."); |
550 | /* Now switch to the next zone we haven't done yet. */ |
551 | pass = 1; |
552 | switch (search_zone) { |
553 | case 1: |
554 | ntfs_debug("Switching from mft zone to data1 " |
555 | "zone."); |
556 | /* Update mft zone position. */ |
557 | if (rlpos) { |
558 | LCN tc; |
559 | |
560 | ntfs_debug("Before checks, " |
561 | "vol->mft_zone_pos " |
562 | "0x%llx.", |
563 | (unsigned long long) |
564 | vol->mft_zone_pos); |
565 | tc = rl[rlpos - 1].lcn + |
566 | rl[rlpos - 1].length; |
567 | if (tc >= vol->mft_zone_end) { |
568 | vol->mft_zone_pos = |
569 | vol->mft_lcn; |
570 | if (!vol->mft_zone_end) |
571 | vol->mft_zone_pos = 0; |
572 | } else if ((bmp_initial_pos >= |
573 | vol->mft_zone_pos || |
574 | tc > vol->mft_zone_pos) |
575 | && tc >= vol->mft_lcn) |
576 | vol->mft_zone_pos = tc; |
577 | ntfs_debug("After checks, " |
578 | "vol->mft_zone_pos " |
579 | "0x%llx.", |
580 | (unsigned long long) |
581 | vol->mft_zone_pos); |
582 | } |
583 | /* Switch from mft zone to data1 zone. */ |
584 | switch_to_data1_zone: search_zone = 2; |
585 | zone_start = bmp_initial_pos = |
586 | vol->data1_zone_pos; |
587 | zone_end = vol->nr_clusters; |
588 | if (zone_start == vol->mft_zone_end) |
589 | pass = 2; |
590 | if (zone_start >= zone_end) { |
591 | vol->data1_zone_pos = zone_start = |
592 | vol->mft_zone_end; |
593 | pass = 2; |
594 | } |
595 | break; |
596 | case 2: |
597 | ntfs_debug("Switching from data1 zone to " |
598 | "data2 zone."); |
599 | /* Update data1 zone position. */ |
600 | if (rlpos) { |
601 | LCN tc; |
602 | |
603 | ntfs_debug("Before checks, " |
604 | "vol->data1_zone_pos " |
605 | "0x%llx.", |
606 | (unsigned long long) |
607 | vol->data1_zone_pos); |
608 | tc = rl[rlpos - 1].lcn + |
609 | rl[rlpos - 1].length; |
610 | if (tc >= vol->nr_clusters) |
611 | vol->data1_zone_pos = |
612 | vol->mft_zone_end; |
613 | else if ((bmp_initial_pos >= |
614 | vol->data1_zone_pos || |
615 | tc > vol->data1_zone_pos) |
616 | && tc >= vol->mft_zone_end) |
617 | vol->data1_zone_pos = tc; |
618 | ntfs_debug("After checks, " |
619 | "vol->data1_zone_pos " |
620 | "0x%llx.", |
621 | (unsigned long long) |
622 | vol->data1_zone_pos); |
623 | } |
624 | /* Switch from data1 zone to data2 zone. */ |
625 | search_zone = 4; |
626 | zone_start = bmp_initial_pos = |
627 | vol->data2_zone_pos; |
628 | zone_end = vol->mft_zone_start; |
629 | if (!zone_start) |
630 | pass = 2; |
631 | if (zone_start >= zone_end) { |
632 | vol->data2_zone_pos = zone_start = |
633 | bmp_initial_pos = 0; |
634 | pass = 2; |
635 | } |
636 | break; |
637 | case 4: |
638 | ntfs_debug("Switching from data2 zone to " |
639 | "data1 zone."); |
640 | /* Update data2 zone position. */ |
641 | if (rlpos) { |
642 | LCN tc; |
643 | |
644 | ntfs_debug("Before checks, " |
645 | "vol->data2_zone_pos " |
646 | "0x%llx.", |
647 | (unsigned long long) |
648 | vol->data2_zone_pos); |
649 | tc = rl[rlpos - 1].lcn + |
650 | rl[rlpos - 1].length; |
651 | if (tc >= vol->mft_zone_start) |
652 | vol->data2_zone_pos = 0; |
653 | else if (bmp_initial_pos >= |
654 | vol->data2_zone_pos || |
655 | tc > vol->data2_zone_pos) |
656 | vol->data2_zone_pos = tc; |
657 | ntfs_debug("After checks, " |
658 | "vol->data2_zone_pos " |
659 | "0x%llx.", |
660 | (unsigned long long) |
661 | vol->data2_zone_pos); |
662 | } |
663 | /* Switch from data2 zone to data1 zone. */ |
664 | goto switch_to_data1_zone; |
665 | default: |
666 | BUG(); |
667 | } |
668 | ntfs_debug("After zone switch, search_zone %i, " |
669 | "pass %i, bmp_initial_pos 0x%llx, " |
670 | "zone_start 0x%llx, zone_end 0x%llx.", |
671 | search_zone, pass, |
672 | (unsigned long long)bmp_initial_pos, |
673 | (unsigned long long)zone_start, |
674 | (unsigned long long)zone_end); |
675 | bmp_pos = zone_start; |
676 | if (zone_start == zone_end) { |
677 | ntfs_debug("Empty zone, going to " |
678 | "done_zones_check."); |
679 | /* Empty zone. Don't bother searching it. */ |
680 | goto done_zones_check; |
681 | } |
682 | ntfs_debug("Continuing outer while loop."); |
683 | continue; |
684 | } /* done_zones == 7 */ |
685 | ntfs_debug("All zones are finished."); |
686 | /* |
687 | * All zones are finished! If DATA_ZONE, shrink mft zone. If |
688 | * MFT_ZONE, we have really run out of space. |
689 | */ |
690 | mft_zone_size = vol->mft_zone_end - vol->mft_zone_start; |
691 | ntfs_debug("vol->mft_zone_start 0x%llx, vol->mft_zone_end " |
692 | "0x%llx, mft_zone_size 0x%llx.", |
693 | (unsigned long long)vol->mft_zone_start, |
694 | (unsigned long long)vol->mft_zone_end, |
695 | (unsigned long long)mft_zone_size); |
696 | if (zone == MFT_ZONE || mft_zone_size <= 0) { |
697 | ntfs_debug("No free clusters left, going to out."); |
698 | /* Really no more space left on device. */ |
699 | err = -ENOSPC; |
700 | goto out; |
701 | } /* zone == DATA_ZONE && mft_zone_size > 0 */ |
702 | ntfs_debug("Shrinking mft zone."); |
703 | zone_end = vol->mft_zone_end; |
704 | mft_zone_size >>= 1; |
705 | if (mft_zone_size > 0) |
706 | vol->mft_zone_end = vol->mft_zone_start + mft_zone_size; |
707 | else /* mft zone and data2 zone no longer exist. */ |
708 | vol->data2_zone_pos = vol->mft_zone_start = |
709 | vol->mft_zone_end = 0; |
710 | if (vol->mft_zone_pos >= vol->mft_zone_end) { |
711 | vol->mft_zone_pos = vol->mft_lcn; |
712 | if (!vol->mft_zone_end) |
713 | vol->mft_zone_pos = 0; |
714 | } |
715 | bmp_pos = zone_start = bmp_initial_pos = |
716 | vol->data1_zone_pos = vol->mft_zone_end; |
717 | search_zone = 2; |
718 | pass = 2; |
719 | done_zones &= ~2; |
720 | ntfs_debug("After shrinking mft zone, mft_zone_size 0x%llx, " |
721 | "vol->mft_zone_start 0x%llx, " |
722 | "vol->mft_zone_end 0x%llx, " |
723 | "vol->mft_zone_pos 0x%llx, search_zone 2, " |
724 | "pass 2, dones_zones 0x%x, zone_start 0x%llx, " |
725 | "zone_end 0x%llx, vol->data1_zone_pos 0x%llx, " |
726 | "continuing outer while loop.", |
727 | (unsigned long long)mft_zone_size, |
728 | (unsigned long long)vol->mft_zone_start, |
729 | (unsigned long long)vol->mft_zone_end, |
730 | (unsigned long long)vol->mft_zone_pos, |
731 | done_zones, (unsigned long long)zone_start, |
732 | (unsigned long long)zone_end, |
733 | (unsigned long long)vol->data1_zone_pos); |
734 | } |
735 | ntfs_debug("After outer while loop."); |
736 | out: |
737 | ntfs_debug("At out."); |
738 | /* Add runlist terminator element. */ |
739 | if (likely(rl)) { |
740 | rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; |
741 | rl[rlpos].lcn = is_extension ? LCN_ENOENT : LCN_RL_NOT_MAPPED; |
742 | rl[rlpos].length = 0; |
743 | } |
744 | if (likely(page && !IS_ERR(page))) { |
745 | if (need_writeback) { |
746 | ntfs_debug("Marking page dirty."); |
747 | flush_dcache_page(page); |
748 | set_page_dirty(page); |
749 | need_writeback = 0; |
750 | } |
751 | ntfs_unmap_page(page); |
752 | } |
753 | if (likely(!err)) { |
754 | up_write(&vol->lcnbmp_lock); |
755 | ntfs_debug("Done."); |
756 | return rl; |
757 | } |
758 | ntfs_error(vol->sb, "Failed to allocate clusters, aborting " |
759 | "(error %i).", err); |
760 | if (rl) { |
761 | int err2; |
762 | |
763 | if (err == -ENOSPC) |
764 | ntfs_debug("Not enough space to complete allocation, " |
765 | "err -ENOSPC, first free lcn 0x%llx, " |
766 | "could allocate up to 0x%llx " |
767 | "clusters.", |
768 | (unsigned long long)rl[0].lcn, |
769 | (unsigned long long)(count - clusters)); |
770 | /* Deallocate all allocated clusters. */ |
771 | ntfs_debug("Attempting rollback..."); |
772 | err2 = ntfs_cluster_free_from_rl_nolock(vol, rl); |
773 | if (err2) { |
774 | ntfs_error(vol->sb, "Failed to rollback (error %i). " |
775 | "Leaving inconsistent metadata! " |
776 | "Unmount and run chkdsk.", err2); |
777 | NVolSetErrors(vol); |
778 | } |
779 | /* Free the runlist. */ |
780 | ntfs_free(rl); |
781 | } else if (err == -ENOSPC) |
782 | ntfs_debug("No space left at all, err = -ENOSPC, first free " |
783 | "lcn = 0x%llx.", |
784 | (long long)vol->data1_zone_pos); |
785 | up_write(&vol->lcnbmp_lock); |
786 | return ERR_PTR(err); |
787 | } |
788 | |
789 | /** |
790 | * __ntfs_cluster_free - free clusters on an ntfs volume |
791 | * @ni: ntfs inode whose runlist describes the clusters to free |
792 | * @start_vcn: vcn in the runlist of @ni at which to start freeing clusters |
793 | * @count: number of clusters to free or -1 for all clusters |
794 | * @ctx: active attribute search context if present or NULL if not |
795 | * @is_rollback: true if this is a rollback operation |
796 | * |
797 | * Free @count clusters starting at the cluster @start_vcn in the runlist |
798 | * described by the vfs inode @ni. |
799 | * |
800 | * If @count is -1, all clusters from @start_vcn to the end of the runlist are |
801 | * deallocated. Thus, to completely free all clusters in a runlist, use |
802 | * @start_vcn = 0 and @count = -1. |
803 | * |
804 | * If @ctx is specified, it is an active search context of @ni and its base mft |
805 | * record. This is needed when __ntfs_cluster_free() encounters unmapped |
806 | * runlist fragments and allows their mapping. If you do not have the mft |
807 | * record mapped, you can specify @ctx as NULL and __ntfs_cluster_free() will |
808 | * perform the necessary mapping and unmapping. |
809 | * |
810 | * Note, __ntfs_cluster_free() saves the state of @ctx on entry and restores it |
811 | * before returning. Thus, @ctx will be left pointing to the same attribute on |
812 | * return as on entry. However, the actual pointers in @ctx may point to |
813 | * different memory locations on return, so you must remember to reset any |
814 | * cached pointers from the @ctx, i.e. after the call to __ntfs_cluster_free(), |
815 | * you will probably want to do: |
816 | * m = ctx->mrec; |
817 | * a = ctx->attr; |
818 | * Assuming you cache ctx->attr in a variable @a of type ATTR_RECORD * and that |
819 | * you cache ctx->mrec in a variable @m of type MFT_RECORD *. |
820 | * |
821 | * @is_rollback should always be 'false', it is for internal use to rollback |
822 | * errors. You probably want to use ntfs_cluster_free() instead. |
823 | * |
824 | * Note, __ntfs_cluster_free() does not modify the runlist, so you have to |
825 | * remove from the runlist or mark sparse the freed runs later. |
826 | * |
827 | * Return the number of deallocated clusters (not counting sparse ones) on |
828 | * success and -errno on error. |
829 | * |
830 | * WARNING: If @ctx is supplied, regardless of whether success or failure is |
831 | * returned, you need to check IS_ERR(@ctx->mrec) and if 'true' the @ctx |
832 | * is no longer valid, i.e. you need to either call |
833 | * ntfs_attr_reinit_search_ctx() or ntfs_attr_put_search_ctx() on it. |
834 | * In that case PTR_ERR(@ctx->mrec) will give you the error code for |
835 | * why the mapping of the old inode failed. |
836 | * |
837 | * Locking: - The runlist described by @ni must be locked for writing on entry |
838 | * and is locked on return. Note the runlist may be modified when |
839 | * needed runlist fragments need to be mapped. |
840 | * - The volume lcn bitmap must be unlocked on entry and is unlocked |
841 | * on return. |
842 | * - This function takes the volume lcn bitmap lock for writing and |
843 | * modifies the bitmap contents. |
844 | * - If @ctx is NULL, the base mft record of @ni must not be mapped on |
845 | * entry and it will be left unmapped on return. |
846 | * - If @ctx is not NULL, the base mft record must be mapped on entry |
847 | * and it will be left mapped on return. |
848 | */ |
849 | s64 __ntfs_cluster_free(ntfs_inode *ni, const VCN start_vcn, s64 count, |
850 | ntfs_attr_search_ctx *ctx, const bool is_rollback) |
851 | { |
852 | s64 delta, to_free, total_freed, real_freed; |
853 | ntfs_volume *vol; |
854 | struct inode *lcnbmp_vi; |
855 | runlist_element *rl; |
856 | int err; |
857 | |
858 | BUG_ON(!ni); |
859 | ntfs_debug("Entering for i_ino 0x%lx, start_vcn 0x%llx, count " |
860 | "0x%llx.%s", ni->mft_no, (unsigned long long)start_vcn, |
861 | (unsigned long long)count, |
862 | is_rollback ? " (rollback)" : ""); |
863 | vol = ni->vol; |
864 | lcnbmp_vi = vol->lcnbmp_ino; |
865 | BUG_ON(!lcnbmp_vi); |
866 | BUG_ON(start_vcn < 0); |
867 | BUG_ON(count < -1); |
868 | /* |
869 | * Lock the lcn bitmap for writing but only if not rolling back. We |
870 | * must hold the lock all the way including through rollback otherwise |
871 | * rollback is not possible because once we have cleared a bit and |
872 | * dropped the lock, anyone could have set the bit again, thus |
873 | * allocating the cluster for another use. |
874 | */ |
875 | if (likely(!is_rollback)) |
876 | down_write(&vol->lcnbmp_lock); |
877 | |
878 | total_freed = real_freed = 0; |
879 | |
880 | rl = ntfs_attr_find_vcn_nolock(ni, start_vcn, ctx); |
881 | if (IS_ERR(rl)) { |
882 | if (!is_rollback) |
883 | ntfs_error(vol->sb, "Failed to find first runlist " |
884 | "element (error %li), aborting.", |
885 | PTR_ERR(rl)); |
886 | err = PTR_ERR(rl); |
887 | goto err_out; |
888 | } |
889 | if (unlikely(rl->lcn < LCN_HOLE)) { |
890 | if (!is_rollback) |
891 | ntfs_error(vol->sb, "First runlist element has " |
892 | "invalid lcn, aborting."); |
893 | err = -EIO; |
894 | goto err_out; |
895 | } |
896 | /* Find the starting cluster inside the run that needs freeing. */ |
897 | delta = start_vcn - rl->vcn; |
898 | |
899 | /* The number of clusters in this run that need freeing. */ |
900 | to_free = rl->length - delta; |
901 | if (count >= 0 && to_free > count) |
902 | to_free = count; |
903 | |
904 | if (likely(rl->lcn >= 0)) { |
905 | /* Do the actual freeing of the clusters in this run. */ |
906 | err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn + delta, |
907 | to_free, likely(!is_rollback) ? 0 : 1); |
908 | if (unlikely(err)) { |
909 | if (!is_rollback) |
910 | ntfs_error(vol->sb, "Failed to clear first run " |
911 | "(error %i), aborting.", err); |
912 | goto err_out; |
913 | } |
914 | /* We have freed @to_free real clusters. */ |
915 | real_freed = to_free; |
916 | }; |
917 | /* Go to the next run and adjust the number of clusters left to free. */ |
918 | ++rl; |
919 | if (count >= 0) |
920 | count -= to_free; |
921 | |
922 | /* Keep track of the total "freed" clusters, including sparse ones. */ |
923 | total_freed = to_free; |
924 | /* |
925 | * Loop over the remaining runs, using @count as a capping value, and |
926 | * free them. |
927 | */ |
928 | for (; rl->length && count != 0; ++rl) { |
929 | if (unlikely(rl->lcn < LCN_HOLE)) { |
930 | VCN vcn; |
931 | |
932 | /* Attempt to map runlist. */ |
933 | vcn = rl->vcn; |
934 | rl = ntfs_attr_find_vcn_nolock(ni, vcn, ctx); |
935 | if (IS_ERR(rl)) { |
936 | err = PTR_ERR(rl); |
937 | if (!is_rollback) |
938 | ntfs_error(vol->sb, "Failed to map " |
939 | "runlist fragment or " |
940 | "failed to find " |
941 | "subsequent runlist " |
942 | "element."); |
943 | goto err_out; |
944 | } |
945 | if (unlikely(rl->lcn < LCN_HOLE)) { |
946 | if (!is_rollback) |
947 | ntfs_error(vol->sb, "Runlist element " |
948 | "has invalid lcn " |
949 | "(0x%llx).", |
950 | (unsigned long long) |
951 | rl->lcn); |
952 | err = -EIO; |
953 | goto err_out; |
954 | } |
955 | } |
956 | /* The number of clusters in this run that need freeing. */ |
957 | to_free = rl->length; |
958 | if (count >= 0 && to_free > count) |
959 | to_free = count; |
960 | |
961 | if (likely(rl->lcn >= 0)) { |
962 | /* Do the actual freeing of the clusters in the run. */ |
963 | err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn, |
964 | to_free, likely(!is_rollback) ? 0 : 1); |
965 | if (unlikely(err)) { |
966 | if (!is_rollback) |
967 | ntfs_error(vol->sb, "Failed to clear " |
968 | "subsequent run."); |
969 | goto err_out; |
970 | } |
971 | /* We have freed @to_free real clusters. */ |
972 | real_freed += to_free; |
973 | } |
974 | /* Adjust the number of clusters left to free. */ |
975 | if (count >= 0) |
976 | count -= to_free; |
977 | |
978 | /* Update the total done clusters. */ |
979 | total_freed += to_free; |
980 | } |
981 | if (likely(!is_rollback)) |
982 | up_write(&vol->lcnbmp_lock); |
983 | |
984 | BUG_ON(count > 0); |
985 | |
986 | /* We are done. Return the number of actually freed clusters. */ |
987 | ntfs_debug("Done."); |
988 | return real_freed; |
989 | err_out: |
990 | if (is_rollback) |
991 | return err; |
992 | /* If no real clusters were freed, no need to rollback. */ |
993 | if (!real_freed) { |
994 | up_write(&vol->lcnbmp_lock); |
995 | return err; |
996 | } |
997 | /* |
998 | * Attempt to rollback and if that succeeds just return the error code. |
999 | * If rollback fails, set the volume errors flag, emit an error |
1000 | * message, and return the error code. |
1001 | */ |
1002 | delta = __ntfs_cluster_free(ni, start_vcn, total_freed, ctx, true); |
1003 | if (delta < 0) { |
1004 | ntfs_error(vol->sb, "Failed to rollback (error %i). Leaving " |
1005 | "inconsistent metadata! Unmount and run " |
1006 | "chkdsk.", (int)delta); |
1007 | NVolSetErrors(vol); |
1008 | } |
1009 | up_write(&vol->lcnbmp_lock); |
1010 | ntfs_error(vol->sb, "Aborting (error %i).", err); |
1011 | return err; |
1012 | } |
1013 | |
1014 | #endif /* NTFS_RW */ |
1015 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9