My Blog

Namespace issues in Apache

2011-11-25T08:32:00.000-08:00

Some time ago I was given a task to write a Python WSGI script that handles all (really all!) URLs on a given Apache-based virtual host. Doesn't that sound easy? Here is the "obvious" part of the Apache configuration file for that virtual host:

WSGIScriptAlias / /path/to/script.wsgi

Except that it is slightly wrong. The problem is that the script really should handle all URLS, even "evil" ones, without any omissions. In the above form, it doesn't.

First, if the URL contains a percent-encoded slash (e.g., as in http://example.org/foo%2fbar), Apache gives a 404 error by default, without even calling the script. Solution:

AllowEncodedSlashes On

Wait, there is more! Regular aliases have higher priority than our WSGIScriptAlias, and that there are some default aliases usually set by distributions. Due to that, http://example.org/icons/folder.gif will map to a static file, not to the WSGI script. There is a wishlist bug in Apache that one cannot easily remove aliases from the namespace.

The solution (or, more precisely, a bad hack) that I found is to use mod_rewrite. By adding some prefix to all URLs (and, of course, dealing with it in the script), one makes sure that the existing aliases are not hit:

AllowEncodedSlashes On

RewriteEngine On
RewriteRule ^/(.*)$ /dummyprefix/$1 [PT]

WSGIScriptAlias /dummyprefix /path/to/script.wsgi

Still, this doesn't work (gives a 404 error instead of calling the script) on URLs that include some bad characters such as newlines, e.g. http://example.org/foo%0abar . Removing the dollar sign from the pattern fixes the 404 error, calls the script, but it then receives a truncated PATH_INFO in the environment. Still, SCRIPT_URI is correct, so this may be enough. In fact, if the script doesn't care about PATH_INFO, even this works:

AllowEncodedSlashes On

RewriteEngine On
RewriteRule ^/ /dummyprefix [PT]

WSGIScriptAlias /dummyprefix /path/to/script.wsgi

The real cause of the issue with the original RewriteRule is that the "." metacharacter doesn't really match all characters. Indeed, it doesn't match a newline. So, in order to match the full URL, including the evil encoded newline in the middle, one has to write an explicit range covering all possible characters:

AllowEncodedSlashes On

RewriteEngine On
RewriteRule ^/([\x00-\xff]*)$ /dummyprefix/$1 [PT]

WSGIScriptAlias /dummyprefix /path/to/script.wsgi

Whoops. Now a typical sysadmin probably won't understand the need (or will forget the reason) behind such a complex configuration for a seemingly simple issue of passing all URLs to a single script. And I am still not 100% sure that all valid URLs are really handled by the script. Maybe I should have started with a different web server, the one that doesn't have a polluted namespace in virtual hosts by default.

Update: In the comments, the following was suggested:

AllowEncodedSlashes On
WSGIHandlerScript wsgi-handler /path/to/handler.wsgi
SetHandler wsgi-handler

Here handler.wsgi would be a typical WSGI script, except that it provides the "handle_request" callable object instead of "application".

This solution looks elegant and simple, but, if PHP is also installed on the same server, it is wrong (thus proving the complexity of the problem and the fragility of Apache URL namespace). It misses URLs that end in .php (even though the document root s empty). So, back to the ugly solution based on mod_rewrite.

Autoconf and defaults

2011-09-27T00:25:00.000-07:00

Autoconf is based on a set of macros. these macros are put by developers into the configure.ac file, and the "autoconf" program generates a proper configure script from that. The configure script commonly accepts options such as --enable-foo and --with-foo. It is important that they behave in a sensible way.

The --with-foo argument is processed with the AC_ARG_WITH macro. It is documented as follows:

AC_ARG_WITH (package, help-string, [action-if-given], [action-if-not-given])

If the user gave configure the option --with-packageor --without-package, run shell commandsaction-if-given. If neither option was given, run shell commandsaction-if-not-given. The name package indicates anothersoftware package that this program should work with. It should consistonly of alphanumeric characters, dashes, plus signs, and dots.

The option's argument is available to the shell commandsaction-if-given in the shell variable withval, which isactually just the value of the shell variable namedwith_package, with any non-alphanumeric characters inpackage changed into ‘_’. You may use that variable instead,if you wish.

Let's see what's wrong with this piece of configure.ac, found in lxdm-0.4.1:

AC_ARG_WITH(pam,AC_HELP_STRING([--without-pam],[build without pam]),
[],[AC_CHECK_LIB([pam], [pam_open_session])])

This does nothing if the --without-pam option is not given, and checks for the PAM library if the option is given. Looks right? No!

This also does nothing if the --with-pam option is given, thus, resulting in a build without PAM support!

Note that the documentation for AC_ARG_WITH even provides examples how to use the macro properly. Use them as a reference, and have the following checklist:

Use the $withval or $with_package variable.
Test it for values such as "yes", "no", "auto" and explicit path.
Check the presence of the package unless it is explicitly disabled or the support is experimental.
Fail if the external package is requested but not available.

Yes, this becomes verbose, but it is necessary for correctness.

The first point also applies to the AC_ARG_ENABLE macro:

AC_ARG_ENABLE(debug,         AS_HELP_STRING([--enable-debug],
                                  [Enable debugging (default: disabled)]),
                                [DEBUGGING=$enableval], [DEBUGGING=no])

I wrote a DTS encoder

2011-09-24T06:13:00.000-07:00

Let me announce a piece of software that I have published a week ago: dcaenc, an open-source DTS encoder. The package contains sources for a shared library, a command-line tool and an ALSA plugin.

DTS is one of the compressed formats that allow transfer of multichannel (e.g., 5.1) audio over SPDIF connections. The other common format is AC3. The SPDIF standard does not define a method for passing more than two channels of uncompressed PCM audio, so compression has to be used. Both AC3 and DTS are also used in DVD sound tracks.

Open-source decoders for both AC3 and DTS already exist: liba52 and libdca (side note: please don't use libdca, it is a security risk, there are some files that crash it or are decoded improperly). FFmpeg can also decode these formats. However, useful open-source encoders existed only for AC3: one in FFmpeg, and the other one (aften) based on it. The DTS "encoder" in FFmpeg was ported by someone else from my old proof-of-concept code that served as a tool to understand the DTS subband transform. It could only encode stereo PCM files into a valid DTS bitstream of the same bitrate, which is useless for any practical purpose. Now dcaenc provides a useful encoder that accepts multichannel sound and encodes it to the bitrate specified by the command line parameter.

As already mentioned, there are the following use cases for my encoder:

On-the-fly encoding of multichannel PCM audio produced by arbitrary ALSA applications (e.g. games) for transmission via SPDIF
Creation of DVD soundtracks and DTS CDs.

Some people ask me why I didn't integrate my encoder into FFmpeg instead of releasing it as a standalone package. Indeed, there are faster implementations of the basic DSP building blocks in FFmpeg, and the criticism that I reinvented a lot of wheels is valid. Integration with FFmpeg is indeed a desired long-term goal.

There are still several reasons why I decided not to integrate right from the beginning. First, I don't think that my work is in the necessary shape for integration yet. E.g., in FFmpeg, floating-point codecs are preferred, while my library currently uses fixed-point (I thought it would be beneficial for porting to the ARM architecture). Second and the most important reason: when the encoder is standalone, users can get it immediately and use it, without the hassle of replacing the distribution-provided FFmpeg package and potentially breaking distribution-provided software such as VLC that depends on it. Third, if I know that I wrote all the code myself, I can sell LGPL exceptions.

While dcaenc already produces "transparent" output at 1411 or 1536 kilobits per second, there is still room for quality improvement at lower bitrates. This is because the library does not yet use all compression possibilities offered by the DTS standard. I am going to implement at least linear prediction (incorrectly called ADPCM in the specification) and channel coupling in the future versions. Stay tuned!

I am going to Desktop Summit 2011

2011-08-05T14:25:00.000-07:00

I am going to Desktop Summit. Actually, I have already arrived in Berlin.

At the summit, I will mostly follow the Platform track (Rm2002) and then try to participate in BoFs.

The case of a non-raised exception

2011-03-12T14:10:00.000-08:00

As you probably know, python uses exceptions for error handling. It is considered a good style to avoid adding error-handling code in the form of conditional statements. Instead, one should rely on the fact that an appropriate exception is raised once an error condition is detected, and caught when it can be dealt with.

So, let'a assume that you are given a task of downloading a file given the URL and the file name on disk, using Python. You may want to write the following code and hope that you don't have to add any error-handling because (as you think) all errors that can happen are either network errors or file write errors, and those two types of errors already raise exceptions for you.

#!/usr/bin/python

import urllib2
import sys
import socket

def download(url, fname):
    net = urllib2.urlopen(url)
    f = open(fname, "wb")
    
    while True:
        data = net.read(4096)
        if not data:
            break
        f.write(data)
    
    net.close()
    f.close()

if __name__ == "__main__":
    if len(sys.argv) != 3:
        print "Usage: download.py URL filename"
    
    url = sys.argv[1]
    fname = sys.argv[2]
    
    socket.setdefaulttimeout(30)
    
    download(url, fname)

Indeed, this code downloads existing files via HTTP just fine. Also, it provides sensible tracebacks for non-existing hosts, 404 errors, full-disk situations, and socket timeouts. So, it looks like the result of calling the download() fnction is either a successfully downloaded file, or an exception that the other part of the application will likely be able to deal with.

But actually, it only looks like this. Consider a situation when the HTTP server closes the connection gracefully at the TCP level, but prematurely. You can test this by starting your own Apache web server, putting a large file there, and calling "apache2ctl restart" while the client is downloading the file. Result: an incompletely downloaded file, and no exceptions.

I don't know if it should be considered a bug in urllib2 or in the example download() function above. In fact, urllib2 could have noticed the mismatch of the total number of bytes before the EOF and the value in the Content-Length HTTP header.

Here is a version of the download() function that detects incomplete downloads based on the Content-Length header:

def download(url, fname):
    net = urllib2.urlopen(url)
    contentlen = net.info().get("Content-Length", "")
    f = open(fname, "wb")
    datalen = 0
    
    while True:
        data = net.read(4096)
        if not data:
            break
        f.write(data)
 datalen += len(data)
    
    net.close()
    f.close()

    try:
        contentlen = int(contentlen)
    except ValueError:
        contentlen = None

    if contentlen is not None and contentlen != datalen:
        raise urllib2.URLError("Incomplete download")

Writing systemd service files

2011-01-04T10:44:00.000-08:00

Today I tried to convert a Gentoo initscript for VDE to a systemd service file. This post documents the required steps. VDE has been chosen as an example because it is a simple daemon (commonly used for communication between several instances of QEMU and the host) that illustrates the matter well.

Background

For those who don't know, systemd is a next-generation replacement for /sbin/init written by Lennart Poettering. While systemd supports traditional initscripts, service files are its native form of configuration. Service files have a structure similar to that of desktop files or Windows ini files. Their syntax is well documented in the manual pages.

Initscripts typically contain boilerplate code that checks whether the daemon is already running or figures out which process to kill when the daemon has to be stopped. Tools like start-stop-daemon help, but systemd reduces the syntax overhead to the minimum. This simplification occurs because service files specify what should be done, not how it should be done. I.e., unlike initscripts, they follow the declarative style and are not programs.

Simple services

Here is the simplest possible service file that starts VDE with options that work for me on my computer. Save it as /etc/systemd/system/vde.service:

[Unit]
Description=Virtual Distributed Ethernet

[Service]
ExecStart=/usr/bin/vde_switch --tap tap0 --mode 0660 \
 --dirmode 0750 --group qemu

[Install]
WantedBy=multi-user.target

Note the difference from a traditional init script: for simplicity, vde_switch is started in such a way that it doesn't become a daemon. In fact, it is possible to start real daemons that fork, you just have to tell systemd about that:

[Unit]
Description=Virtual Distributed Ethernet

[Service]
Type=forking
# The PID file is optional, but recommended in the manpage
# "so that systemd can identify the main process of the daemon"
PIDFile=/var/run/vde.pid
ExecStart=/usr/bin/vde_switch --tap tap0 --mode 0660 \
 --dirmode 0750 --group qemu \
 --daemon --pidfile /var/run/vde.pid

[Install]
WantedBy=multi-user.target

The difference is in the way the dependencies are handled. If some other services depend on vde.service, then, in the first example, systemd will be able to run them as soon as it starts vde_switch. In the second example, systemd will wait until vde_switch forks. The difference matters, because vde_switch creates its control socket after starting, but before forking. So, in the first example, there is some chance that systemd will start something that tries to connect to the socket before vde_switch creates it.

Automatic restarts

Let's also add the proper dependency on the system logger and tell systemd to restart vde_switch if it crashes due to an uncaught signal (although it never happened to me):

[Unit]
Description=Virtual Distributed Ethernet
After=syslog.target

[Service]
Type=forking
PIDFile=/var/run/vde.pid
ExecStart=/usr/bin/vde_switch --tap tap0 --mode 0660 \
 --dirmode 0750 --group qemu \
 --daemon --pidfile /var/run/vde.pid
Restart=on-abort

[Install]
WantedBy=multi-user.target

Now try to start and crash the daemon:

home ~ # systemctl start vde.service
home ~ # systemctl status vde.service
vde.service - Virtual Distributed Ethernet
   Loaded: loaded (/etc/systemd/system/vde.service)
   Active: active (running) since Tue, 04 Jan 2011 22:08:10 +0500;
15s ago
  Process: 31434 (/usr/bin/vde_switch --tap tap0...,
code=exited, status=0/SUCCESS)
 Main PID: 31435 (vde_switch)
   CGroup: name=systemd:/system/vde.service
    └ 31435 /usr/bin/vde_switch --tap tap0...
home ~ # kill -SEGV 31435
home ~ # systemctl status vde.service
vde.service - Virtual Distributed Ethernet
   Loaded: loaded (/etc/systemd/system/vde.service)
   Active: failed since Tue, 04 Jan 2011 22:11:27 +0500;
4s ago
  Process: 31503 (/usr/bin/vde_switch --tap tap0...,
code=exited, status=0/SUCCESS)
 Main PID: 31504 (code=exited, status=1/FAILURE)
   CGroup: name=systemd:/system/vde.service

I.e., restarting didn't work. The system log tells us why:

Jan  4 22:11:27 home vde_switch[31504]: Error in pidfile
creation: File exists

So, VDE has a bug in its pidfile creation. There are two ways how one can deal with this: either tell systemd to remove the PID file before starting vde_switch, or drop the PID file altogether (because vde_switch has exactly one process, there can be no confusion which process is the main one). Both ways work. Here is how to implement the first alternative:

[Unit]
Description=Virtual Distributed Ethernet
After=syslog.target

[Service]
Type=forking
PIDFile=/var/run/vde.pid
# Note the -f: don't fail if there is no PID file
ExecStartPre=/bin/rm -f /var/run/vde.pid
ExecStart=/usr/bin/vde_switch --tap tap0 --mode 0660 \
 --dirmode 0750 --group qemu \
 --daemon --pidfile /var/run/vde.pid
Restart=on-abort

[Install]
WantedBy=multi-user.target

And here is the second alternative:

[Unit]
Description=Virtual Distributed Ethernet
After=syslog.target

[Service]
Type=forking
ExecStart=/usr/bin/vde_switch --tap tap0 --mode 0660 \
 --dirmode 0750 --group qemu \
 --daemon
Restart=on-abort

[Install]
WantedBy=multi-user.target

Configuration

Many initscripts come with configuration files that allow the user to customize how the daemon is started. For example, some users may want to pass the --hub argument to vde_switch, and others may want to enable the management socket. So, in Gentoo, the traditional configuration file for the initscript looks like this:

# load the tun module
VDE_MODPROBE_TUN="yes"
# virtual tap networking device to be used for vde
VDE_TAP="tap0"
# mode and group for the socket
VDE_SOCK_CHMOD="770"
VDE_SOCK_CHOWN=":qemu"

# This is the actual options string passed to VDE.
# Change this at your own risk.
VDE_OPTS="--tap ${VDE_TAP} -daemon"

Systemd service files typically use the EnvironmentFile key to provide users with a file where they can put their preferences regarding the service.

Traditional initscripts source their configuration files. Thus, any syntax construction supported by /bin/sh will work in the configuration file. In the example above, we see comments, assignment of values to variables, and reusing the values in later assignments. Systemd uses a different syntax from bash, so please resist the temptation to reuse the same configuration file for the traditional initscript and the service file. Resist even though some service files in the Gentoo systemd overlay do use the same configuration files as the corresponding traditional initscripts -- they are just buggy. Let me explain this in more detail.

Of course, the configuration file example above is not suitable for systemd because variable interpolation is not supported in systemd environment files. But let's suppose that we want to invent something that is suitable both as a bash script fragment and a systemd environment file, and still allows the user to configure vde_switch according to his wishes.

Let's focus on the VDE_OPTS variable only, as it is the only thing that matters. Indeed, module loading can be done directly by systemd (man modules-load.d), and the options related to the socket group and octal permissions can be expressed using vde_switch command line options, as illustrated in the examples above. Since the value of the VDE_OPTS variable can contain spaces, we have to quote it if we want bash to be able to understand what we mean:

VDE_OPTS="--tap tap0 --mode 0660 --dirmode 0750 --group qemu"

Without quotes, bash would interpret this as follows: with the variable VDE_OPTS that has value "--tap" in the environment, start the "tap0" process and pass 6 parameters to it. So, quotes are essential here.

Let's try to use this variable from the service file. We want it to be split by the spaces, so that each part becomes a separate vde_switch parameter. So, according to the systemd.service manpage, we have to use the $VDE_OPTS form, not ${VDE_OPTS}. So here is what we have:

[Unit]
Description=Virtual Distributed Ethernet
After=syslog.target

[Service]
Type=forking
EnvironmentFile=/etc/conf.d/vde2
ExecStart=/usr/bin/vde_switch --daemon $VDE_OPTS
Restart=on-abort

[Install]
WantedBy=multi-user.target

Result: no "tap0" interface and wrong permissions on the control socket. This happened because quotes play a special role in systemd environment files, different from their role in bash scripts. For systemd, they mean that the spaces inside them should not be treated as argument separators. So, all the arguments in $VDE_OPTS were passed to vde_switch as one long argument. No surprise that it didn't work.

In fact, the service file is correct. Its configuration just can't be made compatible with bash, because it is in a different language. The service works with the following configuration file (alas, incompatible with bash):

VDE_OPTS=--tap tap0 --mode 0660 --dirmode 0750 --group qemu

Conclusion

Let's hope that all of the above will get you started writing your own systemd service files. Since there are many initscripts in Gentoo still not converted, the project needs your help.

Thanks

The following people from #systemd IRC channel on freenode provided me with valuable support: MK_FG, zdzichuBG, miti1.

Minimizing server downtime

2010-11-12T21:35:00.000-08:00

Suppose that you are responsible for a typical LAMP server running Debian. The goal is to have the needed security updates and minimize downtime. Unfortunately, due to installation of security updates, services need to be restarted, and sometimes (after kernel updates) even a reboot is required. Here are some tips that will help you shrink the time of service unavailability.

Upgrade your key services (apache, php and mysql) separately from the rest of software. Reason: if you just run "apt-get dist-upgrade" to upgrade everything, then your MySQL server will be stopped at the beginning of the whole upgrade and started only at the end, after unpacking all other packages. So, run "apt-get install mysql-server" before "apt-get dist-upgrade" to minimize the delay.
If you know that kexec works on your hardware, use it: apt-get install kexec-tools. This way, you will avoid the long time (sometimes more than a minute) while your server shows useless BIOS screens. Instead of rebooting to the BIOS, the old kernel will load the new kernel directly and pass control to it, thus avoiding the delay.

DNS servers in resolv.conf

2010-10-23T20:20:00.000-07:00

Yesterday I found a problem with my Linode VPS. When running "aptitude update", it complained about not being able to resolve the name for security.debian.org (a server from where Debian distributes security updates).

Here is the /etc/resolv.conf file from that VPS, generated by dhclient:

domain members.linode.com
search members.linode.com
nameserver 109.74.194.20
nameserver 109.74.192.20
nameserver 109.74.193.20

It looks like the 109.74.194.20 server is overloaded and returns a SERVFAIL ("server failure - The name server was unable to process this query due to a problem with the name server") answer from time to time. Unfortunately, Debian has a bug in its version of libc that prevents the resolver from trying the other (working) servers if the first one returns an answer indicating a temporary failure.

The bug does not exist in glibc-2.12.1 on my Gentoo box at home. However, if the server does not respond at all, the Gentoo resolver spends 15 seconds before trying the next one, which is also not nice.

To work around the bug, you can run your own DNS server on 127.0.0.1 that forwards all queries to the official servers, and put 127.0.0.1 as the only nameserver in /etc/resolv.conf.

Floating-point fields in MySQL

2010-08-05T21:54:00.000-07:00

It is a well-known fact that floating-point values should not be compared for equality, due to rounding problems. MySQL puts an interesting twist to it, as demonstrated on the linux.org.ru forum. To see the strange effect, run the following SQL statements:

mysql> create table test (field float);
mysql> insert into test(field) values(0.3);
mysql> select * from test;
+-------+
| field |
+-------+
|   0.3 |
+-------+
1 row in set (0.00 sec)

mysql> select * from test where field = 0.3;
Empty set (0.00 sec)

I.e., it looks like MySQL successfully stores the value, but cannot find it later.

To see why it happens, recall that 0.3 cannot be represented exactly in binary form. It is a recurring binary fraction 0b0.0100110011... that has to be truncated somewhere when stored by a computer. When stored as a float data type in the table, 24 significant binary digits are retained. However, when 0.3 is mentioned directly in the query, it is treated as a double-precision number, and 53 significant bits are kept. The truncation thus occurs in different places, and the resulting numbers are just different:

mysql> select cast(field as decimal(15,15)) from test;
+-------------------------------+
| cast(field as decimal(15,15)) |
+-------------------------------+
|             0.300000011920929 |
+-------------------------------+
1 row in set (0.00 sec)

mysql> select cast(0.3 as decimal(15,15));
+-----------------------------+
| cast(0.3 as decimal(15,15)) |
+-----------------------------+
|           0.300000000000000 |
+-----------------------------+
1 row in set (0.00 sec)

MySQL documentation contains more information on problems with floating-point values.

When linear search is faster than binary

2010-05-29T07:29:00.000-07:00

It is often stated that a binary search algorithm performs better than linear search. Indeed, let's assume that the goal is to find the index of the largest integer in the sorted zero-based array A that is less than or equal to the given integer X. For simplicity, let's also assume that the size of array is N = 2^K, that for all possible inputs A[0] <= X and that one can also put a sentinel value after the end, so that X < A[N] for all possible inputs X. E.g., if it is known that X always fits in 16 bits, one can put 65536 as the sentinel.

The assumptions above are true for the entropy decoder found in the Monkey's Audio codec. In that case, N = 64, X is unsigned and always fits in 16 bits, A[0] = 0, A[64] = 65536.

This is linear search:

A[N] = sentinel;
index = 0;
while (A[index + 1] <= X)
    ++index;

This is binary search:

int bit = N >> 1;  /* N is a power of two */
index = 0;
while (bit != 0) {
    if (A[index + bit] <= X)
        index += bit;
    bit >>= 1;
}

If the size of array to be searched is N, then the average case complexity is commonly stated to be O(log(N)) for binary search and O(N) for linear search. So, for the Monkey's Audio case presented above, one would expect, on average, 32 loop iterations for the linear search algorithm and 6 iterations for the binary search.

However, there is one key fact that makes the estimate above invalid. Such simple averaging is valid only if each result appears with the same probability. For Monkey's Audio entropy decoder, this is not the case.

In fact, out of the 64 possible results, "0" appears with 31% probability, and the total probability of the first 6 results is 87%. So, it is quite natural that linear search is faster than binary in this case, because it often stops very early.

Converting audio samples

2010-05-10T01:56:00.000-07:00

Different audio applications process audio in different sample formats. Some use 16-bit samples internally, others use 32-bit or floating point samples. In either case, there is a need to convert the sample format for the purposes of export and playback. Sounds like a simple task? No, a rich field for disagreements and bugs, even without taking dithering into account.

E.g., when converting from floating-point samples to 16 bits, there is no universal agreement on the scale. Some (e.g., JACK) think that 1.0 should convert to 32767 and -1.0 to -32767. Within that model, there are two opinions how to get -32768 (the most negative integer representable in 16 bits): "-1.00003" or "you can't". The other viewpoint, implemented, e.g., in ALSA-lib, is that -1.0 should map to -32768, 0.99997 should give 32767 and 1.0 should clip. There is also a third possibility, namely, to use different scale factors for negative and positive sample values, so that 0.0 maps to 0, 1.0 maps to 32767 and -1.0 maps to -32768.

And now some code. If one adopts the 32767.0 scale factor (as in JACK) and declares the -32768 sample value as being unreachable, one can use the following C function for conversion:


int16_t to_int16(float f)
{
    if (f > 1.0) f = 1.0;
    if (f < -1.0) f = -1.0;
    return (int16_t)(f * 0x7fff);
}

As expected, to_int16(1.0) == 32767 and to_int16(-1.0) == -32767. However, the following quite similar function that is supposed to convert floating-point samples to 32-bit signed ones doesn't actually work properly:


int32_t to_int32(float f)
{
    if (f > 1.0) f = 1.0;
    if (f < -1.0) f = -1.0;
    return (int32_t)(f * 0x7fffffff);
}

Indeed, to_int32(1.0) returns the minimum, not the maximum possible 32-bit integer. That happens because, unlike 0x7fff, one cannot represent 0x7fffffff exactly as a floating-point number. So the nearest representable one is substituted, and that's 0x80000000. So the overflow happens, and the function returns a wrong result.

One fix would be to cast 0x7fffffff to a double-precision floating point number. Another (but not 100% equivalent) option is to change the scale factor so that it is close enough, but doesn't cause this overflow, i.e. to 0x7fffff00.

New job

2010-05-10T01:15:00.000-07:00

This blog didn't receive any updates for quite a while. That's both because I was too busy at Yandex and because there were no interesting bugs to blog about. I no longer work at Yandex. There was no single big reason for this decision, just a lot of small issues that accumulated and that don't apply to anyone else.

Now I work for a different company (won't name it here, it is nether SEO nor Google) as a senior developer of a web service. The most pleasant result of the job change is that now I feel more like a developer: write mostly C code, not bash scripts, and can even make architectural decisions.

Matching multiple strings

2009-09-06T01:23:00.000-07:00

Sometimes, it is necessary to check efficiently which of the many input strings contain one of the few pre-defined substrings.

The simplest approach

This task, of course, can be solved inefficiently by brute force, i.e. by passing each substring to strstr(), as demonstrated in the following benchmark that tries to search for known names of linux games in the same string (that actually doesn't match) 100000 times:


/* compile as follows: gcc -o benchmark1 benchmark1.c */
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

const char* words[] = { "actioncube", "alien arena", "astromenace",
"armagetron", "assault cube", "atomorun2008", "battle for wesnoth",
"blob wars", "breakout", "briquolo", "bzflag", "celetania",
"conquest", "enigma", "freeciv", "freecol", "freeorion",
"freetrain", "glest", "hedgewars", "heretic", "hexen",
"jardinanis", "lordsawar", "lxdream", "maniadrive", "neverball",
"nexuiz", "oolite", "openarena", "opencity", "openmw",
"open quartz", "openttd", "paintball 2", "planeshift", "postal 2",
"sacred", "scorched 3d", "smokin' guns", "supertux", "supertuxkart",
"teeworlds", "tremulous", "urban terror", "vegastrike", "warsow",
"wormux", "x-moto" };

const char* text = "gnome uses gconf to store all of its configuration";

int check(const char* p)
{
    int i;
    for (i = 0; i < sizeof(words)/sizeof(words[0]); i++) {
        if (strstr(p, words[i]) != NULL)
            return 0;
    }
    return -1;
}

int main(int argc, char* argv[])
{
    struct timeval start, end;
    int usec_spent;
    int i;
    int result;

    gettimeofday(&start, NULL);
    for (i = 0; i < 100000; i++)
        result = check(text);

    gettimeofday(&end, NULL);
    if (result == 0)
        printf("The string matched\n");
    else
        printf("The string didn't match\n");
    usec_spent = 1000000 * (end.tv_sec - start.tv_sec);
    usec_spent += (end.tv_usec - start.tv_usec);
    printf("Spent %d ms\n", usec_spent / 1000);
    return 0;
}

On my desktop, this benchmark takes 2925 ms.

Aho-Corasick algorithm

Special fast algorithms exist for the same task. All of them preprocess the given set of substrings and use the result of such preprocessing when deciding whether the input string matches. One of such ahorithms is the Aho-Corasick algorithm. A free (BSD-licensed) implementation is available for download. Unfortunately, this implementation operates on wide-character strings and thus is not directly comparable with the strstr() approach. Also, if one of the substrings matches the very beginning of the input string, one cannot distinguish this situation with CSuffixTrie::SearchAhoCorasik() from non-match by looking only atCSuffixTrie::_DataFound::iFoundPosition. To compensate for this, I have extracted the SuffixTrie.{h,cpp} files from the archive and applied the following edits:


--- SuffixTrie.h
+++ SuffixTrie.h
@@ -51,7 +51,7 @@
 {
 public:
     //Our string type
-    typedef std::wstring SearchString;
+    typedef std::string SearchString;
 
     //Data returned from our search
     typedef struct _DataFound
@@ -107,7 +107,7 @@
     virtual ~CSuffixTrie();
 private:
     //Our char search type
-    typedef wchar_t SearchChar;
+    typedef char SearchChar;
 
     //Forward declare the node
     struct _Node;
--- SuffixTrie.cpp    2008-09-24 02:20:46.000000000 +0600
+++ SuffixTrie.cpp    2009-09-06 15:22:11.000000000 +0600
@@ -1,4 +1,3 @@
-#include "stdafx.h"
 #include "SuffixTrie.h"
 
 CSuffixTrie::CSuffixTrie()
@@ -136,7 +135,7 @@
 void CSuffixTrie::BuildTreeIndex()
 {
     //Build index on the root
-    BuildIndex(L"",
+    BuildIndex("",
                &m_aRoot);
 }
 
@@ -261,7 +260,7 @@
 {
     //Our data found
     DataFound aData;
-    aData.iFoundPosition=0;
+    aData.iFoundPosition=-1;
 
     //The current string we match
     SearchString sMatchedString;
@@ -295,7 +294,7 @@
                     pNode=&m_aRoot;
 
                     //Reset search string
-                    sMatchedString=L"";
+                    sMatchedString="";
 
                     //Did we do a switch?
                     if (bSwitch)
@@ -386,7 +385,7 @@
                     pNode=&m_aRoot;
 
                     //Reset search string
-                    sMatchedString=L"";
+                    sMatchedString="";
 
                     //Did we do a switch?
                     if (bSwitch)
@@ -439,7 +438,7 @@
             iCount-=sMatchedString.length()-1;
 
             //Reset the data
-            sMatchedString=L"";
+            sMatchedString="";
         }
     }
 
@@ -495,7 +494,7 @@
 
     //Start to build the trie
     BuildStrings(aVector,
-                 L"",
+                 "",
                  &m_aRoot);
 
     //Done

Here is a benchmark:


/* compile as follows: g++ -O2 -o benchmark2 benchmark2.cpp SuffixTrie.cpp */
#include "SuffixTrie.h"
#include <stdio.h>
#include <string>
#include <sys/time.h>

const char* words[] = { "actioncube", "alien arena", "astromenace",
"armagetron", "assault cube", "atomorun2008", "battle for wesnoth",
"blob wars", "breakout", "briquolo", "bzflag", "celetania",
"conquest", "enigma", "freeciv", "freecol", "freeorion",
"freetrain", "glest", "hedgewars", "heretic", "hexen",
"jardinanis", "lordsawar", "lxdream", "maniadrive", "neverball",
"nexuiz", "oolite", "openarena", "opencity", "openmw",
"open quartz", "openttd", "paintball 2", "planeshift", "postal 2",
"sacred", "scorched 3d", "smokin' guns", "supertux", "supertuxkart",
"teeworlds", "tremulous", "urban terror", "vegastrike", "warsow",
"wormux", "x-moto" };

const char* text = "gnome uses gconf to store all of its configuration";

int main(int argc, char* argv[])
{
    struct timeval start, end;
    int usec_spent;

    CSuffixTrie aTree;
    int i;
    for (i = 0; i < sizeof(words)/sizeof(words[0]); i++)
        aTree.AddString(words[i]);

    aTree.BuildTreeIndex();

    std::string stext = text;
    int pos;

    gettimeofday(&start, NULL);
    for (i = 0; i < 100000; i++) {
        pos = aTree.SearchAhoCorasik(stext).iFoundPosition;
    }
    gettimeofday(&end, NULL);

    if (pos == -1)
        printf("The string didn't match\n");
    else
        printf("The string matched\n");

    usec_spent = 1000000 * (end.tv_sec - start.tv_sec);
    usec_spent += (end.tv_usec - start.tv_usec);
    printf("Spent %d ms\n", usec_spent / 1000);
    return 0;
}

On my desktop, this benchmark takes 326 ms. I.e., this is indeed faster than the simple strstr()-based approach.

Regular expressions

One may wonder why the Aho-Corasick algorithm is not available in the standard C library. The answer is that a more general mechanism, based on a similar idea, is available: regular expressions. One first constructs a regular expression by escaping and joining the given substrings using "|" as the separator, then compiles this regular expression with regcomp() and uses the result in regexec(). Here is a benchmark:


/* compile as follows: gcc -o benchmark3 benchmark3.c */
#include <stdio.h>
#include <regex.h>
#include <string.h>
#include <sys/time.h>

const char* re = "(actioncube|alien arena|astromenace|armagetron|"
"assault cube|atomorun2008|battle for wesnoth|blob wars|breakout|"
"briquolo|bzflag|celetania|conquest|enigma|freeciv|freecol|"
"freeorion|freetrain|glest|hedgewars|heretic|hexen|jardinanis|"
"lordsawar|lxdream|maniadrive|neverball|nexuiz|oolite|openarena|"
"opencity|openmw|open quartz|openttd|paintball 2|planeshift|"
"postal 2|sacred|scorched 3d|smokin' guns|supertux|supertuxkart|"
"teeworlds|tremulous|urban terror|vegastrike|warsow|wormux|x-moto)";

const char* text = "gnome uses gconf to store all of its configuration";

int main(int argc, char* argv[])
{
    struct timeval start, end;
    int usec_spent;
    int i;
    regex_t reg;
    int result;

    result = regcomp(&reg, re, REG_EXTENDED | REG_NOSUB);
    if (result)
        return 1;

    gettimeofday(&start, NULL);
    for (i = 0; i < 100000; i++)
        result = regexec(&reg, text, 0, NULL, 0);
    gettimeofday(&end, NULL);
    if (result == 0)
        printf("The string matched\n");
    else
        printf("The string didn't match\n");
    usec_spent = 1000000 * (end.tv_sec - start.tv_sec);
    usec_spent += (end.tv_usec - start.tv_usec);
    printf("Spent %d ms\n", usec_spent / 1000);
    return 0;
}

On this linux x86 system with glibc-2.10.1, it takes 312 ms, i.e., as good as the Aho-Corasick implementation referenced above.

On other platforms, the result may be different, because the system C library uses a different regular expression engine. E.g., the same benchmark, when compiled with TRE (replace <regex.h> with <tre/regex.h> and add -ltre to the gcc command line), takes 4158 ms, i.e., more than the brute-force approach. Since NetBSD will use TRE in the next release, this unsatisfactory result will likely manifest itself there. So, if you want to give the same performance guarantees on all platforms, don't use regcomp()/regexec().

The same note about unsatisfactory speed (8884 ms here) applies to PCRE. To repeat this test, replace <regex.h> with <pcreposix.h> and add -lpcreposix to gcc command line.

Generated code

It is possible to match multiple substrings much faster, if they are known at compile time. The trick is to convert the regular expression to C code with a tool such as re2c. Here is a benchmark of this approach:


/* compile as follows:
  re2c benchmark4.re >benchmark4.c
  gcc -O1 -o benchmark4 benchmark4.c */
#include <stdio.h>
#include <sys/time.h>

int check(const char* p)
{
    const unsigned char* marker;
/*!re2c
    re2c:define:YYCTYPE  = "unsigned char";
    re2c:define:YYCURSOR = p;
    re2c:yyfill:enable = 0;
    re2c:define:YYMARKER = marker;
    re2c:yych:conversion = 1;
    [\001-\377]*( "actioncube" | "alien arena" |
    "astromenace" | "armagetron" |
    "assault cube" | "atomorun2008" |
    "battle for wesnoth" | "blob wars" |
    "breakout" | "briquolo" | "bzflag" |
    "celetania" | "conquest" | "enigma" |
    "freeciv" | "freecol" | "freeorion" |
    "freetrain" | "glest" | "hedgewars" |
    "heretic" | "hexen" | "jardinanis" |
    "lordsawar" | "lxdream" | "maniadrive" |
    "neverball" | "nexuiz" | "oolite" |
    "openarena" | "opencity" | "openmw" |
    "open quartz" | "openttd" | "paintball 2" |
    "planeshift" | "postal 2" | "sacred" |
    "scorched 3d" | "smokin' guns" |
    "supertux" | "supertuxkart" |
    "teeworlds" | "tremulous" |
    "urban terror" | "vegastrike" |
    "warsow" | "wormux" |
    "x-moto" ) { return 0; }
    "" { return 1; }
*/
}

const char* text = "gnome uses gconf to store all of its configuration";

int main(int argc, char* argv[])
{
    struct timeval start, end;
    int usec_spent;
    int i;
    int result;

    gettimeofday(&start, NULL);
    for (i = 0; i < 100000; i++)
        result = check(text);
    gettimeofday(&end, NULL);
    if (result == 0)
        printf("The string matched\n");
    else
        printf("The string didn't match\n");
    usec_spent = 1000000 * (end.tv_sec - start.tv_sec);
    usec_spent += (end.tv_usec - start.tv_usec);
    printf("Spent %d ms\n", usec_spent / 1000);
    return 0;
}

When compiled with -O1 or -O3, this benchmark runs 12 ms here (i.e., almost 250 times faster than the brute-force approach). However, the -O2 optimization option makes the code slower (it runs 16 ms).

Dangers of setjmp()/longjmp()

2009-07-25T06:43:00.000-07:00

Suppose that you want to use an external library (e.g., libpng or libjpeg) that, in terms of error handling, only gives you a choice between an approach based on setjmp()/longjmp(), or aborting the program. Of course, in robust programs, the first method should be used. But there are pitfalls inherently associated with using setjmp(). Let me illustrate one of them using ImageMagick as an example.

Once ImageMagick determines the dimensions of a PNG image that it reads, it allocates memory to store the pixels. The task is to free it if the image file is in fact broken. But the input image can be so broken that libpng calls longjmp() before telling the dimensions of the image. In this case, ImageMagick allocates nothing and thus has nothing to free. In short, the error path has to free memory if and only if it has been allocated before.

Sounds simple? Let's look at the code that seems to implement this logic:


static Image *ReadOnePNGImage(MngInfo *mng_info,
  const ImageInfo *image_info, ExceptionInfo *exception)
{
Image
  *image;

png_struct
  *ping;

unsigned char
  *png_pixels;

/* set up ping, do other things */

png_pixels=(unsigned char *) NULL;
if (setjmp(ping->jmpbuf))
  {
    /*
      PNG image is corrupt.
    */
    /* ... */
      if (png_pixels != (unsigned char *) NULL)
       png_pixels=(unsigned char *) RelinquishMagickMemory(png_pixels);
    /* ... */
    return(GetFirstImageInList(image));
  }

/* read png dimensions and other information - might call longjmp() */

if (num_passes > 1)
  png_pixels=(unsigned char *) AcquireQuantumMemory(image->rows,
    ping_info->rowbytes*sizeof(*png_pixels));
else
  png_pixels=(unsigned char *) AcquireQuantumMemory(ping_info->rowbytes,
    sizeof(*png_pixels));

/* read the scanlines - might call longjmp() */
/* do other useful things */
return (image);
}

At first, it seems that the code does exactly what is stated above: the bold statement frees the png_pixels pointer only if the memory has been allocated. But actually it doesn't work: the memory leaks if a broken PNG file is attempted to be processed. The library seems to forget after returning to setjmp() that a non-NULL value has been assigned to png_pixels. If one inserts printf() calls for debugging, they will print a non-NULL value after AcquireQuantumMemory(), but a NULL before the NULL check. So the memory is allocated and then not freed.

The explanation is that, after longjmp(), according to the ISO C standard (7.13.2.1, "The longjmp function"),

All accessible objects have values as of the time longjmp was called, except that the values of objects of automatic storage duration that are local to the function containing the invocation of the corresponding setjmp macro that do not have volatile-qualified type and have been changed between the setjmp invocation and longjmp call are indeterminate.

Indeed, the png_pixels variable is automatic, not volatile, and is changed between the calls to setjmp() and longjmp(), and thus the standard allows it to forget its value. GCC sometimes (but not always!) warns about such cases.

The simplest fix is usually to declare the variable as volatile. As for ImageMagick, they opted to fix the problem in a different way (but, if I read it correctly - with some dead code, and not for all variables), and version 6.5.4-6 is supposed to have no such memory leak.

New TV Set

2009-06-28T07:20:00.000-07:00

Recently I bougth a new TV set - a Sony KDL-32W5500 LCD. It replaced the old Soviet-era CRT-based "Akari" TV.

The new TV set receives both analog (still the norm in Russia) and digital stations. It contains an AVC tuner and thus doesn't need a set-top box or a separate decoder to watch the digital broadcasts (Russia, unlike the rest of the world, uses MPEG-4 Part 10, aka H.264, for them).

The default color settings are good, unlike those in the old TV, which gave oversaturated colors by default. The new TV set has a 1920x1080 panel, but I found that, for my eyes, 1080i and 720p (from the computer monitor) look nearly the same. And there is not a lot of HD content in Yekaterinburg anyway.

The default option for aspect ratio, however, is to stretch 4:3 content to 16:9 non-uniformly. The options to preserve the original 4:3 aspect and to stretch the letterboxed content uniformly do exist. I wish it could autodetect the letterbox - this would mean one less button to use.

While digital broadcasts are displayed perfectly, the analog tuner is not so good as in the old TV. Stations that were displayed with "snow" by the old TV now are not watchable at all due to either flashing color stripes or the "no signal" message.

As far as the inputs go, the Sony TV has 4 HDMI sockets, one VGA, one USB and one Ethernet connection. Using a DVI -> HDMI cable and a separate analog audio cable, this TV can be connected to my computer's video card and sound card. The intel driver had no problems recognizing it as a 1920x1080@60p panel.

However, as the primary TV show consumer is my mother, this is still not a very viable solution. I want to work while she watches films. So, I tried using the built-in media playback capabilities of this TV set.

First, it can play files from USB flash drives. The instruction says it accepts only MPEG-1, but de-facto, it accepted non-interlaced MPEG-2, too. It could not play a DVD rip from the flash drive. So, using this option means transcoding everything - not very good.

Second, it can act as a UPnP Renderer. The instruction says that the TV accepts MPEG-1, MPEG-2 and AVCHD formats. So, I thought I could set up a media server on my computer. I have tried MediaTomb and MiniDLNA. MediaTomb did not work at all (the TV displayed the "server is unsupported" message), MiniDLNA worked somewhat. I was able to send MPEG-1 and MPEG-2 files (including the DVD rip that failed to play from the flash drive) to the TV. I could not remux an available H.264 + AC3 Matroska file to MPEG-TS in such a way that the TV understands it. So, for typical torrented video files, this still means transcoding. So, I must conclude that the media playback capabilities of this TV are there only for the marketing department to be able to say that they exist.

So, I am a bit dissatisfied with this offer from Sony.

Don't use old dtoa.c

2009-03-08T11:10:00.000-07:00

A lot of projects use the dtoa.c file that bears the following copyright notice:

 * The author of this software is David M. Gay.
 *
 * Copyright (c) 1991, 2000, 2001 by Lucent Technologies.

If your software uses it, please take steps to update this file or stop using it. The reason is very simple: your program will compile just fine, but will work incorrectly when compiled with gcc-4.4.0 (not released yet). Here is a short testcase (save as test.c):

#include <stdio.h>

double strtod(const char *s00, char **se);

int main(int argc, char* argv[])
{
 double result = strtod(argv[1], 0);
 printf("%f\n", result);
 return 0;
}

Compile as follows: gcc-4.4 -O2 -Dstrtod=my_strtod -DIEEE_8087=1 -DHonor_FLT_ROUNDS=1 -DTrust_FLT_ROUNDS -DOmit_Private_Memory=1 -DNO_INFNAN_CHECK=1 -DNO_HEX_FP=1 dtoa.c test.c

The -Dstrtod=my_strtod flag is needed in order to make sure that the version of strtod() from dtoa.c, not from your system C library, is used. -O2 is the default optimization level used by many software projects. The rest of the flags are explained in the dtoa.c file.

The testcase converts its argument to a double-precision floating-point number, and then prints the result. So, when given a number, this testcase should print it back. let's try:

$ ./a.out 1.1
11.000000

The result is clearly incorrect. The reason (as one can see by appending -Wall to the compiler command line) is that strict aliasing rules are violated in dtoa.c. Indeed, if one adds the -fno-strict-aliasing flag to the compiler command line, the resulting program will behave correctly:

$ ./a.out 1.1
1.100000

Here is the formulation of the aliasing rules from ISO/IEC 9899:TC2, section 6.5:

An object shall have its stored value accessed only by an lvalue expression that has one of the following types:

a type compatible with the effective type of the object,

a qualified version of a type compatible with the effective type of the object,

a type that is the signed or unsigned type corresponding to the effective type of the object,

a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,

an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or

a character type.

dtoa.c does this:

typedef union { double d; ULong L[2]; } U;

#define word0(x) ((U*)&x)->L[1]
#define word1(x) ((U*)&x)->L[0]
#define dval(x) ((U*)&x)->d

So, it stores doubles, but reads this memory using lvalue expressions of the "ULong" type (and the other way round), contrary to the standard.

GCC allows such access only if the memory is accessed through a union type. The TC3 revision of the C99 standard also allows type punning through the union in the footnote in the section 6.5.2.3:

If the member used to access the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning".

In dtoa.c, the union is "invented" each time the code wants to reinterpret a double value as two ULongs. So, it doesn't make sense to speak about the member last used to store a value in the union, and the note above doesn't apply. I.e., instead of this code,

double a;
word0(a) = L;
word1(a) = 0;
return dval(a);

this should be used:

U a;
a.L[0] = L;
a.L[1] = 0;
return a.d;

Note that there are no pointer casts in the corrected code.

The topic of strict aliasing rules, with working and non-working examples, is explained in the GCC manual. An updated version of dtoa.c and the needed header are available in the sources of GCC itself.

Package dependencies

2009-01-31T01:43:00.000-08:00

Let's start with this fact: linphone uses the ffmpeg library to encode video. How can various package managers be informed about this fact by maintainers while building the linphone package?

In Arch Linux, the dependency information is expressed in the PKGBUILD file in a very straightforward way:

depends=('alsa-lib' 'ffmpeg>=20080715' 'gtk2' 'libexosip2>=3.1.0' 'speex>=1.1.12')

And this propagates in the same form into the binary package of linphone. But, is it really what is needed to prevent installation of a broken package? No.

The linphone binary from the package uses the libavcodec.so.51 library, not just "any ffmpeg >=20080715". So the linphone package will break when the ffmpeg package starts providing libavcodec.so.52 (and this already happened in the testing repository). Let's see how other package managers deal with the situation.

RPM-based distributions have to add this line to the linphone.spec script:

BuildRequires:  ffmpeg-dev

Then, RPM will build the linphone package and examine the resulting binaries. It will notice that the linphone binary uses the libavcodec.so.51 library and will add the dependency on that library (not on some abstract "ffmpeg" package). This way, if the new ffmpeg package no longer includes libavcodec.so.51, RPM will notice that the linphone package now has an unsatisfied dependency, print an error message and refuse to upgrade ffmpeg.

This is better than the Arch Linux way, but requires some external tool to know that libavcodec.so.51 is actually in the ffmpeg package. Otherwise, how would the "install linphone with all dependencies" request be handled?

Now let's talk about Debian and its derivatives. They also have a notion of a build-time dependency, and it is expressed in the debian/control file:

Build-Depends: ..., libavcodec-dev, ...

When the package is built, debhelper also notices that the resulting linphone binary depends on libavcodec.so.51, and searches the installed packages for this library. As a result, the dependency on the found package is added automatically to the binary package of linphone. This looks similar to the Arch Linux case, but Debian has a policy that requires the shared library version to be mentioned in the package name. I.e., linphone gets a dependency on "libavcodec51" package, while "libavcodec52" is a completely different package that (assuming no bugs) can be installed in parallel with libavcodec51, thus allowing the rebuilds of other packages for the ffmpeg upgrade to take place gradually, without any hurry and without the broken intermediate state.

Inefficient use of Valgrind

2009-01-06T01:04:00.000-08:00

This is already stated in the documentation, but let me repeat. Valgrind can detect memory leaks only if the application uses malloc() and free(), or, in C++, operator new() and operator delete().

This is not always the case. E.g., ImageMagick, when configured with the --enable-embeddable switch, uses mmap() directly in order to allocate memory for its needs. Other problematic cases involve custom memory pools on top of malloc() and free(), as done in Glib.

So, if you want to find a memory leak with Valgrind, the first thing to do is to turn off all those custom memory allocation schemes. OTOH, if the buggy thing is the allocator itself, this will hide the bug.

Getting more quality from onboard sound

2008-12-27T04:17:00.000-08:00

Onboard high-definition audio chips are very common now. From the viewpoint of software, they support unbelievable quality of sound reproduction: 24 bits of precision at the 192 kHz sampling rate. The reality is in fact worse, as there is always noise in the analog output that the headphones are connected to.

I am not talking about the thermal noise or 1/f noise that is created intrinsically by every electronic device and sounds like a soft "shshsh...". These kinds of noise are important in radio receivers or tape recorders that have a high-gain amplifier needed to recover a weak incoming signal, but not in computers.

I am talking about the interference, where the signal in one wire (not intended to be played as sound) propagates into the other wire located nearby or to another circuit connected to the same badly-filtered power supply. The exact sound of such interference depends on what the computer is doing. If the computer is doing something periodically (e.g., drawing a scene on the screen 60 times a second, or filling a sound buffer in JACK 500 times a second), this unwanted sound becomes a tone, and thus becomes easily noticeable. Here are the steps that helped me to reduce it in my desktop computer based on the Intel DG965SS motherboard.

First, the wire that picks up a lot of interference is the wire that connects the front headphone socket to the motherboard. It is better to avoid using the front socket at all, and plug the headphones (if the cord is long enough) into the green socket on the back of the motherboard. This way, the cord is screened from the noisy components inside the computer by the metallic case.

Second, it may be a good idea to reduce the time variations of the power consumption of various components in the computer.

E.g., the processor draws a lot of power when it is busy, but consumes less power when it is idle. When it switches between the busy and idle states periodically, it creates a tone in the power line, and that tone ultimately gets to the sound chip output. So, to suppress the tone, one solution would be to keep the processor always busy. This is what the "idle=poll" Linux kernel parameter does. Note that a busy processor runs hot (in my computer, at 47.0°C), so think twice before using this option. A less dragonian solution would be to pass the "max_cstate=3" parameter to the "processor" module. (A big "thanks" goes to Robert Hancock and Sitsofe Wheeler who suggested these parameters.)

The other component of the computer that periodically draws a lot of power is the video card. But it is easier to keep it mostly idle, not busy. The most common desktop process that keeps the GPU busy is a compositing window manager (kwin or compiz). So, disable desktop effects, and enjoy better sound quality.

JPEG quality is a meaningless number

2008-12-13T03:44:00.000-08:00

Suppose that a web designer tells you:

Your task is to make a script that creates images for this web page. The images should be in JPEG format, have such-and-such dimensions, and their quality should be this number of percent.

Ignore the bit about the desired quality, especially if the web designer uses Adobe Photoshop and has tested his page only with images made with Photoshop. The reason is that the same number yields different quality in different applications. Let me demonstrate this using this original image.

The image has been resized to 400x300 pixels using Photoshop (that contains Adobe's own JPEG encoder) and GIMP (that uses libjpeg from IJG, as many web scripts do). Here are the screenshots of the corresponding settings.

Photoshop:

GIMP:

As you see, both programs are set to optimization of Huffman tables, no smoothing, no chroma subsampling, and 60% quality according to their scales. Here are the resulting images.

Photoshop:

GIMP:

As you can see, the image created by Adobe Photoshop is almost perfect, while on the image created with GIMP there are visible artifacts in the form of double contours around the parrots in the top row. This is not what the web designer wanted.

Here are some statistics. The image made with Photoshop takes 46 KB, while the image made with GIMP takes only 26 KB.

The quantization tables stored in the JPEG files are also different. If you don't know how to interpret numbers in them: the bigger the number is, the more precision is lost. The closer the number is to the right or bottom, to finer horizontal or vertical details it corresponds.

Photoshop:


          Luminance                           Chrominance
 6   4   4   6   9  11  12  16       7   7  13  24  26  31  31  31
 4   5   5   6   8  10  12  12       7  12  16  21  31  31  31  31
 4   5   5   6  10  12  14  19      13  16  17  31  31  31  31  31
 6   6   6  11  12  15  19  28      24  21  31  31  31  31  31  31
 9   8  10  12  16  20  27  31      26  31  31  31  31  31  31  31
11  10  12  15  20  27  31  31      31  31  31  31  31  31  31  31
12  12  14  19  27  31  31  31      31  31  31  31  31  31  31  31
16  12  19  28  31  31  31  31      31  31  31  31  31  31  31  31

GIMP:


          Luminance                           Chrominance
13   9   8  13  19  32  41  49      14  14  19  38  79  79  79  79
10  10  11  15  21  46  48  44      14  17  21  53  79  79  79  79
11  10  13  19  32  46  55  45      19  21  45  79  79  79  79  79
11  14  18  23  41  70  64  50      38  53  79  79  79  79  79  79
14  18  30  45  54  87  82  62      79  79  79  79  79  79  79  79
19  28  44  51  65  83  90  74      79  79  79  79  79  79  79  79
39  51  62  70  82  97  96  81      79  79  79  79  79  79  79  79
58  74  76  78  90  80  82  79      79  79  79  79  79  79  79  79

So indeed, Photoshop saves more details than GIMP at the indicated settings. The meaningless quality percentages match, the actual quality settings don't. In order to achieve in GIMP (and thus in web scripts that use the same libjpeg library from IJG) what the web designer actually meant, one would need to use quality=85% or so.

A way to lose a file

2008-12-06T01:59:00.000-08:00

The ln command from GNU coreutils warns when the source and the destination of the attempted hardlink are the same file, and does nothing:


$ echo 123 >testfile
$ ls -l testfile
--rw-r--r--  1 aep  aep  4 Dec  6 15:08 testfile
$ ln testfile testfile 
ln: creating hard link `testfile': File exists
$ ln -f testfile testfile 
ln: `testfile' and `testfile' are the same file
$ ls -l testfile
--rw-r--r--  1 aep  aep  4 Dec  6 15:08 testfile

Its counterpart from FreeBSD, however, doesn't warn. Instead, it erases the file.


$ echo 123 >testfile
$ ls -l testfile
--rw-r--r--  1 aep  aep  4 Dec  6 15:08 testfile
$ ln testfile testfile
ln: testfile: No such file or directory
$ ls -l testfile
ls: testfile: No such file or directory

Fixes

2008-12-06T01:51:00.000-08:00

Some time ago, I mentioned in this blog some bugs that annoyed me. Some of them got fixes:

Speaker-test fails with pcsp: fixed in ALSA Git.
Kernel panic due to iwlwifi: fixed in linux-2.6.27.6
Internal compiler error in GCC-4.3 on proprietary code: fixed in GCC SVN, the fix will be a part of GCC-4.4.

Linux audio sucks

2008-11-23T05:31:00.000-08:00

because of bugs in drivers, libraries, and applications. Here are some of them. They are quite real, because they interfere with my not-so-unrealistic requirements (play music through headphones connected to the onboard HD audio chip, make some noise with the PC speaker when someone calls me via SIP, and copy sound from my TV tuner to the HD audio chip when I watch TV).

In a driver. Take, for example, saa7134-alsa (a kernel module that allows recording audio from SAA713X-based TV tuners). It advertises support for the following sample rates: 32 kHz and 48 kHz. What it fails to mention is that it doesn't support recording at 48 kHz except for the case of "original SAA7134 with the MIXER_ADDR_LINE2 capture source". In all other cases (e.g., SAA7133 with the MIXER_ADDR_TVTUNER capture source), it gives out 32 kHz samples, but mislabels them as 48 kHz. Thus, applications such as MPlayer have to be configured to use only the 32 kHz sample rate. Not a big problem if such configuration is possible (i.e.: if not using PulseAudio together with HAL), but still a bug.
In the ALSA library. Today I discovered that the PC speaker at home no longer plays ring tones in SIP clients. It did work before, but I can no longer find a working revision. While testing this sound device with speaker-test, I found this floating point exception inside the ALSA library.
In applications. The most frequent bug is that an application doesn't have a way to use an arbitrary ALSA device, and instead has a drop-down box with pre-defined choices. Such applications often cannot work with Bluetooth headsets (that I don't have), FireWire audio cards (that I don't have either), and through non-default PulseAudio devices (and this has bit me when I tried to use Linphone with PulseAudio - I couldn't configure it to use the PC speaker through PulseAudio). What's even worse is that HAL endorses this faulty "drop-down box" enumeration scheme.

Strange backtrace

2008-11-16T04:01:00.000-08:00

Some time ago I had to debug a strange crash. It was in a multithreaded program and manifested itself only on FreeBSD i386. The code (with all the needed declarations included, seemingly irrelevant details removed, and everything renamed) looks like this:


#include <cstdio>
#include <cstring>
#include <cerrno>
#include <fcntl.h>
#include <unistd.h>
#include <exception>


class system_error : public exception
{
public:
    system_error() throw() :error_text(strerror(errno)) {}
    virtual const char* what() const throw() { return error_text; }
private:
    const char* error_text;
};

class strange_thing
{
public:
    strange_thing(); // fills in some useful defaults
private:
    // lots of implementation details
};

class strange_container
{
public:
    strange_container();
    ~strange_container()  { if (fd != -1) close(fd); }
    void play_with_strange_thing(const char* filename);
private:
    int fd;
};

strange_container::strange_container()
: fd(-1)
{
    play_with_strange_thing("test.file");
}

void strange_container::play_with_strange_thing(const char* filename)
{
    fd = open(filename, O_CREAT | O_TRUNC | O_RDWR, 0777);
    if (fd == -1)
        throw system_error();
    strange_thing ss;
    /* here goes some code that uses ss and fd */
}

// well, actually it is not the main function, but something buried in a thread
int main(int argc, char* argv[])
{
    strange_container c;
    return 0;
}

The test file is not created, and the segfault looks like this:


[aep@bsd1 ~/crashtest]$ gdb ./a.out
GNU gdb 6.1.1 [FreeBSD]
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-marcel-freebsd"...
(gdb) run
Starting program: /usr/home/aep/crashtest/a.out 
[New LWP 100043]
[New Thread 0x28301100 (LWP 100043)]

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x28301100 (LWP 100043)]
strange_container::play_with_strange_thing (this=0x28306098, 
    filename=0x8048c33 "test.file") at crashtest.cpp:57
57  fd = open(filename, O_CREAT | O_TRUNC | O_RDWR, 0666);

At this point, everything looks valid, including the "this" pointer. By all applicable logic, the program just cannot segfault by calling open() with valid parameters. So I started adding debugging printf() statements. The statement just before the call to play_with_strange_thing() worked fine, and none of the statements inside play_with_strange_thing() worked. Moreover, when I added a printf() as the very first line of strange_container::play_with_strange_thing() and ran gdb on the result, it showed this printf() in the backtrace!

So, I didn't believe my eyes. I thought (wrongly) that printf() and buffering somehow interacts with the segfault, and thus invented a different mechanism to find out whether a certain line of code was reached by the program. Namely, I replaced all my debugging printf() calls in strange_container::play_with_strange_thing() with throwing exceptions, with the intention to remove them one-by-one:


void strange_container::play_with_strange_thing(const char* filename)
{
    throw system_error();  // (1)
    fd = open(filename, O_CREAT | O_TRUNC | O_RDWR, 0777);
    throw system_error();
    if (fd == -1)
        throw system_error();
    throw system_error(); // (2)
    strange_thing ss;
    throw system_error(); // (3)
    /* here goes some code that uses ss and fd, err... throws system_error() */
}

This worked. I knew for sure that point (2) was reached, and point (3) was't. So there is something bad with creation of the strange thing that, however, doesn't cause gdb to complain about its constructor.

So, I had to take another look into the implementation of the strange_thing class. The issue was actually with the huge size of the object (several megabytes)! So, no wonder that it overflowed the thread stack. You can reproduce the crash on your own system by replacing "lots of implementation details" with "char c[2000000];", implementing the strange_thing default constructor, and running with a low-enough "ulimit -s" setting.

As the reason of the crash became known, it was an easy matter to fix properly, by not creating huge objects on the stack.

Unexpected warning

2008-10-25T03:25:00.000-07:00

Today I refactored a function in my C program in order to make it more readable and remove special-casing. What came unexpected is that I got a new warning in a function that I didn't touch. While this sounds strange, here is a very simple example that shows how it could happen.

This is the function that I didn't touch, but that will, at the end, get a warning:


extern const int db_to_add[32];

static int add_db(int a, int b)
{
 if (a < b) {
  int tmp = a;
  a = b;
  b = tmp;
 }
 if (a - b >= 32)
  return a;

 return a + db_to_add[a - b];
}

Here is a caller, just to make it sure that a static function is used:


int peak_db[32];
static int noise(int band1, int band2, int spectrum1, int spectrum2)
{
 /* actually a lot more complex, but the idea is that
    it takes two bands, except for special cases */
 int noise1 = peak_db[band1] + spectrum1;
 int noise2 = peak_db[band2] + spectrum2;
 return add_db(noise1, noise2);
}

int valid_use(int b, int s)
{
 /* a dummy warning-free function
    only for the purpose of this blog post */
 return noise(b, b + 1, 0, s);
}

With all of the above, there is no warning, even when "-O3 -Wall" flags are passed to gcc. Now add this (in the real program, this is the result of value propagation over various branches):


int trigger_warning()
{
 return noise(0, 0, 0, -200);
}

The intention is to attenuate the unneeded term enough so that it doesn't matter, and use the general two-band case. With gcc-4.3.1 -O3 -Wall, the result, referring to the line in add_db() where a is compared with b, is:


warning: assuming signed overflow does not occur when assuming that (X - c) > X is always false

So it looks like gcc inlined everything and attempted to test whether peak_db[0] < peak_db[0] - 200. Because C compilers are allowed to think that signed overflow never occurs, this is always false (as intended). However, tests of this form are often incorrectly used as security checks, that's why the warning.

Don't believe rrdtool

2008-10-23T04:48:00.000-07:00

rrdtool is the industry standard for plotting time-dependent data (t.g., for monitoring). However, Debian's rrdtool 1.3.1-4 can create misleading plots. Here is how to reproduce.

First, create a round-robin database that will hold our test data.


rrdtool create testdata.rrd --start 1224453000 --step 1800 \
   DS:testdata:GAUGE:28000:0:U RRA:LAST:0.5:1:1800

Then, populate it with numbers:


rrdtool update testdata.rrd 1224453300:1350535
rrdtool update testdata.rrd 1224467700:1350545
rrdtool update testdata.rrd 1224482100:1350554
rrdtool update testdata.rrd 1224496500:1350560
rrdtool update testdata.rrd 1224514800:1350562
rrdtool update testdata.rrd 1224539700:1350562
rrdtool update testdata.rrd 1224557700:1350562
rrdtool update testdata.rrd 1224576000:1350562
rrdtool update testdata.rrd 1224590100:1350562
rrdtool update testdata.rrd 1224604800:1350562
rrdtool update testdata.rrd 1224622500:1350562
rrdtool update testdata.rrd 1224636900:1350562
rrdtool update testdata.rrd 1224651300:1350562
rrdtool update testdata.rrd 1224669300:1350562
rrdtool update testdata.rrd 1224683700:1350562
rrdtool update testdata.rrd 1224698100:1350562
rrdtool update testdata.rrd 1224712500:1350562
rrdtool update testdata.rrd 1224730500:1350562
rrdtool update testdata.rrd 1224744900:1350562

The number before the semicolon is a UNIX timestamp, and the number after the semicolon is the corresponding value. As you see from the numbers, the value is slightly above 1.35 million and slowly grows in the beginning of the period.

Let's plot it:


rrdtool graph testdata.png -t testdata --start 1224453000 --end 1224757634 \
   DEF:testdata=testdata.rrd:testdata:LAST 'LINE2:testdata#ff0000'

Indeed, there is not much change. But let's suppose that we are really interested in the small change that happened over the week.

Let's use the alternative autoscaling option that, according to the manual page, is designed specifically for such cases:


rrdtool graph testdata-bug.png -t testdata --start 1224453000 --end 1224757634 \
   -A -Y DEF:testdata=testdata.rrd:testdata:LAST 'LINE2:testdata#ff0000'

What? The plot says that the value is 35000M, which is waaaay wrong.

I don't know yet whether this bug is Debian-spedific, but that's enough for discouraging me from using -A and -Y options.

Update: not a bug. The label is just cut off from the left. Here is the correct plot:


rrdtool graph testdata-bug.png -t testdata --start 1224453000 --end 1224757634 \
   -A -Y -L 10 DEF:testdata=testdata.rrd:testdata:LAST 'LINE2:testdata#ff0000'

Although I must say that MS Excel handles this case better: it replaces numbers that don't fit with "###". Such placeholder (no number) is better than a wrong (chopped) number.

Porting C/C++ code from Unix to Win32

2008-10-12T06:48:00.000-07:00

At Yandex, some employees use Microsoft Visual Studio on Windows for compiling and debugging their code, some use gcc and gdb on Linux or FreeBSD (via ssh). And thus, portability problems arise. Here is one example.

A chunk of new code was written on FreeBSD that, essentially, opens a file (or maybe stdin), determines which plugin (i.e., shared library) to load, and passes the file descriptor to a function in the plugin. A natural design for Unix, however, it doesn't work for Windows: the file descriptors opened with open() are valid only in the same module (i.e., DLL or application) that opened them. It appears that one has to use _get_osfhandle() and _open_osfhandle() Win32 functions to overcome this limitation. That's just ugly.

Just for fun, I also tried to rebuild my own C code (not related to my work at Yandex), on Windows with Microsoft Visual Studio. This, obviously, resulted in problems:

The Microsoft compiler doesn't have such standard C99 headers as <stdint.h>. I had to download this header from the msinttypes project.

When compiling C files, the compiler doesn't recognize the "inline" keyword and the definition for int64_t from the <stdint.h> header doesn't work. Both issues were fixed with the /TP switch that tells the compiler to treat the code as C++.

The compiler warns about the POSIX function open() and suggests to use the "standard" _open() function. What standard does it talk about?

Well, the standard C function for opening files is actually fopen(), so I converted my program to use that. Guess what? A warning saying that fopen() is deprecated and suggesting to use fopen_s() that actually exists only in Microsoft compilers.

The intentions of Microsoft are obvious: to teach people to write programs that will require significant amount of work when porting to other platforms. Thus, if you are a newbie programmer working on Win32, please, switch to a non-Microsoft compiler now, before you acquire any bad habits.

Kernel panic

2008-09-27T06:37:00.000-07:00

When I moved to another room in the office, my laptop started getting this kernel panic. So far, this means that I can't use the wireless network. I can work around this by either blacklisting the iwl4965 module or by turning the wireless card off with the hardware rfkill switch.

Maybe related: this laptop gets "ACPI: EC: non-query interrupt received, switching to interrupt mode" during boot.

I will report this panic to both the debian bug tracker and the linux-wireless list, let's see how they resolve it.

Wrong macro

2008-09-20T03:52:00.000-07:00

Here is how you shouldn't test for old compilers:

#if _MSC_VER < 1400
    /* some workaround */
#endif

Reason: the workaround will also be applied to non-Microsoft compilers, e.g., gcc. Here is a more correct version:

#if defined(_MSC_VER) && _MSC_VER < 1400
    /* some workaround */
#endif

Recording SIP conversations

2008-09-18T08:30:00.000-07:00

My chief prefers to use SIP (voice conversations) instead of Jabber (text messaging). The problem is that he sometimes overloads me with a lot of information, and later I forget 90%. This is not a problem with Jabber, as there are logs. However, I don't know any SIP client that supports recording of conversations out of the box.

Here is my solution. You need alsa-lib 1.0.17 or later (i.e., if you are using Debian Lenny, due to the freeze, you'll have to fetch libasound2 and libasound2-dev from experimental). Create the subdirectory named "voice" in your home directory. Add these lines to $HOME/.asoundrc:

pcm.voice {
        type asym
        playback.pcm {
                type file
                file "/home/user/voice/p"
                slave.pcm "default"
                format "wav"
                truncate 0
        }
        capture.pcm {
                type file
                file "/home/user/voice/c"
                slave.pcm "default"
                format "wav"
                truncate 0
        }
}

Then, configure your SIP client (I use twinkle) as follows. ALSA device for rings: "default", ALSA speaker: "voice", ALSA microphone: "voice", Play back ring tone when the network doesn't: disable. As the result, ALSA library will write the following files into the voice directory: p, c, p.0001, c.0001, p.0002, c.0002, and so on (the number is incremented for each new call). All these files are in wav format, "p" files correspond to the remote side, and "c" files contain what you spoke into the microphone. It appears that it is impossible to record both parties of the conversation into one file using only built-in features that come with ALSA.

To play back the conversation, do:

aplay p.0002 & aplay c.0002

This will cause two aplay processes to be started in parallel, with their outputs mixed. Or, you can make one mixed wav file with sox:

sox -m c.0002 p.0002 -f wav talk0002.wav

gcc-4.3 troubles

2008-09-17T08:53:00.000-07:00

After obtaining access to the CVS server at Yandex, I tried to build some internal utilities for daily use (e.g., for examining database contents) on my work laptop. The first attempt failed, because Debian Lenny comes with gcc-4.3.1, and the official build machines (that I was in fact supposed to use instead of the laptop) still use gcc-4.2.x.

First, some of the "known good" snapshots of external projects that are used by the to-be-built utilities have gcc-4.3 related issues. Fortunately, Debian's bug and package database was very helpful, and I was able to extract the needed patches.

Second, gcc-4.3 added some new warnings, and the build system is set up to use -Werror by default. While some of the new warnings are helpful, others are not. Try, e.g., compiling this simple function with g++ -Wconversion -c test.cpp:


typedef unsigned char uint8_t;
void grow(uint8_t & u)
{
        u *= 7;
}

Result:


test.cpp: In function 'void grow(uint8_t&)':
test.cpp:4: warning: conversion to 'unsigned char' from 'int' may alter its value

I.e., almost every in-place mathematical operation with shorts and chars results in warnings! With -Werror, this means errors in many files. Obviously, this isn't worth fixing, so I removed -Wconversion from the compiler flags in my checkout. Similar bugs are already recorded in GCC bugzilla.

Third, even after fixing fixable warnings and removing -Wconversion, I hit an internal compiler error. Since I found no similar reports (the error manifested itself on proprietary code, after all), I reduced the testcase and submitted it to GCC bugzilla.

After that, I gave up. I posted my changes to the internal code review list (just so that they don't get lost), switched the compiler to gcc-4.2 (it is available in Debian side-by-side with 4.3), and compiled what I needed without further problems.

BTW, Debian still uses gcc-4.1.2 for compiling their kernels. It would be interesting to know why.

New job!

2008-09-16T09:44:00.001-07:00

Since September 15, 2008, I work at Yandex, as a developer in the Image search department. I am busy with bash scripts, C++ and even XML. My work computer is a Fujitsu Siemens S laptop, and I installed Debian Lenny there. One strange thing about this job is that I have never seen my chief: he is in Moscow, and all conversations with him are via Jabber and SIP.

The office in Yekaterinburg is clean, there are nice flowers in front of the building, and my colleagues seem to enjoy working there. Our windows (on the fifth floor) remain lit even at 10 PM.