1 /* 1 2 * lib/parman.c - Manager for linear priority 3 * Copyright (c) 2017 Mellanox Technologies. A 4 * Copyright (c) 2017 Jiri Pirko <jiri@mellano 5 * 6 * Redistribution and use in source and binary 7 * modification, are permitted provided that t 8 * 9 * 1. Redistributions of source code must reta 10 * notice, this list of conditions and the 11 * 2. Redistributions in binary form must repr 12 * notice, this list of conditions and the 13 * documentation and/or other materials pro 14 * 3. Neither the names of the copyright holde 15 * contributors may be used to endorse or p 16 * this software without specific prior wri 17 * 18 * Alternatively, this software may be distrib 19 * GNU General Public License ("GPL") version 20 * Software Foundation. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT 23 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCL 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND F 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYR 26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL 27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT L 28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THE 30 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUD 31 * ARISING IN ANY WAY OUT OF THE USE OF THIS S 32 * POSSIBILITY OF SUCH DAMAGE. 33 */ 34 35 #include <linux/kernel.h> 36 #include <linux/module.h> 37 #include <linux/slab.h> 38 #include <linux/export.h> 39 #include <linux/list.h> 40 #include <linux/err.h> 41 #include <linux/parman.h> 42 43 struct parman_algo { 44 int (*item_add)(struct parman *parman, 45 struct parman_item *it 46 void (*item_remove)(struct parman *par 47 struct parman_item 48 }; 49 50 struct parman { 51 const struct parman_ops *ops; 52 void *priv; 53 const struct parman_algo *algo; 54 unsigned long count; 55 unsigned long limit_count; 56 struct list_head prio_list; 57 }; 58 59 static int parman_enlarge(struct parman *parma 60 { 61 unsigned long new_count = parman->limi 62 parman->ops- 63 int err; 64 65 err = parman->ops->resize(parman->priv 66 if (err) 67 return err; 68 parman->limit_count = new_count; 69 return 0; 70 } 71 72 static int parman_shrink(struct parman *parman 73 { 74 unsigned long new_count = parman->limi 75 parman->ops- 76 int err; 77 78 if (new_count < parman->ops->base_coun 79 return 0; 80 err = parman->ops->resize(parman->priv 81 if (err) 82 return err; 83 parman->limit_count = new_count; 84 return 0; 85 } 86 87 static bool parman_prio_used(struct parman_pri 88 { 89 return !list_empty(&prio->item_list); 90 } 91 92 static struct parman_item *parman_prio_first_i 93 { 94 return list_first_entry(&prio->item_li 95 typeof(struct 96 } 97 98 static unsigned long parman_prio_first_index(s 99 { 100 return parman_prio_first_item(prio)->i 101 } 102 103 static struct parman_item *parman_prio_last_it 104 { 105 return list_last_entry(&prio->item_lis 106 typeof(struct p 107 } 108 109 static unsigned long parman_prio_last_index(st 110 { 111 return parman_prio_last_item(prio)->in 112 } 113 114 static unsigned long parman_lsort_new_index_fi 115 116 { 117 list_for_each_entry_from_reverse(prio, 118 if (!parman_prio_used(prio)) 119 continue; 120 return parman_prio_last_index( 121 } 122 return 0; 123 } 124 125 static void __parman_prio_move(struct parman * 126 struct parman_i 127 unsigned long c 128 { 129 parman->ops->move(parman->priv, item-> 130 } 131 132 static void parman_prio_shift_down(struct parm 133 struct parm 134 { 135 struct parman_item *item; 136 unsigned long to_index; 137 138 if (!parman_prio_used(prio)) 139 return; 140 item = parman_prio_first_item(prio); 141 to_index = parman_prio_last_index(prio 142 __parman_prio_move(parman, prio, item, 143 list_move_tail(&item->list, &prio->ite 144 item->index = to_index; 145 } 146 147 static void parman_prio_shift_up(struct parman 148 struct parman 149 { 150 struct parman_item *item; 151 unsigned long to_index; 152 153 if (!parman_prio_used(prio)) 154 return; 155 item = parman_prio_last_item(prio); 156 to_index = parman_prio_first_index(pri 157 __parman_prio_move(parman, prio, item, 158 list_move(&item->list, &prio->item_lis 159 item->index = to_index; 160 } 161 162 static void parman_prio_item_remove(struct par 163 struct par 164 struct par 165 { 166 struct parman_item *last_item; 167 unsigned long to_index; 168 169 last_item = parman_prio_last_item(prio 170 if (last_item == item) { 171 list_del(&item->list); 172 return; 173 } 174 to_index = item->index; 175 __parman_prio_move(parman, prio, last_ 176 list_del(&last_item->list); 177 list_replace(&item->list, &last_item-> 178 last_item->index = to_index; 179 } 180 181 static int parman_lsort_item_add(struct parman 182 struct parman 183 struct parman 184 { 185 struct parman_prio *prio2; 186 unsigned long new_index; 187 int err; 188 189 if (parman->count + 1 > parman->limit_ 190 err = parman_enlarge(parman); 191 if (err) 192 return err; 193 } 194 195 new_index = parman_lsort_new_index_fin 196 list_for_each_entry_reverse(prio2, &pa 197 if (prio2 == prio) 198 break; 199 parman_prio_shift_down(parman, 200 } 201 item->index = new_index; 202 list_add_tail(&item->list, &prio->item 203 parman->count++; 204 return 0; 205 } 206 207 static void parman_lsort_item_remove(struct pa 208 struct pa 209 struct pa 210 { 211 parman_prio_item_remove(parman, prio, 212 list_for_each_entry_continue(prio, &pa 213 parman_prio_shift_up(parman, p 214 parman->count--; 215 if (parman->limit_count - parman->coun 216 parman_shrink(parman); 217 } 218 219 static const struct parman_algo parman_lsort = 220 .item_add = parman_lsort_item_ad 221 .item_remove = parman_lsort_item_re 222 }; 223 224 static const struct parman_algo *parman_algos[ 225 &parman_lsort, 226 }; 227 228 /** 229 * parman_create - creates a new parman instan 230 * @ops: caller-specific callbacks 231 * @priv: pointer to a private data pass 232 * 233 * Note: all locking must be provided by the c 234 * 235 * Each parman instance manages an array area 236 * with the same priority. Consider following 237 * 238 * item 1 with prio 10 239 * item 2 with prio 10 240 * item 3 with prio 10 241 * item 4 with prio 20 242 * item 5 with prio 20 243 * item 6 with prio 30 244 * item 7 with prio 30 245 * item 8 with prio 30 246 * 247 * In this example, there are 3 priority chunk 248 * matters, however the order of items within 249 * matter. So the same array could be ordered 250 * 251 * item 2 with prio 10 252 * item 3 with prio 10 253 * item 1 with prio 10 254 * item 5 with prio 20 255 * item 4 with prio 20 256 * item 7 with prio 30 257 * item 8 with prio 30 258 * item 6 with prio 30 259 * 260 * The goal of parman is to maintain the prior 261 * provides @ops with callbacks parman uses to 262 * and resize the array area. 263 * 264 * Returns a pointer to newly created parman i 265 * otherwise it returns NULL. 266 */ 267 struct parman *parman_create(const struct parm 268 { 269 struct parman *parman; 270 271 parman = kzalloc(sizeof(*parman), GFP_ 272 if (!parman) 273 return NULL; 274 INIT_LIST_HEAD(&parman->prio_list); 275 parman->ops = ops; 276 parman->priv = priv; 277 parman->limit_count = ops->base_count; 278 parman->algo = parman_algos[ops->algo] 279 return parman; 280 } 281 EXPORT_SYMBOL(parman_create); 282 283 /** 284 * parman_destroy - destroys existing parman i 285 * @parman: parman instance 286 * 287 * Note: all locking must be provided by the c 288 */ 289 void parman_destroy(struct parman *parman) 290 { 291 WARN_ON(!list_empty(&parman->prio_list 292 kfree(parman); 293 } 294 EXPORT_SYMBOL(parman_destroy); 295 296 /** 297 * parman_prio_init - initializes a parman pri 298 * @parman: parman instance 299 * @prio: parman prio structure to be in 300 * @priority: desired priority of the chunk 301 * 302 * Note: all locking must be provided by the c 303 * 304 * Before caller could add an item with certai 305 * initialize a priority chunk for it using th 306 */ 307 void parman_prio_init(struct parman *parman, s 308 unsigned long priority) 309 { 310 struct parman_prio *prio2; 311 struct list_head *pos; 312 313 INIT_LIST_HEAD(&prio->item_list); 314 prio->priority = priority; 315 316 /* Position inside the list according 317 list_for_each(pos, &parman->prio_list) 318 prio2 = list_entry(pos, typeof 319 if (prio2->priority > prio->pr 320 break; 321 } 322 list_add_tail(&prio->list, pos); 323 } 324 EXPORT_SYMBOL(parman_prio_init); 325 326 /** 327 * parman_prio_fini - finalizes use of parman 328 * @prio: parman prio structure 329 * 330 * Note: all locking must be provided by the c 331 */ 332 void parman_prio_fini(struct parman_prio *prio 333 { 334 WARN_ON(parman_prio_used(prio)); 335 list_del(&prio->list); 336 } 337 EXPORT_SYMBOL(parman_prio_fini); 338 339 /** 340 * parman_item_add - adds a parman item under 341 * @parman: parman instance 342 * @prio: parman prio instance to add th 343 * @item: parman item instance 344 * 345 * Note: all locking must be provided by the c 346 * 347 * Adds item to a array managed by parman inst 348 * 349 * Returns 0 in case of success, negative numb 350 */ 351 int parman_item_add(struct parman *parman, str 352 struct parman_item *item) 353 { 354 return parman->algo->item_add(parman, 355 } 356 EXPORT_SYMBOL(parman_item_add); 357 358 /** 359 * parman_item_remove - deletes parman item 360 * @parman: parman instance 361 * @prio: parman prio instance to delete 362 * @item: parman item instance 363 * 364 * Note: all locking must be provided by the c 365 */ 366 void parman_item_remove(struct parman *parman, 367 struct parman_item *it 368 { 369 parman->algo->item_remove(parman, prio 370 } 371 EXPORT_SYMBOL(parman_item_remove); 372 373 MODULE_LICENSE("Dual BSD/GPL"); 374 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>" 375 MODULE_DESCRIPTION("Priority-based array manag 376
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.