月度归档:2017年10月

pluto实现分析

pluto实现分析(1)
本文档的Copyleft归yfydz所有,使用GPL发布,可以自由拷贝,转载,转载时请保持文档的完整性,严禁用于任何商业用途。
msn: yfydz_no1@hotmail.com
来源:http://yfydz.cublog.cn
1. 前言
pluto是著名的VPN开源项目freeswan及其后续项目中的一个重要组成部分,实现了IKEv1(RFC2409),原始的fresswan只是实现IKE的基本功能,但不包括很多其他扩展功能,都需要打补丁实现,freeswan停止开发后,继续扩展出两个不同的分支,openswan和strongswan,前者综合各种功能的补丁,IKE功能比较全面;后者功能相对少点,但重要特点就是支持了IKEv2(RFC4306),因此两者各有优势。目前国内做IPSec VPN的基本都是基于这实现的,好象没听说一家国内公司敢拍胸脯说自己的VPN产品是全部是自己写的代码,所作的最大改动就是增加硬件加密卡的支持了。目前国内IKEv2使用的可能性应该还不大,因为即使是上面要制定的国内的VPN标准其实还是根据IKEv1来走的,会不会升级到IKEv2还是未知数。
本文主要是解析openswan-2.4.7中的pluto的实现过程,代码基本都是在programs/pluto目录下。
2. IKEv1概述
2.1 概述
IKEv1在RFC2409中定义,用于定义自动建立IPSec SA的协商处理过程,该RFC只是定义数据的交换过程,而具体的数据格式的定义则是在RFC2408中定义的。
IKEv1协商过程分两个阶段,第一个阶段分两种模式,一种是主模式(main mode),是用于正常情况下的协商处理,交换数据回合比较多,速度较慢,这个模式是IKE的具体实现中必须实现的;另一种的野蛮模式(Aggressive Mode),这种模式的数据交换回合比较少,速度较快,但有不安全因素,通常用于已经建立过的IPSec连接中断后的重新建立处理,而且不是在具体实现中必须实现的。第一阶段的处理目的是建立一个ISAKMP SA,为下一阶段的协商建立安全通道。
IKEv1的第二阶段只有一种模式:快速模式(quick mode),通过这个阶段的数据协商,最终建立起IPSec SA。
对于扩展认证EAP(XAUTH),是在第一阶段结束,第二阶段开始前处理的。
在进行协商时,肯定是要用到非对称加密算法或DH交换来协商对称加密密钥的,使用非对称加密算法时可以使用RSA,或者是本质相同的相同的;另外也可以使用共享密钥方式进行对称密钥的协商,协商算法可使用DH。按不同的密钥处理方法,IKEv1的协商过程也有区别。
2.2 第一阶段: (以下各类是独立,HDR*表示数据包是加密的)

1) Authenticated With Signatures
主模式:
Initiator                          Responder
-----------                        -----------
HDR, SA                -->
                    <--             HDR, SA
HDR, KE, Ni            -->
                    <--          HDR, KE, Nr
HDR*, IDii, [ CERT, ] SIG_I     -->
             <--  HDR*, IDir, [ CERT, ] SIG_R
野蛮模式:
Initiator                          Responder
-----------                        -----------
HDR, SA, KE, Ni, IDii  -->
                      <--    HDR, SA, KE, Nr,
                              IDir, [ CERT, ]
                          SIG_RHDR, [ CERT, ] 
SIG_I                  -->
2) Authenticated With Public Key Encryption
主模式:
Initiator                        Responder
-----------                      -----------
HDR, SA               -->
                  <--           HDR, SA
                       HDR, KE, [ HASH(1), ]
                         PubKey_r,
PubKey_r           -->
HDR, KE, PubKey_i,
                    <--        PubKey_i
HDR*, HASH_I            -->
                      <--    HDR*, HASH_R
野蛮模式:
Initiator                        Responder
-----------                      -----------
HDR, SA, [ HASH(1),] KE,
Pubkey_r,
Pubkey_r         -->
                  HDR, SA, KE, PubKey_i,
            <--         PubKey_i, HASH_R
HDR, HASH_I           -->
3) Authenticated With a Revised Mode of Public Key Encryption
主模式:
Initiator                        Responder
-----------                      -----------
HDR, SA             -->
                         <--    HDR, SA
                         HDR, [ HASH(1), ]
                          Pubkey_r,
                            Ke_i,
                           Ke_i,
[<Ke_i]       -->
HDR, PubKey_i,
Ke_r,
                <--          Ke_r,
HDR*, HASH_I          -->
                <--             HDR*, HASH_R
野蛮模式:
Initiator                        Responder
-----------                      -----------
HDR, SA, [ HASH(1),]
Pubkey_r,
Ke_i, Ke_i
[, Ke_i ]      -->
                     HDR, SA, PubKey_i,
                     Ke_r, Ke_r,
                <--                HASH_R
HDR, HASH_I          -->
 
4) Authenticated With a Pre-Shared Key
主模式:
Initiator                        Responder
----------                       -----------
HDR, SA             -->
                <--                HDR, SA
HDR, KE, Ni           -->
                <--              HDR, KE, Nr
HDR*, IDii, HASH_I         -->
                <--         HDR*, IDir, HASH_R
