classpath* vs classpath in spring

记录一下spring里读取资源时的classpath*和classpath表达式的区别。不想看细节的可以直接跳到最后直接看结论。

读取资源的主要逻辑在PathMatchingResourcePatternResolver.getResources

public Resource[] getResources(String locationPattern) throws IOException {
    Assert.notNull(locationPattern, "Location pattern must not be null");
    if (locationPattern.startsWith(CLASSPATH_ALL_URL_PREFIX)) {
        // a class path resource (multiple resources for same name possible)
        if (getPathMatcher().isPattern(locationPattern.substring(CLASSPATH_ALL_URL_PREFIX.length()))) {
            // a class path resource pattern
            return findPathMatchingResources(locationPattern);
        }
        else {
            // all class path resources with the given name
            return findAllClassPathResources(locationPattern.substring(CLASSPATH_ALL_URL_PREFIX.length()));
        }
    }
    else {
        // Only look for a pattern after a prefix here
        // (to not get fooled by a pattern symbol in a strange prefix).
        int prefixEnd = locationPattern.indexOf(":") + 1;
        if (getPathMatcher().isPattern(locationPattern.substring(prefixEnd))) {
            // a file pattern
            return findPathMatchingResources(locationPattern);
        }
        else {
            // a single resource with the given name
            return new Resource[] {getResourceLoader().getResource(locationPattern)};
        }
    }
}
  • classpath*:resource

    代码中的if逻辑,通过findAllClassPathResources,遍历整个classpath,搜索所有名字匹配的文件返回

  • classpath:resource

    代码中的else逻辑,getResourceLoader().getResource(locationPattern)最终调用tomcat提供的WebappClassLoader,从classpath中遍历每个目录(包括jar),寻找指定的resource直到找到指定的第一个匹配文件返回

读取完resource列表之后,AbstractBeanDefinitionReader.loadBeanDefinitions会载入得到resource列表

Resource[] resources = ((ResourcePatternResolver) resourceLoader).getResources(location);
int loadCount = loadBeanDefinitions(resources);

结论

classpath*:resource中读取资源,就相当于把整个classpath下能找到的同名resource按照classpath中的次序拼接成一个大文件后载入,位于classpath后部的resource定义会覆盖前面的。由于tomcat会保证WEB-INF/class下的class会放在classpath中的第一位,所以导致jar中的同名resource定义覆盖app中的定义。

classpath:resource仅载入classpath路径中碰到的第一个resource。

Cookie坑一记

关于Cookie的domain属性,RFC6265上是这么说的:

  1. 如果domain属性缺失,那么该cookie只能对当前host可见。比如,xx.com下有个cookie,Set-Cookie头没有带domain属性,那么这个cookie只对xx.com下的页面可见,a.xx.com等子域名不可见
  2. .xx.com这种domain其实是不合法的,只不过浏览器在见到这种域名的时候,需要自动把最前面的.忽略掉,把xx.com作为cookie的domain,即xx.com及其子域名都可见

thymeleaf的坑一记

记录下thymeleaf 3.0新增的th:fieldth:each中生成的变量结合使用时的坑。

代码就是官方例子https://github.com/thymeleaf/thymeleafexamples-stsm.git,在webapp/WEB-INF/seedstartermng.html中118-131行

<tr th:each="row,rowStat : *{rows}">
  <td th:text="${rowStat.count}">1</td>
  <td>
    <select th:field="*{rows[__${rowStat.index}__].variety}">
      <option th:each="var : ${allVarieties}" th:value="${var.id}" th:text="${var.name}">Thymus Thymi</option>
    </select>
  </td>
  <td>
    <input type="text" th:field="*{rows[__${rowStat.index}__].seedsPerCell}" th:errorclass="fieldError" />
  </td>
  <td>
    <button type="submit" name="removeRow" th:value="${rowStat.index}" th:text="#{seedstarter.row.remove}">Remove row</button>
  </td>
</tr>

其中第二个td取出rows中的每一行的variety,做成一个select下拉菜单,当我尝试用${row.variety}替换原文的*{rows[__${rowStat.index}__].variety}时,页面渲染抛出异常Neither BindingResult nor plain target object for bean name 'row' available as request attribute。多方探索之后得出结论:这是我们使用的问题,设计时特意在遇到这种情况时为了避免服务端无法处理提交后的表单,就抛出异常。

用例子中的代码渲染完生成后的页面为:

