File:  [DragonFly] / src / sys / vfs / hpfs / hpfs_alsubr.c
Revision 1.4: download - view: text, annotated - select for diffs
Thu Aug 7 21:17:41 2003 UTC (10 years, 11 months ago) by dillon
Branches: MAIN
CVS tags: HEAD
kernel tree reorganization stage 1: Major cvs repository work (not logged as
commits) plus a major reworking of the #include's to accomodate the
relocations.

    * CVS repository files manually moved.  Old directories left intact
      and empty (temporary).

    * Reorganize all filesystems into vfs/, most devices into dev/,
      sub-divide devices by function.

    * Begin to move device-specific architecture files to the device
      subdirs rather then throwing them all into, e.g. i386/include

    * Reorganize files related to system busses, placing the related code
      in a new bus/ directory.  Also move cam to bus/cam though this may
      not have been the best idea in retrospect.

    * Reorganize emulation code and place it in a new emulation/ directory.

    * Remove the -I- compiler option in order to allow #include file
      localization, rename all config generated X.h files to use_X.h to
      clean up the conflicts.

    * Remove /usr/src/include (or /usr/include) dependancies during the
      kernel build, beyond what is normally needed to compile helper
      programs.

    * Make config create 'machine' softlinks for architecture specific
      directories outside of the standard <arch>/include.

    * Bump the config rev.

    WARNING! after this commit /usr/include and /usr/src/sys/compile/*
    should be regenerated from scratch.

    1: /*-
    2:  * Copyright (c) 1998, 1999 Semen Ustimenko (semenu@FreeBSD.org)
    3:  * All rights reserved.
    4:  *
    5:  * Redistribution and use in source and binary forms, with or without
    6:  * modification, are permitted provided that the following conditions
    7:  * are met:
    8:  * 1. Redistributions of source code must retain the above copyright
    9:  *    notice, this list of conditions and the following disclaimer.
   10:  * 2. Redistributions in binary form must reproduce the above copyright
   11:  *    notice, this list of conditions and the following disclaimer in the
   12:  *    documentation and/or other materials provided with the distribution.
   13:  *
   14:  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   15:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   16:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   17:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   18:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   19:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   20:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   21:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   22:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   23:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   24:  * SUCH DAMAGE.
   25:  *
   26:  * $FreeBSD: src/sys/fs/hpfs/hpfs_alsubr.c,v 1.1 1999/12/09 19:09:58 semenu Exp $
   27:  * $DragonFly: src/sys/vfs/hpfs/hpfs_alsubr.c,v 1.4 2003/08/07 21:17:41 dillon Exp $
   28:  */
   29: 
   30: #include <sys/param.h>
   31: #include <sys/systm.h>
   32: #include <sys/kernel.h>
   33: #include <sys/proc.h>
   34: #include <sys/time.h>
   35: #include <sys/types.h>
   36: #include <sys/stat.h>
   37: #include <sys/vnode.h>
   38: #include <sys/mount.h>
   39: #include <sys/namei.h>
   40: #include <sys/malloc.h>
   41: #include <sys/buf.h>
   42: 
   43: #include "hpfs.h"
   44: #include "hpfs_subr.h"
   45: 
   46: #define	AE_DONE		0		/* Nothing to change */
   47: #define	AE_SPLIT	2		/* Split was done, ranp is valid */
   48: 
   49: int		hpfs_addextentr (struct hpfsmount *, lsn_t, alleaf_t *,
   50: 			         alnode_t *, u_long *);
   51: int		hpfs_allocalsec (struct hpfsmount *, lsn_t, struct buf **);
   52: int		hpfs_alblk2alsec (struct hpfsmount *, alblk_t *, alsec_t **,
   53: 				  struct buf **);
   54: int		hpfs_splitalsec (struct hpfsmount *, alsec_t *, alsec_t **,
   55: 				 struct buf **);
   56: int		hpfs_concatalsec (struct hpfsmount *, alsec_t *, alsec_t *,
   57: 				  alnode_t *);
   58: 
   59: /*
   60:  * Map file offset to disk offset. hpfsnode have to be locked.
   61:  */
   62: int
   63: hpfs_hpbmap(hp, bn, bnp, runp)
   64: 	struct hpfsnode *hp;
   65: 	daddr_t  bn;
   66: 	daddr_t *bnp;
   67: 	int *runp;
   68: {
   69: 	struct buf *bp;
   70: 	alblk_t * abp;
   71: 	alleaf_t *alp;
   72: 	alnode_t *anp;
   73: 	int error, i;
   74: 
   75: 	dprintf(("hpfs_hpbmap(0x%x, 0x%x): ",hp->h_no, bn));
   76: 
   77: 	bp = NULL;
   78: 	abp = &hp->h_fn.fn_ab;
   79: 	alp = (alleaf_t *)&hp->h_fn.fn_abd;
   80: 	anp = (alnode_t *)&hp->h_fn.fn_abd;
   81: 
   82: dive:
   83: 	if (abp->ab_flag & AB_NODES) {
   84: 		for (i=0; i<abp->ab_busycnt; i++, anp++) {
   85: 			dprintf(("[0x%x,0x%x] ",anp->an_nextoff,anp->an_lsn));
   86: 			if (bn < anp->an_nextoff) {
   87: 				alsec_t *asp;
   88: 
   89: 				dprintf(("< found | "));
   90: 
   91: 				if (bp)
   92: 					brelse(bp);
   93: 				error = bread(hp->h_devvp, anp->an_lsn, 
   94: 					      DEV_BSIZE, &bp);
   95: 				if (error) {
   96: 					printf("hpfs_hpbmap: bread error\n");
   97: 					brelse(bp);
   98: 					return (error);
   99: 				}
  100: 
  101: 				asp = (alsec_t *) bp->b_data;
  102: 				if (asp->as_magic != AS_MAGIC) {
  103: 					brelse(bp);
  104: 					printf("hpfs_hpbmap: "
  105: 					       "MAGIC DOESN'T MATCH");
  106: 					return (EINVAL);
  107: 				}
  108: 
  109: 				abp = &asp->as_ab;
  110: 				alp = (alleaf_t *)&asp->as_abd;
  111: 				anp = (alnode_t *)&asp->as_abd;
  112: 
  113: 				goto dive;
  114: 			}
  115: 		}
  116: 	} else {
  117: 		for (i=0; i<abp->ab_busycnt; i++, alp++) {
  118: 			dprintf(("[0x%x,0x%x,0x%x] ",
  119: 				 alp->al_off,alp->al_len,alp->al_lsn));
  120: 
  121: 			if ((bn >= alp->al_off) &&
  122: 			    (!alp->al_len || (bn < alp->al_off + alp->al_len))) {
  123: 				dprintf(("found, "));
  124: 
  125: 				*bnp = bn - alp->al_off + alp->al_lsn;
  126: 
  127: 				dprintf((" 0x%x ", *bnp));
  128: 
  129: 				if (runp != NULL) {
  130: 					if (alp->al_len)
  131: 						*runp = alp->al_off - 1 +
  132: 							alp->al_len - bn;
  133: 					else
  134: 						*runp = 3; /* XXX */
  135: 
  136: 					dprintf((" 0x%x cont", *runp));
  137: 				}
  138: 
  139: 				if (bp)
  140: 					brelse(bp);
  141: 
  142: 				dprintf(("\n"));
  143: 				return (0);
  144: 			}
  145: 		}
  146: 	}
  147: 
  148: 	dprintf(("END, notfound\n"));
  149: 	if (bp)
  150: 		brelse(bp);
  151: 
  152: 	dprintf(("hpfs_hpbmap: offset too big\n"));
  153: 
  154: 	return (EFBIG);
  155: }
  156: 
  157: /*
  158:  * Find place and preinitialize AlSec structure
  159:  * AlBlk is initialized to contain AlLeafs.
  160:  */
  161: int
  162: hpfs_allocalsec (
  163: 	struct hpfsmount *hpmp,
  164: 	lsn_t parlsn,
  165: 	struct buf **bpp)
  166: {
  167: 	alsec_t * asp;
  168: 	struct buf * bp;
  169: 	lsn_t lsn;
  170: 	int error;
  171: 
  172: 	*bpp = NULL;
  173: 
  174: 	error = hpfs_bmfblookup(hpmp, &lsn);
  175: 	if (error) {
  176: 		printf("hpfs_allocalsec: CAN'T ALLOC SPACE FOR AlSec\n");
  177: 		return (error);
  178: 	}
  179: 
  180: 	error = hpfs_bmmarkbusy(hpmp, lsn, 1);
  181: 	if (error) 
  182: 		return (error);
  183: 
  184: 	bp = getblk(hpmp->hpm_devvp, lsn, DEV_BSIZE, 0, 0);
  185: 	clrbuf(bp);
  186: 
  187: 	/* Fill AlSec info */
  188: 	asp = (alsec_t *) bp->b_data;
  189: 	asp->as_magic = AS_MAGIC;
  190: 	asp->as_self = lsn;
  191: 	asp->as_parent = parlsn;
  192: 
  193: 	/* Fill AlBlk */
  194: 	asp->as_ab.ab_flag = 0;
  195: 	asp->as_ab.ab_busycnt = 0;
  196: 	asp->as_ab.ab_freecnt = 0x28;
  197: 	asp->as_ab.ab_freeoff = sizeof(alblk_t);
  198: 
  199: 	*bpp = bp;
  200: 
  201: 	return (0);
  202: }
  203: 
  204: /*
  205:  * Split AlSec structure into new allocated:
  206:  * allocate new AlSec; then move second half of asp's entries in
  207:  * into it; set proper flags.
  208:  *
  209:  * IF AlSec CONTAINS AlNodes, THEN YOU ALMOST EVERYTIME HAVE TO
  210:  * FIX LAST AlNode in OLD AlSec (NEXTOFF TO BE 0xFFFFFFFF).
  211:  * TOGETHER WITH FIXING ALL CHILDREN'S AlSecs (THEY HAVE GOT NEW PARENT).
  212:  */
  213: int
  214: hpfs_splitalsec (
  215: 	struct hpfsmount *hpmp,
  216: 	alsec_t *asp,
  217: 	alsec_t **naspp,
  218: 	struct buf **nbpp)
  219: {
  220: 	alsec_t *nasp;
  221: 	struct buf *nbp;
  222: 	alblk_t *abp;
  223: 	alblk_t *nabp;
  224: 	int error, n1, n2, sz;
  225: 
  226: 	error = hpfs_allocalsec(hpmp, asp->as_parent, &nbp);
  227: 	if (error)
  228: 		return (error);
  229: 
  230: 	nasp = (alsec_t *)nbp->b_data;
  231: 	nabp = &nasp->as_ab;
  232: 	abp = &asp->as_ab;
  233: 
  234: 	n1 = (abp->ab_busycnt + 1) / 2;
  235: 	n2 = (abp->ab_busycnt - n1);
  236: 	sz = (abp->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t);
  237: 
  238: 	bcopy((caddr_t)abp + sizeof(alblk_t) + n1 * sz, 
  239: 	      (caddr_t)nabp + sizeof(alblk_t), n2 * sz);
  240: 
  241: 	nabp->ab_flag = abp->ab_flag;
  242: 	nabp->ab_busycnt = n2;
  243: 	nabp->ab_freecnt = (0x1e0 / sz - n2);
  244: 	nabp->ab_freeoff += n2 * sz;
  245: 
  246: 	abp->ab_busycnt -= n1;
  247: 	abp->ab_freecnt += n1;
  248: 	abp->ab_freeoff -= n1 * sz;
  249: 
  250: 	*naspp = nasp;
  251: 	*nbpp = nbp;
  252: 
  253: 	return (0);
  254: }
  255: 
  256: /*
  257:  * Try to concatenate two AlSec's
  258:  *
  259:  * Moves all entries from AlSec corresponding (as1p, aanp[1]) into 
  260:  * corresponding aanp[0] one. If not enought space, then return ENOSPC.
  261:  *
  262:  * WARNING! YOU HAVE TO FIX aanp VALUES YOURSELF LATER:
  263:  * aanp[0].an_nextoff = aanp[1].an_nextoff;
  264:  */
  265: int
  266: hpfs_concatalsec (
  267: 	struct hpfsmount *hpmp,
  268: 	alsec_t *as0p,
  269: 	alsec_t *as1p,
  270: 	alnode_t *aanp)
  271: {
  272: 	alblk_t *ab0p;
  273: 	alblk_t *ab1p;
  274: 	int sz;
  275: 	
  276: 	dprintf(("hpfs_concatalsec: AlSecs at 0x%x and 0x%x \n",
  277: 		as0p->as_self,as1p->as_self));
  278: 
  279: 	ab0p = &as0p->as_ab;
  280: 	ab1p = &as1p->as_ab;
  281: 	sz = (ab0p->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t);
  282: 
  283: 	if (ab0p->ab_freecnt > ab1p->ab_busycnt) {
  284: 		/*
  285: 		 * Concatenate AlSecs
  286: 		 */
  287: 		if (ab0p->ab_flag & AB_NODES) 
  288: 			AB_LASTANP(ab0p)->an_nextoff = aanp[0].an_nextoff;
  289: 
  290: 		bcopy (AB_ALNODE(ab1p), AB_FREEANP(ab0p),
  291: 			 ab1p->ab_busycnt * sz);
  292: 
  293: 		AB_ADDNREC(ab0p, sz, ab1p->ab_busycnt);
  294: 
  295: 		return (0);
  296: 	} else {
  297: 		/* Not enought space to concatenate */
  298: 		return (ENOSPC);
  299: 	}
  300: }
  301: 
  302: /*
  303:  * Transform AlBlk structure into new allocated 
  304:  * AlSec.
  305:  *
  306:  * DOESN'T SET AlSec'S PARENT LSN.
  307:  */
  308: int
  309: hpfs_alblk2alsec (
  310: 	struct hpfsmount *hpmp,
  311: 	alblk_t *abp,
  312: 	alsec_t **naspp,
  313: 	struct buf **nbpp)
  314: {
  315: 	alsec_t *nasp;
  316: 	alblk_t *nabp;
  317: 	struct buf *nbp;
  318: 	int error, sz;
  319: 
  320: 	error = hpfs_allocalsec(hpmp, 0, &nbp);
  321: 	if (error)
  322: 		return (error);
  323: 
  324: 	nasp = (alsec_t *)nbp->b_data;
  325: 	nabp = &nasp->as_ab;
  326: 
  327: 	sz = (abp->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t);
  328: 
  329: 	bcopy (abp, nabp, sizeof(alblk_t) + sz * abp->ab_busycnt);
  330: 
  331: 	nabp->ab_freecnt = 0x1e0 / sz - nabp->ab_busycnt;
  332: 
  333: 	*naspp = nasp;
  334: 	*nbpp = nbp;
  335: 
  336: 	return (0);
  337: }
  338: 
  339: /*
  340:  * Allocate len blocks and concatenate them to file.
  341:  * If we hadn't found contignous run of len blocks, concatenate
  342:  * as much as we can, and return.
  343:  * 
  344:  */
  345: int
  346: hpfs_addextent (
  347: 	struct hpfsmount *hpmp,
  348: 	struct hpfsnode *hp,
  349: 	u_long len)
  350: {
  351: 	alblk_t *rabp;
  352: 	alnode_t ranp[2];
  353: 	alleaf_t al;
  354: 	int error;
  355: 	u_long pf;
  356: 
  357: 	/*
  358: 	 * We don't know for now start lsn of block
  359: 	 */
  360: 	al.al_lsn = ~0;
  361: 	al.al_len = len;
  362: 	al.al_off = (hp->h_fn.fn_size + DEV_BSIZE - 1) >> DEV_BSHIFT;
  363: 
  364: 	rabp = &hp->h_fn.fn_ab;
  365: 
  366: 	/* Init AlBlk if this is first extent */
  367: 	if (al.al_off == 0) {
  368: 		lsn_t nlsn;
  369: 		u_long nlen;
  370: 
  371: 		dprintf(("hpfs_addextent: init AlBlk in root\n"));
  372: 
  373: 		rabp->ab_busycnt = 0;
  374: 		rabp->ab_freecnt = 0x8;
  375: 		rabp->ab_freeoff = sizeof(alblk_t);
  376: 		rabp->ab_flag = 0;
  377: 
  378: 		error = hpfs_bmlookup (hpmp, 0, hp->h_no + 1, al.al_len, &nlsn, &nlen);
  379: 		if (error)
  380: 			return (error);
  381: 
  382: 		error = hpfs_bmmarkbusy(hpmp, nlsn, nlen);
  383: 		if (error)
  384: 			return (error);
  385: 						
  386: 		dprintf(("hpfs_addextent: new: 0x%x 0x%lx, ", nlsn, nlen));
  387: 
  388: 		AL_SET(AB_FREEALP(rabp), al.al_off, nlen, nlsn);
  389: 		AB_ADDAL(rabp);
  390: 
  391: 		al.al_off += nlen;
  392: 		al.al_len -= nlen;
  393: 	}
  394: 
  395: retry:
  396: 	dprintf(("hpfs_addextent: AlBlk: [0x%x, 0x%x, 0x%x] need: 0x%x\n",
  397: 		 rabp->ab_freecnt, rabp->ab_busycnt, rabp->ab_flag, al.al_len));
  398: 
  399: 	while ((al.al_len) && (rabp->ab_freecnt > 0)) {
  400: 		if (rabp->ab_flag & AB_NODES) {
  401: 			alnode_t *anp;
  402: 			/*
  403: 			 * This is level containing AlNodes, so try to 
  404: 			 * insert recursively into last entry.
  405: 			 */
  406: 			anp = AB_LASTANP(rabp);
  407: 			dprintf(("hpfs_addextent: AlNode: [0x%x,0x%x] \n",
  408: 				 anp->an_nextoff,anp->an_lsn));
  409: 
  410: 			/*
  411: 			 * Try to insert...
  412: 			 */
  413: 			error = hpfs_addextentr (hpmp, anp->an_lsn, &al, ranp, &pf);
  414: 			if (error) {
  415: 				printf("hpfs_addextent: FAILED %d\n",error);
  416: 				return (error);
  417: 			}
  418: 
  419: 			switch (pf) {
  420: 			case AE_SPLIT:
  421: 				dprintf(("hpfs_addextent: successful (split)\n"));
  422: 				/*
  423: 				 * Then hpfs_addextentr has split tree below, now
  424: 				 * we need to fix this level. Particulary:
  425: 				 * fix last AlNode and add another one.
  426: 				 */
  427: 
  428: 				bcopy(ranp, AB_LASTANP(rabp), sizeof(alnode_t) * 2);
  429: 				AB_ADDAN(rabp);
  430: 				break;
  431: 
  432: 			default:
  433: 			case AE_DONE:
  434: 				dprintf(("hpfs_addextent: successful\n"));
  435: 				break;
  436: 			}
  437: 		} else {
  438: 			alleaf_t *alp;
  439: 
  440: 			alp = AB_LASTALP(rabp);
  441: 			dprintf(("hpfs_addextent: AlLeaf: [0x%x,0x%x,0x%x] \n",
  442: 				 alp->al_off,alp->al_len,alp->al_lsn));
  443: 
  444: 			/* Check if we trying to add in right place */
  445: 			if (alp->al_off + alp->al_len == al.al_off) {
  446: 				lsn_t nlsn;
  447: 				u_long nlen;
  448: 
  449: 				/*
  450: 				 * Search bitmap for block begining from
  451: 				 * alp->al_lsn + alp->al_len and long of ralp->al_len
  452: 				 */
  453: 				error = hpfs_bmlookup (hpmp, 0,
  454: 					alp->al_lsn + alp->al_len, al.al_len, &nlsn, &nlen);
  455: 				if (error)
  456: 					return (error);
  457: 
  458: 				error = hpfs_bmmarkbusy(hpmp, nlsn, nlen);
  459: 				if (error)
  460: 					return (error);
  461: 						
  462: 				dprintf(("hpfs_addextent: new: 0x%x 0x%lx, ", nlsn, nlen));
  463: 
  464: 				if (alp->al_lsn + alp->al_len == nlsn) {
  465: 					dprintf(("extended existed leaf\n"));
  466: 
  467: 					alp->al_len += nlen;
  468: 				} else {
  469: 					dprintf(("created new leaf\n"));
  470: 					AL_SET(AB_FREEALP(rabp), al.al_off, nlen, nlsn);
  471: 					AB_ADDAL(rabp);
  472: 				}
  473: 				al.al_off += nlen;
  474: 				al.al_len -= nlen;
  475: 			} else {
  476: 				printf("hpfs_addextent: INTERNAL INCONSISTENCE\n");
  477: 				return (EINVAL);
  478: 			}
  479: 		}
  480: 	}
  481: 
  482: 	/*
  483: 	 * Move AlBlk contain to new AlSec (it will fit more
  484: 	 * entries) if overflowed (no more free entries).
  485: 	 */
  486: 	if (rabp->ab_freecnt <= 0) {
  487: 		struct buf *nbp;
  488: 		alsec_t * nrasp;
  489: 
  490: 		dprintf(("hpfs_addextent: overflow, convt\n"));
  491: 
  492: 		/*
  493: 		 * Convert AlBlk to new AlSec, it will set
  494: 		 * AB_FNPARENT also.
  495: 		 */
  496: 		rabp->ab_flag |= AB_FNPARENT;
  497: 		error = hpfs_alblk2alsec (hpmp, rabp, &nrasp, &nbp);
  498: 		if (error) {
  499: 			printf("hpfs_addextent: CAN'T CONVT\n");
  500: 			return (error);
  501: 		}
  502: 		nrasp->as_parent = hp->h_no;
  503: 
  504: 		/*
  505: 		 * Scan all childrens (if exist), set new parent and
  506: 		 * clean their AB_FNPARENT flag.
  507: 		 */
  508: 		if (rabp->ab_flag & AB_NODES) {
  509: 			int i;
  510: 			alsec_t * asp;
  511: 			alnode_t * anp;
  512: 			struct buf * bp;
  513: 
  514: 			anp = AB_ALNODE(rabp);
  515: 			for (i=0; i<rabp->ab_busycnt; i++) {
  516: 				error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp);
  517: 				if (error)
  518: 					return (error);
  519: 
  520: 				asp = (alsec_t *)bp->b_data;
  521: 				asp->as_ab.ab_flag &= ~AB_FNPARENT;
  522: 				asp->as_parent = nrasp->as_self;
  523: 
  524: 				bdwrite(bp);
  525: 				anp ++;
  526: 			}
  527: 		}
  528: 
  529: 		/* Convert AlBlk to contain AlNodes */
  530: 		rabp->ab_flag = AB_NODES;
  531: 		rabp->ab_busycnt = 0;
  532: 		rabp->ab_freecnt = 0xC;
  533: 		rabp->ab_freeoff = sizeof(alblk_t);
  534: 
  535: 		/* Add AlNode for new allocated AlSec */
  536: 		AN_SET(AB_FREEANP(rabp), ~0, nrasp->as_self);
  537: 		AB_ADDAN(rabp);
  538: 
  539: 		bdwrite(nbp);
  540: 	}
  541: 
  542: 	if (al.al_len) {
  543: 		dprintf(("hpfs_addextent: root retry\n"));
  544: 		goto retry;
  545: 	}
  546: 
  547: 	return (0);
  548: }
  549: 
  550: /*
  551:  * Descent down to the end of tree, then search for
  552:  * ralp->len contignous run begining from last run's end and
  553:  * concatenate new block! If we can't find one, then...
  554:  */
  555: int
  556: hpfs_addextentr (
  557: 	struct hpfsmount *hpmp,		/* Mix info */
  558: 	lsn_t rlsn,			/* LSN containing AlSec */
  559: 	alleaf_t *ralp,			/* AlLeaf to insert */
  560: 	alnode_t *ranp,			/* New AlNodes' values */
  561: 	u_long *resp)			/* Mix returning info */
  562: {
  563: 	struct buf *rbp;
  564: 	alsec_t *rasp;
  565: 	alblk_t *rabp;
  566: 	alleaf_t *alp;
  567: 	alnode_t *anp;
  568: 	int error;
  569: 	u_long pf;
  570: 	u_long wb;
  571: 
  572: 	*resp = 0;
  573: 
  574: 	dprintf(("hpfs_addextentr: AlSec at 0x%x\n", rlsn));
  575: 
  576: 	error = hpfs_breadalsec(hpmp, rlsn, &rbp);
  577: 	if (error)
  578: 		return (error);
  579: 
  580: 	rasp = (alsec_t *)rbp->b_data;
  581: 	rabp = &rasp->as_ab;
  582: 	wb = 0;
  583: 
  584: 	dprintf(("hpfs_addextentr: AlBlk: [0x%x, 0x%x, 0x%x]\n",
  585: 		 rabp->ab_freecnt, rabp->ab_busycnt, rabp->ab_flag));
  586: 
  587: 	while ((ralp->al_len) && (rabp->ab_freecnt > 0)) {
  588: 		if (rabp->ab_flag & AB_NODES) {
  589: 			/*
  590: 			 * This is level containing AlNodes, so try to 
  591: 			 * insert recursively into last entry.
  592: 			 */
  593: 			anp = AB_LASTANP(rabp);
  594: 			dprintf(("hpfs_addextentr: AlNode: [0x%x,0x%x] \n",
  595: 				 anp->an_nextoff,anp->an_lsn));
  596: 
  597: 			/*
  598: 			 * Try to insert...
  599: 			 */
  600: 			error = hpfs_addextentr (hpmp, anp->an_lsn, ralp, ranp, &pf);
  601: 			if (error) {
  602: 				printf("hpfs_addextentr: FAILED %d\n",error);
  603: 				goto fail;
  604: 			}
  605: 
  606: 			switch (pf) {
  607: 			case AE_SPLIT:
  608: 				dprintf(("hpfs_addextentr: successful (split)\n"));
  609: 				/*
  610: 				 * Then hpfs_addextentr has split tree below, now
  611: 				 * we need to fix this level. Particulary:
  612: 				 * fix last AlNode and add another one.
  613: 				 */
  614: 				bcopy(ranp, AB_LASTANP(rabp), sizeof(alnode_t) * 2);
  615: 				AB_ADDAN(rabp);
  616: 				wb = 1;
  617: 				break;
  618: 
  619: 			default:
  620: 			case AE_DONE:
  621: 				dprintf(("hpfs_addextentr: successful\n"));
  622: 				break;		
  623: 			}
  624: 		} else {
  625: 			alp = AB_LASTALP(rabp);
  626: 			dprintf(("hpfs_addextentr: AlLeaf: [0x%x,0x%x,0x%x] \n",
  627: 				 alp->al_off,alp->al_len,alp->al_lsn));
  628: 
  629: 			/* Check if we trying to add in right place */
  630: 			if (alp->al_off + alp->al_len == ralp->al_off) {
  631: 				lsn_t nlsn;
  632: 				u_long nlen;
  633: 				/*
  634: 				 * Search bitmap for block begining from
  635: 				 * alp->al_lsn + alp->al_len and long of ralp->al_len
  636: 				 */
  637: 				error = hpfs_bmlookup (hpmp, 0,
  638: 					alp->al_lsn + alp->al_len, ralp->al_len, &nlsn, &nlen);
  639: 				if (error)
  640: 					goto fail;
  641: 
  642: 				error = hpfs_bmmarkbusy(hpmp, nlsn, nlen);
  643: 				if (error)
  644: 					goto fail;
  645: 						
  646: 				dprintf(("hpfs_addextentr: new: 0x%x 0x%lx, ", nlsn, nlen));
  647: 
  648: 				/* 
  649: 				 * If ending of existed entry fits the
  650: 				 * begining of the extent being added,
  651: 				 * then we add concatenate two extents.
  652: 				 */
  653: 				if (alp->al_lsn + alp->al_len == nlsn) {
  654: 					dprintf(("concat\n"));
  655: 					alp->al_len += nlen;
  656: 				} else {
  657: 					dprintf(("created new leaf\n"));
  658: 					AL_SET(AB_FREEALP(rabp), ralp->al_off, nlen, nlsn);
  659: 					AB_ADDAL(rabp);
  660: 				}
  661: 
  662: 				ralp->al_len -= nlen;
  663: 				ralp->al_off += nlen;
  664: 			} else {
  665: 				printf("hpfs_addextentr: INTERNAL INCONSISTENCE\n");
  666: 				error = (EINVAL);
  667: 				goto fail;
  668: 			}
  669: 		}
  670: 	}
  671: 
  672: 	/*
  673: 	 * Split AlBlk if overflowed.
  674: 	 */
  675: 	if (rabp->ab_freecnt <= 0) {
  676: 		struct buf *nbp;
  677: 		alsec_t * nrasp;
  678: 
  679: 		dprintf(("hpfs_addextentr: overflow, split\n"));
  680: 
  681: 		error = hpfs_splitalsec (hpmp, rasp, &nrasp, &nbp);
  682: 		if (error) {
  683: 			printf("hpfs_addextent: CAN'T SPLIT\n");
  684: 			goto fail;
  685: 		}
  686: 
  687: 		if (rabp->ab_flag & AB_NODES) {
  688: 			int i;
  689: 			alsec_t * asp;
  690: 			alnode_t * anp;
  691: 			struct buf * bp;
  692: 
  693: 			ranp[0].an_nextoff = 
  694: 				AB_LASTANP(&rasp->as_ab)->an_nextoff;
  695: 
  696: 			/* We need to set left subtree's last entry
  697: 			 * offset to 0xFFFFFFFF for OS/2 to be able
  698: 			 * to read our files. It treats absence  of
  699: 			 * 0xFFFFFFFF as error.
  700: 			 */
  701: 			AB_LASTANP(&rasp->as_ab)->an_nextoff = ~0;
  702: 
  703: 			/* We need to fix new allocated AlSec's
  704: 			 * children, becouse their parent has changed.
  705: 			 */
  706: 			anp = AB_ALNODE(&nrasp->as_ab);
  707: 			for (i=0; i<nrasp->as_ab.ab_busycnt; i++) {
  708: 				error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp);
  709: 				if (error) {
  710: 					brelse(nbp);
  711: 					goto fail;
  712: 				}
  713: 
  714: 				asp = (alsec_t *)bp->b_data;
  715: 				asp->as_parent = nrasp->as_self;
  716: 
  717: 				bdwrite(bp);
  718: 				anp ++;
  719: 			}
  720: 		} else {
  721: 			ranp[0].an_nextoff = 
  722: 				AB_ALLEAF(&nrasp->as_ab)->al_off;
  723: 		}
  724: 
  725: 		ranp[0].an_lsn = rasp->as_self;
  726: 		ranp[1].an_nextoff = ~0;
  727: 		ranp[1].an_lsn = nrasp->as_self;
  728: 
  729: 		bdwrite(nbp);
  730: 
  731: 		*resp = AE_SPLIT;
  732: 		wb = 1;
  733: 	}
  734: 
  735: 	if (wb)
  736: 		bdwrite (rbp);
  737: 	else
  738: 		brelse(rbp);
  739: 
  740: 	return (0);
  741: 
  742: fail:
  743: 	brelse(rbp);
  744: 
  745: 	return (error);
  746: }
  747: 
  748: /*
  749:  * Recursive routine walking down the b-tree and deallocating all
  750:  * extents above bn. Returns *resp != 0 if alblk was totally 
  751:  * deallocated and may be freed. Tries to keep b-tree.
  752:  *
  753:  * (XXXX) NOTE! THIS ROUTINE WILL NEVER DECREMENT DEPTH OF
  754:  * THE TREE.
  755:  */
  756: int
  757: hpfs_truncatealblk (
  758: 	struct hpfsmount *hpmp,
  759: 	alblk_t *abp,
  760: 	lsn_t bn,
  761: 	int *resp)
  762: {
  763: 	int error;
  764: 	alleaf_t *alp;
  765: 	alnode_t *anp;
  766: 	alsec_t *asp;
  767: 	struct buf *bp;
  768: 
  769: 	dprintf(("hpfs_truncatealblk: AlBlk: [0x%x,0x%x, 0x%x]\n",
  770: 		 abp->ab_freecnt, abp->ab_busycnt, abp->ab_flag));
  771: 
  772: 	if (abp->ab_flag & AB_NODES) {
  773: 		/*
  774: 		 * Scan array of AlNodes backward,
  775: 		 * diving in recursion if needed
  776: 		 */
  777: 		anp = AB_LASTANP(abp);
  778: 
  779: 		while (abp->ab_busycnt && (bn <= anp->an_nextoff)) {
  780: 			dprintf(("hpfs_truncatealblk: AlNode: [0x%x,0x%x] \n",
  781: 				anp->an_nextoff,anp->an_lsn));
  782: 
  783: 			error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp);
  784: 			if (error)
  785: 				return (error);
  786: 
  787: 			asp = (alsec_t *)bp->b_data;
  788: 
  789: 			error = hpfs_truncatealblk (hpmp,
  790: 					&asp->as_ab, bn, resp);
  791: 			if (error) {
  792: 				brelse(bp);
  793: 				return (error);
  794: 			}
  795: 
  796: 			if (*resp) {
  797: 				brelse (bp);
  798: 
  799: 				error = hpfs_bmmarkfree(hpmp,
  800: 						anp->an_lsn, 1);
  801: 				if (error)
  802: 					return (error);
  803: 
  804: 				AB_RMAN(abp);
  805: 				anp --;
  806: 			} else {
  807: 				/* 
  808: 				 * We have deallocated some entries, some space
  809: 				 * migth been freed, then try to concat two 
  810: 				 * last AlSec.
  811: 				 */
  812: 				anp->an_nextoff = ~0;
  813: 				if (abp->ab_busycnt >= 2) {
  814: 					alsec_t *as0p;
  815: 					struct buf *b0p;
  816: 
  817: 					error = hpfs_breadalsec(hpmp,
  818: 							(anp-1)->an_lsn, &b0p);
  819: 					if (error)
  820: 						return (error);
  821: 
  822: 					as0p = (alsec_t *)b0p->b_data;
  823: 					error = hpfs_concatalsec(hpmp,
  824: 							as0p, asp, anp - 1);
  825: 					if (error == ENOSPC) {
  826: 						/* Not enought space */
  827: 						brelse (b0p);
  828: 						bdwrite (bp);
  829: 					} else if (error == 0) {
  830: 						/* All OK  */
  831: 						(anp-1)->an_nextoff = anp->an_nextoff;
  832: 
  833: 						bdwrite (b0p);
  834: 						brelse (bp);
  835: 
  836: 						error = hpfs_bmmarkfree(hpmp,
  837: 								anp->an_lsn, 1);
  838: 						if (error)
  839: 							return (error);
  840: 
  841: 						AB_RMAN(abp);
  842: 					} else {
  843: 						/* True error */
  844: 						brelse (b0p);
  845: 						brelse (bp);
  846: 						return (error);
  847: 					}
  848: 				} else {
  849: 					/* Nowhere to concatenate */
  850: 					bdwrite (bp);
  851: 				}
  852: 
  853: 				/* There can not be any more entries
  854: 				 * over greater bn, becouse last AlSec
  855: 				 * wasn't freed totally. So go out.
  856: 				 */
  857: 				break;
  858: 			}
  859: 		}
  860: 
  861: 		if (abp->ab_busycnt == 0)
  862: 			*resp = 1;
  863: 		else
  864: 			*resp = 0;
  865: 	} else {
  866: 		/*
  867: 		 * Scan array of AlLeafs backward,
  868: 		 * free all above bn.
  869: 		 */
  870: 		alp = AB_LASTALP(abp);
  871: 
  872: 		while (abp->ab_busycnt && (bn < alp->al_off + alp->al_len)){
  873: 			dprintf(("hpfs_truncatealblk: AlLeaf: [0x%x,0x%x,0x%x] \n",
  874: 				 alp->al_off,alp->al_len,alp->al_lsn));
  875: 
  876: 			if (bn <= alp->al_off) {
  877: 				error = hpfs_bmmarkfree(hpmp, alp->al_lsn,
  878: 						alp->al_len);
  879: 				if (error)
  880: 					return (error);
  881: 
  882: 				AB_RMAL(abp);
  883: 				alp --;
  884: 			} else if ((bn > alp->al_off) &&
  885: 			    	   (bn < alp->al_off + alp->al_len)){
  886: 				error = hpfs_bmmarkfree(hpmp,
  887: 						alp->al_lsn + bn - alp->al_off,
  888: 						alp->al_len - bn + alp->al_off);
  889: 				if (error)
  890: 					return (error);
  891: 
  892: 				alp->al_len = bn - alp->al_off;
  893: 
  894: 				break;
  895: 			} else
  896: 				break;
  897: 		}
  898: 	}
  899: 
  900: 	/* Signal parent deallocation, if need */
  901: 	if (abp->ab_busycnt == 0) 
  902: 		*resp = 1;
  903: 	else
  904: 		*resp = 0;
  905: 
  906: 	return (0);
  907: }