RFC: Package Management System

A package management system is a program that manages archives of software to be automatically installed on your system. PMSes automate installation and deinstallation, and often also support automatic downloading of dependencies, listing of software from repositories, and in some cases compiling software for you.

PMSes are most commonly found in free and open source UNIX-like operating systems, such as the various GNU/Linux distributions and free BSDs. There are also a few for Mac OS X, but very few, if any, can be found for Windows.

I will not be going too far into the details of package management in this article, because that is not its point. This article is about a package manager that I am developing. Code name (and possibly normal name in the future): CANDY.

For more information on PMSes, please visit Wikipedia.

I am developing a package management systems inspired by the Slackware and MacPorts package management systems. It will be able to install two types of packages: Source and Binary packages (as with the RPM Package Manager). Source packages will function similarly to MacPorts Portfiles and RPM Specfiles. They will contain instructions on fetching, verifying, extracting, installing, and then later uninstalling software.

Source Package Format #1

Each package will get its own directory. In this directory, there will be a series of files:

• static.yml: This file will contain static (non-scripted) information about the package, such as metadata (title, description, etc.) and dependencies.
  
• features.lst: (Produced by Candy, deleted if --dont-save-features is specified.) See below: Compile-Time Features.
  
• fetch.sh: This file is a Bourne Shell script that will download and verify (via WHIRLPOOL, SHA512, and RMD160 checksums) the source code. This script should not re-download archives unless the checksums do not match. If the downloaded archive still does not match, then it should exit with code 1.
• build.sh: This file will compile and install the files. It will compile the files to install to locations that are specified by Candy's configuration file, but will actually install the files into a temporary directory via a DESTROOT (i.e. make install DESTROOT=/tmp/blah).
• preinstall.sh: (Optional) this file will be executed before files are installed into the root directory.
• postinstall.sh: (Optional) this file will be executed after files are installed into the root directory.
• predeinstall.sh: (Optional) this file will be executed before files are uninstalled.
• postdeinstall.sh: (Optional) this file will be executed after files are uninstalled.
• patches/*.patch: (Optional) patch files to be applied to the source archive post-extraction.
• source/: Unextracted sources. This will be produced by fetch.sh. This directory will be deletable with the clean command.
• source-archive.*: May be an archive or a directory checked out with a version control system. If it was a VCS checkout, source/ will be a symbolic link, and the directory should have the .vcs extension. This will be produced by fetch.sh.

During any form of build procedure, build.sh will be called. However, there are two things that may happen after build.sh executes, depending on the command specified to Candy. The two commands are:

• install: This command will run preinstall.sh, move the files into the root directory, and then run postinstall.sh. The predeinstall.sh and postdeinstall.sh files will be saved for whenever the program gets deinstalled.
• build-binary: This command will create an archive from the temporary files which will also include the pre- and post-scripts. This package is faster to install, does not require any development utilities in most cases, but is not configurable and less portable.

Source Package Format #2

Another format that will be supported is an archive that contains the files static.yml, build.sh, preinstall.sh, postinstall.sh, predeinstall.sh, and postdeinstall.sh (all files but fetch.sh and features.lst). Along with these files will be the downloaded source files. This is more similar to RPM, while the previous format is more similar to MacPorts.

Binary Package Format

Yet another format that will be supported is an archive that contains the files static.yml, features.lst, preinstall.sh, postinstall.sh, predeinstall.sh, and postdeinstall.sh (all files but fetch.sh and build.sh). It will also contain the built program binaries (produced by build.sh) which will be extracted into the root directory.

Compile-Time Features

Like MacPorts and Portage, Candy will support Compile-Time Features (in Portage talk, USE flags). They can be enabled with -f and disabled with -F, and all features are enabled by default. static.yml will contain summaries/descriptions of these features, and information about which features are enabled/disabled will be saved in features.lst. The various scripts will use features.lst, a list of enabled features separated by newlines, to determine which features to include.

Initially, I was planning to have static.yml truncated in Binary Package Format, but I decided that it was useful for users to have information about which features were enabled/disabled by the binary package author.

Dialogs

Packages will be passed the variable $DIALOG, which will evaluate to a program compatible with dialog which will vary between the original program or a graphical replica.

Amendment 1: File Selection and Multi-Package Output

This is an amendment to the previous section. It was added after the original article was written but before the article was published. I found that it would cause inconsistencies in the article to edit this in, so I decided to add it in this section. Further amendments will be posted in separate posts and linked to from here.

In the original design specified in this document, all of the files installed into a temporary directory are installed or archived in Source Package Format #2 or Binary Package Format. This amendment changes this: static.yml will contain globs (a.k.a. wildcards) specifying which files in the temporary directory are to be installed or archived (where /**/* would specify all files recursively). All files are excluded by default, since certain files such as the GNU Info dir file should be excluded.

