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