<tr>
  <td>1</td>
  <td>
    <select id="rows0.variety" name="rows[0].variety">
      <option value="1">Thymus vulgaris</option>
      <option value="2">Thymus x citriodorus</option>
      <option value="3">Thymus herba-barona</option>
      <option value="4">Thymus pseudolaginosus</option>
      <option value="5">Thymus serpyllum</option>
    </select>
  </td>
  <td>
    <input type="text" id="rows0.seedsPerCell" name="rows[0].seedsPerCell" value="">
  </td>
  <td>
    <button type="submit" name="removeRow" value="0">Remove row</button>
  </td>
</tr>

其中,th:field在渲染时会给目标元素加上id和name属性,name属性取*{...}中表达式的值。由于__${rowStat.index}__是个预处理语句,在渲染之前会直接文本替换,所以最终的表达式为rows[0].variety

但是如果是${row.variety},则最终name会被替换为row.variety,由于浏览器作为客户端无法知道服务端的逻辑,这样之后的每个tr中的元素都是这个表达式,表单提交的时候无法被spring解析成一个list对象,就会出现错误。

官方站在实现角度的解释可以看这个issue

XPath备忘

最近写了几个scrapy的爬虫程序,里面用到了xpath,写个日志记录一下用法。

XPath是什么

XPath是一种用于xml、html等结构化文档中寻址定位特定元素等描述性语言

XPath主要功能

下面以如下测试文档为例进行说明:

<html>
    <body>
        <contents id="content">
        <para><a href="one.html" class="normal-link">One</a></para>
        <para><a href="two.html" class="normal-link">Two</a></para>
        <para><a href="three.html" class="ex-link">Three</a></para>
        </contents>
    </body>
</html>

精确路径寻址

指通过精确制定的路径取得元素。例如

和unix文件系统概念一致,有如下几种定位方式:

  • 绝对路径,/html/body/contents/para能查找出文档中的三个para元素
  • 相对路径,在/html/body路径下,/contents/para同样也能查找出这三个para元素
  • 父级路径,.表示当前路径,..表示当前路径的父级路径

模糊路径寻址

不需要指定绝对路径或根据当前路径确定的相对路径,只需要指定某个子结构,就能查找出所有符合这个子结构的元素。如

  • //contents/para在任何路径下,都能查找到整个文档下的这三个para元素
  • .//contents/para能在当前路径下,查找到子节点中任何符合contents/para结构的元素

节点属性匹配

格式:元素[@属性="xxx"]

  • a[@class="normal-link"]能查找出两个有带normal-link class的a链
  • para[a/@class="ex-link"]能查找出一级子元素中有带ex-link class的a链的para元素,这里就是<para><a href="three.html" class="ex-link">Three</a></para>

属性选择

查找某个元素中的特定属性值,如:a[@class="ex-link"]/@href能读取第三个a链的href值

内置函数

  • node(),返回任意种类的节点。比如和内置关键字child组合成/html/body/contents/child::node(),可以选择所有的para节点
  • text(),返回节点中包含的文本。/html/body/contents/para/a[@class="ex-link"]/text()返回Three。特别的,和模糊路径寻址配合,如/html/body/contents//text(),能返回contents下的One Two Three字符串

搭建智能翻墙路由器

本文着重介绍如何搭建智能翻墙路由器,实现避免DNS污染,并且自动根据是否是国内IP来决定是否翻墙,从而使任何连接路由器的设备无障碍穿墙出去。

思路是,用shadowsocks建立起翻墙代理服务,用shadowsocks的udp relay模式转发DNS请求,解决DNS污染,再配置iptables根据IP决定是否走shadowsocks来翻墙。

准备材料

  • 能刷OpenWrt的智能路由器。我用的是小米路由器MINI,16MB ROM,128MB DDR2内存,MT7620A处理器,运行毫无压力(真的不是广告。。。)
  • OpenWrt。这里选的是PandoraBox
  • shadowsocks client,PandoraBox自带
  • ChinaDNS,PandoraBox自带
  • VPS一台
  • shadowsocks server,选用C实现:shadowsocks-libev,go和Python版没有UDP relay功能,不能实现DNS请求转发

步骤

shadowsocks server

shadowsocks-libev的安装参考http://shadowsocks.org/en/download/servers.html中的“C with libev”一节

安装完成之后将如下配置写入config.json

{
    "server":"0.0.0.0",
    "server_port":8025,
    "password":"123456",
    "timeout":300,
    "method":"aes-256-cfb"
}

分别指定了服务器的binding address,端口,密码,超时时间和加密方式。按需更改

在远程VPS上启动shadowsocks server: ss-server -c config.json -u

注意得加上-u选项,enable udprelay mode。用作DNS请求转发,避免DNS污染。

shadowsocks client

在本地路由器上起shadowsocks client

ss-redir

