blob: a00c88398e5397328af26d96c1b814862cf719c8 [file] [log] [blame]
Takahiro Suzuki241c10e2020-12-17 20:17:57 +09001// 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
7package gopacket
8
9import (
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.
27const 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.
32type Endpoint struct {
33 typ EndpointType
34 len int
35 raw [MaxEndpointSize]byte
36}
37
38// EndpointType returns the endpoint type associated with this endpoint.
39func (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.
43func (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 lexicographically.
53func (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/.
60func 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
69const fnvBasis = 14695981039346656037
70const 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.
78func (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.
89func 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.
100type 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.
110type EndpointType int64
111
112var 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.
117func 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
126func (e EndpointType) String() string {
127 if t, ok := endpointTypes[e]; ok {
128 return t.Name
129 }
130 return strconv.Itoa(int(e))
131}
132
133func (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.
142type 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.
151func 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.
167func (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"
178func (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.
184func (f Flow) EndpointType() EndpointType {
185 return f.typ
186}
187
188// Endpoints returns the two Endpoints for this flow.
189func (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.
194func (f Flow) Src() (src Endpoint) {
195 src, _ = f.Endpoints()
196 return
197}
198
199// Dst returns the destination Endpoint for this flow.
200func (f Flow) Dst() (dst Endpoint) {
201 _, dst = f.Endpoints()
202 return
203}
204
205// Reverse returns a new flow with endpoints reversed.
206func (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.
214func 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.
228var 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.
233var InvalidEndpoint = NewEndpoint(EndpointInvalid, nil)
234
235// InvalidFlow is a singleton Flow of type EndpointInvalid.
236var InvalidFlow = NewFlow(EndpointInvalid, nil, nil)