Working with Minix 3 on Ubuntu with VirtualBox

In my OS course, we use the Minix operating system. We have various assignments that require us to edit kernel source code, etc. We use virtual machines for doing our work, and my preferred VM software is VirtualBox. There seems to be little info about using Minix with VirtualBox on the net, as Minix is not officially supported by VBox. Nevertheless it can be used fine. I am going to write about my own setup in roughly tutorial form.

First, about my software versions. At the time of this writing, I am using:

  1. the latest stable Ubuntu, which is Jaunty Jackalope, version 9.04, as the host operating system,
  2. the latest stable VirtualBox, which is version 3.0.4, and,
  3. the latest stable Minix 3, version 3.1.3a

It is quite simple to install Virtualbox on Ubuntu.

Installing Minix on VBox

http://wiki.minix3.org/en/UsersGuide/RunningMinixOnVirtualBox

My own VM settings are 128 MB RAM and a 1 GB virtual hard disk.

Installing packages

http://wiki.minix3.org/en/UsersGuide/InstallingBinaryPackages

Packages that are useful for me: flex, gcc, emacs, less, make.

Networking

Networking has not been possible to setup. I have tried to get bridged networking to work, so that files can be shared via ssh, but it has not worked yet. I will update if I do succeed. Please post in the comments if you have any tips.

Networking would have been ideal for transferring files both ways between the two OSes, but I am managing with one way transfers for now (Linux to Minix).

Exchanging files between Minix and Ubuntu

I have so far only succeeded in copying files into the guest OS and not vice versa. Since networking has not worked for me, I transfer files via cd images. To transfer single files, create a cd image containing the files in Ubuntu with:

mkisofs -o t.iso <list of single files>

Then, mount the cd image in the VM through VBox’s GUI: Devices->Mount CD ROM. To read the cdrom in Minix, use the isoread, and isodir commands. To copy files from the cd, use a command of the form:

isoread - /dev/c0d2 src.c > src.c

Don’t forget the hyphen after “isoread”.

Copying a whole directory into minix may seem complex using the above method, but the trick is to create a tar file out of the directory we want to copy. We copy the tar archive into minix using the method discussed above and then extract it in the guest.

Getting Minix kernel sources

This initially turned out to be challenging, because though the source code is available in the VM at /usr/src, it can’t be copied to the host for editing using powerful editors in Linux. The source code is available on the Minix cd but it is present in a cd sub-partition that is in the Minix filesystem format. Also, there is no readily available download package on the Minix website.

But there is the SVN repo. The only thing to find is the right revision for the version of Minix we use. Looking the tags folder, helped. To download the sources for my version, I fired off a terminal and typed:

svn checkout https://gforge.cs.vu.nl/svn/minix/tags/r3_1_3a

Enter the username as “anonymous” and enter a blank password.

To get rid of the .svn folders (these are not part of Minix source code) inside the sources folder we downloaded, use the following command from inside the folder created by the subversion checkout:

find . -name ".svn$" | xargs rm -rf

Now our sources are ready for editing.

Recompiling the Minix kernel

After we edit sources, we copy the files into Minix’s /usr/src. Then, from /usr/src/ we type:

make world

If everything works, this builds a new kernel and sets it up for booting. Type “shutdown” to shutdown the VM, and from the boot prompt, type “boot d0p0″ to start minix. In the resulting boot menu enter “3”, and we boot into the kernel we just modified! More information about recompiling is here.

/r3_1_3a

Editing files on remote servers via multihop-ssh on emacs

Suppose you need to access you department’s computer from outside the institute. The usual solution would be to use ssh. But what if you can access your department’s computer only via a different computer in your institute? Multiple ssh would be the usual way:

aditya@donatello:~$ ssh clac.edu
aditya@clac.edu's password:
aditya@clac.edu:~$ ssh adi@malhar
adi@malhar's password:
adi@malhar:~$

This is the situation at my institute where, we have access to one central departmental server via ssh, from which we can access computers in our labs.

I found that a single command is sufficient to achieve this:

ssh -t clac.edu -t ssh adi@malhar

