/*-
 * Copyright (c) 1997, 1998, 1999
 *  Nan Yang Computer Services Limited.  All rights reserved.
 *
 *  Parts copyright (c) 1997, 1998 Cybernet Corporation, NetMAX project.
 *
 *  Written by Greg Lehey
 *
 *  This software is distributed under the so-called ``Berkeley
 *  License'':
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by Nan Yang Computer
 *      Services Limited.
 * 4. Neither the name of the Company nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * This software is provided ``as is'', and any express or implied
 * warranties, including, but not limited to, the implied warranties of
 * merchantability and fitness for a particular purpose are disclaimed.
 * In no event shall the company or contributors be liable for any
 * direct, indirect, incidental, special, exemplary, or consequential
 * damages (including, but not limited to, procurement of substitute
 * goods or services; loss of use, data, or profits; or business
 * interruption) however caused and on any theory of liability, whether
 * in contract, strict liability, or tort (including negligence or
 * otherwise) arising in any way out of the use of this software, even if
 * advised of the possibility of such damage.
 *
 * $Id: vinumrequest.c,v 1.30 2001/01/09 04:20:55 grog Exp grog $
 * $FreeBSD: src/sys/dev/vinum/vinumrequest.c,v 1.44.2.5 2002/08/28 04:30:56 grog Exp $
 */

#include "vinumhdr.h"
#include "request.h"
#include <sys/resourcevar.h>

enum requeststatus bre(struct request *rq,
    int plexno,
    vinum_off_t * diskstart,
    vinum_off_t diskend);
enum requeststatus bre5(struct request *rq,
    int plexno,
    vinum_off_t * diskstart,
    vinum_off_t diskend);
enum requeststatus build_read_request(struct request *rq, int volplexno);
enum requeststatus build_write_request(struct request *rq);
enum requeststatus build_rq_buffer(struct rqelement *rqe, struct plex *plex);
int find_alternate_sd(struct request *rq);
int check_range_covered(struct request *);
void complete_rqe(struct bio *bio);
void complete_raid5_write(struct rqelement *);
int abortrequest(struct request *rq, int error);
void sdio_done(struct bio *bio);
struct bio *vinum_bounds_check(struct bio *bio, struct volume *vol);
caddr_t allocdatabuf(struct rqelement *rqe);
void freedatabuf(struct rqelement *rqe);

#ifdef VINUMDEBUG
struct rqinfo rqinfo[RQINFO_SIZE];
struct rqinfo *rqip = rqinfo;

void
logrq(enum rqinfo_type type, union rqinfou info, struct bio *ubio)
{
    cdev_t dev;

    crit_enter();

    microtime(&rqip->timestamp);			    /* when did this happen? */
    rqip->type = type;
    rqip->bio = ubio;					    /* user buffer */

    switch (type) {
    case loginfo_user_bp:
    case loginfo_user_bpl:
    case loginfo_sdio:					    /* subdisk I/O */
    case loginfo_sdiol:					    /* subdisk I/O launch */
    case loginfo_sdiodone:				    /* subdisk I/O complete */
	bcopy(info.bio, &rqip->info.bio, sizeof(struct bio));
	dev = info.bio->bio_driver_info;
	rqip->devmajor = major(dev);
	rqip->devminor = minor(dev);
	break;

    case loginfo_iodone:
    case loginfo_rqe:
    case loginfo_raid5_data:
    case loginfo_raid5_parity:
	bcopy(info.rqe, &rqip->info.rqe, sizeof(struct rqelement));
	dev = info.rqe->b.b_bio1.bio_driver_info;
	rqip->devmajor = major(dev);
	rqip->devminor = minor(dev);
	break;

    case loginfo_lockwait:
    case loginfo_lock:
    case loginfo_unlock:
	bcopy(info.lockinfo, &rqip->info.lockinfo, sizeof(struct rangelock));

	break;

    case loginfo_unused:
	break;
    }
    rqip++;
    if (rqip >= &rqinfo[RQINFO_SIZE])			    /* wrap around */
	rqip = rqinfo;
    crit_exit();
}

#endif

int
vinumstrategy(struct dev_strategy_args *ap)
{
    cdev_t dev = ap->a_head.a_dev;
    struct bio *bio = ap->a_bio;
    struct buf *bp = bio->bio_buf;
    struct bio *nbio = bio;
    struct volume *vol = NULL;
    int volno;

    switch (DEVTYPE(dev)) {
    case VINUM_SD_TYPE:
    case VINUM_RAWSD_TYPE:
	bio->bio_driver_info = dev;
	sdio(bio);
	break;
    case VINUM_DRIVE_TYPE:
    default:
	/*
	 * In fact, vinum doesn't handle drives: they're
	 * handled directly by the disk drivers
	 */
	bp->b_error = EIO;				    /* I/O error */
	bp->b_flags |= B_ERROR;
	biodone(bio);
	break;

    case VINUM_VOLUME_TYPE:				    /* volume I/O */
	volno = Volno(dev);
	vol = &VOL[volno];
	if (vol->state != volume_up) {			    /* can't access this volume */
	    bp->b_error = EIO;				    /* I/O error */
	    bp->b_flags |= B_ERROR;
	    biodone(bio);
	    break;
	}
	nbio = vinum_bounds_check(bio, vol);
	if (nbio == NULL) {
	    biodone(bio);
	    break;
	}
	/* FALLTHROUGH */
    case VINUM_PLEX_TYPE:
    case VINUM_RAWPLEX_TYPE:
	/*
	 * Plex I/O is pretty much the same as volume I/O
	 * for a single plex.  Indicate this by passing a NULL
	 * pointer (set above) for the volume
	 */
	bp->b_resid = bp->b_bcount;			    /* transfer everything */
	vinumstart(dev, nbio, 0);
	break;
    }
    return(0);
}

