1*2b46a8cbSderaadt /* $OpenBSD: kern_bufq.c,v 1.35 2022/12/05 23:18:37 deraadt Exp $ */
2c158b662Sthib /*
3c158b662Sthib * Copyright (c) 2010 Thordur I. Bjornsson <thib@openbsd.org>
45384af04Sdlg * Copyright (c) 2010 David Gwynne <dlg@openbsd.org>
5c158b662Sthib *
6c158b662Sthib * Permission to use, copy, modify, and distribute this software for any
7c158b662Sthib * purpose with or without fee is hereby granted, provided that the above
8c158b662Sthib * copyright notice and this permission notice appear in all copies.
9c158b662Sthib *
10c158b662Sthib * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11c158b662Sthib * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12c158b662Sthib * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13c158b662Sthib * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14c158b662Sthib * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15c158b662Sthib * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16c158b662Sthib * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17c158b662Sthib */
18c158b662Sthib
19c158b662Sthib #include <sys/param.h>
20c158b662Sthib #include <sys/systm.h>
21c158b662Sthib #include <sys/malloc.h>
22b4c20274Sbeck #include <sys/mount.h>
23c158b662Sthib #include <sys/mutex.h>
24c158b662Sthib #include <sys/buf.h>
25c158b662Sthib #include <sys/errno.h>
26c158b662Sthib #include <sys/queue.h>
27c158b662Sthib
287887b06bSguenther SLIST_HEAD(, bufq) bufqs = SLIST_HEAD_INITIALIZER(bufqs);
291d5d36d3Skettenis struct mutex bufqs_mtx = MUTEX_INITIALIZER(IPL_NONE);
3075ede837Skettenis int bufqs_stop;
3175ede837Skettenis
32c2235760Sdlg struct bufq_impl {
33c2235760Sdlg void *(*impl_create)(void);
34c2235760Sdlg void (*impl_destroy)(void *);
35c2235760Sdlg
36c2235760Sdlg void (*impl_queue)(void *, struct buf *);
37c2235760Sdlg struct buf *(*impl_dequeue)(void *);
38c2235760Sdlg void (*impl_requeue)(void *, struct buf *);
39c2235760Sdlg int (*impl_peek)(void *);
40c158b662Sthib };
41c2235760Sdlg
42c2235760Sdlg void *bufq_fifo_create(void);
43c2235760Sdlg void bufq_fifo_destroy(void *);
44c2235760Sdlg void bufq_fifo_queue(void *, struct buf *);
45c2235760Sdlg struct buf *bufq_fifo_dequeue(void *);
46c2235760Sdlg void bufq_fifo_requeue(void *, struct buf *);
47c2235760Sdlg int bufq_fifo_peek(void *);
48c158b662Sthib
490aae235bSbeck void *bufq_nscan_create(void);
500aae235bSbeck void bufq_nscan_destroy(void *);
510aae235bSbeck void bufq_nscan_queue(void *, struct buf *);
520aae235bSbeck struct buf *bufq_nscan_dequeue(void *);
530aae235bSbeck void bufq_nscan_requeue(void *, struct buf *);
540aae235bSbeck int bufq_nscan_peek(void *);
550aae235bSbeck
564b9a9690Smatthew const struct bufq_impl bufq_impls[BUFQ_HOWMANY] = {
574b9a9690Smatthew {
58c2235760Sdlg bufq_fifo_create,
59c2235760Sdlg bufq_fifo_destroy,
60c2235760Sdlg bufq_fifo_queue,
61c2235760Sdlg bufq_fifo_dequeue,
62c2235760Sdlg bufq_fifo_requeue,
63c2235760Sdlg bufq_fifo_peek
640aae235bSbeck },
650aae235bSbeck {
660aae235bSbeck bufq_nscan_create,
670aae235bSbeck bufq_nscan_destroy,
680aae235bSbeck bufq_nscan_queue,
690aae235bSbeck bufq_nscan_dequeue,
700aae235bSbeck bufq_nscan_requeue,
710aae235bSbeck bufq_nscan_peek
724b9a9690Smatthew }
73c2235760Sdlg };
74c2235760Sdlg
75c2235760Sdlg int
bufq_init(struct bufq * bq,int type)76c2235760Sdlg bufq_init(struct bufq *bq, int type)
77c158b662Sthib {
78b4c20274Sbeck u_int hi = BUFQ_HI, low = BUFQ_LOW;
79b4c20274Sbeck
80319652f5Smikeb if (type >= BUFQ_HOWMANY)
81c2235760Sdlg panic("bufq_init: type %i unknown", type);
82c158b662Sthib
83b4c20274Sbeck /*
84b4c20274Sbeck * Ensure that writes can't consume the entire amount of kva
85b4c20274Sbeck * available the buffer cache if we only have a limited amount
86b4c20274Sbeck * of kva available to us.
87b4c20274Sbeck */
88b4c20274Sbeck if (hi >= (bcstats.kvaslots / 16)) {
89b4c20274Sbeck hi = bcstats.kvaslots / 16;
90b4c20274Sbeck if (hi < 2)
91b4c20274Sbeck hi = 2;
92b4c20274Sbeck low = hi / 2;
93b4c20274Sbeck }
94b4c20274Sbeck
95c158b662Sthib mtx_init(&bq->bufq_mtx, IPL_BIO);
96b4c20274Sbeck bq->bufq_hi = hi;
97b4c20274Sbeck bq->bufq_low = low;
98c158b662Sthib bq->bufq_type = type;
994b9a9690Smatthew bq->bufq_impl = &bufq_impls[type];
100c2235760Sdlg bq->bufq_data = bq->bufq_impl->impl_create();
101c2235760Sdlg if (bq->bufq_data == NULL) {
102c2235760Sdlg /*
103c2235760Sdlg * we should actually return failure so disks attaching after
104c2235760Sdlg * boot in low memory situations dont panic the system.
105c2235760Sdlg */
106c2235760Sdlg panic("bufq init fail");
107c2235760Sdlg }
108c158b662Sthib
10975ede837Skettenis mtx_enter(&bufqs_mtx);
1101d5d36d3Skettenis while (bufqs_stop) {
111babb761dSmpi msleep_nsec(&bufqs_stop, &bufqs_mtx, PRIBIO, "bqinit", INFSLP);
1121d5d36d3Skettenis }
11375ede837Skettenis SLIST_INSERT_HEAD(&bufqs, bq, bufq_entries);
11475ede837Skettenis mtx_leave(&bufqs_mtx);
11575ede837Skettenis
116c2235760Sdlg return (0);
117c2235760Sdlg }
118c2235760Sdlg
119c2235760Sdlg int
bufq_switch(struct bufq * bq,int type)120c2235760Sdlg bufq_switch(struct bufq *bq, int type)
121c2235760Sdlg {
122c2235760Sdlg void *data;
123c2235760Sdlg void *odata;
124c2235760Sdlg int otype;
125c2235760Sdlg struct buf *bp;
126c2235760Sdlg int ret;
127c2235760Sdlg
128c2235760Sdlg mtx_enter(&bq->bufq_mtx);
129c2235760Sdlg ret = (bq->bufq_type == type);
130c2235760Sdlg mtx_leave(&bq->bufq_mtx);
131c2235760Sdlg if (ret)
132c2235760Sdlg return (0);
133c2235760Sdlg
1344b9a9690Smatthew data = bufq_impls[type].impl_create();
135c2235760Sdlg if (data == NULL)
136c2235760Sdlg return (ENOMEM);
137c2235760Sdlg
138c2235760Sdlg mtx_enter(&bq->bufq_mtx);
139c2235760Sdlg if (bq->bufq_type != type) { /* might have changed during create */
140c2235760Sdlg odata = bq->bufq_data;
141c2235760Sdlg otype = bq->bufq_type;
142c2235760Sdlg
1434b9a9690Smatthew while ((bp = bufq_impls[otype].impl_dequeue(odata)) != NULL)
1444b9a9690Smatthew bufq_impls[type].impl_queue(data, bp);
145c2235760Sdlg
146c2235760Sdlg bq->bufq_data = data;
147c2235760Sdlg bq->bufq_type = type;
1484b9a9690Smatthew bq->bufq_impl = &bufq_impls[type];
149c2235760Sdlg } else {
150c2235760Sdlg otype = type;
151c2235760Sdlg odata = data;
152c2235760Sdlg }
153c2235760Sdlg mtx_leave(&bq->bufq_mtx);
154c2235760Sdlg
1554b9a9690Smatthew bufq_impls[otype].impl_destroy(odata);
156c2235760Sdlg
157c2235760Sdlg return (0);
158c158b662Sthib }
159c158b662Sthib
160c158b662Sthib void
bufq_destroy(struct bufq * bq)161c158b662Sthib bufq_destroy(struct bufq *bq)
162c158b662Sthib {
163c158b662Sthib bufq_drain(bq);
164c158b662Sthib
165c2235760Sdlg bq->bufq_impl->impl_destroy(bq->bufq_data);
166c2235760Sdlg bq->bufq_data = NULL;
167c158b662Sthib
16875ede837Skettenis mtx_enter(&bufqs_mtx);
16975ede837Skettenis while (bufqs_stop) {
170babb761dSmpi msleep_nsec(&bufqs_stop, &bufqs_mtx, PRIBIO, "bqdest", INFSLP);
17175ede837Skettenis }
17275ede837Skettenis SLIST_REMOVE(&bufqs, bq, bufq, bufq_entries);
17375ede837Skettenis mtx_leave(&bufqs_mtx);
174c158b662Sthib }
175c158b662Sthib
176c2235760Sdlg
177c158b662Sthib void
bufq_queue(struct bufq * bq,struct buf * bp)17875ede837Skettenis bufq_queue(struct bufq *bq, struct buf *bp)
17975ede837Skettenis {
18075ede837Skettenis mtx_enter(&bq->bufq_mtx);
18175ede837Skettenis while (bq->bufq_stop) {
182babb761dSmpi msleep_nsec(&bq->bufq_stop, &bq->bufq_mtx, PRIBIO, "bqqueue",
183babb761dSmpi INFSLP);
18475ede837Skettenis }
185c2235760Sdlg
186c2235760Sdlg bp->b_bq = bq;
187c2235760Sdlg bq->bufq_outstanding++;
188c2235760Sdlg bq->bufq_impl->impl_queue(bq->bufq_data, bp);
18975ede837Skettenis mtx_leave(&bq->bufq_mtx);
19075ede837Skettenis }
19175ede837Skettenis
192c2235760Sdlg struct buf *
bufq_dequeue(struct bufq * bq)193c2235760Sdlg bufq_dequeue(struct bufq *bq)
194c2235760Sdlg {
195c2235760Sdlg struct buf *bp;
196c2235760Sdlg
197c2235760Sdlg mtx_enter(&bq->bufq_mtx);
198c2235760Sdlg bp = bq->bufq_impl->impl_dequeue(bq->bufq_data);
199c2235760Sdlg mtx_leave(&bq->bufq_mtx);
200c2235760Sdlg
201c2235760Sdlg return (bp);
202c2235760Sdlg }
203c2235760Sdlg
20475ede837Skettenis void
bufq_requeue(struct bufq * bq,struct buf * bp)20575ede837Skettenis bufq_requeue(struct bufq *bq, struct buf *bp)
20675ede837Skettenis {
20775ede837Skettenis mtx_enter(&bq->bufq_mtx);
208c2235760Sdlg bq->bufq_impl->impl_requeue(bq->bufq_data, bp);
20975ede837Skettenis mtx_leave(&bq->bufq_mtx);
21075ede837Skettenis }
21175ede837Skettenis
212c2235760Sdlg int
bufq_peek(struct bufq * bq)213c2235760Sdlg bufq_peek(struct bufq *bq)
214c2235760Sdlg {
215c2235760Sdlg int rv;
216c2235760Sdlg
217c2235760Sdlg mtx_enter(&bq->bufq_mtx);
218c2235760Sdlg rv = bq->bufq_impl->impl_peek(bq->bufq_data);
219c2235760Sdlg mtx_leave(&bq->bufq_mtx);
220c2235760Sdlg
221c2235760Sdlg return (rv);
222c2235760Sdlg }
223c2235760Sdlg
22475ede837Skettenis void
bufq_drain(struct bufq * bq)225c158b662Sthib bufq_drain(struct bufq *bq)
226c158b662Sthib {
227c158b662Sthib struct buf *bp;
228c158b662Sthib int s;
229c158b662Sthib
230c2235760Sdlg while ((bp = bufq_dequeue(bq)) != NULL) {
231c158b662Sthib bp->b_error = ENXIO;
232c158b662Sthib bp->b_flags |= B_ERROR;
233c158b662Sthib s = splbio();
234c158b662Sthib biodone(bp);
235c158b662Sthib splx(s);
236c158b662Sthib }
237c158b662Sthib }
238c158b662Sthib
239c158b662Sthib void
bufq_wait(struct bufq * bq)24079acc2d2Stedu bufq_wait(struct bufq *bq)
241b4c20274Sbeck {
242b4c20274Sbeck if (bq->bufq_hi) {
243b4c20274Sbeck assertwaitok();
244b4c20274Sbeck mtx_enter(&bq->bufq_mtx);
245b4c20274Sbeck while (bq->bufq_outstanding >= bq->bufq_hi) {
246b4c20274Sbeck bq->bufq_waiting++;
247babb761dSmpi msleep_nsec(&bq->bufq_waiting, &bq->bufq_mtx,
248babb761dSmpi PRIBIO, "bqwait", INFSLP);
249b4c20274Sbeck bq->bufq_waiting--;
250b4c20274Sbeck }
251b4c20274Sbeck mtx_leave(&bq->bufq_mtx);
252b4c20274Sbeck }
253b4c20274Sbeck }
254b4c20274Sbeck
255b4c20274Sbeck void
bufq_done(struct bufq * bq,struct buf * bp)25675ede837Skettenis bufq_done(struct bufq *bq, struct buf *bp)
25775ede837Skettenis {
25875ede837Skettenis mtx_enter(&bq->bufq_mtx);
259c4427c45Smiod KASSERT(bq->bufq_outstanding > 0);
26075ede837Skettenis bq->bufq_outstanding--;
261b757b5d6Skettenis if (bq->bufq_stop && bq->bufq_outstanding == 0)
26275ede837Skettenis wakeup(&bq->bufq_outstanding);
263b4c20274Sbeck if (bq->bufq_waiting && bq->bufq_outstanding < bq->bufq_low)
2642ee83f03Sbeck wakeup(&bq->bufq_waiting);
26575ede837Skettenis mtx_leave(&bq->bufq_mtx);
26675ede837Skettenis bp->b_bq = NULL;
26775ede837Skettenis }
26875ede837Skettenis
26975ede837Skettenis void
bufq_quiesce(void)27075ede837Skettenis bufq_quiesce(void)
27175ede837Skettenis {
27275ede837Skettenis struct bufq *bq;
27375ede837Skettenis
27475ede837Skettenis mtx_enter(&bufqs_mtx);
27575ede837Skettenis bufqs_stop = 1;
2761d5d36d3Skettenis mtx_leave(&bufqs_mtx);
27774277713Skettenis /*
27874277713Skettenis * We can safely walk the list since it can't be modified as
27974277713Skettenis * long as bufqs_stop is non-zero.
28074277713Skettenis */
28174277713Skettenis SLIST_FOREACH(bq, &bufqs, bufq_entries) {
28275ede837Skettenis mtx_enter(&bq->bufq_mtx);
28375ede837Skettenis bq->bufq_stop = 1;
2841d5d36d3Skettenis while (bq->bufq_outstanding) {
285babb761dSmpi msleep_nsec(&bq->bufq_outstanding, &bq->bufq_mtx,
286babb761dSmpi PRIBIO, "bqquies", INFSLP);
28775ede837Skettenis }
28875ede837Skettenis mtx_leave(&bq->bufq_mtx);
28975ede837Skettenis }
29075ede837Skettenis }
29175ede837Skettenis
29275ede837Skettenis void
bufq_restart(void)29375ede837Skettenis bufq_restart(void)
29475ede837Skettenis {
29575ede837Skettenis struct bufq *bq;
29675ede837Skettenis
29775ede837Skettenis mtx_enter(&bufqs_mtx);
29875ede837Skettenis SLIST_FOREACH(bq, &bufqs, bufq_entries) {
29975ede837Skettenis mtx_enter(&bq->bufq_mtx);
30075ede837Skettenis bq->bufq_stop = 0;
30175ede837Skettenis wakeup(&bq->bufq_stop);
30275ede837Skettenis mtx_leave(&bq->bufq_mtx);
30375ede837Skettenis }
30475ede837Skettenis bufqs_stop = 0;
30575ede837Skettenis wakeup(&bufqs_stop);
30675ede837Skettenis mtx_leave(&bufqs_mtx);
30775ede837Skettenis }
30875ede837Skettenis
309c2235760Sdlg
310c2235760Sdlg /*
311c2235760Sdlg * fifo implementation
312c2235760Sdlg */
313c2235760Sdlg
314c2235760Sdlg void *
bufq_fifo_create(void)315c2235760Sdlg bufq_fifo_create(void)
316c2235760Sdlg {
317c2235760Sdlg struct bufq_fifo_head *head;
318c2235760Sdlg
319c2235760Sdlg head = malloc(sizeof(*head), M_DEVBUF, M_NOWAIT | M_ZERO);
320c2235760Sdlg if (head == NULL)
321c2235760Sdlg return (NULL);
322c2235760Sdlg
323c2235760Sdlg SIMPLEQ_INIT(head);
324c2235760Sdlg
325c2235760Sdlg return (head);
326c2235760Sdlg }
327c2235760Sdlg
328c2235760Sdlg void
bufq_fifo_destroy(void * data)329c2235760Sdlg bufq_fifo_destroy(void *data)
330c2235760Sdlg {
331bae2bd50Sderaadt struct bufq_fifo_head *head = data;
332bae2bd50Sderaadt
333bae2bd50Sderaadt free(head, M_DEVBUF, sizeof(*head));
334c2235760Sdlg }
335c2235760Sdlg
336c2235760Sdlg void
bufq_fifo_queue(void * data,struct buf * bp)337c2235760Sdlg bufq_fifo_queue(void *data, struct buf *bp)
338c2235760Sdlg {
339c2235760Sdlg struct bufq_fifo_head *head = data;
340c2235760Sdlg
341c2235760Sdlg SIMPLEQ_INSERT_TAIL(head, bp, b_bufq.bufq_data_fifo.bqf_entries);
342c2235760Sdlg }
343c2235760Sdlg
344c2235760Sdlg struct buf *
bufq_fifo_dequeue(void * data)345c2235760Sdlg bufq_fifo_dequeue(void *data)
346c2235760Sdlg {
347c2235760Sdlg struct bufq_fifo_head *head = data;
348c2235760Sdlg struct buf *bp;
349c2235760Sdlg
350c2235760Sdlg bp = SIMPLEQ_FIRST(head);
351c2235760Sdlg if (bp != NULL)
352c2235760Sdlg SIMPLEQ_REMOVE_HEAD(head, b_bufq.bufq_data_fifo.bqf_entries);
353c158b662Sthib
354c158b662Sthib return (bp);
355c158b662Sthib }
356c158b662Sthib
357c158b662Sthib void
bufq_fifo_requeue(void * data,struct buf * bp)358c2235760Sdlg bufq_fifo_requeue(void *data, struct buf *bp)
359c158b662Sthib {
360c2235760Sdlg struct bufq_fifo_head *head = data;
361c158b662Sthib
362212c947bSmatthew SIMPLEQ_INSERT_HEAD(head, bp, b_bufq.bufq_data_fifo.bqf_entries);
363c158b662Sthib }
364c158b662Sthib
365c158b662Sthib int
bufq_fifo_peek(void * data)366c2235760Sdlg bufq_fifo_peek(void *data)
367c158b662Sthib {
368c2235760Sdlg struct bufq_fifo_head *head = data;
369c158b662Sthib
370c2235760Sdlg return (SIMPLEQ_FIRST(head) != NULL);
371c158b662Sthib }
3720aae235bSbeck
3730aae235bSbeck /*
3740aae235bSbeck * nscan implementation
3750aae235bSbeck */
3760aae235bSbeck
37719a2caaeSdlg #define BUF_INORDER(ba, bb) ((ba)->b_blkno < (bb)->b_blkno)
3780aae235bSbeck
3790aae235bSbeck #define dsentries b_bufq.bufq_data_nscan.bqf_entries
3800aae235bSbeck
3810aae235bSbeck struct bufq_nscan_data {
3820aae235bSbeck struct bufq_nscan_head sorted;
3830aae235bSbeck struct bufq_nscan_head fifo;
38421cecceaSbeck int leftoverroom; /* Remaining number of buffer inserts allowed */
3850aae235bSbeck };
3860aae235bSbeck
3870aae235bSbeck void bufq_nscan_resort(struct bufq_nscan_data *data);
3880aae235bSbeck void bufq_simple_nscan(struct bufq_nscan_head *, struct buf *);
3890aae235bSbeck
3900aae235bSbeck void
bufq_simple_nscan(struct bufq_nscan_head * head,struct buf * bp)3910aae235bSbeck bufq_simple_nscan(struct bufq_nscan_head *head, struct buf *bp)
3920aae235bSbeck {
3930aae235bSbeck struct buf *cur, *prev;
3940aae235bSbeck
3950aae235bSbeck prev = NULL;
3960aae235bSbeck /*
3970aae235bSbeck * We look for the first slot where we would fit, then insert
3980aae235bSbeck * after the element we just passed.
3990aae235bSbeck */
4000aae235bSbeck SIMPLEQ_FOREACH(cur, head, dsentries) {
4010aae235bSbeck if (BUF_INORDER(bp, cur))
4020aae235bSbeck break;
4030aae235bSbeck prev = cur;
4040aae235bSbeck }
4050aae235bSbeck if (prev)
4060aae235bSbeck SIMPLEQ_INSERT_AFTER(head, prev, bp, dsentries);
4070aae235bSbeck else
4080aae235bSbeck SIMPLEQ_INSERT_HEAD(head, bp, dsentries);
4090aae235bSbeck
4100aae235bSbeck }
4110aae235bSbeck
4120aae235bSbeck /*
4130aae235bSbeck * Take N elements from the fifo queue and sort them
4140aae235bSbeck */
4150aae235bSbeck void
bufq_nscan_resort(struct bufq_nscan_data * data)4160aae235bSbeck bufq_nscan_resort(struct bufq_nscan_data *data)
4170aae235bSbeck {
4180aae235bSbeck struct bufq_nscan_head *fifo = &data->fifo;
4190aae235bSbeck struct bufq_nscan_head *sorted = &data->sorted;
4200aae235bSbeck int count, segmentsize = BUFQ_NSCAN_N;
4210aae235bSbeck struct buf *bp;
4220aae235bSbeck
4230aae235bSbeck for (count = 0; count < segmentsize; count++) {
4240aae235bSbeck bp = SIMPLEQ_FIRST(fifo);
4250aae235bSbeck if (!bp)
4260aae235bSbeck break;
4270aae235bSbeck SIMPLEQ_REMOVE_HEAD(fifo, dsentries);
4280aae235bSbeck bufq_simple_nscan(sorted, bp);
4290aae235bSbeck }
4300aae235bSbeck data->leftoverroom = segmentsize - count;
4310aae235bSbeck }
4320aae235bSbeck
4330aae235bSbeck void *
bufq_nscan_create(void)4340aae235bSbeck bufq_nscan_create(void)
4350aae235bSbeck {
4360aae235bSbeck struct bufq_nscan_data *data;
4370aae235bSbeck
4380aae235bSbeck data = malloc(sizeof(*data), M_DEVBUF, M_NOWAIT | M_ZERO);
4390aae235bSbeck if (!data)
4400aae235bSbeck return NULL;
4410aae235bSbeck SIMPLEQ_INIT(&data->sorted);
4420aae235bSbeck SIMPLEQ_INIT(&data->fifo);
4430aae235bSbeck
4440aae235bSbeck return data;
4450aae235bSbeck }
4460aae235bSbeck
4470aae235bSbeck void
bufq_nscan_destroy(void * vdata)4480aae235bSbeck bufq_nscan_destroy(void *vdata)
4490aae235bSbeck {
450bae2bd50Sderaadt struct bufq_nscan_data *data = vdata;
451bae2bd50Sderaadt
452bae2bd50Sderaadt free(data, M_DEVBUF, sizeof(*data));
4530aae235bSbeck }
4540aae235bSbeck
4550aae235bSbeck void
bufq_nscan_queue(void * vdata,struct buf * bp)4560aae235bSbeck bufq_nscan_queue(void *vdata, struct buf *bp)
4570aae235bSbeck {
4580aae235bSbeck struct bufq_nscan_data *data = vdata;
4590aae235bSbeck
4600aae235bSbeck /*
46121cecceaSbeck * If the previous sorted segment was small, we will continue
4620aae235bSbeck * packing in bufs as long as they're in order.
4630aae235bSbeck */
4640aae235bSbeck if (data->leftoverroom) {
4650aae235bSbeck struct buf *next = SIMPLEQ_FIRST(&data->sorted);
4660aae235bSbeck if (next && BUF_INORDER(next, bp)) {
4670aae235bSbeck bufq_simple_nscan(&data->sorted, bp);
46821cecceaSbeck data->leftoverroom--;
4690aae235bSbeck return;
4700aae235bSbeck }
4710aae235bSbeck }
4720aae235bSbeck
4730aae235bSbeck SIMPLEQ_INSERT_TAIL(&data->fifo, bp, dsentries);
4740aae235bSbeck
4750aae235bSbeck }
4760aae235bSbeck
4770aae235bSbeck struct buf *
bufq_nscan_dequeue(void * vdata)4780aae235bSbeck bufq_nscan_dequeue(void *vdata)
4790aae235bSbeck {
4800aae235bSbeck struct bufq_nscan_data *data = vdata;
4810aae235bSbeck struct bufq_nscan_head *sorted = &data->sorted;
4820aae235bSbeck struct buf *bp;
4830aae235bSbeck
4840aae235bSbeck if (SIMPLEQ_FIRST(sorted) == NULL)
4850aae235bSbeck bufq_nscan_resort(data);
4860aae235bSbeck
4870aae235bSbeck bp = SIMPLEQ_FIRST(sorted);
4880aae235bSbeck if (bp != NULL)
4890aae235bSbeck SIMPLEQ_REMOVE_HEAD(sorted, dsentries);
4900aae235bSbeck
4910aae235bSbeck return (bp);
4920aae235bSbeck }
4930aae235bSbeck
4940aae235bSbeck void
bufq_nscan_requeue(void * vdata,struct buf * bp)4950aae235bSbeck bufq_nscan_requeue(void *vdata, struct buf *bp)
4960aae235bSbeck {
4970aae235bSbeck struct bufq_nscan_data *data = vdata;
4980aae235bSbeck
4990aae235bSbeck SIMPLEQ_INSERT_HEAD(&data->fifo, bp, dsentries);
5000aae235bSbeck }
5010aae235bSbeck
5020aae235bSbeck int
bufq_nscan_peek(void * vdata)5030aae235bSbeck bufq_nscan_peek(void *vdata)
5040aae235bSbeck {
5050aae235bSbeck struct bufq_nscan_data *data = vdata;
5060aae235bSbeck
5070aae235bSbeck return (SIMPLEQ_FIRST(&data->sorted) != NULL) ||
5080aae235bSbeck (SIMPLEQ_FIRST(&data->fifo) != NULL);
5090aae235bSbeck }
510