2013年1月30日星期三

glibc内存管理ptmalloc2瓶颈分析

之前遇到一个glibc-2.4内存管理的性能问题,这里拿来分析一下。

问题现象是业务程序响应很慢,cpu占用升高。最初怀疑是程序代码逻辑的问题,为确认这一点,首先使用oprofile进行采样分析。

oprofile可以以进程、动态库、内核模块、内核为分析对象,统计cpu具体消耗在什么地方。

使用oprofile进行抓取后,看到并不是上层程序问题,而是glibc在消耗cpu,安装对应glibc版本的debuginfo包之后,看到具体消耗cpu的是以下这一段代码:















为什么以上一段while语句消耗大量cpu?结合上层程序代码和glibc中ptmalloc2管理内存的机制,有以下分析。

首先ptmalloc2是以以下方式管理内存的:

















其中chunk表示一块内存,small bins存储16~512 bytes的内存块链表,相邻的bin之间相差8bytes,large bins存储大于512bytes的不规则大小内存块链表,unsorted bin存放调用free/delete进行内存释放后,未归入small bins和large bins的内存块。

small bins下各链表的内存块大小固定,如以上16下面连接的内存块均为16bytes;而large bins下各链表的内存块大小在一个范围内,如576下面连接的内存块可以为 [576, 640) 大小的内存块,并且从大到小排好序。

调用free/delete之后,内存并不是直接还给操作系统,而归还由ptmalloc2管理。对于属于large bins的free chunk,将放入适合的bin,并且每一个large bin下形成由大到小的有序链表。

以下结构用于表示一个free chunk:







接下来调用malloc/new申请一个大于512bytes的内存块时,将采用best-fit的方式,通过fd指针遍历large bins下某一条链表,查找方法正如以上代码所示。假设有N块内存,那么搜寻best-fit内存块的时间复杂度就是O(N),N值很大时,这将使得后续的malloc/new大于512bytes的调用非常慢。


为缓解这个问题,glibc-2.6释出一个patch,在表示内存块的chunk结构中,除了原连接chunk的双向链表指针fd和bk,增加了fd_nextsize和bk_nextsize指针,用于将size相同的chunk组成双向链表:









当在large bins中查找某大小的chunk时,通过fd_nextsiz遍历链表,而不是fd,这样就跳过了相同大小的chunk,减少无谓遍历:






当然问题并没有真正解决,以上方法在有相当多同样size的chunk时奏效,有大量size不等的大于512bytes的chunk时,同样会有malloc调用返回慢问题。

另struct mallinfo和mallinfo调用可用于获取malloc信息,帮助我们分析ptmalloc2相关问题,其中struct mallinfo中的ordblks字段表示空闲内存块的数量,可以理解为以上的N值。

参考:

复现问题的代码:sizetest.cpp
glibc-2.6中针对该问题的patch:serious performance regression in glibc-2.5 malloc


Have fun!

2013年1月25日星期五

使用dumpmem显示进程内存空间中的内容

面对一些内存占用率无端升高的问题,通过top等系统命令我们可以看到哪个进程消耗了内存。进一步地,我们想了解这些进程到底将什么内容载入内存,这时我们可以用到dumpmem这个工具。

dumpmem使用c编写,底层使用ptrace实现,可以在某进程运行的情况下,在线地dump出该进程内存空间中的内容。

每个进程的虚拟内存空间在内核中用mm_struct管理,其中每一个地址段用vm_area_struct管理,/proc/$/maps即显示进程的所有地址段:









dumpmem即先通过/proc/$/maps文件,读取指定进程的所有虚拟内存地址段,记录于以下结构:








最后通过传递PTRACE_PEEKDATA选项给 ptrace 调用,将内存地址中的内容dump到文件中:












除PTRACE_PEEKDATA选项用于dump出进程内存内容外,PTRACE_ATTACH、PTRACE_TRACEME等选项可用于进程跟踪,在dump在线进程内存内容时用到。

ptrace “跟踪” 指定进程的执行,在被跟踪进程执行系统调用或机器指令时,父进程可捕捉到相关信息,给查看被跟踪进程内存、寄存器信息,甚至修改相关内容、更改代码执行路径提供了条件。

Have fun!

2013年1月10日星期四

自旋锁在用户态下的应用——谈folly库的MicroSpinLock

自旋锁(如pthreads中的pthread_spin_lock)特点是线程一直占用cpu,直到其他线程退出临界区、设置锁释放标志。相比基于OS休眠和唤醒机制的互斥锁(如pthreads中的mutex),自旋锁更适用于临界区短、对cpu延时要求比较高的情况。

而当临界区持续时间较长时,传统的自旋锁会有高cpu占用率的缺点;用户态下的进程又有可能被更高优先级的进程或内核线程抢占的可能,因而不能很准确地计算用户态程序临界区持续时间。

