coregrind/m_rangemap.c

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- A mapping where the keys exactly cover the address space.    ---*/
   4 /*---                                                 m_rangemap.c ---*/
   5 /*--------------------------------------------------------------------*/
   6
   7 /*
   8    This file is part of Valgrind, a dynamic binary instrumentation
   9    framework.
  10
  11    Copyright (C) 2014-2017 Mozilla Foundation
  12
  13    This program is free software; you can redistribute it and/or
  14    modify it under the terms of the GNU General Public License as
  15    published by the Free Software Foundation; either version 2 of the
  16    License, or (at your option) any later version.
  17
  18    This program is distributed in the hope that it will be useful, but
  19    WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21    General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, see <http://www.gnu.org/licenses/>.
  25
  26    The GNU General Public License is contained in the file COPYING.
  27 */
  28
  29 /* Contributed by Julian Seward <jseward@acm.org> */
  30
  31 #include "pub_core_basics.h"
  32 #include "pub_core_libcassert.h"
  33 #include "pub_core_libcprint.h"
  34 #include "pub_core_xarray.h"
  35 #include "pub_core_rangemap.h"    /* self */
  36
  37
  38 /* See pub_tool_rangemap.h for details of what this is all about. */
  39
  40 #define UWORD_MIN ((UWord)0)
  41 #define UWORD_MAX (~(UWord)0)
  42
  43 typedef
  44    struct { UWord key_min; UWord key_max; UWord val; }
  45    Range;
  46
  47
  48 struct _RangeMap {
  49    Alloc_Fn_t alloc_fn;                /* alloc fn (nofail) */
  50    const HChar* cc;                    /* cost centre for alloc */
  51    Free_Fn_t free_fn;                  /* free fn */
  52    XArray* ranges;
  53 };
  54
  55
  56 /* fwds */
  57 static void preen (/*MOD*/RangeMap* rm);
  58 static Word find ( const RangeMap* rm, UWord key );
  59 static void split_at ( /*MOD*/RangeMap* rm, UWord key );
  60 static void show ( const RangeMap* rm );
  61
  62
  63 RangeMap* VG_(newRangeMap) ( Alloc_Fn_t alloc_fn,
  64                              const HChar* cc,
  65                              Free_Fn_t free_fn,
  66                              UWord initialVal )
  67 {
  68    /* check user-supplied info .. */
  69    vg_assert(alloc_fn);
  70    vg_assert(free_fn);
  71    RangeMap* rm = alloc_fn(cc, sizeof(RangeMap));
  72    rm->alloc_fn = alloc_fn;
  73    rm->cc       = cc;
  74    rm->free_fn  = free_fn;
  75    rm->ranges = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(Range) );
  76    /* Add the initial range */
  77    Range r;
  78    r.key_min = UWORD_MIN;
  79    r.key_max = UWORD_MAX;
  80    r.val     = initialVal;
  81    Word i = VG_(addToXA)(rm->ranges, &r);
  82    vg_assert(i == 0);
  83    vg_assert(VG_(sizeXA)(rm->ranges) == 1);
  84    /* */
  85    return rm;
  86 }
  87
  88 void VG_(deleteRangeMap) ( RangeMap* rm )
  89 {
  90    vg_assert(rm);
  91    vg_assert(rm->free_fn);
  92    vg_assert(rm->ranges);
  93    VG_(deleteXA)(rm->ranges);
  94    rm->free_fn(rm);
  95 }
  96
  97 void VG_(bindRangeMap) ( RangeMap* rm,
  98                          UWord key_min, UWord key_max, UWord val )
  99 {
 100    vg_assert(key_min <= key_max);
 101    split_at(rm, key_min);
 102    if (key_max < UWORD_MAX)
 103       split_at(rm, key_max + 1);
 104    Word iMin, iMax, i;
 105    iMin = find(rm, key_min);
 106    iMax = find(rm, key_max);
 107    for (i = iMin; i <= iMax; i++) {
 108       Range* rng = VG_(indexXA)(rm->ranges, i);
 109       rng->val = val;
 110    }
 111    preen(rm);
 112 }
 113
 114 void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
 115                            /*OUT*/UWord* val, const RangeMap* rm, UWord key )
 116 {
 117    Word   i   = find(rm, key);
 118    Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
 119    *key_min = rng->key_min;
 120    *key_max = rng->key_max;
 121    *val     = rng->val;
 122 }
 123
 124 UInt VG_(sizeRangeMap) ( const RangeMap* rm )
 125 {
 126    vg_assert(rm && rm->ranges);
 127    Word size = VG_(sizeXA)(rm->ranges);
 128    vg_assert(size >= 0);
 129    return size;
 130 }
 131
 132 void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
 133                           /*OUT*/UWord* val, const RangeMap* rm, Word ix )
 134 {
 135    vg_assert(rm && rm->ranges);
 136    Range* rng = (Range*)VG_(indexXA)(rm->ranges, ix);
 137    *key_min = rng->key_min;
 138    *key_max = rng->key_max;
 139    *val     = rng->val;
 140 }
 141
 142 /* Helper functions, not externally visible. */
 143
 144 static void preen (/*MOD*/RangeMap* rm)
 145 {
 146    Word    i;
 147    XArray* ranges = rm->ranges;
 148    for (i = 0; i < VG_(sizeXA)(ranges) - 1; i++) {
 149       Range* rng0 = VG_(indexXA)(ranges, i+0);
 150       Range* rng1 = VG_(indexXA)(ranges, i+1);
 151       if (rng0->val != rng1->val)
 152          continue;
 153       rng0->key_max = rng1->key_max;
 154       VG_(removeIndexXA)(ranges, i+1);
 155       /* Back up one, so as not to miss an opportunity to merge with
 156          the entry after this one. */
 157       i--;
 158    }
 159 }
 160
 161 static Word find ( const RangeMap* rm, UWord key )
 162 {
 163    XArray* ranges = rm->ranges;
 164    Word    lo     = 0;
 165    Word    hi     = VG_(sizeXA)(ranges);
 166    while (True) {
 167       /* The unsearched space is lo .. hi inclusive */
 168       if (lo > hi) {
 169          /* Not found.  This can't happen. */
 170          VG_(core_panic)("RangeMap::find: not found");
 171          /*NOTREACHED*/
 172          return -1;
 173       }
 174       Word   mid         = (lo + hi) / 2;
 175       Range* mid_rng     = (Range*)VG_(indexXA)(ranges, mid);
 176       UWord  key_mid_min = mid_rng->key_min;
 177       UWord  key_mid_max = mid_rng->key_max;
 178       if (key < key_mid_min) { hi = mid-1; continue; }
 179       if (key > key_mid_max) { lo = mid+1; continue; }
 180       return mid;
 181    }
 182 }
 183
 184 static void split_at ( /*MOD*/RangeMap* rm, UWord key )
 185 {
 186    XArray* ranges = rm->ranges;
 187    Word    i      = find(rm, key);
 188    Range   rng_i0 = *(Range*)VG_(indexXA)( ranges, i+0 );
 189    if (rng_i0.key_min == key)
 190       return;
 191    VG_(insertIndexXA)( ranges, i+1, &rng_i0 );
 192    /* The insert could have relocated the payload, hence the
 193       re-indexing of i+0 here. */
 194    Range* rng_i0p = (Range*)VG_(indexXA)( ranges, i+0 );
 195    Range* rng_i1p = (Range*)VG_(indexXA)( ranges, i+1 );
 196    rng_i0p->key_max = key-1;
 197    rng_i1p->key_min = key;
 198 }
 199
 200 __attribute__((unused))
 201 static void show ( const RangeMap* rm )
 202 {
 203    Word i;
 204    VG_(printf)("<< %ld entries:\n", VG_(sizeXA)(rm->ranges) );
 205    for (i = 0; i < VG_(sizeXA)(rm->ranges); i++) {
 206       Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
 207       VG_(printf)("  %016llx  %016llx  --> 0x%llx\n",
 208                   (ULong)rng->key_min, (ULong)rng->key_max, (ULong)rng->val);
 209    }
 210    VG_(printf)(">>\n");
 211 }
 212
 213
 214 /*--------------------------------------------------------------------*/
 215 /*--- end                                             m_rangemap.c ---*/
 216 /*--------------------------------------------------------------------*/