1/* fsys_xfs.c - an implementation for the SGI XFS file system */
2/*
3 *  GRUB  --  GRand Unified Bootloader
4 *  Copyright (C) 2001,2002,2004  Free Software Foundation, Inc.
5 *
6 *  This program is free software; you can redistribute it and/or modify
7 *  it under the terms of the GNU General Public License as published by
8 *  the Free Software Foundation; either version 2 of the License, or
9 *  (at your option) any later version.
10 *
11 *  This program is distributed in the hope that it will be useful,
12 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 *  GNU General Public License for more details.
15 *
16 *  You should have received a copy of the GNU General Public License
17 *  along with this program; if not, write to the Free Software
18 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
20
21#ifdef FSYS_XFS
22
23#include "shared.h"
24#include "filesys.h"
25#include "xfs.h"
26
27#define MAX_LINK_COUNT	8
28
29typedef struct xad {
30	xfs_fileoff_t offset;
31	xfs_fsblock_t start;
32	xfs_filblks_t len;
33} xad_t;
34
35struct xfs_info {
36	int bsize;
37	int dirbsize;
38	int isize;
39	unsigned int agblocks;
40	int bdlog;
41	int blklog;
42	int inopblog;
43	int agblklog;
44	int agnolog;
45	unsigned int nextents;
46	xfs_daddr_t next;
47	xfs_daddr_t daddr;
48	xfs_dablk_t forw;
49	xfs_dablk_t dablk;
50	xfs_bmbt_rec_32_t *xt;
51	xfs_bmbt_ptr_t ptr0;
52	int btnode_ptr0_off;
53	int i8param;
54	int dirpos;
55	int dirmax;
56	int blkoff;
57	int fpos;
58	xfs_ino_t rootino;
59};
60
61static struct xfs_info xfs;
62
63#define dirbuf		((char *)FSYS_BUF)
64#define filebuf		((char *)FSYS_BUF + 4096)
65#define inode		((xfs_dinode_t *)((char *)FSYS_BUF + 8192))
66#define icore		(inode->di_core)
67
68#define	mask32lo(n)	(((xfs_uint32_t)1 << (n)) - 1)
69
70#define	XFS_INO_MASK(k)		((xfs_uint32_t)((1ULL << (k)) - 1))
71#define	XFS_INO_OFFSET_BITS	xfs.inopblog
72#define	XFS_INO_AGBNO_BITS	xfs.agblklog
73#define	XFS_INO_AGINO_BITS	(xfs.agblklog + xfs.inopblog)
74#define	XFS_INO_AGNO_BITS	xfs.agnolog
75
76static inline xfs_agblock_t
77agino2agbno (xfs_agino_t agino)
78{
79	return agino >> XFS_INO_OFFSET_BITS;
80}
81
82static inline xfs_agnumber_t
83ino2agno (xfs_ino_t ino)
84{
85	return ino >> XFS_INO_AGINO_BITS;
86}
87
88static inline xfs_agino_t
89ino2agino (xfs_ino_t ino)
90{
91	return ino & XFS_INO_MASK(XFS_INO_AGINO_BITS);
92}
93
94static inline int
95ino2offset (xfs_ino_t ino)
96{
97	return ino & XFS_INO_MASK(XFS_INO_OFFSET_BITS);
98}
99
100static inline __const__ xfs_uint16_t
101le16 (xfs_uint16_t x)
102{
103	__asm__("xchgb %b0,%h0"	\
104		: "=q" (x) \
105		:  "0" (x)); \
106		return x;
107}
108
109static inline __const__ xfs_uint32_t
110le32 (xfs_uint32_t x)
111{
112#if 0
113        /* 386 doesn't have bswap.  */
114	__asm__("bswap %0" : "=r" (x) : "0" (x));
115#else
116	/* This is slower but this works on all x86 architectures.  */
117	__asm__("xchgb %b0, %h0" \
118		"\n\troll $16, %0" \
119		"\n\txchgb %b0, %h0" \
120		: "=q" (x) : "0" (x));
121#endif
122	return x;
123}
124
125static inline __const__ xfs_uint64_t
126le64 (xfs_uint64_t x)
127{
128	xfs_uint32_t h = x >> 32;
129        xfs_uint32_t l = x & ((1ULL<<32)-1);
130        return (((xfs_uint64_t)le32(l)) << 32) | ((xfs_uint64_t)(le32(h)));
131}
132
133
134static xfs_fsblock_t
135xt_start (xfs_bmbt_rec_32_t *r)
136{
137	return (((xfs_fsblock_t)(le32 (r->l1) & mask32lo(9))) << 43) |
138	       (((xfs_fsblock_t)le32 (r->l2)) << 11) |
139	       (((xfs_fsblock_t)le32 (r->l3)) >> 21);
140}
141
142static xfs_fileoff_t
143xt_offset (xfs_bmbt_rec_32_t *r)
144{
145	return (((xfs_fileoff_t)le32 (r->l0) &
146		mask32lo(31)) << 23) |
147		(((xfs_fileoff_t)le32 (r->l1)) >> 9);
148}
149
150static xfs_filblks_t
151xt_len (xfs_bmbt_rec_32_t *r)
152{
153	return le32(r->l3) & mask32lo(21);
154}
155
156static inline int
157xfs_highbit32(xfs_uint32_t v)
158{
159	int i;
160
161	if (--v) {
162		for (i = 0; i < 31; i++, v >>= 1) {
163			if (v == 0)
164				return i;
165		}
166	}
167	return 0;
168}
169
170static int
171isinxt (xfs_fileoff_t key, xfs_fileoff_t offset, xfs_filblks_t len)
172{
173	return (key >= offset) ? (key < offset + len ? 1 : 0) : 0;
174}
175
176static xfs_daddr_t
177agb2daddr (xfs_agnumber_t agno, xfs_agblock_t agbno)
178{
179	return ((xfs_fsblock_t)agno*xfs.agblocks + agbno) << xfs.bdlog;
180}
181
182static xfs_daddr_t
183fsb2daddr (xfs_fsblock_t fsbno)
184{
185	return agb2daddr ((xfs_agnumber_t)(fsbno >> xfs.agblklog),
186			 (xfs_agblock_t)(fsbno & mask32lo(xfs.agblklog)));
187}
188
189#undef offsetof
190#define offsetof(t,m)	((int)&(((t *)0)->m))
191
192static inline int
193btroot_maxrecs (void)
194{
195	int tmp = icore.di_forkoff ? (icore.di_forkoff << 3) : xfs.isize;
196
197	return (tmp - sizeof(xfs_bmdr_block_t) - offsetof(xfs_dinode_t, di_u)) /
198		(sizeof (xfs_bmbt_key_t) + sizeof (xfs_bmbt_ptr_t));
199}
200
201static int
202di_read (xfs_ino_t ino)
203{
204	xfs_agino_t agino;
205	xfs_agnumber_t agno;
206	xfs_agblock_t agbno;
207	xfs_daddr_t daddr;
208	int offset;
209
210	agno = ino2agno (ino);
211	agino = ino2agino (ino);
212	agbno = agino2agbno (agino);
213	offset = ino2offset (ino);
214	daddr = agb2daddr (agno, agbno);
215
216	devread (daddr, offset*xfs.isize, xfs.isize, (char *)inode);
217
218	xfs.ptr0 = *(xfs_bmbt_ptr_t *)
219		    (inode->di_u.di_c + sizeof(xfs_bmdr_block_t)
220		    + btroot_maxrecs ()*sizeof(xfs_bmbt_key_t));
221
222	return 1;
223}
224
225static void
226init_extents (void)
227{
228	xfs_bmbt_ptr_t ptr0;
229	xfs_btree_lblock_t h;
230
231	switch (icore.di_format) {
232	case XFS_DINODE_FMT_EXTENTS:
233		xfs.xt = inode->di_u.di_bmx;
234		xfs.nextents = le32 (icore.di_nextents);
235		break;
236	case XFS_DINODE_FMT_BTREE:
237		ptr0 = xfs.ptr0;
238		for (;;) {
239			xfs.daddr = fsb2daddr (le64(ptr0));
240			devread (xfs.daddr, 0,
241				 sizeof(xfs_btree_lblock_t), (char *)&h);
242			if (!h.bb_level) {
243				xfs.nextents = le16(h.bb_numrecs);
244				xfs.next = fsb2daddr (le64(h.bb_rightsib));
245				xfs.fpos = sizeof(xfs_btree_block_t);
246				return;
247			}
248			devread (xfs.daddr, xfs.btnode_ptr0_off,
249				 sizeof(xfs_bmbt_ptr_t), (char *)&ptr0);
250		}
251	}
252}
253
254static xad_t *
255next_extent (void)
256{
257	static xad_t xad;
258
259	switch (icore.di_format) {
260	case XFS_DINODE_FMT_EXTENTS:
261		if (xfs.nextents == 0)
262			return NULL;
263		break;
264	case XFS_DINODE_FMT_BTREE:
265		if (xfs.nextents == 0) {
266			xfs_btree_lblock_t h;
267			if (xfs.next == 0)
268				return NULL;
269			xfs.daddr = xfs.next;
270			devread (xfs.daddr, 0, sizeof(xfs_btree_lblock_t), (char *)&h);
271			xfs.nextents = le16(h.bb_numrecs);
272			xfs.next = fsb2daddr (le64(h.bb_rightsib));
273			xfs.fpos = sizeof(xfs_btree_block_t);
274		}
275		/* Yeah, I know that's slow, but I really don't care */
276		devread (xfs.daddr, xfs.fpos, sizeof(xfs_bmbt_rec_t), filebuf);
277		xfs.xt = (xfs_bmbt_rec_32_t *)filebuf;
278		xfs.fpos += sizeof(xfs_bmbt_rec_32_t);
279	}
280	xad.offset = xt_offset (xfs.xt);
281	xad.start = xt_start (xfs.xt);
282	xad.len = xt_len (xfs.xt);
283	++xfs.xt;
284	--xfs.nextents;
285
286	return &xad;
287}
288
289/*
290 * Name lies - the function reads only first 100 bytes
291 */
292static void
293xfs_dabread (void)
294{
295	xad_t *xad;
296	xfs_fileoff_t offset;;
297
298	init_extents ();
299	while ((xad = next_extent ())) {
300		offset = xad->offset;
301		if (isinxt (xfs.dablk, offset, xad->len)) {
302			devread (fsb2daddr (xad->start + xfs.dablk - offset),
303				 0, 100, dirbuf);
304			break;
305		}
306	}
307}
308
309static inline xfs_ino_t
310sf_ino (char *sfe, int namelen)
311{
312	void *p = sfe + namelen + 3;
313
314	return (xfs.i8param == 0)
315		? le64(*(xfs_ino_t *)p) : le32(*(xfs_uint32_t *)p);
316}
317
318static inline xfs_ino_t
319sf_parent_ino (void)
320{
321	return (xfs.i8param == 0)
322		? le64(*(xfs_ino_t *)(&inode->di_u.di_dir2sf.hdr.parent))
323		: le32(*(xfs_uint32_t *)(&inode->di_u.di_dir2sf.hdr.parent));
324}
325
326static inline int
327roundup8 (int n)
328{
329	return ((n+7)&~7);
330}
331
332static char *
333next_dentry (xfs_ino_t *ino)
334{
335	int namelen = 1;
336	int toread;
337	static char usual[2][3] = {".", ".."};
338	static xfs_dir2_sf_entry_t *sfe;
339	char *name = usual[0];
340
341	if (xfs.dirpos >= xfs.dirmax) {
342		if (xfs.forw == 0)
343			return NULL;
344		xfs.dablk = xfs.forw;
345		xfs_dabread ();
346#define h	((xfs_dir2_leaf_hdr_t *)dirbuf)
347		xfs.dirmax = le16 (h->count) - le16 (h->stale);
348		xfs.forw = le32 (h->info.forw);
349#undef h
350		xfs.dirpos = 0;
351	}
352
353	switch (icore.di_format) {
354	case XFS_DINODE_FMT_LOCAL:
355		switch (xfs.dirpos) {
356		case -2:
357			*ino = 0;
358			break;
359		case -1:
360			*ino = sf_parent_ino ();
361			++name;
362			++namelen;
363			sfe = (xfs_dir2_sf_entry_t *)
364				(inode->di_u.di_c
365				 + sizeof(xfs_dir2_sf_hdr_t)
366				 - xfs.i8param);
367			break;
368		default:
369			namelen = sfe->namelen;
370			*ino = sf_ino ((char *)sfe, namelen);
371			name = sfe->name;
372			sfe = (xfs_dir2_sf_entry_t *)
373				  ((char *)sfe + namelen + 11 - xfs.i8param);
374		}
375		break;
376	case XFS_DINODE_FMT_BTREE:
377	case XFS_DINODE_FMT_EXTENTS:
378#define dau	((xfs_dir2_data_union_t *)dirbuf)
379		for (;;) {
380			if (xfs.blkoff >= xfs.dirbsize) {
381				xfs.blkoff = sizeof(xfs_dir2_data_hdr_t);
382				filepos &= ~(xfs.dirbsize - 1);
383				filepos |= xfs.blkoff;
384			}
385			xfs_read (dirbuf, 4);
386			xfs.blkoff += 4;
387			if (dau->unused.freetag == XFS_DIR2_DATA_FREE_TAG) {
388				toread = roundup8 (le16(dau->unused.length)) - 4;
389				xfs.blkoff += toread;
390				filepos += toread;
391				continue;
392			}
393			break;
394		}
395		xfs_read ((char *)dirbuf + 4, 5);
396		*ino = le64 (dau->entry.inumber);
397		namelen = dau->entry.namelen;
398#undef dau
399		toread = roundup8 (namelen + 11) - 9;
400		xfs_read (dirbuf, toread);
401		name = (char *)dirbuf;
402		xfs.blkoff += toread + 5;
403	}
404	++xfs.dirpos;
405	name[namelen] = 0;
406
407	return name;
408}
409
410static char *
411first_dentry (xfs_ino_t *ino)
412{
413	xfs.forw = 0;
414	switch (icore.di_format) {
415	case XFS_DINODE_FMT_LOCAL:
416		xfs.dirmax = inode->di_u.di_dir2sf.hdr.count;
417		xfs.i8param = inode->di_u.di_dir2sf.hdr.i8count ? 0 : 4;
418		xfs.dirpos = -2;
419		break;
420	case XFS_DINODE_FMT_EXTENTS:
421	case XFS_DINODE_FMT_BTREE:
422		filepos = 0;
423		xfs_read (dirbuf, sizeof(xfs_dir2_data_hdr_t));
424		if (((xfs_dir2_data_hdr_t *)dirbuf)->magic == le32(XFS_DIR2_BLOCK_MAGIC)) {
425#define tail		((xfs_dir2_block_tail_t *)dirbuf)
426			filepos = xfs.dirbsize - sizeof(*tail);
427			xfs_read (dirbuf, sizeof(*tail));
428			xfs.dirmax = le32 (tail->count) - le32 (tail->stale);
429#undef tail
430		} else {
431			xfs.dablk = (1ULL << 35) >> xfs.blklog;
432#define h		((xfs_dir2_leaf_hdr_t *)dirbuf)
433#define n		((xfs_da_intnode_t *)dirbuf)
434			for (;;) {
435				xfs_dabread ();
436				if ((n->hdr.info.magic == le16(XFS_DIR2_LEAFN_MAGIC))
437				    || (n->hdr.info.magic == le16(XFS_DIR2_LEAF1_MAGIC))) {
438					xfs.dirmax = le16 (h->count) - le16 (h->stale);
439					xfs.forw = le32 (h->info.forw);
440					break;
441				}
442				xfs.dablk = le32 (n->btree[0].before);
443			}
444#undef n
445#undef h
446		}
447		xfs.blkoff = sizeof(xfs_dir2_data_hdr_t);
448		filepos = xfs.blkoff;
449		xfs.dirpos = 0;
450	}
451	return next_dentry (ino);
452}
453
454int
455xfs_mount (void)
456{
457	xfs_sb_t super;
458
459	if (!devread (0, 0, sizeof(super), (char *)&super)
460	    || (le32(super.sb_magicnum) != XFS_SB_MAGIC)
461	    || ((le16(super.sb_versionnum)
462		& XFS_SB_VERSION_NUMBITS) != XFS_SB_VERSION_4) ) {
463		return 0;
464	}
465
466	xfs.bsize = le32 (super.sb_blocksize);
467	xfs.blklog = super.sb_blocklog;
468	xfs.bdlog = xfs.blklog - SECTOR_BITS;
469	xfs.rootino = le64 (super.sb_rootino);
470	xfs.isize = le16 (super.sb_inodesize);
471	xfs.agblocks = le32 (super.sb_agblocks);
472	xfs.dirbsize = xfs.bsize << super.sb_dirblklog;
473
474	xfs.inopblog = super.sb_inopblog;
475	xfs.agblklog = super.sb_agblklog;
476	xfs.agnolog = xfs_highbit32 (le32(super.sb_agcount));
477
478	xfs.btnode_ptr0_off =
479		((xfs.bsize - sizeof(xfs_btree_block_t)) /
480		(sizeof (xfs_bmbt_key_t) + sizeof (xfs_bmbt_ptr_t)))
481		 * sizeof(xfs_bmbt_key_t) + sizeof(xfs_btree_block_t);
482
483	return 1;
484}
485
486int
487xfs_read (char *buf, int len)
488{
489	xad_t *xad;
490	xfs_fileoff_t endofprev, endofcur, offset;
491	xfs_filblks_t xadlen;
492	int toread, startpos, endpos;
493
494	if (icore.di_format == XFS_DINODE_FMT_LOCAL) {
495		grub_memmove (buf, inode->di_u.di_c + filepos, len);
496		filepos += len;
497		return len;
498	}
499
500	startpos = filepos;
501	endpos = filepos + len;
502	endofprev = (xfs_fileoff_t)-1;
503	init_extents ();
504	while (len > 0 && (xad = next_extent ())) {
505		offset = xad->offset;
506		xadlen = xad->len;
507		if (isinxt (filepos >> xfs.blklog, offset, xadlen)) {
508			endofcur = (offset + xadlen) << xfs.blklog;
509			toread = (endofcur >= endpos)
510				  ? len : (endofcur - filepos);
511
512			disk_read_func = disk_read_hook;
513			devread (fsb2daddr (xad->start),
514				 filepos - (offset << xfs.blklog), toread, buf);
515			disk_read_func = NULL;
516
517			buf += toread;
518			len -= toread;
519			filepos += toread;
520		} else if (offset > endofprev) {
521			toread = ((offset << xfs.blklog) >= endpos)
522				  ? len : ((offset - endofprev) << xfs.blklog);
523			len -= toread;
524			filepos += toread;
525			for (; toread; toread--) {
526				*buf++ = 0;
527			}
528			continue;
529		}
530		endofprev = offset + xadlen;
531	}
532
533	return filepos - startpos;
534}
535
536int
537xfs_dir (char *dirname)
538{
539	xfs_ino_t ino, parent_ino, new_ino;
540	xfs_fsize_t di_size;
541	int di_mode;
542	int cmp, n, link_count;
543	char linkbuf[xfs.bsize];
544	char *rest, *name, ch;
545
546	parent_ino = ino = xfs.rootino;
547	link_count = 0;
548	for (;;) {
549		di_read (ino);
550		di_size = le64 (icore.di_size);
551		di_mode = le16 (icore.di_mode);
552
553		if ((di_mode & IFMT) == IFLNK) {
554			if (++link_count > MAX_LINK_COUNT) {
555				errnum = ERR_SYMLINK_LOOP;
556				return 0;
557			}
558			if (di_size < xfs.bsize - 1) {
559				filepos = 0;
560				filemax = di_size;
561				n = xfs_read (linkbuf, filemax);
562			} else {
563				errnum = ERR_FILELENGTH;
564				return 0;
565			}
566
567			ino = (linkbuf[0] == '/') ? xfs.rootino : parent_ino;
568			while (n < (xfs.bsize - 1) && (linkbuf[n++] = *dirname++));
569			linkbuf[n] = 0;
570			dirname = linkbuf;
571			continue;
572		}
573
574		if (!*dirname || isspace (*dirname)) {
575			if ((di_mode & IFMT) != IFREG) {
576				errnum = ERR_BAD_FILETYPE;
577				return 0;
578			}
579			filepos = 0;
580			filemax = di_size;
581			return 1;
582		}
583
584		if ((di_mode & IFMT) != IFDIR) {
585			errnum = ERR_BAD_FILETYPE;
586			return 0;
587		}
588
589		for (; *dirname == '/'; dirname++);
590
591		for (rest = dirname; (ch = *rest) && !isspace (ch) && ch != '/'; rest++);
592		*rest = 0;
593
594		name = first_dentry (&new_ino);
595		for (;;) {
596			cmp = (!*dirname) ? -1 : substring (dirname, name);
597#ifndef STAGE1_5
598			if (print_possibilities && ch != '/' && cmp <= 0) {
599				if (print_possibilities > 0)
600					print_possibilities = -print_possibilities;
601				print_a_completion (name);
602			} else
603#endif
604			if (cmp == 0) {
605				parent_ino = ino;
606				if (new_ino)
607					ino = new_ino;
608		        	*(dirname = rest) = ch;
609				break;
610			}
611			name = next_dentry (&new_ino);
612			if (name == NULL) {
613				if (print_possibilities < 0)
614					return 1;
615
616				errnum = ERR_FILE_NOT_FOUND;
617				*rest = ch;
618				return 0;
619			}
620		}
621	}
622}
623
624#endif /* FSYS_XFS */
625