path: root/libntfs-3g/lcnalloc.c (plain)
blob: 9eb907cd9a026b1682e8dda65ed97cf79026b9b0

1	/**
2	* lcnalloc.c - Cluster (de)allocation code. Originated from the Linux-NTFS project.
3	*
4	* Copyright (c) 2002-2004 Anton Altaparmakov
5	* Copyright (c) 2004 Yura Pakhuchiy
6	* Copyright (c) 2004-2008 Szabolcs Szakacsits
7	* Copyright (c) 2008-2009 Jean-Pierre Andre
8	*
9	* This program/include file is free software; you can redistribute it and/or
10	* modify it under the terms of the GNU General Public License as published
11	* by the Free Software Foundation; either version 2 of the License, or
12	* (at your option) any later version.
13	*
14	* This program/include file is distributed in the hope that it will be
15	* useful, but WITHOUT ANY WARRANTY; without even the implied warranty
16	* of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17	* GNU General Public License for more details.
18	*
19	* You should have received a copy of the GNU General Public License
20	* along with this program (in the main directory of the NTFS-3G
21	* distribution in the file COPYING); if not, write to the Free Software
22	* Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23	*/
24
25	#ifdef HAVE_CONFIG_H
26	#include "config.h"
27	#endif
28
29	#ifdef HAVE_STDLIB_H
30	#include <stdlib.h>
31	#endif
32	#ifdef HAVE_STDIO_H
33	#include <stdio.h>
34	#endif
35	#ifdef HAVE_ERRNO_H
36	#include <errno.h>
37	#endif
38
39	#include "types.h"
40	#include "attrib.h"
41	#include "bitmap.h"
42	#include "debug.h"
43	#include "runlist.h"
44	#include "volume.h"
45	#include "lcnalloc.h"
46	#include "logging.h"
47	#include "misc.h"
48
49	/*
50	* Plenty possibilities for big optimizations all over in the cluster
51	* allocation, however at the moment the dominant bottleneck (~ 90%) is
52	* the update of the mapping pairs which converges to the cubic Faulhaber's
53	* formula as the function of the number of extents (fragments, runs).
54	*/
55	#define NTFS_LCNALLOC_BSIZE 4096
56	#define NTFS_LCNALLOC_SKIP NTFS_LCNALLOC_BSIZE
57
58	enum {
59	ZONE_MFT = 1,
60	ZONE_DATA1 = 2,
61	ZONE_DATA2 = 4
62	} ;
63
64	static void ntfs_cluster_set_zone_pos(LCN start, LCN end, LCN *pos, LCN tc)
65	{
66	ntfs_log_trace("pos: %lld tc: %lld\n", (long long)*pos, (long long)tc);
67
68	if (tc >= end)
69	*pos = start;
70	else if (tc >= start)
71	*pos = tc;
72	}
73
74	static void ntfs_cluster_update_zone_pos(ntfs_volume *vol, u8 zone, LCN tc)
75	{
76	ntfs_log_trace("tc = %lld, zone = %d\n", (long long)tc, zone);
77
78	if (zone == ZONE_MFT)
79	ntfs_cluster_set_zone_pos(vol->mft_lcn, vol->mft_zone_end,
80	&vol->mft_zone_pos, tc);
81	else if (zone == ZONE_DATA1)
82	ntfs_cluster_set_zone_pos(vol->mft_zone_end, vol->nr_clusters,
83	&vol->data1_zone_pos, tc);
84	else /* zone == ZONE_DATA2 */
85	ntfs_cluster_set_zone_pos(0, vol->mft_zone_start,
86	&vol->data2_zone_pos, tc);
87	}
88
89	/*
90	* Unmark full zones when a cluster has been freed in a full zone
91	*
92	* Next allocation will reuse the freed cluster
93	*/
94
95	static void update_full_status(ntfs_volume *vol, LCN lcn)
96	{
97	if (lcn >= vol->mft_zone_end) {
98	if (vol->full_zones & ZONE_DATA1) {
99	ntfs_cluster_update_zone_pos(vol, ZONE_DATA1, lcn);
100	vol->full_zones &= ~ZONE_DATA1;
101	}
102	} else
103	if (lcn < vol->mft_zone_start) {
104	if (vol->full_zones & ZONE_DATA2) {
105	ntfs_cluster_update_zone_pos(vol, ZONE_DATA2, lcn);
106	vol->full_zones &= ~ZONE_DATA2;
107	}
108	} else {
109	if (vol->full_zones & ZONE_MFT) {
110	ntfs_cluster_update_zone_pos(vol, ZONE_MFT, lcn);
111	vol->full_zones &= ~ZONE_MFT;
112	}
113	}
114	}
115
116	static s64 max_empty_bit_range(unsigned char *buf, int size)
117	{
118	int i, j, run = 0;
119	int max_range = 0;
120	s64 start_pos = -1;
121
122	ntfs_log_trace("Entering\n");
123
124	i = 0;
125	while (i < size) {
126	switch (*buf) {
127	case 0 :
128	do {
129	buf++;
130	run += 8;
131	i++;
132	} while ((i < size) && !*buf);
133	break;
134	case 255 :
135	if (run > max_range) {
136	max_range = run;
137	start_pos = (s64)i * 8 - run;
138	}
139	run = 0;
140	do {
141	buf++;
142	i++;
143	} while ((i < size) && (*buf == 255));
144	break;
145	default :
146	for (j = 0; j < 8; j++) {
147
148	int bit = *buf & (1 << j);
149
150	if (bit) {
151	if (run > max_range) {
152	max_range = run;
153	start_pos = (s64)i * 8 + (j - run);
154	}
155	run = 0;
156	} else
157	run++;
158	}
159	i++;
160	buf++;
161
162	}
163	}
164
165	if (run > max_range)
166	start_pos = (s64)i * 8 - run;
167
168	return start_pos;
169	}
170
171	static int bitmap_writeback(ntfs_volume *vol, s64 pos, s64 size, void *b,
172	u8 *writeback)
173	{
174	s64 written;
175
176	ntfs_log_trace("Entering\n");
177
178	if (!*writeback)
179	return 0;
180
181	*writeback = 0;
182
183	written = ntfs_attr_pwrite(vol->lcnbmp_na, pos, size, b);
184	if (written != size) {
185	if (!written)
186	errno = EIO;
187	ntfs_log_perror("Bitmap write error (%lld, %lld)",
188	(long long)pos, (long long)size);
189	return -1;
190	}
191
192	return 0;
193	}
194
195	/**
196	* ntfs_cluster_alloc - allocate clusters on an ntfs volume
197	* @vol: mounted ntfs volume on which to allocate the clusters
198	* @start_vcn: vcn to use for the first allocated cluster
199	* @count: number of clusters to allocate
200	* @start_lcn: starting lcn at which to allocate the clusters (or -1 if none)
201	* @zone: zone from which to allocate the clusters
202	*
203	* Allocate @count clusters preferably starting at cluster @start_lcn or at the
204	* current allocator position if @start_lcn is -1, on the mounted ntfs volume
205	* @vol. @zone is either DATA_ZONE for allocation of normal clusters and
206	* MFT_ZONE for allocation of clusters for the master file table, i.e. the
207	* $MFT/$DATA attribute.
208	*
209	* On success return a runlist describing the allocated cluster(s).
210	*
211	* On error return NULL with errno set to the error code.
212	*
213	* Notes on the allocation algorithm
214	* =================================
215	*
216	* There are two data zones. First is the area between the end of the mft zone
217	* and the end of the volume, and second is the area between the start of the
218	* volume and the start of the mft zone. On unmodified/standard NTFS 1.x
219	* volumes, the second data zone doesn't exist due to the mft zone being
220	* expanded to cover the start of the volume in order to reserve space for the
221	* mft bitmap attribute.
222	*
223	* The complexity stems from the need of implementing the mft vs data zoned
224	* approach and from the fact that we have access to the lcn bitmap via up to
225	* NTFS_LCNALLOC_BSIZE bytes at a time, so we need to cope with crossing over
226	* boundaries of two buffers. Further, the fact that the allocator allows for
227	* caller supplied hints as to the location of where allocation should begin
228	* and the fact that the allocator keeps track of where in the data zones the
229	* next natural allocation should occur, contribute to the complexity of the
230	* function. But it should all be worthwhile, because this allocator:
231	* 1) implements MFT zone reservation
232	* 2) causes reduction in fragmentation.
233	* The code is not optimized for speed.
234	*/
235	runlist *ntfs_cluster_alloc(ntfs_volume *vol, VCN start_vcn, s64 count,
236	LCN start_lcn, const NTFS_CLUSTER_ALLOCATION_ZONES zone)
237	{
238	LCN zone_start, zone_end; /* current search range */
239	LCN last_read_pos, lcn;
240	LCN bmp_pos; /* current bit position inside the bitmap */
241	LCN prev_lcn = 0, prev_run_len = 0;
242	s64 clusters, br;
243	runlist *rl = NULL, *trl;
244	u8 *buf, *byte, bit, writeback;
245	u8 pass = 1; /* 1: inside zone; 2: start of zone */
246	u8 search_zone; /* 4: data2 (start) 1: mft (middle) 2: data1 (end) */
247	u8 done_zones = 0;
248	u8 has_guess, used_zone_pos;
249	int err = 0, rlpos, rlsize, buf_size;
250
251	ntfs_log_enter("Entering with count = 0x%llx, start_lcn = 0x%llx, "
252	"zone = %s_ZONE.\n", (long long)count, (long long)
253	start_lcn, zone == MFT_ZONE ? "MFT" : "DATA");
254
255	if (!vol || count < 0 || start_lcn < -1 || !vol->lcnbmp_na ||
256	(s8)zone < FIRST_ZONE || zone > LAST_ZONE) {
257	errno = EINVAL;
258	ntfs_log_perror("%s: vcn: %lld, count: %lld, lcn: %lld",
259	__FUNCTION__, (long long)start_vcn,
260	(long long)count, (long long)start_lcn);
261	goto out;
262	}
263
264	/* Return empty runlist if @count == 0 */
265	if (!count) {
266	rl = ntfs_malloc(0x1000);
267	if (rl) {
268	rl[0].vcn = start_vcn;
269	rl[0].lcn = LCN_RL_NOT_MAPPED;
270	rl[0].length = 0;
271	}
272	goto out;
273	}
274
275	buf = ntfs_malloc(NTFS_LCNALLOC_BSIZE);
276	if (!buf)
277	goto out;
278	/*
279	* If no @start_lcn was requested, use the current zone
280	* position otherwise use the requested @start_lcn.
281	*/
282	has_guess = 1;
283	zone_start = start_lcn;
284
285	if (zone_start < 0) {
286	if (zone == DATA_ZONE)
287	zone_start = vol->data1_zone_pos;
288	else
289	zone_start = vol->mft_zone_pos;
290	has_guess = 0;
291	}
292
293	used_zone_pos = has_guess ? 0 : 1;
294
295	if (!zone_start || zone_start == vol->mft_zone_start ||
296	zone_start == vol->mft_zone_end)
297	pass = 2;
298
299	if (zone_start < vol->mft_zone_start) {
300	zone_end = vol->mft_zone_start;
301	search_zone = ZONE_DATA2;
302	} else if (zone_start < vol->mft_zone_end) {
303	zone_end = vol->mft_zone_end;
304	search_zone = ZONE_MFT;
305	} else {
306	zone_end = vol->nr_clusters;
307	search_zone = ZONE_DATA1;
308	}
309
310	bmp_pos = zone_start;
311
312	/* Loop until all clusters are allocated. */
313	clusters = count;
314	rlpos = rlsize = 0;
315	while (1) {
316	/* check whether we have exhausted the current zone */
317	if (search_zone & vol->full_zones)
318	goto zone_pass_done;
319	last_read_pos = bmp_pos >> 3;
320	br = ntfs_attr_pread(vol->lcnbmp_na, last_read_pos,
321	NTFS_LCNALLOC_BSIZE, buf);
322	if (br <= 0) {
323	if (!br)
324	goto zone_pass_done;
325	err = errno;
326	ntfs_log_perror("Reading $BITMAP failed");
327	goto err_ret;
328	}
329	/*
330	* We might have read less than NTFS_LCNALLOC_BSIZE bytes
331	* if we are close to the end of the attribute.
332	*/
333	buf_size = (int)br << 3;
334	lcn = bmp_pos & 7;
335	bmp_pos &= ~7;
336	writeback = 0;
337
338	while (lcn < buf_size) {
339	byte = buf + (lcn >> 3);
340	bit = 1 << (lcn & 7);
341	if (has_guess) {
342	if (*byte & bit) {
343	has_guess = 0;
344	break;
345	}
346	} else {
347	lcn = max_empty_bit_range(buf, br);
348	if (lcn < 0)
349	break;
350	has_guess = 1;
351	continue;
352	}
353
354	/* First free bit is at lcn + bmp_pos. */
355
356	/* Reallocate memory if necessary. */
357	if ((rlpos + 2) * (int)sizeof(runlist) >= rlsize) {
358	rlsize += 4096;
359	trl = realloc(rl, rlsize);
360	if (!trl) {
361	err = ENOMEM;
362	ntfs_log_perror("realloc() failed");
363	goto wb_err_ret;
364	}
365	rl = trl;
366	}
367
368	/* Allocate the bitmap bit. */
369	*byte |= bit;
370	writeback = 1;
371	if (vol->free_clusters <= 0)
372	ntfs_log_error("Non-positive free clusters "
373	"(%lld)!\n",
374	(long long)vol->free_clusters);
375	else
376	vol->free_clusters--;
377
378	/*
379	* Coalesce with previous run if adjacent LCNs.
380	* Otherwise, append a new run.
381	*/
382	if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) {
383	ntfs_log_debug("Cluster coalesce: prev_lcn: "
384	"%lld lcn: %lld bmp_pos: %lld "
385	"prev_run_len: %lld\n",
386	(long long)prev_lcn,
387	(long long)lcn, (long long)bmp_pos,
388	(long long)prev_run_len);
389	rl[rlpos - 1].length = ++prev_run_len;
390	} else {
391	if (rlpos)
392	rl[rlpos].vcn = rl[rlpos - 1].vcn +
393	prev_run_len;
394	else {
395	rl[rlpos].vcn = start_vcn;
396	ntfs_log_debug("Start_vcn: %lld\n",
397	(long long)start_vcn);
398	}
399
400	rl[rlpos].lcn = prev_lcn = lcn + bmp_pos;
401	rl[rlpos].length = prev_run_len = 1;
402	rlpos++;
403	}
404
405	ntfs_log_debug("RUN: %-16lld %-16lld %-16lld\n",
406	(long long)rl[rlpos - 1].vcn,
407	(long long)rl[rlpos - 1].lcn,
408	(long long)rl[rlpos - 1].length);
409	/* Done? */
410	if (!--clusters) {
411	if (used_zone_pos)
412	ntfs_cluster_update_zone_pos(vol,
413	search_zone, lcn + bmp_pos + 1 +
414	NTFS_LCNALLOC_SKIP);
415	goto done_ret;
416	}
417
418	lcn++;
419	}
420
421	if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) {
422	err = errno;
423	goto err_ret;
424	}
425
426	if (!used_zone_pos) {
427
428	used_zone_pos = 1;
429
430	if (search_zone == ZONE_MFT)
431	zone_start = vol->mft_zone_pos;
432	else if (search_zone == ZONE_DATA1)
433	zone_start = vol->data1_zone_pos;
434	else
435	zone_start = vol->data2_zone_pos;
436
437	if (!zone_start || zone_start == vol->mft_zone_start ||
438	zone_start == vol->mft_zone_end)
439	pass = 2;
440	bmp_pos = zone_start;
441	} else
442	bmp_pos += buf_size;
443
444	if (bmp_pos < zone_end)
445	continue;
446
447	zone_pass_done:
448	ntfs_log_trace("Finished current zone pass(%i).\n", pass);
449	if (pass == 1) {
450	pass = 2;
451	zone_end = zone_start;
452
453	if (search_zone == ZONE_MFT)
454	zone_start = vol->mft_zone_start;
455	else if (search_zone == ZONE_DATA1)
456	zone_start = vol->mft_zone_end;
457	else
458	zone_start = 0;
459
460	/* Sanity check. */
461	if (zone_end < zone_start)
462	zone_end = zone_start;
463
464	bmp_pos = zone_start;
465
466	continue;
467	}
468	/* pass == 2 */
469	done_zones_check:
470	done_zones |= search_zone;
471	vol->full_zones |= search_zone;
472	if (done_zones < (ZONE_MFT + ZONE_DATA1 + ZONE_DATA2)) {
473	ntfs_log_trace("Switching zone.\n");
474	pass = 1;
475	if (rlpos) {
476	LCN tc = rl[rlpos - 1].lcn +
477	rl[rlpos - 1].length + NTFS_LCNALLOC_SKIP;
478
479	if (used_zone_pos)
480	ntfs_cluster_update_zone_pos(vol,
481	search_zone, tc);
482	}
483
484	switch (search_zone) {
485	case ZONE_MFT:
486	ntfs_log_trace("Zone switch: mft -> data1\n");
487	switch_to_data1_zone: search_zone = ZONE_DATA1;
488	zone_start = vol->data1_zone_pos;
489	zone_end = vol->nr_clusters;
490	if (zone_start == vol->mft_zone_end)
491	pass = 2;
492	break;
493	case ZONE_DATA1:
494	ntfs_log_trace("Zone switch: data1 -> data2\n");
495	search_zone = ZONE_DATA2;
496	zone_start = vol->data2_zone_pos;
497	zone_end = vol->mft_zone_start;
498	if (!zone_start)
499	pass = 2;
500	break;
501	case ZONE_DATA2:
502	if (!(done_zones & ZONE_DATA1)) {
503	ntfs_log_trace("data2 -> data1\n");
504	goto switch_to_data1_zone;
505	}
506	ntfs_log_trace("Zone switch: data2 -> mft\n");
507	search_zone = ZONE_MFT;
508	zone_start = vol->mft_zone_pos;
509	zone_end = vol->mft_zone_end;
510	if (zone_start == vol->mft_zone_start)
511	pass = 2;
512	break;
513	}
514
515	bmp_pos = zone_start;
516
517	if (zone_start == zone_end) {
518	ntfs_log_trace("Empty zone, skipped.\n");
519	goto done_zones_check;
520	}
521
522	continue;
523	}
524
525	ntfs_log_trace("All zones are finished, no space on device.\n");
526	err = ENOSPC;
527	goto err_ret;
528	}
529	done_ret:
530	ntfs_log_debug("At done_ret.\n");
531	/* Add runlist terminator element. */
532	rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length;
533	rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
534	rl[rlpos].length = 0;
535	if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) {
536	err = errno;
537	goto err_ret;
538	}
539	done_err_ret:
540	free(buf);
541	if (err) {
542	errno = err;
543	ntfs_log_perror("Failed to allocate clusters");
544	rl = NULL;
545	}
546	out:
547	ntfs_log_leave("\n");
548	return rl;
549
550	wb_err_ret:
551	ntfs_log_trace("At wb_err_ret.\n");
552	if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback))
553	err = errno;
554	err_ret:
555	ntfs_log_trace("At err_ret.\n");
556	if (rl) {
557	/* Add runlist terminator element. */
558	rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length;
559	rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
560	rl[rlpos].length = 0;
561	ntfs_debug_runlist_dump(rl);
562	ntfs_cluster_free_from_rl(vol, rl);
563	free(rl);
564	rl = NULL;
565	}
566	goto done_err_ret;
567	}
568
569	/**
570	* ntfs_cluster_free_from_rl - free clusters from runlist
571	* @vol: mounted ntfs volume on which to free the clusters
572	* @rl: runlist from which deallocate clusters
573	*
574	* On success return 0 and on error return -1 with errno set to the error code.
575	*/
576	int ntfs_cluster_free_from_rl(ntfs_volume *vol, runlist *rl)
577	{
578	s64 nr_freed = 0;
579	int ret = -1;
580
581	ntfs_log_trace("Entering.\n");
582
583	for (; rl->length; rl++) {
584
585	ntfs_log_trace("Dealloc lcn 0x%llx, len 0x%llx.\n",
586	(long long)rl->lcn, (long long)rl->length);
587
588	if (rl->lcn >= 0) {
589	update_full_status(vol,rl->lcn);
590	if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn,
591	rl->length)) {
592	ntfs_log_perror("Cluster deallocation failed "
593	"(%lld, %lld)",
594	(long long)rl->lcn,
595	(long long)rl->length);
596	goto out;
597	}
598	nr_freed += rl->length ;
599	}
600	}
601
602	ret = 0;
603	out:
604	vol->free_clusters += nr_freed;
605	if (vol->free_clusters > vol->nr_clusters)
606	ntfs_log_error("Too many free clusters (%lld > %lld)!",
607	(long long)vol->free_clusters,
608	(long long)vol->nr_clusters);
609	return ret;
610	}
611
612	/**
613	* ntfs_cluster_free - free clusters on an ntfs volume
614	* @vol: mounted ntfs volume on which to free the clusters
615	* @na: attribute whose runlist describes the clusters to free
616	* @start_vcn: vcn in @rl at which to start freeing clusters
617	* @count: number of clusters to free or -1 for all clusters
618	*
619	* Free @count clusters starting at the cluster @start_vcn in the runlist
620	* described by the attribute @na from the mounted ntfs volume @vol.
621	*
622	* If @count is -1, all clusters from @start_vcn to the end of the runlist
623	* are deallocated.
624	*
625	* On success return the number of deallocated clusters (not counting sparse
626	* clusters) and on error return -1 with errno set to the error code.
627	*/
628	int ntfs_cluster_free(ntfs_volume *vol, ntfs_attr *na, VCN start_vcn, s64 count)
629	{
630	runlist *rl;
631	s64 delta, to_free, nr_freed = 0;
632	int ret = -1;
633
634	if (!vol || !vol->lcnbmp_na || !na || start_vcn < 0 ||
635	(count < 0 && count != -1)) {
636	ntfs_log_trace("Invalid arguments!\n");
637	errno = EINVAL;
638	return -1;
639	}
640
641	ntfs_log_enter("Entering for inode 0x%llx, attr 0x%x, count 0x%llx, "
642	"vcn 0x%llx.\n", (unsigned long long)na->ni->mft_no,
643	na->type, (long long)count, (long long)start_vcn);
644
645	rl = ntfs_attr_find_vcn(na, start_vcn);
646	if (!rl) {
647	if (errno == ENOENT)
648	ret = 0;
649	goto leave;
650	}
651
652	if (rl->lcn < 0 && rl->lcn != LCN_HOLE) {
653	errno = EIO;
654	ntfs_log_perror("%s: Unexpected lcn (%lld)", __FUNCTION__,
655	(long long)rl->lcn);
656	goto leave;
657	}
658
659	/* Find the starting cluster inside the run that needs freeing. */
660	delta = start_vcn - rl->vcn;
661
662	/* The number of clusters in this run that need freeing. */
663	to_free = rl->length - delta;
664	if (count >= 0 && to_free > count)
665	to_free = count;
666
667	if (rl->lcn != LCN_HOLE) {
668	/* Do the actual freeing of the clusters in this run. */
669	update_full_status(vol,rl->lcn + delta);
670	if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn + delta,
671	to_free))
672	goto leave;
673	nr_freed = to_free;
674	}
675
676	/* Go to the next run and adjust the number of clusters left to free. */
677	++rl;
678	if (count >= 0)
679	count -= to_free;
680
681	/*
682	* Loop over the remaining runs, using @count as a capping value, and
683	* free them.
684	*/
685	for (; rl->length && count != 0; ++rl) {
686	// FIXME: Need to try ntfs_attr_map_runlist() for attribute
687	// list support! (AIA)
688	if (rl->lcn < 0 && rl->lcn != LCN_HOLE) {
689	// FIXME: Eeek! We need rollback! (AIA)
690	errno = EIO;
691	ntfs_log_perror("%s: Invalid lcn (%lli)",
692	__FUNCTION__, (long long)rl->lcn);
693	goto out;
694	}
695
696	/* The number of clusters in this run that need freeing. */
697	to_free = rl->length;
698	if (count >= 0 && to_free > count)
699	to_free = count;
700
701	if (rl->lcn != LCN_HOLE) {
702	update_full_status(vol,rl->lcn);
703	if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn,
704	to_free)) {
705	// FIXME: Eeek! We need rollback! (AIA)
706	ntfs_log_perror("%s: Clearing bitmap run failed",
707	__FUNCTION__);
708	goto out;
709	}
710	nr_freed += to_free;
711	}
712
713	if (count >= 0)
714	count -= to_free;
715	}
716
717	if (count != -1 && count != 0) {
718	// FIXME: Eeek! BUG()
719	errno = EIO;
720	ntfs_log_perror("%s: count still not zero (%lld)", __FUNCTION__,
721	(long long)count);
722	goto out;
723	}
724
725	ret = nr_freed;
726	out:
727	vol->free_clusters += nr_freed ;
728	if (vol->free_clusters > vol->nr_clusters)
729	ntfs_log_error("Too many free clusters (%lld > %lld)!",
730	(long long)vol->free_clusters,
731	(long long)vol->nr_clusters);
732	leave:
733	ntfs_log_leave("\n");
734	return ret;
735	}
736