Posterous theme by Cory Watilo

redsocks on android指南

redsocks的作用

redsocks是一个通用的proxy redirector,能实现系统级别的全局代理(HTTP或者socks),从而可以实现HTTP代理或者SSH翻墙。

大概的原理是用iptables把外向的包重定向到本地redsocks开的端口,然后redsocks可以从tcp/ip头里得到包的目标ip的端口,然后就通过代理建立连接。

由于iptables的语法非常灵活,可以非常有效地控制哪些包走代理(国内国外,端口,进程,甚至是Level7的协议种类),但是这个方案也有一个比较致命的缺点。

由于redsocks并非针对http协议,所以只能得到目标地址的ip而不是域名,这样的话在建立连接之前需要有一次dns询问。 这个问题在ssh的情况下是不存在的,因为ssh采用的socks5提供了dns的代理,同时redsocks也支持udp,在config文件里多加一个udp就可以了。 但是在使用http代理的情况下,这个问题必须通过一个干净无污染的dns解决,而且显然,这个dns服务器必须在国内。否则就必须手工维护一个很大的hosts文件了。

cross compile ARM下的redsocks

先下载codesourcery.com提供的gcc arm toolchain,不嫌麻烦也可以自己做一个

$ wget http://www.codesourcery.com/sgpp/lite/arm/portal/package7851/public/arm-none-linux-gnueabi/arm-2010.09-50-arm-none-linux-gnueabi-i686-pc-linux-gnu.tar.bz2
$ md5sum arm-2010.09-50-arm-none-linux-gnueabi-i686-pc-linux-gnu.tar.bz2
f9dbd7a2daf20724e013cc4b5b64d62f  arm-2010.09-50-arm-none-linux-gnueabi-i686-pc-linux-gnu.tar.bz2
$ tar jxf arm-2010.09-50-arm-none-linux-gnueabi-i686-pc-linux-gnu.tar.bz2
$ export PATH=$PATH:`pwd`/arm-2010.09/bin

下载并交叉编译libevent2

$ wget http://monkey.org/~provos/libevent-2.0.10-stable.tar.gz
$ md5sum libevent-2.0.10-stable.tar.gz
a37401d26cbbf28185211d582741a3d4  libevent-2.0.10-stable.tar.gz
$ tar zxf libevent-2.0.10-stable.tar.gz
$ cd libevent-2.0.10-stable
$ ./configure --host=arm-none-linux-gnueabi
$ make
$ cp .libs/libevent.a ..
$ DESTDIR=/tmp make install
$ cd ..

用生成的libevent.a编译redsocks

$ git clone -b libevent2-fix https://github.com/bjin/redsocks
$ cd redsocks
$ sed -i 's/-levent/..\/libevent.a -lrt/g' Makefile
$ CC=arm-none-linux-gnueabi-gcc CFLAGS="-O4 -static -I /tmp/usr/local/include" make
$ file redsocks
redsocks: ELF 32-bit LSB executable, ARM, version 1 (SYSV), statically linked, for GNU/Linux 2.6.16, not stripped

手机端的配置

先说下手机端的要求,必须有iptables,这个在CyanogenMod里是自带的,否则可以从网上下一个。另外显然需要有root权限,最好配合SuperUser这个app。

下面的例子是以比较简单的http代理为例,ssh的情况复杂些,需要额外用openssh建立隧道

$ cat redsocks.conf # redsocks的配置文件
base {
    log_debug = on;
    log_info = on;
    log = "file:/data/redsocks/redsocks.log";
    daemon = on; // 在后台运行
    redirector = iptables;
}
redsocks {
    local_ip = 127.0.0.1;
    local_port = 12345;
    ip = <PROXY IP>;
    port = <PROXY PORT>;
    type = http-connect; // HTTP CONNECT,一般用于HTTPS
    login = "<PROXY USER>"; // 可选
    password = "<PROXY PASS>"; // 可选
}
redsocks {
    local_ip = 127.0.0.1;
    local_port = 54321;
    ip = <PROXY IP>;
    port = <PROXY PORT>;
    type = http-relay; // 一般的HTTP 代理
    login = "<PROXY USER>"; // 可选
    password = "<PROXY PASS>"; // 可选
}

$ cat start_re.sh # 启动iptables重定向的脚本
/system/bin/iptables -t nat -A OUTPUT -p tcp --dport 80 -j REDIRECT --to 54321
/system/bin/iptables -t nat -A OUTPUT -p tcp --dport 443 -j REDIRECT --to 12345
/system/bin/iptables -t nat -A OUTPUT -p udp --dport 53 -j DNAT --to-destination x.x.x.x:53 #用iptables重定向dns包,x.x.x.x必须是国内干净的dns服务器

