libparted/fs/r/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);
 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
 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                 free (needed);
 139                 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);
 185         PED_ASSERT (out_fat_size != NULL);
 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);
 237         PED_ASSERT (out_cluster_count != NULL);
 238         PED_ASSERT (out_fat_size != NULL);
 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);
 294         PED_ASSERT (out_cluster_sectors != NULL);
 295         PED_ASSERT (out_cluster_count != NULL);
 296         PED_ASSERT (out_fat_size != NULL);
 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
 379         return (cluster - 2) * fs_info->cluster_frags;
 380 }
 381
 382 FatCluster
 383 fat_frag_to_cluster (const PedFileSystem* fs, FatFragment frag)
 384 {
 385         FatSpecific*    fs_info = FAT_SPECIFIC (fs);
 386
 387         PED_ASSERT (frag >= 0 && frag < fs_info->frag_count);
 388
 389         return frag / fs_info->cluster_frags + 2;
 390 }
 391
 392 PedSector
 393 fat_frag_to_sector (const PedFileSystem* fs, FatFragment frag)
 394 {
 395         FatSpecific*    fs_info = FAT_SPECIFIC (fs);
 396
 397         PED_ASSERT (frag >= 0 && frag < fs_info->frag_count);
 398
 399         return frag * fs_info->frag_sectors + fs_info->cluster_offset;
 400 }
 401
 402 FatFragment
 403 fat_sector_to_frag (const PedFileSystem* fs, PedSector sector)
 404 {
 405         FatSpecific*    fs_info = FAT_SPECIFIC (fs);
 406
 407         PED_ASSERT (sector >= fs_info->cluster_offset);
 408
 409         return (sector - fs_info->cluster_offset) / fs_info->frag_sectors;
 410 }
 411
 412 PedSector
 413 fat_cluster_to_sector (const PedFileSystem* fs, FatCluster cluster)
 414 {
 415         FatSpecific*    fs_info = FAT_SPECIFIC (fs);
 416
 417         PED_ASSERT (cluster >= 2 && cluster < fs_info->cluster_count + 2);
 418
 419         return (cluster - 2) * fs_info->cluster_sectors
 420                 + fs_info->cluster_offset;
 421 }
 422
 423 FatCluster
 424 fat_sector_to_cluster (const PedFileSystem* fs, PedSector sector)
 425 {
 426         FatSpecific*    fs_info = FAT_SPECIFIC (fs);
 427
 428         PED_ASSERT (sector >= fs_info->cluster_offset);
 429
 430         return (sector - fs_info->cluster_offset) / fs_info->cluster_sectors
 431                 + 2;
 432 }
 433 #endif /* !DISCOVER_ONLY */