1 /* 2 * Copyright (C) 2008 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 package java.lang; 18 19 /* 20 * Android's thread local is not derived from Harmony's classlib. It is used in 21 * Harmony's DRLVM, however, whose source is here: 22 * http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/kernel_classes/ 23 */ 24 25 import java.lang.ref.WeakReference; 26 import java.lang.ref.Reference; 27 import java.util.concurrent.atomic.AtomicInteger; 28 29 /** 30 * Implements a thread-local storage, that is, a variable for which each thread 31 * has its own value. All threads share the same {@code ThreadLocal} object, 32 * but each sees a different value when accessing it, and changes made by one 33 * thread do not affect the other threads. The implementation supports 34 * {@code null} values. 35 * 36 * @see java.lang.Thread 37 * @author Bob Lee 38 */ 39 public class ThreadLocal<T> { 40 41 /* Thanks to Josh Bloch and Doug Lea for code reviews and impl advice. */ 42 43 /** 44 * Creates a new thread-local variable. 45 */ 46 public ThreadLocal() {} 47 48 /** 49 * Returns the value of this variable for the current thread. If an entry 50 * doesn't yet exist for this variable on this thread, this method will 51 * create an entry, populating the value with the result of 52 * {@link #initialValue()}. 53 * 54 * @return the current value of the variable for the calling thread. 55 */ 56 @SuppressWarnings("unchecked") 57 public T get() { 58 // Optimized for the fast path. 59 Thread currentThread = Thread.currentThread(); 60 Values values = values(currentThread); 61 if (values != null) { 62 Object[] table = values.table; 63 int index = hash & values.mask; 64 if (this.reference == table[index]) { 65 return (T) table[index + 1]; 66 } 67 } else { 68 values = initializeValues(currentThread); 69 } 70 71 return (T) values.getAfterMiss(this); 72 } 73 74 /** 75 * Provides the initial value of this variable for the current thread. 76 * The default implementation returns {@code null}. 77 * 78 * @return the initial value of the variable. 79 */ 80 protected T initialValue() { 81 return null; 82 } 83 84 /** 85 * Sets the value of this variable for the current thread. If set to 86 * {@code null}, the value will be set to null and the underlying entry will 87 * still be present. 88 * 89 * @param value the new value of the variable for the caller thread. 90 */ 91 public void set(T value) { 92 Thread currentThread = Thread.currentThread(); 93 Values values = values(currentThread); 94 if (values == null) { 95 values = initializeValues(currentThread); 96 } 97 values.put(this, value); 98 } 99 100 /** 101 * Removes the entry for this variable in the current thread. If this call 102 * is followed by a {@link #get()} before a {@link #set}, 103 * {@code #get()} will call {@link #initialValue()} and create a new 104 * entry with the resulting value. 105 * 106 * @since 1.5 107 */ 108 public void remove() { 109 Thread currentThread = Thread.currentThread(); 110 Values values = values(currentThread); 111 if (values != null) { 112 values.remove(this); 113 } 114 } 115 116 /** 117 * Creates Values instance for this thread and variable type. 118 */ 119 Values initializeValues(Thread current) { 120 return current.localValues = new Values(); 121 } 122 123 /** 124 * Gets Values instance for this thread and variable type. 125 */ 126 Values values(Thread current) { 127 return current.localValues; 128 } 129 130 /** Weak reference to this thread local instance. */ 131 private final Reference<ThreadLocal<T>> reference 132 = new WeakReference<ThreadLocal<T>>(this); 133 134 /** Hash counter. */ 135 private static AtomicInteger hashCounter = new AtomicInteger(0); 136 137 /** 138 * Internal hash. We deliberately don't bother with #hashCode(). 139 * Hashes must be even. This ensures that the result of 140 * (hash & (table.length - 1)) points to a key and not a value. 141 * 142 * We increment by Doug Lea's Magic Number(TM) (*2 since keys are in 143 * every other bucket) to help prevent clustering. 144 */ 145 private final int hash = hashCounter.getAndAdd(0x61c88647 << 1); 146 147 /** 148 * Per-thread map of ThreadLocal instances to values. 149 */ 150 static class Values { 151 152 /** 153 * Size must always be a power of 2. 154 */ 155 private static final int INITIAL_SIZE = 16; 156 157 /** 158 * Placeholder for deleted entries. 159 */ 160 private static final Object TOMBSTONE = new Object(); 161 162 /** 163 * Map entries. Contains alternating keys (ThreadLocal) and values. 164 * The length is always a power of 2. 165 */ 166 private Object[] table; 167 168 /** Used to turn hashes into indices. */ 169 private int mask; 170 171 /** Number of live entries. */ 172 private int size; 173 174 /** Number of tombstones. */ 175 private int tombstones; 176 177 /** Maximum number of live entries and tombstones. */ 178 private int maximumLoad; 179 180 /** Points to the next cell to clean up. */ 181 private int clean; 182 183 /** 184 * Constructs a new, empty instance. 185 */ 186 Values() { 187 initializeTable(INITIAL_SIZE); 188 this.size = 0; 189 this.tombstones = 0; 190 } 191 192 /** 193 * Used for InheritableThreadLocals. 194 */ 195 Values(Values fromParent) { 196 this.table = fromParent.table.clone(); 197 this.mask = fromParent.mask; 198 this.size = fromParent.size; 199 this.tombstones = fromParent.tombstones; 200 this.maximumLoad = fromParent.maximumLoad; 201 this.clean = fromParent.clean; 202 inheritValues(fromParent); 203 } 204 205 /** 206 * Inherits values from a parent thread. 207 */ 208 @SuppressWarnings({"unchecked"}) 209 private void inheritValues(Values fromParent) { 210 // Transfer values from parent to child thread. 211 Object[] table = this.table; 212 for (int i = table.length - 2; i >= 0; i -= 2) { 213 Object k = table[i]; 214 215 if (k == null || k == TOMBSTONE) { 216 // Skip this entry. 217 continue; 218 } 219 220 // The table can only contain null, tombstones and references. 221 Reference<InheritableThreadLocal<?>> reference 222 = (Reference<InheritableThreadLocal<?>>) k; 223 // Raw type enables us to pass in an Object below. 224 InheritableThreadLocal key = reference.get(); 225 if (key != null) { 226 // Replace value with filtered value. 227 // We should just let exceptions bubble out and tank 228 // the thread creation 229 table[i + 1] = key.childValue(fromParent.table[i + 1]); 230 } else { 231 // The key was reclaimed. 232 table[i] = TOMBSTONE; 233 table[i + 1] = null; 234 fromParent.table[i] = TOMBSTONE; 235 fromParent.table[i + 1] = null; 236 237 tombstones++; 238 fromParent.tombstones++; 239 240 size--; 241 fromParent.size--; 242 } 243 } 244 } 245 246 /** 247 * Creates a new, empty table with the given capacity. 248 */ 249 private void initializeTable(int capacity) { 250 this.table = new Object[capacity << 1]; 251 this.mask = table.length - 1; 252 this.clean = 0; 253 this.maximumLoad = capacity * 2 / 3; // 2/3 254 } 255 256 /** 257 * Cleans up after garbage-collected thread locals. 258 */ 259 private void cleanUp() { 260 if (rehash()) { 261 // If we rehashed, we needn't clean up (clean up happens as 262 // a side effect). 263 return; 264 } 265 266 if (size == 0) { 267 // No live entries == nothing to clean. 268 return; 269 } 270 271 // Clean log(table.length) entries picking up where we left off 272 // last time. 273 int index = clean; 274 Object[] table = this.table; 275 for (int counter = table.length; counter > 0; counter >>= 1, 276 index = next(index)) { 277 Object k = table[index]; 278 279 if (k == TOMBSTONE || k == null) { 280 continue; // on to next entry 281 } 282 283 // The table can only contain null, tombstones and references. 284 @SuppressWarnings("unchecked") 285 Reference<ThreadLocal<?>> reference 286 = (Reference<ThreadLocal<?>>) k; 287 if (reference.get() == null) { 288 // This thread local was reclaimed by the garbage collector. 289 table[index] = TOMBSTONE; 290 table[index + 1] = null; 291 tombstones++; 292 size--; 293 } 294 } 295 296 // Point cursor to next index. 297 clean = index; 298 } 299 300 /** 301 * Rehashes the table, expanding or contracting it as necessary. 302 * Gets rid of tombstones. Returns true if a rehash occurred. 303 * We must rehash every time we fill a null slot; we depend on the 304 * presence of null slots to end searches (otherwise, we'll infinitely 305 * loop). 306 */ 307 private boolean rehash() { 308 if (tombstones + size < maximumLoad) { 309 return false; 310 } 311 312 int capacity = table.length >> 1; 313 314 // Default to the same capacity. This will create a table of the 315 // same size and move over the live entries, analogous to a 316 // garbage collection. This should only happen if you churn a 317 // bunch of thread local garbage (removing and reinserting 318 // the same thread locals over and over will overwrite tombstones 319 // and not fill up the table). 320 int newCapacity = capacity; 321 322 if (size > (capacity >> 1)) { 323 // More than 1/2 filled w/ live entries. 324 // Double size. 325 newCapacity = capacity << 1; 326 } 327 328 Object[] oldTable = this.table; 329 330 // Allocate new table. 331 initializeTable(newCapacity); 332 333 // We won't have any tombstones after this. 334 this.tombstones = 0; 335 336 // If we have no live entries, we can quit here. 337 if (size == 0) { 338 return true; 339 } 340 341 // Move over entries. 342 for (int i = oldTable.length - 2; i >= 0; i -= 2) { 343 Object k = oldTable[i]; 344 if (k == null || k == TOMBSTONE) { 345 // Skip this entry. 346 continue; 347 } 348 349 // The table can only contain null, tombstones and references. 350 @SuppressWarnings("unchecked") 351 Reference<ThreadLocal<?>> reference 352 = (Reference<ThreadLocal<?>>) k; 353 ThreadLocal<?> key = reference.get(); 354 if (key != null) { 355 // Entry is still live. Move it over. 356 add(key, oldTable[i + 1]); 357 } else { 358 // The key was reclaimed. 359 size--; 360 } 361 } 362 363 return true; 364 } 365 366 /** 367 * Adds an entry during rehashing. Compared to put(), this method 368 * doesn't have to clean up, check for existing entries, account for 369 * tombstones, etc. 370 */ 371 void add(ThreadLocal<?> key, Object value) { 372 for (int index = key.hash & mask;; index = next(index)) { 373 Object k = table[index]; 374 if (k == null) { 375 table[index] = key.reference; 376 table[index + 1] = value; 377 return; 378 } 379 } 380 } 381 382 /** 383 * Sets entry for given ThreadLocal to given value, creating an 384 * entry if necessary. 385 */ 386 void put(ThreadLocal<?> key, Object value) { 387 cleanUp(); 388 389 // Keep track of first tombstone. That's where we want to go back 390 // and add an entry if necessary. 391 int firstTombstone = -1; 392 393 for (int index = key.hash & mask;; index = next(index)) { 394 Object k = table[index]; 395 396 if (k == key.reference) { 397 // Replace existing entry. 398 table[index + 1] = value; 399 return; 400 } 401 402 if (k == null) { 403 if (firstTombstone == -1) { 404 // Fill in null slot. 405 table[index] = key.reference; 406 table[index + 1] = value; 407 size++; 408 return; 409 } 410 411 // Go back and replace first tombstone. 412 table[firstTombstone] = key.reference; 413 table[firstTombstone + 1] = value; 414 tombstones--; 415 size++; 416 return; 417 } 418 419 // Remember first tombstone. 420 if (firstTombstone == -1 && k == TOMBSTONE) { 421 firstTombstone = index; 422 } 423 } 424 } 425 426 /** 427 * Gets value for given ThreadLocal after not finding it in the first 428 * slot. 429 */ 430 Object getAfterMiss(ThreadLocal<?> key) { 431 Object[] table = this.table; 432 int index = key.hash & mask; 433 434 // If the first slot is empty, the search is over. 435 if (table[index] == null) { 436 Object value = key.initialValue(); 437 438 // If the table is still the same and the slot is still empty... 439 if (this.table == table && table[index] == null) { 440 table[index] = key.reference; 441 table[index + 1] = value; 442 size++; 443 444 cleanUp(); 445 return value; 446 } 447 448 // The table changed during initialValue(). 449 put(key, value); 450 return value; 451 } 452 453 // Keep track of first tombstone. That's where we want to go back 454 // and add an entry if necessary. 455 int firstTombstone = -1; 456 457 // Continue search. 458 for (index = next(index);; index = next(index)) { 459 Object reference = table[index]; 460 if (reference == key.reference) { 461 return table[index + 1]; 462 } 463 464 // If no entry was found... 465 if (reference == null) { 466 Object value = key.initialValue(); 467 468 // If the table is still the same... 469 if (this.table == table) { 470 // If we passed a tombstone and that slot still 471 // contains a tombstone... 472 if (firstTombstone > -1 473 && table[firstTombstone] == TOMBSTONE) { 474 table[firstTombstone] = key.reference; 475 table[firstTombstone + 1] = value; 476 tombstones--; 477 size++; 478 479 // No need to clean up here. We aren't filling 480 // in a null slot. 481 return value; 482 } 483 484 // If this slot is still empty... 485 if (table[index] == null) { 486 table[index] = key.reference; 487 table[index + 1] = value; 488 size++; 489 490 cleanUp(); 491 return value; 492 } 493 } 494 495 // The table changed during initialValue(). 496 put(key, value); 497 return value; 498 } 499 500 if (firstTombstone == -1 && reference == TOMBSTONE) { 501 // Keep track of this tombstone so we can overwrite it. 502 firstTombstone = index; 503 } 504 } 505 } 506 507 /** 508 * Removes entry for the given ThreadLocal. 509 */ 510 void remove(ThreadLocal<?> key) { 511 cleanUp(); 512 513 for (int index = key.hash & mask;; index = next(index)) { 514 Object reference = table[index]; 515 516 if (reference == key.reference) { 517 // Success! 518 table[index] = TOMBSTONE; 519 table[index + 1] = null; 520 tombstones++; 521 size--; 522 return; 523 } 524 525 if (reference == null) { 526 // No entry found. 527 return; 528 } 529 } 530 } 531 532 /** 533 * Gets the next index. If we're at the end of the table, we wrap back 534 * around to 0. 535 */ 536 private int next(int index) { 537 return (index + 2) & mask; 538 } 539 } 540 } 541
