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

runtime: deltimer in time.go doesn't update the last after removing a timer #19887

Closed
ghasemloo opened this issue Apr 8, 2017 · 2 comments
Closed
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@ghasemloo
Copy link

ghasemloo commented Apr 8, 2017

https://github.com/golang/go/blob/master/src/runtime/time.go#L148
We remove the timer t at location i from the heap timers.t by replacing timers.t[i] with the last timer in the heap slice and then shrinking the slice. Then we need to shift it up/down to its correct location in the heap. In line 148 there is a short path that checks if it is already the last item in the heap slice.

We have not updated the value of the variable last so this if will always fail and we will perform shift up/down even if it is the last item in the updated slice. If we want to avoid shift up/down in that case we should either update the value of the variable last by last-- after line 147 or use if i != last-1 { instead of if i != last {;

However I think the short path might not actually work. The last item in the heap slice is not the largest item, even if its new location is the new last item of the slice it doesn't mean it is in the right location because it may need to move up, consider [0, 5, 2, 6, 7, 4] and assume we remove 7. if we don't perform a shift up/down we will end up with [0, 5, 2, 6, 4] which doesn't have the heap property as 4 is a child of 5 but is smaller than it. So I think we should just remove the if for the short path and always do shift up/down.

@bradfitz bradfitz changed the title deltimer in runtime/time.go doesn't update the last after removing a timer runtime: deltimer in time.go doesn't update the last after removing a timer Apr 8, 2017
@bradfitz bradfitz added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Apr 8, 2017
@bradfitz bradfitz added this to the Go1.9Maybe milestone Apr 8, 2017
@ianlancetaylor
Copy link
Contributor

It's true that we haven't updated the variable last, but we also haven't updated the variable i. If the condition i != last was true a few lines up, it will still be true. This code looks correct to me.

@ghasemloo
Copy link
Author

ghasemloo commented Apr 10, 2017

I see. So this if is not a short path for checking if the last timer is still the last in the slice but for checking if we moved a timer, in which case we need a shift up/down, otherwise we don't need to.

@golang golang locked and limited conversation to collaborators Apr 10, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

5 participants