Tech rider

CLSF 2011 - Day 2

2011-11-01T03:04:00.000-07:00

The second day of CLSF 2011 started with Wu Fengguang's IO-less throttling. It is a continuous work from last year. Fengguang has done great work in improving Linux kernel read-ahead. And in the last two years, he is working on improving writeback.

There are many dirty page writeback path in Linux kernel: fsync(), sync(), periodic writeback, backgroud writeback, balance_dirty_pages() and page reclaim path. Among them, balance_dirty_pages() and page reclaim path are worst for performance because they tend to writeback random single page. The purpose of balance_dirty_pages() is to balance page dirtying and page writeback, so that task doesn't cause too much memory pressure. Currently, balance_dirty_pages() calls writeback_inodes_wb() to writeback dirty pages. What Fengguang does is to adjust balance_dirty_pages() to:
1. let dirtier task sleep instead of initiate writeback in balance_dirty_pages(), so flusher can start writeback when necessary;
2. make page dirtying and writeback speed matching smoothly so that page reclaim is avoided as much as possible;
3. balance the dirty speed of each memory dirtier so that large writer don't eat all memory causing smaller writers stall for a long time.

There are a few parameters to tune and the most important one is how long dirtier should task sleep, which takes into account current disk write bandwidth, system memory pressure and task dirtying speed.

The whole patchsets are referred as IO-less throttling and are getting merged in 3.2 merge window as decided in Kernel Summit last week. It is really a time-consuming critical work that needs brilliant and patient mind. Fengguang said he draw more than 10K performance graphs and read even more in the past year.

While the IO-less throttling patches help improving writeback performance, Coly and Ma Tao said they are more interested in a side effect of the patches, per-task buffer writer bandwidth control. The problem comes with current implementation of blkio cgroup, which calculates IO bandwidth on the task that submitted bio. However, for buffer write, the pages are most likely written back by flusher thread. So the blkio controller does not work for buffer write. But Fengguang's IO-less throttling gives another way -- control write speed at balance_dirty_pages(). Fengguang said it should be possible and easy for balance_dirty_pages().

The second topic is memory management discussion led by Li Shaohua. We mainly discussed some issues found in Taobao's/Baidu's data centers. The first issue Coly presented is whether swap-off on all-in-memory service servers. When swap on, performance may get hurt when pages are swapping out, while swap off, oom-killer is easy to trigger when applications uses too many memory. The real problem is that application doesn't know about system memory pressure (malloc doesn't fail at all) until oom. A possible solution would be to send sigfault to application when system reaching memory high watermark. Xie Guangjun from Baidu, commented that swap is on in their deployment. Only small databases are all-in-memory. For file data, they use auto tiering, and their search engine applications are not allowed to allocate memory dynamically...

Another issue in Taobao is about SSD+HD auto tiering. HD data cache hit ratio is very low. As a result, when there is a cache miss in SSD, reading from HD is very slow (avg 3 IO per file, dentry, inode, data). Possible solutions:
1. Use cgroups to control memory for SSD and HD, to keep HD buffers cache in memory.
2. Use DIO to read these small data, to avoid wasting page cache for HD data.
3. create a new zone, use bdi->mapping flag to specify which zone to alloc memoroy for device, for the same reason as 1.

Also it is mentioned that memcg count buffer cache to first users but it is unfair. Possible solution would be to create a task struct for each bdi and count these pages to bdi task.

In the afternoon, first I led a session on pNFS discussion. The first issue is how much layout client should be asking for IO. Current pNFS client only asks 4KB length of layout in writepages, even if the wbc requires much more. Fengguang agreed that client has the information of how much to writeback and it is a pity to drop the information letting server do a wild guess. Then I presented the idea of making pNFS Linux a full POSIX client. It is technically do-able but the main reason (for EMC) would be business need.

After that, Xie Guangjun led a session about Baidu's work in their data centers. The first change is to use memcg to guild oom-killer. They make mapreduce jobtracker send down memory limit per task, then task tracker creates new task with memory limit (now use cgroups) and oom-killer kills all processes in the same cgroup.

Another interesting thing is that, Baidu is building a global resource manager in their data center. The idea is similar to Hadoop's new resource manager in MDS will be a general purpose one. Guangjun mentioned that Google has a similar implementation in their data center as well.

The most interesting thing from Baidu is their work on flash. In current deployment, they build SSD from NAND with MTD+UBI+LVM. It is a joint work together with Huawei and fully implemented the functionality of mysterious FTL. In the future,they will build the SSD such that it bypasses whole VFS layer and uses ioctl API to do read/write/trim. It seems that even with some of Nick Pidgin's scalability patches merged, Linux VFS is still a hot pot of lock contention for high speed storage. In our previous training from Whamcloud, they came to the same conclusion and are planning to drop VFS interface in the future.

After Baidu, Intel performance team let a discussion about the impact of emerging new hardware on current system architecture, namingly SSD and PCM. SSD is already changing system architecture in Baidu. PCM is likely to be even more evolutionary, even removing the need for current complex implemented file systems. However, it is still way far in the future. We need to focus on what we have at hand.

That's all for the two days event. I didn't mean to write so long stories but all the above are worth documenting. So I can't drop any of them...

In the end, thanks Baidu and Fujitsu for their generous sponsorship. Thank you all CLSF committees for making this happen. And thanks EMC for sending me there. It is really a valuable experience and will benefit me for quite a long time.

CLSF 2011 - Day 1

2011-11-01T03:03:00.000-07:00

One year passed since last CLSF2010 in Shanghai. This year, CLSF is held in Nanjing and sponsored by Baidu and Fujitsu. And Coly has kindly built an official website for the event.

The workshop started with Btrfs updates given by Fujitsu's Zefan Li. Fujitsu has been contributing a lot to btrfs development this year. The first important feature Fujitsu developed for btrfs is LZO transparent compression. Before, btrfs only uses Zlib but the infrastructure allows adding more compression algorithms. LZO consumes less CPU and is faster than Zlib. The current compression unit is extent (at most 160KB) and every RW needs to read/write whole extent. So the feature seems to be more suitable for SRSW use case.

Another interesting feature added to btrfs is auto-defragment. Copy-on-write filesystems like btrfs/WAFL all suffer from file fragmentation. So btrfs tries to (sort of) solve it in a nice and easy way. When a page is written, btrfs tries to read in the extent around current page and mark pages dirty in memory. So later writeback can write continuous blocks and ondisk extents tend to be less fragmented. However, a side effect is that it causes more IO than necessary and may hurt random write performance. While the idea of auto-defrag is cool, defragmentation consumes resources and thus timing is very important. What is the best time for starting auto-defrag and how far it should go (e.g., 5 frags into 4 may not be worth doing at all) remains still a open question.

Miao Xie also introduced btrfs tree log and sub-transaction feature. Before tree log, btrfs maintains a big transaction (default 30sec) and if user fsync one file, the whole transaction has to be committed, hurting very much the performance of other writers. With tree log, btrfs maintains a write-ahead on-disk log for each of such fsync operations. And when transaction commits, it discards all these logs. As a result, fsync one file will only result in writing back the file's dirty data in tree log and other writers can continue writing to the same transaction, which improves performance in many writers with fsync use case.

One defect of tree log is that, when writing new logs, it also writes all old logs (again and again). The solution is to assign a sub-transaction id to each log and use it to avoid writing old logs. And it improves performance in large file many fsync use case.

One question that we are all interested is when btrfs will be suitable for production. Currently the most concern is about btrfsck, which has been delayed for years. Although btrfs has built-in RAID and scrub (which rebuilds broken RAID block automatically), people still think fsck a must. Zefan explained that Chris Mason will demo btrfsck at LinuxCon later this month. The reason he (Chris) didn't release btrfsck for so long is that he was trying different designs/implementations and do not want to corrupt user data with half-done btrfsck. Good news is that Chris is pushing btrfs into Oracle's next release UBL.

The last but most important question for btrfs is performance. According to Intel guys' tests, btrfs is slower than ext4 in many cases. Some argued that btrfs presents many fancy features ext4 don't. But these features are more attractive to desktop users than to server users, and server users are the real force to push Linux kernel going forward these days.

The second topic is Distributed/cluster storage and cloud, led by Novell's Zhang Jiaju. This is a general talk about open source cloud infrastructure. Distributed systems put a lot of pressure on DLM and sometimes make DLM itself too heavy. We also discussed why Lustre isn't wildly used outside of HPC market. Jiaju thought the most important reason is Lustre is not merged in Linux kernel thus enterprise users do not trust them as much as Kernel filesystems even like ceph.

Jiaju maintains corosync in SUSE Linux and made an implementation of Paxos. Paxos came into people's eye because of Google Chubby. He also introduced a little about corosync's Totem. Totem performs better than Paxos when cluster membership doesn't change. But we all agree that quorum is not the best way to solve large cluster synchronization problem and that's why common Chubby cluster only have several machines.

That's all for the morning. Bellow is we are continuing discussion during lunch break.

Taobao holds first two sessions in the afternoon.Taobao is using ext4 heavily in many of their servers and they are particularly interested in some features. First is Ted's bigalloc, which tries to allocate larger chunk of data and is useful for large sequential write applications like HDFS. One issue with bigalloc is directory. With bigalloc, minimal 1MB block for each directory is certainly a waste. Ma Tao has sent out preview patches , the main idea is to make use of the inode xattr space to store the inline data.

Metadata checksum, snapshot and compression are also in Taobao's eyes. Meta checksum is mainly for debug purpose. When file system corrupts, people can first check meta checksum. If checksum doesn't agree, it is very likely a disk problem instead of file system bug. However, it doesn't help no journal mode. For snapshot, Yang Yongqiang is actively working on it.

The third topic in the afternoon is block layer updates, led by Li Shaohua. The most important change in block layer is the dropping of IO barriers, in favor of FLUSH/FUA. IO barrier has been there for a very long time. They are a concept in the block layer, implemented via FLUSH/FUA and serve two purposes: request ordering and forced flushing to physcial medium. Both block layer and disk cache may queue/reorder io requests. IO barriers ensure preceding requests are processed before the barrier and following requests after. Also they ensure that all data in disk write cache are flushed before returning.

IO barriers are well-known as performance killers. However, enforcing ordering with IO barriers at block layer is more than enough. Filesystems just want to ensure some important requests to get to disk, instead of EVERYTHING sent to block layer privier to IO barriers. Filesystems should concern themselves with ordering, since that's where the information is, and not dump that problem into the block layer. A filesystem which wants operations to happen in a specific order will simply need to issue them in the proper order, waiting for completion when necessary. The block layer can then reorder requests at will.

The resolution is to export FLUSH/FUA and let filesystems decide. Therefore REQ_HARDBARRIER no longer exists, while REQ_FLUSH and REQ_FUA are added. REQ_FLUSH request forces the write cache to be flushed before beginning the operation, and REQ_FUA means the data associated with the request itself must be committed to persistent media by the time the request completes.

So the procedure of write has changed from:
submit_bio(WRITE_BARRIER)
other reqs -> (wait)preflush -> (wait)bio reqs-> (wait)postflush -> other reqs
to:
submit_bio(WRITE_FLUSH_FUA)
other reqs -> preflush -> other reqs -> (preflush finishes) bio reqs -> other reqs -> (bio reqs finish) postflush

For both cases, if device supports FUA, the bio reqs are issued with REQ_FUA flag and the postflush is omitted. Apparently, the performance gain comes from the fact that one transaction on longer need to wait for IO requests of other transactions, at the cost of letting file systems maintain the dependency of different io requests.

The last session is a from industry session led by Huawei's chief scientist Hu Ziang. Ziang asked some questions for their engineers and then introduced Huawei's Linux strategy. Huawei used to be a very closed company but now they are seeking to get open and embrace Linux and open source. They will build a very large Linux developer team in near future. Good news for China Linux community.

That's all for the first day of excitement.

X86 Calling Conversion

2011-09-02T21:54:00.000-07:00

Wikipedian has some definition: a calling convention is a scheme for how functions receive parameters from their caller and how they return a results.

Basically, it is a compiler ABI and varies on different platforms (like Windows and Linux). This is interesting and useful for debugging (at least for understanding how debuggers work...).

For example, a simple piece of code:

  1 void f(int arg1, int arg2, int arg3, int arg4, float arg5, int arg6, float arg7,

  2         float arg8, int arg9, int arg10, int arg11, int arg12)

  3 {

  4         printf("%d %d %d %d %f %d %f %f %d %d %d %d\n",

  5                 arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8, arg9,

  6                 arg10, arg11, arg12);

  7 }

  8

  9 void main()

 10 {

 11         f(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);

 12 }

On Linux i386, above compiles to assembly:

[SID@test]$cc a.c -o a

a.c: In function ‘f’:

a.c:4: warning: incompatible implicit declaration of built-in function ‘printf’

[SID@test]$objdump -d a > a.s

In a.s, we can see the main function calls f function by passing every argument through the stack.

160 0804842e :

161  804842e:       55                      push   %ebp

162  804842f:       89 e5                   mov    %esp,%ebp

163  8048431:       83 e4 f0                and    $0xfffffff0,%esp

164  8048434:       83 ec 30                sub    $0x30,%esp

165  8048437:       c7 44 24 2c 0c 00 00    movl   $0xc,0x2c(%esp)

166  804843e:       00

167  804843f:       c7 44 24 28 0b 00 00    movl   $0xb,0x28(%esp)

168  8048446:       00

169  8048447:       c7 44 24 24 0a 00 00    movl   $0xa,0x24(%esp)

170  804844e:       00

171  804844f:       c7 44 24 20 09 00 00    movl   $0x9,0x20(%esp)

172  8048456:       00

173  8048457:       b8 00 00 00 41          mov    $0x41000000,%eax

174  804845c:       89 44 24 1c             mov    %eax,0x1c(%esp)

175  8048460:       b8 00 00 e0 40          mov    $0x40e00000,%eax

176  8048465:       89 44 24 18             mov    %eax,0x18(%esp)

177  8048469:       c7 44 24 14 06 00 00    movl   $0x6,0x14(%esp)

178  8048470:       00

179  8048471:       b8 00 00 a0 40          mov    $0x40a00000,%eax

180  8048476:       89 44 24 10             mov    %eax,0x10(%esp)

181  804847a:       c7 44 24 0c 04 00 00    movl   $0x4,0xc(%esp)

182  8048481:       00

183  8048482:       c7 44 24 08 03 00 00    movl   $0x3,0x8(%esp)

184  8048489:       00

185  804848a:       c7 44 24 04 02 00 00    movl   $0x2,0x4(%esp)

186  8048491:       00

187  8048492:       c7 04 24 01 00 00 00    movl   $0x1,(%esp)

188  8048499:       e8 26 ff ff ff          call   80483c4 

189  804849e:       c9                      leave

190  804849f:       c3                      ret

Then on X86_64 Linux, the code compiles into following, where parameters are passed to f function through three ways: general purpose registers (di, si, dx, cx, r8d, r9d), xmm registers (xmm0~xmm2), and function stack.

159 000000000040054b :

160   40054b:       55                      push   %rbp

161   40054c:       48 89 e5                mov    %rsp,%rbp

162   40054f:       48 83 ec 20             sub    $0x20,%rsp

163   400553:       c7 44 24 10 0c 00 00    movl   $0xc,0x10(%rsp)

164   40055a:       00

165   40055b:       c7 44 24 08 0b 00 00    movl   $0xb,0x8(%rsp)

166   400562:       00

167   400563:       c7 04 24 0a 00 00 00    movl   $0xa,(%rsp)

168   40056a:       41 b9 09 00 00 00       mov    $0x9,%r9d

169   400570:       f3 0f 10 15 60 01 00    movss  0x160(%rip),%xmm2        # 4006d8 <__dso_handle+0    x30>

170   400577:       00

171   400578:       f3 0f 10 0d 5c 01 00    movss  0x15c(%rip),%xmm1        # 4006dc <__dso_handle+0    x34>

172   40057f:       00

173   400580:       41 b8 06 00 00 00       mov    $0x6,%r8d

174   400586:       f3 0f 10 05 52 01 00    movss  0x152(%rip),%xmm0        # 4006e0 <__dso_handle+0    x38>

175   40058d:       00

176   40058e:       b9 04 00 00 00          mov    $0x4,%ecx

177   400593:       ba 03 00 00 00          mov    $0x3,%edx

178   400598:       be 02 00 00 00          mov    $0x2,%esi

179   40059d:       bf 01 00 00 00          mov    $0x1,%edi

180   4005a2:       e8 1d ff ff ff          callq  4004c4 

181   4005a7:       c9                      leaveq

182   4005a8:       c3                      retq

183   4005a9:       90                      nop

184   4005aa:       90                      nop

185   4005ab:       90                      nop

186   4005ac:       90                      nop

187   4005ad:       90                      nop

188   4005ae:       90                      nop

189   4005af:       90                      nop

So why the difference? Basically this is part of System V AMD64 ABI convention which GCC and ICC (Intel compiler) implements on Linux, BSD and Mac and which defines that rdi, rsi, rdx, rcx, r8, r9 can be used to pass down integer parameters and xmm0-7 can be used to pass down float point parameters.

This leads to another question, why not other registers? On X86_64, there are 16 general purpose registers that can save integers (rax, rbx, rcx, rdx, rsi, rdi, rbp, rsp r8~r15), and 16 xmm registers that can save float points (xmm0~xmm15). They are divided by compiler ABI into volatile and non-volatile registers. Volatile registers are scratch registers presumed by the caller to be destroyed across a call. Nonvolatile registers are required to retain their values across a function call and must be saved by the callee if used. So volatile registers are naturally suitable for function arguments while there is overhead of using non-volatile registers (must be saved).

The calling conversion ABI is basically about which register is volatile/non-volatile, which is reserved for specially purpose (parameter passing, frame pointer, stack pointer, etc.), what is the order of arguments on stack, who (caller or callee) is responsible for cleaning up the stack, as well as stack layout/alignness.

Architecture	Calling convention name	Operating system, Compiler	Parameters in registers	Parameter order on stack	Stack cleanup by	Notes
64bit	Microsoft x64 calling convention	Windows (Microsoft compiler, Intel compiler)	rcx/xmm0, rdx/xmm1, r8/xmm2, r9/xmm3	RTL (C)	caller	Stack aligned on 16 bytes. 32 bytes shadow space on stack. The specified 8 registers can only be used for parameter number 1,2,3 and 4.
64bit	System V AMD64 ABI convention	Linux, BSD, Mac (GCC, Intel compiler)	rdi, rsi, rdx, rcx, r8, r9, xmm0-7	RTL (C)	caller	Stack aligned on 16 bytes. Red zone below stack.

The above table is only for either user space application or kernel space functions. Likewise, there is always an exception. Here the exception is system calls. System calls trap user space context into kernel space and have specially requirement for parameter passing:
1. User-level applications use as integer registers for passing the sequence %rdi, %rsi, %rdx, %rcx, %r8 and %r9. The kernel interface uses %rdi, %rsi, %rdx, %r10, %r8 and %r9.

2. A system-call is done via the syscall instruction. The kernel destroys registers %rcx and %r11.

