maxrss

The ru_maxrss field in struct rusage provides a convenient way to measure peak memory usage of a program (via getrusage, wait4, or simply `/usr/bin/time -p') on BSD systems, including Mac OS X. According the man page, ru_maxrss represents `the maximum resident set size utilized (in kilobytes)'.

Let's try it on Mac OS X (Leopard, 10.5.6).
$ /usr/bin/time -l uname -v
Darwin Kernel Version 9.6.0: Mon Nov 24 17:37:00 PST 2008; root:xnu-1228.9.59~1/RELEASE_I386
0.00 real 0.00 user 0.00 sys
385024 maximum resident set size
...

Do you really think the simple `uname' could take 385,024 KB (376 MB) memory ? It also reports 282624 maxrss for a small C program that only contains an empty main and is compiled by `gcc -O2'.

Here is a comparison.

FreeBSD 7.1, kern_clock.c

 527 rss = pgtok(vmspace_resident_count(vm));
 528 if (ru->ru_maxrss < rss)
 529   ru->ru_maxrss = rss;

Note pgtok is often defined as follows.
#define pgtok(x) ((unsigned long)(x) * (PAGE_SIZE / 1024))

Mac OS X 10.5.6, kern_exit.c

 612 p->p_ru->ru_maxrss = tinfo.resident_size;

task.c

1205 if (flavor == TASK_BASIC2_INFO_32) {
       ...
1210   basic_info->resident_size = pmap_resident_max(...);
1211 } else {
1212   basic_info->resident_size = pmap_resident_count(...);
1213 }
1214 basic_info->resident_size *= PAGE_SIZE;

Does Apple forget `/ 1024' or something? Hope Linux would not give a strange number.

Replay

It's so perfect that our replay work R2 finishes with an OSDI acceptance. Just got the news right before saying goodbye to my friends at MSR Asia. Awesome the past two years!

Silas's paper on multicore OS was also accepted. Congratulations!

Welly: Rethink the BBS

In the past month I have been hacking the Welly BBS term client while waiting for the visa approval. I was fortunate to work with some amazing people: aqua, gtCarrera, and KOed, who are nice, young, and smart. I envy them. :-)

The project was initially a fork of Nally, which was developed by yllan and now is maintained by jjgod. It uses Core Text for rendering, much faster than state-of-the-art (ATSUI based) BBS terms on Mac OS X. Nevertheless, we don't want a general terminal application; there are enough good ones. Welly is tailored for exploring BBS, where we can also try fancy stuff for fun, such as Cover Flow and Quick Look integration that I finished recently.




One day Geoff asked me why Chinese prefer such old-fashioned term BBS sites. Yes, this is a little bit weird. It seems that most people, particularly on-campus students, prefer telnet access and the terminal way to present and exchange ideas. Some even spend hours there every day, as I did. We are using terminal emulators that have a history of more than 20 years, though they may be implemented via modern technology. Many term BBS sites also provide Web access and may use AJAX extensively, however, the core parts are derived from aged systems, mostly either Firebird or Maple.

I can still remember the days in 2005, which consequently drove me to get down to preparing for GRE and brought me two awesome years at MSR Asia as well. It changed anything, as least to myself --- I once had a dream of having a good job and a stable life in the city but gave up after the hard time. Thanks to better who stood with me. The immediate issue of Sci-Fi World, the most popular Chinese sci-fi magazine, came up with a Ma Boyong's novel titled The City of Silence, which quoted from the famous song by Paul Simon:

People talking without speaking
People hearing without listening

I guess I might be overacted at that time, but there is no turning back.

Here is the move within a couple of weeks: Beijing => Haikou => Beijing => San Francisco => Boston.

Building CIL on Leopard

Following the standard configure/make approach to build CIL on Mac OS X Leopard (10.5), one may encounter the following error:
Compiling obj/x86_DARWIN/feature_config.ml to bytecode
File "obj/x86_DARWIN/feature_config.ml", line 4, characters 1-2:
Unbound value n
make: *** [obj/x86_DARWIN/feature_config.cmo] Error 2

It is due to the echo command in the file Makefile.in (around line 230):
echo -n " (* EXTRAFEATURES: *)" >> $@
Because Leopard follows the UNIX specification more strictly, the syntax echo -n is no longer supported by /bin/sh.

To fix it, replace echo -n with printf, or use /bin/echo, or just omit the -n option.

See #1940018.

Small Patch for bddbddb

Here's a small bug for bddbddb. If there is a small sized domain (e.g., only 2 functions in the Domain F), and some constant strings in a Datalog file (e.g., 4 additional function names used in the rules), the resulting size of the domain will be out of range (e.g., the size of F is 6 rather than 2, which requires a different bit size) and an exception is raised (e.g., Exception in thread "main" net.sf.javabdd.BDDException: 6 is out of range).

Usually this doesn't hurt because the size of a domain is large enough and it's unlikely to cross the boundary of the BDD size. Though it would fail to compute a call graph for a simple hello-world program.

A possible patch for the method namedConstant in net/sf/bddbddb/Domain.java.

Index: Domain.java
===================================================================
--- Domain.java (revision 654)
+++ Domain.java (working copy)
@@ -114,6 +114,8 @@
        if (false && map == null) throw new
IllegalArgumentException("No constant map for Domain " + name + " in
which to look up constant " + constant);
        if (map == null) map = new IndexMap(name);
        if (!map.contains(constant)) System.err.println("Warning:
Constant " + constant + " not found in map for relation " + name);
-        return map.get(constant);
+        int index = map.get(constant);
+        size = BigInteger.valueOf(index + 1L).max(size);
+        return index;
    }
 }

Another Acceptance

My paper on region safety has been accepted to PLDI 2008. Many thanks to sunnymonkey!

Two Papers Accepted

Both my hang analysis paper submitted to EuroSys 2008 and the online predicate checking paper submitted to NSDI 2008 have been accepted. I'm so grateful for my friends and colleagues at Tsinghua and Microsoft. Bin and Lex's VOD work has also been accepted to EuroSys. Congrats!

Break Changes in VC9

I've been using VC9 (Orcas, or 2008) for a couple of weeks. Well, let's just say maybe newer is better. Here lists some break changes in VC CRT. The list is not complete, at least in my experience of building a number of open source packages. VC CRT misses a bundle of POSIX headers (e.g. stdint.h) and functions (too many!), and it's likely sticking to this tradition. Er, I'd rather say it's also improving. Some packages using libxml may fail to compile on VC9 due to one of the improvements: libxml defines a macro vsnprintf to _vsnprintf for VC (why adding the underscore!), but VC9 provides both functions while previous versions only provide the latter. So the macro redefinition would cause trouble on VC9.

It's said that the next VC release will start using Phoenix as the backend engine. That's good news. But I don't really feel good about the Phoenix IR. Why is it so complicated as most other Microsoft products are? It's ugly. It's hard to analyze and understand. It's even not complete; much important information remains missing in current release. Though it might be a better choice to evaluate analysis algorithms on Java code, I'd rather take C/C++ code as the first choice because most systems are still written in C/C++. I just wish next release of Phoenix SDK targeting on VC9 backend would come up soon, though I could build it from scratch myself.

VCBuild on x64

I was making my static analysis programs as an easy-to-use tool. It's a little weird that VCBuild seemed not work on x64: it did not take the right include/lib path. Even using the /u option, it might fail to link, and the unicode set did not function (it tried to link with the ANSI version of Windows API). So now I use the x86 version rather than the native x64 version. Someone got the similar problem long ago.

Another headache was about Phoenix. I tried to integrate it with Orcas, and finally it worked (VS 2008 beta 2 frontend with a nightly build Phoenix backend) with my own plug-ins. But the compiling performance was really terrific. No idea what was going, it was rolled back to VS 2005.

Visual Studio 2008 Shell

It seems to be alternative RCP solution to Eclipse: Visual Studio IDE serves as a general platform for building client applications. Maybe I'll try it for my next toy:-)

When can we use Ribbon GUI that appears in Office 2007?

APR 1.2.9 on Vista

It fails to compile on Vista again due to inappropriate orders of Windows headers.

Open misc/win32/rand.c, and change

#include <windows.h>
#include <wincrypt.h>
#include "apr.h"
#include "apr_private.h"
#include "apr_general.h"
#include "apr_portable.h"
#include "apr_arch_misc.h"

to

#include "apr.h"
#include "apr_private.h"
#include "apr_general.h"
#include "apr_portable.h"
#include "apr_arch_misc.h"
#include <windows.h>
#include <wincrypt.h>


Recursive Destruction and Stack Overflow

Here's something stupid for C++. I was testing an algorithm using a trie implemented by std::list on some data today, which resulted in a very deep tree. At exit the program crashed, due to recursive destruction: std::list destroyed all its elements, which were also tries. There is a similar vulnerability in PHP, though they use C rather than C++. I'm still wondering how to do this in C++. Pool design may be much better in such cases, especially for parse trees. I think I have discussed this with Nirvana when we were implementing a bencode parser several months ago.

Building PCRE on Windows

My environment is Visual Studio 2005 on Windows Vista for PCRE 7.1. Since PCRE is written in ANSI C, just follow instructions in the doc NON-UNIX-USE. Remember to turn off some macros in config.h such as HAVE_UNISTD_H.

Two weird things here:

1. Define macro NO_RECURSE in config.h if necessary; otherwise running test on data "testinput2" would fail with stack overflow. The current GnuWin32 PCRE 7.0 suffers from this problem.

2. Add a call to _set_printf_count_output(1) at the beginning of main in pcregrep.c; by default VC CRT does not support the format "%n" and the program pcregrep.exe using such format would crash.

Program Analysis using Phoenix

For C/C++, writing a C2 phase plug-in may be the best choice. I prefer to put the analysis phase after the "Type Checker" phase. On the other hand, reading from PE executables requires .pdb (linking with /debug and /profile). A more serious problem is that LIR cannot be raised to HIR in such case, which makes it hard for further analysis. Besides, the alias algorithm seems too conservative, and the SSA algorithm is sometimes a little confusing.

For C#/.NET, writing an analysis tool (stand-alone .exe) is quite simple: set FunctionUnit.HighLevelIRFunctionUnitState for RaisePhase in the generated code. Remember to skip function units with !functionUnit.AliasInfo.IsComplete since they are unmanaged code.

Missing information in Phoenix IR is still a headache, as well as not-so-canonical IR forms. There's a talk with Open64 guys on Wednesday. I'm wondering if Open64 IR or LLVM IR would be better for program analysis. However, Visual C++ is always the ultimate front-end on Windows: other compilers could even hardly parse Windows.h as Microsoft-specific grammars keep growing.

Wrap Vararg Functions

In my mind to wrap a vararg function I have to call its corresponding v-function (e.g. printf and vprintf). For those functions that do not have such counterparts, I intended to use Zhenyu's assembly code to inspect the stack. Last weekend when looking into cURL's source code, I found out that using the va_arg macro and passing the resulting pointer directly to vararg functions worked quite well. It's so easy! Phew!

Hook Unexported Functions

PDB files provide a simple approach to locate and hook unexported functions, especially for those static-linked functions, and usually they can be easily obtained in addition to pre-built release files (e.g. Apache, PHP, Subversion). Moreover, I'm lazy and do not want to modify and recompile a large project such as Subversion to export some internal API functions just for instrumentation. DIA provides a group of convenient interfaces though it is COM:-)

There are some pitfalls as well. First, remember to call the method ISession::put_loadAddress to set the base address of a module before any other invocation, otherwise retrieved function addresses would be invalid. Besides, the documentation of GetModuleInformation which can be used to get the base address of a module is wrong: providing NULL for the first parameter hProcess for current calling process, as is described in MSDN, leads to unexpected failure. Use INVALID_HANDLE_VALUE(-1) or GetCurrentProcess() instead.

Build Apache on Vista

It's reported that APR fails to compile on Vista with the latest SDK. This is due to the new macro MCAST_JOIN_SOURCE_GROUP in Vista. The workaround is quite simple:
1. open the generated apr.h;
2. set _WIN32_WINNT to 0x0600;
3. set APR_HAVE_IPV6 to 1 (or there would be a link error with the function find_if_index).

Btw, just got back to Beijing this morning. Well, there's rather a lot of work to do.

Update1: ASF Bugzilla Bug 40398
Update2: APR 1.2.9 on Vista

Mercury

There is no messenger service in Vista, and I cannot get notifications from the SVN server by "net send". So I use the HTTP Server API in Vista to build a lightweight message delivery service called "Mercury" for receiving notifications (by cURL, for example) and popping up message boxes. It's quite simple, only about 150 lines C++ code. Here are some notes.

1. ATL is of great help for building Windows services.

2. The model of HTTP Server API 2.0 is more flexible, which requires binding handles to URL groups. Notably, HttpAddUrlToUrlGroup returns the error "access is denied" when running as a basic user.

4. I/O cancellation in Vista simplifies the development of asynchronous programs. I've successfully used CancelIoEx to cancel blocking HttpReceiveHttpRequest in another thread; However, CancelSynchronousIo does not work. I'm still trying to figure out why.

4. Services in Vista are running in a separate session so that MessageBox has no effect for user sessions; use WTSSendMessage instead for notifications.

5. The security model in Vista is interesting and sometimes a little boring; set the appropriate privilege level when registering services or attaching processes in Visual Studio.

The Vista Era Begins

I'm on Windows Vista Now. It took me the whole afternoon to migrate all my files from XP to Vista. All applications run well, and my current code also works on Vista: at least the TLS implementation does not change and even low-level instrumentation is fine. It's awesome. Maybe I'll try the new system features later, especially some I/O improvements.

Orcas Sucks

It crashed my Visual Studio 2005 and took me another afternoon to restore the system. So maybe that's why it's suggested to install on a virtual machine. The shipped SDK headers seemed not up-to-date with Vista, for there're quite a lot of annotations missed as far as I've looked into.

By the way, the program of NSDI '07 is out, where waikok published a paper titled WiDS Checker: Combating Bugs in Distributed Systems. Congrats!