Project homepage Mailing List  API Docs  Github Mirror 
{"schema":"libjg2-1", "vpath":"/git/", "avatar":"/git/avatar/", "alang":"en-US,en;q\u003d0.5", "gen_ut":1603325485, "reponame":"libwebsockets", "desc":"libwebsockets lightweight C networking library", "owner": { "name": "Andy Green", "email": "", "md5": "c50933ca2aa61e0fe2c43d46bb6b59cb" },"url":"", "f":3, "items": [ { "schema":"libjg2-1", "oid":{ "oid": "ed1e558eedc79a07837db2f0a41eb94197ad23fa", "alias": [ "refs/heads/master"]},"tree": [ { "name": "","mode": "33188", "size":6464}, { "name": "cached-file.c","mode": "33188", "size":5652}, { "name": "lwsac.c","mode": "33188", "size":7528}, { "name": "lwsac.cxx","mode": "33188", "size":2329}, { "name": "private-lib-misc-lwsac.h","mode": "33188", "size":2223}],"s":{"c":1603227050,"u": 733}} ,{"schema":"libjg2-1", "cid":"e6a93c0cc2a0f20a13fb57f6d648d6d8", "oid":{ "oid": "ed1e558eedc79a07837db2f0a41eb94197ad23fa", "alias": [ "refs/heads/master"]},"blobname": "lib/misc/lwsac/", "blob": "## LWS Allocated Chunks\n\n![lwsac flow](/doc-assets/lwsac.svg)\n\nThese apis provide a way to manage a linked-list of allocated chunks...\n\n[ HEAD alloc ] -\u003e [ next alloc ] -\u003e [ next alloc ] -\u003e [ curr alloc ]\n\n... and sub-allocate trivially inside the chunks. These sub-allocations are\nnot tracked by lwsac at all, there is a \u0022used\u0022 high-water mark for each chunk\nthat's simply advanced by the amount sub-allocated. If the allocation size\nmatches the platform pointer alignment, there is zero overhead to sub-allocate\n(otherwise the allocation is padded to the next platform pointer alignment\nautomatically).\n\nIf you have an unknown amount of relatively little things to allocate, including\nstrings or other unstructured data, lwsac is significantly more efficient than\nindividual allocations using malloc or so.\n\n[lwsac full public api](\n\n## lwsac_use() api\n\n```\n/**\n * lwsac_use - allocate / use some memory from a lwsac\n *\n * \u005cparam head: pointer to the lwsac list object\n * \u005cparam ensure: the number of bytes we want to use\n * \u005cparam chunk_size: 0, or the size of the chunk to (over)allocate if\n *\t\t\twhat we want won't fit in the current tail chunk. If\n *\t\t\t0, the default value of 4000 is used. If ensure is\n *\t\t\tlarger, it is used instead.\n *\n * This also serves to init the lwsac if *head is NULL. Basically it does\n * whatever is necessary to return you a pointer to ensure bytes of memory\n * reserved for the caller.\n *\n * Returns NULL if OOM.\n */\nLWS_VISIBLE LWS_EXTERN void *\nlwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size);\n```\n\nWhen you make an sub-allocation using `lwsac_use()`, you can either\nset the `chunk_size` arg to zero, defaulting to 4000, or a specific chunk size.\nIn the event the requested sub-allocation exceeds the chunk size, the chunk\nsize is increated to match it automatically for this allocation only.\n\nSubsequent `lwsac_use()` calls will advance internal pointers to use up the\nremaining space inside the current chunk if possible; if not enough remaining\nspace it is skipped, a new allocation is chained on and the request pointed to\nthere.\n\nLwsac does not store information about sub-allocations. There is really zero\noverhead for individual sub-allocations (unless their size is not\npointer-aligned, in which case the actual amount sub-allocated is rounded up to\nthe next pointer alignment automatically). For structs, which are pointer-\naligned naturally, and a chunk size relatively large for the sub-allocation\nsize, lwsac is extremely efficient even for huge numbers of small allocations.\n\nThis makes lwsac very effective when the total amount of allocation needed is\nnot known at the start and may be large... it will simply add on chunks to cope\nwith whatever happens.\n\n## lwsac_free() api\n\n```\n/**\n * lwsac_free - deallocate all chunks in the lwsac and set head NULL\n *\n * \u005cparam head: pointer to the lwsac list object\n *\n * This deallocates all chunks in the lwsac, then sets *head to NULL. All\n * lwsac_use() pointers are invalidated in one hit without individual frees.\n */\nLWS_VISIBLE LWS_EXTERN void\nlwsac_free(struct lwsac **head);\n```\n\nWhen you are finished with the lwsac, you simply free the chain of allocated\nchunks using lwsac_free() on the lwsac head. There's no tracking or individual\ndestruction of suballocations - the whole chain of chunks the suballocations\nlive in are freed and invalidated all together.\n\nIf the structs stored in the lwsac allocated things **outside** the lwsac, then the\nuser must unwind through them and perform the frees. But the idea of lwsac is\nthings stored in the lwsac also suballocate into the lwsac, and point into the\nlwsac if they need to, avoiding any need to visit them during destroy. It's\nlike clearing up after a kids' party by gathering up a disposable tablecloth:\nno matter what was left on the table, it's all gone in one step.\n\n## `lws_list_ptr` helpers\n\n```\n/* sort may be NULL if you don't care about order */\nLWS_VISIBLE LWS_EXTERN void\nlws_list_ptr_insert(lws_list_ptr *phead, lws_list_ptr *add,\n\t\t lws_list_ptr_sort_func_t sort);\n```\n\nA common pattern needed with sub-allocated structs is they are on one or more\nlinked-list. To make that simple to do cleanly, `lws_list...` apis are provided\nalong with a generic insertion function that can take a sort callback. These\nallow a struct to participate on multiple linked-lists simultaneously.\n\n## common const string and blob folding\n\nIn some cases the input to be stored in the lwsac may repeat the same tokens\nmultiple times... if the pattern is to store the string or blob in the lwsac\nand then point to it, you can make use of a helper api\n\n```\nuint8_t *\nlwsac_scan_extant(struct lwsac *head, uint8_t *find, size_t len, int nul);\n```\n\nThis lets you check in all previous used parts of the lwsac for the same\nstring or blob, plus optionally a terminal NUL afterwards. If not found,\nit returns `NULL` and you can copy it into the lwsac as usual. If it is\nfound, a pointer is returned, and you can use this directly without copying\nthe string or blob in again.\n\n## optimizations to minimize overhead\n\nIf the lwsac will persist in the system for some time, it's desirable to reduce\nthe memory needed as overhead. Overhead is created\n\n - once per chunk... in addition to the malloc overhead, there's an lwsac\n chunk header of 2 x pointers and 2 x size_t\n \n - at the unused part at the end that was allocated but not used\n \nA good strategy is to make the initial allocation reflect the minimum expected\nsize of the overall lwsac in one hit. Then use a chunk size that is a tradeoff\nbetween the number of chunks that might be needed and the fact that on average,\nyou can expect to waste half a chunk. For example if the storage is typically\nbetween 4K - 6K, you could allocate 4K or 4.5K for the first chunk and then fill\nin using 256 or 512 byte chunks.\n\nYou can measure the overhead in an lwsac using `lwsac_total_overhead()`.\n\nThe lwsac apis look first in the unused part of previous chunks, if any, and\nwill place new allocations there preferentially if they fit. This helps for the\ncase lwsac was forced to allocate a new chunk because you asked for something\nlarge, while there was actually significant free space left in the old chunk,\njust not enough for that particular allocation. Subsequent lwsac use can then\n\u0022backfill\u0022 smaller things there to make best use of allocated space.\n","s":{"c":1603227050,"u": 328}} ],"g": 873,"chitpc": 0,"ehitpc": 0,"indexed":0 , "ab": 0, "si": 0, "db":0, "di":0, "sat":0, "lfc": "7d0a"}