/*
 * Start a transfer.  Return -1 on error,
 * 0 if OK, 1 if we need to retry.
 * Parameter reviveok is set when doing
 * transfers for revives: it allows transfers to
 * be started immediately when a revive is in
 * progress.  During revive, normal transfers
 * are queued if they share address space with
 * a currently active revive operation.
 */
int
vinumstart(cdev_t dev, struct bio *bio, int reviveok)
{
    struct buf *bp = bio->bio_buf;
    int plexno;
    struct volume *vol;
    struct request *rq;					    /* build up our request here */
    enum requeststatus status;

    bio->bio_driver_info = dev;

#ifdef VINUMDEBUG
    if (debug & DEBUG_LASTREQS)
	logrq(loginfo_user_bp, (union rqinfou) bio, bio);
#endif

    if ((bp->b_bcount % DEV_BSIZE) != 0) {		    /* bad length */
	bp->b_error = EINVAL;				    /* invalid size */
	bp->b_flags |= B_ERROR;
	biodone(bio);
	return -1;
    }
    rq = (struct request *) Malloc(sizeof(struct request)); /* allocate a request struct */
    if (rq == NULL) {					    /* can't do it */
	bp->b_error = ENOMEM;				    /* can't get memory */
	bp->b_flags |= B_ERROR;
	biodone(bio);
	return -1;
    }
    bzero(rq, sizeof(struct request));

    /*
     * Note the volume ID.  This can be NULL, which
     * the request building functions use as an
     * indication for single plex I/O
     */
    rq->bio = bio;					    /* and the user buffer struct */

    if (DEVTYPE(dev) == VINUM_VOLUME_TYPE) {	    /* it's a volume, */
	rq->volplex.volno = Volno(dev);		    /* get the volume number */
	vol = &VOL[rq->volplex.volno];			    /* and point to it */
	vol->active++;					    /* one more active request */
    } else {
	vol = NULL;					    /* no volume */
	rq->volplex.plexno = Plexno(dev);		    /* point to the plex */
	rq->isplex = 1;					    /* note that it's a plex */
    }

    if (bp->b_cmd == BUF_CMD_READ) {
	/*
	 * This is a read request.  Decide
	 * which plex to read from.
	 *
	 * There's a potential race condition here,
	 * since we're not locked, and we could end
	 * up multiply incrementing the round-robin
	 * counter.  This doesn't have any serious
	 * effects, however.
	 */
	if (vol != NULL) {
	    plexno = vol->preferred_plex;		    /* get the plex to use */
	    if (plexno < 0) {				    /* round robin */
		plexno = vol->last_plex_read;
		vol->last_plex_read++;
		if (vol->last_plex_read >= vol->plexes)	    /* got the the end? */
		    vol->last_plex_read = 0;		    /* wrap around */
	    }
	    status = build_read_request(rq, plexno);	    /* build a request */
	} else {
	    vinum_off_t diskaddr = (vinum_off_t)(bio->bio_offset >> DEV_BSHIFT);
							    /* start offset of transfer */
	    status = bre(rq,				    /* build a request list */
		rq->volplex.plexno,
		&diskaddr,
		diskaddr + (bp->b_bcount / DEV_BSIZE));
	}

	if (status > REQUEST_RECOVERED) {		    /* can't satisfy it */
	    if (status == REQUEST_DOWN) {		    /* not enough subdisks */
		bp->b_error = EIO;			    /* I/O error */
		bp->b_flags |= B_ERROR;
	    }
	    biodone(bio);
	    freerq(rq);
	    return -1;
	}
	return launch_requests(rq, reviveok);		    /* now start the requests if we can */
    } else
	/*
	 * This is a write operation.  We write to all plexes.  If this is
	 * a RAID-4 or RAID-5 plex, we must also update the parity stripe.
	 */
    {
	if (vol != NULL)
	    status = build_write_request(rq);		    /* Not all the subdisks are up */
	else {						    /* plex I/O */
	    vinum_off_t diskstart;
	    vinum_off_t diskend;

	    diskstart = (vinum_off_t)(bio->bio_offset >> DEV_BSHIFT); /* start offset of transfer */
	    diskend = diskstart + bp->b_bcount / DEV_BSIZE;
	    status = bre(rq, Plexno(dev),
		&diskstart, diskend);  /* build requests for the plex */
	}
	if (status > REQUEST_RECOVERED) {		    /* can't satisfy it */
	    if (status == REQUEST_DOWN) {		    /* not enough subdisks */
		bp->b_error = EIO;			    /* I/O error */
		bp->b_flags |= B_ERROR;
	    }
	    biodone(bio);
	    freerq(rq);
	    return -1;
	}
	return launch_requests(rq, reviveok);		    /* now start the requests if we can */
    }
}

/*
 * Call the low-level strategy routines to
 * perform the requests in a struct request
 */
