001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.util;
019
020import java.util.concurrent.atomic.AtomicBoolean;
021import java.util.concurrent.atomic.AtomicLongFieldUpdater;
022import java.util.concurrent.atomic.AtomicReference;
023
024import org.apache.yetus.audience.InterfaceAudience;
025
026/**
027 * High scalable counter. Thread safe.
028 * @deprecated since 2.0.0 and will be removed in 3.0.0. Use
029 *   {@link java.util.concurrent.atomic.LongAdder} instead.
030 * @see java.util.concurrent.atomic.LongAdder
031 * @see <a href="https://issues.apache.org/jira/browse/HBASE-7612">HBASE-7612</a>
032 */
033@InterfaceAudience.Public
034@Deprecated
035public class Counter {
036  private static final int MAX_CELLS_LENGTH = 1 << 20;
037
038  private static class Cell {
039    // Pads are added around the value to avoid cache-line contention with
040    // another cell's value. The cache-line size is expected to be equal to or
041    // less than about 128 Bytes (= 64 Bits * 16).
042
043    @SuppressWarnings("unused")
044    volatile long p0, p1, p2, p3, p4, p5, p6;
045    volatile long value;
046    @SuppressWarnings("unused")
047    volatile long q0, q1, q2, q3, q4, q5, q6;
048
049    static final AtomicLongFieldUpdater<Cell> valueUpdater =
050        AtomicLongFieldUpdater.newUpdater(Cell.class, "value");
051
052    Cell() {}
053
054    Cell(long initValue) {
055      value = initValue;
056    }
057
058    long get() {
059      return value;
060    }
061
062    boolean add(long delta) {
063      long current = value;
064      return valueUpdater.compareAndSet(this, current, current + delta);
065    }
066  }
067
068  private static class Container {
069    /** The length should be a power of 2. */
070    final Cell[] cells;
071
072    /** True if a new extended container is going to replace this. */
073    final AtomicBoolean demoted = new AtomicBoolean();
074
075    Container(Cell cell) {
076      this(new Cell[] { cell });
077    }
078
079    /**
080     * @param cells the length should be a power of 2
081     */
082    Container(Cell[] cells) {
083      this.cells = cells;
084    }
085  }
086
087  private final AtomicReference<Container> containerRef;
088
089  public Counter() {
090    this(new Cell());
091  }
092
093  public Counter(long initValue) {
094    this(new Cell(initValue));
095  }
096
097  private Counter(Cell initCell) {
098    containerRef = new AtomicReference<>(new Container(initCell));
099  }
100
101  private static int hash() {
102    // The logic is borrowed from high-scale-lib's ConcurrentAutoTable.
103
104    int h = System.identityHashCode(Thread.currentThread());
105    // You would think that System.identityHashCode on the current thread
106    // would be a good hash fcn, but actually on SunOS 5.8 it is pretty lousy
107    // in the low bits.
108
109    h ^= (h >>> 20) ^ (h >>> 12); // Bit spreader, borrowed from Doug Lea
110    h ^= (h >>>  7) ^ (h >>>  4);
111    return h;
112  }
113
114  public void add(long delta) {
115    Container container = containerRef.get();
116    Cell[] cells = container.cells;
117    int mask = cells.length - 1;
118
119    int baseIndex = hash();
120    if(cells[baseIndex & mask].add(delta)) {
121      return;
122    }
123
124    int index = baseIndex + 1;
125    while(true) {
126      if(cells[index & mask].add(delta)) {
127        break;
128      }
129      index++;
130    }
131
132    if(index - baseIndex >= cells.length &&
133        cells.length < MAX_CELLS_LENGTH &&
134        container.demoted.compareAndSet(false, true)) {
135
136      if(containerRef.get() == container) {
137        Cell[] newCells = new Cell[cells.length * 2];
138        System.arraycopy(cells, 0, newCells, 0, cells.length);
139        for(int i = cells.length; i < newCells.length; i++) {
140          newCells[i] = new Cell();
141          // Fill all of the elements with instances. Creating a cell on demand
142          // and putting it into the array makes a concurrent problem about
143          // visibility or, in other words, happens-before relation, because
144          // each element of the array is not volatile so that you should
145          // establish the relation by some piggybacking.
146        }
147        containerRef.compareAndSet(container, new Container(newCells));
148      }
149    }
150  }
151
152  public void increment() {
153    add(1);
154  }
155
156  public void decrement() {
157    add(-1);
158  }
159
160  public void set(long value) {
161    containerRef.set(new Container(new Cell(value)));
162  }
163
164  public long get() {
165    long sum = 0;
166    for(Cell cell : containerRef.get().cells) {
167      sum += cell.get();
168    }
169    return sum;
170  }
171
172  @Override
173  public String toString() {
174    Cell[] cells = containerRef.get().cells;
175
176    long min = Long.MAX_VALUE;
177    long max = Long.MIN_VALUE;
178    long sum = 0;
179
180    for(Cell cell : cells) {
181      long value = cell.get();
182      sum += value;
183      if(min > value) { min = value; }
184      if(max < value) { max = value; }
185    }
186
187    return new StringBuilder(100)
188    .append("[value=").append(sum)
189    .append(", cells=[length=").append(cells.length)
190    .append(", min=").append(min)
191    .append(", max=").append(max)
192    .append("]]").toString();
193  }
194}