/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* Operations on sleepq_t structures.
*
* A sleep queue is a singly linked NULL-terminated list with doubly
* linked circular sublists. The singly linked list is in descending
* priority order and FIFO for threads of the same priority. It links
* through the t_link field of the thread structure. The doubly linked
* sublists link threads of the same priority. They use the t_priforw
* and t_priback fields of the thread structure.
*
* Graphically (with priorities in parens):
*
* ________________ _______ _______
* / \ / \ / \
* | | | | | |
* v v v v v v
* t1(60)-->t2(60)-->t3(60)-->t4(50)-->t5(50)-->t6(30)-->t7(0)-->t8(0)
* ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
* | | | | | | | | | |
* \______/ \______/ \_______/ \__/ \_______/
*
* There are three interesting operations on a sleepq list: inserting
* a thread into the proper position according to priority; removing a
* thread given a pointer to it; and walking the list, possibly
* removing threads along the way. This design allows all three
* operations to be performed efficiently and easily.
*
* To insert a thread, traverse the list looking for the sublist of
* the same priority as the thread (or one of a lower priority,
* meaning there are no other threads in the list of the same
* priority). This can be done without touching all threads in the
* list by following the links between the first threads in each
* sublist. Given a thread t that is the head of a sublist (the first
* thread of that priority found when following the t_link pointers),
* t->t_priback->t_link points to the head of the next sublist. It's
* important to do this since a sleepq may contain thousands of
* threads.
*
* Removing a thread from the list is also efficient. First, the
* t_sleepq field contains a pointer to the sleepq on which a thread
* is waiting (or NULL if it's not on a sleepq). This is used to
* determine if the given thread is on the given sleepq without
* searching the list. Assuming it is, if it's not the head of a
* sublist, just remove it from the sublist and use the t_priback
* pointer to find the thread that points to it with t_link. If it is
* the head of a sublist, search for it by walking the sublist heads,
* similar to searching for a given priority level when inserting a
* thread.
*
* To walk the list, simply follow the t_link pointers. Removing
* threads along the way can be done easily if the code maintains a
* pointer to the t_link field that pointed to the thread being
* removed.
*/
/*
* Common code to unlink a thread from the queue. tpp is a pointer to
* the t_link pointer that points to tp.
*/
void
{
/* remove it from the t_link list */
/*
* Take it off the priority sublist if there's more than one
* thread there.
*/
}
/* Clear out the link junk */
}
/*
* Insert thread t into sleep queue spq in dispatch priority order.
* For lwp_rwlock_t queueing, we must queue writers ahead of readers
* of the same priority. We do this by making writers appear to have
* a half point higher priority for purposes of priority comparisions.
*/
void
{
break;
}
*tpp = t;
/* last_tp points to the last thread of this priority */
} else {
}
}
/*
* Yank a particular thread out of sleep queue and wake it up.
*/
void
{
/* remove it from queue */
sleepq_dequeue(t);
/* wake it up */
t->t_sobj_ops = NULL;
/*
* Change thread to transition state without
* dropping the sleep queue lock.
*/
}
/*
* Yank a particular thread out of sleep queue but don't wake it up.
*/
void
{
/*
* Is it the head of a priority sublist? If so, need to walk
* the priorities to find the t_link pointer that points to it.
*/
if (*ptl != t) {
/*
* Find the right priority level.
*/
}
sleepq_unlink(ptl, t);
}
{
/*
* Let the target thread know it was cv_signal()ed.
* This assumes that cv_signal() is the only
* caller of sleepq_wakeone_chan(). If this
* becomes false, this code must be revised.
*/
return (tp);
}
}
return (NULL);
}
void
{
continue;
}
}
}