drivers/net/ethernet/mellanox/mlxsw/spectrum_kvdl.c

   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 }