Frames

Hacking strings in Redis.

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1/* SDSLib 2.0 -- A C dynamic strings library
2 *
3 * Copyright (c) 2006-2015, Salvatore Sanfilippo <antirez at gmail dot com>
4 * Copyright (c) 2015, Oran Agra
5 * Copyright (c) 2015, Redis Labs, Inc
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * * Redistributions of source code must retain the above copyright notice,
12 * this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * * Neither the name of Redis nor the names of its contributors may be used
17 * to endorse or promote products derived from this software without
18 * specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
24 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 * POSSIBILITY OF SUCH DAMAGE.
31 */
32
33#ifndef __SDS_H
34#define __SDS_H
35
36#define SDS_MAX_PREALLOC (1024*1024)
37const char *SDS_NOINIT;
38
39#include <sys/types.h>
40#include <stdarg.h>
41#include <stdint.h>
42
43typedef char *sds;
44
45/* Note: sdshdr5 is never used, we just access the flags byte directly.
46 * However is here to document the layout of type 5 SDS strings. */
47struct __attribute__ ((__packed__)) sdshdr5 {
48 unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
49 char buf[];
50};
51struct __attribute__ ((__packed__)) sdshdr8 {
52 uint8_t len; /* used */
53 uint8_t alloc; /* excluding the header and null terminator */
54 unsigned char flags; /* 3 lsb of type, 5 unused bits */
55 char buf[];
56};
57struct __attribute__ ((__packed__)) sdshdr16 {
58 uint16_t len; /* used */
59 uint16_t alloc; /* excluding the header and null terminator */
60 unsigned char flags; /* 3 lsb of type, 5 unused bits */
61 char buf[];
62};
63struct __attribute__ ((__packed__)) sdshdr32 {
64 uint32_t len; /* used */
65 uint32_t alloc; /* excluding the header and null terminator */
66 unsigned char flags; /* 3 lsb of type, 5 unused bits */
67 char buf[];
68};
69struct __attribute__ ((__packed__)) sdshdr64 {
70 uint64_t len; /* used */
71 uint64_t alloc; /* excluding the header and null terminator */
72 unsigned char flags; /* 3 lsb of type, 5 unused bits */
73 char buf[];
74};
75
76#define SDS_TYPE_5 0
77#define SDS_TYPE_8 1
78#define SDS_TYPE_16 2
79#define SDS_TYPE_32 3
80#define SDS_TYPE_64 4
81#define SDS_TYPE_MASK 7
82#define SDS_TYPE_BITS 3
83#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
84#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
85#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
86
87static inline size_t sdslen(const sds s) {
88 unsigned char flags = s[-1];
89 switch(flags&SDS_TYPE_MASK) {
90 case SDS_TYPE_5:
91 return SDS_TYPE_5_LEN(flags);
92 case SDS_TYPE_8:
93 return SDS_HDR(8,s)->len;
94 case SDS_TYPE_16:
95 return SDS_HDR(16,s)->len;
96 case SDS_TYPE_32:
97 return SDS_HDR(32,s)->len;
98 case SDS_TYPE_64:
99 return SDS_HDR(64,s)->len;
100 }
101 return 0;
102}
103
104static inline size_t sdsavail(const sds s) {
105 unsigned char flags = s[-1];
106 switch(flags&SDS_TYPE_MASK) {
107 case SDS_TYPE_5: {
108 return 0;
109 }
110 case SDS_TYPE_8: {
111 SDS_HDR_VAR(8,s);
112 return sh->alloc - sh->len;
113 }
114 case SDS_TYPE_16: {
115 SDS_HDR_VAR(16,s);
116 return sh->alloc - sh->len;
117 }
118 case SDS_TYPE_32: {
119 SDS_HDR_VAR(32,s);
120 return sh->alloc - sh->len;
121 }
122 case SDS_TYPE_64: {
123 SDS_HDR_VAR(64,s);
124 return sh->alloc - sh->len;
125 }
126 }
127 return 0;
128}
129
130static inline void sdssetlen(sds s, size_t newlen) {
131 unsigned char flags = s[-1];
132 switch(flags&SDS_TYPE_MASK) {
133 case SDS_TYPE_5:
134 {
135 unsigned char *fp = ((unsigned char*)s)-1;
136 *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
137 }
138 break;
139 case SDS_TYPE_8:
140 SDS_HDR(8,s)->len = newlen;
141 break;
142 case SDS_TYPE_16:
143 SDS_HDR(16,s)->len = newlen;
144 break;
145 case SDS_TYPE_32:
146 SDS_HDR(32,s)->len = newlen;
147 break;
148 case SDS_TYPE_64:
149 SDS_HDR(64,s)->len = newlen;
150 break;
151 }
152}
153
154static inline void sdsinclen(sds s, size_t inc) {
155 unsigned char flags = s[-1];
156 switch(flags&SDS_TYPE_MASK) {
157 case SDS_TYPE_5:
158 {
159 unsigned char *fp = ((unsigned char*)s)-1;
160 unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
161 *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
162 }
163 break;
164 case SDS_TYPE_8:
165 SDS_HDR(8,s)->len += inc;
166 break;
167 case SDS_TYPE_16:
168 SDS_HDR(16,s)->len += inc;
169 break;
170 case SDS_TYPE_32:
171 SDS_HDR(32,s)->len += inc;
172 break;
173 case SDS_TYPE_64:
174 SDS_HDR(64,s)->len += inc;
175 break;
176 }
177}
178
179/* sdsalloc() = sdsavail() + sdslen() */
180static inline size_t sdsalloc(const sds s) {
181 unsigned char flags = s[-1];
182 switch(flags&SDS_TYPE_MASK) {
183 case SDS_TYPE_5:
184 return SDS_TYPE_5_LEN(flags);
185 case SDS_TYPE_8:
186 return SDS_HDR(8,s)->alloc;
187 case SDS_TYPE_16:
188 return SDS_HDR(16,s)->alloc;
189 case SDS_TYPE_32:
190 return SDS_HDR(32,s)->alloc;
191 case SDS_TYPE_64:
192 return SDS_HDR(64,s)->alloc;
193 }
194 return 0;
195}
196
197static inline void sdssetalloc(sds s, size_t newlen) {
198 unsigned char flags = s[-1];
199 switch(flags&SDS_TYPE_MASK) {
200 case SDS_TYPE_5:
201 /* Nothing to do, this type has no total allocation info. */
202 break;
203 case SDS_TYPE_8:
204 SDS_HDR(8,s)->alloc = newlen;
205 break;
206 case SDS_TYPE_16:
207 SDS_HDR(16,s)->alloc = newlen;
208 break;
209 case SDS_TYPE_32:
210 SDS_HDR(32,s)->alloc = newlen;
211 break;
212 case SDS_TYPE_64:
213 SDS_HDR(64,s)->alloc = newlen;
214 break;
215 }
216}
217
218sds sdsnewlen(const void *init, size_t initlen);
219sds sdsnew(const char *init);
220sds sdsempty(void);
221sds sdsdup(const sds s);
222void sdsfree(sds s);
223sds sdsgrowzero(sds s, size_t len);
224sds sdscatlen(sds s, const void *t, size_t len);
225sds sdscat(sds s, const char *t);
226sds sdscatsds(sds s, const sds t);
227sds sdscpylen(sds s, const char *t, size_t len);
228sds sdscpy(sds s, const char *t);
229
230sds sdscatvprintf(sds s, const char *fmt, va_list ap);
231#ifdef __GNUC__
232sds sdscatprintf(sds s, const char *fmt, ...)
233 __attribute__((format(printf, 2, 3)));
234#else
235sds sdscatprintf(sds s, const char *fmt, ...);
236#endif
237
238sds sdscatfmt(sds s, char const *fmt, ...);
239sds sdstrim(sds s, const char *cset);
240void sdsrange(sds s, ssize_t start, ssize_t end);
241void sdsupdatelen(sds s);
242void sdsclear(sds s);
243int sdscmp(const sds s1, const sds s2);
244sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
245void sdsfreesplitres(sds *tokens, int count);
246void sdstolower(sds s);
247void sdstoupper(sds s);
248sds sdsfromlonglong(long long value);
249sds sdscatrepr(sds s, const char *p, size_t len);
250sds *sdssplitargs(const char *line, int *argc);
251sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
252sds sdsjoin(char **argv, int argc, char *sep);
253sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);
254
255/* Low level functions exposed to the user API */
256sds sdsMakeRoomFor(sds s, size_t addlen);
257void sdsIncrLen(sds s, ssize_t incr);
258sds sdsRemoveFreeSpace(sds s);
259size_t sdsAllocSize(sds s);
260void *sdsAllocPtr(sds s);
261
262/* Export the allocator used by SDS to the program using SDS.
263 * Sometimes the program SDS is linked to, may use a different set of
264 * allocators, but may want to allocate or free things that SDS will
265 * respectively free or allocate. */
266void *sds_malloc(size_t size);
267void *sds_realloc(void *ptr, size_t size);
268void sds_free(void *ptr);
269
270#ifdef REDIS_TEST
271int sdsTest(int argc, char *argv[]);
272#endif
273
274#endif
275

If you are hacking Redis source code or generally curious about how strings are implemented inside Redis, this story is for you.


Redis string code is implemented in sds.c. Lets look at the structure of strings in sds.h