野蛮模式:
            Initiator                        Responder
-----------                      -----------
HDR, SA, KE, Ni, IDii     -->
                <-- HDR, SA, KE, Nr, IDir, HASH_R
HDR, HASH_I          -->
 
2.3 第二阶段
快速模式:
Initiator                        Responder
-----------                      -----------
HDR*, HASH(1), SA, Ni
[, KE ] [, IDci, IDcr ] -->
                 <--    HDR*, HASH(2), SA, Nr
                      [, KE ] [, IDci, IDcr ]
HDR*, HASH(3)          -->
 
如果有多个SA和密钥可使用下面的数据交换方法:
Initiator                        Responder
-----------                      -----------
HDR*, HASH(1), SA0, SA1, Ni,
[, KE ] [, IDci, IDcr ]     -->
                <--  HDR*, HASH(2), SA0, SA1, Nr,
                     [, KE ] [, IDci, IDcr ]
HDR*, HASH(3)         -->
HASH(1) = prf(SKEYID_a, M-ID | SA | Ni [ | KE ] [ | IDci | IDcr )
HASH(2) = prf(SKEYID_a, M-ID | Ni_b | SA | Nr [ | KE ] [ | IDci | IDcr )
HASH(3) = prf(SKEYID_a, 0 | M-ID | Ni_b | Nr_b)
 
2.4 新组模式(New Group Mode)
新组模式不是必须实现的, 是用来定义DH交换的私有组的, 必须在ISAKMP SA建立前使用, 也就是在第一阶段后, 第二阶段前。
Initiator                        Responder
-----------                      -----------
HDR*, HASH(1), SA        -->
                  <--       HDR*, HASH(2), SA
                    HASH(1) = prf(SKEYID_a, M-ID | SA)
                 HASH(2) = prf(SKEYID_a, M-ID | SA)
 

3. 源文件概述
programs/pluto目录下编译后会生成3个执行文件:pluto, whack, _pluto_adns。其中pluto是基本程序,提供IKEv1服务,打开UDP500和4500端口监听网卡数据,打开UNIX域套接口监听whack的输入,并和内核进行PFKEY/netlink通信;whack是控制程序,通过UNIX域套接口和pluto通信;_pluto_adns
进行异步DNS处理。
各个C程序大致功能如下:
ac.c:X509证书相关支持处理
adns.c:异步DNS辅助处理
asn1.c:简单的ASN.1解析器
certs.c:证书处理
connections.c:连接处理
cookie.c:cookie处理
crypto.c:加密
crypt_dh.c:DH算法
crypt_ke.c:密钥交换KE处理
crypt_utils.c:加密相关函数
db_ops.c:数据库操作
defs.c:一些辅助函数集合
demux.c:数据包解析
dnskey.c:从DNS获取公钥的处理
dpd.c:DPD处理
dsa.c:DSA签名
elgamal.c:ElGamal公开密钥加密
fetch.c:动态获取X.509的证书吊销列表CRL
foodgroups.c:策略组控制
gcryptfix.c:进行gcrypt处理
id.c:端点ID处理
ikeping.c:ping IKE包
ikev1_aggr.c:野蛮模式处理
ikev1_quick.c:快速模式处理
ike_alg.c:IKE算法处理
ike_alginit.c:IKE算法初始化
ike_alg_aes.c:AES加密算法
ike_alg_blowfish.c:blowfish加密算法
ike_alg_serpent.c:serpent加密算法
ike_alg_sha2.c:SHA2哈希算法
ike_alg_twofish.c:twofish加密算法
ipsec_doi.c:IKE模式转换处理
kernel.c:内核接口
kernel_netlink.c:和内核的netlink接口
kernel_noklips.c:noklips模式下的内核接口
kernel_pfkey.c:和内核的pfkey接口
keys.c:密钥处理
lex.c:配置文件语法分析器
log.c:日志处理
md2.c:MD2哈希算法
md5.c:MD5哈希算法
nat_traversal.c:NAT穿越支持
ocsp.c:在线证书状态协议支持
oid.c:常见的一些对象的ID定义
pem.c:PEM格式证书处理
pending.c:连接的相关信息处理
pgp.c:PGP证书处理
pkcs.c:PKCS#1和PKCS#7数据结构支持
plutoalg.c:pluto算法处理
plutomain.c:主函数
pluto_constants.c:pluto常数
pluto_crypt.c:pluto加密算法处理
primegen.c:生成素数
rcv_info.c:接收数据
rcv_whack.c:接收whack输入信息
rnd.c:随机数
server.c:IKE服务
sha1.c:SHA1哈希算法
smallprime.c:小素数处理
smartcard.c:smartcard支持
spdb.c:安全策略数据库处理
spdb_print.c:安全策略输出
spdb_struct.c:安全策略结构
state.c:状态处理
stubs.c:某些功能的stub
sysdep_linux.c:和linux相关的相关处理
timer.c:定时器
vendor.c:VPN功能提供者信息
virtual.c:虚拟IP支持
whack.c:whack控制
whackinit.c:whack初始化
whacklib.c:whack相关库函数
x509.c:X509证书支持
x509keys.c:X509密钥
xauth.c:扩展认证处理
...... 待续 ......

CentOS 6.x openvpn

OpenVPN 下载地址: http://openvpn.net

查看系统版本
cat /etc/redhat-release
CentOS release 6.5 (Final)

查看内核和cpu架构
uname -rm
2.6.32-431.el6.x86_64 x86_64

查看ip
ifconfig
eth0 Link encap:Ethernet HWaddr 08:00:27:5E:DF:74
inet addr:xxx.xxx.xxx.xxx Bcast:xxx.xxx.xxx.255 Mask:255.255.255.0
inet6 addr: fe80::a00:27ff:fe5e:df74/64 Scope:Link
UP BROADCAST RUNNING MULTICAST MTU:1500 Metric:1
RX packets:457 errors:0 dropped:0 overruns:0 frame:0
TX packets:55 errors:0 dropped:0 overruns:0 carrier:0
collisions:0 txqueuelen:1000
RX bytes:37261 (36.3 KiB) TX bytes:6438 (6.2 KiB)

lo Link encap:Local Loopback
inet addr:127.0.0.1 Mask:255.0.0.0
inet6 addr: ::1/128 Scope:Host
UP LOOPBACK RUNNING MTU:16436 Metric:1
RX packets:0 errors:0 dropped:0 overruns:0 frame:0
TX packets:0 errors:0 dropped:0 overruns:0 carrier:0
collisions:0 txqueuelen:0
RX bytes:0 (0.0 b) TX bytes:0 (0.0 b)
#使用单网卡

添加epel源
rpm -ivh http://dl.fedoraproject.org/pub/epel/5/i386/epel-release-5-4.noarch.rpm

安装openvpn和easy-rsa
yum -y install openvpn easy-rsa

拷贝文件
cp /usr/share/doc/openvpn-2.3.10/sample/sample-config-files/server.conf /etc/openvpn
cp -r /usr/share/easy-rsa/2.0/* /etc/openvpn/

进入openvpn目录
cd /etc/openvpn/

配置PKI
vi vars

编辑下面内容,自定义。
export KEY_COUNTRY="CN"
export KEY_PROVINCE="guangdong"
export KEY_CITY="guangzhou"
export KEY_ORG="xxx"
export KEY_EMAIL="xxx@qq.com"
export KEY_OU="xxx"

初始化vars
source vars

清理原有证书
./clean-all

生成ca证书
./build-ca
#一路按回车键

生成服务器密钥证书
./build-key-server server
#一路按回车键,两次按y

生成DH验证文件
./build-dh

生成客户端密钥证书
./build-key xxx
#一路按回车键,两次按y

生成ta.key文件
openvpn --genkey --secret /etc/openvpn/keys/ta.key

编辑服务配置文件server.conf
vi /etc/openvpn/server.conf

主要修改以下内容:
port 1194
proto udp
dev tun
ca keys/ca.crt
cert keys/server.crt
key keys/server.key
dh keys/dh2048.pem
server 10.8.0.0 255.255.255.0
push "dhcp-option DNS 8.8.8.8"
push "dhcp-option DNS 8.8.4.4"
log-append /var/log/openvpn/openvpn.log
#我采用的是相对路径

新建日志目录
mkdir -p /var/log/openvpn

启动openvpn服务
service openvpn start

新手一般都会在这一步启动不了,但是重要的是要学会通过查看日志排错。
cat /var/log/openvpn/openvpn.log

添加openvpn到后台启动
chkconfig openvpn on

开启路由转发功能
sed -i '/net.ipv4.ip_forward/s/0/1/' /etc/sysctl.conf
sysctl -p

配置防火墙让openvpn端口通过
iptables -A INPUT -p UDP --dport 1194 -j ACCEPT
iptables -A INPUT -m state --state ESTABLISHED,RELATED -j ACCEPT
iptables -t nat -A POSTROUTING -o eth0 -s 10.8.0.0/24 -j MASQUERADE
service iptables save

客户端文件配置
cp /usr/share/doc/openvpn-2.3.10/sample/sample-config-files/client.conf /etc/openvpn/keys/client.ovpn
vi /etc/openvpn/keys/client.ovpn

主要修改以下内容:
dev tun
proto udp
remote xxx.xxx.xxx.xxx 1194 #ip为服务器网卡的ip
ca ca.crt
cert xxx.crt
key xxx.key
#以上证书路径均为相对路径

将客户端所需的五个文件下载到本地
sz /etc/openvpn/keys/{ca.crt,xxx.crt,xxx.key,ta.key,client.ovpn}

下载windows客户端并安装
https://openvpn.net/index.php/open-source/downloads.html

将之前下载的五个文件拷贝到C:/Program Files/OpenVPN/config目录下,双击桌面openvpn图标就ok了。

添加新用户

以上仅生成了一个 xxx 用户, 仅一用户可用,可以用相同的方法添加其它用户。

1: cd /etc/openvpn/easy-rsa/2.0
2: source vars

PS:如果不执行这步,执行第三步./build-key 会导致如下问题:

Please edit the vars script to reflect your configuration,
then source it with "source ./vars".
Next, to start with a fresh PKI configuration and to delete any
previous certificates and keys, run "./clean-all".
Finally, you can run this tool (pkitool) to build certificates/keys.

3: ./build-key client2
执行完这步后,会在keys目录下生成client2.crt client2.key两个文件。

同第一个用户一样,将此两个文件与ca.crt,ta.key文件一同拷贝到使用者设备上即可使用。

4: 创建对应的 client2.ovpn
可直接拷贝第一个生成的ovpn或从示例中复制, 替换其中的 client2.crt 与 client2.key 即可。

注销一个用户

例如一位同事离职等情况下需要禁用或删除一个用户。使用revoke-full命令来注销其证书。若服务器上无用户证书需要将该同证书文件放到对应的keys下。
第1,2步同添加用户

1: cd /etc/openvpn/easy-rsa/2.0
2: source vars
3: revoke-full client1
注销common name为client1的用户


revoke-full client2

注销common name为client2的用户
revoke-full xxxx

注销common name为xxxx的用户

4: 将生成的crl.pem文件放到相应的配置目录config下,然后在配置文件加入如下参数,重启或重新载入openvpn服务器

crl-verify keys/crl.pem

 

Adf.NumberServer v2.0.0 manual

本文简要介绍Adf.NumberServer在windows平台下的使用。
本服务常用于生成用户标识,订单标识,会话标识等场景。

1.  协议描述

服务完全兼容 memcached 文本协议, 使用支持1.2.0 或以上版本的任意一款客户端均可访问,不区分语言,本服务仅支持 set,incr,decr,get,stats 五个命令,其它命令均不受支持。

Protocol:
https://github.com/memcached/memcached/blob/1.6.0-beta1/doc/protocol.txt

根据协议:

incr 可至int64最大值,超过最大值后将会归零后循环,
decr 可至最小值0,低于0值时会保持0值,不会出现负数。

2.  键约束

本服务支持最长KEY为 250字符, 超过该长度服务将会出现异常。
本服务不支持多字节KEY, 仅支持ASCII字符。

3.  单机模式

在数据不要求安全的情况下,本服务支持单机模式。
单机模式时需要将配置文件中所有以HA:方式开始的配置禁用或删除掉。

4.  高可用模式(High-Availability)

本服务基于 adf.service 组件, 支持master/slave/witness 的高可用方式,为提高可用性,master与slave通信为实时同步而保持数据的绝对一致性。

启用HA需配置:
HA:Path                高可用配置数据存储路径
HA:Node1             默认的master服务
HA:Node2             默认的slave服务
HA:Node3             默认的witness 服务

注意:本服务在高可用环境时, 只有master会对外提供服务,其它两个节点不会对外提供服务,因此,你的客户端需要能自动的判断节点的可用性。

5.  主备切换

本服务允许你直接停掉master主机来进行手动的主备切换,主机停止后slave将自动成为master以提供服务。
当有需要再次启动原master时,原master节点将会以slave成员启动。

注意:你不能手动的频繁来回切换,因为数据复制原因,你必需确定现slave成员的日志文件中出现 replication client: request replicate sync 日志后再进行回切, 否则有可能出现数据丢失。

6.  下载与安装

通过以下连接下载:
http://www.aooshi.org/adf/download/Adf.NumberServer-2.0.0.zip
http://www.aooshi.org/adf/doc/adf.numberserver-2.0.0-manual.pdf

工具描述:
ToolInstallService             用于将应用以服务方式安装至系统
ToolRunConsole               手动运行应用
ToolUninstallService            用于卸载已安装在系统中的应用

7.   配置说明

区分大小写

Port 服务端口,默认为: 6224
Ip 允许配置本机IP或 * , * 表示当前设备的所有网络接口。
DataPath 数据存储路径
Log:FlushInterval 日志刷新间隔, 建议值: 5s
Log:Path 日志存储路径。
HA:Node1 高可用模式的Master节点
HA:Node2 高可用模式的Slave节点
HA:Node3 高可用模式的Witness节点
HA:Keepalive 高可用模式节点检测间隔,默认: 5s
HA:ElectTimeout 高可用模式Master节点选举超时时间,默认:5s
HA:Mails 高可用模式时 节点变化通知邮件收件人

8.   模糊查询协议扩展

在原服务协议基础上,增加模糊查询命令扩展。
get * {prefix} {size}
*               获取模糊匹配,第一个*  表示模糊匹配模式
prefix        表示需要匹配的键前缀
size           表示需要返回的条数

get * * 10
上述命令将获取所有键中的任意 10 条数据

get * * 100
上述命令将获取所有键中的任意 100 条数据

get * ab 10
上述命令将获取所有键以ab开始的的任意10 条数据

get * am 10
上述命令将获取所有键以am开始的的任意10 条数据

匹配:  amaooshi,  amtom
不匹配: name,  toam

9.    使用Adf.MemcachePool 示例

配置添加:

将下列配置中的IP地址更换为自已的

<configSections>
<section name="NumberServer" type="Adf.Config.IpGroupSection,Adf"/>
</configSections>

<NumberServer>
<!-- HA:Node1 -->
<add ip="192.168.199.14" port="6224"/>
<!-- HA:Node1 -->
<add ip="192.168.199.13" port="6224"/>
</NumberServer>

添加类:

public class NumberServerClient : Adf.MemcachePool
{
public static readonly Adf.MemcachePool Instance = new Adf.MemcachePool("NumberServer");
}

使用与示例:

long userId = NumberServerClient.Instance.Increment("userid");
long userId = NumberServerClient.Instance.Increment("id.user.net.cn");
long productId = NumberServerClient.Instance.Increment("/product1/id");
long p2Id = NumberServerClient.Instance.Increment("/product2/id");
long p3Id = NumberServerClient.Instance.Increment("/product3/id");
long orderId = NumberServerClient.Instance.Increment("/order/id");
long bookId = NumberServerClient.Instance.Increment("/book/id");
long bookId = NumberServerClient.Instance.Increment("id.book.net.cn");


 

 

 

memcache start parameters

【黑体字的参数较为常用】

-p<num> 监听的TCP端口(默认:11211)
-U<num> UDP监听端口(默认:11211 0关闭)
-d 以守护进程方式运行
-u<username> 指定用户运行
-m<num>. 最大内存使用,单位MB。默认64MB
-c<num> 最大同时连接数,默认是1024
-v 输出警告和错误消息
-vv 打印客户端的请求和返回信息
-h 帮助信息
-l<ip> 绑定地址(默认任何ip地址都可以访问)
-P<file> 将PID保存在file文件
-i 打印memcached和libevent版权信息
-M 禁止LRU策略,内存耗尽时返回错误
-f<factor> 增长因子,默认1.25
-n<bytes> 初始chunk=key+suffix+value+32结构体,默认48字节
-L 启用大内存页,可以降低内存浪费,改进性能
-l

调整分配slab页的大小,默认1M,最小1k到128M

-t<num>

线程数,默认4。由于memcached采用NIO,所以更多线程没有太多作用

-R

每个event连接最大并发数,默认20

-C

禁用CAS命令(可以禁止版本计数,减少开销)

-b

Set the backlog queue limit (default: 1024)

-B

Binding protocol-one of ascii, binary or auto (default)

-s<file>

UNIX socket

-a<mask>

access mask for UNIX socket, in octal (default: 0700)

5、Memcache指令汇总

指令 描述 例子
get key #返回对应的value get mykey
set key 标识符 有效时间 长度 key不存在添加,存在更新 set mykey 0 60 5
add key标识符 有效时间 长度 #添加key-value值,返回stored/not_stored add mykey 0 60 5
replace key标识符 有效时间 长度 #替换key中的value,key存在成功返回stored,key不存在失败返回not_stored replace mykey 0 60 5
append key标识符 有效时间 长度 #追加key中的value值,成功返回stored,失败返回not_stored append mykey 0 60 5
prepend key标识符 有效时间 长度 #前置追加key中的value值,成功返回stored,失败返回not_stored prepend mykey 0 60 5
incr key num #给key中的value增加num。若key中不是数字,则将使用num替换value值。返回增加后的value Incre mykey 1
decr #同上 同上
delete key [key2…] 删除一个或者多个key-value。成功删除返回deleted,不存在失败则返回not_found delete mykey
flush_all [timeount] #清除所有[timeout时间内的]键值,但不会删除items,所以memcache依旧占用内存 flush_all 20
version #返回版本号 version
verbosity #日志级别 verbosity
quit #关闭连接 quit
stats #返回Memcache通用统计信息 stats
stats slabs #返回Memcache运行期间创建的每个slab的信息 stats slabs
stats items #返回各个slab中item的个数,和最老的item秒数 stats items
stats malloc #显示内存分配数据 stats malloc
stats detail [on|off|dump] #on:打开详细操作记录、off:关闭详细操作记录、dump显示详细操作记录(每一个键的get、set、hit、del的次数) stats detail on

stats detail off

stats detail dump

stats cachedump slab_id limit_num #显示slab_id中前limit_num个key stats cachedump 1 2
stats reset #清空统计数据 stats reset
stats settings #查看配置设置 stats settings
stats sizes #展示了固定chunk大小中的items的数量 Stats sizes

注意:标识符:一个十六进制无符号的整数(以十进制来表示),需和数据一起存储,get的时候一起返回

memcached code analyse

名词

Slab
用于表示存储的最大size数据,仅仅只是用于定义(通俗的讲就是表示可以存储数据大小的范围)。默认情况下,前后两个slab表示存储的size以1.25倍进行增长。例如slab1为96字节,slab2为120字节

Page
分配给Slab的内存空间,默认为1MB。分给Slab后将会根据slab的大小切割成chunk

Chunk
用于缓存记录的内存空间

Slab calss
特定大小的Chunk集合

增长因子

增长因子就是相邻两个chunk之间的增长倍数。 memcache默认是1.25。
2倍 chunk size增长。
 
 

struct item:

#define ITEM_LINKED 1 //该item插入到LRU队列了
#define ITEM_CAS 2 //该item使用CAS
#define ITEM_SLABBED 4 //该item还在slab的空闲队列里面,没有分配出去
#define ITEM_FETCHED 8 //该item插入到LRU队列后,被worker线程访问过

typedef struct _stritem {
    struct _stritem *next;//next指针,用于LRU链表
    struct _stritem *prev;//prev指针,用于LRU链表
    struct _stritem *h_next;//h_next指针,用于哈希表的冲突链
    rel_time_t      time;//最后一次访问时间。绝对时间
    rel_time_t      exptime;//过期失效时间,绝对时间
    int             nbytes;//本item存放的数据的长度   
    unsigned short  refcount;//本item的引用数
    uint8_t         nsuffix;//后缀长度    /* length of flags-and-length string */
    uint8_t         it_flags;//item的属性   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;//键值的长度       /* key length, w/terminating null and padding */
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
        uint64_t cas;
        char end;
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

struct slabclass:

typedef struct {
    unsigned int size;      /* sizes of items */
    unsigned int perslab;   /* how many items per slab */

    void *slots;           /* list of item ptrs */
    unsigned int sl_curr;   /* total free items in list */

    void *end_page_ptr;         /* pointer to next free item at end of page, or 0 */
    unsigned int end_page_free; /* number of items remaining at end of last alloced page */

    unsigned int slabs;     /* how many slabs were allocated for this class */

    void **slab_list;       /* array of slab pointers */
    unsigned int list_size; /* size of prev array */

    unsigned int killing;  /* index+1 of dying slab, or zero if none */
    size_t requested; /* The number of requested bytes */
} slabclass_t;


item_link_q:

将item插入到LRU队列的头部
//将item插入到LRU队列的头部
static void item_link_q(item *it) { /* item is the new head */
    item **head, **tail;
    assert(it->slabs_clsid < LARGEST_ID); assert((it->it_flags & ITEM_SLABBED) == 0);

    head = &heads[it->slabs_clsid];
    tail = &tails[it->slabs_clsid];
    assert(it != *head);
    assert((*head && *tail) || (*head == 0 && *tail == 0));

	//头插法插入该item
    it->prev = 0;
    it->next = *head;
    if (it->next) it->next->prev = it;
    *head = it;//该item作为对应链表的第一个节点

	//如果该item是对应id上的第一个item,那么还会被认为是该id链上的最后一个item
	//因为在head那里使用头插法,所以第一个插入的item,到了后面确实成了最后一个item
    if (*tail == 0) *tail = it;
    sizes[it->slabs_clsid]++;//个数加一
    return;
}

item_unlink_q:

将item从对应的LRU队列中删除
static void item_unlink_q(item *it) {
    item **head, **tail;
    assert(it->slabs_clsid < LARGEST_ID); head = &heads[it->slabs_clsid];
    tail = &tails[it->slabs_clsid];

	
    if (*head == it) {//链表上的第一个节点
        assert(it->prev == 0);
        *head = it->next;
    }
    if (*tail == it) {//链表上的最后一个节点
        assert(it->next == 0);
        *tail = it->prev;
    }
    assert(it->next != it);
    assert(it->prev != it);

	//把item的前驱节点和后驱节点连接起来
    if (it->next) it->next->prev = it->prev;
    if (it->prev) it->prev->next = it->next;
    sizes[it->slabs_clsid]--;//个数减一
    return;
}


do_item_update:

更新item
#define ITEM_UPDATE_INTERVAL 60 //更新频率为60秒

void do_item_update(item *it) {
	//下面的代码可以看到update操作是耗时的。如果这个item频繁被访问,
	//那么会导致过多的update,过多的一系列费时操作。此时更新间隔就应运而生
	//了。如果上一次的访问时间(也可以说是update时间)距离现在(current_time)
	//还在更新间隔内的,就不更新。超出了才更新。
    if (it->time < current_time - ITEM_UPDATE_INTERVAL) { mutex_lock(&cache_lock); if ((it->it_flags & ITEM_LINKED) != 0) {
            item_unlink_q(it);//从LRU队列中删除
            it->time = current_time;//更新访问时间
            item_link_q(it);//插入到LRU队列的头部
        }
        mutex_unlock(&cache_lock);
    }
}

do_slabs_newslab:

分配一个新的 slab
static int do_slabs_newslab(const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    int len = settings.slab_reassign ? settings.item_size_max
        : p->size * p->perslab;
    char *ptr;

    if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||
        (grow_slab_list(id) == 0) ||
        ((ptr = memory_allocate((size_t)len)) == 0)) {

        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }

    memset(ptr, 0, (size_t)len);
    p->end_page_ptr = ptr;
    p->end_page_free = p->perslab;

    p->slab_list[p->slabs++] = ptr;
    mem_malloced += len;
    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);

    return 1;
}

