diff options
Diffstat (limited to 'debian')
5 files changed, 466 insertions, 0 deletions
diff --git a/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch b/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch new file mode 100644 index 00000000..bd7498c1 --- /dev/null +++ b/debian/patches/ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch @@ -0,0 +1,109 @@ +From 5aa7e263521b934c2e23e7fb795fd9163999219a Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Sat, 21 Nov 2015 16:12:53 +0100 +Subject: [PATCH hurd 1/4] libihash: fix ill-devised locp lookup interface + +* libihash/ihash.c (hurd_ihash_locp_find): Return both the item and the slot. +* libihash/ihash.h (hurd_ihash_locp_find): Adjust prototype. +(hurd_ihash_locp_value): Remove function. +--- + libihash/ihash.c | 19 +++++++++---------- + libihash/ihash.h | 31 ++++++------------------------- + 2 files changed, 15 insertions(+), 35 deletions(-) + +diff --git a/libihash/ihash.c b/libihash/ihash.c +index 87d7abf..8b1ad1f 100644 +--- a/libihash/ihash.c ++++ b/libihash/ihash.c +@@ -370,13 +370,9 @@ 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. ++/* Find and return the item in the hash table HT with key KEY, or NULL ++ if it doesn't exist. If it is not found, this function may still ++ return a location in SLOT. + + If the lookup is successful, the returned location can be used with + hurd_ihash_locp_add to update the item, and with +@@ -387,8 +383,10 @@ hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key) + + 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) ++hurd_ihash_value_t ++hurd_ihash_locp_find (hurd_ihash_t ht, ++ hurd_ihash_key_t key, ++ hurd_ihash_locp_t *slot) + { + int idx; + +@@ -396,7 +394,8 @@ hurd_ihash_locp_find (hurd_ihash_t ht, hurd_ihash_key_t key) + return NULL; + + idx = find_index (ht, key); +- return &ht->items[idx].value; ++ *slot = &ht->items[idx].value; ++ return index_valid (ht, idx, key) ? ht->items[idx].value : NULL; + } + + +diff --git a/libihash/ihash.h b/libihash/ihash.h +index 1dbc348..fdfc367 100644 +--- a/libihash/ihash.h ++++ b/libihash/ihash.h +@@ -218,13 +218,9 @@ error_t hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, + 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. ++/* Find and return the item in the hash table HT with key KEY, or NULL ++ if it doesn't exist. If it is not found, this function may still ++ return a location in SLOT. + + If the lookup is successful, the returned location can be used with + hurd_ihash_locp_add to update the item, and with +@@ -235,24 +231,9 @@ hurd_ihash_value_t hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key); + + 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; +-} ++hurd_ihash_value_t hurd_ihash_locp_find (hurd_ihash_t ht, ++ hurd_ihash_key_t key, ++ hurd_ihash_locp_t *slot); + + /* 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-cache0002-libihash-fix-fast-insertion-corner-case.patch b/debian/patches/ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch new file mode 100644 index 00000000..341f580e --- /dev/null +++ b/debian/patches/ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch @@ -0,0 +1,26 @@ +From 143ea78cf3e14b9f9f7609e9fbb0a30635a92788 Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Sun, 22 Nov 2015 18:13:01 +0100 +Subject: [PATCH hurd 2/4] libihash: fix fast insertion corner case + +* libihash/ihash.c (hurd_ihash_locp_add): Fix insertion if the key +doesn't match. +--- + libihash/ihash.c | 1 + + 1 file changed, 1 insertion(+) + +diff --git a/libihash/ihash.c b/libihash/ihash.c +index 8b1ad1f..598d341 100644 +--- a/libihash/ihash.c ++++ b/libihash/ihash.c +@@ -267,6 +267,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, + if (ht->size == 0 + || item == NULL + || item->value == _HURD_IHASH_DELETED ++ || ! compare (ht, item->key, key) + || hurd_ihash_get_load (ht) > ht->max_load) + return hurd_ihash_add (ht, key, value); + +-- +2.1.4 + diff --git a/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch b/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch new file mode 100644 index 00000000..9c0ce1e2 --- /dev/null +++ b/debian/patches/ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch @@ -0,0 +1,218 @@ +From 5ee3f205f6aa7a15dfd7be26467000c550db7e4f Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Sat, 21 Nov 2015 16:27:40 +0100 +Subject: [PATCH hurd 3/4] libihash: generalize the interface to support + non-integer keys + +* libihash/ihash.c (hash, compare): New functions that are used +throughout libihash to hash and compare keys. +(hurd_ihash_set_gki): New function. +* libihash/ihash.h (hurd_ihash_fct_hash_t): New type for hash functions. +(hurd_ihash_fct_cmp_t): New type for comparison functions. +(struct hurd_ihash): New fields for hash and comparison functions. +(hurd_ihash_set_gki): New prototype. +--- + libihash/ihash.c | 58 +++++++++++++++++++++++++++++++++++++++++++++----------- + libihash/ihash.h | 26 ++++++++++++++++++++++++- + 2 files changed, 72 insertions(+), 12 deletions(-) + +diff --git a/libihash/ihash.c b/libihash/ihash.c +index 598d341..8e7383e 100644 +--- a/libihash/ihash.c ++++ b/libihash/ihash.c +@@ -1,5 +1,5 @@ + /* ihash.c - Integer-keyed hash table functions. +- Copyright (C) 1993-1997, 2001, 2003, 2004, 2006 ++ Copyright (C) 1993-1997, 2001, 2003, 2004, 2006, 2014, 2015 + Free Software Foundation, Inc. + Written by Michael I. Bushnell. + Revised by Miles Bader <miles@gnu.org>. +@@ -32,6 +32,21 @@ + + #include "ihash.h" + ++/* This function is used to hash the key. */ ++static inline hurd_ihash_key_t ++hash (hurd_ihash_t ht, hurd_ihash_key_t k) ++{ ++ return ht->fct_hash ? ht->fct_hash ((void *) k) : k; ++} ++ ++/* This function is used to compare the key. Returns true if A is ++ equal to B. */ ++static inline int ++compare (hurd_ihash_t ht, hurd_ihash_key_t a, hurd_ihash_key_t b) ++{ ++ return ht->fct_cmp ? (a && ht->fct_cmp (a, b)) : a == b; ++} ++ + /* Return 1 if the slot with the index IDX in the hash table HT is + empty, and 0 otherwise. */ + static inline int +@@ -46,7 +61,7 @@ index_empty (hurd_ihash_t ht, unsigned int idx) + static inline int + index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key) + { +- return !index_empty (ht, idx) && ht->items[idx].key == key; ++ return !index_empty (ht, idx) && compare (ht, ht->items[idx].key, key); + } + + +@@ -60,9 +75,10 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) + unsigned int up_idx; + unsigned int mask = ht->size - 1; + +- idx = key & mask; ++ idx = hash (ht, key) & mask; + +- if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key) ++ if (ht->items[idx].value == _HURD_IHASH_EMPTY ++ || compare (ht, ht->items[idx].key, key)) + return idx; + + up_idx = idx; +@@ -71,7 +87,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) + { + up_idx = (up_idx + 1) & mask; + if (ht->items[up_idx].value == _HURD_IHASH_EMPTY +- || ht->items[up_idx].key == key) ++ || compare (ht, ht->items[up_idx].key, key)) + return up_idx; + } + while (up_idx != idx); +@@ -88,9 +104,11 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) + static inline void + locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp) + { ++ struct _hurd_ihash_item *item = locp; + if (ht->cleanup) +- (*ht->cleanup) (*locp, ht->cleanup_data); +- *locp = _HURD_IHASH_DELETED; ++ (*ht->cleanup) (item->value, ht->cleanup_data); ++ item->value = _HURD_IHASH_DELETED; ++ item->key = 0; + ht->nr_items--; + } + +@@ -106,6 +124,8 @@ hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs) + ht->locp_offset = locp_offs; + ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT; + ht->cleanup = 0; ++ ht->fct_hash = NULL; ++ ht->fct_cmp = NULL; + } + + +@@ -166,6 +186,21 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, + } + + ++/* Use the generalized key interface. Must be called before any item ++ is inserted into the table. */ ++void ++hurd_ihash_set_gki (hurd_ihash_t ht, ++ hurd_ihash_fct_hash_t fct_hash, ++ hurd_ihash_fct_cmp_t fct_cmp) ++{ ++ assert (ht->size == 0 || !"called after insertion"); ++ assert (fct_hash); ++ assert (fct_cmp); ++ ht->fct_hash = fct_hash; ++ ht->fct_cmp = fct_cmp; ++} ++ ++ + /* Set the maximum load factor in binary percent to MAX_LOAD, which + should be between 64 and 128. The default is + HURD_IHASH_MAX_LOAD_DEFAULT. New elements are only added to the +@@ -199,10 +234,11 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) + unsigned int first_free; + unsigned int mask = ht->size - 1; + +- idx = key & mask; ++ idx = hash (ht, key) & mask; + first_free = idx; + +- if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key) ++ if (ht->items[idx].value != _HURD_IHASH_EMPTY ++ && ! compare (ht, ht->items[idx].key, key)) + { + unsigned int up_idx = idx; + +@@ -210,7 +246,7 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) + { + up_idx = (up_idx + 1) & mask; + if (ht->items[up_idx].value == _HURD_IHASH_EMPTY +- || ht->items[up_idx].key == key) ++ || compare (ht, ht->items[up_idx].key, key)) + { + idx = up_idx; + break; +@@ -278,7 +314,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, + } + else + { +- assert (item->key == key); ++ assert (compare (ht, item->key, key)); + if (ht->cleanup) + (*ht->cleanup) (locp, ht->cleanup_data); + } +diff --git a/libihash/ihash.h b/libihash/ihash.h +index fdfc367..986291b 100644 +--- a/libihash/ihash.h ++++ b/libihash/ihash.h +@@ -1,5 +1,5 @@ + /* ihash.h - Integer keyed hash table interface. +- Copyright (C) 1995, 2003, 2004 Free Software Foundation, Inc. ++ Copyright (C) 1995, 2003, 2004, 2014, 2015 Free Software Foundation, Inc. + Written by Miles Bader <miles@gnu.org>. + Revised by Marcus Brinkmann <marcus@gnu.org>. + +@@ -57,6 +57,20 @@ typedef uintptr_t hurd_ihash_key_t; + typedef hurd_ihash_value_t *hurd_ihash_locp_t; + + ++/* We support non-integer keys using the generalized key interface. ++ ++ To use it, supply a pair of functions matching the following ++ specification, and use pointers to the key instead of the key ++ itself in all calls to libihash. */ ++ ++/* The type of a function computing a hash for the given key. */ ++typedef hurd_ihash_key_t (*hurd_ihash_fct_hash_t) (void *); ++ ++/* The type of a function comparing two given keys. Return true if ++ both keys are equal. */ ++typedef int (*hurd_ihash_fct_cmp_t) (void *, void *); ++ ++ + /* The type of the cleanup function, which is called for every value + removed from the hash table. */ + typedef void (*hurd_ihash_cleanup_t) (hurd_ihash_value_t value, void *arg); +@@ -95,6 +109,10 @@ struct hurd_ihash + second argument. This does not happen if CLEANUP is NULL. */ + hurd_ihash_cleanup_t cleanup; + void *cleanup_data; ++ ++ /* User-supplied functions for the generalized key interface. */ ++ hurd_ihash_fct_hash_t fct_hash; ++ hurd_ihash_fct_cmp_t fct_cmp; + }; + typedef struct hurd_ihash *hurd_ihash_t; + +@@ -152,6 +170,12 @@ void hurd_ihash_free (hurd_ihash_t ht); + void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, + void *cleanup_data); + ++/* Use the generalized key interface. Must be called before any item ++ is inserted into the table. */ ++void hurd_ihash_set_gki (hurd_ihash_t ht, ++ hurd_ihash_fct_hash_t fct_hash, ++ hurd_ihash_fct_cmp_t fct_cmp); ++ + /* Set the maximum load factor in binary percent to MAX_LOAD, which + should be between 64 and 128. The default is + HURD_IHASH_MAX_LOAD_DEFAULT. New elements are only added to the +-- +2.1.4 + diff --git a/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch b/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch new file mode 100644 index 00000000..d278298c --- /dev/null +++ b/debian/patches/ihash-as-cache0004-libihash-fix-item-insertion.patch @@ -0,0 +1,109 @@ +From 1e52fab24dd7dc549c6120ff4c2904be5f1f852b Mon Sep 17 00:00:00 2001 +From: Justus Winter <4winter@informatik.uni-hamburg.de> +Date: Sun, 22 Nov 2015 21:04:51 +0100 +Subject: [PATCH hurd 4/4] libihash: fix item insertion + +* libihash/ihash.c (find_index): Keep track and return the index where +we could insert the item. +(add_one): Use 'find_index'. +--- + libihash/ihash.c | 54 ++++++++++++++++++------------------------------------ + 1 file changed, 18 insertions(+), 36 deletions(-) + +diff --git a/libihash/ihash.c b/libihash/ihash.c +index 8e7383e..ae9f970 100644 +--- a/libihash/ihash.c ++++ b/libihash/ihash.c +@@ -73,6 +73,8 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) + { + unsigned int idx; + unsigned int up_idx; ++ unsigned int first_deleted = 0; ++ int first_deleted_set = 0; + unsigned int mask = ht->size - 1; + + idx = hash (ht, key) & mask; +@@ -86,15 +88,21 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) + do + { + up_idx = (up_idx + 1) & mask; +- if (ht->items[up_idx].value == _HURD_IHASH_EMPTY +- || compare (ht, ht->items[up_idx].key, key)) ++ if (ht->items[up_idx].value == _HURD_IHASH_EMPTY) ++ return first_deleted_set ? first_deleted : up_idx; ++ if (compare (ht, ht->items[up_idx].key, key)) + return up_idx; ++ if (! first_deleted_set ++ && ht->items[up_idx].value == _HURD_IHASH_DELETED) ++ first_deleted = up_idx, first_deleted_set = 1; + } + while (up_idx != idx); + +- /* If we end up here, the item could not be found. Return any +- invalid index. */ +- return idx; ++ /* If we end up here, the item could not be found. Return the index ++ of the first deleted item, as this is the position where we can ++ insert an item with the given key once we established that it is ++ not in the table. */ ++ return first_deleted; + } + + +@@ -231,48 +239,22 @@ static inline int + add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) + { + unsigned int idx; +- unsigned int first_free; +- unsigned int mask = ht->size - 1; +- +- idx = hash (ht, key) & mask; +- first_free = idx; +- +- if (ht->items[idx].value != _HURD_IHASH_EMPTY +- && ! compare (ht, ht->items[idx].key, key)) +- { +- unsigned int up_idx = idx; + +- do +- { +- up_idx = (up_idx + 1) & mask; +- if (ht->items[up_idx].value == _HURD_IHASH_EMPTY +- || compare (ht, ht->items[up_idx].key, key)) +- { +- idx = up_idx; +- break; +- } +- } +- while (up_idx != idx); +- } ++ idx = find_index (ht, key); + + /* Remove the old entry for this key if necessary. */ + if (index_valid (ht, idx, key)) + locp_remove (ht, &ht->items[idx].value); + +- /* If we have not found an empty slot, maybe the last one we +- looked at was empty (or just got deleted). */ +- if (!index_empty (ht, first_free)) +- first_free = idx; +- +- if (index_empty (ht, first_free)) ++ if (index_empty (ht, idx)) + { + ht->nr_items++; +- ht->items[first_free].value = value; +- ht->items[first_free].key = key; ++ ht->items[idx].value = value; ++ ht->items[idx].key = key; + + if (ht->locp_offset != HURD_IHASH_NO_LOCP) + *((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset)) +- = &ht->items[first_free].value; ++ = &ht->items[idx].value; + + return 1; + } +-- +2.1.4 + diff --git a/debian/patches/series b/debian/patches/series index 61535e3b..d16482ae 100644 --- a/debian/patches/series +++ b/debian/patches/series @@ -58,3 +58,7 @@ 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 +ihash-as-cache0001-libihash-fix-ill-devised-locp-lookup-interface.patch +ihash-as-cache0002-libihash-fix-fast-insertion-corner-case.patch +ihash-as-cache0003-libihash-generalize-the-interface-to-support-non-int.patch +ihash-as-cache0004-libihash-fix-item-insertion.patch |