/*
 * Copyright (c) 2018, 2025, Oracle and/or its affiliates. All rights reserved.
 * Copyright (c) 2018, Google and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "logging/log.hpp"
#include "logging/logTag.hpp"
#include "prims/jvmtiExport.hpp"
#include "runtime/atomic.hpp"
#include "runtime/handles.inline.hpp"
#include "runtime/sharedRuntime.hpp"
#include "runtime/threadHeapSampler.hpp"
#include "utilities/checkedCast.hpp"

// Cheap random number generator.
uint64_t ThreadHeapSampler::_rnd;
// Default is 512kb.
volatile int ThreadHeapSampler::_sampling_interval = 512 * 1024;

// Statics for the fast log
static const int FastLogNumBits = 10;
static const int FastLogCount = 1 << FastLogNumBits;
static const int FastLogMask = FastLogCount - 1;
static const double log_table[FastLogCount] = {
  0.000704269011247, 0.002111776479852, 0.003517912108602, 0.004922678569045,
  0.006326078524934, 0.007728114632254, 0.009128789539256, 0.010528105886485,
  0.011926066306808, 0.013322673425448, 0.014717929860010, 0.016111838220512,
  0.017504401109415, 0.018895621121649, 0.020285500844648, 0.021674042858370,
  0.023061249735335, 0.024447124040647, 0.025831668332026, 0.027214885159835,
  0.028596777067108, 0.029977346589579, 0.031356596255709, 0.032734528586714,
  0.034111146096593, 0.035486451292154, 0.036860446673046, 0.038233134731779,
  0.039604517953758, 0.040974598817306, 0.042343379793691, 0.043710863347156,
  0.045077051934941, 0.046441948007312, 0.047805554007589, 0.049167872372170,
  0.050528905530555, 0.051888655905378, 0.053247125912426, 0.054604317960672,
  0.055960234452294, 0.057314877782703, 0.058668250340571, 0.060020354507853,
  0.061371192659811, 0.062720767165044, 0.064069080385509, 0.065416134676548,
  0.066761932386908, 0.068106475858773, 0.069449767427783, 0.070791809423061,
  0.072132604167234, 0.073472153976460, 0.074810461160454, 0.076147528022505,
  0.077483356859507, 0.078817949961979, 0.080151309614087, 0.081483438093674,
  0.082814337672274, 0.084144010615144, 0.085472459181283, 0.086799685623453,
  0.088125692188207, 0.089450481115907, 0.090774054640751, 0.092096414990791,
  0.093417564387961, 0.094737505048093, 0.096056239180946, 0.097373768990222,
  0.098690096673594, 0.100005224422721, 0.101319154423276, 0.102631888854968,
  0.103943429891557, 0.105253779700883, 0.106562940444883, 0.107870914279614,
  0.109177703355275, 0.110483309816226, 0.111787735801012, 0.113090983442381,
  0.114393054867307, 0.115693952197011, 0.116993677546981, 0.118292233026990,
  0.119589620741122, 0.120885842787790, 0.122180901259752, 0.123474798244141,
  0.124767535822473, 0.126059116070680, 0.127349541059119, 0.128638812852598,
  0.129926933510393, 0.131213905086272, 0.132499729628509, 0.133784409179907,
  0.135067945777817, 0.136350341454156, 0.137631598235428, 0.138911718142743,
  0.140190703191836, 0.141468555393084, 0.142745276751529, 0.144020869266892,
  0.145295334933597, 0.146568675740786, 0.147840893672337, 0.149111990706888,
  0.150381968817848, 0.151650829973421, 0.152918576136622, 0.154185209265297,
  0.155450731312137, 0.156715144224702, 0.157978449945432, 0.159240650411673,
  0.160501747555687, 0.161761743304675, 0.163020639580794, 0.164278438301170,
  0.165535141377924, 0.166790750718180, 0.168045268224090, 0.169298695792846,
  0.170551035316700, 0.171802288682983, 0.173052457774115, 0.174301544467631,
  0.175549550636190, 0.176796478147599, 0.178042328864822, 0.179287104646004,
  0.180530807344482, 0.181773438808808, 0.183015000882756, 0.184255495405349,
  0.185494924210866, 0.186733289128866, 0.187970591984199, 0.189206834597024,
  0.190442018782825, 0.191676146352428, 0.192909219112013, 0.194141238863136,
  0.195372207402739, 0.196602126523170, 0.197830998012197, 0.199058823653021,
  0.200285605224298, 0.201511344500146, 0.202736043250167, 0.203959703239463,
  0.205182326228643, 0.206403913973847, 0.207624468226758, 0.208843990734615,
  0.210062483240231, 0.211279947482008, 0.212496385193948, 0.213711798105673,
  0.214926187942435, 0.216139556425135, 0.217351905270334, 0.218563236190271,
  0.219773550892874, 0.220982851081777, 0.222191138456332, 0.223398414711628,
  0.224604681538499, 0.225809940623543, 0.227014193649133, 0.228217442293435,
  0.229419688230416, 0.230620933129866, 0.231821178657404, 0.233020426474497,
  0.234218678238471, 0.235415935602526, 0.236612200215751, 0.237807473723136,
  0.239001757765583, 0.240195053979925, 0.241387363998937, 0.242578689451346,
  0.243769031961852, 0.244958393151134, 0.246146774635865, 0.247334178028729,
  0.248520604938429, 0.249706056969705, 0.250890535723341, 0.252074042796184,
  0.253256579781154, 0.254438148267256, 0.255618749839596, 0.256798386079390,
  0.257977058563978, 0.259154768866840, 0.260331518557602, 0.261507309202055,
  0.262682142362165, 0.263856019596082, 0.265028942458160, 0.266200912498961,
  0.267371931265274, 0.268542000300123, 0.269711121142782, 0.270879295328784,
  0.272046524389938, 0.273212809854334, 0.274378153246363, 0.275542556086722,
  0.276706019892431, 0.277868546176841, 0.279030136449649, 0.280190792216907,
  0.281350514981036, 0.282509306240837, 0.283667167491501, 0.284824100224623,
  0.285980105928212, 0.287135186086704, 0.288289342180970, 0.289442575688332,
  0.290594888082571, 0.291746280833939, 0.292896755409173, 0.294046313271500,
  0.295194955880655, 0.296342684692889, 0.297489501160979, 0.298635406734241,
  0.299780402858540, 0.300924490976300, 0.302067672526519, 0.303209948944775,
  0.304351321663238, 0.305491792110684, 0.306631361712501, 0.307770031890703,
  0.308907804063939, 0.310044679647506, 0.311180660053355, 0.312315746690106,
  0.313449940963058, 0.314583244274195, 0.315715658022202, 0.316847183602472,
  0.317977822407119, 0.319107575824984, 0.320236445241649, 0.321364432039446,
  0.322491537597468, 0.323617763291577, 0.324743110494416, 0.325867580575418,
  0.326991174900817, 0.328113894833656, 0.329235741733800, 0.330356716957943,
  0.331476821859620, 0.332596057789214, 0.333714426093970, 0.334831928118000,
  0.335948565202297, 0.337064338684741, 0.338179249900111, 0.339293300180094,
  0.340406490853295, 0.341518823245243, 0.342630298678407, 0.343740918472201,
  0.344850683942991, 0.345959596404112, 0.347067657165871, 0.348174867535556,
  0.349281228817452, 0.350386742312842, 0.351491409320021, 0.352595231134304,
  0.353698209048035, 0.354800344350596, 0.355901638328417, 0.357002092264984,
  0.358101707440847, 0.359200485133632, 0.360298426618046, 0.361395533165889,
  0.362491806046063, 0.363587246524577, 0.364681855864560, 0.365775635326268,
  0.366868586167093, 0.367960709641570, 0.369052007001388, 0.370142479495399,
  0.371232128369622, 0.372320954867259, 0.373408960228696, 0.374496145691516,
  0.375582512490507, 0.376668061857668, 0.377752795022220, 0.378836713210614,
  0.379919817646538, 0.381002109550926, 0.382083590141966, 0.383164260635110,
  0.384244122243078, 0.385323176175872, 0.386401423640778, 0.387478865842379,
  0.388555503982561, 0.389631339260521, 0.390706372872775, 0.391780606013166,
  0.392854039872873, 0.393926675640417, 0.394998514501672, 0.396069557639868,
  0.397139806235604, 0.398209261466852, 0.399277924508967, 0.400345796534695,
  0.401412878714178, 0.402479172214964, 0.403544678202014, 0.404609397837712,
  0.405673332281866, 0.406736482691724, 0.407798850221975, 0.408860436024760,
  0.409921241249679, 0.410981267043796, 0.412040514551651, 0.413098984915263,
  0.414156679274141, 0.415213598765286, 0.416269744523207, 0.417325117679919,
  0.418379719364956, 0.419433550705378, 0.420486612825775, 0.421538906848277,
  0.422590433892561, 0.423641195075856, 0.424691191512953, 0.425740424316211,
  0.426788894595561, 0.427836603458520, 0.428883552010191, 0.429929741353273,
  0.430975172588069, 0.432019846812492, 0.433063765122069, 0.434106928609955,
  0.435149338366930, 0.436190995481417, 0.437231901039479, 0.438272056124831,
  0.439311461818846, 0.440350119200562, 0.441388029346687, 0.442425193331607,
  0.443461612227394, 0.444497287103809, 0.445532219028312, 0.446566409066067,
  0.447599858279950, 0.448632567730552, 0.449664538476192, 0.450695771572915,
  0.451726268074506, 0.452756029032494, 0.453785055496155, 0.454813348512524,
  0.455840909126398, 0.456867738380343, 0.457893837314700, 0.458919206967592,
  0.459943848374931, 0.460967762570422, 0.461990950585571, 0.463013413449693,
  0.464035152189912, 0.465056167831175, 0.466076461396253, 0.467096033905747,
  0.468114886378099, 0.469133019829591, 0.470150435274359, 0.471167133724392,
  0.472183116189541, 0.473198383677527, 0.474212937193944, 0.475226777742266,
  0.476239906323851, 0.477252323937953, 0.478264031581720, 0.479275030250205,
  0.480285320936372, 0.481294904631098, 0.482303782323183, 0.483311954999353,
  0.484319423644267, 0.485326189240524, 0.486332252768664, 0.487337615207182,
  0.488342277532524, 0.489346240719100, 0.490349505739287, 0.491352073563435,
  0.492353945159870, 0.493355121494907, 0.494355603532845, 0.495355392235982,
  0.496354488564616, 0.497352893477049, 0.498350607929600, 0.499347632876599,
  0.500343969270403, 0.501339618061397, 0.502334580197997, 0.503328856626662,
  0.504322448291891, 0.505315356136237, 0.506307581100306, 0.507299124122766,
  0.508289986140348, 0.509280168087859, 0.510269670898178, 0.511258495502268,
  0.512246642829179, 0.513234113806053, 0.514220909358129, 0.515207030408751,
  0.516192477879367, 0.517177252689541, 0.518161355756956, 0.519144787997414,
  0.520127550324851, 0.521109643651332, 0.522091068887064, 0.523071826940395,
  0.524051918717823, 0.525031345124000, 0.526010107061737, 0.526988205432007,
  0.527965641133954, 0.528942415064895, 0.529918528120324, 0.530893981193921,
  0.531868775177554, 0.532842910961282, 0.533816389433366, 0.534789211480267,
  0.535761377986656, 0.536732889835414, 0.537703747907644, 0.538673953082668,
  0.539643506238036, 0.540612408249530, 0.541580659991169, 0.542548262335212,
  0.543515216152167, 0.544481522310791, 0.545447181678094, 0.546412195119352,
  0.547376563498101, 0.548340287676148, 0.549303368513575, 0.550265806868740,
  0.551227603598288, 0.552188759557150, 0.553149275598548, 0.554109152574003,
  0.555068391333337, 0.556026992724677, 0.556984957594463, 0.557942286787447,
  0.558898981146702, 0.559855041513625, 0.560810468727941, 0.561765263627707,
  0.562719427049319, 0.563672959827513, 0.564625862795372, 0.565578136784329,
  0.566529782624171, 0.567480801143044, 0.568431193167460, 0.569380959522294,
  0.570330101030798, 0.571278618514596, 0.572226512793695, 0.573173784686486,
  0.574120435009748, 0.575066464578656, 0.576011874206780, 0.576956664706092,
  0.577900836886970, 0.578844391558203, 0.579787329526992, 0.580729651598958,
  0.581671358578144, 0.582612451267020, 0.583552930466485, 0.584492796975875,
  0.585432051592962, 0.586370695113965, 0.587308728333545, 0.588246152044817,
  0.589182967039351, 0.590119174107175, 0.591054774036780, 0.591989767615125,
  0.592924155627638, 0.593857938858223, 0.594791118089265, 0.595723694101627,
  0.596655667674663, 0.597587039586216, 0.598517810612622, 0.599447981528719,
  0.600377553107844, 0.601306526121841, 0.602234901341064, 0.603162679534382,
  0.604089861469180, 0.605016447911364, 0.605942439625368, 0.606867837374152,
  0.607792641919210, 0.608716854020573, 0.609640474436812, 0.610563503925040,
  0.611485943240922, 0.612407793138670, 0.613329054371054, 0.614249727689401,
  0.615169813843603, 0.616089313582115, 0.617008227651965, 0.617926556798751,
  0.618844301766652, 0.619761463298424, 0.620678042135410, 0.621594039017540,
  0.622509454683335, 0.623424289869911, 0.624338545312985, 0.625252221746873,
  0.626165319904499, 0.627077840517394, 0.627989784315704, 0.628901152028190,
  0.629811944382234, 0.630722162103839, 0.631631805917638, 0.632540876546891,
  0.633449374713493, 0.634357301137976, 0.635264656539513, 0.636171441635921,
  0.637077657143663, 0.637983303777853, 0.638888382252261, 0.639792893279312,
  0.640696837570094, 0.641600215834357, 0.642503028780520, 0.643405277115674,
  0.644306961545581, 0.645208082774684, 0.646108641506103, 0.647008638441647,
  0.647908074281808, 0.648806949725770, 0.649705265471412, 0.650603022215310,
  0.651500220652738, 0.652396861477678, 0.653292945382815, 0.654188473059545,
  0.655083445197979, 0.655977862486942, 0.656871725613981, 0.657765035265364,
  0.658657792126085, 0.659549996879870, 0.660441650209173, 0.661332752795187,
  0.662223305317840, 0.663113308455806, 0.664002762886501, 0.664891669286088,
  0.665780028329483, 0.666667840690356, 0.667555107041132, 0.668441828052998,
  0.669328004395903, 0.670213636738564, 0.671098725748465, 0.671983272091864,
  0.672867276433793, 0.673750739438063, 0.674633661767266, 0.675516044082778,
  0.676397887044763, 0.677279191312175, 0.678159957542760, 0.679040186393061,
  0.679919878518420, 0.680799034572981, 0.681677655209692, 0.682555741080310,
  0.683433292835402, 0.684310311124349, 0.685186796595348, 0.686062749895414,
  0.686938171670387, 0.687813062564931, 0.688687423222536, 0.689561254285525,
  0.690434556395054, 0.691307330191115, 0.692179576312539, 0.693051295396999,
  0.693922488081015, 0.694793154999950, 0.695663296788022, 0.696532914078300,
  0.697402007502708, 0.698270577692031, 0.699138625275914, 0.700006150882866,
  0.700873155140263, 0.701739638674351, 0.702605602110248, 0.703471046071947,
  0.704335971182319, 0.705200378063116, 0.706064267334970, 0.706927639617403,
  0.707790495528823, 0.708652835686530, 0.709514660706716, 0.710375971204471,
  0.711236767793784, 0.712097051087546, 0.712956821697550, 0.713816080234498,
  0.714674827308002, 0.715533063526583, 0.716390789497679, 0.717248005827646,
  0.718104713121757, 0.718960911984210, 0.719816603018127, 0.720671786825556,
  0.721526464007477, 0.722380635163802, 0.723234300893377, 0.724087461793988,
  0.724940118462359, 0.725792271494157, 0.726643921483994, 0.727495069025431,
  0.728345714710977, 0.729195859132094, 0.730045502879201, 0.730894646541672,
  0.731743290707842, 0.732591435965008, 0.733439082899433, 0.734286232096346,
  0.735132884139946, 0.735979039613404, 0.736824699098865, 0.737669863177453,
  0.738514532429268, 0.739358707433394, 0.740202388767900, 0.741045577009838,
  0.741888272735251, 0.742730476519174, 0.743572188935634, 0.744413410557655,
  0.745254141957257, 0.746094383705463, 0.746934136372297, 0.747773400526791,
  0.748612176736981, 0.749450465569916, 0.750288267591654, 0.751125583367269,
  0.751962413460854, 0.752798758435516, 0.753634618853387, 0.754469995275621,
  0.755304888262399, 0.756139298372928, 0.756973226165448, 0.757806672197228,
  0.758639637024576, 0.759472121202833, 0.760304125286382, 0.761135649828646,
  0.761966695382092, 0.762797262498232, 0.763627351727628, 0.764456963619890,
  0.765286098723682, 0.766114757586723, 0.766942940755785, 0.767770648776705,
  0.768597882194375, 0.769424641552754, 0.770250927394865, 0.771076740262799,
  0.771902080697716, 0.772726949239850, 0.773551346428504, 0.774375272802063,
  0.775198728897986, 0.776021715252813, 0.776844232402167, 0.777666280880755,
  0.778487861222371, 0.779308973959898, 0.780129619625307, 0.780949798749665,
  0.781769511863131, 0.782588759494964, 0.783407542173518, 0.784225860426252,
  0.785043714779724, 0.785861105759600, 0.786678033890652, 0.787494499696761,
  0.788310503700919, 0.789126046425230, 0.789941128390916, 0.790755750118313,
  0.791569912126878, 0.792383614935189, 0.793196859060945, 0.794009645020972,
  0.794821973331222, 0.795633844506778, 0.796445259061850, 0.797256217509785,
  0.798066720363063, 0.798876768133299, 0.799686361331250, 0.800495500466812,
  0.801304186049023, 0.802112418586066, 0.802920198585270, 0.803727526553114,
  0.804534402995225, 0.805340828416384, 0.806146803320525, 0.806952328210736,
  0.807757403589267, 0.808562029957525, 0.809366207816078, 0.810169937664658,
  0.810973220002164, 0.811776055326660, 0.812578444135380, 0.813380386924727,
  0.814181884190280, 0.814982936426790, 0.815783544128185, 0.816583707787570,
  0.817383427897233, 0.818182704948640, 0.818981539432443, 0.819779931838480,
  0.820577882655774, 0.821375392372539, 0.822172461476178, 0.822969090453287,
  0.823765279789659, 0.824561029970280, 0.825356341479334, 0.826151214800207,
  0.826945650415485, 0.827739648806957, 0.828533210455617, 0.829326335841667,
  0.830119025444515, 0.830911279742782, 0.831703099214300, 0.832494484336112,
  0.833285435584481, 0.834075953434884, 0.834866038362018, 0.835655690839800,
  0.836444911341368, 0.837233700339087, 0.838022058304546, 0.838809985708559,
  0.839597483021174, 0.840384550711666, 0.841171189248543, 0.841957399099547,
  0.842743180731658, 0.843528534611089, 0.844313461203296, 0.845097960972975,
  0.845882034384061, 0.846665681899738, 0.847448903982432, 0.848231701093818,
  0.849014073694819, 0.849796022245609, 0.850577547205614, 0.851358649033513,
  0.852139328187243, 0.852919585123995, 0.853699420300221, 0.854478834171630,
  0.855257827193196, 0.856036399819156, 0.856814552503010, 0.857592285697526,
  0.858369599854740, 0.859146495425959, 0.859922972861758, 0.860699032611988,
  0.861474675125773, 0.862249900851513, 0.863024710236886, 0.863799103728850,
  0.864573081773641, 0.865346644816780, 0.866119793303070, 0.866892527676600,
  0.867664848380745, 0.868436755858169, 0.869208250550826, 0.869979332899962,
  0.870750003346114, 0.871520262329114, 0.872290110288090, 0.873059547661470,
  0.873828574886976, 0.874597192401634, 0.875365400641771, 0.876133200043017,
  0.876900591040306, 0.877667574067881, 0.878434149559290, 0.879200317947393,
  0.879966079664357, 0.880731435141664, 0.881496384810110, 0.882260929099804,
  0.883025068440173, 0.883788803259962, 0.884552133987234, 0.885315061049376,
  0.886077584873094, 0.886839705884419, 0.887601424508708, 0.888362741170644,
  0.889123656294237, 0.889884170302829, 0.890644283619089, 0.891403996665022,
  0.892163309861966, 0.892922223630591, 0.893680738390908, 0.894438854562262,
  0.895196572563340, 0.895953892812168, 0.896710815726115, 0.897467341721893,
  0.898223471215558, 0.898979204622514, 0.899734542357511, 0.900489484834649,
  0.901244032467376, 0.901998185668496, 0.902751944850161, 0.903505310423880,
  0.904258282800518, 0.905010862390296, 0.905763049602793, 0.906514844846950,
  0.907266248531065, 0.908017261062803, 0.908767882849189, 0.909518114296615,
  0.910267955810839, 0.911017407796985, 0.911766470659550, 0.912515144802397,
  0.913263430628762, 0.914011328541254, 0.914758838941858, 0.915505962231931,
  0.916252698812210, 0.916999049082807, 0.917745013443216, 0.918490592292311,
  0.919235786028347, 0.919980595048962, 0.920725019751180, 0.921469060531410,
  0.922212717785448, 0.922955991908478, 0.923698883295072, 0.924441392339197,
  0.925183519434208, 0.925925264972856, 0.926666629347283, 0.927407612949032,
  0.928148216169037, 0.928888439397636, 0.929628283024562, 0.930367747438952,
  0.931106833029342, 0.931845540183673, 0.932583869289291, 0.933321820732945,
  0.934059394900794, 0.934796592178403, 0.935533412950747, 0.936269857602210,
  0.937005926516589, 0.937741620077096, 0.938476938666352, 0.939211882666397,
  0.939946452458687, 0.940680648424094, 0.941414470942911, 0.942147920394849,
  0.942880997159041, 0.943613701614043, 0.944346034137834, 0.945077995107817,
  0.945809584900821, 0.946540803893103, 0.947271652460349, 0.948002130977671,
  0.948732239819614, 0.949461979360154, 0.950191349972701, 0.950920352030097,
  0.951648985904620, 0.952377251967984, 0.953105150591341, 0.953832682145281,
  0.954559846999833, 0.955286645524468, 0.956013078088099, 0.956739145059080,
  0.957464846805211, 0.958190183693738, 0.958915156091350, 0.959639764364186,
  0.960364008877834, 0.961087889997331, 0.961811408087163, 0.962534563511272,
  0.963257356633048, 0.963979787815339, 0.964701857420447, 0.965423565810129,
  0.966144913345602, 0.966865900387539, 0.967586527296073, 0.968306794430798,
  0.969026702150771, 0.969746250814509, 0.970465440779995, 0.971184272404677,
  0.971902746045467, 0.972620862058745, 0.973338620800360, 0.974056022625630,
  0.974773067889342, 0.975489756945754, 0.976206090148598, 0.976922067851080,
  0.977637690405876, 0.978352958165143, 0.979067871480510, 0.979782430703087,
  0.980496636183459, 0.981210488271695, 0.981923987317340, 0.982637133669424,
  0.983349927676458, 0.984062369686437, 0.984774460046841, 0.985486199104635,
  0.986197587206273, 0.986908624697693, 0.987619311924326, 0.988329649231088,
  0.989039636962390, 0.989749275462133, 0.990458565073711, 0.991167506140010,
  0.991876099003415, 0.992584344005802, 0.993292241488548, 0.993999791792523,
  0.994706995258101, 0.995413852225151, 0.996120363033046, 0.996826528020659,
  0.997532347526366, 0.998237821888046, 0.998942951443085, 0.999647736528371,
};

#ifndef PRODUCT
static double log_table_value(int i) {
  return (log(1.0 + static_cast<double>(i + 0.5) / FastLogCount) / log(2.0));
}

// Ensure initialization checks only happen once during bootstrap
static volatile bool log_table_checked = false;

// Sanity check all log_table values or print it out if running
// -Xlog:heapsampling+generate::none
static void verify_or_generate_log_table() {
  log_table_checked = true;
  assert(is_power_of_2(FastLogCount) && FastLogCount >= 4, "table size should be power of two and at least 4");
  if (log_is_enabled(Info,heapsampling,generate)) {
    log_info(heapsampling,generate)("FastLogCount = %d", FastLogCount);
    log_info(heapsampling,generate)("static const double log_table[FastLogCount] = {");
    int i = 0;
    for (; i < FastLogCount; i += 4) {
      double v1 = log_table_value(i);
      double v2 = log_table_value(i + 1);
      double v3 = log_table_value(i + 2);
      double v4 = log_table_value(i + 3);
      log_info(heapsampling,generate)("  %.15f, %.15f, %.15f, %.15f,", v1, v2, v3, v4);
    }
    log_info(heapsampling,generate)("};");
    assert(i == FastLogCount, "post-loop invariant");
  } else {
    // sanity check log_table - disabled when generating
    for (int i = 0; i < FastLogCount; i++) {
    assert(abs(log_table_value(i) - log_table[i]) < 0.0001,
      "log_table deviates too much at index: %d %.15f %.15f",
      i, log_table_value(i), log_table[i]);
    }
  }
}
#endif

// Returns the next prng value.
// pRNG is: aX+b mod c with a = 0x5DEECE66D, b =  0xB, c = 1<<48
// This is the lrand64 generator.
uint64_t ThreadHeapSampler::next_random(uint64_t rnd) {
  const uint64_t PrngMult = 0x5DEECE66DLL;
  const uint64_t PrngAdd = 0xB;
  const uint64_t PrngModPower = 48;
  const uint64_t PrngModMask = ((uint64_t)1 << PrngModPower) - 1;
  //assert(IS_SAFE_SIZE_MUL(PrngMult, rnd), "Overflow on multiplication.");
  //assert(IS_SAFE_SIZE_ADD(PrngMult * rnd, PrngAdd), "Overflow on addition.");
  return (PrngMult * rnd + PrngAdd) & PrngModMask;
}

double ThreadHeapSampler::fast_log2(const double& d) {
  assert(d>0, "bad value passed to assert");
  uint64_t x = 0;
  assert(sizeof(d) == sizeof(x),
         "double and uint64_t do not have the same size");
  x = *reinterpret_cast<const uint64_t*>(&d);
  const uint32_t x_high = checked_cast<uint32_t>(x >> 32);
  assert(FastLogNumBits <= 20, "FastLogNumBits should be less than 20.");
  const uint32_t y = x_high >> (20 - FastLogNumBits) & FastLogMask;
  const int32_t exponent = ((x_high >> 20) & 0x7FF) - 1023;
  return exponent + log_table[y];
}

// Generates a geometric variable with the specified mean (512K by default).
// This is done by generating a random number between 0 and 1 and applying
// the inverse cumulative distribution function for an exponential.
// Specifically: Let m be the inverse of the sample interval, then
// the probability distribution function is m*exp(-mx) so the CDF is
// p = 1 - exp(-mx), so
// q = 1 - p = exp(-mx)
// log_e(q) = -mx
// -log_e(q)/m = x
// log_2(q) * (-log_e(2) * 1/m) = x
// In the code, q is actually in the range 1 to 2**26, hence the -26 below
void ThreadHeapSampler::pick_next_geometric_sample() {
  _rnd = next_random(_rnd);
  // Take the top 26 bits as the random number
  // (This plus a 1<<58 sampling bound gives a max possible step of
  // 5194297183973780480 bytes.  In this case,
  // for sample_parameter = 1<<19, max possible step is
  // 9448372 bytes (24 bits).
  const uint64_t PrngModPower = 48;  // Number of bits in prng
  // The uint32_t cast is to prevent a (hard-to-reproduce) NAN
  // under piii debug for some binaries.
  double q = static_cast<uint32_t>(_rnd >> (PrngModPower - 26)) + 1.0;
  // Put the computed p-value through the CDF of a geometric.
  // For faster performance (save ~1/20th exec time), replace
  // min(0.0, FastLog2(q) - 26)  by  (Fastlog2(q) - 26.000705)
  // The value 26.000705 is used rather than 26 to compensate
  // for inaccuracies in FastLog2 which otherwise result in a
  // negative answer.
  double log_val = (fast_log2(q) - 26);
  double result =
      (0.0 < log_val ? 0.0 : log_val) * (-log(2.0) * (get_sampling_interval())) + 1;
  assert(result > 0 && result < static_cast<double>(SIZE_MAX), "Result is not in an acceptable range.");
  size_t interval = static_cast<size_t>(result);
  _sample_threshold = interval;
}

void ThreadHeapSampler::pick_next_sample() {
#ifndef PRODUCT
  if (!log_table_checked) {
    verify_or_generate_log_table();
  }
#endif
  // Explicitly test if the sampling interval is 0, return 0 to sample every
  // allocation.
  if (get_sampling_interval() == 0) {
    _sample_threshold = 0;
    return;
  }

  pick_next_geometric_sample();
}

#ifndef PRODUCT
void ThreadHeapSampler::log_sample_decision(HeapWord* tlab_top) {
  LogTarget(Debug, gc, tlab) log;
  if (log.is_enabled()) {
    const bool should_sample = bytes_since_last_sample(tlab_top) >= _sample_threshold;
    log_debug(gc, tlab)("Should sample: %s sample threshold: %zu total: %zu tlab: %zu current tlab: %zu outside tlab: %zu",
                        should_sample ? "yes" : "no ",
                        _sample_threshold,
                        bytes_since_last_sample(tlab_top),
                        tlab_bytes_since_last_sample(tlab_top),
                        current_tlab_bytes_since_last_sample(tlab_top),
                        outside_tlab_bytes_since_last_sample());
  }
}
#endif

void ThreadHeapSampler::sample(oop obj, HeapWord* tlab_top) {
  JvmtiExport::sampled_object_alloc_event_collector(obj);

  pick_next_sample();

  reset_after_sample(tlab_top);
}

int ThreadHeapSampler::get_sampling_interval() {
  return Atomic::load_acquire(&_sampling_interval);
}

void ThreadHeapSampler::set_sampling_interval(int sampling_interval) {
  Atomic::release_store(&_sampling_interval, sampling_interval);
}