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

sync: sync.Map keys will never be garbage collected #40999

Closed
PureWhiteWu opened this issue Aug 24, 2020 · 39 comments
Closed

sync: sync.Map keys will never be garbage collected #40999

PureWhiteWu opened this issue Aug 24, 2020 · 39 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@PureWhiteWu
Copy link
Contributor

What version of Go are you using (go version)?

$ go version
go1.15

Does this issue reproduce with the latest release?

yes

What operating system and processor architecture are you using (go env)?

Can reproduce on any os and arch.

What did you do?

We are using some big struct as keys for sync.Map, struct{} as value, and we observed a memory leak after upgrading to go 1.15. I confirmed that this is because sync.Map will never delete keys. Instead, it only set the value to nil.

It worked well before 1.15 because we happened to have no read operation during the lifetime, and we were only reading it during shutdown so we didn't discover the memory leak, as some code like this: https://play.golang.org/p/YdY4gOcXVMO. So we happened to only have no key prompted to sync.Map.read, and thus Delete could delete the key in sync.Map.dirty.

In go1.15, this behaviour was changed by https://go-review.googlesource.com/c/go/+/205899, and causes a memory leak in our code.

This isn't the same as the behaviour of the native map. I admit I have misused sync.Map, but I think this behaviour should either be documented clearly or be changed.

PureWhiteWu added a commit to PureWhiteWu/go that referenced this issue Aug 24, 2020
Keys of sync.Map will never be deleted, this behaviour isn't the same as the native map.
We should document this clearly.

Fixes golang#40999 .
PureWhiteWu added a commit to PureWhiteWu/go that referenced this issue Aug 24, 2020
Keys of sync.Map will never be deleted, this behaviour isn't the same as the native map.
We should document this clearly.

Fixes golang#40999 .
@PureWhiteWu

This comment has been minimized.

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/250157 mentions this issue: sync: document keys of sync.Map will never be deleted

@ALTree ALTree changed the title doc: sync.Map keys will never be garbage collected sync: sync.Map keys will never be garbage collected Aug 24, 2020
@ALTree ALTree added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. and removed Documentation labels Aug 24, 2020
@davecheney
Copy link
Contributor

I don’t think deleting a key from a map should leave the key. How are you determining that memory is leaking?

@ALTree ALTree added this to the Go1.16 milestone Aug 24, 2020
@PureWhiteWu
Copy link
Contributor Author

@davecheney the current behaviour of sync.Map leaves the key. You can check it.

@davecheney
Copy link
Contributor

Could you please explain how.

@PureWhiteWu
Copy link
Contributor Author

@davecheney m.Delete only gets the value(e) from m.read or m.dirty, and e.delete() only sets it to nil.
It doesn't delete the key in m.read or m.dirty(after go1.15).

// LoadAndDelete deletes the value for a key, returning the previous value if any.
// The loaded result reports whether the key was present.
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// Regardless of whether the entry was present, record a miss: this key
			// will take the slow path until the dirty map is promoted to the read
			// map.
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if ok {
		return e.delete()
	}
	return nil, false
}

// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
	m.LoadAndDelete(key)
}

func (e *entry) delete() (value interface{}, ok bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == nil || p == expunged {
			return nil, false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return *(*interface{})(p), true
		}
	}
}

@davecheney
Copy link
Contributor

@bcmills please excuse me if I got the attribution wrong, but is this the expected behaviour?

@davecheney
Copy link
Contributor

@PureWhiteWu are you able to demonstrate a difference in runtime.Memstats to confirm that the key is not being deleted?

@PureWhiteWu
Copy link
Contributor Author

@davecheney It's quite easy to obverse from pprof/heap. You can try it.
The flame graph contains some internal code structure, so I cannot paste it here, sorry for this.

@PureWhiteWu
Copy link
Contributor Author

@rsc Excuse me, is this behaviour by-design or a bug?

@davecheney
Copy link
Contributor

@davecheney It's quite easy to obverse from pprof/heap. You can try it.
The flame graph contains some internal code structure, so I cannot paste it here, sorry for this.

Would you be able to include that data with your bug report please.

@PureWhiteWu
Copy link
Contributor Author

@davecheney Is this enough?
image

@PureWhiteWu
Copy link
Contributor Author

here, the linkBufferNode is referenced by something which is a key in a sync.Map that should have been deleted.

@davecheney
Copy link
Contributor