ss-redir用于将客户端的原始数据封装成shadowsocks协议内容,转发给server,实现透明转发。

在本地路由器启动ss-redir: ss-redir -s "your_server_ip" -p "your_server_port" -l "local_service_port" -m "encryption_method" -k "server_password" -f "pid_file_path" 注意这里不需要-u选项,转发的是TCP包,ss-redir也不支持这个选项。

ss-tunnel

ss-tunnel用于实现本地port forward,和ssh的port forward一样,只是加密方式用了shadowsocks协议,用于在本地起服务,转发DNS请求

在本地路由器启动ss-tunnel: ss-tunnel -s "your_server_ip" -p "your_server_port" -l "local_service_port" -m "encryption_method" -k "server_password" -L "server_ip:server_port" -f "pid_file_path" -u

这个-L选项理论上可以填国外DNS的IP/PORT,比如8.8.8.8:53,我在我的VPS起了一个DNS转发服务,填了自己的IP/PORT,效果应该一样。-u是开启udp relay,DNS是UDP包嘛

ChinaDNS

如果所有DNS请求都走国外DNS server,国内有些网站(如微博)在海外有服务器,就会比较慢。ChinaDNS保证的就是国内域名能解析成国内IP,国外域名解析成国外IP。

在本地路由器启动ChinaDNS: chinadns -l /etc/chinadns_iplist.txt -c /etc/chinadns_chnroute.txt -d -p "local_dns_port" -s 114.114.114.114,127.0.0.1:8026

-s选项后加以逗号分隔的DNS服务器列表,最好国内、国外各有一个。由于前面通过ss-tunnel在本地起了一个端口转发到我的DNS服务,所以填的是127.0.0.1:8026

ChinaDNS原理是,向所有列表中的DNS server发DNS请求,判断结果可信任条件是:国内DNS解析出的是国内IP,国外DNS解析出的是国外IP,/etc/chinadns_chnroute.txt里包含了国内IP网段,/etc/chinadns_iplist.txt里包含的是常见的被污染后的DNS解析结果IP。这样只要通过dnsmasq之类的把本地DNS请求转发到ChinaDNS的端口上,就能解决DNS污染的问题。

iptables

前面的准备工作完成之后,只要配置一下iptables,将国内TCP流量直接放行,国外TCP流量转发到ss-redir起的端口就行,判断依据是IP。

在nat表中新建一个SHADOWSOCKS链

iptables -t nat -N SHADOWSOCKS

远程VPS流量直接放行

iptables -t nat -A SHADOWSOCKS -d xxx.xxx.xx.xxx -j RETURN

内网流量直接放行

iptables -t nat -A SHADOWSOCKS -d 0.0.0.0/8 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 10.0.0.0/8 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 127.0.0.0/8 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 169.254.0.0/16 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 172.16.0.0/12 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 192.168.0.0/16 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 224.0.0.0/4 -j RETURN
iptables -t nat -A SHADOWSOCKS -d 240.0.0.0/4 -j RETURN

国内IP流量直接放行(列表较长,这里不列举了,网上随便搜搜就有)

剩下的TCP流量转发到ss-redir端口

iptables -t nat -A SHADOWSOCKS -p tcp -j REDIRECT --to-ports xxx

完工

搞定之后,任何连接这个路由器的设备都能实现透明翻墙了。

以上

关于Python异常处理流程

def f():
    try:
        print 'try'
        raise NameError
    except Exception, e:
        print 'except'
        raise KeyError
    else:
        print 'else'
        raise IOError
    finally:
        print 'finally'
        raise ValueError

在以上代码中,无论try里有没有异常,走得是except还是else,最终抛出的都是finally中的ValueError。为此小记一下Python里的异常处理流程。

Python当前状态的异常信息存储在线程状态PyThreadState中,包括type, value, traceback。无论是主动raise还是bug触发,异常信息最终都会通过PyErr_Restore(Python/errors.c)被修改。

异常处理的主要流程在PyEval_EvalFrameEx(Python/ceval.c)里,也是Python虚拟机的核心处理流程。

先说明几个概念以便理解:

  1. Python虚拟机里PyEval_EvalFrameEx干的活就是物理机里CPU干的活,根据指令作出相应动作
  2. frame:一个函数的执行环境,可以理解为物理机上EBP, ESP等寄存器确定的函数调用栈,外加一点别的状态信息
  3. blockstack:也是一个栈,隶属于一个frame。每当遇到循环或者try异常处理块都会压入一个block对象,块流程完了弹出
  4. traceback:一个链表,记录发生异常时候的调用栈信息
