1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#include <linux/errno.h>
35#include <linux/slab.h>
36#include <linux/mm.h>
37#include <linux/export.h>
38#include <linux/bitmap.h>
39#include <linux/dma-mapping.h>
40#include <linux/vmalloc.h>
41
42#include "mlx4.h"
43
44u32 mlx4_bitmap_alloc(struct mlx4_bitmap *bitmap)
45{
46 u32 obj;
47
48 spin_lock(&bitmap->lock);
49
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)
53 & bitmap->mask;
54 obj = find_first_zero_bit(bitmap->table, bitmap->max);
55 }
56
57 if (obj < bitmap->max) {
58 set_bit(obj, bitmap->table);
59 bitmap->last = (obj + 1);
60 if (bitmap->last == bitmap->max)
61 bitmap->last = 0;
62 obj |= bitmap->top;
63 } else
64 obj = -1;
65
66 if (obj != -1)
67 --bitmap->avail;
68
69 spin_unlock(&bitmap->lock);
70
71 return obj;
72}
73
74void mlx4_bitmap_free(struct mlx4_bitmap *bitmap, u32 obj, int use_rr)
75{
76 mlx4_bitmap_free_range(bitmap, obj, 1, use_rr);
77}
78
79static unsigned long find_aligned_range(unsigned long *bitmap,
80 u32 start, u32 nbits,
81 int len, int align, u32 skip_mask)
82{
83 unsigned long end, i;
84
85again:
86 start = ALIGN(start, align);
87
88 while ((start < nbits) && (test_bit(start, bitmap) ||
89 (start & skip_mask)))
90 start += align;
91
92 if (start >= nbits)
93 return -1;
94
95 end = start+len;
96 if (end > nbits)
97 return -1;
98
99 for (i = start + 1; i < end; i++) {
100 if (test_bit(i, bitmap) || ((u32)i & skip_mask)) {
101 start = i + 1;
102 goto again;
103 }
104 }
105
106 return start;
107}
108
109u32 mlx4_bitmap_alloc_range(struct mlx4_bitmap *bitmap, int cnt,
110 int align, u32 skip_mask)
111{
112 u32 obj;
113
114 if (likely(cnt == 1 && align == 1 && !skip_mask))
115 return mlx4_bitmap_alloc(bitmap);
116
117 spin_lock(&bitmap->lock);
118
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)
123 & bitmap->mask;
124 obj = find_aligned_range(bitmap->table, 0, bitmap->max,
125 cnt, align, skip_mask);
126 }
127
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)
133 bitmap->last = 0;
134 }
135 obj |= bitmap->top;
136 } else
137 obj = -1;
138
139 if (obj != -1)
140 bitmap->avail -= cnt;
141
142 spin_unlock(&bitmap->lock);
143
144 return obj;
145}
146
147u32 mlx4_bitmap_avail(struct mlx4_bitmap *bitmap)
148{
149 return bitmap->avail;
150}
151
152static u32 mlx4_bitmap_masked_value(struct mlx4_bitmap *bitmap, u32 obj)
153{
154 return obj & (bitmap->max + bitmap->reserved_top - 1);
155}
156
157void mlx4_bitmap_free_range(struct mlx4_bitmap *bitmap, u32 obj, int cnt,
158 int use_rr)
159{
160 obj &= bitmap->max + bitmap->reserved_top - 1;
161
162 spin_lock(&bitmap->lock);
163 if (!use_rr) {
164 bitmap->last = min(bitmap->last, obj);
165 bitmap->top = (bitmap->top + bitmap->max + bitmap->reserved_top)
166 & bitmap->mask;
167 }
168 bitmap_clear(bitmap->table, obj, cnt);
169 bitmap->avail += cnt;
170 spin_unlock(&bitmap->lock);
171}
172
173int mlx4_bitmap_init(struct mlx4_bitmap *bitmap, u32 num, u32 mask,
174 u32 reserved_bot, u32 reserved_top)
175{
176
177 if (num != roundup_pow_of_two(num))
178 return -EINVAL;
179
180 bitmap->last = 0;
181 bitmap->top = 0;
182 bitmap->max = num - reserved_top;
183 bitmap->mask = mask;
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 = bitmap_zalloc(bitmap->max, GFP_KERNEL);
189 if (!bitmap->table)
190 return -ENOMEM;
191
192 bitmap_set(bitmap->table, 0, reserved_bot);
193
194 return 0;
195}
196
197void mlx4_bitmap_cleanup(struct mlx4_bitmap *bitmap)
198{
199 bitmap_free(bitmap->table);
200}
201
202struct mlx4_zone_allocator {
203 struct list_head entries;
204 struct list_head prios;
205 u32 last_uid;
206 u32 mask;
207
208 spinlock_t lock;
209 enum mlx4_zone_alloc_flags flags;
210};
211
212struct mlx4_zone_entry {
213 struct list_head list;
214 struct list_head prio_list;
215 u32 uid;
216 struct mlx4_zone_allocator *allocator;
217 struct mlx4_bitmap *bitmap;
218 int use_rr;
219 int priority;
220 int offset;
221 enum mlx4_zone_flags flags;
222};
223
224struct mlx4_zone_allocator *mlx4_zone_allocator_create(enum mlx4_zone_alloc_flags flags)
225{
226 struct mlx4_zone_allocator *zones = kmalloc(sizeof(*zones), GFP_KERNEL);
227
228 if (NULL == zones)
229 return NULL;
230
231 INIT_LIST_HEAD(&zones->entries);
232 INIT_LIST_HEAD(&zones->prios);
233 spin_lock_init(&zones->lock);
234 zones->last_uid = 0;
235 zones->mask = 0;
236 zones->flags = flags;
237
238 return zones;
239}
240
241int mlx4_zone_add_one(struct mlx4_zone_allocator *zone_alloc,
242 struct mlx4_bitmap *bitmap,
243 u32 flags,
244 int priority,
245 int offset,
246 u32 *puid)
247{
248 u32 mask = mlx4_bitmap_masked_value(bitmap, (u32)-1);
249 struct mlx4_zone_entry *it;
250 struct mlx4_zone_entry *zone = kmalloc(sizeof(*zone), GFP_KERNEL);
251
252 if (NULL == zone)
253 return -ENOMEM;
254
255 zone->flags = flags;
256 zone->bitmap = bitmap;
257 zone->use_rr = (flags & MLX4_ZONE_USE_RR) ? MLX4_USE_RR : 0;
258 zone->priority = priority;
259 zone->offset = offset;
260
261 spin_lock(&zone_alloc->lock);
262
263 zone->uid = zone_alloc->last_uid++;
264 zone->allocator = zone_alloc;
265
266 if (zone_alloc->mask < mask)
267 zone_alloc->mask = mask;
268
269 list_for_each_entry(it, &zone_alloc->prios, prio_list)
270 if (it->priority >= priority)
271 break;
272
273 if (&it->prio_list == &zone_alloc->prios || it->priority > priority)
274 list_add_tail(&zone->prio_list, &it->prio_list);
275 list_add_tail(&zone->list, &it->list);
276
277 spin_unlock(&zone_alloc->lock);
278
279 *puid = zone->uid;
280
281 return 0;
282}
283
284
285static void __mlx4_zone_remove_one_entry(struct mlx4_zone_entry *entry)
286{
287 struct mlx4_zone_allocator *zone_alloc = entry->allocator;
288
289 if (!list_empty(&entry->prio_list)) {
290
291 if (!list_is_last(&entry->list, &zone_alloc->entries)) {
292 struct mlx4_zone_entry *next = list_first_entry(&entry->list,
293 typeof(*next),
294 list);
295
296 if (next->priority == entry->priority)
297 list_add_tail(&next->prio_list, &entry->prio_list);
298 }
299
300 list_del(&entry->prio_list);
301 }
302
303 list_del(&entry->list);
304
305 if (zone_alloc->flags & MLX4_ZONE_ALLOC_FLAGS_NO_OVERLAP) {
306 u32 mask = 0;
307 struct mlx4_zone_entry *it;
308
309 list_for_each_entry(it, &zone_alloc->prios, prio_list) {
310 u32 cur_mask = mlx4_bitmap_masked_value(it->bitmap, (u32)-1);
311
312 if (mask < cur_mask)
313 mask = cur_mask;
314 }
315 zone_alloc->mask = mask;
316 }
317}
318
319void mlx4_zone_allocator_destroy(struct mlx4_zone_allocator *zone_alloc)
320{
321 struct mlx4_zone_entry *zone, *tmp;
322
323 spin_lock(&zone_alloc->lock);
324
325 list_for_each_entry_safe(zone, tmp, &zone_alloc->entries, list) {
326 list_del(&zone->list);
327 list_del(&zone->prio_list);
328 kfree(zone);
329 }
330
331 spin_unlock(&zone_alloc->lock);
332 kfree(zone_alloc);
333}
334
335
336static u32 __mlx4_alloc_from_zone(struct mlx4_zone_entry *zone, int count,
337 int align, u32 skip_mask, u32 *puid)
338{
339 u32 uid = 0;
340 u32 res;
341 struct mlx4_zone_allocator *zone_alloc = zone->allocator;
342 struct mlx4_zone_entry *curr_node;
343
344 res = mlx4_bitmap_alloc_range(zone->bitmap, count,
345 align, skip_mask);
346
347 if (res != (u32)-1) {
348 res += zone->offset;
349 uid = zone->uid;
350 goto out;
351 }
352
353 list_for_each_entry(curr_node, &zone_alloc->prios, prio_list) {
354 if (unlikely(curr_node->priority == zone->priority))
355 break;
356 }
357
358 if (zone->flags & MLX4_ZONE_ALLOW_ALLOC_FROM_LOWER_PRIO) {
359 struct mlx4_zone_entry *it = curr_node;
360
361 list_for_each_entry_continue_reverse(it, &zone_alloc->entries, list) {
362 res = mlx4_bitmap_alloc_range(it->bitmap, count,
363 align, skip_mask);
364 if (res != (u32)-1) {
365 res += it->offset;
366 uid = it->uid;
367 goto out;
368 }
369 }
370 }
371
372 if (zone->flags & MLX4_ZONE_ALLOW_ALLOC_FROM_EQ_PRIO) {
373 struct mlx4_zone_entry *it = curr_node;
374
375 list_for_each_entry_from(it, &zone_alloc->entries, list) {
376 if (unlikely(it == zone))
377 continue;
378
379 if (unlikely(it->priority != curr_node->priority))
380 break;
381
382 res = mlx4_bitmap_alloc_range(it->bitmap, count,
383 align, skip_mask);
384 if (res != (u32)-1) {
385 res += it->offset;
386 uid = it->uid;
387 goto out;
388 }
389 }
390 }
391
392 if (zone->flags & MLX4_ZONE_FALLBACK_TO_HIGHER_PRIO) {
393 if (list_is_last(&curr_node->prio_list, &zone_alloc->prios))
394 goto out;
395
396 curr_node = list_first_entry(&curr_node->prio_list,
397 typeof(*curr_node),
398 prio_list);
399
400 list_for_each_entry_from(curr_node, &zone_alloc->entries, list) {
401 res = mlx4_bitmap_alloc_range(curr_node->bitmap, count,
402 align, skip_mask);
403 if (res != (u32)-1) {
404 res += curr_node->offset;
405 uid = curr_node->uid;
406 goto out;
407 }
408 }
409 }
410
411out:
412 if (NULL != puid && res != (u32)-1)
413 *puid = uid;
414 return res;
415}
416
417
418static void __mlx4_free_from_zone(struct mlx4_zone_entry *zone, u32 obj,
419 u32 count)
420{
421 mlx4_bitmap_free_range(zone->bitmap, obj - zone->offset, count, zone->use_rr);
422}
423
424
425static struct mlx4_zone_entry *__mlx4_find_zone_by_uid(
426 struct mlx4_zone_allocator *zones, u32 uid)
427{
428 struct mlx4_zone_entry *zone;
429
430 list_for_each_entry(zone, &zones->entries, list) {
431 if (zone->uid == uid)
432 return zone;
433 }
434
435 return NULL;
436}
437
438struct mlx4_bitmap *mlx4_zone_get_bitmap(struct mlx4_zone_allocator *zones, u32 uid)
439{
440 struct mlx4_zone_entry *zone;
441 struct mlx4_bitmap *bitmap;
442
443 spin_lock(&zones->lock);
444
445 zone = __mlx4_find_zone_by_uid(zones, uid);
446
447 bitmap = zone == NULL ? NULL : zone->bitmap;
448
449 spin_unlock(&zones->lock);
450
451 return bitmap;
452}
453
454int mlx4_zone_remove_one(struct mlx4_zone_allocator *zones, u32 uid)
455{
456 struct mlx4_zone_entry *zone;
457 int res = 0;
458
459 spin_lock(&zones->lock);
460
461 zone = __mlx4_find_zone_by_uid(zones, uid);
462
463 if (NULL == zone) {
464 res = -1;
465 goto out;
466 }
467
468 __mlx4_zone_remove_one_entry(zone);
469
470out:
471 spin_unlock(&zones->lock);
472 kfree(zone);
473
474 return res;
475}
476
477
478static struct mlx4_zone_entry *__mlx4_find_zone_by_uid_unique(
479 struct mlx4_zone_allocator *zones, u32 obj)
480{
481 struct mlx4_zone_entry *zone, *zone_candidate = NULL;
482 u32 dist = (u32)-1;
483
484
485
486
487
488
489
490 list_for_each_entry(zone, &zones->entries, list) {
491 if (obj >= zone->offset) {
492 u32 mobj = (obj - zone->offset) & zones->mask;
493
494 if (mobj < zone->bitmap->max) {
495 u32 curr_dist = zone->bitmap->effective_len;
496
497 if (curr_dist < dist) {
498 dist = curr_dist;
499 zone_candidate = zone;
500 }
501 }
502 }
503 }
504
505 return zone_candidate;
506}
507
508u32 mlx4_zone_alloc_entries(struct mlx4_zone_allocator *zones, u32 uid, int count,
509 int align, u32 skip_mask, u32 *puid)
510{
511 struct mlx4_zone_entry *zone;
512 int res = -1;
513
514 spin_lock(&zones->lock);
515
516 zone = __mlx4_find_zone_by_uid(zones, uid);
517
518 if (NULL == zone)
519 goto out;
520
521 res = __mlx4_alloc_from_zone(zone, count, align, skip_mask, puid);
522
523out:
524 spin_unlock(&zones->lock);
525
526 return res;
527}
528
529u32 mlx4_zone_free_entries(struct mlx4_zone_allocator *zones, u32 uid, u32 obj, u32 count)
530{
531 struct mlx4_zone_entry *zone;
532 int res = 0;
533
534 spin_lock(&zones->lock);
535
536 zone = __mlx4_find_zone_by_uid(zones, uid);
537
538 if (NULL == zone) {
539 res = -1;
540 goto out;
541 }
542
543 __mlx4_free_from_zone(zone, obj, count);
544
545out:
546 spin_unlock(&zones->lock);
547
548 return res;
549}
550
551u32 mlx4_zone_free_entries_unique(struct mlx4_zone_allocator *zones, u32 obj, u32 count)
552{
553 struct mlx4_zone_entry *zone;
554 int res;
555
556 if (!(zones->flags & MLX4_ZONE_ALLOC_FLAGS_NO_OVERLAP))
557 return -EFAULT;
558
559 spin_lock(&zones->lock);
560
561 zone = __mlx4_find_zone_by_uid_unique(zones, obj);
562
563 if (NULL == zone) {
564 res = -1;
565 goto out;
566 }
567
568 __mlx4_free_from_zone(zone, obj, count);
569 res = 0;
570
571out:
572 spin_unlock(&zones->lock);
573
574 return res;
575}
576
577static int mlx4_buf_direct_alloc(struct mlx4_dev *dev, int size,
578 struct mlx4_buf *buf)
579{
580 dma_addr_t t;
581
582 buf->nbufs = 1;
583 buf->npages = 1;
584 buf->page_shift = get_order(size) + PAGE_SHIFT;
585 buf->direct.buf =
586 dma_alloc_coherent(&dev->persist->pdev->dev, size, &t,
587 GFP_KERNEL);
588 if (!buf->direct.buf)
589 return -ENOMEM;
590
591 buf->direct.map = t;
592
593 while (t & ((1 << buf->page_shift) - 1)) {
594 --buf->page_shift;
595 buf->npages *= 2;
596 }
597
598 return 0;
599}
600
601
602
603
604
605
606int mlx4_buf_alloc(struct mlx4_dev *dev, int size, int max_direct,
607 struct mlx4_buf *buf)
608{
609 if (size <= max_direct) {
610 return mlx4_buf_direct_alloc(dev, size, buf);
611 } else {
612 dma_addr_t t;
613 int i;
614
615 buf->direct.buf = NULL;
616 buf->nbufs = DIV_ROUND_UP(size, PAGE_SIZE);
617 buf->npages = buf->nbufs;
618 buf->page_shift = PAGE_SHIFT;
619 buf->page_list = kcalloc(buf->nbufs, sizeof(*buf->page_list),
620 GFP_KERNEL);
621 if (!buf->page_list)
622 return -ENOMEM;
623
624 for (i = 0; i < buf->nbufs; ++i) {
625 buf->page_list[i].buf =
626 dma_alloc_coherent(&dev->persist->pdev->dev,
627 PAGE_SIZE, &t, GFP_KERNEL);
628 if (!buf->page_list[i].buf)
629 goto err_free;
630
631 buf->page_list[i].map = t;
632 }
633 }
634
635 return 0;
636
637err_free:
638 mlx4_buf_free(dev, size, buf);
639
640 return -ENOMEM;
641}
642EXPORT_SYMBOL_GPL(mlx4_buf_alloc);
643
644void mlx4_buf_free(struct mlx4_dev *dev, int size, struct mlx4_buf *buf)
645{
646 if (buf->nbufs == 1) {
647 dma_free_coherent(&dev->persist->pdev->dev, size,
648 buf->direct.buf, buf->direct.map);
649 } else {
650 int i;
651
652 for (i = 0; i < buf->nbufs; ++i)
653 if (buf->page_list[i].buf)
654 dma_free_coherent(&dev->persist->pdev->dev,
655 PAGE_SIZE,
656 buf->page_list[i].buf,
657 buf->page_list[i].map);
658 kfree(buf->page_list);
659 }
660}
661EXPORT_SYMBOL_GPL(mlx4_buf_free);
662
663static struct mlx4_db_pgdir *mlx4_alloc_db_pgdir(struct device *dma_device)
664{
665 struct mlx4_db_pgdir *pgdir;
666
667 pgdir = kzalloc(sizeof(*pgdir), GFP_KERNEL);
668 if (!pgdir)
669 return NULL;
670
671 bitmap_fill(pgdir->order1, MLX4_DB_PER_PAGE / 2);
672 pgdir->bits[0] = pgdir->order0;
673 pgdir->bits[1] = pgdir->order1;
674 pgdir->db_page = dma_alloc_coherent(dma_device, PAGE_SIZE,
675 &pgdir->db_dma, GFP_KERNEL);
676 if (!pgdir->db_page) {
677 kfree(pgdir);
678 return NULL;
679 }
680
681 return pgdir;
682}
683
684static int mlx4_alloc_db_from_pgdir(struct mlx4_db_pgdir *pgdir,
685 struct mlx4_db *db, int order)
686{
687 int o;
688 int i;
689
690 for (o = order; o <= 1; ++o) {
691 i = find_first_bit(pgdir->bits[o], MLX4_DB_PER_PAGE >> o);
692 if (i < MLX4_DB_PER_PAGE >> o)
693 goto found;
694 }
695
696 return -ENOMEM;
697
698found:
699 clear_bit(i, pgdir->bits[o]);
700
701 i <<= o;
702
703 if (o > order)
704 set_bit(i ^ 1, pgdir->bits[order]);
705
706 db->u.pgdir = pgdir;
707 db->index = i;
708 db->db = pgdir->db_page + db->index;
709 db->dma = pgdir->db_dma + db->index * 4;
710 db->order = order;
711
712 return 0;
713}
714
715int mlx4_db_alloc(struct mlx4_dev *dev, struct mlx4_db *db, int order)
716{
717 struct mlx4_priv *priv = mlx4_priv(dev);
718 struct mlx4_db_pgdir *pgdir;
719 int ret = 0;
720
721 mutex_lock(&priv->pgdir_mutex);
722
723 list_for_each_entry(pgdir, &priv->pgdir_list, list)
724 if (!mlx4_alloc_db_from_pgdir(pgdir, db, order))
725 goto out;
726
727 pgdir = mlx4_alloc_db_pgdir(&dev->persist->pdev->dev);
728 if (!pgdir) {
729 ret = -ENOMEM;
730 goto out;
731 }
732
733 list_add(&pgdir->list, &priv->pgdir_list);
734
735
736 WARN_ON(mlx4_alloc_db_from_pgdir(pgdir, db, order));
737
738out:
739 mutex_unlock(&priv->pgdir_mutex);
740
741 return ret;
742}
743EXPORT_SYMBOL_GPL(mlx4_db_alloc);
744
745void mlx4_db_free(struct mlx4_dev *dev, struct mlx4_db *db)
746{
747 struct mlx4_priv *priv = mlx4_priv(dev);
748 int o;
749 int i;
750
751 mutex_lock(&priv->pgdir_mutex);
752
753 o = db->order;
754 i = db->index;
755
756 if (db->order == 0 && test_bit(i ^ 1, db->u.pgdir->order0)) {
757 clear_bit(i ^ 1, db->u.pgdir->order0);
758 ++o;
759 }
760 i >>= o;
761 set_bit(i, db->u.pgdir->bits[o]);
762
763 if (bitmap_full(db->u.pgdir->order1, MLX4_DB_PER_PAGE / 2)) {
764 dma_free_coherent(&dev->persist->pdev->dev, PAGE_SIZE,
765 db->u.pgdir->db_page, db->u.pgdir->db_dma);
766 list_del(&db->u.pgdir->list);
767 kfree(db->u.pgdir);
768 }
769
770 mutex_unlock(&priv->pgdir_mutex);
771}
772EXPORT_SYMBOL_GPL(mlx4_db_free);
773
774int mlx4_alloc_hwq_res(struct mlx4_dev *dev, struct mlx4_hwq_resources *wqres,
775 int size)
776{
777 int err;
778
779 err = mlx4_db_alloc(dev, &wqres->db, 1);
780 if (err)
781 return err;
782
783 *wqres->db.db = 0;
784
785 err = mlx4_buf_direct_alloc(dev, size, &wqres->buf);
786 if (err)
787 goto err_db;
788
789 err = mlx4_mtt_init(dev, wqres->buf.npages, wqres->buf.page_shift,
790 &wqres->mtt);
791 if (err)
792 goto err_buf;
793
794 err = mlx4_buf_write_mtt(dev, &wqres->mtt, &wqres->buf);
795 if (err)
796 goto err_mtt;
797
798 return 0;
799
800err_mtt:
801 mlx4_mtt_cleanup(dev, &wqres->mtt);
802err_buf:
803 mlx4_buf_free(dev, size, &wqres->buf);
804err_db:
805 mlx4_db_free(dev, &wqres->db);
806
807 return err;
808}
809EXPORT_SYMBOL_GPL(mlx4_alloc_hwq_res);
810
811void mlx4_free_hwq_res(struct mlx4_dev *dev, struct mlx4_hwq_resources *wqres,
812 int size)
813{
814 mlx4_mtt_cleanup(dev, &wqres->mtt);
815 mlx4_buf_free(dev, size, &wqres->buf);
816 mlx4_db_free(dev, &wqres->db);
817}
818EXPORT_SYMBOL_GPL(mlx4_free_hwq_res);
819