royalfern

Write Yourself a Scheme - 1

2009-04-02T05:41:00.000-07:00

Here are the solutions to ``Write Yourself a Scheme in 48 Hours'', "First steps: Compiling and running".

ex1.
main = do args <- getArgs
    putStrLn ("Hello, " ++ args !! 0 ++ ", " ++ args !! 1)

ex2.
main = do line <- getLine
    putStrLn("Hello, " ++ line)

ex3.
str2int s = read s :: Int
str2flt s = read s :: Float

main = do args <- getArgs
    putStrLn (show (str2int(args !! 0) + str2int(args !! 1)))

metaSendsEscape

2009-03-30T19:53:00.000-07:00

Occasionally we can found that the Bash key-binding such as M-f/M-b will not work in XTerm (this happened both in my laptop and desktop), to solve this problem, just press `Control' and left mouse and check the item `Meta Sends Escape' from the main options.

To turn it on permanently, add the following line to configure file '/etc/X11/app-defaults/XTerm':

*metaSendsEscape: true

g_thread_init

2009-03-11T05:37:00.000-07:00

This afternoon I spent almost two hours hunting a memory leak reported by valgrind. It said that there are 2034 bytes definitely lost in g_hash_table_new_full(), but I am pretty sure that g_hash_table_destroy() is invoked with each key been passed to g_free().

The fix turned out to be a slight modification of call sequence to g_thread_init(), from:

create hash table
add hash entry
g_thread_init()
reclaim hash table

to:

g_thread_init()
create hash table
add hash entry
reclaim hash table

then, the error memory leak error just vanished.

debug-set!

2009-02-23T07:12:00.000-08:00

If you wrote a scheme procedure which will recursive too much and exhaust all you stack, guile will print a horrible error message like below:

ERROR: Stack overflow

You might fix your algorithm and make the procedure tail-recursive to get rid of the compliant, or either, for debugging purpose, increase the stack size:

(debug-set! stack 200000)

reconnect

2009-02-18T20:59:00.000-08:00

Several days ago there was a bug reported that our XML-RPC client over SSL will compliant that "no data is available" when trying to read the HTTP header from the server. Since it is a P2-critical bug, I spent a lot of time debugging it immediately.

GDB shows me that "BIO_read()" returned zero when reading the HTTP header, and its manual said that:
A 0 or -1 return is not necessarily an indication of an error. In par-
ticular when the source/sink is non-blocking or of a certain type it
may merely be an indication that no data is currently available and
that the application should retry the operation later.

But finally I can see that when we switching to HTTP from HTTPS, the client works just fine. And later, we are confirmed that the SSL handling in the server side has a race condition and the connection would be shutdown by then.

In order to make the client more robust, I worked our a patch to do reconnection. The result is rather exciting -- I did thousands of XML-RPC calls over a persistent connection, and everything works perfectly.

At last, I am glad to share that, in section 6.3 of "UNIX Network Programming Volume 1", the author described the conditions that a descriptor being select() is ready for read:

b. The read half of the connection is closed (i.e., a TCP connection that has received a FIN). A read operation on the socket will not block and will return 0 (i.e., EOF).

Actually our underlying socket is handled by select() , and I checked that BIO_get_close() really returns 1 when the connection is closed by the server.

1234567890

2009-02-09T06:59:00.000-08:00

$ date -d @1234567890
Sat Feb 14 07:31:30 CST 2009

autoconf

2008-12-08T06:24:00.000-08:00

I submitted another patch to libxr mailing list just now, it is used to fix the small bug in `configure.ac', so that libxr will generate a correct `xr-config.h' when a JSON run-time is found.

I started to contribute to libxr since last Dec., and I consider it my first real participation in OSS development. Yes I've previous experiences writting test suites for openhpi, openipmi and openwsman, during my internship. But frankly speaking, I had few feelings of joy then.

I enjoyed the discussion in E-mail, and I'd like to thank the author of libxr, who gave me a lot of helps.

timeout

2008-12-04T08:06:00.000-08:00

Eventually I managed to add a timeout value in the server side code so that an idle connection will be shutdown [patch] within a given time. The patch is much simpler than what's expected, and at the same time, I realized that I did NOT turn libxr back to non-blocking I/O, but non-buffering I/O.

I solved another problem which blocked our development this afternoon. It turned out to be SSL re-handshake problem -- as I guessed. Adding a Squid proxy between our client and server application is not that transparent as we thought, it will request the server program to do SSL re-handshake.

