1 /*-
2  * CAM request queue management functions.
4  * SPDX-License-Identifier: BSD-2-Clause
27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 #include <cam/cam.h>
38 #include <cam/cam_ccb.h>
39 #include <cam/cam_queue.h>
40 #include <cam/cam_debug.h>
42 static MALLOC_DEFINE(M_CAMQ, "CAM queue", "CAM queue buffers");
43 static MALLOC_DEFINE(M_CAMDEVQ, "CAM dev queue", "CAM dev queue buffers");
44 static MALLOC_DEFINE(M_CAMCCBQ, "CAM ccb queue", "CAM ccb queue buffers");
54 	camq->array_size = size;  in camq_init()
55 	if (camq->array_size != 0) {  in camq_init()
60 		camq->queue_array = malloc((size + 1) * sizeof(cam_pinfo*),  in camq_init()
62 		if (camq->queue_array == NULL) {  in camq_init()
63 			printf("camq_init: - cannot malloc array!\n");  in camq_init()
71  * Free a camq structure.  This should only be called if a controller
79 	if (queue->queue_array != NULL) {  in camq_fini()
80 		free(queue->queue_array, M_CAMQ);  in camq_fini()
89 	KASSERT(new_size >= queue->entries, ("camq_resize: "  in camq_resize()
91 	    new_size, queue->entries));  in camq_resize()
94 	if (new_array == NULL) {  in camq_resize()
103 	if (queue->queue_array != NULL) {  in camq_resize()
104 		bcopy(queue->queue_array, new_array,  in camq_resize()
105 		    (queue->entries + 1) * sizeof(cam_pinfo *));  in camq_resize()
106 		free(queue->queue_array, M_CAMQ);  in camq_resize()
108 	queue->queue_array = new_array;  in camq_resize()
109 	queue->array_size = new_size;  in camq_resize()
115  * the Heap(1, num_elements) property and array_size - num_elements >= 1,
122 	KASSERT(queue->entries < queue->array_size,  in camq_insert()
124 	    queue->entries, queue->array_size));  in camq_insert()
125 	queue->entries++;  in camq_insert()
126 	queue->queue_array[queue->entries] = new_entry;  in camq_insert()
127 	new_entry->index = queue->entries;  in camq_insert()
128 	if (queue->entries != 0)  in camq_insert()
129 		heap_up(queue->queue_array, queue->entries);  in camq_insert()
135  * num_elements, remove that entry and restore the Heap(1, num_elements-1)
143 	if (index <= 0 || index > queue->entries)  in camq_remove()
144 		panic("%s: Attempt to remove out-of-bounds index %d "  in camq_remove()
146 		    queue->entries);  in camq_remove()
148 	removed_entry = queue->queue_array[index];  in camq_remove()
149 	if (queue->entries != index) {  in camq_remove()
150 		queue->queue_array[index] = queue->queue_array[queue->entries];  in camq_remove()
151 		queue->queue_array[index]->index = index;  in camq_remove()
152 		heap_down(queue->queue_array, index, queue->entries - 1);  in camq_remove()
154 	removed_entry->index = CAM_UNQUEUED_INDEX;  in camq_remove()
155 	queue->entries--;  in camq_remove()
168 	if (new_priority > queue->queue_array[index]->priority) {  in camq_change_priority()
169 		queue->queue_array[index]->priority = new_priority;  in camq_change_priority()
170 		heap_down(queue->queue_array, index, queue->entries);  in camq_change_priority()
173 		queue->queue_array[index]->priority = new_priority;  in camq_change_priority()
174 		heap_up(queue->queue_array, index);  in camq_change_priority()
184 	if (devq == NULL) {  in cam_devq_alloc()
185 		printf("cam_devq_alloc: - cannot malloc!\n");  in cam_devq_alloc()
188 	if (cam_devq_init(devq, devices, openings) != 0) {  in cam_devq_alloc()
200 	mtx_init(&devq->send_mtx, "CAM queue lock", NULL, MTX_DEF);  in cam_devq_init()
201 	if (camq_init(&devq->send_queue, devices) != 0)  in cam_devq_init()
203 	devq->send_openings = openings;  in cam_devq_init()
204 	devq->send_active = 0;  in cam_devq_init()
212 	camq_fini(&devq->send_queue);  in cam_devq_free()
213 	mtx_destroy(&devq->send_mtx);  in cam_devq_free()
222 	retval = camq_resize(&camq->send_queue, devices);  in cam_devq_resize()
232 	if (ccbq == NULL) {  in cam_ccbq_alloc()
233 		printf("cam_ccbq_alloc: - cannot malloc!\n");  in cam_ccbq_alloc()
236 	if (cam_ccbq_init(ccbq, openings) != 0) {  in cam_ccbq_alloc()
247 	if (ccbq) {  in cam_ccbq_free()
258 	delta = new_size - (ccbq->dev_active + ccbq->dev_openings);  in cam_ccbq_resize()
259 	ccbq->total_openings += delta;  in cam_ccbq_resize()
260 	ccbq->dev_openings += delta;  in cam_ccbq_resize()
263 	if (new_size > ccbq->queue.array_size)  in cam_ccbq_resize()
264 		return (camq_resize(&ccbq->queue, new_size));  in cam_ccbq_resize()
273 	if (camq_init(&ccbq->queue,  in cam_ccbq_init()
276 	ccbq->total_openings = openings;  in cam_ccbq_init()
277 	ccbq->dev_openings = openings;  in cam_ccbq_init()
285 	camq_fini(&ccbq->queue);  in cam_ccbq_fini()
289  * Heap routines for manipulating CAM queues.
293  * and j, return less than 0, 0, or greater than 0 if i is less than,
299 	if (queue_array[i]->priority == queue_array[j]->priority)  in queue_cmp()
300 		return (  queue_array[i]->generation  in queue_cmp()
301 			- queue_array[j]->generation );  in queue_cmp()
303 		return (  queue_array[i]->priority  in queue_cmp()
304 			- queue_array[j]->priority );  in queue_cmp()
319 	queue_array[j]->index = j;  in swap()
320 	queue_array[i]->index = i;  in swap()
325  * Heap(1, new_index-1) property and a new element in location
338 		if (queue_cmp(queue_array, parent, child) <= 0)  in heap_up()
359 		if (child < num_entries) {  in heap_down()
361 			if (queue_cmp(queue_array, child + 1, child) < 0)  in heap_down()
365 		if (queue_cmp(queue_array, parent, child) <= 0)  in heap_down()