curve.go

Documentation: google.golang.org/grpc/benchmark/stats

     1  /*
     2   *
     3   * Copyright 2019 gRPC authors.
     4   *
     5   * Licensed under the Apache License, Version 2.0 (the "License");
     6   * you may not use this file except in compliance with the License.
     7   * You may obtain a copy of the License at
     8   *
     9   *     http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   *
    17   */
    18  
    19  package stats
    20  
    21  import (
    22  	"crypto/sha256"
    23  	"encoding/csv"
    24  	"encoding/hex"
    25  	"fmt"
    26  	"math"
    27  	"math/rand"
    28  	"os"
    29  	"sort"
    30  	"strconv"
    31  )
    32  
    33  // payloadCurveRange represents a line within a payload curve CSV file.
    34  type payloadCurveRange struct {
    35  	from, to int32
    36  	weight   float64
    37  }
    38  
    39  // newPayloadCurveRange receives a line from a payload curve CSV file and
    40  // returns a *payloadCurveRange if the values are acceptable.
    41  func newPayloadCurveRange(line []string) (*payloadCurveRange, error) {
    42  	if len(line) != 3 {
    43  		return nil, fmt.Errorf("invalid number of entries in line %v (expected 3)", line)
    44  	}
    45  
    46  	var from, to int64
    47  	var weight float64
    48  	var err error
    49  	if from, err = strconv.ParseInt(line[0], 10, 32); err != nil {
    50  		return nil, err
    51  	}
    52  	if from <= 0 {
    53  		return nil, fmt.Errorf("line %v: field (%d) must be in (0, %d]", line, from, math.MaxInt32)
    54  	}
    55  	if to, err = strconv.ParseInt(line[1], 10, 32); err != nil {
    56  		return nil, err
    57  	}
    58  	if to <= 0 {
    59  		return nil, fmt.Errorf("line %v: field %d must be in (0, %d]", line, to, math.MaxInt32)
    60  	}
    61  	if from > to {
    62  		return nil, fmt.Errorf("line %v: from (%d) > to (%d)", line, from, to)
    63  	}
    64  	if weight, err = strconv.ParseFloat(line[2], 64); err != nil {
    65  		return nil, err
    66  	}
    67  	return &payloadCurveRange{from: int32(from), to: int32(to), weight: weight}, nil
    68  }
    69  
    70  // chooseRandom picks a payload size (in bytes) for a particular range. This is
    71  // done with a uniform distribution.
    72  func (pcr *payloadCurveRange) chooseRandom() int {
    73  	if pcr.from == pcr.to { // fast path
    74  		return int(pcr.from)
    75  	}
    76  
    77  	return int(rand.Int31n(pcr.to-pcr.from+1) + pcr.from)
    78  }
    79  
    80  // sha256file is a helper function that returns a hex string matching the
    81  // SHA-256 sum of the input file.
    82  func sha256file(file string) (string, error) {
    83  	data, err := os.ReadFile(file)
    84  	if err != nil {
    85  		return "", err
    86  	}
    87  	sum := sha256.Sum256(data)
    88  	return hex.EncodeToString(sum[:]), nil
    89  }
    90  
    91  // PayloadCurve is an internal representation of a weighted random distribution
    92  // CSV file. Once a *PayloadCurve is created with NewPayloadCurve, the
    93  // ChooseRandom function should be called to generate random payload sizes.
    94  type PayloadCurve struct {
    95  	pcrs []*payloadCurveRange
    96  	// Sha256 must be a public field so that the gob encoder can write it to
    97  	// disk. This will be needed at decode-time by the Hash function.
    98  	Sha256 string
    99  }
   100  
   101  // NewPayloadCurve parses a .csv file and returns a *PayloadCurve if no errors
   102  // were encountered in parsing and initialization.
   103  func NewPayloadCurve(file string) (*PayloadCurve, error) {
   104  	f, err := os.Open(file)
   105  	if err != nil {
   106  		return nil, err
   107  	}
   108  	defer f.Close()
   109  
   110  	r := csv.NewReader(f)
   111  	lines, err := r.ReadAll()
   112  	if err != nil {
   113  		return nil, err
   114  	}
   115  
   116  	ret := &PayloadCurve{}
   117  	var total float64
   118  	for _, line := range lines {
   119  		pcr, err := newPayloadCurveRange(line)
   120  		if err != nil {
   121  			return nil, err
   122  		}
   123  
   124  		ret.pcrs = append(ret.pcrs, pcr)
   125  		total += pcr.weight
   126  	}
   127  
   128  	ret.Sha256, err = sha256file(file)
   129  	if err != nil {
   130  		return nil, err
   131  	}
   132  	for _, pcr := range ret.pcrs {
   133  		pcr.weight /= total
   134  	}
   135  
   136  	sort.Slice(ret.pcrs, func(i, j int) bool {
   137  		if ret.pcrs[i].from == ret.pcrs[j].from {
   138  			return ret.pcrs[i].to < ret.pcrs[j].to
   139  		}
   140  		return ret.pcrs[i].from < ret.pcrs[j].from
   141  	})
   142  
   143  	var lastTo int32
   144  	for _, pcr := range ret.pcrs {
   145  		if lastTo >= pcr.from {
   146  			return nil, fmt.Errorf("[%d, %d] overlaps with a different line", pcr.from, pcr.to)
   147  		}
   148  		lastTo = pcr.to
   149  	}
   150  
   151  	return ret, nil
   152  }
   153  
   154  // ChooseRandom picks a random payload size (in bytes) that follows the
   155  // underlying weighted random distribution.
   156  func (pc *PayloadCurve) ChooseRandom() int {
   157  	target := rand.Float64()
   158  	var seen float64
   159  	for _, pcr := range pc.pcrs {
   160  		seen += pcr.weight
   161  		if seen >= target {
   162  			return pcr.chooseRandom()
   163  		}
   164  	}
   165  
   166  	// This should never happen, but if it does, return a sane default.
   167  	return 1
   168  }
   169  
   170  // Hash returns a string uniquely identifying a payload curve file for feature
   171  // matching purposes.
   172  func (pc *PayloadCurve) Hash() string {
   173  	return pc.Sha256
   174  }
   175  
   176  // ShortHash returns a shortened version of Hash for display purposes.
   177  func (pc *PayloadCurve) ShortHash() string {
   178  	return pc.Sha256[:8]
   179  }
   180
View as plain text