| 1 | /* Caching code for GDB, the GNU debugger. |
| 2 | |
| 3 | Copyright (C) 1992, 1993, 1995, 1996, 1998, 1999, 2000, 2001, 2003, 2007, |
| 4 | 2008, 2009 Free Software Foundation, Inc. |
| 5 | |
| 6 | This file is part of GDB. |
| 7 | |
| 8 | This program is free software; you can redistribute it and/or modify |
| 9 | it under the terms of the GNU General Public License as published by |
| 10 | the Free Software Foundation; either version 3 of the License, or |
| 11 | (at your option) any later version. |
| 12 | |
| 13 | This program is distributed in the hope that it will be useful, |
| 14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 16 | GNU General Public License for more details. |
| 17 | |
| 18 | You should have received a copy of the GNU General Public License |
| 19 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
| 20 | |
| 21 | #include "defs.h" |
| 22 | #include "dcache.h" |
| 23 | #include "gdbcmd.h" |
| 24 | #include "gdb_string.h" |
| 25 | #include "gdbcore.h" |
| 26 | #include "target.h" |
| 27 | #include "inferior.h" |
| 28 | #include "splay-tree.h" |
| 29 | |
| 30 | /* The data cache could lead to incorrect results because it doesn't |
| 31 | know about volatile variables, thus making it impossible to debug |
| 32 | functions which use memory mapped I/O devices. Set the nocache |
| 33 | memory region attribute in those cases. |
| 34 | |
| 35 | In general the dcache speeds up performance. Some speed improvement |
| 36 | comes from the actual caching mechanism, but the major gain is in |
| 37 | the reduction of the remote protocol overhead; instead of reading |
| 38 | or writing a large area of memory in 4 byte requests, the cache |
| 39 | bundles up the requests into LINE_SIZE chunks, reducing overhead |
| 40 | significantly. This is most useful when accessing a large amount |
| 41 | of data, such as when performing a backtrace. |
| 42 | |
| 43 | The cache is a splay tree along with a linked list for replacement. |
| 44 | Each block caches a LINE_SIZE area of memory. Wtihin each line we remember |
| 45 | the address of the line (which must be a multiple of LINE_SIZE) and the |
| 46 | actual data block. |
| 47 | |
| 48 | Lines are only allocated as needed, so DCACHE_SIZE really specifies the |
| 49 | *maximum* number of lines in the cache. |
| 50 | |
| 51 | At present, the cache is write-through rather than writeback: as soon |
| 52 | as data is written to the cache, it is also immediately written to |
| 53 | the target. Therefore, cache lines are never "dirty". Whether a given |
| 54 | line is valid or not depends on where it is stored in the dcache_struct; |
| 55 | there is no per-block valid flag. */ |
| 56 | |
| 57 | /* NOTE: Interaction of dcache and memory region attributes |
| 58 | |
| 59 | As there is no requirement that memory region attributes be aligned |
| 60 | to or be a multiple of the dcache page size, dcache_read_line() and |
| 61 | dcache_write_line() must break up the page by memory region. If a |
| 62 | chunk does not have the cache attribute set, an invalid memory type |
| 63 | is set, etc., then the chunk is skipped. Those chunks are handled |
| 64 | in target_xfer_memory() (or target_xfer_memory_partial()). |
| 65 | |
| 66 | This doesn't occur very often. The most common occurance is when |
| 67 | the last bit of the .text segment and the first bit of the .data |
| 68 | segment fall within the same dcache page with a ro/cacheable memory |
| 69 | region defined for the .text segment and a rw/non-cacheable memory |
| 70 | region defined for the .data segment. */ |
| 71 | |
| 72 | /* The maximum number of lines stored. The total size of the cache is |
| 73 | equal to DCACHE_SIZE times LINE_SIZE. */ |
| 74 | #define DCACHE_SIZE 4096 |
| 75 | |
| 76 | /* The size of a cache line. Smaller values reduce the time taken to |
| 77 | read a single byte and make the cache more granular, but increase |
| 78 | overhead and reduce the effectiveness of the cache as a prefetcher. */ |
| 79 | #define LINE_SIZE_POWER 6 |
| 80 | #define LINE_SIZE (1 << LINE_SIZE_POWER) |
| 81 | |
| 82 | /* Each cache block holds LINE_SIZE bytes of data |
| 83 | starting at a multiple-of-LINE_SIZE address. */ |
| 84 | |
| 85 | #define LINE_SIZE_MASK ((LINE_SIZE - 1)) |
| 86 | #define XFORM(x) ((x) & LINE_SIZE_MASK) |
| 87 | #define MASK(x) ((x) & ~LINE_SIZE_MASK) |
| 88 | |
| 89 | struct dcache_block |
| 90 | { |
| 91 | struct dcache_block *newer; /* for LRU and free list */ |
| 92 | CORE_ADDR addr; /* address of data */ |
| 93 | gdb_byte data[LINE_SIZE]; /* bytes at given address */ |
| 94 | int refs; /* # hits */ |
| 95 | }; |
| 96 | |
| 97 | struct dcache_struct |
| 98 | { |
| 99 | splay_tree tree; |
| 100 | struct dcache_block *oldest; |
| 101 | struct dcache_block *newest; |
| 102 | |
| 103 | struct dcache_block *freelist; |
| 104 | |
| 105 | /* The number of in-use lines in the cache. */ |
| 106 | int size; |
| 107 | |
| 108 | /* The ptid of last inferior to use cache or null_ptid. */ |
| 109 | ptid_t ptid; |
| 110 | }; |
| 111 | |
| 112 | static struct dcache_block *dcache_hit (DCACHE *dcache, CORE_ADDR addr); |
| 113 | |
| 114 | static int dcache_write_line (DCACHE *dcache, struct dcache_block *db); |
| 115 | |
| 116 | static int dcache_read_line (DCACHE *dcache, struct dcache_block *db); |
| 117 | |
| 118 | static struct dcache_block *dcache_alloc (DCACHE *dcache, CORE_ADDR addr); |
| 119 | |
| 120 | static void dcache_info (char *exp, int tty); |
| 121 | |
| 122 | void _initialize_dcache (void); |
| 123 | |
| 124 | static int dcache_enabled_p = 0; /* OBSOLETE */ |
| 125 | |
| 126 | static void |
| 127 | show_dcache_enabled_p (struct ui_file *file, int from_tty, |
| 128 | struct cmd_list_element *c, const char *value) |
| 129 | { |
| 130 | fprintf_filtered (file, _("Deprecated remotecache flag is %s.\n"), value); |
| 131 | } |
| 132 | |
| 133 | static DCACHE *last_cache; /* Used by info dcache */ |
| 134 | |
| 135 | /* Free all the data cache blocks, thus discarding all cached data. */ |
| 136 | |
| 137 | void |
| 138 | dcache_invalidate (DCACHE *dcache) |
| 139 | { |
| 140 | struct dcache_block *block, *next; |
| 141 | |
| 142 | block = dcache->oldest; |
| 143 | |
| 144 | while (block) |
| 145 | { |
| 146 | splay_tree_remove (dcache->tree, (splay_tree_key) block->addr); |
| 147 | next = block->newer; |
| 148 | |
| 149 | block->newer = dcache->freelist; |
| 150 | dcache->freelist = block; |
| 151 | |
| 152 | block = next; |
| 153 | } |
| 154 | |
| 155 | dcache->oldest = NULL; |
| 156 | dcache->newest = NULL; |
| 157 | dcache->size = 0; |
| 158 | dcache->ptid = null_ptid; |
| 159 | } |
| 160 | |
| 161 | /* Invalidate the line associated with ADDR. */ |
| 162 | |
| 163 | static void |
| 164 | dcache_invalidate_line (DCACHE *dcache, CORE_ADDR addr) |
| 165 | { |
| 166 | struct dcache_block *db = dcache_hit (dcache, addr); |
| 167 | |
| 168 | if (db) |
| 169 | { |
| 170 | splay_tree_remove (dcache->tree, (splay_tree_key) db->addr); |
| 171 | db->newer = dcache->freelist; |
| 172 | dcache->freelist = db; |
| 173 | --dcache->size; |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | /* If addr is present in the dcache, return the address of the block |
| 178 | containing it. */ |
| 179 | |
| 180 | static struct dcache_block * |
| 181 | dcache_hit (DCACHE *dcache, CORE_ADDR addr) |
| 182 | { |
| 183 | struct dcache_block *db; |
| 184 | |
| 185 | splay_tree_node node = splay_tree_lookup (dcache->tree, |
| 186 | (splay_tree_key) MASK (addr)); |
| 187 | |
| 188 | if (!node) |
| 189 | return NULL; |
| 190 | |
| 191 | db = (struct dcache_block *) node->value; |
| 192 | db->refs++; |
| 193 | return db; |
| 194 | } |
| 195 | |
| 196 | /* Fill a cache line from target memory. */ |
| 197 | |
| 198 | static int |
| 199 | dcache_read_line (DCACHE *dcache, struct dcache_block *db) |
| 200 | { |
| 201 | CORE_ADDR memaddr; |
| 202 | gdb_byte *myaddr; |
| 203 | int len; |
| 204 | int res; |
| 205 | int reg_len; |
| 206 | struct mem_region *region; |
| 207 | |
| 208 | len = LINE_SIZE; |
| 209 | memaddr = db->addr; |
| 210 | myaddr = db->data; |
| 211 | |
| 212 | while (len > 0) |
| 213 | { |
| 214 | /* Don't overrun if this block is right at the end of the region. */ |
| 215 | region = lookup_mem_region (memaddr); |
| 216 | if (region->hi == 0 || memaddr + len < region->hi) |
| 217 | reg_len = len; |
| 218 | else |
| 219 | reg_len = region->hi - memaddr; |
| 220 | |
| 221 | /* Skip non-readable regions. The cache attribute can be ignored, |
| 222 | since we may be loading this for a stack access. */ |
| 223 | if (region->attrib.mode == MEM_WO) |
| 224 | { |
| 225 | memaddr += reg_len; |
| 226 | myaddr += reg_len; |
| 227 | len -= reg_len; |
| 228 | continue; |
| 229 | } |
| 230 | |
| 231 | res = target_read (¤t_target, TARGET_OBJECT_RAW_MEMORY, |
| 232 | NULL, myaddr, memaddr, reg_len); |
| 233 | if (res < reg_len) |
| 234 | return 0; |
| 235 | |
| 236 | memaddr += res; |
| 237 | myaddr += res; |
| 238 | len -= res; |
| 239 | } |
| 240 | |
| 241 | return 1; |
| 242 | } |
| 243 | |
| 244 | /* Get a free cache block, put or keep it on the valid list, |
| 245 | and return its address. */ |
| 246 | |
| 247 | static struct dcache_block * |
| 248 | dcache_alloc (DCACHE *dcache, CORE_ADDR addr) |
| 249 | { |
| 250 | struct dcache_block *db; |
| 251 | |
| 252 | if (dcache->size >= DCACHE_SIZE) |
| 253 | { |
| 254 | /* Evict the least recently used line. */ |
| 255 | db = dcache->oldest; |
| 256 | dcache->oldest = db->newer; |
| 257 | |
| 258 | splay_tree_remove (dcache->tree, (splay_tree_key) db->addr); |
| 259 | } |
| 260 | else |
| 261 | { |
| 262 | db = dcache->freelist; |
| 263 | if (db) |
| 264 | dcache->freelist = db->newer; |
| 265 | else |
| 266 | db = xmalloc (sizeof (struct dcache_block)); |
| 267 | |
| 268 | dcache->size++; |
| 269 | } |
| 270 | |
| 271 | db->addr = MASK (addr); |
| 272 | db->newer = NULL; |
| 273 | db->refs = 0; |
| 274 | |
| 275 | if (dcache->newest) |
| 276 | dcache->newest->newer = db; |
| 277 | |
| 278 | dcache->newest = db; |
| 279 | |
| 280 | if (!dcache->oldest) |
| 281 | dcache->oldest = db; |
| 282 | |
| 283 | splay_tree_insert (dcache->tree, (splay_tree_key) db->addr, |
| 284 | (splay_tree_value) db); |
| 285 | |
| 286 | return db; |
| 287 | } |
| 288 | |
| 289 | /* Using the data cache DCACHE return the contents of the byte at |
| 290 | address ADDR in the remote machine. |
| 291 | |
| 292 | Returns 1 for success, 0 for error. */ |
| 293 | |
| 294 | static int |
| 295 | dcache_peek_byte (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr) |
| 296 | { |
| 297 | struct dcache_block *db = dcache_hit (dcache, addr); |
| 298 | |
| 299 | if (!db) |
| 300 | { |
| 301 | db = dcache_alloc (dcache, addr); |
| 302 | |
| 303 | if (!dcache_read_line (dcache, db)) |
| 304 | return 0; |
| 305 | } |
| 306 | |
| 307 | *ptr = db->data[XFORM (addr)]; |
| 308 | return 1; |
| 309 | } |
| 310 | |
| 311 | /* Write the byte at PTR into ADDR in the data cache. |
| 312 | |
| 313 | The caller is responsible for also promptly writing the data |
| 314 | through to target memory. |
| 315 | |
| 316 | If addr is not in cache, this function does nothing; writing to |
| 317 | an area of memory which wasn't present in the cache doesn't cause |
| 318 | it to be loaded in. |
| 319 | |
| 320 | Always return 1 (meaning success) to simplify dcache_xfer_memory. */ |
| 321 | |
| 322 | static int |
| 323 | dcache_poke_byte (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr) |
| 324 | { |
| 325 | struct dcache_block *db = dcache_hit (dcache, addr); |
| 326 | |
| 327 | if (db) |
| 328 | db->data[XFORM (addr)] = *ptr; |
| 329 | |
| 330 | return 1; |
| 331 | } |
| 332 | |
| 333 | static int |
| 334 | dcache_splay_tree_compare (splay_tree_key a, splay_tree_key b) |
| 335 | { |
| 336 | if (a > b) |
| 337 | return 1; |
| 338 | else if (a == b) |
| 339 | return 0; |
| 340 | else |
| 341 | return -1; |
| 342 | } |
| 343 | |
| 344 | /* Initialize the data cache. */ |
| 345 | |
| 346 | DCACHE * |
| 347 | dcache_init (void) |
| 348 | { |
| 349 | DCACHE *dcache; |
| 350 | int i; |
| 351 | |
| 352 | dcache = (DCACHE *) xmalloc (sizeof (*dcache)); |
| 353 | |
| 354 | dcache->tree = splay_tree_new (dcache_splay_tree_compare, |
| 355 | NULL, |
| 356 | NULL); |
| 357 | |
| 358 | dcache->oldest = NULL; |
| 359 | dcache->newest = NULL; |
| 360 | dcache->freelist = NULL; |
| 361 | dcache->size = 0; |
| 362 | dcache->ptid = null_ptid; |
| 363 | last_cache = dcache; |
| 364 | |
| 365 | return dcache; |
| 366 | } |
| 367 | |
| 368 | /* Free a data cache. */ |
| 369 | |
| 370 | void |
| 371 | dcache_free (DCACHE *dcache) |
| 372 | { |
| 373 | struct dcache_block *db, *next; |
| 374 | |
| 375 | if (last_cache == dcache) |
| 376 | last_cache = NULL; |
| 377 | |
| 378 | splay_tree_delete (dcache->tree); |
| 379 | for (db = dcache->freelist; db != NULL; db = next) |
| 380 | { |
| 381 | next = db->newer; |
| 382 | xfree (db); |
| 383 | } |
| 384 | xfree (dcache); |
| 385 | } |
| 386 | |
| 387 | /* Read or write LEN bytes from inferior memory at MEMADDR, transferring |
| 388 | to or from debugger address MYADDR. Write to inferior if SHOULD_WRITE is |
| 389 | nonzero. |
| 390 | |
| 391 | The meaning of the result is the same as for target_write. */ |
| 392 | |
| 393 | int |
| 394 | dcache_xfer_memory (struct target_ops *ops, DCACHE *dcache, |
| 395 | CORE_ADDR memaddr, gdb_byte *myaddr, |
| 396 | int len, int should_write) |
| 397 | { |
| 398 | int i; |
| 399 | int res; |
| 400 | int (*xfunc) (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr); |
| 401 | xfunc = should_write ? dcache_poke_byte : dcache_peek_byte; |
| 402 | |
| 403 | /* If this is a different inferior from what we've recorded, |
| 404 | flush the cache. */ |
| 405 | |
| 406 | if (! ptid_equal (inferior_ptid, dcache->ptid)) |
| 407 | { |
| 408 | dcache_invalidate (dcache); |
| 409 | dcache->ptid = inferior_ptid; |
| 410 | } |
| 411 | |
| 412 | /* Do write-through first, so that if it fails, we don't write to |
| 413 | the cache at all. */ |
| 414 | |
| 415 | if (should_write) |
| 416 | { |
| 417 | res = target_write (ops, TARGET_OBJECT_RAW_MEMORY, |
| 418 | NULL, myaddr, memaddr, len); |
| 419 | if (res <= 0) |
| 420 | return res; |
| 421 | /* Update LEN to what was actually written. */ |
| 422 | len = res; |
| 423 | } |
| 424 | |
| 425 | for (i = 0; i < len; i++) |
| 426 | { |
| 427 | if (!xfunc (dcache, memaddr + i, myaddr + i)) |
| 428 | { |
| 429 | /* That failed. Discard its cache line so we don't have a |
| 430 | partially read line. */ |
| 431 | dcache_invalidate_line (dcache, memaddr + i); |
| 432 | /* If we're writing, we still wrote LEN bytes. */ |
| 433 | if (should_write) |
| 434 | return len; |
| 435 | else |
| 436 | return i; |
| 437 | } |
| 438 | } |
| 439 | |
| 440 | return len; |
| 441 | } |
| 442 | |
| 443 | /* FIXME: There would be some benefit to making the cache write-back and |
| 444 | moving the writeback operation to a higher layer, as it could occur |
| 445 | after a sequence of smaller writes have been completed (as when a stack |
| 446 | frame is constructed for an inferior function call). Note that only |
| 447 | moving it up one level to target_xfer_memory[_partial]() is not |
| 448 | sufficient since we want to coalesce memory transfers that are |
| 449 | "logically" connected but not actually a single call to one of the |
| 450 | memory transfer functions. */ |
| 451 | |
| 452 | /* Just update any cache lines which are already present. This is called |
| 453 | by memory_xfer_partial in cases where the access would otherwise not go |
| 454 | through the cache. */ |
| 455 | |
| 456 | void |
| 457 | dcache_update (DCACHE *dcache, CORE_ADDR memaddr, gdb_byte *myaddr, int len) |
| 458 | { |
| 459 | int i; |
| 460 | for (i = 0; i < len; i++) |
| 461 | dcache_poke_byte (dcache, memaddr + i, myaddr + i); |
| 462 | } |
| 463 | |
| 464 | static void |
| 465 | dcache_print_line (int index) |
| 466 | { |
| 467 | splay_tree_node n; |
| 468 | struct dcache_block *db; |
| 469 | int i, j; |
| 470 | |
| 471 | if (!last_cache) |
| 472 | { |
| 473 | printf_filtered (_("No data cache available.\n")); |
| 474 | return; |
| 475 | } |
| 476 | |
| 477 | n = splay_tree_min (last_cache->tree); |
| 478 | |
| 479 | for (i = index; i > 0; --i) |
| 480 | { |
| 481 | if (!n) |
| 482 | break; |
| 483 | n = splay_tree_successor (last_cache->tree, n->key); |
| 484 | } |
| 485 | |
| 486 | if (!n) |
| 487 | { |
| 488 | printf_filtered (_("No such cache line exists.\n")); |
| 489 | return; |
| 490 | } |
| 491 | |
| 492 | db = (struct dcache_block *) n->value; |
| 493 | |
| 494 | printf_filtered (_("Line %d: address %s [%d hits]\n"), |
| 495 | index, paddress (target_gdbarch, db->addr), db->refs); |
| 496 | |
| 497 | for (j = 0; j < LINE_SIZE; j++) |
| 498 | { |
| 499 | printf_filtered ("%02x ", db->data[j]); |
| 500 | |
| 501 | /* Print a newline every 16 bytes (48 characters) */ |
| 502 | if ((j % 16 == 15) && (j != LINE_SIZE - 1)) |
| 503 | printf_filtered ("\n"); |
| 504 | } |
| 505 | printf_filtered ("\n"); |
| 506 | } |
| 507 | |
| 508 | static void |
| 509 | dcache_info (char *exp, int tty) |
| 510 | { |
| 511 | splay_tree_node n; |
| 512 | int i, refcount, lineno; |
| 513 | |
| 514 | if (exp) |
| 515 | { |
| 516 | char *linestart; |
| 517 | i = strtol (exp, &linestart, 10); |
| 518 | if (linestart == exp || i < 0) |
| 519 | { |
| 520 | printf_filtered (_("Usage: info dcache [linenumber]\n")); |
| 521 | return; |
| 522 | } |
| 523 | |
| 524 | dcache_print_line (i); |
| 525 | return; |
| 526 | } |
| 527 | |
| 528 | printf_filtered (_("Dcache line width %d, maximum size %d\n"), |
| 529 | LINE_SIZE, DCACHE_SIZE); |
| 530 | |
| 531 | if (!last_cache || ptid_equal (last_cache->ptid, null_ptid)) |
| 532 | { |
| 533 | printf_filtered (_("No data cache available.\n")); |
| 534 | return; |
| 535 | } |
| 536 | |
| 537 | printf_filtered (_("Contains data for %s\n"), |
| 538 | target_pid_to_str (last_cache->ptid)); |
| 539 | |
| 540 | refcount = 0; |
| 541 | |
| 542 | n = splay_tree_min (last_cache->tree); |
| 543 | i = 0; |
| 544 | |
| 545 | while (n) |
| 546 | { |
| 547 | struct dcache_block *db = (struct dcache_block *) n->value; |
| 548 | |
| 549 | printf_filtered (_("Line %d: address %s [%d hits]\n"), |
| 550 | i, paddress (target_gdbarch, db->addr), db->refs); |
| 551 | i++; |
| 552 | refcount += db->refs; |
| 553 | |
| 554 | n = splay_tree_successor (last_cache->tree, n->key); |
| 555 | } |
| 556 | |
| 557 | printf_filtered (_("Cache state: %d active lines, %d hits\n"), i, refcount); |
| 558 | } |
| 559 | |
| 560 | void |
| 561 | _initialize_dcache (void) |
| 562 | { |
| 563 | add_setshow_boolean_cmd ("remotecache", class_support, |
| 564 | &dcache_enabled_p, _("\ |
| 565 | Set cache use for remote targets."), _("\ |
| 566 | Show cache use for remote targets."), _("\ |
| 567 | This used to enable the data cache for remote targets. The cache\n\ |
| 568 | functionality is now controlled by the memory region system and the\n\ |
| 569 | \"stack-cache\" flag; \"remotecache\" now does nothing and\n\ |
| 570 | exists only for compatibility reasons."), |
| 571 | NULL, |
| 572 | show_dcache_enabled_p, |
| 573 | &setlist, &showlist); |
| 574 | |
| 575 | add_info ("dcache", dcache_info, |
| 576 | _("\ |
| 577 | Print information on the dcache performance.\n\ |
| 578 | With no arguments, this command prints the cache configuration and a\n\ |
| 579 | summary of each line in the cache. Use \"info dcache <lineno> to dump\"\n\ |
| 580 | the contents of a given line.")); |
| 581 | } |