Merge Sort in Bash

Posted in Code on March 25th, 2010 by hobogod

Thanks to Adam Vite for this.

So, during spring break, I was extremely bored and implimented merge sort into a language that doesn’t really need it: Bash. I got inspiration to do this from seeing  merge sort implimented in Prolog. As of right now, it merely sorts integers, but can sort anything, given that a compareTo method of what you want sorted is written into the merge method (bash isn’t object oriented, so it’s not really so adaptable to adaptability.) I doubt I’m the first person to do this, but it’s a nice thought experiment to see how limited languages can still allow the performance of advanced operations. I don’t guarantee that this algorithm performs in n*log(n) time as I’m not sure of the individual costs of bash operations or the cost of reading and executing this, but I tested it with 1330 numbers and it sorted them in about 35 seconds on my 1.6 Ghz laptop.


mrgsrt() {
# This function impliments the merge sort algorithm into bash.
# @Author: Adam Vite

if [ $# = 1 ]; then
echo $1;
# There is only one arguement, list is sorted
elif [ $# -gt 1 ]; then
unset left;
unset right;
for x in [email protected] ; do
if [ $i -lt $(($# / 2)) ]; then
left=$( echo $left $x );
i=$(($i + 1));
right=$( echo $right $x );
# The arguments have been split in half

left=$( mrgsrt $left );
right=$( mrgsrt $right );
# each half has been sorted recursively

mrg $left $right;
# The two halves have been merged together with a helper method
echo “Usage: mrgsrt <series of numbers seperated by spaces>”;

mrg() {
# This method sorts two sorted lists of numbers by adding the lowest of
# firstmost unsorted number into a new list until all numbers have been
# added and then returns that list.
# @Author: Adam Vite

l=1; # Begining index of left half
r=$(($# / 2 + 1)); # Begining index of right half
unset list;
while [ $l -ne $(($# / 2 + 1)) ] || [ $r -ne $(($# + 1)) ]; do
if [ $l = $(($# / 2 + 1)) ]; then
list=$( echo $list ${!r} );
# Left half has been sorted

elif [ $r = $(($# + 1)) ]; then
list=$( echo $list ${!l} );

# Right half has been sorted

elif [ ${!l} -lt ${!r} ]; then
list=$( echo $list ${!l} );
# Firstmost unsorted left is less than firstmost unsorted right
list=$( echo $list ${!r} );
# Firstmost unsorted right is less than firstmost unsorted left
echo $list;

Automate Restart of D-Link DCS-900 Cameras

Posted in HowTo, Informational, Security on January 18th, 2010 by termina

I have some older D-Link DCS-900 cameras being used with ZoneMinder for a security system at home.

While these cameras are normally very stable (no lock-ups for weeks or months at a time) it still happens. To make things work more smoothly, I decided to find a way to restart the devices with cron.

I decided to have the cameras be reset twice a month (on the 1st and 15th of each month at 4am).

crontab -e

0 4 1,15 * * wget –http-user=admin –http-password=YOUR-PASSWORD -O /dev/null –post-data=”Reset= Yes ” http://camera1/Reply.html


You can remove the –http-user and –http-password sections if you do not have an admin user/password set.

Ubuntu 9.10 PXE Boot

Posted in Networking, Services on November 16th, 2009 by termina

Ubuntu 9.10 uses initrd.lz instead of initrd.gz, so PXE booting like you did in previous versions does not work.

This article assumes you’ve already downloaded the iso and have a working PXE boot server.

First, copy the contents of the iso to a directory we can work with

mkdir /tmp/910

mount -o loop ubuntu-9.10-desktop-i386.iso /tmp/910

cp -r /tmp/910 /tftpboot

Convert initrd.lz to initrd.gz

cd /tftpboot/910/casper

mkdir initrd

cp initrd.lz initrd

cd initrd

lzma -dc -S .lz initrd.lz | cpio -id

rm initrd.lz

find . | cpio –quiet –dereference -o -H newc | gzip -9 > initrd.gz

cp initrd.gz /tftpboot/910/casper

Now add the appropriate lines to pxelinux (Example: /tftpboot/pxelinux.cfg/default)

LABEL Ubuntu 9.10 i386 Unmodified Livecd
KERNEL 910/casper/vmlinuz
APPEND root=/dev/nfs boot=casper netboot=nfs nfsroot= initrd=910/casper/initrd.gz quiet splash --

Make sure /tftpboot is shared via nfs; in /etc/exports add the following line


Reload the NFS server

/etc/init.d/nfs-kernel-server reload

OpenSolaris LDAP Client to Linux OpenLDAP Server

Posted in Networking, Security, Services on November 13th, 2009 by termina

The following outlines how to set up a OpenSolaris client to work with a Linux OpenLDAP server.

The following is one line

ldapclient manual -a credentialLevel=proxy -a authenticationMethod=simple -a proxyDN=cn=admin,dc=server -a proxyPassword=yourpassword -a defaultSearchBase=dc=server -a defaultServerList= -a serviceSearchDescriptor=passwd:ou=People,dc=server -a

Add the following lines to their appropriate sections in /etc/pam.conf

login   auth required 
other   auth required 
passwd  auth required

Test LDAP with

ldaplist -l passwd

Test user authentication using the following steps

mkdir /export/home/ldapuser

chown ldapuser /export/home/ldapuser

Edit /etc/auto_home and add the following BEFORE “+auto_home”

ldapuser localhost:/export/home/ldapuser

SSH to test

ssh [email protected]

You should be in! If not, you may have to change the following in /etc/ssh/sshd_config

PAMAuthenticationViaKBDInt no

#Change from yes to no

Restart SSH

svcadm restart ssh

If you are still unable to log in, your userPassword attribute probably needs to be changed from md5/md5crypt to crypt.

su – ldapuser


After changing your password you should be able to log in.

View processes (PID) using disk I/O

Posted in Informational, Issues, Storage on July 28th, 2009 by termina

Install the sysstat package

apt-get install sysstat

# iostat -m
Linux 2.6.27-14-generic (slowaris)      07/28/2009      _x86_64_

avg-cpu:  %user   %nice %system %iowait  %steal   %idle
4.88    6.65    3.03    1.49    0.00   83.95

Device:            tps    MB_read/s    MB_wrtn/s    MB_read    MB_wrtn

md0             221.24         0.64         0.78    1765002    2159490

We can see that I/O isn’t terribly high here, but there are 221 transfers per second going on.

To check what processes are causing I/O

echo 1 > /proc/sys/vm/block_dump

tail -f /var/log/syslog | grep md0

Jul 28 08:20:12 server kernel: [2752582.434647] kvm(17362): READ block 1017744552 on md0
Jul 28 08:20:12 server kernel: [2752582.502401] kvm(17362): READ block 615283608 on md0
Jul 28 08:20:13 server kernel: [2752582.634622] kvm(17362): READ block 1017744576 on md0
Jul 28 08:20:14 server kernel: [2752583.964709] kvm(17362): READ block 1017744608 on md0
Jul 28 08:20:14 server kernel: [2752584.372889] kvm(1868): dirtied inode 17367041 (live-default-32.img) on md0
Jul 28 08:20:14 server kernel: [2752584.372908] kvm(1868): dirtied inode 17367041 (live-default-32.img) on md0

We see that kvm is causing some disk I/O; now where know where to start investigating!

To turn off these messages

echo 0 > /proc/sys/vm/block_dump

OpenVZ on Ubuntu 8.10

Posted in Services on July 14th, 2009 by termina

Other OpenVZ Ubuntu 8.10 guides that I’ve seen have you use the old lenny repository; since this no longer exists let’s try another way!

I used a 64-bit machine; steps will be the same for 32-bit. If you have 64-bit and just want to download the kernel I used:

Now let’s build the kernel.

cd /usr/src
tar xjf linux-2.6.27.tar.bz2
cd linux-2.6.27

gunzip patch-briullov.1-combined.gz


cp kernel-2.6.27-*.config.ovz .config
patch -p1 < patch*

make oldconfig

make modules_install install

cd /boot
mkinitramfs -o /boot/initrd.img-2.6.27 2.6.27

vi /boot/grub/menu.lst

#Replace uuid entries with your disks uuid
title           Ubuntu 8.10 OpenVZ 2.6.27
uuid            2d5b2466-4bdf-44c7-b8e5-4d46a9f927c8
kernel          /boot/vmlinuz-2.6.27 root=UUID=2d5b2466-4bdf-44c7-b8e5-4d46a9f927c8 ro quiet splash
initrd          /boot/initrd.img-2.6.27

grub-install /dev/sda

apt-get install vzctl vzquota


If everything went according to plan, you’ll boot into your new kernel. If you get a kernel panic, or things are not working as expected, you may have to

make menuconfig

Once the kernel is working, let’s create a container.

cd /var/lib/vz/private

mkdir 1

debootstrap hardy 1

When you see:

#I: Base system installed successfully.

You can continue.

vi /etc/vz/dists/default
#Change redhat to debian OR copy ubuntu.conf to default

Create the container and set an IP

vzctl set 1 –applyconfig vps.basic –save
vzctl set 1 –ipadd –save
vzctl set 1 –nameserver –save

vzctl start 1

At this time you cannot enter the container. You will receive the error

Unable to open pty: No such file or directory

To fix this:

vzctl exec 1 update-rc.d -f udev remove

Restart and enter the container

vzctl restart 1

vzctl enter 1

If network doesn’t work add to /etc/sysctl.conf on server (not container):


Ubuntu 8.10 LDAP Server with TLS

Posted in HowTo, Networking, Services on July 8th, 2009 by termina

This should also work with Ubuntu 9.04

apt-get install slapd ldap-utils libnss-ldap libpam-ldap migrationtools

Much like Debian, we must perform an extra step to make our changes permanent.

dpkg-reconfigure slapd

Omit OpenLDAP server configuration? No
DNS domain name: your-server
Organization name: whatever
Database backend to use: HDB
Do you want the database to be removed when slapd is purged? No
Move old database? Yes
Admin password: <password>
Confirm: <password>
Allow LDAPv2 protocol: No

Now we will populate LDAP. You should probably add a temporary LDAP user for testing. After we populate LDAP we’ll remove it.

adduser test
cd /usr/share/migrationtools

Edit and replace “” with your domain and dc=padl,dc=com with dc=YOUR,dc=DOMAIN

./ > /tmp/base.ldif

./ /etc/passwd /tmp/passwd.ldif

./ /etc/group /tmp/group.ldif

Remove the top section of /tmp/base.ldif

dn: dc=dev
dc: dev
objectClass: top
objectClass: domain

Restart LDAP and add our information to LDAP

/etc/init.d/slapd restart

ldapadd -x -W -D 'cn=admin,dc=example,dc=net' < /tmp/base.ldif
ldapadd -x -W -D 'cn=admin,dc=example,dc=net' < /tmp/passwd.ldif
ldapadd -x -W -D 'cn=admin,dc=example,dc=net' < /tmp/group.ldif

To enable PAM I suggest

cd /tmp
tar xf pam.d.tar -C /etc

Alternativly, you can try the following Ubuntu specific method:

auth-client-config -t nss -p lac_ldap
pam-auth-update ldap

Please note that I was unable to change user passwords with ‘passwd’ using this method.

Remove the test user

userdel test

Set up TLS Certificate

mkdir /etc/ldap/ssl
cd /etc/ldap/ssl

openssl req -new -nodes -out req.pem -keyout key.pem
#No challenge password, leave empty
openssl rsa -in key.pem -out new.key.pem
openssl x509 -in req.pem -out ca-cert -req -signkey new.key.pem -days 9999
mv new.key.pem server.pem
cat ca-cert >> server.pem

Enable TLS on server

ldapmodify -x -D cn=admin,cn=config -W

Paste in the following:

dn: cn=config
add: olcTLSCACertificateFile
olcTLSCACertificateFile: /etc/ldap/ssl/server.pem
add: olcTLSCertificateFile
olcTLSCertificateFile: /etc/ldap/ssl/server.pem
add: olcTLSCertificateKeyFile
olcTLSCertificateKeyFile: /etc/ldap/ssl/server.pem

Press ENTER a few times to finish modifying and then Control+C when you see:

modifying entry "cn=config"

Edit /etc/default/slapd and add

SLAPD_SERVICES="ldap:/// ldaps:/// ldapi:///"

Restart slapd

/etc/init.d/slapd restart

If it fails, try:

chown -R openldap /etc/ldap/ssl
/etc/init.d/slapd restart

Client configuration

vi /etc/ldap.conf

uri ldaps://server
port 636
ssl start_tls
ssl on
tls_checkpeer no
tls_cacertfile /etc/ldap/ssl/server.pem

vi /etc/nsswitch.conf

passwd: compat ldap
group: compat ldap
shadow: compat ldap
hosts: files dns
networks: files
protocols: db files
services: db files
ethers: db files
rpc: db files
netgroup: ldap

Now test! Make sure to stop nscd if you’re using it

/etc/init.d/nscd stop


$ id test
uid=1001(test) gid=1001(test) groups=1001(test)

Remember to keep an eye on /var/log/auth.log if you run into any problems

Enable network virtio (Gigabit) in libvirt/kvm Virtual Machine Ubuntu 8.10

Posted in Issues, Networking on July 7th, 2009 by termina

If you create a domain with virt-manager, it does not always add the appropriate ‘virtio’ entry to the xml file for your VM.

If this is the case, you will notice that network speeds on the VM will not break 10/100 speeds.

To fix this, edit the xml file

vi /etc/libvirt/qemu/vm.xml

Make sure your network block looks like this (keep your MAC address the same)

<interface type='network'>
<mac address='00:16:36:0b:4c:9c'/>
<source network='default'/>
<model type='virtio'/>

Shut down the VM and confirm it’s shut down

virsh shutdown vm

# virsh list
Connecting to uri: qemu:///system
Id Name                 State

If you do not see your vm “running” you can proceed. If it’s still running you need to shut it down another way.

Update the xml definition

virsh define /etc/libvirt/qemu/vm.xml

Start the domain

virsh start vm

Log into the VM and test with a 1GB file

dd if=/dev/zero of=/tmp/test bs=1M count=1000
scp /tmp/test [email protected]:/tmp

You should see transfer speeds above 11-12 megabytes/second.

Apache2 hangs with ‘Digest: generating secret for digest authentication’

Posted in Issues, Security, Services on June 22nd, 2009 by termina

I’m running Apache2+SSL inside a libvirtd (kvm) Virtual Machine.

After enabling SSL and trying to add another SSL site, apache should refuse to restart and the following error would show up in /var/log/apache2.log

Digest: generating secret for digest authentication

After doing some research, it turns out that the VM did not have enough entropy to generate much of anything. Increasing this is easy, but may not be completely secure.

# cat /proc/sys/kernel/random/entropy_avail

# apt-get install rng-tools

# rngd -r /dev/urandom -o /dev/random

# cat /proc/sys/kernel/random/entropy_avail

After running rngd, the entropy will increase at a gradual rate.

If you want this to survive a reboot, you’ll need to put it in a startup script.

Recover from accidental mkfs using fsck

Posted in HowTo, Issues on June 13th, 2009 by termina

Recently I accidentally ran mkfs.ext3 on the wrong RAID1 array.

As soon as I realized what had happened, I shut power off from the PC.

Booting to a live CD, I ran

mdadm –assemble /dev/md0 /dev/sda1 /dev/sdb1

fsck -y /dev/md0

I was able to then mount the drive

mkdir /media/md0

mount /dev/md0 /media/md0

ls /media/md0/lost+found

And the majority of my files were saved.

Check to see if your filesystem is ext2 or ext3

mount | grep md0

If it’s ext2, convert it to ext3

umount /media/md0

tune2fs -j /dev/md0

WARNING: If you choose to run fsck manually (without -y), choosing “n” to Clear? and “y” to Fix? will cause you to lose that file.