Ssh prompts for the password twice, first for clac.edu and then for adi@malhar.

This is however not usually sufficient. We want to edit files remotely too. Being an emacs fan, I heard how tramp is a great component of emacs that lets you access files on remote hosts via ssh. I use it pretty often. But the usual way of using tramp to access files through multihop ssh did not work for me. Tramp would just wait for 60 secs and then say that login failed. Perhaps they might work for you.

After a little more investigation, I found that OpenSSH can do wonderful things. Let’s say we want to access a file on the host malhar in the example above. OpenSSH can be configured to access malhar by proxying through clac.edu. The settings are reasonably simple. Just open ~/.ssh/config and enter the lines:

Host malhar
ProxyCommand ssh clac.edu nc malhar 22

This requires that the server at clac.edu have a program called netcat installed. Luckily in my case, the server did.

Once this was setup, tramp is able to access files on malhar. I press C-x f (the emacs key combo to open a file) and enter /ssh:adi@malhar:textfile.txt and then tramp prompts for a password twice. First enter the password for clac.edu and then for adi@malhar, and we’re in. Awesome!

Dump MySQL table into CSV

I needed to dump MySQL tables into CSV for use with WEKA. A little google search helped. I found this. I am copying the command here for my reference:

SELECT * INTO OUTFILE ‘result.csv’
FIELDS TERMINATED BY ‘,’ OPTIONALLY ENCLOSED BY ‘”‘
LINES TERMINATED BY ‘\n’
FROM my_table;

Thank you, Terminally Incoherent! I love MySQL too!

Getting WiFi to work on Intel PRO/Wireless 3945ABG in Ubuntu Hardy

I have a brand new Elcot Laptop (Acer TravelMate 5720), which came with Suse Enterprise and Ubuntu Hardy preinstalled. I prefer Ubuntu, but I found that it does not detect my wireless card. My wireless device is Intel PRO/Wireless 3945ABG.

If you have the same setup you can simply follow the steps that I did. To check what wireless device you have, run:

sudo lshw -C network

To get your card running, create a file in /etc/modprobe.d called iwl3945. Paste the following into it:

alias wlan0 iwl3945
options iwl3945 disable_hw_scan=1 hwcrypto=1

Now, you need to install the package linux-backports-modules-hardy-generic. To do this, you need to enable the Hardy Backports repository in Synaptic and then install it. If you are not sure how to do this, you can find instructions with screenshots here.

Reboot and your device should be working along with the wifi LED. You should be able to connect to unencrypted networks using this setup. A different network manager is needed connect to encrypted networks called wicd. To install wicd, follows these instructions. You should be all set now!

NOTE: All this information is also available in many scattered discussions in the Ubuntu Forums.

Best buys this season: The ELCOT Student Laptop

The Electronics Corporation of Tamil Nadu has started this year’s sale of inexpensive laptops with preloaded Linux (SUSE Linux Enterprise) for students studying in Tamil Nadu. There have been many press releases, for example, see this one. The laptop is said to be procured from Dell or Acer.

The high capacity version of the ELCOT laptop is priced at Rs. 31,717 and is really cheap! To be really convinced of this, I checked out the Dell site for their price on an equivalent configuration. This is really easy, because they have a nice customise feature on their site. So I went here and chose options to make the configuration equivalent to ELCOT’s config here. The results are astounding! The Dell price turns out to be Rs. 55317! The big price addons were 7000 rupees for the 320 GB upgrade, from 160 GB and the 3 years international support which added another (approx.) 8000 rupees. Of course, since Dell has not rolled out its preloaded Linux version in India (Dell sells with Ubuntu preloaded, in the US), the price above includes the price of Microsoft’s operating system.

Students are going to make a killing in this sale! Hurry! Last date for registrations in this first phase is July 15.

Edit: Elcot has extended the last date, as expected. The new last date is 31 July.

Edit 2: Elcot has further extended the last date! The new last date is 15 August.

Edit 3: Elcot has further extended the last date! The new last date is 31 August. And, I’m bored of updating this.

Edit 4: Elcot has finally closed the student laptop scheme 2008.

Download day Announced!

Download Day 2008

