sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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 | |
Elliott Hughes | ed39800 | 2017-06-21 14:41:24 -0700 | [diff] [blame^] | 11 | Copyright (C) 2014-2017 Mozilla Foundation |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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 { |
Elliott Hughes | ed39800 | 2017-06-21 14:41:24 -0700 | [diff] [blame^] | 51 | Alloc_Fn_t alloc_fn; /* alloc fn (nofail) */ |
florian | b9d8fbb | 2014-09-14 22:19:52 +0000 | [diff] [blame] | 52 | const HChar* cc; /* cost centre for alloc */ |
Elliott Hughes | ed39800 | 2017-06-21 14:41:24 -0700 | [diff] [blame^] | 53 | Free_Fn_t free_fn; /* free fn */ |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 54 | XArray* ranges; |
| 55 | }; |
| 56 | |
| 57 | |
| 58 | /* fwds */ |
| 59 | static void preen (/*MOD*/RangeMap* rm); |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 60 | static Word find ( const RangeMap* rm, UWord key ); |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 61 | static void split_at ( /*MOD*/RangeMap* rm, UWord key ); |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 62 | static void show ( const RangeMap* rm ); |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 63 | |
| 64 | |
Elliott Hughes | ed39800 | 2017-06-21 14:41:24 -0700 | [diff] [blame^] | 65 | RangeMap* VG_(newRangeMap) ( Alloc_Fn_t alloc_fn, |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 66 | const HChar* cc, |
Elliott Hughes | ed39800 | 2017-06-21 14:41:24 -0700 | [diff] [blame^] | 67 | Free_Fn_t free_fn, |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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)); |
florian | b9d8fbb | 2014-09-14 22:19:52 +0000 | [diff] [blame] | 74 | rm->alloc_fn = alloc_fn; |
| 75 | rm->cc = cc; |
| 76 | rm->free_fn = free_fn; |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 77 | rm->ranges = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(Range) ); |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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); |
florian | b9d8fbb | 2014-09-14 22:19:52 +0000 | [diff] [blame] | 93 | vg_assert(rm->free_fn); |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 94 | vg_assert(rm->ranges); |
| 95 | VG_(deleteXA)(rm->ranges); |
florian | b9d8fbb | 2014-09-14 22:19:52 +0000 | [diff] [blame] | 96 | rm->free_fn(rm); |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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, |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 117 | /*OUT*/UWord* val, const RangeMap* rm, UWord key ) |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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 | |
florian | ca63145 | 2015-08-05 13:23:11 +0000 | [diff] [blame] | 126 | UInt VG_(sizeRangeMap) ( const RangeMap* rm ) |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 127 | { |
| 128 | vg_assert(rm && rm->ranges); |
florian | ca63145 | 2015-08-05 13:23:11 +0000 | [diff] [blame] | 129 | Word size = VG_(sizeXA)(rm->ranges); |
| 130 | vg_assert(size >= 0); |
| 131 | return size; |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 132 | } |
| 133 | |
| 134 | void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max, |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 135 | /*OUT*/UWord* val, const RangeMap* rm, Word ix ) |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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 | |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 163 | static Word find ( const RangeMap* rm, UWord key ) |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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)) |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 203 | static void show ( const RangeMap* rm ) |
sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 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 | /*--------------------------------------------------------------------*/ |