Fixes https://github.com/tendermint/tmlibs/issues/145
Fixes https://github.com/tendermint/tmlibs/issues/146
The code in here has been fragile when it comes to nil
but these edge cases were never tested, although they've
showed up in the wild and were only noticed because
the reporter actually read the logs otherwise
we'd have never known.
This changes covers some of these cases and adds some tests.
Fixes https://github.com/tendermint/tendermint/issues/1189
For every TxEventBuffer.Flush() invoking, we were invoking
a:
b.events = make([]EventDataTx, 0, b.capacity)
whose intention is to innocently clear the events slice but
maintain the underlying capacity.
However, unfortunately this is memory and garbage collection intensive
which is linear in the number of events added. If an attack had access
to our code somehow, invoking .Flush() in tight loops would be a sure
way to cause huge GC pressure, and say if they added about 1e9
events maliciously, every Flush() would take at least 3.2seconds
which is enough to now control our application.
The new using of the capacity preserving slice clearing idiom
takes a constant time regardless of the number of elements with zero
allocations so we are killing many birds with one stone i.e
b.events = b.events[:0]
For benchmarking results, please see
https://gist.github.com/odeke-em/532c14ab67d71c9c0b95518a7a526058
for a reference on how things can get out of hand easily.
* GetByHeight will now switch to using binary search once
we have >=50 items.
* Feedback from @ebuchman to catch a missed spot where
we forgot about lazy sorting that the original code
assumed would always have sorted commits by height.
Added a lazy sorting routine here too.
A test as well to ensure that we always get the properly
sorted and last value.
Addressing PR review requests from @melekes and @ebuchman to
add a test that checks that the heights returned from both are
the same thus providing a perceptible equivalence of the code
linear range search vs binary range search code.
Updates #1021
* Implement a GetHeightBinarySearch method that looks for
the height using the binary search algorithm guaranteeing
worst case iteration time of O(log2(n))
whereas
worst case iteration time of O(n) for the current linear search
So if n we had 500 commits stored by height and sorted, to
trigger the worst case scenario for each, pass in
the most negative height you can find e.g. -1
Linear search: 500 iterations
Binary search: 9 iterations
with n=1000, qHeight = -1
Linear search: 1000 iterations
Binary search: 10 iterations
with n=1e6, qHeight = -1
Linear search: 1e6 iterations
Binary search: 20 iterations
Of course there are realistic expectations e.g. a max of
commits that may be saved so linear search might be useful
for very small size set because it has less preparing overhead
and only ~2 types of comparisons, but nonetheless binary search
shines as soon as we start to hit say 50 commits to search from
as you can see below:
```shell
$ go test -v -run=^$ -bench=MemStore
goos: darwin
goarch: amd64
pkg: github.com/tendermint/tendermint/lite
BenchmarkMemStoreProviderGetByHeightLinearSearch5-4 300000 6491 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch50-4 200000 12064 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch100-4 50000 32987 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch500-4 5000 395521 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch1000-4 500 2940724 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch5-4 300000 6281 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch50-4 200000 10117 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch100-4 100000 18447 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch500-4 20000 89029 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch1000-4 5000 265719 ns/op 1600 B/op 15 allocs/op
PASS
ok github.com/tendermint/tendermint/lite 86.614s
$ go test -v -run=^$ -bench=MemStore
goos: darwin
goarch: amd64
pkg: github.com/tendermint/tendermint/lite
BenchmarkMemStoreProviderGetByHeightLinearSearch5-4 300000 6779 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch50-4 100000 12980 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch100-4 30000 43598 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch500-4 5000 377462 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch1000-4 500 3278122 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch5-4 300000 7084 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch50-4 200000 9852 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch100-4 100000 19020 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch500-4 20000 99463 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch1000-4 5000 259293 ns/op 1600 B/op 15 allocs/op
PASS
ok github.com/tendermint/tendermint/lite 86.204s
```
which gives
```shell
$ benchstat old.txt new.txt
name old time/op new time/op delta
MemStoreProviderGetByHeight5-4 6.63µs ± 2% 6.68µs ± 6% ~ (p=1.000 n=2+2)
MemStoreProviderGetByHeight50-4 12.5µs ± 4% 10.0µs ± 1% ~ (p=0.333 n=2+2)
MemStoreProviderGetByHeight100-4 38.3µs ±14% 18.7µs ± 2% ~ (p=0.333 n=2+2)
MemStoreProviderGetByHeight500-4 386µs ± 2% 94µs ± 6% ~ (p=0.333 n=2+2)
MemStoreProviderGetByHeight1000-4 3.11ms ± 5% 0.26ms ± 1% ~ (p=0.333 n=2+2)
```
If need be we can make a hybrid algorithm that switches between the
linear and binary search depending on the number of items.
This is reminiscent of Python's TimSort algorithm.
The previous doc seemed misleading and was out of date i.e.
RandHex(24)
not
CRandHex.
Anyways provide a doc of what the function does in relation to
the length of digits of the hex value returned i.e.
floor(numDigits / 2) * 2
so the even lowest number
e.g:
* len(CRandHex(5)) = 4
* len(CRandHex(4)) = 4
Lesson articulated by @jaekwon on why we need 80 bits
of entropy at least before we can think of cryptographic
safety. math/rand's seed is a max of 64 bits so can never
be cryptographically secure.
Also added some benchmarks for RandBytes
+ *FSDB.HasKey now uses common.FileExists to test for file existence
+ IsKeyInDomain takes key as a []byte slice instead of as a string
to avoid extraneous []byte<-->string conversions for start and end
+ Iterator.Close() instead of Iterator.Release()
+ withDB helper to encapsulate DB creation, deferred cleanups
so that for loops can use opened DBs and discard them ASAP
Addressing accepted changes from review with @jaekwon
Fixes https://github.com/tendermint/tmlibs/issues/99
Updates https://github.com/tendermint/tendermint/issues/973
Removed usages of math/rand.DefaultSource in favour of our
own source that's seeded with a completely random source
and is safe for use in concurrent in multiple goroutines.
Also extend some functionality that the stdlib exposes such as
* RandPerm
* RandIntn
* RandInt31
* RandInt63
Also added an integration test whose purpose is to be run as
a consistency check to ensure that our results never repeat
hence that our internal PRNG is uniquely seeded each time.
This integration test can be triggered by setting environment variable:
`TENDERMINT_INTEGRATION_TESTS=true`
for example
```shell
TENDERMINT_INTEGRATION_TESTS=true go test
```
* Build tags need to come before the package name
and have at least a blank line, between them and
the package, please see
https://golang.org/pkg/go/build/#hdr-Build_Constraints
* fmt.Println doesn't take formatting verbs
* Fix a missing formatting argument to fmt.Printf
Can now run batch which can be tested by:
```shell
echo -e "echo foo\necho blue" | abci-cli batch
```
giving
```shell
I[12-12|07:55:55.513] Starting socketClient
module=abci-client impl=socketClient
-> code: OK
-> data: foo
-> data.hex: 0x666F6F
-> code: OK
-> data: blue
-> data.hex: 0x626C7565
```
Use the single client connection at startup time
for sending over commands instead of shelling out
for every command.
This code fixes the regression from
https://github.com/tendermint/abci/pull/117
which instead used "os/exec".Command with:
"abci-cli <the_command> [args...]"
The purpose of this code is to restore us
back to the state after cobra replace urlfave/cli.
There is still a bit of work to implement Batch
itself, but that should be simpler as a focused
command.
Fixes#133
Ensure that the types in result.go implement both
json.Marshaler and json.Unmarshaler
and thus avoid any accidental deletions of their respective
methods which would then cause surprises at runtime.
Add tests to test store, to the fullest reasonable extent for
paths that can taken by input arguments altering internal behavior,
as well as by mutating content in the DB.
Updates https://github.com/tendermint/tmlibs/issues/81
No longer using tmlibs/process.Process as we deemed
it racy and would incur a maintenance cost yet not
used anywhere else but in these tests and not in actual
code.
Fixes https://github.com/tendermint/tendermint/issues/875
Ensure that every DialSeeds call uses a new PRNG seeded from
tendermint/tmlibs/common.RandInt which internally uses
crypto/rand to seed its source.
Updates https://github.com/tendermint/tendermint/issues/850
My security alarms falsely blarred when I skimmed and noticed
keys being compared with `==`, without the proper context
so I mistakenly filed an issue, yet the purpose of that
comparison was to check if the local ephemeral public key
was just the least, sorted lexicographically.
Anyways, let's use the proper bytes.Equal check, to save future labor.
Fixes https://github.com/tendermint/tendermint/issues/851
Go1.9 and below's net.Pipe did not implement the SetDeadline
method so after commit
https://github.com/golang/go/commit/e2dd8ca946be884bb877e074a21727f1a685a706
this problem was exposed since now we check for errors.
To counter this problem, implement a simple composition for
net.Conn that always returns nil on SetDeadline instead of
tripping out.
Added build tags so that anyone using go1.10 when it is released
will be able to automatically use net.Pipe's net.Conns
Noticed while auditing the code that we aren't respecting
(*net.Conn) SetDeadline errors which return after
a connection has been killed and is simultaneously
being used.
For example given program, without SetDeadline error checks
```go
package main
import (
"log"
"net"
"time"
)
func main() {
conn, err := net.Dial("tcp", "tendermint.com:443")
if err != nil {
log.Fatal(err)
}
go func() {
<-time.After(400 * time.Millisecond)
conn.Close()
}()
for i := 0; i < 5; i++ {
if err := conn.SetDeadline(time.Now().Add(time.Duration(10 * time.Second))); err != nil {
log.Fatalf("set deadline #%d, err: %v", i, err)
}
log.Printf("Successfully set deadline #%d", i)
<-time.After(150 * time.Millisecond)
}
}
```
erraneously gives
```shell
2017/11/14 17:46:28 Successfully set deadline #0
2017/11/14 17:46:29 Successfully set deadline #1
2017/11/14 17:46:29 Successfully set deadline #2
2017/11/14 17:46:29 Successfully set deadline #3
2017/11/14 17:46:29 Successfully set deadline #4
```
However, if we properly fix it to respect that error with
```diff
--- wild.go 2017-11-14 17:44:38.000000000 -0700
+++ main.go 2017-11-14 17:45:40.000000000 -0700
@@ -16,7 +16,9 @@
conn.Close()
}()
for i := 0; i < 5; i++ {
- conn.SetDeadline(time.Now().Add(time.Duration(10 * time.Second)))
+ if err := conn.SetDeadline(time.Now().Add(time.Duration(10 *
time.Second))); err != nil {
+ log.Fatalf("set deadline #%d, err: %v", i, err)
+ }
log.Printf("Successfully set deadline #%d", i)
<-time.After(150 * time.Millisecond)
}
```
properly catches any problems and gives
```shell
$ go run main.go
2017/11/14 17:43:44 Successfully set deadline #0
2017/11/14 17:43:45 Successfully set deadline #1
2017/11/14 17:43:45 Successfully set deadline #2
2017/11/14 17:43:45 set deadline #3, err: set tcp 10.182.253.51:57395:
use of closed network connection
exit status 1
```
Just noticed while auditing the code in p2p/addrbook.go,
wg.Add(1) but no subsequent defer.
@jaekwon and I had a discussion offline and we agreed to
comment about why the code was that way and why
we shouldn't move the wg.Add(1) into .saveRoutine() because
if go a.saveRoutine() isn't started before anyone invokes
a.Wait(), then we'd have raced a.saveRoutine().
Follow up of PR https://github.com/tendermint/tendermint/pull/724
For https://github.com/tendermint/tendermint/issues/708
Reported initially in #708, this bug was reconfirmed
by the fuzzer.
This fix ensures that:
* if the user doesn't pass in `"id"` that we send them back
a message in an error telling them to send `"id"`. Previously
we let the handler return a 200 with nothing.
* passing in nil `params` doesn't crash
* not passing in `params` doesn't crash
* passing in non-JSON parseable data to `params` doesn't crash
Fixes https://github.com/tendermint/go-crypto/issues/43
Avoid susceptibility to timing/side channel attacks by ensuring
that private key and signature comparisons use
`subtle.ConstantTimeCompare`
instead of
`bytes.Equal`
* Updated code with feedback from @melekes, @ebuchman and @silasdavis.
* Added Makefile clause `release` to only run the test on seeing tag
`release` during releases i.e
```shell
make release
```
which will run the comprehensive and long integration-ish tests.
Fixes https://github.com/tendermint/tendermint/issues/751.
Adds jitter to our exponential backoff to mitigate a self DDOS
vector. The jitter is a randomly picked percentage of a second
whose purpose is to ensure that each exponential backoff retry
occurs within (1<<attempts) == 2**attempts, but with the delay
each client will have a random buffer time before it tries to
reconnect instead of all at once reconnections that might even
bring back the previous conditions that might have caused the
dial to the WSServer to have failed e.g
* Network outage
* File descriptor exhaustion
* False positives from firewalls
etc
Fixes https://github.com/tendermint/abci/issues/114.
Fix and test for StopForError deadlock due to accidental
Mutex misuse. The test should return instantenously if
StopForError works without erraneous contention, lest it regressed.
Fixes#671
Unexpose GenesisDoc and ChainID fields to avoid them being
serialized to the DB on every block write/state.Save()
A GenesisDoc can now be alternatively written to the state's
database, by serializing its JSON as a value of key "genesis-doc".
There are now accessors and a setter for these attributes:
- state.GenesisDoc() (*types.GenesisDoc, error)
- state.ChainID() (string, error)
- state.SetGenesisDoc(*types.GenesisDoc)
This is a breaking change since it changes how the state's
serialization and requires that if loading the GenesisDoc entirely
from the database, you'll need to set its value in the database
as the GenesisDoc's JSON marshaled bytes.
Updates https://github.com/tendermint/tendermint/issues/693
* Adjusted Heartbeat.Copy to return nil on
trying to copy a nil value instead of panicking.
* Also documented that WriteSignBytes panics
if the Heartbeat is nil.
Fixes#514
Replaces #540
If a peer requests a block with a height that we don't have
respond with a bcNoBlockResponseMessage.
However, according to the Tendermint spec, if all nodes are honest
this condition shouldn't occur, so this is a possible hint of an
dishonest node.
Fixes https://github.com/tendermint/tmlibs/issues/55
MemDB previously mistakenly set the actual DB pointer to nil
although that side effect is not visible to the outside world
since p is an identifier within the scope of just that function
call. However, @melekes and I had a discussion in which we
came to the conclusion that Close for an in-memory DB should
instead be a noop and not cause any data loss. See the
discussion on https://github.com/tendermint/tmlibs/pull/56.
Fixes#35
Updates https://github.com/tendermint/coding/issues/27
Started a doc.go file to provide an overview/high level
dive into the functionality of this repo.
Also added an example_test.go file in which we can
put end-to-end code examples/actual usage patterns
that can be copied and pasted and will always have to
compile when tests are run to ensure that we don't regress.
* Full test PeerSet and check its concurrent guarantees
* Improve the doc for PeerSet.Has and remove unnecessary
defer for a path that sets a variable, make it fast anyways.
* Parallelize PeerSet tests with t.Parallel()
* Document functions in peer_set.go more.
Currently IsDirEmpty returns true, err if it encounters
any error after trying to os.Open the directory.
I noticed this while studying the code and recalled a bug
from an earlier project in which doing the exact same thing
on code without permissions would trip out and falsely report
that the directory was empty.
Given demo.go in https://play.golang.org/p/vhTPU2RiCJ
* Demo:
```shell
$ mkdir -p sample-demo/1 && touch sample-demo/2
$ echo "1st round" && go run demo.go sample-demo
$ sudo chown root sample-demo && sudo chmod 0700 sample-demo
$ echo "2nd round" && go run demo.go sample-demo
```
That then prints out
```shell
1st round
original:: empty: false err: <nil>
updated:: empty: false err: <nil>
2nd round
original:: empty: true err: open data/: permission denied
updated:: empty: false err: open data/: permission denied
```
where in "2nd round", the original code falsely reports that
the directory is empty but that's a permission error.
I could write a code test for it, but that test requires me to change
users and switch to root as a Go user so no point in complicating our
tests, but otherwise it is a 1-to-1 translation between shell and Go.
Found common http utils that were being multiply duplicated across
many libraries and since am moving things in basecoin/unstable to
add for more functionality, it's better to put them in one
place.
Utilities and tests added:
- [X] FparseJSON
- [X] FparseAndValidateJSON
- [X] ParseRequestJSON
- [X] ParseAndValidateRequestJSON
- [X] WriteCode
- [X] WriteError
- [X] WriteSuccess
- [X] ErrorResponse
During review from @ethanfrey, made updates:
* Removed tt.want since it was a distraction/artifact that made
the reviewer think the tests weren't testing for both failed
and passed results.
* Added ErrorWithCode as WithCode is a common options pattern
in Go that could cause confusion:
ErrorWithCode(error, int) ErrorResponse
* Using json.NewDecoder(io.Reader) error instead of
ioutil.ReadAll(io.Reader) to slurp all the bytes.
* Added more test scenarios to achieve 100% coverage of http.go
Add a godoc reference to delegate indexing and references
to that service, thus keeping our library and usages upto date,
instead of relying on generated markdown that goes stale
especially for changing API signatures, and becomes tedious
where someone has to remember to always regenerate the README
markdown and then commit it.
Fixes#24
* Optimized ReverseBytes to:
a) Minimally allocate --> 60.0% reduction in the number of allocations
b) Only walk halfway the length of the string thus performing
byte swaps from left to right. Improves the performance as well.
Complexity is O(n/2) instead of O(n) which is still O(n) but
benchmarks show the new time is in deed 1/2 of the original time.
* Added unit tests and some common cases to ensure correctness.
* Benchmark shoot out results:
```shell
name old time/op new time/op delta
ReverseBytes-4 554ns ± 4% 242ns ± 3% -56.20% (p=0.000 n=10+10)
name old alloc/op new alloc/op delta
ReverseBytes-4 208B ± 0% 114B ± 0% -45.19% (p=0.000 n=10+10)
name old allocs/op new allocs/op delta
ReverseBytes-4 10.0 ± 0% 4.0 ± 0% -60.00% (p=0.000 n=10+10)
```
Emmanuel Odeke
