Skip to content

fix: return trie if child is nil during compact to avoid nil-pointer panic#42

Merged
tchap merged 2 commits intotchap:masterfrom
AtakanPehlivanoglu:bugfix/child-head-nil-protection
Jul 1, 2025
Merged

fix: return trie if child is nil during compact to avoid nil-pointer panic#42
tchap merged 2 commits intotchap:masterfrom
AtakanPehlivanoglu:bugfix/child-head-nil-protection

Conversation

@AtakanPehlivanoglu
Copy link
Copy Markdown
Contributor

@AtakanPehlivanoglu AtakanPehlivanoglu commented Jun 19, 2025

Issue link

#41

@tchap
Copy link
Copy Markdown
Owner

tchap commented Jun 23, 2025

Hi @AtakanPehlivanoglu , thanks for your contribution. Can you add a test that panics on the current branch, but is fixed by our change? Thanks.

@AtakanPehlivanoglu
Copy link
Copy Markdown
Contributor Author

AtakanPehlivanoglu commented Jun 25, 2025

Hello @tchap,

I have added a simple unit test to prove the mitigation and show how this problem can happen:

1. Test Run Without Mitigation

=== RUN   TestTrie_compactChildrenHeadIsNil
=== RUN   TestTrie_compactChildrenHeadIsNil/children_head_is_nil
--- FAIL: TestTrie_compactChildrenHeadIsNil/children_head_is_nil (0.00s)

--- FAIL: TestTrie_compactChildrenHeadIsNil (0.00s)
panic: runtime error: invalid memory address or nil pointer dereference [recovered]
	panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x18 pc=0x1049d0e58]

goroutine 19 [running]:
testing.tRunner.func1.2({0x104a2f000, 0x104b2fbd0})
	/Users/atakan.pehlivanoglu/go/pkg/mod/golang.org/[email protected]/src/testing/testing.go:1632 +0x1bc
testing.tRunner.func1()
	/Users/atakan.pehlivanoglu/go/pkg/mod/golang.org/[email protected]/src/testing/testing.go:1635 +0x334
panic({0x104a2f000?, 0x104b2fbd0?})
	/Users/atakan.pehlivanoglu/go/pkg/mod/golang.org/[email protected]/src/runtime/panic.go:791 +0x124
github.com/tchap/go-patricia/v2/patricia.(*Trie).compact(0x14000132140)
	/Users/atakan.pehlivanoglu/Documents/Bitbucket/go-patricia/patricia/patricia.go:468 +0x58
github.com/tchap/go-patricia/v2/patricia.TestTrie_compactChildrenHeadIsNil.func1(0x1400011a9c0)
	/Users/atakan.pehlivanoglu/Documents/Bitbucket/go-patricia/patricia/patricia_sparse_test.go:642 +0x50
testing.tRunner(0x1400011a9c0, 0x104a51990)
	/Users/atakan.pehlivanoglu/go/pkg/mod/golang.org/[email protected]/src/testing/testing.go:1690 +0xe4
created by testing.(*T).Run in goroutine 18
	/Users/atakan.pehlivanoglu/go/pkg/mod/golang.org/[email protected]/src/testing/testing.go:1743 +0x314

Process finished with the exit code 1

2. Test Run With Mitigation


=== RUN   TestTrie_compactChildrenHeadIsNil
=== RUN   TestTrie_compactChildrenHeadIsNil/children_head_is_nil
--- PASS: TestTrie_compactChildrenHeadIsNil/children_head_is_nil (0.00s)
--- PASS: TestTrie_compactChildrenHeadIsNil (0.00s)
PASS

Process finished with the exit code 0

@tchap
Copy link
Copy Markdown
Owner

tchap commented Jun 25, 2025

Yeah, but I want to see a test using the public API. Surely you can break it using private methods. In reality I don't see how you would end up calling children.add(nil).

@AtakanPehlivanoglu
Copy link
Copy Markdown
Contributor Author

AtakanPehlivanoglu commented Jun 25, 2025

Totally agree that this is not reproducible with using the Public API but in our use case, this happens probably due to race condition and it rarely happens like once in a month.
We have all the locks in place to prevent race conditions but we really don't have a time to put '-race' flag or debug in production env because it's quite complicated Trie structure that we have.
Guard that I proposed is a good mitigation and will prevent restarts happening in our code whilst we investigate the root cause.
I would highly appreciate if that guard won't cause any breaking changes or concerns for you.

Thank you

@tchap
Copy link
Copy Markdown
Owner

tchap commented Jul 1, 2025

Normally I wouldn't merge this as I still don't understand how this is happening to you, but I don't have time to dig into this deeper, so I will merge it.

@tchap tchap merged commit 8c5d7fa into tchap:master Jul 1, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@AtakanPehlivanoglu @tchap