那么有没有什么方法,既能在临界区短时,自旋锁像传统意义那样工作,在临界区持续时间较长时,让出cpu,降低cpu资源消耗呢?

Fackbook folly库的MicroSpinLock就是根据以上需求改进而来的spin lock,下面我们看其具体实现。

MicroSpinLock实现spin lock的核心是cas原语,cas过程是原子的,其依赖于硬件实现,x86上对应cmpxchg指令。cas原语的逻辑如下:










以上addr是lock(可以是一个unsinged char变量)的起始地址,expected是当前进程认为lock起始地址头字节应该等于的值,newValue是当前进程将要赋给lock起始地址头字节的值。

利用cas原语,我们可以设计实现spin lock的方法为:

  1. 设定锁的两种状态enum{ FREE=0, LOCKED=1 }
  2. 当前进程调用cas(&lock, FREE, LOCKED)进行加锁(实际就是尝试改变lock头字节为1)
  3. 若lock头字节不为本进程预期的值0,表示有其他进程已占用锁,cas返回false
  4. 当前进程反复以上过程,直到case返回true,此时本进程加锁成功

由以上逻辑,有以下代码实现:











有了基于cas原语实现的spin lock,我们可以进一步考虑如何在临界区持续时间较长的情况下,如何让spin lock让出cpu。简单地,我们引入一个计数器spinCount,每次尝试加锁时spinCount加1,当spinCount达到一定次数时调用sleep,让进程休眠以让出cpu,如是有以下代码实现:




















基于我们临界区短时使用spin lock的假设,多数是不会出现锁竞争情况的,因而很少会调用sleep进行休眠。我们通过添加一条语句,减少不必要的执行路径:













又因为在锁竞争情况出现时,锁未释放的情况下没必要再进行一次加锁操作,因而代码可以修改为:













以上方法属于锁的double check优化,在lock == FREE条件不达成的情况下,避免不必要的加锁开销。

folly MicroSpinLock源码地址:
https://github.com/facebook/folly/blob/master/folly/SmallLocks.h

Have fun!

2013年1月5日星期六

基数估算算法LogLog

一个数据集中不同数据的数量叫做基数(cradinality),现实中有很多计算基数的需求,如统计网站的UV,统计商城中某一件物品的独立ip点击量。

使用bitmap可以精确地计算基数,并且利用位运算,可以方便地统计以小时、天、周为单位的数据集。但当数据量的范围十分庞大的时候,即使bitmap用一个bit标识一条数据,让要消耗比较多的内存(1亿条数据约需12M内存)。

LogLog是一种估算基数的方法,其以基数统计精度为牺牲,换来很少的内存消耗(1亿条数据仅需1K内存)。LogLog得名于其基数统计内存消耗约为log2log2(N),算法描述如下:

  • 对数据集中的数据进行哈希
  • 取哈希后的哈希值后K bit作为桶编号
  • 计算除用作桶编号的后K bit,哈希值还有多少个0尾缀
  • 最后该数据集中基数约为 2**X*num_buckets*0.79402(其中X=最大0尾缀数/num_buckets)

以上魔数0.79402是一个估算经验值,LogLog简单的算法实现如下:










参考:Damn Cool Algorithms: Cardinality Estimation

          LogLog counting of large cardinalities

Have fun!

2012年12月19日星期三

查找中国防火墙设备ip地址

前两天看到一个用于查找GFC(Great Firewall of China)设备ip的python脚本mongol.py,觉得挺有意思,拿来研究了一下。

这个脚本基于 Internet Censorship in China: Where Does the Filtering Occur? 这篇论文,mongol.py基本就是该论文4.3节Algorithm的实现。除了防火墙设备ip查找算法,论文还阐述了以下内容:

  • 从现有实验结果看,有状态的连接(即已完成三次握手的连接)+ 敏感词 才会触发审查
  • 对访问外国的流量审查严格,国内主要还是靠social control(如人工审查)
  • 国内两大ISP,电信的审查设备主要设置在省区城域网,网通的主要设置在骨干网,因在省区也有审查设备,GFC其实也具备国内流量审查的能力
  • 审查起作用后,链路被阻塞的状态会维持一段时间,这段时间内,即使后续的报文不包含敏感词,也会被阻塞


mongol.py接受一个ip参数,其完成以下工作:

首先新建socket与指定ip 80端口进行连接,发送一条GET消息:
GET / HTTP/1.1      \r\n
Host: ip    \r\n
\r\n

在connect调用返回前,三次握手已经完成。之后拿到response,判断响应状态码,如果是200 OK 或 302 Redirect 或 401 Unauthorized,则表明可与目的ip 80端口建立有效连接。

然后对于有效连接,利用scapy进行ackattack(相当于traceroute),并记录本机到目的ip的中间router设备ip,注意所记录的router中可能有一个就是GFC设备,此时由于还没有发送敏感词,并未触发审查

