1/*
2 * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * * Neither the name of Redis nor the names of its contributors may be used
14 * to endorse or promote products derived from this software without
15 * specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#include "fmacros.h"
31#include <stdlib.h>
32#include <stdio.h>
33#include <string.h>
34#include <ctype.h>
35#include <limits.h>
36#include <math.h>
37#include <unistd.h>
38#include <sys/time.h>
39#include <float.h>
40#include <stdint.h>
41#include <errno.h>
42#include <time.h>
43#include <sys/stat.h>
44#include <dirent.h>
45#include <fcntl.h>
46#include <libgen.h>
47
48#include "util.h"
49#include "sha256.h"
50#include "config.h"
51
52/* Glob-style pattern matching. */
53int stringmatchlen(const char *pattern, int patternLen,
54 const char *string, int stringLen, int nocase)
55{
56 while(patternLen && stringLen) {
57 switch(pattern[0]) {
58 case '*':
59 while (patternLen && pattern[1] == '*') {
60 pattern++;
61 patternLen--;
62 }
63 if (patternLen == 1)
64 return 1; /* match */
65 while(stringLen) {
66 if (stringmatchlen(pattern+1, patternLen-1,
67 string, stringLen, nocase))
68 return 1; /* match */
69 string++;
70 stringLen--;
71 }
72 return 0; /* no match */
73 break;
74 case '?':
75 string++;
76 stringLen--;
77 break;
78 case '[':
79 {
80 int not, match;
81
82 pattern++;
83 patternLen--;
84 not = pattern[0] == '^';
85 if (not) {
86 pattern++;
87 patternLen--;
88 }
89 match = 0;
90 while(1) {
91 if (pattern[0] == '\\' && patternLen >= 2) {
92 pattern++;
93 patternLen--;
94 if (pattern[0] == string[0])
95 match = 1;
96 } else if (pattern[0] == ']') {
97 break;
98 } else if (patternLen == 0) {
99 pattern--;
100 patternLen++;
101 break;
102 } else if (patternLen >= 3 && pattern[1] == '-') {
103 int start = pattern[0];
104 int end = pattern[2];
105 int c = string[0];
106 if (start > end) {
107 int t = start;
108 start = end;
109 end = t;
110 }
111 if (nocase) {
112 start = tolower(start);
113 end = tolower(end);
114 c = tolower(c);
115 }
116 pattern += 2;
117 patternLen -= 2;
118 if (c >= start && c <= end)
119 match = 1;
120 } else {
121 if (!nocase) {
122 if (pattern[0] == string[0])
123 match = 1;
124 } else {
125 if (tolower((int)pattern[0]) == tolower((int)string[0]))
126 match = 1;
127 }
128 }
129 pattern++;
130 patternLen--;
131 }
132 if (not)
133 match = !match;
134 if (!match)
135 return 0; /* no match */
136 string++;
137 stringLen--;
138 break;
139 }
140 case '\\':
141 if (patternLen >= 2) {
142 pattern++;
143 patternLen--;
144 }
145 /* fall through */
146 default:
147 if (!nocase) {
148 if (pattern[0] != string[0])
149 return 0; /* no match */
150 } else {
151 if (tolower((int)pattern[0]) != tolower((int)string[0]))
152 return 0; /* no match */
153 }
154 string++;
155 stringLen--;
156 break;
157 }
158 pattern++;
159 patternLen--;
160 if (stringLen == 0) {
161 while(*pattern == '*') {
162 pattern++;
163 patternLen--;
164 }
165 break;
166 }
167 }
168 if (patternLen == 0 && stringLen == 0)
169 return 1;
170 return 0;
171}
172
173int stringmatch(const char *pattern, const char *string, int nocase) {
174 return stringmatchlen(pattern,strlen(pattern),string,strlen(string),nocase);
175}
176
177/* Fuzz stringmatchlen() trying to crash it with bad input. */
178int stringmatchlen_fuzz_test(void) {
179 char str[32];
180 char pat[32];
181 int cycles = 10000000;
182 int total_matches = 0;
183 while(cycles--) {
184 int strlen = rand() % sizeof(str);
185 int patlen = rand() % sizeof(pat);
186 for (int j = 0; j < strlen; j++) str[j] = rand() % 128;
187 for (int j = 0; j < patlen; j++) pat[j] = rand() % 128;
188 total_matches += stringmatchlen(pat, patlen, str, strlen, 0);
189 }
190 return total_matches;
191}
192
193
194/* Convert a string representing an amount of memory into the number of
195 * bytes, so for instance memtoull("1Gb") will return 1073741824 that is
196 * (1024*1024*1024).
197 *
198 * On parsing error, if *err is not NULL, it's set to 1, otherwise it's
199 * set to 0. On error the function return value is 0, regardless of the
200 * fact 'err' is NULL or not. */
201unsigned long long memtoull(const char *p, int *err) {
202 const char *u;
203 char buf[128];
204 long mul; /* unit multiplier */
205 unsigned long long val;
206 unsigned int digits;
207
208 if (err) *err = 0;
209
210 /* Search the first non digit character. */
211 u = p;
212 if (*u == '-') {
213 if (err) *err = 1;
214 return 0;
215 }
216 while(*u && isdigit(*u)) u++;
217 if (*u == '\0' || !strcasecmp(u,"b")) {
218 mul = 1;
219 } else if (!strcasecmp(u,"k")) {
220 mul = 1000;
221 } else if (!strcasecmp(u,"kb")) {
222 mul = 1024;
223 } else if (!strcasecmp(u,"m")) {
224 mul = 1000*1000;
225 } else if (!strcasecmp(u,"mb")) {
226 mul = 1024*1024;
227 } else if (!strcasecmp(u,"g")) {
228 mul = 1000L*1000*1000;
229 } else if (!strcasecmp(u,"gb")) {
230 mul = 1024L*1024*1024;
231 } else {
232 if (err) *err = 1;
233 return 0;
234 }
235
236 /* Copy the digits into a buffer, we'll use strtoll() to convert
237 * the digit (without the unit) into a number. */
238 digits = u-p;
239 if (digits >= sizeof(buf)) {
240 if (err) *err = 1;
241 return 0;
242 }
243 memcpy(buf,p,digits);
244 buf[digits] = '\0';
245
246 char *endptr;
247 errno = 0;
248 val = strtoull(buf,&endptr,10);
249 if ((val == 0 && errno == EINVAL) || *endptr != '\0') {
250 if (err) *err = 1;
251 return 0;
252 }
253 return val*mul;
254}
255
256/* Search a memory buffer for any set of bytes, like strpbrk().
257 * Returns pointer to first found char or NULL.
258 */
259const char *mempbrk(const char *s, size_t len, const char *chars, size_t charslen) {
260 for (size_t j = 0; j < len; j++) {
261 for (size_t n = 0; n < charslen; n++)
262 if (s[j] == chars[n]) return &s[j];
263 }
264
265 return NULL;
266}
267
268/* Modify the buffer replacing all occurrences of chars from the 'from'
269 * set with the corresponding char in the 'to' set. Always returns s.
270 */
271char *memmapchars(char *s, size_t len, const char *from, const char *to, size_t setlen) {
272 for (size_t j = 0; j < len; j++) {
273 for (size_t i = 0; i < setlen; i++) {
274 if (s[j] == from[i]) {
275 s[j] = to[i];
276 break;
277 }
278 }
279 }
280 return s;
281}
282
283/* Return the number of digits of 'v' when converted to string in radix 10.
284 * See ll2string() for more information. */
285uint32_t digits10(uint64_t v) {
286 if (v < 10) return 1;
287 if (v < 100) return 2;
288 if (v < 1000) return 3;
289 if (v < 1000000000000UL) {
290 if (v < 100000000UL) {
291 if (v < 1000000) {
292 if (v < 10000) return 4;
293 return 5 + (v >= 100000);
294 }
295 return 7 + (v >= 10000000UL);
296 }
297 if (v < 10000000000UL) {
298 return 9 + (v >= 1000000000UL);
299 }
300 return 11 + (v >= 100000000000UL);
301 }
302 return 12 + digits10(v / 1000000000000UL);
303}
304
305/* Like digits10() but for signed values. */
306uint32_t sdigits10(int64_t v) {
307 if (v < 0) {
308 /* Abs value of LLONG_MIN requires special handling. */
309 uint64_t uv = (v != LLONG_MIN) ?
310 (uint64_t)-v : ((uint64_t) LLONG_MAX)+1;
311 return digits10(uv)+1; /* +1 for the minus. */
312 } else {
313 return digits10(v);
314 }
315}
316
317/* Convert a long long into a string. Returns the number of
318 * characters needed to represent the number.
319 * If the buffer is not big enough to store the string, 0 is returned. */
320int ll2string(char *dst, size_t dstlen, long long svalue) {
321 unsigned long long value;
322 int negative = 0;
323
324 /* The ull2string function with 64bit unsigned integers for simplicity, so
325 * we convert the number here and remember if it is negative. */
326 if (svalue < 0) {
327 if (svalue != LLONG_MIN) {
328 value = -svalue;
329 } else {
330 value = ((unsigned long long) LLONG_MAX)+1;
331 }
332 if (dstlen < 2)
333 return 0;
334 negative = 1;
335 dst[0] = '-';
336 dst++;
337 dstlen--;
338 } else {
339 value = svalue;
340 }
341
342 /* Converts the unsigned long long value to string*/
343 int length = ull2string(dst, dstlen, value);
344 if (length == 0) return 0;
345 return length + negative;
346}
347
348/* Convert a unsigned long long into a string. Returns the number of
349 * characters needed to represent the number.
350 * If the buffer is not big enough to store the string, 0 is returned.
351 *
352 * Based on the following article (that apparently does not provide a
353 * novel approach but only publicizes an already used technique):
354 *
355 * https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920 */
356int ull2string(char *dst, size_t dstlen, unsigned long long value) {
357 static const char digits[201] =
358 "0001020304050607080910111213141516171819"
359 "2021222324252627282930313233343536373839"
360 "4041424344454647484950515253545556575859"
361 "6061626364656667686970717273747576777879"
362 "8081828384858687888990919293949596979899";
363
364 /* Check length. */
365 uint32_t length = digits10(value);
366 if (length >= dstlen) return 0;
367
368 /* Null term. */
369 uint32_t next = length - 1;
370 dst[next + 1] = '\0';
371 while (value >= 100) {
372 int const i = (value % 100) * 2;
373 value /= 100;
374 dst[next] = digits[i + 1];
375 dst[next - 1] = digits[i];
376 next -= 2;
377 }
378
379 /* Handle last 1-2 digits. */
380 if (value < 10) {
381 dst[next] = '0' + (uint32_t) value;
382 } else {
383 int i = (uint32_t) value * 2;
384 dst[next] = digits[i + 1];
385 dst[next - 1] = digits[i];
386 }
387
388 return length;
389}
390
391/* Convert a string into a long long. Returns 1 if the string could be parsed
392 * into a (non-overflowing) long long, 0 otherwise. The value will be set to
393 * the parsed value when appropriate.
394 *
395 * Note that this function demands that the string strictly represents
396 * a long long: no spaces or other characters before or after the string
397 * representing the number are accepted, nor zeroes at the start if not
398 * for the string "0" representing the zero number.
399 *
400 * Because of its strictness, it is safe to use this function to check if
401 * you can convert a string into a long long, and obtain back the string
402 * from the number without any loss in the string representation. */
403int string2ll(const char *s, size_t slen, long long *value) {
404 const char *p = s;
405 size_t plen = 0;
406 int negative = 0;
407 unsigned long long v;
408
409 /* A string of zero length or excessive length is not a valid number. */
410 if (plen == slen || slen >= LONG_STR_SIZE)
411 return 0;
412
413 /* Special case: first and only digit is 0. */
414 if (slen == 1 && p[0] == '0') {
415 if (value != NULL) *value = 0;
416 return 1;
417 }
418
419 /* Handle negative numbers: just set a flag and continue like if it
420 * was a positive number. Later convert into negative. */
421 if (p[0] == '-') {
422 negative = 1;
423 p++; plen++;
424
425 /* Abort on only a negative sign. */
426 if (plen == slen)
427 return 0;
428 }
429
430 /* First digit should be 1-9, otherwise the string should just be 0. */
431 if (p[0] >= '1' && p[0] <= '9') {
432 v = p[0]-'0';
433 p++; plen++;
434 } else {
435 return 0;
436 }
437
438 /* Parse all the other digits, checking for overflow at every step. */
439 while (plen < slen && p[0] >= '0' && p[0] <= '9') {
440 if (v > (ULLONG_MAX / 10)) /* Overflow. */
441 return 0;
442 v *= 10;
443
444 if (v > (ULLONG_MAX - (p[0]-'0'))) /* Overflow. */
445 return 0;
446 v += p[0]-'0';
447
448 p++; plen++;
449 }
450
451 /* Return if not all bytes were used. */
452 if (plen < slen)
453 return 0;
454
455 /* Convert to negative if needed, and do the final overflow check when
456 * converting from unsigned long long to long long. */
457 if (negative) {
458 if (v > ((unsigned long long)(-(LLONG_MIN+1))+1)) /* Overflow. */
459 return 0;
460 if (value != NULL) *value = -v;
461 } else {
462 if (v > LLONG_MAX) /* Overflow. */
463 return 0;
464 if (value != NULL) *value = v;
465 }
466 return 1;
467}
468
469/* Helper function to convert a string to an unsigned long long value.
470 * The function attempts to use the faster string2ll() function inside
471 * Redis: if it fails, strtoull() is used instead. The function returns
472 * 1 if the conversion happened successfully or 0 if the number is
473 * invalid or out of range. */
474int string2ull(const char *s, unsigned long long *value) {
475 long long ll;
476 if (string2ll(s,strlen(s),&ll)) {
477 if (ll < 0) return 0; /* Negative values are out of range. */
478 *value = ll;
479 return 1;
480 }
481 errno = 0;
482 char *endptr = NULL;
483 *value = strtoull(s,&endptr,10);
484 if (errno == EINVAL || errno == ERANGE || !(*s != '\0' && *endptr == '\0'))
485 return 0; /* strtoull() failed. */
486 return 1; /* Conversion done! */
487}
488
489/* Convert a string into a long. Returns 1 if the string could be parsed into a
490 * (non-overflowing) long, 0 otherwise. The value will be set to the parsed
491 * value when appropriate. */
492int string2l(const char *s, size_t slen, long *lval) {
493 long long llval;
494
495 if (!string2ll(s,slen,&llval))
496 return 0;
497
498 if (llval < LONG_MIN || llval > LONG_MAX)
499 return 0;
500
501 *lval = (long)llval;
502 return 1;
503}
504
505/* Convert a string into a double. Returns 1 if the string could be parsed
506 * into a (non-overflowing) double, 0 otherwise. The value will be set to
507 * the parsed value when appropriate.
508 *
509 * Note that this function demands that the string strictly represents
510 * a double: no spaces or other characters before or after the string
511 * representing the number are accepted. */
512int string2ld(const char *s, size_t slen, long double *dp) {
513 char buf[MAX_LONG_DOUBLE_CHARS];
514 long double value;
515 char *eptr;
516
517 if (slen == 0 || slen >= sizeof(buf)) return 0;
518 memcpy(buf,s,slen);
519 buf[slen] = '\0';
520
521 errno = 0;
522 value = strtold(buf, &eptr);
523 if (isspace(buf[0]) || eptr[0] != '\0' ||
524 (size_t)(eptr-buf) != slen ||
525 (errno == ERANGE &&
526 (value == HUGE_VAL || value == -HUGE_VAL || fpclassify(value) == FP_ZERO)) ||
527 errno == EINVAL ||
528 isnan(value))
529 return 0;
530
531 if (dp) *dp = value;
532 return 1;
533}
534
535/* Convert a string into a double. Returns 1 if the string could be parsed
536 * into a (non-overflowing) double, 0 otherwise. The value will be set to
537 * the parsed value when appropriate.
538 *
539 * Note that this function demands that the string strictly represents
540 * a double: no spaces or other characters before or after the string
541 * representing the number are accepted. */
542int string2d(const char *s, size_t slen, double *dp) {
543 errno = 0;
544 char *eptr;
545 *dp = strtod(s, &eptr);
546 if (slen == 0 ||
547 isspace(((const char*)s)[0]) ||
548 (size_t)(eptr-(char*)s) != slen ||
549 (errno == ERANGE &&
550 (*dp == HUGE_VAL || *dp == -HUGE_VAL || fpclassify(*dp) == FP_ZERO)) ||
551 isnan(*dp))
552 return 0;
553 return 1;
554}
555
556/* Returns 1 if the double value can safely be represented in long long without
557 * precision loss, in which case the corresponding long long is stored in the out variable. */
558int double2ll(double d, long long *out) {
559#if (DBL_MANT_DIG >= 52) && (DBL_MANT_DIG <= 63) && (LLONG_MAX == 0x7fffffffffffffffLL)
560 /* Check if the float is in a safe range to be casted into a
561 * long long. We are assuming that long long is 64 bit here.
562 * Also we are assuming that there are no implementations around where
563 * double has precision < 52 bit.
564 *
565 * Under this assumptions we test if a double is inside a range
566 * where casting to long long is safe. Then using two castings we
567 * make sure the decimal part is zero. If all this is true we can use
568 * integer without precision loss.
569 *
570 * Note that numbers above 2^52 and below 2^63 use all the fraction bits as real part,
571 * and the exponent bits are positive, which means the "decimal" part must be 0.
572 * i.e. all double values in that range are representable as a long without precision loss,
573 * but not all long values in that range can be represented as a double.
574 * we only care about the first part here. */
575 if (d < (double)(-LLONG_MAX/2) || d > (double)(LLONG_MAX/2))
576 return 0;
577 long long ll = d;
578 if (ll == d) {
579 *out = ll;
580 return 1;
581 }
582#endif
583 return 0;
584}
585
586/* Convert a double to a string representation. Returns the number of bytes
587 * required. The representation should always be parsable by strtod(3).
588 * This function does not support human-friendly formatting like ld2string
589 * does. It is intended mainly to be used inside t_zset.c when writing scores
590 * into a listpack representing a sorted set. */
591int d2string(char *buf, size_t len, double value) {
592 if (isnan(value)) {
593 len = snprintf(buf,len,"nan");
594 } else if (isinf(value)) {
595 if (value < 0)
596 len = snprintf(buf,len,"-inf");
597 else
598 len = snprintf(buf,len,"inf");
599 } else if (value == 0) {
600 /* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */
601 if (1.0/value < 0)
602 len = snprintf(buf,len,"-0");
603 else
604 len = snprintf(buf,len,"0");
605 } else {
606 long long lvalue;
607 /* Integer printing function is much faster, check if we can safely use it. */
608 if (double2ll(value, &lvalue))
609 len = ll2string(buf,len,lvalue);
610 else
611 len = snprintf(buf,len,"%.17g",value);
612 }
613
614 return len;
615}
616
617/* Trims off trailing zeros from a string representing a double. */
618int trimDoubleString(char *buf, size_t len) {
619 if (strchr(buf,'.') != NULL) {
620 char *p = buf+len-1;
621 while(*p == '0') {
622 p--;
623 len--;
624 }
625 if (*p == '.') len--;
626 }
627 buf[len] = '\0';
628 return len;
629}
630
631/* Create a string object from a long double.
632 * If mode is humanfriendly it does not use exponential format and trims trailing
633 * zeroes at the end (may result in loss of precision).
634 * If mode is default exp format is used and the output of snprintf()
635 * is not modified (may result in loss of precision).
636 * If mode is hex hexadecimal format is used (no loss of precision)
637 *
638 * The function returns the length of the string or zero if there was not
639 * enough buffer room to store it. */
640int ld2string(char *buf, size_t len, long double value, ld2string_mode mode) {
641 size_t l = 0;
642
643 if (isinf(value)) {
644 /* Libc in odd systems (Hi Solaris!) will format infinite in a
645 * different way, so better to handle it in an explicit way. */
646 if (len < 5) return 0; /* No room. 5 is "-inf\0" */
647 if (value > 0) {
648 memcpy(buf,"inf",3);
649 l = 3;
650 } else {
651 memcpy(buf,"-inf",4);
652 l = 4;
653 }
654 } else {
655 switch (mode) {
656 case LD_STR_AUTO:
657 l = snprintf(buf,len,"%.17Lg",value);
658 if (l+1 > len) return 0; /* No room. */
659 break;
660 case LD_STR_HEX:
661 l = snprintf(buf,len,"%La",value);
662 if (l+1 > len) return 0; /* No room. */
663 break;
664 case LD_STR_HUMAN:
665 /* We use 17 digits precision since with 128 bit floats that precision
666 * after rounding is able to represent most small decimal numbers in a
667 * way that is "non surprising" for the user (that is, most small
668 * decimal numbers will be represented in a way that when converted
669 * back into a string are exactly the same as what the user typed.) */
670 l = snprintf(buf,len,"%.17Lf",value);
671 if (l+1 > len) return 0; /* No room. */
672 /* Now remove trailing zeroes after the '.' */
673 if (strchr(buf,'.') != NULL) {
674 char *p = buf+l-1;
675 while(*p == '0') {
676 p--;
677 l--;
678 }
679 if (*p == '.') l--;
680 }
681 if (l == 2 && buf[0] == '-' && buf[1] == '0') {
682 buf[0] = '0';
683 l = 1;
684 }
685 break;
686 default: return 0; /* Invalid mode. */
687 }
688 }
689 buf[l] = '\0';
690 return l;
691}
692
693/* Get random bytes, attempts to get an initial seed from /dev/urandom and
694 * the uses a one way hash function in counter mode to generate a random
695 * stream. However if /dev/urandom is not available, a weaker seed is used.
696 *
697 * This function is not thread safe, since the state is global. */
698void getRandomBytes(unsigned char *p, size_t len) {
699 /* Global state. */
700 static int seed_initialized = 0;
701 static unsigned char seed[64]; /* 512 bit internal block size. */
702 static uint64_t counter = 0; /* The counter we hash with the seed. */
703
704 if (!seed_initialized) {
705 /* Initialize a seed and use SHA1 in counter mode, where we hash
706 * the same seed with a progressive counter. For the goals of this
707 * function we just need non-colliding strings, there are no
708 * cryptographic security needs. */
709 FILE *fp = fopen("/dev/urandom","r");
710 if (fp == NULL || fread(seed,sizeof(seed),1,fp) != 1) {
711 /* Revert to a weaker seed, and in this case reseed again
712 * at every call.*/
713 for (unsigned int j = 0; j < sizeof(seed); j++) {
714 struct timeval tv;
715 gettimeofday(&tv,NULL);
716 pid_t pid = getpid();
717 seed[j] = tv.tv_sec ^ tv.tv_usec ^ pid ^ (long)fp;
718 }
719 } else {
720 seed_initialized = 1;
721 }
722 if (fp) fclose(fp);
723 }
724
725 while(len) {
726 /* This implements SHA256-HMAC. */
727 unsigned char digest[SHA256_BLOCK_SIZE];
728 unsigned char kxor[64];
729 unsigned int copylen =
730 len > SHA256_BLOCK_SIZE ? SHA256_BLOCK_SIZE : len;
731
732 /* IKEY: key xored with 0x36. */
733 memcpy(kxor,seed,sizeof(kxor));
734 for (unsigned int i = 0; i < sizeof(kxor); i++) kxor[i] ^= 0x36;
735
736 /* Obtain HASH(IKEY||MESSAGE). */
737 SHA256_CTX ctx;
738 sha256_init(&ctx);
739 sha256_update(&ctx,kxor,sizeof(kxor));
740 sha256_update(&ctx,(unsigned char*)&counter,sizeof(counter));
741 sha256_final(&ctx,digest);
742
743 /* OKEY: key xored with 0x5c. */
744 memcpy(kxor,seed,sizeof(kxor));
745 for (unsigned int i = 0; i < sizeof(kxor); i++) kxor[i] ^= 0x5C;
746
747 /* Obtain HASH(OKEY || HASH(IKEY||MESSAGE)). */
748 sha256_init(&ctx);
749 sha256_update(&ctx,kxor,sizeof(kxor));
750 sha256_update(&ctx,digest,SHA256_BLOCK_SIZE);
751 sha256_final(&ctx,digest);
752
753 /* Increment the counter for the next iteration. */
754 counter++;
755
756 memcpy(p,digest,copylen);
757 len -= copylen;
758 p += copylen;
759 }
760}
761
762/* Generate the Redis "Run ID", a SHA1-sized random number that identifies a
763 * given execution of Redis, so that if you are talking with an instance
764 * having run_id == A, and you reconnect and it has run_id == B, you can be
765 * sure that it is either a different instance or it was restarted. */
766void getRandomHexChars(char *p, size_t len) {
767 char *charset = "0123456789abcdef";
768 size_t j;
769
770 getRandomBytes((unsigned char*)p,len);
771 for (j = 0; j < len; j++) p[j] = charset[p[j] & 0x0F];
772}
773
774/* Given the filename, return the absolute path as an SDS string, or NULL
775 * if it fails for some reason. Note that "filename" may be an absolute path
776 * already, this will be detected and handled correctly.
777 *
778 * The function does not try to normalize everything, but only the obvious
779 * case of one or more "../" appearing at the start of "filename"
780 * relative path. */
781sds getAbsolutePath(char *filename) {
782 char cwd[1024];
783 sds abspath;
784 sds relpath = sdsnew(filename);
785
786 relpath = sdstrim(relpath," \r\n\t");
787 if (relpath[0] == '/') return relpath; /* Path is already absolute. */
788
789 /* If path is relative, join cwd and relative path. */
790 if (getcwd(cwd,sizeof(cwd)) == NULL) {
791 sdsfree(relpath);
792 return NULL;
793 }
794 abspath = sdsnew(cwd);
795 if (sdslen(abspath) && abspath[sdslen(abspath)-1] != '/')
796 abspath = sdscat(abspath,"/");
797
798 /* At this point we have the current path always ending with "/", and
799 * the trimmed relative path. Try to normalize the obvious case of
800 * trailing ../ elements at the start of the path.
801 *
802 * For every "../" we find in the filename, we remove it and also remove
803 * the last element of the cwd, unless the current cwd is "/". */
804 while (sdslen(relpath) >= 3 &&
805 relpath[0] == '.' && relpath[1] == '.' && relpath[2] == '/')
806 {
807 sdsrange(relpath,3,-1);
808 if (sdslen(abspath) > 1) {
809 char *p = abspath + sdslen(abspath)-2;
810 int trimlen = 1;
811
812 while(*p != '/') {
813 p--;
814 trimlen++;
815 }
816 sdsrange(abspath,0,-(trimlen+1));
817 }
818 }
819
820 /* Finally glue the two parts together. */
821 abspath = sdscatsds(abspath,relpath);
822 sdsfree(relpath);
823 return abspath;
824}
825
826/*
827 * Gets the proper timezone in a more portable fashion
828 * i.e timezone variables are linux specific.
829 */
830long getTimeZone(void) {
831#if defined(__linux__) || defined(__sun)
832 return timezone;
833#else
834 struct timeval tv;
835 struct timezone tz;
836
837 gettimeofday(&tv, &tz);
838
839 return tz.tz_minuteswest * 60L;
840#endif
841}
842
843/* Return true if the specified path is just a file basename without any
844 * relative or absolute path. This function just checks that no / or \
845 * character exists inside the specified path, that's enough in the
846 * environments where Redis runs. */
847int pathIsBaseName(char *path) {
848 return strchr(path,'/') == NULL && strchr(path,'\\') == NULL;
849}
850
851int fileExist(char *filename) {
852 struct stat statbuf;
853 return stat(filename, &statbuf) == 0 && S_ISREG(statbuf.st_mode);
854}
855
856int dirExists(char *dname) {
857 struct stat statbuf;
858 return stat(dname, &statbuf) == 0 && S_ISDIR(statbuf.st_mode);
859}
860
861int dirCreateIfMissing(char *dname) {
862 if (mkdir(dname, 0755) != 0) {
863 if (errno != EEXIST) {
864 return -1;
865 } else if (!dirExists(dname)) {
866 errno = ENOTDIR;
867 return -1;
868 }
869 }
870 return 0;
871}
872
873int dirRemove(char *dname) {
874 DIR *dir;
875 struct stat stat_entry;
876 struct dirent *entry;
877 char full_path[PATH_MAX + 1];
878
879 if ((dir = opendir(dname)) == NULL) {
880 return -1;
881 }
882
883 while ((entry = readdir(dir)) != NULL) {
884 if (!strcmp(entry->d_name, ".") || !strcmp(entry->d_name, "..")) continue;
885
886 snprintf(full_path, sizeof(full_path), "%s/%s", dname, entry->d_name);
887
888 int fd = open(full_path, O_RDONLY|O_NONBLOCK);
889 if (fd == -1) {
890 closedir(dir);
891 return -1;
892 }
893
894 if (fstat(fd, &stat_entry) == -1) {
895 close(fd);
896 closedir(dir);
897 return -1;
898 }
899 close(fd);
900
901 if (S_ISDIR(stat_entry.st_mode) != 0) {
902 if (dirRemove(full_path) == -1) {
903 return -1;
904 }
905 continue;
906 }
907
908 if (unlink(full_path) != 0) {
909 closedir(dir);
910 return -1;
911 }
912 }
913
914 if (rmdir(dname) != 0) {
915 closedir(dir);
916 return -1;
917 }
918
919 closedir(dir);
920 return 0;
921}
922
923sds makePath(char *path, char *filename) {
924 return sdscatfmt(sdsempty(), "%s/%s", path, filename);
925}
926
927/* Given the filename, sync the corresponding directory.
928 *
929 * Usually a portable and safe pattern to overwrite existing files would be like:
930 * 1. create a new temp file (on the same file system!)
931 * 2. write data to the temp file
932 * 3. fsync() the temp file
933 * 4. rename the temp file to the appropriate name
934 * 5. fsync() the containing directory */
935int fsyncFileDir(const char *filename) {
936#ifdef _AIX
937 /* AIX is unable to fsync a directory */
938 return 0;
939#endif
940 char temp_filename[PATH_MAX + 1];
941 char *dname;
942 int dir_fd;
943
944 if (strlen(filename) > PATH_MAX) {
945 errno = ENAMETOOLONG;
946 return -1;
947 }
948
949 /* In the glibc implementation dirname may modify their argument. */
950 memcpy(temp_filename, filename, strlen(filename) + 1);
951 dname = dirname(temp_filename);
952
953 dir_fd = open(dname, O_RDONLY);
954 if (dir_fd == -1) {
955 /* Some OSs don't allow us to open directories at all, just
956 * ignore the error in that case */
957 if (errno == EISDIR) {
958 return 0;
959 }
960 return -1;
961 }
962 /* Some OSs don't allow us to fsync directories at all, so we can ignore
963 * those errors. */
964 if (redis_fsync(dir_fd) == -1 && !(errno == EBADF || errno == EINVAL)) {
965 int save_errno = errno;
966 close(dir_fd);
967 errno = save_errno;
968 return -1;
969 }
970
971 close(dir_fd);
972 return 0;
973}
974
975#ifdef REDIS_TEST
976#include <assert.h>
977
978static void test_string2ll(void) {
979 char buf[32];
980 long long v;
981
982 /* May not start with +. */
983 strcpy(buf,"+1");
984 assert(string2ll(buf,strlen(buf),&v) == 0);
985
986 /* Leading space. */
987 strcpy(buf," 1");
988 assert(string2ll(buf,strlen(buf),&v) == 0);
989
990 /* Trailing space. */
991 strcpy(buf,"1 ");
992 assert(string2ll(buf,strlen(buf),&v) == 0);
993
994 /* May not start with 0. */
995 strcpy(buf,"01");
996 assert(string2ll(buf,strlen(buf),&v) == 0);
997
998 strcpy(buf,"-1");
999 assert(string2ll(buf,strlen(buf),&v) == 1);
1000 assert(v == -1);
1001
1002 strcpy(buf,"0");
1003 assert(string2ll(buf,strlen(buf),&v) == 1);
1004 assert(v == 0);
1005
1006 strcpy(buf,"1");
1007 assert(string2ll(buf,strlen(buf),&v) == 1);
1008 assert(v == 1);
1009
1010 strcpy(buf,"99");
1011 assert(string2ll(buf,strlen(buf),&v) == 1);
1012 assert(v == 99);
1013
1014 strcpy(buf,"-99");
1015 assert(string2ll(buf,strlen(buf),&v) == 1);
1016 assert(v == -99);
1017
1018 strcpy(buf,"-9223372036854775808");
1019 assert(string2ll(buf,strlen(buf),&v) == 1);
1020 assert(v == LLONG_MIN);
1021
1022 strcpy(buf,"-9223372036854775809"); /* overflow */
1023 assert(string2ll(buf,strlen(buf),&v) == 0);
1024
1025 strcpy(buf,"9223372036854775807");
1026 assert(string2ll(buf,strlen(buf),&v) == 1);
1027 assert(v == LLONG_MAX);
1028
1029 strcpy(buf,"9223372036854775808"); /* overflow */
1030 assert(string2ll(buf,strlen(buf),&v) == 0);
1031}
1032
1033static void test_string2l(void) {
1034 char buf[32];
1035 long v;
1036
1037 /* May not start with +. */
1038 strcpy(buf,"+1");
1039 assert(string2l(buf,strlen(buf),&v) == 0);
1040
1041 /* May not start with 0. */
1042 strcpy(buf,"01");
1043 assert(string2l(buf,strlen(buf),&v) == 0);
1044
1045 strcpy(buf,"-1");
1046 assert(string2l(buf,strlen(buf),&v) == 1);
1047 assert(v == -1);
1048
1049 strcpy(buf,"0");
1050 assert(string2l(buf,strlen(buf),&v) == 1);
1051 assert(v == 0);
1052
1053 strcpy(buf,"1");
1054 assert(string2l(buf,strlen(buf),&v) == 1);
1055 assert(v == 1);
1056
1057 strcpy(buf,"99");
1058 assert(string2l(buf,strlen(buf),&v) == 1);
1059 assert(v == 99);
1060
1061 strcpy(buf,"-99");
1062 assert(string2l(buf,strlen(buf),&v) == 1);
1063 assert(v == -99);
1064
1065#if LONG_MAX != LLONG_MAX
1066 strcpy(buf,"-2147483648");
1067 assert(string2l(buf,strlen(buf),&v) == 1);
1068 assert(v == LONG_MIN);
1069
1070 strcpy(buf,"-2147483649"); /* overflow */
1071 assert(string2l(buf,strlen(buf),&v) == 0);
1072
1073 strcpy(buf,"2147483647");
1074 assert(string2l(buf,strlen(buf),&v) == 1);
1075 assert(v == LONG_MAX);
1076
1077 strcpy(buf,"2147483648"); /* overflow */
1078 assert(string2l(buf,strlen(buf),&v) == 0);
1079#endif
1080}
1081
1082static void test_ll2string(void) {
1083 char buf[32];
1084 long long v;
1085 int sz;
1086
1087 v = 0;
1088 sz = ll2string(buf, sizeof buf, v);
1089 assert(sz == 1);
1090 assert(!strcmp(buf, "0"));
1091
1092 v = -1;
1093 sz = ll2string(buf, sizeof buf, v);
1094 assert(sz == 2);
1095 assert(!strcmp(buf, "-1"));
1096
1097 v = 99;
1098 sz = ll2string(buf, sizeof buf, v);
1099 assert(sz == 2);
1100 assert(!strcmp(buf, "99"));
1101
1102 v = -99;
1103 sz = ll2string(buf, sizeof buf, v);
1104 assert(sz == 3);
1105 assert(!strcmp(buf, "-99"));
1106
1107 v = -2147483648;
1108 sz = ll2string(buf, sizeof buf, v);
1109 assert(sz == 11);
1110 assert(!strcmp(buf, "-2147483648"));
1111
1112 v = LLONG_MIN;
1113 sz = ll2string(buf, sizeof buf, v);
1114 assert(sz == 20);
1115 assert(!strcmp(buf, "-9223372036854775808"));
1116
1117 v = LLONG_MAX;
1118 sz = ll2string(buf, sizeof buf, v);
1119 assert(sz == 19);
1120 assert(!strcmp(buf, "9223372036854775807"));
1121}
1122
1123#define UNUSED(x) (void)(x)
1124int utilTest(int argc, char **argv, int flags) {
1125 UNUSED(argc);
1126 UNUSED(argv);
1127 UNUSED(flags);
1128
1129 test_string2ll();
1130 test_string2l();
1131 test_ll2string();
1132 return 0;
1133}
1134#endif
1135