int
launch_requests(struct request *rq, int reviveok)
{
    struct rqgroup *rqg;
    int rqno;						    /* loop index */
    struct rqelement *rqe;				    /* current element */
    struct drive *drive;
    int rcount;						    /* request count */

    /*
     * First find out whether we're reviving, and the
     * request contains a conflict.  If so, we hang
     * the request off plex->waitlist of the first
     * plex we find which is reviving
     */

    if ((rq->flags & XFR_REVIVECONFLICT)		    /* possible revive conflict */
    &&(!reviveok)) {					    /* and we don't want to do it now, */
	struct sd *sd;
	struct request *waitlist;			    /* point to the waitlist */

	sd = &SD[rq->sdno];
	if (sd->waitlist != NULL) {			    /* something there already, */
	    waitlist = sd->waitlist;
	    while (waitlist->next != NULL)		    /* find the end */
		waitlist = waitlist->next;
	    waitlist->next = rq;			    /* hook our request there */
	} else
	    sd->waitlist = rq;				    /* hook our request at the front */

#ifdef VINUMDEBUG
	if (debug & DEBUG_REVIVECONFLICT) {
	    log(LOG_DEBUG,
		"Revive conflict sd %d: %p\n%s dev %d.%d, offset 0x%jx, length %d\n",
		rq->sdno,
		rq,
		(rq->bio->bio_buf->b_cmd & BUF_CMD_READ) ? "Read" : "Write",
		major(((cdev_t)rq->bio->bio_driver_info)),
		minor(((cdev_t)rq->bio->bio_driver_info)),
		(uintmax_t)rq->bio->bio_offset,
		rq->bio->bio_buf->b_bcount);
	}
#endif
	return 0;					    /* and get out of here */
    }
    rq->active = 0;					    /* nothing yet */
#ifdef VINUMDEBUG
    if (debug & DEBUG_ADDRESSES)
	log(LOG_DEBUG,
	    "Request: %p\n%s dev %d.%d, offset 0x%jx, length %d\n",
	    rq,
	    (rq->bio->bio_buf->b_cmd == BUF_CMD_READ) ? "Read" : "Write",
	    major(((cdev_t)rq->bio->bio_driver_info)),
	    minor(((cdev_t)rq->bio->bio_driver_info)),
	    (uintmax_t)rq->bio->bio_offset,
	    rq->bio->bio_buf->b_bcount);
    vinum_conf.lastrq = rq;
    vinum_conf.lastbio = rq->bio;
    if (debug & DEBUG_LASTREQS)
	logrq(loginfo_user_bpl, (union rqinfou) rq->bio, rq->bio);
#endif

    /*
     * This loop happens without any participation
     * of the bottom half, so it requires no
     * protection.
     */
    for (rqg = rq->rqg; rqg != NULL; rqg = rqg->next) {	    /* through the whole request chain */
	rqg->active = rqg->count;			    /* they're all active */
	for (rqno = 0; rqno < rqg->count; rqno++) {
	    rqe = &rqg->rqe[rqno];
	    if (rqe->flags & XFR_BAD_SUBDISK)		    /* this subdisk is bad, */
		rqg->active--;				    /* one less active request */
	}
	if (rqg->active)				    /* we have at least one active request, */
	    rq->active++;				    /* one more active request group */
    }

    /*
     * Now fire off the requests.  In this loop the
     * bottom half could be completing requests
     * before we finish, so we need critical section protection.
     */
    crit_enter();
    for (rqg = rq->rqg; rqg != NULL;) {			    /* through the whole request chain */
	if (rqg->lockbase >= 0)				    /* this rqg needs a lock first */
	    rqg->lock = lockrange(rqg->lockbase, rqg->rq->bio->bio_buf, &PLEX[rqg->plexno]);
	rcount = rqg->count;
	for (rqno = 0; rqno < rcount;) {
	    cdev_t dev;

	    rqe = &rqg->rqe[rqno];

	    /*
	     * Point to next rqg before the bottom end
	     * changes the structures.
	     */
	    if (++rqno >= rcount)
		rqg = rqg->next;
	    if ((rqe->flags & XFR_BAD_SUBDISK) == 0) {	    /* this subdisk is good, */
		drive = &DRIVE[rqe->driveno];		    /* look at drive */
		drive->active++;
		if (drive->active >= drive->maxactive)
		    drive->maxactive = drive->active;
		vinum_conf.active++;
		if (vinum_conf.active >= vinum_conf.maxactive)
		    vinum_conf.maxactive = vinum_conf.active;

		dev = rqe->b.b_bio1.bio_driver_info;
#ifdef VINUMDEBUG
		if (debug & DEBUG_ADDRESSES)
		    log(LOG_DEBUG,
			"  %s dev %d.%d, sd %d, offset 0x%jx, devoffset 0x%jx, length %d\n",
			(rqe->b.b_cmd == BUF_CMD_READ) ? "Read" : "Write",
			major(dev),
			minor(dev),
			rqe->sdno,
			(uintmax_t)(rqe->b.b_bio1.bio_offset - ((off_t)SD[rqe->sdno].driveoffset << DEV_BSHIFT)),
			(uintmax_t)rqe->b.b_bio1.bio_offset,
			rqe->b.b_bcount);
		if (debug & DEBUG_LASTREQS)
		    logrq(loginfo_rqe, (union rqinfou) rqe, rq->bio);
#endif
		/* fire off the request */
		/* XXX this had better not be a low level drive */
		dev_dstrategy(dev, &rqe->b.b_bio1);
	    }
	}
    }
    crit_exit();
    return 0;
}

