xref: /freebsd/sys/kern/vfs_cluster.c (revision 09e8dea79366f1e5b3a73e8a271b26e4b6bf2e6a)
1 /*-
2  * Copyright (c) 1993
3  *	The Regents of the University of California.  All rights reserved.
4  * Modifications/enhancements:
5  * 	Copyright (c) 1995 John S. Dyson.  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  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  * 3. All advertising materials mentioning features or use of this software
16  *    must display the following acknowledgement:
17  *	This product includes software developed by the University of
18  *	California, Berkeley and its contributors.
19  * 4. Neither the name of the University nor the names of its contributors
20  *    may be used to endorse or promote products derived from this software
21  *    without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33  * SUCH DAMAGE.
34  *
35  *	@(#)vfs_cluster.c	8.7 (Berkeley) 2/13/94
36  * $FreeBSD$
37  */
38 
39 #include "opt_debug_cluster.h"
40 
41 #include <sys/param.h>
42 #include <sys/systm.h>
43 #include <sys/stdint.h>
44 #include <sys/kernel.h>
45 #include <sys/proc.h>
46 #include <sys/bio.h>
47 #include <sys/buf.h>
48 #include <sys/vnode.h>
49 #include <sys/malloc.h>
50 #include <sys/mount.h>
51 #include <sys/resourcevar.h>
52 #include <sys/vmmeter.h>
53 #include <vm/vm.h>
54 #include <vm/vm_object.h>
55 #include <vm/vm_page.h>
56 #include <sys/sysctl.h>
57 
58 #if defined(CLUSTERDEBUG)
59 #include <sys/sysctl.h>
60 static int	rcluster= 0;
61 SYSCTL_INT(_debug, OID_AUTO, rcluster, CTLFLAG_RW, &rcluster, 0,
62     "Debug VFS clustering code");
63 #endif
64 
65 static MALLOC_DEFINE(M_SEGMENT, "cluster_save buffer", "cluster_save buffer");
66 
67 static struct cluster_save *
68 	cluster_collectbufs(struct vnode *vp, struct buf *last_bp);
69 static struct buf *
70 	cluster_rbuild(struct vnode *vp, u_quad_t filesize, daddr_t lbn,
71 			 daddr_t blkno, long size, int run, struct buf *fbp);
72 
73 static int write_behind = 1;
74 SYSCTL_INT(_vfs, OID_AUTO, write_behind, CTLFLAG_RW, &write_behind, 0,
75     "Cluster write-behind; 0: disable, 1: enable, 2: backed off");
76 
77 /* Page expended to mark partially backed buffers */
78 extern vm_page_t	bogus_page;
79 
80 /*
81  * Number of physical bufs (pbufs) this subsystem is allowed.
82  * Manipulated by vm_pager.c
83  */
84 extern int cluster_pbuf_freecnt;
85 
86 /*
87  * Maximum number of blocks for read-ahead.
88  */
89 #define MAXRA 32
90 
91 /*
92  * Read data to a buf, including read-ahead if we find this to be beneficial.
93  * cluster_read replaces bread.
94  */
95 int
96 cluster_read(vp, filesize, lblkno, size, cred, totread, seqcount, bpp)
97 	struct vnode *vp;
98 	u_quad_t filesize;
99 	daddr_t lblkno;
100 	long size;
101 	struct ucred *cred;
102 	long totread;
103 	int seqcount;
104 	struct buf **bpp;
105 {
106 	struct buf *bp, *rbp, *reqbp;
107 	daddr_t blkno, origblkno;
108 	int error, num_ra;
109 	int i;
110 	int maxra, racluster;
111 	long origtotread;
112 
113 	error = 0;
114 
115 	/*
116 	 * Try to limit the amount of read-ahead by a few
117 	 * ad-hoc parameters.  This needs work!!!
118 	 */
119 	racluster = vp->v_mount->mnt_iosize_max / size;
120 	maxra = 2 * racluster + (totread / size);
121 	if (maxra > MAXRA)
122 		maxra = MAXRA;
123 	if (maxra > nbuf/8)
124 		maxra = nbuf/8;
125 
126 	/*
127 	 * get the requested block
128 	 */
129 	*bpp = reqbp = bp = getblk(vp, lblkno, size, 0, 0);
130 	origblkno = lblkno;
131 	origtotread = totread;
132 
133 	/*
134 	 * if it is in the cache, then check to see if the reads have been
135 	 * sequential.  If they have, then try some read-ahead, otherwise
136 	 * back-off on prospective read-aheads.
137 	 */
138 	if (bp->b_flags & B_CACHE) {
139 		if (!seqcount) {
140 			return 0;
141 		} else if ((bp->b_flags & B_RAM) == 0) {
142 			return 0;
143 		} else {
144 			int s;
145 			struct buf *tbp;
146 			bp->b_flags &= ~B_RAM;
147 			/*
148 			 * We do the spl here so that there is no window
149 			 * between the incore and the b_usecount increment
150 			 * below.  We opt to keep the spl out of the loop
151 			 * for efficiency.
152 			 */
153 			s = splbio();
154 			for (i = 1; i < maxra; i++) {
155 
156 				if (!(tbp = incore(vp, lblkno+i))) {
157 					break;
158 				}
159 
160 				/*
161 				 * Set another read-ahead mark so we know
162 				 * to check again.
163 				 */
164 				if (((i % racluster) == (racluster - 1)) ||
165 					(i == (maxra - 1)))
166 					tbp->b_flags |= B_RAM;
167 			}
168 			splx(s);
169 			if (i >= maxra) {
170 				return 0;
171 			}
172 			lblkno += i;
173 		}
174 		reqbp = bp = NULL;
175 	} else {
176 		off_t firstread = bp->b_offset;
177 
178 		KASSERT(bp->b_offset != NOOFFSET,
179 		    ("cluster_read: no buffer offset"));
180 		if (firstread + totread > filesize)
181 			totread = filesize - firstread;
182 		if (totread > size) {
183 			int nblks = 0;
184 			int ncontigafter;
185 			while (totread > 0) {
186 				nblks++;
187 				totread -= size;
188 			}
189 			if (nblks == 1)
190 				goto single_block_read;
191 			if (nblks > racluster)
192 				nblks = racluster;
193 
194 	    		error = VOP_BMAP(vp, lblkno, NULL,
195 				&blkno, &ncontigafter, NULL);
196 			if (error)
197 				goto single_block_read;
198 			if (blkno == -1)
199 				goto single_block_read;
200 			if (ncontigafter == 0)
201 				goto single_block_read;
202 			if (ncontigafter + 1 < nblks)
203 				nblks = ncontigafter + 1;
204 
205 			bp = cluster_rbuild(vp, filesize, lblkno,
206 				blkno, size, nblks, bp);
207 			lblkno += (bp->b_bufsize / size);
208 		} else {
209 single_block_read:
210 			/*
211 			 * if it isn't in the cache, then get a chunk from
212 			 * disk if sequential, otherwise just get the block.
213 			 */
214 			bp->b_flags |= B_RAM;
215 			bp->b_iocmd = BIO_READ;
216 			lblkno += 1;
217 		}
218 	}
219 
220 	/*
221 	 * if we have been doing sequential I/O, then do some read-ahead
222 	 */
223 	rbp = NULL;
224 	if (seqcount && (lblkno < (origblkno + seqcount))) {
225 		/*
226 		 * we now build the read-ahead buffer if it is desirable.
227 		 */
228 		if (((u_quad_t)(lblkno + 1) * size) <= filesize &&
229 		    !(error = VOP_BMAP(vp, lblkno, NULL, &blkno, &num_ra, NULL)) &&
230 		    blkno != -1) {
231 			int nblksread;
232 			int ntoread = num_ra + 1;
233 			nblksread = (origtotread + size - 1) / size;
234 			if (seqcount < nblksread)
235 				seqcount = nblksread;
236 			if (seqcount < ntoread)
237 				ntoread = seqcount;
238 			if (num_ra) {
239 				rbp = cluster_rbuild(vp, filesize, lblkno,
240 					blkno, size, ntoread, NULL);
241 			} else {
242 				rbp = getblk(vp, lblkno, size, 0, 0);
243 				rbp->b_flags |= B_ASYNC | B_RAM;
244 				rbp->b_iocmd = BIO_READ;
245 				rbp->b_blkno = blkno;
246 			}
247 		}
248 	}
249 
250 	/*
251 	 * handle the synchronous read
252 	 */
253 	if (bp) {
254 #if defined(CLUSTERDEBUG)
255 		if (rcluster)
256 			printf("S(%ld,%ld,%d) ",
257 			    (long)bp->b_lblkno, bp->b_bcount, seqcount);
258 #endif
259 		if ((bp->b_flags & B_CLUSTER) == 0) {
260 			vfs_busy_pages(bp, 0);
261 		}
262 		bp->b_flags &= ~B_INVAL;
263 		bp->b_ioflags &= ~BIO_ERROR;
264 		if ((bp->b_flags & B_ASYNC) || bp->b_iodone != NULL)
265 			BUF_KERNPROC(bp);
266 		error = VOP_STRATEGY(vp, bp);
267 		curproc->p_stats->p_ru.ru_inblock++;
268 	}
269 
270 	/*
271 	 * and if we have read-aheads, do them too
272 	 */
273 	if (rbp) {
274 		if (error) {
275 			rbp->b_flags &= ~B_ASYNC;
276 			brelse(rbp);
277 		} else if (rbp->b_flags & B_CACHE) {
278 			rbp->b_flags &= ~B_ASYNC;
279 			bqrelse(rbp);
280 		} else {
281 #if defined(CLUSTERDEBUG)
282 			if (rcluster) {
283 				if (bp)
284 					printf("A+");
285 				else
286 					printf("A");
287 				printf("(%lld,%ld,%lld,%d) ",
288 				    (intmax_t)rbp->b_lblkno, rbp->b_bcount,
289 				    (intmax_t)(rbp->b_lblkno - origblkno),
290 				    seqcount);
291 			}
292 #endif
293 
294 			if ((rbp->b_flags & B_CLUSTER) == 0) {
295 				vfs_busy_pages(rbp, 0);
296 			}
297 			rbp->b_flags &= ~B_INVAL;
298 			rbp->b_ioflags &= ~BIO_ERROR;
299 			if ((rbp->b_flags & B_ASYNC) || rbp->b_iodone != NULL)
300 				BUF_KERNPROC(rbp);
301 			(void) VOP_STRATEGY(vp, rbp);
302 			curproc->p_stats->p_ru.ru_inblock++;
303 		}
304 	}
305 	if (reqbp)
306 		return (bufwait(reqbp));
307 	else
308 		return (error);
309 }
310 
311 /*
312  * If blocks are contiguous on disk, use this to provide clustered
313  * read ahead.  We will read as many blocks as possible sequentially
314  * and then parcel them up into logical blocks in the buffer hash table.
315  */
316 static struct buf *
317 cluster_rbuild(vp, filesize, lbn, blkno, size, run, fbp)
318 	struct vnode *vp;
319 	u_quad_t filesize;
320 	daddr_t lbn;
321 	daddr_t blkno;
322 	long size;
323 	int run;
324 	struct buf *fbp;
325 {
326 	struct buf *bp, *tbp;
327 	daddr_t bn;
328 	int i, inc, j;
329 
330 	GIANT_REQUIRED;
331 
332 	KASSERT(size == vp->v_mount->mnt_stat.f_iosize,
333 	    ("cluster_rbuild: size %ld != filesize %ld\n",
334 	    size, vp->v_mount->mnt_stat.f_iosize));
335 
336 	/*
337 	 * avoid a division
338 	 */
339 	while ((u_quad_t) size * (lbn + run) > filesize) {
340 		--run;
341 	}
342 
343 	if (fbp) {
344 		tbp = fbp;
345 		tbp->b_iocmd = BIO_READ;
346 	} else {
347 		tbp = getblk(vp, lbn, size, 0, 0);
348 		if (tbp->b_flags & B_CACHE)
349 			return tbp;
350 		tbp->b_flags |= B_ASYNC | B_RAM;
351 		tbp->b_iocmd = BIO_READ;
352 	}
353 
354 	tbp->b_blkno = blkno;
355 	if( (tbp->b_flags & B_MALLOC) ||
356 		((tbp->b_flags & B_VMIO) == 0) || (run <= 1) )
357 		return tbp;
358 
359 	bp = trypbuf(&cluster_pbuf_freecnt);
360 	if (bp == 0)
361 		return tbp;
362 
363 	/*
364 	 * We are synthesizing a buffer out of vm_page_t's, but
365 	 * if the block size is not page aligned then the starting
366 	 * address may not be either.  Inherit the b_data offset
367 	 * from the original buffer.
368 	 */
369 	bp->b_data = (char *)((vm_offset_t)bp->b_data |
370 	    ((vm_offset_t)tbp->b_data & PAGE_MASK));
371 	bp->b_flags = B_ASYNC | B_CLUSTER | B_VMIO;
372 	bp->b_iocmd = BIO_READ;
373 	bp->b_iodone = cluster_callback;
374 	bp->b_blkno = blkno;
375 	bp->b_lblkno = lbn;
376 	bp->b_offset = tbp->b_offset;
377 	KASSERT(bp->b_offset != NOOFFSET, ("cluster_rbuild: no buffer offset"));
378 	pbgetvp(vp, bp);
379 
380 	TAILQ_INIT(&bp->b_cluster.cluster_head);
381 
382 	bp->b_bcount = 0;
383 	bp->b_bufsize = 0;
384 	bp->b_npages = 0;
385 
386 	inc = btodb(size);
387 	for (bn = blkno, i = 0; i < run; ++i, bn += inc) {
388 		if (i != 0) {
389 			if ((bp->b_npages * PAGE_SIZE) +
390 			    round_page(size) > vp->v_mount->mnt_iosize_max) {
391 				break;
392 			}
393 
394 			/*
395 			 * Shortcut some checks and try to avoid buffers that
396 			 * would block in the lock.  The same checks have to
397 			 * be made again after we officially get the buffer.
398 			 */
399 			if ((tbp = incore(vp, lbn + i)) != NULL) {
400 				if (BUF_LOCK(tbp, LK_EXCLUSIVE | LK_NOWAIT))
401 					break;
402 				BUF_UNLOCK(tbp);
403 
404 				for (j = 0; j < tbp->b_npages; j++) {
405 					if (tbp->b_pages[j]->valid)
406 						break;
407 				}
408 
409 				if (j != tbp->b_npages)
410 					break;
411 
412 				if (tbp->b_bcount != size)
413 					break;
414 			}
415 
416 			tbp = getblk(vp, lbn + i, size, 0, 0);
417 
418 			/*
419 			 * Stop scanning if the buffer is fully valid
420 			 * (marked B_CACHE), or locked (may be doing a
421 			 * background write), or if the buffer is not
422 			 * VMIO backed.  The clustering code can only deal
423 			 * with VMIO-backed buffers.
424 			 */
425 			if ((tbp->b_flags & (B_CACHE|B_LOCKED)) ||
426 				(tbp->b_flags & B_VMIO) == 0) {
427 				bqrelse(tbp);
428 				break;
429 			}
430 
431 			/*
432 			 * The buffer must be completely invalid in order to
433 			 * take part in the cluster.  If it is partially valid
434 			 * then we stop.
435 			 */
436 			for (j = 0;j < tbp->b_npages; j++) {
437 				if (tbp->b_pages[j]->valid)
438 					break;
439 			}
440 			if (j != tbp->b_npages) {
441 				bqrelse(tbp);
442 				break;
443 			}
444 
445 			/*
446 			 * Set a read-ahead mark as appropriate
447 			 */
448 			if ((fbp && (i == 1)) || (i == (run - 1)))
449 				tbp->b_flags |= B_RAM;
450 
451 			/*
452 			 * Set the buffer up for an async read (XXX should
453 			 * we do this only if we do not wind up brelse()ing?).
454 			 * Set the block number if it isn't set, otherwise
455 			 * if it is make sure it matches the block number we
456 			 * expect.
457 			 */
458 			tbp->b_flags |= B_ASYNC;
459 			tbp->b_iocmd = BIO_READ;
460 			if (tbp->b_blkno == tbp->b_lblkno) {
461 				tbp->b_blkno = bn;
462 			} else if (tbp->b_blkno != bn) {
463 				brelse(tbp);
464 				break;
465 			}
466 		}
467 		/*
468 		 * XXX fbp from caller may not be B_ASYNC, but we are going
469 		 * to biodone() it in cluster_callback() anyway
470 		 */
471 		BUF_KERNPROC(tbp);
472 		TAILQ_INSERT_TAIL(&bp->b_cluster.cluster_head,
473 			tbp, b_cluster.cluster_entry);
474 		for (j = 0; j < tbp->b_npages; j += 1) {
475 			vm_page_t m;
476 			m = tbp->b_pages[j];
477 			vm_page_io_start(m);
478 			vm_object_pip_add(m->object, 1);
479 			if ((bp->b_npages == 0) ||
480 				(bp->b_pages[bp->b_npages-1] != m)) {
481 				bp->b_pages[bp->b_npages] = m;
482 				bp->b_npages++;
483 			}
484 			if ((m->valid & VM_PAGE_BITS_ALL) == VM_PAGE_BITS_ALL)
485 				tbp->b_pages[j] = bogus_page;
486 		}
487 		/*
488 		 * XXX shouldn't this be += size for both, like in
489 		 * cluster_wbuild()?
490 		 *
491 		 * Don't inherit tbp->b_bufsize as it may be larger due to
492 		 * a non-page-aligned size.  Instead just aggregate using
493 		 * 'size'.
494 		 */
495 		if (tbp->b_bcount != size)
496 			printf("warning: tbp->b_bcount wrong %ld vs %ld\n", tbp->b_bcount, size);
497 		if (tbp->b_bufsize != size)
498 			printf("warning: tbp->b_bufsize wrong %ld vs %ld\n", tbp->b_bufsize, size);
499 		bp->b_bcount += size;
500 		bp->b_bufsize += size;
501 	}
502 
503 	/*
504 	 * Fully valid pages in the cluster are already good and do not need
505 	 * to be re-read from disk.  Replace the page with bogus_page
506 	 */
507 	for (j = 0; j < bp->b_npages; j++) {
508 		if ((bp->b_pages[j]->valid & VM_PAGE_BITS_ALL) ==
509 		    VM_PAGE_BITS_ALL) {
510 			bp->b_pages[j] = bogus_page;
511 		}
512 	}
513 	if (bp->b_bufsize > bp->b_kvasize)
514 		panic("cluster_rbuild: b_bufsize(%ld) > b_kvasize(%d)\n",
515 		    bp->b_bufsize, bp->b_kvasize);
516 	bp->b_kvasize = bp->b_bufsize;
517 
518 	pmap_qenter(trunc_page((vm_offset_t) bp->b_data),
519 		(vm_page_t *)bp->b_pages, bp->b_npages);
520 	return (bp);
521 }
522 
523 /*
524  * Cleanup after a clustered read or write.
525  * This is complicated by the fact that any of the buffers might have
526  * extra memory (if there were no empty buffer headers at allocbuf time)
527  * that we will need to shift around.
528  */
529 void
530 cluster_callback(bp)
531 	struct buf *bp;
532 {
533 	struct buf *nbp, *tbp;
534 	int error = 0;
535 
536 	GIANT_REQUIRED;
537 
538 	/*
539 	 * Must propogate errors to all the components.
540 	 */
541 	if (bp->b_ioflags & BIO_ERROR)
542 		error = bp->b_error;
543 
544 	pmap_qremove(trunc_page((vm_offset_t) bp->b_data), bp->b_npages);
545 	/*
546 	 * Move memory from the large cluster buffer into the component
547 	 * buffers and mark IO as done on these.
548 	 */
549 	for (tbp = TAILQ_FIRST(&bp->b_cluster.cluster_head);
550 		tbp; tbp = nbp) {
551 		nbp = TAILQ_NEXT(&tbp->b_cluster, cluster_entry);
552 		if (error) {
553 			tbp->b_ioflags |= BIO_ERROR;
554 			tbp->b_error = error;
555 		} else {
556 			tbp->b_dirtyoff = tbp->b_dirtyend = 0;
557 			tbp->b_flags &= ~B_INVAL;
558 			tbp->b_ioflags &= ~BIO_ERROR;
559 			/*
560 			 * XXX the bdwrite()/bqrelse() issued during
561 			 * cluster building clears B_RELBUF (see bqrelse()
562 			 * comment).  If direct I/O was specified, we have
563 			 * to restore it here to allow the buffer and VM
564 			 * to be freed.
565 			 */
566 			if (tbp->b_flags & B_DIRECT)
567 				tbp->b_flags |= B_RELBUF;
568 		}
569 		bufdone(tbp);
570 	}
571 	relpbuf(bp, &cluster_pbuf_freecnt);
572 }
573 
574 /*
575  *	cluster_wbuild_wb:
576  *
577  *	Implement modified write build for cluster.
578  *
579  *		write_behind = 0	write behind disabled
580  *		write_behind = 1	write behind normal (default)
581  *		write_behind = 2	write behind backed-off
582  */
583 
584 static __inline int
585 cluster_wbuild_wb(struct vnode *vp, long size, daddr_t start_lbn, int len)
586 {
587 	int r = 0;
588 
589 	switch(write_behind) {
590 	case 2:
591 		if (start_lbn < len)
592 			break;
593 		start_lbn -= len;
594 		/* fall through */
595 	case 1:
596 		r = cluster_wbuild(vp, size, start_lbn, len);
597 		/* fall through */
598 	default:
599 		/* fall through */
600 		break;
601 	}
602 	return(r);
603 }
604 
605 /*
606  * Do clustered write for FFS.
607  *
608  * Three cases:
609  *	1. Write is not sequential (write asynchronously)
610  *	Write is sequential:
611  *	2.	beginning of cluster - begin cluster
612  *	3.	middle of a cluster - add to cluster
613  *	4.	end of a cluster - asynchronously write cluster
614  */
615 void
616 cluster_write(bp, filesize, seqcount)
617 	struct buf *bp;
618 	u_quad_t filesize;
619 	int seqcount;
620 {
621 	struct vnode *vp;
622 	daddr_t lbn;
623 	int maxclen, cursize;
624 	int lblocksize;
625 	int async;
626 
627 	vp = bp->b_vp;
628 	if (vp->v_type == VREG) {
629 		async = vp->v_mount->mnt_flag & MNT_ASYNC;
630 		lblocksize = vp->v_mount->mnt_stat.f_iosize;
631 	} else {
632 		async = 0;
633 		lblocksize = bp->b_bufsize;
634 	}
635 	lbn = bp->b_lblkno;
636 	KASSERT(bp->b_offset != NOOFFSET, ("cluster_write: no buffer offset"));
637 
638 	/* Initialize vnode to beginning of file. */
639 	if (lbn == 0)
640 		vp->v_lasta = vp->v_clen = vp->v_cstart = vp->v_lastw = 0;
641 
642 	if (vp->v_clen == 0 || lbn != vp->v_lastw + 1 ||
643 	    (bp->b_blkno != vp->v_lasta + btodb(lblocksize))) {
644 		maxclen = vp->v_mount->mnt_iosize_max / lblocksize - 1;
645 		if (vp->v_clen != 0) {
646 			/*
647 			 * Next block is not sequential.
648 			 *
649 			 * If we are not writing at end of file, the process
650 			 * seeked to another point in the file since its last
651 			 * write, or we have reached our maximum cluster size,
652 			 * then push the previous cluster. Otherwise try
653 			 * reallocating to make it sequential.
654 			 *
655 			 * Change to algorithm: only push previous cluster if
656 			 * it was sequential from the point of view of the
657 			 * seqcount heuristic, otherwise leave the buffer
658 			 * intact so we can potentially optimize the I/O
659 			 * later on in the buf_daemon or update daemon
660 			 * flush.
661 			 */
662 			cursize = vp->v_lastw - vp->v_cstart + 1;
663 			if (((u_quad_t) bp->b_offset + lblocksize) != filesize ||
664 			    lbn != vp->v_lastw + 1 || vp->v_clen <= cursize) {
665 				if (!async && seqcount > 0) {
666 					cluster_wbuild_wb(vp, lblocksize,
667 						vp->v_cstart, cursize);
668 				}
669 			} else {
670 				struct buf **bpp, **endbp;
671 				struct cluster_save *buflist;
672 
673 				buflist = cluster_collectbufs(vp, bp);
674 				endbp = &buflist->bs_children
675 				    [buflist->bs_nchildren - 1];
676 				if (VOP_REALLOCBLKS(vp, buflist)) {
677 					/*
678 					 * Failed, push the previous cluster
679 					 * if *really* writing sequentially
680 					 * in the logical file (seqcount > 1),
681 					 * otherwise delay it in the hopes that
682 					 * the low level disk driver can
683 					 * optimize the write ordering.
684 					 */
685 					for (bpp = buflist->bs_children;
686 					     bpp < endbp; bpp++)
687 						brelse(*bpp);
688 					free(buflist, M_SEGMENT);
689 					if (seqcount > 1) {
690 						cluster_wbuild_wb(vp,
691 						    lblocksize, vp->v_cstart,
692 						    cursize);
693 					}
694 				} else {
695 					/*
696 					 * Succeeded, keep building cluster.
697 					 */
698 					for (bpp = buflist->bs_children;
699 					     bpp <= endbp; bpp++)
700 						bdwrite(*bpp);
701 					free(buflist, M_SEGMENT);
702 					vp->v_lastw = lbn;
703 					vp->v_lasta = bp->b_blkno;
704 					return;
705 				}
706 			}
707 		}
708 		/*
709 		 * Consider beginning a cluster. If at end of file, make
710 		 * cluster as large as possible, otherwise find size of
711 		 * existing cluster.
712 		 */
713 		if ((vp->v_type == VREG) &&
714 			((u_quad_t) bp->b_offset + lblocksize) != filesize &&
715 		    (bp->b_blkno == bp->b_lblkno) &&
716 		    (VOP_BMAP(vp, lbn, NULL, &bp->b_blkno, &maxclen, NULL) ||
717 		     bp->b_blkno == -1)) {
718 			bawrite(bp);
719 			vp->v_clen = 0;
720 			vp->v_lasta = bp->b_blkno;
721 			vp->v_cstart = lbn + 1;
722 			vp->v_lastw = lbn;
723 			return;
724 		}
725 		vp->v_clen = maxclen;
726 		if (!async && maxclen == 0) {	/* I/O not contiguous */
727 			vp->v_cstart = lbn + 1;
728 			bawrite(bp);
729 		} else {	/* Wait for rest of cluster */
730 			vp->v_cstart = lbn;
731 			bdwrite(bp);
732 		}
733 	} else if (lbn == vp->v_cstart + vp->v_clen) {
734 		/*
735 		 * At end of cluster, write it out if seqcount tells us we
736 		 * are operating sequentially, otherwise let the buf or
737 		 * update daemon handle it.
738 		 */
739 		bdwrite(bp);
740 		if (seqcount > 1)
741 			cluster_wbuild_wb(vp, lblocksize, vp->v_cstart, vp->v_clen + 1);
742 		vp->v_clen = 0;
743 		vp->v_cstart = lbn + 1;
744 	} else if (vm_page_count_severe()) {
745 		/*
746 		 * We are low on memory, get it going NOW
747 		 */
748 		bawrite(bp);
749 	} else {
750 		/*
751 		 * In the middle of a cluster, so just delay the I/O for now.
752 		 */
753 		bdwrite(bp);
754 	}
755 	vp->v_lastw = lbn;
756 	vp->v_lasta = bp->b_blkno;
757 }
758 
759 
760 /*
761  * This is an awful lot like cluster_rbuild...wish they could be combined.
762  * The last lbn argument is the current block on which I/O is being
763  * performed.  Check to see that it doesn't fall in the middle of
764  * the current block (if last_bp == NULL).
765  */
766 int
767 cluster_wbuild(vp, size, start_lbn, len)
768 	struct vnode *vp;
769 	long size;
770 	daddr_t start_lbn;
771 	int len;
772 {
773 	struct buf *bp, *tbp;
774 	int i, j, s;
775 	int totalwritten = 0;
776 	int dbsize = btodb(size);
777 
778 	GIANT_REQUIRED;
779 
780 	while (len > 0) {
781 		s = splbio();
782 		/*
783 		 * If the buffer is not delayed-write (i.e. dirty), or it
784 		 * is delayed-write but either locked or inval, it cannot
785 		 * partake in the clustered write.
786 		 */
787 		if (((tbp = gbincore(vp, start_lbn)) == NULL) ||
788 		  ((tbp->b_flags & (B_LOCKED | B_INVAL | B_DELWRI)) != B_DELWRI) ||
789 		  BUF_LOCK(tbp, LK_EXCLUSIVE | LK_NOWAIT)) {
790 			++start_lbn;
791 			--len;
792 			splx(s);
793 			continue;
794 		}
795 		bremfree(tbp);
796 		tbp->b_flags &= ~B_DONE;
797 		splx(s);
798 
799 		/*
800 		 * Extra memory in the buffer, punt on this buffer.
801 		 * XXX we could handle this in most cases, but we would
802 		 * have to push the extra memory down to after our max
803 		 * possible cluster size and then potentially pull it back
804 		 * up if the cluster was terminated prematurely--too much
805 		 * hassle.
806 		 */
807 		if (((tbp->b_flags & (B_CLUSTEROK | B_MALLOC | B_VMIO)) !=
808 		     (B_CLUSTEROK | B_VMIO)) ||
809 		  (tbp->b_bcount != tbp->b_bufsize) ||
810 		  (tbp->b_bcount != size) ||
811 		  (len == 1) ||
812 		  ((bp = getpbuf(&cluster_pbuf_freecnt)) == NULL)) {
813 			totalwritten += tbp->b_bufsize;
814 			bawrite(tbp);
815 			++start_lbn;
816 			--len;
817 			continue;
818 		}
819 
820 		/*
821 		 * We got a pbuf to make the cluster in.
822 		 * so initialise it.
823 		 */
824 		TAILQ_INIT(&bp->b_cluster.cluster_head);
825 		bp->b_bcount = 0;
826 		bp->b_magic = tbp->b_magic;
827 		bp->b_op = tbp->b_op;
828 		bp->b_bufsize = 0;
829 		bp->b_npages = 0;
830 		if (tbp->b_wcred != NOCRED)
831 			bp->b_wcred = crhold(tbp->b_wcred);
832 
833 		bp->b_blkno = tbp->b_blkno;
834 		bp->b_lblkno = tbp->b_lblkno;
835 		bp->b_offset = tbp->b_offset;
836 
837 		/*
838 		 * We are synthesizing a buffer out of vm_page_t's, but
839 		 * if the block size is not page aligned then the starting
840 		 * address may not be either.  Inherit the b_data offset
841 		 * from the original buffer.
842 		 */
843 		bp->b_data = (char *)((vm_offset_t)bp->b_data |
844 		    ((vm_offset_t)tbp->b_data & PAGE_MASK));
845 		bp->b_flags |= B_CLUSTER |
846 				(tbp->b_flags & (B_VMIO | B_NEEDCOMMIT | B_NOWDRAIN));
847 		bp->b_iodone = cluster_callback;
848 		pbgetvp(vp, bp);
849 		/*
850 		 * From this location in the file, scan forward to see
851 		 * if there are buffers with adjacent data that need to
852 		 * be written as well.
853 		 */
854 		for (i = 0; i < len; ++i, ++start_lbn) {
855 			if (i != 0) { /* If not the first buffer */
856 				s = splbio();
857 				/*
858 				 * If the adjacent data is not even in core it
859 				 * can't need to be written.
860 				 */
861 				if ((tbp = gbincore(vp, start_lbn)) == NULL) {
862 					splx(s);
863 					break;
864 				}
865 
866 				/*
867 				 * If it IS in core, but has different
868 				 * characteristics, or is locked (which
869 				 * means it could be undergoing a background
870 				 * I/O or be in a weird state), then don't
871 				 * cluster with it.
872 				 */
873 				if ((tbp->b_flags & (B_VMIO | B_CLUSTEROK |
874 				    B_INVAL | B_DELWRI | B_NEEDCOMMIT))
875 				  != (B_DELWRI | B_CLUSTEROK |
876 				    (bp->b_flags & (B_VMIO | B_NEEDCOMMIT))) ||
877 				    (tbp->b_flags & B_LOCKED) ||
878 				    tbp->b_wcred != bp->b_wcred ||
879 				    BUF_LOCK(tbp, LK_EXCLUSIVE | LK_NOWAIT)) {
880 					splx(s);
881 					break;
882 				}
883 
884 				/*
885 				 * Check that the combined cluster
886 				 * would make sense with regard to pages
887 				 * and would not be too large
888 				 */
889 				if ((tbp->b_bcount != size) ||
890 				  ((bp->b_blkno + (dbsize * i)) !=
891 				    tbp->b_blkno) ||
892 				  ((tbp->b_npages + bp->b_npages) >
893 				    (vp->v_mount->mnt_iosize_max / PAGE_SIZE))) {
894 					BUF_UNLOCK(tbp);
895 					splx(s);
896 					break;
897 				}
898 				/*
899 				 * Ok, it's passed all the tests,
900 				 * so remove it from the free list
901 				 * and mark it busy. We will use it.
902 				 */
903 				bremfree(tbp);
904 				tbp->b_flags &= ~B_DONE;
905 				splx(s);
906 			} /* end of code for non-first buffers only */
907 			/* check for latent dependencies to be handled */
908 			if ((LIST_FIRST(&tbp->b_dep)) != NULL)
909 				buf_start(tbp);
910 			/*
911 			 * If the IO is via the VM then we do some
912 			 * special VM hackery (yuck).  Since the buffer's
913 			 * block size may not be page-aligned it is possible
914 			 * for a page to be shared between two buffers.  We
915 			 * have to get rid of the duplication when building
916 			 * the cluster.
917 			 */
918 			if (tbp->b_flags & B_VMIO) {
919 				vm_page_t m;
920 
921 				if (i != 0) { /* if not first buffer */
922 					for (j = 0; j < tbp->b_npages; j += 1) {
923 						m = tbp->b_pages[j];
924 						if (m->flags & PG_BUSY) {
925 							bqrelse(tbp);
926 							goto finishcluster;
927 						}
928 					}
929 				}
930 
931 				for (j = 0; j < tbp->b_npages; j += 1) {
932 					m = tbp->b_pages[j];
933 					vm_page_io_start(m);
934 					vm_object_pip_add(m->object, 1);
935 					if ((bp->b_npages == 0) ||
936 					  (bp->b_pages[bp->b_npages - 1] != m)) {
937 						bp->b_pages[bp->b_npages] = m;
938 						bp->b_npages++;
939 					}
940 				}
941 			}
942 			bp->b_bcount += size;
943 			bp->b_bufsize += size;
944 
945 			s = splbio();
946 			bundirty(tbp);
947 			tbp->b_flags &= ~B_DONE;
948 			tbp->b_ioflags &= ~BIO_ERROR;
949 			tbp->b_flags |= B_ASYNC;
950 			tbp->b_iocmd = BIO_WRITE;
951 			reassignbuf(tbp, tbp->b_vp);	/* put on clean list */
952 			++tbp->b_vp->v_numoutput;
953 			splx(s);
954 			BUF_KERNPROC(tbp);
955 			TAILQ_INSERT_TAIL(&bp->b_cluster.cluster_head,
956 				tbp, b_cluster.cluster_entry);
957 		}
958 	finishcluster:
959 		pmap_qenter(trunc_page((vm_offset_t) bp->b_data),
960 			(vm_page_t *) bp->b_pages, bp->b_npages);
961 		if (bp->b_bufsize > bp->b_kvasize)
962 			panic(
963 			    "cluster_wbuild: b_bufsize(%ld) > b_kvasize(%d)\n",
964 			    bp->b_bufsize, bp->b_kvasize);
965 		bp->b_kvasize = bp->b_bufsize;
966 		totalwritten += bp->b_bufsize;
967 		bp->b_dirtyoff = 0;
968 		bp->b_dirtyend = bp->b_bufsize;
969 		bawrite(bp);
970 
971 		len -= i;
972 	}
973 	return totalwritten;
974 }
975 
976 /*
977  * Collect together all the buffers in a cluster.
978  * Plus add one additional buffer.
979  */
980 static struct cluster_save *
981 cluster_collectbufs(vp, last_bp)
982 	struct vnode *vp;
983 	struct buf *last_bp;
984 {
985 	struct cluster_save *buflist;
986 	struct buf *bp;
987 	daddr_t lbn;
988 	int i, len;
989 
990 	len = vp->v_lastw - vp->v_cstart + 1;
991 	buflist = malloc(sizeof(struct buf *) * (len + 1) + sizeof(*buflist),
992 	    M_SEGMENT, M_WAITOK);
993 	buflist->bs_nchildren = 0;
994 	buflist->bs_children = (struct buf **) (buflist + 1);
995 	for (lbn = vp->v_cstart, i = 0; i < len; lbn++, i++) {
996 		(void) bread(vp, lbn, last_bp->b_bcount, NOCRED, &bp);
997 		buflist->bs_children[i] = bp;
998 		if (bp->b_blkno == bp->b_lblkno)
999 			VOP_BMAP(bp->b_vp, bp->b_lblkno, NULL, &bp->b_blkno,
1000 				NULL, NULL);
1001 	}
1002 	buflist->bs_children[i] = bp = last_bp;
1003 	if (bp->b_blkno == bp->b_lblkno)
1004 		VOP_BMAP(bp->b_vp, bp->b_lblkno, NULL, &bp->b_blkno,
1005 			NULL, NULL);
1006 	buflist->bs_nchildren = i + 1;
1007 	return (buflist);
1008 }
1009