view src/main/java/org/openjdk/gcbench/util/ratelimit/MultiTokenBucket.java @ 88:583fef4276f5

Update license and copyright headers.
author shade
date Wed, 22 Nov 2017 15:58:02 +0100
parents 2175102c5611
children 14c1bb4faa6e
line wrap: on
line source

/*
 * Copyright (c) 2017, Red Hat Inc. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */
package org.openjdk.gcbench.util.ratelimit;

import java.util.concurrent.atomic.*;

public class MultiTokenBucket implements RateLimiter {

    static final int QUANTA_PER_SEC = 10;
    static final int MS_PER_QUANTUM = 1000 / QUANTA_PER_SEC;

    static final AtomicReferenceFieldUpdater<MultiTokenBucket, Counters> STATE =
            AtomicReferenceFieldUpdater.newUpdater(MultiTokenBucket.class, Counters.class, "counters");

    private final int tokensPerQuantum;
    private final long timeBase;

    private final int stateCount;
    private final int stateCountMask;

    private volatile Counters counters;
    private volatile int currentQuant;

    public MultiTokenBucket(int ratePerSec) {
        this.tokensPerQuantum = Math.max(1, ratePerSec / QUANTA_PER_SEC);
        this.stateCount = roundToPow2(Runtime.getRuntime().availableProcessors() * 2);
        this.stateCountMask = stateCount - 1;
        this.timeBase = System.currentTimeMillis();
        STATE.set(this, new Counters(newCounters(), 0));

        new StampUpdater().start();
    }

    private Counter[] newCounters() {
        Counter[] counters = new Counter[stateCount];
        for (int c = 0; c < stateCount; c++) {
            counters[c] = new Counter();
        }
        return counters;
    }

    private static int roundToPow2(int v) {
        v--;
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        v++;
        return v;
    }

