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: stable/11/sys/cam/cam_queue.h 308352 2016-11-05 20:23:18Z markj $
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 */
48struct 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
56TAILQ_HEAD(ccb_hdr_tailq, ccb_hdr);
57LIST_HEAD(ccb_hdr_list, ccb_hdr);
58SLIST_HEAD(ccb_hdr_slist, ccb_hdr);
59
60struct 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
70struct cam_ed;
71
72struct cam_devq {
73	struct mtx	 send_mtx;
74	struct camq	 send_queue;
75	int		 send_openings;
76	int		 send_active;
77};
78
79
80struct cam_devq *cam_devq_alloc(int devices, int openings);
81
82int		 cam_devq_init(struct cam_devq *devq, int devices,
83			       int openings);
84
85void		 cam_devq_free(struct cam_devq *devq);
86
87u_int32_t	 cam_devq_resize(struct cam_devq *camq, int openings);
88
89/*
90 * Allocate a cam_ccb_queue structure and initialize it.
91 */
92struct cam_ccbq	*cam_ccbq_alloc(int openings);
93
94u_int32_t	cam_ccbq_resize(struct cam_ccbq *ccbq, int devices);
95
96int		cam_ccbq_init(struct cam_ccbq *ccbq, int openings);
97
98void		cam_ccbq_free(struct cam_ccbq *ccbq);
99
100void		cam_ccbq_fini(struct cam_ccbq *ccbq);
101
102/*
103 * Allocate and initialize a cam_queue structure.
104 */
105struct camq	*camq_alloc(int size);
106
107/*
108 * Resize a cam queue
109 */
110u_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 */
115int		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 */
122void		camq_free(struct camq *queue);
123
124/*
125 * Finialize any internal storage or state of a cam_queue.
126 */
127void		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 */
133void		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 */
139cam_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 */
153void		camq_change_priority(struct camq *queue, int index,
154				     u_int32_t new_priority);
155
156static __inline int
157cam_ccbq_pending_ccb_count(struct cam_ccbq *ccbq);
158
159static __inline void
160cam_ccbq_take_opening(struct cam_ccbq *ccbq);
161
162static __inline void
163cam_ccbq_insert_ccb(struct cam_ccbq *ccbq, union ccb *new_ccb);
164
165static __inline void
166cam_ccbq_remove_ccb(struct cam_ccbq *ccbq, union ccb *ccb);
167
168static __inline union ccb *
169cam_ccbq_peek_ccb(struct cam_ccbq *ccbq, int index);
170
171static __inline void
172cam_ccbq_send_ccb(struct cam_ccbq *queue, union ccb *send_ccb);
173
174static __inline void
175cam_ccbq_ccb_done(struct cam_ccbq *ccbq, union ccb *done_ccb);
176
177static __inline void
178cam_ccbq_release_opening(struct cam_ccbq *ccbq);
179
180
181static __inline int
182cam_ccbq_pending_ccb_count(struct cam_ccbq *ccbq)
183{
184	return (ccbq->queue.entries + ccbq->queue_extra_entries);
185}
186
187static __inline void
188cam_ccbq_take_opening(struct cam_ccbq *ccbq)
189{
190
191	ccbq->allocated++;
192}
193
194static __inline void
195cam_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	KASSERT((new_ccb->ccb_h.func_code & XPT_FC_QUEUED) != 0 &&
201	    (new_ccb->ccb_h.func_code & XPT_FC_USER_CCB) == 0,
202	    ("%s: Cannot queue ccb %p func_code %#x", __func__, new_ccb,
203	     new_ccb->ccb_h.func_code));
204
205	/*
206	 * If queue is already full, try to resize.
207	 * If resize fail, push CCB with lowest priority out to the TAILQ.
208	 */
209	if (queue->entries == queue->array_size &&
210	    camq_resize(&ccbq->queue, queue->array_size * 2) != CAM_REQ_CMP) {
211		old_ccb = (struct ccb_hdr *)camq_remove(queue, queue->entries);
212		TAILQ_INSERT_HEAD(&ccbq->queue_extra_head, old_ccb,
213		    xpt_links.tqe);
214		old_ccb->pinfo.index = CAM_EXTRAQ_INDEX;
215		ccbq->queue_extra_entries++;
216	}
217
218	camq_insert(queue, &new_ccb->ccb_h.pinfo);
219}
220
221static __inline void
222cam_ccbq_remove_ccb(struct cam_ccbq *ccbq, union ccb *ccb)
223{
224	struct ccb_hdr *cccb, *bccb;
225	struct camq *queue = &ccbq->queue;
226	cam_pinfo *removed_entry __unused;
227
228	/* If the CCB is on the TAILQ, remove it from there. */
229	if (ccb->ccb_h.pinfo.index == CAM_EXTRAQ_INDEX) {
230		TAILQ_REMOVE(&ccbq->queue_extra_head, &ccb->ccb_h,
231		    xpt_links.tqe);
232		ccb->ccb_h.pinfo.index = CAM_UNQUEUED_INDEX;
233		ccbq->queue_extra_entries--;
234		return;
235	}
236
237	removed_entry = camq_remove(queue, ccb->ccb_h.pinfo.index);
238	KASSERT(removed_entry == &ccb->ccb_h.pinfo,
239	    ("%s: Removed wrong entry from queue (%p != %p)", __func__,
240	     removed_entry, &ccb->ccb_h.pinfo));
241
242	/*
243	 * If there are some CCBs on TAILQ, find the best one and move it
244	 * to the emptied space in the queue.
245	 */
246	bccb = TAILQ_FIRST(&ccbq->queue_extra_head);
247	if (bccb == NULL)
248		return;
249	TAILQ_FOREACH(cccb, &ccbq->queue_extra_head, xpt_links.tqe) {
250		if (bccb->pinfo.priority > cccb->pinfo.priority ||
251		    (bccb->pinfo.priority == cccb->pinfo.priority &&
252		     GENERATIONCMP(bccb->pinfo.generation, >,
253		      cccb->pinfo.generation)))
254		        bccb = cccb;
255	}
256	TAILQ_REMOVE(&ccbq->queue_extra_head, bccb, xpt_links.tqe);
257	ccbq->queue_extra_entries--;
258	camq_insert(queue, &bccb->pinfo);
259}
260
261static __inline union ccb *
262cam_ccbq_peek_ccb(struct cam_ccbq *ccbq, int index)
263{
264	return((union ccb *)ccbq->queue.queue_array[index]);
265}
266
267static __inline void
268cam_ccbq_send_ccb(struct cam_ccbq *ccbq, union ccb *send_ccb)
269{
270
271	send_ccb->ccb_h.pinfo.index = CAM_ACTIVE_INDEX;
272	ccbq->dev_active++;
273	ccbq->dev_openings--;
274}
275
276static __inline void
277cam_ccbq_ccb_done(struct cam_ccbq *ccbq, union ccb *done_ccb)
278{
279
280	ccbq->dev_active--;
281	ccbq->dev_openings++;
282}
283
284static __inline void
285cam_ccbq_release_opening(struct cam_ccbq *ccbq)
286{
287
288	ccbq->allocated--;
289}
290
291#endif /* _KERNEL */
292#endif  /* _CAM_CAM_QUEUE_H */
293