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