View Javadoc

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