buddy.c

  1// SPDX-License-Identifier: GPL-2.0 OR Linux-OpenIB
  2/* Copyright (c) 2024 NVIDIA Corporation & Affiliates */
  3
  4#include "internal.h"
  5#include "buddy.h"
  6
  7static int hws_buddy_init(struct mlx5hws_buddy_mem *buddy, u32 max_order)
  8{
  9	int i, s, ret = 0;
 10
 11	buddy->max_order = max_order;
 12
 13	buddy->bitmap = kcalloc(buddy->max_order + 1,
 14				sizeof(*buddy->bitmap),
 15				GFP_KERNEL);
 16	if (!buddy->bitmap)
 17		return -ENOMEM;
 18
 19	buddy->num_free = kcalloc(buddy->max_order + 1,
 20				  sizeof(*buddy->num_free),
 21				  GFP_KERNEL);
 22	if (!buddy->num_free) {
 23		ret = -ENOMEM;
 24		goto err_out_free_bits;
 25	}
 26
 27	for (i = 0; i <= (int)buddy->max_order; ++i) {
 28		s = 1 << (buddy->max_order - i);
 29
 30		buddy->bitmap[i] = bitmap_zalloc(s, GFP_KERNEL);
 31		if (!buddy->bitmap[i]) {
 32			ret = -ENOMEM;
 33			goto err_out_free_num_free;
 34		}
 35	}
 36
 37	bitmap_set(buddy->bitmap[buddy->max_order], 0, 1);
 38	buddy->num_free[buddy->max_order] = 1;
 39
 40	return 0;
 41
 42err_out_free_num_free:
 43	for (i = 0; i <= (int)buddy->max_order; ++i)
 44		bitmap_free(buddy->bitmap[i]);
 45
 46	kfree(buddy->num_free);
 47
 48err_out_free_bits:
 49	kfree(buddy->bitmap);
 50	return ret;
 51}
 52
 53struct mlx5hws_buddy_mem *mlx5hws_buddy_create(u32 max_order)
 54{
 55	struct mlx5hws_buddy_mem *buddy;
 56
 57	buddy = kzalloc(sizeof(*buddy), GFP_KERNEL);
 58	if (!buddy)
 59		return NULL;
 60
 61	if (hws_buddy_init(buddy, max_order))
 62		goto free_buddy;
 63
 64	return buddy;
 65
 66free_buddy:
 67	kfree(buddy);
 68	return NULL;
 69}
 70
 71void mlx5hws_buddy_cleanup(struct mlx5hws_buddy_mem *buddy)
 72{
 73	int i;
 74
 75	for (i = 0; i <= (int)buddy->max_order; ++i)
 76		bitmap_free(buddy->bitmap[i]);
 77
 78	kfree(buddy->num_free);
 79	kfree(buddy->bitmap);
 80}
 81
 82static int hws_buddy_find_free_seg(struct mlx5hws_buddy_mem *buddy,
 83				   u32 start_order,
 84				   u32 *segment,
 85				   u32 *order)
 86{
 87	unsigned int seg, order_iter, m;
 88
 89	for (order_iter = start_order;
 90	     order_iter <= buddy->max_order; ++order_iter) {
 91		if (!buddy->num_free[order_iter])
 92			continue;
 93
 94		m = 1 << (buddy->max_order - order_iter);
 95		seg = find_first_bit(buddy->bitmap[order_iter], m);
 96
 97		if (WARN(seg >= m,
 98			 "ICM Buddy: failed finding free mem for order %d\n",
 99			 order_iter))
100			return -ENOMEM;
101
102		break;
103	}
104
105	if (order_iter > buddy->max_order)
106		return -ENOMEM;
107
108	*segment = seg;
109	*order = order_iter;
110	return 0;
111}
112
113int mlx5hws_buddy_alloc_mem(struct mlx5hws_buddy_mem *buddy, u32 order)
114{
115	u32 seg, order_iter, err;
116
117	err = hws_buddy_find_free_seg(buddy, order, &seg, &order_iter);
118	if (err)
119		return err;
120
121	bitmap_clear(buddy->bitmap[order_iter], seg, 1);
122	--buddy->num_free[order_iter];
123
124	while (order_iter > order) {
125		--order_iter;
126		seg <<= 1;
127		bitmap_set(buddy->bitmap[order_iter], seg ^ 1, 1);
128		++buddy->num_free[order_iter];
129	}
130
131	seg <<= order;
132
133	return seg;
134}
135
136void mlx5hws_buddy_free_mem(struct mlx5hws_buddy_mem *buddy, u32 seg, u32 order)
137{
138	seg >>= order;
139
140	while (test_bit(seg ^ 1, buddy->bitmap[order])) {
141		bitmap_clear(buddy->bitmap[order], seg ^ 1, 1);
142		--buddy->num_free[order];
143		seg >>= 1;
144		++order;
145	}
146
147	bitmap_set(buddy->bitmap[order], seg, 1);
148	++buddy->num_free[order];
149}