Copyright (c) 2017 Google, Inc and others.
This program and the accompanying materials
are made available under the terms of the Eclipse Public License 2.0
which accompanies this distribution, and is available at
https://www.eclipse.org/legal/epl-2.0/
SPDX-License-Identifier: EPL-2.0
Contributors:
  Stefan Xenos (Google) - Initial implementation
/*******************************************************************************
 * Copyright (c) 2017 Google, Inc and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *   Stefan Xenos (Google) - Initial implementation
 *******************************************************************************/
package org.eclipse.jdt.internal.core.nd.db;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Records a record of every modification to the database, in a circular buffer of fixed size. Whenever anything writes
to the database, the log records the address and size of the write, along with a call stack describing what was going
on at the time of the write. The actual bytes written to the database are not recorded. In addition to writes, it
also records every invocation of malloc and free.

Given a memory address range, we can trace the log backwards to find everything that ever happened to that address
range since the start of the log.

"call stacks" don't use java call stacks. They use explicit tags that are pushed and popped at the start and
end of operations related to modifying the database.
/**
 * Records a record of every modification to the database, in a circular buffer of fixed size. Whenever anything writes
 * to the database, the log records the address and size of the write, along with a call stack describing what was going
 * on at the time of the write. The actual bytes written to the database are not recorded. In addition to writes, it
 * also records every invocation of malloc and free.
 * <p>
 * Given a memory address range, we can trace the log backwards to find everything that ever happened to that address
 * range since the start of the log.
 * </p>
 * "call stacks" don't use java call stacks. They use explicit tags that are pushed and popped at the start and
 * end of operations related to modifying the database.
 */
public class ModificationLog {
	
Used to attach messages to events in the log. Tags should be allocated in static initializers at application startup by calling ModificationLog.createTag(String). Once allocated, the tag can be pushed and popped on to the stack in the log to mark the beginning and end of operations. /**
	 * Used to attach messages to events in the log. Tags should be allocated in static initializers at application
	 * startup by calling {@link ModificationLog#createTag(String)}. Once allocated, the tag can be pushed and popped on to
	 * the stack in the log to mark the beginning and end of operations.
	 */
	public static class Tag {
		public final String name;
		public final int opNum;

		Tag(String name, int opNum) {
			this.name = name;
			this.opNum = opNum;
		}

		@Override
		public String toString() {
			return this.opNum + ":" + this.name; //$NON-NLS-1$
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + this.opNum;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Tag other = (Tag) obj;
			if (this.opNum != other.opNum)
				return false;
			return true;
		}
	}

	
Represents a single entry in a MemoryAccessLog. That is, a single read, write, malloc, or free event that affected the memory range of interest. /**
	 * Represents a single entry in a {@link MemoryAccessLog}. That is, a single read, write, malloc, or free event that
	 * affected the memory range of interest.
	 */
	public static class MemoryOperation {
		private final List<Tag> stack;
		private final long time;
		private final long startAddress;
		private final int addressSize;
		private final byte operationType;

		public MemoryOperation(byte operationType, long time, long startAddress, int size, List<Tag> stack) {
			super();
			this.operationType = operationType;
			this.time = time;
			this.startAddress = startAddress;
			this.addressSize = size;
			this.stack = stack;
		}

		public List<Tag> getStack() {
			return this.stack;
		}

		public long getTime() {
			return this.time;
		}

		public long getStartAddress() {
			return this.startAddress;
		}

		public int getSize() {
			return this.addressSize;
		}

		public byte getOperationType() {
			return this.operationType;
		}

