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