2 * Copyright (c) 2006, 2007 Cisco Systems, Inc. All rights reserved.
3 * Copyright (c) 2007, 2008 Mellanox Technologies. All rights reserved.
5 * This software is available to you under a choice of one of two
6 * licenses. You may choose to be licensed under the terms of the GNU
7 * General Public License (GPL) Version 2, available from the file
8 * COPYING in the main directory of this source tree, or the
9 * OpenIB.org BSD license below:
11 * Redistribution and use in source and binary forms, with or
12 * without modification, are permitted provided that the following
15 * - Redistributions of source code must retain the above
16 * copyright notice, this list of conditions and the following
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials
22 * provided with the distribution.
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
28 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
29 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
30 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
34 #include <linux/errno.h>
35 #include <linux/slab.h>
37 #include <linux/export.h>
38 #include <linux/bitmap.h>
39 #include <linux/dma-mapping.h>
40 #include <linux/vmalloc.h>
44 u32
mlx4_bitmap_alloc(struct mlx4_bitmap
*bitmap
)
48 spin_lock(&bitmap
->lock
);
50 obj
= find_next_zero_bit(bitmap
->table
, bitmap
->max
, bitmap
->last
);
51 if (obj
>= bitmap
->max
) {
52 bitmap
->top
= (bitmap
->top
+ bitmap
->max
+ bitmap
->reserved_top
)
54 obj
= find_first_zero_bit(bitmap
->table
, bitmap
->max
);
57 if (obj
< bitmap
->max
) {
58 set_bit(obj
, bitmap
->table
);
59 bitmap
->last
= (obj
+ 1);
60 if (bitmap
->last
== bitmap
->max
)
69 spin_unlock(&bitmap
->lock
);
74 void mlx4_bitmap_free(struct mlx4_bitmap
*bitmap
, u32 obj
, int use_rr
)
76 mlx4_bitmap_free_range(bitmap
, obj
, 1, use_rr
);
79 static unsigned long find_aligned_range(unsigned long *bitmap
,
81 int len
, int align
, u32 skip_mask
)
86 start
= ALIGN(start
, align
);
88 while ((start
< nbits
) && (test_bit(start
, bitmap
) ||
99 for (i
= start
+ 1; i
< end
; i
++) {
100 if (test_bit(i
, bitmap
) || ((u32
)i
& skip_mask
)) {
109 u32
mlx4_bitmap_alloc_range(struct mlx4_bitmap
*bitmap
, int cnt
,
110 int align
, u32 skip_mask
)
114 if (likely(cnt
== 1 && align
== 1 && !skip_mask
))
115 return mlx4_bitmap_alloc(bitmap
);
117 spin_lock(&bitmap
->lock
);
119 obj
= find_aligned_range(bitmap
->table
, bitmap
->last
,
120 bitmap
->max
, cnt
, align
, skip_mask
);
121 if (obj
>= bitmap
->max
) {
122 bitmap
->top
= (bitmap
->top
+ bitmap
->max
+ bitmap
->reserved_top
)
124 obj
= find_aligned_range(bitmap
->table
, 0, bitmap
->max
,
125 cnt
, align
, skip_mask
);
128 if (obj
< bitmap
->max
) {
129 bitmap_set(bitmap
->table
, obj
, cnt
);
130 if (obj
== bitmap
->last
) {
131 bitmap
->last
= (obj
+ cnt
);
132 if (bitmap
->last
>= bitmap
->max
)
140 bitmap
->avail
-= cnt
;
142 spin_unlock(&bitmap
->lock
);
147 u32
mlx4_bitmap_avail(struct mlx4_bitmap
*bitmap
)
149 return bitmap
->avail
;
152 static u32
mlx4_bitmap_masked_value(struct mlx4_bitmap
*bitmap
, u32 obj
)
154 return obj
& (bitmap
->max
+ bitmap
->reserved_top
- 1);
157 void mlx4_bitmap_free_range(struct mlx4_bitmap
*bitmap
, u32 obj
, int cnt
,
160 obj
&= bitmap
->max
+ bitmap
->reserved_top
- 1;
162 spin_lock(&bitmap
->lock
);
164 bitmap
->last
= min(bitmap
->last
, obj
);
165 bitmap
->top
= (bitmap
->top
+ bitmap
->max
+ bitmap
->reserved_top
)
168 bitmap_clear(bitmap
->table
, obj
, cnt
);
169 bitmap
->avail
+= cnt
;
170 spin_unlock(&bitmap
->lock
);
173 int mlx4_bitmap_init(struct mlx4_bitmap
*bitmap
, u32 num
, u32 mask
,
174 u32 reserved_bot
, u32 reserved_top
)
176 /* num must be a power of 2 */
177 if (num
!= roundup_pow_of_two(num
))
182 bitmap
->max
= num
- reserved_top
;
184 bitmap
->reserved_top
= reserved_top
;
185 bitmap
->avail
= num
- reserved_top
- reserved_bot
;
186 bitmap
->effective_len
= bitmap
->avail
;
187 spin_lock_init(&bitmap
->lock
);
188 bitmap
->table
= kzalloc(BITS_TO_LONGS(bitmap
->max
) *
189 sizeof (long), GFP_KERNEL
);
193 bitmap_set(bitmap
->table
, 0, reserved_bot
);
198 void mlx4_bitmap_cleanup(struct mlx4_bitmap
*bitmap
)
200 kfree(bitmap
->table
);
203 struct mlx4_zone_allocator
{
204 struct list_head entries
;
205 struct list_head prios
;
208 /* protect the zone_allocator from concurrent accesses */
210 enum mlx4_zone_alloc_flags flags
;
213 struct mlx4_zone_entry
{
214 struct list_head list
;
215 struct list_head prio_list
;
217 struct mlx4_zone_allocator
*allocator
;
218 struct mlx4_bitmap
*bitmap
;
222 enum mlx4_zone_flags flags
;
225 struct mlx4_zone_allocator
*mlx4_zone_allocator_create(enum mlx4_zone_alloc_flags flags
)
227 struct mlx4_zone_allocator
*zones
= kmalloc(sizeof(*zones
), GFP_KERNEL
);
232 INIT_LIST_HEAD(&zones
->entries
);
233 INIT_LIST_HEAD(&zones
->prios
);
234 spin_lock_init(&zones
->lock
);
237 zones
->flags
= flags
;
242 int mlx4_zone_add_one(struct mlx4_zone_allocator
*zone_alloc
,
243 struct mlx4_bitmap
*bitmap
,
249 u32 mask
= mlx4_bitmap_masked_value(bitmap
, (u32
)-1);
250 struct mlx4_zone_entry
*it
;
251 struct mlx4_zone_entry
*zone
= kmalloc(sizeof(*zone
), GFP_KERNEL
);
257 zone
->bitmap
= bitmap
;
258 zone
->use_rr
= (flags
& MLX4_ZONE_USE_RR
) ? MLX4_USE_RR
: 0;
259 zone
->priority
= priority
;
260 zone
->offset
= offset
;
262 spin_lock(&zone_alloc
->lock
);
264 zone
->uid
= zone_alloc
->last_uid
++;
265 zone
->allocator
= zone_alloc
;
267 if (zone_alloc
->mask
< mask
)
268 zone_alloc
->mask
= mask
;
270 list_for_each_entry(it
, &zone_alloc
->prios
, prio_list
)
271 if (it
->priority
>= priority
)
274 if (&it
->prio_list
== &zone_alloc
->prios
|| it
->priority
> priority
)
275 list_add_tail(&zone
->prio_list
, &it
->prio_list
);
276 list_add_tail(&zone
->list
, &it
->list
);
278 spin_unlock(&zone_alloc
->lock
);
285 /* Should be called under a lock */
286 static void __mlx4_zone_remove_one_entry(struct mlx4_zone_entry
*entry
)
288 struct mlx4_zone_allocator
*zone_alloc
= entry
->allocator
;
290 if (!list_empty(&entry
->prio_list
)) {
291 /* Check if we need to add an alternative node to the prio list */
292 if (!list_is_last(&entry
->list
, &zone_alloc
->entries
)) {
293 struct mlx4_zone_entry
*next
= list_first_entry(&entry
->list
,
297 if (next
->priority
== entry
->priority
)
298 list_add_tail(&next
->prio_list
, &entry
->prio_list
);
301 list_del(&entry
->prio_list
);
304 list_del(&entry
->list
);
306 if (zone_alloc
->flags
& MLX4_ZONE_ALLOC_FLAGS_NO_OVERLAP
) {
308 struct mlx4_zone_entry
*it
;
310 list_for_each_entry(it
, &zone_alloc
->prios
, prio_list
) {
311 u32 cur_mask
= mlx4_bitmap_masked_value(it
->bitmap
, (u32
)-1);
316 zone_alloc
->mask
= mask
;
320 void mlx4_zone_allocator_destroy(struct mlx4_zone_allocator
*zone_alloc
)
322 struct mlx4_zone_entry
*zone
, *tmp
;
324 spin_lock(&zone_alloc
->lock
);
326 list_for_each_entry_safe(zone
, tmp
, &zone_alloc
->entries
, list
) {
327 list_del(&zone
->list
);
328 list_del(&zone
->prio_list
);
332 spin_unlock(&zone_alloc
->lock
);
336 /* Should be called under a lock */
337 static u32
__mlx4_alloc_from_zone(struct mlx4_zone_entry
*zone
, int count
,
338 int align
, u32 skip_mask
, u32
*puid
)
342 struct mlx4_zone_allocator
*zone_alloc
= zone
->allocator
;
343 struct mlx4_zone_entry
*curr_node
;
345 res
= mlx4_bitmap_alloc_range(zone
->bitmap
, count
,
348 if (res
!= (u32
)-1) {
354 list_for_each_entry(curr_node
, &zone_alloc
->prios
, prio_list
) {
355 if (unlikely(curr_node
->priority
== zone
->priority
))
359 if (zone
->flags
& MLX4_ZONE_ALLOW_ALLOC_FROM_LOWER_PRIO
) {
360 struct mlx4_zone_entry
*it
= curr_node
;
362 list_for_each_entry_continue_reverse(it
, &zone_alloc
->entries
, list
) {
363 res
= mlx4_bitmap_alloc_range(it
->bitmap
, count
,
365 if (res
!= (u32
)-1) {
373 if (zone
->flags
& MLX4_ZONE_ALLOW_ALLOC_FROM_EQ_PRIO
) {
374 struct mlx4_zone_entry
*it
= curr_node
;
376 list_for_each_entry_from(it
, &zone_alloc
->entries
, list
) {
377 if (unlikely(it
== zone
))
380 if (unlikely(it
->priority
!= curr_node
->priority
))
383 res
= mlx4_bitmap_alloc_range(it
->bitmap
, count
,
385 if (res
!= (u32
)-1) {
393 if (zone
->flags
& MLX4_ZONE_FALLBACK_TO_HIGHER_PRIO
) {
394 if (list_is_last(&curr_node
->prio_list
, &zone_alloc
->prios
))
397 curr_node
= list_first_entry(&curr_node
->prio_list
,
401 list_for_each_entry_from(curr_node
, &zone_alloc
->entries
, list
) {
402 res
= mlx4_bitmap_alloc_range(curr_node
->bitmap
, count
,
404 if (res
!= (u32
)-1) {
405 res
+= curr_node
->offset
;
406 uid
= curr_node
->uid
;
413 if (NULL
!= puid
&& res
!= (u32
)-1)
418 /* Should be called under a lock */
419 static void __mlx4_free_from_zone(struct mlx4_zone_entry
*zone
, u32 obj
,
422 mlx4_bitmap_free_range(zone
->bitmap
, obj
- zone
->offset
, count
, zone
->use_rr
);
425 /* Should be called under a lock */
426 static struct mlx4_zone_entry
*__mlx4_find_zone_by_uid(
427 struct mlx4_zone_allocator
*zones
, u32 uid
)
429 struct mlx4_zone_entry
*zone
;
431 list_for_each_entry(zone
, &zones
->entries
, list
) {
432 if (zone
->uid
== uid
)
439 struct mlx4_bitmap
*mlx4_zone_get_bitmap(struct mlx4_zone_allocator
*zones
, u32 uid
)
441 struct mlx4_zone_entry
*zone
;
442 struct mlx4_bitmap
*bitmap
;
444 spin_lock(&zones
->lock
);
446 zone
= __mlx4_find_zone_by_uid(zones
, uid
);
448 bitmap
= zone
== NULL
? NULL
: zone
->bitmap
;
450 spin_unlock(&zones
->lock
);
455 int mlx4_zone_remove_one(struct mlx4_zone_allocator
*zones
, u32 uid
)
457 struct mlx4_zone_entry
*zone
;
460 spin_lock(&zones
->lock
);
462 zone
= __mlx4_find_zone_by_uid(zones
, uid
);
469 __mlx4_zone_remove_one_entry(zone
);
472 spin_unlock(&zones
->lock
);
478 /* Should be called under a lock */
479 static struct mlx4_zone_entry
*__mlx4_find_zone_by_uid_unique(
480 struct mlx4_zone_allocator
*zones
, u32 obj
)
482 struct mlx4_zone_entry
*zone
, *zone_candidate
= NULL
;
485 /* Search for the smallest zone that this obj could be
486 * allocated from. This is done in order to handle
487 * situations when small bitmaps are allocated from bigger
488 * bitmaps (and the allocated space is marked as reserved in
491 list_for_each_entry(zone
, &zones
->entries
, list
) {
492 if (obj
>= zone
->offset
) {
493 u32 mobj
= (obj
- zone
->offset
) & zones
->mask
;
495 if (mobj
< zone
->bitmap
->max
) {
496 u32 curr_dist
= zone
->bitmap
->effective_len
;
498 if (curr_dist
< dist
) {
500 zone_candidate
= zone
;
506 return zone_candidate
;
509 u32
mlx4_zone_alloc_entries(struct mlx4_zone_allocator
*zones
, u32 uid
, int count
,
510 int align
, u32 skip_mask
, u32
*puid
)
512 struct mlx4_zone_entry
*zone
;
515 spin_lock(&zones
->lock
);
517 zone
= __mlx4_find_zone_by_uid(zones
, uid
);
522 res
= __mlx4_alloc_from_zone(zone
, count
, align
, skip_mask
, puid
);
525 spin_unlock(&zones
->lock
);
530 u32
mlx4_zone_free_entries(struct mlx4_zone_allocator
*zones
, u32 uid
, u32 obj
, u32 count
)
532 struct mlx4_zone_entry
*zone
;
535 spin_lock(&zones
->lock
);
537 zone
= __mlx4_find_zone_by_uid(zones
, uid
);
544 __mlx4_free_from_zone(zone
, obj
, count
);
547 spin_unlock(&zones
->lock
);
552 u32
mlx4_zone_free_entries_unique(struct mlx4_zone_allocator
*zones
, u32 obj
, u32 count
)
554 struct mlx4_zone_entry
*zone
;
557 if (!(zones
->flags
& MLX4_ZONE_ALLOC_FLAGS_NO_OVERLAP
))
560 spin_lock(&zones
->lock
);
562 zone
= __mlx4_find_zone_by_uid_unique(zones
, obj
);
569 __mlx4_free_from_zone(zone
, obj
, count
);
573 spin_unlock(&zones
->lock
);
578 static int mlx4_buf_direct_alloc(struct mlx4_dev
*dev
, int size
,
579 struct mlx4_buf
*buf
)
585 buf
->page_shift
= get_order(size
) + PAGE_SHIFT
;
587 dma_zalloc_coherent(&dev
->persist
->pdev
->dev
,
588 size
, &t
, GFP_KERNEL
);
589 if (!buf
->direct
.buf
)
594 while (t
& ((1 << buf
->page_shift
) - 1)) {
602 /* Handling for queue buffers -- we allocate a bunch of memory and
603 * register it in a memory region at HCA virtual address 0. If the
604 * requested size is > max_direct, we split the allocation into
605 * multiple pages, so we don't require too much contiguous memory.
607 int mlx4_buf_alloc(struct mlx4_dev
*dev
, int size
, int max_direct
,
608 struct mlx4_buf
*buf
)
610 if (size
<= max_direct
) {
611 return mlx4_buf_direct_alloc(dev
, size
, buf
);
616 buf
->direct
.buf
= NULL
;
617 buf
->nbufs
= (size
+ PAGE_SIZE
- 1) / PAGE_SIZE
;
618 buf
->npages
= buf
->nbufs
;
619 buf
->page_shift
= PAGE_SHIFT
;
620 buf
->page_list
= kcalloc(buf
->nbufs
, sizeof(*buf
->page_list
),
625 for (i
= 0; i
< buf
->nbufs
; ++i
) {
626 buf
->page_list
[i
].buf
=
627 dma_zalloc_coherent(&dev
->persist
->pdev
->dev
,
628 PAGE_SIZE
, &t
, GFP_KERNEL
);
629 if (!buf
->page_list
[i
].buf
)
632 buf
->page_list
[i
].map
= t
;
639 mlx4_buf_free(dev
, size
, buf
);
643 EXPORT_SYMBOL_GPL(mlx4_buf_alloc
);
645 void mlx4_buf_free(struct mlx4_dev
*dev
, int size
, struct mlx4_buf
*buf
)
647 if (buf
->nbufs
== 1) {
648 dma_free_coherent(&dev
->persist
->pdev
->dev
, size
,
649 buf
->direct
.buf
, buf
->direct
.map
);
653 for (i
= 0; i
< buf
->nbufs
; ++i
)
654 if (buf
->page_list
[i
].buf
)
655 dma_free_coherent(&dev
->persist
->pdev
->dev
,
657 buf
->page_list
[i
].buf
,
658 buf
->page_list
[i
].map
);
659 kfree(buf
->page_list
);
662 EXPORT_SYMBOL_GPL(mlx4_buf_free
);
664 static struct mlx4_db_pgdir
*mlx4_alloc_db_pgdir(struct device
*dma_device
)
666 struct mlx4_db_pgdir
*pgdir
;
668 pgdir
= kzalloc(sizeof(*pgdir
), GFP_KERNEL
);
672 bitmap_fill(pgdir
->order1
, MLX4_DB_PER_PAGE
/ 2);
673 pgdir
->bits
[0] = pgdir
->order0
;
674 pgdir
->bits
[1] = pgdir
->order1
;
675 pgdir
->db_page
= dma_alloc_coherent(dma_device
, PAGE_SIZE
,
676 &pgdir
->db_dma
, GFP_KERNEL
);
677 if (!pgdir
->db_page
) {
685 static int mlx4_alloc_db_from_pgdir(struct mlx4_db_pgdir
*pgdir
,
686 struct mlx4_db
*db
, int order
)
691 for (o
= order
; o
<= 1; ++o
) {
692 i
= find_first_bit(pgdir
->bits
[o
], MLX4_DB_PER_PAGE
>> o
);
693 if (i
< MLX4_DB_PER_PAGE
>> o
)
700 clear_bit(i
, pgdir
->bits
[o
]);
705 set_bit(i
^ 1, pgdir
->bits
[order
]);
709 db
->db
= pgdir
->db_page
+ db
->index
;
710 db
->dma
= pgdir
->db_dma
+ db
->index
* 4;
716 int mlx4_db_alloc(struct mlx4_dev
*dev
, struct mlx4_db
*db
, int order
)
718 struct mlx4_priv
*priv
= mlx4_priv(dev
);
719 struct mlx4_db_pgdir
*pgdir
;
722 mutex_lock(&priv
->pgdir_mutex
);
724 list_for_each_entry(pgdir
, &priv
->pgdir_list
, list
)
725 if (!mlx4_alloc_db_from_pgdir(pgdir
, db
, order
))
728 pgdir
= mlx4_alloc_db_pgdir(&dev
->persist
->pdev
->dev
);
734 list_add(&pgdir
->list
, &priv
->pgdir_list
);
736 /* This should never fail -- we just allocated an empty page: */
737 WARN_ON(mlx4_alloc_db_from_pgdir(pgdir
, db
, order
));
740 mutex_unlock(&priv
->pgdir_mutex
);
744 EXPORT_SYMBOL_GPL(mlx4_db_alloc
);
746 void mlx4_db_free(struct mlx4_dev
*dev
, struct mlx4_db
*db
)
748 struct mlx4_priv
*priv
= mlx4_priv(dev
);
752 mutex_lock(&priv
->pgdir_mutex
);
757 if (db
->order
== 0 && test_bit(i
^ 1, db
->u
.pgdir
->order0
)) {
758 clear_bit(i
^ 1, db
->u
.pgdir
->order0
);
762 set_bit(i
, db
->u
.pgdir
->bits
[o
]);
764 if (bitmap_full(db
->u
.pgdir
->order1
, MLX4_DB_PER_PAGE
/ 2)) {
765 dma_free_coherent(&dev
->persist
->pdev
->dev
, PAGE_SIZE
,
766 db
->u
.pgdir
->db_page
, db
->u
.pgdir
->db_dma
);
767 list_del(&db
->u
.pgdir
->list
);
771 mutex_unlock(&priv
->pgdir_mutex
);
773 EXPORT_SYMBOL_GPL(mlx4_db_free
);
775 int mlx4_alloc_hwq_res(struct mlx4_dev
*dev
, struct mlx4_hwq_resources
*wqres
,
780 err
= mlx4_db_alloc(dev
, &wqres
->db
, 1);
786 err
= mlx4_buf_direct_alloc(dev
, size
, &wqres
->buf
);
790 err
= mlx4_mtt_init(dev
, wqres
->buf
.npages
, wqres
->buf
.page_shift
,
795 err
= mlx4_buf_write_mtt(dev
, &wqres
->mtt
, &wqres
->buf
);
802 mlx4_mtt_cleanup(dev
, &wqres
->mtt
);
804 mlx4_buf_free(dev
, size
, &wqres
->buf
);
806 mlx4_db_free(dev
, &wqres
->db
);
810 EXPORT_SYMBOL_GPL(mlx4_alloc_hwq_res
);
812 void mlx4_free_hwq_res(struct mlx4_dev
*dev
, struct mlx4_hwq_resources
*wqres
,
815 mlx4_mtt_cleanup(dev
, &wqres
->mtt
);
816 mlx4_buf_free(dev
, size
, &wqres
->buf
);
817 mlx4_db_free(dev
, &wqres
->db
);
819 EXPORT_SYMBOL_GPL(mlx4_free_hwq_res
);