1/*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
5 * All rights reserved.
6 * Copyright (c) 2024 The FreeBSD Foundation
7 *
8 * Portions of this software were developed by Olivier Certner
9 * <olce.freebsd@certner.fr> at Kumacom SARL under sponsorship from the FreeBSD
10 * Foundation.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34#ifndef _RUNQ_H_
35#define _RUNQ_H_
36
37#ifndef _KERNEL
38#error "no user-serviceable parts inside"
39#endif
40
41#include <sys/types.h> /* For bool. */
42#include <sys/_param.h>
43#include <sys/libkern.h>
44#include <sys/queue.h>
45
46struct thread;
47
48/*
49 * Run queue parameters.
50 */
51
52#define RQ_MAX_PRIO (255) /* Maximum priority (minimum is 0). */
53#define RQ_PPQ (1) /* Priorities per queue. */
54
55/*
56 * Deduced from the above parameters and machine ones.
57 */
58#define RQ_NQS (howmany(RQ_MAX_PRIO + 1, RQ_PPQ)) /* Number of run queues. */
59#define RQ_PRI_TO_QUEUE_IDX(pri) ((pri) / RQ_PPQ) /* Priority to queue index. */
60
61typedef unsigned long rqsw_t; /* runq's status words type. */
62#define RQSW_BPW (sizeof(rqsw_t) * NBBY) /* Bits per runq word. */
63#define RQSW_PRI "%#lx" /* printf() directive. */
64
65/* Number of status words to cover RQ_NQS queues. */
66#define RQSW_NB (howmany(RQ_NQS, RQSW_BPW))
67#define RQSW_IDX(idx) ((idx) / RQSW_BPW)
68#define RQSW_BIT_IDX(idx) ((idx) % RQSW_BPW)
69#define RQSW_BIT(idx) (1ul << RQSW_BIT_IDX(idx))
70#define RQSW_BSF(word) __extension__ ({ \
71 int _res = ffsl((long)(word)); /* Assumes two-complement. */ \
72 MPASS(_res > 0); \
73 _res - 1; \
74})
75#define RQSW_TO_QUEUE_IDX(word_idx, bit_idx) \
76 (((word_idx) * RQSW_BPW) + (bit_idx))
77#define RQSW_FIRST_QUEUE_IDX(word_idx, word) \
78 RQSW_TO_QUEUE_IDX(word_idx, RQSW_BSF(word))
79
80
81/*
82 * The queue for a given index as a list of threads.
83 */
84TAILQ_HEAD(rq_queue, thread);
85
86/*
87 * Bit array which maintains the status of a run queue. When a queue is
88 * non-empty the bit corresponding to the queue number will be set.
89 */
90struct rq_status {
91 rqsw_t rq_sw[RQSW_NB];
92};
93
94/*
95 * Run queue structure. Contains an array of run queues on which processes
96 * are placed, and a structure to maintain the status of each queue.
97 */
98struct runq {
99 struct rq_status rq_status;
100 struct rq_queue rq_queues[RQ_NQS];
101};
102
103void runq_init(struct runq *);
104bool runq_is_queue_empty(struct runq *, int _idx);
105void runq_add(struct runq *, struct thread *, int _flags);
106void runq_add_idx(struct runq *, struct thread *, int _idx, int _flags);
107bool runq_remove(struct runq *, struct thread *);
108
109/*
110 * Implementation helpers for common and scheduler-specific runq_choose*()
111 * functions.
112 */
113typedef bool runq_pred_t(int _idx, struct rq_queue *, void *_data);
114int runq_findq(struct runq *const rq, const int lvl_min,
115 const int lvl_max,
116 runq_pred_t *const pred, void *const pred_data);
117struct thread *runq_first_thread_range(struct runq *const rq,
118 const int lvl_min, const int lvl_max);
119
120bool runq_not_empty(struct runq *);
121struct thread *runq_choose(struct runq *);
122struct thread *runq_choose_fuzz(struct runq *, int _fuzz);
123
124#endif