add patch series

4 files changed, 311 insertions, 0 deletions

diff --git a/debian/patches/ext2fs-optimize-bcache0001-ext2fs-improve-the-block-cache.patch b/debian/patches/ext2fs-optimize-bcache0001-ext2fs-improve-the-block-cache.patch
new file mode 100644
index 00000000..c9ac8927
--- /dev/null
+++ b/debian/patches/ext2fs-optimize-bcache0001-ext2fs-improve-the-block-cache.patch
@@ -0,0 +1,53 @@
+From dc14a3413d9c93ecd043e8c3d5ca99670419d400 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Thu, 12 Nov 2015 23:22:13 +0100
+Subject: [PATCH hurd 1/3] ext2fs: improve the block cache
+
+* ext2fs/pager.c (disk_cache_block_ref): Improve the cache by using
+the new lookup and insertion functions that return and use a location
+pointer.
+---
+ ext2fs/pager.c | 10 ++++++----
+ 1 file changed, 6 insertions(+), 4 deletions(-)
+
+diff --git a/ext2fs/pager.c b/ext2fs/pager.c
+index 9df7e0b..2528856 100644
+--- a/ext2fs/pager.c
++++ b/ext2fs/pager.c
+@@ -960,6 +960,7 @@ disk_cache_block_ref (block_t block)
+ {
+   int index;
+   void *bptr;
++  hurd_ihash_locp_t slot;
+ 
+   assert (block < store->size >> log2_block_size);
+ 
+@@ -968,7 +969,7 @@ disk_cache_block_ref (block_t block)
+ retry_ref:
+   pthread_mutex_lock (&disk_cache_lock);
+ 
+-  bptr = hurd_ihash_find (disk_cache_bptr, block);
++  bptr = hurd_ihash_locp_find (disk_cache_bptr, block, &slot);
+   if (bptr)
+     /* Already mapped.  */
+     {
+@@ -1091,12 +1092,13 @@ retry_ref:
+ #endif
+ 
+   /* Re-associate.  */
++
++  /* New association.  */
++  if (hurd_ihash_locp_add (disk_cache_bptr, slot, block, bptr))
++    ext2_panic ("Couldn't hurd_ihash_locp_add new disk block");
+   if (disk_cache_info[index].block != DC_NO_BLOCK)
+     /* Remove old association.  */
+     hurd_ihash_remove (disk_cache_bptr, disk_cache_info[index].block);
+-  /* New association.  */
+-  if (hurd_ihash_add (disk_cache_bptr, block, bptr))
+-    ext2_panic ("Couldn't hurd_ihash_add new disk block");
+   assert (! (disk_cache_info[index].flags & DC_DONT_REUSE & ~DC_UNTOUCHED));
+   disk_cache_info[index].block = block;
+   assert (! disk_cache_info[index].ref_count);
+-- 
+2.1.4
+
diff --git a/debian/patches/ext2fs-optimize-bcache0002-ext2fs-disable-block-cache-debugging-by-default.patch b/debian/patches/ext2fs-optimize-bcache0002-ext2fs-disable-block-cache-debugging-by-default.patch
new file mode 100644
index 00000000..aea3021c
--- /dev/null
+++ b/debian/patches/ext2fs-optimize-bcache0002-ext2fs-disable-block-cache-debugging-by-default.patch
@@ -0,0 +1,68 @@
+From 7b02fdcafc95fc305d67143bed40e8eb72ae96d6 Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Thu, 12 Nov 2015 23:33:35 +0100
+Subject: [PATCH hurd 2/3] ext2fs: disable block cache debugging by default
+
+* ext2fs/ext2fs.h: Disable block cache debugging by default.
+* ext2fs/pager.c: Likewise.
+---
+ ext2fs/ext2fs.h | 4 ++--
+ ext2fs/pager.c  | 6 +++---
+ 2 files changed, 5 insertions(+), 5 deletions(-)
+
+diff --git a/ext2fs/ext2fs.h b/ext2fs/ext2fs.h
+index 42717c5..0b6b79e 100644
+--- a/ext2fs/ext2fs.h
++++ b/ext2fs/ext2fs.h
+@@ -244,7 +244,7 @@ extern int disk_cache_blocks;
+ 
+ #define DC_NO_BLOCK	((block_t) -1L)
+ 
+-#ifndef NDEBUG
++#ifdef DEBUG_DISK_CACHE
+ #define DISK_CACHE_LAST_READ_XOR	0xDEADBEEF
+ #endif
+ 
+@@ -254,7 +254,7 @@ struct disk_cache_info
+   block_t block;
+   uint16_t flags;
+   uint16_t ref_count;
+-#ifndef NDEBUG
++#ifdef DEBUG_DISK_CACHE
+   block_t last_read, last_read_xor;
+ #endif
+ };
+diff --git a/ext2fs/pager.c b/ext2fs/pager.c
+index 2528856..f28bcab 100644
+--- a/ext2fs/pager.c
++++ b/ext2fs/pager.c
+@@ -433,7 +433,7 @@ disk_pager_read_page (vm_offset_t page, void **buf, int *writelock)
+     + offset % block_size;
+   disk_cache_info[index].flags |= DC_INCORE;
+   disk_cache_info[index].flags &=~ DC_UNTOUCHED;
+-#ifndef NDEBUG
++#ifdef DEBUG_DISK_CACHE
+   disk_cache_info[index].last_read = disk_cache_info[index].block;
+   disk_cache_info[index].last_read_xor
+     = disk_cache_info[index].block ^ DISK_CACHE_LAST_READ_XOR;
+@@ -469,7 +469,7 @@ disk_pager_write_page (vm_offset_t page, void *buf)
+   assert (disk_cache_info[index].block != DC_NO_BLOCK);
+   offset = ((store_offset_t) disk_cache_info[index].block << log2_block_size)
+     + offset % block_size;
+-#ifndef NDEBUG			/* Not strictly needed.  */
++#ifdef DEBUG_DISK_CACHE			/* Not strictly needed.  */
+   assert ((disk_cache_info[index].last_read ^ DISK_CACHE_LAST_READ_XOR)
+ 	  == disk_cache_info[index].last_read_xor);
+   assert (disk_cache_info[index].last_read
+@@ -873,7 +873,7 @@ disk_cache_init (void)
+       disk_cache_info[i].block = DC_NO_BLOCK;
+       disk_cache_info[i].flags = 0;
+       disk_cache_info[i].ref_count = 0;
+-#ifndef NDEBUG
++#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;
+-- 
+2.1.4
+
diff --git a/debian/patches/ext2fs-optimize-bcache0003-ext2fs-keep-list-of-reusable-disk-cache-entries.patch b/debian/patches/ext2fs-optimize-bcache0003-ext2fs-keep-list-of-reusable-disk-cache-entries.patch
new file mode 100644
index 00000000..2ee46c07
--- /dev/null
+++ b/debian/patches/ext2fs-optimize-bcache0003-ext2fs-keep-list-of-reusable-disk-cache-entries.patch
@@ -0,0 +1,187 @@
+From e68df91a9fbeba5ee6ec311a996f74132de1d34c Mon Sep 17 00:00:00 2001
+From: Justus Winter <4winter@informatik.uni-hamburg.de>
+Date: Sun, 22 Nov 2015 20:19:52 +0100
+Subject: [PATCH hurd 3/3] 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.
+---
+ ext2fs/ext2fs.h |  1 +
+ ext2fs/pager.c  | 83 ++++++++++++++++++++++++++++++++++++---------------------
+ 2 files changed, 53 insertions(+), 31 deletions(-)
+
+diff --git a/ext2fs/ext2fs.h b/ext2fs/ext2fs.h
+index 0b6b79e..b839819 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 f28bcab..47c5f94 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);
+ }
+ 
+-- 
+2.1.4
+
diff --git a/debian/patches/series b/debian/patches/series
index 2be0e703..29d5722e 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -53,3 +53,6 @@ ihash-as-cache0004-libihash-fix-item-insertion.patch
 ihash-as-cache0005-libihash-provide-a-general-purpose-hash-algorithm.patch
 nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch
 nodeihash0002-xxx-fix-node-iteration.patch
+ext2fs-optimize-bcache0001-ext2fs-improve-the-block-cache.patch
+ext2fs-optimize-bcache0002-ext2fs-disable-block-cache-debugging-by-default.patch
+ext2fs-optimize-bcache0003-ext2fs-keep-list-of-reusable-disk-cache-entries.patch