vendor/github.com/google/gopacket/flows.go

   1 // Copyright 2012 Google, Inc. All rights reserved.
   2 //
   3 // Use of this source code is governed by a BSD-style license
   4 // that can be found in the LICENSE file in the root of the source
   5 // tree.
   6
   7 package gopacket
   8
   9 import (
  10         "bytes"
  11         "fmt"
  12         "strconv"
  13 )
  14
  15 // MaxEndpointSize determines the maximum size in bytes of an endpoint address.
  16 //
  17 // Endpoints/Flows have a problem:  They need to be hashable.  Therefore, they
  18 // can't use a byte slice.  The two obvious choices are to use a string or a
  19 // byte array.  Strings work great, but string creation requires memory
  20 // allocation, which can be slow.  Arrays work great, but have a fixed size.  We
  21 // originally used the former, now we've switched to the latter.  Use of a fixed
  22 // byte-array doubles the speed of constructing a flow (due to not needing to
  23 // allocate).  This is a huge increase... too much for us to pass up.
  24 //
  25 // The end result of this, though, is that an endpoint/flow can't be created
  26 // using more than MaxEndpointSize bytes per address.
  27 const MaxEndpointSize = 16
  28
  29 // Endpoint is the set of bytes used to address packets at various layers.
  30 // See LinkLayer, NetworkLayer, and TransportLayer specifications.
  31 // Endpoints are usable as map keys.
  32 type Endpoint struct {
  33         typ EndpointType
  34         len int
  35         raw [MaxEndpointSize]byte
  36 }
  37
  38 // EndpointType returns the endpoint type associated with this endpoint.
  39 func (a Endpoint) EndpointType() EndpointType { return a.typ }
  40
  41 // Raw returns the raw bytes of this endpoint.  These aren't human-readable
  42 // most of the time, but they are faster than calling String.
  43 func (a Endpoint) Raw() []byte { return a.raw[:a.len] }
  44
  45 // LessThan provides a stable ordering for all endpoints.  It sorts first based
  46 // on the EndpointType of an endpoint, then based on the raw bytes of that
  47 // endpoint.
  48 //
  49 // For some endpoints, the actual comparison may not make sense, however this
  50 // ordering does provide useful information for most Endpoint types.
  51 // Ordering is based first on endpoint type, then on raw endpoint bytes.
  52 // Endpoint bytes are sorted lexigraphically.
  53 func (a Endpoint) LessThan(b Endpoint) bool {
  54         return a.typ < b.typ || (a.typ == b.typ && bytes.Compare(a.raw[:a.len], b.raw[:b.len]) < 0)
  55 }
  56
  57 // fnvHash is used by our FastHash functions, and implements the FNV hash
  58 // created by Glenn Fowler, Landon Curt Noll, and Phong Vo.
  59 // See http://isthe.com/chongo/tech/comp/fnv/.
  60 func fnvHash(s []byte) (h uint64) {
  61         h = fnvBasis
  62         for i := 0; i < len(s); i++ {
  63                 h ^= uint64(s[i])
  64                 h *= fnvPrime
  65         }
  66         return
  67 }
  68
  69 const fnvBasis = 14695981039346656037
  70 const fnvPrime = 1099511628211
  71
  72 // FastHash provides a quick hashing function for an endpoint, useful if you'd
  73 // like to split up endpoints by modulos or other load-balancing techniques.
  74 // It uses a variant of Fowler-Noll-Vo hashing.
  75 //
  76 // The output of FastHash is not guaranteed to remain the same through future
  77 // code revisions, so should not be used to key values in persistent storage.
  78 func (a Endpoint) FastHash() (h uint64) {
  79         h = fnvHash(a.raw[:a.len])
  80         h ^= uint64(a.typ)
  81         h *= fnvPrime
  82         return
  83 }
  84
  85 // NewEndpoint creates a new Endpoint object.
  86 //
  87 // The size of raw must be less than MaxEndpointSize, otherwise this function
  88 // will panic.
  89 func NewEndpoint(typ EndpointType, raw []byte) (e Endpoint) {
  90         e.len = len(raw)
  91         if e.len > MaxEndpointSize {
  92                 panic("raw byte length greater than MaxEndpointSize")
  93         }
  94         e.typ = typ
  95         copy(e.raw[:], raw)
  96         return
  97 }
  98
  99 // EndpointTypeMetadata is used to register a new endpoint type.
 100 type EndpointTypeMetadata struct {
 101         // Name is the string returned by an EndpointType's String function.
 102         Name string
 103         // Formatter is called from an Endpoint's String function to format the raw
 104         // bytes in an Endpoint into a human-readable string.
 105         Formatter func([]byte) string
 106 }
 107
 108 // EndpointType is the type of a gopacket Endpoint.  This type determines how
 109 // the bytes stored in the endpoint should be interpreted.
 110 type EndpointType int64
 111
 112 var endpointTypes = map[EndpointType]EndpointTypeMetadata{}
 113
 114 // RegisterEndpointType creates a new EndpointType and registers it globally.
 115 // It MUST be passed a unique number, or it will panic.  Numbers 0-999 are
 116 // reserved for gopacket's use.
 117 func RegisterEndpointType(num int, meta EndpointTypeMetadata) EndpointType {
 118         t := EndpointType(num)
 119         if _, ok := endpointTypes[t]; ok {
 120                 panic("Endpoint type number already in use")
 121         }
 122         endpointTypes[t] = meta
 123         return t
 124 }
 125
 126 func (e EndpointType) String() string {
 127         if t, ok := endpointTypes[e]; ok {
 128                 return t.Name
 129         }
 130         return strconv.Itoa(int(e))
 131 }
 132
 133 func (a Endpoint) String() string {
 134         if t, ok := endpointTypes[a.typ]; ok && t.Formatter != nil {
 135                 return t.Formatter(a.raw[:a.len])
 136         }
 137         return fmt.Sprintf("%v:%v", a.typ, a.raw)
 138 }
 139
 140 // Flow represents the direction of traffic for a packet layer, as a source and destination Endpoint.
 141 // Flows are usable as map keys.
 142 type Flow struct {
 143         typ        EndpointType
 144         slen, dlen int
 145         src, dst   [MaxEndpointSize]byte
 146 }
 147
 148 // FlowFromEndpoints creates a new flow by pasting together two endpoints.
 149 // The endpoints must have the same EndpointType, or this function will return
 150 // an error.
 151 func FlowFromEndpoints(src, dst Endpoint) (_ Flow, err error) {
 152         if src.typ != dst.typ {
 153                 err = fmt.Errorf("Mismatched endpoint types: %v->%v", src.typ, dst.typ)
 154                 return
 155         }
 156         return Flow{src.typ, src.len, dst.len, src.raw, dst.raw}, nil
 157 }
 158
 159 // FastHash provides a quick hashing function for a flow, useful if you'd
 160 // like to split up flows by modulos or other load-balancing techniques.
 161 // It uses a variant of Fowler-Noll-Vo hashing, and is guaranteed to collide
 162 // with its reverse flow.  IE: the flow A->B will have the same hash as the flow
 163 // B->A.
 164 //
 165 // The output of FastHash is not guaranteed to remain the same through future
 166 // code revisions, so should not be used to key values in persistent storage.
 167 func (f Flow) FastHash() (h uint64) {
 168         // This combination must be commutative.  We don't use ^, since that would
 169         // give the same hash for all A->A flows.
 170         h = fnvHash(f.src[:f.slen]) + fnvHash(f.dst[:f.dlen])
 171         h ^= uint64(f.typ)
 172         h *= fnvPrime
 173         return
 174 }
 175
 176 // String returns a human-readable representation of this flow, in the form
 177 // "Src->Dst"
 178 func (f Flow) String() string {
 179         s, d := f.Endpoints()
 180         return fmt.Sprintf("%v->%v", s, d)
 181 }
 182
 183 // EndpointType returns the EndpointType for this Flow.
 184 func (f Flow) EndpointType() EndpointType {
 185         return f.typ
 186 }
 187
 188 // Endpoints returns the two Endpoints for this flow.
 189 func (f Flow) Endpoints() (src, dst Endpoint) {
 190         return Endpoint{f.typ, f.slen, f.src}, Endpoint{f.typ, f.dlen, f.dst}
 191 }
 192
 193 // Src returns the source Endpoint for this flow.
 194 func (f Flow) Src() (src Endpoint) {
 195         src, _ = f.Endpoints()
 196         return
 197 }
 198
 199 // Dst returns the destination Endpoint for this flow.
 200 func (f Flow) Dst() (dst Endpoint) {
 201         _, dst = f.Endpoints()
 202         return
 203 }
 204
 205 // Reverse returns a new flow with endpoints reversed.
 206 func (f Flow) Reverse() Flow {
 207         return Flow{f.typ, f.dlen, f.slen, f.dst, f.src}
 208 }
 209
 210 // NewFlow creates a new flow.
 211 //
 212 // src and dst must have length <= MaxEndpointSize, otherwise NewFlow will
 213 // panic.
 214 func NewFlow(t EndpointType, src, dst []byte) (f Flow) {
 215         f.slen = len(src)
 216         f.dlen = len(dst)
 217         if f.slen > MaxEndpointSize || f.dlen > MaxEndpointSize {
 218                 panic("flow raw byte length greater than MaxEndpointSize")
 219         }
 220         f.typ = t
 221         copy(f.src[:], src)
 222         copy(f.dst[:], dst)
 223         return
 224 }
 225
 226 // EndpointInvalid is an endpoint type used for invalid endpoints, IE endpoints
 227 // that are specified incorrectly during creation.
 228 var EndpointInvalid = RegisterEndpointType(0, EndpointTypeMetadata{Name: "invalid", Formatter: func(b []byte) string {
 229         return fmt.Sprintf("%v", b)
 230 }})
 231
 232 // InvalidEndpoint is a singleton Endpoint of type EndpointInvalid.
 233 var InvalidEndpoint = NewEndpoint(EndpointInvalid, nil)
 234
 235 // InvalidFlow is a singleton Flow of type EndpointInvalid.
 236 var InvalidFlow = NewFlow(EndpointInvalid, nil, nil)