common

Documentation

Overview

Hopper uses the implementation from the following bloom Library for mumur hash: https://github.com/bits-and-blooms/bloom. We require this because the default implementation of bloomfilter interface doesn't fit the exact requirments needed by Hopper. TLDR; the hash needs to sometimes be computed on worker nodes.

The bloom library relied on the excellent murmur library by Sébastien Paolacci. Unfortunately, it involved some heap allocation. We want to avoid any heap allocation whatsoever in the hashing process. To preserve backward compatibility, we roll our own hashing functions. They are designed to be strictly equivalent to Paolacci's implementation.

License on original code:

Copyright 2013, Sébastien Paolacci.

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

• Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
• Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
• Neither the name of the library nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

• type BFHash
  • func BloomHash(data []byte) BFHash
• type Digest128
  • func (d *Digest128) Sum128(pad_tail bool, length uint, tail []byte) (h1, h2 uint64)
  • func (d *Digest128) Sum256(data []byte) (hash1, hash2, hash3, hash4 uint64)
• type FTask
• type FTaskArgs
• type FTaskID
  • func Hash(b []byte) FTaskID
• type SeedInfo
• type Stats
• type UpdateFTask
• type UpdateReply

Types

type BFHash

type BFHash [4]uint64

func BloomHash

func BloomHash(data []byte) BFHash

baseHashes returns the four hash values of data that are used to create k hashes

type Digest128

type Digest128 struct {
	// contains filtered or unexported fields
}

digest128 represents a partial evaluation of a 128 bites hash.

func (*Digest128) Sum128

func (d *Digest128) Sum128(pad_tail bool, length uint, tail []byte) (h1, h2 uint64)

sum128 computers two 64-bit hash value. It is assumed that bmix was first called on the data to process complete blocks of 16 bytes. The 'tail' is a slice representing the 'tail' (leftover elements, fewer than 16). If pad_tail is true, we make it seem like there is an extra element with value 1 appended to the tail. The length parameter represents the full length of the data (including the blocks of 16 bytes, and, if pad_tail is true, an extra byte).

func (*Digest128) Sum256

func (d *Digest128) Sum256(data []byte) (hash1, hash2, hash3, hash4 uint64)

sum256 will compute 4 64-bit hash values from the input. It is designed to never allocate memory on the heap. So it works without any byte buffer whatsoever. It is designed to be strictly equivalent to

			a1 := []byte{1}
         hasher := murmur3.New128()
         hasher.Write(data) // #nosec
         v1, v2 := hasher.Sum128()
         hasher.Write(a1) // #nosec
         v3, v4 := hasher.Sum128()

See TestHashRandom.

type FTask

type FTask struct {
	Id   FTaskID
	Seed []byte
	Die  bool
}

type FTaskArgs

type FTaskArgs struct {
}

type FTaskID

type FTaskID uint64

func Hash

func Hash(b []byte) FTaskID

type SeedInfo

type SeedInfo struct {
	NodeId   uint64
	Id       FTaskID
	Bytes    []byte
	CovHash  BFHash
	CovEdges uint64
	Crash    bool
}

type Stats

type Stats struct {
	Its           uint64
	Port          int
	Havoc         uint64
	CrashN        uint64
	SeedsN        uint64
	MaxCov        uint64
	UniqueCrashes int
	UniquePaths   uint64
	Nodes         int
}

type UpdateFTask

type UpdateFTask struct {
	NodeId   uint64
	Ok       bool
	Id       FTaskID
	CovHash  BFHash
	CovEdges uint64
	Crash    bool
	CrashMsg string
}

type UpdateReply

type UpdateReply struct {
	Log bool
}