17th June 2008

That’s the official release date that has been announced for Firefox 3 on the Mozilla Developers blog! So lets get ready to implement our pledges and download the best browser out there!

EDIT: 15th June’s “The Hindu” newspapers features an article about Ubuntu and Firefox, how they rock and why they are great for Linux newbies!

Interesting CS Interview Questions #2

This post is a continuation of my interesting CS interview questions series. The last two problems discussed in this post lean more towards logic and probability rather than a CS concept.

Consider the Lock and Unlock operation defined on an m-ary tree as follows:

Lock Node X => If (no node present in the subtree rooted at X (including X) is locked) AND (no direct ancestor of X is locked), then lock X

Unlock Node X => Assumes that it is called only a node that has been previously locked. Simply unlocks the node X.

Design an efficient data structure and algorithms to perform the required lock and unlock operations.

The first solutions that struck me was to simply perform a complete tree traversal and determine if the required conditions for locking are being met or not. This has complexity O(N) where N is the number of nodes. Is this the best that can be done?

On further thought, since we can decide the data structure which suits us best, we can improve the efficiency. Suppose for each node we have a pointer to the parent node. Then, determining if any direct ancestor is locked is simply a loop that climbs the tree, via the parent pointers. How to check if any of the children in the subtree is already locked? Another traversal is possible, but it would not improve our time complexity. If a node is locked, all the direct ancestors need to know that a child is locked. So, this gives the idea to use a flag for each node which is set if a child is locked. Now the lock operation can check if a child is locked in constant time. After locking successfully, it needs to traverse back up to the root via the parent pointers and mark for each node that a child is locked.

How will unlock happen then? We just unlock the node that is given, but we cannot simply unmark the child-node-locked flags in the parents. Why? Because there may be other children that are locked! This seems to complicate things. But not really. Instead of using a flag to hold the information, we use an integer. The integer simply counts the number of child nodes locked. Thus, while unlocking we simply decrement these counts.

Now, what is the time complexity? It is logarithmic because we only look at the path from the node to the root (via the parent pointers).

This one is like a puzzle. A table has 100 coins, 30 of them with Heads facing up. There is another table with no coins. With your eyes blindfolded, what will do so that the number of coins with Heads facing up is equal on each table? You cannot determine if a coin is facing Heads up or not by touching it. You are basically allowed to flip coins and move them from one table to the other.

This problem was pretty challenging for me. Initially the number of Heads in each table is 30 and 0. After experimenting various things with a smaller number of coins, one notices (or at least is supposed to notice) that moving one coin from the first table to the second and flipping it causes the difference in the number of Heads between the tables to decrease by 1. Why? Suppose the coin was a Head in the first table. On flipping and moving it to the other table, the number of Heads in the first table decreases by 1 but the number of Heads on the second table remains the same (as it is added to the Tails count). If the coin was a Tail, then it increases the Heads count in the second table without affecting that of the first table. So the solution is to repeat this process of choosing some coin and flipping it, and moving it to the other table, 30 times. Since the initial difference in the number of Heads is 30, after this process the difference becomes 0. Thus, the number of Heads is equal in each table.

Given a long stream of numbers, how will you choose a single number, such that it is uniformly random among the numbers so far seen?

Although, one can store all the numbers and then choose one at random using standard random functions (like in C), we would like a method that is space efficient. There does exist a method that requires only constant space. Any idea?

Say we have reached the N-th number in the sequence and suppose we already have the solution for the first (N-1) numbers that appeared in the sequence. Suppose this solution is X. Then X was chosen with probability 1/(N-1) from the first (N-1) numbers. Since the N-th number in the sequence should have a 1/N probability of being the random number chosen among the first N numbers in the sequence, we decide if it is indeed the chosen random number with a probability of 1/N. Suppose it were not, then the number X will be the random number chosen. We can verify its probability by noting that it is given by (1/(N-1))*((N-1)/N) = 1/N. Thus, we have the solution: for the i-th number in the sequence, choose it as the random number with probability 1/i, otherwise, do not modify the previously chosen random number.

Follow

Get every new post delivered to your Inbox.