$ cat start.sh  # 启动redsocks的脚本
cd /data/redsocks
if [ -e redsocks.log ] ; then 
    rm redsocks.log
fi
./redsocks -p /data/redsocks/redsocks.pid

$ cat stop_re.sh # 关闭iptables重定向的脚本
/system/bin/iptables -t nat -F OUTPUT

$ cat stop.sh # 关闭redsocks的脚本
cd /data/redsocks
if [ -e redsocks.pid ]; then
    kill `cat redsocks.pid`
    rm redsocks.pid
else
    echo already killed, anyway, I will try killall
    killall -9 redsocks
fi

$ adb shell mkdir /data/redsocks
$ for file in `ls *.sh` redsocks redsocks.conf; do adb push $file /data/redsocks/; done

最后建议采用Scripter运行脚本,直接调用/data/redsocks/xxx.sh就可以了,全局建议开着redsocks,想翻墙就start_re.sh,想关闭就stop_re.sh

Purely Functional Data Structure笔记(上)

这本书是根据作者Chris Okasaki在CMU的博士论文整理成的书,网上能找到原论文, 但是还是推荐看最终的书。正文中的实现都是用的Standard ML,但是最后有Haskell的 代码。笔记还是完全以Haskell记录。

简单说下Haskell的数据类型的构成,被称之为Algebra Data Type。以二叉树为例

data Tree a = Leaf a
            | Node (Tree a) (Tree a)

这里的Tree a就是一个类型,它按照sum of product的方式组成,sum指这种类型 可能有多种构造函数,这里有LeafNode两个。而LeafNode虽然都是大写字母 开头(必须以大写字母开头),但本质上却是一个函数。额外的,构造函数在之后pattern matching 阶段有重要作用。 最终这个Tree a表示了一棵只有在叶子节点有类型a的信息的二叉树。

1. Introduction

这一章主要阐述了本书介绍的函数式数据结构的两个特点,分别是Persistent和Lazy

  • 在纯函数式语言中,是没有内存这个概念的,所有的函数式数据在生成之后都不会被修改,同时GC会 自动回收再也不会被用到的数据。这样带来的就是Persistence这个特性,对应就是一般的过程式 语言中的Imperactive。(实际上在Haskell中可以用实现基于修改数组的素数筛法,但是代价是所有的数组 操作都是使用了类似于IO的机制,这在Haskell中是不鼓励的)

  • Lazy是一种执行的策略,与strict对应。早期的函数式语言像Lisp和本书使用的standard ML都是用的传统 的较容易实现的执行方式,称之为call-by-value,即在调用一个函数的时候就把所有的的参数都计算出来 之后在调用,这个函数可以是构造函数,所以strict的规则也适用于数据结构。与之对应的就是所谓的call-by-need。 这个可以理解为调用函数的时候传入的参数到最后需要用的时候才会被执行,同时有记忆化的过程,即只会 被执行一次。在复杂的程序中这样定义的执行顺序是很难想清楚的,可以理解成,某个计算总会被托后,只有在 必须算的时候才会被计算。纯的函数式语言中的函数是没有副作用的,就是说不会修改全局的设置, 进行IO操作,所以最终的结果是确定的,是可以记忆化的

这两个内容在后面的章节会有进一步阐述。

2. Persistence

这一章用list和binary search tree介绍了persistence。

  • Haskell(以及大部分函数式语言)中的list和一般意义上的stack类似。但是这里的list是通过一个“指针”指向下一个 元素实现的,通过重用公共的数据在不修改内存已有数据的情况下很容易做到常数时间的各种栈操作。最终不断出栈压栈而形成 的拓扑结构是一棵树,所有的历史状态都保存完好,同时不需要的部分会被GC自动回收。

  • Binary Search Tree,这个需要点想象力,和上边类似,但是最终的效果大概是如果修改在某个叶子节点发生,那么 根节点到叶子节点的路径会被复制。复制出来的路径的最后叶子节点就是新的值,起点就是新的根。

3. Some Familiar Data Structure in a Functional Setting

