lib/misc/lwsac/README.md

   1 ## LWS Allocated Chunks
   2
   3 ![lwsac flow](/doc-assets/lwsac.svg)
   4
   5 These 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
  10 not tracked by lwsac at all, there is a "used" high-water mark for each chunk
  11 that's simply advanced by the amount sub-allocated.  If the allocation size
  12 matches the platform pointer alignment, there is zero overhead to sub-allocate
  13 (otherwise the allocation is padded to the next platform pointer alignment
  14 automatically).
  15
  16 If you have an unknown amount of relatively little things to allocate, including
  17 strings or other unstructured data, lwsac is significantly more efficient than
  18 individual 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  */
  41 LWS_VISIBLE LWS_EXTERN void *
  42 lwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size);
  43 ```
  44
  45 When you make an sub-allocation using `lwsac_use()`, you can either
  46 set the `chunk_size` arg to zero, defaulting to 4000, or a specific chunk size.
  47 In the event the requested sub-allocation exceeds the chunk size, the chunk
  48 size is increated to match it automatically for this allocation only.
  49
  50 Subsequent `lwsac_use()` calls will advance internal pointers to use up the
  51 remaining space inside the current chunk if possible; if not enough remaining
  52 space it is skipped, a new allocation is chained on and the request pointed to
  53 there.
  54
  55 Lwsac does not store information about sub-allocations.  There is really zero
  56 overhead for individual sub-allocations (unless their size is not
  57 pointer-aligned, in which case the actual amount sub-allocated is rounded up to
  58 the next pointer alignment automatically).  For structs, which are pointer-
  59 aligned naturally, and a chunk size relatively large for the sub-allocation
  60 size, lwsac is extremely efficient even for huge numbers of small allocations.
  61
  62 This makes lwsac very effective when the total amount of allocation needed is
  63 not known at the start and may be large... it will simply add on chunks to cope
  64 with 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  */
  77 LWS_VISIBLE LWS_EXTERN void
  78 lwsac_free(struct lwsac **head);
  79 ```
  80
  81 When you are finished with the lwsac, you simply free the chain of allocated
  82 chunks using lwsac_free() on the lwsac head.  There's no tracking or individual
  83 destruction of suballocations - the whole chain of chunks the suballocations
  84 live in are freed and invalidated all together.
  85
  86 If the structs stored in the lwsac allocated things **outside** the lwsac, then the
  87 user must unwind through them and perform the frees.  But the idea of lwsac is
  88 things stored in the lwsac also suballocate into the lwsac, and point into the
  89 lwsac if they need to, avoiding any need to visit them during destroy.  It's
  90 like clearing up after a kids' party by gathering up a disposable tablecloth:
  91 no 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 */
  97 LWS_VISIBLE LWS_EXTERN void
  98 lws_list_ptr_insert(lws_list_ptr *phead, lws_list_ptr *add,
  99                     lws_list_ptr_sort_func_t sort);
 100 ```
 101
 102 A common pattern needed with sub-allocated structs is they are on one or more
 103 linked-list.  To make that simple to do cleanly, lws_list... apis are provided
 104 along with a generic insertion function that can take a sort callback.  These
 105 allow a struct to participate on multiple linked-lists simultaneously.
 106