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值。

参考：

问题描述：_int_malloc extremely slow with ordblks free chunks

复现问题的代码：sizetest.cpp

glibc-2.6中针对该问题的patch：serious performance regression in glibc-2.5 malloc

Have fun!

使用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!

自旋锁在用户态下的应用——谈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!

基数估算算法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!