1 /* $OpenBSD: kern_bufq.c,v 1.32 2017/08/16 17:52:17 mikeb Exp $ */ 2 /* 3 * Copyright (c) 2010 Thordur I. Bjornsson <thib@openbsd.org> 4 * Copyright (c) 2010 David Gwynne <dlg@openbsd.org> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #include <sys/param.h> 20 #include <sys/systm.h> 21 #include <sys/kernel.h> 22 #include <sys/malloc.h> 23 #include <sys/mount.h> 24 #include <sys/mutex.h> 25 #include <sys/buf.h> 26 #include <sys/errno.h> 27 #include <sys/queue.h> 28 29 SLIST_HEAD(, bufq) bufqs = SLIST_HEAD_INITIALIZER(bufqs); 30 struct mutex bufqs_mtx = MUTEX_INITIALIZER(IPL_NONE); 31 int bufqs_stop; 32 33 struct bufq_impl { 34 void *(*impl_create)(void); 35 void (*impl_destroy)(void *); 36 37 void (*impl_queue)(void *, struct buf *); 38 struct buf *(*impl_dequeue)(void *); 39 void (*impl_requeue)(void *, struct buf *); 40 int (*impl_peek)(void *); 41 }; 42 43 void *bufq_fifo_create(void); 44 void bufq_fifo_destroy(void *); 45 void bufq_fifo_queue(void *, struct buf *); 46 struct buf *bufq_fifo_dequeue(void *); 47 void bufq_fifo_requeue(void *, struct buf *); 48 int bufq_fifo_peek(void *); 49 50 void *bufq_nscan_create(void); 51 void bufq_nscan_destroy(void *); 52 void bufq_nscan_queue(void *, struct buf *); 53 struct buf *bufq_nscan_dequeue(void *); 54 void bufq_nscan_requeue(void *, struct buf *); 55 int bufq_nscan_peek(void *); 56 57 const struct bufq_impl bufq_impls[BUFQ_HOWMANY] = { 58 { 59 bufq_fifo_create, 60 bufq_fifo_destroy, 61 bufq_fifo_queue, 62 bufq_fifo_dequeue, 63 bufq_fifo_requeue, 64 bufq_fifo_peek 65 }, 66 { 67 bufq_nscan_create, 68 bufq_nscan_destroy, 69 bufq_nscan_queue, 70 bufq_nscan_dequeue, 71 bufq_nscan_requeue, 72 bufq_nscan_peek 73 } 74 }; 75 76 int 77 bufq_init(struct bufq *bq, int type) 78 { 79 u_int hi = BUFQ_HI, low = BUFQ_LOW; 80 81 if (type >= BUFQ_HOWMANY) 82 panic("bufq_init: type %i unknown", type); 83 84 /* 85 * Ensure that writes can't consume the entire amount of kva 86 * available the buffer cache if we only have a limited amount 87 * of kva available to us. 88 */ 89 if (hi >= (bcstats.kvaslots / 16)) { 90 hi = bcstats.kvaslots / 16; 91 if (hi < 2) 92 hi = 2; 93 low = hi / 2; 94 } 95 96 mtx_init(&bq->bufq_mtx, IPL_BIO); 97 bq->bufq_hi = hi; 98 bq->bufq_low = low; 99 bq->bufq_type = type; 100 bq->bufq_impl = &bufq_impls[type]; 101 bq->bufq_data = bq->bufq_impl->impl_create(); 102 if (bq->bufq_data == NULL) { 103 /* 104 * we should actually return failure so disks attaching after 105 * boot in low memory situations dont panic the system. 106 */ 107 panic("bufq init fail"); 108 } 109 110 mtx_enter(&bufqs_mtx); 111 while (bufqs_stop) { 112 msleep(&bufqs_stop, &bufqs_mtx, PRIBIO, "bqinit", 0); 113 } 114 SLIST_INSERT_HEAD(&bufqs, bq, bufq_entries); 115 mtx_leave(&bufqs_mtx); 116 117 return (0); 118 } 119 120 int 121 bufq_switch(struct bufq *bq, int type) 122 { 123 void *data; 124 void *odata; 125 int otype; 126 struct buf *bp; 127 int ret; 128 129 mtx_enter(&bq->bufq_mtx); 130 ret = (bq->bufq_type == type); 131 mtx_leave(&bq->bufq_mtx); 132 if (ret) 133 return (0); 134 135 data = bufq_impls[type].impl_create(); 136 if (data == NULL) 137 return (ENOMEM); 138 139 mtx_enter(&bq->bufq_mtx); 140 if (bq->bufq_type != type) { /* might have changed during create */ 141 odata = bq->bufq_data; 142 otype = bq->bufq_type; 143 144 while ((bp = bufq_impls[otype].impl_dequeue(odata)) != NULL) 145 bufq_impls[type].impl_queue(data, bp); 146 147 bq->bufq_data = data; 148 bq->bufq_type = type; 149 bq->bufq_impl = &bufq_impls[type]; 150 } else { 151 otype = type; 152 odata = data; 153 } 154 mtx_leave(&bq->bufq_mtx); 155 156 bufq_impls[otype].impl_destroy(odata); 157 158 return (0); 159 } 160 161 void 162 bufq_destroy(struct bufq *bq) 163 { 164 bufq_drain(bq); 165 166 bq->bufq_impl->impl_destroy(bq->bufq_data); 167 bq->bufq_data = NULL; 168 169 mtx_enter(&bufqs_mtx); 170 while (bufqs_stop) { 171 msleep(&bufqs_stop, &bufqs_mtx, PRIBIO, "bqdest", 0); 172 } 173 SLIST_REMOVE(&bufqs, bq, bufq, bufq_entries); 174 mtx_leave(&bufqs_mtx); 175 } 176 177 178 void 179 bufq_queue(struct bufq *bq, struct buf *bp) 180 { 181 mtx_enter(&bq->bufq_mtx); 182 while (bq->bufq_stop) { 183 msleep(&bq->bufq_stop, &bq->bufq_mtx, PRIBIO, "bqqueue", 0); 184 } 185 186 bp->b_bq = bq; 187 bq->bufq_outstanding++; 188 bq->bufq_impl->impl_queue(bq->bufq_data, bp); 189 mtx_leave(&bq->bufq_mtx); 190 } 191 192 struct buf * 193 bufq_dequeue(struct bufq *bq) 194 { 195 struct buf *bp; 196 197 mtx_enter(&bq->bufq_mtx); 198 bp = bq->bufq_impl->impl_dequeue(bq->bufq_data); 199 mtx_leave(&bq->bufq_mtx); 200 201 return (bp); 202 } 203 204 void 205 bufq_requeue(struct bufq *bq, struct buf *bp) 206 { 207 mtx_enter(&bq->bufq_mtx); 208 bq->bufq_impl->impl_requeue(bq->bufq_data, bp); 209 mtx_leave(&bq->bufq_mtx); 210 } 211 212 int 213 bufq_peek(struct bufq *bq) 214 { 215 int rv; 216 217 mtx_enter(&bq->bufq_mtx); 218 rv = bq->bufq_impl->impl_peek(bq->bufq_data); 219 mtx_leave(&bq->bufq_mtx); 220 221 return (rv); 222 } 223 224 void 225 bufq_drain(struct bufq *bq) 226 { 227 struct buf *bp; 228 int s; 229 230 while ((bp = bufq_dequeue(bq)) != NULL) { 231 bp->b_error = ENXIO; 232 bp->b_flags |= B_ERROR; 233 s = splbio(); 234 biodone(bp); 235 splx(s); 236 } 237 } 238 239 void 240 bufq_wait(struct bufq *bq) 241 { 242 if (bq->bufq_hi) { 243 assertwaitok(); 244 mtx_enter(&bq->bufq_mtx); 245 while (bq->bufq_outstanding >= bq->bufq_hi) { 246 bq->bufq_waiting++; 247 msleep(&bq->bufq_waiting, &bq->bufq_mtx, 248 PRIBIO, "bqwait", 0); 249 bq->bufq_waiting--; 250 } 251 mtx_leave(&bq->bufq_mtx); 252 } 253 } 254 255 void 256 bufq_done(struct bufq *bq, struct buf *bp) 257 { 258 mtx_enter(&bq->bufq_mtx); 259 KASSERT(bq->bufq_outstanding > 0); 260 bq->bufq_outstanding--; 261 if (bq->bufq_stop && bq->bufq_outstanding == 0) 262 wakeup(&bq->bufq_outstanding); 263 if (bq->bufq_waiting && bq->bufq_outstanding < bq->bufq_low) 264 wakeup(&bq->bufq_waiting); 265 mtx_leave(&bq->bufq_mtx); 266 bp->b_bq = NULL; 267 } 268 269 void 270 bufq_quiesce(void) 271 { 272 struct bufq *bq; 273 274 mtx_enter(&bufqs_mtx); 275 bufqs_stop = 1; 276 mtx_leave(&bufqs_mtx); 277 /* 278 * We can safely walk the list since it can't be modified as 279 * long as bufqs_stop is non-zero. 280 */ 281 SLIST_FOREACH(bq, &bufqs, bufq_entries) { 282 mtx_enter(&bq->bufq_mtx); 283 bq->bufq_stop = 1; 284 while (bq->bufq_outstanding) { 285 msleep(&bq->bufq_outstanding, &bq->bufq_mtx, 286 PRIBIO, "bqquies", 0); 287 } 288 mtx_leave(&bq->bufq_mtx); 289 } 290 } 291 292 void 293 bufq_restart(void) 294 { 295 struct bufq *bq; 296 297 mtx_enter(&bufqs_mtx); 298 SLIST_FOREACH(bq, &bufqs, bufq_entries) { 299 mtx_enter(&bq->bufq_mtx); 300 bq->bufq_stop = 0; 301 wakeup(&bq->bufq_stop); 302 mtx_leave(&bq->bufq_mtx); 303 } 304 bufqs_stop = 0; 305 wakeup(&bufqs_stop); 306 mtx_leave(&bufqs_mtx); 307 } 308 309 310 /* 311 * fifo implementation 312 */ 313 314 void * 315 bufq_fifo_create(void) 316 { 317 struct bufq_fifo_head *head; 318 319 head = malloc(sizeof(*head), M_DEVBUF, M_NOWAIT | M_ZERO); 320 if (head == NULL) 321 return (NULL); 322 323 SIMPLEQ_INIT(head); 324 325 return (head); 326 } 327 328 void 329 bufq_fifo_destroy(void *data) 330 { 331 struct bufq_fifo_head *head = data; 332 333 free(head, M_DEVBUF, sizeof(*head)); 334 } 335 336 void 337 bufq_fifo_queue(void *data, struct buf *bp) 338 { 339 struct bufq_fifo_head *head = data; 340 341 SIMPLEQ_INSERT_TAIL(head, bp, b_bufq.bufq_data_fifo.bqf_entries); 342 } 343 344 struct buf * 345 bufq_fifo_dequeue(void *data) 346 { 347 struct bufq_fifo_head *head = data; 348 struct buf *bp; 349 350 bp = SIMPLEQ_FIRST(head); 351 if (bp != NULL) 352 SIMPLEQ_REMOVE_HEAD(head, b_bufq.bufq_data_fifo.bqf_entries); 353 354 return (bp); 355 } 356 357 void 358 bufq_fifo_requeue(void *data, struct buf *bp) 359 { 360 struct bufq_fifo_head *head = data; 361 362 SIMPLEQ_INSERT_HEAD(head, bp, b_bufq.bufq_data_fifo.bqf_entries); 363 } 364 365 int 366 bufq_fifo_peek(void *data) 367 { 368 struct bufq_fifo_head *head = data; 369 370 return (SIMPLEQ_FIRST(head) != NULL); 371 } 372 373 /* 374 * nscan implementation 375 */ 376 377 #define BUF_INORDER(ba, bb) ((ba)->b_blkno < (bb)->b_blkno) 378 379 #define dsentries b_bufq.bufq_data_nscan.bqf_entries 380 381 struct bufq_nscan_data { 382 struct bufq_nscan_head sorted; 383 struct bufq_nscan_head fifo; 384 int leftoverroom; /* Remaining number of buffer inserts allowed */ 385 }; 386 387 void bufq_nscan_resort(struct bufq_nscan_data *data); 388 void bufq_simple_nscan(struct bufq_nscan_head *, struct buf *); 389 390 void 391 bufq_simple_nscan(struct bufq_nscan_head *head, struct buf *bp) 392 { 393 struct buf *cur, *prev; 394 395 prev = NULL; 396 /* 397 * We look for the first slot where we would fit, then insert 398 * after the element we just passed. 399 */ 400 SIMPLEQ_FOREACH(cur, head, dsentries) { 401 if (BUF_INORDER(bp, cur)) 402 break; 403 prev = cur; 404 } 405 if (prev) 406 SIMPLEQ_INSERT_AFTER(head, prev, bp, dsentries); 407 else 408 SIMPLEQ_INSERT_HEAD(head, bp, dsentries); 409 410 } 411 412 /* 413 * Take N elements from the fifo queue and sort them 414 */ 415 void 416 bufq_nscan_resort(struct bufq_nscan_data *data) 417 { 418 struct bufq_nscan_head *fifo = &data->fifo; 419 struct bufq_nscan_head *sorted = &data->sorted; 420 int count, segmentsize = BUFQ_NSCAN_N; 421 struct buf *bp; 422 423 for (count = 0; count < segmentsize; count++) { 424 bp = SIMPLEQ_FIRST(fifo); 425 if (!bp) 426 break; 427 SIMPLEQ_REMOVE_HEAD(fifo, dsentries); 428 bufq_simple_nscan(sorted, bp); 429 } 430 data->leftoverroom = segmentsize - count; 431 } 432 433 void * 434 bufq_nscan_create(void) 435 { 436 struct bufq_nscan_data *data; 437 438 data = malloc(sizeof(*data), M_DEVBUF, M_NOWAIT | M_ZERO); 439 if (!data) 440 return NULL; 441 SIMPLEQ_INIT(&data->sorted); 442 SIMPLEQ_INIT(&data->fifo); 443 444 return data; 445 } 446 447 void 448 bufq_nscan_destroy(void *vdata) 449 { 450 struct bufq_nscan_data *data = vdata; 451 452 free(data, M_DEVBUF, sizeof(*data)); 453 } 454 455 void 456 bufq_nscan_queue(void *vdata, struct buf *bp) 457 { 458 struct bufq_nscan_data *data = vdata; 459 460 /* 461 * If the previous sorted segment was small, we will continue 462 * packing in bufs as long as they're in order. 463 */ 464 if (data->leftoverroom) { 465 struct buf *next = SIMPLEQ_FIRST(&data->sorted); 466 if (next && BUF_INORDER(next, bp)) { 467 bufq_simple_nscan(&data->sorted, bp); 468 data->leftoverroom--; 469 return; 470 } 471 } 472 473 SIMPLEQ_INSERT_TAIL(&data->fifo, bp, dsentries); 474 475 } 476 477 struct buf * 478 bufq_nscan_dequeue(void *vdata) 479 { 480 struct bufq_nscan_data *data = vdata; 481 struct bufq_nscan_head *sorted = &data->sorted; 482 struct buf *bp; 483 484 if (SIMPLEQ_FIRST(sorted) == NULL) 485 bufq_nscan_resort(data); 486 487 bp = SIMPLEQ_FIRST(sorted); 488 if (bp != NULL) 489 SIMPLEQ_REMOVE_HEAD(sorted, dsentries); 490 491 return (bp); 492 } 493 494 void 495 bufq_nscan_requeue(void *vdata, struct buf *bp) 496 { 497 struct bufq_nscan_data *data = vdata; 498 499 SIMPLEQ_INSERT_HEAD(&data->fifo, bp, dsentries); 500 } 501 502 int 503 bufq_nscan_peek(void *vdata) 504 { 505 struct bufq_nscan_data *data = vdata; 506 507 return (SIMPLEQ_FIRST(&data->sorted) != NULL) || 508 (SIMPLEQ_FIRST(&data->fifo) != NULL); 509 } 510