Merge Sort in Bash

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.


#!/bin/bash

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
i=0;
unset left;
unset right;
for x in $@ ; do
if [ $i -lt $(($# / 2)) ]; then
left=$( echo $left $x );
i=$(($i + 1));
else
right=$( echo $right $x );
fi;
done;
# 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
else
echo "Usage: mrgsrt <series of numbers seperated by spaces>";
fi;
}

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} );
r=$(($r+1));
# Left half has been sorted

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

# Right half has been sorted

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

Run Levels

In Linux, you generally have run levels that range from 0-6.

0: Halt (shutdown) the system
1: Single user mode (major upgrades, maintenance, etc.)
2: Basic multi user mode
3: Full multi user mode
4: Unused (custom)
5: Multi user mode with GUI
6: Reboot

0,1 and 6 are always the same, but different distros do different things with the other run levels (for example, Debian-based systems use run level 2 for GUI and full multi-user mode)

You can see what services start at what run level by looking in the directory /etc/rc#.d where # is the run level number.

The run level number can be found in /etc/inittab (id:2:initdefault: for example)
If you were to look in /etc/rc2.d, you would see files that look like:

S99program

These are usually symbolic links to files in /etc/init.d (so a change to /etc/init.d/program would change the programs script for every run level).

Start-up scripts in Linux follow the form “start-stop” (at minimum). Many have “start-stop-restart-reload-check” or possible more.

A basic start-stop script would look like this:

#!/bin/bash
case $1 in
start)
program
;;
stop)
program
;;
esac

Don’t forget

chmod +x script

This is useful to know, especially if you are dealing with a machine that may need specific commands to be run when booting or shutting down in order to function properly (for example, in the radio station we need the client machines to run dhclient at S99 in order to obtain an IP address).

These scripts are not all run at once (by default). S##program where ## is the priority of the script.

S99 will run last, while S10 will run before most other things.

Automate Restart of D-Link DCS-900 Cameras

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.

View processes (PID) using disk I/O

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

Debian Corefiles

If you have any issues with programs segfaulting, it can be useful to allow coredumps in order to see what happened.

You first have to allow coredumps

vi /etc/security/limits.conf

*  –  core  100000

@users  –  core  0

core is measured in kbytes, and core files can be fairly large (the simple script below generates a 350kb file).  Do not set this to unlimited for regular users!

echo 1 > /proc/sys/kernel/core_uses_pid

mkdir /tmp/core

echo “/tmp/core/dump” > /proc/sys/kernel/core_pattern

ulimit -c 100000

To test it let’s create a script that will cause a coredump.

vi core_dump.sh

#!/bin/bash
#core_dump.sh
kill -s $$
#end

chmod +x core_dump.sh
./core_dump.sh

ls /tmp/cores

dump.14594 core_dump.sh

To view the corefile, you need gdb.

apt-get install gdb

gdb -c dump.13594

Easy Ubuntu Traffic Shaping

I manage a Linux router that provides internet access to tenants in an apartment building. From time to time, a user will do something that will ruin the connection.

It can be Limewire, BitTorrent or just Skype… but the end result is a latency of more than 400ms!

Recently I came across a simple way to do this on Debian/Ubuntu.

apt-get install wondershaper

The usage is simple

wondershaper eth0 4600 490

This would limit you to 4600 kbits download and 490 kbits upload.

Before you limit your speed, make sure your connection is not being heavily used and ping google.com (and a few other servers). Get a good idea of your latency (Mine is 15ms at night, and 25ms during the day).

You should find out your actual speed; I suggest speedtest.net for testing. You should also do this across several days at different times!

Let’s say you find out that you have 5800 down and 600 up. If you ping google while you’re testing your connection you are going to notice that your latency goes up.

Since you probably want to avoid this, try different values for wondershaper until your latency is a low value even when you are using all avaible bandwidth. I find that 80% of your max speed is a good value to shoot for.

I find that I can use bittorrent on multiple computers and use speedtest.net and still have a latency of around 30ms limiting a 6000/600 connection to 5000/500.

If you come across any errors when running this script (Debian has this problem for me), just comment out the line causing the error. Everything will still work.

Raid on Debian Etch

If you’d like to do some RAID 0/1 in Debian Etch with some SATA drives you can do this in only a few simple steps.

cfdisk all your drives; create your partition(s) and make the type linux-raid-autodetect (Type: FD).

mknod /dev/md0 b 9 0

mdadm –create /dev/md0 –level 0 –raid-devices=2 /dev/sda1 /dev/sdb1

You can do level 1 the same way. Keep in mind that if you do multiple md devices, change the last number to the number of the device (mknod /dev/md1 b 9 1, for example).

For RAID 5, do

mdadm –create /dev/md0 –level 5 –raid-devices=3 /dev/sda1 /dev/sdb1 /dev/sdb1

Just keep in mind that RAID 5 needs three or more drives to work.

If you’d like to add more drives to a RAID 5, you can do so easily.

mdadm –add /dev/md0 /dev/sdd1
mdadm –grow /dev/md0 –raid-devices=4

After doing this, you need to resize your filesystem on md0

apt-get install lvm2 lvm-common

pvresize /dev/md0

pvdisplay

You should now be using the full size of the array.

Now all you have to do is

mkfs.ext3 /dev/md0

Startup Scripts in Debian

If you would like to add a custom startup script to your Linux machine (for running ircd or an iptables script for example) the process is simple.

Create a file in /etc/init.d

touch /etc/init.d/program

chmod +x /etc/init.d/program

Edit it, and create something like this

#!/bin/bash

case $1 in

start)

sudo -u irc /home/ircd/unreal start

;;

stop)

sudo -u irc /home/ircd/unreal stop

;;

esac

These scripts are run as root, so you should probably use sudo to run programs as unprivileged users.

Now we just have to add it to our default runlevel (runlevel can be found in /etc/inittab on Debian, in Ubuntu this file does not exist as far as I know). The runlevel should be the same across all Debian (including ubuntu) systems.

ln -s /etc/init.d/program /etc/rc2.d/S20program

The S20 requires a little bit of explanation. S means Start, and 20 means to run after the 19’s but before the 21+’s. It’s simply a priority system.  You can replace S with K to ‘stop’ instead of ‘start’ when the computer shuts down.

tcpwrappers

TCP wrappers are one of Linux’s most useful built-in features.

Instead of using a complex set of firewall rules, tcpwrappers provides an easy method of restricting access to certain daemons using ip addresses, host names, and ranges. While I wouldn’t reccommend on relying soley on them, they are a great tool for workstations and other machines behind a firewall.

hosts.deny is checked first; then hosts.allow. By default, if a program is not listed in either it is granted access to everyone.

/etc/hosts.deny

sshd: ALL
ftpd: ALL
mountd: ALL

/etc/hosts.allow

sshd: 192.168.0.0/24
ftpd: 192.168.1.0/255.255.255.0
mountd: 192.168.5.2,server2,192.168.3.2,192.168.6.0/24

As you can see, you have several different ways to give (or prevent) access.

Generally any program you see running as rpc.program will be supported via tcpwrappers (use program, not rpc.program in hosts.*). Anything running from inetd.conf will also be supported.

Stand-alone services (ignoring SSH/FTP) will generally not work with this, and rely on the program denying access or iptables.

Even if you use iptables, have some service: ALL lines in /etc/hosts.deny can be useful if you ever have problems with iptables