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