diff options
| -rw-r--r-- | debian/patches/nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch | 263 | ||||
| -rw-r--r-- | debian/patches/nodeihash0002-xxx-fix-node-iteration.patch | 118 | ||||
| -rw-r--r-- | debian/patches/series | 2 |
3 files changed, 383 insertions, 0 deletions
diff --git a/debian/patches/nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch b/debian/patches/nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch new file mode 100644 index 00000000..f5c7661c --- /dev/null +++ b/debian/patches/nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch @@ -0,0 +1,263 @@ +From cda144ffdde66cbe0084f0d1d0286d9f99970f43 Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Wed, 24 Jun 2015 02:30:01 +0200 +Subject: [PATCH hurd 1/2] libdiskfs: use ihash for the node cache + +Replace the hand-written hash table in the node cache with libihash. +Libihash is a self-tuning hash table, whereas the previous code used a +fixed number of buckets. + +* libdiskfs/Makefile (HURDLIBS): Link to `ihash'. +* libdiskfs/diskfs.h (struct node): Remove bucket list, add slot pointer. +* libdiskfs/node-cache.c (nodecache): New ihash table replacing the +old `nodehash'. +(lookup): Drop function. +(diskfs_cached_lookup_context): Adapt accordingly. +(diskfs_cached_ifind): Likewise. +(diskfs_try_dropping_softrefs): Likewise. +(diskfs_node_iterate): Likewise. +--- + libdiskfs/Makefile | 2 +- + libdiskfs/diskfs.h | 5 ++- + libdiskfs/node-cache.c | 111 +++++++++++++++++++++++++------------------------ + 3 files changed, 60 insertions(+), 58 deletions(-) + +diff --git a/libdiskfs/Makefile b/libdiskfs/Makefile +index 47b9339..803761d 100644 +--- a/libdiskfs/Makefile ++++ b/libdiskfs/Makefile +@@ -61,7 +61,7 @@ MIGSTUBS = fsServer.o ioServer.o fsysServer.o exec_startupServer.o \ + startup_notifyServer.o + OBJS = $(sort $(SRCS:.c=.o) $(MIGSTUBS)) + +-HURDLIBS = fshelp iohelp store ports shouldbeinlibc pager ++HURDLIBS = fshelp iohelp store ports shouldbeinlibc pager ihash + LDLIBS += -lpthread + + fsys-MIGSFLAGS = -imacros $(srcdir)/fsmutations.h -DREPLY_PORTS +diff --git a/libdiskfs/diskfs.h b/libdiskfs/diskfs.h +index 11fb0ad..106aeb0 100644 +--- a/libdiskfs/diskfs.h ++++ b/libdiskfs/diskfs.h +@@ -25,6 +25,7 @@ + #include <pthread.h> + #include <hurd/ports.h> + #include <hurd/fshelp.h> ++#include <hurd/ihash.h> + #include <hurd/iohelp.h> + #include <idvec.h> + #include <features.h> +@@ -80,8 +81,8 @@ struct peropen + filesystem. */ + struct node + { +- /* Links on hash list. */ +- struct node *hnext, **hprevp; ++ /* The slot we occupy in the node cache. */ ++ hurd_ihash_locp_t slot; + + struct disknode *dn; + +diff --git a/libdiskfs/node-cache.c b/libdiskfs/node-cache.c +index a76474a..f187a73 100644 +--- a/libdiskfs/node-cache.c ++++ b/libdiskfs/node-cache.c +@@ -17,44 +17,53 @@ + You should have received a copy of the GNU General Public License + along with the GNU Hurd. If not, see <http://www.gnu.org/licenses/>. */ + +-#include "priv.h" +- +-#define INOHSZ 8192 +-#if ((INOHSZ&(INOHSZ-1)) == 0) +-#define INOHASH(ino) ((ino)&(INOHSZ-1)) +-#else +-#define INOHASH(ino) (((unsigned)(ino))%INOHSZ) +-#endif ++#include <hurd/ihash.h> + +-/* The nodehash is a cache of nodes. ++#include "priv.h" + +- Access to nodehash and nodehash_nr_items is protected by +- nodecache_lock. ++/* The node cache is implemented using a hash table. Access to the ++ cache is protected by nodecache_lock. + +- Every node in the nodehash carries a light reference. When we are ++ Every node in the cache carries a light reference. When we are + asked to give up that light reference, we reacquire our lock + momentarily to check whether someone else reacquired a reference +- through the nodehash. */ +-static struct node *nodehash[INOHSZ]; +-static size_t nodehash_nr_items; ++ through the cache. */ ++static struct hurd_ihash nodecache = ++ HURD_IHASH_INITIALIZER (offsetof (struct node, slot)); + static pthread_rwlock_t nodecache_lock = PTHREAD_RWLOCK_INITIALIZER; + +-/* Initialize the inode hash table. */ +-static void __attribute__ ((constructor)) +-nodecache_init () ++/* The size of ino_t is larger than hurd_ihash_key_t on 32 bit ++ platforms. We therefore have to use libihashs generalized key ++ interface. */ ++ ++/* This is the mix function of fasthash. Marsaglia, George. "Xorshift ++ rngs." Journal of Statistical Software 8.14 (2003): 1-6. Code take ++ from https://code.google.com/p/fast-hash/. */ ++#define mix_fasthash(h) ({ \ ++ (h) ^= (h) >> 23; \ ++ (h) *= 0x2127599bf4325c37ULL; \ ++ (h) ^= (h) >> 47; }) ++ ++static hurd_ihash_key_t ++hash (void *key) + { ++ ino_t i; ++ i = *(ino_t *) key; ++ mix_fasthash (i); ++ return (hurd_ihash_key_t) i; + } + +-/* Lookup node with inode number INUM. Returns NULL if the node is +- not found in the node cache. */ +-static struct node * +-lookup (ino_t inum) ++static int ++compare (void *a, void *b) + { +- struct node *np; +- for (np = nodehash[INOHASH(inum)]; np; np = np->hnext) +- if (np->cache_id == inum) +- return np; +- return NULL; ++ return *(ino_t *) a == *(ino_t *) b; ++} ++ ++/* Initialize the inode hash table. */ ++static void __attribute__ ((constructor)) ++nodecache_init () ++{ ++ hurd_ihash_set_gki (&nodecache, hash, compare); + } + + /* Fetch inode INUM, set *NPP to the node structure; +@@ -73,9 +82,10 @@ diskfs_cached_lookup_context (ino_t inum, struct node **npp, + { + error_t err; + struct node *np, *tmp; ++ hurd_ihash_locp_t slot; + + pthread_rwlock_rdlock (&nodecache_lock); +- np = lookup (inum); ++ np = hurd_ihash_locp_find (&nodecache, (hurd_ihash_key_t) &inum, &slot); + if (np) + goto gotit; + pthread_rwlock_unlock (&nodecache_lock); +@@ -89,7 +99,8 @@ diskfs_cached_lookup_context (ino_t inum, struct node **npp, + + /* Put NP in NODEHASH. */ + pthread_rwlock_wrlock (&nodecache_lock); +- tmp = lookup (inum); ++ tmp = hurd_ihash_locp_find (&nodecache, (hurd_ihash_key_t) &np->cache_id, ++ &slot); + if (tmp) + { + /* We lost a race. */ +@@ -98,13 +109,10 @@ diskfs_cached_lookup_context (ino_t inum, struct node **npp, + goto gotit; + } + +- np->hnext = nodehash[INOHASH(inum)]; +- if (np->hnext) +- np->hnext->hprevp = &np->hnext; +- np->hprevp = &nodehash[INOHASH(inum)]; +- nodehash[INOHASH(inum)] = np; ++ err = hurd_ihash_locp_add (&nodecache, slot, ++ (hurd_ihash_key_t) &np->cache_id, np); ++ assert_perror (err); + diskfs_nref_light (np); +- nodehash_nr_items += 1; + pthread_rwlock_unlock (&nodecache_lock); + + /* Get the contents of NP off disk. */ +@@ -133,7 +141,7 @@ diskfs_cached_ifind (ino_t inum) + struct node *np; + + pthread_rwlock_rdlock (&nodecache_lock); +- np = lookup (inum); ++ np = hurd_ihash_find (&nodecache, (hurd_ihash_key_t) &inum); + pthread_rwlock_unlock (&nodecache_lock); + + assert (np); +@@ -144,7 +152,7 @@ void __attribute__ ((weak)) + diskfs_try_dropping_softrefs (struct node *np) + { + pthread_rwlock_wrlock (&nodecache_lock); +- if (np->hprevp != NULL) ++ if (np->slot != NULL) + { + /* Check if someone reacquired a reference through the + nodehash. */ +@@ -159,12 +167,8 @@ diskfs_try_dropping_softrefs (struct node *np) + return; + } + +- *np->hprevp = np->hnext; +- if (np->hnext) +- np->hnext->hprevp = np->hprevp; +- np->hnext = NULL; +- np->hprevp = NULL; +- nodehash_nr_items -= 1; ++ hurd_ihash_locp_remove (&nodecache, np->slot); ++ np->slot = NULL; + diskfs_nrele_light (np); + } + pthread_rwlock_unlock (&nodecache_lock); +@@ -179,7 +183,6 @@ error_t __attribute__ ((weak)) + diskfs_node_iterate (error_t (*fun)(struct node *)) + { + error_t err = 0; +- int n; + size_t num_nodes; + struct node *node, **node_list, **p; + +@@ -191,7 +194,7 @@ diskfs_node_iterate (error_t (*fun)(struct node *)) + nodecache_lock, but we can't hold this while locking the + individual node locks). */ + /* XXX: Can we? */ +- num_nodes = nodehash_nr_items; ++ num_nodes = nodecache.nr_items; + + /* TODO This method doesn't scale beyond a few dozen nodes and should be + replaced. */ +@@ -203,17 +206,15 @@ diskfs_node_iterate (error_t (*fun)(struct node *)) + } + + p = node_list; +- for (n = 0; n < INOHSZ; n++) +- for (node = nodehash[n]; node; node = node->hnext) +- { +- *p++ = node; +- +- /* We acquire a hard reference for node, but without using +- diskfs_nref. We do this so that diskfs_new_hardrefs will not +- get called. */ +- refcounts_ref (&node->refcounts, NULL); +- } ++ HURD_IHASH_ITERATE (&nodecache, i) ++ { ++ *p++ = node = i; + ++ /* We acquire a hard reference for node, but without using ++ diskfs_nref. We do this so that diskfs_new_hardrefs will not ++ get called. */ ++ refcounts_ref (&node->refcounts, NULL); ++ } + pthread_rwlock_unlock (&nodecache_lock); + + p = node_list; +-- +2.1.4 + diff --git a/debian/patches/nodeihash0002-xxx-fix-node-iteration.patch b/debian/patches/nodeihash0002-xxx-fix-node-iteration.patch new file mode 100644 index 00000000..a78da3b7 --- /dev/null +++ b/debian/patches/nodeihash0002-xxx-fix-node-iteration.patch @@ -0,0 +1,118 @@ +From 00bd1a54e878c29ad56c539484c57bf9cf9f5b51 Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Fri, 20 Nov 2015 12:45:28 +0100 +Subject: [PATCH hurd 2/2] xxx fix node iteration + +--- + libdiskfs/diskfs.h | 8 +++---- + libdiskfs/node-cache.c | 63 ++++++++++++++++---------------------------------- + 2 files changed, 24 insertions(+), 47 deletions(-) + +diff --git a/libdiskfs/diskfs.h b/libdiskfs/diskfs.h +index 106aeb0..51bb79f 100644 +--- a/libdiskfs/diskfs.h ++++ b/libdiskfs/diskfs.h +@@ -521,10 +521,10 @@ void diskfs_write_disknode (struct node *np, int wait); + void diskfs_file_update (struct node *np, int wait); + + /* The user must define this function unless she wants to use the node +- cache. See the section `Node cache' below. For each active node, call +- FUN. The node is to be locked around the call to FUN. If FUN +- returns non-zero for any node, then immediately stop, and return +- that value. */ ++ cache. See the section `Node cache' below. For each active node, ++ call FUN. The node is to be locked around the call to FUN. FUN ++ must be idempotent. If FUN returns non-zero for any node, then ++ immediately stop, and return that value. */ + error_t diskfs_node_iterate (error_t (*fun)(struct node *)); + + /* The user must define this function. Sync all the pagers and any +diff --git a/libdiskfs/node-cache.c b/libdiskfs/node-cache.c +index f187a73..984ae4c 100644 +--- a/libdiskfs/node-cache.c ++++ b/libdiskfs/node-cache.c +@@ -176,61 +176,38 @@ diskfs_try_dropping_softrefs (struct node *np) + diskfs_user_try_dropping_softrefs (np); + } + +-/* For each active node, call FUN. The node is to be locked around the call +- to FUN. If FUN returns non-zero for any node, then immediately stop, and +- return that value. */ ++/* For each active node, call FUN. FUN must be idempotent. The node ++ is to be locked around the call to FUN. If FUN returns non-zero ++ for any node, then immediately stop, and return that value. */ + error_t __attribute__ ((weak)) + diskfs_node_iterate (error_t (*fun)(struct node *)) + { + error_t err = 0; +- size_t num_nodes; +- struct node *node, **node_list, **p; ++ struct node *node; + ++ /* XXX */ ++ restart: + pthread_rwlock_rdlock (&nodecache_lock); + +- /* We must copy everything from the hash table into another data structure +- to avoid running into any problems with the hash-table being modified +- during processing (normally we delegate access to hash-table with +- nodecache_lock, but we can't hold this while locking the +- individual node locks). */ +- /* XXX: Can we? */ +- num_nodes = nodecache.nr_items; +- +- /* TODO This method doesn't scale beyond a few dozen nodes and should be +- replaced. */ +- node_list = malloc (num_nodes * sizeof (struct node *)); +- if (node_list == NULL) +- { +- pthread_rwlock_unlock (&nodecache_lock); +- return ENOMEM; +- } +- +- p = node_list; + HURD_IHASH_ITERATE (&nodecache, i) + { +- *p++ = node = i; +- +- /* We acquire a hard reference for node, but without using +- diskfs_nref. We do this so that diskfs_new_hardrefs will not +- get called. */ +- refcounts_ref (&node->refcounts, NULL); ++ node = i; ++ ++ if (pthread_mutex_trylock (&node->lock)) ++ { ++ /* Failed to acquire the lock. Release the cache lock and ++ restart iteration. */ ++ pthread_rwlock_unlock (&nodecache_lock); ++ goto restart; ++ } ++ err = (*fun)(node); ++ pthread_mutex_unlock (&node->lock); ++ if (err) ++ break; + } +- pthread_rwlock_unlock (&nodecache_lock); + +- p = node_list; +- while (num_nodes-- > 0) +- { +- node = *p++; +- if (!err) +- { +- pthread_mutex_lock (&node->lock); +- err = (*fun)(node); +- pthread_mutex_unlock (&node->lock); +- } +- diskfs_nrele (node); +- } ++ pthread_rwlock_unlock (&nodecache_lock); + +- free (node_list); + return err; + } + +-- +2.1.4 + diff --git a/debian/patches/series b/debian/patches/series index 5e5387fc..a12bf1b5 100644 --- a/debian/patches/series +++ b/debian/patches/series @@ -58,3 +58,5 @@ ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch ext2fs-optimize-bcache0001-ext2fs-improve-the-block-cache.patch ext2fs-optimize-bcache0002-ext2fs-disable-block-cache-debugging-by-default.patch +nodeihash0001-libdiskfs-use-ihash-for-the-node-cache.patch +nodeihash0002-xxx-fix-node-iteration.patch |