Merge remote-tracking branch 'gh/wip-2101'

6 files changed, 173 insertions, 71 deletions

diff --git a/src/crush/CrushCompiler.cc b/src/crush/CrushCompiler.cc
index ec3ab2a1427..5a0cdbd0848 100644
--- a/src/crush/CrushCompiler.cc
+++ b/src/crush/CrushCompiler.cc
@@ -12,6 +12,7 @@
 #include <stdexcept>
 #include <map>
 
+
 #include <typeinfo>
 
 // -------------
@@ -439,9 +440,9 @@ int CrushCompiler::parse_bucket(iter_t const& i)
   vector<int> weights(size);
 
   int curpos = 0;
-  float bucketweight = 0;
+  unsigned bucketweight = 0;
   bool have_uniform_weight = false;
-  float uniform_weight = 0;
+  unsigned uniform_weight = 0;
   for (unsigned p=3; p<i->children.size()-1; p++) {
     iter_t sub = i->children.begin() + p;
     string tag = string_node(sub->children[0]);
@@ -454,19 +455,30 @@ int CrushCompiler::parse_bucket(iter_t const& i)
       }
       int itemid = item_id[iname];
 
-      float weight = 1.0;
+      unsigned weight = 0x10000;
       if (item_weight.count(itemid))
 	weight = item_weight[itemid];
 
       int pos = -1;
       for (unsigned q = 2; q < sub->children.size(); q++) {
 	string tag = string_node(sub->children[q++]);
-	if (tag == "weight")
-	  weight = float_node(sub->children[q]);
+	if (tag == "weight") {
+	  weight = float_node(sub->children[q]) * (float)0x10000;
+	  if (weight > CRUSH_MAX_DEVICE_WEIGHT && itemid >= 0) {
+	    err << "device weight limited to " << CRUSH_MAX_DEVICE_WEIGHT / 0x10000 << std::endl;
+	    return -ERANGE;
+	  }
+	  else if (weight > CRUSH_MAX_BUCKET_WEIGHT && itemid < 0) {
+	    err << "bucket weight limited to " << CRUSH_MAX_BUCKET_WEIGHT / 0x10000
+	        << " to prevent overflow" << std::endl;
+	    return -ERANGE;
+	  }
+	}
 	else if (tag == "pos") 
 	  pos = int_node(sub->children[q]);
 	else
 	  assert(0);
+
       }
       if (alg == CRUSH_BUCKET_UNIFORM) {
 	if (!have_uniform_weight) {
@@ -475,7 +487,7 @@ int CrushCompiler::parse_bucket(iter_t const& i)
 	} else {
 	  if (uniform_weight != weight) {
 	    err << "item '" << iname << "' in uniform bucket '" << name << "' has weight " << weight
-		<< " but previous item(s) have weight " << uniform_weight
+		<< " but previous item(s) have weight " << (float)uniform_weight/(float)0x10000
 		<< "; uniform bucket items must all have identical weights." << std::endl;
 	    return -1;
 	  }
@@ -492,7 +504,13 @@ int CrushCompiler::parse_bucket(iter_t const& i)
       }
       //err << " item " << iname << " (" << itemid << ") pos " << pos << " weight " << weight << std::endl;
       items[pos] = itemid;
-      weights[pos] = (unsigned)(weight * 0x10000);
+      weights[pos] = weight;
+
+      if (crush_addition_is_unsafe(bucketweight, weight)) {
+        err << "oh no! our bucket weights are overflowing all over the place, better lower the item weights" << std::endl;
+        return -ERANGE;
+      }
+
       bucketweight += weight;
     }
   }
@@ -502,7 +520,8 @@ int CrushCompiler::parse_bucket(iter_t const& i)
     //err << "assigned id " << id << std::endl;
   }
 
-  if (verbose) err << "bucket " << name << " (" << id << ") " << size << " items and weight " << bucketweight << std::endl;
+  if (verbose) err << "bucket " << name << " (" << id << ") " << size << " items and weight "
+		   << (float)bucketweight / (float)0x10000 << std::endl;
   id_item[id] = name;
   item_id[name] = id;
   item_weight[id] = bucketweight;
