1 /* addrmap.h --- interface to address map data structure. 2 3 Copyright (C) 2007-2023 Free Software Foundation, Inc. 4 5 This file is part of GDB. 6 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. 11 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. 16 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/>. */ 19 20 #ifndef ADDRMAP_H 21 #define ADDRMAP_H 22 23 #include "splay-tree.h" 24 #include "gdbsupport/function-view.h" 25 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. 31 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), 35 can't be edited. */ 36 37 /* The type of a function used to iterate over the map. 38 OBJ is NULL for unmapped regions. */ 39 typedef gdb::function_view<int (CORE_ADDR start_addr, void *obj)> 40 addrmap_foreach_fn; 41 42 /* The base class for addrmaps. */ 43 struct addrmap 44 { 45 virtual ~addrmap () = default; 46 47 /* In the mutable address map MAP, associate the addresses from START 48 to END_INCLUSIVE that are currently associated with NULL with OBJ 49 instead. Addresses mapped to an object other than NULL are left 50 unchanged. 51 52 As the name suggests, END_INCLUSIVE is also mapped to OBJ. This 53 convention is unusual, but it allows callers to accurately specify 54 ranges that abut the top of the address space, and ranges that 55 cover the entire address space. 56 57 This operation seems a bit complicated for a primitive: if it's 58 needed, why not just have a simpler primitive operation that sets a 59 range to a value, wiping out whatever was there before, and then 60 let the caller construct more complicated operations from that, 61 along with some others for traversal? 62 63 It turns out this is the mutation operation we want to use all the 64 time, at least for now. Our immediate use for address maps is to 65 represent lexical blocks whose address ranges are not contiguous. 66 We walk the tree of lexical blocks present in the debug info, and 67 only create 'struct block' objects after we've traversed all a 68 block's children. If a lexical block declares no local variables 69 (and isn't the lexical block for a function's body), we omit it 70 from GDB's data structures entirely. 71 72 However, this means that we don't decide to create a block (and 73 thus record it in the address map) until after we've traversed its 74 children. If we do decide to create the block, we do so at a time 75 when all its children have already been recorded in the map. So 76 this operation --- change only those addresses left unset --- is 77 actually the operation we want to use every time. 78 79 It seems simpler to let the code which operates on the 80 representation directly deal with the hair of implementing these 81 semantics than to provide an interface which allows it to be 82 implemented efficiently, but doesn't reveal too much of the 83 representation. */ 84 virtual void set_empty (CORE_ADDR start, CORE_ADDR end_inclusive, 85 void *obj) = 0; 86 87 /* Return the object associated with ADDR in MAP. */ 88 virtual void *find (CORE_ADDR addr) const = 0; 89 90 /* Relocate all the addresses in MAP by OFFSET. (This can be applied 91 to either mutable or immutable maps.) */ 92 virtual void relocate (CORE_ADDR offset) = 0; 93 94 /* Call FN for every address in MAP, following an in-order traversal. 95 If FN ever returns a non-zero value, the iteration ceases 96 immediately, and the value is returned. Otherwise, this function 97 returns 0. */ 98 virtual int foreach (addrmap_foreach_fn fn) = 0; 99 }; 100 101 struct addrmap_mutable; 102 103 /* Fixed address maps. */ 104 struct addrmap_fixed : public addrmap, 105 public allocate_on_obstack 106 { 107 public: 108 109 addrmap_fixed (struct obstack *obstack, addrmap_mutable *mut); 110 DISABLE_COPY_AND_ASSIGN (addrmap_fixed); 111 112 void set_empty (CORE_ADDR start, CORE_ADDR end_inclusive, 113 void *obj) override; 114 void *find (CORE_ADDR addr) const override; 115 void relocate (CORE_ADDR offset) override; 116 int foreach (addrmap_foreach_fn fn) override; 117 118 private: 119 120 /* A transition: a point in an address map where the value changes. 121 The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to 122 something else. */ 123 struct addrmap_transition 124 { 125 CORE_ADDR addr; 126 void *value; 127 }; 128 129 /* The number of transitions in TRANSITIONS. */ 130 size_t num_transitions; 131 132 /* An array of transitions, sorted by address. For every point in 133 the map where either ADDR == 0 or ADDR is mapped to one value and 134 ADDR - 1 is mapped to something different, we have an entry here 135 containing ADDR and VALUE. (Note that this means we always have 136 an entry for address 0). */ 137 struct addrmap_transition *transitions; 138 }; 139 140 /* Mutable address maps. */ 141 142 struct addrmap_mutable : public addrmap 143 { 144 public: 145 146 addrmap_mutable (); 147 ~addrmap_mutable (); 148 DISABLE_COPY_AND_ASSIGN (addrmap_mutable); 149 150 void set_empty (CORE_ADDR start, CORE_ADDR end_inclusive, 151 void *obj) override; 152 void *find (CORE_ADDR addr) const override; 153 void relocate (CORE_ADDR offset) override; 154 int foreach (addrmap_foreach_fn fn) override; 155 156 private: 157 158 /* A splay tree, with a node for each transition; there is a 159 transition at address T if T-1 and T map to different objects. 160 161 Any addresses below the first node map to NULL. (Unlike 162 fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't 163 simplify enough.) 164 165 The last region is assumed to end at CORE_ADDR_MAX. 166 167 Since we can't know whether CORE_ADDR is larger or smaller than 168 splay_tree_key (unsigned long) --- I think both are possible, 169 given all combinations of 32- and 64-bit hosts and targets --- 170 our keys are pointers to CORE_ADDR values. Since the splay tree 171 library doesn't pass any closure pointer to the key free 172 function, we can't keep a freelist for keys. Since mutable 173 addrmaps are only used temporarily right now, we just leak keys 174 from deleted nodes; they'll be freed when the obstack is freed. */ 175 splay_tree tree; 176 177 /* Various helper methods. */ 178 splay_tree_key allocate_key (CORE_ADDR addr); 179 void force_transition (CORE_ADDR addr); 180 splay_tree_node splay_tree_lookup (CORE_ADDR addr) const; 181 splay_tree_node splay_tree_predecessor (CORE_ADDR addr) const; 182 splay_tree_node splay_tree_successor (CORE_ADDR addr); 183 void splay_tree_remove (CORE_ADDR addr); 184 void splay_tree_insert (CORE_ADDR key, void *value); 185 }; 186 187 188 /* Dump the addrmap to OUTFILE. If PAYLOAD is non-NULL, only dump any 189 components that map to PAYLOAD. (If PAYLOAD is NULL, the entire 190 map is dumped.) */ 191 void addrmap_dump (struct addrmap *map, struct ui_file *outfile, 192 void *payload); 193 194 #endif /* ADDRMAP_H */ 195