diff options
Diffstat (limited to 'debian/patches')
4 files changed, 307 insertions, 0 deletions
diff --git a/debian/patches/ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch b/debian/patches/ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch new file mode 100644 index 00000000..f115220d --- /dev/null +++ b/debian/patches/ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch @@ -0,0 +1,47 @@ +From 6c948532d2799bcc172053cac504c4aa5f016bba Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Thu, 15 May 2014 17:55:45 +0200 +Subject: [PATCH hurd 1/3] libihash: add hurd_ihash_value_valid + +* libihash/ihash.h (hurd_ihash_value_valid): New function. +* libihash/ihash.c (index_empty): Use hurd_ihash_value_valid. +--- + libihash/ihash.c | 3 +-- + libihash/ihash.h | 7 +++++++ + 2 files changed, 8 insertions(+), 2 deletions(-) + +diff --git a/libihash/ihash.c b/libihash/ihash.c +index fa29257..74e9edd 100644 +--- a/libihash/ihash.c ++++ b/libihash/ihash.c +@@ -37,8 +37,7 @@ + static inline int + index_empty (hurd_ihash_t ht, unsigned int idx) + { +- return ht->items[idx].value == _HURD_IHASH_EMPTY +- || ht->items[idx].value == _HURD_IHASH_DELETED; ++ return ! hurd_ihash_value_valid (ht->items[idx].value); + } + + +diff --git a/libihash/ihash.h b/libihash/ihash.h +index 849a55a..128027a 100644 +--- a/libihash/ihash.h ++++ b/libihash/ihash.h +@@ -41,6 +41,13 @@ typedef void *hurd_ihash_value_t; + #define _HURD_IHASH_EMPTY ((hurd_ihash_value_t) 0) + #define _HURD_IHASH_DELETED ((hurd_ihash_value_t) -1) + ++/* Test if VALUE is valid. */ ++static inline int ++hurd_ihash_value_valid (hurd_ihash_value_t value) ++{ ++ return value != _HURD_IHASH_EMPTY && value != _HURD_IHASH_DELETED; ++} ++ + /* The type of integer we want to use for the keys. */ + typedef uintptr_t hurd_ihash_key_t; + +-- +2.1.4 + diff --git a/debian/patches/ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch b/debian/patches/ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch new file mode 100644 index 00000000..2b5dd1f8 --- /dev/null +++ b/debian/patches/ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch @@ -0,0 +1,196 @@ +From c1d5c163a89f53a3c6e4e67f5f4119af96f7a470 Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Wed, 14 May 2014 16:24:21 +0200 +Subject: [PATCH hurd 2/3] libihash: optimize lookup-or-insert operations + +If libihash is used to implement a cache, a insertion is always +preceeded by a lookup. hurd_ihash_add has to do the lookup again. + +Provide a new pair of functions, hurd_ihash_locp_add and +hurd_ihash_locp_find, that can be used in combination to avoid the +second lookup. + +* libihash/ihash.c (hurd_ihash_locp_add): New function using a +location pointer... +(hurd_ihash_locp_find): ... that has been returned by this function. +* libihash/ihash.h (hurd_ihash_locp_add): New declaration. +(hurd_ihash_locp_find): Likewise. +(hurd_ihash_locp_value): New function. +--- + libihash/ihash.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++- + libihash/ihash.h | 52 +++++++++++++++++++++++++++++++++++++ + 2 files changed, 129 insertions(+), 1 deletion(-) + +diff --git a/libihash/ihash.c b/libihash/ihash.c +index 74e9edd..a97de3e 100644 +--- a/libihash/ihash.c ++++ b/libihash/ihash.c +@@ -244,7 +244,54 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) + return 0; + } + +- ++ ++/* Add VALUE to the hash table HT under the key KEY at LOCP. If there ++ already is an item under this key, call the cleanup function (if ++ any) for it before overriding the value. This function is faster ++ than hurd_ihash_add. ++ ++ If LOCP is NULL, fall back to hurd_ihash_add. Otherwise, LOCP must ++ be valid and may either be obtained from hurd_ihash_locp_find, or ++ from an item that is currently in the hash table. If an item is ++ replaced, KEY must match the key of the previous item. ++ ++ If a memory allocation error occurs, ENOMEM is returned, otherwise ++ 0. */ ++error_t ++hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, ++ hurd_ihash_key_t key, hurd_ihash_value_t value) ++{ ++ struct _hurd_ihash_item *item = (struct _hurd_ihash_item *) locp; ++ ++ /* In case of complications, fall back to hurd_ihash_add. */ ++ if (ht->size == 0 ++ || item == NULL ++ || item->value == _HURD_IHASH_DELETED ++ || hurd_ihash_get_load (ht) > ht->max_load) ++ return hurd_ihash_add (ht, key, value); ++ ++ if (item->value == _HURD_IHASH_EMPTY) ++ { ++ item->key = key; ++ ht->nr_items += 1; ++ } ++ else ++ { ++ assert (item->key == key); ++ if (ht->cleanup) ++ (*ht->cleanup) (locp, ht->cleanup_data); ++ } ++ ++ item->value = value; ++ ++ if (ht->locp_offset != HURD_IHASH_NO_LOCP) ++ *((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset)) ++ = locp; ++ ++ return 0; ++} ++ ++ + /* Add ITEM to the hash table HT under the key KEY. If there already + is an item under this key, call the cleanup function (if any) for + it before overriding the value. If a memory allocation error +@@ -313,6 +360,35 @@ hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key) + } + } + ++/* Find the item in the hash table HT with key KEY. If it is found, ++ return the location of its slot in the hash table. If it is not ++ found, this function may still return a location. ++ ++ This location pointer can always be safely accessed using ++ hurd_ihash_locp_value. If the lookup is successful, ++ hurd_ihash_locp_value will return the value related to KEY. ++ ++ If the lookup is successful, the returned location can be used with ++ hurd_ihash_locp_add to update the item, and with ++ hurd_ihash_locp_remove to remove it. ++ ++ If the lookup is not successful, the returned location can be used ++ with hurd_ihash_locp_add to add the item. ++ ++ Note that returned location is only valid until the next insertion ++ or deletion. */ ++hurd_ihash_locp_t ++hurd_ihash_locp_find (hurd_ihash_t ht, hurd_ihash_key_t key) ++{ ++ int idx; ++ ++ if (ht->size == 0) ++ return NULL; ++ ++ idx = find_index (ht, key); ++ return &ht->items[idx].value; ++} ++ + + /* Remove the entry with the key KEY from the hash table HT. If such + an entry was found and removed, 1 is returned, otherwise 0. */ +diff --git a/libihash/ihash.h b/libihash/ihash.h +index 128027a..1dbc348 100644 +--- a/libihash/ihash.h ++++ b/libihash/ihash.h +@@ -26,6 +26,7 @@ + #include <sys/types.h> + #include <limits.h> + #include <stdint.h> ++#include <stddef.h> + + + /* The type of the values corresponding to the keys. Must be a +@@ -198,10 +199,61 @@ hurd_ihash_get_load (hurd_ihash_t ht) + error_t hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, + hurd_ihash_value_t item); + ++/* Add VALUE to the hash table HT under the key KEY at LOCP. If there ++ already is an item under this key, call the cleanup function (if ++ any) for it before overriding the value. This function is faster ++ than hurd_ihash_add. ++ ++ If LOCP is NULL, fall back to hurd_ihash_add. Otherwise, LOCP must ++ be valid and may either be obtained from hurd_ihash_locp_find, or ++ from an item that is currently in the hash table. If an item is ++ replaced, KEY must match the key of the previous item. ++ ++ If a memory allocation error occurs, ENOMEM is returned, otherwise ++ 0. */ ++error_t hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, ++ hurd_ihash_key_t key, hurd_ihash_value_t value); ++ + /* Find and return the item in the hash table HT with key KEY, or NULL + if it doesn't exist. */ + hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key); + ++/* Find the item in the hash table HT with key KEY. If it is found, ++ return the location of its slot in the hash table. If it is not ++ found, this function may still return a location. ++ ++ This location pointer can always be safely accessed using ++ hurd_ihash_locp_value. If the lookup is successful, ++ hurd_ihash_locp_value will return the value related to KEY. ++ ++ If the lookup is successful, the returned location can be used with ++ hurd_ihash_locp_add to update the item, and with ++ hurd_ihash_locp_remove to remove it. ++ ++ If the lookup is not successful, the returned location can be used ++ with hurd_ihash_locp_add to add the item. ++ ++ Note that returned location is only valid until the next insertion ++ or deletion. */ ++hurd_ihash_locp_t hurd_ihash_locp_find (hurd_ihash_t ht, ++ hurd_ihash_key_t key); ++ ++/* Given an hash table bucket location LOCP, return the value stored ++ there, or NULL if it is empty or LOCP is NULL. */ ++static inline void * ++hurd_ihash_locp_value (hurd_ihash_locp_t locp) ++{ ++ struct _hurd_ihash_item *item = (struct _hurd_ihash_item *) locp; ++ ++ if (item == NULL) ++ return NULL; ++ ++ if (hurd_ihash_value_valid (item->value)) ++ return item->value; ++ ++ return NULL; ++} ++ + /* Iterate over all elements in the hash table. You use this macro + with a block, for example like this: + +-- +2.1.4 + diff --git a/debian/patches/ihash-as-cache0003-libihash-prefer-performance-degradation-over-failure.patch b/debian/patches/ihash-as-cache0003-libihash-prefer-performance-degradation-over-failure.patch new file mode 100644 index 00000000..90178650 --- /dev/null +++ b/debian/patches/ihash-as-cache0003-libihash-prefer-performance-degradation-over-failure.patch @@ -0,0 +1,61 @@ +From 820fa61ad45099e413acc04674ca645ad758e26b Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Sun, 7 Jun 2015 00:58:36 +0200 +Subject: [PATCH hurd 3/3] libihash: prefer performance degradation over + failure + +* libihash/ihash.c (hurd_ihash_add): Add the item even though we are +above the load factor if resizing failed. +--- + libihash/ihash.c | 14 ++++++++++++-- + 1 file changed, 12 insertions(+), 2 deletions(-) + +diff --git a/libihash/ihash.c b/libihash/ihash.c +index a97de3e..8133e01 100644 +--- a/libihash/ihash.c ++++ b/libihash/ihash.c +@@ -301,18 +301,19 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) + { + struct hurd_ihash old_ht = *ht; + int was_added; ++ int fatal = 0; /* bail out on allocation errors */ + unsigned int i; + + if (ht->size) + { + /* Only fill the hash table up to its maximum load factor. */ + if (hurd_ihash_get_load (ht) <= ht->max_load) ++ add_one: + if (add_one (ht, key, item)) + return 0; + } + + /* The hash table is too small, and we have to increase it. */ +- ht->nr_items = 0; + if (ht->size == 0) + ht->size = HURD_IHASH_MIN_SIZE; + else +@@ -324,10 +325,19 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) + if (ht->items == NULL) + { + *ht = old_ht; +- return ENOMEM; ++ if (fatal || ht->size == 0) ++ return ENOMEM; ++ ++ /* We prefer performance degradation over failure. Therefore, ++ we add the item even though we are above the load factor. If ++ the table is full, this will fail. We set the fatal flag to ++ avoid looping. */ ++ fatal = 1; ++ goto add_one; + } + + /* We have to rehash the old entries. */ ++ ht->nr_items = 0; + for (i = 0; i < old_ht.size; i++) + if (!index_empty (&old_ht, i)) + { +-- +2.1.4 + diff --git a/debian/patches/series b/debian/patches/series index 1ec2b4a9..5fbb94bd 100644 --- a/debian/patches/series +++ b/debian/patches/series @@ -53,3 +53,6 @@ introspection0006-libpager-annotate-objects-managed-by-libports.patch introspection0007-ext2fs-annotate-objects-managed-by-libports.patch introspection0008-utils-rpctrace-support-attaching-to-servers.patch introspection0009-pflocal-annotate-objects-managed-by-libports.patch +ihash-as-cache0001-libihash-add-hurd_ihash_value_valid.patch +ihash-as-cache0002-libihash-optimize-lookup-or-insert-operations.patch +ihash-as-cache0003-libihash-prefer-performance-degradation-over-failure.patch |