CRUSH(X) -> (OSDi, OSDj, OSDk)

host test1{                          //类型host，名字为test1
	id -2                            //bucket的id，一般为负值
	# weight 3.000                   //权重，默认为子item的权重之和
	alg straw                        //bucket随机选择的算法
	hash 0                           //bucket随机选择的算法使用的hash函数，这里0代表使用hash函数jenkins1

	item osd.1 weight 1.000          //item1: osd.1和权重
	item osd.2 weight 1.000
	item osd.3 weight 1.000
}


host test2{                          
	id -3                            
	# weight 3.000                   
	alg straw                        
	hash 0                           

	item osd.3 weight 1.000          
	item osd.4 weight 1.000
	item osd.5 weight 1.000
}


root default{                   //root的类型为bucket，名字为default
	id -1                       //id号
	# weight 6.000                 
	alg straw
	hash 0

	item test1 weight 3.000
	item test2 weight 3.000
}

take(a)
choose
	choose firstn {num} type {bucket-type}
	chooseleaf firstn {num} type {bucket-type} 
		If {num} == 0, choose pool-num-replicas buckets (all-available).
		If {num} > 0 && < pool-num-replicas, choose that many buckets.
		If {num} < 0, it means pool-num-replicas - |{num}|.
Emit

rule replicated_sata {
        ruleset 5
        type replicated
        min_size 1
        max_size 10
        step take ceph-test-sata
        step chooseleaf firstn 0 type rack
        step emit
}

rule replicated_ruleset {
	ruleset 0                          //ruleset的编号id
	type replicated                    //类型replicated或者erasure code	
	min_size 1                         //副本数最小值
	max_size 10                        //副本数最大值
	
	step take root                     //选择一个root bucket，做下一步的输入
	step choose firstn 1 type row      //选择一个row，同一排
	step choose firstn 3 type cabinet  //选择三个cabinet，三副本分别在不同的cabinet
	step choose firstn 1 type osd      //在上一步输出的3个cabinet中，分别选择一个OSD
	step emit
}

rule ssd-primary {
	ruleset 5
	type replicated
	min_size 5
	max_size 10
	step take ssd                        //选择ssd这个root bucket为输入
	step chooseleaf firstn 1 type host   //选择一个host, 并递归选择叶子节点OSD
	step emit                            //输出结果

	step take hdd                         //选择hdd这个root bucket为输入
	step chooseleaf firstn -1 type host   //选择总副本数减一个host，并分别递归选择一个叶子节点OSD
	step emit                             //输出结果
}

hash(x, r, i)

struct crush_bucket_uniform {
	struct crush_bucket h;
	__u32 item_weight;               /* 16-bit fixed point; all items equally weighted */
};

struct crush_bucket_list {
	struct crush_bucket h;
	__u32 *item_weights;           /* 16-bit fixed point */
	__u32 *sum_weights;   /* 16-bit fixed point.  element i is sum of weights 0..i, inclusive */
};

struct crush_bucket_tree {
	struct crush_bucket h;     /* note: h.size is _tree_ size, not number of actual items */
	__u8 num_nodes;
	__u32 *node_weights;
};

length = f(Wi) * hash(x, r, i)

struct crush_bucket_straw {
	struct crush_bucket h;
	__u32 *item_weights;   /* 16-bit fixed point */
	__u32 *straws;         /* 16-bit fixed point */
};

hash(x, r, i)

/*
 * CRUSH map includes all buckets, rules, etc.
 */
struct crush_map {
	struct crush_bucket **buckets;
	struct crush_rule **rules;

	__s32 max_buckets;
	__u32 max_rules;
	__s32 max_devices;

	/* choose local retries before re-descent */
	__u32 choose_local_tries;
	/* choose local attempts using a fallback permutation before
	 * re-descent */
	__u32 choose_local_fallback_tries;
	/* choose attempts before giving up */
	__u32 choose_total_tries;
	/* attempt chooseleaf inner descent once for firstn mode; on
	 * reject retry outer descent.  Note that this does *not*
	 * apply to a collision: in that case we will retry as we used
	 * to. */
	__u32 chooseleaf_descend_once;

	/* if non-zero, feed r into chooseleaf, bit-shifted right by (r-1)
	 * bits.  a value of 1 is best for new clusters.  for legacy clusters
	 * that want to limit reshuffling, a value of 3 or 4 will make the
	 * mappings line up a bit better with previous mappings. */
	__u8 chooseleaf_vary_r;

