libparted/fs/fat/calc.c

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