1/*	$NetBSD: proc_compare.c,v 1.1 2011/10/21 02:09:00 christos Exp $	*/
2
3/*-
4 * Copyright (c) 1990, 1993
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 *    may be used to endorse or promote products derived from this software
17 *    without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31#ifndef _STANDALONE
32# ifndef _KERNEL
33
34#  if HAVE_NBTOOL_CONFIG_H
35#   include "nbtool_config.h"
36#  endif
37
38#  include <sys/cdefs.h>
39#  if defined(LIBC_SCCS) && !defined(lint)
40__RCSID("$NetBSD: proc_compare.c,v 1.1 2011/10/21 02:09:00 christos Exp $");
41#  endif
42
43#  include <sys/types.h>
44#  include <sys/inttypes.h>
45#  include <sys/sysctl.h>
46#  include <stdio.h>
47#  include <util.h>
48#  include <errno.h>
49#  define PROC		struct kinfo_proc2
50#  define LWP		struct kinfo_lwp
51#  define P_RTIME_SEC	p_rtime_sec
52#  define P_RTIME_USEC	p_rtime_usec
53# else
54#  include <sys/cdefs.h>
55__KERNEL_RCSID(0, "$NetBSD: proc_compare.c,v 1.1 2011/10/21 02:09:00 christos Exp $");
56#  include <sys/param.h>
57#  include <sys/inttypes.h>
58#  include <sys/systm.h>
59#  include <sys/proc.h>
60#  include <sys/lwp.h>
61#  include <lib/libkern/libkern.h>
62#  define PROC		struct proc
63#  define LWP		struct lwp
64#  define P_RTIME_SEC	p_rtime.sec
65#  define P_RTIME_USEC	p_rtime.frac
66# endif
67/*
68 * Returns 1 if p2 is "better" than p1
69 *
70 * The algorithm for picking the "interesting" process is thus:
71 *
72 *	1) Only foreground processes are eligible - implied.
73 *	2) Runnable processes are favored over anything else.  The runner
74 *	   with the highest CPU utilization is picked (l_pctcpu).  Ties are
75 *	   broken by picking the highest pid.
76 *	3) The sleeper with the shortest sleep time is next.  With ties,
77 *	   we pick out just "short-term" sleepers (P_SINTR == 0).
78 *	4) Further ties are broken by picking the one started last.
79 *	5) Finally the one with the biggest pid wins, but that is nonsense
80 *	   because of pid randomization.
81 */
82#define	ISRUN(p)	((p)->p_nrlwps > 0)
83#define	TESTAB(a, b)	(((a) << 1) | (b))
84#define	ONLYA	2
85#define	ONLYB	1
86#define	BOTH	3
87
88int
89proc_compare(const PROC *p1, const LWP *l1, const PROC *p2, const LWP *l2)
90{
91	/*
92	 * see if at least one of them is runnable
93	 */
94	switch (TESTAB(ISRUN(p1), ISRUN(p2))) {
95	case ONLYA:
96		return 0;
97	case ONLYB:
98		return 1;
99	case BOTH:
100		/*
101		 * tie - favor one with highest recent CPU utilization
102		 */
103		if (l2->l_pctcpu > l1->l_pctcpu)
104			return 1;
105		goto out;
106	}
107	/*
108 	 * weed out zombies
109	 */
110	switch (TESTAB(P_ZOMBIE(p1), P_ZOMBIE(p2))) {
111	case ONLYA:
112		return 1;
113	case ONLYB:
114		return 0;
115	case BOTH:
116		goto out;
117	}
118	/*
119	 * pick the one with the smallest sleep time
120	 */
121	if (l1->l_slptime < l2->l_slptime)
122		return 0;
123	if (l2->l_slptime < l1->l_slptime)
124		return 1;
125
126	/*
127	 * favor one sleeping in a non-interruptible sleep
128	 */
129	if ((l1->l_flag & LW_SINTR) && (l2->l_flag & LW_SINTR) == 0)
130		return 0;
131	if ((l2->l_flag & LW_SINTR) && (l1->l_flag & LW_SINTR) == 0)
132		return 1;
133out:
134	/* tie, return the one with the smallest realtime */
135	if (p1->P_RTIME_SEC < p2->P_RTIME_SEC)
136		return 0;
137	if (p2->P_RTIME_SEC < p1->P_RTIME_SEC)
138		return 1;
139	if (p1->P_RTIME_USEC < p2->P_RTIME_USEC)
140		return 0;
141	if (p2->P_RTIME_USEC < p1->P_RTIME_USEC)
142		return 1;
143
144	return p2->p_pid > p1->p_pid;	/* Nonsense */
145}
146#endif /* STANDALONE */
147