介绍了一些很容易移植到Persistent这样的环境中的数据结构。由于没有in place的修改,这些数据结构往往在functional环境下 的实现往往非常简洁。

  • 左偏树
  • 二项堆
  • 红黑树(没有介绍删除,删除可以参见matt might的文章

都是比较基础的内容,可以看完代码直接跳过。

4. Lazy Evaluation

刚才说本书使用的standard ML是strict的语言,由于后面内容的需要,这章给standard ML加入了lazy的扩展语法。 Haskell党在跳过之前有几个名词需要弄清楚(以后会大量用到)

  • suspension 指一个被拖后执行的表达式。
  • 如果suspension被执行了称之为realize,之后会被记忆化。
  • force指没有realize就执行,否则直接取结果。
  • stream就是lazy list

5. Fundamentals of Amortization

这一章讲的是均摊复杂度的相关知识,内容也比较基本,但是最后说明了为什么均摊复杂度的数据结构无法直接完美移植到 persistent setting里。

  • 均摊的大致想法是在一串操作序列中虽然每个特定的操作可能有很大的时间复杂度,但是对于任何一个序列的前缀,平均的 复杂度却可以很小。一般来说是前面如果比较省时间,后面就可以大把花时间,所以策略是credit saving的策略。

  • 但是传统均摊分析的前提是每个数据对象都只有一个逻辑上的未来,所以这个操作序列的历史版本是一个list,而在persistent setting中 完全没有这个要求。最后的数据历史版本的拓扑结构会是一棵树,这样如果对反复执行某个复杂度很高的操作,那么就悲剧了。 这个问题在过程式语言中同样适用,只是过程式语言的文化默认了只有一个逻辑未来,所以不会被关注。而在函数式语言中,这却是非常现实的 比如后面章节介绍到的bootstrap技术,在外层数据结构中用了内部的数据结构,在这种情况下,内部的数据结构的就像一般的数一样被操作 往往就无法保证只有一个逻辑未来了。

这章讲了若干个数据结构的复杂度分析,其中Queue的实现最简单,而且非常有代表性:

data BatchedQueue a = BQ [a] [a]

check [] r = BQ (reverse r) []
check f r = BQ f r

instance Queue BatchedQueue where
    empty = BQ [] []
    isEmpty (BQ f r) = null f

    snoc (BQ f r) c = check f (x:r)

    head (BQ [] _) = error "empty queue"
    head (BQ (x:f) r) = x

    tail (BQ [] _) = error "empty queue"
    tail (BQ (x:f) r) = check f r

大概的想法是用两个list模拟队列,弹队列就从前面list弹一个元素,压队列就压入后面的list,当弹队列的时候发现前面list为空的时候 就把后面的list reverse之后变成前面的操作。(注意这里的list可以理解成过程式语言上的stack)

如果单考虑一个操作序列(逻辑未来),那么常数的均摊复杂度为常数是显然的,唯一不是常数的操作是reverse,但是在reverse n个元素之前 肯定需要把这n个元素压入队列,均摊一下就是常数了。 注意这里的分析还完全是按照strict的执行策略,但这里的分析确实是正确的,由于 reverse不是incremental的,所以lazy不能起到作用。

另外对于书中提到的banker和physicist的两种分析方法,我想来想去觉得似乎只有形式上的差别,并没有本质上的差别。如果有不同看法欢迎和我交流

6. Amortization and Persistence via Lazy Evaluation

这章是就是利用lazy的特性,把均摊分析中可能出现的多个逻辑未来这样一个问题通过lazy的方式消除了,最终使得均摊分析在persistent的 设置下也能成立。刚才提到了函数式语言中的纯函数是没有副作用的,所以有一个看法是对一个复杂度很高的操作反复执行,他们之间由于 没有副作用的存在,那么应该是所有的调用之间毫无关系。但是这里的纯函数只是在结果上没有副作用,在执行时间上是有的,如果他们内部 都使用了同一个复杂度很大的suspension,那么在第一个花了很多时间之后force这个suspension之后,后面的操作会简单很多,所以如果能实现 这一点,那么就可以忽略多个逻辑未来这样的情况了。这里的均摊和之前还有差别,之前是credit saving,这里由于需要在操作之前有一个很大的 suspension,所以需要在之前做就弄一个suspension,书中理解为debit,然后通过不断realize这些suspension,不断偿还这些债务。

大概的思路如下

  • 在有种理想的情况下,之前建立的suspension由于符合incremental的性质,即realize这个suspension需要很多此操作,同时每次的时间都是一样的, 在这种情况下甚至都不要用到均摊分析了,直接就能给出复杂度了。(值得注意的是,在lazy下最坏复杂度的证明还是很复杂的,但是往往设定一些操作 是strict之后却很容易得到,而且有的时候必须force一些,这在之后的realtime queue中会用到)
  • 在绝大部分其他情况下,往往不这么顺利,在偿还债务的时候有些时候的复杂度会很高,这时候就要对总的偿还债务的过程做个均摊分析。首先在建立了一个 suspension之后会有一部分的代价由于lazy的存在被拖后了,这部分被称作shared cost。在上一章的均摊分析中,是把后面的大的复杂度均摊到之前的若干操作上, 理解为之前便宜的操作为之后的操作省下了很多credit,只要保证credit都是非负的,显然就可以均摊分析了。这里正好相反,采用的是还债的方式
    • 建立一个suspension之后,如果之后的某一个操作需要force这个suspension,则要花一定的时间,这个可以简单理解称实际force这个suspension的时间
    • 然后这个suspension会声明一笔债和上面的时间相同,告诉后面的操作说,如果之前能把债务还完,就不用最后花force suspension的时间了
    • 注意还债其实是由中间的一些操作完成的,而且实际上用的是虚拟的时间,这个过程等价于把最后实际执行force suspension用掉的大量时间转移到了中间的操作上。
    • 总结下,只要能保证force 任何一个suspension之前,这个suspension的债务都有之前的操作用均摊复杂度级别的虚拟时间还完,那么最后的复杂度就是对的。

这章也举了很多例子,还是采用Queue这个比较简单的例子解释

data BankersQueue a = BQ Int [a] Int [a]

check lenf f lenr r = 
    if lenr <= lenf then BQ lenf f lenr r
    else BQ (lenf + lenr) (f ++ reverse r) 0 []

instance Queue BankersQueue where
    empty = BQ 0 [] 0 []
    isEmpty (BQ lenf f lenr r) = (lenf == 0)

    snoc (BQ lenf f lenr r) x = check lenf f (lenr+1) (x:r)

    head (BQ lenf [] lenr r) = error "empty queue"
    head (BQ lenf (x:f') lenr r) = x

    tail (BQ lenf [] lenr r) = error "empty queue"
    tail (BQ lenf (x:f') lenr r) = check (lenf - 1) f' lenr

大概的想法是记录前后两个list的长度,当后面的list的长度超过前面的list之后,就把后面的的list reverse之后接到前面list之后。

f ++ reverse r这就是整个实现的核心,先考虑++,由于++操作是符合incremental性质的,所以前面的f完全可以在均摊分析中忽略,但是 reverse r却不是incremental的,force这个suspension需要length r的时间,但是在建立suspension到后面必须force这个suspension中间有 length f次tail操作,如果这length f次每次还1个债务(实际上并没有花费实际运行时间),最后就可以还清length r的债务了,这时候就 可以放心大胆地调用reverse了,而均摊下来的复杂度就是常数了。

Haskell书单

主要还是测试下posterous的设置

由于我本人能力所限,书单仅供参考,但是有错误或者补充欢迎指出

入门和综合类
Learn You a Haskell for Great Good - 有在线插图版,进阶很快,很有趣
Real World Haskell - 必备
Programming in Haskell

比较老的综合类
The Haskell School of Expression: Learning Functional Programming through Multimedia
Haskell: The Craft of Functional Programming
Introduction to Functional Programming using Haskell

逻辑和离散数学
Discrete Mathematics Using a Computer - 不错的书
The Haskell Road to Logic, Maths and Programming

算法与数据结构
Purely Functional Data Structures - 用的是standard ml,但是实在lazy的设置下,同时也提供了haskell代码,不错的书
Pearls of Functional Algorithm design - haskell实现的各种算法,按照literature programming的方式组织,强烈推荐
Algebra of Programming
Algorithms: A functional programming approach

Haskell编译器的实现和优化
The Implementing of Functional Programming Languages - ghc主要作者 Simon Peyton Jone的书,用的是miranda,但是书偏重后端,扫描版可以在线看
Implementing Functional Languages:a tutorial - 可以作为上一本书的参照,draft可以在线看

语言基础理论
Types and Programming Languages
Functional Programming: Application and Implementation

以Haskell作为基础描述其他领域
Fun of Programming - 算是论文集,覆盖范围很广
Computational Semantics with Functional Programming - 刚出的一本书,从目录看似乎和自然语言有关

期刊
The Monad Reader - http://themonadreader.wordpress.com/ issue4之后都有做得不错的pdf