← Back to branch summary

~ubuntu-branches/ubuntu/trusty/linux-armadaxp/trusty

« back to all changes in this revision

Viewing changes to lib/genalloc.c

  • Committer: Package Import Robot
  • Author(s): Michael Casadevall, Bryan Wu, Dann Frazier, Michael Casadeall
  • Date: 2012-03-10 15:00:54 UTC
  • mfrom: (1.1.1)
  • Revision ID: package-import@ubuntu.com-20120310150054-flugb39zon8vvgwe
Tags: 3.2.0-1600.1
[ Bryan Wu ]
* UBUNTU: import debian/debian.env and debian.armadaxp

[ Dann Frazier ]
* ARM: Armada XP: remove trailing '/' in dirnames in mvRules.mk

[ Michael Casadeall ]
* tools: add some tools for Marvell Armada XP processor
* kernel: timer tick hacking from Marvell
* kernel: Sheeva Errata: add delay on Sheeva when powering down
* net: add Marvell NFP netfilter
* net: socket and skb modifications made by Marvell
* miscdevice: add minor IDs for some Marvell Armada drivers
* fs: introduce memory pool for splice()
* video: EDID detection updates from Marvell Armada XP patchset
* video: backlight: add Marvell Dove LCD backlight driver
* video: display: add THS8200 display driver
* video: framebuffer: add Marvell Dove and Armada XP processor onchip LCD controller driver
* usbtest: add Interrupt transfer testing by Marvell Armada XP code
* usb: ehci: add support for Marvell EHCI controler
* tty/serial: 8250: add support for Marvell Armada XP processor and DeviceTree work
* rtc: add support for Marvell Armada XP onchip RTC controller
* net: pppoe: add Marvell ethernet NFP hook in PPPoE networking driver
* mtd: nand: add support for Marvell Armada XP Nand Flash Controller
* mtd: maps: add Marvell Armada XP specific map driver
* mmc: add support for Marvell Armada XP MMC/SD host controller
* i2c: add support for Marvell Armada XP onchip i2c bus controller
* hwmon: add Kconfig option for Armada XP onchip thermal sensor driver
* dmaengine: add Net DMA support for splice and update Marvell XOR DMA engine driver
* ata: add support for Marvell Armada XP SATA controller and update some quirks
* ARM: add Marvell Armada XP machine to mach-types
* ARM: oprofile: add support for Marvell PJ4B core
* ARM: mm: more ARMv6 switches for Marvell Armada XP
* ARM: remove static declaration to allow compilation
* ARM: alignment access fault trick
* ARM: mm: skip some fault fixing when run on NONE SMP ARMv6 mode during early abort event
* ARM: mm: add Marvell Sheeva CPU Architecture for PJ4B
* ARM: introduce optimized copy operation for Marvell Armada XP
* ARM: SAUCE: hardware breakpoint trick for Marvell Armada XP
* ARM: big endian and little endian tricks for Marvell Armada XP
* ARM: SAUCE: Add Marvell Armada XP build rules to arch/arm/kernel/Makefile
* ARM: vfp: add special handling for Marvell Armada XP
* ARM: add support for Marvell U-Boot
* ARM: add mv_controller_num for ARM PCI drivers
* ARM: add support for local PMUs, general SMP tweaks and cache flushing
* ARM: add Marvell device identifies in glue-proc.h
* ARM: add IPC driver support for Marvell platforms
* ARM: add DMA mapping for Marvell platforms
* ARM: add Sheeva errata and PJ4B code for booting
* ARM: update Kconfig and Makefile to include Marvell Armada XP platforms
* ARM: Armada XP: import LSP from Marvell for Armada XP 3.2 kernel enablement

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/genalloc.c
1
1
/*
2
 
 * Basic general purpose allocator for managing special purpose memory
3
 
 * not managed by the regular kmalloc/kfree interface.
4
 
 * Uses for this includes on-device special memory, uncached memory
5
 
 * etc.
 
2
 * Basic general purpose allocator for managing special purpose
 
3
 * memory, for example, memory that is not managed by the regular
 
4
 * kmalloc/kfree interface.  Uses for this includes on-device special
 
5
 * memory, uncached memory etc.
 
6
 *
 
7
 * It is safe to use the allocator in NMI handlers and other special
 
8
 * unblockable contexts that could otherwise deadlock on locks.  This
 
9
 * is implemented by using atomic operations and retries on any
 
10
 * conflicts.  The disadvantage is that there may be livelocks in
 
11
 * extreme cases.  For better scalability, one allocator can be used
 
12
 * for each CPU.
 
13
 *
 
14
 * The lockless operation only works if there is enough memory
 
15
 * available.  If new memory is added to the pool a lock has to be
 
16
 * still taken.  So any user relying on locklessness has to ensure
 
17
 * that sufficient memory is preallocated.
 
18
 *
 
19
 * The basic atomic operation of this allocator is cmpxchg on long.
 
20
 * On architectures that don't have NMI-safe cmpxchg implementation,
 
21
 * the allocator can NOT be used in NMI handler.  So code uses the
 
22
 * allocator in NMI handler should depend on
 
23
 * CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
6
24
 *
7
25
 * Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org>
8
26
 *
13
31
#include <linux/slab.h>
14
32
#include <linux/module.h>
15
33
#include <linux/bitmap.h>
 
34
#include <linux/rculist.h>
 
35
#include <linux/interrupt.h>
16
36
#include <linux/genalloc.h>
17
37
 
 
38
static int set_bits_ll(unsigned long *addr, unsigned long mask_to_set)
 
39
{
 
40
        unsigned long val, nval;
 
41
 
 
42
        nval = *addr;
 
43
        do {
 
44
                val = nval;
 
45
                if (val & mask_to_set)
 
46
                        return -EBUSY;
 
47
                cpu_relax();
 
48
        } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val);
 
49
 
 
50
        return 0;
 
51
}
 
52
 
 
53
static int clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear)
 
54
{
 
55
        unsigned long val, nval;
 
56
 
 
57
        nval = *addr;
 
58
        do {
 
59
                val = nval;
 
60
                if ((val & mask_to_clear) != mask_to_clear)
 
61
                        return -EBUSY;
 
62
                cpu_relax();
 
63
        } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val);
 
64
 
 
65
        return 0;
 
66
}
 
67
 
 
68
/*
 
69
 * bitmap_set_ll - set the specified number of bits at the specified position
 
70
 * @map: pointer to a bitmap
 
71
 * @start: a bit position in @map
 
72
 * @nr: number of bits to set
 
73
 *
 
74
 * Set @nr bits start from @start in @map lock-lessly. Several users
 
75
 * can set/clear the same bitmap simultaneously without lock. If two
 
76
 * users set the same bit, one user will return remain bits, otherwise
 
77
 * return 0.
 
78
 */
 