do_slabs_alloc:

从指定的 slabclass, 即 slabclass[id], 分配大小为 size 的内存块供申请者使用.
分配的原则是, 优先从 slots 指向的空闲链表中分配, 空闲链表没有, 才从 slab 中分配一个空闲的 chunk.
static void *do_slabs_alloc(const size_t size, unsigned int id) {
    slabclass_t *p;
    void *ret = NULL;
    item *it = NULL;

    if (id < POWER_SMALLEST || id > power_largest) {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
        return NULL;
    }

    p = &slabclass[id];
    assert(p->sl_curr == 0 || ((item *)p->slots)->slabs_clsid == 0);

 /* 如果不使用 slab 机制, 则直接从操作系统分配 */
#ifdef USE_SYSTEM_MALLOC
    if (mem_limit && mem_malloced + size > mem_limit) {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
        return 0;
    }
    mem_malloced += size;
    ret = malloc(size);
    MEMCACHED_SLABS_ALLOCATE(size, id, 0, ret);
    return ret;
#endif

    /* fail unless we have space at the end of a recently allocated page,
       we have something on our freelist, or we could allocate a new page */
 /* 确保最后一个slab 有空闲的chunk */
    if (! (p->end_page_ptr != 0 || p->sl_curr != 0 ||
           do_slabs_newslab(id) != 0)) {
        /* We don't have more memory available */
        ret = NULL;
    } else if (p->sl_curr != 0) {
  /* 从空闲list分配一个item */
        /* return off our freelist */
        it = (item *)p->slots;
        p->slots = it->next;
        if (it->next) it->next->prev = 0;
        p->sl_curr--;
        ret = (void *)it;
    } else {
  /* 从最后一个slab中分配一个空闲chunk */
        /* if we recently allocated a whole page, return from that */
        assert(p->end_page_ptr != NULL);
        ret = p->end_page_ptr;
        if (--p->end_page_free != 0) {
            p->end_page_ptr = ((caddr_t)p->end_page_ptr) + p->size;
        } else {
            p->end_page_ptr = 0;
        }
    }

    if (ret) {
        p->requested += size;
        MEMCACHED_SLABS_ALLOCATE(size, id, p->size, ret);
    } else {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
    }

    return ret;
}