PyObject *
PyEval_EvalFrameEx(PyFrameObject *f, int throwflag)
{

     register enum why_code why; // 每一条指令处理完之后的状态,用来标记是否有异常

     switch(opcode){} // 一个处理字节码指令的巨大switch
     ...

     // 记录traceback,用来在异常最终没有处理时打印调用栈信息
     // 这个why ==WHY_EXCEPTION条件很重要,如果在finally中发生异常,则why的值是WHY_RERAISE,因此不会进入这个条件记录新的traceback,而是直接覆盖当前的traceback,所以在最终的调用栈里,finally异常之前try/except/else中的异常信息也就被覆盖了
       if (why == WHY_EXCEPTION) {
            PyTraceBack_Here(f);

            if (tstate->c_tracefunc != NULL)
                call_exc_trace(tstate->c_tracefunc,
                               tstate->c_traceobj, f);
        }

     // 这种是finally中有异常的状态,reraise
       if (why == WHY_RERAISE)
            why = WHY_EXCEPTION;

     // 栈帧展开,主要为了在当前frame,沿着block栈向上寻找有没有try/except来接住异常

fast_block_end:
        while (why != WHY_NOT && f->f_iblock > 0) {
            /* Peek at the current block. */
            PyTryBlock *b = &f->f_blockstack[f->f_iblock - 1];

           ......

            /* Now we have to pop the block. */
            f->f_iblock--;

           ......

          // 在finally块中
            if (b->b_type == SETUP_FINALLY ||
                ......
                ) {

               // 有异常(raise xxxError或bug触发的情况)
                if (why == WHY_EXCEPTION) {
                    PyObject *exc, *val, *tb;

                    // 取出异常信息,压入执行栈
                    PyErr_Fetch(&exc, &val, &tb);
                    if (tb == NULL) {
                        Py_INCREF(Py_None);
                        PUSH(Py_None);
                    } else
                        PUSH(tb);
                    PUSH(val);
                    PUSH(exc);
                }
                else {
                    // return或者continue语句
                    if (why & (WHY_RETURN | WHY_CONTINUE))
                        PUSH(retval);
                    v = PyInt_FromLong((long)why);
                    PUSH(v);
                }
               // 跳转到END_FINALLY指令进行扫尾工作
                why = WHY_NOT;
                JUMPTO(b->b_handler);
                break;
            }
        } /* unwind stack */

     // 函数返回值为null说明函数中发生异常未处理

    if (why != WHY_RETURN)
        retval = NULL;

     // 栈帧回退,取回上一层函数执行信息

    tstate->frame = f->f_back;

    return retval;
}

补充一点:

dis模块可以“反汇编”Python字节码变成“Python汇编语言”,下面就是示例代码的反汇编结果:

  6           0 SETUP_FINALLY           63 (to 66)
              3 SETUP_EXCEPT            15 (to 21)

  7           6 LOAD_CONST               1 ('try')
              9 PRINT_ITEM
             10 PRINT_NEWLINE

  8          11 LOAD_GLOBAL              0 (NameError)
             14 RAISE_VARARGS            1
             17 POP_BLOCK
             18 JUMP_FORWARD            30 (to 51)

  9     >>   21 DUP_TOP
             22 LOAD_GLOBAL              1 (Exception)
             25 COMPARE_OP              10 (exception match)
             28 POP_JUMP_IF_FALSE       50
             31 POP_TOP
             32 STORE_FAST               0 (e)
             35 POP_TOP

 10          36 LOAD_CONST               2 ('except')
             39 PRINT_ITEM
             40 PRINT_NEWLINE

 11          41 LOAD_GLOBAL              2 (KeyError)
             44 RAISE_VARARGS            1
             47 JUMP_FORWARD            12 (to 62)
        >>   50 END_FINALLY

 13     >>   51 LOAD_CONST               3 ('else')
             54 PRINT_ITEM
             55 PRINT_NEWLINE

 14          56 LOAD_GLOBAL              3 (IOError)
             59 RAISE_VARARGS            1
        >>   62 POP_BLOCK
             63 LOAD_CONST               0 (None)

 16     >>   66 LOAD_CONST               4 ('finally')
             69 PRINT_ITEM
             70 PRINT_NEWLINE

 17          71 LOAD_GLOBAL              4 (ValueError)
             74 RAISE_VARARGS            1
             77 END_FINALLY
             78 LOAD_CONST               0 (None)
             81 RETURN_VALUE

InnoDB引擎索引学习笔记

最近在研究学习MySQL,本文记录下索引相关(主要B-Tree索引)的特性。


索引是什么

数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。

