vm/Misc.c

   1 /*
   2  * Copyright (C) 2008 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 /*
  17  * Miscellaneous utility functions.
  18  */
  19 #include "Dalvik.h"
  20
  21 #include <stdlib.h>
  22 #include <stddef.h>
  23 #include <string.h>
  24 #include <strings.h>
  25 #include <ctype.h>
  26 #include <time.h>
  27 #include <sys/time.h>
  28 #include <fcntl.h>
  29 #include <cutils/ashmem.h>
  30 #include <sys/mman.h>
  31
  32 #define ALIGN_UP_TO_PAGE_SIZE(p) \
  33     (((size_t)(p) + (SYSTEM_PAGE_SIZE - 1)) & ~(SYSTEM_PAGE_SIZE - 1))
  34
  35 /*
  36  * Print a hex dump in this format:
  37  *
  38 01234567: 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff  0123456789abcdef\n
  39  *
  40  * If "mode" is kHexDumpLocal, we start at offset zero, and show a full
  41  * 16 bytes on the first line.  If it's kHexDumpMem, we make this look
  42  * like a memory dump, using the actual address, outputting a partial line
  43  * if "vaddr" isn't aligned on a 16-byte boundary.
  44  *
  45  * "priority" and "tag" determine the values passed to the log calls.
  46  *
  47  * Does not use printf() or other string-formatting calls.
  48  */
  49 void dvmPrintHexDumpEx(int priority, const char* tag, const void* vaddr,
  50     size_t length, HexDumpMode mode)
  51 {
  52     static const char gHexDigit[] = "0123456789abcdef";
  53     const unsigned char* addr = vaddr;
  54     char out[77];           /* exact fit */
  55     unsigned int offset;    /* offset to show while printing */
  56     char* hex;
  57     char* asc;
  58     int gap;
  59     //int trickle = 0;
  60
  61     if (mode == kHexDumpLocal)
  62         offset = 0;
  63     else
  64         offset = (int) addr;
  65
  66     memset(out, ' ', sizeof(out)-1);
  67     out[8] = ':';
  68     out[sizeof(out)-2] = '\n';
  69     out[sizeof(out)-1] = '\0';
  70
  71     gap = (int) offset & 0x0f;
  72     while (length) {
  73         unsigned int lineOffset = offset & ~0x0f;
  74         int i, count;
  75
  76         hex = out;
  77         asc = out + 59;
  78
  79         for (i = 0; i < 8; i++) {
  80             *hex++ = gHexDigit[lineOffset >> 28];
  81             lineOffset <<= 4;
  82         }
  83         hex++;
  84         hex++;
  85
  86         count = ((int)length > 16-gap) ? 16-gap : (int)length; /* cap length */
  87         assert(count != 0);
  88         assert(count+gap <= 16);
  89
  90         if (gap) {
  91             /* only on first line */
  92             hex += gap * 3;
  93             asc += gap;
  94         }
  95
  96         for (i = gap ; i < count+gap; i++) {
  97             *hex++ = gHexDigit[*addr >> 4];
  98             *hex++ = gHexDigit[*addr & 0x0f];
  99             hex++;
 100             if (*addr >= 0x20 && *addr < 0x7f /*isprint(*addr)*/)
 101                 *asc++ = *addr;
 102             else
 103                 *asc++ = '.';
 104             addr++;
 105         }
 106         for ( ; i < 16; i++) {
 107             /* erase extra stuff; only happens on last line */
 108             *hex++ = ' ';
 109             *hex++ = ' ';
 110             hex++;
 111             *asc++ = ' ';
 112         }
 113
 114         LOG_PRI(priority, tag, "%s", out);
 115 #if 0 //def HAVE_ANDROID_OS
 116         /*
 117          * We can overrun logcat easily by writing at full speed.  On the
 118          * other hand, we can make Eclipse time out if we're showing
 119          * packet dumps while debugging JDWP.
 120          */
 121         {
 122             if (trickle++ == 8) {
 123                 trickle = 0;
 124                 usleep(20000);
 125             }
 126         }
 127 #endif
 128
 129         gap = 0;
 130         length -= count;
 131         offset += count;
 132     }
 133 }
 134
 135
 136 /*
 137  * Fill out a DebugOutputTarget, suitable for printing to the log.
 138  */
 139 void dvmCreateLogOutputTarget(DebugOutputTarget* target, int priority,
 140     const char* tag)
 141 {
 142     assert(target != NULL);
 143     assert(tag != NULL);
 144
 145     target->which = kDebugTargetLog;
 146     target->data.log.priority = priority;
 147     target->data.log.tag = tag;
 148 }
 149
 150 /*
 151  * Fill out a DebugOutputTarget suitable for printing to a file pointer.
 152  */
 153 void dvmCreateFileOutputTarget(DebugOutputTarget* target, FILE* fp)
 154 {
 155     assert(target != NULL);
 156     assert(fp != NULL);
 157
 158     target->which = kDebugTargetFile;
 159     target->data.file.fp = fp;
 160 }
 161
 162 /*
 163  * Free "target" and any associated data.
 164  */
 165 void dvmFreeOutputTarget(DebugOutputTarget* target)
 166 {
 167     free(target);
 168 }
 169
 170 /*
 171  * Print a debug message, to either a file or the log.
 172  */
 173 void dvmPrintDebugMessage(const DebugOutputTarget* target, const char* format,
 174     ...)
 175 {
 176     va_list args;
 177
 178     va_start(args, format);
 179
 180     switch (target->which) {
 181     case kDebugTargetLog:
 182         LOG_PRI_VA(target->data.log.priority, target->data.log.tag,
 183             format, args);
 184         break;
 185     case kDebugTargetFile:
 186         vfprintf(target->data.file.fp, format, args);
 187         break;
 188     default:
 189         LOGE("unexpected 'which' %d\n", target->which);
 190         break;
 191     }
 192
 193     va_end(args);
 194 }
 195
 196
 197 /*
 198  * Allocate a bit vector with enough space to hold at least the specified
 199  * number of bits.
 200  */
 201 BitVector* dvmAllocBitVector(int startBits, bool expandable)
 202 {
 203     BitVector* bv;
 204     int count;
 205
 206     assert(sizeof(bv->storage[0]) == 4);        /* assuming 32-bit units */
 207     assert(startBits >= 0);
 208
 209     bv = (BitVector*) malloc(sizeof(BitVector));
 210
 211     count = (startBits + 31) >> 5;
 212
 213     bv->storageSize = count;
 214     bv->expandable = expandable;
 215     bv->storage = (u4*) malloc(count * sizeof(u4));
 216     memset(bv->storage, 0x00, count * sizeof(u4));
 217     return bv;
 218 }
 219
 220 /*
 221  * Free a BitVector.
 222  */
 223 void dvmFreeBitVector(BitVector* pBits)
 224 {
 225     if (pBits == NULL)
 226         return;
 227
 228     free(pBits->storage);
 229     free(pBits);
 230 }
 231
 232 /*
 233  * "Allocate" the first-available bit in the bitmap.
 234  *
 235  * This is not synchronized.  The caller is expected to hold some sort of
 236  * lock that prevents multiple threads from executing simultaneously in
 237  * dvmAllocBit/dvmFreeBit.
 238  */
 239 int dvmAllocBit(BitVector* pBits)
 240 {
 241     int word, bit;
 242
 243 retry:
 244     for (word = 0; word < pBits->storageSize; word++) {
 245         if (pBits->storage[word] != 0xffffffff) {
 246             /*
 247              * There are unallocated bits in this word.  Return the first.
 248              */
 249             bit = ffs(~(pBits->storage[word])) -1;
 250             assert(bit >= 0 && bit < 32);
 251             pBits->storage[word] |= 1 << bit;
 252             return (word << 5) | bit;
 253         }
 254     }
 255
 256     /*
 257      * Ran out of space, allocate more if we're allowed to.
 258      */
 259     if (!pBits->expandable)
 260         return -1;
 261
 262     pBits->storage = realloc(pBits->storage,
 263                     (pBits->storageSize + kBitVectorGrowth) * sizeof(u4));
 264     memset(&pBits->storage[pBits->storageSize], 0x00,
 265         kBitVectorGrowth * sizeof(u4));
 266     pBits->storageSize += kBitVectorGrowth;
 267     goto retry;
 268 }
 269
 270 /*
 271  * Mark the specified bit as "set".
 272  *
 273  * Returns "false" if the bit is outside the range of the vector and we're
 274  * not allowed to expand.
 275  */
 276 bool dvmSetBit(BitVector* pBits, int num)
 277 {
 278     assert(num >= 0);
 279     if (num >= pBits->storageSize * (int)sizeof(u4) * 8) {
 280         if (!pBits->expandable)
 281             return false;
 282
 283         int newSize = (num + 31) >> 5;
 284         assert(newSize > pBits->storageSize);
 285         pBits->storage = realloc(pBits->storage, newSize * sizeof(u4));
 286         memset(&pBits->storage[pBits->storageSize], 0x00,
 287             (newSize - pBits->storageSize) * sizeof(u4));
 288         pBits->storageSize = newSize;
 289     }
 290
 291     pBits->storage[num >> 5] |= 1 << (num & 0x1f);
 292     return true;
 293 }
 294
 295 /*
 296  * Mark the specified bit as "clear".
 297  */
 298 void dvmClearBit(BitVector* pBits, int num)
 299 {
 300     assert(num >= 0 && num < (int) pBits->storageSize * (int)sizeof(u4) * 8);
 301
 302     pBits->storage[num >> 5] &= ~(1 << (num & 0x1f));
 303 }
 304
 305 /*
 306  * Mark all bits bit as "clear".
 307  */
 308 void dvmClearAllBits(BitVector* pBits)
 309 {
 310     int count = pBits->storageSize;
 311     memset(pBits->storage, 0, count * sizeof(u4));
 312 }
 313
 314 /*
 315  * Determine whether or not the specified bit is set.
 316  */
 317 bool dvmIsBitSet(const BitVector* pBits, int num)
 318 {
 319     assert(num >= 0 && num < (int) pBits->storageSize * (int)sizeof(u4) * 8);
 320
 321     int val = pBits->storage[num >> 5] & (1 << (num & 0x1f));
 322     return (val != 0);
 323 }
 324
 325 /*
 326  * Count the number of bits that are set.
 327  */
 328 int dvmCountSetBits(const BitVector* pBits)
 329 {
 330     int word;
 331     int count = 0;
 332
 333     for (word = 0; word < pBits->storageSize; word++) {
 334         u4 val = pBits->storage[word];
 335
 336         if (val != 0) {
 337             if (val == 0xffffffff) {
 338                 count += 32;
 339             } else {
 340                 /* count the number of '1' bits */
 341                 while (val != 0) {
 342                     val &= val - 1;
 343                     count++;
 344                 }
 345             }
 346         }
 347     }
 348
 349     return count;
 350 }
 351
 352 /*
 353  * Copy a whole vector to the other. Only do that when the both vectors have
 354  * the same size and attribute.
 355  */
 356 bool dvmCopyBitVector(BitVector *dest, const BitVector *src)
 357 {
 358     if (dest->storageSize != src->storageSize ||
 359         dest->expandable != src->expandable)
 360         return false;
 361     memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
 362     return true;
 363 }
 364
 365 /*
 366  * Intersect two bit vectores and merge the result on top of the pre-existing
 367  * value in the dest vector.
 368  */
 369 bool dvmIntersectBitVectors(BitVector *dest, const BitVector *src1,
 370                             const BitVector *src2)
 371 {
 372     if (dest->storageSize != src1->storageSize ||
 373         dest->storageSize != src2->storageSize ||
 374         dest->expandable != src1->expandable ||
 375         dest->expandable != src2->expandable)
 376         return false;
 377
 378     int i;
 379     for (i = 0; i < dest->storageSize; i++) {
 380         dest->storage[i] |= src1->storage[i] & src2->storage[i];
 381     }
 382     return true;
 383 }
 384
 385 /*
 386  * Return a newly-allocated string in which all occurrences of '.' have
 387  * been changed to '/'.  If we find a '/' in the original string, NULL
 388  * is returned to avoid ambiguity.
 389  */
 390 char* dvmDotToSlash(const char* str)
 391 {
 392     char* newStr = strdup(str);
 393     char* cp = newStr;
 394
 395     if (newStr == NULL)
 396         return NULL;
 397
 398     while (*cp != '\0') {
 399         if (*cp == '/') {
 400             assert(false);
 401             return NULL;
 402         }
 403         if (*cp == '.')
 404             *cp = '/';
 405         cp++;
 406     }
 407
 408     return newStr;
 409 }
 410
 411 /*
 412  * Return a newly-allocated string for the "dot version" of the class
 413  * name for the given type descriptor. That is, The initial "L" and
 414  * final ";" (if any) have been removed and all occurrences of '/'
 415  * have been changed to '.'.
 416  */
 417 char* dvmDescriptorToDot(const char* str)
 418 {
 419     size_t at = strlen(str);
 420     char* newStr;
 421
 422     if ((at >= 2) && (str[0] == 'L') && (str[at - 1] == ';')) {
 423         at -= 2; /* Two fewer chars to copy. */
 424         str++; /* Skip the 'L'. */
 425     }
 426
 427     newStr = malloc(at + 1); /* Add one for the '\0'. */
 428     if (newStr == NULL)
 429         return NULL;
 430
 431     newStr[at] = '\0';
 432
 433     while (at > 0) {
 434         at--;
 435         newStr[at] = (str[at] == '/') ? '.' : str[at];
 436     }
 437
 438     return newStr;
 439 }
 440
 441 /*
 442  * Return a newly-allocated string for the type descriptor
 443  * corresponding to the "dot version" of the given class name. That
 444  * is, non-array names are surrounded by "L" and ";", and all
 445  * occurrences of '.' are changed to '/'.
 446  */
 447 char* dvmDotToDescriptor(const char* str)
 448 {
 449     size_t length = strlen(str);
 450     int wrapElSemi = 0;
 451     char* newStr;
 452     char* at;
 453
 454     if (str[0] != '[') {
 455         length += 2; /* for "L" and ";" */
 456         wrapElSemi = 1;
 457     }
 458
 459     newStr = at = malloc(length + 1); /* + 1 for the '\0' */
 460
 461     if (newStr == NULL) {
 462         return NULL;
 463     }
 464
 465     if (wrapElSemi) {
 466         *(at++) = 'L';
 467     }
 468
 469     while (*str) {
 470         char c = *(str++);
 471         if (c == '.') {
 472             c = '/';
 473         }
 474         *(at++) = c;
 475     }
 476
 477     if (wrapElSemi) {
 478         *(at++) = ';';
 479     }
 480
 481     *at = '\0';
 482     return newStr;
 483 }
 484
 485 /*
 486  * Return a newly-allocated string for the internal-form class name for
 487  * the given type descriptor. That is, the initial "L" and final ";" (if
 488  * any) have been removed.
 489  */
 490 char* dvmDescriptorToName(const char* str)
 491 {
 492     if (str[0] == 'L') {
 493         size_t length = strlen(str) - 1;
 494         char* newStr = malloc(length);
 495
 496         if (newStr == NULL) {
 497             return NULL;
 498         }
 499
 500         strlcpy(newStr, str + 1, length);
 501         return newStr;
 502     }
 503
 504     return strdup(str);
 505 }
 506
 507 /*
 508  * Return a newly-allocated string for the type descriptor for the given
 509  * internal-form class name. That is, a non-array class name will get
 510  * surrounded by "L" and ";", while array names are left as-is.
 511  */
 512 char* dvmNameToDescriptor(const char* str)
 513 {
 514     if (str[0] != '[') {
 515         size_t length = strlen(str);
 516         char* descriptor = malloc(length + 3);
 517
 518         if (descriptor == NULL) {
 519             return NULL;
 520         }
 521
 522         descriptor[0] = 'L';
 523         strcpy(descriptor + 1, str);
 524         descriptor[length + 1] = ';';
 525         descriptor[length + 2] = '\0';
 526
 527         return descriptor;
 528     }
 529
 530     return strdup(str);
 531 }
 532
 533 /*
 534  * Get a notion of the current time, in nanoseconds.  This is meant for
 535  * computing durations (e.g. "operation X took 52nsec"), so the result
 536  * should not be used to get the current date/time.
 537  */
 538 u8 dvmGetRelativeTimeNsec(void)
 539 {
 540 #ifdef HAVE_POSIX_CLOCKS
 541     struct timespec now;
 542     clock_gettime(CLOCK_MONOTONIC, &now);
 543     return (u8)now.tv_sec*1000000000LL + now.tv_nsec;
 544 #else
 545     struct timeval now;
 546     gettimeofday(&now, NULL);
 547     return (u8)now.tv_sec*1000000000LL + now.tv_usec * 1000LL;
 548 #endif
 549 }
 550
 551 /*
 552  * Get the per-thread CPU time, in nanoseconds.
 553  *
 554  * Only useful for time deltas.
 555  */
 556 u8 dvmGetThreadCpuTimeNsec(void)
 557 {
 558 #ifdef HAVE_POSIX_CLOCKS
 559     struct timespec now;
 560     clock_gettime(CLOCK_THREAD_CPUTIME_ID, &now);
 561     return (u8)now.tv_sec*1000000000LL + now.tv_nsec;
 562 #else
 563     return (u8) -1;
 564 #endif
 565 }
 566
 567 /*
 568  * Get the per-thread CPU time, in nanoseconds, for the specified thread.
 569  */
 570 u8 dvmGetOtherThreadCpuTimeNsec(pthread_t thread)
 571 {
 572 #if 0 /*def HAVE_POSIX_CLOCKS*/
 573     int clockId;
 574
 575     if (pthread_getcpuclockid(thread, &clockId) != 0)
 576         return (u8) -1;
 577
 578     struct timespec now;
 579     clock_gettime(clockId, &now);
 580     return (u8)now.tv_sec*1000000000LL + now.tv_nsec;
 581 #else
 582     return (u8) -1;
 583 #endif
 584 }
 585
 586
 587 /*
 588  * Call this repeatedly, with successively higher values for "iteration",
 589  * to sleep for a period of time not to exceed "maxTotalSleep".
 590  *
 591  * For example, when called with iteration==0 we will sleep for a very
 592  * brief time.  On the next call we will sleep for a longer time.  When
 593  * the sum total of all sleeps reaches "maxTotalSleep", this returns false.
 594  *
 595  * The initial start time value for "relStartTime" MUST come from the
 596  * dvmGetRelativeTimeUsec call.  On the device this must come from the
 597  * monotonic clock source, not the wall clock.
 598  *
 599  * This should be used wherever you might be tempted to call sched_yield()
 600  * in a loop.  The problem with sched_yield is that, for a high-priority
 601  * thread, the kernel might not actually transfer control elsewhere.
 602  *
 603  * Returns "false" if we were unable to sleep because our time was up.
 604  */
 605 bool dvmIterativeSleep(int iteration, int maxTotalSleep, u8 relStartTime)
 606 {
 607     const int minSleep = 10000;
 608     u8 curTime;
 609     int curDelay;
 610
 611     /*
 612      * Get current time, and see if we've already exceeded the limit.
 613      */
 614     curTime = dvmGetRelativeTimeUsec();
 615     if (curTime >= relStartTime + maxTotalSleep) {
 616         LOGVV("exsl: sleep exceeded (start=%llu max=%d now=%llu)\n",
 617             relStartTime, maxTotalSleep, curTime);
 618         return false;
 619     }
 620
 621     /*
 622      * Compute current delay.  We're bounded by "maxTotalSleep", so no
 623      * real risk of overflow assuming "usleep" isn't returning early.
 624      * (Besides, 2^30 usec is about 18 minutes by itself.)
 625      *
 626      * For iteration==0 we just call sched_yield(), so the first sleep
 627      * at iteration==1 is actually (minSleep * 2).
 628      */
 629     curDelay = minSleep;
 630     while (iteration-- > 0)
 631         curDelay *= 2;
 632     assert(curDelay > 0);
 633
 634     if (curTime + curDelay >= relStartTime + maxTotalSleep) {
 635         LOGVV("exsl: reduced delay from %d to %d\n",
 636             curDelay, (int) ((relStartTime + maxTotalSleep) - curTime));
 637         curDelay = (int) ((relStartTime + maxTotalSleep) - curTime);
 638     }
 639
 640     if (iteration == 0) {
 641         LOGVV("exsl: yield\n");
 642         sched_yield();
 643     } else {
 644         LOGVV("exsl: sleep for %d\n", curDelay);
 645         usleep(curDelay);
 646     }
 647     return true;
 648 }
 649
 650
 651 /*
 652  * Set the "close on exec" flag so we don't expose our file descriptors
 653  * to processes launched by us.
 654  */
 655 bool dvmSetCloseOnExec(int fd)
 656 {
 657     int flags;
 658
 659     /*
 660      * There's presently only one flag defined, so getting the previous
 661      * value of the fd flags is probably unnecessary.
 662      */
 663     flags = fcntl(fd, F_GETFD);
 664     if (flags < 0) {
 665         LOGW("Unable to get fd flags for fd %d\n", fd);
 666         return false;
 667     }
 668     if (fcntl(fd, F_SETFD, flags | FD_CLOEXEC) < 0) {
 669         LOGW("Unable to set close-on-exec for fd %d\n", fd);
 670         return false;
 671     }
 672     return true;
 673 }
 674
 675 #if (!HAVE_STRLCPY)
 676 /* Implementation of strlcpy() for platforms that don't already have it. */
 677 size_t strlcpy(char *dst, const char *src, size_t size) {
 678     size_t srcLength = strlen(src);
 679     size_t copyLength = srcLength;
 680
 681     if (srcLength > (size - 1)) {
 682         copyLength = size - 1;
 683     }
 684
 685     if (size != 0) {
 686         strncpy(dst, src, copyLength);
 687         dst[copyLength] = '\0';
 688     }
 689
 690     return srcLength;
 691 }
 692 #endif
 693
 694 /*
 695  *  Allocates a memory region using ashmem and mmap, initialized to
 696  *  zero.  Actual allocation rounded up to page multiple.  Returns
 697  *  NULL on failure.
 698  */
 699 void *dvmAllocRegion(size_t size, int prot, const char *name) {
 700     void *base;
 701     int fd, ret;
 702
 703     size = ALIGN_UP_TO_PAGE_SIZE(size);
 704     fd = ashmem_create_region(name, size);
 705     if (fd == -1) {
 706         return NULL;
 707     }
 708     base = mmap(NULL, size, prot, MAP_PRIVATE, fd, 0);
 709     ret = close(fd);
 710     if (base == MAP_FAILED) {
 711         return NULL;
 712     }
 713     if (ret == -1) {
 714         return NULL;
 715     }
 716     return base;
 717 }
 718
 719 /* documented in header file */
 720 const char* dvmPathToAbsolutePortion(const char* path) {
 721     if (path == NULL) {
 722         return NULL;
 723     }
 724
 725     if (path[0] == '/') {
 726         /* It's a regular absolute path. Return it. */
 727         return path;
 728     }
 729
 730     const char* sentinel = strstr(path, "/./");
 731
 732     if (sentinel != NULL) {
 733         /* It's got the sentinel. Return a pointer to the second slash. */
 734         return sentinel + 2;
 735     }
 736
 737     return NULL;
 738 }