再之后重新新建一个socket进行目的ip连接,此时发送一条包含敏感词的GET消息:
GET /tibetalk  \r\n
Host: ip  \r\n
\r\n

如果发送后出现socket error,则说明GFC设备在该链路上向本机发送了RST报文(也会向目的ip发送),审查机制被触发

最后再次进行ackattack,因为本机收到RST后,本机到目的ip的链路还会阻塞一段时间,这时即使是不包含敏感词的一个ack报文都会被阻塞,trace到的最后一个ip地址就是GFC设备的ip地址


貌似直接traceroute实现不是基于tcp三次握手的,否则直接traceroute Facebook就可以找到防火墙服务器ip;另对于是否stateful的连接才会触发审查,还可以用netcat工具进行验证。

以上提到的论文作者为查找全中国范围内的GFC设备,提到的一个方法也很有趣,利用中国政府网-部门地方链接以及各种导航网站获取到全国各个地方的网站,以此作为检测工具的目的ip地址参数。

Have fun!

2012年12月15日星期六

微信公众平台开放接口

微信公众平台,是为有更多话语权的人设置的一个功能,这部分人或许是明星,或许是地产大佬,或许是某行业中知道更多内幕、小道消息的人。公众平台的推广口号虽说是每个人都有自己的品牌,但在这本已信息过载的时代,谁会专门设置一个通道,关注某个普通人生活中鸡毛蒜皮的那点事。

本着折腾的精神看了下公众平台的开放接口,目前提供的接口就2个:

  • 网址接入公众平台合法性校验功能
  • 普通微信用户消息回复功能

使用前先需要填一些信息,包括token、URL等:















对于以上第二个功能,普通微信用户向公众平台发送消息时,公众平台再以POST的方式向以上配置的URL发送信息,包含以下一些数据:

  • 文本消息:包括文本消息内容、接受/发送方微信号等
  • 地理位置消息:包括地理位置经纬度等信息
  • 图片消息:包括图片链接等信息
我们部署在指定URL上的应用可以以POST方式回应文本、图文信息。

或许可以利用公众平台开放接口实现文本信息查询、基于地理位置的应用。

Have fun!

2012年12月14日星期五

新浪微博开放平台应用之登录授权

在前文《新浪微博开放平台应用之数据抓取》中,我们学会了如何使用 trends/statuses 接口抓取话题数据,相比 trends/statuses 接口,有些抓取数据的接口需要登录授权后才能调用,比如获取评论的接口 2/comments/show。下面我们就来看如何进行登录授权。

完成登录需要用到 oauth2/authorize 接口,其接收以下参数:
  • client_id: 所申请的app_key
  • response_type: 返回数据类型,值可为code或state,code用于后续获取access_token
  • display: 授权页面的终端类型,default指示游览器
  • redirect_uri: 授权回调地址,需与开放平台中设置的回调地址一致

参数既可以以POST方式传送,也可以以GET方式发送,如下例子:
https://api.weibo.com/oauth2/authorize?redirect_uri=http://liuxiaofang.sinaapp.com/callback?url=/init-comments&ids=3522096338448283&response_type=code&client_id=622387540&display=default

以上url以人为可读的方式显示,向应用服务器发送前还得经过编码(如使用python中的urllib.quote)。

这里所说的回调地址,通过 应用页面 -> 接口管理 -> 授权设置 进行配置。














正确发送URL后,将进入以下登录界面:













成功登录后,将跳转到我们之前设定的 redirect_uri,并返回 code 值:
http://liuxiaofang.sinaapp.com/callback?url=/init-comments&ids=3522096338448283&code=123456

有了code,我们就可以请求获取access_token,获取 access_token 的接口为 oauth2/access_token,其接收以下参数:
  • grant_type: 请求类型,对应与调用 authorize 获得的code,这里值应为 authorization_code
  • code: 以上获得的 code 值
  • client_id: 所申请的 app_key
  • client_secret: 所申请的 app_secret
  • redirect_uri: 回调地址,需与开放平台中设置的回调地址一致
向 oauth2/access_token 传送参数,需用POST方式,如:
https://api.weibo.com/oauth2/access_token
grant_typeauthorization_code
client_id622387540
client_secret = 123456
redirect_urihttp://liuxiaofang.sinaapp.com/callback?
code = 123456

正确发送URL后,将跳转到类似以下授权页面:















完成授权后,将跳转到之前设定的回调地址,并且从 response 中,我们可以获取到 access_token 和 expires_in 超时值。

有了 access_token,我们终于可以使用 2/comments/show 这类需要事先登录授权的接口了。下面通过GET方式获取指定微博id的评论,获取到的 access_token 放置在请求头中:

https://api.weibo.com/2/comments/show?id=3522885349661782
Authorization: OAuth2 123456

之后新浪服务器将返回评论id、评论文本、评论创建时间、评论作者等信息。

欢迎访问我的一个基于sae和新浪开放平台的网站 带上猫咪去旅行

Have fun!