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 46 struct 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 61 typedef 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 */ 84 TAILQ_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 */ 90 struct 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 */ 98 struct runq { 99 struct rq_status rq_status; 100 struct rq_queue rq_queues[RQ_NQS]; 101 }; 102 103 void runq_init(struct runq *); 104 bool runq_is_queue_empty(struct runq *, int _idx); 105 void runq_add(struct runq *, struct thread *, int _flags); 106 void runq_add_idx(struct runq *, struct thread *, int _idx, int _flags); 107 bool runq_remove(struct runq *, struct thread *); 108 109 /* 110 * Implementation helpers for common and scheduler-specific runq_choose*() 111 * functions. 112 */ 113 typedef bool runq_pred_t(int _idx, struct rq_queue *, void *_data); 114 int 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); 117 struct thread *runq_first_thread_range(struct runq *const rq, 118 const int lvl_min, const int lvl_max); 119 120 bool runq_not_empty(struct runq *); 121 struct thread *runq_choose(struct runq *); 122 struct thread *runq_choose_fuzz(struct runq *, int _fuzz); 123 124 #endif 125