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