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
45typedef
46   struct { UWord key_min; UWord key_max; UWord val; }
47   Range;
48
49
50struct _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 */
59static void preen (/*MOD*/RangeMap* rm);
60static Word find ( const RangeMap* rm, UWord key );
61static void split_at ( /*MOD*/RangeMap* rm, UWord key );
62static void show ( const RangeMap* rm );
63
64
65RangeMap* 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
90void 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
99void 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
116void 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
126UInt 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
134void 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
146static 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
163static 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
186static 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))
203static 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