On Fri, Feb 22, 2019 at 07:31:59PM -0800, Han Zhou wrote: > On Fri, Feb 22, 2019 at 5:27 PM Ben Pfaff <b...@ovn.org> wrote: > > > > On Fri, Feb 22, 2019 at 05:21:51PM -0800, Han Zhou wrote: > > > On Fri, Feb 22, 2019 at 3:04 PM Ben Pfaff <b...@ovn.org> wrote: > > > > > > > > Using HMAP_FOR_EACH_SAFE_WITH_HASH tends to imply that an hmap can have > > > > more than one item with a given key. Nothing prevents that, and it will > > > > otherwise work, but it is unusual and it normally makes sense to use an > > > > hindex instead of an hmap for efficiency's sake if it is going to happen > > > > very often. Does the data structure in question often have duplicates? > > > > Should we change it to an hindex? > > > > > > Hi Ben, I think you are asking if there can be more than one item with > > > a given "hash value". Yes it is possible, but it should not be often > > > for the data structure in question here - the json cache. The key is > > > uuid of the change set combined with monitor version, and the hash is > > > the uuid_hash. So conflicts of uuid_hash should be rare. When there > > > are different versions (e.g. monitor v1, v2, v3) of clients referring > > > same change sets we do get more items with same hash value, but there > > > were at most 2 versions and I am adding 1 more in next patches in the > > > series, and I guess it is not likely we add too many versions of > > > monitors in the future, and even that is possible, it is unlikely that > > > many different versions of clients co-exists in same environment. So I > > > don't think it has a real impact to performance. > > > > > > The reason for using HMAP_FOR_EACH_SAFE_WITH_HASH instead of > > > HMAP_FOR_EACH_WITH_HASH is just because the node is going to be > > > removed and freed in the loop. It needs to be safe regardless of the > > > probability of hash conflicts. > > > > It's important to be clear about the difference between hashes and keys. > > The hash is what's stored in the hmap_node (that is, the uuid_hash() > > return value in this case), the key in this case is what uuid_equals() > > compares. I *think* you are saying there can be a small number of > > duplicate keys in the hmap in this case. Is that correct? > > I thought you were talking about hashes instead of keys (I thought it > was a typo), because I assume keys are always unique. > Let me clarify a little more. In the json_cache hmap, the key is the > combination of <change_set_uuid, version> of the struct > ovsdb_monitor_json_cache_node. This key uniquely identifies each > element in the hmap. The hash function doesn't take version into the > hash calculation, so if there are multiple versions of clients exist > at the same time, there will be different elements with same hash. > However, since the number of versions should be very small (worse case > 3, most cases 1), this is not going to cause any performance problem. > There do exist probability of hash conflict even if there is only one > version, but the chances are very low (ensured by uuid_hash). > > Now for the function: > +/* Free all versions of json cache for a given change_set.*/ > +static void > +ovsdb_monitor_json_cache_destroy(struct ovsdb_monitor *dbmon, > + struct ovsdb_monitor_change_set *change_set) > > It is different from a general function that destroys an element in a > hmap with the unique key. Instead, it destroys *all versions* of the > json cache for a given change_set uuid. So it uses only part of the > key to do the search, which may have caused some confusion.
Ah. This is an unusual combination of factors. Very unusual in fact. If it is something we really want, then I think that it should be carefully documented in a comment on the data structure. _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev