From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-1.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,HK_RANDOM_FROM,MAILING_LIST_MULTI,SPF_HELO_NONE, SPF_PASS autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D55B7C433F5 for ; Tue, 21 Sep 2021 15:42:47 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 87D5B61168 for ; Tue, 21 Sep 2021 15:42:47 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.1 mail.kernel.org 87D5B61168 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=kvack.org Received: by kanga.kvack.org (Postfix) id C960B940010; Tue, 21 Sep 2021 11:42:46 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C459D940007; Tue, 21 Sep 2021 11:42:46 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B33ED940010; Tue, 21 Sep 2021 11:42:46 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0112.hostedemail.com [216.40.44.112]) by kanga.kvack.org (Postfix) with ESMTP id A1592940007 for ; Tue, 21 Sep 2021 11:42:46 -0400 (EDT) Received: from smtpin01.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 4C0532D39A for ; Tue, 21 Sep 2021 15:42:46 +0000 (UTC) X-FDA: 78611998332.01.C257B4B Received: from mail-pj1-f42.google.com (mail-pj1-f42.google.com [209.85.216.42]) by imf15.hostedemail.com (Postfix) with ESMTP id 155AED000097 for ; Tue, 21 Sep 2021 15:42:45 +0000 (UTC) Received: by mail-pj1-f42.google.com with SMTP id me1so6014469pjb.4 for ; Tue, 21 Sep 2021 08:42:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=RD5aX+bq0mWaigsgwff4LifiFIskfGBYOuz23IRmF4A=; b=gQysE9fy9UdDCPFaMP9zJNGweHy7ylFyDDUJqj0hCp6Syl8h4CQSjjBIJ5X2PhUdnL bOJLbvXVF1dZZScDOJKeXVDV4okYScgUR4FjIDhVbjMqZ+O5RG2MyTEjwHjpkNfLLHfM aJAIWyWct1v/cLXuCv0Qzbzy0jZzPO6SVWANWrDXS29VPpKgm+M5ueXm/OaKypKWo5nC FgLjm2nHB7V9voFQuIyN/A0/6wfxrnlgDRESguvuXgG0bOfgXnEAotuz3ma+9fBgm5z0 shrcwHRe3VeWIRCYwhXKi+vJlgD4HxrXdAoNQNznain0ZjBHHU0p1J6EUyETbz4oZozs KOjQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=RD5aX+bq0mWaigsgwff4LifiFIskfGBYOuz23IRmF4A=; b=8GJQMrTffZFCg1gvjhDPalfrw/RouCs3vardT3joxebzrNjrefvkHD7lroBZDp4koh sXBtKp2Leww0Fqz5jO64MPWTaE6CjT/wpgYeqrkD2T0zMDzX8Earmjh3sdX2SlpT5VY/ aKgt2xSLOALSYWzw3jt8wr6G+Ggpitt9K3cZQniBhiSAJHAVDlOCes8CSv16CIqmx3r0 i3xvz1ZyJseOmiPULw7h5kRh2av38mFgWlncaD9chxoaBe8+VSxLvuNu1O9xkoah/4i9 hfk2R/LOCHuDsd7hPLqlSowRMVky+vo0nHp3mpSzfgOQwUOc6XInX6hOcr9Za0Cod603 nc+g== X-Gm-Message-State: AOAM532YzqzGRlD35WOwo4TW0BDje+5vRT83UhwEmX5KT87MdZxzOt68 AycBrW9Fp9ks2l8OEjVYD+w= X-Google-Smtp-Source: ABdhPJx/Zmb6zD2WZ4KC4j4SUn/d8h/e2zioznqSPJAtibgwO8DI4PddxHOSmQdfF8LHqBQbnbl9MQ== X-Received: by 2002:a17:903:102:b0:13a:66a8:f28 with SMTP id y2-20020a170903010200b0013a66a80f28mr28067530plc.62.1632238964906; Tue, 21 Sep 2021 08:42:44 -0700 (PDT) Received: from kvm.asia-northeast3-a.c.our-ratio-313919.internal (252.229.64.34.bc.googleusercontent.com. [34.64.229.252]) by smtp.gmail.com with ESMTPSA id y6sm17819188pfb.64.2021.09.21.08.42.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 21 Sep 2021 08:42:44 -0700 (PDT) Date: Tue, 21 Sep 2021 15:42:39 +0000 From: Hyeonggon Yoo <42.hyeyoo@gmail.com> To: Matthew Wilcox Cc: linux-mm@kvack.org, Christoph Lameter , Pekka Enberg , David Rientjes , Joonsoo Kim , Andrew Morton , Vlastimil Babka , linux-kernel@vger.kernel.org, Jens Axboe , John Garry , linux-block@vger.kernel.org, netdev@vger.kernel.org Subject: Re: [RFC v2 PATCH] mm, sl[au]b: Introduce lockless cache Message-ID: <20210921154239.GA5092@kvm.asia-northeast3-a.c.our-ratio-313919.internal> References: <20210920154816.31832-1-42.hyeyoo@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 155AED000097 Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=gQysE9fy; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf15.hostedemail.com: domain of 42.hyeyoo@gmail.com designates 209.85.216.42 as permitted sender) smtp.mailfrom=42.hyeyoo@gmail.com X-Stat-Signature: u9npgby1arrkursspaux9nnyk6yxdomy X-HE-Tag: 1632238965-657618 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Mon, Sep 20, 2021 at 11:01:16PM +0100, Matthew Wilcox wrote: > On Mon, Sep 20, 2021 at 03:48:16PM +0000, Hyeonggon Yoo wrote: > > +#define KMEM_LOCKLESS_CACHE_QUEUE_SIZE 64 > > I would suggest that, to be nice to the percpu allocator, this be > one less than 2^n. I think first we need to discuss if KMEM_LOCKLESS_CACHE_QUEUE_SIZE will be okay with constant, or per kmem_cache size, or global boot parameter. But even before that, we need to discuss how to manage magazine. because that affect on what KMEM_LOCKLESS_CACHE_QUEUE_SIZE will be. > > +struct kmem_lockless_cache { > > + void *queue[KMEM_LOCKLESS_CACHE_QUEUE_SIZE]; > > + unsigned int size; > > +}; > > I would also suggest that 'size' be first as it is going to be accessed > every time, and then there's a reasonable chance that queue[size - 1] will > be in the same cacheline. CPUs will tend to handle that better. That looks good to me, as you said there's chance that 'size' and some of queue's elements (hopefully queue[size - 1]) are in same cacheline. Plus, in v2 I didn't consider cache line when determining position of kmem_lockless_cache in kmem_cache, I think we need to reconsider this too. > > +/** > > + * kmem_cache_alloc_cached - try to allocate from cache without lock > > + * @s: slab cache > > + * @flags: SLAB flags > > + * > > + * Try to allocate from cache without lock. If fails, fill the lockless cache > > + * using bulk alloc API > > + * > > + * Be sure that there's no race condition. > > + * Must create slab cache with SLAB_LOCKLESS_CACHE flag to use this function. > > + * > > + * Return: a pointer to free object on allocation success, NULL on failure. > > + */ > > +void *kmem_cache_alloc_cached(struct kmem_cache *s, gfp_t gfpflags) > > +{ > > + struct kmem_lockless_cache *cache = this_cpu_ptr(s->cache); > > + > > + BUG_ON(!(s->flags & SLAB_LOCKLESS_CACHE)); > > + > > + if (cache->size) /* fastpath without lock */ > > + return cache->queue[--cache->size]; > > + > > + /* slowpath */ > > + cache->size = kmem_cache_alloc_bulk(s, gfpflags, > > + KMEM_LOCKLESS_CACHE_QUEUE_SIZE, cache->queue); > > Go back to the Bonwick paper and look at the magazine section again. > You have to allocate _half_ the size of the queue, otherwise you get > into pathological situations where you start to free and allocate > every time. I want to ask you where idea of allocating 'half' the size of queue came from. the paper you sent does not work with single queue(magazine). Instead, it manages pool of magazines. And after reading the paper, I see managing pool of magazine (where M is an boot parameter) is valid approach to reduce hitting slowpath. Thanks, Hyeonggon Yoo > > +void kmem_cache_free_cached(struct kmem_cache *s, void *p) > > +{ > > + struct kmem_lockless_cache *cache = this_cpu_ptr(s->cache); > > + > > + BUG_ON(!(s->flags & SLAB_LOCKLESS_CACHE)); > > + > > + /* Is there better way to do this? */ > > + if (cache->size == KMEM_LOCKLESS_CACHE_QUEUE_SIZE) > > + kmem_cache_free(s, cache->queue[--cache->size]); > > Yes. > > if (cache->size == KMEM_LOCKLESS_CACHE_QUEUE_SIZE) { > kmem_cache_free_bulk(s, KMEM_LOCKLESS_CACHE_QUEUE_SIZE / 2, > &cache->queue[KMEM_LOCKLESS_CACHE_QUEUE_SIZE / 2)); > cache->size = KMEM_LOCKLESS_CACHE_QUEUE_SIZE / 2; > > (check the maths on that; it might have some off-by-one)