gdb/dcache.c

   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.  Within each line we
  45    remember the address of the line (which must be a multiple of
  46    LINE_SIZE) and the 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   /* for least-recently-allocated and free lists */
  92   struct dcache_block *prev;
  93   struct dcache_block *next;
  94
  95   CORE_ADDR addr;               /* address of data */
  96   gdb_byte data[LINE_SIZE];     /* bytes at given address */
  97   int refs;                     /* # hits */
  98 };
  99
 100 struct dcache_struct
 101 {
 102   splay_tree tree;
 103   struct dcache_block *oldest; /* least-recently-allocated list */
 104
 105   /* The free list is maintained identically to OLDEST to simplify
 106      the code: we only need one set of accessors.  */
 107   struct dcache_block *freelist;
 108
 109   /* The number of in-use lines in the cache.  */
 110   int size;
 111
 112   /* The ptid of last inferior to use cache or null_ptid.  */
 113   ptid_t ptid;
 114 };
 115
 116 typedef void (block_func) (struct dcache_block *block, void *param);
 117
 118 static struct dcache_block *dcache_hit (DCACHE *dcache, CORE_ADDR addr);
 119
 120 static int dcache_write_line (DCACHE *dcache, struct dcache_block *db);
 121
 122 static int dcache_read_line (DCACHE *dcache, struct dcache_block *db);
 123
 124 static struct dcache_block *dcache_alloc (DCACHE *dcache, CORE_ADDR addr);
 125
 126 static void dcache_info (char *exp, int tty);
 127
 128 void _initialize_dcache (void);
 129
 130 static int dcache_enabled_p = 0; /* OBSOLETE */
 131
 132 static void
 133 show_dcache_enabled_p (struct ui_file *file, int from_tty,
 134                        struct cmd_list_element *c, const char *value)
 135 {
 136   fprintf_filtered (file, _("Deprecated remotecache flag is %s.\n"), value);
 137 }
 138
 139 static DCACHE *last_cache; /* Used by info dcache */
 140
 141 /* Add BLOCK to circular block list BLIST, behind the block at *BLIST.
 142    *BLIST is not updated (unless it was previously NULL of course).
 143    This is for the least-recently-allocated list's sake:
 144    BLIST points to the oldest block.
 145    ??? This makes for poor cache usage of the free list,
 146    but is it measurable?  */
 147
 148 static void
 149 append_block (struct dcache_block **blist, struct dcache_block *block)
 150 {
 151   if (*blist)
 152     {
 153       block->next = *blist;
 154       block->prev = (*blist)->prev;
 155       block->prev->next = block;
 156       (*blist)->prev = block;
 157       /* We don't update *BLIST here to maintain the invariant that for the
 158          least-recently-allocated list *BLIST points to the oldest block.  */
 159     }
 160   else
 161     {
 162       block->next = block;
 163       block->prev = block;
 164       *blist = block;
 165     }
 166 }
 167
 168 /* Remove BLOCK from circular block list BLIST.  */
 169
 170 static void
 171 remove_block (struct dcache_block **blist, struct dcache_block *block)
 172 {
 173   if (block->next == block)
 174     {
 175       *blist = NULL;
 176     }
 177   else
 178     {
 179       block->next->prev = block->prev;
 180       block->prev->next = block->next;
 181       /* If we removed the block *BLIST points to, shift it to the next block
 182          to maintain the invariant that for the least-recently-allocated list
 183          *BLIST points to the oldest block.  */
 184       if (*blist == block)
 185         *blist = block->next;
 186     }
 187 }
 188
 189 /* Iterate over all elements in BLIST, calling FUNC.
 190    PARAM is passed to FUNC.
 191    FUNC may remove the block it's passed, but only that block.  */
 192
 193 static void
 194 for_each_block (struct dcache_block **blist, block_func *func, void *param)
 195 {
 196   struct dcache_block *db;
 197
 198   if (*blist == NULL)
 199     return;
 200
 201   db = *blist;
 202   do
 203     {
 204       struct dcache_block *next = db->next;
 205
 206       func (db, param);
 207       db = next;
 208     }
 209   while (*blist && db != *blist);
 210 }
 211
 212 /* BLOCK_FUNC function for dcache_invalidate.
 213    This doesn't remove the block from the oldest list on purpose.
 214    dcache_invalidate will do it later.  */
 215
 216 static void
 217 invalidate_block (struct dcache_block *block, void *param)
 218 {
 219   DCACHE *dcache = (DCACHE *) param;
 220
 221   splay_tree_remove (dcache->tree, (splay_tree_key) block->addr);
 222   append_block (&dcache->freelist, block);
 223 }
 224
 225 /* Free all the data cache blocks, thus discarding all cached data.  */
 226
 227 void
 228 dcache_invalidate (DCACHE *dcache)
 229 {
 230   for_each_block (&dcache->oldest, invalidate_block, dcache);
 231
 232   dcache->oldest = NULL;
 233   dcache->size = 0;
 234   dcache->ptid = null_ptid;
 235 }
 236
 237 /* Invalidate the line associated with ADDR.  */
 238
 239 static void
 240 dcache_invalidate_line (DCACHE *dcache, CORE_ADDR addr)
 241 {
 242   struct dcache_block *db = dcache_hit (dcache, addr);
 243
 244   if (db)
 245     {
 246       splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
 247       remove_block (&dcache->oldest, db);
 248       append_block (&dcache->freelist, db);
 249       --dcache->size;
 250     }
 251 }
 252
 253 /* If addr is present in the dcache, return the address of the block
 254    containing it.  */
 255
 256 static struct dcache_block *
 257 dcache_hit (DCACHE *dcache, CORE_ADDR addr)
 258 {
 259   struct dcache_block *db;
 260
 261   splay_tree_node node = splay_tree_lookup (dcache->tree,
 262                                             (splay_tree_key) MASK (addr));
 263
 264   if (!node)
 265     return NULL;
 266
 267   db = (struct dcache_block *) node->value;
 268   db->refs++;
 269   return db;
 270 }
 271
 272 /* Fill a cache line from target memory.  */
 273
 274 static int
 275 dcache_read_line (DCACHE *dcache, struct dcache_block *db)
 276 {
 277   CORE_ADDR memaddr;
 278   gdb_byte *myaddr;
 279   int len;
 280   int res;
 281   int reg_len;
 282   struct mem_region *region;
 283
 284   len = LINE_SIZE;
 285   memaddr = db->addr;
 286   myaddr  = db->data;
 287
 288   while (len > 0)
 289     {
 290       /* Don't overrun if this block is right at the end of the region.  */
 291       region = lookup_mem_region (memaddr);
 292       if (region->hi == 0 || memaddr + len < region->hi)
 293         reg_len = len;
 294       else
 295         reg_len = region->hi - memaddr;
 296
 297       /* Skip non-readable regions.  The cache attribute can be ignored,
 298          since we may be loading this for a stack access.  */
 299       if (region->attrib.mode == MEM_WO)
 300         {
 301           memaddr += reg_len;
 302           myaddr  += reg_len;
 303           len     -= reg_len;
 304           continue;
 305         }
 306
 307       res = target_read (&current_target, TARGET_OBJECT_RAW_MEMORY,
 308                          NULL, myaddr, memaddr, reg_len);
 309       if (res < reg_len)
 310         return 0;
 311
 312       memaddr += res;
 313       myaddr += res;
 314       len -= res;
 315     }
 316
 317   return 1;
 318 }
 319
 320 /* Get a free cache block, put or keep it on the valid list,
 321    and return its address.  */
 322
 323 static struct dcache_block *
 324 dcache_alloc (DCACHE *dcache, CORE_ADDR addr)
 325 {
 326   struct dcache_block *db;
 327
 328   if (dcache->size >= DCACHE_SIZE)
 329     {
 330       /* Evict the least recently allocated line.  */
 331       db = dcache->oldest;
 332       remove_block (&dcache->oldest, db);
 333
 334       splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
 335     }
 336   else
 337     {
 338       db = dcache->freelist;
 339       if (db)
 340         remove_block (&dcache->freelist, db);
 341       else
 342         db = xmalloc (sizeof (struct dcache_block));
 343
 344       dcache->size++;
 345     }
 346
 347   db->addr = MASK (addr);
 348   db->refs = 0;
 349
 350   /* Put DB at the end of the list, it's the newest.  */
 351   append_block (&dcache->oldest, db);
 352
 353   splay_tree_insert (dcache->tree, (splay_tree_key) db->addr,
 354                      (splay_tree_value) db);
 355
 356   return db;
 357 }
 358
 359 /* Using the data cache DCACHE return the contents of the byte at
 360    address ADDR in the remote machine.
 361
 362    Returns 1 for success, 0 for error.  */
 363
 364 static int
 365 dcache_peek_byte (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr)
 366 {
 367   struct dcache_block *db = dcache_hit (dcache, addr);
 368
 369   if (!db)
 370     {
 371       db = dcache_alloc (dcache, addr);
 372
 373       if (!dcache_read_line (dcache, db))
 374          return 0;
 375     }
 376
 377   *ptr = db->data[XFORM (addr)];
 378   return 1;
 379 }
 380
 381 /* Write the byte at PTR into ADDR in the data cache.
 382
 383    The caller is responsible for also promptly writing the data
 384    through to target memory.
 385
 386    If addr is not in cache, this function does nothing; writing to
 387    an area of memory which wasn't present in the cache doesn't cause
 388    it to be loaded in.
 389
 390    Always return 1 (meaning success) to simplify dcache_xfer_memory.  */
 391
 392 static int
 393 dcache_poke_byte (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr)
 394 {
 395   struct dcache_block *db = dcache_hit (dcache, addr);
 396
 397   if (db)
 398     db->data[XFORM (addr)] = *ptr;
 399
 400   return 1;
 401 }
 402
 403 static int
 404 dcache_splay_tree_compare (splay_tree_key a, splay_tree_key b)
 405 {
 406   if (a > b)
 407     return 1;
 408   else if (a == b)
 409     return 0;
 410   else
 411     return -1;
 412 }
 413
 414 /* Initialize the data cache.  */
 415
 416 DCACHE *
 417 dcache_init (void)
 418 {
 419   DCACHE *dcache;
 420   int i;
 421
 422   dcache = (DCACHE *) xmalloc (sizeof (*dcache));
 423
 424   dcache->tree = splay_tree_new (dcache_splay_tree_compare,
 425                                  NULL,
 426                                  NULL);
 427
 428   dcache->oldest = NULL;
 429   dcache->freelist = NULL;
 430   dcache->size = 0;
 431   dcache->ptid = null_ptid;
 432   last_cache = dcache;
 433
 434   return dcache;
 435 }
 436
 437 /* BLOCK_FUNC routine for dcache_free.  */
 438
 439 static void
 440 free_block (struct dcache_block *block, void *param)
 441 {
 442   free (block);
 443 }
 444
 445 /* Free a data cache.  */
 446
 447 void
 448 dcache_free (DCACHE *dcache)
 449 {
 450   if (last_cache == dcache)
 451     last_cache = NULL;
 452
 453   splay_tree_delete (dcache->tree);
 454   for_each_block (&dcache->oldest, free_block, NULL);
 455   for_each_block (&dcache->freelist, free_block, NULL);
 456   xfree (dcache);
 457 }
 458
 459 /* Read or write LEN bytes from inferior memory at MEMADDR, transferring
 460    to or from debugger address MYADDR.  Write to inferior if SHOULD_WRITE is
 461    nonzero.
 462
 463    The meaning of the result is the same as for target_write.  */
 464
 465 int
 466 dcache_xfer_memory (struct target_ops *ops, DCACHE *dcache,
 467                     CORE_ADDR memaddr, gdb_byte *myaddr,
 468                     int len, int should_write)
 469 {
 470   int i;
 471   int res;
 472   int (*xfunc) (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr);
 473   xfunc = should_write ? dcache_poke_byte : dcache_peek_byte;
 474
 475   /* If this is a different inferior from what we've recorded,
 476      flush the cache.  */
 477
 478   if (! ptid_equal (inferior_ptid, dcache->ptid))
 479     {
 480       dcache_invalidate (dcache);
 481       dcache->ptid = inferior_ptid;
 482     }
 483
 484   /* Do write-through first, so that if it fails, we don't write to
 485      the cache at all.  */
 486
 487   if (should_write)
 488     {
 489       res = target_write (ops, TARGET_OBJECT_RAW_MEMORY,
 490                           NULL, myaddr, memaddr, len);
 491       if (res <= 0)
 492         return res;
 493       /* Update LEN to what was actually written.  */
 494       len = res;
 495     }
 496
 497   for (i = 0; i < len; i++)
 498     {
 499       if (!xfunc (dcache, memaddr + i, myaddr + i))
 500         {
 501           /* That failed.  Discard its cache line so we don't have a
 502              partially read line.  */
 503           dcache_invalidate_line (dcache, memaddr + i);
 504           /* If we're writing, we still wrote LEN bytes.  */
 505           if (should_write)
 506             return len;
 507           else
 508             return i;
 509         }
 510     }
 511
 512   return len;
 513 }
 514
 515 /* FIXME: There would be some benefit to making the cache write-back and
 516    moving the writeback operation to a higher layer, as it could occur
 517    after a sequence of smaller writes have been completed (as when a stack
 518    frame is constructed for an inferior function call).  Note that only
 519    moving it up one level to target_xfer_memory[_partial]() is not
 520    sufficient since we want to coalesce memory transfers that are
 521    "logically" connected but not actually a single call to one of the
 522    memory transfer functions.  */
 523
 524 /* Just update any cache lines which are already present.  This is called
 525    by memory_xfer_partial in cases where the access would otherwise not go
 526    through the cache.  */
 527
 528 void
 529 dcache_update (DCACHE *dcache, CORE_ADDR memaddr, gdb_byte *myaddr, int len)
 530 {
 531   int i;
 532   for (i = 0; i < len; i++)
 533     dcache_poke_byte (dcache, memaddr + i, myaddr + i);
 534 }
 535
 536 static void
 537 dcache_print_line (int index)
 538 {
 539   splay_tree_node n;
 540   struct dcache_block *db;
 541   int i, j;
 542
 543   if (!last_cache)
 544     {
 545       printf_filtered (_("No data cache available.\n"));
 546       return;
 547     }
 548
 549   n = splay_tree_min (last_cache->tree);
 550
 551   for (i = index; i > 0; --i)
 552     {
 553       if (!n)
 554         break;
 555       n = splay_tree_successor (last_cache->tree, n->key);
 556     }
 557
 558   if (!n)
 559     {
 560       printf_filtered (_("No such cache line exists.\n"));
 561       return;
 562     }
 563
 564   db = (struct dcache_block *) n->value;
 565
 566   printf_filtered (_("Line %d: address %s [%d hits]\n"),
 567                    index, paddress (target_gdbarch, db->addr), db->refs);
 568
 569   for (j = 0; j < LINE_SIZE; j++)
 570     {
 571       printf_filtered ("%02x ", db->data[j]);
 572
 573       /* Print a newline every 16 bytes (48 characters) */
 574       if ((j % 16 == 15) && (j != LINE_SIZE - 1))
 575         printf_filtered ("\n");
 576     }
 577   printf_filtered ("\n");
 578 }
 579
 580 static void
 581 dcache_info (char *exp, int tty)
 582 {
 583   splay_tree_node n;
 584   int i, refcount, lineno;
 585
 586   if (exp)
 587     {
 588       char *linestart;
 589       i = strtol (exp, &linestart, 10);
 590       if (linestart == exp || i < 0)
 591         {
 592           printf_filtered (_("Usage: info dcache [linenumber]\n"));
 593           return;
 594         }
 595
 596       dcache_print_line (i);
 597       return;
 598     }
 599
 600   printf_filtered (_("Dcache line width %d, maximum size %d\n"),
 601                    LINE_SIZE, DCACHE_SIZE);
 602
 603   if (!last_cache || ptid_equal (last_cache->ptid, null_ptid))
 604     {
 605       printf_filtered (_("No data cache available.\n"));
 606       return;
 607     }
 608
 609   printf_filtered (_("Contains data for %s\n"),
 610                    target_pid_to_str (last_cache->ptid));
 611
 612   refcount = 0;
 613
 614   n = splay_tree_min (last_cache->tree);
 615   i = 0;
 616
 617   while (n)
 618     {
 619       struct dcache_block *db = (struct dcache_block *) n->value;
 620
 621       printf_filtered (_("Line %d: address %s [%d hits]\n"),
 622                        i, paddress (target_gdbarch, db->addr), db->refs);
 623       i++;
 624       refcount += db->refs;
 625
 626       n = splay_tree_successor (last_cache->tree, n->key);
 627     }
 628
 629   printf_filtered (_("Cache state: %d active lines, %d hits\n"), i, refcount);
 630 }
 631
 632 void
 633 _initialize_dcache (void)
 634 {
 635   add_setshow_boolean_cmd ("remotecache", class_support,
 636                            &dcache_enabled_p, _("\
 637 Set cache use for remote targets."), _("\
 638 Show cache use for remote targets."), _("\
 639 This used to enable the data cache for remote targets.  The cache\n\
 640 functionality is now controlled by the memory region system and the\n\
 641 \"stack-cache\" flag; \"remotecache\" now does nothing and\n\
 642 exists only for compatibility reasons."),
 643                            NULL,
 644                            show_dcache_enabled_p,
 645                            &setlist, &showlist);
 646
 647   add_info ("dcache", dcache_info,
 648             _("\
 649 Print information on the dcache performance.\n\
 650 With no arguments, this command prints the cache configuration and a\n\
 651 summary of each line in the cache.  Use \"info dcache <lineno> to dump\"\n\
 652 the contents of a given line."));
 653 }