Re: control of partition numbers

[Andrew Clausen]

On Tue, Dec 31, 2002 at 02:45:08PM -0500, D. Hugh Redelmeier wrote:
> | > Sometimes I wish to control the partition number of a partition that
> | > I've just created or modified.
> | 
> | It is rather difficult to implement this.
> 
> I would expect that exchanging two partition table entries would be
> quite easy.

It is up until you start implementing it :(

> |  There are some combinations
> | that are illegal.
> 
> Yes: exchanging a logical and primary partition table entry isn't
> possible.  For one thing, the space for a primary partition must not
> be inside an extended partition but the space for a logical partition
> must be inside the extended partition.

Also, you can't have "holes".  Like, you can't renumber 5 to 10
if there's no 9.

Also, there are some cases where you can't renumber 5 at all,
or possibly only swap 5 with 6, or some other number.

It's totally counter-intuitive.

> |  Also, remember that Parted supports many different
> | types of partition tables.
> 
> Good point.  Unfortunately, I don't know enough about other types of
> partition tables to speak to this.  Perhaps you could describe the
> constraints on exchanges for these other types.

Msdos's layout is the only really insane one.

> Whenever a logical partition is deleted, all later ones get
> renumbered.  Whenever a logical partition is added, it becomes last.
> So if you delete and recreate a partition, it and all higher-numbered
> ones are renumbered -- often inconvenient.

This is because you can't have "holes"

> How could parted address these problems?
> 
> - Perhaps when the user asks to create a partition, he could specify
>   its number.  If the number were in the extended partition, all
>   partitions with that number or higher would have their number
>   incremented.  If the number were of an existing primary partition,
>   parted should refuse.
> 
>   This solves the delete/recreate problem, but leaves other imaginable
>   ones.  For example, if he created a partition with the wrong number,
>   he could not fix up the mistake without deleting a partition and
>   recreating it.

Also, it complicates the UI somewhat.  Should partition numbers
be optional?  Should parted infer primary vs logical via the
partition number, or ask that also?

> How doe you specify a permutation of partitions?
> 
> There are many notations used by mathematicians.  For example:
> 
>       / 1 2 3 \
>       \ 3 1 2 /
> (I think parentheses are normally used, but ASCII doesn't have
> double-height ones.)  This means that what was 1 becomes 3 and what
> was 2 becomes 1 and what was 3 becomes 2.

Yep, I'm familiar with permutation groups and this notation.
It is equivalent to your rotate notation.  You would write the
above as:

        (1 3 2)

(1 goes to 3, 3 goes to 2, 2 goes to 1, and everything else stays
the same)

Another example:

        / 1 2 3 4 \
        \ 3 4 1 2 /

Is equivalent to (1 3)(2 4)


> The tr(1) command suggests a notation for a permutation (but it does
> not restrict itself to permutations).  How about a parted command:
> 
>       renumber 1 2 3 to 3 1 2

Ah, good idea! :)

> This has more syntax than most parted commands.
> 
> It turns out that any permutation can be expressed as a sequence of
> exchanges (the exchanges may overlap).

But, you don't want to refer users to maths textbooks so they can
use Parted!

> Here is one sequence that has
> the same effect as the above:
> 
>       exchange 1 3
>       exchange 2 3
> 
> The good thing is that this has trivial syntax.  The syntax and
> semantics are minimal in some sense.

That said, "exchange" is just a special case of "renumber".
I'm leaning towards renumber.

> The bad thing is that it may not be easy for a user to think of the
> right sequence of exchanges to accomplish what he wants.

Exactly.

> A slightly more powerful command would allow a rotation of a number of
> partitions:
>       rotate-right  1 2 3
>       rotate-left   3 2 1
> 
> As you can see, rotate-left and rotate-right can accomplish the same
> things.  An exchange is the same as a rotation of just two partitions.

I think this notation is a bit more confusing for users, although
it is a good internal representation.  (It's the one mathematicians
like :)

> If I remember correctly, any permutation can be partitioned into a set
> of rotates.  I use the word "partitioned" because the rotations are
> not overlapping: they can be performed in any order (that is also why
> I called them a set, rather than a sequence).  This makes rotation
> slightly nicer than exchange.

This is correct.

> My recommendation: implement exchange.  It is minimal and yet can
> accomplish anything that the others can do.  Although it is slightly
> awkward for the user, we don't yet know how often this facility would
> be used.

I reckon the tr(1) notation is intuitive, and can be used like exchange
if users are scared, so it's a better solution.

> Note that for primary partitions, full power requires that unused
> partitions table entries be candidates for exchange.  This reflects
> what the underlying partition table allows.  It also enables all
> possible control of minor device numbers.  There is no concept of an
> unused partition table entry for logical partitions, as far as I
> know.

Correct.  This complicates the problem a bit :/

[group theory hat on]

I guess all existing partitions, and "free space slot" partitions
are elements of a set, and the permutations themselves are
form a group action on the set, with composition being the group
operation.

So, above, I mentioned, for example, that you might not be able
to renumber 5 to anything other than 6.

How could this constraint be expressed?

The obvious (but impractical) method is: a constraint is a set
of solutions.  Therefore, a constraint is just a set (say, a list)
of permutations.  You can find intersection the obvious way, etc.

I can't think of a better representation.  Unfortunately such
subsets of the permutation group aren't subgroups of the
original group.

        Counterexample:
        If P is a group of all permutations on {1, 2, 3, 4}, and S
        is the set of all permutations, except those that permute 1
        to anything other than 1 or 2, then S isn't a subgroup of P.

        Proof: the order of P, |P| = 4! = 24.
        S contains the elements { (1), (2 3), (3 4), (2 4), (2 3 4),
        (1 2), (1 2) (3 4) }
        |S| = 7, so |S| = 7 doesn't divide |P| = 24, and therefore
        S isn't a subgroup of P.

        [Alternative proof: Composing these two elements of S:
        (1 2) (3 4) with (2 3) gives you (1 3 4 2), which isn't a member
        of S, so S isn't closed under the group operation]

This fact seems to make it hard to represent permutation constraints.
No fancy tricks like representing constraints as permutations and
finding some intersection operator are going to work.
The obvious list of all possibilities isn't doable, because it could
have size of n!, where n is the number of partition slots.  Say, if
you have 15 partitions:

        15! = 1307674368000

This is more RAM than I have :/

Maybe a list of ad-hoc functions would suffice?  (yuck!)

Other than that, you can have the partition table type specific
code accept/reject permutations.  But this is bad for making good
UI's.

> There are some other tasks that can be accomplished simply by changing
> partition table entries, but not via permutation.  The constraints on
> applicability make them less elegant.

These all look like some kind of import/export logical partition
command, in combination with renumber.

Thanks for the interesting email :)  This is the second time group
theory has come in handy with Parted... pretty funny really :)

Andrew