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 41 #include "util.h" 42 43 /* Glob-style pattern matching. */ 44 int stringmatchlen(const char *pattern, int patternLen, 45 const char *string, int stringLen, int nocase) 46 { 47 while(patternLen) { 48 switch(pattern[0]) { 49 case '*': 50 while (pattern[1] == '*') { 51 pattern++; 52 patternLen--; 53 } 54 if (patternLen == 1) 55 return 1; /* match */ 56 while(stringLen) { 57 if (stringmatchlen(pattern+1, patternLen-1, 58 string, stringLen, nocase)) 59 return 1; /* match */ 60 string++; 61 stringLen--; 62 } 63 return 0; /* no match */ 64 break; 65 case '?': 66 if (stringLen == 0) 67 return 0; /* no match */ 68 string++; 69 stringLen--; 70 break; 71 case '[': 72 { 73 int not, match; 74 75 pattern++; 76 patternLen--; 77 not = pattern[0] == '^'; 78 if (not) { 79 pattern++; 80 patternLen--; 81 } 82 match = 0; 83 while(1) { 84 if (pattern[0] == '\\') { 85 pattern++; 86 patternLen--; 87 if (pattern[0] == string[0]) 88 match = 1; 89 } else if (pattern[0] == ']') { 90 break; 91 } else if (patternLen == 0) { 92 pattern--; 93 patternLen++; 94 break; 95 } else if (pattern[1] == '-' && patternLen >= 3) { 96 int start = pattern[0]; 97 int end = pattern[2]; 98 int c = string[0]; 99 if (start > end) { 100 int t = start; 101 start = end; 102 end = t; 103 } 104 if (nocase) { 105 start = tolower(start); 106 end = tolower(end); 107 c = tolower(c); 108 } 109 pattern += 2; 110 patternLen -= 2; 111 if (c >= start && c <= end) 112 match = 1; 113 } else { 114 if (!nocase) { 115 if (pattern[0] == string[0]) 116 match = 1; 117 } else { 118 if (tolower((int)pattern[0]) == tolower((int)string[0])) 119 match = 1; 120 } 121 } 122 pattern++; 123 patternLen--; 124 } 125 if (not) 126 match = !match; 127 if (!match) 128 return 0; /* no match */ 129 string++; 130 stringLen--; 131 break; 132 } 133 case '\\': 134 if (patternLen >= 2) { 135 pattern++; 136 patternLen--; 137 } 138 /* fall through */ 139 default: 140 if (!nocase) { 141 if (pattern[0] != string[0]) 142 return 0; /* no match */ 143 } else { 144 if (tolower((int)pattern[0]) != tolower((int)string[0])) 145 return 0; /* no match */ 146 } 147 string++; 148 stringLen--; 149 break; 150 } 151 pattern++; 152 patternLen--; 153 if (stringLen == 0) { 154 while(*pattern == '*') { 155 pattern++; 156 patternLen--; 157 } 158 break; 159 } 160 } 161 if (patternLen == 0 && stringLen == 0) 162 return 1; 163 return 0; 164 } 165 166 int stringmatch(const char *pattern, const char *string, int nocase) { 167 return stringmatchlen(pattern,strlen(pattern),string,strlen(string),nocase); 168 } 169 170 /* Convert a string representing an amount of memory into the number of 171 * bytes, so for instance memtoll("1Gi") will return 1073741824 that is 172 * (1024*1024*1024). 173 * 174 * On parsing error, if *err is not NULL, it's set to 1, otherwise it's 175 * set to 0 */ 176 long long memtoll(const char *p, int *err) { 177 const char *u; 178 char buf[128]; 179 long mul; /* unit multiplier */ 180 long long val; 181 unsigned int digits; 182 183 if (err) *err = 0; 184 /* Search the first non digit character. */ 185 u = p; 186 if (*u == '-') u++; 187 while(*u && isdigit(*u)) u++; 188 if (*u == '\0' || !strcasecmp(u,"b")) { 189 mul = 1; 190 } else if (!strcasecmp(u,"k")) { 191 mul = 1000; 192 } else if (!strcasecmp(u,"kb")) { 193 mul = 1024; 194 } else if (!strcasecmp(u,"m")) { 195 mul = 1000*1000; 196 } else if (!strcasecmp(u,"mb")) { 197 mul = 1024*1024; 198 } else if (!strcasecmp(u,"g")) { 199 mul = 1000L*1000*1000; 200 } else if (!strcasecmp(u,"gb")) { 201 mul = 1024L*1024*1024; 202 } else { 203 if (err) *err = 1; 204 mul = 1; 205 } 206 digits = u-p; 207 if (digits >= sizeof(buf)) { 208 if (err) *err = 1; 209 return LLONG_MAX; 210 } 211 memcpy(buf,p,digits); 212 buf[digits] = '\0'; 213 val = strtoll(buf,NULL,10); 214 return val*mul; 215 } 216 217 /* Convert a long long into a string. Returns the number of 218 * characters needed to represent the number, that can be shorter if passed 219 * buffer length is not enough to store the whole number. */ 220 int ll2string(char *s, size_t len, long long value) { 221 char buf[32], *p; 222 unsigned long long v; 223 size_t l; 224 225 if (len == 0) return 0; 226 v = (value < 0) ? -value : value; 227 p = buf+31; /* point to the last character */ 228 do { 229 *p-- = '0'+(v%10); 230 v /= 10; 231 } while(v); 232 if (value < 0) *p-- = '-'; 233 p++; 234 l = 32-(p-buf); 235 if (l+1 > len) l = len-1; /* Make sure it fits, including the nul term */ 236 memcpy(s,p,l); 237 s[l] = '\0'; 238 return l; 239 } 240 241 /* Convert a string into a long long. Returns 1 if the string could be parsed 242 * into a (non-overflowing) long long, 0 otherwise. The value will be set to 243 * the parsed value when appropriate. */ 244 int string2ll(const char *s, size_t slen, long long *value) { 245 const char *p = s; 246 size_t plen = 0; 247 int negative = 0; 248 unsigned long long v; 249 250 if (plen == slen) 251 return 0; 252 253 /* Special case: first and only digit is 0. */ 254 if (slen == 1 && p[0] == '0') { 255 if (value != NULL) *value = 0; 256 return 1; 257 } 258 259 if (p[0] == '-') { 260 negative = 1; 261 p++; plen++; 262 263 /* Abort on only a negative sign. */ 264 if (plen == slen) 265 return 0; 266 } 267 268 /* First digit should be 1-9, otherwise the string should just be 0. */ 269 if (p[0] >= '1' && p[0] <= '9') { 270 v = p[0]-'0'; 271 p++; plen++; 272 } else if (p[0] == '0' && slen == 1) { 273 *value = 0; 274 return 1; 275 } else { 276 return 0; 277 } 278 279 while (plen < slen && p[0] >= '0' && p[0] <= '9') { 280 if (v > (ULLONG_MAX / 10)) /* Overflow. */ 281 return 0; 282 v *= 10; 283 284 if (v > (ULLONG_MAX - (p[0]-'0'))) /* Overflow. */ 285 return 0; 286 v += p[0]-'0'; 287 288 p++; plen++; 289 } 290 291 /* Return if not all bytes were used. */ 292 if (plen < slen) 293 return 0; 294 295 if (negative) { 296 if (v > ((unsigned long long)(-(LLONG_MIN+1))+1)) /* Overflow. */ 297 return 0; 298 if (value != NULL) *value = -v; 299 } else { 300 if (v > LLONG_MAX) /* Overflow. */ 301 return 0; 302 if (value != NULL) *value = v; 303 } 304 return 1; 305 } 306 307 /* Convert a string into a long. Returns 1 if the string could be parsed into a 308 * (non-overflowing) long, 0 otherwise. The value will be set to the parsed 309 * value when appropriate. */ 310 int string2l(const char *s, size_t slen, long *lval) { 311 long long llval; 312 313 if (!string2ll(s,slen,&llval)) 314 return 0; 315 316 if (llval < LONG_MIN || llval > LONG_MAX) 317 return 0; 318 319 *lval = (long)llval; 320 return 1; 321 } 322 323 /* Convert a double to a string representation. Returns the number of bytes 324 * required. The representation should always be parsable by stdtod(3). */ 325 int d2string(char *buf, size_t len, double value) { 326 if (isnan(value)) { 327 len = snprintf(buf,len,"nan"); 328 } else if (isinf(value)) { 329 if (value < 0) 330 len = snprintf(buf,len,"-inf"); 331 else 332 len = snprintf(buf,len,"inf"); 333 } else if (value == 0) { 334 /* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */ 335 if (1.0/value < 0) 336 len = snprintf(buf,len,"-0"); 337 else 338 len = snprintf(buf,len,"0"); 339 } else { 340 #if (DBL_MANT_DIG >= 52) && (LLONG_MAX == 0x7fffffffffffffffLL) 341 /* Check if the float is in a safe range to be casted into a 342 * long long. We are assuming that long long is 64 bit here. 343 * Also we are assuming that there are no implementations around where 344 * double has precision < 52 bit. 345 * 346 * Under this assumptions we test if a double is inside an interval 347 * where casting to long long is safe. Then using two castings we 348 * make sure the decimal part is zero. If all this is true we use 349 * integer printing function that is much faster. */ 350 double min = -4503599627370495; /* (2^52)-1 */ 351 double max = 4503599627370496; /* -(2^52) */ 352 if (value > min && value < max && value == ((double)((long long)value))) 353 len = ll2string(buf,len,(long long)value); 354 else 355 #endif 356 len = snprintf(buf,len,"%.17g",value); 357 } 358 359 return len; 360 } 361 362 /* Generate the Redis "Run ID", a SHA1-sized random number that identifies a 363 * given execution of Redis, so that if you are talking with an instance 364 * having run_id == A, and you reconnect and it has run_id == B, you can be 365 * sure that it is either a different instance or it was restarted. */ 366 void getRandomHexChars(char *p, unsigned int len) { 367 FILE *fp = fopen("/dev/urandom","r"); 368 char *charset = "0123456789abcdef"; 369 unsigned int j; 370 371 if (fp == NULL || fread(p,len,1,fp) == 0) { 372 /* If we can't read from /dev/urandom, do some reasonable effort 373 * in order to create some entropy, since this function is used to 374 * generate run_id and cluster instance IDs */ 375 char *x = p; 376 unsigned int l = len; 377 struct timeval tv; 378 pid_t pid = getpid(); 379 380 /* Use time and PID to fill the initial array. */ 381 gettimeofday(&tv,NULL); 382 if (l >= sizeof(tv.tv_usec)) { 383 memcpy(x,&tv.tv_usec,sizeof(tv.tv_usec)); 384 l -= sizeof(tv.tv_usec); 385 x += sizeof(tv.tv_usec); 386 } 387 if (l >= sizeof(tv.tv_sec)) { 388 memcpy(x,&tv.tv_sec,sizeof(tv.tv_sec)); 389 l -= sizeof(tv.tv_sec); 390 x += sizeof(tv.tv_sec); 391 } 392 if (l >= sizeof(pid)) { 393 memcpy(x,&pid,sizeof(pid)); 394 l -= sizeof(pid); 395 x += sizeof(pid); 396 } 397 /* Finally xor it with rand() output, that was already seeded with 398 * time() at startup. */ 399 for (j = 0; j < len; j++) 400 p[j] ^= rand(); 401 } 402 /* Turn it into hex digits taking just 4 bits out of 8 for every byte. */ 403 for (j = 0; j < len; j++) 404 p[j] = charset[p[j] & 0x0F]; 405 if (fp) fclose(fp); 406 } 407 408 /* Given the filename, return the absolute path as an SDS string, or NULL 409 * if it fails for some reason. Note that "filename" may be an absolute path 410 * already, this will be detected and handled correctly. 411 * 412 * The function does not try to normalize everything, but only the obvious 413 * case of one or more "../" appearning at the start of "filename" 414 * relative path. */ 415 sds getAbsolutePath(char *filename) { 416 char cwd[1024]; 417 sds abspath; 418 sds relpath = sdsnew(filename); 419 420 relpath = sdstrim(relpath," \r\n\t"); 421 if (relpath[0] == '/') return relpath; /* Path is already absolute. */ 422 423 /* If path is relative, join cwd and relative path. */ 424 if (getcwd(cwd,sizeof(cwd)) == NULL) { 425 sdsfree(relpath); 426 return NULL; 427 } 428 abspath = sdsnew(cwd); 429 if (sdslen(abspath) && abspath[sdslen(abspath)-1] != '/') 430 abspath = sdscat(abspath,"/"); 431 432 /* At this point we have the current path always ending with "/", and 433 * the trimmed relative path. Try to normalize the obvious case of 434 * trailing ../ elements at the start of the path. 435 * 436 * For every "../" we find in the filename, we remove it and also remove 437 * the last element of the cwd, unless the current cwd is "/". */ 438 while (sdslen(relpath) >= 3 && 439 relpath[0] == '.' && relpath[1] == '.' && relpath[2] == '/') 440 { 441 sdsrange(relpath,3,-1); 442 if (sdslen(abspath) > 1) { 443 char *p = abspath + sdslen(abspath)-2; 444 int trimlen = 1; 445 446 while(*p != '/') { 447 p--; 448 trimlen++; 449 } 450 sdsrange(abspath,0,-(trimlen+1)); 451 } 452 } 453 454 /* Finally glue the two parts together. */ 455 abspath = sdscatsds(abspath,relpath); 456 sdsfree(relpath); 457 return abspath; 458 } 459 460 /* Return true if the specified path is just a file basename without any 461 * relative or absolute path. This function just checks that no / or \ 462 * character exists inside the specified path, that's enough in the 463 * environments where Redis runs. */ 464 int pathIsBaseName(char *path) { 465 return strchr(path,'/') == NULL && strchr(path,'\\') == NULL; 466 } 467 468 #ifdef UTIL_TEST_MAIN 469 #include <assert.h> 470 471 void test_string2ll(void) { 472 char buf[32]; 473 long long v; 474 475 /* May not start with +. */ 476 strcpy(buf,"+1"); 477 assert(string2ll(buf,strlen(buf),&v) == 0); 478 479 /* Leading space. */ 480 strcpy(buf," 1"); 481 assert(string2ll(buf,strlen(buf),&v) == 0); 482 483 /* Trailing space. */ 484 strcpy(buf,"1 "); 485 assert(string2ll(buf,strlen(buf),&v) == 0); 486 487 /* May not start with 0. */ 488 strcpy(buf,"01"); 489 assert(string2ll(buf,strlen(buf),&v) == 0); 490 491 strcpy(buf,"-1"); 492 assert(string2ll(buf,strlen(buf),&v) == 1); 493 assert(v == -1); 494 495 strcpy(buf,"0"); 496 assert(string2ll(buf,strlen(buf),&v) == 1); 497 assert(v == 0); 498 499 strcpy(buf,"1"); 500 assert(string2ll(buf,strlen(buf),&v) == 1); 501 assert(v == 1); 502 503 strcpy(buf,"99"); 504 assert(string2ll(buf,strlen(buf),&v) == 1); 505 assert(v == 99); 506 507 strcpy(buf,"-99"); 508 assert(string2ll(buf,strlen(buf),&v) == 1); 509 assert(v == -99); 510 511 strcpy(buf,"-9223372036854775808"); 512 assert(string2ll(buf,strlen(buf),&v) == 1); 513 assert(v == LLONG_MIN); 514 515 strcpy(buf,"-9223372036854775809"); /* overflow */ 516 assert(string2ll(buf,strlen(buf),&v) == 0); 517 518 strcpy(buf,"9223372036854775807"); 519 assert(string2ll(buf,strlen(buf),&v) == 1); 520 assert(v == LLONG_MAX); 521 522 strcpy(buf,"9223372036854775808"); /* overflow */ 523 assert(string2ll(buf,strlen(buf),&v) == 0); 524 } 525 526 void test_string2l(void) { 527 char buf[32]; 528 long v; 529 530 /* May not start with +. */ 531 strcpy(buf,"+1"); 532 assert(string2l(buf,strlen(buf),&v) == 0); 533 534 /* May not start with 0. */ 535 strcpy(buf,"01"); 536 assert(string2l(buf,strlen(buf),&v) == 0); 537 538 strcpy(buf,"-1"); 539 assert(string2l(buf,strlen(buf),&v) == 1); 540 assert(v == -1); 541 542 strcpy(buf,"0"); 543 assert(string2l(buf,strlen(buf),&v) == 1); 544 assert(v == 0); 545 546 strcpy(buf,"1"); 547 assert(string2l(buf,strlen(buf),&v) == 1); 548 assert(v == 1); 549 550 strcpy(buf,"99"); 551 assert(string2l(buf,strlen(buf),&v) == 1); 552 assert(v == 99); 553 554 strcpy(buf,"-99"); 555 assert(string2l(buf,strlen(buf),&v) == 1); 556 assert(v == -99); 557 558 #if LONG_MAX != LLONG_MAX 559 strcpy(buf,"-2147483648"); 560 assert(string2l(buf,strlen(buf),&v) == 1); 561 assert(v == LONG_MIN); 562 563 strcpy(buf,"-2147483649"); /* overflow */ 564 assert(string2l(buf,strlen(buf),&v) == 0); 565 566 strcpy(buf,"2147483647"); 567 assert(string2l(buf,strlen(buf),&v) == 1); 568 assert(v == LONG_MAX); 569 570 strcpy(buf,"2147483648"); /* overflow */ 571 assert(string2l(buf,strlen(buf),&v) == 0); 572 #endif 573 } 574 575 int main(int argc, char **argv) { 576 test_string2ll(); 577 test_string2l(); 578 return 0; 579 } 580 #endif 581