From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
        id S1751919AbdIOVO6 (ORCPT <rfc822;w@1wt.eu>);
        Fri, 15 Sep 2017 17:14:58 -0400
Received: from mail.linuxfoundation.org ([140.211.169.12]:59932 "EHLO
        mail.linuxfoundation.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
        with ESMTP id S1751894AbdIOVO5 (ORCPT
        <rfc822;linux-kernel@vger.kernel.org>);
        Fri, 15 Sep 2017 17:14:57 -0400
Date: Fri, 15 Sep 2017 14:14:56 -0700
From: Andrew Morton <akpm@linux-foundation.org>
To: Felix Kuehling <Felix.Kuehling@amd.com>
Cc: linux-kernel@vger.kernel.org, amd-gfx@lists.freedesktop.org
Subject: Re: [PATCH] lib: Closed hash table with low overhead
Message-Id: <20170915141456.4382d7ffae7ec8a9a86c8cf9@linux-foundation.org>
In-Reply-To: <1503971590-15963-1-git-send-email-Felix.Kuehling@amd.com>
References: <1503971590-15963-1-git-send-email-Felix.Kuehling@amd.com>
X-Mailer: Sylpheed 3.4.1 (GTK+ 2.24.23; x86_64-pc-linux-gnu)
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On Mon, 28 Aug 2017 21:53:10 -0400 Felix Kuehling <Felix.Kuehling@amd.com> 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.