		public void printTo(StringBuilder builder, int indent) {
			indent(builder, indent);
			switch (getOperationType()) {
				case FREE_OPERATION: builder.append("freed"); break; //$NON-NLS-1$
				case MALLOC_OPERATION: builder.append("malloc'd"); break; //$NON-NLS-1$
				case WRITE_OPERATION: builder.append("wrote"); break; //$NON-NLS-1$
			}
			builder.append(" [address "); //$NON-NLS-1$
			builder.append(this.startAddress);
			builder.append(", size "); //$NON-NLS-1$
			builder.append(this.addressSize);
			builder.append("] at time "); //$NON-NLS-1$
			builder.append(this.time);
			builder.append("\n");  //$NON-NLS-1$
			List<Tag> theStack = new ArrayList<>();
			theStack.addAll(getStack());
			Collections.reverse(theStack);
			for (Tag next : theStack) {
				indent(builder, indent + 1);
				builder.append(next.name + "\n");  //$NON-NLS-1$
			}
		}
	}

	
Contains a log of events related to a specific range of database addresses, in reverse chronological order.
/**
	 * Contains a log of events related to a specific range of database addresses, in reverse chronological order.
	 */
	public static class MemoryAccessLog {
		private final List<MemoryOperation> operations;

		public MemoryAccessLog(List<MemoryOperation> operations) {
			super();
			this.operations = operations;
		}

		
Returns a list of operations, in reverse order of time.
/**
		 * Returns a list of operations, in reverse order of time.
		 */
		public List<MemoryOperation> getOperations() {
			return this.operations;
		}

		
Returns true iff this log contains a double malloc or a double free
/**
		 * Returns true iff this log contains a double malloc or a double free
		 */
		public boolean hasInconsistentMemoryAllocation() {
			boolean known = false;
			boolean allocated = false;
			for (MemoryOperation next : this.operations) {
				boolean newAllocatedState;
				if (next.getOperationType() == MALLOC_OPERATION) {
					newAllocatedState = false;
				} else if (next.getOperationType() == FREE_OPERATION) {
					newAllocatedState = true;
				} else {
					continue;
				}

				if (!known) {
					known = true;
				} else if (allocated == newAllocatedState) {
					return true;
				}
				allocated = newAllocatedState;
			}
			return false;
		}

		
Search for anomalies in the log and produce a reduced report
Returns:
a log containing the most interesting results/**
		 * Search for anomalies in the log and produce a reduced report
		 * 
		 * @return a log containing the most interesting results
		 */
		public MemoryAccessLog reduce(int maxWrites) {
			boolean includeAllMallocs = hasInconsistentMemoryAllocation();
			int numWrites = 0;

			List<MemoryOperation> result = new ArrayList<>();
			for (MemoryOperation next : this.operations) {
				boolean keepGoing = true;
				switch (next.getOperationType()) {
					case MALLOC_OPERATION: {
						result.add(next);
						keepGoing = includeAllMallocs;
						break;
					}
					case FREE_OPERATION: {
						result.add(next);
						break;
					}
					case WRITE_OPERATION: {
						if (numWrites < maxWrites) {
							result.add(next);
						}
						numWrites++;
					}
				}
				if (!keepGoing) {
					break;
				}
			}

			return new MemoryAccessLog(result);
		}
	}

	private static Map<Integer, Tag> activeTags = new HashMap<>();
	private final ArrayDeque<Tag> operationStack = new ArrayDeque<>();
	private long[] buffer0;
	private int[] buffer1;
	private byte[] operation;
	private int insertionPosition;
	private int currentEntries;
	private long timer;

	public static final byte PUSH_OPERATION = 0;
	public static final byte POP_OPERATION = 1;
	public static final byte WRITE_OPERATION = 2;
	public static final byte MALLOC_OPERATION = 3;
	public static final byte FREE_OPERATION = 4;

	public ModificationLog(int size) {
		allocateBuffers(size);
	}

	public void clear() {
		this.currentEntries = 0;
	}

	private void allocateBuffers(int sizeInMegs) {
		int entries = getBufferEntriesFor(sizeInMegs);
		if (entries != 0) {
			this.buffer0 = new long[entries];
			this.buffer1 = new int[entries];
			this.operation = new byte[entries];
		} else {
			this.buffer0 = null;
			this.buffer1 = null;
			this.operation = null;
		}
	}

