1 /*
2 * Copyright 2018 The Netty Project
3 *
4 * The Netty Project licenses this file to you under the Apache License,
5 * version 2.0 (the "License"); you may not use this file except in compliance
6 * with the License. You may obtain a copy of the License at:
7 *
8 * https://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, WITHOUT
12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13 * License for the specific language governing permissions and limitations
14 * under the License.
15 */
16 package io.netty.resolver.dns;
17
18 import io.netty.channel.EventLoop;
19 import io.netty.util.internal.PlatformDependent;
20
21 import java.util.ArrayList;
22 import java.util.Collections;
23 import java.util.Iterator;
24 import java.util.List;
25 import java.util.Map;
26 import java.util.Map.Entry;
27 import java.util.concurrent.ConcurrentMap;
28 import java.util.concurrent.Delayed;
29 import java.util.concurrent.ScheduledFuture;
30 import java.util.concurrent.TimeUnit;
31 import java.util.concurrent.atomic.AtomicReference;
32 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
33
34 import static java.util.Collections.singletonList;
35
36 /**
37 * Abstract cache that automatically removes entries for a hostname once the TTL for an entry is reached.
38 *
39 * @param <E>
40 */
41 abstract class Cache<E> {
42 private static final AtomicReferenceFieldUpdater<Cache.Entries, ScheduledFuture> FUTURE_UPDATER =
43 AtomicReferenceFieldUpdater.newUpdater(Cache.Entries.class, ScheduledFuture.class, "expirationFuture");
44
45 private static final ScheduledFuture<?> CANCELLED = new ScheduledFuture<Object>() {
46
47 @Override
48 public boolean cancel(boolean mayInterruptIfRunning) {
49 return false;
50 }
51
52 @Override
53 public long getDelay(TimeUnit unit) {
54 // We ignore unit and always return the minimum value to ensure the TTL of the cancelled marker is
55 // the smallest.
56 return Long.MIN_VALUE;
57 }
58
59 @Override
60 public int compareTo(Delayed o) {
61 throw new UnsupportedOperationException();
62 }
63
64 @Override
65 public boolean isCancelled() {
66 return true;
67 }
68
69 @Override
70 public boolean isDone() {
71 return true;
72 }
73
74 @Override
75 public Object get() {
76 throw new UnsupportedOperationException();
77 }
78
79 @Override
80 public Object get(long timeout, TimeUnit unit) {
81 throw new UnsupportedOperationException();
82 }
83 };
84
85 // Two years are supported by all our EventLoop implementations and so safe to use as maximum.
86 // See also: https://github.com/netty/netty/commit/b47fb817991b42ec8808c7d26538f3f2464e1fa6
87 static final int MAX_SUPPORTED_TTL_SECS = (int) TimeUnit.DAYS.toSeconds(365 * 2);
88
89 private final ConcurrentMap<String, Entries> resolveCache = PlatformDependent.newConcurrentHashMap();
90
91 /**
92 * Remove everything from the cache.
93 */
94 final void clear() {
95 while (!resolveCache.isEmpty()) {
96 for (Iterator<Entry<String, Entries>> i = resolveCache.entrySet().iterator(); i.hasNext();) {
97 Map.Entry<String, Entries> e = i.next();
98 i.remove();
99
100 e.getValue().clearAndCancel();
101 }
102 }
103 }
104
105 /**
106 * Clear all entries (if anything exists) for the given hostname and return {@code true} if anything was removed.
107 */
108 final boolean clear(String hostname) {
109 Entries entries = resolveCache.remove(hostname);
110 return entries != null && entries.clearAndCancel();
111 }
112
113 /**
114 * Returns all caches entries for the given hostname.
115 */
116 final List<? extends E> get(String hostname) {
117 Entries entries = resolveCache.get(hostname);
118 return entries == null ? null : entries.get();
119 }
120
121 /**
122 * Cache a value for the given hostname that will automatically expire once the TTL is reached.
123 */
124 final void cache(String hostname, E value, int ttl, EventLoop loop) {
125 Entries entries = resolveCache.get(hostname);
126 if (entries == null) {
127 entries = new Entries(hostname);
128 Entries oldEntries = resolveCache.putIfAbsent(hostname, entries);
129 if (oldEntries != null) {
130 entries = oldEntries;
131 }
132 }
133 entries.add(value, ttl, loop);
134 }
135
136 /**
137 * Return the number of hostnames for which we have cached something.
138 */
139 final int size() {
140 return resolveCache.size();
141 }
142
143 /**
144 * Returns {@code true} if this entry should replace all other entries that are already cached for the hostname.
145 */
146 protected abstract boolean shouldReplaceAll(E entry);
147
148 /**
149 * Sort the {@link List} for a {@code hostname} before caching these.
150 */
151 protected void sortEntries(
152 @SuppressWarnings("unused") String hostname, @SuppressWarnings("unused") List<E> entries) {
153 // NOOP.
154 }
155
156 /**
157 * Returns {@code true} if both entries are equal.
158 */
159 protected abstract boolean equals(E entry, E otherEntry);
160
161 // Directly extend AtomicReference for intrinsics and also to keep memory overhead low.
162 private final class Entries extends AtomicReference<List<E>> implements Runnable {
163
164 private final String hostname;
165 // Needs to be package-private to be able to access it via the AtomicReferenceFieldUpdater
166 volatile ScheduledFuture<?> expirationFuture;
167
168 Entries(String hostname) {
169 super(Collections.<E>emptyList());
170 this.hostname = hostname;
171 }
172
173 void add(E e, int ttl, EventLoop loop) {
174 if (!shouldReplaceAll(e)) {
175 for (;;) {
176 List<E> entries = get();
177 if (!entries.isEmpty()) {
178 final E firstEntry = entries.get(0);
179 if (shouldReplaceAll(firstEntry)) {
180 assert entries.size() == 1;
181
182 if (compareAndSet(entries, singletonList(e))) {
183 scheduleCacheExpirationIfNeeded(ttl, loop);
184 return;
185 } else {
186 // Need to try again as CAS failed
187 continue;
188 }
189 }
190
191 // Create a new List for COW semantics
192 List<E> newEntries = new ArrayList<E>(entries.size() + 1);
193 int i = 0;
194 E replacedEntry = null;
195 do {
196 E entry = entries.get(i);
197 // Only add old entry if the address is not the same as the one we try to add as well.
198 // In this case we will skip it and just add the new entry as this may have
199 // more up-to-date data and cancel the old after we were able to update the cache.
200 if (!Cache.this.equals(e, entry)) {
201 newEntries.add(entry);
202 } else {
203 replacedEntry = entry;
204 newEntries.add(e);
205
206 ++i;
207 for (; i < entries.size(); ++i) {
208 newEntries.add(entries.get(i));
209 }
210 break;
211 }
212 } while (++i < entries.size());
213 if (replacedEntry == null) {
214 newEntries.add(e);
215 }
216 sortEntries(hostname, newEntries);
217
218 if (compareAndSet(entries, Collections.unmodifiableList(newEntries))) {
219 scheduleCacheExpirationIfNeeded(ttl, loop);
220 return;
221 }
222 } else if (compareAndSet(entries, singletonList(e))) {
223 scheduleCacheExpirationIfNeeded(ttl, loop);
224 return;
225 }
226 }
227 } else {
228 set(singletonList(e));
229 scheduleCacheExpirationIfNeeded(ttl, loop);
230 }
231 }
232
233 private void scheduleCacheExpirationIfNeeded(int ttl, EventLoop loop) {
234 for (;;) {
235 // We currently don't calculate a new TTL when we need to retry the CAS as we don't expect this to
236 // be invoked very concurrently and also we use SECONDS anyway. If this ever becomes a problem
237 // we can reconsider.
238 ScheduledFuture<?> oldFuture = FUTURE_UPDATER.get(this);
239 if (oldFuture == null || oldFuture.getDelay(TimeUnit.SECONDS) > ttl) {
240 ScheduledFuture<?> newFuture = loop.schedule(this, ttl, TimeUnit.SECONDS);
241 // It is possible that
242 // 1. task will fire in between this line, or
243 // 2. multiple timers may be set if there is concurrency
244 // (1) Shouldn't be a problem because we will fail the CAS and then the next loop will see CANCELLED
245 // so the ttl will not be less, and we will bail out of the loop.
246 // (2) This is a trade-off to avoid concurrency resulting in contention on a synchronized block.
247 if (FUTURE_UPDATER.compareAndSet(this, oldFuture, newFuture)) {
248 if (oldFuture != null) {
249 oldFuture.cancel(true);
250 }
251 break;
252 } else {
253 // There was something else scheduled in the meantime... Cancel and try again.
254 newFuture.cancel(true);
255 }
256 } else {
257 break;
258 }
259 }
260 }
261
262 boolean clearAndCancel() {
263 List<E> entries = getAndSet(Collections.<E>emptyList());
264 if (entries.isEmpty()) {
265 return false;
266 }
267
268 ScheduledFuture<?> expirationFuture = FUTURE_UPDATER.getAndSet(this, CANCELLED);
269 if (expirationFuture != null) {
270 expirationFuture.cancel(false);
271 }
272
273 return true;
274 }
275
276 @Override
277 public void run() {
278 // We always remove all entries for a hostname once one entry expire. This is not the
279 // most efficient to do but this way we can guarantee that if a DnsResolver
280 // be configured to prefer one ip family over the other we will not return unexpected
281 // results to the enduser if one of the A or AAAA records has different TTL settings.
282 //
283 // As a TTL is just a hint of the maximum time a cache is allowed to cache stuff it's
284 // completely fine to remove the entry even if the TTL is not reached yet.
285 //
286 // See https://github.com/netty/netty/issues/7329
287 resolveCache.remove(hostname, this);
288
289 clearAndCancel();
290 }
291 }
292 }