79
static int bitmap_set_ll(unsigned long *map, int start, int nr)
 
80
{
 
81
        unsigned long *p = map + BIT_WORD(start);
 
82
        const int size = start + nr;
 
83
        int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
 
84
        unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 
85
 
 
86
        while (nr - bits_to_set >= 0) {
 
87
                if (set_bits_ll(p, mask_to_set))
 
88
                        return nr;
 
89
                nr -= bits_to_set;
 
90
                bits_to_set = BITS_PER_LONG;
 
91
                mask_to_set = ~0UL;
 
92
                p++;
 
93
        }
 
94
        if (nr) {
 
95
                mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 
96
                if (set_bits_ll(p, mask_to_set))
 
97
                        return nr;
 
98
        }
 
99
 
 
100
        return 0;
 
101
}
 
102
 
 
103
/*
 
104
 * bitmap_clear_ll - clear the specified number of bits at the specified position
 
105
 * @map: pointer to a bitmap
 
106
 * @start: a bit position in @map
 
107
 * @nr: number of bits to set
 
108
 *
 
109
 * Clear @nr bits start from @start in @map lock-lessly. Several users
 
110
 * can set/clear the same bitmap simultaneously without lock. If two
 
111
 * users clear the same bit, one user will return remain bits,
 
112
 * otherwise return 0.
 
113
 */
 
