1/*
2 * Copyright (c) 2019  Intel Corporation.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#include "memtank.h"
17#include <rte_errno.h>
18
19#define	ALIGN_MUL_CEIL(v, mul)	\
20	((typeof(v))(((uint64_t)(v) + (mul) - 1) / (mul)))
21
22
23static inline size_t
24memtank_meta_size(uint32_t nb_free)
25{
26	size_t sz;
27	static const struct memtank *mt;
28
29	sz = sizeof(*mt) + nb_free * sizeof(mt->pub.free[0]);
30	sz = RTE_ALIGN_CEIL(sz, alignof(*mt));
31	return sz;
32}
33
34static inline size_t
35memchunk_meta_size(uint32_t nb_obj)
36{
37	size_t sz;
38	static const struct memchunk *ch;
39
40	sz = sizeof(*ch) +  nb_obj * sizeof(ch->free[0]);
41	sz = RTE_ALIGN_CEIL(sz, alignof(*ch));
42	return sz;
43}
44
45static inline size_t
46memobj_size(uint32_t obj_size, uint32_t obj_align)
47{
48	size_t sz;
49	static const struct memobj *obj;
50
51	sz = sizeof(*obj) + obj_size;
52	sz = RTE_ALIGN_CEIL(sz, obj_align);
53	return sz;
54}
55
56static inline size_t
57memchunk_size(uint32_t nb_obj, uint32_t obj_size, uint32_t obj_align)
58{
59	size_t algn, sz;
60	static const struct memchunk *ch;
61
62	algn = RTE_MAX(alignof(*ch), obj_align);
63	sz = memchunk_meta_size(nb_obj);
64	sz += nb_obj * memobj_size(obj_size, obj_align);
65	sz = RTE_ALIGN_CEIL(sz + algn - 1, algn);
66	return sz;
67}
68
69static void
70init_chunk(struct memtank *mt, struct memchunk *ch)
71{
72	uint32_t i, n, sz;
73	uintptr_t p;
74	struct memobj *obj;
75
76	const struct memobj cobj = {
77		.red_zone1 = RED_ZONE_V1,
78		.chunk = ch,
79		.red_zone2 = RED_ZONE_V2,
80	};
81
82	n = mt->prm.nb_obj_chunk;
83	sz = mt->obj_size;
84
85	/* get start of memobj array */
86	p = (uintptr_t)ch + memchunk_meta_size(n);
87	p = RTE_ALIGN_CEIL(p, mt->prm.obj_align);
88
89	for (i = 0; i != n; i++) {
90		obj = obj_pub_full(p, sz);
91		obj[0] = cobj;
92		ch->free[i] = (void *)p;
93		p += sz;
94	}
95
96	ch->nb_total = n;
97	ch->nb_free = n;
98
99	if (mt->prm.init != NULL)
100		mt->prm.init(ch->free, n, mt->prm.udata);
101}
102
103static void
104put_chunk(struct memtank *mt, struct memchunk *ch, void * const obj[],
105	uint32_t num)
106{
107	uint32_t k, n;
108	struct mchunk_list *ls;
109
110	/* chunk should be in the *used* list */
111	k = MC_USED;
112	ls = &mt->chl[k];
113	rte_spinlock_lock(&ls->lock);
114
115	n = ch->nb_free;
116	RTE_ASSERT(n + num <= ch->nb_total);
117
118	_copy_objs(ch->free + n, obj, num);
119	ch->nb_free = n + num;
120
121	/* chunk is full now */
122	if (ch->nb_free == ch->nb_total) {
123		TAILQ_REMOVE(&ls->chunk, ch, link);
124		k = MC_FULL;
125	/* chunk is not empty anymore, move it to the head */
126	} else if (n == 0) {
127		TAILQ_REMOVE(&ls->chunk, ch, link);
128		TAILQ_INSERT_HEAD(&ls->chunk, ch, link);
129	}
130
131	rte_spinlock_unlock(&ls->lock);
132
133	/* insert this chunk into the *full* list */
134	if (k == MC_FULL) {
135		ls = &mt->chl[k];
136		rte_spinlock_lock(&ls->lock);
137		TAILQ_INSERT_HEAD(&ls->chunk, ch, link);
138		rte_spinlock_unlock(&ls->lock);
139	}
140}
141
142static uint32_t
143shrink_chunk(struct memtank *mt, uint32_t num)
144{
145	uint32_t i, k;
146	struct mchunk_list *ls;
147	struct memchunk *ch[num];
148
149	ls = &mt->chl[MC_FULL];
150	rte_spinlock_lock(&ls->lock);
151
152	for (k = 0; k != num; k++) {
153		ch[k] = TAILQ_LAST(&ls->chunk, mchunk_head);
154		if (ch[k] == NULL)
155			break;
156		TAILQ_REMOVE(&ls->chunk, ch[k], link);
157	}
158
159	rte_spinlock_unlock(&ls->lock);
160
161	rte_atomic32_sub(&mt->nb_chunks, k);
162
163	for (i = 0; i != k; i++)
164		mt->prm.free(ch[i]->raw, mt->prm.udata);
165
166	return k;
167}
168
169static struct memchunk *
170alloc_chunk(struct memtank *mt)
171{
172	void *p;
173	struct memchunk *ch;
174
175	p = mt->prm.alloc(mt->chunk_size, mt->prm.udata);
176	if (p == NULL)
177		return NULL;
178	ch = RTE_PTR_ALIGN_CEIL(p, alignof(*ch));
179	ch->raw = p;
180	return ch;
181}
182
183/* Determine by how many chunks we can actually grow */
184static inline uint32_t
185grow_num(struct memtank *mt, uint32_t num)
186{
187	uint32_t k, n, max;
188
189	max = mt->max_chunk;
190	n = rte_atomic32_add_return(&mt->nb_chunks, num);
191
192	if (n <= max)
193		return num;
194
195	k = n - max;
196	return (k >= num) ? 0 : num - k;
197}
198
199static uint32_t
200grow_chunk(struct memtank *mt, uint32_t num)
201{
202	uint32_t i, k, n;
203	struct mchunk_list *fls;
204	struct mchunk_head ls;
205	struct memchunk *ch[num];
206
207	/* check can we grow further */
208	k = grow_num(mt, num);
209
210	for (n = 0; n != k; n++) {
211		ch[n] = alloc_chunk(mt);
212		if (ch[n] == NULL)
213			break;
214	}
215
216	TAILQ_INIT(&ls);
217
218	for (i = 0; i != n; i++) {
219		init_chunk(mt, ch[i]);
220		TAILQ_INSERT_HEAD(&ls, ch[i], link);
221	}
222
223	if (n != 0) {
224		fls = &mt->chl[MC_FULL];
225		rte_spinlock_lock(&fls->lock);
226		TAILQ_CONCAT(&fls->chunk, &ls, link);
227		rte_spinlock_unlock(&fls->lock);
228	}
229
230	if (n != num)
231		rte_atomic32_sub(&mt->nb_chunks, num - n);
232
233	return n;
234}
235
236static void
237obj_dbg_alloc(struct memtank *mt, void * const obj[], uint32_t nb_obj)
238{
239	uint32_t i, sz;
240	struct memobj *po;
241
242	sz = mt->obj_size;
243	for (i = 0; i != nb_obj; i++) {
244		po = obj_pub_full((uintptr_t)obj[i], sz);
245		RTE_VERIFY(memobj_verify(po, 0) == 0);
246		po->dbg.nb_alloc++;
247	}
248}
249
250static void
251obj_dbg_free(struct memtank *mt, void * const obj[], uint32_t nb_obj)
252{
253	uint32_t i, sz;
254	struct memobj *po;
255
256	sz = mt->obj_size;
257	for (i = 0; i != nb_obj; i++) {
258		po = obj_pub_full((uintptr_t)obj[i], sz);
259		RTE_VERIFY(memobj_verify(po, 1) == 0);
260		po->dbg.nb_free++;
261	}
262}
263
264
265void
266tle_memtank_chunk_free(struct tle_memtank *t, void * const obj[],
267	uint32_t nb_obj, uint32_t flags)
268{
269	uint32_t i, j, k, sz;
270	struct memtank *mt;
271	struct memobj *mo;
272	struct memchunk *ch[nb_obj];
273
274	mt = tank_pub_full(t);
275	sz = mt->obj_size;
276
277	if (mt->flags & TLE_MTANK_OBJ_DBG)
278		obj_dbg_free(mt, obj, nb_obj);
279
280	for (i = 0; i != nb_obj; i++) {
281		mo = obj_pub_full((uintptr_t)obj[i], sz);
282		ch[i] = mo->chunk;
283	}
284
285	k = 0;
286	for (i = 0; i != nb_obj; i = j) {
287
288		/* find number of consequtive objs from the same chunk */
289		for (j = i + 1; j != nb_obj && ch[j] == ch[i]; j++)
290			;
291
292		put_chunk(mt, ch[i], obj + i, j - i);
293		k++;
294	}
295
296	if (flags & TLE_MTANK_FREE_SHRINK)
297		shrink_chunk(mt, k);
298}
299
300static uint32_t
301get_chunk(struct mchunk_list *ls, struct mchunk_head *els,
302	struct mchunk_head *uls, void *obj[], uint32_t nb_obj)
303{
304	uint32_t l, k, n;
305	struct memchunk *ch, *nch;
306
307	rte_spinlock_lock(&ls->lock);
308
309	n = 0;
310	for (ch = TAILQ_FIRST(&ls->chunk);
311			n != nb_obj && ch != NULL && ch->nb_free != 0;
312			ch = nch, n += k) {
313
314		k = RTE_MIN(nb_obj - n, ch->nb_free);
315		l = ch->nb_free - k;
316		_copy_objs(obj + n, ch->free + l, k);
317		ch->nb_free = l;
318
319		nch = TAILQ_NEXT(ch, link);
320
321		/* chunk is empty now */
322		if (l == 0) {
323			TAILQ_REMOVE(&ls->chunk, ch, link);
324			TAILQ_INSERT_TAIL(els, ch, link);
325		} else if (uls != NULL) {
326			TAILQ_REMOVE(&ls->chunk, ch, link);
327			TAILQ_INSERT_HEAD(uls, ch, link);
328		}
329	}
330
331	rte_spinlock_unlock(&ls->lock);
332	return n;
333}
334
335uint32_t
336tle_memtank_chunk_alloc(struct tle_memtank *t, void *obj[], uint32_t nb_obj,
337	uint32_t flags)
338{
339	uint32_t k, n;
340	struct memtank *mt;
341	struct mchunk_head els, uls;
342
343	mt = tank_pub_full(t);
344
345	/* walk though the the *used* list first */
346	n = get_chunk(&mt->chl[MC_USED], &mt->chl[MC_USED].chunk, NULL,
347		obj, nb_obj);
348
349	if (n != nb_obj) {
350
351		TAILQ_INIT(&els);
352		TAILQ_INIT(&uls);
353
354		/* walk though the the *full* list */
355		n += get_chunk(&mt->chl[MC_FULL], &els, &uls,
356			obj + n, nb_obj - n);
357
358		if (n != nb_obj && (flags & TLE_MTANK_ALLOC_GROW) != 0) {
359
360			/* try to allocate extra memchunks */
361			k = ALIGN_MUL_CEIL(nb_obj - n,
362				mt->prm.nb_obj_chunk);
363			k = grow_chunk(mt, k);
364
365			/* walk through the *full* list again */
366			if (k != 0)
367				n += get_chunk(&mt->chl[MC_FULL], &els, &uls,
368					obj + n, nb_obj - n);
369		}
370
371		/* concatenate with *used* list our temporary lists */
372		rte_spinlock_lock(&mt->chl[MC_USED].lock);
373
374		/* put new non-emtpy elems at head of the *used* list */
375		TAILQ_CONCAT(&uls, &mt->chl[MC_USED].chunk, link);
376		TAILQ_CONCAT(&mt->chl[MC_USED].chunk, &uls, link);
377
378		/* put new emtpy elems at tail of the *used* list */
379		TAILQ_CONCAT(&mt->chl[MC_USED].chunk, &els, link);
380
381		rte_spinlock_unlock(&mt->chl[MC_USED].lock);
382	}
383
384	if (mt->flags & TLE_MTANK_OBJ_DBG)
385		obj_dbg_alloc(mt, obj, n);
386
387	return n;
388}
389
390int
391tle_memtank_grow(struct tle_memtank *t)
392{
393	uint32_t k, n, num;
394	struct memtank *mt;
395
396	mt = tank_pub_full(t);
397
398	/* how many chunks we need to grow */
399	k = t->min_free - t->nb_free;
400	if ((int32_t)k <= 0)
401		return 0;
402
403	num = ALIGN_MUL_CEIL(k, mt->prm.nb_obj_chunk);
404
405	/* try to grow and refill the *free* */
406	n = grow_chunk(mt, num);
407	if (n != 0)
408		_fill_free(t, k, 0);
409
410	return n;
411}
412
413int
414tle_memtank_shrink(struct tle_memtank *t)
415{
416	uint32_t n;
417	struct memtank *mt;
418
419	mt = tank_pub_full(t);
420
421	/* how many chunks we need to shrink */
422	if (t->nb_free < t->max_free)
423		return 0;
424
425	/* how many chunks we need to free */
426	n = ALIGN_MUL_CEIL(t->min_free, mt->prm.nb_obj_chunk);
427
428	/* free up to *num* chunks */
429	return shrink_chunk(mt, n);
430}
431
432static int
433check_param(const struct tle_memtank_prm *prm)
434{
435	if (prm->alloc == NULL || prm->free == NULL ||
436			prm->min_free > prm->max_free ||
437			rte_is_power_of_2(prm->obj_align) == 0)
438		return -EINVAL;
439	return 0;
440}
441
442struct tle_memtank *
443tle_memtank_create(const struct tle_memtank_prm *prm)
444{
445	int32_t rc;
446	size_t sz;
447	void *p;
448	struct memtank *mt;
449
450	rc = check_param(prm);
451	if (rc != 0) {
452		rte_errno = -rc;
453		return NULL;
454	}
455
456	sz = memtank_meta_size(prm->max_free);
457	p = prm->alloc(sz, prm->udata);
458	if (p == NULL) {
459		rte_errno = ENOMEM;
460		return NULL;
461	}
462
463	mt = RTE_PTR_ALIGN_CEIL(p, alignof(*mt));
464
465	memset(mt, 0, sizeof(*mt));
466	mt->prm = *prm;
467
468	mt->raw = p;
469	mt->chunk_size = memchunk_size(prm->nb_obj_chunk, prm->obj_size,
470		prm->obj_align);
471	mt->obj_size = memobj_size(prm->obj_size, prm->obj_align);
472	mt->max_chunk = ALIGN_MUL_CEIL(prm->max_obj, prm->nb_obj_chunk);
473	mt->flags = prm->flags;
474
475	mt->pub.min_free = prm->min_free;
476	mt->pub.max_free = prm->max_free;
477
478	TAILQ_INIT(&mt->chl[MC_FULL].chunk);
479	TAILQ_INIT(&mt->chl[MC_USED].chunk);
480
481	return &mt->pub;
482}
483
484static void
485free_mchunk_list(struct memtank *mt, struct mchunk_list *ls)
486{
487	struct memchunk *ch;
488
489	for (ch = TAILQ_FIRST(&ls->chunk); ch != NULL;
490			ch = TAILQ_FIRST(&ls->chunk)) {
491		TAILQ_REMOVE(&ls->chunk, ch, link);
492		mt->prm.free(ch->raw, mt->prm.udata);
493	}
494}
495
496void
497tle_memtank_destroy(struct tle_memtank *t)
498{
499	struct memtank *mt;
500
501	if (t != NULL) {
502		mt = tank_pub_full(t);
503		free_mchunk_list(mt, &mt->chl[MC_FULL]);
504		free_mchunk_list(mt, &mt->chl[MC_USED]);
505		mt->prm.free(mt->raw, mt->prm.udata);
506	}
507}
508