xref: /freebsd/sys/cam/cam_queue.h (revision a5921bc3653e2e286715e6fe8d473ec0d02da38c)
1 /*-
2  * CAM request queue management definitions.
3  *
4  * Copyright (c) 1997 Justin T. Gibbs.
5  * 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  *    without modification, immediately at the beginning of the file.
13  * 2. The name of the author may not be used to endorse or promote products
14  *    derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
20  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26  * SUCH DAMAGE.
27  *
28  * $FreeBSD$
29  */
30 
31 #ifndef _CAM_CAM_QUEUE_H
32 #define _CAM_CAM_QUEUE_H 1
33 
34 #ifdef _KERNEL
35 
36 #include <sys/lock.h>
37 #include <sys/mutex.h>
38 #include <sys/queue.h>
39 #include <cam/cam.h>
40 
41 /*
42  * This structure implements a heap based priority queue.  The queue
43  * assumes that the objects stored in it begin with a cam_qentry
44  * structure holding the priority information used to sort the objects.
45  * This structure is opaque to clients (outside of the XPT layer) to allow
46  * the implementation to change without affecting them.
47  */
48 struct camq {
49 	cam_pinfo **queue_array;
50 	int	   array_size;
51 	int	   entries;
52 	u_int32_t  generation;
53 	u_int32_t  qfrozen_cnt;
54 };
55 
56 TAILQ_HEAD(ccb_hdr_tailq, ccb_hdr);
57 LIST_HEAD(ccb_hdr_list, ccb_hdr);
58 SLIST_HEAD(ccb_hdr_slist, ccb_hdr);
59 
60 struct cam_ccbq {
61 	struct	camq queue;
62 	struct ccb_hdr_tailq	queue_extra_head;
63 	int	queue_extra_entries;
64 	int	total_openings;
65 	int	allocated;
66 	int	dev_openings;
67 	int	dev_active;
68 };
69 
70 struct cam_ed;
71 
72 struct cam_devq {
73 	struct mtx	 send_mtx;
74 	struct camq	 send_queue;
75 	int		 send_openings;
76 	int		 send_active;
77 };
78 
79 
80 struct cam_devq *cam_devq_alloc(int devices, int openings);
81 
82 int		 cam_devq_init(struct cam_devq *devq, int devices,
83 			       int openings);
84 
85 void		 cam_devq_free(struct cam_devq *devq);
86 
87 u_int32_t	 cam_devq_resize(struct cam_devq *camq, int openings);
88 
89 /*
90  * Allocate a cam_ccb_queue structure and initialize it.
91  */
92 struct cam_ccbq	*cam_ccbq_alloc(int openings);
93 
94 u_int32_t	cam_ccbq_resize(struct cam_ccbq *ccbq, int devices);
95 
96 int		cam_ccbq_init(struct cam_ccbq *ccbq, int openings);
97 
98 void		cam_ccbq_free(struct cam_ccbq *ccbq);
99 
100 void		cam_ccbq_fini(struct cam_ccbq *ccbq);
101 
102 /*
103  * Allocate and initialize a cam_queue structure.
104  */
105 struct camq	*camq_alloc(int size);
106 
107 /*
108  * Resize a cam queue
109  */
110 u_int32_t	camq_resize(struct camq *queue, int new_size);
111 
112 /*
113  * Initialize a camq structure.  Return 0 on success, 1 on failure.
114  */
115 int		camq_init(struct camq *camq, int size);
116 
117 /*
118  * Free a cam_queue structure.  This should only be called if a controller
119  * driver failes somehow during its attach routine or is unloaded and has
120  * obtained a cam_queue structure.
121  */
122 void		camq_free(struct camq *queue);
123 
124 /*
125  * Finialize any internal storage or state of a cam_queue.
126  */
127 void		camq_fini(struct camq *queue);
128 
129 /*
130  * cam_queue_insert: Given a CAM queue with at least one open spot,
131  * insert the new entry maintaining order.
132  */
133 void		camq_insert(struct camq *queue, cam_pinfo *new_entry);
134 
135 /*
136  * camq_remove: Remove and arbitrary entry from the queue maintaining
137  * queue order.
138  */
139 cam_pinfo	*camq_remove(struct camq *queue, int index);
140 #define CAMQ_HEAD 1	/* Head of queue index */
141 
142 /* Index the first element in the heap */
143 #define CAMQ_GET_HEAD(camq) ((camq)->queue_array[CAMQ_HEAD])
144 
145 /* Get the first element priority. */
146 #define CAMQ_GET_PRIO(camq) (((camq)->entries > 0) ?			\
147 			    ((camq)->queue_array[CAMQ_HEAD]->priority) : 0)
148 
149 /*
150  * camq_change_priority: Raise or lower the priority of an entry
151  * maintaining queue order.
152  */
153 void		camq_change_priority(struct camq *queue, int index,
154 				     u_int32_t new_priority);
155 
156 static __inline int
157 cam_ccbq_pending_ccb_count(struct cam_ccbq *ccbq);
158 
159 static __inline void
160 cam_ccbq_take_opening(struct cam_ccbq *ccbq);
161 
162 static __inline void
163 cam_ccbq_insert_ccb(struct cam_ccbq *ccbq, union ccb *new_ccb);
164 
165 static __inline void
166 cam_ccbq_remove_ccb(struct cam_ccbq *ccbq, union ccb *ccb);
167 
168 static __inline union ccb *
169 cam_ccbq_peek_ccb(struct cam_ccbq *ccbq, int index);
170 
171 static __inline void
172 cam_ccbq_send_ccb(struct cam_ccbq *queue, union ccb *send_ccb);
173 
174 static __inline void
175 cam_ccbq_ccb_done(struct cam_ccbq *ccbq, union ccb *done_ccb);
176 
177 static __inline void
178 cam_ccbq_release_opening(struct cam_ccbq *ccbq);
179 
180 
181 static __inline int
182 cam_ccbq_pending_ccb_count(struct cam_ccbq *ccbq)
183 {
184 	return (ccbq->queue.entries + ccbq->queue_extra_entries);
185 }
186 
187 static __inline void
188 cam_ccbq_take_opening(struct cam_ccbq *ccbq)
189 {
190 
191 	ccbq->allocated++;
192 }
193 
194 static __inline void
195 cam_ccbq_insert_ccb(struct cam_ccbq *ccbq, union ccb *new_ccb)
196 {
197 	struct ccb_hdr *old_ccb;
198 	struct camq *queue = &ccbq->queue;
199 
200 	/*
201 	 * If queue is already full, try to resize.
202 	 * If resize fail, push CCB with lowest priority out to the TAILQ.
203 	 */
204 	if (queue->entries == queue->array_size &&
205 	    camq_resize(&ccbq->queue, queue->array_size * 2) != CAM_REQ_CMP) {
206 		old_ccb = (struct ccb_hdr *)camq_remove(queue, queue->entries);
207 		TAILQ_INSERT_HEAD(&ccbq->queue_extra_head, old_ccb,
208 		    xpt_links.tqe);
209 		old_ccb->pinfo.index = CAM_EXTRAQ_INDEX;
210 		ccbq->queue_extra_entries++;
211 	}
212 
213 	camq_insert(queue, &new_ccb->ccb_h.pinfo);
214 }
215 
216 static __inline void
217 cam_ccbq_remove_ccb(struct cam_ccbq *ccbq, union ccb *ccb)
218 {
219 	struct ccb_hdr *cccb, *bccb;
220 	struct camq *queue = &ccbq->queue;
221 
222 	/* If the CCB is on the TAILQ, remove it from there. */
223 	if (ccb->ccb_h.pinfo.index == CAM_EXTRAQ_INDEX) {
224 		TAILQ_REMOVE(&ccbq->queue_extra_head, &ccb->ccb_h,
225 		    xpt_links.tqe);
226 		ccb->ccb_h.pinfo.index = CAM_UNQUEUED_INDEX;
227 		ccbq->queue_extra_entries--;
228 		return;
229 	}
230 
231 	camq_remove(queue, ccb->ccb_h.pinfo.index);
232 
233 	/*
234 	 * If there are some CCBs on TAILQ, find the best one and move it
235 	 * to the emptied space in the queue.
236 	 */
237 	bccb = TAILQ_FIRST(&ccbq->queue_extra_head);
238 	if (bccb == NULL)
239 		return;
240 	TAILQ_FOREACH(cccb, &ccbq->queue_extra_head, xpt_links.tqe) {
241 		if (bccb->pinfo.priority > cccb->pinfo.priority ||
242 		    (bccb->pinfo.priority == cccb->pinfo.priority &&
243 		     GENERATIONCMP(bccb->pinfo.generation, >,
244 		      cccb->pinfo.generation)))
245 		        bccb = cccb;
246 	}
247 	TAILQ_REMOVE(&ccbq->queue_extra_head, bccb, xpt_links.tqe);
248 	ccbq->queue_extra_entries--;
249 	camq_insert(queue, &bccb->pinfo);
250 }
251 
252 static __inline union ccb *
253 cam_ccbq_peek_ccb(struct cam_ccbq *ccbq, int index)
254 {
255 	return((union ccb *)ccbq->queue.queue_array[index]);
256 }
257 
258 static __inline void
259 cam_ccbq_send_ccb(struct cam_ccbq *ccbq, union ccb *send_ccb)
260 {
261 
262 	send_ccb->ccb_h.pinfo.index = CAM_ACTIVE_INDEX;
263 	ccbq->dev_active++;
264 	ccbq->dev_openings--;
265 }
266 
267 static __inline void
268 cam_ccbq_ccb_done(struct cam_ccbq *ccbq, union ccb *done_ccb)
269 {
270 
271 	ccbq->dev_active--;
272 	ccbq->dev_openings++;
273 }
274 
275 static __inline void
276 cam_ccbq_release_opening(struct cam_ccbq *ccbq)
277 {
278 
279 	ccbq->allocated--;
280 }
281 
282 #endif /* _KERNEL */
283 #endif  /* _CAM_CAM_QUEUE_H */
284