按所用的数据结构分,有B-Tree索引(B+ Tree)、哈希索引、R-Tree索引等。按数据块的顺序和索引节点的逻辑顺序是否一致可以分为聚集索引和非聚集索引。聚集索引由于物理块连续,在范围扫描的时候可以减少磁头寻道时间,因而比非聚集索引高效。

InnoDB索引结构

InnoDB引擎的索引主体结构是B+Tree(这种数据结构的描述可以参考CSDN博主v_JULY_v的从B树、B+树、B*树谈到R 树)。

其中,主键索引(Primary Index)是聚集索引,中间节点是用于查询的边界值,叶子节点就是数据节点,叶子节点之间通过指针形成双向链表。如图:

primary_index.jpg

辅助索引(Secondary Index)同样为B-Tree索引,只是叶子节点不是数据节点,而是对主键的引用。

secondary_index.jpg

由于此特性,InnoDB引擎要求数据表必须有一个主键,如果没有主键,在数据表创建的时候会自动生成一个唯一非空索引替代。这个特性也决定了InnoDB表的主键最好是一个自增的ID序列,这样在后续插入的过程中不会造成数据块的唯一,提升性能。

当所建立的索引为多列索引的时候,例如KEY(a,b,c),中间节点依旧以最左边的一列a进行索引,只是在叶子节点上保存的不仅仅是a,而是(a,b,c)多字段排序后的序列。

性能实测

下面结合实际例子阐述现象和内部结构的关系

首先建立一个测试表:

CREATE TABLE test (
     id INT NOT NULL AUTO_INCREMENT,
     a INT NOT NULL,
     b INT NOT NULL,
     c INT NOT NULL,
     PRIMARY KEY (id),
     KEY(a,b,c)
)ENGINE=InnoDB;

数据项为(a,b,c)在0~200之间的所有组合项,共计8000000行记录。为了消除几次实验中以query cache为代表的各种server cache对实验数据的影响,每次实验后均重启mysql服务。

索引对查询效率的影响

首先是建立KEY(a,b,c)索引前后的性能对比,能很明显地看到索引大幅提升查询速度。没有索引的时候需要做全表扫描,建立索引之后通过B-Tree搜索。

没有索引(除主键,下同)
[SQL]select * from test where a = 0 and b = 1;
Affected rows: 0
Time: 0.324s

建立KEY(a,b,c)
[SQL]select * from test where a = 0 and b = 1;
Affected rows: 0
Time: 0.004s

由于MySQL优化器的优化,where条件中的各个子条件顺序对索引的使用没有影响。

[SQL]select * from test where b = 1 and a = 0;
Affected rows: 0
Time: 0.002s

当使用的列非严格的索引最左前缀时,可以想象,只有a加速了索引搜索,找到所有符合a条件的记录的之后只能顺序扫描检查c是否符合条件。所以相比没有索引时要快,但是慢于使用严格索引最左前缀时的速度。

[SQL]select * from test where a = 0 and c = 1;
Affected rows: 0
Time: 0.043s

当没有使用到a列作为条件时完全没法使用索引,甚至比没有索引时还要慢。因为建表的时候a在前,b、c在后,并且数据节点有序。在没有索引的测试中,InnoDB引擎到a不为0时自动停止搜索。而在这个例子中需要扫描全表找出满足符合条件的b、c,达到完全没法忍受的16秒。

[SQL]select * from test where b = 0 and c = 1;
Affected rows: 0
Time: 16.023s

索引对排序效率的影响

只要能用到索引,并且ORDER BY后面的列在索引中,则顺序还是倒序排序对性能无影响。因为叶子节点是个双向链表,倒序可以从后向前遍历,与顺序的代价相同。

[SQL]select * from test where a = 0 ORDER BY b;
Affected rows: 0
Time: 0.085s

[SQL]select * from test where a = 0 ORDER BY b DESC;
Affected rows: 0
Time: 0.089s

但是,当有两个字段排序的顺序不同时,叶子节点的有序性就无法用在排序中,必须读出所有叶子节点之后再按指定的字段进行一趟排序,所以速度就慢了下来。

[SQL]select * from test where a = 0 ORDER BY b DESC, c DESC;
Affected rows: 0
Time: 0.089s

[SQL]select * from test where a = 0 ORDER BY b ASC, c DESC;
Affected rows: 0
Time: 0.184s

同样,下面的例子中对索引左边的字段a进行范围选择的时候也没法运用索引,因为多个取值的a无法保证b和c字段有序,必须重新排序

[SQL]select * from test where a <= 0 ORDER BY b;
Affected rows: 0
Time: 0.103s

所以,尽可能做到覆盖索引(即where,order by中用到的字段被索引覆盖),能利用索引加速搜索和排序。


参考资料:

