js/src/jsutil.cpp

   1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is Mozilla Communicator client code, released
  17  * March 31, 1998.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * Netscape Communications Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 1998
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *   IBM Corp.
  26  *
  27  * Alternatively, the contents of this file may be used under the terms of
  28  * either of the GNU General Public License Version 2 or later (the "GPL"),
  29  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  30  * in which case the provisions of the GPL or the LGPL are applicable instead
  31  * of those above. If you wish to allow use of your version of this file only
  32  * under the terms of either the GPL or the LGPL, and not to allow others to
  33  * use your version of this file under the terms of the MPL, indicate your
  34  * decision by deleting the provisions above and replace them with the notice
  35  * and other provisions required by the GPL or the LGPL. If you do not delete
  36  * the provisions above, a recipient may use your version of this file under
  37  * the terms of any one of the MPL, the GPL or the LGPL.
  38  *
  39  * ***** END LICENSE BLOCK ***** */
  40
  41 /*
  42  * PR assertion checker.
  43  */
  44 #include "jsstddef.h"
  45 #include <stdio.h>
  46 #include <stdlib.h>
  47 #include "jstypes.h"
  48 #include "jsutil.h"
  49
  50 #ifdef WIN32
  51 #    include <windows.h>
  52 #endif
  53
  54 JS_PUBLIC_API(void) JS_Assert(const char *s, const char *file, JSIntn ln)
  55 {
  56     fprintf(stderr, "Assertion failure: %s, at %s:%d\n", s, file, ln);
  57 #if defined(WIN32)
  58     DebugBreak();
  59     exit(3);
  60 #elif defined(XP_OS2) || (defined(__GNUC__) && defined(__i386))
  61     asm("int $3");
  62 #endif
  63     abort();
  64 }
  65
  66 #ifdef JS_BASIC_STATS
  67
  68 #include <math.h>
  69 #include <string.h>
  70 #include "jscompat.h"
  71 #include "jsbit.h"
  72
  73 /*
  74  * Histogram bins count occurrences of values <= the bin label, as follows:
  75  *
  76  *   linear:  0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10 or more
  77  *     2**x:  0,   1,   2,   4,   8,  16,  32,  64, 128, 256, 512 or more
  78  *    10**x:  0,   1,  10, 100, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9 or more
  79  *
  80  * We wish to count occurrences of 0 and 1 values separately, always.
  81  */
  82 static uint32
  83 BinToVal(uintN logscale, uintN bin)
  84 {
  85     JS_ASSERT(bin <= 10);
  86     if (bin <= 1 || logscale == 0)
  87         return bin;
  88     --bin;
  89     if (logscale == 2)
  90         return JS_BIT(bin);
  91     JS_ASSERT(logscale == 10);
  92     return (uint32) pow(10.0, (double) bin);
  93 }
  94
  95 static uintN
  96 ValToBin(uintN logscale, uint32 val)
  97 {
  98     uintN bin;
  99
 100     if (val <= 1)
 101         return val;
 102     bin = (logscale == 10)
 103           ? (uintN) ceil(log10((double) val))
 104           : (logscale == 2)
 105           ? (uintN) JS_CeilingLog2(val)
 106           : val;
 107     return JS_MIN(bin, 10);
 108 }
 109
 110 void
 111 JS_BasicStatsAccum(JSBasicStats *bs, uint32 val)
 112 {
 113     uintN oldscale, newscale, bin;
 114     double mean;
 115
 116     ++bs->num;
 117     if (bs->max < val)
 118         bs->max = val;
 119     bs->sum += val;
 120     bs->sqsum += (double)val * val;
 121
 122     oldscale = bs->logscale;
 123     if (oldscale != 10) {
 124         mean = bs->sum / bs->num;
 125         if (bs->max > 16 && mean > 8) {
 126             newscale = (bs->max > 1e6 && mean > 1000) ? 10 : 2;
 127             if (newscale != oldscale) {
 128                 uint32 newhist[11], newbin;
 129
 130                 memset(newhist, 0, sizeof newhist);
 131                 for (bin = 0; bin <= 10; bin++) {
 132                     newbin = ValToBin(newscale, BinToVal(oldscale, bin));
 133                     newhist[newbin] += bs->hist[bin];
 134                 }
 135                 memcpy(bs->hist, newhist, sizeof bs->hist);
 136                 bs->logscale = newscale;
 137             }
 138         }
 139     }
 140
 141     bin = ValToBin(bs->logscale, val);
 142     ++bs->hist[bin];
 143 }
 144
 145 double
 146 JS_MeanAndStdDev(uint32 num, double sum, double sqsum, double *sigma)
 147 {
 148     double var;
 149
 150     if (num == 0 || sum == 0) {
 151         *sigma = 0;
 152         return 0;
 153     }
 154
 155     var = num * sqsum - sum * sum;
 156     if (var < 0 || num == 1)
 157         var = 0;
 158     else
 159         var /= (double)num * (num - 1);
 160
 161     /* Windows says sqrt(0.0) is "-1.#J" (?!) so we must test. */
 162     *sigma = (var != 0) ? sqrt(var) : 0;
 163     return sum / num;
 164 }
 165
 166 void
 167 JS_DumpBasicStats(JSBasicStats *bs, const char *title, FILE *fp)
 168 {
 169     double mean, sigma;
 170
 171     mean = JS_MeanAndStdDevBS(bs, &sigma);
 172     fprintf(fp, "\nmean %s %g, std. deviation %g, max %lu\n",
 173             title, mean, sigma, (unsigned long) bs->max);
 174     JS_DumpHistogram(bs, fp);
 175 }
 176
 177 void
 178 JS_DumpHistogram(JSBasicStats *bs, FILE *fp)
 179 {
 180     uintN bin;
 181     uint32 cnt, max, prev, val, i;
 182     double sum, mean;
 183
 184     for (bin = 0, max = 0, sum = 0; bin <= 10; bin++) {
 185         cnt = bs->hist[bin];
 186         if (max < cnt)
 187             max = cnt;
 188         sum += cnt;
 189     }
 190     mean = sum / cnt;
 191     for (bin = 0, prev = 0; bin <= 10; bin++, prev = val) {
 192         val = BinToVal(bs->logscale, bin);
 193         cnt = bs->hist[bin];
 194         if (prev + 1 >= val)
 195             fprintf(fp, "        [%6u]", val);
 196         else
 197             fprintf(fp, "[%6u, %6u]", prev + 1, val);
 198         fprintf(fp, "%s %8u ", (bin == 10) ? "+" : ":", cnt);
 199         if (cnt != 0) {
 200             if (max > 1e6 && mean > 1e3)
 201                 cnt = (uint32) ceil(log10((double) cnt));
 202             else if (max > 16 && mean > 8)
 203                 cnt = JS_CeilingLog2(cnt);
 204             for (i = 0; i < cnt; i++)
 205                 putc('*', fp);
 206         }
 207         putc('\n', fp);
 208     }
 209 }
 210
 211 #endif /* JS_BASIC_STATS */
 212
 213 #if defined DEBUG_notme && defined XP_UNIX
 214
 215 #define __USE_GNU 1
 216 #include <dlfcn.h>
 217 #include <string.h>
 218 #include "jshash.h"
 219 #include "jsprf.h"
 220
 221 JSCallsite js_calltree_root = {0, NULL, NULL, 0, NULL, NULL, NULL, NULL};
 222
 223 static JSCallsite *
 224 CallTree(void **bp)
 225 {
 226     void **bpup, **bpdown, *pc;
 227     JSCallsite *parent, *site, **csp;
 228     Dl_info info;
 229     int ok, offset;
 230     const char *symbol;
 231     char *method;
 232
 233     /* Reverse the stack frame list to avoid recursion. */
 234     bpup = NULL;
 235     for (;;) {
 236         bpdown = (void**) bp[0];
 237         bp[0] = (void*) bpup;
 238         if ((void**) bpdown[0] < bpdown)
 239             break;
 240         bpup = bp;
 241         bp = bpdown;
 242     }
 243
 244     /* Reverse the stack again, finding and building a path in the tree. */
 245     parent = &js_calltree_root;
 246     do {
 247         bpup = (void**) bp[0];
 248         bp[0] = (void*) bpdown;
 249         pc = bp[1];
 250
 251         csp = &parent->kids;
 252         while ((site = *csp) != NULL) {
 253             if (site->pc == (uint32)pc) {
 254                 /* Put the most recently used site at the front of siblings. */
 255                 *csp = site->siblings;
 256                 site->siblings = parent->kids;
 257                 parent->kids = site;
 258
 259                 /* Site already built -- go up the stack. */
 260                 goto upward;
 261             }
 262             csp = &site->siblings;
 263         }
 264
 265         /* Check for recursion: see if pc is on our ancestor line. */
 266         for (site = parent; site; site = site->parent) {
 267             if (site->pc == (uint32)pc)
 268                 goto upward;
 269         }
 270
 271         /*
 272          * Not in tree at all: let's find our symbolic callsite info.
 273          * XXX static syms are masked by nearest lower global
 274          */
 275         info.dli_fname = info.dli_sname = NULL;
 276         ok = dladdr(pc, &info);
 277         if (ok < 0) {
 278             fprintf(stderr, "dladdr failed!\n");
 279             return NULL;
 280         }
 281
 282 /* XXXbe sub 0x08040000? or something, see dbaron bug with tenthumbs comment */
 283         symbol = info.dli_sname;
 284         offset = (char*)pc - (char*)info.dli_fbase;
 285         method = symbol
 286                  ? strdup(symbol)
 287                  : JS_smprintf("%s+%X",
 288                                info.dli_fname ? info.dli_fname : "main",
 289                                offset);
 290         if (!method)
 291             return NULL;
 292
 293         /* Create a new callsite record. */
 294         site = (JSCallsite *) malloc(sizeof(JSCallsite));
 295         if (!site)
 296             return NULL;
 297
 298         /* Insert the new site into the tree. */
 299         site->pc = (uint32)pc;
 300         site->name = method;
 301         site->library = info.dli_fname;
 302         site->offset = offset;
 303         site->parent = parent;
 304         site->siblings = parent->kids;
 305         parent->kids = site;
 306         site->kids = NULL;
 307
 308       upward:
 309         parent = site;
 310         bpdown = bp;
 311         bp = bpup;
 312     } while (bp);
 313
 314     return site;
 315 }
 316
 317 JSCallsite *
 318 JS_Backtrace(int skip)
 319 {
 320     void **bp, **bpdown;
 321
 322     /* Stack walking code adapted from Kipp's "leaky". */
 323 #if defined(__i386)
 324     __asm__( "movl %%ebp, %0" : "=g"(bp));
 325 #elif defined(__x86_64__)
 326     __asm__( "movq %%rbp, %0" : "=g"(bp));
 327 #else
 328     /*
 329      * It would be nice if this worked uniformly, but at least on i386 and
 330      * x86_64, it stopped working with gcc 4.1, because it points to the
 331      * end of the saved registers instead of the start.
 332      */
 333     bp = (void**) __builtin_frame_address(0);
 334 #endif
 335     while (--skip >= 0) {
 336         bpdown = (void**) *bp++;
 337         if (bpdown < bp)
 338             break;
 339         bp = bpdown;
 340     }
 341
 342     return CallTree(bp);
 343 }
 344
 345 #endif /* DEBUG_notme && XP_UNIX */