Abbreviations in Vim

There are a few bits of text that are common to almost every file I edit with Vim. One of them is, of course, my name. The others are my e-mail address, and the date.

Vim allows you to define simple text abbreviations to make entering such strings super-easy. Here's a snip of my .vimrc.

" Some handy abbreviations.
"
" Insert date.
iab xdate =strftime("%Y/%m/%d %H:%M:%S")

" What's my name?
iab xname Mohit Muthanna Cheppudira

" My personal sig.
iab xsigp Mohit Muthanna Cheppudira 

" My work sig.
iab xsigw Mohit Muthanna Cheppudira 

With the above in my Vim configuration, the text xdate gets auto-replaced to today's date.

Slick.

Simple Code Folding in Vim

I've been on a Vim customization frenzy the last few days, and I just discovered an uber-cool feature: code folding. Folding is the process of rolling up a block of lines in the buffer, to a single line.

Here's what folded code looks like:



So, to unfold a block, simply move the cursor to the block and hit "zO". (All the fold commands begin with "z"). Here's what an unfolded block looks like:


There are many ways to fold code, but the simplest way to enable it is by setting the foldmethod option to indent. This folds code based on its indentation.

If you're looking for syntax-aware folding, you can set fold-method to syntax. This generally takes a little more tweaking to get the right fold behaviour.

Add the following to your .vimrc, to get simple straightforward indentation-based code folding:

" Enable folding by indentation
" Use: zc, zo, zC, zO, zR, zM
" Ctrl-K .3 for ⋯
set foldmethod=indent
highlight Folded ctermfg=red
highlight FoldColumn ctermfg=white
set fillchars=fold:⋯

For more information about code folding, and to get a list of all the commands, see http://www.vim.org/htmldoc/usr_28.html.

Generating Circular Primes

I've been having way too much fun with Project Euler (and Haskell) lately. Below is a listing of my solution to problem 35: "How many circular primes are there below a million?"

It solves in about 2 seconds on my laptop (using -O2). This isn't great, but not bad given that the only optimizations in the code are: a memoized prime number generator, and the use of Data.Set for quick primality tests.

-- Project Euler: Problem 35
--
-- The number, 197, is called a circular prime because all rotations of the
-- digits: 197, 971, and 719, are themselves prime.
--
-- There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37,
-- 71, 73, 79, and 97.
--
-- How many circular primes are there below one million?

import Data.Set (Set)
import qualified Data.Set as Set
import System (getArgs)

-- How many circular primes do you want?
limit = 1000000

-- Memoized prime number generator.
primes :: [Integer]
primes = 2 : 3 : 5 : filter (not . hasFactor) [7..]
  where hasFactor n = any (divides n) $ takeWhile (<= lowestFactor n) primes
        divides n m = n `mod` m == 0
        lowestFactor = ceiling . sqrt . fromIntegral

-- Given an integer, return the number of digits in it.
digits :: Integer -> Int
digits n = ceiling $ logBase 10 $ fromIntegral (n + 1)

-- Rotate number right:
--   rotate 456 = 645
--   rotate 3498 = 8349
--
-- Note that this does not work for numbers that have zeroes in them. But
-- that's okay because any number with a zero in it is not a circular prime.
-- Also, right rotation catches the zero before it disappears into the 
-- significant digit.
rotate :: Integer -> Integer
rotate n = strip_last_digit + (last_digit * tens_place)
  where last_digit = n `mod` 10
        strip_last_digit = (n - last_digit) `div` 10
        tens_place = (10 ^ (digits n - 1))

-- Set of million primes. This enables fast lookup in isCircularPrime.
primeSet :: Set Integer
primeSet = Set.fromList $ takeWhile (< limit) primes

-- Returns True if number is prime.
isPrime :: Integer -> Bool
isPrime n = Set.member n primeSet

-- Returns True if the number is a circular prime.
isCircularPrime :: Integer -> Bool
isCircularPrime n = all isPrime $ take (digits n) $ iterate rotate n

-- Go.
main :: IO ()
main = print $ length $ filter isCircularPrime $ takeWhile (< limit) primes

So... how can I optimize this some more?

Project Euler

I can't believe I never knew about this before. Project Euler is very addictive. You've been warned.

Tackling the Awkward Squad

It's been a long time since I've blogged a new post.

Some of the time it's because I start a topic, and never finish it, leaving behind a mess of draft posts. But most of the time, it's because I have nothing interesting to say.

Today, I have something interesting to say:

Haskell is full of lazy-sugary-pure-functional goodness.

There. I said it.

If you have never used Haskell, now would be a great time to start. I'm not going to pimp it too much, because there's a huge community out there who are already doing that quite well.