114
static int bitmap_clear_ll(unsigned long *map, int start, int nr)
 
115
{
 
116
        unsigned long *p = map + BIT_WORD(start);
 
117
        const int size = start + nr;
 
118
        int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 
119
        unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 
120
 
 
121
        while (nr - bits_to_clear >= 0) {
 
122
                if (clear_bits_ll(p, mask_to_clear))
 
123
                        return nr;
 
124
                nr -= bits_to_clear;
 
125
                bits_to_clear = BITS_PER_LONG;
 
126
                mask_to_clear = ~0UL;
 
127
                p++;
 
128
        }
 
129
        if (nr) {
 
130
                mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 
131
                if (clear_bits_ll(p, mask_to_clear))
 
132
                        return nr;
 
133
        }
 
134
 
 
135
        return 0;
 
136
}
18
137
 
19
138
/**
20
139
 * gen_pool_create - create a new special memory pool
30
149
 
31
150
        pool = kmalloc_node(sizeof(struct gen_pool), GFP_KERNEL, nid);
32
151
        if (pool != NULL) {
33
 
                rwlock_init(&pool->lock);
 
152
                spin_lock_init(&pool->lock);
34
153
                INIT_LIST_HEAD(&pool->chunks);
35
154
                pool->min_alloc_order = min_alloc_order;
36
155
        }
63
182
        if (unlikely(chunk == NULL))
64
183
                return -ENOMEM;
65
184
 
66
 
        spin_lock_init(&chunk->lock);
67
185
        chunk->phys_addr = phys;
68
186
        chunk->start_addr = virt;
69
187
        chunk->end_addr = virt + size;
 
188
        atomic_set(&chunk->avail, size);
70
189
 
71
 
        write_lock(&pool->lock);
72
 
        list_add(&chunk->next_chunk, &pool->chunks);
73
 
        write_unlock(&pool->lock);
 
190
        spin_lock(&pool->lock);
 
191
        list_add_rcu(&chunk->next_chunk, &pool->chunks);
 
192
        spin_unlock(&pool->lock);
74
193
 
75
194
        return 0;
76
195
}
85
204
 */
86
205
phys_addr_t gen_pool_virt_to_phys(struct gen_pool *pool, unsigned long addr)
87
206
{
88
 
        struct list_head *_chunk;
89
207
        struct gen_pool_chunk *chunk;
90
 
 
91
 
        read_lock(&pool->lock);
92
 
        list_for_each(_chunk, &pool->chunks) {
93
 
                chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
94
 
 
95
 
                if (addr >= chunk->start_addr && addr < chunk->end_addr)
96
 
                        return chunk->phys_addr + addr - chunk->start_addr;
 
208
        phys_addr_t paddr = -1;
 
209
 
 
210
        rcu_read_lock();
 
211
        list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
 
212
                if (addr >= chunk->start_addr && addr < chunk->end_addr) {
 
213
                        paddr = chunk->phys_addr + (addr - chunk->start_addr);
 
214
                        break;
 
215
                }
97
216
        }
98
 
        read_unlock(&pool->lock);
 
217
        rcu_read_unlock();
99
218
 
100
 
        return -1;
 
219
        return paddr;
101
220
}
102
221
EXPORT_SYMBOL(gen_pool_virt_to_phys);
103
222
 
115
234
        int order = pool->min_alloc_order;
116
235
        int bit, end_bit;
117
236
 
