1 /* 2 * libwebsockets - small server side websockets and web server implementation 3 * 4 * Copyright (C) 2010 - 2020 Andy Green <andy@warmcat.com> 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a copy 7 * of this software and associated documentation files (the "Software"), to 8 * deal in the Software without restriction, including without limitation the 9 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 10 * sell copies of the Software, and to permit persons to whom the Software is 11 * furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be included in 14 * all copies or substantial portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 22 * IN THE SOFTWARE. 23 */ 24 25 /** \defgroup lwsac lwsac 26 * 27 * ##Allocated Chunks 28 * 29 * If you know you will be allocating a large, unknown number of same or 30 * differently sized objects, it's certainly possible to do it with libc 31 * malloc. However the allocation cost in time and memory overhead can 32 * add up, and deallocation means walking the structure of every object and 33 * freeing them in turn. 34 * 35 * lwsac (LWS Allocated Chunks) allocates chunks intended to be larger 36 * than your objects (4000 bytes by default) which you linearly allocate from 37 * using lwsac_use(). 38 * 39 * If your next request won't fit in the current chunk, a new chunk is added 40 * to the chain of chunks and the allocaton done from there. If the request 41 * is larger than the chunk size, an oversize chunk is created to satisfy it. 42 * 43 * When you are finished with the allocations, you call lwsac_free() and 44 * free all the *chunks*. So you may have thousands of objects in the chunks, 45 * but they are all destroyed with the chunks without having to deallocate them 46 * one by one pointlessly. 47 */ 48 ///@{ 49 50 struct lwsac; 51 typedef unsigned char * lwsac_cached_file_t; 52 53 54 #define lws_list_ptr_container(P,T,M) ((T *)((char *)(P) - offsetof(T, M))) 55 56 /* 57 * linked-list helper that's commonly useful to manage lists of things 58 * allocated using lwsac. 59 * 60 * These lists point to their corresponding "next" member in the target, NOT 61 * the original containing struct. To get the containing struct, you must use 62 * lws_list_ptr_container() to convert. 63 * 64 * It's like that because it means we no longer have to have the next pointer 65 * at the start of the struct, and we can have the same struct on multiple 66 * linked-lists with everything held in the struct itself. 67 */ 68 typedef void * lws_list_ptr; 69 70 /* 71 * optional sorting callback called by lws_list_ptr_insert() to sort the right 72 * things inside the opqaue struct being sorted / inserted on the list. 73 */ 74 typedef int (*lws_list_ptr_sort_func_t)(lws_list_ptr a, lws_list_ptr b); 75 76 #define lws_list_ptr_advance(_lp) _lp = *((void **)_lp) 77 78 /* sort may be NULL if you don't care about order */ 79 LWS_VISIBLE LWS_EXTERN void 80 lws_list_ptr_insert(lws_list_ptr *phead, lws_list_ptr *add, 81 lws_list_ptr_sort_func_t sort); 82 83 84 /** 85 * lwsac_use - allocate / use some memory from a lwsac 86 * 87 * \param head: pointer to the lwsac list object 88 * \param ensure: the number of bytes we want to use 89 * \param chunk_size: 0, or the size of the chunk to (over)allocate if 90 * what we want won't fit in the current tail chunk. If 91 * 0, the default value of 4000 is used. If ensure is 92 * larger, it is used instead. 93 * 94 * This also serves to init the lwsac if *head is NULL. Basically it does 95 * whatever is necessary to return you a pointer to ensure bytes of memory 96 * reserved for the caller. 97 * 98 * This always allocates in the current chunk or a new chunk... see the 99 * lwsac_use_backfill() variant to try first to find space in earlier chunks. 100 * 101 * Returns NULL if OOM. 102 */ 103 LWS_VISIBLE LWS_EXTERN void * 104 lwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size); 105 106 /** 107 * lwsac_use_backfill - allocate / use some memory from a lwsac 108 * 109 * \param head: pointer to the lwsac list object 110 * \param ensure: the number of bytes we want to use 111 * \param chunk_size: 0, or the size of the chunk to (over)allocate if 112 * what we want won't fit in the current tail chunk. If 113 * 0, the default value of 4000 is used. If ensure is 114 * larger, it is used instead. 115 * 116 * This also serves to init the lwsac if *head is NULL. Basically it does 117 * whatever is necessary to return you a pointer to ensure bytes of memory 118 * reserved for the caller. 119 * 120 * Also checks if earlier blocks have enough remaining space to take the 121 * allocation before making a new allocation. 122 * 123 * Returns NULL if OOM. 124 */ 125 LWS_VISIBLE LWS_EXTERN void * 126 lwsac_use_backfill(struct lwsac **head, size_t ensure, size_t chunk_size); 127 128 /** 129 * lwsac_use - allocate / use some memory from a lwsac 130 * 131 * \param head: pointer to the lwsac list object 132 * \param ensure: the number of bytes we want to use, which must be zeroed 133 * \param chunk_size: 0, or the size of the chunk to (over)allocate if 134 * what we want won't fit in the current tail chunk. If 135 * 0, the default value of 4000 is used. If ensure is 136 * larger, it is used instead. 137 * 138 * Same as lwsac_use(), but \p ensure bytes of memory at the return address 139 * are zero'd before returning. 140 * 141 * Returns NULL if OOM. 142 */ 143 LWS_VISIBLE LWS_EXTERN void * 144 lwsac_use_zero(struct lwsac **head, size_t ensure, size_t chunk_size); 145 146 #define lwsac_use_zeroed lwsac_use_zero 147 148 /** 149 * lwsac_free - deallocate all chunks in the lwsac and set head NULL 150 * 151 * \param head: pointer to the lwsac list object 152 * 153 * This deallocates all chunks in the lwsac, then sets *head to NULL. All 154 * lwsac_use() pointers are invalidated in one hit without individual frees. 155 */ 156 LWS_VISIBLE LWS_EXTERN void 157 lwsac_free(struct lwsac **head); 158 159 /* 160 * Optional helpers useful for where consumers may need to defer destruction 161 * until all consumers are finished with the lwsac 162 */ 163 164 /** 165 * lwsac_detach() - destroy an lwsac unless somebody else is referencing it 166 * 167 * \param head: pointer to the lwsac list object 168 * 169 * The creator of the lwsac can all this instead of lwsac_free() when it itself 170 * has finished with the lwsac, but other code may be consuming it. 171 * 172 * If there are no other references, the lwsac is destroyed, *head is set to 173 * NULL and that's the end; however if something else has called 174 * lwsac_reference() on the lwsac, it simply returns. When lws_unreference() 175 * is called and no references are left, it will be destroyed then. 176 */ 177 LWS_VISIBLE LWS_EXTERN void 178 lwsac_detach(struct lwsac **head); 179 180 /** 181 * lwsac_reference() - increase the lwsac reference count 182 * 183 * \param head: pointer to the lwsac list object 184 * 185 * Increment the reference count on the lwsac to defer destruction. 186 */ 187 LWS_VISIBLE LWS_EXTERN void 188 lwsac_reference(struct lwsac *head); 189 190 /** 191 * lwsac_reference() - increase the lwsac reference count 192 * 193 * \param head: pointer to the lwsac list object 194 * 195 * Decrement the reference count on the lwsac... if it reached 0 on a detached 196 * lwsac then the lwsac is immediately destroyed and *head set to NULL. 197 */ 198 LWS_VISIBLE LWS_EXTERN void 199 lwsac_unreference(struct lwsac **head); 200 201 /** 202 * lwsac_extend() - try to increase the size of the last block 203 * 204 * \param head: pointer to the lwsac list object 205 * \param amount: amount to try to increase usage for 206 * 207 * This will either increase the usage reservation of the last allocated block 208 * by amount and return 0, or fail and return 1. 209 * 210 * This is very cheap to call and is designed to optimize usage after a static 211 * struct for vari-sized additional content which may flow into an additional 212 * block in a new chunk if necessary, but wants to make the most of the space 213 * in front of it first to try to avoid gaps and the new chunk if it can. 214 * 215 * The additional area if the call succeeds will have been memset to 0. 216 * 217 * To use it, the following must be true: 218 * 219 * - only the last lwsac use can be extended 220 * 221 * - if another use happens inbetween the use and extend, it will break 222 * 223 * - the use cannot have been using backfill 224 * 225 * - a user object must be tracking the current allocated size of the last use 226 * (lwsac doesn't know it) and increment by amount if the extend call succeeds 227 * 228 * Despite these restrictions this can be an important optimization for some 229 * cases 230 */ 231 LWS_VISIBLE LWS_EXTERN int 232 lwsac_extend(struct lwsac *head, int amount); 233 234 /* helpers to keep a file cached in memory */ 235 236 LWS_VISIBLE LWS_EXTERN void 237 lwsac_use_cached_file_start(lwsac_cached_file_t cache); 238 239 LWS_VISIBLE LWS_EXTERN void 240 lwsac_use_cached_file_end(lwsac_cached_file_t *cache); 241 242 LWS_VISIBLE LWS_EXTERN void 243 lwsac_use_cached_file_detach(lwsac_cached_file_t *cache); 244 245 LWS_VISIBLE LWS_EXTERN int 246 lwsac_cached_file(const char *filepath, lwsac_cached_file_t *cache, 247 size_t *len); 248 249 /* more advanced helpers */ 250 251 /* offset from lac to start of payload, first = 1 = first lac in chain */ 252 LWS_VISIBLE LWS_EXTERN size_t 253 lwsac_sizeof(int first); 254 255 LWS_VISIBLE LWS_EXTERN size_t 256 lwsac_get_tail_pos(struct lwsac *lac); 257 258 LWS_VISIBLE LWS_EXTERN struct lwsac * 259 lwsac_get_next(struct lwsac *lac); 260 261 LWS_VISIBLE LWS_EXTERN size_t 262 lwsac_align(size_t length); 263 264 LWS_VISIBLE LWS_EXTERN void 265 lwsac_info(struct lwsac *head); 266 267 LWS_VISIBLE LWS_EXTERN uint64_t 268 lwsac_total_alloc(struct lwsac *head); 269 270 LWS_VISIBLE LWS_EXTERN uint64_t 271 lwsac_total_overhead(struct lwsac *head); 272 273 /** 274 * lwsac_scan_extant() - returns existing copy of blob, or NULL 275 * 276 * \param head: the lwsac to scan 277 * \param find: the blob to look for 278 * \param len: the length of the blob to look for 279 * \param nul: nonzero if the next byte must be NUL 280 * 281 * Helper that looks through a whole lwsac for a given binary blob already 282 * present. Used in the case that lwsac contents are const once written, and 283 * strings or blobs may be repeated in the input: this allows the earlier 284 * copy to be pointed to by subsequent references without repeating the string 285 * or blob redundantly. 286 */ 287 LWS_VISIBLE LWS_EXTERN uint8_t * 288 lwsac_scan_extant(struct lwsac *head, uint8_t *find, size_t len, int nul); 289 290 ///@} 291