Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ETS select_replace behaves inconsistently with a key containing an empty map and reference #8385

Closed
tsloughter opened this issue Apr 16, 2024 · 4 comments · May be fixed by #8387
Closed

ETS select_replace behaves inconsistently with a key containing an empty map and reference #8385

tsloughter opened this issue Apr 16, 2024 · 4 comments · May be fixed by #8387
Assignees
Labels
bug Issue is reported as a bug team:VM Assigned to OTP team VM

Comments

@tsloughter
Copy link
Contributor

Describe the bug

A table with a key of type {map(), reference()} with multiple entries and one with the key contaiing an empty map can result in ets:select_replace when used with an empty map in the key replacing 2 instead of 1 object.

This doesn't always happen. It'll replace only the 1 object with key containing #{} in some tables, while others tables it'll replace 2. If no object as the key #{} then it'll never replace one of the other objects and if there are more than 2 objects it'll never replace more than 1 or 2. And if no object has #{} in the key it'll always replace 0. So there has to be one exactly equal key for it to replace any and with certain tables it'll replace 2 instead of 1.

Important to also note that it happens immediately when a tables with this behavior is used, so the example to reproduce does 1 select_replace but must do it hundreds of times on a new table each time in order to reproduce.

To Reproduce

Thanks to @max-au for creating a minimal example, https://gist.github.com/max-au/2d4bb71f2b41a93c465dce592a21e86d

Running this code will result in output like:

Iteration 95: replaced 2 entries. Before:
[{{#{key => value},#Ref<0.2679931898.3968073729.103219>},original},
 {{#{},#Ref<0.2679931898.3968073729.103219>},original}]

After:
[{{#{key => value},#Ref<0.2679931898.3968073729.103219>},new},
 {{#{},#Ref<0.2679931898.3968073729.103219>},new}]

** exception error: {[{{#{key => value},#Ref<0.2679931898.3968073729.103219>},
                       original},
                      {{#{},#Ref<0.2679931898.3968073729.103219>},original}],
                     {#{},#Ref<0.2679931898.3968073729.103219>}}

This shows that on the 95th new table both elements in the table were replaced, all 94 before it only replaced the 1 element.

Expected behavior

Only 1 element being replaced each time, the one with key {#{}, #Ref<...>}. But I could also see it being correct to replace all objects because #{} will match any map in a match, but not it sometimes 1, sometimes 2, sometimes 0 if no #{} exists in the table and never >2. And it should be consistent whether a reference is in the key or not.

Affected versions

I have tried this on OTP-24 and 27.0-rc2.

Additional context

This was found due to transient CI failures in the metrics testing of https://github.com/open-telemetry/opentelemetry-erlang. Sometimes a result in a float counter (which use select_replace to increment the counter) would be wrong.

@tsloughter tsloughter added the bug Issue is reported as a bug label Apr 16, 2024
@jhogberg jhogberg self-assigned this Apr 16, 2024
@jhogberg jhogberg added the team:VM Assigned to OTP team VM label Apr 16, 2024
@jhogberg
Copy link
Contributor

Thanks for your report, I'll make a PR with a fix shortly. The correct behavior is to match both objects.

jhogberg added a commit to jhogberg/otp that referenced this issue Apr 16, 2024
@tsloughter
Copy link
Contributor Author

I was afraid of that :)

I see the fix is to treat it as not fully bound?

But I can't tell from the patch why it only happened on occasion and only to 2 objects, not all, when it would match multiple.

@jhogberg
Copy link
Contributor

jhogberg commented Apr 16, 2024

Since it got accidentally treated as fully bound, we went right to the hash bucket we "knew" that the object would be in. This bucket could either not contain any matching objects at all[1], or contain a subset thereof. Adding a reference made the test work by shaking the hash values around, and we'd see 2 objects returned whenever both objects happened to land in the same bucket.

[1]: For example when we have one object #{ a => a, b => b } and we query #{ a => a }, there is no guarantee that the bucket for #{ a => a } contains #{ a => a, b => b }

@tsloughter
Copy link
Contributor Author

Ah, neat!

jhogberg added a commit to jhogberg/otp that referenced this issue Apr 16, 2024
… into john/merge-25/OTP-19070

* john/erts/fix-ets-map-matching/erlangGH-8385/OTP-19070:
  ets: Treat keys containing maps as unbound
jhogberg added a commit that referenced this issue Apr 22, 2024
…maint

* john/erts/fix-ets-map-matching/GH-8385/OTP-19070:
  ets: Treat keys containing maps as unbound
@jhogberg jhogberg linked a pull request May 6, 2024 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Issue is reported as a bug team:VM Assigned to OTP team VM
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants