[ceph.git] / ceph / src / test / crush / crush.cc

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
/*
 * Ceph - scalable distributed file system
 *
 * Copyright (C) 2013 Inktank <info@inktank.com>
 *
 * LGPL2.1 (see COPYING-LGPL2.1) or later
 */

#include <iostream>
#include <memory>
#include <gtest/gtest.h>

#include "include/stringify.h"

#include "crush/CrushWrapper.h"
#include "osd/osd_types.h"

#include <set>

std::unique_ptr<CrushWrapper> build_indep_map(CephContext *cct, int num_rack,
                              int num_host, int num_osd)
{
  std::unique_ptr<CrushWrapper> c(new CrushWrapper);
  c->create();

  c->set_type_name(5, "root");
  c->set_type_name(4, "row");
  c->set_type_name(3, "rack");
  c->set_type_name(2, "chasis");
  c->set_type_name(1, "host");
  c->set_type_name(0, "osd");

  int rootno;
  c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
		5, 0, NULL, NULL, &rootno);
  c->set_item_name(rootno, "default");

  map<string,string> loc;
  loc["root"] = "default";

  int osd = 0;
  for (int r=0; r<num_rack; ++r) {
    loc["rack"] = string("rack-") + stringify(r);
    for (int h=0; h<num_host; ++h) {
      loc["host"] = string("host-") + stringify(r) + string("-") + stringify(h);
      for (int o=0; o<num_osd; ++o, ++osd) {
	c->insert_item(cct, osd, 1.0, string("osd.") + stringify(osd), loc);
      }
    }
  }
  int ret;
  int ruleno = 0;
  int rule = 0;
  ruleno = rule;
  ret = c->add_rule(4, rule, 123, 1, 20, ruleno);
  assert(ret == ruleno);
  ret = c->set_rule_step(ruleno, 0, CRUSH_RULE_SET_CHOOSELEAF_TRIES, 10, 0);
  assert(ret == 0);
  ret = c->set_rule_step(ruleno, 1, CRUSH_RULE_TAKE, rootno, 0);
  assert(ret == 0);
  ret = c->set_rule_step(ruleno, 2, CRUSH_RULE_CHOOSELEAF_INDEP, CRUSH_CHOOSE_N, 1);
  assert(ret == 0);
  ret = c->set_rule_step(ruleno, 3, CRUSH_RULE_EMIT, 0, 0);
  assert(ret == 0);
  c->set_rule_name(ruleno, "data");

  c->finalize();

  if (false) {
    Formatter *f = Formatter::create("json-pretty");
    f->open_object_section("crush_map");
    c->dump(f);
    f->close_section();
    f->flush(cout);
    delete f;
  }

  return c;
}

int get_num_dups(const vector<int>& v)
{
  std::set<int> s;
  int dups = 0;
  for (unsigned i=0; i<v.size(); ++i) {
    if (s.count(v[i]))
      ++dups;
    else if (v[i] != CRUSH_ITEM_NONE)
      s.insert(v[i]);
  }
  return dups;
}

TEST(CRUSH, indep_toosmall) {
  std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 1, 3, 1));
  vector<__u32> weight(c->get_max_devices(), 0x10000);
  c->dump_tree(&cout, NULL);

  for (int x = 0; x < 100; ++x) {
    vector<int> out;
    c->do_rule(0, x, out, 5, weight, 0);
    cout << x << " -> " << out << std::endl;
    int num_none = 0;
    for (unsigned i=0; i<out.size(); ++i) {
      if (out[i] == CRUSH_ITEM_NONE)
	num_none++;
    }
    ASSERT_EQ(2, num_none);
    ASSERT_EQ(0, get_num_dups(out));
  }
}

TEST(CRUSH, indep_basic) {
  std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3));
  vector<__u32> weight(c->get_max_devices(), 0x10000);
  c->dump_tree(&cout, NULL);

  for (int x = 0; x < 100; ++x) {
    vector<int> out;
    c->do_rule(0, x, out, 5, weight, 0);
    cout << x << " -> " << out << std::endl;
    int num_none = 0;
    for (unsigned i=0; i<out.size(); ++i) {
      if (out[i] == CRUSH_ITEM_NONE)
	num_none++;
    }
    ASSERT_EQ(0, num_none);
    ASSERT_EQ(0, get_num_dups(out));
  }
}

TEST(CRUSH, indep_out_alt) {
  std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3));
  vector<__u32> weight(c->get_max_devices(), 0x10000);

  // mark a bunch of osds out
  int num = 3*3*3;
  for (int i=0; i<num / 2; ++i)
    weight[i*2] = 0;
  c->dump_tree(&cout, NULL);

  // need more retries to get 9/9 hosts for x in 0..99
  c->set_choose_total_tries(100);
  for (int x = 0; x < 100; ++x) {
    vector<int> out;
    c->do_rule(0, x, out, 9, weight, 0);
    cout << x << " -> " << out << std::endl;
    int num_none = 0;
    for (unsigned i=0; i<out.size(); ++i) {
      if (out[i] == CRUSH_ITEM_NONE)
	num_none++;
    }
    ASSERT_EQ(0, num_none);
    ASSERT_EQ(0, get_num_dups(out));
  }
}

TEST(CRUSH, indep_out_contig) {
  std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3));
  vector<__u32> weight(c->get_max_devices(), 0x10000);

  // mark a bunch of osds out
  int num = 3*3*3;
  for (int i=0; i<num / 3; ++i)
    weight[i] = 0;
  c->dump_tree(&cout, NULL);

  c->set_choose_total_tries(100);
  for (int x = 0; x < 100; ++x) {
    vector<int> out;
    c->do_rule(0, x, out, 7, weight, 0);
    cout << x << " -> " << out << std::endl;
    int num_none = 0;
    for (unsigned i=0; i<out.size(); ++i) {
      if (out[i] == CRUSH_ITEM_NONE)
	num_none++;
    }
    ASSERT_EQ(1, num_none);
    ASSERT_EQ(0, get_num_dups(out));
  }
}


TEST(CRUSH, indep_out_progressive) {
  std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3));
  c->set_choose_total_tries(100);
  vector<__u32> tweight(c->get_max_devices(), 0x10000);
  c->dump_tree(&cout, NULL);

  int tchanged = 0;
  for (int x = 1; x < 5; ++x) {
    vector<__u32> weight(c->get_max_devices(), 0x10000);

    std::map<int,unsigned> pos;
    vector<int> prev;
    for (unsigned i=0; i<weight.size(); ++i) {
      vector<int> out;
      c->do_rule(0, x, out, 7, weight, 0);
      cout << "(" << i << "/" << weight.size() << " out) "
	   << x << " -> " << out << std::endl;
      int num_none = 0;
      for (unsigned k=0; k<out.size(); ++k) {
	if (out[k] == CRUSH_ITEM_NONE)
	  num_none++;
      }
      ASSERT_EQ(0, get_num_dups(out));

      // make sure nothing moved
      int moved = 0;
      int changed = 0;
      for (unsigned j=0; j<out.size(); ++j) {
	if (i && out[j] != prev[j]) {
	  ++changed;
	  ++tchanged;
	}
	if (out[j] == CRUSH_ITEM_NONE) {
	  continue;
	}
	if (i && pos.count(out[j])) {
	  // result shouldn't have moved position
	  if (j != pos[out[j]]) {
	    cout << " " << out[j] << " moved from " << pos[out[j]] << " to " << j << std::endl;
	    ++moved;
	  }
	  //ASSERT_EQ(j, pos[out[j]]);
	}
      }
      if (moved || changed)
	cout << " " << moved << " moved, " << changed << " changed" << std::endl;
      ASSERT_LE(moved, 1);
      ASSERT_LE(changed, 3);

      // mark another osd out
      weight[i] = 0;
      prev = out;
      pos.clear();
      for (unsigned j=0; j<out.size(); ++j) {
	if (out[j] != CRUSH_ITEM_NONE)
	  pos[out[j]] = j;
      }
    }
  }
  cout << tchanged << " total changed" << std::endl;

}

TEST(CRUSH, straw_zero) {
  // zero weight items should have no effect on placement.

  std::unique_ptr<CrushWrapper> c(new CrushWrapper);
  const int ROOT_TYPE = 1;
  c->set_type_name(ROOT_TYPE, "root");
  const int OSD_TYPE = 0;
  c->set_type_name(OSD_TYPE, "osd");

  int n = 5;
  int items[n], weights[n];
  for (int i=0; i <n; ++i) {
    items[i] = i;
    weights[i] = 0x10000 * (n-i-1);
  }

  c->set_max_devices(n);

  string root_name0("root0");
  int root0;
  EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
			     ROOT_TYPE, n, items, weights, &root0));
  EXPECT_EQ(0, c->set_item_name(root0, root_name0));

  string name0("rule0");
  int rule0 = c->add_simple_rule(name0, root_name0, "osd", "",
				       "firstn", pg_pool_t::TYPE_REPLICATED);
  EXPECT_EQ(0, rule0);

  string root_name1("root1");
  int root1;
  EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
			     ROOT_TYPE, n-1, items, weights, &root1));
  EXPECT_EQ(0, c->set_item_name(root1, root_name1));

  string name1("rule1");
  int rule1 = c->add_simple_rule(name1, root_name1, "osd", "",
				       "firstn", pg_pool_t::TYPE_REPLICATED);
  EXPECT_EQ(1, rule1);

  c->finalize();

  vector<unsigned> reweight(n, 0x10000);
  for (int i=0; i<10000; ++i) {
    vector<int> out0, out1;
    c->do_rule(rule0, i, out0, 1, reweight, 0);
    ASSERT_EQ(1u, out0.size());
    c->do_rule(rule1, i, out1, 1, reweight, 0);
    ASSERT_EQ(1u, out1.size());
    ASSERT_EQ(out0[0], out1[0]);
    //cout << i << "\t" << out0 << "\t" << out1 << std::endl;
  }
}

TEST(CRUSH, straw_same) {
  // items with the same weight should map about the same as items
  // with very similar weights.
  //
  // give the 0 vector a paired stair pattern, with dup weights.  note
  // that the original straw flaw does not appear when there are 2 of
  // the initial weight, but it does when there is just 1.
  //
  // give the 1 vector a similar stair pattern, but make the same
  // steps weights slightly different (no dups).  this works.
  //
  // compare the result and verify that the resulting mapping is
  // almost identical.

  std::unique_ptr<CrushWrapper> c(new CrushWrapper);
  const int ROOT_TYPE = 1;
  c->set_type_name(ROOT_TYPE, "root");
  const int OSD_TYPE = 0;
  c->set_type_name(OSD_TYPE, "osd");

  int n = 10;
  int items[n], weights[n];
  for (int i=0; i <n; ++i) {
    items[i] = i;
    weights[i] = 0x10000 * ((i+1)/2 + 1);
  }

  c->set_max_devices(n);

  string root_name0("root0");
  int root0;
  EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
			     ROOT_TYPE, n, items, weights, &root0));
  EXPECT_EQ(0, c->set_item_name(root0, root_name0));

  string name0("rule0");
  int rule0 = c->add_simple_rule(name0, root_name0, "osd", "",
				       "firstn", pg_pool_t::TYPE_REPLICATED);
  EXPECT_EQ(0, rule0);

  for (int i=0; i <n; ++i) {
    items[i] = i;
    weights[i] = 0x10000 * ((i+1)/2 + 1) + (i%2)*100;
  }

  string root_name1("root1");
  int root1;
  EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
			     ROOT_TYPE, n, items, weights, &root1));
  EXPECT_EQ(0, c->set_item_name(root1, root_name1));

  string name1("rule1");
  int rule1 = c->add_simple_rule(name1, root_name1, "osd", "",
				       "firstn", pg_pool_t::TYPE_REPLICATED);
  EXPECT_EQ(1, rule1);

  if (0) {
    crush_bucket_straw *sb0 = reinterpret_cast<crush_bucket_straw*>(c->get_crush_map()->buckets[-1-root0]);
    crush_bucket_straw *sb1 = reinterpret_cast<crush_bucket_straw*>(c->get_crush_map()->buckets[-1-root1]);

    for (int i=0; i<n; ++i) {
      cout << i
	   << "\t" << sb0->item_weights[i]
	   << "\t" << sb1->item_weights[i]
	   << "\t"
	   << "\t" << sb0->straws[i]
	   << "\t" << sb1->straws[i]
	   << std::endl;
    }
  }

  if (0) {
    JSONFormatter jf(true);
    jf.open_object_section("crush");
    c->dump(&jf);
    jf.close_section();
    jf.flush(cout);
  }

  c->finalize();

  vector<int> sum0(n, 0), sum1(n, 0);
  vector<unsigned> reweight(n, 0x10000);
  int different = 0;
  int max = 100000;
  for (int i=0; i<max; ++i) {
    vector<int> out0, out1;
    c->do_rule(rule0, i, out0, 1, reweight, 0);
    ASSERT_EQ(1u, out0.size());
    c->do_rule(rule1, i, out1, 1, reweight, 0);
    ASSERT_EQ(1u, out1.size());
    sum0[out0[0]]++;
    sum1[out1[0]]++;
    if (out0[0] != out1[0])
      different++;
  }
  for (int i=0; i<n; ++i) {
    cout << i
	 << "\t" << ((double)weights[i] / (double)weights[0])
	 << "\t" << sum0[i] << "\t" << ((double)sum0[i]/(double)sum0[0])
	 << "\t" << sum1[i] << "\t" << ((double)sum1[i]/(double)sum1[0])
	 << std::endl;
  }
  double ratio = ((double)different / (double)max);
  cout << different << " of " << max << " = "
       << ratio
       << " different" << std::endl;
  ASSERT_LT(ratio, .001);
}

double calc_straw2_stddev(int *weights, int n, bool verbose)
{
  std::unique_ptr<CrushWrapper> c(new CrushWrapper);
  const int ROOT_TYPE = 2;
  c->set_type_name(ROOT_TYPE, "root");
  const int HOST_TYPE = 1;
  c->set_type_name(HOST_TYPE, "host");
  const int OSD_TYPE = 0;
  c->set_type_name(OSD_TYPE, "osd");

  int items[n];
  for (int i=0; i <n; ++i) {
    items[i] = i;
  }

  c->set_max_devices(n);

  string root_name0("root0");
  int root0;
  crush_bucket *b0 = crush_make_bucket(c->get_crush_map(),
				       CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1,
				       ROOT_TYPE, n, items, weights);
  crush_add_bucket(c->get_crush_map(), 0, b0, &root0);
  c->set_item_name(root0, root_name0);

  string name0("rule0");
  int rule0 = c->add_simple_rule(name0, root_name0, "osd", "",
				       "firstn", pg_pool_t::TYPE_REPLICATED);

  int sum[n];
  double totalweight = 0;
  vector<unsigned> reweight(n);
  for (int i=0; i<n; ++i) {
    sum[i] = 0;
    reweight[i] = 0x10000;
    totalweight += weights[i];
  }
  totalweight /= (double)0x10000;
  double avgweight = totalweight / n;

  c->finalize();

  int total = 1000000;
  for (int i=0; i<total; ++i) {
    vector<int> out;
    c->do_rule(rule0, i, out, 1, reweight, 0);
    sum[out[0]]++;
  }

  double expected = (double)total / (double)n;
  if (verbose)
    cout << "expect\t\t\t" << expected << std::endl;
  double stddev = 0;
  double exptotal = 0;
  if (verbose)
    cout << "osd\tweight\tcount\tadjusted\n";
  std::streamsize p = cout.precision();
  cout << std::setprecision(4);
  for (int i=0; i<n; ++i) {
    double w = (double)weights[i] / (double)0x10000;
    double adj = (double)sum[i] * avgweight / w;
    stddev += (adj - expected) * (adj - expected);
    exptotal += adj;
    if (verbose)
      cout << i
	   << "\t" << w
	   << "\t" << sum[i]
	   << "\t" << (int)adj
	   << std::endl;
  }
  cout << std::setprecision(p);
  {
    stddev = sqrt(stddev / (double)n);
    if (verbose)
      cout << "std dev " << stddev << std::endl;

    double p = 1.0 / (double)n;
    double estddev = sqrt(exptotal * p * (1.0 - p));
    if (verbose)
      cout << "     vs " << estddev << "\t(expected)" << std::endl;
  }
  return stddev;
}

TEST(CRUSH, straw2_stddev)
{
  int n = 15;
  int weights[n];
  cout << "maxskew\tstddev\n";
  for (double step = 1.0; step < 2; step += .25) {
    int w = 0x10000;
    for (int i = 0; i < n; ++i) {
      weights[i] = w;
      w *= step;
    }
    double stddev = calc_straw2_stddev(weights, n, true);
    cout << ((double)weights[n-1]/(double)weights[0])
	 << "\t" << stddev << std::endl;
  }
}

