1## LWS Allocated Chunks 2 3 4 5These apis provide a way to manage a linked-list of allocated chunks... 6 7[ HEAD alloc ] -> [ next alloc ] -> [ next alloc ] -> [ curr alloc ] 8 9... and sub-allocate trivially inside the chunks. These sub-allocations are 10not tracked by lwsac at all, there is a "used" high-water mark for each chunk 11that's simply advanced by the amount sub-allocated. If the allocation size 12matches the platform pointer alignment, there is zero overhead to sub-allocate 13(otherwise the allocation is padded to the next platform pointer alignment 14automatically). 15 16If you have an unknown amount of relatively little things to allocate, including 17strings or other unstructured data, lwsac is significantly more efficient than 18individual allocations using malloc or so. 19 20[lwsac full public api](https://libwebsockets.org/git/libwebsockets/tree/include/libwebsockets/lws-lwsac.h) 21 22## lwsac_use() api 23 24``` 25/** 26 * lwsac_use - allocate / use some memory from a lwsac 27 * 28 * \param head: pointer to the lwsac list object 29 * \param ensure: the number of bytes we want to use 30 * \param chunk_size: 0, or the size of the chunk to (over)allocate if 31 * what we want won't fit in the current tail chunk. If 32 * 0, the default value of 4000 is used. If ensure is 33 * larger, it is used instead. 34 * 35 * This also serves to init the lwsac if *head is NULL. Basically it does 36 * whatever is necessary to return you a pointer to ensure bytes of memory 37 * reserved for the caller. 38 * 39 * Returns NULL if OOM. 40 */ 41LWS_VISIBLE LWS_EXTERN void * 42lwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size); 43``` 44 45When you make an sub-allocation using `lwsac_use()`, you can either 46set the `chunk_size` arg to zero, defaulting to 4000, or a specific chunk size. 47In the event the requested sub-allocation exceeds the chunk size, the chunk 48size is increated to match it automatically for this allocation only. 49 50Subsequent `lwsac_use()` calls will advance internal pointers to use up the 51remaining space inside the current chunk if possible; if not enough remaining 52space it is skipped, a new allocation is chained on and the request pointed to 53there. 54 55Lwsac does not store information about sub-allocations. There is really zero 56overhead for individual sub-allocations (unless their size is not 57pointer-aligned, in which case the actual amount sub-allocated is rounded up to 58the next pointer alignment automatically). For structs, which are pointer- 59aligned naturally, and a chunk size relatively large for the sub-allocation 60size, lwsac is extremely efficient even for huge numbers of small allocations. 61 62This makes lwsac very effective when the total amount of allocation needed is 63not known at the start and may be large... it will simply add on chunks to cope 64with whatever happens. 65 66## lwsac_free() api 67 68``` 69/** 70 * lwsac_free - deallocate all chunks in the lwsac and set head NULL 71 * 72 * \param head: pointer to the lwsac list object 73 * 74 * This deallocates all chunks in the lwsac, then sets *head to NULL. All 75 * lwsac_use() pointers are invalidated in one hit without individual frees. 76 */ 77LWS_VISIBLE LWS_EXTERN void 78lwsac_free(struct lwsac **head); 79``` 80 81When you are finished with the lwsac, you simply free the chain of allocated 82chunks using lwsac_free() on the lwsac head. There's no tracking or individual 83destruction of suballocations - the whole chain of chunks the suballocations 84live in are freed and invalidated all together. 85 86If the structs stored in the lwsac allocated things **outside** the lwsac, then the 87user must unwind through them and perform the frees. But the idea of lwsac is 88things stored in the lwsac also suballocate into the lwsac, and point into the 89lwsac if they need to, avoiding any need to visit them during destroy. It's 90like clearing up after a kids' party by gathering up a disposable tablecloth: 91no matter what was left on the table, it's all gone in one step. 92 93## `lws_list_ptr` helpers 94 95``` 96/* sort may be NULL if you don't care about order */ 97LWS_VISIBLE LWS_EXTERN void 98lws_list_ptr_insert(lws_list_ptr *phead, lws_list_ptr *add, 99 lws_list_ptr_sort_func_t sort); 100``` 101 102A common pattern needed with sub-allocated structs is they are on one or more 103linked-list. To make that simple to do cleanly, `lws_list...` apis are provided 104along with a generic insertion function that can take a sort callback. These 105allow a struct to participate on multiple linked-lists simultaneously. 106 107## common const string and blob folding 108 109In some cases the input to be stored in the lwsac may repeat the same tokens 110multiple times... if the pattern is to store the string or blob in the lwsac 111and then point to it, you can make use of a helper api 112 113``` 114uint8_t * 115lwsac_scan_extant(struct lwsac *head, uint8_t *find, size_t len, int nul); 116``` 117 118This lets you check in all previous used parts of the lwsac for the same 119string or blob, plus optionally a terminal NUL afterwards. If not found, 120it returns `NULL` and you can copy it into the lwsac as usual. If it is 121found, a pointer is returned, and you can use this directly without copying 122the string or blob in again. 123 124## optimizations to minimize overhead 125 126If the lwsac will persist in the system for some time, it's desirable to reduce 127the memory needed as overhead. Overhead is created 128 129 - once per chunk... in addition to the malloc overhead, there's an lwsac 130 chunk header of 2 x pointers and 2 x size_t 131 132 - at the unused part at the end that was allocated but not used 133 134A good strategy is to make the initial allocation reflect the minimum expected 135size of the overall lwsac in one hit. Then use a chunk size that is a tradeoff 136between the number of chunks that might be needed and the fact that on average, 137you can expect to waste half a chunk. For example if the storage is typically 138between 4K - 6K, you could allocate 4K or 4.5K for the first chunk and then fill 139in using 256 or 512 byte chunks. 140 141You can measure the overhead in an lwsac using `lwsac_total_overhead()`. 142 143The lwsac apis look first in the unused part of previous chunks, if any, and 144will place new allocations there preferentially if they fit. This helps for the 145case lwsac was forced to allocate a new chunk because you asked for something 146large, while there was actually significant free space left in the old chunk, 147just not enough for that particular allocation. Subsequent lwsac use can then 148"backfill" smaller things there to make best use of allocated space. 149
