Per-CPU VFS Namecache Effectiveness Statistics:
[dragonfly.git] / sys / vfs / hpfs / hpfs_alsubr.c
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 }