src/add-ons/kernel/partitioning_systems/intel/PartitionMap.cpp

   1 /*
   2  * Copyright 2003-2011, Haiku, Inc. All Rights Reserved.
   3  * Distributed under the terms of the MIT License.
   4  *
   5  * Authors:
   6  *              Ingo Weinhold, bonefish@cs.tu-berlin.de
   7  */
   8
   9
  10 /*!     \file PartitionMap.cpp
  11         \brief Definitions for "intel" style partitions and implementation
  12                    of related classes.
  13 */
  14
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <string.h>
  19
  20 #ifndef _USER_MODE
  21 #       include <util/kernel_cpp.h>
  22 #       include <KernelExport.h>
  23 #else
  24 #       include <new>
  25 #endif
  26 #ifndef _BOOT_MODE
  27 #       include <DiskDeviceTypes.h>
  28 #else
  29 #       include <boot/partitions.h>
  30 #endif
  31
  32 #include "PartitionMap.h"
  33
  34
  35 //#define TRACE_ENABLED
  36 #ifdef TRACE_ENABLED
  37 #       ifdef _USER_MODE
  38 #               define TRACE(x) printf x
  39 #       else
  40 #               define TRACE(x) dprintf x
  41 #       endif
  42 #else
  43 #       define TRACE(x) ;
  44 #endif
  45
  46 using std::nothrow;
  47
  48
  49 static const char* const kUnrecognizedTypeString = "Unrecognized Type ";
  50 static const size_t kUnrecognizedTypeStringLength = 18;
  51
  52 static const struct partition_type kPartitionTypes[] = {
  53     // Can be created (in display order)
  54     { 0x00, "empty", true },
  55     { 0x0f, INTEL_EXTENDED_PARTITION_NAME, true },
  56     { 0x0c, "FAT 32-bit, LBA-mapped", true },
  57     { 0x82, "Linux swap", true },
  58     { 0x83, "Linux native", true },
  59     { 0xa5, "FreeBSD", true },
  60     { 0xa6, "OpenBSD", true },
  61     { 0xa9, "NetBSD", true },
  62     { 0xa8, "MacOS X", true },
  63     { 0xab, "MacOS X boot", true },
  64     { 0xaf, "MacOS X HFS/HFS+", true },
  65     { 0x4d, "QNX 4", true },
  66     { 0xb3, "QNX 6", true },
  67     { 0xeb, BFS_NAME, true },
  68     // Known file system types
  69     { 0x01, "FAT 12-bit", false},
  70     { 0x02, "Xenix root", false },
  71     { 0x03, "Xenix user", false },
  72     { 0x04, "FAT 16-bit (dos 3.0)", false },
  73     { 0x05, INTEL_EXTENDED_PARTITION_NAME, false },
  74     { 0x06, "FAT 16-bit (dos 3.31)", false },
  75     { 0x07, "Windows NT, OS/2 IFS, Advanced Unix", false },
  76     { 0x08, "AIX", false },
  77     { 0x09, "AIX bootable", false },
  78     { 0x0a, "OS/2 Boot Manager", false },
  79     { 0x0b, "FAT 32-bit", false },
  80     { 0x0e, "FAT 16-bit, LBA-mapped", false },
  81     { 0x10, "OPUS", false },
  82     { 0x11, "Hidden FAT 12-bit", false },
  83     { 0x12, "Compaq diagnostic", false },
  84     { 0x14, "Hidden FAT 16-bit", false },
  85     { 0x16, "Hidden FAT 16-bit", false },
  86     { 0x17, "Hidden HPFS/NTFS", false },
  87     { 0x18, "AST SmartSleep", false },
  88     { 0x1b, "Hidden W95 FAT 32-bit", false },
  89     { 0x1c, "Hidden W95 FAT 32-bit", false },
  90     { 0x1e, "Hidden W95 FAT 16-bit", false },
  91     { 0x24, "NEC DOS", false },
  92     { 0x39, "Plan 9", false },
  93     { 0x3c, "PartitionMagic", false },
  94     { 0x40, "Venix 80286", false },
  95     { 0x41, "PPC PReP Boot", false },
  96     { 0x42, "Windows 2000 marker (proprietary extended)",
  97     false },
  98     { 0x4e, "QNX 4 2nd part", false },
  99     { 0x4f, "QNX 4 3rd part", false },
 100     { 0x50, "OnTrack DM", false },
 101     { 0x51, "OnTrack DM6 Aux", false },
 102     { 0x52, "CP/M", false },
 103     { 0x53, "OnTrack DM6 Aux", false },
 104     { 0x54, "OnTrack DM6", false },
 105     { 0x55, "EZ-Drive", false },
 106     { 0x56, "Golden Bow", false },
 107     { 0x5c, "Priam Edisk", false },
 108     { 0x61, "SpeedStor", false },
 109     { 0x63, "GNU HURD", false },
 110     { 0x64, "Novell Netware", false },
 111     { 0x65, "Novell Netware", false },
 112     { 0x70, "DiskSecure Mult", false },
 113     { 0x75, "PC/IX", false },
 114     { 0x78, "XOSL boot loader", false },
 115     { 0x80, "Old Minix", false },
 116     { 0x81, "Minix", false },
 117     { 0x84, "OS/2 hidden", false },
 118     { 0x85, /*"Linux extendend partition"*/INTEL_EXTENDED_PARTITION_NAME,
 119     false },
 120     { 0x86, "NTFS volume set", false },
 121     { 0x87, "NTFS volume set", true },
 122     { 0x88, "Linux plaintext", false },
 123     { 0x8e, "Linux LVM", false },
 124     { 0x93, "Amoeba", false },
 125     { 0x94, "Amoeba BBT", false },
 126     { 0x9f, "BSD/OS", false },
 127     { 0xa0, "IBM Hibernation", false },
 128     { 0xa7, "NextSTEP", false },
 129     { 0xb1, "QNX 6", false},
 130     { 0xb2, "QNX 6", false},
 131     { 0xb7, "BSDI fs", false },
 132     { 0xb8, "BSDI swap", false },
 133     { 0xbe, "Solaris 8 boot", false },
 134     { 0xbf, "Solaris 10", false },
 135     { 0xc1, "DR-DOS FAT", false },
 136     { 0xc4, "DR-DOS FAT", false },
 137     { 0xc6, "DR-DOS FAT", false },
 138     { 0xc7, "Syrinx", false },
 139     { 0xe4, "SpeedStor", false },
 140     { 0xee, "GPT", false },
 141     { 0xef, "EFI", false },
 142     { 0xfb, "VMware VMFS", false },
 143     { 0xfc, "VMware VMKCORE", false },
 144     { 0xfd, "Linux raid auto", false },
 145     { 0, NULL, false }
 146 };
 147
 148 static const struct partition_type kPartitionContentTypes[] = {
 149 #ifndef _USER_MODE
 150         { 0x01, kPartitionTypeFAT12 },
 151         { 0x07, kPartitionTypeEXFAT },
 152         { 0x0c, kPartitionTypeFAT32 },
 153         { 0x0f, kPartitionTypeIntelExtended },
 154         { 0x83, kPartitionTypeBTRFS },
 155         { 0x83, kPartitionTypeEXT2 },
 156         { 0x83, kPartitionTypeEXT3 },
 157         { 0x83, kPartitionTypeReiser },
 158         { 0xaf, kPartitionTypeHFS },
 159         { 0xaf, kPartitionTypeHFSPlus },
 160         { 0xeb, kPartitionTypeBFS },
 161 #endif
 162         { 0, NULL }
 163 };
 164
 165
 166 static const char*
 167 partition_type_string(uint8 type)
 168 {
 169         int32 i;
 170         for (i = 0; kPartitionTypes[i].name ; i++) {
 171                 if (type == kPartitionTypes[i].type)
 172                         return kPartitionTypes[i].name;
 173         }
 174         return NULL;
 175 }
 176
 177
 178 void
 179 get_partition_type_string(uint8 type, char* buffer)
 180 {
 181         if (buffer) {
 182                 if (const char* typeString = partition_type_string(type))
 183                         strcpy(buffer, typeString);
 184                 else
 185                         sprintf(buffer, "%s0x%x", kUnrecognizedTypeString, type);
 186         }
 187 }
 188
 189
 190 static int
 191 cmp_partition_offset(const void* p1, const void* p2)
 192 {
 193         const Partition* partition1 = *(const Partition**)p1;
 194         const Partition* partition2 = *(const Partition**)p2;
 195
 196         if (partition1->Offset() < partition2->Offset())
 197                 return -1;
 198         if (partition1->Offset() > partition2->Offset())
 199                 return 1;
 200
 201         return 0;
 202 }
 203
 204
 205 static int
 206 cmp_offset(const void* o1, const void* o2)
 207 {
 208         off_t offset1 = *static_cast<const off_t*>(o1);
 209         off_t offset2 = *static_cast<const off_t*>(o2);
 210
 211         if (offset1 < offset2)
 212                 return -1;
 213         if (offset1 > offset2)
 214                 return 1;
 215
 216         return 0;
 217 }
 218
 219
 220 static bool
 221 is_inside_partitions(off_t location, const Partition** partitions, int32 count)
 222 {
 223         bool result = false;
 224         if (count > 0) {
 225                 // binary search
 226                 int32 lower = 0;
 227                 int32 upper = count - 1;
 228                 while (lower < upper) {
 229                         int32 mid = (lower + upper) / 2;
 230                         const Partition* midPartition = partitions[mid];
 231                         if (location >= midPartition->Offset() + midPartition->Size())
 232                                 lower = mid + 1;
 233                         else
 234                                 upper = mid;
 235                 }
 236                 const Partition* partition = partitions[lower];
 237                 result = (location >= partition->Offset() &&
 238                                   location < partition->Offset() + partition->Size());
 239         }
 240         return result;
 241 }
 242
 243
 244 //      #pragma mark - PartitionType
 245
 246
 247 PartitionType::PartitionType()
 248         :
 249         fType(0),
 250         fValid(false)
 251 {
 252 }
 253
 254
 255 /*!     \brief Sets the \a type via its ID.
 256         \param type ID of the partition type, it is in the range [0..255].
 257 */
 258 bool
 259 PartitionType::SetType(uint8 type)
 260 {
 261         fType = type;
 262         fValid = partition_type_string(type);
 263         return fValid;
 264 }
 265
 266
 267 /*!     \brief Sets the type via its string name.
 268         \param typeName Name of the partition type.
 269 */
 270 bool
 271 PartitionType::SetType(const char* typeName)
 272 {
 273         for (int32 i = 0; kPartitionTypes[i].name ; i++) {
 274                 if (!strcmp(typeName, kPartitionTypes[i].name)) {
 275                         fType = kPartitionTypes[i].type;
 276                         fValid = true;
 277                         return fValid;
 278                 }
 279         }
 280
 281         // If this is an unrecognized type, parse the type number.
 282         if (strncmp(typeName, kUnrecognizedTypeString,
 283                         kUnrecognizedTypeStringLength) == 0) {
 284                 long type = strtol(typeName + kUnrecognizedTypeStringLength, NULL, 0);
 285                 if (type != 0 && type <= 255) {
 286                         fType = type;
 287                         fValid = true;
 288                         return fValid;
 289                 }
 290         }
 291
 292         fValid = false;
 293         return fValid;
 294 }
 295
 296
 297 /*!     \brief Converts content type to the partition type that fits best.
 298         \param content_type Name of the content type, it is standardized by system.
 299 */
 300 bool
 301 PartitionType::SetContentType(const char* contentType)
 302 {
 303         for (int32 i = 0; kPartitionContentTypes[i].name ; i++) {
 304                 if (!strcmp(contentType, kPartitionContentTypes[i].name)) {
 305                         fType = kPartitionContentTypes[i].type;
 306                         fValid = true;
 307                         return fValid;
 308                 }
 309         }
 310         fValid = false;
 311         return fValid;
 312 }
 313
 314
 315 /*!     \brief Finds next supported partition.
 316 */
 317 bool
 318 PartitionType::FindNext()
 319 {
 320         for (int32 i = 0; kPartitionTypes[i].name; i++) {
 321                 if (fType < kPartitionTypes[i].type) {
 322                         fType = kPartitionTypes[i].type;
 323                         fValid = true;
 324                         return true;
 325                 }
 326         }
 327         fValid = false;
 328         return false;
 329 }
 330
 331
 332 /*!     \fn bool PartitionType::IsValid() const
 333         \brief Check whether the current type is valid.
 334 */
 335
 336 /*!     \fn bool PartitionType::IsEmpty() const
 337         \brief Check whether the current type describes empty type.
 338 */
 339
 340 /*!     \fn bool PartitionType::IsExtended() const
 341         \brief Check whether the current type describes extended partition type.
 342 */
 343
 344 /*!     \fn uint8 PartitionType::Type() const
 345         \brief Returns ID of the current type.
 346 */
 347
 348 /*!     \fn void PartitionType::GetTypeString(char *buffer) const
 349         \brief Returns string name of the current type.
 350         \param buffer Buffer where the name is stored, has to be allocated with
 351         sufficient length.
 352 */
 353
 354
 355 //      #pragma mark - Partition
 356
 357
 358 Partition::Partition()
 359         :
 360         fPartitionTableOffset(0),
 361         fOffset(0),
 362         fSize(0),
 363         fType(0),
 364         fActive(false)
 365 {
 366 }
 367
 368
 369 Partition::Partition(const partition_descriptor* descriptor, off_t tableOffset,
 370                 off_t baseOffset, uint32 blockSize)
 371         :
 372         fPartitionTableOffset(0),
 373         fOffset(0),
 374         fSize(0),
 375         fType(0),
 376         fActive(false)
 377 {
 378         SetTo(descriptor, tableOffset, baseOffset, blockSize);
 379 }
 380
 381
 382 void
 383 Partition::SetTo(const partition_descriptor* descriptor, off_t tableOffset,
 384         off_t baseOffset, uint32 blockSize)
 385 {
 386         TRACE(("Partition::SetTo(): active: %x\n", descriptor->active));
 387         SetTo(baseOffset + (off_t)descriptor->start * blockSize,
 388                 (off_t)descriptor->size * blockSize, descriptor->type,
 389                 descriptor->active, tableOffset, blockSize);
 390 }
 391
 392
 393 void
 394 Partition::SetTo(off_t offset, off_t size, uint8 type, bool active,
 395         off_t tableOffset, uint32 blockSize)
 396 {
 397         fPartitionTableOffset = tableOffset;
 398         fOffset = offset;
 399         fSize = size;
 400         fType = type;
 401         fActive = active;
 402         fBlockSize = blockSize;
 403
 404         if (fSize == 0)
 405                 Unset();
 406 }
 407
 408
 409 void
 410 Partition::Unset()
 411 {
 412         fPartitionTableOffset = 0;
 413         fOffset = 0;
 414         fSize = 0;
 415         fType = 0;
 416         fActive = false;
 417 }
 418
 419
 420 bool
 421 Partition::CheckLocation(off_t sessionSize) const
 422 {
 423         if (fBlockSize == 0)
 424                 return false;
 425         // offsets and size must be block aligned, partition table and partition must
 426         // lie within the session
 427         if (fPartitionTableOffset % fBlockSize != 0) {
 428                 TRACE(("Partition::CheckLocation() - bad partition table offset: %lld "
 429                         "(session: %lld), (fBlockSize: %ld)\n", fPartitionTableOffset,
 430                         sessionSize, fBlockSize));
 431                 return false;
 432         }
 433         if (fOffset % fBlockSize != 0) {
 434                 TRACE(("Partition::CheckLocation() - bad offset: %lld "
 435                         "(session: %lld)\n", fOffset, sessionSize));
 436                 return false;
 437         }
 438         if (fSize % fBlockSize != 0) {
 439                 TRACE(("Partition::CheckLocation() - bad size: %lld "
 440                         "(session: %lld)\n", fSize, sessionSize));
 441                 return false;
 442         }
 443         if (fPartitionTableOffset < 0 || fPartitionTableOffset >= sessionSize) {
 444                 TRACE(("Partition::CheckLocation() - partition table offset outside "
 445                         "session: %lld (session size: %lld)\n", fPartitionTableOffset,
 446                         sessionSize));
 447                 return false;
 448         }
 449         if (fOffset < 0) {
 450                 TRACE(("Partition::CheckLocation() - offset before session: %lld "
 451                         "(session: %lld)\n", fOffset, sessionSize));
 452                 return false;
 453         }
 454         if (fOffset + fSize > sessionSize) {
 455                 TRACE(("Partition::CheckLocation() - end after session: %lld "
 456                         "(session: %lld)\n", fOffset + fSize, sessionSize));
 457                 return false;
 458         }
 459         return true;
 460 }
 461
 462
 463 bool
 464 Partition::FitSizeToSession(off_t sessionSize)
 465 {
 466         // To work around buggy (or older) BIOS, we shrink the partition size to
 467         // always fit into its session - this should improve detection of boot
 468         // partitions (see bug #238 for more information).
 469         // Also, the drive size is obviously reported differently sometimes; this
 470         // should let us read problematic drives - let the file system figure out
 471         // if something is wrong.
 472         if (sessionSize < fOffset + fSize && sessionSize > fOffset) {
 473                 fSize = sessionSize - fOffset;
 474                 return true;
 475         }
 476
 477         return false;
 478 }
 479
 480
 481 //      #pragma mark - PrimaryPartition
 482
 483
 484 PrimaryPartition::PrimaryPartition()
 485         :
 486         Partition(),
 487         fHead(NULL),
 488         fTail(NULL),
 489         fLogicalPartitionCount(0)
 490 {
 491 }
 492
 493
 494 void
 495 PrimaryPartition::SetTo(const partition_descriptor* descriptor,
 496         off_t tableOffset, uint32 blockSize)
 497 {
 498         Unset();
 499         Partition::SetTo(descriptor, tableOffset, 0, blockSize);
 500 }
 501
 502
 503 void
 504 PrimaryPartition::SetTo(off_t offset, off_t size, uint8 type, bool active,
 505         uint32 blockSize)
 506 {
 507         Unset();
 508         Partition::SetTo(offset, size, type, active, 0, blockSize);
 509 }
 510
 511
 512 void
 513 PrimaryPartition::Unset()
 514 {
 515         while (LogicalPartition* partition = fHead) {
 516                 fHead = partition->Next();
 517                 delete partition;
 518         }
 519         fHead = NULL;
 520         fTail = NULL;
 521         fLogicalPartitionCount = 0;
 522         Partition::Unset();
 523 }
 524
 525
 526 status_t
 527 PrimaryPartition::Assign(const PrimaryPartition& other)
 528 {
 529         partition_descriptor descriptor;
 530         other.GetPartitionDescriptor(&descriptor);
 531         SetTo(&descriptor, 0, other.BlockSize());
 532
 533         const LogicalPartition* otherLogical = other.fHead;
 534         while (otherLogical) {
 535                 off_t tableOffset = otherLogical->PartitionTableOffset();
 536                 otherLogical->GetPartitionDescriptor(&descriptor);
 537
 538                 LogicalPartition* logical = new(nothrow) LogicalPartition(
 539                         &descriptor, tableOffset, this);
 540                 if (!logical)
 541                         return B_NO_MEMORY;
 542
 543                 AddLogicalPartition(logical);
 544
 545                 otherLogical = otherLogical->Next();
 546         }
 547
 548         return B_OK;
 549 }
 550
 551
 552 void
 553 PrimaryPartition::GetPartitionDescriptor(partition_descriptor* descriptor) const
 554 {
 555         if (IsEmpty()) {
 556                 memset(descriptor, 0, sizeof(partition_descriptor));
 557         } else {
 558                 descriptor->start = Offset() / BlockSize();
 559                 descriptor->size = Size() / BlockSize();
 560                 descriptor->type = Type();
 561                 descriptor->active = Active() ? 0x80 : 0x00;
 562                 descriptor->begin.Unset();
 563                 descriptor->end.Unset();
 564         }
 565 }
 566
 567
 568 LogicalPartition*
 569 PrimaryPartition::LogicalPartitionAt(int32 index) const
 570 {
 571         LogicalPartition* partition = NULL;
 572         if (index >= 0 && index < fLogicalPartitionCount) {
 573                 for (partition = fHead; index > 0; index--)
 574                         partition = partition->Next();
 575         }
 576         return partition;
 577 }
 578
 579
 580 void
 581 PrimaryPartition::AddLogicalPartition(LogicalPartition* partition)
 582 {
 583         if (!partition)
 584                 return;
 585
 586         partition->SetPrimaryPartition(this);
 587         partition->SetPrevious(fTail);
 588         if (fTail) {
 589                 fTail->SetNext(partition);
 590                 fTail = partition;
 591         } else
 592                 fHead = fTail = partition;
 593
 594         partition->SetNext(NULL);
 595
 596         fLogicalPartitionCount++;
 597 }
 598
 599
 600 void
 601 PrimaryPartition::RemoveLogicalPartition(LogicalPartition* partition)
 602 {
 603         if (!partition || partition->GetPrimaryPartition() != this)
 604                 return;
 605
 606         LogicalPartition* prev = partition->Previous();
 607         LogicalPartition* next = partition->Next();
 608
 609         if (prev)
 610                 prev->SetNext(next);
 611         else
 612                 fHead = next;
 613         if (next)
 614                 next->SetPrevious(prev);
 615         else
 616                 fTail = prev;
 617
 618         fLogicalPartitionCount--;
 619
 620         partition->SetNext(NULL);
 621         partition->SetPrevious(NULL);
 622         partition->SetPrimaryPartition(NULL);
 623 }
 624
 625
 626 //      #pragma mark - LogicalPartition
 627
 628
 629 LogicalPartition::LogicalPartition()
 630         :
 631         Partition(),
 632         fPrimary(NULL),
 633         fNext(NULL),
 634         fPrevious(NULL)
 635 {
 636 }
 637
 638
 639 LogicalPartition::LogicalPartition(const partition_descriptor* descriptor,
 640                 off_t tableOffset, PrimaryPartition* primary)
 641         :
 642         Partition(),
 643         fPrimary(NULL),
 644         fNext(NULL),
 645         fPrevious(NULL)
 646 {
 647         SetTo(descriptor, tableOffset, primary);
 648 }
 649
 650
 651 void
 652 LogicalPartition::SetTo(const partition_descriptor* descriptor,
 653         off_t tableOffset, PrimaryPartition* primary)
 654 {
 655         Unset();
 656         if (descriptor && primary) {
 657                 // There are two types of LogicalPartitions. There are so called
 658                 // "inner extended" partitions and the "real" logical partitions
 659                 // which contain data. The "inner extended" partitions don't contain
 660                 // data and are only used to point to the next partition table in the
 661                 // linked list of logical partitions. For "inner extended" partitions,
 662                 // the baseOffset is in relation to the (first sector of the)
 663                 // "primary extended" partition, in another words, all inner extended
 664                 // partitions use the same base offset for reference.
 665                 // The data containing, real logical partitions use the offset of the
 666                 // partition table that contains their partition descriptor as their
 667                 // baseOffset.
 668                 off_t baseOffset = descriptor->is_extended()
 669                         ? primary->Offset() : tableOffset;
 670                 Partition::SetTo(descriptor, tableOffset, baseOffset,
 671                         primary->BlockSize());
 672                 fPrimary = primary;
 673         }
 674 }
 675
 676
 677 void
 678 LogicalPartition::SetTo(off_t offset, off_t size, uint8 type, bool active,
 679         off_t tableOffset, PrimaryPartition* primary)
 680 {
 681         Unset();
 682         if (primary) {
 683                 Partition::SetTo(offset, size, type, active, tableOffset,
 684                         primary->BlockSize());
 685                 fPrimary = primary;
 686         }
 687 }
 688
 689
 690 void
 691 LogicalPartition::Unset()
 692 {
 693         fPrimary = NULL;
 694         fNext = NULL;
 695         fPrevious = NULL;
 696         Partition::Unset();
 697 }
 698
 699
 700 void
 701 LogicalPartition::GetPartitionDescriptor(partition_descriptor* descriptor,
 702         bool inner) const
 703 {
 704         PrimaryPartition* primary = GetPrimaryPartition();
 705         if (inner) {
 706                 descriptor->start = (PartitionTableOffset() - primary->Offset())
 707                         / BlockSize();
 708                 descriptor->type = primary->Type();
 709         } else {
 710                 descriptor->start = (Offset() - PartitionTableOffset()) / BlockSize();
 711                 descriptor->type = Type();
 712         }
 713
 714         descriptor->size = Size() / BlockSize();
 715         descriptor->active = 0x00;
 716         descriptor->begin.Unset();
 717         descriptor->end.Unset();
 718 }
 719
 720
 721 //      #pragma mark - PartitionMap
 722
 723
 724 PartitionMap::PartitionMap()
 725 {
 726         for (int32 i = 0; i < 4; i++)
 727                 fPrimaries[i].SetIndex(i);
 728 }
 729
 730
 731 PartitionMap::~PartitionMap()
 732 {
 733 }
 734
 735
 736 void
 737 PartitionMap::Unset()
 738 {
 739         for (int32 i = 0; i < 4; i++)
 740                 fPrimaries[i].Unset();
 741 }
 742
 743
 744 status_t
 745 PartitionMap::Assign(const PartitionMap& other)
 746 {
 747         for (int32 i = 0; i < 4; i++) {
 748                 status_t error = fPrimaries[i].Assign(other.fPrimaries[i]);
 749                 if (error != B_OK)
 750                         return error;
 751         }
 752
 753         return B_OK;
 754 }
 755
 756
 757 PrimaryPartition*
 758 PartitionMap::PrimaryPartitionAt(int32 index)
 759 {
 760         PrimaryPartition* partition = NULL;
 761         if (index >= 0 && index < 4)
 762                 partition = fPrimaries + index;
 763         return partition;
 764 }
 765
 766
 767 const PrimaryPartition*
 768 PartitionMap::PrimaryPartitionAt(int32 index) const
 769 {
 770         const PrimaryPartition* partition = NULL;
 771         if (index >= 0 && index < 4)
 772                 partition = fPrimaries + index;
 773         return partition;
 774 }
 775
 776
 777 int32
 778 PartitionMap::CountNonEmptyPrimaryPartitions() const
 779 {
 780         int32 count = 0;
 781         for (int32 i = 0; i < 4; i++) {
 782                 if (!fPrimaries[i].IsEmpty())
 783                         count++;
 784         }
 785
 786         return count;
 787 }
 788
 789
 790 int32
 791 PartitionMap::ExtendedPartitionIndex() const
 792 {
 793         for (int32 i = 0; i < 4; i++) {
 794                 if (fPrimaries[i].IsExtended())
 795                         return i;
 796         }
 797
 798         return -1;
 799 }
 800
 801
 802 int32
 803 PartitionMap::CountPartitions() const
 804 {
 805         int32 count = 4;
 806         for (int32 i = 0; i < 4; i++)
 807                 count += fPrimaries[i].CountLogicalPartitions();
 808         return count;
 809 }
 810
 811
 812 int32
 813 PartitionMap::CountNonEmptyPartitions() const
 814 {
 815         int32 count = 0;
 816         for (int32 i = CountPartitions() - 1; i >= 0; i--) {
 817                 if (!PartitionAt(i)->IsEmpty())
 818                         count++;
 819         }
 820
 821         return count;
 822 }
 823
 824
 825 Partition*
 826 PartitionMap::PartitionAt(int32 index)
 827 {
 828         Partition* partition = NULL;
 829         int32 count = CountPartitions();
 830         if (index >= 0 && index < count) {
 831                 if (index < 4)
 832                         partition  = fPrimaries + index;
 833                 else {
 834                         index -= 4;
 835                         int32 primary = 0;
 836                         while (index >= fPrimaries[primary].CountLogicalPartitions()) {
 837                                 index -= fPrimaries[primary].CountLogicalPartitions();
 838                                 primary++;
 839                         }
 840                         partition = fPrimaries[primary].LogicalPartitionAt(index);
 841                 }
 842         }
 843         return partition;
 844 }
 845
 846
 847 const Partition*
 848 PartitionMap::PartitionAt(int32 index) const
 849 {
 850         return const_cast<PartitionMap*>(this)->PartitionAt(index);
 851 }
 852
 853
 854 bool
 855 PartitionMap::Check(off_t sessionSize) const
 856 {
 857         int32 partitionCount = CountPartitions();
 858
 859         // 1. check partition locations
 860         for (int32 i = 0; i < partitionCount; i++) {
 861                 if (!PartitionAt(i)->CheckLocation(sessionSize))
 862                         return false;
 863         }
 864
 865         // 2. check overlapping of partitions and location of partition tables
 866         bool result = true;
 867         Partition** byOffset = new(nothrow) Partition*[partitionCount];
 868         off_t* tableOffsets = new(nothrow) off_t[partitionCount - 3];
 869         if (byOffset && tableOffsets) {
 870                 // fill the arrays
 871                 int32 byOffsetCount = 0;
 872                 int32 tableOffsetCount = 1;     // primary partition table
 873                 tableOffsets[0] = 0;
 874                 for (int32 i = 0; i < partitionCount; i++) {
 875                         Partition* partition = (Partition*)PartitionAt(i);
 876                         if (!partition->IsExtended())
 877                                 byOffset[byOffsetCount++] = partition;
 878
 879                         // add only logical partition partition table locations
 880                         if (i >= 4) {
 881                                 tableOffsets[tableOffsetCount++]
 882                                         = partition->PartitionTableOffset();
 883                         }
 884                 }
 885
 886                 // sort the arrays
 887                 qsort(byOffset, byOffsetCount, sizeof(Partition*),
 888                         cmp_partition_offset);
 889                 qsort(tableOffsets, tableOffsetCount, sizeof(off_t), cmp_offset);
 890
 891                 // check for overlappings
 892                 off_t nextOffset = 0;
 893                 for (int32 i = 0; i < byOffsetCount; i++) {
 894                         Partition* partition = byOffset[i];
 895                         if (partition->Offset() < nextOffset && i > 0) {
 896                                 Partition* previousPartition = byOffset[i - 1];
 897                                 off_t previousSize = previousPartition->Size()
 898                                         - (nextOffset - partition->Offset());
 899                                 TRACE(("intel: PartitionMap::Check(): "));
 900                                 if (previousSize == 0) {
 901                                         previousPartition->Unset();
 902                                         TRACE(("partition offset hides previous partition."
 903                                                 " Removing previous partition from disk layout.\n"));
 904                                 } else {
 905                                         TRACE(("overlapping partitions! Setting partition %ld "
 906                                                 "size to %lld\n", i - 1, previousSize));
 907                                         previousPartition->SetSize(previousSize);
 908                                 }
 909                         }
 910                         nextOffset = partition->Offset() + partition->Size();
 911                 }
 912
 913                 // check uniqueness of partition table offsets and whether they lie
 914                 // outside of the non-extended partitions
 915                 if (result) {
 916                         for (int32 i = 0; i < tableOffsetCount; i++) {
 917                                 if (i > 0 && tableOffsets[i] == tableOffsets[i - 1]) {
 918                                         TRACE(("intel: PartitionMap::Check(): same partition table "
 919                                                 "for different extended partitions!\n"));
 920                                         result = false;
 921                                         break;
 922                                 } else if (is_inside_partitions(tableOffsets[i],
 923                                                 (const Partition**)byOffset, byOffsetCount)) {
 924                                         TRACE(("intel: PartitionMap::Check(): a partition table "
 925                                                 "lies inside a non-extended partition!\n"));
 926                                         result = false;
 927                                         break;
 928                                 }
 929                         }
 930                 }
 931         } else
 932                 result = false;         // no memory: assume failure
 933
 934         // cleanup
 935         delete[] byOffset;
 936         delete[] tableOffsets;
 937
 938         return result;
 939 }
 940
 941
 942 const partition_type*
 943 PartitionMap::GetNextSupportedPartitionType(uint32 index)
 944 {
 945         if (index > (sizeof(kPartitionTypes) / sizeof(partition_type) - 2))
 946                 return NULL;
 947
 948         return kPartitionTypes + index;
 949 }