Wednesday, April 14, 2010

Continue running a non nohup-ed command after logout (no SIGHUP)

Many times it happens that you start a command that takes fairly long time to complete, and before it ends, you must log out for some reason - maybe the network will go down soon or you do not want to keep staring at the screen till it completes, or you just don't want to keep that terminal around.

A bit of shell behaviour for the uninformed. When you launch a command in a shell, the new process is created by fork()ing the current shell and immediately exec()ing the command executable/binary, which means the new process is a child of the shell process. You can stop the running process and keep it running in background as

% java some.long.running.application
{java program spits out something}
{hit ^z}
^Z
zsh: suspended  java some.long.running.application
% bg
[1]  + continued  java some.long.running.application

or you can start it in background as

% java some.long.running.application &
[1]  1001
{java program spits out something}

of course you can bring these jobs in foreground any time you want

% jobs
[1]  - running    iostat -xd 100
[2]  + running    java some.long.running.application
[3]  + suspended  ~/bin/startOfflineIMAP.sh
% fg %2 {bash users must drop the %}
[2]    running    java some.long.running.application
{java program spits out something}

Now you want to log out. The moment you log out of the terminal, the shell process sends SIGHUP signal to all running children and SIGCONT->SIGHUP for all stopped children. The default behaviour of an application after receiving SIGHUP is to exit. Any applications - foreground, as well as background, that were started from this shell are killed. We want our application to survive after logout.

The textbook way of doing this is to start the command with `nohup' as

% nohup java some.long.running.application &
[1] 1001
% logout

or the subshell trick :

% (java some.long.running.application &)
% {prompt returns, java disowned}
{java program spits out something}

zsh users can do it as :

% java some.long.running.application &!
% {prompt returns, java disowned}
{java program spits out something}

Or use the good old screen (my favorite)!

Unfortunately you did not start the process with nohup or subshell trick, and say the process can not be restarted because of some reason or it has done significant work already.

What if we could tell the shell not to send SIGHUP to a particular child?
`disown' command lets you do just that! :D

% jobs
[1]  - running    iostat -xd 100
[2]  + running    java some.long.running.application
[3]  + suspended  ~/bin/startOfflineIMAP.sh
% disown %2 {bash users must drop the %, also bashers can add -h option}
{java program spits out something}

This tells the shell not to send SIGHUP to our precious java process. And you'd think you can now happily log out with java process still running.

Well, not quite. Say the shell has pid 1000 and java process has pid 1001, then

% ls -l /proc/1000/fd
total 0
lrwx------. {...} 0 -> /dev/pts/1
lrwx------. {...} 1 -> /dev/pts/1
lrwx------. {...} 2 -> /dev/pts/1

% ls -l /proc/1001/fd
total 0
lrwx------. {...} 0 -> /dev/pts/1
lrwx------. {...} 1 -> /dev/pts/1
lrwx------. {...} 2 -> /dev/pts/1


Which means process 1001 uses terminal /dev/pts/1 as it's stdin, stdout and stderr. Even if we disown the java process, when the shell quits, terminal device /dev/pts/1 will not be available, and hence next read or write by java process to any of stdin/stdout/stderr will probably result in an abort. Even if it does not abort, you might want to capture stdout and stderr of the program somewhere to a file maybe, and possibly feed some file to it as input. That is not possible as

% ls -l /proc/1000/fd
total 0
lrwx------. {...} 0 -> /dev/pts/1 (deleted)
lrwx------. {...} 1 -> /dev/pts/1 (deleted)
lrwx------. {...} 2 -> /dev/pts/1 (deleted)

Sad, isn't it?

Not quite!