Thank you for the frame graph, it’s hard to tell what is going on from that. I’m going to wait for the person who made that change to comment

@PureWhiteWu
Copy link
Contributor Author

@davecheney I've added a Debug method in sync.Map:

func (m *Map) Debug() {
	m.mu.Lock()
	println("sync.Map read:")
	for k := range m.read.Load().(readOnly).m {
		println(k)
	}
	println("sync.Map dirty:")
	for k := range m.dirty {
		println(k)
	}
	println("sync.Map debug end.")
	m.mu.Unlock()
}

And the example code to call Debug: https://play.golang.org/p/H3fkSdAw-JJ
Output:

sync.Map read:
(0x1064920,0xc00000c060)
(0x1064920,0xc00000c0e0)
(0x1064920,0xc00000c140)
(0x1064920,0xc00000c100)
(0x1064920,0xc00000c120)
(0x1064920,0xc00000c160)
(0x1064920,0xc00000c040)
(0x1064920,0xc00000c080)
(0x1064920,0xc00000c0a0)
(0x1064920,0xc00000c0c0)
sync.Map dirty:
sync.Map debug end.

As you can see, the keys are not deleted.

@iand
Copy link
Contributor

iand commented Aug 24, 2020

@PureWhiteWu are you able to write a test that passes on 1.14 but fails on 1.15

@PureWhiteWu
Copy link
Contributor Author

@iand Sure, example code: https://play.golang.org/p/lHKYvukGbpZ
Also I added the Debug method above in both go 1.15 and 1.14.
On go 1.15, output:

sync.Map read:
sync.Map dirty:
(0x1064560,0xc00000c080)
(0x1064560,0xc00000c0a0)
(0x1064560,0xc00000c0c0)
(0x1064560,0xc00000c100)
(0x1064560,0xc00000c120)
(0x1064560,0xc00000c140)
(0x1064560,0xc00000c160)
(0x1064560,0xc00000c040)
(0x1064560,0xc00000c0e0)
(0x1064560,0xc00000c060)
sync.Map debug end.

On go 1.14, output:

sync.Map read:
sync.Map dirty:
(0x10603e0,0xc00000c100)
(0x10603e0,0xc00000c0c0)
(0x10603e0,0xc00000c140)
(0x10603e0,0xc00000c040)
(0x10603e0,0xc00000c080)
sync.Map debug end.

You can see that, if there's no read operation on map, the keys in dirty part can be deleted.

@PureWhiteWu
Copy link
Contributor Author

@iand keys in sync.Map.read are not deleted neither on go1.14 not go1.15, I just happened to have no read operation, so all my keys are in dirty and can be deleted.

@davecheney
Copy link
Contributor

Here is a simpler reproduction

(~/src) % env GODEBUG=gctrace=1 ./leak
gc 1 @0.015s 4%: 0.024+3.3+0.018 ms clock, 0.096+0.37/3.1/0.077+0.074 ms cpu, 5->5->3 MB, 6 MB goal, 4 P
gc 2 @0.032s 5%: 0.009+4.8+0.031 ms clock, 0.038+0.45/4.3/5.4+0.12 ms cpu, 8->8->6 MB, 9 MB goal, 4 P
gc 3 @0.069s 6%: 0.014+11+0.017 ms clock, 0.058+0.31/10/7.3+0.070 ms cpu, 16->17->12 MB, 17 MB goal, 4 P
gc 4 @0.152s 5%: 0.012+34+0.018 ms clock, 0.050+4.6/16/16+0.074 ms cpu, 33->34->25 MB, 34 MB goal, 4 P
gc 5 @0.317s 5%: 0.013+48+0.018 ms clock, 0.055+3.8/37/63+0.075 ms cpu, 67->67->50 MB, 68 MB goal, 4 P
gc 6 @0.652s 5%: 0.014+92+0.052 ms clock, 0.058+0.66/91/157+0.20 ms cpu, 135->135->100 MB, 136 MB goal, 4 P
gc 7 @1.322s 6%: 0.014+203+0.020 ms clock, 0.057+42/192/357+0.080 ms cpu, 269->270->200 MB, 270 MB goal, 4 P
gc 8 @2.721s 7%: 0.014+479+0.019 ms clock, 0.056+120/478/955+0.079 ms cpu, 539->541->400 MB, 540 MB goal, 4 P
gc 9 @5.619s 10%: 0.016+1205+0.026 ms clock, 0.064+759/1202/2360+0.10 ms cpu, 1079->1081->799 MB, 1080 MB goal, 4 P
^C
(~/src) % cat leak.go 
package main

