1 /*
2 SPDX-FileCopyrightText: 2008-2012 Volker Lanz <vl@fidra.de>
3 SPDX-FileCopyrightText: 2009 Andrew Coles <andrew.i.coles@googlemail.com>
4 SPDX-FileCopyrightText: 2013-2020 Andrius Štikonas <andrius@stikonas.eu>
5 SPDX-FileCopyrightText: 2015-2016 Teo Mrnjavac <teo@kde.org>
6 SPDX-FileCopyrightText: 2016 Chantara Tith <tith.chantara@gmail.com>
7 SPDX-FileCopyrightText: 2018 Caio Jordão Carvalho <caiojcarvalho@gmail.com>
8
9 SPDX-License-Identifier: GPL-3.0-or-later
10 */
11
12 /** @file
13 */
14
15 #include "core/partitiontable.h"
16 #include "core/partition.h"
17 #include "core/device.h"
18 #include "core/diskdevice.h"
19 #include "core/lvmdevice.h"
20 #include "core/partitionalignment.h"
21 #include "fs/filesystem.h"
22 #include "fs/filesystemfactory.h"
23
24 #include "util/globallog.h"
25
26 #include <utility>
27
28 #include <KLocalizedString>
29
30 #include <QDebug>
31 #include <QTextStream>
32
33 /** Creates a new PartitionTable object with type MSDOS
34 @param type name of the PartitionTable type (e.g. "msdos" or "gpt")
35 */
PartitionTable(TableType type,qint64 firstUsable,qint64 lastUsable)36 PartitionTable::PartitionTable(TableType type, qint64 firstUsable, qint64 lastUsable)
37 : PartitionNode()
38 , m_Children()
39 , m_MaxPrimaries(maxPrimariesForTableType(type))
40 , m_Type(type)
41 , m_FirstUsable(firstUsable)
42 , m_LastUsable(lastUsable)
43 {
44 }
45
46 /** Copy constructor for PartitionTable.
47 * @param other the other PartitionTable.
48 */
PartitionTable(const PartitionTable & other)49 PartitionTable::PartitionTable(const PartitionTable& other)
50 : PartitionNode()
51 , m_Children()
52 , m_MaxPrimaries(other.m_MaxPrimaries)
53 , m_Type(other.m_Type)
54 , m_FirstUsable(other.m_FirstUsable)
55 , m_LastUsable(other.m_LastUsable)
56 {
57 for (Partitions::const_iterator it = other.m_Children.constBegin();
58 it != other.m_Children.constEnd(); ++it)
59 {
60 m_Children.append(new Partition(**it, this));
61 }
62 }
63
64 /** Destroys a PartitionTable object, destroying all children */
~PartitionTable()65 PartitionTable::~PartitionTable()
66 {
67 clearChildren();
68 }
69
70 /** Gets the number of free sectors before a given child Partition in this PartitionTable.
71
72 @param p the Partition for which to get the free sectors before
73 @returns the number of free sectors before the Partition
74 */
freeSectorsBefore(const Partition & p) const75 qint64 PartitionTable::freeSectorsBefore(const Partition& p) const
76 {
77 const Partition* pred = predecessor(p);
78
79 // due to the space required for extended boot records the
80 // below is NOT the same as pred->length()
81 if (pred && pred->roles().has(PartitionRole::Unallocated))
82 return p.firstSector() - pred->firstSector();
83
84 return 0;
85 }
86
87 /** Gets the number of free sectors after a given child Partition in this PartitionTable.
88
89 @param p the Partition for which to get the free sectors after
90 @returns the number of free sectors after the Partition
91 */
freeSectorsAfter(const Partition & p) const92 qint64 PartitionTable::freeSectorsAfter(const Partition& p) const
93 {
94 const Partition* succ = successor(p);
95
96 // due to the space required for extended boot records the
97 // below is NOT the same as succ->length()
98 if (succ && succ->roles().has(PartitionRole::Unallocated))
99 return succ->lastSector() - p.lastSector();
100
101 return 0;
102 }
103
freeSectors() const104 qint64 PartitionTable::freeSectors() const
105 {
106 qint64 sectors = 0;
107 for (const auto &p : children()) {
108 if (p->roles().has(PartitionRole::Unallocated)) {
109 sectors += p->length();
110 }
111 }
112
113 return sectors;
114 }
115
116 /** @return true if the PartitionTable has an extended Partition */
hasExtended() const117 bool PartitionTable::hasExtended() const
118 {
119 for (const auto &p : children())
120 if (p->roles().has(PartitionRole::Extended))
121 return true;
122
123 return false;
124 }
125
126 /** @return pointer to the PartitionTable's extended Partition or nullptr if none exists */
extended() const127 Partition* PartitionTable::extended() const
128 {
129 for (const auto &p : children())
130 if (p->roles().has(PartitionRole::Extended))
131 return p;
132
133 return nullptr;
134 }
135
136 /** Gets valid PartitionRoles for a Partition
137 @param p the Partition
138 @return valid roles for the given Partition
139 */
childRoles(const Partition & p) const140 PartitionRole::Roles PartitionTable::childRoles(const Partition& p) const
141 {
142 Q_ASSERT(p.parent());
143
144 PartitionRole::Roles r = p.parent()->isRoot() ? PartitionRole::Primary : PartitionRole::Logical;
145
146 if (r == PartitionRole::Primary && hasExtended() == false && tableTypeSupportsExtended(type()))
147 r |= PartitionRole::Extended;
148
149 return r;
150 }
151
152 /** @return the number of primaries in this PartitionTable */
numPrimaries() const153 int PartitionTable::numPrimaries() const
154 {
155 int result = 0;
156
157 for (const auto &p : children())
158 if (p->roles().has(PartitionRole::Primary) || p->roles().has(PartitionRole::Extended))
159 result++;
160
161 return result;
162 }
163
164 /** Appends a Partition to this PartitionTable
165 @param partition pointer of the partition to append. Must not be nullptr.
166 */
append(Partition * partition)167 void PartitionTable::append(Partition* partition)
168 {
169 children().append(partition);
170 std::sort(children().begin(), children().end(), [] (const Partition *a, const Partition *b) -> bool {return a->firstSector() < b->firstSector();});
171 }
172
173 /** @param f the flag to get the name for
174 @returns the flags name or an empty QString if the flag is not known
175 */
flagName(Flag f)176 QString PartitionTable::flagName(Flag f)
177 {
178 switch (f) {
179 case PartitionTable::Flag::Boot:
180 return xi18nc("@item partition flag", "boot");
181 case PartitionTable::Flag::Root:
182 return xi18nc("@item partition flag", "root");
183 case PartitionTable::Flag::Swap:
184 return xi18nc("@item partition flag", "swap");
185 case PartitionTable::Flag::Hidden:
186 return xi18nc("@item partition flag", "hidden");
187 case PartitionTable::Flag::Raid:
188 return xi18nc("@item partition flag", "raid");
189 case PartitionTable::Flag::Lvm:
190 return xi18nc("@item partition flag", "lvm");
191 case PartitionTable::Flag::Lba:
192 return xi18nc("@item partition flag", "lba");
193 case PartitionTable::Flag::HpService:
194 return xi18nc("@item partition flag", "hpservice");
195 case PartitionTable::Flag::Palo:
196 return xi18nc("@item partition flag", "palo");
197 case PartitionTable::Flag::Prep:
198 return xi18nc("@item partition flag", "prep");
199 case PartitionTable::Flag::MsftReserved:
200 return xi18nc("@item partition flag", "msft-reserved");
201 case PartitionTable::Flag::BiosGrub:
202 return xi18nc("@item partition flag", "bios-grub");
203 case PartitionTable::Flag::AppleTvRecovery:
204 return xi18nc("@item partition flag", "apple-tv-recovery");
205 case PartitionTable::Flag::Diag:
206 return xi18nc("@item partition flag", "diag");
207 case PartitionTable::Flag::LegacyBoot:
208 return xi18nc("@item partition flag", "legacy-boot");
209 case PartitionTable::Flag::MsftData:
210 return xi18nc("@item partition flag", "msft-data");
211 case PartitionTable::Flag::Irst:
212 return xi18nc("@item partition flag", "irst");
213 default:
214 break;
215 }
216
217 return QString();
218 }
219
220 /** @return list of all flags */
flagList()221 const QList<PartitionTable::Flag> PartitionTable::flagList()
222 {
223 QList<PartitionTable::Flag> rval;
224
225 rval.append(PartitionTable::Flag::Boot);
226 rval.append(PartitionTable::Flag::Root);
227 rval.append(PartitionTable::Flag::Swap);
228 rval.append(PartitionTable::Flag::Hidden);
229 rval.append(PartitionTable::Flag::Raid);
230 rval.append(PartitionTable::Flag::Lvm);
231 rval.append(PartitionTable::Flag::Lba);
232 rval.append(PartitionTable::Flag::HpService);
233 rval.append(PartitionTable::Flag::Palo);
234 rval.append(PartitionTable::Flag::Prep);
235 rval.append(PartitionTable::Flag::MsftReserved);
236 rval.append(PartitionTable::Flag::BiosGrub);
237 rval.append(PartitionTable::Flag::AppleTvRecovery);
238 rval.append(PartitionTable::Flag::Diag);
239 rval.append(PartitionTable::Flag::LegacyBoot);
240 rval.append(PartitionTable::Flag::MsftData);
241 rval.append(PartitionTable::Flag::Irst);
242
243 return rval;
244 }
245
246 /** @param flags the flags to get the names for
247 @returns QStringList of the flags' names
248 */
flagNames(Flags flags)249 QStringList PartitionTable::flagNames(Flags flags)
250 {
251 QStringList rval;
252
253 int f = 1;
254
255 QString s;
256 while (!(s = flagName(static_cast<PartitionTable::Flag>(f))).isEmpty()) {
257 if (flags & f)
258 rval.append(s);
259
260 f <<= 1;
261 }
262
263 return rval;
264 }
265
266 /** @param list QStringList of the flags' names
267 @returns flags corresponding to names
268 */
flagsFromList(const QStringList list)269 PartitionTable::Flags PartitionTable::flagsFromList(const QStringList list)
270 {
271 Flags flags;
272
273 for (const auto &flag : flagList())
274 if (list.contains(flagName(flag)))
275 flags.setFlag(flag);
276
277 return flags;
278 }
279
getUnallocatedRange(const Device & d,PartitionNode & parent,qint64 & start,qint64 & end)280 bool PartitionTable::getUnallocatedRange(const Device& d, PartitionNode& parent, qint64& start, qint64& end)
281 {
282 if (d.type() == Device::Type::Disk_Device) {
283 const DiskDevice& device = dynamic_cast<const DiskDevice&>(d);
284 if (!parent.isRoot()) {
285 Partition* extended = dynamic_cast<Partition*>(&parent);
286
287 if (extended == nullptr) {
288 qWarning() << "extended is null. start: " << start << ", end: " << end << ", device: " << device.deviceNode();
289 return false;
290 }
291
292 // Leave a track (cylinder aligned) or sector alignment sectors (sector based) free at the
293 // start for a new partition's metadata
294 start += device.partitionTable()->type() == PartitionTable::msdos ? device.sectorsPerTrack() : PartitionAlignment::sectorAlignment(device);
295
296 // .. and also at the end for the metadata for a partition to follow us, if we're not
297 // at the end of the extended partition
298 if (end < extended->lastSector())
299 end -= device.partitionTable()->type() == PartitionTable::msdos ? device.sectorsPerTrack() : PartitionAlignment::sectorAlignment(device);
300 }
301
302 return end - start + 1 >= PartitionAlignment::sectorAlignment(device);
303 } else if (d.type() == Device::Type::LVM_Device || d.type() == Device::Type::SoftwareRAID_Device) {
304 if (end - start + 1 > 0) {
305 return true;
306 }
307 }
308 return false;
309 }
310
311
312 /** Creates a new unallocated Partition on the given Device.
313 @param device the Device to create the new Partition on
314 @param parent the parent PartitionNode for the new Partition
315 @param start the new Partition's start sector
316 @param end the new Partition's end sector
317 @return pointer to the newly created Partition object or nullptr if the Partition could not be created
318 */
createUnallocated(const Device & device,PartitionNode & parent,qint64 start,qint64 end)319 Partition* createUnallocated(const Device& device, PartitionNode& parent, qint64 start, qint64 end)
320 {
321 PartitionRole::Roles r = PartitionRole::Unallocated;
322
323 if (!parent.isRoot())
324 r |= PartitionRole::Logical;
325
326 // Mark unallocated space in LVM VG as LVM LV so that pasting can be easily disabled (it does not work yet)
327 if (device.type() == Device::Type::LVM_Device)
328 r |= PartitionRole::Lvm_Lv;
329
330 if (!PartitionTable::getUnallocatedRange(device, parent, start, end))
331 return nullptr;
332
333 return new Partition(&parent, device, PartitionRole(r), FileSystemFactory::create(FileSystem::Type::Unknown, start, end, device.logicalSize()), start, end, QString());
334 }
335
336 /** Removes all unallocated children from a PartitionNode
337 @param p pointer to the parent to remove unallocated children from
338 */
removeUnallocated(PartitionNode * p)339 void PartitionTable::removeUnallocated(PartitionNode* p)
340 {
341 Q_ASSERT(p);
342
343 qint32 i = 0;
344
345 while (i < p->children().size()) {
346 Partition* child = p->children()[i];
347
348 if (child->roles().has(PartitionRole::Unallocated)) {
349 p->remove(child);
350 delete child;
351 continue;
352 }
353
354 if (child->roles().has(PartitionRole::Extended))
355 removeUnallocated(child);
356
357 i++;
358 }
359 }
360
361 /**
362 @overload
363 */
removeUnallocated()364 void PartitionTable::removeUnallocated()
365 {
366 removeUnallocated(this);
367 }
368
369 /** Inserts unallocated children for a Device's PartitionTable with the given parent.
370
371 This method inserts unallocated Partitions for a parent, usually the Device this
372 PartitionTable is on. It will also insert unallocated Partitions in any extended
373 Partitions it finds.
374
375 @warning This method assumes that no unallocated Partitions exist when it is called.
376
377 @param d the Device this PartitionTable and @p p are on
378 @param p the parent PartitionNode (may be this or an extended Partition)
379 @param start the first sector to begin looking for free space
380 */
insertUnallocated(const Device & d,PartitionNode * p,qint64 start)381 void PartitionTable::insertUnallocated(const Device& d, PartitionNode* p, qint64 start)
382 {
383 Q_ASSERT(p);
384
385 qint64 lastEnd = start;
386
387 if (d.type() == Device::Type::LVM_Device && !p->children().isEmpty()) {
388 // rearranging the sectors of all partitions to keep unallocated space at the end
389 lastEnd = 0;
390 std::sort(children().begin(), children().end(), [](const Partition* p1, const Partition* p2) { return p1->deviceNode() < p2->deviceNode(); });
391 for (const auto &child : children()) {
392 qint64 totalSectors = child->length();
393 child->setFirstSector(lastEnd);
394 child->setLastSector(lastEnd + totalSectors - 1);
395
396 lastEnd += totalSectors;
397 }
398 } else {
399 const auto pChildren = p->children();
400 for (const auto &child : pChildren) {
401 p->insert(createUnallocated(d, *p, lastEnd, child->firstSector() - 1));
402
403 if (child->roles().has(PartitionRole::Extended))
404 insertUnallocated(d, child, child->firstSector());
405
406 lastEnd = child->lastSector() + 1;
407 }
408 }
409
410 if (d.type() == Device::Type::LVM_Device)
411 {
412 const LvmDevice& lvm = static_cast<const LvmDevice&>(d);
413 p->insert(createUnallocated(d, *p, lastEnd, lastEnd + lvm.freePE() - 1));
414 }
415 else
416 {
417 // Take care of the free space between the end of the last child and the end
418 // of the device or the extended partition.
419 qint64 parentEnd = lastUsable();
420
421 if (!p->isRoot()) {
422 Partition* extended = dynamic_cast<Partition*>(p);
423 parentEnd = extended ? extended->lastSector() : -1;
424 Q_ASSERT(extended);
425 }
426
427 if (parentEnd >= firstUsable() && parentEnd >= lastEnd)
428 p->insert(createUnallocated(d, *p, lastEnd, parentEnd));
429 }
430 }
431
432 /** Updates the unallocated Partitions for this PartitionTable.
433 @param d the Device this PartitionTable is on
434 */
updateUnallocated(const Device & d)435 void PartitionTable::updateUnallocated(const Device& d)
436 {
437 removeUnallocated();
438 insertUnallocated(d, this, firstUsable());
439 }
440
defaultFirstUsable(const Device & d,TableType t)441 qint64 PartitionTable::defaultFirstUsable(const Device& d, TableType t)
442 {
443 Q_UNUSED(t)
444 if (d.type() == Device::Type::LVM_Device || d.type() == Device::Type::SoftwareRAID_Device || t == PartitionTable::TableType::none) {
445 return 0;
446 }
447
448 const DiskDevice& diskDevice = dynamic_cast<const DiskDevice&>(d);
449 return PartitionAlignment::sectorAlignment(diskDevice);
450 }
451
defaultLastUsable(const Device & d,TableType t)452 qint64 PartitionTable::defaultLastUsable(const Device& d, TableType t)
453 {
454 if (t == gpt)
455 return d.totalLogical() - 1 - 32 - 1;
456
457 return d.totalLogical() - 1;
458 }
459
460 static struct {
461 const QLatin1String name; /**< name of partition table type */
462 quint32 maxPrimaries; /**< max numbers of primary partitions supported */
463 bool canHaveExtended; /**< does partition table type support extended partitions */
464 bool isReadOnly; /**< does KDE Partition Manager support this only in read only mode */
465 PartitionTable::TableType type; /**< enum type */
466 } tableTypes[] = {
467 { QLatin1String("aix"), 4, false, true, PartitionTable::TableType::aix },
468 { QLatin1String("bsd"), 8, false, true, PartitionTable::TableType::bsd },
469 { QLatin1String("dasd"), 1, false, true, PartitionTable::TableType::dasd },
470 { QLatin1String("msdos"), 4, true, false, PartitionTable::TableType::msdos },
471 { QLatin1String("msdos"), 4, true, false, PartitionTable::TableType::msdos_sectorbased },
472 { QLatin1String("dos"), 4, true, false, PartitionTable::TableType::msdos_sectorbased },
473 { QLatin1String("dvh"), 16, true, true, PartitionTable::TableType::dvh },
474 { QLatin1String("gpt"), 128, false, false, PartitionTable::TableType::gpt },
475 { QLatin1String("loop"), 1, false, true, PartitionTable::TableType::loop },
476 { QLatin1String("mac"), 0xffff, false, true, PartitionTable::TableType::mac },
477 { QLatin1String("pc98"), 16, false, true, PartitionTable::TableType::pc98 },
478 { QLatin1String("amiga"), 128, false, true, PartitionTable::TableType::amiga },
479 { QLatin1String("sun"), 8, false, true, PartitionTable::TableType::sun },
480 { QLatin1String("vmd"), 0xffff, false, false, PartitionTable::TableType::vmd },
481 { QLatin1String("none"), 1, false, false, PartitionTable::TableType::none },
482 };
483
nameToTableType(const QString & n)484 PartitionTable::TableType PartitionTable::nameToTableType(const QString& n)
485 {
486 for (const auto &type : tableTypes)
487 if (n == type.name)
488 return type.type;
489
490 return PartitionTable::TableType::unknownTableType;
491 }
492
tableTypeToName(TableType l)493 QString PartitionTable::tableTypeToName(TableType l)
494 {
495 for (const auto &type : tableTypes)
496 if (l == type.type)
497 return type.name;
498
499 return xi18nc("@item partition table name", "unknown");
500 }
501
maxPrimariesForTableType(TableType l)502 qint32 PartitionTable::maxPrimariesForTableType(TableType l)
503 {
504 for (const auto &type : tableTypes)
505 if (l == type.type)
506 return type.maxPrimaries;
507
508 return 1;
509 }
510
tableTypeSupportsExtended(TableType l)511 bool PartitionTable::tableTypeSupportsExtended(TableType l)
512 {
513 for (const auto &type : tableTypes)
514 if (l == type.type)
515 return type.canHaveExtended;
516
517 return false;
518 }
519
tableTypeIsReadOnly(TableType l)520 bool PartitionTable::tableTypeIsReadOnly(TableType l)
521 {
522 for (const auto &type : tableTypes)
523 if (l == type.type)
524 return type.isReadOnly;
525
526 return false;
527 }
528
529 /** Simple heuristic to determine if the PartitionTable is sector aligned (i.e.
530 if its Partitions begin at sectors evenly divisable by PartitionAlignment::sectorAlignment().
531 @return true if is sector aligned, otherwise false
532 */
isSectorBased(const Device & d) const533 bool PartitionTable::isSectorBased(const Device& d) const
534 {
535 if (d.type() == Device::Type::Disk_Device) {
536 const DiskDevice& diskDevice = dynamic_cast<const DiskDevice&>(d);
537
538 if (type() == PartitionTable::msdos) {
539 // the default for empty partition tables is sector based
540 if (numPrimaries() == 0)
541 return true;
542
543 quint32 numCylinderAligned = 0;
544 quint32 numSectorAligned = 0;
545
546 // see if we have more cylinder aligned partitions than sector
547 // aligned ones.
548 for (const auto &p : children()) {
549 if (p->firstSector() % PartitionAlignment::sectorAlignment(diskDevice) == 0)
550 numSectorAligned++;
551 else if (p->firstSector() % diskDevice.cylinderSize() == 0)
552 numCylinderAligned++;
553 }
554
555 return numSectorAligned >= numCylinderAligned;
556 }
557 return type() == PartitionTable::msdos_sectorbased;
558 }
559
560 return false;
561 }
562
setType(const Device & d,TableType t)563 void PartitionTable::setType(const Device& d, TableType t)
564 {
565 setFirstUsableSector(defaultFirstUsable(d, t));
566 setLastUsableSector(defaultLastUsable(d, t));
567
568 m_Type = t;
569
570 updateUnallocated(d);
571 }
572
operator <<(QTextStream & stream,const PartitionTable & ptable)573 QTextStream& operator<<(QTextStream& stream, const PartitionTable& ptable)
574 {
575 stream << "type: \"" << ptable.typeName() << "\"\n"
576 << "align: \"" << (ptable.type() == PartitionTable::msdos ? "cylinder" : "sector") << "\"\n"
577 << "\n# number start end type roles label flags\n";
578
579 QList<const Partition*> partitions;
580
581 for (const auto &p : ptable.children()) {
582 if (!p->roles().has(PartitionRole::Unallocated)) {
583 partitions.append(p);
584
585 if (p->roles().has(PartitionRole::Extended)) {
586 const auto partChildren = p->children();
587 for (const auto &child : partChildren) {
588 if (!child->roles().has(PartitionRole::Unallocated))
589 partitions.append(child);
590 }
591 }
592 }
593 }
594
595 std::sort(partitions.begin(), partitions.end(), [](const Partition* p1, const Partition* p2) { return p1->number() < p2->number(); });
596
597 for (const auto &p : std::as_const(partitions))
598 stream << *p;
599
600 return stream;
601 }
602