xref: /illumos-gate/usr/src/uts/common/sys/callo.h (revision b4203d75)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
22 /*	  All Rights Reserved	*/
23 
24 
25 /*
26  * Copyright 2010 Sun Microsystems, Inc.  All rights reserved.
27  * Use is subject to license terms.
28  */
29 
30 #ifndef _SYS_CALLO_H
31 #define	_SYS_CALLO_H
32 
33 #include <sys/t_lock.h>
34 #include <sys/taskq.h>
35 #include <sys/lgrp.h>
36 #include <sys/processor.h>
37 #include <sys/cyclic.h>
38 #include <sys/kstat.h>
39 #include <sys/systm.h>
40 
41 #ifdef	__cplusplus
42 extern "C" {
43 #endif
44 
45 #ifdef	_KERNEL
46 
47 typedef struct callout_list	callout_list_t;
48 
49 /*
50  * The callout mechanism provides general-purpose event scheduling:
51  * an arbitrary function is called in a specified amount of time.
52  * The expiration time for a callout is kept in its callout list
53  * structure.
54  */
55 typedef struct callout {
56 	struct callout	*c_idnext;	/* next in ID hash, or on freelist */
57 	struct callout	*c_idprev;	/* prev in ID hash */
58 	struct callout	*c_clnext;	/* next in callout list */
59 	struct callout	*c_clprev;	/* prev in callout list */
60 	callout_id_t	c_xid;		/* extended callout ID; see below */
61 	callout_list_t	*c_list;	/* callout list */
62 	void		(*c_func)(void *); /* function to call */
63 	void		*c_arg;		/* argument to function */
64 	kthread_t	*c_executor;	/* executing thread */
65 	kcondvar_t	c_done;		/* signal callout completion */
66 	ushort_t	c_waiting;	/* untimeout waiting flag */
67 } callout_t;
68 
69 /*
70  * The callout ID (callout_id_t) uniquely identifies a callout. The callout
71  * ID is always 64 bits internally. The lower 32 bits contain an ID value.
72  * The upper 32 bits contain a generation number and flags. When the ID value
73  * wraps the generation number is incremented during ID generation. This
74  * protects callers from ID collisions that can happen as a result of the wrap.
75  *
76  * The kernel internal interface, timeout_generic(), always returns a
77  * callout_id_t. But the legacy interfaces, timeout() and realtime_timeout()
78  * return a timeout_id_t. On a 64-bit system, timeout_id_t is also 64 bits.
79  * So, the full 64-bit ID (sans the flags) can be returned. However, on 32-bit
80  * systems, timeout_id_t is 32 bits. So, only the lower 32 bits can be
81  * returned. In such cases, a default generation number of 0 is assigned to
82  * the legacy IDs.
83  *
84  * The lower 32-bit ID space is partitioned into two spaces - one for
85  * short-term callouts and one for long-term.
86  *
87  * Here is the bit layout for the callout ID:
88  *
89  *      63    62    61 ...  32    31      30     29 .. X+1  X ... 1   0
90  *  -----------------------------------------------------------------------
91  *  | Free | Exec | Generation | Long | Counter | ID bits | Table  | Type |
92  *  |      |      | number     | term | High    |         | number |      |
93  *  -----------------------------------------------------------------------
94  *
95  * Free:
96  *    This bit indicates that this callout has been freed. This is for
97  *    debugging purposes.
98  *
99  * Exec(uting):
100  *    This is the executing bit which is only set in the extended callout
101  *    ID. This bit indicates that the callout handler is currently being
102  *    executed.
103  *
104  * Generation number:
105  *    This is the generation part of the ID.
106  *
107  * Long term:
108  *    This bit indicates whether this is a short-term or a long-term callout.
109  *    The long-term bit exists to address the problem of callout ID collision
110  *    on 32-bit systems. This is an issue because the system typically
111  *    generates a large number of timeout() requests, which means that callout
112  *    IDs eventually get recycled. Most timeouts are very short-lived, so that
113  *    ID recycling isn't a problem; but there are a handful of timeouts which
114  *    are sufficiently long-lived to see their own IDs reused. We use the
115  *    long-term bit to partition the ID namespace into pieces; the short-term
116  *    space gets all the heavy traffic and can wrap frequently (i.e., on the
117  *    order of a day) with no ill effects; the long-term space gets very little
118  *    traffic and thus never wraps. That said, we need to future proof callouts
119  *    in case 32-bit systems grow in size and are able to consume callout IDs
120  *    at faster rates. So, we should make all the kernel clients that use
121  *    callouts to use the internal interface so that they can use IDs outside
122  *    of the legacy space with a proper generation number.
123  *
124  * Counter High + ID counter bits:
125  *    These bits represent the actual ID bits in the callout ID.
126  *    The highest bit of the running counter is always set; this ensures that
127  *    the callout ID is always non-zero, thus eliminating the need for an
128  *    explicit wrap-around test during ID generation.
129  *
130  * Table number:
131  *    These bits carry the table number for the callout table where the callout
132  *    is queued. Each CPU has its own callout table. So, the callout tables are
133  *    numbered from 0 - (max_ncpus - 1). Because max_ncpus is different on
134  *    different systems, the actual number of table number bits will vary
135  *    accordingly. And so will the ID counter bits.
136  *
137  * Type:
138  *    This bit represents the callout (table) type. Each CPU has one realtime
139  *    and one normal callout table.
140  */
141 #define	CALLOUT_ID_FREE		0x8000000000000000ULL
142 #define	CALLOUT_EXECUTING	0x4000000000000000ULL
143 #define	CALLOUT_ID_FLAGS	(CALLOUT_ID_FREE | CALLOUT_EXECUTING)
144 #define	CALLOUT_ID_MASK		~CALLOUT_ID_FLAGS
145 #define	CALLOUT_GENERATION_LOW	0x100000000ULL
146 #define	CALLOUT_LONGTERM	0x80000000
147 #define	CALLOUT_COUNTER_HIGH	0x40000000
148 #define	CALLOUT_TYPE_BITS	1
149 #define	CALLOUT_NTYPES		(1 << CALLOUT_TYPE_BITS)
150 #define	CALLOUT_TYPE_MASK	(CALLOUT_NTYPES - 1)
151 #define	CALLOUT_COUNTER_SHIFT	callout_table_bits
152 #define	CALLOUT_TABLE(t, f)	(((f) << CALLOUT_TYPE_BITS) | (t))
153 #define	CALLOUT_TABLE_NUM(ct)	((ct) - callout_table)
154 #define	CALLOUT_TABLE_SEQID(ct)	(CALLOUT_TABLE_NUM(ct) >> CALLOUT_TYPE_BITS)
155 
156 /*
157  * We assume that during any period of CALLOUT_LONGTERM_TICKS ticks, at most
158  * (CALLOUT_COUNTER_HIGH / callout_counter_low) callouts will be generated.
159  */
160 #define	CALLOUT_LONGTERM_TICKS	0x4000UL
161 #define	CALLOUT_BUCKET_SHIFT	9
162 #define	CALLOUT_BUCKETS		(1 << CALLOUT_BUCKET_SHIFT)
163 #define	CALLOUT_BUCKET_MASK	(CALLOUT_BUCKETS - 1)
164 #define	CALLOUT_HASH(x)		((x) & CALLOUT_BUCKET_MASK)
165 #define	CALLOUT_IDHASH(x)	CALLOUT_HASH((x) >> CALLOUT_COUNTER_SHIFT)
166 /*
167  * The multiply by 0 and 1 below are cosmetic. Just to align things better
168  * and make it more readable. The multiplications will be done at compile
169  * time.
170  */
171 #define	CALLOUT_CLHASH(x)			\
172 	CALLOUT_HASH(				\
173 	    ((x)>>(CALLOUT_BUCKET_SHIFT*0)) ^	\
174 	    ((x)>>(CALLOUT_BUCKET_SHIFT*1)) ^	\
175 	    ((x)>>(CALLOUT_BUCKET_SHIFT*2)) ^	\
176 	    ((x)>>(CALLOUT_BUCKET_SHIFT*3)))
177 
178 #define	CALLOUT_ID_TO_TABLE(id)		((id) & callout_table_mask)
179 
180 #define	CALLOUT_SHORT_ID(table)		\
181 		((callout_id_t)(table) | CALLOUT_COUNTER_HIGH)
182 #define	CALLOUT_LONG_ID(table)		\
183 		(CALLOUT_SHORT_ID(table) | CALLOUT_LONGTERM)
184 
185 #define	CALLOUT_THREADS		2
186 
187 #define	CALLOUT_REALTIME	0		/* realtime callout type */
188 #define	CALLOUT_NORMAL		1		/* normal callout type */
189 
190 /*
191  * callout_t's are cache-aligned structures allocated from kmem caches. One kmem
192  * cache is created per lgrp and is shared by all CPUs in that lgrp. Benefits:
193  *	- cache pages are mapped only in the TLBs of the CPUs of the lgrp
194  *	- data in cache pages is present only in those CPU caches
195  *	- memory access performance improves with locality-awareness in kmem
196  *
197  * The following structure is used to manage per-lgroup kmem caches.
198  *
199  * NOTE: Free callout_t's go to a callout table's freelist. CPUs map to callout
200  * tables via their sequence IDs, not CPU IDs. DR operations can cause a
201  * free list to have callouts from multiple lgrp caches. This takes away some
202  * performance, but is no worse than if we did not use lgrp caches at all.
203  */
204 typedef struct callout_cache {
205 	struct callout_cache	*cc_next;	/* link in the global list */
206 	lgrp_handle_t		cc_hand;	/* lgroup handle */
207 	kmem_cache_t		*cc_cache;	/* kmem cache pointer */
208 	kmem_cache_t		*cc_lcache;	/* kmem cache pointer */
209 } callout_cache_t;
210 
211 /*
212  * The callout hash structure is used for queueing both callouts and
213  * callout lists. That is why the fields are declared as void *.
214  */
215 typedef struct callout_hash {
216 	void	*ch_head;
217 	void	*ch_tail;
218 } callout_hash_t;
219 
220 /*
221  * CALLOUT_LIST_FLAG_FREE
222  *	Callout list is free.
223  * CALLOUT_LIST_FLAG_ABSOLUTE
224  *	Callout list contains absolute timers.
225  * CALLOUT_LIST_FLAG_HRESTIME
226  *	Callout list contains hrestime timers.
227  * CALLOUT_LIST_FLAG_NANO
228  *	Callout list contains 1-nanosecond resolution callouts.
229  * CALLOUT_LIST_FLAG_HEAPED
230  *	Callout list is present in the callout heap.
231  * CALLOUT_LIST_FLAG_QUEUED
232  *	Callout list is present in the callout queue.
233  */
234 #define	CALLOUT_LIST_FLAG_FREE			0x1
235 #define	CALLOUT_LIST_FLAG_ABSOLUTE		0x2
236 #define	CALLOUT_LIST_FLAG_HRESTIME		0x4
237 #define	CALLOUT_LIST_FLAG_NANO			0x8
238 #define	CALLOUT_LIST_FLAG_HEAPED		0x10
239 #define	CALLOUT_LIST_FLAG_QUEUED		0x20
240 
241 struct callout_list {
242 	callout_list_t	*cl_next;	/* next in clhash */
243 	callout_list_t	*cl_prev;	/* prev in clhash */
244 	hrtime_t	cl_expiration;	/* expiration for callouts in list */
245 	callout_hash_t	cl_callouts;	/* list of callouts */
246 	int		cl_flags;	/* callout flags */
247 };
248 
249 /*
250  * Callout heap element. Each element in the heap stores the expiration
251  * as well as the corresponding callout list. This is to avoid a lookup
252  * of the callout list when the heap is processed. Because we store the
253  * callout list pointer in the heap element, we have to always remove
254  * a heap element and its callout list together. We cannot remove one
255  * without the other.
256  *
257  * This structure's size must be a power of two because we want an
258  * integral number of these to fit into a page.
259  */
260 typedef struct callout_heap {
261 	hrtime_t	ch_expiration;
262 	callout_list_t	*ch_list;
263 #ifndef _LP64
264 	char		ch_pad[4];	/* pad to power of 2 */
265 #endif
266 } callout_heap_t;
267 
268 /*
269  * When the heap contains too many empty callout lists, it needs to be
270  * cleaned up. The decision to clean up the heap is a function of the
271  * number of empty entries and the heap size. Also, we don't want to
272  * clean up small heaps.
273  */
274 #define	CALLOUT_MIN_REAP	(CALLOUT_BUCKETS >> 3)
275 #define	CALLOUT_CLEANUP(ct)	((ct->ct_nreap >= callout_min_reap) &&	\
276 				    (ct->ct_nreap >= (ct->ct_heap_num >> 1)))
277 
278 /*
279  * Per-callout table kstats.
280  *
281  * CALLOUT_TIMEOUTS
282  *	Callouts created since boot.
283  * CALLOUT_TIMEOUTS_PENDING
284  *	Number of outstanding callouts.
285  * CALLOUT_UNTIMEOUTS_UNEXPIRED
286  *	Number of cancelled callouts that have not expired.
287  * CALLOUT_UNTIMEOUTS_EXECUTING
288  *	Number of cancelled callouts that were executing at the time of
289  *	cancellation.
290  * CALLOUT_UNTIMEOUTS_EXPIRED
291  *	Number of cancelled callouts that had already expired at the time
292  *	of cancellations.
293  * CALLOUT_EXPIRATIONS
294  *	Number of callouts that expired.
295  * CALLOUT_ALLOCATIONS
296  *	Number of callout structures allocated.
297  * CALLOUT_CLEANUPS
298  *	Number of times a callout table is cleaned up.
299  */
300 typedef enum callout_stat_type {
301 	CALLOUT_TIMEOUTS,
302 	CALLOUT_TIMEOUTS_PENDING,
303 	CALLOUT_UNTIMEOUTS_UNEXPIRED,
304 	CALLOUT_UNTIMEOUTS_EXECUTING,
305 	CALLOUT_UNTIMEOUTS_EXPIRED,
306 	CALLOUT_EXPIRATIONS,
307 	CALLOUT_ALLOCATIONS,
308 	CALLOUT_CLEANUPS,
309 	CALLOUT_NUM_STATS
310 } callout_stat_type_t;
311 
312 /*
313  * Callout flags:
314  *
315  * CALLOUT_FLAG_ROUNDUP
316  *	Roundup the expiration time to the next resolution boundary.
317  *	If this flag is not specified, the expiration time is rounded down.
318  * CALLOUT_FLAG_ABSOLUTE
319  *	Normally, the expiration passed to the timeout API functions is an
320  *	expiration interval. If this flag is specified, then it is
321  *	interpreted as the expiration time itself.
322  * CALLOUT_FLAG_HRESTIME
323  *	Normally, callouts are not affected by changes to system time
324  *	(hrestime). This flag is used to create a callout that is affected
325  *	by system time. If system time changes, these timers must be
326  *	handled in a special way (see callout.c). These are used by condition
327  *	variables and LWP timers that need this behavior.
328  * CALLOUT_FLAG_32BIT
329  *	Legacy interfaces timeout() and realtime_timeout() pass this flag
330  *	to timeout_generic() to indicate that a 32-bit ID should be allocated.
331  */
332 #define	CALLOUT_FLAG_ROUNDUP		0x1
333 #define	CALLOUT_FLAG_ABSOLUTE		0x2
334 #define	CALLOUT_FLAG_HRESTIME		0x4
335 #define	CALLOUT_FLAG_32BIT		0x8
336 
337 /*
338  * On 32-bit systems, the legacy interfaces, timeout() and realtime_timeout(),
339  * must pass CALLOUT_FLAG_32BIT to timeout_generic() so that a 32-bit ID
340  * can be generated.
341  */
342 #ifdef _LP64
343 #define	CALLOUT_LEGACY		0
344 #else
345 #define	CALLOUT_LEGACY		CALLOUT_FLAG_32BIT
346 #endif
347 
348 /*
349  * All of the state information associated with a callout table.
350  * The fields are ordered with cache performance in mind.
351  */
352 typedef struct callout_table {
353 	kmutex_t	ct_mutex;	/* protects all callout state */
354 	callout_t	*ct_free;	/* free callout structures */
355 	callout_list_t	*ct_lfree;	/* free callout list structures */
356 	callout_id_t	ct_short_id;	/* most recently issued short-term ID */
357 	callout_id_t	ct_long_id;	/* most recently issued long-term ID */
358 	callout_hash_t 	*ct_idhash;	/* ID hash chains */
359 	callout_hash_t 	*ct_clhash;	/* callout list hash */
360 	kstat_named_t	*ct_kstat_data;	/* callout kstat data */
361 
362 	uint_t		ct_type;	/* callout table type */
363 	uint_t		ct_suspend;	/* suspend count */
364 	cyclic_id_t	ct_cyclic;	/* cyclic for this table */
365 	callout_heap_t	*ct_heap;	/* callout expiration heap */
366 	ulong_t		ct_heap_num;	/* occupied slots in the heap */
367 	ulong_t		ct_heap_max;	/* end of the heap */
368 	kmem_cache_t	*ct_cache;	/* callout kmem cache */
369 	kmem_cache_t	*ct_lcache;	/* callout list kmem cache */
370 	callout_id_t	ct_gen_id;	/* generation based ID */
371 
372 	callout_hash_t	ct_expired;	/* list of expired callout lists */
373 	taskq_t		*ct_taskq;	/* taskq to execute normal callouts */
374 	kstat_t		*ct_kstats;	/* callout kstats */
375 	int		ct_nreap;	/* # heap entries that need reaping */
376 	cyclic_id_t	ct_qcyclic;	/* cyclic for the callout queue */
377 	callout_hash_t	ct_queue;	/* overflow queue of callouts */
378 #ifndef _LP64
379 	char		ct_pad[12];	/* cache alignment */
380 #endif
381 	/*
382 	 * This structure should be aligned to a 64-byte (cache-line)
383 	 * boundary. Make sure the padding is right for 32-bit as well
384 	 * as 64-bit kernels.
385 	 */
386 } callout_table_t;
387 
388 /*
389  * Short hand definitions for the callout kstats.
390  */
391 #define	ct_timeouts							\
392 		ct_kstat_data[CALLOUT_TIMEOUTS].value.ui64
393 #define	ct_timeouts_pending						\
394 		ct_kstat_data[CALLOUT_TIMEOUTS_PENDING].value.ui64
395 #define	ct_untimeouts_unexpired						\
396 		ct_kstat_data[CALLOUT_UNTIMEOUTS_UNEXPIRED].value.ui64
397 #define	ct_untimeouts_executing						\
398 		ct_kstat_data[CALLOUT_UNTIMEOUTS_EXECUTING].value.ui64
399 #define	ct_untimeouts_expired						\
400 		ct_kstat_data[CALLOUT_UNTIMEOUTS_EXPIRED].value.ui64
401 #define	ct_expirations							\
402 		ct_kstat_data[CALLOUT_EXPIRATIONS].value.ui64
403 #define	ct_allocations							\
404 		ct_kstat_data[CALLOUT_ALLOCATIONS].value.ui64
405 #define	ct_cleanups							\
406 		ct_kstat_data[CALLOUT_CLEANUPS].value.ui64
407 
408 /*
409  * CALLOUT_CHUNK is the minimum initial size of each heap, and the amount
410  * by which a full heap is expanded to make room for new entries.
411  */
412 #define	CALLOUT_CHUNK		(PAGESIZE / sizeof (callout_heap_t))
413 
414 /*
415  * CALLOUT_MIN_HEAP_SIZE defines the minimum size for the callout heap for
416  * the whole system.
417  */
418 #define	CALLOUT_MIN_HEAP_SIZE	(64 * 1024 * sizeof (callout_heap_t))
419 
420 /*
421  * CALLOUT_MEM_FRACTION defines the fraction of available physical memory that
422  * can be allocated towards the callout heap for the whole system.
423  */
424 #define	CALLOUT_MEM_FRACTION	4096
425 
426 #define	CALLOUT_HEAP_PARENT(index)	(((index) - 1) >> 1)
427 #define	CALLOUT_HEAP_RIGHT(index)	(((index) + 1) << 1)
428 #define	CALLOUT_HEAP_LEFT(index)	((((index) + 1) << 1) - 1)
429 
430 #define	CALLOUT_TCP_RESOLUTION		10000000ULL
431 
432 #define	CALLOUT_ALIGN	64	/* cache line size */
433 
434 #ifdef _LP64
435 #define	CALLOUT_MAX_TICKS	NSEC_TO_TICK(CY_INFINITY);
436 #else
437 #define	CALLOUT_MAX_TICKS	LONG_MAX
438 #endif
439 
440 #define	CALLOUT_TOLERANCE	200000		/* nanoseconds */
441 
442 extern void		callout_init(void);
443 extern void		membar_sync(void);
444 extern void		callout_cpu_online(cpu_t *);
445 extern void		callout_cpu_offline(cpu_t *);
446 extern void		callout_hrestime(void);
447 
448 #endif
449 
450 #ifdef	__cplusplus
451 }
452 #endif
453 
454 #endif	/* _SYS_CALLO_H */
455