Round up to the next highest power of 2

version1

1
2
3
4
5
6
static unsigned int power2gt(unsigned int size) {
while (1) {
if (i >= size) return i;
i *= 2;
}
}

version2

1
2
3
4
5
6
7
8
9
static unsigned int power2gt(unsigned int size) {
--size;
size |= size >> 1;
size |= size >> 2;
size |= size >> 4;
size |= size >> 8;
size |= size >> 16;
return size + 1;
}

参考资料

  1. the explanation of version2:here
  2. Reidis#issue4776

Atoi&Itoa函数

  • atoi函数实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*************************************************************************
> File Name: Atoi.c
> Author: qinchao
> Mail: 1187620726@qq.com
> Created Date:2018-01-28 Time:04:36:18.
************************************************************************/
// 32bits无符号整数表示范围[0, 2^32-1]
#define UINTEGER32_MAX (4294967295)
// 32bits有符号整数表示范围为[-2^31, 2^31-1]
#define INTEGER32_MAX (2147483647)
#define INTEGER32_MIN (-2147483648)
int Atoi(const char *str) {
unsigned int value = 0;
// 1表示负数,0表示整数
int negative = 0;
//判断str指针非NULL
if (str != NULL) {
//判断是否为负数
if (str[0] == '-') {
negative = 1;
str++;
}
else if (str[0] == '+') {
str++;
}
// str指向的字符串以0结尾
while (str[0] != '\0') {
if (str[0] >= '0' && str[0] <= '9') {
//判断value是否会溢出
if (value > UINTEGER32_MAX / 10) return 0;
value *= 10;
//判断value是否会溢出
if (value > UINTEGER32_MAX - (str[0] - '0')) return 0;
value += (str[0] - '0');
str++;
} else {
//含有非法字符,value的值返回0
value = 0;
break;
}
}
if (str[0] == '\0') {
if (negative) //负数
{
// INT32_MINI = -(INT32_MAX+1)
if (value > (unsigned int)(INTEGER32_MAX + 1)) return 0;
return -value;
} else { //正数
if (value > INTEGER32_MAX) return 0;
return value;
}
}
}
return value;
}

redis4.0_输入/输出缓冲区处理

之前读了一下redis事件处理器的代码点我,今天无所事事,看了下redis对输入缓冲区(querybuf)和输出缓冲区(buf/replylist)的代码,记录一下学习过程。

1. 读缓冲区处理

读取fd数据,然后放入client的输入缓冲区(querybuf)的整个调用栈如下:

1
2
3
4
5
6
7
8
9
10
1211 int processMultibulkBuffer(client *c) {
(gdb) bt
#0 processMultibulkBuffer (c=c@entry=0x7ffff6f15e00) at networking.c:1211
#1 0x000000000043c736 in processInputBuffer (c=0x7ffff6f15e00)
at networking.c:1408
#2 0x00000000004262de in aeProcessEvents (
eventLoop=eventLoop@entry=0x7ffff6e340a0, flags=flags@entry=11) at ae.c:452
#3 0x000000000042670b in aeMain (eventLoop=0x7ffff6e340a0) at ae.c:495
#4 0x00000000004232d6 in main (argc=<optimized out>, argv=0x7fffffffe3e8)
at server.c:3897

redis4.0_发布/订阅

1. channel的订阅与退订

  • UBSCRIBE, UNSUBSCRIBE and PUBLISH implement the Publish/Subscribe messaging paradigm where senders (publishers) are not programmed to send their messages to specific receivers (subscribers). Rather, published messages are characterized into channels, without knowledge of what (if any) subscribers there may be. Subscribers express interest in one or more channels, and only receive messages that are of interest, without knowledge of what (if any) publishers there are.

  • Messages sent by other clients to these channels will be pushed by Redis to all the subscribed clients.

  • A client subscribed to one or more channels should not issue commands, although it can subscribe and unsubscribe to and from other channels. The replies to subscription and unsubscription operations are sent in the form of messages, so that the client can just read a coherent stream of messages where the first element indicates the type of message. The commands that are allowed in the context of a subscribed client are SUBSCRIBE, PSUBSCRIBE, UNSUBSCRIBE, PUNSUBSCRIBE, PING and QUIT.

    • Please note that redis-cli will not accept any commands once in subscribed mode and can only quit the mode with Ctrl-C.
  • channel订阅实现:在客户端结构体的pubsub_channels(为dict)添加key为订阅的channel的entry,在server结构体的pubsub_chanels(dict)添加key为channel的entry,该entry为所有订阅该channel的list

2.Pattern-matching订阅与退订

  • The Redis Pub/Sub implementation supports pattern matching. Clients may subscribe to glob-style patterns in order to receive all the messages sent to channel names matching a given pattern.

  • pattern订阅实现:在客户端结构体的pubsub_patterns(为list)添加node,该node的value为订阅的pattern(robj),在server结构体的pubsub_patterns(为list)添加pubsubPattern Node,该node的client为订阅该pattern的客户端指针,该pattern为订阅pattern的robj.

1
2
3
4
5
//src/server.h
typedef struct pubsubPattern {
client *client;
robj *pattern;
} pubsubPattern;

