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, write to the Free Software
  25    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  26    02111-1307, USA.
  27
  28    The GNU General Public License is contained in the file COPYING.
  29 */
  30
  31 /* Contributed by Julian Seward <jseward@acm.org> */
  32
  33 #include "pub_core_basics.h"
  34 #include "pub_core_libcassert.h"
  35 #include "pub_core_libcprint.h"
  36 #include "pub_core_xarray.h"
  37 #include "pub_core_rangemap.h"    /* self */
  38
  39
  40 /* See pub_tool_rangemap.h for details of what this is all about. */
  41
  42 #define UWORD_MIN ((UWord)0)
  43 #define UWORD_MAX (~(UWord)0)
  44
  45 typedef
  46    struct { UWord key_min; UWord key_max; UWord val; }
  47    Range;
  48
  49
  50 struct _RangeMap {
  51    Alloc_Fn_t alloc_fn;                /* alloc fn (nofail) */
  52    const HChar* cc;                    /* cost centre for alloc */
  53    Free_Fn_t free_fn;                  /* free fn */
  54    XArray* ranges;
  55 };
  56
  57
  58 /* fwds */
  59 static void preen (/*MOD*/RangeMap* rm);
  60 static Word find ( const RangeMap* rm, UWord key );
  61 static void split_at ( /*MOD*/RangeMap* rm, UWord key );
  62 static void show ( const RangeMap* rm );
  63
  64
  65 RangeMap* VG_(newRangeMap) ( Alloc_Fn_t alloc_fn,
  66                              const HChar* cc,
  67                              Free_Fn_t free_fn,
  68                              UWord initialVal )
  69 {
  70    /* check user-supplied info .. */
  71    vg_assert(alloc_fn);
  72    vg_assert(free_fn);
  73    RangeMap* rm = alloc_fn(cc, sizeof(RangeMap));
  74    rm->alloc_fn = alloc_fn;
  75    rm->cc       = cc;
  76    rm->free_fn  = free_fn;
  77    rm->ranges = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(Range) );
  78    /* Add the initial range */
  79    Range r;
  80    r.key_min = UWORD_MIN;
  81    r.key_max = UWORD_MAX;
  82    r.val     = initialVal;
  83    Word i = VG_(addToXA)(rm->ranges, &r);
  84    vg_assert(i == 0);
  85    vg_assert(VG_(sizeXA)(rm->ranges) == 1);
  86    /* */
  87    return rm;
  88 }
  89
  90 void VG_(deleteRangeMap) ( RangeMap* rm )
  91 {
  92    vg_assert(rm);
  93    vg_assert(rm->free_fn);
  94    vg_assert(rm->ranges);
  95    VG_(deleteXA)(rm->ranges);
  96    rm->free_fn(rm);
  97 }
  98
  99 void VG_(bindRangeMap) ( RangeMap* rm,
 100                          UWord key_min, UWord key_max, UWord val )
 101 {
 102    vg_assert(key_min <= key_max);
 103    split_at(rm, key_min);
 104    if (key_max < UWORD_MAX)
 105       split_at(rm, key_max + 1);
 106    Word iMin, iMax, i;
 107    iMin = find(rm, key_min);
 108    iMax = find(rm, key_max);
 109    for (i = iMin; i <= iMax; i++) {
 110       Range* rng = VG_(indexXA)(rm->ranges, i);
 111       rng->val = val;
 112    }
 113    preen(rm);
 114 }
 115
 116 void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
 117                            /*OUT*/UWord* val, const RangeMap* rm, UWord key )
 118 {
 119    Word   i   = find(rm, key);
 120    Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
 121    *key_min = rng->key_min;
 122    *key_max = rng->key_max;
 123    *val     = rng->val;
 124 }
 125
 126 UInt VG_(sizeRangeMap) ( const RangeMap* rm )
 127 {
 128    vg_assert(rm && rm->ranges);
 129    Word size = VG_(sizeXA)(rm->ranges);
 130    vg_assert(size >= 0);
 131    return size;
 132 }
 133
 134 void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
 135                           /*OUT*/UWord* val, const RangeMap* rm, Word ix )
 136 {
 137    vg_assert(rm && rm->ranges);
 138    Range* rng = (Range*)VG_(indexXA)(rm->ranges, ix);
 139    *key_min = rng->key_min;
 140    *key_max = rng->key_max;
 141    *val     = rng->val;
 142 }
 143
 144 /* Helper functions, not externally visible. */
 145
 146 static void preen (/*MOD*/RangeMap* rm)
 147 {
 148    Word    i;
 149    XArray* ranges = rm->ranges;
 150    for (i = 0; i < VG_(sizeXA)(ranges) - 1; i++) {
 151       Range* rng0 = VG_(indexXA)(ranges, i+0);
 152       Range* rng1 = VG_(indexXA)(ranges, i+1);
 153       if (rng0->val != rng1->val)
 154          continue;
 155       rng0->key_max = rng1->key_max;
 156       VG_(removeIndexXA)(ranges, i+1);
 157       /* Back up one, so as not to miss an opportunity to merge with
 158          the entry after this one. */
 159       i--;
 160    }
 161 }
 162
 163 static Word find ( const RangeMap* rm, UWord key )
 164 {
 165    XArray* ranges = rm->ranges;
 166    Word    lo     = 0;
 167    Word    hi     = VG_(sizeXA)(ranges);
 168    while (True) {
 169       /* The unsearched space is lo .. hi inclusive */
 170       if (lo > hi) {
 171          /* Not found.  This can't happen. */
 172          VG_(core_panic)("RangeMap::find: not found");
 173          /*NOTREACHED*/
 174          return -1;
 175       }
 176       Word   mid         = (lo + hi) / 2;
 177       Range* mid_rng     = (Range*)VG_(indexXA)(ranges, mid);
 178       UWord  key_mid_min = mid_rng->key_min;
 179       UWord  key_mid_max = mid_rng->key_max;
 180       if (key < key_mid_min) { hi = mid-1; continue; }
 181       if (key > key_mid_max) { lo = mid+1; continue; }
 182       return mid;
 183    }
 184 }
 185
 186 static void split_at ( /*MOD*/RangeMap* rm, UWord key )
 187 {
 188    XArray* ranges = rm->ranges;
 189    Word    i      = find(rm, key);
 190    Range   rng_i0 = *(Range*)VG_(indexXA)( ranges, i+0 );
 191    if (rng_i0.key_min == key)
 192       return;
 193    VG_(insertIndexXA)( ranges, i+1, &rng_i0 );
 194    /* The insert could have relocated the payload, hence the
 195       re-indexing of i+0 here. */
 196    Range* rng_i0p = (Range*)VG_(indexXA)( ranges, i+0 );
 197    Range* rng_i1p = (Range*)VG_(indexXA)( ranges, i+1 );
 198    rng_i0p->key_max = key-1;
 199    rng_i1p->key_min = key;
 200 }
 201
 202 __attribute__((unused))
 203 static void show ( const RangeMap* rm )
 204 {
 205    Word i;
 206    VG_(printf)("<< %ld entries:\n", VG_(sizeXA)(rm->ranges) );
 207    for (i = 0; i < VG_(sizeXA)(rm->ranges); i++) {
 208       Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
 209       VG_(printf)("  %016llx  %016llx  --> 0x%llx\n",
 210                   (ULong)rng->key_min, (ULong)rng->key_max, (ULong)rng->val);
 211    }
 212    VG_(printf)(">>\n");
 213 }
 214
 215
 216 /*--------------------------------------------------------------------*/
 217 /*--- end                                             m_rangemap.c ---*/
 218 /*--------------------------------------------------------------------*/