Haskell will bend your mind. Haskell will make you feel young again. Haskell will save the cheerleader.

And if you have already been learning Haskell, and plan to do serious work with it, you need to know how to tackle the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls.

I'll defer to Simon Peyton Jones from Microsoft Research, Cambridge in his awesomely awesome paper: Tackling the Awkward Squad.

Scheduling on SMP Hardware

Ever wondered how the Linux scheduler schedules a job on another processor, after the idle task has halted the CPU?

On x86 systems, the answer lies in InterProcessor Interrupts (IPI). An IPI is a type of custom interrupt that can be sent from one processor to another, using an Advanced Programmable Interrupt Controller (APIC).

One of the customers of IPIs happens to be the OS task scheduler, where a processor can be woken up after a task is added to it's per-processor run queue.

Let me add some context.

On a uni-processor machine, the idle task is scheduled when the OS has absolutely nothing to do. The main purpose of this task is to shut down the CPU by first making sure that interrupts are enabled, and then sending the hlt instruction. This happens in the default_idle() function within arch/i386/process.c, via a call to safe_halt().

100 void default_idle(void)
101 {
102         local_irq_enable();
103
104         if (!hlt_counter && boot_cpu_data.hlt_works_ok) {
105                 clear_thread_flag(TIF_POLLING_NRFLAG);
106                 smp_mb__after_clear_bit();
107                 while (!need_resched()) {
108                         local_irq_disable();
109                         if (!need_resched())
110                                 safe_halt();
111                         else
112                                 local_irq_enable();
113                 }
114                 set_thread_flag(TIF_POLLING_NRFLAG);
115         } else {
116                 while (!need_resched())
117                         cpu_relax();
118         }
119 }

The safe_halt() function, is not really a function, but a preprocessor macro that calls the sti and hlt instructions, and is defined in include/asm-i386/system.h.

#define safe_halt()             __asm__ __volatile__("sti; hlt": : :"memory")

Of course, since interrupts are enabled, the CPU is immediately woken up when an interrupt is received. This could be from any IO device, the timer, or even another processor. On an idle machine, the timer interrupt vector gates into the scheduler, which may examine it's per-processor run-queues, and try to find a task to execute. If nothing is found, the idle task gets rescheduled.

This works well on uniprocessor systems, but on an SMP system, the timer interrupt only wakes up the primary CPU. So what happens when a new task is forked, and the scheduler decides that it needs to run on another CPU?

The answer lies within the scheduler code (kernel/sched.c), in the resched_task() function.

820 #ifdef CONFIG_SMP
821 static void resched_task(task_t *p)
822 {
823         int cpu;
824
825         assert_spin_locked(&task_rq(p)->lock);
826
827         if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
828                 return;
829
830         set_tsk_thread_flag(p, TIF_NEED_RESCHED);
831
832         cpu = task_cpu(p);
833         if (cpu == smp_processor_id())
834                 return;
835
836         /* NEED_RESCHED must be visible before we test POLLING_NRFLAG */
837         smp_mb();
838         if (!test_tsk_thread_flag(p, TIF_POLLING_NRFLAG))
839                 smp_send_reschedule(cpu);
840 }
841 #else
842 static inline void resched_task(task_t *p)
843 {
844         assert_spin_locked(&task_rq(p)->lock);
845         set_tsk_need_resched(p);
846 }
847 #endif

As you can see there are two versions of this function, one for uniprocessor systems, and the other for SMP systems. On a uniprocessor, the task is rescheduled by setting the TIF_NEED_RESCHED flag, via a call to set_tsk_need_resched().

On a multiprocessor system, the same flag is set, and a check is made to see if the task should be running on a different processor from the current one. If not, it just returns, and lets the scheduler take care of rescheduling the task. Otherwise, it wakes up the target processor by calling the smp_send_reschedule() function.

The smp_send_reschedule() function (defined in arch/i386/kernel/smp.c) simply sends an IPI to the specified processor, by calling send_IPI_mask().

472 /*
473  * This function sends a 'reschedule' IPI to another CPU.
474  * it goes straight through and wastes no time serializing
475  * anything. Worst case is that we lose a reschedule ...
476  */
477 void smp_send_reschedule(int cpu)
478 {
479         WARN_ON(cpu_is_offline(cpu));
480         send_IPI_mask(cpumask_of_cpu(cpu), RESCHEDULE_VECTOR);
481 }

The send_IPI_mask() function uses the APIC to fire an interrupt off to the target processor. It calls send_IPI_mask_bitmask(), which in-turn programs the APIC using the functions in include/asm-i386/apic.h.

