2 * Copyright (c) 1998, 1999 Semen Ustimenko (semenu@FreeBSD.org)
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
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.8 2006/12/23 00:41:29 swildner Exp $
30 #include <sys/param.h>
31 #include <sys/systm.h>
32 #include <sys/kernel.h>
35 #include <sys/types.h>
37 #include <sys/vnode.h>
38 #include <sys/mount.h>
39 #include <sys/namei.h>
40 #include <sys/malloc.h>
46 #include "hpfs_subr.h"
48 #define AE_DONE 0 /* Nothing to change */
49 #define AE_SPLIT 2 /* Split was done, ranp is valid */
51 int hpfs_addextentr (struct hpfsmount *, lsn_t, alleaf_t *,
52 alnode_t *, u_long *);
53 int hpfs_allocalsec (struct hpfsmount *, lsn_t, struct buf **);
54 int hpfs_alblk2alsec (struct hpfsmount *, alblk_t *, alsec_t **,
56 int hpfs_splitalsec (struct hpfsmount *, alsec_t *, alsec_t **,
58 int hpfs_concatalsec (struct hpfsmount *, alsec_t *, alsec_t *,
62 * Map file offset to disk offset. hpfsnode have to be locked.
65 hpfs_hpbmap(struct hpfsnode *hp, daddr_t bn, daddr_t *bnp, int *runp)
73 dprintf(("hpfs_hpbmap(0x%x, 0x%x): ",hp->h_no, bn));
76 abp = &hp->h_fn.fn_ab;
77 alp = (alleaf_t *)&hp->h_fn.fn_abd;
78 anp = (alnode_t *)&hp->h_fn.fn_abd;
81 if (abp->ab_flag & AB_NODES) {
82 for (i=0; i<abp->ab_busycnt; i++, anp++) {
83 dprintf(("[0x%x,0x%x] ",anp->an_nextoff,anp->an_lsn));
84 if (bn < anp->an_nextoff) {
87 dprintf(("< found | "));
91 error = bread(hp->h_devvp,
92 dbtodoff(anp->an_lsn),
95 kprintf("hpfs_hpbmap: bread error\n");
100 asp = (alsec_t *) bp->b_data;
101 if (asp->as_magic != AS_MAGIC) {
103 kprintf("hpfs_hpbmap: "
104 "MAGIC DOESN'T MATCH");
109 alp = (alleaf_t *)&asp->as_abd;
110 anp = (alnode_t *)&asp->as_abd;
116 for (i=0; i<abp->ab_busycnt; i++, alp++) {
117 dprintf(("[0x%x,0x%x,0x%x] ",
118 alp->al_off,alp->al_len,alp->al_lsn));
120 if ((bn >= alp->al_off) &&
121 (!alp->al_len || (bn < alp->al_off + alp->al_len))) {
122 dprintf(("found, "));
124 *bnp = bn - alp->al_off + alp->al_lsn;
126 dprintf((" 0x%x ", *bnp));
130 *runp = alp->al_off - 1 +
135 dprintf((" 0x%x cont", *runp));
147 dprintf(("END, notfound\n"));
151 dprintf(("hpfs_hpbmap: offset too big\n"));
157 * Find place and preinitialize AlSec structure
158 * AlBlk is initialized to contain AlLeafs.
161 hpfs_allocalsec(struct hpfsmount *hpmp, lsn_t parlsn, struct buf **bpp)
170 error = hpfs_bmfblookup(hpmp, &lsn);
172 kprintf("hpfs_allocalsec: CAN'T ALLOC SPACE FOR AlSec\n");
176 error = hpfs_bmmarkbusy(hpmp, lsn, 1);
180 bp = getblk(hpmp->hpm_devvp, dbtodoff(lsn), DEV_BSIZE, 0, 0);
183 /* Fill AlSec info */
184 asp = (alsec_t *) bp->b_data;
185 asp->as_magic = AS_MAGIC;
187 asp->as_parent = parlsn;
190 asp->as_ab.ab_flag = 0;
191 asp->as_ab.ab_busycnt = 0;
192 asp->as_ab.ab_freecnt = 0x28;
193 asp->as_ab.ab_freeoff = sizeof(alblk_t);
201 * Split AlSec structure into new allocated:
202 * allocate new AlSec; then move second half of asp's entries in
203 * into it; set proper flags.
205 * IF AlSec CONTAINS AlNodes, THEN YOU ALMOST EVERYTIME HAVE TO
206 * FIX LAST AlNode in OLD AlSec (NEXTOFF TO BE 0xFFFFFFFF).
207 * TOGETHER WITH FIXING ALL CHILDREN'S AlSecs (THEY HAVE GOT NEW PARENT).
210 hpfs_splitalsec(struct hpfsmount *hpmp, alsec_t *asp, alsec_t **naspp,
217 int error, n1, n2, sz;
219 error = hpfs_allocalsec(hpmp, asp->as_parent, &nbp);
223 nasp = (alsec_t *)nbp->b_data;
227 n1 = (abp->ab_busycnt + 1) / 2;
228 n2 = (abp->ab_busycnt - n1);
229 sz = (abp->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t);
231 bcopy((caddr_t)abp + sizeof(alblk_t) + n1 * sz,
232 (caddr_t)nabp + sizeof(alblk_t), n2 * sz);
234 nabp->ab_flag = abp->ab_flag;
235 nabp->ab_busycnt = n2;
236 nabp->ab_freecnt = (0x1e0 / sz - n2);
237 nabp->ab_freeoff += n2 * sz;
239 abp->ab_busycnt -= n1;
240 abp->ab_freecnt += n1;
241 abp->ab_freeoff -= n1 * sz;
250 * Try to concatenate two AlSec's
252 * Moves all entries from AlSec corresponding (as1p, aanp[1]) into
253 * corresponding aanp[0] one. If not enought space, then return ENOSPC.
255 * WARNING! YOU HAVE TO FIX aanp VALUES YOURSELF LATER:
256 * aanp[0].an_nextoff = aanp[1].an_nextoff;
259 hpfs_concatalsec(struct hpfsmount *hpmp, alsec_t *as0p, alsec_t *as1p,
266 dprintf(("hpfs_concatalsec: AlSecs at 0x%x and 0x%x \n",
267 as0p->as_self,as1p->as_self));
271 sz = (ab0p->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t);
273 if (ab0p->ab_freecnt > ab1p->ab_busycnt) {
277 if (ab0p->ab_flag & AB_NODES)
278 AB_LASTANP(ab0p)->an_nextoff = aanp[0].an_nextoff;
280 bcopy (AB_ALNODE(ab1p), AB_FREEANP(ab0p),
281 ab1p->ab_busycnt * sz);
283 AB_ADDNREC(ab0p, sz, ab1p->ab_busycnt);
287 /* Not enought space to concatenate */
293 * Transform AlBlk structure into new allocated
296 * DOESN'T SET AlSec'S PARENT LSN.
299 hpfs_alblk2alsec(struct hpfsmount *hpmp, alblk_t *abp, alsec_t **naspp,
307 error = hpfs_allocalsec(hpmp, 0, &nbp);
311 nasp = (alsec_t *)nbp->b_data;
314 sz = (abp->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t);
316 bcopy (abp, nabp, sizeof(alblk_t) + sz * abp->ab_busycnt);
318 nabp->ab_freecnt = 0x1e0 / sz - nabp->ab_busycnt;
327 * Allocate len blocks and concatenate them to file.
328 * If we hadn't found contignous run of len blocks, concatenate
329 * as much as we can, and return.
333 hpfs_addextent(struct hpfsmount *hpmp, struct hpfsnode *hp, u_long len)
342 * We don't know for now start lsn of block
346 al.al_off = (hp->h_fn.fn_size + DEV_BSIZE - 1) >> DEV_BSHIFT;
348 rabp = &hp->h_fn.fn_ab;
350 /* Init AlBlk if this is first extent */
351 if (al.al_off == 0) {
355 dprintf(("hpfs_addextent: init AlBlk in root\n"));
357 rabp->ab_busycnt = 0;
358 rabp->ab_freecnt = 0x8;
359 rabp->ab_freeoff = sizeof(alblk_t);
362 error = hpfs_bmlookup (hpmp, 0, hp->h_no + 1, al.al_len, &nlsn, &nlen);
366 error = hpfs_bmmarkbusy(hpmp, nlsn, nlen);
370 dprintf(("hpfs_addextent: new: 0x%x 0x%lx, ", nlsn, nlen));
372 AL_SET(AB_FREEALP(rabp), al.al_off, nlen, nlsn);
380 dprintf(("hpfs_addextent: AlBlk: [0x%x, 0x%x, 0x%x] need: 0x%x\n",
381 rabp->ab_freecnt, rabp->ab_busycnt, rabp->ab_flag, al.al_len));
383 while ((al.al_len) && (rabp->ab_freecnt > 0)) {
384 if (rabp->ab_flag & AB_NODES) {
387 * This is level containing AlNodes, so try to
388 * insert recursively into last entry.
390 anp = AB_LASTANP(rabp);
391 dprintf(("hpfs_addextent: AlNode: [0x%x,0x%x] \n",
392 anp->an_nextoff,anp->an_lsn));
397 error = hpfs_addextentr (hpmp, anp->an_lsn, &al, ranp, &pf);
399 kprintf("hpfs_addextent: FAILED %d\n",error);
405 dprintf(("hpfs_addextent: successful (split)\n"));
407 * Then hpfs_addextentr has split tree below, now
408 * we need to fix this level. Particulary:
409 * fix last AlNode and add another one.
412 bcopy(ranp, AB_LASTANP(rabp), sizeof(alnode_t) * 2);
418 dprintf(("hpfs_addextent: successful\n"));
424 alp = AB_LASTALP(rabp);
425 dprintf(("hpfs_addextent: AlLeaf: [0x%x,0x%x,0x%x] \n",
426 alp->al_off,alp->al_len,alp->al_lsn));
428 /* Check if we trying to add in right place */
429 if (alp->al_off + alp->al_len == al.al_off) {
434 * Search bitmap for block begining from
435 * alp->al_lsn + alp->al_len and long of ralp->al_len
437 error = hpfs_bmlookup (hpmp, 0,
438 alp->al_lsn + alp->al_len, al.al_len, &nlsn, &nlen);
442 error = hpfs_bmmarkbusy(hpmp, nlsn, nlen);
446 dprintf(("hpfs_addextent: new: 0x%x 0x%lx, ", nlsn, nlen));
448 if (alp->al_lsn + alp->al_len == nlsn) {
449 dprintf(("extended existed leaf\n"));
453 dprintf(("created new leaf\n"));
454 AL_SET(AB_FREEALP(rabp), al.al_off, nlen, nlsn);
460 kprintf("hpfs_addextent: INTERNAL INCONSISTENCE\n");
467 * Move AlBlk contain to new AlSec (it will fit more
468 * entries) if overflowed (no more free entries).
470 if (rabp->ab_freecnt <= 0) {
474 dprintf(("hpfs_addextent: overflow, convt\n"));
477 * Convert AlBlk to new AlSec, it will set
480 rabp->ab_flag |= AB_FNPARENT;
481 error = hpfs_alblk2alsec (hpmp, rabp, &nrasp, &nbp);
483 kprintf("hpfs_addextent: CAN'T CONVT\n");
486 nrasp->as_parent = hp->h_no;
489 * Scan all childrens (if exist), set new parent and
490 * clean their AB_FNPARENT flag.
492 if (rabp->ab_flag & AB_NODES) {
498 anp = AB_ALNODE(rabp);
499 for (i=0; i<rabp->ab_busycnt; i++) {
500 error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp);
504 asp = (alsec_t *)bp->b_data;
505 asp->as_ab.ab_flag &= ~AB_FNPARENT;
506 asp->as_parent = nrasp->as_self;
513 /* Convert AlBlk to contain AlNodes */
514 rabp->ab_flag = AB_NODES;
515 rabp->ab_busycnt = 0;
516 rabp->ab_freecnt = 0xC;
517 rabp->ab_freeoff = sizeof(alblk_t);
519 /* Add AlNode for new allocated AlSec */
520 AN_SET(AB_FREEANP(rabp), ~0, nrasp->as_self);
527 dprintf(("hpfs_addextent: root retry\n"));
535 * Descent down to the end of tree, then search for
536 * ralp->len contignous run begining from last run's end and
537 * concatenate new block! If we can't find one, then...
541 * rlsn: LSN containing AlSec
542 * ralp: AlLeaf to insert
543 * ranp: New AlNodes' values
544 * resp: Mix returning info
547 hpfs_addextentr(struct hpfsmount *hpmp, lsn_t rlsn, alleaf_t *ralp,
548 alnode_t *ranp, u_long *resp)
561 dprintf(("hpfs_addextentr: AlSec at 0x%x\n", rlsn));
563 error = hpfs_breadalsec(hpmp, rlsn, &rbp);
567 rasp = (alsec_t *)rbp->b_data;
571 dprintf(("hpfs_addextentr: AlBlk: [0x%x, 0x%x, 0x%x]\n",
572 rabp->ab_freecnt, rabp->ab_busycnt, rabp->ab_flag));
574 while ((ralp->al_len) && (rabp->ab_freecnt > 0)) {
575 if (rabp->ab_flag & AB_NODES) {
577 * This is level containing AlNodes, so try to
578 * insert recursively into last entry.
580 anp = AB_LASTANP(rabp);
581 dprintf(("hpfs_addextentr: AlNode: [0x%x,0x%x] \n",
582 anp->an_nextoff,anp->an_lsn));
587 error = hpfs_addextentr (hpmp, anp->an_lsn, ralp, ranp, &pf);
589 kprintf("hpfs_addextentr: FAILED %d\n",error);
595 dprintf(("hpfs_addextentr: successful (split)\n"));
597 * Then hpfs_addextentr has split tree below, now
598 * we need to fix this level. Particulary:
599 * fix last AlNode and add another one.
601 bcopy(ranp, AB_LASTANP(rabp), sizeof(alnode_t) * 2);
608 dprintf(("hpfs_addextentr: successful\n"));
612 alp = AB_LASTALP(rabp);
613 dprintf(("hpfs_addextentr: AlLeaf: [0x%x,0x%x,0x%x] \n",
614 alp->al_off,alp->al_len,alp->al_lsn));
616 /* Check if we trying to add in right place */
617 if (alp->al_off + alp->al_len == ralp->al_off) {
621 * Search bitmap for block begining from
622 * alp->al_lsn + alp->al_len and long of ralp->al_len
624 error = hpfs_bmlookup (hpmp, 0,
625 alp->al_lsn + alp->al_len, ralp->al_len, &nlsn, &nlen);
629 error = hpfs_bmmarkbusy(hpmp, nlsn, nlen);
633 dprintf(("hpfs_addextentr: new: 0x%x 0x%lx, ", nlsn, nlen));
636 * If ending of existed entry fits the
637 * begining of the extent being added,
638 * then we add concatenate two extents.
640 if (alp->al_lsn + alp->al_len == nlsn) {
641 dprintf(("concat\n"));
644 dprintf(("created new leaf\n"));
645 AL_SET(AB_FREEALP(rabp), ralp->al_off, nlen, nlsn);
649 ralp->al_len -= nlen;
650 ralp->al_off += nlen;
652 kprintf("hpfs_addextentr: INTERNAL INCONSISTENCE\n");
660 * Split AlBlk if overflowed.
662 if (rabp->ab_freecnt <= 0) {
666 dprintf(("hpfs_addextentr: overflow, split\n"));
668 error = hpfs_splitalsec (hpmp, rasp, &nrasp, &nbp);
670 kprintf("hpfs_addextent: CAN'T SPLIT\n");
674 if (rabp->ab_flag & AB_NODES) {
681 AB_LASTANP(&rasp->as_ab)->an_nextoff;
683 /* We need to set left subtree's last entry
684 * offset to 0xFFFFFFFF for OS/2 to be able
685 * to read our files. It treats absence of
686 * 0xFFFFFFFF as error.
688 AB_LASTANP(&rasp->as_ab)->an_nextoff = ~0;
690 /* We need to fix new allocated AlSec's
691 * children, becouse their parent has changed.
693 anp = AB_ALNODE(&nrasp->as_ab);
694 for (i=0; i<nrasp->as_ab.ab_busycnt; i++) {
695 error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp);
701 asp = (alsec_t *)bp->b_data;
702 asp->as_parent = nrasp->as_self;
709 AB_ALLEAF(&nrasp->as_ab)->al_off;
712 ranp[0].an_lsn = rasp->as_self;
713 ranp[1].an_nextoff = ~0;
714 ranp[1].an_lsn = nrasp->as_self;
736 * Recursive routine walking down the b-tree and deallocating all
737 * extents above bn. Returns *resp != 0 if alblk was totally
738 * deallocated and may be freed. Tries to keep b-tree.
740 * (XXXX) NOTE! THIS ROUTINE WILL NEVER DECREMENT DEPTH OF
744 hpfs_truncatealblk(struct hpfsmount *hpmp, alblk_t *abp, lsn_t bn, int *resp)
752 dprintf(("hpfs_truncatealblk: AlBlk: [0x%x,0x%x, 0x%x]\n",
753 abp->ab_freecnt, abp->ab_busycnt, abp->ab_flag));
755 if (abp->ab_flag & AB_NODES) {
757 * Scan array of AlNodes backward,
758 * diving in recursion if needed
760 anp = AB_LASTANP(abp);
762 while (abp->ab_busycnt && (bn <= anp->an_nextoff)) {
763 dprintf(("hpfs_truncatealblk: AlNode: [0x%x,0x%x] \n",
764 anp->an_nextoff,anp->an_lsn));
766 error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp);
770 asp = (alsec_t *)bp->b_data;
772 error = hpfs_truncatealblk (hpmp,
773 &asp->as_ab, bn, resp);
782 error = hpfs_bmmarkfree(hpmp,
791 * We have deallocated some entries, some space
792 * migth been freed, then try to concat two
795 anp->an_nextoff = ~0;
796 if (abp->ab_busycnt >= 2) {
800 error = hpfs_breadalsec(hpmp,
801 (anp-1)->an_lsn, &b0p);
805 as0p = (alsec_t *)b0p->b_data;
806 error = hpfs_concatalsec(hpmp,
808 if (error == ENOSPC) {
809 /* Not enought space */
812 } else if (error == 0) {
814 (anp-1)->an_nextoff = anp->an_nextoff;
819 error = hpfs_bmmarkfree(hpmp,
832 /* Nowhere to concatenate */
836 /* There can not be any more entries
837 * over greater bn, becouse last AlSec
838 * wasn't freed totally. So go out.
844 if (abp->ab_busycnt == 0)
850 * Scan array of AlLeafs backward,
853 alp = AB_LASTALP(abp);
855 while (abp->ab_busycnt && (bn < alp->al_off + alp->al_len)){
856 dprintf(("hpfs_truncatealblk: AlLeaf: [0x%x,0x%x,0x%x] \n",
857 alp->al_off,alp->al_len,alp->al_lsn));
859 if (bn <= alp->al_off) {
860 error = hpfs_bmmarkfree(hpmp, alp->al_lsn,
867 } else if ((bn > alp->al_off) &&
868 (bn < alp->al_off + alp->al_len)){
869 error = hpfs_bmmarkfree(hpmp,
870 alp->al_lsn + bn - alp->al_off,
871 alp->al_len - bn + alp->al_off);
875 alp->al_len = bn - alp->al_off;
883 /* Signal parent deallocation, if need */
884 if (abp->ab_busycnt == 0)