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