160 void send_IPI_mask_bitmask(cpumask_t cpumask, int vector)
161 {
162         unsigned long mask = cpus_addr(cpumask)[0];
163         unsigned long cfg;
164         unsigned long flags;
165
166         local_irq_save(flags);
167         WARN_ON(mask & ~cpus_addr(cpu_online_map)[0]);
168         /*
169          * Wait for idle.
170          */
171         apic_wait_icr_idle();
172                
173         /*
174          * prepare target chip field
175          */
176         cfg = __prepare_ICR2(mask);
177         apic_write_around(APIC_ICR2, cfg);
178                
179         /*
180          * program the ICR
181          */
182         cfg = __prepare_ICR(0, vector);
183                        
184         /*
185          * Send the IPI. The write to APIC_ICR fires this off.
186          */
187         apic_write_around(APIC_ICR, cfg);
188
189         local_irq_restore(flags);
190 }

The specific IPI-gate is defined as RESCHEDULE_VECTOR, and is installed by the smp_intr_init() function in arch/i386/kernel/smpboot.c.

1454 void __init smp_intr_init(void)
1455 {
1456         /*
1457          * IRQ0 must be given a fixed assignment and initialized,
1458          * because it's used before the IO-APIC is set up.
1459          */
1460         set_intr_gate(FIRST_DEVICE_VECTOR, interrupt[0]);
1461
1462         /*
1463          * The reschedule interrupt is a CPU-to-CPU reschedule-helper
1464          * IPI, driven by wakeup.
1465          */
1466         set_intr_gate(RESCHEDULE_VECTOR, reschedule_interrupt);
1467
1468         /* IPI for invalidation */
1469         set_intr_gate(INVALIDATE_TLB_VECTOR, invalidate_interrupt);
1470
1471         /* IPI for generic function call */
1472         set_intr_gate(CALL_FUNCTION_VECTOR, call_function_interrupt);
1473 }

These gates are installed at boot time, and are responsible for handling the various interrupts on multiprocessor systems. An APIC is required on all SMP systems for various reasons, and scheduling is one of them.

There is one small detail that I left out. You may have wondered about the TIF_POLLING_NRFLAG scattered about in the code. If you provide "idle=poll" as a kernel parameter at boot time, the idle function points to poll_idle(), instead of default_idle().

The poll_idle() function does not halt the processor, but spins around checking to see if a task is ready to run. As you may have guessed, although performance may improve, it's not very power-friendly. You certainly don't want this on your laptop.

124 /*
125  * On SMP it's slightly faster (but much more power-consuming!)
126  * to poll the ->work.need_resched flag instead of waiting for the
127  * cross-CPU IPI to arrive. Use this option with caution.
128  */
129 static void poll_idle (void)
130 {
131         local_irq_enable();
132
133         asm volatile(
134                 "2:"
135                 "testl %0, %1;"
136                 "rep; nop;"
137                 "je 2b;"
138                 : : "i"(_TIF_NEED_RESCHED), "m" (current_thread_info()->flags));
139 }

If you go back and read the resched_task() function, you will notice that the IPI is only sent if TIF_POLLING_NRFLAG is not set. Since the CPU is already running, it is not necessary to interrupt it.

A final word about IPIs. Waking up a halted processor is not all that it is used for. It is also used in the memory management code, to maintain cache coherency, in certian synchronization code, and many other places in the scheduler.

If you found this interesting and want to learn more, listed below are a few places you can go digging around. Happy hacking!

Note: All file paths are relative to the base of the Linux kernel source tree. The code snippets in this article are from version 2.6.20 of the kernel.

kernel/sched.c
kernel/cpu.c
arch/i386/kernel/smp.c
arch/i386/kernel/smpboot.c
arch/i386/kernel/process.c
arch/i386/kernel/head.S
include/asm-i386/apic.h
Intel APIC Architecture

The Game of Life in JavaScript

I just discovered the canvas tag. <canvas> is a HTML element used for embedding vector graphics within your web pages. It was first introduced by Apple for Dashboard Widgets, and was later implemented in Safari.

It is now supported by most major browsers, except Internet Explorer. Fortunately, Google has a compatibility layer called ExplorerCanvas that brings the canvas tag to IE.

To learn more about <canvas>, Mozilla has a very good tutorial.

Anyhow, for a quick demo of what it can do, check out my interpretation of John Conway's Game of Life, in JavaScript, aptly named Game of Death. I coded it on a Saturday afternoon, slightly hungover, to teach myself JavaScript and familiarize myself with <canvas>.

Here's the source code. Warning: No fancy algorithms within.