TEST(CRUSH, straw2_reweight) {
  // when we adjust the weight of an item in a straw2 bucket,
  // we should *only* see movement from or to that item, never
  // between other items.
  int weights[] = {
    0x10000,
    0x10000,
    0x20000,
    0x20000,
    0x30000,
    0x50000,
    0x8000,
    0x20000,
    0x10000,
    0x10000,
    0x20000,
    0x10000,
    0x10000,
    0x20000,
    0x300000,
    0x10000,
    0x20000
  };
  int n = 15;

  std::unique_ptr<CrushWrapper> c(new CrushWrapper);
  const int ROOT_TYPE = 2;
  c->set_type_name(ROOT_TYPE, "root");
  const int HOST_TYPE = 1;
  c->set_type_name(HOST_TYPE, "host");
  const int OSD_TYPE = 0;
  c->set_type_name(OSD_TYPE, "osd");

  int items[n];
  for (int i=0; i <n; ++i) {
    items[i] = i;
    //weights[i] = 0x10000;
  }

  c->set_max_devices(n);

  string root_name0("root0");
  int root0;
  crush_bucket *b0 = crush_make_bucket(c->get_crush_map(),
				       CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1,
				       ROOT_TYPE, n, items, weights);
  EXPECT_EQ(0, crush_add_bucket(c->get_crush_map(), 0, b0, &root0));
  EXPECT_EQ(0, c->set_item_name(root0, root_name0));

  string name0("rule0");
  int rule0 = c->add_simple_rule(name0, root_name0, "osd", "",
				       "firstn", pg_pool_t::TYPE_REPLICATED);
  EXPECT_EQ(0, rule0);

  int changed = 1;
  weights[changed] = weights[changed] / 10 * (rand() % 10);

  string root_name1("root1");
  int root1;
  crush_bucket *b1 = crush_make_bucket(c->get_crush_map(),
				       CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1,
				       ROOT_TYPE, n, items, weights);
  EXPECT_EQ(0, crush_add_bucket(c->get_crush_map(), 0, b1, &root1));
  EXPECT_EQ(0, c->set_item_name(root1, root_name1));

  string name1("rule1");
  int rule1 = c->add_simple_rule(name1, root_name1, "osd", "",
				       "firstn", pg_pool_t::TYPE_REPLICATED);
  EXPECT_EQ(1, rule1);

  int sum[n];
  double totalweight = 0;
  vector<unsigned> reweight(n);
  for (int i=0; i<n; ++i) {
    sum[i] = 0;
    reweight[i] = 0x10000;
    totalweight += weights[i];
  }
  totalweight /= (double)0x10000;
  double avgweight = totalweight / n;

  c->finalize();

  int total = 1000000;
  for (int i=0; i<total; ++i) {
    vector<int> out0, out1;
    c->do_rule(rule0, i, out0, 1, reweight, 0);
    ASSERT_EQ(1u, out0.size());

    c->do_rule(rule1, i, out1, 1, reweight, 0);
    ASSERT_EQ(1u, out1.size());

    sum[out1[0]]++;
    //sum[rand()%n]++;

    if (out1[0] == changed) {
      ASSERT_EQ(changed, out0[0]);
    } else if (out0[0] != changed) {
      ASSERT_EQ(out0[0], out1[0]);
    }
  }

  double expected = (double)total / (double)n;
  cout << "expect\t\t\t" << expected << std::endl;
  double stddev = 0;
  cout << "osd\tweight\tcount\tadjusted\n";
  std::streamsize p = cout.precision();
  cout << std::setprecision(4);
  for (int i=0; i<n; ++i) {
    double w = (double)weights[i] / (double)0x10000;
    double adj = (double)sum[i] * avgweight / w;
    stddev += (adj - expected) * (adj - expected);
    cout << i
	 << "\t" << w
	 << "\t" << sum[i]
	 << "\t" << (int)adj
	 << std::endl;
  }
  cout << std::setprecision(p);
  {
    stddev = sqrt(stddev / (double)n);
    cout << "std dev " << stddev << std::endl;

    double p = 1.0 / (double)n;
    double estddev = sqrt((double)total * p * (1.0 - p));
    cout << "     vs " << estddev << std::endl;
  }
}
Commit	Line	Data
7c673cae FG	1	// -- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t --
	2	// vim: ts=8 sw=2 smarttab
	3	/*
	4	* Ceph - scalable distributed file system
	5	*
	6	* Copyright (C) 2013 Inktank <info@inktank.com>
	7	*
	8	* LGPL2.1 (see COPYING-LGPL2.1) or later
	9	*/
	10
	11	#include <iostream>
	12	#include <memory>
	13	#include <gtest/gtest.h>
	14
	15	#include "include/stringify.h"
	16
	17	#include "crush/CrushWrapper.h"
	18	#include "osd/osd_types.h"
	19
	20	#include <set>
	21
	22	std::unique_ptr<CrushWrapper> build_indep_map(CephContext *cct, int num_rack,
	23	int num_host, int num_osd)
	24	{
	25	std::unique_ptr<CrushWrapper> c(new CrushWrapper);
	26	c->create();
	27
	28	c->set_type_name(5, "root");
	29	c->set_type_name(4, "row");
	30	c->set_type_name(3, "rack");
	31	c->set_type_name(2, "chasis");
	32	c->set_type_name(1, "host");
	33	c->set_type_name(0, "osd");
	34
	35	int rootno;
	36	c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
	37	5, 0, NULL, NULL, &rootno);
	38	c->set_item_name(rootno, "default");
	39
	40	map<string,string> loc;
	41	loc["root"] = "default";
	42
	43	int osd = 0;
	44	for (int r=0; r<num_rack; ++r) {
	45	loc["rack"] = string("rack-") + stringify(r);
	46	for (int h=0; h<num_host; ++h) {
	47	loc["host"] = string("host-") + stringify(r) + string("-") + stringify(h);
	48	for (int o=0; o<num_osd; ++o, ++osd) {
	49	c->insert_item(cct, osd, 1.0, string("osd.") + stringify(osd), loc);
	50	}
	51	}
	52	}
	53	int ret;
	54	int ruleno = 0;
