[PATCH 0/9] hashmap fixes

[PATCH 0/9] hashmap fixes

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 843 bytes --]

Hi,

noticed some issues in hashmap while implementing
an applicantion on top of ell.

Cheers,
Jukka

Jukka Rissanen (9):
  hashmap: Add value free function
  hashmap: Call user supplied value free function in destroy
  hashmap: Call user supplied value free function in insert
  unit: hashmap: Add value free hash entry test
  unit: hashmap: Add replace entry test
  hashmap: Add re-entrancy support to foreach function
  unit: hashmap: Re-entrancy tests added
  hashmap: Add support to finding an element from hash
  unit: hashmap: Add unit test for l_hashmap_find

 ell/hashmap.c       | 176 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 ell/hashmap.h       |  11 ++++
 unit/test-hashmap.c | 142 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 326 insertions(+), 3 deletions(-)

-- 
1.8.3.1

[PATCH 1/9] hashmap: Add value free function

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 2914 bytes --]

User is able to set a function to free the value of the hashmap
entry.
---
 ell/hashmap.c | 37 +++++++++++++++++++++++++++++++++++++
 ell/hashmap.h |  6 ++++++
 2 files changed, 43 insertions(+)

diff --git a/ell/hashmap.c b/ell/hashmap.c
index b60cc62..f707d64 100644
--- a/ell/hashmap.c
+++ b/ell/hashmap.c
@@ -54,6 +54,8 @@ struct l_hashmap {
 	l_hashmap_compare_func_t compare_func;
 	l_hashmap_key_new_func_t key_new_func;
 	l_hashmap_key_free_func_t key_free_func;
+	l_hashmap_value_free_func_t value_free_func;
+	void *user_data;
 	unsigned int entries;
 	struct entry buckets[NBUCKETS];
 };
@@ -73,6 +75,12 @@ static inline void free_key(const struct l_hashmap *hashmap, void *key)
 		hashmap->key_free_func(key);
 }
 
+static inline void free_value(const struct l_hashmap *hashmap, void *value)
+{
+	if (hashmap->value_free_func)
+		hashmap->value_free_func(hashmap, value, hashmap->user_data);
+}
+
 static inline unsigned int hash_superfast(const uint8_t *key, unsigned int len)
 {
 	/*
@@ -307,6 +315,35 @@ LIB_EXPORT bool l_hashmap_set_key_free_function(struct l_hashmap *hashmap,
 }
 
 /**
+ * l_hashmap_set_value_free_function:
+ * @hashmap: hash table object
+ * @func: Value destructor function
+ *
+ * Sets the value destructor function to be used by this object.
+ * This function can be NULL, in which case no destructor is called.
+ *
+ * This function can only be called when the @hashmap is empty.
+ *
+ * Returns: #true when the value free function could be updated successfully,
+ * and #false otherwise.
+ **/
+LIB_EXPORT bool l_hashmap_set_value_free_function(struct l_hashmap *hashmap,
+					l_hashmap_value_free_func_t func,
+					void *user_data)
+{
+	if (unlikely(!hashmap))
+		return false;
+
+	if (hashmap->entries != 0)
+		return false;
+
+	hashmap->value_free_func = func;
+	hashmap->user_data = user_data;
+
+	return true;
+}
+
+/**
  * l_hashmap_destroy:
  * @hashmap: hash table object
  * @destroy: destroy function
diff --git a/ell/hashmap.h b/ell/hashmap.h
index 9f4f5fa..a904109 100644
--- a/ell/hashmap.h
+++ b/ell/hashmap.h
@@ -39,6 +39,9 @@ typedef void (*l_hashmap_key_free_func_t) (void *p);
 
 struct l_hashmap;
 
+typedef void (*l_hashmap_value_free_func_t) (const struct l_hashmap *hashmap,
+					void *p, void *user_data);
+
 unsigned int l_str_hash(const void *p);
 
 struct l_hashmap *l_hashmap_new(void);
@@ -52,6 +55,9 @@ bool l_hashmap_set_key_copy_function(struct l_hashmap *hashmap,
 						l_hashmap_key_new_func_t func);
 bool l_hashmap_set_key_free_function(struct l_hashmap *hashmap,
 					l_hashmap_key_free_func_t func);
+bool l_hashmap_set_value_free_function(struct l_hashmap *hashmap,
+				l_hashmap_value_free_func_t func,
+				void *user_data);
 
 void l_hashmap_destroy(struct l_hashmap *hashmap,
 			l_hashmap_destroy_func_t destroy);
-- 
1.8.3.1

[PATCH 2/9] hashmap: Call user supplied value free function in destroy

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 1000 bytes --]

If user has supplied a value free function, then that will be
called for each deleted entry.
---
 ell/hashmap.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/ell/hashmap.c b/ell/hashmap.c
index f707d64..c51abfd 100644
--- a/ell/hashmap.c
+++ b/ell/hashmap.c
@@ -349,6 +349,9 @@ LIB_EXPORT bool l_hashmap_set_value_free_function(struct l_hashmap *hashmap,
  * @destroy: destroy function
  *
  * Free hash table and call @destory on all remaining entries.
+ * If user has set the value free function by
+ * l_hashmap_set_value_free_function() then the user specified free
+ * function will be called in order to free the value.
  **/
 LIB_EXPORT void l_hashmap_destroy(struct l_hashmap *hashmap,
 				l_hashmap_destroy_func_t destroy)
@@ -369,6 +372,7 @@ LIB_EXPORT void l_hashmap_destroy(struct l_hashmap *hashmap,
 				destroy(entry->value);
 
 			free_key(hashmap, entry->key);
+			free_value(hashmap, entry->value);
 
 			next = entry->next;
 
-- 
1.8.3.1

Re: [PATCH 2/9] hashmap: Call user supplied value free function in destroy

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 1353 bytes --]

Hi Jukka,

On 02/10/2015 08:42 AM, Jukka Rissanen wrote:
> If user has supplied a value free function, then that will be
> called for each deleted entry.
> ---
>   ell/hashmap.c | 4 ++++
>   1 file changed, 4 insertions(+)
>
> diff --git a/ell/hashmap.c b/ell/hashmap.c
> index f707d64..c51abfd 100644
> --- a/ell/hashmap.c
> +++ b/ell/hashmap.c
> @@ -349,6 +349,9 @@ LIB_EXPORT bool l_hashmap_set_value_free_function(struct l_hashmap *hashmap,
>    * @destroy: destroy function
>    *
>    * Free hash table and call @destory on all remaining entries.
> + * If user has set the value free function by
> + * l_hashmap_set_value_free_function() then the user specified free
> + * function will be called in order to free the value.
>    **/
>   LIB_EXPORT void l_hashmap_destroy(struct l_hashmap *hashmap,
>   				l_hashmap_destroy_func_t destroy)
> @@ -369,6 +372,7 @@ LIB_EXPORT void l_hashmap_destroy(struct l_hashmap *hashmap,
>   				destroy(entry->value);
>
>   			free_key(hashmap, entry->key);
> +			free_value(hashmap, entry->value);

So this is not the way hashmap has been designed.  The destroy function 
(which is the last argument to this call) is being called already to 
cleanup memory, etc.  In effect, you're now duplicating this functionality.

>
>   			next = entry->next;
>
>

Regards,
-Denis

[PATCH 3/9] hashmap: Call user supplied value free function in insert

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 1590 bytes --]

If user has supplied a value free function, then that will be
called for each replaced entry.
---
 ell/hashmap.c | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)

diff --git a/ell/hashmap.c b/ell/hashmap.c
index c51abfd..a204726 100644
--- a/ell/hashmap.c
+++ b/ell/hashmap.c
@@ -393,7 +393,11 @@ LIB_EXPORT void l_hashmap_destroy(struct l_hashmap *hashmap,
  * @key: key pointer
  * @value: value pointer
  *
- * Insert new @value entry with @key.
+ * Insert new @value entry with @key. If there is already an same key
+ * in the hash, the new value will replace the old one. If user has set
+ * the value free function by l_hashmap_set_value_free_function() then
+ * the user specified free function will be called in order to free the
+ * value.
  *
  * Returns: #true when value has been added and #false in case of failure
  **/
@@ -419,6 +423,27 @@ LIB_EXPORT bool l_hashmap_insert(struct l_hashmap *hashmap,
 		goto done;
 	}
 
+	/* If the key is already in the hash, we just replace the value */
+	for (entry = head;; entry = entry->next) {
+		if (entry->hash == hash &&
+				!hashmap->compare_func(key, entry->key)) {
+			if (entry->key != key_new) {
+				free_key(hashmap, entry->key);
+				entry->key = key_new;
+			}
+
+			if (entry->value != value) {
+				free_value(hashmap, entry->value);
+				entry->value = value;
+			}
+
+			return true;
+		}
+
+		if (entry->next == head)
+			break;
+	}
+
 	entry = l_new(struct entry, 1);
 	entry->key = key_new;
 	entry->value = value;
-- 
1.8.3.1

Re: [PATCH 3/9] hashmap: Call user supplied value free function in insert

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 2750 bytes --]

Hi Jukka,

On 02/10/2015 08:42 AM, Jukka Rissanen wrote:
> If user has supplied a value free function, then that will be
> called for each replaced entry.
> ---
>   ell/hashmap.c | 27 ++++++++++++++++++++++++++-
>   1 file changed, 26 insertions(+), 1 deletion(-)
>
> diff --git a/ell/hashmap.c b/ell/hashmap.c
> index c51abfd..a204726 100644
> --- a/ell/hashmap.c
> +++ b/ell/hashmap.c
> @@ -393,7 +393,11 @@ LIB_EXPORT void l_hashmap_destroy(struct l_hashmap *hashmap,
>    * @key: key pointer
>    * @value: value pointer
>    *
> - * Insert new @value entry with @key.
> + * Insert new @value entry with @key. If there is already an same key
> + * in the hash, the new value will replace the old one. If user has set
> + * the value free function by l_hashmap_set_value_free_function() then
> + * the user specified free function will be called in order to free the
> + * value.
>    *
>    * Returns: #true when value has been added and #false in case of failure
>    **/
> @@ -419,6 +423,27 @@ LIB_EXPORT bool l_hashmap_insert(struct l_hashmap *hashmap,
>   		goto done;
>   	}
>

So the current implementation allows duplicates to be added.  However, 
it is implementation dependent what happens if you lookup a duplicate 
key.  With the current implementation, the item inserted first is 
returned.  I don't think enforcement of unique keys is required at the 
hashmap_insert level.  The user should not be always made to pay the 
cost of duplicate detection (e.g. if he knows no duplicates will ever be 
present).

If duplicates are an issue, the way to handle this in the client code 
would be to
	- Call l_hashmap_remove first
	- Insert the new element

Alternatively, you could add an l_hashmap_replace() method call, e.g.:

bool l_hashmap_replace(struct l_hashmap *hashmap,
                         const void *key, void *value,
			l_hashmap_destroy_func_t destroy);

> +	/* If the key is already in the hash, we just replace the value */
> +	for (entry = head;; entry = entry->next) {
> +		if (entry->hash == hash &&
> +				!hashmap->compare_func(key, entry->key)) {
> +			if (entry->key != key_new) {
> +				free_key(hashmap, entry->key);
> +				entry->key = key_new;
> +			}

So this part doesn't really match the comment above.  You're also 
freeing the key, which is an unnecessary step.  If the keys are the 
same, just reuse them.

> +
> +			if (entry->value != value) {
> +				free_value(hashmap, entry->value);
> +				entry->value = value;
> +			}
> +
> +			return true;
> +		}
> +
> +		if (entry->next == head)
> +			break;
> +	}
> +
>   	entry = l_new(struct entry, 1);
>   	entry->key = key_new;
>   	entry->value = value;
>

Regards,
-Denis

Re: [PATCH 3/9] hashmap: Call user supplied value free function in insert

[Patrik Flykt]

[-- Attachment #1: Type: text/plain, Size: 595 bytes --]

On Tue, 2015-02-10 at 13:18 -0600, Denis Kenzior wrote:
> With the current implementation, the item inserted first is 
> returned.  I don't think enforcement of unique keys is required at the
> hashmap_insert level.

As long as there is no function to read out more than one of the values
from the hashmap, the hashmap should definitely require keys to be
unique. It's way much simpler to require unique keys as the opposite
situation with multiple values per key  as it is really uncommon and
shows that the upper level data structure needs a rethought.


Cheers,

	Patrik

Re: [PATCH 3/9] hashmap: Call user supplied value free function in insert

[Tomasz Bursztyka]

[-- Attachment #1: Type: text/plain, Size: 1511 bytes --]

Hi Guys,

> On Tue, 2015-02-10 at 13:18 -0600, Denis Kenzior wrote:
>> With the current implementation, the item inserted first is
>> returned.  I don't think enforcement of unique keys is required at the
>> hashmap_insert level.
> As long as there is no function to read out more than one of the values
> from the hashmap, the hashmap should definitely require keys to be
> unique. It's way much simpler to require unique keys as the opposite
> situation with multiple values per key  as it is really uncommon and
> shows that the upper level data structure needs a rethought.

Actually, looking at the implementation in addition of Patrik's comment, 
it just looks as a bug. Nothing else.
What it tries to handle is collisions the classical way, and insert it 
here buggy as it does not check if the key is indeed unique.

The hash and/or bucket place might provoke a collision because of the 
hash function itself, not because the key is the same,
thus why it is possible to link entries to each other.
Thus why remove does check the key against each entries (if there are 
more than one) to retrieve the right one.
There were no point of "handling multiple identical keys" there, or then 
as Patrik said: the API would provide means to play with it.

insert _should_ return false if the key is already present.

So now: either we add a replace, or we let the dev to handle a lookup 
(and necessary remove) before doing any inserts.
But insert has to be fixed.

Br,

Tomasz

Re: [PATCH 3/9] hashmap: Call user supplied value free function in insert

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 1217 bytes --]

Hi Patrik,

On 02/11/2015 03:27 AM, Patrik Flykt wrote:
> On Tue, 2015-02-10 at 13:18 -0600, Denis Kenzior wrote:
>> With the current implementation, the item inserted first is
>> returned.  I don't think enforcement of unique keys is required at the
>> hashmap_insert level.
>
> As long as there is no function to read out more than one of the values
> from the hashmap, the hashmap should definitely require keys to be
> unique. It's way much simpler to require unique keys as the opposite
> situation with multiple values per key  as it is really uncommon and
> shows that the upper level data structure needs a rethought.
>

The point is, you can't just add a 'value destroy' function when we 
already provide l_hashmap_destroy_func_t as an argument.  That is just 
wrong, no ifs or buts about it.  If you want to do that, then you need 
to fix a ton of existing code to handle the new usage model.  Not just 
hack stuff in.

Duplicate key detection is just overhead, if the programmer knows that 
no duplicate keys are possible.  This is about 99% of how we do things. 
  If you need guaranteed enforcement, then just implement 
l_hashmap_replace like I suggested.

Regards,
-Denis

[PATCH 4/9] unit: hashmap: Add value free hash entry test

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 1452 bytes --]

Use the value free function to test that we can replace an
existing value in the hash.
---
 unit/test-hashmap.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/unit/test-hashmap.c b/unit/test-hashmap.c
index a606099..836ed1c 100644
--- a/unit/test-hashmap.c
+++ b/unit/test-hashmap.c
@@ -86,6 +86,14 @@ static void test_ptr(const void *test_data)
 	l_hashmap_destroy(hashmap, NULL);
 }
 
+static void free_value(const struct l_hashmap *hashmap,
+					void *value, void *user_data)
+{
+	assert(hashmap == user_data);
+
+	l_free(value);
+}
+
 static void test_str(const void *test_data)
 {
 	struct l_hashmap *hashmap;
@@ -97,6 +105,8 @@ static void test_str(const void *test_data)
 		"a long key here, bla bla bla bla bla hey! enough?",
 		NULL
 	};
+	const char *duplicate = "hello";
+	unsigned int entries;
 
 	hashmap = l_hashmap_string_new();
 	assert(hashmap);
@@ -154,6 +164,13 @@ static void test_str(const void *test_data)
 		assert(ptr == itr);
 	}
 