do_item_alloc:

从 slab 系统分配一个空闲 item
item *do_item_alloc(char *key, const size_t nkey, const int flags, const rel_time_t exptime, const int nbytes) {
    uint8_t nsuffix;
    item *it = NULL;
    char suffix[40];
    size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);
    if (settings.use_cas) {
        ntotal += sizeof(uint64_t);
    }

    unsigned int id = slabs_clsid(ntotal);
    if (id == 0)
        return 0;

    mutex_lock(&cache_lock);
    /* do a quick check if we have any expired items in the tail.. */
    item *search;
    rel_time_t oldest_live = settings.oldest_live;

    search = tails[id];
    if (search != NULL && (refcount_incr(&search->refcount) == 2)) {
  /* 先检查 LRU 队列最后一个 item 是否超时, 超时的话就把这个 item 分配给用户 */
        if ((search->exptime != 0 && search->exptime < current_time) || (search->time <= oldest_live && oldest_live <= current_time)) { // dead by flush STATS_LOCK(); stats.reclaimed++; STATS_UNLOCK(); itemstats[id].reclaimed++; if ((search->it_flags & ITEM_FETCHED) == 0) {
                STATS_LOCK();
                stats.expired_unfetched++;
                STATS_UNLOCK();
                itemstats[id].expired_unfetched++;
            }
            it = search;
            slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal);
   /* 把这个 item 从 LRU 队列和哈希表中移除 */
            do_item_unlink_nolock(it, hash(ITEM_key(it), it->nkey, 0));
            /* Initialize the item block: */
            it->slabs_clsid = 0;
  /* 没有超时的 item, 那就尝试从 slabclass 分配, 运气不好的话, 分配失败,
     那就把 LRU 队列最后一个 item 剔除, 然后分配给用户 */
        } else if ((it = slabs_alloc(ntotal, id)) == NULL) {
            if (settings.evict_to_free == 0) {
                itemstats[id].outofmemory++;
                pthread_mutex_unlock(&cache_lock);
                return NULL;
            }
            itemstats[id].evicted++;
            itemstats[id].evicted_time = current_time - search->time;
            if (search->exptime != 0)
                itemstats[id].evicted_nonzero++;
            if ((search->it_flags & ITEM_FETCHED) == 0) {
                STATS_LOCK();
                stats.evicted_unfetched++;
                STATS_UNLOCK();
                itemstats[id].evicted_unfetched++;
            }
            STATS_LOCK();
            stats.evictions++;
            STATS_UNLOCK();
            it = search;
            slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal);
   /* 把这个 item 从 LRU 队列和哈希表中移除 */
            do_item_unlink_nolock(it, hash(ITEM_key(it), it->nkey, 0));
            /* Initialize the item block: */
            it->slabs_clsid = 0;
        } else {
            refcount_decr(&search->refcount);
        }
 /* LRU 队列是空的, 或者锁住了, 那就只能从 slabclass 分配内存 */
    } else {
        /* If the LRU is empty or locked, attempt to allocate memory */
        it = slabs_alloc(ntotal, id);
        if (search != NULL)
            refcount_decr(&search->refcount);
    }

    if (it == NULL) {
        itemstats[id].outofmemory++;
        /* Last ditch effort. There was a very rare bug which caused
         * refcount leaks. We leave this just in case they ever happen again.
         * We can reasonably assume no item can stay locked for more than
         * three hours, so if we find one in the tail which is that old,
         * free it anyway.
         */
        if (search != NULL &&
            search->refcount != 2 &&
            search->time + TAIL_REPAIR_TIME < current_time) { itemstats[id].tailrepairs++; search->refcount = 1;
            do_item_unlink_nolock(search, hash(ITEM_key(search), search->nkey, 0));
        }
        pthread_mutex_unlock(&cache_lock);
        return NULL;
    }

    assert(it->slabs_clsid == 0);
    assert(it != heads[id]);

 /* 顺便对 item 做一些初始化 */
    /* Item initialization can happen outside of the lock; the item's already
     * been removed from the slab LRU.
     */
    it->refcount = 1;     /* the caller will have a reference */
    pthread_mutex_unlock(&cache_lock);
    it->next = it->prev = it->h_next = 0;
    it->slabs_clsid = id;

    DEBUG_REFCNT(it, '*');
    it->it_flags = settings.use_cas ? ITEM_CAS : 0;
    it->nkey = nkey;
    it->nbytes = nbytes;
    memcpy(ITEM_key(it), key, nkey);
    it->exptime = exptime;
    memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix);
    it->nsuffix = nsuffix;
    return it;
}

