diff options
Diffstat (limited to 'ANDROID_3.4.5/include/linux/crush')
| -rw-r--r-- | ANDROID_3.4.5/include/linux/crush/crush.h | 180 | ||||
| -rw-r--r-- | ANDROID_3.4.5/include/linux/crush/hash.h | 17 | ||||
| -rw-r--r-- | ANDROID_3.4.5/include/linux/crush/mapper.h | 20 |
3 files changed, 0 insertions, 217 deletions
diff --git a/ANDROID_3.4.5/include/linux/crush/crush.h b/ANDROID_3.4.5/include/linux/crush/crush.h deleted file mode 100644 index 97e435b1..00000000 --- a/ANDROID_3.4.5/include/linux/crush/crush.h +++ /dev/null @@ -1,180 +0,0 @@ -#ifndef CEPH_CRUSH_CRUSH_H -#define CEPH_CRUSH_CRUSH_H - -#include <linux/types.h> - -/* - * CRUSH is a pseudo-random data distribution algorithm that - * efficiently distributes input values (typically, data objects) - * across a heterogeneous, structured storage cluster. - * - * The algorithm was originally described in detail in this paper - * (although the algorithm has evolved somewhat since then): - * - * http://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf - * - * LGPL2 - */ - - -#define CRUSH_MAGIC 0x00010000ul /* for detecting algorithm revisions */ - - -#define CRUSH_MAX_DEPTH 10 /* max crush hierarchy depth */ -#define CRUSH_MAX_SET 10 /* max size of a mapping result */ - - -/* - * CRUSH uses user-defined "rules" to describe how inputs should be - * mapped to devices. A rule consists of sequence of steps to perform - * to generate the set of output devices. - */ -struct crush_rule_step { - __u32 op; - __s32 arg1; - __s32 arg2; -}; - -/* step op codes */ -enum { - CRUSH_RULE_NOOP = 0, - CRUSH_RULE_TAKE = 1, /* arg1 = value to start with */ - CRUSH_RULE_CHOOSE_FIRSTN = 2, /* arg1 = num items to pick */ - /* arg2 = type */ - CRUSH_RULE_CHOOSE_INDEP = 3, /* same */ - CRUSH_RULE_EMIT = 4, /* no args */ - CRUSH_RULE_CHOOSE_LEAF_FIRSTN = 6, - CRUSH_RULE_CHOOSE_LEAF_INDEP = 7, -}; - -/* - * for specifying choose num (arg1) relative to the max parameter - * passed to do_rule - */ -#define CRUSH_CHOOSE_N 0 -#define CRUSH_CHOOSE_N_MINUS(x) (-(x)) - -/* - * The rule mask is used to describe what the rule is intended for. - * Given a ruleset and size of output set, we search through the - * rule list for a matching rule_mask. - */ -struct crush_rule_mask { - __u8 ruleset; - __u8 type; - __u8 min_size; - __u8 max_size; -}; - -struct crush_rule { - __u32 len; - struct crush_rule_mask mask; - struct crush_rule_step steps[0]; -}; - -#define crush_rule_size(len) (sizeof(struct crush_rule) + \ - (len)*sizeof(struct crush_rule_step)) - - - -/* - * A bucket is a named container of other items (either devices or - * other buckets). Items within a bucket are chosen using one of a - * few different algorithms. The table summarizes how the speed of - * each option measures up against mapping stability when items are - * added or removed. - * - * Bucket Alg Speed Additions Removals - * ------------------------------------------------ - * uniform O(1) poor poor - * list O(n) optimal poor - * tree O(log n) good good - * straw O(n) optimal optimal - */ -enum { - CRUSH_BUCKET_UNIFORM = 1, - CRUSH_BUCKET_LIST = 2, - CRUSH_BUCKET_TREE = 3, - CRUSH_BUCKET_STRAW = 4 -}; -extern const char *crush_bucket_alg_name(int alg); - -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 */ - __u32 size; /* num items */ - __s32 *items; - - /* - * cached random permutation: used for uniform bucket and for - * the linear search fallback for the other bucket types. - */ - __u32 perm_x; /* @x for which *perm is defined */ - __u32 perm_n; /* num elements of *perm that are permuted/defined */ - __u32 *perm; -}; - -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; -}; - -struct crush_bucket_straw { - struct crush_bucket h; - __u32 *item_weights; /* 16-bit fixed point */ - __u32 *straws; /* 16-bit fixed point */ -}; - - - -/* - * CRUSH map includes all buckets, rules, etc. - */ -struct crush_map { - struct crush_bucket **buckets; - struct crush_rule **rules; - - /* - * Parent pointers to identify the parent bucket a device or - * bucket in the hierarchy. If an item appears more than - * once, this is the _last_ time it appeared (where buckets - * are processed in bucket id order, from -1 on down to - * -max_buckets. - */ - __u32 *bucket_parents; - __u32 *device_parents; - - __s32 max_buckets; - __u32 max_rules; - __s32 max_devices; -}; - - -/* crush.c */ -extern int crush_get_bucket_item_weight(struct crush_bucket *b, int pos); -extern void crush_calc_parents(struct crush_map *map); -extern void crush_destroy_bucket_uniform(struct crush_bucket_uniform *b); -extern void crush_destroy_bucket_list(struct crush_bucket_list *b); -extern void crush_destroy_bucket_tree(struct crush_bucket_tree *b); -extern void crush_destroy_bucket_straw(struct crush_bucket_straw *b); -extern void crush_destroy_bucket(struct crush_bucket *b); -extern void crush_destroy(struct crush_map *map); - -#endif diff --git a/ANDROID_3.4.5/include/linux/crush/hash.h b/ANDROID_3.4.5/include/linux/crush/hash.h deleted file mode 100644 index 91e88423..00000000 --- a/ANDROID_3.4.5/include/linux/crush/hash.h +++ /dev/null @@ -1,17 +0,0 @@ -#ifndef CEPH_CRUSH_HASH_H -#define CEPH_CRUSH_HASH_H - -#define CRUSH_HASH_RJENKINS1 0 - -#define CRUSH_HASH_DEFAULT CRUSH_HASH_RJENKINS1 - -extern const char *crush_hash_name(int type); - -extern __u32 crush_hash32(int type, __u32 a); -extern __u32 crush_hash32_2(int type, __u32 a, __u32 b); -extern __u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c); -extern __u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d); -extern __u32 crush_hash32_5(int type, __u32 a, __u32 b, __u32 c, __u32 d, - __u32 e); - -#endif diff --git a/ANDROID_3.4.5/include/linux/crush/mapper.h b/ANDROID_3.4.5/include/linux/crush/mapper.h deleted file mode 100644 index c46b99c1..00000000 --- a/ANDROID_3.4.5/include/linux/crush/mapper.h +++ /dev/null @@ -1,20 +0,0 @@ -#ifndef CEPH_CRUSH_MAPPER_H -#define CEPH_CRUSH_MAPPER_H - -/* - * CRUSH functions for find rules and then mapping an input to an - * output set. - * - * LGPL2 - */ - -#include "crush.h" - -extern int crush_find_rule(struct crush_map *map, int pool, int type, int size); -extern int crush_do_rule(struct crush_map *map, - int ruleno, - int x, int *result, int result_max, - int forcefeed, /* -1 for none */ - __u32 *weights); - -#endif |