2009-11-11 Doug Evans * 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); }