xref: /onnv-gate/usr/src/lib/libntfs/common/libntfs/bitmap.c (revision 10214:1f70f0c2183c)
1 /**
2  * bitmap.c - Bitmap handling code. Part of the Linux-NTFS project.
3  *
4  * Copyright (c) 2002-2006 Anton Altaparmakov
5  * Copyright (c) 2004-2005 Richard Russon
6  *
7  * This program/include file is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License as published
9  * by the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * This program/include file is distributed in the hope that it will be
13  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program (in the main directory of the Linux-NTFS
19  * distribution in the file COPYING); if not, write to the Free Software
20  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
21  */
22 
23 #ifdef HAVE_CONFIG_H
24 #include "config.h"
25 #endif
26 
27 #ifdef HAVE_STDLIB_H
28 #include <stdlib.h>
29 #endif
30 #ifdef HAVE_STDIO_H
31 #include <stdio.h>
32 #endif
33 #ifdef HAVE_STRING_H
34 #include <string.h>
35 #endif
36 #ifdef HAVE_ERRNO_H
37 #include <errno.h>
38 #endif
39 
40 #include "compat.h"
41 #include "types.h"
42 #include "attrib.h"
43 #include "bitmap.h"
44 #include "debug.h"
45 #include "logging.h"
46 
47 /**
48  * ntfs_bitmap_set_bits_in_run - set a run of bits in a bitmap to a value
49  * @na:		attribute containing the bitmap
50  * @start_bit:	first bit to set
51  * @count:	number of bits to set
52  * @value:	value to set the bits to (i.e. 0 or 1)
53  *
54  * Set @count bits starting at bit @start_bit in the bitmap described by the
55  * attribute @na to @value, where @value is either 0 or 1.
56  *
57  * On success return 0 and on error return -1 with errno set to the error code.
58  */
ntfs_bitmap_set_bits_in_run(ntfs_attr * na,s64 start_bit,s64 count,int value)59 static int ntfs_bitmap_set_bits_in_run(ntfs_attr *na, s64 start_bit,
60 		s64 count, int value)
61 {
62 	ntfs_volume *vol = na->ni->vol;
63 	s64 bufsize, br, left = count;
64 	u8 *buf, *lastbyte_buf;
65 	int bit, firstbyte, lastbyte, lastbyte_pos, tmp, err;
66 
67 	if (!na || start_bit < 0 || count < 0) {
68 		errno = EINVAL;
69 		return -1;
70 	}
71 
72 	bit = start_bit & 7;
73 	if (bit)
74 		firstbyte = 1;
75 	else
76 		firstbyte = 0;
77 
78 	/* Calculate the required buffer size in bytes, capping it at 8kiB. */
79 	bufsize = ((count - (bit ? 8 - bit : 0) + 7) >> 3) + firstbyte;
80 	if (bufsize > 8192)
81 		bufsize = 8192;
82 
83 	buf = (u8*)ntfs_malloc(bufsize);
84 	if (!buf)
85 		return -1;
86 
87 	/* Depending on @value, zero or set all bits in the allocated buffer. */
88 	memset(buf, value ? 0xff : 0, bufsize);
89 
90 	/* If there is a first partial byte... */
91 	if (bit) {
92 		/* read it in... */
93 		br = ntfs_attr_pread(na, start_bit >> 3, 1, buf);
94 		if (br != 1) {
95 			free(buf);
96 			errno = EIO;
97 			return -1;
98 		}
99 		/* and set or clear the appropriate bits in it. */
100 		while ((bit & 7) && left--) {
101 			if (value)
102 				*buf |= 1 << bit++;
103 			else
104 				*buf &= ~(1 << bit++);
105 		}
106 		/* Update @start_bit to the new position. */
107 		start_bit = (start_bit + 7) & ~7;
108 	}
109 
110 	/* Loop until @left reaches zero. */
111 	lastbyte = 0;
112 	lastbyte_buf = NULL;
113 	bit = left & 7;
114 	do {
115 		/* If there is a last partial byte... */
116 		if (left > 0 && bit) {
117 			lastbyte_pos = ((left + 7) >> 3) + firstbyte;
118 			if (!lastbyte_pos) {
119 				// FIXME: Eeek! BUG!
120 				ntfs_log_trace("lastbyte is zero. Leaving "
121 						"inconsistent metadata.\n");
122 				err = EIO;
123 				goto free_err_out;
124 			}
125 			/* and it is in the currently loaded bitmap window... */
126 			if (lastbyte_pos <= bufsize) {
127 				lastbyte_buf = buf + lastbyte_pos - 1;
128 
129 				/* read the byte in... */
130 				br = ntfs_attr_pread(na, (start_bit + left) >>
131 						3, 1, lastbyte_buf);
132 				if (br != 1) {
133 					// FIXME: Eeek! We need rollback! (AIA)
134 					ntfs_log_trace("Read of last byte "
135 							"failed. Leaving "
136 							"inconsistent "
137 							"metadata.\n");
138 					err = EIO;
139 					goto free_err_out;
140 				}
141 				/* and set/clear the appropriate bits in it. */
142 				while (bit && left--) {
143 					if (value)
144 						*lastbyte_buf |= 1 << --bit;
145 					else
146 						*lastbyte_buf &= ~(1 << --bit);
147 				}
148 				/* We don't want to come back here... */
149 				bit = 0;
150 				/* We have a last byte that we have handled. */
151 				lastbyte = 1;
152 			}
153 		}
154 
155 		/* Write the prepared buffer to disk. */
156 		tmp = (start_bit >> 3) - firstbyte;
157 		br = ntfs_attr_pwrite(na, tmp, bufsize, buf);
158 		if (br != bufsize) {
159 			// FIXME: Eeek! We need rollback! (AIA)
160 			ntfs_log_trace("Failed to write buffer to bitmap. "
161 					"Leaving inconsistent metadata.\n");
162 			err = EIO;
163 			goto free_err_out;
164 		}
165 
166 		/* Update counters. */
167 		tmp = (bufsize - firstbyte - lastbyte) << 3;
168 		if (firstbyte) {
169 			firstbyte = 0;
170 			/*
171 			 * Re-set the partial first byte so a subsequent write
172 			 * of the buffer does not have stale, incorrect bits.
173 			 */
174 			*buf = value ? 0xff : 0;
175 		}
176 		start_bit += tmp;
177 		left -= tmp;
178 		if (bufsize > (tmp = (left + 7) >> 3))
179 			bufsize = tmp;
180 
181 		if (lastbyte && left != 0) {
182 			// FIXME: Eeek! BUG!
183 			ntfs_log_trace("Last buffer but count is not zero (= "
184 					"%lli). Leaving inconsistent metadata."
185 					"\n", (long long)left);
186 			err = EIO;
187 			goto free_err_out;
188 		}
189 	} while (left > 0);
190 
191 	/* Update free clusters and MFT records. */
192 	if (na == vol->mftbmp_na) {
193 		if (value)
194 			vol->nr_free_mft_records -= count;
195 		else
196 			vol->nr_free_mft_records += count;
197 	}
198 	if (na == vol->lcnbmp_na) {
199 		if (value)
200 			vol->nr_free_clusters -= count;
201 		else
202 			vol->nr_free_clusters += count;
203 	}
204 
205 	/* Done! */
206 	free(buf);
207 	return 0;
208 
209 free_err_out:
210 	free(buf);
211 	errno = err;
212 	return -1;
213 }
214 
215 /**
216  * ntfs_bitmap_set_run - set a run of bits in a bitmap
217  * @na:		attribute containing the bitmap
218  * @start_bit:	first bit to set
219  * @count:	number of bits to set
220  *
221  * Set @count bits starting at bit @start_bit in the bitmap described by the
222  * attribute @na.
223  *
224  * On success return 0 and on error return -1 with errno set to the error code.
225  */
ntfs_bitmap_set_run(ntfs_attr * na,s64 start_bit,s64 count)226 int ntfs_bitmap_set_run(ntfs_attr *na, s64 start_bit, s64 count)
227 {
228 	return ntfs_bitmap_set_bits_in_run(na, start_bit, count, 1);
229 }
230 
231 /**
232  * ntfs_bitmap_clear_run - clear a run of bits in a bitmap
233  * @na:		attribute containing the bitmap
234  * @start_bit:	first bit to clear
235  * @count:	number of bits to clear
236  *
237  * Clear @count bits starting at bit @start_bit in the bitmap described by the
238  * attribute @na.
239  *
240  * On success return 0 and on error return -1 with errno set to the error code.
241  */
ntfs_bitmap_clear_run(ntfs_attr * na,s64 start_bit,s64 count)242 int ntfs_bitmap_clear_run(ntfs_attr *na, s64 start_bit, s64 count)
243 {
244 	ntfs_log_trace("Dealloc from bit 0x%llx, count 0x%llx.\n",
245 		       (long long)start_bit, (long long)count);
246 
247 	return ntfs_bitmap_set_bits_in_run(na, start_bit, count, 0);
248 }
249 
250