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>
44 #include "hpfs_subr.h"
46 #define AE_DONE 0 /* Nothing to change */
47 #define AE_SPLIT 2 /* Split was done, ranp is valid */
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
**,
54 int hpfs_splitalsec (struct hpfsmount
*, alsec_t
*, alsec_t
**,
56 int hpfs_concatalsec (struct hpfsmount
*, alsec_t
*, alsec_t
*,
60 * Map file offset to disk offset. hpfsnode have to be locked.
63 hpfs_hpbmap(struct hpfsnode
*hp
, daddr_t bn
, daddr_t
*bnp
, int *runp
)
71 dprintf(("hpfs_hpbmap(0x%x, 0x%x): ",hp
->h_no
, bn
));
74 abp
= &hp
->h_fn
.fn_ab
;
75 alp
= (alleaf_t
*)&hp
->h_fn
.fn_abd
;
76 anp
= (alnode_t
*)&hp
->h_fn
.fn_abd
;
79 if (abp
->ab_flag
& AB_NODES
) {
80 for (i
=0; i
<abp
->ab_busycnt
; i
++, anp
++) {
81 dprintf(("[0x%x,0x%x] ",anp
->an_nextoff
,anp
->an_lsn
));
82 if (bn
< anp
->an_nextoff
) {
85 dprintf(("< found | "));
89 error
= bread(hp
->h_devvp
,
90 dbtodoff(anp
->an_lsn
),
93 kprintf("hpfs_hpbmap: bread error\n");
98 asp
= (alsec_t
*) bp
->b_data
;
99 if (asp
->as_magic
!= AS_MAGIC
) {
101 kprintf("hpfs_hpbmap: "
102 "MAGIC DOESN'T MATCH");
107 alp
= (alleaf_t
*)&asp
->as_abd
;
108 anp
= (alnode_t
*)&asp
->as_abd
;
114 for (i
=0; i
<abp
->ab_busycnt
; i
++, alp
++) {
115 dprintf(("[0x%x,0x%x,0x%x] ",
116 alp
->al_off
,alp
->al_len
,alp
->al_lsn
));
118 if ((bn
>= alp
->al_off
) &&
119 (!alp
->al_len
|| (bn
< alp
->al_off
+ alp
->al_len
))) {
120 dprintf(("found, "));
122 *bnp
= bn
- alp
->al_off
+ alp
->al_lsn
;
124 dprintf((" 0x%x ", *bnp
));
128 *runp
= alp
->al_off
- 1 +
133 dprintf((" 0x%x cont", *runp
));
145 dprintf(("END, notfound\n"));
149 dprintf(("hpfs_hpbmap: offset too big\n"));
155 * Find place and preinitialize AlSec structure
156 * AlBlk is initialized to contain AlLeafs.
159 hpfs_allocalsec(struct hpfsmount
*hpmp
, lsn_t parlsn
, struct buf
**bpp
)
168 error
= hpfs_bmfblookup(hpmp
, &lsn
);
170 kprintf("hpfs_allocalsec: CAN'T ALLOC SPACE FOR AlSec\n");
174 error
= hpfs_bmmarkbusy(hpmp
, lsn
, 1);
178 bp
= getblk(hpmp
->hpm_devvp
, dbtodoff(lsn
), DEV_BSIZE
, 0, 0);
181 /* Fill AlSec info */
182 asp
= (alsec_t
*) bp
->b_data
;
183 asp
->as_magic
= AS_MAGIC
;
185 asp
->as_parent
= parlsn
;
188 asp
->as_ab
.ab_flag
= 0;
189 asp
->as_ab
.ab_busycnt
= 0;
190 asp
->as_ab
.ab_freecnt
= 0x28;
191 asp
->as_ab
.ab_freeoff
= sizeof(alblk_t
);
199 * Split AlSec structure into new allocated:
200 * allocate new AlSec; then move second half of asp's entries in
201 * into it; set proper flags.
203 * IF AlSec CONTAINS AlNodes, THEN YOU ALMOST EVERYTIME HAVE TO
204 * FIX LAST AlNode in OLD AlSec (NEXTOFF TO BE 0xFFFFFFFF).
205 * TOGETHER WITH FIXING ALL CHILDREN'S AlSecs (THEY HAVE GOT NEW PARENT).
208 hpfs_splitalsec(struct hpfsmount
*hpmp
, alsec_t
*asp
, alsec_t
**naspp
,
215 int error
, n1
, n2
, sz
;
217 error
= hpfs_allocalsec(hpmp
, asp
->as_parent
, &nbp
);
221 nasp
= (alsec_t
*)nbp
->b_data
;
225 n1
= (abp
->ab_busycnt
+ 1) / 2;
226 n2
= (abp
->ab_busycnt
- n1
);
227 sz
= (abp
->ab_flag
& AB_NODES
) ? sizeof(alnode_t
) : sizeof(alleaf_t
);
229 bcopy((caddr_t
)abp
+ sizeof(alblk_t
) + n1
* sz
,
230 (caddr_t
)nabp
+ sizeof(alblk_t
), n2
* sz
);
232 nabp
->ab_flag
= abp
->ab_flag
;
233 nabp
->ab_busycnt
= n2
;
234 nabp
->ab_freecnt
= (0x1e0 / sz
- n2
);
235 nabp
->ab_freeoff
+= n2
* sz
;
237 abp
->ab_busycnt
-= n1
;
238 abp
->ab_freecnt
+= n1
;
239 abp
->ab_freeoff
-= n1
* sz
;
248 * Try to concatenate two AlSec's
250 * Moves all entries from AlSec corresponding (as1p, aanp[1]) into
251 * corresponding aanp[0] one. If not enought space, then return ENOSPC.
253 * WARNING! YOU HAVE TO FIX aanp VALUES YOURSELF LATER:
254 * aanp[0].an_nextoff = aanp[1].an_nextoff;
257 hpfs_concatalsec(struct hpfsmount
*hpmp
, alsec_t
*as0p
, alsec_t
*as1p
,
264 dprintf(("hpfs_concatalsec: AlSecs at 0x%x and 0x%x \n",
265 as0p
->as_self
,as1p
->as_self
));
269 sz
= (ab0p
->ab_flag
& AB_NODES
) ? sizeof(alnode_t
) : sizeof(alleaf_t
);
271 if (ab0p
->ab_freecnt
> ab1p
->ab_busycnt
) {
275 if (ab0p
->ab_flag
& AB_NODES
)
276 AB_LASTANP(ab0p
)->an_nextoff
= aanp
[0].an_nextoff
;
278 bcopy (AB_ALNODE(ab1p
), AB_FREEANP(ab0p
),
279 ab1p
->ab_busycnt
* sz
);
281 AB_ADDNREC(ab0p
, sz
, ab1p
->ab_busycnt
);
285 /* Not enought space to concatenate */
291 * Transform AlBlk structure into new allocated
294 * DOESN'T SET AlSec'S PARENT LSN.
297 hpfs_alblk2alsec(struct hpfsmount
*hpmp
, alblk_t
*abp
, alsec_t
**naspp
,
305 error
= hpfs_allocalsec(hpmp
, 0, &nbp
);
309 nasp
= (alsec_t
*)nbp
->b_data
;
312 sz
= (abp
->ab_flag
& AB_NODES
) ? sizeof(alnode_t
) : sizeof(alleaf_t
);
314 bcopy (abp
, nabp
, sizeof(alblk_t
) + sz
* abp
->ab_busycnt
);
316 nabp
->ab_freecnt
= 0x1e0 / sz
- nabp
->ab_busycnt
;
325 * Allocate len blocks and concatenate them to file.
326 * If we hadn't found contignous run of len blocks, concatenate
327 * as much as we can, and return.
331 hpfs_addextent(struct hpfsmount
*hpmp
, struct hpfsnode
*hp
, u_long len
)
340 * We don't know for now start lsn of block
344 al
.al_off
= (hp
->h_fn
.fn_size
+ DEV_BSIZE
- 1) >> DEV_BSHIFT
;
346 rabp
= &hp
->h_fn
.fn_ab
;
348 /* Init AlBlk if this is first extent */
349 if (al
.al_off
== 0) {
353 dprintf(("hpfs_addextent: init AlBlk in root\n"));
355 rabp
->ab_busycnt
= 0;
356 rabp
->ab_freecnt
= 0x8;
357 rabp
->ab_freeoff
= sizeof(alblk_t
);
360 error
= hpfs_bmlookup (hpmp
, 0, hp
->h_no
+ 1, al
.al_len
, &nlsn
, &nlen
);
364 error
= hpfs_bmmarkbusy(hpmp
, nlsn
, nlen
);
368 dprintf(("hpfs_addextent: new: 0x%x 0x%lx, ", nlsn
, nlen
));
370 AL_SET(AB_FREEALP(rabp
), al
.al_off
, nlen
, nlsn
);
378 dprintf(("hpfs_addextent: AlBlk: [0x%x, 0x%x, 0x%x] need: 0x%x\n",
379 rabp
->ab_freecnt
, rabp
->ab_busycnt
, rabp
->ab_flag
, al
.al_len
));
381 while ((al
.al_len
) && (rabp
->ab_freecnt
> 0)) {
382 if (rabp
->ab_flag
& AB_NODES
) {
385 * This is level containing AlNodes, so try to
386 * insert recursively into last entry.
388 anp
= AB_LASTANP(rabp
);
389 dprintf(("hpfs_addextent: AlNode: [0x%x,0x%x] \n",
390 anp
->an_nextoff
,anp
->an_lsn
));
395 error
= hpfs_addextentr (hpmp
, anp
->an_lsn
, &al
, ranp
, &pf
);
397 kprintf("hpfs_addextent: FAILED %d\n",error
);
403 dprintf(("hpfs_addextent: successful (split)\n"));
405 * Then hpfs_addextentr has split tree below, now
406 * we need to fix this level. Particulary:
407 * fix last AlNode and add another one.
410 bcopy(ranp
, AB_LASTANP(rabp
), sizeof(alnode_t
) * 2);
416 dprintf(("hpfs_addextent: successful\n"));
422 alp
= AB_LASTALP(rabp
);
423 dprintf(("hpfs_addextent: AlLeaf: [0x%x,0x%x,0x%x] \n",
424 alp
->al_off
,alp
->al_len
,alp
->al_lsn
));
426 /* Check if we trying to add in right place */
427 if (alp
->al_off
+ alp
->al_len
== al
.al_off
) {
432 * Search bitmap for block begining from
433 * alp->al_lsn + alp->al_len and long of ralp->al_len
435 error
= hpfs_bmlookup (hpmp
, 0,
436 alp
->al_lsn
+ alp
->al_len
, al
.al_len
, &nlsn
, &nlen
);
440 error
= hpfs_bmmarkbusy(hpmp
, nlsn
, nlen
);
444 dprintf(("hpfs_addextent: new: 0x%x 0x%lx, ", nlsn
, nlen
));
446 if (alp
->al_lsn
+ alp
->al_len
== nlsn
) {
447 dprintf(("extended existed leaf\n"));
451 dprintf(("created new leaf\n"));
452 AL_SET(AB_FREEALP(rabp
), al
.al_off
, nlen
, nlsn
);
458 kprintf("hpfs_addextent: INTERNAL INCONSISTENCE\n");
465 * Move AlBlk contain to new AlSec (it will fit more
466 * entries) if overflowed (no more free entries).
468 if (rabp
->ab_freecnt
<= 0) {
472 dprintf(("hpfs_addextent: overflow, convt\n"));
475 * Convert AlBlk to new AlSec, it will set
478 rabp
->ab_flag
|= AB_FNPARENT
;
479 error
= hpfs_alblk2alsec (hpmp
, rabp
, &nrasp
, &nbp
);
481 kprintf("hpfs_addextent: CAN'T CONVT\n");
484 nrasp
->as_parent
= hp
->h_no
;
487 * Scan all childrens (if exist), set new parent and
488 * clean their AB_FNPARENT flag.
490 if (rabp
->ab_flag
& AB_NODES
) {
496 anp
= AB_ALNODE(rabp
);
497 for (i
=0; i
<rabp
->ab_busycnt
; i
++) {
498 error
= hpfs_breadalsec(hpmp
, anp
->an_lsn
, &bp
);
502 asp
= (alsec_t
*)bp
->b_data
;
503 asp
->as_ab
.ab_flag
&= ~AB_FNPARENT
;
504 asp
->as_parent
= nrasp
->as_self
;
511 /* Convert AlBlk to contain AlNodes */
512 rabp
->ab_flag
= AB_NODES
;
513 rabp
->ab_busycnt
= 0;
514 rabp
->ab_freecnt
= 0xC;
515 rabp
->ab_freeoff
= sizeof(alblk_t
);
517 /* Add AlNode for new allocated AlSec */
518 AN_SET(AB_FREEANP(rabp
), ~0, nrasp
->as_self
);
525 dprintf(("hpfs_addextent: root retry\n"));
533 * Descent down to the end of tree, then search for
534 * ralp->len contignous run begining from last run's end and
535 * concatenate new block! If we can't find one, then...
539 * rlsn: LSN containing AlSec
540 * ralp: AlLeaf to insert
541 * ranp: New AlNodes' values
542 * resp: Mix returning info
545 hpfs_addextentr(struct hpfsmount
*hpmp
, lsn_t rlsn
, alleaf_t
*ralp
,
546 alnode_t
*ranp
, u_long
*resp
)
559 dprintf(("hpfs_addextentr: AlSec at 0x%x\n", rlsn
));
561 error
= hpfs_breadalsec(hpmp
, rlsn
, &rbp
);
565 rasp
= (alsec_t
*)rbp
->b_data
;
569 dprintf(("hpfs_addextentr: AlBlk: [0x%x, 0x%x, 0x%x]\n",
570 rabp
->ab_freecnt
, rabp
->ab_busycnt
, rabp
->ab_flag
));
572 while ((ralp
->al_len
) && (rabp
->ab_freecnt
> 0)) {
573 if (rabp
->ab_flag
& AB_NODES
) {
575 * This is level containing AlNodes, so try to
576 * insert recursively into last entry.
578 anp
= AB_LASTANP(rabp
);
579 dprintf(("hpfs_addextentr: AlNode: [0x%x,0x%x] \n",
580 anp
->an_nextoff
,anp
->an_lsn
));
585 error
= hpfs_addextentr (hpmp
, anp
->an_lsn
, ralp
, ranp
, &pf
);
587 kprintf("hpfs_addextentr: FAILED %d\n",error
);
593 dprintf(("hpfs_addextentr: successful (split)\n"));
595 * Then hpfs_addextentr has split tree below, now
596 * we need to fix this level. Particulary:
597 * fix last AlNode and add another one.
599 bcopy(ranp
, AB_LASTANP(rabp
), sizeof(alnode_t
) * 2);
606 dprintf(("hpfs_addextentr: successful\n"));
610 alp
= AB_LASTALP(rabp
);
611 dprintf(("hpfs_addextentr: AlLeaf: [0x%x,0x%x,0x%x] \n",
612 alp
->al_off
,alp
->al_len
,alp
->al_lsn
));
614 /* Check if we trying to add in right place */
615 if (alp
->al_off
+ alp
->al_len
== ralp
->al_off
) {
619 * Search bitmap for block begining from
620 * alp->al_lsn + alp->al_len and long of ralp->al_len
622 error
= hpfs_bmlookup (hpmp
, 0,
623 alp
->al_lsn
+ alp
->al_len
, ralp
->al_len
, &nlsn
, &nlen
);
627 error
= hpfs_bmmarkbusy(hpmp
, nlsn
, nlen
);
631 dprintf(("hpfs_addextentr: new: 0x%x 0x%lx, ", nlsn
, nlen
));
634 * If ending of existed entry fits the
635 * begining of the extent being added,
636 * then we add concatenate two extents.
638 if (alp
->al_lsn
+ alp
->al_len
== nlsn
) {
639 dprintf(("concat\n"));
642 dprintf(("created new leaf\n"));
643 AL_SET(AB_FREEALP(rabp
), ralp
->al_off
, nlen
, nlsn
);
647 ralp
->al_len
-= nlen
;
648 ralp
->al_off
+= nlen
;
650 kprintf("hpfs_addextentr: INTERNAL INCONSISTENCE\n");
658 * Split AlBlk if overflowed.
660 if (rabp
->ab_freecnt
<= 0) {
664 dprintf(("hpfs_addextentr: overflow, split\n"));
666 error
= hpfs_splitalsec (hpmp
, rasp
, &nrasp
, &nbp
);
668 kprintf("hpfs_addextent: CAN'T SPLIT\n");
672 if (rabp
->ab_flag
& AB_NODES
) {
679 AB_LASTANP(&rasp
->as_ab
)->an_nextoff
;
681 /* We need to set left subtree's last entry
682 * offset to 0xFFFFFFFF for OS/2 to be able
683 * to read our files. It treats absence of
684 * 0xFFFFFFFF as error.
686 AB_LASTANP(&rasp
->as_ab
)->an_nextoff
= ~0;
688 /* We need to fix new allocated AlSec's
689 * children, becouse their parent has changed.
691 anp
= AB_ALNODE(&nrasp
->as_ab
);
692 for (i
=0; i
<nrasp
->as_ab
.ab_busycnt
; i
++) {
693 error
= hpfs_breadalsec(hpmp
, anp
->an_lsn
, &bp
);
699 asp
= (alsec_t
*)bp
->b_data
;
700 asp
->as_parent
= nrasp
->as_self
;
707 AB_ALLEAF(&nrasp
->as_ab
)->al_off
;
710 ranp
[0].an_lsn
= rasp
->as_self
;
711 ranp
[1].an_nextoff
= ~0;
712 ranp
[1].an_lsn
= nrasp
->as_self
;
734 * Recursive routine walking down the b-tree and deallocating all
735 * extents above bn. Returns *resp != 0 if alblk was totally
736 * deallocated and may be freed. Tries to keep b-tree.
738 * (XXXX) NOTE! THIS ROUTINE WILL NEVER DECREMENT DEPTH OF
742 hpfs_truncatealblk(struct hpfsmount
*hpmp
, alblk_t
*abp
, lsn_t bn
, int *resp
)
750 dprintf(("hpfs_truncatealblk: AlBlk: [0x%x,0x%x, 0x%x]\n",
751 abp
->ab_freecnt
, abp
->ab_busycnt
, abp
->ab_flag
));
753 if (abp
->ab_flag
& AB_NODES
) {
755 * Scan array of AlNodes backward,
756 * diving in recursion if needed
758 anp
= AB_LASTANP(abp
);
760 while (abp
->ab_busycnt
&& (bn
<= anp
->an_nextoff
)) {
761 dprintf(("hpfs_truncatealblk: AlNode: [0x%x,0x%x] \n",
762 anp
->an_nextoff
,anp
->an_lsn
));
764 error
= hpfs_breadalsec(hpmp
, anp
->an_lsn
, &bp
);
768 asp
= (alsec_t
*)bp
->b_data
;
770 error
= hpfs_truncatealblk (hpmp
,
771 &asp
->as_ab
, bn
, resp
);
780 error
= hpfs_bmmarkfree(hpmp
,
789 * We have deallocated some entries, some space
790 * migth been freed, then try to concat two
793 anp
->an_nextoff
= ~0;
794 if (abp
->ab_busycnt
>= 2) {
798 error
= hpfs_breadalsec(hpmp
,
799 (anp
-1)->an_lsn
, &b0p
);
803 as0p
= (alsec_t
*)b0p
->b_data
;
804 error
= hpfs_concatalsec(hpmp
,
806 if (error
== ENOSPC
) {
807 /* Not enought space */
810 } else if (error
== 0) {
812 (anp
-1)->an_nextoff
= anp
->an_nextoff
;
817 error
= hpfs_bmmarkfree(hpmp
,
830 /* Nowhere to concatenate */
834 /* There can not be any more entries
835 * over greater bn, becouse last AlSec
836 * wasn't freed totally. So go out.
842 if (abp
->ab_busycnt
== 0)
848 * Scan array of AlLeafs backward,
851 alp
= AB_LASTALP(abp
);
853 while (abp
->ab_busycnt
&& (bn
< alp
->al_off
+ alp
->al_len
)){
854 dprintf(("hpfs_truncatealblk: AlLeaf: [0x%x,0x%x,0x%x] \n",
855 alp
->al_off
,alp
->al_len
,alp
->al_lsn
));
857 if (bn
<= alp
->al_off
) {
858 error
= hpfs_bmmarkfree(hpmp
, alp
->al_lsn
,
865 } else if ((bn
> alp
->al_off
) &&
866 (bn
< alp
->al_off
+ alp
->al_len
)){
867 error
= hpfs_bmmarkfree(hpmp
,
868 alp
->al_lsn
+ bn
- alp
->al_off
,
869 alp
->al_len
- bn
+ alp
->al_off
);
873 alp
->al_len
= bn
- alp
->al_off
;
881 /* Signal parent deallocation, if need */
882 if (abp
->ab_busycnt
== 0)