1 // SPDX-License-Identifier: GPL-2.0 OR Linux-OpenIB
2 /* Copyright (c) 2004 Topspin Communications. All rights reserved.
3 * Copyright (c) 2005 - 2008 Mellanox Technologies. All rights reserved.
4 * Copyright (c) 2006 - 2007 Cisco Systems, Inc. All rights reserved.
5 * Copyright (c) 2020 NVIDIA CORPORATION. All rights reserved.
6 */
7
8 #include "dr_types.h"
9
mlx5dr_buddy_init(struct mlx5dr_icm_buddy_mem * buddy,unsigned int max_order)10 int mlx5dr_buddy_init(struct mlx5dr_icm_buddy_mem *buddy,
11 unsigned int max_order)
12 {
13 int i;
14
15 buddy->max_order = max_order;
16
17 INIT_LIST_HEAD(&buddy->list_node);
18
19 buddy->bitmap = kcalloc(buddy->max_order + 1,
20 sizeof(*buddy->bitmap),
21 GFP_KERNEL);
22 buddy->num_free = kcalloc(buddy->max_order + 1,
23 sizeof(*buddy->num_free),
24 GFP_KERNEL);
25
26 if (!buddy->bitmap || !buddy->num_free)
27 goto err_free_all;
28
29 /* Allocating max_order bitmaps, one for each order */
30
31 for (i = 0; i <= buddy->max_order; ++i) {
32 unsigned int size = 1 << (buddy->max_order - i);
33
34 buddy->bitmap[i] = bitmap_zalloc(size, GFP_KERNEL);
35 if (!buddy->bitmap[i])
36 goto err_out_free_each_bit_per_order;
37 }
38
39 /* In the beginning, we have only one order that is available for
40 * use (the biggest one), so mark the first bit in both bitmaps.
41 */
42
43 bitmap_set(buddy->bitmap[buddy->max_order], 0, 1);
44
45 buddy->num_free[buddy->max_order] = 1;
46
47 return 0;
48
49 err_out_free_each_bit_per_order:
50 for (i = 0; i <= buddy->max_order; ++i)
51 bitmap_free(buddy->bitmap[i]);
52
53 err_free_all:
54 kfree(buddy->num_free);
55 kfree(buddy->bitmap);
56 return -ENOMEM;
57 }
58
mlx5dr_buddy_cleanup(struct mlx5dr_icm_buddy_mem * buddy)59 void mlx5dr_buddy_cleanup(struct mlx5dr_icm_buddy_mem *buddy)
60 {
61 int i;
62
63 list_del(&buddy->list_node);
64
65 for (i = 0; i <= buddy->max_order; ++i)
66 bitmap_free(buddy->bitmap[i]);
67
68 kfree(buddy->num_free);
69 kfree(buddy->bitmap);
70 }
71
dr_buddy_find_free_seg(struct mlx5dr_icm_buddy_mem * buddy,unsigned int start_order,unsigned int * segment,unsigned int * order)72 static int dr_buddy_find_free_seg(struct mlx5dr_icm_buddy_mem *buddy,
73 unsigned int start_order,
74 unsigned int *segment,
75 unsigned int *order)
76 {
77 unsigned int seg, order_iter, m;
78
79 for (order_iter = start_order;
80 order_iter <= buddy->max_order; ++order_iter) {
81 if (!buddy->num_free[order_iter])
82 continue;
83
84 m = 1 << (buddy->max_order - order_iter);
85 seg = find_first_bit(buddy->bitmap[order_iter], m);
86
87 if (WARN(seg >= m,
88 "ICM Buddy: failed finding free mem for order %d\n",
89 order_iter))
90 return -ENOMEM;
91
92 break;
93 }
94
95 if (order_iter > buddy->max_order)
96 return -ENOMEM;
97
98 *segment = seg;
99 *order = order_iter;
100 return 0;
101 }
102
103 /**
104 * mlx5dr_buddy_alloc_mem() - Update second level bitmap.
105 * @buddy: Buddy to update.
106 * @order: Order of the buddy to update.
107 * @segment: Segment number.
108 *
109 * This function finds the first area of the ICM memory managed by this buddy.
110 * It uses the data structures of the buddy system in order to find the first
111 * area of free place, starting from the current order till the maximum order
112 * in the system.
113 *
114 * Return: 0 when segment is set, non-zero error status otherwise.
115 *
116 * The function returns the location (segment) in the whole buddy ICM memory
117 * area - the index of the memory segment that is available for use.
118 */
mlx5dr_buddy_alloc_mem(struct mlx5dr_icm_buddy_mem * buddy,unsigned int order,unsigned int * segment)119 int mlx5dr_buddy_alloc_mem(struct mlx5dr_icm_buddy_mem *buddy,
120 unsigned int order,
121 unsigned int *segment)
122 {
123 unsigned int seg, order_iter;
124 int err;
125
126 err = dr_buddy_find_free_seg(buddy, order, &seg, &order_iter);
127 if (err)
128 return err;
129
130 bitmap_clear(buddy->bitmap[order_iter], seg, 1);
131 --buddy->num_free[order_iter];
132
133 /* If we found free memory in some order that is bigger than the
134 * required order, we need to split every order between the required
135 * order and the order that we found into two parts, and mark accordingly.
136 */
137 while (order_iter > order) {
138 --order_iter;
139 seg <<= 1;
140 bitmap_set(buddy->bitmap[order_iter], seg ^ 1, 1);
141 ++buddy->num_free[order_iter];
142 }
143
144 seg <<= order;
145 *segment = seg;
146
147 return 0;
148 }
149
mlx5dr_buddy_free_mem(struct mlx5dr_icm_buddy_mem * buddy,unsigned int seg,unsigned int order)150 void mlx5dr_buddy_free_mem(struct mlx5dr_icm_buddy_mem *buddy,
151 unsigned int seg, unsigned int order)
152 {
153 seg >>= order;
154
155 /* Whenever a segment is free,
156 * the mem is added to the buddy that gave it.
157 */
158 while (test_bit(seg ^ 1, buddy->bitmap[order])) {
159 bitmap_clear(buddy->bitmap[order], seg ^ 1, 1);
160 --buddy->num_free[order];
161 seg >>= 1;
162 ++order;
163 }
164 bitmap_set(buddy->bitmap[order], seg, 1);
165
166 ++buddy->num_free[order];
167 }
168
169