src/mem/ruby/filters/H3BloomFilter.cc

   1 /*
   2  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   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
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include "base/intmath.hh"
  30 #include "base/str.hh"
  31 #include "mem/ruby/filters/H3BloomFilter.hh"
  32
  33 using namespace std;
  34
  35 static int H3[64][16] = {
  36     { 33268410,   395488709,  311024285,  456111753,
  37       181495008,  119997521,  220697869,  433891432,
  38       755927921,  515226970,  719448198,  349842774,
  39       269183649,  463275672,  429800228,  521598937,  },
  40
  41     { 628677802,  820947732,  809435975,  1024657192,
  42       887631270,  412050215,  391365090,  324227279,
  43       318338329,  1038393087, 489807930,  387366128,
  44       518096428,  324184340,  429376066,  447109279,  },
  45
  46     { 599747653,  404960623,  103933604,  946416030,
  47       656460913,  925957005,  1047665689, 163552053,
  48       88359290,   841315415,  899833584,  1067336680,
  49       348549994,  464045876,  270252128,  829897652,  },
  50
  51     { 215495230,  966696438,  82589012,   750102795,
  52       909780866,  920285789,  769759214,  331966823,
  53       939936006,  439950703,  883794828,  1009277508,
  54       61634610,   741444350,  98689608,   524144422,  },
  55
  56     { 93868534,   196958667,  774076619,  327921978,
  57       122538783,  879785030,  690748527,  3498564,
  58       83163077,   1027963025, 582088444,  466152216,
  59       312424878,  550064499,  646612667,  561099434,  },
  60
  61     { 1002047931, 395477707,  821317480,  890482112,
  62       697094476,  263813044,  840275189,  469664185,
  63       795625845,  211504898,  99204277,   1004491153,
  64       725930417,  1064479221, 893834767,  839719181,  },
  65
  66     { 278507126,  985111995,  706462983,  1042178726,
  67       123281719,  963778122,  500881056,  726291104,
  68       134293026,  568379664,  317050609,  533470307,
  69       1022365922, 197645211,  315125721,  634827678,  },
  70
  71     { 219227366,  553960647,  870169525,  322232839,
  72       508322497,  648672696,  249405795,  883596102,
  73       476433133,  541372919,  646647793,  1042679515,
  74       43242483,   600187508,  499866821,  135713210,  },
  75
  76     { 52837162,   96966684,   401840460,  1071661176,
  77       733560065,  150035417,  341319946,  811582750,
  78       636173904,  519054065,  196321433,  1028294565,
  79       882204070,  522965093,  48884074,   117810166,  },
  80
  81     { 650860353,  789534698,  328813544,  473250022,
  82       143128306,  173196006,  846958825,  174632187,
  83       683273509,  405459497,  787235556,  773873501,
  84       240110267,  426797736,  92043842,   711789240,  },
  85
  86     { 586637493,  5059646,    398035664,  6686087,
  87       498300175,  948278148,  681227731,  592751744,
  88       572019677,  558044722,  589368271,  695745538,
  89       1073416749, 529192035,  550984939,  1070620580, },
  90
  91     { 102904663,  647598516,  758863940,  313426443,
  92       76504114,   1050747783, 708436441,  563815069,
  93       224107668,  875925186,  167675944,  926209739,
  94       279737287,  1040288182, 768184312,  371708956,  },
  95
  96     { 683968868,  1027427757, 180781926,  742898864,
  97       624078545,  645659833,  577225838,  987150210,
  98       723410002,  224013421,  993286634,  33188488,
  99       247264323,  888018697,  38048664,   189037096,  },
 100
 101     { 475612146,  426739285,  873726278,  529192871,
 102       607715202,  388486246,  987001312,  474493980,
 103       259747270,  417465536,  217062395,  392858482,
 104       563810075,  137852805,  1051814153, 72895217,   },
 105
 106     { 71277086,   785496675,  500608842,  89633426,
 107       274085706,  248467935,  838061983,  48106147,
 108       773662506,  49545328,   9071573,    100739031,
 109       602018002,  904371654,  534132064,  332211304,  },
 110
 111     { 401893602,  735125342,  775548339,  210224843,
 112       256081130,  482894412,  350801633,  1035713633,
 113       429458128,  327281409,  739927752,  359327650,
 114       886942880,  847691759,  752417993,  359445596,  },
 115
 116     { 267472014,  1050659620, 1068232362, 1049684368,
 117       17130239,   690524969,  793224378,  14455158,
 118       423092885,  873853424,  430535778,  7867877,
 119       309731959,  370260786,  862353083,  403906850,  },
 120
 121     { 993077283,  218812656,  389234651,  393202875,
 122       413116501,  263300295,  470013158,  592730725,
 123       441847172,  732392823,  407574059,  875664777,
 124       271347307,  792954404,  554774761,  1022424300, },
 125
 126     { 675919719,  637054073,  784720745,  149714381,
 127       813144874,  502525801,  635436670,  1003196587,
 128       160786091,  947509775,  969788637,  26854073,
 129       257964369,  63898568,   539767732,  772364518,  },
 130
 131     { 943076868,  1021732472, 697575075,  15843624,
 132       617573396,  534113303,  122953324,  964873912,
 133       942995378,  87830944,   1012914818, 455484661,
 134       592160054,  599844284,  810394353,  836812568,  },
 135
 136     { 688992674,  279465370,  731582262,  687883235,
 137       438178468,  80493001,   342701501,  663561405,
 138       23360106,   531315007,  508931618,  36294623,
 139       231216223,  840438413,  255665680,  663205938,  },
 140
 141     { 857265418,  552630887,  8173237,    792122963,
 142       210140052,  823124938,  667709953,  751538219,
 143       991957789,  462064153,  19070176,   726604748,
 144       714567823,  151147895,  1012619677, 697114353,  },
 145
 146     { 467105652,  683256174,  702387467,  28730434,
 147       549942998,  48712701,   960519696,  1008345587,
 148       679267717,  370932249,  880419471,  352141567,
 149       331640403,  598772468,  95160685,   812053015,  },
 150
 151     { 1053491323, 430526562,  1014938507, 109685515,
 152       765949103,  177288303,  1034642653, 485421658,
 153       71850281,   981034542,  61620389,   601367920,
 154       504420930,  220599168,  583051998,  158735752,  },
 155
 156     { 103033901,  522494916,  658494760,  959206022,
 157       931348143,  834510661,  21542994,   189699884,
 158       679327018,  171983002,  96774168,   456133168,
 159       543103352,  923945936,  970074188,  643658485,  },
 160
 161     { 566379913,  805798263,  840662512,  820206124,
 162       796507494,  223712542,  118811519,  662246595,
 163       809326534,  416471323,  748027186,  161169753,
 164       739149488,  276330378,  924837051,  964873733,  },
 165
 166     { 585882743,  135502711,  3386031,    625631285,
 167       1068193307, 270342640,  432739484,  556606453,
 168       826419155,  1038540977, 158000202,  69109538,
 169       207087256,  298111218,  678046259,  184611498,  },
 170
 171     { 305310710,  46237988,   855726974,  735975153,
 172       930663798,  425764232,  104362407,  391371443,
 173       867622101,  71645091,   61824734,   661902640,
 174       293738633,  309416189,  281710675,  879317360,  },
 175
 176     { 398146324,  398293087,  689145387,  1038451703,
 177       521637478,  516134620,  314658937,  830334981,
 178       583400300,  340083705,  68029852,   675389876,
 179       994635780,  788959180,  406967042,  74403607,   },
 180
 181     { 69463153,   744427484,  191639960,  590927798,
 182       969916795,  546846769,  728756758,  889355646,
 183       520855076,  136068426,  776132410,  189663815,
 184       252051082,  533662856,  362198652,  1026161384, },
 185
 186     { 584984279,  1004834381, 568439705,  834508761,
 187       21812513,   670870173,  1052043300, 341868768,
 188       473755574,  124339439,  36193947,   437997647,
 189       137419489,  58705193,   337793711,  340738909,  },
 190
 191     { 898051466,  512792906,  234874060,  655358775,
 192       683745319,  671676404,  428888546,  639928192,
 193       672697722,  176477579,  747020991,  758211282,
 194       443045009,  205395173,  1016944273, 5584717,    },
 195
 196     { 156038300,  138620174,  588466825,  1061494056,
 197       1013672100, 1064257198, 881417791,  839470738,
 198       83519030,   100875683,  237486447,  461483733,
 199       681527127,  777996147,  574635362,  815974538,  },
 200
 201     { 184168473,  519509808,  62531892,   51821173,
 202       43787358,   385711644,  141325169,  36069511,
 203       584183031,  571372909,  671503175,  226486781,
 204       194932686,  1045460970, 753718579,  331442433,  },
 205
 206     { 73065106,   1015327221, 630916840,  1058053470,
 207       306737587,  296343219,  907194989,  920172546,
 208       224516225,  818625553,  551143849,  634570650,
 209       432966225,  756438259,  939564853,  767999933,  },
 210
 211     { 884775648,  394862257,  446787794,  219833788,
 212       727195727,  728122304,  249888353,  732947974,
 213       289908868,  448282580,  618161877,  898939716,
 214       739554163,  860631799,  1058977530, 86916736,   },
 215
 216     { 143850006,  352708694,  200194048,  979764914,
 217       629404175,  546279766,  72106714,   860980514,
 218       313190585,  897143111,  308425797,  953791785,
 219       349924906,  221457005,  950588925,  908254505,  },
 220
 221     { 950032043,  829868728,  68623614,   714624605,
 222       69760597,   297275854,  355894016,  985369737,
 223       882852618,  864071289,  958512902,  950910111,
 224       991368991,  829645051,  434698210,  771350575,  },
 225
 226     { 552695074,  319195551,  80297396,   496413831,
 227       944046531,  621525571,  617653363,  416729825,
 228       441842808,  9847464,    99420657,   1033914550,
 229       812966458,  937053011,  673390195,  934577365,  },
 230
 231     { 1034695843, 190969665,  332900185,  51897434,
 232       523888639,  883512843,  146908572,  506785674,
 233       565814307,  692255649,  314052926,  826386588,
 234       430691325,  866927620,  413880214,  936474339,  },
 235
 236     { 129380164,  741739952,  1013703462, 494392795,
 237       957214600,  1010879043, 931790677,  94551922,
 238       988065869,  120637871,  882506912,  395075379,
 239       210570485,  812422692,  910383687,  817722285,  },
 240
 241     { 51850866,   283408630,  1053047202, 858940389,
 242       818507731,  477082181,  353546901,  993324368,
 243       407093779,  231608253,  1067319867, 73159811,
 244       429792535,  971320614,  565699344,  718823399,  },
 245
 246     { 408185106,  491493570,  596050720,  310776444,
 247       703628192,  454438809,  523988035,  728512200,
 248       686012353,  976339656,  72816924,   116926720,
 249       165866591,  452043792,  866943072,  968545481,  },
 250
 251     { 443231195,  905907843,  1061421320, 746360489,
 252       1043120338, 1069659155, 463359031,  688303227,
 253       186550710,  155347339,  1044842421, 1005904570,
 254       69332909,   706951903,  422513657,  882038450,  },
 255
 256     { 430990623,  946501980,  742556791,  278398643,
 257       183759217,  659404315,  279754382,  1069347846,
 258       843746517,  222777670,  990835599,  548741637,
 259       129220580,  1392170,    1032654091, 894058935,  },
 260
 261     { 452042227,  751640705,  259481376,  765824585,
 262       145991469,  1013683228, 1055491225, 536379588,
 263       392593350,  913368594,  1029429776, 226857786,
 264       31505342,   1054416381, 32341741,   687106649,  },
 265
 266     { 404750944,  811417027,  869530820,  773491060,
 267       810901282,  979340397,  1036910290, 461764404,
 268       834235095,  765695033,  604692390,  452158120,
 269       928988098,  442719218,  1024059719, 167723114,  },
 270
 271     { 974245177,  1046377300, 1003424287, 787349855,
 272       336314155,  875074696,  1018462718, 890313003,
 273       367376809,  86355556,   1020618772, 890710345,
 274       444741481,  373230261,  767064947,  840920177,  },
 275
 276     { 719581124,  431808156,  138301690,  668222575,
 277       497413494,  740492013,  485033226,  125301442,
 278       831265111,  879071459,  341690480,  152975256,
 279       850330086,  717444507,  694225877,  785340566,  },
 280
 281     { 1032766252, 140959364,  737474726,  1062767538,
 282       364464647,  331414723,  356152634,  642832379,
 283       158733632,  374691640,  285504811,  345349905,
 284       876599880,  476392727,  479589210,  606376325,  },
 285
 286     { 174997730,  778177086,  319164313,  163614456,
 287       10331364,   599358958,  8331663,    237538058,
 288       159173957,  174533880,  65588684,   878222844,
 289       424467599,  901803515,  187504218,  776690353,  },
 290
 291     { 803856182,  965850321,  694948067,  218315960,
 292       358416571,  683713254,  178069303,  428076035,
 293       686176454,  579553217,  357306738,  315018080,
 294       886852373,  568563910,  896839725,  257416821,  },
 295
 296     { 401650013,  183289141,  497957228,  879734476,
 297       265024455,  825794561,  889237440,  323359863,
 298       100258491,  991414783,  313986632,  85847250,
 299       362520248,  276103512,  1041630342, 525981595,  },
 300
 301     { 487732740,  46201705,   990837834,  62744493,
 302       1067364756, 58015363,   690846283,  680262648,
 303       997278956,  469357861,  432164624,  996763915,
 304       211907847,  167824295,  144928194,  454839915,  },
 305
 306     { 41404232,   514493300,  259546924,  578217256,
 307       972345130,  123299213,  346040332,  1014668104,
 308       520910639,  579955198,  36627803,   179072921,
 309       547684341,  598950511,  269497394,  854352266,  },
 310
 311     { 603906768,  100863318,  708837659,  204175569,
 312       375560904,  908375384,  28314106,   6303733,
 313       175283124,  749851198,  308667367,  415293931,
 314       225365403,  1032188331, 977112710,  819705229,  },
 315
 316     { 399767123,  697985692,  356790426,  643687584,
 317       298624218,  185095167,  381653926,  876816342,
 318       296720023,  2205879,    235816616,  521850105,
 319       622753786,  1021421218, 726349744,  256504902,  },
 320
 321     { 851245024,  1022500222, 511909628,  313809625,
 322       99776025,   39710175,   798739932,  741832408,
 323       140631966,  898295927,  607660421,  870669312,
 324       1051422478, 789055529,  669113756,  681943450,  },
 325
 326     { 853872755,  491465269,  503341472,  98019440,
 327       258267420,  335602837,  320687824,  1053324395,
 328       24932389,   955011453,  934255131,  435625663,
 329       501568768,  238967025,  549987406,  248619780,  },
 330
 331     { 411151284,  576471205,  757985419,  544137226,
 332       968135693,  877548443,  194586894,  74882373,
 333       248353663,  21207540,   273789651,  853653916,
 334       861267970,  533253322,  3739570,    661358586,  },
 335
 336     { 271430986,  71390029,   257643671,  949329860,
 337       348156406,  251939238,  445808698,  48269799,
 338       907589462,  105677619,  635451508,  20805932,
 339       464874661,  7542147,    243619464,  288304568,  },
 340
 341     { 368215982,  530288964,  770090421,  660961164,
 342       614935537,  630760399,  931299233,  794519275,
 343       779918979,  401746493,  561237006,  1027202224,
 344       258968003,  339508073,  1050610516, 1064307013, },
 345
 346     { 1039172162, 448331205,  928997884,  49813151,
 347       198712120,  992335354,  671024050,  879525220,
 348       745915336,  1038822580, 138669665,  917958819,
 349       681422342,  792868818,  924762727,  816386174,  },
 350
 351     { 515190336,  313808618,  441296783,  1022120897,
 352       792325033,  354387581,  59273006,   280075434,
 353       411357221,  665274694,  4054464,    1059046246,
 354       394261773,  848616745,  15446017,   517723271,  },
 355 };
 356
 357 H3BloomFilter::H3BloomFilter(string str)
 358 {
 359     //TODO: change this ugly init code...
 360     primes_list[0] = 9323;
 361     primes_list[1] = 11279;
 362     primes_list[2] = 10247;
 363     primes_list[3] = 30637;
 364     primes_list[4] = 25717;
 365     primes_list[5] = 43711;
 366
 367     mults_list[0] = 255;
 368     mults_list[1] = 29;
 369     mults_list[2] = 51;
 370     mults_list[3] = 3;
 371     mults_list[4] = 77;
 372     mults_list[5] = 43;
 373
 374     adds_list[0] = 841;
 375     adds_list[1] = 627;
 376     adds_list[2] = 1555;
 377     adds_list[3] = 241;
 378     adds_list[4] = 7777;
 379     adds_list[5] = 65931;
 380
 381     vector<string> items;
 382     tokenize(items, str, '_');
 383     assert(items.size() == 3);
 384
 385     // head contains filter size, tail contains bit offset from block number
 386     m_filter_size = atoi(items[0].c_str());
 387     m_num_hashes = atoi(items[1].c_str());
 388
 389     if (items[2] == "Regular") {
 390         isParallel = false;
 391     } else if (items[2] == "Parallel") {
 392         isParallel = true;
 393     } else {
 394         panic("ERROR: Incorrect config string for MultiHash Bloom! :%s", str);
 395     }
 396
 397     m_filter_size_bits = floorLog2(m_filter_size);
 398
 399     m_par_filter_size = m_filter_size / m_num_hashes;
 400     m_par_filter_size_bits = floorLog2(m_par_filter_size);
 401
 402     m_filter.resize(m_filter_size);
 403     clear();
 404 }
 405
 406 H3BloomFilter::~H3BloomFilter()
 407 {
 408 }
 409
 410 void
 411 H3BloomFilter::clear()
 412 {
 413     for (int i = 0; i < m_filter_size; i++) {
 414         m_filter[i] = 0;
 415     }
 416 }
 417
 418 void
 419 H3BloomFilter::increment(const Address& addr)
 420 {
 421     // Not used
 422 }
 423
 424 void
 425 H3BloomFilter::decrement(const Address& addr)
 426 {
 427     // Not used
 428 }
 429
 430 void
 431 H3BloomFilter::merge(AbstractBloomFilter *other_filter)
 432 {
 433     // assumes both filters are the same size!
 434     H3BloomFilter * temp = (H3BloomFilter*) other_filter;
 435     for(int i = 0; i < m_filter_size; ++i){
 436         m_filter[i] |= (*temp)[i];
 437     }
 438 }
 439
 440 void
 441 H3BloomFilter::set(const Address& addr)
 442 {
 443     for (int i = 0; i < m_num_hashes; i++) {
 444         int idx = get_index(addr, i);
 445         m_filter[idx] = 1;
 446     }
 447 }
 448
 449 void
 450 H3BloomFilter::unset(const Address& addr)
 451 {
 452     cout << "ERROR: Unset should never be called in a Bloom filter";
 453     assert(0);
 454 }
 455
 456 bool
 457 H3BloomFilter::isSet(const Address& addr)
 458 {
 459     bool res = true;
 460
 461     for (int i = 0; i < m_num_hashes; i++) {
 462         int idx = get_index(addr, i);
 463         res = res && m_filter[idx];
 464     }
 465     return res;
 466 }
 467
 468 int
 469 H3BloomFilter::getCount(const Address& addr)
 470 {
 471     return isSet(addr)? 1: 0;
 472 }
 473
 474 int
 475 H3BloomFilter::getIndex(const Address& addr)
 476 {
 477     return 0;
 478 }
 479
 480 int
 481 H3BloomFilter::readBit(const int index)
 482 {
 483     return 0;
 484 }
 485
 486 void
 487 H3BloomFilter::writeBit(const int index, const int value)
 488 {
 489 }
 490
 491 int
 492 H3BloomFilter::getTotalCount()
 493 {
 494     int count = 0;
 495
 496     for (int i = 0; i < m_filter_size; i++) {
 497         count += m_filter[i];
 498     }
 499     return count;
 500 }
 501
 502 void
 503 H3BloomFilter::print(ostream& out) const
 504 {
 505 }
 506
 507 int
 508 H3BloomFilter::get_index(const Address& addr, int i)
 509 {
 510     uint64 x = addr.getLineAddress();
 511     // uint64 y = (x*mults_list[i] + adds_list[i]) % primes_list[i];
 512     int y = hash_H3(x,i);
 513
 514     if (isParallel) {
 515         return (y % m_par_filter_size) + i*m_par_filter_size;
 516     } else {
 517         return y % m_filter_size;
 518     }
 519 }
 520
 521 int
 522 H3BloomFilter::hash_H3(uint64 value, int index)
 523 {
 524     uint64 mask = 1;
 525     uint64 val = value;
 526     int result = 0;
 527
 528     for (int i = 0; i < 64; i++) {
 529         if(val&mask) result ^= H3[i][index];
 530         val = val >> 1;
 531     }
 532     return result;
 533 }
 534