118
 
 
119
237
        list_for_each_safe(_chunk, _next_chunk, &pool->chunks) {
120
238
                chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
121
239
                list_del(&chunk->next_chunk);
137
255
 * @size: number of bytes to allocate from the pool
138
256
 *
139
257
 * Allocate the requested number of bytes from the specified pool.
140
 
 * Uses a first-fit algorithm.
 
258
 * Uses a first-fit algorithm. Can not be used in NMI handler on
 
259
 * architectures without NMI-safe cmpxchg implementation.
141
260
 */
142
261
unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
143
262
{
144
 
        struct list_head *_chunk;
145
263
        struct gen_pool_chunk *chunk;
146
 
        unsigned long addr, flags;
 
264
        unsigned long addr = 0;
147
265
        int order = pool->min_alloc_order;
148
 
        int nbits, start_bit, end_bit;
 
266
        int nbits, start_bit = 0, end_bit, remain;
 
267
 
 
268
#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
 
269
        BUG_ON(in_nmi());
 
270
#endif
149
271
 
150
272
        if (size == 0)
151
273
                return 0;
152
274
 
153
275
        nbits = (size + (1UL << order) - 1) >> order;
154
 
 
155
 
        read_lock(&pool->lock);
156
 
        list_for_each(_chunk, &pool->chunks) {
157
 
                chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
 
276
        rcu_read_lock();
 
277
        list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
 
278
                if (size > atomic_read(&chunk->avail))
 
279
                        continue;
158
280
 
159
281
                end_bit = (chunk->end_addr - chunk->start_addr) >> order;
160
 
 
161
 
                spin_lock_irqsave(&chunk->lock, flags);
162
 
                start_bit = bitmap_find_next_zero_area(chunk->bits, end_bit, 0,
163
 
                                                nbits, 0);
164
 
                if (start_bit >= end_bit) {
165
 
                        spin_unlock_irqrestore(&chunk->lock, flags);
 
282
retry:
 
283
                start_bit = bitmap_find_next_zero_area(chunk->bits, end_bit,
 
284
                                                       start_bit, nbits, 0);
 
285
                if (start_bit >= end_bit)
166
286
                        continue;
 
287
                remain = bitmap_set_ll(chunk->bits, start_bit, nbits);
 
288
                if (remain) {
 
289
                        remain = bitmap_clear_ll(chunk->bits, start_bit,
 
290
                                                 nbits - remain);
 
291
                        BUG_ON(remain);
 
292
                        goto retry;
167
293
                }
168
294
 
169
295
                addr = chunk->start_addr + ((unsigned long)start_bit << order);
170
 
 
171
 
                bitmap_set(chunk->bits, start_bit, nbits);
172
 
                spin_unlock_irqrestore(&chunk->lock, flags);
173
 
                read_unlock(&pool->lock);
174
 
                return addr;
 
296
                size = nbits << order;
 
297
                atomic_sub(size, &chunk->avail);
 
298
                break;
175
299
        }
176
 
        read_unlock(&pool->lock);
177
 
        return 0;
 
300
        rcu_read_unlock();
 
301
        return addr;
178
302
}
179
303
EXPORT_SYMBOL(gen_pool_alloc);
180
304
 
184
308
 * @addr: starting address of memory to free back to pool
185
309
 * @size: size in bytes of memory to free
186
310
 *
187
 
 * Free previously allocated special memory back to the specified pool.
 
311
 * Free previously allocated special memory back to the specified
 
312
 * pool.  Can not be used in NMI handler on architectures without
 
313
 * NMI-safe cmpxchg implementation.
188
314
 */
189
315
void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size)
190
316
{
191
 
        struct list_head *_chunk;
192
317
        struct gen_pool_chunk *chunk;
193
 
        unsigned long flags;
194
318
        int order = pool->min_alloc_order;
195
 
        int bit, nbits;
 
319
        int start_bit, nbits, remain;
 
320
 
 
321
#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
 
322
        BUG_ON(in_nmi());
 
323
#endif
196
324
 
197
325
        nbits = (size + (1UL << order) - 1) >> order;
198
 
 
199
 
        read_lock(&pool->lock);
200
 
        list_for_each(_chunk, &pool->chunks) {
201
 
                chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
202
 
 
 
326
        rcu_read_lock();
 
327
        list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
203
328
                if (addr >= chunk->start_addr && addr < chunk->end_addr) {
204
329
                        BUG_ON(addr + size > chunk->end_addr);
205
 
                        spin_lock_irqsave(&chunk->lock, flags);
206
 
                        bit = (addr - chunk->start_addr) >> order;
207
 
                        while (nbits--)
208
 
                                __clear_bit(bit++, chunk->bits);
209
 
                        spin_unlock_irqrestore(&chunk->lock, flags);
210
 
                        break;
 
330
                        start_bit = (addr - chunk->start_addr) >> order;
 
331
                        remain = bitmap_clear_ll(chunk->bits, start_bit, nbits);
 
332
                        BUG_ON(remain);
 
333
                        size = nbits << order;
 
334
                        atomic_add(size, &chunk->avail);
 
335
                        rcu_read_unlock();
 
336
                        return;
211
337
                }
212
338
        }
213
 
        BUG_ON(nbits > 0);
214
 
        read_unlock(&pool->lock);
 
339
        rcu_read_unlock();
 
340
        BUG();
215
341
}
216
342
EXPORT_SYMBOL(gen_pool_free);
 
343
 
 
344
/**
 
345
 * gen_pool_for_each_chunk - call func for every chunk of generic memory pool
 
346
 * @pool:       the generic memory pool
 
347
 * @func:       func to call
 
348
 * @data:       additional data used by @func
 
349
 *
 
350
 * Call @func for every chunk of generic memory pool.  The @func is
 
351
 * called with rcu_read_lock held.
 
352
 */
 
353
void gen_pool_for_each_chunk(struct gen_pool *pool,
 
354
        void (*func)(struct gen_pool *pool, struct gen_pool_chunk *chunk, void *data),
 
355
        void *data)
 
356
{
 
357
        struct gen_pool_chunk *chunk;
 
358
 
 
359
        rcu_read_lock();
 
360
        list_for_each_entry_rcu(chunk, &(pool)->chunks, next_chunk)
 
361
                func(pool, chunk, data);
 
362
        rcu_read_unlock();
 
363
}
 
364
EXPORT_SYMBOL(gen_pool_for_each_chunk);
 
365
 
 
366
/**
 
367
 * gen_pool_avail - get available free space of the pool
 
368
 * @pool: pool to get available free space
 
369
 *
 
370
 * Return available free space of the specified pool.
 
371
 */
 
372
size_t gen_pool_avail(struct gen_pool *pool)
 
373
{
 
374
        struct gen_pool_chunk *chunk;
 
375
        size_t avail = 0;
 
376
 
 
377
        rcu_read_lock();
 
378
        list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)
 
379
                avail += atomic_read(&chunk->avail);
 
380
        rcu_read_unlock();
 
381
        return avail;
 
382
}
 
383
EXPORT_SYMBOL_GPL(gen_pool_avail);
 
384
 
 
385
/**
 
386
 * gen_pool_size - get size in bytes of memory managed by the pool
 
387
 * @pool: pool to get size
 
388
 *
 
389
 * Return size in bytes of memory managed by the pool.
 
390
 */
 
391
size_t gen_pool_size(struct gen_pool *pool)
 
392
{
 
393
        struct gen_pool_chunk *chunk;
 
394
        size_t size = 0;
 
395
 
 
396
        rcu_read_lock();
 
397
        list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)
 
398
                size += chunk->end_addr - chunk->start_addr;
 
399
        rcu_read_unlock();
 
400
        return size;
 
401
}
 
402
EXPORT_SYMBOL_GPL(gen_pool_size);