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
VG_(newRangeMap)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
VG_(deleteRangeMap)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
VG_(bindRangeMap)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
VG_(lookupRangeMap)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
VG_(sizeRangeMap)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
VG_(indexRangeMap)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
preen(RangeMap * rm)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
find(const RangeMap * rm,UWord key)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
split_at(RangeMap * rm,UWord key)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))
show(const RangeMap * rm)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