do_item_link

形成了一个完成的 item 后, 就要把它放入两个数据结构中, 一是 memcached 的哈希表,
memcached 运行过程中只有一个哈希表, 二是 item 所在的 slabclass 的 LRU 队列.
每个 slabclass 都有一个 LRU 队列
int do_item_link(item *it, const uint32_t hv) {
    MEMCACHED_ITEM_LINK(ITEM_key(it), it->nkey, it->nbytes);
    assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0);
    mutex_lock(&cache_lock);
    it->it_flags |= ITEM_LINKED;
    it->time = current_time;

    STATS_LOCK();
    stats.curr_bytes += ITEM_ntotal(it);
    stats.curr_items += 1;
    stats.total_items += 1;
    STATS_UNLOCK();

    /* Allocate a new CAS ID on link. */
    ITEM_set_cas(it, (settings.use_cas) ? get_cas_id() : 0);
 /* 把 item 放入哈希表 */
    assoc_insert(it, hv);
 /* 把 item 放入 LRU 队列*/
    item_link_q(it);
    refcount_incr(&it->refcount);
    pthread_mutex_unlock(&cache_lock);

    return 1;
}
 

do_item_unlink

do_item_unlink 与 do_item_unlink 做的工作相反, 把 item 从哈希表和 LRU 队列中删除,
而且还释放掉 item 所占的内存 (其实只是把 item 放到空闲链表中).
void do_item_unlink(item *it, const uint32_t hv) {
    MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes);
    mutex_lock(&cache_lock);
    if ((it->it_flags & ITEM_LINKED) != 0) {
        it->it_flags &= ~ITEM_LINKED;
        STATS_LOCK();
        stats.curr_bytes -= ITEM_ntotal(it);
        stats.curr_items -= 1;
        STATS_UNLOCK();
  /* 从哈希表中删除 item */
        assoc_delete(ITEM_key(it), it->nkey, hv);
  /* 从 LRU 队列中删除 item */
        item_unlink_q(it);
  /* 释放 item 所占的内存 */
        do_item_remove(it);
    }
    pthread_mutex_unlock(&cache_lock);
}
 

