knossos.history — knossos 0.3.9

Operations on histories

complete clj

(complete history)

When a request is initiated, we may not know what the result will be--but find out when it completes. In the history, this might look like

[{:type :invoke :f :read :value nil} ; We don't know what we're going to read. {:type :ok :f :read :value 2}] ; We received 2.

This function fills in missing values for invocations, where those requests complete. It constructs a new history in which we 'already knew' what the results of successful operations would have been.

For failed operations, complete fills in the value for both invocation and completion; depending on whichever has a value available. We also add a :fails? key to invocations which will fail, allowing checkers to skip them.

complete-fold-op clj

(complete-fold-op [history index] op)

Folds an operation into a completed history, keeping track of outstanding invocations.

History is our complete history of operations: a transient vector. Index is a transient map of processes to the index of their most recent invocation. Note that we assume processes are singlethreaded; e.g. they do not perform multiple invocations without receiving responses.

completion clj

(completion pair-index op)

Returns the completion for an op, using a pair index. If the op is itself a completion, returns the op. If the op is an invocation, looks up its completion in the pair index.

convert-op-index clj

(convert-op-index mapping op)

Maps the index of the op to its corresponding value in the given mapping

convert-op-indices clj

(convert-op-indices mapping ops)

Maps convert-op-index over a collection of ops

crashed-invokes clj

(crashed-invokes history)

Which invoke ops in a history have no corresponding :ok or :fail?

ensure-indexed clj

(ensure-indexed history)

Makes sure a history is indexed when we start our analysis

index clj

(index history)

Attaches an :index key to each element of the history, identifying its position in the history vector.

indexed? clj

(indexed? history)

Is the given history indexed?

invocation clj

(invocation pair-index op)

Returns the invocation for an op, using a pair index. If the op is itself a completion, returns the op. If the op is an invocation, looks up its completion in the pair index.

kindex clj

(kindex history)

Takes a history and returns a new history with internal knossos indices and a map of knossos indices to external indices. Throws IllegalArgumentException if given history does not have unique indices

pair-index clj

(pair-index history)

(pair-index pair-fn history)

Given a history, constructs a map from operations to their counterparts--invocations to their completions or completions to their invocations. Infos map to nil.

pair-index+ clj

(pair-index+ history)

Like pair-index, but matches invokes to infos as well.

pairs clj

(pairs history)

(pairs invocations [op & ops])

Pairs up ops from each process in a history. Yields a lazy sequence of [info] or [invoke, ok|fail] pairs.

pairs+ clj

(pairs+ history)

(pairs+ invocations [op & ops])

Pairs up ops from each process in a history. Yields a lazy sequence of [info] or [invoke, ok|fail|info] pairs. The difference from pairs is that this variant maps invocations to infos.

parse-ops clj

(parse-ops history)

We're going to construct Op defrecords throughout our analysis, which means that a map without a value, e.g. {:type :invoke, :f :lock, :process 2} is not equal to the corresponding Op, which will have an explicit :value nil. We convert all maps in the history to Ops before doing anything else.

preprocess clj

(preprocess history)

We're going to make several assumptions in Knossos about the structure of histories. This function massages histories to make those assumptions legal.

1. First, we make sure we have an :index field on ops. This is important so we can uniquely identify operations.

2. We convert all operation maps to our internal Op representation.

3. We fill in invocation :values with the results of completions, because we may not know exactly what an operation does at invocation time.

4. We strip out failed ops; they can't influence state.

5. We append synthetic :info operations for any incomplete invocations.

6. We re-index the history so that indices go 0, 1, 2, ..., and compute a map of these knossos :index'es to original :index'es.

processes clj

(processes history)

What processes are in a history?

render-op clj

(render-op indices op)

Prepares an op to be returned by converting it to a plain old map and reassigning its external index

sort-processes clj

(sort-processes coll)

Sort a collection of processes. Puts numbers second, keywords first.

unmatched-invokes clj

(unmatched-invokes history)

Which invoke ops in a history have no corresponding :ok, :fail, or :info?

with-synthetic-infos clj

(with-synthetic-infos history)

Histories may arrive with :invoke operations that never complete. We append synthetic :info ops to the end of the history for any in-process calls.

without-failures clj

(without-failures history)

Takes a completed history, and returns a copy of the given history without any failed operations--either invocations or completions.

without-infos clj

(without-infos history)

Takes a completed history, and returns a copy of that history without any :info operations.