diff options
author | Felföldi Zsolt <zsfelfoldi@gmail.com> | 2018-08-15 04:44:46 +0800 |
---|---|---|
committer | Felix Lange <fjl@users.noreply.github.com> | 2018-08-15 04:44:46 +0800 |
commit | b2ddb1fcbf77771d0693ee5a00f8ae1cd4c0f87c (patch) | |
tree | cc70e50a0aa168afdda0a7737996686ca836621b /common/prque/sstack.go | |
parent | a1783d169732dd34aa8c7d68f411ce741c1a5015 (diff) | |
download | dexon-b2ddb1fcbf77771d0693ee5a00f8ae1cd4c0f87c.tar dexon-b2ddb1fcbf77771d0693ee5a00f8ae1cd4c0f87c.tar.gz dexon-b2ddb1fcbf77771d0693ee5a00f8ae1cd4c0f87c.tar.bz2 dexon-b2ddb1fcbf77771d0693ee5a00f8ae1cd4c0f87c.tar.lz dexon-b2ddb1fcbf77771d0693ee5a00f8ae1cd4c0f87c.tar.xz dexon-b2ddb1fcbf77771d0693ee5a00f8ae1cd4c0f87c.tar.zst dexon-b2ddb1fcbf77771d0693ee5a00f8ae1cd4c0f87c.zip |
les: implement client connection logic (#16899)
This PR implements les.freeClientPool. It also adds a simulated clock
in common/mclock, which enables time-sensitive tests to run quickly
and still produce accurate results, and package common/prque which is
a generalised variant of prque that enables removing elements other
than the top one from the queue.
les.freeClientPool implements a client database that limits the
connection time of each client and manages accepting/rejecting
incoming connections and even kicking out some connected clients. The
pool calculates recent usage time for each known client (a value that
increases linearly when the client is connected and decreases
exponentially when not connected). Clients with lower recent usage are
preferred, unknown nodes have the highest priority. Already connected
nodes receive a small bias in their favor in order to avoid accepting
and instantly kicking out clients.
Note: the pool can use any string for client identification. Using
signature keys for that purpose would not make sense when being known
has a negative value for the client. Currently the LES protocol
manager uses IP addresses (without port address) to identify clients.
Diffstat (limited to 'common/prque/sstack.go')
-rwxr-xr-x | common/prque/sstack.go | 106 |
1 files changed, 106 insertions, 0 deletions
diff --git a/common/prque/sstack.go b/common/prque/sstack.go new file mode 100755 index 000000000..4875dae99 --- /dev/null +++ b/common/prque/sstack.go @@ -0,0 +1,106 @@ +// This is a duplicated and slightly modified version of "gopkg.in/karalabe/cookiejar.v2/collections/prque". + +package prque + +// The size of a block of data +const blockSize = 4096 + +// A prioritized item in the sorted stack. +// +// Note: priorities can "wrap around" the int64 range, a comes before b if (a.priority - b.priority) > 0. +// The difference between the lowest and highest priorities in the queue at any point should be less than 2^63. +type item struct { + value interface{} + priority int64 +} + +// setIndexCallback is called when the element is moved to a new index. +// Providing setIndexCallback is optional, it is needed only if the application needs +// to delete elements other than the top one. +type setIndexCallback func(a interface{}, i int) + +// Internal sortable stack data structure. Implements the Push and Pop ops for +// the stack (heap) functionality and the Len, Less and Swap methods for the +// sortability requirements of the heaps. +type sstack struct { + setIndex setIndexCallback + size int + capacity int + offset int + + blocks [][]*item + active []*item +} + +// Creates a new, empty stack. +func newSstack(setIndex setIndexCallback) *sstack { + result := new(sstack) + result.setIndex = setIndex + result.active = make([]*item, blockSize) + result.blocks = [][]*item{result.active} + result.capacity = blockSize + return result +} + +// Pushes a value onto the stack, expanding it if necessary. Required by +// heap.Interface. +func (s *sstack) Push(data interface{}) { + if s.size == s.capacity { + s.active = make([]*item, blockSize) + s.blocks = append(s.blocks, s.active) + s.capacity += blockSize + s.offset = 0 + } else if s.offset == blockSize { + s.active = s.blocks[s.size/blockSize] + s.offset = 0 + } + if s.setIndex != nil { + s.setIndex(data.(*item).value, s.size) + } + s.active[s.offset] = data.(*item) + s.offset++ + s.size++ +} + +// Pops a value off the stack and returns it. Currently no shrinking is done. +// Required by heap.Interface. +func (s *sstack) Pop() (res interface{}) { + s.size-- + s.offset-- + if s.offset < 0 { + s.offset = blockSize - 1 + s.active = s.blocks[s.size/blockSize] + } + res, s.active[s.offset] = s.active[s.offset], nil + if s.setIndex != nil { + s.setIndex(res.(*item).value, -1) + } + return +} + +// Returns the length of the stack. Required by sort.Interface. +func (s *sstack) Len() int { + return s.size +} + +// Compares the priority of two elements of the stack (higher is first). +// Required by sort.Interface. +func (s *sstack) Less(i, j int) bool { + return (s.blocks[i/blockSize][i%blockSize].priority - s.blocks[j/blockSize][j%blockSize].priority) > 0 +} + +// Swaps two elements in the stack. Required by sort.Interface. +func (s *sstack) Swap(i, j int) { + ib, io, jb, jo := i/blockSize, i%blockSize, j/blockSize, j%blockSize + a, b := s.blocks[jb][jo], s.blocks[ib][io] + if s.setIndex != nil { + s.setIndex(a.value, i) + s.setIndex(b.value, j) + } + s.blocks[ib][io], s.blocks[jb][jo] = a, b +} + +// Resets the stack, effectively clearing its contents. +func (s *sstack) Reset() { + *s = *newSstack(s.setIndex) +} |