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