lsquic_malo.c revision a74702c6
1a74702c6SGeorge Wang/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc. See LICENSE. */ 250aadb33SDmitri Tikhonov/* 350aadb33SDmitri Tikhonov * lsquic_malo.c -- malo allocator implementation. 450aadb33SDmitri Tikhonov * 550aadb33SDmitri Tikhonov * The malo allocator is a pool of objects of fixed size. It tries to 650aadb33SDmitri Tikhonov * allocate and deallocate objects as fast as possible. To do so, it 750aadb33SDmitri Tikhonov * does the following: 850aadb33SDmitri Tikhonov * 950aadb33SDmitri Tikhonov * 1. Allocations occur 4 KB at a time. 105392f7a3SLiteSpeed Tech * 2. No division or multiplication operations are performed for 115392f7a3SLiteSpeed Tech * appropriately sized objects. (More on this below.) 1250aadb33SDmitri Tikhonov * 1350aadb33SDmitri Tikhonov * (In recent testing, malo was about 2.7 times faster than malloc for 1450aadb33SDmitri Tikhonov * 64-byte objects.) 1550aadb33SDmitri Tikhonov * 1650aadb33SDmitri Tikhonov * Besides speed, two other important characteristics distinguish it 1750aadb33SDmitri Tikhonov * from other pool allocators: 1850aadb33SDmitri Tikhonov * 1950aadb33SDmitri Tikhonov * 1. To free (put) an object, one does not need a pointer to the malo 2050aadb33SDmitri Tikhonov * object. This makes this allocator easy to use. 2150aadb33SDmitri Tikhonov * 2. A built-in iterator is provided to iterate over all allocated 225392f7a3SLiteSpeed Tech * objects (with ability safely to release objects while iterator 2350aadb33SDmitri Tikhonov * is active). This may be useful in some circumstances. 2450aadb33SDmitri Tikhonov * 2550aadb33SDmitri Tikhonov * To gain all these advantages, there are trade-offs: 2650aadb33SDmitri Tikhonov * 2750aadb33SDmitri Tikhonov * 1. There are two memory penalties: 285392f7a3SLiteSpeed Tech * a. Per object overhead. If an object is at least ROUNDUP_THRESH in 295392f7a3SLiteSpeed Tech * size as the next power of two, the allocator uses that power of 305392f7a3SLiteSpeed Tech * two value as the object size. This is done to avoid using 315392f7a3SLiteSpeed Tech * division and multiplication. For example, a 104-byte object 325392f7a3SLiteSpeed Tech * will have a 24-byte overhead. 3350aadb33SDmitri Tikhonov * b. Per page overhead. Page links occupy some bytes in the 3450aadb33SDmitri Tikhonov * page. To keep things fast, at least one slot per page is 3550aadb33SDmitri Tikhonov * always occupied, independent of object size. Thus, for a 3650aadb33SDmitri Tikhonov * 1 KB object size, 25% of the page is used for the page 3750aadb33SDmitri Tikhonov * header. 3850aadb33SDmitri Tikhonov * 2. 4 KB pages are not freed until the malo allocator is destroyed. 3950aadb33SDmitri Tikhonov * This is something to keep in mind. 4050aadb33SDmitri Tikhonov * 4150aadb33SDmitri Tikhonov * P.S. In Russian, "malo" (��������) means "little" or "few". Thus, the 4250aadb33SDmitri Tikhonov * malo allocator aims to perform its job in as few CPU cycles as 4350aadb33SDmitri Tikhonov * possible. 4450aadb33SDmitri Tikhonov */ 4550aadb33SDmitri Tikhonov 4650aadb33SDmitri Tikhonov#include <assert.h> 4750aadb33SDmitri Tikhonov#include <errno.h> 4850aadb33SDmitri Tikhonov#include <stdint.h> 4950aadb33SDmitri Tikhonov#include <stdlib.h> 5050aadb33SDmitri Tikhonov#include <sys/queue.h> 51461e84d8SAmol Deshpande#ifdef WIN32 52461e84d8SAmol Deshpande#include <vc_compat.h> 532d296031SDmitri Tikhonov#include <intrin.h> 54461e84d8SAmol Deshpande#endif 5550aadb33SDmitri Tikhonov 5650aadb33SDmitri Tikhonov#include "fiu-local.h" 5750aadb33SDmitri Tikhonov#include "lsquic_malo.h" 5850aadb33SDmitri Tikhonov 595392f7a3SLiteSpeed Tech#ifndef LSQUIC_USE_POOLS 605392f7a3SLiteSpeed Tech#define LSQUIC_USE_POOLS 1 615392f7a3SLiteSpeed Tech#endif 625392f7a3SLiteSpeed Tech 6350aadb33SDmitri Tikhonov/* 64 slots in a 4KB page means that the smallest object is 64 bytes. 6450aadb33SDmitri Tikhonov * The largest object is 2KB. 6550aadb33SDmitri Tikhonov */ 6650aadb33SDmitri Tikhonov#define MALO_MIN_NBITS 6 6750aadb33SDmitri Tikhonov#define MALO_MAX_NBITS 11 6850aadb33SDmitri Tikhonov 695392f7a3SLiteSpeed Tech#define ROUNDUP_THRESH 0.75f 705392f7a3SLiteSpeed Tech 7150aadb33SDmitri Tikhonov/* A "free page" is a page with free slots available. 7250aadb33SDmitri Tikhonov */ 7350aadb33SDmitri Tikhonov 745392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 7550aadb33SDmitri Tikhonovstatic unsigned find_free_slot (uint64_t slots); 7650aadb33SDmitri Tikhonovstatic unsigned size_in_bits (size_t sz); 775392f7a3SLiteSpeed Tech#endif 7850aadb33SDmitri Tikhonov 7950aadb33SDmitri Tikhonovstruct malo_page { 8050aadb33SDmitri Tikhonov SLIST_ENTRY(malo_page) next_page; 8150aadb33SDmitri Tikhonov LIST_ENTRY(malo_page) next_free_page; 8250aadb33SDmitri Tikhonov struct malo *malo; 8350aadb33SDmitri Tikhonov uint64_t slots, 8450aadb33SDmitri Tikhonov full_slot_mask; 855392f7a3SLiteSpeed Tech unsigned nbits; /* If pow is zero, stores object size */ 8650aadb33SDmitri Tikhonov unsigned initial_slot; 875392f7a3SLiteSpeed Tech int pow; /* True if object is power of 2 */ 8850aadb33SDmitri Tikhonov}; 8950aadb33SDmitri Tikhonov 9050aadb33SDmitri Tikhonovtypedef char malo_header_fits_in_one_slot 915392f7a3SLiteSpeed Tech [(sizeof(struct malo_page) > (1 << MALO_MIN_NBITS)) ? -1 : 1]; 925392f7a3SLiteSpeed Tech 935392f7a3SLiteSpeed Tech#if !LSQUIC_USE_POOLS 945392f7a3SLiteSpeed Techstruct nopool_elem 955392f7a3SLiteSpeed Tech{ 965392f7a3SLiteSpeed Tech TAILQ_ENTRY(nopool_elem) next; 975392f7a3SLiteSpeed Tech struct malo *malo; 985392f7a3SLiteSpeed Tech unsigned char data[0]; 995392f7a3SLiteSpeed Tech}; 1005392f7a3SLiteSpeed Tech#endif 10150aadb33SDmitri Tikhonov 10250aadb33SDmitri Tikhonovstruct malo { 1035392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 10450aadb33SDmitri Tikhonov struct malo_page page_header; 10550aadb33SDmitri Tikhonov SLIST_HEAD(, malo_page) all_pages; 10650aadb33SDmitri Tikhonov LIST_HEAD(, malo_page) free_pages; 10750aadb33SDmitri Tikhonov struct { 10850aadb33SDmitri Tikhonov struct malo_page *cur_page; 10950aadb33SDmitri Tikhonov unsigned next_slot; 11050aadb33SDmitri Tikhonov } iter; 1115392f7a3SLiteSpeed Tech#else 1125392f7a3SLiteSpeed Tech /* List of all elements: used by the iterator */ 1135392f7a3SLiteSpeed Tech TAILQ_HEAD(, nopool_elem) elems; 1145392f7a3SLiteSpeed Tech size_t obj_size; 1155392f7a3SLiteSpeed Tech struct nopool_elem *next_iter_elem; 1165392f7a3SLiteSpeed Tech#endif 11750aadb33SDmitri Tikhonov}; 11850aadb33SDmitri Tikhonov 11950aadb33SDmitri Tikhonovstruct malo * 12050aadb33SDmitri Tikhonovlsquic_malo_create (size_t obj_size) 12150aadb33SDmitri Tikhonov{ 1225392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 1235392f7a3SLiteSpeed Tech int pow, n_slots; 1245392f7a3SLiteSpeed Tech unsigned nbits; 1255392f7a3SLiteSpeed Tech 1265392f7a3SLiteSpeed Tech obj_size = (obj_size + 7) & -8; 1275392f7a3SLiteSpeed Tech nbits = size_in_bits(obj_size); 12850aadb33SDmitri Tikhonov if (nbits < MALO_MIN_NBITS) 12950aadb33SDmitri Tikhonov nbits = MALO_MIN_NBITS; 13050aadb33SDmitri Tikhonov else if (nbits > MALO_MAX_NBITS) 13150aadb33SDmitri Tikhonov { 13250aadb33SDmitri Tikhonov errno = EOVERFLOW; 13350aadb33SDmitri Tikhonov return NULL; 13450aadb33SDmitri Tikhonov } 13550aadb33SDmitri Tikhonov 1365392f7a3SLiteSpeed Tech pow = obj_size <= (1 << MALO_MIN_NBITS) 1375392f7a3SLiteSpeed Tech || (float) obj_size / (1 << nbits) > ROUNDUP_THRESH; 1385392f7a3SLiteSpeed Tech 13950aadb33SDmitri Tikhonov struct malo *malo; 14050aadb33SDmitri Tikhonov if (0 != posix_memalign((void **) &malo, 0x1000, 0x1000)) 14150aadb33SDmitri Tikhonov return NULL; 14250aadb33SDmitri Tikhonov 14350aadb33SDmitri Tikhonov SLIST_INIT(&malo->all_pages); 14450aadb33SDmitri Tikhonov LIST_INIT(&malo->free_pages); 14550aadb33SDmitri Tikhonov malo->iter.cur_page = &malo->page_header; 14650aadb33SDmitri Tikhonov malo->iter.next_slot = 0; 14750aadb33SDmitri Tikhonov 1485392f7a3SLiteSpeed Tech if (pow) 1495392f7a3SLiteSpeed Tech n_slots = sizeof(*malo) / (1 << nbits) 15050aadb33SDmitri Tikhonov + ((sizeof(*malo) % (1 << nbits)) > 0); 1515392f7a3SLiteSpeed Tech else 1525392f7a3SLiteSpeed Tech n_slots = sizeof(*malo) / obj_size 1535392f7a3SLiteSpeed Tech + ((sizeof(*malo) % obj_size) > 0); 15450aadb33SDmitri Tikhonov 15550aadb33SDmitri Tikhonov struct malo_page *const page = &malo->page_header; 15650aadb33SDmitri Tikhonov SLIST_INSERT_HEAD(&malo->all_pages, page, next_page); 15750aadb33SDmitri Tikhonov LIST_INSERT_HEAD(&malo->free_pages, page, next_free_page); 15850aadb33SDmitri Tikhonov page->malo = malo; 1595392f7a3SLiteSpeed Tech if (!pow) 1605392f7a3SLiteSpeed Tech page->full_slot_mask = (1ULL << (0x1000 / obj_size)) - 1; 1615392f7a3SLiteSpeed Tech else if (nbits == MALO_MIN_NBITS) 16250aadb33SDmitri Tikhonov page->full_slot_mask = ~0ULL; 16350aadb33SDmitri Tikhonov else 16450aadb33SDmitri Tikhonov page->full_slot_mask = (1ULL << (1 << (12 - nbits))) - 1; 16550aadb33SDmitri Tikhonov page->slots = (1ULL << n_slots) - 1; 1665392f7a3SLiteSpeed Tech page->pow = pow; 1675392f7a3SLiteSpeed Tech page->nbits = pow ? nbits : obj_size; 16850aadb33SDmitri Tikhonov page->initial_slot = n_slots; 16950aadb33SDmitri Tikhonov 17050aadb33SDmitri Tikhonov return malo; 1715392f7a3SLiteSpeed Tech#else 1725392f7a3SLiteSpeed Tech struct malo *malo; 1735392f7a3SLiteSpeed Tech 1745392f7a3SLiteSpeed Tech /* Use the same sizing mechanism as in the normal version */ 1755392f7a3SLiteSpeed Tech if (obj_size < (1 << MALO_MIN_NBITS)) 1765392f7a3SLiteSpeed Tech obj_size = 1 << MALO_MIN_NBITS; 1775392f7a3SLiteSpeed Tech else 1785392f7a3SLiteSpeed Tech obj_size = (obj_size + 7) & -8; 1795392f7a3SLiteSpeed Tech 1805392f7a3SLiteSpeed Tech malo = malloc(sizeof(*malo)); 1815392f7a3SLiteSpeed Tech if (malo) 1825392f7a3SLiteSpeed Tech { 1835392f7a3SLiteSpeed Tech TAILQ_INIT(&malo->elems); 1845392f7a3SLiteSpeed Tech malo->obj_size = obj_size; 185b1a7c3f9SDmitri Tikhonov malo->next_iter_elem = NULL; 1865392f7a3SLiteSpeed Tech return malo; 1875392f7a3SLiteSpeed Tech } 1885392f7a3SLiteSpeed Tech else 1895392f7a3SLiteSpeed Tech return NULL; 1905392f7a3SLiteSpeed Tech#endif 19150aadb33SDmitri Tikhonov} 19250aadb33SDmitri Tikhonov 19350aadb33SDmitri Tikhonov 1945392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 19550aadb33SDmitri Tikhonovstatic struct malo_page * 19650aadb33SDmitri Tikhonovallocate_page (struct malo *malo) 19750aadb33SDmitri Tikhonov{ 19850aadb33SDmitri Tikhonov struct malo_page *page; 19950aadb33SDmitri Tikhonov if (0 != posix_memalign((void **) &page, 0x1000, 0x1000)) 20050aadb33SDmitri Tikhonov return NULL; 20150aadb33SDmitri Tikhonov SLIST_INSERT_HEAD(&malo->all_pages, page, next_page); 20250aadb33SDmitri Tikhonov LIST_INSERT_HEAD(&malo->free_pages, page, next_free_page); 20350aadb33SDmitri Tikhonov page->slots = 1; 20450aadb33SDmitri Tikhonov page->full_slot_mask = malo->page_header.full_slot_mask; 20550aadb33SDmitri Tikhonov page->nbits = malo->page_header.nbits; 2065392f7a3SLiteSpeed Tech page->pow = malo->page_header.pow; 20750aadb33SDmitri Tikhonov page->malo = malo; 20850aadb33SDmitri Tikhonov page->initial_slot = 1; 20950aadb33SDmitri Tikhonov return page; 21050aadb33SDmitri Tikhonov} 2115392f7a3SLiteSpeed Tech#endif 21250aadb33SDmitri Tikhonov 21350aadb33SDmitri Tikhonov 21450aadb33SDmitri Tikhonov#define FAIL_NOMEM do { errno = ENOMEM; return NULL; } while (0) 21550aadb33SDmitri Tikhonov 21650aadb33SDmitri Tikhonov/* Get a new object. */ 21750aadb33SDmitri Tikhonovvoid * 21850aadb33SDmitri Tikhonovlsquic_malo_get (struct malo *malo) 21950aadb33SDmitri Tikhonov{ 2205392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 22150aadb33SDmitri Tikhonov fiu_do_on("malo/get", FAIL_NOMEM); 22250aadb33SDmitri Tikhonov struct malo_page *page = LIST_FIRST(&malo->free_pages); 22350aadb33SDmitri Tikhonov if (!page) 22450aadb33SDmitri Tikhonov { 22550aadb33SDmitri Tikhonov page = allocate_page(malo); 22650aadb33SDmitri Tikhonov if (!page) 22750aadb33SDmitri Tikhonov return NULL; 22850aadb33SDmitri Tikhonov } 22950aadb33SDmitri Tikhonov unsigned slot = find_free_slot(page->slots); 23050aadb33SDmitri Tikhonov page->slots |= (1ULL << slot); 23150aadb33SDmitri Tikhonov if (page->full_slot_mask == page->slots) 23250aadb33SDmitri Tikhonov LIST_REMOVE(page, next_free_page); 2335392f7a3SLiteSpeed Tech if (page->pow) 2345392f7a3SLiteSpeed Tech return (char *) page + (slot << page->nbits); 2355392f7a3SLiteSpeed Tech else 2365392f7a3SLiteSpeed Tech return (char *) page + (slot * page->nbits); 2375392f7a3SLiteSpeed Tech#else 2385392f7a3SLiteSpeed Tech struct nopool_elem *el; 2395392f7a3SLiteSpeed Tech el = malloc(sizeof(*el) + malo->obj_size); 2405392f7a3SLiteSpeed Tech if (el) 2415392f7a3SLiteSpeed Tech { 2425392f7a3SLiteSpeed Tech TAILQ_INSERT_HEAD(&malo->elems, el, next); 2435392f7a3SLiteSpeed Tech el->malo = malo; 2445392f7a3SLiteSpeed Tech return el->data; 2455392f7a3SLiteSpeed Tech } 2465392f7a3SLiteSpeed Tech else 2475392f7a3SLiteSpeed Tech return NULL; 2485392f7a3SLiteSpeed Tech#endif 24950aadb33SDmitri Tikhonov} 25050aadb33SDmitri Tikhonov 25150aadb33SDmitri Tikhonov 25250aadb33SDmitri Tikhonov/* Return obj to the pool */ 25350aadb33SDmitri Tikhonovvoid 25450aadb33SDmitri Tikhonovlsquic_malo_put (void *obj) 25550aadb33SDmitri Tikhonov{ 2565392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 25750aadb33SDmitri Tikhonov uintptr_t page_addr = (uintptr_t) obj & ~((1 << 12) - 1); 25850aadb33SDmitri Tikhonov struct malo_page *page = (void *) page_addr; 2595392f7a3SLiteSpeed Tech unsigned slot; 2605392f7a3SLiteSpeed Tech if (page->pow) 2615392f7a3SLiteSpeed Tech slot = ((uintptr_t) obj - page_addr) >> page->nbits; 2625392f7a3SLiteSpeed Tech else 2635392f7a3SLiteSpeed Tech slot = ((uintptr_t) obj - page_addr) / page->nbits; 26450aadb33SDmitri Tikhonov if (page->full_slot_mask == page->slots) 26550aadb33SDmitri Tikhonov LIST_INSERT_HEAD(&page->malo->free_pages, page, next_free_page); 26650aadb33SDmitri Tikhonov page->slots &= ~(1ULL << slot); 2675392f7a3SLiteSpeed Tech#else 2685392f7a3SLiteSpeed Tech struct nopool_elem *el; 2695392f7a3SLiteSpeed Tech el = (struct nopool_elem *) ((char *) obj - sizeof(*el)); 2705392f7a3SLiteSpeed Tech if (el == el->malo->next_iter_elem) 2715392f7a3SLiteSpeed Tech el->malo->next_iter_elem = TAILQ_NEXT(el->malo->next_iter_elem, next); 2725392f7a3SLiteSpeed Tech TAILQ_REMOVE(&el->malo->elems, el, next); 2735392f7a3SLiteSpeed Tech free(el); 2745392f7a3SLiteSpeed Tech#endif 27550aadb33SDmitri Tikhonov} 27650aadb33SDmitri Tikhonov 27750aadb33SDmitri Tikhonov 27850aadb33SDmitri Tikhonovvoid 27950aadb33SDmitri Tikhonovlsquic_malo_destroy (struct malo *malo) 28050aadb33SDmitri Tikhonov{ 2815392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 28250aadb33SDmitri Tikhonov struct malo_page *page, *next; 28350aadb33SDmitri Tikhonov page = SLIST_FIRST(&malo->all_pages); 28450aadb33SDmitri Tikhonov while (page != &malo->page_header) 28550aadb33SDmitri Tikhonov { 28650aadb33SDmitri Tikhonov next = SLIST_NEXT(page, next_page); 287461e84d8SAmol Deshpande#ifndef WIN32 28850aadb33SDmitri Tikhonov free(page); 289461e84d8SAmol Deshpande#else 290461e84d8SAmol Deshpande _aligned_free(page); 291461e84d8SAmol Deshpande#endif 29250aadb33SDmitri Tikhonov page = next; 29350aadb33SDmitri Tikhonov } 294461e84d8SAmol Deshpande#ifndef WIN32 29550aadb33SDmitri Tikhonov free(page); 296461e84d8SAmol Deshpande#else 297461e84d8SAmol Deshpande _aligned_free(page); 298461e84d8SAmol Deshpande#endif 2995392f7a3SLiteSpeed Tech#else 3005392f7a3SLiteSpeed Tech struct nopool_elem *el, *next_el; 3015392f7a3SLiteSpeed Tech for (el = TAILQ_FIRST(&malo->elems); el; el = next_el) 3025392f7a3SLiteSpeed Tech { 3035392f7a3SLiteSpeed Tech next_el = TAILQ_NEXT(el, next); 3045392f7a3SLiteSpeed Tech free(el); 3055392f7a3SLiteSpeed Tech } 3065392f7a3SLiteSpeed Tech free(malo); 3075392f7a3SLiteSpeed Tech#endif 30850aadb33SDmitri Tikhonov} 30950aadb33SDmitri Tikhonov 31050aadb33SDmitri Tikhonov 31150aadb33SDmitri Tikhonov/* The iterator is built-in. Usage: 31250aadb33SDmitri Tikhonov * void *obj; 31350aadb33SDmitri Tikhonov * for (obj = lsquic_malo_first(malo); obj; lsquic_malo_next(malo)) 31450aadb33SDmitri Tikhonov * do_stuff(obj); 31550aadb33SDmitri Tikhonov */ 31650aadb33SDmitri Tikhonovvoid * 31750aadb33SDmitri Tikhonovlsquic_malo_first (struct malo *malo) 31850aadb33SDmitri Tikhonov{ 3195392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 32050aadb33SDmitri Tikhonov malo->iter.cur_page = SLIST_FIRST(&malo->all_pages); 32150aadb33SDmitri Tikhonov malo->iter.next_slot = malo->iter.cur_page->initial_slot; 3225392f7a3SLiteSpeed Tech#else 3235392f7a3SLiteSpeed Tech malo->next_iter_elem = TAILQ_FIRST(&malo->elems); 3245392f7a3SLiteSpeed Tech#endif 32550aadb33SDmitri Tikhonov return lsquic_malo_next(malo); 32650aadb33SDmitri Tikhonov} 32750aadb33SDmitri Tikhonov 32850aadb33SDmitri Tikhonov 32950aadb33SDmitri Tikhonovvoid * 33050aadb33SDmitri Tikhonovlsquic_malo_next (struct malo *malo) 33150aadb33SDmitri Tikhonov{ 3325392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 33350aadb33SDmitri Tikhonov struct malo_page *page; 33450aadb33SDmitri Tikhonov unsigned max_slot, slot; 33550aadb33SDmitri Tikhonov 33650aadb33SDmitri Tikhonov page = malo->iter.cur_page; 33750aadb33SDmitri Tikhonov if (page) 33850aadb33SDmitri Tikhonov { 3395392f7a3SLiteSpeed Tech if (page->pow) 3405392f7a3SLiteSpeed Tech max_slot = 1 << (12 - page->nbits); /* Same for all pages */ 3415392f7a3SLiteSpeed Tech else 3425392f7a3SLiteSpeed Tech max_slot = 0x1000 / page->nbits; 34350aadb33SDmitri Tikhonov slot = malo->iter.next_slot; 34450aadb33SDmitri Tikhonov while (1) 34550aadb33SDmitri Tikhonov { 34650aadb33SDmitri Tikhonov for (; slot < max_slot; ++slot) 34750aadb33SDmitri Tikhonov { 34850aadb33SDmitri Tikhonov if (page->slots & (1ULL << slot)) 34950aadb33SDmitri Tikhonov { 35050aadb33SDmitri Tikhonov malo->iter.cur_page = page; 35150aadb33SDmitri Tikhonov malo->iter.next_slot = slot + 1; 3525392f7a3SLiteSpeed Tech if (page->pow) 3535392f7a3SLiteSpeed Tech return (char *) page + (slot << page->nbits); 3545392f7a3SLiteSpeed Tech else 3555392f7a3SLiteSpeed Tech { 3565392f7a3SLiteSpeed Tech assert(slot * (page->nbits + 1) < 0x1000); 3575392f7a3SLiteSpeed Tech return (char *) page + (slot * page->nbits); 3585392f7a3SLiteSpeed Tech } 35950aadb33SDmitri Tikhonov } 36050aadb33SDmitri Tikhonov } 36150aadb33SDmitri Tikhonov page = SLIST_NEXT(page, next_page); 36250aadb33SDmitri Tikhonov if (page) 36350aadb33SDmitri Tikhonov slot = page->initial_slot; 36450aadb33SDmitri Tikhonov else 36550aadb33SDmitri Tikhonov { 36650aadb33SDmitri Tikhonov malo->iter.cur_page = NULL; /* Stop iterator */ 36750aadb33SDmitri Tikhonov return NULL; 36850aadb33SDmitri Tikhonov } 36950aadb33SDmitri Tikhonov } 37050aadb33SDmitri Tikhonov } 37150aadb33SDmitri Tikhonov 37250aadb33SDmitri Tikhonov return NULL; 3735392f7a3SLiteSpeed Tech#else 3745392f7a3SLiteSpeed Tech struct nopool_elem *retval; 3755392f7a3SLiteSpeed Tech 3765392f7a3SLiteSpeed Tech if (malo->next_iter_elem) 3775392f7a3SLiteSpeed Tech { 3785392f7a3SLiteSpeed Tech retval = malo->next_iter_elem; 3795392f7a3SLiteSpeed Tech malo->next_iter_elem = TAILQ_NEXT(malo->next_iter_elem, next); 3805392f7a3SLiteSpeed Tech return retval->data; 3815392f7a3SLiteSpeed Tech } 3825392f7a3SLiteSpeed Tech else 3835392f7a3SLiteSpeed Tech return NULL; 3845392f7a3SLiteSpeed Tech#endif 38550aadb33SDmitri Tikhonov} 38650aadb33SDmitri Tikhonov 38750aadb33SDmitri Tikhonov 3885392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 38950aadb33SDmitri Tikhonovstatic unsigned 39050aadb33SDmitri Tikhonovsize_in_bits (size_t sz) 39150aadb33SDmitri Tikhonov{ 39250aadb33SDmitri Tikhonov#if __GNUC__ 3935392f7a3SLiteSpeed Tech unsigned clz = sz > 1 ? __builtin_clz(sz - 1) : 31; 39450aadb33SDmitri Tikhonov return 32 - clz; 3952d296031SDmitri Tikhonov#elif defined(WIN32) 3962d296031SDmitri Tikhonov unsigned char s; 3972d296031SDmitri Tikhonov unsigned long idx; 3982d296031SDmitri Tikhonov s = _BitScanReverse(&idx, sz); 3992d296031SDmitri Tikhonov assert(s); 4002d296031SDmitri Tikhonov return (unsigned) idx + 1; 40150aadb33SDmitri Tikhonov#else 4022d296031SDmitri Tikhonov#error This function contains a bug! 40350aadb33SDmitri Tikhonov unsigned clz; 40450aadb33SDmitri Tikhonov size_t y; 40550aadb33SDmitri Tikhonov 40650aadb33SDmitri Tikhonov --sz; 40750aadb33SDmitri Tikhonov clz = 32; 40850aadb33SDmitri Tikhonov y = sz >> 16; if (y) { clz -= 16; sz = y; } 40950aadb33SDmitri Tikhonov y = sz >> 8; if (y) { clz -= 8; sz = y; } 41050aadb33SDmitri Tikhonov y = sz >> 4; if (y) { clz -= 4; sz = y; } 41150aadb33SDmitri Tikhonov y = sz >> 2; if (y) { clz -= 2; sz = y; } 41250aadb33SDmitri Tikhonov y = sz >> 1; if (y) return 32 - clz + 1; 41350aadb33SDmitri Tikhonov return 32 - clz + sz; 41450aadb33SDmitri Tikhonov#endif 41550aadb33SDmitri Tikhonov} 41650aadb33SDmitri Tikhonov 41750aadb33SDmitri Tikhonov 41850aadb33SDmitri Tikhonovstatic unsigned 41950aadb33SDmitri Tikhonovfind_free_slot (uint64_t slots) 42050aadb33SDmitri Tikhonov{ 42150aadb33SDmitri Tikhonov#if __GNUC__ 42250aadb33SDmitri Tikhonov return __builtin_ffsll(~slots) - 1; 42350aadb33SDmitri Tikhonov#else 42450aadb33SDmitri Tikhonov unsigned n; 42550aadb33SDmitri Tikhonov 42650aadb33SDmitri Tikhonov slots =~ slots; 42750aadb33SDmitri Tikhonov n = 0; 42850aadb33SDmitri Tikhonov 42950aadb33SDmitri Tikhonov if (0 == (slots & ((1ULL << 32) - 1))) { n += 32; slots >>= 32; } 43050aadb33SDmitri Tikhonov if (0 == (slots & ((1ULL << 16) - 1))) { n += 16; slots >>= 16; } 43150aadb33SDmitri Tikhonov if (0 == (slots & ((1ULL << 8) - 1))) { n += 8; slots >>= 8; } 43250aadb33SDmitri Tikhonov if (0 == (slots & ((1ULL << 4) - 1))) { n += 4; slots >>= 4; } 43350aadb33SDmitri Tikhonov if (0 == (slots & ((1ULL << 2) - 1))) { n += 2; slots >>= 2; } 43450aadb33SDmitri Tikhonov if (0 == (slots & ((1ULL << 1) - 1))) { n += 1; slots >>= 1; } 43550aadb33SDmitri Tikhonov return n; 43650aadb33SDmitri Tikhonov#endif 43750aadb33SDmitri Tikhonov} 4385392f7a3SLiteSpeed Tech#endif 439c51ce338SDmitri Tikhonov 440c51ce338SDmitri Tikhonov 441c51ce338SDmitri Tikhonovsize_t 442c51ce338SDmitri Tikhonovlsquic_malo_mem_used (const struct malo *malo) 443c51ce338SDmitri Tikhonov{ 4445392f7a3SLiteSpeed Tech#if LSQUIC_USE_POOLS 445c51ce338SDmitri Tikhonov const struct malo_page *page; 446c51ce338SDmitri Tikhonov size_t size; 447c51ce338SDmitri Tikhonov 448c51ce338SDmitri Tikhonov size = 0; 449c51ce338SDmitri Tikhonov SLIST_FOREACH(page, &malo->all_pages, next_page) 450c51ce338SDmitri Tikhonov size += sizeof(*page); 451c51ce338SDmitri Tikhonov 452c51ce338SDmitri Tikhonov return size; 4535392f7a3SLiteSpeed Tech#else 4545392f7a3SLiteSpeed Tech return 0; 4555392f7a3SLiteSpeed Tech#endif 456c51ce338SDmitri Tikhonov} 457