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

PureWhiteWu · 2020-08-24T07:53:08Z

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.

The text was updated successfully, but these errors were encountered:

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 .

gopherbot · 2020-08-24T08:13:31Z

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

davecheney · 2020-08-24T08:26:00Z

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

PureWhiteWu · 2020-08-24T08:29:16Z

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

davecheney · 2020-08-24T08:31:59Z

Could you please explain how.

PureWhiteWu · 2020-08-24T08:41:14Z

@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 · 2020-08-24T08:44:31Z

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

davecheney · 2020-08-24T08:45:42Z

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

PureWhiteWu · 2020-08-24T08:50:06Z

@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 · 2020-08-24T08:50:40Z

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

davecheney · 2020-08-24T08:54:08Z

@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 · 2020-08-24T08:56:59Z

@davecheney Is this enough?

PureWhiteWu · 2020-08-24T08:58:12Z

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

davecheney · 2020-08-24T09:01:34Z

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 · 2020-08-24T09:03:25Z

@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 · 2020-08-24T09:13:30Z

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

PureWhiteWu · 2020-08-24T09:19:36Z

@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 · 2020-08-24T09:22:33Z

@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 · 2020-08-24T09:30:13Z

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 · 2020-08-24T09:33:06Z

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 · 2020-08-24T09:33:59Z

@davecheney Thank you for your reproduction!

davecheney · 2020-08-24T09:34:29Z

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

PureWhiteWu · 2020-08-24T09:38:49Z

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

iand · 2020-08-24T09:48:44Z

@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 · 2020-08-24T09:55:35Z

git bisect points to 2e8dbae as @PureWhiteWu noted.

PureWhiteWu · 2020-08-24T10:00:36Z

@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 · 2020-08-24T10:01:31Z

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

davecheney · 2020-08-24T10:03:56Z

@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 · 2020-08-24T10:05:48Z

@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 · 2020-08-24T10:09:07Z

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 · 2020-08-24T10:15:04Z

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 · 2020-08-24T11:48:28Z

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

bcmills · 2020-08-24T18:30:16Z

@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 · 2020-08-24T18:30:27Z

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 · 2020-08-24T20:08:39Z

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

PureWhiteWu · 2020-08-25T01:25:18Z

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 · 2020-08-25T01:31:10Z

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 · 2020-08-25T01:38:44Z

@bcmills thanks for your reply!

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>

overdue fixing: golang/go#40999

gopherbot added the Documentation label Aug 24, 2020

PureWhiteWu added a commit to PureWhiteWu/go that referenced this issue Aug 24, 2020

doc: keys of sync.Map will never be deleted

0a09eed

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

doc: keys of sync.Map will never be deleted

7b211bb

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 mentioned this issue Aug 24, 2020

sync: document keys of sync.Map will never be deleted #41000

Closed

This comment has been minimized.

Sign in to view

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 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

ALTree added this to the Go1.16 milestone Aug 24, 2020

bcmills added the NeedsFix The path to resolution is known, but the work has not been done. label Aug 24, 2020

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

This was referenced Aug 24, 2020

sync: sync.Map keys will never be garbage collected [1.14 backport] #41010

Closed

sync: sync.Map keys will never be garbage collected [1.15 backport] #41011

Closed

bcmills mentioned this issue Aug 24, 2020

x/build/cmd/gopherbot: ignore Go versions in backport comments after the first period? #41012

Closed

gopherbot closed this as completed in 94953d3 Aug 24, 2020

This comment has been minimized.

Sign in to view

dustinxie mentioned this issue Aug 25, 2020

replace sync.Map iotexproject/iotex-core#2420

Closed

AZ-X added a commit to AZ-X/pique that referenced this issue Sep 1, 2020

remove unused type;

f51c1a0

overdue fixing: golang/go#40999

Sean-Der mentioned this issue Jan 3, 2021

memory overflow pion/webrtc#1622

Closed

golang locked and limited conversation to collaborators Aug 25, 2021

gopherbot added the FrozenDueToAge label Aug 25, 2021

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

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

Comments

PureWhiteWu commented Aug 24, 2020

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

Does this issue reproduce with the latest release?

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

What did you do?

This comment has been minimized.

gopherbot commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

davecheney commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

iand commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

davecheney commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

iand commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020

davecheney commented Aug 24, 2020

PureWhiteWu commented Aug 24, 2020 • edited

PureWhiteWu commented Aug 24, 2020

davecheney commented Aug 24, 2020

gopherbot commented Aug 24, 2020

bcmills commented Aug 24, 2020

gopherbot commented Aug 24, 2020

gopherbot commented Aug 24, 2020

PureWhiteWu commented Aug 25, 2020 • edited

bcmills commented Aug 25, 2020 • edited

PureWhiteWu commented Aug 25, 2020

This comment has been minimized.

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

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

PureWhiteWu commented Aug 24, 2020 •

edited

PureWhiteWu commented Aug 25, 2020 •

edited

bcmills commented Aug 25, 2020 •

edited