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 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 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 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 */ 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 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