import "sync"

func main() {
	var sm sync.Map

	var value [16]byte

	for i := 0; i < 1<<26; i++ {
		sm.Store(i, value)
		sm.Delete(i - 1)
	}
}

@davecheney
Copy link
Contributor

This is not reproducible under Go 1.14

(~/src) % go1.14 build leak.go 
(~/src) % env GODEBUG=gctrace=1 ./leak
gc 1 @0.023s 0%: 0.005+0.18+0.023 ms clock, 0.020+0.038/0.016/0.15+0.092 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 2 @0.044s 0%: 0.047+0.12+0.016 ms clock, 0.19+0.072/0.008/0.065+0.064 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 3 @0.065s 0%: 0.031+0.13+0.004 ms clock, 0.12+0.090/0.001/0.13+0.016 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 4 @0.087s 0%: 0.049+0.088+0.003 ms clock, 0.19+0.078/0.012/0.068+0.014 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 5 @0.109s 0%: 0.019+0.16+0.017 ms clock, 0.078+0.066/0.045/0.10+0.070 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 6 @0.131s 0%: 0.046+0.11+0.003 ms clock, 0.18+0.082/0.006/0.075+0.013 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 7 @0.152s 0%: 0.048+0.15+0.022 ms clock, 0.19+0.067/0.009/0.065+0.089 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 8 @0.173s 0%: 0.048+0.16+0.018 ms clock, 0.19+0.068/0.009/0.079+0.073 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 9 @0.194s 0%: 0.051+0.095+0.003 ms clock, 0.20+0.084/0.009/0.079+0.012 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 10 @0.215s 0%: 0.045+0.13+0.018 ms clock, 0.18+0.068/0.014/0.081+0.072 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
gc 11 @0.236s 0%: 0.051+0.20+0.026 ms clock, 0.20+0.083/0.011/0.072+0.10 ms cpu, 4->4->0 MB, 5 MB goal, 4 P

@PureWhiteWu
Copy link
Contributor Author

@davecheney Thank you for your reproduction!

@davecheney
Copy link
Contributor

@PureWhiteWu would you consider abandoning your documentation CL. I do not believe we should document this incorrect behaviour.

@PureWhiteWu
Copy link
Contributor Author

@davecheney maybe we should confirm if this is by-design or a bug first?

@iand
Copy link
Contributor

iand commented Aug 24, 2020

@davecheney maybe we should confirm if this is by-design or a bug first?

This is clearly a change in behaviour between versions so it needs fixing

@davecheney
Copy link
Contributor

git bisect points to 2e8dbae as @PureWhiteWu noted.

@PureWhiteWu
Copy link
Contributor Author

@iand This is an undocumented behaviour, which is quite related to the implementation(on go 1.14 keys in dirty can be deleted, which on 1.15 cannot).
On all go versions, keys in read cannot be deleted, this is consistent.
I think we should discuss if this behaviour is by-design.

@PureWhiteWu
Copy link
Contributor Author

And I think users should not know if a key is in dirty or read.

@davecheney
Copy link
Contributor

@PureWhiteWu what reason would there be for chaining sync.Map in Go 1.15 so that Delete did not delete entries? I think the more reasonable answer is this is a bug.

@PureWhiteWu
Copy link
Contributor Author

PureWhiteWu commented Aug 24, 2020

@davecheney
On go < 1.15, if a key has been prompted to read, it cannot be deleted either.
This is the problem, not only at dirty.

@PureWhiteWu
Copy link
Contributor Author

Here is a simpler reproduction

