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 (at) 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 /*--------------------------------------------------------------------*/ 219
