dr_buddy.c

  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
 10int 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
 49err_out_free_each_bit_per_order:
 50	for (i = 0; i <= buddy->max_order; ++i)
 51		bitmap_free(buddy->bitmap[i]);
 52
 53err_free_all:
 54	kfree(buddy->num_free);
 55	kfree(buddy->bitmap);
 56	return -ENOMEM;
 57}
 58
 59void 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
 72static 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 */
119int 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
150void 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