findinconsistentsync2.java

A static analysis tool to find bugs in Java programs

									" (frame=" + vnaDataflow.getFactAtLocation(location) + ")");
					}
				}

				if (xfield == null)
					continue;

				// We only care about mutable nonvolatile nonpublic instance fields.
				if (xfield.isStatic() || xfield.isPublic() || xfield.isVolatile() || xfield.isFinal())
					continue;

				// The value number frame could be invalid if the basic
				// block became unreachable due to edge pruning (dead code).
				ValueNumberFrame frame = vnaDataflow.getFactAtLocation(location);
				if (!frame.isValid())
					continue;

				// Get lock set and instance value
				ValueNumber thisValue = !method.isStatic() ? vnaDataflow.getAnalysis().getThisValue() : null;
				LockSet lockSet = lockChecker.getFactAtLocation(location);
				InstructionHandle handle = location.getHandle();
				ValueNumber instance = frame.getInstance(handle.getInstruction(), cpg);
				if (DEBUG) {
					System.out.println("Lock set: " + lockSet);
					System.out.println("value number: " + instance.getNumber());
					System.out.println("Lock count: " + lockSet.getLockCount(instance.getNumber()));
				}


				// Is the instance locked?
				// We consider the access to be locked if either
				//   - the object is explicitly locked, or
				//   - the field is accessed through the "this" reference,
				//     and the method is in the locked method set, or
				//   - any value returned by a called method is locked;
				//     the (conservative) assumption is that the return lock object
				//     is correct for synchronizing the access
				boolean isExplicitlyLocked = lockSet.getLockCount(instance.getNumber()) > 0;
				boolean isAccessedThroughThis = thisValue != null && thisValue.equals(instance);
				boolean isLocked = isExplicitlyLocked
						|| (lockedMethodSet.contains(method) && isAccessedThroughThis)
						|| lockSet.containsReturnValue(vnaDataflow.getAnalysis().getFactory());

				// Adjust the field so its class name is the same
				// as the type of reference it is accessed through.
				// This helps fix false positives produced when a
				// threadsafe class is extended by a subclass that
				// doesn't care about thread safety.
				if (ADJUST_SUBCLASS_ACCESSES) {
					// Find the type of the object instance
					TypeDataflow typeDataflow = classContext.getTypeDataflow(method);
					TypeFrame typeFrame = typeDataflow.getFactAtLocation(location);
					if (!typeFrame.isValid()) continue;
					Type instanceType = typeFrame.getInstance(handle.getInstruction(), cpg);
					if (instanceType instanceof TopType) {
						if (DEBUG) System.out.println("Freaky: typeFrame is " + typeFrame);
						continue;
					}
					// Note: instance type can be Null,
					// in which case we won't adjust the field type.
					if (instanceType != TypeFrame.getNullType()) {
						if (!(instanceType instanceof ObjectType)) {
							throw new DataflowAnalysisException("Field accessed through non-object reference " + instanceType,
									methodGen, handle);
						}
						ObjectType objType = (ObjectType) instanceType;

						// If instance class name is not the same as that of the field,
						// make it so
						String instanceClassName = objType.getClassName();
						if (!instanceClassName.equals(xfield.getClassName())) {
							xfield = new InstanceField(instanceClassName,
									xfield.getName(),
									xfield.getSignature(),
									xfield.getAccessFlags());
						}
					}
				}

				int kind = 0;
				kind |= isLocked ? LOCKED : UNLOCKED;
				kind |= isWrite ? WRITE : READ;

				if (isLocked || !isConstructor(method.getName())) {
					if (DEBUG)
						System.out.println("IS2:\t" +
								SignatureConverter.convertMethodSignature(methodGen) +
								"\t" + xfield + "\t" + ((isWrite ? "W" : "R") + "/" + (isLocked ? "L" : "U")));

					FieldStats stats = getStats(xfield);
					stats.addAccess(kind);

					if (isExplicitlyLocked && isLocal)
						stats.addLocalLock();

					if (isGetterMethod && !isLocked)
						stats.addGetterMethodAccess();

					stats.addAccess(classContext, method, handle, isLocked);
				}
			} catch (ClassNotFoundException e) {
				bugReporter.reportMissingClass(e);
			}
		}
	}

	/**
	 * Determine whether or not the the given method is
	 * a getter method.  I.e., if it just returns the
	 * value of an instance field.
	 *
	 * @param classContext the ClassContext for the class containing the method
	 * @param method       the method
	 */
	public static boolean isGetterMethod(ClassContext classContext, Method method) {
		MethodGen methodGen = classContext.getMethodGen(method);
		if (methodGen == null) return false;
		InstructionList il = methodGen.getInstructionList();
		// System.out.println("Checking getter method: " + method.getName());
		if (il.getLength() > 60)
			return false;

		int count = 0;
		Iterator<InstructionHandle> it = il.iterator();
		while (it.hasNext()) {
			InstructionHandle ih = it.next();
			switch (ih.getInstruction().getOpcode()) {
			case Constants.GETFIELD:
				count++;
				if (count > 1) return false;
				break;
			case Constants.PUTFIELD:
			case Constants.BALOAD:
			case Constants.CALOAD:
			case Constants.DALOAD:
			case Constants.FALOAD:
			case Constants.IALOAD:
			case Constants.LALOAD:
			case Constants.SALOAD:
			case Constants.AALOAD:
			case Constants.BASTORE:
			case Constants.CASTORE:
			case Constants.DASTORE:
			case Constants.FASTORE:
			case Constants.IASTORE:
			case Constants.LASTORE:
			case Constants.SASTORE:
			case Constants.AASTORE:
			case Constants.PUTSTATIC:
				return false;
			case Constants.INVOKESTATIC:
			case Constants.INVOKEVIRTUAL:
			case Constants.INVOKEINTERFACE:
			case Constants.INVOKESPECIAL:
			case Constants.GETSTATIC:
				// no-op

			}
		}
		// System.out.println("Found getter method: " + method.getName());
		return true;
	}

	/**
	 * Get the access statistics for given field.
	 */
	private FieldStats getStats(XField field) {
		FieldStats stats = statMap.get(field);
		if (stats == null) {
			stats = new FieldStats();
			statMap.put(field, stats);
		}
		return stats;
	}

	/**
	 * Find methods that appear to never be called from an unlocked context
	 * We assume that nonpublic methods will only be called from
	 * within the class, which is not really a valid assumption.
	 */
	private Set<Method> findNotUnlockedMethods(ClassContext classContext, SelfCalls selfCalls,
											   Set<CallSite> obviouslyLockedSites)
			throws CFGBuilderException, DataflowAnalysisException {

		JavaClass javaClass = classContext.getJavaClass();
		Method[] methodList = javaClass.getMethods();

		CallGraph callGraph = selfCalls.getCallGraph();

		// Initially, assume no methods are called from an
		// unlocked context
		Set<Method> lockedMethodSet = new HashSet<Method>();
		lockedMethodSet.addAll(Arrays.asList(methodList));

		// Assume all public methods are called from
		// unlocked context
		for (Method method : methodList) {
			if (method.isPublic()
					&& !isConstructor(method.getName())) {
				lockedMethodSet.remove(method);
			}
		}

		// Explore the self-call graph to find nonpublic methods
		// that can be called from an unlocked context.
		boolean change;
		do {
			change = false;

			for (Iterator<CallGraphEdge> i = callGraph.edgeIterator(); i.hasNext();) {
				CallGraphEdge edge = i.next();
				CallSite callSite = edge.getCallSite();

				// Ignore obviously locked edges
				if (obviouslyLockedSites.contains(callSite))
					continue;

				// If the calling method is locked, ignore the edge
				if (lockedMethodSet.contains(callSite.getMethod()))
					continue;

				// Calling method is unlocked, so the called method
				// is also unlocked.
				CallGraphNode target = edge.getTarget();
				if (lockedMethodSet.remove(target.getMethod()))
					change = true;
			}
		} while (change);

		if (DEBUG) {
			System.out.println("Apparently not unlocked methods:");
			for (Method method : lockedMethodSet) {
				System.out.println("\t" + method.getName());
			}
		}

		// We assume that any methods left in the locked set
		// are called only from a locked context.
		return lockedMethodSet;
	}

	/**
	 * Find methods that appear to always be called from a locked context.
	 * We assume that nonpublic methods will only be called from
	 * within the class, which is not really a valid assumption.
	 */
	private Set<Method> findLockedMethods(ClassContext classContext, SelfCalls selfCalls,
										  Set<CallSite> obviouslyLockedSites)
			throws CFGBuilderException, DataflowAnalysisException {

		JavaClass javaClass = classContext.getJavaClass();
		Method[] methodList = javaClass.getMethods();

		CallGraph callGraph = selfCalls.getCallGraph();

		// Initially, assume all methods are locked
		Set<Method> lockedMethodSet = new HashSet<Method>();

		// Assume all public methods are unlocked
		for (Method method : methodList) {
			if (method.isSynchronized()) {
				lockedMethodSet.add(method);
			}
		}

		// Explore the self-call graph to find nonpublic methods
		// that can be called from an unlocked context.
		boolean change;
		do {
			change = false;

			for (Iterator<CallGraphEdge> i = callGraph.edgeIterator(); i.hasNext();) {
				CallGraphEdge edge = i.next();
				CallSite callSite = edge.getCallSite();

				// Ignore obviously locked edges
				// If the calling method is locked, ignore the edge
				if (obviouslyLockedSites.contains(callSite)
						|| lockedMethodSet.contains(callSite.getMethod())) {
					// Calling method is unlocked, so the called method
					// is also unlocked.
					CallGraphNode target = edge.getTarget();
					if (lockedMethodSet.add(target.getMethod()))
						change = true;
				}
			}
		} while (change);

		if (DEBUG) {
			System.out.println("Apparently locked methods:");
			for (Method method : lockedMethodSet) {
				System.out.println("\t" + method.getName());
			}
		}

		// We assume that any methods left in the locked set
		// are called only from a locked context.
		return lockedMethodSet;
	}

	/**
	 * Find methods that do not appear to be reachable from public methods.
	 * Such methods will not be analyzed.
	 */
	private Set<Method> findPublicReachableMethods(ClassContext classContext, SelfCalls selfCalls)
			throws CFGBuilderException, DataflowAnalysisException {

		JavaClass javaClass = classContext.getJavaClass();
		Method[] methodList = javaClass.getMethods();

		CallGraph callGraph = selfCalls.getCallGraph();

		// Initially, assume all methods are locked
		Set<Method> publicReachableMethodSet = new HashSet<Method>();

		// Assume all public methods are unlocked
		for (Method method : methodList) {
			if (method.isPublic()
					&& !isConstructor(method.getName())) {
				publicReachableMethodSet.add(method);
			}
		}

		// Explore the self-call graph to find nonpublic methods
		// that can be called from an unlocked context.
		boolean change;
		do {
			change = false;

			for (Iterator<CallGraphEdge> i = callGraph.edgeIterator(); i.hasNext();) {
				CallGraphEdge edge = i.next();
				CallSite callSite = edge.getCallSite();

				// Ignore obviously locked edges
				// If the calling method is locked, ignore the edge
				if (publicReachableMethodSet.contains(callSite.getMethod())) {
					// Calling method is reachable, so the called method
					// is also reachable.
					CallGraphNode target = edge.getTarget();
					if (publicReachableMethodSet.add(target.getMethod()))
						change = true;
				}
			}
		} while (change);

		if (DEBUG) {
			System.out.println("Methods apparently reachable from public non-constructor methods:");
			for (Method method : publicReachableMethodSet) {
				System.out.println("\t" + method.getName());
			}
		}

		return publicReachableMethodSet;
	}

	/**
	 * Find all self-call sites that are obviously locked.
	 */
	private Set<CallSite> findObviouslyLockedCallSites(ClassContext classContext, SelfCalls selfCalls)
			throws CFGBuilderException, DataflowAnalysisException {
		ConstantPoolGen cpg = classContext.getConstantPoolGen();

		// Find all obviously locked call sites
		Set<CallSite> obviouslyLockedSites = new HashSet<CallSite>();
		for (Iterator<CallSite> i = selfCalls.callSiteIterator(); i.hasNext();) {
			CallSite callSite = i.next();
			Method method = callSite.getMethod();
			Location location = callSite.getLocation();
			InstructionHandle handle = location.getHandle();

			// Only instance method calls qualify as candidates for
			// "obviously locked"
			Instruction ins = handle.getInstruction();
			if (ins.getOpcode() == Constants.INVOKESTATIC)
				continue;

			// Get lock set for site
			LockChecker lockChecker = classContext.getLockChecker(method);
			LockSet lockSet = lockChecker.getFactAtLocation(location);

			// Get value number frame for site
			ValueNumberDataflow vnaDataflow = classContext.getValueNumberDataflow(method);
			ValueNumberFrame frame = vnaDataflow.getFactAtLocation(location);

			// NOTE: if the CFG on which the value number analysis was performed
			// was pruned, there may be unreachable instructions.  Therefore,
			// we can't assume the frame is valid.
			if (!frame.isValid())
				continue;

			// Find the ValueNumber of the receiver object
			int numConsumed = ins.consumeStack(cpg);
			MethodGen methodGen = classContext.getMethodGen(method);
			assert methodGen != null;
			if (numConsumed == Constants.UNPREDICTABLE)
				throw new DataflowAnalysisException(
						"Unpredictable stack consumption",
						methodGen,
						handle);
			//if (DEBUG) System.out.println("Getting receiver for frame: " + frame);
			ValueNumber instance = frame.getStackValue(numConsumed - 1);

			// Is the instance locked?
			int lockCount = lockSet.getLockCount(instance.getNumber());
			if (lockCount > 0) {
				// This is a locked call site
				obviouslyLockedSites.add(callSite);
			}
		}

		return obviouslyLockedSites;
	}
}

// vim:ts=3