3. The number of the syscall has to be passed in register %rax.

4. System-calls are limited to six arguments, no argument is passed directly on
the stack.

5. Returning from the syscall, register %rax contains the result of the system-call. A value in the range between -4095 and -1 indicates an error, it is -errno.

6. Only values of class INTEGER or class MEMORY are passed to the kernel.

CLFS 2010

2011-09-01T04:05:00.001-07:00

I wasn't able to write down the details about CLFS (China Linux Filesystem and Storage workshop) last year (too busy at that time...). But luckily, I have written this slide to recode the major events in it. Here it is...

CLFS 2010

View more presentations from bergwolf

Virtual Machine File System

2011-09-01T04:02:00.000-07:00

VMFS is an interesting paper. It tells us how VMware builds its high performance SAN file system. Since I was writing file system in ESX kernel in the passed year, I feel I got a good position in understand VMFS's designs and intentions. Here is the summary slides about it. I did my best to make sure no confidential information are leaked. All sentences and pictures are either from the paper or from Internet.

vmfs intro

View more presentations from bergwolf

Google Megastore

2011-09-01T03:52:00.000-07:00

Reading google's infrastructure paper is always joy, of which I have just had one recently. Google's megastore presents how Google builds transactional service on top of bigtable. Here is the slide I wrote about it...

Google Megastore

View more presentations from bergwolf

RCU

2011-09-01T03:47:00.000-07:00

RCU had been a mystery to me for quite a long time. I finally had sometime to walk it through and understand what happened and why. Here is the slide I presented to guys on Auguest's linuxfb.net (@linuxfb) seminar...

RCU

View more presentations from bergwolf

Several filesystem related trees (0)

2009-12-04T05:11:00.000-08:00

Coly has given an intro to the B_tree algorithm in Nov.'s linuxfb.org seminar. Here I'm going to extend his introduction to a brief overview of several file system related trees.

Following is a list of trees I plan to write about(might be extended). I hope I can finish the list before the end of 2009 :)

1. B_tree
2. b+tree
3. Htree
4. Dancing tree
5. Hash tree
6. Tiger tree
7. rb-tree

glibc malloc implementation

2009-09-18T20:31:00.000-07:00

I've been asked several time in interviews how libc implements malloc function. So here I give the a simple summary.

First, I'd like to copy some simple malloc implementation found from Internet.
simple explaintion of malloc:

struct mem_control_block {
 int is_available;
 int size;
};

1. If our allocator has not been initialized, initialize it.
2. Add sizeof(struct mem_control_block) to the size requested.
3. start at managed_memory_start.
4. Are we at last_valid address?
5. If we are:
A. We didn't find any existing space that was large enough
-- ask the operating system for more and return that.
6. Otherwise:
A. Is the current space available (check is_available from
the mem_control_block)?
B. If it is:
i) Is it large enough (check "size" from the mem_control_block)?
ii) If so:
a. Mark it as unavailable
b. Move past mem_control_block and return the pointer
iii) Otherwise:
a. Move forward "size" bytes
b. Go back go step 4
C. Otherwise:
i) Move forward "size" bytes
ii) Go back to step 4

However, the real-world in libc in much more complicated and thus much more efficient.
Since 2.3 release GNU C library (glibc) uses a modified ptmalloc2, based on "Doug Lea's Malloc" (dlmalloc), which is a lock free implementation.

Quoting glibc/malloc/malloc.c:

  The main properties of the algorithms are:
  * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
    with ties normally decided via FIFO (i.e. least recently used).
  * For small (<= 64 bytes by default) requests, it is a caching
    allocator, that maintains pools of quickly recycled chunks.
  * In between, and for combinations of large and small requests, it does
    the best it can trying to meet both goals at once.
  * For very large requests (>= 128KB by default), it relies on system
    memory mapping facilities, if supported

The differences between memory allocated by sbrk() and mmap() are: 1). A released memory map does not create any "hole" that would need to be managed. 2). mmaped regions must be page-aligned. 3). invoking mmap and mfree is much slower than carving out an existing chunk of memory, because mmap will force kernel to zero out the memory it returns, which eats a lot of cache and memory bandwidth.

The basic memory structure in glibc malloc is:

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free.  */
  struct malloc_chunk* bk_nextsize;
};

There are two core elements in dlmalloc: Boundary tags and bins.

Basically, boundary tags are how memory chunks look like, and bins are how memory chunks are managed.

An allocated chunk looks like this (boundary tags):

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if allocated            | |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk                                     |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk                            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                         |P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Forward pointer to next chunk in list             |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Back pointer to previous chunk in list            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Unused space (may be 0 bytes long)                .
            .                                                               .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Bins
    chunk in a list is known to be preceeded and followed by either
    inuse chunks or the ends of memory.

Fastbins
    A single-linked LIFO array of lists holding recently freed small chunks.
    Chunks in fastbins keep their inuse bit set. malloc_consolidate
    releases all chunks in fastbins and consolidates them with
    other free chunks.

the "unsorted" bin
    chunks being placed on it in free (and malloc_consolidate),
    and taken off (to be either used or placed in bins) in malloc.

Binmap
    a bitvector recording whether bins are definitely empty so they can
    be skipped over during during traversal

First kernel patch

2009-07-16T09:12:00.001-07:00

My real first kernel patch. I am quite exciting about it. Finally I got a Signed-off-by in the kernel commit log :)

Luckily enough, the patch got merged just before 2.6.30-rc3 was released.

commit ac046f1d6121ccdda6db66bd88acd52418f489b2
Author: Peng Tao
Date: Mon Jul 13 09:30:17 2009 -0400

ext4: fix null handler of ioctls in no journal mode

The EXT4_IOC_GROUP_ADD and EXT4_IOC_GROUP_EXTEND ioctls should not
flush the journal in no_journal mode. Otherwise, running resize2fs on
a mounted no_journal partition triggers the following error messages:

BUG: unable to handle kernel NULL pointer dereference at 00000014
IP: [] _spin_lock+0x8/0x19
*pde = 00000000
Oops: 0002 [#1] SMP

Signed-off-by: Peng Tao
Signed-off-by: "Theodore Ts'o"

Valerie's Advice to FS Developpers

2009-07-15T08:24:00.000-07:00

From an interview from Linux journal.
Keep it in mind...

Keep talking to other file system developers face to face, keep experimenting with new file systems, keep talking to people in research and academia, keep paying attention to hardware trends. The way to avoid the “file systems are a solved problem” echo chamber is to stay in touch with both each other and the outside world.

Content Addressable Storage -- The Next Step

2009-07-13T01:34:00.000-07:00

Recently, I was writing an slightly modified version of implementation of Content Addressable Storage (CAS) for our on-line image servers. I found it a perfect choice to apply CAS to image servers, where images are uploaded once and never changed, and where disk access throughput is a main bottleneck to many large-scale on-line image service providers.

As explained on wikipedia, CAS is a mechanism for storing information that can be retrieved based on its content, not its storage location. It is typically used for high-speed storage and retrieval of fixed content.

CAS Characteristics:
1. Storage is identified by its content
2. Designed to make the searching for a given document content very quick
3. Works most efficiently on data that does not change often

Currently, most servers store images as common files and rely on filesystem's mechanism to optimize reading speed. However, filesystems are limited by POSIX standards and are optimized only for everyday usage. For large-scale image servers (or any application storing large amount of images), CAS will be a better choice (for the following reasons).

1. deduplication: both block-level CAS and file-level CAS achieve efficient storage utilization by storing same data only once.
2. Aggregation: log-structured extent-based on-disk object-stores, storing many images continuously in a single large file, resulting only one disk seek if index files are saved/managed in-memory (verses 2~3 disk seeks per read for common files).

My CAS implementation is written by the fact that most images are small files (~10MB) and there are huge amount of them on image servers. The implementation should speed up accessing of these image files. I am planing some benchmarks this week and hope to post them here soon.

After that, I will be writing a paper illustrating the opportunistic of applying CAS system to large-scale image servers. Then, I also want to explore the possibility of changing the interface (to, maybe dbus?) and make it runnable on common desktop, because current gnome/kde also read a lot of thumbnails. Maybe I can make it quicker somehow. Who knows :)

Easter egg in opensuse grub

2009-06-29T18:50:00.000-07:00

Yesterday I booted my laptop while shaking it. First I saw some error messages saying something like "not enough memory". Then amazing things happened. A beautiful grub boot screen came into my eye. It's a snowy background with several penguins running around. I'm impressed! After booting into my system, I decided to find out what actually happened.

opensuse grub uses a gfxmenu option in menu.list to set the colorful boot menus. In my case,

gfxmenu (hd0,2)/message

So I need to open (hd0,2)/message to see what's inside.

$cp /boot/message ~/test/grub/
$cpio -i <>

Good, let's first see the about file

$cat pabout.txt
Penguin theme originally made by Raphael Quinet
(http://www.gamers.org/~quinet/lilo/).
Modernized for openSUSE by Steffen Winterfeldt.

Like it or hate it? Edit gfxboot.cfg in /boot/message
to have it always or to get rid of it.

So gfxboot.cfg next. I found an option setting penguin theme there.

; penguin theme likelihood (in percent, -1 = auto)
penguin=0

Wow, the likelihood is set 0, which explains why I didn't see the theme before. I must be so lucky that my shaking hands made grub to read the bit wrongly and presented the penguin theme to me. What a lucky dog I am!
I really like the penguin grub theme. So I decided to have it always by setting penguin likelihood to 100. and then reinstall the picture. Of course don't forget to delete the original message before archiving the new one.

penguin=100
$rm message
$find ./ -print | cpio -ov > message
./
./message
./16x16.fnt
./back.jpg
./en.hlp
./en.tr
./gfxboot.cfg
./init
./lang
./languages
./pabout.txt
./panim_a.jpg
./panim.jpg
./pback.jpg
./phead.jpg
./timer_a.jpg
./translations.en
835 blocks
$mv message /boot/

OK, let me reboot to see the new grub theme.

For those who want to try opensuse grub, please download from the official repository (look for grub here). To install grub in command line, see here. Of course root privilege is needed.

tesseract-ocr: jpeg support added

2009-06-19T02:57:00.000-07:00

I just pushed some patches to the github host to add jpeg image support with libjpeg.

One drawback is that, because the image operation infrastructure in tesseract doesn't allow passing libjpeg private structures between open and read operations, I have to open the file stream twice in opening and reading jpeg images.

To test the patch, pull from git://github.com/bergwolf/tesseract-ocr-copy.git and build tesseract-ocr. Then run some tests, this time against jpeg images :)

github copy of tesseract-ocr

2009-06-19T02:51:00.000-07:00

We need to modify tesseract-ocr to support more image formats. So I set up a project host at github and pulled the source code from tesseract-ocr's googlecode host.

So, to get the new code base, just type the following commands:
1. git clone git://github.com/bergwolf/tesseract-ocr-copy.git
2. cd tesseract-ocr-copy
3. ./configure
4. make
5. make install

works perfect :)

Great news: we have passed 1st round evaluation

2009-06-19T02:37:00.000-07:00

Just got a notification email saying that our online namecard ocr project has passed the first round of Nokia Innovation Contest.

Nokia is very generous to plan to sponsor us with a N95. Cool!

libevent and so on

2009-05-12T02:00:00.000-07:00

Since we need a HTTP server to provide efficient service to all kinds of clients, I started to look into some lightweight open source solutions. The first item that jumps into my eyes is libevent, because I happen to read a blog of a facebook developer's, stating that facebook is using libevent as a HTTP server in their haystack photo storage service.

Libevent is a lightweight event driven library wildly used in many applications, such as memcached and tor. Libevent has simple but efficient HTTP support. Here is a sample code building a simple HTTP server with evhttp:

#include <sys/queue.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netdb.h>

#include <string.h>
#include <stdio.h>

#include <evhttp.h>

void ocr_handler(struct evhttp_request *req, void *arg)
{
 struct evbuffer *buf;
 struct evkeyval *header;

 TAILQ_FOREACH(header, req->input_headers, next) {
  fprintf(stdout, "key:%s\tvalue:%s\n", header->key, header->value);
 }
}

int main(int argc, char **argv)
{
 int err;
 struct evhttp *httpd;
 struct event_base *evbase;
 int port = 1234;

 evbase = event_init();

 fprintf(stderr, "event method: %s\n", event_base_get_method(evbase));

 httpd = evhttp_new(evbase);
 if ((err = evhttp_bind_socket(httpd, NULL, port)) < 0) {
  fprintf(stderr, "error binding http server to port %d\n", port);
  return -1;
 }

 /* set callback for "/" */
 evhttp_set_cb(httpd, "/", ocr_handler, NULL);

 /* Set a send callback for all other requests. */
 evhttp_set_gencb(httpd, NULL, NULL);

 event_base_dispatch(evbase);

 evhttp_free(httpd);
 event_base_free(evbase);
 return 0;
}

However, as I looked into the library in details and wrote some test programs, it turns out that life is not that easy. I tried to dynamically create threads to serve incoming HTTP requests, but the code didn't work as I thought. After searching for a while, I found the problem:

Steven Grimm:

What libevent doesn't support is sharing a libevent instance across threads. It works just fine to use libevent in a multithreaded process where only one thread is making libevent calls.

Therefore, to use libevent in a multi-threaded program, we should create each thread a event base when initialising the program and call ev_set_base() after ev_set() but before ev_add(). Then we will have a thread pool to serve HTTP requests. There will a main thread listening to all incoming HTTP requests. When a request comes, it passes the request to some thread from the thread pool and wakes it up to handle the request.

Although this will work, we somehow end up with a master/worker thread architecture, where the main thread handles all reads from netwrok. This will certainly be a bottleneck when there are thousands of clients(think the C10K problem). I don't know how the facebook guys deal with this problem(maybe they patched libevent?:), But IMO, using an evhttp dispacher in a multi-threaded process, we'll end up this way.

So, currently, I'm planning to look at other solutions like lighttpd before making any decision on the server architecture.

A first glance at tesseract-ocr

2009-04-28T08:49:00.000-07:00

So, I start to look into the name card OCR project. As suggested by Alex, I'd first look at the OCR engine developed by Google, tesseract-ocr.

From wikipedia:
Tesseract is a free optical character recognition engine. It was originally developed as proprietary software at Hewlett-Packard between 1985 until 1995. After ten years without any development taking place, Hewlett Packard and UNLV released it as open source in 2005. Tesseract is currently developed by Google and released under the Apache License, Version 2.0

It's a little strange that the featured tar balls listed on the project home page have compile errors. After modifying the source code, I successfully got the program binaries, but the language charsets aren't built. Then I change to the svn HEAD version, and it works.

To use tesseract, I simply type:
[bergwolf@bin]$./tesseract phototest.tif result
Tesseract Open Source OCR Engine
[bergwolf@bin]$cat result.txt
This is a lot of 12 point text to test the
ocr code and see if it works on all types
of file format.
The quick brown dog jumped over the
lazy fox. The quick brown dog jumped
over the lazy fox. The quick brown dog
jumped over the lazy fox. The quick
brown dog jumped over the lazy fox.

Tesseract OCR engine is very accurate, and is very suitable for our name card OCR service, because usually we only have white background and black letters in our images.

However, the drawback is that it doesn't support many image formats. Most mobile device save camera photos in jpeg format. Currently, only tiff and bmp formats are recognizable by tesseract. If we want to use it as our OCR engine, two options are available: either patch tesseract with other image formats support, or use other tools like imagemagick to convert other image formats to tiff or bmp format, both of which shouldn't be very hard.

Being one of opensource apprentices

2009-04-18T08:07:00.000-07:00

A few days ago, I applied to be one of Alex Lau's 12 open source apprentices. After several conversations via email with Alex, I finally got a chance to see him face to face.

It was a wonderful and pleasant talk. Alex gave me a lot of advices, on my tech path and on my future plans. We talked about many open source projects, like name card OCR, SyncML, Ifolder, Logfs(and FTL), as well as p2p file systems. At this point, I'm planning to first look at the on-line name card OCR project. It is most related to the Maemo project in my laboratory, and maybe, I can find someone in the lab to implement it together with me.

My problem is that I applied for this year's GSoC program. But the GSoC slots allocation is not decided yet. So I don't know how much time I can devote to this program. Nevertheless, let's see the GSoC results first, which is due soon.

Kernel basis(2): radix trees

2009-01-05T03:57:00.000-08:00

Abstract: this article talks about the data structure radix trees and its usage in Linux kernel.

1. What is a radix tree?
As described by wikipedia, A radix tree, Patricia trie/tree, or crit bit tree is a specialized set data structure based on the trie that is used to store a set of strings.

2. Linux kernel radix tree internals

struct radix_tree_root {
unsigned int  height;
gfp_t   gfp_mask;
struct radix_tree_node *rnode;
};