《高性能MySQL》,电子工业出版社,2010年1月

Python垃圾回收机制

题记:我是来填坑的。。。

本文主要结合CPython源码分析一下Python的GC机制(面试的时候被问到这个问题,之前理解不深,答得不好,一波大坑啊。。。)


Python GC主要使用引用计数(reference counting)来跟踪和回收垃圾。在引用计数的基础上,通过“标记-清除”(mark and sweep)解决容器对象可能产生的循环引用问题,通过“分代回收”(generation collection)以空间换时间的方法提高垃圾回收效率。

引用计数

引用计数法在对象内部维护了一个被其他对象引用数的引用计数值,当这个引用计数值为0时,说明这个对象不再被其他对象引用,就可以被回收了。

结合源码来看,所有Python对象的头部包含了这样一个结构PyObject(相当于继承自PyObject):

// object.h
struct _object {
    Py_ssize_t ob_refcnt;
    struct PyTypeObject *ob_type;
} PyObject;

ob_refcnt就是引用计数值。

例如,下面是int型对象的定义:

// intobject.h
typedef struct {
        PyObject_HEAD
        long ob_ival;
} PyIntObject;

引用计数法有很明显的优点:

  1. 高效
  2. 运行期没有停顿
  3. 对象有确定的生命周期
  4. 易于实现

原始的引用计数法也有明显的缺点:

  1. 维护引用计数的次数和引用赋值成正比,而不像mark and sweep等基本与回收的内存数量有关。
  2. 无法解决循环引用的问题。A和B相互引用而再没有外部引用A与B中的任何一个,它们的引用计数都为1,但显然应该被回收。

为了解决这两个致命弱点,Python又引入了以下两种GC机制。

标记-清除

“标记-清除”法是为了解决循环引用问题。可以包含其他对象引用的容器对象(如list, dict, set,甚至class)都可能产生循环引用,为此,在申请内存时,所有容器对象的头部又加上了PyGC_Head来实现“标记-清除”机制。

// objimpl.h
typedef union _gc_head {
    struct {
        union _gc_head *gc_next;
        union _gc_head *gc_prev;
        Py_ssize_t gc_refs;
    } gc;
    long double dummy;  /* force worst-case alignment */
} PyGC_Head;

在为对象申请内存的时候,可以明显看到,实际申请的内存数量已经加上了PyGC_Head的大小

// gcmodule.c
PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
    PyObject *op;
    PyGC_Head *g = (PyGC_Head *)PyObject_MALLOC(
                sizeof(PyGC_Head) + basicsize);
    if (g == NULL)
        return PyErr_NoMemory();

    ......

    op = FROM_GC(g);
    return op;
}

举例来说,从list对象的创建中,有如下主要逻辑:

// listobject.c
PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    ......
    op = PyObject_GC_New(PyListObject, &PyList_Type);
    ......
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

_PyObject_GC_TRACK就将对象链接到了第0代对象集合中(后文详述分代回收)。

垃圾标记时,先将集合中对象的引用计数复制一份副本(以免在操作过程中破坏真实的引用计数值):

// gcmodule.c
static void
update_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc = gc->gc.gc_next) {
        assert(gc->gc.gc_refs == GC_REACHABLE);
        gc->gc.gc_refs = FROM_GC(gc)->ob_refcnt;
        assert(gc->gc.gc_refs != 0);
    }
}

然后操作这个副本,遍历对象集合,将被引用对象的引用计数副本值减1:

// gcmodule.c
static void
subtract_refs(PyGC_Head *containers)
{
    traverseproc traverse;
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc=gc->gc.gc_next) {
        traverse = FROM_GC(gc)->ob_type->tp_traverse;
        (void) traverse(FROM_GC(gc),
                   (visitproc)visit_decref,
                   NULL);
    }
}

这个traverse是对象类型定义的函数,用来遍历对象,通过传入的回调函数visit_decref来操作引用计数副本。

例如dict就要在key和value上都用visit_decref操作一遍:

// dictobject.c
static int
dict_traverse(PyObject *op, visitproc visit, void *arg)
{
    Py_ssize_t i = 0;
    PyObject *pk;
    PyObject *pv;

    while (PyDict_Next(op, &i, &pk, &pv)) {
        visit(pk);
        visit(pv);
    }
    return 0;
}

然后根据引用计数副本值是否为0将集合内的对象分成两类,reachable和unreachable,其中unreachable是可以被回收的对象:

