View Javadoc

1   /*
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
18   */
19  package org.apache.hadoop.hbase.util;
20  
21  import java.io.IOException;
22  import java.io.InterruptedIOException;
23  import java.util.concurrent.ConcurrentHashMap;
24  import java.util.concurrent.ConcurrentMap;
25  
26  import org.apache.hadoop.classification.InterfaceAudience;
27  
28  /**
29   * Allows multiple concurrent clients to lock on a numeric id with a minimal
30   * memory overhead. The intended usage is as follows:
31   *
32   * <pre>
33   * IdLock.Entry lockEntry = idLock.getLockEntry(id);
34   * try {
35   *   // User code.
36   * } finally {
37   *   idLock.releaseLockEntry(lockEntry);
38   * }</pre>
39   */
40  @InterfaceAudience.Private
41  public class IdLock {
42  
43    /** An entry returned to the client as a lock object */
44    public static class Entry {
45      private final long id;
46      private int numWaiters;
47      private boolean isLocked = true;
48  
49      private Entry(long id) {
50        this.id = id;
51      }
52  
53      public String toString() {
54        return "id=" + id + ", numWaiter=" + numWaiters + ", isLocked="
55            + isLocked;
56      }
57    }
58  
59    private ConcurrentMap<Long, Entry> map =
60        new ConcurrentHashMap<Long, Entry>();
61  
62    /**
63     * Blocks until the lock corresponding to the given id is acquired.
64     *
65     * @param id an arbitrary number to lock on
66     * @return an "entry" to pass to {@link #releaseLockEntry(Entry)} to release
67     *         the lock
68     * @throws IOException if interrupted
69     */
70    public Entry getLockEntry(long id) throws IOException {
71      Entry entry = new Entry(id);
72      Entry existing;
73      while ((existing = map.putIfAbsent(entry.id, entry)) != null) {
74        synchronized (existing) {
75          if (existing.isLocked) {
76            ++existing.numWaiters;  // Add ourselves to waiters.
77            while (existing.isLocked) {
78              try {
79                existing.wait();
80              } catch (InterruptedException e) {
81                --existing.numWaiters;  // Remove ourselves from waiters.
82                throw new InterruptedIOException(
83                    "Interrupted waiting to acquire sparse lock");
84              }
85            }
86  
87            --existing.numWaiters;  // Remove ourselves from waiters.
88            existing.isLocked = true;
89            return existing;
90          }
91          // If the entry is not locked, it might already be deleted from the
92          // map, so we cannot return it. We need to get our entry into the map
93          // or get someone else's locked entry.
94        }
95      }
96      return entry;
97    }
98  
99    /**
100    * Must be called in a finally block to decrease the internal counter and
101    * remove the monitor object for the given id if the caller is the last
102    * client.
103    *
104    * @param entry the return value of {@link #getLockEntry(long)}
105    */
106   public void releaseLockEntry(Entry entry) {
107     synchronized (entry) {
108       entry.isLocked = false;
109       if (entry.numWaiters > 0) {
110         entry.notify();
111       } else {
112         map.remove(entry.id);
113       }
114     }
115   }
116 
117   /** For testing */
118   void assertMapEmpty() {
119     assert map.size() == 0;
120   }
121 
122 }