1 /*
2 libparted
3 Copyright (C) 1998, 1999, 2000, 2002, 2007 Free Software Foundation, Inc.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <config.h>
20 #include "fat.h"
21
22 #ifndef DISCOVER_ONLY
23
24 /* returns the minimum size of clusters for a given file system type */
25 PedSector
26 fat_min_cluster_size (FatType fat_type) {
27 switch (fat_type) {
28 case FAT_TYPE_FAT12: return 1;
29 case FAT_TYPE_FAT16: return 1024/512;
30 case FAT_TYPE_FAT32: return 4096/512;
31 }
32 return 0;
33 }
34
35 static PedSector
36 _smallest_power2_over (PedSector ceiling)
37 {
38 PedSector result = 1;
39
40 while (result < ceiling)
41 result *= 2;
42
43 return result;
44 }
45
46 /* returns the minimum size of clusters for a given file system type */
47 PedSector
48 fat_recommend_min_cluster_size (FatType fat_type, PedSector size) {
49 switch (fat_type) {
50 case FAT_TYPE_FAT12: return 1;
51 case FAT_TYPE_FAT16: return fat_min_cluster_size(fat_type);
52 case FAT_TYPE_FAT32:
53 return PED_MAX(_smallest_power2_over(size
54 / MAX_FAT32_CLUSTERS),
55 fat_min_cluster_size (fat_type));
56 }
57 return 0;
58 }
59
60 /* returns the maxmimum size of clusters for a given file system type */
61 PedSector
62 fat_max_cluster_size (FatType fat_type) {
63 switch (fat_type) {
64 case FAT_TYPE_FAT12: return 1; /* dunno... who cares? */
65 case FAT_TYPE_FAT16: return 32768/512;
66 case FAT_TYPE_FAT32: return 65536/512;
67 }
68 return 0;
69 }
70
71 /* returns the minimum number of clusters for a given file system type */
72 FatCluster
73 fat_min_cluster_count (FatType fat_type) {
74 switch (fat_type) {
75 case FAT_TYPE_FAT12:
76 case FAT_TYPE_FAT16:
77 return fat_max_cluster_count (fat_type) / 2;
78
79 case FAT_TYPE_FAT32: return 0xfff0;
80 }
81 return 0;
82 }
83
84 /* returns the maximum number of clusters for a given file system type */
85 FatCluster
86 fat_max_cluster_count (FatType fat_type) {
87 switch (fat_type) {
88 case FAT_TYPE_FAT12: return 0xff0;
89 case FAT_TYPE_FAT16: return 0xfff0;
90 case FAT_TYPE_FAT32: return 0x0ffffff0;
91 }
92 return 0;
93 }
94
95 /* what is this supposed to be? What drugs are M$ on? (Can I have some? :-) */
96 PedSector
97 fat_min_reserved_sector_count (FatType fat_type)
98 {
99 return (fat_type == FAT_TYPE_FAT32) ? 32 : 1;
100 }
101
102 int
103 fat_check_resize_geometry (const PedFileSystem* fs,
104 const PedGeometry* geom,
105 PedSector new_cluster_sectors,
106 FatCluster new_cluster_count)
107 {
108 FatSpecific* fs_info = FAT_SPECIFIC (fs);
109 PedSector free_space;
110 PedSector min_free_space;
111 PedSector total_space;
112 PedSector new_total_space;
113 PedSector dir_space;
114
115 PED_ASSERT (geom != NULL, return 0);
116
117 dir_space = fs_info->total_dir_clusters * fs_info->cluster_sectors;
118 free_space = fs_info->fat->free_cluster_count
119 * fs_info->cluster_sectors;
120 total_space = fs_info->fat->cluster_count * fs_info->cluster_sectors;
121 new_total_space = new_cluster_count * new_cluster_sectors;
122 min_free_space = total_space - new_total_space + dir_space;
123
124 PED_ASSERT (new_cluster_count
125 <= fat_max_cluster_count (FAT_TYPE_FAT32),
126 return 0);
127
128 if (free_space < min_free_space) {
129 char* needed = ped_unit_format (geom->dev, min_free_space);
130 char* have = ped_unit_format (geom->dev, free_space);
131 ped_exception_throw (
132 PED_EXCEPTION_ERROR,
133 PED_EXCEPTION_CANCEL,
134 _("You need %s of free disk space to shrink this "
135 "partition to this size. Currently, only %s is "
136 "free."),
137 needed, have);
138 ped_free (needed);
139 ped_free (have);
140 return 0;
141 }
142
143 return 1;
144 }
145
146
147 /******************************************************************************/
148
149 /* DO NOT EDIT THIS ALGORITHM!
150 * As far as I can tell, this is the same algorithm used by Microsoft to
151 * calculate the size of the file allocaion tables, and the number of clusters.
152 * I have not verified this by dissassembling Microsoft code - I came to this
153 * conclusion by empirical analysis (i.e. trial and error - this was HORRIBLE).
154 *
155 * If you think this code makes no sense, then you are right. I will restrain
156 * the urge to inflict serious bodily harm on Microsoft people.
157 */
158
159 static int
160 entries_per_sector (FatType fat_type)
161 {
162 switch (fat_type) {
163 case FAT_TYPE_FAT12:
164 return 512 * 3 / 2;
165 case FAT_TYPE_FAT16:
166 return 512 / 2;
167 case FAT_TYPE_FAT32:
168 return 512 / 4;
169 }
170 return 0;
171 }
172
173 static int
174 calc_sizes (PedSector size, PedSector align, FatType fat_type,
175 PedSector root_dir_sectors, PedSector cluster_sectors,
176 FatCluster* out_cluster_count, PedSector* out_fat_size)
177 {
178 PedSector data_fat_space; /* space available to clusters + FAT */
179 PedSector fat_space; /* space taken by each FAT */
180 PedSector cluster_space; /* space taken by clusters */
181 FatCluster cluster_count;
182 int i;
183
184 PED_ASSERT (out_cluster_count != NULL, return 0);
185 PED_ASSERT (out_fat_size != NULL, return 0);
186
187 data_fat_space = size - fat_min_reserved_sector_count (fat_type)
188 - align;
189 if (fat_type == FAT_TYPE_FAT16)
190 data_fat_space -= root_dir_sectors;
191
192 fat_space = 0;
193 for (i = 0; i < 2; i++) {
194 if (fat_type == FAT_TYPE_FAT32)
195 cluster_space = data_fat_space - fat_space;
196 else
197 cluster_space = data_fat_space - 2 * fat_space;
198
199 cluster_count = cluster_space / cluster_sectors;
200 fat_space = ped_div_round_up (cluster_count + 2,
201 entries_per_sector (fat_type));
202 }
203
204 cluster_space = data_fat_space - 2 * fat_space;
205 cluster_count = cluster_space / cluster_sectors;
206
207 /* looks like this should be part of the loop condition?
208 * Need to build the Big Table TM again to check
209 */
210 if (fat_space < ped_div_round_up (cluster_count + 2,
211 entries_per_sector (fat_type))) {
212 fat_space = ped_div_round_up (cluster_count + 2,
213 entries_per_sector (fat_type));
214 }
215
216 if (cluster_count > fat_max_cluster_count (fat_type)
217 || cluster_count < fat_min_cluster_count (fat_type))
218 return 0;
219
220 *out_cluster_count = cluster_count;
221 *out_fat_size = fat_space;
222
223 return 1;
224 }
225
226 /****************************************************************************/
227
228 int
229 fat_calc_sizes (PedSector size, PedSector align, FatType fat_type,
230 PedSector root_dir_sectors,
231 PedSector* out_cluster_sectors, FatCluster* out_cluster_count,
232 PedSector* out_fat_size)
233 {
234 PedSector cluster_sectors;
235
236 PED_ASSERT (out_cluster_sectors != NULL, return 0);
237 PED_ASSERT (out_cluster_count != NULL, return 0);
238 PED_ASSERT (out_fat_size != NULL, return 0);
239
240 for (cluster_sectors = fat_recommend_min_cluster_size (fat_type, size);
241 cluster_sectors <= fat_max_cluster_size (fat_type);
242 cluster_sectors *= 2) {
243 if (calc_sizes (size, align, fat_type, root_dir_sectors,
244 cluster_sectors,
245 out_cluster_count, out_fat_size)) {
246 *out_cluster_sectors = cluster_sectors;
247 return 1;
248 }
249 }
250
251 for (cluster_sectors = fat_recommend_min_cluster_size (fat_type, size);
252 cluster_sectors >= fat_min_cluster_size (fat_type);
253 cluster_sectors /= 2) {
254 if (calc_sizes (size, align, fat_type, root_dir_sectors,
255 cluster_sectors,
256 out_cluster_count, out_fat_size)) {
257 *out_cluster_sectors = cluster_sectors;
258 return 1;
259 }
260 }
261
262 /* only make the cluster size really small (<4k) if a bigger one is
263 * isn't possible. Windows never makes FS's like this, but it
264 * seems to work... (do more tests!)
265 */
266 for (cluster_sectors = 4; cluster_sectors > 0; cluster_sectors /= 2) {
267 if (calc_sizes (size, align, fat_type, root_dir_sectors,
268 cluster_sectors,
269 out_cluster_count, out_fat_size)) {
270 *out_cluster_sectors = cluster_sectors;
271 return 1;
272 }
273 }
274
275 return 0;
276 }
277
278 /* Same as fat_calc_sizes, except it only attempts to match a particular
279 * cluster size. This is useful, because the FAT resizer can only shrink the
280 * cluster size.
281 */
282 int
283 fat_calc_resize_sizes (
284 const PedGeometry* geom,
285 PedSector align,
286 FatType fat_type,
287 PedSector root_dir_sectors,
288 PedSector cluster_sectors,
289 PedSector* out_cluster_sectors,
290 FatCluster* out_cluster_count,
291 PedSector* out_fat_size)
292 {
293 PED_ASSERT (geom != NULL, return 0);
294 PED_ASSERT (out_cluster_sectors != NULL, return 0);
295 PED_ASSERT (out_cluster_count != NULL, return 0);
296 PED_ASSERT (out_fat_size != NULL, return 0);
297
298 /* libparted can only reduce the cluster size at this point */
299 for (*out_cluster_sectors = cluster_sectors;
300 *out_cluster_sectors >= fat_min_cluster_size (fat_type);
301 *out_cluster_sectors /= 2) {
302 if (calc_sizes (geom->length, align, fat_type, root_dir_sectors,
303 *out_cluster_sectors,
304 out_cluster_count, out_fat_size))
305 return 1;
306 }
307 return 0;
308 }
309
310 /* Calculates the number of sectors needed to be added to cluster_offset,
311 to make the cluster on the new file system match up with the ones
312 on the old file system.
313 However, some space is reserved by fat_calc_resize_sizes() and
314 friends, to allow room for this space. If too much of this space is left
315 over, everyone will complain, so we have to be greedy, and use it all up...
316 */
317 PedSector
318 fat_calc_align_sectors (const PedFileSystem* new_fs,
319 const PedFileSystem* old_fs)
320 {
321 FatSpecific* old_fs_info = FAT_SPECIFIC (old_fs);
322 FatSpecific* new_fs_info = FAT_SPECIFIC (new_fs);
323 PedSector raw_old_meta_data_end;
324 PedSector new_meta_data_size;
325 PedSector min_new_meta_data_end;
326 PedSector new_data_size;
327 PedSector new_clusters_size;
328 PedSector align;
329
330 new_meta_data_size
331 = fat_min_reserved_sector_count (new_fs_info->fat_type)
332 + new_fs_info->fat_sectors * 2;
333
334 if (new_fs_info->fat_type == FAT_TYPE_FAT16)
335 new_meta_data_size += new_fs_info->root_dir_sector_count;
336
337 raw_old_meta_data_end = old_fs->geom->start
338 + old_fs_info->cluster_offset;
339
340 min_new_meta_data_end = new_fs->geom->start + new_meta_data_size;
341
342 if (raw_old_meta_data_end > min_new_meta_data_end)
343 align = (raw_old_meta_data_end - min_new_meta_data_end)
344 % new_fs_info->cluster_sectors;
345 else
346 align = (new_fs_info->cluster_sectors
347 - ( (min_new_meta_data_end - raw_old_meta_data_end)
348 % new_fs_info->cluster_sectors ))
349 % new_fs_info->cluster_sectors;
350
351 new_data_size = new_fs->geom->length - new_meta_data_size;
352 new_clusters_size = new_fs_info->cluster_count
353 * new_fs_info->cluster_sectors;
354
355 while (new_clusters_size + align + new_fs_info->cluster_sectors
356 <= new_data_size)
357 align += new_fs_info->cluster_sectors;
358
359 return align;
360 }
361
362 int
363 fat_is_sector_in_clusters (const PedFileSystem* fs, PedSector sector)
364 {
365 FatSpecific* fs_info = FAT_SPECIFIC (fs);
366
367 return sector >= fs_info->cluster_offset
368 && sector < fs_info->cluster_offset
369 + fs_info->cluster_sectors * fs_info->cluster_count;
370 }
371
372 FatFragment
373 fat_cluster_to_frag (const PedFileSystem* fs, FatCluster cluster)
374 {
375 FatSpecific* fs_info = FAT_SPECIFIC (fs);
376
377 PED_ASSERT (cluster >= 2 && cluster < fs_info->cluster_count + 2,
378 return 0);
379
380 return (cluster - 2) * fs_info->cluster_frags;
381 }
382
383 FatCluster
384 fat_frag_to_cluster (const PedFileSystem* fs, FatFragment frag)
385 {
386 FatSpecific* fs_info = FAT_SPECIFIC (fs);
387
388 PED_ASSERT (frag >= 0 && frag < fs_info->frag_count, return 0);
389
390 return frag / fs_info->cluster_frags + 2;
391 }
392
393 PedSector
394 fat_frag_to_sector (const PedFileSystem* fs, FatFragment frag)
395 {
396 FatSpecific* fs_info = FAT_SPECIFIC (fs);
397
398 PED_ASSERT (frag >= 0 && frag < fs_info->frag_count, return 0);
399
400 return frag * fs_info->frag_sectors + fs_info->cluster_offset;
401 }
402
403 FatFragment
404 fat_sector_to_frag (const PedFileSystem* fs, PedSector sector)
405 {
406 FatSpecific* fs_info = FAT_SPECIFIC (fs);
407
408 PED_ASSERT (sector >= fs_info->cluster_offset, return 0);
409
410 return (sector - fs_info->cluster_offset) / fs_info->frag_sectors;
411 }
412
413 PedSector
414 fat_cluster_to_sector (const PedFileSystem* fs, FatCluster cluster)
415 {
416 FatSpecific* fs_info = FAT_SPECIFIC (fs);
417
418 PED_ASSERT (cluster >= 2 && cluster < fs_info->cluster_count + 2,
419 return 0);
420
421 return (cluster - 2) * fs_info->cluster_sectors
422 + fs_info->cluster_offset;
423 }
424
425 FatCluster
426 fat_sector_to_cluster (const PedFileSystem* fs, PedSector sector)
427 {
428 FatSpecific* fs_info = FAT_SPECIFIC (fs);
429
430 PED_ASSERT (sector >= fs_info->cluster_offset, return 0);
431
432 return (sector - fs_info->cluster_offset) / fs_info->cluster_sectors
433 + 2;
434 }
435 #endif /* !DISCOVER_ONLY */