Grcov report - deterministic

1

#if defined(ENVOY_ENABLE_FULL_PROTOS)

2

#include "source/common/protobuf/deterministic_hash.h"

3

4

#include "source/common/common/assert.h"

5

#include "source/common/common/hash.h"

6

7

namespace Envoy {

8

namespace DeterministicProtoHash {

9

namespace {

10

11

// Get a scalar field from protobuf reflection field definition. The return

12

// type must be specified by the caller. Every implementation is a specialization

13

// because the reflection interface did separate named functions instead of a

14

// template.

15

template <typename T>

16

T reflectionGet(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

17

                const Protobuf::FieldDescriptor& field);

18

19

template <>

20

uint32_t reflectionGet(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

21

58311

                       const Protobuf::FieldDescriptor& field) {

22

58311

  return reflection.GetUInt32(message, &field);

23

58311

24

25

template <>

26

int32_t reflectionGet(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

27

9961

                      const Protobuf::FieldDescriptor& field) {

28

9961

  return reflection.GetInt32(message, &field);

29

9961

30

31

template <>

32

uint64_t reflectionGet(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

33

347

                       const Protobuf::FieldDescriptor& field) {

34

347

  return reflection.GetUInt64(message, &field);

35

347

36

37

template <>

38

int64_t reflectionGet(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

39

24881

                      const Protobuf::FieldDescriptor& field) {

40

24881

  return reflection.GetInt64(message, &field);

41

24881

42

43

template <>

44

float reflectionGet(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

45

4

                    const Protobuf::FieldDescriptor& field) {

46

4

  return reflection.GetFloat(message, &field);

47

4

48

49

template <>

50

double reflectionGet(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

51

156

                     const Protobuf::FieldDescriptor& field) {

52

156

  return reflection.GetDouble(message, &field);

53

156

54

55

template <>

56

bool reflectionGet(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

57

7994

                   const Protobuf::FieldDescriptor& field) {

58

7994

  return reflection.GetBool(message, &field);

59

7994

60

61

// Takes a field of scalar type, and hashes it. In case the field is a repeated field,

62

// the function hashes each of its elements.

63

template <typename T, std::enable_if_t<std::is_scalar_v<T>, bool> = true>

64

uint64_t hashScalarField(const Protobuf::Reflection& reflection, const Protobuf::Message& message,

65

101811

                         const Protobuf::FieldDescriptor& field, uint64_t seed) {

66

101811

  if (field.is_repeated()) {

67

187

    for (const T& scalar : reflection.GetRepeatedFieldRef<T>(message, &field)) {

68

187

      seed = HashUtil::xxHash64Value(scalar, seed);

69

187

70

101654

  } else {

71

101654

    seed = HashUtil::xxHash64Value(reflectionGet<T>(reflection, message, field), seed);

72

101654

73

101811

  return seed;

74

101811

75

76

uint64_t reflectionHashMessage(const Protobuf::Message& message, uint64_t seed = 0);

77

uint64_t reflectionHashField(const Protobuf::Message& message,

78

                             const Protobuf::FieldDescriptor& field, uint64_t seed);

79

80

// To make a map serialize deterministically we need to ignore the order of

81

// the map fields. To do that, we simply combine the hashes of each entry

82

// using an unordered operator (addition), and then apply that combined hash to

83

// the seed.

84

uint64_t reflectionHashMapField(const Protobuf::Message& message,

85

20160

                                const Protobuf::FieldDescriptor& field, uint64_t seed) {

86

20160

  const Protobuf::Reflection& reflection = *message.GetReflection();

87

20160

  ASSERT(field.is_map());

88

20160

  const auto& entries = reflection.GetRepeatedFieldRef<Protobuf::Message>(message, &field);

89

20160

  ASSERT(!entries.empty());

90

20160

  const Protobuf::Descriptor& map_descriptor = *entries.begin()->GetDescriptor();

91

20160

  const Protobuf::FieldDescriptor& key_field = *map_descriptor.map_key();

92

20160

  const Protobuf::FieldDescriptor& value_field = *map_descriptor.map_value();

93

20160

  uint64_t combined_hash = 0;

94

23322

  for (const Protobuf::Message& entry : entries) {

95

23322

    uint64_t entry_hash = reflectionHashField(entry, key_field, 0);

96

23322

    entry_hash = reflectionHashField(entry, value_field, entry_hash);

97

23322

    combined_hash += entry_hash;

98

23322

99

20160

  return HashUtil::xxHash64Value(combined_hash, seed);

100

20160

101

102

uint64_t reflectionHashField(const Protobuf::Message& message,

103

998368

                             const Protobuf::FieldDescriptor& field, uint64_t seed) {

104

998368

  using Protobuf::FieldDescriptor;

105

998368

  const Protobuf::Reflection& reflection = *message.GetReflection();

106

998368

  seed = HashUtil::xxHash64Value(field.number(), seed);

107

998368

  switch (field.cpp_type()) {

108

10049

  case FieldDescriptor::CPPTYPE_INT32:

109

10049

    seed = hashScalarField<int32_t>(reflection, message, field, seed);

110

10049

    break;

111

58358

  case FieldDescriptor::CPPTYPE_UINT32:

112

58358

    seed = hashScalarField<uint32_t>(reflection, message, field, seed);

113

58358

    break;

114

24885

  case FieldDescriptor::CPPTYPE_INT64:

115

24885

    seed = hashScalarField<int64_t>(reflection, message, field, seed);

116

24885

    break;

117

351

  case FieldDescriptor::CPPTYPE_UINT64:

118

351

    seed = hashScalarField<uint64_t>(reflection, message, field, seed);

119

351

    break;

120

160

  case FieldDescriptor::CPPTYPE_DOUBLE:

121

160

    seed = hashScalarField<double>(reflection, message, field, seed);

122

160

    break;

123

8

  case FieldDescriptor::CPPTYPE_FLOAT:

124

8

    seed = hashScalarField<float>(reflection, message, field, seed);

125

8

    break;

126

8000

  case FieldDescriptor::CPPTYPE_BOOL:

127

8000

    seed = hashScalarField<bool>(reflection, message, field, seed);

128

8000

    break;

129

25363

  case FieldDescriptor::CPPTYPE_ENUM:

130

25363

    if (field.is_repeated()) {

131

7

      const int c = reflection.FieldSize(message, &field);

132

18

      for (int i = 0; i < c; i++) {

133

11

        seed = HashUtil::xxHash64Value(reflection.GetRepeatedEnumValue(message, &field, i), seed);

134

11

135

25356

    } else {

136

25356

      seed = HashUtil::xxHash64Value(reflection.GetEnumValue(message, &field), seed);

137

25356

138

25363

    break;

139

313116

  case FieldDescriptor::CPPTYPE_STRING:

140

313116

    if (field.is_repeated()) {

141

15885

      for (const std::string& str : reflection.GetRepeatedFieldRef<std::string>(message, &field)) {

142

15885

        seed = HashUtil::xxHash64(str, seed);

143

15885

144

298218

    } else {

145

      // Scratch may be used by GetStringReference if the field is not already a std::string.

146

298218

      std::string scratch;

147

298218

      seed = HashUtil::xxHash64(reflection.GetStringReference(message, &field, &scratch), seed);

148

298218

149

313116

    break;

150

558078

  case FieldDescriptor::CPPTYPE_MESSAGE:

151

558078

    if (field.is_map()) {

152

20160

      seed = reflectionHashMapField(message, field, seed);

153

537947

    } else if (field.is_repeated()) {

154

126340

      for (const Protobuf::Message& submsg :

155

149703

           reflection.GetRepeatedFieldRef<Protobuf::Message>(message, &field)) {

156

149703

        seed = reflectionHashMessage(submsg, seed);

157

149703

158

411578

    } else {

159

411578

      seed = reflectionHashMessage(reflection.GetMessage(message, &field), seed);

160

411578

161

558078

    break;

162

998368

163

998368

  return seed;

164

998368

165

166

// Converts from type urls OR descriptor full names to descriptor full names.

167

// Type urls are as used in envoy yaml config, e.g.

168

// "type.googleapis.com/envoy.extensions.filters.udp.udp_proxy.v3.UdpProxyConfig"

169

// becomes

170

// "envoy.extensions.filters.udp.udp_proxy.v3.UdpProxyConfig"

171

64568

absl::string_view typeUrlToDescriptorFullName(absl::string_view url) {

172

64568

  const size_t pos = url.rfind('/');

173

64568

  if (pos != absl::string_view::npos) {

174

64531

    return url.substr(pos + 1);

175

64531

176

37

  return url;

177

64568

178

179

64568

std::unique_ptr<Protobuf::Message> unpackAnyForReflection(const Protobuf::Any& any) {

180

64568

  const Protobuf::Descriptor* descriptor =

181

64568

      Protobuf::DescriptorPool::generated_pool()->FindMessageTypeByName(

182

64568

          typeUrlToDescriptorFullName(any.type_url()));

183

  // If the type name refers to an unknown type, we treat it the same as other

184

  // unknown fields - not including its contents in the hash.

185

64568

  if (descriptor == nullptr) {

186

38

    return nullptr;

187

38

188

64530

  const Protobuf::Message* prototype =

189

64530

      Protobuf::MessageFactory::generated_factory()->GetPrototype(descriptor);

190

64530

  ASSERT(prototype != nullptr, "should be impossible since the descriptor is known");

191

64530

  std::unique_ptr<Protobuf::Message> msg(prototype->New());

192

64530

  if (!any.UnpackTo(msg.get())) {

193

2

    return nullptr;

194

2

195

64528

  return msg;

196

64530

197

198

// This is intentionally ignoring unknown fields.

199

666325

uint64_t reflectionHashMessage(const Protobuf::Message& message, uint64_t seed) {

200

666325

  using Protobuf::FieldDescriptor;

201

666325

  const Protobuf::Reflection* reflection = message.GetReflection();

202

666325

  const Protobuf::Descriptor* descriptor = message.GetDescriptor();

203

666325

  seed = HashUtil::xxHash64(descriptor->full_name(), seed);

204

666325

  if (descriptor->well_known_type() == Protobuf::Descriptor::WELLKNOWNTYPE_ANY) {

205

64568

    const Protobuf::Any* any = Protobuf::DynamicCastMessage<Protobuf::Any>(&message);

206

64568

    ASSERT(any != nullptr, "casting to any should always work for WELLKNOWNTYPE_ANY");

207

64568

    std::unique_ptr<Protobuf::Message> submsg = unpackAnyForReflection(*any);

208

64568

    if (submsg == nullptr) {

209

      // If we wanted to handle unknown types in Any, this is where we'd have to do it.

210

      // Since we don't know the type to introspect it, we hash just its type name.

211

40

      return HashUtil::xxHash64(any->type_url(), seed);

212

40

213

64528

    return reflectionHashMessage(*submsg, seed);

214

64568

215

601757

  std::vector<const FieldDescriptor*> fields;

216

  // ListFields returned the fields ordered by field number.

217

601757

  reflection->ListFields(message, &fields);

218

  // If we wanted to handle unknown fields, we'd need to also GetUnknownFields here.

219

952471

  for (const FieldDescriptor* field : fields) {

220

951724

    seed = reflectionHashField(message, *field, seed);

221

951724

222

  // Hash one extra character to signify end of message, so that

223

  // msg{} field2=2

224

  // hashes differently from

225

  // msg{field2=2}

226

601757

  return HashUtil::xxHash64("\x17", seed);

227

666325

228

} // namespace

229

230

40516

uint64_t hash(const Protobuf::Message& message) { return reflectionHashMessage(message, 0); }

231

232

} // namespace DeterministicProtoHash

233

} // namespace Envoy

234

#endif