1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright (c) 2022 NVIDIA Corporation & Affiliates
3 */
4
5 #include <rte_bitmap.h>
6 #include <rte_malloc.h>
7 #include "mlx5dr_internal.h"
8 #include "mlx5dr_buddy.h"
9
bitmap_alloc0(int s)10 static struct rte_bitmap *bitmap_alloc0(int s)
11 {
12 struct rte_bitmap *bitmap;
13 uint32_t bmp_size;
14 void *mem;
15
16 bmp_size = rte_bitmap_get_memory_footprint(s);
17 mem = rte_zmalloc("create_bmap", bmp_size, RTE_CACHE_LINE_SIZE);
18 if (!mem) {
19 DR_LOG(ERR, "No mem for bitmap");
20 rte_errno = ENOMEM;
21 return NULL;
22 }
23
24 bitmap = rte_bitmap_init(s, mem, bmp_size);
25 if (!bitmap) {
26 DR_LOG(ERR, "%s Failed to initialize bitmap", __func__);
27 rte_errno = EINVAL;
28 goto err_mem_alloc;
29 }
30
31 return bitmap;
32
33 err_mem_alloc:
34 rte_free(mem);
35 return NULL;
36 }
37
bitmap_set_bit(struct rte_bitmap * bmp,uint32_t pos)38 static void bitmap_set_bit(struct rte_bitmap *bmp, uint32_t pos)
39 {
40 rte_bitmap_set(bmp, pos);
41 }
42
bitmap_clear_bit(struct rte_bitmap * bmp,uint32_t pos)43 static void bitmap_clear_bit(struct rte_bitmap *bmp, uint32_t pos)
44 {
45 rte_bitmap_clear(bmp, pos);
46 }
47
bitmap_test_bit(struct rte_bitmap * bmp,unsigned long n)48 static bool bitmap_test_bit(struct rte_bitmap *bmp, unsigned long n)
49 {
50 return !!rte_bitmap_get(bmp, n);
51 }
52
bitmap_ffs(struct rte_bitmap * bmap,uint64_t n,unsigned long m)53 static unsigned long bitmap_ffs(struct rte_bitmap *bmap,
54 uint64_t n, unsigned long m)
55 {
56 uint64_t out_slab = 0;
57 uint32_t pos = 0; /* Compilation warn */
58
59 __rte_bitmap_scan_init(bmap);
60 if (!rte_bitmap_scan(bmap, &pos, &out_slab)) {
61 DR_LOG(ERR, "Failed to get slab from bitmap.");
62 return m;
63 }
64 pos = pos + rte_ctz64(out_slab);
65
66 if (pos < n) {
67 DR_LOG(ERR, "Unexpected bit (%d < %"PRIx64") from bitmap", pos, n);
68 return m;
69 }
70 return pos;
71 }
72
mlx5dr_buddy_find_first_bit(struct rte_bitmap * addr,uint32_t size)73 static unsigned long mlx5dr_buddy_find_first_bit(struct rte_bitmap *addr,
74 uint32_t size)
75 {
76 return bitmap_ffs(addr, 0, size);
77 }
78
mlx5dr_buddy_init(struct mlx5dr_buddy_mem * buddy,uint32_t max_order)79 static int mlx5dr_buddy_init(struct mlx5dr_buddy_mem *buddy, uint32_t max_order)
80 {
81 int i, s;
82
83 buddy->max_order = max_order;
84
85 buddy->bits = simple_calloc(buddy->max_order + 1, sizeof(long *));
86 if (!buddy->bits) {
87 rte_errno = ENOMEM;
88 return -1;
89 }
90
91 buddy->num_free = simple_calloc(buddy->max_order + 1, sizeof(*buddy->num_free));
92 if (!buddy->num_free) {
93 rte_errno = ENOMEM;
94 goto err_out_free_bits;
95 }
96
97 for (i = 0; i <= (int)buddy->max_order; ++i) {
98 s = 1 << (buddy->max_order - i);
99 buddy->bits[i] = bitmap_alloc0(s);
100 if (!buddy->bits[i])
101 goto err_out_free_num_free;
102 }
103
104 bitmap_set_bit(buddy->bits[buddy->max_order], 0);
105
106 buddy->num_free[buddy->max_order] = 1;
107
108 return 0;
109
110 err_out_free_num_free:
111 for (i = 0; i <= (int)buddy->max_order; ++i)
112 rte_free(buddy->bits[i]);
113
114 simple_free(buddy->num_free);
115
116 err_out_free_bits:
117 simple_free(buddy->bits);
118 return -1;
119 }
120
mlx5dr_buddy_create(uint32_t max_order)121 struct mlx5dr_buddy_mem *mlx5dr_buddy_create(uint32_t max_order)
122 {
123 struct mlx5dr_buddy_mem *buddy;
124
125 buddy = simple_calloc(1, sizeof(*buddy));
126 if (!buddy) {
127 rte_errno = ENOMEM;
128 return NULL;
129 }
130
131 if (mlx5dr_buddy_init(buddy, max_order))
132 goto free_buddy;
133
134 return buddy;
135
136 free_buddy:
137 simple_free(buddy);
138 return NULL;
139 }
140
mlx5dr_buddy_cleanup(struct mlx5dr_buddy_mem * buddy)141 void mlx5dr_buddy_cleanup(struct mlx5dr_buddy_mem *buddy)
142 {
143 int i;
144
145 for (i = 0; i <= (int)buddy->max_order; ++i)
146 rte_free(buddy->bits[i]);
147
148 simple_free(buddy->num_free);
149 simple_free(buddy->bits);
150 }
151
mlx5dr_buddy_alloc_mem(struct mlx5dr_buddy_mem * buddy,int order)152 int mlx5dr_buddy_alloc_mem(struct mlx5dr_buddy_mem *buddy, int order)
153 {
154 int seg;
155 int o, m;
156
157 for (o = order; o <= (int)buddy->max_order; ++o)
158 if (buddy->num_free[o]) {
159 m = 1 << (buddy->max_order - o);
160 seg = mlx5dr_buddy_find_first_bit(buddy->bits[o], m);
161 if (m <= seg)
162 return -1;
163
164 goto found;
165 }
166
167 return -1;
168
169 found:
170 bitmap_clear_bit(buddy->bits[o], seg);
171 --buddy->num_free[o];
172
173 while (o > order) {
174 --o;
175 seg <<= 1;
176 bitmap_set_bit(buddy->bits[o], seg ^ 1);
177 ++buddy->num_free[o];
178 }
179
180 seg <<= order;
181
182 return seg;
183 }
184
mlx5dr_buddy_free_mem(struct mlx5dr_buddy_mem * buddy,uint32_t seg,int order)185 void mlx5dr_buddy_free_mem(struct mlx5dr_buddy_mem *buddy, uint32_t seg, int order)
186 {
187 seg >>= order;
188
189 while (bitmap_test_bit(buddy->bits[order], seg ^ 1)) {
190 bitmap_clear_bit(buddy->bits[order], seg ^ 1);
191 --buddy->num_free[order];
192 seg >>= 1;
193 ++order;
194 }
195
196 bitmap_set_bit(buddy->bits[order], seg);
197
198 ++buddy->num_free[order];
199 }
200
201