1 /* addrmap.h --- interface to address map data structure.
3 Copyright (C) 2007-2024 Free Software Foundation, Inc.
5 This file is part of GDB.
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
23 #include "splay-tree.h"
24 #include "gdbsupport/function-view.h"
26 /* An address map is essentially a table mapping CORE_ADDRs onto GDB
27 data structures, like blocks, symtabs, partial symtabs, and so on.
28 An address map uses memory proportional to the number of
29 transitions in the map, where a CORE_ADDR N is mapped to one
30 object, and N+1 is mapped to a different object.
32 Address maps come in two flavors: fixed, and mutable. Mutable
33 address maps consume more memory, but can be changed and extended.
34 A fixed address map, once constructed (from a mutable address map),
37 /* The type of a function used to iterate over the map.
38 OBJ is NULL for unmapped regions. */
39 using addrmap_foreach_fn
40 = gdb::function_view
<int (CORE_ADDR start_addr
, void *obj
)>;
41 using addrmap_foreach_const_fn
42 = gdb::function_view
<int (CORE_ADDR start_addr
, const void *obj
)>;
44 /* The base class for addrmaps. */
47 virtual ~addrmap () = default;
49 /* In the mutable address map MAP, associate the addresses from START
50 to END_INCLUSIVE that are currently associated with NULL with OBJ
51 instead. Addresses mapped to an object other than NULL are left
54 As the name suggests, END_INCLUSIVE is also mapped to OBJ. This
55 convention is unusual, but it allows callers to accurately specify
56 ranges that abut the top of the address space, and ranges that
57 cover the entire address space.
59 This operation seems a bit complicated for a primitive: if it's
60 needed, why not just have a simpler primitive operation that sets a
61 range to a value, wiping out whatever was there before, and then
62 let the caller construct more complicated operations from that,
63 along with some others for traversal?
65 It turns out this is the mutation operation we want to use all the
66 time, at least for now. Our immediate use for address maps is to
67 represent lexical blocks whose address ranges are not contiguous.
68 We walk the tree of lexical blocks present in the debug info, and
69 only create 'struct block' objects after we've traversed all a
70 block's children. If a lexical block declares no local variables
71 (and isn't the lexical block for a function's body), we omit it
72 from GDB's data structures entirely.
74 However, this means that we don't decide to create a block (and
75 thus record it in the address map) until after we've traversed its
76 children. If we do decide to create the block, we do so at a time
77 when all its children have already been recorded in the map. So
78 this operation --- change only those addresses left unset --- is
79 actually the operation we want to use every time.
81 It seems simpler to let the code which operates on the
82 representation directly deal with the hair of implementing these
83 semantics than to provide an interface which allows it to be
84 implemented efficiently, but doesn't reveal too much of the
86 virtual void set_empty (CORE_ADDR start
, CORE_ADDR end_inclusive
,
89 /* Return the object associated with ADDR in MAP. */
90 const void *find (CORE_ADDR addr
) const
91 { return this->do_find (addr
); }
93 void *find (CORE_ADDR addr
)
94 { return this->do_find (addr
); }
96 /* Relocate all the addresses in MAP by OFFSET. (This can be applied
97 to either mutable or immutable maps.) */
98 virtual void relocate (CORE_ADDR offset
) = 0;
100 /* Call FN for every address in MAP, following an in-order traversal.
101 If FN ever returns a non-zero value, the iteration ceases
102 immediately, and the value is returned. Otherwise, this function
104 int foreach (addrmap_foreach_const_fn fn
) const
105 { return this->do_foreach (fn
); }
107 int foreach (addrmap_foreach_fn fn
)
108 { return this->do_foreach (fn
); }
112 /* Worker for find, implemented by sub-classes. */
113 virtual void *do_find (CORE_ADDR addr
) const = 0;
115 /* Worker for foreach, implemented by sub-classes. */
116 virtual int do_foreach (addrmap_foreach_fn fn
) const = 0;
119 struct addrmap_mutable
;
121 /* Fixed address maps. */
122 struct addrmap_fixed
: public addrmap
,
123 public allocate_on_obstack
127 addrmap_fixed (struct obstack
*obstack
, addrmap_mutable
*mut
);
128 DISABLE_COPY_AND_ASSIGN (addrmap_fixed
);
130 void set_empty (CORE_ADDR start
, CORE_ADDR end_inclusive
,
132 void relocate (CORE_ADDR offset
) override
;
135 void *do_find (CORE_ADDR addr
) const override
;
136 int do_foreach (addrmap_foreach_fn fn
) const override
;
138 /* A transition: a point in an address map where the value changes.
139 The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
141 struct addrmap_transition
147 /* The number of transitions in TRANSITIONS. */
148 size_t num_transitions
;
150 /* An array of transitions, sorted by address. For every point in
151 the map where either ADDR == 0 or ADDR is mapped to one value and
152 ADDR - 1 is mapped to something different, we have an entry here
153 containing ADDR and VALUE. (Note that this means we always have
154 an entry for address 0). */
155 struct addrmap_transition
*transitions
;
158 /* Mutable address maps. */
160 struct addrmap_mutable
: public addrmap
166 DISABLE_COPY_AND_ASSIGN (addrmap_mutable
);
168 void set_empty (CORE_ADDR start
, CORE_ADDR end_inclusive
,
170 void relocate (CORE_ADDR offset
) override
;
173 void *do_find (CORE_ADDR addr
) const override
;
174 int do_foreach (addrmap_foreach_fn fn
) const override
;
176 /* A splay tree, with a node for each transition; there is a
177 transition at address T if T-1 and T map to different objects.
179 Any addresses below the first node map to NULL. (Unlike
180 fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't
183 The last region is assumed to end at CORE_ADDR_MAX.
185 Since we can't know whether CORE_ADDR is larger or smaller than
186 splay_tree_key (unsigned long) --- I think both are possible,
187 given all combinations of 32- and 64-bit hosts and targets ---
188 our keys are pointers to CORE_ADDR values. Since the splay tree
189 library doesn't pass any closure pointer to the key free
190 function, we can't keep a freelist for keys. Since mutable
191 addrmaps are only used temporarily right now, we just leak keys
192 from deleted nodes; they'll be freed when the obstack is freed. */
195 /* Various helper methods. */
196 splay_tree_key
allocate_key (CORE_ADDR addr
);
197 void force_transition (CORE_ADDR addr
);
198 splay_tree_node
splay_tree_lookup (CORE_ADDR addr
) const;
199 splay_tree_node
splay_tree_predecessor (CORE_ADDR addr
) const;
200 splay_tree_node
splay_tree_successor (CORE_ADDR addr
);
201 void splay_tree_remove (CORE_ADDR addr
);
202 void splay_tree_insert (CORE_ADDR key
, void *value
);
206 /* Dump the addrmap to OUTFILE. If PAYLOAD is non-NULL, only dump any
207 components that map to PAYLOAD. (If PAYLOAD is NULL, the entire
209 void addrmap_dump (struct addrmap
*map
, struct ui_file
*outfile
,
212 #endif /* ADDRMAP_H */