Furthermore, the globs may be specified to specific Binary Packages, meaning that although both Source Packages will see them all as one tree, multiple Binary Packages may be generated. By standard, architecture-specific files, non-architecture-specific files, documentation, and development files (headers and static libraries) will be in separate packages. All of them will share the same package root name, but have the following mechanism for distinguishing them (by standard):

• packagerootname: Architecture-specific files.
• packagerootname-share: Non-architecture-specific files (will be stored in just packagerootname if there are no architecture-specific files.
• packagerootname-doc: Documentation files (man pages will be stored in packagerootname-share or packagerootname if there are no non-architecture-specific files).
• packagerootname-devel: Development header files.
• packagerootname-static: Static object files (if it is a library, that is).

Furthermore, while I am describing conventions, libraries will be prefixed with lib.

Conclusion

As you can see I have a lot of plans for this program, and I hope you have become interested in them. The RFC in the title of this post stands for Request For Comments, which means that I want you to tell me what you think. I am interested in knowing what others think of my ideas, and since this is really, really early in development, Candy can be subjected to radical changes (although I would prefer to avoid them).

How to Retrieve Files from a Broken Fedora Linux System

Not too long ago I installed the Fedora Core 13 GNU/Linux operating system onto my computer. A month in, I turned it on and it would not boot. It would get to the point in the loading screen when the loading bar was complete then it would just stop. I waited for half an hour, hoping that it was just trying to resolve some sort of issue, but no such luck. The day before I had been installing and uninstalling a lot of software, and apparently, I ended up corrupting the operating system. I could not retrieve my files.

Generally, you use a Linux system's Live CD to retrieve files and even repair a broken system; however, I had lost Fedora's Live CD. So instead, I used Ubuntu Linux 10.04's Live CD, which I found in my collection of Live CDs. I inserted the disk, rebooted the computer, and came upon the Live CD's instance of the GNOME desktop environment. The hard drive was listed as a readable entity, but when I clicked on it, I got an error message saying that the disk could not be read (a very indescript message, yes).

I fumbled through my disks and found a fairly old openSUSE 11.2 Live CD. I was really excited, because openSUSE has an automated system repair program on it. It was sure to figure out what was wrong. Well, wrong. It could not read the disk, and it seems that means it cannot help at all. How disappointing.

Searching through the disks again, I came upon an Arch Linux Live CD (yes, I have a lot of Live CDs). I booted it up and came upon the infamous command-line. I tried to mount the hard drive with mkdir /mnt/hd; mount /dev/sda3 /mnt/hd, and it said it could not recognize the filesystem.

I finally knuckled down and burnt another Fedora Live CD, and guess what? I was able to read off the hard drive no problems at all! I was able to retrieve my files. What did Fedora do to make it so that no other Linux could read its filesystem? What? I still do not know, but I do know that openSUSE never had that problem, so I installed that instead.

The moral of the story is that if you want to retrieve your files from a Linux, you should probably use that distribution's Live CD.

Microkernels: The Next Generation of Operating System Kernels

Microkernels are epic.  Why?  Because they hold the possibility to run multiple operating systems simultaneously, among other things.

The most popular kernel design family today is the Monolithic kernel design.  Monolithic kernels have huge number of features integrated into the kernel.  These features include user multiplexing, executable loading, drivers, and filesystems.

This design has two fatal flaws:

1. When any of these services fail, the entire kernel fails, and everything is lost.
2. Only one implementation of certain features, such as user multiplexing, may be implemented at a time, since the kernel's built-in features will get in the way.

Microkernels solve both of these problems.  Here is how.

Microkernels aim to implement the minimal requirements of a kernel and to move as much as possible into the user space, as in processes that you would see in a task manager.  These processes are known as "servers".  They provide the operating system with user multiplexing, executable loading, drivers, filesystems, and all of the other features most programmers expect from the kernel.  This has a few major advantages over the Monolithic kernel design.

For one thing, each server is its own process separate from the kernel, if a server crashes, the kernel remains functional and can even restart the server, thus massively decreasing the chances of error.  Along with this, each server has the least privilege possible, meaning that, for instance, a driver server is unable to accidentally delete files.

The increased modularity of the operating system is often much easier to manage, because each server may be assigned to a different programmer task force, may be coded in a different programming language, or even compiled into a different executable file format.

Each server may be interchanged with other servers, should a different server be more efficient or secure for your purposes.  In some cases you may even have two servers providing the same function (such as executable loading) at the same time, allowing the individual processes to decide which server they would like to use.

In some operating systems, you must rebuild the operating system in order to add new device drivers, filesystems, etc.  Microkernels simply need you to run new servers.  (This is not nearly as much of a problem now with Hybrid Kernels, in which much functionality remains in the kernel but it may be extended with user space programs.  In both Microkernels and Hybrid Kernels, a computer restart may be required depending on the operating system.)

Issues with the Microkernel Design

Microkernel design has one major issue--efficiency.  In order for a Microkernel to function, processes must communicate with each other through the kernel, as opposed to directly with the kernel.  For instance, a text editor must communicate with a filesystem server in order to load a file.

This entails "bouncing" your message from the kernel to another process.  This is a method of inter-process communication, or IPC.  In first generation Microkernels like Mach, the message would have to be copied from the sending process to the kernel, then copied again to the receiving process.  This turns out to be considerably less efficient then directly communicating with the kernel.

This inefficiency was not good at all.  While IPC took 400μs (microseconds) to send the average message, it took Monolithic kernels less than 1μs.  This issue led to noticeably slower operating systems and a dying design philosophy.

Furthermore, the fact that the servers are their own processes means that you must switch contexts more often, which also causes noticeable slowdown.

However, there is now a second generation of Microkernels that now run 400 times faster then the first generation Microkernels.  They have done this through various optimizations, and are just as fast, if not faster, than most Monolithic kernels.

Each kernel takes a different approach to this.

L4

The L4 microkernel implements the philosophy that Microkernels are inherently non-portable between processors and must take advantage of every optimization the processor has to offer.

L4, unlike Mach, only copies the message once, initially sharing memory with the sender then copying it to the receiver, leading to a two-fold speed improvement.  Another thing L4 does is when messages are small enough, it uses the processor registers (small but EXTREMELY quick-to-access memory zones), leading to a considerable amount of speed improvement.

In total, L4 only takes ~1.4μs to send the average IPC message.

MIT Exokernel

MIT's Exokernel has a different approach.  Its philosophy is that the kernel's purpose is only to section out resources to the processes, and that is it, letting the processes manage memory how they see fit and to talk to the hardware directly, reminiscent of DOS.  This is contrary to most kernels, which try to abstract the hardware in a portable manner.

This philosophy is inspired by another philosophy; the program knows better than the operating system.  The kernel is general.  The program is specific.

Essentially, this means that Exokernel will simply say "this part of memory is yours and this part of memory is yours, and you get to talk to the computer screen and you get to talk to the speakers".  Thus, the functionality of the operating system is implemented in libraries that abstract the hardware, however if the abstractions are unsuitable the program may simply bypass the operating system and talk directly through the kernel to the hardware, as long as it has acquired permission to do so.

Processes may also upload code to the Exokernel to help it decide what to do with the information it receives, which can be used, for example, in network package filtering.  The code uploaded is in a type-safe programming language that can quickly be dynamically compiled and sandboxed to prevent any harm to the kernel.  This can also be used to move intensive operations to the kernel so that the processor does not have to switch context as often.

In total, Exokernel only takes ~1.3μs to send the average IPC message.

SPIN

SPIN takes a radically different approach from the entire IPC concept itself (though it still supports IPC, as most kernels of all forms do).  It allows programs to upload code to be executed directly in the kernel.  This leads to massive speed improvement. Since SPIN sandboxes the code, and the code is uploaded in the type-safe Modula-3 programming language, it retains the ability to continue running upon failure of the uploaded code.

One major advantage of this is that code executed by the kernel itself is much more efficient, since processes communicate directly with the kernel to access the uploaded code and context switches occur a lot less.


In total, SPIN takes 400μs to send the average IPC message (due to roots in Mach), but its alternative method of extension theoretically removes this issue.

Now, for the part you have all been waiting for...

The Ability to Run Multiple Operating Systems Simultaneously

This is the greatest ability that Microkernels have.  Because there is nothing getting in the way of implementing alternative user multiplexers, executable loaders, etc., one is fully capable of implementing two operating systems on the same Microkernel and having them run at the same time.

For instance, you could have a UNIX-like server series in which you have a UNIX-like user multiplexer, UNIX-like executable loader, etc., allowing any program that runs on UNIX-like systems to run fully.  Then you could also have a BeOS-like server series, implementing a BeOS-like user multiplexer, and a BeOS-like executable loader, and have it run programs that run on BeOS-like systems, and both servers may run simultaneously.  This means that you could have both UNIX and BeOS programs running on the same computer without use of an emulator!

This feature is why I am personally interested in Microkernels.  For a long time I have wanted to run Windows-only Notepad++ using UNIX-only GNOME.

Have you ever wanted to use two programs from different operating systems at the same time?  What are they?

Resources:
http://pdos.csail.mit.edu/exo/
http://www.cs.cornell.edu/home/ulfar/ukernel/ukernel.html
http://en.wikipedia.org/w/index.php?title=L4_microkernel_family&oldid=383231412
http://en.wikipedia.org/w/index.php?title=Exokernel&oldid=379188198