File: /usr/src/linux/fs/ntfs/super.c
1 /*
2 * super.c
3 *
4 * Copyright (C) 1995-1997, 1999 Martin von Löwis
5 * Copyright (C) 1996-1997 Régis Duchesne
6 * Copyright (C) 1999 Steve Dodd
7 * Copyright (C) 2000-2001 Anton Altparmakov (AIA)
8 */
9
10 #include <linux/ntfs_fs.h>
11 #include <linux/errno.h>
12 #include <linux/bitops.h>
13 #include <linux/module.h>
14 #include "ntfstypes.h"
15 #include "struct.h"
16 #include "super.h"
17 #include "macros.h"
18 #include "inode.h"
19 #include "support.h"
20 #include "util.h"
21 #include <linux/smp_lock.h>
22
23 /* All important structures in NTFS use 2 consistency checks:
24 * . a magic structure identifier (FILE, INDX, RSTR, RCRD...)
25 * . a fixup technique : the last word of each sector (called a fixup) of a
26 * structure's record should end with the word at offset <n> of the first
27 * sector, and if it is the case, must be replaced with the words following
28 * <n>. The value of <n> and the number of fixups is taken from the fields
29 * at the offsets 4 and 6. Note that the sector size is defined as
30 * NTFS_SECTOR_SIZE and not as the hardware sector size (this is concordant
31 * with what the Windows NTFS driver does).
32 *
33 * This function performs these 2 checks, and _fails_ if:
34 * . the input size is invalid
35 * . the fixup header is invalid
36 * . the size does not match the number of sectors
37 * . the magic identifier is wrong
38 * . a fixup is invalid
39 */
40 int ntfs_fixup_record(char *record, char *magic, int size)
41 {
42 int start, count, offset;
43 ntfs_u16 fixup;
44
45 if (!IS_MAGIC(record, magic))
46 return 0;
47 start = NTFS_GETU16(record + 4);
48 count = NTFS_GETU16(record + 6) - 1;
49 if (size & (NTFS_SECTOR_SIZE - 1) || start & 1 ||
50 start + count * 2 > size || size >> 9 != count) {
51 if (size <= 0)
52 printk(KERN_ERR "NTFS: BUG: ntfs_fixup_record() got "
53 "zero size! Please report this to "
54 "linux-ntfs-dev@lists.sf.net\n");
55 return 0;
56 }
57 fixup = NTFS_GETU16(record + start);
58 start += 2;
59 offset = NTFS_SECTOR_SIZE - 2;
60 while (count--) {
61 if (NTFS_GETU16(record + offset) != fixup)
62 return 0;
63 NTFS_PUTU16(record + offset, NTFS_GETU16(record + start));
64 start += 2;
65 offset += NTFS_SECTOR_SIZE;
66 }
67 return 1;
68 }
69
70 /*
71 * Get vital informations about the ntfs partition from the boot sector.
72 * Return 0 on success or -1 on error.
73 */
74 int ntfs_init_volume(ntfs_volume *vol, char *boot)
75 {
76 int sectors_per_cluster_bits;
77 __s64 ll;
78 ntfs_cluster_t mft_zone_size, tc;
79
80 /* System defined default values, in case we don't load $AttrDef. */
81 vol->at_standard_information = 0x10;
82 vol->at_attribute_list = 0x20;
83 vol->at_file_name = 0x30;
84 vol->at_volume_version = 0x40;
85 vol->at_security_descriptor = 0x50;
86 vol->at_volume_name = 0x60;
87 vol->at_volume_information = 0x70;
88 vol->at_data = 0x80;
89 vol->at_index_root = 0x90;
90 vol->at_index_allocation = 0xA0;
91 vol->at_bitmap = 0xB0;
92 vol->at_symlink = 0xC0;
93 /* Sector size. */
94 vol->sector_size = NTFS_GETU16(boot + 0xB);
95 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->sector_size = 0x%x\n",
96 vol->sector_size);
97 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: sectors_per_cluster = "
98 "0x%x\n", NTFS_GETU8(boot + 0xD));
99 sectors_per_cluster_bits = ffs(NTFS_GETU8(boot + 0xD)) - 1;
100 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: sectors_per_cluster_bits "
101 "= 0x%x\n", sectors_per_cluster_bits);
102 vol->mft_clusters_per_record = NTFS_GETS8(boot + 0x40);
103 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_clusters_per_record"
104 " = 0x%x\n", vol->mft_clusters_per_record);
105 vol->index_clusters_per_record = NTFS_GETS8(boot + 0x44);
106 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: "
107 "vol->index_clusters_per_record = 0x%x\n",
108 vol->index_clusters_per_record);
109 vol->cluster_size = vol->sector_size << sectors_per_cluster_bits;
110 vol->cluster_size_bits = ffs(vol->cluster_size) - 1;
111 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->cluster_size = 0x%x\n",
112 vol->cluster_size);
113 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->cluster_size_bits = "
114 "0x%x\n", vol->cluster_size_bits);
115 if (vol->mft_clusters_per_record > 0)
116 vol->mft_record_size = vol->cluster_size <<
117 (ffs(vol->mft_clusters_per_record) - 1);
118 else
119 /*
120 * When mft_record_size < cluster_size, mft_clusters_per_record
121 * = -log2(mft_record_size) bytes. mft_record_size normaly is
122 * 1024 bytes, which is encoded as 0xF6 (-10 in decimal).
123 */
124 vol->mft_record_size = 1 << -vol->mft_clusters_per_record;
125 vol->mft_record_size_bits = ffs(vol->mft_record_size) - 1;
126 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_record_size = 0x%x"
127 "\n", vol->mft_record_size);
128 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_record_size_bits = "
129 "0x%x\n", vol->mft_record_size_bits);
130 if (vol->index_clusters_per_record > 0)
131 vol->index_record_size = vol->cluster_size <<
132 (ffs(vol->index_clusters_per_record) - 1);
133 else
134 /*
135 * When index_record_size < cluster_size,
136 * index_clusters_per_record = -log2(index_record_size) bytes.
137 * index_record_size normaly equals 4096 bytes, which is
138 * encoded as 0xF4 (-12 in decimal).
139 */
140 vol->index_record_size = 1 << -vol->index_clusters_per_record;
141 vol->index_record_size_bits = ffs(vol->index_record_size) - 1;
142 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->index_record_size = "
143 "0x%x\n", vol->index_record_size);
144 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->index_record_size_bits "
145 "= 0x%x\n", vol->index_record_size_bits);
146 /*
147 * Get the size of the volume in clusters (ofs 0x28 is nr_sectors) and
148 * check for 64-bit-ness. Windows currently only uses 32 bits to save
149 * the clusters so we do the same as it is much faster on 32-bit CPUs.
150 */
151 ll = NTFS_GETS64(boot + 0x28) >> sectors_per_cluster_bits;
152 if (ll >= (__s64)1 << 31) {
153 ntfs_error("Cannot handle 64-bit clusters. Please inform "
154 "linux-ntfs-dev@lists.sf.net that you got this "
155 "error.\n");
156 return -1;
157 }
158 vol->nr_clusters = (ntfs_cluster_t)ll;
159 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->nr_clusters = 0x%x\n",
160 vol->nr_clusters);
161 vol->mft_lcn = (ntfs_cluster_t)NTFS_GETS64(boot + 0x30);
162 vol->mft_mirr_lcn = (ntfs_cluster_t)NTFS_GETS64(boot + 0x38);
163 /* Determine MFT zone size. */
164 mft_zone_size = vol->nr_clusters;
165 switch (vol->mft_zone_multiplier) { /* % of volume size in clusters */
166 case 4:
167 mft_zone_size >>= 1; /* 50% */
168 break;
169 case 3:
170 mft_zone_size = mft_zone_size * 3 >> 3; /* 37.5% */
171 break;
172 case 2:
173 mft_zone_size >>= 2; /* 25% */
174 break;
175 /* case 1: */
176 default:
177 mft_zone_size >>= 3; /* 12.5% */
178 break;
179 }
180 /* Setup mft zone. */
181 vol->mft_zone_start = vol->mft_zone_pos = vol->mft_lcn;
182 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_pos = %x\n",
183 vol->mft_zone_pos);
184 /*
185 * Calculate the mft_lcn for an unmodified NTFS volume (see mkntfs
186 * source) and if the actual mft_lcn is in the expected place or even
187 * further to the front of the volume, extend the mft_zone to cover the
188 * beginning of the volume as well. This is in order to protect the
189 * area reserved for the mft bitmap as well within the mft_zone itself.
190 * On non-standard volumes we don't protect it as well as the overhead
191 * would be higher than the speed increase we would get by doing it.
192 */
193 tc = (8192 + 2 * vol->cluster_size - 1) / vol->cluster_size;
194 if (tc * vol->cluster_size < 16 * 1024)
195 tc = (16 * 1024 + vol->cluster_size - 1) / vol->cluster_size;
196 if (vol->mft_zone_start <= tc)
197 vol->mft_zone_start = (ntfs_cluster_t)0;
198 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_start = %x\n",
199 vol->mft_zone_start);
200 /*
201 * Need to cap the mft zone on non-standard volumes so that it does
202 * not point outside the boundaries of the volume, we do this by
203 * halving the zone size until we are inside the volume.
204 */
205 vol->mft_zone_end = vol->mft_lcn + mft_zone_size;
206 while (vol->mft_zone_end >= vol->nr_clusters) {
207 mft_zone_size >>= 1;
208 vol->mft_zone_end = vol->mft_lcn + mft_zone_size;
209 }
210 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_end = %x\n",
211 vol->mft_zone_end);
212 /*
213 * Set the current position within each data zone to the start of the
214 * respective zone.
215 */
216 vol->data1_zone_pos = vol->mft_zone_end;
217 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->data1_zone_pos = %x\n",
218 vol->data1_zone_pos);
219 vol->data2_zone_pos = (ntfs_cluster_t)0;
220 ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->data2_zone_pos = %x\n",
221 vol->data2_zone_pos);
222 /* Set the mft data allocation position to mft record 24. */
223 vol->mft_data_pos = 24UL;
224 /* This will be initialized later. */
225 vol->upcase = 0;
226 vol->upcase_length = 0;
227 vol->mft_ino = 0;
228 return 0;
229 }
230
231 static void ntfs_init_upcase(ntfs_inode *upcase)
232 {
233 ntfs_io io;
234 #define UPCASE_LENGTH 256
235 upcase->vol->upcase = ntfs_malloc(UPCASE_LENGTH << 1);
236 if (!upcase->vol->upcase)
237 return;
238 io.fn_put = ntfs_put;
239 io.fn_get = 0;
240 io.param = (char*)upcase->vol->upcase;
241 io.size = UPCASE_LENGTH << 1;
242 ntfs_read_attr(upcase, upcase->vol->at_data, 0, 0, &io);
243 upcase->vol->upcase_length = io.size >> 1;
244 }
245
246 static int process_attrdef(ntfs_inode* attrdef, ntfs_u8* def)
247 {
248 int type = NTFS_GETU32(def+0x80);
249 int check_type = 0;
250 ntfs_volume *vol = attrdef->vol;
251 ntfs_u16* name = (ntfs_u16*)def;
252
253 if (!type) {
254 ntfs_debug(DEBUG_OTHER, "process_atrdef: finished processing "
255 "and returning 1\n");
256 return 1;
257 }
258 if (ntfs_ua_strncmp(name, "$STANDARD_INFORMATION", 64) == 0) {
259 vol->at_standard_information = type;
260 check_type = 0x10;
261 } else if (ntfs_ua_strncmp(name, "$ATTRIBUTE_LIST", 64) == 0) {
262 vol->at_attribute_list = type;
263 check_type = 0x20;
264 } else if (ntfs_ua_strncmp(name, "$FILE_NAME", 64) == 0) {
265 vol->at_file_name = type;
266 check_type = 0x30;
267 } else if (ntfs_ua_strncmp(name, "$VOLUME_VERSION", 64) == 0) {
268 vol->at_volume_version = type;
269 check_type = 0x40;
270 } else if (ntfs_ua_strncmp(name, "$SECURITY_DESCRIPTOR", 64) == 0) {
271 vol->at_security_descriptor = type;
272 check_type = 0x50;
273 } else if (ntfs_ua_strncmp(name, "$VOLUME_NAME", 64) == 0) {
274 vol->at_volume_name = type;
275 check_type = 0x60;
276 } else if (ntfs_ua_strncmp(name, "$VOLUME_INFORMATION", 64) == 0) {
277 vol->at_volume_information = type;
278 check_type = 0x70;
279 } else if (ntfs_ua_strncmp(name, "$DATA", 64) == 0) {
280 vol->at_data = type;
281 check_type = 0x80;
282 } else if (ntfs_ua_strncmp(name, "$INDEX_ROOT", 64) == 0) {
283 vol->at_index_root = type;
284 check_type = 0x90;
285 } else if (ntfs_ua_strncmp(name, "$INDEX_ALLOCATION", 64) == 0) {
286 vol->at_index_allocation = type;
287 check_type = 0xA0;
288 } else if (ntfs_ua_strncmp(name, "$BITMAP", 64) == 0) {
289 vol->at_bitmap = type;
290 check_type = 0xB0;
291 } else if (ntfs_ua_strncmp(name, "$SYMBOLIC_LINK", 64) == 0 ||
292 ntfs_ua_strncmp(name, "$REPARSE_POINT", 64) == 0) {
293 vol->at_symlink = type;
294 check_type = 0xC0;
295 }
296 if (check_type && check_type != type) {
297 ntfs_error("process_attrdef: unexpected type 0x%x for 0x%x\n",
298 type, check_type);
299 return -EINVAL;
300 }
301 ntfs_debug(DEBUG_OTHER, "process_attrdef: found %s attribute of type "
302 "0x%x\n", check_type ? "known" : "unknown", type);
303 return 0;
304 }
305
306 int ntfs_init_attrdef(ntfs_inode* attrdef)
307 {
308 ntfs_u8 *buf;
309 ntfs_io io;
310 __s64 offset;
311 unsigned i;
312 int error;
313 ntfs_attribute *data;
314
315 ntfs_debug(DEBUG_BSD, "Entered ntfs_init_attrdef()\n");
316 buf = ntfs_malloc(4050); /* 90*45 */
317 if (!buf)
318 return -ENOMEM;
319 io.fn_put = ntfs_put;
320 io.fn_get = ntfs_get;
321 io.do_read = 1;
322 offset = 0;
323 data = ntfs_find_attr(attrdef, attrdef->vol->at_data, 0);
324 ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after call to "
325 "ntfs_find_attr.\n");
326 if (!data) {
327 ntfs_free(buf);
328 return -EINVAL;
329 }
330 do {
331 io.param = buf;
332 io.size = 4050;
333 ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() going to call "
334 "ntfs_readwrite_attr.\n");
335 error = ntfs_readwrite_attr(attrdef, data, offset, &io);
336 ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after call to "
337 "ntfs_readwrite_attr.\n");
338 for (i = 0; !error && i <= io.size - 0xA0; i += 0xA0) {
339 ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() going "
340 "to call process_attrdef.\n");
341 error = process_attrdef(attrdef, buf + i);
342 ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after "
343 "call to process_attrdef.\n");
344 }
345 offset += 4096;
346 } while (!error && io.size);
347 ntfs_debug(DEBUG_BSD, "Exiting ntfs_init_attrdef()\n");
348 ntfs_free(buf);
349 return error == 1 ? 0 : error;
350 }
351
352 /* ntfs_get_version will determine the NTFS version of the volume and will
353 * return the version in a BCD format, with the MSB being the major version
354 * number and the LSB the minor one. Otherwise return <0 on error.
355 * Example: version 3.1 will be returned as 0x0301. This has the obvious
356 * limitation of not coping with version numbers above 0x80 but that shouldn't
357 * be a problem... */
358 int ntfs_get_version(ntfs_inode* volume)
359 {
360 ntfs_attribute *volinfo;
361
362 volinfo = ntfs_find_attr(volume, volume->vol->at_volume_information, 0);
363 if (!volinfo)
364 return -EINVAL;
365 if (!volinfo->resident) {
366 ntfs_error("Volume information attribute is not resident!\n");
367 return -EINVAL;
368 }
369 return ((ntfs_u8*)volinfo->d.data)[8] << 8 |
370 ((ntfs_u8*)volinfo->d.data)[9];
371 }
372
373 int ntfs_load_special_files(ntfs_volume *vol)
374 {
375 int error;
376 ntfs_inode upcase, attrdef, volume;
377
378 vol->mft_ino = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
379 vol->mftmirr = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
380 vol->bitmap = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
381 vol->ino_flags = 4 | 2 | 1;
382 error = -ENOMEM;
383 ntfs_debug(DEBUG_BSD, "Going to load MFT\n");
384 if (!vol->mft_ino || (error = ntfs_init_inode(vol->mft_ino, vol,
385 FILE_Mft))) {
386 ntfs_error("Problem loading MFT\n");
387 return error;
388 }
389 ntfs_debug(DEBUG_BSD, "Going to load MIRR\n");
390 if ((error = ntfs_init_inode(vol->mftmirr, vol, FILE_MftMirr))) {
391 ntfs_error("Problem %d loading MFTMirr\n", error);
392 return error;
393 }
394 ntfs_debug(DEBUG_BSD, "Going to load BITMAP\n");
395 if ((error = ntfs_init_inode(vol->bitmap, vol, FILE_BitMap))) {
396 ntfs_error("Problem loading Bitmap\n");
397 return error;
398 }
399 ntfs_debug(DEBUG_BSD, "Going to load UPCASE\n");
400 error = ntfs_init_inode(&upcase, vol, FILE_UpCase);
401 if (error)
402 return error;
403 ntfs_init_upcase(&upcase);
404 ntfs_clear_inode(&upcase);
405 ntfs_debug(DEBUG_BSD, "Going to load ATTRDEF\n");
406 error = ntfs_init_inode(&attrdef, vol, FILE_AttrDef);
407 if (error)
408 return error;
409 error = ntfs_init_attrdef(&attrdef);
410 ntfs_clear_inode(&attrdef);
411 if (error)
412 return error;
413
414 /* Check for NTFS version and if Win2k version (ie. 3.0+) do not allow
415 * write access since the driver write support is broken. */
416 ntfs_debug(DEBUG_BSD, "Going to load VOLUME\n");
417 error = ntfs_init_inode(&volume, vol, FILE_Volume);
418 if (error)
419 return error;
420 if ((error = ntfs_get_version(&volume)) >= 0x0300 &&
421 !(NTFS_SB(vol)->s_flags & MS_RDONLY)) {
422 NTFS_SB(vol)->s_flags |= MS_RDONLY;
423 ntfs_error("Warning! NTFS volume version is Win2k+: Mounting "
424 "read-only\n");
425 }
426 ntfs_clear_inode(&volume);
427 if (error < 0)
428 return error;
429 ntfs_debug(DEBUG_BSD, "NTFS volume is v%d.%d\n", error >> 8,
430 error & 0xff);
431 return 0;
432 }
433
434 int ntfs_release_volume(ntfs_volume *vol)
435 {
436 if (((vol->ino_flags & 1) == 1) && vol->mft_ino) {
437 ntfs_clear_inode(vol->mft_ino);
438 ntfs_free(vol->mft_ino);
439 vol->mft_ino = 0;
440 }
441 if (((vol->ino_flags & 2) == 2) && vol->mftmirr) {
442 ntfs_clear_inode(vol->mftmirr);
443 ntfs_free(vol->mftmirr);
444 vol->mftmirr = 0;
445 }
446 if (((vol->ino_flags & 4) == 4) && vol->bitmap) {
447 ntfs_clear_inode(vol->bitmap);
448 ntfs_free(vol->bitmap);
449 vol->bitmap = 0;
450 }
451 ntfs_free(vol->mft);
452 ntfs_free(vol->upcase);
453 return 0;
454 }
455
456 /*
457 * Writes the volume size (units of clusters) into vol_size.
458 * Returns 0 if successful or error.
459 */
460 int ntfs_get_volumesize(ntfs_volume *vol, ntfs_s64 *vol_size)
461 {
462 ntfs_io io;
463 char *cluster0;
464
465 if (!vol_size)
466 return -EFAULT;
467 cluster0 = ntfs_malloc(vol->cluster_size);
468 if (!cluster0)
469 return -ENOMEM;
470 io.fn_put = ntfs_put;
471 io.fn_get = ntfs_get;
472 io.param = cluster0;
473 io.do_read = 1;
474 io.size = vol->cluster_size;
475 ntfs_getput_clusters(vol, 0, 0, &io);
476 *vol_size = NTFS_GETU64(cluster0 + 0x28) >>
477 (ffs(NTFS_GETU8(cluster0 + 0xD)) - 1);
478 ntfs_free(cluster0);
479 return 0;
480 }
481
482 static int nc[16]={4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0};
483
484 int ntfs_get_free_cluster_count(ntfs_inode *bitmap)
485 {
486 ntfs_io io;
487 int offset, error, clusters;
488 unsigned char *bits = ntfs_malloc(2048);
489 if (!bits)
490 return -ENOMEM;
491 offset = clusters = 0;
492 io.fn_put = ntfs_put;
493 io.fn_get = ntfs_get;
494 while (1) {
495 register int i;
496 io.param = bits;
497 io.size = 2048;
498 error = ntfs_read_attr(bitmap, bitmap->vol->at_data, 0, offset,
499 &io);
500 if (error || io.size == 0)
501 break;
502 /* I never thought I would do loop unrolling some day */
503 for (i = 0; i < io.size - 8; ) {
504 clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
505 clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
506 clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
507 clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
508 clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
509 clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
510 clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
511 clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
512 }
513 while (i < io.size) {
514 clusters += nc[bits[i] >> 4];
515 clusters += nc[bits[i++] & 0xF];
516 }
517 offset += io.size;
518 }
519 ntfs_free(bits);
520 return clusters;
521 }
522
523 /*
524 * Insert the fixups for the record. The number and location of the fixes
525 * is obtained from the record header but we double check with @rec_size and
526 * use that as the upper boundary, if necessary overwriting the count value in
527 * the record header.
528 *
529 * We return 0 on success or -1 if fixup header indicated the beginning of the
530 * update sequence array to be beyond the valid limit.
531 */
532 int ntfs_insert_fixups(unsigned char *rec, int rec_size)
533 {
534 int first;
535 int count;
536 int offset = -2;
537 ntfs_u16 fix;
538
539 first = NTFS_GETU16(rec + 4);
540 count = (rec_size >> NTFS_SECTOR_BITS) + 1;
541 if (first + count * 2 > NTFS_SECTOR_SIZE - 2) {
542 printk(KERN_CRIT "NTFS: ntfs_insert_fixups() detected corrupt "
543 "NTFS record update sequence array position. - "
544 "Cannot hotfix.\n");
545 return -1;
546 }
547 if (count != NTFS_GETU16(rec + 6)) {
548 printk(KERN_ERR "NTFS: ntfs_insert_fixups() detected corrupt "
549 "NTFS record update sequence array size. - "
550 "Applying hotfix.\n");
551 NTFS_PUTU16(rec + 6, count);
552 }
553 fix = (NTFS_GETU16(rec + first) + 1) & 0xffff;
554 if (fix == 0xffff || !fix)
555 fix = 1;
556 NTFS_PUTU16(rec + first, fix);
557 count--;
558 while (count--) {
559 first += 2;
560 offset += NTFS_SECTOR_SIZE;
561 NTFS_PUTU16(rec + first, NTFS_GETU16(rec + offset));
562 NTFS_PUTU16(rec + offset, fix);
563 }
564 return 0;
565 }
566
567 /**
568 * ntfs_allocate_clusters - allocate logical clusters on an ntfs volume
569 * @vol: volume on which to allocate clusters
570 * @location: preferred location for first allocated cluster
571 * @count: number of clusters to allocate
572 * @rl: address of pointer in which to return the allocated run list
573 * @rl_len: the number of elements returned in @*rl
574 *
575 * Allocate @*count clusters (LCNs), preferably beginning at @*location in the
576 * bitmap of the volume @vol. If @*location is -1, it does not matter where the
577 * clusters are. @rl is the address of a ntfs_runlist pointer which this
578 * function will allocate and fill with the runlist of the allocated clusters.
579 * It is the callers responsibility to ntfs_vfree() @*rl after she is finished
580 * with it. If the function was not successful, @*rl will be set to NULL.
581 * @*rl_len will contain the number of ntfs_runlist elements in @*rl or 0 if
582 * @*rl is NULL.
583 *
584 * Return 0 on success, or -errno on error. On success, @*location and @*count
585 * say what was really allocated. On -ENOSPC, @*location and @*count say what
586 * could have been allocated. If nothing could be allocated or a different
587 * error occured, @*location = -1 and @*count = 0.
588 *
589 * There are two data zones. First is the area between the end of the mft zone
590 * and the end of the volume, and second is the area between the start of the
591 * volume and the start of the mft zone. On unmodified/standard volumes, the
592 * second mft zone doesn't exist due to the mft zone being expanded to cover
593 * the start of volume in order to reserve space for the mft bitmap attribute.
594 *
595 * This is not the prettiest function but the complexity stems from the need of
596 * implementing the mft vs data zoned approach and from the fact that we have
597 * access to the lcn bitmap in portions of PAGE_SIZE bytes at a time, so we
598 * need to cope with crossing over boundaries of two pages. Further, the fact
599 * that the allocator allows for caller supplied hints as to the location of
600 * where allocation should begin and the fact that the allocator keeps track of
601 * where in the data zones the next natural allocation should occur, contribute
602 * to the complexity of the function. But it should all be worthwhile, because
603 * this allocator should: 1) be a full implementation of the MFT zone approach
604 * used by Windows, 2) cause reduction in fragmentation as much as possible,
605 * and 3) be speedy in allocations (the code is not optimized for speed, but
606 * the algorithm is, so further speed improvements are probably possible).
607 *
608 * FIXME: Really need finer-grained locking but this will do for the moment. I
609 * just want to kill all races and have a working allocator. When that is done,
610 * we can beautify... (AIA)
611 *
612 * FIXME: We should be monitoring cluster allocation and increment the MFT zone
613 * size dynamically but this is something for the future. We will just cause
614 * heavier fragmentation by not doing it and I am not even sure Windows would
615 * grow the MFT zone dynamically, so might even be correct not doing this. The
616 * overhead in doing dynamic MFT zone expansion would be very large and unlikely
617 * worth the effort. (AIA)
618 *
619 * TODO: I have added in double the required zone position pointer wrap around
620 * logic which can be optimized to having only one of the two logic sets.
621 * However, having the double logic will work fine, but if we have only one of
622 * the sets and we get it wrong somewhere, then we get into trouble, so
623 * removing the duplicate logic requires _very_ careful consideration of _all_
624 * possible code paths. So at least for now, I am leaving the double logic -
625 * better safe than sorry... (AIA)
626 */
627 int ntfs_allocate_clusters(ntfs_volume *vol, ntfs_cluster_t *location,
628 ntfs_cluster_t *count, ntfs_runlist **rl, int *rl_len,
629 const NTFS_CLUSTER_ALLOCATION_ZONES zone)
630 {
631 ntfs_runlist *rl2 = NULL, *rlt;
632 ntfs_attribute *data;
633 ntfs_cluster_t buf_pos, zone_start, zone_end, mft_zone_size;
634 ntfs_cluster_t lcn, last_read_pos, prev_lcn = (ntfs_cluster_t)0;
635 ntfs_cluster_t initial_location, prev_run_len = (ntfs_cluster_t)0;
636 ntfs_cluster_t clusters = (ntfs_cluster_t)0;
637 unsigned char *buf, *byte, bit, search_zone, done_zones;
638 unsigned char pass, need_writeback;
639 int rlpos = 0, rlsize, buf_size, err = 0;
640 ntfs_io io;
641
642 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Entering with *location = "
643 "0x%x, *count = 0x%x, zone = %s_ZONE.\n", *location,
644 *count, zone == DATA_ZONE ? "DATA" : "MFT");
645 buf = (char*)__get_free_page(GFP_NOFS);
646 if (!buf) {
647 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Returning "
648 "-ENOMEM.\n");
649 return -ENOMEM;
650 }
651 io.fn_put = ntfs_put;
652 io.fn_get = ntfs_get;
653 lock_kernel();
654 /* Get the $DATA attribute of $Bitmap. */
655 data = ntfs_find_attr(vol->bitmap, vol->at_data, 0);
656 if (!data) {
657 err = -EINVAL;
658 goto err_ret;
659 }
660 /*
661 * If no specific location was requested, use the current data zone
662 * position, otherwise use the requested location but make sure it lies
663 * outside the mft zone. Also set done_zones to 0 (no zones done) and
664 * pass depending on whether we are starting inside a zone (1) or
665 * at the beginning of a zone (2). If requesting from the MFT_ZONE, then
666 * we either start at the current position within the mft zone or at the
667 * specified position and if the latter is out of bounds then we start
668 * at the beginning of the MFT_ZONE.
669 */
670 done_zones = 0;
671 pass = 1;
672 /*
673 * zone_start and zone_end are the current search range. search_zone
674 * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of
675 * volume) and 4 for data zone 2 (start of volume till start of mft
676 * zone).
677 */
678 zone_start = *location;
679 if (zone_start < 0) {
680 if (zone == DATA_ZONE)
681 zone_start = vol->data1_zone_pos;
682 else
683 zone_start = vol->mft_zone_pos;
684 if (!zone_start)
685 /*
686 * Zone starts at beginning of volume which means a
687 * single pass is sufficient.
688 */
689 pass = 2;
690 } else if (zone_start >= vol->mft_zone_start && zone_start <
691 vol->mft_zone_end && zone == DATA_ZONE) {
692 zone_start = vol->mft_zone_end;
693 pass = 2;
694 } else if ((zone_start < vol->mft_zone_start || zone_start >=
695 vol->mft_zone_end) && zone == MFT_ZONE) {
696 zone_start = vol->mft_lcn;
697 if (!vol->mft_zone_end)
698 zone_start = (ntfs_cluster_t)0;
699 pass = 2;
700 }
701 if (zone == DATA_ZONE) {
702 /* Skip searching the mft zone. */
703 done_zones |= 1;
704 if (zone_start >= vol->mft_zone_end) {
705 zone_end = vol->nr_clusters;
706 search_zone = 2;
707 } else {
708 zone_end = vol->mft_zone_start;
709 search_zone = 4;
710 }
711 } else /* if (zone == MFT_ZONE) */ {
712 zone_end = vol->mft_zone_end;
713 search_zone = 1;
714 }
715 /*
716 * buf_pos is the current bit position inside the bitmap. We use
717 * initial_location to determine whether or not to do a zone switch.
718 */
719 buf_pos = initial_location = zone_start;
720 /* Loop until all clusters are allocated, i.e. clusters == 0. */
721 clusters = *count;
722 rlpos = rlsize = 0;
723 if (*count <= 0) {
724 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *count <= 0, "
725 "returning -EINVAL.\n");
726 err = -EINVAL;
727 goto err_ret;
728 }
729 while (1) {
730 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Start of outer while "
731 "loop: done_zones = 0x%x, search_zone = %i, "
732 "pass = %i, zone_start = 0x%x, zone_end = "
733 "0x%x, initial_location = 0x%x, buf_pos = "
734 "0x%x, rlpos = %i, rlsize = %i.\n",
735 done_zones, search_zone, pass, zone_start,
736 zone_end, initial_location, buf_pos, rlpos,
737 rlsize);
738 /* Loop until we run out of free clusters. */
739 io.param = buf;
740 io.size = PAGE_SIZE;
741 io.do_read = 1;
742 last_read_pos = buf_pos >> 3;
743 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): last_read_pos = "
744 "0x%x.\n", last_read_pos);
745 err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
746 &io);
747 if (err) {
748 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
749 "ntfs_read_attr failed with error "
750 "code %i, going to err_ret.\n", -err);
751 goto err_ret;
752 }
753 if (!io.size) {
754 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): !io.size, "
755 "going to zone_pass_done.\n");
756 goto zone_pass_done;
757 }
758 buf_size = io.size << 3;
759 lcn = buf_pos & 7;
760 buf_pos &= ~7;
761 need_writeback = 0;
762 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Before inner while "
763 "loop: buf_size = 0x%x, lcn = 0x%x, buf_pos = "
764 "0x%x, need_writeback = %i.\n", buf_size, lcn,
765 buf_pos, need_writeback);
766 while (lcn < buf_size && lcn + buf_pos < zone_end) {
767 byte = buf + (lcn >> 3);
768 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): In inner "
769 "while loop: buf_size = 0x%x, lcn = "
770 "0x%x, buf_pos = 0x%x, need_writeback "
771 "= %i, byte ofs = 0x%x, *byte = "
772 "0x%x.\n", buf_size, lcn, buf_pos,
773 need_writeback, lcn >> 3, *byte);
774 /* Skip full bytes. */
775 if (*byte == 0xff) {
776 lcn += 8;
777 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
778 "continuing while loop 1.\n");
779 continue;
780 }
781 bit = 1 << (lcn & 7);
782 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): bit = %i.\n",
783 bit);
784 /* If the bit is already set, go onto the next one. */
785 if (*byte & bit) {
786 lcn++;
787 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
788 "continuing while loop 2.\n");
789 continue;
790 }
791 /* Allocate the bitmap bit. */
792 *byte |= bit;
793 /* We need to write this bitmap buffer back to disk! */
794 need_writeback = 1;
795 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *byte = "
796 "0x%x, need_writeback = %i.\n", *byte,
797 need_writeback);
798 /* Reallocate memory if necessary. */
799 if ((rlpos + 2) * sizeof(ntfs_runlist) >= rlsize) {
800 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
801 "Reallocating space.\n");
802 /* Setup first free bit return value. */
803 if (!rl2) {
804 *location = lcn + buf_pos;
805 ntfs_debug(DEBUG_OTHER, __FUNCTION__
806 "(): *location = "
807 "0x%x.\n", *location);
808 }
809 rlsize += PAGE_SIZE;
810 rlt = ntfs_vmalloc(rlsize);
811 if (!rlt) {
812 err = -ENOMEM;
813 ntfs_debug(DEBUG_OTHER, __FUNCTION__
814 "(): Failed to "
815 "allocate memory, "
816 "returning -ENOMEM, "
817 "going to "
818 "wb_err_ret.\n");
819 goto wb_err_ret;
820 }
821 if (rl2) {
822 ntfs_memcpy(rlt, rl2, rlsize -
823 PAGE_SIZE);
824 ntfs_vfree(rl2);
825 }
826 rl2 = rlt;
827 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
828 "Reallocated memory, rlsize = "
829 "0x%x.\n", rlsize);
830 }
831 /*
832 * Coalesce with previous run if adjacent LCNs.
833 * Otherwise, append a new run.
834 */
835 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Adding run "
836 "(lcn 0x%x, len 0x%x), prev_lcn = "
837 "0x%x, lcn = 0x%x, buf_pos = 0x%x, "
838 "prev_run_len = 0x%x, rlpos = %i.\n",
839 lcn + buf_pos, 1, prev_lcn, lcn,
840 buf_pos, prev_run_len, rlpos);
841 if (prev_lcn == lcn + buf_pos - prev_run_len && rlpos) {
842 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
843 "Coalescing to run (lcn 0x%x, "
844 "len 0x%x).\n",
845 rl2[rlpos - 1].lcn,
846 rl2[rlpos - 1].len);
847 rl2[rlpos - 1].len = ++prev_run_len;
848 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
849 "Run now (lcn 0x%x, len 0x%x), "
850 "prev_run_len = 0x%x.\n",
851 rl2[rlpos - 1].lcn,
852 rl2[rlpos - 1].len,
853 prev_run_len);
854 } else {
855 if (rlpos)
856 ntfs_debug(DEBUG_OTHER, __FUNCTION__
857 "(): Adding new run, "
858 "(previous run lcn "
859 "0x%x, len 0x%x).\n",
860 rl2[rlpos - 1].lcn,
861 rl2[rlpos - 1].len);
862 else
863 ntfs_debug(DEBUG_OTHER, __FUNCTION__
864 "(): Adding new run, "
865 "is first run.\n");
866 rl2[rlpos].lcn = prev_lcn = lcn + buf_pos;
867 rl2[rlpos].len = prev_run_len =
868 (ntfs_cluster_t)1;
869
870 rlpos++;
871 }
872 /* Done? */
873 if (!--clusters) {
874 ntfs_cluster_t tc;
875 /*
876 * Update the current zone position. Positions
877 * of already scanned zones have been updated
878 * during the respective zone switches.
879 */
880 tc = lcn + buf_pos + 1;
881 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
882 "Done. Updating current zone "
883 "position, tc = 0x%x, "
884 "search_zone = %i.\n", tc,
885 search_zone);
886 switch (search_zone) {
887 case 1:
888 ntfs_debug(DEBUG_OTHER, __FUNCTION__
889 "(): Before checks, "
890 "vol->mft_zone_pos = "
891 "0x%x.\n",
892 vol->mft_zone_pos);
893 if (tc >= vol->mft_zone_end) {
894 vol->mft_zone_pos =
895 vol->mft_lcn;
896 if (!vol->mft_zone_end)
897 vol->mft_zone_pos =
898 (ntfs_cluster_t)0;
899 } else if ((initial_location >=
900 vol->mft_zone_pos ||
901 tc > vol->mft_zone_pos)
902 && tc >= vol->mft_lcn)
903 vol->mft_zone_pos = tc;
904 ntfs_debug(DEBUG_OTHER, __FUNCTION__
905 "(): After checks, "
906 "vol->mft_zone_pos = "
907 "0x%x.\n",
908 vol->mft_zone_pos);
909 break;
910 case 2:
911 ntfs_debug(DEBUG_OTHER, __FUNCTION__
912 "(): Before checks, "
913 "vol->data1_zone_pos = "
914 "0x%x.\n",
915 vol->data1_zone_pos);
916 if (tc >= vol->nr_clusters)
917 vol->data1_zone_pos =
918 vol->mft_zone_end;
919 else if ((initial_location >=
920 vol->data1_zone_pos ||
921 tc > vol->data1_zone_pos)
922 && tc >= vol->mft_zone_end)
923 vol->data1_zone_pos = tc;
924 ntfs_debug(DEBUG_OTHER, __FUNCTION__
925 "(): After checks, "
926 "vol->data1_zone_pos = "
927 "0x%x.\n",
928 vol->data1_zone_pos);
929 break;
930 case 4:
931 ntfs_debug(DEBUG_OTHER, __FUNCTION__
932 "(): Before checks, "
933 "vol->data2_zone_pos = "
934 "0x%x.\n",
935 vol->data2_zone_pos);
936 if (tc >= vol->mft_zone_start)
937 vol->data2_zone_pos =
938 (ntfs_cluster_t)0;
939 else if (initial_location >=
940 vol->data2_zone_pos ||
941 tc > vol->data2_zone_pos)
942 vol->data2_zone_pos = tc;
943 ntfs_debug(DEBUG_OTHER, __FUNCTION__
944 "(): After checks, "
945 "vol->data2_zone_pos = "
946 "0x%x.\n",
947 vol->data2_zone_pos);
948 break;
949 default:
950 BUG();
951 }
952 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
953 "Going to done_ret.\n");
954 goto done_ret;
955 }
956 lcn++;
957 }
958 buf_pos += buf_size;
959 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After inner while "
960 "loop: buf_size = 0x%x, lcn = 0x%x, buf_pos = "
961 "0x%x, need_writeback = %i.\n", buf_size, lcn,
962 buf_pos, need_writeback);
963 if (need_writeback) {
964 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing "
965 "back.\n");
966 need_writeback = 0;
967 io.param = buf;
968 io.do_read = 0;
969 err = ntfs_readwrite_attr(vol->bitmap, data,
970 last_read_pos, &io);
971 if (err) {
972 ntfs_error(__FUNCTION__ "(): Bitmap writeback "
973 "failed in read next buffer "
974 "code path with error code "
975 "%i.\n", -err);
976 goto err_ret;
977 }
978 }
979 if (buf_pos < zone_end) {
980 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
981 "outer while loop, buf_pos = 0x%x, "
982 "zone_end = 0x%x.\n", buf_pos,
983 zone_end);
984 continue;
985 }
986 zone_pass_done: /* Finished with the current zone pass. */
987 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At zone_pass_done, "
988 "pass = %i.\n", pass);
989 if (pass == 1) {
990 /*
991 * Now do pass 2, scanning the first part of the zone
992 * we omitted in pass 1.
993 */
994 pass = 2;
995 zone_end = zone_start;
996 switch (search_zone) {
997 case 1: /* mft_zone */
998 zone_start = vol->mft_zone_start;
999 break;
1000 case 2: /* data1_zone */
1001 zone_start = vol->mft_zone_end;
1002 break;
1003 case 4: /* data2_zone */
1004 zone_start = (ntfs_cluster_t)0;
1005 break;
1006 default:
1007 BUG();
1008 }
1009 /* Sanity check. */
1010 if (zone_end < zone_start)
1011 zone_end = zone_start;
1012 buf_pos = zone_start;
1013 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
1014 "outer while loop, pass = 2, "
1015 "zone_start = 0x%x, zone_end = 0x%x, "
1016 "buf_pos = 0x%x.\n");
1017 continue;
1018 } /* pass == 2 */
1019 done_zones_check:
1020 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_zones_check, "
1021 "search_zone = %i, done_zones before = 0x%x, "
1022 "done_zones after = 0x%x.\n",
1023 search_zone, done_zones, done_zones |
1024 search_zone);
1025 done_zones |= search_zone;
1026 if (done_zones < 7) {
1027 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Switching "
1028 "zone.\n");
1029 /* Now switch to the next zone we haven't done yet. */
1030 pass = 1;
1031 switch (search_zone) {
1032 case 1:
1033 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
1034 "Switching from mft zone to "
1035 "data1 zone.\n");
1036 /* Update mft zone position. */
1037 if (rlpos) {
1038 ntfs_cluster_t tc;
1039 ntfs_debug(DEBUG_OTHER, __FUNCTION__
1040 "(): Before checks, "
1041 "vol->mft_zone_pos = "
1042 "0x%x.\n",
1043 vol->mft_zone_pos);
1044 tc = rl2[rlpos - 1].lcn +
1045 rl2[rlpos - 1].len;
1046 if (tc >= vol->mft_zone_end) {
1047 vol->mft_zone_pos =
1048 vol->mft_lcn;
1049 if (!vol->mft_zone_end)
1050 vol->mft_zone_pos =
1051 (ntfs_cluster_t)0;
1052 } else if ((initial_location >=
1053 vol->mft_zone_pos ||
1054 tc > vol->mft_zone_pos)
1055 && tc >= vol->mft_lcn)
1056 vol->mft_zone_pos = tc;
1057 ntfs_debug(DEBUG_OTHER, __FUNCTION__
1058 "(): After checks, "
1059 "vol->mft_zone_pos = "
1060 "0x%x.\n",
1061 vol->mft_zone_pos);
1062 }
1063 /* Switch from mft zone to data1 zone. */
1064 switch_to_data1_zone: search_zone = 2;
1065 zone_start = initial_location =
1066 vol->data1_zone_pos;
1067 zone_end = vol->nr_clusters;
1068 if (zone_start == vol->mft_zone_end)
1069 pass = 2;
1070 if (zone_start >= zone_end) {
1071 vol->data1_zone_pos = zone_start =
1072 vol->mft_zone_end;
1073 pass = 2;
1074 }
1075 break;
1076 case 2:
1077 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
1078 "Switching from data1 zone to "
1079 "data2 zone.\n");
1080 /* Update data1 zone position. */
1081 if (rlpos) {
1082 ntfs_cluster_t tc;
1083 ntfs_debug(DEBUG_OTHER, __FUNCTION__
1084 "(): Before checks, "
1085 "vol->data1_zone_pos = "
1086 "0x%x.\n",
1087 vol->data1_zone_pos);
1088 tc = rl2[rlpos - 1].lcn +
1089 rl2[rlpos - 1].len;
1090 if (tc >= vol->nr_clusters)
1091 vol->data1_zone_pos =
1092 vol->mft_zone_end;
1093 else if ((initial_location >=
1094 vol->data1_zone_pos ||
1095 tc > vol->data1_zone_pos)
1096 && tc >= vol->mft_zone_end)
1097 vol->data1_zone_pos = tc;
1098 ntfs_debug(DEBUG_OTHER, __FUNCTION__
1099 "(): After checks, "
1100 "vol->data1_zone_pos = "
1101 "0x%x.\n",
1102 vol->data1_zone_pos);
1103 }
1104 /* Switch from data1 zone to data2 zone. */
1105 search_zone = 4;
1106 zone_start = initial_location =
1107 vol->data2_zone_pos;
1108 zone_end = vol->mft_zone_start;
1109 if (!zone_start)
1110 pass = 2;
1111 if (zone_start >= zone_end) {
1112 vol->data2_zone_pos = zone_start =
1113 initial_location =
1114 (ntfs_cluster_t)0;
1115 pass = 2;
1116 }
1117 break;
1118 case 4:
1119 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
1120 "Switching from data2 zone to "
1121 "data1 zone.\n");
1122 /* Update data2 zone position. */
1123 if (rlpos) {
1124 ntfs_cluster_t tc;
1125 ntfs_debug(DEBUG_OTHER, __FUNCTION__
1126 "(): Before checks, "
1127 "vol->data2_zone_pos = "
1128 "0x%x.\n",
1129 vol->data2_zone_pos);
1130 tc = rl2[rlpos - 1].lcn +
1131 rl2[rlpos - 1].len;
1132 if (tc >= vol->mft_zone_start)
1133 vol->data2_zone_pos =
1134 (ntfs_cluster_t)0;
1135 else if (initial_location >=
1136 vol->data2_zone_pos ||
1137 tc > vol->data2_zone_pos)
1138 vol->data2_zone_pos = tc;
1139 ntfs_debug(DEBUG_OTHER, __FUNCTION__
1140 "(): After checks, "
1141 "vol->data2_zone_pos = "
1142 "0x%x.\n",
1143 vol->data2_zone_pos);
1144 }
1145 /* Switch from data2 zone to data1 zone. */
1146 goto switch_to_data1_zone; /* See above. */
1147 default:
1148 BUG();
1149 }
1150 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After zone "
1151 "switch, search_zone = %i, pass = %i, "
1152 "initial_location = 0x%x, zone_start "
1153 "= 0x%x, zone_end = 0x%x.\n",
1154 search_zone, pass, initial_location,
1155 zone_start, zone_end);
1156 buf_pos = zone_start;
1157 if (zone_start == zone_end) {
1158 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
1159 "Empty zone, going to "
1160 "done_zones_check.\n");
1161 /* Empty zone. Don't bother searching it. */
1162 goto done_zones_check;
1163 }
1164 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
1165 "outer while loop.\n");
1166 continue;
1167 } /* done_zones == 7 */
1168 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): All zones are "
1169 "finished.\n");
1170 /*
1171 * All zones are finished! If DATA_ZONE, shrink mft zone. If
1172 * MFT_ZONE, we have really run out of space.
1173 */
1174 mft_zone_size = vol->mft_zone_end - vol->mft_zone_start;
1175 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): vol->mft_zone_start "
1176 "= 0x%x, vol->mft_zone_end = 0x%x, "
1177 "mft_zone_size = 0x%x.\n", vol->mft_zone_start,
1178 vol->mft_zone_end, mft_zone_size);
1179 if (zone == MFT_ZONE || mft_zone_size <= (ntfs_cluster_t)0) {
1180 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): No free "
1181 "clusters left, returning -ENOSPC, "
1182 "going to fail_ret.\n");
1183 /* Really no more space left on device. */
1184 err = -ENOSPC;
1185 goto fail_ret;
1186 } /* zone == DATA_ZONE && mft_zone_size > 0 */
1187 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Shrinking mft "
1188 "zone.\n");
1189 zone_end = vol->mft_zone_end;
1190 mft_zone_size >>= 1;
1191 if (mft_zone_size > (ntfs_cluster_t)0)
1192 vol->mft_zone_end = vol->mft_zone_start + mft_zone_size;
1193 else /* mft zone and data2 zone no longer exist. */
1194 vol->data2_zone_pos = vol->mft_zone_start =
1195 vol->mft_zone_end = (ntfs_cluster_t)0;
1196 if (vol->mft_zone_pos >= vol->mft_zone_end) {
1197 vol->mft_zone_pos = vol->mft_lcn;
1198 if (!vol->mft_zone_end)
1199 vol->mft_zone_pos = (ntfs_cluster_t)0;
1200 }
1201 buf_pos = zone_start = initial_location =
1202 vol->data1_zone_pos = vol->mft_zone_end;
1203 search_zone = 2;
1204 pass = 2;
1205 done_zones &= ~2;
1206 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After shrinking mft "
1207 "zone, mft_zone_size = 0x%x, "
1208 "vol->mft_zone_start = 0x%x, vol->mft_zone_end "
1209 "= 0x%x, vol->mft_zone_pos = 0x%x, search_zone "
1210 "= 2, pass = 2, dones_zones = 0x%x, zone_start "
1211 "= 0x%x, zone_end = 0x%x, vol->data1_zone_pos "
1212 "= 0x%x, continuing outer while loop.\n",
1213 mft_zone_size, vol->mft_zone_start,
1214 vol->mft_zone_end, vol->mft_zone_pos,
1215 search_zone, pass, done_zones, zone_start,
1216 zone_end, vol->data1_zone_pos);
1217 }
1218 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After outer while loop.\n");
1219 done_ret:
1220 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_ret.\n");
1221 rl2[rlpos].lcn = (ntfs_cluster_t)-1;
1222 rl2[rlpos].len = (ntfs_cluster_t)0;
1223 *rl = rl2;
1224 *rl_len = rlpos;
1225 if (need_writeback) {
1226 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing back.\n");
1227 need_writeback = 0;
1228 io.param = buf;
1229 io.do_read = 0;
1230 err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
1231 &io);
1232 if (err) {
1233 ntfs_error(__FUNCTION__ "(): Bitmap writeback failed "
1234 "in done code path with error code "
1235 "%i.\n", -err);
1236 goto err_ret;
1237 }
1238 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Wrote 0x%Lx bytes.\n",
1239 io.size);
1240 }
1241 done_fail_ret:
1242 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_fail_ret (follows "
1243 "done_ret).\n");
1244 unlock_kernel();
1245 free_page((unsigned long)buf);
1246 if (err)
1247 ntfs_debug(DEBUG_FILE3, __FUNCTION__ "(): Failed to allocate "
1248 "clusters. Returning with error code %i.\n",
1249 -err);
1250 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Syncing $Bitmap inode.\n");
1251 if (ntfs_update_inode(vol->bitmap))
1252 ntfs_error(__FUNCTION__ "(): Failed to sync inode $Bitmap. "
1253 "Continuing anyway.\n");
1254 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Returning with code %i.\n",
1255 err);
1256 return err;
1257 fail_ret:
1258 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At fail_ret.\n");
1259 if (rl2) {
1260 if (err == -ENOSPC) {
1261 /* Return first free lcn and count of free clusters. */
1262 *location = rl2[0].lcn;
1263 *count -= clusters;
1264 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): err = "
1265 "-ENOSPC, *location = 0x%x, *count = "
1266 "0x%x.\n", *location, *count);
1267 }
1268 /* Deallocate all allocated clusters. */
1269 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Deallocating "
1270 "allocated clusters.\n");
1271 ntfs_deallocate_clusters(vol, rl2, rlpos);
1272 /* Free the runlist. */
1273 ntfs_vfree(rl2);
1274 } else {
1275 if (err == -ENOSPC) {
1276 /* Nothing free at all. */
1277 *location = vol->data1_zone_pos; /* Irrelevant... */
1278 *count = 0;
1279 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): No space "
1280 "left at all, err = -ENOSPC, *location "
1281 "= 0x%x, *count = 0.\n", *location);
1282 }
1283 }
1284 *rl = NULL;
1285 *rl_len = 0;
1286 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *rl = NULL, *rl_len = 0, "
1287 "going to done_fail_ret.\n");
1288 goto done_fail_ret;
1289 wb_err_ret:
1290 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At wb_err_ret.\n");
1291 if (need_writeback) {
1292 int __err;
1293 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing back.\n");
1294 io.param = buf;
1295 io.do_read = 0;
1296 __err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
1297 &io);
1298 if (__err)
1299 ntfs_error(__FUNCTION__ "(): Bitmap writeback failed "
1300 "in error code path with error code "
1301 "%i.\n", -__err);
1302 need_writeback = 0;
1303 }
1304 err_ret:
1305 ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At err_ret, *location = -1, "
1306 "*count = 0, going to fail_ret.\n");
1307 *location = -1;
1308 *count = 0;
1309 goto fail_ret;
1310 }
1311
1312 /*
1313 * IMPORTANT: Caller has to hold big kernel lock or the race monster will come
1314 * to get you! (-;
1315 * TODO: Need our own lock for bitmap accesses but BKL is more secure for now,
1316 * considering we might not have covered all places with a lock yet. In that
1317 * case the BKL offers a one way exclusion which is better than no exclusion
1318 * at all... (AIA)
1319 */
1320 static int ntfs_clear_bitrange(ntfs_inode *bitmap,
1321 const ntfs_cluster_t start_bit, const ntfs_cluster_t count)
1322 {
1323 ntfs_cluster_t buf_size, bit, nr_bits = count;
1324 unsigned char *buf, *byte;
1325 int err;
1326 ntfs_io io;
1327
1328 io.fn_put = ntfs_put;
1329 io.fn_get = ntfs_get;
1330 /* Calculate the required buffer size in bytes. */
1331 buf_size = (ntfs_cluster_t)((start_bit & 7) + nr_bits + 7) >> 3;
1332 if (buf_size <= (ntfs_cluster_t)(64 * 1024))
1333 buf = ntfs_malloc(buf_size);
1334 else
1335 buf = ntfs_vmalloc(buf_size);
1336 if (!buf)
1337 return -ENOMEM;
1338 /* Read the bitmap from the data attribute. */
1339 io.param = byte = buf;
1340 io.size = buf_size;
1341 err = ntfs_read_attr(bitmap, bitmap->vol->at_data, 0, start_bit >> 3,
1342 &io);
1343 if (err || io.size != buf_size)
1344 goto err_out;
1345 /* Now clear the bits in the read bitmap. */
1346 bit = start_bit & 7;
1347 while (bit && nr_bits) { /* Process first partial byte, if present. */
1348 *byte &= ~(1 << bit++);
1349 nr_bits--;
1350 bit &= 7;
1351 if (!bit)
1352 byte++;
1353 }
1354 while (nr_bits >= 8) { /* Process full bytes. */
1355 *byte = 0;
1356 nr_bits -= 8;
1357 byte++;
1358 }
1359 bit = 0;
1360 while (nr_bits) { /* Process last partial byte, if present. */
1361 *byte &= ~(1 << bit);
1362 nr_bits--;
1363 bit++;
1364 }
1365 /* Write the modified bitmap back to disk. */
1366 io.param = buf;
1367 io.size = buf_size;
1368 err = ntfs_write_attr(bitmap, bitmap->vol->at_data, 0, start_bit >> 3,
1369 &io);
1370 err_out:
1371 if (buf_size <= (ntfs_cluster_t)(64 * 1024))
1372 ntfs_free(buf);
1373 else
1374 ntfs_vfree(buf);
1375 if (!err && io.size != buf_size)
1376 err = -EIO;
1377 return err;
1378 }
1379
1380 /*
1381 * See comments for lack of zone adjustments below in the description of the
1382 * function ntfs_deallocate_clusters().
1383 */
1384 int ntfs_deallocate_cluster_run(const ntfs_volume *vol,
1385 const ntfs_cluster_t lcn, const ntfs_cluster_t len)
1386 {
1387 int err;
1388
1389 lock_kernel();
1390 err = ntfs_clear_bitrange(vol->bitmap, lcn, len);
1391 unlock_kernel();
1392 return err;
1393 }
1394
1395 /*
1396 * This is inefficient, but logically trivial, so will do for now. Note, we
1397 * do not touch the mft nor the data zones here because we want to minimize
1398 * recycling of clusters to enhance the chances of data being undeleteable.
1399 * Also we don't want the overhead. Instead we do one additional sweep of the
1400 * current data zone during cluster allocation to check for freed clusters.
1401 */
1402 int ntfs_deallocate_clusters(const ntfs_volume *vol, const ntfs_runlist *rl,
1403 const int rl_len)
1404 {
1405 int i, err;
1406
1407 lock_kernel();
1408 for (i = err = 0; i < rl_len && !err; i++)
1409 err = ntfs_clear_bitrange(vol->bitmap, rl[i].lcn, rl[i].len);
1410 unlock_kernel();
1411 return err;
1412 }
1413
1414