Let us analyze how nohup works. If output of nohup is not redirected to some file, by default all the output of nohup-ed program goes to some default file (such as $HOME/nohup.out or $PWD/nohup.out). In any case, nohup has a writeable file descriptor to the file where output is supposed to go. Immediately after fork() but before exec(), nohup duplicates this fd to stdout and stderr using dup2(). This way, the child can keep running after being released from the shell without SIGHUP (which means it's parent=1), as stdout and stderr fds are still valid because they no longer are the fds of parent shell but fds of some real file opened. Stdin is probably uncared for as we are running the process in background, non-interactive mode after all.

The question is : all this is fine as it is done _before_ starting the java process. What can we do to change it's stdout and stderr _after_ it has been launched already?
Note that we can not modify /proc/1001/fd/1 to link to some real file (me wonders what issues would creep up if it was allowed).

Our good old friend gdb comes to rescue! The solution is trivial. Just attach the process, open a file you want the output to go to within that program with open() and dup2() the new fd to 1 and 2 :D

% gdb -p 1001
....
Attaching to process 1001
Reading symbols from /usr/bin/java...(no debugging symbols found)...done.
...
(gdb) call open("/home/prashant/tmp/output", O_WRONLY | O_CREAT | O_APPEND)
$1 = 5
(gdb) call dup2(5,1)
$2 = 1
(gdb) call open("/home/prashant/tmp/output.err", O_WRONLY | O_CREAT | O_APPEND)
$1 = 6
(gdb) call dup2(6,2)
$3 = 2
(gdb) detach 
Detaching from program: /usr/bin/java, process 1001
(gdb) quit
%

In case debug info is not available, you can replace the O_ macros to actual values in fcntl.h

...
(gdb) call dup2(open("/home/prashant/tmp/output", 0x209),1)
$2 = 1
(gdb) call dup2(open("/home/prashant/tmp/output.err", 0x209),2)
$3 = 2
(gdb) detach
...

Note that you can redirect stdin and stdout in same file if you wish (just be careful with append mode on NFS and truncate mode in general ;).

And that's about it. Go ahead and logout. Your process should be busy while you are gone.

PS : this will work as long as the program does not try to read anything from stdin. If and when it does, it may crash depending on whether the program abort()s when it can not do basic IO on fds 0,1 and 2. You might want to open another file to read and use dup2() in similar way if you plan to provide input from a file.

Monday, March 29, 2010

Debugging kernel with qemu and gdb

Assuming that you have your (or Linux/*BSD/Solaris/Windows or any other) kernel on a bootable device, you can debug the kernel and also the loadable modules as well as user mode applications with QEmu/Bochs and good old gdb.
  • Configuring QEmu
You need qemu compiled with gdb support. QEmu needs no configuration file as such, and can be launched with gdb support as:
qemu -hda hd.img -fda floppy.img -boot ac -m 512M -S -gdb tcp::5022
 After this, qemu will continue executing the VM, and wait for a gdbmi connection on tcp 5022.
  • Configuring bochs
bochs is one of the most popular emulators in the hobbyist x86 kernel developers' world. Again, you need bochs which was configured and compiled with gdb stub. Some distributions like Fedora have a separate package for bochs with gdb stub, in case you do not want to go through the trouble of compiling it yourself.

Bochs needs a configuration file for launching a VM. Assuming you know the basic syntax, go ahead and add the following :
gdbstub: enabled=1, port=5022, text_base=0, data_base=0, bss_base=0
adjust the segment bases according to the bases of your segments. If you are following a flat memory model, pin them to 0.
After starting with this config, bochs will wait for a gdb connection even before the first instruction in BIOS trampoline is executed. This way you can debug a bootloader, and also your custom bios!
  • GDB
Obviously you need to compile what you plan to debug (be it kernel, user libs, user apps) with good amount of debug support. -g3 with gcc is my default. Not to mention, do not strip the binaries.

Start up gdb.

This tells gdb to read debug info from kernel image 'krnl/kernel'.
file krnl/kernel

This tells gdb to connect with a gdbmi connection to tcp 5022, the port on which either qemu or bochs is already waiting.
target remote localhost:5022

In order to debug user mode apps,
add-symbol-file apps/testApp1.elf 0x04000000

There you go. Now you can pretty much debug the entire system so as to say. Almost all common gdb commands like breakpoint, watchpoint, assembly debugging etc. work without sweat. If your fingers hurt, put all these commands in a file named '.gdbinit' in your project directory. gdb will pick it up and load and connect automatically.

This can save gazillions of man hours of a hobby kernel developer. Believe me, printk debugging is no fun. Source level kernel debugging when you are writing IDT handling code is must. When writing interrupt handler and paging, I have wasted two weekends in pleasing company of triple faults, completely clueless.

For the sickle minded and the general wannabe h4x0r, you just got a (way more) powerful alternative to rootkits. Rev those dongles and drivers. Let your imagination run wild ;)

Tuesday, February 16, 2010

Software piracy and Open Source (OSS)

Software piracy eats up a lot of revenue of the big guys. One might think that since piracy is bad for software companies selling proprietary software, it is good for open source. It is surprising to see many open source followers correlate lower business or loss of software giants (due to piracy) with growth or victory of open source. I believe this is not true.

Take example of Microsoft Windows. Paying for windows is a new concept for many people in the place I come from. Undoubtedly, Windows is the best operating system to go for if you are a serious gamer, as almost all games that come for PC are targeted at Windows. If you do not have Windows, you are left out. At this point, there are two choices - either legally buy a copy of Windows, or use a pirated copy. If you buy, you have already fueled the proprietary engine.

Assuming you chose to use pirated copy instead, you essentially got it for free (in a free beer sense, even though you do not have the sources and consent that you can freely modify and redistribute). This is where comparison starts between pirated proprietary software and the open source alternative. Many times the open source alternatives are under-manned and under-funded, which means they lack some (probably game changing) features that are present only in the proprietary software. This makes the open source versions look inferior. The general public does not think twice; they can get both for same price - free! Obviously they would go for the better proprietary version. They do not realize that they are weighing watermelons (well funded, manned and planned proprietary software) against grapes(OSS), and the OSS alternative loses popularity. As OSS versions' popularity reduces, more and more people turn to the proprietary software, either buying it or using pirated copies - a vicious circle. As more and more people use Windows, more and more softwares (utilities, office software, games, multimedia etc.) are made available for windows (many times exclusively), which in turn attracts even more people towards Windows. If not a single person used pirated Windows, the number of installations of Windows would be _significantly_ lesser than it is now, which would force application developers to write software that also runs on other operating systems, which in turn will lead to more adaptation of non-Windows operating systems by people. It is essentially a balance, which miraculously tilts in favor of proprietary software when it is pirated. This is why some companies deliberately let people use pirated copies of their softwares long enough to set the `vendor lock-in'.

I believe this is true for any proprietary software and it's OSS alternatives. To break this cycle, next time someone asks you for a pirated copy of a software, hand him an (or a list of) OSS alternative, ask him to support the development team by providing money, manuals, free advertisement space, compute power etc.

When two or more OSS softwares doing similar things compete against each other, the price and piracy factors are missing from the equation, but everything else still holds - the better the software at solving users' problems, the more followers/popularity/user-base it will get. A purely merit based system/balance! We want people to fairly compare proprietary software and corresponding OSS on equal grounds, which means asking users to compare the copy of Windows they _bought_ for a couple hundred dollars, with Linux which is available for free.

I still do not know if the open source model is the best for our industry, but if you strongly believe in open source, please persuade people not to pirate.

Tuesday, December 01, 2009

Duplicate or missing numbers in an array

This is one of the most frequently asked questions in CS job written tests and interviews. Though other solutions like counting sort, linked-list-loop detection, sum etc. exist, they have their own complexities and limitations.

here is one O(n) approach I came up with (during a test), which actually seems to work.

Throughout, I assume that the numbers are between [1..n], all positive and integers are large enough to hold all of these (but not necessarily their sum, which can be an issue with the sum based approach), and XOR works with regular semantics.

given an array of length n which contains elements from [1..n] without repetitions, let x = XOR(all elements of the array)
Then

x = n if n = 0 mod 4
x = 1 if n = 1 mod 4
x = n+1 if n = 2 mod 4
x = 0 if n = 3 mod 4

We know n and also the expected value of x if the missing number was there. Just XOR the result of XORing all elements of the given array with expected x from given n, which gives the missing number. The same argument holds for one repeated number too.

Here is a sample C program which finds one repeated number.

int n = 100000;
int a[n + 1];
int rep = n - 1;
int i = 0;
int idx = 0;
for(i = 1; i <= n; i++){
  a[idx++] = i;
  if(i == rep)
    a[idx++] = i;
}

int res = 0;
for(i = 0; i < n + 1; i++){
  res ^= a[i];
}
switch(n % 4){
  case 0 : res ^= n;     break;
  case 1 : res ^= 1;     break;
  case 2 : res ^= n + 1; break;
  case 3 : res ^= 0;     break;
}
printf("%d\n", res);

Sunday, November 08, 2009

Going lambda/functional with m4

m4 is the GNU version of traditional macro processor. Even though it is a single pass macro processor, unlike cpp, it can also process the substitutions of a macro, we can define a macro to define another macro, and use the newly created macro, and so on. Thus, we can, in some sense, use m4 as a functional programming language.

Recursive version of factorial program is straightforward in m4:

define(`rec_fact', `ifelse($1,0,1,`eval'($1 * `rec_fact'(`eval'($1 - 1))))')
rec_fact(15)


We can also create non-recursive version in m4. Since lambda terms are essentially anonymous functions, we write m4 macros to create and destroy new pseudo-anonymous macro definitions. Following macro defines the Y combinator equivalent in m4.

dnl Thanks to Toby White (http://uszla.me.uk/space/essays/m4Y)

define(define(`Y_COMB', `dnl
pushdef(`recur',dnl
`pushdef(`y_anon',dnl
`$1''changequote([,])(['changequote([,])`changequote`]`$[]1'(``$[]1'')dnl
['changequote([,])'changequote`])changequote`dnl
(changequote([,])`$[]1'changequote)dnl
`popdef(`y_anon')')'dnl
`y_anon')dnl
pushdef(`y_anon',`dnl
recur(`recur')'changequote([,])(`$[]1')changequote`dnl
popdef(`recur')`'popdef(`y_anon')')`'dnl
'`y_anon')`'dnl


This essentially is a version of fixed point combinator given by Haskell Curry and is defined as Y = \lambda f.(\lambda x.f (x x)) (\lambda x.f (x x)). This is similar to recur(recur). \lambda x.f (x x) is implemented as $1(`$1') in y_anon.

The non-recursive version of factorial can be written as :
define(`ARG1', `changequote([,])`$[]1'changequote')dnl
define(`F_fact',`dnl
pushdef(`anon',dnl
`ifelse'(ARG1,1,1, dnl
``eval''(ARG1 * ``$1''(`eval'(ARG1 - 1))))dnl
`popdef(`anon')')'dnl
`anon')dnl


And now all we need to do to call this non-recursive factorial functions is:
Y_COMB(`F_fact')(5)


We can also define a sugar function named fact that expands to Y_COMB(`F_fact').

Not just tail recursion but we can also run any kind of general recursive program in non-recursive fashion:

define(`F_fib',`dnl
pushdef(`anon',dnl
`ifelse'(ARG1,1,1, ARG1,2,1, dnl
``eval''(``$1''(`eval'(ARG1 - 2)) + ``$1''(`eval'(ARG1 - 1))))dnl
`popdef(`anon')')'dnl
`anon')dnl
Y_COMB(`F_fib')(11)


Run the above with m4 -dV to get sequence of reductions, it helps a lot with debugging.

Note that data constructors are also actual functions in m4, and there is no built-in support for say tuples or lists. It is more lambda-ish than say Haskell-ish. We have to build all such structures ourselves. The evaluation scheme is not full-lazy.

Saturday, November 07, 2009

Pidgin : Log in invisible for Google Talk (XMPP/Jabber)

I am a big fan of pidgin, primarily due to it's configurability and plugin support. One of major turn-off people report around me is that pidgin does not support logging in as invisible with gtalk account. Not that I am a big fan of invisibility, I built a plugin that lets you do just that.

Not supporting neat 'sign on as invisible' for gtalk is basically due to lack of time and willingness on Pidgin developers' part. Not that they can't, they just don't want to at the moment due to some extra stuff gtalk uses/needs.

Installation instructions:

It is written in Perl, which means you need perl 5+, pidgin-perl and libpurple-perl packages.


On apt based systems (like Ubuntu), do (as root)
apt-get install pidgin-perl

looks like Ubuntu 9.10 has this built in.

on fedora and alike

yum install pidgin-perl

That should install all required packages, with dependencies.

Download and extract the plugin perl script.
Save it to your ~/.purple/plugins/ directory. That is, /home/{username}/.purple/plugins/.
If you find that hard, there is an install script included.

Usage:
Go to Tools->Plugins. Find 'Google Talk Invisible Plugin' and enable it.
Now, when you set your status as "Extended Away", you become invisible. Simple!

This is the pre-pre-pre-...-alpha release, which means I did not go through the trouble of activating the INVISIBLE status for gtalk accounts, and hijacked xa instead. I hope it is not a big mistake.

Update : there is a serious bug in this plugin. After you become invisible, you can not get updates to your contact list, and hence if you start pidgin with the plugin enabled in extended away mode, you may not see any online friends at all. I am working on it.

Thursday, September 10, 2009

Basic Authenticating pseudo-proxy with bash/netcat

Yes, you can also do authentication with netcat.


#!/bin/bash
# @author : Prashant Borole (prashantb  :can be reached at:     cse iitb ac in)

# A simple proxy-proxy that authenticates on users' behalf.
# Known limitations :
#       Works for Basic proxy authentication at the moment (though it is not that hard to add digest support)
#       Can process single request at a time. Any parallel requests will not be satisfied. This may lead to referred elements not being loaded, eg. images. Download accelerators are rendered useless.
#       Due to the logging format, there can be storage issues when downloading huge files.
#       Significantly slower than squid or some custom asyncio implementation as each request spawns bunch of new processes
#       No cache. Each request is strictly sent to upstream proxy
#       no https or ftp support

# TODO put this in some standard location
CONFIG_FILE="$HOME/.proxy.conf"

export LISTEN_PORT=
export PROXY=
export PROXY_PORT=
export LOG_FILE=

init()
{
        exec   2>&- 2>&1
        exec   5>&1
        exec   >>"$LOG_FILE"
}

readConfig()
{
        # really cheap config parsing.
        # FIXME improve
        # echo "Loading Configuration from $CONFIG_FILE"
        export LISTEN_PORT=$(grep "LISTEN_PORT=" "$CONFIG_FILE" | cut -d '=' -f2)
        export PROXY=$(grep "PROXY=" "$CONFIG_FILE" | cut -d '=' -f2)
        export PROXY_PORT=$(grep "PROXY_PORT=" "$CONFIG_FILE" | cut -d '=' -f2)
        export LOG_FILE=$(grep "LOG_FILE=" "$CONFIG_FILE" | cut -d '=' -f2)
}

if [ "$1" != "--" ]; then
        # read the config initially
        readConfig
        
        # accept credentials
        echo -n "$PROXY:$PROXY_PORT    user name : "
        read USER_NAME
        echo -n "$USER_NAME@$PROXY:$PROXY_PORT Password : "
        read -s PASSWORD
        echo
        export B64CRED=`echo -ne "$USER_NAME:$PASSWORD" | base64`
        unset USER_NAME PASSWORD
        echo "Credentials accepted."

        # launch in background
        $0 -- &
        exit 0
else
        trap 'echo "cleaning up $TMP_DIR" ; rm -fr "$TMP_DIR"; killall -9  nc tee >/dev/null 2>&1' EXIT
        trap 'echo "Shutting down proxy server on port $LISTEN_PORT" ; exit 0' SIGUSR1
        trap 'echo "Reloading config..." ; readConfig' SIGUSR2
        trap 'echo "[UNCLEAN] Shutting down proxy server on port $LISTEN_PORT" ; exit 1' SIGINT SIGKILL SIGSEGV SIGPIPE SIGHUP SIGTERM SIGABRT

        readConfig
        init
        echo "`date`   Server $0[$$] started"
fi

TMP_DIR=`mktemp -d /tmp/proxy.XXXXXXXX`

BACK_FIFO="$TMP_DIR"/back_fifo
# create a pipe
mknod "$BACK_FIFO" p

echo "Accepting connections on port $LISTEN_PORT"
while true ; do
        nc -l "$LISTEN_PORT" 0<$BACK_FIFO | tee request | (while read line ; do if [ "$line" = "^M" ] ; then echo "Proxy-Authorization: Basic $B64CRED" ; echo ; else echo "$line" ; fi;  done) | nc -w 5 "$PROXY" "$PROXY_PORT" | tee response 1>$BACK_FIFO
        head -n+1 request
        head -n+1 response
done

echo "THIS SHOULD NEVER HAPPEN. SOMETHING IS WRONG !!!"
exit 1


Note that you can NOT use something like sed or awk, because they simply give up when there is no text to read. This breaks the pipe. A "while read" loop just cuts it :)