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.  Otherwise return NULL.  */
 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    The result is 1 for success, 0 if the (entire) cache line
 274    wasn't readable.  */
 275
 276 static int
 277 dcache_read_line (DCACHE *dcache, struct dcache_block *db)
 278 {
 279   CORE_ADDR memaddr;
 280   gdb_byte *myaddr;
 281   int len;
 282   int res;
 283   int reg_len;
 284   struct mem_region *region;
 285
 286   len = LINE_SIZE;
 287   memaddr = db->addr;
 288   myaddr  = db->data;
 289
 290   while (len > 0)
 291     {
 292       /* Don't overrun if this block is right at the end of the region.  */
 293       region = lookup_mem_region (memaddr);
 294       if (region->hi == 0 || memaddr + len < region->hi)
 295         reg_len = len;
 296       else
 297         reg_len = region->hi - memaddr;
 298
 299       /* Skip non-readable regions.  The cache attribute can be ignored,
 300          since we may be loading this for a stack access.  */
 301       if (region->attrib.mode == MEM_WO)
 302         {
 303           memaddr += reg_len;
 304           myaddr  += reg_len;
 305           len     -= reg_len;
 306           continue;
 307         }
 308
 309       res = target_read (&current_target, TARGET_OBJECT_RAW_MEMORY,
 310                          NULL, myaddr, memaddr, reg_len);
 311       if (res < reg_len)
 312         return 0;
 313
 314       memaddr += res;
 315       myaddr += res;
 316       len -= res;
 317     }
 318
 319   return 1;
 320 }
 321
 322 /* Get a free cache block, put or keep it on the valid list,
 323    and return its address.  */
 324
 325 static struct dcache_block *
 326 dcache_alloc (DCACHE *dcache, CORE_ADDR addr)
 327 {
 328   struct dcache_block *db;
 329
 330   if (dcache->size >= DCACHE_SIZE)
 331     {
 332       /* Evict the least recently allocated line.  */
 333       db = dcache->oldest;
 334       remove_block (&dcache->oldest, db);
 335
 336       splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
 337     }
 338   else
 339     {
 340       db = dcache->freelist;
 341       if (db)
 342         remove_block (&dcache->freelist, db);
 343       else
 344         db = xmalloc (sizeof (struct dcache_block));
 345
 346       dcache->size++;
 347     }
 348
 349   db->addr = MASK (addr);
 350   db->refs = 0;
 351
 352   /* Put DB at the end of the list, it's the newest.  */
 353   append_block (&dcache->oldest, db);
 354
 355   splay_tree_insert (dcache->tree, (splay_tree_key) db->addr,
 356                      (splay_tree_value) db);
 357
 358   return db;
 359 }
 360
 361 /* Using the data cache DCACHE, store in *PTR the contents of the byte at
 362    address ADDR in the remote machine.
 363
 364    Returns 1 for success, 0 for error.  */
 365
 366 static int
 367 dcache_peek_byte (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr)
 368 {
 369   struct dcache_block *db = dcache_hit (dcache, addr);
 370
 371   if (!db)
 372     {
 373       db = dcache_alloc (dcache, addr);
 374
 375       if (!dcache_read_line (dcache, db))
 376          return 0;
 377     }
 378
 379   *ptr = db->data[XFORM (addr)];
 380   return 1;
 381 }
 382
 383 /* Write the byte at PTR into ADDR in the data cache.
 384
 385    The caller is responsible for also promptly writing the data
 386    through to target memory.
 387
 388    If addr is not in cache, this function does nothing; writing to
 389    an area of memory which wasn't present in the cache doesn't cause
 390    it to be loaded in.
 391
 392    Always return 1 (meaning success) to simplify dcache_xfer_memory.  */
 393
 394 static int
 395 dcache_poke_byte (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr)
 396 {
 397   struct dcache_block *db = dcache_hit (dcache, addr);
 398
 399   if (db)
 400     db->data[XFORM (addr)] = *ptr;
 401
 402   return 1;
 403 }
 404
 405 static int
 406 dcache_splay_tree_compare (splay_tree_key a, splay_tree_key b)
 407 {
 408   if (a > b)
 409     return 1;
 410   else if (a == b)
 411     return 0;
 412   else
 413     return -1;
 414 }
 415
 416 /* Allocate and initialize a data cache.  */
 417
 418 DCACHE *
 419 dcache_init (void)
 420 {
 421   DCACHE *dcache;
 422   int i;
 423
 424   dcache = (DCACHE *) xmalloc (sizeof (*dcache));
 425
 426   dcache->tree = splay_tree_new (dcache_splay_tree_compare,
 427                                  NULL,
 428                                  NULL);
 429
 430   dcache->oldest = NULL;
 431   dcache->freelist = NULL;
 432   dcache->size = 0;
 433   dcache->ptid = null_ptid;
 434   last_cache = dcache;
 435
 436   return dcache;
 437 }
 438
 439 /* BLOCK_FUNC routine for dcache_free.  */
 440
 441 static void
 442 free_block (struct dcache_block *block, void *param)
 443 {
 444   free (block);
 445 }
 446
 447 /* Free a data cache.  */
 448
 449 void
 450 dcache_free (DCACHE *dcache)
 451 {
 452   if (last_cache == dcache)
 453     last_cache = NULL;
 454
 455   splay_tree_delete (dcache->tree);
 456   for_each_block (&dcache->oldest, free_block, NULL);
 457   for_each_block (&dcache->freelist, free_block, NULL);
 458   xfree (dcache);
 459 }
 460
 461 /* Read or write LEN bytes from inferior memory at MEMADDR, transferring
 462    to or from debugger address MYADDR.  Write to inferior if SHOULD_WRITE is
 463    nonzero.
 464
 465    Return the number of bytes actually transfered, or -1 if the
 466    transfer is not supported or otherwise fails.  Return of a non-negative
 467    value less than LEN indicates that no further transfer is possible.
 468    NOTE: This is different than the to_xfer_partial interface, in which
 469    positive values less than LEN mean further transfers may be possible.  */
 470
 471 int
 472 dcache_xfer_memory (struct target_ops *ops, DCACHE *dcache,
 473                     CORE_ADDR memaddr, gdb_byte *myaddr,
 474                     int len, int should_write)
 475 {
 476   int i;
 477   int res;
 478   int (*xfunc) (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr);
 479   xfunc = should_write ? dcache_poke_byte : dcache_peek_byte;
 480
 481   /* If this is a different inferior from what we've recorded,
 482      flush the cache.  */
 483
 484   if (! ptid_equal (inferior_ptid, dcache->ptid))
 485     {
 486       dcache_invalidate (dcache);
 487       dcache->ptid = inferior_ptid;
 488     }
 489
 490   /* Do write-through first, so that if it fails, we don't write to
 491      the cache at all.  */
 492
 493   if (should_write)
 494     {
 495       res = target_write (ops, TARGET_OBJECT_RAW_MEMORY,
 496                           NULL, myaddr, memaddr, len);
 497       if (res <= 0)
 498         return res;
 499       /* Update LEN to what was actually written.  */
 500       len = res;
 501     }
 502
 503   for (i = 0; i < len; i++)
 504     {
 505       if (!xfunc (dcache, memaddr + i, myaddr + i))
 506         {
 507           /* That failed.  Discard its cache line so we don't have a
 508              partially read line.  */
 509           dcache_invalidate_line (dcache, memaddr + i);
 510           /* If we're writing, we still wrote LEN bytes.  */
 511           if (should_write)
 512             return len;
 513           else
 514             return i;
 515         }
 516     }
 517
 518   return len;
 519 }
 520
 521 /* FIXME: There would be some benefit to making the cache write-back and
 522    moving the writeback operation to a higher layer, as it could occur
 523    after a sequence of smaller writes have been completed (as when a stack
 524    frame is constructed for an inferior function call).  Note that only
 525    moving it up one level to target_xfer_memory[_partial]() is not
 526    sufficient since we want to coalesce memory transfers that are
 527    "logically" connected but not actually a single call to one of the
 528    memory transfer functions.  */
 529
 530 /* Just update any cache lines which are already present.  This is called
 531    by memory_xfer_partial in cases where the access would otherwise not go
 532    through the cache.  */
 533
 534 void
 535 dcache_update (DCACHE *dcache, CORE_ADDR memaddr, gdb_byte *myaddr, int len)
 536 {
 537   int i;
 538   for (i = 0; i < len; i++)
 539     dcache_poke_byte (dcache, memaddr + i, myaddr + i);
 540 }
 541
 542 static void
 543 dcache_print_line (int index)
 544 {
 545   splay_tree_node n;
 546   struct dcache_block *db;
 547   int i, j;
 548
 549   if (!last_cache)
 550     {
 551       printf_filtered (_("No data cache available.\n"));
 552       return;
 553     }
 554
 555   n = splay_tree_min (last_cache->tree);
 556
 557   for (i = index; i > 0; --i)
 558     {
 559       if (!n)
 560         break;
 561       n = splay_tree_successor (last_cache->tree, n->key);
 562     }
 563
 564   if (!n)
 565     {
 566       printf_filtered (_("No such cache line exists.\n"));
 567       return;
 568     }
 569
 570   db = (struct dcache_block *) n->value;
 571
 572   printf_filtered (_("Line %d: address %s [%d hits]\n"),
 573                    index, paddress (target_gdbarch, db->addr), db->refs);
 574
 575   for (j = 0; j < LINE_SIZE; j++)
 576     {
 577       printf_filtered ("%02x ", db->data[j]);
 578
 579       /* Print a newline every 16 bytes (48 characters) */
 580       if ((j % 16 == 15) && (j != LINE_SIZE - 1))
 581         printf_filtered ("\n");
 582     }
 583   printf_filtered ("\n");
 584 }
 585
 586 static void
 587 dcache_info (char *exp, int tty)
 588 {
 589   splay_tree_node n;
 590   int i, refcount, lineno;
 591
 592   if (exp)
 593     {
 594       char *linestart;
 595       i = strtol (exp, &linestart, 10);
 596       if (linestart == exp || i < 0)
 597         {
 598           printf_filtered (_("Usage: info dcache [linenumber]\n"));
 599           return;
 600         }
 601
 602       dcache_print_line (i);
 603       return;
 604     }
 605
 606   printf_filtered (_("Dcache line width %d, maximum size %d\n"),
 607                    LINE_SIZE, DCACHE_SIZE);
 608
 609   if (!last_cache || ptid_equal (last_cache->ptid, null_ptid))
 610     {
 611       printf_filtered (_("No data cache available.\n"));
 612       return;
 613     }
 614
 615   printf_filtered (_("Contains data for %s\n"),
 616                    target_pid_to_str (last_cache->ptid));
 617
 618   refcount = 0;
 619
 620   n = splay_tree_min (last_cache->tree);
 621   i = 0;
 622
 623   while (n)
 624     {
 625       struct dcache_block *db = (struct dcache_block *) n->value;
 626
 627       printf_filtered (_("Line %d: address %s [%d hits]\n"),
 628                        i, paddress (target_gdbarch, db->addr), db->refs);
 629       i++;
 630       refcount += db->refs;
 631
 632       n = splay_tree_successor (last_cache->tree, n->key);
 633     }
 634
 635   printf_filtered (_("Cache state: %d active lines, %d hits\n"), i, refcount);
 636 }
 637
 638 void
 639 _initialize_dcache (void)
 640 {
 641   add_setshow_boolean_cmd ("remotecache", class_support,
 642                            &dcache_enabled_p, _("\
 643 Set cache use for remote targets."), _("\
 644 Show cache use for remote targets."), _("\
 645 This used to enable the data cache for remote targets.  The cache\n\
 646 functionality is now controlled by the memory region system and the\n\
 647 \"stack-cache\" flag; \"remotecache\" now does nothing and\n\
 648 exists only for compatibility reasons."),
 649                            NULL,
 650                            show_dcache_enabled_p,
 651                            &setlist, &showlist);
 652
 653   add_info ("dcache", dcache_info,
 654             _("\
 655 Print information on the dcache performance.\n\
 656 With no arguments, this command prints the cache configuration and a\n\
 657 summary of each line in the cache.  Use \"info dcache <lineno> to dump\"\n\
 658 the contents of a given line."));
 659 }