1 // SPDX-License-Identifier: GPL-2.0 2 #include <stdlib.h> 3 #include <string.h> 4 #include <malloc.h> 5 #include <pthread.h> 6 #include <unistd.h> 7 #include <assert.h> 8 9 #include <linux/gfp.h> 10 #include <linux/poison.h> 11 #include <linux/slab.h> 12 #include <linux/radix-tree.h> 13 #include <urcu/uatomic.h> 14 15 int nr_allocated; 16 int preempt_count; 17 int test_verbose; 18 19 void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *)) 20 { 21 cachep->callback = callback; 22 } 23 24 void kmem_cache_set_private(struct kmem_cache *cachep, void *private) 25 { 26 cachep->private = private; 27 } 28 29 void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val) 30 { 31 cachep->non_kernel = val; 32 } 33 34 unsigned long kmem_cache_get_alloc(struct kmem_cache *cachep) 35 { 36 return cachep->size * cachep->nr_allocated; 37 } 38 39 unsigned long kmem_cache_nr_allocated(struct kmem_cache *cachep) 40 { 41 return cachep->nr_allocated; 42 } 43 44 unsigned long kmem_cache_nr_tallocated(struct kmem_cache *cachep) 45 { 46 return cachep->nr_tallocated; 47 } 48 49 void kmem_cache_zero_nr_tallocated(struct kmem_cache *cachep) 50 { 51 cachep->nr_tallocated = 0; 52 } 53 54 void *kmem_cache_alloc_lru(struct kmem_cache *cachep, struct list_lru *lru, 55 int gfp) 56 { 57 void *p; 58 59 if (cachep->exec_callback) { 60 if (cachep->callback) 61 cachep->callback(cachep->private); 62 cachep->exec_callback = false; 63 } 64 65 if (!(gfp & __GFP_DIRECT_RECLAIM)) { 66 if (!cachep->non_kernel) { 67 cachep->exec_callback = true; 68 return NULL; 69 } 70 71 cachep->non_kernel--; 72 } 73 74 pthread_mutex_lock(&cachep->lock); 75 if (cachep->nr_objs) { 76 struct radix_tree_node *node = cachep->objs; 77 cachep->nr_objs--; 78 cachep->objs = node->parent; 79 pthread_mutex_unlock(&cachep->lock); 80 node->parent = NULL; 81 p = node; 82 } else { 83 pthread_mutex_unlock(&cachep->lock); 84 if (cachep->align) { 85 if (posix_memalign(&p, cachep->align, cachep->size) < 0) 86 return NULL; 87 } else { 88 p = malloc(cachep->size); 89 } 90 91 if (cachep->ctor) 92 cachep->ctor(p); 93 else if (gfp & __GFP_ZERO) 94 memset(p, 0, cachep->size); 95 } 96 97 uatomic_inc(&cachep->nr_allocated); 98 uatomic_inc(&nr_allocated); 99 uatomic_inc(&cachep->nr_tallocated); 100 if (kmalloc_verbose) 101 printf("Allocating %p from slab\n", p); 102 return p; 103 } 104 105 void __kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) 106 { 107 assert(objp); 108 if (cachep->nr_objs > 10 || cachep->align) { 109 memset(objp, POISON_FREE, cachep->size); 110 free(objp); 111 } else { 112 struct radix_tree_node *node = objp; 113 cachep->nr_objs++; 114 node->parent = cachep->objs; 115 cachep->objs = node; 116 } 117 } 118 119 void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) 120 { 121 uatomic_dec(&nr_allocated); 122 uatomic_dec(&cachep->nr_allocated); 123 if (kmalloc_verbose) 124 printf("Freeing %p to slab\n", objp); 125 __kmem_cache_free_locked(cachep, objp); 126 } 127 128 void kmem_cache_free(struct kmem_cache *cachep, void *objp) 129 { 130 pthread_mutex_lock(&cachep->lock); 131 kmem_cache_free_locked(cachep, objp); 132 pthread_mutex_unlock(&cachep->lock); 133 } 134 135 void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list) 136 { 137 if (kmalloc_verbose) 138 pr_debug("Bulk free %p[0-%zu]\n", list, size - 1); 139 140 if (cachep->exec_callback) { 141 if (cachep->callback) 142 cachep->callback(cachep->private); 143 cachep->exec_callback = false; 144 } 145 146 pthread_mutex_lock(&cachep->lock); 147 for (int i = 0; i < size; i++) 148 kmem_cache_free_locked(cachep, list[i]); 149 pthread_mutex_unlock(&cachep->lock); 150 } 151 152 void kmem_cache_shrink(struct kmem_cache *cachep) 153 { 154 } 155 156 int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, 157 void **p) 158 { 159 size_t i; 160 161 if (kmalloc_verbose) 162 pr_debug("Bulk alloc %zu\n", size); 163 164 pthread_mutex_lock(&cachep->lock); 165 if (cachep->nr_objs >= size) { 166 struct radix_tree_node *node; 167 168 for (i = 0; i < size; i++) { 169 if (!(gfp & __GFP_DIRECT_RECLAIM)) { 170 if (!cachep->non_kernel) 171 break; 172 cachep->non_kernel--; 173 } 174 175 node = cachep->objs; 176 cachep->nr_objs--; 177 cachep->objs = node->parent; 178 p[i] = node; 179 node->parent = NULL; 180 } 181 pthread_mutex_unlock(&cachep->lock); 182 } else { 183 pthread_mutex_unlock(&cachep->lock); 184 for (i = 0; i < size; i++) { 185 if (!(gfp & __GFP_DIRECT_RECLAIM)) { 186 if (!cachep->non_kernel) 187 break; 188 cachep->non_kernel--; 189 } 190 191 if (cachep->align) { 192 if (posix_memalign(&p[i], cachep->align, 193 cachep->size) < 0) 194 break; 195 } else { 196 p[i] = malloc(cachep->size); 197 if (!p[i]) 198 break; 199 } 200 if (cachep->ctor) 201 cachep->ctor(p[i]); 202 else if (gfp & __GFP_ZERO) 203 memset(p[i], 0, cachep->size); 204 } 205 } 206 207 if (i < size) { 208 size = i; 209 pthread_mutex_lock(&cachep->lock); 210 for (i = 0; i < size; i++) 211 __kmem_cache_free_locked(cachep, p[i]); 212 pthread_mutex_unlock(&cachep->lock); 213 return 0; 214 } 215 216 for (i = 0; i < size; i++) { 217 uatomic_inc(&nr_allocated); 218 uatomic_inc(&cachep->nr_allocated); 219 uatomic_inc(&cachep->nr_tallocated); 220 if (kmalloc_verbose) 221 printf("Allocating %p from slab\n", p[i]); 222 } 223 224 return size; 225 } 226 227 struct kmem_cache * 228 __kmem_cache_create_args(const char *name, unsigned int size, 229 struct kmem_cache_args *args, 230 unsigned int flags) 231 { 232 struct kmem_cache *ret = malloc(sizeof(*ret)); 233 234 pthread_mutex_init(&ret->lock, NULL); 235 ret->size = size; 236 ret->align = args->align; 237 ret->sheaf_capacity = args->sheaf_capacity; 238 ret->nr_objs = 0; 239 ret->nr_allocated = 0; 240 ret->nr_tallocated = 0; 241 ret->objs = NULL; 242 ret->ctor = args->ctor; 243 ret->non_kernel = 0; 244 ret->exec_callback = false; 245 ret->callback = NULL; 246 ret->private = NULL; 247 248 return ret; 249 } 250 251 struct slab_sheaf * 252 kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size) 253 { 254 struct slab_sheaf *sheaf; 255 unsigned int capacity; 256 257 if (s->exec_callback) { 258 if (s->callback) 259 s->callback(s->private); 260 s->exec_callback = false; 261 } 262 263 capacity = max(size, s->sheaf_capacity); 264 265 sheaf = calloc(1, sizeof(*sheaf) + sizeof(void *) * capacity); 266 if (!sheaf) 267 return NULL; 268 269 sheaf->cache = s; 270 sheaf->capacity = capacity; 271 sheaf->size = kmem_cache_alloc_bulk(s, gfp, size, sheaf->objects); 272 if (!sheaf->size) { 273 free(sheaf); 274 return NULL; 275 } 276 277 return sheaf; 278 } 279 280 int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp, 281 struct slab_sheaf **sheafp, unsigned int size) 282 { 283 struct slab_sheaf *sheaf = *sheafp; 284 int refill; 285 286 if (sheaf->size >= size) 287 return 0; 288 289 if (size > sheaf->capacity) { 290 sheaf = kmem_cache_prefill_sheaf(s, gfp, size); 291 if (!sheaf) 292 return -ENOMEM; 293 294 kmem_cache_return_sheaf(s, gfp, *sheafp); 295 *sheafp = sheaf; 296 return 0; 297 } 298 299 refill = kmem_cache_alloc_bulk(s, gfp, size - sheaf->size, 300 &sheaf->objects[sheaf->size]); 301 if (!refill) 302 return -ENOMEM; 303 304 sheaf->size += refill; 305 return 0; 306 } 307 308 void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp, 309 struct slab_sheaf *sheaf) 310 { 311 if (sheaf->size) 312 kmem_cache_free_bulk(s, sheaf->size, &sheaf->objects[0]); 313 314 free(sheaf); 315 } 316 317 void * 318 kmem_cache_alloc_from_sheaf(struct kmem_cache *s, gfp_t gfp, 319 struct slab_sheaf *sheaf) 320 { 321 void *obj; 322 323 if (sheaf->size == 0) { 324 printf("Nothing left in sheaf!\n"); 325 return NULL; 326 } 327 328 obj = sheaf->objects[--sheaf->size]; 329 sheaf->objects[sheaf->size] = NULL; 330 331 return obj; 332 } 333 334 /* 335 * Test the test infrastructure for kem_cache_alloc/free and bulk counterparts. 336 */ 337 void test_kmem_cache_bulk(void) 338 { 339 int i; 340 void *list[12]; 341 static struct kmem_cache *test_cache, *test_cache2; 342 343 /* 344 * Testing the bulk allocators without aligned kmem_cache to force the 345 * bulk alloc/free to reuse 346 */ 347 test_cache = kmem_cache_create("test_cache", 256, 0, SLAB_PANIC, NULL); 348 349 for (i = 0; i < 5; i++) 350 list[i] = kmem_cache_alloc(test_cache, __GFP_DIRECT_RECLAIM); 351 352 for (i = 0; i < 5; i++) 353 kmem_cache_free(test_cache, list[i]); 354 assert(test_cache->nr_objs == 5); 355 356 kmem_cache_alloc_bulk(test_cache, __GFP_DIRECT_RECLAIM, 5, list); 357 kmem_cache_free_bulk(test_cache, 5, list); 358 359 for (i = 0; i < 12 ; i++) 360 list[i] = kmem_cache_alloc(test_cache, __GFP_DIRECT_RECLAIM); 361 362 for (i = 0; i < 12; i++) 363 kmem_cache_free(test_cache, list[i]); 364 365 /* The last free will not be kept around */ 366 assert(test_cache->nr_objs == 11); 367 368 /* Aligned caches will immediately free */ 369 test_cache2 = kmem_cache_create("test_cache2", 128, 128, SLAB_PANIC, NULL); 370 371 kmem_cache_alloc_bulk(test_cache2, __GFP_DIRECT_RECLAIM, 10, list); 372 kmem_cache_free_bulk(test_cache2, 10, list); 373 assert(!test_cache2->nr_objs); 374 375 376 } 377