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