item_get

根据 key 找对应的 item
/** wrapper around assoc_find which does the lazy expiration logic */
item *do_item_get(const char *key, const size_t nkey, const uint32_t hv) {
    mutex_lock(&cache_lock);
 /* 从哈希表中找 item */
    item *it = assoc_find(key, nkey, hv);
    if (it != NULL) {
        refcount_incr(&it->refcount);
        /* Optimization for slab reassignment. prevents popular items from
         * jamming in busy wait. Can only do this here to satisfy lock order
         * of item_lock, cache_lock, slabs_lock. */
        if (slab_rebalance_signal &&
            ((void *)it >= slab_rebal.slab_start && (void *)it < slab_rebal.slab_end)) { do_item_unlink_nolock(it, hv); do_item_remove(it); it = NULL; } } pthread_mutex_unlock(&cache_lock); int was_found = 0; if (settings.verbose > 2) {
        if (it == NULL) {
            fprintf(stderr, "> NOT FOUND %s", key);
        } else {
            fprintf(stderr, "> FOUND KEY %s", ITEM_key(it));
            was_found++;
        }
    }

 /* 找到了, 然后检查是否超时 */
    if (it != NULL) {
        if (settings.oldest_live != 0 && settings.oldest_live <= current_time && it->time <= settings.oldest_live) { do_item_unlink(it, hv); do_item_remove(it); it = NULL; if (was_found) { fprintf(stderr, " -nuked by flush"); } } else if (it->exptime != 0 && it->exptime <= current_time) { do_item_unlink(it, hv); do_item_remove(it); it = NULL; if (was_found) { fprintf(stderr, " -nuked by expire"); } } else { it->it_flags |= ITEM_FETCHED;
            DEBUG_REFCNT(it, '+');
        }
    }

    if (settings.verbose > 2)
        fprintf(stderr, "\n");

    return it;
}

slabs_clsid:

根据大小判定slab class
unsigned int slabs_clsid(const size_t size) {//返回slabclass索引下标值
    int res = POWER_SMALLEST;//res的初始值为1

	//返回0表示查找失败,因为slabclass数组中,第一个元素是没有使用的
    if (size == 0)
        return 0;
	
	//因为slabclass数组中各个元素能分配的item大小是升序的
	//所以从小到大直接判断即可在数组找到最小但又能满足的元素
    while (size > slabclass[res].size)
        if (res++ == power_largest)     /* won't fit in the biggest slab */
            return 0;
    return res;
}

 

 
Links:
http://blog.csdn.net/luotuo44/article/details/42963793