31f18b77 FG	55	int rule = 0;
	56	ruleno = rule;
	57	ret = c->add_rule(4, rule, 123, 1, 20, ruleno);
7c673cae FG	58	assert(ret == ruleno);
	59	ret = c->set_rule_step(ruleno, 0, CRUSH_RULE_SET_CHOOSELEAF_TRIES, 10, 0);
	60	assert(ret == 0);
	61	ret = c->set_rule_step(ruleno, 1, CRUSH_RULE_TAKE, rootno, 0);
	62	assert(ret == 0);
	63	ret = c->set_rule_step(ruleno, 2, CRUSH_RULE_CHOOSELEAF_INDEP, CRUSH_CHOOSE_N, 1);
	64	assert(ret == 0);
	65	ret = c->set_rule_step(ruleno, 3, CRUSH_RULE_EMIT, 0, 0);
	66	assert(ret == 0);
	67	c->set_rule_name(ruleno, "data");
	68
	69	c->finalize();
	70
	71	if (false) {
	72	Formatter *f = Formatter::create("json-pretty");
	73	f->open_object_section("crush_map");
	74	c->dump(f);
	75	f->close_section();
	76	f->flush(cout);
	77	delete f;
	78	}
	79
	80	return c;
	81	}
	82
	83	int get_num_dups(const vector<int>& v)
	84	{
	85	std::set<int> s;
	86	int dups = 0;
	87	for (unsigned i=0; i<v.size(); ++i) {
	88	if (s.count(v[i]))
	89	++dups;
	90	else if (v[i] != CRUSH_ITEM_NONE)
	91	s.insert(v[i]);
	92	}
	93	return dups;
	94	}
	95
	96	TEST(CRUSH, indep_toosmall) {
	97	std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 1, 3, 1));
	98	vector<__u32> weight(c->get_max_devices(), 0x10000);
	99	c->dump_tree(&cout, NULL);
	100
	101	for (int x = 0; x < 100; ++x) {
	102	vector<int> out;
	103	c->do_rule(0, x, out, 5, weight, 0);
	104	cout << x << " -> " << out << std::endl;
	105	int num_none = 0;
	106	for (unsigned i=0; i<out.size(); ++i) {
	107	if (out[i] == CRUSH_ITEM_NONE)
	108	num_none++;
	109	}
	110	ASSERT_EQ(2, num_none);
	111	ASSERT_EQ(0, get_num_dups(out));
	112	}
	113	}
	114
	115	TEST(CRUSH, indep_basic) {
	116	std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3));
	117	vector<__u32> weight(c->get_max_devices(), 0x10000);
	118	c->dump_tree(&cout, NULL);
	119
	120	for (int x = 0; x < 100; ++x) {
	121	vector<int> out;
122	c->do_rule(0, x, out, 5, weight, 0);
123	cout << x << " -> " << out << std::endl;
124	int num_none = 0;
125	for (unsigned i=0; i<out.size(); ++i) {
126	if (out[i] == CRUSH_ITEM_NONE)
127	num_none++;
128	}
129	ASSERT_EQ(0, num_none);
130	ASSERT_EQ(0, get_num_dups(out));
131	}
132	}
133
134	TEST(CRUSH, indep_out_alt) {
135	std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3));
136	vector<__u32> weight(c->get_max_devices(), 0x10000);
137
138	// mark a bunch of osds out
139	int num = 333;
140	for (int i=0; i<num / 2; ++i)
141	weight[i*2] = 0;
142	c->dump_tree(&cout, NULL);
143
144	// need more retries to get 9/9 hosts for x in 0..99
145	c->set_choose_total_tries(100);
146	for (int x = 0; x < 100; ++x) {
147	vector<int> out;
148	c->do_rule(0, x, out, 9, weight, 0);
149	cout << x << " -> " << out << std::endl;
150	int num_none = 0;
151	for (unsigned i=0; i<out.size(); ++i) {
152	if (out[i] == CRUSH_ITEM_NONE)
153	num_none++;
154	}
155	ASSERT_EQ(0, num_none);
156	ASSERT_EQ(0, get_num_dups(out));
157	}
158	}
159
160	TEST(CRUSH, indep_out_contig) {
161	std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3));
162	vector<__u32> weight(c->get_max_devices(), 0x10000);
163
164	// mark a bunch of osds out
165	int num = 333;
166	for (int i=0; i<num / 3; ++i)
167	weight[i] = 0;
168	c->dump_tree(&cout, NULL);
169
170	c->set_choose_total_tries(100);
171	for (int x = 0; x < 100; ++x) {
172	vector<int> out;
173	c->do_rule(0, x, out, 7, weight, 0);
174	cout << x << " -> " << out << std::endl;
175	int num_none = 0;
176	for (unsigned i=0; i<out.size(); ++i) {
177	if (out[i] == CRUSH_ITEM_NONE)
178	num_none++;
179	}
180	ASSERT_EQ(1, num_none);
181	ASSERT_EQ(0, get_num_dups(out));
182	}
183	}
184
185
186	TEST(CRUSH, indep_out_progressive) {
187	std::unique_ptr<CrushWrapper> c(build_indep_map(g_ceph_context, 3, 3, 3));
188	c->set_choose_total_tries(100);
189	vector<__u32> tweight(c->get_max_devices(), 0x10000);
190	c->dump_tree(&cout, NULL);
191
192	int tchanged = 0;
193	for (int x = 1; x < 5; ++x) {
194	vector<__u32> weight(c->get_max_devices(), 0x10000);
195
196	std::map<int,unsigned> pos;
197	vector<int> prev;
198	for (unsigned i=0; i<weight.size(); ++i) {
199	vector<int> out;
200	c->do_rule(0, x, out, 7, weight, 0);
201	cout << "(" << i << "/" << weight.size() << " out) "
202	<< x << " -> " << out << std::endl;
203	int num_none = 0;
204	for (unsigned k=0; k<out.size(); ++k) {
205	if (out[k] == CRUSH_ITEM_NONE)
206	num_none++;
207	}
208	ASSERT_EQ(0, get_num_dups(out));
209
210	// make sure nothing moved
211	int moved = 0;
212	int changed = 0;
213	for (unsigned j=0; j<out.size(); ++j) {
214	if (i && out[j] != prev[j]) {
215	++changed;
216	++tchanged;
217	}
218	if (out[j] == CRUSH_ITEM_NONE) {
219	continue;
220	}
221	if (i && pos.count(out[j])) {
222	// result shouldn't have moved position
223	if (j != pos[out[j]]) {
224	cout << " " << out[j] << " moved from " << pos[out[j]] << " to " << j << std::endl;
225	++moved;
226	}
227	//ASSERT_EQ(j, pos[out[j]]);
228	}
229	}
230	if (moved \|\| changed)
231	cout << " " << moved << " moved, " << changed << " changed" << std::endl;
232	ASSERT_LE(moved, 1);
233	ASSERT_LE(changed, 3);
234
235	// mark another osd out
236	weight[i] = 0;
237	prev = out;
238	pos.clear();
239	for (unsigned j=0; j<out.size(); ++j) {
240	if (out[j] != CRUSH_ITEM_NONE)
241	pos[out[j]] = j;
242	}
243	}
244	}
245	cout << tchanged << " total changed" << std::endl;
246
247	}
248
249	TEST(CRUSH, straw_zero) {
250	// zero weight items should have no effect on placement.
251
252	std::unique_ptr<CrushWrapper> c(new CrushWrapper);
253	const int ROOT_TYPE = 1;
254	c->set_type_name(ROOT_TYPE, "root");
255	const int OSD_TYPE = 0;
256	c->set_type_name(OSD_TYPE, "osd");
257
258	int n = 5;
259	int items[n], weights[n];
260	for (int i=0; i <n; ++i) {
261	items[i] = i;
262	weights[i] = 0x10000 * (n-i-1);
263	}
264
265	c->set_max_devices(n);
266
267	string root_name0("root0");
268	int root0;
269	EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
270	ROOT_TYPE, n, items, weights, &root0));
271	EXPECT_EQ(0, c->set_item_name(root0, root_name0));
272
273	string name0("rule0");
224ce89b	274	int rule0 = c->add_simple_rule(name0, root_name0, "osd", "",
7c673cae	275	"firstn", pg_pool_t::TYPE_REPLICATED);
31f18b77	276	EXPECT_EQ(0, rule0);
7c673cae FG	277
	278	string root_name1("root1");
	279	int root1;
	280	EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
	281	ROOT_TYPE, n-1, items, weights, &root1));
	282	EXPECT_EQ(0, c->set_item_name(root1, root_name1));
	283
	284	string name1("rule1");
