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