From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S941809AbcIHQMK (ORCPT ); Thu, 8 Sep 2016 12:12:10 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:42282 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932650AbcIHQMH (ORCPT ); Thu, 8 Sep 2016 12:12:07 -0400 Subject: Re: [PATCH v2 1/5] blk-mq: abstract tag allocation out into scale_bitmap library To: Alexei Starovoitov , Omar Sandoval References: <57D0AA74.5010000@fb.com> <20160908003859.GA31704@vader> <57D0BB13.30905@fb.com> CC: , , From: Jens Axboe Message-ID: Date: Thu, 8 Sep 2016 10:11:58 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 MIME-Version: 1.0 In-Reply-To: <57D0BB13.30905@fb.com> Content-Type: text/plain; charset="windows-1252"; format=flowed Content-Transfer-Encoding: 7bit X-Originating-IP: [216.160.245.98] X-ClientProxiedBy: DM3PR18CA0015.namprd18.prod.outlook.com (10.164.243.25) To BN6PR15MB1186.namprd15.prod.outlook.com (10.172.205.140) X-MS-Office365-Filtering-Correlation-Id: db6154f1-ca10-437f-42fb-08d3d802dea4 X-Microsoft-Exchange-Diagnostics: 1;BN6PR15MB1186;2:GJdaa8h39naGUC/vHwthxRV4Jo7ErnaUO+y5BwNmCLGBcFhsM3PE2sGVOA4BuUc2acX59xIoLthCVaFaevtYCiv21QOqTX9YGQx5sm4C2LFl2GYrdxjQnOEQljJRQ/ueURn2rm13PdQfWQNEZH5Ru2XJkzZvVu7oOo8DNlRPCU9+MKkQaq34I6pEfwerqdS3;3:susZ20URgzWxCDz7KCF7ItDzcZKuHfgvoWy32Hi6V1E1idy1W4p+Ccv9mJQtd6z7/ycWduSW/5UENECC9MAJeDJN7vNnXBJirX2xvQHYsHkhh5gjpUnnWNcfebWY8Km9;25:Wb+1erH/pljCHdm7YkfGMgr15mEXFa23UHeR+zdLFk77G3KR++6v5TMqWUebdtLumH21JPxXYeTEgP4pGFMT2/sWNpjhJJ712UZ+LjE1rdXRCTEBFV+2XyvRfh/uS9CxaKWbnCwi/3LEsCsLxAJe7nM6L+5sj5+c92TBjxgJHZSLMTnSTtoGHjDIsF3TrrnUy0aKsdhCRjthQyTVs+en6g3feWiBuQCP4w+zvBDG0a3OZ2r5axkpo9IfBXh9W9ZPUzdzeZVGYalR1Srb5PxeIr1ZMKDKOILfIgtUxzOIGxE8Wpq9rVlV5MYjzcM9hUe25W1mhQqyODhiScZVw0chxPbmlF/wGObBy/q60E3MqCvI2W18qAL8PAm7mHEeHFxSCnbagQe5O3T+z/C73tNfksU75kfBu/aFwKBVWFfaMU0= X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BN6PR15MB1186; X-LD-Processed: 8ae927fe-1255-47a7-a2af-5f3a069daaa2,ExtAddr X-Microsoft-Exchange-Diagnostics: 1;BN6PR15MB1186;31:D6B6hNTwDzxRx/nnr4LCHIsJxuaW81QebpL+NNknH16VxWVCIvemHWFF9vzEjVU07J+vM7nzl1Go6rR75RmHoh1FCCsj34a19r14qhRQTUNM2Edx6iSCz71DXjSR9kE88yONx+koEBb48/Ymbe/5JCv/vB0MHZ/ppnScp6sp25UpcyVFH51LbHdX6gsFJPSxEqunS2Hg7J485xuGtA0APWsvnJ/orrlfNhxmPPx4bMI=;20:Vrx/EhYbj1LZRJdxuK+eAPPMthoqBKbR4gzSluKTIox5OundljcssnozorB4zhW1+8+f9BA4i6UjCpbvBt9OFR728w+4uj5OWLprTTQP3mxOlXbsoQ4aQk49lzwn5KY+3y4lmL76KQGRwHfMwPB8jLeLBAP+3ExTaBfTBWoGJLk=;4:J7hxZm/ex6vustC+xJcffcW8C4INZ1fra6cATwTfh83OWjhifZNuE4Zn6rBHHN3kR4QlF6Bk1HHimWhZuI4VIRrMO/SG0uRHRXkRa5sHnsMBMJQTFF7t05ZXEtlM4r35zV54EuKqjcXJ6jALar7s0zEbdsj5+Ma9pbRDMYq+UXOf1yrOv/N4fk4HDv0K/LVC4CWHQL6KhlTIF75+RDYYpoD6lzDXqgLknZhAGckydwDabA0RPXYCwgwPaPV78okKdjkAn2nNY8x3Zb+QqbVksptqXXbC8xKmiyBIGmxc2W07eVoTUsHOt04szjmeIyK2HtHMWMj7xGDh20nr7JM2yVFtYjPONsL0QpH+GK4sEg+SJuwt0F0YDXOp0W9WWtdUjvX7OpYoTr6/7DtASmcPB9LGBKR9HkcjdCWAB5a9JOV6QTWsEPTLyqnEcrRVDzf2 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:BN6PR15MB1186;BCL:0;PCL:0;RULEID:;SRVR:BN6PR15MB1186; X-Forefront-PRVS: 00594E8DBA X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(4630300001)(6009001)(6049001)(7916002)(24454002)(199003)(377454003)(189002)(51444003)(97736004)(5001770100001)(2950100001)(65826007)(8676002)(50986999)(65806001)(83506001)(4001350100001)(47776003)(76176999)(117156001)(93886004)(5660300001)(81156014)(81166006)(77096005)(65956001)(66066001)(19580395003)(33646002)(305945005)(92566002)(7736002)(86362001)(7846002)(23746002)(19580405001)(189998001)(68736007)(4326007)(50466002)(3846002)(586003)(106356001)(36756003)(105586002)(64126003)(101416001)(6116002)(31696002)(230700001)(42186005)(31686004)(2906002)(54356999);DIR:OUT;SFP:1102;SCL:1;SRVR:BN6PR15MB1186;H:[192.168.1.153];FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?Windows-1252?Q?1;BN6PR15MB1186;23:i+nIosyUvhur/Zb4juBRho7uvhknu/HcqdD/i?= =?Windows-1252?Q?yAF8lyB53DJVWCMNW6EElbEkZ+VsZtM6YXIQPNGOFL4crbPcMuaiU7n4?= =?Windows-1252?Q?55xWI8emYHbWuVOL4jhovYYbCvSSjK9/o33xpo93cKNPiwm2pS2o4kg0?= =?Windows-1252?Q?yck3pnLyc8hGnwjbvcPhIRKS1E3Ux4JYcSQxHjRf/Y+Dg6lF9u4ZG5vb?= =?Windows-1252?Q?bebj81d00tkTqJT47zB32FPFtqQbbiHc1c8+EMCwGOLrk+5fWEHKkwyl?= =?Windows-1252?Q?6pML9ISlsDSdDxEPX7V12nZPrDmKtEkr8y5GS1v9RkQB9PvgAQLOOgM+?= =?Windows-1252?Q?NRH62jwSOXKJt36N53YPgKJr8aAYhj/wxPLnQQ4L03RssswB14JPxQlm?= =?Windows-1252?Q?LcQ0JOmxvrJ3/c9TBHp1Nu9qyyXYqE4bsQKNEgrTFWuF4zsY+Sv8KQQI?= =?Windows-1252?Q?7/QgdfBDUIsV3S6i92zmqTEiWj0r4oehz+VeVHcXbJ9oO7f1MYp5/i8z?= =?Windows-1252?Q?9qjOWURTFEmr7if4ly+VGcgzJ9k/nrp27udynLquTRslwWtTk2tOcCiP?= =?Windows-1252?Q?Kl+7ukKC0a61Q/Nj1LZvAUZpKZl66BFPcwrbrkivLZJotxYVl/E8eVt8?= =?Windows-1252?Q?3mcjZYW2kujvasFdn5p0EcGPwyoIPZQrIXK8trBUqiFU+XK3oHIqfhVN?= =?Windows-1252?Q?sszOsW/gOJWG6Aw1Vp3jqsOC7kouB9cHj6TMI3zmo7sJ/HNprW7Y6lqI?= =?Windows-1252?Q?SodcQXfbdakBJFUdZ5j5g54WN7irFGFSQeuHB5UvAXprqZD5oPN99V9G?= =?Windows-1252?Q?lRoaABgiEAjUR3kFzj7wpexcpR9ClGHBuwtW14jewljb0BrMcDXlmvnS?= =?Windows-1252?Q?TyBV9k82nvQpPg+TBue7Y6F78uOVaO2AeIadwRF8rEcDFd5zD2ZY1w7z?= =?Windows-1252?Q?rxhIXDZ30xoMTCsNuz7yaPD7Aqzg0ZOt3Rga+ppB4OmzqKCS49x/iP40?= =?Windows-1252?Q?fkz7Om+J0l0l/O+zYQ0w3UZ8oTRCoKhetqOP50QNeMimkA7X+nxJYexe?= =?Windows-1252?Q?bL+2pOIPE3yGBRk67rkC6Hf5ymmZc+lcqeWgWUdI9FyIHoisyf8wQdi3?= =?Windows-1252?Q?+MN7pHT3/JganSft0DaDRKwDAtw4Jf42HjE0+IqA1ogyPz9M6d1ixSn0?= =?Windows-1252?Q?k6tHSQPKlq5/u84Eh/IZIBUpKqNuvHgZLr/zQmeL68m3H+bjBcRo3CTa?= =?Windows-1252?Q?gJm6q/RbksPjhfTkTXfqvsmXGwoTwV6XaumA2YzHyZrEOETl3yPgh+4I?= =?Windows-1252?Q?dkiUUWWEHR0l6rLIVWP1tKsYtlDP59cov/fpqL2uxPzJqwNWFxQOGq+B?= =?Windows-1252?Q?cDBs/UcxNeiI6VrdZvxAUh7T2IskwyWmoiTo+jbgkmpD1eGLdCX/QYeK?= =?Windows-1252?Q?/PSirtLd0MtIejMI9N2ed6m8TMP1IFSZMFkWnsdei1L0IpiaU21y5M4f?= =?Windows-1252?Q?NK57xc=3D?= X-Microsoft-Exchange-Diagnostics: 1;BN6PR15MB1186;6:adBiYPcuLK5Gv7mUwxYV3AFCkwJJpUaFpNRBbjv3fcQeFqlPcwPmzDwXpy8SbGy///SriGSPCUhXohZoEtiKoaxkDcE0JofTbdm1TN4Cpd1KEd4RflaJUOpk05BSk5GOLmyDlpODQpUTJDLlU/0FxXgKaX4AYxAdpfCygxPBe2btl5haLzPGbdu64NkdrmmEHhoWZ8sQIjiyj7cdBc6JN2p6/a9no/B7kmzlpLE1mSt0etfMV16j1rsGkGKL/4dsGBkw4jlQgUlA/rhktf0IOz5UD8zRIiK0RHgRz3D5Sa0=;5:a6dMpPP+lNj/OzaIN1gSCANYyw/dkLx7weqU1l6pZbyXJAsqc1dGg7wQkbh/0Pg486R03cT8TcxRGR/13R/CAF5QflZjKjbzGF96NRKD5cMOYF+juoXo36DeCBkOoLsWscd5REzjjmuVQcfQUTgD+w==;24:EpYnClPnpc6EcYiVMpiClRr94T2ymkYPdQ1fn2LB6q+Wkj4NhHr3iUDKR5933LUYsP9ZvKni70/WXyRQQr0Cc+qg9XswqZRPpUxrXV6+Y6Y=;7:l11KKwdjVyGTP6l6j9526PY6awWFOaNFj2hYxScdJgJO9oK3dOBbKV3HJM1u6I5OhX32AzP+ZyZGNyLRZWmJVRp6WyTqkkLllPXoGdEqDb5nNdZqilnD8yGwbfOCfbjfjQwe32evTcIVugXkLIO2W0FaL3rHvtWzBhHL6iWBSYCfGmrWYhU09LFKPtdi/nmiK4Gc7DbBUX9bo0CZf5XoZ/PGHG0XDDX53agSpu6LOPkO1hJU9UZdmV1muBSGtV4l SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1;BN6PR15MB1186;20:nbZ/KPa6fV74shCuEMpFQK4AHMs2LaHswQW97TPgpJXw7VWF/QFVIfYkGosdru4rz2EwS5YKN0B2nPlSsAReLVJ08rCaSAa2HCmiuUFWHcoiGlpj7vsAveu1wv0DfWKmjk4YOXxdUnckXbJOXhExfCxvCCQznxzsV33RO4wGYDA= X-MS-Exchange-CrossTenant-OriginalArrivalTime: 08 Sep 2016 16:12:02.0708 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN6PR15MB1186 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-08_08:,, signatures=0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 09/07/2016 07:12 PM, Alexei Starovoitov wrote: > On 9/7/16 5:38 PM, Omar Sandoval wrote: >> On Wed, Sep 07, 2016 at 05:01:56PM -0700, Alexei Starovoitov wrote: >>> 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. >> >> Agreed, I'm not a huge fan of the name. >> >>> May be resizable bitmap would be a better name? >>> 'struct rbitmap'... lib/rbitmap.c ? >>> >> >> Hm, the resizing operation isn't very well thought-out right now, it's >> there because it's okay for the way blk-mq uses it, but it's definitely >> not the point of the data structure. It's more of a cache-friendly >> bitmap, or a sparse bitmap. `struct sbitmap`? `struct cbitmap`? > > yeah. naming is hard. > I think the name ideally should indicate how this bitmap > is different from array of bits that is already covered by > primitives in bitmap.h > Is it because the user can wait on the bit or because it's > smp aware? sort of percpu? I think that's the main trick how > it achieves good concurrent set/get access, right? > struct pcpu_bitmap ? > struct sbitmap is fine too. It's not a true percpu bitmap. Rather it's a sparse bitmap, that provides some nice cache behavior through the nature of the sparseness. The percpu hinting helps with that. sbitmap might work, S for scale and/or sparse. No name is going to convey what is special about it, but luckily Omar did a great job documenting it while pulling it out of blk-mq-tag. So I'm fine with just calling it sbitmap. I'll be pronouncing it like "spitmap". -- Jens Axboe