224ce89b	285	int rule1 = c->add_simple_rule(name1, root_name1, "osd", "",
7c673cae	286	"firstn", pg_pool_t::TYPE_REPLICATED);
31f18b77	287	EXPECT_EQ(1, rule1);
7c673cae FG	288
	289	c->finalize();
	290
	291	vector<unsigned> reweight(n, 0x10000);
	292	for (int i=0; i<10000; ++i) {
	293	vector<int> out0, out1;
31f18b77	294	c->do_rule(rule0, i, out0, 1, reweight, 0);
7c673cae	295	ASSERT_EQ(1u, out0.size());
31f18b77	296	c->do_rule(rule1, i, out1, 1, reweight, 0);
7c673cae FG	297	ASSERT_EQ(1u, out1.size());
	298	ASSERT_EQ(out0[0], out1[0]);
	299	//cout << i << "\t" << out0 << "\t" << out1 << std::endl;
	300	}
	301	}
	302
	303	TEST(CRUSH, straw_same) {
	304	// items with the same weight should map about the same as items
	305	// with very similar weights.
	306	//
	307	// give the 0 vector a paired stair pattern, with dup weights. note
	308	// that the original straw flaw does not appear when there are 2 of
	309	// the initial weight, but it does when there is just 1.
	310	//
	311	// give the 1 vector a similar stair pattern, but make the same
	312	// steps weights slightly different (no dups). this works.
	313	//
	314	// compare the result and verify that the resulting mapping is
	315	// almost identical.
	316
	317	std::unique_ptr<CrushWrapper> c(new CrushWrapper);
	318	const int ROOT_TYPE = 1;
	319	c->set_type_name(ROOT_TYPE, "root");
	320	const int OSD_TYPE = 0;
	321	c->set_type_name(OSD_TYPE, "osd");
	322
	323	int n = 10;
	324	int items[n], weights[n];
	325	for (int i=0; i <n; ++i) {
	326	items[i] = i;
	327	weights[i] = 0x10000 * ((i+1)/2 + 1);
	328	}
	329
	330	c->set_max_devices(n);
	331
	332	string root_name0("root0");
	333	int root0;
	334	EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
	335	ROOT_TYPE, n, items, weights, &root0));
	336	EXPECT_EQ(0, c->set_item_name(root0, root_name0));
	337
	338	string name0("rule0");
224ce89b	339	int rule0 = c->add_simple_rule(name0, root_name0, "osd", "",
7c673cae	340	"firstn", pg_pool_t::TYPE_REPLICATED);
31f18b77	341	EXPECT_EQ(0, rule0);
7c673cae FG	342
	343	for (int i=0; i <n; ++i) {
	344	items[i] = i;
	345	weights[i] = 0x10000 * ((i+1)/2 + 1) + (i%2)*100;
	346	}
	347
	348	string root_name1("root1");
	349	int root1;
	350	EXPECT_EQ(0, c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
	351	ROOT_TYPE, n, items, weights, &root1));
	352	EXPECT_EQ(0, c->set_item_name(root1, root_name1));
	353
	354	string name1("rule1");
