From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752207AbcIHACU (ORCPT ); Wed, 7 Sep 2016 20:02:20 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:60973 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1751176AbcIHACL (ORCPT ); Wed, 7 Sep 2016 20:02:11 -0400 Subject: Re: [PATCH v2 1/5] blk-mq: abstract tag allocation out into scale_bitmap library To: Omar Sandoval , Jens Axboe , References: CC: , From: Alexei Starovoitov Message-ID: <57D0AA74.5010000@fb.com> Date: Wed, 7 Sep 2016 17:01:56 -0700 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset="windows-1252"; format=flowed Content-Transfer-Encoding: 7bit X-Originating-IP: [2620:10d:c090:180::1:bd79] X-ClientProxiedBy: BN6PR04CA0012.namprd04.prod.outlook.com (10.172.194.22) To BL2PR15MB0962.namprd15.prod.outlook.com (10.167.116.24) X-MS-Office365-Filtering-Correlation-Id: 55c56e73-f6c9-49af-806f-08d3d77b5c08 X-Microsoft-Exchange-Diagnostics: 1;BL2PR15MB0962;2:hodW/qcJuojVpc+H1e5jmot3KD35M4iNHqotAam90PO80jxpx0sGeio3blkTHWg+tBBGdblYyEyHEvpIyjLooWFutj4mCYeGxcqF0y4KltfazkKRobVrUFtvUZgYPrgcGNTJFA3fAK52n/etXXoIVu3k81kqy/OfsFb0E14Gb4nfn+vDL88nJxIEG5JiA/Qs;3:w+4Q6Ihef9FJPvHB6q6tZLdWUrx1wxgv1WGWczwjjRnKMFHhvPBUG/H2ylyKLoVwiqgzaAYQcO6yEG+0VXGZcszf8Lxa7n86vH25YqgeCQj0MI91QuQHLsKRNKHQJD6f;25:V0Oan+YVSatiI0ciFv4pMOi2Ha1ps6aabEQ1IVOa4jAPPu3lRoK6+5S7bz39kY9WEL1RbVNEingC6SUYb9aNZ7QGU2xrGxv7N/Qc6SV+w3DAmzXOEmuQb1vEMejRiRYnaeJuFU4wrmzIoyBRhXbUuZgHE/Hg2UGcJT5HNAZZxCeEsp4PR4E6r75UK6E+VbGkGmUWrXHfA3P00/nANWxMXfs+GzPesTDl46hCOUAOZAylyk+PCrl+bfobQ6xNo3Fhz0w4b5gV5Yq3cQ9oEbLlHWxCkVDoEFwVJspmLNdVv2mj8KswmzGqKSEvPFfvnduEHQXrKLg1lTQG0JkIsIl63cdN/Y4D71AF6VIU4RhS+esv7gslTqtyjit5rDTcdp/hG4UjJFKZDIDJMWHbY6EuxVbsMpVcPBPKYJWRgtxERdw= X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BL2PR15MB0962; X-LD-Processed: 8ae927fe-1255-47a7-a2af-5f3a069daaa2,ExtAddr X-Microsoft-Exchange-Diagnostics: 1;BL2PR15MB0962;31:cTZlbv144Wlmrj8dyXnHAIaJqpFy0ZDvXZcQGU7asn070sErVldW9CEiP0jwFlvVNGw+4BjBhrmq4rJguvmyCLEJLmOeFwGDx2UrW/T2dYi9ZletM14lbdFm2uZGvHzR8WvdyCmU140cOGGk93C+J95dnsevy0jA2jUX8PPuBW1JwDLbunDsIBLtDMX52qHqMGUde5z6wmCEfk5sTui8ilwzjbEspjIBUqTmEBmBt00=;20:GBJYFUiRekkkubFhPAx0OB8fuNb9n+vEzkuHZ7h0We1yCkQhfLbIFQmWE8FserUOHCzkgqxjOKvFnSyMu07OAAokSaY5Aw9RbWg9VCb95wA3wWqHoHDTu8eMzYI4+MuKxl51NMrEUXlGsNKyywHTMeTAYC2ETsiBSp3xhRcj/sU=;4:L5Ahxy/1UTGnKpPuxi4U0M8E1kssl8Dmd2ycf+X8hDClKcZrX8YwETVNNe9cUPsndGpIrAtuIoLPUdxndjbWg0fSNoRq78rKfzf4GQfdXUKcod6ZfRfLuj/UEfmfNvdxz1yhX8V+qsviLYQeqHe8H0izsUAytZGIGeKDpDp9L3FkwF5dlbWOCkYMt2fKM7f5BDYtQzFknyCsKXJbRRoyeoZdVxkGjYs7U4nk0gXgSEXktH+LZFAzzbesZqzJKR/+Uvd0gQzEyHE6Mj+jVv7aYDX0Ue0rxmOpq8FuS2wAKCUjhpYwGUDJP5E0l8TbQebZ8LAe9i41lCFlbWN65nc3rGIxLx/pl3LzboyNaRh5uNwAj4id+eW4enKSKQqJuM8/rmp7VOySRM/U2v4rUj3mgIF8JS2PhQ5ftItttAcQtdEeRjbpxPn87Eav8fxUZcKv X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(67672495146484); X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(6040176)(601004)(2401047)(8121501046)(5005006)(3002001)(10201501046);SRVR:BL2PR15MB0962;BCL:0;PCL:0;RULEID:;SRVR:BL2PR15MB0962; X-Forefront-PRVS: 00594E8DBA X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(4630300001)(6009001)(7916002)(189002)(199003)(377454003)(24454002)(189998001)(586003)(92566002)(2950100001)(5660300001)(6116002)(101416001)(42186005)(1706002)(59896002)(47776003)(7736002)(19580395003)(68736007)(230700001)(7846002)(8676002)(81156014)(81166006)(5001770100001)(19580405001)(4326007)(305945005)(50466002)(4001350100001)(77096005)(2906002)(97736004)(80316001)(65816999)(50986999)(54356999)(64126003)(87266999)(76176999)(106356001)(65956001)(65806001)(86362001)(83506001)(105586002)(33656002)(36756003)(23746002)(3826002)(42262002);DIR:OUT;SFP:1102;SCL:1;SRVR:BL2PR15MB0962;H:[IPv6:2620:10d:c081:1110:8000::23a8];FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?Windows-1252?Q?1;BL2PR15MB0962;23:pknQl6fnIjnWFHLcxAN1y33UvcNN4FlE/xztP?= =?Windows-1252?Q?1Pr3+dM1RBauM4Xd3rSrxiKMifRLAAVcoCmexWCLQcA0wNX5PVKopMls?= =?Windows-1252?Q?KKpUfq3upb0d7AOF85q79FUTepIt6fU5ZQ1s5l5neMPvgTi2JtMGjGzZ?= =?Windows-1252?Q?pp1QPbQFsjNkct77kv3AENlenYzARoYs6+jnE7IBzUkAPIR5uuuu5EI+?= =?Windows-1252?Q?JPJMPtF3v7PWDmTncrEaGTbxT+HBhCJSY4Rg8lryf6FF6LLpJ+DTnMjM?= =?Windows-1252?Q?3xT/cLanvHapo84oH+H39agzIaP8jgTQyRsJ7ka5nS9KnVDuUjXgbV2v?= =?Windows-1252?Q?vcN9LLlSwpOSwSU629iP/ZrJafnDQXJa6V6Raxu4yoy8BoEznHFXXLjq?= =?Windows-1252?Q?Xg6AIgpenTAU1qmtdemIvukNUSNS/zuUR5gO0IoDV4LrrgmqwCGQadAx?= =?Windows-1252?Q?b/C2QRdQ2RXoLXC/EkndhX2LyqdFOyU5TY56DSAfzwlIJVzumDltRW2B?= =?Windows-1252?Q?kJkM6icLTAYOlELhZtGIKVr746J6pduhNFehWLaHIQYyD3Hc0xVjV+bp?= =?Windows-1252?Q?d2pQewQobWXrJF3ERWNyv4u3MY6PzhjQNVBDXml2fp7OxVZx1IqAyKNO?= =?Windows-1252?Q?CWeJrUsjcym49i5U0fGPnnBFIsUE9dVuVAYTNYKQhk3Ioie2fxBRfvIV?= =?Windows-1252?Q?nC1VS0urZ5Dff24d1icjm4tSE+WuSaZhCiHbHtZmNZBXRWVNt/HAi1/O?= =?Windows-1252?Q?maV0rfva6NPRwyvOrJCYgaEGYywxvRW4th+4bj2I0aicKuf97fNwWtum?= =?Windows-1252?Q?eucbEEuD/cm1ZeiOQHlWNlaXvNWwNztBs9TFMUF2OXlp4zWUNLgMWFUH?= =?Windows-1252?Q?0gIpqh1s/8zeXeVU96NjkELkGHE4fAG7AMqAhUl32RRlKa5u+uRWQxes?= =?Windows-1252?Q?vIZSYuvCbO0anwD72LbKlZZ0VQNjrJiPrX/9FWkim/sFPEfM1kFeMNnk?= =?Windows-1252?Q?SWxM5FDVEVw0HaF450Gii12dLMcIxKcZfRMmU7LxyAQdF7ush1WRFAFR?= =?Windows-1252?Q?CAbEQ55j/yRyTwCrepwGvtn7QTy6Q4Gi3Tv7BjI4B83bXe2GamE6WHDT?= =?Windows-1252?Q?5IrSHjIAsRJ2PE5pWZg3cc7hMHBdmEz4wK+dCeLZrIGyq/bvaGhBMRYe?= =?Windows-1252?Q?occlb7tWBC5nwUXlLfub039dwZ9mcLcY6bIWDhbiVVguAdZ/235cZJ9B?= =?Windows-1252?Q?qV7VGel7V6POs/2cUdW2LSKQq98IA+YAKSdP2fm+h1FMBlfly58Usj/I?= =?Windows-1252?Q?Yre/PtWROV2pwvtQym0T3k+UbcTsZi5fz8TG/f11m8MrQgJ0MuPSvq6R?= =?Windows-1252?Q?zwWQJzkmPcjE2gd6VlWtda9FFK2jJp5XGO6L7VxQikGNeMoKakkAHU?= =?Windows-1252?Q?=3D?= X-Microsoft-Exchange-Diagnostics: 1;BL2PR15MB0962;6:eDo87x/rl/ex6xqscGGsYnPRrMC7dngfadVKQt+wzFHC1gbrh8N4iVkIheR417QF8naGyiGyKelWeG+SliWqldowBeYkEnuzf0m6TSVJQj+aNgbxdcbiOWK2HTgBmyjvZiuDUknQZXaX09bmXLbs6t6+TinCi/sMeaCKUKnN6XGT9+JXTRXl7BW+sBDn0l8hSDfxUIRF5JknoOeFY3FV0jTsDmsZdsjO1ksWkAa3Oo+XkBfeiwi1dV55nugZnSkgcBIKfORlvI+fdF30IaNWQYDbpSjmjh9fM6Ogm2YZv6s=;5:xaN+j64CedF90XnfPhLOcsba7Q6uzCVkyrIaQDYy3klXVnVHF7e/eauCttLt+nmNzxbgzX6TLallRlMz/6HGlw1ePMwZq6SyZa37steIPbETo/ZIARY2mIA93tWXzIARh4aUSGIpCad5mDqd9euKpw==;24:6nSkU/PDDnrWjhsUteOkson5MOZR0Ge90T8OHKBeWihxxNiWuoyabDR/YkDUS4Q1JA9ESOeyrYNTokg2tfQWka9RmDJ51MjAXDvmsnY0UbA=;7:isEOL1668nriaBAdCokxP60283pjI24KpnUcbZH5/6s1s2DMyc3umlqGZ7VLlT/AbieefJussKKfFKVdTINSuQTs9S00gUzANRt5my0dCKCFPN34ZJ9wfsvVpaiXvNWjGaCgyx1J//v347mQ23yjj0kuvGN7Z7JLAHDeNSe4YSJHTTwKZJX82yC/eAoZPiuclY4JAzbnZGYZStWhuJb33J5M6XVN7PP8MnknYepWsnbRMiL2ydNaiLHA4HpqByTf SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1;BL2PR15MB0962;20:4RExvJFcwlCUQ6MHxZrmbqKWQj+fviaEc6ps6Tler9IDhNHcNazOHxgbYrUWyODReAyRTKroKofZ7AvDI6dIMfGccCrNqUYo3M+zmaZZydUpCnult2BtHtrAmHjPmHLkqdCc+I8mP7ylM0kOr/m1sylJG5bwY6+TEJvQQ18ICpA= X-MS-Exchange-CrossTenant-OriginalArrivalTime: 08 Sep 2016 00:02:00.5584 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL2PR15MB0962 X-OriginatorOrg: fb.com X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2016-09-07_10:,, signatures=0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 9/7/16 4:46 PM, Omar Sandoval wrote: > From: Omar Sandoval > > This is a generally useful data structure, so make it available to > anyone else who might want to use it. It's also a nice cleanup > separating the allocation logic from the rest of the tag handling logic. > > The code is behind a new Kconfig option, CONFIG_SCALE_BITMAP, which is > only selected by CONFIG_BLOCK for now. > > This should be a complete noop functionality-wise. > > Signed-off-by: Omar Sandoval > --- > MAINTAINERS | 1 + > block/Kconfig | 1 + > block/blk-mq-tag.c | 469 ++++++++++--------------------------------- > block/blk-mq-tag.h | 37 +--- > block/blk-mq.c | 113 +++-------- > block/blk-mq.h | 9 - > include/linux/blk-mq.h | 9 +- > include/linux/scale_bitmap.h | 340 +++++++++++++++++++++++++++++++ > lib/Kconfig | 3 + > lib/Makefile | 2 + > lib/scale_bitmap.c | 305 ++++++++++++++++++++++++++++ ... > diff --git a/include/linux/scale_bitmap.h b/include/linux/scale_bitmap.h > new file mode 100644 > index 0000000..63f712b > --- /dev/null > +++ b/include/linux/scale_bitmap.h > @@ -0,0 +1,340 @@ > +/* > + * Fast and scalable bitmaps. ... > +/** > + * struct scale_bitmap_word - Word in a &struct scale_bitmap. > + */ > +struct scale_bitmap_word { > +/** > + * struct scale_bitmap - Scalable bitmap. > + * > + * A &struct scale_bitmap is spread over multiple cachelines to avoid ping-pong. > + * This trades off higher memory usage for better scalability. > + */ > +struct scale_bitmap { scale_bitmap sounds odd, since 'scale' is also a verb. We also have lib/rhashtable.c: * Resizable, Scalable, Concurrent Hash Table everything is 'scalable' nowadays. May be resizable bitmap would be a better name? 'struct rbitmap'... lib/rbitmap.c ?