View Javadoc
1   /*
2    * Copyright 2012 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    *   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, 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.util;
17  
18  import io.netty.util.internal.PlatformDependent;
19  
20  import java.util.concurrent.atomic.AtomicReference;
21  import java.util.concurrent.atomic.AtomicReferenceArray;
22  import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
23  
24  /**
25   * Default {@link AttributeMap} implementation which use simple synchronization per bucket to keep the memory overhead
26   * as low as possible.
27   */
28  public class DefaultAttributeMap implements AttributeMap {
29  
30      @SuppressWarnings("rawtypes")
31      private static final AtomicReferenceFieldUpdater<DefaultAttributeMap, AtomicReferenceArray> updater;
32  
33      static {
34          @SuppressWarnings("rawtypes")
35          AtomicReferenceFieldUpdater<DefaultAttributeMap, AtomicReferenceArray> referenceFieldUpdater =
36                  PlatformDependent.newAtomicReferenceFieldUpdater(DefaultAttributeMap.class, "attributes");
37          if (referenceFieldUpdater == null) {
38              referenceFieldUpdater = AtomicReferenceFieldUpdater
39                              .newUpdater(DefaultAttributeMap.class, AtomicReferenceArray.class, "attributes");
40          }
41          updater = referenceFieldUpdater;
42      }
43  
44      private static final int BUCKET_SIZE = 4;
45      private static final int MASK = BUCKET_SIZE  - 1;
46  
47      // Initialize lazily to reduce memory consumption; updated by AtomicReferenceFieldUpdater above.
48      @SuppressWarnings("UnusedDeclaration")
49      private volatile AtomicReferenceArray<DefaultAttribute<?>> attributes;
50  
51      @SuppressWarnings("unchecked")
52      @Override
53      public <T> Attribute<T> attr(AttributeKey<T> key) {
54          if (key == null) {
55              throw new NullPointerException("key");
56          }
57          AtomicReferenceArray<DefaultAttribute<?>> attributes = this.attributes;
58          if (attributes == null) {
59              // Not using ConcurrentHashMap due to high memory consumption.
60              attributes = new AtomicReferenceArray<DefaultAttribute<?>>(BUCKET_SIZE);
61  
62              if (!updater.compareAndSet(this, null, attributes)) {
63                  attributes = this.attributes;
64              }
65          }
66  
67          int i = index(key);
68          DefaultAttribute<?> head = attributes.get(i);
69          if (head == null) {
70              // No head exists yet which means we may be able to add the attribute without synchronization and just
71              // use compare and set. At worst we need to fallback to synchronization
72              head = new DefaultAttribute(key);
73              if (attributes.compareAndSet(i, null, head)) {
74                  // we were able to add it so return the head right away
75                  return (Attribute<T>) head;
76              } else {
77                  head = attributes.get(i);
78              }
79          }
80  
81          synchronized (head) {
82              DefaultAttribute<?> curr = head;
83              for (;;) {
84                  if (!curr.removed && curr.key == key) {
85                      return (Attribute<T>) curr;
86                  }
87  
88                  DefaultAttribute<?> next = curr.next;
89                  if (next == null) {
90                      DefaultAttribute<T> attr = new DefaultAttribute<T>(head, key);
91                      curr.next =  attr;
92                      attr.prev = curr;
93                      return attr;
94                  } else {
95                      curr = next;
96                  }
97              }
98          }
99      }
100 
101     @Override
102     public <T> boolean hasAttr(AttributeKey<T> key) {
103         if (key == null) {
104             throw new NullPointerException("key");
105         }
106         AtomicReferenceArray<DefaultAttribute<?>> attributes = this.attributes;
107         if (attributes == null) {
108             // no attribute exists
109             return false;
110         }
111 
112         int i = index(key);
113         DefaultAttribute<?> head = attributes.get(i);
114         if (head == null) {
115             // No attribute exists which point to the bucket in which the head should be located
116             return false;
117         }
118 
119         // check on the head can be done without synchronization
120         if (head.key == key && !head.removed) {
121             return true;
122         }
123 
124         synchronized (head) {
125             // we need to synchronize on the head
126             DefaultAttribute<?> curr = head.next;
127             while (curr != null) {
128                 if (!curr.removed && curr.key == key) {
129                     return true;
130                 }
131                 curr = curr.next;
132             }
133             return false;
134         }
135     }
136 
137     private static int index(AttributeKey<?> key) {
138         return key.id() & MASK;
139     }
140 
141     @SuppressWarnings("serial")
142     private static final class DefaultAttribute<T> extends AtomicReference<T> implements Attribute<T> {
143 
144         private static final long serialVersionUID = -2661411462200283011L;
145 
146         // The head of the linked-list this attribute belongs to, which may be itself
147         private final DefaultAttribute<?> head;
148         private final AttributeKey<T> key;
149 
150         // Double-linked list to prev and next node to allow fast removal
151         private DefaultAttribute<?> prev;
152         private DefaultAttribute<?> next;
153 
154         // Will be set to true one the attribute is removed via getAndRemove() or remove()
155         private volatile boolean removed;
156 
157         DefaultAttribute(DefaultAttribute<?> head, AttributeKey<T> key) {
158             this.head = head;
159             this.key = key;
160         }
161 
162         DefaultAttribute(AttributeKey<T> key) {
163             head = this;
164             this.key = key;
165         }
166 
167         @Override
168         public AttributeKey<T> key() {
169             return key;
170         }
171 
172         @Override
173         public T setIfAbsent(T value) {
174             while (!compareAndSet(null, value)) {
175                 T old = get();
176                 if (old != null) {
177                     return old;
178                 }
179             }
180             return null;
181         }
182 
183         @Override
184         public T getAndRemove() {
185             removed = true;
186             T oldValue = getAndSet(null);
187             remove0();
188             return oldValue;
189         }
190 
191         @Override
192         public void remove() {
193             removed = true;
194             set(null);
195             remove0();
196         }
197 
198         private void remove0() {
199             synchronized (head) {
200                 // We only update the linked-list structure if prev != null because if it is null this
201                 // DefaultAttribute acts also as head. The head must never be removed completely and just be
202                 // marked as removed as all synchronization is done on the head itself for each bucket.
203                 // The head itself will be GC'ed once the DefaultAttributeMap is GC'ed. So at most 5 heads will
204                 // be removed lazy as the array size is 5.
205                 if (prev != null) {
206                     prev.next = next;
207 
208                     if (next != null) {
209                         next.prev = prev;
210                     }
211                 }
212             }
213         }
214     }
215 }