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;
023import org.apache.yetus.audience.InterfaceAudience;
024
025/**
026 * High scalable counter. Thread safe.
027 * @deprecated since 2.0.0 and will be removed in 3.0.0. Use
028 *             {@link java.util.concurrent.atomic.LongAdder} instead.
029 * @see java.util.concurrent.atomic.LongAdder
030 * @see <a href="https://issues.apache.org/jira/browse/HBASE-7612">HBASE-7612</a>
031 */
032@InterfaceAudience.Public
033@Deprecated
034public class Counter {
035  private static final int MAX_CELLS_LENGTH = 1 << 20;
036
037  private static class Cell {
038    // Pads are added around the value to avoid cache-line contention with
039    // another cell's value. The cache-line size is expected to be equal to or
040    // less than about 128 Bytes (= 64 Bits * 16).
041
042    @SuppressWarnings("unused")
043    volatile long p0, p1, p2, p3, p4, p5, p6;
044    volatile long value;
045    @SuppressWarnings("unused")
046    volatile long q0, q1, q2, q3, q4, q5, q6;
047
048    static final AtomicLongFieldUpdater<Cell> valueUpdater =
049      AtomicLongFieldUpdater.newUpdater(Cell.class, "value");
050
051    Cell() {
052    }
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 (
133      index - baseIndex >= cells.length && cells.length < MAX_CELLS_LENGTH
134        && container.demoted.compareAndSet(false, true)
135    ) {
136
137      if (containerRef.get() == container) {
138        Cell[] newCells = new Cell[cells.length * 2];
139        System.arraycopy(cells, 0, newCells, 0, cells.length);
140        for (int i = cells.length; i < newCells.length; i++) {
141          newCells[i] = new Cell();
142          // Fill all of the elements with instances. Creating a cell on demand
143          // and putting it into the array makes a concurrent problem about
144          // visibility or, in other words, happens-before relation, because
145          // each element of the array is not volatile so that you should
146          // establish the relation by some piggybacking.
147        }
148        containerRef.compareAndSet(container, new Container(newCells));
149      }
150    }
151  }
152
153  public void increment() {
154    add(1);
155  }
156
157  public void decrement() {
158    add(-1);
159  }
160
161  public void set(long value) {
162    containerRef.set(new Container(new Cell(value)));
163  }
164
165  public long get() {
166    long sum = 0;
167    for (Cell cell : containerRef.get().cells) {
168      sum += cell.get();
169    }
170    return sum;
171  }
172
173  @Override
174  public String toString() {
175    Cell[] cells = containerRef.get().cells;
176
177    long min = Long.MAX_VALUE;
178    long max = Long.MIN_VALUE;
179    long sum = 0;
180
181    for (Cell cell : cells) {
182      long value = cell.get();
183      sum += value;
184      if (min > value) {
185        min = value;
186      }
187      if (max < value) {
188        max = value;
189      }
190    }
191
192    return new StringBuilder(100).append("[value=").append(sum).append(", cells=[length=")
193      .append(cells.length).append(", min=").append(min).append(", max=").append(max).append("]]")
194      .toString();
195  }
196}