* Re: [RFA] dcache invalidate fix
2009-11-10 21:35 [RFA] dcache invalidate fix Michael Snyder
@ 2009-11-11 23:37 ` Doug Evans
2009-11-12 0:06 ` Michael Snyder
0 siblings, 1 reply; 3+ messages in thread
From: Doug Evans @ 2009-11-11 23:37 UTC (permalink / raw)
To: Michael Snyder; +Cc: gdb-patches
[-- Attachment #1: Type: text/plain, Size: 2217 bytes --]
On Tue, Nov 10, 2009 at 1:33 PM, Michael Snyder <msnyder@vmware.com> wrote:
> Doug, I'm vague about this, but it seems right and it fixes the
> bug that I'm running into.
>
> It seems like dcache_invalidate_line needs to remove the block
> from the in use list at the same time as adding it to the freed
> list.
>
> The problem that bit me was getting the two lists cross-linked,
> which eventually led to an infinite loop behavior in dcache_invalidate.
>
>
> 2009-11-10 Michael Snyder <msnyder@vmware.com>
>
> * dcache.c (dcache_invalidate_line): Remove block from used list
> when adding it to freed list.
>
> Index: dcache.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/dcache.c,v
> retrieving revision 1.37
> diff -u -p -r1.37 dcache.c
> --- dcache.c 10 Nov 2009 18:36:50 -0000 1.37
> +++ dcache.c 10 Nov 2009 21:31:03 -0000
> @@ -167,10 +167,18 @@ dcache_invalidate_line (DCACHE *dcache,
>
> if (db)
> {
> + struct dcache_block *db2;
> splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
> db->newer = dcache->freelist;
> dcache->freelist = db;
> --dcache->size;
> + /* Remove db from dcache in-use chain. */
> + for (db2 = dcache->oldest; db2; db2 = db2->newer)
> + if (db2->newer == db)
> + {
> + dcache->newest = db2;
> + db2->newer = NULL;
> + }
> }
> }
Blech. Thanks for catching this.
The list will contain 4096 elements at this point so I think we need
to do something different.
The following comes to mind.
I'll check it in in a few days if there are no objections.
2009-11-11 Doug Evans <dje@google.com>
* dcache.c (dcache_block): Replace member newer with next,prev.
(dcache_struct): Delete member newest.
(block_func): New typedef.
(append_block, remove_block, for_each_block): New functions.
(invalidate_block, free_block): New functions.
(dcache_invalidate): Update
(dcache_invalidate_line, dcache_alloc): Update to use new list
accessors.
(dcache_free): Ditto. Fix memory leak.
[-- Attachment #2: gdb-091111-dcache-block-list-1.patch.txt --]
[-- Type: text/plain, Size: 6835 bytes --]
2009-11-11 Doug Evans <dje@google.com>
* dcache.c (dcache_block): Replace member newer with next,prev.
(dcache_struct): Delete member newest.
(block_func): New typedef.
(append_block, remove_block, for_each_block): New functions.
(invalidate_block, free_block): New functions.
(dcache_invalidate): Update
(dcache_invalidate_line, dcache_alloc): Update to use new list
accessors.
(dcache_free): Ditto. Fix memory leak.
Index: dcache.c
===================================================================
RCS file: /cvs/src/src/gdb/dcache.c,v
retrieving revision 1.37
diff -u -p -r1.37 dcache.c
--- dcache.c 10 Nov 2009 18:36:50 -0000 1.37
+++ dcache.c 11 Nov 2009 23:10:31 -0000
@@ -88,7 +88,10 @@
struct dcache_block
{
- struct dcache_block *newer; /* for LRU and free list */
+ /* for least-recently-allocated and free lists */
+ struct dcache_block *prev;
+ struct dcache_block *next;
+
CORE_ADDR addr; /* address of data */
gdb_byte data[LINE_SIZE]; /* bytes at given address */
int refs; /* # hits */
@@ -97,9 +100,10 @@ struct dcache_block
struct dcache_struct
{
splay_tree tree;
- struct dcache_block *oldest;
- struct dcache_block *newest;
+ struct dcache_block *oldest; /* least-recently-allocated list */
+ /* The free list is maintained identically to OLDEST to simplify
+ the code: we only need one set of accessors. */
struct dcache_block *freelist;
/* The number of in-use lines in the cache. */
@@ -109,6 +113,8 @@ struct dcache_struct
ptid_t ptid;
};
+typedef void (block_func) (struct dcache_block *block, void *param);
+
static struct dcache_block *dcache_hit (DCACHE *dcache, CORE_ADDR addr);
static int dcache_write_line (DCACHE *dcache, struct dcache_block *db);
@@ -132,28 +138,93 @@ show_dcache_enabled_p (struct ui_file *f
static DCACHE *last_cache; /* Used by info dcache */
-/* Free all the data cache blocks, thus discarding all cached data. */
+/* Append BLOCK to circular block list starting at BLIST.
+ The block is appended for the least-recently-allocated list's sake:
+ BLIST points to the oldest block. */
-void
-dcache_invalidate (DCACHE *dcache)
+static void
+append_block (struct dcache_block **blist, struct dcache_block *block)
{
- struct dcache_block *block, *next;
+ if (*blist)
+ {
+ block->next = *blist;
+ block->prev = (*blist)->prev;
+ block->prev->next = block;
+ (*blist)->prev = block;
+ /* We don't update *BLIST here to maintain the invariant that for the
+ least-recently-allocated list *BLIST points to the oldest block. */
+ }
+ else
+ {
+ block->next = block;
+ block->prev = block;
+ *blist = block;
+ }
+}
- block = dcache->oldest;
+/* Remove BLOCK from circular block list BLIST. */
- while (block)
+static void
+remove_block (struct dcache_block **blist, struct dcache_block *block)
+{
+ if (block->next == block)
+ {
+ *blist = NULL;
+ }
+ else
{
- splay_tree_remove (dcache->tree, (splay_tree_key) block->addr);
- next = block->newer;
+ block->next->prev = block->prev;
+ block->prev->next = block->next;
+ /* If we removed the block *BLIST points to, shift it to the next block
+ to maintain the invariant that for the least-recently-allocated list
+ *BLIST points to the oldest block. */
+ if (*blist == block)
+ *blist = block->next;
+ }
+}
- block->newer = dcache->freelist;
- dcache->freelist = block;
+/* Iterate over all elements in BLIST, calling FUNC.
+ PARAM is passed to FUNC.
+ FUNC may remove the block it's passed, but only that block. */
- block = next;
+static void
+for_each_block (struct dcache_block **blist, block_func *func, void *param)
+{
+ struct dcache_block *db;
+
+ if (*blist == NULL)
+ return;
+
+ db = *blist;
+ do
+ {
+ struct dcache_block *next = db->next;
+
+ func (db, param);
+ db = next;
}
+ while (*blist && db != *blist);
+}
+
+/* BLOCK_FUNC function for dcache_invalidate. */
+
+static void
+invalidate_block (struct dcache_block *block, void *param)
+{
+ DCACHE *dcache = (DCACHE *) param;
+
+ splay_tree_remove (dcache->tree, (splay_tree_key) block->addr);
+ append_block (&dcache->freelist, block);
+}
+
+/* Free all the data cache blocks, thus discarding all cached data. */
+
+void
+dcache_invalidate (DCACHE *dcache)
+{
+ for_each_block (&dcache->oldest, invalidate_block, dcache);
dcache->oldest = NULL;
- dcache->newest = NULL;
dcache->size = 0;
dcache->ptid = null_ptid;
}
@@ -168,8 +239,8 @@ dcache_invalidate_line (DCACHE *dcache,
if (db)
{
splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
- db->newer = dcache->freelist;
- dcache->freelist = db;
+ remove_block (&dcache->oldest, db);
+ append_block (&dcache->freelist, db);
--dcache->size;
}
}
@@ -251,9 +322,9 @@ dcache_alloc (DCACHE *dcache, CORE_ADDR
if (dcache->size >= DCACHE_SIZE)
{
- /* Evict the least recently used line. */
+ /* Evict the least recently allocated line. */
db = dcache->oldest;
- dcache->oldest = db->newer;
+ remove_block (&dcache->oldest, db);
splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
}
@@ -261,7 +332,7 @@ dcache_alloc (DCACHE *dcache, CORE_ADDR
{
db = dcache->freelist;
if (db)
- dcache->freelist = db->newer;
+ remove_block (&dcache->freelist, db);
else
db = xmalloc (sizeof (struct dcache_block));
@@ -269,16 +340,10 @@ dcache_alloc (DCACHE *dcache, CORE_ADDR
}
db->addr = MASK (addr);
- db->newer = NULL;
db->refs = 0;
- if (dcache->newest)
- dcache->newest->newer = db;
-
- dcache->newest = db;
-
- if (!dcache->oldest)
- dcache->oldest = db;
+ /* Put DB at the end of the list, it's the newest. */
+ append_block (&dcache->oldest, db);
splay_tree_insert (dcache->tree, (splay_tree_key) db->addr,
(splay_tree_value) db);
@@ -356,7 +421,6 @@ dcache_init (void)
NULL);
dcache->oldest = NULL;
- dcache->newest = NULL;
dcache->freelist = NULL;
dcache->size = 0;
dcache->ptid = null_ptid;
@@ -365,22 +429,25 @@ dcache_init (void)
return dcache;
}
+/* BLOCK_FUNC routine for dcache_free. */
+
+static void
+free_block (struct dcache_block *block, void *param)
+{
+ free (block);
+}
+
/* Free a data cache. */
void
dcache_free (DCACHE *dcache)
{
- struct dcache_block *db, *next;
-
if (last_cache == dcache)
last_cache = NULL;
splay_tree_delete (dcache->tree);
- for (db = dcache->freelist; db != NULL; db = next)
- {
- next = db->newer;
- xfree (db);
- }
+ for_each_block (&dcache->oldest, free_block, NULL);
+ for_each_block (&dcache->freelist, free_block, NULL);
xfree (dcache);
}
^ permalink raw reply [flat|nested] 3+ messages in thread