src/util.h

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7 #ifndef INCLUDE_util_h__
   8 #define INCLUDE_util_h__
   9
  10 #if defined(GIT_MSVC_CRTDBG)
  11 /* Enable MSVC CRTDBG memory leak reporting.
  12  *
  13  * We DO NOT use the "_CRTDBG_MAP_ALLOC" macro described in the MSVC
  14  * documentation because all allocs/frees in libgit2 already go through
  15  * the "git__" routines defined in this file.  Simply using the normal
  16  * reporting mechanism causes all leaks to be attributed to a routine
  17  * here in util.h (ie, the actual call to calloc()) rather than the
  18  * caller of git__calloc().
  19  *
  20  * Therefore, we declare a set of "git__crtdbg__" routines to replace
  21  * the corresponding "git__" routines and re-define the "git__" symbols
  22  * as macros.  This allows us to get and report the file:line info of
  23  * the real caller.
  24  *
  25  * We DO NOT replace the "git__free" routine because it needs to remain
  26  * a function pointer because it is used as a function argument when
  27  * setting up various structure "destructors".
  28  *
  29  * We also DO NOT use the "_CRTDBG_MAP_ALLOC" macro because it causes
  30  * "free" to be remapped to "_free_dbg" and this causes problems for
  31  * structures which define a field named "free".
  32  *
  33  * Finally, CRTDBG must be explicitly enabled and configured at program
  34  * startup.  See tests/main.c for an example.
  35  */
  36 #include <stdlib.h>
  37 #include <crtdbg.h>
  38 #include "win32/w32_crtdbg_stacktrace.h"
  39 #endif
  40
  41 #include "common.h"
  42 #include "strnlen.h"
  43
  44 #define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))
  45 #define bitsizeof(x) (CHAR_BIT * sizeof(x))
  46 #define MSB(x, bits) ((x) & (~0ULL << (bitsizeof(x) - (bits))))
  47 #ifndef min
  48 # define min(a,b) ((a) < (b) ? (a) : (b))
  49 #endif
  50 #ifndef max
  51 # define max(a,b) ((a) > (b) ? (a) : (b))
  52 #endif
  53
  54 #define GIT_DATE_RFC2822_SZ  32
  55
  56 /**
  57  * Return the length of a constant string.
  58  * We are aware that `strlen` performs the same task and is usually
  59  * optimized away by the compiler, whilst being safer because it returns
  60  * valid values when passed a pointer instead of a constant string; however
  61  * this macro will transparently work with wide-char and single-char strings.
  62  */
  63 #define CONST_STRLEN(x) ((sizeof(x)/sizeof(x[0])) - 1)
  64
  65 #if defined(GIT_MSVC_CRTDBG)
  66
  67 GIT_INLINE(void *) git__crtdbg__malloc(size_t len, const char *file, int line)
  68 {
  69         void *ptr = _malloc_dbg(len, _NORMAL_BLOCK, git_win32__crtdbg_stacktrace(1,file), line);
  70         if (!ptr) giterr_set_oom();
  71         return ptr;
  72 }
  73
  74 GIT_INLINE(void *) git__crtdbg__calloc(size_t nelem, size_t elsize, const char *file, int line)
  75 {
  76         void *ptr = _calloc_dbg(nelem, elsize, _NORMAL_BLOCK, git_win32__crtdbg_stacktrace(1,file), line);
  77         if (!ptr) giterr_set_oom();
  78         return ptr;
  79 }
  80
  81 GIT_INLINE(char *) git__crtdbg__strdup(const char *str, const char *file, int line)
  82 {
  83         char *ptr = _strdup_dbg(str, _NORMAL_BLOCK, git_win32__crtdbg_stacktrace(1,file), line);
  84         if (!ptr) giterr_set_oom();
  85         return ptr;
  86 }
  87
  88 GIT_INLINE(char *) git__crtdbg__strndup(const char *str, size_t n, const char *file, int line)
  89 {
  90         size_t length = 0, alloclength;
  91         char *ptr;
  92
  93         length = p_strnlen(str, n);
  94
  95         if (GIT_ADD_SIZET_OVERFLOW(&alloclength, length, 1) ||
  96                 !(ptr = git__crtdbg__malloc(alloclength, file, line)))
  97                 return NULL;
  98
  99         if (length)
 100                 memcpy(ptr, str, length);
 101
 102         ptr[length] = '\0';
 103
 104         return ptr;
 105 }
 106
 107 GIT_INLINE(char *) git__crtdbg__substrdup(const char *start, size_t n, const char *file, int line)
 108 {
 109         char *ptr;
 110         size_t alloclen;
 111
 112         if (GIT_ADD_SIZET_OVERFLOW(&alloclen, n, 1) ||
 113                 !(ptr = git__crtdbg__malloc(alloclen, file, line)))
 114                 return NULL;
 115
 116         memcpy(ptr, start, n);
 117         ptr[n] = '\0';
 118         return ptr;
 119 }
 120
 121 GIT_INLINE(void *) git__crtdbg__realloc(void *ptr, size_t size, const char *file, int line)
 122 {
 123         void *new_ptr = _realloc_dbg(ptr, size, _NORMAL_BLOCK, git_win32__crtdbg_stacktrace(1,file), line);
 124         if (!new_ptr) giterr_set_oom();
 125         return new_ptr;
 126 }
 127
 128 GIT_INLINE(void *) git__crtdbg__reallocarray(void *ptr, size_t nelem, size_t elsize, const char *file, int line)
 129 {
 130         size_t newsize;
 131
 132         return GIT_MULTIPLY_SIZET_OVERFLOW(&newsize, nelem, elsize) ?
 133                 NULL : _realloc_dbg(ptr, newsize, _NORMAL_BLOCK, git_win32__crtdbg_stacktrace(1,file), line);
 134 }
 135
 136 GIT_INLINE(void *) git__crtdbg__mallocarray(size_t nelem, size_t elsize, const char *file, int line)
 137 {
 138         return git__crtdbg__reallocarray(NULL, nelem, elsize, file, line);
 139 }
 140
 141 #define git__malloc(len)                      git__crtdbg__malloc(len, __FILE__, __LINE__)
 142 #define git__calloc(nelem, elsize)            git__crtdbg__calloc(nelem, elsize, __FILE__, __LINE__)
 143 #define git__strdup(str)                      git__crtdbg__strdup(str, __FILE__, __LINE__)
 144 #define git__strndup(str, n)                  git__crtdbg__strndup(str, n, __FILE__, __LINE__)
 145 #define git__substrdup(str, n)                git__crtdbg__substrdup(str, n, __FILE__, __LINE__)
 146 #define git__realloc(ptr, size)               git__crtdbg__realloc(ptr, size, __FILE__, __LINE__)
 147 #define git__reallocarray(ptr, nelem, elsize) git__crtdbg__reallocarray(ptr, nelem, elsize, __FILE__, __LINE__)
 148 #define git__mallocarray(nelem, elsize)       git__crtdbg__mallocarray(nelem, elsize, __FILE__, __LINE__)
 149
 150 #else
 151
 152 /*
 153  * Custom memory allocation wrappers
 154  * that set error code and error message
 155  * on allocation failure
 156  */
 157 GIT_INLINE(void *) git__malloc(size_t len)
 158 {
 159         void *ptr = malloc(len);
 160         if (!ptr) giterr_set_oom();
 161         return ptr;
 162 }
 163
 164 GIT_INLINE(void *) git__calloc(size_t nelem, size_t elsize)
 165 {
 166         void *ptr = calloc(nelem, elsize);
 167         if (!ptr) giterr_set_oom();
 168         return ptr;
 169 }
 170
 171 GIT_INLINE(char *) git__strdup(const char *str)
 172 {
 173         char *ptr = strdup(str);
 174         if (!ptr) giterr_set_oom();
 175         return ptr;
 176 }
 177
 178 GIT_INLINE(char *) git__strndup(const char *str, size_t n)
 179 {
 180         size_t length = 0, alloclength;
 181         char *ptr;
 182
 183         length = p_strnlen(str, n);
 184
 185         if (GIT_ADD_SIZET_OVERFLOW(&alloclength, length, 1) ||
 186                 !(ptr = git__malloc(alloclength)))
 187                 return NULL;
 188
 189         if (length)
 190                 memcpy(ptr, str, length);
 191
 192         ptr[length] = '\0';
 193
 194         return ptr;
 195 }
 196
 197 /* NOTE: This doesn't do null or '\0' checking.  Watch those boundaries! */
 198 GIT_INLINE(char *) git__substrdup(const char *start, size_t n)
 199 {
 200         char *ptr;
 201         size_t alloclen;
 202
 203         if (GIT_ADD_SIZET_OVERFLOW(&alloclen, n, 1) ||
 204                 !(ptr = git__malloc(alloclen)))
 205                 return NULL;
 206
 207         memcpy(ptr, start, n);
 208         ptr[n] = '\0';
 209         return ptr;
 210 }
 211
 212 GIT_INLINE(void *) git__realloc(void *ptr, size_t size)
 213 {
 214         void *new_ptr = realloc(ptr, size);
 215         if (!new_ptr) giterr_set_oom();
 216         return new_ptr;
 217 }
 218
 219 /**
 220  * Similar to `git__realloc`, except that it is suitable for reallocing an
 221  * array to a new number of elements of `nelem`, each of size `elsize`.
 222  * The total size calculation is checked for overflow.
 223  */
 224 GIT_INLINE(void *) git__reallocarray(void *ptr, size_t nelem, size_t elsize)
 225 {
 226         size_t newsize;
 227         return GIT_MULTIPLY_SIZET_OVERFLOW(&newsize, nelem, elsize) ?
 228                 NULL : realloc(ptr, newsize);
 229 }
 230
 231 /**
 232  * Similar to `git__calloc`, except that it does not zero memory.
 233  */
 234 GIT_INLINE(void *) git__mallocarray(size_t nelem, size_t elsize)
 235 {
 236         return git__reallocarray(NULL, nelem, elsize);
 237 }
 238
 239 #endif /* !MSVC_CTRDBG */
 240
 241 GIT_INLINE(void) git__free(void *ptr)
 242 {
 243         free(ptr);
 244 }
 245
 246 #define STRCMP_CASESELECT(IGNORE_CASE, STR1, STR2) \
 247         ((IGNORE_CASE) ? strcasecmp((STR1), (STR2)) : strcmp((STR1), (STR2)))
 248
 249 #define CASESELECT(IGNORE_CASE, ICASE, CASE) \
 250         ((IGNORE_CASE) ? (ICASE) : (CASE))
 251
 252 extern int git__prefixcmp(const char *str, const char *prefix);
 253 extern int git__prefixcmp_icase(const char *str, const char *prefix);
 254 extern int git__prefixncmp_icase(const char *str, size_t str_n, const char *prefix);
 255 extern int git__suffixcmp(const char *str, const char *suffix);
 256
 257 GIT_INLINE(int) git__signum(int val)
 258 {
 259         return ((val > 0) - (val < 0));
 260 }
 261
 262 extern int git__strtol32(int32_t *n, const char *buff, const char **end_buf, int base);
 263 extern int git__strtol64(int64_t *n, const char *buff, const char **end_buf, int base);
 264
 265 extern void git__hexdump(const char *buffer, size_t n);
 266 extern uint32_t git__hash(const void *key, int len, uint32_t seed);
 267
 268 /* 32-bit cross-platform rotl */
 269 #ifdef _MSC_VER /* use built-in method in MSVC */
 270 #       define git__rotl(v, s) (uint32_t)_rotl(v, s)
 271 #else /* use bitops in GCC; with o2 this gets optimized to a rotl instruction */
 272 #       define git__rotl(v, s) (uint32_t)(((uint32_t)(v) << (s)) | ((uint32_t)(v) >> (32 - (s))))
 273 #endif
 274
 275 extern char *git__strtok(char **end, const char *sep);
 276 extern char *git__strsep(char **end, const char *sep);
 277
 278 extern void git__strntolower(char *str, size_t len);
 279 extern void git__strtolower(char *str);
 280
 281 #ifdef GIT_WIN32
 282 GIT_INLINE(int) git__tolower(int c)
 283 {
 284         return (c >= 'A' && c <= 'Z') ? (c + 32) : c;
 285 }
 286 #else
 287 # define git__tolower(a) tolower(a)
 288 #endif
 289
 290 GIT_INLINE(const char *) git__next_line(const char *s)
 291 {
 292         while (*s && *s != '\n') s++;
 293         while (*s == '\n' || *s == '\r') s++;
 294         return s;
 295 }
 296
 297 GIT_INLINE(const void *) git__memrchr(const void *s, int c, size_t n)
 298 {
 299         const unsigned char *cp;
 300
 301         if (n != 0) {
 302                 cp = (unsigned char *)s + n;
 303                 do {
 304                         if (*(--cp) == (unsigned char)c)
 305                                 return cp;
 306                 } while (--n != 0);
 307         }
 308
 309         return NULL;
 310 }
 311
 312 typedef int (*git__tsort_cmp)(const void *a, const void *b);
 313
 314 extern void git__tsort(void **dst, size_t size, git__tsort_cmp cmp);
 315
 316 typedef int (*git__sort_r_cmp)(const void *a, const void *b, void *payload);
 317
 318 extern void git__tsort_r(
 319         void **dst, size_t size, git__sort_r_cmp cmp, void *payload);
 320
 321 extern void git__qsort_r(
 322         void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload);
 323
 324 extern void git__insertsort_r(
 325         void *els, size_t nel, size_t elsize, void *swapel,
 326         git__sort_r_cmp cmp, void *payload);
 327
 328 /**
 329  * @param position If non-NULL, this will be set to the position where the
 330  *              element is or would be inserted if not found.
 331  * @return 0 if found; GIT_ENOTFOUND if not found
 332  */
 333 extern int git__bsearch(
 334         void **array,
 335         size_t array_len,
 336         const void *key,
 337         int (*compare)(const void *key, const void *element),
 338         size_t *position);
 339
 340 extern int git__bsearch_r(
 341         void **array,
 342         size_t array_len,
 343         const void *key,
 344         int (*compare_r)(const void *key, const void *element, void *payload),
 345         void *payload,
 346         size_t *position);
 347
 348 extern int git__strcmp_cb(const void *a, const void *b);
 349 extern int git__strcasecmp_cb(const void *a, const void *b);
 350
 351 extern int git__strcmp(const char *a, const char *b);
 352 extern int git__strcasecmp(const char *a, const char *b);
 353 extern int git__strncmp(const char *a, const char *b, size_t sz);
 354 extern int git__strncasecmp(const char *a, const char *b, size_t sz);
 355
 356 extern int git__strcasesort_cmp(const char *a, const char *b);
 357
 358 #include "thread-utils.h"
 359
 360 typedef struct {
 361         git_atomic refcount;
 362         void *owner;
 363 } git_refcount;
 364
 365 typedef void (*git_refcount_freeptr)(void *r);
 366
 367 #define GIT_REFCOUNT_INC(r) { \
 368         git_atomic_inc(&((git_refcount *)(r))->refcount);       \
 369 }
 370
 371 #define GIT_REFCOUNT_DEC(_r, do_free) { \
 372         git_refcount *r = (git_refcount *)(_r); \
 373         int val = git_atomic_dec(&r->refcount); \
 374         if (val <= 0 && r->owner == NULL) { do_free(_r); } \
 375 }
 376
 377 #define GIT_REFCOUNT_OWN(r, o) { \
 378         ((git_refcount *)(r))->owner = o; \
 379 }
 380
 381 #define GIT_REFCOUNT_OWNER(r) (((git_refcount *)(r))->owner)
 382
 383 #define GIT_REFCOUNT_VAL(r) git_atomic_get(&((git_refcount *)(r))->refcount)
 384
 385
 386 static signed char from_hex[] = {
 387 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 00 */
 388 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 10 */
 389 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 20 */
 390  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, /* 30 */
 391 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 40 */
 392 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 50 */
 393 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 60 */
 394 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 70 */
 395 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 80 */
 396 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 90 */
 397 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a0 */
 398 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* b0 */
 399 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* c0 */
 400 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* d0 */
 401 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* e0 */
 402 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* f0 */
 403 };
 404
 405 GIT_INLINE(int) git__fromhex(char h)
 406 {
 407         return from_hex[(unsigned char) h];
 408 }
 409
 410 GIT_INLINE(int) git__ishex(const char *str)
 411 {
 412         unsigned i;
 413         for (i=0; str[i] != '\0'; i++)
 414                 if (git__fromhex(str[i]) < 0)
 415                         return 0;
 416         return 1;
 417 }
 418
 419 GIT_INLINE(size_t) git__size_t_bitmask(size_t v)
 420 {
 421         v--;
 422         v |= v >> 1;
 423         v |= v >> 2;
 424         v |= v >> 4;
 425         v |= v >> 8;
 426         v |= v >> 16;
 427
 428         return v;
 429 }
 430
 431 GIT_INLINE(size_t) git__size_t_powerof2(size_t v)
 432 {
 433         return git__size_t_bitmask(v) + 1;
 434 }
 435
 436 GIT_INLINE(bool) git__isupper(int c)
 437 {
 438         return (c >= 'A' && c <= 'Z');
 439 }
 440
 441 GIT_INLINE(bool) git__isalpha(int c)
 442 {
 443         return ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'));
 444 }
 445
 446 GIT_INLINE(bool) git__isdigit(int c)
 447 {
 448         return (c >= '0' && c <= '9');
 449 }
 450
 451 GIT_INLINE(bool) git__isspace(int c)
 452 {
 453         return (c == ' ' || c == '\t' || c == '\n' || c == '\f' || c == '\r' || c == '\v');
 454 }
 455
 456 GIT_INLINE(bool) git__isspace_nonlf(int c)
 457 {
 458         return (c == ' ' || c == '\t' || c == '\f' || c == '\r' || c == '\v');
 459 }
 460
 461 GIT_INLINE(bool) git__iswildcard(int c)
 462 {
 463         return (c == '*' || c == '?' || c == '[');
 464 }
 465
 466 /*
 467  * Parse a string value as a boolean, just like Core Git does.
 468  *
 469  * Valid values for true are: 'true', 'yes', 'on'
 470  * Valid values for false are: 'false', 'no', 'off'
 471  */
 472 extern int git__parse_bool(int *out, const char *value);
 473
 474 /*
 475  * Parse a string into a value as a git_time_t.
 476  *
 477  * Sample valid input:
 478  * - "yesterday"
 479  * - "July 17, 2003"
 480  * - "2003-7-17 08:23"
 481  */
 482 extern int git__date_parse(git_time_t *out, const char *date);
 483
 484 /*
 485  * Format a git_time as a RFC2822 string
 486  *
 487  * @param out buffer to store formatted date; a '\\0' terminator will automatically be added.
 488  * @param len size of the buffer; should be atleast `GIT_DATE_RFC2822_SZ` in size;
 489  * @param date the date to be formatted
 490  * @return 0 if successful; -1 on error
 491  */
 492 extern int git__date_rfc2822_fmt(char *out, size_t len, const git_time *date);
 493
 494 /*
 495  * Unescapes a string in-place.
 496  *
 497  * Edge cases behavior:
 498  * - "jackie\" -> "jacky\"
 499  * - "chan\\" -> "chan\"
 500  */
 501 extern size_t git__unescape(char *str);
 502
 503 /*
 504  * Iterate through an UTF-8 string, yielding one
 505  * codepoint at a time.
 506  *
 507  * @param str current position in the string
 508  * @param str_len size left in the string; -1 if the string is NULL-terminated
 509  * @param dst pointer where to store the current codepoint
 510  * @return length in bytes of the read codepoint; -1 if the codepoint was invalid
 511  */
 512 extern int git__utf8_iterate(const uint8_t *str, int str_len, int32_t *dst);
 513
 514 /*
 515  * Safely zero-out memory, making sure that the compiler
 516  * doesn't optimize away the operation.
 517  */
 518 GIT_INLINE(void) git__memzero(void *data, size_t size)
 519 {
 520 #ifdef _MSC_VER
 521         SecureZeroMemory((PVOID)data, size);
 522 #else
 523         volatile uint8_t *scan = (volatile uint8_t *)data;
 524
 525         while (size--)
 526                 *scan++ = 0x0;
 527 #endif
 528 }
 529
 530 #ifdef GIT_WIN32
 531
 532 GIT_INLINE(double) git__timer(void)
 533 {
 534         /* We need the initial tick count to detect if the tick
 535          * count has rolled over. */
 536         static DWORD initial_tick_count = 0;
 537
 538         /* GetTickCount returns the number of milliseconds that have
 539          * elapsed since the system was started. */
 540         DWORD count = GetTickCount();
 541
 542         if(initial_tick_count == 0) {
 543                 initial_tick_count = count;
 544         } else if (count < initial_tick_count) {
 545                 /* The tick count has rolled over - adjust for it. */
 546                 count = (0xFFFFFFFF - initial_tick_count) + count;
 547         }
 548
 549         return (double) count / (double) 1000;
 550 }
 551
 552 #elif __APPLE__
 553
 554 #include <mach/mach_time.h>
 555
 556 GIT_INLINE(double) git__timer(void)
 557 {
 558    uint64_t time = mach_absolute_time();
 559    static double scaling_factor = 0;
 560
 561    if (scaling_factor == 0) {
 562        mach_timebase_info_data_t info;
 563        (void)mach_timebase_info(&info);
 564        scaling_factor = (double)info.numer / (double)info.denom;
 565    }
 566
 567    return (double)time * scaling_factor / 1.0E9;
 568 }
 569
 570 #elif defined(AMIGA)
 571
 572 #include <proto/timer.h>
 573
 574 GIT_INLINE(double) git__timer(void)
 575 {
 576         struct TimeVal tv;
 577         ITimer->GetUpTime(&tv);
 578         return (double)tv.Seconds + (double)tv.Microseconds / 1.0E6;
 579 }
 580
 581 #else
 582
 583 #include <sys/time.h>
 584
 585 GIT_INLINE(double) git__timer(void)
 586 {
 587         struct timespec tp;
 588
 589         if (clock_gettime(CLOCK_MONOTONIC, &tp) == 0) {
 590                 return (double) tp.tv_sec + (double) tp.tv_nsec / 1.0E9;
 591         } else {
 592                 /* Fall back to using gettimeofday */
 593                 struct timeval tv;
 594                 struct timezone tz;
 595                 gettimeofday(&tv, &tz);
 596                 return (double)tv.tv_sec + (double)tv.tv_usec / 1.0E6;
 597         }
 598 }
 599
 600 #endif
 601
 602 #endif /* INCLUDE_util_h__ */