/*
 * define the low-level requests needed to perform a
 * high-level I/O operation for a specific plex 'plexno'.
 *
 * Return REQUEST_OK if all subdisks involved in the request are up,
 * REQUEST_DOWN if some subdisks are not up, and REQUEST_EOF if the
 * request is at least partially outside the bounds of the subdisks.
 *
 * Modify the pointer *diskstart to point to the end address.  On
 * read, return on the first bad subdisk, so that the caller
 * (build_read_request) can try alternatives.
 *
 * On entry to this routine, the rqg structures are not assigned.  The
 * assignment is performed by expandrq().  Strictly speaking, the
 * elements rqe->sdno of all entries should be set to -1, since 0
 * (from bzero) is a valid subdisk number.  We avoid this problem by
 * initializing the ones we use, and not looking at the others (index
 * >= rqg->requests).
 */
enum requeststatus
bre(struct request *rq,
    int plexno,
    vinum_off_t * diskaddr,
    vinum_off_t diskend)
{
    int sdno;
    struct sd *sd;
    struct rqgroup *rqg;
    struct bio *bio;
    struct buf *bp;					    /* user's bp */
    struct plex *plex;
    enum requeststatus status;				    /* return value */
    vinum_off_t plexoffset;					    /* offset of transfer in plex */
    vinum_off_t stripebase;					    /* base address of stripe (1st subdisk) */
    vinum_off_t stripeoffset;				    /* offset in stripe */
    vinum_off_t blockoffset;				    /* offset in stripe on subdisk */
    struct rqelement *rqe;				    /* point to this request information */
    vinum_off_t diskstart = *diskaddr;			    /* remember where this transfer starts */
    enum requeststatus s;				    /* temp return value */

    bio = rq->bio;					    /* buffer pointer */
    bp = bio->bio_buf;
    status = REQUEST_OK;				    /* return value: OK until proven otherwise */
    plex = &PLEX[plexno];				    /* point to the plex */

    switch (plex->organization) {
    case plex_concat:
	sd = NULL;					    /* (keep compiler quiet) */
	for (sdno = 0; sdno < plex->subdisks; sdno++) {
	    sd = &SD[plex->sdnos[sdno]];
	    if (*diskaddr < sd->plexoffset)		    /* we must have a hole, */
		status = REQUEST_DEGRADED;		    /* note the fact */
	    if (*diskaddr < (sd->plexoffset + sd->sectors)) { /* the request starts in this subdisk */
		rqg = allocrqg(rq, 1);			    /* space for the request */
		if (rqg == NULL) {			    /* malloc failed */
		    bp->b_error = ENOMEM;
		    bp->b_flags |= B_ERROR;
		    return REQUEST_ENOMEM;
		}
		rqg->plexno = plexno;

		rqe = &rqg->rqe[0];			    /* point to the element */
		rqe->rqg = rqg;				    /* group */
		rqe->sdno = sd->sdno;			    /* put in the subdisk number */
		plexoffset = *diskaddr;			    /* start offset in plex */
		rqe->sdoffset = plexoffset - sd->plexoffset; /* start offset in subdisk */
		rqe->useroffset = plexoffset - diskstart;   /* start offset in user buffer */
		rqe->dataoffset = 0;
		rqe->datalen = u64min(diskend - *diskaddr,
				      sd->sectors - rqe->sdoffset);
		rqe->groupoffset = 0;			    /* no groups for concatenated plexes */
		rqe->grouplen = 0;
		rqe->buflen = rqe->datalen;		    /* buffer length is data buffer length */
		rqe->flags = 0;
		rqe->driveno = sd->driveno;
		if (sd->state != sd_up) {		    /* *now* we find the sd is down */
		    s = checksdstate(sd, rq, *diskaddr, diskend); /* do we need to change state? */
		    if (s == REQUEST_DOWN) {		    /* down? */
			rqe->flags = XFR_BAD_SUBDISK;	    /* yup */
			if (rq->bio->bio_buf->b_cmd == BUF_CMD_READ)    /* read request, */
			    return REQUEST_DEGRADED;	    /* give up here */
			/*
			 * If we're writing, don't give up
			 * because of a bad subdisk.  Go
			 * through to the bitter end, but note
			 * which ones we can't access.
			 */
			status = REQUEST_DEGRADED;	    /* can't do it all */
		    }
		}
		*diskaddr += rqe->datalen;		    /* bump the address */
		if (build_rq_buffer(rqe, plex)) {	    /* build the buffer */
		    deallocrqg(rqg);
		    bp->b_error = ENOMEM;
		    bp->b_flags |= B_ERROR;
		    return REQUEST_ENOMEM;		    /* can't do it */
		}
	    }
	    if (*diskaddr == diskend)			    /* we're finished, */
		break;					    /* get out of here */
	}
	/*
	 * We've got to the end of the plex.  Have we got to the end of
	 * the transfer?  It would seem that having an offset beyond the
	 * end of the subdisk is an error, but in fact it can happen if
	 * the volume has another plex of different size.  There's a valid
	 * question as to why you would want to do this, but currently
	 * it's allowed.
	 *
	 * In a previous version, I returned REQUEST_DOWN here.  I think
	 * REQUEST_EOF is more appropriate now.
	 */
	if (diskend > sd->sectors + sd->plexoffset)	    /* pointing beyond EOF? */
	    status = REQUEST_EOF;
	break;

    case plex_striped:
	{
	    while (*diskaddr < diskend) {		    /* until we get it all sorted out */
		if (*diskaddr >= plex->length)		    /* beyond the end of the plex */
		    return REQUEST_EOF;			    /* can't continue */

		/* The offset of the start address from the start of the stripe. */
		stripeoffset = *diskaddr % (plex->stripesize * plex->subdisks);

		/* The plex-relative address of the start of the stripe. */
		stripebase = *diskaddr - stripeoffset;

		/* The number of the subdisk in which the start is located. */
		sdno = stripeoffset / plex->stripesize;

		/* The offset from the beginning of the stripe on this subdisk. */
		blockoffset = stripeoffset % plex->stripesize;

		sd = &SD[plex->sdnos[sdno]];		    /* the subdisk in question */
		rqg = allocrqg(rq, 1);			    /* space for the request */
		if (rqg == NULL) {			    /* malloc failed */
		    bp->b_error = ENOMEM;
		    bp->b_flags |= B_ERROR;
		    return REQUEST_ENOMEM;
		}
		rqg->plexno = plexno;

		rqe = &rqg->rqe[0];			    /* point to the element */
		rqe->rqg = rqg;
		rqe->sdoffset = stripebase / plex->subdisks + blockoffset; /* start offset in this subdisk */
		rqe->useroffset = *diskaddr - diskstart;    /* The offset of the start in the user buffer */
		rqe->dataoffset = 0;
		rqe->datalen = u64min(diskend - *diskaddr,
				      plex->stripesize - blockoffset);
		rqe->groupoffset = 0;			    /* no groups for striped plexes */
		rqe->grouplen = 0;
		rqe->buflen = rqe->datalen;		    /* buffer length is data buffer length */
		rqe->flags = 0;
		rqe->sdno = sd->sdno;			    /* put in the subdisk number */
		rqe->driveno = sd->driveno;

		if (sd->state != sd_up) {		    /* *now* we find the sd is down */
		    s = checksdstate(sd, rq, *diskaddr, diskend); /* do we need to change state? */
		    if (s == REQUEST_DOWN) {		    /* down? */
			rqe->flags = XFR_BAD_SUBDISK;	    /* yup */
			if (rq->bio->bio_buf->b_cmd == BUF_CMD_READ)	    /* read request, */
			    return REQUEST_DEGRADED;	    /* give up here */
			/*
			 * If we're writing, don't give up
			 * because of a bad subdisk.  Go through
			 * to the bitter end, but note which
			 * ones we can't access.
			 */
			status = REQUEST_DEGRADED;	    /* can't do it all */
		    }
		}
		/*
		 * It would seem that having an offset
		 * beyond the end of the subdisk is an
		 * error, but in fact it can happen if the
		 * volume has another plex of different
		 * size.  There's a valid question as to why
		 * you would want to do this, but currently
		 * it's allowed.
		 */
		if (rqe->sdoffset + rqe->datalen > sd->sectors) { /* ends beyond the end of the subdisk? */
		    rqe->datalen = sd->sectors - rqe->sdoffset;	/* truncate */
#ifdef VINUMDEBUG
		    if (debug & DEBUG_EOFINFO) {	    /* tell on the request */
			log(LOG_DEBUG,
			    "vinum: EOF on plex %s, sd %s offset %jx (user offset %jx)\n",
			    plex->name,
			    sd->name,
			    (uintmax_t)sd->sectors,
			    (uintmax_t)bp->b_bio1.bio_offset);
			log(LOG_DEBUG,
			    "vinum: stripebase 0x%llx, stripeoffset 0x%llx, "
			    "blockoffset 0x%llx\n",
			    (long long)stripebase,
			    (long long)stripeoffset,
			    (long long)blockoffset);
		    }
#endif
		}
		if (build_rq_buffer(rqe, plex)) {	    /* build the buffer */
		    deallocrqg(rqg);
		    bp->b_error = ENOMEM;
		    bp->b_flags |= B_ERROR;
		    return REQUEST_ENOMEM;		    /* can't do it */
		}
		*diskaddr += rqe->datalen;		    /* look at the remainder */
		if ((*diskaddr < diskend)		    /* didn't finish the request on this stripe */
		&&(*diskaddr < plex->length)) {		    /* and there's more to come */
		    plex->multiblock++;			    /* count another one */
		    if (sdno == plex->subdisks - 1)	    /* last subdisk, */
			plex->multistripe++;		    /* another stripe as well */
		}
	    }
	}
	break;

	/*
	 * RAID-4 and RAID-5 are complicated enough to have their own
	 * function.
	 */
    case plex_raid4:
    case plex_raid5:
	status = bre5(rq, plexno, diskaddr, diskend);
	break;

    default:
	log(LOG_ERR, "vinum: invalid plex type %d in bre\n", plex->organization);
	status = REQUEST_DOWN;				    /* can't access it */
    }

    return status;
}