224ce89b	355	int rule1 = c->add_simple_rule(name1, root_name1, "osd", "",
7c673cae	356	"firstn", pg_pool_t::TYPE_REPLICATED);
31f18b77	357	EXPECT_EQ(1, rule1);
7c673cae FG	358
	359	if (0) {
	360	crush_bucket_straw sb0 = reinterpret_cast<crush_bucket_straw>(c->get_crush_map()->buckets[-1-root0]);
	361	crush_bucket_straw sb1 = reinterpret_cast<crush_bucket_straw>(c->get_crush_map()->buckets[-1-root1]);
	362
	363	for (int i=0; i<n; ++i) {
	364	cout << i
	365	<< "\t" << sb0->item_weights[i]
	366	<< "\t" << sb1->item_weights[i]
	367	<< "\t"
	368	<< "\t" << sb0->straws[i]
	369	<< "\t" << sb1->straws[i]
	370	<< std::endl;
	371	}
	372	}
	373
	374	if (0) {
	375	JSONFormatter jf(true);
	376	jf.open_object_section("crush");
	377	c->dump(&jf);
	378	jf.close_section();
	379	jf.flush(cout);
	380	}
	381
	382	c->finalize();
	383
	384	vector<int> sum0(n, 0), sum1(n, 0);
	385	vector<unsigned> reweight(n, 0x10000);
	386	int different = 0;
	387	int max = 100000;
	388	for (int i=0; i<max; ++i) {
	389	vector<int> out0, out1;
31f18b77	390	c->do_rule(rule0, i, out0, 1, reweight, 0);
7c673cae	391	ASSERT_EQ(1u, out0.size());
31f18b77	392	c->do_rule(rule1, i, out1, 1, reweight, 0);
7c673cae FG	393	ASSERT_EQ(1u, out1.size());
	394	sum0[out0[0]]++;
	395	sum1[out1[0]]++;
	396	if (out0[0] != out1[0])
	397	different++;
	398	}
	399	for (int i=0; i<n; ++i) {
	400	cout << i
	401	<< "\t" << ((double)weights[i] / (double)weights[0])
	402	<< "\t" << sum0[i] << "\t" << ((double)sum0[i]/(double)sum0[0])
	403	<< "\t" << sum1[i] << "\t" << ((double)sum1[i]/(double)sum1[0])
	404	<< std::endl;
	405	}
	406	double ratio = ((double)different / (double)max);
	407	cout << different << " of " << max << " = "
	408	<< ratio
	409	<< " different" << std::endl;
	410	ASSERT_LT(ratio, .001);
	411	}
	412
	413	double calc_straw2_stddev(int *weights, int n, bool verbose)
	414	{
	415	std::unique_ptr<CrushWrapper> c(new CrushWrapper);
	416	const int ROOT_TYPE = 2;
	417	c->set_type_name(ROOT_TYPE, "root");
	418	const int HOST_TYPE = 1;
	419	c->set_type_name(HOST_TYPE, "host");
	420	const int OSD_TYPE = 0;
	421	c->set_type_name(OSD_TYPE, "osd");
	422
	423	int items[n];
	424	for (int i=0; i <n; ++i) {
	425	items[i] = i;
	426	}
	427
	428	c->set_max_devices(n);
	429
	430	string root_name0("root0");
	431	int root0;
	432	crush_bucket *b0 = crush_make_bucket(c->get_crush_map(),
	433	CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1,
	434	ROOT_TYPE, n, items, weights);
	435	crush_add_bucket(c->get_crush_map(), 0, b0, &root0);
	436	c->set_item_name(root0, root_name0);
	437
	438	string name0("rule0");
224ce89b	439	int rule0 = c->add_simple_rule(name0, root_name0, "osd", "",
7c673cae FG	440	"firstn", pg_pool_t::TYPE_REPLICATED);
	441
	442	int sum[n];
	443	double totalweight = 0;
	444	vector<unsigned> reweight(n);
	445	for (int i=0; i<n; ++i) {
	446	sum[i] = 0;
	447	reweight[i] = 0x10000;
	448	totalweight += weights[i];
	449	}
	450	totalweight /= (double)0x10000;
	451	double avgweight = totalweight / n;
	452
	453	c->finalize();
	454
	455	int total = 1000000;
	456	for (int i=0; i<total; ++i) {
	457	vector<int> out;
31f18b77	458	c->do_rule(rule0, i, out, 1, reweight, 0);
7c673cae FG	459	sum[out[0]]++;
	460	}
	461
	462	double expected = (double)total / (double)n;
	463	if (verbose)
	464	cout << "expect\t\t\t" << expected << std::endl;
	465	double stddev = 0;
	466	double exptotal = 0;
	467	if (verbose)
	468	cout << "osd\tweight\tcount\tadjusted\n";
	469	std::streamsize p = cout.precision();
	470	cout << std::setprecision(4);
	471	for (int i=0; i<n; ++i) {
	472	double w = (double)weights[i] / (double)0x10000;
	473	double adj = (double)sum[i] * avgweight / w;
	474	stddev += (adj - expected) * (adj - expected);
	475	exptotal += adj;
	476	if (verbose)
	477	cout << i
	478	<< "\t" << w
	479	<< "\t" << sum[i]
	480	<< "\t" << (int)adj
	481	<< std::endl;
	482	}
	483	cout << std::setprecision(p);
	484	{
	485	stddev = sqrt(stddev / (double)n);
	486	if (verbose)
	487	cout << "std dev " << stddev << std::endl;
	488
	489	double p = 1.0 / (double)n;
	490	double estddev = sqrt(exptotal * p * (1.0 - p));
	491	if (verbose)
	492	cout << " vs " << estddev << "\t(expected)" << std::endl;
	493	}
	494	return stddev;
	495	}
	496
	497	TEST(CRUSH, straw2_stddev)
	498	{
	499	int n = 15;
	500	int weights[n];
	501	cout << "maxskew\tstddev\n";
	502	for (double step = 1.0; step < 2; step += .25) {
	503	int w = 0x10000;
	504	for (int i = 0; i < n; ++i) {
	505	weights[i] = w;
	506	w *= step;
	507	}
	508	double stddev = calc_straw2_stddev(weights, n, true);
	509	cout << ((double)weights[n-1]/(double)weights[0])
	510	<< "\t" << stddev << std::endl;
	511	}
	512	}
	513
	514	TEST(CRUSH, straw2_reweight) {
	515	// when we adjust the weight of an item in a straw2 bucket,
	516	// we should only see movement from or to that item, never
	517	// between other items.
	518	int weights[] = {
	519	0x10000,
	520	0x10000,
	521	0x20000,
	522	0x20000,
523	0x30000,
524	0x50000,
525	0x8000,
526	0x20000,
527	0x10000,
528	0x10000,
529	0x20000,
530	0x10000,
531	0x10000,
532	0x20000,
533	0x300000,
534	0x10000,
535	0x20000
536	};
537	int n = 15;
538
539	std::unique_ptr<CrushWrapper> c(new CrushWrapper);
540	const int ROOT_TYPE = 2;
541	c->set_type_name(ROOT_TYPE, "root");
542	const int HOST_TYPE = 1;
543	c->set_type_name(HOST_TYPE, "host");
544	const int OSD_TYPE = 0;
545	c->set_type_name(OSD_TYPE, "osd");
546
547	int items[n];
548	for (int i=0; i <n; ++i) {
549	items[i] = i;
550	//weights[i] = 0x10000;
551	}
552
553	c->set_max_devices(n);
554
555	string root_name0("root0");
556	int root0;
557	crush_bucket *b0 = crush_make_bucket(c->get_crush_map(),
558	CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1,
559	ROOT_TYPE, n, items, weights);
560	EXPECT_EQ(0, crush_add_bucket(c->get_crush_map(), 0, b0, &root0));
561	EXPECT_EQ(0, c->set_item_name(root0, root_name0));
562
563	string name0("rule0");
224ce89b	564	int rule0 = c->add_simple_rule(name0, root_name0, "osd", "",
7c673cae	565	"firstn", pg_pool_t::TYPE_REPLICATED);
31f18b77	566	EXPECT_EQ(0, rule0);
7c673cae FG	567
	568	int changed = 1;
	569	weights[changed] = weights[changed] / 10 * (rand() % 10);
	570
	571	string root_name1("root1");
	572	int root1;
	573	crush_bucket *b1 = crush_make_bucket(c->get_crush_map(),
	574	CRUSH_BUCKET_STRAW2, CRUSH_HASH_RJENKINS1,
	575	ROOT_TYPE, n, items, weights);
	576	EXPECT_EQ(0, crush_add_bucket(c->get_crush_map(), 0, b1, &root1));
	577	EXPECT_EQ(0, c->set_item_name(root1, root_name1));
	578
	579	string name1("rule1");
224ce89b	580	int rule1 = c->add_simple_rule(name1, root_name1, "osd", "",
7c673cae	581	"firstn", pg_pool_t::TYPE_REPLICATED);
31f18b77	582	EXPECT_EQ(1, rule1);
7c673cae FG	583
	584	int sum[n];
	585	double totalweight = 0;
	586	vector<unsigned> reweight(n);
	587	for (int i=0; i<n; ++i) {
	588	sum[i] = 0;
	589	reweight[i] = 0x10000;
	590	totalweight += weights[i];
	591	}
	592	totalweight /= (double)0x10000;
	593	double avgweight = totalweight / n;
	594
	595	c->finalize();
	596
	597	int total = 1000000;
	598	for (int i=0; i<total; ++i) {
	599	vector<int> out0, out1;
31f18b77	600	c->do_rule(rule0, i, out0, 1, reweight, 0);
7c673cae FG	601	ASSERT_EQ(1u, out0.size());
7c673cae FG	602
31f18b77	603	c->do_rule(rule1, i, out1, 1, reweight, 0);
7c673cae FG	604	ASSERT_EQ(1u, out1.size());
	605
	606	sum[out1[0]]++;
	607	//sum[rand()%n]++;
	608
	609	if (out1[0] == changed) {
	610	ASSERT_EQ(changed, out0[0]);
	611	} else if (out0[0] != changed) {
	612	ASSERT_EQ(out0[0], out1[0]);
	613	}
	614	}
	615
	616	double expected = (double)total / (double)n;
	617	cout << "expect\t\t\t" << expected << std::endl;
	618	double stddev = 0;
	619	cout << "osd\tweight\tcount\tadjusted\n";
	620	std::streamsize p = cout.precision();
	621	cout << std::setprecision(4);
	622	for (int i=0; i<n; ++i) {
	623	double w = (double)weights[i] / (double)0x10000;
	624	double adj = (double)sum[i] * avgweight / w;
	625	stddev += (adj - expected) * (adj - expected);
	626	cout << i
	627	<< "\t" << w
	628	<< "\t" << sum[i]
	629	<< "\t" << (int)adj
	630	<< std::endl;
	631	}
	632	cout << std::setprecision(p);
	633	{
	634	stddev = sqrt(stddev / (double)n);
	635	cout << "std dev " << stddev << std::endl;
	636
	637	double p = 1.0 / (double)n;
	638	double estddev = sqrt((double)total * p * (1.0 - p));
	639	cout << " vs " << estddev << std::endl;
	640	}
	641	}