1/*
2 * Copyright � 2007 Alistair Crooks.  All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 * 3. The name of the author may not be used to endorse or promote
13 *    products derived from this software without specific prior written
14 *    permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
17 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
22 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28#include <sys/types.h>
29#include <sys/stat.h>
30
31#define FUSE_USE_VERSION	26
32
33#include <fuse.h>
34#include <stdio.h>
35#include <stdlib.h>
36#include <unistd.h>
37
38#include "virtdir.h"
39#include "defs.h"
40
41 /* utility comparison routine for sorting and searching */
42static int
43compare(const void *vp1, const void *vp2)
44{
45	const virt_dirent_t	*tp1 = (const virt_dirent_t *) vp1;
46	const virt_dirent_t	*tp2 = (const virt_dirent_t *) vp2;
47
48	return strcmp(tp1->name, tp2->name);
49}
50
51/* save `n' chars of `s' in allocated storage */
52static char *
53strnsave(const char *s, int n)
54{
55	char	*cp;
56
57	if (n < 0) {
58		n = strlen(s);
59	}
60	NEWARRAY(char, cp, n + 1, "strnsave", return NULL);
61	(void) memcpy(cp, s, n);
62	cp[n] = 0x0;
63	return cp;
64}
65
66/* ensure intermediate directories exist */
67static void
68mkdirs(virtdir_t *tp, const char *path, size_t size)
69{
70	virt_dirent_t	*ep;
71	char		 name[MAXPATHLEN];
72	char		*slash;
73
74	(void) strlcpy(name, path, sizeof(name));
75	for (slash = name + 1 ; (slash = strchr(slash + 1, '/')) != NULL ; ) {
76		*slash = 0x0;
77		if ((ep = virtdir_find(tp, name, strlen(name))) == NULL) {
78			virtdir_add(tp, name, strlen(name), 'd', NULL, 0);
79		}
80		*slash = '/';
81	}
82}
83
84/* get rid of multiple slashes in input */
85static int
86normalise(const char *name, size_t namelen, char *path, size_t pathsize)
87{
88	const char	*np;
89	char		*pp;
90	int		 done;
91
92	for (pp = path, np = name, done = 0 ;
93	     !done && (unsigned)(pp - path) < pathsize - 1 &&
94	     (unsigned)(np - name) <= namelen ; ) {
95		switch(*np) {
96		case '/':
97			if (pp == path || *(pp - 1) != '/') {
98				*pp++ = *np;
99			}
100			np += 1;
101			break;
102		case 0x0:
103			done = 1;
104			break;
105		default:
106			*pp++ = *np++;
107			break;
108		}
109	}
110	/* XXX - trailing slash? */
111	*pp = 0x0;
112	return (int)(pp - path);
113}
114
115/* initialise the tree */
116int
117virtdir_init(virtdir_t *tp, const char *rootdir, struct stat *d, struct stat *f, struct stat *l)
118{
119	(void) memcpy(&tp->dir, d, sizeof(tp->dir));
120	tp->dir.st_mode = S_IFDIR | 0755;
121	tp->dir.st_nlink = 2;
122	(void) memcpy(&tp->file, f, sizeof(tp->file));
123	tp->file.st_mode = S_IFREG | 0644;
124	tp->file.st_nlink = 1;
125	(void) memcpy(&tp->lnk, l, sizeof(tp->lnk));
126	tp->lnk.st_mode = S_IFLNK | 0644;
127	tp->lnk.st_nlink = 1;
128	if (rootdir != NULL) {
129		tp->rootdir = strdup(rootdir);
130	}
131	return 1;
132}
133
134/* add an entry to the tree */
135int
136virtdir_add(virtdir_t *tp, const char *name, size_t size, uint8_t type, const char *tgt, size_t tgtlen)
137{
138	struct stat	st;
139	char		path[MAXPATHLEN];
140	int		pathlen;
141
142	if (tp->v == NULL) {
143		(void) stat(".", &st);
144		virtdir_init(tp, NULL, &st, &st, &st);
145	}
146	pathlen = normalise(name, size, path, sizeof(path));
147	if (virtdir_find(tp, path, pathlen) != NULL) {
148		/* attempt to add a duplicate directory entry */
149		return 0;
150	}
151	ALLOC(virt_dirent_t, tp->v, tp->size, tp->c, 10, 10, "virtdir_add",
152			return 0);
153	tp->v[tp->c].namelen = pathlen;
154	if ((tp->v[tp->c].name = strnsave(path, pathlen)) == NULL) {
155		return 0;
156	}
157	tp->v[tp->c].d_name = strrchr(tp->v[tp->c].name, '/') + 1;
158	tp->v[tp->c].type = type;
159	tp->v[tp->c].ino = (ino_t) random() & 0xfffff;
160	if (tgt != NULL) {
161		tp->v[tp->c].tgtlen = tgtlen;
162		tp->v[tp->c].tgt = strnsave(tgt, tgtlen);
163	}
164	tp->c += 1;
165	qsort(tp->v, tp->c, sizeof(tp->v[0]), compare);
166	mkdirs(tp, path, pathlen);
167	return 1;
168}
169
170/* delete an entry from the tree */
171int
172virtdir_del(virtdir_t *tp, const char *name, size_t size)
173{
174	virt_dirent_t	*ep;
175	unsigned	 i;
176
177	if ((ep = virtdir_find(tp, name, size)) == NULL) {
178		return 0;
179	}
180	i = (int)(ep - tp->v);
181	for (tp->c -= 1 ; i < tp->c ; i++) {
182		tp->v[i] = tp->v[i + 1];
183	}
184	return 1;
185}
186
187/* find an entry in the tree */
188virt_dirent_t *
189virtdir_find(virtdir_t *tp, const char *name, size_t namelen)
190{
191	virt_dirent_t	e;
192	char		path[MAXPATHLEN];
193
194	(void) memset(&e, 0x0, sizeof(e));
195	e.namelen = normalise(name, namelen, path, sizeof(path));
196	e.name = path;
197	return bsearch(&e, tp->v, tp->c, sizeof(tp->v[0]), compare);
198}
199
200/* return the virtual offset in the tree */
201int
202virtdir_offset(virtdir_t *tp, virt_dirent_t *dp)
203{
204	return (int)(dp - tp->v);
205}
206
207/* analogous to opendir(3) - open a directory, save information, and
208* return a pointer to the dynamically allocated structure */
209VIRTDIR *
210openvirtdir(virtdir_t *tp, const char *d)
211{
212	VIRTDIR	*dirp;
213
214	NEW(VIRTDIR, dirp, "openvirtdir", exit(EXIT_FAILURE));
215	dirp->dirname = strdup(d);
216	dirp->dirnamelen = strlen(d);
217	dirp->tp = tp;
218	dirp->i = 0;
219	return dirp;
220}
221
222/* analogous to readdir(3) - read the next entry in the directory that
223* was opened, and return a pointer to it */
224virt_dirent_t *
225readvirtdir(VIRTDIR *dirp)
226{
227	char	*from;
228
229	for ( ; dirp->i < dirp->tp->c ; dirp->i++) {
230		from = (strcmp(dirp->dirname, "/") == 0) ?
231			&dirp->tp->v[dirp->i].name[1] :
232			&dirp->tp->v[dirp->i].name[dirp->dirnamelen + 1];
233		if (strncmp(dirp->tp->v[dirp->i].name, dirp->dirname,
234				dirp->dirnamelen) == 0 &&
235		    *from != 0x0 &&
236		    strchr(from, '/') == NULL) {
237			return &dirp->tp->v[dirp->i++];
238		}
239	}
240	return NULL;
241}
242
243/* free the storage associated with the virtual directory structure */
244void
245closevirtdir(VIRTDIR *dirp)
246{
247	free(dirp->dirname);
248	FREE(dirp);
249}
250
251/* find a target in the tree -- not quick! */
252virt_dirent_t *
253virtdir_find_tgt(virtdir_t *tp, const char *tgt, size_t tgtlen)
254{
255	/* we don't need no stinking binary searches */
256	unsigned	i;
257	char		path[MAXPATHLEN];
258
259	(void) normalise(tgt, tgtlen, path, sizeof(path));
260	for (i = 0 ; i < tp->c ; i++) {
261		if (tp->v[i].tgt && strcmp(tp->v[i].tgt, path) == 0) {
262			return &tp->v[i];
263		}
264	}
265	return NULL;
266}
267
268/* kill all of the space allocated to the tree */
269void
270virtdir_drop(virtdir_t *tp)
271{
272	unsigned	i;
273
274	for (i = 0 ; i < tp->c ; i++) {
275		FREE(tp->v[i].name);
276		if (tp->v[i].tgt) {
277			FREE(tp->v[i].tgt);
278		}
279	}
280	FREE(tp->v);
281}
282
283/* return the value of the root directory of the tree */
284char *
285virtdir_rootdir(virtdir_t *tp)
286{
287	return tp->rootdir;
288}
289
290#ifdef VIRTDIR_DEBUG
291static void
292ptree(virtdir_t * tp)
293{
294	int	i;
295
296	for (i = 0 ; i < tp->c ; i++) {
297		printf("%s, tgt %s\n", tp->v[i].name, tp->v[i].tgt);
298	}
299}
300#endif
301
302#ifdef VIRTDIR_DEBUG
303int
304main(int argc, char **argv)
305{
306	virt_dirent_t	*tp;
307	virtdir_t		 t;
308	struct stat		 st;
309
310	(void) memset(&t, 0x0, sizeof(t));
311	stat(".", &st);
312	virtdir_add(&t, ".", 1, 'd', NULL, 0);
313	stat("..", &st);
314	virtdir_add(&t, "..", 2, 'd', NULL, 0);
315	st.st_mode = S_IFREG | 0644;
316	virtdir_add(&t, "file1", 5, 'f', NULL, 0);
317	ptree(&t);
318	virtdir_add(&t, "file2", 5, 'f', NULL, 0);
319	virtdir_add(&t, "file0", 5, 'f', NULL, 0);
320	virtdir_add(&t, "abcde", 5, 'f', NULL, 0);
321	virtdir_add(&t, "bcdef", 5, 'f', NULL, 0);
322	virtdir_add(&t, "a", 1, 'f', NULL, 0);
323	ptree(&t);
324	if ((tp = virtdir_find(&t, "a", 1)) == NULL) {
325		printf("borked2\n");
326	} else {
327		printf("a found\n");
328	}
329	virtdir_drop(&t);
330	exit(EXIT_SUCCESS);
331}
332#endif
333