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 &params)
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