3.源码分析

  • 订阅channel代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /* Subscribe a client to a channel. Returns 1 if the operation succeeded, or
    * 0 if the client was already subscribed to that channel. */
    int pubsubSubscribeChannel(client *c, robj *channel) {
    dictEntry *de;
    list *clients = NULL;
    int retval = 0;
    /* Add the channel to the client -> channels hash table */
    //将订阅的channel添加到client结构体的pubsub_channels字典
    //key为channel
    if (dictAdd(c->pubsub_channels,channel,NULL) == DICT_OK) {
    retval = 1;
    incrRefCount(channel);
    /* Add the client to the channel -> list of clients hash table */
    //将channel添加到server的pubsub_channels字典
    //首先在dict中查找是否该channel存在,如果存在,将c添加到entry的value链表中
    //如果不存在,在字典中添加entry,该entry的key为robj,value为client的链表
    de = dictFind(server.pubsub_channels,channel);
    if (de == NULL) {
    //den=NULL表示该channel在dict不存在
    clients = listCreate();
    dictAdd(server.pubsub_channels,channel,clients);
    //robj引用+1
    incrRefCount(channel);
    } else {
    //该channel在dict中已经存在
    clients = dictGetVal(de);
    }
    listAddNodeTail(clients,c);
    }
    /* Notify the client */
    addReply(c,shared.mbulkhdr[3]);
    addReply(c,shared.subscribebulk);
    addReplyBulk(c,channel);
    addReplyLongLong(c,clientSubscriptionsCount(c));
    return retval;
    }
  • 订阅pattern代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* Subscribe a client to a pattern. Returns 1 if the operation succeeded, or 0 if the client was already subscribed to that pattern. */
//订阅一个pattern
int pubsubSubscribePattern(client *c, robj *pattern) {
int retval = 0;
//首先查找链表中是否存在该pattern
if (listSearchKey(c->pubsub_patterns,pattern) == NULL) {
retval = 1;
pubsubPattern *pat;
//如果不存在,则添加到client的pubsub_patterns链表结尾
listAddNodeTail(c->pubsub_patterns,pattern);
//增加引用计数
incrRefCount(pattern);
//将该pattern添加到server的pubsub_patterns链表
pat = zmalloc(sizeof(*pat));
pat->pattern = getDecodedObject(pattern);
pat->client = c;
listAddNodeTail(server.pubsub_patterns,pat);
}
/* Notify the client */
addReply(c,shared.mbulkhdr[3]);
addReply(c,shared.psubscribebulk);
addReplyBulk(c,pattern);
addReplyLongLong(c,clientSubscriptionsCount(c));
return retval;
}

4.参考文献

redis.io

redis_reading

redis4.0_Transactions源码剖析

1.Transactions

  • MULTI, EXEC, DISCARD and WATCH are the foundation of transactions in Redis. They allow the execution of a group of commands in a single step, with two important guarantees:

    • All the commands in a transaction are serialized and executed sequentially. It can never happen that a request issued by another client is served in the middle of the execution of a Redis transaction. This guarantees that the commands are executed as a single isolated operation(隔离性).

    • Either all of the commands or none are processed, so a Redis transaction is also atomic(原子性).

  • WATCH命令

    • 在对应的db结构体中用dict保存WATCHed keys,其中dict的entry的key为WATCHed key robj,value为一个链表,链表的每个Node指向一个Client的指针(表示该client WATCHed该key)

    • 在每个client结构体中用链表保存了该客户端WATCHed的key的robj,和该key对应的db指针

redis4.0_event源码剖析

1.Event概述

redis是一个事件驱动程序,服务器处理以下两个事件:

  1. fd事件(IO多路复用)

  2. time事件(时间精度秒级)
    服务器所有的时间事件都放在一个无序链表中,每当时间事件处理器运行时,就遍历整个链表,查找所有已经到达的时间事件,并调用相应的处理函数

2.关键数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/* File event structure */
typedef struct aeFileEvent {
//读或者写
int mask; /* one of AE_(READABLE|WRITABLE) */
//读处理函数指针
aeFileProc *rfileProc;
//写函数指针
aeFileProc *wfileProc;
void *clientData;
} aeFileEvent;
/* Time event structure */
typedef struct aeTimeEvent {
//时间事件ID
long long id; /* time event identifier. */
long when_sec; /* seconds */
long when_ms; /* milliseconds */
aeTimeProc *timeProc;
aeEventFinalizerProc *finalizerProc;
void *clientData;
//无序链表
struct aeTimeEvent *next;
} aeTimeEvent;
/* A fired event */
//fd有event触发
typedef struct aeFiredEvent {
int fd;
int mask;
} aeFiredEvent;
/* State of an event based program */
typedef struct aeEventLoop {
//当前注册的fd的最大值
int maxfd; /* highest file descriptor currently registered */
int setsize; /* max number of file descriptors tracked */
long long timeEventNextId;
time_t lastTime; /* Used to detect system clock skew */
aeFileEvent *events; /* Registered events */
aeFiredEvent *fired; /* Fired events */
//时间事件链表
aeTimeEvent *timeEventHead;
int stop;
void *apidata; /* This is used for polling API specific data */
//select/poll/epoll sleep之前执行的函数指针
aeBeforeSleepProc *beforesleep;
//select/poll/epoll wakeup之后执行的函数指针
aeBeforeSleepProc *aftersleep;
} aeEventLoop;

redis4.0_intset源码剖析

1.intset概述

intset(整数集合)可以用于保存类型为int16_t, int32_t, int64_t的整数值,并且保证intset中不会出现重复元素。

2.intst结构体

  • 表示intset的结构体定义如下:

    1
    2
    3
    4
    5
    6
    7
    8
    typedef struct intset {
    //intset的编码方式:int*_t
    uint32_t encoding;
    //intset中元素的数量
    uint32_t length;
    //用于保存元素的数组(0长度数组的妙用)
    int8_t contents[];
    } intset;
  • intset对应的图示如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    |----------|
    | encoding |
    |----------|
    | length |
    |----------|
    |int*_t v0 |
    |----------|
    |int*_t v1 |
    |----------|
    |int*_t |
    |vlength-1 |
    |----------|