Keegan Carruthers-Smith's Blog

Suspend on Lid Close in Ubuntu

Fri, 26 Oct 2012 10:00:00 -0000

Suspend on Lid Close in Ubuntu

I just got a new laptop (Lenovo T420s) and installed Ubuntu 12.10. The default behaviour when closing the lid is to show a black screen and nothing else. I don’t know who prefers this use case (maybe external monitor users?) My issue might also be that I don’t use gnome-power-manager which may override the default behaviour. What I would prefer is suspending and showing a lock screen when the lid is opened up again.

So how do we go about fixing this? Well closing the lid sends an ACPI event, and on Ubuntu there are a bunch of shell scripts in /etc/acpi which get called depending on the event. In the case of a lid close it runs /etc/acpi/lid.sh. Reading that file we can see that it runs a file /etc/acpi/local/lid.post.sh if it exists and is executable.

If we save /etc/acpi/local/lid.post.sh as

#!/bin/bash

# On lid close show lock screen and suspend laptop.

. /usr/share/acpi-support/power-funcs

grep -q closed /proc/acpi/button/lid/*/state
if [ $? = 0 ]; then
    for x in /tmp/.X11-unix/*; do
        displaynum=`echo $x | sed s#/tmp/.X11-unix/X##`
        getXuser;
        if [ x"$XAUTHORITY" != x"" ]; then
            export DISPLAY=":$displaynum"
            su $user -c 'gnome-screensaver-command --lock'
        fi
    done
    pm-suspend
fi

then on suspend we run pm-suspend as root and gnome-screensaver-command –lock for every user which has an X session running. Remember to make the file executable:

$ sudo chown root:root /etc/acpi/local/lid.post.sh
$ sudo chmod 0755 /etc/acpi/local/lid.post.sh

You can pretty much do anything on lid close (and other acpi events) if you know a bit of scripting. An example of something would be checking if any external monitors are connected, and if they are don’t suspend and switch off the laptop screen (just a bit of xrandr magic).

DNS Caching with Network Manager

Wed, 11 Jan 2012 15:00:00 -0000

DNS Caching with Network Manager

I have been finding the DNS server on my router to be a bit flaky. It can take up-to 2 seconds to resolve a domain name and does no caching. This leads to slower network performance in applications that don’t do there own DNS caching.

There is an easy fix to this in Linux, just install dnsmasq, enable its DNS server and add 127.0.0.1 to your /etc/resolv.conf. dnsmasq then uses the nameservers specified in /etc/resolv.conf (other than itself) to lookup hostnames.

Unfortunately if you use Network Manager, it manages your /etc/resolv.conf and there doesn’t seem to be a way to add in custom entries on top of the ones Network Manager receives from DHCP. However, each time Network Manager brings up a network interface it runs the scripts in /etc/network/if-up.d/. The script below prepends the nameservers 127.0.0.1 (dnsmasq’s DNS server) and 8.8.4.4 (Google’s open DNS server) to /etc/resolv.conf.

#!/bin/sh
# Add dnsmasq caching server and google dns to /etc/resolv.conf

set -e

# No need to do anything on loopback.
if [ "$IFACE" = lo ]; then exit 0; fi

# Only run from ifup.
if [ "$MODE" != start ]; then exit 0; fi

cp /etc/resolv.conf /etc/resolv.conf.tmp
echo nameserver 127.0.0.1 > /etc/resolv.conf
echo nameserver 8.8.4.4 >> /etc/resolv.conf
cat /etc/resolv.conf.tmp >> /etc/resolv.conf
rm /etc/resolv.conf.tmp

Here are some step by step instructions to get it working in Ubuntu/Debian:

$ sudo apt-get install dnsmasq
$ # Add `listen-address=127.0.0.1` to `/etc/dnsmasq.conf`
$ sudo /etc/init.d/dnsmasq restart
$ # Copy the above script into a file called dnsmasq-cache
$ chmod +x dnsmasq-cache
$ sudo mv dnsmasq-cache /etc/network/if-up.d/

Now when Network Manager brings up an interface it should enable use of dnsmasq’s caching DNS server. Take care when configuring dnsmasq to not enable it’s DHCP server unless you intend on using it. This can cause havoc on some LANs.

Now DNS records which haven’t expired should be super quick after the first access. On a simple test over crappy tethered internet I go from 952 msec to 0 msec for a query:

$ dig www.uct.ac.za | grep 'Query time'
;; Query time: 952 msec
$ dig www.uct.ac.za | grep 'Query time'
;; Query time: 0 msec

Better Python Flymake Integration in Emacs

Tue, 18 Oct 2011 18:30:00 -0000

Better Python Flymake Integration in Emacs

Flymake is a great feature in Emacs for getting warnings and errors in source code as you type it. When I am coding in Python I like to use PEP8 and pyflakes to warn me about stylistic and potential errors. I integrated those tools into Emacs by following the guide at http://reinout.vanrees.org/weblog/2010/05/11/pep8-pyflakes-emacs.html

However, I find it annoying that all output from PEP8 and pyflakes is treated as an error by flymake. Notice in the following image that only the last highlighted line is an error, while the rest of the lines should be treated as warnings.

Wouldn’t it be much better if flymake treated the warning lines as warnings, and highlighted them as such?

We can accomplish this by modifying the output of PEP8 and pyflakes such that flymake correctly recognizes messages as warnings. The following code does just that (and runs both PEP8 and pyflakes on the input):

#!/usr/bin/env python

import commands
import re
import sys

def make_re(*msgs):
    return re.compile('(%s)' % '|'.join(msgs))

pyflakes_ignore = make_re('unable to detect undefined names')
pyflakes_warning = make_re(
    'imported but unused',
    'is assigned to but never used',
    'redefinition of unused',
)
pep8_ignore = ['E501']
pep8_warning = make_re('.')

def run(cmd, ignore_re, warning_re):
    output = commands.getoutput(cmd)
    for line in output.splitlines():
        if ignore_re and ignore_re.search(line):
            continue
        elif ': ' in line and warning_re.search(line):
            line = '%s: WARNING %s' % tuple(line.split(': ', 1))
        print line

run('pyflakes %s' % sys.argv[1], pyflakes_ignore, pyflakes_warning)
print '## pyflakes above, pep8 below ##'
pep8_ignore = ' '.join('--ignore=%s' % i for i in pep8_ignore)
run('pep8 %s --repeat %s' % (pep8_ignore, sys.argv[1]), None, pep8_warning)

This code may change over time, as I find different outputs that should be treated as warnings. The latest version of this code is here.

Here is the snippet of elisp to make flymake use the above command in python-mode. Replace /PATH/TO/pyflakespep8.py to a valid path to the command.

;; Pyflakes for python
(when (load "flymake" t)
  (defun flymake-pychecker-init ()
    (let* ((temp-file (flymake-init-create-temp-buffer-copy
                       'flymake-create-temp-inplace))
           (local-file (file-relative-name
                        temp-file
                        (file-name-directory buffer-file-name))))
      (list "/PATH/TO/pyflakespep8.py" (list local-file))))
  (add-to-list 'flymake-allowed-file-name-masks
               '("\\.py\\'" flymake-pychecker-init)))

Labelled Breaks in Python with Context Managers

Sat, 04 Jun 2011 18:30:00 -0000

Labelled Breaks in Python with Context Managers

A friend of mine who codes in Java a lot was lamenting the fact that Python does not support labelled breaks. Labelled breaks are useful when you have nested loops and want to break out of the outer loop based on a condition in an inner loop.

For example say we had a list of lists containing numbers

import random
lists = [[random.randint(0, 100) for i in range(10)] for i in range(10)]

We then want to check if the number 42 is in any of the lists

found = False
for li in lists:
    for val in li:
        if val == 42:
            found = True
            break
    if found:
        break

For the purpose of illustration we use nested for loops instead of something like

found = any(42 in li for li in lists)

The two for loops are a simple example, but in more complicated examples we may have extremely nested loops. This usually calls for some refactoring into classes/function, but with labelled breaks we can keep a clean code structure. For example in Java we could write this as

// int lists[][] = something;
boolean found = false;

search:
for (i = 0; i < lists.length; i++) {
    for (j = 0; j < lists[i].length; j++) {
        if (lists[i][j] == 42) {
            found = true;
            break search;
        }
    }
}

There is PEP 3136 which proposed labelled breaks for Python, but that was rejected. Luckily Python 2.5 introduced context managers, which give us a way to hack in labelled breaks.

class Label(object):
    class __break(Exception):
        def __init__(self, ctx):
            self.ctx = ctx

    def __enter__(self):
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        return isinstance(exc_val, self.__break) and exc_val.ctx is self

    def break_(self):
        raise self.__break(self)

When a context manager’s block has finished executing, the __exit__ method is called. It is passed exception info (or None if it exited without exception). When the block is exiting due to an exception Python will look at the return value of __exit__. If the __exit__ method returns True the exception is not reraised. If __exit__ returns something else then the exception is reraised.

So we can simulate labelled breaks using exceptions and context managers. In the above code the __exit__ method returns True only when the exception passed is one thrown from its instance of break_. We can now write our search code with labelled breaks:

found = False
with Label() as search:
 for li in lists:
     for val in li:
         if val == 42:
             found = True
             search.break_()

Sliding Window Minimum

Thu, 05 May 2011 12:00:00 -0000

Sliding Window Minimum

Sliding window minimum is an interesting algorithm, so I thought I would implement it in a bunch of different languages. See https://bitbucket.org/keegan_csmith/sliding-window-minimum/src for implementations of the algorithm in different programming languages. What follows is an explanation of the problem and the algorithm.

Problem Introduction

The algorithm is sometimes also referred to as the Ascending Minima algorithm. I learnt the algorithm from a South African Computer Olympiad camp some years ago. I couldn’t find any references to it in any journal, however there are some explanations on the Internet.

Given an array ARR and an integer K, the problem boils down to computing for each index i: min(ARR[i], ARR[i-1], ..., ARR[i-K+1]). The algorithm for this “slides” a “window” of size K over ARR computing at each step the current minimum. In other words the algorithm roughly follows this psuedocode:

for (i = 0; i < ARR.size(); i++) {
  remove ARR[i-K] from the sliding window
  insert ARR[i] into the sliding window
  output the smallest value in the window
}

The sliding window algorithm does the remove, insert and output step in amortized constant time. Or rather the time it takes to run the algorithm is O(ARR.size()).

Naive Algorithms

Before I explain the O(1) solution for sliding window minimum, let me explain some alternative solutions which are suboptimal. The most straight-forward solution is for each index i in ARR, simply loop over the values from ARR[i-K+1] to ARR[i] and keep track of the minimum

void brute_force_time(std::vector<int> & ARR, int K) {
  for (int i = 0; i < ARR.size(); i++) {
     int min_value = ARR[i];
     for (int j = i - 1; j >= min(i - K + 1, 0); j--)
        min_value = min(min_value, ARR[j]);
     std::cout << min_value << ' ';
  }
}

The above C++ code runs in O(NK) where N = ARR.size(). We can improve on this by using a sorted set to speed up the minimum value queries to logarithmic time

void logarithmic_time(std::vector<int> & ARR, int K) {
  std::multiset<int> window;
  for (int i = 0; i < ARR.size(); i++) {
     window.insert(ARR[i]);
     if (i - K >= 0)
       window.erase(window.find(ARR[i - K]));
     std::cout << *window.begin() << ' ';
  }
}

The window can have at most K elements, so the multiset insert, find and begin operations all take time O(logK). This gives us an overall time of O(NlogK).

We can improve the run-time by a constant factor by using a heap instead. All the heap operations (except finding the minima) have the same run-time complexity as the multiset versions, however heaps empirically perform better. We need to be able to remove arbitrary items in the heap, but the implementation of heaps in C++ (std::priority_queue) does not support this operation. Luckily a technique I have mastered in real life helps us get around this: we delete lazily. For each element in the priority queue we also store what index it was inserted from. Then when we query what the smallest element is, we discard it if its index falls out of range of our current window.

void logarithmic_time2(std::vector<int> & ARR, int K) {
  // pair<int, int> represents the pair (-ARR[i], i). We use -ARR[i] since
  // priority_queue is by default a max-heap, but we want a min-heap. By
  // negating the value on insertion and removal we get a min-heap. One can
  // also use the rather ugly
  // std::priority_queue< std::pair<int, int>,
  //                      std::vector< std::pair<int, int> >,
  //                      std::greater< std::pair<int, int> > >

  std::priority_queue< std::pair<int, int> > window;
  for (int i = 0; i < ARR.size(); i++) {
     window.push(std::make_pair(-ARR[i], i));
     while(window.top().second <= i - K)
       window.pop();
     std::cout << (-window.top().first) << ' ';
  }
}

Note that deleting lazily can actually make this algorithm perform rather badly. If the input is N values from N to 1, then a value is never deleted from the priority queue leading to O(logN) insertions. However, on average this is empirically faster than the multiset version.

Sliding Window Minimum Algorithm

The idea of lazily deleting elements is a salient one, but by putting in a bit more effort when inserting an element into the window we can get amortized O(1) run-time. Say our window contains the elements {1, 6, 7, 2, 4, 2}. We want to add the element 5 to our window. Notice that all elements in the window greater than 5 will now never be the minimum in the window for future i values, so we might as well get rid of them. The trick to this is to store the numbers in a deque [1] and whenever inserting a number x we remove all numbers at the back of the deque which are greater than equal to x. Notice that if the deque was sorted before inserting, it will still be sorted after inserting x. Since the deque starts off sorted, it remains sorted throughout the sliding window algorithm. So the front of the deque will always be the smallest value.

The front of the queue might have a value which shouldn’t be in the window anymore, but we can use the lazy delete idea with the deques as well. Now each element of ARR is inserted into the deque and deleted from the deque at most once. This gives as a total run-time of O(N) for the algorithm (amortized O(1) per insertion/deletion). Pretty sweet

void sliding_window_minimum(std::vector<int> & ARR, int K) {
  // pair<int, int> represents the pair (ARR[i], i)
  std::deque< std::pair<int, int> > window;
  for (int i = 0; i < ARR.size(); i++) {
     while (!window.empty() && window.back().first >= ARR[i])
       window.pop_back();
     window.push_back(std::make_pair(ARR[i], i));

     while(window.front().second <= i - K)
       window.pop_front();

     std::cout << (window.front().first) << ' ';
  }
}

Extensions

You can modify the algorithm by flipping >= to <= to get the sliding window maximum algorithm.

In fact this algorithm works on any totally ordered set. So the elements can be floats, sets, strings, etc. Essentially anything which has a <= operator that behaves “nicely”.

Think you fully understand this algorithm, try solving these problems:

Task “sound” at http://www.boi2007.de/en/tasks

Task “pyramid” at http://olympiads.win.tue.nl/ioi/ioi2006/contest/day1/ (medium to hard problem)

[1]	Double-Ended Queue. Supports constant time insertion, removal and lookups at the front and the back of the queue.