    @Override
    public void limit() {
        int id = (int)(Thread.currentThread().getId() & stateCountMask);

        while (true) {
            int quantId = currentQuant;

            Counters st = STATE.get(this);
            Counter[] states = st.states;
            int time = st.time;

            if (time == quantId) {
                // our time, try to figure out the state

                // try to optimistically poll my own ID
                Counter my = states[id];

                if (my.val() > 0 && my.dec() >= 1) {
                    return; // success!
                }

                // try to steal!
                for (int i = id + 1; i < stateCount; i++) {
                    if (trySteal(my, states[i]))
                        return; // success!
                }

                for (int i = 0; i < id; i++) {
                    if (trySteal(my, states[i]))
                        return; // success!
                }
            }

            // no rush, this is not our quantum: wait before re-spinning
            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                // ignore
            }
        }
    }

    private boolean trySteal(Counter dst, Counter src) {
        if (src.val() != 0) {
            int stolen = src.steal();
            if (stolen > 0) {
                dst.add(stolen - 1); // borrow one!
                return true;
            }
        }
        return false;
    }

    class StampUpdater extends Thread {
        public StampUpdater() {
            setDaemon(true);
            setPriority(MAX_PRIORITY);
        }

        @Override
        public void run() {
            int lastQuantId = 0;
            while (!Thread.interrupted()) {
                int quantId = (int) ((System.currentTimeMillis() - timeBase) / MS_PER_QUANTUM);
                if (quantId != lastQuantId) {
                    Counter[] cnts = newCounters();
                    cnts[0].add(tokensPerQuantum);

                    currentQuant = quantId;
                    lastQuantId = quantId;

                    STATE.set(MultiTokenBucket.this, new Counters(cnts, quantId));
                }
                try {
                    Thread.sleep(1);
                } catch (InterruptedException e) {
                    // do nothing
                }
            }
        }
    }

    static class Counters {
        private final Counter[] states;
        private final int time;

        public Counters(Counter[] states, int time) {
            this.states = states;
            this.time = time;
        }
    }

    private static class Counter_Payload extends Counter_B1 {
        static final AtomicIntegerFieldUpdater<Counter_Payload> CURRENT =
                AtomicIntegerFieldUpdater.newUpdater(Counter_Payload.class, "cnt");

        volatile int cnt;

        int val() {
            return CURRENT.get(this);
        }

        int dec() {
            return CURRENT.getAndDecrement(this);
        }

        public int steal() {
            while (true) {
                int val = CURRENT.get(this);
                int steal = Math.max(1, val / 2); // try to steal at least one
                int remain = val - steal;
                if (remain < 0)
                    return 0;
                if (CURRENT.compareAndSet(this, val, remain))
                    return steal;
            }
        }

        void add(int val) {
            CURRENT.addAndGet(this, val);
        }
    }

    private static class Counter_B1 {
        boolean p000, p001, p002, p003, p004, p005, p006, p007, p008, p009, p010, p011, p012, p013, p014, p015;
        boolean p016, p017, p018, p019, p020, p021, p022, p023, p024, p025, p026, p027, p028, p029, p030, p031;
        boolean p032, p033, p034, p035, p036, p037, p038, p039, p040, p041, p042, p043, p044, p045, p046, p047;
        boolean p048, p049, p050, p051, p052, p053, p054, p055, p056, p057, p058, p059, p060, p061, p062, p063;
        boolean p064, p065, p066, p067, p068, p069, p070, p071, p072, p073, p074, p075, p076, p077, p078, p079;
        boolean p080, p081, p082, p083, p084, p085, p086, p087, p088, p089, p090, p091, p092, p093, p094, p095;
        boolean p096, p097, p098, p099, p100, p101, p102, p103, p104, p105, p106, p107, p108, p109, p110, p111;
        boolean p112, p113, p114, p115, p116, p117, p118, p119, p120, p121, p122, p123, p124, p125, p126, p127;
        boolean p128, p129, p130, p131, p132, p133, p134, p135, p136, p137, p138, p139, p140, p141, p142, p143;
        boolean p144, p145, p146, p147, p148, p149, p150, p151, p152, p153, p154, p155, p156, p157, p158, p159;
        boolean p160, p161, p162, p163, p164, p165, p166, p167, p168, p169, p170, p171, p172, p173, p174, p175;
        boolean p176, p177, p178, p179, p180, p181, p182, p183, p184, p185, p186, p187, p188, p189, p190, p191;
        boolean p192, p193, p194, p195, p196, p197, p198, p199, p200, p201, p202, p203, p204, p205, p206, p207;
        boolean p208, p209, p210, p211, p212, p213, p214, p215, p216, p217, p218, p219, p220, p221, p222, p223;
        boolean p224, p225, p226, p227, p228, p229, p230, p231, p232, p233, p234, p235, p236, p237, p238, p239;
        boolean p240, p241, p242, p243, p244, p245, p246, p247, p248, p249, p250, p251, p252, p253, p254, p255;
    }

    private static class Counter_B2 extends Counter_Payload {
        boolean p000, p001, p002, p003, p004, p005, p006, p007, p008, p009, p010, p011, p012, p013, p014, p015;
        boolean p016, p017, p018, p019, p020, p021, p022, p023, p024, p025, p026, p027, p028, p029, p030, p031;
        boolean p032, p033, p034, p035, p036, p037, p038, p039, p040, p041, p042, p043, p044, p045, p046, p047;
        boolean p048, p049, p050, p051, p052, p053, p054, p055, p056, p057, p058, p059, p060, p061, p062, p063;
        boolean p064, p065, p066, p067, p068, p069, p070, p071, p072, p073, p074, p075, p076, p077, p078, p079;
        boolean p080, p081, p082, p083, p084, p085, p086, p087, p088, p089, p090, p091, p092, p093, p094, p095;
        boolean p096, p097, p098, p099, p100, p101, p102, p103, p104, p105, p106, p107, p108, p109, p110, p111;
        boolean p112, p113, p114, p115, p116, p117, p118, p119, p120, p121, p122, p123, p124, p125, p126, p127;
        boolean p128, p129, p130, p131, p132, p133, p134, p135, p136, p137, p138, p139, p140, p141, p142, p143;
        boolean p144, p145, p146, p147, p148, p149, p150, p151, p152, p153, p154, p155, p156, p157, p158, p159;
        boolean p160, p161, p162, p163, p164, p165, p166, p167, p168, p169, p170, p171, p172, p173, p174, p175;
        boolean p176, p177, p178, p179, p180, p181, p182, p183, p184, p185, p186, p187, p188, p189, p190, p191;
        boolean p192, p193, p194, p195, p196, p197, p198, p199, p200, p201, p202, p203, p204, p205, p206, p207;
        boolean p208, p209, p210, p211, p212, p213, p214, p215, p216, p217, p218, p219, p220, p221, p222, p223;
        boolean p224, p225, p226, p227, p228, p229, p230, p231, p232, p233, p234, p235, p236, p237, p238, p239;
        boolean p240, p241, p242, p243, p244, p245, p246, p247, p248, p249, p250, p251, p252, p253, p254, p255;
    }

    private static class Counter extends Counter_B2 {

    }

}