// gcmodule.c
static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
    PyGC_Head *gc = young->gc.gc_next;
    while (gc != young) {
        PyGC_Head *next;
        if (gc->gc.gc_refs) {
            PyObject *op = FROM_GC(gc);
            traverseproc traverse = op->ob_type->tp_traverse;
            assert(gc->gc.gc_refs > 0);
            gc->gc.gc_refs = GC_REACHABLE;
            (void) traverse(op,
                            (visitproc)visit_reachable,
                            (void *)young);
            next = gc->gc.gc_next;
        }
        else {
            next = gc->gc.gc_next;
            gc_list_move(gc, unreachable);
            gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
        }
        gc = next;
    }
}

在处理了weak reference和finalizer等琐碎细节后(本文不展开讲述,有兴趣的童鞋请参考python源码),就可以回收unreachable中的对象了。

分代回收

分代回收的整体思想是:将系统中的所有内存块根据其存活时间划分为不同的集合,每个集合就成为一个“代”,垃圾收集频率随着“代”的存活时间的增大而减小,存活时间通常利用经过几次垃圾回收来度量。

用来表示“代”的结构体是gc_generation, 包括了当前代链表表头、对象数量上限、当前对象数量:

// gcmodule.c
struct gc_generation {
    PyGC_Head head;
    int threshold; /* collection threshold */
    int count; /* count of allocations or collections of younger
              generations */
};

Python默认定义了三代对象集合,索引数越大,对象存活时间越长。

#define NUM_GENERATIONS 3
#define GEN_HEAD(n) (&generations[n].head)

/* linked lists of container objects */
static struct gc_generation generations[NUM_GENERATIONS] = {
    /* PyGC_Head,               threshold,  count */
    {{{GEN_HEAD(0), GEN_HEAD(0), 0}},   700,        0},
    {{{GEN_HEAD(1), GEN_HEAD(1), 0}},   10,     0},
    {{{GEN_HEAD(2), GEN_HEAD(2), 0}},   10,     0},
};

新生成的对象会被加入第0代,前面_PyObject_GC_Malloc中省略的部分就是Python GC触发的时机。每新生成一个对象都会检查第0代有没有满,如果满了就开始着手进行垃圾回收:

 g->gc.gc_refs = GC_UNTRACKED;
 generations[0].count++; /* number of allocated GC objects */
 if (generations[0].count > generations[0].threshold &&
     enabled &&
     generations[0].threshold &&
     !collecting &&
     !PyErr_Occurred()) {
          collecting = 1;
          collect_generations();
          collecting = 0;
 }

参考资料:

  1. 《Python源码剖析》,陈儒著,2008
  2. Wikipedia - Reference counting: http://en.wikipedia.org/wiki/Reference_counting
  3. Wikipedia - Garbage collection: http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

利用LD_PRELOAD进行hook

好久没玩hook这种猥琐的东西里,今天在Linux下体验了一把。

loader在进行动态链接的时候,会将有相同符号名的符号覆盖成LD_PRELOAD指定的so文件中的符号。换句话说,可以用我们自己的so库中的函数替换原来库里有的函数,从而达到hook的目的。这和Windows下通过修改import table来hook API很类似。相比较之下,LD_PRELOAD更方便了,都不用自己写代码了,系统的loader会帮我们搞定。但是LD_PRELOAD有个限制:只能hook动态链接的库,对静态链接的库无效,因为静态链接的代码都写到可执行文件里了嘛,没有坑让你填。

上代码

先是受害者,我们的主程序main.c,通过strcmp比较字符串是否相等:

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

int main(int argc, char *argv[])
{
    if( strcmp(argv[1], "test") )
    {
        printf("Incorrect password\n");
    }
    else
    {
        printf("Correct password\n");
    }
    return 0;
}

然后是用来hook的库hook.c:

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

typedef int(*STRCMP)(const char*, const char*);

int strcmp(const char *s1, const char *s2)
{
    static void *handle = NULL;
    static STRCMP old_strcmp = NULL;

    if( !handle )
    {
        handle = dlopen("libc.so.6", RTLD_LAZY);
        old_strcmp = (STRCMP)dlsym(handle, "strcmp");
    }
    printf("hack function invoked. s1=<%s> s2=<%s>\n", s1, s2);
    return old_strcmp(s1, s2);
}

因为hook的目标是strcmp,所以typedef了一个STRCMP函数指针。由于hook的目的是要控制函数行为,所以需要从原库libc.so.6中拿到“正版”strcmp指针,保存成old_strcmp以备调用。

Makefile:

test: main.c hook.so
    gcc -o test main.c

hook.so: hook.c
    gcc -fPIC -shared -o hook.so hook.c -ldl

执行:

$ LD_PRELOAD=./hook.so ./test 123
hack function invoked. s1=<123> s2=<test>
Incorrect password