	/* if true, it makes chooseleaf firstn to return stable results (if
	 * no local retry) so that data migrations would be optimal when some
	 * device fails. */
	__u8 chooseleaf_stable;

#ifndef __KERNEL__
	/*
	 * version 0 (original) of straw_calc has various flaws.  version 1
	 * fixes a few of them.
	 */
	__u8 straw_calc_version;

	/*
	 * allowed bucket algs is a bitmask, here the bit positions
	 * are CRUSH_BUCKET_*.  note that these are *bits* and
	 * CRUSH_BUCKET_* values are not, so we need to or together (1
	 * << CRUSH_BUCKET_WHATEVER).  The 0th bit is not used to
	 * minimize confusion (bucket type values start at 1).
	 */
	__u32 allowed_bucket_algs;

	__u32 *choose_tries;
#endif
};

struct crush_bucket {
	__s32 id;            // this'll be negative 
	__u16 type;          // non-zero; type=0 is reserved for devices
	__u8 alg;            // one of CRUSH_BUCKET_* 
	__u8 hash;           // which hash function to use, CRUSH_HASH_* 
	__u32 weight;        // 16-bit fixed point， bucket的权重
	__u32 size;          // num items，即bucket下的item的数量
	
	//子bucket在crush_bucket结构buckets数组的下标，这里特别要注意的是，其子item的crush_bucket结构体都统一保存在crush map
	//结构中的buckets数组中，这里只保存其在数组中的下标
	__s32 *items;        


	/*
	 * 以下是随机排序选择算法的一些Cache的参数：主要用于uniform bucket，而对于其他bucket类型，在进行fallback线性搜索
	 * 时也会用到
	 */
	__u32 perm_x;        //要选择的x
	__u32 perm_n;        //排列的总的元素
	__u32 *perm;         //排列组合的结果
};

struct crush_rule_step {
	__u32 op;                       //step操作步的操作码
	__s32 arg1;                     //如果是take，参数就是选择的bucket的id号；如果是select，就是选择的数量
	__s32 arg2;                     //如果是select，是选择的类型
};


struct crush_rule_mask {
	__u8 ruleset;                  //ruleset的编号
	__u8 type;                     //类型(replicated,...)
	__u8 min_size;                 //最小的size
	__u8 max_size;                 //最大的size
};

struct crush_rule {
	__u32 len;                        //steps数组的长度
	struct crush_rule_mask mask;      //ruleset相关的配置参数
	struct crush_rule_step steps[0];  //操作步
};

int crush_do_rule(const struct crush_map *map,      //crush map结构
		  int ruleno,                               //ruleset的号
		  int x,                                    //输入，一般是PG的id
		  int *result,                              //输出OSD列表
		  int result_max,                           //输出OSD列表的数量
		  const __u32 *weight,                      //所有OSD的权重，通过它来判断OSD是否out
		  int weight_max,                           //所有OSD的数量
		  int *scratch)                             

static int crush_bucket_choose(struct crush_bucket *in, int x, int r)
{
	dprintk(" crush_bucket_choose %d x=%d r=%d\n", in->id, x, r);
	BUG_ON(in->size == 0);
	switch (in->alg) {
	case CRUSH_BUCKET_UNIFORM:
		return bucket_uniform_choose((struct crush_bucket_uniform *)in,
					  x, r);
	case CRUSH_BUCKET_LIST:
		return bucket_list_choose((struct crush_bucket_list *)in,
					  x, r);
	case CRUSH_BUCKET_TREE:
		return bucket_tree_choose((struct crush_bucket_tree *)in,
					  x, r);
	case CRUSH_BUCKET_STRAW:
		return bucket_straw_choose((struct crush_bucket_straw *)in,
					   x, r);
	case CRUSH_BUCKET_STRAW2:
		return bucket_straw2_choose((struct crush_bucket_straw2 *)in,
					    x, r);
	default:
		dprintk("unknown bucket %d alg %d\n", in->id, in->alg);
		return in->items[0];
	}
}

static int bucket_straw_choose(struct crush_bucket_straw *bucket,
			       int x, int r);

draw = crush_hash32_3(bucket->h.hash, x, bucket->h.items[i], r);

draw &= 0xffff;
draw *= bucket->straws[i];