/*
 * Build up a request structure for reading volumes.
 * This function is not needed for plex reads, since there's
 * no recovery if a plex read can't be satisified.
 */
enum requeststatus
build_read_request(struct request *rq,			    /* request */
    int plexindex)
{							    /* index in the volume's plex table */
    struct bio *bio;
    struct buf *bp;
    vinum_off_t startaddr;					    /* offset of previous part of transfer */
    vinum_off_t diskaddr;					    /* offset of current part of transfer */
    vinum_off_t diskend;					    /* and end offset of transfer */
    int plexno;						    /* plex index in vinum_conf */
    struct volume *vol;					    /* volume in question */
    int recovered = 0;					    /* set if we recover a read */
    enum requeststatus status = REQUEST_OK;
    int plexmask;					    /* bit mask of plexes, for recovery */

    bio = rq->bio;					    /* buffer pointer */
    bp = bio->bio_buf;
    diskaddr = bio->bio_offset >> DEV_BSHIFT;		    /* start offset of transfer */
    diskend = diskaddr + (bp->b_bcount / DEV_BSIZE);	    /* and end offset of transfer */
    vol = &VOL[rq->volplex.volno];			    /* point to volume */

    while (diskaddr < diskend) {			    /* build up request components */
	startaddr = diskaddr;
	status = bre(rq, vol->plex[plexindex], &diskaddr, diskend); /* build up a request */
	switch (status) {
	case REQUEST_OK:
	    continue;

	case REQUEST_RECOVERED:
	    /*
	     * XXX FIXME if we have more than one plex, and we can
	     * satisfy the request from another, don't use the
	     * recovered request, since it's more expensive.
	     */
	    recovered = 1;
	    break;

	case REQUEST_ENOMEM:
	    return status;
	    /*
	     * If we get here, our request is not complete.  Try
	     * to fill in the missing parts from another plex.
	     * This can happen multiple times in this function,
	     * and we reinitialize the plex mask each time, since
	     * we could have a hole in our plexes.
	     */
	case REQUEST_EOF:
	case REQUEST_DOWN:				    /* can't access the plex */
	case REQUEST_DEGRADED:				    /* can't access the plex */
	    plexmask = ((1 << vol->plexes) - 1)		    /* all plexes in the volume */
	    &~(1 << plexindex);				    /* except for the one we were looking at */
	    for (plexno = 0; plexno < vol->plexes; plexno++) {
		if (plexmask == 0)			    /* no plexes left to try */
		    return REQUEST_DOWN;		    /* failed */
		diskaddr = startaddr;			    /* start at the beginning again */
		if (plexmask & (1 << plexno)) {		    /* we haven't tried this plex yet */
		    bre(rq, vol->plex[plexno], &diskaddr, diskend); /* try a request */
		    if (diskaddr > startaddr) {		    /* we satisfied another part */
			recovered = 1;			    /* we recovered from the problem */
			status = REQUEST_OK;		    /* don't complain about it */
			break;
		    }
		}
	    }
	    if (diskaddr == startaddr)			    /* didn't get any further, */
		return status;
	}
	if (recovered)
	    vol->recovered_reads += recovered;		    /* adjust our recovery count */
    }
    return status;
}

