/*
* Copyright 2003-2011, Haiku, Inc. All Rights Reserved.
* Distributed under the terms of the MIT License.
*
* Authors:
* Ingo Weinhold, bonefish@cs.tu-berlin.de
*/
/*! \file PartitionMap.cpp
\brief Definitions for "intel" style partitions and implementation
of related classes.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef _USER_MODE
# include <util/kernel_cpp.h>
# include <KernelExport.h>
#else
# include <new>
#endif
#ifndef _BOOT_MODE
# include <DiskDeviceTypes.h>
#else
# include <boot/partitions.h>
#endif
#include "PartitionMap.h"
//#define TRACE_ENABLED
#ifdef TRACE_ENABLED
# ifdef _USER_MODE
# define TRACE(x) printf x
# else
# define TRACE(x) dprintf x
# endif
#else
# define TRACE(x) ;
#endif
using std::nothrow;
static const char* const kUnrecognizedTypeString = "Unrecognized Type ";
static const size_t kUnrecognizedTypeStringLength = 18;
static const struct partition_type kPartitionTypes[] = {
// Can be created (in display order)
{ 0x00, "empty", true },
{ 0x0f, INTEL_EXTENDED_PARTITION_NAME, true },
{ 0x0c, "FAT 32-bit, LBA-mapped", true },
{ 0x82, "Linux swap", true },
{ 0x83, "Linux native", true },
{ 0xa5, "FreeBSD", true },
{ 0xa6, "OpenBSD", true },
{ 0xa9, "NetBSD", true },
{ 0xa8, "MacOS X", true },
{ 0xab, "MacOS X boot", true },
{ 0xaf, "MacOS X HFS/HFS+", true },
{ 0x4d, "QNX 4", true },
{ 0xb3, "QNX 6", true },
{ 0xeb, BFS_NAME, true },
// Known file system types
{ 0x01, "FAT 12-bit", false},
{ 0x02, "Xenix root", false },
{ 0x03, "Xenix user", false },
{ 0x04, "FAT 16-bit (dos 3.0)", false },
{ 0x05, INTEL_EXTENDED_PARTITION_NAME, false },
{ 0x06, "FAT 16-bit (dos 3.31)", false },
{ 0x07, "Windows NT, OS/2 IFS, Advanced Unix", false },
{ 0x08, "AIX", false },
{ 0x09, "AIX bootable", false },
{ 0x0a, "OS/2 Boot Manager", false },
{ 0x0b, "FAT 32-bit", false },
{ 0x0e, "FAT 16-bit, LBA-mapped", false },
{ 0x10, "OPUS", false },
{ 0x11, "Hidden FAT 12-bit", false },
{ 0x12, "Compaq diagnostic", false },
{ 0x14, "Hidden FAT 16-bit", false },
{ 0x16, "Hidden FAT 16-bit", false },
{ 0x17, "Hidden HPFS/NTFS", false },
{ 0x18, "AST SmartSleep", false },
{ 0x1b, "Hidden W95 FAT 32-bit", false },
{ 0x1c, "Hidden W95 FAT 32-bit", false },
{ 0x1e, "Hidden W95 FAT 16-bit", false },
{ 0x24, "NEC DOS", false },
{ 0x39, "Plan 9", false },
{ 0x3c, "PartitionMagic", false },
{ 0x40, "Venix 80286", false },
{ 0x41, "PPC PReP Boot", false },
{ 0x42, "Windows 2000 marker (proprietary extended)",
false },
{ 0x4e, "QNX 4 2nd part", false },
{ 0x4f, "QNX 4 3rd part", false },
{ 0x50, "OnTrack DM", false },
{ 0x51, "OnTrack DM6 Aux", false },
{ 0x52, "CP/M", false },
{ 0x53, "OnTrack DM6 Aux", false },
{ 0x54, "OnTrack DM6", false },
{ 0x55, "EZ-Drive", false },
{ 0x56, "Golden Bow", false },
{ 0x5c, "Priam Edisk", false },
{ 0x61, "SpeedStor", false },
{ 0x63, "GNU HURD", false },
{ 0x64, "Novell Netware", false },
{ 0x65, "Novell Netware", false },
{ 0x70, "DiskSecure Mult", false },
{ 0x75, "PC/IX", false },
{ 0x78, "XOSL boot loader", false },
{ 0x80, "Old Minix", false },
{ 0x81, "Minix", false },
{ 0x84, "OS/2 hidden", false },
{ 0x85, /*"Linux extendend partition"*/INTEL_EXTENDED_PARTITION_NAME,
false },
{ 0x86, "NTFS volume set", false },
{ 0x87, "NTFS volume set", true },
{ 0x88, "Linux plaintext", false },
{ 0x8e, "Linux LVM", false },
{ 0x93, "Amoeba", false },
{ 0x94, "Amoeba BBT", false },
{ 0x9f, "BSD/OS", false },
{ 0xa0, "IBM Hibernation", false },
{ 0xa7, "NextSTEP", false },
{ 0xb1, "QNX 6", false},
{ 0xb2, "QNX 6", false},
{ 0xb7, "BSDI fs", false },
{ 0xb8, "BSDI swap", false },
{ 0xbe, "Solaris 8 boot", false },
{ 0xbf, "Solaris 10", false },
{ 0xc1, "DR-DOS FAT", false },
{ 0xc4, "DR-DOS FAT", false },
{ 0xc6, "DR-DOS FAT", false },
{ 0xc7, "Syrinx", false },
{ 0xe4, "SpeedStor", false },
{ 0xee, "GPT", false },
{ 0xef, "EFI", false },
{ 0xfb, "VMware VMFS", false },
{ 0xfc, "VMware VMKCORE", false },
{ 0xfd, "Linux raid auto", false },
{ 0, NULL, false }
};
static const struct partition_type kPartitionContentTypes[] = {
#ifndef _USER_MODE
{ 0x01, kPartitionTypeFAT12 },
{ 0x07, kPartitionTypeEXFAT },
{ 0x0c, kPartitionTypeFAT32 },
{ 0x0f, kPartitionTypeIntelExtended },
{ 0x83, kPartitionTypeBTRFS },
{ 0x83, kPartitionTypeEXT2 },
{ 0x83, kPartitionTypeEXT3 },
{ 0x83, kPartitionTypeReiser },
{ 0xaf, kPartitionTypeHFS },
{ 0xaf, kPartitionTypeHFSPlus },
{ 0xeb, kPartitionTypeBFS },
#endif
{ 0, NULL }
};
static const char*
partition_type_string(uint8 type)
{
int32 i;
for (i = 0; kPartitionTypes[i].name ; i++) {
if (type == kPartitionTypes[i].type)
return kPartitionTypes[i].name;
}
return NULL;
}
void
get_partition_type_string(uint8 type, char* buffer)
{
if (buffer) {
if (const char* typeString = partition_type_string(type))
strcpy(buffer, typeString);
else
sprintf(buffer, "%s0x%x", kUnrecognizedTypeString, type);
}
}
static int
cmp_partition_offset(const void* p1, const void* p2)
{
const Partition* partition1 = *(const Partition**)p1;
const Partition* partition2 = *(const Partition**)p2;
if (partition1->Offset() < partition2->Offset())
return -1;
if (partition1->Offset() > partition2->Offset())
return 1;
return 0;
}
static int
cmp_offset(const void* o1, const void* o2)
{
off_t offset1 = *static_cast<const off_t*>(o1);
off_t offset2 = *static_cast<const off_t*>(o2);
if (offset1 < offset2)
return -1;
if (offset1 > offset2)
return 1;
return 0;
}
static bool
is_inside_partitions(off_t location, const Partition** partitions, int32 count)
{
bool result = false;
if (count > 0) {
// binary search
int32 lower = 0;
int32 upper = count - 1;
while (lower < upper) {
int32 mid = (lower + upper) / 2;
const Partition* midPartition = partitions[mid];
if (location >= midPartition->Offset() + midPartition->Size())
lower = mid + 1;
else
upper = mid;
}
const Partition* partition = partitions[lower];
result = (location >= partition->Offset() &&
location < partition->Offset() + partition->Size());
}
return result;
}
// #pragma mark - PartitionType
PartitionType::PartitionType()
:
fType(0),
fValid(false)
{
}
/*! \brief Sets the \a type via its ID.
\param type ID of the partition type, it is in the range [0..255].
*/
bool
PartitionType::SetType(uint8 type)
{
fType = type;
fValid = partition_type_string(type);
return fValid;
}
/*! \brief Sets the type via its string name.
\param typeName Name of the partition type.
*/
bool
PartitionType::SetType(const char* typeName)
{
for (int32 i = 0; kPartitionTypes[i].name ; i++) {
if (!strcmp(typeName, kPartitionTypes[i].name)) {
fType = kPartitionTypes[i].type;
fValid = true;
return fValid;
}
}
// If this is an unrecognized type, parse the type number.
if (strncmp(typeName, kUnrecognizedTypeString,
kUnrecognizedTypeStringLength) == 0) {
long type = strtol(typeName + kUnrecognizedTypeStringLength, NULL, 0);
if (type != 0 && type <= 255) {
fType = type;
fValid = true;
return fValid;
}
}
fValid = false;
return fValid;
}
/*! \brief Converts content type to the partition type that fits best.
\param content_type Name of the content type, it is standardized by system.
*/
bool
PartitionType::SetContentType(const char* contentType)
{
for (int32 i = 0; kPartitionContentTypes[i].name ; i++) {
if (!strcmp(contentType, kPartitionContentTypes[i].name)) {
fType = kPartitionContentTypes[i].type;
fValid = true;
return fValid;
}
}
fValid = false;
return fValid;
}
/*! \brief Finds next supported partition.
*/
bool
PartitionType::FindNext()
{
for (int32 i = 0; kPartitionTypes[i].name; i++) {
if (fType < kPartitionTypes[i].type) {
fType = kPartitionTypes[i].type;
fValid = true;
return true;
}
}
fValid = false;
return false;
}
/*! \fn bool PartitionType::IsValid() const
\brief Check whether the current type is valid.
*/
/*! \fn bool PartitionType::IsEmpty() const
\brief Check whether the current type describes empty type.
*/
/*! \fn bool PartitionType::IsExtended() const
\brief Check whether the current type describes extended partition type.
*/
/*! \fn uint8 PartitionType::Type() const
\brief Returns ID of the current type.
*/
/*! \fn void PartitionType::GetTypeString(char *buffer) const
\brief Returns string name of the current type.
\param buffer Buffer where the name is stored, has to be allocated with
sufficient length.
*/
// #pragma mark - Partition
Partition::Partition()
:
fPartitionTableOffset(0),
fOffset(0),
fSize(0),
fType(0),
fActive(false)
{
}
Partition::Partition(const partition_descriptor* descriptor, off_t tableOffset,
off_t baseOffset, uint32 blockSize)
:
fPartitionTableOffset(0),
fOffset(0),
fSize(0),
fType(0),
fActive(false)
{
SetTo(descriptor, tableOffset, baseOffset, blockSize);
}
void
Partition::SetTo(const partition_descriptor* descriptor, off_t tableOffset,
off_t baseOffset, uint32 blockSize)
{
TRACE(("Partition::SetTo(): active: %x\n", descriptor->active));
SetTo(baseOffset + (off_t)descriptor->start * blockSize,
(off_t)descriptor->size * blockSize, descriptor->type,
descriptor->active, tableOffset, blockSize);
}
void
Partition::SetTo(off_t offset, off_t size, uint8 type, bool active,
off_t tableOffset, uint32 blockSize)
{
fPartitionTableOffset = tableOffset;
fOffset = offset;
fSize = size;
fType = type;
fActive = active;
fBlockSize = blockSize;
if (fSize == 0)
Unset();
}
void
Partition::Unset()
{
fPartitionTableOffset = 0;
fOffset = 0;
fSize = 0;
fType = 0;
fActive = false;
}
bool
Partition::CheckLocation(off_t sessionSize) const
{
if (fBlockSize == 0)
return false;
// offsets and size must be block aligned, partition table and partition must
// lie within the session
if (fPartitionTableOffset % fBlockSize != 0) {
TRACE(("Partition::CheckLocation() - bad partition table offset: %lld "
"(session: %lld), (fBlockSize: %ld)\n", fPartitionTableOffset,
sessionSize, fBlockSize));
return false;
}
if (fOffset % fBlockSize != 0) {
TRACE(("Partition::CheckLocation() - bad offset: %lld "
"(session: %lld)\n", fOffset, sessionSize));
return false;
}
if (fSize % fBlockSize != 0) {
TRACE(("Partition::CheckLocation() - bad size: %lld "
"(session: %lld)\n", fSize, sessionSize));
return false;
}
if (fPartitionTableOffset < 0 || fPartitionTableOffset >= sessionSize) {
TRACE(("Partition::CheckLocation() - partition table offset outside "
"session: %lld (session size: %lld)\n", fPartitionTableOffset,
sessionSize));
return false;
}
if (fOffset < 0) {
TRACE(("Partition::CheckLocation() - offset before session: %lld "
"(session: %lld)\n", fOffset, sessionSize));
return false;
}
if (fOffset + fSize > sessionSize) {
TRACE(("Partition::CheckLocation() - end after session: %lld "
"(session: %lld)\n", fOffset + fSize, sessionSize));
return false;
}
return true;
}
bool
Partition::FitSizeToSession(off_t sessionSize)
{
// To work around buggy (or older) BIOS, we shrink the partition size to
// always fit into its session - this should improve detection of boot
// partitions (see bug #238 for more information).
// Also, the drive size is obviously reported differently sometimes; this
// should let us read problematic drives - let the file system figure out
// if something is wrong.
if (sessionSize < fOffset + fSize && sessionSize > fOffset) {
fSize = sessionSize - fOffset;
return true;
}
return false;
}
// #pragma mark - PrimaryPartition
PrimaryPartition::PrimaryPartition()
:
Partition(),
fHead(NULL),
fTail(NULL),
fLogicalPartitionCount(0)
{
}
void
PrimaryPartition::SetTo(const partition_descriptor* descriptor,
off_t tableOffset, uint32 blockSize)
{
Unset();
Partition::SetTo(descriptor, tableOffset, 0, blockSize);
}
void
PrimaryPartition::SetTo(off_t offset, off_t size, uint8 type, bool active,
uint32 blockSize)
{
Unset();
Partition::SetTo(offset, size, type, active, 0, blockSize);
}
void
PrimaryPartition::Unset()
{
while (LogicalPartition* partition = fHead) {
fHead = partition->Next();
delete partition;
}
fHead = NULL;
fTail = NULL;
fLogicalPartitionCount = 0;
Partition::Unset();
}
status_t
PrimaryPartition::Assign(const PrimaryPartition& other)
{
partition_descriptor descriptor;
other.GetPartitionDescriptor(&descriptor);
SetTo(&descriptor, 0, other.BlockSize());
const LogicalPartition* otherLogical = other.fHead;
while (otherLogical) {
off_t tableOffset = otherLogical->PartitionTableOffset();
otherLogical->GetPartitionDescriptor(&descriptor);
LogicalPartition* logical = new(nothrow) LogicalPartition(
&descriptor, tableOffset, this);
if (!logical)
return B_NO_MEMORY;
AddLogicalPartition(logical);
otherLogical = otherLogical->Next();
}
return B_OK;
}
void
PrimaryPartition::GetPartitionDescriptor(partition_descriptor* descriptor) const
{
if (IsEmpty()) {
memset(descriptor, 0, sizeof(partition_descriptor));
} else {
descriptor->start = Offset() / BlockSize();
descriptor->size = Size() / BlockSize();
descriptor->type = Type();
descriptor->active = Active() ? 0x80 : 0x00;
descriptor->begin.SetUnused();
descriptor->end.SetUnused();
}
}
LogicalPartition*
PrimaryPartition::LogicalPartitionAt(int32 index) const
{
LogicalPartition* partition = NULL;
if (index >= 0 && index < fLogicalPartitionCount) {
for (partition = fHead; index > 0; index--)
partition = partition->Next();
}
return partition;
}
void
PrimaryPartition::AddLogicalPartition(LogicalPartition* partition)
{
if (!partition)
return;
partition->SetPrimaryPartition(this);
partition->SetPrevious(fTail);
if (fTail) {
fTail->SetNext(partition);
fTail = partition;
} else
fHead = fTail = partition;
partition->SetNext(NULL);
fLogicalPartitionCount++;
}
void
PrimaryPartition::RemoveLogicalPartition(LogicalPartition* partition)
{
if (!partition || partition->GetPrimaryPartition() != this)
return;
LogicalPartition* prev = partition->Previous();
LogicalPartition* next = partition->Next();
if (prev)
prev->SetNext(next);
else
fHead = next;
if (next)
next->SetPrevious(prev);
else
fTail = prev;
fLogicalPartitionCount--;
partition->SetNext(NULL);
partition->SetPrevious(NULL);
partition->SetPrimaryPartition(NULL);
}
// #pragma mark - LogicalPartition
LogicalPartition::LogicalPartition()
:
Partition(),
fPrimary(NULL),
fNext(NULL),
fPrevious(NULL)
{
}
LogicalPartition::LogicalPartition(const partition_descriptor* descriptor,
off_t tableOffset, PrimaryPartition* primary)
:
Partition(),
fPrimary(NULL),
fNext(NULL),
fPrevious(NULL)
{
SetTo(descriptor, tableOffset, primary);
}
void
LogicalPartition::SetTo(const partition_descriptor* descriptor,
off_t tableOffset, PrimaryPartition* primary)
{
Unset();
if (descriptor && primary) {
// There are two types of LogicalPartitions. There are so called
// "inner extended" partitions and the "real" logical partitions
// which contain data. The "inner extended" partitions don't contain
// data and are only used to point to the next partition table in the
// linked list of logical partitions. For "inner extended" partitions,
// the baseOffset is in relation to the (first sector of the)
// "primary extended" partition, in another words, all inner extended
// partitions use the same base offset for reference.
// The data containing, real logical partitions use the offset of the
// partition table that contains their partition descriptor as their
// baseOffset.
off_t baseOffset = descriptor->is_extended()
? primary->Offset() : tableOffset;
Partition::SetTo(descriptor, tableOffset, baseOffset,
primary->BlockSize());
fPrimary = primary;
}
}
void
LogicalPartition::SetTo(off_t offset, off_t size, uint8 type, bool active,
off_t tableOffset, PrimaryPartition* primary)
{
Unset();
if (primary) {
Partition::SetTo(offset, size, type, active, tableOffset,
primary->BlockSize());
fPrimary = primary;
}
}
void
LogicalPartition::Unset()
{
fPrimary = NULL;
fNext = NULL;
fPrevious = NULL;
Partition::Unset();
}
void
LogicalPartition::GetPartitionDescriptor(partition_descriptor* descriptor,
bool inner) const
{
PrimaryPartition* primary = GetPrimaryPartition();
if (inner) {
descriptor->start = (PartitionTableOffset() - primary->Offset())
/ BlockSize();
descriptor->type = primary->Type();
} else {
descriptor->start = (Offset() - PartitionTableOffset()) / BlockSize();
descriptor->type = Type();
}
descriptor->size = Size() / BlockSize();
descriptor->active = 0x00;
descriptor->begin.SetUnused();
descriptor->end.SetUnused();
}
// #pragma mark - PartitionMap
PartitionMap::PartitionMap()
{
for (int32 i = 0; i < 4; i++)
fPrimaries[i].SetIndex(i);
}
PartitionMap::~PartitionMap()
{
}
void
PartitionMap::Unset()
{
for (int32 i = 0; i < 4; i++)
fPrimaries[i].Unset();
}
status_t
PartitionMap::Assign(const PartitionMap& other)
{
for (int32 i = 0; i < 4; i++) {
status_t error = fPrimaries[i].Assign(other.fPrimaries[i]);
if (error != B_OK)
return error;
}
return B_OK;
}
PrimaryPartition*
PartitionMap::PrimaryPartitionAt(int32 index)
{
PrimaryPartition* partition = NULL;
if (index >= 0 && index < 4)
partition = fPrimaries + index;
return partition;
}
const PrimaryPartition*
PartitionMap::PrimaryPartitionAt(int32 index) const
{
const PrimaryPartition* partition = NULL;
if (index >= 0 && index < 4)
partition = fPrimaries + index;
return partition;
}
int32
PartitionMap::CountNonEmptyPrimaryPartitions() const
{
int32 count = 0;
for (int32 i = 0; i < 4; i++) {
if (!fPrimaries[i].IsEmpty())
count++;
}
return count;
}
int32
PartitionMap::ExtendedPartitionIndex() const
{
for (int32 i = 0; i < 4; i++) {
if (fPrimaries[i].IsExtended())
return i;
}
return -1;
}
int32
PartitionMap::CountPartitions() const
{
int32 count = 4;
for (int32 i = 0; i < 4; i++)
count += fPrimaries[i].CountLogicalPartitions();
return count;
}
int32
PartitionMap::CountNonEmptyPartitions() const
{
int32 count = 0;
for (int32 i = CountPartitions() - 1; i >= 0; i--) {
if (!PartitionAt(i)->IsEmpty())
count++;
}
return count;
}
Partition*
PartitionMap::PartitionAt(int32 index)
{
Partition* partition = NULL;
int32 count = CountPartitions();
if (index >= 0 && index < count) {
if (index < 4)
partition = fPrimaries + index;
else {
index -= 4;
int32 primary = 0;
while (index >= fPrimaries[primary].CountLogicalPartitions()) {
index -= fPrimaries[primary].CountLogicalPartitions();
primary++;
}
partition = fPrimaries[primary].LogicalPartitionAt(index);
}
}
return partition;
}
const Partition*
PartitionMap::PartitionAt(int32 index) const
{
return const_cast<PartitionMap*>(this)->PartitionAt(index);
}
bool
PartitionMap::Check(off_t sessionSize) const
{
int32 partitionCount = CountPartitions();
// 1. check partition locations
for (int32 i = 0; i < partitionCount; i++) {
if (!PartitionAt(i)->CheckLocation(sessionSize))
return false;
}
// 2. check overlapping of partitions and location of partition tables
bool result = true;
Partition** byOffset = new(nothrow) Partition*[partitionCount];
off_t* tableOffsets = new(nothrow) off_t[partitionCount - 3];
if (byOffset && tableOffsets) {
// fill the arrays
int32 byOffsetCount = 0;
int32 tableOffsetCount = 1; // primary partition table
tableOffsets[0] = 0;
for (int32 i = 0; i < partitionCount; i++) {
Partition* partition = (Partition*)PartitionAt(i);
if (!partition->IsExtended())
byOffset[byOffsetCount++] = partition;
// add only logical partition partition table locations
if (i >= 4) {
tableOffsets[tableOffsetCount++]
= partition->PartitionTableOffset();
}
}
// sort the arrays
qsort(byOffset, byOffsetCount, sizeof(Partition*),
cmp_partition_offset);
qsort(tableOffsets, tableOffsetCount, sizeof(off_t), cmp_offset);
// check for overlappings
off_t nextOffset = 0;
for (int32 i = 0; i < byOffsetCount; i++) {
Partition* partition = byOffset[i];
if (partition->Offset() < nextOffset && i > 0) {
Partition* previousPartition = byOffset[i - 1];
off_t previousSize = previousPartition->Size()
- (nextOffset - partition->Offset());
TRACE(("intel: PartitionMap::Check(): "));
if (previousSize == 0) {
previousPartition->Unset();
TRACE(("partition offset hides previous partition."
" Removing previous partition from disk layout.\n"));
} else {
TRACE(("overlapping partitions! Setting partition %ld "
"size to %lld\n", i - 1, previousSize));
previousPartition->SetSize(previousSize);
}
}
nextOffset = partition->Offset() + partition->Size();
}
// check uniqueness of partition table offsets and whether they lie
// outside of the non-extended partitions
if (result) {
for (int32 i = 0; i < tableOffsetCount; i++) {
if (i > 0 && tableOffsets[i] == tableOffsets[i - 1]) {
TRACE(("intel: PartitionMap::Check(): same partition table "
"for different extended partitions!\n"));
result = false;
break;
} else if (is_inside_partitions(tableOffsets[i],
(const Partition**)byOffset, byOffsetCount)) {
TRACE(("intel: PartitionMap::Check(): a partition table "
"lies inside a non-extended partition!\n"));
result = false;
break;
}
}
}
} else
result = false; // no memory: assume failure
// cleanup
delete[] byOffset;
delete[] tableOffsets;
return result;
}
const partition_type*
PartitionMap::GetNextSupportedPartitionType(uint32 index)
{
if (index > (sizeof(kPartitionTypes) / sizeof(partition_type) - 2))
return NULL;
return kPartitionTypes + index;
}
↑ V730 Not all members of a class are initialized inside the constructor. Consider inspecting: fBlockSize.
↑ V730 Not all members of a class are initialized inside the constructor. Consider inspecting: fIndex.