1 /* 2 * Copyright (C) 2018 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef NETDUTILS_BACKOFFSEQUENCE_H 18 #define NETDUTILS_BACKOFFSEQUENCE_H 19 20 #include <stdint.h> 21 #include <algorithm> 22 #include <chrono> 23 #include <limits> 24 25 namespace android { 26 namespace netdutils { 27 28 // Encapsulate some RFC 3315 section 14 -style backoff mechanics. 29 // 30 // https://tools.ietf.org/html/rfc3315#section-14 31 template<typename time_type = std::chrono::seconds, typename counter_type = uint32_t> 32 class BackoffSequence { 33 public: 34 struct Parameters { 35 time_type initialRetransTime{TIME_UNITY}; 36 counter_type maxRetransCount{0U}; 37 time_type maxRetransTime{TIME_ZERO}; 38 time_type maxRetransDuration{TIME_ZERO}; 39 time_type endOfSequenceIndicator{TIME_ZERO}; 40 }; 41 BackoffSequence()42 BackoffSequence() : BackoffSequence(Parameters{}) {} 43 BackoffSequence(const BackoffSequence &) = default; 44 BackoffSequence(BackoffSequence &&) = default; 45 BackoffSequence& operator=(const BackoffSequence &) = default; 46 BackoffSequence& operator=(BackoffSequence &&) = default; 47 hasNextTimeout()48 bool hasNextTimeout() const noexcept { 49 return !maxRetransCountExceed() && !maxRetransDurationExceeded(); 50 } 51 52 // Returns 0 when the sequence is exhausted. getNextTimeout()53 time_type getNextTimeout() { 54 if (!hasNextTimeout()) return getEndOfSequenceIndicator(); 55 56 mRetransTime = getNextTimeoutAfter(mRetransTime); 57 58 mRetransCount++; 59 mTotalRetransDuration += mRetransTime; 60 return mRetransTime; 61 } 62 getEndOfSequenceIndicator()63 time_type getEndOfSequenceIndicator() const noexcept { 64 return mParams.endOfSequenceIndicator; 65 } 66 67 class Builder { 68 public: Builder()69 Builder() {} 70 withInitialRetransmissionTime(time_type irt)71 constexpr Builder& withInitialRetransmissionTime(time_type irt) { 72 mParams.initialRetransTime = irt; 73 return *this; 74 } withMaximumRetransmissionCount(counter_type mrc)75 constexpr Builder& withMaximumRetransmissionCount(counter_type mrc) { 76 mParams.maxRetransCount = mrc; 77 return *this; 78 } withMaximumRetransmissionTime(time_type mrt)79 constexpr Builder& withMaximumRetransmissionTime(time_type mrt) { 80 mParams.maxRetransTime = mrt; 81 return *this; 82 } withMaximumRetransmissionDuration(time_type mrd)83 constexpr Builder& withMaximumRetransmissionDuration(time_type mrd) { 84 mParams.maxRetransDuration = mrd; 85 return *this; 86 } withEndOfSequenceIndicator(time_type eos)87 constexpr Builder& withEndOfSequenceIndicator(time_type eos) { 88 mParams.endOfSequenceIndicator = eos; 89 return *this; 90 } 91 build()92 constexpr BackoffSequence build() const { 93 return BackoffSequence(mParams); 94 } 95 96 private: 97 Parameters mParams; 98 }; 99 100 private: 101 static constexpr int PER_ITERATION_SCALING_FACTOR = 2; 102 static constexpr time_type TIME_ZERO = time_type(); 103 static constexpr time_type TIME_UNITY = time_type(1); 104 BackoffSequence(const struct Parameters & params)105 constexpr BackoffSequence(const struct Parameters ¶ms) 106 : mParams(params), 107 mRetransCount(0), 108 mRetransTime(TIME_ZERO), 109 mTotalRetransDuration(TIME_ZERO) {} 110 maxRetransCountExceed()111 constexpr bool maxRetransCountExceed() const { 112 return (mParams.maxRetransCount > 0) && (mRetransCount >= mParams.maxRetransCount); 113 } 114 maxRetransDurationExceeded()115 constexpr bool maxRetransDurationExceeded() const { 116 return (mParams.maxRetransDuration > TIME_ZERO) && 117 (mTotalRetransDuration >= mParams.maxRetransDuration); 118 } 119 getNextTimeoutAfter(time_type lastTimeout)120 time_type getNextTimeoutAfter(time_type lastTimeout) const { 121 // TODO: Support proper random jitter. Also, consider supporting some 122 // per-iteration scaling factor other than doubling. 123 time_type nextTimeout = (lastTimeout > TIME_ZERO) 124 ? PER_ITERATION_SCALING_FACTOR * lastTimeout 125 : mParams.initialRetransTime; 126 127 // Check if overflow occurred. 128 if (nextTimeout < lastTimeout) { 129 nextTimeout = std::numeric_limits<time_type>::max(); 130 } 131 132 // Cap to maximum allowed, if necessary. 133 if (mParams.maxRetransTime > TIME_ZERO) { 134 nextTimeout = std::min(nextTimeout, mParams.maxRetransTime); 135 } 136 137 // Don't overflow the maximum total duration. 138 if (mParams.maxRetransDuration > TIME_ZERO) { 139 nextTimeout = std::min(nextTimeout, mParams.maxRetransDuration - lastTimeout); 140 } 141 return nextTimeout; 142 } 143 144 const Parameters mParams; 145 counter_type mRetransCount; 146 time_type mRetransTime; 147 time_type mTotalRetransDuration; 148 }; 149 150 } // namespace netdutils 151 } // namespace android 152 153 #endif /* NETDUTILS_BACKOFFSEQUENCE_H */ 154