libparted/labels/dos.c

   1 /*
   2     libparted - a library for manipulating disk partitions
   3     Copyright (C) 1999-2001, 2004-2005, 2007-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
  22 #include <sys/time.h>
  23 #include <stdbool.h>
  24 #include <parted/parted.h>
  25 #include <parted/debug.h>
  26 #include <parted/endian.h>
  27
  28 #if ENABLE_NLS
  29 #  include <libintl.h>
  30 #  define _(String) dgettext (PACKAGE, String)
  31 #else
  32 #  define _(String) (String)
  33 #endif /* ENABLE_NLS */
  34
  35 #include "misc.h"
  36 #include "pt-tools.h"
  37
  38 /* this MBR boot code is loaded into 0000:7c00 by the BIOS.  See mbr.s for
  39  * the source, and how to build it
  40  */
  41
  42 static const char MBR_BOOT_CODE[] = {
  43         0xfa, 0xb8, 0x00, 0x10, 0x8e, 0xd0, 0xbc, 0x00,
  44         0xb0, 0xb8, 0x00, 0x00, 0x8e, 0xd8, 0x8e, 0xc0,
  45         0xfb, 0xbe, 0x00, 0x7c, 0xbf, 0x00, 0x06, 0xb9,
  46         0x00, 0x02, 0xf3, 0xa4, 0xea, 0x21, 0x06, 0x00,
  47         0x00, 0xbe, 0xbe, 0x07, 0x38, 0x04, 0x75, 0x0b,
  48         0x83, 0xc6, 0x10, 0x81, 0xfe, 0xfe, 0x07, 0x75,
  49         0xf3, 0xeb, 0x16, 0xb4, 0x02, 0xb0, 0x01, 0xbb,
  50         0x00, 0x7c, 0xb2, 0x80, 0x8a, 0x74, 0x01, 0x8b,
  51         0x4c, 0x02, 0xcd, 0x13, 0xea, 0x00, 0x7c, 0x00,
  52         0x00, 0xeb, 0xfe
  53 };
  54
  55 #define MSDOS_MAGIC             0xAA55
  56 #define PARTITION_MAGIC_MAGIC   0xf6f6
  57
  58 /* The maximum number of DOS primary partitions.  */
  59 #define DOS_N_PRI_PARTITIONS    4
  60
  61 #define PARTITION_EMPTY         0x00
  62 #define PARTITION_FAT12         0x01
  63 #define PARTITION_FAT16_SM      0x04
  64 #define PARTITION_DOS_EXT       0x05
  65 #define PARTITION_FAT16         0x06
  66 #define PARTITION_NTFS          0x07
  67 #define PARTITION_HPFS          0x07
  68 #define PARTITION_FAT32         0x0b
  69 #define PARTITION_FAT32_LBA     0x0c
  70 #define PARTITION_FAT16_LBA     0x0e
  71 #define PARTITION_EXT_LBA       0x0f
  72
  73 #define PART_FLAG_HIDDEN        0x10    /* Valid for FAT/NTFS only */
  74 #define PARTITION_FAT12_H       (PARTITION_FAT12        | PART_FLAG_HIDDEN)
  75 #define PARTITION_FAT16_SM_H    (PARTITION_FAT16_SM     | PART_FLAG_HIDDEN)
  76 #define PARTITION_DOS_EXT_H     (PARTITION_DOS_EXT      | PART_FLAG_HIDDEN)
  77 #define PARTITION_FAT16_H       (PARTITION_FAT16        | PART_FLAG_HIDDEN)
  78 #define PARTITION_NTFS_H        (PARTITION_NTFS         | PART_FLAG_HIDDEN)
  79 #define PARTITION_FAT32_H       (PARTITION_FAT32        | PART_FLAG_HIDDEN)
  80 #define PARTITION_FAT32_LBA_H   (PARTITION_FAT32_LBA    | PART_FLAG_HIDDEN)
  81 #define PARTITION_FAT16_LBA_H   (PARTITION_FAT16_LBA    | PART_FLAG_HIDDEN)
  82
  83 #define PARTITION_COMPAQ_DIAG   0x12
  84 #define PARTITION_MSFT_RECOVERY 0x27
  85 #define PARTITION_LDM           0x42
  86 #define PARTITION_LINUX_SWAP    0x82
  87 #define PARTITION_LINUX         0x83
  88 #define PARTITION_LINUX_EXT     0x85
  89 #define PARTITION_LINUX_LVM     0x8e
  90 #define PARTITION_HFS           0xaf
  91 #define PARTITION_SUN_UFS       0xbf
  92 #define PARTITION_DELL_DIAG     0xde
  93 #define PARTITION_GPT           0xee
  94 #define PARTITION_PALO          0xf0
  95 #define PARTITION_PREP          0x41
  96 #define PARTITION_LINUX_RAID    0xfd
  97 #define PARTITION_LINUX_LVM_OLD 0xfe
  98
  99 /* This constant contains the maximum cylinder number that can be represented
 100  * in (C,H,S) notation.  Higher cylinder numbers are reserved for
 101  * "too big" indicators (in which case only LBA addressing can be used).
 102  *      Some partition tables in the wild indicate this number is 1021.
 103  * (i.e. 1022 is sometimes used to indicate "use LBA").
 104  */
 105 #define MAX_CHS_CYLINDER        1021
 106 #define MAX_TOTAL_PART          16
 107
 108 typedef struct _DosRawPartition         DosRawPartition;
 109 typedef struct _DosRawTable             DosRawTable;
 110
 111 /* note: lots of bit-bashing here, thus, you shouldn't look inside it.
 112  * Use chs_to_sector() and sector_to_chs() instead.
 113  */
 114 typedef struct {
 115         uint8_t         head;
 116         uint8_t         sector;
 117         uint8_t         cylinder;
 118 } __attribute__((packed)) RawCHS;
 119
 120 /* ripped from Linux source */
 121 struct _DosRawPartition {
 122         uint8_t         boot_ind;       /* 00:  0x80 - active */
 123         RawCHS          chs_start;      /* 01: */
 124         uint8_t         type;           /* 04: partition type */
 125         RawCHS          chs_end;        /* 05: */
 126         uint32_t        start;          /* 08: starting sector counting from 0 */
 127         uint32_t        length;         /* 0c: nr of sectors in partition */
 128 } __attribute__((packed));
 129
 130 struct _DosRawTable {
 131         char                    boot_code [440];
 132         uint32_t                mbr_signature;  /* really a unique ID */
 133         uint16_t                Unknown;
 134         DosRawPartition         partitions [DOS_N_PRI_PARTITIONS];
 135         uint16_t                magic;
 136 } __attribute__((packed));
 137
 138 /* OrigState is information we want to preserve about the partition for
 139  * dealing with CHS issues
 140  */
 141 typedef struct {
 142         PedGeometry     geom;
 143         DosRawPartition raw_part;
 144         PedSector       lba_offset;     /* needed for computing start/end for
 145                                          * logical partitions */
 146 } OrigState;
 147
 148 typedef struct {
 149         int             cylinder_alignment;
 150 } DosDiskData;
 151
 152 typedef struct {
 153         unsigned char   system;
 154         int             boot;
 155         int             hidden;
 156         int             raid;
 157         int             lvm;
 158         int             lba;
 159         int             palo;
 160         int             prep;
 161         int             diag;
 162         OrigState*      orig;                   /* used for CHS stuff */
 163 } DosPartitionData;
 164
 165 static PedDiskType msdos_disk_type;
 166
 167 #if 0
 168 From http://www.win.tue.nl/~aeb/linux/fs/fat/fat-1.html
 169
 170 The 2-byte numbers are stored little endian (low order byte first).
 171
 172 Here the FAT12 version, that is also the common part of the FAT12, FAT16 and FAT32 boot sectors. See further below.
 173
 174 Bytes   Content
 175 0-2     Jump to bootstrap (E.g. eb 3c 90; on i86: JMP 003E NOP.
 176         One finds either eb xx 90, or e9 xx xx.
 177         The position of the bootstrap varies.)
 178 3-10    OEM name/version (E.g. "IBM  3.3", "IBM 20.0", "MSDOS5.0", "MSWIN4.0".
 179         Various format utilities leave their own name, like "CH-FOR18".
 180         Sometimes just garbage. Microsoft recommends "MSWIN4.1".)
 181         /* BIOS Parameter Block starts here */
 182 11-12   Number of bytes per sector (512)
 183         Must be one of 512, 1024, 2048, 4096.
 184 13      Number of sectors per cluster (1)
 185         Must be one of 1, 2, 4, 8, 16, 32, 64, 128.
 186         A cluster should have at most 32768 bytes. In rare cases 65536 is OK.
 187 14-15   Number of reserved sectors (1)
 188         FAT12 and FAT16 use 1. FAT32 uses 32.
 189 16      Number of FAT copies (2)
 190 17-18   Number of root directory entries (224)
 191         0 for FAT32. 512 is recommended for FAT16.
 192 19-20   Total number of sectors in the filesystem (2880)
 193         (in case the partition is not FAT32 and smaller than 32 MB)
 194 21      Media descriptor type (f0: 1.4 MB floppy, f8: hard disk; see below)
 195 22-23   Number of sectors per FAT (9)
 196         0 for FAT32.
 197 24-25   Number of sectors per track (12)
 198 26-27   Number of heads (2, for a double-sided diskette)
 199 28-29   Number of hidden sectors (0)
 200         Hidden sectors are sectors preceding the partition.
 201         /* BIOS Parameter Block ends here */
 202 30-509  Bootstrap
 203 510-511 Signature 55 aa
 204 #endif
 205
 206 /* There is a significant risk of misclassifying (as msdos)
 207    a disk that is composed solely of a single FAT partition.
 208    Return false if sector S could not be a valid FAT boot sector.
 209    Otherwise, return true.  */
 210 static bool
 211 maybe_FAT (unsigned char const *s)
 212 {
 213   if (! (s[0] == 0xeb || s[0] == 0xe9))
 214     return false;
 215
 216   unsigned int sector_size = PED_LE16_TO_CPU (*(uint16_t *) (s + 11));
 217   switch (sector_size)
 218     {
 219     case 512:
 220     case 1024:
 221     case 2048:
 222     case 4096:
 223       break;
 224     default:
 225       return false;
 226     }
 227
 228   if (! (s[21] == 0xf0 || s[21] == 0xf8))
 229     return false;
 230
 231   return true;
 232 }
 233
 234 static int
 235 msdos_probe (const PedDevice *dev)
 236 {
 237         PedDiskType*    disk_type;
 238         DosRawTable*    part_table;
 239         int             i;
 240
 241         PED_ASSERT (dev != NULL);
 242
 243         if (dev->sector_size < sizeof *part_table)
 244                 return 0;
 245
 246         void *label;
 247         if (!ptt_read_sector (dev, 0, &label))
 248                 return 0;
 249
 250         part_table = (DosRawTable *) label;
 251
 252         /* check magic */
 253         if (PED_LE16_TO_CPU (part_table->magic) != MSDOS_MAGIC)
 254                 goto probe_fail;
 255
 256         /* If this is a FAT fs, fail here.  Checking for the FAT signature
 257          * has some false positives; instead, do what the Linux kernel does
 258          * and ensure that each partition has a boot indicator that is
 259          * either 0 or 0x80.
 260          */
 261         unsigned int n_active = 0;
 262         for (i = 0; i < DOS_N_PRI_PARTITIONS; i++) {
 263                 if (part_table->partitions[i].boot_ind == 0x80)
 264                         ++n_active;
 265                 if (part_table->partitions[i].boot_ind != 0
 266                     && part_table->partitions[i].boot_ind != 0x80)
 267                         goto probe_fail;
 268         }
 269
 270         /* If there are no active partitions and this is probably
 271            a FAT file system, do not classify it as msdos.  */
 272         if (n_active == 0 && maybe_FAT (label))
 273           goto probe_fail;
 274
 275         /* If this is a GPT disk, fail here */
 276         for (i = 0; i < DOS_N_PRI_PARTITIONS; i++) {
 277                 if (part_table->partitions[i].type == PARTITION_GPT)
 278                         goto probe_fail;
 279         }
 280
 281         /* If this is an AIX Physical Volume, fail here.  IBMA in EBCDIC */
 282         if (part_table->boot_code[0] == (char) 0xc9 &&
 283             part_table->boot_code[1] == (char) 0xc2 &&
 284             part_table->boot_code[2] == (char) 0xd4 &&
 285             part_table->boot_code[3] == (char) 0xc1)
 286                 goto probe_fail;
 287
 288 #ifdef ENABLE_PC98
 289         /* HACK: it's impossible to tell PC98 and msdos disk labels apart.
 290          * Someone made the signatures the same (very clever).  Since
 291          * PC98 has some idiosyncracies with it's boot-loader, it's detection
 292          * is more reliable */
 293         disk_type = ped_disk_type_get ("pc98");
 294         if (disk_type && disk_type->ops->probe (dev))
 295                 goto probe_fail;
 296 #endif /* ENABLE_PC98 */
 297
 298         free (label);
 299         return 1;
 300
 301  probe_fail:
 302         free (label);
 303         return 0;
 304 }
 305
 306 static PedDisk*
 307 msdos_alloc (const PedDevice* dev)
 308 {
 309         PedDisk* disk;
 310         PED_ASSERT (dev != NULL);
 311
 312         disk = _ped_disk_alloc ((PedDevice*)dev, &msdos_disk_type);
 313         if (disk) {
 314                 DosDiskData *disk_specific = ped_malloc(sizeof *disk_specific);
 315                 if (!disk_specific) {
 316                         free (disk);
 317                         return NULL;
 318                 }
 319                 disk_specific->cylinder_alignment = 1;
 320                 disk->disk_specific = disk_specific;
 321         }
 322
 323         return disk;
 324 }
 325
 326 static PedDisk*
 327 msdos_duplicate (const PedDisk* disk)
 328 {
 329         PedDisk*        new_disk;
 330
 331         new_disk = ped_disk_new_fresh (disk->dev, &msdos_disk_type);
 332         if (!new_disk)
 333                 return NULL;
 334
 335         memcpy(new_disk->disk_specific, disk->disk_specific,
 336                sizeof(DosDiskData));
 337
 338         return new_disk;
 339 }
 340
 341 static void
 342 msdos_free (PedDisk* disk)
 343 {
 344         PED_ASSERT (disk != NULL);
 345
 346         DosDiskData *disk_specific = disk->disk_specific;
 347         _ped_disk_free (disk);
 348         free(disk_specific);
 349 }
 350
 351 static int
 352 msdos_disk_set_flag (PedDisk *disk, PedDiskFlag flag, int state)
 353 {
 354         DosDiskData *disk_specific = disk->disk_specific;
 355         switch (flag) {
 356         case PED_DISK_CYLINDER_ALIGNMENT:
 357                 disk_specific->cylinder_alignment = !!state;
 358                 return 1;
 359         default:
 360                 return 0;
 361         }
 362 }
 363
 364 static int
 365 msdos_disk_get_flag (const PedDisk *disk, PedDiskFlag flag)
 366 {
 367         DosDiskData *disk_specific = disk->disk_specific;
 368         switch (flag) {
 369         case PED_DISK_CYLINDER_ALIGNMENT:
 370                 return disk_specific->cylinder_alignment;
 371         default:
 372                 return 0;
 373         }
 374 }
 375
 376 static int
 377 msdos_disk_is_flag_available (const PedDisk *disk, PedDiskFlag flag)
 378 {
 379         switch (flag) {
 380         case PED_DISK_CYLINDER_ALIGNMENT:
 381                return 1;
 382         default:
 383                return 0;
 384         }
 385 }
 386
 387 static int
 388 chs_get_cylinder (const RawCHS* chs)
 389 {
 390         return chs->cylinder + ((chs->sector >> 6) << 8);
 391 }
 392
 393 static int
 394 chs_get_head (const RawCHS* chs)
 395 {
 396         return chs->head;
 397 }
 398
 399 /* counts from 0 */
 400 static int
 401 chs_get_sector (const RawCHS* chs)
 402 {
 403         return (chs->sector & 0x3f) - 1;
 404 }
 405
 406 static PedSector _GL_ATTRIBUTE_PURE
 407 chs_to_sector (const PedDevice* dev, const PedCHSGeometry *bios_geom,
 408                const RawCHS* chs)
 409 {
 410         PedSector       c;              /* not measured in sectors, but need */
 411         PedSector       h;              /* lots of bits */
 412         PedSector       s;
 413
 414         PED_ASSERT (bios_geom != NULL);
 415         PED_ASSERT (chs != NULL);
 416
 417         c = chs_get_cylinder (chs);
 418         h = chs_get_head (chs);
 419         s = chs_get_sector (chs);
 420
 421         if (c > MAX_CHS_CYLINDER)               /* MAGIC: C/H/S is irrelevant */
 422                 return 0;
 423         if (s < 0)
 424                 return 0;
 425         return (c * bios_geom->heads + h) * bios_geom->sectors + s;
 426 }
 427
 428 static void
 429 sector_to_chs (const PedDevice* dev, const PedCHSGeometry* bios_geom,
 430                PedSector sector, RawCHS* chs)
 431 {
 432         PedSector       real_c, real_h, real_s;
 433
 434         PED_ASSERT (dev != NULL);
 435         PED_ASSERT (chs != NULL);
 436
 437         if (!bios_geom)
 438                 bios_geom = &dev->bios_geom;
 439
 440         real_c = sector / (bios_geom->heads * bios_geom->sectors);
 441         real_h = (sector / bios_geom->sectors) % bios_geom->heads;
 442         real_s = sector % bios_geom->sectors;
 443
 444         if (real_c > MAX_CHS_CYLINDER) {
 445                 real_c = 1023;
 446                 real_h = bios_geom->heads - 1;
 447                 real_s = bios_geom->sectors - 1;
 448         }
 449
 450         chs->cylinder = real_c % 0x100;
 451         chs->head = real_h;
 452         chs->sector = real_s + 1 + (real_c >> 8 << 6);
 453 }
 454
 455 static PedSector _GL_ATTRIBUTE_PURE
 456 legacy_start (const PedDisk* disk, const PedCHSGeometry* bios_geom,
 457               const DosRawPartition* raw_part)
 458 {
 459         PED_ASSERT (disk != NULL);
 460         PED_ASSERT (raw_part != NULL);
 461
 462         return chs_to_sector (disk->dev, bios_geom, &raw_part->chs_start);
 463 }
 464
 465 static PedSector _GL_ATTRIBUTE_PURE
 466 legacy_end (const PedDisk* disk, const PedCHSGeometry* bios_geom,
 467             const DosRawPartition* raw_part)
 468 {
 469         PED_ASSERT (disk != NULL);
 470         PED_ASSERT (raw_part != NULL);
 471
 472         return chs_to_sector (disk->dev, bios_geom, &raw_part->chs_end);
 473 }
 474
 475 static PedSector _GL_ATTRIBUTE_PURE
 476 linear_start (const PedDisk* disk, const DosRawPartition* raw_part,
 477               PedSector offset)
 478 {
 479         PED_ASSERT (disk != NULL);
 480         PED_ASSERT (raw_part != NULL);
 481
 482         return offset + PED_LE32_TO_CPU (raw_part->start);
 483 }
 484
 485 static PedSector _GL_ATTRIBUTE_PURE
 486 linear_end (const PedDisk* disk, const DosRawPartition* raw_part,
 487             PedSector offset)
 488 {
 489         PED_ASSERT (disk != NULL);
 490         PED_ASSERT (raw_part != NULL);
 491
 492         return (linear_start (disk, raw_part, offset)
 493                 + (PED_LE32_TO_CPU (raw_part->length) - 1));
 494 }
 495
 496 #ifndef DISCOVER_ONLY
 497 static int _GL_ATTRIBUTE_PURE
 498 partition_check_bios_geometry (PedPartition* part, PedCHSGeometry* bios_geom)
 499 {
 500         PedSector               leg_start, leg_end;
 501         DosPartitionData*       dos_data;
 502         PedDisk*                disk;
 503
 504         PED_ASSERT (part != NULL);
 505         PED_ASSERT (part->disk != NULL);
 506         PED_ASSERT (part->disk_specific != NULL);
 507         dos_data = part->disk_specific;
 508
 509         if (!dos_data->orig)
 510                 return 1;
 511
 512         disk = part->disk;
 513         leg_start = legacy_start (disk, bios_geom, &dos_data->orig->raw_part);
 514         leg_end = legacy_end (disk, bios_geom, &dos_data->orig->raw_part);
 515
 516         if (leg_start && leg_start != dos_data->orig->geom.start)
 517                 return 0;
 518         if (leg_end && leg_end != dos_data->orig->geom.end)
 519                 return 0;
 520         return 1;
 521 }
 522
 523 static int _GL_ATTRIBUTE_PURE
 524 disk_check_bios_geometry (const PedDisk* disk, PedCHSGeometry* bios_geom)
 525 {
 526         PedPartition* part = NULL;
 527
 528         PED_ASSERT (disk != NULL);
 529
 530         while ((part = ped_disk_next_partition (disk, part))) {
 531                 if (ped_partition_is_active (part)) {
 532                         if (!partition_check_bios_geometry (part, bios_geom))
 533                                 return 0;
 534                 }
 535         }
 536
 537         return 1;
 538 }
 539
 540 static int
 541 probe_filesystem_for_geom (const PedPartition* part, PedCHSGeometry* bios_geom)
 542 {
 543         const char* ms_types[] = {"ntfs", "fat16", "fat32", NULL};
 544         int i;
 545         int found;
 546         unsigned char* buf;
 547         int sectors;
 548         int heads;
 549         int res = 0;
 550
 551         PED_ASSERT (bios_geom        != NULL);
 552         PED_ASSERT (part             != NULL);
 553         PED_ASSERT (part->disk       != NULL);
 554         PED_ASSERT (part->disk->dev  != NULL);
 555         PED_ASSERT (part->disk->dev->sector_size % PED_SECTOR_SIZE_DEFAULT == 0);
 556
 557         buf = ped_malloc (part->disk->dev->sector_size);
 558
 559         if (!buf)
 560                 return 0;
 561
 562         if (!part->fs_type)
 563                 goto end;
 564
 565         found = 0;
 566         for (i = 0; ms_types[i]; i++) {
 567                 if (!strcmp(ms_types[i], part->fs_type->name))
 568                         found = 1;
 569         }
 570         if (!found)
 571                 goto end;
 572
 573         if (!ped_geometry_read(&part->geom, buf, 0, 1))
 574                 goto end;
 575
 576         /* shared by the start of all Microsoft file systems */
 577         sectors = buf[0x18] + (buf[0x19] << 8);
 578         heads = buf[0x1a] + (buf[0x1b] << 8);
 579
 580         if (sectors < 1 || sectors > 63)
 581                 goto end;
 582         if (heads > 255 || heads < 1)
 583                 goto end;
 584
 585         bios_geom->sectors = sectors;
 586         bios_geom->heads = heads;
 587         bios_geom->cylinders = part->disk->dev->length / (sectors * heads);
 588         res = 1;
 589 end:
 590         free(buf);
 591         return res;
 592 }
 593
 594 /* This function attempts to infer the BIOS CHS geometry of the hard disk
 595  * from the CHS + LBA information contained in the partition table from
 596  * a single partition's entry.
 597  *
 598  * This involves some maths.  Let (c,h,s,a) be the starting cylinder,
 599  * starting head, starting sector and LBA start address of the partition.
 600  * Likewise, (C,H,S,A) the end addresses.  Using both of these pieces
 601  * of information, we want to deduce cyl_sectors and head_sectors which
 602  * are the sizes of a single cylinder and a single head, respectively.
 603  *
 604  * The relationships are:
 605  * c*cyl_sectors + h * head_sectors + s = a
 606  * C*cyl_sectors + H * head_sectors + S = A
 607  *
 608  * We can rewrite this in matrix form:
 609  *
 610  * [ c h ] [ cyl_sectors  ]  =  [ s - a ]  =  [ a_ ]
 611  * [ C H ] [ head_sectors ]     [ S - A ]     [ A_ ].
 612  *
 613  * (s - a is abbreviated to a_to simplify the notation.)
 614  *
 615  * This can be abbreviated into augmented matrix form:
 616  *
 617  * [ c h | a_ ]
 618  * [ C H | A_ ].
 619  *
 620  * Solving these equations requires following the row reduction algorithm.  We
 621  * need to be careful about a few things though:
 622  *      - the equations might be linearly dependent, in which case there
 623  *      are many solutions.
 624  *      - the equations might be inconsistent, in which case there
 625  *      are no solutions.  (Inconsistent partition table entry!)
 626  *      - there might be zeros, so we need to be careful about applying
 627  *      the algorithm.  We know, however, that C > 0.
 628  */
 629 static int
 630 probe_partition_for_geom (const PedPartition* part, PedCHSGeometry* bios_geom)
 631 {
 632         DosPartitionData* dos_data;
 633         RawCHS* start_chs;
 634         RawCHS* end_chs;
 635         PedSector c, h, s, a, a_;       /* start */
 636         PedSector C, H, S, A, A_;       /* end */
 637         PedSector dont_overflow, denum;
 638         PedSector cyl_size, head_size;
 639         PedSector cylinders, heads, sectors;
 640
 641         PED_ASSERT (part != NULL);
 642         PED_ASSERT (part->disk_specific != NULL);
 643         PED_ASSERT (bios_geom != NULL);
 644
 645         dos_data = part->disk_specific;
 646
 647         if (!dos_data->orig)
 648                 return 0;
 649
 650         start_chs = &dos_data->orig->raw_part.chs_start;
 651         c = chs_get_cylinder (start_chs);
 652         h = chs_get_head (start_chs);
 653         s = chs_get_sector (start_chs);
 654         a = dos_data->orig->geom.start;
 655         a_ = a - s;
 656
 657         end_chs = &dos_data->orig->raw_part.chs_end;
 658         C = chs_get_cylinder (end_chs);
 659         H = chs_get_head (end_chs);
 660         S = chs_get_sector (end_chs);
 661         A = dos_data->orig->geom.end;
 662         A_ = A - S;
 663
 664         if (h < 0 || H < 0 || h > 254 || H > 254)
 665                 return 0;
 666         if (c > C)
 667                 return 0;
 668
 669         /* If no geometry is feasible, then don't even bother.
 670          * Useful for eliminating assertions for broken partition
 671          * tables generated by Norton Ghost et al.
 672          */
 673         if (A > (C+1) * 255 * 63)
 674                 return 0;
 675
 676         /* Not enough information.  In theory, we can do better.  Should we? */
 677         if (C > MAX_CHS_CYLINDER)
 678                 return 0;
 679         if (C == 0)
 680                 return 0;
 681
 682         /* Calculate the maximum number that can be multiplied by
 683          * any head count without overflowing a PedSector
 684          * 2^8 = 256, 8 bits + 1(sign bit) = 9
 685          */
 686         dont_overflow = 1;
 687         dont_overflow <<= (8*sizeof(dont_overflow)) - 9;
 688         dont_overflow--;
 689
 690         if (a_ > dont_overflow || A_ > dont_overflow)
 691                 return 0;
 692
 693         /* The matrix is solved by :
 694          *
 695          * [ c h | a_]                  R1
 696          * [ C H | A_]                  R2
 697          *
 698          * (cH - Ch) cyl_size = a_H - A_h               H R1 - h R2
 699          * => (if cH - Ch != 0) cyl_size = (a_H - A_h) / (cH - Ch)
 700          *
 701          * (Hc - hC) head_size = A_c - a_C              c R2 - C R1
 702          * => (if cH - Ch != 0) head_size = (A_c - a_C) / (cH - Ch)
 703          *
 704          *   But this calculation of head_size would need
 705          *   not overflowing A_c or a_C
 706          *   So substitution is use instead, to minimize dimension
 707          *   of temporary results :
 708          *
 709          * If h != 0 : head_size = ( a_ - c cyl_size ) / h
 710          * If H != 0 : head_size = ( A_ - C cyl_size ) / H
 711          *
 712          */
 713         denum = c * H - C * h;
 714         if (denum == 0)
 715                 return 0;
 716
 717         cyl_size = (a_*H - A_*h) / denum;
 718         /* Check for non integer result */
 719         if (cyl_size * denum != a_*H - A_*h)
 720                 return 0;
 721
 722         if (!(cyl_size > 0))
 723                 return 0;
 724         if (!(cyl_size <= 255 * 63))
 725                 return 0;
 726
 727         if (h > 0)
 728                 head_size = ( a_ - c * cyl_size ) / h;
 729         else if (H > 0)
 730                 head_size = ( A_ - C * cyl_size ) / H;
 731         else {
 732                 /* should not happen because denum != 0 */
 733                 PED_ASSERT (0);
 734         }
 735
 736         if (!(head_size > 0))
 737                 return 0;
 738         if (!(head_size <= 63))
 739                 return 0;
 740
 741         cylinders = part->disk->dev->length / cyl_size;
 742         heads = cyl_size / head_size;
 743         sectors = head_size;
 744
 745         if (!(heads > 0))
 746                 return 0;
 747         if (!(heads < 256))
 748                 return 0;
 749
 750         if (!(sectors > 0))
 751                 return 0;
 752         if (!(sectors <= 63))
 753                 return 0;
 754
 755         /* Some broken OEM partitioning program(s) seem to have an out-by-one
 756          * error on the end of partitions.  We should offer to fix the
 757          * partition table...
 758          */
 759         if (((C + 1) * heads + H) * sectors + S == A)
 760                 C++;
 761
 762         if (!((c * heads + h) * sectors + s == a))
 763                 return 0;
 764         if (!((C * heads + H) * sectors + S == A))
 765                 return 0;
 766
 767         bios_geom->cylinders = cylinders;
 768         bios_geom->heads = heads;
 769         bios_geom->sectors = sectors;
 770
 771         return 1;
 772 }
 773
 774 static void
 775 partition_probe_bios_geometry (const PedPartition* part,
 776                                PedCHSGeometry* bios_geom)
 777 {
 778         PED_ASSERT (part != NULL);
 779         PED_ASSERT (part->disk != NULL);
 780         PED_ASSERT (bios_geom != NULL);
 781
 782         if (ped_partition_is_active (part)) {
 783                 if (probe_partition_for_geom (part, bios_geom))
 784                         return;
 785                 if (part->type & PED_PARTITION_EXTENDED) {
 786                         if (probe_filesystem_for_geom (part, bios_geom))
 787                                 return;
 788                 }
 789         }
 790         if (part->type & PED_PARTITION_LOGICAL) {
 791                 PedPartition* ext_part;
 792                 ext_part = ped_disk_extended_partition (part->disk);
 793                 PED_ASSERT (ext_part != NULL);
 794                 partition_probe_bios_geometry (ext_part, bios_geom);
 795         } else {
 796                 *bios_geom = part->disk->dev->bios_geom;
 797         }
 798 }
 799
 800 static void
 801 disk_probe_bios_geometry (const PedDisk* disk, PedCHSGeometry* bios_geom)
 802 {
 803         PedPartition*   part;
 804
 805         /* first look at the boot partition */
 806         part = NULL;
 807         while ((part = ped_disk_next_partition (disk, part))) {
 808                 if (!ped_partition_is_active (part))
 809                         continue;
 810                 if (ped_partition_get_flag (part, PED_PARTITION_BOOT)) {
 811                         if (probe_filesystem_for_geom (part, bios_geom))
 812                                 return;
 813                         if (probe_partition_for_geom (part, bios_geom))
 814                                 return;
 815                 }
 816         }
 817
 818         /* that didn't work... try all partition table entries */
 819         part = NULL;
 820         while ((part = ped_disk_next_partition (disk, part))) {
 821                 if (ped_partition_is_active (part)) {
 822                         if (probe_partition_for_geom (part, bios_geom))
 823                                 return;
 824                 }
 825         }
 826
 827         /* that didn't work... look at all file systems */
 828         part = NULL;
 829         while ((part = ped_disk_next_partition (disk, part))) {
 830                 if (ped_partition_is_active (part)) {
 831                         if (probe_filesystem_for_geom (part, bios_geom))
 832                                 return;
 833                 }
 834         }
 835 }
 836 #endif /* !DISCOVER_ONLY */
 837
 838 static int _GL_ATTRIBUTE_PURE
 839 raw_part_is_extended (const DosRawPartition* raw_part)
 840 {
 841         PED_ASSERT (raw_part != NULL);
 842
 843         switch (raw_part->type) {
 844         case PARTITION_DOS_EXT:
 845         case PARTITION_EXT_LBA:
 846         case PARTITION_LINUX_EXT:
 847                 return 1;
 848
 849         default:
 850                 return 0;
 851         }
 852
 853         return 0;
 854 }
 855
 856 static int _GL_ATTRIBUTE_PURE
 857 raw_part_is_hidden (const DosRawPartition* raw_part)
 858 {
 859         PED_ASSERT (raw_part != NULL);
 860
 861         switch (raw_part->type) {
 862         case PARTITION_FAT12_H:
 863         case PARTITION_FAT16_SM_H:
 864         case PARTITION_FAT16_H:
 865         case PARTITION_FAT32_H:
 866         case PARTITION_NTFS_H:
 867         case PARTITION_FAT32_LBA_H:
 868         case PARTITION_FAT16_LBA_H:
 869                 return 1;
 870
 871         default:
 872                 return 0;
 873         }
 874
 875         return 0;
 876 }
 877
 878 static int _GL_ATTRIBUTE_PURE
 879 raw_part_is_lba (const DosRawPartition* raw_part)
 880 {
 881         PED_ASSERT (raw_part != NULL);
 882
 883         switch (raw_part->type) {
 884         case PARTITION_FAT32_LBA:
 885         case PARTITION_FAT16_LBA:
 886         case PARTITION_EXT_LBA:
 887         case PARTITION_FAT32_LBA_H:
 888         case PARTITION_FAT16_LBA_H:
 889                 return 1;
 890
 891         default:
 892                 return 0;
 893         }
 894
 895         return 0;
 896 }
 897
 898 static PedPartition*
 899 raw_part_parse (const PedDisk* disk, const DosRawPartition* raw_part,
 900                 PedSector lba_offset, PedPartitionType type)
 901 {
 902         PedPartition* part;
 903         DosPartitionData* dos_data;
 904
 905         PED_ASSERT (disk != NULL);
 906         PED_ASSERT (raw_part != NULL);
 907
 908         part = ped_partition_new (
 909                 disk, type, NULL,
 910                 linear_start (disk, raw_part, lba_offset),
 911                 linear_end (disk, raw_part, lba_offset));
 912         if (!part)
 913                 return NULL;
 914         dos_data = part->disk_specific;
 915         dos_data->system = raw_part->type;
 916         dos_data->boot = raw_part->boot_ind != 0;
 917         dos_data->diag = raw_part->type == PARTITION_COMPAQ_DIAG ||
 918                          raw_part->type == PARTITION_MSFT_RECOVERY ||
 919                          raw_part->type == PARTITION_DELL_DIAG;
 920         dos_data->hidden = raw_part_is_hidden (raw_part);
 921         dos_data->raid = raw_part->type == PARTITION_LINUX_RAID;
 922         dos_data->lvm = raw_part->type == PARTITION_LINUX_LVM_OLD
 923                         || raw_part->type == PARTITION_LINUX_LVM;
 924         dos_data->lba = raw_part_is_lba (raw_part);
 925         dos_data->palo = raw_part->type == PARTITION_PALO;
 926         dos_data->prep = raw_part->type == PARTITION_PREP;
 927         dos_data->orig = ped_malloc (sizeof (OrigState));
 928         if (!dos_data->orig) {
 929                 ped_partition_destroy (part);
 930                 return NULL;
 931         }
 932         dos_data->orig->geom = part->geom;
 933         dos_data->orig->raw_part = *raw_part;
 934         dos_data->orig->lba_offset = lba_offset;
 935         return part;
 936 }
 937
 938 static int
 939 read_table (PedDisk* disk, PedSector sector, int is_extended_table)
 940 {
 941         int                     i;
 942         DosRawTable*            table;
 943         DosRawPartition*        raw_part;
 944         PedPartition*           part;
 945         PedPartitionType        type;
 946         PedSector               lba_offset;
 947
 948         PED_ASSERT (disk != NULL);
 949         PED_ASSERT (disk->dev != NULL);
 950
 951         void *label = NULL;
 952         if (!ptt_read_sector (disk->dev, sector, &label))
 953                 goto error;
 954
 955         table = (DosRawTable *) label;
 956
 957         /* weird: empty extended partitions are filled with 0xf6 by PM */
 958         if (is_extended_table
 959             && PED_LE16_TO_CPU (table->magic) == PARTITION_MAGIC_MAGIC)
 960                 goto read_ok;
 961
 962 #ifndef DISCOVER_ONLY
 963         if (PED_LE16_TO_CPU (table->magic) != MSDOS_MAGIC) {
 964                 if (ped_exception_throw (
 965                         PED_EXCEPTION_ERROR, PED_EXCEPTION_IGNORE_CANCEL,
 966                         _("Invalid partition table on %s "
 967                           "-- wrong signature %x."),
 968                         disk->dev->path,
 969                         PED_LE16_TO_CPU (table->magic))
 970                                 != PED_EXCEPTION_IGNORE)
 971                         goto error;
 972                 goto read_ok;
 973         }
 974 #endif
 975
 976         /* parse the partitions from this table */
 977         for (i = 0; i < DOS_N_PRI_PARTITIONS; i++) {
 978                 raw_part = &table->partitions [i];
 979                 if (raw_part->type == PARTITION_EMPTY || !raw_part->length)
 980                         continue;
 981
 982                 /* process nested extended partitions after normal logical
 983                  * partitions, to make sure we get the order right.
 984                  */
 985                 if (is_extended_table && raw_part_is_extended (raw_part))
 986                         continue;
 987
 988                 lba_offset = is_extended_table ? sector : 0;
 989
 990                 if (linear_start (disk, raw_part, lba_offset) == sector) {
 991                         if (ped_exception_throw (
 992                                 PED_EXCEPTION_ERROR,
 993                                 PED_EXCEPTION_IGNORE_CANCEL,
 994                                 _("Invalid partition table - recursive "
 995                                 "partition on %s."),
 996                                 disk->dev->path)
 997                                         != PED_EXCEPTION_IGNORE)
 998                                 goto error;
 999                         continue;       /* avoid infinite recursion */
1000                 }
1001
1002                 if (is_extended_table)
1003                         type = PED_PARTITION_LOGICAL;
1004                 else if (raw_part_is_extended (raw_part))
1005                         type = PED_PARTITION_EXTENDED;
1006                 else
1007                         type = PED_PARTITION_NORMAL;
1008
1009                 part = raw_part_parse (disk, raw_part, lba_offset, type);
1010                 if (!part)
1011                         goto error;
1012                 if (!is_extended_table)
1013                         part->num = i + 1;
1014                 if (type != PED_PARTITION_EXTENDED)
1015                         part->fs_type = ped_file_system_probe (&part->geom);
1016
1017                 PedConstraint *constraint_exact
1018                   = ped_constraint_exact (&part->geom);
1019                 bool ok = ped_disk_add_partition (disk, part, constraint_exact);
1020                 ped_constraint_destroy (constraint_exact);
1021                 if (!ok)
1022                         goto error;
1023
1024                 /* non-nested extended partition */
1025                 if (part->type == PED_PARTITION_EXTENDED) {
1026                         if (!read_table (disk, part->geom.start, 1))
1027                                 goto error;
1028                 }
1029         }
1030
1031         if (is_extended_table) {
1032                 /* process the nested extended partitions */
1033                 for (i = 0; i < DOS_N_PRI_PARTITIONS; i++) {
1034                         PedSector part_start;
1035
1036                         raw_part = &table->partitions [i];
1037                         if (!raw_part_is_extended (raw_part))
1038                                 continue;
1039
1040                         lba_offset = ped_disk_extended_partition
1041                                         (disk)->geom.start;
1042                         part_start = linear_start (disk, raw_part, lba_offset);
1043                         if (part_start == sector) {
1044                                 /* recursive table - already threw an
1045                                  * exception above.
1046                                  */
1047                                 continue;
1048                         }
1049                         if (!read_table (disk, part_start, 1))
1050                                 goto error;
1051                 }
1052         }
1053
1054 read_ok:
1055         free (label);
1056         return 1;
1057
1058 error:
1059         free (label);
1060         ped_disk_delete_all (disk);
1061         return 0;
1062 }
1063
1064 static int
1065 msdos_read (PedDisk* disk)
1066 {
1067         PED_ASSERT (disk != NULL);
1068         PED_ASSERT (disk->dev != NULL);
1069
1070         ped_disk_delete_all (disk);
1071         if (!read_table (disk, 0, 0))
1072                 return 0;
1073
1074 #ifndef DISCOVER_ONLY
1075         /* try to figure out the correct BIOS CHS values */
1076         if (!disk_check_bios_geometry (disk, &disk->dev->bios_geom)) {
1077                 PedCHSGeometry bios_geom = disk->dev->bios_geom;
1078                 disk_probe_bios_geometry (disk, &bios_geom);
1079
1080                 /* if the geometry was wrong, then we should reread, to
1081                  * make sure the metadata is allocated in the right places.
1082                  */
1083                 if (disk->dev->bios_geom.cylinders != bios_geom.cylinders
1084                     || disk->dev->bios_geom.heads != bios_geom.heads
1085                     || disk->dev->bios_geom.sectors != bios_geom.sectors) {
1086                         disk->dev->bios_geom = bios_geom;
1087                         return msdos_read (disk);
1088                 }
1089         }
1090 #endif
1091
1092         return 1;
1093 }
1094
1095 #ifndef DISCOVER_ONLY
1096 static int
1097 fill_raw_part (DosRawPartition* raw_part,
1098                const PedPartition* part, PedSector offset)
1099 {
1100         DosPartitionData*       dos_data;
1101         PedCHSGeometry          bios_geom;
1102
1103         PED_ASSERT (raw_part != NULL);
1104         PED_ASSERT (part != NULL);
1105
1106         partition_probe_bios_geometry (part, &bios_geom);
1107
1108         dos_data = part->disk_specific;
1109
1110         raw_part->boot_ind = 0x80 * dos_data->boot;
1111         raw_part->type = dos_data->system;
1112         raw_part->start = PED_CPU_TO_LE32 (part->geom.start - offset);
1113         raw_part->length = PED_CPU_TO_LE32 (part->geom.length);
1114
1115         sector_to_chs (part->disk->dev, &bios_geom, part->geom.start,
1116                        &raw_part->chs_start);
1117         sector_to_chs (part->disk->dev, &bios_geom, part->geom.end,
1118                        &raw_part->chs_end);
1119
1120         if (dos_data->orig) {
1121                 DosRawPartition* orig_raw_part = &dos_data->orig->raw_part;
1122                 if (dos_data->orig->geom.start == part->geom.start)
1123                         raw_part->chs_start = orig_raw_part->chs_start;
1124                 if (dos_data->orig->geom.end == part->geom.end)
1125                         raw_part->chs_end = orig_raw_part->chs_end;
1126         }
1127
1128         return 1;
1129 }
1130
1131 static int
1132 fill_ext_raw_part_geom (DosRawPartition* raw_part,
1133                         const PedCHSGeometry* bios_geom,
1134                         const PedGeometry* geom, PedSector offset)
1135 {
1136         PED_ASSERT (raw_part != NULL);
1137         PED_ASSERT (geom != NULL);
1138         PED_ASSERT (geom->dev != NULL);
1139
1140         raw_part->boot_ind = 0;
1141         raw_part->type = PARTITION_DOS_EXT;
1142         raw_part->start = PED_CPU_TO_LE32 (geom->start - offset);
1143         raw_part->length = PED_CPU_TO_LE32 (geom->length);
1144
1145         sector_to_chs (geom->dev, bios_geom, geom->start, &raw_part->chs_start);
1146         sector_to_chs (geom->dev, bios_geom, geom->start + geom->length - 1,
1147                        &raw_part->chs_end);
1148
1149         return 1;
1150 }
1151
1152 static int
1153 write_ext_table (const PedDisk* disk,
1154                  PedSector sector, const PedPartition* logical)
1155 {
1156         PedPartition*           part;
1157         PedSector               lba_offset;
1158
1159         PED_ASSERT (disk != NULL);
1160         PED_ASSERT (ped_disk_extended_partition (disk) != NULL);
1161         PED_ASSERT (logical != NULL);
1162
1163         lba_offset = ped_disk_extended_partition (disk)->geom.start;
1164
1165         void* s;
1166         if (!ptt_read_sector (disk->dev, sector, &s))
1167                 return 0;
1168
1169         DosRawTable *table = s;
1170         memset(&(table->partitions), 0, sizeof (table->partitions));
1171         table->magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);
1172
1173         int ok = 0;
1174         if (!fill_raw_part (&table->partitions[0], logical, sector))
1175                 goto cleanup;
1176
1177         part = ped_disk_get_partition (disk, logical->num + 1);
1178         if (part) {
1179                 PedGeometry*            geom;
1180                 PedCHSGeometry          bios_geom;
1181
1182                 geom = ped_geometry_new (disk->dev, part->prev->geom.start,
1183                                 part->geom.end - part->prev->geom.start + 1);
1184                 if (!geom)
1185                         goto cleanup;
1186                 partition_probe_bios_geometry (part, &bios_geom);
1187                 fill_ext_raw_part_geom (&table->partitions[1], &bios_geom,
1188                                         geom, lba_offset);
1189                 ped_geometry_destroy (geom);
1190
1191                 if (!write_ext_table (disk, part->prev->geom.start, part))
1192                         goto cleanup;
1193         }
1194
1195         ok = ped_device_write (disk->dev, table, sector, 1);
1196  cleanup:
1197         free (s);
1198         return ok;
1199 }
1200
1201 static int
1202 write_empty_table (const PedDisk* disk, PedSector sector)
1203 {
1204         DosRawTable             table;
1205         void*                   table_sector;
1206
1207         PED_ASSERT (disk != NULL);
1208
1209         if (ptt_read_sector (disk->dev, sector, &table_sector)) {
1210                 memcpy (&table, table_sector, sizeof (table));
1211                 free(table_sector);
1212         }
1213         memset (&(table.partitions), 0, sizeof (table.partitions));
1214         table.magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);
1215
1216         return ped_device_write (disk->dev, (void*) &table, sector, 1);
1217 }
1218
1219 /* Find the first logical partition, and write the partition table for it.
1220  */
1221 static int
1222 write_extended_partitions (const PedDisk* disk)
1223 {
1224         PedPartition*           ext_part;
1225         PedPartition*           part;
1226         PedCHSGeometry          bios_geom;
1227
1228         PED_ASSERT (disk != NULL);
1229
1230         ext_part = ped_disk_extended_partition (disk);
1231         partition_probe_bios_geometry (ext_part, &bios_geom);
1232         part = ped_disk_get_partition (disk, 5);
1233         if (part)
1234                 return write_ext_table (disk, ext_part->geom.start, part);
1235         else
1236                 return write_empty_table (disk, ext_part->geom.start);
1237 }
1238
1239 static inline uint32_t generate_random_id (void)
1240 {
1241         struct timeval tv;
1242         int rc;
1243         rc = gettimeofday(&tv, NULL);
1244         if (rc == -1)
1245                 return 0;
1246         return (uint32_t)(tv.tv_usec & 0xFFFFFFFFUL);
1247 }
1248
1249 static int
1250 msdos_write (const PedDisk* disk)
1251 {
1252         PedPartition*           part;
1253         int                     i;
1254
1255         PED_ASSERT (disk != NULL);
1256         PED_ASSERT (disk->dev != NULL);
1257
1258         void *s0;
1259         if (!ptt_read_sector (disk->dev, 0, &s0))
1260                 return 0;
1261         DosRawTable *table = (DosRawTable *) s0;
1262
1263         if (!table->boot_code[0]) {
1264                 memset (table->boot_code, 0, 512);
1265                 memcpy (table->boot_code, MBR_BOOT_CODE, sizeof (MBR_BOOT_CODE));
1266         }
1267
1268         /* If there is no unique identifier, generate a random one */
1269         if (!table->mbr_signature)
1270                 table->mbr_signature = generate_random_id();
1271
1272         memset (table->partitions, 0, sizeof (table->partitions));
1273         table->magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);
1274
1275         for (i=1; i<=DOS_N_PRI_PARTITIONS; i++) {
1276                 part = ped_disk_get_partition (disk, i);
1277                 if (!part)
1278                         continue;
1279
1280                 if (!fill_raw_part (&table->partitions [i - 1], part, 0))
1281                         goto write_fail;
1282
1283                 if (part->type == PED_PARTITION_EXTENDED) {
1284                         if (!write_extended_partitions (disk))
1285                                 goto write_fail;
1286                 }
1287         }
1288
1289         int write_ok = ped_device_write (disk->dev, (void*) table, 0, 1);
1290         free (s0);
1291         if (!write_ok)
1292                 return 0;
1293         return ped_device_sync (disk->dev);
1294
1295  write_fail:
1296         free (s0);
1297         return 0;
1298
1299 }
1300 #endif /* !DISCOVER_ONLY */
1301
1302 static PedPartition*
1303 msdos_partition_new (const PedDisk* disk, PedPartitionType part_type,
1304                      const PedFileSystemType* fs_type,
1305                      PedSector start, PedSector end)
1306 {
1307         PedPartition*           part;
1308         DosPartitionData*       dos_data;
1309
1310         part = _ped_partition_alloc (disk, part_type, fs_type, start, end);
1311         if (!part)
1312                 goto error;
1313
1314         if (ped_partition_is_active (part)) {
1315                 part->disk_specific
1316                         = dos_data = ped_malloc (sizeof (DosPartitionData));
1317                 if (!dos_data)
1318                         goto error_free_part;
1319                 dos_data->orig = NULL;
1320                 dos_data->system = PARTITION_LINUX;
1321                 dos_data->hidden = 0;
1322                 dos_data->boot = 0;
1323                 dos_data->diag = 0;
1324                 dos_data->raid = 0;
1325                 dos_data->lvm = 0;
1326                 dos_data->lba = 0;
1327                 dos_data->palo = 0;
1328                 dos_data->prep = 0;
1329         } else {
1330                 part->disk_specific = NULL;
1331         }
1332         return part;
1333
1334 error_free_part:
1335         free (part);
1336 error:
1337         return 0;
1338 }
1339
1340 static PedPartition*
1341 msdos_partition_duplicate (const PedPartition* part)
1342 {
1343         PedPartition*           new_part;
1344         DosPartitionData*       new_dos_data;
1345         DosPartitionData*       old_dos_data;
1346
1347         new_part = ped_partition_new (part->disk, part->type, part->fs_type,
1348                                       part->geom.start, part->geom.end);
1349         if (!new_part)
1350                 return NULL;
1351         new_part->num = part->num;
1352
1353         old_dos_data = (DosPartitionData*) part->disk_specific;
1354         new_dos_data = (DosPartitionData*) new_part->disk_specific;
1355         new_dos_data->system = old_dos_data->system;
1356         new_dos_data->boot = old_dos_data->boot;
1357         new_dos_data->diag = old_dos_data->diag;
1358         new_dos_data->hidden = old_dos_data->hidden;
1359         new_dos_data->raid = old_dos_data->raid;
1360         new_dos_data->lvm = old_dos_data->lvm;
1361         new_dos_data->lba = old_dos_data->lba;
1362         new_dos_data->palo = old_dos_data->palo;
1363         new_dos_data->prep = old_dos_data->prep;
1364
1365         if (old_dos_data->orig) {
1366                 new_dos_data->orig = ped_malloc (sizeof (OrigState));
1367                 if (!new_dos_data->orig) {
1368                         ped_partition_destroy (new_part);
1369                         return NULL;
1370                 }
1371                 new_dos_data->orig->geom = old_dos_data->orig->geom;
1372                 new_dos_data->orig->raw_part = old_dos_data->orig->raw_part;
1373                 new_dos_data->orig->lba_offset = old_dos_data->orig->lba_offset;
1374         }
1375         return new_part;
1376 }
1377
1378 static void
1379 msdos_partition_destroy (PedPartition* part)
1380 {
1381         PED_ASSERT (part != NULL);
1382
1383         if (ped_partition_is_active (part)) {
1384                 DosPartitionData* dos_data;
1385                 dos_data = (DosPartitionData*) part->disk_specific;
1386                 free (dos_data->orig);
1387                 free (part->disk_specific);
1388         }
1389         free (part);
1390 }
1391
1392 static int
1393 msdos_partition_set_system (PedPartition* part,
1394                             const PedFileSystemType* fs_type)
1395 {
1396         DosPartitionData* dos_data = part->disk_specific;
1397
1398         part->fs_type = fs_type;
1399
1400         if (dos_data->hidden
1401                     && fs_type
1402                     && strncmp (fs_type->name, "fat", 3) != 0
1403                     && strcmp (fs_type->name, "ntfs") != 0)
1404                 dos_data->hidden = 0;
1405
1406         if (part->type & PED_PARTITION_EXTENDED) {
1407                 dos_data->diag = 0;
1408                 dos_data->raid = 0;
1409                 dos_data->lvm = 0;
1410                 dos_data->palo = 0;
1411                 dos_data->prep = 0;
1412                 if (dos_data->lba)
1413                         dos_data->system = PARTITION_EXT_LBA;
1414                 else
1415                         dos_data->system = PARTITION_DOS_EXT;
1416                 return 1;
1417         }
1418
1419         if (dos_data->diag) {
1420                 /* Don't change the system if it already is a diag type,
1421                    otherwise use Compaq as almost all vendors use that. */
1422                 if (dos_data->system != PARTITION_COMPAQ_DIAG &&
1423                     dos_data->system != PARTITION_MSFT_RECOVERY &&
1424                     dos_data->system != PARTITION_DELL_DIAG)
1425                         dos_data->system = PARTITION_COMPAQ_DIAG;
1426                 return 1;
1427         }
1428         if (dos_data->lvm) {
1429                 dos_data->system = PARTITION_LINUX_LVM;
1430                 return 1;
1431         }
1432         if (dos_data->raid) {
1433                 dos_data->system = PARTITION_LINUX_RAID;
1434                 return 1;
1435         }
1436         if (dos_data->palo) {
1437                 dos_data->system = PARTITION_PALO;
1438                 return 1;
1439         }
1440         if (dos_data->prep) {
1441                 dos_data->system = PARTITION_PREP;
1442                 return 1;
1443         }
1444
1445         if (!fs_type)
1446                 dos_data->system = PARTITION_LINUX;
1447         else if (!strcmp (fs_type->name, "fat16")) {
1448                 dos_data->system = dos_data->lba
1449                                    ? PARTITION_FAT16_LBA : PARTITION_FAT16;
1450                 dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
1451         } else if (!strcmp (fs_type->name, "fat32")) {
1452                 dos_data->system = dos_data->lba
1453                                    ? PARTITION_FAT32_LBA : PARTITION_FAT32;
1454                 dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
1455         } else if (!strcmp (fs_type->name, "ntfs")
1456                    || !strcmp (fs_type->name, "hpfs")) {
1457                 dos_data->system = PARTITION_NTFS;
1458                 dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
1459         } else if (!strcmp (fs_type->name, "hfs")
1460                    || !strcmp (fs_type->name, "hfs+"))
1461                 dos_data->system = PARTITION_HFS;
1462         else if (!strcmp (fs_type->name, "sun-ufs"))
1463                 dos_data->system = PARTITION_SUN_UFS;
1464         else if (is_linux_swap (fs_type->name))
1465                 dos_data->system = PARTITION_LINUX_SWAP;
1466         else
1467                 dos_data->system = PARTITION_LINUX;
1468
1469         return 1;
1470 }
1471
1472 static void
1473 clear_flags (DosPartitionData *dos_data)
1474 {
1475   dos_data->diag = 0;
1476   dos_data->hidden = 0;
1477   dos_data->lvm = 0;
1478   dos_data->palo = 0;
1479   dos_data->prep = 0;
1480   dos_data->raid = 0;
1481 }
1482
1483 static int
1484 msdos_partition_set_flag (PedPartition* part,
1485                           PedPartitionFlag flag, int state)
1486 {
1487         PedDisk*                        disk;
1488         PedPartition*                   walk;
1489         DosPartitionData*               dos_data;
1490
1491         PED_ASSERT (part != NULL);
1492         PED_ASSERT (part->disk_specific != NULL);
1493         PED_ASSERT (part->disk != NULL);
1494
1495         dos_data = part->disk_specific;
1496         disk = part->disk;
1497
1498         switch (flag) {
1499         case PED_PARTITION_HIDDEN:
1500                 if (part->type == PED_PARTITION_EXTENDED) {
1501                         ped_exception_throw (
1502                                 PED_EXCEPTION_ERROR,
1503                                 PED_EXCEPTION_CANCEL,
1504                                 _("Extended partitions cannot be hidden on "
1505                                   "msdos disk labels."));
1506                         return 0;
1507                 }
1508                 dos_data->hidden = state;
1509                 return ped_partition_set_system (part, part->fs_type);
1510
1511         case PED_PARTITION_BOOT:
1512                 dos_data->boot = state;
1513                 if (!state)
1514                         return 1;
1515
1516                 walk = ped_disk_next_partition (disk, NULL);
1517                 for (; walk; walk = ped_disk_next_partition (disk, walk)) {
1518                         if (walk == part || !ped_partition_is_active (walk))
1519                                 continue;
1520                         msdos_partition_set_flag (walk, PED_PARTITION_BOOT, 0);
1521                 }
1522                 return 1;
1523
1524         case PED_PARTITION_DIAG:
1525                 if (state)
1526                         clear_flags (dos_data);
1527                 dos_data->diag = state;
1528                 return ped_partition_set_system (part, part->fs_type);
1529
1530         case PED_PARTITION_RAID:
1531                 if (state)
1532                         clear_flags (dos_data);
1533                 dos_data->raid = state;
1534                 return ped_partition_set_system (part, part->fs_type);
1535
1536         case PED_PARTITION_LVM:
1537                 if (state)
1538                         clear_flags (dos_data);
1539                 dos_data->lvm = state;
1540                 return ped_partition_set_system (part, part->fs_type);
1541
1542         case PED_PARTITION_LBA:
1543                 dos_data->lba = state;
1544                 return ped_partition_set_system (part, part->fs_type);
1545
1546         case PED_PARTITION_PALO:
1547                 if (state)
1548                         clear_flags (dos_data);
1549                 dos_data->palo = state;
1550                 return ped_partition_set_system (part, part->fs_type);
1551
1552         case PED_PARTITION_PREP:
1553                 if (state)
1554                         clear_flags (dos_data);
1555                 dos_data->prep = state;
1556                 return ped_partition_set_system (part, part->fs_type);
1557
1558         default:
1559                 return 0;
1560         }
1561 }
1562
1563 static int _GL_ATTRIBUTE_PURE
1564 msdos_partition_get_flag (const PedPartition* part, PedPartitionFlag flag)
1565 {
1566         DosPartitionData*       dos_data;
1567
1568         PED_ASSERT (part != NULL);
1569         PED_ASSERT (part->disk_specific != NULL);
1570
1571         dos_data = part->disk_specific;
1572         switch (flag) {
1573         case PED_PARTITION_HIDDEN:
1574                 if (part->type == PED_PARTITION_EXTENDED)
1575                         return 0;
1576                 else
1577                         return dos_data->hidden;
1578
1579         case PED_PARTITION_BOOT:
1580                 return dos_data->boot;
1581
1582         case PED_PARTITION_DIAG:
1583                 return dos_data->diag;
1584
1585         case PED_PARTITION_RAID:
1586                 return dos_data->raid;
1587
1588         case PED_PARTITION_LVM:
1589                 return dos_data->lvm;
1590
1591         case PED_PARTITION_LBA:
1592                 return dos_data->lba;
1593
1594         case PED_PARTITION_PALO:
1595                 return dos_data->palo;
1596
1597         case PED_PARTITION_PREP:
1598                 return dos_data->prep;
1599
1600         default:
1601                 return 0;
1602         }
1603 }
1604
1605 static int
1606 msdos_partition_is_flag_available (const PedPartition* part,
1607                                    PedPartitionFlag flag)
1608 {
1609         switch (flag) {
1610         case PED_PARTITION_HIDDEN:
1611                 if (part->type == PED_PARTITION_EXTENDED)
1612                         return 0;
1613                 else
1614                         return 1;
1615
1616         case PED_PARTITION_BOOT:
1617         case PED_PARTITION_RAID:
1618         case PED_PARTITION_LVM:
1619         case PED_PARTITION_LBA:
1620         case PED_PARTITION_PALO:
1621         case PED_PARTITION_PREP:
1622         case PED_PARTITION_DIAG:
1623                 return 1;
1624
1625         default:
1626                 return 0;
1627         }
1628 }
1629
1630 static PedGeometry*
1631 _try_constraint (const PedPartition* part, const PedConstraint* external,
1632                  PedConstraint* internal)
1633 {
1634         PedConstraint*          intersection;
1635         PedGeometry*            solution;
1636
1637         intersection = ped_constraint_intersect (external, internal);
1638         ped_constraint_destroy (internal);
1639         if (!intersection)
1640                 return NULL;
1641
1642         solution = ped_constraint_solve_nearest (intersection, &part->geom);
1643         ped_constraint_destroy (intersection);
1644         return solution;
1645 }
1646
1647 static PedGeometry*
1648 _best_solution (const PedPartition* part, const PedCHSGeometry* bios_geom,
1649                 PedGeometry* a, PedGeometry* b)
1650 {
1651         PedSector       cyl_size = bios_geom->heads * bios_geom->sectors;
1652         int             a_cylinder;
1653         int             b_cylinder;
1654
1655         if (!a)
1656                 return b;
1657         if (!b)
1658                 return a;
1659
1660         a_cylinder = a->start / cyl_size;
1661         b_cylinder = b->start / cyl_size;
1662
1663         if (a_cylinder == b_cylinder) {
1664                 if ( (a->start / bios_geom->sectors) % bios_geom->heads
1665                           < (b->start / bios_geom->sectors) % bios_geom->heads)
1666                         goto choose_a;
1667                 else
1668                         goto choose_b;
1669         } else {
1670                 PedSector       a_delta;
1671                 PedSector       b_delta;
1672
1673                 a_delta = abs (part->geom.start - a->start);
1674                 b_delta = abs (part->geom.start - b->start);
1675
1676                 if (a_delta < b_delta)
1677                         goto choose_a;
1678                 else
1679                         goto choose_b;
1680         }
1681
1682         return NULL;    /* never get here! */
1683
1684 choose_a:
1685         ped_geometry_destroy (b);
1686         return a;
1687
1688 choose_b:
1689         ped_geometry_destroy (a);
1690         return b;
1691 }
1692
1693 /* This constraint is for "normal" primary partitions, that start at the
1694  * beginning of a cylinder, and end at the end of a cylinder.
1695  *      Note: you can't start a partition at the beginning of the 1st
1696  * cylinder, because that's where the partition table is!  There are different
1697  * rules for that - see the _primary_start_constraint.
1698  */
1699 static PedConstraint*
1700 _primary_constraint (const PedDisk* disk, const PedCHSGeometry* bios_geom,
1701                      PedGeometry* min_geom)
1702 {
1703         PedDevice*      dev = disk->dev;
1704         PedSector       cylinder_size = bios_geom->sectors * bios_geom->heads;
1705         PedAlignment    start_align;
1706         PedAlignment    end_align;
1707         PedGeometry     start_geom;
1708         PedGeometry     end_geom;
1709
1710         if (!ped_alignment_init (&start_align, 0, cylinder_size))
1711                 return NULL;
1712         if (!ped_alignment_init (&end_align, -1, cylinder_size))
1713                 return NULL;
1714
1715         if (min_geom) {
1716                 if (min_geom->start < cylinder_size)
1717                         return NULL;
1718                 if (!ped_geometry_init (&start_geom, dev, cylinder_size,
1719                                         min_geom->start + 1 - cylinder_size))
1720                         return NULL;
1721                 if (!ped_geometry_init (&end_geom, dev, min_geom->end,
1722                                         dev->length - min_geom->end))
1723                         return NULL;
1724         } else {
1725                 /* Use cylinder_size as the starting sector number
1726                    when the device is large enough to accommodate that.
1727                    Otherwise, use sector 1.  */
1728                 PedSector start = (cylinder_size < dev->length
1729                                    ? cylinder_size : 1);
1730                 if (!ped_geometry_init (&start_geom, dev, start,
1731                                         dev->length - start))
1732                         return NULL;
1733                 if (!ped_geometry_init (&end_geom, dev, 0, dev->length))
1734                         return NULL;
1735         }
1736
1737         return ped_constraint_new (&start_align, &end_align, &start_geom,
1738                                    &end_geom, 1, dev->length);
1739 }
1740
1741 /* This constraint is for partitions starting on the first cylinder.  They
1742  * must start on the 2nd head of the 1st cylinder.
1743  *
1744  * NOTE: We don't always start on the 2nd head of the 1st cylinder.  Windows
1745  * Vista aligns starting partitions at sector 2048 (0x800) by default.  See:
1746  * http://support.microsoft.com/kb/923332
1747  */
1748 static PedConstraint*
1749 _primary_start_constraint (const PedDisk* disk,
1750                            const PedPartition *part,
1751                            const PedCHSGeometry* bios_geom,
1752                            const PedGeometry* min_geom)
1753 {
1754         PedDevice*      dev = disk->dev;
1755         PedSector       cylinder_size = bios_geom->sectors * bios_geom->heads;
1756         PedAlignment    start_align;
1757         PedAlignment    end_align;
1758         PedGeometry     start_geom;
1759         PedGeometry     end_geom;
1760         PedSector start_pos;
1761
1762         if (part->geom.start == 2048)
1763                 /* check for known Windows Vista (NTFS >= 3.1) alignments */
1764                 /* sector 0x800 == 2048                                   */
1765                 start_pos = 2048;
1766         else
1767                 /* all other primary partitions on a DOS label align to   */
1768                 /* the 2nd head of the first cylinder (0x3F == 63)        */
1769                 start_pos = bios_geom->sectors;
1770
1771         if (!ped_alignment_init (&start_align, start_pos, 0))
1772                 return NULL;
1773         if (!ped_alignment_init (&end_align, -1, cylinder_size))
1774                 return NULL;
1775         if (min_geom) {
1776                 if (!ped_geometry_init (&start_geom, dev, start_pos, 1))
1777                         return NULL;
1778                 if (!ped_geometry_init (&end_geom, dev, min_geom->end,
1779                                         dev->length - min_geom->end))
1780                         return NULL;
1781         } else {
1782                 if (!ped_geometry_init (&start_geom, dev, start_pos,
1783                         dev->length - start_pos))
1784                         return NULL;
1785                 if (!ped_geometry_init (&end_geom, dev, 0, dev->length))
1786                         return NULL;
1787         }
1788
1789         return ped_constraint_new (&start_align, &end_align, &start_geom,
1790                                    &end_geom, 1, dev->length);
1791 }
1792
1793 /* constraints for logical partitions:
1794  *      - start_offset is the offset in the start alignment.  "normally",
1795  * this is bios_geom->sectors.  exceptions: MINOR > 5 at the beginning of the
1796  * extended partition, or MINOR == 5 in the middle of the extended partition
1797  *      - is_start_part == 1 if the constraint is for the first cylinder of
1798  * the extended partition, or == 0 if the constraint is for the second cylinder
1799  * onwards of the extended partition.
1800  */
1801 static PedConstraint*
1802 _logical_constraint (const PedDisk* disk, const PedCHSGeometry* bios_geom,
1803                      PedSector start_offset, int is_start_part)
1804 {
1805         PedPartition*   ext_part = ped_disk_extended_partition (disk);
1806         PedDevice*      dev = disk->dev;
1807         PedSector       cylinder_size = bios_geom->sectors * bios_geom->heads;
1808         PedAlignment    start_align;
1809         PedAlignment    end_align;
1810         PedGeometry     max_geom;
1811
1812         PED_ASSERT (ext_part != NULL);
1813
1814         if (!ped_alignment_init (&start_align, start_offset, cylinder_size))
1815                 return NULL;
1816         if (!ped_alignment_init (&end_align, -1, cylinder_size))
1817                 return NULL;
1818         if (is_start_part) {
1819                 if (!ped_geometry_init (&max_geom, dev,
1820                                         ext_part->geom.start,
1821                                         ext_part->geom.length))
1822                         return NULL;
1823         } else {
1824                 PedSector       min_start;
1825                 PedSector       max_length;
1826
1827                 min_start = ped_round_up_to (ext_part->geom.start + 1,
1828                                              cylinder_size);
1829                 max_length = ext_part->geom.end - min_start + 1;
1830                 if (min_start >= ext_part->geom.end)
1831                         return NULL;
1832
1833                 if (!ped_geometry_init (&max_geom, dev, min_start, max_length))
1834                         return NULL;
1835         }
1836
1837         return ped_constraint_new (&start_align, &end_align, &max_geom,
1838                                    &max_geom, 1, dev->length);
1839 }
1840
1841 /* returns the minimum geometry for the extended partition, given that the
1842  * extended partition must contain:
1843  *   * all logical partitions
1844  *   * all partition tables for all logical partitions (except the first)
1845  *   * the extended partition table
1846  */
1847 static PedGeometry*
1848 _get_min_extended_part_geom (const PedPartition* ext_part,
1849                              const PedCHSGeometry* bios_geom)
1850 {
1851         PedDisk*                disk = ext_part->disk;
1852         PedSector               head_size = bios_geom ? bios_geom->sectors : 1;
1853         PedPartition*           walk;
1854         PedGeometry*            min_geom;
1855
1856         walk = ped_disk_get_partition (disk, 5);
1857         if (!walk)
1858                 return NULL;
1859
1860         min_geom = ped_geometry_duplicate (&walk->geom);
1861         if (!min_geom)
1862                 return NULL;
1863         /* We must always allow at least two sectors at the start, to leave
1864          * room for LILO.  See linux/fs/partitions/msdos.c.
1865          */
1866         ped_geometry_set_start (min_geom,
1867                                 walk->geom.start - PED_MAX (1 * head_size, 2));
1868
1869         for (walk = ext_part->part_list; walk; walk = walk->next) {
1870                 if (!ped_partition_is_active (walk) || walk->num == 5)
1871                         continue;
1872                 if (walk->geom.start < min_geom->start)
1873                         ped_geometry_set_start (min_geom,
1874                                         walk->geom.start - 2 * head_size);
1875                 if (walk->geom.end > min_geom->end)
1876                         ped_geometry_set_end (min_geom, walk->geom.end);
1877         }
1878
1879         return min_geom;
1880 }
1881
1882 static int
1883 _align_primary (PedPartition* part, const PedCHSGeometry* bios_geom,
1884                 const PedConstraint* constraint)
1885 {
1886         PedDisk*        disk = part->disk;
1887         PedGeometry*    min_geom = NULL;
1888         PedGeometry*    solution = NULL;
1889
1890         if (part->type == PED_PARTITION_EXTENDED)
1891                 min_geom = _get_min_extended_part_geom (part, bios_geom);
1892
1893         solution = _best_solution (part, bios_geom, solution,
1894                         _try_constraint (part, constraint,
1895                                          _primary_start_constraint (disk, part,
1896                                                  bios_geom, min_geom)));
1897
1898         solution = _best_solution (part, bios_geom, solution,
1899                         _try_constraint (part, constraint,
1900                                 _primary_constraint (disk, bios_geom,
1901                                 min_geom)));
1902
1903         if (min_geom)
1904                 ped_geometry_destroy (min_geom);
1905
1906         if (solution) {
1907                 ped_geometry_set (&part->geom, solution->start,
1908                                   solution->length);
1909                 ped_geometry_destroy (solution);
1910                 return 1;
1911         }
1912
1913         return 0;
1914 }
1915
1916 static int
1917 _logical_min_start_head (const PedPartition* part,
1918                          const PedCHSGeometry* bios_geom,
1919                          const PedPartition* ext_part,
1920                          int is_start_ext_part)
1921 {
1922         PedSector       cylinder_size = bios_geom->sectors * bios_geom->heads;
1923         PedSector       base_head;
1924
1925         if (is_start_ext_part)
1926                 base_head = 1 + (ext_part->geom.start % cylinder_size)
1927                                         / bios_geom->sectors;
1928         else
1929                 base_head = 0;
1930
1931         if (part->num == 5)
1932                 return base_head + 0;
1933         else
1934                 return base_head + 1;
1935 }
1936
1937 /* Shamelessly copied and adapted from _partition_get_overlap_constraint
1938  * (in disk.c)
1939  * This should get rid of the infamous Assertion (metadata_length > 0) failed
1940  * bug for extended msdos disklabels generated by Parted.
1941  * 1) There always is a partition table at the start of ext_part, so we leave
1942  *    a one sector gap there.
1943  * 2)*The partition table of part5 is always at the beginning of the ext_part
1944  *    so there is no need to leave a one sector gap before part5.
1945  *   *There always is a partition table at the beginning of each partition != 5.
1946  * We don't need to worry to much about consistency with
1947  * _partition_get_overlap_constraint because missing it means we are in edge
1948  * cases anyway, and we don't lose anything by just refusing to do the job in
1949  * those cases.
1950  */
1951 static PedConstraint*
1952 _log_meta_overlap_constraint (PedPartition* part, const PedGeometry* geom)
1953 {
1954         PedGeometry     safe_space;
1955         PedSector       min_start;
1956         PedSector       max_end;
1957         PedPartition*   ext_part = ped_disk_extended_partition (part->disk);
1958         PedPartition*   walk;
1959         int             not_5 = (part->num != 5);
1960
1961         PED_ASSERT (ext_part != NULL);
1962
1963         walk = ext_part->part_list;
1964
1965         /*                                 1)  2)     */
1966         min_start = ext_part->geom.start + 1 + not_5;
1967         max_end = ext_part->geom.end;
1968
1969         while (walk != NULL             /*      2)                         2) */
1970                 && (   walk->geom.start - (walk->num != 5) < geom->start - not_5
1971                     || walk->geom.start - (walk->num != 5) <= min_start )) {
1972                 if (walk != part && ped_partition_is_active (walk))
1973                         min_start = walk->geom.end + 1 + not_5; /* 2) */
1974                 walk = walk->next;
1975         }
1976
1977         while (walk && (walk == part || !ped_partition_is_active (walk)))
1978                 walk = walk->next;
1979
1980         if (walk)
1981                 max_end = walk->geom.start - 1 - (walk->num != 5); /* 2) */
1982
1983         if (min_start >= max_end)
1984                 return NULL;
1985
1986         ped_geometry_init (&safe_space, part->disk->dev,
1987                            min_start, max_end - min_start + 1);
1988         return ped_constraint_new_from_max (&safe_space);
1989 }
1990
1991 static int
1992 _align_logical (PedPartition* part, const PedCHSGeometry* bios_geom,
1993                 const PedConstraint* constraint)
1994 {
1995         PedDisk*        disk = part->disk;
1996         PedPartition*   ext_part = ped_disk_extended_partition (disk);
1997         PedSector       cyl_size = bios_geom->sectors * bios_geom->heads;
1998         PedSector       start_base;
1999         int             head;
2000         PedGeometry*    solution = NULL;
2001         PedConstraint   *intersect, *log_meta_overlap;
2002
2003         PED_ASSERT (ext_part != NULL);
2004
2005         log_meta_overlap = _log_meta_overlap_constraint(part, &part->geom);
2006         intersect = ped_constraint_intersect (constraint, log_meta_overlap);
2007         ped_constraint_destroy (log_meta_overlap);
2008         if (!intersect)
2009                 return 0;
2010
2011         start_base = ped_round_down_to (part->geom.start, cyl_size);
2012
2013         for (head = _logical_min_start_head (part, bios_geom, ext_part, 0);
2014              head < PED_MIN (5, bios_geom->heads); head++) {
2015                 PedConstraint*  disk_constraint;
2016                 PedSector       start = start_base + head * bios_geom->sectors;
2017
2018                 if (head >= _logical_min_start_head (part, bios_geom,
2019                                                      ext_part, 1))
2020                         disk_constraint =
2021                                 _logical_constraint (disk, bios_geom, start, 1);
2022                 else
2023                         disk_constraint =
2024                                 _logical_constraint (disk, bios_geom, start, 0);
2025
2026                 solution = _best_solution (part, bios_geom, solution,
2027                                 _try_constraint (part, intersect,
2028                                                  disk_constraint));
2029         }
2030
2031         ped_constraint_destroy (intersect);
2032
2033         if (solution) {
2034                 ped_geometry_set (&part->geom, solution->start,
2035                                   solution->length);
2036                 ped_geometry_destroy (solution);
2037                 return 1;
2038         }
2039
2040         return 0;
2041 }
2042
2043 static int
2044 _align (PedPartition* part, const PedCHSGeometry* bios_geom,
2045         const PedConstraint* constraint)
2046 {
2047         if (part->type == PED_PARTITION_LOGICAL)
2048                 return _align_logical (part, bios_geom, constraint);
2049         else
2050                 return _align_primary (part, bios_geom, constraint);
2051 }
2052
2053 static PedConstraint*
2054 _no_geom_constraint (const PedDisk* disk, PedSector start, PedSector end)
2055 {
2056         PedGeometry      max;
2057
2058         ped_geometry_init (&max, disk->dev, start, end - start + 1);
2059         return ped_constraint_new_from_max (&max);
2060 }
2061
2062 static PedConstraint*
2063 _no_geom_extended_constraint (const PedPartition* part)
2064 {
2065         PedDevice*      dev = part->disk->dev;
2066         PedGeometry*    min = _get_min_extended_part_geom (part, NULL);
2067         PedGeometry     start_range;
2068         PedGeometry     end_range;
2069         PedConstraint*  constraint;
2070
2071         if (min) {
2072                 ped_geometry_init (&start_range, dev, 1, min->start);
2073                 ped_geometry_init (&end_range, dev, min->end,
2074                                    dev->length - min->end);
2075                 ped_geometry_destroy (min);
2076         } else {
2077                 ped_geometry_init (&start_range, dev, 1, dev->length - 1);
2078                 ped_geometry_init (&end_range, dev, 1, dev->length - 1);
2079         }
2080         constraint = ped_constraint_new (ped_alignment_any, ped_alignment_any,
2081                         &start_range, &end_range, 1, dev->length);
2082         return constraint;
2083 }
2084
2085 static int
2086 _align_primary_no_geom (PedPartition* part, const PedConstraint* constraint)
2087 {
2088         PedDisk*        disk = part->disk;
2089         PedGeometry*    solution;
2090
2091         if (part->type == PED_PARTITION_EXTENDED) {
2092                 solution = _try_constraint (part, constraint,
2093                                 _no_geom_extended_constraint (part));
2094         } else {
2095                 solution = _try_constraint (part, constraint,
2096                                 _no_geom_constraint (disk, 1,
2097                                                      disk->dev->length - 1));
2098         }
2099
2100         if (solution) {
2101                 ped_geometry_set (&part->geom, solution->start,
2102                                   solution->length);
2103                 ped_geometry_destroy (solution);
2104                 return 1;
2105         }
2106         return 0;
2107 }
2108
2109 static int
2110 _align_logical_no_geom (PedPartition* part, const PedConstraint* constraint)
2111 {
2112         PedGeometry*    solution;
2113
2114         solution = _try_constraint (part, constraint,
2115                         _log_meta_overlap_constraint (part, &part->geom));
2116
2117         if (solution) {
2118                 ped_geometry_set (&part->geom, solution->start,
2119                                   solution->length);
2120                 ped_geometry_destroy (solution);
2121                 return 1;
2122         }
2123         return 0;
2124 }
2125
2126 static int
2127 _align_no_geom (PedPartition* part, const PedConstraint* constraint)
2128 {
2129         if (part->type == PED_PARTITION_LOGICAL)
2130                 return _align_logical_no_geom (part, constraint);
2131         else
2132                 return _align_primary_no_geom (part, constraint);
2133 }
2134
2135 static int
2136 msdos_partition_align (PedPartition* part, const PedConstraint* constraint)
2137 {
2138         PedCHSGeometry  bios_geom;
2139         DosPartitionData* dos_data;
2140
2141         PED_ASSERT (part != NULL);
2142         PED_ASSERT (part->disk_specific != NULL);
2143
2144         dos_data = part->disk_specific;
2145
2146         if (dos_data->system == PARTITION_LDM && dos_data->orig) {
2147                 PedGeometry *orig_geom = &dos_data->orig->geom;
2148
2149                 if (ped_geometry_test_equal (&part->geom, orig_geom)
2150                     && ped_constraint_is_solution (constraint, &part->geom))
2151                         return 1;
2152
2153                 ped_geometry_set (&part->geom, orig_geom->start,
2154                                   orig_geom->length);
2155                 ped_exception_throw (
2156                         PED_EXCEPTION_ERROR,
2157                         PED_EXCEPTION_CANCEL,
2158                         _("Parted can't resize partitions managed by "
2159                           "Windows Dynamic Disk."));
2160                 return 0;
2161         }
2162
2163         partition_probe_bios_geometry (part, &bios_geom);
2164
2165         DosDiskData *disk_specific = part->disk->disk_specific;
2166         if (disk_specific->cylinder_alignment
2167             && _align(part, &bios_geom, constraint))
2168                 return 1;
2169         if (_align_no_geom (part, constraint))
2170                 return 1;
2171
2172 #ifndef DISCOVER_ONLY
2173         ped_exception_throw (
2174                 PED_EXCEPTION_ERROR,
2175                 PED_EXCEPTION_CANCEL,
2176                 _("Unable to satisfy all constraints on the partition."));
2177 #endif
2178         return 0;
2179 }
2180
2181 static int
2182 add_metadata_part (PedDisk* disk, PedPartitionType type, PedSector start,
2183                    PedSector end)
2184 {
2185         PedPartition*           new_part;
2186
2187         PED_ASSERT (disk != NULL);
2188
2189         new_part = ped_partition_new (disk, type | PED_PARTITION_METADATA, NULL,
2190                                       start, end);
2191         if (!new_part)
2192                 goto error;
2193         if (!ped_disk_add_partition (disk, new_part, NULL))
2194                 goto error_destroy_new_part;
2195
2196         return 1;
2197
2198 error_destroy_new_part:
2199         ped_partition_destroy (new_part);
2200 error:
2201         return 0;
2202 }
2203
2204 /* There are a few objectives here:
2205  *      - avoid having lots of "free space" partitions lying around, to confuse
2206  * the front end.
2207  *      - ensure that there's enough room to put in the extended partition
2208  * tables, etc.
2209  */
2210 static int
2211 add_logical_part_metadata (PedDisk* disk, const PedPartition* log_part)
2212 {
2213         PedPartition*   ext_part = ped_disk_extended_partition (disk);
2214         PedPartition*   prev = log_part->prev;
2215         PedCHSGeometry  bios_geom;
2216         PedSector       cyl_size;
2217         PedSector       metadata_start;
2218         PedSector       metadata_end;
2219         PedSector       metadata_length;
2220
2221         partition_probe_bios_geometry (ext_part, &bios_geom);
2222         cyl_size = bios_geom.sectors * bios_geom.heads;
2223
2224         /* if there's metadata shortly before the partition (on the same
2225          * cylinder), then make this new metadata partition touch the end of
2226          * the other.  No point having 63 bytes (or whatever) of free space
2227          * partition - just confuses front-ends, etc.
2228          *      Otherwise, start the metadata at the start of the cylinder
2229          */
2230
2231         metadata_end = log_part->geom.start - 1;
2232         metadata_start = ped_round_down_to (metadata_end, cyl_size);
2233         if (prev)
2234                 metadata_start = PED_MAX (metadata_start, prev->geom.end + 1);
2235         else
2236                 metadata_start = PED_MAX (metadata_start,
2237                                           ext_part->geom.start + 1);
2238         metadata_length = metadata_end - metadata_start + 1;
2239
2240         /* partition 5 doesn't need to have any metadata */
2241         if (log_part->num == 5 && metadata_length < bios_geom.sectors)
2242                 return 1;
2243
2244         PED_ASSERT (metadata_length > 0);
2245
2246         return add_metadata_part (disk, PED_PARTITION_LOGICAL,
2247                                   metadata_start, metadata_end);
2248 }
2249
2250 /*
2251  * Find the starting sector number of the first non-free partition,
2252  * set *SECTOR to that value, and return 1.
2253  * If there is no non-free partition, don't modify *SECTOR and return 0.
2254  */
2255 static int
2256 get_start_first_nonfree_part (const PedDisk* disk, PedSector *sector)
2257 {
2258         PedPartition* walk;
2259
2260         // disk->part_list is the first partition on the disk.
2261         if (!disk->part_list)
2262                 return 0;
2263
2264         for (walk = disk->part_list; walk; walk = walk->next) {
2265                 if (walk->type == PED_PARTITION_NORMAL ||
2266                                 walk->type == PED_PARTITION_EXTENDED) {
2267                         *sector = walk->geom.start;
2268                         return 1;
2269                 }
2270         }
2271         return 0;
2272 }
2273
2274 /*
2275  * Find the ending sector number of the last non-free partition,
2276  * set *SECTOR to that value, and return 1.
2277  * If there is no non-free partition, don't modify *SECTOR and return 0.
2278  */
2279 static int
2280 get_end_last_nonfree_part (const PedDisk* disk, PedSector *sector)
2281 {
2282         PedPartition* last_part = NULL;
2283         PedPartition* walk;
2284
2285         // disk->part_list is the first partition on the disk.
2286         if (!disk->part_list)
2287                 return 0;
2288
2289         for (walk = disk->part_list; walk; walk = walk->next) {
2290                 if (walk->type == PED_PARTITION_NORMAL ||
2291                                 walk->type == PED_PARTITION_EXTENDED) {
2292                         last_part = walk;
2293                 }
2294         }
2295
2296         if (!last_part)
2297                 return 0;
2298         else {
2299                 *sector = last_part->geom.end;
2300                 return 1;
2301         }
2302 }
2303
2304 /* Adds metadata placeholder partitions to cover the partition table (and
2305  * "free" space after it that often has bootloader stuff), and the last
2306  * incomplete cylinder at the end of the disk.
2307  *      Parted has to be mindful of the uncertainty of dev->bios_geom.
2308  * It therefore makes sure this metadata doesn't overlap with partitions.
2309  */
2310 static int
2311 add_startend_metadata (PedDisk* disk)
2312 {
2313         PedDevice* dev = disk->dev;
2314         PedSector cyl_size = dev->bios_geom.sectors * dev->bios_geom.heads;
2315         PedSector init_start, init_end, final_start, final_end;
2316
2317         // Ranges for the initial and final metadata partition.
2318         init_start = 0;
2319         if (!get_start_first_nonfree_part(disk, &init_end))
2320                 init_end = dev->bios_geom.sectors - 1;
2321         else
2322                 init_end = PED_MIN (dev->bios_geom.sectors - 1, init_end - 1);
2323
2324         DosDiskData *disk_specific = disk->disk_specific;
2325         if (!disk_specific->cylinder_alignment)
2326                 final_start = dev->length - 1;
2327         else if (!get_end_last_nonfree_part(disk, &final_start))
2328                 final_start = ped_round_down_to (dev->length, cyl_size);
2329         else
2330                 final_start = PED_MAX (final_start + 1,
2331                                 ped_round_down_to (dev->length, cyl_size));
2332         final_end = dev->length - 1;
2333
2334         // Create the metadata partitions.
2335         // init_end <= dev->length for devices that are _real_ small.
2336         if (init_start < init_end &&
2337                         init_end <= dev->length &&
2338                         !add_metadata_part (disk, PED_PARTITION_NORMAL,
2339                                 init_start, init_end))
2340                         return 0;
2341
2342         // init_end < final_start so they dont overlap.  For very small devs.
2343         if (final_start < final_end &&
2344                         init_end < final_start &&
2345                         final_end <= dev->length &&
2346                         !add_metadata_part (disk, PED_PARTITION_NORMAL,
2347                                 final_start, final_end))
2348                         return 0;
2349
2350         return 1;
2351 }
2352
2353 static int
2354 msdos_alloc_metadata (PedDisk* disk)
2355 {
2356         PedPartition*           ext_part;
2357
2358         PED_ASSERT (disk != NULL);
2359         PED_ASSERT (disk->dev != NULL);
2360
2361         if (!add_startend_metadata (disk))
2362                 return 0;
2363
2364         ext_part = ped_disk_extended_partition (disk);
2365         if (ext_part) {
2366                 int             i;
2367                 PedSector       start, end;
2368                 PedCHSGeometry  bios_geom;
2369
2370                 for (i=5; 1; i++) {
2371                         PedPartition* log_part;
2372                         log_part = ped_disk_get_partition (disk, i);
2373                         if (!log_part)
2374                                 break;
2375                         if (!add_logical_part_metadata (disk, log_part))
2376                                 return 0;
2377                 }
2378
2379                 partition_probe_bios_geometry (ext_part, &bios_geom);
2380                 start = ext_part->geom.start;
2381                 end = start + bios_geom.sectors - 1;
2382                 if (ext_part->part_list)
2383                         end = PED_MIN (end,
2384                                        ext_part->part_list->geom.start - 1);
2385                 if (!add_metadata_part (disk, PED_PARTITION_LOGICAL,
2386                                         start, end))
2387                         return 0;
2388         }
2389
2390         return 1;
2391 }
2392
2393 static int
2394 next_primary (const PedDisk* disk)
2395 {
2396         int     i;
2397         for (i=1; i<=DOS_N_PRI_PARTITIONS; i++) {
2398                 if (!ped_disk_get_partition (disk, i))
2399                         return i;
2400         }
2401         return 0;
2402 }
2403
2404 static int _GL_ATTRIBUTE_PURE
2405 next_logical (const PedDisk* disk)
2406 {
2407         int     i;
2408         for (i=5; 1; i++) {
2409                 if (!ped_disk_get_partition (disk, i))
2410                         return i;
2411         }
2412 }
2413
2414 static int
2415 msdos_partition_enumerate (PedPartition* part)
2416 {
2417         PED_ASSERT (part != NULL);
2418         PED_ASSERT (part->disk != NULL);
2419
2420         /* don't re-number a primary partition */
2421         if (part->num != -1 && part->num <= DOS_N_PRI_PARTITIONS)
2422                 return 1;
2423
2424         part->num = -1;
2425
2426         if (part->type & PED_PARTITION_LOGICAL)
2427                 part->num = next_logical (part->disk);
2428         else
2429                 part->num = next_primary (part->disk);
2430
2431         return 1;
2432 }
2433
2434 static int
2435 msdos_get_max_primary_partition_count (const PedDisk* disk)
2436 {
2437         return DOS_N_PRI_PARTITIONS;
2438 }
2439
2440 static bool
2441 msdos_get_max_supported_partition_count(const PedDisk* disk, int *max_n)
2442 {
2443         *max_n = MAX_TOTAL_PART;
2444         return true;
2445 }
2446
2447 #include "pt-common.h"
2448 PT_define_limit_functions (msdos)
2449
2450 static PedDiskOps msdos_disk_ops = {
2451         clobber:                NULL,
2452         write:                  NULL_IF_DISCOVER_ONLY (msdos_write),
2453
2454         disk_set_flag:          msdos_disk_set_flag,
2455         disk_get_flag:          msdos_disk_get_flag,
2456         disk_is_flag_available: msdos_disk_is_flag_available,
2457
2458         partition_set_name:     NULL,
2459         partition_get_name:     NULL,
2460
2461   PT_op_function_initializers (msdos)
2462 };
2463
2464 static PedDiskType msdos_disk_type = {
2465         next:           NULL,
2466         name:           "msdos",
2467         ops:            &msdos_disk_ops,
2468         features:       PED_DISK_TYPE_EXTENDED
2469 };
2470
2471 void
2472 ped_disk_msdos_init ()
2473 {
2474         PED_ASSERT (sizeof (DosRawPartition) == 16);
2475         PED_ASSERT (sizeof (DosRawTable) == 512);
2476
2477         ped_disk_type_register (&msdos_disk_type);
2478 }
2479
2480 void
2481 ped_disk_msdos_done ()
2482 {
2483         ped_disk_type_unregister (&msdos_disk_type);
2484 }