struct radix_tree_node {
unsigned int height;  /* Height from the bottom */
unsigned int count;
struct rcu_head rcu_head;
void *slots[RADIX_TREE_MAP_SIZE];
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
#ifdef __KERNEL__
#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
#else
#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
#endif

In Linux kernel, each radix tree node has 16/64 slots and can be indexed by a portion of the integer key. The leaf node points to the content. Empty slots contain a NULL pointer. For example, each node of the above three levels radix tree is indexed by 6 bits of the key. Nodes that have no children are not presented. Thus radix tree can be used to store sparse files.

3. Usage
In vanilla kernel, the PowPC architecture uses a radix tree to map real and virtual IRQ numbers. The NFS code uses a radix tree to index inode structures to keep track of outstanding requests. The address_space structure used to keep track of backing store contains a radix tree which tracks in-core pages tied to that mapping. Among other things, this tree allows the memory management code to quickly find pages which are dirty or under writeback.

4. How to use radix trees?
There are two ways to initialize a radix tree:

#include linux/radix-tree.h
then
 RADIX_TREE(name, gfp_mask);  /* Declare and initialize */
or
 struct radix_tree_root my_tree;
 INIT_RADIX_TREE(my_tree, gfp_mask);

The first approach is simply a wrapper of combination of the latter one.
Then all functions defined in linux/radix-tree.h can be used to manipulate the tree.

5. Notes
(1)Synchronization
The radix-tree API requires users to provide all synchronizations(with some specific exceptions).
For API usage, in general,
- any function _modifying_ the tree or tags (inserting or deleting
items, setting or clearing tags) must exclude other modifications, and
exclude any functions reading the tree.
- any function _reading_ the tree or tags (looking up items or tags,
gang lookups) must exclude modifications to the tree, but may occur
concurrently with other readers.

The notable exceptions to this rule are the following functions:
radix_tree_lookup
radix_tree_lookup_slot
radix_tree_tag_get
radix_tree_gang_lookup
radix_tree_gang_lookup_slot
radix_tree_gang_lookup_tag
radix_tree_gang_lookup_tag_slot
radix_tree_tagged
(1)Destroying a radix tree.
There is no function for destroying a radix tree. It is, evidently, assumed that radix trees will last forever. In practice, deleting all items from a radix tree will free all memory associated with it other than the root node, which can then be disposed of normally.

6. Reference:
http://lwn.net/Articles/175432/
http://en.wikipedia.org/wiki/Radix_tree

Kernel basis(1): the container_of macro

2009-01-01T19:45:00.000-08:00

Short version:
The following article explains how container_of macro works and how to use
it(based on http://www.kroah.com/log/linux/container_of.html).

Long version:
The container_of macro is defined in linux/kernel.h
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

Some fundamentals:
1. typeof:
This is one of GNU C extensions. In ANSI C and ISO C, this should be
__typeof__. The macro takes in two types of arguments: an expression or
a type.

Expression: typeof(x[0](1))
where x is an array of pointers to functions. The macro returns the value
of the function.

Type: typeof(int *)
This is the type of pointers to int.

2. offsetof(TYPE, MEMBER)
This is an ANSI C library feature defined in stddef.h. It evaluates to
offset(in bytes) of a given member within a struct or union type.
Typical implementations:
#define offsetof(TYPE, MEMBER) ((site_t) &((TYPE*)0)->MEMBER)

#define offsetof(TYPE, MEMBER) \
((size_t) ((char *)&((TYPE*)(0))->MEMBER - (char *)0))

gcc has buitin offsetof. To use it, do
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

Now, we come to the container_of macro at last. Really easy to understand.
The first line defines a pointer(__mptr) that points to *ptr. So we have
tow pointers(__mptr and ptr) both pointing to the same memory location.

The second line finds the real location in memory of the containing
structure that contains what ptr points to. The offsetof macro calculates
the memory offset of member starting from type. Then it dismiss the offset
from memory location __mptr and gives us the memory location of the
containing structure, type.

How to use it?
This is useful for calling back functions between different software layers.

 container_of_sample.c/* test code to illustrate use of Linux kernel container_of macro
 *
 * Copyright (c) 2008 Cliff Brake, BEC Systems LLC
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* This program illustrates how the container_of macro works.
 * The container of macro is very useful in multi layered
 * software systems where you have progressivly more detailed
 * software layers.  Below is an example of a bus layer,
 * and then a device layer where a number of different
 * devices might register with the bus.
 * The device registers itself with the bus subsystem, and
 * then the bus subsystem makes a callback into the device.
 * Normally if there are multiple devices registered, the 
 * bus subsystem must store and pass a device structure
 * when making callbacks.  With the container_of macro, this is
 * no longer necessary, and the bus subsystem only has to
 * know about one generic device structure, and does not need visibility
 * into lots of different device structures, or do tricks
 * by casting void pointers, etc.  With the container_of macro
 * we can backcast from the generic data structure, to the containing
 * datastructure.  This forces good separation of code in that
 * that bus layer cannot modifiy data structures that are specific
 * to the device layer.
 *
 */


/**
 * (from Linux kernel source)
 * container_of - cast a member of a structure out to the containing structure
 * @ptr: the pointer to the member.
 * @type: the type of the container struct this is embedded in.
 * @member: the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({   \
 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
 (type *)( (char *)__mptr - offsetof(type,member) );})

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)


/*==========================================================
 * BUS layer code
 *==========================================================*/

/* generic bus device structure */
struct bus_device 
{
 int general_device_param_a;
 int general_device_param_b;
 void (*device_callback)(struct bus_device * bd);
};

/* the following is a global list of
 * devices that have registered with the 
 * bus subsystem.  Normally this would
 * be something like a dynamic linked list.
 */
struct bus_device * bd_list[5];

/* function to register a device with the bus */
void register_with_bus(struct bus_device * bd)
{
 /* since this example only deals with one
  * device, will put it in slot 0
  */

 bd_list[0] = bd;
}

void start_bus()
{
 int i;
 struct bus_device * bd;

 /* make callbacks to all devices on bus */
 for (i=0;i<sizeof(bd_list)/sizeof(bd_list[0]);i++) {
  bd = bd_list[i];
  if (!bd) continue;
  /* call device callback with generic
   * bus device structure
   */
  bd->device_callback(bd);
 }
}

/*==========================================================
 * device X specific code
 * this would normally be in a different module
 *==========================================================*/

/* structure that holds device X specific stuff, as well as
 * generic bus_device structure
 */
struct device_x
{
 int device_x_specific_param_a;
 int device_x_specific_param_b;
 struct bus_device bd;
};

void device_x_callback(struct bus_device * bd)
{
 /* if we know the structure type that contains the bus_device structure,
  * we can extract a pointer to the containing structure using the container_of
  * macro
  */

 /*                                   ptr       type       member  */
 struct device_x * devx = container_of(bd, struct device_x, bd);

 /* the above statement expands to
  * struct device_x * devx = (
  * { 
  *   const typeof( ((struct device_x *)0)->bd ) *__mptr = (bd); 
  *   (struct device_x *)( (char *)__mptr - ((size_t) &((struct device_x *)0)->bd) );
  * }
  * );
  */  

 printf("device_x_callback called!, device_x_specific_param_a = %i\n", 
   devx->device_x_specific_param_a);
}

void device_x_init()
{
 /* dynamically allocate structures */
 struct device_x * devx = malloc(sizeof(*devx));
 memset(devx, 0, sizeof(*devx));

 /* set a parameter in the device_x structure so 
  * we can test for this in the callback
  */
 devx->device_x_specific_param_a = 1001;

 /* set up callback function */
 devx->bd.device_callback = device_x_callback;

 /* we register the generic bus device structure
  * as the bus layer does not need to know
  * about the device_x stucture.  Note, the 
  * devx structure is not stored anywhere, yet
  * its location is being preserved without
  * specifically passing it to the bus 
  * layer.
  */
 register_with_bus(&devx->bd);
}


int main()
{

 /* test the above system */

 /* first, initialize device_x */
 device_x_init();

 /* now, start the bus.  This should make
  * a callback into the device_x
  */
 start_bus();
}

/* when run, this program returns:
 * device_x_callback called!, device_x_specific_param_a = 1001
 */

Enable ext4 to run without a journal

2008-11-29T08:50:00.000-08:00

This is really useful on flash devices.
According to the kernel documents, there are three kind of journal mode in ext4: writeback, ordered, journal.
(1) writeback mode: ext4 doesn't journal data at all. Only metadata journaling is provided. Data ordering is not preserved. Data may be written into the disk after its metadata has been committed to the journal. A crash-recovery may cause data corruption in files which written shortly before the crash.
(2) ordered mode: ext4 only journals metadata, but logically groups metadata information related to data changes with the data blocks into a single unit called a transaction. When it's time to write the new metadata out to disk, the associated data blocks are written first.
(3) journal mode: ext4 provides full metadata and data journaling. All new data is written to the journal first, and then to its final location. In the event of a crash, the journal can be replayed, bringing both data and metadata into a consistent state.

Basically, the idea is to make use of data writeback mode. In writeback mode, data is written directly to disk, and when it comes to metadata, we need to write it out to disk once a dirty_metadata_buffer_head request is received. Superblock buffer head and inode buffer header are handled separately.

Use git behind a proxy

2008-11-27T06:50:00.000-08:00

Since someone is asking me to provide an English version about git proxy configuration in my former blog. Here it is.
Basically, I know two ways to use git behind a proxy.
(1). Set the http_proxy environment if git repository supports http connections.
(2). find a proxy command to bypass the connection:
1. gcc -o connect connect.c
mv connect ~/bin
2. set up a wrapper
echo "/home/gigi/bin/connect -H proxy.bupt.edu.cn:8080 $@" >> ~/bin/proxy
chmod +x ~/bin/proxy
Here I'm using a http proxy offered by my school, which uses port 8080
The connect command also support socket proxy. Use -S host:port to indicate that.
3. echo "export CONNECT_USER=bergwolf" >> .bashrc
echo "export GIT_PROXY_COMMAND=proxy" >> .bashrc
The connect command reads proxy username and password from CONNECT_USER and CONNECT_PASSWORD evironment. The default username is current login user if no CONNECT_USER is set. Password will be requested interactively if CONNECT_PASSWORD is empty.
GIT_PROXY_COMMAND indicates that git should use the command "proxy"(the wrapper we setup at step 2) as its proxy_command. This can also be set in .git/config.

Now, everything we need is done. Have a try:
[gigi-Ubuntu:bin]$git clone git://git.kernel.org/pub/scm/fs/ext2/e2fsprogs.git
Initialized empty Git repository in /home/gigi/bin/e2fsprogs/.git/
Enter proxy authentication password for bergwolf@proxy.bupt.edu.cn:
remote: Counting objects: 24006, done.
remote: Compressing objects: 100% (4701/4701), done.
ceiving objects: 1% (241/24006), 43.99 KiB | 56 KiB/s

connect.c:


/***********************************************************************
 * connect.c -- Make socket connection using SOCKS4/5 and HTTP tunnel.
 *
 * Copyright (c) 2000-2006 Shun-ichi Goto
 * Copyright (c) 2002, J. Grant (English Corrections)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * ---------------------------------------------------------
 * PROJECT:  My Test Program
 * AUTHOR:   Shun-ichi GOTO <gotoh@taiyo.co.jp>
 * CREATE:   Wed Jun 21, 2000
 * REVISION: $Revision: 100 $
 * ---------------------------------------------------------
 *
 * Getting Source
 * ==============
 *
 *   Recent version of 'connect.c' is available from
 *     http://www.taiyo.co.jp/~gotoh/ssh/connect.c
 *
 *   Related tool, ssh-askpass.exe (alternative ssh-askpass on UNIX)
 *   is available:
 *     http://www.taiyo.co.jp/~gotoh/ssh/ssh-askpass.exe.gz
 *
 *   See more detail:
 *     http://www.taiyo.co.jp/~gotoh/ssh/connect.html
 *
 * How To Compile
 * ==============
 *
 *  On UNIX environment:
 *      $ gcc connect.c -o connect
 *
 *  On SOLARIS:
 *      $ gcc -o connect -lresolv -lsocket -lnsl connect.c
 *
 *  on Win32 environment:
 *      $ cl connect.c wsock32.lib advapi32.lib
 *    or
 *      $ bcc32 connect.c wsock32.lib advapi32.lib
 *    or
 *      $ gcc connect.c -o connect
 *
 *  on Mac OS X environment:
 *      $ gcc connect.c -o connect -lresolv
 *    or
 *      $ gcc connect.c -o connect -DBIND_8_COMPAT=1
 *
 * How To Use
 * ==========
 *
 *   You can specify proxy method in an environment variable or in a
 *   command line option.
 *
 *   usage:  connect [-dnhst45] [-R resolve] [-p local-port] [-w sec]
 *                   [-H [user@]proxy-server[:port]]
 *                   [-S [user@]socks-server[:port]]
 *                   [-T proxy-server[:port]]
 *                   [-c telnet proxy command]
 *                   host port
 *
 *   "host" and "port" is for the target hostname and port-number to
 *   connect to.
 *
 *   The -H option specifys a hostname and port number of the http proxy
 *   server to relay. If port is omitted, 80 is used. You can specify this
 *   value in the environment variable HTTP_PROXY and pass the -h option
 *   to use it.
 *
 *   The -S option specifys the hostname and port number of the SOCKS
 *   server to relay.  Like -H, port number can be omitted and the default
 *   is 1080. You can also specify this value pair in the environment
 *   variable SOCKS5_SERVER and give the -s option to use it.
 *
 *   The '-4' and the '-5' options are for specifying SOCKS relaying and
 *   indicates protocol version to use. It is valid only when used with
 *   '-s' or '-S'. Default is '-5' (protocol version 5)
 *
 *   The '-R' option is for specifying method to resolve the
 *   hostname. Three keywords ("local", "remote", "both") or dot-notation
 *   IP address are acceptable.  The keyword "both" means, "Try local
 *   first, then remote". If a dot-notation IP address is specified, use
 *   this host as nameserver. The default is "remote" for SOCKS5 or
 *   "local" for others. On SOCKS4 protocol, remote resolving method
 *   ("remote" and "both") requires protocol 4a supported server.
 *
 *   The '-p' option will forward a local TCP port instead of using the
 *   standard input and output.
 *
 *   The '-P' option is same to '-p' except keep remote session. The
 *   program repeats waiting the port with holding remote session without
 *   disconnecting. To disconnect the remote session, send EOF to stdin or
 *   kill the program.
 *
 *   The '-w' option specifys timeout seconds for making connection with
 *   TARGET host.
 *
 *   The '-d' option is used for debug. If you fail to connect, use this
 *   and check request to and response from server.
 *
 *   You can omit the "port" argument when program name is special format
 *   containing port number itself. For example,
 *     $ ln -s connect connect-25
 *   means this connect-25 command is spcifying port number 25 already
 *   so you need not 2nd argument (and ignored if specified).
 *
 *   To use proxy, this example is for SOCKS5 connection to connect to
 *   'host' at port 25 via SOCKS5 server on 'firewall' host.
 *     $ connect -S firewall  host 25
 *   or
 *     $ SOCKS5_SERVER=firewall; export SOCKS5_SERVER
 *     $ connect -s host 25
 *
 *   For a HTTP-PROXY connection:
 *     $ connect -H proxy-server:8080  host 25
 *   or
 *     $ HTTP_PROXY=proxy-server:8080; export HTTP_PROXY
 *     $ connect -h host 25
 *   To forward a local port, for example to use ssh:
 *     $ connect -p 5550 -H proxy-server:8080  host 22
 *    ($ ssh -l user -p 5550 localhost )
 *
 * TIPS
 * ====
 *
 *   Connect.c doesn't have any configuration to specify the SOCKS server.
 *   If you are a mobile user, this limitation might bother you.  However,
 *   You can compile connect.c and link with other standard SOCKS library
 *   like the NEC SOCKS5 library or Dante. This means connect.c is
 *   socksified and uses a configration file like to other SOCKSified
 *   network commands and you can switch configuration file any time
 *   (ex. when ppp startup) that brings you switching of SOCKS server for
 *   connect.c in same way with other commands. For this case, you can
 *   write ~/.ssh/config like this:
 *
 *     ProxyCommand connect -n %h %p
 *
 * SOCKS5 authentication
 * =====================
 *
 *   Only USER/PASS authentication is supported.
 *
 * Proxy authentication
 * ====================
 *
 *   Only BASIC scheme is supported.
 *
 * Authentication informations
 * ===========================
 *
 *   User name for authentication is specifed by an environment variable
 *   or system login name.  And password is specified from environment
 *   variable or external program (specified in $SSH_ASKPASS) or tty.
 *
 *   Following environment variable is used for specifying user name.
 *     SOCKS: $SOCKS5_USER, $LOGNAME, $USER
 *     HTTP Proxy: $HTTP_PROXY_USER, $LOGNAME, $USER
 *
 * ssh-askpass support
 * ===================
  *
 *   You can use ssh-askpass (came from OpenSSH or else) to specify
 *   password on graphical environment (X-Window or MS Windows). To use
 *   this, set program name to environment variable SSH_ASKPASS. On UNIX,
 *   X-Window must be required, so $DISPLAY environment variable is also
 *   needed.  On Win32 environment, $DISPLAY is not mentioned.
 *
 * Related Informations
 * ====================
 *
 *   SOCKS5 -- RFC 1928, RFC 1929, RFC 1961
 *             NEC SOCKS Reference Implementation is available from:
 *               http://www.socks.nec.com
 *             DeleGate version 5 or earlier can be SOCKS4 server,
 *             and version 6 can be SOCKS5 and SOCKS4 server.
 *             and version 7.7.0 or later can be SOCKS5 and SOCKS4a server.
 *               http://www.delegate.org/delegate/
 *
 *   HTTP-Proxy --
 *             Many http proxy servers supports this, but https should
 *             be allowed as configuration on your host.
 *             For example on DeleGate, you should add "https" to the
 *             "REMITTABLE" parameter to allow HTTP-Proxy like this:
 *               delegated -Pxxxx ...... REMITTABLE="+,https" ...
 *
 *  Hypertext Transfer Protocol -- HTTP/1.1  -- RFC 2616
 *  HTTP Authentication: Basic and Digest Access Authentication -- RFC 2617
 *             For proxy authentication, refer these documents.
 *
 ***********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <memory.h>
#include <errno.h>
#include <assert.h>
#include <sys/types.h>
#include <stdarg.h>
#include <fcntl.h>
#include <signal.h>

#ifdef __CYGWIN32__
#undef _WIN32
#endif

#ifdef _WIN32
#include <windows.h>
#include <winsock.h>
#include <sys/stat.h>
#include <io.h>
#include <conio.h>
#else /* !_WIN32 */
#include <unistd.h>
#include <pwd.h>
#include <termios.h>
#include <sys/time.h>
#ifndef __hpux
#include <sys/select.h>
#endif /* __hpux */
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <netdb.h>
#if !defined(_WIN32) && !defined(__CYGWIN32__)
#define WITH_RESOLVER 1
#include <arpa/nameser.h>
#include <resolv.h>
#else  /* not ( not _WIN32 && not __CYGWIN32__) */
#undef WITH_RESOLVER
#endif /* not ( not _WIN32 && not __CYGWIN32__) */
#endif /* !_WIN32 */

#ifdef _WIN32
#define ECONNRESET WSAECONNRESET
#endif /* _WI32 */



#ifndef LINT
static char *vcid = "$Id: connect.c 100 2007-07-03 10:48:26Z gotoh $";
#endif

/* Microsoft Visual C/C++ has _snprintf() and _vsnprintf() */
#ifdef _MSC_VER
#define snprintf _snprintf
#define vsnprintf _vsnprintf
#endif

/* consider Borland C */
#ifdef __BORLANDC__
#define _kbhit kbhit
#define _setmode setmode
#endif

/* help message.
   Win32 environment does not support -R option (vc and cygwin)
   Win32 native compilers does not support -w option, yet (vc)
*/
static char *usage = "usage: %s [-dnhst45] [-p local-port]"
#ifdef _WIN32
#ifdef __CYGWIN32__
"[-w timeout] \n"                               /* cygwin cannot -R */
#else  /* not __CYGWIN32__ */
" \n"                                           /* VC cannot -w nor -R  */
#endif /* not __CYGWIN32__ */
#else  /* not _WIN32 */
/* help message for UNIX */
"[-R resolve] [-w timeout] \n"
#endif /* not _WIN32 */
"          [-H proxy-server[:port]] [-S [user@]socks-server[:port]] \n"
"          [-T proxy-server[:port]]\n"
"          [-c telnet-proxy-command]\n"
"          host port\n";

/* name of this program */
char *progname = NULL;
char *progdesc = "connect --- simple relaying command via proxy.";
char *rcs_revstr = "$Revision: 100 $";
char *revstr = NULL;
int major_version = 1;
int minor_version = 0;

/* set of character for strspn() */
const char *digits    = "0123456789";
const char *dotdigits = "0123456789.";

/* options */
int f_debug = 0;

/* report flag to hide secure information */
int f_report = 1;

int connect_timeout = 0;

/* local input type */
#define LOCAL_STDIO     0
#define LOCAL_SOCKET    1
char *local_type_names[] = { "stdio", "socket" };
int   local_type = LOCAL_STDIO;
u_short local_port = 0;                         /* option 'p' */
int f_hold_session = 0;                         /* option 'P' */

char *telnet_command = "telnet %h %p";

/* utiity types, pair holder of number and string */
typedef struct {
    int num;
    const char *str;
} LOOKUP_ITEM;

/* relay method, server and port */
#define METHOD_UNDECIDED 0
#define METHOD_DIRECT    1
#define METHOD_SOCKS     2
#define METHOD_HTTP      3
#define METHOD_TELNET    4
char *method_names[] = { "UNDECIDED", "DIRECT", "SOCKS", "HTTP", "TELNET" };

int   relay_method = METHOD_UNDECIDED;          /* relaying method */
char *relay_host = NULL;                        /* hostname of relay server */
u_short relay_port = 0;                         /* port of relay server */
char *relay_user = NULL;                        /* user name for auth */

/* destination target host and port */
char *dest_host = NULL;
struct sockaddr_in dest_addr;
u_short dest_port = 0;

/* informations for SOCKS */
#define SOCKS5_REP_SUCCEEDED    0x00    /* succeeded */
#define SOCKS5_REP_FAIL         0x01    /* general SOCKS serer failure */
#define SOCKS5_REP_NALLOWED     0x02    /* connection not allowed by ruleset */
#define SOCKS5_REP_NUNREACH     0x03    /* Network unreachable */
#define SOCKS5_REP_HUNREACH     0x04    /* Host unreachable */
#define SOCKS5_REP_REFUSED      0x05    /* connection refused */
#define SOCKS5_REP_EXPIRED      0x06    /* TTL expired */
#define SOCKS5_REP_CNOTSUP      0x07    /* Command not supported */
#define SOCKS5_REP_ANOTSUP      0x08    /* Address not supported */
#define SOCKS5_REP_INVADDR      0x09    /* Inalid address */

LOOKUP_ITEM socks5_rep_names[] = {
    { SOCKS5_REP_SUCCEEDED, "succeeded"},
    { SOCKS5_REP_FAIL,      "general SOCKS server failure"},
    { SOCKS5_REP_NALLOWED,  "connection not allowed by ruleset"},
    { SOCKS5_REP_NUNREACH,  "Network unreachable"},
    { SOCKS5_REP_HUNREACH,  "Host unreachable"},
    { SOCKS5_REP_REFUSED,   "connection refused"},
    { SOCKS5_REP_EXPIRED,   "TTL expired"},
    { SOCKS5_REP_CNOTSUP,   "Command not supported"},
    { SOCKS5_REP_ANOTSUP,   "Address not supported"},
    { SOCKS5_REP_INVADDR,   "Invalid address"},
    { -1, NULL }
};

/* SOCKS5 authentication methods */
#define SOCKS5_AUTH_REJECT      0xFF    /* No acceptable auth method */
#define SOCKS5_AUTH_NOAUTH      0x00    /* without authentication */
#define SOCKS5_AUTH_GSSAPI      0x01    /* GSSAPI */
#define SOCKS5_AUTH_USERPASS    0x02    /* User/Password */
#define SOCKS5_AUTH_CHAP        0x03    /* Challenge-Handshake Auth Proto. */
#define SOCKS5_AUTH_EAP         0x05    /* Extensible Authentication Proto. */
#define SOCKS5_AUTH_MAF         0x08    /* Multi-Authentication Framework */

#define SOCKS4_REP_SUCCEEDED    90      /* rquest granted (succeeded) */
#define SOCKS4_REP_REJECTED     91      /* request rejected or failed */
#define SOCKS4_REP_IDENT_FAIL   92      /* cannot connect identd */
#define SOCKS4_REP_USERID       93      /* user id not matched */

LOOKUP_ITEM socks4_rep_names[] = {
    { SOCKS4_REP_SUCCEEDED,  "request granted (succeeded)"},
    { SOCKS4_REP_REJECTED,   "request rejected or failed"},
    { SOCKS4_REP_IDENT_FAIL, "cannot connect identd"},
    { SOCKS4_REP_USERID,     "user id not matched"},
    { -1, NULL }
};

#define RESOLVE_UNKNOWN 0
#define RESOLVE_LOCAL   1
#define RESOLVE_REMOTE  2
#define RESOLVE_BOTH    3
char *resolve_names[] = { "UNKNOWN", "LOCAL", "REMOTE", "BOTH" };

int socks_version = 5;                          /* SOCKS protocol version */
int socks_resolve = RESOLVE_UNKNOWN;
struct sockaddr_in socks_ns;
char *socks5_auth = NULL;

/* Environment variable names */
#define ENV_SOCKS_SERVER  "SOCKS_SERVER"        /* SOCKS server */
#define ENV_SOCKS5_SERVER "SOCKS5_SERVER"
#define ENV_SOCKS4_SERVER "SOCKS4_SERVER"

#define ENV_SOCKS_RESOLVE  "SOCKS_RESOLVE"      /* resolve method */
#define ENV_SOCKS5_RESOLVE "SOCKS5_RESOLVE"
#define ENV_SOCKS4_RESOLVE "SOCKS4_RESOLVE"

#define ENV_SOCKS5_USER     "SOCKS5_USER"       /* auth user for SOCKS5 */
#define ENV_SOCKS4_USER     "SOCKS4_USER"       /* auth user for SOCKS4 */
#define ENV_SOCKS_USER      "SOCKS_USER"        /* auth user for SOCKS */
#define ENV_SOCKS5_PASSWD   "SOCKS5_PASSWD"     /* auth password for SOCKS5 */
#define ENV_SOCKS5_PASSWORD "SOCKS5_PASSWORD"   /* old style */

#define ENV_HTTP_PROXY          "HTTP_PROXY"    /* common env var */
#define ENV_HTTP_PROXY_USER     "HTTP_PROXY_USER" /* auth user */
#define ENV_HTTP_PROXY_PASSWORD "HTTP_PROXY_PASSWORD" /* auth password */

#define ENV_TELNET_PROXY          "TELNET_PROXY"    /* common env var */

#define ENV_CONNECT_USER     "CONNECT_USER"     /* default auth user name */
#define ENV_CONNECT_PASSWORD "CONNECT_PASSWORD" /* default auth password */

#define ENV_SOCKS_DIRECT   "SOCKS_DIRECT"       /* addr-list for non-proxy */
#define ENV_SOCKS5_DIRECT  "SOCKS5_DIRECT"
#define ENV_SOCKS4_DIRECT  "SOCKS4_DIRECT"
#define ENV_HTTP_DIRECT    "HTTP_DIRECT"
#define ENV_CONNECT_DIRECT "CONNECT_DIRECT"

#define ENV_SOCKS5_AUTH "SOCKS5_AUTH"
#define ENV_SSH_ASKPASS "SSH_ASKPASS"           /* askpass program */

/* Prefix string of HTTP_PROXY */
#define HTTP_PROXY_PREFIX "http://"
#define PROXY_AUTH_NONE 0
#define PROXY_AUTH_BASIC 1
#define PROXY_AUTH_DIGEST 2
int proxy_auth_type = PROXY_AUTH_NONE;

/* reason of end repeating */
#define REASON_UNK              -2
#define REASON_ERROR            -1
#define REASON_CLOSED_BY_LOCAL  0
#define REASON_CLOSED_BY_REMOTE 1

/* return value of relay start function. */
#define START_ERROR -1
#define START_OK     0
#define START_RETRY  1

/* socket related definitions */
#ifndef _WIN32
#define SOCKET int
#endif
#ifndef SOCKET_ERROR
#define SOCKET_ERROR -1
#endif

#ifdef _WIN32
#define socket_errno() WSAGetLastError()
#else /* !_WIN32 */
#define closesocket close
#define socket_errno() (errno)
#endif /* !_WIN32 */

#ifdef _WIN32
#define popen _popen
#endif /* WIN32 */

/* packet operation macro */
#define PUT_BYTE(ptr,data) (*(unsigned char*)ptr = data)

/* debug message output */
void
debug( const char *fmt, ... )
{
    va_list args;
    if ( f_debug ) {
        va_start( args, fmt );
        fprintf(stderr, "DEBUG: ");
        vfprintf( stderr, fmt, args );
        va_end( args );
    }
}

void
debug_( const char *fmt, ... )                  /* without prefix */
{
    va_list args;
    if ( f_debug ) {
        va_start( args, fmt );
        vfprintf( stderr, fmt, args );
        va_end( args );
    }
}

/* error message output */
void
error( const char *fmt, ... )
{
    va_list args;
    va_start( args, fmt );
    fprintf(stderr, "ERROR: ");
    vfprintf( stderr, fmt, args );
    va_end( args );
}

void
fatal( const char *fmt, ... )
{
    va_list args;
    va_start( args, fmt );
    fprintf(stderr, "FATAL: ");
    vfprintf( stderr, fmt, args );
    va_end( args );
    exit (EXIT_FAILURE);
}


void *
xmalloc (size_t size)
{
    void *ret = malloc(size);
    if (ret == NULL)
        fatal("Cannot allocate memory: %d bytes.\n", size);
    return ret;
}

char *
downcase( char *str )
{
    char *buf = str;
    while ( *buf ) {
        if ( isupper(*buf) )
            *buf += 'a'-'A';
        buf++;
    }
    return str;                                 /* return converted arg */
}

char *
expand_host_and_port (const char *fmt, const char *host, int port)
{
    const char *src;
    char *buf, *dst, *ptr;
    size_t len = strlen(fmt) + strlen(host) + 20;
    buf = xmalloc (len);
    dst = buf;
    src = fmt;
    
    while (*src) {
        if (*src == '%') {
            switch (src[1]) {
            case 'h':
                strcpy (dst, host);
                src += 2;
                break;
            case 'p':
                snprintf (dst, len, "%d", port);
                src += 2;
                break;
            default:
                src ++;
                break;
            }
            dst = buf + strlen (buf);
        } else if (*src == '\\') {
            switch (src[1]) {
            case 'r':                                /* CR */
                *dst++ = '\r';
                src += 2;
                break;
            case 'n':                                /* LF */
                *dst++ = '\n';
                src += 2;
                break;
            case 't':                                /* TAB */
                *dst++ = '\t';
                src += 2;
                break;
            default:
                src ++;
                break;
            }
        } else {
            /* usual */
            *dst++ = *src++;
        }
        *dst = '\0';
    }
    assert (strlen(buf) < len);
    return buf;
}


int
lookup_resolve( const char *str )
{
    char *buf = strdup( str );
    int ret;

    downcase( buf );
    if ( strcmp( buf, "both" ) == 0 )
        ret = RESOLVE_BOTH;
    else if ( strcmp( buf, "remote" ) == 0 )
        ret = RESOLVE_REMOTE;
    else if ( strcmp( buf, "local" ) == 0 )
        ret = RESOLVE_LOCAL;
    else if ( strspn(buf, dotdigits) == strlen(buf) ) {
#ifndef WITH_RESOLVER
        fatal("Sorry, you can't specify to resolve the hostname with the -R option on Win32 environment.");
#endif /* not WITH_RESOLVER */
        ret = RESOLVE_LOCAL;                    /* this case is also 'local' */
        socks_ns.sin_addr.s_addr = inet_addr(buf);
        socks_ns.sin_family = AF_INET;
    }
    else
        ret = RESOLVE_UNKNOWN;
    free(buf);
    return ret;
}

char *
getusername(void)
{
#ifdef _WIN32
    static char buf[1024];
    DWORD size = sizeof(buf);
    buf[0] = '\0';
    GetUserName( buf, &size);
    return buf;
#else  /* not _WIN32 */
    struct passwd *pw = getpwuid(getuid());
    if ( pw == NULL )
        fatal("getpwuid() failed for uid: %d\n", getuid());
    return pw->pw_name;
#endif /* not _WIN32 */
}

/* expect
   check STR is begin with substr with case-ignored comparison.
   Return 1 if matched, otherwise 0.
*/
int
expect( char *str, char *substr)
{
    int len = strlen(substr);
    while ( 0 < len-- ) {
        if ( toupper(*str) != toupper(*substr) )
            return 0;                           /* not matched */
        str++, substr++;
    }
    return 1;                   /* good, matched */
}


/** PARAMETER operation **/
#define PARAMETER_FILE "/etc/connectrc"
#define PARAMETER_DOTFILE ".connectrc"
typedef struct {
    char* name;
    char* value;
} PARAMETER_ITEM;
PARAMETER_ITEM parameter_table[] = {
    { ENV_SOCKS_SERVER, NULL },
    { ENV_SOCKS5_SERVER, NULL },
    { ENV_SOCKS4_SERVER, NULL },
    { ENV_SOCKS_RESOLVE, NULL },
    { ENV_SOCKS5_RESOLVE, NULL },
    { ENV_SOCKS4_RESOLVE, NULL },
    { ENV_SOCKS5_USER, NULL },
    { ENV_SOCKS5_PASSWD, NULL },
    { ENV_SOCKS5_PASSWORD, NULL },
    { ENV_HTTP_PROXY, NULL },
    { ENV_HTTP_PROXY_USER, NULL },
    { ENV_HTTP_PROXY_PASSWORD, NULL },
    { ENV_CONNECT_USER, NULL },
    { ENV_CONNECT_PASSWORD, NULL },
    { ENV_SSH_ASKPASS, NULL },
    { ENV_SOCKS5_DIRECT, NULL },
    { ENV_SOCKS4_DIRECT, NULL },
    { ENV_SOCKS_DIRECT, NULL },
    { ENV_HTTP_DIRECT, NULL },
    { ENV_CONNECT_DIRECT, NULL },
    { ENV_SOCKS5_AUTH, NULL },
    { NULL, NULL }
};

PARAMETER_ITEM*
find_parameter_item(const char* name)
{
    int i;
    for( i = 0; parameter_table[i].name != NULL; i++ ){
        if ( strcmp(name, parameter_table[i].name) == 0 )
            return &parameter_table[i];
    }
    return NULL;
}

void
read_parameter_file_1(const char* name)
{
    FILE* f;
    int line;
    char lbuf[1025];
    f = fopen(name, "r");
    if( f ){
        debug("Reading parameter file(%s)\n", name);
        for ( line = 1; fgets(lbuf, 1024, f); line++ ) {
            char *p, *q, *param, *value;
            p = strchr(lbuf, '\n');
            if ( p == NULL )
                fatal("%s:%d: buffer overflow\n", name, line);
            *p = '\0';
            p = strchr(lbuf, '#');
            if ( p )
                *p = '\0';
            for ( p = lbuf; *p; p++ )
                if( *p != ' ' && *p != '\t' ) break;
            if ( *p == '\0' ) continue;
            param = p;
            p = strchr(p, '=');
            if ( p == NULL ) {
                error("%s:%d: missing equal sign\n", name, line);
                continue;
            }
            for ( q = p - 1; q >= lbuf; q-- )
                if ( *q != ' ' && *q != '\t' ) break;
            *++q = '\0';
            for ( ++p; *p; p++ )
                if ( *p != ' ' && *p != '\t' ) break;
            value = p;
            for ( ; *p; p++ );
            for ( p--; p >= lbuf; p-- )
                if ( *p != ' ' && *p != '\t' ) break;
            *++p = '\0';
            if ( param && value ) {
                PARAMETER_ITEM *item;
                item = find_parameter_item(param);
                if ( item == NULL ) {
                    error("%s:%d: unknown parameter `%s'\n", name, line, param);
                    continue;
                }
                item->value = strdup(value);
                debug("Parameter `%s' is set to `%s'\n", param, value);
            }
        }
    }
}

void
read_parameter_file(void)
{
#if !defined(_WIN32) || defined(cygwin)
    char *name;
    struct passwd *pw;
#endif

    read_parameter_file_1(PARAMETER_FILE);
#if !defined(_WIN32) || defined(cygwin)
    pw = getpwuid(getuid());
    if ( pw == NULL )
        fatal("getpwuid() failed for uid: %d\n", getuid());
    name = xmalloc(strlen(pw->pw_dir) + strlen(PARAMETER_DOTFILE) + 2);
    strcpy(name, pw->pw_dir);
    strcat(name, "/" PARAMETER_DOTFILE);
    read_parameter_file_1(name);
    free(name);
#endif /* _WIN32 */
}

char*
getparam(const char* name)
{
    char *value = getenv(name);
    if ( value == NULL ){
        PARAMETER_ITEM *item = find_parameter_item(name);
        if ( item != NULL )
            value = item->value;
    }
    return value;
}


/** DIRECT connection **/
#define MAX_DIRECT_ADDR_LIST 256

struct ADDRPAIR {
    struct in_addr addr;
    struct in_addr mask;
    char *name;
    int negative;
};

struct ADDRPAIR direct_addr_list[MAX_DIRECT_ADDR_LIST];
int n_direct_addr_list = 0;

void
mask_addr (void *addr, void *mask, int addrlen)
{
    char *a, *m;
    a = addr;
    m = mask;
    while ( 0 < addrlen-- )
        *a++ &= *m++;
}

int
add_direct_addr (struct in_addr *addr, struct in_addr *mask, int negative)
{
    struct in_addr iaddr;
    char *s;
    if ( MAX_DIRECT_ADDR_LIST <= n_direct_addr_list ) {
        error("direct address table is full!\n");
        return -1;
    }
    iaddr = *addr;
    mask_addr(&iaddr, mask, sizeof(iaddr));
    s = strdup(inet_ntoa(iaddr));
    debug("adding direct addr entry: %s%s/%s\n",
          negative? "!": "", s, inet_ntoa(*mask));
    free(s);
    memcpy( &direct_addr_list[n_direct_addr_list].addr,
            &iaddr, sizeof(iaddr));
    memcpy( &direct_addr_list[n_direct_addr_list].mask,
            mask, sizeof(*mask));
    direct_addr_list[n_direct_addr_list].name = NULL;
    direct_addr_list[n_direct_addr_list].negative = negative;
    n_direct_addr_list++;
    return 0;
}


/* add domain/host name entry to direct name table */
int
add_direct_host( const char *name, int negative)
{
    if ( MAX_DIRECT_ADDR_LIST <= n_direct_addr_list ) {
        error("direct address table is full!\n");
        return -1;
    }
    if (*name == '*')
        name++;
    if (*name == '.')
        name++;
    debug("adding direct name entry: %s%s\n", negative? "!": "", name);
    direct_addr_list[n_direct_addr_list].name = downcase(strdup(name));
    direct_addr_list[n_direct_addr_list].negative = negative;
    n_direct_addr_list++;
    return 0;
}


int
parse_addr_pair (const char *str, struct in_addr *addr, struct in_addr *mask)
{
    /* NOTE: */
    /* Assume already be splitted by separator
       and formatted as folowing:
       1)  12.34.56.789/255.255.255.0
       2)  12.34.56.789/24
       3)  12.34.56.
       All above generates same addr/mask pair 12.34.56.0 and 255.255.255.0
    */
    const char *ptr;
    u_char *dsta, *dstm;
    int i, n;

    assert( str != NULL );
    addr->s_addr = 0;
    mask->s_addr = 0;
    ptr = str;
    dsta = (u_char*)&addr->s_addr;
    dstm = (u_char*)&mask->s_addr;
    for (i=0; i<4; i++ ) {
        if ( *ptr == '\0' )
            break;              /* case of format #3 */
        if ( !isdigit(*ptr) )
            return -1;          /* format error: */
        *dsta++ = atoi( ptr );
        *dstm++ = 255;          /* automatic mask for format #3 */
        while ( isdigit(*ptr) ) /* skip digits */
            ptr++;
        if ( *ptr == '.' )
            ptr++;
        else
            break;
    }
    /* At this point, *ptr points '/' or EOS ('\0') */
    if ( *ptr == '\0' )
        return 0;                       /* complete as format #3 */
    if ( *ptr != '/' )
        return -1;                      /* format error */
    /* Now parse mask for format #1 or #2 */
    ptr++;
    mask->s_addr = 0;                   /* clear automatic mask */

    if ( strchr( ptr, '.') ) {
        /* case of format #1 */
        dstm = (u_char*)&mask->s_addr;
        for (i=0; i<4; i++) {
            if ( !isdigit(*ptr) )
                return -1;              /* format error: */
            *dstm++ = atoi(ptr);
            while ( isdigit(*ptr) )     /* skip digits */
                ptr++;
            if ( *ptr == '.' )
                ptr++;
            else
                break;                  /* from for loop */
        }
        /* complete as format #1 */
    } else {
        /* case of format #2 */
        if ( !isdigit(*ptr) )
            return -1;                  /* format error: */
        n = atoi(ptr);
        if ( n<0 || 32<n)
            return -1;                  /* format error */
        mask->s_addr = (n==0)? 0: htonl(((u_long)0xFFFFFFFF)<<(32-n));
        /* complete as format #1 */
    }
    return 0;
}

void
initialize_direct_addr (void)
{
    int negative;
    int n_entries;
    char *env = NULL, *beg, *next, *envkey = NULL;
    struct in_addr addr, mask;

    if ( relay_method == METHOD_SOCKS ){
        if ( socks_version == 5 )
            envkey = ENV_SOCKS5_DIRECT;
        else
            envkey = ENV_SOCKS4_DIRECT;
        env = getparam(envkey);
        if ( env == NULL )
            env = getparam(ENV_SOCKS_DIRECT);
    } else if ( relay_method == METHOD_HTTP ){
        env = getparam(ENV_HTTP_DIRECT);
    }

    if ( env == NULL )
        env = getparam(ENV_CONNECT_DIRECT);

    if ( env == NULL )
        return;                 /* no entry */
    debug("making direct addr list from: '%s'\n", env);
    env = strdup( env );        /* reallocate to modify */
    beg = next = env;
    n_entries = 0;
    do {
        if ( MAX_DIRECT_ADDR_LIST <= n_entries ) {
            error("too many entries in %s", envkey);
            break;              /* from do loop */
        }
        next = strchr( beg, ',');
        if ( next != NULL )
            *next++ = '\0';
        addr.s_addr = 0;
        mask.s_addr = 0;
        if (*beg == '!') {
            negative = 1;
            beg++;
        } else
            negative = 0;
        if ( !parse_addr_pair( beg, &addr, &mask ) ) {
            add_direct_addr( &addr, &mask, negative );
        } else {
            add_direct_host( beg, negative );
        }
        if ( next != NULL )
            beg = next;
    } while ( next != NULL );

    free( env );
    return;
}

int
cmp_addr (void *addr1, void *addr2, int addrlen)
{
    return memcmp( addr1, addr2, addrlen );
}

int
is_direct_address (const struct in_addr addr)
{
    int i, neg;
    struct in_addr iaddr;

    /* Note: assume IPV4 address !! */
    for (i=0; i<n_direct_addr_list; i++ ) {
        if (direct_addr_list[i].name != NULL)
            continue;                           /* it's name entry */
        neg = direct_addr_list[i].negative;
        iaddr = addr;
        mask_addr( &iaddr, &direct_addr_list[i].mask,
                   sizeof(struct in_addr));
        if (cmp_addr(&iaddr, &direct_addr_list[i].addr,
                     sizeof(struct in_addr)) == 0) {
            char *a, *m;
            a = strdup(inet_ntoa(direct_addr_list[i].addr));
            m = strdup(inet_ntoa(direct_addr_list[i].mask));
            debug("match with: %s/%s%s\n", a, m, neg? " (negative)": "");
            free(a);
            free(m);
            return !neg? 1: 0;
        }
    }
    debug("not matched, addr to be relayed: %s\n", inet_ntoa(addr));
    return 0;                   /* not direct */
}


/* check s1 is ends with s2.
   return 1 if exact match or domain part match.
   return 0 if s1 is shorter than s2 or partial match.
   For example, 
    ends_with("bar.com", "bar.com")        => 1 (exact match)
    ends_with("foo.bar.com", "bar.com")    => 1 (domain match)
    ends_with("foo.beebar.com", "bar.com") => 0 (partial match)
    ends_with("bar", "bar.com")            => 0 (shorter)
 */
domain_match(const char *s1, const char *s2)
{
    int len1, len2;
    const char *tail1, *tail2;
    len1 = strlen(s1);
    len2 = strlen(s2);
    if (len1 < len2 || len1 == 0 || len2 == 0)
        return 0;                               /* not match */
    tail1 = s1 + len1;
    tail2 = s2 + len2;
    while (0 < len1 && 0 < len2) {
        if (*--tail1 != *--tail2)
            break;                              /* not match */
        len1--, len2--;
    }
    if (len2 != 0)
        return 0;                               /* not match */
    /* Now exact match, domain match or partial match.
       Return true if exact or domain match.
       Or continue checking. */
    if (tail1 == s1 || tail1[-1] == '.')
        return 1;                               /* match! */
    return 0;                                   /* not match */
}

/* Check given NAME is ends with one of 
   registered direct name entry.
   Return 1 if matched, or 0.
*/
int
is_direct_name (const char *name)
{
    int len, i;
    const char *tail;
    debug("checking %s is for direct?\n", name);
    name = downcase(strdup(name));
    len = strlen(name);
    if (len < 1)
        return 0;                               /* false */
    tail = &name[len];
    for (i=0; i<n_direct_addr_list; i++ ) {
        int dlen, neg;
        const char *dname;
        const char *n, *d;
        dname = direct_addr_list[i].name;
        if (dname == NULL)
            continue;                           /* it's addr/mask entry */
        neg = direct_addr_list[i].negative;
        if (domain_match(name, dname)) {
            debug("match with: %s%s\n", dname, neg? " (negative)": "");
            if (neg) {
                return 0;       /* not direct */
            } else {
                return 1;       /* direct*/
            }
        }
    }
    return 0;                                   /* not matched */
}

/* check to connect to HOST directyly?
   return 1 if to be direct, 0 for else. */
int
check_direct(const char *host)
{
    struct in_addr addr;
    addr.s_addr = inet_addr(host);
    if (addr.s_addr != INADDR_NONE) {
        /* case of IP address */
        if (is_direct_address(addr)) {
            debug("%s is for direct.\n", host);
            return 1;                           /* true */
        }
    } else {
        /* case of hostname */
        if (is_direct_name(host)) {
            debug("%s is for direct.\n", host);
            return 1;                           /* true */
        }
    }
    debug("%s is for not direct.\n", host);
    return 0;                                    /* false */
}


/** TTY operation **/

int intr_flag = 0;

#ifndef _WIN32
void
intr_handler(int sig)
{
    intr_flag = 1;
}

void
tty_change_echo(int fd, int enable)
{
    static struct termios ntio, otio;           /* new/old termios */
    static sigset_t nset, oset;                 /* new/old sigset */
    static struct sigaction nsa, osa;           /* new/old sigaction */
    static int disabled = 0;

    if ( disabled && enable ) {
        /* enable echo */
        tcsetattr(fd, TCSANOW, &otio);
        disabled = 0;
        /* resotore sigaction */
        sigprocmask(SIG_SETMASK, &oset, NULL);
        sigaction(SIGINT, &osa, NULL);
        if ( intr_flag != 0 ) {
            /* re-generate signal  */
            kill(getpid(), SIGINT);
            sigemptyset(&nset);
            sigsuspend(&nset);
            intr_flag = 0;
        }
    } else if (!disabled && !enable) {
        /* set SIGINTR handler and break syscall on singal */
        sigemptyset(&nset);
        sigaddset(&nset, SIGTSTP);
        sigprocmask(SIG_BLOCK, &nset, &oset);
        intr_flag = 0;
        memset(&nsa, 0, sizeof(nsa));
        nsa.sa_handler = intr_handler;
        sigaction(SIGINT, &nsa, &osa);
        /* disable echo */
        if (tcgetattr(fd, &otio) == 0 && (otio.c_lflag & ECHO)) {
            disabled = 1;
            ntio = otio;
            ntio.c_lflag &= ~(ECHO | ECHOE | ECHOK | ECHONL);
            (void) tcsetattr(fd, TCSANOW, &ntio);
        }
    }

    return;
}

#define TTY_NAME "/dev/tty"
int
tty_readpass( const char *prompt, char *buf, size_t size )
{
    int tty, ret = 0;

    tty = open(TTY_NAME, O_RDWR);
    if ( tty < 0 ) {
        error("Unable to open %s\n", TTY_NAME);
        return -1;                              /* can't open tty */
    }
    if ( size <= 0 )
        return -1;                              /* no room */
    write(tty, prompt, strlen(prompt));
    buf[0] = '\0';
    tty_change_echo(tty, 0);                    /* disable echo */
    ret = read(tty,buf, size-1);
    tty_change_echo(tty, 1);                    /* restore */
    write(tty, "\n", 1);                        /* new line */
    close(tty);
    if ( strchr(buf,'\n') == NULL  )
        return -1;
    if ( 0 < ret )
        buf[ret] = '\0';
    return ret;
}

#else  /* _WIN32 */

BOOL __stdcall
w32_intr_handler(DWORD dwCtrlType)
{
    if ( dwCtrlType == CTRL_C_EVENT ) {
        intr_flag = 1;
        return TRUE;
    } else {
        return FALSE;
    }
}

#define tty_readpass w32_tty_readpass
int
w32_tty_readpass( const char *prompt, char *buf, size_t size )
{
    HANDLE in = CreateFile("CONIN$", GENERIC_READ|GENERIC_WRITE,
                           0, NULL, OPEN_EXISTING, 0, NULL);
    HANDLE out = CreateFile("CONOUT$", GENERIC_WRITE,
                            0, NULL, OPEN_EXISTING, 0, NULL);
    DWORD mode;
    DWORD ret, bytes;

    if (in == INVALID_HANDLE_VALUE || out == INVALID_HANDLE_VALUE)
        fatal("Cannot open console. (errno=%d)", GetLastError());

    WriteFile(out, prompt, strlen(prompt), &bytes, 0);
    SetConsoleCtrlHandler(w32_intr_handler, TRUE ); /* add handler */
    GetConsoleMode(in, &mode);
    SetConsoleMode(in, mode&~ENABLE_ECHO_INPUT); /* disable echo */
    ret = ReadFile(in, buf, size, &bytes, 0);
    SetConsoleMode(in, mode);                   /* enable echo */
    SetConsoleCtrlHandler( w32_intr_handler, FALSE ); /* remove handler */
    if ( intr_flag )
        GenerateConsoleCtrlEvent(CTRL_C_EVENT, 0); /* re-signal */
    WriteFile(out,"\n", 1, &bytes, 0);
    CloseHandle(in);
    CloseHandle(out);
    return ret;
}

#endif /* _WIN32 */

/*** User / Password ***/

/* SOCKS5 and HTTP Proxy authentication may requires username and
   password. We ll give it via environment variable or tty.
   Username and password for authentication are decided by
   following rules:

   Username is taken from
     1) server location spec (i.e. user@host:port)
     2) environment variables (see tables.1)
     3) system account name currently logged in.

     Table.1 Order of environment variables for username

        |  SOCKS v5   |  SOCKS v4   |   HTTP proxy    |
      --+-------------+-------------+-----------------+
      1 | SOCKS45_USER | SOCKS4_USER | HTTP_PROXY_USER |
      --+-------------+-------------+                 |
      2 |        SOCKS_USER         |                 |
      --+---------------------------+-----------------+
      3 |              CONNECT_USER                   |
      --+---------------------------------------------+

   Password is taken from
     1) by environment variables (see table.2)
     2) by entering from tty.

     Table.2 Order of environment variables for password

        |    SOCKS v5     |     HTTP proxy      |
      --+-----------------+---------------------+
      1 | SOCKS5_PASSWD   |                     |
      --+-----------------+ HTTP_PROXY_PASSWORD |
      2 | SOCKS5_PASSWORD |                     |
      --+-----------------+---------------------+
      3 |           CONNECT_PASSWORD            |
      --+---------------------------------------+

      Note: SOCKS5_PASSWD which is added in rev. 1.79
            to share value with NEC SOCKS implementation.
 */

char *
determine_relay_user ()
{
    char *user = NULL;
    /* get username from environment variable, or system. */
    if (relay_method == METHOD_SOCKS) {
        if (user == NULL && socks_version == 5)
            user = getparam (ENV_SOCKS5_USER);
        if (user == NULL && socks_version == 4)
            user = getparam (ENV_SOCKS4_USER);
        if (user == NULL)
            user = getparam (ENV_SOCKS_USER);
    } else if (relay_method == METHOD_HTTP) {
        if (user == NULL)
            user = getparam (ENV_HTTP_PROXY_USER);
    }
    if (user == NULL)
        user = getparam (ENV_CONNECT_USER);
    /* determine relay user by system call if not yet. */
    if (user == NULL)
        user = getusername();
    return user;
}

char *
determine_relay_password ()
{
    char *pass = NULL;
    if (pass == NULL && relay_method == METHOD_HTTP)
        pass = getparam(ENV_HTTP_PROXY_PASSWORD);
    if (pass == NULL && relay_method == METHOD_SOCKS)
        pass = getparam(ENV_SOCKS5_PASSWD);
    if (pass == NULL && relay_method == METHOD_SOCKS)
        pass = getparam(ENV_SOCKS5_PASSWORD);
    if (pass == NULL)
        pass = getparam(ENV_CONNECT_PASSWORD);
    return pass;
}


/*** network operations ***/


/* set_relay()
   Determine relay informations:
   method, host, port, and username.
   1st arg, METHOD should be METHOD_xxx.
   2nd arg, SPEC is hostname or hostname:port or user@hostame:port.
   hostname is domain name or dot notation.
   If port is omitted, use 80 for METHOD_HTTP method,
   use 1080 for METHOD_SOCKS method.
   Username is also able to given by 3rd. format.
   2nd argument SPEC can be NULL. if NULL, use environment variable.
 */
int
set_relay( int method, char *spec )
{
    char *buf, *sep, *resolve;

    relay_method = method;

    read_parameter_file();
    initialize_direct_addr();
    if (n_direct_addr_list == 0) {
        debug ("No direct address are specified.\n");
    } else {
        debug ("%d direct address entries.\n", n_direct_addr_list);
    }

    switch ( method ) {
    case METHOD_DIRECT:
        return -1;                              /* nothing to do */

    case METHOD_SOCKS:
        if ( spec == NULL ) {
            switch ( socks_version ) {
            case 5:
                spec = getparam(ENV_SOCKS5_SERVER);
                break;
            case 4:
                spec = getparam(ENV_SOCKS4_SERVER);
                break;
            }
        }
        if ( spec == NULL )
            spec = getparam(ENV_SOCKS_SERVER);

        if ( spec == NULL )
            fatal("Failed to determine SOCKS server.\n");
        relay_port = 1080;                      /* set default first */

        /* determine resolve method */
        if ( socks_resolve == RESOLVE_UNKNOWN ) {
            if ( ((socks_version == 5) &&
                  ((resolve = getparam(ENV_SOCKS5_RESOLVE)) != NULL)) ||
                 ((socks_version == 4) &&
                  ((resolve = getparam(ENV_SOCKS4_RESOLVE)) != NULL)) ||
                 ((resolve = getparam(ENV_SOCKS_RESOLVE)) != NULL) ) {
                socks_resolve = lookup_resolve( resolve );
                if ( socks_resolve == RESOLVE_UNKNOWN )
                    fatal("Invalid resolve method: %s\n", resolve);
            } else {
                /* default */
                if ( socks_version == 5 )
                    socks_resolve = RESOLVE_REMOTE;
                else
                    socks_resolve = RESOLVE_LOCAL;
            }
        }
        break;

    case METHOD_HTTP:
        if ( spec == NULL )
            spec = getparam(ENV_HTTP_PROXY);
        if ( spec == NULL )
            fatal("You must specify http proxy server\n");
        relay_port = 80;                        /* set default first */
        break;
    case METHOD_TELNET:
        if ( spec == NULL )
            spec = getparam(ENV_TELNET_PROXY);
        if ( spec == NULL )
            fatal("You must specify telnet proxy server\n");
        relay_port = 23;                        /* set default first */
    }

    if (expect( spec, HTTP_PROXY_PREFIX)) {
        /* URL format like: "http://server:port/" */
        /* extract server:port part */
        buf = strdup( spec + strlen(HTTP_PROXY_PREFIX));
        buf[strcspn(buf, "/")] = '\0';
    } else {
        /* assume spec is aready "server:port" format */
        buf = strdup( spec );
    }
    spec = buf;

    /* check username in spec */
    sep = strchr( spec, '@' );
    if ( sep != NULL ) {
        *sep = '\0';
        relay_user = strdup( spec );
        spec = sep +1;
    }
    if (relay_user == NULL)
        relay_user = determine_relay_user();

    /* split out hostname and port number from spec */
    sep = strchr(spec,':');
    if ( sep == NULL ) {
        /* hostname only, port is already set as default */
        relay_host = strdup( spec );
    } else {
        /* hostname and port */
        relay_port = atoi(sep+1);
        *sep = '\0';
        relay_host = strdup( spec );
    }
    free(buf);
    return 0;
}


u_short
resolve_port( const char *service )
{
    int port;
    if ( service[strspn (service, digits)] == '\0'  ) {
        /* all digits, port number */
        port = atoi(service);
    } else {
        /* treat as service name */
        struct servent *ent;
        ent = getservbyname( service, NULL );
        if ( ent == NULL ) {
            debug("Unknown service, '%s'\n", service);
            port = 0;
        } else {
            port = ntohs(ent->s_port);
            debug("service: %s => %d\n", service, port);
        }
    }
    return (u_short)port;
}

void
make_revstr(void)
{
    char *ptr;
    size_t len;
    ptr = strstr(rcs_revstr, ": ");
    if (!ptr) {
        revstr = strdup("unknown");
        return;
    }
    ptr += 2;
    /* assume subversion's keyword expansion like "Revision: 96". */
    minor_version = atoi(ptr);
    revstr = xmalloc(20);
    snprintf(revstr, 20, "%d.%d", major_version, minor_version);
}

int
getarg( int argc, char **argv )
{
    int err = 0;
    char *ptr, *server = (char*)NULL;
    int method = METHOD_DIRECT;

    progname = *argv;
    argc--, argv++;

    /* check optinos */
    while ( (0 < argc) && (**argv == '-') ) {
        ptr = *argv + 1;
        while ( *ptr ) {
            switch ( *ptr ) {
            case 's':                           /* use SOCKS */
                method = METHOD_SOCKS;
                break;

            case 'n':                           /* no proxy */
                method = METHOD_DIRECT;
                break;

            case 'h':                           /* use http-proxy */
                method = METHOD_HTTP;
                break;
            case 't':
                method = METHOD_TELNET;
                break;

            case 'S':                           /* specify SOCKS server */
                if ( 1 < argc ) {
                    argv++, argc--;
                    method = METHOD_SOCKS;
                    server = *argv;
                } else {
                    error("option '-%c' needs argument.\n", *ptr);
                    err++;
                }
                break;

            case 'H':                           /* specify http-proxy server */
                if ( 1 < argc ) {
                    argv++, argc--;
                    method = METHOD_HTTP;
                    server = *argv;
                } else {
                    error("option '-%c' needs argument.\n", *ptr);
                    err++;
                }
                break;
            case 'T':                           /* specify telnet proxy server */
                if ( 1 < argc ) {
                    argv++, argc--;
                    method = METHOD_TELNET;
                    server = *argv;
                } else {
                    error("option '-%c' needs argument.\n", *ptr);
                    err++;
                }
                break;

            case 'c':
                 if (1 < argc) {
                      argv++, argc--;
                      telnet_command = *argv;
                 } else {
                      error("option '%c' needs argument.\n", *ptr);
                      err++;
                 }
                 break;

            case 'P':
                f_hold_session = 1;
                /* without break */
            case 'p':                          /* specify port to forward */
                if ( 1 < argc ) {
                    argv++, argc--;
                    local_type = LOCAL_SOCKET;
                    local_port = resolve_port(*argv);
                } else {
                    error("option '-%c' needs argument.\n", *ptr);
                    err++;
                }
                break;

#ifndef _WIN32
            case 'w':
                if ( 1 < argc ) {
                    argv++, argc--;
                    connect_timeout = atoi(*argv);
                } else {
                    error("option '-%c' needs argument.\n", *ptr);
                    err++;
                }
                break;
#endif /* not _WIN32 */

            case '4':
                socks_version = 4;
                break;

            case '5':
                socks_version = 5;
                break;

            case 'a':
                if ( 1 < argc ) {
                    argv++, argc--;
                    socks5_auth = *argv;
                } else {
                    error("option '-%c' needs argument.\n", *ptr);
                    err++;
                }
                break;

            case 'R':                           /* specify resolve method */
                if ( 1 < argc ) {
                    argv++, argc--;
                    socks_resolve = lookup_resolve( *argv );
                } else {
                    error("option '-%c' needs argument.\n", *ptr);
                    err++;
                }
                break;

            case 'V':                           /* print version */
                fprintf(stderr, "%s\nVersion %s\n", progdesc, revstr);
                exit(0);

            case 'd':                           /* debug mode */
                f_debug++;
                break;

            default:
                error("unknown option '-%c'\n", *ptr);
                err++;
            }
            ptr++;
        }
        argc--, argv++;
    }

    /* check error */
    if ( 0 < err )
        goto quit;

    set_relay( method, server );

    /* check destination HOST (MUST) */
    if ( argc == 0  ) {
        fprintf(stderr, "%s\nVersion %s\n", progdesc, revstr);
        fprintf(stderr, usage, progname);
        exit(0);
    }
    dest_host = argv[0];
    /* decide port or service name from programname or argument */
    if ( ((ptr=strrchr( progname, '/' )) != NULL) ||
         ((ptr=strchr( progname, '\\')) != NULL) )
        ptr++;
    else
        ptr = progname;
    if ( dest_port == 0 ) {
        /* accept only if -P is not specified. */
        if ( 1 < argc ) {
            /* get port number from argument (prior to progname) */
            /* NOTE: This way is for cvs ext method. */
            dest_port = resolve_port(argv[1]);
        } else if ( strncmp( ptr, "connect-", 8) == 0 ) {
            /* decide port number from program name */
            char *str = strdup( ptr+8 );
            str[strcspn( str, "." )] = '\0';
            dest_port = resolve_port(str);
            free(str);
        }
    }
    /* check port number */
    if ( dest_port <= 0 ) {
        error( "You must specify the destination port correctly.\n");
        err++;
        goto quit;
    }
    if ( (relay_method != METHOD_DIRECT) && (relay_port <= 0) ) {
        error("Invalid relay port: %d\n", dest_port);
        err++;
        goto quit;
    }

quit:
    /* report for debugging */
    debug("relay_method = %s (%d)\n",
          method_names[relay_method], relay_method);
    if ( relay_method != METHOD_DIRECT ) {
        debug("relay_host=%s\n", relay_host);
        debug("relay_port=%d\n", relay_port);
        debug("relay_user=%s\n", relay_user);
    }
    if ( relay_method == METHOD_SOCKS ) {
        debug("socks_version=%d\n", socks_version);
        debug("socks_resolve=%s (%d)\n",
              resolve_names[socks_resolve], socks_resolve);
    }
    debug("local_type=%s\n", local_type_names[local_type]);
    if ( local_type == LOCAL_SOCKET ) {
        debug("local_port=%d\n", local_port);
        if (f_hold_session)
            debug ("  with holding remote session.\n");
    }
    debug("dest_host=%s\n", dest_host);
    debug("dest_port=%d\n", dest_port);
    if ( 0 < err ) {
        fprintf(stderr, usage, progname);
        exit(1);
    }
    return 0;
}

#ifndef _WIN32
/* Time-out feature is not allowed for Win32 native compilers. */
/* MSVC and Borland C cannot but Cygwin and UNIXes can. */

/* timeout signal hander */
void
sig_timeout(void)
{
    signal( SIGALRM, SIG_IGN );
    alarm( 0 );
    error( "timed out\n" );
    exit(1);
}

/* set timeout param = seconds, 0 clears */
void
set_timeout(int timeout)
{
    /* This feature is allowed for UNIX or cygwin environments, currently */
    if ( timeout == 0 ) {
        debug( "clearing timeout\n" );
        signal( SIGALRM, SIG_IGN );
        alarm( 0 );
    } else {
        debug( "setting timeout: %d seconds\n", timeout );
        signal(SIGALRM, (void *)sig_timeout);
        alarm( timeout );
    }
}
#endif

#if !defined(_WIN32) && !defined(__CYGWIN32__)
void
switch_ns (struct sockaddr_in *ns)
{
    res_init();
    memcpy (&_res.nsaddr_list[0], ns, sizeof(*ns));
    _res.nscount = 1;
    debug("Using nameserver at %s\n", inet_ntoa(ns->sin_addr));
}
#endif /* !_WIN32 && !__CYGWIN32__ */

/* TODO: IPv6
   TODO: fallback if askpass execution failed.
 */

int
local_resolve (const char *host, struct sockaddr_in *addr)
{
    struct hostent *ent;
    if ( strspn(host, dotdigits) == strlen(host) ) {
        /* given by IPv4 address */
        addr->sin_family = AF_INET;
        addr->sin_addr.s_addr = inet_addr(host);
    } else {
        debug("resolving host by name: %s\n", host);
        ent = gethostbyname (host);
        if ( ent ) {
            memcpy (&addr->sin_addr, ent->h_addr, ent->h_length);
            addr->sin_family = ent->h_addrtype;
            debug("resolved: %s (%s)\n",
                  host, inet_ntoa(addr->sin_addr));
        } else {
            debug("failed to resolve locally.\n");
            return -1;                          /* failed */
        }
    }
    return 0;                                   /* good */
}

int
open_connection( const char *host, u_short port )
{
    SOCKET s;
    struct sockaddr_in saddr;

    /* resolve address of proxy or direct target */
    if (local_resolve (host, &saddr) < 0) {
        error("can't resolve hostname: %s\n", host);
        return SOCKET_ERROR;
    }
    saddr.sin_port = htons(port);

    debug("connecting to %s:%u\n", inet_ntoa(saddr.sin_addr), port);
    s = socket( AF_INET, SOCK_STREAM, 0 );
    if ( connect( s, (struct sockaddr *)&saddr, sizeof(saddr))
         == SOCKET_ERROR) {
        debug( "connect() failed.\n");
        return SOCKET_ERROR;
    }
    return s;
}

void
report_text( char *prefix, char *buf )
{
    static char work[1024];
    char *tmp;

    if ( !f_debug )
        return;
    if ( !f_report )
        return;                                 /* don't report */
    debug("%s \"", prefix);
    while ( *buf ) {
        memset( work, 0, sizeof(work));
        tmp = work;
        while ( *buf && ((tmp-work) < (int)sizeof(work)-5) ) {
            switch ( *buf ) {
            case '\t': *tmp++ = '\\'; *tmp++ = 't'; break;
            case '\r': *tmp++ = '\\'; *tmp++ = 'r'; break;
            case '\n': *tmp++ = '\\'; *tmp++ = 'n'; break;
            case '\\': *tmp++ = '\\'; *tmp++ = '\\'; break;
            default:
                if ( isprint(*buf) ) {
                    *tmp++ = *buf;
                } else {
                    int consumed = tmp - work;
                    snprintf( tmp, sizeof(work)-consumed,
                              "\\x%02X", (unsigned char)*buf);
                    tmp += strlen(tmp);
                }
            }
            buf++;
            *tmp = '\0';
        }
        debug_("%s", work);
    }

    debug_("\"\n");
}


void
report_bytes( char *prefix, char *buf, int len )
{
    if ( ! f_debug )
        return;
    debug( "%s", prefix );
    while ( 0 < len ) {
        fprintf( stderr, " %02x", *(unsigned char *)buf);
        buf++;
        len--;
    }
    fprintf(stderr, "\n");
    return;
}

int
atomic_out( SOCKET s, char *buf, int size )
{
    int ret, len;

    assert( buf != NULL );
    assert( 0<=size );
    /* do atomic out */
    ret = 0;
    while ( 0 < size ) {
        len = send( s, buf+ret, size, 0 );
        if ( len == -1 )
            fatal("atomic_out() failed to send(), %d\n", socket_errno());
        ret += len;
        size -= len;
    }
    if (!f_report) {
        debug("atomic_out()  [some bytes]\n");
        debug(">>> xx xx xx xx ...\n");
    } else {
        debug("atomic_out()  [%d bytes]\n", ret);
        report_bytes(">>>", buf, ret);
    }
    return ret;
}

int
atomic_in( SOCKET s, char *buf, int size )
{
    int ret, len;

    assert( buf != NULL );
    assert( 0<=size );

    /* do atomic in */
    ret = 0;
    while ( 0 < size ) {
        len = recv( s, buf+ret, size, 0 );
        if ( len == -1 ) {
            fatal("atomic_in() failed to recv(), %d\n", socket_errno());
        } else if ( len == 0 ) {
            fatal( "Connection closed by peer.\n");
        }
        ret += len;
        size -= len;
    }
    if (!f_report) {
        debug("atomic_in()  [some bytes]\n");
        debug("<<< xx xx xx xx ...\n");
    } else {
        debug("atomic_in() [%d bytes]\n", ret);
        report_bytes("<<<", buf, ret);
    }
    return ret;
}

int
line_input( SOCKET s, char *buf, int size )
{
    char *dst = buf;
    if ( size == 0 )
        return 0;                               /* no error */
    size--;
    while ( 0 < size ) {
        switch ( recv( s, dst, 1, 0) ) {        /* recv one-by-one */
        case SOCKET_ERROR:
            error("recv() error\n");
            return -1;                          /* error */
        case 0:
            size = 0;                           /* end of stream */
            break;
        default:
            /* continue reading until last 1 char is EOL? */
            if ( *dst == '\n' ) {
                /* finished */
                size = 0;
            } else {
                /* more... */
                size--;
            }
            dst++;
        }
    }
    *dst = '\0';
    report_text( "<<<", buf);
    return 0;
}

/* cut_token()
   Span token in given string STR until char in DELIM is appeared.
   Then replace contiguous DELIMS with '\0' for string termination
   and returns next pointer.
   If no next token, return NULL.
*/
char *
cut_token( char *str, char *delim)
{
    char *ptr = str + strcspn(str, delim);
    char *end = ptr + strspn(ptr, delim);
    if ( ptr == str )
        return NULL;
    while ( ptr < end )
        *ptr++ = '\0';
    return ptr;
}

const char *
lookup(int num, LOOKUP_ITEM *items)
{
    int i = 0;
    while (0 <= items[i].num) {
        if (items[i].num == num)
            return items[i].str;
        i++;
    }
    return "(unknown)";
}

/* readpass()
   password input routine
   Use ssh-askpass (same mechanism to OpenSSH)
*/
char *
readpass( const char* prompt, ...)
{
    static char buf[1000];                      /* XXX, don't be fix length */
    va_list args;
    va_start(args, prompt);
    vsnprintf(buf, sizeof(buf), prompt, args);
    va_end(args);

    if ( getparam(ENV_SSH_ASKPASS)
#if !defined(_WIN32) && !defined(__CYGWIN32__)
         && getenv("DISPLAY")
#endif /* not _WIN32 && not __CYGWIN32__ */
        ) {
        /* use ssh-askpass to get password */
        FILE *fp;
        char *askpass = getparam(ENV_SSH_ASKPASS), *cmd;
        int cmd_size = strlen(askpass) +1 +1 +strlen(buf) +1 +1;
        cmd = xmalloc(cmd_size);
        snprintf(cmd, cmd_size, "%s \"%s\"", askpass, buf);
        fp = popen(cmd, "r");
        free(cmd);
        if ( fp == NULL )
            return NULL;                        /* fail */
        buf[0] = '\0';
        if (fgets(buf, sizeof(buf), fp) == NULL)
            return NULL;                        /* fail */
        fclose(fp);
    } else {
        tty_readpass( buf, buf, sizeof(buf));
    }
    buf[strcspn(buf, "\r\n")] = '\0';
    return buf;
}

static int
socks5_do_auth_userpass( int s )
{
    unsigned char buf[1024], *ptr;
    char *pass = NULL;
    int len;

    /* do User/Password authentication. */
    /* This feature requires username and password from
       command line argument or environment variable,
       or terminal. */
    if (relay_user == NULL)
        fatal("cannot determine user name.\n");

    /* get password from environment variable if exists. */
    if ((pass=determine_relay_password()) == NULL &&
        (pass=readpass("Enter SOCKS5 password for %s@%s: ",
                       relay_user, relay_host)) == NULL)
        fatal("Cannot get password for user: %s\n", relay_user);

    /* make authentication packet */
    ptr = buf;
    PUT_BYTE( ptr++, 1 );                       /* subnegotiation ver.: 1 */
    len = strlen( relay_user );                 /* ULEN and UNAME */
    PUT_BYTE( ptr++, len );
    strcpy( ptr, relay_user );
    ptr += len;
    len = strlen( pass );                       /* PLEN and PASSWD */
    PUT_BYTE( ptr++, strlen(pass));
    strcpy( ptr, pass );
    ptr += len;
    memset (pass, 0, strlen(pass));             /* erase password */

    /* send it and get answer */
    f_report = 0;
    atomic_out( s, buf, ptr-buf );
    f_report = 1;
    atomic_in( s, buf, 2 );

    /* check status */
    if ( buf[1] == 0 )
        return 0;                               /* success */
    else
        return -1;                              /* fail */
}

static const char *
socks5_getauthname( int auth )
{
    switch ( auth ) {
    case SOCKS5_AUTH_REJECT: return "REJECTED";
    case SOCKS5_AUTH_NOAUTH: return "NO-AUTH";
    case SOCKS5_AUTH_GSSAPI: return "GSSAPI";
    case SOCKS5_AUTH_USERPASS: return "USERPASS";
    case SOCKS5_AUTH_CHAP: return "CHAP";
    case SOCKS5_AUTH_EAP: return "EAP";
    case SOCKS5_AUTH_MAF: return "MAF";
    default: return "(unknown)";
    }
}

typedef struct {
    char* name;
    unsigned char auth;
} AUTH_METHOD_ITEM;

AUTH_METHOD_ITEM socks5_auth_table[] = {
    { "none", SOCKS5_AUTH_NOAUTH },
    { "gssapi", SOCKS5_AUTH_GSSAPI },
    { "userpass", SOCKS5_AUTH_USERPASS },
    { "chap", SOCKS5_AUTH_CHAP },
    { NULL, -1 },
};

int
socks5_auth_parse_1(char *start, char *end){
    int i, len;
    for ( ; *start; start++ )
        if ( *start != ' ' && *start != '\t') break;
    for ( end--; end >= start; end-- ) {
        if ( *end != ' ' && *end != '\t'){
            end++;
            break;
        }
    }
    len = end - start;
    for ( i = 0; socks5_auth_table[i].name != NULL; i++ ){
        if ( strncmp(start, socks5_auth_table[i].name, len) == 0) {
            return socks5_auth_table[i].auth;
        }
    }
    fatal("Unknown auth method: %s\n", start);
    return -1;
}

int
socks5_auth_parse(char *start, unsigned char *auth_list, int max_auth){
    char *end;
    int i = 0;
    while ( i < max_auth ) {
        end = strchr(start, ',');
        if (*start && end) {
            auth_list[i++] = socks5_auth_parse_1(start, end);
            start = ++end;
        } else {
            break;
        }
    }
    if ( *start && ( i < max_auth ) ){
        for( end = start; *end; end++ );
        auth_list[i++] = socks5_auth_parse_1(start, end);
    } else {
        fatal("Too much auth method.\n");
    }
    return i;
}

/* begin SOCKS5 relaying
   And no authentication is supported.
 */
int
begin_socks5_relay( SOCKET s )
{
    unsigned char buf[256], *ptr, *env = socks5_auth;
    unsigned char n_auth = 0; unsigned char auth_list[10], auth_method;
    int len, auth_result, i;

    debug( "begin_socks_relay()\n");

    /* request authentication */
    ptr = buf;
    PUT_BYTE( ptr++, 5);                        /* SOCKS version (5) */

    if ( env == NULL )
        env = getparam(ENV_SOCKS5_AUTH);
    if ( env == NULL ) {
        /* add no-auth authentication */
        auth_list[n_auth++] = SOCKS5_AUTH_NOAUTH;
        /* add user/pass authentication */
        auth_list[n_auth++] = SOCKS5_AUTH_USERPASS;
    } else {
        n_auth = socks5_auth_parse(env, auth_list, 10);
    }
    PUT_BYTE( ptr++, n_auth);                   /* num auth */
    for (i=0; i<n_auth; i++) {
        debug("available auth method[%d] = %s (0x%02x)\n",
              i, socks5_getauthname(auth_list[i]), auth_list[i]);
        PUT_BYTE( ptr++, auth_list[i]);         /* authentications */
    }
    atomic_out( s, buf, ptr-buf );              /* send requst */
    atomic_in( s, buf, 2 );                     /* recv response */
    if ( (buf[0] != 5) ||                       /* ver5 response */
         (buf[1] == 0xFF) ) {                   /* check auth method */
        error("No auth method accepted.\n");
        return -1;
    }
    auth_method = buf[1];

    debug("auth method: %s\n", socks5_getauthname(auth_method));

    switch ( auth_method ) {
    case SOCKS5_AUTH_REJECT:
        error("No acceptable authentication method\n");
        return -1;                              /* fail */

    case SOCKS5_AUTH_NOAUTH:
        /* nothing to do */
        auth_result = 0;
        break;

    case SOCKS5_AUTH_USERPASS:
        auth_result = socks5_do_auth_userpass(s);
        break;

    default:
        error("Unsupported authentication method: %s\n",
              socks5_getauthname( auth_method ));
        return -1;                              /* fail */
    }
    if ( auth_result != 0 ) {
        error("Authentication failed.\n");
        return -1;
    }
    /* request to connect */
    ptr = buf;
    PUT_BYTE( ptr++, 5);                        /* SOCKS version (5) */
    PUT_BYTE( ptr++, 1);                        /* CMD: CONNECT */
    PUT_BYTE( ptr++, 0);                        /* FLG: 0 */
    if ( dest_addr.sin_addr.s_addr == 0 ) {
        /* resolved by SOCKS server */
        PUT_BYTE( ptr++, 3);                    /* ATYP: DOMAINNAME */
        len = strlen(dest_host);
        PUT_BYTE( ptr++, len);                  /* DST.ADDR (len) */
        memcpy( ptr, dest_host, len );          /* (hostname) */
        ptr += len;
    } else {
        /* resolved localy */
        PUT_BYTE( ptr++, 1 );                   /* ATYP: IPv4 */
        memcpy( ptr, &dest_addr.sin_addr.s_addr, sizeof(dest_addr.sin_addr));
        ptr += sizeof(dest_addr.sin_addr);
    }
    PUT_BYTE( ptr++, dest_port>>8);     /* DST.PORT */
    PUT_BYTE( ptr++, dest_port&0xFF);
    atomic_out( s, buf, ptr-buf);               /* send request */
    atomic_in( s, buf, 4 );                     /* recv response */
    if ( (buf[1] != SOCKS5_REP_SUCCEEDED) ) {   /* check reply code */
        error("Got error response from SOCKS server: %d (%s).\n",
              buf[1], lookup(buf[1], socks5_rep_names));
        return -1;
    }
    ptr = buf + 4;
    switch ( buf[3] ) {                         /* case by ATYP */
    case 1:                                     /* IP v4 ADDR*/
        atomic_in( s, ptr, 4+2 );               /* recv IPv4 addr and port */
        break;
    case 3:                                     /* DOMAINNAME */
        atomic_in( s, ptr, 1 );                 /* recv name and port */
        atomic_in( s, ptr+1, *(unsigned char*)ptr + 2);
        break;
    case 4:                                     /* IP v6 ADDR */
        atomic_in( s, ptr, 16+2 );              /* recv IPv6 addr and port */
        break;
    }

    /* Conguraturation, connected via SOCKS5 server! */
    return 0;
}

/* begin SOCKS protocol 4 relaying
   And no authentication is supported.

   There's SOCKS protocol version 4 and 4a. Protocol version
   4a has capability to resolve hostname by SOCKS server, so
   we don't need resolving IP address of destination host on
   local machine.

   Environment variable SOCKS_RESOLVE directs how to resolve
   IP addess. There's 3 keywords allowed; "local", "remote"
   and "both" (case insensitive). Keyword "local" means taht
   target host name is resolved by localhost resolver
   (usualy with gethostbyname()), "remote" means by remote
   SOCKS server, "both" means to try resolving by localhost
   then remote.

   SOCKS4 protocol and authentication of SOCKS5 protocol
   requires user name on connect request.
   User name is determined by following method.

   1. If server spec has user@hostname:port format then
      user part is used for this SOCKS server.

   2. Get user name from environment variable LOGNAME, USER
      (in this order).

*/
int
begin_socks4_relay( SOCKET s )
{
    unsigned char buf[256], *ptr;

    debug( "begin_socks_relay()\n");

    /* make connect request packet
       protocol v4:
         VN:1, CD:1, PORT:2, ADDR:4, USER:n, NULL:1
       protocol v4a:
         VN:1, CD:1, PORT:2, DUMMY:4, USER:n, NULL:1, HOSTNAME:n, NULL:1
    */
    ptr = buf;
    PUT_BYTE( ptr++, 4);                        /* protocol version (4) */
    PUT_BYTE( ptr++, 1);                        /* CONNECT command */
    PUT_BYTE( ptr++, dest_port>>8);     /* destination Port */
    PUT_BYTE( ptr++, dest_port&0xFF);
    /* destination IP */
    memcpy(ptr, &dest_addr.sin_addr, sizeof(dest_addr.sin_addr));
    ptr += sizeof(dest_addr.sin_addr);
    if ( dest_addr.sin_addr.s_addr == 0 )
        *(ptr-1) = 1;                           /* fake, protocol 4a */
    /* username */
    if (relay_user == NULL)
        fatal( "Cannot determine user name.\n");
    strcpy( ptr, relay_user );
    ptr += strlen( relay_user ) +1;
    /* destination host name (for protocol 4a) */
    if ( (socks_version == 4) && (dest_addr.sin_addr.s_addr == 0)) {
        strcpy( ptr, dest_host );
        ptr += strlen( dest_host ) +1;
    }
    /* send command and get response
       response is: VN:1, CD:1, PORT:2, ADDR:4 */
    atomic_out( s, buf, ptr-buf);               /* send request */
    atomic_in( s, buf, 8 );                     /* recv response */
    if ( (buf[1] != SOCKS4_REP_SUCCEEDED) ) {   /* check reply code */
        error("Got error response: %d: '%s'.\n",
              buf[1], lookup(buf[1], socks4_rep_names));
        return -1;                              /* failed */
    }

    /* Conguraturation, connected via SOCKS4 server! */
    return 0;
}

int
sendf(SOCKET s, const char *fmt,...)
{
    static char buf[10240];                     /* xxx, enough? */

    va_list args;
    va_start( args, fmt );
    vsnprintf( buf, sizeof(buf), fmt, args );
    va_end( args );

    report_text(">>>", buf);
    if ( send(s, buf, strlen(buf), 0) == SOCKET_ERROR ) {
        debug("failed to send http request. errno=%d\n", socket_errno());
        return -1;
    }
    return 0;
}

const char *base64_table =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

char *
make_base64_string(const char *str)
{
    static char *buf;
    unsigned char *src;
    char *dst;
    int bits, data, src_len, dst_len;
    /* make base64 string */
    src_len = strlen(str);
    dst_len = (src_len+2)/3*4;
    buf = xmalloc(dst_len+1);
    bits = data = 0;
    src = (unsigned char *)str;
    dst = (unsigned char *)buf;
    while ( dst_len-- ) {
        if ( bits < 6 ) {
            data = (data << 8) | *src;
            bits += 8;
            if ( *src != 0 )
                src++;
        }
        *dst++ = base64_table[0x3F & (data >> (bits-6))];
        bits -= 6;
    }
    *dst = '\0';
    /* fix-up tail padding */
    switch ( src_len%3 ) {
    case 1:
        *--dst = '=';
    case 2:
        *--dst = '=';
    }
    return buf;
}


int
basic_auth (SOCKET s)
{
    char *userpass;
    char *cred;
    const char *user = relay_user;
    char *pass = NULL;
    int len, ret;

    /* Get username/password for authentication */
    if (user == NULL)
        fatal("Cannot decide username for proxy authentication.");
    if ((pass = determine_relay_password ()) == NULL &&
        (pass = readpass("Enter proxy authentication password for %s@%s: ",
                         relay_user, relay_host)) == NULL)
        fatal("Cannot decide password for proxy authentication.");

    len = strlen(user)+strlen(pass)+1;
    userpass = xmalloc(len+1);
    snprintf(userpass, len+1, "%s:%s", user, pass);
    memset (pass, 0, strlen(pass));
    cred = make_base64_string(userpass);
    memset (userpass, 0, len);

    f_report = 0;                               /* don't report for security */
    ret = sendf(s, "Proxy-Authorization: Basic %s\r\n", cred);
    f_report = 1;
    report_text(">>>", "Proxy-Authorization: Basic xxxxx\r\n");

    memset(cred, 0, strlen(cred));
    free(cred);

    return ret;
}

/* begin relaying via HTTP proxy
   Directs CONNECT method to proxy server to connect to
   destination host (and port). It may not be allowed on your
   proxy server.
 */
int
begin_http_relay( SOCKET s )
{
    char buf[1024];
    int result;
    char *auth_what;

    debug("begin_http_relay()\n");

    if (sendf(s,"CONNECT %s:%d HTTP/1.0\r\n", dest_host, dest_port) < 0)
        return START_ERROR;
    if (proxy_auth_type == PROXY_AUTH_BASIC && basic_auth (s) < 0)
        return START_ERROR;
    if (sendf(s,"\r\n") < 0)
        return START_ERROR;

    /* get response */
    if ( line_input(s, buf, sizeof(buf)) < 0 ) {
        debug("failed to read http response.\n");
        return START_ERROR;
    }

    /* check status */
    if (!strchr(buf, ' ')) {
        error ("Unexpected http response: '%s'.\n", buf);
        return START_ERROR;
    }
    result = atoi(strchr(buf,' '));

    switch ( result ) {
    case 200:
        /* Conguraturation, connected via http proxy server! */
        debug("connected, start user session.\n");
        break;
    case 302:                                   /* redirect */
        do {
            if (line_input(s, buf, sizeof(buf)))
                break;
            downcase(buf);
            if (expect(buf, "Location: ")) {
                relay_host = cut_token(buf, "//");
                cut_token(buf, "/");
                relay_port = atoi(cut_token(buf, ":"));
            }
        } while (strcmp(buf,"\r\n") != 0);
        return START_RETRY;

    /* We handle both 401 and 407 codes here: 401 is WWW-Authenticate, which
     * not strictly the correct response, but some proxies do send this (e.g.
     * Symantec's Raptor firewall) */
    case 401:                                   /* WWW-Auth required */
    case 407:                                   /* Proxy-Auth required */
        /** NOTE: As easy implementation, we support only BASIC scheme
            and ignore realm. */
        /* If proxy_auth_type is PROXY_AUTH_BASIC and get
         this result code, authentication was failed. */
        if (proxy_auth_type != PROXY_AUTH_NONE) {
            error("Authentication failed.\n");
            return START_ERROR;
        }
        auth_what = (result == 401) ? "WWW-Authenticate:" : "Proxy-Authenticate:";
        do {
            if ( line_input(s, buf, sizeof(buf)) ) {
                break;
            }
            downcase(buf);
            if (expect(buf, auth_what)) {
                /* parse type and realm */
                char *scheme, *realm;
                scheme = cut_token(buf, " ");
                realm = cut_token(scheme, " ");
                if ( scheme == NULL || realm == NULL ) {
                    debug("Invalid format of %s field.", auth_what);
                    return START_ERROR;         /* fail */
                }
                /* check supported auth type */
                if (expect(scheme, "basic")) {
                    proxy_auth_type = PROXY_AUTH_BASIC;
                } else {
                    debug("Unsupported authentication type: %s", scheme);
                }
            }
        } while (strcmp(buf,"\r\n") != 0);
        if ( proxy_auth_type == PROXY_AUTH_NONE ) {
            debug("Can't find %s in response header.", auth_what);
            return START_ERROR;
        } else {
            return START_RETRY;
        }

    default:
        /* Not allowed */
        debug("http proxy is not allowed.\n");
        return START_ERROR;
    }
    /* skip to end of response header */
    do {
        if ( line_input(s, buf, sizeof(buf) ) ) {
            debug("Can't skip response headers\n");
            return START_ERROR;
        }
    } while ( strcmp(buf,"\r\n") != 0 );

    return START_OK;
}

/* begin relaying via TELNET proxy.
   Sends string specified by telnet_command (-c option) with
   replacing host name and port number to the socket.  */
int
begin_telnet_relay( SOCKET s )
{
    char buf[1024];
    char *cmd;
    char *good_phrase = "connected to";
    char *bad_phrase_list[] = {
        " failed", " refused", " rejected", " closed"
    };
    char sep = ' ';
    int i;

    debug("begin_telnet_relay()\n");

    /* report phrase */
    debug("good phrase: '%s'\n", good_phrase);
    debug("bad phrases");
    sep = ':';
    for (i=0; i< (sizeof(bad_phrase_list) / sizeof(char*)); i++) {
        debug_("%c '%s'", sep, bad_phrase_list[i]);
        sep = ',';
    }
    debug_("\n");

    /* make request string with replacing %h by destination hostname
       and %p by port number, etc. */
    cmd = expand_host_and_port(telnet_command, dest_host, dest_port);
    
    /* Sorry, we send request string now without waiting a prompt. */
    if (sendf(s, "%s\r\n", cmd) < 0) {
        free(cmd);
        return START_ERROR;
    }
    free(cmd);

    /* Process answer from proxy until good or bad phrase is detected.  We
       assume that the good phrase should be appeared only in the final
       line of proxy responses. Bad keywods in the line causes operation
       fail. First checks a good phrase, then checks bad phrases.
       If no match, continue reading line from proxy. */
    while (!line_input(s, buf, sizeof(buf)) && buf[0] != '\0') {
        downcase(buf);
        /* first, check good phrase */
        if (strstr(buf, good_phrase)) {
            debug("good phrase is detected: '%s'\n", good_phrase);
            return START_OK;
        }
        /* then, check bad phrase */
        for (i=0; i<(sizeof(bad_phrase_list)/sizeof(char*)); i++) {
            if (strstr(buf, bad_phrase_list[i]) != NULL) {
                debug("bad phrase is detected: '%s'\n", bad_phrase_list[i]);
                return START_ERROR;
            }
        }
    }
    debug("error reading from telnet proxy\n");

    return START_ERROR;
}


#ifdef _WIN32
/* ddatalen()
   Returns 1 if data is available, otherwise return 0
 */
int
stdindatalen (void)
{
    DWORD len = 0;
    struct stat st;
    fstat( 0, &st );
    if ( st.st_mode & _S_IFIFO ) {
        /* in case of PIPE */
        if ( !PeekNamedPipe( GetStdHandle(STD_INPUT_HANDLE),
                             NULL, 0, NULL, &len, NULL) ) {
            if ( GetLastError() == ERROR_BROKEN_PIPE ) {
                /* PIPE source is closed */
                /* read() will detects EOF */
                len = 1;
            } else {
                fatal("PeekNamedPipe() failed, errno=%d\n",
                      GetLastError());
            }
        }
    } else if ( st.st_mode & _S_IFREG ) {
        /* in case of regular file (redirected) */
        len = 1;                        /* always data ready */
    } else if ( _kbhit() ) {
        /* in case of console */
        len = 1;
    }
    return len;
}
#endif /* _WIN32 */

/* relay byte from stdin to socket and fro socket to stdout.
   returns reason of termination */
int
do_repeater( SOCKET local_in, SOCKET local_out, SOCKET remote )
{
    /** vars for local input data **/
    char lbuf[1024];                            /* local input buffer */
    int lbuf_len;                               /* available data in lbuf */
    int f_local;                                /* read local input more? */
    /** vars for remote input data **/
    char rbuf[1024];                            /* remote input buffer */
    int rbuf_len;                               /* available data in rbuf */
    int f_remote;                               /* read remote input more? */
    int close_reason = REASON_UNK;              /* reason of end repeating */
    /** other variables **/
    int nfds, len;
    fd_set ifds, ofds;
    struct timeval *tmo;
#ifdef _WIN32
    struct timeval win32_tmo;
#endif /* _WIN32 */

    /* repeater between stdin/out and socket  */
    nfds = ((local_in<remote)? remote: local_in) +1;
    f_local = 1;                                /* yes, read from local */
    f_remote = 1;                               /* yes, read from remote */
    lbuf_len = 0;
    rbuf_len = 0;

    while ( f_local || f_remote ) {
        FD_ZERO(&ifds );
        FD_ZERO(&ofds );
        tmo = NULL;

        /** prepare for reading local input **/
        if ( f_local && (lbuf_len < (int)sizeof(lbuf)) ) {
#ifdef _WIN32
            if ( local_type != LOCAL_SOCKET ) {
                /* select() on Winsock is not accept standard handle.
                   So use select() with short timeout and checking data
                   in stdin by another method. */
                win32_tmo.tv_sec = 0;
                win32_tmo.tv_usec = 10*1000;    /* 10 ms */
                tmo = &win32_tmo;
            } else
#endif /* !_WIN32 */
            FD_SET( local_in, &ifds );
        }

        /** prepare for reading remote input **/
        if ( f_remote && (rbuf_len < (int)sizeof(rbuf)) ) {
            FD_SET( remote, &ifds );
        }

        /* FD_SET( local_out, ofds ); */
        /* FD_SET( remote, ofds ); */

        if ( select( nfds, &ifds, &ofds, (fd_set*)NULL, tmo ) == -1 ) {
            /* some error */
            error( "select() failed, %d\n", socket_errno());
            return REASON_ERROR;
        }
#ifdef _WIN32
        /* fake ifds if local is stdio handle because
           select() of Winsock does not accept stdio
           handle. */
        if (f_local && (local_type!=LOCAL_SOCKET) && (0<stdindatalen()))
            FD_SET(0,&ifds);            /* data ready */
#endif

        /* remote => local */
        if ( FD_ISSET(remote, &ifds) && (rbuf_len < (int)sizeof(rbuf)) ) {
            len = recv( remote, rbuf + rbuf_len, sizeof(rbuf)-rbuf_len, 0);
            if ( len == 0 || (len == -1 && socket_errno() == ECONNRESET)) {
                debug("connection %s by peer\n",
                      (len==0)? "closed": "reset");
                close_reason = REASON_CLOSED_BY_REMOTE;
                f_remote = 0;                   /* no more read from socket */
                f_local = 0;
            } else if ( len == -1 ) {
                /* error */
                fatal("recv() failed, %d\n", socket_errno());
            } else {
                debug("recv %d bytes\n", len);
                if ( 1 < f_debug )              /* more verbose */
                    report_bytes( "<<<", rbuf+rbuf_len, len);
                rbuf_len += len;
            }
        }

        /* local => remote */
        if ( FD_ISSET(local_in, &ifds) && (lbuf_len < (int)sizeof(lbuf)) ) {
            if (local_type == LOCAL_SOCKET)
                len = recv(local_in, lbuf + lbuf_len,
                           sizeof(lbuf)-lbuf_len, 0);
            else
                len = read(local_in, lbuf + lbuf_len, sizeof(lbuf)-lbuf_len);
            if ( len == 0 ) {
                /* stdin is EOF */
                debug("local input is EOF\n");
                if (!f_hold_session)
                    shutdown(remote, 1);        /* no-more writing */
                f_local = 0;
                close_reason = REASON_CLOSED_BY_LOCAL;
            } else if ( len == -1 ) {
                /* error on reading from stdin */
                if (f_hold_session) {
                    debug ("failed to read from local\n");
                    f_local = 0;
                    close_reason = REASON_CLOSED_BY_LOCAL;
                } else
                    fatal("recv() failed, errno = %d\n", errno);
            } else {
                /* repeat */
                lbuf_len += len;
            }
        }

        /* flush data in buffer to socket */
        if ( 0 < lbuf_len ) {
            len = send(remote, lbuf, lbuf_len, 0);
            if ( len == -1 ) {
                fatal("send() failed, %d\n", socket_errno());
            } else if ( 0 < len ) {
                if ( 1 < f_debug )              /* more verbose */
                    report_bytes( ">>>", lbuf, len);
                /* move data on to top of buffer */
                debug("sent %d bytes\n", len);
                lbuf_len -= len;
                if ( 0 < lbuf_len )
                    memcpy( lbuf, lbuf+len, lbuf_len );
                assert( 0 <= lbuf_len );
            }
        }

        /* flush data in buffer to local output */
        if ( 0 < rbuf_len ) {
            if (local_type == LOCAL_SOCKET)
                len = send( local_out, rbuf, rbuf_len, 0);
            else
                len = write( local_out, rbuf, rbuf_len);
            if ( len == -1 ) {
                fatal("output (local) failed, errno=%d\n", errno);
            }
            rbuf_len -= len;
            if ( len < rbuf_len )
                memcpy( rbuf, rbuf+len, rbuf_len );
            assert( 0 <= rbuf_len );
        }
        if (f_local == 0 && f_hold_session) {
            debug ("closing local port without disconnecting from remote\n");
            f_remote = 0;
            shutdown (local_out, 2);
            close (local_out);
            break;
        }
    }

    return close_reason;
}

int
accept_connection (u_short port)
{
    static int sock = -1;
    int connection;
    struct sockaddr_in name;
    struct sockaddr client;
    int socklen;
    fd_set ifds;
    int nfds;
    int sockopt;

    /* Create the socket. */
    debug("Creating source port to forward.\n");
    sock = socket (PF_INET, SOCK_STREAM, 0);
    if (sock < 0)
        fatal("socket() failed, errno=%d\n", socket_errno());
    sockopt = 1;
    setsockopt (sock, SOL_SOCKET, SO_REUSEADDR,
                (void*)&sockopt, sizeof(sockopt));

    /* Give the socket a name. */
    name.sin_family = AF_INET;
    name.sin_port = htons (port);
    name.sin_addr.s_addr = htonl (INADDR_ANY);
    if (bind (sock, (struct sockaddr *) &name, sizeof (name)) < 0)
        fatal ("bind() failed, errno=%d\n", socket_errno());

    if (listen( sock, 1) < 0)
        fatal ("listen() failed, errno=%d\n", socket_errno());

    /* wait for new connection with watching EOF of stdin. */
    debug ("waiting new connection at port %d (socket=%d)\n", port, sock);
    nfds = sock + 1;
    do {
        int n;
        struct timeval *ptmo = NULL;
#ifdef _WIN32
        struct timeval tmo;
        tmo.tv_sec = 0;
        tmo.tv_usec = 100*1000;                 /* On Windows, 100ms timeout */
        ptmo = &tmo;
#endif /* _WIN32 */
        FD_ZERO (&ifds);
        FD_SET ((SOCKET)sock, &ifds);
#ifndef _WIN32
        FD_SET (0, &ifds);                      /* watch stdin */
#endif
        n = select (nfds, &ifds, NULL, NULL, ptmo);
        if (n == -1) {
            fatal ("select() failed, %d\n", socket_errno());
            exit (1);
        }
#ifdef _WIN32
        if (0 < stdindatalen()) {
            FD_SET (0, &ifds);          /* fake */
            n++;
        }
#endif
        if (0 < n) {
            if (FD_ISSET(0, &ifds) && (getchar() <= 0)) {
                /* EOF */
                debug ("Give-up waiting port because stdin is closed.");
                exit(0);
            }
            if (FD_ISSET(sock, &ifds))
                break;                          /* socket is stimulated */
        }
    } while (1);
    socklen = sizeof(client);
    connection = accept( sock, &client, &socklen);
    if ( connection < 0 )
        fatal ("accept() failed, errno=%d\n", socket_errno());
    return connection;
}



/** Main of program **/
int
main( int argc, char **argv )
{
    int ret;
    int remote;                                 /* socket */
    int local_in;                               /* Local input */
    int local_out;                              /* Local output */
    int reason;
#ifdef _WIN32
    WSADATA wsadata;
    WSAStartup( 0x101, &wsadata);
#endif /* _WIN32 */

    /* initialization */
    make_revstr();
    getarg( argc, argv );
    debug("Program is $Revision: 100 $\n");

    /* Open local_in and local_out if forwarding a port */
    if ( local_type == LOCAL_SOCKET ) {
        /* Relay between local port and destination */
        local_in = local_out = accept_connection( local_port );
    } else {
        /* Relay between stdin/stdout and desteination */
        local_in = 0;
        local_out = 1;
#ifdef _WIN32
        _setmode(local_in, O_BINARY);
        _setmode(local_out, O_BINARY);
#endif
    }

retry:
#ifndef _WIN32
    if (0 < connect_timeout)
        set_timeout (connect_timeout);
#endif /* not _WIN32 */

    if (check_direct(dest_host))
        relay_method = METHOD_DIRECT;
    /* make connection */
    if ( relay_method == METHOD_DIRECT ) {
        remote = open_connection (dest_host, dest_port);
        if ( remote == SOCKET_ERROR )
            fatal( "Unable to connect to destination host, errno=%d\n",
                   socket_errno());
    } else {
        remote = open_connection (relay_host, relay_port);
        if ( remote == SOCKET_ERROR )
            fatal( "Unable to connect to relay host, errno=%d\n",
                   socket_errno());
    }

    /** resolve destination host (SOCKS) **/
#if !defined(_WIN32) && !defined(__CYGWIN32__)
    if (socks_ns.sin_addr.s_addr != 0)
        switch_ns (&socks_ns);
#endif /* not _WIN32 && not __CYGWIN32__ */
    if (relay_method == METHOD_SOCKS &&
        socks_resolve == RESOLVE_LOCAL &&
        local_resolve (dest_host, &dest_addr) < 0) {
        fatal("Unknown host: %s", dest_host);
    }

    /** relay negociation **/
    switch ( relay_method ) {
    case METHOD_SOCKS:
        if ( ((socks_version == 5) && (begin_socks5_relay(remote) < 0)) ||
             ((socks_version == 4) && (begin_socks4_relay(remote) < 0)) )
            fatal( "failed to begin relaying via SOCKS.\n");
        break;

    case METHOD_HTTP:
        ret = begin_http_relay(remote);
        switch (ret) {
        case START_ERROR:
            close (remote);
            fatal("failed to begin relaying via HTTP.\n");
        case START_OK:
            break;
        case START_RETRY:
            /* retry with authentication */
            close (remote);
            goto retry;
        }
        break;
    case METHOD_TELNET:
        if (begin_telnet_relay(remote) < 0)
             fatal("failed to begin relaying via telnet.\n");
        break;
    }
    debug("connected\n");

#ifndef _WIN32
    if (0 < connect_timeout)
        set_timeout (0);
#endif /* not _WIN32 */

    /* main loop */
    debug ("start relaying.\n");
do_repeater:
    reason = do_repeater(local_in, local_out, remote);
    debug ("relaying done.\n");
    if (local_type == LOCAL_SOCKET &&
        reason == REASON_CLOSED_BY_LOCAL &&
        f_hold_session) {
        /* re-wait at local port without closing remote session */
        debug ("re-waiting at local port %d\n", local_port);
        local_in = local_out = accept_connection( local_port );
        debug ("re-start relaying\n");
        goto do_repeater;
    }
    closesocket(remote);
    if ( local_type == LOCAL_SOCKET)
        closesocket(local_in);
#ifdef _WIN32
    WSACleanup();
#endif /* _WIN32 */
    debug ("that's all, bye.\n");

    return 0;
}

/* ------------------------------------------------------------
   Local Variables:
   compile-command: "cc connect.c -o connect"
   tab-width: 8
   fill-column: 74
   comment-column: 48
   End:
   ------------------------------------------------------------ */

/*** end of connect.c ***/

FTL

2008-11-17T23:37:00.000-08:00

Most of the following conclusions are taken from Intel's "Understanding the Flash Translation Layer (FTL) Specification".

Note: the problem of FTL is that it has no idea about the contents that it handles. Thus when it stores something, it has to find a new place instead of appending to the original place.

FTL is the driver that works in conjunction with an existing operating system (or, in some embedded applications, as the operating system) to make linear flash memory appear to the system like a disk drive. First, it creates “virtual” small blocks of data, or sectors, out of flash’s large erase blocks. Next, it manages data on the flash so that it appears to be “write in place” when in fact it is being stored in different spots in the flash. Finally, FTL manages the flash so there are clean/erased places to store data.

Basically, FTL does one thing: read the block data from the file system, write it at a free/erased location on the flash media and invalidates the block that previously contained the block's data.

For Intel NOR flash, Erased state is 1, programmed state is 0, a 0 cannot be changed back to a 1 except by an erase, and an erase must occur on a full erase block.

The main weakness of a FTL is that it has no idea of what part of an erase block belong to the same file. Thus leads to massive obslated blocks and more often garbage collection. The introduction of SATA 3.0 interface can solve this problem, with the new TRIM command which tells the underlying FTL which blocks are no longer being used and can be erased in garbage collection.

Flash limitations

2008-11-13T19:24:00.000-08:00

As stated in the paper of Jorn Engel's(author of logfs), flash device has some limitations to be a storage device.
1. Flash requires out of place updates of existing data. Before being
able to write to a specific location, that erase block has to be
erased. After being erased, all bits are set to 1. An unclean
unmount at this time will cause data loss, as neither the old nor
the new data can be retrieved.
Notes: which means, transaction writes is a must.

2. Lifetime of flash erase blocks is limited by the number of erase cycles on them. Hardware manufacturers usually guarantee 100.000
erase cycles. This number is per individual erase block.
Notes: in-memory superblock or dynamic superblock? balanced writes.

3. Erase blocks are significantly larger than hard disk sectors or
filesystem blocks. Therefore, erase blocks must be shared by
several filesystem blocks. During operation, erase blocks get par-
tially obsoleted and require garbage collection to free space.
Notes: GC is only one of the ways to solve this problem...

NGFS: From ext4 to btrfs

2008-10-20T00:22:00.000-07:00

In a mail Ted sent to LKML, he described the core filesystem developers' plan for the future: ext4 as interim step to btrfs[1].

From: Theodore Tso
Subject: Re: [RFC] Btrfs mainline plans
Newsgroups: gmane.linux.file-systems, gmane.linux.kernel, gmane.comp.file-systems.ext4
Date: 2008-10-10 03:01:31 GMT
...
...
...
As far as ext4 is concerned, being in the mainline was all upside, and
I believe that having in the kernel *did* accelerate its progress.  It
meant that kernel-wide API changes were applied automatically, and it
meant that kernel developers who wanted to try out ext4 could do so
quite easily.  Yes, in the past two releases I started maintaining
patchsets against a stable kernel; this was mainly to support those
users who didn't want to follow the latest git releases --- and that
was a reflection that ext4 was mature enough that there were stable
kernel users who were interested in using ext4.  I could have used the
-stable infrastructure, but ext4 was changing so rapidly that it was
easier just to maintain a full patchset.  As a matter of fact,
starting with 2.6.27, given that we'll be renaming ext4dev to ext4 in
the 2.6.28 mergeset, the plan is that we'll be submitting patches to
the -stable series.

Yes, ext4 didn't go as quickly as I would have liked, but part of the
problem was I personally didn't have enough time to review the patches
being created by the various ext4 developers, and I wasn't about to
merge patches until they were ready.  We didn't have enough senior
developers on ext4, and it took a while for some of the developers
assigned to the project to get up to speed.  (I was the most senior
developer, but I've never had time assigned by my employer to work on
ext4; it has always something I did on my own time, often late at
night (hint: check the time this mail was sent, and when the last ext4
patchset was sent out last night).  Fortunately, at this point a
number of developers like Aneesh have become comfortable with the
code, and good at writing patches that don't require major review and
changes, and the addition of engineers hired by Red Hat, such as Eric
and Val, have also helped immensely.

As far as btrfs is concerned, one of the things that you may not know
is that about a year ago (on November 12-13, 2007), a small group key
filesystem developers, that included engineers employed by HP, Oracle,
IBM, Intel, HP, and Red Hat, and whose experience included working
with a large number of filesystems: ext2, ext4, ext4, ocfs2, lustre,
btrfs, advfs, reiserfs, and xfs came together for a two day "next
generation filesystem" (NGFS) workshop.  At the end of the that
workshop, there was unaminous agreement (including from yours truly)
that (a) Linux needed a next generation filesystem to be competitive,
(b) Chris Mason's btrfs (with some changes/enhancements discussed
during the workshop) was the best long-term solution for NGFS, and (c)
because creating a new enterprise filesystem always takes longer than
people expect, and even then, it takes a while for enterprise users to
trust a new filesystem for their most critical data, ext4 in the next
generation of filesystems was needed as the bridge to the NGFS.

The reason why we made these recommendations was not to influence open
source developers (which is why we haven't really talked about it a
lot in venues like the LKML) but as recommendations to the management
of the above-mentioned for assigning resources to the project.  (One
of the recommendations we made was that a critical success factor was
that knowledge about the filesystem must be spread throughout multiple
vendors and distributions.)  But I think it is fair to say that btrfs
isn't just a private a project of a single Linux kernel developer, but
rather the design has been discussed and reviewed by a large number of
experienced filesystem architects.  What *is* important is that Chris
is a well-known kernel developer who is trusted to create and maintain
quality kernel code, and his employer *has* apparently given him
enough time that he can do a lot of personal, hands-on development.

Given btrfs's current status, in terms of its functionality, even its
format is not fully cast into stone yet, and given Chris's reputation
and skills as a kernel devleoper, my personal opinion is that we would
not be making a "special case exception" for btrfs to get it into
mainline, but rather something which makes completely good sense.

references:
[1] http://thread.gmane.org/gmane.linux.file-systems/26246/focus=26492

undelete still open files on ext2/3/4

2008-10-19T20:19:00.000-07:00

As mentioned by Ted on linux-ext4 mailing list, there are some ways to get your files back if it is still open:

Some background:
On ext3/4, once deleted, the inode will be put to orphaned inode list. On recovery,on recovery this orphan list is traversed and iput will be called on each of the inodes to mark them as free.

So, theoretically, we have out first solution:
1. provoke a crash and manually remove the inode from the orphan list, then mount the partition as ext3.

But another simple solution exists:
2. kill -STOP the process that owns the file, copy it via "cat /proc/$pid/fd/$fd > rescue-file". and then kill -9 the process if you don't want it to make any further changes.

Gnome Asia Summit 2008

2008-10-19T19:54:00.000-07:00

Gnome Asia Summit 2008于上周末在北航举行。会上有一些很有意思且与我们项目相关(主要是maemo相关)的topic，我总结了一下：

1. Introduction of Gstreamer in maemo[1]
这个topic的speaker是Nokia芬兰研发中心的工程师Huaming Wang。他主要介绍maemo中Gstreamer的应用。在maemo中多媒体数据除了real格式以外都是由Gstreamer来handle的。同时Nokia把一些视频和音频的解码程序固化到了DSP上，从而加强了N8*0上多媒体数据的处理能力。

2. Qt maemo hildon port, making Qt and GTK+ working together in mobile devices
这个topic的speaker是Forum Nokia的maemo首席工程师Kate Alhola，她主要讲strategy上的东东。hildon是Nokia开发并upstream的Linux上移动设备应用程序的framework，实验室之前项目的代码包括现在UI项目上的代码都是基于这个框架的。以前hildon只支持gtk+，现在在maemo Diablo版本中添加了Qt的支持。Kate并没有留下她的slides，比较可惜。。。
这可以作为我们的一个alternative，夏双荣之前提到的gtk+中图形无法准确定位的问题也可以在Qt中很好的解决。但是Qt的一个问题就是lisense。社区版的Qt使用的是GPL，如果我们项目要用Qt的话只有两种办法，要么GPL发布我们的代码，要么向Trolltech购买商业授权。不过Trolltech已经被Nokia收购，估计让Nokia购买商业授权也不会有太大阻力。

3. Out-of-memory management in a mobile GNOME device[2]
这个topic的speaker是Nokia maemo的资深开发人员Kimmo Hamalainen。他主要介绍了如何编写内存受限的移动设备应用程序，以及当内存不足的时候Linux kernel会如何处理，在maemo中又做了哪些方面的改进。

4. Cross-platform GUI Application Design In The View of a Mac Developer[3]
这个topic的speaker是名叫Jiang Jiang的在读研究生。他专注于Mac和Linux平台上的程序开发。他从一个Mac开发人员的角度来介绍了如何设计和开发用户友好的GUI程序。

5. Moblin Hugs Gnome[4]
这个topic的speaker是Intel北京OTC的开源策略经理Xu Chen。moblin是maemo在市场上的主要竞争对手，二者有很多相似之处。比如都是采用Linux内核的开源平台，都有以自己公司为核心的community，都以Gnome mobile作为图形界面，应用程序都使用hildon作为应用程序的框架等。Intel刚刚在国内成立了moblin的team，估计要不了多久就会来学校宣传，北邮嵌入式协会也已经在和陈绪接触，可能用不了多久就会拿到一些moblin的项目。上周例会上王老师提到的３D的桌面效果在moblin上已经有支持，他们用基于openGL的Clutter实现了在3D以及动画效果。maemo方面也打算采用Clutter，他们正在working on it。。。让我比较惊奇的是，Nokia居然打算完全自己去做Clutter的maemo port，“与其指望与他们（指Clutter）合作，不如等着我们来提供给你们（指在座的developer）“。。。搞通信的人的想法到底还是和搞计算机的有本质的区别。。。

6. Metadata management for the Desktop
这个topic的speaker是Nokia芬兰研发中心负责maemo平台和hildon库研发的工程师Richard
Sun。他主要介绍了基于metadata的文件索引和检索工具tracker。tracker是目前Linux平台上三大metadata检索工具（另外两个beagle, strigi）之一。tracker目前focus on的是桌面搜索，即对本地资源的快速索引和检索。目前在maemo中的本地检索也可以使用tracker，而且Nokia方面希望long term support这个项目，所以如果我们项目以后有桌面搜索需要的话，也可以选择通过D-bus直接与trackerd通信来使用tracker的高效检索服务。Richard也没有留下他的slides。。。

references:
[1]http://www.gnome.asia/static/upload/event_file/GNOMEAisaSummit.odp
[2]http://www.gnome.asia/static/upload/event_file/gnome-asia-low-memory-handling.odp
[3]http://www.gnome.asia/static/upload/event_file/gui-app-design.pdf
[4]http://www.gnome.asia/static/upload/event_file/MoblinHugsGnome.pdf