101a0f853SOlivier Houchard /* $NetBSD: walk.c,v 1.24 2008/12/28 21:51:46 christos Exp $ */ 2d347a0daSSam Leffler 3d347a0daSSam Leffler /* 4d347a0daSSam Leffler * Copyright (c) 2001 Wasabi Systems, Inc. 5d347a0daSSam Leffler * All rights reserved. 6d347a0daSSam Leffler * 7d347a0daSSam Leffler * Written by Luke Mewburn for Wasabi Systems, Inc. 8d347a0daSSam Leffler * 9d347a0daSSam Leffler * Redistribution and use in source and binary forms, with or without 10d347a0daSSam Leffler * modification, are permitted provided that the following conditions 11d347a0daSSam Leffler * are met: 12d347a0daSSam Leffler * 1. Redistributions of source code must retain the above copyright 13d347a0daSSam Leffler * notice, this list of conditions and the following disclaimer. 14d347a0daSSam Leffler * 2. Redistributions in binary form must reproduce the above copyright 15d347a0daSSam Leffler * notice, this list of conditions and the following disclaimer in the 16d347a0daSSam Leffler * documentation and/or other materials provided with the distribution. 17d347a0daSSam Leffler * 3. All advertising materials mentioning features or use of this software 18d347a0daSSam Leffler * must display the following acknowledgement: 19d347a0daSSam Leffler * This product includes software developed for the NetBSD Project by 20d347a0daSSam Leffler * Wasabi Systems, Inc. 21d347a0daSSam Leffler * 4. The name of Wasabi Systems, Inc. may not be used to endorse 22d347a0daSSam Leffler * or promote products derived from this software without specific prior 23d347a0daSSam Leffler * written permission. 24d347a0daSSam Leffler * 25d347a0daSSam Leffler * THIS SOFTWARE IS PROVIDED BY WASABI SYSTEMS, INC. ``AS IS'' AND 26d347a0daSSam Leffler * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 27d347a0daSSam Leffler * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 28d347a0daSSam Leffler * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL WASABI SYSTEMS, INC 29d347a0daSSam Leffler * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 30d347a0daSSam Leffler * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 31d347a0daSSam Leffler * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 32d347a0daSSam Leffler * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 33d347a0daSSam Leffler * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 34d347a0daSSam Leffler * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 35d347a0daSSam Leffler * POSSIBILITY OF SUCH DAMAGE. 36d347a0daSSam Leffler */ 37d347a0daSSam Leffler 38d347a0daSSam Leffler 39d347a0daSSam Leffler #include <sys/cdefs.h> 40d347a0daSSam Leffler __FBSDID("$FreeBSD$"); 41d347a0daSSam Leffler 42d347a0daSSam Leffler #include <sys/param.h> 43cfa62825SEd Maste #include <sys/stat.h> 445d71efbeSMarcel Moolenaar #include <sys/time.h> 45d347a0daSSam Leffler 46d347a0daSSam Leffler #include <assert.h> 47d347a0daSSam Leffler #include <errno.h> 48d347a0daSSam Leffler #include <fcntl.h> 49d347a0daSSam Leffler #include <stdio.h> 50d347a0daSSam Leffler #include <dirent.h> 51d347a0daSSam Leffler #include <stdlib.h> 52d347a0daSSam Leffler #include <string.h> 53d347a0daSSam Leffler #include <unistd.h> 54d347a0daSSam Leffler 55d347a0daSSam Leffler #include "makefs.h" 56d347a0daSSam Leffler #include "mtree.h" 5701a0f853SOlivier Houchard #include "extern.h" 58d347a0daSSam Leffler 5901a0f853SOlivier Houchard static void apply_specdir(const char *, NODE *, fsnode *, int); 60d347a0daSSam Leffler static void apply_specentry(const char *, NODE *, fsnode *); 61688aaa09SJung-uk Kim static fsnode *create_fsnode(const char *, const char *, const char *, 62688aaa09SJung-uk Kim struct stat *); 63d347a0daSSam Leffler 64d347a0daSSam Leffler 65d347a0daSSam Leffler /* 66d347a0daSSam Leffler * walk_dir -- 67688aaa09SJung-uk Kim * build a tree of fsnodes from `root' and `dir', with a parent 68688aaa09SJung-uk Kim * fsnode of `parent' (which may be NULL for the root of the tree). 69688aaa09SJung-uk Kim * append the tree to a fsnode of `join' if it is not NULL. 70d347a0daSSam Leffler * each "level" is a directory, with the "." entry guaranteed to be 71d347a0daSSam Leffler * at the start of the list, and without ".." entries. 72d347a0daSSam Leffler */ 73d347a0daSSam Leffler fsnode * 74688aaa09SJung-uk Kim walk_dir(const char *root, const char *dir, fsnode *parent, fsnode *join) 75d347a0daSSam Leffler { 76688aaa09SJung-uk Kim fsnode *first, *cur, *prev, *last; 77d347a0daSSam Leffler DIR *dirp; 78d347a0daSSam Leffler struct dirent *dent; 79d347a0daSSam Leffler char path[MAXPATHLEN + 1]; 80d347a0daSSam Leffler struct stat stbuf; 81688aaa09SJung-uk Kim char *name, *rp; 82688aaa09SJung-uk Kim int dot, len; 83d347a0daSSam Leffler 84688aaa09SJung-uk Kim assert(root != NULL); 85d347a0daSSam Leffler assert(dir != NULL); 86d347a0daSSam Leffler 87688aaa09SJung-uk Kim len = snprintf(path, sizeof(path), "%s/%s", root, dir); 88688aaa09SJung-uk Kim if (len >= (int)sizeof(path)) 89688aaa09SJung-uk Kim errx(1, "Pathname too long."); 90d347a0daSSam Leffler if (debug & DEBUG_WALK_DIR) 91688aaa09SJung-uk Kim printf("walk_dir: %s %p\n", path, parent); 92688aaa09SJung-uk Kim if ((dirp = opendir(path)) == NULL) 93688aaa09SJung-uk Kim err(1, "Can't opendir `%s'", path); 94688aaa09SJung-uk Kim rp = path + strlen(root) + 1; 95688aaa09SJung-uk Kim if (join != NULL) { 96688aaa09SJung-uk Kim first = cur = join; 97688aaa09SJung-uk Kim while (cur->next != NULL) 98688aaa09SJung-uk Kim cur = cur->next; 99688aaa09SJung-uk Kim prev = cur; 100688aaa09SJung-uk Kim } else 101d347a0daSSam Leffler first = prev = NULL; 102688aaa09SJung-uk Kim last = prev; 103d347a0daSSam Leffler while ((dent = readdir(dirp)) != NULL) { 104688aaa09SJung-uk Kim name = dent->d_name; 105688aaa09SJung-uk Kim dot = 0; 106688aaa09SJung-uk Kim if (name[0] == '.') 107688aaa09SJung-uk Kim switch (name[1]) { 108688aaa09SJung-uk Kim case '\0': /* "." */ 109688aaa09SJung-uk Kim if (join != NULL) 110d347a0daSSam Leffler continue; 111688aaa09SJung-uk Kim dot = 1; 112688aaa09SJung-uk Kim break; 113688aaa09SJung-uk Kim case '.': /* ".." */ 114688aaa09SJung-uk Kim if (name[2] == '\0') 115688aaa09SJung-uk Kim continue; 116688aaa09SJung-uk Kim /* FALLTHROUGH */ 117688aaa09SJung-uk Kim default: 118688aaa09SJung-uk Kim dot = 0; 119688aaa09SJung-uk Kim } 120d347a0daSSam Leffler if (debug & DEBUG_WALK_DIR_NODE) 121688aaa09SJung-uk Kim printf("scanning %s/%s/%s\n", root, dir, name); 122688aaa09SJung-uk Kim if (snprintf(path + len, sizeof(path) - len, "/%s", name) >= 123688aaa09SJung-uk Kim (int)sizeof(path) - len) 124d347a0daSSam Leffler errx(1, "Pathname too long."); 125d347a0daSSam Leffler if (lstat(path, &stbuf) == -1) 126d347a0daSSam Leffler err(1, "Can't lstat `%s'", path); 127d347a0daSSam Leffler #ifdef S_ISSOCK 128d347a0daSSam Leffler if (S_ISSOCK(stbuf.st_mode & S_IFMT)) { 129d347a0daSSam Leffler if (debug & DEBUG_WALK_DIR_NODE) 130d347a0daSSam Leffler printf(" skipping socket %s\n", path); 131d347a0daSSam Leffler continue; 132d347a0daSSam Leffler } 133d347a0daSSam Leffler #endif 134d347a0daSSam Leffler 135688aaa09SJung-uk Kim if (join != NULL) { 136688aaa09SJung-uk Kim cur = join->next; 137688aaa09SJung-uk Kim for (;;) { 138688aaa09SJung-uk Kim if (cur == NULL || strcmp(cur->name, name) == 0) 139688aaa09SJung-uk Kim break; 140688aaa09SJung-uk Kim if (cur == last) { 141688aaa09SJung-uk Kim cur = NULL; 142688aaa09SJung-uk Kim break; 143688aaa09SJung-uk Kim } 144688aaa09SJung-uk Kim cur = cur->next; 145688aaa09SJung-uk Kim } 146688aaa09SJung-uk Kim if (cur != NULL) { 147688aaa09SJung-uk Kim if (S_ISDIR(cur->type) && 148688aaa09SJung-uk Kim S_ISDIR(stbuf.st_mode)) { 149688aaa09SJung-uk Kim if (debug & DEBUG_WALK_DIR_NODE) 150688aaa09SJung-uk Kim printf("merging %s with %p\n", 151688aaa09SJung-uk Kim path, cur->child); 152688aaa09SJung-uk Kim cur->child = walk_dir(root, rp, cur, 153688aaa09SJung-uk Kim cur->child); 154688aaa09SJung-uk Kim continue; 155688aaa09SJung-uk Kim } 156688aaa09SJung-uk Kim errx(1, "Can't merge %s `%s' with existing %s", 157688aaa09SJung-uk Kim inode_type(stbuf.st_mode), path, 158688aaa09SJung-uk Kim inode_type(cur->type)); 159688aaa09SJung-uk Kim } 160688aaa09SJung-uk Kim } 161688aaa09SJung-uk Kim 162688aaa09SJung-uk Kim cur = create_fsnode(root, dir, name, &stbuf); 163d347a0daSSam Leffler cur->parent = parent; 164688aaa09SJung-uk Kim if (dot) { 165d347a0daSSam Leffler /* ensure "." is at the start of the list */ 166d347a0daSSam Leffler cur->next = first; 167d347a0daSSam Leffler first = cur; 168d347a0daSSam Leffler if (! prev) 169d347a0daSSam Leffler prev = cur; 170688aaa09SJung-uk Kim cur->first = first; 171d347a0daSSam Leffler } else { /* not "." */ 172d347a0daSSam Leffler if (prev) 173d347a0daSSam Leffler prev->next = cur; 174d347a0daSSam Leffler prev = cur; 175d347a0daSSam Leffler if (!first) 176d347a0daSSam Leffler first = cur; 177688aaa09SJung-uk Kim cur->first = first; 178d347a0daSSam Leffler if (S_ISDIR(cur->type)) { 179688aaa09SJung-uk Kim cur->child = walk_dir(root, rp, cur, NULL); 180d347a0daSSam Leffler continue; 181d347a0daSSam Leffler } 182d347a0daSSam Leffler } 183d347a0daSSam Leffler if (stbuf.st_nlink > 1) { 184d347a0daSSam Leffler fsinode *curino; 185d347a0daSSam Leffler 186d347a0daSSam Leffler curino = link_check(cur->inode); 187d347a0daSSam Leffler if (curino != NULL) { 188d347a0daSSam Leffler free(cur->inode); 189d347a0daSSam Leffler cur->inode = curino; 190d347a0daSSam Leffler cur->inode->nlink++; 19101a0f853SOlivier Houchard if (debug & DEBUG_WALK_DIR_LINKCHECK) 19201a0f853SOlivier Houchard printf("link_check: found [%llu, %llu]\n", 19301a0f853SOlivier Houchard (unsigned long long)curino->st.st_dev, 19401a0f853SOlivier Houchard (unsigned long long)curino->st.st_ino); 195d347a0daSSam Leffler } 196d347a0daSSam Leffler } 197d347a0daSSam Leffler if (S_ISLNK(cur->type)) { 198d347a0daSSam Leffler char slink[PATH_MAX+1]; 199d347a0daSSam Leffler int llen; 200d347a0daSSam Leffler 201d347a0daSSam Leffler llen = readlink(path, slink, sizeof(slink) - 1); 202d347a0daSSam Leffler if (llen == -1) 203d347a0daSSam Leffler err(1, "Readlink `%s'", path); 204d347a0daSSam Leffler slink[llen] = '\0'; 205*5f5598b1SEd Maste cur->symlink = estrdup(slink); 206d347a0daSSam Leffler } 207d347a0daSSam Leffler } 208688aaa09SJung-uk Kim assert(first != NULL); 209688aaa09SJung-uk Kim if (join == NULL) 210688aaa09SJung-uk Kim for (cur = first->next; cur != NULL; cur = cur->next) 211d347a0daSSam Leffler cur->first = first; 212d347a0daSSam Leffler if (closedir(dirp) == -1) 213688aaa09SJung-uk Kim err(1, "Can't closedir `%s/%s'", root, dir); 214d347a0daSSam Leffler return (first); 215d347a0daSSam Leffler } 216d347a0daSSam Leffler 217d347a0daSSam Leffler static fsnode * 218688aaa09SJung-uk Kim create_fsnode(const char *root, const char *path, const char *name, 219688aaa09SJung-uk Kim struct stat *stbuf) 220d347a0daSSam Leffler { 221d347a0daSSam Leffler fsnode *cur; 222d347a0daSSam Leffler 223*5f5598b1SEd Maste cur = ecalloc(1, sizeof(*cur)); 224*5f5598b1SEd Maste cur->path = estrdup(path); 225*5f5598b1SEd Maste cur->name = estrdup(name); 226*5f5598b1SEd Maste cur->inode = ecalloc(1, sizeof(*cur->inode)); 227688aaa09SJung-uk Kim cur->root = root; 228d347a0daSSam Leffler cur->type = stbuf->st_mode & S_IFMT; 229d347a0daSSam Leffler cur->inode->nlink = 1; 230d347a0daSSam Leffler cur->inode->st = *stbuf; 2317b03d164SEd Maste if (stampst.st_ino) { 2327b03d164SEd Maste cur->inode->st.st_atime = stampst.st_atime; 2337b03d164SEd Maste cur->inode->st.st_mtime = stampst.st_mtime; 2347b03d164SEd Maste cur->inode->st.st_ctime = stampst.st_ctime; 2357b03d164SEd Maste #if HAVE_STRUCT_STAT_ST_MTIMENSEC 2367b03d164SEd Maste cur->inode->st.st_atimensec = stampst.st_atimensec; 2377b03d164SEd Maste cur->inode->st.st_mtimensec = stampst.st_mtimensec; 2387b03d164SEd Maste cur->inode->st.st_ctimensec = stampst.st_ctimensec; 2397b03d164SEd Maste #endif 2407b03d164SEd Maste #if HAVE_STRUCT_STAT_BIRTHTIME 2417b03d164SEd Maste cur->inode->st.st_birthtime = stampst.st_birthtime; 2427b03d164SEd Maste cur->inode->st.st_birthtimensec = stampst.st_birthtimensec; 2437b03d164SEd Maste #endif 2447b03d164SEd Maste } 245d347a0daSSam Leffler return (cur); 246d347a0daSSam Leffler } 247d347a0daSSam Leffler 248d347a0daSSam Leffler /* 24901a0f853SOlivier Houchard * free_fsnodes -- 25001a0f853SOlivier Houchard * Removes node from tree and frees it and all of 2513df5ecacSUlrich Spörlein * its descendants. 25201a0f853SOlivier Houchard */ 25301a0f853SOlivier Houchard void 25401a0f853SOlivier Houchard free_fsnodes(fsnode *node) 25501a0f853SOlivier Houchard { 25601a0f853SOlivier Houchard fsnode *cur, *next; 25701a0f853SOlivier Houchard 25801a0f853SOlivier Houchard assert(node != NULL); 25901a0f853SOlivier Houchard 26001a0f853SOlivier Houchard /* for ".", start with actual parent node */ 26101a0f853SOlivier Houchard if (node->first == node) { 26201a0f853SOlivier Houchard assert(node->name[0] == '.' && node->name[1] == '\0'); 26301a0f853SOlivier Houchard if (node->parent) { 26401a0f853SOlivier Houchard assert(node->parent->child == node); 26501a0f853SOlivier Houchard node = node->parent; 26601a0f853SOlivier Houchard } 26701a0f853SOlivier Houchard } 26801a0f853SOlivier Houchard 26901a0f853SOlivier Houchard /* Find ourselves in our sibling list and unlink */ 27001a0f853SOlivier Houchard if (node->first != node) { 27101a0f853SOlivier Houchard for (cur = node->first; cur->next; cur = cur->next) { 27201a0f853SOlivier Houchard if (cur->next == node) { 27301a0f853SOlivier Houchard cur->next = node->next; 27401a0f853SOlivier Houchard node->next = NULL; 27501a0f853SOlivier Houchard break; 27601a0f853SOlivier Houchard } 27701a0f853SOlivier Houchard } 27801a0f853SOlivier Houchard } 27901a0f853SOlivier Houchard 28001a0f853SOlivier Houchard for (cur = node; cur != NULL; cur = next) { 28101a0f853SOlivier Houchard next = cur->next; 28201a0f853SOlivier Houchard if (cur->child) { 28301a0f853SOlivier Houchard cur->child->parent = NULL; 28401a0f853SOlivier Houchard free_fsnodes(cur->child); 28501a0f853SOlivier Houchard } 28601a0f853SOlivier Houchard if (cur->inode->nlink-- == 1) 28701a0f853SOlivier Houchard free(cur->inode); 28801a0f853SOlivier Houchard if (cur->symlink) 28901a0f853SOlivier Houchard free(cur->symlink); 290688aaa09SJung-uk Kim free(cur->path); 29101a0f853SOlivier Houchard free(cur->name); 29201a0f853SOlivier Houchard free(cur); 29301a0f853SOlivier Houchard } 29401a0f853SOlivier Houchard } 29501a0f853SOlivier Houchard 29601a0f853SOlivier Houchard /* 297d347a0daSSam Leffler * apply_specfile -- 298d347a0daSSam Leffler * read in the mtree(8) specfile, and apply it to the tree 299d347a0daSSam Leffler * at dir,parent. parameters in parent on equivalent types 300d347a0daSSam Leffler * will be changed to those found in specfile, and missing 301d347a0daSSam Leffler * entries will be added. 302d347a0daSSam Leffler */ 303d347a0daSSam Leffler void 30401a0f853SOlivier Houchard apply_specfile(const char *specfile, const char *dir, fsnode *parent, int speconly) 305d347a0daSSam Leffler { 306d347a0daSSam Leffler struct timeval start; 307d347a0daSSam Leffler FILE *fp; 308d347a0daSSam Leffler NODE *root; 309d347a0daSSam Leffler 310d347a0daSSam Leffler assert(specfile != NULL); 311d347a0daSSam Leffler assert(parent != NULL); 312d347a0daSSam Leffler 313d347a0daSSam Leffler if (debug & DEBUG_APPLY_SPECFILE) 314d347a0daSSam Leffler printf("apply_specfile: %s, %s %p\n", specfile, dir, parent); 315d347a0daSSam Leffler 316d347a0daSSam Leffler /* read in the specfile */ 317d347a0daSSam Leffler if ((fp = fopen(specfile, "r")) == NULL) 318d347a0daSSam Leffler err(1, "Can't open `%s'", specfile); 319d347a0daSSam Leffler TIMER_START(start); 32043e8dbd3SBrooks Davis root = spec(fp); 321d347a0daSSam Leffler TIMER_RESULTS(start, "spec"); 322d347a0daSSam Leffler if (fclose(fp) == EOF) 323d347a0daSSam Leffler err(1, "Can't close `%s'", specfile); 324d347a0daSSam Leffler 325d347a0daSSam Leffler /* perform some sanity checks */ 326d347a0daSSam Leffler if (root == NULL) 327d347a0daSSam Leffler errx(1, "Specfile `%s' did not contain a tree", specfile); 328d347a0daSSam Leffler assert(strcmp(root->name, ".") == 0); 329d347a0daSSam Leffler assert(root->type == F_DIR); 330d347a0daSSam Leffler 331d347a0daSSam Leffler /* merge in the changes */ 33201a0f853SOlivier Houchard apply_specdir(dir, root, parent, speconly); 33301a0f853SOlivier Houchard 33410d64b77SEd Maste free_nodes(root); 335d347a0daSSam Leffler } 336d347a0daSSam Leffler 337d347a0daSSam Leffler static void 33801a0f853SOlivier Houchard apply_specdir(const char *dir, NODE *specnode, fsnode *dirnode, int speconly) 339d347a0daSSam Leffler { 340d347a0daSSam Leffler char path[MAXPATHLEN + 1]; 341d347a0daSSam Leffler NODE *curnode; 342d347a0daSSam Leffler fsnode *curfsnode; 343d347a0daSSam Leffler 344d347a0daSSam Leffler assert(specnode != NULL); 345d347a0daSSam Leffler assert(dirnode != NULL); 346d347a0daSSam Leffler 347d347a0daSSam Leffler if (debug & DEBUG_APPLY_SPECFILE) 348d347a0daSSam Leffler printf("apply_specdir: %s %p %p\n", dir, specnode, dirnode); 349d347a0daSSam Leffler 350d347a0daSSam Leffler if (specnode->type != F_DIR) 351d347a0daSSam Leffler errx(1, "Specfile node `%s/%s' is not a directory", 352d347a0daSSam Leffler dir, specnode->name); 353d347a0daSSam Leffler if (dirnode->type != S_IFDIR) 354d347a0daSSam Leffler errx(1, "Directory node `%s/%s' is not a directory", 355d347a0daSSam Leffler dir, dirnode->name); 356d347a0daSSam Leffler 357d347a0daSSam Leffler apply_specentry(dir, specnode, dirnode); 358d347a0daSSam Leffler 35901a0f853SOlivier Houchard /* Remove any filesystem nodes not found in specfile */ 36001a0f853SOlivier Houchard /* XXX inefficient. This is O^2 in each dir and it would 36101a0f853SOlivier Houchard * have been better never to have walked this part of the tree 36201a0f853SOlivier Houchard * to begin with 36301a0f853SOlivier Houchard */ 36401a0f853SOlivier Houchard if (speconly) { 36501a0f853SOlivier Houchard fsnode *next; 36601a0f853SOlivier Houchard assert(dirnode->name[0] == '.' && dirnode->name[1] == '\0'); 36701a0f853SOlivier Houchard for (curfsnode = dirnode->next; curfsnode != NULL; curfsnode = next) { 36801a0f853SOlivier Houchard next = curfsnode->next; 36901a0f853SOlivier Houchard for (curnode = specnode->child; curnode != NULL; 37001a0f853SOlivier Houchard curnode = curnode->next) { 37101a0f853SOlivier Houchard if (strcmp(curnode->name, curfsnode->name) == 0) 37201a0f853SOlivier Houchard break; 37301a0f853SOlivier Houchard } 37401a0f853SOlivier Houchard if (curnode == NULL) { 37501a0f853SOlivier Houchard if (debug & DEBUG_APPLY_SPECONLY) { 37601a0f853SOlivier Houchard printf("apply_specdir: trimming %s/%s %p\n", dir, curfsnode->name, curfsnode); 37701a0f853SOlivier Houchard } 37801a0f853SOlivier Houchard free_fsnodes(curfsnode); 37901a0f853SOlivier Houchard } 38001a0f853SOlivier Houchard } 38101a0f853SOlivier Houchard } 38201a0f853SOlivier Houchard 383d347a0daSSam Leffler /* now walk specnode->child matching up with dirnode */ 384d347a0daSSam Leffler for (curnode = specnode->child; curnode != NULL; 385d347a0daSSam Leffler curnode = curnode->next) { 386d347a0daSSam Leffler if (debug & DEBUG_APPLY_SPECENTRY) 387d347a0daSSam Leffler printf("apply_specdir: spec %s\n", 388d347a0daSSam Leffler curnode->name); 389d347a0daSSam Leffler for (curfsnode = dirnode->next; curfsnode != NULL; 390d347a0daSSam Leffler curfsnode = curfsnode->next) { 391d347a0daSSam Leffler #if 0 /* too verbose for now */ 392d347a0daSSam Leffler if (debug & DEBUG_APPLY_SPECENTRY) 393d347a0daSSam Leffler printf("apply_specdir: dirent %s\n", 394d347a0daSSam Leffler curfsnode->name); 395d347a0daSSam Leffler #endif 396d347a0daSSam Leffler if (strcmp(curnode->name, curfsnode->name) == 0) 397d347a0daSSam Leffler break; 398d347a0daSSam Leffler } 399d347a0daSSam Leffler if (snprintf(path, sizeof(path), "%s/%s", 400d347a0daSSam Leffler dir, curnode->name) >= sizeof(path)) 401d347a0daSSam Leffler errx(1, "Pathname too long."); 402d347a0daSSam Leffler if (curfsnode == NULL) { /* need new entry */ 403d347a0daSSam Leffler struct stat stbuf; 404d347a0daSSam Leffler 405d347a0daSSam Leffler /* 406d347a0daSSam Leffler * don't add optional spec entries 407d347a0daSSam Leffler * that lack an existing fs entry 408d347a0daSSam Leffler */ 409d347a0daSSam Leffler if ((curnode->flags & F_OPT) && 410d347a0daSSam Leffler lstat(path, &stbuf) == -1) 411d347a0daSSam Leffler continue; 412d347a0daSSam Leffler 413d347a0daSSam Leffler /* check that enough info is provided */ 414d347a0daSSam Leffler #define NODETEST(t, m) \ 415d347a0daSSam Leffler if (!(t)) \ 416d347a0daSSam Leffler errx(1, "`%s': %s not provided", path, m) 417d347a0daSSam Leffler NODETEST(curnode->flags & F_TYPE, "type"); 418d347a0daSSam Leffler NODETEST(curnode->flags & F_MODE, "mode"); 419d347a0daSSam Leffler /* XXX: require F_TIME ? */ 420d347a0daSSam Leffler NODETEST(curnode->flags & F_GID || 421d347a0daSSam Leffler curnode->flags & F_GNAME, "group"); 422d347a0daSSam Leffler NODETEST(curnode->flags & F_UID || 423d347a0daSSam Leffler curnode->flags & F_UNAME, "user"); 42401a0f853SOlivier Houchard /* if (curnode->type == F_BLOCK || curnode->type == F_CHAR) 42501a0f853SOlivier Houchard NODETEST(curnode->flags & F_DEV, 42601a0f853SOlivier Houchard "device number");*/ 427d347a0daSSam Leffler #undef NODETEST 428d347a0daSSam Leffler 429d347a0daSSam Leffler if (debug & DEBUG_APPLY_SPECFILE) 430d347a0daSSam Leffler printf("apply_specdir: adding %s\n", 431d347a0daSSam Leffler curnode->name); 432d347a0daSSam Leffler /* build minimal fsnode */ 433d347a0daSSam Leffler memset(&stbuf, 0, sizeof(stbuf)); 434d347a0daSSam Leffler stbuf.st_mode = nodetoino(curnode->type); 435d347a0daSSam Leffler stbuf.st_nlink = 1; 436d347a0daSSam Leffler stbuf.st_mtime = stbuf.st_atime = 437d347a0daSSam Leffler stbuf.st_ctime = start_time.tv_sec; 438d347a0daSSam Leffler #if HAVE_STRUCT_STAT_ST_MTIMENSEC 439d347a0daSSam Leffler stbuf.st_mtimensec = stbuf.st_atimensec = 440d347a0daSSam Leffler stbuf.st_ctimensec = start_time.tv_nsec; 441d347a0daSSam Leffler #endif 442688aaa09SJung-uk Kim curfsnode = create_fsnode(".", ".", curnode->name, 443688aaa09SJung-uk Kim &stbuf); 444d347a0daSSam Leffler curfsnode->parent = dirnode->parent; 445d347a0daSSam Leffler curfsnode->first = dirnode; 446d347a0daSSam Leffler curfsnode->next = dirnode->next; 447d347a0daSSam Leffler dirnode->next = curfsnode; 448d347a0daSSam Leffler if (curfsnode->type == S_IFDIR) { 449d347a0daSSam Leffler /* for dirs, make "." entry as well */ 450688aaa09SJung-uk Kim curfsnode->child = create_fsnode(".", ".", ".", 451688aaa09SJung-uk Kim &stbuf); 452d347a0daSSam Leffler curfsnode->child->parent = curfsnode; 453d347a0daSSam Leffler curfsnode->child->first = curfsnode->child; 454d347a0daSSam Leffler } 455d347a0daSSam Leffler if (curfsnode->type == S_IFLNK) { 456d347a0daSSam Leffler assert(curnode->slink != NULL); 457d347a0daSSam Leffler /* for symlinks, copy the target */ 458*5f5598b1SEd Maste curfsnode->symlink = estrdup(curnode->slink); 459d347a0daSSam Leffler } 460d347a0daSSam Leffler } 461d347a0daSSam Leffler apply_specentry(dir, curnode, curfsnode); 462d347a0daSSam Leffler if (curnode->type == F_DIR) { 463d347a0daSSam Leffler if (curfsnode->type != S_IFDIR) 464d347a0daSSam Leffler errx(1, "`%s' is not a directory", path); 465d347a0daSSam Leffler assert (curfsnode->child != NULL); 46601a0f853SOlivier Houchard apply_specdir(path, curnode, curfsnode->child, speconly); 467d347a0daSSam Leffler } 468d347a0daSSam Leffler } 469d347a0daSSam Leffler } 470d347a0daSSam Leffler 471d347a0daSSam Leffler static void 472d347a0daSSam Leffler apply_specentry(const char *dir, NODE *specnode, fsnode *dirnode) 473d347a0daSSam Leffler { 474d347a0daSSam Leffler 475d347a0daSSam Leffler assert(specnode != NULL); 476d347a0daSSam Leffler assert(dirnode != NULL); 477d347a0daSSam Leffler 478d347a0daSSam Leffler if (nodetoino(specnode->type) != dirnode->type) 479d347a0daSSam Leffler errx(1, "`%s/%s' type mismatch: specfile %s, tree %s", 480d347a0daSSam Leffler dir, specnode->name, inode_type(nodetoino(specnode->type)), 481d347a0daSSam Leffler inode_type(dirnode->type)); 482d347a0daSSam Leffler 483d347a0daSSam Leffler if (debug & DEBUG_APPLY_SPECENTRY) 484d347a0daSSam Leffler printf("apply_specentry: %s/%s\n", dir, dirnode->name); 485d347a0daSSam Leffler 486d347a0daSSam Leffler #define ASEPRINT(t, b, o, n) \ 487d347a0daSSam Leffler if (debug & DEBUG_APPLY_SPECENTRY) \ 488d347a0daSSam Leffler printf("\t\t\tchanging %s from " b " to " b "\n", \ 489d347a0daSSam Leffler t, o, n) 490d347a0daSSam Leffler 491d347a0daSSam Leffler if (specnode->flags & (F_GID | F_GNAME)) { 492d347a0daSSam Leffler ASEPRINT("gid", "%d", 493d347a0daSSam Leffler dirnode->inode->st.st_gid, specnode->st_gid); 494d347a0daSSam Leffler dirnode->inode->st.st_gid = specnode->st_gid; 495d347a0daSSam Leffler } 496d347a0daSSam Leffler if (specnode->flags & F_MODE) { 497d347a0daSSam Leffler ASEPRINT("mode", "%#o", 498d347a0daSSam Leffler dirnode->inode->st.st_mode & ALLPERMS, specnode->st_mode); 499d347a0daSSam Leffler dirnode->inode->st.st_mode &= ~ALLPERMS; 500d347a0daSSam Leffler dirnode->inode->st.st_mode |= (specnode->st_mode & ALLPERMS); 501d347a0daSSam Leffler } 502d347a0daSSam Leffler /* XXX: ignoring F_NLINK for now */ 503d347a0daSSam Leffler if (specnode->flags & F_SIZE) { 504d347a0daSSam Leffler ASEPRINT("size", "%lld", 505d347a0daSSam Leffler (long long)dirnode->inode->st.st_size, 506d347a0daSSam Leffler (long long)specnode->st_size); 507d347a0daSSam Leffler dirnode->inode->st.st_size = specnode->st_size; 508d347a0daSSam Leffler } 509d347a0daSSam Leffler if (specnode->flags & F_SLINK) { 510d347a0daSSam Leffler assert(dirnode->symlink != NULL); 511d347a0daSSam Leffler assert(specnode->slink != NULL); 512d347a0daSSam Leffler ASEPRINT("symlink", "%s", dirnode->symlink, specnode->slink); 513d347a0daSSam Leffler free(dirnode->symlink); 514*5f5598b1SEd Maste dirnode->symlink = estrdup(specnode->slink); 515d347a0daSSam Leffler } 516d347a0daSSam Leffler if (specnode->flags & F_TIME) { 517d347a0daSSam Leffler ASEPRINT("time", "%ld", 518d347a0daSSam Leffler (long)dirnode->inode->st.st_mtime, 519d347a0daSSam Leffler (long)specnode->st_mtimespec.tv_sec); 520d347a0daSSam Leffler dirnode->inode->st.st_mtime = specnode->st_mtimespec.tv_sec; 521d347a0daSSam Leffler dirnode->inode->st.st_atime = specnode->st_mtimespec.tv_sec; 522d347a0daSSam Leffler dirnode->inode->st.st_ctime = start_time.tv_sec; 523d347a0daSSam Leffler #if HAVE_STRUCT_STAT_ST_MTIMENSEC 524d347a0daSSam Leffler dirnode->inode->st.st_mtimensec = specnode->st_mtimespec.tv_nsec; 525d347a0daSSam Leffler dirnode->inode->st.st_atimensec = specnode->st_mtimespec.tv_nsec; 526d347a0daSSam Leffler dirnode->inode->st.st_ctimensec = start_time.tv_nsec; 527d347a0daSSam Leffler #endif 528d347a0daSSam Leffler } 529d347a0daSSam Leffler if (specnode->flags & (F_UID | F_UNAME)) { 530d347a0daSSam Leffler ASEPRINT("uid", "%d", 531d347a0daSSam Leffler dirnode->inode->st.st_uid, specnode->st_uid); 532d347a0daSSam Leffler dirnode->inode->st.st_uid = specnode->st_uid; 533d347a0daSSam Leffler } 534d347a0daSSam Leffler #if HAVE_STRUCT_STAT_ST_FLAGS 535d347a0daSSam Leffler if (specnode->flags & F_FLAGS) { 536d347a0daSSam Leffler ASEPRINT("flags", "%#lX", 537d347a0daSSam Leffler (unsigned long)dirnode->inode->st.st_flags, 538d347a0daSSam Leffler (unsigned long)specnode->st_flags); 539d347a0daSSam Leffler dirnode->inode->st.st_flags = specnode->st_flags; 540d347a0daSSam Leffler } 541d347a0daSSam Leffler #endif 54201a0f853SOlivier Houchard /* if (specnode->flags & F_DEV) { 54301a0f853SOlivier Houchard ASEPRINT("rdev", "%#llx", 54401a0f853SOlivier Houchard (unsigned long long)dirnode->inode->st.st_rdev, 54501a0f853SOlivier Houchard (unsigned long long)specnode->st_rdev); 54601a0f853SOlivier Houchard dirnode->inode->st.st_rdev = specnode->st_rdev; 54701a0f853SOlivier Houchard }*/ 548d347a0daSSam Leffler #undef ASEPRINT 549d347a0daSSam Leffler 550d347a0daSSam Leffler dirnode->flags |= FSNODE_F_HASSPEC; 551d347a0daSSam Leffler } 552d347a0daSSam Leffler 553d347a0daSSam Leffler 554d347a0daSSam Leffler /* 555d347a0daSSam Leffler * dump_fsnodes -- 556688aaa09SJung-uk Kim * dump the fsnodes from `cur' 557d347a0daSSam Leffler */ 558d347a0daSSam Leffler void 559688aaa09SJung-uk Kim dump_fsnodes(fsnode *root) 560d347a0daSSam Leffler { 561d347a0daSSam Leffler fsnode *cur; 562d347a0daSSam Leffler char path[MAXPATHLEN + 1]; 563d347a0daSSam Leffler 564688aaa09SJung-uk Kim printf("dump_fsnodes: %s %p\n", root->path, root); 565d347a0daSSam Leffler for (cur = root; cur != NULL; cur = cur->next) { 566688aaa09SJung-uk Kim if (snprintf(path, sizeof(path), "%s/%s", cur->path, 567688aaa09SJung-uk Kim cur->name) >= (int)sizeof(path)) 568d347a0daSSam Leffler errx(1, "Pathname too long."); 569d347a0daSSam Leffler 570d347a0daSSam Leffler if (debug & DEBUG_DUMP_FSNODES_VERBOSE) 571d347a0daSSam Leffler printf("cur=%8p parent=%8p first=%8p ", 572d347a0daSSam Leffler cur, cur->parent, cur->first); 573d347a0daSSam Leffler printf("%7s: %s", inode_type(cur->type), path); 574d347a0daSSam Leffler if (S_ISLNK(cur->type)) { 575d347a0daSSam Leffler assert(cur->symlink != NULL); 576d347a0daSSam Leffler printf(" -> %s", cur->symlink); 577d347a0daSSam Leffler } else { 578d347a0daSSam Leffler assert (cur->symlink == NULL); 579d347a0daSSam Leffler } 580d347a0daSSam Leffler if (cur->inode->nlink > 1) 581d347a0daSSam Leffler printf(", nlinks=%d", cur->inode->nlink); 582d347a0daSSam Leffler putchar('\n'); 583d347a0daSSam Leffler 584d347a0daSSam Leffler if (cur->child) { 585d347a0daSSam Leffler assert (cur->type == S_IFDIR); 586688aaa09SJung-uk Kim dump_fsnodes(cur->child); 587d347a0daSSam Leffler } 588d347a0daSSam Leffler } 589688aaa09SJung-uk Kim printf("dump_fsnodes: finished %s/%s\n", root->path, root->name); 590d347a0daSSam Leffler } 591d347a0daSSam Leffler 592d347a0daSSam Leffler 593d347a0daSSam Leffler /* 594d347a0daSSam Leffler * inode_type -- 595d347a0daSSam Leffler * for a given inode type `mode', return a descriptive string. 59601a0f853SOlivier Houchard * for most cases, uses inotype() from mtree/misc.c 597d347a0daSSam Leffler */ 598d347a0daSSam Leffler const char * 599d347a0daSSam Leffler inode_type(mode_t mode) 600d347a0daSSam Leffler { 601d347a0daSSam Leffler if (S_ISREG(mode)) 602d347a0daSSam Leffler return ("file"); 603d347a0daSSam Leffler if (S_ISLNK(mode)) 604d347a0daSSam Leffler return ("symlink"); 605d347a0daSSam Leffler if (S_ISDIR(mode)) 606d347a0daSSam Leffler return ("dir"); 607d347a0daSSam Leffler if (S_ISLNK(mode)) 608d347a0daSSam Leffler return ("link"); 609d347a0daSSam Leffler if (S_ISFIFO(mode)) 610d347a0daSSam Leffler return ("fifo"); 611d347a0daSSam Leffler if (S_ISSOCK(mode)) 612d347a0daSSam Leffler return ("socket"); 613d347a0daSSam Leffler /* XXX should not happen but handle them */ 614d347a0daSSam Leffler if (S_ISCHR(mode)) 615d347a0daSSam Leffler return ("char"); 616d347a0daSSam Leffler if (S_ISBLK(mode)) 617d347a0daSSam Leffler return ("block"); 618d347a0daSSam Leffler return ("unknown"); 619d347a0daSSam Leffler } 620d347a0daSSam Leffler 621d347a0daSSam Leffler 622d347a0daSSam Leffler /* 623d347a0daSSam Leffler * link_check -- 62401a0f853SOlivier Houchard * return pointer to fsinode matching `entry's st_ino & st_dev if it exists, 625d347a0daSSam Leffler * otherwise add `entry' to table and return NULL 626d347a0daSSam Leffler */ 62701a0f853SOlivier Houchard /* This was borrowed from du.c and tweaked to keep an fsnode 62801a0f853SOlivier Houchard * pointer instead. -- dbj@netbsd.org 62901a0f853SOlivier Houchard */ 6301f0ed3c0SBrooks Davis fsinode * 631d347a0daSSam Leffler link_check(fsinode *entry) 632d347a0daSSam Leffler { 63301a0f853SOlivier Houchard static struct entry { 63401a0f853SOlivier Houchard fsinode *data; 63501a0f853SOlivier Houchard } *htable; 63601a0f853SOlivier Houchard static int htshift; /* log(allocated size) */ 63701a0f853SOlivier Houchard static int htmask; /* allocated size - 1 */ 63801a0f853SOlivier Houchard static int htused; /* 2*number of insertions */ 63901a0f853SOlivier Houchard int h, h2; 64001a0f853SOlivier Houchard uint64_t tmp; 64101a0f853SOlivier Houchard /* this constant is (1<<64)/((1+sqrt(5))/2) 64201a0f853SOlivier Houchard * aka (word size)/(golden ratio) 64301a0f853SOlivier Houchard */ 64401a0f853SOlivier Houchard const uint64_t HTCONST = 11400714819323198485ULL; 64501a0f853SOlivier Houchard const int HTBITS = 64; 646d347a0daSSam Leffler 64701a0f853SOlivier Houchard /* Never store zero in hashtable */ 64801a0f853SOlivier Houchard assert(entry); 649d347a0daSSam Leffler 65001a0f853SOlivier Houchard /* Extend hash table if necessary, keep load under 0.5 */ 65101a0f853SOlivier Houchard if (htused<<1 >= htmask) { 65201a0f853SOlivier Houchard struct entry *ohtable; 653d347a0daSSam Leffler 65401a0f853SOlivier Houchard if (!htable) 65501a0f853SOlivier Houchard htshift = 10; /* starting hashtable size */ 65601a0f853SOlivier Houchard else 65701a0f853SOlivier Houchard htshift++; /* exponential hashtable growth */ 658d347a0daSSam Leffler 65901a0f853SOlivier Houchard htmask = (1 << htshift) - 1; 66001a0f853SOlivier Houchard htused = 0; 66101a0f853SOlivier Houchard 66201a0f853SOlivier Houchard ohtable = htable; 663*5f5598b1SEd Maste htable = ecalloc(htmask+1, sizeof(*htable)); 66401a0f853SOlivier Houchard /* populate newly allocated hashtable */ 66501a0f853SOlivier Houchard if (ohtable) { 66601a0f853SOlivier Houchard int i; 66701a0f853SOlivier Houchard for (i = 0; i <= htmask>>1; i++) 66801a0f853SOlivier Houchard if (ohtable[i].data) 66901a0f853SOlivier Houchard link_check(ohtable[i].data); 67001a0f853SOlivier Houchard free(ohtable); 67101a0f853SOlivier Houchard } 67201a0f853SOlivier Houchard } 67301a0f853SOlivier Houchard 67401a0f853SOlivier Houchard /* multiplicative hashing */ 67501a0f853SOlivier Houchard tmp = entry->st.st_dev; 67601a0f853SOlivier Houchard tmp <<= HTBITS>>1; 67701a0f853SOlivier Houchard tmp |= entry->st.st_ino; 67801a0f853SOlivier Houchard tmp *= HTCONST; 67901a0f853SOlivier Houchard h = tmp >> (HTBITS - htshift); 68001a0f853SOlivier Houchard h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */ 68101a0f853SOlivier Houchard 68201a0f853SOlivier Houchard /* open address hashtable search with double hash probing */ 68301a0f853SOlivier Houchard while (htable[h].data) { 68401a0f853SOlivier Houchard if ((htable[h].data->st.st_ino == entry->st.st_ino) && 68501a0f853SOlivier Houchard (htable[h].data->st.st_dev == entry->st.st_dev)) { 68601a0f853SOlivier Houchard return htable[h].data; 68701a0f853SOlivier Houchard } 68801a0f853SOlivier Houchard h = (h + h2) & htmask; 68901a0f853SOlivier Houchard } 69001a0f853SOlivier Houchard 69101a0f853SOlivier Houchard /* Insert the current entry into hashtable */ 69201a0f853SOlivier Houchard htable[h].data = entry; 69301a0f853SOlivier Houchard htused++; 69401a0f853SOlivier Houchard return NULL; 695d347a0daSSam Leffler } 696