From patchwork Tue May 15 16:00:43 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10401517 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 2159760284 for ; Tue, 15 May 2018 16:02:09 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0DB592811A for ; Tue, 15 May 2018 16:02:09 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 21A0B27F10; Tue, 15 May 2018 16:02:08 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, MAILING_LIST_MULTI, RCVD_IN_DNSWL_HI, T_DKIM_INVALID autolearn=unavailable version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 44842283BB for ; Tue, 15 May 2018 16:01:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753030AbeEOQAx (ORCPT ); Tue, 15 May 2018 12:00:53 -0400 Received: from bombadil.infradead.org ([198.137.202.133]:55476 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752539AbeEOQAt (ORCPT ); Tue, 15 May 2018 12:00:49 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=References:In-Reply-To:Message-Id: Date:Subject:Cc:To:From:Sender:Reply-To:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=iWlZoT50LKuj0bFUQ062XuWEl4P5i8EY0A2Z8Sq10YE=; b=rE5Li5P2WP4r7tmqZqLyQiKt6 xzG4MUUlr5RI2jSp+u93KDx6Ix3WyUEsRypfyEYQVIHKUbmYW7HR9UnwDwdzE5DymL8Qaz5YyNH7m ANYCOcIA5EzZtOcIlTAtdnbIzDB1+d+XeYaIIESWVdCwB1Smi9xkyRWqUI5CgenQu9Aph6vXq+ftX utzb8LVM4zezHQloRYyF2kJxYOXN5mz8ERqYvFJpeFHDOe+TAxI6jEA+cp4lA8aAs5fan9frpLPh7 6pKAdSf7usNP21iI6IoCXstPx85wOWCSa5ftcfvRSILKcYj6KRKMcs3u/K4ypvQsVzBQ/egPBRyE0 lSJLLUIHQ==; Received: from willy by bombadil.infradead.org with local (Exim 4.90_1 #2 (Red Hat Linux)) id 1fIcNc-00073h-TZ; Tue, 15 May 2018 16:00:48 +0000 From: Matthew Wilcox To: linux-kernel@vger.kernel.org, linux-scsi@vger.kernel.org, target-devel@vger.kernel.org, linux1394-devel@lists.sourceforge.net, linux-usb@vger.kernel.org, kvm@vger.kernel.org, virtualization@lists.linux-foundation.org, netdev@vger.kernel.org, Juergen Gross , qla2xxx-upstream@qlogic.com, Kent Overstreet , Jens Axboe Cc: Matthew Wilcox Subject: [PATCH 2/2] Remove percpu_ida Date: Tue, 15 May 2018 09:00:43 -0700 Message-Id: <20180515160043.27044-3-willy@infradead.org> X-Mailer: git-send-email 2.14.3 In-Reply-To: <20180515160043.27044-1-willy@infradead.org> References: <20180515160043.27044-1-willy@infradead.org> Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Matthew Wilcox With its one user gone, remove the library code. Signed-off-by: Matthew Wilcox --- include/linux/percpu_ida.h | 83 -------- lib/Makefile | 2 +- lib/percpu_ida.c | 391 ------------------------------------- 3 files changed, 1 insertion(+), 475 deletions(-) delete mode 100644 include/linux/percpu_ida.h delete mode 100644 lib/percpu_ida.c diff --git a/include/linux/percpu_ida.h b/include/linux/percpu_ida.h deleted file mode 100644 index 07d78e4653bc..000000000000 --- a/include/linux/percpu_ida.h +++ /dev/null @@ -1,83 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ -#ifndef __PERCPU_IDA_H__ -#define __PERCPU_IDA_H__ - -#include -#include -#include -#include -#include -#include -#include - -struct percpu_ida_cpu; - -struct percpu_ida { - /* - * number of tags available to be allocated, as passed to - * percpu_ida_init() - */ - unsigned nr_tags; - unsigned percpu_max_size; - unsigned percpu_batch_size; - - struct percpu_ida_cpu __percpu *tag_cpu; - - /* - * Bitmap of cpus that (may) have tags on their percpu freelists: - * steal_tags() uses this to decide when to steal tags, and which cpus - * to try stealing from. - * - * It's ok for a freelist to be empty when its bit is set - steal_tags() - * will just keep looking - but the bitmap _must_ be set whenever a - * percpu freelist does have tags. - */ - cpumask_t cpus_have_tags; - - struct { - spinlock_t lock; - /* - * When we go to steal tags from another cpu (see steal_tags()), - * we want to pick a cpu at random. Cycling through them every - * time we steal is a bit easier and more or less equivalent: - */ - unsigned cpu_last_stolen; - - /* For sleeping on allocation failure */ - wait_queue_head_t wait; - - /* - * Global freelist - it's a stack where nr_free points to the - * top - */ - unsigned nr_free; - unsigned *freelist; - } ____cacheline_aligned_in_smp; -}; - -/* - * Number of tags we move between the percpu freelist and the global freelist at - * a time - */ -#define IDA_DEFAULT_PCPU_BATCH_MOVE 32U -/* Max size of percpu freelist, */ -#define IDA_DEFAULT_PCPU_SIZE ((IDA_DEFAULT_PCPU_BATCH_MOVE * 3) / 2) - -int percpu_ida_alloc(struct percpu_ida *pool, int state); -void percpu_ida_free(struct percpu_ida *pool, unsigned tag); - -void percpu_ida_destroy(struct percpu_ida *pool); -int __percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags, - unsigned long max_size, unsigned long batch_size); -static inline int percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags) -{ - return __percpu_ida_init(pool, nr_tags, IDA_DEFAULT_PCPU_SIZE, - IDA_DEFAULT_PCPU_BATCH_MOVE); -} - -typedef int (*percpu_ida_cb)(unsigned, void *); -int percpu_ida_for_each_free(struct percpu_ida *pool, percpu_ida_cb fn, - void *data); - -unsigned percpu_ida_free_tags(struct percpu_ida *pool, int cpu); -#endif /* __PERCPU_IDA_H__ */ diff --git a/lib/Makefile b/lib/Makefile index ce20696d5a92..7626dece1d27 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -39,7 +39,7 @@ obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \ bust_spinlocks.o kasprintf.o bitmap.o scatterlist.o \ gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \ bsearch.o find_bit.o llist.o memweight.o kfifo.o \ - percpu-refcount.o percpu_ida.o rhashtable.o reciprocal_div.o \ + percpu-refcount.o rhashtable.o reciprocal_div.o \ once.o refcount.o usercopy.o errseq.o bucket_locks.o obj-$(CONFIG_STRING_SELFTEST) += test_string.o obj-y += string_helpers.o diff --git a/lib/percpu_ida.c b/lib/percpu_ida.c deleted file mode 100644 index 6016f1deb1f5..000000000000 --- a/lib/percpu_ida.c +++ /dev/null @@ -1,391 +0,0 @@ -/* - * Percpu IDA library - * - * Copyright (C) 2013 Datera, Inc. Kent Overstreet - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License as - * published by the Free Software Foundation; either version 2, or (at - * your option) any later version. - * - * This program is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - */ - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -struct percpu_ida_cpu { - /* - * Even though this is percpu, we need a lock for tag stealing by remote - * CPUs: - */ - spinlock_t lock; - - /* nr_free/freelist form a stack of free IDs */ - unsigned nr_free; - unsigned freelist[]; -}; - -static inline void move_tags(unsigned *dst, unsigned *dst_nr, - unsigned *src, unsigned *src_nr, - unsigned nr) -{ - *src_nr -= nr; - memcpy(dst + *dst_nr, src + *src_nr, sizeof(unsigned) * nr); - *dst_nr += nr; -} - -/* - * Try to steal tags from a remote cpu's percpu freelist. - * - * We first check how many percpu freelists have tags - * - * Then we iterate through the cpus until we find some tags - we don't attempt - * to find the "best" cpu to steal from, to keep cacheline bouncing to a - * minimum. - */ -static inline void steal_tags(struct percpu_ida *pool, - struct percpu_ida_cpu *tags) -{ - unsigned cpus_have_tags, cpu = pool->cpu_last_stolen; - struct percpu_ida_cpu *remote; - - for (cpus_have_tags = cpumask_weight(&pool->cpus_have_tags); - cpus_have_tags; cpus_have_tags--) { - cpu = cpumask_next(cpu, &pool->cpus_have_tags); - - if (cpu >= nr_cpu_ids) { - cpu = cpumask_first(&pool->cpus_have_tags); - if (cpu >= nr_cpu_ids) - BUG(); - } - - pool->cpu_last_stolen = cpu; - remote = per_cpu_ptr(pool->tag_cpu, cpu); - - cpumask_clear_cpu(cpu, &pool->cpus_have_tags); - - if (remote == tags) - continue; - - spin_lock(&remote->lock); - - if (remote->nr_free) { - memcpy(tags->freelist, - remote->freelist, - sizeof(unsigned) * remote->nr_free); - - tags->nr_free = remote->nr_free; - remote->nr_free = 0; - } - - spin_unlock(&remote->lock); - - if (tags->nr_free) - break; - } -} - -/* - * Pop up to IDA_PCPU_BATCH_MOVE IDs off the global freelist, and push them onto - * our percpu freelist: - */ -static inline void alloc_global_tags(struct percpu_ida *pool, - struct percpu_ida_cpu *tags) -{ - move_tags(tags->freelist, &tags->nr_free, - pool->freelist, &pool->nr_free, - min(pool->nr_free, pool->percpu_batch_size)); -} - -static inline unsigned alloc_local_tag(struct percpu_ida_cpu *tags) -{ - int tag = -ENOSPC; - - spin_lock(&tags->lock); - if (tags->nr_free) - tag = tags->freelist[--tags->nr_free]; - spin_unlock(&tags->lock); - - return tag; -} - -/** - * percpu_ida_alloc - allocate a tag - * @pool: pool to allocate from - * @state: task state for prepare_to_wait - * - * Returns a tag - an integer in the range [0..nr_tags) (passed to - * tag_pool_init()), or otherwise -ENOSPC on allocation failure. - * - * Safe to be called from interrupt context (assuming it isn't passed - * TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, of course). - * - * @gfp indicates whether or not to wait until a free id is available (it's not - * used for internal memory allocations); thus if passed __GFP_RECLAIM we may sleep - * however long it takes until another thread frees an id (same semantics as a - * mempool). - * - * Will not fail if passed TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE. - */ -int percpu_ida_alloc(struct percpu_ida *pool, int state) -{ - DEFINE_WAIT(wait); - struct percpu_ida_cpu *tags; - unsigned long flags; - int tag; - - local_irq_save(flags); - tags = this_cpu_ptr(pool->tag_cpu); - - /* Fastpath */ - tag = alloc_local_tag(tags); - if (likely(tag >= 0)) { - local_irq_restore(flags); - return tag; - } - - while (1) { - spin_lock(&pool->lock); - - /* - * prepare_to_wait() must come before steal_tags(), in case - * percpu_ida_free() on another cpu flips a bit in - * cpus_have_tags - * - * global lock held and irqs disabled, don't need percpu lock - */ - if (state != TASK_RUNNING) - prepare_to_wait(&pool->wait, &wait, state); - - if (!tags->nr_free) - alloc_global_tags(pool, tags); - if (!tags->nr_free) - steal_tags(pool, tags); - - if (tags->nr_free) { - tag = tags->freelist[--tags->nr_free]; - if (tags->nr_free) - cpumask_set_cpu(smp_processor_id(), - &pool->cpus_have_tags); - } - - spin_unlock(&pool->lock); - local_irq_restore(flags); - - if (tag >= 0 || state == TASK_RUNNING) - break; - - if (signal_pending_state(state, current)) { - tag = -ERESTARTSYS; - break; - } - - schedule(); - - local_irq_save(flags); - tags = this_cpu_ptr(pool->tag_cpu); - } - if (state != TASK_RUNNING) - finish_wait(&pool->wait, &wait); - - return tag; -} -EXPORT_SYMBOL_GPL(percpu_ida_alloc); - -/** - * percpu_ida_free - free a tag - * @pool: pool @tag was allocated from - * @tag: a tag previously allocated with percpu_ida_alloc() - * - * Safe to be called from interrupt context. - */ -void percpu_ida_free(struct percpu_ida *pool, unsigned tag) -{ - struct percpu_ida_cpu *tags; - unsigned long flags; - unsigned nr_free; - - BUG_ON(tag >= pool->nr_tags); - - local_irq_save(flags); - tags = this_cpu_ptr(pool->tag_cpu); - - spin_lock(&tags->lock); - tags->freelist[tags->nr_free++] = tag; - - nr_free = tags->nr_free; - spin_unlock(&tags->lock); - - if (nr_free == 1) { - cpumask_set_cpu(smp_processor_id(), - &pool->cpus_have_tags); - wake_up(&pool->wait); - } - - if (nr_free == pool->percpu_max_size) { - spin_lock(&pool->lock); - - /* - * Global lock held and irqs disabled, don't need percpu - * lock - */ - if (tags->nr_free == pool->percpu_max_size) { - move_tags(pool->freelist, &pool->nr_free, - tags->freelist, &tags->nr_free, - pool->percpu_batch_size); - - wake_up(&pool->wait); - } - spin_unlock(&pool->lock); - } - - local_irq_restore(flags); -} -EXPORT_SYMBOL_GPL(percpu_ida_free); - -/** - * percpu_ida_destroy - release a tag pool's resources - * @pool: pool to free - * - * Frees the resources allocated by percpu_ida_init(). - */ -void percpu_ida_destroy(struct percpu_ida *pool) -{ - free_percpu(pool->tag_cpu); - free_pages((unsigned long) pool->freelist, - get_order(pool->nr_tags * sizeof(unsigned))); -} -EXPORT_SYMBOL_GPL(percpu_ida_destroy); - -/** - * percpu_ida_init - initialize a percpu tag pool - * @pool: pool to initialize - * @nr_tags: number of tags that will be available for allocation - * - * Initializes @pool so that it can be used to allocate tags - integers in the - * range [0, nr_tags). Typically, they'll be used by driver code to refer to a - * preallocated array of tag structures. - * - * Allocation is percpu, but sharding is limited by nr_tags - for best - * performance, the workload should not span more cpus than nr_tags / 128. - */ -int __percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags, - unsigned long max_size, unsigned long batch_size) -{ - unsigned i, cpu, order; - - memset(pool, 0, sizeof(*pool)); - - init_waitqueue_head(&pool->wait); - spin_lock_init(&pool->lock); - pool->nr_tags = nr_tags; - pool->percpu_max_size = max_size; - pool->percpu_batch_size = batch_size; - - /* Guard against overflow */ - if (nr_tags > (unsigned) INT_MAX + 1) { - pr_err("percpu_ida_init(): nr_tags too large\n"); - return -EINVAL; - } - - order = get_order(nr_tags * sizeof(unsigned)); - pool->freelist = (void *) __get_free_pages(GFP_KERNEL, order); - if (!pool->freelist) - return -ENOMEM; - - for (i = 0; i < nr_tags; i++) - pool->freelist[i] = i; - - pool->nr_free = nr_tags; - - pool->tag_cpu = __alloc_percpu(sizeof(struct percpu_ida_cpu) + - pool->percpu_max_size * sizeof(unsigned), - sizeof(unsigned)); - if (!pool->tag_cpu) - goto err; - - for_each_possible_cpu(cpu) - spin_lock_init(&per_cpu_ptr(pool->tag_cpu, cpu)->lock); - - return 0; -err: - percpu_ida_destroy(pool); - return -ENOMEM; -} -EXPORT_SYMBOL_GPL(__percpu_ida_init); - -/** - * percpu_ida_for_each_free - iterate free ids of a pool - * @pool: pool to iterate - * @fn: interate callback function - * @data: parameter for @fn - * - * Note, this doesn't guarantee to iterate all free ids restrictly. Some free - * ids might be missed, some might be iterated duplicated, and some might - * be iterated and not free soon. - */ -int percpu_ida_for_each_free(struct percpu_ida *pool, percpu_ida_cb fn, - void *data) -{ - unsigned long flags; - struct percpu_ida_cpu *remote; - unsigned cpu, i, err = 0; - - local_irq_save(flags); - for_each_possible_cpu(cpu) { - remote = per_cpu_ptr(pool->tag_cpu, cpu); - spin_lock(&remote->lock); - for (i = 0; i < remote->nr_free; i++) { - err = fn(remote->freelist[i], data); - if (err) - break; - } - spin_unlock(&remote->lock); - if (err) - goto out; - } - - spin_lock(&pool->lock); - for (i = 0; i < pool->nr_free; i++) { - err = fn(pool->freelist[i], data); - if (err) - break; - } - spin_unlock(&pool->lock); -out: - local_irq_restore(flags); - return err; -} -EXPORT_SYMBOL_GPL(percpu_ida_for_each_free); - -/** - * percpu_ida_free_tags - return free tags number of a specific cpu or global pool - * @pool: pool related - * @cpu: specific cpu or global pool if @cpu == nr_cpu_ids - * - * Note: this just returns a snapshot of free tags number. - */ -unsigned percpu_ida_free_tags(struct percpu_ida *pool, int cpu) -{ - struct percpu_ida_cpu *remote; - if (cpu == nr_cpu_ids) - return pool->nr_free; - remote = per_cpu_ptr(pool->tag_cpu, cpu); - return remote->nr_free; -} -EXPORT_SYMBOL_GPL(percpu_ida_free_tags);