1 /* 2 * drivers/net/ethernet/mellanox/mlxsw/spectrum_kvdl.c 3 * Copyright (c) 2016 Mellanox Technologies. All rights reserved. 4 * Copyright (c) 2016 Jiri Pirko <jiri@mellanox.com> 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. Neither the names of the copyright holders nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * Alternatively, this software may be distributed under the terms of the 19 * GNU General Public License ("GPL") version 2 as published by the Free 20 * Software Foundation. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 23 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 30 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 31 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 32 * POSSIBILITY OF SUCH DAMAGE. 33 */ 34 35 #include <linux/kernel.h> 36 #include <linux/bitops.h> 37 38 #include "spectrum.h" 39 40 #define MLXSW_SP_KVDL_SINGLE_BASE 0 41 #define MLXSW_SP_KVDL_SINGLE_SIZE 16384 42 #define MLXSW_SP_KVDL_SINGLE_END \ 43 (MLXSW_SP_KVDL_SINGLE_SIZE + MLXSW_SP_KVDL_SINGLE_BASE - 1) 44 45 #define MLXSW_SP_KVDL_CHUNKS_BASE \ 46 (MLXSW_SP_KVDL_SINGLE_BASE + MLXSW_SP_KVDL_SINGLE_SIZE) 47 #define MLXSW_SP_KVDL_CHUNKS_SIZE 49152 48 #define MLXSW_SP_KVDL_CHUNKS_END \ 49 (MLXSW_SP_KVDL_CHUNKS_SIZE + MLXSW_SP_KVDL_CHUNKS_BASE - 1) 50 51 #define MLXSW_SP_KVDL_LARGE_CHUNKS_BASE \ 52 (MLXSW_SP_KVDL_CHUNKS_BASE + MLXSW_SP_KVDL_CHUNKS_SIZE) 53 #define MLXSW_SP_KVDL_LARGE_CHUNKS_SIZE \ 54 (MLXSW_SP_KVD_LINEAR_SIZE - MLXSW_SP_KVDL_LARGE_CHUNKS_BASE) 55 #define MLXSW_SP_KVDL_LARGE_CHUNKS_END \ 56 (MLXSW_SP_KVDL_LARGE_CHUNKS_SIZE + MLXSW_SP_KVDL_LARGE_CHUNKS_BASE - 1) 57 58 #define MLXSW_SP_CHUNK_MAX 32 59 #define MLXSW_SP_LARGE_CHUNK_MAX 512 60 61 struct mlxsw_sp_kvdl_part_info { 62 unsigned int part_index; 63 unsigned int start_index; 64 unsigned int end_index; 65 unsigned int alloc_size; 66 }; 67 68 struct mlxsw_sp_kvdl_part { 69 struct list_head list; 70 const struct mlxsw_sp_kvdl_part_info *info; 71 unsigned long usage[0]; /* Entries */ 72 }; 73 74 struct mlxsw_sp_kvdl { 75 struct list_head parts_list; 76 }; 77 78 static struct mlxsw_sp_kvdl_part * 79 mlxsw_sp_kvdl_alloc_size_part(struct mlxsw_sp_kvdl *kvdl, 80 unsigned int alloc_size) 81 { 82 struct mlxsw_sp_kvdl_part *part, *min_part = NULL; 83 84 list_for_each_entry(part, &kvdl->parts_list, list) { 85 if (alloc_size <= part->info->alloc_size && 86 (!min_part || 87 part->info->alloc_size <= min_part->info->alloc_size)) 88 min_part = part; 89 } 90 91 return min_part ?: ERR_PTR(-ENOBUFS); 92 } 93 94 static struct mlxsw_sp_kvdl_part * 95 mlxsw_sp_kvdl_index_part(struct mlxsw_sp_kvdl *kvdl, u32 kvdl_index) 96 { 97 struct mlxsw_sp_kvdl_part *part; 98 99 list_for_each_entry(part, &kvdl->parts_list, list) { 100 if (kvdl_index >= part->info->start_index && 101 kvdl_index <= part->info->end_index) 102 return part; 103 } 104 105 return ERR_PTR(-EINVAL); 106 } 107 108 static u32 109 mlxsw_sp_entry_index_kvdl_index(const struct mlxsw_sp_kvdl_part_info *info, 110 unsigned int entry_index) 111 { 112 return info->start_index + entry_index * info->alloc_size; 113 } 114 115 static unsigned int 116 mlxsw_sp_kvdl_index_entry_index(const struct mlxsw_sp_kvdl_part_info *info, 117 u32 kvdl_index) 118 { 119 return (kvdl_index - info->start_index) / info->alloc_size; 120 } 121 122 static int mlxsw_sp_kvdl_part_alloc(struct mlxsw_sp_kvdl_part *part, 123 u32 *p_kvdl_index) 124 { 125 const struct mlxsw_sp_kvdl_part_info *info = part->info; 126 unsigned int entry_index, nr_entries; 127 128 nr_entries = (info->end_index - info->start_index + 1) / 129 info->alloc_size; 130 entry_index = find_first_zero_bit(part->usage, nr_entries); 131 if (entry_index == nr_entries) 132 return -ENOBUFS; 133 __set_bit(entry_index, part->usage); 134 135 *p_kvdl_index = mlxsw_sp_entry_index_kvdl_index(part->info, 136 entry_index); 137 138 return 0; 139 } 140 141 static void mlxsw_sp_kvdl_part_free(struct mlxsw_sp_kvdl_part *part, 142 u32 kvdl_index) 143 { 144 unsigned int entry_index; 145 146 entry_index = mlxsw_sp_kvdl_index_entry_index(part->info, 147 kvdl_index); 148 __clear_bit(entry_index, part->usage); 149 } 150 151 int mlxsw_sp_kvdl_alloc(struct mlxsw_sp *mlxsw_sp, unsigned int entry_count, 152 u32 *p_entry_index) 153 { 154 struct mlxsw_sp_kvdl_part *part; 155 156 /* Find partition with smallest allocation size satisfying the 157 * requested size. 158 */ 159 part = mlxsw_sp_kvdl_alloc_size_part(mlxsw_sp->kvdl, entry_count); 160 if (IS_ERR(part)) 161 return PTR_ERR(part); 162 163 return mlxsw_sp_kvdl_part_alloc(part, p_entry_index); 164 } 165 166 void mlxsw_sp_kvdl_free(struct mlxsw_sp *mlxsw_sp, int entry_index) 167 { 168 struct mlxsw_sp_kvdl_part *part; 169 170 part = mlxsw_sp_kvdl_index_part(mlxsw_sp->kvdl, entry_index); 171 if (IS_ERR(part)) 172 return; 173 mlxsw_sp_kvdl_part_free(part, entry_index); 174 } 175 176 int mlxsw_sp_kvdl_alloc_size_query(struct mlxsw_sp *mlxsw_sp, 177 unsigned int entry_count, 178 unsigned int *p_alloc_size) 179 { 180 struct mlxsw_sp_kvdl_part *part; 181 182 part = mlxsw_sp_kvdl_alloc_size_part(mlxsw_sp->kvdl, entry_count); 183 if (IS_ERR(part)) 184 return PTR_ERR(part); 185 186 *p_alloc_size = part->info->alloc_size; 187 188 return 0; 189 } 190 191 static const struct mlxsw_sp_kvdl_part_info kvdl_parts_info[] = { 192 { 193 .part_index = 0, 194 .start_index = MLXSW_SP_KVDL_SINGLE_BASE, 195 .end_index = MLXSW_SP_KVDL_SINGLE_END, 196 .alloc_size = 1, 197 }, 198 { 199 .part_index = 1, 200 .start_index = MLXSW_SP_KVDL_CHUNKS_BASE, 201 .end_index = MLXSW_SP_KVDL_CHUNKS_END, 202 .alloc_size = MLXSW_SP_CHUNK_MAX, 203 }, 204 { 205 .part_index = 2, 206 .start_index = MLXSW_SP_KVDL_LARGE_CHUNKS_BASE, 207 .end_index = MLXSW_SP_KVDL_LARGE_CHUNKS_END, 208 .alloc_size = MLXSW_SP_LARGE_CHUNK_MAX, 209 }, 210 }; 211 212 static struct mlxsw_sp_kvdl_part * 213 mlxsw_sp_kvdl_part_find(struct mlxsw_sp *mlxsw_sp, unsigned int part_index) 214 { 215 struct mlxsw_sp_kvdl_part *part; 216 217 list_for_each_entry(part, &mlxsw_sp->kvdl->parts_list, list) { 218 if (part->info->part_index == part_index) 219 return part; 220 } 221 222 return NULL; 223 } 224 225 static int mlxsw_sp_kvdl_part_init(struct mlxsw_sp *mlxsw_sp, 226 unsigned int part_index) 227 { 228 const struct mlxsw_sp_kvdl_part_info *info; 229 struct mlxsw_sp_kvdl_part *part; 230 unsigned int nr_entries; 231 size_t usage_size; 232 233 info = &kvdl_parts_info[part_index]; 234 235 nr_entries = (info->end_index - info->start_index + 1) / 236 info->alloc_size; 237 usage_size = BITS_TO_LONGS(nr_entries) * sizeof(unsigned long); 238 part = kzalloc(sizeof(*part) + usage_size, GFP_KERNEL); 239 if (!part) 240 return -ENOMEM; 241 242 part->info = info; 243 list_add(&part->list, &mlxsw_sp->kvdl->parts_list); 244 245 return 0; 246 } 247 248 static void mlxsw_sp_kvdl_part_fini(struct mlxsw_sp *mlxsw_sp, 249 unsigned int part_index) 250 { 251 struct mlxsw_sp_kvdl_part *part; 252 253 part = mlxsw_sp_kvdl_part_find(mlxsw_sp, part_index); 254 if (!part) 255 return; 256 257 list_del(&part->list); 258 kfree(part); 259 } 260 261 static int mlxsw_sp_kvdl_parts_init(struct mlxsw_sp *mlxsw_sp) 262 { 263 int err, i; 264 265 INIT_LIST_HEAD(&mlxsw_sp->kvdl->parts_list); 266 267 for (i = 0; i < ARRAY_SIZE(kvdl_parts_info); i++) { 268 err = mlxsw_sp_kvdl_part_init(mlxsw_sp, i); 269 if (err) 270 goto err_kvdl_part_init; 271 } 272 273 return 0; 274 275 err_kvdl_part_init: 276 for (i--; i >= 0; i--) 277 mlxsw_sp_kvdl_part_fini(mlxsw_sp, i); 278 return err; 279 } 280 281 static void mlxsw_sp_kvdl_parts_fini(struct mlxsw_sp *mlxsw_sp) 282 { 283 int i; 284 285 for (i = ARRAY_SIZE(kvdl_parts_info) - 1; i >= 0; i--) 286 mlxsw_sp_kvdl_part_fini(mlxsw_sp, i); 287 } 288 289 static u64 mlxsw_sp_kvdl_part_occ(struct mlxsw_sp_kvdl_part *part) 290 { 291 unsigned int nr_entries; 292 int bit = -1; 293 u64 occ = 0; 294 295 nr_entries = (part->info->end_index - 296 part->info->start_index + 1) / 297 part->info->alloc_size; 298 while ((bit = find_next_bit(part->usage, nr_entries, bit + 1)) 299 < nr_entries) 300 occ += part->info->alloc_size; 301 return occ; 302 } 303 304 u64 mlxsw_sp_kvdl_occ_get(const struct mlxsw_sp *mlxsw_sp) 305 { 306 struct mlxsw_sp_kvdl_part *part; 307 u64 occ = 0; 308 309 list_for_each_entry(part, &mlxsw_sp->kvdl->parts_list, list) 310 occ += mlxsw_sp_kvdl_part_occ(part); 311 312 return occ; 313 } 314 315 int mlxsw_sp_kvdl_init(struct mlxsw_sp *mlxsw_sp) 316 { 317 struct mlxsw_sp_kvdl *kvdl; 318 int err; 319 320 kvdl = kzalloc(sizeof(*mlxsw_sp->kvdl), GFP_KERNEL); 321 if (!kvdl) 322 return -ENOMEM; 323 mlxsw_sp->kvdl = kvdl; 324 325 err = mlxsw_sp_kvdl_parts_init(mlxsw_sp); 326 if (err) 327 goto err_kvdl_parts_init; 328 329 return 0; 330 331 err_kvdl_parts_init: 332 kfree(mlxsw_sp->kvdl); 333 return err; 334 } 335 336 void mlxsw_sp_kvdl_fini(struct mlxsw_sp *mlxsw_sp) 337 { 338 mlxsw_sp_kvdl_parts_fini(mlxsw_sp); 339 kfree(mlxsw_sp->kvdl); 340 } 341