	private static int getBufferEntriesFor(int sizeInMegs) {
		long sizeOfABufferEntry = 8 + 4 + 1; // size, in bytes, of one long, one int, and one byte 
		return (int) (sizeInMegs * 1024L * 1024L / sizeOfABufferEntry);
	}

	public int getBufferEntries() {
		return this.buffer0 == null ? 0 : this.buffer0.length;
	}

	public void setBufferSize(int megs) {
		int oldBufferLength = getBufferEntries();
		int newBufferLength = getBufferEntriesFor(megs);

		if (oldBufferLength == newBufferLength) {
			return;
		}

		long[] oldBuffer0 = this.buffer0;
		int[] oldBuffer1 = this.buffer1;
		byte[] oldOperation = this.operation;

		allocateBuffers(megs);

		if (this.buffer0 == null) {
			this.currentEntries = 0;
			this.insertionPosition = 0;
			this.operationStack.clear();
			return;
		}
		int newBufferSize = Math.min(this.buffer0.length, this.currentEntries);
		if (oldBufferLength > 0) {
			int readStart = (this.insertionPosition + oldBufferLength - newBufferSize) % oldBufferLength;
			if (readStart >= this.insertionPosition) {
				int entriesFromEnd = oldBufferLength - readStart;
				System.arraycopy(oldBuffer0, readStart, this.buffer0, 0, entriesFromEnd);
				System.arraycopy(oldBuffer1, readStart, this.buffer1, 0, entriesFromEnd);
				System.arraycopy(oldOperation, readStart, this.operation, 0, entriesFromEnd);

				System.arraycopy(oldBuffer0, 0, this.buffer0, entriesFromEnd, this.insertionPosition);
				System.arraycopy(oldBuffer1, 0, this.buffer1, entriesFromEnd, this.insertionPosition);
				System.arraycopy(oldOperation, 0, this.operation, entriesFromEnd, this.insertionPosition);
			} else {
				int entriesToCopy = this.insertionPosition - readStart;
				System.arraycopy(oldBuffer0, readStart, this.buffer0, 0, entriesToCopy);
				System.arraycopy(oldBuffer1, readStart, this.buffer1, 0, entriesToCopy);
				System.arraycopy(oldOperation, readStart, this.operation, 0, entriesToCopy);
			}
		}

		this.currentEntries = newBufferSize;
		this.insertionPosition = newBufferSize % this.buffer0.length;
	}

	public static void indent(StringBuilder builder, int indent) {
		for (int count = 0; count < indent; count++) {
			builder.append("    "); //$NON-NLS-1$
		}
	}

	public boolean enabled() {
		return this.buffer0 != null;
	}

	public void start(Tag tag) {
		if (!enabled()) {
			return;
		}

		this.operationStack.add(tag);
		addToQueue(PUSH_OPERATION, 0, tag.opNum);
	}

	public void end(Tag tag) {
		if (!enabled()) {
			return;
		}
		if (!this.operationStack.getLast().equals(tag)) {
			throw new IllegalStateException();
		}
		this.operationStack.removeLast();
		addToQueue(POP_OPERATION, 0, tag.opNum);
	}

	public void recordWrite(long address, int size) {
		if (!enabled()) {
			return;
		}
		this.timer++;
		addToQueue(WRITE_OPERATION, address, size);
	}

	public void recordMalloc(long address, int size) {
		if (!enabled()) {
			return;
		}
		this.timer++;
		addToQueue(MALLOC_OPERATION, address, size);
	}

	public void recordFree(long address, int size) {
		if (!enabled()) {
			return;
		}
		this.timer++;
		addToQueue(FREE_OPERATION, address, size);
	}

