summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJustus Winter <4winter@informatik.uni-hamburg.de>2015-11-22 20:19:52 +0100
committerJustus Winter <4winter@informatik.uni-hamburg.de>2015-11-29 23:59:48 +0100
commit315a491d390a26c668ede6c8fa703b7620c10d08 (patch)
tree2656ce11fd292e29b8afbcd972f3a58915210831
parentfe9ece07747eb7281e0749a3dde7c02267af8ae6 (diff)
ext2fs: keep list of reusable disk cache entries
This avoids a linear scan through the cache. * ext2fs/ext2fs.h (struct disk_cache_info): New field 'next'. * ext2fs/pager.c (disk_cache_hint): Drop. (disk_cache_info_free, disk_cache_info_free_lock): New variables. (disk_cache_info_free_pop, disk_cache_info_free_push): New functions. (disk_cache_init): Adjust slightly. (disk_cache_block_ref): Use new functions. (disk_cache_block_deref): Likewise.
-rw-r--r--ext2fs/ext2fs.h1
-rw-r--r--ext2fs/pager.c83
2 files changed, 53 insertions, 31 deletions
diff --git a/ext2fs/ext2fs.h b/ext2fs/ext2fs.h
index 0b6b79ef..b8398192 100644
--- a/ext2fs/ext2fs.h
+++ b/ext2fs/ext2fs.h
@@ -254,6 +254,7 @@ struct disk_cache_info
block_t block;
uint16_t flags;
uint16_t ref_count;
+ struct disk_cache_info *next; /* List of reusable entries. */
#ifdef DEBUG_DISK_CACHE
block_t last_read, last_read_xor;
#endif
diff --git a/ext2fs/pager.c b/ext2fs/pager.c
index f28bcabc..47c5f947 100644
--- a/ext2fs/pager.c
+++ b/ext2fs/pager.c
@@ -840,13 +840,50 @@ int disk_cache_blocks;
hurd_ihash_t disk_cache_bptr;
/* Cached blocks' info. */
struct disk_cache_info *disk_cache_info;
-/* Hint index for which cache block to reuse next. */
-int disk_cache_hint;
/* Lock for these structures. */
pthread_mutex_t disk_cache_lock;
/* Fired when a re-association is done. */
pthread_cond_t disk_cache_reassociation;
+/* Linked list of potentially unused blocks. */
+static struct disk_cache_info *disk_cache_info_free;
+static pthread_mutex_t disk_cache_info_free_lock;
+
+/* Get a reusable entry. Must be called with disk_cache_lock
+ held. */
+static struct disk_cache_info *
+disk_cache_info_free_pop (void)
+{
+ struct disk_cache_info *p;
+
+ do
+ {
+ pthread_mutex_lock (&disk_cache_info_free_lock);
+ p = disk_cache_info_free;
+ if (p)
+ {
+ disk_cache_info_free = p->next;
+ p->next = NULL;
+ }
+ pthread_mutex_unlock (&disk_cache_info_free_lock);
+ }
+ while (p && (p->flags & DC_DONT_REUSE || p->ref_count > 0));
+ return p;
+}
+
+/* Add P to the list of potentially re-usable entries. */
+static void
+disk_cache_info_free_push (struct disk_cache_info *p)
+{
+ pthread_mutex_lock (&disk_cache_info_free_lock);
+ if (! p->next)
+ {
+ p->next = disk_cache_info_free;
+ disk_cache_info_free = p;
+ }
+ pthread_mutex_unlock (&disk_cache_info_free_lock);
+}
+
/* Finish mapping initialization. */
static void
disk_cache_init (void)
@@ -857,6 +894,7 @@ disk_cache_init (void)
pthread_mutex_init (&disk_cache_lock, NULL);
pthread_cond_init (&disk_cache_reassociation, NULL);
+ pthread_mutex_init (&disk_cache_info_free_lock, NULL);
/* Allocate space for block num -> in-memory pointer mapping. */
if (hurd_ihash_create (&disk_cache_bptr, HURD_IHASH_NO_LOCP))
@@ -867,19 +905,22 @@ disk_cache_init (void)
if (!disk_cache_info)
ext2_panic ("Cannot allocate space for disk cache info");
- /* Initialize disk_cache_info. */
- for (int i = 0; i < disk_cache_blocks; i++)
+ /* Initialize disk_cache_info. Start with the last entry so that
+ the first ends up at the front of the free list. This keeps the
+ assertions at the end of this function happy. */
+ for (int i = disk_cache_blocks; i >= 0; i--)
{
disk_cache_info[i].block = DC_NO_BLOCK;
disk_cache_info[i].flags = 0;
disk_cache_info[i].ref_count = 0;
+ disk_cache_info[i].next = NULL;
+ disk_cache_info_free_push (&disk_cache_info[i]);
#ifdef DEBUG_DISK_CACHE
disk_cache_info[i].last_read = DC_NO_BLOCK;
disk_cache_info[i].last_read_xor
= DC_NO_BLOCK ^ DISK_CACHE_LAST_READ_XOR;
#endif
}
- disk_cache_hint = 0;
/* Map the superblock and the block group descriptors. */
block_t fixed_first = boffs_block (SBLOCK_OFFS);
@@ -958,6 +999,7 @@ disk_cache_return_unused (void)
void *
disk_cache_block_ref (block_t block)
{
+ struct disk_cache_info *info;
int index;
void *bptr;
hurd_ihash_locp_t slot;
@@ -1005,34 +1047,10 @@ retry_ref:
}
/* Search for a block that is not in core and is not referenced. */
- index = disk_cache_hint;
- while ((disk_cache_info[index].flags & DC_DONT_REUSE)
- || (disk_cache_info[index].ref_count))
- {
- ext2_debug ("reject %u -> %d (ref_count = %hu, flags = %#hx)",
- disk_cache_info[index].block, index,
- disk_cache_info[index].ref_count,
- disk_cache_info[index].flags);
-
- /* Just move to next block. */
- index++;
- if (index >= disk_cache_blocks)
- index -= disk_cache_blocks;
-
- /* If we return to where we started, than there is no suitable
- block. */
- if (index == disk_cache_hint)
- break;
- }
-
- /* The next place in the disk cache becomes the current hint. */
- disk_cache_hint = index + 1;
- if (disk_cache_hint >= disk_cache_blocks)
- disk_cache_hint -= disk_cache_blocks;
+ info = disk_cache_info_free_pop ();
/* Is suitable place found? */
- if ((disk_cache_info[index].flags & DC_DONT_REUSE)
- || disk_cache_info[index].ref_count)
+ if (info == NULL)
/* No place is found. Try to release some blocks and try
again. */
{
@@ -1046,6 +1064,7 @@ retry_ref:
}
/* Suitable place is found. */
+ index = info - disk_cache_info;
/* Calculate pointer to data. */
bptr = (char *)disk_cache + (index << log2_block_size);
@@ -1177,6 +1196,8 @@ disk_cache_block_deref (void *ptr)
assert (! (disk_cache_info[index].flags & DC_UNTOUCHED));
assert (disk_cache_info[index].ref_count >= 1);
disk_cache_info[index].ref_count--;
+ if (disk_cache_info[index].ref_count == 0)
+ disk_cache_info_free_push (&disk_cache_info[index]);
pthread_mutex_unlock (&disk_cache_lock);
}