Thinking Recursively
One of the most important programming constructs that can be learned is recursive programming. To most, it's a mystery. To some it's a source of endless frustration. However, once recursion is mastered, many other data structures become relatively easy.
So, what exactly is recursion? Put simply, recursion is the process of taking a larger problem and breaking it down into smaller problems that are each solved in the exact same way. In recursive programming, you first establish a base case or stopping case (I prefer to call it an "escape clause"). It is this base case that prevents your program from recursively calling itself to infinity (that's not necessarily true I suppose. The computer would eventually crash due to the exhaustion of memory). Once a base case is established, recursive calls are created, and they're usually conditional (if/else).
Before we get into code, let's illustrate recursion with a simple real life example: climbing a stair case. The larger problem is getting up (or maybe down) a flight of stairs. It can be broken down into many smaller similar problems - walking up steps. Think about it: to reach the end of the stair case, you have to take a step. This process is repeated until you reach the base/stopping case. So, what's the base/stopping case? If you said, "when I reach the top/bottom of the stairs", you're starting to think recursively! Another example could be tracing your family tree. What is the larger problem to solve? What is the base case? What are the recursive steps? Think about these for a moment...
Now that you're back, let's get into some code. We'll start with a simple example: calculating the factorial of a number (known colloquially as the "hello world" of recursion). As a reminder, you calculate a factorial of a number by multiplying the number by one less than the number. You then take the number that was decremented and multiply it times one less than that number. The process is repeated until you reach zero, in which case you can no longer calculate the factorial. As an example, to calculate the factorial of 3: (3*2*1). My code is in C, though you could use any language that supports recursive function calls.
unsigned factorial(unsigned number)
{
if(number == 0)
return 1;
return number * factorial(number-1);
}
The function takes an unsigned integer as its argument. The first line in the function body is the base case. If the number is equal to zero, there is no more work to be done so a 1 is returned and the function ceases to recursively call itself. Notice this code is at the top of the function. The return call does all the work. It multiplies the current number by what appears to be a function call! In reality, it's doing what you'd expect in order to calculate a factorial, although it's probably confusing at first. Let's trace the function in order to see exactly what happens.
We'll use the number 4 as input.
1. To begin, 4 is passed into the function. It is not equal to zero so the line of code with "return" is reached and factorial() is called on "number-1" or 3.
2. The number 3 is not equal to zero, so the return line is called once again, this time with an argument of 2.
3. The number 2 is not equal to zero, so the return line is called again, this time with an argument of 1.
4. The number 1 is not equal to zero. Yep, the return line is called again and factorial is passed zero as an argument.
5. The number zero is equal to zero. A-ha! We've hit our stopping case, but where do we go from here? The next line of code with "return 1" is executed. But where do we return to? Just like any other function, we return to whatever called us. In this case, it was the previous instance of factorial() in step 4. We return there and multiply 1 times the result of what was returned from the stopping case, or 1.
6. With that, the cascade of returns ensues... We now return to step 3 and multiply 2 times 1 and return that to step 2.
7. The number 3 in step 2 is multiplied with the 2 that was returned from step 3. The result, 6, is returned to step 1.
8. The number 6 from step 2 is multiplied with 4 and returned to the function that made the original call to factorial(), likely a printf() call. That's it!
Though there are many steps in recursion, they all do very simple things. In this case a comparison is made with the argument to the factorial function to see if it's equal to zero. If it is, the function returns with no further recursive calls.
So what exactly is the benefit of all this? The first benefit is simpler code. You could write the factorial code using a for loop or while loop but you'd write more code than doing it recursively. A second benefit is that the code is simpler and easier to follow (assuming you understand recursion!). A third benefit is that more complex data structures such as trees and heaps are all but impossible without recursion. Recursion isn't beneficial everywhere though. If you're working with large amounts of data, it may well be faster to use iterative loops such as a for loop over recursion, due to the need to put data on the stack for each recursive call. It's up to you to decide.
As a parting exercise, see if you can figure out what this code does:
void write_binary(int n)
{
if (n == 0 || n == 1)
printf("%d", n);
else
{
write_binary(n/2);
printf("%d", n % 2);
}
}
Using sshfs on FreeBSD
Yep, been a while since I've last posted something (actually this would be the first thing I've posted in 2011), but indispensable utilities like this one motivate me to post more often.
sshfs is part of the FUSE project for implementing file systems in userspace. A file system is typically run in kernel space, both because it gets more tightly integrated with the kernel and it becomes more transparent to the user. Running a file system in userspace alongside applications is a fairly new concept but it works surpringly well.
sshfs is easily installed from the ports system:
cd /usr/ports/sysutils/fusefs-sshfs; sudo make config-recursive; sudo make install clean
is all that's needed. With that step completed, enable mounting file systems devices as a normal user:
#sysctl vfs.usermount=1
I recommend sticking that in /etc/sysctl.conf (omitting the sysctl : ) to make it permanent . Lastly, add 'fusefs_enable="YES"' to your /etc/rc.conf and run /usr/local/etc/rc.d/fusefs start to load the fusefs kernel module that was built with the port.
In order to mount remote machines over ssh, you'll use the sshfs utility. I highly recommend setting up password-less ssh login using a public/private key pair. A simple Google search will show you how that's done. As a first example of mounting a remote server (don't try to mount something from your local machine. weirdness will ensue.), use the following:
%sshfs remotebox: local_dir
Notice the colon after the remote machine. By default, sshfs will try to mount your home directory on the remote server as the local_dir. You can specify any paths your user would normally have access to:
%sshfs remotebox:/usr/src local_dir
The command above would mount the /usr/src directory on the remote machine as /usr/home/<your user>/local_dir. To unmount a directory, the documentation states that you should use fusermount -u <mountpoint> but I was perfectly ok using the normal umount command. To keep the mountpoint available, it's worth adding a keepalive to your ssh client configuration. Simply add something like ServerAliveInterval 5 to your ~/.ssh/config file to send keepalives every 5 seconds to the server.
Enjoy!
The perfect Open Source laptop
I'm a huge fan of FreeBSD. So much so that all my systems are running the latest version (8.1 as of this writing). Many of my blog posts are about FreeBSD or mention it in some way. So maybe that's why it bothers me to say this: FreeBSD just isn't well suited for a portable computer. I've fought it for some time and come to the conclusion that Linux just works better on laptops. A few of my gripes:
- Non-journaled filesystems suck. Using UFS + soft-updates helps but can be tedious on large drives. I think journaling + soft-updates is coming in 9.0 so maybe the level of suck will be less. Nonetheless, having to fsck a drive is an idea whose time has passed.
- ZFS kicks major butt but really needs a 64-bit CPU plus several gigs of memory, which leaves older laptops like mine out to dry. I can't get it to work as a root filesystem on any of my portable systems. I get a kernel panic on my i386 machines and the boot loader doesn't properly recognize my drives on my lone amd64 laptop.
- There's no good wireless manager for any of the BSDs. Linux has one called Wicd. It works with anything you throw at it, including WAPs that require an SSL certificate. You can do most of that in FreeBSD but it requires you to edit several config files. Try changing between locations that use different SSIDs or different encryption. Wicd continues to just work without needing to change any configs, even with the built in ncurses interface. Wicd is heavily tied to Linux (it makes use of the Linux proc filesystem) so porting it would basically require a rewrite.
- For some reason, Xorg seems to be hit or miss, driver-wise. It frequently hard locks on one of my systems with a Radeon but not another with a newer Radeon. I've never seen a lock up using the proprietary Nvidia drivers but the Nouveou drivers don't support 3D acceleration on all cards. I realize that most of the Xorg stuff is the same between BSD and Linux so that begs the question of why I see this on BSD but not Linux?
FreeBSD is rock solid on my desktop machines and ZFS on the root file system is a dream, so it's a bit disheartening that that experience didn't carry over to laptop-land. So, after dealing with the above annoyances I decided to throw my favorite Linux distribution on my laptops: Gentoo.
I wrote about Gentoo some time ago, ironically because I was critical of some things I needed in FreeBSD before I made the switch. Gentoo is unlike every Linux distribution out there (except the Linux From Scratch project) in that you have to build it in order to use it. This can be a serious turn off for folks that just want to install and get on with life, but I find it very intriguing and a great way to understand Linux at a much deeper level. The same idea holds when you want to install software; instead of prepackaged archives, you build it from source. This process is made easier with the Portage software management system, but you can tweak a near limitless amount of things to get exactly the kind of system you want. No bloat, no muss, no fuss.
With Gentoo installed, your next step to laptop bliss is to install Wicd to manage both your wired and your wireless interface (assuming you have one). Wicd is in the base Portage system, and assuming you chose the "desktop" Portage profile, installing Wicd should install a bunch of stuff. If you followed the Gentoo installation documentation, you probably added one or more of your Ethernet interfaces to your init scripts. Delete the net.eth scripts, but leave the net.lo script for the loopback interface. Add wicd to your init scripts by using 'rc-update add wicd default'. This ensures the wicd daemon starts so you can connect to networks. Since you don't have Xorg installed, you can use the ncurses interface by typing wicd-curses. Check out the man page for wicd for more details.
Next up is getting Xorg installed. This can take a while, but it basically involves specifying your video card type and input method (typically evdev on modern versions of the Linux kernel) in the /etc/make.conf file. Building Xorg will likely take quite a while so now might be a good time to catch up on your bash.org quotes. Make sure you get hald and dbus started and added to your init scripts when the build completes.
With the X server built, we're in the home stretch. The next thing to install is some sort of desktop environment like Gnome or KDE, or my preference, a simple window manager. You are, of course, free to install whatever tickles your fancy but for all my portable systems, nothing, and I mean NOTHING, beats StumpWM for a window manager. StumpWM is a rewrite of the Ratpoison window manager in Common Lisp. Ratpoison is heavily inspired by GNU Screen, so if you're an avid screen user, you'll feel right at home with both Ratpoison and StumpWM. Let me give you a few reasons why I think you should give one of these window managers a try before you go kicking and screaming back to Gnome or KDE.
- First and foremost, they're keyboard-driven. You're on a laptop, probably with an annoying touch pad or worse, the little pencil eraser pointer-thingy. Why would you inflict that kind of pain on yourself when you'll be far more productive if you could just keep your fingers on the keyboard?
- Ever fly commercial? Ever get stuck in coach next to someone that doesn't know the meaning of personal space? Good luck using an external mouse when you're crammed in like a sardine at 60,000 feet.
- If you write code for a living or even just as a hobby (you weirdo
), your brain will appreciate not having to break concentration to reach for a mouse when you need to switch between terminals or editors. - They automatically maximize windows for you. You can see everything without needing to get a window sized just right with the mouse. You can, of course resize windows and split them as needed.
- Pretty much anything you can do on a laptop would be enhanced by a window manager that is keyboard controlled.
With all the above in mind, you'll want to pick either Ratpoison or StumpWM to use. Ratpoison is written in C, uses minuscule amounts of memory, and is easily installed using the 'emerge' command. StumpWM is written in Common Lisp, so you'll need to install that first. If hearing the word Lisp sounds vaguely familiar, it should be. Lots of other open source software is written in Lisp or uses it, such as Emacs and The Gimp. Some closed source software uses Lisp as well.
To get a Lisp interpreter, you'll want to install either the CLISP interpreter or the SBCL interpreter. I highly recommend you install SBCL instead of CLISP. Add the following to your '/etc/portage/package.use' file (you may need to create the /etc/portage directory and the package.use file if they don't exist):
media-libs/gd fontconfig dev-lisp/sbcl doc
Next, add the following to your '/etc/portage/package.keywords' file:
x11-wm/stumpwm ~x86
Your USE flags in '/etc/make.conf' should look at minimum like the following:
USE="sbcl -qt4 -kde X dbus hal -cups"
This should get you a working install of StumpWM but the version in Portage is pretty old and looks like it hasn't been touched in some time. Plus it doesn't even compile a StumpWM binary for you! Instead, you should use the version in the Git repository. In addition to making the changes above, emerge the following ports like so:
sudo emerge -av cl-clx cl-ppcre autoconf
You may need to install Git in order to grab the StumpWM source. Grab the StumpWM source like so:
git clone git://git.savannah.nongnu.org/stumpwm.git
I generally just keep the StumpWM source in my home directory. It doesn't take much space at all and there are several goodies in there. Go into that directory now and type "autoconf". Once that completes, type "./configure" You should see a lot of messages whizz by. Make sure the output of the configure script shows you're using SBCL. Once that completes, type "make". That should actually compile the StumpWM and Stumpish (Stumpish is a "shell" to StumpWM) binaries for you. Once that completes, you should have a StumpWM binary in your ~/stumpwm folder and a Stumpish binary in your ~/stumpwm/contrib folder. Copy both to /usr/local/bin as root. I tried adding my ~/stumpwm folder to my PATH and running it that way but it just doesn't work right, so installing both to /usr/local/bin is the way to go.
With a fresh copy of StumpWM built, add it to your .xinitrc: "echo 'exec stumpwm' >> ~/.xinitrc" and fire up a startx! You should see a welcome message. If you do, congrats! If not, you may want to try the StumpWM wiki.
Below is my .stumpwmrc file for you to pick apart and customize for your own needs:
;; My key bindings
(in-package stumpwm)
(define-key stumpwm:*top-map* (stumpwm:kbd "F12") "mode-line")
;; switching window
(define-key stumpwm:*top-map* (stumpwm:kbd "M-Up") "pull-hidden-previous")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-Down") "pull-hidden-next")
;; switching frames
(define-key *top-map* (kbd "M-Page_Down") "fnext")
;; switching groups
(define-key stumpwm:*top-map* (stumpwm:kbd "M-Left") "gprev")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-Right") "gnext")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-F1") "gselect 1")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-F2") "gselect 2")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-F3") "gselect 3")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-F4") "gselect 4")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-F5") "gselect 5")
;; splits
(define-key stumpwm:*top-map* (stumpwm:kbd "M-s") "vsplit")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-S") "hsplit")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-q") "only")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-r") "remove")
;; programs
(define-key stumpwm:*top-map* (stumpwm:kbd "M-c") "exec xfce4-terminal")
(define-key stumpwm:*top-map* (stumpwm:kbd "M-F") "exec firefox-2")
;; mouse
(setf *mouse-focus-policy* :sloppy)
;; prefix key
(set-prefix-key (kbd "Pause"))
;; wallpaper
;; (stumpwm:run-shell-command "display -window root '/home/<USER>/backgrounds/someimage.jpg'")
(stumpwm:run-shell-command "fbsetbg -l")
;; ff command
(define-stumpwm-command "firefox" ()
"Run or switch to firefox."
(run-or-raise "firefox" '(:class "Firefox")))
(define-key *root-map* (kbd "w") "firefox")
;; Multimedia Keys
(load "/home/<USER>/.stumpwm/multimedia-keys.lisp")
; Brightness Adjust (Fn + Up/Down)
(run-shell-command "xmodmap -e \'keycode 212 = XF86LaunchE'")
(run-shell-command "xmodmap -e \'keycode 101 = XF86LaunchD'")
(define-key stumpwm:*top-map* (stumpwm:kbd "XF86LaunchE") "exec brightness +")
(define-key stumpwm:*top-map* (stumpwm:kbd "XF86LaunchD") "exec brightness -")
;; Load Mode line
;; (load "/home/<USER>/.stumpwm/modeline-config.lisp")
(toggle-mode-line (current-screen) (current-head))
;; show the time in the mode-line
(setf *screen-mode-line-format*
(list '(:eval (run-shell-command "date '+%R, %F %a'|tr -d [:cntrl:]" t)) " | [^B%n^b] %W"))
;; Modeline Group Scrolling
(setf stumpwm:*mode-line-click-hook*
(list (lambda (&rest args)
(cond ((eq (second args) 5)
(run-commands "gnext"))
((eq (second args) 4)
(run-commands "gprev"))))))
;; Theming
;; (load "/home/<USER>/.stumpwm/effects.lisp")
;; Male's code for key sequence display
(defun key-press-hook (key key-seq cmd)
(declare (ignore key))
(unless (eq *top-map* *resize-map*)
(let ((*message-window-gravity* :bottom-right))
(message "Keys sequence: ~A" (print-key-seq (reverse key-seq))))
(when (stringp cmd)
;; Give 'em time to read it.
(sleep 0))))
(defmacro replace-hook (hook fn)
`(remove-hook ,hook ,fn)
`(add-hook ,hook ,fn))
(replace-hook *key-press-hook* 'key-press-hook)
Feel free to use what you can and look around for anything I missed. It'll take a bit of getting used to, but once you do, using a keyboard driven, tiling window manager on your laptop becomes second nature and you wonder how you went without it. For a great video introduction to StumpWM, go here. Enjoy!
Using two screens in FreeBSD 8 with an Nvidia graphics card
So I finally made the jump to a multiple monitor setup, and boy is it NICE! I've been using a dual screen setup at work for several years and found that it really does boost productivity. I had previously been using a single Apple 23" HD display I bought in 2004 when I bought a PowerMac G5. While I was a little apprehensive at first, it turns out that configuring a dual screen setup in FreeBSD is really quite simple.
First, you'll need to physically set your monitors up, including placing them on your desk and running the power and video cables. For video, you really will want to use at least DVI. VGA just doesn't cut it these days, both in terms of clarity and resolution. Fortunately, just about any display you can buy these days has a DVI connector (most have both VGA and DVI). Don't skimp on monitors either. You do have to look at them for some period of time so you'll want something with a good contrast ratio and response rate. I managed to snag two Samsung SyncMaster 2243 22" LCD monitors for $179 a piece at Microcenter (marked down from $219 a piece). I don't recommend going above this size if you sit close to your screens (and most of us do) because you may end up straining your eyes with very large displays. Also, don't just line the screens up side by side either. You'll want to have a somewhat concave layout so it feels more natural to your eyes and brain. I set my screens so that they meet in the middle of my desk and then a tilt them inward a few inches where they meet. Do this by lightly pushing against the place where the bezels meet with your thumb. You may need to adjust the pitch and tilt of the screens afterward to get the bezels properly lined up. With that done, connect the power and video cables. If you are connecting new screens to your system while you are already in your window manager, I would highly recommend powering down your system. I tried a warm reboot on mine after attaching the screens and was greeted by a kernel crash.
When your system boots, you might be greeted with a clone display (same picture on both monitors) or you may see output on just one screen. I'm no expert on Nvidia graphics cards, so I can't tell you what to expect for a given card. For my setup, I've got a Nvidia GeForce 9500GT. It's a low end card by today's standards for sure, but I don't do much gaming at all, so it meets my needs. Depending upon your setup, you may be greeted by either a display manager (Gnome Display Manager, etc...) or just a login prompt. I prefer to keep it simple and shun a display manager for the comfort of a black screen and a login prompt.
Once logged in, you'll need a shell, so open a terminal if you're in a window manager. Most users of Xorg these days can get by without a configuration file since Xorg is much better at configuring hardware on its own these days. If you have a static Xorg configuration and have your resolution hard coded, you may see nothing but gibberish. You can either reboot into single user mode and move your configuration file to a backup or just reattach your old screen. Personally, I never specify a resolution since Xorg gets it right anyways. If you do not have an Xorg config, su to root and use the following command to generate one:
# Xorg -configure
This should dump a file called xorg.conf.new in root's home directory. Open that file up in your favorite editor. Under the Device section, add the following line:
Option "TwinView"
Here's what my Device section looks like:
Section "Device" Identifier "Card0" Driver "nvidia" VendorName "nVidia Corporation" BoardName "G96 [GeForce 9500 GT]" BusID "PCI:1:0:0" Option "TwinView" EndSection
Next, look for the Screen section. Under that will be several subsections named Display that are used for different color depths. In each of these, we need to add the Virtual directive. The parameters will be different depending on your screen resolution. Since my two screens are capable of a resolution of 1680x1050, I simply double my width parameter to 3360 (we want to span the width of the desktop across the two screens, remember?) to get a Virtual directive of "Virtual 3360 1050". Here's what it looks like for 24 bit depth:
SubSection "Display"
Virtual 3360 1050
Viewport 0 0
Depth 24
EndSubSection
With both the TwinView option and the Virtual directive added, copy the configuration over to /etc/X11/ as just xorg.conf. You should be able to restart X or start it up if you're not using a display manager. You should see one gigantic screen! If not, check your settings. You may need to use Xrandr. It gets installed by default with the xorg-apps port. If you don't have the xrandr command, you may need to rebuild that port with the Xrandr option enabled. You can test it out by typing "xrandr" at a terminal prompt. You should see a good amount of output including your two display connectors (probably DVI0 and DVI1 or some variation), as well as the supported resolutions. If you do, try the following command:
% xrandr --output DVI1 --right-of DVI0
If you see a single large desktop, congratulations! You'll want to add the above command to your startup. This is usually at the top of the xinitrc file for non-GDM users or xsessions for GDM users.
Enjoy your added productivity and enormous desktop!
Installing the Kismet wireless scanner on Gentoo Linux on a Thinkpad T40
Kismet is a very handy wireless scanning and capture program. Unlike programs such as Netstumbler, Kismet allows you to capture wireless traffic. This could, of course, be used for both good and evil, so I leave it up to you to do what you will.
Kismet is in Portage, but it lags a bit behind the current version (2008.05 is in Portage and 2010.07R1 is the latest as of this writing). You should be able to get the latest version by using an overlay, but I'm not keen on using overlay software unless I really need the bleeding edge. Use portage to install Kismet:
%sudo emerge -av net-wireless/kismet
Once installed, you'll need to modify the config file before you begin scanning. Open /etc/kismet.conf in your favorite text editor and add your login to the 'suidsuser' variable. There are quite a few options to configure, but the one you must configure is a capture source. For our needs, change the 'source=' line to the following:
source=ipw2100,eth1,ipw
I suppose this would work for most of the older IPW2100-based Centrino notebooks since the Centrino chipset is the same. Save the config and exit. You should be able to type 'kismet' at a terminal and have the client and server automatically start. If this doesn't work, you may have to manually change the kismet server to set uid. Do the following:
%sudo chmod +s /usr/bin/kismet_server
Try launching the program again. If you see a text based interface and some SSIDs, you're good to go! If not, you may have to fiddle with your settings a bit more. Either way, happy scanning!
Using the Dvorak layout in FreeBSD
Those of us that type a lot will eventually begin to feel the effects of such an activity manifest as some sort of pain, most likely carpal tunnel syndrome. As somebody who has touch typed for the better part of 15 years, I definitely feel the effects every now and then. Several years ago I heard of an alternate keyboard layout called "Dvorak" that allegedly helped reduce the stress on your hands, but could potentially give you a free speed boost. I won't go into the nitty-gritty details, but encourage you to take a look at the Wikipedia article.
There are two ways to use the Dvorak layout: in the console and in Xorg. They're both quite easy to switch to as well.
To switch over your console, you can either run the sysinstall program as root or just manually specify the keymap using kbdcontrol -l "us.dvorak". Using sysinstall ensures that the Dvorak layout is retained after a reboot, whereas the kbdcontrol command does not. Switching back is as simple as using kbdcontrol -l "us" and removing the entry from rc.conf if you used sysinstall.
For Xorg users, simply open a terminal and run the following to toggle back and forth:
setxkbmap dvorak setxkbmap us
If you are using a desktop environment such as Gnome or KDE, you should be able to change the layout using the appropriate control panel.
I hope to work my way up to my QWERTY speed fairly quickly and be proficient in both layouts, but I'll certainly need to practice. For the record, this post took about 40 minutes to compose with my layout switched to Dvorak...
Configuring a 6in4 tunnel on the pfSense firewall
If you've read my article on connecting to the IPv6 Internet, you should be familiar with the principles of IPv6 over IPv4 connectivity and have some basic IPv6 knowledge.
I've wanted to use IPv6 with my pfSense firewall for quite some time but it seems that the developers don't want to be bothered supporting it. Fear not! There is a way to get IPv6 connectivity, though it won't work through the GUI.
I won't go into a great amount of detail on configuring your end PCs for IPv6 connectivity except to say that it's generally turned on by default for Linux, you need to add "ipv6_enable" and reboot for FreeBSD, and that you need to add the IPV6 protocol in Windows XP (newer versions have it enabled by default). From that point on, your computer should send out solicitation messages which your pfSense firewall will respond to and you'll get allocated an IPv6 address.
For the remainder of this article, I'm using this article (cached version here) for my template. That article is intended for native IPv6 connectivity, not tunneled connectivity. Also note that you should have configured an IPv6 over IPv4 tunnel. I suggest using a provider such as Hurricane Electric. Lastly, once you have a tunnel configured, you'll want to allow pings from the tunnel's endpoint to your router so it knows your side is up. I enabled this by going to Firewall/Rules and adding a ping rule that allows only the IPv4 tunnel endpoint to ping your firewall's external IP. Use ICMP, then Any ICMP type, then specify the host IP of the remote tunnel endpoint. Don't forget to apply it!
For your pfSense box, you'll want to be running the latest release (1.2.3-RELEASE as of this writing). Be sure to enable SSH from the web gui since you'll need to log into the command line. For your tunnel settings, I'll assume the following addresses:
- WAN IPv6 IP: 2001:db8:0:1::2
- WAN IPv4 IP: 192.0.2.2
- WAN IPv4 Tunnel Destination: 192.0.2.15
- LAN IPv6 allocation: 2001:db8:0:2::/64
Log into your firewall using the credentials you configured when you first set it up. At the menu, use option 8 to drop to a shell. Next, create the following file:
#!/bin/sh # IFOUT = outside interface # IFIN = inside interface # DFGW = default gateway IFOUT="gif0" IFIN="bge0" DFGW="2001:db8:0:1::1" ####### Configure the stuff # Configure the interfaces ifconfig $IFOUT create ifconfig $IFOUT tunnel 192.0.2.2 192.0.2.15 ifconfig $IFOUT inet6 2001:db8:0:1::2 prefixlen 64 route -n add -inet6 default 2001:db8:0:1::1 ifconfig $IFOUT up ifconfig $IFIN inet6 alias 2001:db8:0:2::1 prefixlen 64 # Set the default route route -n add -inet6 default $DFGW # Configure IPv6 forwarding sysctl net.inet6.ip6.forwarding=1 # My /etc/rtadvd.conf looks like this # # bce1:\ # :addrs#1:addr="2001:db8:0:2::":prefixlen#64:tc=ether: # # Startup rtadvd /usr/sbin/rtadvd -d -D -c /etc/rtadvd.conf $IFIN
Save this file as 00_config-ipv6-if.sh under /usr/local/etc/rc.d/ so it will automatically be executed upon reboot and change the permissions to 755 so it has permissions to execute. Don't forget to change the inside interface to the name of your interface.
Next we need to configure the pf firewall to allow the tunnel to work. Create a file with the following contents:
#!/bin/sh
#
# IFOUT = outside interface
# IFIN = inside interface
# DFGW = default gateway
IFOUT="gif0"
IFIN="bge0"
####### Configure the stuff
# Configure PF
# pfSense puts it's rules in /tmp/rules.debug for debugging purposes after boot
# We will use these rules, add IPv6 additions, read the config with pfctl and
# disable and enable PF
cat /tmp/rules.debug | sed "/User-defined rules follow/{
p;s/.*/\
pass in quick on $IFIN inet6 from any to any\\
pass out quick on $IFIN inet6 from any to any\\
pass out quick on $IFOUT inet6 from any to any\\
pass quick proto ipv6-icmp from any to any\\
# pass in on $IFOUT inet6 proto tcp from any to any port 22\\
/;}" > /tmp/rules.config-ipv6.txt
# Read the new PF configuration file
pfctl -f /tmp/rules.config-ipv6.txt
pfctl -d; pfctl -e
Save this file as 10_config-ipv6-pf.sh under /usr/local/etc/rc.d/ and chmod it to 755 so it can execute on startup.
Lastly, create /etc/rtadvd.conf and add the following to it:
bge1:\ :addrs#1:addr="2001:db8:0:2::":prefixlen#64:tc=ether:
Save that file. At this point you can either reboot your pfSense box or execute the two scripts. You should have IPv6 connectivity through your tunnel. You can test it using traceroute6 and ping6. Another great test to try is to go to http://ipv6.google.com. If the logo bounces, you have IPv6 connectivity.
Enjoy!
Updating a ZFS on Root installation in FreeBSD 8
Ever since ZFS became production ready on FreeBSD 8 (and backported to 7), I've been itching to switch to using it and getting rid of UFS. For one, UFS is OLD. It was first used in 4.2BSD if that gives any indication. The most salient problem with UFS is the lack of real journaling. True, you have the soft-updates feature, but soft-updates are an alternative to journaling. This may not be a problem for users with older hardware and smaller hard disks, but with today's multi-terabyte drives, a power failure or system crash can lead to painfully long waits as fsck verifies the consistency of your file system.
To that end, I followed this handy guide to installing a FreeBSD system on a pure ZFS-only setup. Note that you'll end up with a system with no traces of UFS whatsoever, meaning you have to use the ZFS bootloader and can't dual boot anymore. If that's not to your liking, have a look at the index of ZFS on root guides. If you need to dual boot, you'll want to follow one of the MBR guides. For my needs, if I find myself needing to boot to another operating system, I simply hit F12 when my system is performing a POST test and choose a different drive to boot to. It's simple and separates your operating systems so they don't affect one another. Another alternative is to use virtualization if your needs aren't too demanding.
One thing none of the ZFS on root guides show you is also one of the most important: how to update and rebuild your system! If you're a developer you probably already know how to do this, but for the rest of us, it's important to know how to properly update your system when needed.
To begin, you'll want to sync your source tree. Instructions for that are located in the handbook, but it really boils down to using csup to synchronize source from a cvsup server to your local machine. If you do anything that requires building a kernel module, you're probably familiar with this. With your source tree synchronized to your desired version of FreeBSD, you can follow the the handbook guide to rebuilding world.
Once you have installed the kernel, reboot into single user mode as the guide tells you. Issue the "mount" command. You'll notice that no filesystems are mounted except for devfs and the root ZFS filesystem you marked as legacy. The handbook tells you to use "mount -a -t ufs" but obviously this won't work since we have banished UFS from our FreeBSD box. To mount all the ZFS mountpoints you have, simply use "zfs mount -a". This should mount everything except for / (root) as read-write. To enable a writable file system root, use "mount -uw /" and then "mount -a" to mount anything else. The "-uw" option unsets any mount options and then sets the write bit so you can write to that mount point. At this point you should be able to use mergmaster and installworld to finish rebuilding your system. One important task you must do before rebooting into your updated system is to install updated boot code. This is done with the following command after installing the new world: "gpart bootcode -b /boot/pmbr -p /boot/gptzfsboot -i 1 disk" where disk is the name of the drive you installed to (usually ad0). With this, you should have an updated system with ZFS as your file system!
Enjoy!
Fun with numbers…
So I'm neck deep in my GRE studies. I've already gone through two GRE books and an ebook. I'm close to finishing my third book (this test is NOT easy). I'm learning some interesting properties of numbers such as the following:
Integers:
- Integers are whole numbers (whether positive or negative)
- Fractions are not integers
- Zero is an integer!
- Positive integers get larger as they move farther from zero
- Negative integers get smaller as they move farther from zero
Consecutive numbers:
- Listed in order of increasing value without any numbers missing between them
- Fractions and decimals cannot be consecutive numbers; only integers can!
- You can even have consecutive even integers: 2, 4, 6, 8...
Properties of Zero:
- 0 is even
- 0 plus any other number is equal to that number
- 0 multiplied by any other number is equal to 0.
Positives and Negatives:
- pos x pos = pos
- neg x neg = pos ("two wrongs make a right" is my memorization tool)
- pos x neg = neg
Even or odd?
- Any number that can be cleanly divided by 2 is even (i.e. no remainder)
- Any number that cannot be cleanly divided by 2 is odd (i.e. has a remainder)
- Zero is even
- Fractions are neither even nor odd
- Any integer is even if its units digit is even, and odd if its units digit is odd
- Multiplying and adding odd and even integers
- even x even = even
- odd x odd = odd
- even x odd = even
- even + even = even
- odd + odd = even
- even + odd = odd
Absolute Value:
- Absolute value is how far away a number is from zero
- Absolute value is always a positive integer whether or not the number in question is positive or not
Prime Numbers:
- A number is prime when it is only divisible by itself and the number 1
- Here's all the prime numbers less than 30: 2,3,5,7,11,13,17,19,23,29
- Zero is not a prime number
- 1 is not a prime number
- 2 is the only even prime number
- Prime numbers are always positive integers. There's no such thing as a negative prime number
Rules of Divisibility:
- An integer is divisible by 2 if its units digit is divisible by 2. For example, 598,447,896 is divisible by 2 because the units digit (6) is divisible by 2.
- An integer is divisible by 3 if the sum of its digits is divisible by 3. For example, 2,145 is divisible by 3 because (2+1+4+5 = 12) is divisible by 3.
- An integer is divisible by 4 if its last 2 digits form a number that's divisible by 4. For example, 712 is divisible by 4 because 12 is divisible by 4.
- An integer is divisible by 5 if its units digit is either 0 or 5
- An integer is divisible by 6 if it's divisible by both 2 and 3
- An integer is divisible by 9 if the sum of its digits is divisible by 9
- An integer is divisible by 10 if its units digit is 0
Remainders:
- When one integer cannot be divided evenly by another, the remainder is what is left over after the division
- When one integer divides evenly by another the remainder is zero (no remainder)
Factors:
- A number is a factor of another number if the second number can be divided by the first with no remainder
- Factors of 12: 1,2,3,4,6,12
- Best to write factors in pairs to make sure you get them all:
- 1 and 12
- 2 and 6
- 3 and 4
Multiples:
- A multiple of a number is that number multiplied by an integer
- Multiples of 10: -20 (10 x -2), -10 (10 x -1), 10 (10 x 1), 20 (10 x 2), etc...
There's obviously far more to the GRE than these simple concepts but some are quite handy and will make short work of doing calculations for the GRE. Yea, you can't use a calculator at all. Fire up those neurons!
Configuring wireless networking on a Thinkpad T40 on FreeBSD 8
I've been happily using FreeBSD 7.2 on my IBM Thinkpad T40 and decided it was time to upgrade to the latest and greatest: FreeBSD 8. FreeBSD 8.0 brings many changes to the base system, but one of the more significant ones is the configuration of wireless (802.11) networking. After a bit of mucking around, I've figured out some interesting things that relate to wireless, especially on the Thinkpad T40.
The biggest change is that you no longer configure the physical device interface. That is, no more "ifconfig_" where interface is either ath or ipw or some variation. Instead, you create a pseudo-interface, map it to the physical interface, and from there, configure your IP settings on the pseudo interface.
Another important point is the the existing ipw2100 driver that the Thinkpad relies on is horribly broken in FreeBSD 8. This means we'll have to configure the interface using NDIS instead. Don't worry though, it's not that difficult.
To begin, go to the Lenovo website and download the wireless drivers. There are several there, so be sure to grab the one for the Intel 2100 802.11b wireless interface. The filename should be 1rwc89ww.exe. Unfortunately, you'll need a nearby Windows machine to decompress the executable. Alternatively, you could probably download the same driver from Intel's website directly, but it's likely to be a self-extracting executable as well. Regardless of which method you use to obtain the driver, the two files we're interested in are named W70N501.INF and W70N51.SYS. The first file describes how to install the driver on a Windows computer and the second file is the actual driver itself.
Next, we need to convert the Windows driver to a kernel module that FreeBSD understands. To do this, go to the directory containing the two files mentioned above and type "% ndisgen W70N501.INF W70N51.SYS". From here, the ndisgen utility will prompt you for a few questions. Just continue to keep hitting enter. Note that you'll want to have a source tree on your system that is in sync with your kernel so ndisgen is able to build a kernel module. Consult the FreeBSD handbook in order to learn how to synchronize a source tree to your system. When finished, you should see a new file named W70N51_SYS.ko in your directory. Copy this file to the /boot/modules directory. You might even convert it to lower case to make things easier.
Now that we have a suitable driver in place, we need to load up the ndis API. To do this, type "sudo kldload if_ndis" and "sudo kldload ndis". To load our fancy new driver, type "sudo kldload W70N51_SYS" (or the lower case equivalent if you changed case). We're now ready to configure IP addressing.
I'll take the simplest use case and assume you're using WPA authentication and getting an IP address via DHCP. Add the following lines to /etc/rc.conf
#Wireless
wlans_ndis0="wlan0"
ifconfig_wlan0="WPA DHCP"
The first line incorporates the new wireless interface in FreeBSD 8. It creates a "wlan0" pseudo-interface and maps it to the physical ndis interface. The second line simply tells the ifconfig command to use WPA authentication and to grab a dynamic IP. Next, add the following to your /boot/loader.conf to make these changes permanent:
#Wireless
if_ndis_load="YES"
W70N51_SYS_load="YES"
At this point, you can either reboot the laptop or restart networking using "/etc/rc.d/netif restart". If you choose to restart networking, you might have to manually create the pseudo-interface using the following command: "ifconfig wlan0 create wlandev ndis0". If you are upgrading your laptop, you may wish to remove all the ipw* entries from both configuration files as they are no longer needed.
Using this configuration, one odd bug I've run into is that my wireless interface comes up and associates with the WAP but I do not get an IP address. I suspect that this could possibly be due to the fact that the DHCP server is on a different box, but I'll have to run a few debugs to see where it's sticking.
Using ndis, while a little clunky initially, has proven to be a much better replacement for the built in ipw driver. While I was on FreeBSD 7.2 and even Linux, my wireless interface would frequently reload the driver firmware. I'm told that's due to a bursting configuration on the WAP but I don't have bursting enabled and no other wireless device on my network displays the same behavior. Along with the cool changes in FreeBSD 8, this makes BSD on my laptop that much more enjoyable!