(~/src) % env GODEBUG=gctrace=1 ./leak
gc 1 @0.015s 4%: 0.024+3.3+0.018 ms clock, 0.096+0.37/3.1/0.077+0.074 ms cpu, 5->5->3 MB, 6 MB goal, 4 P
gc 2 @0.032s 5%: 0.009+4.8+0.031 ms clock, 0.038+0.45/4.3/5.4+0.12 ms cpu, 8->8->6 MB, 9 MB goal, 4 P
gc 3 @0.069s 6%: 0.014+11+0.017 ms clock, 0.058+0.31/10/7.3+0.070 ms cpu, 16->17->12 MB, 17 MB goal, 4 P
gc 4 @0.152s 5%: 0.012+34+0.018 ms clock, 0.050+4.6/16/16+0.074 ms cpu, 33->34->25 MB, 34 MB goal, 4 P
gc 5 @0.317s 5%: 0.013+48+0.018 ms clock, 0.055+3.8/37/63+0.075 ms cpu, 67->67->50 MB, 68 MB goal, 4 P
gc 6 @0.652s 5%: 0.014+92+0.052 ms clock, 0.058+0.66/91/157+0.20 ms cpu, 135->135->100 MB, 136 MB goal, 4 P
gc 7 @1.322s 6%: 0.014+203+0.020 ms clock, 0.057+42/192/357+0.080 ms cpu, 269->270->200 MB, 270 MB goal, 4 P
gc 8 @2.721s 7%: 0.014+479+0.019 ms clock, 0.056+120/478/955+0.079 ms cpu, 539->541->400 MB, 540 MB goal, 4 P
gc 9 @5.619s 10%: 0.016+1205+0.026 ms clock, 0.064+759/1202/2360+0.10 ms cpu, 1079->1081->799 MB, 1080 MB goal, 4 P
^C
(~/src) % cat leak.go 
package main

import "sync"

func main() {
	var sm sync.Map

	var value [16]byte

	for i := 0; i < 1<<26; i++ {
		sm.Store(i, value)
		sm.Delete(i - 1)
	}
}

If you add a sm.Range(...) between sm.Store and sm.Delete, the memory leaks on go 1.14, too.

@davecheney
Copy link
Contributor

If you add a sm.Range(...) between sm.Store and sm.Delete, the memory leaks on go 1.14, too.

One bug at a time mate

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/250197 mentions this issue: sync: collect dirty keys

@bcmills bcmills added the NeedsFix The path to resolution is known, but the work has not been done. label Aug 24, 2020
@gopherbot gopherbot removed the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Aug 24, 2020
@bcmills
Copy link
Contributor

bcmills commented Aug 24, 2020

@gopherbot, please backport to 1.15. This is a regression from Go 1.14.7, and can cause difficult-to-predict memory leaks in existing code.

@gopherbot
Copy link
Contributor

Backport issue(s) opened: #41010 (for 1.14), #41011 (for 1.15).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://golang.org/wiki/MinorReleases.

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/250297 mentions this issue: [release-branch.go1.15] sync: delete dirty keys inside Map.LoadAndDelete

@PureWhiteWu
Copy link
Contributor Author

PureWhiteWu commented Aug 25, 2020

Here's another problem: keys in the read map cannot be deleted.
Should we reopen this issue and discuss this? Or shall I open another issue for this?
@bcmills @davecheney

@bcmills
Copy link
Contributor

bcmills commented Aug 25, 2020

Keys in the read map cannot be purged immediately, but they are only retained until the cost to rebuild the map has been amortized away. That is an intentional tradeoff in the design.

But perhaps we are missing some sort of cache-miss tracking for deleted keys. If you have a real-world program for which that causes a problem, please open a new issue and we can at least see if there is a straightforward fix for it.

(But also bear in mind that sync.Map is intended to solve a specific pattern in the Go standard library. It is surely not optimal for all “concurrent map” use-cases, and if it's not a good fit for your use-case it is totally fine to use something else instead. sync.Map should almost never appear in exported APIs, so in most cases it is easy to swap out for something else.)

@PureWhiteWu
Copy link
Contributor Author

@bcmills thanks for your reply!

@jhuix

This comment has been minimized.

gopherbot pushed a commit that referenced this issue Aug 27, 2020
Updates #40999
Fixes #41011

Change-Id: Ie32427e5cb5ed512b976b554850f50be156ce9f2
Reviewed-on: https://go-review.googlesource.com/c/go/+/250197
Run-TryBot: Emmanuel Odeke <emm.odeke@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Bryan C. Mills <bcmills@google.com>
(cherry picked from commit 94953d3)
Reviewed-on: https://go-review.googlesource.com/c/go/+/250297
Run-TryBot: Bryan C. Mills <bcmills@google.com>
Reviewed-by: Emmanuel Odeke <emm.odeke@gmail.com>
AZ-X added a commit to AZ-X/pique that referenced this issue Sep 1, 2020
@golang golang locked and limited conversation to collaborators Aug 25, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

7 participants