]> git.kernelconcepts.de Git - karo-tx-linux.git/blob - fs/ntfs/lcnalloc.c
radix-tree tests: add regression3 test
[karo-tx-linux.git] / fs / ntfs / lcnalloc.c
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 */