content: /*
   * Copyright (C) 2013 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.android.internal.app.procstats;
  
  import android.os.Build;
  import android.os.Parcel;
  import android.util.EventLog;
  import android.util.Slog;
  import libcore.util.EmptyArray;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  
  import com.android.internal.util.GrowingArrayUtils;
  
  /**
   * Class that contains a set of tables mapping byte ids to long values.
   *
   * This class is used to store the ProcessStats data.  This data happens to be
   * a set of very sparse tables, that is mostly append or overwrite, with infrequent
   * resets of the data.
   *
   * Data is stored as a list of large long[] arrays containing the actual values.  There are a
   * set of Table objects that each contain a small array mapping the byte IDs to a position
   * in the larger arrays.
   *
   * The data itself is either a single long value or a range of long values which are always
   * stored continguously in one of the long arrays. When the caller allocates a slot with
   * getOrAddKey, an int key is returned.  That key can be re-retreived with getKey without
   * allocating the value.  The data can then be set or retrieved with that key.
   */
  public class SparseMappingTable {
      private static final String TAG = "SparseMappingTable";
  
      // How big each array is.
      public static final int ARRAY_SIZE = 4096;
  
      public static final int INVALID_KEY = 0xffffffff;
  
      // Where the "type"/"state" part of the data appears in an offset integer.
      private static final int ID_SHIFT = 0;
      private static final int ID_MASK = 0xff;
      // Where the "which array" part of the data appears in an offset integer.
      private static final int ARRAY_SHIFT = 8;
      private static final int ARRAY_MASK = 0xff;
      // Where the "index into array" part of the data appears in an offset integer.
      private static final int INDEX_SHIFT = 16;
      private static final int INDEX_MASK = 0xffff;
  
      private int mSequence;
      private int mNextIndex;
      private final ArrayList<long[]> mLongs = new ArrayList<long[]>();
  
      /**
       * A table of data as stored in a SparseMappingTable.
       */
      public static class Table {
          private SparseMappingTable mParent;
          private int mSequence = 1;
          private int[] mTable;
          private int mSize;
  
          public Table(SparseMappingTable parent) {
              mParent = parent;
              mSequence = parent.mSequence;
          }
  
          /**
           * Pulls the data from 'copyFrom' and stores it in our own longs table.
           *
           * @param copyFrom   The Table to copy from
           * @param valueCount The number of values to copy for each key
           */
          public void copyFrom(Table copyFrom, int valueCount) {
              mTable = null;
              mSize = 0;
  
              final int N = copyFrom.getKeyCount();
              for (int i=0; i<N; i++) {
                  final int theirKey = copyFrom.getKeyAt(i);
                  final long[] theirLongs = copyFrom.mParent.mLongs.get(getArrayFromKey(theirKey));
  
                  final byte id = SparseMappingTable.getIdFromKey(theirKey);
  
                  final int myKey = this.getOrAddKey((byte)id, valueCount);
                  final long[] myLongs = mParent.mLongs.get(getArrayFromKey(myKey));
  
                  System.arraycopy(theirLongs, getIndexFromKey(theirKey),
                          myLongs, getIndexFromKey(myKey), valueCount);
              }
          }
  
          /**
           * Allocates data in the buffer, and stores that key in the mapping for this
           * table.
           *
           * @param id    The id of the item (will be used in making the key)
           * @param count The number of bytes to allocate.  Must be less than
           *              SparseMappingTable.ARRAY_SIZE.
           *
           * @return The 'key' for this data value, which contains both the id itself
           *         and the location in the long arrays that the data is actually stored
           *         but should be considered opaque to the caller.
           */
          public int getOrAddKey(byte id, int count) {
              assertConsistency();
  
              final int idx = binarySearch(id);
              if (idx >= 0) {
                  // Found
                  return mTable[idx];
              } else {
                  // Not found. Need to allocate it.
  
                  // Get an array with enough space to store 'count' values.
                  final ArrayList<long[]> list = mParent.mLongs;
                  int whichArray = list.size()-1;
                  long[] array = list.get(whichArray);
                  if (mParent.mNextIndex + count > array.length) {
                      // if it won't fit then make a new array.
                      array = new long[ARRAY_SIZE];
                      list.add(array);
                      whichArray++;
                      mParent.mNextIndex = 0;
                  }
  
                  // The key is a combination of whichArray, which index in that array, and
                  // the table value itself, which will be used for lookup
                  final int key = (whichArray << ARRAY_SHIFT)
                          | (mParent.mNextIndex << INDEX_SHIFT)
                          | (((int)id) << ID_SHIFT);
  
                  mParent.mNextIndex += count;
  
                  // Store the key in the sparse lookup table for this Table object.
                  mTable = GrowingArrayUtils.insert(mTable != null ? mTable : EmptyArray.INT,
                          mSize, ~idx, key);
                  mSize++;
  
                  return key;
              }
          }
  
          /**
           * Looks up a key in the table.
           *
           * @return The key from this table or INVALID_KEY if the id is not found.
           */
          public int getKey(byte id) {
              assertConsistency();
  
              final int idx = binarySearch(id);
              if (idx >= 0) {
                  return mTable[idx];
              } else {
                  return INVALID_KEY;
              }
          }
  
          /**
           * Get the value for the given key and offset from that key.
           *
           * @param key   A key as obtained from getKey or getOrAddKey.
           */
          public long getValue(int key) {
              return getValue(key, 0);
          }
  
          /**
           * Get the value for the given key and offset from that key.
           *
           * @param key   A key as obtained from getKey or getOrAddKey.
           * @param index The offset from that key.  Must be less than the count
           *              provided to getOrAddKey when the space was allocated.
           *
           * @return the value, or 0 in case of an error
           */
          public long getValue(int key, int index) {
              assertConsistency();
  
              try {
                  final long[] array = mParent.mLongs.get(getArrayFromKey(key));
                  return array[getIndexFromKey(key) + index];
              } catch (IndexOutOfBoundsException ex) {
                  logOrThrow("key=0x" + Integer.toHexString(key)
                          + " index=" + index + " -- " + dumpInternalState(), ex);
                  return 0;
              }
          }
  
          /**
           * Set the value for the given id at offset 0 from that id.
           * If the id is not found, return 0 instead.
           *
           * @param id    The id of the item.
           */
          public long getValueForId(byte id) {
              return getValueForId(id, 0);
          }
  
          /**
           * Set the value for the given id and index offset from that id.
           * If the id is not found, return 0 instead.
           *
           * @param id    The id of the item.
           * @param index The offset from that key.  Must be less than the count
           *              provided to getOrAddKey when the space was allocated.
           */
          public long getValueForId(byte id, int index) {
              assertConsistency();
  
              final int idx = binarySearch(id);
              if (idx >= 0) {
                  final int key = mTable[idx];
                  try {
                      final long[] array = mParent.mLongs.get(getArrayFromKey(key));
                      return array[getIndexFromKey(key) + index];
                  } catch (IndexOutOfBoundsException ex) {
                      logOrThrow("id=0x" + Integer.toHexString(id) + " idx=" + idx
                              + " key=0x" + Integer.toHexString(key) + " index=" + index
                              + " -- " + dumpInternalState(), ex);
                      return 0;
                  }
              } else {
                  return 0;
              }
          }
  
          /**
           * Return the raw storage long[] for the given key.
           */
          public long[] getArrayForKey(int key) {
              assertConsistency();
  
              return mParent.mLongs.get(getArrayFromKey(key));
          }
  
          /**
           * Set the value for the given key and offset from that key.
           *
           * @param key   A key as obtained from getKey or getOrAddKey.
           * @param value The value to set.
           */
          public void setValue(int key, long value) {
              setValue(key, 0, value);
          }
  
          /**
           * Set the value for the given key and offset from that key.
           *
           * @param key   A key as obtained from getKey or getOrAddKey.
           * @param index The offset from that key.  Must be less than the count
           *              provided to getOrAddKey when the space was allocated.
           * @param value The value to set.
           */
          public void setValue(int key, int index, long value) {
              assertConsistency();
  
              if (value < 0) {
                  logOrThrow("can't store negative values"
                          + " key=0x" + Integer.toHexString(key)
                          + " index=" + index + " value=" + value
                          + " -- " + dumpInternalState());
                  return;
              }
  
              try {
                  final long[] array = mParent.mLongs.get(getArrayFromKey(key));
                  array[getIndexFromKey(key) + index] = value;
              } catch (IndexOutOfBoundsException ex) {
                  logOrThrow("key=0x" + Integer.toHexString(key)
                          + " index=" + index + " value=" + value
                          + " -- " + dumpInternalState(), ex);
                  return;
              }
          }
  
          /**
           * Clear out the table, and reset the sequence numbers so future writes
           * without allocations will assert.
           */
          public void resetTable() {
              // Clear out our table.
              mTable = null;
              mSize = 0;
  
              // Reset our sequence number.  This will make all read/write calls
              // start to fail, and then when we re-allocate it will be re-synced
              // to that of mParent.
              mSequence = mParent.mSequence;
          }
  
          /**
           * Write the keys stored in the table to the parcel. The parent must
           * be separately written. Does not save the actual data.
           */
          public void writeToParcel(Parcel out) {
              out.writeInt(mSequence);
              out.writeInt(mSize);
              for (int i=0; i<mSize; i++) {
                  out.writeInt(mTable[i]);
              }
          }
  
          /**
           * Read the keys from the parcel. The parent (with its long array) must
           * have been previously initialized.
           */
          public boolean readFromParcel(Parcel in) {
              // Read the state
              mSequence = in.readInt();
              mSize = in.readInt();
              if (mSize != 0) {
                  mTable = new int[mSize];
                  for (int i=0; i<mSize; i++) {
                      mTable[i] = in.readInt();
                  }
              } else {
                  mTable = null;
              }
  
              // Make sure we're all healthy
              if (validateKeys(true)) {
                  return true;
              } else {
                  // Clear it out
                  mSize = 0;
                  mTable = null;
                  return false;
              }
          }
  
          /**
           * Return the number of keys that have been added to this Table.
           */
          public int getKeyCount() {
              return mSize;
          }
  
          /**
           * Get the key at the given index in our table.
           */
          public int getKeyAt(int i) {
              return mTable[i];
          }
  
          /**
           * Throw an exception if one of a variety of internal consistency checks fails.
           */
          private void assertConsistency() {
              // Something with this checking isn't working and is triggering
              // more problems than it's helping to debug.
              //   Original bug: b/27045736
              //   New bug: b/27960286
              if (false) {
                  // Assert that our sequence number matches mParent's.  If it isn't that means
                  // we have been reset and our.  If our sequence is UNITIALIZED_SEQUENCE, then 
                  // it's possible that everything is working fine and we just haven't been
                  // written to since the last resetTable().
                  if (mSequence != mParent.mSequence) {
                      if (mSequence < mParent.mSequence) {
                          logOrThrow("Sequence mismatch. SparseMappingTable.reset()"
                                  + " called but not Table.resetTable() -- "
                                  + dumpInternalState());
                          return;
                      } else if (mSequence > mParent.mSequence) {
                          logOrThrow("Sequence mismatch. Table.resetTable()"
                                  + " called but not SparseMappingTable.reset() -- "
                                  + dumpInternalState());
                          return;
                      }
                  }
              }
          }
  
          /**
           * Finds the 'id' inside the array of length size (physical size of the array
           * is not used).
           *
           * @return The index of the array, or the bitwise not (~index) of where it
           * would go if you wanted to insert 'id' into the array.
           */
          private int binarySearch(byte id) {
              int lo = 0;
              int hi = mSize - 1;
  
              while (lo <= hi) {
                  int mid = (lo + hi) >>> 1;
                  byte midId = (byte)((mTable[mid] >> ID_SHIFT) & ID_MASK);
  
                  if (midId < id) {
                      lo = mid + 1;
                  } else if (midId > id) {
                      hi = mid - 1;
                  } else {
                      return mid;  // id found
                  }
              }
              return ~lo;  // id not present
          }
  
          /**
           * Check that all the keys are valid locations in the long arrays.
           *
           * If any aren't, log it and return false. Else return true.
           */
          private boolean validateKeys(boolean log) {
              ArrayList<long[]> longs = mParent.mLongs;
              final int longsSize = longs.size();
  
              final int N = mSize;
              for (int i=0; i<N; i++) {
                  final int key = mTable[i];
                  final int arrayIndex = getArrayFromKey(key);
                  final int index = getIndexFromKey(key);
                  if (arrayIndex >= longsSize || index >= longs.get(arrayIndex).length) {
                      if (log) {
                          Slog.w(TAG, "Invalid stats at index " + i + " -- " + dumpInternalState());
                      }
                      return false;
                  }
              }
  
              return true;
          }
  
          public String dumpInternalState() {
              StringBuilder sb = new StringBuilder();
              sb.append("SparseMappingTable.Table{mSequence=");
              sb.append(mSequence);
              sb.append(" mParent.mSequence=");
              sb.append(mParent.mSequence);
              sb.append(" mParent.mLongs.size()=");
              sb.append(mParent.mLongs.size());
              sb.append(" mSize=");
              sb.append(mSize);
              sb.append(" mTable=");
              if (mTable == null) {
                  sb.append("null");
              } else {
                  final int N = mTable.length;
                  sb.append('[');
                  for (int i=0; i<N; i++) {
                      final int key = mTable[i];
                      sb.append("0x");
                      sb.append(Integer.toHexString((key >> ID_SHIFT) & ID_MASK));
                      sb.append("/0x");
                      sb.append(Integer.toHexString((key >> ARRAY_SHIFT) & ARRAY_MASK));
                      sb.append("/0x");
                      sb.append(Integer.toHexString((key >> INDEX_SHIFT) & INDEX_MASK));
                      if (i != N-1) {
                          sb.append(", ");
                      }
                  }
                  sb.append(']');
              }
              sb.append(" clazz=");
              sb.append(getClass().getName());
              sb.append('}');
  
              return sb.toString();
          }
      }
  
      public SparseMappingTable() {
          mLongs.add(new long[ARRAY_SIZE]);
      }
  
      /**
       * Wipe out all the data.
       */
      public void reset() {
          // Clear out mLongs, and prime it with a new array of data
          mLongs.clear();
          mLongs.add(new long[ARRAY_SIZE]);
          mNextIndex = 0;
  
          // Increment out sequence counter, because all of the tables will
          // now be out of sync with the data.
          mSequence++;
      }
  
      /**
       * Write the data arrays to the parcel.
       */
      public void writeToParcel(Parcel out) {
          out.writeInt(mSequence);
          out.writeInt(mNextIndex);
          final int N = mLongs.size();
          out.writeInt(N);
          for (int i=0; i<N-1; i++) {
              final long[] array = mLongs.get(i);
              out.writeInt(array.length);
              writeCompactedLongArray(out, array, array.length);
          }
          // save less for the last one. upon re-loading they'll just start a new array.
          final long[] lastLongs = mLongs.get(N-1);
          out.writeInt(mNextIndex);
          writeCompactedLongArray(out, lastLongs, mNextIndex);
      }
  
      /**
       * Read the data arrays from the parcel.
       */
      public void readFromParcel(Parcel in) {
          mSequence = in.readInt();
          mNextIndex = in.readInt();
  
          mLongs.clear();
          final int N = in.readInt();
          for (int i=0; i<N; i++) {
              final int size = in.readInt();
              final long[] array = new long[size];
              readCompactedLongArray(in, array, size);
              mLongs.add(array);
          }
          // Verify that last array's length is consistent with writeToParcel
          if (N > 0 && mLongs.get(N - 1).length != mNextIndex) {
              EventLog.writeEvent(0x534e4554, "73252178", -1, "");
              throw new IllegalStateException("Expected array of length " + mNextIndex + " but was "
                      + mLongs.get(N - 1).length);
          }
      }
  
      /**
       * Return a string for debugging.
       */
      public String dumpInternalState(boolean includeData) {
          final StringBuilder sb = new StringBuilder();
          sb.append("SparseMappingTable{");
          sb.append("mSequence=");
          sb.append(mSequence);
          sb.append(" mNextIndex=");
          sb.append(mNextIndex);
          sb.append(" mLongs.size=");
          final int N = mLongs.size();
          sb.append(N);
          sb.append("\n");
          if (includeData) {
              for (int i=0; i<N; i++) {
                  final long[] array = mLongs.get(i);
                  for (int j=0; j<array.length; j++) {
                      if (i == N-1 && j == mNextIndex) {
                          break;
                      }
                      sb.append(String.format(" %4d %d 0x%016x %-19d\n", i, j, array[j], array[j]));
                  }
              }
          }
          sb.append("}");
          return sb.toString();
      }
  
      /**
       * Write the long array to the parcel in a compacted form.  Does not allow negative
       * values in the array.
       */
      private static void writeCompactedLongArray(Parcel out, long[] array, int num) {
          for (int i=0; i<num; i++) {
              long val = array[i];
              if (val < 0) {
                  Slog.w(TAG, "Time val negative: " + val);
                  val = 0;
              }
              if (val <= Integer.MAX_VALUE) {
                  out.writeInt((int)val);
              } else {
                  int top = ~((int)((val>>32)&0x7fffffff));
                  int bottom = (int)(val&0x0ffffffffL);
                  out.writeInt(top);
                  out.writeInt(bottom);
              }
          }
      }
  
      /**
       * Read the compacted array into the long[].
       */
      private static void readCompactedLongArray(Parcel in, long[] array, int num) {
          final int alen = array.length;
          if (num > alen) {
              logOrThrow("bad array lengths: got " + num + " array is " + alen);
              return;
          }
          int i;
          for (i=0; i<num; i++) {
              int val = in.readInt();
              if (val >= 0) {
                  array[i] = val;
              } else {
                  int bottom = in.readInt();
                  array[i] = (((long)~val)<<32) | bottom;
              }
          }
          while (i < alen) {
              array[i] = 0;
              i++;
          }
      }
  
      /**
       * Extract the id from a key.
       */
      public static byte getIdFromKey(int key) {
          return (byte)((key >> ID_SHIFT) & ID_MASK);
      }
  
      /**
       * Gets the index of the array in the list of arrays.
       *
       * Not to be confused with getIndexFromKey.
       */
      public static int getArrayFromKey(int key) {
          return (key >> ARRAY_SHIFT) & ARRAY_MASK;
      }
  
      /**
       * Gets the index of a value in a long[].
       *
       * Not to be confused with getArrayFromKey.
       */
      public static int getIndexFromKey(int key) {
          return (key >> INDEX_SHIFT) & INDEX_MASK;
      }
  
      /**
       * Do a Slog.wtf or throw an exception (thereby crashing the system process if
       * this is a debug build.)
       */
      private static void logOrThrow(String message) {
          logOrThrow(message, new RuntimeException("Stack trace"));
      }
  
      /**
       * Do a Slog.wtf or throw an exception (thereby crashing the system process if
       * this is an eng build.)
       */
      private static void logOrThrow(String message, Throwable th) {
          Slog.e(TAG, message, th);
          if (Build.IS_ENG) {
              throw new RuntimeException(message, th);
          }
      }
  }
  