From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751009AbdISBdb (ORCPT ); Mon, 18 Sep 2017 21:33:31 -0400 Received: from mail-cys01nam02on0079.outbound.protection.outlook.com ([104.47.37.79]:49984 "EHLO NAM02-CY1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1750781AbdISBd3 (ORCPT ); Mon, 18 Sep 2017 21:33:29 -0400 Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Felix.Kuehling@amd.com; Subject: Re: [PATCH] lib: Closed hash table with low overhead To: Andrew Morton Cc: linux-kernel@vger.kernel.org, amd-gfx@lists.freedesktop.org References: <1503971590-15963-1-git-send-email-Felix.Kuehling@amd.com> <20170915141456.4382d7ffae7ec8a9a86c8cf9@linux-foundation.org> From: Felix Kuehling Organization: AMD Inc. Message-ID: <1183ff82-8ec0-6ea7-4613-2f0fe5e90bfb@amd.com> Date: Mon, 18 Sep 2017 21:33:16 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0 MIME-Version: 1.0 In-Reply-To: <20170915141456.4382d7ffae7ec8a9a86c8cf9@linux-foundation.org> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Content-Language: en-CA X-Originating-IP: [165.204.55.251] X-ClientProxiedBy: CY4PR13CA0042.namprd13.prod.outlook.com (10.173.156.156) To MWHPR1201MB0237.namprd12.prod.outlook.com (10.174.99.23) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: d8c3b4de-ba3b-4e54-4e30-08d4fefe6d0b X-MS-Office365-Filtering-HT: Tenant X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:(300000500095)(300135000095)(300000501095)(300135300095)(300000502095)(300135100095)(22001)(2017030254152)(48565401081)(300000503095)(300135400095)(2017052603199)(201703131423075)(201703031133081)(201702281549075)(300000504095)(300135200095)(300000505095)(300135600095)(300000506095)(300135500095);SRVR:MWHPR1201MB0237; X-Microsoft-Exchange-Diagnostics: 1;MWHPR1201MB0237;3:GE2UK7OEpAgoG0Mp4QKb8utlWhHKpSP1qbOrxIbS2f+4fATKPxbq9jDTD54ZrcEJV1QXqkC2Nai0FStKS2jv0eS4B/BpGKeK/Z6M6HTes9FNR/iZAygwollH5u+JAbsGzRMfOLKx9o2T69/vDqO1jHoIdMjuWR5WjaVfexe+35f2WgzvVXe0u7RWrcOABgTekHBYufoZ4H5uNF1YqMgMisYR5i9wwvRVTfPKOb53mU+x2v2Db2/p927dtF4hkOpa;25:9/jcmmTfVMnSGS8iztYU4O6xp9iuw5PTr3khQY+CD/V5awIjC37qo9PACnOOJAL3uxQ8vPaU1s9vVjAvtiFHGjtivzWvTWn2RqtFCX69tUe0dlpwSwGGJQgA3YGIa/heFMNqrfebUs/YcqeoPqcb4df4wvwxNWG4Zc2Wm0n2c0GW1chUy019xajzY2S6aBVBKbvhfSzlT0UzixBa1Y+bNlPBrmwUeN2DX7ZfA4WD0mHz8+u3HpEcaLhRibuByYNtKsU95Kos2gdX5UlGQqn2UHoLHu7LqfBqot8RHCuN4tSu9VYzBRViThluVtdakXjcrvrAOWuADBVV0jLgXU7L0w==;31:LIjuprTJ4BsrR1V9+Z7TsG8YrOa2y8sGf+Itp29mnT+CWPHD1a0iiwTzNMoAfGSUDu9yip5HQtFN6qV28U5g/rIvQWvg0G6b8y54TQqOe2aQZpLUe3I75gfNq/tMPvCoEVnaZm/J6nrEcE5WpuZ6DMU6AYhmtyDfCNVhM5Qx3gPBlIW1f5UTT5ncliQlTocRgv1C2cdV9MsoWJbOklP1WVg5sqPNbkIB8b8VnoEjSYU= X-MS-TrafficTypeDiagnostic: MWHPR1201MB0237: X-Microsoft-Exchange-Diagnostics: 1;MWHPR1201MB0237;20:aKpq5/+aZJSPYrkOjSsCJ2A/F5/rTOfou0M0WEmkgeddN9EbdDojPs3bdUqh5VgSULnYkHyN7VAx6V34gFKJIJzjvEJmTXfQ4rFiVq/SxaeoqN1m4NwXl5y0c/4Goh7tIPhBB5oXiKZMY+jbXF11UPIO+LefvynVQu0fXzlRZHRZAhEuOOdmCwE+xF+oBZ6jHPzTHY7G2+jzKl99VFaF3ZnACmXb/BY4wdaPYa58EFpFxFqGP37QvlrThbH6Fdo3kI/X94ObDH+F7IuNT4rSGx6Bgkd2oVWmWov2jqNl0SdnwsJTfwXvPxktfNWt4wUsBAcNAyg89KL5NwaRjvc0YGDi/b3IRA21RCTiC8JtR29OwPJK9kXkAXUY319n6OD9fI2gZbhXNJGRJMa2xe07D9SH9OENIWaCrWQ+gtHHDZPcTqftM3Knx4vi/xtakg7NqbYbW+dyltpPkVGuGnf0imMhfDF5tecEgCvT6xDREetOpW2ZQLat3BJMpvKDbD/Y;4:bP3GNpRPmgMl1U0DUus8dOpQhBXVYVLV65MVTcoqiSbKeW3SNGlUZGMA8ZSq24efCpc44eKKdKmEj8YNuqibzOtptO5Z5oMicBuJdhNhnH7e5KZNzTfH13docNoxhEB/kcajIXi7J6kSUI6G0BRfRUg893Scr2N9WXgwJ2Y+co0BACcNS8JqrjqBojaJHxE71E796spKKoerZeSgfWJRyc24e42bmOGFVw7MAJoojP8D7SyvoWpY/Lb9tEW95kKjiHW9neaW+T8P21gPTEB74fxfhusxptjUxbRRHaCVbu1SuecAgaDBkUMacT3bkA0VC3FzU8nJ7Q6Mz3gBD61JfA== X-Exchange-Antispam-Report-Test: UriScan:(278428928389397)(767451399110); X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6040450)(2401047)(8121501046)(5005006)(100000703101)(100105400095)(93006095)(93001095)(10201501046)(3002001)(6055026)(6041248)(20161123555025)(20161123560025)(20161123558100)(20161123564025)(20161123562025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095);SRVR:MWHPR1201MB0237;BCL:0;PCL:0;RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095);SRVR:MWHPR1201MB0237; X-Forefront-PRVS: 04359FAD81 X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10009020)(6009001)(6049001)(346002)(39860400002)(376002)(377424004)(377454003)(199003)(24454002)(189002)(50986999)(81156014)(23676002)(76176999)(31696002)(478600001)(8936002)(72206003)(4326008)(86362001)(105586002)(101416001)(25786009)(33646002)(106356001)(53546010)(8676002)(81166006)(65826007)(5660300001)(7736002)(305945005)(54356999)(2870700001)(189998001)(6486002)(65956001)(68736007)(31686004)(90366009)(47776003)(66066001)(77096006)(36756003)(6666003)(64126003)(229853002)(6116002)(83506001)(3846002)(16526017)(65806001)(50466002)(316002)(53936002)(6246003)(6916009)(2950100002)(2906002)(16576012)(97736004)(58126008);DIR:OUT;SFP:1101;SCL:1;SRVR:MWHPR1201MB0237;H:[172.27.225.16];FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtNV0hQUjEyMDFNQjAyMzc7MjM6NmZmVGVUNUJESVc2ekZHOE1wanlUNmo2?= =?utf-8?B?K3hDZ0s2K3ZaUDVrd2EvS1pCUzlTbzBvR2NaaXBDaUdnTFJsdDM1SmFsbitk?= =?utf-8?B?cG9BREJDYUtkdzBUZHk2WW5ycGhqUjh6OU9pbU5oajQza3Fia2JVd3lERDZ4?= =?utf-8?B?dU52S29vNlhrZDRoTG5UaWpGTFJvanBVMWRZVWovM0YxZFlQNlVSN2dOWVBG?= =?utf-8?B?ZTNLc1psOFFNK2lyazRFVGdUT0kyckFDM0s4Y01YZzNsYmREc3hqdGhBTGJt?= =?utf-8?B?R0VWWTl5WjRjckIySHRKSldQU2JQN1RQOWdKZnRrK2VnYXRRVUg2bExIWmVM?= =?utf-8?B?Mk5uUEJUdndmaFlaMmRGUXp6WjRNUjF2RG9DVUU4S0piMk9lMFEvTk83am1t?= =?utf-8?B?bHZsQmxMT0NXUnh4SytiWlhRMEY0N1V2bjZ5SmVHQlk5Mzg0RStjcENvVXQy?= =?utf-8?B?VTNON3l1aWJBcTRDOHgweWl5d3ZkcHFhOVVsOStDZnI0QVMyMlVWeVFzT0p1?= =?utf-8?B?RWpYKzVpRkJTcFZQNXFYOEZiZDFqQmpIVTFMUFlyQkxIUGxSNFVKb2V1TWh6?= =?utf-8?B?NURFazdVWFloMVB3clo1Mm1JYnBqU3FGb3JRbzRaZWFnVGVRL3cxOHU1Y1VE?= =?utf-8?B?Mi9KVFhkL0RQWm5OSjRkaWxEc0RuOVVKaXVteE5QZ1NqNUhNQUdFRVRBek5l?= =?utf-8?B?djdDb214aW13cm93OGZueEwzTnZKVVdhWDdMQXhxejBYcHF4bzFRcmFpek9R?= =?utf-8?B?SElhOUhKVERFNFRxNy9kTnlNQ2hTM01lcXJ5aWFIN09xTi9zVHgwRGVaTFRG?= =?utf-8?B?UEdGeHFLMmk5cERkbFgvRUlxY2cycW5oMWFYM3NZMkwzMFRIT3U5OFBwVXYv?= =?utf-8?B?R2paYWNPM3FJckg5a3pzcUtHY2xMdkdDdUpYcFUrT2N4K09lT0RDVk1sa3Nj?= =?utf-8?B?MlNsWlRGeEg1eXBhbHhBNE9wdGttTkJBeCtsakVIUFJFdEZYZVBWOE8wTDZZ?= =?utf-8?B?SHFEeFQyZkxYbGJzVzBLRFR1OWV0L2VaeXNJVTFrNkNaRDhreGNCYlVoQndO?= =?utf-8?B?aXBiZU05YitwRVluSzJsYjZZUFZLZjhoWFd3b2YwNGE3ekJpR0c0ZGxVR0Y3?= =?utf-8?B?QURsL3RUdEFTSFJKTklaNGFHSFVUSE91ZlNJS0duaFd3QnB2VWllNVhERjNt?= =?utf-8?B?M2c0dHJWQmlSekwxdVpvS2JrTnpsVVNsMlN5REFBSFcyMTB2eGgwTExabHVl?= =?utf-8?B?THZSS0g5aWIrSmNJZ1M0dFhRZDRqNGlIVWJheE5PZFdybHJxaU5HRHpXOG0y?= =?utf-8?B?ZVJQRXQ1MWY1R2tocXFSVkVHY0M4R2RmY253YUtLdkoxK244Wis4bFJzcTFQ?= =?utf-8?B?emZ5MmZLTDB1RUNBbFdpTDFUM2paendjTkhXWVVCcUFHRExsM2dmMW1JamF6?= =?utf-8?B?Nk9OYjZEVVBscGpvNWVWMnNnT0xCR1NJRjQ2Qk05NEFwMG11UDBYVHBpQTZa?= =?utf-8?B?QlcwSTc0Qy82TElMRGQ3UVp1alp6bUhPVUQxaXpQVWhycGlKUHF6TzU5U2Zx?= =?utf-8?B?RTJTaXZRMjJvcHlRSWh0ZWNjYitiTG5LQVpSd1FXS1J1TGJ5OHdSZ1J4aDZ3?= =?utf-8?B?M3piMUUyM25qZ3FSaUVWR0VIZnJtYmtIQ3BkZUVzTlkxakFUdDVGMTByZE12?= =?utf-8?B?WDJRVHIzbmI5RFZrNG9zbklZN0hDZStINFNNblBOSEpYaGJ5Mmw4RGEvTW1Q?= =?utf-8?B?ZG5DSzJyNDdxdUY3Q2NBVHNsemNwYjVGclFVZ3ZyOHdldlEvNWxyYktEMGNB?= =?utf-8?B?VEF6RnFBdzNPWjJOZ1l4TEVXdlB1NzNuS0ZObm1qZEgydnVYSzFVR1NWOVY2?= =?utf-8?B?SndKZXdoLzN2elVRTVRteFVlQTlqSVZHYVdabEpjTksvcm04VmJGS0FITlRo?= =?utf-8?Q?brR8z//IC02bRbCfVIMDsEKOvNBWUUac=3D?= X-Microsoft-Exchange-Diagnostics: 1;MWHPR1201MB0237;6:ekwjeKvU8YKMct59BzbOZSsCLUgQzpRoKZHVwrYfwAZsTG2V2BI61xYajnfSvdy1dtuOeiOn+YmNJQy300jWYVVDPHhdJDuLbzU8nMlMPwVcm0PRKKjrs8r35YYEphQrBK8bkNdK0yzzTP+QVV7bmNwxy++oKdvBiiKattH0ARuW5STgcCoep4P0VGn5Rew7cFbLLKN9LPO2vgYNDh+RFqkJO5+2cs6xPHpwmy/rgTRxx+Jbh/AUW64ImYqq+hKXLO41bxGkkbs5wAxfYCyi07dhRi0hiPjqfo1lUHqa4PKe1H2EzVYP56MIyiqIg094yhaOsnBmJip5jFpkK2zRbw==;5:0ZjRyOY0HlxWwokD5avD89RhylojpmXKAv1Nz3B0Eh21PYNBDf6137lZt4A+CRNt5jApKQU2gzL63LZIgoV1ub1xSZOU8YPihaEHNKNxOFELOGF39Foja2UpeAykfvLpXRiYHI1Jion9kIlpCwd4BQ==;24:SjjNsDHIyos42nNSQLVoDNCHYjjCdPysJ5XB+bMGrfArxLbk73CbBi4t/YTMN9VBoa2LzpGvsTDNn6XHkVoBhCsh34o1J5qM3VOWAHxudTU=;7:T4wdqvG1rTkFKJRRhmZ2kXFlV7Y65vD4VStY+bj6MA9fIWVf57RKq3HEiYVLMtwcd1jucvvf+4M7ib4hsFTQ087D6KCm6JVDokN2/frJGyMqyr7GznYtYD9psInnYmOQt7/jtc0v4MMF+BBVBoN7Sut7cQQxN9Y39G1I/f9C6KBMHgO7L36qvWh9q/hEb21/tsG0Ow3nLcLBbyeEvDBKcfuXHqRwhCxf7FayDhG8VqE= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1;MWHPR1201MB0237;20:fHlP7qmgl1p9CXzHCsbhiyD/0iPxIk/q/6tPshtKuneNbv4itGvRsuxwAQ3R8/tzumlbUqufQiCVDCl2DiSwQ/JMlBcZ8894hq25KFQ8BBbf8taR3eNOp93MJMAvtci1E6ERIvSUvDfTjHYoW2+Ky6kqj6uUvK0WmEkBDQUh+2MsGb6zP6p2+pi9pC0ptAY3MxeHS+CIVR5d3qUSsX65SublZwGVoq5vS6ZE1SJQR+K0KQX2Rmo1ABGTLVLLFnQG X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 19 Sep 2017 01:33:26.2094 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR1201MB0237 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 2017-09-15 05:14 PM, Andrew Morton wrote: > On Mon, 28 Aug 2017 21:53:10 -0400 Felix Kuehling wrote: > >> This adds a statically sized closed hash table implementation with >> low memory and CPU overhead. The API is inspired by kfifo. >> >> Storing, retrieving and deleting data does not involve any dynamic >> memory management, which makes it ideal for use in interrupt context. >> Static memory usage per entry comprises a 32 or 64 bit hash key, two >> bits for occupancy tracking and the value size stored in the table. >> No list heads or pointers are needed. Therefore this data structure >> should be quite cache-friendly, too. >> >> It uses linear probing and lazy deletion. During lookups free space >> is reclaimed and entries relocated to speed up future lookups. > I haven't looked at the implementation (yet), but I'm wondering if you > have identified hash table users (or implementations) elsewhere in the > kernel which might be migrated to use this? If so, such conversions > can be used to determine/demonstrate the desirability of the patch. I haven't looked into this. I did a quick search for where hash tables are currently used in the kernel tree. But I'm not sufficiently familiar with the subsystems to easily decide which ones could benefit from my work. My implementation has some constraints because the hash table is not resizable (by design). I think it may be useful for some applications in drivers, where the amount of data in the hash table is limited by HW constraints. Data stored in the table should also be quite small. For larger data structures that need to be allocated with kmalloc, you may as well use hashtable or rhashtable. To see a performance impact, you'd need very frequent lookups. For now I've settled on checking the code into the amdgpu driver so I can make progress. If someone finds another application for it, it can be moved to lib/ easily. Regards,   Felix