- if length best_plc == length ini_plc then -- no advancement
- ini_tbl
- else
- best_tbl
-
-{- | Auxiliary function for solution computation.
-
-We write this in an explicit recursive fashion in order to control
-early-abort in case we have met the min delta. We can't use foldr
-instead of explicit recursion since we need the accumulator for the
-abort decision.
-
--}
-advanceSolution :: [Maybe Removal] -- ^ The removal to process
- -> Int -- ^ Minimum delta parameter
- -> Int -- ^ Maximum delta parameter
- -> Maybe Solution -- ^ Current best solution
- -> Maybe Solution -- ^ New best solution
-advanceSolution [] _ _ sol = sol
-advanceSolution (Nothing:xs) m n sol = advanceSolution xs m n sol
-advanceSolution ((Just (Removal nx removed)):xs) min_d max_d prev_sol =
- let new_sol = checkPlacement nx removed [] 0 prev_sol max_d
- new_delta = solutionDelta $! new_sol
- in
- if new_delta >= 0 && new_delta <= min_d then
- new_sol
- else
- advanceSolution xs min_d max_d new_sol
-
--- | Computes the placement solution.
-solutionFromRemovals :: [Maybe Removal] -- ^ The list of (possible) removals
- -> Int -- ^ Minimum delta parameter
- -> Int -- ^ Maximum delta parameter
- -> Maybe Solution -- ^ The best solution found
-solutionFromRemovals removals min_delta max_delta =
- advanceSolution removals min_delta max_delta Nothing
-
-{- | Computes the solution at the given depth.
-
-This is a wrapper over both computeRemovals and
-solutionFromRemovals. In case we have no solution, we return Nothing.
-
--}
-computeSolution :: Node.List -- ^ The original node data
- -> [Instance.Instance] -- ^ The list of /bad/ instances
- -> Int -- ^ The /depth/ of removals
- -> Int -- ^ Maximum number of removals to process
- -> Int -- ^ Minimum delta parameter
- -> Int -- ^ Maximum delta parameter
- -> Maybe Solution -- ^ The best solution found (or Nothing)
-computeSolution nl bad_instances depth max_removals min_delta max_delta =
- let
- removals = computeRemovals nl bad_instances depth
- removals' = capRemovals removals max_removals
- in
- solutionFromRemovals removals' min_delta max_delta
-
--- Solution display functions (pure)
+ if fin_cv < ini_cv && (ini_cv > mg_limit || ini_cv - fin_cv >= min_gain)
+ then Just fin_tbl -- this round made success, return the new table
+ else Nothing
+
+-- * Allocation functions
+
+-- | Build failure stats out of a list of failures
+collapseFailures :: [FailMode] -> FailStats
+collapseFailures flst =
+ map (\k -> (k, length $ filter (k ==) flst)) [minBound..maxBound]
+
+-- | Update current Allocation solution and failure stats with new
+-- elements
+concatAllocs :: AllocSolution -> OpResult Node.AllocElement -> AllocSolution
+concatAllocs as (OpFail reason) = as { asFailures = reason : asFailures as }
+
+concatAllocs as (OpGood ns@(_, _, _, nscore)) =
+ let -- Choose the old or new solution, based on the cluster score
+ cntok = asAllocs as
+ osols = asSolutions as
+ nsols = case osols of
+ [] -> [ns]
+ (_, _, _, oscore):[] ->
+ if oscore < nscore
+ then osols
+ else [ns]
+ -- FIXME: here we simply concat to lists with more
+ -- than one element; we should instead abort, since
+ -- this is not a valid usage of this function
+ xs -> ns:xs
+ nsuc = cntok + 1
+ -- Note: we force evaluation of nsols here in order to keep the
+ -- memory profile low - we know that we will need nsols for sure
+ -- in the next cycle, so we force evaluation of nsols, since the
+ -- foldl' in the caller will only evaluate the tuple, but not the
+ -- elements of the tuple
+ in nsols `seq` nsuc `seq` as { asAllocs = nsuc, asSolutions = nsols }
+
+-- | Try to allocate an instance on the cluster.
+tryAlloc :: (Monad m) =>
+ Node.List -- ^ The node list
+ -> Instance.List -- ^ The instance list
+ -> Instance.Instance -- ^ The instance to allocate
+ -> Int -- ^ Required number of nodes
+ -> m AllocSolution -- ^ Possible solution list
+tryAlloc nl _ inst 2 =
+ let all_nodes = getOnline nl
+ all_pairs = liftM2 (,) all_nodes all_nodes
+ ok_pairs = filter (\(x, y) -> Node.idx x /= Node.idx y) all_pairs
+ sols = foldl' (\cstate (p, s) ->
+ concatAllocs cstate $ allocateOnPair nl inst p s
+ ) emptySolution ok_pairs
+ in return sols
+
+tryAlloc nl _ inst 1 =
+ let all_nodes = getOnline nl
+ sols = foldl' (\cstate ->
+ concatAllocs cstate . allocateOnSingle nl inst
+ ) emptySolution all_nodes
+ in return sols
+
+tryAlloc _ _ _ reqn = fail $ "Unsupported number of allocation \
+ \destinations required (" ++ show reqn ++
+ "), only two supported"
+
+-- | Try to allocate an instance on the cluster.
+tryReloc :: (Monad m) =>
+ Node.List -- ^ The node list
+ -> Instance.List -- ^ The instance list
+ -> Idx -- ^ The index of the instance to move
+ -> Int -- ^ The number of nodes required
+ -> [Ndx] -- ^ Nodes which should not be used
+ -> m AllocSolution -- ^ Solution list
+tryReloc nl il xid 1 ex_idx =
+ let all_nodes = getOnline nl
+ inst = Container.find xid il
+ ex_idx' = Instance.pNode inst:ex_idx
+ valid_nodes = filter (not . flip elem ex_idx' . Node.idx) all_nodes
+ valid_idxes = map Node.idx valid_nodes
+ sols1 = foldl' (\cstate x ->
+ let em = do
+ (mnl, i, _, _) <-
+ applyMove nl inst (ReplaceSecondary x)
+ return (mnl, i, [Container.find x mnl],
+ compCV mnl)
+ in concatAllocs cstate em
+ ) emptySolution valid_idxes
+ in return sols1
+
+tryReloc _ _ _ reqn _ = fail $ "Unsupported number of relocation \
+ \destinations required (" ++ show reqn ++
+ "), only one supported"
+
+-- | Try to evacuate a list of nodes.
+tryEvac :: (Monad m) =>
+ Node.List -- ^ The node list
+ -> Instance.List -- ^ The instance list
+ -> [Ndx] -- ^ Nodes to be evacuated
+ -> m AllocSolution -- ^ Solution list
+tryEvac nl il ex_ndx =
+ let ex_nodes = map (`Container.find` nl) ex_ndx
+ all_insts = nub . concatMap Node.sList $ ex_nodes
+ in do
+ (_, sol) <- foldM (\(nl', old_as) idx -> do
+ -- FIXME: hardcoded one node here
+ -- (fm, cs, aes)
+ new_as <- tryReloc nl' il idx 1 ex_ndx
+ case asSolutions new_as of
+ csol@(nl'', _, _, _):_ ->
+ -- an individual relocation succeeded,
+ -- we kind of compose the data from
+ -- the two solutions
+ return (nl'',
+ new_as { asSolutions =
+ csol:asSolutions old_as })
+ -- this relocation failed, so we fail
+ -- the entire evac
+ _ -> fail $ "Can't evacuate instance " ++
+ Instance.name (Container.find idx il)
+ ) (nl, emptySolution) all_insts
+ return sol
+
+-- | Recursively place instances on the cluster until we're out of space
+iterateAlloc :: Node.List
+ -> Instance.List
+ -> Instance.Instance
+ -> Int
+ -> [Instance.Instance]
+ -> Result (FailStats, Node.List, Instance.List,
+ [Instance.Instance])
+iterateAlloc nl il newinst nreq ixes =
+ let depth = length ixes
+ newname = printf "new-%d" depth::String
+ newidx = length (Container.elems il) + depth
+ newi2 = Instance.setIdx (Instance.setName newinst newname) newidx
+ in case tryAlloc nl il newi2 nreq of
+ Bad s -> Bad s
+ Ok (AllocSolution { asFailures = errs, asSolutions = sols3 }) ->
+ case sols3 of
+ [] -> Ok (collapseFailures errs, nl, il, ixes)
+ (xnl, xi, _, _):[] ->
+ iterateAlloc xnl (Container.add newidx xi il)
+ newinst nreq $! (xi:ixes)
+ _ -> Bad "Internal error: multiple solutions for single\
+ \ allocation"
+
+tieredAlloc :: Node.List
+ -> Instance.List
+ -> Instance.Instance
+ -> Int
+ -> [Instance.Instance]
+ -> Result (FailStats, Node.List, Instance.List,
+ [Instance.Instance])
+tieredAlloc nl il newinst nreq ixes =
+ case iterateAlloc nl il newinst nreq ixes of
+ Bad s -> Bad s
+ Ok (errs, nl', il', ixes') ->
+ case Instance.shrinkByType newinst . fst . last $
+ sortBy (comparing snd) errs of
+ Bad _ -> Ok (errs, nl', il', ixes')
+ Ok newinst' ->
+ tieredAlloc nl' il' newinst' nreq ixes'
+
+-- * Formatting functions