3:42 p.m.
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
3:42 p.m.
New subject: [PATCH 1/9] hashmap: Add value free function
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
3:42 p.m.
New subject: [PATCH 2/9] hashmap: Call user supplied value free function in destroy
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
8:07 p.m.
New subject: [PATCH 2/9] hashmap: Call user supplied value free function in destroy
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
3:42 p.m.
New subject: [PATCH 3/9] hashmap: Call user supplied value free function in insert
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
8:18 p.m.
New subject: [PATCH 3/9] hashmap: Call user supplied value free function in insert
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
10:27 a.m.
New subject: [PATCH 3/9] hashmap: Call user supplied value free function in insert
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
12:04 p.m.
New subject: [PATCH 3/9] hashmap: Call user supplied value free function in insert
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
2:50 p.m.
New subject: [PATCH 3/9] hashmap: Call user supplied value free function in insert
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
3:42 p.m.
New subject: [PATCH 4/9] unit: hashmap: Add value free hash entry test
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
3:42 p.m.
New subject: [PATCH 5/9] unit: hashmap: Add replace entry test
---
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
3:42 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
8:47 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
10:21 a.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
3:06 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
8:23 a.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
7:02 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
8:25 a.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
6:55 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
4:38 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
Hi Denis, Jukka,
On Thu, Feb 12, 2015 at 7:55 PM, Denis Kenzior <denkenz(a)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
6:04 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
6:36 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
10:44 a.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
Hi Marcel, Denis,
On Fri, Feb 13, 2015 at 7:36 PM, Marcel Holtmann <marcel(a)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
5:18 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
7:27 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
Hi Marcel,
On Mon, Feb 16, 2015 at 6:18 PM, Marcel Holtmann <marcel(a)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=b72dee02b2e5de...
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
8:03 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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=b72dee02b2e5de...
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
10:48 a.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
5:41 p.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
9:23 a.m.
New subject: [PATCH 6/9] hashmap: Add re-entrancy support to foreach function
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
3:42 p.m.
New subject: [PATCH 7/9] unit: hashmap: Re-entrancy tests added
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
3:42 p.m.
New subject: [PATCH 8/9] hashmap: Add support to finding an element from hash
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
9:35 a.m.
New subject: [PATCH 8/9] hashmap: Add support to finding an element from hash
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
1:19 a.m.
New subject: [PATCH 8/9] hashmap: Add support to finding an element from hash
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
3:42 p.m.
New subject: [PATCH 9/9] unit: hashmap: Add unit test for l_hashmap_find
---
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
2477
days inactive
2483
days old
33 comments
6 participants
participants (6)
-
Denis Kenzior -
Jukka Rissanen -
Luiz Augusto von Dentz -
Marcel Holtmann -
Patrik Flykt -
Tomasz Bursztyka