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
46using std::nothrow;
47
48
49static const char* const kUnrecognizedTypeString = "Unrecognized Type ";
50static const size_t kUnrecognizedTypeStringLength = 18;
51
52static 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
148static 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
166static const char*
167partition_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
178void
179get_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
190static int
191cmp_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
205static int
206cmp_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
220static bool
221is_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
247PartitionType::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*/
258bool
259PartitionType::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*/
270bool
271PartitionType::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*/
300bool
301PartitionType::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*/
317bool
318PartitionType::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
358Partition::Partition()
359	:
360	fPartitionTableOffset(0),
361	fOffset(0),
362	fSize(0),
363	fType(0),
364	fActive(false)
365{
366}
367
368
369Partition::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
382void
383Partition::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
393void
394Partition::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
409void
410Partition::Unset()
411{
412	fPartitionTableOffset = 0;
413	fOffset = 0;
414	fSize = 0;
415	fType = 0;
416	fActive = false;
417}
418
419
420bool
421Partition::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
463bool
464Partition::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
484PrimaryPartition::PrimaryPartition()
485	:
486	Partition(),
487	fHead(NULL),
488	fTail(NULL),
489	fLogicalPartitionCount(0)
490{
491}
492
493
494void
495PrimaryPartition::SetTo(const partition_descriptor* descriptor,
496	off_t tableOffset, uint32 blockSize)
497{
498	Unset();
499	Partition::SetTo(descriptor, tableOffset, 0, blockSize);
500}
501
502
503void
504PrimaryPartition::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
512void
513PrimaryPartition::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
526status_t
527PrimaryPartition::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
552void
553PrimaryPartition::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.SetUnused();
563		descriptor->end.SetUnused();
564	}
565}
566
567
568LogicalPartition*
569PrimaryPartition::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
580void
581PrimaryPartition::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
600void
601PrimaryPartition::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
629LogicalPartition::LogicalPartition()
630	:
631	Partition(),
632	fPrimary(NULL),
633	fNext(NULL),
634	fPrevious(NULL)
635{
636}
637
638
639LogicalPartition::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
651void
652LogicalPartition::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
677void
678LogicalPartition::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
690void
691LogicalPartition::Unset()
692{
693	fPrimary = NULL;
694	fNext = NULL;
695	fPrevious = NULL;
696	Partition::Unset();
697}
698
699
700void
701LogicalPartition::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.SetUnused();
717	descriptor->end.SetUnused();
718}
719
720
721//	#pragma mark - PartitionMap
722
723
724PartitionMap::PartitionMap()
725{
726	for (int32 i = 0; i < 4; i++)
727		fPrimaries[i].SetIndex(i);
728}
729
730
731PartitionMap::~PartitionMap()
732{
733}
734
735
736void
737PartitionMap::Unset()
738{
739	for (int32 i = 0; i < 4; i++)
740		fPrimaries[i].Unset();
741}
742
743
744status_t
745PartitionMap::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
757PrimaryPartition*
758PartitionMap::PrimaryPartitionAt(int32 index)
759{
760	PrimaryPartition* partition = NULL;
761	if (index >= 0 && index < 4)
762		partition = fPrimaries + index;
763	return partition;
764}
765
766
767const PrimaryPartition*
768PartitionMap::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
777int32
778PartitionMap::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
790int32
791PartitionMap::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
802int32
803PartitionMap::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
812int32
813PartitionMap::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
825Partition*
826PartitionMap::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
847const Partition*
848PartitionMap::PartitionAt(int32 index) const
849{
850	return const_cast<PartitionMap*>(this)->PartitionAt(index);
851}
852
853
854bool
855PartitionMap::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
942const partition_type*
943PartitionMap::GetNextSupportedPartitionType(uint32 index)
944{
945	if (index > (sizeof(kPartitionTypes) / sizeof(partition_type) - 2))
946		return NULL;
947
948	return kPartitionTypes + index;
949}
950