+	/* check that value free function works */
+	hashmap = l_hashmap_string_new();
+	assert(l_hashmap_set_value_free_function(hashmap, free_value,
+							hashmap));
+	assert(l_hashmap_insert(hashmap, strings[0], l_strdup(strings[0])));
+	assert(l_hashmap_insert(hashmap, strings[0], l_strdup(strings[0])));
+
 	assert(l_hashmap_lookup(hashmap, "not in hash") == NULL);
 
 	l_hashmap_destroy(hashmap, NULL);
-- 
1.8.3.1

[PATCH 5/9] unit: hashmap: Add replace entry test

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 796 bytes --]

---
 unit/test-hashmap.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/unit/test-hashmap.c b/unit/test-hashmap.c
index 836ed1c..75c249c 100644
--- a/unit/test-hashmap.c
+++ b/unit/test-hashmap.c
@@ -164,6 +164,14 @@ static void test_str(const void *test_data)
 		assert(ptr == itr);
 	}
 
+	/* check we can replace entry with new value */
+	entries = l_hashmap_size(hashmap);
+	assert(l_hashmap_insert(hashmap, strings[0], (char *)strings[0]));
+	assert(l_hashmap_insert(hashmap, duplicate, (char *)duplicate));
+	assert(entries == l_hashmap_size(hashmap));
+
+	l_hashmap_destroy(hashmap, NULL);
+
 	/* check that value free function works */
 	hashmap = l_hashmap_string_new();
 	assert(l_hashmap_set_value_free_function(hashmap, free_value,
-- 
1.8.3.1

[PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 5569 bytes --]

Allow user to remove and add values while inside a callback
from foreach function. This is very much needed as it is
easy to get things wrong here and it helps to avoid complicated
call flows in calling applications.

So foreach logic is changed so that if user tries to remove
an entry from the hash while inside foreach callback, the
entry is not yet removed from hash but marked as removable.
After foreach has finished calling the callback function,
it checks what elements it needs to remove from the hash.

This valgrind report was seen and it relates to this issue.
Here a DBus message was received and its callback function
eventually called l_dbus_unregister() because of application
logic. This then caused the signal_list hash to get corrupted
because the unregister removed an entry from hash while
traversing it.

==28077== Invalid read of size 1
==28077==    at 0x4044A9: l_hashmap_foreach (hashmap.c:606)
==28077==    by 0x4071D9: message_read_handler (dbus.c:244)
==28077==    by 0x410D94: io_callback (io.c:120)
==28077==    by 0x404C42: l_main_run (main.c:346)
==28077==    by 0x401D08: main (test-agent.c:460)
==28077==  Address 0x1c is not stack'd, malloc'd or (recently) free'd
==28077==
==28077==
==28077== Process terminating with default action of signal 11 (SIGSEGV)
==28077==  Access not within mapped region at address 0x1C
==28077==    at 0x4044A9: l_hashmap_foreach (hashmap.c:606)
==28077==    by 0x4071D9: message_read_handler (dbus.c:244)
==28077==    by 0x410D94: io_callback (io.c:120)
==28077==    by 0x404C42: l_main_run (main.c:346)
==28077==    by 0x401D08: main (test-agent.c:460)
==28077==  If you believe this happened as a result of a stack
==28077==  overflow in your program's main thread (unlikely but
==28077==  possible), you can try to increase the size of the
==28077==  main thread stack using the --main-stacksize= flag.
==28077==  The main thread stack size used in this run was 8388608.
---
 ell/hashmap.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 67 insertions(+), 2 deletions(-)

diff --git a/ell/hashmap.c b/ell/hashmap.c
index a204726..6c7c10f 100644
--- a/ell/hashmap.c
+++ b/ell/hashmap.c
@@ -42,6 +42,7 @@ struct entry {
 	void *value;
 	struct entry *next;
 	unsigned int hash;
+	bool removed;
 };
 
 /**
@@ -50,6 +51,8 @@ struct entry {
  * Opague object representing the hash table.
  */
 struct l_hashmap {
+	bool dirty;
+	bool traversing;
 	l_hashmap_hash_func_t hash_func;
 	l_hashmap_compare_func_t compare_func;
 	l_hashmap_key_new_func_t key_new_func;
@@ -431,6 +434,7 @@ LIB_EXPORT bool l_hashmap_insert(struct l_hashmap *hashmap,
 				free_key(hashmap, entry->key);
 				entry->key = key_new;
 			}
+			entry->removed = false;
 
 			if (entry->value != value) {
 				free_value(hashmap, entry->value);
@@ -490,11 +494,20 @@ LIB_EXPORT void *l_hashmap_remove(struct l_hashmap *hashmap, const void *key)
 		if (entry->hash != hash)
 			goto next;
 
+		if (entry->removed)
+			goto next;
+
 		if (hashmap->compare_func(key, entry->key))
 			goto next;
 
 		value = entry->value;
 
+		if (hashmap->traversing) {
+			entry->removed = true;
+			hashmap->dirty = true;
+			goto skip;
+		}
+
 		if (entry == head) {
 			if (entry->next == head) {
 				free_key(hashmap, entry->key);
@@ -517,6 +530,7 @@ LIB_EXPORT void *l_hashmap_remove(struct l_hashmap *hashmap, const void *key)
 			l_free(entry);
 		}
 
+	skip:
 		hashmap->entries--;
 
 		return value;
@@ -553,7 +567,7 @@ LIB_EXPORT void *l_hashmap_lookup(struct l_hashmap *hashmap, const void *key)
 		return NULL;
 
 	for (entry = head;; entry = entry->next) {
-		if (entry->hash == hash &&
+		if (entry->hash == hash && !entry->removed &&
 				!hashmap->compare_func(key, entry->key))
 			return entry->value;
 
@@ -580,6 +594,8 @@ LIB_EXPORT void l_hashmap_foreach(struct l_hashmap *hashmap,
 	if (unlikely(!hashmap || !function))
 		return;
 
+	hashmap->traversing = true;
+
 	for (i = 0; i < NBUCKETS; i++) {
 		struct entry *entry, *head = &hashmap->buckets[i];
 
@@ -587,12 +603,61 @@ LIB_EXPORT void l_hashmap_foreach(struct l_hashmap *hashmap,
 			continue;
 
 		for (entry = head;; entry = entry->next) {
-			function(entry->key, entry->value, user_data);
+			if (!entry->removed)
+				function(entry->key, entry->value, user_data);
 
 			if (entry->next == head)
 				break;
 		}
 	}
+
+	hashmap->traversing = false;
+
+	if (!hashmap->dirty)
+		return;
+
+	/* Remove the entries that were marked removed. */
+	for (i = 0; i < NBUCKETS; i++) {
+		struct entry *entry, *prev, *head = &hashmap->buckets[i];
+
+		if (!head->next)
+			continue;
+
+		for (entry = head, prev = NULL; entry;
+					prev = entry, entry = entry->next) {
+
+			if (!entry->removed)
+				goto next;
+
+			if (entry == head) {
+				if (entry->next == head) {
+					free_key(hashmap, entry->key);
+					head->key = NULL;
+					head->value = NULL;
+					head->hash = 0;
+					head->next = NULL;
+				} else {
+					entry = entry->next;
+					free_key(hashmap, head->key);
+					head->key = entry->key;
+					head->value = entry->value;
+					head->hash = entry->hash;
+					head->next = entry->next;
+					l_free(entry);
+				}
+			} else {
+				prev->next = entry->next;
+				free_key(hashmap, entry->key);
+				l_free(entry);
+			}
+
+		next:
+			if (entry->next == head)
+				break;
+		}
+	}
+
+	hashmap->dirty = false;
 }
 
 /**
-- 
1.8.3.1

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 1440 bytes --]

Hi Jukka,

On 02/10/2015 08:42 AM, Jukka Rissanen wrote:
> Allow user to remove and add values while inside a callback
> from foreach function. This is very much needed as it is
> easy to get things wrong here and it helps to avoid complicated
> call flows in calling applications.
>

Can you tell me why this is needed?  This sounds like abuse of 
hashmap_foreach and an alternate data structure might be in order.

> So foreach logic is changed so that if user tries to remove
> an entry from the hash while inside foreach callback, the
> entry is not yet removed from hash but marked as removable.
> After foreach has finished calling the callback function,
> it checks what elements it needs to remove from the hash.
>

So let me politely say: "No way are we doing this" ;)

> This valgrind report was seen and it relates to this issue.
> Here a DBus message was received and its callback function
> eventually called l_dbus_unregister() because of application
> logic. This then caused the signal_list hash to get corrupted
> because the unregister removed an entry from hash while
> traversing it.
>

So I think I understand why you're doing this...

l_dbus_register and l_dbus_unregister need to actually go away.  They 
are not workable long term.  We need a way smarter data structure to 
handle signal filtering.

Look at libsystemd/sd-bus/bus-match.c for some inspiration.

Regards,
-Denis

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Patrik Flykt]

[-- Attachment #1: Type: text/plain, Size: 1676 bytes --]

On Tue, 2015-02-10 at 13:47 -0600, Denis Kenzior wrote:
> Can you tell me why this is needed?  This sounds like abuse of 
> hashmap_foreach and an alternate data structure might be in order.

One should not be able to crash the library by (mis)using the provided
API. The implementation needs to work all the time or politely tell that
the API function call did not complete at this time.

> > So foreach logic is changed so that if user tries to remove
> > an entry from the hash while inside foreach callback, the
> > entry is not yet removed from hash but marked as removable.
> > After foreach has finished calling the callback function,
> > it checks what elements it needs to remove from the hash.
> >
> 
> So let me politely say: "No way are we doing this" ;)

Then the only alternative is to return false for any functionality that
otherwise causes the implementation to crash. For example when
inserting/removing items from the hash while an foreach is ongoing.

glib also crashed with this pattern. Or usually worked ok, as the
removed/added item wasn't always the item used in foreach or the next
item. Fixing this to allow any API call successfully work at any time
requires quite some more work to be done, the above patch by Jukka was
approximately the minimum needed for a remove to work at any one time. 

With that the insert part is still left, but it might be easier if the
one and only foreach iterator next element is remembered by the hash
data structure and the insert/remove operation move the next position
when needed. In addition, also the foreach operation needs to guard
against itself...


Cheers,

	Patrik

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 2391 bytes --]

Hi Patrik,

On 02/11/2015 03:21 AM, Patrik Flykt wrote:
> On Tue, 2015-02-10 at 13:47 -0600, Denis Kenzior wrote:
>> Can you tell me why this is needed?  This sounds like abuse of
>> hashmap_foreach and an alternate data structure might be in order.
>
> One should not be able to crash the library by (mis)using the provided
> API. The implementation needs to work all the time or politely tell that
> the API function call did not complete at this time.
>

Are you serious?  I've yet to see any library that I can't crash by 
deliberately misusing the API; even the best can't do what you're 
describing.  Ell's job is not to hand-hold the programmer.

>>> So foreach logic is changed so that if user tries to remove
>>> an entry from the hash while inside foreach callback, the
>>> entry is not yet removed from hash but marked as removable.
>>> After foreach has finished calling the callback function,
>>> it checks what elements it needs to remove from the hash.
>>>
>>
>> So let me politely say: "No way are we doing this" ;)
>
> Then the only alternative is to return false for any functionality that
> otherwise causes the implementation to crash. For example when
> inserting/removing items from the hash while an foreach is ongoing.

No, the alternative is to crash.  Crashing is pretty much the best way 
to tell the programmer he's doing something stupid.

>
> glib also crashed with this pattern. Or usually worked ok, as the
> removed/added item wasn't always the item used in foreach or the next
> item. Fixing this to allow any API call successfully work at any time
> requires quite some more work to be done, the above patch by Jukka was
> approximately the minimum needed for a remove to work at any one time.
>

If you find a good way to fix this in the data structure, great.  But 
the current fix is not acceptable.  We will not be iterating over the 
_entire_ data structure twice.  The foreach operation is already 
expensive and too tempting to abuse.

> With that the insert part is still left, but it might be easier if the
> one and only foreach iterator next element is remembered by the hash
> data structure and the insert/remove operation move the next position
> when needed. In addition, also the foreach operation needs to guard
> against itself...

I look forward to your patch :)

Regards,
-Denis

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 1229 bytes --]

On ke, 2015-02-11 at 08:06 -0600, Denis Kenzior wrote:
> Hi Patrik,
> 
> On 02/11/2015 03:21 AM, Patrik Flykt wrote:
> > On Tue, 2015-02-10 at 13:47 -0600, Denis Kenzior wrote:
> >> Can you tell me why this is needed?  This sounds like abuse of
> >> hashmap_foreach and an alternate data structure might be in order.
> >
> > One should not be able to crash the library by (mis)using the provided
> > API. The implementation needs to work all the time or politely tell that
> > the API function call did not complete at this time.
> >
> 
> Are you serious?  I've yet to see any library that I can't crash by 
> deliberately misusing the API; even the best can't do what you're 
> describing.  Ell's job is not to hand-hold the programmer.

I disagree you here. It is quite difficult to know how ell is being used
so it should be prepared to not to crash. For example here it is not
very obvious from the library user point of view that calling
l_dbus_unregister() from dbus callback will cause a segfault. It is
clearly a bug that needs to be fixed. I do not understand why we would
leave this kind of bug in the code and then let the library user to
invent some workarounds for this issue.


Jukka

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 1986 bytes --]

Hi Jukka,

On 02/12/2015 01:23 AM, Jukka Rissanen wrote:
> On ke, 2015-02-11 at 08:06 -0600, Denis Kenzior wrote:
>> Hi Patrik,
>>
>> On 02/11/2015 03:21 AM, Patrik Flykt wrote:
>>> On Tue, 2015-02-10 at 13:47 -0600, Denis Kenzior wrote:
>>>> Can you tell me why this is needed?  This sounds like abuse of
>>>> hashmap_foreach and an alternate data structure might be in order.
>>>
>>> One should not be able to crash the library by (mis)using the provided
>>> API. The implementation needs to work all the time or politely tell that
>>> the API function call did not complete at this time.
>>>
>>
>> Are you serious?  I've yet to see any library that I can't crash by
>> deliberately misusing the API; even the best can't do what you're
>> describing.  Ell's job is not to hand-hold the programmer.
>
> I disagree you here. It is quite difficult to know how ell is being used
> so it should be prepared to not to crash. For example here it is not
> very obvious from the library user point of view that calling
> l_dbus_unregister() from dbus callback will cause a segfault. It is
> clearly a bug that needs to be fixed. I do not understand why we would
> leave this kind of bug in the code and then let the library user to
> invent some workarounds for this issue.
>

Except you're not fixing l_dbus_unregister.  You're fixing l_hashmap, 
which does not need to be 'fixed'.

l_dbus_register used a hashmap for whatever reason.  The reason might 
have been to have a fast O(1) unregister implementation.  But then it 
was not meant to handle re-entrancy in the way you're trying to 
implement it.

I already pointed out to you the long term fix.  We should get rid of 
l_dbus_register completely and add proper signal watch functions with a 
multi-level/tree data structure for fast signal matching.

A stop-gap solution based on gdbus signal watch implementation is also 
acceptable.  But it is only a stop-gap solution.

Regards,
-Denis

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 890 bytes --]

On ke, 2015-02-11 at 08:06 -0600, Denis Kenzior wrote:
> Hi Patrik,
> 

> >
> > glib also crashed with this pattern. Or usually worked ok, as the
> > removed/added item wasn't always the item used in foreach or the next
> > item. Fixing this to allow any API call successfully work at any time
> > requires quite some more work to be done, the above patch by Jukka was
> > approximately the minimum needed for a remove to work at any one time.
> >
> 
> If you find a good way to fix this in the data structure, great.  But 
> the current fix is not acceptable.  We will not be iterating over the 
> _entire_ data structure twice.  The foreach operation is already 
> expensive and too tempting to abuse.

The patch would iterate the data structure twice only if user did modify
the hash in the callback func. That is probably not very common case
anyway.


Jukka

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 1498 bytes --]

Hi Jukka,

On 02/12/2015 01:25 AM, Jukka Rissanen wrote:
> On ke, 2015-02-11 at 08:06 -0600, Denis Kenzior wrote:
>> Hi Patrik,
>>
>
>>>
>>> glib also crashed with this pattern. Or usually worked ok, as the
>>> removed/added item wasn't always the item used in foreach or the next
>>> item. Fixing this to allow any API call successfully work at any time
>>> requires quite some more work to be done, the above patch by Jukka was
>>> approximately the minimum needed for a remove to work at any one time.
>>>
>>
>> If you find a good way to fix this in the data structure, great.  But
>> the current fix is not acceptable.  We will not be iterating over the
>> _entire_ data structure twice.  The foreach operation is already
>> expensive and too tempting to abuse.
>
> The patch would iterate the data structure twice only if user did modify
> the hash in the callback func. That is probably not very common case
> anyway.
>

Does not matter. An operation that you expect to take O(n) suddenly 
becomes O(2n).  That's just not acceptable.  Remember, we're running on 
low-power devices, so our data structures will be optimized for speed. 
Programmer convenience is a secondary concern.

Anyway, I pushed a documentation clarification to ell/hashmap.c 
explaining that the hashmap must be invariant during an ongoing 
l_hashmap_foreach operation.

So you need to find an alternate approach.  Think through your data 
structures carefully.

Regards,
-Denis

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Luiz Augusto von Dentz]

[-- Attachment #1: Type: text/plain, Size: 2486 bytes --]

Hi Denis, Jukka,

On Thu, Feb 12, 2015 at 7:55 PM, Denis Kenzior <denkenz@gmail.com> wrote:
> Hi Jukka,
>
> On 02/12/2015 01:25 AM, Jukka Rissanen wrote:
>>
>> On ke, 2015-02-11 at 08:06 -0600, Denis Kenzior wrote:
>>>
>>> Hi Patrik,
>>>
>>
>>>>
>>>> glib also crashed with this pattern. Or usually worked ok, as the
>>>> removed/added item wasn't always the item used in foreach or the next
>>>> item. Fixing this to allow any API call successfully work at any time
>>>> requires quite some more work to be done, the above patch by Jukka was
>>>> approximately the minimum needed for a remove to work at any one time.
>>>>
>>>
>>> If you find a good way to fix this in the data structure, great.  But
>>> the current fix is not acceptable.  We will not be iterating over the
>>> _entire_ data structure twice.  The foreach operation is already
>>> expensive and too tempting to abuse.
>>
>>
>> The patch would iterate the data structure twice only if user did modify
>> the hash in the callback func. That is probably not very common case
>> anyway.
>>
>
> Does not matter. An operation that you expect to take O(n) suddenly becomes
> O(2n).  That's just not acceptable.  Remember, we're running on low-power
> devices, so our data structures will be optimized for speed. Programmer
> convenience is a secondary concern.
>
> Anyway, I pushed a documentation clarification to ell/hashmap.c explaining
> that the hashmap must be invariant during an ongoing l_hashmap_foreach
> operation.
>
> So you need to find an alternate approach.  Think through your data
> structures carefully.

Ive solved a similar problem with queues in BlueZ, it is very similar
to ell queues, the code looks like this now:

http://fpaste.org/185237/14238402/

So it basically protects the entries by taking a reference before
calling the callback, and also the queue itself before starting
iterating, and it just need a single loop. While it can still be
vulnerable to bad usage I still think it worth doing because this case
of callback removing the entry itself it very common, there is
actually 3 cases that we want to allow queue_remove(entry),
queue_remove_all and queue_unref by the callback so we added unit
tests to emulate these 3 scenarios.

> Regards,
> -Denis
>
>
> _______________________________________________
> ell mailing list
> ell(a)lists.01.org
> https://lists.01.org/mailman/listinfo/ell



-- 
Luiz Augusto von Dentz

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 613 bytes --]

Hi Luiz,

 >> So you need to find an alternate approach.  Think through your data
>> structures carefully.
>
> Ive solved a similar problem with queues in BlueZ, it is very similar
> to ell queues, the code looks like this now:
>
> http://fpaste.org/185237/14238402/

We're not going to increase memory consumption by 25% just to support a 
few corner cases involving re-entrancy.  Even STL containers don't 
support the usage models you guys want to support.

So I repeat this again, leave queues and hashmaps alone.  Handle 
re-entrancy separately.

Lets move on please ;)

Regards,
-Denis

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Marcel Holtmann]

[-- Attachment #1: Type: text/plain, Size: 3171 bytes --]

Hi Luiz,

>>>>> glib also crashed with this pattern. Or usually worked ok, as the
>>>>> removed/added item wasn't always the item used in foreach or the next
>>>>> item. Fixing this to allow any API call successfully work at any time
>>>>> requires quite some more work to be done, the above patch by Jukka was
>>>>> approximately the minimum needed for a remove to work at any one time.
>>>>> 
>>>> 
>>>> If you find a good way to fix this in the data structure, great.  But
>>>> the current fix is not acceptable.  We will not be iterating over the
>>>> _entire_ data structure twice.  The foreach operation is already
>>>> expensive and too tempting to abuse.
>>> 
>>> 
>>> The patch would iterate the data structure twice only if user did modify
>>> the hash in the callback func. That is probably not very common case
>>> anyway.
>>> 
>> 
>> Does not matter. An operation that you expect to take O(n) suddenly becomes
>> O(2n).  That's just not acceptable.  Remember, we're running on low-power
>> devices, so our data structures will be optimized for speed. Programmer
>> convenience is a secondary concern.
>> 
>> Anyway, I pushed a documentation clarification to ell/hashmap.c explaining
>> that the hashmap must be invariant during an ongoing l_hashmap_foreach
>> operation.
>> 
>> So you need to find an alternate approach.  Think through your data
>> structures carefully.
> 
> Ive solved a similar problem with queues in BlueZ, it is very similar
> to ell queues, the code looks like this now:
> 
> http://fpaste.org/185237/14238402/
> 
> So it basically protects the entries by taking a reference before
> calling the callback, and also the queue itself before starting
> iterating, and it just need a single loop. While it can still be
> vulnerable to bad usage I still think it worth doing because this case
> of callback removing the entry itself it very common, there is
> actually 3 cases that we want to allow queue_remove(entry),
> queue_remove_all and queue_unref by the callback so we added unit
> tests to emulate these 3 scenarios.

and this is most likely code that we have to take out again. And revert all users to handle this by themselves. It is not in line with the goals of ELL. And I did warn about that. The reference counting for each entry is pretty wasteful from a memory point of view. Especially if we are running on a system where every single byte of memory usage counts.

The goal for BlueZ is to eventually be able to run on top of ELL. This means that we have to be really cautious about what we provide and how. ELL is not just another GLib. It is not a dumping ground. We are looking at really memory restraint systems. There is a high chance that we have to make ELL even modular and provide an option to compile it without certain modules like D-Bus or netlink.

I am just mentioning this here so that everybody understands what our goals here. We might be utilizing systems where the userspace is small and really limited. What ELL needs to do is provide common functionality for its users, but it does not have to solve world hunger for its users.

Regards

Marcel

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Luiz Augusto von Dentz]

[-- Attachment #1: Type: text/plain, Size: 3727 bytes --]

Hi Marcel, Denis,

On Fri, Feb 13, 2015 at 7:36 PM, Marcel Holtmann <marcel@holtmann.org> wrote:
> Hi Luiz,
>
>>>>>> glib also crashed with this pattern. Or usually worked ok, as the
>>>>>> removed/added item wasn't always the item used in foreach or the next
>>>>>> item. Fixing this to allow any API call successfully work at any time
>>>>>> requires quite some more work to be done, the above patch by Jukka was
>>>>>> approximately the minimum needed for a remove to work at any one time.
>>>>>>
>>>>>
>>>>> If you find a good way to fix this in the data structure, great.  But
>>>>> the current fix is not acceptable.  We will not be iterating over the
>>>>> _entire_ data structure twice.  The foreach operation is already
>>>>> expensive and too tempting to abuse.
>>>>
>>>>
>>>> The patch would iterate the data structure twice only if user did modify
>>>> the hash in the callback func. That is probably not very common case
>>>> anyway.
>>>>
>>>
>>> Does not matter. An operation that you expect to take O(n) suddenly becomes
>>> O(2n).  That's just not acceptable.  Remember, we're running on low-power
>>> devices, so our data structures will be optimized for speed. Programmer
>>> convenience is a secondary concern.
>>>
>>> Anyway, I pushed a documentation clarification to ell/hashmap.c explaining
>>> that the hashmap must be invariant during an ongoing l_hashmap_foreach
>>> operation.
>>>
>>> So you need to find an alternate approach.  Think through your data
>>> structures carefully.
>>
>> Ive solved a similar problem with queues in BlueZ, it is very similar
>> to ell queues, the code looks like this now:
>>
>> http://fpaste.org/185237/14238402/
>>
>> So it basically protects the entries by taking a reference before
>> calling the callback, and also the queue itself before starting
>> iterating, and it just need a single loop. While it can still be
>> vulnerable to bad usage I still think it worth doing because this case
>> of callback removing the entry itself it very common, there is
>> actually 3 cases that we want to allow queue_remove(entry),
>> queue_remove_all and queue_unref by the callback so we added unit
>> tests to emulate these 3 scenarios.
>
> and this is most likely code that we have to take out again. And revert all users to handle this by themselves. It is not in line with the goals of ELL. And I did warn about that. The reference counting for each entry is pretty wasteful from a memory point of view. Especially if we are running on a system where every single byte of memory usage counts.
>
> The goal for BlueZ is to eventually be able to run on top of ELL. This means that we have to be really cautious about what we provide and how. ELL is not just another GLib. It is not a dumping ground. We are looking at really memory restraint systems. There is a high chance that we have to make ELL even modular and provide an option to compile it without certain modules like D-Bus or netlink.
>
> I am just mentioning this here so that everybody understands what our goals here. We might be utilizing systems where the userspace is small and really limited. What ELL needs to do is provide common functionality for its users, but it does not have to solve world hunger for its users.

Sorry but I cannot understand this motive, the reference counting will
happen anyway since it is most common way to protect against callbacks
destroying the very entry, if you don't do in ell the user code will
do it and memory will be consumed whether you like it or not. So you
talk about memory restraint system but your solution may actually
cause more memory to be consumed, outside of ell.

-- 
Luiz Augusto von Dentz

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Marcel Holtmann]

[-- Attachment #1: Type: text/plain, Size: 4707 bytes --]

Hi Luiz,

>>>>>>> glib also crashed with this pattern. Or usually worked ok, as the
>>>>>>> removed/added item wasn't always the item used in foreach or the next
>>>>>>> item. Fixing this to allow any API call successfully work at any time
>>>>>>> requires quite some more work to be done, the above patch by Jukka was
>>>>>>> approximately the minimum needed for a remove to work at any one time.
>>>>>>> 
>>>>>> 
>>>>>> If you find a good way to fix this in the data structure, great.  But
>>>>>> the current fix is not acceptable.  We will not be iterating over the
>>>>>> _entire_ data structure twice.  The foreach operation is already
>>>>>> expensive and too tempting to abuse.
>>>>> 
>>>>> 
>>>>> The patch would iterate the data structure twice only if user did modify
>>>>> the hash in the callback func. That is probably not very common case
>>>>> anyway.
>>>>> 
>>>> 
>>>> Does not matter. An operation that you expect to take O(n) suddenly becomes
>>>> O(2n).  That's just not acceptable.  Remember, we're running on low-power
>>>> devices, so our data structures will be optimized for speed. Programmer
>>>> convenience is a secondary concern.
>>>> 
>>>> Anyway, I pushed a documentation clarification to ell/hashmap.c explaining
>>>> that the hashmap must be invariant during an ongoing l_hashmap_foreach
>>>> operation.
>>>> 
>>>> So you need to find an alternate approach.  Think through your data
>>>> structures carefully.
>>> 
>>> Ive solved a similar problem with queues in BlueZ, it is very similar
>>> to ell queues, the code looks like this now:
>>> 
>>> http://fpaste.org/185237/14238402/
>>> 
>>> So it basically protects the entries by taking a reference before
>>> calling the callback, and also the queue itself before starting
>>> iterating, and it just need a single loop. While it can still be
>>> vulnerable to bad usage I still think it worth doing because this case
>>> of callback removing the entry itself it very common, there is
>>> actually 3 cases that we want to allow queue_remove(entry),
>>> queue_remove_all and queue_unref by the callback so we added unit
>>> tests to emulate these 3 scenarios.
>> 
>> and this is most likely code that we have to take out again. And revert all users to handle this by themselves. It is not in line with the goals of ELL. And I did warn about that. The reference counting for each entry is pretty wasteful from a memory point of view. Especially if we are running on a system where every single byte of memory usage counts.
>> 
>> The goal for BlueZ is to eventually be able to run on top of ELL. This means that we have to be really cautious about what we provide and how. ELL is not just another GLib. It is not a dumping ground. We are looking at really memory restraint systems. There is a high chance that we have to make ELL even modular and provide an option to compile it without certain modules like D-Bus or netlink.
>> 
>> I am just mentioning this here so that everybody understands what our goals here. We might be utilizing systems where the userspace is small and really limited. What ELL needs to do is provide common functionality for its users, but it does not have to solve world hunger for its users.
> 
> Sorry but I cannot understand this motive, the reference counting will
> happen anyway since it is most common way to protect against callbacks
> destroying the very entry, if you don't do in ell the user code will
> do it and memory will be consumed whether you like it or not. So you
> talk about memory restraint system but your solution may actually
> cause more memory to be consumed, outside of ell.

so adding an int ref_count to each queue entry is adding substantive overhead for every single user. Meaning that every single queue entry we have to store has an extra sizeof(int) allocated.

Compare this with a single sizeof(bool) for something like in_notify as we used in some of our code. So the more elements you store in the queue, the more data you are using. And on top of that it is more data for every single user. No matter if it requires the queue to re-entrancy safe or not.

You might have realized that our queue entry struct has on purpose only a next pointer. We decided really early that we want the queue to be a single list. And we accepted that because of that corner-case operations will be highly expensive. This means that while queues are useful for a lot of cases, they will not be useful for all.

We really do not want the massive bloat GLib repeated. The user of the ELL data structures has to know what they are doing. The queue data structure is not one fits all use case.

Regards

Marcel

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Luiz Augusto von Dentz]

[-- Attachment #1: Type: text/plain, Size: 5659 bytes --]

Hi Marcel,

On Mon, Feb 16, 2015 at 6:18 PM, Marcel Holtmann <marcel@holtmann.org> wrote:
> Hi Luiz,
>
>>>>>>>> glib also crashed with this pattern. Or usually worked ok, as the
>>>>>>>> removed/added item wasn't always the item used in foreach or the next
>>>>>>>> item. Fixing this to allow any API call successfully work at any time
>>>>>>>> requires quite some more work to be done, the above patch by Jukka was
>>>>>>>> approximately the minimum needed for a remove to work at any one time.
>>>>>>>>
>>>>>>>
>>>>>>> If you find a good way to fix this in the data structure, great.  But
>>>>>>> the current fix is not acceptable.  We will not be iterating over the
>>>>>>> _entire_ data structure twice.  The foreach operation is already
>>>>>>> expensive and too tempting to abuse.
>>>>>>
>>>>>>
>>>>>> The patch would iterate the data structure twice only if user did modify
>>>>>> the hash in the callback func. That is probably not very common case
>>>>>> anyway.
>>>>>>
>>>>>
>>>>> Does not matter. An operation that you expect to take O(n) suddenly becomes
>>>>> O(2n).  That's just not acceptable.  Remember, we're running on low-power
>>>>> devices, so our data structures will be optimized for speed. Programmer
>>>>> convenience is a secondary concern.
>>>>>
>>>>> Anyway, I pushed a documentation clarification to ell/hashmap.c explaining
>>>>> that the hashmap must be invariant during an ongoing l_hashmap_foreach
>>>>> operation.
>>>>>
>>>>> So you need to find an alternate approach.  Think through your data
>>>>> structures carefully.
>>>>
>>>> Ive solved a similar problem with queues in BlueZ, it is very similar
>>>> to ell queues, the code looks like this now:
>>>>
>>>> http://fpaste.org/185237/14238402/
>>>>
>>>> So it basically protects the entries by taking a reference before
>>>> calling the callback, and also the queue itself before starting
>>>> iterating, and it just need a single loop. While it can still be
>>>> vulnerable to bad usage I still think it worth doing because this case
>>>> of callback removing the entry itself it very common, there is
>>>> actually 3 cases that we want to allow queue_remove(entry),
>>>> queue_remove_all and queue_unref by the callback so we added unit
>>>> tests to emulate these 3 scenarios.
>>>
>>> and this is most likely code that we have to take out again. And revert all users to handle this by themselves. It is not in line with the goals of ELL. And I did warn about that. The reference counting for each entry is pretty wasteful from a memory point of view. Especially if we are running on a system where every single byte of memory usage counts.
>>>
>>> The goal for BlueZ is to eventually be able to run on top of ELL. This means that we have to be really cautious about what we provide and how. ELL is not just another GLib. It is not a dumping ground. We are looking at really memory restraint systems. There is a high chance that we have to make ELL even modular and provide an option to compile it without certain modules like D-Bus or netlink.
>>>
>>> I am just mentioning this here so that everybody understands what our goals here. We might be utilizing systems where the userspace is small and really limited. What ELL needs to do is provide common functionality for its users, but it does not have to solve world hunger for its users.
>>
>> Sorry but I cannot understand this motive, the reference counting will
>> happen anyway since it is most common way to protect against callbacks
>> destroying the very entry, if you don't do in ell the user code will
>> do it and memory will be consumed whether you like it or not. So you
>> talk about memory restraint system but your solution may actually
>> cause more memory to be consumed, outside of ell.
>
> so adding an int ref_count to each queue entry is adding substantive overhead for every single user. Meaning that every single queue entry we have to store has an extra sizeof(int) allocated.

That if we use an int, we could use uint8_t which is equivalent to
bool, the reference is just for internal use anyway it does not get
more than 2 ever.

> Compare this with a single sizeof(bool) for something like in_notify as we used in some of our code. So the more elements you store in the queue, the more data you are using. And on top of that it is more data for every single user. No matter if it requires the queue to re-entrancy safe or not.

Not quite, actually there was 4 flags to track this properly in the
mgmt code, see for yourself:
https://git.kernel.org/cgit/bluetooth/bluez.git/commit/?id=b72dee02b2e5dec9fbcf6ce97848fb08363a035d

> You might have realized that our queue entry struct has on purpose only a next pointer. We decided really early that we want the queue to be a single list. And we accepted that because of that corner-case operations will be highly expensive. This means that while queues are useful for a lot of cases, they will not be useful for all.
>
> We really do not want the massive bloat GLib repeated. The user of the ELL data structures has to know what they are doing. The queue data structure is not one fits all use case.

Im not even considering GLib as a good example, it actually surfer
from the very same problem, as you can see there are a lot of corner
cases and we end up with O(2n) situation Denis was complaining about
Jukka's changes, anyway all this code seems to be inspired in at_chat
from oFono which has the very same O(2n) pattern, so perhaps we need a
specialized notification list? One that doesn't bloat the caller at
very least.


-- 
Luiz Augusto von Dentz

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Marcel Holtmann]

[-- Attachment #1: Type: text/plain, Size: 6965 bytes --]

Hi Luiz,

>>>>>>>>> glib also crashed with this pattern. Or usually worked ok, as the
>>>>>>>>> removed/added item wasn't always the item used in foreach or the next
>>>>>>>>> item. Fixing this to allow any API call successfully work at any time
>>>>>>>>> requires quite some more work to be done, the above patch by Jukka was
>>>>>>>>> approximately the minimum needed for a remove to work at any one time.
>>>>>>>>> 
>>>>>>>> 
>>>>>>>> If you find a good way to fix this in the data structure, great. But
>>>>>>>> the current fix is not acceptable.  We will not be iterating over the
>>>>>>>> _entire_ data structure twice.  The foreach operation is already
>>>>>>>> expensive and too tempting to abuse.
>>>>>>> 
>>>>>>> 
>>>>>>> The patch would iterate the data structure twice only if user did modify
>>>>>>> the hash in the callback func. That is probably not very common case
>>>>>>> anyway.
>>>>>>> 
>>>>>> 
>>>>>> Does not matter. An operation that you expect to take O(n) suddenly becomes
>>>>>> O(2n).  That's just not acceptable.  Remember, we're running on low-power
>>>>>> devices, so our data structures will be optimized for speed. Programmer
>>>>>> convenience is a secondary concern.
>>>>>> 
>>>>>> Anyway, I pushed a documentation clarification to ell/hashmap.c explaining
>>>>>> that the hashmap must be invariant during an ongoing l_hashmap_foreach
>>>>>> operation.
>>>>>> 
>>>>>> So you need to find an alternate approach.  Think through your data
>>>>>> structures carefully.
>>>>> 
>>>>> Ive solved a similar problem with queues in BlueZ, it is very similar
>>>>> to ell queues, the code looks like this now:
>>>>> 
>>>>> http://fpaste.org/185237/14238402/
>>>>> 
>>>>> So it basically protects the entries by taking a reference before
>>>>> calling the callback, and also the queue itself before starting
>>>>> iterating, and it just need a single loop. While it can still be
>>>>> vulnerable to bad usage I still think it worth doing because this case
>>>>> of callback removing the entry itself it very common, there is
>>>>> actually 3 cases that we want to allow queue_remove(entry),
>>>>> queue_remove_all and queue_unref by the callback so we added unit
>>>>> tests to emulate these 3 scenarios.
>>>> 
>>>> and this is most likely code that we have to take out again. And revert all users to handle this by themselves. It is not in line with the goals of ELL. And I did warn about that. The reference counting for each entry is pretty wasteful from a memory point of view. Especially if we are running on a system where every single byte of memory usage counts.
>>>> 
>>>> The goal for BlueZ is to eventually be able to run on top of ELL. This means that we have to be really cautious about what we provide and how. ELL is not just another GLib. It is not a dumping ground. We are looking at really memory restraint systems. There is a high chance that we have to make ELL even modular and provide an option to compile it without certain modules like D-Bus or netlink.
>>>> 
>>>> I am just mentioning this here so that everybody understands what our goals here. We might be utilizing systems where the userspace is small and really limited. What ELL needs to do is provide common functionality for its users, but it does not have to solve world hunger for its users.
>>> 
>>> Sorry but I cannot understand this motive, the reference counting will
>>> happen anyway since it is most common way to protect against callbacks
>>> destroying the very entry, if you don't do in ell the user code will
>>> do it and memory will be consumed whether you like it or not. So you
>>> talk about memory restraint system but your solution may actually
>>> cause more memory to be consumed, outside of ell.
>> 
>> so adding an int ref_count to each queue entry is adding substantive overhead for every single user. Meaning that every single queue entry we have to store has an extra sizeof(int) allocated.
> 
> That if we use an int, we could use uint8_t which is equivalent to
> bool, the reference is just for internal use anyway it does not get
> more than 2 ever.
> 
>> Compare this with a single sizeof(bool) for something like in_notify as we used in some of our code. So the more elements you store in the queue, the more data you are using. And on top of that it is more data for every single user. No matter if it requires the queue to re-entrancy safe or not.
> 
> Not quite, actually there was 4 flags to track this properly in the
> mgmt code, see for yourself:
> https://git.kernel.org/cgit/bluetooth/bluez.git/commit/?id=b72dee02b2e5dec9fbcf6ce97848fb08363a035d

you are not comparing the right pieces here.

One is the struct queue and the other struct queue_entry. If you add anything to struct queue_entry you are punishing every single data block. It is not a one-time penalty. It is for every user. So if some user wants to store 100 entries in the queue, then they get 100 * sizeof(int) extra overhead.

And as I explained for that exact reason, the queue_entry is single linked list. This means that queue_pop_tail is not a favorable operation and we do not support it. When we started ELL and discussed these details, I ended up going through GLib users and see how much this operation would be needed and what it is used for. The result was we do not want that.

I prefer having 4 constant flags in the queue user compared to punishing every single queue entry with any extra overhead.

>> You might have realized that our queue entry struct has on purpose only a next pointer. We decided really early that we want the queue to be a single list. And we accepted that because of that corner-case operations will be highly expensive. This means that while queues are useful for a lot of cases, they will not be useful for all.
>> 
>> We really do not want the massive bloat GLib repeated. The user of the ELL data structures has to know what they are doing. The queue data structure is not one fits all use case.
> 
> Im not even considering GLib as a good example, it actually surfer
> from the very same problem, as you can see there are a lot of corner
> cases and we end up with O(2n) situation Denis was complaining about
> Jukka's changes, anyway all this code seems to be inspired in at_chat
> from oFono which has the very same O(2n) pattern, so perhaps we need a
> specialized notification list? One that doesn't bloat the caller at
> very least.

There will be cases where a dedicated data structure just makes more sense and is more efficient. That is totally acceptable and encouraged.

This essentially goes back to the original argument that Denis made. ELL is not something that can solve all your problems. If the caller/user of the data structures is behaving stupid, then the only thing ELL can do is abort. Which is a behavior we want since then we can collect traces of the faulty behavior.

Regards

Marcel

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Tomasz Bursztyka]

[-- Attachment #1: Type: text/plain, Size: 1827 bytes --]

Hi Marcel and Denis,

> I am just mentioning this here so that everybody understands what our goals here. We might be utilizing systems where the userspace is small and really limited. What ELL needs to do is provide common functionality for its users, but it does not have to solve world hunger for its users.

It's nice to get such goal clarifications, the earlier the better 
though: it was not as clear as that when we started.

That said, there are misleading signals about these. I'll be annoying 
about hashmap, last time:

If memory is at stake, why promoting a bit of performance via storing 
the hash per-entry in the hashmap?
Why also enabling the storage of the same key multiple times?
(though that should not be an issue if the code is made without bug, but 
anyway the library should help just a bit when it's not too costly.)

Why also copying the key in the hashmap, when this could be wisely 
shared with the structure it points to?
I am thinking about the network's object path. We rebuilt the object 
path dynamically, when we could be using just the same pointer.
It would only require to be careful not to destroy a network structure, 
before removing its entry in the hash.
(here it's a win/win on memory/performance)


On list - or queues - what are the arguments about using dynamically 
allocated ones vs the linux "list.h" way for instance?
Isn't the later one a bit better from memory point of view if it would 
be single linked one (as it is not if I remember well)?
(though the syntax is odd I agree, taste issue issue here so it's 
subjective).


And about the non-dbus, non-netlink ways, this would require a complete 
rewrite of the targeted projects since these are
not architectured at all for that. That's also quite new as a goal.


Cheers,

Tomasz

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 2562 bytes --]

Hi Tomasz,

 >
> It's nice to get such goal clarifications, the earlier the better
> though: it was not as clear as that when we started.

Seriously? Remember, 'Embedded Linux Library'.  I think the focus is 
pretty clear ;)

>
> If memory is at stake, why promoting a bit of performance via storing
> the hash per-entry in the hashmap?

Because you do want to re-compute the hash, that is expensive. 
Especially since the hash can be supplied by the user and could be 
arbitrarily expensive computationally.

> Why also enabling the storage of the same key multiple times?
> (though that should not be an issue if the code is made without bug, but
> anyway the library should help just a bit when it's not too costly.)

ELL has been designed with existing usage in mind.  We looked at what 
BlueZ, oFono, ConnMan, neard, etc are doing and designed the API around 
that.  The goal is to make an API that would be fairly close to what 
we're already doing today.  This would make our future porting efforts 
easier.

You will find that most of our code uses lookup then insert with no 
possibility of duplicates.  So as I pointed out earlier, I don't see a 
need to detect duplicates at the cost of traversing the collision queue. 
  Simply put, if it ain't broke, don't fix it.

>
> Why also copying the key in the hashmap, when this could be wisely
> shared with the structure it points to?
> I am thinking about the network's object path. We rebuilt the object
> path dynamically, when we could be using just the same pointer.
> It would only require to be careful not to destroy a network structure,
> before removing its entry in the hash.
> (here it's a win/win on memory/performance)

Which hash are you talking about? And we have a path and an id that we 
generate.  You might be able to optimize one, but not the other.

Anyway, can be done and might even be a good idea.  But how is this 
relevant to the discussion about re-entrancy?

>
>
> On list - or queues - what are the arguments about using dynamically
> allocated ones vs the linux "list.h" way for instance?
> Isn't the later one a bit better from memory point of view if it would
> be single linked one (as it is not if I remember well)?
> (though the syntax is odd I agree, taste issue issue here so it's
> subjective).
>

We looked into that and decided against it.  Yes it is a bit more 
efficient storage wise if used right, but the syntax is painful.  It is 
also not really what we're used to (see above).

Regards,
-Denis

Re: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function

[Tomasz Bursztyka]

[-- Attachment #1: Type: text/plain, Size: 3824 bytes --]

Hi Denis,

>> It's nice to get such goal clarifications, the earlier the better
>> though: it was not as clear as that when we started.
>
> Seriously? Remember, 'Embedded Linux Library'.  I think the focus is 
> pretty clear ;)

Sure, but I understood something differently (which I might got wrong), 
let's discuss that privately.

>>
>> If memory is at stake, why promoting a bit of performance via storing
>> the hash per-entry in the hashmap?
>
> Because you do want to re-compute the hash, that is expensive. 
> Especially since the hash can be supplied by the user and could be 
> arbitrarily expensive computationally.

Yes thus the performance gain for lookups (when it loops on the linked 
list in the bucket site: only the similar hash will lead to compare the 
key).
Will there be that many bucket index collision so linked list will be long?
(The only real use case I see could be the dbus object tree in ell, if 
there are many objects)
Though this goes a bit against the memory target ;)

>> Why also enabling the storage of the same key multiple times?
>> (though that should not be an issue if the code is made without bug, but
>> anyway the library should help just a bit when it's not too costly.)
>
> ELL has been designed with existing usage in mind.  We looked at what 
> BlueZ, oFono, ConnMan, neard, etc are doing and designed the API 
> around that.  The goal is to make an API that would be fairly close to 
> what we're already doing today.  This would make our future porting 
> efforts easier.
>
> You will find that most of our code uses lookup then insert with no 
> possibility of duplicates.  So as I pointed out earlier, I don't see a 
> need to detect duplicates at the cost of traversing the collision 
> queue.  Simply put, if it ain't broke, don't fix it.

I still think the library should be robust and doing only 1 thing very 
well without ambiguity. So this needs to be properly documented then.
Because, even if we were using glib properly (lookup first then insert), 
we are changing the behavior of insert in ell here.

>>
>> Why also copying the key in the hashmap, when this could be wisely
>> shared with the structure it points to?
>> I am thinking about the network's object path. We rebuilt the object
>> path dynamically, when we could be using just the same pointer.
>> It would only require to be careful not to destroy a network structure,
>> before removing its entry in the hash.
>> (here it's a win/win on memory/performance)
>
> Which hash are you talking about? And we have a path and an id that we 
> generate.  You might be able to optimize one, but not the other.
>
> Anyway, can be done and might even be a good idea.

I'll propose something in the relevant project.
That's what I did with connman/src/peer.c : the peer->path is the key in 
the hash table, it's the same pointer as the entry key inside the hash 
table.
Though indeed it requires to be a bit more careful.

>   But how is this relevant to the discussion about re-entrancy?

Nothing in my mail has to do with the re-entrancy. I should have started 
another thread.

>> On list - or queues - what are the arguments about using dynamically
>> allocated ones vs the linux "list.h" way for instance?
>> Isn't the later one a bit better from memory point of view if it would
>> be single linked one (as it is not if I remember well)?
>> (though the syntax is odd I agree, taste issue issue here so it's
>> subjective).
>>
>
> We looked into that and decided against it.  Yes it is a bit more 
> efficient storage wise if used right, but the syntax is painful. It is 
> also not really what we're used to (see above).

Ok, though this has implication with my very first answer above, let's see.


Cheers,

Tomasz

[PATCH 7/9] unit: hashmap: Re-entrancy tests added

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 2464 bytes --]

Check that we can add and remove items from hash while inside
foreach callback.
---
 unit/test-hashmap.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)

diff --git a/unit/test-hashmap.c b/unit/test-hashmap.c
index 75c249c..51d03ba 100644
--- a/unit/test-hashmap.c
+++ b/unit/test-hashmap.c
@@ -184,11 +184,92 @@ static void test_str(const void *test_data)
 	l_hashmap_destroy(hashmap, NULL);
 }
 
+static void foreach_cb(const void *key, void *value, void *user_data)
+{
+	struct l_hashmap *hashmap = user_data;
+	static bool removed, insert, conflict;
+	unsigned int entries;
+	char *str, *mykey = "b";
+	bool ret;
+
+	if (!removed) {
+		printf("Removing entry in foreach\n");
+
+		entries = l_hashmap_size(hashmap);
+
+		str = l_hashmap_remove(hashmap, "a");
+		assert(str);
+
+		assert(!l_hashmap_lookup(hashmap, "a"));
+
+		assert(entries == (l_hashmap_size(hashmap) + 1));
+
+		removed = true;
+	}
+
+	if (!insert) {
+		printf("Adding entry in foreach\n");
+
+		entries = l_hashmap_size(hashmap);
+
+		ret = l_hashmap_insert(hashmap, mykey, mykey);
+		assert(ret);
+
+		assert(entries == (l_hashmap_size(hashmap) - 1));
+
+		insert = true;
+	}
+
+	if (!conflict) {
+		printf("Adding conflicting entry in foreach\n");
+
+		entries = l_hashmap_size(hashmap);
+
+		assert(l_hashmap_lookup(hashmap, mykey));
+
+		ret = l_hashmap_insert(hashmap, mykey, mykey);
+		assert(ret);
+
+		assert(entries == l_hashmap_size(hashmap));
+
+		conflict = true;
+	}
+}
+
+static void test_reentrant(const void *test_data)
+{
+	struct l_hashmap *hashmap;
+	const void *ptr;
+	const char **itr, *strings[] = {
+		"hello",
+		"world",
+		"a",
+		"a longer key here",
+		NULL
+	};
+
+	hashmap = l_hashmap_string_new();
+	assert(hashmap);
+	assert(l_hashmap_size(hashmap) == 0);
+	assert(l_hashmap_isempty(hashmap));
+
+	for (itr = strings; *itr != NULL; itr++) {
+		assert(l_hashmap_insert(hashmap, *itr, itr));
+		ptr = l_hashmap_lookup(hashmap, *itr);
+		assert(ptr == itr);
+	}
+
+	l_hashmap_foreach(hashmap, foreach_cb, hashmap);
+
+	l_hashmap_destroy(hashmap, NULL);
+}
+
 int main(int argc, char *argv[])
 {
 	l_test_init(&argc, &argv);
 
 	l_test_add("Pointer Test", test_ptr, NULL);
 	l_test_add("String Test", test_str, NULL);
+	l_test_add("Re-entrant Test", test_reentrant, NULL);
 	return l_test_run();
 }
-- 
1.8.3.1

[PATCH 8/9] hashmap: Add support to finding an element from hash

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 2464 bytes --]

Add new function l_hashmap_find() which is similar to foreach.
The find will start to call a user supplied function for every
entry in hashmap. If user function returns true, then the find
will return and not call remaining hash elements.
---
 ell/hashmap.c | 39 +++++++++++++++++++++++++++++++++++++++
 ell/hashmap.h |  5 +++++
 2 files changed, 44 insertions(+)

diff --git a/ell/hashmap.c b/ell/hashmap.c
index 6c7c10f..03fcd7c 100644
--- a/ell/hashmap.c
+++ b/ell/hashmap.c
@@ -687,3 +687,42 @@ LIB_EXPORT bool l_hashmap_isempty(struct l_hashmap *hashmap)
 
 	return hashmap->entries == 0;
 }
+
+/**
+ * l_hashmap_find:
+ * @hashmap: hash table object
+ * @function: callback function
+ * @user_data: user data given to callback function
+ *
+ * Call @function for every entry in @hashmap. If @function returns true,
+ * then quit calling @function.
+ **/
+LIB_EXPORT void l_hashmap_find(struct l_hashmap *hashmap,
+			l_hashmap_find_func_t function, void *user_data)
+{
+	unsigned int i;
+
+	if (unlikely(!hashmap || !function))
+		return;
+
+	for (i = 0; i < NBUCKETS; i++) {
+		struct entry *entry, *head = &hashmap->buckets[i];
+
+		if (!head->next)
+			continue;
+
+		for (entry = head;; entry = entry->next) {
+			bool found;
+
+			if (!entry->removed) {
+				found = function(entry->key, entry->value,
+						user_data);
+				if (found)
+					return;
+			}
+
+			if (entry->next == head)
+				break;
+		}
+	}
+}
diff --git a/ell/hashmap.h b/ell/hashmap.h
index a904109..3085477 100644
--- a/ell/hashmap.h
+++ b/ell/hashmap.h
@@ -31,6 +31,8 @@ extern "C" {
 
 typedef void (*l_hashmap_foreach_func_t) (const void *key, void *value,
 							void *user_data);
+typedef bool (*l_hashmap_find_func_t) (const void *key, void *value,
+							void *user_data);
 typedef void (*l_hashmap_destroy_func_t) (void *value);
 typedef unsigned int (*l_hashmap_hash_func_t) (const void *p);
 typedef int (*l_hashmap_compare_func_t) (const void *a, const void *b);
@@ -70,6 +72,9 @@ void *l_hashmap_lookup(struct l_hashmap *hashmap, const void *key);
 void l_hashmap_foreach(struct l_hashmap *hashmap,
 			l_hashmap_foreach_func_t function, void *user_data);
 
+void l_hashmap_find(struct l_hashmap *hashmap,
+			l_hashmap_find_func_t function, void *user_data);
+
 unsigned int l_hashmap_size(struct l_hashmap *hashmap);
 bool l_hashmap_isempty(struct l_hashmap *hashmap);
 
-- 
1.8.3.1

Re: [PATCH 8/9] hashmap: Add support to finding an element from hash

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 3088 bytes --]

Hi Denis,

On ti, 2015-02-10 at 16:42 +0200, Jukka Rissanen wrote:
> Add new function l_hashmap_find() which is similar to foreach.
> The find will start to call a user supplied function for every
> entry in hashmap. If user function returns true, then the find
> will return and not call remaining hash elements.
> ---

Just wanted to ask are you ok with func? At the moment there is no
function to traverse the hash, other than the foreach variant and it is
very sub-optimal as it will traverse the whole hash even if such a thing
is not needed by the caller. Even better option would be to change the
return parameter of foreach callback to return bool so we could do with
only one traversing function.


>  ell/hashmap.c | 39 +++++++++++++++++++++++++++++++++++++++
>  ell/hashmap.h |  5 +++++
>  2 files changed, 44 insertions(+)
> 
> diff --git a/ell/hashmap.c b/ell/hashmap.c
> index 6c7c10f..03fcd7c 100644
> --- a/ell/hashmap.c
> +++ b/ell/hashmap.c
> @@ -687,3 +687,42 @@ LIB_EXPORT bool l_hashmap_isempty(struct l_hashmap *hashmap)
>  
>  	return hashmap->entries == 0;
>  }
> +
> +/**
> + * l_hashmap_find:
> + * @hashmap: hash table object
> + * @function: callback function
> + * @user_data: user data given to callback function
> + *
> + * Call @function for every entry in @hashmap. If @function returns true,
> + * then quit calling @function.
> + **/
> +LIB_EXPORT void l_hashmap_find(struct l_hashmap *hashmap,
> +			l_hashmap_find_func_t function, void *user_data)
> +{
> +	unsigned int i;
> +
> +	if (unlikely(!hashmap || !function))
> +		return;
> +
> +	for (i = 0; i < NBUCKETS; i++) {
> +		struct entry *entry, *head = &hashmap->buckets[i];
> +
> +		if (!head->next)
> +			continue;
> +
> +		for (entry = head;; entry = entry->next) {
> +			bool found;
> +
> +			if (!entry->removed) {
> +				found = function(entry->key, entry->value,
> +						user_data);
> +				if (found)
> +					return;
> +			}
> +
> +			if (entry->next == head)
> +				break;
> +		}
> +	}
> +}
> diff --git a/ell/hashmap.h b/ell/hashmap.h
> index a904109..3085477 100644
> --- a/ell/hashmap.h
> +++ b/ell/hashmap.h
> @@ -31,6 +31,8 @@ extern "C" {
>  
>  typedef void (*l_hashmap_foreach_func_t) (const void *key, void *value,
>  							void *user_data);
> +typedef bool (*l_hashmap_find_func_t) (const void *key, void *value,
> +							void *user_data);
>  typedef void (*l_hashmap_destroy_func_t) (void *value);
>  typedef unsigned int (*l_hashmap_hash_func_t) (const void *p);
>  typedef int (*l_hashmap_compare_func_t) (const void *a, const void *b);
> @@ -70,6 +72,9 @@ void *l_hashmap_lookup(struct l_hashmap *hashmap, const void *key);
>  void l_hashmap_foreach(struct l_hashmap *hashmap,
>  			l_hashmap_foreach_func_t function, void *user_data);
>  
> +void l_hashmap_find(struct l_hashmap *hashmap,
> +			l_hashmap_find_func_t function, void *user_data);
> +
>  unsigned int l_hashmap_size(struct l_hashmap *hashmap);
>  bool l_hashmap_isempty(struct l_hashmap *hashmap);
>  


Jukka

Re: [PATCH 8/9] hashmap: Add support to finding an element from hash

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 1899 bytes --]

Hi Jukka,

On 02/12/2015 02:35 AM, Jukka Rissanen wrote:
> Hi Denis,
>
> On ti, 2015-02-10 at 16:42 +0200, Jukka Rissanen wrote:
>> Add new function l_hashmap_find() which is similar to foreach.
>> The find will start to call a user supplied function for every
>> entry in hashmap. If user function returns true, then the find
>> will return and not call remaining hash elements.
>> ---
>
> Just wanted to ask are you ok with func? At the moment there is no
> function to traverse the hash, other than the foreach variant and it is
> very sub-optimal as it will traverse the whole hash even if such a thing
> is not needed by the caller. Even better option would be to change the
> return parameter of foreach callback to return bool so we could do with
> only one traversing function.
>

I'm not totally against it, so I might be convinced this is useful. 
However, I really have to wonder why a hashmap is being used as a
glorified linked list?  Whats the target use case?

<snip>

>>   							void *user_data);
>> +typedef bool (*l_hashmap_find_func_t) (const void *key, void *value,
>> +							void *user_data);
>>   typedef void (*l_hashmap_destroy_func_t) (void *value);
>>   typedef unsigned int (*l_hashmap_hash_func_t) (const void *p);
>>   typedef int (*l_hashmap_compare_func_t) (const void *a, const void *b);
>> @@ -70,6 +72,9 @@ void *l_hashmap_lookup(struct l_hashmap *hashmap, const void *key);
>>   void l_hashmap_foreach(struct l_hashmap *hashmap,
>>   			l_hashmap_foreach_func_t function, void *user_data);
>>
>> +void l_hashmap_find(struct l_hashmap *hashmap,
>> +			l_hashmap_find_func_t function, void *user_data);
>> +

If we're going to do this, then the signature should mimic 
l_hashmap_lookup.  e.g.

void *l_hashmap_find(struct l_hashmap *hashmap,
			l_hashmap_find_func_t function,
			void *user_data);

Regards,
-Denis

[PATCH 9/9] unit: hashmap: Add unit test for l_hashmap_find

[Jukka Rissanen]

[-- Attachment #1: Type: text/plain, Size: 1336 bytes --]

---
 unit/test-hashmap.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/unit/test-hashmap.c b/unit/test-hashmap.c
index 51d03ba..e9c4541 100644
--- a/unit/test-hashmap.c
+++ b/unit/test-hashmap.c
@@ -236,6 +236,39 @@ static void foreach_cb(const void *key, void *value, void *user_data)
 	}
 }
 
+static unsigned int find_called = 0;
+
+static bool find_cb(const void *key, void *value, void *user_data)
+{
+	struct l_hashmap *hashmap = user_data;
+	static bool removed;
+	static unsigned int entries;
+	char *str, *mykey = "b";
+	bool ret;
+
+	if (!removed) {
+		printf("Removing entry in find\n");
+
+		str = l_hashmap_remove(hashmap, "world");
+		assert(str);
+
+		assert(!l_hashmap_lookup(hashmap, "world"));
+
+		entries = l_hashmap_size(hashmap);
+
+		removed = true;
+	}
+
+	find_called++;
+
+	if (!(find_called % 2)) {
+		assert(entries == 3);
+		return true;
+	}
+
+	return false;
+}
+
 static void test_reentrant(const void *test_data)
 {
 	struct l_hashmap *hashmap;
@@ -261,6 +294,9 @@ static void test_reentrant(const void *test_data)
 
 	l_hashmap_foreach(hashmap, foreach_cb, hashmap);
 
+	l_hashmap_find(hashmap, find_cb, hashmap);
+	assert(find_called == 2);
+
 	l_hashmap_destroy(hashmap, NULL);
 }
 
-- 
1.8.3.1