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
50struct lwsac;
51typedef 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 */
68typedef 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 */
74typedef 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 */
79LWS_VISIBLE LWS_EXTERN void
80lws_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 */
103LWS_VISIBLE LWS_EXTERN void *
104lwsac_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 */
125LWS_VISIBLE LWS_EXTERN void *
126lwsac_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 */
143LWS_VISIBLE LWS_EXTERN void *
144lwsac_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 */
156LWS_VISIBLE LWS_EXTERN void
157lwsac_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 */
177LWS_VISIBLE LWS_EXTERN void
178lwsac_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 */
187LWS_VISIBLE LWS_EXTERN void
188lwsac_reference(struct lwsac *head);
189
190/**
191 * lwsac_unreference() - decrease 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 */
198LWS_VISIBLE LWS_EXTERN void
199lwsac_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 */
231LWS_VISIBLE LWS_EXTERN int
232lwsac_extend(struct lwsac *head, size_t amount);
233
234/* helpers to keep a file cached in memory */
235
236LWS_VISIBLE LWS_EXTERN void
237lwsac_use_cached_file_start(lwsac_cached_file_t cache);
238
239LWS_VISIBLE LWS_EXTERN void
240lwsac_use_cached_file_end(lwsac_cached_file_t *cache);
241
242LWS_VISIBLE LWS_EXTERN void
243lwsac_use_cached_file_detach(lwsac_cached_file_t *cache);
244
245LWS_VISIBLE LWS_EXTERN int
246lwsac_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 */
252LWS_VISIBLE LWS_EXTERN size_t
253lwsac_sizeof(int first);
254
255LWS_VISIBLE LWS_EXTERN size_t
256lwsac_get_tail_pos(struct lwsac *lac);
257
258LWS_VISIBLE LWS_EXTERN struct lwsac *
259lwsac_get_next(struct lwsac *lac);
260
261LWS_VISIBLE LWS_EXTERN size_t
262lwsac_align(size_t length);
263
264LWS_VISIBLE LWS_EXTERN void
265lwsac_info(struct lwsac *head);
266
267LWS_VISIBLE LWS_EXTERN uint64_t
268lwsac_total_alloc(struct lwsac *head);
269
270LWS_VISIBLE LWS_EXTERN uint64_t
271lwsac_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 */
287LWS_VISIBLE LWS_EXTERN uint8_t *
288lwsac_scan_extant(struct lwsac *head, uint8_t *find, size_t len, int nul);
289
290///@}
291