/*
 * Build up a request structure for writes.
 * Return 0 if all subdisks involved in the request are up, 1 if some
 * subdisks are not up, and -1 if the request is at least partially
 * outside the bounds of the subdisks.
 */
enum requeststatus
build_write_request(struct request *rq)
{							    /* request */
    struct bio *bio;
    struct buf *bp;
    vinum_off_t diskstart;					    /* offset of current part of transfer */
    vinum_off_t diskend;					    /* and end offset of transfer */
    int plexno;						    /* plex index in vinum_conf */
    struct volume *vol;					    /* volume in question */
    enum requeststatus status;

    bio = rq->bio;					    /* buffer pointer */
    bp = bio->bio_buf;
    vol = &VOL[rq->volplex.volno];			    /* point to volume */
    diskend = (vinum_off_t)(bio->bio_offset >> DEV_BSHIFT) + (bp->b_bcount / DEV_BSIZE);	    /* end offset of transfer */
    status = REQUEST_DOWN;				    /* assume the worst */
    for (plexno = 0; plexno < vol->plexes; plexno++) {
	diskstart = (vinum_off_t)(bio->bio_offset >> DEV_BSHIFT);			    /* start offset of transfer */
	/*
	 * Build requests for the plex.
	 * We take the best possible result here (min,
	 * not max): we're happy if we can write at all
	 */
	status = u64min(status,
		     bre(rq, vol->plex[plexno], &diskstart, diskend));
    }
    return status;
}