$ LD_PRELOAD=./hook.so ./test test
hack function invoked. s1=<test> s2=<test>
Correct password

其中有一点不理解的是,dlopen打开libc.so.6能拿到“正版”strcmp地址,打开libc.so就是hook后的地址。照理说libc.so不是libc.so.6的一个软链吗?为什么结果会不一样嘞?


参考资料:

Reverse Engineering with LD_PRELOAD

Linux下编译链接动态库

记录下Linux下编译和链接动态库的过程。

一、 编写动态库

头文件so.h:

#ifndef  SO_H
#define  SO_H

int add(int a, int b);


#endif  /*SO_H*/

实现文件so.c:

#include "so.h"

int add(int a, int b)
{
    return a + b;
}

二、编译动态库

gcc so.c -fPIC -shared -o libtest.so

解释一下各个参数含义:

  1. -fPIC:生成位置无关代码(Position Independent Code),只有生成PIC才能通过虚拟页映射达到可执行代码在进程间共享,从而节省内存的目的。
  2. 说明我们要生成的是动态库so(Shared Object)文件,从而进行动态链接。

通过nm -g libtest.so可以看到,导出符号表中已经有add这个符号了:

$ nm -g libtest.so 
0000000000000670 T add
0000000000201030 B __bss_start
                 w __cxa_finalize@@GLIBC_2.2.5
0000000000201030 D _edata
0000000000201038 B _end
0000000000000684 T _fini
                 w __gmon_start__
0000000000000540 T _init
                 w _ITM_deregisterTMCloneTable
                 w _ITM_registerTMCloneTable
                 w _Jv_RegisterClasses

三、使用动态库

1. 隐式链接(编译时链接)

编写主程序main.c:

#include <stdio.h>
#include "so.h"

int main(int argc, char *argv[])
{
    printf("%d\n", add(1, 2));
    return 0;
}

使用gcc main.c -L. -ltest -o test进行编译。

  • -L:添加库文件的搜索路径
  • -l:指定需要链接的库。该名称是处在头lib和后缀.so中的名称,如上动态库libtest.so的l参数为-l test

此时通过readelf test -d已经能看到生成的可执行文件test的Dynamic section里依赖libtest.so了

$ readelf test -d

Dynamic section at offset 0xe18 contains 25 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libtest.so]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
......

dynamic symbols中也有一个undefined symbol(add)

$ nm -D test 
                 U add
0000000000601048 B __bss_start
0000000000601048 D _edata
0000000000601050 B _end
00000000004007b4 T _fini
                 w __gmon_start__
0000000000400578 T _init
                 w _ITM_deregisterTMCloneTable
                 w _ITM_registerTMCloneTable
                 w _Jv_RegisterClasses
                 U __libc_start_main
                 U printf

在执行隐式链接的程序之前要注意设置LD_LIBRARY_PATH环境变量,或者把前面生成的libtest.so复制到系统路径下,否则会找不到动态库。

$ ./test 
./test: error while loading shared libraries: libtest.so: cannot open shared object file: No such file or directory

$ export LD_LIBRARY_PATH=.

$ ./test 
3

2. 显式链接(运行时链接)

编写主程序dyn_main.c

#include <stdio.h>
#include <dlfcn.h>

int main(int argc, char *argv[])
{
    void *dl = NULL;
    int (*add)(int a, int b);
    dl = dlopen( "./libtest.so", RTLD_LAZY);
    if( dl == NULL )
    {
        printf("so loading error.\n");
        return 1;
    }
    add = (int(*)(int, int))dlsym(dl, "add");
    if( dlerror() != NULL )
    {
        printf("fun load error.\n");
        return 1;
    }
    printf("%d\n", add(1, 2));
    return 0;
}

使用gcc dyn_main.c -ldl -o dyn_test编译。

这时通过readelf dyn_test -d可以发现,dyn_test不依赖libtest.so:

$ readelf dyn_test -d

Dynamic section at offset 0xe18 contains 25 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libdl.so.2]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
......

dyn_test的dynamic symbols中也没有add:

$ nm -D dyn_test 
                 U dlerror
                 U dlopen
                 U dlsym
                 w __gmon_start__
                 w _ITM_deregisterTMCloneTable
                 w _ITM_registerTMCloneTable
                 w _Jv_RegisterClasses
                 U __libc_start_main
                 U printf
                 U puts

运行程序也不需要设置LD_LIBRARY_PATH环境变量

$ ./dyn_test 
3

参考资料:

  1. Linux动态库的编译与使用 转载
  2. 详细分析Linux动态库的使用方式
  3. How do I list the symbols in a .so file
  4. Import names in ELF binary