gdb/dcache.c

   1 /* Caching code for GDB, the GNU debugger.
   2
   3    Copyright (C) 1992-2020 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 #include "defs.h"
  21 #include "dcache.h"
  22 #include "gdbcmd.h"
  23 #include "gdbcore.h"
  24 #include "target-dcache.h"
  25 #include "inferior.h"
  26 #include "splay-tree.h"
  27 #include "gdbarch.h"
  28
  29 /* Commands with a prefix of `{set,show} dcache'.  */
  30 static struct cmd_list_element *dcache_set_list = NULL;
  31 static struct cmd_list_element *dcache_show_list = NULL;
  32
  33 /* The data cache could lead to incorrect results because it doesn't
  34    know about volatile variables, thus making it impossible to debug
  35    functions which use memory mapped I/O devices.  Set the nocache
  36    memory region attribute in those cases.
  37
  38    In general the dcache speeds up performance.  Some speed improvement
  39    comes from the actual caching mechanism, but the major gain is in
  40    the reduction of the remote protocol overhead; instead of reading
  41    or writing a large area of memory in 4 byte requests, the cache
  42    bundles up the requests into LINE_SIZE chunks, reducing overhead
  43    significantly.  This is most useful when accessing a large amount
  44    of data, such as when performing a backtrace.
  45
  46    The cache is a splay tree along with a linked list for replacement.
  47    Each block caches a LINE_SIZE area of memory.  Within each line we
  48    remember the address of the line (which must be a multiple of
  49    LINE_SIZE) and the actual data block.
  50
  51    Lines are only allocated as needed, so DCACHE_SIZE really specifies the
  52    *maximum* number of lines in the cache.
  53
  54    At present, the cache is write-through rather than writeback: as soon
  55    as data is written to the cache, it is also immediately written to
  56    the target.  Therefore, cache lines are never "dirty".  Whether a given
  57    line is valid or not depends on where it is stored in the dcache_struct;
  58    there is no per-block valid flag.  */
  59
  60 /* NOTE: Interaction of dcache and memory region attributes
  61
  62    As there is no requirement that memory region attributes be aligned
  63    to or be a multiple of the dcache page size, dcache_read_line() and
  64    dcache_write_line() must break up the page by memory region.  If a
  65    chunk does not have the cache attribute set, an invalid memory type
  66    is set, etc., then the chunk is skipped.  Those chunks are handled
  67    in target_xfer_memory() (or target_xfer_memory_partial()).
  68
  69    This doesn't occur very often.  The most common occurrence is when
  70    the last bit of the .text segment and the first bit of the .data
  71    segment fall within the same dcache page with a ro/cacheable memory
  72    region defined for the .text segment and a rw/non-cacheable memory
  73    region defined for the .data segment.  */
  74
  75 /* The maximum number of lines stored.  The total size of the cache is
  76    equal to DCACHE_SIZE times LINE_SIZE.  */
  77 #define DCACHE_DEFAULT_SIZE 4096
  78 static unsigned dcache_size = DCACHE_DEFAULT_SIZE;
  79
  80 /* The default size of a cache line.  Smaller values reduce the time taken to
  81    read a single byte and make the cache more granular, but increase
  82    overhead and reduce the effectiveness of the cache as a prefetcher.  */
  83 #define DCACHE_DEFAULT_LINE_SIZE 64
  84 static unsigned dcache_line_size = DCACHE_DEFAULT_LINE_SIZE;
  85
  86 /* Each cache block holds LINE_SIZE bytes of data
  87    starting at a multiple-of-LINE_SIZE address.  */
  88
  89 #define LINE_SIZE_MASK(dcache)  ((dcache->line_size - 1))
  90 #define XFORM(dcache, x)        ((x) & LINE_SIZE_MASK (dcache))
  91 #define MASK(dcache, x)         ((x) & ~LINE_SIZE_MASK (dcache))
  92
  93 struct dcache_block
  94 {
  95   /* For least-recently-allocated and free lists.  */
  96   struct dcache_block *prev;
  97   struct dcache_block *next;
  98
  99   CORE_ADDR addr;               /* address of data */
 100   int refs;                     /* # hits */
 101   gdb_byte data[1];             /* line_size bytes at given address */
 102 };
 103
 104 struct dcache_struct
 105 {
 106   splay_tree tree;
 107   struct dcache_block *oldest; /* least-recently-allocated list.  */
 108
 109   /* The free list is maintained identically to OLDEST to simplify
 110      the code: we only need one set of accessors.  */
 111   struct dcache_block *freelist;
 112
 113   /* The number of in-use lines in the cache.  */
 114   int size;
 115   CORE_ADDR line_size;  /* current line_size.  */
 116
 117   /* The ptid of last inferior to use cache or null_ptid.  */
 118   ptid_t ptid;
 119 };
 120
 121 typedef void (block_func) (struct dcache_block *block, void *param);
 122
 123 static struct dcache_block *dcache_hit (DCACHE *dcache, CORE_ADDR addr);
 124
 125 static int dcache_read_line (DCACHE *dcache, struct dcache_block *db);
 126
 127 static struct dcache_block *dcache_alloc (DCACHE *dcache, CORE_ADDR addr);
 128
 129 static bool dcache_enabled_p = false; /* OBSOLETE */
 130
 131 static void
 132 show_dcache_enabled_p (struct ui_file *file, int from_tty,
 133                        struct cmd_list_element *c, const char *value)
 134 {
 135   fprintf_filtered (file, _("Deprecated remotecache flag is %s.\n"), value);
 136 }
 137
 138 /* Add BLOCK to circular block list BLIST, behind the block at *BLIST.
 139    *BLIST is not updated (unless it was previously NULL of course).
 140    This is for the least-recently-allocated list's sake:
 141    BLIST points to the oldest block.
 142    ??? This makes for poor cache usage of the free list,
 143    but is it measurable?  */
 144
 145 static void
 146 append_block (struct dcache_block **blist, struct dcache_block *block)
 147 {
 148   if (*blist)
 149     {
 150       block->next = *blist;
 151       block->prev = (*blist)->prev;
 152       block->prev->next = block;
 153       (*blist)->prev = block;
 154       /* We don't update *BLIST here to maintain the invariant that for the
 155          least-recently-allocated list *BLIST points to the oldest block.  */
 156     }
 157   else
 158     {
 159       block->next = block;
 160       block->prev = block;
 161       *blist = block;
 162     }
 163 }
 164
 165 /* Remove BLOCK from circular block list BLIST.  */
 166
 167 static void
 168 remove_block (struct dcache_block **blist, struct dcache_block *block)
 169 {
 170   if (block->next == block)
 171     {
 172       *blist = NULL;
 173     }
 174   else
 175     {
 176       block->next->prev = block->prev;
 177       block->prev->next = block->next;
 178       /* If we removed the block *BLIST points to, shift it to the next block
 179          to maintain the invariant that for the least-recently-allocated list
 180          *BLIST points to the oldest block.  */
 181       if (*blist == block)
 182         *blist = block->next;
 183     }
 184 }
 185
 186 /* Iterate over all elements in BLIST, calling FUNC.
 187    PARAM is passed to FUNC.
 188    FUNC may remove the block it's passed, but only that block.  */
 189
 190 static void
 191 for_each_block (struct dcache_block **blist, block_func *func, void *param)
 192 {
 193   struct dcache_block *db;
 194
 195   if (*blist == NULL)
 196     return;
 197
 198   db = *blist;
 199   do
 200     {
 201       struct dcache_block *next = db->next;
 202
 203       func (db, param);
 204       db = next;
 205     }
 206   while (*blist && db != *blist);
 207 }
 208
 209 /* BLOCK_FUNC routine for dcache_free.  */
 210
 211 static void
 212 free_block (struct dcache_block *block, void *param)
 213 {
 214   xfree (block);
 215 }
 216
 217 /* Free a data cache.  */
 218
 219 void
 220 dcache_free (DCACHE *dcache)
 221 {
 222   splay_tree_delete (dcache->tree);
 223   for_each_block (&dcache->oldest, free_block, NULL);
 224   for_each_block (&dcache->freelist, free_block, NULL);
 225   xfree (dcache);
 226 }
 227
 228
 229 /* BLOCK_FUNC function for dcache_invalidate.
 230    This doesn't remove the block from the oldest list on purpose.
 231    dcache_invalidate will do it later.  */
 232
 233 static void
 234 invalidate_block (struct dcache_block *block, void *param)
 235 {
 236   DCACHE *dcache = (DCACHE *) param;
 237
 238   splay_tree_remove (dcache->tree, (splay_tree_key) block->addr);
 239   append_block (&dcache->freelist, block);
 240 }
 241
 242 /* Free all the data cache blocks, thus discarding all cached data.  */
 243
 244 void
 245 dcache_invalidate (DCACHE *dcache)
 246 {
 247   for_each_block (&dcache->oldest, invalidate_block, dcache);
 248
 249   dcache->oldest = NULL;
 250   dcache->size = 0;
 251   dcache->ptid = null_ptid;
 252
 253   if (dcache->line_size != dcache_line_size)
 254     {
 255       /* We've been asked to use a different line size.
 256          All of our freelist blocks are now the wrong size, so free them.  */
 257
 258       for_each_block (&dcache->freelist, free_block, dcache);
 259       dcache->freelist = NULL;
 260       dcache->line_size = dcache_line_size;
 261     }
 262 }
 263
 264 /* Invalidate the line associated with ADDR.  */
 265
 266 static void
 267 dcache_invalidate_line (DCACHE *dcache, CORE_ADDR addr)
 268 {
 269   struct dcache_block *db = dcache_hit (dcache, addr);
 270
 271   if (db)
 272     {
 273       splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
 274       remove_block (&dcache->oldest, db);
 275       append_block (&dcache->freelist, db);
 276       --dcache->size;
 277     }
 278 }
 279
 280 /* If addr is present in the dcache, return the address of the block
 281    containing it.  Otherwise return NULL.  */
 282
 283 static struct dcache_block *
 284 dcache_hit (DCACHE *dcache, CORE_ADDR addr)
 285 {
 286   struct dcache_block *db;
 287
 288   splay_tree_node node = splay_tree_lookup (dcache->tree,
 289                                             (splay_tree_key) MASK (dcache, addr));
 290
 291   if (!node)
 292     return NULL;
 293
 294   db = (struct dcache_block *) node->value;
 295   db->refs++;
 296   return db;
 297 }
 298
 299 /* Fill a cache line from target memory.
 300    The result is 1 for success, 0 if the (entire) cache line
 301    wasn't readable.  */
 302
 303 static int
 304 dcache_read_line (DCACHE *dcache, struct dcache_block *db)
 305 {
 306   CORE_ADDR memaddr;
 307   gdb_byte *myaddr;
 308   int len;
 309   int res;
 310   int reg_len;
 311   struct mem_region *region;
 312
 313   len = dcache->line_size;
 314   memaddr = db->addr;
 315   myaddr  = db->data;
 316
 317   while (len > 0)
 318     {
 319       /* Don't overrun if this block is right at the end of the region.  */
 320       region = lookup_mem_region (memaddr);
 321       if (region->hi == 0 || memaddr + len < region->hi)
 322         reg_len = len;
 323       else
 324         reg_len = region->hi - memaddr;
 325
 326       /* Skip non-readable regions.  The cache attribute can be ignored,
 327          since we may be loading this for a stack access.  */
 328       if (region->attrib.mode == MEM_WO)
 329         {
 330           memaddr += reg_len;
 331           myaddr  += reg_len;
 332           len     -= reg_len;
 333           continue;
 334         }
 335
 336       res = target_read_raw_memory (memaddr, myaddr, reg_len);
 337       if (res != 0)
 338         return 0;
 339
 340       memaddr += reg_len;
 341       myaddr += reg_len;
 342       len -= reg_len;
 343     }
 344
 345   return 1;
 346 }
 347
 348 /* Get a free cache block, put or keep it on the valid list,
 349    and return its address.  */
 350
 351 static struct dcache_block *
 352 dcache_alloc (DCACHE *dcache, CORE_ADDR addr)
 353 {
 354   struct dcache_block *db;
 355
 356   if (dcache->size >= dcache_size)
 357     {
 358       /* Evict the least recently allocated line.  */
 359       db = dcache->oldest;
 360       remove_block (&dcache->oldest, db);
 361
 362       splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
 363     }
 364   else
 365     {
 366       db = dcache->freelist;
 367       if (db)
 368         remove_block (&dcache->freelist, db);
 369       else
 370         db = ((struct dcache_block *)
 371               xmalloc (offsetof (struct dcache_block, data)
 372                        + dcache->line_size));
 373
 374       dcache->size++;
 375     }
 376
 377   db->addr = MASK (dcache, addr);
 378   db->refs = 0;
 379
 380   /* Put DB at the end of the list, it's the newest.  */
 381   append_block (&dcache->oldest, db);
 382
 383   splay_tree_insert (dcache->tree, (splay_tree_key) db->addr,
 384                      (splay_tree_value) db);
 385
 386   return db;
 387 }
 388
 389 /* Using the data cache DCACHE, store in *PTR the contents of the byte at
 390    address ADDR in the remote machine.
 391
 392    Returns 1 for success, 0 for error.  */
 393
 394 static int
 395 dcache_peek_byte (DCACHE *dcache, CORE_ADDR addr, gdb_byte *ptr)
 396 {
 397   struct dcache_block *db = dcache_hit (dcache, addr);
 398
 399   if (!db)
 400     {
 401       db = dcache_alloc (dcache, addr);
 402
 403       if (!dcache_read_line (dcache, db))
 404          return 0;
 405     }
 406
 407   *ptr = db->data[XFORM (dcache, addr)];
 408   return 1;
 409 }
 410
 411 /* Write the byte at PTR into ADDR in the data cache.
 412
 413    The caller should have written the data through to target memory
 414    already.
 415
 416    If ADDR is not in cache, this function does nothing; writing to an
 417    area of memory which wasn't present in the cache doesn't cause it
 418    to be loaded in.  */
 419
 420 static void
 421 dcache_poke_byte (DCACHE *dcache, CORE_ADDR addr, const gdb_byte *ptr)
 422 {
 423   struct dcache_block *db = dcache_hit (dcache, addr);
 424
 425   if (db)
 426     db->data[XFORM (dcache, addr)] = *ptr;
 427 }
 428
 429 static int
 430 dcache_splay_tree_compare (splay_tree_key a, splay_tree_key b)
 431 {
 432   if (a > b)
 433     return 1;
 434   else if (a == b)
 435     return 0;
 436   else
 437     return -1;
 438 }
 439
 440 /* Allocate and initialize a data cache.  */
 441
 442 DCACHE *
 443 dcache_init (void)
 444 {
 445   DCACHE *dcache = XNEW (DCACHE);
 446
 447   dcache->tree = splay_tree_new (dcache_splay_tree_compare,
 448                                  NULL,
 449                                  NULL);
 450
 451   dcache->oldest = NULL;
 452   dcache->freelist = NULL;
 453   dcache->size = 0;
 454   dcache->line_size = dcache_line_size;
 455   dcache->ptid = null_ptid;
 456
 457   return dcache;
 458 }
 459
 460
 461 /* Read LEN bytes from dcache memory at MEMADDR, transferring to
 462    debugger address MYADDR.  If the data is presently cached, this
 463    fills the cache.  Arguments/return are like the target_xfer_partial
 464    interface.  */
 465
 466 enum target_xfer_status
 467 dcache_read_memory_partial (struct target_ops *ops, DCACHE *dcache,
 468                             CORE_ADDR memaddr, gdb_byte *myaddr,
 469                             ULONGEST len, ULONGEST *xfered_len)
 470 {
 471   ULONGEST i;
 472
 473   /* If this is a different inferior from what we've recorded,
 474      flush the cache.  */
 475
 476   if (inferior_ptid != dcache->ptid)
 477     {
 478       dcache_invalidate (dcache);
 479       dcache->ptid = inferior_ptid;
 480     }
 481
 482   for (i = 0; i < len; i++)
 483     {
 484       if (!dcache_peek_byte (dcache, memaddr + i, myaddr + i))
 485         {
 486           /* That failed.  Discard its cache line so we don't have a
 487              partially read line.  */
 488           dcache_invalidate_line (dcache, memaddr + i);
 489           break;
 490         }
 491     }
 492
 493   if (i == 0)
 494     {
 495       /* Even though reading the whole line failed, we may be able to
 496          read a piece starting where the caller wanted.  */
 497       return raw_memory_xfer_partial (ops, myaddr, NULL, memaddr, len,
 498                                       xfered_len);
 499     }
 500   else
 501     {
 502       *xfered_len = i;
 503       return TARGET_XFER_OK;
 504     }
 505 }
 506
 507 /* FIXME: There would be some benefit to making the cache write-back and
 508    moving the writeback operation to a higher layer, as it could occur
 509    after a sequence of smaller writes have been completed (as when a stack
 510    frame is constructed for an inferior function call).  Note that only
 511    moving it up one level to target_xfer_memory[_partial]() is not
 512    sufficient since we want to coalesce memory transfers that are
 513    "logically" connected but not actually a single call to one of the
 514    memory transfer functions.  */
 515
 516 /* Just update any cache lines which are already present.  This is
 517    called by the target_xfer_partial machinery when writing raw
 518    memory.  */
 519
 520 void
 521 dcache_update (DCACHE *dcache, enum target_xfer_status status,
 522                CORE_ADDR memaddr, const gdb_byte *myaddr,
 523                ULONGEST len)
 524 {
 525   ULONGEST i;
 526
 527   for (i = 0; i < len; i++)
 528     if (status == TARGET_XFER_OK)
 529       dcache_poke_byte (dcache, memaddr + i, myaddr + i);
 530     else
 531       {
 532         /* Discard the whole cache line so we don't have a partially
 533            valid line.  */
 534         dcache_invalidate_line (dcache, memaddr + i);
 535       }
 536 }
 537
 538 /* Print DCACHE line INDEX.  */
 539
 540 static void
 541 dcache_print_line (DCACHE *dcache, int index)
 542 {
 543   splay_tree_node n;
 544   struct dcache_block *db;
 545   int i, j;
 546
 547   if (dcache == NULL)
 548     {
 549       printf_filtered (_("No data cache available.\n"));
 550       return;
 551     }
 552
 553   n = splay_tree_min (dcache->tree);
 554
 555   for (i = index; i > 0; --i)
 556     {
 557       if (!n)
 558         break;
 559       n = splay_tree_successor (dcache->tree, n->key);
 560     }
 561
 562   if (!n)
 563     {
 564       printf_filtered (_("No such cache line exists.\n"));
 565       return;
 566     }
 567
 568   db = (struct dcache_block *) n->value;
 569
 570   printf_filtered (_("Line %d: address %s [%d hits]\n"),
 571                    index, paddress (target_gdbarch (), db->addr), db->refs);
 572
 573   for (j = 0; j < dcache->line_size; j++)
 574     {
 575       printf_filtered ("%02x ", db->data[j]);
 576
 577       /* Print a newline every 16 bytes (48 characters).  */
 578       if ((j % 16 == 15) && (j != dcache->line_size - 1))
 579         printf_filtered ("\n");
 580     }
 581   printf_filtered ("\n");
 582 }
 583
 584 /* Parse EXP and show the info about DCACHE.  */
 585
 586 static void
 587 dcache_info_1 (DCACHE *dcache, const char *exp)
 588 {
 589   splay_tree_node n;
 590   int i, refcount;
 591
 592   if (exp)
 593     {
 594       char *linestart;
 595
 596       i = strtol (exp, &linestart, 10);
 597       if (linestart == exp || i < 0)
 598         {
 599           printf_filtered (_("Usage: info dcache [LINENUMBER]\n"));
 600           return;
 601         }
 602
 603       dcache_print_line (dcache, i);
 604       return;
 605     }
 606
 607   printf_filtered (_("Dcache %u lines of %u bytes each.\n"),
 608                    dcache_size,
 609                    dcache ? (unsigned) dcache->line_size
 610                    : dcache_line_size);
 611
 612   if (dcache == NULL || dcache->ptid == null_ptid)
 613     {
 614       printf_filtered (_("No data cache available.\n"));
 615       return;
 616     }
 617
 618   printf_filtered (_("Contains data for %s\n"),
 619                    target_pid_to_str (dcache->ptid).c_str ());
 620
 621   refcount = 0;
 622
 623   n = splay_tree_min (dcache->tree);
 624   i = 0;
 625
 626   while (n)
 627     {
 628       struct dcache_block *db = (struct dcache_block *) n->value;
 629
 630       printf_filtered (_("Line %d: address %s [%d hits]\n"),
 631                        i, paddress (target_gdbarch (), db->addr), db->refs);
 632       i++;
 633       refcount += db->refs;
 634
 635       n = splay_tree_successor (dcache->tree, n->key);
 636     }
 637
 638   printf_filtered (_("Cache state: %d active lines, %d hits\n"), i, refcount);
 639 }
 640
 641 static void
 642 info_dcache_command (const char *exp, int tty)
 643 {
 644   dcache_info_1 (target_dcache_get (), exp);
 645 }
 646
 647 static void
 648 set_dcache_size (const char *args, int from_tty,
 649                  struct cmd_list_element *c)
 650 {
 651   if (dcache_size == 0)
 652     {
 653       dcache_size = DCACHE_DEFAULT_SIZE;
 654       error (_("Dcache size must be greater than 0."));
 655     }
 656   target_dcache_invalidate ();
 657 }
 658
 659 static void
 660 set_dcache_line_size (const char *args, int from_tty,
 661                       struct cmd_list_element *c)
 662 {
 663   if (dcache_line_size < 2
 664       || (dcache_line_size & (dcache_line_size - 1)) != 0)
 665     {
 666       unsigned d = dcache_line_size;
 667       dcache_line_size = DCACHE_DEFAULT_LINE_SIZE;
 668       error (_("Invalid dcache line size: %u (must be power of 2)."), d);
 669     }
 670   target_dcache_invalidate ();
 671 }
 672
 673 void _initialize_dcache ();
 674 void
 675 _initialize_dcache ()
 676 {
 677   add_setshow_boolean_cmd ("remotecache", class_support,
 678                            &dcache_enabled_p, _("\
 679 Set cache use for remote targets."), _("\
 680 Show cache use for remote targets."), _("\
 681 This used to enable the data cache for remote targets.  The cache\n\
 682 functionality is now controlled by the memory region system and the\n\
 683 \"stack-cache\" flag; \"remotecache\" now does nothing and\n\
 684 exists only for compatibility reasons."),
 685                            NULL,
 686                            show_dcache_enabled_p,
 687                            &setlist, &showlist);
 688
 689   add_info ("dcache", info_dcache_command,
 690             _("\
 691 Print information on the dcache performance.\n\
 692 Usage: info dcache [LINENUMBER]\n\
 693 With no arguments, this command prints the cache configuration and a\n\
 694 summary of each line in the cache.  With an argument, dump\"\n\
 695 the contents of the given line."));
 696
 697   add_basic_prefix_cmd ("dcache", class_obscure, _("\
 698 Use this command to set number of lines in dcache and line-size."),
 699                         &dcache_set_list, "set dcache ", /*allow_unknown*/0,
 700                         &setlist);
 701   add_show_prefix_cmd ("dcache", class_obscure, _("\
 702 Show dcachesettings."),
 703                        &dcache_show_list, "show dcache ", /*allow_unknown*/0,
 704                        &showlist);
 705
 706   add_setshow_zuinteger_cmd ("line-size", class_obscure,
 707                              &dcache_line_size, _("\
 708 Set dcache line size in bytes (must be power of 2)."), _("\
 709 Show dcache line size."),
 710                              NULL,
 711                              set_dcache_line_size,
 712                              NULL,
 713                              &dcache_set_list, &dcache_show_list);
 714   add_setshow_zuinteger_cmd ("size", class_obscure,
 715                              &dcache_size, _("\
 716 Set number of dcache lines."), _("\
 717 Show number of dcache lines."),
 718                              NULL,
 719                              set_dcache_size,
 720                              NULL,
 721                              &dcache_set_list, &dcache_show_list);
 722 }