[RFA] dcache invalidate fix

[RFA] dcache invalidate fix

[Michael Snyder]

[-- Attachment #1: Type: text/plain, Size: 363 bytes --]

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.


[-- Attachment #2: dcache2.txt --]
[-- Type: text/plain, Size: 889 bytes --]

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;
+	  }
     }
 }
 

Re: [RFA] dcache invalidate fix

[Doug Evans]

[-- 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);
 }
 

Re: [RFA] dcache invalidate fix

[Michael Snyder]

Doug Evans wrote:
> 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.

FYI, this fixes the problem that caused me to look into it.
Thanks,
Michael

> 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.