/* Fill in the struct buf part of a request element. */
enum requeststatus
build_rq_buffer(struct rqelement *rqe, struct plex *plex)
{
    struct sd *sd;					    /* point to subdisk */
    struct buf *bp;
    struct buf *ubp;					    /* user (high level) buffer header */
    struct bio *ubio;

    sd = &SD[rqe->sdno];				    /* point to subdisk */
    bp = &rqe->b;
    ubio = rqe->rqg->rq->bio;				    /* pointer to user buffer header */
    ubp = ubio->bio_buf;

    /* Initialize the buf struct */
    /* copy these flags from user bp */
    bp->b_flags = ubp->b_flags & B_NOCACHE;
    bp->b_cmd = ubp->b_cmd;
#ifdef VINUMDEBUG
    if (rqe->flags & XFR_BUFLOCKED)			    /* paranoia */
	panic("build_rq_buffer: rqe already locked");	    /* XXX remove this when we're sure */
#endif
    initbufbio(bp);
    BUF_LOCK(bp, LK_EXCLUSIVE);				    /* and lock it */
    BUF_KERNPROC(bp);
    rqe->flags |= XFR_BUFLOCKED;
    bp->b_bio1.bio_done = complete_rqe;
    /*
     * You'd think that we wouldn't need to even
     * build the request buffer for a dead subdisk,
     * but in some cases we need information like
     * the user buffer address.  Err on the side of
     * generosity and supply what we can.  That
     * obviously doesn't include drive information
     * when the drive is dead.
     */
    if ((rqe->flags & XFR_BAD_SUBDISK) == 0)		    /* subdisk is accessible, */
	bp->b_bio1.bio_driver_info = DRIVE[rqe->driveno].dev; /* drive device */
    bp->b_bio1.bio_offset = (off_t)(rqe->sdoffset + sd->driveoffset) << DEV_BSHIFT;	/* start address */
    bp->b_bcount = rqe->buflen << DEV_BSHIFT;		    /* number of bytes to transfer */
    bp->b_resid = bp->b_bcount;				    /* and it's still all waiting */

    if (rqe->flags & XFR_MALLOCED) {			    /* this operation requires a malloced buffer */
	bp->b_data = Malloc(bp->b_bcount);		    /* get a buffer to put it in */
	if (bp->b_data == NULL) {			    /* failed */
	    abortrequest(rqe->rqg->rq, ENOMEM);
	    return REQUEST_ENOMEM;			    /* no memory */
	}
    } else
	/*
	 * Point directly to user buffer data.  This means
	 * that we don't need to do anything when we have
	 * finished the transfer
	 */
	bp->b_data = ubp->b_data + rqe->useroffset * DEV_BSIZE;
    /*
     * On a recovery read, we perform an XOR of
     * all blocks to the user buffer.  To make
     * this work, we first clean out the buffer
     */
    if ((rqe->flags & (XFR_RECOVERY_READ | XFR_BAD_SUBDISK))
	== (XFR_RECOVERY_READ | XFR_BAD_SUBDISK)) {	    /* bad subdisk of a recovery read */
	int length = rqe->grouplen << DEV_BSHIFT;	    /* and count involved */
	char *data = (char *) &rqe->b.b_data[rqe->groupoffset << DEV_BSHIFT]; /* destination */

	bzero(data, length);				    /* clean it out */
    }
    return 0;
}

/*
 * Abort a request: free resources and complete the
 * user request with the specified error
 */
int
abortrequest(struct request *rq, int error)
{
    struct buf *bp = rq->bio->bio_buf;			    /* user buffer */

    bp->b_error = error;
    freerq(rq);						    /* free everything we're doing */
    bp->b_flags |= B_ERROR;
    return error;					    /* and give up */
}

/*
 * Check that our transfer will cover the
 * complete address space of the user request.
 *
 * Return 1 if it can, otherwise 0
 */
int
check_range_covered(struct request *rq)
{
    return 1;
}

/* Perform I/O on a subdisk */
void
sdio(struct bio *bio)
{
    cdev_t dev;
    struct sd *sd;
    struct sdbuf *sbp;
    vinum_off_t endoffset;
    struct drive *drive;
    struct buf *bp = bio->bio_buf;

    dev = bio->bio_driver_info;

#ifdef VINUMDEBUG
    if (debug & DEBUG_LASTREQS)
	logrq(loginfo_sdio, (union rqinfou) bio, bio);
#endif
    sd = &SD[Sdno(dev)];				    /* point to the subdisk */
    drive = &DRIVE[sd->driveno];

    if (drive->state != drive_up) {
	if (sd->state >= sd_crashed) {
	    if (bp->b_cmd != BUF_CMD_READ)		    /* writing, */
		set_sd_state(sd->sdno, sd_stale, setstate_force);
	    else
		set_sd_state(sd->sdno, sd_crashed, setstate_force);
	}
	bp->b_error = EIO;
	bp->b_flags |= B_ERROR;
	biodone(bio);
	return;
    }
    /*
     * We allow access to any kind of subdisk as long as we can expect
     * to get the I/O performed.
     */
    if (sd->state < sd_empty) {				    /* nothing to talk to, */
	bp->b_error = EIO;
	bp->b_flags |= B_ERROR;
	biodone(bio);
	return;
    }
    /* Get a buffer */
    sbp = (struct sdbuf *) Malloc(sizeof(struct sdbuf));
    if (sbp == NULL) {
	bp->b_error = ENOMEM;
	bp->b_flags |= B_ERROR;
	biodone(bio);
	return;
    }
    bzero(sbp, sizeof(struct sdbuf));			    /* start with nothing */
    sbp->b.b_cmd = bp->b_cmd;
    sbp->b.b_bcount = bp->b_bcount;			    /* number of bytes to transfer */
    sbp->b.b_resid = bp->b_resid;			    /* and amount waiting */
    sbp->b.b_data = bp->b_data;				    /* data buffer */
    initbufbio(&sbp->b);
    BUF_LOCK(&sbp->b, LK_EXCLUSIVE);			    /* and lock it */
    BUF_KERNPROC(&sbp->b);
    sbp->b.b_bio1.bio_offset = bio->bio_offset + ((off_t)sd->driveoffset << DEV_BSHIFT);
    sbp->b.b_bio1.bio_done = sdio_done;			    /* come here on completion */
    sbp->b.b_bio1.bio_flags |= BIO_SYNC;
    sbp->bio = bio;					    /* note the address of the original header */
    sbp->sdno = sd->sdno;				    /* note for statistics */
    sbp->driveno = sd->driveno;
    endoffset = (vinum_off_t)(bio->bio_offset >> DEV_BSHIFT) + sbp->b.b_bcount / DEV_BSIZE;  /* final sector offset */
    if (endoffset > sd->sectors) {			    /* beyond the end */
	sbp->b.b_bcount -= (endoffset - sd->sectors) * DEV_BSIZE; /* trim */
	if (sbp->b.b_bcount <= 0) {			    /* nothing to transfer */
	    bp->b_resid = bp->b_bcount;			    /* nothing transferred */
	    biodone(bio);
	    BUF_UNLOCK(&sbp->b);
	    uninitbufbio(&sbp->b);
	    Free(sbp);
	    return;
	}
    }
#ifdef VINUMDEBUG
    if (debug & DEBUG_ADDRESSES)
	log(LOG_DEBUG,
	    "  %s dev %s, sd %d, offset 0x%jx, devoffset 0x%jx, length %d\n",
	    (sbp->b.b_cmd == BUF_CMD_READ) ? "Read" : "Write",
	    drive->devicename,
	    sbp->sdno,
	    (uintmax_t)(sbp->b.b_bio1.bio_offset - ((off_t)SD[sbp->sdno].driveoffset << DEV_BSHIFT)),
	    (uintmax_t)sbp->b.b_bio1.bio_offset,
	    sbp->b.b_bcount);
#endif
    crit_enter();
#ifdef VINUMDEBUG
    if (debug & DEBUG_LASTREQS)
	logrq(loginfo_sdiol, (union rqinfou) &sbp->b.b_bio1, &sbp->b.b_bio1);
#endif
    vn_strategy(drive->vp, &sbp->b.b_bio1);
    crit_exit();
}

