1 /*
2  * hfsutils - tools for reading and writing Macintosh HFS volumes
3  * Copyright (C) 1996, 1997 Robert Leslie
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 2 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18  */
19 
20 # include <stdlib.h>
21 # include <string.h>
22 # include <errno.h>
23 # include <time.h>
24 
25 # include "internal.h"
26 # include "data.h"
27 # include "low.h"
28 # include "btree.h"
29 # include "record.h"
30 # include "volume.h"
31 
32 /*
33  * NAME:	vol->catsearch()
34  * DESCRIPTION:	search catalog tree
35  */
36 int v_catsearch(hfsvol *vol, long parid, char *name,
37 		CatDataRec *data, char *cname, node *np)
38 {
39   CatKeyRec key;
40   unsigned char pkey[HFS_CATKEYLEN];
41   node n;
42   unsigned char *ptr;
43   int found;
44 
45   if (np == 0)
46     np = &n;
47 
48   r_makecatkey(&key, parid, name);
49   r_packcatkey(&key, pkey, 0);
50 
51   found = bt_search(&vol->cat, pkey, np);
52   if (found <= 0)
53     return found;
54 
55   ptr = HFS_NODEREC(*np, np->rnum);
56 
57   if (cname)
58     {
59       r_unpackcatkey(ptr, &key);
60       strcpy(cname, key.ckrCName);
61     }
62 
63   if (data)
64     r_unpackcatdata(HFS_RECDATA(ptr), data);
65 
66   return 1;
67 }
68 
69 /*
70  * NAME:	vol->extsearch()
71  * DESCRIPTION:	search extents tree
72  */
73 int v_extsearch(hfsfile *file, unsigned int fabn, ExtDataRec *data, node *np)
74 {
75   ExtKeyRec key;
76   ExtDataRec extsave;
77   unsigned int fabnsave;
78   unsigned char pkey[HFS_EXTKEYLEN];
79   node n;
80   unsigned char *ptr;
81   int found;
82 
83   if (np == 0)
84     np = &n;
85 
86   r_makeextkey(&key, file->fork, file->cat.u.fil.filFlNum, fabn);
87   r_packextkey(&key, pkey, 0);
88 
89   /* in case bt_search() clobbers these */
90 
91   memcpy(&extsave, &file->ext, sizeof(ExtDataRec));
92   fabnsave = file->fabn;
93 
94   found = bt_search(&file->vol->ext, pkey, np);
95 
96   memcpy(&file->ext, &extsave, sizeof(ExtDataRec));
97   file->fabn = fabnsave;
98 
99   if (found <= 0)
100     return found;
101 
102   if (data)
103     {
104       ptr = HFS_NODEREC(*np, np->rnum);
105       r_unpackextdata(HFS_RECDATA(ptr), data);
106     }
107 
108   return 1;
109 }
110 
111 /*
112  * NAME:	vol->getthread()
113  * DESCRIPTION:	retrieve catalog thread information for a file or directory
114  */
115 int v_getthread(hfsvol *vol, long id, CatDataRec *thread, node *np, int type)
116 {
117   CatDataRec rec;
118   int found;
119 
120   if (thread == 0)
121     thread = &rec;
122 
123   found = v_catsearch(vol, id, "", thread, 0, np);
124   if (found <= 0)
125     return found;
126 
127   if (thread->cdrType != type)
128     {
129       ERROR(EIO, "bad thread record");
130       return -1;
131     }
132 
133   return 1;
134 }
135 
136 /*
137  * NAME:	vol->putcatrec()
138  * DESCRIPTION:	store catalog information
139  */
140 int v_putcatrec(CatDataRec *data, node *np)
141 {
142   unsigned char pdata[HFS_CATDATALEN], *ptr;
143   int len = 0;
144 
145   r_packcatdata(data, pdata, &len);
146 
147   ptr = HFS_NODEREC(*np, np->rnum);
148   memcpy(HFS_RECDATA(ptr), pdata, len);
149 
150   return bt_putnode(np);
151 }
152 
153 /*
154  * NAME:	vol->putextrec()
155  * DESCRIPTION:	store extent information
156  */
157 int v_putextrec(ExtDataRec *data, node *np)
158 {
159   unsigned char pdata[HFS_EXTDATALEN], *ptr;
160   int len = 0;
161 
162   r_packextdata(data, pdata, &len);
163 
164   ptr = HFS_NODEREC(*np, np->rnum);
165   memcpy(HFS_RECDATA(ptr), pdata, len);
166 
167   return bt_putnode(np);
168 }
169 
170 /*
171  * NAME:	vol->allocblocks()
172  * DESCRIPTION:	allocate a contiguous range of blocks
173  */
174 int v_allocblocks(hfsvol *vol, ExtDescriptor *blocks)
175 {
176   unsigned int request, found, foundat, start, end, pt;
177   block *vbm;
178   int wrap = 0;
179 
180   if (vol->mdb.drFreeBks == 0)
181     {
182       ERROR(ENOSPC, "volume full");
183       return -1;
184     }
185 
186   request = blocks->xdrNumABlks;
187   found   = 0;
188   foundat = 0;
189   start   = vol->mdb.drAllocPtr;
190   end     = vol->mdb.drNmAlBlks;
191   pt      = start;
192   vbm     = vol->vbm;
193 
194   if (request == 0)
195     abort();
196 
197   while (1)
198     {
199       unsigned int mark;
200 
201       /* skip blocks in use */
202 
203       while (pt < end && BMTST(vbm, pt))
204 	++pt;
205 
206       if (wrap && pt >= start)
207 	break;
208 
209       /* count blocks not in use */
210 
211       mark = pt;
212       while (pt < end && pt - mark < request && ! BMTST(vbm, pt))
213 	++pt;
214 
215       if (pt - mark > found)
216 	{
217 	  found   = pt - mark;
218 	  foundat = mark;
219 	}
220 
221       if (pt == end)
222 	pt = 0, wrap = 1;
223 
224       if (found == request)
225 	break;
226     }
227 
228   if (found == 0 || found > vol->mdb.drFreeBks)
229     {
230       ERROR(EIO, "bad volume bitmap or free block count");
231       return -1;
232     }
233 
234   blocks->xdrStABN    = foundat;
235   blocks->xdrNumABlks = found;
236 
237   vol->mdb.drAllocPtr = pt;
238   vol->mdb.drFreeBks -= found;
239 
240   for (pt = foundat; pt < foundat + found; ++pt)
241     BMSET(vbm, pt);
242 
243   vol->flags |= HFS_UPDATE_MDB | HFS_UPDATE_VBM;
244 
245   return 0;
246 }
247 
248 /*
249  * NAME:	vol->freeblocks()
250  * DESCRIPTION:	deallocate a contiguous range of blocks
251  */
252 void v_freeblocks(hfsvol *vol, ExtDescriptor *blocks)
253 {
254   unsigned int start, len, pt;
255   block *vbm;
256 
257   start = blocks->xdrStABN;
258   len   = blocks->xdrNumABlks;
259   vbm   = vol->vbm;
260 
261   vol->mdb.drFreeBks += len;
262 
263   for (pt = start; pt < start + len; ++pt)
264     BMCLR(vbm, pt);
265 
266   vol->flags |= HFS_UPDATE_MDB | HFS_UPDATE_VBM;
267 }
268 
269 /*
270  * NAME:	vol->resolve()
271  * DESCRIPTION:	translate a pathname; return catalog information
272  */
273 int v_resolve(hfsvol **vol, char *path, CatDataRec *data,
274 	      long *parid, char *fname, node *np)
275 {
276   long dirid;
277   char name[HFS_MAX_FLEN + 1], *nptr;
278   int found;
279 
280   if (*path == 0)
281     {
282       ERROR(ENOENT, "empty path");
283       return -1;
284     }
285 
286   if (parid)
287     *parid = 0;
288 
289   nptr = strchr(path, ':');
290 
291   if (*path == ':' || nptr == 0)
292     {
293       dirid = (*vol)->cwd;  /* relative path */
294 
295       if (*path == ':')
296 	++path;
297 
298       if (*path == 0)
299 	{
300 	  found = v_getdthread(*vol, dirid, data, 0);
301 	  if (found <= 0)
302 	    return found;
303 
304 	  if (parid)
305 	    *parid = data->u.dthd.thdParID;
306 
307 	  return v_catsearch(*vol, data->u.dthd.thdParID,
308 			     data->u.dthd.thdCName, data, fname, np);
309 	}
310     }
311   else
312     {
313       hfsvol *check;
314 
315       dirid = HFS_CNID_ROOTPAR;  /* absolute path */
316 
317       if (nptr - path > HFS_MAX_VLEN)
318 	{
319 	  ERROR(ENAMETOOLONG, 0);
320 	  return -1;
321 	}
322 
323       strncpy(name, path, nptr - path);
324       name[nptr - path] = 0;
325 
326       for (check = hfs_mounts; check; check = check->next)
327 	{
328 	  if (d_relstring(check->mdb.drVN, name) == 0)
329 	    {
330 	      *vol = check;
331 	      break;
332 	    }
333 	}
334     }
335 
336   while (1)
337     {
338       while (*path == ':')
339 	{
340 	  ++path;
341 
342 	  found = v_getdthread(*vol, dirid, data, 0);
343 	  if (found <= 0)
344 	    return found;
345 
346 	  dirid = data->u.dthd.thdParID;
347 	}
348 
349       if (*path == 0)
350 	{
351 	  found = v_getdthread(*vol, dirid, data, 0);
352 	  if (found <= 0)
353 	    return found;
354 
355 	  if (parid)
356 	    *parid = data->u.dthd.thdParID;
357 
358 	  return v_catsearch(*vol, data->u.dthd.thdParID,
359 			     data->u.dthd.thdCName, data, fname, np);
360 	}
361 
362       nptr = name;
363       while (nptr < name + sizeof(name) - 1 && *path && *path != ':')
364 	*nptr++ = *path++;
365 
366       if (*path && *path != ':')
367 	{
368 	  ERROR(ENAMETOOLONG, 0);
369 	  return -1;
370 	}
371 
372       *nptr = 0;
373       if (*path == ':')
374 	++path;
375 
376       if (parid)
377 	*parid = dirid;
378 
379       found = v_catsearch(*vol, dirid, name, data, fname, np);
380       if (found < 0)
381 	return -1;
382 
383       if (found == 0)
384 	{
385 	  if (*path && parid)
386 	    *parid = 0;
387 
388 	  if (*path == 0 && fname)
389 	    strcpy(fname, name);
390 
391 	  return 0;
392 	}
393 
394       switch (data->cdrType)
395 	{
396 	case cdrDirRec:
397 	  if (*path == 0)
398 	    return 1;
399 
400 	  dirid = data->u.dir.dirDirID;
401 	  break;
402 
403 	case cdrFilRec:
404 	  if (*path == 0)
405 	    return 1;
406 
407 	  ERROR(ENOTDIR, "invalid pathname");
408 	  return -1;
409 
410 	default:
411 	  ERROR(EIO, "unexpected catalog record");
412 	  return -1;
413 	}
414     }
415 }
416 
417 /*
418  * NAME:	vol->destruct()
419  * DESCRIPTION:	free memory consumed by a volume descriptor
420  */
421 void v_destruct(hfsvol *vol)
422 {
423   FREE(vol->vbm);
424 
425   FREE(vol->ext.map);
426   FREE(vol->cat.map);
427 
428   FREE(vol);
429 }
430 
431 /*
432  * NAME:	vol->getvol()
433  * DESCRIPTION:	validate a volume reference
434  */
435 int v_getvol(hfsvol **vol)
436 {
437   if (*vol == 0)
438     {
439       if (hfs_curvol == 0)
440 	{
441 	  ERROR(EINVAL, "no volume is current");
442 	  return -1;
443 	}
444 
445       *vol = hfs_curvol;
446     }
447 
448   return 0;
449 }
450 
451 /*
452  * NAME:	vol->flush()
453  * DESCRIPTION:	flush all pending changes (B*-tree, MDB, VBM) to disk
454  */
455 int v_flush(hfsvol *vol, int umounting)
456 {
457   if (! (vol->flags & HFS_READONLY))
458     {
459       if ((vol->ext.flags & HFS_UPDATE_BTHDR) &&
460 	  bt_writehdr(&vol->ext) < 0)
461 	return -1;
462 
463       if ((vol->cat.flags & HFS_UPDATE_BTHDR) &&
464 	  bt_writehdr(&vol->cat) < 0)
465 	return -1;
466 
467       if ((vol->flags & HFS_UPDATE_VBM) &&
468 	  l_writevbm(vol) < 0)
469 	return -1;
470 
471       if (umounting &&
472 	  ! (vol->mdb.drAtrb & HFS_ATRB_UMOUNTED))
473 	{
474 	  vol->mdb.drAtrb |= HFS_ATRB_UMOUNTED;
475 	  vol->flags |= HFS_UPDATE_MDB;
476 	}
477 
478       if ((vol->flags & (HFS_UPDATE_MDB | HFS_UPDATE_ALTMDB)) &&
479 	  l_writemdb(vol) < 0)
480 	return -1;
481     }
482 
483   return 0;
484 }
485 
486 /*
487  * NAME:	vol->adjvalence()
488  * DESCRIPTION:	update a volume's valence counts
489  */
490 int v_adjvalence(hfsvol *vol, long parid, int isdir, int adj)
491 {
492   node n;
493   CatDataRec data;
494 
495   if (isdir)
496     vol->mdb.drDirCnt += adj;
497   else
498     vol->mdb.drFilCnt += adj;
499 
500   vol->flags |= HFS_UPDATE_MDB;
501 
502   if (parid == HFS_CNID_ROOTDIR)
503     {
504       if (isdir)
505 	vol->mdb.drNmRtDirs += adj;
506       else
507 	vol->mdb.drNmFls    += adj;
508     }
509   else if (parid == HFS_CNID_ROOTPAR)
510     return 0;
511 
512   if (v_getdthread(vol, parid, &data, 0) <= 0 ||
513       v_catsearch(vol, data.u.dthd.thdParID, data.u.dthd.thdCName,
514 		  &data, 0, &n) <= 0 ||
515       data.cdrType != cdrDirRec)
516     {
517       ERROR(EIO, "can't find parent directory");
518       return -1;
519     }
520 
521   data.u.dir.dirVal  += adj;
522   data.u.dir.dirMdDat = d_tomtime(time(0));
523 
524   return v_putcatrec(&data, &n);
525 }
526 
527 /*
528  * NAME:	vol->newfolder()
529  * DESCRIPTION:	create a new HFS folder
530  */
531 int v_newfolder(hfsvol *vol, long parid, char *name)
532 {
533   CatKeyRec key;
534   CatDataRec data;
535   long id;
536   unsigned char record[HFS_CATRECMAXLEN];
537   int i, reclen;
538 
539   if (bt_space(&vol->cat, 2) < 0)
540     return -1;
541 
542   id = vol->mdb.drNxtCNID++;
543   vol->flags |= HFS_UPDATE_MDB;
544 
545   /* create directory record */
546 
547   data.cdrType   = cdrDirRec;
548   data.cdrResrv2 = 0;
549 
550   data.u.dir.dirFlags = 0;
551   data.u.dir.dirVal   = 0;
552   data.u.dir.dirDirID = id;
553   data.u.dir.dirCrDat = d_tomtime(time(0));
554   data.u.dir.dirMdDat = data.u.dir.dirCrDat;
555   data.u.dir.dirBkDat = 0;
556 
557   memset(&data.u.dir.dirUsrInfo,  0, sizeof(data.u.dir.dirUsrInfo));
558   memset(&data.u.dir.dirFndrInfo, 0, sizeof(data.u.dir.dirFndrInfo));
559   for (i = 0; i < 4; ++i)
560     data.u.dir.dirResrv[i] = 0;
561 
562   r_makecatkey(&key, parid, name);
563   r_packcatkey(&key, record, &reclen);
564   r_packcatdata(&data, HFS_RECDATA(record), &reclen);
565 
566   if (bt_insert(&vol->cat, record, reclen) < 0)
567     return -1;
568 
569   /* create thread record */
570 
571   data.cdrType   = cdrThdRec;
572   data.cdrResrv2 = 0;
573 
574   data.u.dthd.thdResrv[0] = 0;
575   data.u.dthd.thdResrv[1] = 0;
576   data.u.dthd.thdParID    = parid;
577   strcpy(data.u.dthd.thdCName, name);
578 
579   r_makecatkey(&key, id, "");
580   r_packcatkey(&key, record, &reclen);
581   r_packcatdata(&data, HFS_RECDATA(record), &reclen);
582 
583   if (bt_insert(&vol->cat, record, reclen) < 0 ||
584       v_adjvalence(vol, parid, 1, 1) < 0)
585     return -1;
586 
587   return 0;
588 }
589 
590 /*
591  * NAME:	markexts()
592  * DESCRIPTION:	set bits from an extent record in the volume bitmap
593  */
594 static
595 void markexts(block *vbm, ExtDataRec *exts)
596 {
597   int i;
598   unsigned int start, len;
599 
600   for (i = 0; i < 3; ++i)
601     {
602       for (start = (*exts)[i].xdrStABN,
603 	     len = (*exts)[i].xdrNumABlks; len--; ++start)
604 	BMSET(vbm, start);
605     }
606 }
607 
608 /*
609  * NAME:	vol->scavenge()
610  * DESCRIPTION:	safeguard blocks in the volume bitmap
611  */
612 int v_scavenge(hfsvol *vol)
613 {
614   block *vbm = vol->vbm;
615   node n;
616   unsigned int pt, blks;
617 
618   if (vbm == 0)
619     return 0;
620 
621   markexts(vbm, &vol->mdb.drXTExtRec);
622   markexts(vbm, &vol->mdb.drCTExtRec);
623 
624   vol->flags |= HFS_UPDATE_VBM;
625 
626   /* scavenge the extents overflow file */
627 
628   n.bt   = &vol->ext;
629   n.nnum = vol->ext.hdr.bthFNode;
630 
631   if (n.nnum > 0)
632     {
633       if (bt_getnode(&n) < 0)
634 	return -1;
635 
636       n.rnum = 0;
637 
638       while (1)
639 	{
640 	  ExtDataRec data;
641 	  unsigned char *ptr;
642 
643 	  while (n.rnum >= n.nd.ndNRecs)
644 	    {
645 	      n.nnum = n.nd.ndFLink;
646 	      if (n.nnum == 0)
647 		break;
648 
649 	      if (bt_getnode(&n) < 0)
650 		return -1;
651 
652 	      n.rnum = 0;
653 	    }
654 
655 	  if (n.nnum == 0)
656 	    break;
657 
658 	  ptr = HFS_NODEREC(n, n.rnum);
659 	  r_unpackextdata(HFS_RECDATA(ptr), &data);
660 
661 	  markexts(vbm, &data);
662 
663 	  ++n.rnum;
664 	}
665     }
666 
667   /* scavenge the catalog file */
668 
669   n.bt   = &vol->cat;
670   n.nnum = vol->cat.hdr.bthFNode;
671 
672   if (n.nnum > 0)
673     {
674       if (bt_getnode(&n) < 0)
675 	return -1;
676 
677       n.rnum = 0;
678 
679       while (1)
680 	{
681 	  CatDataRec data;
682 	  unsigned char *ptr;
683 
684 	  while (n.rnum >= n.nd.ndNRecs)
685 	    {
686 	      n.nnum = n.nd.ndFLink;
687 	      if (n.nnum == 0)
688 		break;
689 
690 	      if (bt_getnode(&n) < 0)
691 		return -1;
692 
693 	      n.rnum = 0;
694 	    }
695 
696 	  if (n.nnum == 0)
697 	    break;
698 
699 	  ptr = HFS_NODEREC(n, n.rnum);
700 	  r_unpackcatdata(HFS_RECDATA(ptr), &data);
701 
702 	  if (data.cdrType == cdrFilRec)
703 	    {
704 	      markexts(vbm, &data.u.fil.filExtRec);
705 	      markexts(vbm, &data.u.fil.filRExtRec);
706 	    }
707 
708 	  ++n.rnum;
709 	}
710     }
711 
712   for (blks = 0, pt = vol->mdb.drNmAlBlks; pt--; )
713     {
714       if (! BMTST(vbm, pt))
715 	++blks;
716     }
717 
718   if (vol->mdb.drFreeBks != blks)
719     {
720       vol->mdb.drFreeBks = blks;
721       vol->flags |= HFS_UPDATE_MDB;
722     }
723 
724   return 0;
725 }
726