etl::unordered_map buffer overflow

[TG-SAG]

The basic idea of the i... base classes (AFAIK) is that you can use them on interfaces without knowing the size of a container.
This example uses 2 empty etl::unordered_map's of different sizes and compares them via base class references (see Godbolt at the end):

etl::unordered_map<int, int, 666> um1;
etl::unordered_map<int, int, 42> um2;

etl::iunordered_map<int, int>& ium1 = um1;
etl::iunordered_map<int, int>& ium2 = um2;
bool b = ium1 == ium2; 

This seems to be a valid use of the i... base classes. And it worked in version 20.28.0 for me. I tried to switch to version 20.38.10 but it fails in my unit tests (I have additional ones added independent of the ETL unit tests) because I'm using the address sanitizer while developing. BTW, it also fails if you compare unordered_map's instead of iunordered_map's because they seem to use the same operator==.

There seems to be a change in the operator== for the unordered_map. Bevor it just used etl::equal and currently it somehow seems to iterate over the bucket size which is different for the above containers (and therefor "overflows" the second smaller container).

Sadly the buffer overflow is only visible with additional tooling (-fsanitize=address) and looks like it's working without (but it's not).

This Godbolt example - with the currently latest version of ETL - will produce the problem: https://gcc.godbolt.org/z/qnn1e8TeY

[TG-SAG]

I've made a change to thebool operator ==(const etl::iunordered_map<TKey, T, TKeyCompare>& lhs, const etl::iunordered_map<TKey, T, TKeyCompare>& rhs) that seems to have fixed the problem but I don't know if this is the right way to go because there might be a better way to fix it.

diff --git a/include/etl/unordered_map.h b/include/etl/unordered_map.h
index 0e5b9e35..240aa0c0 100644
--- a/include/etl/unordered_map.h
+++ b/include/etl/unordered_map.h
@@ -1577,7 +1577,8 @@ namespace etl
 
     if (sizes_match)
     {
-      for (size_t i = 0; (i < lhs.bucket_count()) && elements_match; ++i)
+      const size_t bucket_count = etl::min(lhs.bucket_count(), rhs.bucket_count());
+      for (size_t i = 0; (i < bucket_count) && elements_match; ++i)
       {
         if (!etl::is_permutation(lhs.begin(i), lhs.end(i), rhs.begin(i)))

At least I have somehow verified my speculation from the above issue

[jwellbelove]

I don't think that would work as the map with the larger number of buckets would not have all of its buckets tested.

[jwellbelove]

What I think is required is an equal_range check and then a value check (using permutation for multimap).

[TG-SAG]

I've a basic question on how a comparison on a ETL container should work.
Say I've two containers from the same type but different sizes and I put the same values in both container, will they compare equal (with operator==)?

A simple example might be:

    etl::vector<int, 42> v1;
    etl::vector<int, 666> v2;

    v1.push_back(1);
    v1.push_back(23);
    
    v2.push_back(1);
    v2.push_back(23);

Will they compare equal? Yes, they do: https://gcc.godbolt.org/z/Gd6o4xx6q (For etl::vector and etl::ivector types)

I would expect the same behavior with an ETL unordered_map. For example:

    etl::unordered_map<int, int, 42> um1;
    etl::unordered_map<int, int, 666> um2;

    um1[45] = 11;
    um1[30] = 2;

    um2[45] = 11;
    um2[30] = 2;

I would expect them to compare equal, but they don't: https://gcc.godbolt.org/z/hdffTrxxz
Curiously if you switch the capacity in the containers they compare equal: https://gcc.godbolt.org/z/j3hPT19v9 (with the hidden problem that the sanitizer will show: https://gcc.godbolt.org/z/oaq99TYM7)

Getting back to the general question on how containers with different capacity should compare in ETL, I think that they should compare equal if the size and content is the same. This is the case (for example) for etl::vector but not for etl::unordered map. Whatever the intended behavior is, it should be the same with all container types, shouldn't it?

If we agree on the defined behavior I can think of a solution for etl::unordered_map

[jwellbelove]

I've tried a new version for etl::unordered_map. As it only has ever 0 or 1 element for each key, its implementation is slightly simpler than that for etl::unordered_multimap, which requires a range distance and permutation test.

I also noticed that the template parameters were incorrect for == & !=.

template <typename TKey, typename T, typename THash, typename TKeyEqual>
bool operator ==(const etl::iunordered_map<TKey, T, THash, TKeyEqual>& lhs, const etl::iunordered_map<TKey, T, THash, TKeyEqual>& rhs)
{
  const bool sizes_match = (lhs.size() == rhs.size());
  bool elements_match = true;

  typedef typename etl::iunordered_map<TKey, T, THash, TKeyEqual>::const_iterator itr_t;
    
  if (sizes_match)
  {
    itr_t l_begin = lhs.begin();
    itr_t l_end   = lhs.end();

    while ((l_begin != l_end) && elements_match)
    {
      const TKey key     = l_begin->first;
      const T    l_value = l_begin->second;

      // See if the lhs key exists in the rhs.
      ETL_OR_STD::pair<itr_t, itr_t> range = rhs.equal_range(key);

      if (range.first != rhs.end())
      {
        // See if the values match
        const T r_value = range.first->second;

        elements_match = (r_value == l_value);
      }
      else
      {
        elements_match = false;
      }

      ++l_begin;
    }
  }

  return (sizes_match && elements_match);
}

[jwellbelove]

Whatever the intended behavior is, it should be the same with all container types, shouldn't it?

Correct.

[jwellbelove]

Operator == patch
etl-18-41-33-unordered-map-set.patch

[TG-SAG]

I applied your patch to my repository and it seems to work. All my unittest are passed now :-)
I might not have full coverage of all the functionality of etl::unordered_map but I will check in the next days.
Currently I don't have any test for etl::[i]unordered_multiset because I'm not using it and therefore I can't comment on that change.

Will you merge it?

[jwellbelove]

I need to run my full CI tests on my machine first, and if everything is ok, I'll merge and push a new version.