crush: add chooseleaf_vary_r tunable

The current crush_choose_firstn code will re-use the same 'r' value for
the recursive call.  That means that if we are hitting a collision or
rejection for some reason (say, an OSD that is marked out) and need to
retry, we will keep making the same (bad) choice in that recursive
selection.

Introduce a tunable that fixes that behavior by incorporating the parent
'r' value into the recursive starting point, so that a different path
will be taken in subsequent placement attempts.

Note that this was done from the get-go for the new crush_choose_indep
algorithm.

This was exposed by a user who was seeing PGs stuck in active+remapped
after reweight-by-utilization because the up set mapped to a single OSD.

Signed-off-by: Sage Weil <sage@inktank.com>
crush: add infrastructure around new chooseleaf_vary_r tunable

- encoding
- feature bit
- decompile/compile

Signed-off-by: Sage Weil <sage@inktank.com>
crush: add SET_CHOOSELEAF_VARY_R step

This lets you adjust the vary_r tunable on a per-rule basis.

Signed-off-by: Sage Weil <sage@inktank.com>
crush: add infrastructure around SET_CHOOSELEAF_VARY_R rule step/command

This will let you vary the vary_r tunable on a per-rule basis.

Signed-off-by: Sage Weil <sage@inktank.com>
crushtool: new cli tests for the vary-r tunable

These illustrate the variation in mapping results as the vary_r tunable
is adjusted.  Note:

1- For the vary_r=0 case, we have several inputs that map to only a single
output:

      rule 3 (delltestrule) num_rep 4 result size == 1:\t27/1024 (esc)
      rule 3 (delltestrule) num_rep 4 result size == 2:\t997/1024 (esc)

This is the behavior we are fixing.  For all of the other values of
vary_r, we get 2 outputs for all inputs.

2- If we use vary_r 1, which is likely the most efficient computation,
we get lots of inputs that change.  By setting larger values of vary_r,
we can trade a bit of extra computation to get a mapping that is more
similar to the legacy behavior. This is useful for legacy clusters:

    $ for f in `seq 1 4` ; do diff -u test-map-vary-r-0.t test-map-vary-r-$f.t | grep -c -- +  ; done
    3030
    1629
    645
    228

The crushmap here comes from a user who was seeing a bad mapping for certain
pgs after some OSDs were reweighted by utilization.

Signed-off-by: Sage Weil <sage@inktank.com>
crush: add firefly tunables baseline test

This is a user's map that gives different results when the vary_r tunable
is adjusted.

Signed-off-by: Sage Weil <sage@inktank.com>
doc/rados/operations/crush: describe new vary_r tunable

Signed-off-by: Sage Weil <sage@inktank.com>
mon: allow firefly crush tunables to be selected

Signed-off-by: Sage Weil <sage@inktank.com>
Merge pull request #1185 from ceph/wip-crush

crush: "vary_r" tunable

Reviewed-by: Loic Dachary <loic@dachary.org>