1#!/usr/bin/env python3
2
3# Copyright 2017 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
17from __future__ import print_function
18
19import collections
20import ctypes
21import json
22import math
23import sys
24
25import yaml
26
27with open('src/core/lib/debug/stats_data.yaml') as f:
28    attrs = yaml.safe_load(f.read(), Loader=yaml.Loader)
29
30REQUIRED_FIELDS = ['name', 'doc']
31
32
33def make_type(name, fields):
34    return (collections.namedtuple(
35        name, ' '.join(list(set(REQUIRED_FIELDS + fields)))), [])
36
37
38def c_str(s, encoding='ascii'):
39    if isinstance(s, str):
40        s = s.encode(encoding)
41    result = ''
42    for c in s:
43        c = chr(c) if isinstance(c, int) else c
44        if not (32 <= ord(c) < 127) or c in ('\\', '"'):
45            result += '\\%03o' % ord(c)
46        else:
47            result += c
48    return '"' + result + '"'
49
50
51types = (
52    make_type('Counter', []),
53    make_type('Histogram', ['max', 'buckets']),
54)
55Shape = collections.namedtuple('Shape', 'max buckets')
56
57inst_map = dict((t[0].__name__, t[1]) for t in types)
58
59stats = []
60
61for attr in attrs:
62    found = False
63    for t, lst in types:
64        t_name = t.__name__.lower()
65        if t_name in attr:
66            name = attr[t_name]
67            del attr[t_name]
68            lst.append(t(name=name, **attr))
69            found = True
70            break
71    assert found, "Bad decl: %s" % attr
72
73
74def dbl2u64(d):
75    return ctypes.c_ulonglong.from_buffer(ctypes.c_double(d)).value
76
77
78def u642dbl(d):
79    return ctypes.c_double.from_buffer(ctypes.c_ulonglong(d)).value
80
81
82def shift_works_until(mapped_bounds, shift_bits):
83    for i, ab in enumerate(zip(mapped_bounds, mapped_bounds[1:])):
84        a, b = ab
85        if (a >> shift_bits) == (b >> shift_bits):
86            return i
87    return len(mapped_bounds)
88
89
90def find_ideal_shift(mapped_bounds, max_size):
91    best = None
92    for shift_bits in reversed(list(range(0, 64))):
93        n = shift_works_until(mapped_bounds, shift_bits)
94        if n == 0:
95            continue
96        table_size = mapped_bounds[n - 1] >> shift_bits
97        if table_size > max_size:
98            continue
99        if best is None:
100            best = (shift_bits, n, table_size)
101        elif best[1] < n:
102            best = (shift_bits, n, table_size)
103    return best
104
105
106def gen_map_table(mapped_bounds, shift_data):
107    #print("gen_map_table(%s, %s)" % (mapped_bounds, shift_data))
108    tbl = []
109    cur = 0
110    mapped_bounds = [x >> shift_data[0] for x in mapped_bounds]
111    for i in range(0, mapped_bounds[shift_data[1] - 1]):
112        while i > mapped_bounds[cur]:
113            cur += 1
114        tbl.append(cur)
115    return tbl
116
117
118static_tables = []
119
120
121def decl_static_table(values, type):
122    global static_tables
123    v = (type, values)
124    for i, vp in enumerate(static_tables):
125        if v == vp:
126            return i
127    r = len(static_tables)
128    static_tables.append(v)
129    return r
130
131
132def type_for_uint_table(table):
133    mv = max(table)
134    if mv < 2**8:
135        return 'uint8_t'
136    elif mv < 2**16:
137        return 'uint16_t'
138    elif mv < 2**32:
139        return 'uint32_t'
140    else:
141        return 'uint64_t'
142
143
144def merge_cases(cases):
145    l = len(cases)
146    if l == 1:
147        return cases[0][1]
148    left_len = l // 2
149    left = cases[0:left_len]
150    right = cases[left_len:]
151    return 'if (value < %d) {\n%s\n} else {\n%s\n}' % (
152        left[-1][0], merge_cases(left), merge_cases(right))
153
154
155def gen_bucket_code(shape):
156    bounds = [0, 1]
157    done_trivial = False
158    done_unmapped = False
159    first_nontrivial = None
160    first_unmapped = None
161    while len(bounds) < shape.buckets + 1:
162        if len(bounds) == shape.buckets:
163            nextb = int(shape.max)
164        else:
165            mul = math.pow(
166                float(shape.max) / bounds[-1],
167                1.0 / (shape.buckets + 1 - len(bounds)))
168            nextb = int(math.ceil(bounds[-1] * mul))
169        if nextb <= bounds[-1] + 1:
170            nextb = bounds[-1] + 1
171        elif not done_trivial:
172            done_trivial = True
173            first_nontrivial = len(bounds)
174        bounds.append(nextb)
175    bounds_idx = decl_static_table(bounds, 'int')
176    #print first_nontrivial, shift_data, bounds
177    #if shift_data is not None: print [hex(x >> shift_data[0]) for x in code_bounds[first_nontrivial:]]
178    if first_nontrivial is None:
179        return ('return grpc_core::Clamp(value, 0, %d);\n' % shape.max,
180                bounds_idx)
181    cases = [(0, 'return 0;'), (first_nontrivial, 'return value;')]
182    if done_trivial:
183        first_nontrivial_code = dbl2u64(first_nontrivial)
184        last_code = first_nontrivial_code
185        while True:
186            code = ''
187            first_nontrivial = u642dbl(first_nontrivial_code)
188            code_bounds_index = None
189            for i, b in enumerate(bounds):
190                if b > first_nontrivial:
191                    code_bounds_index = i
192                    break
193            code_bounds = [dbl2u64(x) - first_nontrivial_code for x in bounds]
194            shift_data = find_ideal_shift(code_bounds[code_bounds_index:],
195                                          65536)
196            if not shift_data:
197                break
198            map_table = gen_map_table(code_bounds[code_bounds_index:],
199                                      shift_data)
200            if not map_table:
201                break
202            if map_table[-1] < 5:
203                break
204            map_table_idx = decl_static_table(
205                [x + code_bounds_index for x in map_table],
206                type_for_uint_table(map_table))
207            last_code = (
208                (len(map_table) - 1) << shift_data[0]) + first_nontrivial_code
209            code += 'DblUint val;\n'
210            code += 'val.dbl = value;\n'
211            code += 'const int bucket = '
212            code += 'kStatsTable%d[((val.uint - %dull) >> %d)];\n' % (
213                map_table_idx, first_nontrivial_code, shift_data[0])
214            code += 'return bucket - (value < kStatsTable%d[bucket]);' % bounds_idx
215            cases.append((int(u642dbl(last_code)) + 1, code))
216            first_nontrivial_code = last_code
217        last = u642dbl(last_code) + 1
218        for i, b in enumerate(bounds[:-2]):
219            if bounds[i + 1] < last:
220                continue
221            cases.append((bounds[i + 1], 'return %d;' % i))
222    cases.append((None, 'return %d;' % (len(bounds) - 2)))
223    return (merge_cases(cases), bounds_idx)
224
225
226# utility: print a big comment block into a set of files
227def put_banner(files, banner):
228    for f in files:
229        for line in banner:
230            print('// %s' % line, file=f)
231        print(file=f)
232
233
234shapes = set()
235for histogram in inst_map['Histogram']:
236    shapes.add(Shape(max=histogram.max, buckets=histogram.buckets))
237
238
239def snake_to_pascal(name):
240    return ''.join([x.capitalize() for x in name.split('_')])
241
242
243with open('src/core/lib/debug/stats_data.h', 'w') as H:
244    # copy-paste copyright notice from this file
245    with open(sys.argv[0]) as my_source:
246        copyright = []
247        for line in my_source:
248            if line[0] != '#':
249                break
250        for line in my_source:
251            if line[0] == '#':
252                copyright.append(line)
253                break
254        for line in my_source:
255            if line[0] != '#':
256                break
257            copyright.append(line)
258        put_banner([H], [line[2:].rstrip() for line in copyright])
259
260    put_banner(
261        [H],
262        ["Automatically generated by tools/codegen/core/gen_stats_data.py"])
263
264    print("#ifndef GRPC_SRC_CORE_LIB_DEBUG_STATS_DATA_H", file=H)
265    print("#define GRPC_SRC_CORE_LIB_DEBUG_STATS_DATA_H", file=H)
266    print(file=H)
267    print("#include <grpc/support/port_platform.h>", file=H)
268    print("#include <atomic>", file=H)
269    print("#include <memory>", file=H)
270    print("#include <stdint.h>", file=H)
271    print("#include \"src/core/lib/debug/histogram_view.h\"", file=H)
272    print("#include \"absl/strings/string_view.h\"", file=H)
273    print("#include \"src/core/lib/gprpp/per_cpu.h\"", file=H)
274    print(file=H)
275    print("namespace grpc_core {", file=H)
276
277    for shape in shapes:
278        print("class HistogramCollector_%d_%d;" % (shape.max, shape.buckets),
279              file=H)
280        print("class Histogram_%d_%d {" % (shape.max, shape.buckets), file=H)
281        print(" public:", file=H)
282        print("  static int BucketFor(int value);", file=H)
283        print("  const uint64_t* buckets() const { return buckets_; }", file=H)
284        print(
285            "  friend Histogram_%d_%d operator-(const Histogram_%d_%d& left, const Histogram_%d_%d& right);"
286            % (shape.max, shape.buckets, shape.max, shape.buckets, shape.max,
287               shape.buckets),
288            file=H)
289        print(" private:", file=H)
290        print("  friend class HistogramCollector_%d_%d;" %
291              (shape.max, shape.buckets),
292              file=H)
293        print("  uint64_t buckets_[%d]{};" % shape.buckets, file=H)
294        print("};", file=H)
295        print("class HistogramCollector_%d_%d {" % (shape.max, shape.buckets),
296              file=H)
297        print(" public:", file=H)
298        print("  void Increment(int value) {", file=H)
299        print("    buckets_[Histogram_%d_%d::BucketFor(value)]" %
300              (shape.max, shape.buckets),
301              file=H)
302        print("        .fetch_add(1, std::memory_order_relaxed);", file=H)
303        print("  }", file=H)
304        print("  void Collect(Histogram_%d_%d* result) const;" %
305              (shape.max, shape.buckets),
306              file=H)
307        print(" private:", file=H)
308        print("  std::atomic<uint64_t> buckets_[%d]{};" % shape.buckets, file=H)
309        print("};", file=H)
310
311    print("struct GlobalStats {", file=H)
312    print("  enum class Counter {", file=H)
313    for ctr in inst_map['Counter']:
314        print("    k%s," % snake_to_pascal(ctr.name), file=H)
315    print("    COUNT", file=H)
316    print("  };", file=H)
317    print("  enum class Histogram {", file=H)
318    for ctr in inst_map['Histogram']:
319        print("    k%s," % snake_to_pascal(ctr.name), file=H)
320    print("    COUNT", file=H)
321    print("  };", file=H)
322    print("  GlobalStats();", file=H)
323    print(
324        "  static const absl::string_view counter_name[static_cast<int>(Counter::COUNT)];",
325        file=H)
326    print(
327        "  static const absl::string_view histogram_name[static_cast<int>(Histogram::COUNT)];",
328        file=H)
329    print(
330        "  static const absl::string_view counter_doc[static_cast<int>(Counter::COUNT)];",
331        file=H)
332    print(
333        "  static const absl::string_view histogram_doc[static_cast<int>(Histogram::COUNT)];",
334        file=H)
335    print("  union {", file=H)
336    print("    struct {", file=H)
337    for ctr in inst_map['Counter']:
338        print("    uint64_t %s;" % ctr.name, file=H)
339    print("    };", file=H)
340    print("    uint64_t counters[static_cast<int>(Counter::COUNT)];", file=H)
341    print("  };", file=H)
342    for ctr in inst_map['Histogram']:
343        print("  Histogram_%d_%d %s;" % (ctr.max, ctr.buckets, ctr.name),
344              file=H)
345    print("  HistogramView histogram(Histogram which) const;", file=H)
346    print(
347        "  std::unique_ptr<GlobalStats> Diff(const GlobalStats& other) const;",
348        file=H)
349    print("};", file=H)
350    print("class GlobalStatsCollector {", file=H)
351    print(" public:", file=H)
352    print("  std::unique_ptr<GlobalStats> Collect() const;", file=H)
353    for ctr in inst_map['Counter']:
354        print(
355            "  void Increment%s() { data_.this_cpu().%s.fetch_add(1, std::memory_order_relaxed); }"
356            % (snake_to_pascal(ctr.name), ctr.name),
357            file=H)
358    for ctr in inst_map['Histogram']:
359        print(
360            "  void Increment%s(int value) { data_.this_cpu().%s.Increment(value); }"
361            % (snake_to_pascal(ctr.name), ctr.name),
362            file=H)
363    print(" private:", file=H)
364    print("  struct Data {", file=H)
365    for ctr in inst_map['Counter']:
366        print("    std::atomic<uint64_t> %s{0};" % ctr.name, file=H)
367    for ctr in inst_map['Histogram']:
368        print("    HistogramCollector_%d_%d %s;" %
369              (ctr.max, ctr.buckets, ctr.name),
370              file=H)
371    print("  };", file=H)
372    print(
373        "  PerCpu<Data> data_{PerCpuOptions().SetCpusPerShard(4).SetMaxShards(32)};",
374        file=H)
375    print("};", file=H)
376    print("}", file=H)
377
378    print(file=H)
379    print("#endif // GRPC_SRC_CORE_LIB_DEBUG_STATS_DATA_H", file=H)
380
381with open('src/core/lib/debug/stats_data.cc', 'w') as C:
382    # copy-paste copyright notice from this file
383    with open(sys.argv[0]) as my_source:
384        copyright = []
385        for line in my_source:
386            if line[0] != '#':
387                break
388        for line in my_source:
389            if line[0] == '#':
390                copyright.append(line)
391                break
392        for line in my_source:
393            if line[0] != '#':
394                break
395            copyright.append(line)
396        put_banner([C], [line[2:].rstrip() for line in copyright])
397
398    put_banner(
399        [C],
400        ["Automatically generated by tools/codegen/core/gen_stats_data.py"])
401
402    print("#include <grpc/support/port_platform.h>", file=C)
403    print(file=C)
404    print("#include \"src/core/lib/debug/stats_data.h\"", file=C)
405    print("#include <stdint.h>", file=C)
406    print(file=C)
407
408    histo_code = []
409    histo_bucket_boundaries = {}
410    for shape in shapes:
411        code, bounds_idx = gen_bucket_code(shape)
412        histo_bucket_boundaries[shape] = bounds_idx
413        histo_code.append(code)
414
415    print("namespace grpc_core {", file=C)
416    print("namespace { union DblUint { double dbl; uint64_t uint; }; }", file=C)
417
418    for shape in shapes:
419        print(
420            "void HistogramCollector_%d_%d::Collect(Histogram_%d_%d* result) const {"
421            % (shape.max, shape.buckets, shape.max, shape.buckets),
422            file=C)
423        print("  for (int i=0; i<%d; i++) {" % shape.buckets, file=C)
424        print(
425            "    result->buckets_[i] += buckets_[i].load(std::memory_order_relaxed);",
426            file=C)
427        print("  }", file=C)
428        print("}", file=C)
429        print(
430            "Histogram_%d_%d operator-(const Histogram_%d_%d& left, const Histogram_%d_%d& right) {"
431            % (shape.max, shape.buckets, shape.max, shape.buckets, shape.max,
432               shape.buckets),
433            file=C)
434        print("  Histogram_%d_%d result;" % (shape.max, shape.buckets), file=C)
435        print("  for (int i=0; i<%d; i++) {" % shape.buckets, file=C)
436        print("    result.buckets_[i] = left.buckets_[i] - right.buckets_[i];",
437              file=C)
438        print("  }", file=C)
439        print("  return result;", file=C)
440        print("}", file=C)
441
442    for typename, instances in sorted(inst_map.items()):
443        print(
444            "const absl::string_view GlobalStats::%s_name[static_cast<int>(%s::COUNT)] = {"
445            % (typename.lower(), typename),
446            file=C)
447        for inst in instances:
448            print("  %s," % c_str(inst.name), file=C)
449        print("};", file=C)
450        print(
451            "const absl::string_view GlobalStats::%s_doc[static_cast<int>(%s::COUNT)] = {"
452            % (typename.lower(), typename),
453            file=C)
454        for inst in instances:
455            print("  %s," % c_str(inst.doc), file=C)
456        print("};", file=C)
457
458    print("namespace {", file=C)
459    for i, tbl in enumerate(static_tables):
460        print("const %s kStatsTable%d[%d] = {%s};" %
461              (tbl[0], i, len(tbl[1]), ','.join('%s' % x for x in tbl[1])),
462              file=C)
463    print("}  // namespace", file=C)
464
465    for shape, code in zip(shapes, histo_code):
466        print(("int Histogram_%d_%d::BucketFor(int value) {%s}") %
467              (shape.max, shape.buckets, code),
468              file=C)
469
470    print("GlobalStats::GlobalStats() : %s {}" %
471          ",".join("%s{0}" % ctr.name for ctr in inst_map['Counter']),
472          file=C)
473
474    print("HistogramView GlobalStats::histogram(Histogram which) const {",
475          file=C)
476    print("  switch (which) {", file=C)
477    print("    default: GPR_UNREACHABLE_CODE(return HistogramView());", file=C)
478    for inst in inst_map['Histogram']:
479        print("    case Histogram::k%s:" % snake_to_pascal(inst.name), file=C)
480        print(
481            "      return HistogramView{&Histogram_%d_%d::BucketFor, kStatsTable%d, %d, %s.buckets()};"
482            % (inst.max, inst.buckets, histo_bucket_boundaries[Shape(
483                inst.max, inst.buckets)], inst.buckets, inst.name),
484            file=C)
485    print("  }", file=C)
486    print("}", file=C)
487
488    print(
489        "std::unique_ptr<GlobalStats> GlobalStatsCollector::Collect() const {",
490        file=C)
491    print("  auto result = std::make_unique<GlobalStats>();", file=C)
492    print("  for (const auto& data : data_) {", file=C)
493    for ctr in inst_map['Counter']:
494        print("    result->%s += data.%s.load(std::memory_order_relaxed);" %
495              (ctr.name, ctr.name),
496              file=C)
497    for h in inst_map['Histogram']:
498        print("    data.%s.Collect(&result->%s);" % (h.name, h.name), file=C)
499    print("  }", file=C)
500    print("  return result;", file=C)
501    print("}", file=C)
502
503    print(
504        "std::unique_ptr<GlobalStats> GlobalStats::Diff(const GlobalStats& other) const {",
505        file=C)
506    print("  auto result = std::make_unique<GlobalStats>();", file=C)
507    for ctr in inst_map['Counter']:
508        print("  result->%s = %s - other.%s;" % (ctr.name, ctr.name, ctr.name),
509              file=C)
510    for h in inst_map['Histogram']:
511        print("  result->%s = %s - other.%s;" % (h.name, h.name, h.name),
512              file=C)
513    print("  return result;", file=C)
514    print("}", file=C)
515
516    print("}", file=C)
517