kernel/lib/percpu_ida.c

   1 /*
   2  * Percpu IDA library
   3  *
   4  * Copyright (C) 2013 Datera, Inc. Kent Overstreet
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as
   8  * published by the Free Software Foundation; either version 2, or (at
   9  * your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  */
  16
  17 #include <linux/bitmap.h>
  18 #include <linux/bitops.h>
  19 #include <linux/bug.h>
  20 #include <linux/err.h>
  21 #include <linux/export.h>
  22 #include <linux/init.h>
  23 #include <linux/kernel.h>
  24 #include <linux/percpu.h>
  25 #include <linux/sched.h>
  26 #include <linux/string.h>
  27 #include <linux/spinlock.h>
  28 #include <linux/percpu_ida.h>
  29 #include <linux/locallock.h>
  30
  31 static DEFINE_LOCAL_IRQ_LOCK(irq_off_lock);
  32
  33 struct percpu_ida_cpu {
  34         /*
  35          * Even though this is percpu, we need a lock for tag stealing by remote
  36          * CPUs:
  37          */
  38         spinlock_t                      lock;
  39
  40         /* nr_free/freelist form a stack of free IDs */
  41         unsigned                        nr_free;
  42         unsigned                        freelist[];
  43 };
  44
  45 static inline void move_tags(unsigned *dst, unsigned *dst_nr,
  46                              unsigned *src, unsigned *src_nr,
  47                              unsigned nr)
  48 {
  49         *src_nr -= nr;
  50         memcpy(dst + *dst_nr, src + *src_nr, sizeof(unsigned) * nr);
  51         *dst_nr += nr;
  52 }
  53
  54 /*
  55  * Try to steal tags from a remote cpu's percpu freelist.
  56  *
  57  * We first check how many percpu freelists have tags
  58  *
  59  * Then we iterate through the cpus until we find some tags - we don't attempt
  60  * to find the "best" cpu to steal from, to keep cacheline bouncing to a
  61  * minimum.
  62  */
  63 static inline void steal_tags(struct percpu_ida *pool,
  64                               struct percpu_ida_cpu *tags)
  65 {
  66         unsigned cpus_have_tags, cpu = pool->cpu_last_stolen;
  67         struct percpu_ida_cpu *remote;
  68
  69         for (cpus_have_tags = cpumask_weight(&pool->cpus_have_tags);
  70              cpus_have_tags; cpus_have_tags--) {
  71                 cpu = cpumask_next(cpu, &pool->cpus_have_tags);
  72
  73                 if (cpu >= nr_cpu_ids) {
  74                         cpu = cpumask_first(&pool->cpus_have_tags);
  75                         if (cpu >= nr_cpu_ids)
  76                                 BUG();
  77                 }
  78
  79                 pool->cpu_last_stolen = cpu;
  80                 remote = per_cpu_ptr(pool->tag_cpu, cpu);
  81
  82                 cpumask_clear_cpu(cpu, &pool->cpus_have_tags);
  83
  84                 if (remote == tags)
  85                         continue;
  86
  87                 spin_lock(&remote->lock);
  88
  89                 if (remote->nr_free) {
  90                         memcpy(tags->freelist,
  91                                remote->freelist,
  92                                sizeof(unsigned) * remote->nr_free);
  93
  94                         tags->nr_free = remote->nr_free;
  95                         remote->nr_free = 0;
  96                 }
  97
  98                 spin_unlock(&remote->lock);
  99
 100                 if (tags->nr_free)
 101                         break;
 102         }
 103 }
 104
 105 /*
 106  * Pop up to IDA_PCPU_BATCH_MOVE IDs off the global freelist, and push them onto
 107  * our percpu freelist:
 108  */
 109 static inline void alloc_global_tags(struct percpu_ida *pool,
 110                                      struct percpu_ida_cpu *tags)
 111 {
 112         move_tags(tags->freelist, &tags->nr_free,
 113                   pool->freelist, &pool->nr_free,
 114                   min(pool->nr_free, pool->percpu_batch_size));
 115 }
 116
 117 static inline unsigned alloc_local_tag(struct percpu_ida_cpu *tags)
 118 {
 119         int tag = -ENOSPC;
 120
 121         spin_lock(&tags->lock);
 122         if (tags->nr_free)
 123                 tag = tags->freelist[--tags->nr_free];
 124         spin_unlock(&tags->lock);
 125
 126         return tag;
 127 }
 128
 129 /**
 130  * percpu_ida_alloc - allocate a tag
 131  * @pool: pool to allocate from
 132  * @state: task state for prepare_to_wait
 133  *
 134  * Returns a tag - an integer in the range [0..nr_tags) (passed to
 135  * tag_pool_init()), or otherwise -ENOSPC on allocation failure.
 136  *
 137  * Safe to be called from interrupt context (assuming it isn't passed
 138  * TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, of course).
 139  *
 140  * @gfp indicates whether or not to wait until a free id is available (it's not
 141  * used for internal memory allocations); thus if passed __GFP_WAIT we may sleep
 142  * however long it takes until another thread frees an id (same semantics as a
 143  * mempool).
 144  *
 145  * Will not fail if passed TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE.
 146  */
 147 int percpu_ida_alloc(struct percpu_ida *pool, int state)
 148 {
 149         DEFINE_WAIT(wait);
 150         struct percpu_ida_cpu *tags;
 151         unsigned long flags;
 152         int tag;
 153
 154         local_lock_irqsave(irq_off_lock, flags);
 155         tags = this_cpu_ptr(pool->tag_cpu);
 156
 157         /* Fastpath */
 158         tag = alloc_local_tag(tags);
 159         if (likely(tag >= 0)) {
 160                 local_unlock_irqrestore(irq_off_lock, flags);
 161                 return tag;
 162         }
 163
 164         while (1) {
 165                 spin_lock(&pool->lock);
 166
 167                 /*
 168                  * prepare_to_wait() must come before steal_tags(), in case
 169                  * percpu_ida_free() on another cpu flips a bit in
 170                  * cpus_have_tags
 171                  *
 172                  * global lock held and irqs disabled, don't need percpu lock
 173                  */
 174                 if (state != TASK_RUNNING)
 175                         prepare_to_wait(&pool->wait, &wait, state);
 176
 177                 if (!tags->nr_free)
 178                         alloc_global_tags(pool, tags);
 179
 180                 if (!tags->nr_free)
 181                         steal_tags(pool, tags);
 182
 183                 if (tags->nr_free) {
 184                         tag = tags->freelist[--tags->nr_free];
 185                         if (tags->nr_free)
 186                                 cpumask_set_cpu(smp_processor_id(),
 187                                                 &pool->cpus_have_tags);
 188                 }
 189
 190                 spin_unlock(&pool->lock);
 191                 local_unlock_irqrestore(irq_off_lock, flags);
 192
 193                 if (tag >= 0 || state == TASK_RUNNING)
 194                         break;
 195
 196                 if (signal_pending_state(state, current)) {
 197                         tag = -ERESTARTSYS;
 198                         break;
 199                 }
 200
 201                 schedule();
 202
 203                 local_lock_irqsave(irq_off_lock, flags);
 204                 tags = this_cpu_ptr(pool->tag_cpu);
 205         }
 206         if (state != TASK_RUNNING)
 207                 finish_wait(&pool->wait, &wait);
 208
 209         return tag;
 210 }
 211 EXPORT_SYMBOL_GPL(percpu_ida_alloc);
 212
 213 /**
 214  * percpu_ida_free - free a tag
 215  * @pool: pool @tag was allocated from
 216  * @tag: a tag previously allocated with percpu_ida_alloc()
 217  *
 218  * Safe to be called from interrupt context.
 219  */
 220 void percpu_ida_free(struct percpu_ida *pool, unsigned tag)
 221 {
 222         struct percpu_ida_cpu *tags;
 223         unsigned long flags;
 224         unsigned nr_free;
 225
 226         BUG_ON(tag >= pool->nr_tags);
 227
 228         local_lock_irqsave(irq_off_lock, flags);
 229         tags = this_cpu_ptr(pool->tag_cpu);
 230
 231         spin_lock(&tags->lock);
 232         tags->freelist[tags->nr_free++] = tag;
 233
 234         nr_free = tags->nr_free;
 235         spin_unlock(&tags->lock);
 236
 237         if (nr_free == 1) {
 238                 cpumask_set_cpu(smp_processor_id(),
 239                                 &pool->cpus_have_tags);
 240                 wake_up(&pool->wait);
 241         }
 242
 243         if (nr_free == pool->percpu_max_size) {
 244                 spin_lock(&pool->lock);
 245
 246                 /*
 247                  * Global lock held and irqs disabled, don't need percpu
 248                  * lock
 249                  */
 250                 if (tags->nr_free == pool->percpu_max_size) {
 251                         move_tags(pool->freelist, &pool->nr_free,
 252                                   tags->freelist, &tags->nr_free,
 253                                   pool->percpu_batch_size);
 254
 255                         wake_up(&pool->wait);
 256                 }
 257                 spin_unlock(&pool->lock);
 258         }
 259
 260         local_unlock_irqrestore(irq_off_lock, flags);
 261 }
 262 EXPORT_SYMBOL_GPL(percpu_ida_free);
 263
 264 /**
 265  * percpu_ida_destroy - release a tag pool's resources
 266  * @pool: pool to free
 267  *
 268  * Frees the resources allocated by percpu_ida_init().
 269  */
 270 void percpu_ida_destroy(struct percpu_ida *pool)
 271 {
 272         free_percpu(pool->tag_cpu);
 273         free_pages((unsigned long) pool->freelist,
 274                    get_order(pool->nr_tags * sizeof(unsigned)));
 275 }
 276 EXPORT_SYMBOL_GPL(percpu_ida_destroy);
 277
 278 /**
 279  * percpu_ida_init - initialize a percpu tag pool
 280  * @pool: pool to initialize
 281  * @nr_tags: number of tags that will be available for allocation
 282  *
 283  * Initializes @pool so that it can be used to allocate tags - integers in the
 284  * range [0, nr_tags). Typically, they'll be used by driver code to refer to a
 285  * preallocated array of tag structures.
 286  *
 287  * Allocation is percpu, but sharding is limited by nr_tags - for best
 288  * performance, the workload should not span more cpus than nr_tags / 128.
 289  */
 290 int __percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags,
 291         unsigned long max_size, unsigned long batch_size)
 292 {
 293         unsigned i, cpu, order;
 294
 295         memset(pool, 0, sizeof(*pool));
 296
 297         init_waitqueue_head(&pool->wait);
 298         spin_lock_init(&pool->lock);
 299         pool->nr_tags = nr_tags;
 300         pool->percpu_max_size = max_size;
 301         pool->percpu_batch_size = batch_size;
 302
 303         /* Guard against overflow */
 304         if (nr_tags > (unsigned) INT_MAX + 1) {
 305                 pr_err("percpu_ida_init(): nr_tags too large\n");
 306                 return -EINVAL;
 307         }
 308
 309         order = get_order(nr_tags * sizeof(unsigned));
 310         pool->freelist = (void *) __get_free_pages(GFP_KERNEL, order);
 311         if (!pool->freelist)
 312                 return -ENOMEM;
 313
 314         for (i = 0; i < nr_tags; i++)
 315                 pool->freelist[i] = i;
 316
 317         pool->nr_free = nr_tags;
 318
 319         pool->tag_cpu = __alloc_percpu(sizeof(struct percpu_ida_cpu) +
 320                                        pool->percpu_max_size * sizeof(unsigned),
 321                                        sizeof(unsigned));
 322         if (!pool->tag_cpu)
 323                 goto err;
 324
 325         for_each_possible_cpu(cpu)
 326                 spin_lock_init(&per_cpu_ptr(pool->tag_cpu, cpu)->lock);
 327
 328         return 0;
 329 err:
 330         percpu_ida_destroy(pool);
 331         return -ENOMEM;
 332 }
 333 EXPORT_SYMBOL_GPL(__percpu_ida_init);
 334
 335 /**
 336  * percpu_ida_for_each_free - iterate free ids of a pool
 337  * @pool: pool to iterate
 338  * @fn: interate callback function
 339  * @data: parameter for @fn
 340  *
 341  * Note, this doesn't guarantee to iterate all free ids restrictly. Some free
 342  * ids might be missed, some might be iterated duplicated, and some might
 343  * be iterated and not free soon.
 344  */
 345 int percpu_ida_for_each_free(struct percpu_ida *pool, percpu_ida_cb fn,
 346         void *data)
 347 {
 348         unsigned long flags;
 349         struct percpu_ida_cpu *remote;
 350         unsigned cpu, i, err = 0;
 351
 352         local_lock_irqsave(irq_off_lock, flags);
 353         for_each_possible_cpu(cpu) {
 354                 remote = per_cpu_ptr(pool->tag_cpu, cpu);
 355                 spin_lock(&remote->lock);
 356                 for (i = 0; i < remote->nr_free; i++) {
 357                         err = fn(remote->freelist[i], data);
 358                         if (err)
 359                                 break;
 360                 }
 361                 spin_unlock(&remote->lock);
 362                 if (err)
 363                         goto out;
 364         }
 365
 366         spin_lock(&pool->lock);
 367         for (i = 0; i < pool->nr_free; i++) {
 368                 err = fn(pool->freelist[i], data);
 369                 if (err)
 370                         break;
 371         }
 372         spin_unlock(&pool->lock);
 373 out:
 374         local_unlock_irqrestore(irq_off_lock, flags);
 375         return err;
 376 }
 377 EXPORT_SYMBOL_GPL(percpu_ida_for_each_free);
 378
 379 /**
 380  * percpu_ida_free_tags - return free tags number of a specific cpu or global pool
 381  * @pool: pool related
 382  * @cpu: specific cpu or global pool if @cpu == nr_cpu_ids
 383  *
 384  * Note: this just returns a snapshot of free tags number.
 385  */
 386 unsigned percpu_ida_free_tags(struct percpu_ida *pool, int cpu)
 387 {
 388         struct percpu_ida_cpu *remote;
 389         if (cpu == nr_cpu_ids)
 390                 return pool->nr_free;
 391         remote = per_cpu_ptr(pool->tag_cpu, cpu);
 392         return remote->nr_free;
 393 }
 394 EXPORT_SYMBOL_GPL(percpu_ida_free_tags);