From patchwork Wed May 1 21:32:52 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alex Elder X-Patchwork-Id: 2508911 Return-Path: X-Original-To: patchwork-ceph-devel@patchwork.kernel.org Delivered-To: patchwork-process-083081@patchwork2.kernel.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by patchwork2.kernel.org (Postfix) with ESMTP id 88FB4DF230 for ; Wed, 1 May 2013 21:32:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758011Ab3EAVc5 (ORCPT ); Wed, 1 May 2013 17:32:57 -0400 Received: from mail-ia0-f170.google.com ([209.85.210.170]:58898 "EHLO mail-ia0-f170.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1761635Ab3EAVcz (ORCPT ); Wed, 1 May 2013 17:32:55 -0400 Received: by mail-ia0-f170.google.com with SMTP id k20so1735061iak.1 for ; Wed, 01 May 2013 14:32:55 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-received:message-id:date:from:user-agent:mime-version:to:subject :references:in-reply-to:content-type:content-transfer-encoding :x-gm-message-state; bh=A2lghK7E6Lp6924wV7i6hCo5TrWYgQDYw85WxRkxUp0=; b=iGHKeVLWru9E1A+ZXJc1aOqr0snITL6B/fwRBOIMhue5FGSQXA1gN9Rta1P5RBjmGm GosBCJCIYZ08Pbo4E7snMT3mVEsqNFm2Uq8wUeAeUywMPY4cu1VfqxG52Q0Mfa3LV/AR Q488hFBQfGXqgAGAEyVEDlFvQAmHHMWBWQs5X0l7Cyo/+Gki2FSW6F/Lc0HfWyP816i0 LqR7njIwpOSZr+U82DCxVJnQfTKghhoQIs6seY4tSOZSNpJ6VSGFlFw3wsQyBj0jlVJR ahhJPKfeVCAoH7a1lSZteNCdbySDBTp06ctb80/CqRCTk7mVEv4Eexlah4MZSOPRZKLa Y28w== X-Received: by 10.43.12.66 with SMTP id ph2mr2291182icb.5.1367443974953; Wed, 01 May 2013 14:32:54 -0700 (PDT) Received: from [172.22.22.4] (c-71-195-31-37.hsd1.mn.comcast.net. [71.195.31.37]) by mx.google.com with ESMTPSA id o10sm5767182igh.2.2013.05.01.14.32.53 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 01 May 2013 14:32:54 -0700 (PDT) Message-ID: <51818A04.5040809@inktank.com> Date: Wed, 01 May 2013 16:32:52 -0500 From: Alex Elder User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130329 Thunderbird/17.0.5 MIME-Version: 1.0 To: ceph-devel@vger.kernel.org Subject: [PATCH 2/2] rbd: use binary search for snapshot lookup References: <51818945.1040002@inktank.com> In-Reply-To: <51818945.1040002@inktank.com> X-Gm-Message-State: ALoCoQn1Qf4l9OsTlNQ8KuGHNTtYzcmILb/5YR76D/Se1zjhOqJpF/redXxXGNgT/p31pVIUIP28 Sender: ceph-devel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: ceph-devel@vger.kernel.org Use bsearch(3) to make snapshot lookup by id more efficient. (There could be thousands of snapshots, and conceivably many more.) Signed-off-by: Alex Elder Reviewed-by: Josh Durgin --- drivers/block/rbd.c | 34 +++++++++++++++++++++++++++++----- 1 file changed, 29 insertions(+), 5 deletions(-) static const char *rbd_dev_v1_snap_name(struct rbd_device *rbd_dev, diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c index 3f58aba..a6e5fe3 100644 --- a/drivers/block/rbd.c +++ b/drivers/block/rbd.c @@ -33,6 +33,7 @@ #include #include #include +#include #include #include @@ -819,16 +820,39 @@ static const char *_rbd_dev_v1_snap_name(struct rbd_device *rbd_dev, u32 which) return kstrdup(snap_name, GFP_KERNEL); } +/* + * Snapshot id comparison function for use with qsort()/bsearch(). + * Note that result is for snapshots in *descending* order. + */ +static int snapid_compare_reverse(const void *s1, const void *s2) +{ + u64 snap_id1 = *(u64 *)s1; + u64 snap_id2 = *(u64 *)s2; + + if (snap_id1 < snap_id2) + return 1; + return snap_id1 == snap_id2 ? 0 : 1; +} + +/* + * Search a snapshot context to see if the given snapshot id is + * present. + * + * Returns the position of the snapshot id in the array if it's found, + * or BAD_SNAP_INDEX otherwise. + * + * Note: The snapshot array is in kept sorted (by the osd) in + * reverse order, highest snapshot id first. + */ static u32 rbd_dev_snap_index(struct rbd_device *rbd_dev, u64 snap_id) { struct ceph_snap_context *snapc = rbd_dev->header.snapc; - u32 which; + u64 *found; - for (which = 0; which < snapc->num_snaps; which++) - if (snapc->snaps[which] == snap_id) - return which; + found = bsearch(&snap_id, &snapc->snaps, snapc->num_snaps, + sizeof (snap_id), snapid_compare_reverse); - return BAD_SNAP_INDEX; + return found ? (u32)(found - &snapc->snaps[0]) : BAD_SNAP_INDEX; }