diff options
8 files changed, 64 insertions, 45 deletions
diff --git a/debian/patches/0001-libports-use-a-single-hash-table.patch b/debian/patches/0001-libports-use-a-single-hash-table.patch index 492a4cab..ec0af1b9 100644 --- a/debian/patches/0001-libports-use-a-single-hash-table.patch +++ b/debian/patches/0001-libports-use-a-single-hash-table.patch @@ -1,15 +1,15 @@ -From 27741dca90e3a6070727fffc22d3105653a33747 Mon Sep 17 00:00:00 2001 +From ad5c0b3331c73bae11c0c9da422ffd190a0dccfc Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Sat, 3 May 2014 03:53:41 +0200 -Subject: [PATCH 1/5] libports: use a single hash table +Subject: [PATCH 01/11] libports: use a single hash table Previously, libports used a hash table per port bucket. This makes looking up a port difficult if one does not know the port bucket, as one has to iterate over all buckets and do a hash table lookup each. -The having to iterate over the buckets makes it necessary to keep a -list of all buckets, which has to be updated and protected by a lock -as well. +Having to iterate over the buckets makes it necessary to keep a list +of all buckets, which has to be updated and protected by a lock as +well. Also, the current code in _ports_bucket_class_iterate iterates over the hash table associated with the bucket given. When diff --git a/debian/patches/0002-include-add-lock-less-reference-counting-primitives.patch b/debian/patches/0002-include-add-lock-less-reference-counting-primitives.patch index 145d340e..6718ab31 100644 --- a/debian/patches/0002-include-add-lock-less-reference-counting-primitives.patch +++ b/debian/patches/0002-include-add-lock-less-reference-counting-primitives.patch @@ -1,20 +1,20 @@ -From 8faea20349dc1d8cfd0117d28a3f1271083192d0 Mon Sep 17 00:00:00 2001 +From 55ddd1b28a57492c5df4afcdf167910fb7bbc3a1 Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Tue, 6 May 2014 19:52:04 +0200 -Subject: [PATCH 2/5] include: add lock-less reference counting primitives +Subject: [PATCH 02/11] include: add lock-less reference counting primitives * include/refcount.h: New file. --- - include/refcount.h | 155 +++++++++++++++++++++++++++++++++++++++++++++++++++++ - 1 file changed, 155 insertions(+) + include/refcount.h | 174 +++++++++++++++++++++++++++++++++++++++++++++++++++++ + 1 file changed, 174 insertions(+) create mode 100644 include/refcount.h diff --git a/include/refcount.h b/include/refcount.h new file mode 100644 -index 0000000..946938a +index 0000000..0a9ed8e --- /dev/null +++ b/include/refcount.h -@@ -0,0 +1,155 @@ +@@ -0,0 +1,174 @@ +/* Lock-less reference counting primitives + + Copyright (C) 2014 Free Software Foundation, Inc. @@ -44,31 +44,36 @@ index 0000000..946938a +/* Simple reference counting. */ + +/* An opaque type. You must not access these values directly. */ -+typedef uint32_t refcount_t; ++typedef unsigned int refcount_t; + +/* Initialize REF with REFERENCES. */ +static inline void -+refcount_init (refcount_t *ref, uint32_t references) ++refcount_init (refcount_t *ref, unsigned int references) +{ + *ref = references; +} + -+/* Increment REF. Return the result of the operation. */ -+static inline uint32_t ++/* Increment REF. Return the result of the operation. This function ++ uses atomic operations. It is not required to serialize calls to ++ this function. */ ++static inline unsigned int +refcount_ref (refcount_t *ref) +{ + return __atomic_add_fetch (ref, 1, __ATOMIC_RELAXED); +} + -+/* Decrement REF. Return the result of the operation. */ -+static inline uint32_t ++/* Decrement REF. Return the result of the operation. This function ++ uses atomic operations. It is not required to serialize calls to ++ this function. */ ++static inline unsigned int +refcount_deref (refcount_t *ref) +{ + return __atomic_sub_fetch (ref, 1, __ATOMIC_RELAXED); +} + -+/* Return REF. */ -+static inline uint32_t ++/* Return REF. This function uses atomic operations. It is not ++ required to serialize calls to this function. */ ++static inline unsigned int +refcount_references (refcount_t *ref) +{ + return __atomic_load_n (ref, __ATOMIC_RELAXED); @@ -100,7 +105,9 @@ index 0000000..946938a +} + +/* Increment the hard reference count of REF. If RESULT is not NULL, -+ the result of the operation is written there. */ ++ the result of the operation is written there. This function uses ++ atomic operations. It is not required to serialize calls to this ++ function. */ +static inline void +refcounts_ref (refcounts_t *ref, struct references *result) +{ @@ -111,7 +118,9 @@ index 0000000..946938a +} + +/* Decrement the hard reference count of REF. If RESULT is not NULL, -+ the result of the operation is written there. */ ++ the result of the operation is written there. This function uses ++ atomic operations. It is not required to serialize calls to this ++ function. */ +static inline void +refcounts_deref (refcounts_t *ref, struct references *result) +{ @@ -122,7 +131,9 @@ index 0000000..946938a +} + +/* Increment the weak reference count of REF. If RESULT is not NULL, -+ the result of the operation is written there. */ ++ the result of the operation is written there. This function uses ++ atomic operations. It is not required to serialize calls to this ++ function. */ +static inline void +refcounts_ref_weak (refcounts_t *ref, struct references *result) +{ @@ -133,7 +144,9 @@ index 0000000..946938a +} + +/* Decrement the weak reference count of REF. If RESULT is not NULL, -+ the result of the operation is written there. */ ++ the result of the operation is written there. This function uses ++ atomic operations. It is not required to serialize calls to this ++ function. */ +static inline void +refcounts_deref_weak (refcounts_t *ref, struct references *result) +{ @@ -143,7 +156,9 @@ index 0000000..946938a + ((union _references *) result)->rc = r; +} + -+/* Store the current reference counts of REF in RESULT. */ ++/* Store the current reference counts of REF in RESULT. This function ++ uses atomic operations. It is not required to serialize calls to ++ this function. */ +static inline void +refcounts_references (refcounts_t *ref, struct references *result) +{ @@ -151,7 +166,9 @@ index 0000000..946938a + __atomic_load_n (ref, __ATOMIC_RELAXED); +} + -+/* Return the hard reference count of REF. */ ++/* Return the hard reference count of REF. This function uses atomic ++ operations. It is not required to serialize calls to this ++ function. */ +static inline uint32_t +refcounts_hard_references (refcounts_t *ref) +{ @@ -160,7 +177,9 @@ index 0000000..946938a + return result.hard; +} + -+/* Return the weak reference count of REF. */ ++/* Return the weak reference count of REF. This function uses atomic ++ operations. It is not required to serialize calls to this ++ function. */ +static inline uint32_t +refcounts_weak_references (refcounts_t *ref) +{ diff --git a/debian/patches/0003-libports-lock-less-reference-counting-for-port_info-.patch b/debian/patches/0003-libports-lock-less-reference-counting-for-port_info-.patch index 9c5754ed..e03a61f7 100644 --- a/debian/patches/0003-libports-lock-less-reference-counting-for-port_info-.patch +++ b/debian/patches/0003-libports-lock-less-reference-counting-for-port_info-.patch @@ -1,10 +1,9 @@ -From 2644982be8c7d742f7d5be02ab9211c72bd356d5 Mon Sep 17 00:00:00 2001 +From c860c73eb7baf5d3846da968969d3b2ef7a541ac Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Sat, 3 May 2014 01:02:35 +0200 -Subject: [PATCH 3/5] libports: lock-less reference counting for port_info +Subject: [PATCH 03/11] libports: lock-less reference counting for port_info objects -* libports/refcount.h: New file with reference counting primitives. * libports/ports.h (struct port_info): Use the new type. * libports/lookup-port.c: No need to lock _ports_lock anymore. * libports/bucket-iterate.c: Likewise. diff --git a/debian/patches/0004-libdiskfs-lock-less-reference-counting-for-peropen-o.patch b/debian/patches/0004-libdiskfs-lock-less-reference-counting-for-peropen-o.patch index cd84b4bc..d90ccf45 100644 --- a/debian/patches/0004-libdiskfs-lock-less-reference-counting-for-peropen-o.patch +++ b/debian/patches/0004-libdiskfs-lock-less-reference-counting-for-peropen-o.patch @@ -1,7 +1,7 @@ -From 51331c90f52801c9f65a002629dff5f9e4fec90d Mon Sep 17 00:00:00 2001 +From e2a2dd50028147ab23a108f21432c47689c0ffd3 Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Tue, 6 May 2014 18:58:10 +0200 -Subject: [PATCH 4/5] libdiskfs: lock-less reference counting for peropen +Subject: [PATCH 04/11] libdiskfs: lock-less reference counting for peropen objects * libdiskfs/diskfs.h (struct peropen): Use refcount_t for field refcnt. diff --git a/debian/patches/0005-libtrivfs-lock-less-reference-counting-for-trivfs_pr.patch b/debian/patches/0005-libtrivfs-lock-less-reference-counting-for-trivfs_pr.patch index 917eece7..f269ee2b 100644 --- a/debian/patches/0005-libtrivfs-lock-less-reference-counting-for-trivfs_pr.patch +++ b/debian/patches/0005-libtrivfs-lock-less-reference-counting-for-trivfs_pr.patch @@ -1,10 +1,10 @@ -From 7eea4685744efdc62f843f88b3abfad4ccd9f699 Mon Sep 17 00:00:00 2001 +From 06c8ddf64b015b150a41a6af8ba8a6cf9d20fef0 Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Tue, 6 May 2014 19:07:13 +0200 -Subject: [PATCH 5/5] libtrivfs: lock-less reference counting for +Subject: [PATCH 05/11] libtrivfs: lock-less reference counting for trivfs_peropen objects -* libtrivfs/trivfs.h (struct trivfs_protid): Use refcount_t for field +* libtrivfs/trivfs.h (struct trivfs_peropen): Use refcount_t for field refcnt. (struct trivfs_control): Remove unused field lock. * libtrivfs/cntl-create.c (trivfs_create_control): Drop the mutex diff --git a/debian/patches/0006-libihash-use-an-integer-hash-function-on-the-keys.patch b/debian/patches/0006-libihash-use-an-integer-hash-function-on-the-keys.patch index 1fcd7a31..89aae003 100644 --- a/debian/patches/0006-libihash-use-an-integer-hash-function-on-the-keys.patch +++ b/debian/patches/0006-libihash-use-an-integer-hash-function-on-the-keys.patch @@ -1,7 +1,7 @@ -From 7849d265ce00e936df1a186647253cd2231d1c90 Mon Sep 17 00:00:00 2001 +From cf90fe8f338d8a3538b7b88e8c64cd0cbf8fda77 Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Thu, 8 May 2014 15:45:00 +0200 -Subject: [PATCH 6/6] libihash: use an integer hash function on the keys +Subject: [PATCH 06/11] libihash: use an integer hash function on the keys Use an integer hash function to derive the index from the key. This should reduce the number of collisions. diff --git a/debian/patches/0007-libihash-reduce-the-default-maximum-load-factor-to-7.patch b/debian/patches/0007-libihash-reduce-the-default-maximum-load-factor-to-7.patch index b82bed03..d4110817 100644 --- a/debian/patches/0007-libihash-reduce-the-default-maximum-load-factor-to-7.patch +++ b/debian/patches/0007-libihash-reduce-the-default-maximum-load-factor-to-7.patch @@ -1,7 +1,7 @@ -From 6c1bcd510bacf9ab630349a7317dcf0d7e6987a1 Mon Sep 17 00:00:00 2001 +From 0f30bbc488fcf38528c447b15c1d53c49f2b6cfb Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Thu, 8 May 2014 16:43:11 +0200 -Subject: [PATCH 7/7] libihash: reduce the default maximum load factor to 75% +Subject: [PATCH 07/11] libihash: reduce the default maximum load factor to 75% * libihash/ihash.h (HURD_IHASH_MAX_LOAD_DEFAULT): Set to 75. --- diff --git a/debian/patches/0008-libihash-use-linear-probing-and-fast-modulo-operatio.patch b/debian/patches/0008-libihash-use-linear-probing-and-fast-modulo-operatio.patch index 84c09fc3..1c4a394c 100644 --- a/debian/patches/0008-libihash-use-linear-probing-and-fast-modulo-operatio.patch +++ b/debian/patches/0008-libihash-use-linear-probing-and-fast-modulo-operatio.patch @@ -1,7 +1,7 @@ -From 6ad3d3f3558391f02468dbac2d1d73daa8e2f7e1 Mon Sep 17 00:00:00 2001 +From b18240df917ef17a7877164e098092728c139bb6 Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Thu, 8 May 2014 18:33:57 +0200 -Subject: [PATCH 8/8] libihash: use linear probing and fast modulo operation +Subject: [PATCH 08/11] libihash: use linear probing and fast modulo operation libihash uses open addressing. Previously, quadratic probing in both directions was used to resolve collisions. Quadratic probing might @@ -22,8 +22,8 @@ sizes, so a bit mask can be used for the modulo operation. * libihash/ihash.h (HURD_IHASH_MIN_SIZE): New macro. --- libihash/ihash.c | 121 ++++++------------------------------------------------- - libihash/ihash.h | 3 ++ - 2 files changed, 16 insertions(+), 108 deletions(-) + libihash/ihash.h | 4 ++ + 2 files changed, 17 insertions(+), 108 deletions(-) diff --git a/libihash/ihash.c b/libihash/ihash.c index 1de4c35..e74a2c5 100644 @@ -210,14 +210,15 @@ index 1de4c35..e74a2c5 100644 ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item)); diff --git a/libihash/ihash.h b/libihash/ihash.h -index 6bdc925..04c957f 100644 +index 6bdc925..057babc 100644 --- a/libihash/ihash.h +++ b/libihash/ihash.h -@@ -93,6 +93,9 @@ typedef struct hurd_ihash *hurd_ihash_t; +@@ -93,6 +93,10 @@ typedef struct hurd_ihash *hurd_ihash_t; /* Construction and destruction of hash tables. */ -+/* The size of the initial allocation in number of items. */ ++/* The size of the initial allocation in number of items. This must ++ be a power of two. */ +#define HURD_IHASH_MIN_SIZE 32 + /* The default value for the maximum load factor in percent. */ |