	private void addToQueue(byte opConstant, long arg0, int arg1) {
		this.buffer0[this.insertionPosition] = arg0;
		this.buffer1[this.insertionPosition] = arg1;
		this.operation[this.insertionPosition] = opConstant;
		this.insertionPosition = (this.insertionPosition + 1) % this.buffer0.length;

		if (this.currentEntries < this.buffer0.length) {
			this.currentEntries++;
		}
	}

	// prints count number of last log records to stdout
	// may be useful when troubleshooting heap corruption
	public void printLog(int count) {
		for (int i = 0; i < count; i++) {
			int pos = (this.insertionPosition - count + i) % this.buffer0.length;
			byte opcode = this.operation[pos];
			switch (opcode) {
				case FREE_OPERATION:
					System.out.printf("FREE_OPERATION(address=%x, size=%d)\n", this.buffer0[pos], this.buffer1[pos]); //$NON-NLS-1$
					break;
				case MALLOC_OPERATION:
					System.out.printf("MALLOC_OPERATION(address=%x, size=%d)\n", this.buffer0[pos], this.buffer1[pos]); //$NON-NLS-1$
					break;
				case WRITE_OPERATION:
					System.out.printf("WRITE_OPERATION(address=%x, size=%d)\n", this.buffer0[pos], this.buffer1[pos]); //$NON-NLS-1$
					break;
				case PUSH_OPERATION:
					System.out.printf("PUSH_OPERATION(tag=%s)\n", activeTags.get(this.buffer1[pos])); //$NON-NLS-1$
					break;
				case POP_OPERATION:
					System.out.printf("POP_OPERATION(tag=%s)\n", activeTags.get(this.buffer1[pos])); //$NON-NLS-1$
					break;
				default:
					System.out.printf("UNKNOWN(opcode=%d, arg0=%d, arg1=%d)\n", opcode, this.buffer0[pos], this.buffer1[pos]); //$NON-NLS-1$
					break;
			}
		}
	}

	public long getWriteCount() {
		return this.timer;
	}

	
Returns information about the last write to the given address range
/**
	 * Returns information about the last write to the given address range
	 */
	public MemoryAccessLog getReportFor(long address, int size) {
		List<Tag> tags = new ArrayList<>();
		tags.addAll(this.operationStack);

		List<MemoryOperation> operations = new ArrayList<>();
		if (this.buffer0 != null) {
			int pointerToStart = (this.insertionPosition + this.buffer0.length - this.currentEntries) % this.buffer0.length;
			int currentPosition = (this.insertionPosition + this.buffer0.length - 1) % this.buffer0.length;
			long currentWrite = this.timer;
			do {
				long nextAddress = this.buffer0[currentPosition];
				int nextArgument = this.buffer1[currentPosition];
				byte nextOp = this.operation[currentPosition];
	
				switch (nextOp) {
					case POP_OPERATION: {
						tags.add(getTagForId(nextArgument));
						break;
					}
					case PUSH_OPERATION: {
						tags.remove(tags.size() - 1);
						break;
					}
					default: {
						boolean isMatch = false;
						if (address < nextAddress) {
							long diff = nextAddress - address;
							if (diff < size) {
								isMatch = true;
							}
						} else {
							long diff = address - nextAddress;
							if (diff < nextArgument) {
								isMatch = true;
							}
						}
	
						if (isMatch) {
							List<Tag> stack = new ArrayList<>();
							stack.addAll(tags);
							MemoryOperation nextOperation = new MemoryOperation(nextOp, currentWrite, nextAddress,
									nextArgument, stack);
							operations.add(nextOperation);
						}
	
						currentWrite--;
					}
				}
				currentPosition = (currentPosition + this.buffer0.length - 1) % this.buffer0.length;
			} while (currentPosition != pointerToStart);
		}
		return new MemoryAccessLog(operations);
	}

	public static Tag createTag(String tagName) {
		Tag result = new Tag(tagName, activeTags.size());
		activeTags.put(activeTags.size(), result);
		return result;
	}

	private Tag getTagForId(int nextArgument) {
		return activeTags.get(nextArgument);
	}
}