#!/usr/bin/env python3

# Copyright 2023 gRPC authors.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# USAGE:
# Run some tests with the GRPC_ARENA_TRACE_POOLED_ALLOCATIONS #define turned on.
# Capture the output to a text file.
# Invoke this program with that as an argument, and let it work its magic.

import collections
import heapq
import random
import re
import sys

# A single allocation, negative size => free
Allocation = collections.namedtuple("Allocation", "size ptr")
Active = collections.namedtuple("Active", "id size")

# Read through all the captures, and build up scrubbed traces
arenas = []
building = collections.defaultdict(list)
active = {}
biggest = 0
smallest = 1024
sizes = set()
for filename in sys.argv[1:]:
    for line in open(filename):
        m = re.search(
            r"ARENA 0x([0-9a-f]+) ALLOC ([0-9]+) @ 0x([0-9a-f]+)", line
        )
        if m:
            size = int(m.group(2))
            if size > biggest:
                biggest = size
            if size < smallest:
                smallest = size
            active[m.group(3)] = Active(m.group(1), size)
            building[m.group(1)].append(size)
            sizes.add(size)
        m = re.search(r"FREE 0x([0-9a-f]+)", line)
        if m:
            # We may have spurious frees, so make sure there's an outstanding allocation
            last = active.pop(m.group(1), None)
            if last is not None:
                building[last.id].append(-last.size)
        m = re.search(r"DESTRUCT_ARENA 0x([0-9a-f]+)", line)
        if m:
            trace = building.pop(m.group(1), None)
            if trace:
                arenas.append(trace)


# Given a list of pool sizes, return which bucket an allocation should go into
def bucket(pool_sizes, size):
    for bucket in sorted(pool_sizes):
        if abs(size) <= bucket:
            return bucket


# Given a list of pool sizes, determine the total outstanding bytes in the arena for once trace
def outstanding_bytes(pool_sizes, trace):
    free_list = collections.defaultdict(int)
    allocated = 0
    for size in trace:
        b = bucket(pool_sizes, size)
        if size < 0:
            free_list[b] += 1
        else:
            if free_list[b] > 0:
                free_list[b] -= 1
            else:
                allocated += b
    return allocated + len(pool_sizes) * 8


# Given a list of pool sizes, determine the maximum outstanding bytes for any seen trace
def measure(pool_sizes):
    max_outstanding = 0
    for trace in arenas:
        max_outstanding = max(
            max_outstanding, outstanding_bytes(pool_sizes, trace)
        )
    return max_outstanding


ALWAYS_INCLUDE = 1024
best = [ALWAYS_INCLUDE, biggest]
best_measure = measure(best)

testq = []
step = 0


def add(l):
    global testq, best_measure, best
    m = measure(l)
    if m < best_measure:
        best_measure = m
        best = l
    if l[-1] == smallest:
        return
    heapq.heappush(testq, (m, l))


add(best)

while testq:
    top = heapq.heappop(testq)[1]
    m = measure(top)
    step += 1
    if step % 1000 == 0:
        print(
            "iter %d; pending=%d; top=%r/%d"
            % (step, len(testq), top, measure(top))
        )
    for i in sizes:
        if i >= top[-1]:
            continue
        add(top + [i])

print("SAW SIZES: %r" % sorted(list(sizes)))
print("BEST: %r" % list(reversed(best)))
print("BEST MEASURE: %d" % best_measure)