/*
 * Determine the size of the transfer, and make sure it is
 * within the boundaries of the partition. Adjust transfer
 * if needed, and signal errors or early completion.
 *
 * Volumes are simpler than disk slices: they only contain
 * one component (though we call them a, b and c to make
 * system utilities happy), and they always take up the
 * complete space of the "partition".
 *
 * I'm still not happy with this: why should the label be
 * protected?  If it weren't so damned difficult to write
 * one in the first pleace (because it's protected), it wouldn't
 * be a problem.
 */
struct bio *
vinum_bounds_check(struct bio *bio, struct volume *vol)
{
    struct buf *bp = bio->bio_buf;
    struct bio *nbio;
    vinum_off_t maxsize = vol->size;				    /* size of the partition (sectors) */
    int size = (bp->b_bcount + DEV_BSIZE - 1) >> DEV_BSHIFT; /* size of this request (sectors) */
    vinum_off_t blkno = (vinum_off_t)(bio->bio_offset >> DEV_BSHIFT);

    if (size == 0)					    /* no transfer specified, */
	return 0;					    /* treat as EOF */
    /* beyond partition? */
    if (bio->bio_offset < 0				    /* negative start */
	|| blkno + size > maxsize) {		    /* or goes beyond the end of the partition */
	/* if exactly at end of disk, return an EOF */
	if (blkno == maxsize) {
	    bp->b_resid = bp->b_bcount;
	    return (NULL);
	}
	/* or truncate if part of it fits */
	size = maxsize - blkno;
	if (size <= 0) {				    /* nothing to transfer */
	    bp->b_error = EINVAL;
	    bp->b_flags |= B_ERROR;
	    return (NULL);
	}
	bp->b_bcount = size << DEV_BSHIFT;
    }
    nbio = push_bio(bio);
    nbio->bio_offset = bio->bio_offset;
    return (nbio);
}

/*
 * Allocate a request group and hook
 * it in in the list for rq
 */
struct rqgroup *
allocrqg(struct request *rq, int elements)
{
    struct rqgroup *rqg;				    /* the one we're going to allocate */
    int size = sizeof(struct rqgroup) + elements * sizeof(struct rqelement);

    rqg = (struct rqgroup *) Malloc(size);
    if (rqg != NULL) {					    /* malloc OK, */
	if (rq->rqg)					    /* we already have requests */
	    rq->lrqg->next = rqg;			    /* hang it off the end */
	else						    /* first request */
	    rq->rqg = rqg;				    /* at the start */
	rq->lrqg = rqg;					    /* this one is the last in the list */

	bzero(rqg, size);				    /* no old junk */
	rqg->rq = rq;					    /* point back to the parent request */
	rqg->count = elements;				    /* number of requests in the group */
	rqg->lockbase = -1;				    /* no lock required yet */
    }
    return rqg;
}

/*
 * Deallocate a request group out of a chain.  We do
 * this by linear search: the chain is short, this
 * almost never happens, and currently it can only
 * happen to the first member of the chain.
 */
void
deallocrqg(struct rqgroup *rqg)
{
    struct rqgroup *rqgc = rqg->rq->rqg;		    /* point to the request chain */

    if (rqg->lock)					    /* got a lock? */
	unlockrange(rqg->plexno, rqg->lock);		    /* yes, free it */
    if (rqgc == rqg)					    /* we're first in line */
	rqg->rq->rqg = rqg->next;			    /* unhook ourselves */
    else {
	while ((rqgc->next != NULL)			    /* find the group */
	&&(rqgc->next != rqg))
	    rqgc = rqgc->next;
	if (rqgc->next == NULL)
	    log(LOG_ERR,
		"vinum deallocrqg: rqg %p not found in request %p\n",
		rqg->rq,
		rqg);
	else
	    rqgc->next = rqg->next;			    /* make the chain jump over us */
    }
    Free(rqg);
}