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