First git branch

2008-12-03T06:46:00.001-08:00

I just created my first git branch of libxr with the command line:
# git checkout -b non-blocking
# git commit -a

Of course, the first commit is a patch which turns libxr back to non-blocking I/O. The next step is to setup the time out value of waiting incoming HTTP header.

BTW, I am also planning to spare sometime writing a document about libxr, with XeTeX.

P1 bug

2008-12-02T07:17:00.000-08:00

These days I've been occupied by a P1 bug and, unfortunately, the fix is far from ready.

The XML-RPC library we use has a thread pool with each thread serves incoming request, and the thread will not be ripped back to the pool until the client shuts down the connection. The problem is, when the number of established connection prevails the number of worker threads, the following connection will be blocked.

Since the library uses buffered I/O thus blocking, the first step I need to take is to change it back to non-blocking I/O style -- If a connection has been idle for a while, we might have a chance to shut it down.

My brain now is jammed with confusion and I felt quit dizzy, as many newbies who are trying openssl programming. Just too many stuff!

buffered I/O
chained BIO
blocking I/O
non-blocking I/O
BIO with select()

sysnotes

2008-06-03T19:42:00.000-07:00

一直在寻找一个免费托管的软件仓库，昨天下午闲来无事，搜到了sharesource，可以提供svn/hg访问。于是注册了一个项目 - sysnotes，用来放置我的LaTeX笔记。今天上午过来已经便收到确认通知邮件。:)

$ hg clone http://hg.sharesource.org/sysnotes

code injection

2008-06-03T07:53:00.001-07:00

有很多文章关于代码注入，主要过程是用ptrace系统调用attach一个进程，注入代码(shellcode)，然后再detach该进程使得被注入的代码得以执行。通常注入的代码被存放于堆栈中，因为它的大小可以动态调整，并且这些``蛛丝马迹''执行后可以被后续过程调用擦除。然而现代CPU（如 Intel IA32)都包含了NX位，即可修改内存不可执行(writable xor executable)，这使得大部分注入到stack中的shellcode都无法运行，从而提高了系统的安全性。

有许多方法可以绕过该限制，比如： return to libc。作为代码注入的示例，我们可以直接将代码注入到EIP指向的内存区域：
if (ptrace(PTRACE_ATTACH, pid, NULL, NULL) == -1) {
perror("ptrace failed");
exit(-1);
}

waitpid(pid, NULL, 0);
printf("[1] - Process attached\n");