diff --git a/src/crush/CrushCompiler.h b/src/crush/CrushCompiler.h
index 9d07d76afa9..d488735bb9e 100644
--- a/src/crush/CrushCompiler.h
+++ b/src/crush/CrushCompiler.h
@@ -36,7 +36,7 @@ class CrushCompiler {
 
   map<string, int> item_id;
   map<int, string> id_item;
-  map<int, float> item_weight;
+  map<int, unsigned> item_weight;
   map<string, int> type_id;
   map<string, int> rule_id;
 
diff --git a/src/crush/builder.c b/src/crush/builder.c
index 0f22b297692..64ad0051a6f 100644
--- a/src/crush/builder.c
+++ b/src/crush/builder.c
@@ -1,4 +1,3 @@
-
 #include <string.h>
 #include <limits.h>
 #include <math.h>
@@ -17,7 +16,7 @@ struct crush_map *crush_create()
 	struct crush_map *m;
 	m = malloc(sizeof(*m));
         if (!m)
-          return NULL;
+                return NULL;
 	memset(m, 0, sizeof(*m));
 
 	/* initialize legacy tunable values */
@@ -84,7 +83,7 @@ struct crush_rule *crush_make_rule(int len, int ruleset, int type, int minsize,
 	struct crush_rule *rule;
 	rule = malloc(crush_rule_size(len));
         if (!rule)
-          return NULL;
+                return NULL;
 	rule->len = len;
 	rule->mask.ruleset = ruleset;
 	rule->mask.type = type;
@@ -141,7 +140,7 @@ int crush_add_bucket(struct crush_map *map,
 
 	assert(map->buckets[pos] == 0);
 
-   	/* add it */
+        /* add it */
 	bucket->id = id;
 	map->buckets[pos] = bucket;
 
@@ -170,22 +169,27 @@ crush_make_uniform_bucket(int hash, int type, int size,
 
 	bucket = malloc(sizeof(*bucket));
         if (!bucket)
-          return NULL;
+                return NULL;
 	memset(bucket, 0, sizeof(*bucket));
 	bucket->h.alg = CRUSH_BUCKET_UNIFORM;
 	bucket->h.hash = hash;
 	bucket->h.type = type;
 	bucket->h.size = size;
-	bucket->h.weight = size * item_weight;
 
-	bucket->item_weight = item_weight;
+	if (crush_multiplication_is_unsafe(size, item_weight))
+                goto err;
 
+	bucket->h.weight = size * item_weight;
+	bucket->item_weight = item_weight;
 	bucket->h.items = malloc(sizeof(__u32)*size);
+
         if (!bucket->h.items)
-          goto err;
-	bucket->h.perm = malloc(sizeof(__u32)*size);
+                goto err;
+
+        bucket->h.perm = malloc(sizeof(__u32)*size);
+
         if (!bucket->h.perm)
-          goto err;
+                goto err;
 	for (i=0; i<size; i++)
 		bucket->h.items[i] = items[i];
 
@@ -211,7 +215,7 @@ crush_make_list_bucket(int hash, int type, int size,
 
 	bucket = malloc(sizeof(*bucket));
         if (!bucket)
-          return NULL;
+                return NULL;
 	memset(bucket, 0, sizeof(*bucket));
 	bucket->h.alg = CRUSH_BUCKET_LIST;
 	bucket->h.hash = hash;
@@ -220,20 +224,26 @@ crush_make_list_bucket(int hash, int type, int size,
 
 	bucket->h.items = malloc(sizeof(__u32)*size);
         if (!bucket->h.items)
-          goto err;
+                goto err;
 	bucket->h.perm = malloc(sizeof(__u32)*size);
         if (!bucket->h.perm)
-          goto err;
-	bucket->item_weights = malloc(sizeof(__u32)*size);
+                goto err;
+
+
+        bucket->item_weights = malloc(sizeof(__u32)*size);
         if (!bucket->item_weights)
-          goto err;
+                goto err;
 	bucket->sum_weights = malloc(sizeof(__u32)*size);
         if (!bucket->sum_weights)
-          goto err;
+                goto err;
 	w = 0;
 	for (i=0; i<size; i++) {
 		bucket->h.items[i] = items[i];
 		bucket->item_weights[i] = weights[i];
+
+		if (crush_addition_is_unsafe(w, weights[i]))
+                        goto err;
+
 		w += weights[i];
 		bucket->sum_weights[i] = w;
 		/*printf("pos %d item %d weight %d sum %d\n",
@@ -298,7 +308,7 @@ crush_make_tree_bucket(int hash, int type, int size,
 
 	bucket = malloc(sizeof(*bucket));
         if (!bucket)
-          return NULL;
+                return NULL;
 	memset(bucket, 0, sizeof(*bucket));
 	bucket->h.alg = CRUSH_BUCKET_TREE;
 	bucket->h.hash = hash;
@@ -307,18 +317,19 @@ crush_make_tree_bucket(int hash, int type, int size,
 
 	bucket->h.items = malloc(sizeof(__u32)*size);
         if (!bucket->h.items)
-          goto err;
+                goto err;
 	bucket->h.perm = malloc(sizeof(__u32)*size);
         if (!bucket->h.perm)
-          goto err;
+                goto err;
 
 	/* calc tree depth */
 	depth = calc_depth(size);
 	bucket->num_nodes = 1 << depth;
 	printf("size %d depth %d nodes %d\n", size, depth, bucket->num_nodes);
-	bucket->node_weights = malloc(sizeof(__u32)*bucket->num_nodes);
+
+        bucket->node_weights = malloc(sizeof(__u32)*bucket->num_nodes);
         if (!bucket->node_weights)
-          goto err;
+                goto err;
 
 	memset(bucket->h.items, 0, sizeof(__u32)*bucket->h.size);
 	memset(bucket->node_weights, 0, sizeof(__u32)*bucket->num_nodes);
@@ -328,9 +339,17 @@ crush_make_tree_bucket(int hash, int type, int size,
 		node = crush_calc_tree_node(i);
 		printf("item %d node %d weight %d\n", i, node, weights[i]);
 		bucket->node_weights[node] = weights[i];
+
+		if (crush_addition_is_unsafe(bucket->h.weight, weights[i]))
+                        goto err;
+
 		bucket->h.weight += weights[i];
 		for (j=1; j<depth; j++) {
 			node = parent(node);
+
+                        if (crush_addition_is_unsafe(bucket->node_weights[node], weights[i]))
+                                goto err;
+
 			bucket->node_weights[node] += weights[i];
 			printf(" node %d weight %d\n", node, bucket->node_weights[node]);
 		}
@@ -362,7 +381,7 @@ int crush_calc_straw(struct crush_bucket_straw *bucket)
 	/* reverse sort by weight (simple insertion sort) */
 	reverse = malloc(sizeof(int) * size);
         if (!reverse)
-          return -ENOMEM;
+                return -ENOMEM;
 	if (size)
 		reverse[0] = 0;
 	for (i=1; i<size; i++) {
@@ -439,35 +458,35 @@ crush_make_straw_bucket(int hash,
 
 	bucket = malloc(sizeof(*bucket));
         if (!bucket)
-          return NULL;
+                return NULL;
 	memset(bucket, 0, sizeof(*bucket));
 	bucket->h.alg = CRUSH_BUCKET_STRAW;
 	bucket->h.hash = hash;
 	bucket->h.type = type;
 	bucket->h.size = size;
 
-	bucket->h.items = malloc(sizeof(__u32)*size);
+        bucket->h.items = malloc(sizeof(__u32)*size);
         if (!bucket->h.items)
-          goto err;
+                goto err;
 	bucket->h.perm = malloc(sizeof(__u32)*size);
         if (!bucket->h.perm)
-          goto err;
+                goto err;
 	bucket->item_weights = malloc(sizeof(__u32)*size);
         if (!bucket->item_weights)
-          goto err;
-	bucket->straws = malloc(sizeof(__u32)*size);
+                goto err;
+        bucket->straws = malloc(sizeof(__u32)*size);
         if (!bucket->straws)
-          goto err;
+                goto err;
 
-	bucket->h.weight = 0;
+        bucket->h.weight = 0;
 	for (i=0; i<size; i++) {
 		bucket->h.items[i] = items[i];
 		bucket->h.weight += weights[i];
 		bucket->item_weights[i] = weights[i];
 	}
 
-	if (crush_calc_straw(bucket) < 0)
-          goto err;
+        if (crush_calc_straw(bucket) < 0)
+                goto err;
 
 	return bucket;
 err:
@@ -513,21 +532,25 @@ crush_make_bucket(int alg, int hash, int type, int size,
 
 int crush_add_uniform_bucket_item(struct crush_bucket_uniform *bucket, int item, int weight)
 {
-	int newsize = bucket->h.size + 1;
+        int newsize = bucket->h.size + 1;
 
 	bucket->h.items = realloc(bucket->h.items, sizeof(__u32)*newsize);
 	bucket->h.perm = realloc(bucket->h.perm, sizeof(__u32)*newsize);
 
 	bucket->h.items[newsize-1] = item;
-	bucket->h.weight += weight;
-	bucket->h.size++;
 
-	return 0;
+        if (crush_addition_is_unsafe(bucket->h.weight, weight))
+                return -ERANGE;
+
+        bucket->h.weight += weight;
+        bucket->h.size++;
+
+        return 0;
 }
 
 int crush_add_list_bucket_item(struct crush_bucket_list *bucket, int item, int weight)
 {
-	int newsize = bucket->h.size + 1;
+        int newsize = bucket->h.size + 1;
 
 	bucket->h.items = realloc(bucket->h.items, sizeof(__u32)*newsize);
 	bucket->h.perm = realloc(bucket->h.perm, sizeof(__u32)*newsize);
@@ -536,10 +559,17 @@ int crush_add_list_bucket_item(struct crush_bucket_list *bucket, int item, int w
 
 	bucket->h.items[newsize-1] = item;
 	bucket->item_weights[newsize-1] = weight;
-	if (newsize > 1)
-		bucket->sum_weights[newsize-1] = bucket->sum_weights[newsize-2] + weight;
-	else
-		bucket->sum_weights[newsize-1] = weight;
+	if (newsize > 1) {
+
+                if (crush_addition_is_unsafe(bucket->sum_weights[newsize-2], weight))
+                        return -ERANGE;
+
+                bucket->sum_weights[newsize-1] = bucket->sum_weights[newsize-2] + weight;
+	}
+
+        else {
+                bucket->sum_weights[newsize-1] = weight;
+        }
 
 	bucket->h.weight += weight;
 	bucket->h.size++;
@@ -563,12 +593,21 @@ int crush_add_tree_bucket_item(struct crush_bucket_tree *bucket, int item, int w
 
 	for (j=1; j<depth; j++) {
 		node = parent(node);
+
+                if (!crush_addition_is_unsafe(bucket->node_weights[node], weight))
+                        return -ERANGE;
+
 		bucket->node_weights[node] += weight;
-		printf(" node %d weight %d\n", node, bucket->node_weights[node]);
+                printf(" node %d weight %d\n", node, bucket->node_weights[node]);
 	}
+
+
+	if (crush_addition_is_unsafe(bucket->h.weight, weight))
+                return -ERANGE;
 	
-	bucket->h.weight += weight;
-	bucket->h.size++;
+        bucket->h.weight += weight;
+        bucket->h.size++;
+
 	return 0;
 }
 
@@ -584,8 +623,11 @@ int crush_add_straw_bucket_item(struct crush_bucket_straw *bucket, int item, int
 	bucket->h.items[newsize-1] = item;
 	bucket->item_weights[newsize-1] = weight;
 
-	bucket->h.weight += weight;
-	bucket->h.size++;
+	if (crush_addition_is_unsafe(bucket->h.weight, weight))
+                return -ERANGE;
+
+	 bucket->h.weight += weight;
+	 bucket->h.size++;
 	
 	return crush_calc_straw(bucket);
 }
@@ -844,7 +886,7 @@ int crush_adjust_straw_bucket_item_weight(struct crush_bucket_straw *bucket, int
 
 	r = crush_calc_straw(bucket);
         if (r < 0)
-          return r;
+                return r;
 
 	return diff;
 }
@@ -872,7 +914,7 @@ int crush_bucket_adjust_item_weight(struct crush_bucket *b, int item, int weight
 
 /************************************************/
 
-static void crush_reweight_uniform_bucket(struct crush_map *crush, struct crush_bucket_uniform *bucket)
+static int crush_reweight_uniform_bucket(struct crush_map *crush, struct crush_bucket_uniform *bucket)
 {
 	unsigned i;
 	unsigned sum = 0, n = 0, leaves = 0;
@@ -882,6 +924,10 @@ static void crush_reweight_uniform_bucket(struct crush_map *crush, struct crush_
 		if (id < 0) {
 			struct crush_bucket *c = crush->buckets[-1-id];
 			crush_reweight_bucket(crush, c);
+
+			if (crush_addition_is_unsafe(sum, c->weight))
+                                return -ERANGE;
+
 			sum += c->weight;
 			n++;
 		} else {
@@ -892,9 +938,11 @@ static void crush_reweight_uniform_bucket(struct crush_map *crush, struct crush_
 	if (n > leaves)
 		bucket->item_weight = sum / n;  // more bucket children than leaves, average!
 	bucket->h.weight = bucket->item_weight * bucket->h.size;
+
+	return 0;
 }
 
-static void crush_reweight_list_bucket(struct crush_map *crush, struct crush_bucket_list *bucket)
+static int crush_reweight_list_bucket(struct crush_map *crush, struct crush_bucket_list *bucket)
 {
 	unsigned i;
 
@@ -906,11 +954,17 @@ static void crush_reweight_list_bucket(struct crush_map *crush, struct crush_buc
 			crush_reweight_bucket(crush, c);
 			bucket->item_weights[i] = c->weight;
 		}
+
+		if (crush_addition_is_unsafe(bucket->h.weight, bucket->item_weights[i]))
+                        return -ERANGE;
+
 		bucket->h.weight += bucket->item_weights[i];
 	}
+
+	return 0;
 }
 
-static void crush_reweight_tree_bucket(struct crush_map *crush, struct crush_bucket_tree *bucket)
+static int crush_reweight_tree_bucket(struct crush_map *crush, struct crush_bucket_tree *bucket)
 {
 	unsigned i;
 
@@ -923,11 +977,19 @@ static void crush_reweight_tree_bucket(struct crush_map *crush, struct crush_buc
 			crush_reweight_bucket(crush, c);
 			bucket->node_weights[node] = c->weight;
 		}
+
+		if (crush_addition_is_unsafe(bucket->h.weight, bucket->node_weights[node]))
+                        return -ERANGE;
+
 		bucket->h.weight += bucket->node_weights[node];
+
+
 	}
+
+	return 0;
 }
 
-static void crush_reweight_straw_bucket(struct crush_map *crush, struct crush_bucket_straw *bucket)
+static int crush_reweight_straw_bucket(struct crush_map *crush, struct crush_bucket_straw *bucket)
 {
 	unsigned i;
 
@@ -939,25 +1001,27 @@ static void crush_reweight_straw_bucket(struct crush_map *crush, struct crush_bu
 			crush_reweight_bucket(crush, c);
 			bucket->item_weights[i] = c->weight;
 		}
-		bucket->h.weight += bucket->item_weights[i];
+
+                if (crush_addition_is_unsafe(bucket->h.weight, bucket->item_weights[i]))
+                        return -ERANGE;
+
+                bucket->h.weight += bucket->item_weights[i];
 	}
+
+	return 0;
 }
 
 int crush_reweight_bucket(struct crush_map *crush, struct crush_bucket *b)
 {
 	switch (b->alg) {
 	case CRUSH_BUCKET_UNIFORM:
-		crush_reweight_uniform_bucket(crush, (struct crush_bucket_uniform *)b);
-		break;
+		return crush_reweight_uniform_bucket(crush, (struct crush_bucket_uniform *)b);
 	case CRUSH_BUCKET_LIST:
-		crush_reweight_list_bucket(crush, (struct crush_bucket_list *)b);
-		break;
+		return crush_reweight_list_bucket(crush, (struct crush_bucket_list *)b);
 	case CRUSH_BUCKET_TREE:
-		crush_reweight_tree_bucket(crush, (struct crush_bucket_tree *)b);
-		break;
+		return crush_reweight_tree_bucket(crush, (struct crush_bucket_tree *)b);
 	case CRUSH_BUCKET_STRAW:
-		crush_reweight_straw_bucket(crush, (struct crush_bucket_straw *)b);
-		break;
+		return crush_reweight_straw_bucket(crush, (struct crush_bucket_straw *)b);
 	default:
 		return -1;
 	}
diff --git a/src/crush/crush.c b/src/crush/crush.c
index 7f800b3404b..19a765228e9 100644
--- a/src/crush/crush.c
+++ b/src/crush/crush.c
@@ -124,4 +124,19 @@ void crush_destroy(struct crush_map *map)
 	kfree(map);
 }
 
+// methods to check for safe arithmetic operations
+int crush_addition_is_unsafe(__u32 a, __u32 b)
+{
+  if ((((__u32)(-1)) - b) < a)
+    return 1;
+  else
+    return 0;
+}
 
+int crush_multiplication_is_unsafe(__u32  a, __u32 b)
+{
+  if ((((__u32)(-1)) / b) < a)
+    return 1;
+  else
+    return 0;
+}
diff --git a/src/crush/crush.h b/src/crush/crush.h
index 084c4a97869..de22386ed70 100644
--- a/src/crush/crush.h
+++ b/src/crush/crush.h
@@ -28,6 +28,8 @@
 #define CRUSH_MAX_DEPTH 10  /* max crush hierarchy depth */
 #define CRUSH_MAX_SET   10  /* max size of a mapping result */
 
+#define CRUSH_MAX_DEVICE_WEIGHT (100u * 0x10000u)
+#define CRUSH_MAX_BUCKET_WEIGHT (65535u * 0x10000u)
 
 /*
  * CRUSH uses user-defined "rules" to describe how inputs should be
@@ -174,6 +176,8 @@ struct crush_map {
 
 /* crush.c */
 extern int crush_get_bucket_item_weight(const struct crush_bucket *b, int pos);
+extern int crush_addition_is_unsafe(__u32 a, __u32 b);
+extern int crush_multiplication_is_unsafe(__u32  a, __u32 b);
 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);
diff --git a/src/crushtool.cc b/src/crushtool.cc
index dd1484d6c2f..d628f6e1e96 100644
--- a/src/crushtool.cc
+++ b/src/crushtool.cc
@@ -370,7 +370,7 @@ int main(int argc, const char **argv)
   }
 
   if (decompile) {
-    CrushCompiler cc(crush, cerr);
+    CrushCompiler cc(crush, cerr, (int)verbose);
     if (!outfn.empty()) {
       ofstream o;
       o.open(outfn.c_str(), ios::out | ios::binary | ios::trunc);
@@ -395,7 +395,7 @@ int main(int argc, const char **argv)
       return -ENOENT;
     }
 
-    CrushCompiler cc(crush, cerr);
+    CrushCompiler cc(crush, cerr, (int)verbose);
     if (unsafe_tunables)
       cc.enable_unsafe_tunables();
     int r = cc.compile(in, srcfn.c_str());