1/*
2 * Copyright (c) 2016 Cisco and/or its affiliates.
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 * Copyright (c) 2016  Intel Corporation.
17 * Licensed under the Apache License, Version 2.0 (the "License");
18 * you may not use this file except in compliance with the License.
19 * You may obtain a copy of the License at:
20 *
21 *     http://www.apache.org/licenses/LICENSE-2.0
22 *
23 * Unless required by applicable law or agreed to in writing, software
24 * distributed under the License is distributed on an "AS IS" BASIS,
25 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
26 * See the License for the specific language governing permissions and
27 * limitations under the License.
28 */
29
30#include <string.h>
31#include <sys/queue.h>
32#include <rte_cycles.h>
33#include <rte_errno.h>
34#include <tle_timer.h>
35
36#define TW_SLOTS_PER_RING	512
37#define TW_RING_SHIFT		9
38#define TW_RING_MASK		(TW_SLOTS_PER_RING - 1)
39#define	MAX_TIMER_BURST		0x20
40
41enum {
42	TW_RING_FAST,
43	TW_RING_SLOW,
44	TW_N_RINGS,
45};
46
47struct tle_timer_list;
48
49struct tle_timer_elmt {
50	void *obj; /** object for which timer is created */
51
52	struct tle_timer_list *list; /* current list object belongs to */
53
54	/** Slow ring only, saved when timer added to ring */
55	uint16_t fast_index;
56
57	LIST_ENTRY(tle_timer_elmt) link;
58};
59
60struct tle_timer_list {
61	uint32_t num;
62	LIST_HEAD(, tle_timer_elmt) head;
63};
64
65struct tle_timer_wheel {
66	uint64_t next_run_time; /** Next time the wheel should run */
67
68	uint64_t last_run_time; /** Last time the wheel ran */
69
70	uint32_t current_tick; /** current tick */
71
72	uint32_t current_index[TW_N_RINGS]; /** current wheel indices */
73
74	struct tle_timer_list free; /** free timers to be used */
75
76	struct tle_timer_list expired; /** expired timers to be pulled */
77
78	struct tle_timer_wheel_args prm; /** timer wheel configuration params */
79
80	/** wheel arrays */
81	struct tle_timer_list w[TW_N_RINGS][TW_SLOTS_PER_RING];
82};
83
84/** helper functions to manipulate the linked lists */
85static inline uint32_t
86get_timers(struct tle_timer_list *list, struct tle_timer_elmt *re[],
87	uint32_t num)
88{
89	struct tle_timer_elmt *e;
90	uint32_t i, n;
91
92	n = RTE_MIN(list->num, num);
93	for (i = 0; i != n; i++) {
94		e = LIST_FIRST(&list->head);
95		LIST_REMOVE(e, link);
96		e->list = NULL;
97		re[i] = e;
98	}
99
100	list->num -= n;
101	return n;
102}
103
104static inline struct tle_timer_elmt *
105get_timer(struct tle_timer_list *list)
106{
107	struct tle_timer_elmt *e;
108
109	e = LIST_FIRST(&list->head);
110	LIST_REMOVE(e, link);
111	e->list = NULL;
112	list->num--;
113	return e;
114}
115
116static inline void
117put_timers(struct tle_timer_list *list, struct tle_timer_elmt *te[],
118	uint32_t num)
119{
120	uint32_t i;
121
122	for (i = 0; i != num; i++) {
123		te[i]->list = list;
124		LIST_INSERT_HEAD(&list->head, te[i], link);
125	}
126	list->num += num;
127}
128
129static inline void
130put_timer(struct tle_timer_list *list, struct tle_timer_elmt *e)
131{
132	e->list = list;
133	LIST_INSERT_HEAD(&list->head, e, link);
134	list->num++;
135}
136
137static inline void
138rem_timer(struct tle_timer_list *list, struct tle_timer_elmt *e)
139{
140	LIST_REMOVE(e, link);
141	e->list = NULL;
142	list->num--;
143}
144
145/** create the tle timer wheel */
146struct tle_timer_wheel *
147tle_timer_create(struct tle_timer_wheel_args *prm, uint64_t now)
148{
149	uint32_t i, j;
150	size_t sz;
151	struct tle_timer_wheel *tw;
152	struct tle_timer_elmt *e;
153	struct tle_timer_elmt *timers;
154
155	if (prm == NULL) {
156		rte_errno = -EINVAL;
157		return NULL;
158	}
159
160	/* at least one timer has to be created */
161	if (prm->max_timer == 0) {
162		rte_errno = -EINVAL;
163		return NULL;
164	}
165
166	/* do not allow tick size smaller than 1ms */
167	if (prm->tick_size == 0) {
168		rte_errno = -EINVAL;
169		return NULL;
170	}
171
172	sz = sizeof(*tw) + prm->max_timer * sizeof(struct tle_timer_elmt);
173
174	/* allocate memory */
175	tw = rte_zmalloc_socket(NULL, sz, RTE_CACHE_LINE_SIZE,
176		prm->socket_id);
177
178	if (tw == NULL) {
179		rte_errno = -ENOMEM;
180		return NULL;
181	}
182
183	tw->last_run_time = now;
184	tw->prm = *prm;
185	timers = (struct tle_timer_elmt *)(tw + 1);
186
187	/* initialize the lists */
188	LIST_INIT(&tw->free.head);
189	LIST_INIT(&tw->expired.head);
190
191	for (i = 0; i < prm->max_timer; i++) {
192		e = timers + i;
193		put_timer(&tw->free, e);
194	}
195
196	for (i = 0; i < TW_N_RINGS; i++)
197		for (j = 0; j < TW_SLOTS_PER_RING; j++)
198			LIST_INIT(&tw->w[i][j].head);
199
200	return tw;
201}
202
203/** free the tle timer wheel */
204void
205tle_timer_free(struct tle_timer_wheel *tw)
206{
207	rte_free(tw);
208}
209
210/** start a timer */
211void *
212tle_timer_start(struct tle_timer_wheel *tw, void *obj, uint64_t interval)
213{
214	uint16_t slow_ring_index, fast_ring_index;
215	struct tle_timer_list *ts;
216	struct tle_timer_elmt *e;
217	uint32_t carry;
218	uint32_t nb_tick;
219
220	rte_errno = 0;
221	if (!interval) {
222		rte_errno = EINVAL;
223		return NULL;
224	}
225
226	if (tw->free.num == 0) {
227		rte_errno = ENOMEM;
228		return NULL;
229	}
230
231	nb_tick = interval / tw->prm.tick_size;
232
233	fast_ring_index = nb_tick & TW_RING_MASK;
234	fast_ring_index += tw->current_index[TW_RING_FAST];
235	carry = fast_ring_index >= TW_SLOTS_PER_RING ? 1 : 0;
236	fast_ring_index %= TW_SLOTS_PER_RING;
237	slow_ring_index = (nb_tick >> TW_RING_SHIFT) + carry;
238
239	/* Timer duration exceeds ~7 hrs? Oops */
240	if (slow_ring_index >= TW_SLOTS_PER_RING) {
241		rte_errno = ERANGE;
242		return NULL;
243	}
244
245	/* Timer expires more than 51.2 seconds from now? */
246	if (slow_ring_index) {
247		slow_ring_index += tw->current_index[TW_RING_SLOW];
248		slow_ring_index %= TW_SLOTS_PER_RING;
249		ts = &tw->w[TW_RING_SLOW][slow_ring_index];
250
251		e = get_timer(&tw->free);
252		e->obj = obj;
253		e->fast_index = fast_ring_index;
254		put_timer(ts, e);
255
256		/* Return the user timer-cancellation handle */
257		return (void *)e;
258	}
259
260	/* Timer expires less than 51.2 seconds from now */
261	ts = &tw->w[TW_RING_FAST][fast_ring_index];
262
263	e = get_timer(&tw->free);
264	e->obj = obj;
265	put_timer(ts, e);
266
267	/* Give the user a handle to cancel the timer */
268	return (void *)e;
269}
270
271/** stop a timer */
272void tle_timer_stop(struct tle_timer_wheel *tw, void *timer)
273{
274	struct tle_timer_elmt *e;
275	struct tle_timer_list *ts;
276
277	/* Cancel the timer */
278	e = (struct tle_timer_elmt *)timer;
279	ts = e->list;
280	rem_timer(ts, e);
281	put_timer(&tw->free, e);
282}
283
284/** run the timer wheel. Call in every tick_size cycles
285 * (e.g. equivalent of 100ms).
286 */
287void tle_timer_expire(struct tle_timer_wheel *tw, uint64_t now)
288{
289	uint32_t nb_tick, i, n;
290	uint32_t fast_wheel_index, slow_wheel_index, demoted_index;
291	struct tle_timer_list *ts, *ts2;
292	struct tle_timer_elmt *re[MAX_TIMER_BURST], *e;
293
294	/* Shouldn't happen */
295	if (unlikely(now < tw->next_run_time))
296		return;
297
298	/* Number of tick_size cycles which have occurred */
299	nb_tick = (now - tw->last_run_time) / tw->prm.tick_size;
300	if (nb_tick == 0)
301		return;
302
303	/* Remember when we ran, compute next runtime */
304	tw->next_run_time = (now + tw->prm.tick_size);
305	tw->last_run_time = now;
306
307	for (i = 0; i < nb_tick; i++) {
308		fast_wheel_index = tw->current_index[TW_RING_FAST];
309
310		/* If we've been around the fast ring once,
311		 * process one slot in the slow ring before we handle
312		 * the fast ring.
313		 */
314		if (unlikely(fast_wheel_index == TW_SLOTS_PER_RING)) {
315			fast_wheel_index = tw->current_index[TW_RING_FAST] = 0;
316
317			tw->current_index[TW_RING_SLOW]++;
318			tw->current_index[TW_RING_SLOW] %= TW_SLOTS_PER_RING;
319			slow_wheel_index = tw->current_index[TW_RING_SLOW];
320
321			ts = &tw->w[TW_RING_SLOW][slow_wheel_index];
322
323			/* Deal slow-ring elements into the fast ring. */
324			while (ts->num != 0) {
325				e = get_timer(ts);
326				demoted_index = e->fast_index;
327				ts2 = &tw->w[TW_RING_FAST][demoted_index];
328				put_timer(ts2, e);
329			};
330			LIST_INIT(&ts->head);
331		}
332
333		/* Handle the fast ring */
334		ts = &tw->w[TW_RING_FAST][fast_wheel_index];
335
336		/* Clear the fast-ring slot and move timers in expired list*/
337		n = get_timers(ts, re, RTE_DIM(re));
338		while (n != 0) {
339			put_timers(&tw->expired, re, n);
340			n = get_timers(ts, re, RTE_DIM(re));
341		};
342		LIST_INIT(&ts->head);
343
344		tw->current_index[TW_RING_FAST]++;
345		tw->current_tick++;
346	}
347}
348
349/** bulk retrieve of expired timers */
350int
351tle_timer_get_expired_bulk(struct tle_timer_wheel *tw, void *rt[], uint32_t num)
352{
353	uint32_t i, n;
354	struct tle_timer_elmt *e[MAX_TIMER_BURST];
355
356	n = get_timers(&tw->expired, e, num);
357
358	for (i = 0; i != n; i++)
359		rt[i] = e[i]->obj;
360
361	put_timers(&tw->free, e, n);
362
363	return n;
364}
365