if (ptrace(PTRACE_GETREGS, pid, NULL, &regs)!=-1) {
printf("[2] - Extract register eip (0x%.8x)\n", regs.eip);

for (i=0; i ptrace(PTRACE_POKEDATA, pid, regs.eip+i, *(int*)(injected_code+i));
printf("[3] - Code inserted\n");
}

ptrace(PTRACE_DETACH, pid, NULL, NULL);
printf("[4] - Running Code\n");
其中injected_code即为shellcode首地址，一般以汇编语言书写，如上例as风格汇编代码（当然一般是exece("/bin/sh", ["/bin/sh", NULL], NULL）。由于被注入进程的文本段被修改，这样该进程的行为被修改，这并不是一个好主意。这里仅仅是代码注入的一个简单示例罢了。

INJECTED_LEN是被注入代码的字节长度，可以由size命令获得。

汇编语言的艺术

2008-06-03T06:33:00.000-07:00

Linux下使用汇编语言有很多选择：内联汇编，as或者nasm/yasm，下面是使用 as的例子：
.text
.globl _start
_start:
jmp get_string
print_string:
movl $4, %eax /* __NR_write */
movl $1, %ebx
popl %ecx
movl $6, %edx
int $0x80

movl %eax, %ebx
movl $1, %eax /* __NR_exit */
int $0x80

get_string:
call print_string
.string "hello\n"

这段汇编使用了传统的int $0x80系统调用，这里最重要的窍门是怎样获取字符串的首地址(call/popl)。这个小技巧使得生成的代码是位置无关的(PIC - Position Independent Code)。这在code injection中注入shellcode非常普遍。

Vim tips for SVN

2008-05-27T06:32:00.000-07:00

function! SVN_diff()
let fn = expand('%:p')
vnew +setl\ ft=diff\ bt=nowrite
exe ":.!svn diff -r BASE " . fn
unlet fn
endfunction

map ,v :call SVN_diff()

Paste above code in your ~/.vimrc, then you can use `,v' to display a diff in a vertical-split window.

volatile

2008-03-31T22:56:00.000-07:00

[Original: ] http://www.airs.com/blog/archives/154

The volatile qualifier in C/C++ is widely misunderstood. Because it is described so vaguely in language standards, many people interpret it as a do-what-I-mean qualifier.

What the standard says is that accesses to volatile objects must be evaluated strictly according to the abstract machine defined by the language standard; this means that if the C/C++ code reads the volatile object twice, then the machine code must do so as wel. The standard says that volatile objects must be stable at sequence points; this means, approximately, that in between statements all reads and writes of volatile objects must have been completed–the value may not be cached in a register. The standard makes clear that it is possible that the values of volatile objects may change in some unknown way between accesses.

One relatively unimportant misunderstanding is due to the fact that the standard only talks about accesses to volatile objects. It does not talk about accesses via volatile qualified pointers. Some programmers believe that using a pointer-to-volatile should be handled as though it pointed to a volatile object. That is not guaranteed by the standard and is therefore not portable. However, this is relatively unimportant because gcc does in fact treat a pointer-to-volatile as though it pointed to a volatile object.

A way to think about volatile is to observe that it was invented to support memory mapped hardware. Some hardware is controlled by accesses to specific memory addresses. For example, a serial controller often handles input by setting a bit in one memory location and making the new byte available in another memory location. The kernel code must observe that the bit is set, read the byte, and set another bit to tell the serial controller that the byte has been read (I’m skipping the interrupt which is also involved). These accesses should use volatile to make sure that they happen in the exact order written in the program.

The standard also explicitly describes two other uses of volatile. One is for setjmp and is relatively uninteresting. The other is that a variable of type volatile sig_atomic_t may be set in a signal handler and read by code outside the signal handler. In fact, just about all that a portable signal handler may do is set such a variable.

For dealing with memory mapped hardware, volatile is exactly what you want. For most other types of code, including multi-threaded code, volatile does not help.

Using volatile does not mean that the variable is accessed atomically; no locks are used. Using volatile does not mean that other cores in a multi-core system will see the memory accesses; no cache flushes are used. While volatile writes are guaranteed to occur in the program order for the core which is executing them, there is no guarantee that any other core will see the writes in the same order. Using volatile does not imply any sort of memory barrier; the processor can and will rearrange volatile memory accesses (this will not happen for address ranges used for memory mapped hardware, but it will for ordinary memory).

Conversely, if you use the locking primitives which are part of any threading library, then you do not need to use volatile. The locking primitives will include the required memory barriers or cache flushes. They will include whatever special directives are needed to tell the compiler that memory must be stable.

There is one case where volatile may be used for multi-threaded programming with some reliability. You may use a single volatile sig_atomic_t variable to communicate between threads, much as you may use such a variable to communicate between a signal handler and the main program. You should not use more than one such variable to communicate between any pair of threads, as there is no guarantee that the different threads will see the accesses in the same order.

In summary, if you are using volatile for anything other than manipulating memory mapped hardware, or for very limited communication between threads, it is very likely that you are making a mistake. Think carefully about what volatile means and about what it does not mean.

CJKbookmarks with dvipdfm

2008-03-28T08:33:00.000-07:00

Today I eventually managed to create a PDF file with Chinese bookmark.
Suppose the LaTeX source file is foo.tex:

Insert the following code into preamble section:
\usepackage[CJKbookmarks,dvipdfm,bookmarksnumbered=true,%
colorlinks=true,linkbordercolor={1 1 1},%
linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
The following command line create the PDF file.

latex foo.tex
gbk2uni foo.out
latex foo.tex
dvipdfm foo.dvi

The linkbordercolor option will change the color of link border to white other than the default red color.

A couple of Bash tips

2008-03-27T06:36:00.000-07:00

Single instance
# make use of bash `set -C'
(set -C; : > $lockfile) 2>/dev/null
if [ $? -ne 0 ]; then
log_msg "$0 already running, exit"
exit 0
fi
Daemonize script
# `-d' option indicates to daemonize
if [ x"$1" = "x-d" ]; then
$0 2>&1 >/dev/null &
exit 0
fi

First GDB Script

2008-03-11T00:41:00.000-07:00

Here I added my first GDB macro functions in the file $HOME/.gdbinit to dump the content of task array.

define tasks
x/210u *((unsigned int*) tobj+1)
end
document tasks
Display content of tasks.
end

The array is of 210 machine words long and it's easy to use awk to format the output neatly.

symbol-file

2008-03-07T23:46:00.000-08:00

Although still I do NOT know now to extract a symbol file from
unstripped binary executable, but seems I got a solution. -_-

% echo "int main(void) {return 0; }" > foo.c
% gcc -ggdb foo.c -o foo.gdb
% gcc -s foo.c -o foo
% gdb -q foo
(no debugging symbols found)
Using host libthread_db library "/lib/libthread_db.so.1".
(gdb) b main
Function "main" not defined.
Make breakpoint pending on future shared library load? (y or [n]) n
(gdb) symbol-file foo.gdb
Reading symbols from /home/david/foo.gdb...done.
(gdb) b main
Breakpoint 1 at 0x8048352: file foo.c, line 1.
(gdb) l
1 int main(void) {return 0; }
(gdb)

How to Generate Symbol file?

2008-03-06T07:56:00.000-08:00

I wonder how to generate symbol file from binary executable under GNU/Linux?

I googled a lot and tried the following but with no luck. x-(

nm -n
objdump -h -S
objdump -t

GDB 'symbol-file' always complaint:
can't read symbols: File format not recognized.

Assertions

2007-09-05T20:27:00.001-07:00

[From] http://xmlrpc-c.sourceforge.net/doc/libxmlrpc.html

The concept of assertions in code is widely misunderstood, because it is somewhat more abstract than C coders are used to. An assertion is a statement in code that declares a certain fact to be true. It doesn't make it true; it just declares that the coder knows it is true. In a standard C library, the assert() function performs this duty.

But what does the statement cause the computer to do? If you're a high level coder, that's none of your business. You write code to describe the solution to a computational problem, and how the computer manipulates itself to compute the solution is beyond your concern. Your audience is the human reading your code.

So the most basic function of an assertion is to help the reader read the code. You assert that the value of variable foo is not zero, and that helps the reader see that it won't cause a problem to divide by it.

Another practical effect of an assertion could be that the compiler generates more efficient code with the additional information from your higher intelligence about how the program works. But I've never seen any actual compiler capable of that.

An assertion might also help the compiler to point out bugs in your program. You assert that the value of foo is zero, but you never initialized foo, so you obviously didn't write the program you thought you did. But I've never seen a compiler with that capability either.

Finally, there is run time checking of the assertion. This one is real. At run time, the program checks that the condition asserted really is true. If it isn't, which means the program is broken, it crashes itself. The advantages of this are twofold: 1) this makes it easier to diagnose the bug; 2) it stops the broken program from going on to damage something.

People often have trouble seeing the abstract meaning of an assertion and simply see it as a statement that tells the computer, "crash if X is not true." But in fact, it's quite the opposite: It says, "I assure you X is true."

People sometimes get the idea that assertion statements are for error checking. That is definitely not what they are for. If there is a possibility that X is false when the program is working as designed, you should not assert that X is true. Instead, check the truth of X and if it's false, issue an error message or exit the program or return with a failure return code, or something like that.

Incidentally, a common way you know something is true inside a subroutine is that you required as an entry condition to the subroutine that the caller make sure it is true. A subroutine assumes that it's entry conditions are met, so if you set up the requirement that the caller pass only positive values for parameter X, you may legitimately assert inside the subroutine that X is positive. In fact, that assertion is a good formal way to state that entry condition for the reader of the code.

High-order Procedures

2007-05-24T22:20:00.000-07:00

Most modern programming languages provide certain abilities to blur the traditional distinction between ``passive'' data and ``active'' process, one of the most well-known techniques might be so-called OOD, i.e., Object Oriented Design. Languages such as Lisp in traditional way provide programmers the power to handle precedures as data, which pioneered a new programming flavor called Functional Programming, or, FP in short (Now some FP languages also implemented OO facilities). Procedures that manipulate procedures are called higher-order procedures.

Put aside the consideration of efficiency, we can implement some atomic operations such as cons, car and cdr like following:

(define (cons x y)
  (lambda (f) (f x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

Here, cons just returns a procedure which takes x and y as parameters. car and cdr applies the procedure constructed above with parameter (a procedure) which returns the former and latter parameter, respectively.

Generator

2007-05-14T09:10:00.000-07:00

Languages like Python, Ruby provide a keyword `yield' to help build a generator. It's really convenient for programmers who hate C-style static local variables, which indicates not thread-safe. For example:

def sequence(start):
  current = start
    while True:
      yield current
      current = current + 1

#Create a new sequence generator starting at 1
generator_func = sequence(1)
print generator_func.next() #prints 1
print generator_func.next() #prints 2
print generator_func.next() #prints 3

Languages support functional programming needn't craft a `yield' keyword (most of them support another more general mechanism named `continuation'). We can easily build a generator like above use Scheme:

; helper procedure to construct a simple generator
(define (make-iter start step)
  (lambda ()
    (let ((old start))
      (begin (set! start (+ start step))
          old))))

; a generator which starts from 1 and steps 1 on each accumulation
(define sequence (make-iter 1 1))

(sequence) ; evaluates 1
(sequence) ; evaluates 2
(sequence) ; evaluates 3

Fast Exponential

2007-05-13T22:07:00.000-07:00

Generally, we can compute exponentials in a linear-recursive way.
For example: exp(b, n) = b * b * ... * b which requires n steps.

But there is a faster approach which makes use of successive squaring, for instance, to compute exp(b, 8):
b^2 = b * b
b^4 = b^2 * b^2
b^8 = b^4 * b^4

This method needs only 3 steps instead of 8, and works fine or exponents that are powers of 2. Of course we can expand this to general usage with the help of the following rules:
b^n = (b^(n/2))^2 if n is even;
b^n = b* (b^(n-1)) if n is odd.

So, we can compute exp(b, n) with time complexity costs O(logn) rather than O(n).

Inspired by this method, you can even find a cleverer algorithm to compute the Fibonacci numbers in a logarithmic number of steps.

Some Lessons

2007-05-09T00:38:00.001-07:00

There are some important ideas in algorithm and program design:

There is more than one way to do it.
Your first task is to find a correct algorithm. After that, strive for clarity,simplicity, efficiency, scalability and elegance. Good algorithms and programs are like poems of logic. They are a pleasure to read and maintain.
Be the computer.
Grand Master Turing once dreamed that he was a machine. When he awoke he exclaimed: "I dono't know whether I am Turing dreaming that I am a machine, or a machine dreaming that I am Turing!"
Generality is good.
Don't reinvent the wheel.
As you are learning to program, designing from scratch is great experience. Truly expertprogrammers, however, know when to borrow.

-- 7.5.5 Some Lessons

Science is organized knowledge. Wisdom is organized life.
-- Immanuel Kant

What is Computer Science?

2007-05-04T20:09:00.000-07:00

You might be suprised to learn that computer science is not the study of computers. A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy. The computer is an important tool in computer science, but is is not itself the object of study. Since a computer can carry out any process that we we describe, the real question is What process can be describe? Put another way, the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question. The three main ones are design, analysis, and experimentation.
-- Python Programming: An Introduction to Computer Science, section 1.3

Function v.s. Procedure

2007-04-24T22:06:00.001-07:00

The contrast between function and procedure is a reflection of the
general distinction between describing properties of things and
describing how to do things, or, as it is sometimes referred to, the
distinction between declarative knowledge and imperative
knowledge. In mathematics we are usually concerned with declarative
(what is) descriptions, whereas in computer science we are usually
concerned with imperative (how to) descriptions.

-- SICP, 1.1.7 Example: Square Roots by Newton's Method

SICPing again

2007-04-22T07:37:00.000-07:00

We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.

-- SICP, Chaper 1, Building Abstractions with Procedures

Goodbye

2006-10-09T19:38:00.000-07:00

After 15 months spent at Shanghai, now I need go back to Chengdu to finish my M.S. degree, eventually.

It's interesting that my last post was named "New Start". It is exactly another new start for me tonight. I am thirsty for the experience of staying at the train, and enjoying the different scenery on the way, just like the way of our life with specific characters each period.

Maybe most of the time we can not choose what to do following our inclinations. Now I must go without any alternative. Still there is a good side, I have a dream, that the next year I can meet again with my friends here.

Two suggestions to myself before leaving Shanghai:
o Keep doing sports;
o Regularize work and rest;

Goodbye, guys. See you again next year.

New Start

2005-08-30T02:18:00.000-07:00

Throw out the old spymac blog, now using this new one. :)