From patchwork Mon Dec 23 17:09:38 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Dryomov X-Patchwork-Id: 3397451 Return-Path: X-Original-To: patchwork-ceph-devel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork2.web.kernel.org (Postfix) with ESMTP id A985EC0D4A for ; Mon, 23 Dec 2013 17:11:09 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 7D6C320568 for ; Mon, 23 Dec 2013 17:11:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 30BC6205F1 for ; Mon, 23 Dec 2013 17:11:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757620Ab3LWRKz (ORCPT ); Mon, 23 Dec 2013 12:10:55 -0500 Received: from mail-ea0-f180.google.com ([209.85.215.180]:39397 "EHLO mail-ea0-f180.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752635Ab3LWRKy (ORCPT ); Mon, 23 Dec 2013 12:10:54 -0500 Received: by mail-ea0-f180.google.com with SMTP id f15so2475232eak.11 for ; Mon, 23 Dec 2013 09:10:53 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=9HpavqO264glX41nfgDHDlmNpkjzRlHv9XhrPEYttNM=; b=WXufBItiO5lhexI26P5gl0tMvvpmjfcTtSTxSvDWtl3nTfUQGZ/OTetXPqaWJQOERL aWk8VYDGc78SX3Pi5tnUy9vFSWRTmybd6cCaQDkWAlcvv7PuN2u79ATkdKEKPn0H+G/+ j0jXLLwOEJvde3u7bMDy3cE9DC/0MqyuVjPbSNuBPhP63dIDhXmm9LA4PR/iExhJNIGt V+wlwU3PJZ8BDtlp9UXwxftRDtglhNIxhNir5kN2e28EhWz/w7iJYEfxI5K5Y4eM7RYM KmEm4p5X3dk5iNOiIV0IMrLwBJiszltz8ni1YdihOQd7NThvGZT4fhhoTjQ6iWSwlzXv 9O9Q== X-Gm-Message-State: ALoCoQlFMJJmKuMI82oa+WsmVVPo2SRYa/aoBjCXyaTsmwNiFpHzytl4xV7P+NOPPF8MfuI0D9eh X-Received: by 10.15.82.136 with SMTP id a8mr1426896eez.81.1387818653659; Mon, 23 Dec 2013 09:10:53 -0800 (PST) Received: from localhost ([109.110.66.29]) by mx.google.com with ESMTPSA id o1sm47317722eea.10.2013.12.23.09.10.52 for (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Mon, 23 Dec 2013 09:10:53 -0800 (PST) From: Ilya Dryomov To: ceph-devel@vger.kernel.org Cc: Sage Weil , ilya.dryomov@inktank.com Subject: [PATCH 07/19] crush: use breadth-first search for indep mode Date: Mon, 23 Dec 2013 19:09:38 +0200 Message-Id: <1387818590-30483-8-git-send-email-ilya.dryomov@inktank.com> X-Mailer: git-send-email 1.7.10.4 In-Reply-To: <1387818590-30483-1-git-send-email-ilya.dryomov@inktank.com> References: <1387818590-30483-1-git-send-email-ilya.dryomov@inktank.com> Sender: ceph-devel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: ceph-devel@vger.kernel.org X-Spam-Status: No, score=-7.4 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Reflects ceph.git commit 86e978036a4ecbac4c875e7c00f6c5bbe37282d3. Signed-off-by: Ilya Dryomov --- include/linux/crush/crush.h | 3 +- net/ceph/crush/mapper.c | 172 ++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 165 insertions(+), 10 deletions(-) diff --git a/include/linux/crush/crush.h b/include/linux/crush/crush.h index 3d6a12928560..4023b1b52296 100644 --- a/include/linux/crush/crush.h +++ b/include/linux/crush/crush.h @@ -22,7 +22,8 @@ #define CRUSH_MAX_DEPTH 10 /* max crush hierarchy depth */ -#define CRUSH_ITEM_UNDEF 0x7fffffff /* undefined result */ +#define CRUSH_ITEM_UNDEF 0x7ffffffe /* undefined result (internal use only) */ +#define CRUSH_ITEM_NONE 0x7fffffff /* no result */ /* * CRUSH uses user-defined "rules" to describe how inputs should be diff --git a/net/ceph/crush/mapper.c b/net/ceph/crush/mapper.c index a8605245d190..caeb1066bea3 100644 --- a/net/ceph/crush/mapper.c +++ b/net/ceph/crush/mapper.c @@ -474,6 +474,148 @@ reject: /** + * choose indep: alternative breadth-first positionally stable mapping + * + */ +static void crush_choose_indep(const struct crush_map *map, + struct crush_bucket *bucket, + const __u32 *weight, int weight_max, + int x, int numrep, int type, + int *out, int outpos, + int recurse_to_leaf, + int *out2) +{ + struct crush_bucket *in = bucket; + int left = numrep - outpos; + int rep; + unsigned int ftotal; + int r; + int i; + int item = 0; + int itemtype; + int collide; + + dprintk("CHOOSE%s INDEP bucket %d x %d outpos %d numrep %d\n", recurse_to_leaf ? "_LEAF" : "", + bucket->id, x, outpos, numrep); + + /* initially my result is undefined */ + for (rep = outpos; rep < numrep; rep++) { + out[rep] = CRUSH_ITEM_UNDEF; + if (out2) + out2[rep] = CRUSH_ITEM_UNDEF; + } + + for (ftotal = 0; left > 0 && ftotal < map->choose_total_tries; ftotal++) { + for (rep = outpos; rep < numrep; rep++) { + if (out[rep] != CRUSH_ITEM_UNDEF) + continue; + + in = bucket; /* initial bucket */ + + /* choose through intervening buckets */ + for (;;) { + r = rep; + + /* be careful */ + if (in->alg == CRUSH_BUCKET_UNIFORM && + in->size % numrep == 0) + /* r'=r+(n+1)*f_total */ + r += (numrep+1) * ftotal; + else + /* r' = r + n*f_total */ + r += numrep * ftotal; + + /* bucket choose */ + if (in->size == 0) { + dprintk(" empty bucket\n"); + break; + } + + item = crush_bucket_choose(in, x, r); + if (item >= map->max_devices) { + dprintk(" bad item %d\n", item); + out[rep] = CRUSH_ITEM_NONE; + if (out2) + out2[rep] = CRUSH_ITEM_NONE; + left--; + break; + } + + /* desired type? */ + if (item < 0) + itemtype = map->buckets[-1-item]->type; + else + itemtype = 0; + dprintk(" item %d type %d\n", item, itemtype); + + /* keep going? */ + if (itemtype != type) { + if (item >= 0 || + (-1-item) >= map->max_buckets) { + dprintk(" bad item type %d\n", type); + out[rep] = CRUSH_ITEM_NONE; + if (out2) + out2[rep] = + CRUSH_ITEM_NONE; + left--; + break; + } + in = map->buckets[-1-item]; + continue; + } + + /* collision? */ + collide = 0; + for (i = outpos; i < numrep; i++) { + if (out[i] == item) { + collide = 1; + break; + } + } + if (collide) + break; + + if (recurse_to_leaf) { + if (item < 0) { + crush_choose_indep(map, + map->buckets[-1-item], + weight, weight_max, + x, rep+1, 0, + out2, rep, + 0, NULL); + if (out2[rep] == CRUSH_ITEM_NONE) { + /* placed nothing; no leaf */ + break; + } + } else { + /* we already have a leaf! */ + out2[rep] = item; + } + } + + /* out? */ + if (itemtype == 0 && + is_out(map, weight, weight_max, item, x)) + break; + + /* yay! */ + out[rep] = item; + left--; + break; + } + } + } + for (rep = outpos; rep < numrep; rep++) { + if (out[rep] == CRUSH_ITEM_UNDEF) { + out[rep] = CRUSH_ITEM_NONE; + } + if (out2 && out2[rep] == CRUSH_ITEM_UNDEF) { + out2[rep] = CRUSH_ITEM_NONE; + } + } +} + +/** * crush_do_rule - calculate a mapping with the given input and rule * @map: the crush_map * @ruleno: the rule id @@ -556,15 +698,27 @@ int crush_do_rule(const struct crush_map *map, continue; } j = 0; - osize += crush_choose(map, - map->buckets[-1-w[i]], - weight, weight_max, - x, numrep, - curstep->arg2, - o+osize, j, - firstn, - recurse_to_leaf, - descend_once, c+osize); + if (firstn) { + osize += crush_choose(map, + map->buckets[-1-w[i]], + weight, weight_max, + x, numrep, + curstep->arg2, + o+osize, j, + firstn, + recurse_to_leaf, + descend_once, c+osize); + } else { + crush_choose_indep(map, + map->buckets[-1-w[i]], + weight, weight_max, + x, numrep, + curstep->arg2, + o+osize, j, + recurse_to_leaf, + c+osize); + osize += numrep; + } } if (recurse_to_leaf)